当"后悔药"遇上会学习的对手：重复博弈中的策略后悔最小化
你有没有过这样的经历：和同一个对手下了很多盘棋，你每次都根据之前的对局调整策略，但对手也在根据你的调整而调整——你变了他也变了，永远追不上那个"如果我当时一直这么做就好了"的影子。
这就是重复博弈中自适应对手的核心难题。传统理论告诉你：用"后悔最小化"来指导学习——每次选让自己后悔最少的策略。但问题是，当对手也在学习时，传统的后悔定义就失效了。
囚徒困境：一个让人不安的例子
考虑最经典的重复囚徒困境。两个玩家反复选择合作或背叛，收益矩阵如下：双方合作各得0.6，双方背叛各得0.2，一方背叛一方合作则背叛者得1.0、合作者得0。
传统的外部后悔（External Regret）告诉你：每一轮，如果你选了合作，而背叛会更好，你就有了后悔。最小化这种后悔的结果是什么？双方都选择背叛——因为背叛是占优策略。最终收敛到双方各得0.2的悲惨均衡。
但所有人都知道，"以牙还牙"（Tit-for-Tat）策略——第一轮合作，之后模仿对手上一轮的动作——在无限重复囚徒困境中是纳什均衡，双方各得0.6，远好于0.2。然而，以牙还牙在传统后悔框架下却有线性后悔——因为当对手突然背叛时，你跟着背叛的那一轮"本可以"一直合作来获得更高收益。
这里暴露了一个深刻的矛盾：一个在博弈论意义上最优的策略，在传统后悔框架下却不是"无后悔"的。 问题出在哪里？
传统后悔的盲区
传统外部后悔的定义是：在T轮博弈后，比较你实际获得的累计收益与"如果你每轮都选某个固定动作"的收益之差。关键在于——比较对象是固定策略，它假设对手的行为不会因为你换了一个策略而改变。
但在重复博弈中，这个假设根本不成立。如果你从"总是合作"换成"以牙还牙"，对手的行为一定会改变——因为对手也在观察你的历史行为并做出响应。传统后悔完全忽略了这种"策略替换会改变对手行为"的连锁效应。
这就是Mingyang Liu、Asuman Ozdaglar和Tiancheng Yu在论文中要解决的核心问题。
RP-Regret：一种新的后悔度量
论文提出了重复策略后悔（Repeated Policy Regret, RP-Regret）。与外部后悔的关键区别在于比较对象：RP-Regret的比较对象不是一个固定动作，而是一个完整的策略序列——而且这个策略序列中的每一步都可以根据历史做出响应。
形式化地说，RP-Regret衡量的是：
如果你把整个策略序列替换成另一个策略序列（其中每一步都可以根据历史调整），而对手也相应地调整了他们的响应，你的收益会有多大差距？
这个定义天然地捕捉了"策略替换会改变对手行为"这一事实。回到囚徒困境的例子：以牙还牙策略在RP-Regret下是无后悔的——因为任何单方面的策略替换，在对手也以牙还牙的情况下，都不会获得更高的收益。
什么时候RP-Regret最小化是可能的？
论文给出了一个精密的"必要条件"分析，列出了RP-Regret最小化必须满足的条件：
条件1：比较策略的缓慢变化。 比较对象（那个"本可以用的"策略序列）不能变化太快。直觉上，如果你的比较对象每一轮都在剧烈变化，那它本身就不是一个合理的学习目标。
条件2：对手策略的确定性。 对手的策略需要是确定性的（或近似确定性的），这样你才能预测对手对你策略变化的响应。
条件3：策略对远期历史的指数衰减依赖。 每个玩家的策略对远期历史的敏感度应该随距离指数衰减——最近的几轮博弈对决策影响最大，很久以前的影响可以忽略。这保证了有效的记忆长度只需要O(log(1/ε))轮。
论文证明了这些条件不仅是充分的，而且是必要的——去掉任何一个，RP-Regret最小化都不可能实现。这组条件构成了一个完整的"可能性边界"。
三条通往RP-Regret最小化的路径
面对RP-Regret的非凸性（因为连续时间步的策略乘积使得目标函数非凸），论文提出了三种算法路径：
路径一：非凸优化预言机。 如果我们有一个能解决非凸优化的"黑箱"，那么在条件1和条件3下就可以实现RP-Regret最小化。虽然计算上可能不可行，但这个结果告诉我们：RP-Regret最小化在信息论上是可能的，瓶颈只在计算。
路径二：局部RP-Regret（LRP-Regret）。 这是一个巧妙的凸化技巧。与其比较整个策略序列的替换效果，不如只看"在某一轮单点替换"的效果。形式化地，LRP-Regret只考虑在时间步s将策略替换为比较策略，而其他时间步保持不变。
这个局部化操作使得每一步的损失函数关于当前策略是线性的，因此可以用简单的**投影梯度下降（PGD）**来优化。论文证明，当对手满足条件3且比较策略的变化PT是次线性的时，LRP-Regret以Õ(|A|^(m+1)√(PT/T) + Cγ_m)的速率收敛。
路径三：马尔可夫博弈重构。 这是最有技术深度的路径。核心思想是：将重复博弈重新参数化为一个马尔可夫博弈（Markov Game），状态空间是最近M轮的历史，然后用**占位测度（Occupancy Measure）**来凸化优化问题。
具体来说，在M-有界记忆的假设下，重复博弈可以被重构为一个状态空间为H^M的马尔可夫博弈。策略不再是优化的变量，取而代之的是占位测度q——描述在每个状态下采取每个动作的频率。占位测度空间是凸的，因此期望损失关于占位测度也是凸的。
但这里有一个精巧的技术挑战：占位测度天然地包含了所有玩家的策略，而在我们的设定中，对手的策略是不受我们控制的。论文设计了一组约束条件，确保从占位测度中提取的对手策略与实际对手策略的一阶差分有界，从而避免了误差的累积爆炸。
从后悔到均衡
RP-Regret不仅是学习指标，还与均衡计算有深刻联系。论文证明：
当所有玩家都实现RP-Regret最小化时，他们的策略序列构成一个近似的子博弈完美纳什均衡（SPNE）。 这意味着RP-Regret最小化不仅让每个个体"不后悔"，还让整个系统收敛到博弈论意义上的合理结果。
特别地，对于无限重复博弈，如果所有玩家的RP-Regret都是次线性的，那么时间平均策略收敛到SPNE。对于有限重复博弈，RP-Regret最小化对应于近似粗相关均衡（CCE）。
为什么这很重要？
这篇论文的意义在于重新定义了"在自适应对手面前学习"这个问题本身。
传统的在线学习框架假设对手是"健忘"的——每轮独立选择，不受你的历史行为影响。但现实中的对手是"有记忆"的：你的每一个动作都在塑造对手未来的行为。RP-Regret首次为这种场景提供了一个博弈论原生（game-theoretic native）的后悔度量。
三条算法路径各有适用场景：非凸预言机提供了理论上的可能性保证，LRP-Regret提供了计算高效的近似方案，马尔可夫博弈重构提供了直接最小化原始RP-Regret的路径。
回到囚徒困境的例子：传统后悔理论告诉我们"总是背叛"是最优的，RP-Regret理论则告诉我们"以牙还牙"才是真正无后悔的。这不仅是一个技术修正，更是一个视角的转换——当对手也在学习时，"后悔"的定义本身需要被重新思考。
本文基于论文 Regret Minimization in Repeated Games with Adaptive Opponents（Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, 2026）撰写。论文暂无官方开源代码。
