Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, March 11, 2021, 12:15 pm

Duration: 30 minutes

Location: Zoom: conference room

Speaker: Maxime Larcher

A More Efficient Algorithm for the Multi-Armed Bandit Problem with Non-Stationary Reward Distribution

The multi-armed bandit problem is a classical problem of computer science. At all steps t=1, 2, ..., T, an agent has to pull one of K arms and receives a reward drawn according to the chosen arm’s distribution; his goal is to maximise the total reward, or in other words, minimise the regret.

We consider the variant of this problem where the distributions of the rewards of all arms may change up to L times. Auer, Gajane and Ortner (2019) proposed the algorithm AdSwitch which achieves nearly optimal regret, without knowledge of L. We present a conceptually similar but simpler algorithm which achieves similar regret but has faster running time. We also simplify some parts of the theoretical analysis.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login