带反馈图多臂老虎机的近最优一阶遗憾界

针对带反馈图的对抗性多臂老虎机，该研究提出了达到 $\widetilde{O}(\sqrt{\alpha L^\star}+\alpha)$ 期望遗憾界的新算法，弥合了一阶界与最坏情况界在图独立数 $\alpha$ 上的差距。算法将 EXP3 与优化探索采样相结合，其不动点分布可在多项式时间内通过几何收敛迭代求解。该成果通过两层聚合机制扩展至一般强可观测图，同样具备该近最优保证。