Stochastic Game / Markov Game

随机博弈 / 马尔可夫博弈

基础定义

多个智能体在同一个环境进行的交互可以被建模为一个随机博弈过程：

组成元素	数学定义	组成元素	数学定义
智能体集合	$\mathcal{N} = \{ 1,\ 2,\ \cdots,\ n \}$	联合动作空间	$\mathcal{A} = \mathcal{A}^{1} \times \mathcal{A}^{2} \times \cdots \times \mathcal{A}^{n}$
状态空间	$\mathcal{S}$	智能体 $i$ 的奖励函数	$\mathcal{R}^{i} : \mathcal{S} \times \mathcal{A} \mapsto \mathbb{R}$
智能体 $i$ 的动作空间	$\mathcal{A}^{i}$	状态转移概率	$\mathcal{P} : \mathcal{S} \times \mathcal{A} \times \mathcal{S} \mapsto [0,\ 1]$

每个智能体在环境状态的基础上进行决策，不同的智能体拥有不同的独立的策略：

$\pi_{1}(\cdot \mid \cdot) : \mathcal{S} \times \mathcal{A}^{1} \mapsto [0,\ 1] \quad \pi_{2}(\cdot \mid \cdot) : \mathcal{S} \times \mathcal{A}^{2} \mapsto [0,\ 1] \quad \cdots \quad \pi_{n}(\cdot \mid \cdot) : \mathcal{S} \times \mathcal{A}^{n} \mapsto [0,\ 1]$

环境状态的转移取决于当前状态 $s_{t}$ 以及联合动作 $a_{t} = \{ a_{t}^{1},\ a_{t}^{2},\ \cdots,\ a_{t}^{n} \}$，联合策略可以表示为：

$\pi(a_{t} \mid s_{t}) = \pi(a_{t}^{1},\ a_{t}^{2},\ \cdots,\ a_{t}^{n} \mid s_{t}) = \prod_{i = 1}^{n} \pi_{i}(a_{t}^{i} \mid s_{t})$

在随机博弈下，每个智能体的目标是最大化各自的累计奖励：

$J_{i}(\pi) = \mathcal{E}_{s_{0} \sim b_{0}(\cdot)} \mathcal{E}_{a_{0} \sim \pi(\cdot \mid s_{0})} \mathcal{E}_{s_{1} \sim p(\cdot \mid s_{0},\ a_{0})} \mathcal{E}_{a_{1} \mid \pi(\cdot \mid s_{1})} \cdots \mathcal{E}_{s_{\mathrm{T}} \sim p(\cdot \mid s_{\mathrm{T} - 1},\ a_{\mathrm{T} - 1})} \mathcal{E}_{a_{\mathrm{T}} \sim \pi(\cdot \mid s_{\mathrm{T}})} \left[ \sum_{t = 0}^{\mathrm{T}} \gamma^{t} \mathcal{R}^{i}(s_{t},\ a_{t}) \right]$

类似地，定义每个智能体的动作价值函数以及状态价值函数：

$\begin{gathered} q_{i}^{(t)}(s_{t},\ a_{t} \mid \pi) = \mathcal{E}_{s_{t + 1} \sim p(\cdot \mid s_{t},\ a_{t})} \mathcal{E}_{a_{t + 1} \sim \pi(\cdot \mid s_{t + 1})} \cdots \mathcal{E}_{s_{\mathrm{T}} \sim p(\cdot \mid s_{\mathrm{T} - 1},\ a_{\mathrm{T} - 1})} \mathcal{E}_{a_{\mathrm{T}} \sim \pi(\cdot \mid s_{\mathrm{T}})} \left[ \sum_{\tau = t}^{\mathrm{T}} \gamma^{\tau - t} \mathcal{R}^{i}(s_{\tau},\ a_{\tau}) \right] \\[7mm] v_{i}^{(t)}(s_{t} \mid \pi) = \mathcal{E}_{a_{t} \sim \pi(\cdot \mid s_{t})} \mathcal{E}_{s_{t + 1} \sim p(\cdot \mid s_{t},\ a_{t})} \mathcal{E}_{a_{t + 1} \sim \pi(\cdot \mid s_{t + 1})} \cdots \mathcal{E}_{s_{\mathrm{T}} \sim p(\cdot \mid s_{\mathrm{T} - 1},\ a_{\mathrm{T} - 1})} \mathcal{E}_{a_{\mathrm{T}} \sim \pi(\cdot \mid s_{\mathrm{T}})} \left[ \sum_{\tau = t}^{\mathrm{T}} \gamma^{\tau - t} \mathcal{R}^{i}(s_{\tau},\ a_{\tau}) \right] \end{gathered}$

推广到无限期规划下：

