保守策略梯度与策略改进

Conservative Policy Gradient and Policy Improvement

摘要: 本文在双人非合作马尔科夫博弈模型下，引入了一种策略度量指标，将保守策略推广到了双智能体情形，给出了一种保守策略梯度和策略改进的条件。这为双人非合作博弈中寻找保守策略下的纳什均衡提供了一定基础和改进方向。

Abstract: In this paper, a policy metric is introduced under the two-player non-cooperative Markov game model, which generalizes the conservative policy to the two-agent case, and gives a conservative policy gradient and the conditions for policy improvement. This provides a certain foundation and improvement direction for finding Nash equilibrium under policy in two-player non-cooperative game.

1. 引言

强化学习(RL)已取得了有希望的实证进展，包括掌握围棋博弈[1]，扑克博弈[2]，实时策略博弈[3]，和机器人控制[4]，值得注意的是，其中许多成功都属于多智能体强化学习(MARL)领域。MARL是关于在共享环境中交互的多个智能体，每个智能体都旨在最大化自己的长期奖励。在学习过程中，每个智能体不仅需要识别环境动态，还需要与其他智能体竞争/合作。

MARL的一个重要子领域是非合作下的多智能体博弈。随机博弈(SG)已用于对多智能体系统进行建模。然而，大多数现有工作考虑了完全合作的情景[5]或代理之间可以进行特定通信的设置。考虑到自动驾驶汽车等系统及其与行人的交互，很明显，一些多智能体系统是部分合作的，甚至是竞争性的，在许多情况下，智能体之间无法建立通信连接。更重要的是，在这些系统中，智能体选择他们的策略时知道其他智能体也以相同的意识水平选择他们的策略。

另外，大多数工作考虑了非合作的一种特例–零和博弈[6]-[8]，然而在很多场景也存在一些非合作的情况，因此本文考虑了双人非合作马尔科夫博弈模型，在该模型下，给出了价值函数定义，策略度量指标，并给出保守策略梯度和梯度改进条件，为进一步寻找保守策略下的纳什均衡提供了一定的方向。

在双人非合作马尔科夫博弈中，两个智能体通过各自的策略在动态系统中相互作用，其目标是最大化各自的长期累积收益。该模型广泛应用于复杂系统中的决策优化问题，例如市场竞争中的资源分配、智能交通中的车辆协同控制，以及网络对抗中的安全策略制定。

2. 模型描述与预备知识

博弈论可以分为合作博弈和非合作博弈。合作博弈从决策者策略互动可能的结果出发，并规定一个合适的“解”所应满足的性质——特别是对决策者联盟(coalition)具有如“稳定”或“公平”的性质，从而预测博弈结果，决策者之间交流协商，寻求合作。非合作博弈注重从单个决策者的策略选择出发，详细规定各决策者策略互动的过程和影响，一般通过均衡概念把个体最优化决策加总，从而预测博弈结果，决策者之间互不交流单独决策，但对均衡有一致预期。

2.1. 双人非合作马尔可夫博弈

双人非合作马尔科夫博弈是一种在不完全信息和动态环境中进行决策的模型。在这一模型中，两个参与者在每个时间点根据当前状态选择策略，旨在最大化各自的收益。与传统博弈论不同，马尔科夫博弈考虑了状态的转移概率，这使得博弈的结果不仅依赖于当前的策略选择，还受到历史状态的影响。

双人非合作马尔可夫博弈(TNCMG)将单智能体马尔可夫决策过程(MDP)推广到双智能体情况。在本文中，我们考虑了一个有限视野折扣的双人非合作马尔可夫博弈，并介绍了其正式定义，如下所示。

定义1. 一个有限视野的双人非合作马尔可夫博弈由以下元组定义：

$ℳ=\left\{\mathcal{N},\mathcal{S},\mathcal{A},ℬ,T,P,{\left\{r^i\right\}}_{i\in \mathcal{N}},\gamma \right\}$

• $\mathcal{N}$ ：玩家集合$\left\{1,2\right\}$ 。

• $\mathcal{S}$ ：两个玩家共享环境的状态集合。

• $\mathcal{A}$ ：第一个玩家的动作集合。

• $ℬ$ ：第二个玩家的动作集合。

• T：视野长度。

• $\left\{0,1,\cdots ,T-1\right\}$ ：决策时刻集合，表示必须做出决策的时间点集合。当上下文明确时，我们可以将其写作$\left[T\right]$ 。

• $P=\left(P_0,P_1,\cdots ,P_{T-1}\right)$ ：转移模型，其中$P_t:\mathcal{S}\times \mathcal{A}\times ℬ\to \Delta \left(\mathcal{S}\right),\forall t\in \left[T\right]$ 表示时间步t的(未知的)转移概率矩阵。

• $r^i=\left(r_0^i,r_1^i,\cdots ,r_{T-1}^i\right),r_t^i:\mathcal{S}\times \mathcal{A}\times ℬ\to \left[0,1\right],\forall t\in \left[T\right]$ 表示(未知的)确定性奖励函数，它会为第i个玩家返回一个标量值。

• $\gamma \in \left[0,1\right)$ ：表示折扣因子，它决定了未来奖励的现值。

