Research map / Bandits and online learning / Online convex optimization and games
Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies multiclass online learning with bandit feedback in the mistake bound model, giving nearly tight bounds on the price of bandit feedback, adaptive vs oblivious adversaries, and randomized vs deterministic learners.
Problem
Quantifying how bandit feedback (only correct/incorrect signal), adaptive adversaries, and learner randomness affect optimal mistake bounds in realizable adversarial online multiclass classification.
Approach
Shows the bandit-to-full-information mistake bound gap for randomized learners is O(k) via a tree-of-copies reduction to prediction with expert advice, and derives a tight Theta(k(log_k n + r)) bound for expert advice against adaptive adversaries using minimax duality and an exponential potential function.
Key results
- Optimal randomized bandit mistake bound against adaptive adversary is at most O(k) times the full-information randomized bound: optimal bandit bound <= 6k * optimal full-info bound (Theorem: full info vs bandit).
- For prediction with expert advice, the randomized adaptive bound is Theta(k(log_k n + r)), with the upper bound k log_k n + 2kr.
- Deterministic expert-advice bound is Theta(k(log(n/k) + r + 1)), and randomized-vs-deterministic and adaptive-vs-oblivious gaps are Theta~(k) in the bandit setting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace full-information feedback with bandit feedback | Randomized online multiclass classification · Realizable pattern classes | optimal mistake bound: at most 6 k times; a lower bound of \Omega(\optfullrand(\mathcal{H}) \cdot |\mathcal{Y}|) holds for some classes | Mixed |
| allow the adversary to adapt rather than require it to be oblivious | Randomized bandit classification · Bandit feedback; some pattern class with k labels | optimal mistake bound: \Omega(\optbanditobl(\mathcal{P}) \cdot |\mathcal{Y}|) | Hurt |
| remove learner randomization | Bandit classification · Some concept class with k labels | optimal mistake bound: \Omega(\optbanditadap(\mathcal{H}) \cdot |\mathcal{Y}|) | Hurt |
| use randomized learning against an adaptive adversary instead of a deterministic learner | Bandit prediction with expert advice · n experts, k labels, r inconsistencies | optimal mistake bound: \Theta \mleft(k (\log(n/k) + r + 1) \mright) versus \Theta \mleft( k (\log_{k} n + r) \mright) | Helped |
| replace an adaptive adversary with an oblivious adversary | Randomized bandit prediction with expert advice · n experts, k labels, r inconsistencies | optimal mistake bound: adaptive: \Theta \mleft(k(\log_k n + r^\star)\mright); oblivious: O \mleft(k(\log_k n + r^\star)\mright), \Omega \mleft( | Mixed |
Surprising findings
- The Bandit Littlestone dimension does not quantify the optimal randomized bandit mistake bound: some classes have randomized adaptive bound O(k) while deterministic bound is much larger, so the square-root relation holds only roughly.
Limitations
- Lower bound against oblivious adversary is tight only when r = O(log_k n); the oblivious case for large r remains open.
- Lower bound for adaptive vs oblivious uses pattern classes rather than concept classes; concept-class version left open.
- Leading constants are not identified; results are up to logarithmic factors in some gaps.
Experimental setup
Metrics: worst-case expected mistake bound
Baselines: deterministic bandit learners (Daniely and Helbertal; Long) regret bound of Daniely et al. (sqrt(T k d))
Builds on: Littlestone dimension Weighted Majority RandSOA Bandit Littlestone dimension
Closest papers by meaning
- Online Learning in the Random-Order Model (ICML 2025 · similarity 0.87)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.87)
- Online Linear Classification with Massart Noise (ICML 2025 · similarity 0.87)
- Bandit and Delayed Feedback in Online Structured Prediction (NeurIPS 2025 · similarity 0.87)
- From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards (NeurIPS 2025 · similarity 0.87)
- Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.