PaperlayerView exact revision on arXiv

Source-linked AI summary

Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling

Prateek Jaiswal, Debdeep Pati, Anirban Bhattacharya, Bani K. Mallick

arXiv:2609.01999v1stat.MLcs.ITcs.LGmath.ST

TL;DR

Existing Thompson Sampling analyses inflate posterior variance to obtain near-optimal regret guarantees. This paper formalizes that effect with α-TS, analyzes it under general regularity conditions, and obtains O(d^3/2√T log T) regret for α = d^-1 while showing an Ω(d^3/2√T) lower-bound scaling.

  • Problem

    The paper analyzes Thompson Sampling for stochastic generalized linear bandits, where regret measures cumulative loss from selecting suboptimal actions.

  • Method

    α-TS uses a fractional posterior formed by tempering the standard posterior likelihood, with regret analysis based on regularity conditions for the prior and reward model and posterior concentration theory.

  • Results

    For α = d^-1, the framework gives O(d^3/2√T log T) regret for exponential-family and sub-Gaussian rewards, while an α-dependent lower bound shows unavoidable d^3/2 scaling for this class.

  • Takeaways & Limitations

    α-TS provides a principled Bayesian interpretation of variance inflation used in Thompson Sampling analyses and yields expected regret bounds without a hyperparameter δ.

  • Takeaways & Limitations

    Closing the minimax lower bound without additional structural assumptions, extending the framework beyond its current model classes, and efficiently sampling non-conjugate α-posteriors remain open problems.

Abstract

from arXiv · show

We study a variant of the Thompson Sampling (TS) algorithm, called $α$-TS, for solving stochastic generalized linear bandit problems. Existing analyses of TS require inflating the posterior variance to derive near-optimal regret guarantees. We formalize the idea of variance inflation by introducing $α$-TS that uses a fractional or $α$-posterior instead of the standard posterior. Our main contribution is to identify general regularity conditions on the prior and reward distributions that enable a regret analysis of $α$-TS without assuming any tractable approximation of the posterior distribution, unlike previous works. For a specific choice of $α\propto d^{-1}$, our general regret bound yields the best known regret bound of $O(d^{3/2}\sqrt{T}\log T)$ for both the exponential and sub-Gaussian families of reward distributions. We further provide an $α$-dependent lower bound showing that the regret constant depends on the product $αd$, and that when $α\propto d^{-1}$ the regret scales as $Ω(d^{3/2}\sqrt{T})$, explaining the origin of the $d^{3/2}$ factor in the upper bound. Our proof technique adapts and combines recent advancements in the analysis of linear bandit problems with first- and second-order posterior concentration theory from the Bayesian statistics literature.

1 Introduction

The paper formalizes posterior variance inflation in Thompson Sampling through α-posterior sampling for generalized linear bandits. Under suitable α, it obtains near-optimal regret guarantees while extending analysis beyond conjugate Gaussian settings.

  • 1 Introduction: The analysis extends posterior-based regret guarantees beyond conjugate Gaussian models to general prior and reward combinations satisfying regularity conditions.The stated reward conditions include sub-Gaussian and exponential families.
  • 1 Introduction: α-TS replaces the standard posterior with a fractional posterior whose likelihood is tempered by α.The parameter α ∈ (0, 1) inflates posterior variance while preserving a Bayesian interpretation.
  • 1 Introduction: O(d^{3/2}√T log T) regret is obtained for exponential and sub-Gaussian rewards when α = d^-1.The bound is derived in expectation and removes dependence on a hyperparameter δ.
  • 1 Introduction: Without variance inflation, rapid posterior concentration makes optimistic samples unlikely and can produce exponential dependence on dimension d.Choosing α ≤ d^-1 maintains a constant probability of optimism and eliminates this exponential dependence.

2 Literature review

The literature develops stronger Thompson Sampling guarantees and richer contextual-bandit models, but existing approaches differ from this work in structural assumptions and action-set geometry.

  • 2 Literature review: Recent work seeks minimax-optimal frequentist regret for linear-bandit Thompson Sampling, including algorithms that switch between OFU and TS.Feel-Good Thompson Sampling modifies the likelihood and obtains lower-bound-matching guarantees under a finite model class.
  • 2 Literature review: The finite-model construction in Feel-Good Thompson Sampling relies on suboptimal actions that provide no information, violating this paper’s informative-action regularity conditions.The paper requires actions that distinguish nearby parameters and permit posterior concentration.
  • 2 Literature review: Other contextual-bandit studies consider semi-parametric, non-parametric, and high-dimensional reward models.These directions broaden model complexity beyond the setting emphasized in the paper.
  • 2 Literature review: Finite-arm contextual-bandit analyses depend on the number of arms K and exploit concentration with union bounds over the finite action set.The paper distinguishes these methods from its arbitrary action-space setting.