本文关注的是状态空间$\left|\mathcal{S}\right|$ ，动作空间$\left|\mathcal{A}\right|,\left|ℬ\right|$ 和时间长度T都是有限的情况。在这个背景下，这个博弈可以按顺序描述如下：在每个时间步t，环境处于状态$s_t$ ，两个玩家同时执行他们的动作，这些动作随后都被双方知晓。如果第一个玩家在时间步t选择动作$a_t$ ，第二个玩家选择$b_t$ ，那么两个玩家的联合动作会使环境转移到下一个状态$s_{t+1}~P_t\left(\cdot |s_t,a_t,b_t\right)$ ，同时环境会为每个玩家确定一个即时奖励$r_t^i\left(s_t,a_t,b_t\right)$ 。

定义2. 在TNCMG中，一个策略由$\pi =\left(\mu ,\nu \right)$ 定义，其中

• $\mu :=\left({\mu }_0,{\mu }_1,\cdots ,{\mu }_{T-1}\right),{\mu }_t:\mathcal{S}\to \Delta \left(\mathcal{A}\right),\forall t\in \left[T\right]$ 是第一个玩家的策略，其中$\Delta \left(\mathcal{A}\right)$ 是动作集$\mathcal{A}$ 上的概率单纯形。

• $\nu :=\left({\nu }_0,{\nu }_1,\cdots ,{\nu }_{T-1}\right),{\nu }_t:\mathcal{S}\to \Delta \left(ℬ\right),\forall t\in \left[T\right]$ 是第二个玩家的策略，其中$\Delta \left(ℬ\right)$ 是动作集$ℬ$ 上的概率单纯形。其中${\mu }_t(\cdot )$ 和${\nu }_t(\cdot )$ 通常被称为决策规则(decision rules)。

定义3 [9]. 策略$\pi$ 在马尔可夫过程$ℳ$ 及初始状态为$s_0$ 的情况下，会生成一个关于序列

$\tau =\left(s_0,a_0,b_0,r_0^1,r_0^2,\cdots ,s_{T-1},a_{T-1},b_{T-1},r_{T-1}^1,r_{T-1}^2,s_T\right)$

的概率分布：

$\mathrm{Pr}\left(\tau |\pi ,s_0,ℳ\right):={\pi }_0\left(a_0,b_0|s_0\right){\displaystyle \prod _{t=0}^{T-2}{P}_t}\left(s_{t+1}|s_t,a_t,b_t\right){\pi }_{t+1}\left(a_{t+1},b_{t+1}|s_{t+1}\right)\times P_{T-1}\left(s_T|s_{T-1},a_{T-1},b_{T-1}\right)$

其中${\pi }_t\left(a_t,b_t|s_t\right)={\mu }_t\left(a_t|s_t\right){\nu }_t\left(b_t|s_t\right)$ 。

类似地，对于序列${\tau }_t=\left(s_t,a_t,b_t,\cdots ,s_{T-1},a_{T-1},b_{T-1},s_T\right)$ 的概率分布可定义为：

$\mathrm{Pr}\left({\tau }_t|\pi ,s_t,ℳ\right):={\pi }_t\left(a_t,b_t|s_t\right){\displaystyle \prod _{\iota =t}^{T-2}{P}_{\iota }}\left(s_{\iota +1}|s_{\iota },a_{\iota },b_{\iota }\right){\pi }_{\iota +1}\left(a_{\iota +1},b_{\iota +1}|s_{\iota +1}\right)\times P_{T-1}\left(s_T|s_{T-1},a_{T-1},b_{T-1}\right)$

定义4. 设$ℳ$ 是一个视野长度为T的TNCMG，t是$ℳ$ 中的时间步，对于与$ℳ$ 相关的策略$\pi =\left(\mu ,\nu \right)$ ，第i个玩家($i\in \mathcal{N}$ )的t时刻的状态价值函数$V_{\pi ,t,ℳ}^i\left(s\right)$ 和状态–动作价值函数$Q_{\pi ,t,ℳ}^i\left(s,a,b\right)$ 定义分别如下：

$V_{\pi ,t,ℳ}^i\left(s\right):=\left(1-\gamma \right){\mathbb{E}}_{\left(s_t,a_t,b_t,\cdots ,s_T\right)~\mathrm{Pr}\left(\cdot |\pi ,s_t=s,ℳ\right)}\left[{\displaystyle \sum _{\iota =t}^{T-1}{\gamma }^{\iota -t}}{r}_{\iota }^i\left(s_{\iota },a_{\iota },b_{\iota }\right)\right]$ (2.1)

$Q_{\pi ,t,ℳ}^i\left(s,a,b\right):=\left(1-\gamma \right)r_t^i\left(s,a,b\right)+\gamma {\mathbb{E}}_{s^{\prime }~P_t\left(\cdot |s,a,b\right)}\left[V_{\pi ,t+1,ℳ}^i\left(s^{\prime }\right)\right]$ (2.2)

