强化学习的数学原理（五）：蒙特卡洛方法
1. 蒙特卡洛方法的基本思想
1.1 回顾策略迭代 (Policy Iteration)
策略迭代是强化学习中的一个经典框架，它由两个核心步骤交替进行：
策略评估 (Policy Evaluation): 对当前的策略 $\pi_k$ 进行评估，计算出其状态价值函数 $v_{\pi_k}$。这需要求解贝尔曼期望方程： $v_{\pi_k} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}$
策略改进 (Policy Improvement): 基于计算出的价值函数，通过贪心选择来得到一个更优的策略 $\pi_{k+1}$。 $\pi_{k+1} = \arg\max_{\pi} (r_{\pi} + \gamma P_{\pi} v_{\pi_k})$
这个过程需要我们知道环境的动态模型（即 $p(s’, r | s, a)$），因此是一种 基于模型 (Model-based) 的方法。
1.2 如何将策略迭代转换为 Model-Free?
当环境模型未知时，我们无法直接计算动作价值函数 $q_k(s,a)$。这里的关键挑战就是 如何评估策略。
蒙特卡洛方法的核心思想就是利用 大数定律，通过经验采样来替代直接计算。
- 动作价值的定义: $q_{\pi}(s, a) = \mathbb{E}[G_t | S_t=s, A_t=a]$
- MC 的解决思路: 我们无法直接计算这个期望值，但我们可以通过在环境中运行策略 $\pi$ 来获得大量的回报样本 ${G_t^{(1)}, G_t^{(2)}, …, G_t^{(N)}}$，然后用这些样本的平均值来近似 $q_{\pi}(s, a)$。
这就将策略评估从依赖模型的计算，转换为了不依赖模型的、基于采样的估计。
1.3 蒙特卡洛方法估计 Action value 的流程
- 给定一个需要评估的策略 $\pi_k$。
- 从一个状态-动作对 $(s, a)$ 开始，遵循策略 $\pi_k$ 在环境中交互，生成一条完整的轨迹 (episode)。
- 记录这条轨迹从 $(s, a)$ 开始所获得的 回报 (return)，记为 $g(s,a)$。这个回报就是真实价值 $q_{\pi_k}(s,a)$ 的一个无偏样本。
- 重复步骤 2 和 3 多次，获得一组关于 $(s, a)$ 的回报样本 $\{g^{(i)}(s,a)\}$。
- 动作价值的估计值为所有样本的均值： $q_k(s,a) \approx \frac{1}{N} \sum_{i=1}^{N} g^{(i)}(s,a)$
2. MC Basic Algorithm
2.1 算法流程
MC Basic 算法是上述思想最直接的实现。
对于第 k 次迭代：
Step 1: 策略评估 使用当前策略 $\pi_k$，通过蒙特卡洛采样方法，为 所有 的状态-动作对 $(s,a)$ 估算出其价值 $q_{\pi_k}(s,a)$。
Step 2: 策略改进 基于评估出的价值函数，生成一个全新的贪心策略 $\pi_{k+1}$： $\pi_{k+1} = \arg\max_{\pi} (r_{\pi} + \gamma P_{\pi} v_{\pi_k}) $ for all $s \in S$。贪心的最优策略：$\pi_{k+1}(a^*_k|s)=1$, where $a^*_k = \arg\max_{a} q_{\pi_k}(s,a)$
2.2 Pseudocode: MC Basic (a model-free variant of policy iteration)
Initialization:
- Initial guess $\pi_0$.
Goal:
- Search for an optimal policy.
For the $k$-th iteration ($k = 0, 1, 2, \dots$), do:
For each state $s \in S$, do
For each action $a \in A(s)$, do
Collect sufficiently many episodes starting from $(s, a)$ by following $\pi_k$
Policy evaluation:
$$ q_{\pi_k}(s, a) \approx q_k(s, a) = \text{average return of all episodes starting from }(s,a) $$
Policy improvement:
$$ a_k^*(s) = \underset{a}{\operatorname{arg max}} \ q_k(s, a) $$
$$ \pi_{k+1}(a|s) = \begin{cases} 1, & a = a_k^*(s) \\ 0, & \text{otherwise} \end{cases} $$
2.3 算法的局限性
MC Basic 算法在理论上可行，但 并不实用。其主要局限性在于它的更新机制：必须在策略评估阶段，为所有的 $(s,a)$ 对收集到足够多的样本以完成评估后，才能进行 一次 策略改进。这意味着算法需要等待大量的完整轨迹生成后才能更新，效率极其低下。
2.4 Episode Length 的影响
Episode Length可以理解为探索半径，需要足够长才能从初始状态探索到target.
3. MC Exploring Starts
3.1 与 MC Basic 算法的联系
MC Exploring Starts (探索性开端) 是对 MC Basic 算法的一种改进，旨在解决其数据利用和更新效率低下的问题。
3.2 MC Basic 的数据利用方式与局限性
在 MC Basic 中，当我们为估计 $q(s_1, a_2)$ 而生成一条轨迹时： $S_1 \xrightarrow{a_2} S_2 \xrightarrow{a_4} S_1 \xrightarrow{a_2} S_2 \xrightarrow{a_3} S_5 \rightarrow \dots$ 这条轨迹实际上也访问了许多其他的状态-动作对，如 $(S_2, a_4), (S_2, a_3)$ 等。MC Basic 的基础思路没有充分利用这些“中途”产生的数据，造成了浪费。
3.3 如何更充分地利用数据：Two Data-Efficient Methods
为了提升数据利用率，我们可以记录轨迹中 所有 被访问到的状态-动作对的回报。对于在单条轨迹中被多次访问的同一个 $(s,a)$ 对，有两种主流的处理方法：
- 首次访问 (First-visit) MC: 在一条轨迹中，只使用 $(s,a)$ 第一次 被访问时所对应的回报。
- 每次访问 (Every-visit) MC: 在一条轨迹中，每一次 访问 $(s,a)$ 时所对应的回报都会被用来计算平均值。
这两种方法都比原始思路更高效地利用了数据。
3.4 策略更新的改进
- MC Basic 的局限: 如前所述，它需要在收集 所有 轨迹后才能进行一次策略更新，等待时间长。
- MC Exploring Starts 的改进: 算法被改进为 逐条轨迹更新 (episode-by-episode)。每当生成一条完整的轨迹后，就利用这条轨迹中包含的信息，对所有被访问到的 $(s,a)$ 对的价值进行更新，并立刻改进策略。这大大提高了学习效率。
3.5 Pseudocode: MC Exploring Starts (an efficient variant of MC Basic)
Initialization:
- Initial policy $\pi_0(a|s)$ and initial value $q(s, a)$ for all $(s, a)$.
- $Returns(s, a) = 0$ and $Num(s, a) = 0$ for all $(s, a)$.
Goal:
- Search for an optimal policy.
For each episode, do:
Episode generation:
Select a starting state-action pair $(s_0, a_0)$ ensuring all pairs can be selected (exploring-starts condition).
Generate an episode of length $T$:
$$ s_0, a_0, r_1, \dots, s_{T-1}, a_{T-1}, r_T $$
Initialization for this episode: $g \leftarrow 0$
For each step of the episode, $t = T-1, T-2, \dots, 0$, do
$g \leftarrow \gamma g + r_{t+1}$
$Returns(s_t, a_t) \leftarrow Returns(s_t, a_t) + g$
$Num(s_t, a_t) \leftarrow Num(s_t, a_t) + 1$
Policy evaluation:
$$ q(s_t, a_t) \leftarrow \frac{Returns(s_t, a_t)}{Num(s_t, a_t)} $$
Policy improvement:
$$ \pi(a|s_t) = \begin{cases} 1, & a = \underset{a}{\operatorname{arg max}} \ q(s_t, a) \\ 0, & \text{otherwise} \end{cases} $$
3.6 MC Exploring Starts 的局限性
该算法的核心假设是 “探索性开端”：在 MC Exploring Starts 算法中，有两种情况可以得到$return(s, a)$: 1. 轨迹的起始点为$(s, a)$; 2. 在轨迹中被访问到，但是不能保证从一个$(s, a)$出发访问到其他所有$(s’, a’)$。为了保证所有 $(s,a)$ 对都能被评估到，每个 $(s,a)$ 对都要作为一条轨迹的起点。在实际应用中，让环境从任意一个指定的动作开始往往是 不现实或不可能的，这构成了该算法的主要局限性。
4. MC $\epsilon$-Greedy Algorithm
为了克服 Exploring Starts 的不切实际的假设，我们引入一种新的策略来保证探索，从而不再需要强制的“开端”。
4.1 Soft Policies (软性策略)
一个策略被称为 软性策略，如果在该策略下，任何状态 $s$ 选择任意动作 $a$ 的概率都大于零，即 $\pi(a|s) > 0$。这意味着策略会持续地进行探索。
4.2 引入 $\epsilon$-Greedy Policy 及其作用
$\epsilon$-Greedy 策略是一种经典的软性策略，它在 利用 (Exploitation) 和 探索 (Exploration) 之间做出了平衡。
策略定义: $$ \pi(a|s) = \begin{cases} 1 - \epsilon + \frac{\epsilon}{|\mathcal{A}(s)|} & \text{for the greedy action } a^* = \arg\max_{a} q_{\pi_k}(s,a) \\ \frac{\epsilon}{|\mathcal{A}(s)|} & \text{for other non-greedy actions} \end{cases} $$
policy improvement: $$\pi_{k+1}(s) = \arg\max_{\pi \in \Pi_\epsilon} \sum_a \pi(a|s) q_{\pi_k}(s,a) $$ where $\Pi_\epsilon$ denotes the set of all $\epsilon$-Greedy policies with a fixed value of $\epsilon$
特性与作用:
- 该策略以 $1-\epsilon$ 的大概率选择当前认为最优的动作（利用），同时保留了 $\epsilon$ 的概率去随机探索其他所有动作（探索）。
- 它保证了选择“贪心”动作的概率始终不小于任何其他动作。
- 最关键的是，通过使用 $\epsilon$-Greedy 策略，我们 不再需要探索性开端，因为策略本身就内在性地保证了对所有动作的持续探索。
4.3 Pseudocode: MC $\epsilon$-Greedy (a variant of MC Exploring Starts)
Initialization:
- Initial policy $\pi_0(a|s)$ and initial value $q(s, a)$ for all $(s, a)$.
- $Returns(s, a) = 0$ and $Num(s, a) = 0$ for all $(s, a)$.
- $\epsilon \in (0, 1]$.
Goal:
- Search for an optimal policy.
For each episode, do:
Episode generation:
Select a starting state-action pair $(s_0, a_0)$ (no exploring-starts condition).
Generate an episode of length $T$:
$$ s_0, a_0, r_1, \dots, s_{T-1}, a_{T-1}, r_T $$
Initialization for this episode: $g \leftarrow 0$
For each step of the episode, $t = T-1, T-2, \dots, 0$, do
$g \leftarrow \gamma g + r_{t+1}$
$Returns(s_t, a_t) \leftarrow Returns(s_t, a_t) + g$
$Num(s_t, a_t) \leftarrow Num(s_t, a_t) + 1$
Policy evaluation:
$$ q(s_t, a_t) \leftarrow \frac{Returns(s_t, a_t)}{Num(s_t, a_t)} $$
Policy improvement: Let $a^* = \underset{a}{\operatorname{arg max}} q(s_t, a)$
$$ \pi(a|s_t) = \begin{cases} 1 - \dfrac{|\mathcal{A}(s_t)|-1}{|\mathcal{A}(s_t)|}\epsilon, & a = a^* \\ \dfrac{1}{|\mathcal{A}(s_t)|}\epsilon, & a \neq a^* \end{cases} $$
5. 总结
本文根据您的笔记，梳理了蒙特卡洛方法在强化学习中的应用与演进：
- 核心思想：从经典的 策略迭代 出发，通过 采样均值 替代期望计算，将算法改造为 Model-Free 形式。
- MC Basic：作为最基础的实现，因其 “全量更新” 机制导致效率低下而不实用。
- MC Exploring Starts：通过改进数据利用方式（First/Every-visit）和更新机制（Episode-by-Episode），大幅提升了算法效率，但其 “探索性开端” 的假设在现实中难以满足。
- MC $\epsilon$-Greedy：通过引入 软性策略，在策略层面保证了持续的探索，从而摆脱了对探索性开端的依赖，成为一种更加实用和广泛的蒙特卡洛控制算法。