知识卡片：漂移均值多臂老虎机中的最佳臂识别

一句话结论

论文提出“漂移均值”（Shifting Means）这一新的对抗性扰动模型：仅假设各臂奖励的差值稳定、共同偏移可被对抗性设定，并给出在该模型下可用的最佳臂识别算法 $\mathsf{ISM}$ 及样本复杂度上下界。

事件概述或研究问题

• 研究问题：固定置信度（fixed confidence）设定下的最佳臂识别（Best Arm Identification）。
• 经典设定假设 $K$ 个臂的平均奖励随时间稳定；本文引入“Shifting Means”：只有臂间均值差 $\boldsymbol{\Delta}$ 保持稳定，而所有均值的共同偏移量可在每一轮被对抗性地决定。
• 目标：以高概率识别最佳臂，同时最小化样本复杂度。

方法/产品要点

• 负面结果：作者证明采用广义似然比检验（GLRT）停止规则的算法（包括流行的 Track-and-Stop）在时变漂移下会失败。
• 提出方法：$\mathsf{ISM}$（Importance Weights for Shifting Means，漂移均值的重要性权重）。
• 假设条件：均值有界（不超过 $U$），奖励为 $\sigma^2$-亚高斯（sub-Gaussian）。

主要结果或产业意义

• 正确性：$\mathsf{ISM}$ 满足 $\delta$-correct（即以至少 $1-\delta$ 概率返回最佳臂）。
• 样本复杂度上界：量级为 $K (\sigma^2 + U^2) \Delta_{\min}^{-2} \ln \frac{1}{\delta}$。
• 下界：给出与之匹配（至常数因子）的最坏情况下界。
• 文中还进行了实证评估（具体实验细节待核实）。

为什么重要

• 指出现有主流停止准则（GLRT 类，含 Track-and-Stop）在奖励分布随时间漂移时会失效，提示在非平稳环境下需要重新设计算法。
• 将非平稳性从“奖励均值独立变化”推广到“仅差值稳定、共同偏移对抗可控”的更弱假设，为最佳臂识别提供了新的理论边界。
• 在参考的既有卡片脉络中，本条属于基础模型/学习理论方向的理论进展，与 CompactionRL 等应用型条目无直接事实重叠。

局限与不确定性

• 仅覆盖固定置信度设定；固定预算等其他设定下的表现待核实。
• 结论依赖均值有界与亚高斯假设，实际数据是否满足待核实。
• 摘要称进行了实证评估，但具体实验设置、数据集与对比结果待核实。
• 下界为最坏情况、且仅匹配至常数因子，紧致性程度待核实。

可用于图书/PPT/简报的角度

• 作为“非平稳环境下的序贯决策”案例：经典算法为何在漂移下失效。
• 讲解“稳定性假设的弱化”：从均值稳定 → 仅差值稳定。
• 样本复杂度的上下界匹配：理论最优性直觉。
• 对抗性扰动建模的另一种形式：共同偏移 vs. 逐臂独立扰动。

原始材料

• 标题：Best Arm Identification for Bandits with Shifting Means
• 作者：Lukas Zierahn, Wouter M. Koolen, Shubhada Agrawal, Christina Katsimerou, Dirk van der Hoeven
• 发布：2026-10-07（arXiv:2610.10488v1），主分类 stat.ML；分类 stat.ML, cs.LG
• 关键词：Best Arm Identification, Shifting Means, GLRT, Track-and-Stop, Importance Weights for Shifting Means ($\mathsf{ISM}$), Sample Complexity, Fixed Confidence
• Abstract URL: https://arxiv.org/abs/2610.10488v1
• PDF URL: https://arxiv.org/pdf/2610.10488v1