Tata Institute of Fundamental Research

Best arm Identification in Multi-Armed Bandits

Oral Qualifier
Speaker: Agniv Bandyopadhyay
Organiser: Sandeep K Juneja
Date: Wednesday, 20 Jul 2022, 15:00 to 16:00
Venue: Via Zoom

(Scan to add to calendar)
Abstract:  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: https://us02web.zoom.us/j/9290331190