Multi-Agent Reinforcement Learning

从这一节开始进入 Multi-Agent Reinforcement Learning，也就是多智能体强化学习。

在单智能体 RL 中，我们通常只关心一个 agent 的 return：

但是在多智能体场景下，环境中同时存在多个 agent，每个 agent 的收益不仅取决于自己的动作，也取决于其他 agent 的动作。也就是说，问题从“一个 agent 怎么最大化自己的回报”，变成了“多个 agent 在相互影响时会形成什么结果”。

所以在正式进入 MARL 算法之前，需要先补充一些博弈论中的基本概念。

前置准备

布雷斯悖论

先看一个很经典的例子：布雷斯悖论（Braess’s Paradox）。

假设有 $4000$ 辆车要从 Start 开到 End，中间有两个途径点 $A$ 和 $B$，一开始有两条路线可以选：

每条边的通行时间如下，其中 $t$ 表示这条边上的车辆数：

设选择 $S \rightarrow A \rightarrow E$ 的车辆数是 $x$，那么选择 $S \rightarrow B \rightarrow E$ 的车辆数就是 $4000-x$。

两条路线的时间分别是

如果想让两条路都没有单方面换路的动力，就需要两条路时间相同：

解得

所以最优分流是两条路线各走 $2000$ 辆车，此时每辆车的通行时间都是

这个结果很合理：一半车走上面，一半车走下面，大家的时间都是 $65$。

现在加入一条新的 shortcut：

并且这条路不需要时间：

看起来这应该只会让情况更好，因为每辆车多了一个选择。但是如果每辆车都只按照自己的局部最优来选，结果会变差。

首先，从 $S$ 出发时：

• 走 $S \rightarrow A$ 的时间是 $\frac{t}{100}$，最多也就是 $\frac{4000}{100}=40$
• 走 $S \rightarrow B$ 的时间固定是 $45$

所以每辆车都会更倾向于先走

到达 $A$ 之后：

• 直接走 $A \rightarrow E$ 的时间固定是 $45$
• 走 shortcut 到 $B$，再走 $B \rightarrow E$ 的时间是 $0 + \frac{t}{100}$，最多也是 $40$

所以每辆车又会更倾向于走

最后所有车都会选择新路线

这时 $S \rightarrow A$ 上有 $4000$ 辆车，$B \rightarrow E$ 上也有 $4000$ 辆车，所以每辆车的时间变成

也就是说，加入一条免费的 shortcut 之后，原来每辆车只需要 $65$，现在反而变成了 $80$。

这就是布雷斯悖论：在多智能体系统中，给每个个体增加一个看似更好的选择，并不一定会提升整体效率。因为每个个体都在做局部最优决策，最后形成的均衡结果可能比原来的系统更差。

博弈结果的评判标准

假设有两个 agent，分别选择动作 $a_1$ 和 $a_2$，收益函数为

不同的评判标准对应不同的“什么结果是好结果”。

社会福利

社会福利（Social Welfare）关注所有 agent 的收益总和：

对于两个 agent 来说就是

如果只从社会福利角度评价，那么最好的 joint action 是

这个标准不关心收益怎么分配，只关心整体加起来是不是最大。

帕累托优

如果一个结果 $x$ 相比另一个结果 $y$，满足：

1. 对所有 agent 都不更差
2. 至少让一个 agent 变得更好

那么就说 $x$ 帕累托优于 $y$。

写成公式就是

并且存在某个 agent $j$ 满足

如果一个结果已经不存在任何其他结果能帕累托优于它，那么这个结果就是帕累托最优（Pareto Optimal）的。

需要注意的是，帕累托最优并不意味着总收益最大，也不意味着公平。它只表示：想让某个人更好，就一定会让至少另一个人更差

社会福利是帕累托最优的子集

纳什均衡

纳什均衡（Nash Equilibrium）关注的是稳定性。

如果在一个 joint action $(a_1^*,a_2^*)$ 下，任意一个 agent 在其他 agent 动作不变时，都无法通过单方面改变自己的动作获得更高收益，那么这个 joint action 就是纳什均衡。

对于两个 agent，可以写成

也就是说，在纳什均衡处，每个 agent 的动作都是对其他 agent 当前动作的 best response

当我们定义最优反应后，纳什均衡解意味着所有 agent 都在最优反应上

优超

优超（Dominance）关注的是动作之间的比较。

如果对 agent $i$ 来说，动作 $a_i$ 无论其他 agent 选择什么动作，都至少不比动作 $a_i'$ 差，并且在某些情况下更好，那么就说 $a_i$ 弱优超 $a_i'$：

