发现最优探索算法普遍存在统计不稳定性,挑战了其可靠性。
On Instability of Minimax Optimal Optimism-Based Bandit Algorithms
- 分析基于乐观原则的多种最优算法,揭示其内在不稳定性机制
- 实证显示多类最优算法样本均值不满足渐近正态性
- 提出稳定与最优间可能存在根本矛盾,启发新算法设计
由于多臂老虎机(MAB)算法具有自适应、非独立同分布特性,基于其数据进行统计推断极具挑战。经典现象是:在老虎机采样下,各臂奖励的样本均值可能不满足中心极限定理。Lai和Wei提出的稳定性条件为老虎机问题中渐近正态性的充分且几乎必要准则。尽管著名的上置信界(UCB)算法满足该条件,但其并非极小化最大后悔值(minimax optimal),从而引发疑问:能否同时实现最小最大后悔值与统计稳定性?本文分析了一类基于乐观原则的广泛老虎机算法的稳定性。我们建立了此类算法违反Lai-Wei稳定性准则的一般结构条件。结果表明,包括MOSS、Anytime-MOSS、Vanilla-MOSS、ADA-UCB、OC-UCB、KL-MOSS、KL-UCB++、KL-UCB-SWITCH及Anytime KL-UCB-SWITCH在内的多种广泛使用的极小化最大后悔值算法均不稳定。进一步通过数值模拟验证:在所有这些情况下,样本均值均未表现出渐近正态性。整体而言,我们的发现暗示了稳定性与极小化最大后悔值之间存在根本张力,是否能设计出兼具两者特性的算法,仍是重要开放问题。
原文摘要 · Abstract (English)
Statistical inference from data generated by multi-armed bandit (MAB) algorithms is challenging due to their adaptive, non-i.i.d. nature. A classical manifestation is that sample averages of arm rewards under bandit sampling may fail to satisfy a central limit theorem. Lai and Wei's stability condition provides a sufficient, and essentially necessary criterion, for asymptotic normality in bandit problems. While the celebrated Upper Confidence Bound (UCB) algorithm satisfies this stability condition, it is not minimax optimal, raising the question of whether minimax optimality and statistical stability can be achieved simultaneously. In this paper, we analyze the stability properties of a broad class of bandit algorithms that are based on the optimism principle. We establish general structural conditions under which such algorithms violate the Lai-Wei stability criterion. As a consequence, we show that widely used minimax-optimal UCB-style algorithms, including MOSS, Anytime-MOSS, Vanilla-MOSS, ADA-UCB, OC-UCB, KL-MOSS, KL-UCB++, KL-UCB-SWITCH, and Anytime KL-UCB-SWITCH, are unstable. We further complement our theoretical results with numerical simulations demonstrating that, in all these cases, the sample means fail to exhibit asymptotic normality. Overall, our findings suggest a fundamental tension between stability and minimax optimal regret, raising the question of whether it is possible to design bandit algorithms that achieve both. Understanding whether such simultaneously stable and minimax optimal strategies exist remains an important open direction.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。