RLG

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

Posted on 2022-10-01 by Yihua Jiang & Linyu Li in Reinforcement Learning 

本章采用函数逼近方法处理离轨策略。相较于前面的同轨策略的学习，离轨策略学习进行函数逼近的扩展是不同且更难的。
离轨策略学习：目标策略 $\pi$,行动策略b

挑战

  • 表格型情况： 需要处理更新目标-即采样的样本价值与目标策略的样本价值不一致 解决方案：重要度采样，但会带来大方差
  • 函数逼近情况： 需要处理更新的分布-即更新价值函数的时候需要按照一定的顺序，最好就是根据同轨策略下采集的轨迹顺序更新策略，否则可能会不收敛。

解决方案：

  • 再次使用重要度采样，使得更新后的分布转为同轨策略的分布。
  • 寻找一种不依赖于任何特殊分布就能稳定的真实梯度方法。

11.1 半梯度方法

本节讨论了重要度采样在离轨策略中的推广。换句话就是将之前的表格型算法中的离轨方法转换为半梯度形式。这些方法只对表格型的情况才保证稳定且渐进无偏。

在函数逼近中，逼近目标如公式：
$\overline{VE}(w) := \sum_{s} \mu(s)[V_{\pi}(s)-\upsilon(s,w)]^2$
需要在上式的基础上增加重要度采样率：
$\rho_t\doteq\rho_{t:t}=\frac{\pi(A_t|S_t)}{b(A_t|S_t)}$
具体到基于函数逼近的TD(0)方法中（分幕带折扣），状态价值函数的更新公式：
$\boldsymbol{w}_{t+1}:=\boldsymbol{w}_{t}+\alpha\left[R_{t+1}+\gamma\hat v(S_{t+1},\mathbf w_t)-\hat v(S_t,\mathbf w_t)\right] \nabla\hat v(S_t,\mathbf w_t)$
增加了重要度采样率之后：
$\boldsymbol{w}_{t+1}:=\boldsymbol{w}_{t}+\alpha \rho_t\left[R_{t+1}+\gamma\hat v(S_{t+1},\mathbf w_t)-\hat v(S_t,\mathbf w_t)\right] \nabla\hat v(S_t,\mathbf w_t)$
令：

$$\begin{aligned} \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{aligned}$$


则可得到：
$\mathbf w_{t+1}\overset.=\mathbf w_t+\alpha\rho_t\delta_t\nabla\hat v(S_t,\mathbf w_t)$

半梯度期望Sarsa

单步动作价值函数算法

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

$$\begin{aligned} \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{aligned}$$


当前未使用重要度采样，原因是单步期望Sarsa方法的下一步动作与目标策略相关，而与行为策略无关。

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{aligned} 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{aligned}$$

练习


7.9：
$V_{t+n}\left(S_{t}\right) \doteq V_{t+n-1}\left(S_{t}\right)+\alpha \rho_{t : t+n-1}\left[G_{t : t+n}-V_{t+n-1}\left(S_{t}\right)\right], \quad 0 \leq t$
$\begin{aligned} \mathrm{w}_{t+n} & \doteq \mathrm{w}_{t+n-1}+\alpha \rho_{t: t+n-1}\left[G_{t: t+n}-\hat{v}\left(S_t, \mathrm{w}_{t+n-1}\right)\right] \nabla \hat{v}\left(S_t, \mathrm{w}_{t+n-1}\right) \\ G_{t: t+n} & \doteq \sum_{k=1}^n \gamma^{k-1} R_{t+k}+\gamma^n \hat{v}\left(S_{t+n}, \mathrm{w}_{t+n-1}\right) \quad \mid(\text { episodic }) \\ G_{t: t+n} & \doteq \sum_{k=1}^n\left[R_{t+k}-\bar{R}_{t+k-1}\right]+\hat{v}\left(S_{t+n}, \mathrm{w}_{t+n-1}\right) \quad \text { (continuous) } \end{aligned}$

