强化学习思考（7）策略梯度

6 minute read

Published:

关于策略梯度的注意事项。

目录

基本定义

Trajectory $\tau$

动作 action 和状态 state 的轨迹序列，表示为：

\[\tau=\left\{s_{1}, a_{1}, s_{2}, a_{2}, \cdots, s_{T}, a_{T}\right\}\]

Policy of actor $\pi_\theta(a \mid s)$

Policy 可以理解为一个包含参数 $\theta$ 的神经网络，该网络将状态 state 作为模型的输入，输出对应行动 action 的概率分布。

Probability $p_{\theta}(\tau)$

给定神经网络参数 $\theta$ 的情况下，出现轨迹序列 $\tau$ 的概率为：

\[\begin{aligned} p_{\theta}(\tau) &=p\left(s_{1}\right) \pi_{\theta}\left(a_{1} | s_{1}\right) p\left(s_{2} | s_{1}, a_{1}\right) \pi_{\theta}\left(a_{2} | s_{2}\right) p\left(s_{3} | s_{2}, a_{2}\right) \cdots \\ &=p\left(s_{1}\right) \prod_{t=1}^{T} \pi_{\theta}\left(a_{t} | s_{t}\right) p\left(s_{t+1} | s_{t}, a_{t}\right) \end{aligned}\]

The goal of reinforcement learning

最大化期望总奖励 reward：基于轨迹序列 $\tau$ 的概率分布下的期望总奖励 reward。

\[\theta^{\star} = \arg \max _{\theta} E_{\tau \sim p_{\theta}(\tau)}\left[\sum_{t} r\left(s_{t}, a_{t}\right)\right]\]

在 Finite horizon case：

\[\theta^{\star} =\arg \max _{\theta} \sum_{t=1}^{T} E_{\left(s_{t}, a_{t}\right) \sim p_{\theta}\left(s_{t}, a_{t}\right)}\left[r\left(s_{t}, a_{t}\right)\right]\]

在 Infinite horizon case：

\[\begin{aligned} \theta^{\star}&=\arg \max _{\theta} \lim_{T \to \infty}\frac{1}{T} \sum_{t=1}^{T} E_{\left(s_{t}, a_{t}\right) \sim p_{\theta}\left(s_{t}, a_{t}\right)}\left[r\left(s_{t}, a_{t}\right)\right] \\ &= \arg \max _{\theta} E_{(s, a) \sim p_{\theta}(s, a)}[r(s, a)] \end{aligned}\]

注意这里的 $p_{\theta}(s, a)$ 需要是稳态分布，参考强化学习思考（3）马尔可夫决策过程中的 Ergodic MDP

策略梯度 Policy Gradient

模型定义

目标函数

定义期望总奖励 reward 为模型的目标函数，其中通过采样的方法来近似期望。

\[J(\theta) = E_{\tau \sim p_{\theta}(\tau)}\left[\sum_{t} r\left(s_{t}, a_{t}\right)\right] = \int p_{\theta}(\tau) r(\tau)d\tau \\ \approx \frac{1}{N}\sum_i r(\tau_i) =\frac{1}{N}\sum_i \sum_t r\left(s_{i,t}, a_{i,t}\right)\]

其中

\[r(\tau) = \sum_{t} r\left({s}_{t}, {a}_{t}\right)\]

求解梯度

得出目标函数之后，就需要根据目标函数求解目标函数最大值以及最大值对应的 policy 的参数 $\theta$，因此需要采取的方法是梯度上升。

\[\begin{aligned} &\nabla_\theta J(\theta) \\ =&\int \nabla_\theta p_{\theta}(\tau) r(\tau) d\tau \\ =&\int p_{\theta}(\tau) \frac{\nabla_\theta p_{\theta}(\tau)}{p_{\theta}(\tau)}r(\tau) d\tau\\ =&\int p_{\theta}(\tau) \nabla_\theta \log p_{\theta}(\tau) r(\tau) d\tau \quad\fbox{1} \\ =&E_{\tau \sim p_{\theta}(\tau)}\left[ \nabla_\theta \log p_{\theta}(\tau)r(\tau)\right] \\ \approx &\frac{1}{N} \sum_{i=1}^{N} \nabla_\theta \log p_{\theta}\left(\tau_{i}\right) r\left(\tau_{i}\right) \quad\fbox{2} \\ =&\frac{1}{N} \sum_{i=1}^{N} \left(\sum_{t=1}^{T} \nabla_\theta \log \pi_{\theta}\left(a_{i,t} | s_{i,t}\right) \right) \left(\sum_{t=1}^{T} r\left({s}_{i,t}, {a}_{i,t}\right) \right) \quad\fbox{3} \end{aligned}\]

