Research map / Bandits and online learning / Online convex optimization and games
Adaptive Regret for Bandits Made Possible: Two Queries Suffice
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.
Shows that strongly adaptive regret for multi-armed bandits can be achieved with only two queries per round (StABL), matching the lower bound, and extends it to bandit convex optimization with three queries.
Problem
Strongly adaptive regret minimization in bandits is expensive because prior algorithms need O(log T) or O(log log T) queries per round, while a known lower bound shows near-optimal adaptive regret is impossible with one query per round.
Approach
Runs an EXP3-type meta-algorithm over geometric-interval EXP3 base learners, using a second query sampled from a mixture of the meta-learner's and base learners' distributions to build bounded-variance unbiased loss estimators for both levels.
Key results
- StABL achieves O~(sqrt(nI)) strongly adaptive regret for n-armed bandits with two queries per round, matching the known lower bound up to log factors (bound O(sqrt(nI log n) log^1.5 T)).
- For bandit convex optimization, three queries per round give O(dGD sqrt(I) log^2 T) strongly adaptive regret, independent of condition number in the leading term.
- In the synthetic switching-best-arm experiment, StABL adapts after the best arm changes while EXP3 degrades in later intervals; StABL outperforms EXP3 on SPHERE hyperparameter/algorithm selection.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use uniform distribution for the observation query instead of StABL's designed distribution (ablation) | StABL · Learning from expert advice, volatile environments | moving-average reward | Hurt |
| use only one history length of 1024 instead of varying history lengths (ablation) | StABL · Learning from expert advice, random change intervals | moving-average reward | Hurt |
| use a linear surrogate loss and make one additional observation at the played point (ablation) | Strongly Adaptive BCO Learner · Bandit convex optimization | number of queries per round: three to two | Helped |
Surprising findings
- Two queries per round suffice for near-optimal strongly adaptive regret in MAB, despite a prior lower bound implying one query is insufficient.
- Using rewards instead of losses in the algorithms empirically performs better.
Limitations
- Regret bound carries an extra log^1.5 T factor, worse than the sqrt(log T) of full-information results.
- BCO algorithm uses two additional queries while MAB uses one; reducing BCO queries is open.
- Extension to dynamic regret in the bandit setting is not addressed.
Experimental setup
Datasets: synthetic expert-advice reward sequences BBOB black-box optimization functions
Benchmarks: synthetic learning-with-experts environment (N=30, T=4096) BBOB SPHERE function algorithm selection (d=32, 64)
Metrics: moving average reward log objective performance profile score
Baselines: EXP3 EXP3 with uniform exploration StABL Naive StABL Single Scale uniform random EFLH (Lu and Hazan)
Builds on: EXP3 Follow-the-Leading-History (FLH) geometric covering intervals (Daniely et al. 2015) multi-point bandit feedback
Closest papers by meaning
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.91)
- Non-stationary Bandit Convex Optimization: A Comprehensive Study (NeurIPS 2025 · similarity 0.90)
- Bandits with Ranking Feedback (NeurIPS 2024 · similarity 0.90)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.90)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.90)
- Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update (NeurIPS 2025 · similarity 0.90)
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.