The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits

Sharan Sahu; Martin T. Wells

stat.MLOct 21, 2026

The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits

Authors: Sharan Sahu, Martin T. Wells

Organizations: Department of Statistics and Data Science, Cornell University

Abstract

Adaptive experiments use bandit algorithms to favor interventions with higher expected rewards. However, decision-makers also require reliable inference on current treatment effects: differences between intervention and reference-arm mean rewards at the present time, rather than historical averages. These objectives conflict: reward maximization favors better interventions, whereas current-effect inference requires continued exploration of potentially suboptimal interventions as outcomes change over time. We characterize this tradeoff for $K$ -arm bandits with Hölder-smooth mean rewards of exponent $β\in(0,1]$ and constant $L$ . Requiring high-probability simultaneous coverage of all current effects by confidence intervals of width at most $w$ , we establish matching minimax bounds, up to logarithmic factors, on expected dynamic regret. Over horizon $T$ , our algorithm TRACE (Tracking Rewards and Current Effects) achieves regret of order $\widetilde{O}_β\left(\sqrt{KT}+K^{β/(2β+1)}L^{1/(2β+1)}T^{(β+1)/(2β+1)}+Kw^{-2}(1+L^{1/β}w^{-1/β})\right)$ , where the notation hides logarithms and constants depending only on $β$ . This regret--precision tradeoff separates reward-learning regret from the cost of refreshing current-effect estimates, which remains unavoidable even when one arm is uniformly optimal. An empirical-Bernstein e-process extension adapts exploration to realized prediction errors while preserving worst-case guarantees. When within-block drift is negligible relative to sampling error, all observations, including reward-learning observations, can be reused for asymptotically normal pointwise inference and stronger local stationarity yields local asymptotic efficiency. Finally, we show that regret constraints can prevent honest adaptation to unknown smoothness and support our theory with extensive numerical experiments.

Figures & tables

Figure 1: Minimax regret–precision tradeoff. Narrower confidence intervals require more frequent exploration and therefore increase regret. The free-inference threshold $w_{\mathrm{free}}(T)$ separates the inference-limited regime from the regime where current-effect inference is essentially free at the minimax regret scale.

Figure 2: Overview of TRACE . The horizon is partitioned into consecutive blocks $\mathcal{B}_{1},\ldots,\mathcal{B}_{J}$ . At the beginning of each block, TRACE samples all arms in round-robin order to collect fresh observations for current-effect inference. On the remaining rounds, it runs EXP3 for reward learning. Inference in block $\mathcal{B}_{j}$ , $j\geq 2$ , uses estimates constructed from the preceding block, allowing the procedure to maintain up-to-date confidence intervals while continuing to optimize reward.

Panel of Figure 3 — Figure 3: Synthetic experiments. Left: Dynamic regret as the target width $w$ varies. Middle: Total inference samples, with $w^{-3}$ and $w^{-2}$ reference rates. Right: Samples required per arm and block as prediction RMSE increases.

Panel of Figure 4 — Figure 4: Synthetic local-stationarity experiment. Left: Coverage of the nominal $95\%$ confidence interval under the three drift regimes. Right: Average confidence-interval width using all observations versus reserved inference observations only.

Panel of Figure 5 — Figure 5: Yahoo! R6B experiment. Left: Current click-through-rate effects relative to Article 1. Middle: Dynamic regret versus current-effect RMSE for TRACE and Adaptive TRACE , with restarted EXP3 and SW-UCB as reward-only baselines. Right: Fraction of rounds used for inference as the maximum budget $m$ increases.

Panel of Figure 6 — Figure 6: ZOZOTOWN experiment. Left: Number of observations required for inference as a function of prediction RMSE. Right: Available observations and observations used by Adaptive TRACE with the Beta $(1,1)$ predictor across the five selected items.

Panel of Figure 7 — Figure 7: HeartSteps experiment. Left: Time-varying proximal treatment effect estimated using WCLS, together with weekly randomized contrasts. Middle: Empirical coverage of the all-observation Wald interval as a function of the local-drift index $\Gamma_{h}$ . Numbers indicate the local window length in days. Right: Empirical variance relative to the all-observation efficiency bound, comparing the all-observation estimator with inference based on a $25\%$ reserved subset.

Estimand	Estimate	$95\%$ CI	$p$ -value
Marginal proximal effect	$0.1312$	$[-0.0058,\,0.2682]$	$0.0599$
Effect at study day $0$	$0.5074$	$[0.2009,\,0.8140]$	$0.0020$
Change in effect per day	$-0.01848$	$[-0.03090,\,-0.00607]$	$0.00479$

Table 1: WCLS estimates for HeartSteps.

Window	$\Gamma_{h}$	Coverage	Variance ratio	Reserved variance ratio
$1$ day	$0.026$	$94.6\%$	$0.994$	$4.14$
$2$ days	$0.075$	$94.5\%$	$1.004$	$4.16$
$3$ days	$0.138$	$94.7\%$	$1.001$	$4.13$
$5$ days	$0.295$	$94.4\%$	$1.006$	$4.00$
$7$ days	$0.511$	$94.0\%$	$0.978$	$4.07$
$10$ days	$0.906$	$91.4\%$	$1.006$	$4.02$

Table 2: HeartSteps local-inference results. Empirical

95\%

coverage and variance relative to the all-observation efficiency bound, averaged over the five target days.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

	TRACE			Adaptive TRACE
