1. Introduction

在上一节，我们学习了使用 Value Function Approximation 实现将value进行参数化表示，这样做的好处在于可以实现高效存储和泛化。那么，以此类推，我们也可以将Policy的表示进行参数化，通过更新参数的方式优化Policy，这样可以解决之前基于value方法的局限性：

连续动作的处理能力不足。我们知道在受限的MDP下，Value-Based的方法需要评估action value来实现Policy的优化，这就导致这类方法一般都是只处理离散动作，无法处理连续动作。如果我们的action是一些连续的变量，比如速度，力的大小，精确的坐标等，，这个策略使用离散的方式是不好表达的，但是用Policy Based强化学习方法却很容易建模。
受限状态下的问题处理能力不足。在使用特征来描述状态空间中的某一个状态时，有可能因为个体观测的限制或者建模的局限，导致真实环境下本来不同的两个状态却再我们建模后拥有相同的特征描述，进而很有可能导致我们的value-based方法无法得到最优解。
无法获得随机策略。Value-Based方法从众多action value中选择一个最大价值的作为执行的action，这对应的最优策略通常是确定性策略，而有些问题的最优策略却是随机策略，这种情况下同样是无法通过基于价值的学习来求解的。

参数化的Policy更新一般通过梯度实现，我们需要定义以下内容：

通过公式定义最优的Policy，作为目标函数—— 如何设计合适的目标函数？
通过梯度上升更新参数：$\theta_{t+1} = \theta_t + \alpha\nabla_{\theta}J(\theta_t)$ —— 如何计算梯度？

2. Policy Objective Functions

在Policy Based强化学习方法下，我们直接使用一个包含可学习参数 $\theta$ 的函数来表示Policy：

$$
\pi_{\theta}(s, a)=P(a \mid s, \theta) \approx \pi(a \mid s)
$$

将策略表示成一个连续的函数后，我们就可以用连续函数的优化方法来寻找最优的策略了。那么如何定义优化目标呢？我们知道 state value可以衡量基于某个Policy的state好坏，所以我们如果能使得state value更大，那么这个Policy就越好。一般有两种形式：

average state value：

$$
J_{avV}(\theta) =\sum\limits_sd(s)V_{\pi_{\theta}}(s)
$$

其中 $d(s) \ge 0$ 是状态value的权重，且权重和为1，因此也可以理解为基于策略 $\pi_{\theta}$ 的状态概率，所以整个式子也可以看成是state value的期望。$d(s)$ 按照是否与Policy有关可以分为两种形式：

$d$ 与 Policy无关，此时我们可以令 $d$ 等于状态的个数，那么上面的式子就变成了最简单的state value求平均值。此外还有一种形式就是 $d(s_0) = 1, d(s\neq s_0) = 0$ ，此时上面的式子就变成了 $G_0$ ，即初始状态的return
$d$ 与 Policy有关，此时我们一般使用 $\pi_{\theta}$ 的稳态分布 stationary distribution，满足 $d_{\theta}^TP_{\pi} = d_{\theta}^T$ ，$P_{\pi}$ 是状态转移矩阵。因此，可以将这个权重理解为：如果一个状态的转移概率大，说明在一个长序列中会经常被访问，那么就更重要，需要赋予更大的权重；反之，则不重要，权重小一点。

average reward per time-step：

$$
J_{avR}(\theta) = \sum\limits_sd_{\pi_{\theta}}(s) \sum\limits_a \pi_{\theta}(s,a) R_s^a
$$

其中，式子的后半部分表述的是所有从 $s$ 开始执行一步动作获得reward的期望。

3. Policy Gradient

3.1 Gradient

令 $J(\theta)$ 为我们要优化的Policy objective function，我们可以通过沿着梯度上升的方向去更新 $\theta$ 实现局部最大值的搜寻，即更新量可以表示为：

$$
\Delta{\theta} = \alpha\nabla_{\theta} J(\theta)
$$

