An Information-Theoretic Analysis of Thompson Sampling

Daniel Russo; Benjamin Van Roy

Source-linked AI summary

An Information-Theoretic Analysis of Thompson Sampling

Daniel Russo, Benjamin Van Roy

arXiv:1403.5341v2Mar 21, 2014cs.LG

TL;DR

The paper addresses how to analyze sequential decisions under model uncertainty and partial feedback when both structural and prior knowledge matter. It uses information theory to analyze Thompson sampling through regret and information gain, obtaining broad regret guarantees whose dependence on optimal-action entropy captures relevant uncertainty. The results strengthen prior bounds and apply across multiple online optimization settings, though two special-case bounds are tight only up to a logarithmic factor.

Problem
Existing regret bounds mostly use hard knowledge while neglecting soft knowledge, limiting their account of performance improvement as data is collected in partial-feedback problems.
Method
The paper uses information theory to relate Thompson sampling’s expected regret to expected information gain, quantified through an information ratio.
Results
The analysis provides unified, order optimal Bayesian regret bounds for Thompson sampling across independent-arm, full-information, linear, and combinatorial semi-bandit settings, with dependence on optimal-action entropy.
Takeaways & Limitations
Entropy-sensitive bounds quantify how prior knowledge about which action is optimal can benefit performance and inform exploration–exploitation design.
Takeaways & Limitations
For two special cases, the bounds are tight only up to a logarithmic factor.

Abstract

from arXiv · show

We provide an information-theoretic analysis of Thompson sampling that applies across a broad range of online optimization problems in which a decision-maker must learn from partial feedback. This analysis inherits the simplicity and elegance of information theory and leads to regret bounds that scale with the entropy of the optimal-action distribution. This strengthens preexisting results and yields new insight into how information improves performance.

1. Introduction

The paper studies sequential decision-making with partial feedback, where learning which action is best must be balanced against immediate reward. It develops information-theoretic regret bounds for Thompson sampling that incorporate prior knowledge and apply across several online optimization settings.

Problem: Partial feedback creates an exploration–exploitation tradeoff because unchosen actions’ rewards are generally unobserved.The framework includes classical multi-armed bandits and richer information structures relating actions and observations.
Motivation: Existing regret bounds largely depend on hard model knowledge rather than soft knowledge that evolves with observations.The paper identifies this as limiting insight into how performance should improve as data is collected.
Contribution: The paper establishes Thompson-sampling regret bounds that depend on both hard and soft knowledge, strengthening prior results.Thompson sampling is also called posterior sampling or probability matching.
Contribution: Information theory yields a unified analysis covering independent-arm bandits, full-information optimization, linear bandits, and combinatorial semi-bandits.The analysis establishes order optimal Bayesian regret bounds for each listed special case.
Information-sensitive bounds: The bounds depend on the entropy of the optimal-action distribution, making them sensitive to uncertainty specifically relevant to optimization.This dependence formalizes performance benefits when some actions are more likely to be optimal than others.
Preview of results: For linear bandits, the bound depends on model dimension rather than the number of actions and vanishes as optimal-action entropy approaches zero.The broader information-complexity formulation also recovers bounds for full feedback and combinatorial semi-bandit settings.

2. Problem Formulation

The formulation models sequential decisions under uncertainty, where actions reveal partial outcomes and the objective is to minimize expected cumulative regret while learning the unknown environment.

The decision-maker chooses actions sequentially and observes only the outcome corresponding to the selected action.The underlying outcome distribution is randomly drawn, and outcomes are conditionally iid over time.
The optimal action A∗ maximizes expected reward under the unknown outcome distribution.Uncertainty about the distribution induces uncertainty about which action is optimal.
Expected regret measures the cumulative reward gap between always choosing the optimal action and following the algorithm’s action sequence.The expectation includes action and outcome randomness as well as the prior over the unknown distribution.
Actions are generated by randomized policies conditioned on the history of observations.External randomization enters through independent variables, while the policy specifies a conditional distribution over actions.
The main exposition assumes bounded rewards and a finite action set, though the appendix extends some cases to sub-Gaussian rewards and infinite sets.For infinite action sets, discretization arguments address some cases; restricting to the support of A∗ can make the relevant set finite.

3. Basic Measures and Relations in Information Theory

The paper introduces entropy, mutual information, and KL divergence as tools for quantifying uncertainty, information gain, and distributional difference in the learning process.

The analysis applies these measures under posterior distributions and restricts the optimal-action variable to finite support so its entropy is useful.Posterior conditional entropy and mutual information are evaluated under the measure Pt.
KL divergence is an expected log-likelihood ratio and is nonnegative under absolute continuity.Gibbs’ inequality gives equality only when the compared distributions coincide almost everywhere.
Mutual information measures dependence between variables through KL divergence and is nonnegative, vanishing when the variables are independent.It can be written as the KL divergence between a joint distribution and the product of its marginals.
Mutual information equals the expected reduction in posterior entropy produced by observing another variable.The conditional form measures the additional entropy reduction from observing Y when Z is already known.
The chain rule decomposes information about X from multiple observations into sequential conditional information gains.This decomposition supports summing information acquired over time.
Observing an outcome provides at least as much information about the optimal action as observing its deterministic reward transformation.This follows from the weak data processing inequality.

