强化学习笔记(七)- 资格迹

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言,谢谢

引言

  资格迹(Eligibility Trace)是强化学习中一种非常基础的机制,它可以使时序差分学习更加高效,能在回合更新(MC 方法)和单步时序差分更新(TD(0))间进行折中。

  我们该如何理解资格迹呢,通常有两种理解的思路,前向视角和后向视角:

  • 前向视角(forward view),资格迹是一种理论思想,也叫理论视角,即由当前状态向还未访问的状态观察。这种思想作用于基本 TD(0) 算法上,把它改造成一类新的,更强大的 TD 算法。这一类新的TD算法介于 MC 和 TD(0) 之间,但是效果比这两者都要好,因此可以把资格迹看成 TD(0) 和 MC 的折中。
  • 后向视角(backward view),资格迹是轨迹中每个状态的附加属性,也叫机理视角,即由当前状态向已经访问过的状态观察。每个状态的资格迹决定了该状态与当前正在访问的状态的价值更新值之间的关联程度,或者说影响程度。

  前向视角,告诉我们资格迹在理论层面是如何工作的。后向视角,则告诉我们资格迹在工程层面是如何实现的。

\(\lambda\)-return

  \(n\)-steps return:

\[ G_{t: t+n} = R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{n-1} R_{t+n}+\gamma^{n} \hat{v}\left(S_{t+n}, \mathbf{w}_{t+n-1}\right), \quad 0 \leq t \leq T-n \]

  对多个 \(n\)-steps return 作加权平均,只需权重和为 1,例如下面的 backup 图所示的 \(\frac{1}{2} G_{t: t+2}+\frac{1}{2} G_{t: t+4}\),这种更新方式称为 compound update:

  我们接下来要说的 TD(\(\lambda\)) 也属于这种 averaging n-step update,它包括了所有的 \(n\)-steps updates,\(\lambda\)-return 的定义如下:

\[ G_{t}^{\lambda} =(1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_{t: t+n} \]

  我们可以看出它的权重系数为 \(\lambda^{n-1}\),它的 backup 图:

  如图中所写一样,当 \(\lambda=1\) 时就是 MC,当 \(\lambda=0\) 时就是 1-step TD。权重的递减如下图所示:

  因为要满足权重和为 1,所以上式又可以写为:

\[ G_{t}^{\lambda}=(1-\lambda) \sum_{n=1}^{T-t-1} \lambda^{n-1} G_{t: t+n}+\lambda^{T-t-1} G_{t} \]

  将 \(G_{t}^{\lambda}\) 作为回报更新,这个算法也叫做为 offline \(\lambda\)-return algorithm,可以采用半梯度更新:

\[ \mathbf{w}_{t+1} = \mathbf{w}_{t}+\alpha\left[G_{t}^{\lambda}-\hat{v}\left(S_{t}, \mathbf{w}_{t}\right)\right] \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right), \quad t=0, \ldots, T-1 \]

  这个算法也是一个前向视角的算法,它在每个状态都需要一些未来状态的信息,示意图如下:

TD(\(\lambda\))

  相比于 offline \(\lambda\)-return,TD(\(\lambda\)) 单步更新权重向量,无需等待 episode 结束,并且计算在时间上均匀分布,不仅可用于 episode 问题,还适用于连续问题。
  我们记资格迹 \(\mathbf{z}_{t} \in \mathbb{R}^{d}\)

\[ \begin{aligned} &\mathbf{z}_{-1} = \mathbf{0}\\ &\mathbf{z}_{t} = \gamma \lambda \mathbf{z}_{t-1}+\nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right), \quad 0 \leq t \leq T \end{aligned} \]

  通过它的定义式,我们可以发现其与权重 \(\mathbf{w}_{t}\) 维度相同,\(\mathbf{w}_{t}\) 有长期的记忆性,其存在时间与系统等长,而资格迹则体现了短期记忆,存在于回合内的一个子片段中。
  资格迹试图找到那些对最近状态价值有贡献的权重分量,这个最近体现在系数 \(\gamma \lambda\) 上。
  one-step TD error:

\[ \delta_{t} = R_{t+1}+\gamma \hat{v}\left(S_{t+1}, \mathbf{w}_{t}\right)-\hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \]

  TD(\(\lambda\)) 更新式:

\[ \begin{aligned} \mathbf{w}_{t+1} &= \mathbf{w}_{t}+\alpha \delta_{t} \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \\ &= \mathbf{w}_{t}+\alpha \delta_{t}\left[\nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right)+\gamma \lambda \mathbf{z}_{t-1}\right] (给梯度增加一些信息)\\ &= \mathbf{w}_{t}+\alpha \delta_{t} \mathbf{z}_{t} \end{aligned} \]

  伪代码如下:

  TD(\(\lambda\)) 是后向视角的算法,每个时刻得到新的 TD error 后,又依据它对之前状态的资格迹作一些调整,示意图如下所示:

  使用了资格迹后仍能统一地表示各种算法。当 \(\lambda=0\) 时,恰好就是价值函数的梯度,此时正好对应 one-step TD。当 \(\lambda=1\) 时,可以看出每一个状态都刚好衰减 \(\gamma\) 倍,跑完这个回合 ,恰好就是 MC。

