PaperlayerView exact revision on arXiv

Source-linked AI summary

Thompson Sampling for 1-Dimensional Exponential Family Bandits

Nathaniel Korda, Emilie Kaufmann, Remi Munos

arXiv:1307.3400v1stat.ML

TL;DR

The paper addresses limited theoretical guarantees for Thompson Sampling in parametric bandits beyond the Bernoulli case. It analyzes Thompson Sampling with Jeffreys prior for one-dimensional exponential-family bandits, proving asymptotic optimality and a finite-time exponential posterior-concentration bound. The analysis also covers some heavy-tailed exponential-family bandits.

  • Problem

    Theoretical guarantees for Thompson Sampling in parametric multi-armed bandits had been established only in the Bernoulli case, leaving broader exponential families insufficiently covered.

  • Method

    The paper analyzes Thompson Sampling with Jeffreys prior using closed-form exponential-family relationships among KL divergence, Fisher information, and posterior concentration.

  • Results

    The paper proves asymptotic optimality for Thompson Sampling with Jeffreys prior in one-dimensional canonical exponential-family bandits.

  • Takeaways & Limitations

    The result provides a provably competitive alternative to KL-UCB and covers some heavy-tailed exponential-family bandits.

  • Takeaways & Limitations

    The theoretical guarantees established in the paper hold only for Jeffreys prior, while broader prior choices remain an open direction.

Abstract

from arXiv · show

Thompson Sampling has been demonstrated in many complex bandit models, however the theoretical guarantees available for the parametric multi-armed bandit are still limited to the Bernoulli case. Here we extend them by proving asymptotic optimality of the algorithm using the Jeffreys prior for 1-dimensional exponential family bandits. Our proof builds on previous work, but also makes extensive use of closed forms for Kullback-Leibler divergence and Fisher information (and thus Jeffreys prior) available in an exponential family. This allow us to give a finite time exponential concentration inequality for posterior distributions on exponential families that may be of interest in its own right. Moreover our analysis covers some distributions for which no optimistic algorithm has yet been proposed, including heavy-tailed exponential families.

1 Introduction

The paper studies Thompson Sampling for parametric multi-armed bandits, where exploration must be balanced against exploiting arms with high expected rewards. It extends theoretical analysis beyond Bernoulli models to one-dimensional exponential families using Jeffreys prior.

  • Bandit setting: K-armed bandits model exploration-exploitation tradeoffs by requiring choices among reward distributions while maximizing cumulative expected reward.The agent weighs sampling well-performing arms against exploring uncertain arms that may yield higher rewards.
  • Thompson Sampling: Thompson Sampling draws parameters from each arm’s posterior and selects the arm with the largest sampled mean.The posterior is updated from observed rewards, and the probability of selecting an arm corresponds to its posterior probability of being optimal.
  • Motivation: Prior theoretical guarantees for parametric Thompson Sampling largely centered on Bernoulli rewards, motivating analysis for broader exponential-family models.Earlier work established asymptotic optimality in the Bernoulli case, while this paper targets one-dimensional exponential families.
  • Contribution: The paper proves asymptotic optimality for Thompson Sampling in one-dimensional exponential families when using Jeffreys prior.The result extends the optimality property previously shown for Bernoulli Thompson Sampling with a uniform prior.
  • Contribution: The analysis develops a finite-time posterior concentration result and exploits explicit relationships among Jeffreys prior, Fisher information, and Kullback-Leibler divergence.These tools support the regret analysis without relying on Bernoulli-specific arguments.
  • Related work: The paper distinguishes its objective from prior Bayes-risk analyses by treating the prior as a tool for guarantees on each fixed parameterized problem.Related work also studies bounded rewards, general models, and distribution-independent or prior-averaged regret bounds.

2 Exponential Families and Jeffreys Priors

