On the Hardness of Bandit Learning

Nataly BrukhimAldo PacchianoMiro DudíkRobert E. Schapire

article2025COLT0 citations

Establishes fundamental theoretical limits of structured bandit learning by proving that no combinatorial dimension can characterize learnability and demonstrating that finding optimal actions can be computationally intractable even when sample complexity is minimal and standard empirical risk minimization is efficient.

Listen

Modern decision-making systems increasingly rely on multi-armed bandit algorithms to identify the best available option across diverse applications, from healthcare trials to digital content recommendation. In classical statistical learning, foundational principles establish clear mathematical limits on how much data is required to learn and how to design efficient algorithms. However, a general, unifying theory for structured bandit learning—where sampling one action provides indirect information about others—has remained elusive, leaving researchers and practitioners without standard tools to predict problem difficulty or guarantee efficient performance.

To address this foundational gap, the article investigates the fundamental boundaries of structured bandit learning, specifically focusing on which problem classes can be learned and how computationally practical algorithms can be designed. The authors employ rigorous mathematical proofs and learning-theoretic analyses, evaluating both noise-free feedback and Gaussian noise environments across finite and structured action spaces. They establish theoretical lower and upper bounds on query complexity (the number of exploratory trials needed to find a near-optimal action), computational runtimes, and cumulative regret.

The article demonstrates several key findings that challenge conventional wisdom. First, it proves that no combinatorial dimension satisfying standard finite properties can universally characterize bandit learnability, unlike in standard classification where such measures predict data efficiency. Second, the authors uncover severe computational barriers by constructing a reward class where identifying the optimal action theoretically requires at most two queries, yet no algorithm can find it in polynomial time unless standard computational complexity assumptions fail (specifically, unless RP equals NP). Crucially, this hardness persists even when the problem admits fast standard optimization procedures. Third, the analysis shows that observation noise creates severe phase transitions: certain problems that require only a single query in the absence of noise become completely unlearnable with moderate noise, while sufficiently low noise preserves the query efficiency of the noise-free regime. Finally, the authors prove a fundamental tradeoff between exploratory efficiency and reward maximization, showing that any algorithm achieving optimal query complexity necessarily incurs large, linear cumulative regret.

These findings have direct implications for the risk and cost of deploying automated decision-making systems. They show that relying on standard statistical heuristics or off-the-shelf optimization routines can lead to severe computational bottlenecks and excessive real-world losses during exploration. System architects must recognize that achieving fast best-option identification and minimizing operational regret are fundamentally incompatible objectives, requiring a deliberate choice between rapid discovery and ongoing performance.

Organizations developing interactive learning platforms should discontinue the search for a single universal metric to measure bandit complexity and instead adopt tailored, structure-aware evaluations. System designs should explicitly separate pure exploration workflows from operational reward-maximization pipelines rather than expecting a single algorithm to optimize both simultaneously. Further research is recommended to characterize intermediate noise regimes and develop practical problem-specific approximations, providing practitioners with actionable confidence bounds before deploying bandit systems in high-stakes environments.

Boston University Broad Institute Institute for Advanced Study Microsoft classification classification models efficient algorithm bandit learnability bandit learning stochastic bandits

arXiv: 2506.14746

