强化学习基础笔记

强化学习定义以下几个变量:

a:操作action,可以是N种操作构成一个有限集合$\{a_1, a_2, …, a_N\}$,每种操作的概率分布是$\pi$;当然如果a是连续操作,那么$\pi$就变成了概率密度分布。

s:状态state,描述了能够用于决策的有关环境的所有信息的表征。

r:回报reward,是当某个状态s下执行了操作a后,对agent的奖励的预期值。

主要优化目标是整个交互过程内的reward收益累积:

$$\mathbb{E}_{p(s_0), \pi(a_0 \mid s_0)}[r(s_1)\mid s_0] + \gamma \mathbb{E}_{p(s_1\mid s_0, a_0), \pi(a_1\mid s_1)}[r(s_2)\mid s_1] + ……$$

每一个step时,收益$r_t$的预期值累加,以$\gamma$的衰弱递减。这里求预期,就涉及到两个不确定分布,首先是状态转移概率$p(s_{t+1} \mid s_t, a_t)$,马尔可夫过程中的状态转移,以及$\pi(a_t\mid s_t)$,策略决策过程本身。要在每个事件“分歧点”对这两个概率分布求预期。

因为“分叉点”的存在,更适合把优化目标写成迭代的形式,这样每个时间点Q的计算,都需要未来各个:

\begin{equation}
Q(s_t, a_t) = \sum\limits_{s_{t+1}} p(s_{t+1}\mid s_t, a_t) r(s_{t+1} \mid s_t, a_t)  + \gamma \sum\limits_{s_{t+1}, a_{t+1}} p(s_{t+1}\mid s_t, a_t) \pi(a_{t+1} \mid s_{t+1}) Q(s_{t+1}, a_{t+1})
\label{eq2}
\end{equation}

Q由两部分组成:

  1. 第一部分是如果当前t时采用策略$a_t$,到下次观测的状态$s_{t+1}$无论是哪个时,即将收获的单步收益的预期,写作$R_s^a$。
  2. 第二部分是当1的预期收益入账之后,对未来尚未发生的一系列事件,在当前策略$\pi(a \mid s)$的影响下,即将累积到的直到游戏结束的所有收益的预期。

agent需要通过$\pi$来选择操作$a(s)$,或是直接调整连续的$a(s)$的值,使得无论任何路径上,只要初始状态和策略固定了,就让累积收益的预期都能最大化。
\begin{equation}
J=\mathbb{E}_{p(s) \sim \tau}[\sum\limits_{t=0}^{\infty} \gamma^{t} \left( \sum\limits_{a \in A} \pi(a \mid s_t) R_s^a \right) \mid s_0, \pi]
\label{eq1}
\end{equation}最大化。

有两种思路来解决这个问题:

  1. 值迭代。平均$P_{s\rightarrow s’}^a$的预期后,$Q(s_t, a_t) \approx r(s_{t+1}) + \mathbb{E}_{\pi(s_{t+1})}[Q(s_{t+1}, a_{t+1})] = r(s_{t+1}) + V(s_{t+1})$。当从真实分布中通过采样来近似出$p(s_{t+1} \mid s_t, a_t)$、$r(s_{t+1})$、$\pi(a \mid s_t)$以及$p(s_0)$时,约等号就变成了等号。所以我们要确保无论任何时候间隔了一步(当然也可以是多步)的Q的差值,符合真实分布中这一(几)步内累积的收益,Q的预测就是准确的。有了准确的Q值预测网络之后,只需要在每一次面临决策时,选取能让Q值收益最大的一个操作,即可得到最优策略。
  2. 策略迭代。直接使用$\frac {\partial J} {\partial \pi} =0$优化策略$\pi$。这时面临的最主要问题是如何获得相对精确的J,这时采样过程非常重要。退一步讲如果没有很好的办法直接获取J,是否存在一些替代方法能够得到等同于优化$\frac {\partial J} {\partial \pi} =0$的效果。

 

值迭代的经典算法DQN,就是用replay buffer以及环境采样trajectory里统计出的$target=\sum\limits_{t=0}^{n} \gamma^t r_t$,与Q值网络$pred = Q(s_0, a_0) – Q(s_n, a_n)$的最小二乘$(pred-target)^2$作为loss来优化Q值网络的评估准确率。

如果从环境采样,那么训练时采样策略一般是epsilon-greedy,其中greedy是在$a^*=argmax_{a} Q_{tgt}(s)$上获得的。

