Newest papers

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

Sharan Sahu, Martin T. Wells · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.29982 · cited by 0 works (OpenAlex) · open-access PDF

Spanish

Este error de separación es el uso de algoritmos de extracción de errores para favorecer intervenciones con recompensas más altas esperadas. Sin embargo, los tomadores de decisiones también requieren inferencias fiables sobre los efectos actuales del tratamiento: las diferencias entre la intervención y las recompensas medias del brazo de referencia en el momento actual, en lugar de las medias locales históricas. Estos conflictos de objetivos: la maximización de recompensas favorecen mejores intervenciones, mientras que la inferencia del efecto de corriente requiere una exploración continua de los efectos potencialmente suboptimales a medida que los resultados cambian a lo largo del tiempo. Caracterizamos este tradeoff para los bandidos del brazo de referencia y del brazo de referencia con recompensas medias de Hölder-smooth en el momento actual. Estas recompensas medias de costes locales

Machine translation (Meta M2M100); the English original follows.

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.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Regret, Logarithm, Inference, Smoothness, Constant (computer programming), Mathematics

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange