强化学习——蒙特卡罗（五）

蒙特卡罗强化学习算法（Monte Carlo Learning）

面对没有预先知道模型的场景，策略迭代算法就无法满足策略的求解。因此引入了蒙特卡罗的方法，使用大量采样的数据去替代模型的作用。

0 蒙特卡罗方法

一句话就是在独立同分布的随机变量中，用样本的平均值去作为随机变量的期望估计。

1 MC Basic（蒙特卡罗基础算法）

与策略迭代的做法相似，只不过在策略评估时，无法使用模型，需要用蒙特卡罗的方法去估算 action value。

1.1 核心区别

policy iteration 的做法是
$v_{\pi_{k}}^{(j+1)}= \displaystyle \sum_a \pi(a|s) \underbrace{\left[\displaystyle \sum_r p(r|s,a) r+\gamma \displaystyle \displaystyle \sum_{s'} p(s'|s,a)v_{\pi_{k}}^{(j)}(s') \right]}_{q_{\pi_{k}}^{(j)}(s,a)}$(elementwise form)
其中$p(s'|s,a),p(r|s,a)$需要模型预先确定，才能进一步计算。

1.2 策略评估（policy evaluation）

目标：通过蒙特卡罗的方法计算出$q_{\pi_k}(s,a)=E[G_t | S_t = s, A_t = a]$。绕过policy iteration 中 state value 的迭代（需要模型）。
步骤：计算前预先设定策略$\pi_k$和 episode 的长度$T$，然后开始从每个状态和动作组合(s,a)出发，按照$\pi_k$，经过$T$步后，获得一个 episode，进而获得$G_t$的采样值$g(s,a)$。获得足够多的采样值$g(s,a)$后，计算平均值得到期望$E[G_t | S_t = s, A_t = a] \approx \frac{1}{N} \displaystyle \sum_{i=1}^N g^{(i)}(s,a)$估计值。而采样$g(s,a)$停止条件是期望已经收敛。

1.3 策略改进（policy improvement）

与 policy iteration 方法相同，在得到 q table 后，用 greedy 策略改进策略。

$$\pi_{k+1} = \displaystyle\argmax_{\pi}\sum_a \pi(a|s)q_{\pi_k}(s,a)$$

即

$$\pi_{k+1}(a|s)=\begin{cases} 1, & a = a_{\pi_{k}}^*= \displaystyle \argmax_a q_{\pi_{k}}(s,a)\\ 0, & a \neq a_{\pi_{k}}^* \end{cases}$$

2 MC exploring starts

考虑到 MC basic 方法效率较低，从数据利用率的方面提升整体效率。

2.1 策略评估

依然是从每个状态、动作组合出发，获得 episode，如（$s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_3} s_4 \xrightarrow{a_1} s_1 \xrightarrow{a_2} s_2$）。但是在获取$g(s,a)$时，不像 MC Basic 方法一样只获得$g(s_1,a_2)$，还获得$g(s_2,a_3),g(s_4,a_1)$。同时每次获得的 episode 采用从最后一位进行计算$g(s,a)$，如$g(s_1,a_2)=r_1,g(s_4,a_1)=r_2+\gamma g(s_1,a_2),g(s_2,a_1)=r_2+\gamma g(s_4,a_1) \cdots$。而且采用 first visit 的方法，在该 episode 第一次遇见该(s,a)组合后，不再重复获取$g(s,a)$，如$g(s_1,a_2)$。

2.2 策略改进（同 MC Basic）

2.3 exploring starts 缺陷

exploring 指需要探索所有状态、动作组合。starts 指需要该状态、动作组合出发进行探索。exploring starts 是 MC exploring starts 和 MC Basic 算法都面临的问题。

3 MC $\epsilon$-greedy

为了解决 exploring starts 的问题，使用一个 episode 完成所有状态、动作组合的探索。

3.1 策略评估

与 MC exploring starts 方法相似，不过不再需要对所有状态、动作组合出发进行探索，而是任一状态、动作组合出发获取得到一个较长的 episode。而且不再使用 first visit 的方法，而是 every visit 的方法，因为 episode 只有一个。

3.2 策略改进

为了满足所有状态、动作组合都得到探索，策略改为

$$\pi_{k+1}(a|s)=\begin{cases} 1 - \frac{\normalsize |A(s_t) | - 1}{\normalsize |A(s_t)|}\epsilon, & a = a_{\pi_{k}}^*= \displaystyle \argmax_a q_{\pi_{k}}(s,a)\\ \frac{\normalsize \epsilon}{\normalsize |A(s_t)|}, & a \neq a_{\pi_{k}}^* \end{cases}$$

$|A(s_t) |$为动作空间动作数。$\epsilon$是[0,1]，使greedy策略下的动作概率始终比其他动作概率大，同时也满足了探索性。
这样既满足了 exploitation（利用率）又满足 exploration（探索）。