【强化学习】5-基于蒙特卡洛的强化学习方法
Categories: RL
目录
一、例子
上一节的算法是model-based的，本节方法是基于model-free的，首先看一个例子：
以扔硬币为例，结果为正面或反面设为随机变量 $X$ ：
- 如果结果为正面，$X=+1$
- 如果结果为反面，$X=-1$
我们的目标是计算：$\mathbb{E}[X]$
方法1：model-based
假设已知概率模型为：\(p(X = 1)=0.5,\ p(X=-1)=0.5\) 根据定义，期望 \(\mathbb{E}[X]=\sum_{x}xp(x)=1\times0.5+(-1)\times0.5 = 0\) 问题：可能无法得知精确的分布。
方法2：model-free
思路：多次抛硬币，然后计算结果的平均值。假设我们得到一个样本序列：\(\{x_1, x_2, \ldots, x_N\}\) 那么，均值可以近似为：\(\mathbb{E}[X] \approx \bar{x}=\frac{1}{N}\sum_{j = 1}^{N}x_j\) 这就是蒙特卡罗估计（Monte Carlo Estimation）的思路。
大数定律（Law of Large Numbers）
对于随机变量 $X$ 。假设 ${x_j}_{j = 1}^{N}$ 是一些独立同分布（independent and identically distributed，iid）的样本。令 $\bar{x}=\frac{1}{N}\sum_{j = 1}^{N}x_j$ 为样本的平均值。那么：
- 期望：$\mathbb{E}[\bar{x}]=\mathbb{E}[X]$
- 方差：$\text{Var}[\bar{x}]=\frac{1}{N}\text{Var}[X]$
因此，$\bar{x}$ 是 $\mathbb{E}[X]$ 的无偏估计，并且随着 $N$ 增加到无穷大，其方差减小到零。
二、MC Basic 算法
1. 算法介绍
本算法的关键在于理解如何将策略迭代算法转换为model-free的。
策略迭代在每次迭代中有两个步骤：
- 策略评估（Policy evaluation）：$v_{\pi_k}=r_{\pi_k}+\gamma P_{\pi_k}v_{\pi_k}$
- 策略改进（Policy improvement）：$\pi_{k + 1}=\arg\max_{\pi}(r_{\pi}+\gamma P_{\pi}v_{\pi_k})$
策略改进步骤的逐元素形式为： \(\begin{equation} \begin{aligned} \pi_{k + 1}(s)&=\arg\max_{\pi}\sum_{a}\pi(a|s)\left[\sum_{r}p(r|s,a)r+\gamma\sum_{s'}p(s'|s,a)v_{\pi_k}(s')\right]\\ &=\arg\max_{\pi}\sum_{a}\pi(a|s)q_{\pi_k}(s,a),\ s\in\mathcal{S} \end{aligned} \end{equation}\)
model-based 和 model-free 关键在于 $q_{\pi_k}(s,a)$ 是否已知。
动作价值的两种表达式：
- 第一种需要模型： \(\begin{equation} q_{\pi_k}(s,a)=\sum_{r}p(r|s,a)r+\gamma\sum_{s'}p(s'|s,a)v_{\pi_k}(s') \end{equation}\)
- 第二种不需要模型（$q_{\pi_k}(s,a)$ 的定义）： \(\begin{equation} q_{\pi_k}(s,a)=\mathbb{E}[G_t|S_t = s,A_t = a] \end{equation}\)
实现无模型强化学习（model-free RL）的思路：我们可以使用第二种表达式，基于数据（样本或经验）来计算 $q_{\pi_k}(s,a)$ 。
动作价值的蒙特卡罗估计过程：
- 从 $(s, a)$ 出发，遵循策略 $\pi_k$ ，执行一个回合（episode）。
- 这个回合的回报是 $g(s, a)$ 。
- $g(s, a)$ 是 $q_{\pi_k}(s,a)=\mathbb{E}[G_t|S_t = s,A_t = a]$ 中 $G_t$ 的一个样本。
- 假设我们有一组回合，即有集合 ${g^{(j)}(s, a)}$ 。那么， \(\begin{equation} q_{\pi_k}(s,a)=\mathbb{E}[G_t|S_t = s,A_t = a]\approx\frac{1}{N}\sum_{i = 1}^{N}g^{(i)}(s,a) \end{equation}\)
基本思想：当模型不可用时，可以使用数据。
更进一步给出算法的具体描述：
给定初始策略 $\pi_0$ ，在第 $k$ 次迭代时有两个步骤。
- 步骤1：策略评估。此步骤是为了获取所有 $(s, a)$ 对应的 $q_{\pi_k}(s, a)$ 。具体来说，对于每个 $(s, a)$ ，运行无限次（或足够多次）的回合。这些回合回报的平均值用于近似 $q_{\pi_k}(s, a)$ 。
- 步骤2：策略改进。此步骤是为所有 $s \in \mathcal{S}$ 求解 $\pi_{k + 1}(s)=\arg\max_{\pi}\sum_{a}\pi(a|s)q_{\pi_k}(s, a)$ 。贪婪最优策略是 $\pi_{k + 1}(a_k^*|s)=1$ ，其中 $a_k^*=\arg\max_{a}q_{\pi_k}(s, a)$ 。
该算法与策略迭代算法几乎完全相同，除了第一步，本算法是直接估计 $q_{\pi_k}(s, a)$ ，而不是求解 $v_{\pi_k}(s)$ 。
2. 伪代码
伪代码：MC Basic 算法（策略迭代的model-free变体）
初始化：初始猜测策略$\pi_0$。 目标：搜索最优策略。
当值估计未收敛时，对于第 $k$ 次迭代，执行以下操作： \(\begin{aligned} &\text{For every state } s \in \mathcal{S}, \text{ do} \\ &\quad \quad \text{For every action } a \in \mathcal{A}(s), \text{ do} \\ &\quad \quad \quad \quad \text{Collect sufficiently many episodes starting from } (s, a) \text{ following } \pi_k \\ &\quad \quad \quad \quad \text{MC-based policy evaluation step: } \\ &\quad \quad \quad \quad q_{\pi_k}(s,a) = \text{average return of all the episodes starting from } (s, a) \\ &\quad \quad \text{Policy improvement step:} \\ &\quad \quad a_k^*(s)=\arg\max_{a}q_{\pi_k}(s,a) \\ &\quad \quad \pi_{k + 1}(a|s)=1 \text{ if } a = a_k^*, \text{ else } \pi_{k + 1}(a|s)=0 \end{aligned}\)
说明：
-
MC Basic 算法在揭示基于MC的模型无关强化学习的核心思想方面是有用的，但由于效率低下而不实用。
-
为什么MC Basic估计动作值而不是状态值？因为状态值不能直接用于改进策略，最终还是会转换为动作值。因此，当模型不可用时，我们应该直接估计动作值。
三、MC Exploring Starts 算法
考虑一个网格世界的例子，按照策略 $\pi$ ，我们可以得到一个episode，例如：
\[\begin{equation*} s_1\xrightarrow{a_2}s_2\xrightarrow{a_4}s_1\xrightarrow{a_2}s_2\xrightarrow{a_3}s_5\xrightarrow{a_1}\cdots \end{equation*}\]-
访问（Visit）：每次一个 $(s,a)$ 出现在回合中，就称对该 $(s,a)$ 进行了一次访问。
- 在 MC Basic 算法中，实际上使用的是首次访问法（Initial-visit method），即在上述的episode中，只考虑从 $(s_1,a_2)$ 开始，得到即时奖励，并把后续的步骤全部用来估计Action Value。因此：
- 仅计算回报并近似 $q_{\pi}(s_1,a_2)$ 。
- 这就是MC基本算法所做的。
- 缺点：没有充分利用数据，有很多数据被浪费了。
1. 从数据的角度改进 MC Basic
在上述例子的episode中，实际上访问了多组 $(s,a)$ ：
\[\begin{equation*} \begin{aligned} s_1\xrightarrow{a_2}s_2\xrightarrow{a_4}s_1\xrightarrow{a_2}s_2\xrightarrow{a_3}s_5\xrightarrow{a_1}\cdots& \text{ [原始episode]}\\ s_2\xrightarrow{a_4}s_1\xrightarrow{a_2}s_2\xrightarrow{a_3}s_5\xrightarrow{a_1}\cdots& \text{ [从 }(s_2,a_4)\text{ 开始的episode]}\\ s_1\xrightarrow{a_2}s_2\xrightarrow{a_3}s_5\xrightarrow{a_1}\cdots& \text{ [从 }(s_1,a_2)\text{ 开始的episode]}\\ s_2\xrightarrow{a_3}s_5\xrightarrow{a_1}\cdots& \text{ [从 }(s_2,a_3)\text{ 开始的episode]}\\ s_5\xrightarrow{a_1}\cdots& \text{ [从 }(s_5,a_1)\text{ 开始的episode]} \end{aligned} \end{equation*}\]因此在原始episode中，可以充分利用数据，估计 $q_{\pi}(s_1,a_2),q_{\pi}(s_2,a_4),q_{\pi}(s_2,a_3),q_{\pi}(s_5,a_1),\cdots$ 。
这里面实际上还有两种方法：
- 首次访问法（first-visit method）：例如，在上述原始episode中，$(s_1,a_2)$ 出现了两次，first-visit就只估计第一次出现的。
- 每次访问法（every-visit method）：每一次访问都进行估计。
2. 从更新策略的角度改进 MC Basic
策略更新有两种方法：
- 第一种方法是在策略评估步骤中，收集从一个 $(s,a)$ 开始的所有episode，然后用平均回报来近似动作价值。
- 这是MC基本算法采用的方法。
-
该方法的问题是智能体必须一直等待，直到收集完所有的episode。
- 第二种方法是使用单个episode的回报来近似动作价值。这样，我们可以episode-by-episode的改进策略。
- 有人可能会说，单个episode的回报不能准确地近似相应的动作价值。事实上，我们在介绍的截断策略迭代算法中已经类似这么做过，是类似的想法。
- 这类方法属于：广义策略迭代（Generalized Policy Iteration）。它指的是在策略评估和策略改进过程之间切换的一般思路或框架。许多基于模型和无模型的强化学习算法都属于这个框架。
3. 伪代码
结合以上方法，就会得到一种新的算法，称为MC Exploring Starts算法，伪代码如下：
初始化：初始猜测策略 $\pi_0$ 。 目标：搜索最优策略。 \(\begin{aligned} &\text{For each episode, do:} \\ &\quad\quad \text{Episode generation: Randomly select a starting state-action pair } (s_0, a_0). \\ &\quad\quad \text{Ensure that all pairs can be possibly selected.} \\ &\quad\quad \text{Following the current policy, generate an episode of length:} \\ &\quad\quad T: s_0, a_0, r_1, \ldots, s_{T - 1}, a_{T - 1}, r_T \\ &\quad\quad \text{Policy evaluation and policy improvement:} \\ &\quad\quad \text{Initialization: } g \leftarrow 0 \\ &\quad\quad \text{For each step of the episode, } t = T - 1, T - 2, \ldots, 0, \text{ do:} \\ &\quad\quad\quad\quad g \leftarrow \gamma g + r_{t + 1} \\ &\quad\quad\quad\quad \text{Use the} \color{red}{\text{ first-visit } } \text{ method:} \\ &\quad\quad\quad\quad \text{If } (s_t, a_t) \text{ does not appear in } (s_0, a_0, s_1, a_1, \ldots, s_{t - 1}, a_{t - 1}), \text{ then:} \\ &\quad\quad\quad\quad\quad\quad Returns(s_t, a_t) \leftarrow Returns(s_t, a_t)+g \\ &\quad\quad\quad\quad\quad\quad q(s_t, a_t)=\text{average}(Returns(s_t, a_t)) \\ &\quad\quad\quad\quad\quad\quad \pi(a|s_t)=1 \text{ if } a = \arg\max_{a}q(s_t, a) \end{aligned}\)
注意：在算法实现上，对于一个episode的 $(s,a)$ 序列，上述算法是逆向来计算的，这样可以复用计算好的结果，提高计算效率。算发使用了first-visit方法，好处是可以确保访问的每个 $(s,a)$ 在都尽可能具有较长的episode length。
为什么我们需要考虑探索起始点（Exploring Starts）？
从理论上讲，只有当每个状态下的每个动作价值都被充分探索时，我们才能正确选择最优动作。相反，如果某个动作没有被探索，这个动作可能恰好是最优动作，从而被错过。
对于一个 $(s,a)$，有两种方法可以计算到它，一个是作为起始点start，另一个是在某个episode中，它不是起始点，而是中间的点，叫做visit。但是，我们无法保证一定能够对每个 $(s,a)$ 进行visit，因此，MC Exploring Starts是对每一个起始点进行探索。在实践中，探索起始点很难实现。对于许多应用，特别是那些涉及与环境进行物理交互的应用，很难收集从每个状态-动作对开始的回合。
因此，理论和实践之间存在差距。我们能否消除对探索起始点的要求呢？接下来，可以通过使用柔性策略（soft policies）来做到这一点。
四、MC Epsilon-Greedy 算法
1. 算法介绍
soft policy即对每一个action都有可能做选择。为什么使用soft policy？因为使用soft policy能够使得在少量足够长的episode中，就能够覆盖所有的 $(s,a)$ 。这样就无需从每个 $(s,a)$ 开始，使得episode的数量非常多，Exploring Starts这样的条件就可以去掉。
这里我们需要使用的soft policy叫做 $\varepsilon$-Greedy policy，它的形式如下：
\[\begin{equation} \pi(a|s) = \begin{cases} 1 - \frac{\varepsilon}{|\mathcal{A}(s)|}(|\mathcal{A}(s)| - 1), & \text{对于贪婪action}, \\ \frac{\varepsilon}{|\mathcal{A}(s)|}, & \text{对于其他 } |\mathcal{A}(s)| - 1 \text{ 个action}. \end{cases} \end{equation}\]其中，$\varepsilon \in [0,1]$ ，$|\mathcal{A}(s)|$ 是状态 $s$ 下的动作数量。贪婪action（action value最大的那一个）的概率总是大于其他非贪婪action，因为 $1 - \frac{\varepsilon}{|\mathcal{A}(s)|}(|\mathcal{A}(s)| - 1) = 1 - \varepsilon + \frac{\varepsilon}{|\mathcal{A}(s)|} \geq \frac{\varepsilon}{|\mathcal{A}(s)|}$。
为什么使用 $\varepsilon$-Greedy policy？在利用（exploitation）和探索（exploration）之间取得平衡
- 当 $\varepsilon = 0$ 时，它就变成了贪婪策略，探索较少但利用较多。
- 当 $\varepsilon = 1$ 时，它变成了均匀分布，探索较多但利用较少。
如何将 $\varepsilon$-Greedy policy应用到基于MC的强化学习算法中？在MC Basic算法和MC Exploring Starts算法中，策略改进步骤是求解：
\[\begin{equation} \pi_{k + 1}(s) = \arg\max_{\pi \in \Pi} \sum_{a} \pi(a|s)q_{\pi_{k} }(s, a) \end{equation}\]其中 $\Pi$ 表示所有可能策略的集合。这里的最优策略是
\[\begin{equation} \pi_{k + 1}(a|s) = \begin{cases} 1, & a = a_{k}^{*}, \\ 0, & a \neq a_{k}^{*} \end{cases} \end{equation}\]其中 $a_{k}^{*} = \arg\max_{a} q_{\pi_{k} }(s, a)$。
要应用 $\varepsilon$-Greedy policy，则策略改进步骤变为求解
\[\begin{equation} \pi_{k + 1}(s)=\arg\max_{\pi\in\Pi_{\varepsilon} }\sum_{a}\pi(a|s)q_{\pi_{k} }(s,a) \end{equation}\]其中 $\Pi_{\varepsilon}$ 表示具有固定 $\varepsilon$ 值的所有 $\varepsilon$-Greedy policy的集合。这里的最优策略是
\[\begin{equation} \pi_{k + 1}(a|s)= \begin{cases} 1-\frac{|\mathcal{A}(s)| - 1}{|\mathcal{A}(s)|}\varepsilon, & a = a_{k}^{*}, \\ \frac{1}{|\mathcal{A}(s)|}\varepsilon, & a \neq a_{k}^{*}. \end{cases} \end{equation}\]- MC $\varepsilon$-Greedy算法与MC Eploring Starts算法相同，除了前者使用 $\varepsilon$-Greedy policy。
- 它不需要探索起始状态，但仍然需要以不同的形式访问所有的状态-动作对。
2. 伪代码
初始化：初始猜测策略 $\pi_0$ 。 目标：搜索最优策略。 \(\begin{aligned} &\text{For each episode, do:} \\ &\quad\quad \text{Episode generation: Randomly select a starting state-action pair } (s_0, a_0). \\ &\quad\quad \text{Ensure that all pairs can be possibly selected.} \\ &\quad\quad \text{Following the current policy, generate an episode of length:} \\ &\quad\quad T: s_0, a_0, r_1, \ldots, s_{T - 1}, a_{T - 1}, r_T \\ &\quad\quad \text{Policy evaluation and policy improvement:} \\ &\quad\quad \text{Initialization: } g \leftarrow 0 \\ &\quad\quad \text{For each step of the episode, } t = T - 1, T - 2, \ldots, 0, \text{ do:} \\ &\quad\quad\quad\quad g \leftarrow \gamma g + r_{t + 1} \\ &\quad\quad\quad\quad \text{Use the} \color{red}{\text{ every-visit } } \text{ method:} \\ &\quad\quad\quad\quad \text{If } (s_t, a_t) \text{ does not appear in } (s_0, a_0, s_1, a_1, \ldots, s_{t - 1}, a_{t - 1}), \text{ then:} \\ &\quad\quad\quad\quad\quad\quad Returns(s_t, a_t) \leftarrow Returns(s_t, a_t)+g \\ &\quad\quad\quad\quad\quad\quad q(s_t, a_t)=\text{average}(Returns(s_t, a_t)) \\ &\quad\quad\quad\quad\quad\quad \text{Let } a^* = \arg\max_{a}q(s_t, a), \\ &\quad\quad\quad\quad\quad\quad\quad\quad \pi_{k + 1}(a|s)= \begin{cases} 1-\frac{|\mathcal{A}(s)| - 1}{|\mathcal{A}(s)|}\varepsilon, & a = a_{k}^{*}, \\ \frac{1}{|\mathcal{A}(s)|}\varepsilon, & a \neq a_{k}^{*}. \end{cases} \end{aligned}\)
与MC Eploring Starts的伪代码几乎完全一致，除了：
- 使用了 $\varepsilon$-Greedy policy
- 使用every-visit，由于使用的是非常长的episode，如果使用first-visit，会造成数据的浪费