Shu Wang

Silence maks big money

(强化学习)- 深入策略梯度

Policy Gradient

记号

符号 解释
$s\in\mathcal{S}$ 状态空间
$a\in\mathcal{A}$ 行为空间
$r\in\mathcal{R}$ 回报
$S_t, A_t, R_t$ 轨迹序列中的状态, 行为和回报, 也可以记为$s_t, a_t, r_t$
$\gamma$ 折扣因子
$G_t$ 带折扣的未来回报, 定义为$G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$
$P(s', r \vert s, a)$ 从状态$s$采取行动$a$转移到状态$s'$且回报为$r$的转移概率
$\pi(a\vert{s})$ 在状态$s$下采取行动$a$的随机(stochastic)概率
$\mu(s)$ 确定性(deterministic)策略. 与$\pi$一样, 这都是 RL 需要学习的目标
$V(s)$ state-value 函数, 用于描述状态$s$的期望的价值(expected return)
$V^\pi(s)$ 依赖策略$\pi$给出的: $V^\pi (s) = \mathbb{E}_{a\sim \pi} [G_t \vert S_t = s]$
$Q(s,a)$ action-value 函数, 用于描述来自于状态, 行为对$(s,a)$的期望价值
$Q^\pi(s,a)$ 依赖策略$\pi$给出$Q^\pi(s, a) = \mathbb{E}_{a\sim \pi} [G_t \vert S_t = s, A_t = a]$
$A(s,a)$ advantage 函数, 定义见下文

按照之前的文章, 定义回报函数(reward function):$$J(\theta)
= \sum_{s \in \mathcal{S}} d^\pi(s) V^\pi(s)
= \sum_{s \in \mathcal{S}} d^\pi(s) \sum_{a \in \mathcal{A}} \pi_\theta(a \vert s) Q^\pi(s, a)$$

其中$d^\pi(s)$是估计的策略$\pi_\theta$的马尔可夫链(on-policy, 策略为$\pi$的状态分布)中的平稳分布.

基于策略的算法与之前的算法有者不同的一点是: 适用于连续空间. 在这种空间下, 有无数的行为和状态需要取估计, 基于值函数(value-based)的方法的计算复杂度太高了. 例如在策略迭代中, 策略改进是通过$\arg\max_{a\in\mathcal{A}}A^\pi(s,a)$, 其需要知悉整个行为空间, 这就会导致维数灾难(curse of dimensionality)

理论

策略梯度:

$$
\begin{aligned}
\nabla_\theta J(\theta)
&= \nabla_\theta \sum_{s \in \mathcal{S}} d^\pi(s) \sum_{a \in \mathcal{A}} Q^\pi(s, a) \pi_\theta(a \vert s) \\
&\propto \sum_{s \in \mathcal{S}} d^\pi(s) \sum_{a \in \mathcal{A}} Q^\pi(s, a) \nabla_\theta \pi_\theta(a \vert s)
\end{aligned}
$$

关于策略梯度的证明

首先看到的是关于状态-值函数:

$$\begin{aligned}
& \nabla_\theta V^\pi(s) \\
=& \nabla_\theta \Big(\sum_{a \in \mathcal{A}} \pi_\theta(a \vert s)Q^\pi(s, a) \Big) & \\
=& \sum_{a \in \mathcal{A}} \Big( \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) + \pi_\theta(a \vert s) \color{red}{\nabla_\theta Q^\pi(s, a)} \Big) & \scriptstyle{\text{; 导数乘法}} \\
=& \sum_{a \in \mathcal{A}} \Big( \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) + \pi_\theta(a \vert s) \color{red}{\nabla_\theta \sum_{s', r} P(s',r \vert s,a)(r + V^\pi(s'))} \Big) & \scriptstyle{\text{; 展开 } Q^\pi \text{ 为使用未来价值的表示}} \\
=& \sum_{a \in \mathcal{A}} \Big( \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) + \pi_\theta(a \vert s) \color{red}{\sum_{s', r} P(s',r \vert s,a) \nabla_\theta V^\pi(s')} \Big) & \scriptstyle{P(s',r \vert s,a) \text{ 或 } r \text{ 与 }\theta\text{无关}}\\
=& \sum_{a \in \mathcal{A}} \Big( \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) + \pi_\theta(a \vert s) \color{red}{\sum_{s'} P(s' \vert s,a) \nabla_\theta V^\pi(s')} \Big) & \scriptstyle{\text{; 因为 } P(s' \vert s, a) = \sum_r P(s', r \vert s, a)}
\end{aligned}
$$

则有:

$$
\begin{equation}
\color{red}{\nabla_\theta V^\pi(s)}
= \sum_{a \in \mathcal{A}} \Big( \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) + \pi_\theta(a \vert s) \sum_{s'} P(s' \vert s,a) \color{red}{\nabla_\theta V^\pi(s')} \Big)
\label{v_pi_geadient}
\end{equation}
$$

公式中有递归形式(红色部分)因此未来的state-value 函数$V^\pi(s')$能够被替换为相同的展开后的部分.

举个例子, 假设基于策略$\pi_\theta$通过$k$时间从状态$s$转移到状态$x$, 记为$\rho^\pi(s\rightarrow{x},k)$:

$$s \xrightarrow[]{a \sim \pi_\theta(.\vert s)} s' \xrightarrow[]{a \sim \pi_\theta(.\vert s')} s'' \xrightarrow[]{a \sim \pi_\theta(.\vert s'')} \dots
$$

其中:

  • $k=0$: $\rho^\pi(s\rightarrow{s},k=0)=1$
  • $k=1$: 需要扫描状态$s$转移到之后的状态的联合概率:$\rho^\pi(s\rightarrow{s},k=1)=\sum_a{\pi_\theta(a|s)P(s'|s,a)}$
  • 目标是从状态$s$经过$k+1$时间到状态$x$, 我们都会在时间步$k$的时候经过任何一个中间状态($s'\in\mathcal{S}$)然后临门一脚转移到状态$x$. 在这种情况下, 我们可以递归地更新访问(visitation)概率: $\rho^\pi(s \to x, k+1) = \sum_{s'} \rho^\pi(s \to s', k) \rho^\pi(s' \to x, 1)$

重新回到之前的梯度的递归定义:$\eqref{v_pi_geadient}$. 令$\phi(s) = \sum_{a \in \mathcal{A}} \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a)$无限地展开$\nabla_\theta{V^\pi(\cdot)}$我们能够得到从状态$s$转移到任何一个给定时间之后地状态.

$$
\begin{aligned}
& \color{red}{\nabla_\theta V^\pi(s)} \\
=& \phi(s) + \sum_a \pi_\theta(a \vert s) \sum_{s'} P(s' \vert s,a) \color{red}{\nabla_\theta V^\pi(s')} \\
=& \phi(s) + \sum_{s'} \sum_a \pi_\theta(a \vert s) P(s' \vert s,a) \color{red}{\nabla_\theta V^\pi(s')} \\
=& \phi(s) + \sum_{s'} \rho^\pi(s \to s', 1) \color{red}{\nabla_\theta V^\pi(s')} \\
=& \phi(s) + \sum_{s'} \rho^\pi(s \to s', 1) \color{red}{\nabla_\theta V^\pi(s')} \\
=& \phi(s) + \sum_{s'} \rho^\pi(s \to s', 1) \color{red}{[ \phi(s') + \sum_{s''} \rho^\pi(s' \to s'', 1) \nabla_\theta V^\pi(s'')]} \\
=& \phi(s) + \sum_{s'} \rho^\pi(s \to s', 1) \phi(s') + \sum_{s''} \rho^\pi(s \to s'', 2)\color{red}{\nabla_\theta V^\pi(s'')} \scriptstyle{\text{ ; 其中 }s'\text{ 作为从状态 }s \to \text{转移到状态}s''\text{的中间状态}}\\
=& \phi(s) + \sum_{s'} \rho^\pi(s \to s', 1) \phi(s') + \sum_{s''} \rho^\pi(s \to s'', 2)\phi(s'') + \sum_{s'''} \rho^\pi(s \to s''', 3)\color{red}{\nabla_\theta V^\pi(s''')} \\
=& \dots \scriptstyle{\text{; 重复地展开剩下的部分 }\nabla_\theta V^\pi(.)} \\
=& \sum_{x\in\mathcal{S}}\sum_{k=0}^\infty \rho^\pi(s \to x, k) \phi(x)
\end{aligned}
$$

如果把$J(\theta)$替换为状态-行为值函数(Q-value function), 可以得到:

$$
\begin{aligned}
\nabla_\theta J(\theta)
&= \nabla_\theta V^\pi(s_0) & \scriptstyle{\text{; 初始状态 } s_0} \\
&= \sum_{s}\color{blue}{\sum_{k=0}^\infty \rho^\pi(s_0 \to s, k)} \phi(s) &\scriptstyle{\text{; 令 }\color{blue}{\eta(s) = \sum_{k=0}^\infty \rho^\pi(s_0 \to s, k)}} \\
&= \sum_{s}\eta(s) \phi(s) & \\
&= \Big( {\sum_s \eta(s)} \Big)\sum_{s}\frac{\eta(s)}{\sum_s \eta(s)} \phi(s) & \scriptstyle{\text{; 标准化 } \eta(s), s\in\mathcal{S} \text{ 是一个分布}}\\
&\propto \sum_s \frac{\eta(s)}{\sum_s \eta(s)} \phi(s) & \scriptstyle{\sum_s \eta(s)\text{ 是常数}} \\
&= \sum_s d^\pi(s) \sum_a \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) & \scriptstyle{d^\pi(s) = \frac{\eta(s)}{\sum_s \eta(s)}\text{ 是平稳分布}}
\end{aligned}
$$

在 episodic 任务中, 常数$\sum_s{\eta(s)}$是一次 episode 的平均长度, 在连续人物中, 为 1. 梯度可以写作:

$$
\begin{aligned}
\nabla_\theta J(\theta)
&\propto \sum_{s \in \mathcal{S}} d^\pi(s) \sum_{a \in \mathcal{A}} Q^\pi(s, a) \nabla_\theta \pi_\theta(a \vert s) &\\
&= \sum_{s \in \mathcal{S}} d^\pi(s) \sum_{a \in \mathcal{A}} \pi_\theta(a \vert s) Q^\pi(s, a) \frac{\nabla_\theta \pi_\theta(a \vert s)}{\pi_\theta(a \vert s)} &\\
&= \mathbb{E}_\pi [Q^\pi(s, a) \nabla_\theta \ln \pi_\theta(a \vert s)] & \scriptstyle{\text{; 因为 } (\ln x)' = 1/x}
\end{aligned}
$$

其中$\mathbb{E}_\pi$指的是$\mathbb{E}_{s\sim{d_\pi},a\sim{\pi_\theta}}$(状态分布和行为分布都遵循策略$\pi_\theta$, on policy).

假设和问题陈述

按照之前的叙述, 一个完整的序列轨迹(trajectories)是一个完整的从开始到结束的状态的 episode 序列, 即 episodic 性. 定义长度为$T$的轨迹$\tau$:

$$\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \ldots, s_{T-1}, a_{T-1}, r_{T-1}, s_T)$$

$s_0$通常来自于状态的分布$a_i\sim\pi_\theta(a_i|s_i)$, 当前环境采取 action 之后的状态$s_i\sim{P(s_i|s_{i-1},a_{a-1})}$

与之前的 DQN 采用求最优的 Q-values 不同间接求最优策略, 策略梯度直接计算最优策略. 公式化后:

$$\max_{\theta}\mathbb{E_{\pi_\theta}}\left[{\sum_{t=0}^{T-1}\gamma^tr_t}\right]$$

现在的问题就是如何求最优的策略, 即最好的参数$\theta$.

计算技巧

之前的文章我们给出了如何求$f(x)$的期望的梯度, 其中$p_\theta$是随机变量$x$的参数化后的概率密度函数:

$$
\begin{equation}
\nabla_\theta\mathbb{E}[f(x)]=\mathbb{E}[f(x)\nabla_\theta\log{p_\theta(x)}]
\label{trick1}
\end{equation}
$$

在上面的公式中, 令$x$为$\tau$可以得到

$$\begin{aligned}
\nabla_\theta \log p_\theta(\tau) &= \nabla \log \left(\mu(s_0) \prod_{t=0}^{T-1} \pi_\theta(a_t|s_t)P(s_{t+1}|s_t,a_t)\right) \\
&= \nabla_\theta \left[\log \mu(s_0)+ \sum_{t=0}^{T-1} (\log \pi_\theta(a_t|s_t) + \log P(s_{t+1}|s_t,a_t)) \right]\\
&= \nabla_\theta \sum_{t=0}^{T-1}\log \pi_\theta(a_t|s_t)
\end{aligned}$$

计算原始梯度

定义$R(\tau)$为需要最大化的价值函数, 使用上述的两个技巧:

$$\nabla_\theta \mathbb{E}_{\tau \sim \pi_\theta}[R(\tau)] = \mathbb{E}_{\tau \sim
\pi_\theta} \left[R(\tau) \cdot \nabla_\theta \left(\sum_{t=0}^{T-1}\log
\pi_\theta(a_t|s_t)\right)\right]$$

当然平均价值函数也是可以使用的: 见

$\tau$中的状态来自于策略$\pi_\theta$, 也就是$\tau\sim\pi_\theta$. 实际上, 这是一个经验期望(empirical expectation)以估计实际的期望. 如果直接使用梯度下降得到最优参数不仅很慢还会带来在梯度估计上的高方差(high variance), 得到结果时好时坏. 为了降低偏差有很多的方法, 引入 baseline 就是解决方案之一

Baseline

解决高方差的方法之一. 简化的累计回报:$R(\tau)=\sum_{t=0}^{T-1}r_t$

重新表述策略梯度:

$$\begin{aligned}
\nabla_\theta \mathbb{E}_{\tau \sim \pi_\theta}\Big[R(\tau)\Big] \;&{\overset{(i)}{=}}\; \mathbb{E}_{\tau \sim \pi_\theta} \left[\left(\sum_{t=0}^{T-1}r_t\right) \cdot \nabla_\theta \left(\sum_{t=0}^{T-1}\log \pi_\theta(a_t|s_t)\right)\right] \\
&{\overset{(ii)}{=}}\; \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t'=0}^{T-1} r_{t'} \sum_{t=0}^{t'}\nabla_\theta \log \pi_\theta(a_t|s_t)\right] \\
&{\overset{(iii)}{=}}\; \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t) \left(\sum_{t'=t}^{T-1}r_{t'}\right) \right]
\end{aligned}
$$

关于公式的解释:

i: 按照计算技巧$\eqref{trick1}$展开

ii: 将$\tau$压缩为一个确定的事件$t'$, 此时的及时回报为$r_{t'}$. 则按照计算技巧$\eqref{trick1}$, 梯度为:

$$\nabla_\theta
\mathbb{E}_{\tau}\Big[r_{t'}\Big] = \mathbb{E}_\tau\left[r_{t'} \cdot
\sum_{t=0}^{t'} \nabla_\theta \log \pi_\theta(a_t|s_t)\right]$$

然后目标是计算:

$$
\begin{aligned}
\nabla_\theta \mathbb{E}_{\tau \sim \pi_\theta} \left[ R(\tau) \right] &= \nabla_\theta \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t'=0}^{T-1} r_{t'}\right] \\
&= \sum_{t'=0}^{T-1}\nabla_\theta \mathbb{E}_{\tau^{(t')}} \Big[r_{t'}\Big] \\
&= \sum_{t'}^{T-1} \mathbb{E}_{\tau^{(t')}}\left[r_{t'} \cdot \sum_{t=0}^{t'} \nabla_\theta \log \pi_\theta(a_t|s_t)\right] \\
&= \mathbb{E}_{\tau \sim \pi_\theta}\left[ \sum_{t'}^{T-1} r_{t'} \cdot \sum_{t=0}^{t'} \nabla_\theta \log \pi_\theta(a_t|s_t)\right]
\end{aligned}
$$

$\tau^{(t')}$表示的是结束是为$t'$的轨迹$\tau$.

iii: 为了简化表示, $f_t := \nabla_\theta \log \pi_\theta(a_t|s_t)$. 除此之外, 忽略公式中的期望, 在ii公式期望的计算中有(两个求和):

$$\begin{aligned}
r_0f_0 &+ \\
r_1f_0 &+ r_1f_1 + \\
r_2f_0 &+ r_2f_1 + r_2f_2 + \\
\cdots \\
r_{T-1}f_0 &+ r_{T-1}f_1 + r_{T-1}f_2 \cdots + r_{T-1}f_{T-1}
\end{aligned}
$$

如果竖(column-wise)着看, 可以总结到第一列为:$f_0\cdot{(\sum_{t=0}^{T-1})}$; 第二列为:$f_1\cdot{(\sum_{t=1}^{T-1})}$. 如果将$f_t$替换, 则得到了想要的期望.

使用上述的公式, 则引入 baseline $b$, 关于$s_t$的函数, 然后插入到公式iii的小括号中:

$$\nabla_\theta \mathbb{E}_{\tau \sim \pi_\theta}[R(\tau)] =
\mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{T-1} \nabla_\theta \log
\pi_\theta(a_t|s_t) \left(\sum_{t'=t}^{T-1}r_{t'} - b(s_t)\right) \right]$$

目前来说, 这个引入的$b$仅仅是关于$s_t$的函数, 而$s_t$仅仅依赖于时间$t$.

如何理解 Baseline

将带有 baseline 的公式展开, 得到:

$$\nabla_\theta \mathbb{E}_{\tau \sim \pi_\theta}[R(\tau)] =
\mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{T-1} \nabla_\theta \log
\pi_\theta(a_t|s_t) \left(\sum_{t'=t}^{T-1}r_{t'}\right) - \sum_{t=0}^{T-1}
\nabla_\theta \log \pi_\theta(a_t|s_t) b(s_t) \right]$$

由于期望的线性(linearity of expectation), 对于任意的时间$t$, 梯度$\log{\pi_\theta(a_t|s_t)}$乘以$b(s_t)$是0:

$$
\begin{aligned}
\mathbb{E}_{\tau \sim \pi_\theta}\Big[\nabla_\theta \log \pi_\theta(a_t|s_t) b(s_t)\Big] &= \mathbb{E}_{s_{0:t},a_{0:t-1}}\Big[ \mathbb{E}_{s_{t+1:T},a_{t:T-1}} [\nabla_\theta \log \pi_\theta(a_t|s_t) b(s_t)]\Big] \\
&= \mathbb{E}_{s_{0:t},a_{0:t-1}}\Big[ b(s_t) \cdot \underbrace{\mathbb{E}_{s_{t+1:T},a_{t:T-1}} [\nabla_\theta \log \pi_\theta(a_t|s_t)]}_{E}\Big] \\
&= \mathbb{E}_{s_{0:t},a_{0:t-1}}\Big[ b(s_t) \cdot \mathbb{E}_{a_t} [\nabla_\theta \log \pi_\theta(a_t|s_t)]\Big] \\
&= \mathbb{E}_{s_{0:t},a_{0:t-1}}\Big[ b(s_t) \cdot 0 \Big] = 0
\end{aligned}
$$

下面关于公式的解释:

  • 为了简化表述, 令轨迹$s_0,a_0,\cdots,a_{T-1},s_{T}$为$s_{0:T}, a_{0:T-1}$. 在离散的抢矿下定义行为空间为$\mathcal{A}$, 状态空间$\mathcal{S}$. 考虑两个随机变量的期望定义:

$$
\begin{aligned}
E &= \sum_{a_t\in \mathcal{A}}\sum_{s_{t+1}\in \mathcal{S}}\cdots \sum_{s_T\in \mathcal{S}} \underbrace{\pi_\theta(a_t|s_t)P(s_{t+1}|s_t,a_t) \cdots P(s_T|s_{T-1},a_{T-1})}_{p((a_t,s_{t+1},a_{t+1}, \ldots, a_{T-1},s_{T}))} (\nabla_\theta \log \pi_\theta(a_t|s_t)) \\
&= \sum_{a_t\in \mathcal{A}} \pi_\theta(a_t|s_t)\nabla_\theta \log \pi_\theta(a_t|s_t) \sum_{s_{t+1}\in \mathcal{S}} P(s_{t+1}|s_t,a_t) \sum_{a_{t+1}\in \mathcal{A}}\cdots \sum_{s_T\in \mathcal{S}} P(s_T|s_{T-1},a_{T-1})\\
&= \sum_{a_t\in \mathcal{A}} \pi_\theta(a_t|s_t)\nabla_\theta \log \pi_\theta(a_t|s_t)
\end{aligned}$$
这个可以参考概率图模型中的变量消除(variable elimination)variable elimination for graphical models

  • 当连续行为时, 也就是$T=\infty$, 在论文: Generalized Advantage Estimation的 Appendix B 中证明了$T=\infty$以及$T-1=\infty$
  • 致使期望为0的另一个现实的原因是分值函数(score function)定义为(连续形式): $\nabla_\theta{\log{\pi_\theta(a_t|s_t)}}$:

$$\mathbb{E}_{a_t}\Big[\nabla_\theta \log \pi_\theta(a_t|s_t)\Big]
= \int \frac{\nabla_\theta
\pi_\theta(a_t|s_t)}{\pi_{\theta}(a_t|s_t)}\pi_{\theta}(a_t|s_t)da_t
= \nabla_\theta \int \pi_{\theta}(a_t|s_t)da_t = \nabla_\theta \cdot 1 = 0
$$
以上都证明了 baseline 不会带来新的偏差. 所以接下来就需要说明 baseline 减小了方差. 简化的未来回报$R_t(\tau) =\sum_{t'=t}^{T-1}r_{t'}$

计算引入的方差:

$$
\begin{aligned}
{\rm Var}\left(\sum_{t=0}^{T-1}\nabla_\theta \log \pi_\theta(a_t|s_t) (R_t(\tau)-b(s_t))\right)\;&\overset{(i)}{\approx}\; \sum_{t=0}^{T-1} \mathbb{E}\tau\left[\Big(\nabla_\theta \log \pi_\theta(a_t|s_t) (R_t(\tau)-b(s_t))\Big)^2\right] \\
\;&{\overset{(ii)}{\approx}}\; \sum_{t=0}^{T-1} \mathbb{E}_\tau \left[\Big(\nabla_\theta \log \pi_\theta(a_t|s_t)\Big)^2\right]\mathbb{E}_\tau\left[\Big(R_t(\tau) - b(s_t))^2\right]
\end{aligned}$$

Approximation (i): 根据方差的定义 ${\rm Var}(X) :=\mathbb{E}[X^2]-(\mathbb{E}[X])^2$, 由于已经直到引入 baseline 不会造成偏差, 所以$\mathbb{E}[X]$可以去掉.

Approximation (ii): 留下的公式简化为$\mathbb{E}_{\tau} \left[\Big(R_t(\tau) - b(s_t))^2\right]$. 如果需要选择最优的$b(s_t)$, 这就变成了最小二乘问题(least squares), 最好的选择就是$R_t(\tau)$的期望. 事实上, PG 的研究者都希望通过$b(s_t)\approx\mathbb{E}[R_t(\tau)]$来估计从时间$t$以来的未来回报的期望.

baseline 降低方差的方法工作地很好. 如果能够将采样之间的关联性破坏, 也就是$s_0,a_0,\cdots,a_{T-1},s_{T}$不是来自于同一个轨迹, 那么Approximation (i) 表现得会更好.

如果$R_t:=G_t$则引入的代折扣因子$\gamma\in{(0,1]}$:

$$
\begin{aligned}
\nabla_\theta \mathbb{E}_{\tau \sim \pi_\theta}[R(\tau)] &= \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t) \left(\sum_{t'=t}^{T-1}r_{t'} - b(s_t)\right) \right] \\
&\approx \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t) \left(\sum_{t'=t}^{T-1}\gamma^{t'-t}r_{t'} - b(s_t)\right) \right]
\end{aligned}$$

按照之前关于 baseline 关于目标期望的叙述, baseline 定义为:

$$b(s_t) \approx \mathbb{E}[r_t + \gamma
r_{t+1} + \cdots + \gamma^{T-1-t} r_{T-1}]$$

Advantage 函数

在没有对未来回报进行折扣处理的情况下, 定义状态-值函数, 状态-行为值函数:

$$V^\pi(s) = \mathbb{E}_{\tau \sim \pi_\theta}\left[\sum_{t=0}^{T-1} r_t \;\Bigg|\; s_0=s\right]$$
$$Q^\pi(s,a) = \mathbb{E}_{\tau \sim \pi_\theta}\left[\sum_{t=0}^{T-1} r_t \;\Bigg|\; s_0=s,a_0=a\right]$$

advantage 函数的定义:

$$A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s)$$

这个函数反应了在状态$s$下选择 action $a$要比平均回报要好多少. 当然可以定义折扣未来回报的$V$和$Q$, 分别表示为$V^{\pi,\gamma}(s)$和$Q^{\pi,\gamma}(s,a)$

回到策略梯度的公式:

$$\begin{aligned}
\nabla_\theta \mathbb{E}_{\tau \sim \pi_\theta}[R(\tau)] &= \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t) \left(\sum_{t'=t}^{T-1}r_{t'} - b(s_t)\right) \right] \\
&{\overset{(i)}{=}}\; \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t) \cdot \Big(Q^{\pi}(s_t,a_t)-V^\pi(s_t)\Big) \right] \\
&{\overset{(ii)}{=}}\; \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t) \cdot A^{\pi}(s_t,a_t) \right] \\
&{\overset{(iii)}{\approx}}\; \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t) \cdot A^{\pi,\gamma}(s_t,a_t) \right]
\end{aligned}
$$

