Lecture 9: Policy Gradient Methods

Basic idea of policy gradient

之前，policy是用表格表示的：

所有state的action概率都存储在表 $\pi (a|s)$中。 表的每个条目都由state和action索引。

因此可以直接访问或更改表中的值。

现在，policy可以用参数化函数来表示：
$$\pi (a|s,\theta )$$
其中，$\theta \in {\mathbb{R}}^m$是参数向量。

例如，该函数可以是一个神经网络，其输入是 $s$，输出是采取每个动作的概率，参数是 $\theta$。

优势：当state空间较大时，表格表示在存储和泛化方面效率较低。

函数表示有时也写为 $\pi (a,s,\theta )$、${\pi }_{\theta }(a|s)$ 或 ${\pi }_{\theta }(a,s)$。

表格表示和函数表示之间的差异：

最优policy的定义：

当表示为表格时，如果policy $\pi$ 可以最大化每个 state value，则该policy $\pi$ 是最优的。

当用函数表示时，如果policy $\pi$ 可以最大化某些标量指标，则该policy $\pi$ 是最优的。

获取action的概率：

在表格情况下，可以通过查找表格 policy 来直接获取在 $s$ 处取 $a$ 的概率。

在函数表示的情况下，需要在给定函数结构和参数的情况下计算 $\pi (a|s,\theta )$ 的值。

更新policy的方法：

当用表格表示时，可以通过直接更改表中的条目来更新 policy $\pi$。

当用参数化函数表示时，policy $\pi$ 不能再以这种方式更新。 相反，它只能通过改变参数 $\theta$ 来更新。

策略梯度的基本思想：

第一，定义最优 policy 的标准（或目标函数）：$J(\theta )$，其可以定义最优policy。

第二，基于梯度的优化算法来搜索最优policy
$${\theta }_{t+1}={\theta }_t+\alpha {\nabla }_{\theta }J({\theta }_t)$$

Metrics to define optimal policies

有两个指标。

第一个指标是平均 state value 或简称为平均值。 特别地，该度量定义为：
$${\bar{v}}_{\pi }=\sum _{s\in \mathcal{S}}d(s)v_{\pi }(s)$$

• ${\bar{v}}_{\pi }$ 是state value的加权平均值。

• $d(s)\ge 0$ 是状态 $s$ 的权重。

• 由于 ${\sum }_{s\in \mathcal{S}}d(s)=1$，可以将 $d(s)$ 解释为概率分布。 那么，指标可以写为：
  $${\bar{v}}_{\pi }=\mathbb{E}[v_{\pi }(S)]$$
  其中：$S\sim d$

Vector-product form：
$${\bar{v}}_{\pi }=\sum _{s\in \mathcal{S}}d(s)v_{\pi }(s)=d^T{v}_{\pi }$$
其中：
$$\begin{array}{rl}{v}_{\pi }& =[\dots ,v_{\pi }(s),\dots {]}^T\in {\mathbb{R}}^{|\mathcal{S}|}\\ d& =[\dots ,d(s),\dots {]}^T\in {\mathbb{R}}^{|\mathcal{S}|}\end{array}$$
关于选择分布$d$，有两个方式：

第一种情况是 $d$ 与policy $\pi$ 无关。

这种情况相对简单，因为指标的梯度更容易计算。

在这种情况下，具体将 $d$ 表示为 $d_0$，将 ${\bar{v}}_{\pi }$ 表示为 ${\bar{v}}_{\pi }^0$

关于 $d_0$ 的选择：

一种简单的方法是将所有 state 同等重要，因此选择 $d_0(s)=1/|\mathcal{S}|.$。

该方法有一个特例是只对特定的state $s_0$ 感兴趣。 例如，某些任务中的情节总是从相同的state $s_0$ 开始。 那么，只关心从$s_0$开始的长期回报。 在这种情况下，
$$d_0(s_0)=1,d_0(s\ne s_0)=0.$$
第二种情况是 $d$ 取决于policy $\pi$。

一种常用的方法是选择 $d$ 作为 $d_{\pi }(s)$，它是 $\pi$ 下的平稳分布。

