Timezone: »

 
Poster
Connections Between Mirror Descent, Thompson Sampling and the Information Ratio
Julian Zimmert · Tor Lattimore

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #12
in Algorithms -- Bandit Algorithms »
The information-theoretic analysis by Russo and Van Roy [2014] in combination with minimax duality has proved a powerful tool for the analysis of online learning algorithms in full and partial information settings. In most applications there is a tantalising similarity to the classical analysis based on mirror descent. We make a formal connection, showing that the information-theoretic bounds in most applications are derived from existing techniques from online convex optimisation. Besides this, we improve best known regret guarantees for $k$-armed adversarial bandits, online linear optimisation on $\ell_p$-balls and bandits with graph feedback.
Keywords: Information Theory · Bandit Algorithms · Algorithms · Algorithms -> Online Learning; Theory
[ Paper]  [ Poster] 

Author Information

Julian Zimmert (University of Copenhagen)
Tor Lattimore (DeepMind)

More from the Same Authors