Constrained Policy Optimization

---

简单介绍CMDP: 在 MDP 的基础上，CMDP 设置了一系列约束回报函数，并类似 MDP 的回报函数，CMDP 对每个约束回报进行了折现，要求所有策略的这些折现值不超过对应的阈值。至于最优化目标，CMDP 依旧是采用的 MDP 的折现回报最大化。

带约束的策略优化: 策略搜索算法能够有效处理维度较大或连续的 MDP 问题，其本质就是在现有策略的邻域范围内搜索让目标函数值更优的策略。在 CMDP 中，策略优化要求评估新搜索出的新策略是否满足约束，这显然难以实现。

一、研究背景

​ 现有的强化学习算法着眼于算法的收敛性能，并被证明在训练过程中会放任智能体进行一些完全自由的尝试。在基于现实场景的训练中，这可能会带来一些安全问题。比如，无人机的自由探索可能导致昂贵设备的损坏、工厂机械臂在训练过程中会对附近工人造成潜在安全威胁。

​ 不妨把安全问题转换为约束条件，很容易想到使用带约束的马尔科夫决策过程（CMDP）来进行问题建模。不过，该文章发表之前还没有人提出保证在训练过程中满足约束的连续CMDP算法。

​ 对比已有工作，CPO 是第一个在训练中保障智能体时刻满足约束（尽管只是近似满足）、并能胜任包括神经网络在内任意策略类型（policy classes）的策略搜索算法（policy search algorithm）。

二、目标问题

​ CMDP 中，策略梯度算法多了关于折现约束回报函数值的约束条件，这要求算法在每次搜索新策略时进行可行性判断，但在连续的高维空间中优化该问题是很难进行更新的。一种容易想到的做法，直接使用采样来计算策略更新。但这种做法需要使用离策略（off-policy evaluation），非常具有挑战性。

​ CPO 针对的目标问题就是在 CMDP 场景下设计一种可靠的策略梯度算法，以实现高维空间的策略更新。对此，CPO 用一种更容易估计的近似函数来避免有关约束的估计问题。

​ 同时，策略采样算法往往会遇到性能崩溃（performance collapse）的问题，这往往源于不合理的更新步长设置。CPO提出一种基于 trust region 的方法（类似 TRPO），在使用近似函数简化目标的同时，又能保证整个优化过程是单调提升的。

三、核心方法

​ 约束策略优化（Constrained Policy Optimization，CPO）是一种应用于 CMDP 问题的信赖空间方法。它使用了一种容易估计的近似函数，而近似函数的更新方法一般是推出一个下界，然后优化时推高下界，从而达到优化原始问题的目的。所以，现在问题就集中在：如何得到一个下界，然后优化这个下界。

a. 策略更新性能的边界

​ TRPO 使用了一个表达式来描述新旧策略之间的差异，CPO同样基于该方法。这个表达式可以化简为：

$$J\left(\pi^{\prime}\right)-J(\pi)=\frac{1}{1-\gamma} \underset{s \sim d^{\pi^{\prime}} \atop a \sim \pi^{\prime}}{\mathrm{E}}\left[A^{\pi}(s, a)\right]\\ A^{\pi}(s, a) \doteq Q^{\pi}(s, a)-V^{\pi}(s)\\ d^{\pi}(s)=(1-\gamma) \sum_{t=0}^{\infty} \gamma^{t} P\left(s_{t}=s \mid \pi\right)$$

​ 上式中，$J(\pi)$ 是目标函数，$\pi^\prime$ 与 $\pi$ 代表新旧两种策略，$\gamma$ 是折现因子，$A^{\pi}(s, a)$ 是优势函数，$d^{\pi}(s)$ 是 discounted future state distribution。通过基于TV散度的推导，CPO 得到了下面所示的更新前后目标差值的下界与约束差值的上界：

$$J\left(\pi^{\prime}\right)-J(\pi)\geq \frac{1}{1-\gamma} \underset{s \sim d^{\pi} \atop a \sim \pi^{\prime}}{\mathrm{E}}\left[A^{\pi}(s, a)-\frac{2 \gamma \epsilon^{\pi^\prime}}{1-\gamma} D_{T V}\left(\pi^{\prime} \| \pi\right)[s]\right] \\ J_{C_{i}}\left(\pi^{\prime}\right)-J_{C_{i}}(\pi)\leq \frac{1}{1-\gamma} \underset{s \sim d^{\pi} \atop a \sim \pi^{\prime}}{\mathrm{E}}\left[A_{C_{i}}^{\pi}(s, a)+\frac{2 \gamma \epsilon_{C_{i}}^{\pi^{\prime}}}{1-\gamma} D_{T V}\left(\pi^{\prime} \| \pi\right)[s]\right]$$

​ 其中 $D_{T V}\left(\pi^{\prime} \| \pi\right)[s]=(1 / 2) \sum_{a}\left|\pi^{\prime}(a \mid s)-\pi(a \mid s)\right|$ 是状态 $s$ 处不同行为 $a$ 间的 total variational divergence。需要注意的是，CPO 使用 $d^{\pi}$ 处的 $(1-\gamma)^{-1} \mathrm{E}_{s \sim d^{\pi}, a \sim \pi^{\prime}}\left[A^{\pi}(s, a)\right]$ 来近似 $s$ 的采样过程，而 $a$ 可以直接使用重要性采样获得，这和 TRPO 的思想是一致的。CPO 将这种边界视为描述最坏情况的近似误差，这也是一次策略更新性能的最小边界。接下来，我们只需要最大化这个边界就能保证策略更新的单调提升。（此处的更新性能指的就是新旧两次策略间目标函数值的差值大小）