The paper characterizes one-dimensional canonical exponential families through their sufficient statistics, normalization function, mean, KL divergence, and Fisher information. Jeffreys prior supplies the posterior used by Thompson Sampling, including for selected heavy-tailed examples.

  • Exponential-family structure: A one-dimensional canonical exponential family is described using a parameter θ, sufficient statistic T(x), normalization function F(θ), and parameter space Θ ⊂ R.The paper assumes F is twice differentiable with continuous second derivative.
  • Exponential-family structure: The mean function μ is strictly increasing and therefore one-to-one in the natural parameter θ.This links parameter comparisons to comparisons of expected rewards.
  • Information quantities: Within exponential families, Kullback-Leibler divergence has a closed-form Bregman-divergence representation based on F.The closed form is used in the paper’s theoretical analysis.
  • Jeffreys prior: Jeffreys prior is proportional to the square root of Fisher information, which equals F′′(θ) for canonical exponential families.The resulting posterior combines this prior with the likelihood of the sufficient statistics.
  • Jeffreys prior: The Jeffreys prior is chosen because its mass around KL-divergence neighborhoods can be lower-bounded using the local relationship between Fisher information and KL divergence.This property is central to the posterior concentration proof.
  • Implementation: Jeffreys prior is invariant under reparameterization, so the algorithm can operate on an alternative parameter λ using a prior proportional to I(λ).Posterior sampling can be implemented with methods such as Hastings-Metropolis.
  • Examples: The framework includes Pareto models with known minimum and unknown tail index, and Weibull models with known shape and unknown rate.These examples use T(x)=log(x) for Pareto and T(x)=x^k for Weibull, extending coverage to heavy-tailed distributions.

3 Results and Proof of Regret Bound

The proof establishes a regret bound for Thompson Sampling with Jeffreys prior by combining posterior concentration, control of optimal-arm plays, and a decomposition of suboptimal-arm selections.

  • Regret bound: Thompson Sampling is analyzed for exponential-family rewards whose arm means satisfy µ1 > µa for every suboptimal arm.The regret theorem assumes Jeffreys prior over Θ for every arm.
  • Proof strategy: The proof bounds the expected draws of each suboptimal arm by combining concentration results with a decomposition into principal and negligible components.The decomposition separates posterior-concentration terms for suboptimal and optimal arms.
  • Concentration results: Posterior concentration follows from concentration of the empirical sufficient statistic around its mean, after sufficiently many observations.The result requires Na,t ≥ N(θa, F) and a condition ensuring 1 − δaC2,a(∆a) > 0.
  • Optimal-arm control: A proposition controls the number of optimal-arm plays with high probability, addressing a central difficulty in prior Thompson Sampling regret analyses.The proposition provides a finite constant Cb for every b ∈ (0, 1).
  • Suboptimal-arm control: The suboptimal-arm contribution is logarithmic in T, with term (B) bounded by [(1 − ǫ)(1 − δaC2,a)K(θa, µ−1(µa + ∆a))]−1 ln(T ) plus constants.The constants depend on δa, ∆a, θa, and the posterior-concentration threshold.
  • Parameter choice: Choosing ∆a close to µ1 − µa and δa sufficiently small yields the stated regret bound with an additive constant C(ǫ, P).The intermediate constant increases as δa approaches zero, ∆a approaches the mean gap, or ǫ approaches zero.

4 Posterior Concentration: Proof of Theorem 4

The posterior-concentration proof extracts a Kullback–Leibler rate for overestimating an arm’s mean, then bounds numerator and denominator terms using exponential-family structure and Jeffreys prior.

  • Proof setup: The proof studies the posterior probability that a sampled parameter has mean at least µ + ∆ after conditioning on u observations.The analysis reduces the problem to bounding 1/Eu~P(µ(θu) ≥ µ + ∆ | Y u).
  • KL-rate extraction: The leading exponential term over parameters with mean at least µ + ∆ is K(θ, θ′), and its minimum occurs at θ′ = µ−1(µ + ∆).Strict convexity of F and monotonicity of µ identify the relevant KL boundary.
  • Numerator bound: The numerator is upper-bounded using the KL rate for the mean-overestimation set and the fact that the conditioned prior is a probability distribution.The bound applies when δ satisfies 1 − δC2 > 0.
  • Denominator bound: The denominator is lower-bounded by restricting integration to a KL ball and using the Jeffreys prior’s Fisher-information structure.The proof introduces KL-ball notation and uses local relations between KL divergence and F′′.
  • Proper-prior simplification: With a proper prior, the auxiliary observation ys′ is unnecessary, simplifying the denominator argument and eliminating the constants L and L′.The prior π0 can directly replace the conditioned prior in the relevant bound.

