PG-Guide

The Definitive Guide to Policy Gradients

Abstract

这篇综述的目标是全面概述 On-Policy 的策略梯度算法：

• 第二节 概述了深度强化学习需要的 符号表示、强化学习基础知识 以及必要的 深度学习基础知识。虽然这部分内容基本上大多数人都熟悉了，但是我正好借着这篇综述总结一下。
• 第三节 介绍了策略梯度算法的理论基础，包括 Policy Gradient Theorem 连续版本的详细证明、使用 Baseline 以及优势函数来降低方差的技术。

1. Introduction

强化学习通过与环境交互的试错来实现学习最优策略的任务。在早期的强化学习，最成功的应用大多使用基于价值的方法，这些方法估计预期的未来奖励，从而为智能体的决策提供信息。但是这些方法只是间接优化了我们的真正目标——学习最优策略，况且基于价值的方法在具有连续动作空间的环境中应用并非易事。

在这篇综述中，我们讨论的是 策略梯度算法。策略梯度算法旨在学习最优策略，与基于价值的方法相比，策略梯度算法本质上学习随机策略，进而可以产生更加平滑的搜索空间，也在一定程度上弥补了为了优化策略而必须获取环境知识的探索问题，并且策略梯度方法可以在学习过程中实现策略的更平滑变化，这可能会带来更好的收敛特性。

这篇综述的目标是全面概述 On-Policy 的策略梯度算法，虽然排除了一些流行的算法，包括 DDPG 和 SAC 等等，具体来讲，这篇综述做了下面几件事：

• 全面介绍了策略梯度算法的理论基础，包括 Policy Gradient Theorem 连续版本的详细证明；
• 推导并且比较了最突出的策略梯度算法；
• 「Optional」 提供了高质量的伪代码、发布了这些算法的高质量实现，虽然使用的是 Jax。

2. Preliminaries

主要分三个部分，分别是符号表示、强化学习回顾以及深度学习基础。

符号表示没有什么多说的，我们这里使用的基本都是 Lebesgue 积分，将 $\mathcal{A}$ 上可测函数 $f$ 的积分写成 ${\int }_{a\in \mathcal{A}}f(a)\mathrm{d}a:={\int }_{a\in \mathcal{A}}f(a)\mathrm{d}\lambda (a)$。另外，我们使用 ${\mathbb{E}}_{X\sim p}[X]$ 和 ${\mathrm{Var}}_{X\sim p}[X]$ 表示 $X$ 服从分布 $p$ 的期望和方差。使用 $\Delta (\mathcal{A})$ 表示可测空间 $\mathcal{A}$ 的概率分布集。对于变量或者函数 $x$，使用 $\hat{x}$ 表示对其的近似。

2.1 RL Basics

强化学习中的每一个问题都包含一个 Agent 和一个环境，环境包括 Agent 外部的所有事物，Agent 通过与环境交互实现某一个特定目标。交互的过程可以被形式化为一个马尔可夫决策过程/Markov Decision Process，我们将其写成一个元组 $\mathcal{M}=(\mathcal{S},\mathcal{A},P,\gamma ,p_0)$，其中 $P:\mathcal{S}\times \mathcal{A}\to \Delta (\mathcal{S}\times \mathbb{R})$ 是环境的转移函数，定义了在状态 $s$ 下采取动作 $a$ 后，转移到新的环境状态 $s^{\prime }$ 并获得奖励 $r\in \mathbb{R}$ 的概率 $P(s^{\prime },r\mid s,a)$，$\gamma \in [0,1]$ 是折扣率，$p_0\in \Delta (\mathcal{S})$ 是潜在起始状态上的概率分布。

我们将状态、动作和奖励的序列 $\left(s_t,a_t,r_{t+1},s_{t+1},\dots ,s_{t+k-1},a_{t+k-1},r_{t+k},s_{t+k}\right)$ 称为一个轨迹/Trajectory，一个单步轨迹 $\left(s_t,a_t,r_{t+1},s_{t+1}\right)$ 称为一个转移/Transition。

在接下来的设定中，我们假设奖励 $r$ 是有界的、状态和动作空间都是连续的，并且我们限制在 Episodic 设定下，这意味着 Agent 与环境交互的步数是有限的，在交互结束后，环境被重置为初始状态，这说明轨迹的长度至多为 $T$。

强化学习的主要目标是解决一个控制问题，学习到一个策略 $\pi :\mathcal{S}\to \Delta (\mathcal{A})$，以最大化期望回报。我们讲的折扣回报 $G_t:={\sum }_{k=0}^T{\gamma }^k{r}_{t+k+1}$ 是从时间步 $t$ 开始的折扣奖励之和，在 Episodic 设定以及有界奖励设定下，显然折扣奖励是有界的。

使用 $\pi (a\mid s)$ 表示在策略 $\pi$ 下，在状态 $s$ 下采取动作 $a$ 的概率。对于一个策略 $\pi$，其平稳状态分布 $d^{\pi }$ 决定了在遵循 $\pi$ 时，在任何时间点处于特定状态 $s\in \mathcal{S}$ 的概率。

令 $\Pi$ 是所有可能策略的集合。用于控制问题的强化学习算法 $\mathfrak{A}:\Pi \to \Pi$ 通过不断与环境交互来采样转移，进而更新策略，之后我们将关注如何更新策略。强化学习的一个重要特征是，在学习中需要权衡探索和利用/Exploration-Exploitation Trade-off。Agent 对环境没有先验知识，因此需要探索不同的转移，以便了解哪些状态和动作是可取的。然而，由于状态空间和动作空间通常很大，因此利用已经获得的关于环境的知识对于引导搜索过程，找到最有希望的子空间中的最优策略也至关重要。解决这个探索问题的一个常见方法是向策略添加噪声。

接下来可以回顾价值函数、动作价值函数、Bellman 方程和价值迭代的概念：

• 价值函数 $V_{\pi }(s):={\mathbb{E}}_{\pi }[G_t\mid S_t=s]$ 给出了从状态 $s$ 开始，在遵循策略 $\pi$ 时，选择所有后续动作的期望回报。
• 动作价值函数 $Q_{\pi }(s,a):={\mathbb{E}}_{\pi }[G_t\mid S_t=s,A_t=a]$ 给出了从状态 $s$ 开始，先采取动作 $a$，之后在遵循策略 $\pi$ 时，选择所有后续动作的期望回报。
• 优势函数 $A^{\pi }(s,a):=Q_{\pi }(s,a)-V_{\pi }(s)$ 给出了动作 $a$ 在状态 $s$ 中相对于其他可能动作的好坏程度。

价值函数和动作价值函数之间有一个显然的关系

$$V_{\pi }(s)={\int }_{a\in \mathcal{A}}\pi (a\mid s)Q_{\pi }(s,a)\mathrm{d}a$$

还可以推导出贝尔曼方程：

