# A Complete Characterization of Learnability for Adversarial Noisy Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 23 references that are in the map.
- First posted on arXiv 9 May 2026.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2002.00287/) (2020)
- [The Many Faces of Exponential Weights in Online Learning](https://mlsanity.com/paper/1802.07543/) (2018)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient](https://mlsanity.com/paper/2301.08215/) (2023)
- [Volumetric Spanners: an Efficient Exploration Basis for Learning](https://mlsanity.com/paper/1312.6214/) (2013)
- [The entropic barrier: a simple and optimal universal self-concordant barrier](https://mlsanity.com/paper/1412.1587/) (2014)
- [Scale Free Adversarial Multi Armed Bandits](https://mlsanity.com/paper/2106.04700/) (2021)
- [A Complete Characterization of Learnability for Stochastic Noisy Bandits](https://mlsanity.com/paper/2410.09597/) (2024)
- [On the Hardness of Bandit Learning](https://mlsanity.com/paper/2506.14746/) (2025)

## Abstract (arXiv)

We study adversarial noisy bandits given a known function class F. In each round, the adversary selects a function f ∈ F, the learner chooses an arm, and then observes a noisy reward determined by the chosen arm and the function f. The goal is to minimize the cumulative regret R(T), defined as the difference between the learner's performance and that of the best fixed arm in hindsight over T rounds. We say that a function class F is learnable if there exists an algorithm achieving sublinear regret. Our main result is a complete characterization of learnability for adversarial noisy bandits. The characterization is given in terms of a convexified variant of the generalized maximin volume introduced by Hanneke and Wang (2025): namely, the generalized maximin volume evaluated on the convex hull operatornameco(mathcal F). We prove that mathcal F is learnable if and only if this convexified generalized maximin volume is positive at every scale. This condition characterizes learnability against both oblivious and adaptive adversaries, showing in particular that these two notions of learnability are equivalent in the noisy bandit setting. Our analysis reveals that the key complexity measure is closely connected to two new combinatorial notions, hitting set and distribution covering number, which may be of independent interest. These results establish the first complete characterization of learnability for adversarial noisy bandits.