Best Arm Identification with Minimal Regret

Дата публикации: 17-08-2026 20:26:00

Motivated by real-world applications that necessitate responsible experimentation, we introduce the problem of best arm identification (BAI) with minimal regret. This variant of the multi-armed bandit problem elegantly amalgamates two of its most ubiquitous objectives: regret minimization and BAI. More precisely, the agent's goal is to identify the best arm with a prescribed confidence level $\delta$, while minimizing the cumulative regret up to the stopping time. Focusing on single-parameter exponential families of distributions, we leverage information-theoretic techniques to establish an instance-dependent lower bound on the expected cumulative regret. Moreover, we present an impossibility result that underscores the tension between cumulative regret and sample complexity in fixed-confidence BAI. Complementarily, we design and analyze the Double KL-UCB algorithm, which achieves asymptotic optimality as the confidence level tends to zero. Notably, this algorithm employs two distinct confidence bounds to guide arm selection in a randomized manner. Our findings elucidate a fresh perspective on the inherent connections between regret minimization and BAI.

Схожие новости

#	Наименование новости	Тональность	Информативность	Дата публикации
1	The Role of Contextual Information in Best Arm Identification	0	4.07	17-08-2026
2	Differentially Private Best-Arm Identification	0	12.14	17-08-2026
3	An Anytime Algorithm for Good Arm Identification	0	7.17	17-08-2026
4	Bayesian Inference of Contextual Bandit Policies via Empirical Likelihood	0	3.97	17-08-2026
5	Refined Risk Bounds for Unbounded Losses via Transductive Priors	0	5.33	17-08-2026
6	Mixing times of data-augmentation Gibbs samplers for high-dimensional probit regression	0	8.78	17-08-2026
7	Neural Exploitation and Exploration of Contextual Bandits	0	6.34	17-08-2026
8	A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidance	0	13.12	17-08-2026
9	Transfer Conformal Predictive Inference for Regression	0	5.02	17-08-2026
10	Cheap Bootstrap for Fast Uncertainty Quantification of Stochastic Gradient Descent	0	6.38	17-08-2026

Классификация: Пресс-релизы. Схожих патентов: 0. Схожих новостей: 10. Тональность: 0. Информативность: 8.4. Источник: jmlr.org.