4. Thompson Sampling

Thompson sampling selects actions according to their posterior probability of being optimal, providing a simple Bayesian strategy with practical implementations in parametric models.

Thompson sampling matches the action-selection distribution to the posterior distribution of the optimal action.At time t, each action is selected with probability P(A∗ = a|Ft).
In parametric models, the algorithm samples a parameter from its posterior and chooses an action optimal for that sampled parameter.This implements probability matching through a posterior draw rather than direct action sampling.
For linear bandits, actions have d-dimensional features and mean rewards are inner products with an unknown parameter.The construction targets online linear optimization under bandit feedback.
In the linear-Gaussian case, posterior parameters remain normally distributed and the algorithm updates their mean and covariance after observing rewards.The expectations can be computed efficiently using Kalman filtering.
The implementation is efficient when the sampled linear objective can be maximized efficiently over the action set.Closed-form posteriors help, while Markov chain Monte Carlo can generate samples when the posterior is complex.

5. The Information Ratio and a General Regret Bound

The paper relates Thompson sampling’s expected regret to its expected information gain through the information ratio, then bounds cumulative regret using the prior uncertainty about the optimal action.

The information ratio is the ratio between squared expected regret and expected information gain in period t.Both quantities are evaluated under the posterior measure conditioned on the history.
A small information ratio implies that large regret occurs only when the algorithm expects to gain substantial information about the optimal action.This links inefficient decisions to posterior learning about which action is best.
The general regret argument upper-bounds total expected information gain by the entropy of the prior distribution of the optimal action.The proof invokes conditional expectation, Cauchy–Schwarz, the mutual-information chain rule, and nonnegative entropy.

6. Bounding the Information Ratio

The section bounds Thompson sampling’s information ratio across several feedback and action structures, then combines those bounds with regret results. The bounds reflect how information from selected actions relates to other actions and how the entropy of the optimal-action distribution can improve worst-case guarantees.

General information-ratio bounds: The information ratio measures how sampling actions enables inference about other actions, with worst-case dependence on the number of actions.The section defines its numerator through reward differences and its denominator through changes in observations when the optimal action is known.
Comparison with lower bounds: The paper compares its expected-regret upper bounds with known lower bounds, while noting that general prior-dependent lower bounds remain unavailable.Some cited lower bounds arise from adversarial formulations proved using the probabilistic method.
General information-ratio bounds: Bounded rewards yield an information-ratio bound with explicit dependence on the number of actions, and this scaling cannot generally be improved.The paper then derives tighter bounds for settings with different information structures.
Full information: Under full information, Γt ≤ 1/2 almost surely, because observations do not depend on the selected action.Combining this with the paper’s regret proposition produces an entropy-dependent bound that can improve on log(|A|) when the prior is informative.
Linear optimization under bandit feedback: For stochastic linear bandits, the analysis exploits correlations among actions to obtain bounds involving the feature dimension and the entropy of the optimal-action distribution.Observations from one action can support inferences about other actions because mean rewards are inner products with a shared unknown parameter.
Combinatorial action sets and semi-bandit feedback: For combinatorial semi-bandit feedback, structural dependence among actions yields an information-ratio bound scaling with d rather than the full number of actions.The resulting regret is described as polynomial in m and d because Thompson sampling exploits the relationship among actions.

7. Conclusion

The conclusion presents an information-theoretic analysis of Thompson sampling that applies across broader information structures and quantifies soft knowledge through the entropy of the optimal-action distribution. It also emphasizes the broader potential of the techniques and quantities beyond the paper’s theoretical guarantees.

Conclusion: The analysis uses information theory to derive simple regret bounds for Thompson sampling across a broader range of information structures than prior work.The formulation includes multiple partial-feedback and full-information settings discussed earlier in the paper.
Conclusion: The regret bounds quantify soft knowledge through the entropy of the optimal-action distribution and clarify how past observations affect future performance.The paper connects this perspective to assessing exploration–exploitation tradeoffs.
Conclusion: The analysis may have broader interest because its proofs combine standard information-theoretic relations with conditional-expectation and inequality tools.The authors present the information-theoretic view as a fresh perspective on online optimization with partial feedback.

A.1 Proof of Fact 9

This appendix proves the divergence inequality used to relate bounded mean differences to Kullback–Leibler divergence. The proof applies Pinsker’s inequality after centering and rescaling the relevant function.

