强化学习 Chapter 3 - Monte Carlo 方法

首次发布: 2025-04-17

... 次访问

/

3.1 背景描述#

当把强化学习的问题建模为一个马尔可夫决策过程（MDP）时，我们如果拥有一个完整的环境模型（即状态转移概率和奖励函数），那么就可以用动态规划的方法来求解最优策略。然而，现实中，我们很难能够得到一个完整的环境模型。我们往往只能通过与真实环境不断交互获得一个个的交互数据，并从中来学习到一个近似的环境模型。在这种情况下，是用动态规划方法求解最优策略一定是会有偏差的。如果能够找到一种不需要环境模型的最优策略求解方法，就可以绕开环境模型的估计，从而学习到一个最优策略。

Monte Carlo 方法就是一种 Model-free 的方法，是首个从经验中学习最优策略的方法。 它的理念是通过一幕幕的交互数据（注意，也因此朴素的 Mote Carlo 方法只适用于分幕式任务，因为必须要有终止状态），利用价值估计可以用平均回报得到的思想来估计状态的价值函数。

3.2 朴素的 Monte Carlo 方法#

3.2.1 采样代替期望#

假设当前有一个策略 $\pi$ ，我们可以通过与环境交互得到一系列的状态-动作-奖励序列，记为轨迹 $\tau = (s_0, a_0, r_1, s_1, a_1, r_2, \ldots, s_T) \sim \pi$ ，于是我们使用

\begin{align*} g_t &= r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \ldots\\ &= r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \ldots + \gamma^{T-t} r_T \end{align*}

来表示从 $t$ 时刻开始到终止状态的回报。于是这样得到的一个轨迹的回报 $g_t$ 就是回报随机变量 $G_t$ 的一个样本。我们可以通过多次采样来估计 $G_t$ 的期望值。

于是，状态价值函数的估计也就可以用如下式子完成

\begin{align*} V(s) &= \mathbb{E}_{\pi} [G_t | S_t = s] \\ &\approx \frac{1}{N} \sum_{i=1}^N g_t^{(i)} \end{align*}

这里的 $N$ 是轨迹的数量， $g_t^{(i)}$ 是第 $i$ 条轨迹下的从状态 $s$ 开始的回报。

3.2.2 迭代均值更新#

结论均值迭代化计算

对于一个序列 $(x_1, x_2, \dots, x_n)$ ，若欲计算其前缀子序列 $(x_1, \dots, x_k)\ (\forall k = 1, 2, \dots, n)$ 的均值，可以采用如下迭代方式

\mu_k = \mu_{k-1} + \frac{1}{k}(x_k - \mu_{k-1})

其中 $\mu_1 = x_1$

推导：

\begin{align*} \mu_k &= \frac{1}{k} \sum_{j=1}^{k} x_j = \frac{1}{k}(x_k + \sum_{j=1}^{k-1}x_j) \\ &= \frac{1}{k} (x_k + (k-1)\mu_{k-1})\\ &= \mu_{k-1} + \frac{1}{k} (x_k - \mu_{k-1}) \end{align*}

3.2.3 增量式 MC 价值估计#

当智能体与环境交互结束后，得到一段交互轨迹 $\tau = (s_1, a_1, r_1, \dots, s_T, a_T, r_T)$ ，那么可以用这段轨迹的经验数据逐步更新轨迹中出现的每一个状态 $s_t$ ，利用

\begin{align*} &N(s_t) \leftarrow N(s_T) + 1\\ &V(s_t) \leftarrow V(s_t) + \frac{1}{N(s_t)}(g_t - V(s_t)) \end{align*}

来实现价值函数的更新。这里的迭代更新方式利用了上述的结论。

不过，对于非平稳问题（即环境会随时间发生变化），利用均值更新学习的效果不好。此时可以采用一个常数 $\alpha$ (类似学习率) 来代替 $1 / N(s_t)$ ，来跟踪一个现阶段的平均值（即学习当前时间局域内的价值）

V(s_t) \leftarrow V(s_t) + \alpha (g_t - V(s_t))

3.3 基于 Monte Carlo 的强化学习#

3.3.1 策略评估#

目标是在给定策略 $\pi$ 下经验片段 $\tau = (s_1, a_1, r_1, \dots, s_T, a_T, r_T)$ 中学习状态价值函数 $V_\pi(s)$ ，思想是用采样的经验数据的平均回报来代替有环境模型计算的期望回报。