$$\begin{array}{rl}{V}_{\pi }(s)& ={\mathbb{E}}_{\pi }[G_t\mid S_t=s]={\mathbb{E}}_{\pi }[R_{t+1}+\gamma G_{t+1}\mid S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma V_{\pi }(S_{t+1})\mid S_t=s]\\ & ={\int }_{a\in \mathcal{A}}\pi (a\mid s)\left({\int }_{s^{\prime }\in \mathcal{S}}{\int }_{r\in \mathbb{R}}P(s^{\prime },r\mid s,a)\left(r+\gamma {\mathbb{E}}_{\pi }[G_{t+1}\mid S_{t+1}=s^{\prime }]\right)\mathrm{d}{s}^{\prime }\mathrm{d}r\right)\mathrm{d}a\\ & ={\int }_{a\in \mathcal{A}}\pi (a\mid s)\left({\int }_{s^{\prime }\in \mathcal{S}}{\int }_{r\in \mathbb{R}}P(s^{\prime },r\mid s,a)\left(r+\gamma V_{\pi }(s^{\prime })\right)\mathrm{d}{s}^{\prime }\mathrm{d}r\right)\mathrm{d}a\end{array}$$

简单来讲，贝尔曼方程就是下面两个使用期望形式表示的等式：

$$\begin{array}{rl}{V}_{\pi }(s)& ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma V_{\pi }(S_{t+1})\mid S_t=s]\\ Q_{\pi }(s,a)& ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma Q_{\pi }(S_{t+1},A_{t+1})\mid S_t=s,A_t=a]\end{array}$$

我们知道，强化学习的目标是得到最大化期望回报，这对应着一个最优的策略，这里的最优按照下面定义：如果一个策略 ${\pi }^{\ast }$ 满足对于所有状态 $s\in \mathcal{S}$，有 $V_{{\pi }^{\ast }}(s)\ge V_{\pi }(s)$，则称 ${\pi }^{\ast }$ 是最优策略。使用一些机器学习理论的知识：对每一个有限 MDP 中，都存在一个确定性的最优策略。所有最优策略共享相同的最优价值函数 $V^{\ast }(s):={\max }_{\pi \in \Pi }{V}_{\pi }(s)$ 和最优动作价值函数 $Q^{\ast }(s,a):={\max }_{\pi \in \Pi }{Q}_{\pi }(s,a)$。这意味着我们也有对应的 Bellman 方程

$$Q^{\ast }(s,a)=\mathbb{E}[R_{t+1}+\gamma Q^{\ast }(S_{t+1},A_{t+1})\mid S_t=s,A_t=a]$$

利用最优性，我们也有下面的 广义策略迭代/Generalized Policy Iteration 算法：

Generalized Policy Iteration

令 ${\pi }_{\text{old}}$ 为当前策略。那么，广义策略迭代通过以下方式更新其策略：

$${\pi }_{\text{new}}\in \arg \underset{\pi \in \Pi }{\max }{\mathbb{E}}_{A\sim {\pi }_{\text{old}}}[Q_{{\pi }_{\text{old}}}(s,A)]$$

对于所有 $s\in \mathcal{S}$。令 ${\pi }_n$ 通过广义策略迭代获得的一系列策略。那么，这个序列收敛到一个最优策略，即

$$\underset{n\to \infty }{\lim }{\pi }_n={\pi }^{\ast },\underset{n\to \infty }{\lim }{Q}_{{\pi }_n}=Q^{\ast }$$

2.2 On-Policy Policy Gradient

这部分分别介绍函数近似、策略梯度方法和 On-Policy 方法。

早期的强化学习方法本质上是表学习方法，通过维护查找表来学习价值函数、动作-价值函数以及策略的精确表示，虽然这些方法都有理论的收敛保证，但是并不能很好的推广到连续状态和动作空间，这主要是因为其很难将学习从一个已知的状态推广到其他状态。解决方法是使用函数逼近，我们参数化要学习的函数，这些参数在学习中进行调整，并且选择对于输入连续的函数逼近，就可以进行很好的泛化。当然，现在的工作一般都使用神经网络来进行函数逼近，这些领域被称为深度强化学习。

基于价值的方法目标在学习一系列收敛到最优价值函数的价值函数，然后就可以推断出最优策略。与之对比的是基于策略的方法，主要思想是增加产生高回报动作的概率，直到收敛到（近似）最优策略。虽然显然有很多方法可以解决这个优化问题，但是基于梯度的方法是最常用的。

Policy Gradient Algorithm

设 ${\pi }_{\theta }:\mathcal{S}\to \Delta (\mathcal{A})$ 是一个完全可微的函数，其可学习参数 $\theta \in {\mathbb{R}}^d$ 将状态映射到动作上的概率分布。设 $J:{\mathbb{R}}^d\to \mathbb{R}$ 是参数的某一种性能度量。如果任何学习算法通过在 $J$ 上进行梯度上升/下降来更新 $\theta$，从而学习其策略 ${\pi }_{\theta }$，即其更新具有以下一般形式，则我们称之为策略梯度算法：

$${\theta }_{\text{new}}\leftarrow \theta +\alpha {\nabla }_{\theta }J(\theta ),$$

其中 $\alpha \in \mathbb{R}$ 是该算法的步长参数。

我们有两种方式可以使策略输出动作的概率分布，进而从中采样动作。对于离散动作空间，我们使用 Softmax 进行归一化：

$$\pi (a\mid s)=\frac{\exp ({\pi }_{\theta }(a\mid s))}{{\sum }_{a^{\prime }\in \mathcal{A}}\exp ({\pi }_{\theta }(a^{\prime }\mid s))}$$

对于连续动作空间，我们令 ${\pi }_{\theta }$ 输出高斯分布的均值 ${\mu }_{\theta }$ 和标准差 ${\sigma }_{\theta }$，即 ${\pi }_{\theta }(s)=({\mu }_{\theta }(s),{\sigma }_{\theta }(s))$，使得

$$\pi (a\mid s)=\frac{1}{{\sigma }_{\theta }(s)\sqrt{2\pi }}\exp \left(-\frac{(a-{\mu }_{\theta }(s){)}^2}{2{\sigma }_{\theta }(s{)}^2}\right)$$

这意味着我们为每一个状态都学习了一个动作的概率分布，根据概率分布采样动作。由于强化学习的动作空间一般是有界的，从这类高斯分布采样的动作一般通过裁剪或者挤压来进行转换，使得其落在动作空间之内。

最后，我们区分 On-Policy 和 Off-Policy 方法。在强化学习中，我们区分行为策略和目标策略。

• 行为策略是一种生成数据的策略，数据的形式为我们希望学习的轨迹，这是我们在与环境交互时从中采样动作的策略。
• 目标策略是我们想要了解的策略，我们评估这个策略在环境下的性能，然后加以改进。

比如 Q-Learning 和 DQN 都是 Off-Policy 方法。但是我们在这里只讨论 On-Policy 方法。

