Research map / Bandits and online learning / Multi-armed bandits
Multi-Armed Bandits With Best-Action Queries
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.
Resolves an open question on multi-armed bandits with best-action queries under bandit feedback: correlated/adversarial rewards give Omega(sqrt(T-k)) regret (no gain), while i.i.d. stochastic rewards allow O~(min{T n/k, sqrt(n(T-k))}) regret via querying then UCB-V, with a matching lower bound.
Problem
Whether best-action queries (an oracle revealing the best arm in a round, with a budget of k queries) improve regret in multi-armed bandits under bandit feedback, where full-feedback results of Russo et al. (2024) do not directly apply.
Approach
Shows that correlated rewards make queries useless under bandit feedback (Omega(sqrt(T-k)) lower bound via two correlated instances), while for i.i.d. rewards the negative regret of a query is tied to arm variance; the algorithm spends k queries up front and then runs UCB-V, with a matching lower bound using near-1 Bernoulli instances.
Key results
- Stochastic correlated (and adversarial) bandit-feedback setting: any algorithm with k best-action queries incurs Omega(sqrt(T-k)) regret, so queries cannot improve the O~(sqrt(T)) rate beyond the sqrt(T-k) term.
- Stochastic i.i.d. setting: querying the best arm for the first k rounds followed by UCB-V achieves O(min{nT log T / k, sqrt(nT log T)}) regret.
- A matching lower bound Omega(min{Tn/k, sqrt(n(T-k))}) holds for i.i.d. stochastic bandits with k <= T/C best-action queries, up to log factors.
Surprising findings
- Under correlated rewards, best-action queries provide essentially no regret benefit under bandit feedback, unlike the full-feedback setting.
- Higher-variance arms make queries more valuable: the gap between dynamic and static optimum grows with arm variance, so the lower-bound instances in i.i.d. case must use means near the boundary.
Limitations
- Upper bound for i.i.d. case uses a simple strategy that spends all queries up front and discards query information.
- Lower bounds and algorithm are for the i.i.d. or correlated stochastic models; the adversarial case is covered only via the correlated lower bound.
Experimental setup
Metrics: cumulative regret
Baselines: UCB1 standard adversarial regret minimizer (sqrt(T) regret)
Builds on: UCB-V UCB1 Russo et al. 2024 best-action queries full-feedback
Closest papers by meaning
- Bandits with Ranking Feedback (NeurIPS 2024 · similarity 0.91)
- Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.90)
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.90)
- Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · similarity 0.89)
- Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting (NeurIPS 2024 · similarity 0.89)
- Online Learning with Sublinear Best-Action Queries (NeurIPS 2024 · similarity 0.89)
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.