n-step Truncated \(\lambda\)-return Methods

  offline \(\lambda\)-return 是很难使用的,因为它需要等到一个回合结束才能计算,对于连续性任务来说更不可用,因为这个 \(n\) 可以无限大,所以我们需要做一些截断,用估计值代替抛弃掉的较远的 rewards,定义 Truncated \(lambda\)-return:

\[ G_{t: h}^{\lambda} =(1-\lambda) \sum_{n=1}^{h-t-1} \lambda^{n-1} G_{t: t+n}+\lambda^{h-t-1} G_{t: h}, \quad 0 \leq t<h \leq T \]

  该算法也称为 Truncated TD(\(\lambda\)) ,或 TTD(\(\lambda\)) ,backup 图如下:

  更新式如下:

\[ \mathbf{w}_{t+n} = \mathbf{w}_{t+n-1}+\alpha\left[G_{t: t+n}^{\lambda}-\hat{v}\left(S_{t}, \mathbf{w}_{t+n-1}\right)\right] \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t+n-1}\right), \quad 0 \leq t<T \\ G_{t: t+k}^{\lambda}=\hat{v}\left(S_{t}, \mathbf{w}_{t-1}\right)+\sum_{i=t}^{t+k-1}(\gamma \lambda)^{i-t} \delta_{i} \\ \delta_{t}^{\prime} = R_{t+1}+\gamma \hat{v}\left(S_{t+1}, \mathbf{w}_{t}\right)-\hat{v}\left(S_{t}, \mathbf{w}_{t-1}\right) \]

Redoing Updates: The Online \(\lambda\) -return Algorithm

  对 TTD(\(\lambda\)) 来说,\(n\) 越大越接近 offline \(\lambda\)-return,\(n\) 越小更新速度越快,我们可以达到一个平衡,每次获得更新数据后,重新从头开始执行所有更新:

\[ \begin{aligned} h=1: & \mathbf{w}_{1}^{1} = \mathbf{w}_{0}^{1}+\alpha\left[G_{0: 1}^{\lambda}-\hat{v}\left(S_{0}, \mathbf{w}_{0}^{1}\right)\right] \nabla \hat{v}\left(S_{0}, \mathbf{w}_{0}^{1}\right) \\ h=2: & \mathbf{w}_{1}^{2} = \mathbf{w}_{0}^{2}+\alpha\left[G_{0: 2}^{\lambda}-\hat{v}\left(S_{0}, \mathbf{w}_{0}^{2}\right)\right] \nabla \hat{v}\left(S_{0}, \mathbf{w}_{0}^{2}\right) \\ & \mathbf{w}_{2}^{2} = \mathbf{w}_{1}^{2}+\alpha\left[G_{1: 2}^{\lambda}-\hat{v}\left(S_{1}, \mathbf{w}_{1}^{2}\right)\right] \nabla \hat{v}\left(S_{1}, \mathbf{w}_{1}^{2}\right) \\ h=3: & \mathbf{w}_{1}^{3} = \mathbf{w}_{0}^{3}+\alpha\left[G_{0: 3}^{\lambda}-\hat{v}\left(S_{0}, \mathbf{w}_{0}^{3}\right)\right] \nabla \hat{v}\left(S_{0}, \mathbf{w}_{1}^{3}\right) \\ &\mathbf{w}_{2}^{3} = \mathbf{w}_{1}^{3}+\alpha\left[G_{1: 3}^{\lambda}-\hat{v}\left(S_{1}, \mathbf{w}_{1}^{3}\right)\right] \nabla \hat{v}\left(S_{1}, \mathbf{w}_{1}^{3}\right) \\ & \mathbf{w}_{3}^{3} = \mathbf{w}_{2}^{3}+\alpha\left[G_{2: 3}^{\lambda}-\hat{v}\left(S_{2}, \mathbf{w}_{2}^{3}\right)\right] \nabla \hat{v}\left(S_{2}, \mathbf{w}_{2}^{3}\right) \end{aligned} \]

  每个 \(\mathbf{w}_{0}^{h}\) 都继承自上一个回合,所有的 \(\mathbf{w}_{0}^{h}\) 都为同一值,\(\mathbf{w}_{t}^{h}\) 则为每一步的更新结果。更一般的表示为:

\[ \mathbf{w}_{t+1}^{h} = \mathbf{w}_{t}^{h}+\alpha\left[G_{t: h}^{\lambda}-\hat{v}\left(S_{t}, \mathbf{w}_{t}^{h}\right)\right] \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}^{h}\right), \quad 0 \leq t<h \leq T^{=} \]

  这就是 online \(\lambda\)-return algorithm,是完全在线算法,每个时间点 \(t\) 均使用已有数据产生一个新权重向量 \(\mathbf{w}_{t}\)。他在每个时间点 \(h\) 都能充分利用上一个 \(h\) 时间之前的所有信息,可以看出现在这种算法对数据的利用率更高,更新效果更好,但是它每次均需从头计算,复杂度高。

