# Best-of-Both-Worlds Algorithms for Partial Monitoring

arXiv: https://arxiv.org/abs/2207.14550 · HTML: https://mlsanity.com/paper/2207.14550/

## Key facts

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

## Builds on (most cited first, 20 of 20)

- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition](https://mlsanity.com/paper/2006.05606/) (2020)
- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1702.06103/) (2017)
- [An Information-Theoretic Approach to Minimax Regret in Partial Monitoring](https://mlsanity.com/paper/1902.00470/) (2019)
- [The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition](https://mlsanity.com/paper/2106.04117/) (2021)
- [Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00873/) (2022)
- [Exploration by Optimisation in Partial Monitoring](https://mlsanity.com/paper/1907.05772/) (2019)
- [Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits](https://mlsanity.com/paper/2201.11921/) (2022)
- [A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00557/) (2022)
- [Cleaning up the neighborhood: A full classification for adversarial partial monitoring](https://mlsanity.com/paper/1805.09247/) (2018)
- [Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds](https://mlsanity.com/paper/2206.06810/) (2022)
- [Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring](https://mlsanity.com/paper/1509.09011/) (2015)
- [Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring](https://mlsanity.com/paper/2006.09668/) (2020)
- [Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedback](https://mlsanity.com/paper/2206.07908/) (2022)

## Built on by (most cited first, 19 of 19)

- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms](https://mlsanity.com/paper/2302.13534/) (2023)
- [Best of Both Worlds Policy Optimization](https://mlsanity.com/paper/2302.09408/) (2023)
- [Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds](https://mlsanity.com/paper/2305.17301/) (2023)
- [Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds](https://mlsanity.com/paper/2302.12370/) (2023)
- [Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm](https://mlsanity.com/paper/2303.06825/) (2023)
- [Best-of-Both-Worlds Algorithms for Linear Contextual Bandits](https://mlsanity.com/paper/2312.15433/) (2023)
- [Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds](https://mlsanity.com/paper/2403.00715/) (2024)
- [Follow-the-Perturbed-Leader with Fr'echet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worlds](https://mlsanity.com/paper/2403.05134/) (2024)
- [Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2502.17625/) (2025)
- [uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs](https://mlsanity.com/paper/2410.03284/) (2024)
- [Thompson Sampling in Partially Observable Contextual Bandits](https://mlsanity.com/paper/2402.10289/) (2024)
- [LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2403.03219/) (2024)
- [Randomized Confidence Bounds for Stochastic Partial Monitoring](https://mlsanity.com/paper/2402.05002/) (2024)
- [Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring](https://mlsanity.com/paper/2402.08321/) (2024)
- [A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worlds](https://mlsanity.com/paper/2405.20028/) (2024)
- [Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2312.16489/) (2023)
- [Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback](https://mlsanity.com/paper/2510.17103/) (2025)
- [Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring](https://mlsanity.com/paper/2510.19158/) (2025)

## 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.