7.11:
$Q_{t+n}\left(S_{t}, A_{t}\right) \doteq Q_{t+n-1}\left(S_{t}, A_{t}\right)+\alpha \rho_{t+1 : t+n}\left[G_{t : t+n}-Q_{t+n-1}\left(S_{t}, A_{t}\right)\right]$
7.17

$$\begin{split}\begin{aligned} G_{t : h} \doteq R_{t+1} &+\gamma\left(\sigma_{t+1} \rho_{t+1}+\left(1-\sigma_{t+1}\right) \pi\left(A_{t+1} | S_{t+1}\right)\right)\left(G_{t+1 : h}-Q_{h-1}\left(S_{t+1}, A_{t+1}\right)\right) \\ &+\gamma \overline{V}_{h-1}\left(S_{t+1}\right) \end{aligned}\end{split}$$


$\begin{aligned} \mathrm{w}_{t+n} & \doteq \mathrm{w}_{t+n-1}+\alpha \rho_{t: t+n-1}\left[G_{t: t+n}-\hat{q}\left(S_t,A_t, \mathrm{w}_{t+n-1}\right)\right] \nabla \hat{q}\left(S_t, A_t,\mathrm{w}_{t+n-1}\right) \\ G_{t: h} & \doteq R_{t+1}+\gamma\left(\sigma_{t+1} \rho_{t+1}+\left(1-\sigma_{t+1}\right) \pi\left(A_{t+1} \mid S_{t+1}\right)\right)\left(G_{t+1: h}-\hat{q}\left(S_{t+1}, A_{t+1}, \mathrm{w}_{h-1}\right)\right) \\ &+\gamma \bar{V}_{h-1}\left(S_{t+1}\right) \quad(\text { episodic }) \\ G_{t: h} & \doteq R_{t+1}-\bar{R}_t+\left(\sigma_{t+1} \rho_{t+1}+\left(1-\sigma_{t+1}\right) \pi\left(A_{t+1} \mid S_{t+1}\right)\right)\left(G_{t+1: h}-\hat{q}\left(S_{t+1}, A_{t+1}, \mathrm{w}_{h-1}\right)\right) \\ &+\bar{V}_{h-1}\left(S_{t+1}\right) \quad \text { (continuous) } \quad \text { with } \bar{V}_t(s) \doteq \sum_a \pi(a \mid s) \hat{q}\left(s, a, w_t\right) \end{aligned}$

11.2 发散的例子

1. 简单反例


有两个状态，其估计价值函数形式为w和2w，其中参数向量w仅仅包含一个独立分量w。转移概率为1。
初始化 $w=10，\gamma = 1，\alpha=0.1$

1 2
td-error = 10 td-error = 11
w1 = 11 w1 = 12.1
w2 = 22 w2 = 24.2

具体分析：
两个状态之间转移的TD误差：
$\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)=0+\gamma 2 w_{t}-w_{t}=(2 \gamma-1) w_{t}$
离轨策略半梯度的TD(0)更新：
$w_{t+1}=w_{t}+\alpha \rho_{t} \delta_{t} \nabla \hat{v}\left(S_{t}, w_{t}\right)=w_{t}+\alpha \cdot 1 \cdot(2 \gamma-1) w_{t} \cdot 1=(1+\alpha(2 \gamma-1)) w_{t}$
因为从第一个状态出发只有一个动作可以选，此时重要度采样率为1.
因为从第一个状态出发只有一个动作可以选，此时重要度采样率为1.显然当这个常数大于1系统就是不稳定的，w将会变为正无穷或负无穷。
该例子的关键在于一个转移重复发生，但w没有在其他的转移上更新。这在离轨策略训练的情况下是可能发生的，因为行动策略可能选择那些目标策略不会选的其他转移所对应的动作。而每当有一个从w状态转移到2w状态的转移时，w会被增大。而之后也一定会有一个从2w状态出发的转移，此时将会减小w，除非能够达到一个比2w更高的状态。因此，当前的每个状态都是通过创建一个更高的期望来支持前一个状态。