True Online TD(\(\lambda\))

  为了解决 online \(\lambda\)-return 计算复杂度太高,我们可以利用资格迹将算法变换为后向视角的算法,这就是True Online TD(\(\lambda\))。online \(\lambda\) -return 方法产生的权重序列如下:

\[ \begin{aligned} &\mathbf{w}_{0}^{0}\\ &\begin{array}{lll} {\mathbf{w}_{0}^{1}} & {\mathbf{w}_{1}^{1}} \\ {\mathbf{w}_{0}^{2}} & {\mathbf{w}_{1}^{2}} & {\mathbf{w}_{2}^{2}} \\ {\mathbf{w}_{0}^{3}} & {\mathbf{w}_{1}^{3}} & {\mathbf{w}_{2}^{3}} & {\mathbf{w}_{3}^{3}} \end{array}\\ &\begin{array}{lllll} {\vdots} & {\vdots} & {\vdots} & {\vdots} & {\ddots} \\ {\mathbf{w}_{0}^{T}} & {\mathbf{w}_{1}^{T}} & {\mathbf{w}_{2}^{T}} & {\mathbf{w}_{3}^{T}} & {\cdots} & {\mathbf{w}_{T}^{T}} \end{array} \end{aligned} \]

  其实我们需要的只是每行最后一个权重 \(\mathbf{w}_{t}^{t}\) ,得到 \(\mathbf{w}_{t}=\mathbf{w}_{t}^{t}\)。对于线性情况,True online TD(\(\lambda\)) 定义如下:

\[ \mathbf{w}_{t+1} = \mathbf{w}_{t}+\alpha \delta_{t} \mathbf{z}_{t}+\alpha\left(\mathbf{w}_{t}^{\top} \mathbf{x}_{t}-\mathbf{w}_{t-1}^{\top} \mathbf{x}_{t}\right)\left(\mathbf{z}_{t}-\mathbf{x}_{t}\right) \\ \mathbf{z}_{t} = \gamma \lambda \mathbf{z}_{t-1}+\left(1-\alpha \gamma \lambda \mathbf{z}_{t-1}^{\top} \mathbf{x}_{t}\right) \mathbf{x}_{t} \]

  True online TD(\(\lambda\)) 可以产生和 online \(\lambda\)-return 算法一样的结果,空间要求和 TD(\(\lambda\)) 相同,计算量稍微增加了50%,但仍为\(O(d)\)复杂度。伪代码如下:

 True online TD(\(\lambda\)) 使用的资格迹称为 Dutch Trace,之前的 TD(\(\lambda\)) 中则称为 Accumulating Trace。还有一种叫 Replacing Trace,定义如下:

