改进了带方差感知的多臂赌博机算法，揭示其在长期决策中的不稳定性。
Precise Asymptotics and Refined Regret of Variance-Aware UCB
- 引入方差估计优化选择策略，提升决策精度
- 发现算法长期行为可能随机波动而非稳定收敛
- 适用于追求高精度在线决策的研究者
本文研究了多臂赌博机问题中带方差感知的上置信界（UCB-V）算法的行为。相较于经典的UCB算法，UCB-V通过引入方差估计来改进决策过程。我们首次提供了对UCB-V臂选择频率的渐近刻画，拓展了近期关于经典UCB的成果（Kalvit & Zeevi, 2021；Khamaru & Zhang, 2024）。一个关键发现是：与经典UCB不同，UCB-V的臂选择频率在长期可能呈现非确定性波动，表现出潜在的不稳定性。此外，我们还给出了高概率意义下的非渐近界，为后悔分析提供新视角。基于该高概率结果，我们证明了UCB-V可实现此前未知的更精细后悔界，甚至优于一些更复杂的方差感知在线决策算法。
原文摘要 · Abstract (English)
In this paper, we study the behavior of the Upper Confidence Bound-Variance (UCB-V) algorithm for the Multi-Armed Bandit (MAB) problems, a variant of the canonical Upper Confidence Bound (UCB) algorithm that incorporates variance estimates into its decision-making process. More precisely, we provide an asymptotic characterization of the arm-pulling rates for UCB-V, extending recent results for the canonical UCB in Kalvit and Zeevi (2021) and Khamaru and Zhang (2024). In an interesting contrast to the canonical UCB, our analysis reveals that the behavior of UCB-V can exhibit instability, meaning that the arm-pulling rates may not always be asymptotically deterministic. Besides the asymptotic characterization, we also provide non-asymptotic bounds for the arm-pulling rates in the high probability regime, offering insights into the regret analysis. As an application of this high probability result, we establish that UCB-V can achieve a more refined regret bound, previously unknown even for more complicate and advanced variance-aware online decision-making algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。