多臂老虎机同时实现一阶与最优遗憾保证研究
原文：Achieving Minimax-Optimal First-Order and Best-of-Both-Worlds Regret Simultaneously in Multi-Armed Bandits
我们研究多臂老虎机中的一阶遗憾和两全其美遗憾保证。Pogodin 和 Lattimore（2019）提出了一种算法，将极小极大最优最坏情况遗憾与一阶保证相结合，其损失相关项为 $\mathcal{O}(\sqrt{K L^\star}\log T)$，其中 $T$ 表示时间跨度，$L^\star$ 表示固定臂中最小的期望累积损失，$K$ 表示臂数。然而，该损失相关项与最优一阶尺度之间仍存在对数差距。在本文中，我们通过提出一种高效且无参数的算法消除了该对数因子，实现了极小极大最优一阶遗憾保证 $\mathcal{O}(\sqrt{K L^\star})$。在技术上，我们的算法基于带有 Tsallis 熵正则化器的 FTRL（Zimmert 和 Seldin，2021），其学习率根据学习器的累积损失自适应调整，采样分布由标量不动点确定。该构造以学习器的损失来控制组合的估计成本和稳定性成本。此外，我们证明同一算法实现了两全其美保证，对于具有唯一最佳臂 $i^\star$ 的独立同分布损失，遗憾为 $\mathcal{O}(\sum_{i\ne i^\star}\frac{\log T}{\Delta_i})$，其中 $\Delta_i$ 表示臂 $i$ 的次优性差距。作者：Mengxiao Zhang 类别：cs.LG