n步时序差分预测#

对于固定策略$\pi$下的给定的多幕采样序列，从某一状态开始，蒙特卡洛方法利用直至终止状态的收益序列对该状态的价值进行更新，而时序差分方法只根据下一步的即时收益，在后继状态的价值估计值的基础上进行自举更新。

我们很容易想到一种介于二者之间的方法是利用该状态之后的多个中间时刻的收益来进行更新，但又不到达终止状态。对于$n$步更新，我们利用当前状态之后的$n$步收益和$n$步之后的价值估计来更新当前状态价值估计。$n$步更新仍然属于时序差分方法，因为前面状态的估计值仍根据它与后继状态估计值的差异进行更新，只不过后继状态可以是$n$步之后的状态。时序差分量被扩展成$n$的方法被称为n步时序差分方法。

利用回溯图可以直观地对算法进行图示总结。不同步数下的时序差分方法更新的回溯图如下，空心圈代表采样的状态，实心点代表采样的动作：

接下来我们考虑该方法的数学表示。我们知道，在蒙特卡洛方法中，更新目标$G_t$沿着完整回报的方向计算

其中$T$是终止状态的时刻。

而在单步时序差分中，更新的目标是即时收益加上后继状态的价值函数估计值乘以折扣系数，我们称其为单步回报

其中$V_t$是在$t$时刻$v_\pi$的估计值，后继状态的折后价值函数估计$\gamma V_t(S_{t+1})$可以视为对后续完整回报$\gamma R_{t+2}+\cdots+\gamma^{T-t-1}R_T$的估计。类似地，将这种想法扩展到两步的情况，我们有两步更新的目标两步回报

而任意$n$步更新的目标是n步回报

其中$n\geqslant1$，$0\leqslant t\leqslant T-n$。$n$步回报即在$n$步后截断完整回报，并用$V_{t+n-1}(S_{t+n})$作为对剩余部分的估计。如果$t+n\geqslant T$，则超出终止状态的部分均为零，$n$步回报等于完整回报。

计算时刻$t$的$n$步回报需要在时刻$t+n$时得到$R_{t+n}$和$V_{t+n-1}$后才能计算。最基础的基于$n$步回报的状态价值函数更新算法即n步时序差分（$n$步TD）算法

在更新当前状态的过程中，其他状态$s\neq S_t$的价值估计保持不变

用$n$步回报在$V_{t+n-1}$的基础上更新$V_{t+n}$的一个重要依据是，$n$步回报的期望和真实状态价值函数$v_\pi(s)$之间的最大误差能保证不大于$V_{t+n-1}$和$v_\pi(s)$之间的最大误差的$\gamma^n$倍

这被称为$n$步回报的误差减少性质，其可以证明所有的$n$步时序差分方法在合适的条件下都能收敛到正确的预测，且$n$越大，收敛性越好。

$n$步TD的伪代码如下：

1. 参数：步长$\alpha\in(0,1]$，正整数$n$
2. 对所有的$s\in\mathcal S$，任意初始化$V(s)$
3. 对每幕循环：
   1. 初始化和存储$S_0\neq终止状态$
   2. $T\leftarrow\infty$
   3. 循环$t=0,1,2\cdots$：
      1. 如果$t<T$，那么：
         1. 根据$\pi(\cdot|S_t)$采取动作
         2. 观察和存储下一时刻的收益$R_{t+1}$和状态$S_{t+1}$
         3. 如果$S_{t+1}$是终止状态，则$T\leftarrow t+1$
      2. $\tau\leftarrow t-n+1$（$\tau$是当前正在更新的状态所在时刻）
      3. 如果$\tau\geqslant0$：
         1. $G\leftarrow\displaystyle\sum^{\min(\tau+n,T)}_{i=\tau+1}\gamma^{i-\tau-1}R_i$
         2. 如果$\tau+n<T$，那么$G\leftarrow G+\gamma^nV(S_{\tau+n})$
         3. $V(S_\tau)\leftarrow V(S_\tau)+\alpha[G-V(S_\tau)]$
   4. 直到$\tau=T-1$

该伪代码的逻辑较为晦涩，其进一步解释如下：在每一幕，我们从$S_0$根据策略$\pi$选择动作直至终止状态$S_T$，其中$T$在一开始并不知道，直到遇到终止状态才能确定。$S_0$的更新需要等到时刻$t=n+1$时才能执行，相应地，往后$S_\tau(\tau\geqslant0)$的更新则在时刻$t=n+1+\tau$执行，在代码中则表示为在时刻$t$执行对$S_{t-n+1}(\tau=t-n+1\geqslant0)$的更新。在更新中，如果$S_\tau$距离终止状态$S_T$不足$n$步，则$\min(\tau+n,T)=T$，回报只能在终止状态截断，即直接使用完整回报作为更新目标，此时也无需再加上后继状态的折后价值估计，因为终止状态的价值$v(S_T)=0$。

事实证明，对于大小为$|\mathcal S|$的状态集合，$n$取其中间大小的值时通常效果最好，这也证明了将单步时序差分方法和蒙特卡洛方法推广到$n$步时序差分方法可能会得到更好的效果。