容易验证$V_{\pi ,t,ℳ}^i\left(s\right)={\mathbb{E}}_{\left(a,b\right)~{\pi }_t\left(\cdot |s\right)}\left[Q_{\pi ,t,ℳ}^i\left(s,a,b\right)\right]$ 。当上下文明确$ℳ$ 时，我们可以省略。有关价值函数和根据上述概率分布的事件的更多详细信息，请参阅文献[10]和[11]。

定义5. 设$ℳ,t,\pi$ 的定义与上述相同。对于第i个玩家，策略$\pi$ 关于状态–动作$\left(s,a,b\right)$ 在时间步长t的优势函数$A_{\pi ,t}^i\left(s,a,b\right)$ 定义如下：

$A_{\pi ,t}^i\left(s,a,b\right):=Q_{\pi ,t}^i\left(s,a,b\right)-V_{\pi ,t}^i\left(s\right),i\in \mathcal{N}.$ (2.3)

注：基于上述价值函数的定义可以知道，优势函数$A_{\pi ,t}^i\left(s,a,b\right)\in \left[0,1\right]$ 。此外，它反映了一个动作对相对于其他动作对的相对优势。

2.2. 策略度量指标

对于任意状态分布$\rho =\left({\rho }_0,{\rho }_1,\cdots ,{\rho }_{T-1}\right)$ ，其中${\rho }_t\in \Delta \left(\mathcal{S}\right)$ ，我们引入以下定义：

定义6. 设$ℳ,t,\pi$ 的定义与上述相同，对于每个玩家$i\in \mathcal{N}$ ，称

$V_{\pi ,t}^i\left(\rho \right):={\mathbb{E}}_{s~{\rho }_t}\left[V_{\pi ,t}^i\left(s\right)\right]$ (2.4)

为状态分布$\rho$ 下的平均价值函数。

如果一个策略被表示为一个函数，则通常使用$V_{\pi ,0}^i\left(\rho \right)$ 来衡量策略的优劣。该策略度量指标可用于量化和比较不同策略的有效性。通过计算不同策略下的平均价值函数，可以比较各策略的效果，从而选择最优策略。在智能体学习过程中，策略度量指标用于评估和改进学习策略，以最大化长期回报。通过计算平均价值函数，玩家能够更好地理解在特定状态分布下策略的表现，从而做出更明智的决策。总的来说，策略度量指标有助于量化和比较策略效果，为玩家提供决策依据，在博弈论和强化学习中都有广泛应用。因此，本文采用该指标来衡量保守策略的效果。当上下文清楚时，将其简写为$V_{\pi }^i\left(\rho \right)$ 。

3. 保守策略下的策略梯度与策略改进

本节将在[11]的基础上，将单人的保守策略推广到TNCMG中，并给出保守策略梯度和这种策略下的策略改进的条件。

3.1. 保守策略

我们的目标是基于分布$\rho$ 优化策略，并使用性能指标$V_{\pi }\left(\rho \right)$ 。考虑到我们是在双人非合作博弈，我们希望避免对新策略${\pi }^{\prime }$ 进行贪婪更新，因为这可能会导致价值的严重高估。因此，我们通过采用更保守的更新规则来抑制该指标。

$\begin{array}{l}{\mu }_{\text{new}}\left(a|s,\alpha \right)=\left(1-\alpha \right)\mu \left(a|s\right)+\alpha {\mu }^{\prime }\left(a|s\right),\\ {\nu }_{\text{new}}\left(b|s,\beta \right)=\left(1-\beta \right)\nu \left(b|s\right)+\beta {\nu }^{\prime }\left(b|s\right),\end{array}$ (3.1)

其中${\pi }^{\prime }=\left({\mu }^{\prime },{\nu }^{\prime }\right)$ ，$\alpha ,\beta \in \left[0,1\right]$ 。

注：类似于[3]中的方法，TNCMG在每次迭代中也将策略更新为先前策略和贪婪策略之间的混合分布。

3.2. 策略梯度

下面考虑关于参数$\alpha ,\beta$ 的策略梯度。

引理1. 在定义4的前提下，对于$i\in \mathcal{N}$ ，有

$V_{\pi ,t,ℳ}^i\left(s\right)={\mathbb{E}}_{\left(a,b\right)~{\pi }_t\left(\cdot |s\right)}\left[Q_{\pi ,t,ℳ}^i\left(s,a,b\right)\right]$ (3.2)

证明：对于$\left(s,a,b\right)\in \mathcal{S}\times \mathcal{A}\times ℬ$ ，有

