本
文
摘
要
这一节考察利用SGD随机梯度下降来最小化投影贝尔曼误差PBE。作为真正的SGD方法，梯度TD方法即使在离策略和非线性近似的条件下也具有优良的收敛特性。
在线性近似下，我们总是会得到一个精确解，即TD不动点（张文：9.8 最小二乘TD算法（LSTD）），此时的PBE为0.这里的LSTD方法类似一种解析的计算方式，计算复杂度是 O(d2)O(d^2) ， dd 是状态特征向量的维度。如果用SGD方法，复杂度是 O(d)O(d) 。梯度TD方法和它们类似。
PBE的梯度的推导
既然是随机梯度，那么就要对PBE求导（PBE的定义参考：张文：11.4 线性值函数几何学），为此我们先重写一下PBE的损失函数的形式，如下：
PBE¯(w)=‖Πδ¯w‖μ2=(Πδ¯w)⊤DΠδ¯w=δ¯w⊤Π⊤DΠδ¯w(11.25)=δ¯w⊤DX(X⊤DX)−1X⊤Dδ¯w\begin{align} \overline{\operatorname{PBE}}(\mathbf{w}) &=\left\|\Pi \overline{\delta}_{\mathbf{w}}\right\|_{\mu}^{2} \\ &=\left(\Pi \overline{\delta}_{\mathbf{w}}\right)^{\top} \mathbf{D} \Pi \overline{\delta}_{\mathbf{w}} \\ &=\overline{\delta}_{\mathbf{w}}^{\top} \Pi^{\top} \mathbf{D} \Pi \overline{\delta}_{\mathbf{w}} \\ &=\overline{\delta}_{\mathbf{w}}^{\top} \mathbf{D} \mathbf{X}\left(\mathbf{X}^{\top} \mathbf{D} \mathbf{X}\right)^{-1} \mathbf{X}^{\top} \mathbf{D} \overline{\delta}_{\mathbf{w}} \tag{11.25} \end{align}
D\mathbf{D} 是 |S|×|S||\mathcal{S}|\times |\mathcal{S}| 大小的对角矩阵，其对角元素分别是每个状态的在策略分布概率 μ(s)\mu(s) 。对于线性近似，贝尔曼投影算子 Π\Pi 也是线性的，可以用一个矩阵表示为： Π≐X(X⊤DX)−1X⊤D\Pi \doteq \mathbf{X}\left(\mathbf{X}^{\top} \mathbf{D} \mathbf{X}\right)^{-1} \mathbf{X}^{\top} \mathbf{D} ， X|S|×d\mathbf{X} ^{ |\mathcal{S}| \times d} 是特征向量矩阵。每一行是一个特征向量 x(s)⊤\mathbf{x}(s)^ \top 。带入得：
Π⊤DΠ=D⊤X[(X⊤DX)−1]⊤X⊤DX(X⊤DX)−1X⊤D=DX(X⊤DX)−1X⊤D\Pi^\top \mathbf{D} \Pi = \mathbf{D}^\top \mathbf{X} \left[ (\mathbf{X^\top D X)} ^{-1} \right]^\top \color{red}{\mathbf{X^\top D X} (\mathbf{X^\top D X)}^{-1}} \mathbf{X^\top D} =\mathbf{DX (X^\top D X)^{-1}X^\top D}
注意推导过程中也利用了D是对称阵的性质。我们将上面的结论的带入就得到了（11.25）。在重写一下11.25有：
(11.26)PBE¯(w)=(X⊤Dδ¯w)⊤(X⊤DX)−1(X⊤Dδ¯w)\overline{PBE}(\mathbf{w})=\left(\mathbf{X}^{\top} \mathbf{D} \overline{\delta}_{\mathbf{w}}\right)^{\top}\left(\mathbf{X}^{\top} \mathbf{D} \mathbf{X}\right)^{-1}\left(\mathbf{X}^{\top} \mathbf{D} \overline{\delta}_{\mathbf{w}}\right) \tag{11.26}
对它求导得：
(11.26-1)∇PBE¯(w)=2∇[X⊤Dδ¯w]⊤(X⊤DX)−1(X⊤Dδ¯w)\nabla \overline{\mathrm{PBE}}(\mathbf{w})=2 \nabla\left[\mathbf{X}^{\top} \mathbf{D} \overline{\delta}_{\mathbf{w}}\right]^{\top}\left(\mathbf{X}^{\top} \mathbf{D} \mathbf{X}\right)^{-1}\left(\mathbf{X}^{\top} \mathbf{D} \overline{\delta}_{\mathbf{w}}\right) \tag{11.26-1}
为了使用SGD方法，我们需要把上面的表达式写成期望的形式，对应的SGD就是采样来近似这样一个期望。为此，我们用 μ\mu 表示行为策略下状态的分布。上面的几项都可以写成期望的形式，比如：
X⊤Dδ¯w=[x(s1)x(s2)…x(s|S|)][μs1μs2…μs|S|]⊤[δs1δs2…δ|S|]⊤=[μ1x1μ2x2…μ|S|x|S|][δ1δ2…δ|S|]⊤=∑sμ(s)x(s)δ¯w(s)=E[ρtδtxt]\mathbf{X}^{\top} \mathbf{D} \overline{\delta}_{\mathbf{w}} =\left[\mathbf{x}(s_1) \; \mathbf{x}(s_2) \dots \mathbf{x}(s_{|\mathcal{S}|}) \right] \left [\mu_{s_1} \; \mu_{s_2} \dots \mu_{s_{|\mathcal{S}|}} \right]^\top \left[ \delta_{s_1} \; \delta_{s_2} \dots \delta_{|\mathcal{S}|} \right] ^\top \\ =\left[ \mu_1 \mathbf{x}_1 \; \mu_2 \mathbf{x}_2 \dots \mu_{|\mathcal{S}|}\mathbf{x}_{|\mathcal{S}|} \right] \left[ \delta_1 \; \delta_2 \dots \delta_{|\mathcal{S}|} \right] ^\top \\ =\sum_{s} \mu(s) \mathbf{x}(s) \overline{\delta}_{\mathbf{w}}(s)=\mathbb{E}\left[\rho_{t} \delta_{t} \mathbf{x}_{t}\right]
这个结果刚好是离策略下半梯度TD(0)更新公式的期望。梯度11.26-1中第一项等于：
∇E[ρtδtxt]⊤=E[ρt∇δt⊤xt⊤]=E[ρt∇(Rt+1+γw⊤xt+1−w⊤xt)⊤xt⊤]=E[ρt(γxt+1−xt)xt⊤]\begin{aligned} \nabla \mathbb{E}\left[\rho_{t} \delta_{t} \mathbf{x}_{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}
梯度中间项等于特征向量外积的期望的逆，即：
X⊤DX=∑sμ(s)xsxs⊤=E[xtxt⊤]\mathbf{X}^{\top} \mathbf{D X}=\sum_{s} \mu(s) \mathbf{x}_{s} \mathbf{x}_{s}^{\top}=\mathbb{E}\left[\mathbf{x}_{t} \mathbf{x}_{t}^{\top}\right]
把这些结论带入到11.26-1得到：
(11.27)∇PBE¯(w)=2E[ρt(γxt+1−xt)xt⊤]E[xtxt⊤]−1E[ρtδtxt]\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] \tag{11.27}
有了这个期望的形式，但是我们依然无法高效的通过采样来获得梯度的更新公式。三个期望乘积中第一个和第三个是相关的，都依赖下一个状态 xt+1\mathbf{x}_{t+1} （第三个期望中的 δt\delta_t 依赖下一个状态），所以我们不能简单的对每个期望采样，然后相乘。这样会得到一个有偏的估计，这个问题和原始残差梯度算法中的问题一样（不知道为什么不直接采样出一批对应的 xt\mathbf{x}_t 和 xt+1\mathbf{x}_{t+1} ，然后用这一批数据分别来估计这三个期望）。
另一个思路是单独的估计三个期望，然后结合它们来产生无偏的梯度估计。这样行得通，但是需要大量的计算。尤其是前两项外积运算的结果都是矩阵，而且还需要计算矩阵的逆。我们可以改进一下，先估计三个期望中两个期望的乘积，然后采样第三个期望。比如我们可以先计算存储后两个期望的乘积然后采样第一个期望表达式。但是这个复杂度依然是 O(d2)O(d^2) .
梯度TD方法
梯度TD方法使用的思想和上面一样。我们先估计11.27中后两项期望的乘积，因为这个两项的维度分别是 d×dd\times d 和 dd 维的向量，所以乘积也是一个向量，类似于权重 w\mathbf{w} 自身的维度。我们把这两项的乘积表示为向量 v\mathbf{v} ：
(11.28)v≈E[xtxt⊤]−1E[ρtδtxt]\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] \tag{11.28}
这个形式和线性最小二乘的结果类似。我们类比一下，就会发现v\mathbf{v} 相当于是线性问题 v⊤xt=ρtδt\mathbf{v}^{\top} \mathbf{x}_{t} = \rho_{t} \delta_{t} 的解。对于这个问题我们可以很容易的利用如下的规则来更新得到 v\mathbf{v} ：
vt+1≐vt+βρt(δt−vt⊤xt)xt\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}
这段话是什么意思呢？简单来说，就是本来要计算v\mathbf{v}，我们需要估计外积矩阵的期望，还要求逆。对比一下我们发现这个v\mathbf{v}其实是一个LS问题的解。那么我们就可以用SGD来迭代的更新v\mathbf{v}，从而间接的计算出公式（11.28）中的v\mathbf{v}。这个求解的空间法则度仅仅是 O(d)O(d) 。
结合（11.27）和（11.28），利用SGD就能得到参数向量 wt\mathbf{w}_t 的更新规则：
规则基于采样(SGD 规则)wt+1=wt−12α∇PBE¯(wt)(from (11.27))=wt−12α2E[ρt(γxt+1−xt)xt⊤]E[xtxt⊤]−1E[ρtδtxt](11.29)=wt+αE[ρt(xt−γxt+1)xt⊤]E[xtxt⊤]−1E[ρtδtxt](基于11.28)≈wt+αE[ρt(xt−γxt+1)xt⊤]vt(采样)≈wt+αρt(xt−γxt+1)xt⊤vt\begin{align} \mathbf{w}_{t+1} &=\mathbf{w}_{t}-\frac{1}{2} \alpha \nabla \overline{\operatorname{PBE}}\left(\mathbf{w}_{t}\right) \tag{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] \tag{from (11.27)}\\ &=\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] \tag{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} \tag{基于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} \tag{采样} \end{align}
这个算法叫做GTD2。
对上面11.29式稍微分析整理一下，可以得到下面的结果：
基于采样wt+1=wt+αE[ρt(xt−γxt+1)xt⊤]E[xtxt⊤]−1E[ρtδtxt]=wt+α(E[ρtxtxt⊤]−γE[ρtxt+1xt⊤])E[xtxt⊤]−1E[ρtδtxt]=wt+α(E[xtxt⊤]−γE[ρtxt+1xt⊤])E[xtxt⊤]−1E[ρtδtxt]=wt+α(E[xtρtδt]−γE[ρtxt+1xt⊤]E[xtxt⊤]−1E[ρtδtxt])(基于(11.28))≈wt+α(E[xtρtδt]−γE[ρtxt+1xt⊤]vt)(采样)≈wt+αρt(δtxt−γxt+1xt⊤vt)\begin{align} \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(\color{red}{\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) \color{red}{\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)} \tag{基于(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)} \tag{采样} \end{align}
基本上就是把第一个期望拆开了，然后有一项和后两项中（ v\mathbf{v} ）的 E[xtxt⊤]−1\mathbb{E}\left[ \mathbf{x_t x_t^\top} \right]^{-1} 抵消了。同样的，如果提前计算出了 xt⊤vt\mathbf{x_t^\top v_t} (是个标量）。那么这个算法的空间复杂度是 O(d)O(d) 的。这个算法我们叫做GTD(0)，或者叫做基于梯度纠正（gradient correction）的TD(0)算法(TDC)。
GTD2和TDC算法都包含了两个学习过程，一个是为了学习 v\mathbf{v} ，一个是为了学习我们的主参数 w\mathbf{w} 。学习 w\mathbf{w} 是我们的主要目的，也称为首要学习过程。相应 v\mathbf{v} 是次要的学习过程。学习 w\mathbf{w} 依赖于 v\mathbf{v} ，但是学习 v\mathbf{v} 并不依赖于 w\mathbf{w} ，这样的一种非对称依赖性称为级联（cascade）。在一个级联系统中，我们总是假设次要学习过程学习的足够快，以至于它总是能处在渐进值，并且足够精确来辅助首要学习过程。对于这类系统的收敛性证明叫做two-time-scale证明。
