强化学习 6：基于无模型——时序差分法（Temporal Difference,TD）

参考资料

[1]时雨：强化学习6：时序差分方法

[2]华师数据学院·王嘉宁：强化学习（六）：时序差分方法

[3]张楚珩：【强化学习入门 2】强化学习策略迭代类方法

[4]叶强：《强化学习》第五讲 不基于模型的控制

目录

  • 概念与特点
  • TD误差
  • TD策略评估【预测】
    • TD（0）
    • TD（λ）

  • TD策略提升【控制】
    • 基于on-policy的TD策略提升
      • Sarsa
      • Sarsa(λ)
    • 基于off-policy的TD策略提升
      • Q-learning
      • Expected Sarsa

  • 最大化偏差和双学习
  • DP、MC与TD的关系

1 概念与特点

TD方法结合了动态规划的自举思想与蒙特卡洛的采样思想，其可以像MC方法一样直接从Agent与环境互动的经验中学习，而不需要知道环境的模型，其又可以像DP方法一样无须等待交互的结果，可以边交互边学习。

何为自举（bootstrapping）？对于每一个状态价值函数的估算都依赖于前一时刻各状态价值函数的数值，对于这一特性称为“自举”。

何为采样（sampling）？从与环境的互动过程中所得到的经验作为求解贝尔曼方程的方法，对于这一特性称为“采样”。

TD方法从Episode学习，不需要了解模型本身；但是它可以学习不完整的Episode，通过自举来猜测Episode的结果，同时持续更新这个猜测。

2 TD误差

通用的更新公式：

  • 策略评估更新公式[公式]
  • 策略提升更新公式[公式]

[公式]表示次数的倒数，因为往往在蒙特卡洛采样过程中都是上万次，因此完全可以用一个预设的很小的超参数来描述它。

[公式]在MC方法中表示实际的价值，在TD（0）中表示下一时刻的价值估计值来替代实际值。

[公式]和 [公式] 被成为时序差分误差（TD误差），在MD方法中被成为蒙特卡洛误差（MC误差）。

带有[公式]的TD误差可以衡量当前波动值对更新当前价值的影响程度，充当了学习率的角色，而上面的式子和梯度下降的更新公式也是十分类似的。

3 TD策略评估【预测】

3.1 TD（0）

“0”表示TD误差，在当前状态下往前多看1步（one-step）。

[公式]

原来的[公式]是时刻[公式]的收益值（return），在蒙特卡罗方法中等待Episode结束才能得到该值。而TD方法只需要等待下一个时间步长就可以更新，[公式]是状态[公式]转移到状态 [公式] 所获得的即使回报值。

[公式][公式][公式]

第一个是蒙特卡洛方法，第二个是动态规划法，第三个是时序差分法。

TD（0）和DP都是用“自举”的方式更新，区别在于前者的更新来自于下一确定状态，而后者是了来自于所有可能的后续状态的分布。

3.2 TD（λ）

3.2.1 n-step

在当前状态往前行动n步，计算n步的return，同样TD目标也由两部分组成，已走的步数使用确定的即时reward，剩下的使用估计的状态价值替代。

图中空心大圆圈表示状态，实心小圆圈表示行为

  • n-step收获 [公式]
  • TD状态价值函数更新公式 [公式]

3.2.2 TD（λ）

引入参数[公式]，给其中任意一个n步收益施加一定的权重[公式]，得到[公式]

[公式]

后一个状态的状态价值与之前所有状态的状态价值有关，同时也可以说成是一个状态价值参与决定了后续所有状态的状态价值。但是每个状态的价值对于后续状态价值的影响权重是不同的。

4 TD策略提升【控制】

4.1 基于on-policy的TD策略提升

4.1.1 Sarsa算法

动作价值函数在每一次动作状态转换之后进行更新。

[公式]

如果[公式]是终止状态，那么我们就将[公式]定义为0。

在Sarsa算法中，我们不断评估策略[公式]的价值，采用ε-贪心算法权衡探索与开发。

算法中的[公式]是以一张大表存储的，这不适用于解决规模很大的问题；

对于每一个Episode，在[公式]状态时采用的动作[公式]是基于当前策略的，同时该行为也是实际Episode发生的行为，在更新[公式]状态动作对的价值循环里，个体并不实际执行在[公式]下的[公式]动作，而是将动作[公式]留到下一个循环执行。

4.1.2 Sarsa(λ)

[公式][公式]

关于Sarsa算法，参考资料[4]有详细讲解。

4.2 基于off-policy的TD策略提升

4.2.1 Q-learning算法

[公式]

Q-learning描述的是将下一个时刻到达的状态[公式]以及在这个状态下执行所有可能的动作所产生的一系列状态动作二元组中，取最大的动作价值作为估计值（带折扣的局部收益和）。

之所以称之为离轨策略，是因为这里的行动策略是基于ε-贪心的[公式]策略进行的采样序列，而目标策略则是在所有可能的状态动作二元组中取最大的贪心策略，二者没有关联性。

Sarsa算法需要在当前状态[公式]下执行动作[公式]，获得回报[公式]后达到状态[公式]，还要再执行动作[公式]后才能执行Sarsa回溯。

而Q-learning算法只需要在状态[公式]下执行动作[公式]，获得回报[公式]后达到状态[公式]，观察按照策略[公式]所有可能的动作[公式]与状态[公式]的二元组，无需执行。

4.2.2 Expected Sarsa 算法

当Sarsa算法改变更新的形式，使用 [公式] 的期望来更新时就会使得Sarsa算法变成一种off-policy算法，即Expected Sarsa，更新形式如下所示：

[公式][公式]

这种方法和原始的Sarsa算法相比虽然增加了计算上的复杂度，但是相对来说也减少了由于随机选择 [公式] 所产生的方差，在实验表现中效果往往也略胜一筹。

5 最大化偏差（Maximization Bias）和双学习（Double Learning）

5.1 Maximization Bias

蒙特卡洛是无偏估计，而时序差分是一个有偏估计。因为时序差分是建立在对价值函数估计的基础上来预测，换句话说，本身执行采样的过程就是一种预测过程，而实际价值使用估计值则又是一个近似的过程，所以说时序差分是包含两次估计的方法，会产生一定的正偏差，也叫做最大化偏差（Maximization Bias）。

5.2 Double Learning

如何避免Maximization Bias呢？首先我们造成这种现象的原因是我们使用了同样的样本来产生最大化行为并估计它的价值。

那么我们就可以将样本分为两份，并用它们来学习两个不同的价值函数，即[公式] ，它们都是真实价值[公式]的估计值。

用[公式]来产生最大化的动作[公式]。

用[公式]来更新动作[公式]的动作价值[公式]。

这样就可以做到无偏估计，[公式]。

这一思想运用在Q-learning中就是Double Q-learning。

6 DP、MC与TD的关系

主要参考DP与TD关系、MC与TD关系。

（待完善）