Connections Between Mirror Descent, Thompson Sampling and the Information Ratio

Julian Zimmert, Tor Lattimore

This paper provides a "Rosetta Stone" for online learning theory. It bridges the gap between two historically separate ways of analyzing algorithms: the constructive, geometry-based world of Mirror Descent and the elegant, but often non-constructive, world of Information-Theoretic analysis.

The Discrepancy in Online Learning

In online learning scenarios, such as the multi-armed bandit problem, a learner must choose actions to minimize "regret"—the difference between their performance and the best possible action in hindsight.

Historically, researchers have relied on two main toolkits to analyze this regret:

  1. Online Stochastic Mirror Descent (OSMD): A concrete algorithmic framework that uses gradients and geometry to update predictions.
  2. Information-Theoretic Analysis: A framework (pioneered by Russo and Van Roy) that bounds regret based on how much "information" a learner gains about the optimal action.

The core problem was a persistent mismatch. The information-theoretic approach often produced tighter bounds (specifically, a factor of $\sqrt{2}$ better) but was non-constructive—it proved a good algorithm existed via minimax duality but didn't provide a blueprint to build it. Meanwhile, OSMD provided a concrete algorithm but yielded slightly worse theoretical guarantees. This paper asks: Why does this discrepancy exist, and can we unify these two perspectives?

Bridging the Gap: Modified Thompson Sampling

To bridge these domains, the authors introduce Modified Thompson Sampling (MTS). While standard Thompson Sampling samples from a posterior, and OSMD uses a mirror descent update, MTS connects them by using the sampling scheme of OSMD but replacing the mirror descent update with a Bayesian expected optimal action.

Algorithm for Modified Thompson Sampling (MTS)

The technical core of the paper is a proof demonstrating that the Information Ratio (regret squared divided by information gain) is upper-bounded by the Stability Coefficient of OSMD. This reveals that information-theoretic analysis is essentially a dual way of looking at the stability of a mirror descent algorithm. If an algorithm is "stable" (its iterates don't jump too wildly), it isn't accumulating too much regret while it learns.

Solving the "Factor of 2" Mystery

For years, OSMD bounds for $k$-armed bandits were $\sqrt{8kn}$, while info-theoretic bounds were $\sqrt{2kn}$. The authors show this wasn't a failure of the analysis itself, but rather a suboptimality in how losses were being estimated.

To achieve the tighter bounds constructively, they introduce a shifted loss estimator. In standard bandit algorithms, "importance weighting" is used to estimate losses for unchosen arms. By "shifting" these estimates (effectively adding a constant to the estimated losses), the authors reduce the variance and finally match the tighter information-theoretic bounds using a constructive algorithm.

Empirical comparison showing the shifted estimator (INF+shift) achieving significantly lower regret than standard INF.

While primarily a theoretical paper, the authors include a numerical simulation using Bernoulli losses to empirically demonstrate this breakthrough. As shown above, their "shifted" estimator successfully achieves the predicted factor-of-2 improvement in regret over the standard INF (Implicitly Normalized Forecaster) strategy.

Key Results and Impact

By linking these fields, researchers can now take non-constructive existence proofs from the information-theoretic literature and transform them into efficient, implementable OSMD-style algorithms. Key improvements include:

  • $k$-armed Bandits: The authors provide an efficient algorithm with regret $R_n \le \sqrt{2kn} + O(k)$, matching the best known theoretical lower bounds and improving on previous constructive methods.
  • Graph Feedback: In settings where playing one action reveals information about others (represented by a graph), they improved the minimax regret by a factor of $\log(n)$, matching the lower bound more closely.
  • $\ell_p$-balls: For online linear optimization over $\ell_p$-balls (where $p \in [1, 2]$), they designed a new "potential function" for OSMD that improves existing regret bounds by removing large constant factors that previously grew as $p$ approached 1.

Limitations and Future Work

While the authors successfully show that OSMD tools can be used for Bayesian analysis, they note that "closing the circle"—using info-theoretic tools to directly construct OSMD algorithms—remains an open challenge. Additionally, the current framework relies heavily on the linearity of losses; extending these tight connections to non-linear or more complex partial monitoring settings is a promising next step.

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 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.
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},
}
Figure