(i): 一般来说, 可以把 baseline 定义为$V^\pi$ 之后的iiiii主要是关于 advantage 函数的定义以及使用折扣的未来回报. 有些情况下, 找到关于$A^{\pi,\gamma}$的估计$\hat{A}^{\pi,\gamma}$可以参考论文: Generalized Advantage Estimation

Policy Graident 算法

如之前述, 原始梯度(vanilla policy gradient):

$$
\nabla_\theta J(\theta) = \mathbb{E}_\pi [Q^\pi(s, a) \nabla_\theta \ln \pi_\theta(a \vert s)]
$$

是一个无偏但是高方差, baseline 以及其他更多方法都保证了保持偏差降低方差.

来自于论文(Schulman et al., 2016)

策略梯度相关算法

REINFORCE

又名 Monte-Carlo policy gradient. 这个方法依赖于蒙特卡洛方法. 这个方法使用一次 episode 的样本来更新参数$\theta$, REINFORCE 因为样本的期望的梯度与实际的梯度相同才可工作:

$$
\begin{aligned}
\nabla_\theta J(\theta)
&= \mathbb{E}_\pi [Q^\pi(s, a) \nabla_\theta \ln \pi_\theta(a \vert s)] & \\
&= \mathbb{E}_\pi [G_t \nabla_\theta \ln \pi_\theta(A_t \vert S_t)] & \scriptstyle{\text{; 因为 } Q^\pi(S_t, A_t) = \mathbb{E}_\pi[G_t \vert S_t, A_t]}
\end{aligned}
$$

