时序差分学习算法

时序差分学习(Temporal-Difference Learning)是另一种无模型的强化学习方法。蒙特卡罗方法不足的地方是它只能应用于回合步数有限的情况(因为蒙特卡罗方法只有在一个回合结束并得到一个奖励后,才能去更新一个状态的价值),然而现实问题中,很多问题并不能在有限的步数里结束,例如无人驾驶和机器人控制,而时序差分学习则可以应用于这类回合持续时间很长的任务。

1.蒙特卡罗更新和时序差分更新

在蒙特卡罗方法里,我们都是利用一个回合结束后得到的奖励来更新当前 Q 值的,这种更新的方式称为蒙特卡罗更新。我们希望可以尽早更新 Q 值,而不是只有等到一个回合结束之后才能更新,这就是时序差分更新。

在蒙特卡罗算法中,更新 Q 值的公式为:

Q(st, at)=(c(st, at)×Q(st, at)+G)/(c(st, at)+1)                      式 1


式 1 是将所有的累积奖励取平均值,假设 c(st, at) =k,并用 Gi 表示第 i 次得到的奖励的话,式 1 可以表示为:

Q(st, at)=(1/(k+1))(Gi+k·Q(st, at))=(1/(k+1))(Gi+k·Q(st, at)+Q(st, at)-Q(st, at))            式 2
             =Q(st, at)+(1/(k+1))(Gi-Q(st, at)


我们将式 2 的 1/(k+1) 看作一个参数 α,即学习率,学习率的存在是为了 Q 值最终收敛,并且该参数的值随着时间递减。现在将式 2 改写为一个更常用的形式:

Q(st, at)=Q(st, at) +α(G-Q(st, at))            式 3

上式中的 G-Q(st, at) 称为蒙特卡罗误差。

事实上,Q(st,at) 的值其实就是智能体在状态 st下,执行动作 at 后,沿着当前策略走下去后所能得到的累积奖励的期望,是对奖励的一个估计值。而蒙特卡罗算法中走完一个回合后得到的 G 是真实的奖励值,时序差分学习希望用这个估计的奖励值替代真实的奖励值。因此,时序差分方法更新 Q 值的公式为

Q(st, at)=Q(st, at)+α(rt+1+γQ(st+1, at+1)-Q(st, at))              式 4

式 4 中的 rt+1+γQ(st+1, at+1)-Q(st, at) 称为时序差分误差(即 TD 误差),rt+1+γQ(st+1, at+1) 是式 3 中 G 的近似值,如果去掉式 4 中的折扣因子 γ(0≤γ≤1),则有

rt+1+Q(st+1, at+1)=rt+1+rt+2+rt+3+...=G           式 5

2.Sarsa 算法

Sarsa 算法是时序差分学习的在策略版本,Sarsa 算法的伪代码如下所示:
For s in S:
    For a in A:
        Initialize Q(s, a)
For i in range(k):
    Initialize S
    Choose a using policy derived from Q(e.g. ε-greedy)
    Repeat (for each step of episode):
        Take action a,observe r and s
        Choose a' using policy derived from Q(e.g. ε-greedy)
        Q(s, a) ← Q (s, a) + α[R + γQ(s' ,a') - Q (s, a)]
        s← s'; a← a'
    until s is terminal
End for

3.Q-Learning 算法

Q-Learning 算法是时序差分学习方法的离策略版本,Q-Learning 算法的伪代码如下:
For s in S:
    For a in A:
        Initialize Q(s, a)
For i in range(k):
    Initialize S
    Repeat (for each step of episode):
        Choose a using policy derived from Q(e.g. ε-greedy)
        Take action a,observe r and s
        Choose a' using policy derived from Q(e.g. ε-greedy)
        Q(s, a) ← Q (s, a) + α[R + γmax(Q(s' ,a')) - Q (s, a)]
        s← s
    until s is terminal
End for
在时序差分学习方法中,在策略的 Sarsa 算法使用估计的策略采取动作,而离策略的 Q-Learning 算法选择所有可能的下一动作中Q值最大的动作(即 Q-Learning 有一个专门用来产生行为的策略)。

如果在确定性的环境状态下,Q-Learning 的 Q 值的更新方式可以简化为

Q(st, at)←rt+1+γmax(Q(st+1, at+1))

这里我们介绍的 Sarsa 算法和 Q-Learning 算法均为单步更新算法,即时序差分误差都只用来更新前一个值。我们可以通过使用资格迹(Eligibility Trace)来实现多步的更新,有关资格迹的讨论不在本节教程的范围。