Double DQN与的区别DQN在于$a^*=argmax_{a} Q_{eval}(s)$,之后预估用于最小二乘的目标值$Q(s, a) = r + \gamma Q_{tgt}(s, a^*) $时使用另一个Q网络。$Q_{tgt}$是一个比较落后的版本的$Q_{eval}$。本质上是把actor和critic网络分开,再定时同步。这样做的优点可以避免DQN里过估计(overestimate)的问题。因为$\mathbb{E}[max_a Q] > max_a \mathbb{E}[Q]$是常态,每一步都取max后得到的Q,一般都会大于真实Q。

 

值迭代目的是为了得到优质的评价器criticizer,策略迭代目的是为了更好的actor。两者结合构成了AC框架。 Asynchronous Advantage Actor Critic(A3C)在AC框架的基础上对策略迭代的目标做了些许修改,又对采样部分采用了一些并行策略,于是可以取得更好的效果。

进入A3C具体细节之前,首先讲一下策略梯度方法,策略梯度主要通过策略迭代的方法进行优化。


$\pi=\pi_{\theta}(s)$,假设使用可训练参数$\theta$时策略对其可求导,则根据梯度提升,有$\frac {\partial J} {\partial \theta}=0$

\eqref{eq1}里的$R_s^a$只与环境有关而与$\theta$无关,所以梯度更新时$\nabla_{\theta} J = \mathbb{E}_{p(s) \sim \tau}[\sum\limits_{t=0}^{\infty} \gamma^{t} \left( \sum\limits_{a \in A} \pi(a \mid s_t) \frac{\nabla_{\theta} \pi(a \mid s_t)} { \pi(a \mid s_t)} R_s^a \right) \mid s_0, \pi]$

\begin{equation}
\nabla_{\theta} J = \mathbb{E}_{p(s) \sim \tau, \pi(a) \sim \tau}[ \sum\limits_{t=0}^{\infty} \gamma^{t} \nabla_{\theta}\left(log\pi(a \mid s_t)\right) R_s^a]
\label{eq3}
\end{equation}

where $\tau=(s_0, a_0) \rightarrow (s_1, a_1) \rightarrow ……$

这样的优化梯度需要完整采样出一个足够长的路径$\tau$,每次都从$s_0$按照策略$\pi$开始推演,工程中虽然能够实现,但当环境无法满足on-policy实时推演时,也会使得优化难以进行。

需要转换一下思路:

假设当某步t时观测到$s_t$,过去的所有路径信息已经丢失,可以看作是$i=1, 2…,\infty$条轨迹$\tau_i$分别在不同的演化位置上达成了当前观测到的状态$s\in \tau_i = s_t$。那么可以定义一个静态先验概率$p(s_t)=d(s_t) = \sum\limits_{t^*=0}^{\infty} \gamma^{t^*} P(s_{t^*}=s_t \mid s_{0^*}=\tau_i(0), \pi)$。相当于对无论之前发生了任何事情,算出一个考虑了衰减的用于计算无数个$\tau$之间预期的概率。

$V(s_t) = \mathbb{E}_{\tau} [ \sum\limits_{t^*=t}^{\infty} \gamma^{t^*} \sum\limits_{a \in A} \pi(a \mid s_{t^*})R_s^a]$

之后将t的时间刻度假设看作新起点,例如$t=0$,那么$J =\sum\limits_{s_t \in S} d(s_t) V(s_t)$

于是优化目标将“从$s_0$出发使用$\pi$的无数路径上的收益累积预期(平均$\tau$求预期)”变成了“从$s_0$出发使用$\pi$的,暂时以$s_t$收尾的无论任何长度路径上,所有剩余未累积到的收益预期(使用$d(s_t)$求预期)”。这样一来就不用非要等推演完毕之后再平均求预期,只需要在推演过程中的每一步t不断用网络评估$Q(s_t, a_t)$再结合$\pi(a_t \mid s_t)$算出$V(s_t)$即可。取而代之的难点就变成了如何求$d(s_t)$的问题。

考虑$V(s) = \sum\limits_{a \in A} \pi(a \mid s) Q(s, a)$

定义单步转移概率$ p(s_{t+1}\mid s_t, a_t) = P_{s\rightarrow s’}^a$,对上式求$\nabla_{\theta}$,则有

$$ = \sum\limits_a \left[ Q(s, a) \frac {\partial \pi(a \mid s) } {\partial \theta} + \pi(a\mid s)  \frac {\partial } {\partial \theta} \left[ R_s^a + \gamma \sum\limits_{s’} \sum\limits_{a’} P_{s\rightarrow s’}^a \pi(a’ \mid s’) Q(s’, a’) \right] \right]$$

对$R_s^a$求导得到0,因为critic函数不会改变预先定义好的reward规则。

