GAE——泛化优势估计

GAE——泛化优势估计

GAE主要是讲对优势函数At如何进行估计，网上讲这篇的很少，看着是相当地累了。。

2022/7/9更新：解释更详细了一些。。。文末添加了示例代码。

1 Introduction

省流：如果觉得使用return (一个整episode 的reward) 的计算方差较大，周期太长，想使用估计值函数的形式( $V_\theta(s)$ )来计算优势(advantage)，那可以使用文本提出的GAE算法，使用值函数估计当然会引入偏差，降低方差，但是本文针对此做了一个trade-off，对偏差和方差都容易接受一些(和多步TD类似)

在RL中，最大化policy的reward期望，一个关键问题是动作与最终的奖励往往具有较大的时间延迟，在RL中这个问题被称为“credit assignment problem”，而值函数的提出解决了这个问题，在奖励到来之间，我们可以通过值函数来估计动作的好坏。

使用参数化的随机策略时，可以得到 期望总奖励梯度的无偏估计。但是梯度估计的方差和时间无关。策略梯度的另一类方法是actor-critic，使用value function而不是return，这样引入了偏差，但是也降低了方差。虽然高方差需要使用更多的样本来进行估计，但偏差的危害更大，因为即使样本量很大，偏差也会导致算法无法收敛，或收敛到一个poor solution。

本文提出了policy gradient estimator，在维持一个可以接受的偏差的情况下，大大减小了方差，由参数 $\gamma\in[0,1]$ $\lambda\in[0.1]$ 来表示，称为GAE

本文的贡献主要有：

1.提出了GAE算法，可以有效降低策略梯度的估计方差

2.把GAE用在了TRPO上，得到了不错的效果

3.把算法部署在高维连续控制任务上。

2 Preliminaries

省流：对于策略梯度，我们希望找到策略梯度向着reward增加的更新方向，这个方向就可以由下面5个来决定(有return，后续收到的所有奖励，REINFOCRCE算法提出的减去baseline的算法，Q值，或者优势A)，其实使用这些量进行梯度计算都差不多，重点还是方差问题) 紧接着作者说使用优势A来进行估计是方差最小的，至少来说使用A进行更新，可解释性比较强，因为优势的定义就是Q-V，含义就是当前动作相比平均动作的好坏程度，用这个量来更新再合适不过了，可是这个值只能通过估计来计算，如何估计? 看下文。

对于一个策略来说，策略梯度有很多种表达： $g=E[\sum_{t=0}^\infty \Psi_t\nabla_\theta log~\pi_\theta(a_t|s_t)]$

对于 $\Psi_t$ ，它的表达有很多种形式：

1. $\sum_{t=0}^\infty r_t$ :轨迹的总奖励

2. $\sum_{t=t’}^\infty r_t$ :动作 a_t 奖励 (2是1的改进，因为在t时刻的动作只能影响t时刻之后的收益了)

3. $\sum_{t=t’}^\infty r_t-b(s_t)$ : 在2的基础上减去了一个偏移量，这样可以减小方差，而且经过证明，也不会使原本的计算有偏。

4. $Q^\pi(s_t,a_t)$ ：状态-动作值函数

5. $A^\pi(s_t,a_t)$ : 优势函数表达式是状态动作值函数Q减去状态值函数V $A^\pi(s_t,a_t)=Q^\pi(s_t,a_t)-V^\pi(s_t)$

6. $r_t+V^\pi(s_{t+1})-V^\pi(s_t)$ : TD误差

其中 $V^\pi(s_t):=E_{s_{t+1}:\infty,a_t:\infty}[\sum_{l=0}^\infty r_{t+l}]$ $Q^\pi(s_t,a_t)=E_{s_{t+1}:\infty,a_{t+1}:\infty}[\sum_{l=0}^\infty r_{t+l}]$

