Thompson Sampling for Contextual Bandits with Linear Payoffs

Shipra Agrawal; Navin Goyal

Source-linked AI summary

Thompson Sampling for Contextual Bandits with Linear Payoffs

Shipra Agrawal, Navin Goyal

arXiv:1209.3352v4Sep 15, 2012cs.LGcs.DSstat.ML

TL;DR

The paper addresses limited theoretical guarantees for Thompson Sampling in stochastic contextual bandits with linear payoffs. It analyzes a Gaussian-prior contextual generalization using martingale-based techniques and obtains high-probability regret bounds that are near-optimal and computationally efficient under stated conditions.

Problem
Theoretical guarantees for Thompson Sampling remained limited, particularly high-probability regret bounds and guarantees for contextual bandits.
Method
The paper analyzes a contextual Thompson Sampling generalization with Gaussian prior and likelihood using martingale-based techniques.
Results
The algorithm achieves high-probability, near-optimal regret bounds for stochastic contextual bandits with linear payoff functions.
Takeaways & Limitations
The results establish theoretical guarantees for contextual Thompson Sampling and place its regret close to state-of-the-art methods.
Takeaways & Limitations
The analysis assumes linear realizability, and non-trivial regret bounds for the agnostic case were not known.

Abstract

from arXiv · show

Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have better empirical performance compared to the state-of-the-art methods. However, many questions regarding its theoretical performance remained open. In this paper, we design and analyze a generalization of Thompson Sampling algorithm for the stochastic contextual multi-armed bandit problem with linear payoff functions, when the contexts are provided by an adaptive adversary. This is among the most important and widely studied versions of the contextual bandits problem. We provide the first theoretical guarantees for the contextual version of Thompson Sampling. We prove a high probability regret bound of $\tilde{O}(d^{3/2}\sqrt{T})$ (or $\tilde{O}(d\sqrt{T \log(N)})$), which is the best regret bound achieved by any computationally efficient algorithm available for this problem in the current literature, and is within a factor of $\sqrt{d}$ (or $\sqrt{\log(N)}$) of the information-theoretic lower bound for this problem.

1 Introduction

The paper develops and analyzes a Gaussian-prior generalization of Thompson Sampling for stochastic contextual bandits with linear payoffs. It addresses limited theoretical understanding by establishing high-probability regret guarantees and an efficient implementation.

Problem setting: Contextual bandits present d-dimensional arm features before each of T decisions, requiring the learner to balance exploration with predicting rewards.The learner chooses among N arms using current contexts and past contexts and rewards.
Problem setting: Under linear realizability, an unknown parameter µ determines each arm’s expected reward as b_i^T µ, making µ the learner’s target for estimation.The linear predictor associated with µ is the best predictor under this assumption.
Method: Thompson Sampling samples parameters from posterior distributions and selects an arm whose sampled parameter predicts the best reward.The contextual generalization uses Gaussian prior and likelihood functions.
Motivation: High-probability regret bounds for contextual Thompson Sampling had remained open despite empirical success and progress on expected regret for basic stochastic MABs.Earlier theoretical guarantees were weak, while later work established optimal expected-regret bounds for the non-contextual setting.
Contributions: The analysis establishes the first non-trivial high-probability regret guarantees for contextual Thompson Sampling with linear payoffs.The paper uses novel martingale-based analysis techniques and describes the algorithm as computationally efficient under efficient linear optimization over the arms.
Contributions: The resulting regret bound is the best achieved by any computationally efficient algorithm in the literature when the number of arms N is large, while its gap to the information-theoretic lower bound remains open.The paper identifies determining whether this computational-versus-information-theoretic gap exists as an open question.

2 Problem setting and algorithm description

The paper studies contextual bandits with linear payoffs under adaptive contexts and presents a Gaussian Thompson Sampling algorithm with high-probability regret guarantees. The method is computationally efficient under efficient linear optimization, while its regret remains near the information-theoretic lower bound.

2.1 Problem setting: Each round reveals d-dimensional contexts for N arms, chosen adaptively after observing the previous history, and the learner selects one arm.The reward mean for arm i is b_i(t)^T µ, where µ is fixed but unknown.
2.1 Problem setting: The model assumes R-sub-Gaussian reward noise and bounded contexts, parameter, and per-round gaps; these bounds make regret scale-free.If all corresponding bounds are c instead of 1, the regret bounds increase by a factor of c.
2.2 Thompson Sampling algorithm: Thompson Sampling samples a parameter µ̃(t) from N(µ̂(t), v²B(t)^−1) and plays the arm maximizing b_i(t)^Tµ̃(t).The algorithm uses Gaussian prior and likelihood models for design, while the analysis only requires the actual rewards to be R-sub-Gaussian.
2.2 Thompson Sampling algorithm: The algorithm is efficient when maximizing a linear function over the current arm set is efficient, including some large, infinite, convex, or combinatorial arm sets.Its per-round computation consists of Gaussian sampling and linear optimization.
2.3 Our Results: With probability 1−δ, Theorem 1 bounds total regret by the smaller of two stated bounds, and the bound does not depend on N.This makes the guarantee applicable, with notational changes, to infinitely many arms.
2.4 Related Work: Thompson Sampling achieves the best regret upper bound among efficient algorithms cited, while an efficient algorithm attaining the information-theoretic lower bound remains open.The paper identifies a regret cost for computational efficiency relative to the lower bound.

3 Regret Analysis: Proof of Theorem 1

The proof addresses contextual-bandit difficulties by separating saturated from unsaturated arms and combining concentration, anti-concentration, and martingale arguments. This yields a high-probability regret bound for Thompson Sampling.