$\begin{gathered} q_{i}(s_{t},\ a_{t} \mid \pi) = \mathcal{E}_{s_{t + 1} \sim p(\cdot \mid s_{t},\ a_{t})} \mathcal{E}_{a_{t + 1} \sim \pi(\cdot \mid s_{t + 1})} \mathcal{E}_{s_{t + 2} \sim p(\cdot \mid s_{t + 1},\ a_{t + 1})} \mathcal{E}_{a_{t + 2} \sim \pi(\cdot \mid s_{t + 2})} \cdots \left[ \sum_{\tau = t}^{\infty} \gamma^{\tau - t} \mathcal{R}^{i}(s_{\tau},\ a_{\tau}) \right] \\[7mm] v_{i}(s_{t} \mid \pi) = \mathcal{E}_{a_{t} \sim \pi(\cdot \mid s_{t})} \mathcal{E}_{s_{t + 1} \sim p(\cdot \mid s_{t},\ a_{t})} \mathcal{E}_{a_{t + 1} \sim \pi(\cdot \mid s_{t + 1})} \mathcal{E}_{s_{t + 2} \sim p(\cdot \mid s_{t + 1},\ a_{t + 1})} \mathcal{E}_{a_{t + 2} \sim \pi(\cdot \mid s_{t + 2})} \cdots \left[ \sum_{\tau = t}^{\infty} \gamma^{\tau - t} \mathcal{R}^{i}(s_{\tau},\ a_{\tau}) \right] \end{gathered}$

在以上定义下，每个智能体的动作价值函数和状态价值函数仍然满足贝尔曼期望方程。

系统设定

多智能体强化学习下对于智能体的奖励函数的一些特殊关系设定如下：

设定	描述
完全合作关系	所有智能体的利益一致，获得的奖励相同，有共同的目标
完全竞争关系	一方的收益是另一方的损失，双方奖励负相关，零和博弈下奖励总和为 0
合作竞争混合	智能体分为多个群组，组内为合作关系，组间为竞争关系

在多智能体下，策略学习收敛的标志是所有智能体的平均回报不再变化，达到纳什均衡，形式化的定义为：

$\forall\ s \in \mathcal{S}\ \forall\ i \in \mathcal{N} : v_{i}(s \mid \pi_{1}^{\star},\ \cdots,\ \pi_{i}^{\star},\ \cdots,\ \pi_{n}^{\star}) = \max_{\pi_{i}} v_{i}(s \mid \pi_{1}^{\star},\ \cdots,\ \pi_{i},\ \cdots,\ \pi_{n}^{\star})$

即在任意状态 $s$ 下，任意智能体 $i$ 做出单方面的策略更改无法获得更高的期望回报。可以证明，在参与者、动作空间和状态空间有限时，随机博弈存在静态随机策略的纳什均衡（proof）。

策略梯度

在参数化的策略下，每个智能体的策略 $\pi_{i}$ 的参数为 $\theta_{i}$，每个智能体的目标函数对其策略参数的梯度为：

$\begin{aligned} \nabla_{\theta_{i}} J_{i}(\theta_{i}) &= \nabla_{\theta_{i}} \sum_{s_{0}} \sum_{a_{0}} \sum_{s_{1}} \sum_{a_{1}} \cdots \sum_{s_{\mathrm{T}}} \sum_{a_{\mathrm{T}}} \left[ b_{0}(s_{0}) \prod_{j = 1}^{n} \prod_{t = 0}^{\mathrm{T}} \pi_{j}(a_{t}^{j} \mid s_{t};\ \theta_{j}) \prod_{t = 1}^{\mathrm{T}} p(s_{t} \mid s_{t - 1},\ a_{t - 1}) \sum_{t = 0}^{\mathrm{T}} \gamma^{t} \mathcal{R}^{i}(s_{t},\ a_{t}) \right] \\[7mm] &= \mathcal{E}_{s_{0}} \mathcal{E}_{a_{0}} \mathcal{E}_{s_{1}} \mathcal{E}_{a_{1}} \cdots \mathcal{E}_{s_{\mathrm{T}}} \mathcal{E}_{a_{\mathrm{T}}} \left[ \left( \sum_{t = 0}^{\mathrm{T}} \nabla_{\theta_{i}} \ln \pi_{i}(a_{t}^{i} \mid s_{t};\ \theta_{i}) \right) \cdot \left( \sum_{t = 0}^{\mathrm{T}} \gamma^{t} \mathcal{R}^{i}(s_{t},\ a_{t}) \right) \right] \end{aligned}$

考虑乘积因子 $\nabla_{\theta_{i}} \ln \pi_{i}(a_{t}^{i} \mid s_{t},\ \theta_{i}) \mathcal{R}^{i}(s_{\tau},\ a_{\tau})$ 在 $t > \tau$ 时的期望为：