2.3 Deep Learning Basics

这一节就简单记一记了，我们主要是用前馈网络/Feedforward Neural Network/MLP，不会使用 Transformers。

深度学习相对于传统的机器学习技术，主要优势在于可以使用简单非线性函数的组合从原始数据中学习多个级别的表示来完成预测任务，后者往往需要手工设计的表示作为输入。

MLP 可以表示是一堆函数的组成

$$f=f^{(n+1)}\circ \cdots \circ f^{(1)}$$

我们将前 $n$ 层都称为隐藏层，最后一层 $f^{(n+1)}$ 称为输出层。$n$ 表示网络中隐藏层的数量，每一个隐藏层的特征在于其层宽度 $N_i$。设 $N_0$ 和 $N_{n+1}$ 分别为输入和输出向量的大小。那么，我们可以将每一层写成

$$f^{(i)}(x)=g(W^{(i)}x+b^{(i)}),$$

其中 $x$ 是前一层的输出，或者当 $i=1$ 时是网络的输入，$W^{(i)}\in {\mathbb{R}}^{N_i\times N_{i-1}}$ 和 $b^{(i)}\in {\mathbb{R}}^{N_i}$ 分别是该层的权重矩阵和偏置向量，而 $g:\mathbb{R}\to \mathbb{R}$ 是引入非线性的可微激活函数，对每一个元素逐个应用。

显然可以发现，一个 MLP 可以通过其层大小、层深度以及激活函数类型来表征，也就是使用 $a=\left((N_i{)}_{i=0}^{n+1},g\right)$ 来表征。Universal Approximation Theorem 表明，一个 MLP 只需要有一个隐藏层，且激活函数满足一些弱条件，就可以在给定的任意精度下近似任何一个在给定紧集上的连续函数，在一些广义形式下，甚至可以近似任何可测函数。ReLU 是隐藏层的标准激活函数，对于回归任务，输出层通常不使用激活函数，而对于分类任务，通常使用 sigmoid 或 softmax 函数。每一个隐藏层的每一个元素都被称为一个神经元，任何层的输出 $a^{(i)}(x)=\left(f^{(i)}\circ \cdots \circ f^{(1)}\right)(x)$ 都是输入 $x$ 的学习表示。我们用 $\hat{y}$ 表示神经网络的输出 $f(x)$，即预测值。

对深度学习而言，假设集 $\mathcal{F}$ 的选择是通过选定架构 $a$ 隐式完成的，也就是说，对于具有架构 $a$ 的MLP，其假设集为所有具有该架构的 MLP，记作 ${\mathcal{F}}_a$，这里面的所有 MLP 只在权重和偏置上有所不同。我们将这些网络的可学习参数收集在扁平化的参数向量 $\theta \in {\mathbb{R}}^d$ 中，将具有参数 $\theta$ 的 MLP 记作 $f_{\theta }$。

给定一个假设集 ${\mathcal{F}}_a$，我们现在的目标是学习一个神经网络 $f_{\theta }\in {\mathcal{F}}_a$，即学习参数 $\theta$，从而减少预期风险

$$\mathcal{R}(f):={\mathbb{E}}_{Z\sim {\mathbb{P}}_Z}[\mathcal{L}(f,Z)]={\int }_{z\in \mathcal{Z}}\mathcal{L}(f,z)\mathrm{d}{\mathbb{P}}_Z(z),$$

其中 $\mathcal{L}:\mathcal{F}\times \mathcal{Z}\to \mathbb{R}$ 是损失函数。我们假设训练数据 $S=\{z^{(1)},\dots ,z^{(m)}\}$ 和未见过的样本外数据 $z\in \mathcal{Z}$ 是独立同分布取样的。

常见损失函数包括多用于分类任务的二元交叉熵损失：

$$\mathcal{L}(f,(x,y))=-(y\cdot \ln (f(x))+(1-y)\cdot \ln (1-f(x))),$$

以及多用于回归任务的均方误差损失/MSE：

$$\mathcal{L}(f,(x,y))=(y-f(x){)}^2,$$

有时候损失函数会通过正则化项 $\Omega (\theta )$ 进行增强，比如使用 L2 惩罚，对参数添加项 $\beta \cdot \Vert \theta {\Vert }_2^2$，其中 $\beta \in \mathbb{R}$ 是正则化系数。

一般来讲，背后数据分布 ${\mathbb{P}}_Z$ 是未知的，我们使用频率学派的方法，使用基于采样训练数据 $S$ 的经验分布来代替它，并使用经验风险最小化/ERM 作为学习算法来最小化它：

Empirical Risk

给定训练数据 $S=\{z^{(1)},\dots ,z^{(m)}\}$ 和函数 $f_{\theta }\in \mathcal{M}(\mathcal{X},\mathcal{Y})$，经验风险定义为

$${\hat{\mathcal{R}}}_S(f_{\theta })=\frac{1}{m}\sum _{i=1}^m\mathcal{L}(f_{\theta },z^{(i)}),$$

ERM Learning Algorithm

给定假设集 ${\mathcal{F}}_a$ 和训练数据 $S$，经验风险最小化算法 ${\mathfrak{A}}_{erm}$ 终止于找到一个（近似于）最小化经验风险的函数 ${\hat{f}}_S\in {\mathcal{F}}_a$：

$${\mathfrak{A}}_{erm}(S)={\hat{f}}_S\in \underset{f\in {\mathcal{F}}_a}{\mathrm{argmin}}{\hat{\mathcal{R}}}_S(f),$$

基于反向传播算法可以高效计算逐点导数，因此我们使用梯度优化算法来完成这个优化问题。反向传播实际上运用了链式法则，目标函数 $\mathcal{L}$ 相对于某一层的输入 $a^{(i-1)}$ 可以通过从相对于这一层的输出 $a^{(i)}$ 的梯度向后计算得到，即

$${\nabla }_{a^{(i-1)}}\mathcal{L}=\sum _j({\nabla }_{a^{(i-1)}}{a}_j^{(i)})\cdot \frac{\partial \mathcal{L}}{\partial a_j^{(i)}},$$

将反向传播的过程形成算法如下：

一般情况下，对整个训练集上的数据计算经验风险的代价是昂贵的，更遑论计算梯度了，因此我们更偏向于使用训练集的一个子集来计算梯度与更新参数，这也会带来更快的收敛速度。在每次迭代中，从训练数据中随机抽取大小为 $m^{\prime }\le m$ 的一批数据 $S^{\prime }$（通常 $m^{\prime }\ll m$）来进行更新：

$${\Theta }^{(k)}:={\Theta }^{(k-1)}-{\alpha }_k\frac{1}{m^{\prime }}\sum _{z\in S^{\prime }}{\nabla }_{\theta }\mathcal{L}(f_{{\Theta }^{(k-1)}},z),$$

