Research map / Bandits and online learning / Multi-armed bandits
Best Arm Identification for Stochastic Rising Bandits
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.
Proposes two fixed-budget best-arm-identification algorithms (UCBE-SRB, a UCB-like method, and Successive Reject-SRB, a phase-based method) for stochastic rising bandits, with error-probability and simple-regret guarantees and a matching lower bound for the latter.
Problem
Fixed-budget best arm identification when each arm's expected reward is non-decreasing and concave in its number of pulls, so the optimal arm is defined at the end of the budget T and can change with T.
Approach
Uses a pessimistic sliding-window mean estimator and an optimistic linear-extrapolation estimator (exploiting concavity) to build a UCB-like algorithm and a successive-reject algorithm with budget-based phase lengths that need no knowledge of the reward-growth function; proves an error lower bound matched by the successive-reject method.
Key results
- On the synthetic SRB with K=5, UCBE-SRB clearly outperforms all baselines in error probability for budgets before T=185, while SR-SRB reaches error below 0.05 for T>1000.
- SR-SRB attains the lowest simple regret among compared algorithms in the synthetic setting, while UCBE-SRB suffers large simple regret despite identifying the optimal arm after T=185.
- A lower bound shows any fixed-budget algorithm suffers error at least of order exp(-T/(sigma^2 log(K) H_{1,2})), matched up to constants by SR-SRB.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use UCB with an optimistic estimator | UCB · Synthetic Gaussian SRB, budgets before T = 185 | empirical error probability | Helped |
| use UCB | UCB · Synthetic Gaussian SRB, T > 185 | empirical error probability | Helped |
| use Successive Reject | Successive Reject · Synthetic Gaussian SRB, T > 1000 | empirical error probability | Helped |
| use Successive Reject instead of UCB | Synthetic Gaussian SRB · Synthetic Gaussian SRB | empirical simple regret | Helped |
| vary exploration parameter a across {a*/50, a*/10, a*, 10a*, 50a*} (ablation) | UCB · Synthetic Gaussian SRB, T ≤ 185 | empirical error probability | Mixed |
| vary exploration parameter a across {a*/50, a*/10, a*, 10a*, 50a*} (ablation) | UCB · Synthetic Gaussian SRB, T > 185 | empirical error probability | No clear effect |
Surprising findings
- UCBE-SRB identifies the optimal arm promptly after T=185 yet has large simple regret because it over-exploits suboptimal arms and pulls the optimal arm too few times.
Limitations
- UCBE-SRB requires knowing the complexity index H_{1,eta}(T) to set its exploration parameter a, which is hard to obtain in practice.
- Guarantees require a sufficiently large budget T, and the minimum budget may be unavoidable; the paper does not give an algorithm balancing error probability and minimum budget.
- Analysis assumes concave, non-decreasing expected rewards with polynomial increments; results may not hold outside this assumption.
Experimental setup
Datasets: synthetic Gaussian stochastic rising bandit (K=5, sigma=0.01) realistic online best model selection environment (appendix)
Benchmarks: synthetic Gaussian SRB (K=5) realistic online best model selection
Metrics: empirical error probability empirical simple regret
Baselines: Uniform Uniform-smooth UCB-Bubeck SR-Bubeck ProbOne ETC-Cella Rest-Sure-Cella
Builds on: Successive Rejects (Audibert and Bubeck 2010) Rising bandits (Metelli et al. 2022) Rest-Sure (Chen and others)
Closest papers by meaning
- Stochastic Rising Bandits (ICML 2022 · similarity 0.93)
- Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.91)
- Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.90)
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.89)
- Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification? (NeurIPS 2026 · similarity 0.89)
- Fixed Confidence Best Arm Identification in the Bayesian Setting (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.