但是存在一个问题，即在一段轨迹中，智能体可能从开始到终止会多次访问某几个状态。由此，估计的方法分为 首次访问MC (First visit MC) 和 每次访问MC (Every visit MC) 两种。

Monte Carlo算法对于每个状态的估计是独立的，它对于一个状态的估计并不依赖于对其他状态的估计，这与DP完全不同。这也说明了MC方法没有 自举思想。

首次访问型 MC 策略评估#

First Visit MC 算法


Input:	待评估的策略 $\pi$
Output:	状态价值函数 $V_\pi(s)$
1:	初始化 $V(s) \in \mathbb R$ 和回报 $Returns(s)$ 为空列表对于所有的状态 $s \in \mathcal{S}$
2:	repeat
3:	根据策略 $\pi$ 生成轨迹 $\tau = (s_1, a_1, r_1, \dots, s_T, a_T, r_T)$
4:	初始化 $G \leftarrow 0$
5:	for $t = T, T-2, \dots, 1$
6:	$G \leftarrow \gamma G + r_{t}$
7:	若 $s_t$ 在之前的状态 $s_0, s_1, \dots, s_{t-1}$ 中没有出现
8:	将 $G$ 添加到 $Returns(s_t)$
9:	$V(s_t) \leftarrow average(Returns(s_t))$
10:	令 $V_\pi(s) = V(s),\ \forall s \in \mathcal{S}$

可以发现，这个算法有如下细节：

反向迭代计算回报 $G$ ，因为反向计算比争先计算效率更高。
维护一个 $Returns(s_t)$ 的列表是因为估计状态价值不能单纯只靠一次的经验数据就可以得到
首次访问，排除第二次访问的状态估计

每次访问型 MC 策略评估#

Every Visit MC 算法


Input:	待评估的策略 $\pi$
Output:	状态价值函数 $V_\pi(s)$
1:	初始化 $V(s) \in \mathbb R$ 和回报 $Returns(s)$ 为空列表对于所有的状态 $s \in \mathcal{S}$
2:	repeat
3:	根据策略 $\pi$ 生成轨迹 $\tau = (s_1, a_1, r_1, \dots, s_T, a_T, r_T)$
4:	初始化 $G \leftarrow 0$
5:	for $t = T, T-2, \dots, 1$
6:	$G \leftarrow \gamma G + r_{t}$
7:	将 $G$ 添加到 $Returns(s_t)$
8:	$V(s_t) \leftarrow average(Returns(s_t))$
9:	令 $V_\pi(s) = V(s),\ \forall s \in \mathcal{S}$

动作价值的估计#

很遗憾，上述对状态价值函数的估计方法并不适用于动作价值函数的估计。因为，动作价值函数是关于状态和动作的二元函数，然而，在一段经验轨迹中，智能体可能从未访问过某些确定的状态-动作对，这就导致了这些状态-动作无法被估计。

当然，我们也可以利用 Bellman 方程，使用状态价值函数来求解动作价值函数

\begin{align*} q_\pi(s, a) = \mathbb{E}_{s', r}[r + \gamma V_\pi(s') | s, a] \end{align*}

不过，还有其他的方法。既然我们需要保证智能体的轨迹中能访问每个状态-动作对，不妨设置一个让智能体能够从任意一个状态以任意一个动作开始的轨迹，运用这个轨迹来估计动作价值函数，这个方法称为 Explore-Start. 这个方法将与策略改进放在一起使用。

3.3.2 策略改进#

有了当前最新的价值函数，就可以使用贪心方法来改进当前策略。

\pi'(s) = \arg\max_{a\in \mathcal{A}} Q_\pi(s, a)

Monte Carlo Explore-Start#

同时维护一个近似策略和近似的价值函数，彼此为对方设定优化目标。从而，价值函数不断迭代逼近当前策略的真实价值函数，当前的策略也会根据当前的价值函数不断优化。这个算法框架被称作 广义策略迭代 GPI。（实际上就是 EM 算法的思想）

利用这个思想，得到如下 MC ES 算法

Monte Carlo Explore-Start 算法


