# Best Arm Identification for Stochastic Rising Bandits

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 32 references that are in the map.
- First posted on arXiv 15 Feb 2023.

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

- [AutoGluon-Tabular: Robust and Accurate AutoML for Structured Data](https://mlsanity.com/paper/2003.06505/) (2020)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [Efficient Automatic CASH via Rising Bandits](https://mlsanity.com/paper/2012.04371/) (2020)
- [Non-Stationary Bandits with Habituation and Recovery Dynamics](https://mlsanity.com/paper/1707.08423/) (2017)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Bandits with many optimal arms](https://mlsanity.com/paper/2103.12452/) (2021)
- [ARLO: A Framework for Automated Reinforcement Learning](https://mlsanity.com/paper/2205.10416/) (2022)

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

- [Put CASH on Bandits: A Max K-Armed Problem for Automated Machine Learning](https://mlsanity.com/paper/2505.05226/) (2025)
- [Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem](https://mlsanity.com/paper/2511.10619/) (2025)
- [Combinatorial Rising Bandits](https://mlsanity.com/paper/2412.00798/) (2024)
- [Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting](https://mlsanity.com/paper/2409.05980/) (2024)
- [Beyond Static Bias: Adaptive Multi-Fidelity Bandits with Improving Proxies](https://mlsanity.com/paper/2605.08558/) (2026)
- [Trajectory-Aware Best-Arm Identification for Local Search Allocation in Bayesian Optimization and Beyond](https://mlsanity.com/paper/2605.31050/) (2026)

## Abstract (arXiv)

Stochastic Rising Bandits (SRBs) model sequential decision-making problems in which the expected reward of the available options increases every time they are selected. This setting captures a wide range of scenarios in which the available options are learning entities whose performance improves (in expectation) over time (e.g., online best model selection). While previous works addressed the regret minimization problem, this paper focuses on the fixed-budget Best Arm Identification (BAI) problem for SRBs. In this scenario, given a fixed budget of rounds, we are asked to provide a recommendation about the best option at the end of the identification process. We propose two algorithms to tackle the above-mentioned setting, namely R-UCBE, which resorts to a UCB-like approach, and R-SR, which employs a successive reject procedure. Then, we prove that, with a sufficiently large budget, they provide guarantees on the probability of properly identifying the optimal option at the end of the learning process and on the simple regret. Furthermore, we derive a lower bound on the error probability, matched by our R-SR (up to constants), and illustrate how the need for a sufficiently large budget is unavoidable in the SRB setting. Finally, we numerically validate the proposed algorithms in both synthetic and realistic environments.