$\begin{array}{l}{\mathbb{E}}_{\left(a,b\right)~{\pi }_t\left(\cdot |s\right)}\left[Q_{\pi ,t,ℳ}^i\left(s,a,b\right)\right]\\ ={\mathbb{E}}_{\left(a,b\right)~{\pi }_t\left(\cdot |s\right)}\left[\left(1-\gamma \right)r_t^i\left(s,a,b\right)+\gamma {\mathbb{E}}_{s^{\prime }~P_t\left(\cdot |s,a,b\right)}\left[V_{\pi ,t+1,ℳ}^i\left(s^{\prime }\right)\right]\right]\\ =\left(1-\gamma \right){\mathbb{E}}_{\left(a,b\right)~{\pi }_t\left(\cdot |s\right)}\left[r_t^i\left(s,a,b\right)\right]+\gamma {\mathbb{E}}_{\left(a,b\right)~{\pi }_t\left(\cdot |s\right)}{\mathbb{E}}_{s^{\prime }~P_t\left(\cdot |s,a,b\right)}\left[V_{\pi ,t+1,ℳ}^i\left(s^{\prime }\right)\right]\\ ={\mathbb{E}}_{\left(a,b\right)~{\pi }_t\left(\cdot |s\right)}\left[r_t^i\left(s,a,b\right)\right]+\gamma {\mathbb{E}}_{\left(a,b\right)~{\pi }_t\left(\cdot |s\right)}{\mathbb{E}}_{s^{\prime }~P_t\left(\cdot |s,a,b\right)}\left[V_{\pi ,t+1,ℳ}^i\left(s^{\prime }\right)\right]-\gamma {\mathbb{E}}_{\left(a,b\right)~{\pi }_t\left(\cdot |s\right)}\left[r_t^i\left(s,a,b\right)\right]\\ =\gamma {\mathbb{E}}_{\left(a,b\right)~{\pi }_t\left(\cdot |s\right)}{\mathbb{E}}_{s^{\prime }~P_t\left(\cdot |s,a,b\right)}\left[\left(1-\gamma \right){\mathbb{E}}_{\left(s_{t+1},a_{t+1},b_{t+1},\cdots ,s_T\right)~\mathrm{Pr}\left(\cdot |\pi ,s_{t+1}=s^{\prime }\right)}\left({\displaystyle \sum _{\iota =t+1}^{T-1}{\gamma }^{\iota -\left(t+1\right)}}{r}_{\iota }^i\right)\right]\\ +{\mathbb{E}}_{\left(a,b\right)~{\pi }_t\left(\cdot |s\right)}\left[r_t^i\left(s,a,b\right)\right]-\gamma {\mathbb{E}}_{\left(a,b\right)~{\pi }_t\left(\cdot |s\right)}\left[r_t^i\left(s,a,b\right)\right]\\ ={\mathbb{E}}_{\left(s_t,a_t,b_t,\cdots ,s_T\right)~\mathrm{Pr}\left(\cdot |\pi ,s_t=s\right)}\left({\displaystyle \sum _{\iota =t+1}^{T-1}{\gamma }^{\iota -t}}{r}_{\iota }^i\right)-{\mathbb{E}}_{\left(s_t,a_t,b_t,\cdots ,s_T\right)~\mathrm{Pr}\left(\cdot |\pi ,s_t=s\right)}\left({\displaystyle \sum _{\iota =t+1}^{T-1}{\gamma }^{\iota -t+1}}{r}_{\iota }^i\right)\\ +{\mathbb{E}}_{\left(a,b\right)~{\pi }_t\left(\cdot |s\right)}\left[r_t^i\left(s,a,b\right)\right]-\gamma {\mathbb{E}}_{\left(a,b\right)~{\pi }_t\left(\cdot |s\right)}\left[r_t^i\left(s,a,b\right)\right]\\ ={\mathbb{E}}_{\left(s_t,a_t,b_t,\cdots ,s_T\right)~\mathrm{Pr}\left(\cdot |\pi ,s_t=s\right)}\left({\displaystyle \sum _{\iota =t}^{T-1}{\gamma }^{\iota -t}}{r}_{\iota }^i\right)-\gamma {\mathbb{E}}_{\left(s_t,a_t,b_t,\cdots ,s_T\right)~\mathrm{Pr}\left(\cdot |\pi ,s_t=s\right)}\left({\displaystyle \sum _{\iota =t}^{T-1}{\gamma }^{\iota -t}}{r}_{\iota }^i\right)\\ =V_{\pi ,t,ℳ}^i\left(s\right)\end{array}$

定理1. 设$ℳ$ 是一个视野长度为T的TNCMG，t是$ℳ$ 中的时间步，对于与$ℳ$ 相关的策略$\pi =\left(\mu ,\nu \right)$ 和${\pi }^{\prime }=\left({\mu }^{\prime },{\nu }^{\prime }\right)$ 是与$ℳ$ 有关的策略。对于$\alpha ,\beta \in \left[0,1\right]$ ，在更新策略下，有

${{\nabla }_{\alpha }{V}_{{\pi }_{\text{new}}}^1\left(\rho \right)|}_{\alpha =0}={\mathbb{A}}_{\left(\mu ,{\nu }_{\text{new}}\right)}^1\left(\rho ,\left({\mu }^{\prime },{\nu }_{\text{new}}\right)\right)$ (3.3)

${{\nabla }_{\beta }{V}_{{\pi }_{\text{new}}}^2\left(\rho \right)|}_{\beta =0}={\mathbb{A}}_{\left({\mu }_{\text{new}},\nu \right)}^2\left(\rho ,\left({\mu }_{\text{new}},{\nu }^{\prime }\right)\right)$ (3.4)

其中