这里面 ${\alpha }_k$ 是第 $k$ 次迭代中的步长或学习率。学习率通常在训练过程中衰减以帮助收敛。这个操作其实就是小批量随机梯度下降/minibatch SGD，在算法上形式化如下：

随机梯度下降虽然简单，具有随机性，并且损失函数高度非凸，但是性质很好，比如可以引入随机波动，从而能够逃离鞍点，其收敛性也可以有一定的保障。现在我们更经常使用 Adam 等引入了动量方法以及自适应梯度缩放的算法。

参数 $\theta$ 的初始化对于收敛也十分重要，偏重一般初始化为 0，权重则使用很多策略，随机初始化为接近于 0 的值。

最后，无论损失函数的非凸性质如何，如果神经网络足够大，架构设置合理，局部最小值就不被认为是一个问题。从实践来讲，神经网络的训练是一个迭代过程，我们交替选择网络架构以及学习算法的超参数，近似最小化这组超参数的经验风险，从而找到合适的超参数集合，最大化泛化性能。

3. Theoretical Foundations of PG

3.1 Policy Gradient Theorem

给定一个 MDP $M=(\mathcal{S},\mathcal{A},P,\gamma ,p_0)$，考虑一个参数化的、几乎处处可微的策略 ${\pi }_{\theta }$，以及以下目标函数 $J$，用于最大化预期的 episodic 回报：

$$\begin{array}{rl}J(\theta )& ={\mathbb{E}}_{S_0\sim p_0,{\pi }_{\theta }}[G_0]\\ & ={\mathbb{E}}_{S_0\sim p_0}\left[{\mathbb{E}}_{{\pi }_{\theta }}[G_t|S_t=S_0]\right]\\ & ={\mathbb{E}}_{S_0\sim p_0}[V_{{\pi }_{\theta }}(S_0)],\end{array}$$

策略梯度算法的思想是通过对参数 $\theta$ 进行梯度上升来最大化目标函数 $J(\theta )$，因此我们需要求出梯度 ${\nabla }_{\theta }J(\theta )$。但是从先验上，右侧的期望 ${\mathbb{E}}_{S_0\sim p_0,{\pi }_{\theta }}[G_0]$ 同时收到策略 ${\pi }_{\theta }$ 变化影响，这是因为状态分布 $d^{\pi }$ 自然会随着策略变化而变化。

策略梯度定理的意义就在于其解决了这个难题，给出了一个便于采样的梯度表达式，表达式的形式并不依赖于状态分布 $d^{\pi }$ 的导数。

Policy Gradient Theorem

对于一个给定的 MDP，策略 ${\pi }_{\theta }$ 关于 $\theta$ 可微且 ${\nabla }_{\theta }{\pi }_{\theta }$ 有界，动作价值函数 $Q^{{\pi }_{\theta }}$ 关于 $\theta$ 也可微且对于所有 $s\in \mathcal{S}$ 和 $a\in \mathcal{A}$，${\nabla }_{\theta }{Q}^{{\pi }_{\theta }}$ 有界。那么存在一个常数 $\eta$，使得

$${\nabla }_{\theta }J(\theta )=\eta {\mathbb{E}}_{S\sim d^{{\pi }_{\theta }},A\sim {\pi }_{\theta }}[Q_{{\pi }_{\theta }}(S,A){\nabla }_{\theta }\ln {\pi }_{\theta }(A\mid S)].$$

接下来部分是该定理的证明，我们遵循 Sutton & Barto: Reinforcement Learning, 2nd Edition 的证明，并且将其扩展到了连续的状态与动作空间，在证明中，我们省略了所有的下标 $\theta$，但是需要知道的是，这里面的策略 $\pi$ 和所有的梯度 $\nabla$ 都依赖于参数 $\theta$。

首先处理目标函数：我们显示写出对于起始状态的期望，使用价值函数和动作价值函数的关系：

$$\begin{array}{rl}\nabla J(\theta )& =\nabla {\mathbb{E}}_{S\sim p_0}[V_{\pi }(S)]\\ & =\nabla {\int }_{s\in \mathcal{S}}{p}_0(s)V_{\pi }(s)\mathrm{d}s\\ & =\nabla {\int }_{s\in \mathcal{S}}{p}_0(s){\int }_{a\in \mathcal{A}}\pi (a\mid s)Q_{\pi }(s,a)\mathrm{d}a\mathrm{d}s\\ & ={\int }_{s\in \mathcal{S}}{p}_0(s)\left[{\int }_{a\in \mathcal{A}}(\nabla \pi (a\mid s))Q_{\pi }(s,a)\mathrm{d}a+{\int }_{a\in \mathcal{A}}\pi (a\mid s)\nabla Q_{\pi }(s,a)\mathrm{d}a\right]\mathrm{d}s.\end{array}\text{\hspace{1em}(1)}$$

这里使用了 Leibniz 积分法则，交换了积分和微分的顺序，然后再使用乘法法则。这里使用定理的条件成立，因为对于任何 $s\in \mathcal{S}$，$\pi (\cdot \mid s)Q_{\pi }(s,\cdot )$ 是可积的，并且对于所有 $s\in \mathcal{S}$ 和 $a\in \mathcal{A}$，其偏导数存在且有界，因为 $\pi$ 和 $Q_{\pi }$ 是有界的，且根据假设，$\nabla Q_{\pi }$ 和 $\nabla \pi$ 存在且有界。

下面处理动作价值函数的梯度，注意到一件本质的事情：在给定某个动作 $a$ 后，实际的回报 $r$ 和环境的状态转移并不依赖于策略 $\pi$，因此我们可以将其视为常数，因此就有：

$$\begin{array}{rl}\nabla Q_{\pi }(s,a)& =\nabla {\int }_{s^{\prime }\in \mathcal{S}}{\int }_{r\in \mathbb{R}}P(s^{\prime },r\mid s,a)(r+V_{\pi }(s^{\prime }))\mathrm{d}r\mathrm{d}{s}^{\prime }\\ & ={\int }_{s^{\prime }\in \mathcal{S}}{\int }_{r\in \mathbb{R}}P(s^{\prime },r\mid s,a)\nabla V_{\pi }(s^{\prime })\mathrm{d}r\mathrm{d}{s}^{\prime }\\ & ={\int }_{s^{\prime }\in \mathcal{S}}{\int }_{r\in \mathbb{R}}P(s^{\prime },r\mid s,a)\nabla V_{\pi }(s^{\prime })\mathrm{d}r\mathrm{d}{s}^{\prime }\\ & ={\int }_{s^{\prime }\in \mathcal{S}}\left[{\int }_{r\in \mathbb{R}}P(s^{\prime },r\mid s,a)\mathrm{d}r\right]\nabla V_{\pi }(s^{\prime })\mathrm{d}{s}^{\prime }\\ & ={\int }_{s^{\prime }\in \mathcal{S}}P(s^{\prime }\mid s,a)\nabla V_{\pi }(s^{\prime })\mathrm{d}{s}^{\prime }\end{array}\text{\hspace{1em}(2)}$$

