Source-linked AI summary
Further Optimal Regret Bounds for Thompson Sampling
Shipra Agrawal, Navin Goyal
TL;DR
The paper addresses the gap between Thompson Sampling’s practical popularity and its limited theoretical guarantees for stochastic bandits. It introduces a martingale-based regret analysis and proves optimal problem-dependent and near-optimal problem-independent bounds, with extensions beyond Beta rewards and to contextual bandits.
Problem
Thompson Sampling had empirical success but lacked strong theoretical guarantees, particularly near-optimal problem-independent regret bounds.
Method
The paper uses a martingale-based analysis of Thompson Sampling, developed for Bernoulli bandits with Beta posteriors and extendable beyond Beta rewards and to contextual bandits.
Results
The analysis proves optimal problem-dependent regret and a near-optimal problem-independent regret bound for Thompson Sampling.
Takeaways & Limitations
The results provide the first Thompson Sampling analysis matching the problem-independent lower bound within logarithmic factors and solve a COLT 2012 open problem.
Takeaways & Limitations
The paper does not consider PAC-style performance guarantees and assumes a unique optimal arm for stating and analyzing its results.
Abstract
from arXiv · showhide
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. In this paper, we provide a novel regret analysis for Thompson Sampling that simultaneously proves both the optimal problem-dependent bound of $(1+ε)\sum_i \frac{\ln T}{Δ_i}+O(\frac{N}{ε^2})$ and the first near-optimal problem-independent bound of $O(\sqrt{NT\ln T})$ on the expected regret of this algorithm. Our near-optimal problem-independent bound solves a COLT 2012 open problem of Chapelle and Li. The optimal problem-dependent regret bound for this problem was first proven recently by Kaufmann et al. [ALT 2012]. Our novel martingale-based analysis techniques are conceptually simple, easily extend to distributions other than the Beta distribution, and also extend to the more general contextual bandits setting [Manuscript, Agrawal and Goyal, 2012].
1 Introduction
The paper develops a martingale-based analysis of Thompson Sampling for stochastic multi-armed bandits, addressing its previously weak problem-independent guarantees. It establishes optimal problem-dependent regret and near-optimal problem-independent regret, with extensions beyond Beta rewards and to contextual bandits.
- 1 Introduction: Thompson Sampling previously had empirical success but lacked strong theoretical analysis, especially for problem-independent regret.Earlier results included only sublinear or problem-dependent guarantees, while their implied problem-independent bounds were far from optimal.
- 1 Introduction: The technique is conceptually simple, extends beyond the Beta distribution, and also extends to contextual bandits.The contextual-bandit extension is described as having substantially different details despite being inspired by the paper’s basic analysis idea.
- 1.2 Thompson Sampling: The paper analyzes Bernoulli rewards using Beta priors, updating posteriors from observed successes and failures before sampling an arm according to the largest sampled mean.The initial prior is Beta(1,1), and after observations the posterior for arm i is Beta(S_i(t)+1, F_i(t)+1).
- 1.3 Our results: Theorem 1 gives Thompson Sampling an asymptotically optimal problem-dependent expected-regret bound for stochastic bandits.The result matches the asymptotic lower bound and previous optimal Thompson Sampling bounds.
- 1.3 Our results: Theorem 2 gives a near-optimal problem-independent expected-regret bound, matching the problem-independent lower bound within logarithmic factors.The result improves on the O(T^2/3) problem-independent bound implied by earlier work.
2 Proofs
The proofs use a martingale-based analysis that bounds suboptimal-arm selection through the probability of selecting the optimal arm. Thresholds, concentration events, and beta-sampling properties then yield both problem-dependent and problem-independent regret bounds.
- Proof strategy: A martingale argument bounds the conditional probability of selecting any suboptimal arm by a linear function of the optimal arm's selection probability.The coefficient decreases exponentially as the number of observations increases.
- Concentration: The proof tracks empirical means and beta samples through high-probability concentration events around each arm's mean.Chernoff-Hoeffding bounds control empirical means, while beta concentration applies when an arm has more than Li(T) plays.
- Proof strategy: The analysis conditions on the play history Ft−1, which records previous arms and observed rewards.The history determines the sampling probabilities used in the proof.
- Proof strategy: The optimal-arm sampling probability changes only after each play of the optimal arm, remaining constant between consecutive such plays.This observation organizes the regret analysis over intervals between optimal-arm trials.
- Problem-dependent bound: For the logarithmic problem-dependent analysis, thresholds xi and yi are chosen between µi and µ1 using KL-divergence relations controlled by ε.The construction sets d(xi,µ1)=d(µi,µ1)/(1+ε) and d(xi,yi)=d(µi,µ1)/(1+ε)^2.
- Problem-independent bound: For the problem-independent analysis, thresholds are instead selected using the gaps Δi, and arms with sufficiently small gaps can be treated as optimal.The proof notes that multiple optimal arms can only help.
A Some results used in the proofs
This section collects Chernoff-Hoeffding concentration inequalities and beta-distribution facts used by the proofs. The stated bounds apply to independent Bernoulli variables and to bounded variables with a common conditional mean.
- Concentration bounds: Chernoff-Hoeffding bounds control deviations of sums of independent 0−1 random variables with possibly unequal expectations.The corresponding variables have expectations pi and are aggregated into a sum X.
- Concentration bounds: A second Chernoff-Hoeffding bound applies to variables in [0,1] whose conditional expectation given the previous variables is µ.It bounds deviations of the cumulative sum Sn.
- Beta distribution: The beta-distribution fact used in the analysis holds for all positive integer parameters α and β.This fact supports the beta-sampling calculations in the proofs.
B Proof of Lemma 2
The proof of Lemma 2 analyzes empirical-mean deviations at successive trials of an arm. Chernoff-Hoeffding concentration gives an exponentially decreasing probability for an empirical mean to exceed its threshold.
- Empirical-mean concentration: At the kth trial of arm i, its empirical mean is computed from k independent Bernoulli outcomes with mean µi.The proof indexes these observations by the trial times τk.
- Empirical-mean concentration: Pr(µ̂i(τk+1)>xi)≤e^−kd(xi,µi).The exponential decay follows from applying the Chernoff-Hoeffding bound to the empirical average.
- Empirical-mean concentration: The lemma's remaining inequality follows from the stated event characterization and the preceding concentration argument.The proof explicitly invokes the event used in the bound before completing the derivation.
C Proof of Lemma 3
The proof of Lemma 3 bounds beta-sampling events using beta and binomial distribution functions. Once an arm has more than Li(T) observations, the resulting probability is bounded by Li(T)+1 in the analyzed count.
- Beta-sampling bound: The beta posterior sampling probability is related to a beta-distribution cumulative function and a binomial probability expression.The proof uses the beta random variable generated from the arm's empirical statistics.
- Beta-sampling bound: Chernoff-Hoeffding bounds provide the final inequality when ki(t)>Li(T).The argument introduces τ as the largest time step satisfying ki(t)≤Li(T).
- Beta-sampling bound: The resulting bound is Li(T)+1.This is the terminal inequality of the lemma's calculation.
D Proof of Lemma 4
The proof sets up arm-play and threshold notation, then bounds terms involving F_{j+1,y}(s) by partitioning sums and applying binomial-cdf and Chernoff–Hoeffding estimates.
- The proof introduces τ_{j+1} as the time after the jth play of arm 1, with k_1(τ_{j+1}) = j.
- It defines the threshold gap as Δ′ = μ_1 − y.
- The analysis partitions F_{j+1,y}(s) into four partial sums and bounds the resulting expressions separately.
- The required bounds use binomial-distribution cdf estimates together with Chernoff–Hoeffding bounds.The cdf estimates are applied across the partial sums, while Chernoff–Hoeffding bounds justify intermediate inequalities.
- For sufficiently large s, specifically s ≥ ⌈y^j⌉, the proof obtains F_{j+1,y}(s) = Θ(1).This follows from the displayed inequality involving (j + 1)y(1 − y) and y^j.