强化学习笔记(四)- 时序差分学习

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言,谢谢

引言

  上文我们提到的 MC 方法,用于回合制任务中,并且必须等到回合结束之后才可以更新价值估计。而时序差分学习( Temporal-Difference Learning)不需要等到回合结束也可以更新价值估计,并且不仅可以用于回合制任务,还可以用于连续性任务。

同策时序差分更新

  我们先来解释下何谓时序差分,在给定策略 \(\pi\) 下,状态价值为:

\[ \begin{aligned} v_{\pi}(s) & \doteq \mathbb{E}_{\pi}\left[G_{t} | S_{t}=s\right] \\ &=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma G_{t+1} | S_{t}=s\right] \\ &=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s\right] \end{aligned} \]

  如果用 MC 方法来估计价值函数的话,为了得到回报样本,我们就必须从状态对 \(s\) 出发,一直采样到回合结束。但是对于单步时序差分来说,更新只需要依据 \(v_{\pi}(s) = \mathbb{E}_{\pi}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s\right]\),只需要采样一步,进而用 \(U_t = R_{t+1}+\gamma v_{\pi}(S_{t+1})\) 来估计回报样本的值,与由奖励直接计算得到的无偏回报样本 \(G_t\) 作区分,\(U_t\) 表示使用自益得到的有偏回报样本。
  所以,单步时序差分目标可以定义为:

\[ U_{t: t+1} \doteq R_{t+1}+\gamma V_{t}\left(S_{t+1}\right) \]

  下标 \(t: t+1\) 表示用 \(S_{t+1}\) 的估计值来估计 \(S_t\)。相应的 \(n\) 步时序差分目标可以定义为:

\[ U_{t: t+n} \doteq R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{n-1} R_{t+n}+\gamma^{n} V_{t+n-1}\left(S_{t+n}\right) \]

   TD 误差也可以定义为:

\[ \delta_{t} \doteq R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right) \]

  下图是从单步 TD 到多步 TD,再到没有自益,也就是 MC 估计的一个示意图:

时序差分更新策略评估

  我们用下面形式的增量更新来学习状态价值函数:

\[ V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left[G_{t}-V\left(S_{t}\right)\right] \]

  上面的 \(G_t\) 就是我们之前说的 \(U_t\),单步时序差分更新评估策略的状态价值的算法的伪代码如下:

  时序差分更新不仅可以用于回合制任务,也可用于非回合制任务,对于非回合制任务,我们可以自行将某些时段抽出来当作多个回合,也可以不划分回合当作只有一个回合进行更新。
  \(n\) 步时序差分更新评估策略的状态价值的算法如下:

SARSA(State-Action-Reward-State-Action)

  SARSA 算法就比较容易理解了,就如它的名字一样,它涉及 \((S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})\),更新式:

\[ Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left[R_{t+1}+\gamma Q\left(S_{t+1}, A_{t+1}\right)-Q\left(S_{t}, A_{t}\right)\right] \]

  伪代码如下:

  \(n\) 步的 SARSA 也很容易理解:

期望 SARSA 算法(Expected SARSA)

  期望 SARSA 算法与普通的 SARSA 算法的区别就是,它不使用基于动作价值的时序差分目标,而是使用基于状态价值的时序差分目标,利用 Bellman 方程,这样的目标又可以写为:

\[ \begin{aligned} Q\left(S_{t}, A_{t}\right) & \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left[R_{t+1}+\gamma \mathbb{E}_{\pi}\left[Q\left(S_{t+1}, A_{t+1}\right) | S_{t+1}\right]-Q\left(S_{t}, A_{t}\right)\right] \\ & \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left[R_{t+1}+\gamma \sum_{a} \pi\left(a | S_{t+1}\right) Q\left(S_{t+1}, a\right)-Q\left(S_{t}, A_{t}\right)\right] \end{aligned} \]

  因为需要计算动作价值的求和,所以它有着更大的计算量,但是这样的期望运算减小了 SARSA 算法中出现的个别不恰当决策,这样可以避免在更新后期极个别不当决策对最终效果带来不好的影响,因此它通常需要更大的学习率

异策时序差分更新

基于重要性采样的异策算法

  回顾一下重要性采样比率:

\[ \rho_{t: h} \doteq \prod_{k=t}^{\min (h, T-1)} \frac{\pi\left(A_{k} | S_{k}\right)}{b\left(A_{k} | S_{k}\right)} \]

  也就是说,通过行为策略 \(b\) 拿到的估计,在原策略 \(\pi\) 出现的概率是在策略 \(b\) 中出现概率的 \(\rho_{t: h}\) 倍。
  伪代码如下:

Q-learning

  Q-learning 是从改进后策略的行为出发,将时序差分目标改为 \(U_t = R_{t+1}+\gamma \max _{a} Q\left(S_{t+1}, a\right)\),它这么做的原因是因为在根据 \(S_{t+1}\) 估计 \(U_t\) 时,与其使用 \(Q(S_{t+1}, A_{t+1})\)(SARSA 算法)或 \(v(S_{t+1})\)(期望 SARSA 算法),不如使用根据动作价值改进后的策略来更新,这样可以更接近最优价值。因此,Q-learning 的更新式不是基于当前的策略,而是基于另外一个并不一定要使用的确定性策略来更新动作价值,从这个角度来看 Q-learning 也是一个异策算法。伪代码如下:

Double Q-learning

  Q-learning 使用 \(\max _{a} Q\left(S_{t+1}, a\right)\) 来更新动作价值,会导致最大化偏差(maximization bias),主要会在一些中间状态出问题,需要大量的数据才能纠正。
  出现这个问题的一个主要原因是使用了相同的样本来确定最大化动作并估计其值,用相同的值来选择和评价一个动作,这使得其更偏向于选择过分评估值( overestimated values),导致次优的估计值。Double Q-learning 可以解决这一问题,它使用两个独立的动作价值函数,更新式如下:

\[ Q_{1}\left(S_{t}, A_{t}\right) \leftarrow Q_{1}\left(S_{t}, A_{t}\right)+\alpha\left[R_{t+1}+\gamma Q_{2}\left(S_{t+1}, \underset{a}{\arg \max } Q_{1}\left(S_{t+1}, a\right)\right)-Q_{1}\left(S_{t}, A_{t}\right)\right] \]

  每步学习可以等概率的选择其中的一个动作价值函数:

  Double Q-learning 加倍了内存开销,但是却没有增加额外的计算开销。

总结

  时序差分更新与回合更新的区别就在于,时序差分更新汲取了动态规划方法中“自益”的思想。本文也介绍了几种经典的无模型时序差分更新方法,包括同策算法 SARSA 和 异策算法 Q-learning,以及它们的一些衍生品。

Refer

相关内容


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. 同策时序差分更新
    1. 2.1. 时序差分更新策略评估
    2. 2.2. SARSA(State-Action-Reward-State-Action)
    3. 2.3. 期望 SARSA 算法(Expected SARSA)
  3. 3. 异策时序差分更新
    1. 3.1. 基于重要性采样的异策算法
    2. 3.2. Q-learning
    3. 3.3. Double Q-learning
  4. 4. 总结
  5. 5. Refer
  6. 6. 相关内容
您是第 位小伙伴 | 本站总访问量 | 已经写了 670.5k 字啦

载入天数...载入时分秒...