Best Arm Identification for Bandits with Shifting Means¶

会议: NeurIPS 2026
arXiv: 2610.10488
代码: https://github.com/LukasZierahn/Shifting-Means-Experiments
领域: 优化/理论
关键词: 多臂老虎机、最佳臂识别、Shifting Means、重要性加权、广义似然比检验失效

一句话总结¶

针对均值差固定但基准均值面临未观测对抗性共模漂移的非平稳赌博机，本文揭示经典广义似然比检验与 Track-and-Stop 算法的失效机理，提出具备 $\delta$-正确性与渐近最优样本复杂度的新算法 ISM。

研究背景与动机¶

在序贯决策与自适应实验（如数字营销、A/B/n 测试以及在线推荐系统）中，固定置信度下的最佳臂识别（Best Arm Identification, BAI）是一项基础任务：算法需要在最小化采样步数的同时，以不低于 $1-\delta$ 的预设概率准确推断出期望奖励最高的动作。经典 BAI 理论均建立在环境平稳且独立同分布（i.i.d.）的核心假设之上，由此诞生的渐近最优算法（如著名学者 Garivier 与 Kaufmann 提出的 Track-and-Stop 框架及其广义似然比检验 GLRT 停止准则）被广泛应用。然而在工业级真实场景中，数据分布往往不可避免地面临宏观波动与非平稳扰动——例如电商平台的周期性周末效应、季节性流量滑坡或全站层面的系统级波动。

大量跨领域实证研究表明，此类宏观扰动往往具有显著的「共模」特征：它对所有候选臂的绝对回报产生方向一致且幅度相同的全局抬升或压低，但不同动作之间的本质质量差异（即 pairwise gaps）在相当长的时间窗口内保持相对恒定。面对这种未建模的全局漂移，如果直接运行传统的平稳算法，由于未观测漂移会严重抬高边缘观测方差，算法设定的置信阈值将被过早击穿，引发灾难性的识别错误；若试图在似然比检验中为每个时间步的漂移量单独估计参数，又会因参数量与数据量同阶增长而导致严重过拟合，使得检验统计量恒为零、算法陷入永不停止的僵局。

为了建立针对此类全局趋势扰动的理论鲁棒性，本文形式化提出了「漂移均值」（Shifting Means）这一介于完全随机与完全对抗之间的新设定：在每一轮中，未观测的潜在漂移 $B_t$ 可以任意甚至对抗性地变化，但各臂均值与漂移的相对差值 $\Delta_a$ 恒定不变，从而保证全局最优臂在整个实验周期中始终唯一且确定。本文的核心 idea 是：抛弃对非平稳绝对均值及潜在漂移轨迹的脆弱似然估计，转而设计一种基于指数超鞅构造的重要性加权证据测度（ISM），通过极小化极大化逐轮漂移与自适应在线探索，在对抗性漂移下同时实现严谨的 $\delta$-正确性与阶数匹配的样本复杂度。

方法详解¶

整体框架¶

在 $K$ 臂 Shifting Means 设定下，每一轮 $t \ge 1$，智能体根据历史交互采样臂 $A_t \in [K]$（采样概率记为 $w_{t,A_t}$），环境生成潜在奖励向量 $\boldsymbol{X}_t$ 与隐变量漂移 $B_t$。各臂条件期望满足 $\mu_{t,a} = B_t - \Delta_a$（其中最优臂 $a^* = \arg\min_a \Delta_a$，即 $\Delta_{a^*} = 0$ 且差距向量 $\boldsymbol{\Delta} \in [0, 2U]^K$ 保持不变），且噪声为条件 $\sigma^2$-亚高斯。

针对经典 GLRT 停止规则在该设定下统计量恒为零或方差膨胀失效的问题，ISM（Importance Weights for Shifting Means）算法建立了全新的序贯检验流程：首先通过无偏重要性加权估计量实时追踪各臂之间的相对间距 $\hat{\Delta}_{t,a,b}$；接着利用凸优化求解使得最小证据漂移最大的最优采样比例 $\tilde{\boldsymbol{w}}_t$；随后混入衰减的探索因子得到行动概率 $\boldsymbol{w}_t$；在观测到当前奖励 $X_t$ 后，仅对包含选中臂 $A_t$ 的臂对更新成对累积证据统计量 $Z_{t,a,b}$；当某一候选臂相对于其他所有竞争对手的累积证据均突破由目标置信度 $\delta$ 决定的安全阈值 $\ln((K-1)/\delta)$ 时触发停机，并向用户推荐该最优臂。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入参数：置信度 δ、均值界限 U、方差代理 σ²"] --> B["估计差距投影与凸优化求解<br/>求解 D*(Δ̂_t-1 ∧ 2U) 获取最优基准权重 w̃_t"]
    B --> C["混入强制探索机制<br/>w_t = (1 - 1/√t) w̃_t + 1_K / (K√t)"]
    C --> D["动作采样与环境交互<br/>依 w_t 抽取动作 A_t，观测奖励 X_t"]
    D --> E["超鞅证据统计量更新<br/>优化参数 (λ, α, β)，仅更新含 A_t 的重要性证据 Z_t 与间距估计"]
    E -->|未达到停止阈值| B
    E -->|max_a min_b Z_t,a,b ≥ ln(K-1/δ)| F["停机并推荐最优臂 ã"]