这种行为在同轨策略的情况下，可以保留对未来收益的承诺，系统也会受到制约。但是离轨策略的情况下，可以做出承诺,但在采取一个目标策略永远不会做出的动作之后便会忘记并原谅. 行为策略选择了目标策略不会选择的动作,这种情况下$\rho_t=0$,使得行为策略承诺未来有更高的收益,但是目标策略选择无视,后续更高价值不会被更新到.

2. Baird反例

  • 7个状态,两个动作
  • 行动策略按照其设置,可知下一个状态的分布是均匀的
  • 目标策略则总是选择实线动作
  • 所有转移的收益都为0,折扣率为0.99

    所有状态估计值可以通过权重向量$\mathbf{w} \in \mathbb{R}^{8}$线性表示,如$2w_1 + w_8 \to x(1) = (2,0,0,0,0,0,0,1)^T$ 并且所有转移收益为0,对于每个状态的真实价值函数$v_{\pi}(s)=0$,此时只要$\mathbf{w}=\mathbf{0}$即可实现准确近似. 因此整个任务从设置上来看是比较适合于线性函数近似的.

具体效果
初始化设置$\mathbf{w}=(1,1,1,1,1,1,10,1)^{\top},\alpha=0.01$,分别用半梯度TD(0)和半梯度DP方法得到的结果
具体的采用DP半梯度更新公式:
$\mathbf{w}_{k+1} \doteq \mathbf{w}_{k}+\frac{\alpha}{|\mathcal{S}|} \sum_{s}\left(\mathbb{E}_{\pi}\left[R_{t+1}+\gamma \hat{v}\left(S_{t+1}, \mathbf{w}_{k}\right) | S_{t}=s\right]-\hat{v}\left(s, \mathbf{w}_{k}\right)\right) \nabla \hat{v}\left(s, \mathbf{w}_{k}\right)$
没有随机性与异步性但系统依旧不稳定.

Tsitsiklis和Van Roy的反例

  • 两个状态,收益都为0
  • 最小化估计值与单步回报的偏差:

$$ \begin{split}\begin{aligned} w_{k+1} &=\underset{w \in \mathbb{R}}{\arg\min} \sum_{s \in \mathcal{S}}\left(\hat{v}(s, w)-\mathbb{E}_{\pi}\left[R_{t+1}+\gamma \hat{v}\left(S_{t+1}, w_{k}\right) | S_{t}=s\right]\right)^{2} \\ &=\underset{w \in \mathbb{R}}{\arg\min}\left(w-\gamma 2 w_{k}\right)^{2}+\left(2 w-(1-\varepsilon) \gamma 2 w_{k}\right)^{2} \\ &=\frac{6-4 \varepsilon}{5} \gamma w_{k} & \text{(11.10)} \end{aligned}\end{split} $$


当 $\gamma>\frac{5}{6-4 \varepsilon}$和$w_{0} \neq 0$ 时序列 $\lbrace w_{k} \rbrace$ 发散.

练习


11.3 致命三要素

以上例子表明了基于函数近似的离轨策略是很容易发散的。只要使用的方法同时满足下面三个基本要素，那么一定会有不稳定的危险：

  1. 函数逼近

    线性函数逼近和人工神经网络

  2. 自举法

    动态规划和TD方法

  3. 离轨策略训练

    行为策略与目标策略

这种不稳定的风险并不是由控制或者广义策略迭代造成的。在比控制更简单的预测问题中，只要同时包含这三个要素，不稳定性也会出现，而这些情况更难以分析。不稳定风险也不是由于学习或者环境的不确定性造成的，因为它在环境全部已知的规划算法（动态规划）中也会出现。

如果致命三要素中只有两个是满足的，那么可以避免不稳定性。按照重要性来说：函数逼近 > 自举法 > 异轨策略训练。

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

  • 假设状态空间$\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维空间的投影.
  • 由于需要注意投影时不同维度的权重可能不同,可以利用分布$\mu$结合以下范数定义价值函数之间的距离