更新的过程依赖于完整的轨迹:

注意这个过程需要通过引入 baseline 和 advantage 函数来减小估计的方差.

Actor-Critic

通过之前的文章介绍, 策略梯度的两个主要部分: 策略模型价值函数. 加子函数能够辅助策略更新, 这也能起到降低方差的作用.

Actor-Critic 的由以下的两个模型构成:

  • Critic 更新价值函数的参数$w$. 根据算法的不同可以是更新$Q_w(a|s)$或$V_w(s)$.
  • Actor 根据 Critic 给出的"建议"更新策略$\pi_\theta(a|s)$的参数$\theta$.

简单(vanilla version)的算法:

学习率$\alpha_\theta$和$\alpha_w$分别是策略和值函数的超参数.

Off-policy 的策略梯度

REINFORCE 和简单的 actor-critic 算法都是 on-policy 方法: 所有的训练的样本都是从需要优化的目标策略采样得出. 使用 off-policy 带来的额外好处:

  • off-policy 不需要一个完整的轨迹并且可以重用过去的 episode
  • 更好的探索: 采样的样本集合来自于与目标策略不同的行为策略(behavior policy).

记已经预先定义的行为策略为$\beta(a|s)$. 目标函数在状态分布上过于 reward 求和:

$$J(\theta)
= \sum_{s \in \mathcal{S}} d^\beta(s) \sum_{a \in \mathcal{A}} Q^\pi(s, a) \pi_\theta(a \vert s)
= \mathbb{E}_{s \sim d^\beta} \big[ \sum_{a \in \mathcal{A}} Q^\pi(s, a) \pi_\theta(a \vert s) \big]$$

