Lecture 5: Monte Carlo Learning

The simplest MC-based RL algorithm: MC Basic

理解MC basic算法的关键是理解如何将policy iteration算法迁移到model-free的条件下。

Policy iteration算法在每次迭代过程中有两步：
$$\{\begin{array}{l}\text{Policy evaluation: }{\mathbf{v}}_{{\pi }_k}={\mathbf{r}}_{{\pi }_k}+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_{{\pi }_k}\\ \text{Policy improvement: }{\pi }_{k+1}={\text{argmax}}_{\pi }({\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_{{\pi }_k})\end{array}$$
Policy improvement阶段的元素表现形式为：
$$\begin{array}{rl}{\pi }_{k+1}(s)& ={\text{argmax}}_{\pi }\sum _a\pi (a|s)\left[\sum _{r}p(r|s,a)+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{{\pi }_k}(s^{\prime })\right]\\ & ={\text{argmax}}_{\pi }\sum _a\pi (a|s)q_{{\pi }_k}(s,a)\end{array}$$
其中，关键是$q_{{\pi }_k}(s,a)$。

action value 的两种表达形式：

Expression 1: model-based 方法
$$q_{{\pi }_k}(s,a)=\sum _{r}p(r|s,a)+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{{\pi }_k}(s^{\prime })$$
Expression 2: model-free方法
$$q_{{\pi }_k}(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a]$$
因此，对于model-free的RL算法，可以直接利用数据（samples或experiences）使用expression 2的方法计算$q_{{\pi }_k}(s,a)$。

action values的Monte Carlo estimation步骤：

• 从$(s,a)$开始，按照policy${\pi }_k$，生成一个episode。

• 计算episode的return $g(s,a)$

• 对不同的$g(s,a)$采用，计算$G_t$
  $$q_{{\pi }_k}(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a]$$

• 假设已经获得一个episode集合，那么即拥有 { g ( j ) ( s , a ) } \{ g^{(j)}(s, a) \} {g(j)(s,a)}，则
  $$q_{{\pi }_k}(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a]\approx \frac{1}{N}\sum _{i=1}^N{g}^{(j)}(s,a)$$

上述算法的基本理念是：当model不可获得时，可以使用data。

MC Basic algorithm：

对于给定的初始policy ${\pi }_0$，在第$k$次迭代中，有两个主要的步骤

step 1: policy evaluation。对所有的$(s,a)$获取$q_{{\pi }_k}(s,a)$ 。具体来说，对每一个action-state对，运行得到无限数量（或足够多）的episode。它们的平均return即是$q_{{\pi }_k}(s,a)$的估计。

step 2: policy improvement。对所有$s\in \mathcal{S}$，计算${\pi }_{k+1}(s)={\text{argmax}}_{\pi }{\sum }_a\pi (a|s)q_{{\pi }_k}(s,a)$。当$a_k^{\ast }={\text{argmax}}_a{q}_{{\pi }_k}(s,a)$时，贪心optimal policy为${\pi }_{k+1}(a_k^{\ast }|s)=1$。

注意，MC Basic算法与policy iteration算法是一致的，除了：

MC Basic算法直接估计$q_{{\pi }_k}(s,a)$而不是计算$v_{{\pi }_k}(s)$

• MC Basic是policy iteration算法的一种变体。
• model-free算法是在model-based算法的基础上建立的。 因此，在研究model-free算法之前，有必要先了解model-based算法
• MC Basic对于揭示基于 MC 的model-free强化学习的核心思想很有用，但由于效率低而不实用。
• 为什么 MC Basic 估计的是action value 而不是state value？ 这是因为state value不能直接用来改进policy。 当模型不可用时，应该直接估计action value。
• 由于policy iteration是收敛的，因此在给定足够的episode的情况下，MC Basic也保证是收敛的。

Example:

Task：上图展示的是初始policy，使用MC Basic算法寻找最优policy。

$r_{\text{boundary}}=-1$，$r_{\text{forbidden}}=-1$，$r_{\text{target}}=1$，$\gamma =0.9$

Outline：对于给定的policy ${\pi }_k$

step 1：policy evaluation。计算$q_{{\pi }_k}(s,a)$。共有
$$9\text{ states}\times 5\text{ actions}=45\text{ state-action pairs}$$
step2: policy improvement。贪心的选择action
$$a^{\ast }(s)={\text{argmax}}_{a_i}{q}_{{\pi }_k}(s,a)$$
以计算$q_{{\pi }_k}(s_1,a)$为例：

step 1: policy evaluation。

• 由于当前的policy是确定性的，一个episode就足以得到action value。

• 如果当前policy是随机的，则需要无限数量的episode（或至少许多）。

• 从$(s_1,a_1)$开始，episode是 $s_1\stackrel{a_1}{\to }{s}_1\stackrel{a_1}{\to }{s}_1\stackrel{a_1}{\to }\cdots$，action value为：
  $$q_{{\pi }_0}(s_1,a_1)=-1+\gamma (-1)+{\gamma }^2(-1)+\cdots$$

• 从$(s_1,a_2)$开始，episode是 $s_1\stackrel{a_2}{\to }{s}_2\stackrel{a_3}{\to }{s}_5\stackrel{a_3}{\to }\cdots$，action value为：
  $$q_{{\pi }_0}(s_1,a_2)=0+\gamma 0+{\gamma }^{2}0+{\gamma }^3(1)+{\gamma }^4(1)+\cdots$$

• 从$(s_1,a_3)$开始，episode是 $s_1\stackrel{a_3}{\to }{s}_4\stackrel{a_2}{\to }{s}_5\stackrel{a_3}{\to }\cdots$，action value为：
  $$q_{{\pi }_0}(s_1,a_2)=0+\gamma 0+{\gamma }^{2}0+{\gamma }^3(1)+{\gamma }^4(1)+\cdots$$

• 从$(s_1,a_4)$开始，episode是 $s_1\stackrel{a_4}{\to }{s}_{‘}\stackrel{a_1}{\to }{s}_1\stackrel{a_1}{\to }\cdots$，action value为：
  $$q_{{\pi }_0}(s_1,a_4)=-1+\gamma (-1)+{\gamma }^2(-1)+\cdots$$

• 从$(s_1,a_5)$开始，episode是 $s_1\stackrel{a_5}{\to }{s}_1\stackrel{a_1}{\to }{s}_1\stackrel{a_1}{\to }\cdots$，action value为：
  $$q_{{\pi }_0}(s_1,a_5)=0+\gamma (-1)+{\gamma }^2(-1)+\cdots$$

step 2: policy improvement。

• 通过观察action value，可得：
  $$q_{{\pi }_0}(s_1,a_2)=q_{{\pi }_0}(s_1,a_3)$$
  是最大的。

• 因此，policy可以被提高为：
  $${\pi }_1(a_2|s_2)=1\text{or}{\pi }_1(a_3|s_1)=1$$
  无论哪种方式，$s_1$ 的新policy都变得最优。

对于这个简单的例子来说，一次迭代就足够了！

检查episode长度的影响：

使用 MC Basic 搜索不同episode长度的最优policy。

• 当episode长度很短时，只有接近目标的state才具有非零的state value。
• 随着episode长度的增加，离target较近的state比较远的state更早具有非零值。
• episode长度应该足够长。
• episode长度不必无限长。

Use date more efficiently: MC Exploring Starts

MC Basic 算法：

• 优点：核心思想清晰可见。
• 缺点：太简单而不实用。

考虑一个grid-world的例子，遵循policy $\pi$，可以得到一个episode，例如
$$s_1\stackrel{a_2}{\to }{s}_2\stackrel{a_4}{\to }{s}_1\stackrel{a_2}{\to }{s}_2\stackrel{a_3}{\to }{s}_5\stackrel{a_1}{\to }\cdots$$
visit：每次state-action对出现在episode中，就称为该state-action对的访问

使用数据的方法：Initial-visit method

• 只计算return并估计$q_{\pi }(s_1,a_2)$
• MC Basic算法
• 不能充分利用数据

episode也visit其他state-action对

其可以估计$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$

Data-efficient方法：

• first-visit方法
• every-visit方法

基于 MC 的 RL 的另一个方面是何时更新policy。 有两种方法:

• 第一种方法是，在policy evaluation步骤中，收集从state-action对开始的所有episode，然后使用平均return来近似action value。

  • 这是MC Basic算法采用的
  • 这种方法的问题是agent必须等到所有episodes都收集完毕。

• 第二种方法使用单个episode的return来近似action value。

  这样就可以episode-by-episode完善policy。

对第二种方法分析：

• 也许，单episode的return并不能准确地近似对应的action value。
• 但是，在上一章介绍的truncated policy iteration算法中已经做到了这一点。

Generalized policy iteration:

• 不是一个特定的算法
• 它是指policy-evaluation和policy-improvement过程之间切换的总体思路或框架。
• 许多model-based和model-free的强化学习算法都属于这个框架。

如果想要更有效地使用数据和更新估计，就可以得到一种称为 MC Exploring Starts 的新算法：

What is exploring starts?

• Exploring starts意味着我们需要从每个state-action对开始生成足够多的episode。
• MC Basic 和 MC Exploring Starts 都需要这个假设。

Why do we need to consider exploring starts?

• 理论上，只有充分探索每个state的每个action value，才能正确选择最优动作。
  相反，如果没有探索某个action，则该action可能恰好是最佳action，因此会被错过。
• 在实践中，exploring starts是很难实现的。 对于许多应用程序，尤其是那些涉及与环境的物理交互的应用程序，很难从每个state-action对开始收集episode。

因此理论与实践存在差距！

那么可以取消exploring starts的要求吗？ 接下来将展示可以通过使用soft policy来做到这一点。

MC without exploring starts: MC $\epsilon$-Greedy

如果采取任何action的概率为正，则policy被称为soft policy。

Why introduce soft policies?

• 通过soft policy，一些足够长的episode可以访问每个state-action对足够多次。
• 然后，不需要从每个state-action对开始都有大量的episode。 因此，可以消除exploring starts的要求。

$\epsilon$-greedy policies
$$\pi (a|s)=\{\begin{array}{ll}1-\frac{\epsilon }{|\mathcal{A}(s)|}(|\mathcal{A}(s)|-1)& \text{for the greedy action}\\ \frac{\epsilon }{|\mathcal{A}(s)|}& \text{for other }|\mathcal{A}(s)|-1\text{ actions}\end{array}$$
其中，$\epsilon \in [0,1]$并且$\mathcal{A}(s)$是$s$的action的数量。

选择贪婪action的机会总是大于其他action。因为：
$$1-\frac{\epsilon }{|\mathcal{A}(s)|}(|\mathcal{A}(s)|-1)=1-\epsilon +\frac{\epsilon }{|\mathcal{A}(s)|}\ge \frac{\epsilon }{|\mathcal{A}(s)|}$$
Why use ε-greedy?

平衡利用（exploitation）与探索（exploration）。

• 当$\epsilon =0$时，变得贪婪。更少的探索（exploration），更多的利用（exploitation）。
• 当$\epsilon =1$时，变为均匀分布。更多探索（exploration），更少利用（exploitation）。

How to embed $\epsilon -$greedy into the MC-based RL algorithms?

原本，MC Basic 和 MC Exploring Starts 中的policy improvement步骤是为了解决：
$${\pi }_{k+1}(s)={\text{argmax}}_{x\in \Pi }\sum _a\pi (a|s)q_{{\pi }_k}(s,a)$$
其中，$\Pi$代表所有可能的policy。其中，最优的policy为：
$${\pi }_{k+1}(a|s)=\{\begin{array}{ll}1& a=a_k^{\ast }\\ 0& a\ne s_k^{\ast }\end{array}$$
其中，$a_k^{\ast }={\text{argmax}}_a{q}_{{\pi }_k}(s,a)$。

现在，policy improvement步骤改变为计算：
$${\pi }_{k+1}(s)={\text{argmax}}_{x\in {\Pi }_{\epsilon }}\sum _a\pi (a|s)q_{{\pi }_k}(s,a)$$
其中， ${\Pi }_{\epsilon }$ 表示所有具有固定值 $\epsilon$ 的 $\epsilon$-greedy policy的集合。

最优的policy为：
$${\pi }_{k+1}(a|s)=\{\begin{array}{ll}1-\frac{\epsilon }{|\mathcal{A}(s)|}(|\mathcal{A}(s)|-1)& a=a_k^{\ast }\\ \frac{\epsilon }{|\mathcal{A}(s)|}& a\ne a_k^{\ast }\end{array}$$

• MC $\epsilon$-Greedy 与 MC Exploring Starts 相同，只是前者使用 $\varepsilon $-greedy 策略。
• 它不需要exploring starts，但仍然需要以不同的形式访问所有state-action对。

Can a single episode visit all state-action pairs?

当$\epsilon$=1时，policy（均匀分布）的探索能力最强。

当$\epsilon$较小时，策略的探索能力也较小。

Compared to greedy policies：

• 优点是$\epsilon$-greedy policy的具有更强的探索能力，因此不需要exploring starts条件。
• 缺点是 $\epsilon$-greedy policy一般来说不是最优的（我们只能证明总是存在最优的greedy policy）。
  • MC $\epsilon$-greedy算法给出的最终policy仅在所有 $\epsilon$-greedy policy的集合 ${\Pi }_{\epsilon }$中是最优的。
  • $\epsilon$不能太大

Example：

$r_{\text{boundary}}=-1$，$r_{\text{forbidden}}=-10$，$r_{\text{target}}=1$，$\gamma =0.9$。

当$\epsilon$增大时，policy的最优性能变得更差！最优 $\epsilon$-greedy policy与greedy policy不一致。

Summary

• Mean estimation by the Monte Carlo methods
• Three algorithms:
  • MC Basic
  • MC Exploring Starts
  • MC $\epsilon$-Greedy
• Relationship among the three algorithms
• Optimality vs exploration of $\epsilon$-greedy policies