多智能体交互建模

对多智能体交互的建模主要用到博弈论的内容，本篇主要介绍建模部分。
本篇将会详细介绍标准形式的博弈(Normal-Form Games)、随机博弈(Stochastic Games)、部分可观测随机博弈(Partially Observable Stochastic Game)以及马尔可夫决策过程(Markov Decision Process)。
首先来看一张图，这张图阐明了这些内容之间的关系，我们将会从最基础的标准形式的博弈开始讲解。
注意：文中的翻译不一定准确，对于关键术语，会附上英文

Normal-Form Games

标准形式的博弈定义了两个或多个智能体之间的一次交互。

定义

一个标准形式的博弈由以下几部分构成：

• 有限的智能体数量$I=1,2,...,n$
• 对于每一个智能体$i\in I$ :
  有限的动作$A_i$
  奖励函数$R_i:A\to R_i$,这里的$A$是一个联合动作

过程

一个标准形式的过程：首先每一个智能体$i\in I$选择一个策略$\pi :A_i\to [0,1]$，然后所有智能体的动作就会构成一个联合动作$a=(a_1,a_2,...a_n)$，我们这里假定所有智能体动作是同时做出的，然后每一个智能体就会根据自己的奖励函数得到一个奖励$r_i=R_i(a)$,注意这里的奖励函数$R_i$可以看作是每一个智能体独有的，并不一定是一样的。
标准形式的博弈可以根据各个智能体奖励函数之间的关系分为以下三类：

• 零和博弈，这种形式的博弈满足所有智能体的奖励之和为0。如果是两个智能体$i,j$之间的零和博弈，则此时两者的奖励函数满足$R_i+R_j=0$,即$R_i=-R_j$。
• 奖励相同的博弈（common-reward game),翻译的可能有问题，这种博弈指的是每一个智能体的奖励函数是相同的，即所有智能体获得的奖励是相同的，这在多智能体合作任务中，$R_i=R_j=R_k=...=R_n$,貌似见的比较多。
• 一般形式的博弈（general-sum game),这种形式的博弈，各个智能体之间的奖励函数并没有明显的关系，可以理解为每一个智能体有一个单独的奖励函数。
  两个智能体组成的标准形式的博弈又可以叫做矩阵博弈，相信你可以想象出来，囚徒困境的例子就是一个很好的标准形式的博弈。看图：
  
  我们可以这样理解上面的图片：现在有两个智能体，这两个智能体需要同时给出一个动作，他们可选的动作有$R,P,S$,当两个智能体根据自己的策略$\pi$给出动作后，就会形成一个联结动作,比如$a=(R,P)$,表示第一个智能体做出动作R,第二个智能体做出动作P，这个时候这两个智能体就会根据自己的奖励函数，根据联结动作得到奖励，看上图可知，第一个智能体得到了奖励-1，第二个智能体得到了奖励1.不难发现上图其实表示的是一种零和博弈。

Repeated Normal-Form Games

这个标题可以翻译为重复标准形式的博弈，那就很好理解了，就是将上面标准形式的博弈重复嘛，可以是有限次，也可以是无限次。书上说，这种形式的博弈模型在博弈论里面研究的最多，因为涉及到了重复，那就会设计到时间的概念，比如$t_1$进行一次标准形式的博弈，$t_2$进行一次标准形式的博弈，$t_3$…,这样我们就可以把它叫做时序多智能体交互。换句话说，可以将时序多智能体交互建模为重复标准形式的博弈。
注意：此时还没有涉及到状态的概念。
过程简述：在每一个时间步$t$,每一个智能体从$\pi (a^t|h^t)$里采样一个动作，这里的$h^t$表示的联结动作的历史记录$h^t=(a^0,a^1,...,a^{t-1})$,每一个智能体在$t$时刻根据$h^t$做出动作之后，就会得到$t$时刻的奖励。
对于有限和无限次重复，这里还涉及到了折扣因子的问题，不展开讨论，后面讲解强化学习的时候会重点介绍。

Stochastic Games

翻译为随机博弈，前面的标准形式的博弈和重复标准形式的博弈均没有涉及到状态的概念，对于多智能体之间的交互，往往还会涉及到环境的状态，即智能体不仅仅根据其他智能体的历史动作做出决策，还要考虑环境的状态，所以这里引入随机博弈的模型可以更好的描述多智能体之间的交互。

定义