b. 信任空间方法

​ 通过 Pinsker 不等式，对任意分布 $ p, q $，TV散度和KL散度之间满足 $ D_{T V}(p | q) \leq \sqrt{D_{K L}(p | q) / 2} $，因此可以得到：

$$\begin{aligned} \underset{s \sim d^{\pi}}{\mathrm{E}}\left[D_{T V}\left(\pi^{\prime} \| \pi\right)[s]\right] & \leq \underset{s \sim d^{\pi}}{\mathrm{E}}\left[\sqrt{\frac{1}{2} D_{K L}\left(\pi^{\prime} \| \pi\right)[s]}\right] \\ & \leq \sqrt{\frac{1}{2} \underset{s \sim d^{\pi}}{\mathrm{E}}\left[D_{K L}\left(\pi^{\prime} \| \pi\right)[s]\right]} \end{aligned}$$

​ 观察上下界方程，看到下界中TV散度是负系数，上界中是正系数，于是就能用KL散度替代TV散度，得到近似：

$$\underset{s \sim d^{\pi}}{\mathrm{E}}\left[D_{T V}\left(\pi^{\prime} \| \pi\right)[s]\right] \rightarrow \sqrt{\frac{1}{2} \underset{s \sim d^{\pi}}{\mathrm{E}}\left[D_{K L}\left(\pi^{\prime} \| \pi\right)[s]\right]}$$

​ 整合上述推论，得到CPO最基本的策略迭代方程：

$$\pi_{k+1}=\arg \max _{\pi \in \Pi_{\theta}} \underset{s \sim d^{\pi_{k}} \atop a \sim \pi}{\mathrm{E}}\left[A^{\pi_{k}}(s, a)\right] \\ s.t. \bar{D}_{K L}\left(\pi || \pi_{k}\right) \leq \delta$$

​ 其中，$ \bar{D}{K L}\left(\pi | \pi\right)=\mathrm{E}{s \sim \pi{k}}\left[D_{K L}\left(\pi | \pi_{k}\right)[s]\right] $， $ \delta>0 $ 是更新步长，集合 $ \left{\pi_{\theta} \in \Pi_{\theta}: \bar{D}{K L}\left(\pi | \pi\right) \leq \delta\right} $ 是 trust region。可以看到，优化目标是最大化优势函数的均值，这正是使用前面介绍的下界对新旧策略差值进行的近似。CPO通过控制新策略与旧策略之间的距离，让新策略来自信赖域中，以确保使用来自旧策略的采样能够有效近似新策略，保证了性能的单调提升。

c. 基于信任空间的CMDP优化问题

​ 实际上，前面对单调提升的更新性能保证会使更新步长过小，CPO提出了一种基于信任空间的有实践意义的近似方法。

​ 通过引入合适的参数 $\alpha_k$、$\beta_k$，基于前述更新差值的下界与约束差值的上界，可以整理出以下优化方程：

$$\begin{aligned} &\pi_{k+1}=\arg \max _{\pi \in \Pi_{\theta}} \underset{s \sim d^{\pi_{k}} \atop a \sim \pi}{\mathrm{E}}\left[A^{\pi_{k}}(s, a)\right]-\alpha_{k} \sqrt{\bar{D}_{K L}\left(\pi \| \pi_{k}\right)} \\ &\text { s.t. } J_{C_{i}}\left(\pi_{k}\right)+\underset{s \sim d^{\pi_{k}} \atop a \sim \pi}{\mathrm{E}}\left[\frac{A_{C_{i}}^{\pi_{k}}(s, a)}{1-\gamma}\right]+\beta_{k}^{i} \sqrt{\bar{D}_{K L}\left(\pi \| \pi_{k}\right)} \leq d_{i} \end{aligned}$$

​ 上述优化方程是很“紧”的，因此该问题通常是可行的。然而，当折扣因子（discount factors）接近 1 时，对策略差异（Policy Divergence，KL项）的惩罚会变得相当严峻，此时更新步长可能会很小。

​ 受置信区间方法的启发，CPO 使用置信区间代替对策略差异的惩罚，以实现更大的更新步长：

$$\begin{aligned} \pi_{k+1}=& \arg \max _{\pi \in \Pi_{\theta}} \underset{s \sim d^{\pi_{k}} \atop a \sim \pi}{\mathrm{E}}\left[A^{\pi_{k}}(s, a)\right] \\ \text { s.t. } & J_{C_{i}}\left(\pi_{k}\right)+\frac{1}{1-\gamma} \underset{s \sim d^{\pi_{k}} \atop a \sim \pi}{\mathrm{E}}\left[A_{C_{i}}^{\pi_{k}}(s, a)\right] \leq d_{i} \quad \forall i \\ & \bar{D}_{K L}\left(\pi \| \pi_{k}\right) \leq \delta \end{aligned} \tag{10}$$