Input:	$\gamma$
Output:	最优策略 $\pi$
1:	任意初始化策略 $\pi$ 和动作价值函数 $Q(s, a)$ ，为每个动作和状态创建空列表 $Returns(s, a)$
2:	repeat
3:	随意选择初始状态 $s_0 \in \mathcal{S}$ 和初始动作 $a_0 \in \mathcal{A}$ // 这里不需要初始动作和状态的采样是遵循均匀分布的，但是要保证每个初始的动作和状态都有非0的概率访问到
4:	从初始状态 $s_0$ 和动作 $a_0$ 开始，利用策略 $\pi$ 生成一段轨迹 $\tau = (s_1, a_1, r_1, \dots, s_T, a_T, r_T)$
5：	$G \leftarrow 0$
6:	for $t = T, \dots, 1$
7:	$G \leftarrow \gamma G + r_t$
8:	若 $s_t, a_t$ 在 $s_0, a_0, \dots, s_{t-1}, a_{t-1}$ 中没有出现
9:	把 $G$ 加入到 $Returns(s_t, a_t)$
10:	$Q(s_t, a_t) \leftarrow average(Returns(s_t, a_t))$
11:	$\pi(s_t) = \arg\max_a Q(s_t, a)$

这里是 Explore-Start + First Vist 的策略迭代算法，需要时可修改为其他的组合。

实际上这里维护一个 $Returns(s, a)$ 的列表并不高效，可以使用前述的迭代均值更新来减少内存复杂度。

3.3.3 没有试探性出发假设的 Monte Carlo 控制#

如何避免很难被满足的试探性出发假设呢？唯一的一般性解决方案就是智能体可以持续不断地选择所有可能的动作。有两种方法可以保证这一点，分别是 同轨策略 (on-policy) 和离轨策略 (off-policy)。

Definition On-Policy

在同轨策略种中，用于生成采样数据序列的策略和用于实际决策的待评估和改进的策略是相同的。 同轨策略是在交互中学习，是自学。

Definition Off-Policy

在离轨策略中，用于评估、改进的策略和用于生成采样数据的策略是不同的。 有点类似有一个示教策略和一个学习策略，观察他人的行为进行学习。

同轨策略学习#

在同轨策略方法中，一般会采用”软性”的策略，例如 $\epsilon$ -greedy，在保证整体策略收敛到最优策略的同时，仍然以一定的概率随机选择动作。而正是这里的一定概率的随机动作选择保证了即使没有 Explore-Start 的条件，智能体也能学习到所有状态-动作组合的价值函数。

On-Policy First Visit MC Control with ε-greedy 算法


Input:	$\gamma$ , $\epsilon$
Output:	最优策略 $\pi$
1:	任意初始化策略 $\pi$ 和动作价值函数 $Q(s, a)$ ，为每个动作和状态创建空列表 $Returns(s, a)$ ，注意这里要保证策略初始化为一个 $\epsilon$ -greedy 策略
2:	repeat
3:	从初始状态 $s_0$ 和动作 $a_0$ 开始，利用策略 $\pi$ 生成一段轨迹 $\tau = (s_1, a_1, r_1, \dots, s_T, a_T, r_T)$
4：	$G \leftarrow 0$
5:	for $t = T, \dots, 1$
6:	$G \leftarrow \gamma G + r_t$
7:	若 $s_t, a_t$ 在 $s_0, a_0, \dots, s_{t-1}, a_{t-1}$ 中没有出现
8:	把 $G$ 加入到 $Returns(s_t, a_t)$
9:	$Q(s_t, a_t) \leftarrow average(Returns(s_t, a_t))$
10:	更新策略 $\pi(a \vert s_t) = \begin{cases} 1 - \epsilon + \frac{\epsilon}{\vert \mathcal{A}(s_t)\vert}, &\quad \text{if } a = \arg\max_aQ(s_t, a) \\ \frac{\epsilon}{\mathcal{A}(s_t)}, &\quad \text{otherwise}\end{cases} \forall a \in \mathcal{A(s_t)}$

这个方法非常类似 MC-ES 算法，区别就是一个需要能从任意的动作-状态组合出发，一个可以从固定的动作-状态组合出发但是策略必须是 $\epsilon$ -贪心。

Example Problem 证明 ε-贪心策略能够改进策略

解：

假设 $\pi'$ 是基于 $\pi$ 用 $\epsilon$ -贪心更新的。有

