EL-F算法：无需奖励尺度的可靠Bandit新方案

背景：当Bandit算法不再依赖奖励尺度

在多臂老虎机（Multi-Armed Bandit）问题中，一个长期存在的工程痛点是对奖励尺度和尾部参数的先验知识依赖。实际应用中，奖励分布的量级往往未知，甚至随时间变化，这使得许多理论优雅的算法在部署时表现不稳定。Cowan和Katehakis提出的g-Forcing策略曾给出几乎必然的regret保证，但这类保证只描述"最终会学到什么"，无法回答有限轮次内的期望表现和极端风险。

近期一篇研究论文提出了EL-F算法，通过经验似然（Empirical Likelihood）对g-Forcing进行扩展，试图在保持渐近最优性的同时，给出有限时间的期望regret上界与尾部风险刻画。

多臂老虎机与regret：多臂老虎机（Multi-Armed Bandit, MAB）是序贯决策的经典模型。每一轮，算法从K根臂中选择一根拉动，获得随机奖励；目标是在T轮内最大化累计奖励，等价于最小化regret——即相对于始终拉动最优臂所能获得的期望奖励之差。regret刻画了因探索而付出的代价。伪regret（pseudo-regret）是regret的常见替代量，通常定义为各臂次优性gap与采样次数乘积之和，便于理论分析。

单臂次优性gap：第i根臂的suboptimality gap定义为最优臂期望奖励与第i根臂期望奖励之差，即Δ_i=μ*-μ_i。当Δ_i很小时，区分该臂与最优臂需要更多样本，因此小gap实例通常更难。累计regret可写成∑Δ_i·N_i(T)，其中N_i(T)是第i根臂在T轮内被拉动的次数——这正是"把轮次浪费在次优臂上"的量化表达。

g-Forcing策略：g-Forcing由Cowan和Katehakis提出，核心思想是设定一条非递减、发散且增量趋于零的探索调度g(t)，强制每根臂在第t轮前的采样次数不低于某个由g决定的下界，同时在其余轮次贪心地拉动当前经验均值最高的臂。由于采样下界只依赖轮次t而不依赖奖励的量级或尾部参数，该策略天然具备scale-free（尺度无关）特性。其理论保证是：伪regret满足R(T)=O(g(T))且R(T)/g(T)几乎必然收敛到∑Δ_i，但这是渐近陈述，不回答有限T下的期望表现与极端风险。

三层性能保证：从渐近到有限时间

EL-F的核心贡献在于将性能刻画拆解为三个层次。

渐近最优性保持不变

对于可积奖励分布，以及非递减、发散且增量趋于零的探索调度g，EL-F保持了g-Forcing的伪regret渐近性质：当T趋于无穷时，R(T)/g(T)几乎必然收敛到所有次优臂的suboptimality gap之和。这意味着引入经验似然并没有牺牲长期的渐近效率。

有限时间期望regret上界

在每一个次指数（sub-exponential）实例上，对于满足温和可行性条件的g(t)=ω(log t)，期望伪regret被限制在 g(T)∑Δ_i + C_P 以内，其中C_P是与时间T无关的实例相关常数。这个结果的价值在于：它把"最终会收敛"变成了"任意有限轮次内期望regret有明确天花板"，对实际部署更有指导意义。

尾部风险与下界匹配

论文进一步给出了超越强制探索预算后regret的超多项式衰减尾部界。对于缓变（slowly varying）的g，作者在两臂高斯实例上精确刻画了线性regret偏差的指数，并建立了在同等的每实例期望regret预算约束下策略类的匹配下界。这种上下界匹配意味着该刻画在理论上无法被显著改进。

次指数分布与超多项式衰减：次指数（sub-exponential）分布是一类比次高斯更宽泛的分布族，其尾部衰减速度慢于高斯但快于重尾幂律，典型例子包括指数分布、卡方分布以及部分有界但非对称的分布。若随机变量X满足存在参数使得其矩母函数在原点附近有限，则称其具有次指数尾。在bandit分析中，MGF方法常被用于推导regret的集中不等式。超多项式衰减指尾部概率的衰减速度快于任意多项式——即对任意常数k，尾部概率乘以T^k仍趋于零——这比常见的多项式衰减更强，意味着极端糟糕的regret事件几乎不可能发生，对风险敏感的实际部署尤为关键。

贪心变体与局部乐观性

EL-F在经验似然半径为0时退化为贪心变体，论文的定量保证同样覆盖了这一特例。当半径取固定正值时，算法引入局部乐观性（local optimism），在保持主导渐近regret的同时，带来了两个可证明的优势：

• 在具有确定性次优臂的两臂bandit中，与贪心变体建立了耦合的路径级占优关系；
• 实验表明，在困难实例上，相较于原始g-Forcing，EL-F显著减少了长期次优分配的持续时间。

后一点在工程上尤其重要——很多失败的bandit部署并不是收敛不到最优臂，而是在收敛之前把过多轮次浪费在了明显较差的臂上。

局部乐观性：乐观性（optimism）是bandit算法的经典原则——在面对不确定性时，选择置信上界最高的臂，使算法在探索与利用之间自动平衡。UCB族正是全局乐观性的代表。局部乐观性则指乐观判断只在由强制探索调度界定的局部范围内生效，例如EL-F中仅在经验似然半径为正时对经验均值做出有界上修。相比全局乐观，局部乐观不要求对整个奖励空间构造置信集，从而避免了对奖励尺度、方差或尾部参数的显式估计，同时保留了减少次优臂采样时间的效果。经验似然半径的大小直接控制乐观程度的强弱：半径为零即退化为纯贪心。

与既有方法的对比分析

g-Forcing的策略逻辑是：用一条非递减的探索调度g(t)强制保证每根臂被采样的次数下界，从而绕开对奖励尺度的估计需求。EL-F在此基础上加入了经验似然半径这一自由度，相当于让算法在强制探索的框架内嵌入了数据驱动的置信判断。

从方法论看，这一路径与UCB家族的思路不同。UCB需要构造置信上界，而置信上界的宽度通常依赖奖励分布的方差或尾部参数；EL-F通过经验似然规避了对这些参数的显式依赖，同时通过g-Forcing的调度结构保留了scale-free特性。论文的理论结果说明，这种组合在渐近意义上没有付出额外代价。

实验部分，作者在具有挑战性的实例上展示了EL-F相对g-Forcing在长期次优分配上的减少，验证了固定正半径带来的局部乐观性的实用价值。

适用场景与开放问题

EL-F的适用场景主要落在奖励尺度未知、分布可能次指数尾、且运行轮次有限的实际系统中，例如在线广告出价、推荐系统冷启动探索、以及A/B测试中的流量分配。这些场景的共同特点是对"最坏情况下会浪费多少流量"比"最终是否找到最优解"更敏感。

论文留下的开放方向包括：更高臂数下线性regret偏差指数的精确刻画、非高斯分布下的下界匹配、以及g调度在实际约束（如延迟反馈）下的自适应选择。从工程角度看，固定正半径的最优选取规则目前仍缺少指导，这可能是后续工作最值得填补的空白。