Paper: Best Arm Identification in Multi-Armed Bandits, Jean-Yves Audibert et al. (2010). This seminal paper introduces the theoretical foundation and hardness metrics for best-arm identification in multi-armed bandits that the source paper directly generalizes to arbitrary function classes.
Paper: A Theory of the Learnable, Leslie G. Valiant (1984). This foundational work establishes the PAC learning framework that the source paper seeks to mirror and adapt for structured bandit learnability.
Paper: Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, Sébastien Bubeck et al. (2012). This text provides a comprehensive theoretical survey of multi-armed bandit regimes, regret minimization, and pure exploration, offering essential context for the source's structural investigations.
Paper: Introduction to Multi-Armed Bandits, Aleksandrs Slivkins (2019). This monograph introduces core analytical techniques and lower-bound formulations in multi-armed and structured bandits upon which the source builds.
Paper: Finite-time Analysis of the Multiarmed Bandit Problem, Peter Auer et al. (2002). This classic work establishes finite-time analysis and algorithmic principles for multi-armed bandits that serve as a prerequisite baseline for structured bandit learning.
Paper: Queries and concept learning, DANA ANGLUIN (1988). This foundational paper analyzes query complexity in exact and probabilistic concept learning, establishing concepts directly relevant to the source's query-complexity analysis.
Paper: Improved Algorithms for Linear Stochastic Bandits, Yasin Abbasi-Yadkori et al. (2011). This paper develops optimal algorithms and analysis for linear structured bandits, representing the primary class of structured bandit problems generalized by the source.

No sufficiently relevant recommendations were found.

Cover for On the Hardness of Bandit Learning

Abstract

We study the task of bandit learning, also known as best-arm identification, under the assumption that the true reward function f belongs to a known, but arbitrary, function class F. We seek a general theory of bandit learnability, akin to the PAC framework for classification. Our investigation is guided by the following two questions: (1) which classes F are learnable, and (2) how they are learnable. For example, in the case of binary PAC classification, learnability is fully determined by a combinatorial dimension - the VC dimension- and can be attained via a simple algorithmic principle, namely, empirical risk minimization (ERM). In contrast to classical learning-theoretic results, our findings reveal limitations of learning in structured bandits, offering insights into the boundaries of bandit learnability. First, for the question of "which", we show that the paradigm of identifying the learnable classes via a dimension-like quantity fails for bandit learning. We give a simple proof demonstrating that no combinatorial dimension can characterize bandit learnability, even in finite classes, following a standard definition of dimension introduced by Ben-David et al. (2019). For the question of "how", we prove a computational hardness result: we construct a reward function class for which at most two queries are needed to find the optimal action, yet no algorithm can do so in polynomial time unless RP=NP. We also prove that this class admits efficient algorithms for standard algorithmic operations often considered in learning theory, such as an ERM. This implies that computational hardness is in this case inherent to the task of bandit learning. Beyond these results, we investigate additional themes such as learning under noise, trade-offs between noise models, and the relationship between query complexity and regret minimization.

Topics

classification classification models efficient algorithm reward function trade online learning

Keywords

bandit learnability bandit learning stochastic bandits computational hardness regret minimization noisy query complexity decision-estimation coefficient PAC learnability sample complexity empirical risk minimization

1 Introduction
1.1 Related work
2 Query complexity of bandit learning
3 No combinatorial dimension can characterize bandit learnability
4 Hardness of bandit learning
5 Noise-free vs. noisy setting query complexity
6 Separation between regret and query complexity
6.1 Regret vs. QC: noisy case
7 Conclusion
References
A Missing proof of
A.1 Proof of
B Missing proofs of
B.1 Proof of Proposition
B.2 Proof of Theorem
B.3 Proof of Theorem
C Missing discussion and proofs of
C.1 Regret vs. QC: noise-free case
C.2 Proof of Theorem
D Useful Lemmas

Knowls

Knowl 1 — Non-Existence of Finite-Character Combinatorial Dimension for Bandit Learnability
theoretical result
Let $\mathcal{X}$ and $\mathcal{Y}$ be arbitrary sets satisfying $|\mathcal{Y}| \ge |\mathcal{X}| \ge d + 1$ for an integer $d > 2$ . A dimension $\mathcal{D}: 2^{\mathcal{Y}^\mathcal{X}} \to \mathbb{N} \cup \{\infty\}$ satisfies the finite character property if for every integer $k \in \mathbb{N}$ , there exists a shattering function $V_k : \mathcal{X}^k \times 2^{\mathcal{Y}^k} \to \{\text{YES}, \text{NO}\}$ such that $\mathcal{D}(\mathcal{F}) \ge k$ if and only if there exists a set of domain points $X \in \mathcal{X}^k$ with restricted class $\mathcal{F}|_X$ finite such that $V_k(X, \mathcal{F}|_X) = \text{YES}$ .

