Connections Between Mirror Descent, Thompson Sampling and the Information Ratio

Julian Zimmert, Tor Lattimore

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.

Introduction

In the field of online learning, agents must make sequential decisions under uncertainty to minimize cumulative regret—the difference between their total loss and that of the best fixed decision in hindsight. Historically, two distinct frameworks have dominated the analysis of these problems: the constructive, geometric approach of Mirror Descent and the information-theoretic approach centered on the Information Ratio. While the latter often yields tighter bounds, it frequently relies on minimax duality, proving the existence of optimal algorithms without providing a recipe for their construction. This paper bridges this "constructivity gap" by establishing a formal mathematical link between these two methodologies.

Bridging the Gap: Methods and Frameworks

The core contribution of this work is the demonstration that the Information Ratio used in Bayesian regret analysis is mathematically equivalent to the stability terms in Online Stochastic Mirror Descent (OSMD). By identifying this connection, the authors show that information-theoretic bounds can be derived using established techniques from online convex optimization.

Algorithm 1: The Online Stochastic Mirror Descent (OSMD) framework, which serves as the constructive basis for the paper's unified theory.

Key technical innovations include:

  • Modified Thompson Sampling (MTS): A hybrid algorithm that combines the sampling strategy of Mirror Descent with Bayesian updates, achieving regret bounds identical to OSMD.
  • Shifted Loss Estimators: To address the high variance often found in standard loss estimators for $k$-armed bandits, the authors introduce a "shifted" estimator. This innovation reclaims a factor-of-2 performance gap that previously separated Bayesian and adversarial bounds.
  • New Potential Functions: The authors design specific mathematical potentials to guide Mirror Descent in complex settings, such as graph feedback and linear optimization over $\ell_p$-balls.

Empirical Validation

While primarily a theoretical contribution, the paper includes simulations to validate the effectiveness of the proposed shifted loss estimators. Using Bernoulli losses, the authors demonstrate that the "INF+shift" strategy empirically outperforms standard strategies by the predicted factor of 2, significantly reducing cumulative regret over 100,000 time steps.

Empirical regret comparison between the standard INF strategy and the proposed INF+shift strategy, demonstrating a significant reduction in regret.

Key Results and Impact

The unification of these frameworks leads to several state-of-the-art results:

  1. $k$-armed Bandits: The authors present an efficient algorithm with regret $R_n \le \sqrt{2kn} + O(k)$, matching the best known (previously non-constructive) information-theoretic upper bounds.
  2. Graph Feedback: For "strongly observable" graph-feedback bandits, the minimax regret is improved by a factor of $\log(n)$, narrowing the gap between theory and known lower bounds.
  3. $\ell_p$-balls: For online linear optimization over $\ell_p$-balls ($p \in [1, 2]$), new potentials improve regret guarantees by large constant factors as $p$ approaches 1.

Conclusion and Future Directions

By showing that the Information Ratio is a measure of stability in a geometric optimization process, this work allows researchers to "import" Bayesian insights into the adversarial setting. Future work remains in extending these connections to general non-linear loss functions and fully resolving the optimal dependencies in graph-based bandit problems. The techniques presented here also offer a promising path toward improving algorithms for partial monitoring settings.

Summary updated

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.
BibTeX
@inproceedings{zimmert2019connections,
  author = {Julian Zimmert and Tor Lattimore},
  title = {{Connections Between Mirror Descent, Thompson Sampling and the Information Ratio}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=uSLWI3xAdNJ},
}

Loading related content...

Figure