选择 $d_{\pi }$ 的解释如下。

• 如果一个 state 从长远来看被频繁访问，那么它就更重要，值得更多重视。
• 如果一个 state 很少被访问，那么给予它的权重较小。

第二个指标是平均一步 reward 或简单的平均 reward。
$${\bar{r}}_{\pi }\doteq \sum _{s\in \mathcal{S}}{d}_{\pi }(s)r_{\pi }(s)=\mathbb{E}[r_{\pi }(S)],$$
其中，$S\sim d_{\pi }$，
$$r_{\pi }(s)\doteq \sum _{a\in \mathcal{A}}\pi (a|s)r(s,a)$$
权重 $d_{\pi }$ 是平稳分布。

${\bar{r}}_{\pi }$ 只是一步即时reward的加权平均值。

一种等效定义！

假设 agent 遵循给定的 policy 并生成 reward 为 $(R_{t+1},R_{t+2},\cdots )$ 的轨迹。

沿着这条trajectory 的平均单步 reward 是：
$$\begin{array}{rl}& \underset{n\to \infty }{\lim }\frac{1}{n}\mathbb{E}[R_{t+1}+R_{t+2}+\cdots +R_{t+n}|S_t=s_0]\\ & =\underset{n\to \infty }{\lim }\frac{1}{n}\mathbb{E}\left[\sum _{k=1}^n{R}_{t+k}|S_t=s_0\right]\end{array}$$
其中 $s_0$ 是 trajectory 的起始 state。

一个重要的属性是：
$$\begin{array}{rl}\begin{array}{r}\underset{n\to \infty }{\lim }\frac{1}{n}\mathbb{E}\left[\sum _{k=1}^n{R}_{t+k}|S_t=s_0\right]\end{array}& \begin{array}{r}=\underset{n\to \infty }{\lim }\frac{1}{n}\mathbb{E}\left[\sum _{k=1}^n{R}_{t+k}\right]\end{array}\\ & =\sum _s{d}_{\pi }(s)r_{\pi }(s)\\ & ={\bar{r}}_{\pi }\end{array}$$

• 起始state $s_0$ 并不重要。
• ${\bar{r}}_{\pi }$ 的两个定义是等价的。

关于指标的备注 1：

• 所有这些指标都是 $\pi$ 的函数。
• 由于 $\pi$ 由 $\theta$ 参数化，因此这些指标是 $\theta$ 的函数。
• 不同的 $\theta$ 值可以生成不同的指标值。
• 可以搜索 $\theta$ 的最佳值来最大化这些指标。

关于指标的备注 2：

• 度量可以在 $\gamma \in (0,1)$ 的discounted情况下定义，也可以在 $\gamma =1$ 的undiscounted情况下定义。

关于指标的备注 3：

• 直观上，${\bar{r}}_{\pi }$ 更加短视，因为它只考虑即时reward，而 ${\bar{v}}_{\pi }$ 则考虑整体步骤的总reward。

• 然而，这两个指标是等效的。 在$\gamma \in (0,1)$ 的 discounted 情况下，有：
  $${\bar{r}}_{\pi }=(1-\gamma ){\bar{v}}_{\pi }$$

Excise:

在文献中会经常看到以下指标：
$$J(\theta )=\mathbb{E}\left[\sum _{t=0}^{\infty }{\gamma }^t{R}_{t+1}\right]$$
从 $S_0\sim d$ 开始，然后是 $A_0$, $R_1$, $S_1$, $A_1$, $R_2$, $S_2$，$\cdots$。

$A_t\sim \pi (S_t)$ 并且 $R_{t+1},S_{t+1}\sim p(R_{t+1}|S_t,A_t),p(S_{t+1}|S_t,A_t)$