\begin{align*} V_\pi'(s) &= \sum_a \pi'(a | s) Q_\pi(s, a) \\ &= \frac{\epsilon}{|\mathcal{A(s)}|} \sum_a Q_\pi(s, a) + (1 - \epsilon) \max_a Q_\pi(s, a) \\ &\ge \frac{\epsilon}{\mathcal{A}(s)} \sum_a Q_\pi(s, a) + (1 - \epsilon) \sum_a \frac{\pi(a | s) - \epsilon / m}{ 1 - \epsilon} Q_\pi(s, a) \\ &= \sum_a \pi(a | s) Q_\pi(s, a) = V_\pi(s) \end{align*}

由此得出策略 $\pi'$ 比策略 $\pi$ 好。

离轨策略学习#

离轨策略的方法比同轨策略方法的方差要大，而且收敛速度要慢，但是它的通用性更好。这是因为采用上述的同轨策略例如 $\epsilon$ -greedy 的方法时，存在一个问题。为了克服 Explore-Start 的要求，采用了以 $\epsilon$ 的概率随机选择动作的技巧，。但是，正是这个技巧导致了当策略收敛到最优策略附近时，智能体仍然有一定的概率会选择十分愚蠢的行为，必须以较小的可能去选择非最优的动作。很显然，这是不合适的，尤其是当智能体有可能会做出损害自己或他人的危险的事情的情况下。

于是我们考虑使用两个策略来克服 Explore-Start 的问题。让执行动作的策略 $\mu$ 去产生轨迹，然后用于评估当前的目标策略 $\pi$ ，然后改进目标策略 $\pi$ 。不过，由于两个策略不同，如果直接拿 $\mu$ 产生的轨迹数据来更新 $\pi$ 的话，很可能导致在 $\pi$ 自身需要重点关注的地方没怎么改进，反而在不重要的地方有较大的更新。

因此，需要使用基于重要度采样的技巧。

Theorem 重要性采样

数学中，重要度采样的公式为

\mathbb{E}_{x \sim p} [f(x)] = \int_x p(x) f(x)dx = \int_x q(x) \frac{p(x)}{q(x)} f(x) dx = \mathbb{E}_{x\sim q} \left[\frac{p(x)}{q(x)}f(x)\right]

其中，重要性权重为 $\beta(x) = \frac{p(x)}{q(x)}$

根据

p_\pi(a_t, s_{t + 1}, a_{t+1}, \dots, s_T | s_t) = \pi(a_t | s_t) p(s_{t+1} | s_t, a_t) \pi(a_{t+1} | s_{t+1}) \dots p(s_T | s_{T-1}, a_{T-1})

构造重要性权重为

\begin{align*} \rho_{t:T-1} &= \frac{p_\pi(a_t, s_{t + 1}, a_{t+1}, \dots, s_T | s_t)}{p_\mu(a_t, s_{t + 1}, a_{t+1}, \dots, s_T | s_t)} \\ &= \frac{\pi(a_t | s_t) p(s_{t+1} | s_t, a_t) \pi(a_{t+1} | s_{t+1}) \dots p(s_T | s_{T-1}, a_{T-1})}{\mu(a_t | s_t) p(s_{t+1} | s_t, a_t) \mu(a_{t+1} | s_{t+1}) \dots p(s_T | s_{T-1}, a_{T-1})}\\ &= \prod_{k=t}^{T-1}\frac{\pi(a_k | s_k)}{\mu(a_k |s_k)} \end{align*}

注意看，虽然 $p_\pi(a_t, s_{t + 1}, a_{t+1}, \dots, s_T | s_t)$ 需要环境模型，但是在重要性权重中，由于环境模型的概率被约去，因此实际上并不需要状态转移概率。于是

V_\pi(s) = \mathbb{E}_{\tau \sim \pi} \left[G_t | s_t = s \right] = \mathbb{E}_{\tau \sim \mu} \left[\rho_{t:T-1} G_t | s_t = s\right]

有两种方法可以估计 $\mathbb{E}_{\tau \sim \mu} \left[\rho_{t:T-1} G_t | s_t = s\right]$ ，分别是 普通重要度采样 和 加权重要度采样。

普通重要度采样为

\hat V^{\mathrm{IS}}_\pi(s) = \frac{1}{N}\sum_{i=1}^N \rho_{t:T(i)-1}^{(i)}\,G_t^{(i)},

它保持了无偏性 ( $\mathbb{E}[\rho G] = V_\pi$ )，但是由于权重 $\rho$ 的方差极大，学习过程中仍然有剧烈抖动和发散等不稳定的情况存在。其中 $N$ 为轨迹数量。

加权重要度采样为