For any dimension $\mathcal{D}$ for bandit classes in $\mathcal{Y}^\mathcal{X}$ that satisfies the finite character property and for which there exists some $\mathcal{F} \subseteq \mathcal{Y}^\mathcal{X}$ with $\mathcal{D}(\mathcal{F}) \ge d$ , and for any $\epsilon, \delta \ge 0$ , there exists a function class $\mathcal{F}' \subseteq \mathcal{Y}^\mathcal{X}$ such that: $\mathcal{D}(\mathcal{F}') \ge d,$ yet the noise-free $(\epsilon, \delta)$ -query complexity of bandit learning $\mathcal{F}'$ satisfies: $\text{QC}^0_{\epsilon, \delta}(\mathcal{F}') \le 2.$

Consequently, no combinatorial dimension satisfying the finite character property can characterize bandit learnability or bound best-arm identification query complexity.
Knowl 2 — Computational Hardness of Bandit Learning Despite Efficient Learning Oracles
theoretical result
For every $n \in \mathbb{N}$ , there exists a finite reward function class $\mathcal{F}_n \subseteq [0, 1]^{\mathcal{A}_n}$ over an action set $\mathcal{A}_n$ of size $|\mathcal{A}_n| = 2^{n+1} + 1$ such that:
1. The noise-free $(\epsilon, \delta)$ -query complexity satisfies $\text{QC}^0_{\epsilon, \delta}(\mathcal{F}_n) \le 2$ for all $\epsilon, \delta \ge 0$ .
2. If there exists a bandit learning algorithm for every $\mathcal{F}_n$ with runtime polynomial in $n$ , then $\text{RP} = \text{NP}$ .
Furthermore, despite this computational hardness, each class $\mathcal{F}_n$ admits efficient deterministic algorithms for standard learning operations:
- Empirical Risk Minimization (Consistency): An algorithm running in time $O(n^2)$ that, given any dataset of past observations $S = \{(a_1, f(a_1)), \dots, (a_m, f(a_m))\}$ for $f \in \mathcal{F}_n$ , outputs $\hat{f} \in \mathcal{F}_n$ consistent with $S$ .
- Online Estimation: An algorithm running in time $O(n^2)$ per step that, given past observations, outputs estimators $\hat{f}_t \in \mathcal{F}_n$ achieving cumulative squared prediction error $\sum_{t=1}^T (\hat{f}_t(a_t) - f(a_t))^2 \le 3 = O(1)$ .
- Function Maximization: An algorithm running in time $\tilde{O}(n^2)$ that, given the concise $O(n^2 \log n)$ -bit description of any $f \in \mathcal{F}_n$ , finds an exact optimal action $\hat{a} \in \arg\max_{a \in \mathcal{A}_n} f(a)$ .
Knowl 3 — Incompatibility of Optimal Query Complexity and Sublinear Regret in Stochastic Bandits
theoretical result
In stochastic multi-armed bandits with unit-variance Gaussian noise $\xi \sim \mathcal{N}(0, 1)$ , for any integer $d \ge 1$ and time horizon $T \in \mathbb{N}$ , there exists a function class $\mathcal{F}$ over action space $\mathcal{A}$ such that:
1. The $(0, 1/4)$ -query complexity satisfies: $d \le \text{QC}^1_{0, 1/4}(\mathcal{F}) \le 80d.$
2. Any algorithm $\text{Alg}$ that identifies an optimal action within $T$ queries (satisfying query complexity $m^1_{\text{Alg}}(0, 1/4) \le T$ ) must incur expected cumulative regret bounded by: $\max_{f \in \mathcal{F}} \mathbb{E}_{\text{Alg}}[\text{Regret}(T, f)] \ge \frac{d}{128},$ where $\text{Regret}(T, f) = \sum_{t=1}^T (\max_{a \in \mathcal{A}} f(a) - f(a_t))$ .
3. An alternative algorithm $\text{Alg}'$ (e.g., Upper Confidence Bound restricted to uninformative candidate optimal arms) achieves sublinear regret for all $T \in \mathbb{N}$ : $\max_{f \in \mathcal{F}} \mathbb{E}_{\text{Alg}'}[\text{Regret}(T, f)] \le 8\sqrt{2T \log(T)}.$
Hence, for horizons $T = O(d^\alpha)$ with $\alpha < 2$ , no algorithm can simultaneously achieve optimal query complexity $O(d)$ and optimal sublinear regret $\tilde{O}(\sqrt{T})$ .
Knowl 4 — Phase Transition in Bandit Query Complexity Across Gaussian Noise Regimes
theoretical result
Let $\gamma_{\mathcal{F}, \epsilon} = \sup_{p \in \Delta(\mathcal{A})} \inf_{f \in \mathcal{F}} \mathbb{P}_{a \sim p}(\sup_{a^*} f(a^*) - f(a) \le \epsilon)$ denote the generalized maximin volume of a class $\mathcal{F} \subseteq [0, 1]^\mathcal{A}$ .

