# Cleaning up the neighborhood: A full classification for adversarial partial monitoring

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2018.

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

- [Best-of-Both-Worlds Algorithms for Partial Monitoring](https://mlsanity.com/paper/2207.14550/) (2022)
- [An α-regret analysis of Adversarial Bilateral Trade](https://mlsanity.com/paper/2210.06846/) (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)
- [Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications](https://mlsanity.com/paper/2302.03683/) (2023)
- [Monitored Markov Decision Processes](https://mlsanity.com/paper/2402.06819/) (2024)
- [Multi-Fidelity Multi-Armed Bandits Revisited](https://mlsanity.com/paper/2306.07761/) (2023)
- [Online Learning with Off-Policy Feedback](https://mlsanity.com/paper/2207.08956/) (2022)
- [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)
- [Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring](https://mlsanity.com/paper/2510.19158/) (2025)
- [Online Conformal Prediction Beyond Feedback](https://mlsanity.com/paper/2608.07139/) (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)
- [On Mitigating Affinity Bias through Bandits with Evolving Biased Feedback](https://mlsanity.com/paper/2503.05662/) (2025)
- [Efficient Logistic Regression with Mixture of Sigmoids](https://mlsanity.com/paper/2604.02920/) (2026)

## Abstract (arXiv)

Partial monitoring is a generalization of the well-known multi-armed bandit framework where the loss is not directly observed by the learner. We complete the classification of finite adversarial partial monitoring to include all games, solving an open problem posed by Bartok et al. [2014]. Along the way we simplify and improve existing algorithms and correct errors in previous analyses. Our second contribution is a new algorithm for the class of games studied by Bartok [2013] where we prove upper and lower regret bounds that shed more light on the dependence of the regret on the game structure.