Speaker: Ojash Neopane

Abstract: In this talk I will discuss The Simulator, which is a mechanism which can be used to prove lower bounds for Best-Arm Identification (BAI) in Multi Armed Bandits (MAB). Traditionally, lower bounds for this problem have been proved using so called change-of-measure arguments. However, these lower bounds only paint an accurate picture of the problem difficulty in traditional BAI problem, and can paint a misleading picture when there is some additional structure (i.e when the means of the arms lie in a simplex). The Simulator is an alternative mechanism which can be used to prove these lower bounds as well as a broader range of instance-dependent properties describing the difficulty of a BAI problem. In this talk, I will be going over the ideas from The Simulator paper and showing how it can be used to prove some lower bounds for BAI as well as some other interesting properties.

Paper: https://arxiv.org/abs/1702.05186