​ CPO 的思想类似 TRPO 用目标函数的惩罚项（KL散度项）来代替对两种策略间距离的度量，二者都是为了找到合适的更新步长。

d. 近似求解 CPO 更新过程

​ CPO 的似处理跟 TRPO 一样，对目标函数和约束函数做泰勒展开，得到一个简化后的目标函数。其中，对优势函数的期望值进行一阶展开获得其策略梯度，对KL散度进行二阶展开获得FIM。重新整理公式(10)，得到新的优化方程：

$$\begin{aligned} \theta_{k+1}=\arg \max _{\theta} & g^{T}\left(\theta-\theta_{k}\right) \\ \text { s.t. } & c_{i}+b_{i}^{T}\left(\theta-\theta_{k}\right) \leq 0 \quad i=1, \ldots, m \\ & \frac{1}{2}\left(\theta-\theta_{k}\right)^{T} H\left(\theta-\theta_{k}\right) \leq \delta \end{aligned} \tag{11}$$

​ 其中，$g$ 是目标函数的梯度，$b_i$ 是第 $i$ 个约束的梯度，这俩实际上应该是对公式(10)中对应的那一项求梯度。$H$ 是KL散度的 Hessian 矩阵，$c_i=J_{C_i}(\pi_k)-d_i$。

​ 由于KL散度的 Hessian 矩阵是半正定的，所以该问题为凸，可以转化为对偶问题：

$$\max _{\lambda \geq 0 \atop \nu \succeq 0} \frac{-1}{2 \lambda}\left(g^{T} H^{-1} g-2 r^{T} \nu+\nu^{T} S \nu\right)+\nu^{T} c-\frac{\lambda \delta}{2} \tag{12}$$

​ $c$ 是 $c_i$ 组成的列向量，$B$ 是 $b_i$ 组成的列向量，$ν$ 和 $\lambda$ 是对偶变量，$r=g^TH^{-1}B$，$S=B^TH^{-1}B$。该对偶问题的解为：

$$\theta^{*}=\theta_{k}+\frac{1}{\lambda^{*}} H^{-1}\left(g-B \nu^{*}\right) \tag{13}$$

​ 由于近似误差，CPO 可能在迭代过程中违反约束，因此文中增加了一个回退的步骤，一旦违反约束就回退一部继续搜索。CPO 使用了如公式(14)所示的回退方法，该方法的原则是通过限制搜索方向使信任区域与约束区域的交集缩小为零。说人话，就是把最小化约束当作目标，然后得到此时的 Natural Policy Gradient：

$$\theta^{*}=\theta_{k}-\sqrt{\frac{2 \delta}{b^{T} H^{-1} b}} H^{-1} b \tag{14}$$

​ 结合公式(10)~(14)，可以得到针对单一约束的 CPO 更新算法：

四、性能指标

​ CPO可以在高维约束控制任务中训练具有数千个参数的神经网络策略，同时最大化奖励和近似满足约束。

• 需要计算Fisher information matrix (FIM)
• 由于近似误差，CPO在训练过程并不能完全遵守约束
• CPO的成本趋近于限制条件而不是最小化成本
• 实验显示如果约束为原约束的上界，表现会更好
• CPO相比奖励设置为 $R+\lambda C$ 的 TRPO，通过自适应调整 $\lambda$ 可以更好的权衡奖励和成本

---

---

附录一、相关知识

a. Fisher Information Matrix

​ **费雪信息矩阵（Fisher Information Matrix, FIM）**是一个统计学中极其重要而且核心的概念，定义为 MLE 方程的二阶矩，具有两个重要数学意义：是 MLE 方程的方差、是 log likelihood 在参数真实值处的负二阶导数的期望、其逆是 MLE 渐进分布的方差。Fisher Information 反映了我们对参数估计的准确度，它越大，对参数估计的准确度越高，即代表了越多的信息。

​ 假设观察到 i.i.d 的数据 $ X_{1}, X_{2}, \ldots X_{n} $ 服从一个概率分布 $ f(X ; \theta)$，$ \theta $ 是目标参数（假设 $ \theta $ 是个标量) , 那么似然函数 (likelihood) 就是:

$$L(\mathbf{X} ; \theta)=\prod_{i=1}^{n} f\left(X_{i} ; \theta\right)$$

​ 为了解得最大似然估计量（Maximum Likelihood Estimate, MLE），我们要让 log likelihood 的一阶导数得 0，然后解该方程，得到 $ \hat{\theta}_{M L E} $，这个 log likelihood 的一阶导数也叫 Score function:

$$S(\mathbf{X} ; \theta)=\sum_{i=1}^{n} \frac{\partial \log f\left(X_{i} ; \theta\right)}{\partial \theta}$$

​ 那么 Fisher Information，用 $ I(\theta) $ 表示，的定义就是 Score function 的二阶矩 $I(\theta)=E\left[S(X ; \theta)^{2}\right] $ 。

​ 一般情况下可以很容易地证明， $ E[S(\mathbf{X} ; \theta)]=0 $，该等式可以根据积分和求导可交换的性质得到。从而得到