3 Problem setup

The problem is a stochastic generalized linear bandit with an arbitrary action space, sequential rewards, and performance measured by expected cumulative regret against an oracle action.

  • 3 Problem setup: The learner selects actions from an arbitrary space A ⊂ R^d over horizon T and observes rewards generated by an unknown environment.The history records past action-reward pairs and determines the learner’s information set.
  • 3 Problem setup: A strictly monotonic Lipschitz link function g represents the conditional mean reward through the unknown parameter.The model uses the action-parameter inner product as the link input.
  • 3 Problem setup: The oracle action maximizes g(a^Tθ0), and regret measures the cumulative loss from selecting suboptimal actions.The reported performance criterion is expected cumulative regret E[R(T)].
  • 3 Problem setup: α-TS samples a parameter from the α-posterior, chooses the action optimal for that sample, observes a reward, and updates the history.The α-posterior is defined relative to a prior and the observed action-reward likelihoods.
  • 3 Problem setup: The α-TS data-generating process combines the true reward model with the randomized action-selection rule induced by posterior sampling.Expectations are taken under the corresponding data-generating distribution.

4 Assumptions

The regret analysis assumes compact actions, regular link and reward models, prior thickness, and finite-sample posterior concentration conditions. These assumptions support first- and second-order control of the α-posterior and apply to key reward families.

  • 4 Assumptions: The action space is closed, bounded, and normalized so every action has Euclidean norm at most one.This is a standard compactness assumption in linear-bandit analysis.
  • 4 Assumptions: The link function is Lipschitz continuous and strictly monotonic with derivative bounded below by a positive constant.The identity link covers linear rewards, while exponential-family models use a distribution-specific mean link.
  • 4 Assumptions: Prior thickness requires sufficient prior mass near the true parameter, controlling α-posterior contraction through a shrinking neighborhood sequence.The paper notes that this condition is satisfied by bounded prior densities for exponential and sub-Gaussian rewards.
  • 4 Assumptions: Finite-sample Bernstein-von Mises analysis imposes local and global exponential-moment, curvature, and identifiability conditions on the likelihood.The local conditions replace asymptotic local asymptotic normality with finite-sample controls.
  • 4 Assumptions: The exponential-moment conditions require exponentially decaying reward tails, while local and global identifiability control likelihood separation from the true parameter.These conditions are summarized through ED0, ED1, L0, and Lr.
  • 4 Assumptions: First-order α-posterior concentration needs little reward regularity, whereas refined second-order analysis requires the broader condition set.The exponential and sub-Gaussian families satisfy all conditions under stated smoothness requirements.
  • 4 Assumptions: The prior is continuous, uniformly bounded above, and positive on every compact subset of the parameter space.These properties support the lower-bound analysis for general priors.

5 Lower Bound for α-TS

The lower-bound construction makes explicit how α and dimension d jointly control coordinate-error probabilities and expected regret under α-TS. When αd remains bounded, regret scales as Ω(d^{3/2}√T), showing that the d^{3/2} dependence in the upper bound cannot be avoided for this class.

  • Lower-bound construction: The construction uses a linear bandit with action set [-1,1]^d, Gaussian rewards, and a parameter whose coordinates are independently ±µ.The signal magnitude µ controls the interaction among dimension, tempering, and posterior sampling errors.
  • Error mechanism: The sampled parameter’s coordinate sign-error probability is governed by a signal-to-noise ratio involving the α-posterior mean and precision matrix.The derived ratio controls whether a sampled coordinate disagrees with the true parameter’s sign.
  • Error mechanism: For sufficiently large T, the coordinate error probability is bounded below by a constant multiple of a Gaussian tail term depending on αd.The second term in the Gaussian-CDF argument becomes negligible as T grows.
  • Regret consequence: When αd remains bounded by a constant, the Gaussian tail term stays bounded away from zero and expected regret scales as Ω(d^{3/2}√T).This follows after substituting the coordinate-error lower bound into the regret decomposition.
  • Regret consequence: The lower bound implies that the d^{3/2} dependence in the upper bound cannot be avoided for this class of posterior-sampling algorithms.This conclusion is formalized through a dimension–temperature lower-bound proposition.
  • Regret consequence: The regret constant depends on αd: smaller α inflates posterior covariance and increases sign-disagreement likelihood, whereas larger α accelerates concentration and reduces coordinate errors.The construction therefore highlights the importance of scaling α with dimension d.

