モンテカルロ法（Monte Carlo method, MC法）は、環境のモデル（遷移確率や報酬関数）が未知の場合でも、エピソード（試行）の経験データから価値関数を推定し、最適方策を学習できる手法です。動的計画法がモデルベースの手法であるのに対し、モンテカルロ法はモデルフリーの手法であり、環境との実際の相互作用から得られるサンプルのみを用いて学習します。
モンテカルロ法のアイデアは単純です。方策に従ってエピソードを多数生成し、各状態（または状態-行動ペア）から得られたリターンの平均を計算することで、価値関数を推定します。大数の法則により、サンプル数を増やすほど推定精度が向上していきます。
本記事の内容
- モデルフリーの動機と方策評価の問題設定
- 初回訪問MC法と全訪問MC法の定義と違い
- $V^{\pi}(s)$ のMC推定の不偏性と一致性の証明
- モンテカルロ制御（MC方策改善）
- $\varepsilon$-greedy方策による探索
- 重点サンプリング（Importance Sampling）による方策オフ型MC
- 普通ISと加重ISの分散比較
- Pythonでブラックジャック環境でのMC法の完全実装
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
モデルフリーの動機
動的計画法は強力ですが、2つの重要な前提を必要とします。
- 環境モデルが既知: 遷移確率 $P(s’|s,a)$ と報酬関数 $R(s,a,s’)$ が完全に分かっている
- 計算量の問題: 全ての状態を毎回更新する必要があり、巨大な状態空間では計算が困難
現実の多くの問題ではこれらの前提が満たされません。例えば、ロボットが実環境で動作する場合、物理法則に基づく正確な遷移確率を記述することは極めて困難です。
モンテカルロ法は、環境との実際の相互作用（エピソード）から得られる経験データのみを用いて学習します。エピソードとは、初期状態から終端状態に至るまでの状態-行動-報酬の系列のことです。
$$ S_0, A_0, R_1, S_1, A_1, R_2, \dots, S_{T-1}, A_{T-1}, R_T, S_T $$
ここで $S_T$ は終端状態、$T$ はエピソード長です。
モンテカルロ方策評価
基本アイデア
$V^{\pi}(s) = \mathbb{E}_{\pi}[G_t \mid S_t = s]$ の定義そのものに従い、方策 $\pi$ に従って多数のエピソードを生成し、状態 $s$ を訪問した時点からの実際のリターン $G_t$ のサンプル平均を計算します。
大数の法則により、サンプル数が十分大きければ
$$ \hat{V}^{\pi}(s) = \frac{1}{N(s)} \sum_{i=1}^{N(s)} G_t^{(i)} \to V^{\pi}(s) \quad (N(s) \to \infty) $$
ここで $N(s)$ は状態 $s$ の訪問回数、$G_t^{(i)}$ は $i$ 番目の訪問におけるリターンです。
初回訪問MC法（First-Visit MC）
1つのエピソード中に状態 $s$ を複数回訪問する場合、最初の訪問のリターンのみを使います。
アルゴリズム:
- 空のリターンリスト $\text{Returns}(s) \leftarrow []$ を全状態について初期化
- 繰り返し:
– 方策 $\pi$ に従ってエピソード $S_0, A_0, R_1, \dots, S_T$ を生成
– $G \leftarrow 0$
– $t = T-1, T-2, \dots, 0$ について逆順に:
- $G \leftarrow \gamma G + R_{t+1}$
- $S_t$ がこのエピソード内で $t$ 以前に出現していなければ（初回訪問）:
- $\text{Returns}(S_t)$ に $G$ を追加
- $V(S_t) \leftarrow \text{average}(\text{Returns}(S_t))$
全訪問MC法（Every-Visit MC）
1つのエピソード中に状態 $s$ を訪問するたびに、全ての訪問のリターンを使います。
アルゴリズム:
初回訪問MCとほぼ同じですが、「$S_t$ がこのエピソード内で $t$ 以前に出現していなければ」という条件を除去し、全ての訪問でリターンを追加します。
初回訪問MCと全訪問MCの比較
| 特性 | 初回訪問MC | 全訪問MC |
|---|---|---|
| 不偏性 | 不偏推定量 | 漸近的に不偏（有限サンプルではバイアスあり） |
| 分散 | やや大きい | やや小さい |
| データ効率 | 低い（一部のサンプルを捨てる） | 高い（全サンプルを利用） |
| 実装 | 初回訪問チェックが必要 | シンプル |
不偏性と一致性の証明
初回訪問MCの不偏性
定理: 初回訪問MC法による $V^{\pi}(s)$ の推定は不偏である。
証明:
$G_t^{(i)}$ を $i$ 番目のエピソードで状態 $s$ を初めて訪問した時点からのリターンとします。各エピソードは独立であり、方策 $\pi$ に従って生成されるため
$$ \mathbb{E}[G_t^{(i)}] = V^{\pi}(s), \quad \forall i $$
これはリターンの定義 $V^{\pi}(s) = \mathbb{E}_{\pi}[G_t \mid S_t = s]$ そのものです。
MC推定量は
$$ \hat{V}^{\pi}(s) = \frac{1}{N(s)} \sum_{i=1}^{N(s)} G_t^{(i)} $$
期待値を取ると
$$ \begin{align} \mathbb{E}[\hat{V}^{\pi}(s)] &= \mathbb{E}\left[\frac{1}{N(s)} \sum_{i=1}^{N(s)} G_t^{(i)}\right] \\ &= \frac{1}{N(s)} \sum_{i=1}^{N(s)} \mathbb{E}[G_t^{(i)}] \\ &= \frac{1}{N(s)} \sum_{i=1}^{N(s)} V^{\pi}(s) \\ &= V^{\pi}(s) \end{align} $$
2行目で期待値の線形性を用いました。3行目で各 $G_t^{(i)}$ の期待値が $V^{\pi}(s)$ であることを代入しました。よって、$\hat{V}^{\pi}(s)$ は不偏推定量です。 $\square$
一致性（大数の法則）
定理: $N(s) \to \infty$ のとき、$\hat{V}^{\pi}(s) \xrightarrow{a.s.} V^{\pi}(s)$（概収束する）。
証明:
$G_t^{(i)}$ は独立同一分布（i.i.d.）に従い、$\mathbb{E}[G_t^{(i)}] = V^{\pi}(s)$ です。リターンが有界（$|G_t| \leq R_{\max}/(1-\gamma)$）であるから、特に $\mathbb{E}[|G_t^{(i)}|] < \infty$ が成り立ちます。
大数の強法則により
$$ \frac{1}{N(s)} \sum_{i=1}^{N(s)} G_t^{(i)} \xrightarrow{a.s.} \mathbb{E}[G_t^{(i)}] = V^{\pi}(s) \quad (N(s) \to \infty) $$
よって、MC推定量は一致推定量です。 $\square$
MC推定量の分散
$G_t^{(i)}$ の分散を $\sigma^2 = \text{Var}(G_t)$ とすると、MC推定量の分散は
$$ \text{Var}(\hat{V}^{\pi}(s)) = \frac{\sigma^2}{N(s)} $$
です。これは標準的な標本平均の分散であり、$N(s)$ に反比例して減少します。
モンテカルロ制御
方策評価だけでなく、方策の改善も行うことで最適方策を学習するのがMC制御です。
行動価値関数 $Q^{\pi}$ の推定
モデルフリーの設定では $V^{\pi}$ だけでは方策改善ができません。方策改善には
$$ \pi'(s) = \arg\max_{a} \sum_{s’} P(s’|s,a)[R(s,a,s’) + \gamma V^{\pi}(s’)] $$
の計算が必要ですが、$P(s’|s,a)$ が未知だからです。そのため、行動価値関数 $Q^{\pi}(s,a)$ を直接推定します。
$$ \hat{Q}^{\pi}(s,a) = \frac{1}{N(s,a)} \sum_{i=1}^{N(s,a)} G_t^{(i)} $$
$Q^{\pi}$ が分かれば、モデル不要で貪欲方策を構成できます。
$$ \pi'(s) = \arg\max_{a} Q^{\pi}(s, a) $$
探索の問題
しかし、完全な貪欲方策では問題が生じます。方策 $\pi$ が決定的の場合、選ばれない行動の $Q^{\pi}(s,a)$ は更新されません。つまり、エージェントは既知の良い行動のみを取り続け、未知のもっと良い行動を発見できない可能性があります。これが探索と利用のジレンマ（exploration-exploitation dilemma）です。
$\varepsilon$-greedy方策
探索を保証するために、$\varepsilon$-greedy方策を用います。
$$ \pi_{\varepsilon}(a|s) = \begin{cases} 1 – \varepsilon + \frac{\varepsilon}{|\mathcal{A}|} & \text{if } a = \arg\max_{a’} Q(s, a’) \\ \frac{\varepsilon}{|\mathcal{A}|} & \text{otherwise} \end{cases} $$
確率 $1 – \varepsilon$ で現在の最良行動を選択（利用）し、確率 $\varepsilon$ でランダムに行動を選択（探索）します。
$\varepsilon$-greedy方策はソフト方策の一種であり、$\pi(a|s) > 0$ が全ての $s, a$ に対して成り立ちます。これにより、全ての状態-行動ペアが無限回訪問されることが保証されます。
$\varepsilon$-greedy方策改善定理
定理: $\varepsilon$-greedy方策 $\pi’$ は、元の $\varepsilon$-greedy方策 $\pi$ 以上に良い。すなわち $V^{\pi’}(s) \geq V^{\pi}(s)$。
証明の概略:
$$ \begin{align} Q^{\pi}(s, \pi'(s)) &= \sum_{a} \pi'(a|s) Q^{\pi}(s, a) \\ &= \frac{\varepsilon}{|\mathcal{A}|} \sum_{a} Q^{\pi}(s, a) + (1 – \varepsilon) \max_{a} Q^{\pi}(s, a) \\ &\geq \frac{\varepsilon}{|\mathcal{A}|} \sum_{a} Q^{\pi}(s, a) + (1 – \varepsilon) \sum_{a} \frac{\pi(a|s) – \frac{\varepsilon}{|\mathcal{A}|}}{1 – \varepsilon} Q^{\pi}(s, a) \\ &= \sum_{a} \pi(a|s) Q^{\pi}(s, a) \\ &= V^{\pi}(s) \end{align} $$
3行目で $\max_a Q^{\pi}(s,a) \geq \sum_a w_a Q^{\pi}(s,a)$（$w_a$ は任意の確率分布の重み）を用い、$w_a = \frac{\pi(a|s) – \varepsilon/|\mathcal{A}|}{1-\varepsilon}$ としました。 $\square$
MC制御のアルゴリズム（On-policy）
MC制御のアルゴリズム（方策オン型、$\varepsilon$-greedy）は以下のようになります。
- $Q(s,a)$ を任意に初期化、$\text{Returns}(s,a) \leftarrow []$ を初期化
- 繰り返し:
– $\varepsilon$-greedy方策 $\pi$ に従ってエピソードを生成
– $G \leftarrow 0$
– $t = T-1, T-2, \dots, 0$ について逆順に:
- $G \leftarrow \gamma G + R_{t+1}$
- $(S_t, A_t)$ がこのエピソード内で初回訪問なら:
- $\text{Returns}(S_t, A_t)$ に $G$ を追加
- $Q(S_t, A_t) \leftarrow \text{average}(\text{Returns}(S_t, A_t))$
- 全ての $s$ について: $\pi(s) \leftarrow \varepsilon\text{-greedy}(Q(s, \cdot))$
重点サンプリング（Importance Sampling）
方策オン型 vs 方策オフ型
これまで説明したMC法は方策オン型（on-policy）です。学習対象の方策（ターゲット方策）とデータ収集に使う方策（行動方策）が同一です。
方策オフ型（off-policy）では、データ収集に行動方策 $b$ を用い、ターゲット方策 $\pi$ の価値を推定します。行動方策 $b$ は探索を行い、ターゲット方策 $\pi$ は最適（貪欲）方策にできるため、探索と最適化を分離できます。
重点サンプリング比
行動方策 $b$ のもとで生成されたエピソードのリターンに、重点サンプリング比（importance sampling ratio）を掛けることで、ターゲット方策 $\pi$ のもとでの期待値を推定します。
時刻 $t$ から $T-1$ までの軌跡 $A_t, S_{t+1}, A_{t+1}, \dots, S_T$ について、方策 $\pi$ と $b$ のもとでの確率比は
$$ \rho_{t:T-1} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)}{b(A_k | S_k)} $$
この比率を導出しましょう。軌跡の確率は
$$ \begin{align} \Pr_{\pi}(A_t, S_{t+1}, \dots, S_T) &= \prod_{k=t}^{T-1} \pi(A_k | S_k) P(S_{k+1} | S_k, A_k) \\ \Pr_{b}(A_t, S_{t+1}, \dots, S_T) &= \prod_{k=t}^{T-1} b(A_k | S_k) P(S_{k+1} | S_k, A_k) \end{align} $$
比を取ると
$$ \rho_{t:T-1} = \frac{\Pr_{\pi}(A_t, S_{t+1}, \dots, S_T)}{\Pr_{b}(A_t, S_{t+1}, \dots, S_T)} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)}{b(A_k | S_k)} $$
遷移確率 $P(S_{k+1}|S_k, A_k)$ は分子・分母で共通であるためキャンセルされます。これが重点サンプリングの大きな利点で、環境モデルが不要です。
普通重点サンプリング（Ordinary IS）
$$ V^{\pi}(s) \approx \hat{V}_{\text{OIS}}(s) = \frac{1}{N(s)} \sum_{i=1}^{N(s)} \rho_{t_i:T_i-1} G_{t_i} $$
性質: – 不偏推定量: $\mathbb{E}_b[\rho_{t:T-1} G_t] = V^{\pi}(s)$ – 分散が大きい: $\rho_{t:T-1}$ が非常に大きくなりうる
不偏性の証明:
$$ \begin{align} \mathbb{E}_b[\rho_{t:T-1} G_t] &= \sum_{\tau} \Pr_b(\tau) \cdot \frac{\Pr_{\pi}(\tau)}{\Pr_b(\tau)} \cdot G_t(\tau) \\ &= \sum_{\tau} \Pr_{\pi}(\tau) \cdot G_t(\tau) \\ &= \mathbb{E}_{\pi}[G_t] = V^{\pi}(s) \end{align} $$
ここで $\tau$ は軌跡全体を表します。
加重重点サンプリング（Weighted IS）
$$ \hat{V}_{\text{WIS}}(s) = \frac{\sum_{i=1}^{N(s)} \rho_{t_i:T_i-1} G_{t_i}}{\sum_{i=1}^{N(s)} \rho_{t_i:T_i-1}} $$
性質: – バイアスあり（有限サンプルでは不偏でない） – 分散が小さい: 重みの正規化により安定 – 漸近的に不偏
普通ISと加重ISの分散比較
| 特性 | 普通IS | 加重IS |
|---|---|---|
| バイアス | なし（不偏） | あり（漸近的に消失） |
| 分散 | 大（無限分散の可能性あり） | 小（有界） |
| $N(s) = 1$ | リターンに $\rho$ を掛けた値 | 常にリターンそのもの |
| 実用性 | 分散が問題 | 多くの場合こちらが優れる |
普通ISの分散は $\rho$ の分散に依存し、方策 $\pi$ と $b$ が大きく異なる場合（$\rho$ が大きな値を取る場合）、分散が爆発する可能性があります。加重ISは $\rho$ の大きさに対してロバストであり、実用的にはほとんどの場合で加重ISが好まれます。
Pythonでの実装
ブラックジャック環境
ブラックジャックは、MC法の古典的なベンチマーク問題です。
ルール: – プレイヤーとディーラーがカードを引き、手札の合計が21に近い方が勝ち – 21を超えたら負け（バスト） – プレイヤーはヒット（カードを引く）かスティック（引くのをやめる）を選択 – ディーラーは合計17以上になるまで引く – エース（A）は1または11として数える（使用可能なエース）
import numpy as np
import matplotlib.pyplot as plt
from collections import defaultdict
class BlackjackEnv:
"""シンプルなブラックジャック環境"""
def __init__(self):
# 行動: 0 = スティック, 1 = ヒット
self.action_space = [0, 1]
def draw_card(self):
"""カードを1枚引く（1-10, 絵札は10）"""
card = min(np.random.randint(1, 14), 10)
return card
def hand_value(self, hand):
"""手札の合計値と使用可能なエースの有無を計算"""
total = sum(hand)
usable_ace = False
# エース（1）を11として使えるか
if 1 in hand and total + 10 <= 21:
total += 10
usable_ace = True
return total, usable_ace
def reset(self):
"""環境をリセットして初期状態を返す"""
# プレイヤーの手札
self.player_hand = [self.draw_card(), self.draw_card()]
# ディーラーの見せカード
self.dealer_showing = self.draw_card()
# ディーラーの裏カード
self.dealer_hidden = self.draw_card()
player_sum, usable_ace = self.hand_value(self.player_hand)
# プレイヤーの合計が12未満なら自動的にヒット
while player_sum < 12:
self.player_hand.append(self.draw_card())
player_sum, usable_ace = self.hand_value(self.player_hand)
# 状態: (プレイヤーの合計, ディーラーの見せカード, 使用可能なエースの有無)
self.state = (player_sum, self.dealer_showing, usable_ace)
self.done = False
return self.state
def step(self, action):
"""行動を実行して次の状態、報酬、終了フラグを返す"""
if action == 1: # ヒット
self.player_hand.append(self.draw_card())
player_sum, usable_ace = self.hand_value(self.player_hand)
if player_sum > 21:
# バスト
self.done = True
return (player_sum, self.dealer_showing, usable_ace), -1, True
self.state = (player_sum, self.dealer_showing, usable_ace)
return self.state, 0, False
else: # スティック
player_sum, _ = self.hand_value(self.player_hand)
# ディーラーのプレイ
dealer_hand = [self.dealer_showing, self.dealer_hidden]
dealer_sum, _ = self.hand_value(dealer_hand)
while dealer_sum < 17:
dealer_hand.append(self.draw_card())
dealer_sum, _ = self.hand_value(dealer_hand)
# 結果判定
self.done = True
if dealer_sum > 21:
reward = 1 # ディーラーバスト
elif dealer_sum > player_sum:
reward = -1
elif dealer_sum < player_sum:
reward = 1
else:
reward = 0 # 引き分け
return self.state, reward, True
def generate_episode(env, policy=None):
"""方策に従ってエピソードを1つ生成"""
episode = []
state = env.reset()
while True:
if policy is None:
# ランダム方策
action = np.random.choice(env.action_space)
else:
action = policy(state)
next_state, reward, done = env.step(action)
episode.append((state, action, reward))
if done:
break
state = next_state
return episode
MC方策評価（初回訪問）
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from collections import defaultdict
# BlackjackEnv と generate_episode は上で定義済みとする
def mc_policy_evaluation(env, policy, num_episodes=500000, gamma=1.0):
"""初回訪問モンテカルロ方策評価"""
V = defaultdict(float)
returns_count = defaultdict(int)
returns_sum = defaultdict(float)
for episode_idx in range(num_episodes):
episode = generate_episode(env, policy)
# リターンの計算（逆順）
G = 0
visited = set()
for t in range(len(episode) - 1, -1, -1):
state, action, reward = episode[t]
G = gamma * G + reward
# 初回訪問チェック
if state not in visited:
visited.add(state)
returns_sum[state] += G
returns_count[state] += 1
V[state] = returns_sum[state] / returns_count[state]
return V
def plot_value_function(V, title, figsize=(12, 8)):
"""ブラックジャックの価値関数を3Dで可視化"""
fig, axes = plt.subplots(1, 2, figsize=figsize, subplot_kw={'projection': '3d'})
for idx, usable_ace in enumerate([True, False]):
ax = axes[idx]
x = np.arange(1, 11) # ディーラーの見せカード
y = np.arange(12, 22) # プレイヤーの合計
X, Y = np.meshgrid(x, y)
Z = np.zeros_like(X, dtype=float)
for i in range(len(y)):
for j in range(len(x)):
state = (y[i], x[j], usable_ace)
Z[i, j] = V.get(state, 0)
ax.plot_surface(X, Y, Z, cmap='RdYlGn', edgecolor='none', alpha=0.9)
ax.set_xlabel('Dealer Showing', fontsize=10)
ax.set_ylabel('Player Sum', fontsize=10)
ax.set_zlabel('$V^{\\pi}(s)$', fontsize=10)
ace_str = "Usable Ace" if usable_ace else "No Usable Ace"
ax.set_title(f'{ace_str}', fontsize=12)
ax.view_init(elev=20, azim=-120)
plt.suptitle(title, fontsize=15)
plt.tight_layout()
plt.show()
# 固定方策: 合計20以上ならスティック、それ以外はヒット
def simple_policy(state):
player_sum, _, _ = state
return 0 if player_sum >= 20 else 1
# MC方策評価の実行
env = BlackjackEnv()
V = mc_policy_evaluation(env, simple_policy, num_episodes=500000)
plot_value_function(V, "MC Policy Evaluation: Stick on 20+")
MC制御（On-policy, $\varepsilon$-greedy）
import numpy as np
import matplotlib.pyplot as plt
from collections import defaultdict
# BlackjackEnv は上で定義済みとする
def mc_control_epsilon_greedy(env, num_episodes=1000000, gamma=1.0, epsilon=0.1):
"""
On-policy 初回訪問MC制御（ε-greedy）
"""
Q = defaultdict(lambda: np.zeros(2)) # Q(s, a): 2行動
returns_count = defaultdict(lambda: np.zeros(2))
returns_sum = defaultdict(lambda: np.zeros(2))
def epsilon_greedy_policy(state):
"""ε-greedy方策"""
if np.random.random() < epsilon:
return np.random.choice(env.action_space)
else:
return np.argmax(Q[state])
for episode_idx in range(num_episodes):
# エピソード生成
episode = []
state = env.reset()
while True:
action = epsilon_greedy_policy(state)
next_state, reward, done = env.step(action)
episode.append((state, action, reward))
if done:
break
state = next_state
# リターンの計算と更新（逆順）
G = 0
visited = set()
for t in range(len(episode) - 1, -1, -1):
state, action, reward = episode[t]
G = gamma * G + reward
sa = (state, action)
if sa not in visited:
visited.add(sa)
returns_sum[state][action] += G
returns_count[state][action] += 1
Q[state][action] = returns_sum[state][action] / returns_count[state][action]
# 最終的な貪欲方策を抽出
policy = {}
for state in Q:
policy[state] = np.argmax(Q[state])
# 価値関数を計算
V = {}
for state in Q:
V[state] = np.max(Q[state])
return Q, V, policy
# MC制御の実行
env = BlackjackEnv()
Q, V_optimal, optimal_policy = mc_control_epsilon_greedy(
env, num_episodes=1000000, epsilon=0.1
)
# 最適価値関数の可視化
plot_value_function(V_optimal, "MC Control ($\\varepsilon$-greedy): Optimal Value Function")
最適方策の可視化
import numpy as np
import matplotlib.pyplot as plt
# 上のコードで optimal_policy が定義済みとする
def plot_policy(policy, title):
"""ブラックジャックの最適方策を可視化"""
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
for idx, usable_ace in enumerate([True, False]):
ax = axes[idx]
policy_grid = np.zeros((10, 10))
for i, player_sum in enumerate(range(12, 22)):
for j, dealer_showing in enumerate(range(1, 11)):
state = (player_sum, dealer_showing, usable_ace)
if state in policy:
policy_grid[i, j] = policy[state]
else:
policy_grid[i, j] = 0 # デフォルトはスティック
im = ax.imshow(policy_grid, cmap='RdYlBu', interpolation='nearest',
aspect='auto', vmin=0, vmax=1)
ax.set_xlabel('Dealer Showing', fontsize=12)
ax.set_ylabel('Player Sum', fontsize=12)
ax.set_xticks(range(10))
ax.set_xticklabels(range(1, 11))
ax.set_yticks(range(10))
ax.set_yticklabels(range(12, 22))
ace_str = "Usable Ace" if usable_ace else "No Usable Ace"
ax.set_title(f'{ace_str}', fontsize=13)
# 各セルに行動を表示
for i in range(10):
for j in range(10):
action_str = 'H' if policy_grid[i, j] == 1 else 'S'
ax.text(j, i, action_str, ha='center', va='center',
fontsize=9, fontweight='bold',
color='white' if policy_grid[i, j] == 1 else 'black')
# カラーバー
cbar = plt.colorbar(im, ax=axes, ticks=[0, 1])
cbar.set_ticklabels(['Stick (S)', 'Hit (H)'])
plt.suptitle(title, fontsize=15)
plt.tight_layout()
plt.show()
plot_policy(optimal_policy, "MC Control: Optimal Policy for Blackjack")
重点サンプリング（Off-policy MC）
import numpy as np
import matplotlib.pyplot as plt
from collections import defaultdict
# BlackjackEnv は上で定義済みとする
def mc_off_policy_evaluation(env, target_policy, num_episodes=100000, gamma=1.0):
"""
Off-policy MC方策評価: 普通ISと加重ISの両方を計算
行動方策はランダム方策
"""
# 普通IS用
ois_returns_sum = defaultdict(float)
ois_count = defaultdict(int)
# 加重IS用
wis_weighted_sum = defaultdict(float)
wis_weight_sum = defaultdict(float)
for _ in range(num_episodes):
# ランダム方策でエピソード生成
episode = []
state = env.reset()
while True:
action = np.random.choice(env.action_space) # ランダム方策
next_state, reward, done = env.step(action)
episode.append((state, action, reward))
if done:
break
state = next_state
# リターンと重点サンプリング比の計算（逆順）
G = 0
W = 1.0 # 重点サンプリング比
visited = set()
for t in range(len(episode) - 1, -1, -1):
state, action, reward = episode[t]
G = gamma * G + reward
# ターゲット方策の行動確率
target_action = target_policy(state)
pi_a = 1.0 if action == target_action else 0.0
# 行動方策の行動確率（ランダム: 0.5）
b_a = 0.5
W *= pi_a / b_a
if W == 0:
break # ターゲット方策で選ばない行動が含まれていたら打ち切り
if state not in visited:
visited.add(state)
# 普通IS
ois_returns_sum[state] += W * G
ois_count[state] += 1
# 加重IS
wis_weighted_sum[state] += W * G
wis_weight_sum[state] += W
# 推定値の計算
V_ois = {}
V_wis = {}
for state in ois_count:
V_ois[state] = ois_returns_sum[state] / ois_count[state] if ois_count[state] > 0 else 0
for state in wis_weight_sum:
V_wis[state] = wis_weighted_sum[state] / wis_weight_sum[state] if wis_weight_sum[state] > 0 else 0
return V_ois, V_wis
def compare_is_methods(env, target_policy, state, num_runs=100,
episodes_per_run=10000, gamma=1.0):
"""
普通ISと加重ISの推定値のばらつきを比較
"""
ois_estimates = []
wis_estimates = []
for run in range(num_runs):
ois_sum = 0.0
ois_count = 0
wis_weighted_sum = 0.0
wis_weight_sum = 0.0
for _ in range(episodes_per_run):
# ランダム方策でエピソード生成
episode = []
s = env.reset()
while True:
a = np.random.choice(env.action_space)
ns, r, done = env.step(a)
episode.append((s, a, r))
if done:
break
s = ns
# 状態が含まれているか確認
states_in_episode = [e[0] for e in episode]
if state not in states_in_episode:
continue
# 初回訪問のインデックス
t = states_in_episode.index(state)
# リターン計算
G = 0
for k in range(len(episode) - 1, t - 1, -1):
G = gamma * G + episode[k][2]
# 重点サンプリング比
W = 1.0
for k in range(t, len(episode)):
s_k, a_k, _ = episode[k]
target_a = target_policy(s_k)
pi_a = 1.0 if a_k == target_a else 0.0
b_a = 0.5
W *= pi_a / b_a
if W == 0:
break
if W > 0:
ois_sum += W * G
ois_count += 1
wis_weighted_sum += W * G
wis_weight_sum += W
if ois_count > 0:
ois_estimates.append(ois_sum / ois_count)
if wis_weight_sum > 0:
wis_estimates.append(wis_weighted_sum / wis_weight_sum)
return ois_estimates, wis_estimates
# ターゲット方策: 合計20以上ならスティック
def target_policy(state):
player_sum, _, _ = state
return 0 if player_sum >= 20 else 1
# ISの比較実験
env = BlackjackEnv()
state_to_evaluate = (13, 2, False) # 特定の状態で比較
ois_est, wis_est = compare_is_methods(
env, target_policy, state_to_evaluate,
num_runs=200, episodes_per_run=5000
)
# 結果の可視化
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
ax = axes[0]
ax.hist(ois_est, bins=30, alpha=0.7, color='blue', edgecolor='black')
ax.axvline(np.mean(ois_est), color='red', linestyle='--', linewidth=2,
label=f'Mean = {np.mean(ois_est):.3f}')
ax.set_title(f'Ordinary IS\nStd = {np.std(ois_est):.3f}', fontsize=13)
ax.set_xlabel('$\\hat{V}(s)$', fontsize=12)
ax.set_ylabel('Frequency', fontsize=12)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)
ax = axes[1]
ax.hist(wis_est, bins=30, alpha=0.7, color='green', edgecolor='black')
ax.axvline(np.mean(wis_est), color='red', linestyle='--', linewidth=2,
label=f'Mean = {np.mean(wis_est):.3f}')
ax.set_title(f'Weighted IS\nStd = {np.std(wis_est):.3f}', fontsize=13)
ax.set_xlabel('$\\hat{V}(s)$', fontsize=12)
ax.set_ylabel('Frequency', fontsize=12)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)
plt.suptitle(f'Ordinary IS vs Weighted IS (state = {state_to_evaluate})', fontsize=15)
plt.tight_layout()
plt.show()
print(f"普通IS - 平均: {np.mean(ois_est):.4f}, 標準偏差: {np.std(ois_est):.4f}")
print(f"加重IS - 平均: {np.mean(wis_est):.4f}, 標準偏差: {np.std(wis_est):.4f}")
このコードにより、以下のことが確認できます。
- MC方策評価により、ブラックジャックの状態価値関数を3Dサーフェスとして可視化できる
- MC制御により、プレイヤーの合計値とディーラーの見せカードに基づく最適方策（ヒット/スティック）が学習される
- 普通ISと加重ISでは、加重ISの方が分散が小さく安定した推定値を返すことがヒストグラムで確認できる
まとめ
本記事では、モンテカルロ法による強化学習について解説しました。
- MC法はモデルフリーの手法であり、エピソードの経験データから価値関数を推定する
- 初回訪問MCは不偏推定量であり、大数の法則により一致推定量でもある
- $\varepsilon$-greedy方策により探索を保証しつつ、MC制御で最適方策を学習できる
- 重点サンプリングにより方策オフ型の評価が可能であり、加重ISは普通ISより分散が小さい
- MC法はエピソード完了後にのみ更新できるという制約があり、ステップごとに学習するTD学習が次のステップとなる
次のステップとして、以下の記事も参考にしてください。