$$I(\theta)=E\left[S(X ; \theta)^{2}\right]-E[S(X ; \theta)]^{2}=\operatorname{Var}[S(X ; \theta)]$$

​ 因此，Fisher Information 就是 Score function 的方差。它的直观表述就是，随着收集的数据越来越多，这个方差由于是一个 Independent sum 的形式，也就变的越来越大，也就象征着得到的信息越来越多。也就是说，费雪信息反映的是观测数据携带着模型参数的信息量大小。

​ 同时，Fisher Information 也是 log likelihood 在参数真实值处的负二阶导数的期望

$$I(\theta)=E\left[S(\mathbf{X} ; \theta)^{2}\right]=-E\left(\frac{\partial^{2}}{\partial \theta^{2}} \log L(\mathbf{X} ; \theta)\right)$$

​ 这是费雪信息的一个重要性质，即在真实参数上，log likelihood 的梯度的协方差矩阵和 log likelihood 的 Hessian 相等。log likelihood 在参数真实值处的 Hessian 矩阵，反应了该 log likelihood 在 likely-p 函数图顶点处的弯曲程度，弯曲程度越大，整个log likelihood的形状就越偏向于高而窄，也就代表掌握的信息越多。

---

b. TRPO

​ TRPO 是一种基于 Minorize-Maximization 的算法，它解决了梯度下降算法在更新步长选择上的问题，从数学上证明了该方法一定能够收敛到局部最优或全局最优（而梯度下降容易陷入深渊）。

​ 参考《如何看懂TRPO里所有的数学推导细节?》一文，TRPO 的本质是找到一个对强化学习目标函数（累积折扣回报函数）的替代函数（下界函数），不断基于最新的策略找到替代函数的最优点来更新策略，从而完成算法收敛。

​ TRPO 将策略更新过程建模成了一个迭代式，以表示更新前后策略之间的差距：

$$\eta(\tilde{\pi})=\eta(\pi)+\sum_{s} \rho_{\tilde{\pi}}(s) \sum_{a} \tilde{\pi}(a \mid s) A_{\pi}(s, a)$$

​ 其中，$\tilde{\pi}$ 是更新后的新策略，$\eta(\tilde{\pi})$ 是新策略下的期望折扣奖励值，也是策略 $\tilde{\pi}$ 所对应的优化目标函数值。优势函数定义为$ A_{\pi}(s, a) = Q_{\pi}(s, a) - V_{\pi}(s)$ ，表示状态 $s$ 下选择行为 $a$ 的优越性，能评价当前动作值函数相对于平均值的大小。$\rho_{\tilde{\pi}}(s)$ 是任意时刻中状态 $s$ 的访问概率之和，展开形式表示为：

$$\rho_{\pi}(s)=P\left(s_{0}=s\right)+\gamma P\left(s_{1}=s\right)+\gamma^{2} P\left(s_{2}=s\right)+\cdots$$

​ 该式右端的 $\sum_{s} \rho_{\tilde{\pi}}(s) \sum_{a} \tilde{\pi}(a \mid s) A_{\pi}(s, a)$ 是平均折现优势 $\underset{\tau \sim \tilde{\pi}}{\mathrm{E}}\left[\sum_{t=0}^{\infty} \gamma^{t} A^{\pi}\left(s_{t}, a_{t}\right)\right]$ 化简后的结果，等式的证明过程如下：

$$\begin{array}{l} \underset{\tau \sim \tilde{\pi}}{\mathrm{E}}\left[\sum_{t=0}^{\infty} \gamma^{t} A^{\pi}\left(s_{t}, a_{t}\right)\right] \\ =\underset{\tau \sim \tilde{\pi}}{\mathrm{E}}\left[\sum_{t=0}^{\infty} \gamma^{t}\left(R\left(s_{t}, a_{t}, s_{t+1}\right)+\gamma V^{\pi}\left(s_{t+1}\right)-V^{\pi}\left(s_{t}\right)\right)\right] \\ =\eta(\tilde{\pi})+\underset{\tau \sim \tilde{\pi}}{\mathrm{E}}\left[\sum_{t=0}^{\infty} \gamma^{t+1} V^{\pi}\left(s_{t+1}\right)-\sum_{t=0}^{\infty} \gamma^{t} V^{\pi}\left(s_{t}\right)\right] \\ =\eta(\tilde{\pi})+\underset{\tau \sim \tilde{\pi}}{\mathrm{E}}\left[\sum_{t=1}^{\infty} \gamma^{t} V^{\pi}\left(s_{t}\right)-\sum_{t=0}^{\infty} \gamma^{t} V^{\pi}\left(s_{t}\right)\right] \\ =\eta(\tilde{\pi})-\underset{\tau \sim \tilde{\pi}}{\mathrm{E}}\left[V^{\pi}\left(s_{0}\right)\right] \\ =\eta(\tilde{\pi})-\eta(\pi) \end{array}$$

​ 如果能保证 $ \sum_{s} \rho_{\tilde{\pi}}(s) \sum_{a} \tilde{\pi}(a \mid s) A_{\pi}(s, a) \geq 0$，那么新策略的更新就一直是在进步的。因此，我们需要从某个策略 $ \pi $ 出发，通过计算找到一个策略 $ \tilde{\pi} $，使得 $\sum_{s} \rho_{\tilde{\pi}}(s) \sum_{a} \tilde{\pi}(a \mid s) A_{\pi}(s, a) \geq 0$，从而保证 $ \eta(\tilde{\pi}) \geq \eta(\pi) $。

