mlsanityData to 7 Oct 2026

Best-of-Both-Worlds Algorithms for Partial Monitoring

arXiv 2207.14550 ↗First posted 29 Jul 2022cs.LG stat.MLcited by 19

Not on the map. Why?

Abstract (arXiv)

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(m2 k4 log(T) log(kPi T) / Deltamin) in the stochastic regime and O(m k2/3 √T log(T) log kPi) in the adversarial regime, where T is the number of rounds, m is the maximum number of distinct observations per action, Deltamin is the minimum suboptimality gap, and kPi is the number of Pareto optimal actions. Moreover, we show that for globally observable games, the regret is O(cG2 log(T) log(kPi T) / Deltamin2) in the stochastic regime and O((cG2 log(T) log(kPi T))1/3 T2/3) in the adversarial regime, where cG 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.

Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). Builds on 20 of its 45 references that are in the map. First posted on arXiv 29 Jul 2022.

Builds on

20 of 45 references.

References · 20

  1. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  2. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  3. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  4. 2014A Second-order Bound with Excess Lossescited by 91
  5. 2015Online Learning with Feedback Graphs: Beyond Banditscited by 79
  6. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  7. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  8. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  9. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  10. 2019An Information-Theoretic Approach to Minimax Regret in Partial Monitoringcited by 41
  11. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  12. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
8 more
  1. 2019Exploration by Optimisation in Partial Monitoringcited by 20
  2. 2022Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Banditscited by 17
  3. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  4. 2018Cleaning up the neighborhood: A full classification for adversarial partial monitoringcited by 16
  5. 2022Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Boundscited by 12
  6. 2015Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoringcited by 10
  7. 2020Analysis and Design of Thompson Sampling for Stochastic Partial Monitoringcited by 9
  8. 2022Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedbackcited by 6

Built on by

Cited by year

Citing papers per year: 2023: 8; 2024: 8; 2025: 3.

19 papers.

Sort:

  1. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  2. 2023Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Armscited by 18
  3. 2023Best of Both Worlds Policy Optimizationcited by 17
  4. 2023Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worldscited by 15
  5. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 13
  6. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 11
  7. 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
  8. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 10
  9. 2024Follow-the-Perturbed-Leader with Fr'echet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worldscited by 9
  10. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 9
  11. 2024uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABscited by 7
  12. 2024Thompson Sampling in Partially Observable Contextual Banditscited by 5
7 more
  1. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  2. 2024Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoringcited by 3
  3. 2024A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worldscited by 3
  4. 2023Best-of-Both-Worlds Linear Contextual Banditscited by 2
  5. 2024Randomized Confidence Bounds for Stochastic Partial Monitoringcited by 2
  6. 2025Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedbackcited by 2
  7. 2025Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoringcited by 1