然后处理价值函数的梯度，对所有的 $s\in \mathcal{S}$，有

$$\begin{array}{rl}\nabla V_{\pi }(s)& =\nabla {\int }_{a\in \mathcal{A}}\pi (a\mid s)Q_{\pi }(s,a)\mathrm{d}a\\ & ={\int }_{a\in \mathcal{A}}(\nabla \pi (a\mid s))Q_{\pi }(s,a)\mathrm{d}a+{\int }_{a\in \mathcal{A}}\pi (a\mid s)\nabla Q_{\pi }(s,a)\mathrm{d}a\end{array}\text{\hspace{1em}(3)}$$

这个式子和 (1) 的内层表达式是一致的，我们可以使用 (2) 和 (3) 来将 (1) 转换为递归形式，然后展开该递归，以得到一个显示形式。我们定义下符号：

$$\varphi (s):={\int }_{a\in \mathcal{A}}(\nabla \pi (a\mid s))Q_{\pi }(s,a)\mathrm{d}a\text{\hspace{1em}(4)}$$

对 (1) 使用 (3) 和 (2)，并重新排列积分，得到

$$\begin{array}{rl}\nabla J(\theta )& ={\int }_{s\in \mathcal{S}}{p}_0(s)\left[{\int }_{a\in \mathcal{A}}(\nabla \pi (a\mid s))Q_{\pi }(s,a)\mathrm{d}a+{\int }_{a\in \mathcal{A}}\pi (a\mid s)\nabla Q_{\pi }(s,a)\mathrm{d}a\right]\mathrm{d}s\\ & ={\int }_{s\in \mathcal{S}}{p}_0(s)\left(\varphi (s)+{\int }_{a\in \mathcal{A}}\pi (a\mid s)\nabla Q_{\pi }(s,a)\mathrm{d}a\right)\mathrm{d}s\\ & ={\int }_{s\in \mathcal{S}}{p}_0(s)\left(\varphi (s)+{\int }_{a\in \mathcal{A}}\pi (a\mid s){\int }_{s^{\prime }\in \mathcal{S}}P(s^{\prime }\mid s,a)\nabla V_{\pi }(s^{\prime })\mathrm{d}{s}^{\prime }\mathrm{d}a\right)\mathrm{d}s\\ & ={\int }_{s\in \mathcal{S}}{p}_0(s)\left(\varphi (s)+{\int }_{s^{\prime }\in \mathcal{S}}{\int }_{a\in \mathcal{A}}\pi (a\mid s)P(s^{\prime }\mid s,a)\mathrm{d}a\nabla V_{\pi }(s^{\prime })\mathrm{d}{s}^{\prime }\right)\mathrm{d}s\end{array}\text{\hspace{1em}(5)}$$

这里最后一步使用了 Fubini 定理交换了积分顺序。这是因为 $\nabla V_{\pi }$ 有界，且 $\pi (\cdot \mid s)P(\cdot \mid s,\cdot )$ 是 $\mathcal{S}\times \mathcal{A}$ 上的概率测度，因此 $|\pi (\cdot \mid s)P(\cdot \mid s,\cdot )\nabla V_{\pi }|$ 在乘积空间 $\mathcal{S}\times \mathcal{A}$ 上是可积的。

为了在时间上展开公式 (5)，我们引入多步转移概率的符号。设 ${\rho }_{\pi }(s\to s^{\prime },k)$ 为在策略 $\pi$ 下经过 $k$ 步后从状态 $s$ 转移到 $s^{\prime }$ 的概率。我们显然有

