n步时序差分强化学习

n步时序差分策略评估

对于时序差分策略评估目标值，$TD\ Target\approx G(s_{t},a_{t})$
其中 $n$ 代表往后更新（交互）了 $n$ 步，当 $n=1$ 时，是 $TD\ Target$；当 $n=T-t$ 时，是 $MC\ Target$

故由（11-4）的动作值更新公式变化为：
（1）$n$ 步时序差分策略评估算法（14-3）

1. 输入：环境模型 $MDP(S,A,R,\gamma)$，学习率 $\alpha =0.1$，待评估策略 $\pi$，差分步数 $n$，容忍系数 $\delta$
2. 初始化：随机初始化动作值 $Q(s,a)$
3. 过程：
4. $\qquad$ 循环：动作值变化小于容忍系数 $\delta$
5. $\qquad \qquad$ 初始状态：$s=s_0$
6. $\qquad \qquad$ 选择动作：$a_0=\pi(s_0)$
7. $\qquad \qquad$ 时间步计数器：$t=0$
8. $\qquad \qquad$ 循环：直到到达终止状态，即 $END=True$
9. $\qquad \qquad \qquad$ 执行动作：$s_t,a_t,R_{t+1},s_{t+1},END$
10. $\qquad \qquad \qquad$ 时间步计算器：$t\leftarrow t+1$
11. $\qquad \qquad \qquad$ $if\ \ t<n$
12. $\qquad \qquad \qquad \qquad$ $if\ \ END$
13. $\qquad \qquad \qquad \qquad \qquad$ $break$
14. $\qquad \qquad \qquad \qquad$ $else$
15. $\qquad \qquad \qquad \qquad \qquad$ 选择动作 $a_t=\pi(s_t)$
16. $\qquad \qquad \qquad$ $if\ \ t\ge n$
17. $\qquad \qquad \qquad \qquad$ $if\ \ not\ \ END$
18. $\qquad \qquad \qquad \qquad \qquad$ 选择动作 $a_t=\pi(s_t)$
19. $\qquad \qquad \qquad \qquad \qquad$ 计算 $n$ 步 $TD\ \ Target$：公式（14-1）
20. $\qquad \qquad \qquad \qquad \qquad$ 动作值更新：公式（14-2）
21. $\qquad \qquad \qquad \qquad$ $else$
22. $\qquad \qquad \qquad \qquad \qquad$ $For\ \ k=(t-n)\sim (t-1)$
23. $\qquad \qquad \qquad \qquad \qquad \qquad$ $G\left(s_{k}, a_{k}\right) \leftarrow R_{k+1}+\gamma\ R_{k+2}+\cdots+\gamma^{t-k-1}\ R_{t}$
24. $\qquad \qquad \qquad \qquad \qquad \qquad$ $Q\left(s_{k}, a_{k}\right) \leftarrow Q\left(s_{k}, a_{k}\right)+\alpha\left(G\left(s_{k}, a_{k}\right)-Q\left(s_{k}, a_{k}\right)\right)$
25. $\qquad \qquad \qquad \qquad \qquad$ $break$
26. 输出：策略 $\pi$ 下的动作值 $Q_{\pi}(s,a)$

说明：

(1).至少 $n$ 步交互后的经验数据（一条 $MDP$ 链长度大于 $n$）才能计算 $TD$ 目标值

(2).在交互到达终止状态后，后 $n$ 个动作值己经不能再使用 $n$ 步 $TD\ \ Target$ 进行更新了，因为此时己不足 $n$ 步，而使用 $n-1$ 步 $TD\ \ Target$ 进行更新，然后使用 $n-2$ 步 $TD\ \ Target$，直到 $1$ 步 $TD\ \ Target$

(3).可以把 $t$ 看作是一个滑动窗口

n-step Sarsa 算法

将 $n$ 步时序差分的思想推广到 $Sarsa$ 算法即可得到 $n$ 步 $Sarsa$ 算法

（1）$n$ 步时序差分策略评估算法（14-4）

1. 输入：环境模型 $MDP(S,A,R,\gamma)$，学习率 $\alpha =0.1$，待评估策略 $\pi$，差分步数 $n$，容忍系数 $\delta$
2. 初始化：随机初始化动作值 $Q(s,a)$
3. 过程：
4. $\qquad$ 循环：$episode=1\sim num\_episodes$
5. $\qquad \qquad$ 初始状态：$s_0$
6. $\qquad \qquad$ 选择动作：$a_0=\pi(s_0)$
7. $\qquad \qquad$ 时间步计数器：$t=0$
8. $\qquad \qquad$ 循环：直到到达终止状态，即 $END=True$
9. $\qquad \qquad \qquad$ 执行动作：$s_t,a_t,R_{t+1},s_{t+1},END$
10. $\qquad \qquad \qquad$ 时间步计算器：$t\leftarrow t+1$
11. $\qquad \qquad \qquad$ $if\ \ t<n$
12. $\qquad \qquad \qquad \qquad$ $if\ \ END$
13. $\qquad \qquad \qquad \qquad \qquad$ $break$
14. $\qquad \qquad \qquad \qquad$ $else$
15. $\qquad \qquad \qquad \qquad \qquad$ 选择动作 $a_t=\pi_{\epsilon}(s_t)$
16. $\qquad \qquad \qquad$ $if\ \ t\ge n$
17. $\qquad \qquad \qquad \qquad$ $if\ \ not\ \ END$
18. $\qquad \qquad \qquad \qquad \qquad$ 选择动作 $a_t=\pi_{\epsilon}(s_t)$
19. $\qquad \qquad \qquad \qquad \qquad$ 计算 $n$ 步 $TD\ \ Target$：公式（14-1）
20. $\qquad \qquad \qquad \qquad \qquad$ 动作值更新：公式（14-2）
21. $\qquad \qquad \qquad \qquad \qquad$ 策略改进：$\pi(s_{t-n})=\arg \max _{a \in \mathbb{A}} Q(s_{t-n}, a)$
22. $\qquad \qquad \qquad \qquad$ $else$
23. $\qquad \qquad \qquad \qquad \qquad$ $For\ \ k=(t-n)\sim (t-1)$
24. $\qquad \qquad \qquad \qquad \qquad \qquad$ $G\left(s_{k}, a_{k}\right) \leftarrow R_{k+1}+\gamma\ R_{k+2}+\cdots+\gamma^{t-k-1}\ R_{t}$
25. $\qquad \qquad \qquad \qquad \qquad \qquad$ $Q\left(s_{k}, a_{k}\right) \leftarrow Q\left(s_{k}, a_{k}\right)+\alpha\left(G\left(s_{k}, a_{k}\right)-Q\left(s_{k}, a_{k}\right)\right)$
26. $\qquad \qquad \qquad \qquad \qquad \qquad$ 策略改进：$\pi(s)=\arg \max _{a \in \mathbb{A}} Q(s_k, a)$
27. $\qquad \qquad \qquad \qquad \qquad$ $break$
28. 输出：最终策略 $\pi^*(s)$，最终动作值 $Q^*(s,a)$

同样的，$n$ 步时序差分的思想也可以很容易推广到 $Q-learning$、$Expected\ \ Sarsa$ 和 $Double\ Q-learning$ 算法上，得到相应的 $n$ 步时序差分版本

参考

• https://github.com/QiangLong2017