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:
- Online Stochastic Mirror Descent (OSMD): A concrete algorithmic framework that uses gradients and geometry to update predictions.
- 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.
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.
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