技术摘要：基于均值的算法：一个下界与遗憾度

问题陈述

本文研究了在在线学习背景下的基于均值的算法（mean-based algorithms），特别关注了具有**带置反馈（bandit feedback）且时间跨度未知（unknown time horizon）的多臂老虎机（MAB）**设定。

基于均值的算法由以下原则定义：代理人应以较低的概率选择在未来具有低历史平均回报的动作。虽然近期的文献表明这些算法能有利地收敛至序列劣势动作（近似经济博弈中的纳什均衡），但实证研究表明，在带置反馈场景下，它们相比于成熟的算法存在收敛缓慢的问题。此外，这些算法在委托人-代理人博弈中的“可剥削性（exploitability）”与其理论收敛保证之间存在张力。

解决的具体挑战包括：

1. 为未知跨度设定（即总轮数 $T$ 预先未知的情况）定义基于均值的算法。
2. 确定控制避免“劣势”动作的定义速率序列 $\gamma_t$ 的理论极限。
3. 澄清基于均值的算法与**无外部遗憾（no-external-regret）**算法之间的关系，特别是这类算法在带置反馈下是否能同时具备这两个属性。

研究方法

1. 定义与预备知识

作者形式化了两种基于均值的算法定义：

• $\gamma_t$-基于均值： 基于当前平均回报 $\alpha_t(a)$。如果 $\alpha_t(a') - \alpha_t(a) > \gamma_t$，则在 $t+1$ 时刻选择 $a$ 的概率至多为 $\gamma_t$。
• 预测性 $\gamma_t$-基于均值： 基于下一步的平均回报 $\alpha_{t+1}$。

论文证明了这两种定义是相互可转换的，并侧重于带置设定下的非预测性变体。

2. 提出的算法

作者提出了两种适配带置反馈和未知跨度的算法：

• 广义 $\epsilon$-贪婪算法（Generalized $\epsilon$-Greedy）： 一种变体，其中如果某个动作的估计累积回报显著低于其他动作，则该动作被视为“劣势”动作。该算法向劣势动作分配极小的概率 $\epsilon_t$，并将剩余概率分配给非劣势动作。
• 基于均值的 Exp3（Mean-Based Exp3）： Exp3（用于探索与利用的指数权重算法）的一个变体。它使用基于估计累积回报的多项式权重，并包含一个探索组件 $\epsilon_t$ 以确保充分采样。

两种算法都利用重要性加权估计器来处理缺乏全反馈的问题。

3. 理论下界推导

为了确定这些算法学习能力的根本极限，作者推导了速率序列 $\gamma_t$ 的下界。

• 对抗性构造： 他们构造了两个特定的对抗性环境（$x'_t$ 和 $x''_t$）来利用探索与利用之间的权衡。在这些环境中，算法必须区分两个最初看起来相似但在后期发生分歧的动作。
• 不可区分性论证： 由于带置反馈，如果算法选择特定动作的频率过低（为了满足较小的 $\gamma_t$），它将无法区分这两个环境。
• 不等式推导： 通过分析在这些构造的环境中选择劣势动作的概率，他们得到了一个必要的不等式：$\sum_{t=t_1}^{t_c-1} \gamma_t + k \cdot \gamma_{t_c} \geq 1$。
• 渐近分析： 他们使用积分近似这个求和过程，以证明任何比 $O(1/\sqrt{t})$ 衰减更快的速率序列（具体而言，任何 $\gamma_t \in o(1/\sqrt{t})$ 的序列）都会违反在带置设定下作为基于均值算法所需的条件。

4. 遗憾度分析

作者分析了基于均值的算法与无外部遗憾算法的交集。他们证明，虽然基于均值的算法并不自动保证无遗憾（并且在某些具有极小 $\gamma_t$ 的特定对抗设置下可能会遭受线性遗憾），但存在特定的配置（特别是某些参数化的 Exp3）可以同时满足基于均值属性和无外部遗憾属性。

核心贡献

1. 首次给出 $\gamma_t$ 的下界： 本文为带置反馈设定下基于均值算法的速率序列 $\gamma_t$ 提供了第一个正式的下界。它确立了 $\gamma_t$ 的衰减速度不能快于 $O(1/\sqrt{t})$。具体而言，任何 $\gamma_t \in o(1/\sqrt{t})$ 的序列在带置设定下都是无效的基于均值算法。
2. 未知跨度算法： 作者提出了两种有效的基于均值的算法（广义 $\epsilon$-贪婪和基于均值的 Exp3），它们可以在无需预先知晓时间跨度 $T$ 的情况下有效运行。
3. 澄清定义关系： 本研究澄清了预测性与非预测性基于均值定义之间的关系，展示了它们的互换性。
4. 遗憾度与基于均值的重叠： 论文证明了基于均值的算法集合与无外部遗憾算法集合并非不相交。作者构造了一个既是基于均值又是无遗憾的特定 Exp3 变体。
5. 实证验证： 通过数值实验，作者展示了虽然基于均值的算法可能比标准的对应算法收敛稍慢，但它们在随机 MAB 设置和经济博弈（伯特兰德寡头垄断）中都能取得具有竞争力的表现。

结果

理论结果

• 下界： 序列 $\gamma_t = \frac{1}{2\sqrt{t}+1}$ 被确定为一个关键阈值。任何严格快于此（例如 $\gamma_t = 1/t^{0.51}$ 或 $\gamma_t = 1/t$）的衰减序列都被证明在带置反馈下对于基于均值的算法是无效的。
• 遗憾度： 论文确认了基于均值的算法并非在本质上具有一种会排除无遗憾保证的“可剥削性”。存在既是基于均值又是无遗憾的算法。

实证结果

• 随机 MAB： 在 10 臂老虎机实验中，所提出的基于均值的 Exp3（取 $\alpha=1/2$）与标准 Exp3 配置相比，向最优动作收敛的速度略慢，但差异微乎其微。$\epsilon$-贪婪变体表现出依赖于探索率的性能。
• 伯特兰德寡头垄断： 在重复定价博弈中，基于均值的 Exp3 算法比先前文献（如 Bichler 等人，2025）中观察到的收敛到纳什均衡的速度显著加快。基于均值的 $\epsilon$-贪婪算法较慢，这归因于当支配阈值较高时存在过度的探索。

重要性与主张

本文声称提供了一个关于基于均值算法性能的基本极限。推导出的 $\gamma_t$ 下界解释了为什么这些算法通常学习缓慢：为了在缺乏全反馈的情况下满足基于均值的条件（避免劣势动作），算法必须保持一定水平的探索。如果探索率下降得太快（即 $\gamma_t$ 变得太小），算法就无法区分环境，从而被迫执行劣势动作，这违反了基于均值的定义。

作者将他们的工作定位为协调委托人-代理人博弈中的“可剥削性”担忧与博弈论中的收敛保证的必要步骤。通过展示基于均值属性与无遗憾属性可以共存，他们表明基于均值的算法是经济学习场景中一种可行的替代方案，前提是必须仔细选择 $\gamma_t$ 以尊重所推导的下界。

论文总结道，虽然基于均值的算法并非普遍比标准的无遗憾算法更快，但它们提供了一类独特的学习动态，这种动态在以收敛至序列无劣势策略为主要目标的情况下可以具有竞争力。这项工作留下的悬而未决的问题是：是否可以构造出一种算法，在保持最优遗憾度的同时，精确匹配 $\gamma_t \approx 1/\sqrt{t}$ 的理论下界。