​ 然而，$ \rho_{\tilde{\pi}}(s) $ 在实际中是不能直接求到的，除非我们用新策略去和环境交互，显然非常低效。于是需要去找与上述公式的近似且可解的形式，定义函数 $ \mathcal{L} $

$$\mathcal{L}_{\pi}(\tilde{\pi})=\eta(\pi)+\sum_{s} \rho_{\pi}(s) \sum_{a} \tilde{\pi}(a \mid s) A_{\pi}(s, a)$$

​ 它其实就是使用旧策略的访问概率去替换了新策略的 $\rho_{\tilde{\pi}}(s)$，只要保证更新步伐不是太大，该近似就可成立。该近似的意义在于可以直接使用旧策略来完成对状态分布的采样。

​ TRPO 定义下界函数（Bound Function）$ M = \mathcal{L}_{\pi}(\tilde{\pi}) - C * KL $。$M$ 中的第二项是 KL 散度：

$$D_{K L}(P|Q|)=\mathbb{E}_{x} \log \frac{P(x)}{Q(x)}$$

​ 因此可以把策略模型看成一个概率分布，使用KL散度表示两个分布的距离。原论文中作者用两页纸证明了 $ \boldsymbol{\eta} $ 的下界:

$$\eta\left(\pi_{n e w}\right) \geq \mathcal{L}_{\pi_{o l d}}\left(\pi_{n e w}\right)-\frac{4 \varepsilon \gamma}{(1-\gamma)^{2}} \alpha^{2}$$

​ 其中 $ \varepsilon=\max {s, a}\left|A(s, a)\right|, \quad \alpha=D_{T V}^{\max }\left(\pi_{o l d}, \pi_{n e w}\right), \quad D_{T V}^{\max }(\pi, \tilde{\pi})=\max D_{T V}(\pi(\cdot \mid s) | \tilde{\pi}(\cdot \mid s)) $ ，$ D_{T V}(p | q)=\frac{1}{2} \sum_{i}\left|p_{i}-q_{i}\right| $，$ D_{T V} $ 代表 total variation divergence。由于

$$D_{T V}(p \| q)^{2} \leq D_{K L}(p \| q)$$

​ 可以得到新的下界函数( lower bound function ):

$$\eta(\tilde{\pi}) \geq \mathcal{L}_{\pi}(\tilde{\pi})-C D_{K L}^{\max }(\pi, \tilde{\pi})$$

​ 其中 $ C=\frac{4 \varepsilon \gamma}{(1-\gamma)^{2}}, \quad D_{K L}^{\max }(\pi, \tilde{\pi})=\max {s} D(\pi(\cdot \mid s) | \tilde{\pi}(\cdot \mid s)) $。令 $ M_{i}(\pi)=\mathcal{L}{\pi{i}}(\pi)-C D_{K L}^{\max }\left(\pi_{i}, \pi\right) $，有 $ \eta\left(\pi_{i+1}\right) \geq M_{i}\left(\pi_{i+1}\right)$，$\eta\left(\pi_{i}\right)=M_{i}\left(\pi_{i}\right) $，因此$\eta\left(\pi_{i+1}\right)-\eta\left(\pi_{i}\right) \geq M_{i}\left(\pi_{i+1}\right)-M_{i}\left(\pi_{i}\right)$。则 $ \pi_{i+1}=\arg \max {\pi} M(\pi) $ 时，期望折扣奖励将在下一次迭代被提升。新的优化目标就是寻找 $ \mathcal{L}{\pi{i}}(\pi)-C D_{K L}^{\max }\left(\pi_{i}, \pi\right) $ 的上界。

​ 同时可以发现，$\mathcal{L}_{\pi}(\tilde{\pi})=\eta(\pi)+\sum_{s} \rho_{\pi}(s) \sum_{a} \tilde{\pi}(a \mid s) A_{\pi}(s, a)$ 中，$\tilde{\pi}(a \mid s)$ 与新策略有关，无法对其直接采样，因此可以使用重要性采样的方法：（后面引用原文方程，部分参数的表示方法有点出入）

$$\sum_{a} \pi_{\theta}\left(a \mid s_{n}\right) A_{\theta_{\text {old }}}\left(s_{n}, a\right)=\mathbb{E}_{a \sim q}\left[\frac{\pi_{\theta}\left(a \mid s_{n}\right)}{q\left(a \mid s_{n}\right)} A_{\theta_{\text {old }}}\left(s_{n}, a\right)\right]$$

​ 目标函数可以化简为：

$$\begin{array}{c} \underset{\theta}{\operatorname{maximize}} \mathbb{E}_{s \sim \rho_{\theta_{\text {old }}}, a \sim q}\left[\frac{\pi_{\theta}(a \mid s)}{q(a \mid s)} \hat{A}_{\theta_{\text {old }}}(s, a)\right] \\ \text { subject to } \mathbb{E}_{s \sim \rho_{\theta_{\text {old }}}}\left[D_{\mathrm{KL}}\left(\pi_{\theta_{\text {old }}}(\cdot \mid s) \| \pi_{\theta}(\cdot \mid s)\right)\right] \leq \delta \end{array}$$