其中 $\nabla_{\theta} J(\theta)$ 就是Policy gradient，即 $\theta$ 关于 $J(\theta)$ 的偏导数，$\alpha$ 就是学习率，控制每次更新的幅度：

$$
\nabla_{\theta} J(\theta)=\left(\begin{array}{c}
\frac{\partial J(\theta)}{\partial \theta_{1}} \\
\vdots \\
\frac{\partial J(\theta)}{\partial \theta_{n}}
\end{array}\right)
$$

3.2 Policy Gradient Theorem

3.2.1 One-step MDP

下面考虑一个最简单的 one-step MDP，并在一步执行后进入终止状态，reward表示为 $\mathcal{} R_{s,a}$ ，很容易可以得到Policy gradient：

$$
\begin{aligned}
J(\theta) & =\mathbb{E}_{\pi_{\theta}}[r] \\
& =\sum_{s \in \mathcal{S}} d(s) \sum_{a \in \mathcal{A}} \pi_{\theta}(s, a) \mathcal{R}_{s, a} \\
\nabla_{\theta} J(\theta) & =\sum_{s \in \mathcal{S}} d(s) \sum_{a \in \mathcal{A}} \pi_{\theta}(s, a) \nabla_{\theta} \log \pi_{\theta}(s, a) \mathcal{R}_{s, a} \\
& =\mathbb{E}_{\pi_{\theta}}\left[\nabla_{\theta} \log \pi_{\theta}(s, a) r\right]
\end{aligned}
$$

其中，上式计算梯度时，使用了下面的技巧进行了转换：

$$
\begin{aligned}
\nabla_{\theta} \pi_{\theta}(s, a) & =\pi_{\theta}(s, a) \frac{\nabla_{\theta} \pi_{\theta}(s, a)}{\pi_{\theta}(s, a)} \\
& =\pi_{\theta}(s, a) \nabla_{\theta} \log \pi_{\theta}(s, a)
\end{aligned}
$$

其中 $\nabla_{\theta} \log \pi_{\theta}(s, a)$ 也被称为score function，值得注意的是，如果我们要使用log去进行计算，那么就要求$\pi_\theta > 0$ ，这也进一步说明Policy-based方法得到的都是随机策略。下面给出一些常用的 score function：

3.2.2 Softmax Policy

在softmax policy中，我们先对Policy进行特征化表示，采用最简单的线性组合：$\phi(s,a)^T\theta$ ，然后再使用softmax的形式表示Policy中Action的概率，实现归一化：

$$
\pi_{\theta}(s, a) \propto e^{\phi(s, a)^{\top} \theta}
$$

我们进行梯度计算，可以得到softmax policy下的score function为：

$$
\nabla_{\theta} \log \pi_{\theta}(s, a)=\phi(s, a)-\mathbb{E}_{\pi_{\theta}}[\phi(s, \cdot)]
$$

3.2.3 Gaussian Policy

在连续的动作空间中，使用高斯Policy是很自然的一个想法。首先，使用线性组合对state进行特征化：$\mu(s) = \phi(s)^T\theta$，action的概率服从高斯分布：$a\sim \mathcal{N}(\mu(s),\sigma^2)$，同样我们可以计算得到score function为：

$$
\nabla_{\theta} \log \pi_{\theta}(s, a)=\frac{(a-\mu(s)) \phi(s)}{\sigma^{2}}
$$

3.2.4 Policy Gradient Theorem

更一般化的，对于上面提到的任意Policy Objective Functions，我们可以将 $J(\theta)$ 的梯度统一转换成下面的式子：

$$
\begin{aligned}
\nabla_{\theta} J(\theta) & =\sum_{s \in \mathcal{S}} d(s) \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a) \\
& =\mathbb{E}\left[\nabla_{\theta} \log \pi(A \mid S, \theta) q_{\pi}(S, A)\right]
\end{aligned}
$$

其中，$S \sim d$ ，$A \sim \pi(A|S,\theta)$，将梯度的连加形式转换成期望的形式，好处在于我们可以使用采样的方式去估计梯度了！

证明可以见：https://fancyerii.github.io/books/rl6/