$s_{t+1}:_\infty$ 的意思是from t+1 to $\infty$ ，
就是后续的累计回报 $v^\pi(s)=E_\pi[\sum_{l=0}^\infty r_{t+l+1}|S_t=s]$ $Q^\pi(s)=E_\pi[\sum_{l=0}^\infty r_{t+l+1}|S_t=s,A_t=a]$
结果是换个马甲又不认识了，至于为什么上面给的定于中r的下标是而不是，是因为作者在定义的时候，令 $r_t=r(s_t,a_t,s_{t+1})$

使用 $\Psi=优势函数A^\pi(s_t,a_t)$ 可能是方差较小的，但这个值只能使用估计的方法计算，使用优势函数就是增加采取好于平均水平的行动的可能性，就是当前的动作与平均动作相比，使用优势函数大于0的方向去优化策略。

介绍完了优势函数的好处，它的坏处就是不容易计算，所以我们需要对优势函数 $A^\pi$ 进行一个估计。

下面再介绍参数 $\gamma$ ，在MDP中，一般指的是折扣，这里把它当作是无折扣问题中为了减少方差的一个参数(当然,代价就是引入了偏差)

那么为了引入偏差降低方差，那么我们就得知道不引入偏差，具体是啥样子？所以先提出一个概念 $\gamma-just$ ， $\gamma-just$ 指的是一种不引入偏差的，对于优势函数 A_t 进行代替的一个估计

如果我们构造出的优势函数的估计量 $\hat{A_t}$ 是符合 $\gamma-just$ 就需要满足下面的式子：

两边的式子只有关于A的项是不同的，左边带hat是估计量，而右边的A就是真实的优势函数。这个式子的表达的意思就是对整条轨迹而言，不管使用整条轨迹算出来的优势，还是只使用单步计算出来的优势
$\hat{A_t}$ 期望与真实的A是一样的，即是无偏估计。

如果 $\hat{A_t}$ 是 $\gamma-just$ 对于所有t都满足，那：

这是理所当然的，因为原来的式子就是这样定义的 $g=E[\sum_{t=0}^\infty A^\pi(s_t,a_t)\nabla_\theta log~\pi_\theta(a_t|s_t)]$

有了这样的条件，我们就要考虑去构造一个能够满足这样的式子的估计了，为了构造能够满足 $\gamma-just$ 的估计量，一个充分条件就是把 $\hat{A_t}$ 分解成了两个functions，一个是 Q_t ，一个是 b_t , Q_t 可以依赖于任何轨迹，但要给出Q函数的无偏估计，而 b_t 是 a_t 之前采样的状态和动作的任意函数。于是就有了下面的命题。

给出命题1 ：假设 $\hat{A_t}$ 可以被写作 $\hat{A_t}(s_{0:\infty},a_{0:\infty})=Q_t(s_{t:\infty},a_{t:\infty})-b_t(s_{0:t},a_{0:t-1})$ ，那对于所有的 (s_t,a_t) 如果 $E_{s_{t+1}:\infty,a_{t+1}:\infty|s_t,a_t}[Q_t(s_{t:\infty},a_{t:\infty})]=Q^{\pi,\gamma}(s_t,a_t)$

，那 $\hat{A_t}$ 就是满足 $\gamma-just$

换句话说，只要Q是准确的，A就是无偏的。因为减去的那个b实际上不会对偏差造成影响。

证明如下：

其实这里还是很绕的，很难不考虑一个问题，就是作者搞了这么一堆他在干啥？他自己是这么解释的：我们引入 $A^{\pi,\gamma }$ 来替代 $A^{\pi}$ , 我们需要考虑 $g^\gamma$ 的无偏估计，也就是在无折扣问题中策略梯度的有偏估计。
还是很绕，再换句话说！我是一个销售，我想估计一下我每个月平均能卖多少套房子，但是我还没上几天班，估计这个事情需要的数据量还是比较大的，而且我也不知道我用多少个月的数据来估计是准确的，既然如此，我就人为地引入一个参数来控制这个偏差，根据这个参数我来设定问题，这样问题定死了，我只要保证我的结果是相对于这个时间观察较短的问题是无偏的就行。
再再举个例子，假设我上了三个月班，业绩分别是1月 5套，2月 6套， 3月 7套，所以我平均每个月可以卖6套对吧，但是你也知道这个肯定不准确，因为也许现在是销售旺季呢，对于真实地销售数据，这个每个月6套肯定是不准确的，那现在我想引入一个参数，我现在就想知道如果只考虑三个月，那我的问题就从问题A(平均每个月卖多少套房子)转换到了问题B(我最近三个月卖多少套房子)，那平均每个月6套房子这个结果对问题B就是无偏的。
提醒一下，我们这么做的理由，就是为了控制，你到底想接受多大的偏差？根据你接受的偏差大小，我们就可以定制化的设定一个参数，来做一个方差和偏差都可以trade-off，