​ 上式的优化目标是最大化 $\mathcal{L}_{\pi}(\tilde{\pi})$，KL散度一项作为被惩罚项当成约束处理（因为最大化目标时，要求惩罚尽可能小）。同时，和新策略无关的部分作为系数被省略，最终得到上面的简化函数式。利用拉格朗日对偶, 把约束项提到目标函数中去，以下两个数学表达等价：

$$\begin{array}{ll} \underset{\theta}{\operatorname{maximize}} & \hat{\mathbb{E}}_{t}\left[\frac{\pi_{\theta}\left(a_{t} \mid s_{t}\right)}{\pi_{\theta_{\text {old }}}\left(a_{t} \mid s_{t}\right)} \hat{A}_{t}\right] \\ \text { subject to } & \mathbb{E}_{t}\left[\mathrm{KL}\left[\pi_{\theta_{\text {old }}}\left(\cdot \mid s_{t}\right), \pi_{\theta}\left(\cdot \mid s_{t}\right)\right]\right] \leq \delta \end{array}$$

$$\underset{\theta}{\operatorname{maximize}} \quad \hat{\mathbb{E}}_{t}\left[\frac{\pi_{\theta}\left(a_{t} \mid s_{t}\right)}{\pi_{\theta_{\text {old }}}\left(a_{t} \mid s_{t}\right)} \hat{A}_{t}\right]-\beta \hat{\mathbb{E}}_{t}\left[\mathrm{KL}\left[\pi_{\theta_{\text {old }}}\left(\cdot \mid s_{t}\right), \pi_{\theta}\left(\cdot \mid s_{t}\right)\right]\right]$$

​ 我的理解是，把KL项从目标中抽出成约束，是为了在新目标函数中省掉一些不影响目标的参数或项（尤其是KL前面的系数C），最终使用拉格朗日对偶把约束合并进目标后，就变得十分简洁。

---

c. KL散度

​ KL散度（KL-divergence）就是机器学习中常说的相对熵，可以表示两个概率分布之间的差异性，通常用于评价拟合出的概率分布与真实分布之间的差距。

​ 信息熵可以用来表示数据的信息量大小。下面两式分别表示了离散型随机变量与连续型随机变量的信息熵公式：

$$H(p)=H(X)=\mathrm{E}_{x \sim p(x)}[-\log p(x)]=-\sum_{i=1}^{n} p(x) \log p(x)$$

$$H(p)=H(X)=\mathrm{E}_{x \sim p(x)}[-\log p(x)]=-\int p(x) \log p(x) d x$$

​ 通常在信息熵中， $ \log $ 是以2为底的，但是在神经网络中，一般默认以 $ e $ 为底，这样算出来的香农信息量虽然不是最小的可用于完整表示事件的比特数，但对于信息熵的含义来说是区别不大的。其实只要这个底数大于1，都能用来表达信息熵的大小。

​ 相对熵，又被称为KL散度或信息散度，是两个概率分布间差异的非对称性度量。在信息论中，相对熵等价于两个概率分布的信息熵的差值，若其中一个概率分布为真实分布，另一个为理论（拟合）分布，则此时相对熵等于交叉熵与真实分布的信息熵之差，表示使用理论分布拟合真实分布时产生的信息损耗。定义式如下：

$$D_{K L}(p \| q)=\sum_{i=1}^{N}\left[p\left(x_{i}\right) \log p\left(x_{i}\right)-p\left(x_{i}\right) \log q\left(x_{i}\right)\right]$$

​ 其中，$ p\left(x_{i}\right) $ 为真实事件的概率分布，$ q\left(x_{i}\right) $ 为理论拟合出来的该事件的概率分布。因此，该公式的字面含义就是真实事件的信息熵减去拟合事件的香农信息量与真实事件的概率的乘积的差值的求和累加值。

​ 对于 $ -\sum_{i=1}^{N} p\left(x_{i}\right) \log q\left(x_{i}\right) $ 项，当理论拟合出来的事件概率分布跟真实的一模一样，那么它就等于真实事件的信息熵，其KL散度也就为0，两个概率分布之间毫无差异。而当拟合得并不好时，该项往往会比真实事件的信息熵更小，即KL散度大于0。至此，可以得到相对熵的一个重要结论：当且仅当两个概率分布相同时，KL散度为0，否则KL散度永远大于0。

​ KL散度有一个令人头疼的特性，也就是相对熵的大小并不跟距离有一一对应的关系。比如用 $P$ 拟合 $Q$ 和用 $Q$ 拟合 $P$ 的相对熵大小不一样，导致并不好使用相对熵来调整下降的速度。不过在神经网络中，因为 $sigmoid$ 激活层的存在，均方差损失函数在函数值趋近0或1时会导致梯度消失，因此由KL散度延生的交叉熵损失函数哪怕距离特性并不优秀，也好过梯度消失。

d. 重要性采样

​ 重要性采样（Importance Sampling）是蒙特卡洛积分的一种采样策略。