${\mathbb{A}}_{\left(\mu ,{\nu }_{\text{new}}\right)}^1\left(\rho ,\left({\mu }^{\prime },{\nu }_{\text{new}}\right)\right)={\mathbb{E}}_{s_0~{\rho }_0}\left\{{\displaystyle \sum _{t=0}^{T-1}{\gamma }^t}{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|\left(\mu ,{\nu }_{\text{new}}\right),s_0\right)}{\mathbb{E}}_{\left(a,b\right)~\left({{\mu }^{\prime }}_t,{\nu }_{\text{new},t}\right)}\left[A_{\left(\mu ,{\nu }_{\text{new}}\right),t}^1\left(s,a,b\right)\right]\right\}$ (3.5)

${\mathbb{A}}_{\left({\mu }_{\text{new}},\nu \right)}^2\left(\rho ,\left({\mu }_{\text{new}},{\nu }^{\prime }\right)\right)={\mathbb{E}}_{s_0~{\rho }_0}\left\{{\displaystyle \sum _{t=0}^{T-1}{\gamma }^t}{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|\left({\mu }_{\text{new}},\nu \right),s_0\right)}{\mathbb{E}}_{\left(a,b\right)~\left({\mu }_{\text{new},t},{{\nu }^{\prime }}_t\right)}\left[A_{\left({\mu }_{\text{new}},\nu \right),t}^2\left(s,a,b\right)\right]\right\}$ (3.6)

证明：首先，根据引理1，对于任意的$s\in \mathcal{S},t<T$

$\begin{array}{l}{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\nabla }_{\alpha }{V}_{{\pi }_{\text{new}},t}^1\left(s\right)\right]\\ ={\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\nabla }_{\alpha }{\mathbb{E}}_{\left(a,b\right)~{\pi }_{\text{new},t}\left(\cdot |s,\alpha ,\beta \right)}\left[Q_{{\pi }_{\text{new}},t}^1\left(s,a,b\right)\right]\right]\\ ={\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\displaystyle \sum _{a,b}\left({\nabla }_{\alpha }{\pi }_{\text{new},t}\left(a,b|s,\alpha ,\beta \right)\right)Q_{{\pi }_{\text{new}},t}^1\left(s,a,b\right)}+{\displaystyle \sum _{a,b}{\pi }_{\text{new},t}}\left(a,b|s,\alpha ,\beta \right){\nabla }_{\alpha }{Q}_{{\pi }_{\text{new}},t}^1\left(s,a,b\right)\right]\\ ={\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\displaystyle \sum _{a,b}\left({\nabla }_{\alpha }{\mu }_{\text{new},t}\left(a|s,\alpha \right)\right){\nu }_{\text{new},t}\left(b|s,\beta \right)Q_{{\pi }_{\text{new}},t}^1\left(s,a,b\right)}\right]\\ +{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\displaystyle \sum _{a,b}{\mu }_{\text{new},t}}\left(a|s,\alpha \right){\nu }_{\text{new},t}\left(a|s,\alpha \right){\nabla }_{\alpha }{Q}_{{\pi }_{\text{new}},t}^1\left(s,a,b\right)\right]\\ ={\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\displaystyle \sum _{a,b}\left({\nabla }_{\alpha }{\mu }_{\text{new},t}\left(a|s,\alpha \right)\right){\nu }_{\text{new},t}\left(b|s,\beta \right)Q_{{\pi }_{\text{new}},t}^1\left(s,a,b\right)}\right]\\ +{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}{\mathbb{E}}_{\left(a,b\right)~{\pi }_{\text{new},t}\left(\cdot |s,\alpha ,\beta \right)}\left[{\nabla }_{\alpha }\left(\left(1-\gamma \right)r_t^1\left(s,a,b\right)+\gamma {\mathbb{E}}_{s^{\prime }~P_t\left(\cdot |s,a,b\right)}{V}_{{\pi }_{\text{new}},t+1}^1\left(s^{\prime }\right)\right)\right]\\ ={\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\displaystyle \sum _{a,b}\left({\nabla }_{\alpha }{\mu }_{\text{new},t}\left(a|s,\alpha \right)\right){\nu }_{\text{new},t}\left(b|s,\beta \right)Q_{{\pi }_{\text{new}},t}^1\left(s,a,b\right)}\right]\\ +\gamma {\mathbb{E}}_{s~\mathrm{Pr}\left(s_{t+1}=s|{\pi }_{\text{new}},s_0\right)}\left[{\nabla }_{\alpha }{V}_{{\pi }_{\text{new}},t+1}^1\left(s\right)\right]\end{array}$

其次，由于${\nabla }_{\alpha }{V}_{{\pi }_{\text{new}}}^1\left(s_0\right)={\mathbb{E}}_{s~\mathrm{Pr}\left(s_0=s\text{|}{\pi }_{\text{new}},s_0\right)}\left[{\nabla }_{\alpha }{V}_{{\pi }_{\text{new}}}^1\left(s\right)\right]$ ，对前面的等式进行递归，并利用$V_{\pi ,T}=0$ 对于所有$\pi$ ，可以得到

${\nabla }_{\alpha }{V}_{{\pi }_{\text{new}}}^1\left(s_0\right)={\displaystyle \sum _{t=0}^{T-1}{\gamma }^t}{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\displaystyle \sum _{a,b}\left({\nabla }_{\alpha }{\mu }_{\text{new},t}\left(a|s,\alpha \right)\right){\nu }_{\text{new},t}\left(b|s,\beta \right)Q_{{\pi }_{\text{new},t}}^1\left(s,a,b\right)}\right]$

