ICTS:32504

Asymptotic optimality of confidence interval based algorithms for fixed confidence MABs

(2025). Asymptotic optimality of confidence interval based algorithms for fixed confidence MABs. SciVideos. https://scivideos.org/icts-tifr/32504

Asymptotic optimality of confidence interval based algorithms for fixed confidence MABs. SciVideos, Aug. 13, 2025, https://scivideos.org/icts-tifr/32504 

          @misc{ scivideos_ICTS:32504,
            doi = {},
            url = {https://scivideos.org/icts-tifr/32504},
            author = {},
            keywords = {},
            language = {en},
            title = {Asymptotic optimality of confidence interval based algorithms for fixed confidence MABs},
            publisher = {},
            year = {2025},
            month = {aug},
            note = {ICTS:32504 see, \url{https://scivideos.org/icts-tifr/32504}}
          }
Jayakrishnan Nair
Talk numberICTS:32504
Source RepositoryICTS-TIFR

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 (universal) constant factor of the established lower bounds.