关键设计¶

1. 基于指数超鞅的重要性加权证据测度：解决未观测对抗漂移下的有效假设检验

经典最佳臂识别依赖于似然比检验（GLRT），但在 Shifting Means 设定下，由于漂移 $B_t$ 每轮未知且对抗变化，若在似然函数中联合估计 $B_t$，分母与分子将在每个时间步将绝对均值直接拟合到观测数据 $X_t$，导致 GLRT 统计量 $Z^{\text{GLRT}}_{a,b}(t)$ 恒等于 0，算法完全失去停机能力。为此，ISM 放弃了对似然函数的依赖，为每个有序臂对 $a \neq b$ 构造了关于假说 $\Delta_{a,b} \le 0$（即 $b$ 优于 $a$）的重要性加权逐轮证据测度： $$ z_{t,a,b} \coloneq \frac{\mathbb{I}{t,a}}{w}}\big(\lambda_{t,a,b} X_t - \alpha_{t,a,b}\big) + \frac{\mathbb{I{t,b}}{w\big) $$ 为了保证当备择假设成立（真实最优臂为 }}\big(-\lambda_{t,a,b} X_t - \beta_{t,a,b$b$）时累积证据不会异常发散，本文通过函数 $\Phi(w_a, w_b, \lambda, \alpha, \beta)$ 刻画了最坏环境下的最大指数矩。通过施加安全约束 $\Phi \le 1$，使得随机过程 $(\exp(Z_{t,a,b}))_{t \ge 0}$ 在任何满足条件的赌博机实例下都是一个期望非增的超鞅（Supermartingale），进而结合 Ville 最大值鞅不等式与联合界，数学上严格证明了当停机阈值设为 $\ln\frac{K-1}{\delta}$ 时，推荐错误臂的概率严格受控在 $\delta$ 以内。

2. 极小化极大漂移优化与参数解析解：最大化证据增长速率

为了使算法在保证安全性的同时样本复杂度达到最小，累积证据 $Z_{t,a,b}$ 在真实臂 $a^*$ 下的期望漂移应当尽可能快速增长。算法将逐轮期望增量表示为 $\mathbb{E}_t[z_{t,a,b}] = \lambda_{t,a,b} \Delta_{a,b} - \alpha_{t,a,b} - \beta_{t,a,b}$，并在安全约束 $\Phi \le 1$ 下对乘子 $\lambda \ge 0$ 及偏移项 $\alpha, \beta$ 进行最优化求解。由于指数矩在边界 $u \in \{-U, U\}$ 处取到极值，约束条件在最优解处双侧同时饱和，本文巧妙推导出了参数 $\alpha^*$ 与 $\beta^*$ 针对任意给定 $\lambda$ 的双曲正弦闭式解析表达式： $$ \alpha^*(w_a, w_b, \lambda) \coloneq \frac{\lambda^2 \sigma^2}{2 w_a} - w_a \ln \frac{(w_a + w_b)\sinh(U\lambda / w_b)}{w_a \sinh(U\lambda(1/w_a + 1/w_b))} $$ 将双参数解析解代回后，将复杂的多元非线性约束优化精简为单变量标量优化问题 $D(w_a, w_b, \Delta)$。通过建立极大极小博弈框架 $D^*(\boldsymbol{\Delta}) \coloneq \max_{\boldsymbol{w} \in \triangle_K} \min_{b \neq a^*} D(w_{a^*}, w_b, \Delta_b)$，算法通过三重嵌套二分查找在每一轮以 $O(K)$ 的低算力开销精确求解各臂均衡漂移与全局最优采样配比。

3. 插件式差距估计与受控探索调度：克服未知环境下的信息滞后

在非预言机（未知真空间隙 $\boldsymbol{\Delta}$）的现实设定中，直接使用经验均值将因宏观漂移 $B_t$ 的混淆而失效。ISM 采用无偏重要性加权累积估计量： $$ \hat{\Delta}{t,a,b} \coloneq \frac{1}{t}\sum}^t \left(\frac{\mathbb{I{s,a}}{w}} - \frac{\mathbb{I{s,b}}{w\right) X_s $$ 并将估计值投影截断在物理合法范围 }$[0, 2U]$ 内以保证参数有界性。为了防止早期因估计误差产生欺骗性极值、进而导致某一臂被永久停止采样，ISM 设计了随时间衰减的强制探索调度机制：$w_{t} = (1 - t^{-1/2})\tilde{\boldsymbol{w}}_t + t^{-1/2}\mathbf{1}_K / K$。这种 $O(1/\sqrt{t})$ 的探索速率不仅为每个动作提供了至少 $(K\sqrt{t})^{-1}$ 的采样下界，还完美匹配了 Bernstein 型鞅集中不等式对经验间距误差的收敛控制要求，使得经验漂移在渐近意义下以极高概率无损逼近真实环境的最优漂移率 $D^*(\boldsymbol{\Delta})$。

4. 升余弦极值先验与最优样本复杂度匹配：确立漂移干扰下的理论极限

为了探究在 Shifting Means 设定下任何 $\delta$-正确算法所必须付出的样本代价，本文利用信息论中位置族分布的 Fisher 信息极值理论设计了最难对抗环境。若漂移取确定性序列，对抗者可直接选择 $B_t = \Delta_{A_t}$ 抹除所有各臂均值差异；而若漂移为随机分布，其对各臂观测似然比的稀释效应取决于卷积密度的 Fisher 信息量。本文在有界支撑集 $[-R, R]$ 上引入具有极小 Fisher 信息的升余弦分布（Raised Cosine Distribution）： $$ p(B') = \frac{1}{R} \cos^2\left(\frac{\pi B'}{2R}\right), \quad |B'| \le R $$ 该分布达到了单区间有界支撑集上的最小 Fisher 信息 $\pi^2 / R^2$。基于此构造，将单个观测的 KL 散度有效界定为 $\mathrm{KL} \le \Delta^2 / [2(\sigma^2 + R^2/\pi^2)]$，推导出任意正确算法所必须满足的样本复杂度下界 $\Omega\left((\sigma^2 + U^2/\pi^2) \sum_a \Delta_a^{-2} \ln(1/\delta)\right)$。结合 ISM 建立的上界 $4(\sigma^2 + U^2)(\Delta_{b^*}^{-2} + \sum_{a \neq a^*} \Delta_a^{-2}) \ln(1/\delta)$，证明了 ISM 在最坏情况下仅存在至多 $2\pi^2 \approx 20$ 倍常数差距，不仅涵盖经典平稳 BAI 的已知最优阶数，而且在理论上严格闭合了带漂移均值问题的样本复杂度阶数。

实验关键数据¶

主实验¶

实验在 $K=4$ 臂的标准基准设定下进行，其真实的间距向量为 $\vec{\Delta} = [0.0, 0.05, 0.07, 0.1]$，对应经典平稳文献中的伯努利均值配置 $\vec{\mu} = [0.5, 0.45, 0.43, 0.4]$，设置方差代理 $\sigma^2 = 1/4$。对抗漂移 $B_t$ 每轮独立从均匀分布 $\mathcal{U}[0.1, 1.0]$ 中抽取，已知均值界限设为 $U=1$。计算得到理论最优漂移为 $D^* = 1/4965.74$，理论最优采样权重为 $\vec{w}^* = [0.4168, 0.3896, 0.1363, 0.0572]$。实验统计 1000 次独立运行下的经验停机步数与各理论预测值的对比：

错误率 $\delta$	理论下限 $\frac{1}{D^*}\ln\frac{1}{\delta}$	经典预言机界 $\frac{1}{D^*}\ln\frac{K-1}{\delta}$	Lemma 3 亚高斯界	经验实际停机步数（95% 置信区间）	经验超额样本比例
$10^{-1}$	11,434	16,889	69,702	[28,085, 29,470]	[145.62%, 157.74%]
$10^{-10}$	114,340	119,796	211,870	[140,868, 143,920]	[23.20%, 25.87%]
$10^{-100}$	1,143,403	1,148,858	1,384,182	[1,199,222, 1,207,930]	[4.88%, 5.64%]

超参数错误指定与鲁棒性消融¶

在 $\delta = 1/10$ 的固定置信度下，针对先验均值界限 $U$ 的设定进行错误指定（Misspecification）鲁棒性实验。实际漂移分布要求 $U \ge 1$，实验测试了当输入先验参数 $U$ 严重低于理论真实值时的算法表现（1000 次蒙特卡洛独立重复）：

设定参数 $U$	理论状态	错误识别最佳臂次数（/1000）	实测错误率	经验平均停机步数
$U = 1$	理论完全正确指定	0	0.00%	28,777
$U = 1/2$	严重欠估计（错误指定）	0	0.00%	20,412
$U = 1/4$	极度欠估计（极度保守违反）	4	0.40%	15,180

关键发现¶

渐近收敛严密吻合：随着目标置信度 $\delta$ 趋于 $0$（从 $10^{-1}$ 降至 $10^{-100}$），实际经验采样量与渐近下界 $\frac{1}{D^*}\ln\frac{1}{\delta}$ 之间的超额偏差从 150% 迅速收缩至 5% 左右，完全验证了 Theorem 4 中 $\lim_{\delta \to 0} \mathbb{E}[\tau] / \ln(1/\delta) \le 1/D^*(\boldsymbol{\Delta})$ 的渐近紧致性。
均值范围参数 $U$ 具备宽裕的经验容错性：即使将 $U$ 设为仅有真实值四分之一的 $1/4$，在 1000 次严酷的对抗漂移测试中也仅仅出现了 4 次错误识别（错误率仅 0.4%，远低于名义容忍度 $\delta = 10\%$），表明算法在工程实践中对参数微小失准具有强大的韧性。
与经典平稳算法代价对比：在无漂移的理想环境下，经典 TAS 算法在 $\delta = 0.1$ 下平均耗时约 4000 步，而 ISM 耗时约 28,000 步；这 7 倍左右的额外采样开销正是为了抵御任意宏观对抗漂移、确保统计有效性所必须支付的理论“信息保险费”。

亮点与洞察¶

将 e-变量理论与主动控制动作有机融合：不仅将被测原假设推广至复杂的非凸复合假设，还通过把算法自身主动采样的随机概率权重 $w_{t,a}$ 作为重要性除数，创造性地平衡了对抗非平稳漂移与统计置信度累积。
基于升余弦分布的极值下界构造：突破了传统仅用高斯噪声建立下界的思维定式，将信息论中的 Fisher 信息量极小化理论（Poincaré / 变分极值构造）引入赌博机下界证明，极具数学美感且具备向其他非平稳序列决策问题推广的潜力。
仅需 $O(K)$ 算力与 $O(K^2)$ 存储的轻量级工程落地：通过巧妙追踪单臂充分统计量而非保存全部历史观测，每轮仅需更新涉及选中臂的 $2(K-1)$ 个参数，使高深的前沿测度集中理论具备了在微秒级延迟高并发在线系统中部署的可行性。

局限与展望¶

依赖加性同模漂移与固定差距假设：模型严格依赖各动作在每轮遭受的漂移为完全一致的纯加性标量且 pairwise gaps 绝对时间不变，对于多臂存在非均匀乘性扰动或差距本身随时间缓慢扩散演变的情形尚不能覆盖。
先验参数依赖性：算法在严格理论证明上依然要求预先获知条件均值的绝对界限 $U$ 以及亚高斯方差代理 $\sigma^2$ 的有效上界，尚未实现全参数自适应（Fully Parameter-free）。
渐近常数松弛与离散有限样本阶：虽然建立了 $O(K(\sigma^2 + U^2)\Delta_{\min}^{-2} \ln(1/\delta))$ 的最优匹配阶，但上下界之间仍存在至多 $2\pi^2 \approx 20$ 倍的绝对常数差距，有限步下的非渐近精确漂移界仍有理论压缩空间。

评分¶

新颖性: ⭐⭐⭐⭐⭐ [首次形式化 Shifting Means 设定并证明经典 GLRT 失效，提出全新的超鞅重要性加权识别框架]
实验充分度: ⭐⭐⭐⭐☆ [合成测试与鲁棒性消融完备，代码完全开源，若能补充大规模工业真实 A/B 测试基准更佳]
写作质量: ⭐⭐⭐⭐⭐ [数学推导严丝合缝，附录提供了完备的凸分析与经验过程 Bernstein 鞅集中不等式证明]
价值: ⭐⭐⭐⭐⭐ [为存在宏观潮汐、周期振荡和非平稳环境下的在线评测系统提供了坚如磐石的理论正确性保障]

错误率 \(\delta\)	理论下限 \(\frac{1}{D^*}\ln\frac{1}{\delta}\)	经典预言机界 \(\frac{1}{D^*}\ln\frac{K-1}{\delta}\)	Lemma 3 亚高斯界	经验实际停机步数（95% 置信区间）	经验超额样本比例
\(10^{-1}\)	11,434	16,889	69,702	[28,085, 29,470]	[145.62%, 157.74%]
\(10^{-10}\)	114,340	119,796	211,870	[140,868, 143,920]	[23.20%, 25.87%]
\(10^{-100}\)	1,143,403	1,148,858	1,384,182	[1,199,222, 1,207,930]	[4.88%, 5.64%]

设定参数 \(U\)	理论状态	错误识别最佳臂次数（/1000）	实测错误率	经验平均停机步数
\(U = 1\)	理论完全正确指定	0	0.00%	28,777
\(U = 1/2\)	严重欠估计（错误指定）	0	0.00%	20,412
\(U = 1/4\)	极度欠估计（极度保守违反）	4	0.40%	15,180