\[ z_{i, t} =\left\{\begin{array}{ll} {1} & {\text { if } x_{i, t}=1} \\ {\gamma \lambda z_{i, t-1}} & {\text { otherwise }} \end{array}\right. \]

  它仅针对表格形式或二进制特征向量,例如由图块编码产生的特征向量定义。

Dutch Traces in Monte Carlo Learning

  资格迹其实于 TD 在本质上并无联系,资格迹其实是来自 MC。线性情况下,梯度 MC 法的更新式如下:

\[ \mathbf{w}_{t+1} = \mathbf{w}_{t}+\alpha\left[G-\mathbf{w}_{t}^{\top} \mathbf{x}_{t}\right] \mathbf{x}_{t}, \quad 0 \leq t<T \]

  为了简化,这里的 \(G\) 只是回合结束后得到的单个奖励,所以没有下标,并且没有做 \(\gamma\) 折扣。我们考虑这样一个优化,在回合里的每一步都进行一些计算,但仍只在回合结束后才进行更新,所以复杂度仍为 \(O(d)\) 。算法如下,其中引入 \(\mathbf{F}_{t} = \mathbf{I}-\alpha \mathbf{x}_{t} \mathbf{x}_{t}^{\top}\) 为遗忘矩阵(衰退矩阵):

\[ \begin{aligned} \mathbf{w}_{T} &=\mathbf{w}_{T-1}+\alpha\left(G-\mathbf{w}_{T-1}^{\top} \mathbf{x}_{T-1}\right) \mathbf{x}_{T-1} \\ &=\mathbf{w}_{T-1}+\alpha \mathbf{x}_{T-1}\left(-\mathbf{x}_{T-1}^{\top} \mathbf{w}_{T-1}\right)+\alpha G \mathbf{x}_{T-1} \\ &=\left(\mathbf{I}-\alpha \mathbf{x}_{T-1} \mathbf{x}_{T-1}^{\top}\right) \mathbf{w}_{T-1}+\alpha G \mathbf{x}_{T-1} \\ &=\mathbf{F}_{T-1} \mathbf{w}_{T-1}+\alpha G \mathbf{x}_{T-1} \\ &=\mathbf{F}_{T-1}\left(\mathbf{F}_{T-2} \mathbf{w}_{T-2}+\alpha G \mathbf{x}_{T-2}\right)+\alpha G \mathbf{x}_{T-1}\\ &=\mathbf{F}_{T-1} \mathbf{F}_{T-2} \mathbf{w}_{T-2}+\alpha G\left(\mathbf{F}_{T-1} \mathbf{x}_{T-2}+\mathbf{x}_{T-1}\right)\\ &=\mathbf{F}_{T-1} \mathbf{F}_{T-2}\left(\mathbf{F}_{T-3} \mathbf{w}_{T-3}+\alpha G \mathbf{x}_{T-3}\right)+\alpha G\left(\mathbf{F}_{T-1} \mathbf{x}_{T-2}+\mathbf{x}_{T-1}\right)\\ &=\mathbf{F}_{T-1} \mathbf{F}_{T-2} \mathbf{F}_{T-3} \mathbf{w}_{T-3}+\alpha G\left(\mathbf{F}_{T-1} \mathbf{F}_{T-2} \mathbf{x}_{T-3}+\mathbf{F}_{T-1} \mathbf{x}_{T-2}+\mathbf{x}_{T-1}\right)\\ &=\underbrace{\mathbf{F}_{T-1} \mathbf{F}_{T-2} \cdots \mathbf{F}_{0} \mathbf{w}_{0}}_{\mathbf{a}_{T-1}}+\alpha G \sum_{k=0}^{T-1} \mathbf{F}_{T-1} \mathbf{F}_{T-2} \cdots \mathbf{F}_{k+1} \mathbf{x}_{k}\\ &=\mathbf{a}_{T-1}+\alpha G \mathbf{z}_{T-1} \end{aligned} \]

  其中 \(\mathbf{a}_{T-1}\)\(\mathbf{z}_{T-1}\) 是 T-1 时刻的两个辅助记忆向量,即使不知道 \(G\) ,也能在每步先做一些这样的计算,用以存储一些信息。其实 \(\mathbf{z}_{t}\) 是一个 dutch-style eligibility trace,初始值为 \(\mathbf{z}_{0}=\mathbf{x}_{0}\),更新式为:

\[ \begin{aligned} \mathbf{z}_{t} & = \sum_{k=0}^{t} \mathbf{F}_{t} \mathbf{F}_{t-1} \cdots \mathbf{F}_{k+1} \mathbf{x}_{k}, \quad 1 \leq t<T \\ &=\sum_{k=0}^{t-1} \mathbf{F}_{t} \mathbf{F}_{t-1} \cdots \mathbf{F}_{k+1} \mathbf{x}_{k}+\mathbf{x}_{t} \\ &=\mathbf{F}_{t} \mathbf{F}_{t-1} \cdots \mathbf{F}_{k+1} \mathbf{x}_{k}+\mathbf{x}_{t} \\ &=\mathbf{F}_{t} \sum_{k=0}^{t-1} \mathbf{F}_{t-1} \mathbf{F}_{t-2} \cdots \mathbf{F}_{k+1} \mathbf{x}_{k}+\mathbf{x}_{t} \\ &=\left(\mathbf{I}-\alpha \mathbf{x}_{t-1} \mathbf{F}_{t-1}+\mathbf{x}_{t}\right.\\ &=\mathbf{z}_{t-1}-\alpha\left(\mathbf{z}_{t-1}^{\top} \mathbf{x}_{t}\right) \mathbf{x}_{t}+\mathbf{x}_{t} \\ &=\mathbf{z}_{t-1}+\left(1-\alpha \mathbf{z}_{t-1}^{\top} \mathbf{x}_{t}\right) \mathbf{x}_{t} \\ &=\mathbf{z}_{t-1}+\left(1-\alpha \mathbf{z}_{t-1}^{\top} \mathbf{x}_{t}\right) \mathbf{x}_{t} \end{aligned} \]

  辅助向量 \(\mathbf{a}_{t}\) 初始值为 \(\mathbf{a}_{0}=\mathbf{w}_{0}\) ,更新式为:

\[ \mathbf{a}_{t} = \mathbf{F}_{t} \mathbf{F}_{t-1} \cdots \mathbf{F}_{0} \mathbf{w}_{0}=\mathbf{F}_{t} \mathbf{a}_{t-1}=\mathbf{a}_{t-1}-\alpha \mathbf{x}_{t} \mathbf{x}_{t}^{\top} \mathbf{a}_{t-1}, \quad 1 \leq t<T_{-} \]

  在 t < T 时,每步更新辅助向量 \(\mathbf{a}_{t}\)\(\mathbf{z}_{t}\) ,当 T 时刻获得 \(G\) 后再最终计算出 \(\mathbf{w}_{t}\) 。得到的结果和 MC 相同,但计算更简单。因此资格迹并不局限于 TD 方法,只要想做长期预测,都可以采用资格迹。

SARSA(\(\lambda\))

  将资格迹从状态价值拓展到动作价值,只需把状态价值函数的估计替换成动作价值函数的估计,n-step return:

\[ G_{t: t+n} = R_{t+1}+\cdots+\gamma^{n-1} R_{t+n}+\gamma^{n} \hat{q}\left(S_{t+n}, A_{t+n}, \mathbf{w}_{t+n-1}\right), \quad t+n<T \]

  \(t + n \gt T\)\(G_{t: t+n} = G_t\),结合 n-step return,构造动作价值形式的 Truncated \(\lambda\)-return \(G_{\lambda}^t\),进而得到动作价值形式的 offline \(\lambda\)-return 算法:

\[ \mathbf{w}_{t+1} = \mathbf{w}_{t}+\alpha\left[G_{t}^{\lambda}-\hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right)\right] \nabla \hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right), \quad t=0, \ldots, T-1 \]

  backup 图如下:

  SARSA(\(\lambda\)) 的更新式也与 TD(\(\lambda\)) 的类似:

