[ 强化学习  ]

强化学习基础 4:蒙特卡洛方法

之前介绍的 DP 方法有一个重要的缺陷:需要知道环境的先验的知识(即环境的动态)。而本文介绍的蒙特卡洛方法则没有这个约束,它直接从经验中学习,因此适用范围更广,并且在计算效率上更有巨大优势。

蒙特卡洛方法仅仅适用于 episodic 的任务。其核心思想是将每一轮的轨迹中每个状态的 return 采样下来,将多轮采样取平均值,以此作为每个状态 value 的估计值。因此更新过程发生在每一轮 (episode-by-episode),而不是每一步 (step-by-step,也叫 online)。

一、蒙特卡洛预测

像 DP 中一样,预测的意思是计算给定的 policy 对应的价值函数。如之前所说,蒙特卡洛估计 state-value 的方法是从采样中求平均

方法

这里有两种方法:对每个状态 $s$,一种方法是对第一次访问 $s$ 之后所获得 return 求平均;另一种方法是对每次访问 $s​$ 之后所获得 return 求平均。前者被称为 first-visit MC method,后者被称为 every-visit MC method。First-visit MC 方法的研究较为成熟,因此我们主要考虑这种方法,并给出其算法:

\begin{algorithm}
\caption{First-visit MC prediction}
\begin{algorithmic}
\INPUT $\pi$, policy to be evaluated
\OUTPUT $V\approx v_\pi$

\STATE initialize $V(s)\in\mathbb{R}$, arbitrarily, for all $s\in\mathcal{S}$
\STATE $Returns(s)\gets$ an empty list, for all $s\in\mathcal{S}$
\REPEAT
	\STATE Generate a trajectory following $\pi:S_0,A_0,R_1,S_1,A_1,\dots,S_{T-1},A_{T-1},R_T$
	\STATE $G \gets 0$
	\FORALL{$t=T-1,T-2,\dots,0$}
		\STATE $G\gets\gamma G+R_{t+1}$
		\IF{\NOT $S_t$ appears in $S_0,S_1,\dots,S_{t-1}$}
			\STATE Append $G$ to $Returns(S_t)$
			\STATE $V(S_t)\gets$ average($Returns(S_t)$)
		\ENDIF
	\ENDFOR
\UNTIL{$V$ is stable}
\RETURN $V$
\end{algorithmic}
\end{algorithm}

对于 first-visit MC 方法,由于对每个 $s$,从它采样的 return 是独立同分布的,并且方差有限 (?),所以根据大数定理(伯努利大数定理),采样的平均值在随着采样次数的增加依概率收敛到 return 的期望值 $v_\pi(s)$。对于 every-visit MC,证明没有这么直接,但同样有理论依据证明它收敛到 $v_\pi(s)$。

与 DP 对比

MC 方法可以从实际经验或模拟经验中学习,不需要环境的先验知识,因此适用范围更广;MC 仅仅计算采样的部分,不需要对所有状态空间都计算,因此计算效率更高(例如,MC 可以仅仅计算某个你关心的状态的 value,其他状态都可以不计算。毕竟 MC 不是 bootstrapping 方法,不需要其他状态的估计值)。

二、动作价值的蒙特卡洛估计

如果有了状态价值函数 $v$,要获得相应的贪婪策略 $\pi$,还是需要环境的模型 $p$:

所以,如果完全没有环境的模型,我们必须先获得动作价值函数 $q$,然后用下式来获得策略:

估计动作价值函数的方法和上一节一样,也是从采样取平均,这里的采样是每个 state-action pair 对应一个 return 。

但问题在于:对于已有的策略,很多 state-action pair 根本不会出现。极端情况是对于一个确定性策略,每个状态 $s$ 只可能出现一个 $(s, \pi(s))$。这违背了我们采样的意愿:我们的目标是尽可能尝试多种 state-action pair 并找到哪种选择的价值最大。这个问题叫做维持探索性问题 (maintaining exploration)

解决这个问题的一种方法是提出这样的假设:每一轮开始于一个 state-action pair,每个 state-action pair 被选中的概率都不是 0. 这样随着轮数趋于无穷,每个 state-action pair 被选中的次数也会趋于无穷。这种假设被称为探索性开端 (exploring starts)

但这个假设在很多情况下不成立,尤其是在从实际经验中采样的时候。所以还有其他方法,例如仅仅考虑随机性策略 (stochastic policy),这种策略在每个状态选择每个动作的概率都不为 0。这一类方法将在后面讨论,现在我们主要先看一下基于 exploring starts 假设的方法。

三、蒙特卡洛控制

现在考虑 MC 方法如何获得最优策略,这也叫做蒙特卡洛控制 (Monte Carlo Control)。这里的想法是用之前提到的 GPI 范式来完成:evaluation 的部分就是上一节介绍的动作价值的估计;improvement 部分通过 $\pi_{k+1}(s)\gets \argmax_aq_{\pi_k}(s,a)​$ 来完成。

这里 evaluation 部分仍然和上一节说的一样,建立在两个假设上:

  1. 能够观察到无穷个 episode (轮数趋于无穷)
  2. exploring starts 假设

这两个假设在实际场景下很难实现,所以要尽量去掉这两个假设。对于第一个假设,我们可以像之前 Value-Iteration 算法一样,在 evaluation 的时候不需要到达完全的“真值”(通过无穷次采样的迭代),只需要向目标更接近即可。一种极端情况是仅通过一次采样(一个轨迹/episode)来进行 evaluation, evaluation 完后直接 improvement。这就是下面的 Monte Carlo ES (Exploring Starts) 算法

