---

前言

用于记录MARL当中的经典算法
基础的MARL算法有三种类型：学习联合动作价值函数、学习智能体的显示模型根据过去的动作预测未来的动作、基于策略的学习方法基于梯度上升的方式直接学习策略的参数

---

一、动态规划值迭代算法

该方法类似于在MDP过程中的值迭代算法求解最优价值，算法如下：

将值迭代的方法应用到随机博弈过程中，值迭代的算法是基于有模型的强化学习算法，需要已知状态转移函数与奖励函数等
算法会对整个状态空间进行两次扫描：第一次扫描会计算每个智能体对于的状态的矩阵$M_{i,s}$，其包含了智能体i对于的联合动作得到的奖励，可以看做智能体i的奖励函数${\mathcal{R}}_i(a)=M_{i,s}(a).$；第二次扫描利用每个智能体得到的期望回报更新每个状态的价值函数，扫描的过程重复执行，直到每个智能体价值函数收敛到最优价值函数
$\begin{array}{c}{V}_i^{\ast }(s)=Valu{e}_i(M_{1,s}^{\ast },...,M_{n,s}^{\ast })\\ M_{i,s}^{\ast }=\sum _{s^{\prime }\in S}\mathcal{T}(s^{\prime }\mid s,a)\left[\begin{array}{c}{\mathcal{R}}_i(s,a,s^{\prime })+\gamma V_i^{\ast }(s^{\prime })\end{array}\right]\end{array}$
价值函数更新过程遵循下面的公式：
$\begin{array}{r}V(s)\leftarrow \underset{a\in A}{\max }\sum _{s^{\prime }\in S}\mathcal{T}(s^{\prime }\mid s,a)\left[\mathcal{R}(s,a,s^{\prime })+\gamma V(s^{\prime })\right]\end{array}$

$\begin{array}{rl}Valu{e}_i(M_{i,s})& \begin{array}{r}=\underset{a_i\in A_i}{\max }{M}_{i,s}(a_i)\end{array}\\ & \begin{array}{r}=\underset{a_i\in A_i}{\max }\sum _{s^{\prime }\in S}\mathcal{T}(s^{\prime }|s,a_i)\left[\mathcal{R}(s,a_i,s^{\prime })+\gamma V(s^{\prime })\right]\end{array}\end{array}$

二、TD差分联合动作学习

无模型学习方法，将MDP过程中的TD差分引入到多智能体SG过程中，Joint action learning（联合动作学习）是MARL当中的基本算法，通过学习多智能体的联合动作价值模型评估给定状态下的联合动作的期望回报，联合策略的更新方式如下：
$\begin{array}{rl}{Q}_i^{\pi }(s,a)& =\sum _{s^{\prime }\in S}\mathcal{T}(s^{\prime }\mid s,a)\left[{\mathcal{R}}_i(s,a,s^{\prime })+\gamma \sum _{a^{\prime }\in A}\pi (a^{\prime }\mid s^{\prime })Q_i^{\pi }(s^{\prime },a^{\prime })\right]\end{array}$
在给定状态下，智能体i要根据联合动作选择对于的Q值——${\max }_{a_i}{Q}_i(s,a_1,...,a_n)$，此类算法称为JAL-GT
随机博弈的TD算法如下：

其中${\Gamma }_s$与根据博弈类型有关，其中非重复标准博弈，以2个智能体3个动作为例，${\Gamma }_s$如下所示：

且$Valu{e}_i({\Gamma }_{s^{\prime }})={\sum }_{a\in A}{\Gamma }_{s^{\prime },i}(a){\pi }_{s^{\prime }}^{\ast }(a)$，${\pi }_{s^{\prime }}^{\ast }$代表标准博弈下的均衡联合策略

1.Nash Q-learning

适用范围：一般和博弈的随机博弈过程
使用条件：要求无限次探索所有状态与联合动作的组合以及每个状态s下博弈的过程存在最优点或鞍点
全局最优策略：每个智能体都达到最大的期望回报，没有任何一个智能体能够获得更大的回报
鞍点：任何一个智能体偏离策略$\pi$时，其他所有的智能体都能获得更高的期望回报
更新方式：采用纳什价值进行更新，即$Valu{e}_i({\Gamma }_{s^{\prime }})$，$v^{Nash}(s)=[v_{\pi \ast }^1(s),\dots ,v_{\pi \ast }^N(s)]$

2.Correlated Q-Learning

适用范围：一般和博弈的随机博弈过程
条件：目前无已知的限制条件
优势（相比Nash Q-learning）：更大的解空间，能够带来更高的收益；通过线性规划高效计算标准博弈，二次规划计算纳什均衡
修改：相关均衡中的联合策略不能分解成每个智能体的单独策略，也就不能根据每个智能体的策略采用相应的动作，相反，相关均衡直接从策略中采用联合动作，每个智能体根据联合动作采取对应的动作，为了保证智能体动作之间的相关性，添加中心机制用于采用联合动作以及发送给每个智能体对于的动作

三、JAL的限制

问题：是否在任何的一般和博弈过程中构建一个联合动作函数都能收敛到均衡策略
两种性质：
1.$Q_j$是状态s决定的，与历史状态以及联合动作无关，并且联合策略是$Q_j$决定的，因此也是由此刻的状态决定的，这样的均衡称为稳定的
2.给定一种情况，在一个状态s下，只有一个智能体具有多个动作能选择，而其他智能体只有一个动作能选择，那么在任何均衡的情况下，都会促使这一个智能体选择回报最大的动作
例子：在turn-taking过程中，根据上面的两个性质，JAL算法会学习一个稳定的确定性联合策略(“Stationary Deterministic Equilibrium”)，而turn-taking并不存在此策略，其具有特定的稳定性概率策略

总结

记录MARL基础算法中的JAL-GT算法