An Information-Theoretic Analysis of Thompson Sampling

Daniel Russo, Benjamin Van RoyJMLR 2016

TL;DR

This paper presents a novel information-theoretic framework for analyzing Thompson Sampling, a popular algorithm for sequential decision-making under uncertainty. The authors derive regret bounds that depend on the "soft knowledge" (prior beliefs) about the optimal action, offering a more nuanced understanding of how learning improves performance and paving the way for more efficient algorithms.

What Problem Does This Paper Address?

The paper tackles the fundamental challenge of online optimization with partial feedback. Imagine a scenario where you need to make a sequence of decisions (e.g., choosing which ad to show a user, which drug to administer to a patient) to maximize some cumulative reward. The catch is that you don't know the true outcome of each decision beforehand, and you only observe the result of the action you actually take. This creates a crucial trade-off: exploration (trying out different actions to learn more about them) versus exploitation (sticking with actions you believe are best to maximize immediate reward).

Thompson Sampling is a popular algorithm that elegantly balances this trade-off by sampling actions based on their posterior probability of being optimal. However, existing theoretical guarantees for Thompson Sampling often relied on "hard knowledge" (e.g., the dimensionality of a linear model) and didn't fully capture the benefits of "soft knowledge" – the prior beliefs about which actions are more likely to be good. This paper aims to bridge this gap by providing a more general and insightful analysis of Thompson Sampling's performance, particularly highlighting how prior beliefs can significantly improve learning.

Methods

The core of the paper's contribution lies in its information-theoretic analysis of Thompson Sampling. Instead of relying on traditional complexity measures, the authors leverage concepts from information theory, such as entropy and mutual information, to characterize the algorithm's performance.

Key methodological aspects include:

  • Bayesian Framework: The problem is framed in a Bayesian setting where the unknown system parameters are modeled as random variables with a prior distribution. The analysis focuses on Bayesian regret (or Bayes risk), which is the expected regret averaged over this prior distribution.
  • Information Ratio: A novel quantity, the information ratio, is introduced. This ratio quantifies the trade-off between the expected squared regret and the information gained about the optimal action in a given period. The paper shows that Thompson Sampling's expected regret is bounded by this information ratio multiplied by the entropy of the optimal-action distribution.
  • Entropy of Optimal Action: A key insight is that the regret bounds depend on the entropy of the optimal-action distribution. This entropy quantifies the uncertainty about which action is truly optimal. Lower entropy (stronger prior beliefs) leads to tighter regret bounds, demonstrating the benefit of informative priors.
  • Unified Analysis: The information-theoretic approach allows for a unified analysis across various problem settings, including multi-armed bandits, linear bandits, and problems with combinatorial action sets and semi-bandit feedback.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and does not present empirical evaluations on specific datasets.

Key Insights and Ideas

  • Soft Knowledge Matters: The analysis reveals that prior beliefs ("soft knowledge") about the optimality of actions can significantly reduce regret. The entropy of the optimal-action distribution serves as a direct measure of this benefit.
  • Information Gain is Key: The information ratio elegantly captures the exploration-exploitation trade-off. A high information ratio suggests that learning about the optimal action is difficult, which can lead to higher regret.
  • Thompson Sampling's Elegance: The information-theoretic framework highlights why Thompson Sampling is so effective. It naturally aligns action selection with the posterior belief about the optimal action, leading to efficient learning.
  • Unified Perspective: The information-theoretic lens provides a common ground for understanding Thompson Sampling's performance across diverse online optimization problems, unifying previous results and offering new insights.

Key Results

The paper establishes general upper bounds on the expected regret of Thompson Sampling. These bounds are characterized by:

  • Time Horizon (T): Regret scales linearly with the time horizon.
  • Entropy of Optimal Action (H(A*)): Tighter bounds are achieved when the prior distribution on the optimal action is more concentrated (lower entropy). This is a significant improvement over bounds that only depend on the number of actions.
  • Information Ratio (Γt): The bounds are proportional to the information ratio, which quantifies the problem's information structure.

Specific results include:

  • For linear bandit problems, the regret bound is shown to be $O(\sqrt{dTH(A^*) / 2})$, where $d$ is the dimension of the linear model. This bound is tighter than previous results that depended on the number of actions, especially when $H(A^*)$ is small.
  • For problems with full information, the information ratio is bounded by a constant, leading to regret bounds that are linear in $H(A^*)$ and $T$.
  • For combinatorial action sets and semi-bandit feedback, the bounds are polynomial in the problem's parameters (e.g., $d$ and $m$), demonstrating Thompson Sampling's ability to exploit problem structure.

Limitations and Future Work

  • Focus on Expected Regret: The analysis primarily focuses on expected regret (Bayes risk). While this is a standard measure, future work could explore bounds on worst-case regret or other performance metrics.
  • Infinite Action Spaces: While the paper touches upon infinite action spaces in Appendix D, a more comprehensive treatment could be beneficial.
  • Algorithm Design: The authors explicitly mention that their insights into the role of soft knowledge will be leveraged in forthcoming work to design an algorithm that outperforms Thompson Sampling. This is a direct and promising future direction.
  • Generalization to Contextual Bandits: The current framework is primarily for standard bandit problems. Extending the information-theoretic analysis to contextual bandit settings would be a valuable next step.

Summary updated

BibTeX
@article{russo2016information,
  author = {Daniel Russo and Benjamin Van Roy},
  title = {{An Information-Theoretic Analysis of Thompson Sampling}},
  journal = {J. Mach. Learn. Res.},
  year = {2016},
}
Figure