$$\begin{array}{rl}{\rho }_{\pi }(s\to s^{\prime },0)& :=\{\begin{array}{ll}1& \text{if }s=s^{\prime }\\ 0& \text{else}\end{array}\\ {\rho }_{\pi }(s\to s^{\prime },1)& :={\int }_{a\in \mathcal{A}}\pi (a|s)P(s^{\prime }|s,a)\mathrm{d}a\\ {\rho }_{\pi }(s\to s^{\prime },k+1)& :={\int }_{s^{\prime }\in S}{\rho }_{\pi }(s\to s^{\prime },k){\rho }_{\pi }(s^{\prime }\to s^{\prime \prime },1)\mathrm{d}{s}^{\prime }\end{array}$$

迭代地代入 (5)，不断使用 Fubini 定理：

$$\begin{array}{rl}\nabla J(\theta )& ={\int }_{s\in \mathcal{S}}{p}_0(s)\left(\varphi (s)+{\int }_{s^{\prime }\in \mathcal{S}}{\int }_{a\in \mathcal{A}}\pi (a\mid s)P(s^{\prime }\mid s,a)\mathrm{d}a\nabla V_{\pi }(s^{\prime })\mathrm{d}{s}^{\prime }\right)\mathrm{d}s\\ & ={\int }_{s\in \mathcal{S}}{p}_0(s)\left(\varphi (s)+{\int }_{s^{\prime }\in \mathcal{S}}{\rho }_{\pi }(s\to s^{\prime },1)\nabla V_{\pi }(s^{\prime })\mathrm{d}{s}^{\prime }\right)\mathrm{d}s\\ & ={\int }_{s\in \mathcal{S}}{p}_0(s)\left\{\varphi (s)+{\int }_{s^{\prime }\in \mathcal{S}}{\rho }_{\pi }(s\to s^{\prime },1)\left[\varphi (s^{\prime })+{\int }_{a\in \mathcal{A}}\pi (a\mid s^{\prime })\nabla Q_{\pi }(s^{\prime },a)\mathrm{d}a\right]\mathrm{d}{s}^{\prime }\right\}\mathrm{d}s\\ & ={\int }_{s\in \mathcal{S}}{p}_0(s)\left\{\varphi (s)+{\int }_{s^{\prime }\in \mathcal{S}}{\rho }_{\pi }(s\to s^{\prime },1)\left[\varphi (s^{\prime })+{\int }_{s^{\prime \prime }\in \mathcal{S}}{\rho }_{\pi }(s^{\prime }\to s^{\prime \prime },1)\nabla V_{\pi }(s^{\prime \prime })\mathrm{d}{s}^{\prime \prime }\right]\mathrm{d}{s}^{\prime }\right\}\mathrm{d}s\\ & ={\int }_{s\in \mathcal{S}}{p}_0(s)\left\{\varphi (s)+{\int }_{s^{\prime }\in \mathcal{S}}{\rho }_{\pi }(s\to s^{\prime },1)\varphi (s^{\prime })\mathrm{d}{s}^{\prime }+{\int }_{s^{\prime \prime }\in \mathcal{S}}\left({\int }_{s^{\prime }\in \mathcal{S}}{\rho }_{\pi }(s\to s^{\prime },1){\rho }_{\pi }(s^{\prime }\to s^{\prime \prime },1)\mathrm{d}{s}^{\prime }\right)\nabla V_{\pi }(s^{\prime \prime })\mathrm{d}{s}^{\prime \prime }\right\}\mathrm{d}s\\ & ={\int }_{s\in \mathcal{S}}{p}_0(s)\left\{\varphi (s)+{\int }_{s^{\prime }\in \mathcal{S}}{\rho }_{\pi }(s\to s^{\prime },1)\varphi (s^{\prime })\mathrm{d}{s}^{\prime }+{\int }_{s^{\prime \prime }\in \mathcal{S}}{\rho }_{\pi }(s\to s^{\prime \prime },2)\nabla V_{\pi }(s^{\prime \prime })\mathrm{d}{s}^{\prime \prime }\right\}\mathrm{d}s\\ & ={\int }_{s\in \mathcal{S}}{p}_0(s)\left\{\sum _{k=0}^{t-1}{\int }_{s^{\prime }\in \mathcal{S}}{\rho }_{\pi }(s\to s^{\prime },k)\varphi (s^{\prime })\mathrm{d}{s}^{\prime }+{\int }_{s^{\prime }\in \mathcal{S}}{\rho }_{\pi }(s\to s^{\prime },t)\nabla V_{\pi }(s^{\prime })\mathrm{d}{s}^{\prime }\right\}\mathrm{d}s\\ & ={\int }_{s\in \mathcal{S}}{p}_0(s){\int }_{s^{\prime }\in \mathcal{S}}\sum _{t=0}^T{\rho }_{\pi }(s\to s^{\prime },t)\varphi (s^{\prime })\mathrm{d}{s}^{\prime }\mathrm{d}s\end{array}$$

令 ${\eta }_s(s^{\prime }):={\sum }_{t=0}^T{\rho }^{\pi }(s\to s^{\prime },t)$，考虑 ${\eta }_s(s^{\prime })$ 的含义，其代表了在策略 $\pi$ 下，从状态 $s$ 出发，经过任意步后到达状态 $s^{\prime }$ 的概率总和。对起始状态分布求积分，并且进行归一化（这是因为很有可能这不是一个概率分布），可以注意到

$$d^{\pi }(s^{\prime })={\int }_{s\in \mathcal{S}}{p}_0(s){\eta }_s(s^{\prime })\mathrm{d}s/{\int }_{s^{\prime \prime }\in \mathcal{S}}{\int }_{s\in \mathcal{S}}{p}_0(s){\eta }_s(s^{\prime \prime })\mathrm{d}s\mathrm{d}{s}^{\prime \prime }$$

重新排列积分顺序可以得到：

$$\begin{array}{rl}{\nabla }_{\theta }J(\theta )& ={\int }_{s\in \mathcal{S}}{p}_0(s){\int }_{s^{\prime }\in \mathcal{S}}\sum _{t=0}^T{\rho }_{\pi }(s\to s^{\prime },t)\varphi (s^{\prime })\mathrm{d}{s}^{\prime }\mathrm{d}s\\ & ={\int }_{s^{\prime }\in \mathcal{S}}{\int }_{s\in \mathcal{S}}{p}_0(s){\eta }_s(s^{\prime })\varphi (s^{\prime })\mathrm{d}s\mathrm{d}{s}^{\prime }\\ & =\frac{{\int }_{s^{\prime \prime }\in \mathcal{S}}{\int }_{s\in \mathcal{S}}{p}_0(s){\eta }_s(s^{\prime \prime })\mathrm{d}s\mathrm{d}{s}^{\prime \prime }}{{\int }_{s^{\prime \prime }\in \mathcal{S}}{\int }_{s\in \mathcal{S}}{p}_0(s){\eta }_s(s^{\prime \prime })\mathrm{d}s\mathrm{d}{s}^{\prime \prime }}{\int }_{s^{\prime }\in \mathcal{S}}{\int }_{s\in \mathcal{S}}{p}_0(s){\eta }_s(s^{\prime })\varphi (s^{\prime })\mathrm{d}s\mathrm{d}{s}^{\prime }\\ & ={\int }_{s^{\prime \prime }\in \mathcal{S}}{\int }_{s\in \mathcal{S}}{p}_0(s){\eta }_s(s^{\prime \prime })\mathrm{d}s\mathrm{d}{s}^{\prime \prime }\cdot {\int }_{s^{\prime }\in \mathcal{S}}\frac{{\int }_{s\in \mathcal{S}}{p}_0(s){\eta }_s(s^{\prime })\mathrm{d}s}{{\int }_{s^{\prime \prime }\in \mathcal{S}}{\int }_{s\in \mathcal{S}}{p}_0(s){\eta }_s(s^{\prime \prime })\mathrm{d}s\mathrm{d}{s}^{\prime \prime }}\varphi (s^{\prime })\mathrm{d}{s}^{\prime }\\ & ={\int }_{s\in \mathcal{S}}{p}_0(s){\int }_{s^{\prime \prime }\in \mathcal{S}}{\eta }_s(s^{\prime \prime })\mathrm{d}{s}^{\prime \prime }\mathrm{d}s\cdot {\int }_{s^{\prime }\in \mathcal{S}}{d}^{\pi }(s^{\prime })\varphi (s^{\prime })\mathrm{d}{s}^{\prime }\end{array}$$

接下来就可以直接得出策略梯度定理的规范形式了：令常数 $\eta$ 定义如下：

$$\eta :={\int }_{s\in \mathcal{S}}{p}_0(s){\int }_{s^{\prime \prime }\in \mathcal{S}}{\eta }_s(s^{\prime \prime })\mathrm{d}{s}^{\prime \prime }\mathrm{d}s$$

因此

$$\begin{array}{rl}\nabla J(\theta )& ={\int }_{s\in \mathcal{S}}{p}_0(s){\int }_{s^{\prime \prime }\in \mathcal{S}}{\eta }_s(s^{\prime \prime })\mathrm{d}{s}^{\prime \prime }\mathrm{d}s\cdot {\int }_{s^{\prime }\in \mathcal{S}}{d}^{\pi }(s^{\prime })\varphi (s^{\prime })\mathrm{d}{s}^{\prime }\\ & =\eta {\int }_{s^{\prime }\in \mathcal{S}}{d}^{\pi }(s^{\prime }){\int }_{a\in \mathcal{A}}(\nabla \pi (a\mid s^{\prime }))Q_{\pi }(s^{\prime },a)\mathrm{d}a\mathrm{d}{s}^{\prime }\\ & =\eta {\int }_{s^{\prime }\in \mathcal{S}}{d}^{\pi }(s^{\prime }){\int }_{a\in \mathcal{A}}\pi (a\mid s^{\prime })\frac{\nabla \pi (a\mid s^{\prime })}{\pi (a\mid s^{\prime })}{Q}_{\pi }(s^{\prime },a)\mathrm{d}a\mathrm{d}{s}^{\prime }\\ & =\eta {\int }_{s^{\prime }\in \mathcal{S}}{d}^{\pi }(s^{\prime }){\int }_{a\in \mathcal{A}}\pi (a\mid s^{\prime })(\nabla \ln \pi (a\mid s^{\prime }))Q_{\pi }(s^{\prime },a)\mathrm{d}a\mathrm{d}{s}^{\prime }\\ & =\eta {\mathbb{E}}_{S\sim d^{\pi }}\left[{\mathbb{E}}_{A\sim \pi }\left[Q_{\pi }(S,A)\nabla \ln \pi (A\mid S)\right]\right].\end{array}$$

这就完成了证明。

策略梯度定理给出了策略梯度的显式形式，我们可以从中对梯度进行采样。这就使得我们可以使用基于梯度的优化方法来直接优化策略，也构成了之后的策略梯度算法的基础。

最后我们给出对策略梯度公式的进一步说明，首先是参数 $\eta$ 的含义，简而言之，它是策略 $\pi$ 下的平均 episode 长度。

$$\begin{array}{rl}\eta & ={\int }_{s\in \mathcal{S}}{p}_0(s){\int }_{s^{\prime }\in \mathcal{S}}{\eta }_s(s^{\prime })\mathrm{d}{s}^{\prime }\mathrm{d}s={\int }_{s\in \mathcal{S}}{p}_0(s){\int }_{s^{\prime }\in \mathcal{S}}\sum _{t=0}^T{\rho }_{\pi }(s\to s^{\prime },t)\mathrm{d}{s}^{\prime }\mathrm{d}s\\ & ={\mathbb{E}}_{S\sim p_0}\left[\sum _{t=0}^T{\int }_{s^{\prime }\in \mathcal{S}}{\rho }_{\pi }(S\to s^{\prime },t)\mathrm{d}{s}^{\prime }\right],\end{array}$$

其次，这个参数 $\eta$ 在优化算法的梯度更新中并不那么重要，由于我们使用基于梯度的方法，只要采样得到的梯度与真实梯度成比例即可（这是因为比例常数可以被学习率吸收），因此常数 $\eta$ 通常被省略，我们也通常将其写成

$${\nabla }_{\theta }J(\theta )\propto {\mathbb{E}}_{S\sim d^{{\pi }_{\theta }},A\sim {\pi }_{\theta }}\left[Q_{{\pi }_{\theta }}(S,A){\nabla }_{\theta }\ln {\pi }_{\theta }(A|S)\right].\text{\hspace{1em}(6)}$$

右侧所有项都是已知的或者可以通过采样来估计，这就允许我们设计多样的策略梯度算法。

3.2 Value Function Estimation

在实践中，当直接对公式 (6) 进行采样时，策略梯度的估计可能会引入非常多的噪声，因此，策略梯度算法的一个主要实际挑战是引入措施来降低梯度的方差。一种技术就是在对动作价值函数 $Q_{\pi }$ 进行采样估计的时候使用基线/Baseline，我们这里将证明，使用适当选择的基线不会使估计产生偏差，但可以大大降低采样梯度的方差。

令 $\hat{Q}(s,a)$ 为 $Q_{\pi }(s,a)$ 的采样估计，假设 $\mathbb{E}[\hat{Q}(s,a)]=Q_{\pi }(s,a)$。我们可以通过减掉一个基线 $b:\mathcal{S}\to \mathbb{R}$ 来构建一个新的估计 ${\hat{Q}}_b(s,a)=\hat{Q}(s,a)-b(s)$。这里对 $b$ 的唯一要求就是它不依赖于动作 $a$，除此之外其可以依赖于状态 $s$，甚至可以是一个随机变量。

我们采样估计的梯度 ${\nabla }_{\theta }J(\theta )$ 变为

$${\hat{\nabla }}_{\theta }J(\theta )={\nabla }_{\theta }\ln {\pi }_{\theta }(a\mid s)[\hat{Q}(s,a)-b(s)].$$

对于策略 $\pi$ 求期望，得到

$$\begin{array}{rl}{\mathbb{E}}_{\pi }[{\hat{\nabla }}_{\theta }J(\theta )]& ={\mathbb{E}}_{\pi }[{\nabla }_{\theta }\ln {\pi }_{\theta }(A\mid S)(\hat{Q}(S,A)-b(S))]\\ & ={\mathbb{E}}_{\pi }[{\nabla }_{\theta }\ln {\pi }_{\theta }(A\mid S)\hat{Q}(S,A)]-{\mathbb{E}}_{\pi }[{\nabla }_{\theta }\ln {\pi }_{\theta }(A\mid S)b(S)]\end{array}$$

下面我们证明第二部分其实就是 0，使用 Leibniz 积分法则，我们有

$$\begin{array}{rl}{\mathbb{E}}_{S\sim d^{\pi },A\sim \pi }[{\nabla }_{\theta }\ln {\pi }_{\theta }(A\mid S)b(S)]& ={\int }_{s\in \mathcal{S}}{d}^{\pi }(s){\int }_{a\in \mathcal{A}}{\pi }_{\theta }(a\mid s){\nabla }_{\theta }\ln {\pi }_{\theta }(a\mid s)b(s)\mathrm{d}a\mathrm{d}s\\ & ={\int }_{s\in \mathcal{S}}{d}^{\pi }(s)b(s){\int }_{a\in \mathcal{A}}{\pi }_{\theta }(a\mid s){\nabla }_{\theta }\ln {\pi }_{\theta }(a\mid s)\mathrm{d}a\mathrm{d}s\\ & ={\int }_{s\in \mathcal{S}}{d}^{\pi }(s)b(s){\int }_{a\in \mathcal{A}}{\pi }_{\theta }(a\mid s)\frac{{\nabla }_{\theta }{\pi }_{\theta }(a\mid s)}{{\pi }_{\theta }(a\mid s)}\mathrm{d}a\mathrm{d}s\\ & ={\int }_{s\in \mathcal{S}}{d}^{\pi }(s)b(s){\nabla }_{\theta }{\int }_{a\in \mathcal{A}}{\pi }_{\theta }(a\mid s)\mathrm{d}a\mathrm{d}s\\ & ={\int }_{s\in \mathcal{S}}{d}^{\pi }(s)b(s){\nabla }_{\theta }1\mathrm{d}s\\ & =0\end{array}$$

因此，在对 $Q_{\pi }$ 的估计上减掉一个和动作无关的 Baseline $b$ 并不会给梯度估计造成任何的偏差，High-Dimensional Continuous Control Using Generalized Advantage Estimation 这篇文章将上述结果进行了推广，表明了即使基线依赖于当前和所有后续状态，这个结果依然成立。

下面我们简单分析减去基线 $b$ 可以降低采样梯度的方差。使用公式 $\mathrm{Var}[X]=\mathbb{E}[X^2]-\mathbb{E}[X{]}^2$，由于上面已经证明了 $\mathbb{E}[X{]}^2$ 和基线 $b$ 无关，因此我们只需要分析 $\mathbb{E}[X^2]$ 的变化。我们有

$$\begin{array}{rl}\underset{b}{\mathrm{argmin}}{\mathrm{Var}}_{\pi }[{\nabla }_{\theta }\ln {\pi }_{\theta }(A|S)[\hat{Q}(S,A)-b(S)]]& =\underset{b}{\mathrm{argmin}}{\mathbb{E}}_{\pi }[({\nabla }_{\theta }\ln {\pi }_{\theta }(A|S)[\hat{Q}(S,A)-b(S)]{)}^2]\\ & \approx \underset{b}{\mathrm{argmin}}\left[{\mathbb{E}}_{\pi }[{\nabla }_{\theta }\ln {\pi }_{\theta }(A|S{)}^2]\cdot {\mathbb{E}}_{\pi }[\hat{Q}(S,A)-b(S{)}^2]\right],\end{array}$$

上面的近似基于这两个项的独立性的假设。在这个近似下，我们可以通过最小化 ${\mathbb{E}}_{\pi }[\hat{Q}(S,A)-b(S){]}^2$ 来最小化采样梯度的方差。这是一个常见的最小二乘问题，只需要选择 $b(s)={\mathbb{E}}_{\pi }[\hat{Q}(s,A)]$ 即可。这表明选择一个恰当的 Baseline 可以显著降低梯度的方差。使用这个 Baseline，我们可以按照如下方式计算采样状态和动作的梯度

$$\begin{array}{rl}{\nabla }_{\theta }\ln {\pi }_{\theta }(a|s)[Q_{\pi }(s,a)-{\mathbb{E}}_{A\sim {\pi }_{\theta }}[Q_{\pi }(s,A)]]& ={\nabla }_{\theta }\ln {\pi }_{\theta }(a|s)[Q_{\pi }(s,a)-V_{\pi }(s)]\\ & ={\nabla }_{\theta }\ln {\pi }_{\theta }(a|s)A_{\pi }(s,a).\end{array}$$

这种选择的 Baseline 产生了梯度的最低可能方差。在实践中，优势函数必须也被估计，学习这种估计通常会引入偏差 :-) 这就涉及到了 Bias-Variance 权衡的问题。

