On the Asymptotic Optimality of Confidence Interval Based Algorithms for Fixed Confidence MABs
Kushal Kejriwal, Nikhil Karamchandani, Jayakrishnan Nair
Abstract
In this work, we address the challenge of identifying the optimal arm in a stochastic multi-armed bandit scenario with the minimum number of arm pulls, given a predefined error probability in a fixed confidence setting. Our focus is on examining the asymptotic behavior of sample complexity and the distribution of arm weights upon termination, as the error threshold is scaled to zero, under confidence-interval based algorithms. Specifically, we analyze the asymptotic sample complexity and termination weight fractions for the well-known LUCB algorithm, and introduce a new variant, the LUCB Greedy algorithm. We demonstrate that the upper bounds on the sample complexities for both algorithms are asymptotically within a constant factor of the established lower bounds.
BibTeX
@article{Kejriwal_Karamchandani_Nair_2025, title={On the Asymptotic Optimality of Confidence Interval Based Algorithms for Fixed Confidence MABs}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/33959}, DOI={10.1609/aaai.v39i17.33959}, abstractNote={In this work, we address the challenge of identifying the optimal arm in a stochastic multi-armed bandit scenario with the minimum number of arm pulls, given a predefined error probability in a fixed confidence setting. Our focus is on examining the asymptotic behavior of sample complexity and the distribution of arm weights upon termination, as the error threshold is scaled to zero, under confidence-interval based algorithms. Specifically, we analyze the asymptotic sample complexity and termination weight fractions for the well-known LUCB algorithm, and introduce a new variant, the LUCB Greedy algorithm. We demonstrate that the upper bounds on the sample complexities for both algorithms are asymptotically within a constant factor of the established lower bounds.}, number={17}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Kejriwal, Kushal and Karamchandani, Nikhil and Nair, Jayakrishnan}, year={2025}, month={Apr.}, pages={17814-17821} }