Temporal Difference

增量式MC
- $V(S_{t})=V(S_{t})+\frac{1}{N(S_{t})}(G_{t}-V(S_{t}))$
时间差分TD
- $V(S_{t})=V(S_{t})+\frac{1}{N(S_{t})}(R_{t+1}+\gamma V(S_{t+1})-V(S_{t}))$
核心差别：
- MC是根据[s1→终止状态]完整片段的最终回报更新s1的值函数
- TD是根据[s1→s2]这一步片段的即时回报值R和s2的估计值函数更新s1的值函数

与DP的对比

DP是全宽备份
TD是样本备份

TD与MC的对比

TD 算法在知道结果之前学习
- TD算法在每一步之后都能在线学习
- MC算法必须等待最终回报值得到之后才能学习
TD算法即便没有最终结果也能学习
- TD算法能够从不完整序列中学习
- MC算法仅仅能够从完整序列中学习
- TD算法适用于连续性任务和片段性任务
- MC算法仅仅适用于片段性任务
TD算法有多个驱动力
- MC算法只有奖励值作为更新的驱动力
- TD算法有奖励值和状态转移作为更新的驱动力
MC有高方差,零偏差
- 收敛性较好 (即使采用函数逼近)
- 对初始值不太敏感
- 随着样本数量的增加,方差逐渐减少, 趋近于 0
TD 有低方差,和一些偏差
- 通常比 MC 效率更高
- 表格法下TD(0)收敛到 $V_{\pi }(s)$ (函数逼近时不一定)
- 对初始值更敏感
- 随着样本数量的增加,偏差逐渐减少,趋近于 0
- 样本数量有限时，TD的结果与真实结果的偏差比较稳定。MC可能出现巨大偏差。
TD要求环境符合马尔科夫性，MC不要求

自举和采样

自举: 使用随机变量的估计去更新
- MC 没有自举
- DP 和 TD 都有自举
采样: 通过样本估计期望
- MC 和 TD 采样
- DP 不采样

TD的优化方法

整体思路是策略评价+策略提升
策略评价
- 在策略评价SARSA
  - 公式
    - $Q(S_{t},A_{t})\leftarrow Q(S_{t},A_{t})+\alpha (R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_{t},A_{t}))$
  - 算法流程
    - 1:初始化 $Q(s,a), \forall s\in S, a\in A(s)$ 且 $Q(S_{end},\cdot )=0$
    - 2:repeat(对于每个片段)
    - 3: 初始化状态 $S$
    - 4: 根据 $Q$ 选择一个在 $S$ 处的动作 $A$ (使用 $\varepsilon$ -贪婪策略)
    - 5: repeat(对于片段中每一步)
    - 6: 执行动作 $A$ ，观测 $R,S^{'}$
    - 7: 根据 $Q$ 选择一个在 $S^{'}$ 处的动作 $A^{'}$ (使用 $\varepsilon$ -贪婪策略)
    - 8: $Q(S_{t},A_{t})\leftarrow Q(S_{t},A_{t})+\alpha (R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_{t},A_{t}))$
    - 9: $S\leftarrow S^{'};A\leftarrow A^{'}$
    - 10: until $S$ 是终止状态
    - 11:until收敛
  - 收敛性
    - 在满足以下条件时,Sarsa 算法收敛到最优的状态动作值函数
      - 策略序列 $\pi _{t}(a|s)$ 满足GLIE
      - 步长序列 $\alpha _{t}$ 是一个Robbins-Monro序列
        
        $\sum_{t=1}^{\infty }\alpha _{t}=\infty ,\sum_{t=1}^{\infty }\alpha _{t}^{2}=\infty$
    - GLIE 保证了
      - 充分的探索
      - 策略最终收敛到贪婪的策略
    - Robbins-Monro保证了
      - 步长足够大,足以克服任意初始值
      - 步长足够小,最终收敛 (常量步长不满足)
- 期望SARSA
  - $Q(S_{t},A_{t})\leftarrow Q(S_{t},A_{t})+\alpha (R_{t+1}+\gamma \sum_{a}\pi (a|S_{t+1})Q(S_{t+1},a)-Q(S_{t},A_{t}))$
  - 减少了由于 $A^{'}$ 的选择带来的方差
  - 在相同更新步数时,期望 Sarsa 比 Sarsa 的通用性更好
  - 可以在在策略和离策略中切换
    - 在策略:TD目标值中的 $R_{t+1}+\gamma \sum_{a}\pi (a|S_{t+1})Q(S_{t+1},a)$ 中的策略 $\pi$ 和采样的策略是同一个策略
    - 离策略:TD目标值中的 $R_{t+1}+\gamma \sum_{a}\pi (a|S_{t+1})Q(S_{t+1},a)$ 中的策略 $\pi$ 和采样的策略是不同的策略
  - 一种特殊情况,TD目标值中的策略选择贪婪策略, 采样的策略选用ε-贪婪策略——Q学习
- 离策略评价Q学习
  - 公式
    - $Q(S,A)\leftarrow Q(S,A)+\alpha (R+\gamma \max_{a^{'}}Q(S^{'},a^{'})-Q(S,A))$
  - 算法流程
    - 1:初始化 $Q(s,a), \forall s\in S, a\in A(s)$ 且 $Q(S_{end},\cdot )=0$
    - 2:repeat(对于每个片段)
    - 3: 初始化状态 $S$
    - 4: repeat(对于片段中每一步)
    - 5: 根据 $Q$ 选择一个在 $S$ 处的动作 $A$ (使用 $\varepsilon$ -贪婪策略)
    - 6: 执行动作 $A$ ，观测 $R,S^{'}$
    - 7: $Q(S,A)\leftarrow Q(S,A)+\alpha (R+\gamma \max_{a^{'}}Q(S^{'},a^{'})-Q(S,A))$
    - 8: $S\leftarrow S^{'}$
    - 9: until $S$ 是终止状态
    - 10:until收敛
策略提升
- $\varepsilon$ -贪婪策略提升

朝花夕拾

Temporal Difference

Temporal Difference

与DP的对比

TD与MC的对比

自举和采样

TD的优化方法

策略评价

在策略评价SARSA

公式

算法流程

收敛性

期望SARSA

离策略评价Q学习

公式

算法流程

策略提升

$\varepsilon$ -贪婪策略提升

Search

欢迎添加我的微信

Table of Contents