以下的估计都是符合 $\gamma-just$ 的：

显然前三个没有讨论价值，而最后一个估计形式似乎就是TD，也是Q减去b的形式，因为Q可以写成 $r_t+\gamma V^{\pi,\gamma}(s_{t+1})$

3 优势函数估计

如前所述，构建一个对优势函数的准确估计，就可以进一步估计梯度 $\hat{g}=\frac{1}{N}\sum_{n=1}^{N}\sum_{t=0}^\infty \hat{A^n_t}\nabla_\theta log~\pi_\theta(a_t|s_t)$ n是a batch of episode的数量。

V是近似的值函数，定义 $\delta_t^V=r_t+\gamma (V(s_{t+1})-V(s_t))$ 来估计优势函数 A_t ，如果V是准确的值函数，那这就是 $\gamma-just$ 的估计了，可以得到 A_t 的无偏估计

绕了这么大一圈，不还是TD误差的形式么。

TD误差有 $\lambda$ 步的形式，那这里当然也类似，可以估计k步 $\delta$ 的总和。

偏差一般会随着k增大而减小，因为折扣到最后越来越大，而且 V(s_t) 不会造成偏差。(就跟蒙特卡洛想法一致，前面已经看过了那么多的奖励了，所以看得越多肯定越无偏啊)。k趋近于 $\infty$ 时，就有

Q就是return，Q-V就是A

于是GAE算法的定义就是对k步的估计做了加权，这样就可以把方差和偏差都考虑在内做一个trade-off了。

这里前面有个 $1-\lambda$ 纯粹就是级数求和之后有个分母，直接除掉之后，方便算。

当 $\lambda=0$ 的时候，GAE的形式就是TD误差的形 $\lambda$ 式，有偏差，但方差小。 $\lambda=1$ 的时候，就是蒙特卡洛的形式，无偏差，但是方差大。

所以我们就可以选个合适的 $\lambda$ 值来对偏差和方差做一个trade-off了。进而去估计最终的策略梯度。

总结

结论相对来说还是很简洁的，但是这个中间的一些符号表达真的挺费劲的。。。

怎么实现？

参考openai baseline实现的GAE：

def compute_GAE(self, mb_rewards, mb_values, mb_dones):
    mb_rewards = np.asarray(mb_rewards, dtype=np.float32)
    mb_values = np.asarray(mb_values, dtype=np.float32)
    mb_dones = np.asarray(mb_dones, dtype=np.bool)
    last_values = self.model.value(self.obs, S=self.states, M=self.dones)
    mb_advs = np.zeros_like(mb_rewards)
    lastgaelam = 0
    for t in reversed(range(self.nsteps)):  # 倒序实现，便于进行递归
        if t == self.nsteps - 1:  # 如果是最后一步，要判断当前是否是终止状态，如果是，next_value就是0
            nextnonterminal = 1.0 - self.dones
            nextvalues = last_values
        else:
            nextnonterminal = 1.0 - mb_dones[t + 1]
            nextvalues = mb_values[t + 1]
        delta = mb_rewards[t] + self.gamma * nextvalues * nextnonterminal - mb_values[t]
        mb_advs[t] = lastgaelam = delta + self.gamma * self.lam * nextnonterminal * lastgaelam

当然，这是比较精细的实现了，实际情况下，这么遍历一步一步来算太慢了，一般都是正向来算有限步数的，比如只看前10步的delta,然后做个近似的GAE就可以了。

编辑于 2022-07-09 · 著作权归作者所有

赞同 88