Best-of-Both-Worlds Algorithms for Partial Monitoring

Abstract

This study considers the partial monitoring problem with $k$-actions and $d$-outcomes and provides the first best-of-both-worlds algorithms, whose regrets are favorably bounded both in the stochastic and adversarial regimes. In particular, we show that for non-degenerate locally observable games, the regret is $O(m^2{k}^4\log (T)\log (k_{\Pi }T)/{\Delta }_{\min })$ in the stochastic regime and $O(m{k}^{2/3}\sqrt{T\log (T)\log k_{\Pi }})$ in the adversarial regime, where $T$ is the number of rounds, $m$ is the maximum number of distinct observations per action, ${\Delta }_{\min }$ is the minimum suboptimality gap, and $k_{\Pi }$ is the number of Pareto optimal actions. Moreover, we show that for globally observable games, the regret is $O(c_{\mathcal{G}}^2\log (T)\log (k_{\Pi }T)/{\Delta }_{\min }^2)$ in the stochastic regime and $O((c_{\mathcal{G}}^2\log (T)\log (k_{\Pi }T){)}^{1/3}{T}^{2/3})$ in the adversarial regime, where $c_{\mathcal{G}}$ is a game-dependent constant. We also provide regret bounds for a stochastic regime with adversarial corruptions. Our algorithms are based on the follow-the-regularized-leader framework and are inspired by the approach of exploration by optimization and the adaptive learning rate in the field of online learning with feedback graphs.

31 pages

References in corpus (8)

• An Information-Theoretic Approach to Minimax Regret in Partial Monitoring
• Online Learning with Feedback Graphs: Beyond Bandits
• An Adaptive Algorithm for Finite Stochastic Partial Monitoring
• Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs
• Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds
• Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedback
• Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits
• A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs