Warning: session_start() expects parameter 1 to be array, string given in /www/wwwroot/blog/wp-includes/class-wp-hook.php on line 288
强化学习——蒙特卡洛方法 | 野风
  • 欢迎访问我的个人博客,如遇博客图片无法显示,请用IE浏览器访问。
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧!

强化学习——蒙特卡洛方法

强化学习 野风同学 1年前 (2020-06-22) 1650次浏览 0个评论 扫描二维码

学习目标

  1. 理解Prediction和Control的差别;
  2. 理解什么是first-visit和every-visit;
  3. 理解什么是on-policy和off-policy;
  4. 理解蒙特卡洛方法的Prediction和Control问题;

Prediction和Control

其实这两个名词在总结动态规划方法的文章中也提到过了,但是没有细说,这里再简单的说明一下。预测(Prediction)和控制(Control)是MDP中的两类问题:

预测问题

  • 输入:MDP \langle\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma\rangle 和策略 \pi
  • 输出:状态值函数 v_{\pi} 或者状态动作值函数q_{\pi}

控制问题

输入:MDP \langle\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma\rangle
输出:最优状态值函数 v_{*} 或者最优状态动作值函数 q_{*},和最优策略 \pi_{*}

比如上一节的动态规划方法,两者的对应关系如下图:

蒙特卡洛方法简述

动态规划方法是建立在模型已知的情况下,但是往往大多数情况下模型是未知的,实际应用中我们不可能完全了解一个环境的所有知识,比如说得出它的状态转移矩阵。这个时候蒙特卡洛算法就派上用场了,它只需要从经验(experience)中去学习,这个经验包括样本序列的状态(state)、动作(action)和奖励(reward)。得到若干样本的经验后,通过平均所有样本的回报(return)来解决强化学习的任务。

类似于DP方法,MC求解也可以看作是一种广义的策略迭代过程,即先计算当前策略所对应的值函数,再利用值函数来改进当前策略,不断循环这两个步骤,从而得到最优值函数和最优策略。两个步骤细节上与DP不同,下面就慢慢道来。

蒙特卡洛方法的预测问题——策略评估

回想一下值函数的求解公式,即回报的期望:

v_{\pi}(s)=\mathbb{E}_{\pi}\left[G_{t} | S_{t}=s\right]

但是蒙特卡洛方法在策略评估时不是求的回报的期望,而是使用经验平均回报(empirical mean return)。随着我们的样本越来越多,这个平均值是会收敛于期望的。

一个episode就可以看作是一个样本,假设对于状态 s ,给定策略 \pi ,要计算其值函数 v_{\pi}(s) 。在一个episode中,每次状态 出现都称为一次visit,当然在一个episode中, s 可能出现多次。我们称第一次出现该状态为first-visit,因此first-visit蒙特卡洛方法(first-visit MC method)就是将所有第一次访问到 s 得到的回报求均值。根据大数定理,当样本足够大的时候,该均值就趋近于 v_{\pi}(s)。顾名思义,every-visit蒙特卡洛方法(first-visit MC method)就是将所有访问到 s 得到的回报求均值。下面的算法就是估计v_{\pi}的first-visit MC方法:

说了这么多,估计状态值函数对于我们有用吗?回想一下DP方法中我们是怎么计算 v_{\pi}(s) 的:

v_{k+1}(s)=\sum_{a \in \mathcal{A}} \pi(a | s)\left(\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} v_{k}\left(s^{\prime}\right)\right)

我们是通过one step look ahead的方法来迭代求解的。但是此时我们并不知道模型的具体情况,状态转移矩阵也不知道,所以这种求法就行不通了!还记得当时我在强化学习——马尔科夫决策过程和贝尔曼方程这篇文章中提的一个问题吗?为什么要有状态值函数(state value
function)和状态动作值函数(state-action
function)这两个概念,明明一个状态值函数就可以表征我们强化学习的目标——最大化回报,学到这里就可以给一个说法了,因为在模型已知的时候,只用状态值函数就可以完全决定策略,而模型未知的时候就必须估计每个动作的值,即状态动作值函数。所以,蒙特卡洛了方法就是去得到 q_{*} ,则对应的策略估计问题就是估计 q_{\pi}(s, a) ,即从状态 s开始,并采取动作a ,然后遵循策略 \pi 得到的回报的期望。根据上面的讨论,first-visit MC方法去估计 q_{\pi}(s, a) 就是求所有episode第一次访问 (s, a) 这个state-action pair所得到回报的均值。

