# Exploration by Optimisation in Partial Monitoring

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2019.

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

- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Best-of-Both-Worlds Algorithms for Partial Monitoring](https://mlsanity.com/paper/2207.14550/) (2022)
- [Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds](https://mlsanity.com/paper/2305.17301/) (2023)
- [Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regret](https://mlsanity.com/paper/2202.10997/) (2022)
- [Scale Free Adversarial Multi Armed Bandits](https://mlsanity.com/paper/2106.04700/) (2021)
- [Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications](https://mlsanity.com/paper/2302.03683/) (2023)
- [Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability](https://mlsanity.com/paper/2410.05117/) (2024)
- [A Bit Better? Quantifying Information for Bandit Learning](https://mlsanity.com/paper/2102.09488/) (2021)
- [Gaussian Imagination in Bandit Learning](https://mlsanity.com/paper/2201.01902/) (2022)
- [Isotuning With Applications To Scale-Free Online Learning](https://mlsanity.com/paper/2112.14586/) (2021)
- [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)
- [Decision Making in Hybrid Environments: A Model Aggregation Approach](https://mlsanity.com/paper/2502.05974/) (2025)
- [Regret Minimization via Saddle Point Optimization](https://mlsanity.com/paper/2403.10379/) (2024)
- [Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays](https://mlsanity.com/paper/2110.13400/) (2021)
- [Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring](https://mlsanity.com/paper/2510.19158/) (2025)
- [The Sample Complexity of Multiclass and Sparse Contextual Bandits](https://mlsanity.com/paper/2605.29645/) (2026)
- [On the Minimax Regret in Online Ranking with Top-k Feedback](https://mlsanity.com/paper/2309.02425/) (2023)
- [Bayesian Optimization for General Reaction Conditions](https://mlsanity.com/paper/2502.18966/) (2025)
- [Efficient contextual partial monitoring with general function approximation](https://mlsanity.com/paper/2610.19804/) (2026)

## Abstract (arXiv)

We provide a simple and efficient algorithm for adversarial k-action d-outcome non-degenerate locally observable partial monitoring game for which the n-round minimax regret is bounded by 6(d+1) k3/2 √n log(k), matching the best known information-theoretic upper bound. The same algorithm also achieves near-optimal regret for full information, bandit and globally observable games.