​ 在解决蒙特卡洛积分时，通常会因为积分曲线难以解析，无法直接求解积分。一种直观的思路，在积分区间上进行一组采样，通过对样本值求和取平均的方式来近似积分结果：

$$\int_{a}^{b} f(x) d x=\frac{b-a}{N} \sum_{i=1}^{N} f\left(x_{i}\right)$$

​ 但如果原函数定义在一个分布 $\pi(x)$ 上，我们就不能用上述加权方法近似蒙特卡洛积分。重要性采样希望重新找到一个更加简明的分布 $p(x)$，从它进行取样，间接地求出 $f(x)$ 在分布 $\pi(x)$ 下的期望。

​ 函数 $f(x)$ 在分布 $\pi(x)$ 下的期望为： $ E[f]=\int_{x} \pi(x) f(x) d x $。在 $ p(x) $ 上采样 $ \left{x_{1}, x_{2}, \ldots, x_{n}\right} $，可以估计 $ f $ 在分布 $ p(x) $ 的期望：

$$E[f]=\int_{x} p(x) f(x) d x \approx \frac{1}{N} \sum_{i=1}^{N} f\left(x_{i}\right)$$

​ 然后将式子改写为：$ \pi(x) f(x)=p(x) \frac{\pi(x)}{p(x)} f(x) $，可以得到：

$$E[f]=\int_{x} p(x) \frac{\pi(x)}{p(x)} f(x) d x$$

​ 上式可以看作函数 $ \frac{\pi(x)}{p(x)} f(x) $ 定义在分布 $ p(x) $ 上的期望。我们可以在 $ p(x) $ 上采样 $ \left{x_{1}, x_{2}, \ldots, x_{n}\right} $，然后估计 $ f(x) $ 的期望值 $ E[f]=\frac{1}{N} \sum_{i=1}^{N} \frac{\pi\left(x_{i}\right)}{p\left(x_{i}\right)} f\left(x_{i}\right) $，这里的 $ \frac{\pi\left(x_{i}\right)}{p\left(x_{i}\right)} $ 就是重要性权重。

​ 在重要性采样中，$\pi$ 与 $p$ 的分布是已知的，否则无法计算重要性权重。重要性采样解决的问题其实是利用某种分布（这种分布能区分出被积函数不同点的重要性）更好地积分，本质上是因为现有分布 $\pi$ 不方便采样、或对函数值的配合不好才需要借用其他分布来采样。这样采样过后得到的均值方差会比较小，能够很快收敛。

e. off-policy

​ On-policy 的目标策略和行为策略是同一个策略，好处是直接利用数据就可优化其策略，但会导致策略其实是在学习一个局部最优，因为没办法很好的保持既探索又学习；而 Off-policy 将目标策略和行为策略分开，可以在保持探索的同时，更能求到全局最优值。