蒙特卡洛方法的控制问题——策略提升

根据广义的策略迭代算法,得到值函数以后,下一步就是进行提升,进而得到最优值函数和最优策略。


\pi(s)=\arg \max _{a} q(s, a)
为了使这个过程收敛,我们是建立在两个假设上面的:
1. 策略估计过程需要无限个episode才会收敛到回报的期望;
2. Exploring starts,即能够保证状态集合 [公式] 中的所有状态都是有可能被选中为每个episode的初始状态。

显然,在实际的算法中这是不可能实现的,我们必须想法去掉这两个假设!先看第一个假设,其实这个假设我们在DP方法中也是遇到的,有两种方法可以去掉这个假设。

方法一:坚持在每次策略评估的过程中接近 q_{\pi k} 。有点懵是不是?这是sutton书中的一句话,原话是“One is to hold firm to the idea of approximating q_{\pi k} in each policy evaluation.”其实很简单,就是说虽然理论上必须有无限个episode来作为样本去评估 q_{\pi k},实际上是做不到的,我只能尽力多产生点episode,尽可能的去接近这个收敛值。我们可以设定一个误差,两次估计的值小于这个误差,差不多就行了。


方法二:既然要很多episode才能收敛,那么索性我就不管它收不收敛了,还记得DP方法中,在策略提升过程中我还用到的一个方法吗?就是值迭代(value iteration),这是一个极端的例子,就是在策略估计的时候只进行了一次迭代就转向策略提升了。速度是快了,但最后精度就降低了。


再看第二个假设,怎么解决exploring starts这个假设呢?我们一方面希望能找到最好的策略,另一方面又不知道当前策略是不是最好的,这就得去尝试不同的state action pair。一旦找到了一个更好的,如果一直沿着这个策略进行下去,那就有可能陷入局部最优解,进而找不到最优解了。

为了解决这个矛盾,书中提出了两种方法,就是我们说的on-policy和off-policy。所谓的on-policy就是生成episode的策略和迭代优化的策略是同一个,并且这个策略是一种软(soft)策略,即
\pi(a, s)>0 \text { for all } s \in \mathcal{S}, a \in \mathcal{A}

具体地,我们使用 \varepsilon-greedy 策略,以下算法就是使用该策略的On-policy first-visit MC control

On-policy方法在一定程度上解决了exploring starts这个假设,让策略既greedy又exploratory,最后得到的策略也一定程度上达到最优。Off-policy方法就更加直接了,分别在策略估计和策略提升的时候使用两种策略,一个具有探索性的策略专门用于产生episode积累经验,称为behavior policy \mu ,另一个则是更为贪婪,用来学习成为最优策略的target policy \pi 。为了利用从规则 \mu 产生的 episodes 来评估 \pi 的value,则我们需要规则\pi 下的所有行为在规则 \mu下被执行过,也就是要求对所有满足\pi(s, a)>0(s, a) 均有 \pi(s, a)>0 ,这个假设可以称为是“覆盖”(coverage)。

Off-policy预测问题中的重要性采样(Importance Sampling)

几乎所有off-policy方法使用的都是重要性采样,就是给定服从一种分布的样本情况下,估计另外一种分布下期望值的一般方法。我们根据轨迹在target policy和behavior policies 下发生的相关概率来对 returns 赋予权重,给定初始状态S_{t} ,state-action轨迹为 A_{t}, S_{t+1}, A_{t+1}, \dots, S_{T} 在规则 \pi 下发生的概率为

\prod_{k=t}^{T-1} \pi\left(A_{k} | S_{k}\right) p\left(S_{k+1} | S_{k}, A_{k}\right)

其中,p 代表的是 state-transition 概率函数,因此,轨迹在 target policiy 和 behavior policy 下发生的相关概率(即 importance-sampling ratio)为

