Best arm Identification in Multi-Armed Bandits

Agniv Bandyopadhyay
Sandeep K Juneja
Wednesday, 20 Jul 2022, 15:00 to 16:00
Via Zoom
Papers by:
(1)"Best Arm Identification in Multi-Armed Bandits" by Audibert and Bubeck, 2010.
(2)"Tight (Lower) Bounds for the Fixed Budget Best Arm IdentificationBandit Problem" Carpentier and Locatelli 2016.

Paper (1) gives two algorithms for the best arm identification problem in stochastic multi-armed bandits under a fixed budget: Upper Confidence Bound-Exploration(UCB-E) and Successive Reject(SR). They also prove a lower bound of error probability in the limited budget setting. Paper (2) later improved that lower bound and proved that it matches the upper bound of the probability of error for the SR-Algorithm, thus proving its optimality. We'll look at the results established in Paper (1) and look through paper (2) if time permits.

Joining Link: