Regret Minimization with Adaptive Opponents in Repeated Games

TL;DR 提出 **Repeated Policy Regret (RP-Regret)** 度量重复博弈中自适应对手的后悔，并设计非凸优化算法实现亚线性后悔与更优均衡。

问题

在重复博弈和多智能体交互中，学习算法常需应对自适应对手（adaptive opponents），即对手会根据交互历史动态调整策略，在拍卖、谈判、多智能体系统等场景中普遍存在。传统在线学习多假设对手静态或随机，难以捕获真实互动中的策略适应。

标准外部遗憾（external regret）仅比较实际收益与最佳固定策略收益，忽略对手因我方策略改变而作出的响应，导致指标无法反映动态环境下的真实性能。后续出现的策略遗憾（policy regret）或交换遗憾（swap regret）虽允许对手有某种反应，但对反应函数施加严格限制（如仅依赖玩家自身动作、要求对手变化平滑或有界），使定义与真实博弈脱节，且难以同时保证次线性遗憾并收敛至高质量均衡（如子博弈完美均衡）。

定义能建模反事实推理的遗憾（如本文的重复策略遗憾，RP-Regret），要求比较器依赖完整历史下对手的真实反应，这直接导致优化目标非凸，经典在线凸优化算法失效。同时，为得到次线性遗憾，还需精细平衡比较器策略变化速度与对手记忆长度。该问题处于博弈论、在线学习与多智能体系统交叉点，其解决将为多智能体强化学习（MARL）的训练稳定性、对抗鲁棒性及合作涌现提供理论基础，对自治系统、经济机制设计等意义重大。

类似自动驾驶中，规划模块需预测环境车辆对自车动作的反应，才能使长期交互轨迹安全高效，而非简单假设其他车辆维持当前状态不变。

核心洞察

• Repeated Policy Regret (RP-Regret) 将自适应对手的反应直接纳入遗憾定义，突破了传统外部遗憾假设对手固定的局限。 在重复博弈中，标准外部遗憾仅衡量相对固定策略的损失，无法反映对手基于历史进行反事实推理的能力。RP-Regret 允许比较器策略与对手策略均依赖历史，因而与重复博弈的子博弈完美均衡等概念自然兼容，为对抗自适应行为提供了更坚实的理论框架。
• 本文提出在非凸策略空间中直接最小化 RP-Regret 的三种算法路线，克服了该度量固有非凸性带来的优化困难。 与多数依赖凸代理或假设对手无记忆的工作不同，作者分别设计了基于优化预言机、逐轮凸线性代理以及对手策略缓慢变化时占用度量凸化的方法，各在不同结构性条件下实现次线性悔恨，为非凸在线博弈优化提供了可操作的工具箱。
• 当所有玩家均采用 RP-Regret 最小化算法时，系统可收敛至重复博弈的特定均衡，甚至实现比纳什均衡更优的合作解。 该发现将个体悔恨最小化与全局均衡学习连接起来，区别于仅追求个体无憾的在线学习方法，说明适当设计的悔恨度量能引导多智能体系统自发涌现高效协作成果，对构建合作型 AI 系统具有启发意义。

方法

为解决重复博弈中自适应对手带来的非凸遗憾最小化问题，本文提出 Repeated Policy Regret (RP-Regret) 框架，并设计三种算法，遵循“输入历史交互 → 关键模块 → 输出当前策略”的流程。

核心建模：将博弈转化为带记忆的马尔可夫博弈

对手响应历史，因此将重复博弈建模为有界记忆的马尔可夫博弈，其中状态为有限长度的历史动作序列。这种转化使玩家策略可表示为占有率测度(occupancy measure)，从而利用其凸性。

三种算法模块

1. 基于优化预言机 (Oracle-based)：假设每步可调用一个非凸优化预言机，直接最小化原始 RP-Regret。该模块适用于有现成优化求解器的场景，但计算成本高。
2. 线性化代理 (Local RP-Regret)：在每轮迭代时，对 RP-Regret 目标函数进行线性化展开，得到一个凸代理损失。通过一阶梯度信息更新策略，避免了直接处理非凸性，使算法可高效实现。该代理损失可在玩家均采用时引导收敛到子博弈精炼均衡 (SPNE)。
3. 慢变对手直接优化：当对手策略变化足够慢时，利用 Fast Mixing 性质将 RP-Regret 直接转化为凸优化问题，通过投影梯度下降求解。该模块假设对手具有持续性，适用于缓慢适应的场景。

输出：下一轮动作概率分布

每种算法每轮输出一个混合策略，玩家据此采样动作。所有算法均能保证 RP-Regret 次线性增长，且当所有玩家使用相同算法时，可学习到重复博弈的子博弈精炼粗相关均衡 (SPCCE)。

与传统外部遗憾不同，RP-Regret 允许比较器策略随历史自适应变化，从而在猎鹿博弈 (Stag-Hunt) 等场景中找到更优合作解。

实验

实验设计

实验在经典的 Stag-Hunt 协调博弈上进行，该博弈存在两个纯策略纳什均衡：高风险高回报的“合作捕鹿”与低风险低回报的“单独猎兔”。玩家分别运行基于 RP-Regret（或线性化变体）的在线学习算法，与基于传统外部后悔的算法（如 regret matching）进行对比。实验模拟了重复博弈场景，记录长期累积效用与合作频率，以验证新后悔度量能否自发涌现合作行为。