并且存在某个 $a_{-i}$ 满足

如果上面的不等式对所有 $a_{-i}$ 都严格成立，那么就是严格优超：

直觉上，优超策略就是“不管别人怎么选，我选这个都更好”

如果所有智能体均存在优超，那么优超策略的交集就是一个纳什均衡解

囚徒困境

囚徒困境是最经典的双人博弈问题。两个 agent 都有两个动作：

使用一个常见的收益矩阵：

括号中第一个数是 Agent 1 的收益，第二个数是 Agent 2 的收益。

从社会福利看

计算每个结果的总收益：

所以从社会福利最大化的角度看，最好的结果是

也就是两个 agent 都合作。

从帕累托优看

$(D,D)$ 的收益是 $(1,1)$，而 $(C,C)$ 的收益是 $(3,3)$。

因为

所以 $(C,C)$ 帕累托优于 $(D,D)$。

但是 $(C,C)$、$(C,D)$ 和 $(D,C)$ 都是帕累托最优的。比如从 $(C,C)$ 变成 $(D,C)$，Agent 1 的收益从 $3$ 变成 $5$，但是 Agent 2 的收益从 $3$ 变成 $0$，这不是帕累托改进。

因此帕累托视角下，$(D,D)$ 明显不是好结果，因为它可以被 $(C,C)$ 同时改善。

从纳什均衡看

如果 Agent 2 选择 $C$，Agent 1 选择 $D$ 的收益是 $5$，选择 $C$ 的收益是 $3$，所以 Agent 1 会选 $D$。

如果 Agent 2 选择 $D$，Agent 1 选择 $D$ 的收益是 $1$，选择 $C$ 的收益是 $0$，所以 Agent 1 还是会选 $D$。

对 Agent 2 也是完全对称的。

所以 $(D,D)$ 是纳什均衡，因为在这个结果下，任何一方单独改成 $C$ 都会让自己的收益从 $1$ 变成 $0$。

这里就出现了一个很重要的问题：纳什均衡不一定是社会福利最大的结果，也不一定是帕累托最优的结果。

从优超看

对 Agent 1 来说：

• 如果 Agent 2 选择 $C$，那么 $D$ 的收益 $5$ 大于 $C$ 的收益 $3$
• 如果 Agent 2 选择 $D$，那么 $D$ 的收益 $1$ 大于 $C$ 的收益 $0$

所以 $D$ 严格优超 $C$。

对 Agent 2 来说也是一样，$D$ 严格优超 $C$。

因此从优超策略的角度看，两个 agent 都会选择 $D$，最后得到

这也是囚徒困境的核心矛盾：个体理性会把系统推向整体更差的结果。

纯策略纳什均衡和混合策略纳什均衡

前面囚徒困境中的 $(D,D)$ 是一个纯策略纳什均衡。

纯策略（Pure Strategy）指的是 agent 直接选择某一个确定动作。比如在石头剪刀布中，直接选择“石头”就是一个纯策略。

如果一个纯策略组合 $(a_1^*,a_2^*)$ 满足任意 agent 都不能通过单方面改变动作获得更高收益，那么它就是纯策略纳什均衡。

但是不是所有博弈都有纯策略纳什均衡。一个典型例子就是石头剪刀布。

石头剪刀布

石头剪刀布的规则是：

上表表示 Agent 1 的收益，Agent 2 的收益是它的相反数，所以这是一个 zero-sum game。

石头剪刀布没有纯策略纳什均衡。原因很简单：

• 如果双方都出石头，那么任意一方都可以改成布来赢
• 如果一方赢了，输的一方总可以改成克制对方的动作
• 如果双方平局，任意一方也可以改成能赢的动作

也就是说，任何确定的动作组合都不是稳定的。

这时就需要引入混合策略（Mixed Strategy）。

混合策略不是直接选择一个确定动作，而是在动作上定义一个概率分布：

对于石头剪刀布，Agent 可以用下面的策略：

如果两个 agent 都使用这个均匀随机策略，那么任意一方改成固定出某个动作，期望收益都还是 $0$：

同理，固定出剪刀或布的期望收益也都是 $0$。

因此没有任何一方能通过单方面改变自己的策略获得更高期望收益，所以

是石头剪刀布的混合策略纳什均衡。

Stackelberg 均衡

前面的纳什均衡默认所有 agent 是同时做决策的。而 Stackelberg Game 中存在先后顺序：

1. Leader 先选择策略
2. Follower 观察到 Leader 的策略后，再选择自己的 best response

因此 Stackelberg 均衡关注的是：Leader 在知道 Follower 会做最优回应的前提下，应该提前承诺什么策略。

