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

arXiv: https://arxiv.org/abs/2603.10184 · HTML: https://mlsanity.com/paper/2603.10184/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2026.

## Built on by (most cited first, 1 of 1)

- [Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits](https://mlsanity.com/paper/2608.17841/) (2026)

## Abstract (arXiv)

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~citeplaiwei82 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~citetlaiwei82 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(√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.