aiqbench analysis
This research addresses the fundamental tradeoff in adaptive experiments between maximizing cumulative rewards and maintaining precise, real-time inference on current treatment effects. The authors introduce TRACE, an algorithm that achieves matching minimax bounds for this conflict while adapting exploration to prediction errors without sacrificing worst-case guarantees. For practitioners deploying bandit systems where immediate effect estimation is critical, this work clarifies the unavoidable cost of refreshing confidence intervals in nonstationary environments.
The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits
arXiv:2610.29982v1 Announce Type: cross 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\"older-smooth mean rewards of exponent $\beta\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}_{\beta}\left(\sqrt{KT}+K^{\beta/(2\beta+1)}L^{1/(2\beta+1)}T^{(\beta+1)/(2\beta+1)}+Kw^{-2}(1+L^{1/\beta}w^{-1/\beta})\right)$, where the notation hides logarithms and constants depending only on $\beta$. 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.
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 $\beta\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}_{\beta}\left(\sqrt{KT}+K^{\beta/(2\beta+1)}L^{1/(2\beta+1)}T^{(\beta+1)/(2\beta+1)}+Kw^{-2}(1+L^{1/\beta}w^{-1/\beta})\right)$, where the notation hides logarithms and constants depending only on $\beta$. 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.
Machine Learning (stat.ML); Machine Learning (cs.LG)
arXiv:2610.29982 [stat.ML]
(or arXiv:2610.29982v1 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2610.29982 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 318 words