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

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 46 references that are in the map.
- First posted on arXiv 23 Dec 2025.

## Builds on (most cited first, 28 of 28)

- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Confidence Intervals for Policy Evaluation in Adaptive Experiments](https://mlsanity.com/paper/1911.02768/) (2019)
- [Inference for Batched Bandits](https://mlsanity.com/paper/2002.03217/) (2020)
- [Accurate Inference for Adaptive Linear Models](https://mlsanity.com/paper/1712.06695/) (2017)
- [Anytime-valid off-policy inference for contextual bandits](https://mlsanity.com/paper/2210.10768/) (2022)
- [Why Adaptively Collected Data Have Negative Bias and How to Correct for It](https://mlsanity.com/paper/1708.01977/) (2017)
- [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021)
- [On the bias, risk and consistency of sample means in multi-armed bandits](https://mlsanity.com/paper/1902.00746/) (2019)
- [Sparsity, variance and curvature in multi-armed bandits](https://mlsanity.com/paper/1711.01037/) (2017)
- [Are sample means in multi-armed bandits positively or negatively biased?](https://mlsanity.com/paper/1905.11397/) (2019)
- [Near-optimal inference in adaptive linear regression](https://mlsanity.com/paper/2107.02266/) (2021)
- [UCB algorithms for multi-armed bandits: Precise regret and adaptive inference](https://mlsanity.com/paper/2412.06126/) (2024)
- [Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2103.12487/) (2021)
- [Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2209.06983/) (2022)
- [Online Debiasing for Adaptively Collected High-dimensional Data with Applications to Time Series Analysis](https://mlsanity.com/paper/1911.01040/) (2019)
- [Open Problem: Tight Online Confidence Intervals for RKHS Elements](https://mlsanity.com/paper/2110.15458/) (2021)
- [Statistical Inference After Adaptive Sampling for Longitudinal Data](https://mlsanity.com/paper/2202.07098/) (2022)
- [The Typical Behavior of Bandit Algorithms](https://mlsanity.com/paper/2210.05660/) (2022)
- [Inference with the Upper Confidence Bound Algorithm](https://mlsanity.com/paper/2408.04595/) (2024)
- [Stable Thompson Sampling: Valid Inference via Variance Inflation](https://mlsanity.com/paper/2505.23260/) (2025)
- [Randomization Tests for Adaptively Collected Data](https://mlsanity.com/paper/2301.05365/) (2023)
- [Statistical Inference under Adaptive Sampling with LinUCB](https://mlsanity.com/paper/2512.00222/) (2025)
- [Allocation Stability and Wald Inference under Variance-Aware UCB](https://mlsanity.com/paper/2412.08843/) (2024)
- [Adaptive Off-Policy Inference for M-Estimators Under Model Misspecification](https://mlsanity.com/paper/2509.14218/) (2025)
- [On Instability of Minimax Optimal Optimism-Based Bandit Algorithms](https://mlsanity.com/paper/2511.18750/) (2025)
- [Debiasing Samples from Online Learning Using Bootstrap](https://mlsanity.com/paper/2108.00236/) (2021)

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

- [Optimism Stabilizes Thompson Sampling for Adaptive Inference](https://mlsanity.com/paper/2602.06014/) (2026)
- [Bandit Simulation for Average Reward Inference](https://mlsanity.com/paper/2606.00913/) (2026)

## Abstract (arXiv)

Statistical inference in contextual bandits is challenging due to the adaptive, non-i.i.d. nature of the data. A growing body of work shows that classical least-squares inference can fail under adaptive sampling, and that valid confidence intervals for linear functionals typically require an inflation of order √d log T. This phenomenon -- often termed the price of adaptivity -- reflects the intrinsic difficulty of reliable inference under general contextual bandit policies. A key structural condition that overcomes this limitation is the stability condition of Lai and Wei, which requires the empirical feature covariance to converge to a deterministic limit. When stability holds, the ordinary least-squares estimator satisfies a central limit theorem, and classical Wald-type confidence intervals remain asymptotically valid under adaptation, without incurring the √d log T price of adaptivity. In this paper, we propose and analyze a regularized EXP4 algorithm for linear contextual bandits. Our first main result shows that this procedure satisfies the Lai--Wei stability condition and therefore admits valid Wald-type confidence intervals for linear functionals. We additionally provide quantitative rates of convergence in the associated central limit theorem. Our second result establishes that the same algorithm achieves regret guarantees that are minimax optimal up to logarithmic factors, demonstrating that stability and statistical efficiency can coexist within a single contextual bandit method. As an application of our theory, we show how it can be used to construct confidence intervals for the conditional average treatment effect (CATE) under adaptively collected data. Finally, we complement our theory with simulations illustrating the empirical normality of the resulting estimators and the sharpness of the corresponding confidence intervals.