改进对抗性老虎机的路径长度误差，实现最优二阶路径约束。
Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits
- 复用已有算法，通过更精细分析提升性能
- 达到理论最优的误差上界，含对数因子
- 无需预知路径变化量，适合动态环境
我们研究对抗性K臂老虎机中针对静止损失序列的二阶路径长度后悔。Bubeck等[2019]设计的算法实现了$ ilde{/mathcal{O}}(K+ oot{KQ_{∞,1}})$的后悔界，其中$Q_{∞,1}$为一阶路径长度，但未解决在仅带通带反馈下是否可实现$ ilde{/mathcal{O}}( ext{poly}(K) oot{1+Q_{∞,2}})$后悔界的开放问题。令人意外的是，我们通过更细致的分析证明，使用相同算法即可在已知$Q_{∞,2}$时实现$ ext{O}ig(K ext{log}(KT)+ oot{K ext{log}(KT)(1+Q_{∞,2})}ig)$的期望后悔，该结果在对数因子和加性项内与$Ω( oot{KQ_{∞,2}})$的下界一致。此外，我们通过自适应重启机制移除了对$Q_{∞,2}$的依赖，其路径长度估计器增量始终有界。
原文摘要 · Abstract (English)
We study second-order path-length regret in adversarial $K$-armed bandits against oblivious loss sequences. Bubeck et al. [2019] designed an algorithm that achieves $\widetilde{\mathcal{O}}(K+\sqrt{KQ_{\infty,1}})$ regret, where $Q_{\infty,1}$ is the first-order path length, and left open whether $\widetilde{\mathcal{O}}(\text{poly}(K)\sqrt{1+Q_{\infty,2}})$ regret is achievable under bandit feedback, where $Q_{\infty,2}$ is the second-order path length. Somewhat surprisingly, we resolve this question positively by showing that with a more involved analysis, the exact same algorithm of Bubeck et al. [2019] achieves $\mathcal{O}\left(K\log(KT)+\sqrt{K\log(KT)\bigl(1+Q_{\infty,2}\bigr)}\right)$ expected regret when $Q_{\infty,2}$ is known, where $T$ is the horizon. This matches the $Ω(\sqrt{KQ_{\infty,2}})$ lower bound up to logarithmic factors and additive terms. We further remove the knowledge of $Q_{\infty,2}$ using an adaptive restart scheme whose path-length estimator has uniformly bounded increments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。