参考：Recent Progresses in Multi-Agent RL Theory
我们假设读者已对单智能体强化学习算法熟悉，可以参考该书，该文着眼于单智能体与多智能体强化学习的“不同之处”，同时会有较多博弈论的内容。
Formulation: 马尔可夫博弈
选取马尔可夫博弈作为多智能体强化学习的模型。
我们考虑有 m 个玩家的非零和马尔可夫博弈(MG)，可以被描述为元组 MG(H,S,{Ai}i=1m,P,{ri}i=1m) ，其中，
- H 是每局游戏的长度
- S状态空间的集合
- Ai 第i个玩家的动作空间的集合，所有玩家同时行动，我们使用 a=(a1,…,am)∈∏i=1mAi 表示联合动作
- P={Ph} 是转移概率的集合， Ph=Ph(sh+1|sh,ah)
- ri={ri,h} 是第i个玩家的奖励函数，有 ri,h(sh,ah)∈[0,1]
MG的一条轨迹看起来像这样：
s1,(a1,1,…,am,1),(r1,1,…,rm,1),s2,…,sH,(a1,H,…,am,H),(r1,H,…,rm,H).
其他符号(如 Vi,hπ(sh) 、 Qi,hπ(sh,ah) )和单智能体中表示类似，比较便于理解。
一种特殊情况：零和博弈
即 m=2,r1=−r2 ，此时每位玩家都像最大化自己的奖励，两位玩家之间是纯竞争(full-competitive)关系，我们可以使用 V1π1,π2 来表示玩家1的价值函数，我们假设玩家1想最大化该价值、玩家2想最小化该价值。围棋，国际象棋，将棋都可以用零和MG建模。
纳什均衡
MG中，每个智能体仍想最大化自己的累计奖励，但我们需要额外考虑一些个体最优性条件外的均衡。我们考虑的是纳什均衡，即对于每一个智能体，固定其他智能体的策略，该智能体能够获得最大累计奖励。
Nash equilibrium: Each player plays the best response to all other player’s policies.
特殊地，如果智能体之间的策略互不影响奖励，则MG问题可看作MDP问题求解。
这里推荐阅读综述：《Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms》，里面详细介绍了不同均衡类型的数学形式。
我们定义 ϵ -approximate Nash equilibrium如下：
maxi∈[m](maxπi′Vi,1πi′,π−i−Vi,1πi,π−i)≤ϵ.
如果 ϵ=0 ，我们称此时策略 π 达到纳什均衡(exact Nash equilibrium)。
注意，这里我们假设所有智能体的策略之间是独立的，非独立的策略有其他的均衡形式。
零和博弈中的纳什均衡
性质：
- 纳什值唯一性：存在唯一的 V1⋆∈[0,H] ，尽管 (π1⋆,π2⋆) 可能并不唯一
- 强对偶性：任意的纳什均衡是
最大-最小的结果和最小-最大结果，即
{maxπ1′V1π1′,π2≥minπ2′maxπ1′V1π1′,π2′≥maxπ1′minπ2′V1π1′,π2′≥minπ2′V1π1,π2′maxπ1′V1π1′,π2≥V1π1,π2≥minπ2′V1π1,π2′
当纳什均衡时取等号( =V1⋆,⋆ )
零和MG中的规划算法
有了上述假设，我们如何得到纳什均衡呢？我们引入了纳什价值迭代算法(Nash-VI)
和MDP中的价值迭代类似，但策略选择机制发生了改变：把最大化向量 Q⋆(s,⋅) 替换为了求 Q⋆(s,⋅,⋅) 的MatrixNash，这是因为学习的目标并不是最大化单个玩家的奖励，而是使两个玩家达到纳什均衡。
Nash-VI = Value Iteration with Max(⋅) replaced by MatrixNash(⋅) .
算法流程如下：
对任意矩阵 M∈RA1×A2 ， MatrixNash 定义为：
MatrixNash(M):=arg(maxπ1∈ΔA1minπ2∈ΔA2π1⊤Mπ2),
这里 ΔA1 和 ΔA2 表示 A1 和 A2 的概率单纯形。当然，纳什Q学习也是一种计算纳什的方法。（联想单智能体中的价值迭代、Q学习算法）
注意，Nash-VI和Nash Q-learning都是集中式训练，因为求MatrixNash使用了联合计算。
零和MG中高效采样(样本高效)的纳什均衡学习
在规划算法中，我们是拥有全局信息的，而现在我们通过与环境不断的交互来学习策略，这要求算法能够处理探索-利用之间的平衡。我们的目标是设计一个样本高效的算法，例如通过尽量少的轮数学习到 ϵ -approximate Nash equilibrium。
乐观 Nash-VI
首先是我们在上一节提到Nash-VI算法的乐观变体，由Liu et al. 2020提出，基于更早的样本高效Nash-VI算法工作 (Bai & Jin 2020, Xie et al. 2020)。
算法流程如下：
主要的两个特点：
- 两次乐观Q值估计：上限估计 Q¯h (假设 H 步奖励都是最大值1)，下限估计 Q_h 。乐观程度由两个奖励函数衡量 β,γ 。 β 类似于单智能强化学习中的
Bernstein bonus for exploration，这里推荐Michael I Jordan大牛的一篇文章， γ 是一种针对model-based而设计的奖励，可以参考Dann et al. 2018。 - 使用矩阵CCE( Coarse Correlated Equilibrium)来计算策略。对于任意的矩阵对 M¯,M_∈RA1×A2 ， MatrixCCE(M¯,M_) 定义为任意满足下列条件的联合策略π∈ΔA1×A2 ：
E(a1,a2)∼π[M¯(a1,a2)]≥maxa1′∈A1E(a1,a2)∼π[M¯(a1′,a2)],E(a1,a2)∼π[M_(a1,a2)]≤mina2′∈A2E(a1,a2)∼π[M_(a1,a2′)].
即两个玩家使用联合策略 π 进行游戏，最大值玩家(上述章节已定义)偏离支付矩阵 M¯ 将没有任何益处，最小值玩家同理。使用CCE的目的是高效地找到有关上下限估计的优策略(该计算可以通过线性规划实现)。
Theorem (Liu et al. 2020): With high probability, optimistic Nash-VI outputs an ε-Nash within K=O~(H3SA1A2/ϵ2) episodes of play.
即该算法的复杂度为 A1A2 ，这看起来是很自然的，因为零和MG的联合动作空间也为 A1A2 ，后续我们将看到，通过分布式算法,算法的复杂度可以达到 max{A1,A2} 。
Centralized training, decentralized execution(CTDE)：注意到该算法中，CCE返回的策略和探索时使用的策略都是联合策略，也就是说整个算法必须要以集中式的方式训练。但在算法的结束阶段，输出的是边缘联合策略，即可以分布式执行，这种范式在多智能体强化学习中是常见的。
V-learning
第二种算法是最近才提出的V-learning。这里采用的是该算法发表在期刊上的简化版本。该算法可以看做是一种单智能体强化学习算法，因为每个玩家智能体观察到自己的状态、奖励和下一个时刻的状态(类似于单智能体MDP)。
算法流程如下：
该算法主要分为以下三个部分：
- 使用了 V 的增量更新：这个部分与Q-learning类似，但不对Q函数建模而是对V函数建模。
- Adversarial bandit subroutine：Q-learning是使用贪婪规则来决定策略，而V-learning采用的是Adversarial bandit subroutine来获得策略。具体地说，从 (sh,h) 获得 (rh,sh+1) 后，对应的对抗老虎臂程序按照“动作 ah∈A 获得了 H−rh−min{Vh+1(sh+1),H−h}H∈[0,1] 的损失”来进行更新，V-learning算法具体采用
weighted follow-the-regularized-leader算法进行更新。 - 输出策略：V-learning的策略是嵌套混合策略：在策略执行过程中，使用的轮数 k 是不断更新的，这使得策略具有非马尔可夫性。
该算法有下述定理：
Theorem (Bai et al. 2020, Jin et al. 2021c): Suppose both players run the V-Learning algorithm with the Adv Bandit Update as a suitable weighted Follow-The-Regularized-Leader algorithm for each (s,h) . Then, running this for K episodes, (the product of) their certified output policies (π^1,π^2) is an ε-Nash as long as K≥O~(H5Smax{A1,A2}/ϵ2) .
多玩家的非零和MG
Correlated Equilibria (CE) and Coarse Correlated Equilibria (CCE)
给出了两种均衡的概念以及他们与纳什均衡之间的联系：
通常的，我们有{Nash}⊂{CE}⊂{CCE}。