Challenges and proof outline: The contextual setting creates analysis challenges because basic-bandit techniques do not directly apply.Contexts can make regret exceed the improvement in the design matrix when an arm has a small context vector.
Unsaturated arms: For unsaturated arms, instantaneous regret is bounded by g_t s_i(t), allowing total regret to be controlled through reductions in uncertainty.The standard deviation-related quantity improves as arms are played.
Saturated arms: For saturated arms, accurate estimates make them unlikely to be selected, so the proof lower-bounds the probability that an unsaturated arm is played.This connects saturated-arm regret to regret from unsaturated arms.
Arm classification: Arms are divided into saturated and unsaturated groups according to whether their regret exceeds g_t s_i(t).The optimal arm is always unsaturated, while other arms may change groups over time.
Probabilistic analysis: The analysis uses concentration and anti-concentration events for estimates and Gaussian samples, together with a super-martingale and the Azuma-Hoeffding inequality.These ingredients establish the desired high-probability regret bound.

4 Conclusions

The paper analyzes Thompson Sampling for stochastic contextual bandits with linear payoffs and resolves open questions about its theoretical guarantees. It also identifies extensions to other priors and several unresolved settings.

The paper provides a theoretical analysis of Thompson Sampling for stochastic contextual bandits with linear payoffs.
The martingale-based analysis is described as simpler than prior techniques and amenable to extensions.
The analysis can extend beyond Gaussian priors when another distribution has similar concentration and anti-concentration tail inequalities.
Open directions include tighter dependence on ǫ, generalized linear models, delayed or batched feedback, and agnostic contextual bandits.The agnostic case lacks a known non-trivial regret bound according to the paper.

Nomenclature

The nomenclature defines arms, contexts, parameters, rewards, regret, uncertainty quantities, and the history used in the contextual-bandit analysis.

a(t) denotes the arm played at time t, while a∗(t) denotes the optimal arm at that time.
b_i(t) is the context vector for arm i at time t, and d is the context-vector dimension.
C(t) is the set of saturated arms, and a saturated arm satisfies Δ_i(t) > g_t s_i(t).
μ is the unknown d-dimensional parameter, while H_t−1 records prior actions, rewards, and contexts.
˜μ(t) is a d-dimensional Gaussian sample generated from the distribution centered at the empirical estimate with covariance scaling involving v².
r_i(t) denotes the reward for arm i at time t, and regret(t) denotes regret at time t.

A.1 Posterior distribution computation

The posterior distribution of the unknown parameter at time t+1 is Gaussian with updated mean and covariance determined by B(t+1).

The posterior distribution of μ at time t+1 is N(ˆμ(t+1), v²B(t + 1)⁻¹).

A.2 Some concentration inequalities

This section collects Gaussian concentration tools, the Azuma–Hoeffding inequality, and a self-normalized martingale bound used later in the analysis.

Gaussian concentration and anti-concentration inequalities are derived from Formula 7.1.13 of Abramowitz & Stegun (1964).
Azuma–Hoeffding bounds a super-martingale whose successive differences are bounded by constants c_t.
Lemma 8 provides a self-normalized bound for a vector-valued predictable process with conditionally R-sub-Gaussian martingale differences.

A.3 Proof of Lemma 1

The proof bounds the probabilities of events E_mu(t) and E_theta(t) using self-normalized concentration, Gaussian tail bounds, and a union bound over arms.

Bounding E_mu(t): Lemma 8 is applied with the selected-arm feature and reward-noise processes to establish the bound for event E_mu(t).The filtration contains the history through the relevant arm choices while excluding the next unrevealed reward.
Bounding E_theta(t): For event E_theta(t), conditioning on the past fixes b_i(t) and B(t), enabling Gaussian probability bounds for the sampled parameters.
Bounding E_theta(t): Each sampled parameter θ_i(t) is Gaussian with mean b_i(t)^T ˆµ(t) and variance determined by v_t^2 s_i(t)^2.
Bounding E_theta(t): A union bound over i = 1, . . . , N combines the per-arm inequalities into a high-probability bound for E_theta(t).

A.4 Proof of Lemma 2

The proof of Lemma 2 combines the confidence event E_mu(t) with Gaussian anti-concentration to control the sampled parameter of the optimal arm.

Under E_mu(t), the optimal arm’s sampled mean differs from its posterior mean by at most ℓ_t s_{a*(t)}(t).
Gaussian anti-concentration is applied to θ_{a*(t)}(t), whose standard deviation is v_t s_{a*(t)}(t).
The resulting probability bound controls the sampled value of the optimal arm within the proof of Lemma 2.

A.5 Missing details from Section 3.2

This section supplies eigenvalue and martingale details used to derive a logarithmic matrix-trace bound and extend regret guarantees to an alternative regret definition.

Matrix-growth bound: Lemma 9 controls eigenvalue growth when B(t) is updated by adding b_{a(t)}(t)b_{a(t)}(t)^T.All eigenvalues of B(t) are at least 1, allowing the stated eigenvalue comparison.
Matrix-growth bound: The eigenvalue update yields the inequality needed for the logarithmic bound after algebra following Lemma 3 of Chu et al. (2011).
Alternative regret definition: For the alternative regret definition, the conditional expected regret remains the same because E[r_i(t)|F_{t−1}] = b_i(t)^T µ.
Alternative regret definition: The same-order regret bounds follow by showing the associated process is a super-martingale and applying Azuma–Hoeffding under bounded or R-sub-Gaussian rewards.The R-sub-Gaussian extension is stated without proof.