3.3 Finite Differences

除了直接计算梯度，还有一种方法通过有限差分来近似计算梯度，可以用于不可微分的Policy

4. Monte-Carlo Policy Gradient

下面介绍第一种Policy Gradient算法。首先定义梯度上升算法通过下面的式子最大化目标函数：

$$
\begin{aligned}
\theta_{t+1} & =\theta_{t}+\alpha \nabla_{\theta} J(\theta) \\
& =\theta_{t}+\alpha \mathbb{E}\left[\nabla_{\theta} \ln \pi\left(A \mid S, \theta_{t}\right) q_{\pi}(S, A)\right] \\
& =\theta_{t}+\alpha \nabla_{\theta} \ln \pi\left(a_{t} \mid s_{t}, \theta_{t}\right) q_{\pi}\left(s_{t}, a_{t}\right)
\end{aligned}
$$

上式第二项指的是我们借助梯度期望来更新参数，第三项指的是将期望最换成随机采样的方式进行（stochastic ），由于 $q_{\pi}$ 是未知的，我们可以使用蒙特卡洛或者时间差分对其进行估计，这里我们使用蒙特卡洛，所以这个算法叫做Monte-Carlo Policy Gradient，同时也被称为REINFORCE。

下面我们用一个新视角理解这个算法，根据导数的定义，我们可以得到下面的式子：

$$
\nabla_{\theta} \ln \pi(a \mid s, \theta)=\frac{\nabla_{\theta} \pi(a \mid s, \theta)}{\pi(a \mid s, \theta)}
$$

所以上述的算法可以转写成下面的形式：

$$
\begin{aligned}
\theta_{t+1} & =\theta_{t}+\alpha \nabla_{\theta} \ln \pi\left(a_{t} \mid s_{t}, \theta_{t}\right) q_{t}\left(s_{t}, a_{t}\right) \\
& =\theta_{t}+\alpha \underbrace{\left(\frac{q_{t}\left(s_{t}, a_{t}\right)}{\pi\left(a_{t} \mid s_{t}, \theta_{t}\right)}\right)}_{\beta_{t}} \nabla_{\theta} \pi\left(a_{t} \mid s_{t}, \theta_{t}\right) \\
& =\theta_{t}+\alpha \beta_t \nabla_{\theta} \pi\left(a_{t} \mid s_{t}, \theta_{t}\right)
\end{aligned}
$$

从式子我们可以直观的看出，当 $\beta_t>0$ ，$(s_t,a_t)$ 被选中的概率会被增加。$\beta_t$ 实际上在这个算法中承担了平衡 exploration and exploitation 的作用：

$\beta_t$ 和 $q_t(s_t,a_t)$ 是成正比的，因此这个算法会把value更高的action更新更大的概率
$\beta_t$ 和 $\pi(a_{t} \mid s_{t}, \theta_{t})$ 是成反比的，如果 $\pi(a_{t} \mid s_{t}, \theta_{t})$ 很小，那么 $\beta_t$ 就会很大，这就意味着如果某个action被执行的概率很小，那么即使他的value相对来说没那么大，下次更新后也会增加其被选择的概率。这就使得算法可以探索到更多的区域。

REINFORCE算法相比Value-Based方法训练更稳定，学习曲线不会是上下剧烈波动的锯齿状，而是平滑的曲线。但是这种方法训练非常缓慢，并且会有很大的方差。下面提出新算法解决这个问题。

4. Actor-Critic Policy Gradient

4.1 QAC

Policy Gradient 算法的思想其实很简单——先定义一个标量的metric作为目标函数，然后使用梯度上升方法去最大化目标函数，首先将梯度表示成期望的形式，然后使用随机采样来近似期望（stochastic algorithm），最终更新的式子为：

$$
\theta_{t+1} =\theta_{t}+\alpha \nabla_{\theta} \ln \pi\left(a_{t} \mid s_{t}, \theta_{t}\right) q_{t}\left(s_{t}, a_{t}\right)
$$