3.3 Importace Sampling

Importance Sampling 是一种基于从一个分布中采样来估计另一个分布下的期望的技术。在 Off-Policy 强化学习中非常重要。在某些 On-Policy 的强化学习算法中，由于策略在处理完其采样的所有数据之前就更新了，因此这些数据就变得微微偏离 On-Policy 了，因此 Importance Sampling 也有了用武之地。我们简单介绍 Importance Sampling，可以参见我 未完成的笔记。

给定一个行为策略 $\beta$，我们想要估计目标策略 $\pi$ 的价值函数 $V_{\pi }$。一般来讲都会有 $V_{\beta }(s)={\mathbb{E}}_{\beta }[G_t\mid S_t=s]\ne V_{\pi }(s)$。为了使用行为策略估计目标策略的价值函数，我们需要计算在任何策略 $\pi$ 下的轨迹 $(a_t,s_{t+1},a_{t+1},\dots ,a_{T-1},s_T)$ 的出现概率：

$$\prod _{k=t}^{T-1}\pi (a_k\mid s_k)P(s_{k+1}\mid s_k,a_k).$$

这就可以定义 Importance Sampling Ratio：

Importance Sampling Ratio

给定目标策略 $\pi$，行为策略 $\beta$ 和由 $\beta$ 生成的轨迹 $\tau =(a_t,s_{t+1},a_{t+1},\dots ,s_T)$，Importance Sampling Ratio 定义为