\hat V^{\mathrm{WIS}}_\pi(s) = \sum_{i=1}^N \frac{\rho_{t:T(i)-1}^{(i)}}{\sum_{j=1}^N \rho_{t:T(i)-1}^{(j)}}\,G_t^{(i)}.

这种方法显著降低了方差，因为权重被整体缩放，不至于因单条轨迹的超大权重而主导估计；但归一化也带来了有偏性（估计值收敛到行为策略下的某种加权平均，而非严格的 $V_\pi$ 。

离轨策略的策略评估算法


Input:	策略 $\pi$
Output:	动作价值函数 $Q_\pi(s, a)$
1:	任意初始化 $Q(s, a) \in \mathcal{R}$ ，令计数器 $C(s, a) \leftarrow 0$
2:	repeat
3:	$\mu \leftarrow$ 任何能包括 $\pi$ 的策略（覆盖性假设，即行为策略 $\mu$ 必须在所有状态 $s$ 下对目标策略 $\pi$ 的所有动作 $a$ 赋予非零概率，即行为策略 $\mu$ 必须”覆盖”目标策略 $\pi$ 的所有可能行为， $\forall s, a, \pi(a\vert s) > 0 \Rightarrow \mu(a \vert s) > 0\$ ）
4:	根据策略 $\mu$ 生成一幕数据 $\tau = (s_1, a_1, r_1, \dots, s_T, a_T, r_T)$
5:	$G\leftarrow 0$ 和 $W \leftarrow 1$
6：	for $t = T, \dots, 1$
7:	当 $W \ne 0$ 时
8:	$G \leftarrow \gamma G + r_t$
9:	$C(s_t, a_t) \leftarrow C(s_t, a_t) + W$
10:	$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \frac{W}{C(s_t, a_t)}[G - Q(s_t, a_t)]$
11:	$W \leftarrow W \frac{\pi(a_t \vert s_t)}{\mu(a_t \vert s_t)}$
12:	否则，若 $W = 0$ ，退出循环
13:	令 $Q_\pi(s, a) = Q(s, a),\ \forall s \in \mathcal{S}, \forall a \in \mathcal{A}$

这其中第 3 行的覆盖性假设是为了保证重要性采样比率 $\frac{\pi(a|s)}{\mu(a|s)}$ 的分母不会为 0.

离轨策略的 Monte Carlo 控制算法


Input:	$\gamma$
Output:	最优策略 $\pi$
1:	任意初始化 $Q(s, a) \in \mathcal{R}$ ，令计数器 $C(s, a) \leftarrow 0$
2:	令策略 $\pi(s) \leftarrow \arg\max_a Q(s, a)$
3:	repeat
4:	$\mu \leftarrow$ 任何 $\epsilon$ -greedy 策略
5:	根据策略 $\mu$ 生成一幕数据 $\tau = (s_1, a_1, r_1, \dots, s_T, a_T, r_T)$
6:	$G\leftarrow 0$ 和 $W \leftarrow 1$
7：	for $t = T, \dots, 1$
8:	当 $W \ne 0$ 时
9:	$G \leftarrow \gamma G + r_t$
10:	$C(s_t, a_t) \leftarrow C(s_t, a_t) + W$
11:	$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \frac{W}{C(s_t, a_t)}[G - Q(s_t, a_t)]$
12:	$\pi(s_t) = \arg\max_a Q(s_t, a)$
13:	如果 $a_t \ne \pi(s_t)$ ，则退出循环
14:	$W \leftarrow W \frac{1}{\mu(a_t \vert s_t)}$

3.3.4 一些问题#

为什么做动作选择使用的是动作价值函数，而不是状态价值函数？

解：

如果基于状态价值函数选择来更新策略，公式为

\pi(s) = \arg\max_{a \in \mathcal{A}(s)} \sum_{s' \in \mathcal{S}} p(s' | s, a) V(s')

这里的公式显然需要环境模型 $p(s' | s, a)$ 。但是如果采用动作价值函数，就不需要环境信息了

\pi(s) = \arg\max_a Q(s, a)

这里的策略用 $\pi(s)$ 表示是因为采用的是贪心策略，这样表示比概率更方便。

注意， $Q(s, a) = \sum_{s'} p(s' | s, a) V(s')$ 。如果状态转移模型是一个确定性的模型，那么， $Q(s, a) = V(s'),\ s' = \text{transition}(s, a)$ ，那么此时用状态价值函数更新策略也是可以的。