\[ \begin{aligned} &\mathbf{w}_{t+1} = \mathbf{w}_{t}+\alpha \delta_{t} \mathbf{z}_{t}\\ &\begin{array}{l} {\delta_{t} = R_{t+1}+\gamma \hat{q}\left(S_{t+1}, A_{t+1}, \mathbf{w}_{t}\right)-\hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right)} \\ {\mathbf{z}_{-1} = \mathbf{0}} \end{array}\\ &\mathbf{z}_{t} = \gamma \lambda \mathbf{z}_{t-1}+\nabla \hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right) \end{aligned} \]

  伪代码如下:

  上面是 offline 版本的,我们再看看 True Online SARSA(\(\lambda\)):

Variable \(\lambda\) and \(\gamma\)

  为了更泛化地表示每一步中自益(bootstrapping)和折扣(discounting)的程度,需要更通用的 \(\lambda\)\(\gamma\)。定义函数 \(\lambda: \mathcal{S} \times \mathcal{A} \rightarrow[0,1]\),有 \(\lambda_t=\lambda(S_t,A_t)\)。定义函数 \(\gamma: \mathcal{S} \rightarrow[0,1]\),有 \(\gamma_t = \gamma(S_t)\)
  我们先谈谈对折扣的泛化,函数 \(\gamma\) 称为 termination function,重新定义 return :

\[ \begin{aligned} G_{t} & = R_{t+1}+\gamma_{t+1} G_{t+1} \\ &=R_{t+1}+\gamma_{t+1} R_{t+2}+\gamma_{t+1} \gamma_{t+2} R_{t+3}+\gamma_{t+1} \gamma_{t+2} \gamma_{t+3} R_{t+4}+\cdots \\ &=\sum_{k=t}^{\infty}\left(\prod_{i=t+1}^{k} \gamma_{i}\right) R_{k+1} \end{aligned} \]

  为保证结果有限,需要 \(\Pi_{k=t}^{\infty} \gamma_t = 0\)。这种形式的好处是,基于回合任务无需再指定开始状态和结束状态,只需使 \(\gamma(s)=0\) 即可,因此便能统一回合和折扣。
  下面介绍对自益的泛化。若对状态价值做自益,则泛化参数记为 \(\lambda_s\) ,同理 \(\lambda_a\) 为对动作价值做自益,\(\lambda\) 控制了自益的程度,当为 1 时完全不做自益,当为 0 时则完全是在做自益,于是可以得到新的递归形式的基于状态价值的 \(\lambda\)-return :

\[ G_{t}^{\lambda s} = R_{t+1}+\gamma_{t+1}\left(\left(1-\lambda_{t+1}\right) \hat{v}\left(S_{t+1}, \mathbf{w}_{t}\right)+\lambda_{t+1} G_{t+1}^{\lambda s}\right) \]

  基于动作价值的 \(\lambda\)-return 也类似: \[ G_{t}^{\lambda a} = R_{t+1}+\gamma_{t+1}\left(\left(1-\lambda_{t+1}\right) \hat{q}\left(S_{t+1}, A_{t+1}, \mathbf{w}_{t}\right)+\lambda_{t+1} G_{t+1}^{\lambda a}\right) \]

  还有 Expected SARSA 形式:

\[ G_{t}^{\lambda a} = R_{t+1}+\gamma_{t+1}\left(\left(1-\lambda_{t+1}\right) \bar{V}_{t}\left(S_{t+1}\right)+\lambda_{t+1} G_{t+1}^{\lambda a}\right) \\ \bar{V}_{t}(s) = \sum_{a} \pi(a | s) \hat{q}\left(s, a, \mathbf{w}_{t}\right) \]

Off-policy Traces with Control Variates

  将重要性采样整合进算法得到异策算法。采用 per-decision 方法,基于状态的 \(\lambda\)-return :

\[ G_{t}^{\lambda s} = \rho_{t}\left(R_{t+1}+\gamma_{t+1}\left(\left(1-\lambda_{t+1}\right) \hat{v}\left(S_{t+1}, \mathbf{w}_{t}\right)+\lambda_{t+1} G_{t+1}^{\lambda s}\right)\right)+\left(1-\rho_{t}\right) \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \\ \rho_{t}=\frac{\pi\left(A_{t} | S_{t}\right)}{b\left(A_{t} | S_{t}\right)} \]

  利用 TD error 逼近得到 Truncated \(G_{t}^{\lambda s}\)

