Gnosnay 和他的硅基搭子

CS5446 5. Monte Carlo

· Gnosnay

Notes for CS5446 Reinforcement Learning.

model-free & model-based

还记得 MDP 吗？MDP 是一个四元组：

$$ MDP = (S, A, P, R) $$
  • Set:
    • State Set: $\mathcal{S}$
    • Action Set: $\mathcal{A}(s)$
    • Reward Set: $\mathcal{R}(s, a)$
  • Probability Distribution:
    • State Transition Probability: $p(s'|s,a)$
    • Reward Probability: $p(r|s,a)$
  • Decision policy，$\pi(a|s)$

当 Probability Distribution 不先验的知道的时候，我们就是 model-free 的。

Probability Distribution 不知道的时候，我们可以通过 sampling 的方式来估计概率分布。最简单的方法就是 MC mean estimation。

Monte Carlo Basic

MC basic 的本质是 policy iteration，把依赖模型的部分换成通过采样的方式来估计状态值。

PI 分两步：

  1. policy evaluation: $ v_{\pi_k} = r_{\pi_k} + \gamma P_{\pi_k}v_{\pi_k} \\ = \sum_{a \in \mathcal{A}(s)} \pi(a|s) q_{\pi_k}(s,a) $
  2. policy improvement: $ \pi_{k+1} = \arg \max_{\pi} (r_{\pi} + \gamma P_{\pi}v_{\pi_k}) \\ = \arg \max_{\pi} \sum_{a \in \mathcal{A}(s)} \pi(a|s) q_{\pi_k}(s,a) $

MC basic 和 PI 的核心是一模一样的，不一样的是第一步的求解过程。PI是根据 model 来计算的， MC basic 是直接 sampling 估计的。

我们假设 $g(s, a)$ 是对在 s 状态下，take action a 所获得的 $G_t$ 的采样。

根据定义:

$$ q_{\pi_k}(s,a) = \mathbb{E}[G_t | S_t = s, A_t = a] $$

如果我们对采样结果求平均（期望），那么它就刚好是 action value 的近似估计：

$$ q_{\pi_k}(s,a) \approx \frac{1}{N} \sum_{i=1}^{N} g^{(i)}(s, a) $$

其中 $g^{(i)}(s, a)$ 是第 $i$ 次采样得到的 $G_t$ 。

因此 MC 的思路就是我们不再计算 value，而是通过采样来估计 value。

Example

$$ r_{bound} = -1, r_{target} = 1, r_{forbidden} = -1, \gamma = 0.9 $$

初始的policy 在图中以箭头给出。我们尝试用 MC basic 来找到最优 policy。

由于这个 grid world 是确定的，因此我们只需要采样一次就可以得到结果。

Step 1: policy evaluation

这一步我们要求所有的 $q_{\pi_k}(s,a)$ 。那么对这个例子来说，我们一共有 9 states x 5 actions = 45 个 state-action pairs. 如果我们要采样 n 次的话，那么我们要进行 45*n 次 trajectory 的分析。

又由于这个例子中所有的策略都是 deterministic 的，所以每个 state-action pair 出发的轨迹都是一样的，所以每个 pair 只需要采样一次即可。

注意这里的采样是针对 s1 状态下的不同 action 进行的分析。我们需要分析完整的轨迹：

$$ \begin{array}{l} (s_1, a_1): s_1 \xrightarrow{a_1} s_1 \xrightarrow{a_1} s_1 \xrightarrow{a_1} \ldots \\ q_{\pi_0}(s_1, a_1) = -1 + \gamma(-1) + \gamma^2(-1) + \ldots \\ \\ (s_1, a_2): s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_3} s_5 \xrightarrow{a_3} \ldots \\ q_{\pi_0}(s_1, a_2) = 0 + \gamma 0 + \gamma^2 0 + \gamma^3(1) + \gamma^4(1) + \ldots \\ \\ (s_1, a_3): s_1 \xrightarrow{a_3} s_4 \xrightarrow{a_2} s_5 \xrightarrow{a_3} \ldots \\ q_{\pi_0}(s_1, a_3) = 0 + \gamma 0 + \gamma^2 0 + \gamma^3(1) + \gamma^4(1) + \ldots \\ \\ (s_1, a_4): s_1 \xrightarrow{a_4} s_1 \xrightarrow{a_1} s_1 \xrightarrow{a_1} \ldots \\ q_{\pi_0}(s_1, a_4) = -1 + \gamma(-1) + \gamma^2(-1) + \ldots \\ \\ (s_1, a_5): s_1 \xrightarrow{a_5} s_1 \xrightarrow{a_1} s_1 \xrightarrow{a_1} \ldots \\ q_{\pi_0}(s_1, a_5) = 0 + \gamma(-1) + \gamma^2(-1) + \ldots \end{array} $$

