# A Complete Characterization of Learnability for Stochastic Noisy Bandits

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 39 references that are in the map.
- First posted on arXiv 12 Oct 2024.

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

- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [Low-Rank Generalized Linear Bandit Problems](https://mlsanity.com/paper/2006.02948/) (2020)
- [Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting](https://mlsanity.com/paper/1902.01520/) (2019)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient](https://mlsanity.com/paper/2301.08215/) (2023)
- [Lipschitz Bandits with Batched Feedback](https://mlsanity.com/paper/2110.09722/) (2021)
- [Optimal Learning for Structured Bandits](https://mlsanity.com/paper/2007.07302/) (2020)
- [A Novel Confidence-Based Algorithm for Structured Bandits](https://mlsanity.com/paper/2005.11593/) (2020)

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

- [On the Hardness of Bandit Learning](https://mlsanity.com/paper/2506.14746/) (2025)
- [A Complete Characterization of Learnability for Adversarial Noisy Bandits](https://mlsanity.com/paper/2605.09200/) (2026)

## Abstract (arXiv)

We study the stochastic noisy bandit problem with an unknown reward function f^* in a known function class F. Formally, a model M maps arms π to a probability distribution M(π) of reward. A model class M is a collection of models. For each model M, define its mean reward function fM(π)=mathbbEr ~ M(π)[r]. In the bandit learning problem, we proceed in rounds, pulling one arm π each round and observing a reward sampled from M(π). With knowledge of M, supposing that the true model M∈ M, the objective is to identify an arm hatπ of near-maximal mean reward fM(hatπ) with high probability in a bounded number of rounds. If this is possible, then the model class is said to be learnable. Importantly, a result of citehanneke2023bandit shows there exist model classes for which learnability is undecidable. However, the model class they consider features deterministic rewards, and they raise the question of whether learnability is decidable for classes containing sufficiently noisy models. For the first time, we answer this question in the positive by giving a complete characterization of learnability for model classes with arbitrary noise. In addition to that, we also describe the full spectrum of possible optimal query complexities. Further, we prove adaptivity is sometimes necessary to achieve the optimal query complexity. Last, we revisit an important complexity measure for interactive decision making, the Decision-Estimation-Coefficient citepfoster2021statistical,foster2023tight, and propose a new variant of the DEC which also characterizes learnability in this setting.