注：

$\fbox{1}$ 因为

\[\nabla_\theta\log{p_{\theta}(\tau)}= \frac{1}{p_{\theta}(\tau)} \nabla_\theta p_{\theta}(\tau)\]

此外使用 $\frac{\nabla p_{\theta}(\tau)}{p_{\theta}(\tau)}$ 这种方法还可以达到归一化的效果，通过除以每个 $\tau$ 出现的概率归一化每个 $\tau$ 出现的概率，这样就不会使算法更加倾向于提高出现概率高但总 reward 比较低的 $\tau$ 的概率，而是会提高总 reward 比较高的 $\tau$ 的概率。

$\fbox{2}$ 因为训练的过程中会进行采样训练，采样个数为 $N$，因此公式可以近似表示为 $N$ 次采样得到的 reward 的平均。

$\fbox{3}$ 因为

\[{\log p_\theta(\tau)} {=\log p\left(s_{1}\right)+\sum_{t=1}^{T} \log \pi_\theta \left(a_{t} | s_{t}\right)+\log p\left(r_{t}, s_{t+1} | s_{t}, a_{t}\right)}\]

$p_{\theta}(\tau)$ 中只有 $\pi_{\theta}\left(a_{t} \mid s_{t}\right)$ 项与 $\theta$ 有关，其他项相当于常数，求导之后就没了，而且导数项可以放在求和号里面。

梯度更新

使用当前的 $\pi_{\theta}$ 来采样多个回合的 $\tau$，然后使用采样得到的 $\tau$ 来更新 $\theta$，再用新的 $\pi_{\theta}$ 来重新采样多个回合的 $\tau$ 来更新 $\theta$。

\[\theta \leftarrow \theta+\eta \nabla \overline{R}_{\theta}\]

算法流程

  • step 1、sample $\tau_{i}$ from $\pi_{\theta}$ (run the policy)

  • step 2、compute the gradient

\[\nabla_{\theta} J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \left(\sum_{t=1}^{T} \nabla_\theta \log \pi_{\theta}\left(a_{i,t} \mid s_{i,t}\right) \right) \left(\sum_{t=1}^{T} r\left({s}_{i,t}, {a}_{i,t}\right) \right)\]
  • step 3、$\theta \leftarrow \theta+\alpha \nabla_{\theta} J(\theta)$

策略梯度算法分析

策略梯度与最大化似然

  • 策略梯度 Policy Gradient