因为这个指标与平均值相同，因为：
$$\begin{array}{rl}\begin{array}{r}J(\theta )=\mathbb{E}\left[\sum _{t=0}^{\infty }{\gamma }^t{R}_{t+1}\right]\end{array}& =\sum _{s\in \mathcal{S}}d(s)\mathbb{E}\left[\sum _{t=0}^{\infty }{\gamma }^t{R}_{t+1}|S_0=s\right]\\ & =\sum _{s\in \mathcal{S}}d(s)v_{\pi }(s)\\ & ={\bar{v}}_{\pi }\end{array}$$

Gradients of the metrics

给定一个指标，接下来

• 导出其梯度
• 然后，应用基于梯度的方法来优化指标。

梯度计算是 policy 梯度方法中最复杂的部分之一！ 那是因为

• 首先，需要区分不同的度量 ${\bar{v}}_{\pi }$，${\bar{r}}_{\pi }$，${\bar{v}}_{\pi }^0$

其次，需要区分 discounted 和 undiscounted 的情况。

关于梯度的结果总结：
$${\nabla }_{\theta }J(\theta )=\sum _{s\in \mathcal{S}}\eta (s)\sum _{a\in \mathcal{A}}{\nabla }_{\theta }\pi (a|s,\theta )q_{\pi }(s,a)$$
其中：

• $J(\theta )$可以是 ${\bar{v}}_{\pi }$，${\bar{r}}_{\pi }$ 或 ${\bar{v}}_{\pi }^0$。
• “=” 可以表示严格相等、近似或成比例。
• $\eta$ 是 state 的分布或权重。

一些具体结果：
$${\nabla }_{\theta }{\bar{r}}_{\pi }\simeq \sum _s{d}_{\pi }(s)\sum _a{\nabla }_{\theta }\pi (a|s,\theta )q_{\pi }(s,a),$$

$${\nabla }_{\theta }{\bar{v}}_{\pi }=\frac{1}{1-\gamma }{\nabla }_{\theta }{\bar{r}}_{\pi }$$

$${\nabla }_{\theta }{\bar{v}}_{\pi }^0=\sum _{s\in \mathcal{S}}{\rho }_{\pi }(s)\sum _{a\in \mathcal{A}}{\nabla }_{\theta }\pi (a|s,\theta )q_{\pi }(s,a)$$

一种紧凑且有用的梯度形式：
$$\begin{array}{rl}{\nabla }_{\theta }J(\theta )& =\sum _{s\in \mathcal{S}}\eta (s)\sum _{a\in \mathcal{A}}{\nabla }_{\theta }\pi (a|s,\theta )q_{\pi }(s,a)\\ & =\mathbb{E}[{\nabla }_{\theta }\ln \pi (A|S,\theta )q_{\pi }(S,A)]\end{array}$$
其中，$S\sim \eta$，$A\sim \pi (A|S,\theta )$

Why is this expression useful?

可以用样本来近似梯度。
$${\nabla }_{\theta }J\approx {\nabla }_{\theta }\ln \pi (a|s,\theta )q_{\pi }(s,a)$$

$$\begin{array}{rl}{\nabla }_{\theta }J(\theta )& =\sum _{s\in \mathcal{S}}\eta (s)\sum _{a\in \mathcal{A}}{\nabla }_{\theta }\pi (a|s,\theta )q_{\pi }(s,a)\\ & =\mathbb{E}\left[{\nabla }_{\theta }\ln \pi (A|S,\theta )q_{\pi }(S,A)\right]\end{array}$$

How to prove the above equation?