• 有限的智能体数量$I=1,...n$
• 有限的状态$S$,以及终止状态$\bar{S}\subset S$是$S$的子集
• 对于每一个智能体$i\in I$:
  有限的动作空间$A_i$
  奖励函数$R_i:SXAXS\to R$,这里$A=A_{1}X{A}_{2}X...X{A}_n$
• 状态转移函数$T:SXAXA\to [0,1]$概率和为1
• 初始状态分布：$\mu :S\to [0,1]$,概率和为1，但是初始状态为终止状态的概率为0.

过程

随机博弈过程：博弈开始于一个由$\mu$采集的初始状态$so\in S$,在时间$t$,每一个智能体根据当前观测$s^t$以及先前的观测和动作，根据策略$\pi (a^t|h^t)$做出动作，$h^t=(s_0,a_0,...a_{t-1},s_t)$,因为所有信息都是可以观测的，所以被称为完全观测的博弈。当所有智能体做出动作后，此时形成了一个联合动作$a^t$,根据状态转移函数$T(s^{t+1}|s^t,a^t)$转移到新的状态$s^{t+1}$,并且对于智能体$i$接收奖励$r_i=R_i(s^t,a^t,s^{t+1})$,一直持续，直到进入终止状态或者达到指定的步数。
在随机博弈中，因为状态转移函数和奖励函数都具有马尔科夫性，所以随机博弈又叫做马尔可夫博弈。
马尔科夫性可以用下面的公式来表述：
$Pr(s^{t+1},r^t|s^t,a^t,s^{t-1},a^{t-1},...s^0,a^0)=Pr(s^{t+1},r^t|s^t,a^t)$
即下一时刻的状态至于这一时刻的状态和动作有关，与前面时刻的状态和动作无关。这一时刻的状态已经包含了前面的影响。

Partiallly Observable Stochastic Games

部分可观测随机博弈，又可以叫做部分可观测马尔可夫博弈。
这里的部分可观测指的是智能体只能获得不完整的环境状态信息和其他智能体之前动作的信息。主打一个不完整！
这使得智能体必须依靠不完整的信息去做出决策，如果想通过不完整的信息做出最优决策，往往可能性不大，所以就需要对不完整的信息进行处理，比如利用历史信息去推测出一个完整的信息。首先介绍以下部分可观测随机博弈的定义。

定义

部分可观测随机博弈和随机博弈的定义很相似，不同点在于对于每一个智能体，额外添加下面两条：

• 有限的观测集：$O_i$
• 观测函数$O_i:AXSX{O}_i\to [0,1]$,对于$\forall a\in A,s\in S:{\sum }_{o_i\in O_i}{O}_i(a,s,o_i)=1$
  部分可观测随机博弈的过程与随机博弈相似，不同点在于每一个智能体在做出决策时依据的$h^t$不同，因为是部分观测，所以只能根据部分观测来做出决策，即$h_i^t=(o_i^0,o_i^1,...,o_i^t)$,需要注意，在$t$时刻的观测至于当前时刻的状态$s^t$,$a^{t-1}$有关,即$o_i^t=O_i(a^{t-1},s^t)$.
  对于POSG，当然也可以分类为零和博弈，奖励相同的博弈以及一般博弈，这里奖励相同的博弈又可以称为“Decentralised POMDP",简写为Dec-POMDP,.

这里对观测函数进行进一步的讨论，观测函数既可以包括有限的传感器感知信息，又可以包括无法观测的其他智能体的动作，还可以包括由于通信限制而无法得到有效信息的情况，当然还有观测到的信息含有噪声的情况。

置信状态和滤波

我们说，要做出最优决策，只有部分观测肯定是不够的，那能否利用历史的部分观测信息在当前时刻尽可能多的得到真实的状态信息呢？答案是肯定的，可以由下面的贝叶斯后验分布来表示：
$b_i^{t+1}\propto {\sum }_{s\in S}{b}_i^{t}T(s^{\prime }|s,a^{\prime })O_i(o_i^{t+1}|a_i^t,s^{\prime })$
但是这种方法的空间复杂度和时间复杂度都太高。所以发展有效的滤波算法也是一个研究方向。
深度强化学习算法一般利用循环神经网络去处理时序观察，可以从历史观测中提取有效信息。

博弈论中的条件假设

在博弈论中，标准假设是智能体指导所有定义出来的信息，比如在标准形式的博弈中，智能体知道所有智能体的动作空间和奖励。对于POSG，智能体知道状态空间和状态转移函数，以及所有智能体的观测函数。这样的假设在现实世界的稍微复杂的应用中很难成立，所以现在利用MARL通过与环境进行交互，进而通过经验构建未知的成分，比如状态转移函数。