David silver 强化学习 Lecture 5

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

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

介绍

上一讲介绍不基于模型的预测,即对未知的MDP预测其价值函数;这一讲介绍不基于模型的控制,即对于未知的MDP优化其价值函数。

On-Policy Monte-Carlo Control

  • 关于$V(s)$做策略提升需要MDP模型:

  • 关于$Q(s,a)$做策略提升不需要模型

$\epsilon-$贪婪搜索

这里老师举了一个例子:

  • 有两扇门在我们面前
  • 打开左门得到$0$奖励,$V(\text{left})=0$
  • 打开右门得到$+1$奖励,$V(\text{right})=+1$
  • 打开右门得到$+3$奖励,$V(\text{right})=+2$
  • 打开右门得到$+2$奖励,$V(\text{right})=+2$
  • 我们是否选择了最好的门呢?

上述问题的答案显然是否定的,但是如果按照通常的方法则会一直选右门,为了解决这个问题,可以使用$\epsilon-$贪婪搜索:

  • $\epsilon-$贪婪搜索是确保连续搜索的最简单方法
  • 思路是以非零概率尝试所有$m$个动作
  • 以$1-\epsilon$的概率选择贪婪动作
  • 有$\epsilon$的概率随机选择一个动作
$\epsilon-$贪婪策略提升

关于$\epsilon-$贪婪搜索有如下定理:

定理

对于任意$\epsilon-$贪婪策略$\pi$,关于$q_\pi$的$\epsilon-$贪婪策略$\pi ‘$是一个提升,$v_{\pi^{\prime}}(s) \geq v_{\pi}(s)$

证明:

其中不等号是因为最大值大于等于所有值的加权和。

由上式可得

GLIE

GLIE的全称为Greedy in the Limit with In nite Exploration

  • 所有状态-动作对都经过了无数次探索,

  • 策略收敛到贪婪策略

例如,$\epsilon-$贪婪是GLIE如果$\epsilon_k =\frac 1 k$

GLIE MC控制
  • 利用$\pi:\left\{S_{1}, A_{1}, R_{2}, \ldots, S_{T}\right\} \sim \pi$采样$k$幕

  • 在每一幕中,对每个状态$S_t$和动作$A_t$,

  • 基于新的动作价值函数改进策略

上述方法的有效性由如下定理保证:

定理

GLIE MC收敛到最优动作价值函数,$Q(s, a) \rightarrow q_{*}(s, a)$

On-Policy Temporal-Difference Learning

  • 自然的想法:在我们的循环中使用TD而不是MC
    • 将TD应用于$Q(S, A)$
    • 使用$\epsilon-$贪婪策略提升
    • 实时更新
$\text{Sarsa}(\lambda)$

一个具体例子是$\text{Sarsa}(\lambda)$,思路如下:

伪代码为:

Sarsa的收敛性

Sarsa的收敛性由如下定理保证:

定理

Sarsa在如下条件下收敛到最优动作价值函数$Q(s, a) \rightarrow q_{*}(s, a)$

  • 策略$\pi_t(a|s)$是GLIE序列

  • 步长大小$\alpha_t$满足:

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

  • 定义$n$步回报

  • $n$步Sarsa根据$n$步Q回报更新$Q(s,a)$

$\text{Sarsa}(\lambda)$的前向视角

$\text{Sarsa}(\lambda)$和$\text{TD}(\lambda)$的思路一致,可以用下图表示:

  • $q^{\lambda}$回报结合了所有$n$步$Q$回报$q_t^{(n)}$

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

  • $\text{Sarsa}(\lambda)$的前向视角(Forward-view)

$\text{Sarsa}(\lambda)$的反向视角
  • 类似$\text{TD}(\lambda)$,首先定义合格轨迹:
  • 对于每个状态$s$和动作$a$更新$Q(s,a)$

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

$\text{Sarsa}(\lambda)$算法

Off-Policy Learning

  • 在遵循策略$\mu(a|s)$

    的条件下,通过评估目标策略$\pi(a|s)$以计算$v_\pi(s)$或$q_\pi(s,a)$

  • 为什么这很重要?

    • 通过观察人类或其他智能体学习
    • 重用旧策略$\pi_{1}, \pi_{2}, \ldots, \pi_{t-1}$带来的经验
    • 在遵循探索性策略的同时学习最佳策略
    • 遵循一项策略时了解多种策略
重要性抽样
Off-Policy MC的重要性抽样
  • 通过$\mu$的回报评估$\pi$

  • 根据策略之间的相似性得出权重回报$G_t$

  • 在整个幕中乘以重要性抽样校正

  • 根据校正回报更新价值

  • 当$\pi$是非零但$\mu$是零时无法使用

  • 重要性抽样可以大幅减少方差

Off-Policy TD的重要性抽样
  • 使用$\mu$生成的TD目标来评估$\pi$

  • 通过重要性抽样加权TD目标$R+\gamma V\left(S^{\prime}\right)$

  • 只需要一次重要性抽样校正

  • 比MC重要性抽样的方差小很多

  • 策略只需要在一步中相似

Q-Learning
  • 现在我们考行Off-Policy的动作价值$Q(s,a)$的学习

  • 不需要重要性抽样

  • 下一个动作根据行为策略选择$A_{t+1} \sim \mu\left(\cdot | S_{t}\right)$

  • 但是我们考虑替代性的后续动作$A^{\prime} \sim \pi\left(\cdot | S_{t}\right)$

  • 并将$Q\left(S_{t}, A_{t}\right)$更新为替代动作的价值

使用Q-Learning进行Off-Policy控制
  • 现在,我们允许动作和目标策略都得到提升

  • 目标策略关于$Q(s,a)$贪心

  • 行为策略$\mu$关于$Q(s,a)$是$\epsilon -$贪心

  • 那么Q-Learning的目标得到化简:

Q-Learning控制算法

根据之前讨论得到如下算法:

上述算法的有效性由如下定理保证:

定理

Q-learning控制收敛到最优动作价值函数:$Q(s, a) \rightarrow q_{*}(s, a)$

完整算法的伪代码如下:

总结

DP和TD的关系

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

文章作者:Doraemonzzz

发布时间:2019年12月04日 - 14:45:00

最后更新:2019年12月09日 - 15:10:25

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

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