考虑函数 $ln\pi$，其中 $ln$是自然对数。 很容易看出：
$${\nabla }_{\theta }\ln \pi (a|s,\theta )=\frac{{\nabla }_{\theta }\pi (a|s,\theta )}{\pi (a|s,\theta )}$$
因此：
$${\nabla }_{\theta }\pi (a|s,\theta )=\pi (a|s,\theta ){\nabla }_{\theta }\ln \pi (a|s,\theta ).$$
因此，可得：
$$\begin{array}{rl}{\nabla }_{\theta }J& \begin{array}{rl}& =\sum _{s}d(s)\sum _a{\nabla }_{\theta }\pi (a|s,\theta )q_{\pi }(s,a)\end{array}\\ & =\sum _{s}d(s)\sum _a\pi (a|s,\theta ){\nabla }_{\theta }\ln \pi (a|s,\theta )q_{\pi }(s,a)\\ & ={\mathbb{E}}_{S\sim d}\left[\sum _a\pi (a|S,\theta ){\nabla }_{\theta }\ln \pi (a|S,\theta )q_{\pi }(S,a)\right]\\ & ={\mathbb{E}}_{S\sim d,A\sim \pi }\left[\begin{array}{c}{\nabla }_{\theta }\ln \pi (A|S,\theta )q_{\pi }(S,A)\end{array}\right]\\ & \doteq \mathbb{E}[{\nabla }_{\theta }\ln \pi (A|S,\theta )q_{\pi }(S,A)]\end{array}$$
因为需要计算 $ln\pi (a|s,\theta$)，所以我们必须保证对于所有 $s$, $a$, $\theta$：
$$\pi (a|s,\theta )>0$$
这可以通过使用 softmax 函数来处理，该函数可以将向量中的条目从 $(-\infty ,+\infty )$标准化为 $(0,1)$。

例如，对于任何向量 $x=[x_1,\cdots ,x_n{]}^T$，有：
$$z_i=\frac{e^{x_i}}{{\sum }_{j=1}^n{e}^{x_j}}$$
其中，$z_i\in (0,1)$ 并且 ${\sum }_{i=1}^n{z}_i=1$。

policy 函数的形式为：
$$\pi (a|s,\theta )=\frac{e^{h(s,a,\theta )}}{{\sum }_{a^{\prime }\in \mathcal{A}}{e}^{h(s,a^{\prime },\theta )}},$$
其中，$h(s,a,\theta )$是其他函数。

这种基于 softmax 函数的形式可以通过输入为$s$、参数为 $\theta$ 的神经网络来实现。 网络有 $|\mathcal{A}|$ 输出，每个输出对应于动作 $a$ 的 $\pi (a|s,\theta )$。 输出层的激活函数应该是 softmax。

由于对于所有 $a$，$\pi (a|s,\theta )>0$，因此参数化策略是随机的，因此具有探索性。

还存在确定性 policy 梯度（DPG）方法。

Gradient-ascent algorithm (REINFORCE)

第一个策略梯度算法来寻找最优策略：

最大化 $J(\theta )$ 的梯度上升算法为：
$$\begin{array}{rl}{\theta }_{t+1}& ={\theta }_t+\alpha {\nabla }_{\theta }J(\theta )\\ & ={\theta }_t+\alpha \mathbb{E}[{\nabla }_{\theta }\ln \pi (A|S,{\theta }_t)q_{\pi }(S,A)]\end{array}$$
真实梯度可以用随机梯度代替：
$${\theta }_{t+1}={\theta }_t+\alpha {\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)q_{\pi }(s_t,a_t)$$
此外，由于 $q_{\pi }$ 未知，因此可以近似：
$${\theta }_{t+1}={\theta }_t+\alpha {\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)q_t(s_t,a_t)$$
How to do sampling?
$${\mathbb{E}}_{S\sim d,A\sim \pi }\left[{\nabla }_{\theta }\ln \pi (A|S,{\theta }_t)q_{\pi }(S,A)\right]⟶{\nabla }_{\theta }\ln \pi (a|s,{\theta }_t)q_{\pi }(s,a)$$
$S$ 的采样：$S\sim d$，其中分布 $d$ 是 $\pi$ 下的长期行为。

$A$ 的采样：$A\sim \pi (A|S,\theta )$。 因此，$a_t$ 应该在 $s_t$ 处的 $\pi ({\theta }_t)$ 之后进行采样。

因此，策略梯度方法是on-policy的。

How to interpret this algorithm?