$\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_w$对状态价值函数进行近似.我们把三个 V(s) 看成三维空间中的一个点，这三个价值可以取不同的值，因此它们构成一个三维空间。同理，近似函数的两个参数可以构成一个二维的空间。这个二维空间显然是三维空间的一个子空间。
  • 对于三维空间中的某一点 x，在子空间中距离该点最近的点 x′ 被称为 x 在子空间中的投影。那么，从某个近似参数 w 开始，对$v_w$进行一次贝尔曼算子的计算得到$B_{\pi}v_w$ 就会重新得到一个三维空间的点。随后对该点进行投影就能得到 $\mathbf \Pi B_{\pi}v_w$ 这个点存在于子空间中。
  • 贝尔曼误差定义为:

价值函数$v_\pi$的贝尔曼方程:
$v_{\pi}(s)=\sum_{a} \pi(a | s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma v_{\pi}\left(s^{\prime}\right)\right], \quad \text { 对所有 } s \in \mathcal{S}$
用近似价值函数代替价值函数,并进行差值计算可实现对两者之间距离的度量
$\begin{split}\begin{aligned} \overline{\delta}_{\mathbf{w}}(s) & \doteq\left(\sum_{a} \pi(a | s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma v_{\mathbf{w}}\left(s^{\prime}\right)\right]\right)-v_{\mathbf{w}}(s) & \text{(11.17)} \\ &=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma v_{\mathbf{w}}\left(S_{t+1}\right)-v_{\mathbf{w}}\left(S_{t}\right) | S_{t}=s, A_{t} \sim \pi\right] & \text{(11.18)} \end{aligned}\end{split}$
显然从以上式子可以了解:
贝尔曼误差是TD误差的期望
均方贝尔曼误差:$\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$
贝尔曼算子
$B_{\pi}:\mathbb{R}^{|\mathcal{S}|}\rightarrow\mathbb{R}^{|\mathcal{S}|},\left(B_{\pi} v\right)(s) \doteq \sum_{a} \pi(a | s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma v\left(s^{\prime}\right)\right]$
因此以上贝尔曼误差向量又能写成$\overline{\delta}_{\mathbf{w}}=B_{\pi} v_{\mathbf{w}}-v_{\mathbf{w}}$
通常不可能将均方贝尔曼误差减小到0($v_w = v_\pi$),由于函数近似的更新如图示例下半部分

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

  • 带折扣的单步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}$
如果在上式中简单地在所有期望中使用采样值，那么该算法就几乎规约到朴素残差梯度算法
为了得到两个期望乘积的无偏样本，需要下一个状态的两个独立样本，但通常在交互过程中只能得到一个（即无法回溯重新采样），可以一个用期望值，一个用采样值。
但不幸的是它收敛得很慢。此外在某些环境下它依然没法收敛到正确的值，它并不是一个很好的目标。最后一点是贝尔曼误差是不可学习的。

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

