《强化学习》学习笔记（二）

《强化学习》学习笔记（二）

第二部分 表格型近似求解方法

• 在第二部分，会将第一部分的表格型方法扩展到拥有任意大的状态空间的问题上
• 在这种情况下，目标不是找到最优策略或最优价值函数，而是使用有限的计算资源找到一个比较好的近似解
• 第九章：预测问题，给定策略，去逼近其价值函数
• 第十章：控制问题，介绍最优策略的近似
• 第十一章：对离轨策略进行函数逼近
• 第十二章：资格迹
• 第十三章：策略梯度方法，直接对最优策略进行逼近，且不需要近似的价值函数

Chap 9. 基于函数逼近的同轨策略预测

• 价值函数逼近

  • 通过采样获取数据（状态，价值），然后使用有监督学习来近似价值函数
  • 这样的近似实际上也是一种泛化
  • 有监督学习算法需要支持在线学习，因为学习的目标函数是非平稳的

• 预测目标（$\overline{\mathrm {VE}}$）

  • 在函数逼近中，一个状态的价值估计越准确就意味着别的状态的估计不那么准确

  • 需要制定一个状态的分布$\mu(s)\geq0,\ \sum_s\mu(s)=1$来表示对每个状态$s$误差的重视程度

    • 如使用均方价值误差

    • \[\overline{\mathrm{VE}}(\mathbf w)\overset.=\sum_{s\in\mathcal S}\mu(s)\Big[v_\pi(s)-\hat v(s,\mathbf w)\Big]^2\]
    • $\mu(s)$通常定义为将在状态$s$上消耗的计算时间的比例

  • 同轨策略分幕式任务中，可令$h(s)$表示从状态$s$开始一幕交互序列的概率，则可以求解状态期望访问次数$\eta(s)$

    • \[\eta(s)=h(s)+\sum_\overline s\eta(\overline s)\sum_a\pi(a\vert \overline s)p(s\vert \overline s,a),\ \forall s\in \mathcal S\\ \mu(s)=\frac{\eta(s)}{\sum_{s'}\eta(s')}\]

• 随机梯度和半梯度方法

  • 假设每一步观察到一个新样本$S_t\mapsto v_\pi(S_t)$，显然有

    • \[\begin{align} \mathbf w_{t+1}\overset.=&\mathbf w_t-\frac{1}{2}\alpha\nabla\Big[v_\pi(S_t)-\hat v(S_t,\mathbf w_t)\Big]^2\\ =&\mathbf w_t+\alpha\Big[v_\pi(S_t)-\hat v(S_t,\mathbf w_t)\Big]\nabla\hat v(S_t,\mathbf w_t) \end{align}\]

  • 实际上观察到的样本可能是$S_t\mapsto U_t$，其中$U_t$是$v_\pi(S_t)$的带噪版本无偏估计

    • 因此有梯度蒙特卡洛算法，对每一步

      • \[\mathbf w\leftarrow \mathbf w+\alpha[G_t-\hat v(S_t,\mathbf w)]\nabla\hat v(S_t,\mathbf w)\]

    • 如果使用自举法，由于在n步之后的价值取决于权值向量$\mathbf w_t$的当前值，意味着它是有偏的。

      • 只包含一部分梯度，被称为半梯度方法

  • 状态聚合

    • 一种简单形式的泛化函数逼近
    • 状态被分到不同的组，每一个组内状态的价值估计都是同一个数

• 线性方法

  • 用向量$\mathbf x(s)$表示$s$的特征向量，特征的每一个维度都是关于$s$的函数，对于线性方法，特征被称为基函数

    • \[\hat v(s,\mathbf w)\overset.=\mathbf w^\mathrm T\mathbf x(s)\]

  • 对随机梯度有

    • \[\mathbf w_{t+1}\overset.=\mathbf w_t+\alpha\Big[U_t-\hat v(S_t,\mathbf w_t)\Big]\nabla\hat v(S_t,\mathbf w_t)=\mathbf w_t+\alpha\Big[U_t-\hat v(S_t,\mathbf w_t)\Big]\mathbf x(s)\]

  • 对半梯度TD(0)算法有

    • \[\begin{align} \mathbf w_{t+1}\overset.=&\mathbf w_t+\alpha\Big(R_{t+1}+\gamma\mathbf w_t^\mathrm T\mathbf x_{t+1}-\mathbf w_t^\mathrm T\mathbf x_t\Big)\mathbf x_t\\ =&\mathbf w_t+\alpha\Big(R_{t+1}\mathbf x_t-\mathbf x_t(\mathbf x_t-\gamma\mathbf x_{t+1})^\mathrm T\mathbf w_t\Big) \end{align}\]

  • n步半梯度TD

    • \[\mathbf w_{t+n}\overset.=\mathbf w_{t+n-1}+\alpha\Big[G_{t:t+n}-\hat v(S_t,\mathbf w_{t+n-1})\Big]\nabla\hat v(S_t,\mathbf w_{t+n-1})\\ G_{t:t+n}\overset.=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{n-1}R_{t+n}+\gamma^n\hat v(S_{t+n},\mathbf w_{t+n-1}),\ 0\leq t\leq T-n\]

• 线性方法的特征构造

  • 多项式基

    • 如$\mathbf x(s)=(1,s_1,s_2,s_1s_2,s_1^2,s_2^2,\cdots)^\mathrm T$

  • 傅立叶基

    • 一维n阶傅立叶余弦基：$x_i(s)=\cos(i\pi s),\ s\in[0,1]$

  • 粗编码

    • 当状态集在一个连续二维空间上
    • 可以用圆来表示特征，如果状态在圆内，则为$1$，否则为$0$（也可以不是圆，以及不是二值）
    • 显然当更新一个状态时，覆盖它的圆所覆盖的所有状态价值也会被影响

  • 瓦片编码

    • 一种用于多维连续空间的粗编码
    • 特征的感受野组成状态空间中的一系列划分；每个划分称为一个覆盖，划分中的每个元素被称为瓦片

  • 径向基函数

    • 是粗编码在连续特征（实数）中的自然推广

    • \[x_i(s)\overset.=\exp\Big(-\frac{\parallel s-c_i\parallel^2}{2\sigma_i^2}\Big)\]

• 手动选择步长参数

  • 从基本上相同的特征向量的$\tau$次经验来学习，一个好的粗略经验法

    • \[\alpha\overset.=(\tau\mathbb E[\mathbf x^\mathrm T\mathbf x])^{-1}\]

• 非线性函数逼近：人工神经网络

• 最小二乘时序差分

  • 在前面的半梯度TD(0)算法中有

    • \[\mathbf w_{t+1}\overset.=\mathbf w_t+\alpha\Big(R_{t+1}\mathbf x_t-\mathbf x_t(\mathbf x_t-\gamma\mathbf x_{t+1})^\mathrm T\mathbf w_t\Big)\]

  • 令$\mathbf A\overset.=\mathbb E[\mathbf x_t(\mathbf x_t-\gamma \mathbf x_{t+1})^\mathrm T],\ \mathbf b\overset.=\mathbb E[R_{t+1}\mathbf x_t]$，则有

    • \[\mathbf w_{t+1}\overset.=\mathbf w_t+\alpha\Big(\mathbf b-\mathbf {Aw}_t\Big)\]
    • 因此有不动点$\mathbf w=\mathbf A^{-1}\mathbf b$

  • 可以直接求解期望计算不动点，而不迭代求解

    • \[\mathbf w_t\overset.=\hat {\mathbf A}_t^{-1}\hat{\mathbf b}_t\\ \hat{\mathbf A}_t\overset.=\sum_{k=0}^{t-1}\mathbf x_k(\mathbf x_k-\gamma \mathbf x_{k+1})^\mathrm T+\epsilon\mathbf I\\ \hat{\mathbf b}_t\overset.=\sum_{k=0}^{t-1}R_{t+1}\mathbf x_k\]

  • 上述方法虽然可以直接求解不动点，但是在新的时间步存在逆矩阵的计算，但是可以实现增量式逆矩阵更新，时间复杂度为$O(d^2)$，依然高于半梯度TD的$O(d)$复杂度

• 基于记忆的函数逼近

  • 保存看到过的训练样本（或样本子集）而不更新参数 ，当需要查询状态价值时，从基于记忆中检索查找出一组样本，然后使用这些样本来计算查询状态的价值估计值。这种方法有时被称为懒惰学习(lazy learning)
  • 最简单例子：最近邻居法（$s’\mapsto g$是记忆中的样本，且$s’$是离$s$最近的状态，那么$g$就作为$s$的近似值）
  • 复杂一点：加权平均法（可以让权重随着距离增加而减小）
  • 其他：局部加权回归法（回归一个曲面最小化加权误差？）

