重新审视Successive Rejects算法：优化阶段调度提升最佳臂识别效率

在最佳臂识别（Best-Arm Identification, BAI）问题中，算法通过自适应地选择臂来寻找平均奖励最大的臂。Successive Rejects（SR）作为一种简单且经典的固定预算最佳臂识别算法，每轮淘汰一个候选臂，长期以来被视为有限自适应性的代表——毕竟它的各阶段长度是预先设定的。然而，一篇最新研究对SR算法进行了重新思考与扩展，通过优化其阶段调度，显著提升了算法性能。

SR算法为何如此具有竞争力？

Successive Rejects算法的核心机制相当简洁：将总预算划分为若干阶段，每个阶段结束后淘汰当前表现最差的候选臂，直至只剩下一个臂。这种"逐轮淘汰"的策略看似机械，却在实际表现中出人意料地强劲。

研究指出，对于具有共同方差的高斯臂，SR在最差情况下的误差指数（以流行的复杂度度量H₁(P)归一化后）在常数因子范围内已经达到最优。这一理论性质部分解释了为什么SR能够与当前最先进的自适应采样算法相竞争，甚至在许多场景中不落下风。

换句话说，SR的"非自适应"标签具有误导性——它的预设调度本身已经隐含了某种最优结构，只是这种最优性此前未被充分利用和发挥。

**误差指数（Error Exponent）**是衡量最佳臂识别算法性能的核心指标。在大偏差理论框架下，当总预算趋于无穷时，算法犯错概率以指数速率衰减，该衰减速率即为误差指数。误差指数越大，算法在相同预算下犯错概率越低。对于固定预算BAI问题，误差指数通常与一个复杂度度量成反比，该度量取决于各臂之间的奖励差距：差距越小，识别难度越大，复杂度越高。

H₁(P)复杂度度量是其中一种经典的归一化基准，其形式为各次优臂与最优臂之间差距倒数平方的加权求和。研究者常以误差指数与该度量的乘积（即归一化误差指数）作为评价标准，因为该乘积的上界刻画了所有算法所能达到的最优速率。若某算法的归一化误差指数在常数因子范围内接近上界，则称其在该意义下近似最优。SR算法之所以具有竞争力，正是因为其预设调度恰好使归一化误差指数在常数因子内达到上界。

将阶段调度设计转化为优化问题

既然SR的预设阶段长度并非最优，那么能否通过数学优化来改进它？这正是该研究的核心贡献。

作者将阶段调度设计形式化为一个针对归一化误差指数的优化问题。通过求解该问题，他们提出了一种新的SR变体——H₁-Balanced Successive Rejects（简称H₁-SR）。这一优化后的调度在具有确定性等计数计划的SR类算法中是最优的。

这意味着，在所有遵循"等计数淘汰"框架的算法中，H₁-SR的阶段安排已经达到了理论上的最佳，无法在该约束条件下进一步改进。

共同方差高斯臂模型是BAI理论分析中的标准设定：每个臂的奖励服从方差相同、均值未知的高斯分布，算法通过采样获得带噪观测以推断哪个臂均值最大。共同方差假设简化了分析，使误差指数仅依赖于均值差距，而不受各臂方差差异的干扰。

确定性等计数计划指在SR类算法中，每个阶段采样各候选臂的次数是预先确定且相等的。这一约束保证了算法在固定预算下对每个候选臂的采样量均衡，便于理论分析，同时使阶段长度成为唯一可优化的自由度。在该约束下，阶段长度的选择直接决定了各臂被淘汰的时机，进而影响误差指数。研究正是针对这一自由度进行优化，从而在等计数框架内找到了最优调度。

H₁-SR的理论保证：逼近最优自适应算法

H₁-SR最引人注目的贡献在于其理论保证。对于共同方差的高斯臂，该算法在所有自适应算法中至少能达到最优归一化速率的11/12，且这一比例对任意K≥2成立。

更具深远意义的是，当候选臂数量K趋于无穷时，该近似比以1-O(1/log K)的速度收敛至1。换言之，随着问题规模增大，H₁-SR几乎可以达到完全自适应算法的最优性能。

作为对比，原始SR算法对应的最优归一化速率比例收敛到仅1/4。从1/4到接近1的跃升，说明阶段调度的优化并非微调，而是根本性的改进。

近似比（Approximation Ratio）是衡量算法性能相对于理论最优算法差距的常用指标。在BAI中，若将某算法的归一化误差指数与所有自适应算法所能达到的最优值之比定义为近似比，则该比值越接近1，说明算法越接近完全自适应。H₁-SR的近似比为11/12（约0.917），意味着其误差指数至少达到最优值的91.7%。

收敛速率 1-O(1/log K) 描述了近似比随候选臂数量K增大的渐近行为。当K趋于无穷时，1/log K趋于0，因此近似比趋近于1，即H₁-SR在大规模问题上几乎不损失任何性能。相比之下，原始SR的近似比仅收敛到1/4，说明其误差指数最多只有最优值的四分之一。这一显著差距表明，阶段调度的优化不仅提升了常数因子，更从根本上改变了算法的渐近效率。

实验验证：显著增益与代价揭露

研究在十个合成实例和两个基于数据集的高斯基准上进行了实验，将优化调度与原始SR在有限时间范围内进行对比。

实验结果展示了两个关键发现：一方面，在多数测试实例上，优化调度带来了实质性性能提升，验证了理论分析的预测；另一方面，实验也揭示了一个值得警惕的机制——在某些问题环境下，过于激进的早期淘汰策略反而会带来更高的代价。

这一发现提醒实践者，优化阶段调度虽然前景可观，但并非"越早淘汰越好"，需要根据具体问题结构进行权衡。

合成实例与基于数据集的高斯基准是BAI实验评估的两类典型测试环境。合成实例通过人工设定各臂的均值与方差来精确控制问题难度，便于验证理论预测；基于数据集的高斯基准则从真实数据中估计各臂的奖励分布，更贴近实际应用场景。两者结合既能检验算法在理想化条件下的表现，也能评估其在真实数据分布下的鲁棒性。

有限时间范围指总预算固定且有限的实验设定，这与渐近理论分析不同——理论关注预算趋于无穷时的极限性能，而实际应用往往受限于有限的采样次数。在有限预算下，算法的常数因子和早期决策质量变得至关重要，因此优化调度带来的增益可能比渐近分析所预示的更为显著，也可能因早期淘汰过于激进而付出额外代价。

对最佳臂识别领域的启示

这项工作为SR类算法正名：看似缺乏自适应的预设调度，经过精心优化后，可以在理论上逼近完全自适应算法的最优性能。这一结论挑战了"自适应优于非自适应"的简单认知，也为固定预算最佳臂识别算法的设计提供了新思路。

对于实际应用而言，H₁-SR的计算开销几乎与原始SR相当，却能在理论保证和实验表现上实现显著提升。这种"低复杂度、高回报"的特性，使其在需要快速决策的场景中具有实用价值。