其中, $d^{\beta}(s)$是策略$\beta$的平稳分布, 即$d^\beta(s) = \lim_{t \to \infty} P(S_t = s \vert S_0, \beta)$并且$Q^\pi$是关于策略$\pi$的估计.

重新定义策略梯度, 这次训练的状态(observation)采样自分布$a\sim\beta(a|s)$:

$$
\begin{aligned}
\nabla_\theta J(\theta)
&= \nabla_\theta \mathbb{E}_{s \sim d^\beta} \Big[ \sum_{a \in \mathcal{A}} Q^\pi(s, a) \pi_\theta(a \vert s) \Big] & \\
&= \mathbb{E}_{s \sim d^\beta} \Big[ \sum_{a \in \mathcal{A}} \big( Q^\pi(s, a) \nabla_\theta \pi_\theta(a \vert s) + \color{red}{\pi_\theta(a \vert s) \nabla_\theta Q^\pi(s, a)} \big) \Big] & \scriptstyle{\text{; 导数乘法.}}\\
&\stackrel{(i)}{\approx} \mathbb{E}_{s \sim d^\beta} \Big[ \sum_{a \in \mathcal{A}} Q^\pi(s, a) \nabla_\theta \pi_\theta(a \vert s) \Big] & \scriptstyle{\text{; 忽略红色部分: } \color{red}{\pi_\theta(a \vert s) \nabla_\theta Q^\pi(s, a)}}. \\
&= \mathbb{E}_{s \sim d^\beta} \Big[ \sum_{a \in \mathcal{A}} \beta(a \vert s) \frac{\pi_\theta(a \vert s)}{\beta(a \vert s)} Q^\pi(s, a) \frac{\nabla_\theta \pi_\theta(a \vert s)}{\pi_\theta(a \vert s)} \Big] & \\
&= \mathbb{E}_\beta \Big[\frac{\color{blue}{\pi_\theta(a \vert s)}}{\color{blue}{\beta(a \vert s)}} Q^\pi(s, a) \nabla_\theta \ln \pi_\theta(a \vert s) \Big] & \scriptstyle{\text{; 蓝色部分 importance weight(重要采样).}}
\end{aligned}
$$