6 Frequentist Regret Bound

The frequentist analysis bounds expected regret for α-TS by combining saturated-action decompositions with first- and second-order concentration properties of the α-posterior. Choosing α=d^{-1} controls dimension-dependent exponential terms and yields the stated regret rate for exponential and sub-Gaussian rewards.

  • General regret bound: Theorem 1 provides a general expected-regret bound for α-TS under Assumptions 2–7 and the condition α(1−α)λ<1.The theorem applies for any η>0, with additional terms determined by the regularity conditions.
  • Corollaries: For both exponential and sub-Gaussian reward families, choosing α=d^{-1} and sufficiently large warm-up iterations yields O(d^{3/2}√T log T).This choice balances dimension-dependent exponential terms; α=d^{-1} is identified as optimal within the stated scaling argument.
  • Proof strategy: The proof partitions actions into saturated and unsaturated sets and uses the fact that the optimal action is always unsaturated.The expected regret is decomposed into terms controlled using action-set geometry, posterior concentration, and probability of selecting unsaturated actions.
  • Proof strategy: The analysis derives posterior concentration and anti-concentration properties without relying on closed-form sampling distributions.It combines the saturated-action proof idea with first- and second-order α-posterior properties and expectation-based arguments.
  • Posterior properties: The α-posterior contraction analysis determines the rate at which posterior mass concentrates around the true parameter through the sequence ε_t.The proof uses posterior concentration results and a finite-sample Bernstein–von Mises bound.
  • Posterior properties: The finite-sample Bernstein–von Mises result supplies a concentration approximation under exponential-moment and identifiability conditions on rewards, together with a prior-density condition.The result holds for α∈(0,1) and includes a time-dependent approximation term decreasing with t.

7 Examples

The paper verifies its α-posterior framework for exponential-family and sub-Gaussian reward models under explicit regularity conditions. For both families, choosing α=d^-1 yields the stated regret scaling.

  • Examples: The analysis covers two reward-model classes: exponential families and sub-Gaussian distributions.The paper states definitions and assumptions for both classes before deriving their corollaries.
  • 7.1 Exponential family: Exponential-family models require Lipschitz link-function conditions and strong convexity of the log-partition function.The assumptions impose bounds on the link function, its derivative, and the curvature of the log-partition function.
  • 7.1 Exponential family: These exponential-family conditions are restrictive because they require variances of distributions such as Poisson or Exponential to lie in a compact space.The paper notes that the required curvature and Lipschitz conditions constrain the admissible variance behavior.
  • 7.1 Exponential family: For exponential-family rewards, the paper derives the required α-posterior concentration quantities and establishes the corollary for α=d^-1.The supporting lemmas verify the second-order α-posterior conditions used in the regret analysis.
  • 7.2 Sub-Gaussian Family: For sub-Gaussian rewards, the framework assumes conditionally bounded sub-Gaussian noise, means in [0,1], and additional regularity of the error density.The paper states that these assumptions imply the first- and second-order α-posterior properties needed by the analysis.
  • 7.2 Sub-Gaussian Family: The sub-Gaussian analysis also supports a similar regret bound for generalized mean rewards g(a^Tθ) when the link function satisfies the stated assumption.The extension is obtained by imposing the corresponding regularity condition on g.

8 Conclusion

The conclusion presents α-TS as a posterior-sampling framework that formalizes variance inflation without requiring a tractable posterior representation. With α=d^-1, it recovers the stated regret rate for both reward families and identifies open extensions.

  • 8 Conclusion: α-TS uses a fractional posterior and provides a frequentist regret analysis under structural regularity conditions on the prior and reward model.The framework does not require a tractable closed-form posterior representation.
  • 8 Conclusion: The method interprets the variance inflation used in existing Thompson Sampling analyses without introducing a new algorithmic procedure.The paper characterizes α-TS as a principled interpretation of an analysis device already used in prior work.
  • 8 Conclusion: For α=d^-1, the regret is O(d^3/2√T log T) for both exponential-family and sub-Gaussian reward distributions.The conclusion states that this matches state-of-the-art Thompson Sampling guarantees.
  • 8 Conclusion: The lower-bound construction shows that the d^3/2 dependence is unavoidable for this class of posterior-sampling algorithms.The construction is α-dependent and relates the regret scaling to the tempering parameter and dimension.
  • Future directions: Open directions include closing the minimax lower-bound gap and extending the framework to misspecified, non-stationary, or infinite-dimensional settings.The paper also identifies efficient α-posterior sampling in non-conjugate models as a next step.