​ 为了能从行为策略 $ b $ 产生的样本回合（Episode）中学习目标策略 $ \pi $，要求当执行 $ b $ 策略时， $ \pi $ 中的每个动作都有一定概率发生, 也就是 $ \pi(a \mid s)>0 $ 时，必有 $ b(a \mid s)>0 $ (逆命题不一定成立）。
​ Off-policy 策略主要基于重要性采样方法，它根据目标策略 $ \pi $ 和行为策略 $ b $ 分别所产生的某段相同序列的概率的比值来加权求和奖励值，该比值就是重要性权重：

$$\rho_{t: T-1}=\frac{\prod_{k=t}^{T-1} \pi\left(A_{k} \mid S_{k}\right) p\left(S_{k+1} \mid S_{k}, A_{k}\right)}{\prod_{k=t}^{T-1} b\left(A_{k} \mid S_{k}\right) p\left(S_{k+1} \mid S_{k}, A_{k}\right)}=\frac{\prod_{k=t}^{T-1} \pi\left(A_{k} \mid S_{k}\right)}{\prod_{k=t}^{T-1} b\left(A_{k} \mid S_{k}\right)}$$

​ 当评估在目标策略 $ \pi $ 下的奖励期望时，不能直接使用来自行为策略 $ b $ 产生的样本数据所计算得到的奖励期望 $ E[G_t \mid S_t] $ ，而是应该在求期望的过程中使用重要性权重。

---

---

附录二、证明与推导

a. $J\left(\pi^{\prime}\right)-J(\pi)$

​ 定义 $ J(\pi)=\underset{\tau \sim \pi}{\mathbb{E}}\left[\Sigma_{t=0}^{\infty} \gamma^{t} R\left(s_{t}, a_{t}\right)\right]=\underset{s_{0} \sim \rho}{\mathbb{E}}\left[V^{\pi}\left(s_{0}\right)\right] $ (初始状态s0的分布不随策略变化而变化），有：

$$\begin{aligned} J\left(\pi^{\prime}\right) &=\underset{\tau \sim \pi^{\prime}}{\mathbb{E}}\left[\Sigma_{t=0}^{\infty} \gamma^{t} R\left(s_{t}, a_{t}\right)\right] \\ &=\underset{\tau \sim \pi^{\prime}}{\mathbb{E}}\left[\Sigma_{t=0}^{\infty} \gamma^{t} R\left(s_{t}, a_{t}\right)-\Sigma_{t=0}^{\infty} \gamma^{t} V^{\pi}\left(s_{t}\right)+\Sigma_{t=0}^{\infty} \gamma^{t} V^{\pi}\left(s_{t}\right)\right] \\ &=\underset{\tau \sim \pi^{\prime}}{\mathbb{E}}\left[\Sigma_{t=0}^{\infty} \gamma^{t} R\left(s_{t}, a_{t}\right)-\Sigma_{t=0}^{\infty} \gamma^{t} V^{\pi}\left(s_{t}\right)+\Sigma_{t=0}^{\infty} \gamma^{t+1} V^{\pi}\left(s_{t+1}\right)+V^{\pi}\left(s_{0}\right)\right] \\ &=\underset{\tau \sim \pi^{\prime}}{\mathbb{E}}\left[\Sigma_{t=0}^{\infty} \gamma^{t}\left(R\left(s_{t}, a_{t}\right)-V^{\pi}\left(s_{t}\right)+\gamma V^{\pi}\left(s_{t+1}\right)\right)\right]+\underset{\tau \sim \pi^{\prime}}{\mathbb{E}}\left[V^{\pi}\left(s_{0}\right)\right] \\ &=\underset{\tau \sim \pi^{\prime}}{\mathbb{E}}\left[\Sigma_{t=0}^{\infty} \gamma^{t} A^{\pi}\left(s_{t}, a_{t}\right)\right]+\underset{s_{0} \sim \rho}{\mathbb{E}}\left[V^{\pi}\left(s_{0}\right)\right] \\ &=\underset{\tau \sim \pi^{\prime}}{\mathbb{E}}\left[\Sigma_{t=0}^{\infty} \gamma^{t} A^{\pi}\left(s_{t}, a_{t}\right)\right]+J(\pi) \end{aligned}$$

​ 进一步：

$$\begin{aligned} \underset{\tau \sim \pi^{\prime}}{\mathbb{E}}\left[\Sigma_{t=0}^{\infty} \gamma^{t} A^{\pi}\left(s_{t}, a_{t}\right)\right] &=\mathbb{E}\left[\Sigma_{t=0}^{\infty} \Sigma_{s} P\left(s_{t}=s\right) \Sigma_{a} \pi\left(a_{t}=a \mid s_{t}=s\right) \gamma^{t} A^{\pi}\left(s_{t}, a_{t}\right)\right] \\ &=\mathbb{E}\left[\Sigma_{s} \left(\Sigma_{t=0}^{\infty} \gamma^{t} P\left(s_{t}=s\right)\right) \Sigma_{a} \pi\left(a_{t}=a \mid s_{t}=s\right) A^{\pi}\left(s_{t}, a_{t}\right)\right] \\ &=\frac{1}{1-\gamma} \underset{s \sim d^{\pi^{\prime}} \atop a \sim \pi^{\prime}}{\mathrm{E}}\left[A^{\pi}\left(s_{t}, a_{t}\right)\right] \end{aligned}$$

​ 因此：

$$J\left(\pi^{\prime}\right)-J(\pi)=\frac{1}{1-\gamma} \underset{s \sim d^{\pi^{\prime}} \atop a \sim \pi^{\prime}}{\mathrm{E}}\left[A^{\pi}(s, a)\right]$$

​ 值得注意的是，由于更新策略 $ \pi^{\prime} $ 还没有得到和采样，因此 $ s \sim d^{\pi{\prime}} $ 无法得到，只能用 $ s \sim d^{\pi} $ 近似替代；但是 $ a \sim \pi^{\prime} $ 可以使用重要性采样来修正 $ a \sim \pi $ ，最终可以得到所需样本值。

b. LQCLQ

​ (Optimizing Linear Objective with Linear and Quadratic Constraints). Consider the problem

$$\begin{aligned} p^{*}=\min _{x} & g^{T} x \\ \text { s.t. } & b^{T} x+c \leq 0 \\ & x^{T} H x \leq \delta \end{aligned}$$

​ where $ g, b, x \in \mathbb{R}^{n}, c, \delta \in \mathbb{R}, \delta>0, H \in \mathbb{S}^{n} $, and $ H \succ 0 . $ When there is at least one strictly feasible point, the optimal point $ x^{*} $ satisfies

$$x^{*}=-\frac{1}{\lambda^{*}} H^{-1}\left(g+\nu^{*} b\right)$$

​ where $ \lambda^{} $ and $ \nu^{} $ are defined by

$$\begin{array}{l} \nu^{*}=\left(\frac{\lambda^{*} c-r}{s}\right)_{+} \text{,} \\ \lambda^{*}=\arg \max _{\lambda \geq 0}\left\{\begin{array}{ll} f_{a}(\lambda) \doteq \frac{1}{2 \lambda}\left(\frac{r^{2}}{s}-q\right)+\frac{\lambda}{2}\left(\frac{c^{2}}{s}-\delta\right)-\frac{r c}{s} & \text { if } \lambda c-r>0 \\ f_{b}(\lambda) \doteq-\frac{1}{2}\left(\frac{q}{\lambda}+\lambda \delta\right) & \text { otherwise, } \end{array}\right. \end{array}$$

​ with $ q=g^{T} H^{-1} g, r=g^{T} H^{-1} b $, and $ s=b^{T} H^{-1} b $.