• 基于核函数的函数逼近

  • 前面的权重方法会给记忆的样本分配权值；而权值往往基于两个状态$s,s’$之间的距离，分配权值的函数我们称之为核函数

  • 根据距离分配权值：$\kappa:\mathbb R\rightarrow \mathbb R$

  • 根据相似度分配权值：$\kappa: \mathcal S\times\mathcal S\rightarrow\mathbb R$

  • 核函数回归基于记忆

    • \[\hat v(s,\mathcal D)=\sum_{s'\in\mathcal D}\kappa(s,s')g(s')\]

• 深入了解同轨策略学习：“兴趣”与“强调”

  • 非负随机标量变量：兴趣值$I_t$

    • 表示在时刻$t$有多大的兴趣要精确估计一个状态（或二元组）的价值

  • 非负随机标量变量：强调值$M_t$

    • 这个标量会被乘上学习过程中的更新量，因此决定了在时刻$t$强调或不强调学习

  • 则对于一般的n步学习法，有

    • \[\mathbf w_{t+n}\overset .=\mathbf w_{t+n-1}+\alpha M_t\Big[G_{t:t+n}-\hat v(S_t, \mathbf w_{t+n-1})\Big]\nabla\hat v(S_t,\mathbf w_{t+n-1})\\ M_t=I_t+\gamma ^nM_{t-n}\]

Chap 10. 基于函数逼近的同轨策略控制

• 分幕式半梯度控制

  • 对于动作价值函数的梯度下降更新，样本变为$S_t,A_t\mapsto U_t$，$U_t$可以是$q_\pi(S_t,A_t)$的任意近似

    • \[\mathbf w_{t+1}\overset.=\mathbf w_t+\alpha\Big(U_t-\hat q(S_t,A_t,\mathbf w_t)\Big)\nabla\hat q(S_t,A_t,\mathbf w_t)\]

  • 对于单步Sarsa有

    • \[\mathbf w_{t+1}\overset.=\mathbf w_t+\alpha\Big(R_{t+1}+\gamma\hat q(S_{t+1},A_{t+1},\mathbf w_{t})-\hat q(S_t,A_t,\mathbf w_t))\Big)\nabla\hat q(S_t,A_t,\mathbf w_t)\]

• 半梯度n步Sarsa

  • n步回报

    • \[G_{t:t+n}\overset.=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{n-1}R_{t+n}+\gamma^n\hat q(S_{t+n},A_{t+n},\mathbf w_{t+n-1})\]

  • 更新公式

    • \[\mathbf w_{t+n}\overset .=\mathbf w_{t+n-1}+\alpha\Big[G_{t:t+n}-\hat q(S_t,A_t,\mathbf w_{t+n-1})\Big]\nabla\hat q(S_t,A_t,\mathbf w_{t+n-1})\]

• 平均收益：持续性任务中的新的问题设定

  • 折扣设定对函数逼近来说是有问题的，因此需要用平均收益$r(\pi)$来定义策略的质量

    • \[\begin{align} r(\pi)\overset.=&\lim_{h\rightarrow\infty}\frac{1}{h}\sum_{t=1}^h\mathbb E[R_t\vert S_0,A_{0:t-1}\sim\pi]\\ =&\lim_{t\rightarrow \infty}\mathbb E[R_t\vert S_0,A_{0:t-1}\sim\pi]\\ =&\sum_s \mu_\pi(s)\sum_a\pi(a\vert s)\sum_{s',r}p(s',r\vert s,a)r \end{align}\]

    • 其中$\mu_\pi(s)$是一个稳态分布，有$\mu(s)\overset.=\lim_{t\rightarrow\infty}\Pr{S_t=s\vert A_{0:t-1}\sim\pi}$，这意味着长远地看稳态分布只与策略本身以及MDP的转移概率相关

    • 认为所有达到$r(\pi)$最大值的策略都是最优的

  • 在平均收益设定中，回报是根据即时收益和平均收益的差来定义的

    • \[G_t\overset.=R_{t+1}-r(\pi)+R_{t+2}-r(\pi)+\cdots\]

    • 被称为差分回报，相应的价值函数被称为差分价值函数

    • \[v_\pi(s)\overset.=\mathbb E[G_t\vert S_t=s]\\ q_\pi(s,a)\overset.=[G_t\vert S_t=s,A_t=a]\]

  • 对于两类TD误差，也有对应的差分形式

    • \[\delta_t\overset.=R_{t+1}-\overline R_{t+1}+\hat v(S_{t+1},\mathbf w_t)-\hat v(S_t,\mathbf w_t)\\ \delta_t\overset.=R_{t+1}-\overline R_{t+1}+\hat q(S_{t+1},A_{t+1},\mathbf w_t)-\hat v(S_t,A_t,\mathbf w_t)\]

  • 对于梯度更新则有

    • \[\mathbf w_{t+1}\overset.=\mathbf w_t+\alpha\delta_t\nabla\hat q(S_t,A_t,\mathbf w_t)\]

• 弃用折扣

  • 持续性问题中折扣的无用性

    • 设定策略排序准则为折后价值的概率加权和

    • \[\begin{align} J(\pi)&=\sum_s\mu_\pi(s)v_\pi^\gamma(s)&这里v_\pi^\gamma是折后价值函数\\ &=\sum_s\mu_\pi(s)\sum_a\pi(a\vert s)\sum_{s'}\sum_rp(s',r\vert s,a)[r+\gamma v_\pi^\gamma(s')]&贝尔曼公式\\ &=r(\pi)+\sum_s\mu_\pi(s)\sum_a\pi(a\vert s)\sum_{s'}\sum_rp(s',r\vert s,a)\gamma v_\pi^\gamma(s')\\ &=r(\pi)+\gamma\sum_{s'}v_\pi^\gamma(s')\sum_s\mu_\pi(s)\sum_a\pi(a\vert s)p(s' \vert s,a)\\ &=r(\pi)+\gamma\sum_{s'}v_\pi^\gamma(s')\mu_\pi(s')\\ &=r(\pi)+\gamma J(\pi)\\ &=r(\pi)+\gamma r(\pi)+\gamma^2r(\pi)+\cdots\\ &=\frac{1}{1-\gamma}r(\pi) \end{align}\]

    • 可以发现折扣率$\gamma$的改变完全不会影响到策略的大小顺序

    • 并且在函数逼近的折扣控制设定中，策略改进定理不再存在，我们在单个状态上改进折后价值函数不再保证我们会改进整个策略。

    • 策略改进理论的缺失也是分幕式设定以及平均收益设定的理论缺陷

• 差分半梯度n步Sarsa

  • n步回报

    • \[G_{t:t+n}\overset.=R_{t+1}-\overline R_{t+1}+R_{t+2}-\overline R_{t+2}+\cdots+R_{t+n}-\overline R_{t+n}+\hat q(S_{t+n},A_{t+n},\mathbf w_{t+n-1}),&t+n<T\\ G_{t:t+n}\overset.=G_t,&t+n\geq T\]
    • 其中，$\overline R$是对$r(\pi)$的估计

  • n步TD误差

    • \[\delta_t\overset.=G_{t:t+n}-\hat q(S_t,A_t,\mathbf w)\]

  • 更新

    • \[\delta\leftarrow \sum_{i=\tau+1}^{\tau+n}(R_i-\overline R)+\hat q(S_{\tau+n},A_{\tau+n},\mathbf w)-\hat q(S_\tau,A_\tau,\mathbf w)\\ \overline R\leftarrow \overline R+\beta\delta\\ \mathbf w\leftarrow\mathbf w+\alpha\delta \nabla\hat q(S_\tau,A_\tau,\mathbf w)\]

Chap 11. 基于函数逼近的离轨策略方法

• 半梯度方法

  • 重要度采样率

    • \[\rho_t\overset.=\rho_{t:t}=\frac{\pi(A_t\vert S_t)}{b(A_t\vert S_t)}\]

  • 单步状态价值函数算法：半梯度的离轨TD(0)

    • \[\mathbf w_{t+1}\overset.=\mathbf w_t+\alpha\rho_t\delta_t\nabla\hat v(S_t,\mathbf w_t)\]

    • 其中，$\delta_t$的确切定义取决于问题是分幕式+有折扣或者持续性+无折扣

    • \[\begin{align} \delta_t\overset.=&R_{t+1}+\gamma\hat v(S_{t+1},\mathbf w_t)-\hat v(S_t,\mathbf w_t)&(分幕式任务)\\ \delta_t\overset.=&R_{t+1}-\overline R+\hat v(S_{t+1},\mathbf w_t)-\hat v(S_t,\mathbf w_t)&(持续性任务) \end{align}\]

  • 单步动作价值函数算法：半梯度的期望Sarsa

    • \[\mathbf w_{t+1}\overset.=\mathbf w_t+\alpha\delta_t\nabla\hat q(S_t,A_t,\mathbf w_t)\]
    • \[\begin{align} \delta_t\overset.=&R_{t+1}+\gamma\sum_a\pi(a\vert S_{t+1})\hat q(S_{t+1},a,\mathbf w_t)-\hat q(S_t,A_t,\mathbf w_t)&(分幕式任务)\\ \delta_t\overset.=&R_{t+1}-\overline R+\sum_a\pi(a\vert S_{t+1})\hat q(S_{t+1},a,\mathbf w_t)-\hat q(S_t,A_t,\mathbf w_t)&(持续性任务) \end{align}\]
    • 注意该算法并未使用重要度采样。在表格型情形下，单步算法在更新动作价值时状态$s$和动作$a$都是确定的，因此不需要考虑其他动作。但是在使用函数逼近的情况下，就没有这么确定了，因为可能希望给不同的“状态-动作”二元组以不同的权重。

  • 多步算法中，都包含了重要度采样

  • n步Sarsa

    • \[\mathbf w_{t+n}\overset.=\mathbf w_{t+n-1}+\alpha\rho_{t+1}\cdots\rho_{t+n-1}[G_{t:t+n}-\hat q(S_t,A_t,\mathbf w_{t+n-1})]\nabla\hat q(S_t,A_t,\mathbf w_{t+n-1})\\ \rho_k=1,\ k\geq T\]
    • \[\begin{align} G_{t:t+n}\overset.=&R_{t+1}+\cdots+\gamma^{n-1}R_{t+n}+\gamma^n\hat q(S_{t+n},A_{t+n},\mathbf w_{t+n-1})&(分幕式任务)\\ G_{t:t+n}\overset.=&R_{t+1}-\overline R_{t}+\cdots+R_{t+n}-\overline R_{t+n-1}+\hat q(S_{t+n},A_{t+n},\mathbf w_{t+n-1})&(持续性任务) \end{align}\]

  • 对于完全不包含重要度采样的n步树回溯算法的半梯度版本

    • \[\mathbf w_{t+n}\overset.=\mathbf w_{t+n-1}+\alpha[G_{t:t+n}-\hat q(S_t,A_t,\mathbf w_{t+n-1})]\nabla\hat q(S_t,A_t,\mathbf w_{t+n-1})\\ G_{t:t+n}\overset.=\hat q(S_t,A_t,\mathbf w_{t-1})+\sum_{k=t}^{t+n-1}\delta_k\prod_{i=t+1}^k\gamma \pi(A_i\vert S_i)\]
    • $\delta_t$定义与上面期望Sarsa相同

• 离轨策略发散的例子

• 致命三要素

  • 只要方法同时满足下面的三个基本要素，就一定会有不稳定和发散的危险。
    • 函数逼近
    • 自举法
    • 离轨策略训练
  • 需要根据实际情况进行取舍

• 线性价值函数的几何性质

  • 假设状态空间为$\mathcal S={s_1,s_2,\cdots,s_{\vert \mathcal S\vert}}$，则对于任意价值函数$v$可表示为一个向量$[v(s_1),v(s_2),\cdots,v(s_{\vert\mathcal S\vert})]^\mathrm T$

  • 因此每一个价值函数可以看作是$\vert\mathcal S\vert$维空间上的一个点

  • 当使用n维向量$\mathbf w$作为线性价值函数的参数时，最优解实际上就是最优价值函数在n维空间的投影

  • 需要注意投影时不同维度的权重可能不同

    • 如根据状态的稳态分布来定义距离

    • \[\parallel v\parallel_\mu^2\overset .=\sum_{s\in\mathcal S}\mu(s)v(s)^2\]

  • 投影矩阵

    • 另矩阵$\mathbf D$为对角阵，对角线元素为$\mu(s)$，$\mathbf X$为$\vert\mathcal S\vert\times d$的矩阵，每一行对应一个状态$s$的特征向量$x(s)^\mathrm T$

    • 则有$\parallel v\parallel_\mu^2=v^\mathrm T\mathbf Dv$

    • 投影矩阵

      • \[\mathbf \Pi\overset .=\mathbf X(\mathbf X^\mathrm T\mathbf {DX})^{-1}\mathbf X^\mathrm T\mathbf D\]

    • 近似的线性价值函数可以写为

      • \[v_{\mathbf w}=\mathbf {Xw}\]

  • 贝尔曼误差

    • 在贝尔曼方程中只有最优价值函数是唯一解

    • 考虑使用$v_{\mathbf w}$替换$v_\pi$，则改变后方程两侧的差值可以用于衡量$v_{\mathbf w}$与$v_\pi$之间的差距。称之为在状态$s$时的贝尔曼误差

    • \[\begin{align} \overline \delta_{\mathbf w}(s)\overset.=&\Big(\sum_a\pi(a\vert s)\sum_{s',r}p(s',r\vert s,a)[r+\gamma v_\pi(s')]\Big),\ \forall s\in\mathcal S\\ =&\mathbb E[R_{t+1}+\gamma v_{\mathbf w}(S_{t+1})-v_{\mathbf w}(S_t)\vert S_t=s,A_t\sim\pi] \end{align}\]

    • 贝尔曼误差实际上是TD误差的期望

    • $\overline\delta_{\mathbf w}\in\mathbb R^{\vert\mathcal S\vert}$被称作贝尔曼误差向量

    • $\overline{\mathrm {BE}}(\mathbf w)=\parallel\overline\delta_{\mathbf w}\parallel_\mu^2$被称作均方贝尔曼误差

    • $\overline{\mathrm{PBE}}=\parallel \mathbf \Pi\overline\delta_{\mathbf w}\parallel_\mu^2$被称作均方投影贝尔曼误差

• 对贝尔曼误差做梯度下降

  • 带折扣的单步TD误差

    • \[\delta_t=R_{t+1}+\gamma\hat v(S_{t+1},\mathbf w)-\hat v(S_t,\mathbf w)\]

  • 均方TD误差

    • \[\begin{align} \overline{\mathrm{TDE}}(\mathbf w)=&\sum_{s\in\mathcal S}\mu(s)\mathbb E[\delta_t^2\vert S_t=s,A_t\sim \pi]\\ =&\sum_{s\in\mathcal S}\mu(s)\mathbb E[\rho_t\delta_t^2\vert S_t=s,A_t\sim\pi]\\ =&\mathbb E_b[\rho_t\delta_t^2] \end{align}\]

  • 以均方TD误差作为目标函数，则有：（称为朴素残差梯度算法）

    • \[\begin{align} \mathbf w_{t+1}=&\mathbf w_t-\frac{1}{2}\alpha\nabla(\rho_t\delta_t^2)\\ =&\mathbf w_t-\alpha\rho_t\delta_t\nabla\delta_t\\ =&\mathbf w_t-\alpha\rho_t\delta_t(\nabla\hat v(S_t,\mathbf w)-\gamma\nabla\hat v(S_{t+1},\mathbf w)) \end{align}\]
    • 虽然该算法一定会收敛，但是不一定收敛到想要的地方

  • 考虑以贝尔曼误差（TD误差的期望）作为目标函数，则有：（称为残差梯度算法）

    • \[\begin{align} \mathbf w_{t+1}=&\mathbf w_t-\frac{1}{2}\alpha\nabla(\mathbb E_\pi[\delta_t]^2)\\ =&\mathbf w_t-\frac{1}{2}\alpha\nabla(\mathbb E_b[\rho_t\delta_t]^2)\\ =&\mathbf w_t-\alpha\mathbb E_b[\rho_t\delta_t]\nabla\mathbb E_b[\rho_t\delta_t]\\ =&\mathbf w_t-\alpha\mathbb E_b\Big[\rho_t\big(R_{t+1}+\gamma \hat v(S_{t+1},\mathbf w)-\hat v(S_t,\mathbf w)\big)\Big]\mathbb E_b\big[\rho_t\nabla\delta_t\big]\\ =&\mathbf w_t+\alpha\Big[\mathbb E_b\Big[\rho_t\big(R_{t+1}+\gamma\hat v(S_{t+1},\mathbf w)\big)\Big]-\hat v(S_t,\mathbf w)\Big]\Big[\nabla\hat v(S_t,\mathbf w)-\gamma\mathbb E_b\Big[\rho_t\nabla \hat v(S_{t+1},\mathbf w)\Big]\Big] \end{align}\]

    • 如果在上式中简单地在所有期望中使用采样值，那么该算法就几乎规约到朴素残差梯度算法

    • 为了得到两个期望乘积的无偏样本，需要下一个状态的两个独立样本，但通常在交互过程中只能得到一个（即无法回溯重新采样），可以一个用期望值，一个用采样值。

• 贝尔曼误差是不可学习的

  • 在强化学习中有一些量，即使有无限多的数据，也无法学习到，这样称为不可学习的

    • 即这些量当给定内部环境结构时可以计算出来，但是不能从外部可观测的特征向量、动作和收益的序列中得到
    • 因为特征向量、动作、收益序列可以对应这些量的多种不同可能

  • 引入一个明显可学习的量：均方回报误差$\overline{\mathrm {RE}}$，表示每个时刻的估计价值与这个时刻之后的实际回报的误差

    • \[\begin{align} \overline{\mathrm{RE}}(\mathbf w)=&\mathbb E\Big[\big(G_t-\hat v(S_t,\mathbf w)^2\big)\Big]\\ =&\overline{\mathrm{VE}}(\mathbf w)+\mathbb E\Big[\big(G_t-v_\pi(S_t)\big)^2\Big] \end{align}\]
    • 因此这两个目标必须有相同的最优参数值$\mathbf w^\ast$

  • 贝尔曼误差$\overline{\mathrm{BE}}$在无模型情形下是不可学习的

    • 不同的MDP可以产生相同的数据分布，但是会产生不同的$\overline{\mathrm{BE}}$以及不同的最小化参数$\mathbf w^\ast$
    • 

• 梯度TD方法

  • 考虑最小化$\overline{\mathrm{PBE}}$的SGD方法，前面讨论过，在线性情况下，在TD不动点$\mathbf w_{\mathrm{TD}}$上$\overline{\mathrm{PBE}}=0$，这个解可以用最小二乘法找到，但是每个时间步的时间复杂度为$O(d^2)$，因此寻求$O(d)$且能稳健收敛的SGD方法

  • 重写目标函数

    • \[\begin{align} \overline{\mathrm{PBE}}(\mathbf w)=&\parallel\mathbf\Pi\overline\delta_{\mathbf w}\parallel_{\mu}^2\\ =&(\mathbf \Pi\overline\delta_{\mathbf w})^\mathrm T\mathbf D\mathbf\Pi\overline\delta_{\mathbf w}\\ =&\overline\delta_{\mathbf w}^\mathrm T\mathbf \Pi^\mathrm T \mathbf{D\Pi}\overline\delta_{\mathbf w}\\ =&\overline\delta_{\mathbf w}^\mathrm T\mathbf {DX}(\mathbf X^\mathrm T\mathbf {DX})^{-1}\mathbf X^\mathrm T\mathbf D\overline\delta_{\mathbf w}\\ =&(\mathbf X^\mathrm T\mathbf D\overline\delta_{\mathbf w})^\mathrm T(\mathbf X^\mathrm T\mathbf{DX})^{-1}(\mathbf X^\mathrm T\mathbf D\overline\delta_{\mathbf w}) \end{align}\]

  • 关于$\mathbf w$的梯度为

    • \[\nabla\overline{\mathrm{PBE}}(\mathbf w)=2\nabla[\mathbf X^\mathrm T\mathbf D\overline\delta_{\mathbf w}]^\mathrm T(\mathbf X^\mathrm T\mathbf{DX})^{-1}(\mathbf X^\mathrm T\mathbf D\overline\delta_{\mathbf w})\]

  • 上面的三个因子都可以写成期望形式

    • \[\mathbf X^\mathrm T\mathbf D\overline\delta_{\mathbf w}=\sum_s\mu(s)\mathbf x(s)\overline\delta_{\mathbf w}=\mathbb E[\rho_t\delta_t\mathbf x_t]\]
    • \[\begin{align} \nabla [\mathbf X^\mathrm T\mathbf D\overline\delta_\mathbf w]^\mathrm T=&\nabla\mathbb E[\rho_t\delta_t\mathbf x_t]^\mathrm T\\ =&\mathbb E[\rho_t\nabla\delta_t^\mathrm T\mathbf x_t^\mathrm T]\\ =&\mathbb E[\rho_t\nabla(R_{t+1}+\gamma\mathbf w^\mathrm T\mathbf x_{t+1}-\mathbf w^\mathrm T\mathbf x_t)^\mathrm T\mathbf x_t^\mathrm T]\\ =&\mathbb E[\rho_t(\gamma\mathbf x_{t+1}-\mathbf x_t)\mathbf x_t^\mathrm T] \end{align}\]
    • \[\mathbf X^\mathrm T\mathbf {DX}=\sum_s\mu(s)\mathbf x_s\mathbf x_s^\mathrm T=\mathbb E[\mathbf x_t\mathbf x_t^\mathrm T]\]

  • 则有

    • \[\nabla\overline{\mathrm {PBE}}(\mathbf w)=2\mathbb E[\rho_t(\gamma\mathbf x_{t+1}-\mathbf x_t)\mathbf x_t^\mathrm T]\mathbb E[\mathbf x_t\mathbf x_t^\mathrm T]^{-1}\mathbb E[\rho_t\delta_t\mathbf x_t]\]

    • 显然第一项和第三项依赖于$\mathbf x_{t+1}$，因此直接估计三个期望会得到有偏梯度估计

    • 如果分别估计，则存储和计算的开销依然很大，总的算法依然是$O(d^2)$

  • 梯度TD方法：估计并存储后两个因子，后两个因子的乘积为一个$d$维向量，将这个向量记为$\mathbf v$

    • \[\mathbf v\approx\mathbb E[\mathbf x_t\mathbf x_t^\mathrm T]^{-1}\mathbb E[\rho_t\delta_t\mathbf x_t]\]

    • 这是试图从特征近似$\rho_t\delta_t$的最小二乘解

    • 通过最小化期望平方误差$(\mathbf v^\mathrm T\mathbf x_t-\rho_t\delta_t)^2$增量式地寻找向量$\mathbf v$的标准SGD方法又被称为最小均方规则

      • \[\mathbf v_{t+1}\overset.=\mathbf v_t+\beta\rho_t(\delta_t-\mathbf v_t^\mathrm T\mathbf x_t)\mathbf x_t\]

    • 则参数更新最简单的规则：

      • \[\begin{align} \mathbf w_{t+1}=&\mathbf w_t-\frac{1}{2}\alpha\nabla\overline{\mathrm{PBE}}(\mathbf w_t)\\ =&\mathbf w_t+\alpha\mathbb E[\rho_t(\mathbf x_t-\gamma\mathbf x_{t+1})\mathbf x_t^\mathrm T]\mathbb E[\mathbf x_t\mathbf x_t^\mathrm T]^{-1}\mathbb E[\rho_t\delta_t\mathbf x_t]\\ \approx&\mathbf w_t+\alpha\mathbb E[\rho_t(\mathbf x_t-\gamma\mathbf x_{t+1})\mathbf x_t^\mathrm T]\mathbf v_t\\ \approx&\mathbf w_t+\alpha\rho_t(\mathbf x_t-\gamma\mathbf x_{t+1})\mathbf x_t^\mathrm T\mathbf v_t&(采样) \end{align}\]

      • 注意$\mathbf x_t^\mathrm T\mathbf v_t$是最先完成的，之后整个算法复杂度为$O(d)$

      • 这个算法又被称作GTD2

    • 可以在替换$\mathbf v_t$之前多做几步分析来优化算法

      • \[\begin{align} \mathbf w_{t+1}=&\mathbf w_t+\alpha\mathbb E[\rho_t(\mathbf x_t-\gamma\mathbf x_{t+1})\mathbf x_t^\mathrm T]\mathbb E[\mathbf x_t\mathbf x_t^\mathrm T]^{-1}\mathbb E[\rho_t\delta_t\mathbf x_t]\\ =&\mathbf w_t+\alpha\Big(\mathbb E[\rho_t\mathbf x_t\mathbf x_t^\mathrm T]-\gamma\mathbb E[\rho_t\mathbf x_{t+1}\mathbf x_t^\mathrm T]\Big)\mathbb E[\mathbf x_t\mathbf x_t^\mathrm T]^{-1}\mathbb E[\rho_t\delta_t\mathbf x_t]\\ =&\mathbf w_t+\alpha\Big(\mathbb E[\rho_t\delta_t\mathbf x_t]-\gamma\mathbb E[\rho_t\mathbf x_{t+1}\mathbf x_t^\mathrm T]\mathbb E[\mathbf x_t\mathbf x_t^\mathrm T]^{-1}\mathbb E[\rho_t\delta_t\mathbf x_t]\Big)\\ \approx&\mathbf w_t+\alpha\Big(\mathbb E[\rho_t\delta_t\mathbf x_t]-\gamma\mathbb E[\rho_t\mathbf x_{t+1}\mathbf x_t^\mathrm T]\mathbf v_t\Big)\\ \approx&\mathbf w_t+\alpha\rho_t(\delta_t\mathbf x_t-\gamma\mathbf x_{t+1}\mathbf x_t^\mathrm T\mathbf v_t)&(采样) \end{align}\]

      • 首先计算最后的乘积$\mathbf x_t^\mathrm T\mathbf v_t$，则复杂度同样是$O(d)$

      • 这个算法又被称为带梯度修正的TD(0)（TDC）或者GTD(0)

  • GTD2和TDC都包含两个学习过程，主要过程是学习$\mathbf w$，次要过程是学习$\mathbf v$

    • 主要学习过程的逻辑依赖于次要学习过程结束，至少是近似结束，但是次要过程不依赖于主要过程。这种不对称的依赖称为梯级。
    • 需要次要过程总是处于它的渐进值，即让它足够精确来辅助主要学习过程
    • 如果$\alpha,\beta$分别是主要、次要学习过程步长，那么这些收敛证明通常需要限制$\beta\rightarrow0,\frac{\alpha}{\beta}\rightarrow0$

• 强调TD方法

  • 学习分幕式状态价值函数的单步强调TD算法定义如下：

    • \[\delta_t=R_{t+1}+\gamma\hat v(S_{t+1},\mathbf w_t)-\hat v(S_t,\mathbf w_t)\\ \mathbf w_{t+1}=\mathbf w_{t}+\alpha M_t\rho_t\delta_t\nabla\hat v(S_t,\mathbf w_t)\\ M_t=\gamma\rho_{t-1}M_{t-1}+I_t\]
    • 其中$I_t$为兴趣值，可以取任意值，$M_t$为强调值，初始化为$M_{t-1}=0$

• 减小方差

  • 可以对参数向量的不同部分自适应地设置分离的步长
  • 加权重要度采样
  • 树回溯
  • 允许目标策略部分地由行动策略决定

Chap12. 资格迹

在第7章的n步时序差分中，已经提出了统一时序差分和蒙特卡洛算法的一种方式。而资格迹在此基础上给出了具有明显计算优势的更优雅的算法机制。

在著名的$TD(\lambda)$算法中，$\lambda$就是资格迹的一个应用。这个机制的核心是一个短时记忆向量资格迹$\mathbf z_t\in\mathbb R^d$，以及长时权重向量$\mathbf w_t\in\mathbb R^d$。当参数$\mathbf w_t$的一个分量参与计算并产生一个估计值时，对应的$\mathbf z_t$分量会骤然升高，然后逐渐衰减。在迹归零前，如果发现了非零的时序差分误差，那么相应的$\mathbf w_t$的分量就可以得到学习。迹衰减参数$\lambda\in[0,1]$决定了迹的衰减率。

n步算法的资格迹算法中只需要追踪一个迹向量，而不用存储最近的n个特征向量。另外在遇到一个状态后可以马上学习，而不需要n步的延迟。

前向视图：基于接下来n步的收益及n步之后的状态来更新。而本章中，使用当前的时序差分误差并用资格迹往回看那些已访问的状态，就能够得到几乎一样的更新。这种替代的学习算法称为资格迹的后向视图。

• $\lambda-$回报

  • n步折后收益加预估价值的回报

    • \[G_{t:t+n}\overset.=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{n-1}R_{t+n}+\gamma^n\hat v(S_{t+n},\mathbf w_{t+n-1}),\ 0\leq t\leq T-n\]

  • 一次有效的更新除了以任意的n步回报为目标之外，也可以用不用的n的平均步回报作为更新目标，如$\frac{1}{2}G_{t:t+2}+\frac{1}{2}G_{t:t+4}$。类似地，只要满足权重和为1的加权都是可取的。这样进行更新平均组成的更新被称为复合更新

  • $\lambda-$回报是一种平均n步更新，每一个按$\lambda^{n-1}$进行加权（$\lambda\in[0,1]$），最后乘归一化参数$(1-\lambda)$，如下：

    • \[G_t^\lambda\overset.=(1-\lambda)\sum_{n=1}^\infty \lambda^{n-1}G_{t:t+n}\]
    • 当$\lambda=0$时，$G_t^\lambda=G_{t:t+1}$就是单步回报；当$\lambda=1$时，更新算法就是蒙特卡洛算法

  • $\lambda-$回报半梯度算法

    • \[\mathbf w_{t+1}\overset.=\mathbf w_t+\alpha\Big[G_t^\lambda-\hat v(S_t,\mathbf w_t)\Big]\nabla\hat v(S_t,\mathbf w_t),\ t=0,\cdots,T-1\]

  • 在目前的算法中，理论上都是前向的

• $\mathrm{TD}(\lambda)$

  • 本节介绍基于函数逼近的半梯度$\mathrm {TD}(\lambda)$

  • 通过函数逼近，资格迹$\mathbf z_t\in\mathbb R^d$是一个和权重向量$\mathbf w_t$同维度的向量。

    • 权重向量是一个长期记忆，资格迹是一个短期记忆，持续时间通常少于一幕的长度。

  • 在$\mathrm {TD}(\lambda)$中，资格迹向量更新如下

    • \[\begin{align} &\mathbf z_{-1}\overset .=\mathbf 0\\ &\mathbf z_t\overset.=\gamma\lambda \mathbf z_{t-1}+\nabla\hat v(S_t,\mathbf w_t),\ 0\leq t\leq T \end{align}\]
    • 在线性函数逼近中，$\nabla\hat v(S_t,\mathbf w_t)$就是特征向量$\mathbf x_t$，在这种情况下，资格迹向量就是过去不断衰减的输入向量之和。

  • 权重向量更新为

    • \[\delta_t\overset.=R_{t+1}+\gamma\hat v(S_{t+1},\mathbf w_t)-\hat v(S_t,\mathbf w_t)\\ \mathbf w_{t+1}\overset.=\mathbf w_t+\alpha\delta_t\mathbf z_t\]

  • $\mathrm {TD}(\lambda)$在时间上往回看

• 半梯度$\mathrm{TD}(\lambda)$是$\lambda-$回报半梯度的近似（假设步长较小，将$\mathbf w$视为近似不变则两算法近似相同）

  • \[\begin{align} G_t^\lambda\overset.=&(1-\lambda)\sum_{n=1}^\infty \lambda^{n-1}G_{t:t+n}\\ =&(1-\lambda)\sum_{n=1}^\infty\lambda^{n-1}\Big(\sum_{k=1}^n\gamma^{k-1}R_{t+k}+\gamma^n\hat v(S_{t+n})\Big)\\ =&(1-\lambda)\Big(\sum_{n=1}^\infty\gamma^n\lambda^{n-1}\hat v(S_{t+n})+\sum_{k=1}^\infty\gamma^{k-1}R_{t+k}\sum_{n=k}^\infty\lambda^{n-1}\Big)\\ =&(1-\lambda)\sum_{n=1}^\infty\gamma^n\lambda^{n-1}\hat v(S_{t+n})+\sum_{k=1}^\infty\gamma^{k-1}\lambda^{k-1} R_{t+k}\\ =&\sum_{n=1}^\infty\Big(\gamma^n\lambda^{n-1}\hat v(S_{t+n})-\gamma^n\lambda^{n}\hat v(S_{t+n})+\gamma^{n-1}\lambda^{n-1} R_{t+n}\Big)\\ =&\sum_{n=1}^\infty\gamma^{n-1}\lambda^{n-1}\Big(R_{t+n}+\gamma\hat v(S_{t+n})-\gamma\lambda\hat v(S_{t+n})\Big)\\ =&\sum_{n=1}^\infty\gamma^{n-1}\lambda^{n-1}\Big(R_{t+n}+\gamma\hat v(S_{t+n})-\hat v(S_{t+n-1})\Big)+\hat v(S_t)\\ G_t^\lambda-\hat v(S_t)=&\sum_{n=1}^\infty\gamma^{n-1}\lambda^{n-1}\Big(R_{t+n}+\gamma\hat v(S_{t+n})-\hat v(S_{t+n-1})\Big)\\ =&\sum_{n=1}^\infty\gamma^{n-1}\lambda^{n-1}\delta_{t+n-1}\\ [G_t^\lambda-\hat v(S_t)]\nabla\hat v(S_t)=&\sum_{n=0}^\infty\delta_{t+n}\gamma ^n\lambda^n\nabla\hat v(S_t) \end{align}\]
  • 将时刻$t$的更新分散到后面每一个时刻，即时刻$t+n$更新时，梯度加上$\gamma^n\lambda^n\nabla\hat v(S_t)$

• n-步截断$\lambda-$回报方法

  • 假定数据最远只能到达未来的某个视界$h$，定义时刻$t$的截断$\lambda-$回报为

    • \[G_{t:h}^\lambda\overset.=(1-\lambda)\sum_{n=1}^{h-t-1}\lambda^{n-1}G_{t:t+n}+\lambda^{h-t-1}G_{t:h}\]

  • 则有截断$\mathrm {TD}(\lambda)$（或$\mathrm{TTD}(\lambda)$）

    • \[\mathbf w_{t+n}\overset.=\mathbf w_{t+n-1}+\alpha\Big[G_{t:t+n}^\lambda-\hat v(S_t,\mathbf w_{t+n-1})\Big]\nabla\hat v(S_t,\mathbf w_{t+n-1})\]

  • k步$\lambda-$回报的高效实现

    • \[G_{t:t+k}^\lambda=\hat v(S_t,\mathbf w_{t-1})+\sum_{i=t}^{t+k-1}(\gamma\lambda)^{i-t}\delta_i'\\ \delta_t'\overset.=R_{t+1}+\gamma\hat v(S_{t+1},\mathbf w_t)-\hat v(S_t,\mathbf w_{t-1})\]

• 重做更新：在线$\lambda-$回报算法

  • 在获取一步新的数据时，将前面时刻的权重参数一同更新（假设当前视界为$h$，用当前视界下的每个回报再重新在前面状态下进行更新）

  • 更新的一般形式：

    • \[\mathbf w_{t+1}^h\overset.=\mathbf w_t^h+\alpha[G_{t:h}^\lambda-\hat v(S_t,\mathbf w_t^h)]\nabla\hat v(S_t,\mathbf w_t^h),\ 0\leq t<h\leq T\\ \mathbf w_t\overset.=\mathbf w_t^t\]

• 真实的在线$\mathrm{TD}(\lambda)$

  • 前面的在线$\lambda-$回报算法是效果最好的时序差分算法，但是计算过于复杂。现在考虑将这个前向视图算法转化为一个利用资格迹的有效后向视图算法（在线性函数逼近下，存在一种精确计算实现）

  • 对于$\hat v(s,\mathbf w)=\mathbf w^\mathrm T\mathbf x(s)$的线性情况，下面算法被证明能够产生和在线$\lambda-$回报算法完全相同的权重向量$\mathbf w_t$

    • \[\mathbf w_{t+1}\overset.=\mathbf w_t+\alpha\delta_t\mathbf z_t+\alpha(\mathbf w_t^\mathrm T\mathbf x_t-\mathbf w_{t-1}^\mathrm T\mathbf x_t)(\mathbf z_t-\mathbf x_t)\\ \mathbf z_t\overset.=\gamma\lambda\mathbf z_{t-1}+(1-\alpha\gamma\lambda\mathbf z_{t-1}^\mathrm T\mathbf x_t)\mathbf x_t\]

    • 真实的在线$\mathrm{TD}(\lambda)$算法的资格迹被称为荷兰迹，用以与$\mathrm{TD}(\lambda)$算法中的迹做区分，那种迹被称为积累迹，早期还使用过替换迹，替换迹每个分量定义取决于特征向量中分量是1还是0（如今荷兰迹几乎可以完全取代替代迹）

      • \[z_{i,t}\overset.=\left\{ \begin{align} &1&如果x_{i,t}=1\\ &\gamma\lambda z_{i,t-1}&其他情况 \end{align} \right.\]

• 蒙特卡洛学习中的荷兰迹

  • 可以从一个简单的例子直观感受等价性

  • 考虑线性版本的梯度蒙特卡洛算法，假设回报值$G$是在幕结束时得到的单一收益回报值，且没有折扣存在。

  • 则有

    • \[\mathbf w_{t+1}\overset.=\mathbf w_t+\alpha[G-\mathbf w_t^\mathrm T\mathbf x_t]\mathbf x_t\]

  • 可以直接在幕结尾处高效精确重构相同的整体蒙特卡洛更新序列

    • \[\begin{align} \mathbf w_T=&\mathbf w_{T-1}+\alpha(G-\mathbf w_{T-1}^\mathrm T\mathbf x_{T-1})\mathbf x_{T-1}\\ =&\mathbf w_{T-1}-\alpha\mathbf x_{T-1}\mathbf x_{T-1}^\mathrm T\mathbf w_{T-1}+\alpha G\mathbf x_{T-1}\\ =&(\mathbf I-\alpha\mathbf x_{T-1}\mathbf x_{T-1}^\mathrm T)\mathbf w_{T-1}+\alpha G\mathbf x_{T-1}\\ =&\mathbf F_{T-1}\mathbf w_{T-1}+\alpha G\mathbf x_{T-1} \end{align}\]

  • 其中，$\mathbf F_t\overset.=\mathbf I-\alpha\mathbf x_t\mathbf x_t^\mathrm T$是遗忘矩阵（或衰减矩阵），递归下去则有

    • \[\begin{align} \mathbf w_T=&\mathbf F_{T-1}(\mathbf F_{T-2}\mathbf w_{T-2}+\alpha G\mathbf x_{T-2})+\alpha G\mathbf x_{T-1}\\ =&\underset{\mathbf a_{T-1}}{\underbrace{\mathbf F_{T-1}\mathbf F_{T-2}\cdots\mathbf F_0\mathbf w_0}}+\alpha G\underset{\mathbf z_{T-1}}{\underbrace{\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{align}\]

    • 其中$\mathbf a_{T-1}$和$\mathbf z_{T-1}$是在$T-1$时刻两个辅助记忆向量的值，$\mathbf z_t$实际上就是荷兰迹

      • \[\begin{align} \mathbf z_t\overset.=&\sum_{k=0}^t\mathbf F_t\mathbf F_{t-1}\cdots\mathbf F_{k+1}\mathbf x_k\\ =&\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\sum_{k=0}^{t-1}\mathbf F_{t-1}\cdots\mathbf F_{k+1}\mathbf x_k+\mathbf x_t\\ =&\mathbf F_t\mathbf z_{t-1}+\mathbf x_t\\ =&(\mathbf I-\alpha\mathbf x_t\mathbf x_t^\mathrm T)\mathbf z_{t-1}+\mathbf x_t\\ =&\mathbf z_{t-1}-\alpha\mathbf z_{t-1}^\mathrm T\mathbf x_t\mathbf x_t+\mathbf x_t\\ =&\mathbf z_{t-1}+(1-\alpha\mathbf z_{t-1}^\mathrm T\mathbf x_t)\mathbf x_t \end{align}\]
      • 这就是$\gamma\lambda=1$情况下的荷兰迹

  • 可以看到通过上面的推导最后能实现每一步$O(d)$的复杂度进行增量式更新

• Sarsa($\lambda$)

• 变量$\lambda$和$\gamma$

  • 可令$\lambda:\mathcal S\times\mathcal A\rightarrow[0,1]$是状态和动作到单位区间的函数映射，则有$\lambda_t\overset.=\lambda(S_t,A_t)$

  • 类似地，$\gamma:\mathcal S\rightarrow[0,1]$是状态到单位区间的函数映射，有$\gamma_t\overset.=\gamma(S_t)$

  • 则有

    • \[\begin{align} G_t\overset.=&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}+\cdots\\ =&\sum_{k=t}^\infty R_{k+1}\prod_{i=t+1}^k\gamma_i \end{align}\]

    • 要求$\prod_{k=t}^\infty\gamma_k=0$

    • 根据这样的定义，终止状态就是一个$\gamma(s)=0$的状态，且会转移到一个初始状态

    • “状态相关的终止”是分幕式和带折扣的持续性任务的深层统一（非折扣持续性任务还需要特殊处理）

  • 新的基于状态的$\lambda-$回报值可以被递归地写为

    • \[G_t^{\lambda s}\overset.=R_{t+1}+\gamma_{t+1}\Big((1-\lambda_{t+1})\hat v(S_{t+1},\mathbf w_t)+\lambda_{t+1}G_{t+1}^{\lambda s}\Big)\]

  • 基于动作的$\lambda-$回报值有两种形式

    • Sarsa形式

    • \[G_t^{\lambda a}\overset.=R_{t+1}+\gamma_{t+1}\Big((1-\lambda_{t+1})\hat q(S_{t+1},A_{t+1},\mathbf w_t)+\lambda_{t+1} G_{t+1}^{\lambda a}\Big)\]

    • 期望Sarsa形式

    • \[G_t^{\lambda a}\overset.=R_{t+1}+\gamma_{t+1}\Big((1-\lambda_{t+1})\overline V_t(S_{t+1})+\lambda_{t+1}G_{t+1}^{\lambda a}\Big)\\ \overline V_t(s)\overset.=\sum_a\pi(a\vert s)\hat q(s,a,\mathbf w_t)\]

• 带有控制变量的离轨策略资格迹

  • 直接考虑带有控制变量的每次决策型重要度采样的自举法推广

    • \[G_t^{\lambda s}\overset.=\rho_t\Big(R_{t+1}+\gamma_{t+1}\big((1-\lambda_{t+1})\hat v(S_{t+1},\mathbf w_t)+\lambda_{t+1}G_{t+1}^{\lambda s}\big)\Big)+(1-\rho_t)\hat v(S_t,\mathbf w_t)\]

    • 其中，$\rho_t=\frac{\pi(A_t\vert S_t)}{b(A_t\vert S_t)}$是普通的单步重要度采样率

    • \[\delta_t^s=R_{t+1}+\gamma_{t+1}\hat v(S_{t+1},\mathbf w_t)-\hat v(S_t,\mathbf w_t)\\ G_t^{\lambda s}\approx\hat v(S_t,\mathbf w_t)+\rho_t\sum_{k=t}^\infty\delta_k^s\prod_{i=t+1}^k\gamma_i\lambda_i\rho_i\]
    • 如果近似价值函数不变，则上式中的近似值将变为精确值

  • 上述形式的$\lambda-$回报可以使用前向视图更新

    • \[\begin{align} \mathbf w_{t+1}=&\mathbf w_t+\alpha(G_t^{\lambda s}-\hat v(S_t,\mathbf w_t))\nabla\hat v(S_t,\mathbf w_t)\\ \approx&\mathbf w_t+\alpha\rho_t\Big(\sum_{k=t}^\infty\delta_k^s\prod_{i=t+1}^k\gamma_i\lambda_i\rho_i\Big)\nabla\hat v(S_t,\mathbf w_t) \end{align}\]

  • 则有

    • \[\begin{align} \sum_{t=1}^\infty(\mathbf w_{t+1}-\mathbf w_t)\approx&\sum_{t=1}^\infty\alpha\rho_t\Big(\sum_{k=t}^\infty\delta_k^s\prod_{i=t+1}^k\gamma_i\lambda_i\rho_i\Big)\nabla\hat v(S_t,\mathbf w_t)\\ =&\sum_{k=1}^\infty\sum_{t=1}^k\alpha\rho_t\delta_k^s\nabla\hat v(S_t,\mathbf w_t)\prod_{i=t+1}^k\gamma_i\lambda_i\rho_i\\ =&\sum_{k=1}^\infty\alpha\delta_k^s\sum_{t=1}^k\rho_t\nabla\hat v(S_t,\mathbf w_t)\prod_{i=t+1}^k\gamma_i\lambda_i\rho_i\\ \end{align}\]

    • 可以设置资格迹

    • \[\begin{align} \mathbf z_t=&\sum_{t=1}^k\rho_t\nabla\hat v(S_t,\mathbf w_t)\prod_{i=t+1}^k\gamma_i\lambda_i\rho_i\\ =&\sum_{t=1}^{k-1}\rho_t\nabla\hat v(S_t,\mathbf w_t)\prod_{i=t+1}^k\gamma_i\lambda_i\rho_i+\rho_k\nabla\hat v(S_k,\mathbf w_k)\\ =&\gamma_k\lambda_k\rho_k\underset{\mathbf z_{k-1}}{\underbrace{\sum_{t=1}^{k-1}\rho_t\nabla\hat v(S_t,\mathbf w_t)\prod_{i=t+1}^{k-1}\gamma_i\lambda_i\rho_i}}+\rho_k\nabla\hat v(S_k,\mathbf w_k)\\ =&\rho_k(\gamma_k\lambda_k\mathbf z_{k-1}+\nabla\hat v(S_k,\mathbf w_k)) \end{align}\]
    • 则得到状态值的一般化积累迹更新

  • 类似地对于动作价值函数方法有

    • \[\begin{align} G_t^{\lambda a}\overset.=&R_{t+1}+\gamma_{t+1}\Big(\overline V_t(S_{t+1})+\lambda_{t+1}\rho_{t+1}[G_{t+1}^{\lambda a}-\hat q(S_{t+1},A_{t+1},\mathbf w_t)]\Big)\\ \approx&\hat q(S_t,A_t,\mathbf w_t)+\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}\overline V(S_{t+1})-\hat q(S_t,A_t,\mathbf w_t)\\ \mathbf z_t\overset.=&\gamma_t\lambda_t\rho_t\mathbf z_{t-1}+\nabla\hat q(S_t,A_t,\mathbf w_t) \end{align}\]

• 从Watkins的Q($\lambda$)到树回溯TB($\lambda$)

• \[\begin{align} G_t^{\lambda a}=&R_{t+1}+\gamma_{t+1}\Big((1-\lambda_{t+1})\overline V_t(S_{t+1})+\lambda_{t+1}\Big[\sum_{a\neq A_{t+1}}\pi(a\vert S_{t+1})\hat q(S_{t+1},a,\mathbf w_{t})+\pi(A_{t+1}\vert S_{t+1})G_{t+1}^{\lambda a}\Big]\Big)\\ \approx&\hat q(S_t,A_t,\mathbf w_t)+\sum_{k=t}^\infty\delta_k^a\prod_{i=t+1}^k\gamma_i\lambda_i\pi(A_i\vert S_i)\\ \mathbf z_t\overset.=&\gamma_t\lambda_t\pi(A_t\vert S_t)\mathbf z_{t-1}+\nabla\hat q(S_t,A_t,\mathbf w_t) \end{align}\]

• ==采用资格迹保障离轨策略方法的稳定性(To be read)==

• 总结

  • 在数据稀缺并且不能被重复处理的情况下使用资格迹通常是有意义的，许多在线应用就是这种情况。
  • 另一方面，在离线应用中可以很容易地生成数据，例如从廉价的模拟中生成数据，那么通常不使用资格迹。使用资格迹带来的学习的加速通常抵不上它们的计算成本

Chap 13. 策略梯度方法

前面的方法都是基于价值函数的方法，本章讨论直接学习参数化的策略的方法

在时刻$t$、状态$s$和参数$\mathbf \theta$下选择动作$a$的概率记为$\pi(a\vert s,\mathbf \theta)=\Pr{A_t=a\vert S_t=s,\mathbf \theta_t=\mathbf \theta}$

参数学习方法都基于某种性能度量$J(\mathbf \theta)$的梯度 \(\mathbf \theta_{t+1}=\mathbf \theta_t+\alpha\widehat{\nabla J(\mathbf\theta_t)}\) 其中$\widehat{\nabla J(\mathbf\theta_t)}$是一个随机估计，所有符合这个框架的方法都称为策略梯度方法

同时学习策略和价值函数的方法一般称为行动器-评判器方法，其中，“行动器“指学习到的策略，“评判器”指学习到的价值函数

• 策略近似及其优势

  • 一般要求策略永远不会变成确定的，即$\pi(a\vert s,\mathbf \theta)\in(0,1),\ \forall s,a,\mathbf\theta$

  • 如果动作空间是离散的并且不是特别大，可以对(状态-动作)二元组估计一个参数化的数值偏好$h(s,a,\mathbf \theta)\in\mathbb R$，比如可以设置

    • \[h(s,a,\mathbf\theta)=\mathbf\theta^\mathrm T\mathbf x(s,a)\\ \pi(a\vert s,\mathbf \theta)\overset.=\frac{e^{h(s,a,\mathbf\theta)}}{\sum_be^{h(s,b,\mathbf\theta)}}\]
    • 第二个公式形式的策略参数化称为动作偏好值的柔性最大化

• 策略梯度定理

  • 本节考虑分幕式情况，将性能指标定义为幕初始状态的价值，假设每幕都从某个（非随机的）状态$s_0$开始

    • \[J(\mathbf\theta)\overset.= v_{\pi_{\mathbf \theta}}(s_0)\]
    • 其中，$v_{\pi_{\mathbf\theta}}$是在策略$\pi_{\mathbf\theta}$下的真实价值函数，策略由参数$\mathbf\theta$决定

  • 策略梯度定理提供了一个性能指标相对于策略参数的解析表达式，其中没有涉及对状态分布的求导。对于分幕式：

    • \[\nabla J(\mathbf\theta)\propto \sum_s\mu(s)\sum_aq_\pi(s,a)\nabla\pi(a\vert s,\mathbf\theta)\]
    • 上式中正比的比例常量是幕的平均长度，持续性情况下，常量为1（即相等），这里的分布$\mu$是策略$\pi$下的同轨策略分布

  • ==策略梯度定理证明（分幕式）：==

• REINFORCE:蒙特卡洛策略梯度

  • 策略梯度定理的右边是将目标策略$\pi$下每个状态出现的频率作为加权系数的求和项，如果按策略$\pi$执行，则状态将按照这个比例出现

    • \[\begin{align} \nabla J(\mathbf\theta)\propto& \sum_s\mu(s)\sum_aq_\pi(s,a)\nabla\pi(a\vert s,\mathbf\theta)\\ =&\mathbb E_\pi\Big[\sum_aq_\pi(S_t,a)\nabla\pi(a\vert S_t,\mathbf\theta)\Big] \end{align}\]

  • 则有

    • \[\mathbf\theta_{t+1}\overset.=\mathbf\theta_t+\alpha\sum_a\hat q(S_t,a,\mathbf w)\nabla\pi(a\vert S_t,\mathbf\theta)\]
    • 这里的$\hat q$是由学习得到的$q_\pi$的近似。这个算法被称为全部动作算法

  • 类似地，引入$A_t$

    • \[\begin{align} \nabla J(\mathbf\theta)=&\mathbb E_\pi\Big[\sum_a\pi(a\vert S_t,\mathbf\theta)q_\pi(S_t,a)\frac{\nabla \pi(a\vert S_t,\mathbf\theta)}{\pi(a\vert S_t,\mathbf\theta)}\Big]\\ =&\mathbb E_\pi\Big[q_\pi(S_t,A_t)\frac{\nabla \pi(A_t\vert S_t,\mathbf\theta)}{\pi(A_t\vert S_t,\mathbf\theta)}\Big]\\ =&\mathbb E_\pi\Big[G_t\frac{\nabla \pi(A_t\vert S_t,\mathbf\theta)}{\pi(A_t\vert S_t,\mathbf\theta)}\Big] \end{align}\]

  • 则有

    • \[\mathbf\theta_{t+1}\overset.=\mathbf\theta_t+\alpha G_t\frac{\nabla \pi(A_t\vert S_t,\mathbf\theta_t)}{\pi(A_t\vert S_t,\mathbf\theta_t)}\]
    • 该算法称为REINFORCE

• 带有基线的REINFORCE

  • 将策略梯度定理进行推广，在其中加入一个与动作价值函数进行对比的基线$b(s)$

    • \[\nabla J(\mathbf\theta)\propto\sum_s\mu(s)\sum_a\Big(q_\pi(s,a)-b(s)\Big)\nabla\pi(a\vert s,\mathbf\theta)\]

    • 基线可以是任意函数，甚至是一个随机变量，只要不随动作$a$变化，上式仍然成立，因为

    • \[\sum_ab(s)\nabla\pi(a\vert s,\mathbf\theta)=b(s)\nabla\sum_a\pi(a\vert s,\mathbf\theta)=b(s)\nabla1=0\]

  • 则有

    • \[\mathbf\theta_{t+1}\overset.=\mathbf\theta_t+\alpha\Big(G_t-b(S_t)\Big)\frac{\nabla \pi(A_t\vert S_t,\mathbf\theta_t)}{\pi(A_t\vert S_t,\mathbf\theta_t)}\]

  • 状态价值函数$\hat v(S_t,\mathbf w)$就是一个比较自然想到的基线（加入基线是为了降低方差，比如使用状态价值函数则$G_t$变为$\delta_t=G_t-\hat v_t$）

• “行动器-评判器”方法

  • 带基线的REINFORCE虽然同时学习了策略函数和价值函数，但是价值函数没有用作“评判器”作用

  • 也就是只有采用自举操作：用后继各个状态的价值估计来更新当前某个状态的价值估计值时，才体现了“评判器”的作用，这样才会出现依赖于函数逼近质量的偏差和渐进性收敛

  • 单步“行动器-评判器”方法使用单步回报来替代REINFORCE算法的整个回报

    • \[\begin{align} \mathbf\theta_{t+1}\overset.=&\mathbf\theta_t+\alpha\Big(G_{t:t+1}-\hat v(S_t,\mathbf w)\Big)\frac{\nabla \pi(A_t\vert S_t,\mathbf\theta_t)}{\pi(A_t\vert S_t,\mathbf\theta_t)}\\ =&\mathbf\theta_t+\alpha\Big(R_{t+1}+\gamma\hat v(S_{t+1},\mathbf w)-\hat v(S_t,\mathbf w)\Big)\frac{\nabla \pi(A_t\vert S_t,\mathbf\theta_t)}{\pi(A_t\vert S_t,\mathbf\theta_t)}\\ =&\mathbf\theta_t+\alpha\delta_t\frac{\nabla \pi(A_t\vert S_t,\mathbf\theta_t)}{\pi(A_t\vert S_t,\mathbf\theta_t)} \end{align}\]

    • 对于状态价值函数则很自然地采用半梯度TD(0)来学习

    • 注意这是一个完全在线的、增量式的算法

  • 很自然地推广到n-步方法、再到$\lambda-$回报算法，只需要把式中的单步回报响应地替换为$G_{t:t+n}$或$G_t^\lambda$即可

• 持续性问题的策略梯度

  • 根据每个时刻上的平均收益来定义性能：

    • \[\begin{align} J(\mathbf\theta)\overset.=r(\pi)\overset.=&\lim_{h\rightarrow\infty}\frac{1}{h}\sum_{t=1}^h\mathbb E[R_t\vert S_0,A_{0:t-1}\sim\pi]\\ =&\lim_{t\rightarrow\infty}\mathbb E[R_t\vert S_0,A_{0:t-1}\sim\pi]\\ =&\sum_s\mu(s)\sum_a\pi(a\vert s)\sum_{s',r}p(s',r\vert s,a)r \end{align}\]
    • 其中$\mu$是策略$\pi$下的稳定状态分布，$\mu(s)\overset.=\lim_{t\rightarrow\infty}\Pr{S_t=s\vert A_{0:t}\sim\pi}$，并假设它一定存在并独立于$S_0$

  • 使用差分回报定义价值函数

    • \[v_\pi(s)\overset.=\mathbb E_\pi[G_t\vert S_t=s]\\ q_\pi(s,a)\overset.=\mathbb E_\pi[G_t\vert S_t=s,A_t=a]\\ G_t\overset.=R_{t+1}-r(\pi)+R_{t+2}-r(\pi)+\cdots\]

  • ==策略梯度定理证明（持续性）：==

• 针对连续动作的策略参数化方法

  • 动作空间连续时，学习概率分布的统计量，例如动作集可能是一个实数集，可以根据正态分布来选择动作

    • \[p(x)\overset.=\frac{1}{\sigma\sqrt{2\pi}}\exp\Big(-\frac{(x-\mu)^2}{2\sigma^2}\Big)\]

  • 可以将策略定义为关于实数型的标量动作的正态概率密度，其中均值和标准差由状态的参数化函数近似给出

    • \[\pi(a\vert s,\mathbf\theta)\overset.=\frac{1}{\sigma(s,\mathbf\theta)\sqrt{2\pi}}\exp\Big(-\frac{(a-\mu(s,\mathbf\theta))^2}{2\sigma(s,\mathbf\theta)^2}\Big)\]

    • 均值可用线性函数逼近，标准差可用线性函数的指数形式逼近（必须为正数）

    • \[\mu(s,\mathbf\theta)\overset.=\mathbf\theta_\mu^\mathrm T\mathbf x_\mu(s)\\ \sigma(s,\mathbf\theta)\overset.=\exp\Big(\mathbf\theta_\sigma^\mathrm T\mathbf x_\sigma(s)\Big)\]

• Previous
  《强化学习》学习笔记（一）