\[\nabla_{\theta} J_{PG}(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \left(\sum_{t=1}^{T} \nabla_\theta \log \pi_{\theta}\left(a_{i,t} | s_{i,t}\right) \right) \left(\sum_{t=1}^{T} r\left({s}_{i,t}, {a}_{i,t}\right) \right)\]
  • 最大化似然 Maximum Likelihood
\[\nabla_{\theta} J_{ML}(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \left(\sum_{t=1}^{T} \nabla_\theta \log \pi_{\theta}\left(a_{i,t} | s_{i,t}\right) \right)\]

这两条式子从一定程度上说明了强化学习与监督学习的不同：

  • 监督学习的样本标签是人工标注为“对”的，可以直接用来学习
    • 更新策略使得样本出现的概率越来越高
  • 强化学习的样本“标签”是根据策略选出来的，需要辅助奖励来进行学习
    • 强化学习是一种试错学习 tail and error
    • 更新策略使得奖励大的样本出现的概率越来越高

Partial observability

由于式子中没有利用到 Markov property，所以可以直接将策略梯度用于 Partially observed MDPs

\[\nabla_{\theta} J_{PG}(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \left(\sum_{t=1}^{T} \nabla_\theta \log \pi_{\theta}\left(a_{i,t} | o_{i,t}\right) \right) \left(\sum_{t=1}^{T} r\left({s}_{i,t}, {a}_{i,t}\right) \right)\]
  • 根据前面的推导，即使 $p_\theta(\tau)$ 中包含 $p(o \mid s)$，在求解 $log$ 并求导之后也会消掉。

High Variance

首先简化一下式子方便我们分析：

\[\nabla_{\theta} J_{PG}(\theta) = E_{\tau \sim \pi_\theta (\tau)} [\nabla_\theta \log \pi_{\theta}\left(\tau\right) r(\tau) ] \approx \frac{1}{N} \sum_{i=1}^{N} \nabla_\theta \log \pi_{\theta}\left(\tau\right) r(\tau)\]

其中

\[\nabla_\theta \log \pi_{\theta}(\tau) = \sum_{t} \nabla_\theta \log \pi_{\theta}\left({s}_{t}, {a}_{t}\right) \\ r(\tau) = \sum_{t} r\left({s}_{t}, {a}_{t}\right)\]

前面说到强化学习是试错学习，它会更新策略使得奖励大的样本出现的概率越来越高，但由于训练过程中采样是随机的，可能会出现某个 $\tau$ 不被采样的情况。

  • 如果 $r(\tau)$ 只有正的情况，那么被采样到的 $\tau$ 的概率就会增加，这会导致没被采样到的 $\tau$ 的概率下降
  • 因为采取的 $\tau$ 概率和为 1，可能存在归一化之后，好的 $\tau$ 的概率相对下降，坏的 $\tau$ 概率相对上升的情况。
  • 如果最好的 $\tau$ 的 $r(\tau)=0$，那么采样到这些 $\tau$ 并不会更新策略提高其概率，因为此时计算得到的梯度为 0。
  • 此外该目标函数基于 $r(\tau)$ 对策略的更新是很敏感的，如果采样到三个 $r(\tau)$，两正一负，更新的幅度会比较大（两个概率要增加，一个要减少），但如果给这三个 $r(\tau)$ 都加上一个常数使得其都为正，这时候其实更新的幅度会变小（三个的概率都要增加），虽然三个 $r(\tau)$ 的相对差不变，但是更新的幅度却不一样了，后者的方差明显比前者更大（概率密度曲线更平缓）。

在有限采样的情况下，结果很依赖于初始策略的采样，导致了高方差问题，虽然增加样本能缓解这种高方差，但是增加样本也使得学习效率降低，下面介绍几种减少高方差的方法。

Causal reward

由因果关系（casuality）考虑到在时间 $t$ 采取的行动 action 与 $t$ 时期之前的奖励 reward 无关，因此只需要将 $t$ 时刻开始到结束的 reward 进行加总。

原函数

\[\nabla_{\theta} J_{PG}(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \left(\sum_{t=1}^{T} \nabla_\theta \log \pi_{\theta}\left(a_{i,t} | s_{i,t}\right) \right) \left(\sum_{t=1}^{T} r\left({s}_{i,t}, {a}_{i,t}\right) \right) \\ = \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} \left[\nabla_\theta \log \pi_{\theta}\left(a_{i,t} | s_{i,t}\right) \sum_{t'=1}^{T} r\left({s}_{i,t'}, {a}_{i,t'}\right) \right]\]

修改为

\[\nabla_{\theta} J_{PG}(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} \left[\nabla_\theta \log \pi_{\theta}\left(a_{i,t} | s_{i,t}\right) \sum_{t'=t}^{T} r\left({s}_{i,t'}, {a}_{i,t'}\right) \right]\]

通过这样做数值求和上减少了，方差也倾向于随之减少。

Baesline

我们希望好的轨迹的奖励函数是正的，而差的轨迹是负的，然而之前也提到了它对值非常敏感，如果奖励函数增加或者减少一个常数，结果就会很不同。因此需要引入一个基准线 baseline $b$。

\[\nabla_{\theta} J_{PG}(\theta) = E_{\tau \sim \pi_\theta (\tau)} [\nabla_\theta \log \pi_{\theta}\left(\tau\right) \left( r(\tau) - b \right) ] \\ \approx \frac{1}{N} \sum_{i=1}^{N} \nabla_\theta \log \pi_{\theta}\left(\tau\right) \left( r(\tau) - b \right)\]

证明无偏

可证明这里引入 baesline 不会改变期望的值，是无偏的

\[E_{\tau \sim \pi_\theta (\tau)} \left[\nabla_{\theta} \log \pi_{\theta}(\tau) b\right]=\int \pi_{\theta}(\tau) \nabla_{\theta} \log \pi_{\theta}(\tau) b d \tau \\=\int \nabla_{\theta} \pi_{\theta}(\tau) b d \tau=b \nabla_{\theta} \int \pi_{\theta}(\tau) d \tau=b \nabla_{\theta} 1=0\]

另外的角度：即使 baesline 是 state 相关的也是无偏的

\[\begin{aligned} &E_{(s, a) \sim p_{\theta}(s, a)}\left[\nabla_{\theta} \log \pi_{\theta}(s,a) b(s)\right] \\=&\int d^{\pi_{\theta}}(s) \int \nabla_{\theta} \log \pi_{\theta}(s,a) b(s) d a ds \\=&\int d^{\pi_{\theta}}(s) b(s) \int \nabla_{\theta} \log \pi_{\theta}(s,a) d a ds \\=& \int d^{\pi_{\theta}}(s) b(s) \nabla_{\theta} \int \log \pi_{\theta}(s,a) d a ds \\=& \int d^{\pi_{\theta}}(s) b(s) \nabla_{\theta} 1 \\=&0 \end{aligned}\]

其中 $b$ 可以自己设置。

使用 average reward 作为 baseline \(b = \frac{1}{N} \sum_{i=1}^N r(\tau_i)\)

求解使得方差最小的 baseline

因为 $Var[x] = E[x^2] - E[x]^2$，所以

\[\begin{aligned} Var &= E_{\tau \sim \pi_\theta (\tau)} [(\nabla_\theta \log \pi_{\theta}\left(\tau\right) \left( r(\tau) - b \right) )^2] - E_{\tau \sim \pi_\theta (\tau)} [\nabla_\theta \log \pi_{\theta}\left(\tau\right) \left( r(\tau) - b \right) ]^2 \\ &= E_{\tau \sim \pi_\theta (\tau)} [(\nabla_\theta \log \pi_{\theta}\left(\tau\right) \left( r(\tau) - b \right) )^2] - E_{\tau \sim \pi_\theta (\tau)} [\nabla_\theta \log \pi_{\theta}\left(\tau\right) r(\tau)]^2 \end{aligned}\]

求导得

\[\begin{aligned} \frac{dVar}{db} &= \frac{d}{db}E_{\tau \sim \pi_\theta (\tau)} [(\nabla_\theta \log \pi_{\theta}\left(\tau\right) \left( r(\tau) - b \right) )^2] \\&= \frac{d}{db}(E[(\nabla_\theta \log \pi_{\theta}\left(\tau\right))^2 r(\tau)^2] -2 E[(\nabla_\theta \log \pi_{\theta}\left(\tau\right))^2 r(\tau)b]+ b^2E[(\nabla_\theta \log \pi_{\theta}\left(\tau\right))^2]) \\&= -2 E[(\nabla_\theta \log \pi_{\theta}\left(\tau\right))^2 r(\tau)]+ 2bE[(\nabla_\theta \log \pi_{\theta}\left(\tau\right))^2]) \\&=0 \end{aligned}\]

解得

\[b = \frac{E[(\nabla_\theta \log \pi_{\theta}\left(\tau\right))^2 r(\tau)]}{ E[(\nabla_\theta \log \pi_{\theta}\left(\tau\right))^2])}\]

这其实是加权了梯度大小的期望奖励（expected reward weighted by gradient magnitudes）

Policy Gradient Theorem

Policy Objective Functions

  • In episodic environments we can use the start value
\[J_{1}(\theta)=V^{\pi_{\theta}}\left(s_{1}\right)=E_{\pi_{\theta}}\left[v_{1}\right]\]
  • In continuing environments we can use the average value
\[J_{a v V}(\theta)=\sum_{s} d^{\pi_{\theta}}(s) V^{\pi_{\theta}}(s)\]
  • Or the average reward per time-step
\[J_{a v R}(\theta)=\sum_{s} d^{\pi_{\theta}}(s) \sum_{a} \pi_{\theta}(s, a) \mathcal{R}_{s}^{a}\]

where $d^\pi(s)$ is stationary distribution of Markov chain for $\pi_\theta$

Theorem

For any differentiable policy $\pi_{\theta}(s, a)$,

for any of the policy objective functions $J = J_1$, $J_{avR}$, or $\frac{1}{1-\gamma} J_{avV}$,

the policy gradient is

\[\nabla_{\theta} J(\theta) = E_{\pi_\theta} [\nabla_\theta \log \pi_{\theta}\left(s,a\right) Q^{\pi_\theta}(s,a) ]\]

Advantages of Policy-Based RL

Advantages:

  • Monte-Carlo Policy Gradient is unbiased

  • Better convergence properties
  • Effective in high-dimensional or continuous action spaces
  • Can learn stochastic policies
    • in some case we don’t need a deterministic policy, maybe a uniform random policy is optimal (i.e. Nash equilibrium)
    • Value-based RL learns a near-deterministic policy (e.g. greedy or ε-greedy)

Disadvantages:

  • Typically converge to a local rather than global optimum
  • Evaluating a policy is typically inefficient and high variance

参考资料及致谢

所有参考资料在前言中已列出，再次向强化学习的大佬前辈们表达衷心的感谢！