Fact 9: Pinsker’s inequality lower bounds the Kullback–Leibler divergence between bounded random variables using the difference between their means.The result applies when one distribution is absolutely continuous with respect to the other and the function’s range is at most one.
Proof strategy: The proof chooses a common base measure and centers the bounded function so it lies in [−1/2, 1/2].The centered function differs from the original function only by a constant, preserving the relevant expectation difference.
Auxiliary matrix facts: The appendix also records norm and trace facts for matrices, including relationships among nuclear, Frobenius, and trace quantities.These facts are supported using singular values, symmetry, homogeneity, and the triangle inequality.

Appendix B. Proof of Proposition 6

The appendix proves the combinatorial semi-bandit information-ratio result by bounding reward differences and information gain under conditional independence. The proof combines KL-divergence chain rules with Pinsker-based inequalities, Jensen’s inequality, and conditional expectation.

Information-gain bound: The KL divergence for an action’s observed components is decomposed with the chain rule and controlled using the bounded-variable inequality.The argument conditions on previously indexed components within the selected action.
Information-gain bound: Conditional independence, Jensen’s inequality, and the tower property control the successive expectation terms in the information-gain calculation.These tools are invoked across the lemma proofs to pass between conditional and unconditional quantities.
Proof of Proposition 6: The proof bounds the numerator of the information ratio by d/2m^2 under Proposition 6’s conditions.This is the key reward-difference estimate used to establish the proposition’s information-ratio bound.

Appendix C. Proof of Fact 6

The appendix extends the relevant information-theoretic identity from finite-support observations to general random variables by quantization and successively refined finite partitions.

General random variables: The proof begins with finite-valued X and a general random variable Y, establishing the identity through KL divergence.For finite-support Y, the result follows directly from the joint-distribution factorization; the general case requires an extension.
Quantization: General observations are handled by quantizing Y over finite partitions and taking the supremum over such partitions.The quantized variable YQ records which partition cell contains Y.
Refined partitions: Mutual information and KL-divergence properties are applied to each quantized observation YQ.The argument uses successively refined partitions to connect the quantized divergences with the divergence for Y itself.
Completion: A finite refinement sequence Qn is used to express the limiting divergence through the partition cells, completing the claim when the inequalities become equalities.The appendix explicitly states that the resulting inequalities are equalities and establish the claim.

D.1 Infinite Action Spaces

For infinite action spaces, the analysis focuses on bounded linear optimization and approximates the compact action set with a finite cover, yielding a quantized Thompson-sampling bound.

Problem setup: The infinite-action analysis considers linear optimization with actions and model parameters in bounded subsets of R^d.The setup assumes supa∈A ∥a∥2 ≤ c and supθ∈Θ ∥θ∥2 ≤ c.
Action-space approximation: A finite ε-cover Aε approximates every action, with log |Aε| = O(d log(dc/ε)); the resulting reward approximation error is at most cε.The error bound follows from the Cauchy-Schwarz inequality.
Quantized Thompson sampling: The analysis applies to a Thompson-sampling variant that randomizes according to the posterior distribution of the quantized optimal action A∗Q.The action probability is defined from the posterior distribution over the finite cover.
Regret bound: The resulting bound depends on T, dimension d, the entropy of A∗Q, and the discretization error εT.The construction chooses ε = (cT)^−1 and uses log |Aε| = O(d log(dcT)), giving a bound of order d√T log(dcT).
Regret bound: For d ≤ T, the bound is of order d√T log(cT), while for d > T the analysis notes the trivial regret bound T < √(dT).The comparison distinguishes the dimensional regime from the trivial horizon-based bound.
Relation to standard sampling: A similar result can be obtained for Thompson sampling using the unquantized optimal action, though the analysis is described as more careful.The displayed treatment uses the quantized version for simplicity.

D.2 Unbounded Noise

The paper relaxes uniformly bounded rewards to conditionally sub-Gaussian rewards, extending the key information inequality and deriving more general regret bounds.

Relaxed noise assumption: The unbounded-noise extension replaces the uniform boundedness assumption with sub-Gaussian reward distributions.Uniform boundedness is required for Fact 9 but is otherwise not used in the analysis.
Definitions: A sub-Gaussian random variable has a moment-generating function dominated by that of a Gaussian random variable; bounded-support and Gaussian variables are examples.The paper also defines conditional sub-Gaussianity relative to a sigma-algebra.
Information inequality: Lemma 3 extends Fact 9 when each reward is conditionally σ-sub-Gaussian given the history.The lemma is then substituted into the paper’s existing analysis.
Regret consequences: Corollary 1 gives the resulting bound under conditionally σ-sub-Gaussian reward noise and specifies corresponding upper bounds on Γt.The stated cases include Γt ≤ 2σ^2 under Proposition 4 and Γt ≤ 2dσ^2 under Proposition 5.
Examples: The conditions cover Gaussian prior and Gaussian noise, as well as bounded expected rewards with sub-Gaussian reward noise.These are highlighted as two settings satisfying Corollary 1’s conditions.
Proof mechanism: The proof derives the inequality from the variational form of KL divergence and maximizes over λ.It applies the variational representation to the centered reward variable before optimizing the resulting lower bound.