B Proof of Proposition 1

The proposition’s proof reduces regret to coordinate-wise sign errors between the sampled and true parameters, then analyzes the sampled posterior and Gaussian noise contributions.

  • Proof of Proposition 1: For θ0∈{±μ}^d and A=[−1,1]^d, the optimal and sampled actions are coordinate-wise sign vectors.The proof uses a0=sign(θ0) and at=sign(θ̃t), except on zero-probability ties.
  • Proof of Proposition 1: The instantaneous regret equals 2μ times the number of coordinates where the sampled action has the wrong sign.Taking expectations converts total regret into a sum of coordinate-wise sign-error probabilities.
  • Proof of Proposition 1: The sampled parameter is analyzed through its α-dependent Gaussian distribution.This distribution determines the probability of coordinate-wise action errors.
  • Proof of Proposition 1: Conditional on the history, the noise contribution is centered Gaussian because it is a linear combination of independent Gaussian noises.The proof then applies Gaussian tail reasoning to this noise term.

C Proof of Theorem 1

Theorem 1’s proof combines posterior concentration, optimism probability, and elliptical-potential arguments to control regret contributions from different action classes.

  • Proof of Theorem 1: The proof defines history-adapted concentration sets for controlling the α-posterior around the true parameter.These sets are used to organize the posterior and parameter-deviation bounds.
  • Proof of Theorem 1: A posterior-mass lemma bounds the α-posterior of parameter-deviation events using quadratic distance and divergence terms.The proof derives monotonicity and tail bounds for these events as the threshold increases.
  • Proof of Theorem 1: The proof establishes a lower bound on sampling along the best action sequence through α-posterior probability estimates.The resulting probability bound is expressed using a deviation term depending on dimension and η.
  • Proof of Theorem 1: Elliptical-potential and Cauchy–Schwarz arguments control terms involving action norms and parameter deviations.The proof applies these tools to saturated and unsaturated action contributions.
  • Proof of Theorem 1: Combining the decomposed terms with the posterior concentration bounds yields the theorem’s regret control after selecting sufficiently large time thresholds.The proof uses the monotonicity of the deviation term and the elliptical-potential lemma in the final aggregation.
  • Proof of Theorem 1: The argument shows that if the sampled parameter is optimistic on saturated actions, an unsaturated action must be selected.This event connects posterior optimism to the action-selection decomposition used in the regret bound.

D Verifying assumptions for the Exponential family

The section verifies that exponential-family rewards satisfy the paper’s regularity assumptions by analyzing likelihood derivatives, Rényi divergences, prior-density conditions, and finite-sample posterior concentration.

  • Rényi-divergence bounds: The section derives α-Rényi divergence expressions and bounds them using second-order mean-value arguments, Cauchy–Schwarz, and the exponential-family regularity conditions.These bounds feed into the stated choices of constants and tolerance sequences used to verify the assumptions.
  • Prior conditions: The prior-density condition holds because the prior density is strictly positive everywhere, yielding a positive lower bound Cϕ on local parameter balls.The bound applies for all t ≥ t0 and coordinates i in the stated local neighborhoods.
  • Likelihood regularity: Exponential-family likelihoods satisfy the required stochastic regularity because the centered gradient has zero expectation and is independent of θ, making its Hessian zero.The argument uses the conditional log-likelihood and its stochastic component to establish these properties.
  • Posterior concentration conditions: The exponential family satisfies Assumption 6, with ED0 verified using g := g1T^1/2 and ED1 available for any ω > 0 and g > 0.The proof derives the conditions sequentially from a technical lemma and bounds involving the action vectors and link function.
  • Local concentration: For sufficiently large t, choosing η = O(d) makes Δ_t(d, η) ≤ 1, completing a key local-concentration requirement.The displayed bound is obtained after selecting ω according to δ(r0), v0, and z_H(η).
Loading 2609.01999v1…