$m$	Inference fraction	Regret	Effect RMSE	Inference fraction	Regret	Effect RMSE
25	$2.5\%$	$1353.8$	$0.0578$	$2.5\%$	$1354.3$	$0.0574$
50	$5.0\%$	$1363.5$	$0.0407$	$5.0\%$	$1349.0$	$0.0410$
100	$10.0\%$	$1387.3$	$0.0290$	$9.9\%$	$1385.8$	$0.0295$
200	$20.0\%$	$1430.6$	$0.0207$	$15.0\%$	$1400.8$	$0.0231$
400	$40.0\%$	$1506.8$	$0.0147$	$22.2\%$	$1432.0$	$0.0191$

Appendix

Table 3: Yahoo! R6B results. Dynamic regret, current-effect RMSE, and fraction of rounds used for inference across inferential budgets. Adaptive TRACE uses the Beta

(1,1)

-smoothed historical click-through rate as its predictable reward forecast. Results are averaged over

200

Monte Carlo replications.

Item	Available	Observations used	Prediction RMSE	Reduction
18	$5{,}312$	$3{,}441$	$0.0628$	$35.2\%$
30	$5{,}156$	$3{,}012$	$0.0462$	$41.6\%$
29	$5{,}584$	$2{,}705$	$0.0354$	$51.6\%$
24	$5{,}486$	$3{,}685$	$0.0687$	$32.8\%$
43	$5{,}146$	$2{,}892$	$0.0442$	$43.8\%$
Mean	$5{,}336.8$	$3{,}147.0$	$0.0514$	$41.0\%$

Appendix

Table 4: ZOZOTOWN results. Prediction RMSE and number of randomized observations required by Adaptive TRACE for each selected item. The predictable reward forecast is the Beta

(1,1)

-smoothed historical click-through rate computed using only observations preceding the current impression.

Week	Decisions	Treated	Control	Estimate	$95\%$ CI
1	$960$	$576$	$384$	$0.621$	$[0.298,\ 0.945]$
2	$1{,}061$	$635$	$426$	$0.015$	$[-0.391,\ 0.421]$
3	$1{,}037$	$603$	$434$	$0.104$	$[-0.257,\ 0.466]$
4	$1{,}049$	$608$	$441$	$0.055$	$[-0.319,\ 0.428]$
5	$1{,}034$	$624$	$410$	$-0.163$	$[-0.567,\ 0.241]$
6	$920$	$548$	$372$	$0.098$	$[-0.265,\ 0.461]$

Appendix

Table 5: Weekly randomized contrasts in HeartSteps. Confidence intervals use participant-clustered standard errors.

Figure 8: Studentized local inference in HeartSteps. Quantiles of the studentized all-observation estimator against standard normal quantiles for a locally stable three-day window and a fourteen-day window with larger temporal drift. The three-day estimator closely follows the standard normal reference, while the fourteen-day distribution is shifted by the accumulated temporal bias.

Non-Stationary Bandits

Non-Stationary Bandits study sequential choices when rewards or constraints change over time, requiring learners to balance exploration with adaptation.

See all 39 papers

May 1, 2026

Trading off rewards and errors in multi-armed bandits

In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives. We provide both upper and lower bounds and validate empirically.

Akram Erraqabi, Alessandro Lazaric, Michal Valko +2

Inria SequeL · CMU · EnLearn

Multi-Armed Bandits Exploration-Exploitation Tradeoff Best-Arm Identification Regret Minimization Bandit Learning

Ask PDF

Aug 2, 2026

Sharp Characterization of Bias in Post-Bandit Inference

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.

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 Bandit Learning

Ask PDF

May 30, 2026

Bandit Simulation for Average Reward Inference

Multi-arm bandit algorithms are increasingly used in online platforms, clinical trials, and social science experiments, but valid statistical inference on their performance remains an open challenge. After deploying bandits, a natural question is whether one can construct a confidence interval for its mean reward and assess whether it reliably outperforms a baseline policy. The total reward achieved in any single bandit deployment is random, and deploying a bandit twice on the same population typically yields different reward trajectories due to stochastic rewards. Standard statistical inference methods cannot be used because bandit algorithms introduce complex dependencies in the collected data, which violate the i.i.d. assumption underlying many classical approaches. Moreover, existing inference methods for adaptively collected data only apply to estimands that do not depend on the data-collection algorithm (such as the mean reward under a fixed action). We propose Bandit Simulation for Inference (BSI), a framework that fits a simulator of the bandit environment from observed data--either on-policy or off-policy--and uses it to estimate the mean reward under any evaluation policy, including adaptive blackbox algorithms. BSI formally propagates uncertainty in the estimated simulator parameters into the confidence interval construction. Furthermore, for BSI to be valid, it requires only weak exploration assumptions on the behavior policy and avoids importance weighting. We prove that BSI yields asymptotically valid confidence intervals, and demonstrate empirically that it maintains nominal coverage in settings where standard off-policy evaluation methods fail.

Samya Praharaj, Chih-Yu Chang, Koulik Khamaru +1

Rutgers University · Imperial College London

Multi-Armed Bandits Simulation-Based Inference Off-Policy Evaluation

Ask PDF

Abstract

Non-Stationary Bandits

Explore similar work

Trading off rewards and errors in multi-armed bandits

Sharp Characterization of Bias in Post-Bandit Inference

Bandit Simulation for Average Reward Inference