多臂老虎机新算法同时达到一阶后悔与最优最坏情况后悔界
Achieving Minimax-Optimal First-Order and Best-of-Both-Worlds Regret Simultaneously in Multi-Armed Bandits
把2019年那个带log的遗憾界做到O(√(KL*))，一个算法同时拿下stochastic和adversarial两种场景，做bandit理论的别错过。
论文研究多臂老虎机中的一阶后悔与 best-of-both-worlds 后悔保证。Pogodin 和 Lattimore 在 2019 年提出的算法虽有 minimax 最优最坏情况后悔，但其损失依赖项 O(√(K L*) log T) 与一阶最优尺度之间仍差一个对数因子。本文提出无参数的高效算法，将损失依赖项收紧至最优的 O(√(K L*))。算法基于 FTRL 与 Tsallis 熵正则化器，学习率随累计损失自适应，采样分布由标量不动点决定。同一算法在对立损失下还给出 O(∑ log T / Δ_i) 的 best-of-both-worlds 保证。
Achieving Minimax-Optimal First-Order and Best-of-Both-Worlds Regret Simultaneously in Multi-Armed Bandits
We study first-order and best-of-both-worlds regret guarantees in multi-armed bandits. Pogodin and Lattimore (2019) proposed an algorithm that combines minimax-optimal worst-case regret with a first-order guarantee whose loss-dependent term is $\mathcal{O}(\sqrt{K L^\star}\log T)$, where $T$ denotes the horizon, $L^\star$ denotes the smallest expected cumulative loss among fixed arms, and $K$ denotes the number of arms. However, a logarithmic gap remains between this loss-dependent term and the optimal first-order scale. In this paper, we remove this logarithmic factor by proposing an efficient and parameter-free algorithm that achieves the minimax optimal first-order regret guarantee $\mathcal{O}(\sqrt{K L^\star})$. Technically, our algorithm is built upon FTRL with a Tsallis entropy regularizer (Zimmert and Seldin,2021), with a learning rate adapted to the learner's cumulative loss and a sampling distribution determined by a scalar fixed point. This construction controls the combined estimation and stability cost in terms of the learner's loss. Moreover, we show that the same algorithm achieves a best-of-both-worlds guarantee, with $\mathcal{O}(\sum_{i\ne i^\star}\frac{\log T}{Δ_i})$ regret for i.i.d. losses with a unique best arm $i^\star$, where $Δ_i$ denotes the suboptimality gap of arm $i$.