从式子中，我们可以分离出两个"角色"：

actor：借助梯度更新参数，实现Policy优化，即上述的整个算法
critic：估计 $q_{t}(s_{t}, a_{t})$ 的值，对应value estimate算法。

到目前为止，估计value我们一共有两种方法：Monte-Carlo 和 Temporal-difference，其中使用MC的方法我们称之为REINFORCE，也就是上面介绍过的算法。使用 Temporal-difference 的算法我们称之为Actor-Critic算法。

下面给出最简单的一种AC算法流程：

从流程中我们可以看到，在每个step，根据 $\pi$ 得到 $s_t,a_t,r_{t+1},s_{t+1},a_{t+1}$ ，然后Actor更新Policy的参数，再接着Critic更新value function的参数。所以可以看到，这个算法中我们一次迭代需要更新两个参数。同时，这里的critic使用的是某个value近似算法，其实就是SARSA，这从上面生成的序列就可以看出。
这是一个on-policy的算法。同时，由于我们的sample是根据分布随机采样得到的，所以不需要使用 $\epsilon$-greedy策略。
该算法也被称为QAC，Q就代表value function中的Q。

4.2 Advantage actor-critic

这个算法的核心算法就是引入一个baseline来减少估计的方差。首先介绍一个性质：

$$
\begin{aligned}
\mathbb{E}_{S \sim \eta, A \sim \pi}\left[\nabla_{\theta} \ln \pi\left(A \mid S, \theta_{t}\right) b(S)\right] & =\sum_{s \in \mathcal{S}} \eta(s) \sum_{a \in \mathcal{A}} \pi\left(a \mid s, \theta_{t}\right) \nabla_{\theta} \ln \pi\left(a \mid s, \theta_{t}\right) b(s) \\
& =\sum_{s \in \mathcal{S}} \eta(s) \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi\left(a \mid s, \theta_{t}\right) b(s) \\
& =\sum_{s \in \mathcal{S}} \eta(s) b(s) \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi\left(a \mid s, \theta_{t}\right) \\
& =\sum_{s \in \mathcal{S}} \eta(s) b(s) \nabla_{\theta} \sum_{a \in \mathcal{A}} \pi\left(a \mid s, \theta_{t}\right) \\
& =\sum_{s \in \mathcal{S}} \eta(s) b(s) \nabla_{\theta} 1=0
\end{aligned}
$$

因此我们有：

$$
\mathbb{E}_{S \sim \eta, A \sim \pi}\left[\nabla_{\theta} \ln \pi\left(A \mid S, \theta_{t}\right) q_{\pi}(S, A)\right]=\mathbb{E}_{S \sim \eta, A \sim \pi}\left[\nabla_{\theta} \ln \pi\left(A \mid S, \theta_{t}\right)\left(q_{\pi}(S, A)-b(S)\right)\right]
$$

那么这个式子有啥用呢？我们令 $X(S,A) = \nabla_{\theta} \ln \pi\left(A \mid S, \theta_{t}\right)\left(q_{\pi}(S, A)-b(S)\right)$，由上面的推到我们知道 $\mathbb{E}[X]$ 是与 $b(s)$ 无关的。但是$X$的方差是与 $b(S)$ 有关的。矩阵的方差可以用矩阵的迹来表示，于是有：

$$
\begin{aligned}
\operatorname{tr}[\operatorname{var}(X)] & =\mathbb{E}\left[X^{T} X\right]-\bar{x}^{T} \bar{x} \\
\mathbb{E}\left[X^{T} X\right] & =\mathbb{E}\left[\left(\nabla_{\theta} \ln \pi\right)^{T}\left(\nabla_{\theta} \ln \pi\right)\left(q_{\pi}(S, A)-b(S)\right)^{2}\right] \\
& =\mathbb{E}\left[\left\|\nabla_{\theta} \ln \pi\right\|^{2}\left(q_{\pi}(S, A)-b(S)\right)^{2}\right]
\end{aligned}
$$