设 Leader 的策略为 $a_L$，Follower 的 best response 为

那么 Leader 要解的问题是

最终得到的策略组合

就是 Stackelberg 均衡。

直观来说，Stackelberg 均衡不是“大家同时选完后谁都不想改”，而是“Leader 先承诺，Follower 再最优回应，Leader 提前把这个回应也考虑进去”。

均衡学习

在单智能体 Q-learning 中，下一状态的价值是通过对自己的 action 取最大值得到的：

因此标准 Q-learning 的更新可以写成

但是在多智能体场景中，下一状态的价值不能只看自己的动作，因为其他 agent 的动作也会影响收益。也就是说，$V(s')$ 不再只是一个简单的 $\max_a Q(s',a)$，而是需要根据某种均衡概念，从当前状态对应的 stage game 中计算出来。

这类方法可以统一写成

其中

表示所有 agent 的 joint action。

所以均衡学习（Equilibrium Learning）的核心就是：每个状态 $s$ 都对应一个由 $Q_i(s,\mathbf{a})$ 构成的矩阵博弈，然后用某种均衡解法计算 $V_i(s)$，再把这个 $V_i(s)$ 放回 TD target 中。

Minimax-Q

Minimax-Q 主要用于 two-player zero-sum game，也就是两个 agent 的收益完全相反：

对于 agent $i$ 来说，对手不是一个普通环境，而是一个会尽可能让自己收益变低的 adversary。所以在计算 $V_i(s)$ 时，agent 需要选择一个混合策略 $\pi_i$，让自己在最坏情况下的收益最大。

Minimax-Q 的核心函数是

这里和标准 Q-learning 最大的区别是：

也就是说，标准 Q-learning 只假设自己下一步会选最好的动作，而 Minimax-Q 假设对手会选最坏的反制动作。

Minimax-Q 的更新可以写成

算法流程可以写成

Minimax-Q
初始化 Q_i(s, a_i, a_-i)
for t = 0, 1, 2, ... do
    在状态 s_t 根据当前策略选择动作 a_i^t
    观察对手动作 a_-i^t、奖励 r_i^t 和下一状态 s_{t+1}
    V_i(s_{t+1}) <- max_{pi_i} min_{a_-i} sum_{a_i} pi_i(a_i|s_{t+1}) Q_i(s_{t+1}, a_i, a_-i)
    Q_i(s_t, a_i^t, a_-i^t) <- Q_i(s_t, a_i^t, a_-i^t) + alpha [r_i^t + gamma V_i(s_{t+1}) - Q_i(s_t, a_i^t, a_-i^t)]
end for

Nash-Q

Minimax-Q 适合 zero-sum game，但是很多多智能体问题不是零和的。比如两个 agent 可能既有竞争，也有合作，这时候不能简单假设“别人一定会让自己最差”。

Nash-Q 的做法是：在每个状态 $s$，把所有 agent 的 $Q_i(s,\mathbf{a})$ 看成一个 normal-form game，然后先求这个 stage game 的 Nash equilibrium。

设在状态 $s$ 下求得的 Nash equilibrium 为

那么 agent $i$ 的状态价值定义为这个均衡下的期望收益：

这里和标准 Q-learning 的区别是：