\begin{algorithm}
\caption{Monte Carlo ES (Exploring Starts)}
\begin{algorithmic}
\OUTPUT $\pi\approx\pi_\ast$

\STATE Initialize $\pi(s)\in\mathcal{A}(s)$ (arbitrarily), for all $s\in\mathcal{S}$
\STATE Initialize $Q(s,a)\in\mathbb{R}$ (arbitrarily), for all $s\in\mathcal{S},a\in\mathcal{A}$
\STATE Initialize $Returns(s,a)\gets$ emtpy list, for all $s\in\mathcal{S},a\in\mathcal{A}$
\REPEAT
	\STATE Choose $S_0\in\mathcal{S},A_0\in\mathcal{A}(S_0)$ randomly such that all pairs have probability $>0$
	\STATE Generate a trajectory following $\pi:S_0,A_0,R_1,S_1,A_1,\dots,S_{T-1},A_{T-1},R_T$
	\STATE $G \gets 0$
	\FORALL{$t=T-1,T-2,\dots,0$}
		\STATE $G\gets\gamma G+R_{t+1}$
		\IF{\NOT $S_t,A_t$ appears in $S_0,A_0,S_1,A_1,\dots,S_{t-1},A_{t-1}$}
			\STATE Append $G$ to $Returns(S_t,A_t)$
			\STATE $Q(S_t,A_t)\gets$ average($Returns(S_t,A_t)$)
			\STATE $\pi(S_t)\gets\argmax_aQ(S_t,a)$
		\ENDIF
	\ENDFOR
\UNTIL{$\pi$ is stable}
\RETURN $\pi$
\end{algorithmic}
\end{algorithm}	

四、无 Exploring Starts 假设的蒙特卡洛控制

如果要去掉 Exploring Starts 的假设,我们就需要有某种方法使得在每个状态下的每个动作都有概率被选中。

实现这个要求的方法可以分为两类:on-policy 方法off-policy 方法——on-policy 方法在使用某个 policy 做决策的同时对该 policy 进行改进和评估;off-policy 用来做决策的 policy 和它尝试改进的 policy 不是同一个 policy。之前我们讨论的方法都属于 on-policy 方法。

在 On-policy 控制方法中,策略通常是 soft 的,意思是这个策略对于每个状态 $s\in\mathcal{S}$ 和动作 $a\in\mathcal{A}(s)$,都有 $\pi(a\vert s)>0$,但是它通过学习过程越来越接近一个确定性的最优策略。实现这种 soft 方法的一种自然的想法是使用 Multi-Armed Bandit 中的 $\varepsilon$-greedy 方法——在每个状态 $s$,有 $\varepsilon$ 的概率会随机探索,这样能保证所有动作都至少有 $\frac{\varepsilon}{\vert \mathcal{A}(s)\vert}$ 的概率被选中(而最优动作 $a_\ast$ 被选中的概率还要加上贪婪概率 $1-\varepsilon$,即 $1-\varepsilon+\frac{\varepsilon}{\vert \mathcal{A}(s)\vert}$)。

$\varepsilon$-greedy 策略是 $\varepsilon$-soft 策略的一种实例($\varepsilon$-soft 策略定义为:对某个 $\varepsilon>0$ 和任意状态和动作,有 $\pi(a\vert s)\ge\frac{\varepsilon}{\vert \mathcal{A}(s)\vert}$),在所有 $\varepsilon$-soft 策略中,$\varepsilon$-greedy 策略是最接近贪婪策略的。

本节的 $\varepsilon$-soft 方法和上一个 Monte Carlo ES 算法的一个重要区别在于 policy 从确定性变成随机性了。

\begin{algorithm}
\caption{On-policy first-visit MC control (for $\varepsilon$-soft policies)}
\begin{algorithmic}
\Input $\varepsilon>0$
\Output $\pi\approx\pi_\ast$

\STATE Initialize $\pi(s)\in\mathcal{A}(s)$ (arbitrarily), for all $s\in\mathcal{S}$
\STATE Initialize $Q(s,a)\in\mathbb{R}$ (arbitrarily), for all $s\in\mathcal{S},a\in\mathcal{A}$
\STATE Initialize $Returns(s,a)\gets$ emtpy list, for all $s\in\mathcal{S},a\in\mathcal{A}$
\REPEAT
	\STATE Choose $S_0\in\mathcal{S},A_0\in\mathcal{A}(S_0)$ randomly such that all pairs have probability $>0$
	\STATE Generate a trajectory following $\pi:S_0,A_0,R_1,S_1,A_1,\dots,S_{T-1},A_{T-1},R_T$
	\STATE $G \gets 0$
	\FORALL{$t=T-1,T-2,\dots,0$}
		\STATE $G\gets\gamma G+R_{t+1}$
		\IF{\NOT $S_t,A_t$ appears in $S_0,A_0,S_1,A_1,\dots,S_{t-1},A_{t-1}$}
			\STATE Append $G$ to $Returns(S_t,A_t)$
			\STATE $Q(S_t,A_t)\gets$ average($Returns(S_t,A_t)$)
			\STATE $A^\ast\gets\argmax_aQ(S_t,a)$
			\FORALL{$a\in\mathcal{A}(S_t)$}
				\STATE $\pi(a\vert S_t)\gets\begin{cases}1-\varepsilon+\frac{\varepsilon}{\vert \mathcal{A}(s)\vert}\quad&\text{if }a=A^\ast\\\frac{\varepsilon}{\vert \mathcal{A}(s)\vert}\quad&\text{if }a\ne A^\ast\end{cases}$
			\ENDFOR
		\ENDIF
	\ENDFOR
\UNTIL{$\pi$ is stable}
\RETURN $\pi$
\end{algorithmic}
\end{algorithm}