\[ \begin{aligned} &\delta_{t}^{s} = R_{t+1}+\gamma_{t+1} \hat{v}\left(S_{t+1}, \mathbf{w}_{t}\right)-\hat{v}\left(S_{t}, \mathbf{w}_{t}\right)\\ &G_{t}^{\lambda s} \approx \hat{v}\left(S_{t}, \mathbf{w}_{t}\right)+\rho_{t} \sum_{k=t}^{\infty} \delta_{k}^{s} \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \rho_{i} \end{aligned} \]

  这样就很容易进行基于前向视角的更新:

\[ \begin{aligned} \mathbf{w}_{t+1} &=\mathbf{w}_{t}+\alpha\left(G_{t}^{\lambda s}-\hat{v}\left(S_{t}, \mathbf{w}_{t}\right)\right) \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \\ & \approx \mathbf{w}_{t}+\alpha \rho_{t}\left(\sum_{k=t}^{\infty} \delta_{k}^{s} \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \rho_{i}\right) \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \end{aligned} \]

  我们来探究一下前向视角和后向视角的近似关系。对整个前向视角的过程进行求和,得到:

\[ \begin{aligned} &\begin{aligned} \sum_{t=1}^{\infty}\left(\mathbf{w}_{t+1}-\mathbf{w}_{t}\right) & \approx \sum_{t=1}^{\infty} \sum_{k=t}^{\infty} \alpha \rho_{t} \delta_{k}^{s} \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \rho_{i} \\ &=\sum_{k=1}^{\infty} \sum_{t=1}^{k} \alpha \rho_{t} \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \delta_{k}^{s} \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \rho_{i} \end{aligned}\\ &\text { (using the summation rule: }\left.\sum_{t=x}^{y} \sum_{k=t}^{y}=\sum_{k=x}^{y} \sum_{t=x}^{k}\right)\\ &=\sum_{k=1}^{\infty} \alpha \delta_{k}^{s} \sum_{t=1}^{k} \rho_{t} \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \rho_{i} \end{aligned} \]

  若上式的第二个求和项可写作资格迹并用于更新,则更新式变为基于后向视角的 TD update,也就是若表达式为 k 时刻的 trace,那他可由 k-1 时刻的值更新而得:

\[ \begin{aligned} \mathbf{z}_{k} &=\sum_{t=1}^{k} \rho_{t} \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \rho_{i} \\ &=\sum_{t=1}^{k-1} \rho_{t} \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \rho_{i}+\rho_{k} \nabla \hat{v}\left(S_{k}, \mathbf{w}_{k}\right) \\ &=\gamma_{k} \lambda_{k} \rho_{k} \sum_{t=1}^{k-1} \rho_{t} \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \prod_{i=t+1}^{k-1} \gamma_{i} \lambda_{i} \rho_{i} \\ &=\rho_{k}\left(\gamma_{k} \lambda_{k} \mathbf{z}_{k-1}+\nabla \hat{v}\left(S_{k}, \mathbf{w}_{k}\right)\right) \end{aligned} \]

  更加通用的形式:

\[ \mathbf{z}_{t} = \rho_{t}\left(\gamma_{t} \lambda_{t} \mathbf{z}_{t-1}+\nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right)\right) \]

  这个资格迹结合半梯度 TD(\(\lambda\)) 更新即为一般的 TD(\(\lambda\)) 算法,\(\rho_t=1\) 时就变成了同策算法。在异策情况下,算法性能还不错,但是作为一个半梯度算法,稳定性欠佳。
  基于状态价值的情况类似,基于动作价值的 \(\lambda\)-return :

\[ \begin{aligned} G_{t}^{\lambda a} & = R_{t+1}+\gamma_{t+1}\left(\left(1-\lambda_{t+1}\right) \bar{V}_{t}\left(S_{t+1}\right)+\lambda_{t+1}\left[\rho_{t+1} G_{t+1}^{\lambda a}+\bar{V}_{t}\left(S_{t+1}\right)-\rho_{t+1} \hat{q}\left(S_{t+1}, A_{t+1}, \mathbf{w}_{t}\right)\right]\right) \\ &=R_{t+1}+\gamma_{t+1}\left(\bar{V}_{t}\left(S_{t+1}\right)+\lambda_{t+1} \rho_{t+1}\left[G_{t+1}^{\lambda a}-\hat{q}\left(S_{t+1}, A_{t+1}, \mathbf{w}_{t}\right)\right]\right) \end{aligned}\\ \bar{V}_{t}(s) = \sum_{a} \pi(a | s) \hat{q}\left(s, a, \mathbf{w}_{t}\right) \]

  用基于动作价值的 TD error 来逼近 \(\lambda\)-return :

