Stable Thompson Sampling: Valid Inference via Variance Inflation

2025/05/29 by B. Halder, S Pan, Halder, Budhaditya +3 · 1 citation
Decision Sciences · Mathematics · Medicine · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #SARS-CoV-2 detection and testing #Statistical Methods and Bayesian Inference

paper · pdf · doi:10.48550/arxiv.2505.23260

openalex publication_date 2025/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the problem of statistical inference when the data is collected via a Thompson Sampling-type algorithm. While Thompson Sampling (TS) is known to be both asymptotically optimal and empirically effective, its adaptive sampling scheme poses challenges for constructing confidence intervals for model parameters. We propose and analyze a variant of TS, called Stable Thompson Sampling, in which the posterior variance is inflated by a logarithmic factor. We show that this modification leads to asymptotically normal estimates of the arm means, despite the non-i.i.d. nature of the data. Importantly, this statistical benefit comes at a modest cost: the variance inflation increases regret by only a logarithmic factor compared to standard TS. Our results reveal a principled trade-off: by paying a small price in regret, one can enable valid statistical inference for adaptive decision-making algorithms.

Citations

• UCB algorithms for multi-armed bandits: Precise regret and adaptive inference
• Inference with the Upper Confidence Bound Algorithm
• Oralytics Reinforcement Learning Algorithm
• Statistical Limits of Adaptive Linear Models: Low-Dimensional Estimation and Inference
• Adaptive Linear Estimating Equations
• Semi-parametric inference based on adaptively collected data
• Anytime-valid off-policy inference for contextual bandits
• The Typical Behavior of Bandit Algorithms
• Near-optimal inference in adaptive linear regression
• Off-Policy Evaluation via Adaptive Weighting with Data from Contextual Bandits
• A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms
• Post-Contextual-Bandit Inference
• Confidence Intervals for Policy Evaluation in Adaptive Experiments
• Online Debiasing for Adaptively Collected High-dimensional Data with\n Applications to Time Series Analysis
• Are sample means in multi-armed bandits positively or negatively biased?
• On the bias, risk and consistency of sample means in multi-armed bandits
• Time-uniform Chernoff bounds via nonnegative supermartingales
• Accurate Inference for Adaptive Linear Models
• Risk-Aware Multi-Armed Bandit Problem with Application to Portfolio Selection
• Why Adaptively Collected Data Have Negative Bias and How to Correct for It
• Confidence intervals for AB-test
• Thompson Sampling for 1-Dimensional Exponential Family Bandits
• Thompson Sampling: An Asymptotically Optimal Finite Time Analysis
• Confidence Intervals for Low-Dimensional Parameters in High-Dimensional Linear Models
• Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws
• Least Squares Estimates in Stochastic Regression Models with Applications to Identification and Control of Dynamic Systems
• Distribution of the Estimators for Autoregressive Time Series with a Unit Root
• The Nonstochastic Multiarmed Bandit Problem

Cited by

• Avoiding the Price of Adaptivity: Inference in Linear Contextual Bandits via Stability

Related

• Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling
• On Frequentist Regret of Linear Thompson Sampling
• Thompson Sampling on Symmetric α-Stable Bandits
• A Broader View of Thompson Sampling
• The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models