Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits

Zhiming Huang; Bingshan Hu; Jianping Pan

cs.LGMay 10, 2026

Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits

Authors: Zhiming Huang, Bingshan Hu, Jianping Pan

Abstract

We revisit combinatorial Thompson sampling (CTS) for semi-bandits with sleeping arms, where arm availability varies over time and actions must satisfy combinatorial constraints, as in wireless mesh routing with fluctuating link availability. Despite its practical relevance, CTS has been hindered by several long-standing problems: (i) the absence of worst-case regret guarantees in the semi-bandit setting even without sleeping arms, (ii) the lack of theory under adversarially varying availability, and (iii) the consistently weak empirical performance of CTS with Gaussian priors (CTS-G). This paper resolves these long-standing issues by providing the first worst-case regret analysis of CTS-G, proving an upper bound of $\tilde{O}(m\sqrt{NT})$ and a matching lower bound of $\tildeΩ(m\sqrt{NT})$ . To bridge the gap between theory and practice, we further propose CL-SG, a simple CTS-G variant that samples a single shared Gaussian seed each round to coordinate exploration across arms. We show that CL-SG achieves an improved regret bound of $\tilde{O}(\sqrt{mNT})$ , together with a matching lower bound $Ω(\sqrt{mNT})$ . Experiments on real-world datasets demonstrate that CL-SG consistently outperforms strong baselines including CTS-G and CTS-B, and we open-source our implementation for reproducibility.

Explore similar work

Jun 26, 2026cs.LG

Randomized Exploration for Linear Bandits via Absolute Perturbations

In stochastic linear bandits, the canonical Upper Confidence Bound (UCB) algorithm admits a simple frequentist regret analysis but can be computationally demanding, while Thompson Sampling (TS) is computationally attractive yet typically harder to analyze due to its non-optimistic nature. We propose Absolute Thompson Sampling (ATS), a simple modification of TS that ensures optimism in expectation by replacing the signed exploration noise with its absolute value. This preserves the computational efficiency of TS while avoiding the technically involved anti-concentration arguments common in TS analyses, enabling a simple UCB-style regret analysis. We show that ATS achieves

\tilde{O}(d^{3/2}\sqrt{K})

regret, matching existing bounds for TS in linear bandits. We further introduce Ensemble Absolute Thompson Sampling (EATS), which takes the maximum over multiple absolute perturbations with normalization by the ensemble size. As the ensemble size grows, EATS converges to the UCB objective, recovering UCB behavior in the limit. Experiments show that moderate ensemble sizes already yield strong performance. Our results point to a bridge between randomized exploration and deterministic optimism both in theory and practice.

Toshinori Kitamura, Shuai Liu, Csaba Szepesvári

Thompson Sampling Linear Bandits Efficient Exploration Pessimism Autonomous Exploration Strategies Perturbations

Ask PDF

Jun 8, 2026cs.LG

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

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.

Joel Q. L. Chang

Thompson Sampling Long-Tailed Distribution

Ask PDF

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