$\frac{\pi_\theta(a \vert s)}{\beta(a \vert s)}$就是重要性采样的重要性权重. 由于$Q^\pi$是目标策略的函数且是与$\theta$有关的, 所以在求梯度时, 不可忽略; 但是$\nabla_\theta{Q^\pi(s,a)}$实际很难求, 所以忽略它, 仍能够策略的改进, 代价就是最终收敛到局部最小. 证明可以参考Degris, White & Sutton, 2012.

A3C

Asynchronous Advantage Actor-Critic. 具体可参见: (强化学习)- 策略梯度

在论文中以及我们的作业A3C Pong 中使用了 LSTM. 在论文:Deep Recurrent Q-Learning for Partially Observable MDPs提到了在过去的 DQN 中, 选取了四帧作为一个状态, 任何一个需要四帧以上的记忆的游戏出现了部分马尔可夫性(POMDP), 如 Pong 游戏, 只显示了板子(paddle)和球的位置. 而板子的运动方向需要的是球的前进方向而不是当前的状态(也就是球的位置), 这就不满足马尔可夫性中: 未来状态仅取决于当前状态. 相对于 DQN 中使用 CNN 来学习一个图像的信息(或者说四帧图像), 引入 LSTM 能够更好地处理历史信息以得到板子最优的移动的位置.

A2C

未完待续

DDPG

未完待续

MADDPG

未完待续

摘自

TODO

添加评论