Center for Advanced Intelligence Project

Talk by Dr. Odalric-Ambrym Maillard, INRIA, France.

Title: Multi-armed bandits and Boundary Crossing Probabilities

Abstract: In this talk, we will focus on the stochastic multi-armed bandit problem. After providing some short historical overview of the field, we will focus on its relations with boundary crossing probabilities.
We will present in particular finite-time boundary crossing probabilites valid for exponential families of arbitrary dimension K, contrasting earlier attempts valid only forthe dimension K=1. Perhaps surprisingly, we highlight that the proof techniques to achieve these strong results already existed three decades ago in the work of T.L. Lai, and were apparently forgotten in the bandit community. We provide a modern rewriting of these beautiful techniques that we believe are useful beyond the application to stochastic multi-armed bandit.