根据(2.4)，有

$\begin{array}{c}{\nabla }_{\alpha }{V}_{{\pi }_{\text{new}}}^1\left(\rho \right)={\mathbb{E}}_{s_0~{\rho }_0}\left[{\nabla }_{\alpha }{V}_{\text{new}}^1\left(s_0\right)\right]\\ ={\mathbb{E}}_{s_o~{\rho }_0}\left[{\displaystyle \sum _{t=0}^{T-1}{\gamma }^t}{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}{\displaystyle \sum _{a,b}\left({\nabla }_{\alpha }{\mu }_{\text{new},t}\left(a|s,\alpha \right)\right){\nu }_{\text{new},t}\left(b|s,\beta \right)Q_{{\pi }_{\text{new},t}}^1\left(s,a,b\right)}\right]\end{array}$ (3.7)

根据更新规则(3.1)，有

$\begin{array}{l}{{\displaystyle \sum _{a,b}\left[\left({\nabla }_{\alpha }{\mu }_{\text{new},t}\left(a|s,\alpha \right)\right){\nu }_{\text{new},t}\left(b|s,\beta \right)Q_{{\pi }_{\text{new},t}}^1\left(s,a,b\right)\right]}|}_{\alpha =0}\\ ={\displaystyle \sum _{a,b}\left({{\mu }^{\prime }}_t\left(a|s\right)-{\mu }_t\left(a|s\right)\right){\nu }_{\text{new},t}\left(b|s,\beta \right)Q_{\left(\mu ,{\nu }_{\text{new}}\right),t}^1\left(s,a,b\right)}\\ ={\displaystyle \sum _{a,b}\left({{\mu }^{\prime }}_t\left(a|s\right)-{\mu }_t\left(a|s\right)\right){\nu }_{\text{new},t}\left(b|s,\beta \right)A_{\left(\mu ,{\nu }_{\text{new}}\right),t}^1\left(s,a,b\right)}\\ ={\mathbb{E}}_{\left(a,b\right)~\left({{\mu }^{\prime }}_t,{\nu }_{\text{new},t}\right)}\left[A_{\left(\mu ,{\nu }_{\text{new}}\right),t}^1\left(s,a,b\right)\right]\end{array}$ (3.8)

最后，将(3.8)式代入到(3.7)式有

$\begin{array}{l}{{\nabla }_{\alpha }{V}_{{\pi }_{\text{new}}}^1\left(\rho \right)|}_{\alpha =0}={\mathbb{E}}_{s_0~{\rho }_0}\left\{{\displaystyle \sum _{t=0}^{T-1}{\gamma }^t}{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|\left(\mu ,{\nu }_{\text{new}}\right),s_0\right)}{\mathbb{E}}_{\left(a,b\right)~\left({{\mu }^{\prime }}_t,{\nu }_{\text{new},t}\right)}\left[A_{\left(\mu ,{\nu }_{\text{new}}\right),t}^1\left(s,a,b\right)\right]\right\}\\ ={\mathbb{E}}_{s_0~{\rho }_0}\left\{{\displaystyle \sum _{t=0}^{T-1}{\gamma }^t}{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|\left(\mu ,{\nu }_{\text{new}}\right),s_0\right)}{\mathbb{E}}_{\left(a,b\right)~\left({{\mu }^{\prime }}_t,{\nu }_{\text{new},t}\right)}\left[A_{\left(\mu ,{\nu }_{\text{new}}\right),t}^1\left(s,a,b\right)\right]\right\}\\ ={\mathbb{A}}_{\left(\mu ,{\nu }_{\text{new}}\right)}^1\left(\rho ,\left({\mu }^{\prime },{\nu }_{\text{new}}\right)\right)\end{array}$ (3.9)

类似地，可以证明${{\nabla }_{\beta }{V}_{{\pi }_{\text{new}}}^2\left(\rho \right)|}_{\beta =0}={\mathbb{A}}_{\left({\mu }_{\text{new}},\nu \right)}^2\left(\rho ,\left({\mu }_{\text{new}},{\nu }^{\prime }\right)\right)$ ，为了篇幅限制，证明放在附录。

注：该定理说明，对于玩家1的策略梯度，状态空间上的期望是关于$\left(\mu ,{\nu }_{\text{new}}\right)$ 诱导的，而动作空间上的期望是关于策略$\left({\mu }^{\prime },{\nu }_{\text{new}}\right)$ ，对于玩家2的策略梯度，状态空间上的期望是关于$\left({\mu }_{\text{new}},\nu \right)$ 诱导的，而动作空间上的期望是关于策略$\left({\mu }_{\text{new}},{\nu }^{\prime }\right)$ 。

3.3. 策略改进

定理2. 在定理1的设定和保守更新策略(3.1)下，如果满足条件：