n步Sarsa#

将$n$步方法与Sarsa结合，我们可以得到同轨策略下的$n$步时序差分学习控制方法。$n$步版本的Sarsa被称为n步Sarsa，相应地，上一章介绍的初始版本的Sarsa被称为单步Sarsa或Sarsa(0)。不同步数下的Sarsa方法更新的回溯图如下：

![[Pasted image 20250519191609.png]]

和单步TD到单步Sarsa的转换一样，$n$步TD到$n$步Sarsa的核心思想也是将状态替换为“状态-动作”二元组，并使用$\epsilon$-贪心策略。我们根据动作价值估计重新定义$n$步Sarsa方法下的$n$步回报

当$t+n\geqslant T$时，$G_{t:t+n}=G_t$。

则$n$步Sarsa的更新公式为

在处理对应“动作-状态”二元组的更新时，所有其他二元组保持不变，即对于所有$s\neq S_t$，$a\neq A_t$，有

$n$步Sarsa算法的伪代码如下：

1. 参数：步长$\alpha\in(0,1]$，很小的$\epsilon>0$，正整数$n$
2. 对所有的$s\in\mathcal S,a\in\mathcal A$，任意初始化$Q(s,a)$
3. 初始化$\pi$为基于$Q$的$\epsilon$-贪心策略或者某个给定策略
4. 对每幕循环：
   1. 初始化和存储$S_0\neq终止状态$
   2. 选择和存储动作$A_0\sim\pi(\cdot|S_0)$
   3. $T\leftarrow\infty$
   4. 循环$t=0,1,2\cdots$：
      1. 如果$t<T$，那么：
         1. 采取动作$A_t$
         2. 观察和存储下一时刻的收益$R_{t+1}$和状态$S_{t+1}$
         3. 如果$S_{t+1}$是终止状态：
            1. $T\leftarrow t+1$
         4. 否则：
            1. 选择并存储动作$A_{t+1}\sim\pi(\cdot|S_{t+1})$
      2. $\tau\leftarrow t-n+1$（$\tau$是当前正在更新的状态所在时刻）
      3. 如果$\tau\geqslant0$：
         1. $G\leftarrow\displaystyle\sum^{\min(\tau+n,T)}_{i=\tau+1}\gamma^{i-\tau-1}R_i$
         2. 如果$\tau+n<T$，那么$G\leftarrow G+\gamma^nQ(S_{\tau+n},A_{\tau+n})$
         3. $Q(S_{\tau},A_{\tau})\leftarrow Q(S_{\tau},A_{\tau})+\alpha[G-Q(S_{\tau},A_{\tau})]$
         4. 更新$\pi$为基于$Q$的$\epsilon$-贪心策略
   5. 直到$\tau=T-1$

$n$步Sarsa相比单步Sarsa能够加速策略学习。假设在一个网格世界中，除了终点具有高收益，其余格子的收益均为零，则完成一幕序列的采样后，单步Sarsa的终点收益只能影响到达终点的前一个格子相应的动作价值，而$n$步Sarsa却能更新路径上到达终点的前$n$个格子相应的动作价值，学到了更多的知识。

![[Pasted image 20250519191717.png]]

$n$步期望Sarsa则在Sarsa的基础上重新定义了$n$步回报

其中$\bar V(s)$表示状态$s$的期望近似价值，它通过在目标策略下$t$时刻的动作价值估计的期望来计算

终止状态的期望近似价值为零。

n步离轨策略学习#

$n$步时序差分方法的离轨策略学习与蒙特卡洛方法中介绍的离轨策略控制相似，因为我们需要行动策略和目标策略在$n$步上采取相同行动的相对概率（重要度采样比），进而由行动策略$b$的$n$步回报来预测目标策略$\pi$的$n$步回报。

对于由策略$b$从$t$时刻采样的$n$步回报$G_{t:t+n}$，在对$n$步之后$t+n$时刻策略$\pi$的状态价值估计$V_{t+n}(S_t)$进行更新时，可以简单地用重要度采样比$\rho_{t:t+n-1}$（两种策略采取$A_t\sim A_{t+n}$这$n$个动作的相对概率）进行修正

这里，重要度采样比的计算为

其中$\min(h,T-1)$在终止状态截断截断计算。

在蒙特卡洛方法的离轨策略控制中，我们使用贪心策略作为目标策略。但是尽管我们选择了具有试探性的行为策略，在重要度采样中，价值估计的更新仍然取决于目标策略是否有概率选择，因此在学习中使用绝对的贪心策略并不是一个好的选择。我们仍可以采取$\epsilon$-贪心策略使得所有价值估计都有被更新的可能，在合适的条件下，基于$\epsilon$-贪心策略收敛后的价值估计生成一个贪心策略也能得到最优策略。

离轨策略下的$n$步Sarsa算法伪代码如下：