因此，$b(S)$ 的取值会影响整个期望的大小，如果取值波动很大，期望的波动就会很大，即方差会很大。如果方差太大，我们在随机采样的时候，就可能会得到一个与真实期望相差很多的样本，会导致训练的不稳定。因此，我们希望期望的方差越小越好。自然地，我们可以使用上面的baseline来调整期望的方差，同时不会影响期望本身。

具体而言，我们定义最优的baseline（期望方差最小），对于任意一个 $s$，我们有（证明略）：

$$
b^{*}(s)=\frac{\mathbb{E}_{A \sim \pi}\left[\left\|\nabla_{\theta} \ln \pi\left(A \mid s, \theta_{t}\right)\right\|^{2} q_{\pi}(s, A)\right]}{\mathbb{E}_{A \sim \pi}\left[\left\|\nabla_{\theta} \ln \pi\left(A \mid s, \theta_{t}\right)\right\|^{2}\right]}, \quad s \in \mathcal{S}
$$

然而上面的表达太复杂了，我们采用次优的$b(s) = \mathbb{E}_{A\sim\pi}\left[q(s,A)\right]=v_{\pi}(s)$，即状态的value就是一个合适的baseline，下面将这个结论结合到AC算法中。

$$
\begin{align*}
\theta_{t+1} &= \theta_t + \alpha \mathbb{E} \left[ \nabla_\theta \ln \pi(A \mid S, \theta_t) \left[q_\pi(S, A) – v_\pi(S)\right] \right] \\
&= \theta_t + \alpha \mathbb{E} \left[ \nabla_\theta \ln \pi(A \mid S, \theta_t) \delta_\pi(S, A) \right] \\

\end{align*}
$$

其中 $\delta_\pi(S, A) = {q_\pi(S, A) – v_\pi(S)}$，该式子也被称为advantage function，因为 $ v_\pi(S)$ 其实就是action value的一个平均值，因此两者相减就衡量了当前这个action value比平均值好多少。上式对应的随机采样版本表达式为：

$$
\begin{align*}
\theta_{t+1} &= \theta_t + \alpha \nabla_\theta \ln \pi(a_t \mid s_t, \theta_t) \left[q_t(s_t, a_t) – v_t(s_t)\right] \\
&= \theta_t + \alpha \nabla_\theta \ln \pi(a_t \mid s_t, \theta_t) \delta_t(s_t, a_t)
\end{align*}
$$

此外，$q_t$ 我们可以使用 TD error来近似得到：

$$
\begin{align*}
\delta_t &= {q_t(s_t, a_t) – v_t(s_t)} \rightarrow {r_{t+1} + \gamma v_t(s_{t+1}) – v_t(s_t)}
\end{align*}
$$

等式成立的原因是：