\rho_{t: T-1}=\frac{\prod_{k=t}^{T-1} \pi\left(A_{k} | S_{k}\right) p\left(S_{k+1} | S_{k}, A_{k}\right)}{\prod_{k=t}^{T-1} \mu\left(A_{k} | S_{k}\right) p\left(S_{k+1} | S_{k}, A_{k}\right)}=\prod_{k=t}^{T-1} \frac{\pi\left(A_{k} | S_{k}\right)}{\mu\left(A_{k} | S_{k}\right)}

可以看出, \rho_{t: T-1} 与MDP没有关系,仅仅与两个规则相关。好了,为什么我们要求这个\rho_{t: T-1}?我们的目的是要估计一个规则,即求target policy下回报的期望,但现在我们是根据behavior policy生成的episode,得到的自然是一个错误的期望值 \mathbb{E}\left[G_{t} | S_{t}\right]=v_{\mu}\left(S_{t}\right),但我们要的是v_{\pi}\left(S_{t}\right) ,所以这个时候就该 \rho_{t: T-1} 发挥作用了!

\mathbb{E}\left[\rho_{t, T-1} G_{t} | S_{t}\right]=v_{\pi}\left(S_{t}\right)

好,接下来就要给出off-policy方法是如何评估策略的公式。现在假设我们有了一系列服从规则 \mu的episodes,首先我们对这些 episodes 进行连接和标号,假设第一个 episode 在时刻 100 结束,则第二个 episode 就以时间 101 开始,以此类推。下面规定一些符号表示:
- \mathcal{T}(s):对 every-visit 方法,它代表所有状态 s 被 visit 的时刻的集合,对 first-visit 方法,它仅代表所有状态 s 在某个 episode 中第一次被 visit 的时刻的集合;
- T(s) :从时刻t到T(s)的回报(return);
- \left\{G_{t}\right\}_{t \in \mathcal{T}(s)} :属于状态s的回报;
- \left\{\rho_{t: T-1}\right\}_{t \in \mathcal{T}(s)}:代表相应的importance-sampling ratio;

根据求平均的方法不同,有两种估计 v_{\pi}(s),一种是ordinary importance sampling:
V(s)=\frac{\sum_{t \in \mathcal{T}(s)} \rho_{t: T(t)-1} G_{t}}{|\mathcal{T}(s)|}
另一种是weighted importance sampling,

V(s)=\frac{\sum_{t \in \mathcal{T}(s)} \rho_{t: T(t)-1} G_{t}}{\sum_{t \in \mathcal{T}(s)} \rho_{t: T(t)-1}}

增量式求均值

在策略估计的时候,MC所采用的方法是将所有样本episodes所得到的回报求均值,怎么求这个均值呢?当然可以简单的求和再除以episode的数量。这里要介绍的是另一种方法——增量式求均值。

假设我们得到了一系列回报G_{1}, G_{2}, \ldots, G_{t-1},对于off-policy来说,因为我们利用了重要性采样,所以多了一个权重的因素,设每个回报的权重为W_{k}

V_{n}=\frac{\sum_{k=1}^{n-1} W_{k} G_{k}}{\sum_{k=1}^{n-1} W_{k}}

于是有

V_{n+1}=V_{n}+\frac{W_{n}}{C_{n}}\left(G_{n}-V_{n}\right) C_{n+1}=C_{n}+W_{n+1}

Off-policy的控制问题

前面两个小节就是在为这个小节做铺垫,所以直接给出算法啦。

学习资料

[1] Reinforcement Learning: An Introduction- Chapter 5: Monte Carlo Method
[2] David Silver's RL Course Lecture 4&5
[3] 强化学习入门 第三讲 蒙特卡罗方法
[4] 采样方法(一)


《Reinforcement Learning: An Introduction 第二版》PDF书籍与David Silver课程,欢迎关注我的公众号“野风同学”,回复“RL”即可获取。
一个程序员的自我成长之路,持续分享机器学习基础与应用、LeetCode面试算法和Python基础与应用等技术干货文章,同时也经常推荐高质量软件工具、网站和书籍。


本站提供的一切软件、教程和内容信息仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑或手机中彻底删除上述内容。如果您喜欢该程序,请支持正版,购买注册,得到更好的正版服务。如有侵权请邮件与我们联系处理。敬请谅解!
喜欢 (0)
[打赏赞助]
分享 (0)
野风同学
关于作者:
我是野风同学,这是我的主页。
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址