通过正则化稳定探索算法，实现可验证的统计推断与精确后悔界。
Stabilizing Bandits using Regularization: Precise Regret and A Quantitative Central Limit Theorem
- 基于在线算法迭代设计更精细的稳定性条件
- 给出非渐近的Berry--Esseen界与匹配的后悔上下界
- 证明正则化是实现有效推断的必要代价
自适应采样使经典渐近理论中的独立性假设失效，导致带域数据的统计推断面临根本挑战。近期研究指出稳定性是自适应下有效推断的充分条件。本文首次提出以在线算法迭代为表述的精细化稳定性条件，并证明一大类正则化随机镜面下降算法满足该条件。由此可强化Lai--Wei（1982）的渐近结果：第一，导出自适应采样下经验收益估计的非渐近Berry--Esseen界；第二，得到所提算法后悔率的匹配非渐近上下界，实现精确刻画；第三，证明这些正则化算法在特定对抗污染水平下仍保持渐近正态性与有效推断；第四，表明正则化并非偶然，而是必要：Lai--Wei稳定性与最优$O(\sqrt{T})$后悔率不兼容——后者由无正则化算法（如EXP3）实现，因此有效推断需付出可控的多项式对数级后悔膨胀代价。
原文摘要 · Abstract (English)
Statistical inference with bandit data presents fundamental challenges owing to adaptive sampling, which violates the independence assumptions underlying classical asymptotic theory. Recent work has identified stability~\citep{laiwei82} as a sufficient condition for valid inference under adaptivity. This paper first provides a refined stability condition, stated in terms of the iterates of an online algorithm, and shows that a large class of regularized stochastic-mirror-descent-style algorithms satisfy it. This refined condition allows us to strengthen the asymptotic results of~\citet{laiwei82} in several ways. First, we derive a non-asymptotic Berry--Esseen bound for the empirical reward estimates under adaptive sampling. Second, we derive matching non-asymptotic upper and lower bounds on the regret of the proposed algorithm, yielding a precise characterization of its regret. Third, we show that these regularized algorithms preserve asymptotic normality and valid inference under a prescribed level of adversarial corruption. Finally, we show that regularization is necessary rather than incidental: Lai--Wei stability is incompatible with the optimal $O(\sqrt{T})$ regret rate -- the rate attained by unregularized algorithms such as EXP3 -- so that a controlled, polylogarithmic inflation in regret is the price of valid inference.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。