$${\rho }_{t:T-1}:=\frac{{\prod }_{k=t}^{T-1}\pi (a_k\mid s_k)P(s_{k+1}\mid s_k,a_k)}{{\prod }_{k=t}^{T-1}\beta (a_k\mid s_k)P(s_{k+1}\mid s_k,a_k)}=\frac{{\prod }_{k=t}^{T-1}\pi (a_k\mid s_k)}{{\prod }_{k=t}^{T-1}\beta (a_k\mid s_k)}.$$

设 $\mathcal{T}$ 为可能轨迹的集合，我们通过将由行为策略 $\beta$ 生成的轨迹 $\tau \in \mathcal{T}$ 的回报与 Importance Sampling Ratio $\rho$ 相乘，我们得到

$$\begin{array}{rl}{\mathbb{E}}_{\beta }[{\rho }_{t:T-1}{G}_t\mid S_t=s]& ={\mathbb{E}}_{\beta }[{\rho }_{t:T-1}G(\tau )\mid S_t=s]\\ & =\sum _{\tau \in \mathcal{T}}{\rho }_{t:T-1}G(\tau )\prod _{k=t}^{T-1}\beta (a_k\mid s_k)P(s_{k+1}\mid s_k,a_k)\\ & =\sum _{\tau \in \mathcal{T}}\frac{{\prod }_{k=t}^{T-1}\pi (a_k\mid s_k)}{{\prod }_{k=t}^{T-1}\beta (a_k\mid s_k)}G(\tau )\prod _{k=t}^{T-1}\beta (a_k\mid s_k)P(s_{k+1}\mid s_k,a_k)\\ & =\sum _{\tau \in \mathcal{T}}G(\tau )\prod _{k=t}^{T-1}\pi (a_k\mid s_k)P(s_{k+1}\mid s_k,a_k)\\ & ={\mathbb{E}}_{\pi }[G_t\mid S_t=s]=V_{\pi }(s).\end{array}$$

这就使用了重要度采样比进行了矫正。直觉比较简单，为了评估目标策略 $\pi$，我们希望更多地权衡在 $\pi$ 更容易发生的回报，更少地权衡在 $\beta$ 更容易发生的回报。作为上述推导的扩展，我们还得到了逐决策重要度采样比率 $\rho :=\frac{\pi (a\mid s)}{\beta (a\mid s)}$。

使用 Importance Sampling，我们可以推导出带有行为策略 $\beta$ 的 Off-Policy 设置中，目标策略 ${\pi }_{\theta }$ 的以下近似策略梯度：

$${\nabla }_{\theta }J(\theta )\approx \eta {\mathbb{E}}_{S\sim d^{\beta },A\sim \beta }\left[\frac{{\pi }_{\theta }(A\mid S)}{\beta (A\mid S)}{Q}_{{\pi }_{\theta }}(S,A){\nabla }_{\theta }\ln {\pi }_{\theta }(A\mid S)\right].$$

4. Policy Gradient Algorithms

4.1 REINFORCE

4.2 A3C

4.3 TRPO

4.4 PPO

4.5 V-MPO

4.6 Comparing Design Choices

5. Convergence Results

5.1 Literature Overview

5.2 Mirror Learning