The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits
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 β∈(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 Õβ(√(KT)+Kβ/(2β+1)L1/(2β+1)T(β+1)/(2β+1)+Kw−2(1+L1/βw−1/β)), 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.
Related
- Block Optimism for Nonstationary Bandits with Latent Linear Dynamics
- Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
- Conventional Inference under Nonstationary Heavy Tailed Fractional Processes & Arrays
- Statistical Inference for Continuous Action Bandits
- The Shadow Price of Intelligence: Quality Degradation in LLM Inference as a Supply Chain Problem
BibTeX
@misc{sahu2026price,
title = {{The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits}},
author = {Sharan Sahu and Martin T. Wells},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29982},
eprint = {2610.29982},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29982},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits
AU - Sharan Sahu
AU - Martin T. Wells
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.29982
UR - https://arxiv.org/abs/2610.29982
AB - 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 β∈(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 Õ_β(√(KT)+K^β/(2β+1)L^1/(2β+1)T^(β+1)/(2β+1)+Kw^−2(1+L^1/βw^−1/β)), 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.
ER -