可学习：可用多项式级的样本学会，而不是指数级的样本。
用贝尔曼误差目标（$\overline{\mathrm{BE}}$）不可学习，因为$\overline{\mathrm{BE}}$不可不能从可观测的数据中学到。
两个马尔可夫收益过程（MRP）：每个状态只有一个动作
image.png image.png
左侧与右侧的MRP过程同样产生0和2的流，且概率都为0.5。如果$\gamma=0$，从左到右的三个状态真实值分别是1，0，2。假设w=1，左边的$\overline{\mathrm{VE}}$为0，右边的$\overline{\mathrm{VE}}$为1。
$\overline{\mathrm{VE}}(\mathbf{w}) \doteq \sum_{s \in \mathcal{S}} \mu(s)\left[v_{\pi}(s)-\hat{v}(s, \mathbf{w})\right]^{2}$
$\overline{\mathrm{VE}}$在两个MRP中不同，但所产生的数据序列相同，因此$\overline{\mathrm{VE}}$不可学习。$\overline{\mathrm{VE}}$不是这个数据分布唯一确定的函数。
以上两个MRP的最优解$w=1$相同，但$\overline{\mathrm{VE}}$不同。对于所有有着相同数据分布以及相同最优参数向量的 MDP 而言都是广泛成立。$\overline{\mathrm{VE}}$仍然是一个有用的目标。$\overline{\mathrm{VE}}$是不可学习的，但是优化它的参数是可学习的。
均方回报误差$\overline{\mathrm{RE}}$,一个总是可观察的误差是每个时刻的估计价值与这个时刻之后的实际回报的误差。是一个在$\mu$分布下误差的平方期望。写为：
$\begin{aligned} \overline{\mathrm{RE}} & \doteq \mathbb{E}\left[\left(G_{t}-\hat{v}\left(S_{t}, \boldsymbol{w}\right)\right)^{2}\right] \\ &=\overline{\mathrm{VE}}(\boldsymbol{w})+\mathbb{E}\left[\left(G_{t}-v_{\pi}\left(S_{t}\right)\right)^{2}\right]+2 \mathbb{E}\left[\left(G_{t}-v_{\pi}\left(S_{t}\right)\right)\left[v_{\pi}\left(S_{t}\right)-\hat{v}\left(S_{t}, \boldsymbol{w}\right)\right]\right] \end{aligned}$
$\begin{aligned} \mathbb{E}\left[\left(G_{t}-v_{\pi}\left(S_{t}\right)\right)\left[v_{\pi}\left(S_{t}\right)-\hat{v}\left(S_{t}, \boldsymbol{w}\right)\right]\right] &=\mathbb{E}_{s \sim \mu}\left\{\mathbb{E}\left[\left(G_{t}-v_{\pi}(s)\right)\left[v_{\pi}(s)-\hat{v}(s, \boldsymbol{w})\right]\right] \mid s\right\} \\ &=0 \end{aligned}$
$\begin{aligned} \overline{\mathrm{RE}}(\mathbf{w}) &=\mathbb{E}\left[\left(G_{t}-\hat{v}\left(S_{t}, \mathbf{w}\right)\right)^{2}\right] \\ &=\overline{\mathrm{VE}}(\mathbf{w})+\mathbb{E}\left[\left(G_{t}-v_{\pi}\left(S_{t}\right)\right)^{2}\right] \end{aligned}$
image.png

蒙特卡洛目标：两个不同的 MDP 可以产生相同的数据分布，但是会具有不同的$\overline{\mathrm{VE}}$。这证明 $\overline{\mathrm{VE}}$目标不能够 由数据决定，因此是不可学习的。然而，所有这样的$\overline{\mathrm{VE}}$还具有相同的最优参数向量$w^*$。除此之外，这个相同的$w^*$可以从另一个目标中确定：$\overline{\mathrm{RE}}$，可以从数据分布中唯一确定。
自举法目标：两个不同MDP 可以产生相同的数据分布，但是也会产生不同的$\overline{\mathrm{BE}}$，而且最小化时会有不同的参数向量；这些不可以从数据分布中学习到。$\overline{\mathrm{PBE}}$和$\overline{\mathrm{TDE}}$目标以及它们(不同的)最小值可以直接从数据中确定，因此是可以学习的。

11.7 梯度TD方法