Step 2: policy improvement

因为 $q_{\pi_0}(s_1, a_2) = q_{\pi_0}(s_1, a_3)$ ，且为最大，因此我们更新 policy 为：

$$ \pi_{1}(a_2|s_1) = 1\ or\ \pi_{1}(a_3|s_1) = 1 $$

针对 s1 的策略已经收敛了。我们接下来可以接着分析 s3 的策略。这里不赘述。

Impact of episode length

episode 就是有终结状态的 trajectory。episode length 就是我们在采样的时候沿着这个策略执行了多少步。执行的步越长，episode length 越长。

  • episode length 越短，那么只有 target area 周围的状态才会有更新
  • episode length 越长，需要的时间越久，探索的区域可能就越大

所以 episode length 应当足够长。

MC Exploring Starts

问题一：MC basic 的效率不够高，考虑这个 episode

$$ 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}\ldots $$

这个通常被认为是对 $(s_1, a_2)$ 的采样。如果我们从第二项开始分析，那它也可以被当作是 $(s_2, a_4)$ 的采样。这样我们对这个数据可以利用得更充分。

但是注意到这个 episode 中，$(s_1, a_2)$ 出现了两次。那么我们第二次再遇到 $(s_1, a_2)$ 得时候是否把它当作另一个样本用来估计 avg return呢？这里有两个策略：

  • first-visit method: 只有第一次碰到时才纳入计算
  • every-visit method: 每次碰都都纳入计算

问题二：更新 policy 的时机

MC basic 需要等从一个 state-action pair 出发的所有 episode 都采集到后才能更新 action value 的估计值。我们还可以通过 incremental 的方式来更新 action value 的估计值。$q_{\pi_k}(s,a)$ 更新之后 policy 也可以对应更新。

这种和 truncated policy iteration 有点类似的算法叫做 Generalized policy iteration。

MC Exploring Starts 要求：

  • 我们要尝试对每个 $(s, a)$ 都进行遍历（exploring）
  • 为了确保对每个 $(s, a)$ 都完成遍历，我们生成 episode 的时候都以 $(s, a)$ 开始（starts）

在实际应用中 MC Exploring Starts 是很难被应用的，因为以 $(s, a)$ 开始的策略不够有效率。比如你总不能把机器人搬来搬去并设置好初始动作吧……那多累啊。

MC $\epsilon$ -greedy

为了去掉 Exploring Starts 这个条件，我们尝试为探索加入一点随机性以保证探索可以尽可能覆盖各种 $(s, a)$ 。举个例子，网格世界中，如果机器人每次移动的时候我们为他设置一个概率让他随机选某个方向进行移动，那么只要这个 episode length 足够长，机器人的轨迹总会覆盖所有的 $(s, a)$ 的可能性。

听起来有点像醉汉理论：如果一个醉汉想要回家，他随机选择一个方向前进，只要它前进的步数足够多，他最终总能到家。也有点像打字的猴子，只要给这个猴子足够多的时间，那么总有一天这只猴子可能会打出来莎士比亚全集。

这个算法的形式化表达是：

$$ \pi(a|s) = \begin{cases} 1 - \frac{\epsilon}{|\mathcal{A}(s)|}(|\mathcal{A}(s)|-1), & \text{if the greedy action}, \\ \frac{\epsilon}{|\mathcal{A}(s)|}, & \text{for the other }|\mathcal{A}(s)| - 1\text{ actions}. \end{cases} $$

其中

  • $\epsilon$ 的取值范围是 [0, 1]
  • $\mathcal{A}(s)|$ 是状态 $s$ 下所有 actions 的数量

当 $\epsilon$ 为 1 时，agent 探索欲就会更大，随机性会更高。$\epsilon$ 为 0 时，agent 更 greedy。

这个公式其实是先设定了对其他动作的概率 $\frac{\epsilon}{|\mathcal{A}(s)|}$ 然后对 greedy action 进行了反向约束。即我先留够探索的概率，剩下的都归我目前迭代出来的最优的动作。

这里涉及到一个思路：

  • exploition：充分利用现在已知的信息
  • exploration：认为现在知道的信息不够，积极探索一下

$\epsilon$ 可以用来调整你对exploition和exploration的偏好。通常过大的 $\epsilon$ 会导致算法最后的 optimality 不佳。以至于使得策略和 MC greedy 都不一致了。

因此比较好的选择是在一开始可以选一个大的 $\epsilon$ 然后逐渐减小它。这样可以保证它有足够多的探索性，但是慢慢也会变得最优。