Stabilizing Bandits using Regularization: Precise Regret and A Quantitative Central Limit Theorem

Budhaditya Halder; Ishan Sengupta; Koustav Chowdhury; Samya Praharaj; Koulik Khamaru

stat.MLMar 10, 2026

Stabilizing Bandits using Regularization: Precise Regret and A Quantitative Central Limit Theorem

Authors: Budhaditya Halder, Ishan Sengupta, Koustav Chowdhury, Samya Praharaj, Koulik Khamaru

Organizations: Department of Statistics, Rutgers University · Indian Statistical Institute, Kolkata

Abstract

Statistical inference with bandit data presents fundamental challenges owing to adaptive sampling, which violates the independence assumptions underlying classical asymptotic theory. Recent work has identified stability~\citep{laiwei82} as a sufficient condition for valid inference under adaptivity. This paper first provides a refined stability condition, stated in terms of the iterates of an online algorithm, and shows that a large class of regularized stochastic-mirror-descent-style algorithms satisfy it. This refined condition allows us to strengthen the asymptotic results of~\citet{laiwei82} in several ways. First, we derive a non-asymptotic Berry--Esseen bound for the empirical reward estimates under adaptive sampling. Second, we derive matching non-asymptotic upper and lower bounds on the regret of the proposed algorithm, yielding a precise characterization of its regret. Third, we show that these regularized algorithms preserve asymptotic normality and valid inference under a prescribed level of adversarial corruption. Finally, we show that regularization is necessary rather than incidental: Lai--Wei stability is incompatible with the optimal $O(\sqrt{T})$ regret rate -- the rate attained by unregularized algorithms such as EXP3 -- so that a controlled, polylogarithmic inflation in regret is the price of valid inference.

Figures & tables

Panel of Figure 1 — Figure 1: Empirical behavior for Algorithm 1 for Bernoulli bandit with $\mu=(0.9,0.3,0.1)^{\top}$ and $\alpha=1$ : standardized estimation errors $\sqrt{n_{a,T}}(\widehat{\mu}_{a,T}-\mu_{a})/\widehat{\sigma}_{a,T}$ are approximately standard normal.

Panel of Figure 2 — Figure 2: Empirical behavior for Algorithm 1 for Bernoulli bandit with $\mu=(0.9,0.3,0.1)^{\top}$ : empirical coverage probabilities nearly aligned with diagonal.

Panel of Figure 3 — Figure 3: Empirical behavior for Algorithm 1 for Bernoulli bandit with $\mu=(0.7,0.7,0.7)^{\top}$ and $\alpha=1/2$ : the proportion of pulls concentrate around $1/3$ for each arm.

Panel of Figure 4 — Figure 4: Empirical behavior for Algorithm 1 for Bernoulli bandit with $\mu=(0.7,0.7,0.7)^{\top}$ and $\alpha=1/2$ : standardized estimation errors $\sqrt{n_{a,T}}(\widehat{\mu}_{a,T}-\mu_{a})/\widehat{\sigma}_{a,T}$ are approximately standard normal.

Explore similar work

Sharp Characterization of Bias in Post-Bandit Inference
Aug 2, 2026Lisu Wang, Yilun Chen, Jiaqi LuMulti-Armed Bandits Algorithmic Bias
School of Data Science, The Chinese University of Hong Kong, Shenzhen · School of Management and Economics, The Chinese University of Hong Kong, Shenzhen
Efficient Inference after Directionally Stable Adaptive Experiments
Feb 25, 2026Zikai Shen, Houssam Zenati, Nathan Kallus +3Adaptive Inference Semiparametric Inference
University College London · Gatsby Computational Neuroscience Unit, University College London · Cornell University +3
Statistical Inference for Misspecified Contextual Bandits
Jun 21, 2026Yongyi Guo, Ziping XuInverse Probability Weighting Adaptive Inference
Department of Statistics, University of Wisconsin–Madison · School of Data Science and Society, University of North Carolina at Chapel Hill

Aug 2, 2026J/K move · Enter open · S save

Sharp Characterization of Bias in Post-Bandit Inference

Lisu Wang, Yilun Chen, Jiaqi Lu

School of Data Science, The Chinese University of Hong Kong, Shenzhen · School of Management and Economics, The Chinese University of Hong Kong, Shenzhen

Multi-Armed Bandits Algorithmic Bias UCB Algorithms

Open paper AskPDF arXiv

Bandit algorithms generate data for downstream inference, but adaptive sampling biases post-bandit sample means. We analyze this bias for stable index algorithms, including UCB1 and its generalizations, and derive sharp leading-order expressions for the sample-mean bias and expected

Z

-statistic, in bandit experiments of fixed horizon

T

. Our characterization reveals the algorithmic origin of bias through a key index-function-dependent quantity, which we term effective exploration rate. For example, under UCB1, the effective exploration rate is of order

\sqrt{\log T}

, and the standardized bias of any arm (that is not uniquely optimal) decays at the extremely slow rate

1/\sqrt{\log T}

. We also show how the choice of the index function affects both regret and bias, which reveals a regret-bias trade-off: more exploratory algorithm reduces bias but increases regret. We further show how bias most severely distorts confidence intervals and hypothesis tests when the tested arm is one of the tied-optimal arms. Our sharp characterization for bias uses a novel empirical fluid approximation of the algorithm's sampling dynamics, which may be of independent interest.

Abstract

Explore similar work

Sharp Characterization of Bias in Post-Bandit Inference

Efficient Inference after Directionally Stable Adaptive Experiments

Statistical Inference for Misspecified Contextual Bandits