5 Conclusions

The paper proves asymptotic optimality of Thompson Sampling with Jeffreys prior for 1-dimensional canonical exponential-family bandits. Its guarantees extend beyond KL-UCB’s proven scope, including some heavy-tailed exponential-family bandits, while the analysis remains asymptotic and prior-specific.

  • Thompson Sampling with Jeffreys prior is asymptotically optimal for 1-dimensional canonical exponential-family bandits.
  • The proof’s central technical contribution is a finite-time concentration bound for posterior distributions in exponential families.The authors describe this result as new to the literature and central to their proof.
  • The analysis covers some heavy-tailed exponential-family bandits beyond the problems for which KL-UCB is provably optimal.
  • The stated theoretical guarantees apply to Jeffreys prior, although the proof suggests that other priors could satisfy the key required property.

A Concentration of the Sufficient Statistics: Proof of Lemma 3, and Inequalities (6) and (7)

The proof bounds deviations of sufficient statistics using a Chernoff-style argument, Markov’s inequality, and optimization over an exponential parameter. It treats lower and upper deviations separately and conditions on a designated observation when developing the subsequent bound.

  • The proof uses the classical Cramér–Chernoff technique to derive concentration inequalities for sufficient statistics.
  • Markov’s inequality is used in deriving one of the concentration bounds.
  • The lower-deviation argument is complemented by an analogous upper bound using a parameter ν* satisfying F′(θ − ν*) = F′(θ) − δ.
  • The later proof setup removes a designated observation from the arm’s first u observations before applying the concentration event.

B Extracting the KL-divergence: Proof of Lemma 7

This proof extracts the KL-divergence structure from posterior expressions built from the observations. On a concentration event, direct calculations and the empirical KL-divergence yield the needed inequality.

  • The proof introduces an event under which the designated observation index s′ is at most u.
  • The posterior after the designated observation is represented by π(θ|y_s′), while the remaining observations contribute to the empirical KL-divergence.
  • A direct computation of the posterior expression, together with a recalled identity, produces the inequality required for the lemma.

C Proof of Lemma 6

The proof chooses a finite sample threshold ensuring the required conditions hold, then defines the first time an arm reaches that threshold as a stopping time. The subsequent argument applies after this stopping time.

  • N_ε is defined as the smallest integer after which the required condition holds for all n at least N_ε.
  • The proof requires the arm count N_a,t − 1 to exceed the maximum of L_T, N_ε, and N(θ_a,F).
  • τ is defined as the first time the arm count reaches one more than this threshold, and is identified as a stopping time with respect to F_t.

D Controling the Number of Optimal Plays: Outline Proof of Proposition 5

The proof controls long intervals without optimal-arm plays by decomposing them into subintervals and bounding posterior deviations and interruptions. The generalized argument is asymptotic because avoiding explicit posterior calculations sacrifices explicit constants.

  • Proof scope: The generalized proof avoids explicitly calculating posterior probabilities, simplifying the analysis but losing explicit constants and retaining only an asymptotic guarantee for every b ∈]0, 1[.This extends the proof strategy used for the Bernoulli case to exponential-family bandits.
  • Interval construction: The interval Ij begins at the jth optimal-arm play and, on Ej, contains no subsequent optimal-arm draw.Its length is ⌈t^(1−b) − 1⌉, and Ej requires the gap to the next optimal-arm play to be at least that length.
  • Concentration bounds: Posterior concentration bounds control the probability that a saturated suboptimal arm’s sampled mean exceeds its true mean by more than da.Lemma 10 supplies constants Ca and a threshold N for this bound, while Lemma 9 controls long stretches during which the optimal arm is not selected.
  • Saturation decomposition: The analysis partitions Ij into K subintervals and tracks how many suboptimal arms become saturated and how many interruptions occur in each interval.An arm is saturated after at least Ca ln(t) selections; choosing an unsaturated suboptimal arm is an interruption.
  • Inductive conclusion: The proof handles the subintervals inductively, combining the base case and subsequent steps to obtain the final bound for all t ≥ N0.Step 2 treats the final subinterval when only saturated suboptimal arms are drawn; Step 3 extends the argument to earlier subintervals.
Loading 1307.3400v1…