重复博弈中与自适应对手的遗憾最小化 Regret Minimization with Adaptive Opponents in Repeated Games
提出RP-Regret度量，解决重复博弈中自适应对手的遗憾最小化问题
前置知识
外部遗憾
在线学习中的经典度量，衡量决策者在时间步t的损失与知道事后信息选择某些固定动作时的损失差异。公式定义为 $R_T = \sum_{t=1}^T \ell_t(a_t) - \min_{a \in A} \sum_{t=1}^T \ell_t(a)$，其中 $\ell_t(a)$ 是在时间步t选择动作a的损失。然而在重复博弈中，这种度量假设损失序列仅是时间步的函数，无法捕捉对手基于历史行为的响应特性。
理解外部遗憾的局限性是理解本文新贡献的关键基础，本文正是针对其在博弈理论中的不足而提出了RP-Regret。
重复博弈
同一矩阵博弈在多个时间步中重复进行的博弈形式。在重复博弈中，玩家可以根据历史行动 $h_t = (a_1, a_2, \ldots, a_t)$ 来决定当前行动，这使得策略成为历史依赖的函数 $\pi^{(i)}(a_i|h_t)$。与一次性博弈不同，重复博弈允许更丰富的策略空间和合作可能性，例如在迭代囚徒困境中，tit-for-tat策略可以促成合作均衡。
本文的研究对象是重复博弈，理解其基本概念和历史依赖性对于理解RP-Regret的定义和算法设计至关重要。
子博弈完美纳什均衡（SPNE）
在重复博弈中，不仅要求整体策略构成纳什均衡，还要求从任何历史节点开始的子博弈也构成纳什均衡。这意味着即使在某些历史发生后，玩家也没有动机偏离均衡策略。对于有限重复博弈，当一次性博弈的纳什均衡唯一时，其子博弈完美均衡就是在每个时间步都重复该纳什均衡。但对于无限重复博弈，存在更多可能性。
论文证明了RP-Regret最小化与计算特定子博弈完美均衡之间的关系，这是本文理论贡献的重要组成部分。
研究动机
在重复博弈中，经典的外部遗憾度量存在根本性缺陷。假设在迭代囚徒困境中，两个玩家都追求亚线性外部遗憾，那么他们的时间平均策略只会收敛到唯一的粗相关均衡，即always-defect，此时每个玩家的效用仅为0.2。然而，tit-for-tat策略（从合作开始，模仿对手上一轮动作）是无限轮迭代囚徒困境的纳什均衡，能够实现更高的时间平均效用0.6。但tit-for-tat策略会遭受线性外部遗憾。问题的核心在于：外部遗憾假设损失序列仅是时间步的函数 $\ell_t(a)$，而在重复博弈中，对手会根据历史行动调整策略 $\pi^{(-i)}_t(a_{-i}|h_{t-1})$，玩家的行动会影响对手未来的决策，这种响应性无法被经典遗憾捕捉。已经证明当对手能够响应时，实现无外部遗憾是不可能的。
本文的目标是本文的具体目标是提出一种新的遗憾度量标准，专门用于重复博弈中与自适应对手进行博弈的场景。该度量需要：能够捕捉对手的响应性和适应性；允许比较器策略是时变的（动态的）；对所有玩家的策略空间施加尽可能少的约束；保持计算可行性；并且通过最小化这种度量，能够找到更好的均衡解。同时，本文还致力于识别获得亚线性遗憾的必要条件，开发可证明的算法来最小化这种新的遗憾，并建立遗憾最小化与重复博弈均衡计算之间的理论关系。
与已有工作不同的是，本文的独特切入角度在于：首先，不同于在线学习中的Policy Regret（假设有界记忆，如损失仅依赖于最近m步行动），本文认识到在重复博弈中，早期轮次的偏离可能改变对手的观察，从而影响他们在远超m轮之后的行动，即使每个玩家使用有限记忆策略。其次，不同于Zinkevich提出的Response Regret（考虑依赖整个历史的混合策略空间，虽然使最小化成为凸优化，但策略空间大小是历史长度的指数，计算不可行），本文旨在保持计算可行性。最后，不同于Arora等人将Policy Regret扩展到博弈设置但限制比较器为常数动作，本文允许比较器策略是时变的，并施加最少的约束以保持对手的适应性。
核心方法
方法的核心思路是提出重复策略遗憾（RP-Regret）这一新的博弈论度量，衡量在所有玩家都能响应历史的情况下，已实现效用与事后最佳累积效用之间的差异。直觉上，传统外部遗憾只比较如果我当时选择不同动作的损失，而RP-Regret比较如果我当时选择不同策略，并且对手也相应地调整策略的损失。技术路线上，首先定义RP-Regret的形式化度量，然后分析其可最小化的必要条件（比较器的变化速度和玩家的记忆限制），接着针对RP-Regret的非凸性提出三种最小化方法：基于非凸优化预言机的方法、通过线性化得到的LRP-Regret方法、以及将重复博弈重构为马尔可夫博弈并使用占用测量的方法。最后，建立RP-Regret最小化与重复博弈均衡计算的理论联系。
核心创新点在于RP-Regret的定义，它捕捉了重复博弈中策略改变会影响对手未来响应这一本质特性。与外部遗憾不同，RP-Regret中在时间步t偏离到比较器策略 $\hat{\pi}_t$ 不仅影响时间步t的预期损失，还会影响之后的所有预期损失，因为历史分布改变了，自适应对手会相应调整策略。此外，LRP-Regret基于单步偏离原理，通过在每个时间步局部偏离而非全局偏离来凸化问题，这使得可以使用简单的投影梯度下降算法。将重复博弈重构为马尔可夫博弈并使用占用测量的方法，则通过提升变量维度将非凸问题转化为凸问题，同时设计新的约束来处理对手策略的提取。
方法步骤详情
RP-Regret最小化的完整步骤如下：首先，定义累积预期损失 $J_T(\pi_{1:T}) = \sum_{t=1}^T f^{t-1}(\pi_{1:t})$，其中 $f^m(\pi_{1:m+1})$ 是基于m步历史的预期损失。然后，定义RP-Regret为 $R_T = J_T(\pi_{1:T}) - \min_{\hat{\pi}^{(1)}_{1:T} \in \mathcal{C}^{(1)}_T} J_T((\hat{\pi}^{(1)}_{1:T}, \pi^{(-1)}_{1:T}))$，其中 $\mathcal{C}^{(1)}_T$ 是满足条件1（子线性变化）和条件3（指数衰减记忆）的比较器空间。对于LRP-Regret，定义 $R_{local,T} = \max_{s \in [T]} \sum_{t=s}^T [J_T(\pi_{1:T}) - J_T(\tilde{\pi}^{(1),s}_{1:T}, \pi^{(-1)}_{1:T})]$，其中 $\tilde{\pi}^{(1),s}_{1:T}$ 仅在时间步s偏离。使用投影梯度下降更新：$\pi^{(1)}_{t+1} = \text{Proj}_{\mathcal{X}^{(1)}_\gamma}(\pi^{(1)}_t - \eta \nabla f^{t-1}_{local}(\pi^{(1)}_{1:t}))$，学习率 $\eta = \Theta(\sqrt{T})$。对于马尔可夫博弈方法，将状态空间定义为 $S = H_M$（长度为M的历史），占用测量 $q(h,a)$ 表示在状态h选择联合动作a的频率，策略从占用测量恢复为 $\pi(a|h) = q(h,a)/\sum_{a'} q(h,a')$，并通过在线凸优化约束 $\sum_{h,a} \max(0, -D_t(h,a,q))D_t(h,a,q) \leq 0$ 确保一致性。
技术新颖性
技术新颖性体现在多个方面：首先，RP-Regret是第一个专门为重复博弈设计的、原生且自然的遗憾度量，它同时考虑了玩家的偏离和对手的响应，这是之前工作所没有的。其次，识别了获得亚线性RP-Regret的必要条件，特别是条件3（指数衰减记忆）作为条件2（不完美记忆）的可量化版本，这填补了理论空白。第三，LRP-Regret利用单步偏离原理将非凸问题凸化，这是一个巧妙的技巧。第四，马尔可夫博弈重构中的创新约束设计避免了绝对值函数的非可微问题，同时将约束违反转化为RP-Regret的上界。最后，建立了RP-Regret最小化与近似子博弈完美粗相关均衡（SPCCE）的理论联系，这是遗憾学习与均衡计算之间的重要桥梁。
实验结果
论文的核心发现包括理论保证和实验验证两个方面。在理论上，证明了当对手满足条件3（指数衰减记忆）且选择学习率 $\eta = \Theta(\sqrt{T})$ 和 $\gamma \leq 1/2(N+2)$ 时，LRP-Regret满足 $R_{local,T}/T \leq \tilde{O}(|A|^{m+1}\sqrt{T}/T + C_{\gamma}^m)$，其中 $P_T = \sum_{t=2}^T \|\hat{\pi}^{(1)}_{t-1} - \hat{\pi}^{(1)}_t\|_\infty$ 是比较器策略变化的上界，$C_{\gamma}^m = (2N+1)^{m+1}\gamma^{m+1}$。当 $P_T$ 是T的亚线性函数时，对于任意 $\epsilon > 0$，选择 $m = \Theta(\log(1/\epsilon))$ 可以使 $R_{local,T}/T \leq \epsilon$。对于马尔可夫博弈方法，证明了当 $T \geq \tilde{\Omega}(\Delta_T/\epsilon^4)$（$\Delta_T$ 是所有对手和比较器变化的总和）时，$R_T/T \leq \epsilon$。建立了均衡计算关系：当每个玩家在 $T_0$ 步内达到 $O(T_0^p)$ 的亚线性RP-Regret（$p \in [0,1)$），并且在 $T \to +\infty$ 时循环使用这些策略，则可以得到 $O(T_0^{1-p}/T_0)$ 近似的、有界偏离的SPNE。实验上，在Stag-Hunt博弈中展示了最小化新的RP-Regret和LRP-Regret可以带来更高的效用和更多的合作解决方案，虽然论文没有给出具体的数值指标，但与经典外部遗憾方法的对比显示了明显的优势。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| Stag-Hunt博弈 | 时间平均效用 | RP-Regret最小化实现更高的合作均衡效用 | 外部遗憾最小化收敛到低效均衡 | 从低效合作（如defect-defect）提升到高效合作均衡 |
局限与改进
局限性分析：作者在论文中承认了几个局限性。首先，第一种算法（基于非凸优化预言机）虽然在理论上成立，但在实际中可能是计算不可行的，因为没有提供具体的实现方法。其次，虽然证明了必要条件，但这些条件在某些实际场景中可能过于严格，特别是条件3（指数衰减记忆）可能限制了策略的表达能力。第三，实验部分相对简单，只展示了Stag-Hunt博弈的结果，缺乏更广泛的博弈类型的验证，如多人博弈或零和博弈。第四，马尔可夫博弈方法要求对手策略变化缓慢（条件1也适用于对手），这在实际自适应对手场景中可能不成立。第五，论文没有讨论RP-Regret与现有自适应 regret（如interval regret）之间的关系，这可能影响其在更广泛在线学习场景中的应用。最后，虽然建立了与均衡计算的联系，但除了LRP-Regret的算法外，没有给出实际计算均衡的具体算法。
独立分析的弱点
独立分析的弱点包括：计算复杂度方面，LRP-Regret算法需要维护 $(m+1)$ 步历史，复杂度有 $|A|^{m+1}$ 的指数依赖，当动作空间较大时这可能成为严重瓶颈。在实际应用方面，条件要求对手具有指数衰减记忆，但现实中的对手可能使用更复杂的策略，如基于神经网络的自适应策略，这会破坏理论保证。实验验证不足，缺乏对不同类型博弈（如拍卖、谈判、资源分配等实际场景）的广泛测试，也未与现有的Policy Regret或Response Regret方法进行定量对比。理论界限松散，论文中的 $\tilde{O}$ 符号隐藏了多项式因子，可能使理论界限在实际T值下不够紧致。多人博弈扩展性有限，虽然理论支持N个玩家，但实际算法的扩展性和收敛速度在N较大时可能急剧下降。初始分布敏感性，马尔可夫博弈方法虽然在条件3下对初始分布不敏感，但实际可能需要特定的初始化才能达到良好的性能。
未来方向
未来研究方向包括：作者在结论中提到可以研究由RP-Regret最小化诱导的更弱均衡概念，可能需要更弱的假设来计算这些均衡。基于本文成果可延伸的方向：开发更高效的LRP-Regret算法，减少对历史长度的指数依赖，可能通过近似方法或稀疏表示。将RP-Regret框架扩展到更广泛的在线学习场景，如元学习、多臂老虎机等。研究RP-Regret在其他博弈类型中的应用，如随机博弈、微分博弈或网络博弈。开发实际可用的均衡计算算法，特别是利用RP-Regret的最优性来选择特定的均衡。研究在对手不完全满足指数衰减记忆条件时的鲁棒性分析。探索RP-Regret与深度强化学习方法的结合，使用神经网络表示策略和占用测量。进行更广泛的实证研究，包括真实世界的博弈场景，如拍卖设计、推荐系统中的竞争等。
复现评估
复现评估方面，论文没有提供开源代码或数据集，这增加了复现难度。理论结果相对容易验证，因为数学证明在附录中给出了详细推导。实验部分描述较为简洁，没有提供具体的超参数设置（如学习率的具体值、历史长度m的选择等）、实验运行的随机种子、重复实验的次数和标准差等细节。实验规模也没有明确说明，不清楚进行了多少轮博弈、是否进行了多次独立运行。算力需求方面，算法主要涉及矩阵运算和梯度计算，在普通服务器上应该可以实现，但马尔可夫博弈方法的占用测量优化可能需要较大内存，特别是当状态空间 $H_M$ 较大时。总体而言，复现难度中等偏高，需要根据论文描述重新实现算法，并猜测未公开的超参数。
论文图表
图展示了迭代囚徒困境的博弈矩阵，包含两个玩家（玩家1和玩家2）和两种行动（Cooperate和Defect）。矩阵的四个单元格分别给出了不同行动组合下两个玩家的效用。通常的囚徒困境矩阵中，双方合作获得中等效用，双方背叛获得低效用，一方合作一方背叛时背叛者获得高效用、合作者获得最低效用。
这张图对理解论文至关重要，因为它提供了本文的主要 motivating example。论文用这个矩阵说明了经典外部遗憾的局限性：当两个玩家都追求亚线性外部遗憾时，只能收敛到defect-defect均衡（效用0.2），而tit-for-tat策略虽然能实现更高效用（0.6）但会遭受线性外部遗憾。这直接说明了为什么需要新的RP-Regret度量。