Randomized Exploration for Linear Bandits via Absolute Perturbations

Toshinori Kitamura; Shuai Liu; Csaba Szepesvári

cs.LGJun 26, 2026

Randomized Exploration for Linear Bandits via Absolute Perturbations

Authors: Toshinori Kitamura, Shuai Liu, Csaba Szepesvári

Organizations: Department of Computing Science, University of Alberta, Canada

Abstract

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.

Explore similar work

Sep 2, 2026stat.ML

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

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.

Prateek Jaiswal, Debdeep Pati, Anirban Bhattacharya +1

Thompson Sampling Generalized Linear Bandit Variance Trust Region Regret Posterior

Ask PDF

May 29, 2026cs.LG

Variance-sensitive Thompson sampling for generalised linear bandits, revisited

We prove a variance-sensitive regret bound for Thompson sampling in stochastic generalised linear bandits. The argument assumes a warm-up, after which the regret is controlled through using the Gaussian Poincaré inequality. This bypasses the point at which previous optimism-based analyses break down. Removing the warm-up while retaining the same variance-sensitive scaling remains open, and appears nontrivial.

Tom Perneczky, Marc Abeille, David Janz

Thompson Sampling Dynamic Regret Bounds Generalized Linear Bandit Pessimism

Ask PDF

May 10, 2026cs.LG

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

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.

Zhiming Huang, Bingshan Hu, Jianping Pan

Thompson Sampling Sublinear Regret Worst-Case Sensitivity

Ask PDF