可以看到递归出现,那么如果多展开几次,每次都会带出一个$\gamma$还有$P_{s\rightarrow s’}^a$,所以这两项会累乘起来。

注意到$P_{s\rightarrow s’}^a= Pr(s\rightarrow s’ \mid a)$,利用$ Pr(s\rightarrow s’) = \sum\limits_{a} Pr(s\rightarrow s’ \mid a) \pi(a \mid s)$。可得trajectory上对action空间取预期后的$Pr(s\rightarrow s’)$

所以要让$s \rightarrow s’ \rightarrow s” \rightarrow… \rightarrow x$被连续采出来,就要让右边改成:

$$\sum\limits_a Q(s, a) \frac {\partial \pi(a \mid s) } {\partial \theta} + \sum\limits_a \gamma Pr(s\rightarrow s’ \mid a) \pi(a \mid s)  \frac {\partial } {\partial \theta} \left[  \sum\limits_{s’} \sum\limits_{a’} \pi(a’ \mid s’) Q(s’, a’) \right]$$

$$=\sum\limits_a Q(s, a) \frac {\partial \pi(a \mid s) } {\partial \theta} + \gamma Pr(s\rightarrow s’) \frac {\partial } {\partial \theta} \left[  \sum\limits_{s’} \sum\limits_{a’} \pi(a’ \mid s’) Q(s’, a’) \right]$$

现在转换一下思路,不考虑初始$s$的值是什么,只要在对应第k步的$s_t = x \mid t=k$的state是$x$即可,那么展开后的式子变成了:

$$\frac {\partial V(s)} {\partial \theta} = \sum\limits_x \sum\limits_{k=0}^{\infty} \gamma^k Pr(s \rightarrow x, k \mid \pi) \sum\limits_a Q(x, a) \frac {\partial \pi(a \mid x)}{\partial \theta}$$

其中$Pr(s \rightarrow x, k)$是经历了k轮之后从初始s演变成最终x状态的概率。

把初始状态重写为$s_0$,最终状态重写为$s$,则

$$\frac {\partial V(s_0)} {\partial \theta} = \sum\limits_s \sum\limits_{k=0}^{\infty} \gamma^k Pr(s_0 \rightarrow s, k) \sum\limits_a Q(s, a) \frac {\partial \pi(a \mid s)}{\partial \theta}$$

注意到$\sum\limits_{k=0}^{\infty} \gamma^k Pr(s_0 \rightarrow s, k)$等于$d(s)$,即所有可能的长度的演化路线根据衰减系数$\gamma$后得到的状态为s的概率,所以$\nabla_{\theta} V(s_0) = \sum\limits_{s} d(s) \sum\limits_{a} Q(s, a) \nabla_{\theta} \pi(a \mid s)$。

由于稳态分布$d(s)$不方便求,一般使用MC采样来近似,于是需要在不同的t时刻进行采样。不同t时刻之间的采样又不可避免地进行a的采样,于是$\mathbb{E}_{\tau} = \mathbb{E}_{p(s, a, k) \sim \tau}=\sum\limits_{s, a, k} p(s, a, k)=\sum\limits_{s, a, k} P(s_0 \rightarrow s, k)\pi(a\mid s)$。

$\nabla_{\theta} J = \sum\limits_{s, k}\sum\limits_a P(s_0 \rightarrow s, k) \pi(a \mid s) Q(s, a) \frac {\nabla_{\theta} \pi(a \mid s)} {\pi(a \mid s)} $

$=\mathbb{E}_{p(s, a, k) \sim \tau}[ Q(s, a) \nabla_{\theta}\left(log\pi(a \mid s)\right)]$

这样我们就不需要完整采样整个路径之后按照\eqref{eq3}累加每一步的$R_s^a$,只需要在任意路径的任意一截采出$p(s, a, k)$以及对应的$Q(s, a)$和$\nabla_{\theta}\left(log\pi(a \mid s)\right)$就可以了。

注意到每一步$a_t$之间存在非连续的采样操作,所以例如seq2seq的解码过程里对target loss求导这一类对于非连续不可导的反向传播,也是可以使用策略梯度来更新解码器参数的。


A3C:


Proximal Policy Optimization(PPO):

更新actor时,策略梯度的方向$g = \mathbb{E}_{p(s, a, k) \sim \tau}[ Q(s, a) \nabla_{\theta}\left(log\pi(a \mid s)\right)]$

