Mirror Descent and the Information Ratio

Abstract

We establish a connection between the stability of mirror descent and the information ratio by Russo and Van Roy [2014]. Our analysis shows that mirror descent with suitable loss estimators and exploratory distributions enjoys the same bound on the adversarial regret as the bounds on the Bayesian regret for information-directed sampling. Along the way, we develop the theory for information-directed sampling and provide an efficient algorithm for adversarial bandits for which the regret upper bound matches exactly the best known information-theoretic upper bound.

References in corpus (5)

• More Adaptive Algorithms for Adversarial Bandits
• An Information-Theoretic Analysis for Thompson Sampling with Many Actions
• Exploration by Optimisation in Partial Monitoring
• Connections Between Mirror Descent, Thompson Sampling and the Information Ratio
• First-Order Bayesian Regret Analysis of Thompson Sampling

Cited by in corpus (4)

• Reinforcement Learning, Bit by Bit
• A Bit Better? Quantifying Information for Bandit Learning
• Information Directed Sampling for Sparse Linear Bandits
• The Value of Information When Deciding What to Learn