关键发现

• 最小化 RP-Regret 的玩家在 Stag-Hunt 中显著提高了合作概率，最终收敛到“捕鹿”均衡，获得比基线更高的累积效用。
• 传统外部后悔最小化算法由于无法捕捉对手的策略适应性，往往收敛到低效的“猎兔”均衡或振荡不收敛。
• 线性化替代（Local RP-Regret）在保持计算可行性的同时，仍能引导到合作均衡，表明理论上的凸代理有效捕获了重复博弈的结构。

与基线对比的深度解读

外部后悔仅比较固定策略下的表现，而 RP-Regret 允许比较策略随着历史动态调整，因此能以更强的“反事实”角度评价决策。在 Stag-Hunt 中，这一特性使得算法能推断出：即使当前回合合作有风险，长期历史依赖的策略能构建互信，从而改变均衡选择。实验证明，RP-Regret 类算法在自适应对手环境中比传统后悔度量更具协调能力，为多智能体强化学习中的合作涌现问题提供了新的理论工具，且算法实现无需环境模型，仅依赖历史反馈。

行业影响

落地场景

RP-Regret 框架直接适用于多智能体序列决策场景，其中其他参与者会根据历史行为动态调整策略。典型产品与业务包括：

• 实时广告竞价平台：多个广告主采用自动出价策略，彼此根据历史竞价分布动态调整出价，最小化 RP-Regret 可提升长期展示点击回报。
• 高频交易市场：做市商或算法交易代理需应对其他参与者基于历史订单流变化的响应，RP-Regret 导向的策略可减少被对手“剥削”的损失。
• 内容推荐多平台博弈：内容分发平台间的推荐策略相互影响用户注意力，通过 RP-Regret 可学习到避免囚徒困境的更优均衡。
• 多回合谈判与资源分配：如跨国供应链中多个决策中心根据历史供应请求调整报价或配额。

商业价值

• 效用提升与降本：在 Stag-Hunt 等社会困境中，最小化 RP-Regret 的玩家能收敛到更合作的高效用均衡，相比传统 external regret 仅保证个人不后悔但可能陷入低回报均衡，RP-Regret 直接提升集体收益。这在广告竞价中体现为更高的 ROI，在交易中减少非零和竞争损耗。
• 增强对自适应对手的鲁棒性：对手策略随时间变化时，传统 external regret 无法保证性能，而 RP-Regret 的算法即使在对手策略缓慢变化或记忆有限时也能实现亚线性后悔，业务收益更稳定。
• 降低策略迭代成本：提出的凸代理（线性化后悔）和 occupancy measure 方法使得原本非凸问题可被高效求解，无需大量试错或环境模型即可部署。

与现有产品/工作流的接口

RP-Regret 最小化算法可作为在线策略优化模块嵌入现有决策系统：

• 在基于 bandit 或强化学习的决策服务中，将优化目标从 external regret 替换为 RP-Regret（或 Local RP-Regret），使用文中提出的凸代理或 oracle 方法。
• 对于状态空间有限的问题（如有限记忆博弈），可借助占用测度（occupancy measure） 将问题转为凸规划，集成进现有线性规划求解器或策略梯度框架。
• 实际工程中，可先采用 Local RP-Regret 代理快速迭代，当检测到对手策略变化缓慢时切换到直接最小化 RP-Regret 的算法，以平衡计算开销与最优性。

具体 Use Case

1. 全局广告投放优化：某全球在线广告平台的每个广告主 agent 运行 RP-Regret 出价算法，平台方提供 API 供 agent 获取近期的出价分布（对手行为历史），agent 通过在线凸优化（如 projected gradient descent）最小化 linearized RP-Regret，从而在长期竞价中获得更高转化收益，同时平台整体填充率与价格稳定性提升。
2. 金融量化交易：多家对冲基金使用算法交易，每家策略根据历史价格冲击和对手单流动态调整挂单。采用 RP-Regret 的代理可订阅订单簿快照作为历史信号，通过记忆有限的 Markov game 建模，利用 occupancy measure 规划最优交易执行，在多个回合后获得相对于 hindsight 最优策略的更小后悔，降低因对手自适应而造成的滑点损失。

局限

• - **强假设依赖**：理论保证要求对手策略记忆长度有界或变化缓慢，且需比较器策略变化有限。在实际多智能体场景中，对手可能具备长期记忆或快速自适应，导致次线性 RP-Regret 无法达成。此外，基于 oracle 的算法假设存在优化黑箱，实践中难以满足；直接最小化 RP-Regret 的方法则要求对手策略缓慢变化，这一条件在竞争性博弈中常被违背。
• - **实验验证有限**：仅在 Stag-Hunt 等简单矩阵博弈上验证，未拓展到大规模或复杂动态环境。缺少与现有 regret 概念（如 internal regret、counterfactual regret）在非合作均衡求解上的直接对比，难以评估在真实多智能体任务中的有效性与可扩展性。算法在面对高维状态、连续动作时的适用性也未探讨。
• - **计算与收敛权衡**：RP-Regret 定义非凸，直接优化困难。文中提出的线性化替代（LRP-Regret）虽可简化求解，但可能牺牲部分理论性质；而 occupancy-measure 方法的约束满足依赖于 Markov 游戏重构，当记忆长度增加时易受维度诅咒影响，收敛速率或与状态空间指数相关，实用性受限。