\[ G_{t}^{\lambda a} \approx \hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right)+\sum_{k=t}^{\infty} \delta_{k}^{a} \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \rho_{i} \\ \delta_{t}^{a}=R_{t+1}+\gamma_{t+1} \bar{V}_{t}\left(S_{t+1}\right)-\hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right) \]

  做类似变换,得到动作价值下的资格迹:

\[ \mathbf{z}_{t} \doteq \gamma_{t} \lambda_{t} \rho_{t} \mathbf{z}_{t-1}+\nabla \hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right) \]

  将其用于半梯度更新可得到更一般的 SARSA(\(\lambda\)) ,同样可通用于同策和异策。
  当 \(\lambda=1\) 这些算法和 MC 联系密切,而 \(\lambda \lt 1\) 时,上面所有的 off-policy 算法都将面临致命三因素(the deadly triad),也就是 approximation、bootstrapping、off-policy 这三个问题。

Watkins's Q(\(\lambda\)) to Tree-Backup(\(\lambda\))

  Watkins's Q(\(\lambda\)) 是在 Q-learning 上使用资格迹的算法,若采取 greedy action,则对资格迹进行衰退,否则,就将首个 non-greedy action 之后的迹重置为 0。backup 图如下:

  将资格迹结合进无需 importance sampling 的 n-step tree backup 算法就得到了 \(TB(\)$)。backup 图如下:

  它使用的 \(\lambda\)-return 是基于动作价值的递归式:

\[ \begin{aligned} G_{t}^{\lambda a} & \doteq R_{t+1}+\gamma_{t+1}\left(\left(1-\lambda_{t+1}\right) \bar{V}_{t}\left(S_{t+1}\right)+\lambda_{t+1}\left[\sum_{a \neq A_{t+1}} \pi\left(a | S_{t+1}\right) \hat{q}\left(S_{t+1}, a, \mathbf{w}_{t}\right)+\pi\left(A_{t+1} | S_{t+1}\right) G_{t+1}^{\lambda a}\right]\right) \\ &=R_{t+1}+\gamma_{t+1}\left(\bar{V}_{t}\left(S_{t+1}\right)+\lambda_{t+1} \pi\left(A_{t+1} | S_{t+1}\right)\left(G_{t+1}^{\lambda a}-\hat{q}\left(S_{t+1}, A_{t+1}, \mathbf{w}_{t}\right)\right)\right) \end{aligned} \]

  对 \(\lambda\)-return 做逼近可得:

\[ \begin{aligned} &\delta_{t}^{a}=R_{t+1}+\gamma_{t+1} \bar{V}_{t}\left(S_{t+1}\right)-\hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right)\\ &G_{t}^{\lambda a} \approx \hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right)+\sum_{k=t}^{\infty} \delta_{k}^{a} \prod_{i=t+1}^{k} \gamma_{i} \lambda_{i} \pi\left(A_{i} | S_{i}\right) \end{aligned} \]

  即可得到资格迹的更新式:

\[ \mathbf{z}_{t} \doteq \gamma_{t} \lambda_{t} \pi\left(A_{t} | S_{t}\right) \mathbf{z}_{t-1}+\nabla \hat{q}\left(S_{t}, A_{t}, \mathbf{w}_{t}\right) \]

  按照之前的更新规则可得:

\[ \mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha \delta_{t} \mathbf{z}_{t} \]

  这便是 TB(\(\lambda\)) 算法,不是非常稳定,还需要结合其他 方法。