$\mathcal{E}_{s_{0}} \mathcal{E}_{a_{0}} \mathcal{E}_{s_{1}} \mathcal{E}_{a_{1}} \cdots \mathcal{E}_{s_{\mathrm{T}}} \mathcal{E}_{a_{\mathrm{T}}} \Big[ \nabla_{\theta_{i}} \ln \pi_{i}(a_{t}^{i} \mid s_{t},\ \theta_{i}) \mathcal{R}^{i}(s_{\tau},\ a_{\tau}) \Big] = \mathcal{E}_{s_{0}} \mathcal{E}_{a_{0}} \mathcal{E}_{s_{1}} \mathcal{E}_{a_{1}} \cdots \mathcal{E}_{s_{t}} \mathcal{E}_{a_{t}} \Big[ \nabla_{\theta_{i}} \ln \pi_{i}(a_{t}^{i} \mid s_{t},\ \theta_{i}) \mathcal{R}^{i}(s_{\tau},\ a_{\tau}) \Big]$

其中：

$\begin{aligned} \mathcal{E}_{a_{t}} \Big[ \nabla_{\theta_{i}} \ln \pi_{i}(a_{t}^{i} \mid s_{t},\ \theta_{i}) \mathcal{R}^{i}(s_{\tau},\ a_{\tau}) \Big] = \mathcal{R}^{i}(s_{\tau},\ a_{\tau}) \mathcal{E}_{a_{t}} \nabla_{\theta_{i}} \ln \pi_{i}(a_{t}^{i} \mid s_{t},\ \theta_{i}) = \mathcal{R}^{i}(s_{\tau},\ a_{\tau}) \mathcal{E}_{a_{t}^{i}} \nabla_{\theta_{i}} \ln \pi_{i}(a_{t}^{i} \mid s_{t},\ \theta_{i}) = 0 \end{aligned}$

因此所有 $t > \tau$ 的乘积因子项均为 0，策略梯度简化为：

$\begin{aligned} \nabla_{\theta_{i}} J_{i}(\theta_{i}) &= \mathcal{E}_{s_{0}} \mathcal{E}_{a_{0}} \mathcal{E}_{s_{1}} \mathcal{E}_{a_{1}} \cdots \mathcal{E}_{s_{\mathrm{T}}} \mathcal{E}_{a_{\mathrm{T}}} \left[ \sum_{t = 0}^{\mathrm{T}} \nabla_{\theta_{i}} \ln \pi_{i}(a_{t}^{i} \mid s_{t},\ \theta_{i}) \sum_{\tau = t}^{\mathrm{T}} \gamma^{\tau} \mathcal{R}^{i}(s_{t},\ a_{t}) \right] \\[7mm] &= \mathcal{E}_{s_{0}} \mathcal{E}_{a_{0}} \mathcal{E}_{s_{1}} \mathcal{E}_{a_{1}} \cdots \mathcal{E}_{s_{t}} \mathcal{E}_{a_{t}} \Bigg[ \sum_{t = 0}^{\mathrm{T}} \nabla_{\theta_{i}} \ln \pi_{i}(a_{t}^{i} \mid s_{t},\ \theta_{i}) \cdot \gamma^{t} \underset{q_{i}^{(t)}(s_{t},\ a_{t})}{\underbrace{\mathcal{E}_{s_{t + 1}} \mathcal{E}_{a_{t + 1}} \cdots \mathcal{E}_{s_{\mathrm{T}}} \mathcal{E}_{a_{\mathrm{T}}} \sum_{\tau = t}^{\mathrm{T}} \gamma^{\tau - t} \mathcal{R}^{i}(s_{\tau},\ a_{\tau})}} \Bigg] \\[10mm] &= \sum_{t = 0}^{\mathrm{T}} \gamma^{t} \mathcal{E}_{s_{0}} \mathcal{E}_{a_{0}} \mathcal{E}_{s_{1}} \mathcal{E}_{a_{1}} \cdots \mathcal{E}_{s_{t}} \mathcal{E}_{a_{t}} \Big[ \nabla_{\theta_{i}} \ln \pi_{i}(a_{t}^{i} \mid s_{t},\ \theta_{i}) q_{i}^{(t)}(s_{t},\ a_{t}) \Big] \end{aligned}$

类似地，可以在策略梯度中加入基线函数来降低估计的方差：

$\nabla_{\theta_{i}} J_{i}(\theta_{i}) = \sum_{t = 0}^{\mathrm{T}} \gamma^{t} \mathcal{E}_{s_{0}} \mathcal{E}_{a_{0}} \mathcal{E}_{s_{1}} \mathcal{E}_{a_{1}} \cdots \mathcal{E}_{s_{t}} \mathcal{E}_{a_{t}} \Big[ \nabla_{\theta_{i}} \ln \pi_{i}(a_{t}^{i} \mid s_{t},\ \theta_{i}) \Big( q_{i}^{(t)}(s_{t},\ a_{t}) - b \Big) \Big]$

其中基线函数 $b$ 不依赖于 $a_{t} = \{ a_{t}^{1},\ a_{t}^{2},\ \cdots,\ a_{t}^{n} \}$，一般将基线函数设置为状态价值函数 $v_{i}^{(t)}(s_{t})$。