在沿$\tau$采样action时,一般常见的方式是$a \sim \pi_{\theta}$,这是on-policy的训练方法。如果改变当前的策略,例如加上一些随机性(像epsilon greedy那样),那么就可以变成off-policy的方式了。为了保证模型策略的稳定性,我们的off-policy策略可以使用比较旧版本的$\pi$,写作$\pi_{\theta \text{old}}$。

但是采样策略变了,虽然不影响值迭代,却影响policy gradient,要如何保证梯度方向不变呢?这里就需要使用importance sampling的方法了。

对一个连续函数$f(x)$求预期,可以写作

$$\mathbb{E}_{x \sim p(x)}[f(x)]=\int\limits f(x) p(x) dx = \int\limits f(x) \frac{p(x)} {q(x)} q(x) dx = \mathbb{E}_{x \sim q(x)}[f(x) \frac{p(x)} {q(x)}]$$

其中$\frac{p(x)} {q(x)}$是importance weight,负责在计算预期的采样分布从$p$变成$q$时,把$f$预期还原成原本的值的一个修正。

所以要让gradient即使采样策略变了的情况下,方向(预期值)不变,就要加上importance weight:

$$g = \mathbb{E}_{p(s, a, k) \sim \tau(\theta \text{old})}[ Q(s, a) \frac {\pi_{\theta}(a \mid s)} { \pi_{\theta \text{old}}(a \mid s)} \nabla_{\theta}\left(log\pi_{\theta \text{old}}(a \mid s)\right)]$$

如果使用优势函数$A$代替$Q$,则使用到的$V(s)=\sum\limits_{a} \pi_{\theta \text{old}}(a \mid s) Q(s, a)$也应该基于旧分布。

TRPO对$D_{KL}(\pi_{\theta} || \pi_{\theta \text{old}})$做了硬约束,要搜索出合适的Lagrange multiplier, 不方便求解。所以PPO改成了惩罚项软约束。此外软约束下的优化替代函数$L_{\pi_{old}}(\pi)=\mathbb{E}_{\tau_{old}} \left[ \frac{\pi(a \mid s, \theta)} {\pi(a \mid s, \theta_{old})} A^{GAE}(s, a)  – \lambda D_{KL}(\pi || \pi_{old}) \right]$ 也是直接用adam求导,而非套用Policy Gradient公式的。在升级版本PPO2论文里,在计算importance weight (理论值从$0$到$\infty$)时引入了clip函数,当$A>0$时限制它的上限,当$A<0$时限制它的下限。这样优势函数$A$不会被importance weight修改得即使在新旧策略差异较大(importance weight超出某个门槛。毕竟软KL约束无法杜绝这种情况)时,对于更新方向的影响也特别大。KL距离的约束被clip操作取代,而clip阈值的大小控制了“约束后的新策略”位于“旧策略”与“无约束新策略”之间的某个中间位置是更接近于哪一方。

注意优势函数$A$实际上拥有下标$A_t$,下标t用于求trajectory[0, T]上的时间平均预期用。

$A_t=A(s_t, a_t)=\delta_t + \gamma \delta_{t+1} + \gamma^2\delta_{t+2}+…+\gamma^{T-t+1}\delta_{T-1}$

where $\delta_t = r_t + \gamma V(s_{t+1}) – V(s_t)$

使用GAE的逻辑是这样的:

一个准确评估的$V(s_t)$,在actor达成最优策略时,$\delta_t=0$。而在那之前,单步优势就是$\delta_t = r_t \mid _{a_t} + \gamma V(s_{t+1}) – V(s_t)$

我们希望以任意t作为起点时,对于后续累加的优势$\hat{A}(t) = \sum\limits_{l=0}^{\infty} \delta_{t+l}$ 最大化。但与累加reward时需要$\gamma$来调节衰减一样,累加$\delta$时也添加了一个衰减$\gamma\lambda$,其中$\lambda$的作用就是对$\gamma$做出改变从而获得一个不一样的衰减。

最终得到 $\hat{A}^{GAE}(t)= \sum\limits_{l=0}^{\infty} (\gamma\lambda)^{l} \delta_{t+l}$

当$\lambda=1$时,GAE变成远距离TD,这时reward累加得到的$V_{start}$很准确,但评估$V_{end}$时输入$s$已经经过太多轮不确定的状态转移,导致$V_{end}$的variance很大。而当$\lambda=0$时,GAE变成1步TD,1步采样得到的reward大概率是偏离预期值$\mathbb{E}_{\pi}[r \mid s]$的,所以必然导致V的学习目标带有bias,而状态转移相对确定一些,所以variance会小一些。$\lambda$于是起到了n步TD中调节bias与variance平衡的作用。

发表评论

邮箱地址不会被公开。 必填项已用*标注