第5章：蒙特卡洛方法（Monte Carlo Methods）
一、导读
1.1 本章学习目标
第5章介绍第一种无模型（model-free）的强化学习方法——蒙特卡洛（MC）方法。与动态规划不同，蒙特卡洛方法不需要环境的转移概率模型，它通过与环境交互获得完整的回合（episode）数据，用实际观测到的回报来估计价值函数。
本章的核心学习目标包括：
- 理解蒙特卡洛方法的核心思想：用采样回报的均值来估计期望价值
- 掌握首次访问（First-Visit）和每次访问（Every-Visit）MC 的区别
- 理解 MC 策略评估和控制的方法
- 掌握探索性启动（Exploring Starts）和 $\epsilon$-soft 策略的必要性
- 了解 MC 方法的优缺点：无偏估计但高方差
1.2 为什么本章如此重要
蒙特卡洛方法是从"已知模型"到"未知模型"的关键跨越。在现实世界中，我们通常不知道环境的转移概率，但可以通过交互获得经验数据。MC 方法展示了如何仅凭经验数据来学习最优策略。
MC 方法的另一个重要特点是它只在回合结束时更新，使用真实的回报而非估计值（自举）。这使得 MC 方法具有无偏性，但也带来了高方差的问题。理解 MC 方法的特点，为后续学习时序差分（TD）方法奠定了基础。
1.3 核心问题引导
为什么蒙特卡洛方法不需要环境模型？它用什么替代了模型？
首次访问 MC 和每次访问 MC 有什么区别？它们是否收敛到相同的值？
为什么 MC 控制需要探索性启动或 $\epsilon$-soft 策略？
MC 方法的方差为什么高？如何降低方差？
MC 方法与动态规划相比有什么优势和劣势？
二、核心概念详解
5.1 蒙特卡洛策略评估
蒙特卡洛策略评估的核心思想非常简单：要估计状态 $s$ 在策略 $\pi$ 下的价值 $v_\pi(s)$，只需收集所有经过状态 $s$ 的回合的回报，取平均值。
python
import numpy as np
from collections import defaultdict
class BlackJack:
def __init__(self):
self.deal()
def deal(self):
self.player = [self._draw_card(), self._draw_card()]
self.dealer = [self._draw_card(), self._draw_card()]
def _draw_card(self):
return min(10, np.random.randint(1, 14))
def _hand_value(self, hand):
value = sum(hand)
if 1 in hand and value + 10 <= 21:
value += 10
return value
def step(self, action):
if action == 'hit':
self.player.append(self._draw_card())
if self._hand_value(self.player) > 21:
return self._get_state(), -1, True
return self._get_state(), 0, False
else:
while self._hand_value(self.dealer) < 17:
self.dealer.append(self._draw_card())
player_val = self._hand_value(self.player)
dealer_val = self._hand_value(self.dealer)
if dealer_val > 21 or player_val > dealer_val:
reward = 1
elif player_val == dealer_val:
reward = 0
else:
reward = -1
return self._get_state(), reward, True
def _get_state(self):
player_val = self._hand_value(self.player)
usable_ace = 1 in self.player and sum(self.player) + 10 <= 21
dealer_showing = self.dealer[0]
return (player_val, dealer_showing, usable_ace)
def mc_policy_evaluation(env_factory, policy, n_episodes=10000):
returns = defaultdict(list)
V = defaultdict(float)
for _ in range(n_episodes):
env = env_factory()
state = env._get_state()
episode = []
done = False
while not done:
action = policy(state)
next_state, reward, done = env.step(action)
episode.append((state, action, reward))
state = next_state
G = 0
visited = set()
for t in range(len(episode) - 1, -1, -1):
state, action, reward = episode[t]
G += reward
if state not in visited:
visited.add(state)
returns[state].append(G)
V[state] = np.mean(returns[state])
return V
def random_policy(state):
return np.random.choice(['hit', 'stick'])
V = mc_policy_evaluation(BlackJack, random_policy, n_episodes=50000)
print(f"Number of states visited: {len(V)}")
sample_states = [(20, 10, True), (16, 10, False), (12, 2, True)]
for s in sample_states:
print(f"V({s}) = {V.get(s, 0):.3f}")5.2 首次访问 vs 每次访问 MC
- 首次访问 MC：只使用每个回合中状态 $s$ 第一次被访问时的回报来估计 $v(s)$
- 每次访问 MC：使用每个回合中状态 $s$ 每次被访问时的回报
首次访问 MC 的估计是无偏的（收敛到 $v_\pi(s)$），而每次访问 MC 有轻微偏差但通常有更小的均方误差。在实践中，两者差异不大，每次访问 MC 更常用。
python
def mc_first_visit(env_factory, policy, n_episodes=10000):
returns = defaultdict(list)
V = defaultdict(float)
for _ in range(n_episodes):
env = env_factory()
state = env._get_state()
episode = []
done = False
while not done:
action = policy(state)
next_state, reward, done = env.step(action)
episode.append((state, action, reward))
state = next_state
G = 0
visited = set()
for t in range(len(episode) - 1, -1, -1):
s, a, r = episode[t]
G += r
if s not in visited:
visited.add(s)
returns[s].append(G)
V[s] = np.mean(returns[s])
return V
def mc_every_visit(env_factory, policy, n_episodes=10000):
returns = defaultdict(list)
V = defaultdict(float)
for _ in range(n_episodes):
env = env_factory()
state = env._get_state()
episode = []
done = False
while not done:
action = policy(state)
next_state, reward, done = env.step(action)
episode.append((state, action, reward))
state = next_state
G = 0
for t in range(len(episode) - 1, -1, -1):
s, a, r = episode[t]
G += r
returns[s].append(G)
V[s] = np.mean(returns[s])
return V
V_fv = mc_first_visit(BlackJack, random_policy, n_episodes=10000)
V_ev = mc_every_visit(BlackJack, random_policy, n_episodes=10000)
test_states = [(20, 10, True), (16, 10, False)]
for s in test_states:
print(f"State {s}: First-Visit={V_fv.get(s,0):.3f}, "
f"Every-Visit={V_ev.get(s,0):.3f}")5.3 蒙特卡洛控制
蒙特卡洛控制的目标是找到最优策略。基本思路是：用 MC 评估得到 $q_\pi(s,a)$，然后贪心地改进策略。
关键问题是如何保证探索：如果策略是确定性的，某些状态-动作对可能永远不会被访问。解决方案有两种：
探索性启动（Exploring Starts）：每个回合从一个随机的状态-动作对开始
$\epsilon$-soft 策略：保证每个动作在每个状态下都有非零的概率被选择
python
class SimpleGridEnv:
def __init__(self, size=5):
self.size = size
self.goal = (size-1, size-1)
self.state = (0, 0)
def reset(self):
self.state = (0, 0)
return self.state
def step(self, action):
moves = [(-1,0),(1,0),(0,-1),(0,1)]
dr, dc = moves[action]
r, c = self.state
nr, nc = max(0, min(self.size-1, r+dr)), max(0, min(self.size-1, c+dc))
self.state = (nr, nc)
reward = 1.0 if self.state == self.goal else -0.04
done = self.state == self.goal
return self.state, reward, done
def mc_control_es(env_factory, n_episodes=10000, gamma=0.99):
env = env_factory()
n_actions = 4
Q = defaultdict(lambda: np.zeros(n_actions))
returns = defaultdict(lambda: defaultdict(list))
policy = defaultdict(lambda: np.random.randint(n_actions))
for ep in range(n_episodes):
env = env_factory()
s0 = (np.random.randint(env.size), np.random.randint(env.size))
a0 = np.random.randint(n_actions)
env.state = s0
episode = [(s0, a0, 0)]
state = s0
done = False
first_step = True
while not done:
if first_step:
action = a0
first_step = False
else:
action = policy[state]
next_state, reward, done = env.step(action)
episode.append((next_state, action, reward))
state = next_state
G = 0
visited = set()
for t in range(len(episode) - 1, -1, -1):
s, a, r = episode[t]
G = gamma * G + r
sa = (s, a)
if sa not in visited:
visited.add(sa)
returns[s][a].append(G)
Q[s][a] = np.mean(returns[s][a])
best_a = np.argmax(Q[s])
policy[s] = best_a
return Q, policy
Q, pi = mc_control_es(SimpleGridEnv, n_episodes=5000)
print("MC Control with Exploring Starts")
print(f"Number of state-action pairs: {len(Q)}")5.4 $\epsilon$-soft 策略与 GLIE
在实践中，探索性启动往往不现实（我们不能随意设置起始状态）。更常用的方法是使用 $\epsilon$-soft 策略：
$$\pi(a|s) \geq \frac{\epsilon}{|\mathcal{A}(s)|}$$
GLIE（Greedy in the Limit with Infinite Exploration） 条件要求：
所有状态-动作对被无限次访问
策略在极限情况下收敛到贪心策略
一个满足 GLIE 的常见策略是 $\epsilon$-greedy，其中 $\epsilon$ 按 $\epsilon_t = 1/t$ 衰减。
python
def mc_control_epsilon_greedy(env_factory, n_episodes=10000, gamma=0.99):
env = env_factory()
n_actions = 4
Q = defaultdict(lambda: np.zeros(n_actions))
N = defaultdict(lambda: np.zeros(n_actions))
policy = defaultdict(lambda: 0)
for ep in range(n_episodes):
epsilon = 1.0 / (ep + 1)
env = env_factory()
state = env.reset()
episode = []
done = False
while not done:
if np.random.random() < epsilon:
action = np.random.randint(n_actions)
else:
action = policy[state]
next_state, reward, done = env.step(action)
episode.append((state, action, reward))
state = next_state
G = 0
for t in range(len(episode) - 1, -1, -1):
s, a, r = episode[t]
G = gamma * G + r
N[s][a] += 1
Q[s][a] += (G - Q[s][a]) / N[s][a]
policy[s] = np.argmax(Q[s])
return Q, policy
Q, pi = mc_control_epsilon_greedy(SimpleGridEnv, n_episodes=5000)
print("MC Control with epsilon-greedy (GLIE)")5.5 蒙特卡洛方法的优缺点
优点：
- 不需要环境模型，直接从经验学习
- 估计是无偏的（不受 bootstrap 偏差影响）
- 可以聚焦于特定状态：不需要对所有状态都进行好的估计
- 适合处理回合制任务（如游戏）
缺点：
- 高方差：回报取决于整个回合的随机性
- 必须等到回合结束才能更新
- 不适用于持续性任务（没有终止的任务）
- 样本效率低：需要大量回合才能收敛
三、实战案例
3.1 案例一：二十一点（Blackjack）的最优策略
python
class BlackJackGame:
def __init__(self):
self.reset()
def reset(self):
self.player = [self._draw(), self._draw()]
self.dealer = [self._draw(), self._draw()]
return self._get_state()
def _draw(self):
return min(10, np.random.randint(1, 14))
def _sum(self, hand):
s = sum(hand)
if 1 in hand and s + 10 <= 21:
return s + 10, True
return s, False
def _get_state(self):
p_val, p_ace = self._sum(self.player)
d_show = self.dealer[0]
return (p_val, d_show, int(p_ace))
def step(self, action):
if action == 0:
self.player.append(self._draw())
p_val, _ = self._sum(self.player)
if p_val > 21:
return self._get_state(), -1, True
return self._get_state(), 0, False
else:
while True:
d_val, _ = self._sum(self.dealer)
if d_val >= 17:
break
self.dealer.append(self._draw())
p_val, _ = self._sum(self.player)
d_val, _ = self._sum(self.dealer)
if d_val > 21 or p_val > d_val:
return self._get_state(), 1, True
elif p_val == d_val:
return self._get_state(), 0, True
else:
return self._get_state(), -1, True
def blackjack_mc(n_episodes=500000):
n_actions = 2
Q = defaultdict(lambda: np.zeros(n_actions))
N = defaultdict(lambda: np.zeros(n_actions))
for ep in range(n_episodes):
epsilon = 1.0 / (ep // 1000 + 1)
env = BlackJackGame()
state = env.reset()
episode = []
done = False
while not done:
s_key = state
if np.random.random() < epsilon:
action = np.random.randint(n_actions)
else:
action = int(np.argmax(Q[s_key]))
next_state, reward, done = env.step(action)
episode.append((s_key, action, reward))
state = next_state
G = 0
for t in range(len(episode) - 1, -1, -1):
s, a, r = episode[t]
G += r
N[s][a] += 1
Q[s][a] += (G - Q[s][a]) / N[s][a]
policy = {}
for s in Q:
policy[s] = int(np.argmax(Q[s]))
return Q, policy
Q, pi = blackjack_mc(n_episodes=100000)
print("Blackjack MC results:")
action_names = ['hit', 'stick']
for state in [(20, 10, 1), (16, 10, 0), (12, 3, 1), (21, 7, 0)]:
if state in pi:
print(f" State {state}: {action_names[pi[state]]}")3.2 案例二：MC 方法的收敛曲线
python
def mc_convergence_analysis():
env_factory = SimpleGridEnv
n_actions = 4
for n_ep in [100, 1000, 5000, 10000]:
Q, pi = mc_control_epsilon_greedy(env_factory, n_episodes=n_ep)
env = env_factory()
state = env.reset()
steps = 0
done = False
while not done and steps < 50:
action = pi.get(state, 0)
state, _, done = env.step(action)
steps += 1
success = 1 if done else 0
print(f" Episodes={n_ep}: solution found={'Yes' if done else 'No'}, "
f"steps={steps}")
mc_convergence_analysis()四、本章小结
第5章介绍了蒙特卡洛方法，核心要点：
MC 方法不需要环境模型：通过采样回报的均值来估计价值函数
首次访问 vs 每次访问：两者都收敛，实践中每次访问更常用
MC 控制：需要探索性启动或 $\epsilon$-soft 策略来保证探索
GLIE 条件：保证无限探索且渐近贪心
优点：无偏、不需要模型、可以聚焦特定状态
缺点：高方差、必须等到回合结束、样本效率低
五、思考与练习
思考题
为什么 MC 方法的方差比 TD 方法高？
如果一个任务没有终止（持续性任务），MC 方法还能使用吗？为什么？
$\epsilon$-greedy 策略中，$\epsilon$ 应该如何衰减才能满足 GLIE 条件？
编程练习
在 Grid World 上比较首次访问和每次访问 MC 的均方误差
实现带基线（baseline）的 MC 控制方法，观察方差是否降低
比较不同 $\epsilon$ 衰减策略对收敛速度的影响