因为：
$${\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)=\frac{{\nabla }_{\theta }\pi (a_t|s_t,{\theta }_t)}{\pi (a_t|s_t,{\theta }_t)}$$
因此，算法可以写为：
$$\begin{array}{rl}{\theta }_{t+1}& \begin{array}{r}={\theta }_t+\alpha {\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)q_t(s_t,a_t)\end{array}\\ & ={\theta }_t+\alpha \underset{{\beta }_t}{\underbrace{\left(\frac{q_t(s_t,a_t)}{\pi (a_t|s_t,{\theta }_t)}\right)}}{\nabla }_{\theta }\pi (a_t|s_t,{\theta }_t).\end{array}$$
因此，有算法的重要表达式：
$${\theta }_{t+1}={\theta }_t+\alpha {\beta }_t{\nabla }_{\theta }\pi (a_t|s_t,{\theta }_t)$$
它是一种最大化 $\pi (a_t|s_t,\theta )$ 的梯度上升算法：
$${\theta }_{t+1}={\theta }_t+\alpha {\beta }_t{\nabla }_{\theta }\pi (a_t|s_t,{\theta }_t)$$
当$\alpha {\beta }_t$足够小时：

如果 ${\beta }_t>0$，选择 $(s_t,a_t)$ 的概率就会增强：
$$\pi (a_t|s_t,{\theta }_{t+1})>\pi (a_t|s_t,{\theta }_t)$$
${\beta }_t$越大，增强作用越强。

如果 ${\beta }_t<0$，则 ${\pi }_{(}{a}_t|s_t,{\theta }_{t+1})<\pi (a_t|s_t,{\theta }_t)$。

当 ${\theta }_{t+1}-{\theta }_t$ 足够小时，有：
$$\begin{array}{rl}\pi (a_t|s_t,{\theta }_{t+1})& \approx \pi (a_t|s_t,{\theta }_t)+({\nabla }_{\theta }\pi (a_t|s_t,{\theta }_t){)}^T({\theta }_{t+1}-{\theta }_t)\\ & =\pi (a_t|s_t,{\theta }_t)+\alpha {\beta }_t({\nabla }_{\theta }\pi (a_t|s_t,{\theta }_t){)}^T({\nabla }_{\theta }\pi (a_t|s_t,{\theta }_t))\\ & =\pi (a_t|s_t,{\theta }_t)+\alpha {\beta }_t\Vert {\nabla }_{\theta }\pi (a_t|s_t,{\theta }_t){\Vert }^2\end{array}$$

$${\theta }_{t+1}={\theta }_t+\alpha \underset{{\beta }_t}{\underbrace{\left(\frac{q_t(s_t,a_t)}{\pi (a_t|s_t,{\theta }_t)}\right)}}{\nabla }_{\theta }\pi (a_t|s_t,{\theta }_t)$$

系数${\eta }_t$可以很好地平衡勘探 exploration 和开采 exploitation。

首先，${\eta }_t$ 与 $q_t(s_t,a_t)$ 成正比

• 如果$q_t(s_t,a_t)$ 很大，则${\beta }_t$ 也很大。
• 因此，算法旨在增强具有更大价值的action。

其次，${\beta }_t$ 与 $\pi (a_t|s_t,{\theta }_t)$ 成反比。

• 如果 $\pi (a_t|s_t,{\theta }_t)$ 较小，则 ${\beta }_t$ 较大。
• 因此，算法旨在探索概率较低的action。

因此，
$${\theta }_{t+1}={\theta }_t+\alpha {\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)q_{\pi }(s_t,a_t)$$
被替换为：
$${\theta }_{t+1}={\theta }_t+\alpha {\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)q_t(s_t,a_t)$$
其中， $q_t(s_t,a_t)$ 是 $q_{\pi }(s_t,a_t)$ 的近似值。

• 如果 $q_{\pi }(s_t,a_t)$ 通过Monte Carlo 估计来近似，则该算法有一个具体名称：REINFORCE。
• REINFORCE 是最早、最简单的策略梯度算法之一。
• 许多其他策略梯度算法（例如 actor-critic 方法）可以通过扩展 REINFORCE 来获得。

Summary

Contents of this lecture：

• Metrics for optimality
• Gradients of the metrics
• Gradient-ascent algorithm
• A special case: REINFORCE

以上内容为B站西湖大学智能无人系统 强化学习的数学原理 公开课笔记。