Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

Joel Q. L. Chang

cs.LGJun 8, 2026

Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

Authors: Joel Q. L. Chang

Abstract

We prove that $ρ\text{-}\mathrm{NPTS}_{\mathrm{SG}}$ , an anchor-free nonparametric Thompson Sampling algorithm for risk-averse bandits, achieves regret matching the instance-dependent lower bound to leading order in $\log n$ , establishing it as asymptotically optimal for any continuous risk functional $ρ$ (CVaR, mean-variance, Sharpe ratio, distortion risk measures, and more) on the class of distributions with bounded density and sub-Gaussian tails, including Gaussian arms. Both this result and its bounded-support counterpart require only continuity of $ρ$ : strictly weaker than the dominance condition of prior parametric Thompson Sampling results, and strictly weaker than the Lipschitz condition of UCB-type algorithms, yielding the first instance-optimal guarantees for non-Lipschitz functionals such as the Sharpe ratio without parametric reward assumptions. The bounded-support case is developed first as a stepping stone sharing the same proof structure. The key technical contributions are a discretisation lemma (bounded support) and a truncated discretisation lemma (sub-Gaussian tails), each projecting the growing-alphabet Dirichlet posterior onto a fixed grid via the Dirichlet aggregation property, holding all polynomial prefactors at fixed degree independent of sample size and breaking the super-exponential barrier that blocked prior proofs.

Explore similar work

Sep 12, 2023stat.ML

Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors

Thompson sampling (TS) is one of the most popular and earliest algorithms to solve stochastic multi-armed bandit problems. We consider a variant of TS, named

α

-TS, where we use a fractional or

α

-posterior (

α\in(0,1)

) instead of the standard posterior distribution. To compute an

α

-posterior, the likelihood in the definition of the standard posterior is tempered with a factor

α

. For

α

-TS we obtain both instance-dependent

\mathcal{O}\left(\sum_{k \neq i^*} Δ_k\left(\frac{\log(T)}{C(α)Δ_k^2} + \frac{1}{2} \right)\right)

and instance-independent

\mathcal{O}(\sqrt{KT\log K})

frequentist regret bounds under very mild conditions on the prior and reward distributions, where

Δ_k

is the gap between the true mean rewards of the

k^{th}

and the best arms, and

C(α)

is a known constant. Both the sub-Gaussian and exponential family models satisfy our general conditions on the reward distribution. Our conditions on the prior distribution can be easily satisfied by a density that is positive, continuous, and bounded. We also establish another instance-dependent regret upper bound that matches (up to constants) to that of improved UCB [Auer and Ortner, 2010]. Our regret analysis carefully adapts and combines recent theoretical developments in the non-asymptotic concentration analysis and Bernstein-von Mises type results for the

α

-posterior distribution. Moreover, our analysis does not require additional structural properties such as closed-form posteriors or conjugate priors.

Prateek Jaiswal, Debdeep Pati, Anirban Bhattacharya +1

Thompson Sampling Near-Optimal Regret Guarantees Linear Bandits Regret Posterior

Ask PDF

Sep 11, 2026cs.LG

Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret

Bakhtiari, Lattimore and Szepesv'ari (COLT 2025) proved that Thompson sampling (TS) has Bayesian regret

\tilde O(d^{5/2}\sqrt n)

for bandit convex optimisation with convex \emph{monotone} ridge losses

f(x)=\ell(\ip{x}{\theta})

, and asked whether monotonicity of the link is necessary. We give a qualitative negative answer. For every prior on

[0,1]

-valued,

1

-Lipschitz convex ridge losses with an arbitrary convex, possibly non-monotone, link, and for any fixed measurable selection of minimisers, exact-posterior TS has Bayesian regret

O\big((d+1)^4\sqrt{dn}\,\log(e+nd\max\{1,\diam K\})\big)=\tilde O(d^{9/2}\sqrt n)

. The monotone proof relies on a single-removal John-ellipsoid dichotomy; we show by an explicit twelve-point configuration that this dichotomy fails for non-monotone links, and replace it by an

O(d^2)

cardinality bound for ``uninformative'' configurations. The bound uses a Boolean rounding argument: a

0

1

matrix within

1/(4r)

in max-norm of a rank-

r

matrix has rank at most

2r-1

. We construct

d(d+1)

uninformative losses, showing that the cardinality bound is tight up to constants in the large-diameter-to-gap regime, and give a self-contained information-ratio-to-regret transfer that is uniform over fixed measurable selections. Whether the

d^{5/2}

dependence of the monotone case can be retained remains open.

Xuan Li

Thompson Sampling Linear Regret Monotonicity

Ask PDF

Jan 5, 2026cs.LG

Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

We prove that Thompson sampling exhibits

\tilde{O}(σd \sqrt{T} + d r \sqrt{\mathrm{Tr}(Σ_0)})

Bayesian regret in the linear-Gaussian bandit with a

\mathcal{N}(μ_0, Σ_0)

prior distribution on the coefficients, where

d

is the dimension,

T

is the time horizon,

r

is the maximum

\ell_2

norm of the actions, and

σ^2

is the noise variance. In contrast to existing regret bounds, this shows that to within logarithmic factors, the prior-dependent

burn-in'' term $d r \sqrt{\mathrm{Tr}(Σ_0)}$ decouples additively from the minimax (long run) regret $σd \sqrt{T}$. Previous regret bounds exhibit a multiplicative dependence on these terms. We establish these results via a new

elliptical potential'' lemma, and also provide a lower bound indicating that the burn-in term is unavoidable.

Yifan Zhu, John C. Duchi, Benjamin Van Roy

Thompson Sampling Linear Regret Regret Bayesian Prior Knowledge

Ask PDF