$$
\mathbb{E}\left[q_\pi(S, A) – v_\pi(S) \mid S = s_t, A = a_t\right] = \mathbb{E}\left[R + \gamma v_\pi(S') – v_\pi(S) \mid S = s_t, A = a_t\right]
$$

这样转换的好处是，我们只需要使用一个参数来估计 $v_\pi(s)$ 的值，就能够得到 $\delta_t$ 的值了。整合上面所有得到的式子，就得到了A2C算法：

4.3 Off-policy actor-critic

回顾我们之前学到的 Importance sampling 技术，即使用一个来自其他分布采样的sample来估计另外一个分布的期望：

$$
\mathbb{E}_{X \sim p_0}\left[X\right] = \sum_x p_0(x) x = \sum_x {p_1(x)} \frac{p_0(x)}{p_1(x)} x = {\mathbb{E}_{X \sim p_1}\left[f(X)\right]}

再根据大数定理，我们可以把期望转换成平均数的形式：

$$
\mathbb{E}_{X \sim p_0}\left[X\right] \approx \bar{f} = \frac{1}{n} \sum_{i=1}^{n} f(x_i) = \frac{1}{n} \sum_{i=1}^{n}{\frac{p_0(x_i)}{p_1(x_i)}} {x_i}
$$

$\frac{p_0(x_i)}{p_1(x_i)}$ 称为 importance weight，因为：

If $p_1(x_i) = p_0(x_i)$, the importance weight is one and $\bar{f}$ becomes $\bar{x}$.
If $p_0(x_i) \geq p_1(x_i)$, $x_i$ can be more often sampled by $p_0$ than $p_1$. The importance weight $(> 1)$ can emphasize the importance of this sample.

此外，需要注意的是，虽然我们可以获得 $x$ 和 $p_0(x)$，同时我们的目标是得到期望，那为什么我们不直接通过 $xp_0(x)$ 计算得到呢？因为我们有些时候无法获取 $p_0(x)$ 的表达式，比如在连续的情况下期望需要用积分计算很复杂，还比如$p_0(x)$可能使用神经网络表达。这些时候都只能通过多次采样，然后近似拟合去进行，也就要使用重要性采样。

对于 Off-policy policy gradient 我们也有同样的理论来计算梯度：

$$
\begin{align*}
\nabla_\theta J(\theta) &= \mathbb{E}_{S \sim \rho, A \sim \pi} \left[ \nabla_\theta \ln \pi(A \mid S, \theta) q_\pi(S, A) \right] \\
&= \mathbb{E}_{S \sim \rho, A \sim \beta} \left[ \frac{\pi(A \mid S, \theta)}{\beta(A \mid S)} \nabla_\theta \ln \pi(A \mid S, \theta) q_\pi(S, A) \right]
\end{align*}
$$

最后，我们可以得到Off-policy actor-critic 的算法流程，这里同样使用了 baseline的思想来减少方差：

4.4 Deterministic Policy Gradient

前面的所有算法都是stochastic，也就是对于一个state，Policy会给出所有action被选中的概率，并且保证所有的action概率都不为0. 这样做的好处是，我们可以处理一些需要随机状态的场景，但缺点是没法处理action是连续的问题，因为不能列出所有action的概率。这时候就需要使用Deterministic的方法了，Deterministic Policy的定义如下：

$$
a = \mu(s,\theta) = \mu(s)
$$

即 action 是关于状态 $s$ 和参数 $\theta$ 的函数，注意这里的 $a$ 就是实际的动作是什么，而不是概率。目标函数和随机策略的版本是一致的，只是求梯度时有一点区别：

$$
\begin{align*}
\nabla_\theta J(\theta) &= {\sum_{s \in \mathcal{S}} \rho_\mu(s) \nabla_\theta \mu(s) \left( \nabla_a q_\mu(s, a) \right)\big|_{a = \mu(s)}} \\
&= {\mathbb{E}_{S \sim \rho_\mu} \left[ \nabla_\theta \mu(S) \left( \nabla_a q_\mu(S, a) \right)\big|_{a = \mu(S)} \right]}
\end{align*}
$$

区别在于，这里 $a$ 是直接使用 $\mu(s)$ 进行替换，而不需要进行采样得到。因此，这里也是off-policy的，我们可以任意的选取policy，接着我们就能得到算法更新参数的表达式，以及随机采样的版本：

$$
\theta_{t+1} = \theta_t + \alpha_\theta \mathbb{E}_{S \sim \rho_\mu} \left[ \nabla_\theta \mu(S) \left( \nabla_a q_\mu(S, a) \right)\big|_{a = \mu(S)} \right]\\
\theta_{t+1} = \theta_t + \alpha_\theta \nabla_\theta \mu(s_t) \left( \nabla_a q_\mu(s_t, a) \right)\big|_{a = \mu(s_t)}

整体伪代码如下：

Reference

[1] 西湖大学赵世钰老师的【强化学习的数学原理】课程学习：https://www.bilibili.com/video/BV1sd4y167NS?p=50&vd_source=2720fa88df30f76bcabd203bb6fac9a5

[2] 部分图片来自赵世钰老师的书籍《强化学习的数学原理》https://github.com/MathFoundationRL/Book-Mathematical-Foundation-of-Reinforcement-Learning/blob/main/Book-all-in-one.pdf