强污染对抗线性老虎机实现近极小化极大最优遗憾界

研究者提出 CRW-FTRL 算法，解决了强污染对抗线性老虎机此前未决的统计最优速率问题。该算法采用半径加权熵正则化与归一化核估计，在 $d$ 维 $K$ 动作空间高概率取得 $\tilde O(\sqrt{dT\log K} + dC)$ 遗憾界。用于紧凑动作集离散化可达 $\tilde O(d\sqrt{T} + dC)$ 遗憾界，在对数因子内匹配无污染速率与 $\Omega(dC)$ 下界。