1. 参数：步长$\alpha\in(0,1]$，正整数$n$
2. 对所有的$s\in\mathcal S,a\in\mathcal A$，任意初始化$Q(s,a)$
3. 初始化$b$为一个任意的满足$b(a|s)>0$的策略
4. 初始化$\pi$为基于$Q$的$\epsilon$-贪心策略或者某个给定策略
5. 对每幕循环：
   1. 初始化和存储$S_0\neq终止状态$
   2. 选择和存储动作$A_0\sim b(\cdot|S_0)$
   3. $T\leftarrow\infty$
   4. 循环$t=0,1,2\cdots$：
      1. 如果$t<T$，那么：
         1. 采取动作$A_t$
         2. 观察和存储下一时刻的收益$R_{t+1}$和状态$S_{t+1}$
         3. 如果$S_{t+1}$是终止状态：
            1. $T\leftarrow t+1$
         4. 否则：
            1. 选择并存储动作$A_{t+1}\sim b(\cdot|S_{t+1})$
      2. $\tau\leftarrow t-n+1$（$\tau$是当前正在更新的状态所在时刻）
      3. 如果$\tau\geqslant0$：
         1. $\displaystyle\rho\leftarrow\prod^{\min(\tau+n-1,T-1)}_{i=\tau+1}\frac{\pi(A_i|S_i)}{b(A_i|S_i)}$
         2. $G\leftarrow\displaystyle\sum^{\min(\tau+n,T)}_{i=\tau+1}\gamma^{i-\tau-1}R_i$
         3. 如果$\tau+n<T$，那么$G\leftarrow G+\gamma^nQ(S_{\tau+n},A_{\tau+n})$
         4. $Q(S_{\tau},A_{\tau})\leftarrow Q(S_{\tau},A_{\tau})+\alpha\rho[G-Q(S_{\tau},A_{\tau})]$
         5. 更新$\pi$为基于$Q$的$\epsilon$-贪心策略
   5. 直到$\tau=T-1$

n步树回溯法#

$n$步树回溯法是一种不需要重要度采样的$n$步离轨策略学习方法。普通的$n$步离轨策略方法只依赖行动策略采样的具体动作，因此需要对行动策略的动作采取概率进行修正。而在$n$步树回溯法中，行动策略的作用仅仅是产生状态转移，决定采样的动作-状态路径，在计算$n$步回报时，行动策略选择的动作和未选择的动作都会以在目标策略下的选择概率被加权。一个三步树回溯更新的回溯图如下：

![[Pasted image 20250519201306.png|138]]

树回溯算法的单步回报与期望Sarsa相同，即对于$t<T-1$，有

对于$t<T-2$，两步树回溯的回报将$Q(S_{t+1},A_{t+1})$展开为在$S_{t+1}$选择$A_{t+1}$转移到$S_{t+2}$的单步回报

从这个公式中我们可以看出树回溯的$n$步回报的递归形式，即对于$t<T-1,n\geqslant2$，有

上式是我们在代码中更新$n$步回报的基础。对于$t+n$超出$T-1$的部分，我们仍使用终止状态的收益$R_T$截断，即$G_{T-1:t+n}=R_T$。价值估计的更新公式与$n$步Sarsa一样

$n$步树回溯算法的伪代码如下：

1. 参数：步长$\alpha\in(0,1]$，正整数$n$
2. 对所有的$s\in\mathcal S,a\in\mathcal A$，任意初始化$Q(s,a)$
3. 初始化$b$为一个任意的满足$b(a|s)>0$的策略
4. 初始化$\pi$为基于$Q$的$\epsilon$-贪心策略或者某个给定策略
5. 对每幕循环：
   1. 初始化和存储$S_0\neq终止状态$
   2. 根据$S_0$任意选择并存储动作$A_0$
   3. $T\leftarrow\infty$
   4. 循环$t=0,1,2\cdots$：
      1. 如果$t<T$，那么：
         1. 采取动作$A_t$
         2. 观察和存储下一时刻的收益$R_{t+1}$和状态$S_{t+1}$
         3. 如果$S_{t+1}$是终止状态：
            1. $T\leftarrow t+1$
         4. 否则：
            1. 根据$S_{t+1}$任意选择并存储动作$A_{t+1}$
      2. $\tau\leftarrow t-n+1$（$\tau$是当前正在更新的状态所在时刻）
      3. 如果$\tau\geqslant0$：
         1. 如果$t+1\geqslant T$：
            1. $G\leftarrow R_T$
         2. 否则
            1. $G\leftarrow R_{t+1}+\gamma\displaystyle\sum_a\pi(a|S_{t+1})Q(S_{t+1},a)$
         3. 循环$k$从$\min(t,T-1)$递减到$\tau+1$：
            1. $G\leftarrow R_k+\gamma\displaystyle\sum_{a\neq A_k}\pi(a|S_k)Q(S_k,a)+\gamma\pi(A_k|S_k)G$
         4. $Q(S_{\tau},A_{\tau})\leftarrow Q(S_{\tau},A_{\tau})+\alpha[G-Q(S_{\tau},A_{\tau})]$
         5. 更新$\pi$为基于$Q$的$\epsilon$-贪心策略
   5. 直到$\tau=T-1$