David silver 强化学习 Lecture 4

课程主页: http://web.stanford.edu/class/cs234/index.html

这里回顾David silver 强化学习 Lecture 4的课程内容,这一讲简单介绍了不基于模型的预测。

介绍

上一讲介绍了如何通过DP进行规划,那里假设MDP已知;这一讲介绍不基于模型的预测,即对未知的MDP预测其价值函数。

蒙特卡洛学习

  • 目标:通过策略$\pi$下的信息学习$v_\pi$

  • 注意回报(return)是折扣奖励:

  • 回报价值函数是回报(return)的期望:

  • 蒙特卡洛策略评估使用经验均值回报而非预期回报

具体方式如下:

  • 为了评估状态$s$
  • 在一幕(episode)中访问状态$s$的第一个(每一个)时间戳$t$
  • 增加计数器$N(s) \leftarrow N(s)+1$
  • 增加总回报$S(s) \leftarrow S(s)+G_{t}$
  • 价值通过回报的均值估计$V(s) = S(s)/N(s)$
  • 根据大数定律,随着$N(s)\to \infty$,$V(s) \rightarrow v_{\pi}(s)$
增量均值

序列$x_1,x_2,\ldots$的均值$\mu_1,\mu_2,\ldots$可以通过增量方式计算:

增量MC更新
  • 根据上述公式,可以通过增量方式更新$V(s)$

  • 对于回报为$G_t$的状态$S_t$

  • 在非平稳问题中,跟踪连续平均值(即忘掉旧幕(episodes))可能很有用。

时序差分学习(Temporal-Difference Learning)

  • 首先考虑最简单的时序差分算法:$TD(0)$

    • 通过估计回报$R_{t+1}+\gamma V\left(S_{t+1}\right)$更新$V(S_t)$

    • $R_{t+1}+\gamma V\left(S_{t+1}\right)$被称为TD目标

    • $\delta_{t}=R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right)$被称为TD误差

MC vs TD的优劣势对比(1)
  • TD在知道最终结果之前就可以学习
    • TD可以在每一步后在线学习
    • MC必须等到每一幕结束后能知道回报
  • TD可以在不知道最终结果的条件下学习
    • TD可以从不完全序列中学习
    • MC只能从完全序列中学习
    • TD可以在连续(非终止)环境中运行
    • MC只能在幕(终止)环境中运行
偏差/方差权衡
  • 回报$G_{t}=R_{t+1}+\gamma R_{t+2}+\ldots+\gamma^{T-1} R_{T}$是$v_\pi (S_t)$的无偏估计
  • 真正的TD目标$R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right)$是$v_\pi (S_t)$的无偏估计
  • TD目标$R_{t+1}+\gamma V\left(S_{t+1}\right)$是$v_\pi (S_t)$的有偏估计
  • TD目标比回报的方差要小的多:
    • 因为回报依赖于很多随机动作,转移以及奖励
    • TD目标只依赖一个随机动作,转移以及奖励
MC vs TD的优劣势对比(2)
  • MC有高方差,无偏
    • 很好的收敛性
    • 对初始值不敏感
    • 很好理解和使用
  • TD有低方差,有偏
    • 通常比MC更高效
    • TD(0)收敛于$v_\pi(s)$
    • 对初始值更敏感
批量MC和TD
  • MC和TD都收敛:$V(s)\to v_\pi(s)$随着经验$\to \infty$

  • 但是对于有限经验的批处理解决方案呢?

    • 例如:重复对第$k\in [1,K]$幕采样
    • 对第$k$幕应用MC或$TD(0)$
MC vs TD的优劣势对比(3)

由TD的表达式,不难得到

  • TD利用了马尔可夫性
    • 通常在马尔可夫环境下更高效
  • MC没有利用马尔可夫性
    • 通常在非马尔可夫环境下更高效
对比
MC

TD

DP

Bootstrapping和采样
  • Bootstrapping:更新涉及估计
    • MC不使用Bootstrap
    • DP使用Bootstrap
    • TD使用Bootstrap
  • 采样:
    • MC使用采样
    • DP不使用采样
    • TD使用采样

$TD(\lambda)$

假设$TD$查看未来的$n$步

$n$步回报
  • 考虑如下$n$步回报:

  • 定义$n$步回报

  • $n$步时序差分学习

$\lambda$回报

接下来考虑对不同步数的回报做加权:

  • $\lambda-$回报$G_t^\lambda $结合了所有$n$步回报$G_t^{(n)}$

  • 使用权重$(1-\lambda) \lambda^{n-1}$

  • $TD(\lambda)$的前向视角(Forward-view)

$TD(\lambda)$的前向视角

  • 通过$\lambda-$回报更新价值函数
  • 通过对未来的前瞻性计算$G_t^{\lambda}$
  • 像MC一样,只能根据完整的幕(episodes)计算
$TD(\lambda)$的反向视角
  • 前向视角提供理论
  • 反向提供了机制
  • 从不完整的序列在线更新每一步

为了讨论反向视角,首先定义合格轨迹:

  • 保持每个状态$s$的合格轨迹$E_t(s)$

  • 对每个状态$s$更新$V(s)$

  • 更新项正比于TD-误差$\delta_t$和合格轨迹$E_t(s)$

$TD(\lambda)$和$TD(0)$
  • 当$\lambda =0$,只有当前状态被更新

  • 这等价于$TD(0)$更新

$TD(1)$和MC
  • 考虑在时间戳$k$一次访问$s$的一幕

  • 考虑$TD(1)$的合格轨迹

  • $TD(1)$更新在线累积误差

  • 在幕结束时,累计误差为

  • 利用公式$ \delta_{t} =R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right)$对其处理可得

  • 所以

更一般的,我们有如下定理:

定理

对于$TD(\lambda)$的前向视角和后向视角,所有更新的总和是相同的:

总之,$TD(1)$几乎等价于MC

离线更新

离线更新

  • 更新在一幕中累积
  • 但在幕结束时批量应用
在线更新
  • $TD(\lambda)$在每一幕的每一步中都进行更新
  • $TD(\lambda)$的前向反向视角有所不同
总结

本文标题:David silver 强化学习 Lecture 4

文章作者:Doraemonzzz

发布时间:2019年12月03日 - 23:16:00

最后更新:2019年12月04日 - 15:27:24

原始链接:http://doraemonzzz.com/2019/12/03/David silver 强化学习 Lecture 4/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。