也就是说，Nash-Q 不是直接取最大动作，而是先计算一个多智能体均衡策略，再用均衡策略下的期望收益作为 $V_i(s')$。

Nash-Q 的更新可以写成

算法流程可以写成

Nash-Q
初始化每个 agent 的 Q_i(s, a)
for t = 0, 1, 2, ... do
    所有 agent 在状态 s_t 选择 joint action a_t
    观察奖励 r_i^t 和下一状态 s_{t+1}
    用 {Q_i(s_{t+1}, a')}_{i=1}^n 构造下一状态的 stage game
    求该 stage game 的 Nash equilibrium pi*(s_{t+1})
    V_i(s_{t+1}) <- sum_{a'} [prod_j pi_j*(a_j'|s_{t+1})] Q_i(s_{t+1}, a')
    Q_i(s_t, a_t) <- Q_i(s_t, a_t) + alpha [r_i^t + gamma V_i(s_{t+1}) - Q_i(s_t, a_t)]
end for

Nash-Q 的直觉很自然，但是实际使用会遇到一个问题：一个 stage game 可能存在多个 Nash equilibrium，此时到底选择哪一个均衡会影响 $V_i(s)$ 的计算结果。

Friend-or-Foe Q

Friend-or-Foe Q 可以看作对 Nash-Q 的一个简化。它不在每个状态中求一般的 Nash equilibrium，而是提前假设其他 agent 和自己之间的关系只有两种：

如果其他 agent 是 friend，那么 agent $i$ 假设大家会一起选择让自己收益最大的 joint action：

如果其他 agent 是 foe，那么就回到 Minimax-Q 的形式：

如果同时存在 friend 和 foe，可以把 joint action 拆成三部分：

其中 $\mathbf{a}_F$ 表示 friend 的动作，$\mathbf{a}_E$ 表示 foe 的动作。那么更一般的形式可以写成

这里和标准 Q-learning 的区别是：

也就是说，Friend-or-Foe Q 把其他 agent 先分类：friend 的动作和自己一起 max，foe 的动作进入 min。

算法流程可以写成

Friend-or-Foe Q
初始化 Q_i(s, a)，并给定其他 agent 是 friend 还是 foe
for t = 0, 1, 2, ... do
    在状态 s_t 选择动作，并观察 joint action a_t
    观察奖励 r_i^t 和下一状态 s_{t+1}
    if 其他 agent 是 friend then
        V_i(s_{t+1}) <- max_{a'} Q_i(s_{t+1}, a')
    else if 其他 agent 是 foe then
        V_i(s_{t+1}) <- max_{pi_i} min_{a_-i} sum_{a_i} pi_i(a_i|s_{t+1}) Q_i(s_{t+1}, a_i, a_-i)
    end if
    Q_i(s_t, a_t) <- Q_i(s_t, a_t) + alpha [r_i^t + gamma V_i(s_{t+1}) - Q_i(s_t, a_t)]
end for

总结一下，这三类方法的区别主要就在于 $V_i(s')$ 的定义：

从这个角度看，均衡学习其实就是把标准 Q-learning 中的

替换成一个由博弈均衡定义出来的

而不同算法的差异，就体现在它们相信其他 agent 会如何行动。

对手建模

均衡学习的思路是：假设每个状态下都存在一个 stage game，然后通过某种均衡概念计算 $V_i(s)$。

对手建模（Opponent Modeling）的思路不太一样。它不一定要求直接求均衡，而是尝试显式估计其他 agent 的行为模式：

然后 agent $i$ 在决策时，把这个估计出来的对手策略也考虑进去。

如果在单智能体 Q-learning 中，我们的目标是

那么在对手建模中，更自然的形式是

也就是说，我们不再假设对手一定按照某个均衡行动，而是先学习一个对手模型，再基于这个模型选择自己的 best response。

策略频率建模

最直接的对手建模方法就是策略频率建模，也可以理解为虚拟博弈（Fictitious Play）的思想。

它的核心假设很简单：对手未来的策略，可以用它过去的动作频率来估计。

假设在状态 $s$ 下，对手动作 $a_{-i}$ 被观察到的次数是

那么对手策略可以估计为

然后 agent $i$ 使用这个估计策略来计算自己每个动作的期望价值：

最后选择

这个方法的直觉就是：我不需要知道对手内部怎么想，只要统计它在类似状态下过去怎么做，然后对这个经验分布做 best response。

虚拟博弈的过程可以写成

Fictitious Play / Frequency Modeling
初始化 N(s, a_-i) = 0
for t = 0, 1, 2, ... do
    观察当前状态 s_t
    根据历史频率估计 pi_hat_-i(a_-i|s_t)
    a_i^t <- argmax_{a_i} sum_{a_-i} pi_hat_-i(a_-i|s_t) Q_i(s_t, a_i, a_-i)
    执行 a_i^t，观察对手动作 a_-i^t
    N(s_t, a_-i^t) <- N(s_t, a_-i^t) + 1
end for

这个方法简单、可解释，但也有明显限制：它默认对手策略相对稳定。如果对手也在学习，历史频率就可能滞后于对手当前策略。

对手类型建模

另一类直接建模方法是对手类型建模（Opponent Type Modeling）。

它不是直接估计“对手在每个状态下出每个动作的概率”，而是假设对手来自某个类型集合：

每个类型 $\theta_k$ 对应一种策略模型：

比如在一个游戏里，对手可能是：

agent 维护一个关于对手类型的 belief：

其中 $h_t$ 表示到当前为止观察到的历史轨迹。

当观察到对手在状态 $s_t$ 下选择动作 $a_{-i}^t$ 后，可以用 Bayes rule 更新类型概率：

归一化后得到新的 belief：

有了类型 belief 后，对手策略可以写成一个加权平均：

然后再像前面一样，对这个估计策略做 best response：

算法流程可以写成

Opponent Type Modeling
给定类型集合 Theta = {theta_1, ..., theta_K}
初始化 belief b_0(theta_k)
for t = 0, 1, 2, ... do
    pi_hat_-i(a_-i|s_t) <- sum_k b_t(theta_k) pi_-i(a_-i|s_t, theta_k)
    a_i^t <- argmax_{a_i} sum_{a_-i} pi_hat_-i(a_-i|s_t) Q_i(s_t, a_i, a_-i)
    执行 a_i^t，观察 a_-i^t
    b_{t+1}(theta_k) <- normalize[b_t(theta_k) pi_-i(a_-i^t|s_t, theta_k)]
end for

类型建模比频率建模更有结构，因为它可以利用先验知识。但问题也很明显：如果真实对手不在预设类型集合里，那么 belief 更新得再好，也只能在错误的模型集合中选择一个“最像的”类型。

递归建模

前面两种方法都在建模对手的行为，但还没有考虑一个问题：对手可能也在建模我。

递归建模（Recursive Opponent Modeling）的核心就是引入这种层级推理：

可以粗略写成：

这种思想在博弈论和多智能体系统中很自然，但递归层数一高就会带来很大的计算复杂度。因为每多一层，都要多维护一层“对手的信念”和“对手对我的信念”。

所以递归建模通常更适合用来理解多智能体推理结构，而不是直接在复杂深度 RL 场景中无限展开。

神经虚拟博弈

现代方法会把虚拟博弈的思想和神经网络结合起来，可以简单理解为 Neural Fictitious Self-Play（NFSP）这一类方法。

在普通虚拟博弈中，我们用显式频率统计来表示平均策略：

但是在大规模状态空间中，不能为每个状态都维护一张表，所以可以用神经网络来近似这个平均策略：

同时再用一个 Q 网络学习对平均策略的 best response：

因此 NFSP 类方法通常包含两部分：

可以把它理解为：

其中 RL 部分用于让 agent 变强，SL 部分用于记录长期平均策略，使训练过程更接近虚拟博弈中的策略平均。

这个方向的意义在于：它把原本只适合小型矩阵博弈的虚拟博弈，扩展到了高维状态空间和深度强化学习场景。

MARL 的三个困境

正式进入 MARL 算法之前，先把多智能体学习中最常见的三个问题单独拎出来：

这三个问题会贯穿后面很多 MARL 方法。

非平稳性

在单智能体 RL 中，我们通常假设环境转移是固定的：

但是在 MARL 中，agent $i$ 看到的转移其实和其他 agent 的策略有关：

如果其他 agent 的策略 $\pi_{-i}$ 也在学习，那么从 agent $i$ 的视角看，环境分布就在不断变化。

这就是非平稳性（Non-stationarity）。

IL 和 JAL

处理非平稳性的两种基础思路是 Independent Learner（IL）和 Joint Action Learner（JAL）。

IL 的做法是每个 agent 都把其他 agent 当成环境的一部分，直接学习

它的更新形式和单智能体 Q-learning 很像：

问题是，其他 agent 的策略变化被隐藏进了环境里，所以 IL 面对的是一个非平稳环境。

JAL 的做法更进一步，它直接把 joint action 放进 Q function：

其中 $\mathbf{a}$ 表示所有 agent 的联合动作。

这样 agent 至少知道“整个联合动作”产生了当前结果。在协作任务中，如果把下一状态中最好的联合动作当作 target，那么 JAL 的状态价值可以写成

和 Nash-Q 对比一下，Nash-Q 是先求下一状态 stage game 的 Nash equilibrium：

而 JAL 直接在 joint action 上取最大值：

所以 JAL 和 Nash-Q 的关键区别是：

JAL 的更新可以写成

算法流程可以写成

Joint Action Learner
初始化 Q_i(s, a)
for t = 0, 1, 2, ... do
    在状态 s_t 观察或形成联合动作 a_t
    执行 a_t，观察奖励 r_i^t 和下一状态 s_{t+1}
    V_i(s_{t+1}) <- max_{a'} Q_i(s_{t+1}, a')
    Q_i(s_t, a_t) <- Q_i(s_t, a_t) + alpha [r_i^t + gamma V_i(s_{t+1}) - Q_i(s_t, a_t)]
end for

Joint Action Learner with Opponent Model
初始化 Q_i(s, a_i, a_-i) 和对手模型 pi_hat_-i(a_-i|s)
for t = 0, 1, 2, ... do
    在状态 s_t 选择动作 a_i^t
    观察 (a_i^t, a_-i^t)、奖励 r_i^t 和下一状态 s_{t+1}
    更新对手模型 pi_hat_-i(a_-i^t|s_t)
    V_i(s_{t+1}) <- max_{a_i'} sum_{a_-i'} pi_hat_-i(a_-i'|s_{t+1}) Q_i(s_{t+1}, a_i', a_-i')
    Q_i(s_t, a_i^t, a_-i^t) <- Q_i(s_t, a_i^t, a_-i^t) + alpha [r_i^t + gamma V_i(s_{t+1}) - Q_i(s_t, a_i^t, a_-i^t)]
end for

JAL 比 IL 更能表达多智能体交互，但代价是 joint action 空间会随着 agent 数量指数增长。

相对过度泛化

相对过度泛化（Relative Overgeneralization, RO）通常出现在协作型 MARL 中。

它描述的是这样一种现象：某个 joint action 明明是全局最优，但是它需要多个 agent 精确配合。一旦队友没有配合好，这个动作就会得到很差的回报。结果在学习过程中，这个最优动作被“平均”成了低价值，最后 agent 反而学到了一个更稳但次优的策略。

看一个简单例子，两个 agent 都有动作 $A$ 和 $B$，共享奖励如下：

全局最优显然是

但是如果 Agent 2 还在随机探索，那么对 Agent 1 来说：

于是 Agent 1 会觉得 $B$ 比 $A$ 更好。Agent 2 也会做出类似判断。最后系统可能收敛到 $(B,B)$，虽然它的回报 $7$ 小于最优的 $10$。

这就是 RO 的核心：最优配合因为早期协作失败被低估，而次优但鲁棒的行为被过度泛化。

滞后 Q-learning

滞后 Q-learning（Hysteretic Q-learning）的核心想法是：在协作任务中，负 TD error 不一定说明当前动作不好，也可能是队友探索导致配合失败。

所以它使用两个学习率：

当 TD error 为正时，用较大的学习率 $\alpha$ 更新；当 TD error 为负时，用较小的学习率 $\beta$ 更新：

直觉上，它更愿意相信“好结果”，而对“坏结果”保持宽容。

算法流程可以写成

Hysteretic Q-learning
初始化 Q_i(s, a_i)，设置 alpha > beta
for t = 0, 1, 2, ... do
    选择并执行动作 a_i^t，观察共享奖励 r_t 和 s_{t+1}
    delta_t <- r_t + gamma max_{a_i'} Q_i(s_{t+1}, a_i') - Q_i(s_t, a_i^t)
    if delta_t >= 0 then
        Q_i(s_t, a_i^t) <- Q_i(s_t, a_i^t) + alpha delta_t
    else
        Q_i(s_t, a_i^t) <- Q_i(s_t, a_i^t) + beta delta_t
    end if
end for

宽容 Q-learning

宽容 Q-learning（Lenient Q-learning）和滞后 Q 的思想很像，也是为了避免早期协作失败过度惩罚好动作。

不同之处在于，宽容 Q 会显式维护一个温度或宽容度：

训练早期温度高，对负 TD error 更宽容；访问次数增加后温度逐渐下降，agent 变得更严格。

一种常见写法是根据温度定义宽容概率：

当 $\delta_t < 0$ 时，以概率 $l(s,a)$ 忽略这次负更新；当 $\delta_t \geq 0$ 时正常更新。

其中 $u \sim U(0,1)$。

算法流程可以写成

Lenient Q-learning
初始化 Q_i(s, a_i) 和温度 T(s, a_i)
for t = 0, 1, 2, ... do
    选择动作 a_i^t，观察 r_t 和 s_{t+1}
    delta_t <- r_t + gamma max_{a_i'} Q_i(s_{t+1}, a_i') - Q_i(s_t, a_i^t)
    l(s_t, a_i^t) <- 1 - exp(-K T(s_t, a_i^t))
    u <- Uniform(0, 1)
    if delta_t >= 0 or u > l(s_t, a_i^t) then
        Q_i(s_t, a_i^t) <- Q_i(s_t, a_i^t) + alpha delta_t
    end if
    T(s_t, a_i^t) <- kappa T(s_t, a_i^t)
end for

滞后 Q 是“负更新变小”，宽容 Q 是“早期负更新可能直接忽略”。

PHC

在介绍 WoLF 之前，先介绍 PHC，也就是 Policy Hill-Climbing。

普通 Q-learning 学到 $Q(s,a)$ 后，通常直接用 $\epsilon$-greedy 选动作。但 PHC 会显式维护一个随机策略：

然后一边用 Q-learning 更新 $Q_i(s,a)$，一边把策略往当前 greedy action 的方向推。

设当前最优动作为

那么 PHC 的策略更新可以写成

其中

最后再把策略裁剪到合法概率范围，并重新归一化：

直觉上，PHC 就是：Q-learning 负责估计动作价值，policy hill-climbing 负责把策略慢慢推向当前看起来最好的动作。

算法流程可以写成

Policy Hill-Climbing
初始化 Q_i(s, a_i) 和策略 pi_i(a_i|s)
for t = 0, 1, 2, ... do
    根据 pi_i(.|s_t) 选择动作 a_i^t
    执行动作，观察奖励 r_i^t 和下一状态 s_{t+1}
    Q_i(s_t, a_i^t) <- Q_i(s_t, a_i^t) + alpha [r_i^t + gamma max_{a_i'} Q_i(s_{t+1}, a_i') - Q_i(s_t, a_i^t)]
    a* <- argmax_a Q_i(s_t, a)
    pi_i(a*|s_t) <- pi_i(a*|s_t) + delta
    pi_i(a|s_t) <- pi_i(a|s_t) - delta / (|A|-1), for a != a*
    裁剪并归一化 pi_i(.|s_t)
end for

PHC 的问题是它使用固定策略步长 $\delta$。在多智能体场景中，如果所有 agent 都用固定步长调整策略，很容易相互追逐，导致策略震荡。

WoLF-PHC

WoLF-PHC 是在 PHC 上加入 WoLF 原则。WoLF 的全称是 Win or Learn Fast，它的核心思想是：

这里的 winning 通常通过当前策略 $\pi_i$ 和平均策略 $\bar{\pi}_i$ 的价值比较来判断：

如果

说明当前策略比平均策略更好，agent 处于 winning 状态，使用较小步长 $\delta_w$；否则处于 losing 状态，使用较大步长 $\delta_l$：

所以 WoLF-PHC 和 PHC 的区别就是：PHC 使用固定 $\delta$，而 WoLF-PHC 根据当前是否 winning 自适应选择策略更新步长。

算法流程可以写成

WoLF-PHC
初始化 Q_i(s, a_i), pi_i(a_i|s), pi_bar_i(a_i|s)
设置 delta_w < delta_l
for t = 0, 1, 2, ... do
    根据 pi_i(.|s_t) 选择动作 a_i^t
    执行动作，观察奖励 r_i^t 和下一状态 s_{t+1}
    Q_i(s_t, a_i^t) <- Q_i(s_t, a_i^t) + alpha [r_i^t + gamma max_{a_i'} Q_i(s_{t+1}, a_i') - Q_i(s_t, a_i^t)]
    更新平均策略 pi_bar_i(.|s_t)
    if sum_a pi_i(a|s_t) Q_i(s_t,a) > sum_a pi_bar_i(a|s_t) Q_i(s_t,a) then
        delta <- delta_w
    else
        delta <- delta_l
    end if
    a* <- argmax_a Q_i(s_t, a)
    pi_i(a*|s_t) <- pi_i(a*|s_t) + delta
    pi_i(a|s_t) <- pi_i(a|s_t) - delta / (|A|-1), for a != a*
    裁剪并归一化 pi_i(.|s_t)
end for

WoLF-PHC 的作用更偏向稳定多智能体中的策略变化：当自己表现不错时不要剧烈改变策略，当自己表现差时更快调整。

rFMQ

rFMQ 可以理解为 Frequency Maximum Q-value 这一类方法的递归版本，它的核心目标也是避免 RO。

普通 Q 值是平均意义下的估计：

但 RO 的问题恰好就出在“平均”上：一个动作只有在队友配合时才很好，配合失败时很差，于是平均值被拉低。

rFMQ 会额外记录两个信息：

这里最关键的是 $F_i(s,a_i)$ 的递归更新。更准确地说，rFMQ 不只是记录一个最大回报，还要记录这个最大回报是不是经常能够达到。

记这次用于更新的样本 target 为

如果这次出现了新的最大值：

那么直接更新最大值，并把频率重置为 $1$：

如果没有出现新的最大值，那么才用递归方式更新频率：

实际实现时，连续值场景中一般不会严格相等，所以可以把指示函数换成一个小阈值：

这也是 rFMQ 和 FMQ 的一个关键区别：FMQ 关注 maximum value 和达到 maximum 的频率，而 rFMQ 用递归方式在线维护这个频率，并且当新的最大值出现时把 $F$ 重置为 $1$。你刚才指出的理解是对的，这个重置是 rFMQ 的核心点。

有了 $Q^{max}$ 和 $F$ 后，动作选择时使用的增强评价值是

等价地写成

也就是说，$F$ 越大，说明这个动作越稳定地达到过高回报，那么 $E$ 就越接近 $Q^{max}$；$F$ 越小，说明最大回报更像偶然事件，那么 $E$ 就更接近普通平均 $Q$。

再用这个增强后的评价值进行 Boltzmann 选择：

直觉上，rFMQ 在说：如果某个动作虽然平均回报不高，但它曾经稳定达到过很高的回报，那么它可能是一个需要队友配合的好动作，不应该太早放弃。

算法流程可以写成

rFMQ
初始化 Q_i(s, a_i), Q_i^max(s, a_i), F_i(s, a_i)
for t = 0, 1, 2, ... do
    E_i(s_t, a_i) <- Q_i(s_t, a_i) + F_i(s_t, a_i) [Q_i^max(s_t, a_i) - Q_i(s_t, a_i)]
    根据 E_i(s_t, a_i) 用 Boltzmann 分布选择动作 a_i^t
    观察奖励 r_t 和下一状态 s_{t+1}
    y_t <- r_t + gamma max_{a_i'} Q_i(s_{t+1}, a_i')
    Q_i(s_t, a_i^t) <- Q_i(s_t, a_i^t) + alpha [y_t - Q_i(s_t, a_i^t)]
    if y_t > Q_i^max(s_t, a_i^t) then
        Q_i^max(s_t, a_i^t) <- y_t
        F_i(s_t, a_i^t) <- 1
    else
        F_i(s_t, a_i^t) <- (1-alpha_F)F_i(s_t, a_i^t) + alpha_F I(y_t = Q_i^max(s_t, a_i^t))
    end if
end for

这类方法和滞后 Q、宽容 Q 的区别是：滞后 Q 和宽容 Q 主要处理负反馈，而 rFMQ 通过记录最大回报与频率，让 agent 不要被平均回报误导。

信度分配

在协作型 MARL 中，很多任务只给一个全局奖励：

但是这个奖励是所有 agent 共同产生的。问题是：如果团队成功了，到底是谁贡献最大？如果团队失败了，到底是哪个 agent 的动作导致失败？

这就是信度分配问题（Credit Assignment）。

最直接的做法是让所有 agent 都使用同一个全局奖励：

但这会带来高方差和学习低效。因为某个 agent 的动作可能很好，却因为其他 agent 的错误导致全局奖励很差；反过来也可能某个 agent 做错了，但被队友补救，所以它仍然拿到高奖励。

差分奖励

差分方法（Difference Reward）的核心思想是：衡量 agent $i$ 的贡献时，不看全局奖励本身，而是看“有它”和“没有它”之间的差别。

设整个系统的状态和 joint action 记作 $z$，全局奖励是

如果把 agent $i$ 的行为替换成一个默认行为 $c_i$，得到 counterfactual 系统

那么 agent $i$ 的差分奖励定义为

这里

差分奖励的好处是，它仍然和全局目标一致，但能去掉很多与 agent $i$ 无关的噪声。

如果用于 Q-learning，可以直接把奖励替换成差分奖励：

算法流程可以写成

Difference Reward Learning
初始化每个 agent 的 Q_i(s, a_i)
for t = 0, 1, 2, ... do
    所有 agent 执行动作，得到系统结果 z_t 和全局奖励 G(z_t)
    for each agent i do
        构造 counterfactual z_-i + c_i
        D_i(z_t) <- G(z_t) - G(z_-i + c_i)
        Q_i(s_t, a_i^t) <- Q_i(s_t, a_i^t) + alpha [D_i(z_t) + gamma max_{a_i'} Q_i(s_{t+1}, a_i') - Q_i(s_t, a_i^t)]
    end for
end for

差分奖励最大的问题是 counterfactual 不一定容易得到。很多真实环境中，我们无法真的把 agent $i$ 的动作替换掉再跑一次环境，所以需要用模型估计或者用 critic 近似。

其他解决思路

除了差分奖励，还有几类常见思路：

比如 COMA 的思想就是使用 centralized critic 构造 counterfactual advantage：

它不是简单问“团队奖励是多少”，而是问“在其他 agent 动作不变时，agent $i$ 当前这个动作比它自己的平均动作好多少”。

再比如 VDN 和 QMIX 这类 value decomposition 方法，会把团队价值写成局部价值的组合：

或者更一般地写成

这类方法的目标是让每个 agent 能从全局价值中学到自己的局部贡献。

总结一下，信度分配要解决的是：

而不同方法的区别，就在于它们是通过手工奖励、反事实估计、centralized critic，还是 value decomposition 来完成这个拆分。