Connections Between Mirror Descent, Thompson Sampling and the Information Ratio

Abstract

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 can be derived from existing techniques for online convex optimisation. Besides this, for $k$-armed adversarial bandits we provide an efficient algorithm with regret that matches the best information-theoretic upper bound and improve best known regret guarantees for online linear optimisation on ${\ell }_p$-balls and bandits with graph feedback.

References in corpus (1)

• An Information-Theoretic Approach to Minimax Regret in Partial Monitoring

Cited by in corpus (7)

• Exploration by Optimisation in Partial Monitoring
• Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
• Mirror Descent and the Information Ratio
• Reinforcement Learning, Bit by Bit
• A Bit Better? Quantifying Information for Bandit Learning
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring
• Understanding Bandits with Graph Feedback