证明了1/2-Tsallis熵FTRL在随机多臂赌博机中收敛速度快，无需最优臂唯一。
Last-Iterate Analyses of FTRL with the 1/2-Tsallis Entropy in Stochastic Bandits
- 用1/2-Tsallis熵正则化改进FTRL算法，提升学习稳定性。
- 采样简单后悔值以O(t⁻¹)速率下降，无需最优臂唯一。
- 理论证明收敛率紧致，适合关注在线学习收敛性的研究者。
在线学习算法的收敛性分析是机器学习理论的核心，其中末次迭代收敛尤为重要，因为它捕捉了学习者的实际决策并描述了学习过程的演化。然而，在多臂赌博机问题中，现有算法分析大多集中于后悔值的阶数，而对末次迭代（简单后悔）收敛速率的研究较少——尤其是广泛研究的追随正则化领导者（FTRL）算法。近期，采用1/2-Tsallis熵正则化器Ψ(p) = -4∑_{i=1}^d √p_i的FTRL算法（即1/2-Tsallis-INF，见arXiv:1807.07623）被证明可实现理想的“双世界优势”（BOBW）性能，并在对抗性和随机环境中表现良好。然而其末次迭代收敛速率尚未被充分研究。本文研究了1/2-Tsallis-INF算法在随机多臂赌博机中的表现，证明其采样简单后悔值以O(t⁻¹)速率衰减，且无需最优臂唯一。在最优臂唯一条件下，进一步证明由Ψ诱导的期望Bregman散度从最优臂的点质量分布到第t次迭代的采样分布以O(t⁻¹/²)速率衰减。在相同唯一性假设下，匹配的下界表明这两个指数均为紧致。
原文摘要 · Abstract (English)
The convergence analysis of online learning algorithms is central to machine learning theory, where the last-iterate convergence is particularly important, as it captures the learner's actual decisions and describes the evolution of the learning process over time. However, in multi-armed bandits, most existing algorithmic analyses mainly focus on the order of regret, while the last-iterate (simple regret) convergence rate remains less explored---especially for the widely studied Follow-the-Regularized-Leader (FTRL) algorithms. Recently, FTRL with the $1/2$-Tsallis entropy regularizer $Ψ(p) = -4\sum_{i=1}^d \sqrt{p_i}$ (the $1/2$-Tsallis-INF algorithm, by arXiv:1807.07623) was shown to achieve the desirable Best-of-Both-Worlds (BOBW) guarantees and perform well in both adversarial and stochastic settings. Nevertheless, its last-iterate convergence rate has not yet been fully studied. This paper studies the $1/2$-Tsallis-INF algorithm in stochastic bandits and shows that its sampling simple regret decays at rate $\mathcal{O}(t^{-1})$, without requiring the optimal arm to be unique. Under a unique optimal arm, we further show that the expected Bregman divergence induced by $Ψ$ between the point mass on the optimal arm and the sampling distribution at iteration $t$ decays at rate $\mathcal{O}(t^{-1/2})$. Matching lower bounds under the same uniqueness condition show that both exponents of $t$ are tight.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。