不能使用$\overline{\mathrm{BE}}$，可以考虑以投影贝尔曼误差$\overline{\mathrm{PBE}}$作为目标，首先以矩阵形式扩展重写目标函数：
$\begin{aligned} \overline{\operatorname{PBE}}(\mathbf{w}) &=\left|\Pi \bar{\delta}_{\mathbf{w}}\right|_{\mu}^{2} \\ &=\left(\Pi \bar{\delta}_{\mathbf{w}}\right)^{\top} \mathbf{D} \Pi \bar{\delta}_{\mathbf{w}} \\ &=\bar{\delta}_{\mathbf{w}}^{\top} \Pi^{\top} \mathbf{D} \Pi \bar{\delta}_{\mathbf{w}} \\ &=\bar{\delta}_{\mathbf{w}}^{\top} \mathbf{D} \mathbf{X}\left(\mathbf{X}^{\top} \mathbf{D} \mathbf{X}\right)^{-1} \mathbf{X}^{\top} \mathbf{D} \bar{\delta}_{\mathbf{w}} \end{aligned}$
$=\left(\mathbf{X}^{\top} \mathbf{D} \bar{\delta}_{\mathbf{w}}\right)^{\top}\left(\mathbf{X}^{\top} \mathbf{D} \mathbf{X}\right)^{-1}\left(\mathbf{X}^{\top} \mathbf{D} \bar{\delta}_{\mathbf{w}}\right)$
$\nabla \overline{\mathrm{PBE}}(\mathbf{w})=2 \nabla\left[\mathbf{X}^{\top} \mathbf{D} \bar{\delta}_{\mathbf{w}}\right]^{\top}\left(\mathbf{X}^{\top} \mathbf{D} \mathbf{X}\right)^{-1}\left(\mathbf{X}^{\top} \mathbf{D} \bar{\delta}_{\mathbf{w}}\right)$
为了将其转化为SGD方法，需要在每个时间点上采样，并把采样值作为期望值，所有的三个
因子都可以写成这个分布的某个期望的形式，例如最后一个因子可以写成：
$\mathbf{X}^{\top} \mathbf{D} \bar{\delta}_{\mathbf{w}}=\sum_{s} \mu(s) \mathbf{x}(s) \bar{\delta}_{\mathbf{w}}(s)=\mathbb{E}\left[\rho_{t} \delta_{t} \mathbf{x}_{t}\right]$
第一个因子是这个更新梯度的转置：
$\begin{aligned} \nabla \mathbb{E}\left[\mathbf{x}_{t} \rho_{t} \delta_{t}\right]^{\top} &=\mathbb{E}\left[\rho_{t} \nabla \delta_{t}^{\top} \mathbf{x}_{t}^{\top}\right] \\ &=\mathbb{E}\left[\rho_{t} \nabla\left(R_{t+1}+\gamma \mathbf{w}^{\top} \mathbf{x}_{t+1}-\mathbf{w}^{\top} \mathbf{x}_{t}\right)^{\top} \mathbf{x}_{t}^{\top}\right] \\ &=\mathbb{E}\left[\rho_{t}\left(\gamma \mathbf{x}_{t+1}-\mathbf{x}_{t}\right) \mathbf{x}_{t}^{\top}\right] \end{aligned}$
中间的因子是特征向量的外积矩阵的期望的逆。
$\mathbf{X}^{\top} \mathbf{D} \mathbf{X}=\sum_{s} \mu(s) \mathbf{x}_{s} \mathbf{x}_{s}^{\top}=\mathbb{E}\left[\mathbf{x}_{t} \mathbf{x}_{t}^{\top}\right]$
我们把$\overline{\mathrm{PBE}}$三个梯度的三个因子转成这些期望的形式得到：
$\nabla \overline{\mathrm{PBE}}(\mathbf{w})=2 \mathbb{E}\left[\rho_{t}\left(\gamma \mathbf{x}_{t+1}-\mathbf{x}_{t}\right) \mathbf{x}_{t}^{\top}\right] \mathbb{E}\left[\mathbf{x}_{t} \mathbf{x}_{t}^{\top}\right]^{-1} \mathbb{E}\left[\rho_{t} \delta_{t} \mathbf{x}_{t}\right]$
其中第一个和第三个因子不是独立的，都依赖于下一时刻的特征向量，可以进行采样得到，这样就可以朴素残差梯度方法一样得到一个有偏的估计。另一个想法是分别估计这三个期望，然后合并起来得到一个梯度的无偏估计，但复杂度所需空间太高。
但分别存储一些估计，然后与样本进行合并是可取的，梯度TD估计并存储后两个因子，这些因子是d*d维的一个矩阵和一个d维向量，因此乘积只是一个d维向量，把这个学到的向量记为v：
$\mathbf{v} \approx \mathbb{E}\left[\mathbf{x}_{t} \mathbf{x}_{t}^{\top}\right]^{-1} \mathbb{E}\left[\rho_{t} \delta_{t} \mathbf{x}_{t}\right]$
这是试图从特征近似的最小二乘解，可以使用最小均方（LMS）方法，最小化$(\mathbf{v}^{\top} \mathbf{x}_{t}-\rho_{t} \delta_{t})^{2}$：
$\mathbf{v}_{t+1} \doteq \mathbf{v}_{t}+\beta \rho_{t}\left(\delta_{t}-\mathbf{v}_{t}^{\top} \mathbf{x}_{t}\right) \mathbf{x}_{t}$
那么针对$\overline{\mathrm{PBE}}$梯度，使用v来估计和存储后两个因子，再对第一个因子的期望进行采样，即可得到：
$\begin{split}\begin{aligned} \mathbf{w}_{t+1} &=\mathbf{w}_{t}-\frac{1}{2} \alpha \nabla \overline{\mathrm{PBE}}\left(\mathbf{w}_{t}\right) & \text{(一般的SGD规则)}\\ &=\mathbf{w}_{t}-\frac{1}{2} \alpha 2 \mathbb{E}\left[\rho_{t}\left(\gamma \mathbf{x}_{t+1}-\mathbf{x}_{t}\right) \mathbf{x}_{t}^{\top}\right] \mathbb{E}\left[\mathbf{x}_{t} \mathbf{x}_{t}^{\top}\right]^{-1} \mathbb{E}\left[\rho_{t} \delta_{t} \mathbf{x}_{t}\right] & \text{(由(11.27))}\\ &=\mathbf{w}_{t}+\frac{1}{2} \alpha 2 \mathbb{E}\left[\rho_{t}\left(\mathbf{x}_{t}-\gamma \mathbf{x}_{t+1}\right) \mathbf{x}_{t}^{\top}\right] \mathbb{E}\left[\mathbf{x}_{t} \mathbf{x}_{t}^{\top}\right]^{-1} \mathbb{E}\left[\rho_{t} \delta_{t} \mathbf{x}_{t}\right] & \text{(11.29)}\\ & \approx \mathbf{w}_{t}+\alpha \mathbb{E}\left[\rho_{t}\left(\mathbf{x}_{t}-\gamma \mathbf{x}_{t+1}\right) \mathbf{x}_{t}^{\top}\right] \mathbf{V}_{t} & \text{(基于(11.28))}\\ & \approx \mathbf{w}_{t}+\alpha \rho_{t}\left(\mathbf{x}_{t}-\gamma \mathbf{x}_{t+1}\right) \mathbf{x}_{t}^{\top} \mathbf{v}_{t} & \text{(采样)} \end{aligned}\end{split}$
这个算法被称为GTD2。
再替换v之前可以多做几步分析：
$\begin{split}\begin{aligned} \mathbf{w}_{t+1} &=\mathbf{w}_{t}+\alpha \mathbb{E}\left[\rho_{t}\left(\mathbf{x}_{t}-\gamma \mathbf{x}_{t+1}\right) \mathbf{x}_{t}^{\top}\right] \mathbb{E}\left[\mathbf{x}_{t} \mathbf{x}_{t}^{\top}\right]^{-1} \mathbb{E}\left[\rho_{t} \delta_{t} \mathbf{x}_{t}\right] \\ &=\mathbf{w}_{t}+\alpha\left(\mathbb{E}\left[\rho_{t} \mathbf{x}_{t} \mathbf{x}_{t}^{\top}\right]-\gamma \mathbb{E}\left[\rho_{t} \mathbf{x}_{t+1} \mathbf{x}_{t}^{\top}\right]\right) \mathbb{E}\left[\mathbf{x}_{t} \mathbf{x}_{t}^{\top}\right]^{-1} \mathbb{E}\left[\rho_{t} \delta_{t} \mathbf{x}_{t}\right] \\ &=\mathbf{w}_{t}+\alpha\left(\mathbb{E}\left[\mathbf{x}_{t} \mathbf{x}_{t}^{\top}\right]-\gamma \mathbb{E}\left[\rho_{t} \mathbf{x}_{t+1} \mathbf{x}_{t}^{\top}\right]\right) \mathbb{E}\left[\mathbf{x}_{t} \mathbf{x}_{t}^{\top}\right]^{-1} \mathbb{E}\left[\rho_{t} \delta_{t} \mathbf{x}_{t}\right] \\ &=\mathbf{w}_{t}+\alpha\left(\mathbb{E}\left[\mathbf{x}_{t} \rho_{t} \delta_{t}\right]-\gamma \mathbb{E}\left[\rho_{t} \mathbf{x}_{t+1} \mathbf{x}_{t}^{\top}\right] \mathbb{E}\left[\mathbf{x}_{t} \mathbf{x}_{t}^{\top}\right]^{-1} \mathbb{E}\left[\rho_{t} \delta_{t} \mathbf{x}_{t}\right]\right) \\ &\approx \mathbf{w}_{t}+\alpha\left(\mathbb{E}\left[\mathbf{x}_{t} \rho_{t} \delta_{t}\right]-\gamma \mathbb{E}\left[\rho_{t} \mathbf{x}_{t+1} \mathbf{x}_{t}^{\top}\right] \mathbf{v}_{t}\right) & \text{(基于(11.28))} \\ &\approx \mathbf{w}_{t}+\alpha \rho_{t}\left(\delta_{t} \mathbf{x}_{t}-\gamma \mathbf{x}_{t+1} \mathbf{x}_{t}^{\top} \mathbf{v}_{t}\right) & \text{(采样)} \end{aligned}\end{split}$
该方法又被称为带梯度修正的TD(0)（TDC）或者GTD(0)
GTD2和TDC都包含两个学习过程，主要学习w，次要学习v，主要学习的逻辑依赖于次要学习结束或近似结束，而次要学习不受主要学习的影响，将这种不对称的依赖称为梯级。梯级通常假设次要学习进行得更快，因此总是处于它的渐近值，足够精准得辅助主要学习，这些方法的收敛性都需要显示地做这个假设。

