具有多个最优臂的多臂老虎机：极小极大遗憾与非自适应性

arXiv:2609.38659v2 公告类型：replace-cross 摘要：我们研究具有多个最优臂的多臂老虎机（MAB）问题，其动机在于许多实际决策问题都存在多个正确答案。对于具有 $K$ 个臂和 $A$ 个最优臂的多臂老虎机，我们首先对已有的子采样算法（De Heide et al., 2021；Zhu and Nowak, 2020）进行了更精确的分析，证明其极小极大遗憾为 $\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big)$，其中 $T$ 是交互总次数，$\tilde O(\cdot)$ 忽略所有常数因子和对数因子；相比此前的 $\tilde{O}(\sqrt{KT/A})$ 遗憾，这一结果有所改进。随后，我们给出了一个相差对数因子的匹配下界，表明所建立的速率几乎达到了极小极大最优。我们进一步表明，要实现近最优遗憾，必须掌握 $A$ 的值，且误差至多为 $\tilde{O}(1)$ 因子；因为对于某个最优臂数量而言达到近最优的算法，在较小的最优臂数量下，其遗憾必然会显著大于最优遗憾。总体而言，我们的结果对整个范围 $1 \leq A \leq K-1$ 内具有 $A$ 个最优臂的 $K$ 臂多臂老虎机，给出了全面的极小极大刻画。