Stable Off-policy Methods with Traces

  前面介绍的一些资格迹方法是可以在异策中取得稳定解的,下面四种最为重要的使用了自益和折扣的函数,他们的思想都是基于 Gradient-TD 和 Emphatic-TD。下面的算法都假定了线性函数逼近这一前提,至于非线性,理论上也能做相似的处理。

  • GTD(\(\lambda\)) :TDC 算法的资格迹形式,目标参数:\(\hat{v}(s, \mathbf{w}) \doteq \mathbf{w}_{t}^{\top} \mathbf{x}(s) \approx v_{\pi}(s)\)。更新式: \[ \begin{aligned} \mathbf{w}_{t+1} & \doteq \mathbf{w}_{t}+\alpha \delta_{t}^{s} \mathbf{z}_{t}-\alpha \gamma_{t+1}\left(1-\lambda_{t+1}\right)\left(\mathbf{z}_{t}^{\top} \mathbf{v}_{t}\right) \mathbf{x}_{t+1} \\ \mathbf{v}_{t+1} & \doteq \mathbf{v}_{t}+\beta \delta_{t}^{s} \mathbf{z}_{t}-\beta\left(\mathbf{v}_{t}^{\top} \mathbf{x}_{t}\right) \mathbf{x}_{t} \end{aligned} \]
  • GQ(\(\lambda\)) :Gradient-TD 算法(基于动作价值)的资格迹形式,目标参数:\(\hat{q}\left(s, a, \mathbf{w}_{t}\right) \doteq \mathbf{w}_{t}^{\top} \mathbf{x}(s, a) \approx q_{\pi}(s, a)\)。更新式: \[ \begin{array}{l} {\mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha \delta_{t}^{a} \mathbf{z}_{t}-\alpha \gamma_{t+1}\left(1-\lambda_{t+1}\right)\left(\mathbf{z}_{t}^{\top} \mathbf{v}_{t}\right) \overline{\mathbf{x}}_{t+1}} \\ {\overline{\mathbf{x}}_{t} \doteq \sum_{a} \pi\left(a | S_{t}\right) \mathbf{x}\left(S_{t}, a\right)} \\ {\delta_{t}^{a} \doteq R_{t+1}+\gamma_{t+1} \mathbf{w}_{t}^{\top} \overline{\mathbf{x}}_{t+1}-\mathbf{w}_{t}^{\top} \mathbf{x}_{t}} \end{array} \]
  • HTD(\(\lambda\)) :由 GTD(\(\lambda\)) 和 TD(\(\lambda\)) 的结合算法,目标参数:\(\hat{v}(s, \mathbf{w}) \doteq \mathbf{w}_{t}^{\top} \mathbf{x}(s) \approx v_{\pi}(s)\) 。更新式: \[ \begin{aligned} \mathbf{w}_{t+1} & \doteq \mathbf{w}_{t}+\alpha \delta_{t}^{s} \mathbf{z}_{t}+\alpha\left(\left(\mathbf{z}_{t}-\mathbf{z}_{t}^{b}\right)^{\top} \mathbf{v}_{t}\right)\left(\mathbf{x}_{t}-\gamma_{t+1} \mathbf{x}_{t+1}\right) \\ \mathbf{v}_{t+1} & \doteq \mathbf{v}_{t}+\beta \delta_{t}^{s} \mathbf{z}_{t}-\beta\left(\mathbf{z}_{t}^{b} \mathbf{v}_{t}\right)\left(\mathbf{x}_{t}-\gamma_{t+1} \mathbf{x}_{t+1}\right), \quad \text { with } \mathbf{v}_{0} \doteq \mathbf{0} \\ \mathbf{z}_{t} & \doteq \rho_{t}\left(\gamma_{t} \lambda_{t} \mathbf{z}_{t-1}+\mathbf{x}_{t}\right), \quad \text { with } \mathbf{z}_{-1} \doteq \mathbf{0} \\ \mathbf{z}_{t}^{b} & \doteq \gamma_{t} \lambda_{t} \mathbf{z}_{t-1}^{b}+\mathbf{x}_{t}, \quad \text { with } \mathbf{z}_{-1}^{b} \doteq \mathbf{0} \end{aligned} \]
  • Emphatic TD(\(\lambda\)) :Emphatic TD 的资格迹形式,目标参数:\(\hat{v}(s, \mathbf{w}) \doteq \mathbf{w}_{t}^{\top} \mathbf{x}(s) \approx v_{\pi}(s)\),此算法在异策情况下收敛性很强,代价是高方差、慢速,允许任何程度的自益。更新式: \[ \begin{aligned} &\mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha \delta_{t} \mathbf{z}_{t}\\ &\delta_{t} \doteq R_{t+1}+\gamma_{t+1} \mathbf{w}_{t}^{\top} \mathbf{x}_{t+1}-\mathbf{w}_{t}^{\top} \mathbf{x}_{t}\\ &\mathbf{z}_{t} \doteq \rho_{t}\left(\gamma_{t} \lambda_{t} \mathbf{z}_{t-1}+M_{t} \mathbf{x}_{t}\right), \text { with } \mathbf{z}_{-1} \doteq \mathbf{0}\\ &M_{t} \doteq \lambda_{t} I_{t}+\left(1-\lambda_{t}\right) F_{t}\\ &F_{t} \doteq \rho_{t-1} \gamma_{t} F_{t-1}+I_{t}, \quad \text { with } F_{0} \doteq i\left(S_{0}\right) \end{aligned} \]   其中,\(M_t \ge 0\) 代表 emphasis,\(F_t \ge 0\) 代表 followon trace,\(I_t \ge 0\) 代表 interest。

总结

  本文根据强化学习圣经记录了许多资格迹的算法,几乎强化学习中的所有算法都能结合资格迹,需要好好的理解。

Refer

相关内容


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. \(\lambda\)-return
  3. 3. TD(\(\lambda\))
  4. 4. n-step Truncated \(\lambda\)-return Methods
  5. 5. Redoing Updates: The Online \(\lambda\) -return Algorithm
  6. 6. True Online TD(\(\lambda\))
  7. 7. Dutch Traces in Monte Carlo Learning
  8. 8. SARSA(\(\lambda\))
  9. 9. Variable \(\lambda\) and \(\gamma\)
  10. 10. Off-policy Traces with Control Variates
  11. 11. Watkins's Q(\(\lambda\)) to Tree-Backup(\(\lambda\))
  12. 12. Stable Off-policy Methods with Traces
  13. 13. 总结
  14. 14. Refer
  15. 15. 相关内容
您是第 位小伙伴 | 本站总访问量 | 已经写了 670.5k 字啦

载入天数...载入时分秒...