11.8 强调TD方法

在离线学习中，使用重要度采样重新分配了状态转移的权重，使得它们变得适合学习目标策略，但是状态分布仍然是行动策略产生的，这就有了一个不匹配之处，一个自然的想法就是以某种方式重新分配状态的权重，强调一部分而淡化另外一部分，目的是将更新分布变为同轨策略分布。
对应的单步强调TD算法的定义如下：
$\begin{split}\begin{array}{l} {\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)} \\ {\mathbf{w}_{t+1}=\mathbf{w}_{t}+\alpha M_{t} \rho_{t} \delta_{t} \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right)} \\ {M_{t}=\gamma \rho_{t-1} M_{t-1}+I_{t}} \end{array}\end{split}$
其中I为兴趣值，M为强调值。

11.9 方差减小

off-policy本质上会具有更大的方差，只有当目标和行动策略相关时，即访问相似的状态并且采取类似的动作时，才能在off-policy训练过程中取得显著进步。
基于重要度采样的off-policy问题中，控制方差很重要，重要度采样通常包括策略比率的乘积，这些比率的期望总是1，但是其方差可能很大，但是在SGD方法中，这些比率会乘上学习步长，因此高方差就意味着步长之间的差异会很大。
引入动量、自适应设置分离步长、重要性权重感知、树回溯算法、允许目标策略部分由行动策略决定等方法可以减少off-policy带来的方差问题。

代码

CounterExample.ipynb
exe11-3.ipynb

参考文献

https://zhuanlan.zhihu.com/p/352594241
https://zhuanlan.zhihu.com/p/408973709
https://github.com/vojtamolda/reinforcement-learning-an-introduction
https://lcalem.github.io/blog/2019/02/02/sutton-chap11
https://rl.qiwihui.com/zh_CN/latest/partII/index.html
http://chongjg.com/2021/11/29/%E5%BC%BA%E5%8C%96%E5%AD%A6%E4%B9%A0-%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0-%E4%BA%8C/