## 1. uni-chain 的基本含义 **uni-chain**，也写作 **unichain**，通常译为： [ $$ \text{单链} $$ ] 或更准确地说： [ $$ \text{单常返类马尔可夫链} $$ ] 在有限状态 Markov chain 中，**unichain** 指： [ $$ \boxed{ \text{整个 Markov chain 只有一个 recurrent class，此外可以有若干 transient states。} } $$ ] 也就是：状态空间中最终会长期停留的“闭合常返区域”只有一个；其他状态即使存在，也只是暂态状态，访问有限次后最终会离开。一个常见教材讲义把 unichain 定义为：有限状态 Markov chain 包含一个单一 recurrent class，并且可能包含一些 transient states。([Department of Mathematics](https://math.uchicago.edu/~may/REU2013/REUPapers/Datta.pdf?utm_source=chatgpt.com "markov chains and markov decision theory")) --- ## 2. 先解释 recurrent class 和 transient state 要理解 uni-chain，必须先区分两类状态。 ### 2.1 recurrent state / recurrent class 若状态 ($i$) 一旦被访问，从 ($i$) 出发将来以概率 1 会再次回到 ($i$)，则 ($i$) 是 **recurrent state**。 一组状态 (C) 若满足： 1. 集合内状态彼此可达； 2. 一旦进入 (C)，不会离开 (C)； 则 (C) 是一个 **recurrent class**，也叫 closed recurrent class。 直观地说： # [ $$ \text{recurrent class} \text{长期吸住马尔可夫链的闭合区域} $$ ] 进入 recurrent class 后，链会一直在该类内部运动。 --- ### 2.2 transient state 若状态 ($i$) 只会被访问有限次，之后可能再也不会回来，则 ($i$) 是 **transient state**。 直观地说： # [ $$ \text{transient state} \text{过渡状态} $$ ] 它可能出现在初始阶段，但长期统计中会消失。 --- ## 3. uni-chain 的结构图式 uni-chain 的结构可以表示为： [ $$ \text{transient states} \longrightarrow \text{single recurrent class} $$ ] 例如： [ $$ {1,2} \longrightarrow {3,4,5} $$ ] 其中 ({1,2}) 是 transient states，({3,4,5}) 是唯一 recurrent class。进入 ({3,4,5}) 后，不再离开。 这就是 uni-chain： [ $$ \boxed{ \text{可以有多个暂态状态，但只能有一个长期闭合常返类。} } $$ ] --- ## 4. 不是 uni-chain 的情况：multi-chain 若一个 Markov chain 有两个或更多 recurrent classes，则不是 unichain，而是 **multichain**。 例如： [ $$ \{1,2\} \quad\text{和}\quad \{3,4\} $$ ] 都是 closed recurrent classes。若初始状态进入 ($\{1,2\}$)，则长期只在 ({1,2}) 内活动；若进入 ({3,4})，则长期只在 ({3,4}) 内活动。 这种情况下，长期分布依赖初始状态： [ $$ d^{(1)} \neq d^{(3)} $$ ] 因此不存在一个对所有初始状态都统一的长期访问分布。这正是 TD 理论中不希望出现的复杂情形。 --- ## 5. uni-chain 与 ergodic 的区别 原文说： > We assume that the Markov chain is ergodic and uni-chain. 这里同时使用了 **ergodic** 和 **uni-chain**，二者不是完全同义。 ### 5.1 uni-chain 关注 recurrent class 数量 uni-chain 要求： [ $$ \text{recurrent class 的数量}=1 $$ ] 但它不一定要求周期性消失。 例如唯一 recurrent class 可能是周期为 2 的： [ $$ 1\to2\to1\to2\to\cdots $$ ] 这仍然可以是 unichain，但不一定是 aperiodic。 --- ### 5.2 ergodic 关注长期分布是否良好收敛 通常在有限 Markov chain 中，ergodic 常要求链具有不可约性、非周期性，并存在唯一稳定分布；在很多教材语境中，一个 ergodic class 是 recurrent 且 aperiodic 的类。上述讲义也把 ergodic class 定义为既 recurrent 又 aperiodic 的状态类。([Department of Mathematics](https://math.uchicago.edu/~may/REU2013/REUPapers/Datta.pdf?utm_source=chatgpt.com "markov chains and markov decision theory")) 因此，若一个链是： [ $$ \text{uni-chain} + \text{唯一 recurrent class aperiodic} $$ ] 则长期状态分布通常会收敛到唯一稳定分布： [ $$ d_s=\lim_{t\to\infty}\Pr(s_t=s) $$ ] 这正是论文中使用的条件。 --- ## 6. 为什么论文需要 uni-chain？ 在前文中，固定策略 ($\pi$) 与 MDP 结合后，会诱导一个 Markov chain。MDP 与固定策略结合后变成 Markov chain，是 MDP 的标准性质：策略固定后，状态转移由该策略诱导的转移概率决定。([Wikipedia](https://en.wikipedia.org/wiki/Markov_decision_process?utm_source=chatgpt.com "Markov decision process")) 论文希望定义一个长期状态分布： [ $$ d_s=\lim_{t\to\infty}\Pr(s_t=s) $$ ] 并用它构造加权范数： [ $$ ||v||_D^2=v^\top Dv $$ ] 其中： [ $$ D=\operatorname{diag}(d_1,\dots,d_N) $$ ] 如果 Markov chain 有多个 recurrent classes，则长期分布可能依赖初始状态。这样 ($d$) 就不再唯一，后续 TD 收敛分析中的 ($D$)-加权投影、MSE、MSBE、MSPBE 都会变得不稳定或需要额外区分初始分布。 所以 uni-chain 假设的作用是： [ $$ \boxed{ \text{保证长期行为只有一个稳定的常返区域，从而长期状态分布 }d\text{ 是良定义的。} } $$ ] --- ## 7. ($P^\top d=d$) 与 uni-chain 的关系 在 on-policy 情形中，状态序列来自同一个 Markov chain 的自然演化。若该链具有良好的长期稳定分布 ($d$)，则有： [ $$ P^\top d=d $$ ] 这里 (P) 是行随机转移矩阵： [ $$ P_{ss'}=\Pr(s_{t+1}=s'|s_t=s) $$ ] 若当前状态分布是 (d)，则下一步状态分布为： [ $$ P^\top d $$ ] 平稳性要求： [ $$ P^\top d=d $$ ] uni-chain 加上适当 ergodicity 条件，保证这个 (d) 不会因为初始状态落入不同 recurrent class 而发生歧义。 --- ## 8. 在 MDP 中的 unichain assumption 在 MDP 文献中，“unichain MDP”通常指：对每个 stationary deterministic policy，诱导出来的 Markov chain 都是 unichain，即每个固定策略下最多只有一个 recurrent class，可能加上一些 transient states。相关 MDP 课程材料也区分了 weakly communicating、unichain、multichain 等条件，并指出 unichain/multichain 定义通常要求对所有策略成立。([CISTUP](https://cistup.iisc.ac.in/tarun/CE_273/Lecture_15.pdf?utm_source=chatgpt.com "CE 273 Markov Decision Processes")) 但在这篇 TD/GTD 论文的语境中，策略已经固定，作者说的是： [ $$ \text{the Markov chain is ergodic and uni-chain} $$ ] 也就是固定策略与 MDP 组合后得到的那条 Markov chain 满足 unichain/ergodic 条件，而不是在讨论所有可能策略下的 MDP 分类。 --- ## 9. 一个具体例子 设状态集合： [ $$ \mathcal S=\{1,2,3,4\} $$ ] 转移结构如下： [ $$ 1\to2,\quad 2\to3,\quad 3\leftrightarrow4 $$ ] 其中： [ {3,4} ] 是唯一 closed recurrent class。状态 (1,2) 一旦离开，就不会回来，因此是 transient states。 这个链是 unichain： [ $$ \text{transient states: }{1,2} $$ ] [ $$ \text{single recurrent class: }{3,4} $$ ] 长期来看，无论从 (1,2,3,4) 哪个状态开始，最终都会进入 ({3,4})，并在其中长期运动。 --- ## 10. 反例：不是 unichain 设状态集合： [ $$ \mathcal S=\{1,2,3,4\} $$ ] 转移结构如下： [ $$ 1\leftrightarrow2 $$ ] [ $$ 3\leftrightarrow4 $$ ] 且两组之间没有转移。 此时存在两个 recurrent classes： [ $$ C_1=\{1,2\} $$ ] [ $$ C_2=\{3,4\} $$ ] 如果初始状态在 ($C_1$)，长期分布只支持 ($C_1$)；如果初始状态在 ($C_2$)，长期分布只支持 ($C_2$)。因此该链不是 unichain，而是 multichain。 --- ## 11. 和 TD 学习的关系 TD 分析中经常需要期望更新： [ $$ \mathbb E[\delta\phi] $$ ] 在 on-policy 情形下，这个期望通常按长期状态分布 ($d$) 加权： # [ $$ \mathbb E[\delta\phi] = \sum_s d_s \phi_s \left[ R_s+\gamma\sum_{s'}P_{ss'}\theta^\top\phi_{s'} -\theta^\top\phi_s \right] $$ ] 矩阵形式为： $$ \mathbb E[\delta\phi] = \Phi^\top D(TV_\theta-V_\theta) $$ ] 其中： [ $$ D=\operatorname{diag}(d) $$ ] 如果没有唯一稳定的 ($d$)，则这个期望更新方向会依赖初始状态或不同 recurrent classes 的权重。uni-chain/ergodic 假设使得： [ $$ D $$ ] 可以被稳定定义，从而 TD fixed point、投影 Bellman 方程、MSPBE 等后续概念都能在同一个加权几何中讨论。 --- ## 12. 总结 **uni-chain** 的核心含义是： [ $$ \boxed{ \text{有限 Markov chain 中只有一个 recurrent class，此外可以有 transient states。} } $$ ] 在论文语境中，它的作用是保证固定策略诱导的 Markov chain 只有一个长期闭合区域，因此长期状态分布 ($d$) 不会因初始状态进入不同 recurrent class 而产生歧义。再配合 ergodic/aperiodic 条件，可以得到： [ $$ d_s=\lim_{t\to\infty}\Pr(s_t=s) $$ ] 以及： [ $$ P^\top d=d $$ ] 这正是传统 on-policy TD 收敛分析中所依赖的状态分布结构。 --- 而是先规定： [ $$ \text{有限状态 Markov chain} $$ ] [ $$ \text{固定策略下的状态价值函数} $$ ] [ $$ \text{线性函数近似 } V_\theta(s)=\theta^\top\phi_s $$ ] [ $$ \text{one-step TD update} $$ ] [ $$ \text{on-policy 与 off-policy 的采样分布差异} $$ ] 后续 GTD2/TDC 的核心问题是：普通 TD 更新 # [ $$ \theta_{k+1} \theta_k+\alpha_k\delta_k\phi_k $$ ] 在 on-policy 线性函数近似下通常有良好收敛性质，但在 off-policy 情形中，采样分布 ($d$) 与目标转移矩阵 ($P$) 脱钩后，普通 TD 可能发散。因此需要构造真正的梯度 TD 方法。论文前文也明确说，普通 TD、Sarsa、Q-learning 并不是真正的梯度下降方法，并且 off-policy 时无法保证收敛。 --- # 三、固定策略 + MDP 为什么变成 Markov chain？ 原始 MDP 包含： [ $$ (\mathcal S,\mathcal A,p,r,\gamma) $$ ] 若策略固定为： [ $$ \pi(a|s) $$ ] 则动作不再是外部优化变量，而是由策略随机产生。于是从状态 ($s$) 到状态 ($s'$) 的总体转移概率为： # [ $$ P^\pi_{ss'} = \sum_{a\in\mathcal A} \pi(a|s)p(s'|s,a) $$ ] 因为策略已经固定，状态序列： [ $$ s_0,s_1,s_2,\dots $$ ] 自身构成一个 Markov chain： # [ $$ \Pr(s_{t+1}=s'|s_t=s,s_{t-1},\dots) = P^\pi_{ss'} $$ ] 论文中为简化记号，把固定策略诱导的转移矩阵直接记为： [ $$ P $$ ] 所以这里研究的是 **policy evaluation**，不是 policy control。目标不是学习最优策略，而是学习给定策略的价值函数。 --- # 四、状态价值函数 ($V(s)$) 的含义 真实状态价值函数定义为： # [ $$ V(s) = \mathbb E \left[ \sum_{t=0}^{\infty} \gamma^t r_{t+1} \mid s_0=s \right] $$ ] 这表示：从状态 ($s$) 出发，之后一直按照固定策略行动，能够获得的期望折扣回报。 这里的随机性来自三部分： [ $$ \text{策略动作采样} $$ ] [ $$ \text{环境状态转移} $$ ] [ $$ \text{奖励随机性} $$ ] 由于策略已经固定，动作变量被边缘化，所以价值函数只写成状态函数： [ $$ V:\mathcal S\to\mathbb R $$ ] 而不是动作价值函数： [ $$ Q:\mathcal S\times\mathcal A\to\mathbb R $$ ] --- # 五、为什么需要线性函数近似？ 若状态数为 (N)，tabular value function 需要为每个状态单独存一个值： # [ $$ V = \begin{bmatrix} V(1)\\ V(2)\\ \vdots\\ V(N) \end{bmatrix} \in\mathbb R^N $$ ] 当 ($N$) 很大时，tabular 表示不可行。因此使用特征向量： [ $$ \phi_s\in\mathbb R^n $$ ] 来表示状态 ($s$)，并用参数向量： [ $$ \theta\in\mathbb R^n $$ ] 构造近似值函数： [ $$ V_\theta(s)=\theta^\top\phi_s $$ ] 若： [ $$ n\ll N $$ ] 则参数量远小于状态数。此时不同状态之间通过共享参数 (\theta) 发生泛化。 例如： [ $$ \phi_s= \begin{bmatrix} \text{是否靠近目标}\\ \text{是否处于危险区域}\\ \text{距离中心的归一化距离}\\ \vdots \end{bmatrix} $$ ] 则： [ $$ \theta_i $$ ] 表示第 ($i$) 个特征对价值的线性贡献。 --- # 六、矩阵形式：($V_\theta=\Phi\theta$) 将所有状态的特征向量堆叠成矩阵： # [ $$ \Phi = \begin{bmatrix} \phi_1^\top\\ \phi_2^\top\\ \vdots\\ \phi_N^\top \end{bmatrix} \in\mathbb R^{N\times n} $$ ] 则所有状态上的近似价值可以写为： # [ $$ V_\theta = \Phi\theta $$ ] 其中： # [ $$ V_\theta = \begin{bmatrix} V_\theta(1)\\ V_\theta(2)\\ \vdots\\ V_\theta(N) \end{bmatrix} \in\mathbb R^N $$ ] 线性函数近似能够表示的所有值函数构成一个线性子空间： # [ $$ \mathcal V = {\Phi\theta:\theta\in\mathbb R^n} = \operatorname{span}(\Phi) $$ ] 如果 ($n0 $$ ] 说明当前状态的估计偏低，需要提高： [ $$ V_\theta(s_k) $$ ] 若： [ $$ \delta_k<0 $$ ] 说明当前状态的估计偏高，需要降低： [ $$ V_\theta(s_k) $$ ] --- # 十、传统线性 TD 更新的含义 传统线性 TD 更新为： # [ $$ \theta_{k+1} = \theta_k+\alpha_k\delta_k\phi_k $$ ] 因为： # [ $$ \nabla_\theta V_\theta(s_k) = \nabla_\theta(\theta^\top\phi_k) = \phi_k $$ ] 所以更新方向： [ $$ \delta_k\phi_k $$ ] 表示沿着当前状态特征方向调整参数。 若某个特征 ($\phi_{k,i}$) 在状态 ($s_k$) 中很强，并且 ($\delta_k>0$)，则对应参数 ($\theta_i$) 会增大；若 ($\delta_k<0$)，则 ($\theta_i$) 会减小。 写成逐坐标形式： # [ $$ \theta_{k+1,i} = \theta_{k,i} + \alpha_k\delta_k\phi_{k,i} $$ ] 所以只有当前状态激活的特征会被明显更新。 --- # 十一、为什么说这是 semi-gradient？ 若把一步 TD target 写成： # [ $$ y_k = r_k+\gamma\theta_k^\top\phi'_k $$ ] 则普通 TD 看起来像在减小： [ $$ \frac12 \left( y_k-\theta^\top\phi_k \right)^2 $$ ] 但注意，target (y_k) 本身也含有 (\theta_k)。如果真正对： [ $$ \frac12 \left( r_k+\gamma\theta^\top\phi'_k-\theta^\top\phi_k \right)^2 $$ ] 求梯度，则有： # [ $$ \nabla_\theta \delta_k = \gamma\phi'_k-\phi_k $$ ] 所以真实梯度下降方向应包含： [ $$ \delta_k(\phi_k-\gamma\phi'_k) $$ ] 而普通 TD 使用的是： [ $$ \delta_k\phi_k $$ ] 它忽略了 bootstrap target 中： [ $$ \gamma\theta^\top\phi'_k $$ ] 对 ($\theta$) 的依赖。因此，普通 TD 是 **semi-gradient method**，不是完整梯度下降方法。 这也是整篇论文后续要解决的问题之一：传统 TD 速度快，但在 off-policy + function approximation 下不具备一般梯度方法那样稳健的收敛保证。 --- # 十二、on-policy 设置中的 ($d$) 与 ($P$) 在 on-policy 设置中，样本来自同一个马尔可夫链的自然演化： [ $$ s_0\to s_1\to s_2\to\cdots $$ ] 若链是 ergodic 且 uni-chain，则长期访问频率收敛到唯一稳定分布： # [ $$ d_s = \lim_{t\to\infty}\Pr(s_t=s) $$ ] 将 ($d$) 看作列向量： [ $$ d= \begin{bmatrix} d_1\\ d_2\\ \vdots\\ d_N \end{bmatrix} $$ ] 稳定分布满足： [ $$ P^\top d=d $$ ] 如果 ($P$) 是行随机矩阵，即： [ $$ P_{ss'}=\Pr(s_{t+1}=s'|s_t=s) $$ ] 那么： # [ $$ (P^\top d)_{s'} = \sum_s P_{ss'}d_s $$ ] 表示下一时刻落在 ($s'$) 的总概率。平稳性要求： # [ $$ d_{s'} = \sum_s d_sP_{ss'} $$ ] 即当前状态分布为 ($d$) 时，经过一次转移后仍然是 ($d$)。 原文强调，这种 ($d$) 与 ($P$) 的 linkage 对传统 TD 收敛性很关键。 --- # 十三、为什么 ($P^\top d=d$) 对 TD 收敛重要？ 传统 TD 的期望更新可以写成： [ $$ \mathbb E[\delta\phi] $$ ] 展开： # [ $$ \mathbb E[\delta\phi] = \sum_s d_s\phi_s \left[ R_s+\gamma\sum_{s'}P_{ss'}\theta^\top\phi_{s'} - \theta^\top\phi_s \right] $$ ] 矩阵形式为： # [ $$ \mathbb E[\delta\phi] = \Phi^\top D \left( R+\gamma P\Phi\theta-\Phi\theta \right) $$ ] 其中： [ $$ D=\operatorname{diag}(d_1,\dots,d_N) $$ ] 因此 TD 的期望动力学近似为： [ $$ \theta_{k+1} \approx \theta_k + \alpha \Phi^\top D \left( R+\gamma P\Phi\theta_k-\Phi\theta_k \right) $$ ] 写成线性形式： # [ $$ \mathbb E[\Delta\theta] = \alpha(b-A\theta) $$ ] 其中： [ $$ b=\Phi^\top DR $$ ] [ $$ A=\Phi^\top D(I-\gamma P)\Phi $$ ] on-policy 情况下，($D$) 是 ($P$) 的平稳分布对应的权重矩阵。这使得 projected Bellman operator 在 (D)-加权范数下具有良好性质，从而传统 TD 可以收敛到 projected Bellman fixed point。 而 off-policy 中，($D$) 和 ($P$) 可以不匹配，($A$) 可能失去正定性或稳定性，普通 TD 的期望更新就可能朝发散方向移动。 --- # 十四、off-policy 设置中的关键变化 原文考虑更一般的设置： [ $$ s_k\sim d $$ ] 其中 ($d$) 是任意分布，并且： [ $$ d \text{ may be unrelated to } P $$ ] 接着，根据当前状态 ($s_k$)，通过目标转移矩阵 ($P$) 生成： [ $$ s'_k $$ ] 并生成奖励： [ $$ r_k $$ ] 于是每个样本是独立三元组： [ $$ (s_k,s'_k,r_k) $$ ] 这里的关键不是“下一状态不服从 ($P$)”；下一状态仍然由 ($P$) 给出。关键是：**当前状态的采样分布 ($d$) 不一定是 ($P$) 的平稳分布**。 on-policy： [ $$ d \text{ 是 } P \text{ 的 stationary distribution} $$ ] off-policy： [ $$ d \text{ 可以与 } P \text{ 无关} $$ ] 这正是 TD 稳定性被破坏的根源。 --- # 十五、为什么这对应 off-policy learning？ 在策略评估中，目标策略 ($\pi$) 诱导转移矩阵： [ $$ P^\pi $$ ] 行为策略 ($b$) 产生数据，其状态访问分布可能是： [ $$ d^b $$ ] off-policy 学习希望用行为策略 ($b$) 的数据学习目标策略 ($\pi$) 的价值： [ $$ V^\pi $$ ] 此时通常有： [ $$ d^b \neq d^\pi $$ ] 也就是样本状态分布与目标策略对应的平稳分布不一致。 论文中的抽象设置： [ $$ s_k\sim d $$ ] [ $$ s'_k\sim P(\cdot|s_k) $$ ] 正是把这种 mismatch 抽象出来： [ $$ d \not\leftrightarrow P $$ ] 因此它对应 off-policy learning。原文也直接说明，任意 ($d$) 与 ($P$) 无关的设置对应 off-policy learning。 --- # 十六、为什么作者使用独立三元组 ($(s_k,s'_k,r_k)$)？ 传统在线 TD 的样本是相关的： [ $$ s_0,s_1,s_2,\dots $$ ] 因为相邻状态来自同一条马尔可夫链。 本文为理论分析使用一种更干净的采样模型：每一步的第一个状态独立地从 ($d$) 中采样： [ $$ s_k\overset{i.i.d.}{\sim} d $$ ] 然后生成： [ $$ s'_k,r_k $$ ] 这样得到独立三元组： [ $$ (s_k,s'_k,r_k) $$ ] 这种设置可以避免马尔可夫链时间相关性带来的技术复杂性，把问题集中到核心矛盾上： [ $$ \text{采样分布 } d \quad \text{与} \quad \text{目标转移矩阵 } P \quad \text{是否匹配} $$ ] 因此，本文不是在研究 trajectory correlation，而是在研究 off-policy distribution mismatch 对 TD 稳定性的影响。 --- # 十七、episodic 情形的脚注解释 原文脚注说，结果也适用于 episodic case，只要把： [ $$ d_s $$ ] 理解为状态 ($s$) 在所有时间步中出现的比例。 在 episodic task 中，轨迹形式是： [ $$ s_0,s_1,\dots,s_T $$ ] 回报为有限和： # [ $$ G_t = r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^{T-t-1}r_T $$ ] 由于 episode 终止，求和不必无限进行。 此时 ($P$) 的某些行和可以小于 1，因为可能有概率质量进入终止状态并消失。如果终止状态没有显式纳入状态集合，则非终止状态之间的转移矩阵是 substochastic matrix： [ $$ \sum_{s'}P_{ss'}\leq 1 $$ ] 并且 ($\gamma$) 可以等于 1，只要： [ $$ (\gamma P)^\infty=0 $$ ] 这表示随着时间推移，非终止状态中的概率质量最终消失。直观地说： [ $$ \text{episode 最终终止} $$ ] 所以即使不折扣，回报仍然有限。 --- # 十八、这段与后续 GTD/TDC 的关系 这段看似只是 notation，但实际上已经引出后文所有关键结构。 传统 TD 更新的期望是： [ $$ \mathbb E[\delta\phi] $$ ] TD fixed point 满足： [ $$ \mathbb E[\delta\phi]=0 $$ ] 即： # [ $$ \Phi^\top D \left( R+\gamma P\Phi\theta-\Phi\theta \right) = 0 $$ ] 等价于： [ $$ \Phi^\top D(TV_\theta-V_\theta)=0 $$ ] 这表示 Bellman error： [ $$ TV_\theta-V_\theta $$ ] 与特征空间正交。后文会进一步说明，TD 类算法通常收敛到 projected Bellman equation 的解： [ $$ V_\theta=\Pi TV_\theta $$ ] 而不是直接最小化 ordinary Bellman error： [ $$ ||V_\theta-TV_\theta||_D^2 $$ ] 论文后续也明确指出，TD、LSTD、GTD 等算法的 fixed point 是 composed projection 和 Bellman operator 的 fixed point，即： [ $$ V_\theta=\Pi TV_\theta $$ ] 并把 MSPBE 定义为： # [ $$ \operatorname{MSPBE}(\theta) = ||V_\theta-\Pi TV_\theta||_D^2 $$ ] 作为后续 GTD2/TDC 的目标函数。 所以本节的符号： [ $$ P,\ d,\ \Phi,\ \theta,\ \phi_k,\ \phi'_k,\ \delta_k $$ ] 会直接进入后续所有推导。 --- # 十九、最关键的机制总结 这段话可以压缩成如下逻辑： [ $$ \text{固定策略 + MDP} \Rightarrow \text{Markov chain} $$ ] # [ $$ \text{真实价值} = V(s)= \mathbb E \left[ \sum_{t=0}^{\infty} \gamma^t r_{t+1} \mid s_0=s \right] $$ ] # [ $$ \text{线性近似} = V_\theta(s)=\theta^\top\phi_s $$ ] # [ $$ \text{one-step TD error} = \delta_k = r_k+\gamma\theta_k^\top\phi'_k-\theta_k^\top\phi_k $$ ] # [ $$ \text{传统 TD 更新} = \theta_{k+1} = \theta_k+\alpha_k\delta_k\phi_k $$ ] 核心区别在于采样分布： [ $$ \text{on-policy: } P^\top d=d $$ ] [ $$ \text{off-policy: } d \text{ may be unrelated to } P $$ ] 普通 TD 在 on-policy 下依赖 ($d$) 与 ($P$) 的一致性；off-policy 下这种一致性消失，因此普通 TD 的更新方向可能不再稳定。GTD2/TDC 的目标就是在这种更一般的 ($d$) 与 ($P$) 脱钩情形下，构造仍然可靠收敛的线性复杂度 TD 方法。 --- 目标函数在这里为什么重要？ 的核心问题是： [ $$ \text{如果要把 TD 做成真正的梯度下降算法，应当下降哪个目标函数？} $$ ] 普通 TD 更新为： # [ $$ \theta_{k+1} = \theta_k+\alpha_k\delta_k\phi_k. $$ ] 它看起来像梯度更新，但并不是某个简单平方误差目标的完整梯度下降。因此，若要构造 **true stochastic gradient-descent TD algorithm**，必须先明确目标函数。 候选目标有四类： [ $$ \operatorname{MSE}(\theta) $$ ] [ $$ \operatorname{MSBE}(\theta) $$ ] [ $$ \operatorname{MSPBE}(\theta) $$ ] [ $$ \operatorname{NEU}(\theta) $$ ] 它们看起来相似，但优化意义完全不同。 --- # 三、MSE：最自然，但通常不可用 MSE 定义为： # [ $$ \operatorname{MSE}(\theta) = \sum_s d_s \bigl(V_\theta(s)-V(s)\bigr)^2. $$ ] 矩阵写法为： # [ $$ \operatorname{MSE}(\theta) = ||V_\theta-V||_D^2. $$ ] 其中： [ $$ D=\operatorname{diag}(d_1,d_2,\dots,d_N). $$ ] 它对应 ($D$)-加权内积： [ $$ \langle u,v\rangle_D=u^\top Dv, $$ ] 以及 ($D$)-加权范数： [ $$ ||v||_D^2=v^\top Dv. $$ ] 因此： # [ $$ ||V_\theta-V||_D^2 = \sum_s d_s(V_\theta(s)-V(s))^2. $$ ] 这里的 ($d_s$) 表示状态 ($s$) 的采样权重或长期出现频率。若某状态经常出现，则其误差更重要；若某状态几乎不出现，则其误差权重较小。 MSE 是最接近监督学习的目标：真实标签是 ($V(s)$)，预测值是 ($V_\theta(s)$)。问题是强化学习中通常不知道 ($V(s)$)。真实价值函数本身就是要学习的对象： # [ $$ V(s) = \mathbb E \left[ \sum_{t=0}^{\infty}\gamma^t r_{t+1} \mid s_0=s \right]. $$ ] 因此，MSE 在理论上自然，但不能直接用于增量式 TD 学习。 --- # 四、Bellman 方程与 Bellman 算子 真实价值函数满足 Bellman 方程： [ $$ V=R+\gamma PV. $$ ] 定义 Bellman 算子： [ $$ Tv=R+\gamma Pv. $$ ] 于是 Bellman 方程可写为： [ $$ V=TV. $$ ] 也就是说，真实价值函数是 Bellman 算子 ($T$) 的不动点： [ $$ V \text{ is a fixed point of }T. $$ ] 这给出一种替代思路：既然无法直接比较 ($V_\theta$) 和 ($V$)，可以检查 ($V_\theta$) 是否近似满足 Bellman 方程： [ $$ V_\theta\approx TV_\theta. $$ ] 由此得到 MSBE。 --- # 五、MSBE：直接衡量 Bellman 方程残差 MSBE 定义为： # [ $$ \operatorname{MSBE}(\theta) = ||V_\theta-TV_\theta||_D^2. $$ ] 其中： [ $$ V_\theta-TV_\theta $$ ] 称为 Bellman residual，或者 Bellman error。 展开： # [ $$ TV_\theta = R+\gamma PV_\theta. $$ ] 因此： # [ $$ V_\theta-TV_\theta = V_\theta-R-\gamma PV_\theta. $$ ] 若： [ $$ \operatorname{MSBE}(\theta)=0, $$ ] 则： [ $$ V_\theta=TV_\theta, $$ ] 说明 ($V_\theta$) 精确满足 Bellman 方程。若函数近似空间足够表达真实 ($V$)，那么这个条件意味着： [ $$ V_\theta=V. $$ ] 所以从表面上看，MSBE 是非常自然的目标。 但问题在于：在线性函数近似下，函数空间通常不是整个 ($\mathbb R^N$)。 --- # 六、函数近似空间与 Bellman 映射的不匹配 线性函数近似为： [ $$ V_\theta=\Phi\theta. $$ ] 所有可表示价值函数构成线性子空间： # [ $$ \mathcal V = {\Phi\theta:\theta\in\mathbb R^n} = \operatorname{span}(\Phi). $$ ] 如果状态数为 ($N$)，特征数为 ($n$)，且 ($n0, $$ ] 说明： [ $$ r+\gamma w_{s'}>w_s. $$ ] 普通 TD 会提高 ($w_s$)，使前驱状态接近 target。Residual-gradient 除了提高 (w_s)，还会降低 (w_{s'})，从另一边减少 residual。 如果： [ $$ \delta<0, $$ ] 普通 TD 会降低 (w_s)，Residual-gradient 还会提高 (w_{s'})。 因此 residual-gradient 会让前驱和后继“互相靠近”。Baird 的论文也指出，residual-gradient 使信息双向流动；相比 direct / semi-gradient 方法中信息从后继状态向前驱状态传播，residual-gradient 会让信息也沿“错误方向”流动，因此可能慢得多。([SciSpace](https://scispace.com/pdf/residual-algorithms-reinforcement-learning-with-function-150011hve2.pdf "Residual algorithms: reinforcement learning with function approximation")) --- ## 5. backwards bootstrapping 是什么？ **backwards bootstrapping** 指： [ $$ \boxed{ \text{一个状态的价值被其前驱状态反向影响，使它看起来像前驱状态，而不仅仅由后继回报决定。} } $$ ] Sutton 等人在 GTD2/TDC 论文的 Figure 2 中解释说，residual-gradient 解有时被称为 backwards bootstrapping，因为它会使某个状态的价值不仅像其后继状态，也像其前驱状态；这一现象长期以来被认为应当避免。 这里需要避免一个术语混淆： 普通 TD 中，奖励信息从未来向过去传播，这也是一种“向后传播价值信息”，但这是正常且必要的 credit assignment。 backwards bootstrapping 中的“backwards”不是指“未来奖励向过去传播”，而是指： [ $$ \text{前驱状态反向污染后继状态的价值。} $$ ] 也就是说，正常 TD 是： [ $$ \text{successor / outcome} \longrightarrow \text{predecessor} $$ ] 而 backwards bootstrapping 是： [ $$ \text{predecessor} \longrightarrow \text{successor value} $$ ] 后者是不希望出现的。 --- ## 6. Figure 2 的第一个例子：为什么 residual-gradient 会得到 ($\frac34,\frac14$)？ 考虑 episodic MDP： [ $$ A\to B\to \text{terminal reward }1, $$ ] [ $$ A\to C\to \text{terminal reward }0. $$ ] 从 (A) 到 (B) 或 (C) 的概率各为： [ $$ \frac12. $$ ] 所有非终止转移奖励为 0，且： [ $$ \gamma=1. $$ ] 真实价值为： [ $$ V(A)=\frac12, $$ ] [ $$ V(B)=1, $$ ] [ $$ V(C)=0. $$ ] TD fixed-point solution 给出： [ $$ A=\frac12,\quad B=1,\quad C=0. $$ ] Sutton 等人的 Figure 2 说明，在该例中 TD 解给 (B,C) 的值分别是 (1,0)，而 residual-gradient 解给 (B,C) 的值分别是 (\frac34,\frac14)。 下面解释为什么。 --- ### 6.1 TD 解的 TD error 令： [ $$ V(A)=\frac12,\quad V(B)=1,\quad V(C)=0. $$ ] 转移 (A\to B) 上： # [ $$ \delta_{A\to B} = 0+V(B)-V(A) = 1-\frac12 = \frac12. $$ ] 转移 (A\to C) 上： # [ $$ \delta_{A\to C} = 0+V(C)-V(A) = 0-\frac12 = -\frac12. $$ ] 转移 (B\to terminal) 上： # [ $$ \delta_B = 1-V(B) = 1-1=0 $$ ] 转移 (C\to terminal) 上： # [ $$ \delta_C = 0-V(C)= 0-0 $$ ] 所以 TD 解虽然给 (B,C) 正确价值，但从 (A) 出发的单样本 TD error 较大： [ $$ \delta=\pm\frac12. $$ ] --- ### 6.2 residual-gradient 解的 TD error Residual-gradient 解为： [ $$ V(A)=\frac12,\quad V(B)=\frac34,\quad V(C)=\frac14. $$ ] 此时： # [ $$ \delta_{A\to B} = \frac34-\frac12 = \frac14, $$ ] # [ $$ \delta_{A\to C} = \frac14-\frac12 = -\frac14. $$ ] 终止转移上： # [ $$ \delta_B = 1-\frac34 = \frac14, $$ ] # [ $$ \delta_C = 0-\frac14 = -\frac14. $$ ] 所有 transition 的 TD error 都变成： [ $$ \pm\frac14. $$ ] 如果按每个 episode 包含两个 transition 来计算，residual-gradient 解的 squared TD error 为： # [ $$ 2\left(\frac14\right)^2 = \frac18. $$ ] 而 TD 解每个 episode 只有一项非零误差： # [ $$ \left(\frac12\right)^2 = \frac14. $$ ] 因此 residual-gradient 解通过把误差分摊到两段 transition 上，降低了总体平方 TD error。Sutton 等人的 Figure 2 文字说明正是：RG solution 把 TD error 分摊到两个 transition 上，从而使每 episode 的 mean-square TD error 从 (\frac14) 降到 (\frac18)。 --- ## 7. 为什么这叫 backwards bootstrapping？ 在真实动态中： [ $$ B\to \text{reward }1 $$ ] 所以： [ $$ V(B)=1. $$ ] [ $$ C\to \text{reward }0 $$ ] 所以： [ $$ V(C)=0. $$ ] 但 residual-gradient 解给出： [ $$ V(B)=\frac34,\quad V(C)=\frac14. $$ ] 也就是说，(B) 被从 1 拉向 (A) 的值 (\frac12)，(C) 被从 0 拉向 (A) 的值 (\frac12)。 这意味着 (B,C) 的价值不仅由它们自己的后继结果决定，还被前驱状态 (A) 的价值反向影响。 机制上，转移 (A\to B) 的 residual-gradient 更新包含： [ $$ -\alpha\gamma\delta\nabla V(B). $$ ] 当： [ $$ \delta_{A\to B}>0 $$ ] 时，这一项会降低 (V(B))。 同理，转移 (A\to C) 上： [ $$ \delta_{A\to C}<0 $$ ] 这一项会提高 (V(C))。 于是： [ $$ B:1\to \frac34, $$ ] [ $$ C:0\to \frac14. $$ ] 这就是： [ $$ \boxed{ \text{successor value 被 predecessor 的 residual 反向修改。} } $$ ] 所以 residual-gradient 为了降低当前 transition 的残差，会牺牲后继状态本身的正确价值。 --- ## 8. 为什么 MSBE 在第一个例子中看起来能避免 backwards bootstrapping？ 第一个例子中，(A\to B/C) 是随机的。Bellman error 是条件期望意义下的误差： # [ $$ e(A) = \mathbb E[V(S')\mid A]-V(A) = \frac12 V(B)+\frac12 V(C)-V(A). $$ ] 若： [ $$ V(A)=\frac12 $$ ] 且： [ $$ V(B)+V(C)=1, $$ ] 则： [ $$ e(A)=0. $$ ] TD 解： [ $$ V(B)=1,\quad V(C)=0 $$ ] 满足： [ $$ V(B)+V(C)=1. $$ ] Residual-gradient 解： [ $$ V(B)=\frac34,\quad V(C)=\frac14 $$ ] 也满足： [ $$ V(B)+V(C)=1. $$ ] 但是 MSBE 还包含 (B,C) 的 Bellman residual： [ $$ e(B)=1-V(B), $$ ] [ $$ e(C)=0-V(C). $$ ] 为了让这两项为零，必须有： [ $$ V(B)=1,\quad V(C)=0. $$ ] 因此，在这个无函数近似的随机例子中，TD 解 (1,0) 是 MSBE 的最小解。Sutton 等人也指出，TD solution (1,0) 在这个问题上确实是 minimum MSBE solution，这曾导致一种广泛看法：MSBE 解决了 backwards bootstrapping 问题。 但这个结论不能一般化。 --- ## 9. 加入函数近似后，为什么 MSBE 仍会出现 backwards bootstrapping？ Figure 2 右图把 (A) 拆成两个状态： [ $$ A_1,\quad A_2. $$ ] 它们共享同一个特征表示，因此函数近似器必须给它们相同价值： [ $$ V_\theta(A_1)=V_\theta(A_2)=a. $$ ] 动态变成确定性的： [ $$ A_1\to B\to 1, $$ ] [ $$ A_2\to C\to 0. $$ ] 假设两个起点概率各为： [ $$ \frac12. $$ ] 令： [ $$ V(B)=b,\quad V(C)=c. $$ ] 因为系统确定性，MSBE 与样本 squared TD error 在这里一致。目标可写为： # [ $$ J(a,b,c) = \frac12 \left[ (b-a)^2+(1-b)^2 \right] + \frac12 \left[ (c-a)^2+c^2 \right]. $$ ] 对 (a,b,c) 求一阶条件。 对 (a)： # [ $$ \frac{\partial J}{\partial a} = (a-b)+(a-c)=0. $$ ] 因此： [ $$ a=\frac{b+c}{2}. $$ ] 对 (b)： # [ $$ \frac{\partial J}{\partial b} = (b-a)+(b-1)=0. $$ ] 因此： [ $$ b=\frac{a+1}{2}. $$ ] 对 (c)： # [ $$ \frac{\partial J}{\partial c} = (c-a)+c=0. $$ ] 因此： [ $$ c=\frac{a}{2}. $$ ] 代入： # [ $$ a = \frac{1}{2} \left( \frac{a+1}{2} + \frac{a}{2} \right) = \frac{2a+1}{4}. $$ ] 所以： [ $$ 4a=2a+1, $$ ] [ $$ a=\frac12. $$ ] 于是： [ $$ b=\frac{a+1}{2}=\frac34, $$ ] [ $$ c=\frac{a}{2}=\frac14. $$ ] 因此： [ $$ \boxed{ V(B)=\frac34,\quad V(C)=\frac14. } $$ ] 这正是 backwards bootstrapping 解。Sutton 等人的 Figure 2 明确指出，在加入这种函数近似后，(\frac34,\frac14) 解不仅最小化 squared TD error，也最小化 MSBE；只有 MSPBE 把最小点放在 (1,0) 解上。 --- ## 10. 为什么函数近似会让 MSBE 出问题？ 关键约束是： [ $$ V_\theta(A_1)=V_\theta(A_2). $$ ] 但是 Bellman 更新希望： [ $$ TV(A_1)=V(B)=b, $$ ] [ $$ TV(A_2)=V(C)=c. $$ ] 如果： [ $$ b=1,\quad c=0, $$ ] 则 Bellman target 分别为 1 和 0。可是函数近似器被迫给： [ $$ A_1,A_2 $$ ] 同一个值： [ $$ a. $$ ] 于是 MSBE 试图同时减少： [ $$ b-a $$ ] 和： [ $$ c-a. $$ ] 由于 (a) 无法同时等于 (b) 和 (c)，MSBE 会通过改变 (b,c) 来折中： [ $$ b\downarrow,\quad c\uparrow. $$ ] 也就是： [ $$ 1\to\frac34, $$ ] [ $$ 0\to\frac14. $$ ] 这就是函数近似下的 backwards bootstrapping： 为了减少无法被函数近似空间表达的 (A_1,A_2) 误差，MSBE 牺牲了 (B,C) 的正确值。 --- ## 11. MSPBE 为什么避免这个问题？ MSPBE 是： # [ $$ \operatorname{MSPBE}(\theta) = ||V_\theta-\Pi TV_\theta||_D^2. $$ ] 它不是直接要求： [ $$ V_\theta\approx TV_\theta, $$ ] 而是要求： [ $$ V_\theta\approx \Pi TV_\theta. $$ ] 也就是说，它先把 Bellman 更新结果投影回函数近似空间，再比较误差。 在右图例子中，($A_1,A_2$) 共享特征，所以投影会把二者的 Bellman residual 合并到同一个可表示方向上。对于 (A)-feature，可表示的残差是平均意义下的： # [ $$ \bar e_A = \frac12[(b-a)+(c-a)] = \frac{b+c}{2}-a. $$ ] 若取 TD 解： [ $$ a=\frac12,\quad b=1,\quad c=0, $$ ] 则： # [ $$ \bar e_A = \frac{1+0}{2}-\frac12 $$ ] 并且： [ $$ e(B)=1-b=0, $$ ] [ $$ e(C)=0-c=0. $$ ] 因此 MSPBE 在： [ $$ B=1,\quad C=0 $$ ] 处达到最优。 这说明 MSPBE 的关键不是强行拟合每个不可区分状态的 Bellman target，而是承认函数近似器最终会把 (A_1,A_2) 投影到同一个近似值上。Sutton 等人的解释正是：MSBE 会消耗函数近似资源去减少 (A_1,A_2) 相关的 Bellman error，而 MSPBE 会考虑这些近似值最终会被投影到同一个 value function 上。 --- ## 12. Residual-gradient 为什么通常慢？ Residual-gradient 的慢来自两个层面。 ### 12.1 更新方向更保守 普通 TD 只移动当前状态预测： [ $$ V(s)\leftarrow V(s)+\alpha\delta. $$ ] Residual-gradient 同时移动前驱和后继： [ $$ V(s)\leftarrow V(s)+\alpha\delta, $$ ] [ $$ V(s')\leftarrow V(s')-\alpha\gamma\delta. $$ ] 这样虽然保证局部下降平方残差，但会产生相互抵消的传播。Baird 的分析指出，direct algorithms 可以快但可能不稳定；residual-gradient algorithms 稳定但可能很慢。([SciSpace](https://scispace.com/pdf/residual-algorithms-reinforcement-learning-with-function-150011hve2.pdf "Residual algorithms: reinforcement learning with function approximation")) ### 12.2 信息双向传播，后继价值也被拖动 在链式任务中，正确的信息流应当是： [ $$ \text{terminal reward} \to \text{late states} \to \text{early states}. $$ ] Residual-gradient 会让早期状态误差反过来改变后继状态估计，导致后继状态向前驱状态折中。这会阻碍价值信息从真实后继结果向前传播。 Baird 的原文解释说，direct 方法中信息纯粹从 later states 流向 earlier states；而 residual-gradient 会让信息双向流动，其中错误方向的信息流会导致学习很慢。([SciSpace](https://scispace.com/pdf/residual-algorithms-reinforcement-learning-with-function-150011hve2.pdf "Residual algorithms: reinforcement learning with function approximation")) --- ## 13. Residual-gradient 的优点与缺点 | 方法 | 更新方向 | 优点 | 缺点 | | ------------------------ | ------------------------------------------ | ------------------------------ | ------------------------------ | | 普通 TD / semi-gradient TD | ($\delta\nabla V(s)$) | 快，符合 TD fixed point 语义 | off-policy + 函数近似下可能发散 | | Residual-gradient | ($\delta(\nabla V(s)-\gamma\nabla V(s'))$) | 真梯度方法，收敛性较强 | 慢，可能产生 backwards bootstrapping | | GTD / GTD2 / TDC | MSPBE 梯度相关方向 | 保持 TD fixed point 目标，同时有梯度收敛理论 | 推导与实现更复杂，需要辅助变量 | Residual-gradient 的理论吸引力来自“真梯度下降”：它确实沿某个明确目标函数下降。问题在于，这个目标函数通常不是 TD 想要的 projected Bellman fixed point；在函数近似下，MSBE 目标可能把函数容量用在不该优化的残差方向上。Sutton 等人提出 GTD2/TDC 的动机之一，正是改用 MSPBE 目标，而不是 MSBE 或 squared TD error。 --- ## 14. 最核心机制总结 Residual-gradient 的更新是： [ $$ \boxed{ \theta \leftarrow \theta+\alpha\delta \left( \nabla V_\theta(s)-\gamma\nabla V_\theta(s') \right) } $$ ] 普通 TD 的更新是： [ $$ \boxed{ \theta \leftarrow \theta+\alpha\delta\nabla V_\theta(s) } $$ ] 多出来的项： [ $$ \boxed{ -\alpha\gamma\delta\nabla V_\theta(s') } $$ ] 使 residual-gradient 成为真正的梯度方法，但也导致后继状态被当前 transition 的误差反向修改。 因此： # [ $$ \boxed{ \text{backwards bootstrapping} = \text{为了减少 Bellman residual，使后继状态价值向前驱状态价值折中。} } $$ ] 在无函数近似的简单随机例子中，MSBE 可能避免这种现象；但一旦引入函数近似，MSBE 仍可能让 (\frac34,\frac14) 这类 backwards-bootstrapping 解重新出现。MSPBE 的关键改进是先把 Bellman 更新投影回可表示函数空间，因此目标与 TD fixed point： [ $$ V_\theta=\Pi TV_\theta $$ ] 一致，而不是直接追逐未投影的 Bellman residual。 --- 下面这段是 GTD2 与 TDC 的核心推导。它的主线是： [ $$ \text{MSPBE 目标} \quad\Longrightarrow\quad \text{梯度形式} \quad\Longrightarrow\quad \text{引入辅助变量 }w \quad\Longrightarrow\quad \text{得到 GTD2 和 TDC} $$ ] 论文原文明确指出，本节把两个新算法推导为 **projected Bellman error objective**，即 MSPBE 目标上的随机梯度下降算法；GTD2 和 TDC 都保持 (O(n)) 复杂度，其中 (n) 是特征维度。 # 推导主线总览 这段推导可以压缩成如下链条： # [ $$ \operatorname{MSPBE}(\theta) = |V_\theta-\Pi TV_\theta|_D^2 $$ ] [ $$ \Downarrow $$ ] # [ $$ \operatorname{MSPBE}(\theta) = \mathbb E[\delta\phi]^\top \mathbb E[\phi\phi^\top]^{-1} \mathbb E[\delta\phi] $$ ] [ $$ \Downarrow $$ ] [ $$ w \approx \mathbb E[\phi\phi^\top]^{-1} \mathbb E[\delta\phi] $$ ] [ $$ \Downarrow $$ ] [ $$ -\frac12\nabla\operatorname{MSPBE}(\theta) \approx \mathbb E[(\phi-\gamma\phi')\phi^\top]w $$ ] [ $$ \Downarrow $$ ] [ $$ \text{GTD2} $$ ] 或者： ## [ $$ -\frac12\nabla\operatorname{MSPBE}(\theta) \approx \mathbb E[\delta\phi] - \gamma\mathbb E[\phi'\phi^\top]w $$ ] [ $$ \Downarrow $$ ] [ $$ \text{TDC}. $$ ] GTD2 和 TDC 其实来自同一个 MSPBE 梯度，只是对同一个梯度表达式采用了两种不同的采样分解方式。论文第 4 节正是按这个逻辑从 MSPBE 推导两个算法。 --- # 三、两个基础期望关系的解释 ## 3.1 为什么有 (\mathbb E[\phi\phi^\top]=\Phi^\top D\Phi)？ 设： [ $$ \Phi= \begin{bmatrix} \phi_1^\top\ \phi_2^\top\ \vdots\ \phi_N^\top \end{bmatrix}, \quad D=\operatorname{diag}(d_1,\dots,d_N). $$ ] 则： # [ $$ \Phi^\top D\Phi = \sum_s d_s\phi_s\phi_s^\top. $$ ] 如果状态 (s) 按分布 (d) 被采样，则随机特征向量为： [ $$ \phi=\phi_s. $$ ] 因此： # [ $$ \mathbb E[\phi\phi^\top] = \sum_s d_s\phi_s\phi_s^\top = \Phi^\top D\Phi. $$ ] 这个矩阵通常记为： [ $$ C=\mathbb E[\phi\phi^\top]. $$ ] 它是特征向量在状态采样分布 (d) 下的二阶矩阵，也可以理解为特征协方差型矩阵，不过严格说若特征未中心化，它是 second moment matrix。 --- ## 3.2 为什么有 ($\mathbb E[\delta\phi]=\Phi^\top D(TV_\theta-V_\theta)$)？ TD error 为： # [ $$ \delta = r+\gamma V_\theta(s')-V_\theta(s). $$ ] 在给定当前状态 (s) 后，对下一状态与奖励取条件期望： # [ $$ \mathbb E[\delta\mid s] = R_s+\gamma\sum_{s'}P_{ss'}V_\theta(s')-V_\theta(s). $$ ] 而 Bellman 算子为： # [ $$ TV_\theta = R+\gamma PV_\theta. $$ ] 所以： # [ $$ \mathbb E[\delta\mid s] = (TV_\theta)(s)-V_\theta(s). $$ ] 再乘以 (\phi_s)，对 (s\sim d) 求期望： # [ $$ \mathbb E[\delta\phi] = \sum_s d_s\phi_s \bigl((TV_\theta)(s)-V_\theta(s)\bigr). $$ ] 矩阵形式即： # [ $$ \mathbb E[\delta\phi] = \Phi^\top D(TV_\theta-V_\theta). $$ ] 这个量非常关键，因为传统 TD 的期望更新方向正是： [ $$ \mathbb E[\delta\phi]. $$ ] TD fixed point 满足： [ $$ \mathbb E[\delta\phi]=0. $$ ] --- # 四、Figure 2：为什么要讨论 backward bootstrapping？ 这部分看似插入了一个例子，实际上是在说明： [ $$ \operatorname{MSBE} $$ ] 并不总是合适目标；尤其在函数近似下，MSBE 可能重新导致 residual-gradient 方法的 backward bootstrapping 问题。 ## 4.1 没有函数近似时的例子 结构为： [ $$ A\to B\to \text{terminal reward }1 $$ ] [ $$ A\to C\to \text{terminal reward }0 $$ ] 从 (A) 到 (B) 或 (C) 的概率各为： [ $$ \frac12. $$ ] 且： [ $$ \gamma=1. $$ ] 真实价值为： [ $$ V(A)=\frac12,\quad V(B)=1,\quad V(C)=0. $$ ] TD fixed point 给出： [ $$ V(B)=1,\quad V(C)=0. $$ ] Residual-gradient 解给出： [ $$ V(B)=\frac34,\quad V(C)=\frac14. $$ ] 为什么 residual-gradient 会这样？因为它在最小化 squared TD error 时，会倾向于把误差平均分配到不同转移上。 对于 TD 解： [ $$ V(A)=\frac12,\quad V(B)=1,\quad V(C)=0. $$ ] 从 (A\to B) 的 TD error： # [ $$ \delta_{A\to B} = 0+V(B)-V(A) = 1-\frac12 = \frac12. $$ ] 从 (A\to C) 的 TD error： # [ $$ \delta_{A\to C} = 0+V(C)-V(A) = 0-\frac12 = -\frac12. $$ ] 所以 squared TD error 较大。 Residual-gradient 解使： [ $$ V(B)=\frac34,\quad V(C)=\frac14. $$ ] 此时： # [ $$ \delta_{A\to B} = \frac34-\frac12 = \frac14, $$ ] # [ $$ \delta_{A\to C} = \frac14-\frac12 = -\frac14. $$ ] 同时： # [ $$ \delta_{B\to terminal} = 1-\frac34 = \frac14, $$ ] # [ $$ \delta_{C\to terminal} = 0-\frac14 = -\frac14. $$ ] 所有转移上的 TD error 都变成 (\pm\frac14)。因此 squared TD error 总体下降。论文把这种现象称为 residual-gradient 解把 TD error 分摊到两条转移上。 问题是，这会让： [ $$ B,C $$ ] 的价值不仅受后继奖励影响，还受前驱状态 (A) 影响。于是 (B) 被从 1 拉低到 (\frac34)，(C) 被从 0 拉高到 (\frac14)。这就是： [ $$ \text{backward bootstrapping}. $$ ] 它违背 TD 的基本方向：价值应从后继结果向前传播，而不应让前驱状态反向污染后继状态价值。 --- ## 4.2 为什么 MSBE 不能一般性解决 backward bootstrapping？ 在左/中图那个无函数近似例子中，TD 解 (1,0) 的确是 MSBE 最优解。因此容易误以为： [ $$ \operatorname{MSBE} $$ ] 能解决 backward bootstrapping。 但是右图加入函数近似后，情况改变。 右图中，原来的 (A) 被拆成： [ $$ A_1,\quad A_2. $$ ] 它们共享相同特征表示： [ $$ \phi(A_1)=\phi(A_2). $$ ] 因此近似函数必须给出同一个值： [ $$ V_\theta(A_1)=V_\theta(A_2). $$ ] 动态是确定性的： [ $$ A_1\to B\to 1, $$ ] [ $$ A_2\to C\to 0. $$ ] 从可观察数据看，(A_1,A_2) 因为特征相同而无法区分。此时 MSBE 会试图减少 (A_1,A_2) 的 Bellman error，但函数近似器没有能力分别调节二者价值。结果，MSBE 会重新偏向类似： [ $$ V(B)=\frac34,\quad V(C)=\frac14 $$ ] 的解。论文明确指出，在该函数近似版本中，(\frac34,\frac14) 解不仅最小化 squared TD error，也最小化 MSBE；只有 MSPBE 把最小点放在 (1,0) 解上。 这个例子说明： [ $$ \boxed{ \operatorname{MSBE} \text{ 会关注不可表达结构造成的 Bellman error，} \text{从而浪费函数近似容量。} } $$ ] 而： [ $$ \boxed{ \operatorname{MSPBE} \text{ 会先考虑投影，承认 }A_1,A_2\text{ 最终只能映射到同一个近似值。} } $$ ] 这就是 MSPBE 更适合 TD fixed point 的原因。 --- # 五、从 MSPBE 到期望形式的推导 目标函数为： # [ $$ \operatorname{MSPBE}(\theta) = |V_\theta-\Pi TV_\theta|_D^2. $$ ] 因为： [ $$ V_\theta\in \operatorname{span}(\Phi), $$ ] 所以： [ $$ \Pi V_\theta=V_\theta. $$ ] 因此： # [ $$ V_\theta-\Pi TV_\theta = \Pi V_\theta-\Pi TV_\theta = \Pi(V_\theta-TV_\theta). $$ ] 于是： # [ $$ \operatorname{MSPBE}(\theta) = |\Pi(V_\theta-TV_\theta)|_D^2. $$ ] 展开 (D)-范数： # [ $$ (\Pi(V_\theta-TV_\theta))^\top D (\Pi(V_\theta-TV_\theta)). $$ ] 将 (\Pi) 移到中间： # [ $$ (V_\theta-TV_\theta)^\top \Pi^\top D\Pi (V_\theta-TV_\theta). $$ ] 投影矩阵为： [ $$ \Pi=\Phi(\Phi^\top D\Phi)^{-1}\Phi^\top D. $$ ] 代入可得： # [ $$ \Pi^\top D\Pi = D^\top\Phi(\Phi^\top D\Phi)^{-1}\Phi^\top D. $$ ] 由于 (D) 是对角矩阵，通常有： [ $$ D^\top=D. $$ ] 因此： # [ $$ \operatorname{MSPBE}(\theta) = (V_\theta-TV_\theta)^\top D\Phi(\Phi^\top D\Phi)^{-1} \Phi^\top D (V_\theta-TV_\theta). $$ ] 把符号改成： [ $$ TV_\theta-V_\theta $$ ] 后，由于两边同时取负号，不影响平方型，得到： # [ $$ \left[ \Phi^\top D(TV_\theta-V_\theta) \right]^\top (\Phi^\top D\Phi)^{-1} \left[ \Phi^\top D(TV_\theta-V_\theta) \right]. $$ ] 利用前面两个关系： # [ $$ \Phi^\top D(TV_\theta-V_\theta) = \mathbb E[\delta\phi], $$ ] # [ $$ \Phi^\top D\Phi = \mathbb E[\phi\phi^\top], $$ ] 得到： # [ $$ \boxed{ \operatorname{MSPBE}(\theta) = \mathbb E[\delta\phi]^\top \mathbb E[\phi\phi^\top]^{-1} \mathbb E[\delta\phi]. } $$ ] 这一步是整个推导的中心。论文在第 4 节正是通过该等价式说明 MSPBE 与 NEU 的差别只在一个特征二阶矩阵逆。 --- # 六、MSPBE 与 NEU 的差别 原始 GTD 使用的目标是： # [ $$ \operatorname{NEU}(\theta) = \mathbb E[\delta\phi]^\top \mathbb E[\delta\phi]. $$ ] 而 MSPBE 是： # [ $$ \operatorname{MSPBE}(\theta) = \mathbb E[\delta\phi]^\top C^{-1} \mathbb E[\delta\phi], $$ ] 其中： [ $$ C=\mathbb E[\phi\phi^\top]. $$ ] 所以二者差异为： [ $$ \operatorname{NEU}: \quad I $$ ] [ $$ \operatorname{MSPBE}: \quad C^{-1}. $$ ] 也就是说，NEU 使用普通欧氏范数衡量期望 TD update；MSPBE 使用由特征二阶矩阵逆诱导的度量来衡量同一个量。 如果特征尺度不同、相关性强，NEU 的几何会受特征参数化影响较大；MSPBE 则对应 projected Bellman error 的 (D)-加权投影几何。因此，MSPBE 比 NEU 更直接对应 TD fixed point 的几何意义。 --- # 七、为什么需要辅助变量 (w)？ MSPBE 形式为： # [ $$ J(\theta) = m(\theta)^\top C^{-1}m(\theta), $$ ] 其中： [ $$ m(\theta)=\mathbb E[\delta\phi], $$ ] [ $$ C=\mathbb E[\phi\phi^\top]. $$ ] 如果直接计算梯度，需要： # [ $$ C^{-1}m(\theta) = \mathbb E[\phi\phi^\top]^{-1} \mathbb E[\delta\phi]. $$ ] 这涉及矩阵逆： [ $$ C^{-1}. $$ ] 若特征维度为 (n)，显式维护和求逆 (C) 通常至少需要 (O(n^2)) 存储或计算，违背算法希望保持 (O(n)) 的目标。 因此引入辅助向量： [ $$ w\in\mathbb R^n. $$ ] 令： # [ $$ w\approx C^{-1}m(\theta) = \mathbb E[\phi\phi^\top]^{-1}\mathbb E[\delta\phi]. $$ ] 这样无需显式求逆，只需在线更新 (w)。论文明确说，使用第二个可调参数 (w) 是为了形成准静态估计，并避免对两个独立样本的需求。 --- # 八、(w) 的更新为什么是式 (9)？ 式 (9) 为： # [ $$ w_{k+1} = w_k + \beta_k(\delta_k-\phi_k^\top w_k)\phi_k. $$ ] 固定 (\theta) 时，取期望： # [ $$ \mathbb E[\Delta w] = \beta \mathbb E[(\delta-\phi^\top w)\phi]. $$ ] 展开： # [ $$ \mathbb E[(\delta-\phi^\top w)\phi] = \mathbb E[\delta\phi] - \mathbb E[\phi\phi^\top]w. $$ ] 即： # [ $$ m-Cw. $$ ] 当该期望更新为零时： [ $$ m-Cw=0. $$ ] 所以： [ $$ Cw=m. $$ ] 因此： # [ $$ w=C^{-1}m = \mathbb E[\phi\phi^\top]^{-1} \mathbb E[\delta\phi]. $$ ] 这正是式 (7)。 所以 (w) 更新可以理解为在线求解线性方程： [ $$ Cw=m. $$ ] 也可以理解为用线性预测器 ($\phi^\top w$) 去预测 TD error (\delta)。其均方误差目标为： [ $$ \mathbb E[(\delta-\phi^\top w)^2]. $$ ] 该目标的一阶条件就是： [ $$ \mathbb E[\phi(\delta-\phi^\top w)]=0, $$ ] 等价于： [ $$ Cw=m. $$ ] 论文后续收敛证明中也把 (w) 的 ODE 写成： [ $$ \dot w(t)=\mathbb E[\delta\phi\mid\theta]-Cw(t), $$ ] 其稳定平衡点为： [ $$ w^*=C^{-1}\mathbb E[\delta\phi\mid\theta]. $$ ] 这与上述解释完全一致。 --- # 九、MSPBE 梯度推导 令： # [ $$ J(\theta) = \operatorname{MSPBE}(\theta) = m(\theta)^\top C^{-1}m(\theta). $$ ] 其中： [ $$ m(\theta)=\mathbb E[\delta\phi]. $$ ] 先写出 (m(\theta)) 的线性形式。TD error 为： # [ $$ \delta = r+\gamma\theta^\top\phi'-\theta^\top\phi. $$ ] 因此： # [ $$ \delta\phi = r\phi + \phi(\gamma\phi'-\phi)^\top\theta. $$ ] 所以： # [ $$ m(\theta) = \mathbb E[r\phi] + \mathbb E[\phi(\gamma\phi'-\phi)^\top]\theta. $$ ] 定义： [ $$ A=\mathbb E[\phi(\phi-\gamma\phi')^\top], $$ ] [ $$ b=\mathbb E[r\phi]. $$ ] 则： [ $$ m(\theta)=b-A\theta. $$ ] 于是： [ $$ \nabla_\theta m(\theta)=-A. $$ ] 因为： [ $$ J(\theta)=m^\top C^{-1}m, $$ ] 所以： # [ $$ \nabla_\theta J(\theta) = 2(\nabla_\theta m)^\top C^{-1}m -2A^\top C^{-1}m. $$ ] 因此： # [ $$ -\frac12\nabla_\theta J(\theta) = A^\top C^{-1}m. $$ ] 又因为： # [ $$ A^\top = \mathbb E[(\phi-\gamma\phi')\phi^\top], $$ ] 所以： # [ $$ -\frac12\nabla\operatorname{MSPBE}(\theta) = \mathbb E[(\phi-\gamma\phi')\phi^\top] C^{-1} \mathbb E[\delta\phi]. $$ ] 代入： [ $$ w\approx C^{-1}\mathbb E[\delta\phi], $$ ] 得到： [ $$ -\frac12\nabla\operatorname{MSPBE}(\theta) \approx \mathbb E[(\phi-\gamma\phi')\phi^\top]w. $$ ] 这就是 GTD2 的基础。 --- # 十、GTD2 的采样形式 有： [ $$ \mathbb E[(\phi-\gamma\phi')\phi^\top]w. $$ ] 对单个样本： [ $$ (\phi_k,\phi'_k) $$ ] 可用： [ $$ (\phi_k-\gamma\phi'_k)\phi_k^\top w_k $$ ] 作为采样估计。 因为： [ $$ \phi_k^\top w_k $$ ] 是标量，所以更新方向是： [ $$ (\phi_k-\gamma\phi'_k)(\phi_k^\top w_k). $$ ] 于是 GTD2 更新为： # [ $$ \boxed{ \theta_{k+1} = \theta_k + \alpha_k(\phi_k-\gamma\phi'_k)(\phi_k^\top w_k) } $$ ] # [ $$ \boxed{ w_{k+1} = w_k + \beta_k(\delta_k-\phi_k^\top w_k)\phi_k. } $$ ] 这就是论文称为 GTD2 的 (O(n)) 算法。 注意：GTD2 的 (\theta) 更新不像传统 TD。传统 TD 是： # [ $$ \theta_{k+1} = \theta_k+\alpha_k\delta_k\phi_k. $$ ] GTD2 是： # [ $$ \theta_{k+1} = \theta_k+\alpha_k(\phi_k-\gamma\phi'_k)(\phi_k^\top w_k). $$ ] 它直接采样 MSPBE 的负梯度方向，而不是在 TD 更新上做修正。 --- # 十一、TDC 的推导 TDC 从同一个负梯度开始： # [ $$ -\frac12\nabla J(\theta) = \mathbb E[(\phi-\gamma\phi')\phi^\top]C^{-1}m. $$ ] 展开矩阵： # [ $$ \mathbb E[(\phi-\gamma\phi')\phi^\top] = \mathbb E[\phi\phi^\top] - \gamma\mathbb E[\phi'\phi^\top]. $$ ] 即： # [ $$ C-\gamma\mathbb E[\phi'\phi^\top]. $$ ] 因此： # [ $$ -\frac12\nabla J(\theta) = (C-\gamma\mathbb E[\phi'\phi^\top])C^{-1}m. $$ ] 展开： # [ $$ CC^{-1}m = \gamma\mathbb E[\phi'\phi^\top]C^{-1}m. $$ ] 即： # [ $$ m = \gamma\mathbb E[\phi'\phi^\top]C^{-1}m. $$ ] 由于： [ $$ m=\mathbb E[\delta\phi], $$ ] 以及： [ w\approx C^{-1}m, ] 得到： ## [ $$ -\frac12\nabla J(\theta) \approx \mathbb E[\delta\phi] - \gamma\mathbb E[\phi'\phi^\top]w. $$ ] 单样本估计为： ## [ $$ \delta_k\phi_k = \gamma\phi'_k(\phi_k^\top w_k). $$ ] 于是 TDC 更新为： # [ $$ \boxed{ \theta_{k+1} = \theta_k + \alpha_k\delta_k\phi_k - \alpha_k\gamma\phi'_k(\phi_k^\top w_k) } $$ ] # [ $$ \boxed{ w_{k+1} = w_k + \beta_k(\delta_k-\phi_k^\top w_k)\phi_k. } $$ ] 论文称该算法为 **TD with gradient correction**，简称 TDC。其第一项完全等于 conventional linear TD 的更新；第二项是 correction term，用于把普通 TD 更新修正为 MSPBE 梯度方向。 --- # 十二、TDC 为什么叫 “TD with gradient correction”？ TDC 的 ($\theta$) 更新为： # [ $$ \theta_{k+1} = \theta_k + \alpha_k\delta_k\phi_k - \alpha_k\gamma\phi'_k(\phi_k^\top w_k). $$ ] 把它拆成两部分： [ $$ \underbrace{\alpha_k\delta_k\phi_k}_{\text{普通 TD 更新}} $$ ] [ $$ \underbrace{ -\alpha_k\gamma\phi'_k(\phi_k^\top w_k) }_{\text{gradient correction}} $$ ] 第一项： [ $$ \alpha_k\delta_k\phi_k $$ ] 就是传统线性 TD： # [ $$ \theta_{k+1} = \theta_k+\alpha_k\delta_k\phi_k. $$ ] 第二项用于修正 TD 的方向。普通 TD 不是 MSPBE 的真实梯度下降；它缺少 correction term。TDC 加上第二项后，其期望更新方向变成： ## [ $$ \mathbb E[\delta\phi] = \gamma\mathbb E[\phi'\phi^\top]w $$ ] 而这正近似于： [ $$ -\frac12\nabla\operatorname{MSPBE}(\theta). $$ ] 因此： # [ $$ \boxed{ \text{TDC} = \text{TD} + \text{使其沿 MSPBE 梯度下降的修正项}. } $$ ] 这也是 TDC 比 GTD2 更接近传统 TD 的原因。 --- # 十三、为什么 (w_0=0) 时 TDC 初始接近普通 TD？ 若： [ $$ w_0=0, $$ ] 则初始时 correction term 为： [ $$ -\alpha_k\gamma\phi'_k(\phi_k^\top w_k)=0. $$ ] 因此 TDC 一开始的 ($\theta$) 更新近似为： [ $$ \theta_{k+1} \approx \theta_k+\alpha_k\delta_k\phi_k. $$ ] 这就是普通 TD 更新。 随着 ($w_k$) 逐渐学习到： [ $$ w\approx C^{-1}\mathbb E[\delta\phi], $$ ] correction term 开始发挥作用，把 TD 更新拉向 MSPBE 的梯度方向。 论文原文也指出，若 ($w_0=0$) 且 ($\beta_k$) 较小，TDC 开始时几乎与传统线性 TD 做出相同更新。 --- # 十四、为什么 ($\theta$) 收敛后 ($w$) 会收敛回零？ TD fixed point 满足： [ $$ \mathbb E[\delta\phi]=0. $$ ] 而： [ $$ w \approx C^{-1}\mathbb E[\delta\phi]. $$ ] 如果 (\theta) 已经收敛到 TD fixed point，则： [ $$ \mathbb E[\delta\phi]=0. $$ ] 因此： [ $$ w\approx C^{-1}0=0. $$ ] 所以： [ $$ w\to 0. $$ ] 这解释了论文中的最后一句：在 (\theta_k) 收敛后，(w_k) 会再次收敛到零。 --- # 十五、为什么说避免了 two independent samples？ MSPBE 梯度中含有多个期望的乘积： [ $$ \mathbb E[(\phi-\gamma\phi')\phi^\top] C^{-1} \mathbb E[\delta\phi]. $$ ] 如果直接用单个样本同时估计这些期望乘积，通常会产生偏差。因为： [ $$ \mathbb E[XY]\neq \mathbb E[X]\mathbb E[Y] $$ ] 一般成立。如果想无偏估计期望乘积，可能需要两个独立样本。所谓 two-sample 问题在 Bellman residual/MSBE 梯度方法中尤其常见。 GTD2/TDC 的策略是：不直接采样整个乘积，而是让 (w) 通过另一个递推过程跟踪： [ $$ C^{-1}\mathbb E[\delta\phi]. $$ ] 当 (w) 近似稳定后，(\theta) 更新只需采样： [ $$ (\phi-\gamma\phi')\phi^\top w $$ ] 或： [ $$ \delta\phi-\gamma\phi'(\phi^\top w). $$ ] 这就避免了对两个独立 next-state 样本的需求，同时仍能构造 MSPBE 梯度方向的随机近似。论文第 4 节明确说，引入 (w) 是为了形成准静态估计，从而避免需要两个独立样本。 --- # 十六、GTD2 与 TDC 的关系 两者共享同一个辅助变量更新： # [ $$ w_{k+1} = w_k + \beta_k(\delta_k-\phi_k^\top w_k)\phi_k. $$ ] 差别只在 (\theta) 更新。 ## GTD2 # [ $$ \theta_{k+1} = \theta_k + \alpha_k(\phi_k-\gamma\phi'_k)(\phi_k^\top w_k). $$ ] 它直接采样： [ $$ \mathbb E[(\phi-\gamma\phi')\phi^\top]w. $$ ] ## TDC # [ $$ \theta_{k+1} = \theta_k + \alpha_k\delta_k\phi_k - \alpha_k\gamma\phi'_k(\phi_k^\top w_k). $$ ] 它采样： ## [ $$ \mathbb E[\delta\phi] = \gamma\mathbb E[\phi'\phi^\top]w. $$ ] 二者在期望层面都对应： [ $$ -\frac12\nabla\operatorname{MSPBE}(\theta). $$ ] 但 TDC 的形式保留了传统 TD 项，因此实践中更像普通 TD，只是在其后增加一个 correction term。论文摘要中也强调，TDC 使用与 conventional TD 相同的更新规则，只是多了一个初始为零的附加项。 --- # 十七、复杂度为什么是 (O(n))？ 每一步更新需要计算几个内积： [ $$ \phi_k^\top w_k, $$ ] [ $$ \theta_k^\top\phi_k, $$ ] [ $$ \theta_k^\top\phi'_k. $$ ] 这些都是 (O(n))。 向量更新如： [ $$ (\phi_k-\gamma\phi'_k)(\phi_k^\top w_k) $$ ] 或： [ $$ \delta_k\phi_k-\gamma\phi'_k(\phi_k^\top w_k) $$ ] 也都是 (O(n))。 存储方面，需要： [ $$ \theta\in\mathbb R^n, \quad w\in\mathbb R^n. $$ ] 所以内存是： [ $$ O(n). $$ ] 与 LSTD 这类需要矩阵 (n\times n) 的方法相比，GTD2/TDC 避免了 (O(n^2)) 存储。论文结论也强调，这两个算法的时间和内存复杂度都随特征数量线性增长，并且比早期 GTD 明显更快。 --- # 十八、这一节的核心意义 这段推导的核心结论是： # [ $$ \boxed{ \operatorname{MSPBE} = \mathbb E[\delta\phi]^\top \mathbb E[\phi\phi^\top]^{-1} \mathbb E[\delta\phi] } $$ ] 这个表达把几何意义明确的 projected Bellman error 转换成可用样本估计的期望形式。然后利用辅助变量： [ $$ \boxed{ w\approx \mathbb E[\phi\phi^\top]^{-1} \mathbb E[\delta\phi] } $$ ] 避免显式求逆和 two-sample 问题，最终得到两个 (O(n)) 算法： # [ $$ \boxed{ \text{GTD2: } \theta_{k+1} = \theta_k + \alpha_k(\phi_k-\gamma\phi'_k)(\phi_k^\top w_k) } $$ ] # [ $$ \boxed{ \text{TDC: } \theta_{k+1} = \theta_k + \alpha_k\delta_k\phi_k - \alpha_k\gamma\phi'_k(\phi_k^\top w_k) } $$ ] 二者都以 MSPBE 为目标；差别在于 GTD2 直接采样梯度表达式，而 TDC 把同一梯度拆成“普通 TD 更新 + 梯度修正项”。因此，TDC 可以被理解为： [ $$ \boxed{ \text{把 conventional TD 扩展为 off-policy 稳定的梯度 TD 方法。} } $$ ] 但需要强调：TDC 不是简单地“给 TD 加一个经验修补项”，而是严格来自 MSPBE 的负梯度分解。其 correction term 的作用是把普通 TD 的半梯度更新方向修正为 projected Bellman error 目标的梯度下降方向。 --- 下面这段内容虽然标题从 **“5. Proof of convergence of GTD2”** 开始，但粘贴文本实际包含两部分： [ $$ \text{第 5 节：GTD2 收敛性证明} $$ ] [ $$ \text{第 6 节：TDC 收敛性证明} $$ ] 二者目标相同：证明算法参数 (\theta_k) 最终收敛到 **TD fixed point**： [ $$ V_\theta=\Pi T V_\theta. $$ ] 等价地，在参数空间中收敛到： [ $$ \theta^*=A^{-1}b. $$ ] 其中： [ $$ A=\mathbb E[\phi(\phi-\gamma\phi')^\top], \qquad b=\mathbb E[r\phi], \qquad C=\mathbb E[\phi\phi^\top]. $$ ] 这篇 ICML 2009 论文提出 GTD2 与 TDC，用 MSPBE 作为目标函数，并证明二者在标准随机逼近假设下几乎必然收敛。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- # 一、第 5 节：GTD2 收敛性证明翻译 ## 5. GTD2 的收敛性证明 本节的目的是证明：在标准假设下，GTD2 算法以概率 1 收敛到 TD fixed point，即式 (4)。 ### 定理 1：GTD2 的收敛性 考虑 GTD2 的两个迭代式： # [ $$ \theta_{k+1} \theta_k + \alpha_k(\phi_k-\gamma\phi'_k)(\phi_k^\top w_k), \tag{8} $$ ] # [ $$ w_{k+1} w_k + \beta_k(\delta_k-\phi_k^\top w_k)\phi_k. \tag{9} $$ ] 步长序列 (\alpha_k,\beta_k) 满足： [ $$ \beta_k=\eta\alpha_k,\qquad \eta>0, $$ ] [ $$ \alpha_k,\beta_k\in(0,1], $$ ] [ $$ \sum_{k=0}^{\infty}\alpha_k=\infty, $$ ] [ $$ \sum_{k=0}^{\infty}\alpha_k^2<\infty. $$ ] 进一步假设： [ $$ (\phi_k,r_k,\phi'_k) $$ ] 是独立同分布序列，并且二阶矩一致有界。定义： [ $$ A=\mathbb E[\phi_k(\phi_k-\gamma\phi'_k)^\top], $$ ] [ $$ b=\mathbb E[r_k\phi_k], $$ ] [ $$ C=\mathbb E[\phi_k\phi_k^\top]. $$ ] 假设 (A) 和 (C) 都非奇异。那么参数向量 (\theta_k) 以概率 1 收敛到 TD fixed point。该定理就是论文中 GTD2 收敛性证明的正式表述。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- ## 证明翻译 该证明与 Sutton、Szepesvári 和 Maei 对 GTD 的证明非常相似，因此原文省略了一些细节。先前工作已经说明，TD fixed point 可以写成： [ $$ -A\theta+b=0. \tag{11} $$ ] 首先，把算法的两个迭代式重写成一个 (2n) 维联合参数向量上的单一迭代。定义： [ $$ \rho_k^\top=(d_k^\top,\theta_k^\top), $$ ] 其中： [ $$ d_k=\frac{w_k}{\sqrt{\eta}}. $$ ] 再定义一个与奖励有关的 (2n) 维向量： [ $$ g_{k+1}^\top=(r_k\phi_k^\top,0^\top). $$ ] 于是算法可以写成： # [ $$ \rho_{k+1} = \rho_k + \alpha_k\sqrt{\eta} \left( G_{k+1}\rho_k+g_{k+1} \right), $$ ] 其中： # [ $$ G_{k+1} = \begin{pmatrix} -\sqrt{\eta}\phi_k\phi_k^\top & \phi_k(\gamma\phi'_k-\phi_k)^\top \\ (\phi_k-\gamma\phi'_k)\phi_k^\top & 0 \end{pmatrix}. $$ ] 令： [ Z ] 由于 ($(\phi_k,r_k,\phi'_k)$) 是 i.i.d. 序列，所以 (G) 和 (g) 良定义。具体地： # [ $$ G = \begin{pmatrix} -\sqrt{\eta}C & -A\\ A^\top & 0 \end{pmatrix}, \qquad g = \begin{pmatrix} b\\ 0 \end{pmatrix}. $$ ] 进一步注意：如果 [ $$ G\rho+g=0, $$ ] 其中： [ $$ \rho^\top=(d^\top,\theta^\top), $$ ] 那么可以推出式 (11)： [ $$ -A\theta+b=0. $$ ] 接下来使用常微分方程方法，即 ODE approach，并调用 Borkar 和 Meyn 的 Theorem 2.2。Borkar-Meyn ODE 方法的基本思想是：随机逼近递推可以通过相关 ODE 的全局渐近稳定性来证明稳定和收敛。([Faculty Websites](https://faculty.eng.ufl.edu/meyn/wp-content/uploads/sites/671/archive/spm_files/Papers_pdf/ode.pdf?utm_source=chatgpt.com "The O.D.E. Method for Convergence of Stochastic ...")) 为此，把递推写成： # [ $$ \rho_{k+1} = \rho_k + \alpha_k\sqrt{\eta} \left( G\rho_k+g+(G_{k+1}-G)\rho_k+(g_{k+1}-g) \right). $$ ] 令： [ $$ \alpha'_k=\alpha_k\sqrt{\eta}, $$ ] [ $$ h(\rho)=g+G\rho, $$ ] [ $$ M_{k+1}=(G_{k+1}-G)\rho_k+g_{k+1}-g. $$ ] 于是： # [ $$ \rho_{k+1} = \rho_k+\alpha'_k(h(\rho_k)+M_{k+1}). $$ ] 令： [ $$ F_k=\sigma(\rho_1,M_1,\dots,\rho_{k-1},M_k) $$ ] 为由这些变量生成的 (\sigma)-代数。Borkar-Meyn 定理要求验证以下条件： 1. (h) 是 Lipschitz，并且 # [ $$ h_\infty(\rho) = \lim_{r\to\infty}\frac{h(r\rho)}{r} $$ ] 对每个 (\rho\in\mathbb R^{2n}) 都良定义； 2. ((M_k,F_k)) 是 martingale difference sequence，并且存在 (c_0>0)，使得： [ $$ \mathbb E[|M_{k+1}|^2\mid F_k] \leq c_0(1+|\rho_k|^2); $$ ] 3. 步长 (\alpha'_k) 满足： [ $$ 0<\alpha'_k\leq 1, $$ ] [ $$ \sum_{k=1}^{\infty}\alpha'_k=\infty, $$ ] [ $$ \sum_{k=1}^{\infty}(\alpha'_k)^2<\infty; $$ ] 4. ODE [ $$ \dot\rho=h_\infty(\rho) $$ ] 的原点是全局渐近稳定平衡点； 5. ODE [ $$ \dot\rho=h(\rho) $$ ] 有唯一全局渐近稳定平衡点。 显然： [ $$ h(\rho)=g+G\rho $$ ] 是 Lipschitz 函数，其 Lipschitz 常数可以取为： [ $$ |G|. $$ ] 并且： [ $$ h_\infty(\rho)=G\rho. $$ ] 根据构造： [ $$ \mathbb E[M_{k+1}\mid F_k]=0, $$ ] 且： [ $$ M_k\in F_k, $$ ] 所以 ((M_k,F_k)) 是 martingale difference sequence。条件 (ii-b) 可以由三角不等式和 ($(\phi_k,r_k,\phi'_k)$) 的二阶矩有界性推出。条件 (iii) 由步长假设直接得到。 接下来证明最后两个条件。首先证明矩阵 (G) 的所有特征值实部均为负。 先证明 (G) 非奇异。利用分块矩阵的行列式公式： # [ $$ \det(G) = \det(A^\top C^{-1}A) = (\det C)^{-1}(\det A)^2 \neq 0. $$ ] 因此 (G) 的所有特征值都非零。 令： [ $$ \lambda\in\mathbb C,\quad \lambda\neq 0 $$ ] 是 (G) 的一个特征值，对应归一化特征向量： [ $$ x\in\mathbb C^{2n}, \qquad x^*x=1. $$ ] 其中 (x^*) 表示复共轭转置。于是： [ $$ x^*Gx=\lambda. $$ ] 把 (x) 分成两个 (n) 维分量： [ $$ x^\top=(x_1^\top,x_2^\top), \qquad x_1,x_2\in\mathbb C^n. $$ ] 根据 (G) 的定义： # [ $$ \lambda = x^*Gx -\sqrt{\eta}|x_1|_C^2 x_1^*Ax_2 + x_2^*A^\top x_1, $$ ] 其中： [ $$ |x_1|_C^2=x_1^*Cx_1. $$ ] 因为 (A) 是实矩阵，所以： [ $$ A^*=A^\top, $$ ] 从而： # [ $$ (x_1^*Ax_2)^* = x_2^*A^\top x_1. $$ ] 因此后两项互为共轭，其实部相互抵消，于是： # [ $$ \operatorname{Re}(\lambda) = -\sqrt{\eta}|x_1|_C^2 \leq 0. $$ ] 若能证明 (x_1\neq 0)，则由于 (C) 正定，有： [ $$ |x_1|_C^2>0, $$ ] 从而： [ $$ \operatorname{Re}(\lambda)<0. $$ ] 如果 (x_1=0)，那么由上式可得： [ $$ \lambda=0, $$ ] 这与前面已经证明的 (\lambda\neq 0) 矛盾。因此 (x_1\neq0)，于是所有特征值实部严格为负。这样条件 (iv) 得到满足。 最后，对 ODE： [ $$ \dot\rho=h(\rho), $$ ] 其唯一平衡点为： [ $$ \rho^*=-G^{-1}g. $$ ] 并且： [ $$ \bar V(\rho)=\frac12(G\rho+g)^\top(G\rho+g) $$ ] 可以作为严格 Lyapunov 函数。因此该 ODE 有唯一全局渐近稳定平衡点。由 Borkar-Meyn 定理得到结论：GTD2 收敛到 TD fixed point。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- # 三、GTD2 证明的详细解释 ## 3.1 为什么 TD fixed point 等价于 ($-A\theta+b=0$)？ TD error 为： # [ $$ \delta = r+\gamma\theta^\top\phi'-\theta^\top\phi. $$ ] 于是： # [ $$ \delta\phi = r\phi + \phi(\gamma\phi'-\phi)^\top\theta. $$ ] 取期望： # [ $$ \mathbb E[\delta\phi] = \mathbb E[r\phi] + \mathbb E[\phi(\gamma\phi'-\phi)^\top]\theta. $$ ] 根据定义： [ $$ b=\mathbb E[r\phi], $$ ] [ $$ A=\mathbb E[\phi(\phi-\gamma\phi')^\top]. $$ ] 所以： # [ $$ \mathbb E[\phi(\gamma\phi'-\phi)^\top] = -A. $$ ] 因此： # [ $$ \mathbb E[\delta\phi] = b-A\theta. $$ ] TD fixed point 的条件是： [ $$ \mathbb E[\delta\phi]=0. $$ ] 所以： [ $$ b-A\theta=0, $$ ] 即： [ $$ -A\theta+b=0. $$ ] 若 (A) 非奇异，则唯一解为： [ $$ \theta^*=A^{-1}b. $$ ] 这说明整个收敛性证明的终点就是： [ $$ \theta_k\to A^{-1}b. $$ ] --- ## 3.2 为什么要把 (w) 缩放成 (d=w/\sqrt{\eta})？ GTD2 的两个步长满足： [ $$ \beta_k=\eta\alpha_k. $$ ] 也就是说，(w) 和 (\theta) 的更新在同一个时间尺度上，只是常数比例不同。为了把两个递推合并成一个统一的随机逼近系统，引入： [ $$ d_k=\frac{w_k}{\sqrt{\eta}}. $$ ] 这个缩放使得联合矩阵 (G) 呈现较对称的块结构： [ $$ G= \begin{pmatrix} -\sqrt{\eta}C & -A\\ A^\top & 0 \end{pmatrix}. $$ ] 这种结构便于证明 (G) 的特征值实部为负。若不做该缩放，矩阵块中的 (\eta) 会分布得更不整齐，稳定性证明更不简洁。 --- ## 3.3 合并系统的平衡点为什么对应 TD fixed point？ 联合均值系统为： [ $$ \dot \rho=G\rho+g. $$ ] 平衡点满足： [ $$ G\rho+g=0. $$ ] 展开： # [ $$ \begin{pmatrix} -\sqrt{\eta}C & -A\\ A^\top & 0 \end{pmatrix} \begin{pmatrix} d\\ \theta \end{pmatrix} + \begin{pmatrix} b\\ 0 \end{pmatrix} =0 $$ ] 得到： [ $$ -\sqrt{\eta}Cd-A\theta+b=0, $$ ] [ $$ A^\top d=0. $$ ] 因为 (A) 非奇异，所以： [ $$ A^\top d=0 \Rightarrow d=0. $$ ] 代入第一行： [ $$ -A\theta+b=0. $$ ] 所以： [ $$ \theta=A^{-1}b. $$ ] 因此，联合系统的唯一平衡点在 (\theta)-分量上正是 TD fixed point。 --- ## 3.4 ODE 方法在这里做什么？ 随机递推为： # [ $$ \rho_{k+1} = \rho_k+\alpha'_k(h(\rho_k)+M_{k+1}). $$ ] 其中： [ $$ h(\rho)=G\rho+g $$ ] 是平均漂移项， [ $$ M_{k+1} $$ ] 是均值为零的噪声项。 ODE 方法认为，当步长逐渐减小时，随机递推的长期轨迹近似跟随确定性 ODE： [ $$ \dot\rho=h(\rho)=G\rho+g. $$ ] 如果这个 ODE 有唯一全局渐近稳定平衡点，那么随机递推在标准噪声和步长条件下也会收敛到这个平衡点。Borkar-Meyn 定理正是用于把 ODE 的全局稳定性转化为随机逼近算法的几乎必然收敛性。([Faculty Websites](https://faculty.eng.ufl.edu/meyn/wp-content/uploads/sites/671/archive/spm_files/Papers_pdf/ode.pdf?utm_source=chatgpt.com "The O.D.E. Method for Convergence of Stochastic ...")) --- ## 3.5 为什么矩阵 (G) 稳定？ 要证明： [ $$ \dot\rho=G\rho $$ ] 的原点全局渐近稳定，需要证明 (G) 的所有特征值都在复平面左半部： [ $$ \operatorname{Re}(\lambda)<0. $$ ] 证明分两步。 第一步，证明 (G) 没有零特征值。由于： # [ $$ \det(G) = (\det C)^{-1}(\det A)^2\neq0, $$ ] 所以： [ $$ 0 $$ ] 不是 (G) 的特征值。 第二步，证明任意非零特征值 (\lambda) 都满足： [ $$ \operatorname{Re}(\lambda)<0. $$ ] 设对应特征向量为： [ $$ x=(x_1,x_2). $$ ] 由于： [ $$ x^*Gx=\lambda, $$ ] 并且交叉项： [ $$ -x_1^*Ax_2 + x_2^*A^\top x_1 $$ ] 的实部为 0，所以： # [ $$ \operatorname{Re}(\lambda) = -\sqrt{\eta}x_1^*Cx_1. $$ ] 因为 (C\succ0)，只要 (x_1\neq0)，就有： [ $$ x_1^*Cx_1>0. $$ ] 所以： [ $$ \operatorname{Re}(\lambda)<0. $$ ] 若 (x_1=0)，则由特征方程可推出 (\lambda=0)，与 (G) 非奇异矛盾。因此 (x_1\neq0)。于是所有特征值实部严格为负。 这一步是 GTD2 收敛证明中最关键的线性系统稳定性论证。 --- # 四、第 6 节：TDC 收敛性证明翻译 ## 定理 2：带梯度修正的 TD 的收敛性 考虑 TDC 的两个迭代式： # [ $$ \theta_{k+1} = \theta_k+\alpha_k\delta_k\phi_k - \alpha_k\gamma\phi'_k\phi_k^\top w_k, \tag{10} $$ ] # [ $$ w_{k+1} = w_k+\beta_k(\delta_k-\phi_k^\top w_k)\phi_k. \tag{9} $$ ] 步长满足： [ $$ \alpha_k,\beta_k>0, $$ ] # [ $$ \sum_{k=0}^{\infty}\alpha_k = \sum_{k=0}^{\infty}\beta_k = \infty, $$ ] [ $$ \sum_{k=0}^{\infty}\alpha_k^2<\infty, \qquad \sum_{k=0}^{\infty}\beta_k^2<\infty, $$ ] 并且： [ $$ \frac{\alpha_k}{\beta_k}\to0. $$ ] 进一步假设： [ $$ (\phi_k,r_k,\phi'_k) $$ ] 是 i.i.d. 序列，且二阶矩一致有界。定义： [ $$ A=\mathbb E[\phi_k(\phi_k-\gamma\phi'_k)^\top], $$ ] [ $$ b=\mathbb E[r_k\phi_k], $$ ] [ $$ C=\mathbb E[\phi_k\phi_k^\top]. $$ ] 假设 (A) 和 (C) 非奇异。那么： [ $$ \theta_k $$ ] 以概率 1 收敛到 TD fixed point。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- ## 证明翻译 该证明依赖于两个步长序列 ({\alpha_k}) 和 ({\beta_k}) 之间的双时间尺度差异。关于一般双时间尺度随机逼近递推的收敛分析，可参考 Borkar 的工作。式 (9) 和式 (10) 分别对应快递推和慢递推。原因是：在足够大的 (k) 之后，式 (9) 中的更新增量一致大于式 (10) 中的更新增量，因此 (w) 递推收敛得更快。 在快时间尺度，即对应 ({\beta_k}) 的时间尺度上，相关 ODE 系统为： [ $$ \dot\theta(t)=0, \tag{12} $$ ] # [ $$ \dot w(t) = \mathbb E[\delta_t\phi_t\mid\theta(t)]-Cw(t). \tag{13} $$ ] 式 (12) 表明，从快时间尺度观察时： [ $$ \theta(t)\equiv\theta $$ ] 是时间不变参数。事实上，式 (10) 可以重写为： # [ $$ \theta_{k+1} = \theta_k+\beta_k\xi(k), $$ ] 其中： # [ $$ \xi(k) = \frac{\alpha_k}{\beta_k} \left( \delta_k\phi_k-\gamma\phi'_k\phi_k^\top w_k \right). $$ ] 由于： [ $$ \frac{\alpha_k}{\beta_k}\to0, $$ ] 因此： [ $$ \xi(k)\to0 $$ ] 几乎必然成立。所以根据 Hirsch 引理，可以得到：在快时间尺度上， [ $$ |\theta_k-\theta|\to0 $$ ] 几乎必然成立，其中 (\theta) 由初始条件决定。 现在考虑 (w) 的递推式 (9)。定义噪声项： # [ $$ M_{k+1} = (\delta_k\phi_k-\phi_k\phi_k^\top w_k) - \mathbb E[(\delta_k\phi_k-\phi_k\phi_k^\top w_k)\mid F(k)], $$ ] 其中： # [ $$ F(k) = \sigma(w_l,\theta_l,l\leq k;\phi_s,\phi'_s,r_s,s0)，使得： [ $$ \mathbb E[|M_{k+1}|^2\mid F(k)] \leq c_1(1+|w_k|^2+|\theta_k|^2). $$ ] 现在考虑 ODE 对： [ $$ \dot\theta(t)=0, $$ ] # [ $$ \dot w(t) = \mathbb E[\delta_t\phi_t\mid\theta(t)]-Cw(t). $$ ] 由于快时间尺度上 (\theta(t)\equiv\theta)，所以 (w) 的 ODE 可以写成： # [ $$ \dot w(t) = \mathbb E[\delta\phi\mid\theta]-Cw(t). \tag{14} $$ ] 令： [ $$ h(w)=\mathbb E[\delta\phi\mid\theta]-Cw. $$ ] 对 ODE (14)，唯一全局渐近稳定平衡点为： # [ $$ w^* = C^{-1}\mathbb E[\delta\phi\mid\theta]. $$ ] 又定义： # [ $$ h_\infty(w) = \lim_{r\to\infty}\frac{h(rw)}{r}. $$ ] 则： [ $$ h_\infty(w)=-Cw. $$ ] 对于 ODE： [ $$ \dot w(t)=-Cw(t), $$ ] 由于 (C) 是正定矩阵，原点是全局渐近稳定平衡点。因此 Borkar-Meyn 定理条件得到满足，可以推出： [ $$ |w_k-w^*|\to0 $$ ] 几乎必然成立。 现在考虑慢时间尺度递推式 (10)。根据上面的结论，可以把 (w_k) 替换为： [ $$ C^{-1}\mathbb E[\delta_k\phi_k\mid\theta_k]. $$ ] 于是式 (10) 可以写成： # [ $$ \theta_{k+1} = \theta_k + \alpha_k\delta_k\phi_k - \alpha_k\gamma\phi'_k\phi_k^\top C^{-1} \mathbb E[\delta_k\phi_k\mid\theta_k]. \tag{15} $$ ] 令： # [ G(k) \sigma(\theta_l,l\leq k;\phi_s,\phi'_s,r_s,s0)，使得： [ $$ \mathbb E[|Z_{k+1}|^2\mid G(k)] \leq c_2(1+|\theta_k|^2). $$ ] 现在考虑与式 (10) 相关的 ODE： # [ $$ \dot\theta(t) = \left( I-\mathbb E[\gamma\phi'\phi^\top]C^{-1} \right) \mathbb E[\delta\phi\mid\theta(t)]. \tag{16} $$ ] 令 (\bar h(\theta(t))) 表示该 ODE 的驱动向量场。注意： # [ $$ \bar h(\theta(t)) = \left( I-\mathbb E[\gamma\phi'\phi^\top]C^{-1} \right) \mathbb E[\delta\phi\mid\theta(t)]. $$ ] 进一步有： # [ $$ \bar h(\theta(t)) = \left( C-\mathbb E[\gamma\phi'\phi^\top] \right) C^{-1} \mathbb E[\delta\phi\mid\theta(t)]. $$ ] 因为： [ $$ C=\mathbb E[\phi\phi^\top], $$ ] 所以： # [ $$ C-\mathbb E[\gamma\phi'\phi^\top] = \mathbb E[\phi\phi^\top] - \mathbb E[\gamma\phi'\phi^\top] = A^\top. $$ ] 并且： # [ $$ \mathbb E[\delta\phi\mid\theta(t)] = -A\theta(t)+b. $$ ] 因此： # [ $$ \bar h(\theta(t)) = A^\top C^{-1}(-A\theta(t)+b). $$ ] 现在可以看出： [ $$ \theta^*=A^{-1}b $$ ] 是 ODE (16) 的唯一全局渐近稳定平衡点。 定义： # [ $$ \bar h_\infty(\theta) = \lim_{r\to\infty}\frac{\bar h(r\theta)}{r}. $$ ] 则： # [ $$ \bar h_\infty(\theta) = -A^\top C^{-1}A\theta. $$ ] 考虑 ODE： # [ $$ \dot\theta(t) = -A^\top C^{-1}A\theta(t). \tag{17} $$ ] 因为 (C^{-1}) 正定，且 (A) 满秩，所以： [ $$ A^\top C^{-1}A $$ ] 也是正定矩阵。因此 ODE (17) 的原点是唯一全局渐近稳定平衡点。于是 Borkar-Meyn 定理条件再次得到满足，结论成立。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- # 五、TDC 证明的详细解释 ## 5.1 为什么 TDC 需要双时间尺度？ TDC 的两个递推是： # [ $$ w_{k+1} = w_k+\beta_k(\delta_k-\phi_k^\top w_k)\phi_k, $$ ] # [ $$ \theta_{k+1} = \theta_k+\alpha_k\delta_k\phi_k - \alpha_k\gamma\phi'_k\phi_k^\top w_k. $$ ] 其中 (w) 的作用是估计： # [ $$ w^*(\theta) = C^{-1}\mathbb E[\delta\phi\mid\theta]. $$ ] 如果 (w) 估计不准，那么 (\theta) 的梯度修正项就不准。因此证明要求： [ $$ w $$ ] 比： [ $$ \theta $$ ] 更快收敛。 这由条件： [ $$ \frac{\alpha_k}{\beta_k}\to0 $$ ] 保证。该条件表示： [ $$ \alpha_k $$ ] 相对于： [ $$ \beta_k $$ ] 趋于更小，所以 (\theta) 更新更慢，(w) 更新更快。双时间尺度随机逼近理论正是分析这种快慢变量耦合递推的标准工具。([Faculty Websites](https://faculty.eng.ufl.edu/meyn/wp-content/uploads/sites/671/archive/spm_files/Papers_pdf/ode.pdf?utm_source=chatgpt.com "The O.D.E. Method for Convergence of Stochastic ...")) --- ## 5.2 快时间尺度：(\theta) 固定，(w) 收敛 快时间尺度上： [ $$ \theta(t)\equiv\theta. $$ ] 于是 (w) 的平均动力学是： # [ $$ \dot w = \mathbb E[\delta\phi\mid\theta]-Cw. $$ ] 这是一个线性 ODE。其平衡点满足： [ $$ 0= \mathbb E[\delta\phi\mid\theta]-Cw. $$ ] 因此： # [ $$ w^*(\theta) = C^{-1}\mathbb E[\delta\phi\mid\theta]. $$ ] 由于： [ $$ C=\mathbb E[\phi\phi^\top] $$ ] 半正定且非奇异，所以 (C) 正定，(-C) 是稳定矩阵。因此： [ $$ w_k\to w^*(\theta_k) $$ ] 几乎必然成立。 --- ## 5.3 慢时间尺度：把 (w) 替换为稳定值 慢时间尺度上，由于 (w) 已经快速跟踪： [ $$ w^*(\theta_k)=C^{-1}\mathbb E[\delta\phi\mid\theta_k], $$ ] 所以 TDC 的 (\theta) 更新可视为： # [ $$ \theta_{k+1} = \theta_k + \alpha_k \left[ \delta_k\phi_k - \gamma\phi'_k\phi_k^\top C^{-1} \mathbb E[\delta\phi\mid\theta_k] \right]. $$ ] 其平均 ODE 是： # [ $$ \dot\theta = \left( I-\mathbb E[\gamma\phi'\phi^\top]C^{-1} \right) \mathbb E[\delta\phi\mid\theta]. $$ ] 下面化简这个向量场。 首先： # [ $$ \mathbb E[\delta\phi\mid\theta] = b-A\theta = -A\theta+b. $$ ] 其次： # [ $$ A = \mathbb E[\phi(\phi-\gamma\phi')^\top]. $$ ] 所以： # [ $$ A^\top = \mathbb E[(\phi-\gamma\phi')\phi^\top] = \mathbb E[\phi\phi^\top] - \mathbb E[\gamma\phi'\phi^\top]. $$ ] 也就是： # [ $$ A^\top = C-\mathbb E[\gamma\phi'\phi^\top]. $$ ] 因此： [ $$ \left( I-\mathbb E[\gamma\phi'\phi^\top]C^{-1} \right) \mathbb E[\delta\phi\mid\theta] $$ ] # [ $$ \left( C-\mathbb E[\gamma\phi'\phi^\top] \right) C^{-1} \mathbb E[\delta\phi\mid\theta] $$ ] # [ $$ A^\top C^{-1}(-A\theta+b). $$ ] 于是慢 ODE 是： # [ $$ \dot\theta = A^\top C^{-1}(b-A\theta). $$ ] 这正是 MSPBE 梯度流： [ $$ -\frac12\nabla \operatorname{MSPBE}(\theta). $$ ] --- ## 5.4 为什么 ($\theta^*=A^{-1}b$) 全局稳定？ 平衡点满足： [ $$ A^\top C^{-1}(b-A\theta)=0. $$ ] 由于 (A) 非奇异，(C^{-1}) 正定，所以： [ $$ b-A\theta=0. $$ ] 于是： [ $$ \theta^*=A^{-1}b. $$ ] 令误差： [ $$ e=\theta-\theta^*. $$ ] 因为： # [ $$ b-A\theta = -A(\theta-\theta^*) = -Ae. $$ ] 所以： # [ $$ \dot e = -A^\top C^{-1}Ae. $$ ] 矩阵： [ $$ A^\top C^{-1}A $$ ] 正定。证明如下：对任意非零向量 (x)， # [ $$ x^\top A^\top C^{-1}Ax = (Ax)^\top C^{-1}(Ax). $$ ] 因为 (A) 非奇异，所以： [ $$ x\neq0 \Rightarrow Ax\neq0. $$ ] 又因为 (C^{-1}\succ0)，所以： [ $$ (Ax)^\top C^{-1}(Ax)>0. $$ ] 因此： [ $$ A^\top C^{-1}A\succ0. $$ ] 于是 ODE： [ $$ \dot e=-A^\top C^{-1}Ae $$ ] 全局渐近稳定。Lyapunov 函数可取： [ $$ L(e)=\frac12 e^\top e. $$ ] 则： # [ $$ \dot L(e) = e^\top\dot e = -e^\top A^\top C^{-1}Ae<0 $$ ] 对所有 (e\neq0) 成立。因此： [ $$ e(t)\to0, $$ ] 也就是： [ $$ \theta(t)\to\theta^*. $$ ] 随机逼近定理据此推出： [ $$ \theta_k\to A^{-1}b $$ ] 几乎必然成立。 --- # 六、GTD2 与 TDC 收敛证明的比较 | 项目 | GTD2 | TDC | | ------ | ------------------------------- | ----------------------------------------------------------- | | 步长关系 | ($\beta_k=\eta\alpha_k$) | ($\alpha_k/\beta_k\to0$) | | 时间尺度 | 单时间尺度 | 双时间尺度 | | 证明策略 | 把 ($(w,\theta)$) 合并为 ($2n$) 维系统 | 先证明 ($w$) 快收敛，再证明 ($\theta$) 慢收敛 | | 平均 ODE | ($\dot\rho=G\rho+g$) | 快：($\dot w=m-Cw$)；慢：($\dot\theta=A^\top C^{-1}(b-A\theta)$) | | 稳定性关键 | (G) 的全部特征值实部为负 | ($C\succ0$)，且 ($A^\top C^{-1}A\succ0$) | | 极限点 | ($\theta^*=A^{-1}b)$ | ($\theta^*=A^{-1}b$) | | 收敛目标 | TD fixed point | TD fixed point | --- # 七、几个关键假设的严格含义 ## 7.1 (A) 非奇异 [ $$ A=\mathbb E[\phi(\phi-\gamma\phi')^\top]. $$ ] (A) 非奇异保证： [ $$ -A\theta+b=0 $$ ] 有唯一解： [ $$ \theta^*=A^{-1}b. $$ ] 如果 (A) 奇异，TD fixed point 可能不唯一，或者参数空间中存在不可识别方向。此时上述全局收敛到唯一点的结论不再直接成立。 --- ## 7.2 (C) 非奇异 [ $$ C=\mathbb E[\phi\phi^\top]. $$ ] 由于： [ $$ C $$ ] 是二阶矩矩阵，它天然半正定。若非奇异，则： [ $$ C\succ0. $$ ] 该条件保证： [ $$ C^{-1} $$ ] 存在，也保证 (w) 的平衡点： [ $$ w^*(\theta)=C^{-1}\mathbb E[\delta\phi\mid\theta] $$ ] 唯一。同时在 TDC 中保证： [ $$ A^\top C^{-1}A $$ ] 正定。 --- ## 7.3 二阶矩一致有界 该条件用于控制噪声项： [ $$ M_{k+1},\quad Z_{k+1}. $$ ] 随机逼近收敛定理通常要求噪声是 martingale difference，并且条件二阶矩至多线性增长： [ $$ \mathbb E[|M_{k+1}|^2\mid F_k] \leq c(1+|\rho_k|^2). $$ ] 二阶矩一致有界正是为了确保随机扰动不会破坏 ODE 跟踪性质。 --- ## 7.4 步长条件 对 GTD2： [ $$ \sum_k\alpha_k=\infty, \qquad \sum_k\alpha_k^2<\infty. $$ ] 对 TDC： [ $$ \sum_k\alpha_k=\sum_k\beta_k=\infty, $$ ] [ $$ \sum_k\alpha_k^2<\infty, \qquad \sum_k\beta_k^2<\infty. $$ ] 这些是 Robbins-Monro 型条件。 [ $$ \sum_k\alpha_k=\infty $$ ] 保证总移动量足够大，不会过早停止； [ $$ \sum_k\alpha_k^2<\infty $$ ] 保证随机噪声的累计影响有限。 --- # 八、最终结论 第 5 节和第 6 节分别证明： [ $$ \boxed{ \text{GTD2 收敛到 TD fixed point} } $$ ] [ $$ \boxed{ \text{TDC 收敛到 TD fixed point} } $$ ] 二者的极限点相同： [ $$ \boxed{ \theta^*=A^{-1}b } $$ ] 其中： [ $$ A=\mathbb E[\phi(\phi-\gamma\phi')^\top], \qquad b=\mathbb E[r\phi]. $$ ] 这个点满足： [ $$ -A\theta^*+b=0, $$ ] 等价于： [ $$ \mathbb E[\delta\phi]=0. $$ ] 也等价于 projected Bellman equation： [ $$ \boxed{ V_{\theta^*}=\Pi T V_{\theta^*}. } $$ ] 所以 GTD2 和 TDC 的收敛对象不是 MSE 最小点，也不是 MSBE 最小点，而是 **TD fixed point**，即 MSPBE 的零点。关键技术路线是随机逼近的 ODE 方法：GTD2 通过证明联合线性 ODE 的矩阵 ($G$) 是稳定的；TDC 通过双时间尺度先让 ($w$) 跟踪 ($C^{-1}\mathbb E[\delta\phi]$)，再让 ($\theta$) 沿 MSPBE 梯度流收敛。、 --- ## 1. episode 是什么？ 在强化学习中，**episode** 通常译为： [ $$ \text{回合} $$ ] 或： [ $$ \text{一条完整轨迹} $$ ] 更严格地说，一个 episode 是从环境初始状态开始，到终止状态结束的一段完整交互序列。episodic task 中，agent 与环境的交互会自然分解成一个个 episode；每个 episode 结束后，环境会 reset 到新的初始状态。这个定义与强化学习教材和综述中的用法一致：episodic task 有清楚的起点和终止状态，目标是在每个 episode 内最大化累计回报。([Stanford University](https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf?utm_source=chatgpt.com "Reinforcement Learning: An Introduction")) 一个 episode 可以写成： [ $$ S_0,A_0,R_1,S_1,A_1,R_2,\dots,S_T $$ ] 其中： [ $$ S_0 $$ ] 是初始状态； [ $$ S_T $$ ] 是终止状态； [ $$ T $$ ] 是该 episode 的长度，可能每次不同。 对应的 episode return 是： # [ $$ G_0 = R_1+\gamma R_2+\gamma^2R_3+\cdots+\gamma^{T-1}R_T. $$ ] 如果是无折扣 episodic task，则： [ $$ \gamma=1, $$ ] 于是： # [ $$ G_0 = R_1+R_2+\cdots+R_T. $$ ] 在论文里的 random-walk 问题中，一个 episode 是： [ $$ \text{从中间状态开始} \rightarrow \text{随机左右移动若干步} \rightarrow \text{到达左端或右端吸收终止状态} $$ ] 这整个过程就是一个 episode。论文明确说 random-walk 的 episodes 从五个状态的中间状态开始，然后随机转移到相邻状态，直到到达终止状态。([Stanford University](https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf?utm_source=chatgpt.com "Reinforcement Learning: An Introduction")) --- ## 2. run 是什么？ **run** 通常译为： [ $$ \text{一次独立运行} $$ ] 或： [ $$ \text{一次实验重复} $$ ] 一个 run 不是一个 episode，而是一次完整的训练/评估过程。它通常包含很多 episodes，并且有自己的随机种子、初始化、采样轨迹和训练过程。 例如论文说： > averaged over 100 independent runs 意思是：同一个算法、同一组超参数设置，会从头到尾独立重复 100 次。每一次重复就是一个 run。每个 run 内部又包含 100–500 个 episodes。论文在小规模实验中就是每个算法和参数设置运行 100–500 个 episode，然后把结果在 100 次 independent runs 上平均。([Stanford University](https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf?utm_source=chatgpt.com "Reinforcement Learning: An Introduction")) 可以写成： # [ $$ \text{one run} = \text{初始化一次参数} + \text{训练若干 episodes} + \text{记录指标曲线}. ] $$ 如果做 100 个 runs，就是： [ $$ \text{repeat the whole experiment 100 times independently}. $$ ] --- ## 3. episode 和 run 的层级关系 二者关系是： [ $$ \boxed{ \text{一个 run 包含多个 episodes。} } $$ ] 例如论文中的小规模实验可以理解为： [ $$ \text{算法 = TDC} $$ ] [ $$ \text{步长 } \alpha=0.1,\quad \eta=1 $$ ] 对这一组设置： [ $$ \text{Run 1: 训练 500 episodes} $$ ] [ $$ \text{Run 2: 训练 500 episodes} $$ ] [ $$ \vdots $$ ] [ $$ \text{Run 100: 训练 500 episodes} $$ ] 然后对第 (e) 个 episode 结束后的指标取平均： # [ $$ \overline{\operatorname{MSPBE}}_e = \frac1{100} \sum_{i=1}^{100} \operatorname{MSPBE}_{i,e}. $$ ] 其中： [ $$ i $$ ] 表示第几个 run； [ $$ e $$ ] 表示该 run 内第几个 episode。 所以： [ $$ \text{episode 是时间/训练进度单位} $$ ] [ $$ \text{run 是独立实验重复单位} $$ ] --- ## 4. 为什么需要多个 runs？ 强化学习实验中存在大量随机性，例如： [ $$ \text{初始状态随机} $$ ] [ $$ \text{动作选择随机} $$ ] [ $$ \text{状态转移随机} $$ ] [ $$ \text{奖励随机} $$ ] [ $$ \text{参数初始化随机} $$ ] [ $$ \text{样本轨迹随机} $$ ] 单个 run 的学习曲线可能只是某一次随机采样的结果，不能可靠代表算法平均性能。因此通常需要多个 independent runs，然后报告平均值和标准误差。论文中小规模实验在 100 个 independent runs 上平均，Computer Go 实验在 40 runs 上平均；这正是为了减少单次随机运行带来的偶然性。([Stanford University](https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf?utm_source=chatgpt.com "Reinforcement Learning: An Introduction")) --- ## 5. 用论文中的例子具体区分 ### random-walk 中的 episode 一次 episode： [ $$ S_0=\text{center state} $$ ] 然后随机左右移动： [ $$ S_0\to S_1\to S_2\to\cdots\to S_T $$ ] 直到： [ $$ S_T=\text{left terminal} $$ ] 或： [ $$ S_T=\text{right terminal}. $$ ] 如果进入右终止状态，最后奖励为： [ $$ +1. $$ ] 如果进入左终止状态，奖励为： [ $$ 0. $$ ] 这一整条轨迹就是一个 episode。 ### random-walk 中的 run 一次 run： [ $$ \theta_0=0,\quad w_0=0 $$ ] 然后连续训练，比如： [ $$ 500 \text{ episodes}. $$ ] 每个 episode 后记录： [ $$ \sqrt{\operatorname{MSPBE}}, \sqrt{\operatorname{MSBE}}, \sqrt{\operatorname{NEU}}, \sqrt{\operatorname{MSE}}. $$ ] 这 500 个 episodes 组成一次 run 的学习曲线。 重复 100 次独立 run 后，再取平均曲线。 --- ## 6. 在 Computer Go 实验中的含义 论文中的 Go 实验说： > Training then proceeded for 1000 complete games, after which (\theta) was frozen and another 1000 games run to compute an estimate of an objective function. 这里的一个 complete game 就可以看作一个 episode： # [ $$ \text{一局 9x9 Go self-play} = \text{一个 episode}. $$ ] 一次 run 是： $$ \text{随机初始化 }\theta $$ ] [ $$ \rightarrow \text{训练 1000 games} $$ ] [ $$ \rightarrow \text{冻结 }\theta $$ ] [ $$ \rightarrow \text{再运行 1000 games 估计 NEU} $$ ] 这整个流程是一 run。论文把这个流程重复 40 次，然后平均得到 Figure 4。([Stanford University](https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf?utm_source=chatgpt.com "Reinforcement Learning: An Introduction")) --- ## 7. 最核心区别 |概念|中文|含义|在论文中的例子| |---|---|---|---| |episode|回合 / 完整轨迹|从初始状态到终止状态的一次环境交互|random-walk 从中间状态走到终止状态；Go 的一局完整游戏| |run|一次独立运行 / 实验重复|从初始化开始，训练若干 episodes，并记录结果的一整次实验|一个算法在某组步长下训练 100–500 episodes；重复 100 runs 后平均| 一句话总结： [ $$ \boxed{ \text{episode 是一条轨迹；run 是由很多 episode 构成的一次完整实验重复。} } $$ ] 在论文这句： > run for 100–500 episodes ... averaged over 100 independent runs 中，准确含义是： [ $$ \boxed{ \text{每次独立实验训练 100–500 个 episodes；这样的独立实验重复 100 次后取平均。} } $$ ] --- # 文献总结：Fast Gradient-Descent Methods for Temporal-Difference Learning with Linear Function Approximation ## 1. 文献定位 这篇文献提出了两个新的梯度型时序差分学习算法： [ $$ \text{GTD2} $$ ] 和 [ $$ \text{TDC / TD with Gradient Correction}. $$ ] 核心目标是解决强化学习中一个长期困难问题： [ $$ \boxed{ \text{off-policy learning} + \text{bootstrapping} + \text{linear function approximation} } $$ ] 组合下，传统 TD 方法可能发散，而二阶稳定方法又复杂度过高。论文试图构造一种同时具备以下性质的算法： [ $$ O(n)\text{ 时间复杂度} $$ ] [ $$ O(n)\text{ 内存复杂度} $$ ] [ $$ \text{off-policy 收敛保证} $$ ] [ $$ \text{线性函数近似下可用} $$ ] [ $$ \text{速度接近传统 TD}. $$ ] 其中 (n) 是特征维度。论文明确指出，GTD2 和 TDC 都显著快于此前的 GTD；TDC 在 on-policy 问题中速度接近 conventional linear TD。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- # 2. 研究动机 ## 2.1 传统 TD 方法的根本问题 传统 TD、Sarsa、Q-learning 等算法虽然形式简单、计算高效，但并不是真正的梯度下降方法。以线性 TD(0) 为例： [ $$ V_\theta(s)=\theta^\top\phi_s, $$ ] # [ $$ \delta_t = r_{t+1} + \gamma\theta^\top\phi_{t+1} - \theta^\top\phi_t. $$ ] 普通 TD 更新为： # [ $$ \theta_{t+1} = \theta_t+\alpha_t\delta_t\phi_t. $$ ] 这个更新只对当前估计项 ($V_\theta(s_t)$) 求梯度，而把 bootstrap target： [ $$ r_{t+1}+\gamma V_\theta(s_{t+1}) $$ ] 当作常数。因此它是 **semi-gradient method**，不是完整梯度下降。 在 on-policy + 线性函数近似条件下，传统 TD 通常具有良好收敛性质；但在 off-policy 设置中，采样分布 (d) 与目标策略诱导的转移矩阵 (P) 可以不匹配，传统 TD 的稳定性可能丧失。Baird 反例正是展示 off-policy TD 可发散的经典例子。论文将寻找一种适用于大规模线性函数近似、off-policy、且复杂度为 (O(n)) 的 TD 算法，称为强化学习中持续十余年的重要开放问题。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- ## 2.2 既有方法的不足 文献中比较了几类已有方法： ### 传统 TD 优点： [ $$ O(n)\text{ 复杂度，速度快} $$ ] 缺点： [ $$ \text{off-policy + 函数近似下可能发散} $$ ] ### LSTD 等二阶方法 优点： [ $$ \text{稳定性较强} $$ ] 缺点： [ $$ O(n^2)\text{ 计算或内存复杂度} $$ ] 当特征数达到几十万或百万时，二阶方法不可行。 ### 原始 GTD 优点： [ $$ O(n)\text{ 复杂度} $$ ] [ $$ \text{off-policy 线性函数近似下可收敛} $$ ] 缺点： [ $$ \text{收敛速度慢} $$ ] 论文正是在这一背景下提出 GTD2 和 TDC：目标不是只获得理论收敛性，而是同时提升实际学习速度。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- # 3. 基本问题设置 论文考虑固定策略下的 policy evaluation。固定 MDP 和固定策略共同诱导一个 Markov chain。状态集合为： [ $$ \mathcal S={1,2,\dots,N}. $$ ] 状态转移矩阵为： [ $$ P. $$ ] 目标是学习状态价值函数： # [ $$ V(s) = \mathbb E \left[ \sum_{t=0}^{\infty}\gamma^t r_{t+1} \mid s_0=s \right]. $$ ] 采用线性函数近似： [ $$ V_\theta(s)=\theta^\top\phi_s. $$ ] 令特征矩阵为： [ $$ \Phi= \begin{bmatrix} \phi_1^\top\ \phi_2^\top\ \vdots\ \phi_N^\top \end{bmatrix}. $$ ] 则： [ $$ V_\theta=\Phi\theta. $$ ] 所有可表示价值函数构成线性子空间： [ $$ \mathcal V=\{\Phi\theta:\theta\in\mathbb R^n\}. $$ ] 论文考虑一种一般采样设置：每个 transition 的起始状态独立地从分布 (d) 中采样，随后根据目标转移矩阵 (P) 产生下一状态和奖励。该设置允许 (d) 与 (P) 无关，因此涵盖 off-policy learning。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- # 4. 目标函数：MSE、MSBE、MSPBE、NEU 文献的关键理论贡献之一是明确区分多个可能的目标函数。 --- ## 4.1 MSE：真实值函数误差 # [ $$ \operatorname{MSE}(\theta) = |V_\theta-V|_D^2 = \sum_s d_s(V_\theta(s)-V(s))^2. $$ ] 其中： [ $$ D=\operatorname{diag}(d_1,\dots,d_N). $$ ] MSE 是最直观的监督学习式目标，但真实 (V) 通常未知，因此 TD 方法不能直接最小化它。 --- ## 4.2 MSBE：未投影 Bellman 误差 真实价值函数满足 Bellman 方程： [ $$ V=TV=R+\gamma PV. $$ ] MSBE 定义为： # [ $$ \operatorname{MSBE}(\theta) = |V_\theta-TV_\theta|_D^2. $$ ] MSBE 衡量当前近似函数是否满足 Bellman 方程。表面上看，这是一个自然目标；但在函数近似下存在关键问题： [ $$ V_\theta\in\mathcal V, $$ ] 但通常： [ $$ TV_\theta\notin\mathcal V. $$ ] Bellman 算子由环境动态决定，不受函数近似空间限制。因此，直接追逐 (TV_\theta) 可能要求函数近似器拟合不可表示的方向。论文指出，TD、LSTD、GTD 等算法并不收敛到 MSBE 最小点，而是收敛到投影 Bellman 方程的不动点。([ResearchGate](https://www.researchgate.net/publication/221344791_Fast_gradient-descent_methods_for_temporal-difference_learning_with_linear_function_approximation?utm_source=chatgpt.com "(PDF) Fast gradient-descent methods for temporal- ...")) --- ## 4.3 投影算子与 TD fixed point 定义投影算子： # [ $$ \Pi v = \Phi\theta^*, $$ ] 其中： # [ $$ \theta^* = \arg\min_\theta |\Phi\theta-v|_D^2. $$ ] 在线性函数近似下： # [ $$ \Pi = \Phi(\Phi^\top D\Phi)^{-1}\Phi^\top D. $$ ] TD 类算法的自然 fixed point 是： [ $$ V_\theta=\Pi TV_\theta. $$ ] 这称为 **projected Bellman equation**。参数形式下，它等价于： [ $$ \mathbb E[\delta\phi]=0. $$ ] 进一步可写成： [ $$ -A\theta+b=0, $$ ] 其中： [ $$ A=\mathbb E[\phi(\phi-\gamma\phi')^\top], $$ ] [ $$ b=\mathbb E[r\phi]. $$ ] 因此 TD fixed point 为： [ $$ \theta^*=A^{-1}b. $$ ] --- ## 4.4 MSPBE：投影 Bellman 误差 论文选择的核心目标函数是： # [ $$ \operatorname{MSPBE}(\theta) = |V_\theta-\Pi TV_\theta|_D^2. $$ ] 它衡量当前近似值函数距离 projected Bellman update 的距离。 利用： # [ $$ \mathbb E[\delta\phi] = \Phi^\top D(TV_\theta-V_\theta), $$ ] [ $$ C=\mathbb E[\phi\phi^\top]=\Phi^\top D\Phi, $$ ] 可得： # [ $$ \operatorname{MSPBE}(\theta) = \mathbb E[\delta\phi]^\top \mathbb E[\phi\phi^\top]^{-1} \mathbb E[\delta\phi]. $$ ] 即： # [ $$ \operatorname{MSPBE}(\theta) = m(\theta)^\top C^{-1}m(\theta), $$ ] 其中： [ $$ m(\theta)=\mathbb E[\delta\phi]. $$ ] MSPBE 的优点是：它直接对应 TD fixed point，而不是未投影 Bellman residual。论文明确把 GTD2 和 TDC 推导为 MSPBE 上的随机梯度下降型算法。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- ## 4.5 NEU：期望 TD 更新范数 原始 GTD 使用的目标是： # [ $$ \operatorname{NEU}(\theta) = \mathbb E[\delta\phi]^\top\mathbb E[\delta\phi]. $$ ] 即： [ $$ \operatorname{NEU}(\theta)=|m(\theta)|_2^2. $$ ] MSPBE 与 NEU 的区别只在于： [ $$ \operatorname{NEU}: \quad m^\top I m, $$ ] [ $$ \operatorname{MSPBE}: \quad m^\top C^{-1}m. $$ ] 其中 (C^{-1}) 起到特征尺度和相关性的校正作用。因此 MSPBE 比 NEU 更符合投影几何。论文认为这也是 GTD2 比原始 GTD 快的重要原因。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- # 5. 为什么 MSBE 不够：backward bootstrapping 例子 论文用 Figure 2 说明 MSBE 在函数近似下可能产生不合适解。 基本例子中： [ $$ A\to B\to \text{reward }1, $$ ] [ $$ A\to C\to \text{reward }0, $$ ] 且 (A) 以相等概率转移到 (B) 或 (C)，(\gamma=1)。 真实值为： [ $$ V(A)=\frac12,\quad V(B)=1,\quad V(C)=0. $$ ] Residual-gradient 或平方 TD error 最小化可能给出： [ $$ V(B)=\frac34,\quad V(C)=\frac14. $$ ] 原因是该解把 TD error 分摊到多条 transition 上，从而降低总体平方误差，但使后继状态 (B,C) 的价值被前驱状态 (A) 反向影响。这种现象称为 **backwards bootstrapping**。 进一步，如果把 (A) 拆成 (A_1,A_2)，并令二者共享同一特征表示，则函数近似器必须赋予二者相同价值。此时 MSBE 也可能偏向 (\frac34,\frac14) 解；只有 MSPBE 会把最优点放在 (B=1,C=0)。这说明 MSBE 会消耗函数近似能力去拟合不可表示的 Bellman error，而 MSPBE 会考虑投影后实际可表示的误差。([ResearchGate](https://www.researchgate.net/publication/221344791_Fast_gradient-descent_methods_for_temporal-difference_learning_with_linear_function_approximation?utm_source=chatgpt.com "(PDF) Fast gradient-descent methods for temporal- ...")) --- # 6. GTD2 与 TDC 的推导 核心等式为： # [ $$ \operatorname{MSPBE}(\theta) = m(\theta)^\top C^{-1}m(\theta), $$ ] 其中： [ $$ m(\theta)=\mathbb E[\delta\phi], \quad C=\mathbb E[\phi\phi^\top]. $$ ] 显式计算 (C^{-1}) 需要二阶矩阵操作，复杂度可能达到 (O(n^2))。论文引入辅助参数： [ $$ w\in\mathbb R^n, $$ ] 用来跟踪： # [ $$ w\approx C^{-1}m(\theta) = \mathbb E[\phi\phi^\top]^{-1}\mathbb E[\delta\phi]. $$ ] 辅助变量更新为： # [ $$ w_{k+1} = w_k+\beta_k(\delta_k-\phi_k^\top w_k)\phi_k. $$ ] 在期望意义下： # [ $$ \mathbb E[\Delta w] = \beta(m-Cw). $$ ] 平衡点满足： [ $$ Cw=m, $$ ] 因此： [ $$ w=C^{-1}m. $$ ] --- ## 6.1 GTD2 MSPBE 的负梯度可写成： # [ $$ -\frac12\nabla\operatorname{MSPBE}(\theta) = \mathbb E[(\phi-\gamma\phi')\phi^\top]C^{-1}m. $$ ] 用 (w\approx C^{-1}m) 代替，得到： [ $$ -\frac12\nabla\operatorname{MSPBE}(\theta) \approx \mathbb E[(\phi-\gamma\phi')\phi^\top]w. $$ ] 单样本采样得到 GTD2： # [ $$ \theta_{k+1} = \theta_k + \alpha_k(\phi_k-\gamma\phi'_k)(\phi_k^\top w_k), $$ ] # [ $$ w_{k+1} = w_k+\beta_k(\delta_k-\phi_k^\top w_k)\phi_k. $$ ] GTD2 直接采样 MSPBE 梯度表达式。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- ## 6.2 TDC 对同一梯度表达式作另一种分解： # [ $$ -\frac12\nabla\operatorname{MSPBE}(\theta) = \mathbb E[\delta\phi] - \gamma\mathbb E[\phi'\phi^\top]C^{-1}m. $$ ] 用 ($w\approx C^{-1}m$) 代替： ## [ $$ -\frac12\nabla\operatorname{MSPBE}(\theta) \approx \mathbb E[\delta\phi] - \gamma\mathbb E[\phi'\phi^\top]w. $$ ] 单样本更新为： # [ $$ \theta_{k+1} = \theta_k+\alpha_k\delta_k\phi_k - \alpha_k\gamma\phi'_k(\phi_k^\top w_k), $$ ] # [ $$ w_{k+1} = w_k+\beta_k(\delta_k-\phi_k^\top w_k)\phi_k. $$ ] 第一项： [ $$ \alpha_k\delta_k\phi_k $$ ] 正是传统 TD 更新；第二项： [ $$ -\alpha_k\gamma\phi'_k(\phi_k^\top w_k) $$ ] 是梯度修正项。因此： # [ $$ \boxed{ \text{TDC} = \text{传统 TD} + \text{gradient correction}. } $$ ] 这也是 TDC 在实验中速度接近传统 TD 的主要机制。([ACM Digital Library](https://dl.acm.org/doi/10.1145/1553374.1553501?utm_source=chatgpt.com "Fast gradient-descent methods for temporal-difference ...")) --- # 7. 收敛性证明 论文分别证明 GTD2 和 TDC 在标准随机逼近假设下几乎必然收敛到 TD fixed point。 --- ## 7.1 GTD2 的收敛证明 GTD2 使用单时间尺度步长： [ $$ \beta_k=\eta\alpha_k,\quad \eta>0. $$ ] 把： [ $$ w_k $$ ] 缩放为： [ $$ d_k=\frac{w_k}{\sqrt{\eta}}, $$ ] 并构造联合变量： [ $$ \rho_k= \begin{bmatrix} d_k\ \theta_k \end{bmatrix}. $$ ] 两个递推可写成一个线性随机逼近系统： # [ $$ \rho_{k+1} = \rho_k+\alpha'_k(h(\rho_k)+M_{k+1}), $$ ] 其中： [ $$ h(\rho)=G\rho+g, $$ ] [ $$ G= \begin{pmatrix} -\sqrt{\eta}C & -A\\ A^\top & 0 \end{pmatrix}, \quad g= \begin{pmatrix} b\\ 0 \end{pmatrix}. $$ ] 证明的关键是说明 (G) 的所有特征值实部严格为负。过程如下： 1. 利用分块矩阵行列式公式证明 (G) 非奇异： # [ $$ \det(G)= (\det C)^{-1}(\det A)^2\neq0. $$ ] 2. 对任意特征值 (\lambda) 和特征向量 (x=(x_1,x_2))，证明： # [ $$ \operatorname{Re}(\lambda) = -\sqrt{\eta}x_1^*Cx_1<0. $$ ] 由于 (C\succ0)，且 (x_1\neq0)，因此实部严格为负。 于是 ODE： [ $$ \dot\rho=G\rho+g $$ ] 有唯一全局渐近稳定平衡点。Borkar-Meyn 随机逼近定理推出： [ $$ \theta_k\to A^{-1}b \quad \text{a.s.} $$ ] 即 GTD2 几乎必然收敛到 TD fixed point。论文明确说明 GTD2 的证明采用 ODE approach 和 Borkar-Meyn 定理。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- ## 7.2 TDC 的收敛证明 TDC 使用双时间尺度条件： [ $$ \frac{\alpha_k}{\beta_k}\to0. $$ ] 因此： [ $$ w $$ ] 是快变量， [ $$ \theta $$ ] 是慢变量。 ### 快时间尺度 在快时间尺度上，(\theta) 近似固定： [ $$ \dot\theta(t)=0. $$ ] (w) 的 ODE 为： [ $$ \dot w(t)=\mathbb E[\delta\phi\mid\theta]-Cw(t). $$ ] 平衡点为： [ $$ w^*(\theta)=C^{-1}\mathbb E[\delta\phi\mid\theta]. $$ ] 由于 (C\succ0)，该平衡点全局渐近稳定。 ### 慢时间尺度 在慢时间尺度上，(w) 已经跟踪： [ $$ C^{-1}\mathbb E[\delta\phi\mid\theta]. $$ ] 于是 (\theta) 的 ODE 为： # [ $$ \dot\theta = \left( I-\mathbb E[\gamma\phi'\phi^\top]C^{-1} \right) \mathbb E[\delta\phi\mid\theta]. $$ ] 化简得到： # [ $$ \dot\theta = A^\top C^{-1}(b-A\theta). $$ ] 平衡点为： [ $$ \theta^*=A^{-1}b. $$ ] 误差 (e=\theta-\theta^*) 满足： [ $$ \dot e=-A^\top C^{-1}Ae. $$ ] 由于 (A) 非奇异且 (C^{-1}\succ0)，矩阵： [ $$ A^\top C^{-1}A $$ ] 正定。因此 ODE 全局渐近稳定。最终得到： [ $$ \theta_k\to A^{-1}b \quad \text{a.s.} $$ ] 这证明 TDC 收敛到 TD fixed point。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- # 8. 实验结果 论文通过小规模问题、大规模围棋问题和 off-policy 反例检验算法。 --- ## 8.1 小规模问题 实验包含： [ $$ 3\text{ 个 random-walk 问题} $$ ] 和： [ $$ 1\text{ 个 Boyan-chain 问题}. $$ ] random-walk 有五个非终止状态和两个终止状态，episode 从中间状态开始，随机左右移动直到终止。三个版本只改变特征表示： 1. tabular features：查表特征； 2. inverted features：故意制造不合适泛化； 3. dependent features：只用 3 个特征，无法精确表示真实值函数。 Boyan-chain 使用 14 个状态和 4 个特征，是 TD 线性函数近似实验中的标准任务。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) 实验比较： [ $$ \text{GTD},\quad \text{GTD2},\quad \text{TDC},\quad \text{TD}. $$ ] 评价指标包括： [ $$ \sqrt{\operatorname{MSPBE}}, \quad \sqrt{\operatorname{MSBE}}, \quad \sqrt{\operatorname{NEU}}, \quad \sqrt{\operatorname{MSE}}. $$ ] 结果排序为： [ $$ \boxed{ \text{GTD 最慢} < \text{GTD2} < \text{TDC}\approx\text{TD}. } $$ ] TDC 有时由于额外参数 (\beta) 的灵活性而略优于 TD。论文说明不同目标函数下排序基本相同。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- ## 8.2 Computer Go 实验 大规模实验为 (9\times9) Computer Go 的固定策略 value prediction。 系统使用： [ $$ 969,894 $$ ] 个二值局部形状特征，经权重共享后压缩为： [ $$ n=63,303 $$ ] 个参数。由于 (n) 很大，(O(n^2)) 方法不可行。策略固定为随机合法落子，经验由 self-play 生成，除了赢棋奖励为 1 外，其余奖励为 0。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) 由于状态空间巨大，无法精确计算 MSPBE、MSBE、MSE。作者使用 NEU 的估计作为性能指标：在测试游戏中平均 (\delta\phi)，然后取范数。 结果与小规模实验一致： [ $$ \text{GTD 最慢，随后是 GTD2、TDC、TD}. $$ ] 不过论文谨慎指出，由于参数采样较粗且标准误约为 0.05，GTD2、TDC、TD 三者之间的差异未必显著。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- ## 8.3 Baird 反例 最后，论文在 Baird off-policy counterexample 上展示结果。该反例中传统 TD 发散，而梯度方法收敛。实验表明 GTD、GTD2、TDC 在该 off-policy 反例中收敛，验证了梯度 TD 方法相对于传统 TD 的稳定性优势。([ICML](https://icml.cc/Conferences/2009/papers/546.pdf?utm_source=chatgpt.com "Fast Gradient-Descent Methods for Temporal-Difference ...")) --- # 9. 核心贡献 ## 9.1 提出 MSPBE 作为显式优化目标 论文的重要贡献不是简单提出两个更新式，而是明确把 **MSPBE** 作为 TD fixed point 的自然目标： # [ $$ \operatorname{MSPBE}(\theta) = |V_\theta-\Pi TV_\theta|_D^2. $$ ] 这把 TD 类算法的 fixed point 与真实梯度下降联系起来。 --- ## 9.2 提出 GTD2 GTD2 是对 MSPBE 负梯度的直接采样形式： # [ $$ \theta_{k+1} = \theta_k + \alpha_k(\phi_k-\gamma\phi'_k)(\phi_k^\top w_k). $$ ] 相比原始 GTD，GTD2 使用更合适的目标函数，实验中明显更快。 --- ## 9.3 提出 TDC TDC 更新为： # [ $$ \theta_{k+1} = \theta_k+\alpha_k\delta_k\phi_k - \alpha_k\gamma\phi'_k(\phi_k^\top w_k). $$ ] 其结构保留传统 TD 主项，再加入梯度修正项。因此 TDC 在 on-policy 问题上速度接近 TD，同时保留 off-policy 线性函数近似下的收敛保证。 --- ## 9.4 给出收敛证明 论文证明 GTD2 和 TDC 在标准假设下收敛到： [ $$ \theta^*=A^{-1}b. $$ ] 即： [ $$ V_{\theta^*}=\Pi TV_{\theta^*}. $$ ] GTD2 用单时间尺度 ODE 方法证明；TDC 用双时间尺度随机逼近证明。 --- ## 9.5 证明 (O(n)) 可扩展性 两种算法都只维护： [ $$ \theta,w\in\mathbb R^n. $$ ] 每步只需内积和向量更新。因此时间和内存复杂度均为： [ $$ O(n). $$ ] 这使其可用于大规模线性特征问题，例如论文中的 Computer Go。 --- # 10. 理论意义 这篇文献的理论意义在于澄清了三个长期容易混淆的问题。 ## 10.1 TD 不是 MSBE 最小化 传统 TD 的 fixed point 是： [ $$ V_\theta=\Pi TV_\theta, $$ ] 而不是： [ $$ V_\theta=TV_\theta. $$ ] 因此 MSPBE 比 MSBE 更符合 TD 类算法的本质。 --- ## 10.2 真梯度下降不一定等于好 TD Residual-gradient 是真梯度方法，但若优化 MSBE 或平方 TD error，可能导致 backwards bootstrapping。论文通过例子说明，真梯度下降的关键不只是“是否为梯度”，还包括“目标函数是否正确”。 --- ## 10.3 Off-policy 稳定性需要改变更新结构 传统 TD 的更新： [ $$ \delta\phi $$ ] 在 off-policy + 函数近似下可能不稳定。GTD2/TDC 引入辅助变量 (w)，本质上估计： [ $$ C^{-1}\mathbb E[\delta\phi]. $$ ] 这使算法能够沿 MSPBE 梯度方向移动，而不是沿普通 TD 半梯度方向移动。 --- # 11. 局限性 ## 11.1 只处理线性函数近似 收敛证明依赖： [ $$ V_\theta=\Phi\theta. $$ ] 非线性函数近似，尤其是深度神经网络，不满足同样的线性结构。论文结论不能直接推广到深度 RL 的全局收敛。 ## 11.2 主要是 policy evaluation 算法目标是固定策略的价值估计。完整 control 问题涉及策略改进、目标策略变化、数据分布变化等额外复杂性，论文没有给出完整控制算法的全局收敛结论。 ## 11.3 假设较强 收敛证明依赖： [ $$ (\phi_k,r_k,\phi'_k)\text{ i.i.d.} $$ ] [ $$ A,C\text{ 非奇异} $$ ] [ $$ \text{步长满足随机逼近条件} $$ ] 实际在线 RL 中样本常来自 Markov trajectory，不一定独立同分布。虽然 ODE 方法可扩展到更广泛情形，但论文定理本身使用了这些标准化假设。 ## 11.4 实验规模有限 除 Computer Go 外，小规模实验主要是 random-walk 与 Boyan-chain。Go 实验也使用随机合法动作固定策略，并非强策略学习或完整控制任务。因此实验主要证明预测任务中的速度和可扩展性，而不是通用 RL 性能。 --- # 12. 与后续研究的关系 这篇文献是 gradient TD 方法的重要节点。它把 off-policy TD 收敛问题从“是否存在稳定 (O(n)) 算法”推进到“稳定算法是否足够快”。后续大量工作继续围绕 MSPBE、GTD/TDC 族算法、加速梯度 TD、非线性 GTD、actor-critic 中的 off-policy critic 学习展开。后续研究也将 GTD/TDC 作为基础算法族进行扩展或改进。([mediaTUM](https://mediatum.ub.tum.de/doc/1238750/629937188167.pdf?utm_source=chatgpt.com "Accelerated Gradient Temporal Difference Learning ...")) --- # 13. 总体评价 这篇文献的核心贡献可以压缩为一句话： [ $$ \boxed{ \text{通过 MSPBE 目标和辅助变量 }w， \text{构造出线性复杂度、可证明 off-policy 收敛、且速度接近 TD 的梯度 TD 算法。} } $$ ] 更具体地说： [ $$ \text{GTD2} $$ ] 解决了原始 GTD 目标几何不够自然、收敛慢的问题； [ $$ \text{TDC} $$ ] 进一步把 MSPBE 梯度写成： [ $$ \text{TD update}+\text{gradient correction} $$ ] 的形式，使其在实践中更接近 conventional TD 的速度。 从 TD 理论角度看，该文献的关键启示是： [ $$ \boxed{ \text{函数近似下，TD 的自然目标不是 Bellman error，而是 projected Bellman error。} } $$ ] 从算法角度看，关键启示是： [ $$ \boxed{ \text{off-policy 稳定性可以通过辅助变量估计 }C^{-1}\mathbb E[\delta\phi]\text{ 获得。} } $$ ] 从实践角度看，关键结论是： [ $$ \boxed{ \text{TDC 是传统 TD 在 off-policy 线性函数近似场景中的一个稳定、高效替代方案。} } $$ ] 因此，这篇文献在强化学习理论中的地位主要体现在：它系统连接了 **projected Bellman equation、MSPBE、stochastic gradient descent、off-policy stability、linear-time implementation** 这几个关键概念，并给出了 GTD2/TDC 两个具有明确理论保证和实验优势的算法。