# Fast Rates for Bandit PAC Multiclass Classification

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 26 references that are in the map.
- First posted on arXiv 18 Jun 2024.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Limits of Private Learning with Access to Public Data](https://mlsanity.com/paper/1910.11519/) (2019)
- [The price of bandit information in multiclass online classification](https://mlsanity.com/paper/1302.1043/) (2013)
- [Multiclass Online Learnability under Bandit Feedback](https://mlsanity.com/paper/2308.04620/) (2023)
- [The Real Price of Bandit Information in Multiclass Classification](https://mlsanity.com/paper/2405.10027/) (2024)

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

- [Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back](https://mlsanity.com/paper/2511.12659/) (2025)
- [From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards](https://mlsanity.com/paper/2502.09257/) (2025)
- [PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting](https://mlsanity.com/paper/2605.25678/) (2026)
- [The Sample Complexity of Multiclass and Sparse Contextual Bandits](https://mlsanity.com/paper/2605.29645/) (2026)
- [Policy Gradient with Adaptive Entropy Annealing for Continual Fine-Tuning](https://mlsanity.com/paper/2602.14078/) (2026)
- [Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenon](https://mlsanity.com/paper/2609.29694/) (2026)

## Abstract (arXiv)

We study multiclass PAC learning with bandit feedback, where inputs are classified into one of K possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic (varepsilon,δ)-PAC version of the problem, with sample complexity of Obig( (operatornamepoly(K) + 1 / varepsilon2) log (|H| / δ) big) for any finite hypothesis class H. In terms of the leading dependence on varepsilon, this improves upon existing bounds for the problem, that are of the form O(K/varepsilon2). We also provide an extension of this result to general classes and establish similar sample complexity bounds in which log |H| is replaced by the Natarajan dimension. This matches the optimal rate in the full-information version of the problem and resolves an open question studied by Daniely, Sabato, Ben-David, and Shalev-Shwartz (2011) who demonstrated that the multiplicative price of bandit feedback in realizable PAC learning is Theta(K). We complement this by revealing a stark contrast with the agnostic case, where the price of bandit feedback is only O(1) as varepsilon → 0. Our algorithm utilizes a stochastic optimization technique to minimize a log-barrier potential based on Frank-Wolfe updates for computing a low-variance exploration distribution over the hypotheses, and is made computationally efficient provided access to an ERM oracle over H.