${\mathbb{A}}_{\left(\mu ,{\nu }_{\text{new}}\right)}^1\left(\rho ,\left({\mu }^{\prime },{\nu }_{\text{new}}\right)\right)>0\text{and}{\mathbb{A}}_{\left({\mu }_{\text{new}},\nu \right)}^2\left(\rho ,\left({\mu }_{\text{new}},{\nu }^{\prime }\right)\right)>0$ (3.10)

则策略${\pi }_{\text{new}}$ 可以在足够小的$\alpha$ 和$\beta$ 下得到改进。

证明：该定理可以由定理1直接得出。

注：该定理说明智能体在足够小的$\alpha$ 和$\beta$ 下可以使得自身的价值函数得到提升，在实际应用中我们一般设置一个比较小的平滑值$\epsilon$ ，使得

${\mathbb{A}}_{\left(\mu ,{\nu }_{\text{new}}\right)}^1\left(\rho ,\left({\mu }^{\prime },{\nu }_{\text{new}}\right)\right),{\mathbb{A}}_{\left({\mu }_{\text{new}},\nu \right)}^2\left(\rho ,\left({\mu }_{\text{new}},{\nu }^{\prime }\right)\right)\le \epsilon$

时停止更新策略。

4. 结论与展望

本文将单智能体下的保守策略方式推广到双智能体，在双人非合作马尔科夫博弈的模型下，引入了策略度量指标，给出了一种保守策略梯度和策略改进条件，给出了双人非合作马尔科夫博弈的一种策略改进方式和方向，为之后寻找纳什均衡奠定了一定的基础和方向，其中关键定理指出，玩家1的策略更新在状态空间上取决于策略$\left(\mu ,{\nu }_{\text{new}}\right)$ ，在动作空间上取决于$\left({\mu }^{\prime },{\nu }_{\text{new}}\right)$ ；玩家2的策略更新在状态空间上取决于策略$\left({\mu }_{\text{new}},\nu \right)$ ，在动作空间上取决于$\left({\mu }_{\text{new}},{\nu }^{\prime }\right)$ 。另外，由于保守策略不易导致价值函数高估，因此未来的工作将考虑在离线强化学习中的应用，探索在离线强化学习中是否保守策略能有效降低价值函数高估问题，并尝试找出达到纳什均衡所需的样本复杂度。

附 录

下面证明${{\nabla }_{\beta }{V}_{{\pi }_{\text{new}}}^2\left(\rho \right)|}_{\beta =0}={\mathbb{A}}_{\left({\mu }_{\text{new},\nu }\right)}^2\left(\rho ,\left({\mu }_{\text{new}},{\nu }^{\prime }\right)\right)$

首先，对于任意的$s\in \mathcal{S},t<T$

$\begin{array}{l}{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\nabla }_{\beta }{V}_{{\pi }_{\text{new}},t}^2\left(s\right)\right]\\ ={\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\nabla }_{\beta }{\mathbb{E}}_{\left(a,b\right)~{\pi }_{\text{new},t}\left(\cdot |s,\alpha ,\beta \right)}\left[Q_{{\pi }_{\text{new}},t}^2\left(s,a,b\right)\right]\right]\\ ={\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\displaystyle \sum _{a,b}\left({\nabla }_{\beta }{\pi }_{\text{new},t}\left(a,b|s,\alpha ,\beta \right)\right)Q_{{\pi }_{\text{new}},t}^2\left(s,a,b\right)}+{\displaystyle \sum _{a,b}{\pi }_{\text{new},t}}\left(a,b|s,\alpha ,\beta \right){\nabla }_{\beta }{Q}_{{\pi }_{\text{new}},t}^2\left(s,a,b\right)\right]\\ ={\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\displaystyle \sum _{a,b}{\mu }_{\text{new},t}\left(a|s,\alpha \right)}\left({\nabla }_{\beta }{\nu }_{\text{new},t}\left(b|s,\beta \right)\right)Q_{{\pi }_{\text{new}},t}^2\left(s,a,b\right)\right]\\ +{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\displaystyle \sum _{a,b}{\mu }_{\text{new},t}}\left(a|s,\alpha \right){\nu }_{\text{new},t}\left(a|s,\alpha \right){\nabla }_{\beta }{Q}_{{\pi }_{\text{new}},t}^2\left(s,a,b\right)\right]\\ ={\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\displaystyle \sum _{a,b}{\mu }_{\text{new},t}\left(a|s,\alpha \right)}\left({\nabla }_{\beta }{\nu }_{\text{new},t}\left(b|s,\beta \right)\right)Q_{{\pi }_{\text{new}},t}^2\left(s,a,b\right)\right]\\ +{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}{\mathbb{E}}_{\left(a,b\right)~{\pi }_{\text{new},t}\left(\cdot |s,\alpha ,\beta \right)}\left[{\nabla }_{\beta }\left(\left(1-\gamma \right)r_t^2\left(s,a,b\right)+\gamma {\mathbb{E}}_{s^{\prime }~P_t\left(\cdot |s,a,b\right)}{V}_{{\pi }_{\text{new}},t+1}^2\left(s^{\prime }\right)\right)\right]\\ ={\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\displaystyle \sum _{a,b}{\mu }_{\text{new},t}\left(a|s,\alpha \right)}\left({\nabla }_{\beta }{\nu }_{\text{new},t}\left(b|s,\beta \right)\right)Q_{{\pi }_{\text{new}},t}^2\left(s,a,b\right)\right]\\ +\gamma {\mathbb{E}}_{s~\mathrm{Pr}\left(s_{t+1}=s|{\pi }_{\text{new}},s_0\right)}\left[{\nabla }_{\beta }{V}_{{\pi }_{\text{new}},t+1}^2\left(s\right)\right]\end{array}$

