[Statlist] FDS Seminar talk with Samory K. Kpotufe, Columbia University - 27 October 2022, 16:15-​17:15

[Kaiser-Heinzmann Susanne]

We are pleased to announce and invite you to the next talk in our FDS seminar series:

"Tracking Most Significant Changes in Bandits“
by Samory K. Kpotufe, Columbia University

Date and Time: Thursday, 27 October 2022, 16:15-​17:15 CEST
Place: HG F 3, ETH Zurich

Host: Prof. Afonso Bandeira 

Abstract: In bandit with distribution shifts, one aims to automatically adapt to unknown changes in reward distribution, and restart exploration when necessary. While this problem has received attention for many years, no adaptive procedure was known till a recent breakthrough of Auer et al (2018, 2019) which guarantees an optimal regret (LT)^{1/2}, for T rounds and L stationary phases. However, while this rate is tight in the worst case, we show that significantly faster rates are possible, adaptively, if few changes in distribution are actually severe, e.g., involve no change in best arm. This is arrived at via a new notion of 'significant change', which recovers previous notions of change, and applies in both stochastic and adversarial settings (generally studied separately). If time permits, I’ll discuss the more general case of contextual bandits, i.e., where rewards depend on contexts, and highlight key challenges that arise. This is based on ongoing work with Joe Suk.

Organisers: A. Bandeira, H. Bölcskei, P. Bühlmann, F. Yang, S. van de Geer

Seminar website: https://math.ethz.ch/sfs/news-and-events/data-science-seminar.html