第四课 无模型的预测

这一课帅小哥主要讲的内容是预测的部分,在第五课会加入控制的部分。其中预测的部分主要是两个相似的算法,一个为 Monte-Carlo(MC),另一个为 Temporal-Difference(TD)。两者的区别主要在于,MC 为需要在出现终止状态后,才能得到 Reward,而 TD 则是实时的

Monte-Carlo

Monte-Carlo强化学习指的是,在不清楚 MDP 状态转移和奖励方案的情况下,直接通过经历完整的 episode 来学习状态的 value。一般而言,一个状态的 value 为,其在多个 episode 下的 value 的平均值。

注:episode 指的是不定的起始状态开始,直到某一特定的终止状态结束。

其评价每个状态的 value 的主要算法如下两种:

  • 首次访问 Monte-Carlo 策略评估 首先,固定一个策略 $\pi$ ,之后使用这个策略进行多个完整的 episode。对于每个 episode,当且仅当状态第一次出现时才列入计算:
    1
    2
    3
      N(s) = N(s) + 1 # 状态计数 +1
      S(s) = S(s) + G_t # 总收获更新
      V(s) = V(s) / N(s) # 状态的 value 更新
    

    注:当 N 很大时, $V(s)$ 就是我们所求估计

  • 每次访问 Monte-Carlo 策略评估 同首次访问 MC 算法一致,但是这个算法中,每次出现在状态转移链中的状态都会更新。

Temporal-Difference

首先,在开始 TD 算法前,小哥补充了一个 baby math,即一个求平均值的操作其实是可以写成一种迭代的样式如下:

\[\begin{split} \mu_k &= \frac{1}{k} \sum_{j=1}^k x_j \\ &= \mu_{k-1} + \frac{1}{k}(x_k-\mu_{k-1}) \end{split}\]

再抽象点就得到了以下公式:

\[\begin{split} V(S_t) &= V(S_t) + \frac{1}{N(S_t)}(G_t - V(S_t)) \\ & = V(S_t) + \alpha(G_t - V(S_t)) \end{split}\]

而 TD 算法就是从这里开始的。TD 算法和 MC 算法不同的地方在于,其不用完成整个 episode 才得到状态的 value,即它可以学到一个不完整的 episode,通过自身的引导(bootstrapping)来猜测结果。其公式如下:

\[V(S_T) = V(S_t) + \alpha(R_{t+1} + \gamma V(S_{t+1}) - V(S_t))\]

注:其中 $R_{t+1}$ 为离开该状态的时候的即刻奖励, $S_{t+1}$ 为下一状态的预估状态价值。

TD 与 MC 的对比

  1. TD 可以在知道最终结果前就可以学习,MC 必须在 episode 结束后才知道。 注:小哥举了个例子,说你不能在被车撞死后再重来。
  2. MC 是基于某一个策略的无偏估计,而 TD 则是有偏估计。(毕竟 TD 瞎猜了)
  3. MC 没有 bias,但是有较高的变异性(Variance),对初值不敏感,而 TD 有 bias,低变异性,但效率高。

注:MDP、TD 和 MC 都是计算状态 value 的方案

参考资料

  • 本文作者: Author:DeamoV
  • Github:https://github.com/VDeamoV
  • Email:vincent.duan95@outlook.com
  • 本文链接: Artical: 第四课 无模型的预测
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
  • 版权声明: 原创文章如转载,请注明出处