其次，由于${\nabla }_{\beta }{V}_{{\pi }_{\text{new}}}^2\left(s_0\right)={\mathbb{E}}_{s~\mathrm{Pr}\left(s_0=s\text{|}{\pi }_{\text{new}},s_0\right)}\left[{\nabla }_{\beta }{V}_{{\pi }_{\text{new}}}^2\left(s\right)\right]$ ，对前面的等式进行递归，并利用$V_{\pi ,T}=0$ 对于所有$\pi$ ，可以得到

${\nabla }_{\beta }{V}_{{\pi }_{\text{new}}}^2\left(s_0\right)={\displaystyle \sum _{t=0}^{T-1}{\gamma }^t}{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}\left[{\displaystyle \sum _{a,b}{\mu }_{\text{new},t}\left(a|s,\alpha \right)}\left({\nabla }_{\beta }{\nu }_{\text{new},t}\left(b|s,\beta \right)\right)Q_{{\pi }_{\text{new},t}}^2\left(s,a,b\right)\right]$

根据(2.4)，有

$\begin{array}{c}{\nabla }_{\beta }{V}_{{\pi }_{\text{new}}}^2\left(\rho \right)={\mathbb{E}}_{s_0~{\rho }_0}\left[{\nabla }_{\beta }{V}_{\text{new}}^2\left(s_0\right)\right]\\ ={\mathbb{E}}_{s_0~{\rho }_0}\left[{\displaystyle \sum _{t=0}^{T-1}{\gamma }^t}{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|{\pi }_{\text{new}},s_0\right)}{\displaystyle \sum _{a,b}{\mu }_{\text{new},t}\left(a|s,\alpha \right){\nabla }_{\beta }{\nu }_{\text{new},t}}\left(b|s,\beta \right)Q_{{\pi }_{\text{new},t}}^2\left(s,a,b\right)\right]\end{array}$

根据更新规则(3.1)，有

$\begin{array}{l}{{\displaystyle \sum _{a,b}\left[{\mu }_{\text{new},t}\left(a|s,\alpha \right){\nabla }_{\beta }{\nu }_{\text{new},t}\left(b|s,\beta \right)Q_{{\pi }_{\text{new},t}}^2\left(s,a,b\right)\right]}|}_{\beta =0}\\ ={\displaystyle \sum _{a,b}{\mu }_{\text{new},t}\left(a|s,\alpha \right)\left({{\nu }^{\prime }}_t\left(b|s\right)-{\nu }_t\left(b|s\right)\right)Q_{\left({\mu }_{\text{new}},\nu \right),t}^2\left(s,a,b\right)}\\ ={\displaystyle \sum _{a,b}{\mu }_{\text{new},t}\left(a|s,\alpha \right)\left({{\nu }^{\prime }}_t\left(b|s\right)-{\nu }_t\left(b|s\right)\right)}{A}_{\left({\mu }_{\text{new}},\nu \right),t}^2\left(s,a,b\right)\\ ={\mathbb{E}}_{\left(a,b\right)~\left({\mu }_{\text{new},t},{{\nu }^{\prime }}_t\right)}\left[A_{\left({\mu }_{\text{new}},\nu \right),t}^2\left(s,a,b\right)\right]\end{array}$

最后，结合上面两个式子可以得到：

$\begin{array}{l}{{\nabla }_{\beta }{V}_{{\pi }_{\text{new}}}^2\left(\rho \right)|}_{\beta =0}={\mathbb{E}}_{s_o~{\rho }_0}\left\{{\displaystyle \sum _{t=0}^{T-1}{\gamma }^t}{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|\left({\mu }_{\text{new}},\nu \right),s_0\right)}{\mathbb{E}}_{\left(a,b\right)~\left({\mu }_{\text{new},t},{{\nu }^{\prime }}_t\right)}\left[A_{\left({\mu }_{\text{new}},\nu \right),t}^2\left(s,a,b\right)\right]\right\}\\ ={\mathbb{E}}_{s_o~{\rho }_0}\left\{{\displaystyle \sum _{t=0}^{T-1}{\gamma }^t}{\mathbb{E}}_{s~\mathrm{Pr}\left(s_t=s|\left({\mu }_{\text{new}},\nu \right),s_0\right)}{\mathbb{E}}_{\left(a,b\right)~\left({\mu }_{\text{new},t},{{\nu }^{\prime }}_t\right)}\left[A_{\left({\mu }_{\text{new}},\nu \right),t}^2\left(s,a,b\right)\right]\right\}\\ ={\mathbb{A}}_{\left({\mu }_{\text{new}},\nu \right)}^2\left(\rho ,\left({\mu }_{\text{new}},{\nu }^{\prime }\right)\right)\end{array}$