There exist universal constants $c, \bar{c} > 0$ such that for every integer $K \ge 2$ , there exists a reward function class $\mathcal{F} \subseteq [0, 1]^\mathcal{A}$ over an action space of size $|\mathcal{A}| = K + 1$ satisfying $\gamma_{\mathcal{F}, \epsilon} = 1/K$ for all $\epsilon \in [0, 1/2)$ , where under Gaussian noise $\mathcal{N}(0, \sigma^2)$ :
1. In the low-noise regime, if $\sigma^2 \le \frac{1}{c \log^{2/3}(K) K^{2/3}}$ , then: $\text{QC}^\sigma_{\epsilon, 1/4}(\mathcal{F}) = \text{QC}^0_{\epsilon, 0}(\mathcal{F}) = 1.$
2. In the moderate-to-high noise regime, if $\sigma^2 \ge \frac{1}{\bar{c} K^{2/3}}$ , then: $\bar{c} K^{2/3} \sigma^2 \le \text{QC}^\sigma_{\epsilon, 1/4}(\mathcal{F}) \le c \log^{2/3}(K) K^{2/3} \sigma^2.$
In particular, for small noise, $\text{QC}^\sigma_{\epsilon, 1/4}(\mathcal{F}) = 1 < \log(1/\gamma_{\mathcal{F}, \epsilon})$ , while in the high-noise regime query complexity diverges from the noise-free complexity and scales with $K^{2/3}\sigma^2$ .
Knowl 5 — Query Complexity Preservation Under Low Gaussian Noise via Trajectory Gap
theoretical result
Let $\mathcal{F} \subseteq [0, 1]^\mathcal{A}$ be a finite reward function class over a finite action space $\mathcal{A}$ . For an algorithm $\text{Alg}$ and history length $n$ , let $\Gamma_n(\text{Alg})$ be the set of partial trajectories $\tau_n = ((a_1, r_1), \dots, (a_n, r_n))$ in the support of $\text{Alg}$ . The gap of $(\text{Alg}, \mathcal{F})$ is: $\text{Gap}(\text{Alg}, \mathcal{F}) = \min_{n \in \mathbb{N}} \inf_{\tau_n \in \Gamma_n(\text{Alg})} \inf_{\substack{r \in \{f(a_n) : f \in \mathcal{F}(\tau_{n-1})\} \\ r \ne r_n}} |r - r_n|.$ The $(\epsilon, \delta')$ -gap of $\mathcal{F}$ is defined as $\text{Gap}_{\epsilon, \delta'}(\mathcal{F}) = \max_{\text{Alg} \in \mathcal{A}_{\epsilon, \delta'}} \text{Gap}(\text{Alg}, \mathcal{F})$ , where $\mathcal{A}_{\epsilon, \delta'}$ denotes all randomized algorithms achieving noise-free query complexity $\text{QC}^0_{\epsilon, \delta'}(\mathcal{F})$ .

For any $\delta, \delta' \in (0, 1)$ with $\delta > \delta' \ge 0$ , if zero-mean Gaussian noise has variance satisfying: $\sigma^2 < \frac{\text{Gap}^2_{\epsilon, \delta'}(\mathcal{F})}{4 \log\left(\frac{2\text{QC}^0_{\epsilon, \delta'}(\mathcal{F})}{\delta - \delta'}\right)},$ then the noisy query complexity satisfies: $\text{QC}^\sigma_{\epsilon, \delta}(\mathcal{F}) \le \text{QC}^0_{\epsilon, \delta'}(\mathcal{F}).$
Knowl 6 — Discontinuity and Unboundedness of Query Complexity Under Non-Zero Noise
theoretical result
For any $\epsilon \in [0, 1/2)$ , there exists a reward function class $\mathcal{F} \subseteq [0, 1]^\mathcal{A}$ over an infinite action set $\mathcal{A} = \{0\} \cup \mathbb{N}$ such that:
1. In the noiseless setting (noise variance $\sigma = 0$ ): $\text{QC}^0_{\epsilon, \delta'}(\mathcal{F}) = 1 \quad \text{for all } \delta' \in [0, 1).$
2. Under additive zero-mean Gaussian noise with any variance $\sigma > 0$ : $\text{QC}^\sigma_{\epsilon, \delta}(\mathcal{F}) = \infty \quad \text{for all } \delta \in [0, 1/2).$
This is demonstrated by functions $f_i \in \mathcal{F}$ indexed by $i \in \mathbb{N}$ , defined as $f_i(0) = 2^{-i}$ , $f_i(i) = 1$ , and $f_i(a) = 0$ for $a \notin \{0, i\}$ , where action $0$ perfectly reveals the optimal index $i$ noiselessly, but requires an unbounded number of queries to distinguish under any positive noise variance as $i \to \infty$ .
Knowl 7 — Linear Regret Lower Bound for Query-Optimal Learners in Noise-Free Bandits
theoretical result
For any integer $d \ge 1$ , precision $\epsilon \in [0, 1)$ , and parameter $\gamma \in (0, 1)$ such that $\epsilon + \gamma < 1$ , there exists a function class $\mathcal{F} \subseteq [0, 1]^\mathcal{A}$ over a binary tree action space $\mathcal{A}_{\text{tree}}$ of depth $d + 1$ (having $2^{d+1}-1$ nodes) such that:
1. The noise-free $(\epsilon, 0)$ -query complexity is exactly: $\text{QC}^0_{\epsilon, 0}(\mathcal{F}) = d.$
2. Any algorithm $\text{Alg}$ that identifies an $\epsilon$ -optimal action within $T$ queries ( $m^0_{\text{Alg}}(\epsilon, 0) \le T$ for $T \ge d$ ) incurs cumulative regret bounded by: $\max_{f \in \mathcal{F}} \text{Regret}_{\text{Alg}}(T, f) \ge d,$ where $\text{Regret}_{\text{Alg}}(T, f) = \sum_{t=1}^T (\max_{a \in \mathcal{A}} f(a) - f(a_t))$ .
3. There exists a policy $\text{Alg}'$ (which repeatedly pulls the root action) that guarantees: $\max_{f \in \mathcal{F}} \text{Regret}_{\text{Alg}'}(T, f) \le (\epsilon + \gamma)T \quad \text{for all } T \in \mathbb{N}.$
Thus, achieving the optimal query complexity $d$ forces the learner to explore zero-reward branch actions, preventing query-optimal algorithms from avoiding a linear penalty in $d$ .
Knowl 8 — Query Complexity of Best-Arm Identification in Structured Bandits
definition
Let $\mathcal{A}$ be an action set, $\mathcal{F} \subseteq [0, 1]^\mathcal{A}$ a known reward function class, and $f^* \in \mathcal{F}$ the true underlying reward function. In each round $t = 1, \dots, T$ , a learner queries an action $a_t \in \mathcal{A}$ and observes reward $r_t = f^*(a_t) + \xi_t$ , where $\xi_t \sim \mathcal{N}(0, \sigma^2)$ under Gaussian noise (or $\xi_t = 0$ in the noise-free setting $\sigma = 0$ ).

The class $\mathcal{F}$ is bandit-learnable if there exists an algorithm $\text{Alg}$ and a function $m: (0, 1)^2 \to \mathbb{N}$ such that for any $f^* \in \mathcal{F}$ and any $\epsilon, \delta > 0$ , after at most $m(\epsilon, \delta)$ queries, $\text{Alg}$ outputs an action $\hat{a} \in \mathcal{A}$ satisfying: $\mathbb{P}\left(f^*(\hat{a}) \ge \sup_{a \in \mathcal{A}} f^*(a) - \epsilon\right) \ge 1 - \delta.$

The $(\epsilon, \delta)$ -query complexity of $\mathcal{F}$ under Gaussian noise $\mathcal{N}(0, \sigma^2)$ , denoted $\text{QC}^\sigma_{\epsilon, \delta}(\mathcal{F})$ , is defined as: $\text{QC}^\sigma_{\epsilon, \delta}(\mathcal{F}) = \min_{\text{Alg}} m^\sigma_{\text{Alg}}(\epsilon, \delta),$ where the minimum is taken over all valid bandit learning algorithms $\text{Alg}$ for $\mathcal{F}$ .

Coverage note — No substantial contributed theoretical results were omitted. Intermediate technical lemmas supporting the main theorems (Lemmas 11, 18, 19, 20, 24, 25, 26, 27, 28, 29, and 30) were omitted as they serve solely as proof steps.

References

1.Kareem Amin, Michael Kearns, and Umar Syed. Bandits, query learning, and the haystack dimension. In Proceedings of the 24th Annual Conference on Learning Theory, pages 87–106. JMLR Workshop and Conference Proceedings, 2011.
2.Peter L Bartlett, Philip M Long, and Robert C Williamson. Fat-shattering and the learnability of real-valued functions. In Proceedings of the seventh annual conference on Computational learning theory, pages 299–310, 1994.
3.Shai Ben-David, Nicolo Cesa-Bianchi, and Philip M Long. Characterizations of learnability for classes of {O,..., n}-valued functions. In Proceedings of the fifth annual workshop on Computational learning theory, pages 333–340, 1992.
4.Shai Ben-David, D'avid P'al, and Shai Shalev-Shwartz. Agnostic online learning. In COLT, volume 3, page 1, 2009.
5.Shai Ben-David, Pavel Hrubeš, Shay Moran, Amir Shpilka, and Amir Yehudayoff. Learnability can be undecidable. Nature Machine Intelligence, 1(1):44–48, 2019.
6.Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4):929–965, 1989.
7.Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability. In Annual Symposium on Foundations of Computer Science, FOCS, 2022.
8.Nataly Brukhim, Miro Dudik, Aldo Pacchiano, and Robert E Schapire. A unified model and dimension for interactive estimation. Advances in Neural Information Processing Systems, 36:64589–64617, 2023.
9.S'ebastien Bubeck, R'emi Munos, and Gilles Stoltz. Pure exploration in finitely-armed and continuous-armed bandits. Theoretical Computer Science, 412(19):1832–1852, 2011.
10.S'ebastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multiarmed bandit problems. Foundations and Trends® in Machine Learning, 5(1):1–122, 2012.
11.Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the erm principle. J. Mach. Learn. Res., 16(1):2377–2404, 2015.
12.Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487, 2021.
13.Dylan J Foster, Noah Golowich, and Yanjun Han. Tight guarantees for interactive decision making with the decision-estimation coefficient. In The Thirty Sixth Annual Conference on Learning Theory, pages 3969–4043. PMLR, 2023.
14.Aur'elien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998–1027. PMLR, 2016.
15.John T Gill III. Computational complexity of probabilistic turing machines. In Proceedings of the sixth annual ACM symposium on Theory of computing, pages 91–95, 1974.
16.Steve Hanneke and Kun Wang. A complete characterization of learnability for stochastic noisy bandits. arXiv preprint arXiv:2410.09597, 2024.
17.Steve Hanneke and Liu Yang. Bandit learnability can be undecidable. In The Thirty Sixth Annual Conference on Learning Theory, pages 5813–5849. PMLR, 2023.
18.Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems, 34:13406–13418, 2021.
19.Emilie Kaufmann, Olivier Capp'e, and Aur'elien Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1–42, 2016.
20.Tor Lattimore and Csaba Szepesv'ari. Bandit algorithms. Cambridge University Press, 2020.
21.Gene Li, Pritish Kamath, Dylan J Foster, and Nati Srebro. Understanding the eluder dimension. Advances in Neural Information Processing Systems, 35:23737–23750, 2022.
22.Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2:285–318, 1988.
23.Balas K. Natarajan and Prasad Tadepalli. Two new frameworks for learning. In ICML, pages 402–415, 1988.
24.Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning via sequential complexities. J. Mach. Learn. Res., 16(1):155–186, 2015.
25.Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
26.Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984.
27.Leslie G Valiant and Vijay V Vazirani. Np is as easy as detecting unique solutions. In Proceedings of the seventeenth annual ACM symposium on Theory of computing, pages 458–463, 1985.
28.Vladimir Vapnik. Inductive principles of the search for empirical dependences (methods based on weak convergence of probability measures). In COLT, pages 3–21, 1989.
29.Vladimir Vapnik and Alexey Chervonenkis. Theory of Pattern Recognition. Nauka, Moscow, 1974.
30.Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123–6135, 2020.

Citation

MLA

Brukhim, N., et al. “On the Hardness of Bandit Learning”. arXiv, 2025, http://arxiv.org/abs/2506.14746v1.

APA

Brukhim, N., Pacchiano, A., Dudik, M., & Schapire, R. (2025). On the Hardness of Bandit Learning. arXiv. http://arxiv.org/abs/2506.14746v1

Chicago

Brukhim, N., A. Pacchiano, M. Dudik, and R. Schapire. 2025. “On the Hardness of Bandit Learning”. arXiv. http://arxiv.org/abs/2506.14746v1.

Harvard

Brukhim, N. et al. (2025) “On the Hardness of Bandit Learning”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2506.14746v1.

Vancouver

1. Brukhim N, Pacchiano A, Dudik M, Schapire R (2025) On the Hardness of Bandit Learning. arXiv

BibTeX

@article{brukhim2025the,
  title = {On the Hardness of Bandit Learning},
  author = {Brukhim, Nataly and Pacchiano, Aldo and Dudik, Miroslav and Schapire, Robert},
  year = {2025},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2506.14746v1},
  eprint = {2506.14746}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

On the Hardness of Bandit Learning

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Non-Existence of Finite-Character Combinatorial Dimension for Bandit Learnability

Knowl 2 — Computational Hardness of Bandit Learning Despite Efficient Learning Oracles

Knowl 3 — Incompatibility of Optimal Query Complexity and Sublinear Regret in Stochastic Bandits

Knowl 4 — Phase Transition in Bandit Query Complexity Across Gaussian Noise Regimes

Knowl 5 — Query Complexity Preservation Under Low Gaussian Noise via Trajectory Gap

Knowl 6 — Discontinuity and Unboundedness of Query Complexity Under Non-Zero Noise

Knowl 7 — Linear Regret Lower Bound for Query-Optimal Learners in Noise-Free Bandits

Knowl 8 — Query Complexity of Best-Arm Identification in Structured Bandits

References

Citation

BibTeX

Access the Paper