モンテカルロ法の強化学習

前回の記事では、強化学習の基礎的な枠組みであるマルコフ決定過程(MDP)、価値関数、ベルマン方程式について学びました。そこでの実装例では、環境のモデル（状態遷移確率$P$と報酬関数$R$）が既知という前提で、ベルマン方程式を使った価値関数の計算を行いました。

現実世界の多くの問題では、環境の完全なモデルを事前に知ることはできません。この制約を克服するために開発されたのがモデルフリー学習であり、その第一歩がモンテカルロ法;Monte Carlo methodです。

環境モデルとモデルフリー学習

環境モデルとは何か

前回の記事で使用したベルマン方程式の計算例では、以下の情報が既知でした：

• 状態遷移確率$P(s'|s,a)$：状態$s$で行動$a$を取った時に状態$s'$に遷移する確率
• 報酬関数$R(s,a,s')$：各遷移で得られる報酬

これらを総称して環境モデルと呼びます。モデルがあれば、実際に行動することなく「もし〜したら〜になる」というシミュレーションが可能です。

現実世界でのモデルの困難さ

しかし、現実の多くの問題では、このようなモデルを正確に知ることは困難、または不可能です：

例1：ロボットの歩行学習

• 関節の摩擦、センサーノイズ、地面の状況など無数の要因
• 物理シミュレーションはあっても、現実との差（Reality Gap）が存在
• 製造個体差や経年劣化による特性変化

例2：金融市場での投資判断

• 市場参加者の心理、政治情勢、天候など予測困難な要因
• 過去のデータから未来を完全に予測することは不可能
• 自分の行動自体が市場に影響を与える（相場操縦リスク）

例3：ゲームAIの対戦相手

• 人間の戦略や癖は千差万別
• 学習によって相手も成長・変化する
• 心理戦や意外性も重要な要素

プランニング vs 学習

強化学習の文脈では、以下の3つの問題設定を区別することが重要です：

プランニング（Planning）

• 環境モデル$P$と$R$が完全に既知
• 最適方策を計算で求める問題
• 例：価値反復法、方策反復法（前回記事）
• 「学習」は必要なく、純粋な計算問題

モデルベース学習（Model-based Learning）

• 環境モデルの構造は既知だが、パラメータは未知
• 経験からモデルのパラメータを推定し、それを使って方策を計算
• 例：未知の遷移確率を推定してから価値反復を実行
• モデル学習と方策計算の2段階アプローチ

モデルフリー学習（Model-free Learning）

• 環境モデルを一切仮定しない
• 経験から直接、価値関数や方策を学習
• 例：モンテカルロ法、Q学習、方策勾配法
• モデルを介さず、経験から直接最適行動を学ぶ

モデルベース学習とモデルフリー学習の詳細

モデルベース学習の特徴

• 利点：
  • サンプル効率が良い（少ない経験で学習可能）
  • 学習したモデルで将来の計画立案が可能
  • 環境の変化に柔軟に対応できる
• 欠点：
  • モデルの誤差が方策の性能に直接影響
  • 複雑な環境ではモデル化自体が困難
  • 計算量が多い（モデル学習＋方策計算）

モデルフリー学習の特徴

• 利点：
  • 複雑な環境でも適用可能
  • モデル化の誤差を考慮する必要がない
  • 実装がシンプル
• 欠点：
  • 多くの経験（サンプル）が必要
  • 環境が変化すると再学習が必要
  • 将来の予測や計画立案には不向き

モデルフリー学習の基本戦略

モデルフリー学習では、環境のモデルを知る代わりに「実際に行動して結果を見る」ことで学習します：

1. 行動を実行：現在の方策に従って行動を選択
2. 結果を観測：得られた報酬と次の状態を記録
3. 経験から学習：蓄積した経験データから価値関数や方策を改善
4. 繰り返し：改善した方策で再び行動

この「経験から学ぶ」アプローチの最初の重要な手法がモンテカルロ法です。

モンテカルロ法の基本的なアイデア

モンテカルロ法の核心は驚くほどシンプルです：実際に経験したエピソードから価値を推定する。

人間の学習過程を考えてみましょう：

• 新しいレストランの評価：実際に行ってみて満足度を記憶する
• 通勤ルートの選択：何度か試してみて、平均的な所要時間を把握する
• 投資戦略の評価：実際の運用結果から期待リターンを推定する

モンテカルロ法は、この「経験から学ぶ」プロセスを数学的に定式化したものです。

ベルマン方程式による計算との違い

前回使用したベルマン方程式による直接計算とモンテカルロ法の違いを整理しましょう：

ベルマン方程式による直接計算（モデルベース）

• 環境モデル$P$と$R$が既知
• ベルマン方程式を使って価値を計算
• 1ステップ先の情報から価値を更新
• 数学的に厳密な解が得られる

モンテカルロ法（モデルフリー）

• 環境モデルが未知でも学習可能
• エピソード全体の経験から学習
• 実際の累積報酬から価値を推定
• サンプリングに基づく近似

モンテカルロ法の数学的定式化

エピソードと軌道の関係

モンテカルロ法を理解するために、まずエピソードという概念を明確にしましょう。

前回の記事では軌道（trajectory） を以下のように定義しました：

$$\tau = s_0, a_0, s_1, a_1, s_2, a_2, \ldots$$

軌道は状態と行動の系列でしたが、エピソードはより具体的で実践的な概念です。

定義：エピソード（Episode）

エピソード$\mathcal{E}$は、終端状態で必ず終了する軌道の一種：

$$\mathcal{E} = (s_0, a_0, r_1, s_1, a_1, r_2, ..., s_{T-1}, a_{T-1}, r_T, s_T)$$

ここで$s_T$は終端状態、$T$はエピソードの長さ（有限）。

軌道との違い：

• 軌道：理論的概念、無限に続く可能性がある
• エピソード：実践的概念、必ず有限時間で終了し、報酬も含む

強化学習タスクの分類

強化学習では、解決したい問題のことをタスク（Task） と呼びます。タスクとは、エージェントが環境の中で達成すべき目標を含む問題設定全体を指します。

強化学習のタスクは、終了の有無により2種類に分類されます：

エピソード的タスク（Episodic Tasks）

• 明確な終了条件がある問題
• 必ず終端状態に到達して一区切りとなる
• モンテカルロ法が直接適用可能
• 例：
  • チェス・囲碁：勝敗が決まったら終了
  • 迷路探索：ゴールに到達したら終了
  • 1日の株式取引：市場が閉まったら終了
  • ゲームの1ラウンド：スコアが確定したら終了

継続的タスク（Continuing Tasks）

• 明確な終了条件がない問題
• 理論上は無限に続く
• 例：
  • ロボットの歩行制御：常に歩き続ける
  • 温度調節システム：24時間365日動作
  • Webサーバーの負荷分散：サービス停止まで継続

モンテカルロ法はエピソード的タスクを前提とした手法です。これは、エピソード全体を経験してから累積報酬を計算する必要があるためです。継続的タスクには、後で学ぶTD法などの手法が適用されます。

価値推定の基本原理

前回の記事で、状態価値関数を以下のように定義しました：

$$V^{\pi}(s) = \mathbb{E}_{\pi}\left[G_t \mid s_t = s\right]$$

ここで$G_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}$は割引累積報酬です。

モンテカルロ法の基本的なアイデアは、この期待値を経験的平均で近似することです：

モンテカルロ推定の原理

状態$s$について、多数のエピソードを経験し、状態$s$を実際に訪問した回数を$N_s$回とする。これらの訪問で得られた累積報酬を$G_{t^{(1)}}|_{s_{t^{(1)}} = s}, G_{t^{(2)}}|_{s_{t^{(2)}} = s}, ..., G_{t^{(N_s)}}|_{s_{t^{(N_s)}} = s}$とすると：

$$V^{\pi}(s) \approx \frac{1}{N_s} \sum_{i=1}^{N_s} G_{t^{(i)}}|_{s_{t^{(i)}} = s}$$

ここで$G_{t^{(i)}}|_{s_{t^{(i)}} = s}$は$i$番目の訪問における時刻$t^{(i)}$から計算されたリターン（ただし$s_{t^{(i)}} = s$）：

$$G_{t^{(i)}}|_{s_{t^{(i)}} = s} = r_{t^{(i)}+1} + \gamma r_{t^{(i)}+2} + \gamma^2 r_{t^{(i)}+3} + ... + \gamma^{T^{(i)}-t^{(i)}-1} r_{T^{(i)}}$$

ここで$T^{(i)}$は該当エピソードの終了時刻。

重要な注意：

• 状態$s$を訪問しないエピソードは計算に含まれない
• $N_s$は総エピソード数ではなく、状態$s$の訪問回数

大数の法則により、$N_s \to \infty$で真の価値に収束する。

First-visit MC vs Every-visit MC

同じ状態が1つのエピソード中に複数回出現する場合、どのように扱うべきでしょうか？この問題を具体例で説明しましょう。

具体例：状態の重複訪問

以下のようなエピソードを考えます（報酬は各遷移で-1、γ=0.9）：

時刻   状態   行動   報酬   累積報酬G_t
 0     σ1    a1     -1     G_0 = -1 + 0.9×(-1) + 0.9²×(-1) + 0.9³×(+10) = 5.369
 1     σ2    a2     -1     G_1 = -1 + 0.9×(-1) + 0.9²×(+10) = 6.1  
 2     σ1    a3     -1     G_2 = -1 + 0.9×(+10) = 8.0
 3     σ4   (終了)  +10    G_3 = +10

この例では、状態$\sigma_1$が時刻0と時刻2の2回出現しています。

First-visit Monte Carlo

同じ状態が複数回出現する場合、統計的な独立性を保つために最初の訪問のみを使用する手法です。

定義：First-visit MC

各エピソードにおいて、状態$s$が最初に出現した時点からのリターンのみを価値推定に使用する方法。

上記例での計算：

• 状態$\sigma_1$：最初の出現（時刻0）のみを使用 → $G_0|_{s_0 = \sigma_1} = 5.369$
• 状態$\sigma_2$：時刻1で1回のみ出現 → $G_1|_{s_1 = \sigma_2} = 6.1$
• 状態$\sigma_4$：時刻3で1回のみ出現 → $G_3|_{s_3 = \sigma_4} = 10$

Every-visit Monte Carlo

同じ状態が複数回出現する場合、データを最大限活用するためにすべての訪問を使用する手法です。

定義：Every-visit MC

各エピソードにおいて、状態$s$が出現するすべての時点からのリターンを価値推定に使用する方法。

上記例での計算：

• 状態$\sigma_1$：両方の出現を使用 → $G_0|_{s_0 = \sigma_1} = 5.369$と$G_2|_{s_2 = \sigma_1} = 8.0$
• 状態$\sigma_2$：時刻1で1回のみ出現 → $G_1|_{s_1 = \sigma_2} = 6.1$
• 状態$\sigma_4$：時刻3で1回のみ出現 → $G_3|_{s_3 = \sigma_4} = 10$

両手法の比較と使い分け

First-visit MCとEvery-visit MCの特徴を様々な観点から比較してみましょう。

項目	First-visit MC	Every-visit MC
サンプル数	各エピソードから最大1つ	すべての訪問を使用
理論的性質	統計的独立性が保証	漸近的に同じ値に収束
分散	小さい傾向	やや大きい傾向
学習速度	状態によっては遅い	より安定した学習
実装	訪問チェックが必要	シンプル
メモリ効率	良い	やや劣る
適用場面	理論的厳密性重視	実用性重視

実際の選択指針

First-visit MCは理論研究や厳密な分析に適しています。統計的独立性が保証され、メモリ効率も良好です。一方、Every-visit MCは実用的な問題解決に向いており、より多くのデータを活用できるため学習効率が高く、実装もシンプルです。

実際のプロジェクトではEvery-visit MCから始めることをお勧めします。実装が簡単で、多くの問題で十分な性能を発揮するからです。理論的な分析が必要になった場合のみ、First-visit MCを検討すれば良いでしょう。

方策評価のモンテカルロ法

まず、与えられた方策$\pi$の価値関数を推定する方法を見ていきます。

方策評価の基本アルゴリズム

方策評価のモンテカルロ法は以下の手順で進行します：

1. 方策$\pi$に従ってエピソードを生成：環境で実際に行動し、一連の$(状態, 行動, 報酬)$を記録
2. 各状態のリターン$G_t$を計算：エピソード終了から逆算して累積報酬を求める
3. 価値関数を更新：そのエピソードで得られたリターンを使って状態価値の推定値を改善
4. 収束まで繰り返し：十分多くのエピソードを経験することで真の価値関数$V^\pi(s)$に近づく

重要な点は、環境のモデル（遷移確率$P$や報酬関数$R$）を知らなくても、実際の経験だけから価値を推定できることです。

Pythonによる実装

import numpy as np
from collections import defaultdict
from typing import List, Tuple, Dict

class MonteCarloEvaluation:
    """モンテカルロ法による方策評価"""
    
    def __init__(self, env, gamma=0.9):
        self.env = env
        self.gamma = gamma
        self.value_estimates = defaultdict(float)
        self.returns = defaultdict(list)
        
    def generate_episode(self, policy) -> List[Tuple]:
        """方策に従ってエピソードを生成"""
        episode = []
        state = self.env.reset()
        
        while True:
            action = policy(state)
            next_state, reward, done = self.env.step(state, action)
            episode.append((state, action, reward))
            
            if done:
                break
            state = next_state
            
        return episode
    
    def calculate_returns(self, episode: List[Tuple]) -> Dict:
        """エピソードから各状態のリターンを計算"""
        returns = {}
        G = 0
        
        # 後ろから遡って累積報酬を計算
        for t in reversed(range(len(episode))):
            state, action, reward = episode[t]
            G = reward + self.gamma * G
            
            # First-visit: 最初の訪問のみ記録
            if state not in returns:
                returns[state] = G
                
        return returns
    
    def evaluate_policy(self, policy, num_episodes=10000):
        """方策の価値関数を推定"""
        for _ in range(num_episodes):
            # エピソード生成
            episode = self.generate_episode(policy)
            
            # リターン計算
            returns = self.calculate_returns(episode)
            
            # リターンを記録
            for state, G in returns.items():
                self.returns[state].append(G)
        
        # 平均を計算して価値関数を更新
        for state, return_list in self.returns.items():
            self.value_estimates[state] = np.mean(return_list)
            
        return self.value_estimates

コードの解説

1. generate_episodeメソッド：与えられた方策に従って1つのエピソードを生成します。done=Trueになるまで行動を続け、(状態, 行動, 報酬)の組を記録します。

2. calculate_returnsメソッド：生成されたエピソードから各状態のリターン$G_t$を計算します。エピソードの最後から逆算して累積報酬を求め、First-visit MCに従って各状態で最初に訪問した時のリターンのみを記録します。

3. evaluate_policyメソッド：指定された回数だけエピソードを生成し、各状態のリターンを蓄積します。最後に各状態について、蓄積されたリターンの平均を計算して価値関数の推定値とします。

オンライン更新による効率化

上記の実装では、すべてのエピソードを収集してから平均を計算していますが、メモリ効率が悪くなります。オンライン更新により、逐次的に平均を更新できます：

def evaluate_policy_online(self, policy, num_episodes=10000):
    """オンライン更新による方策評価"""
    state_counts = defaultdict(int)
    
    for episode_num in range(num_episodes):
        episode = self.generate_episode(policy)
        returns = self.calculate_returns(episode)
        
        for state, G in returns.items():
            state_counts[state] += 1
            # インクリメンタル平均の更新
            self.value_estimates[state] += (
                G - self.value_estimates[state]
            ) / state_counts[state]
    
    return self.value_estimates

オンライン更新の利点

オンライン更新では、新しいリターン$G$が得られるたびに即座に価値関数を更新します：

$$V_{n+1}(s) = V_n(s) + \frac{1}{n+1}[G_n - V_n(s)]$$

この方式の利点は：

• メモリ効率：過去のリターンをすべて保存する必要がない
• リアルタイム学習：各エピソード後に即座に推定値が改善される
• 数値安定性：非常に大きな数値の計算を避けられる

ここで$V_n(s)$は$n$回の訪問後の推定値、$G_n$は$n+1$回目の訪問で得られたリターンです。

方策評価から方策制御へ

これまでは方策評価、つまり固定された方策$\pi$に対してその価値関数$V^\pi(s)$を推定する方法を学びました。しかし、強化学習の真の目的は最適方策を見つけることです。

方策制御の必要性

方策評価では「この方策はどれくらい良いか？」という質問に答えていました。しかし、私たちが本当に知りたいのは「どうやったら最も良い方策を見つけられるか？」です。

これが方策制御;Policy Controlの問題です：

• 方策評価：与えられた方策$\pi$の価値$V^\pi(s)$を求める
• 方策制御：最適方策$\pi^*$そのものを見つける

モンテカルロ法による方策制御

モンテカルロ法でも、前回の記事で学んだベルマン方程式の理論を活用できます。基本的なアイデアは：

1. 現在の方策を評価：モンテカルロ法で$Q^\pi(s,a)$を推定
2. 方策を改善：推定した$Q$値に基づいてより良い方策に更新
3. 繰り返し：改善された方策で再び評価・改善を実行

この「評価→改善」のサイクルを繰り返すことで、最適方策に近づいていきます。

方策オン型 vs 方策オフ型

方策制御には大きく2つのアプローチがあります。この違いを理解するため、まず核心的な違いを見てみましょう。

核心的な違い：「学習する方策」と「行動する方策」の関係

方策制御では常に2つの方策が存在します：

• 学習対象の方策：最終的に得たい、改善していきたい方策
• 行動方策：実際に環境で行動を決める際に使う方策

この2つの方策が同じか異なるかによって、アプローチが分かれます。

方策オン型;On-policyでは、学習対象の方策と行動方策が同一です。つまり「改善したい方策そのもので行動して、その経験から学習する」というアプローチです。人間で例えると、新しい料理を作りながら同時にその手順を覚えていく感じです。

方策オフ型;Off-policyでは、学習対象の方策と行動方策が異なります。「ある方策で行動して得た経験から、別の方策について学習する」アプローチです。人間で例えると、他の人の料理を見て（行動方策）、自分の料理手順（学習対象）を改善する感じです。

この基本的な違いから、以下のような特徴の差が生まれます：

観点	方策オン型	方策オフ型
方策の関係	学習対象 = 行動方策	学習対象 ≠ 行動方策
学習の進行	改善しながら同時に行動	行動とは独立して学習可能
データの活用	現在の方策の経験のみ	過去や他の方策の経験も活用
実装の複雑さ	シンプルで直感的	より柔軟だが複雑
探索の制約	学習中も探索が必要	行動方策で自由に探索可能
データ効率	方策変更で過去データ無効	過去データを再利用可能
代表的手法	SARSA、方策勾配法	Q学習、重要度サンプリング

まずは理解しやすい方策オン型から始めましょう。方策オン型モンテカルロ法では、現在の方策に従って行動しながら、その方策を改善していきます。

方策オン型モンテカルロ法

探索と活用のジレンマ

最適方策を学習する際の根本的な課題は探索と活用のトレードオフです：

• 活用(Exploitation)：現在の知識で最良と思われる行動を選択
• 探索(Exploration)：まだ試していない行動を試して新しい知識を獲得

この問題を具体的に考えてみましょう。

活用のみの問題点
現在知っている最良の行動ばかり選択すると：

• 実はもっと良い行動があっても発見できない
• 局所最適解に陥る可能性がある
• 環境が変化した時に対応できない

例えば、レストラン選びで「いつものお気に入りの店」だけに行き続けると、もっと美味しい新しい店を見つける機会を失います。

探索のみの問題点
ランダムに行動ばかりすると：

• せっかく見つけた良い行動を活用できない
• 学習効率が悪くなる
• 実用的な性能が出ない

レストラン選びで毎回ランダムに店を選んでいては、美味しいと分かっている店の価値を活かせません。

現実世界での重要性
この探索・活用のバランスは強化学習の成否を左右します：

• 医療診断：新しい治療法を試すか、確実な治療法を選ぶか
• 金融投資：新しい投資先を探すか、安定した投資を続けるか
• ロボット制御：新しい動作を学習するか、安全な動作を維持するか

ε-グリーディ方策

このジレンマを解決する最も単純で効果的な方法がε-グリーディ方策です。

基本的なアイデア
ε-グリーディ方策は確率的に探索と活用を切り替えます：

• 確率$\varepsilon$（小さな値、例：0.1）で探索：ランダムに行動選択
• 確率$1-\varepsilon$（大きな値、例：0.9）で活用：現在のQ値が最大の行動を選択

これにより、ほとんどの時間は良いと分かっている行動を選びつつ、時々新しい行動も試すことができます。

定義：ε-グリーディ方策

確率$\varepsilon$でランダムな行動を選択し、確率$1-\varepsilon$で現在の価値関数に基づく最良の行動を選択する方策：

$$\pi(a|s) = \begin{cases} 1 - \varepsilon + \frac{\varepsilon}{|A|} & \text{if } a = \arg\max_{a'} Q(s,a') \\ \frac{\varepsilon}{|A|} & \text{otherwise} \end{cases}$$

ここで$|A|$は行動数。

数式の解釈

• 最良の行動：$Q$値が最大の行動は基本確率$(1-\varepsilon)$に加えて、ランダム選択の確率$\frac{\varepsilon}{|A|}$も持つため、合計で$1 - \varepsilon + \frac{\varepsilon}{|A|}$の確率で選ばれる
• その他の行動：各々がランダム選択として$\frac{\varepsilon}{|A|}$の確率で選ばれる
• 全体の確率和：$(1 - \varepsilon + \frac{\varepsilon}{|A|}) + (|A|-1) \times \frac{\varepsilon}{|A|} = 1$となり、正しい確率分布

εの値による挙動の変化

• $\varepsilon = 0$：完全な活用（貪欲方策）、探索なし
• $\varepsilon = 1$：完全なランダム選択、活用なし
• $\varepsilon = 0.1$（典型的）：90%の時間は最良行動、10%の時間は探索

ε値の選択指針

• 学習初期：大きめの$\varepsilon$（例：0.3）で積極的に探索
• 学習後期：小さめの$\varepsilon$（例：0.05）で主に活用
• 実運用時：$\varepsilon = 0$または非常に小さい値で安定動作

実際の実装では、時間と共に$\varepsilon$を減少させるε減衰がよく使われます。

方策改善の理論

方策オン型MCでは、以下のステップを繰り返します：

1. 方策評価：現在の方策$\pi$に従ってエピソードを生成し、$Q^{\pi}(s,a)$を推定
2. 方策改善：推定した$Q$値に基づいて方策を改善

なぜ方策評価だけでは不十分なのか
方策評価では固定された方策の価値を求めていましたが、私たちの目標は「最適方策を見つける」ことです。そのためには：

• 現在の方策がどれくらい良いかを知る（方策評価）
• その情報を使ってより良い方策に変更する（方策改善）

この2つを交互に繰り返すことで、最適方策に収束していきます。

方策改善の数学的保証
重要な性質として、$Q$値に基づくグリーディ方策は元の方策を改善することが保証されています^[1]。具体的には：

$$\pi'(s) = \arg\max_a Q^\pi(s,a)$$

このようにして得られた新しい方策$\pi'$は、元の方策$\pi$と同じかそれ以上の性能を持ちます：

$$V^{\pi'}(s) \geq V^{\pi}(s) \quad \forall s$$

実装：方策オン型モンテカルロ制御

以下は方策オン型モンテカルロ制御の完全な実装です：

class OnPolicyMonteCarloControl:
    """ε-グリーディ方策による方策オン型モンテカルロ制御"""
    
    def __init__(self, env, gamma=0.9, epsilon=0.1):
        self.env = env
        self.gamma = gamma
        self.epsilon = epsilon
        
        # Q関数の初期化
        self.Q = defaultdict(lambda: defaultdict(float))
        self.returns = defaultdict(lambda: defaultdict(list))
        
    def epsilon_greedy_policy(self, state):
        """ε-グリーディ方策による行動選択"""
        if np.random.random() < self.epsilon:
            # 探索：ランダムな行動
            return np.random.choice(self.env.get_actions(state))
        else:
            # 活用：Q値が最大の行動
            q_values = self.Q[state]
            if not q_values:
                # まだ訪問していない状態の場合
                return np.random.choice(self.env.get_actions(state))
            
            max_q = max(q_values.values())
            # 複数の最大値がある場合はランダムに選択
            best_actions = [a for a, q in q_values.items() if q == max_q]
            return np.random.choice(best_actions)
    
    def generate_episode(self):
        """現在の方策でエピソードを生成"""
        episode = []
        state = self.env.reset()
        
        while True:
            action = self.epsilon_greedy_policy(state)
            next_state, reward, done = self.env.step(state, action)
            episode.append((state, action, reward))
            
            if done:
                break
            state = next_state
            
        return episode
    
    def update_q_values(self, episode):
        """エピソードからQ値を更新（First-visit MC）"""
        visited = set()
        G = 0
        
        # 後ろから遡ってリターンを計算
        for t in reversed(range(len(episode))):
            state, action, reward = episode[t]
            G = reward + self.gamma * G
            
            # First-visit: 最初の訪問のみ更新
            if (state, action) not in visited:
                visited.add((state, action))
                self.returns[state][action].append(G)
                # Q値を平均で更新
                self.Q[state][action] = np.mean(self.returns[state][action])
    
    def learn(self, num_episodes=10000, verbose=False):
        """方策オン型モンテカルロ制御のメインループ"""
        episode_rewards = []
        
        for episode_num in range(num_episodes):
            # エピソード生成
            episode = self.generate_episode()
            
            # Q値更新
            self.update_q_values(episode)
            
            # エピソードの総報酬を記録
            total_reward = sum(reward for _, _, reward in episode)
            episode_rewards.append(total_reward)
            
            if verbose and episode_num % 1000 == 0:
                avg_reward = np.mean(episode_rewards[-100:])
                print(f"Episode {episode_num}: Average reward = {avg_reward:.2f}")
        
        return self.Q, episode_rewards

コードの詳細解説

1. クラス初期化 (__init__)

self.Q = defaultdict(lambda: defaultdict(float))
self.returns = defaultdict(lambda: defaultdict(list))

• Q関数：状態-行動ペア$(s,a)$の価値を記録。未訪問のペアは自動的に0.0で初期化
• returns：各状態-行動ペアで経験したリターンのリストを保存。平均計算に使用

2. ε-グリーディ方策 (epsilon_greedy_policy)

このメソッドが方策オン型の核心部分です：

if np.random.random() < self.epsilon:
    # 探索：ランダムな行動
    return np.random.choice(self.env.get_actions(state))
else:
    # 活用：Q値が最大の行動

探索と活用の実際の動作：

• 確率εで完全にランダムな行動（探索）
• 確率(1-ε)で現在のQ値が最大の行動（活用）
• 複数の行動が同じ最大Q値を持つ場合はその中からランダム選択

未訪問状態の処理：

if not q_values:
    return np.random.choice(self.env.get_actions(state))

初めて訪問する状態では、Q値がまだ存在しないためランダムに行動を選択します。

3. エピソード生成 (generate_episode)

while True:
    action = self.epsilon_greedy_policy(state)
    next_state, reward, done = self.env.step(state, action)
    episode.append((state, action, reward))

重要なポイント：

• 方策オン型の特徴：学習したい方策（ε-グリーディ）で実際に行動
• 経験の蓄積：$(s_t, a_t, r_{t+1})$の組を記録
• 終了条件：done=Trueになるまで継続

4. Q値更新 (update_q_values)

モンテカルロ法の本質的な部分：

# 後ろから遡ってリターンを計算
for t in reversed(range(len(episode))):
    state, action, reward = episode[t]
    G = reward + self.gamma * G

リターン計算の仕組み：

• エピソードの最後（終端）から逆算
• $G_t = r_{t+1} + \gamma G_{t+1}$の再帰関係を利用
• 各時刻のリターン$G_t$を正確に計算

First-visit MCの実装：

if (state, action) not in visited:
    visited.add((state, action))
    self.returns[state][action].append(G)
    self.Q[state][action] = np.mean(self.returns[state][action])

• 各エピソードで状態-行動ペアの最初の訪問のみ更新
• リターンを蓄積して平均を計算
• Q値 = そのペアで経験したリターンの平均値

5. 学習ループ (learn)

方策オン型の「評価→改善」サイクル：

for episode_num in range(num_episodes):
    episode = self.generate_episode()  # 現在の方策で行動（評価）
    self.update_q_values(episode)      # Q値更新（暗黙的に方策改善）

暗黙的な方策改善：

• Q値が更新されると、次回のepsilon_greedy_policyでの行動選択が自動的に改善される
• 明示的に方策を変更する必要がない
• Q値の改善 → より良い行動選択 → より良いエピソード → さらなるQ値改善

実装の改善アイデア

基本実装では全てのリターンを保存して平均を計算していますが、実用的な改善が可能です：

インクリメンタル更新
過去のリターンを保存せず、オンラインで平均を更新：

• 更新式：$Q_{n+1}(s,a) = Q_n(s,a) + \frac{1}{n+1}[G - Q_n(s,a)]$
• メモリ効率とリアルタイム学習が可能
• 大規模問題や連続学習に適している

探索戦略の改善
固定εではなく、学習進行に応じて探索量を調整：

• ε減衰：$\varepsilon_t = \max(\varepsilon_{min}, \varepsilon_0 \cdot \alpha^t)$
• 学習初期は積極探索、後期は活用重視
• 最終的に決定的な最適方策に収束

方策オフ型モンテカルロ法

方策オン型では、評価したい方策と実際に行動する方策が同じでした。しかし、これには制限があります：

• 最適な（決定的な）方策を学習したい場合でも、探索のために確率的な行動が必要
• 他のエージェントや人間の行動データから学習することができない

方策オフ型;Off-policy学習では、行動を生成する方策（行動方策）と、評価・改善したい方策（目標方策）を分離します。

行動方策と目標方策

定義：行動方策と目標方策

• 行動方策(Behavior Policy) $b(a|s)$：実際に環境で行動を選択する方策
• 目標方策(Target Policy) $\pi(a|s)$：学習・評価したい方策

方策オフ型学習では、$b$に従って生成されたデータから$\pi$の価値を推定する。

なぜ方策オフ型が重要なのか

1. 最適な決定的方策の学習：探索は行動方策$b$に任せ、目標方策$\pi$は純粋に最適性を追求できる
2. 既存データの活用：過去の経験や他のエージェントのデータから学習可能
3. 安全な学習：危険な行動を含む方策を、実際に実行せずに評価できる

方策が異なる場合の課題

方策オフ型学習の核心的な課題は、「ある方策で生成したデータから、別の方策の価値をどう推定するか」です。

問題の具体例

• 行動方策$b$：ε-グリーディ方策（探索のためランダム行動を含む）
• 目標方策$\pi$：決定的な最適方策（常に最良の行動を選択）

行動方策$b$で経験したリターンを、そのまま目標方策$\pi$の価値として使うことはできません。なぜなら：

• $b$は探索のため時々悪い行動を選ぶ
• $\pi$は常に最良の行動を選ぶはず
• 同じ状態でも選ぶ行動が異なるため、得られるリターンも異なる

重要度サンプリング

この問題を解決するのが重要度サンプリング;Importance Samplingです。これは確率論の手法で、ある分布で生成したサンプルを使って、別の分布の期待値を推定します。

基本的なアイデア
「もし目標方策$\pi$で行動していたら、このエピソードがどれくらいの確率で発生したか」を考慮して、リターンに重み付けをします：

• 目標方策$\pi$でも起こりやすいエピソード → 重みを大きく
• 目標方策$\pi$では起こりにくいエピソード → 重みを小さく

この重み付けにより、行動方策$b$のデータから目標方策$\pi$の価値を正しく推定できます。

数学的基礎
重要度サンプリングの一般原理は、分布$p$での期待値を分布$q$でのサンプルから計算することです：

$$\mathbb{E}_p[V(X)] = \sum_x p(x)V(x) = \sum_x q(x) \frac{p(x)}{q(x)} V(x) = \mathbb{E}_q\left[\frac{p(X)}{q(X)}V(X)\right]$$

強化学習の文脈では：

• $p$：目標方策$\pi$でのエピソード分布
• $q$：行動方策$b$でのエピソード分布
• $V(X)$：エピソードのリターン$G(\tau)$
• $\frac{p(X)}{q(X)}$：重要度比

つまり、目標方策$\pi$での期待リターンを、行動方策$b$で生成したエピソードから推定できます：

$$\mathbb{E}_\pi[G(\tau)] = \mathbb{E}_b\left[\frac{P_\pi(\tau)}{P_b(\tau)}G(\tau)\right]$$

重要度サンプリングの原理

あるエピソード$\tau = (s_0, a_0, s_1, a_1, ..., s_T)$が生成される確率は：

• 行動方策$b$の下で：$P_b(\tau) = \prod_{t=0}^{T-1} b(a_t|s_t) P(s_{t+1}|s_t,a_t)$
• 目標方策$\pi$の下で：$P_\pi(\tau) = \prod_{t=0}^{T-1} \pi(a_t|s_t) P(s_{t+1}|s_t,a_t)$

重要度比$\rho$は：

$$\rho(\tau) = \frac{P_\pi(\tau)}{P_b(\tau)} = \prod_{t=0}^{T-1} \frac{\pi(a_t|s_t)}{b(a_t|s_t)}$$

状態遷移確率$P$が約分されることに注目。

方策オフ型価値推定

重要度比を使って、目標方策の価値を推定できます：

通常の重要度サンプリング（Ordinary Importance Sampling）

$$V^{\pi}(s) \approx \frac{\sum_{i \in \mathcal{T}(s)} \rho_i G_i}{|\mathcal{T}(s)|}$$

重み付き重要度サンプリング（Weighted Importance Sampling）

$$V^{\pi}(s) \approx \frac{\sum_{i \in \mathcal{T}(s)} \rho_i G_i}{\sum_{i \in \mathcal{T}(s)} \rho_i}$$

ここで$\mathcal{T}(s)$は状態$s$を訪問したエピソードの集合、$\rho_i$と$G_i$はそれぞれ$i$番目のエピソードの重要度比とリターン。

なぜWeighted Importance Samplingが必要か？

通常の重要度サンプリングは理論的には正しいですが、実用上の問題があります：

1. 高分散問題：重要度比$\rho$が非常に大きくなることがある

   • 例：行動方策が確率0.1で選んだ行動を、目標方策が確率1.0で選ぶ場合、$\rho = 10$
   • エピソードが長いと積の形で$\rho = \prod_t \frac{\pi(a_t|s_t)}{b(a_t|s_t)}$となり、指数的に増大

2. 極端な値の影響：一つの大きな$\rho$を持つサンプルが平均を支配してしまうことがある

重み付き重要度サンプリングは、重要度比で正規化することで以下のようなメリットがあります。：

• 分散を大幅に削減：極端な重みの影響を抑制
• バイアスとのトレードオフ：わずかなバイアスと引き換えに、実用的な分散を実現
• 数値的安定性：$\sum \rho_i = 0$に近い場合でも安定

実際、多くの実装で重み付き重要度サンプリングが標準的に使われています。

実装：方策オフ型モンテカルロ評価

class OffPolicyMonteCarloEvaluation:
    """重要度サンプリングによる方策オフ型評価"""
    
    def __init__(self, env, target_policy, behavior_policy, gamma=0.9):
        self.env = env
        self.target_policy = target_policy
        self.behavior_policy = behavior_policy
        self.gamma = gamma
        
        # 重み付き重要度サンプリング用
        self.C = defaultdict(float)  # 累積重要度比
        self.Q = defaultdict(lambda: defaultdict(float))
        
    def generate_episode(self):
        """行動方策でエピソードを生成"""
        episode = []
        state = self.env.reset()
        
        while True:
            action = self.behavior_policy(state)
            next_state, reward, done = self.env.step(state, action)
            episode.append((state, action, reward))
            
            if done:
                break
            state = next_state
            
        return episode
    
    def calculate_importance_ratio(self, episode):
        """エピソードの重要度比を計算"""
        rho = 1.0
        
        for state, action, _ in episode:
            # 目標方策と行動方策の確率を取得
            pi_prob = self.target_policy.get_probability(state, action)
            b_prob = self.behavior_policy.get_probability(state, action)
            
            # ゼロ除算を避ける
            if b_prob == 0:
                return 0.0
            
            rho *= pi_prob / b_prob
            
            # 目標方策で確率0の行動が取られた場合
            if pi_prob == 0:
                return 0.0
                
        return rho
    
    def evaluate_policy_weighted(self, num_episodes=10000):
        """重み付き重要度サンプリングによる評価"""
        
        for _ in range(num_episodes):
            episode = self.generate_episode()
            G = 0
            W = 1  # 重要度比の累積
            
            # 後ろから処理
            for t in reversed(range(len(episode))):
                state, action, reward = episode[t]
                G = reward + self.gamma * G
                
                # 重み付き更新
                self.C[state][action] += W
                self.Q[state][action] += (W / self.C[state][action]) * (
                    G - self.Q[state][action]
                )
                
                # 重要度比の更新
                pi_prob = self.target_policy.get_probability(state, action)
                b_prob = self.behavior_policy.get_probability(state, action)
                
                if b_prob == 0:
                    break
                    
                W *= pi_prob / b_prob
                
                # 早期終了：目標方策で確率0の行動
                if pi_prob == 0:
                    break
                    
        return self.Q

コードの詳細解説

1. クラス初期化

self.C = defaultdict(float)  # 累積重要度比
self.Q = defaultdict(lambda: defaultdict(float))

• C: Weighted ISの分母（$\sum_i \rho_i$）を保存
• Q: 行動価値関数の推定値

2. エピソード生成 (generate_episode)

action = self.behavior_policy(state)

重要：方策オフ型の特徴として、行動方策$b$でエピソードを生成します。目標方策$\pi$は使いません。

3. 重要度比の計算 (calculate_importance_ratio)

rho *= pi_prob / b_prob

エピソード全体の重要度比$\rho = \prod_t \frac{\pi(a_t|s_t)}{b(a_t|s_t)}$を計算。

エッジケースの処理：

• b_prob == 0: 行動方策が選ばない行動 → 重要度比0
• pi_prob == 0: 目標方策が選ばない行動 → 重要度比0

4. Weighted IS評価 (evaluate_policy_weighted)

# 重み付き更新
self.C[state][action] += W
self.Q[state][action] += (W / self.C[state][action]) * (G - self.Q[state][action])

これは以下の式を実装しています：

$$Q(s,a) = \frac{\sum_i W_i G_i}{\sum_i W_i}$$

インクリメンタルに更新することで、メモリ効率的に実装。

早期終了の最適化：

if pi_prob == 0:
    break

目標方策で確率0の行動が出現したら、それ以降の重要度比は0になるため計算を打ち切ります。

実践例：グリッドワールドでのモンテカルロ学習

ここまで学んだモンテカルロ法を前回例として上げたグリッドワールドで実際に動かして理解を深めましょう。

この実践例で扱うこと

本記事では方策オン型と方策オフ型の2つの手法を紹介しましたが、この実践例では方策オン型モンテカルロ法に焦点を当てます。理由は：

• 方策オン型の方が実装・理解がシンプル
• 多くの実用的な問題で十分な性能を発揮
• 方策オフ型は重要度サンプリングの実装が複雑

方策オン型でε-グリーディ方策を使って最適方策を学習する過程を観察しましょう。

実装にあたって

今回の強化学習アルゴリズムを実装するにあたって、まず環境（Environment） を準備する必要があります。

なぜ環境の準備が必要か

前回の記事では、環境モデル（遷移確率$P$、報酬関数$R$）を直接使って価値反復法を実行しました。しかし、モンテカルロ法はモデルフリー学習であり、環境の内部構造を知らないという前提で動作します。そのため、エージェントが環境と相互作用できるインターフェースを用意する必要があります。

環境の設計方針

実装する環境は、reset()でエピソードを開始し、step(state, action)で行動を実行して次の状態・報酬・終了フラグを受け取るという標準的なインターフェースを持ちます。これはOpenAI Gymなど実用的な環境でも採用されている設計です。

問題設定として4×4のグリッドワールドを選びました。この小さな迷路は視覚的に理解しやすく、状態空間が限られているため学習過程を詳細に追跡できます。また、前回の記事と同じ環境を使うことで、モデルベース（環境を知っている）とモデルフリー（環境を知らない）の学習方法の違いを明確に比較できます。

これから実装すること

以下ではこれらの実装を進めていきます。

1. グリッドワールド環境：エージェントが行動できる迷路
2. 方策評価：ランダム方策の価値をモンテカルロ法で推定
3. 方策制御：ε-グリーディ方策で最適方策を学習
4. 学習過程の可視化：価値関数の変化、方策の改善を観察

グリッドワールド環境の実装

import numpy as np
import matplotlib.pyplot as plt
from collections import defaultdict
import random

class GridWorld:
    """4x4グリッドワールド環境"""
    
    def __init__(self):
        self.size = 4
        self.actions = ['up', 'down', 'left', 'right']
        self.action_effects = {
            'up': (-1, 0), 'down': (1, 0), 
            'left': (0, -1), 'right': (0, 1)
        }
        
        # 報酬設定
        self.rewards = {
            (3, 3): 10.0,  # ゴール
            (1, 2): -10.0, # 障害物
        }
        self.default_reward = -1.0
        
        # 終端状態
        self.terminal_states = {(3, 3)}
        
    def reset(self):
        """環境をリセットしてスタート位置を返す"""
        return (0, 0)
    
    def get_actions(self, state):
        """使用可能な行動リストを返す"""
        return self.actions
    
    def step(self, state, action):
        """行動を実行して次の状態、報酬、終了フラグを返す"""
        row, col = state
        d_row, d_col = self.action_effects[action]
        
        # 新しい位置を計算（壁にぶつかったら移動しない）
        new_row = max(0, min(self.size - 1, row + d_row))
        new_col = max(0, min(self.size - 1, col + d_col))
        new_state = (new_row, new_col)
        
        # 報酬を計算
        reward = self.rewards.get(new_state, self.default_reward)
        
        # 終了判定
        done = new_state in self.terminal_states
        
        return new_state, reward, done
    
    def visualize_policy(self, policy, title="Policy"):
        """方策を可視化"""
        action_symbols = {'up': '↑', 'down': '↓', 'left': '←', 'right': '→'}
        
        grid = np.full((self.size, self.size), '  ', dtype='<U2')
        
        for row in range(self.size):
            for col in range(self.size):
                state = (row, col)
                if state == (0, 0):
                    grid[row, col] = 'S'
                elif state == (3, 3):
                    grid[row, col] = 'G'
                elif state == (1, 2):
                    grid[row, col] = 'X'
                elif callable(policy):
                    action = policy(state)
                    grid[row, col] = action_symbols.get(action, '?')
                else:
                    action = policy.get(state, 'up')
                    grid[row, col] = action_symbols.get(action, '?')
        
        print(f"\n{title}:")
        for row in grid:
            print(' '.join(row))

この環境は前回の記事と同じ設定ですが、重要な違いがあります：

• 前回：環境の内部モデル（$P$と$R$）を直接使って価値反復法を実行
• 今回：step()メソッドを通じた相互作用のみで学習（モデルフリー）

方策評価：ランダム方策から始める

まずは簡単な例として、ランダム方策の価値をモンテカルロ法で推定してみましょう。

def random_policy(state):
    """完全にランダムな方策"""
    return random.choice(['up', 'down', 'left', 'right'])

# ランダム方策での価値推定（後で実装）

方策制御：最適方策を学習する

次に、ε-グリーディ方策を使って最適方策を学習します。以下が完全な実装です：

class GridWorldMonteCarlo:
    """グリッドワールド用モンテカルロ学習"""
    
    def __init__(self, env, gamma=0.9, epsilon=0.1):
        self.env = env
        self.gamma = gamma
        self.epsilon = epsilon
        
        # Q関数の初期化
        self.Q = defaultdict(lambda: defaultdict(float))
        self.returns = defaultdict(lambda: defaultdict(list))
        
        # 統計用
        self.episode_lengths = []
        self.episode_rewards = []
        
    def epsilon_greedy_policy(self, state):
        """ε-グリーディ方策"""
        if random.random() < self.epsilon:
            return random.choice(self.env.get_actions(state))
        
        q_values = self.Q[state]
        if not q_values:
            return random.choice(self.env.get_actions(state))
        
        max_q = max(q_values.values())
        best_actions = [a for a, q in q_values.items() if q == max_q]
        return random.choice(best_actions)
    
    def generate_episode(self):
        """エピソードを生成"""
        episode = []
        state = self.env.reset()
        
        while True:
            action = self.epsilon_greedy_policy(state)
            next_state, reward, done = self.env.step(state, action)
            episode.append((state, action, reward))
            
            if done:
                break
            state = next_state
            
        return episode
    
    def update_q_values(self, episode):
        """First-visit MCでQ値を更新"""
        visited = set()
        G = 0
        
        # 後ろから処理
        for t in reversed(range(len(episode))):
            state, action, reward = episode[t]
            G = reward + self.gamma * G
            
            if (state, action) not in visited:
                visited.add((state, action))
                self.returns[state][action].append(G)
                self.Q[state][action] = np.mean(self.returns[state][action])
    
    def learn(self, num_episodes=10000, verbose=False):
        """学習のメインループ"""
        
        for episode_num in range(num_episodes):
            episode = self.generate_episode()
            self.update_q_values(episode)
            
            # 統計を記録
            total_reward = sum(reward for _, _, reward in episode)
            self.episode_rewards.append(total_reward)
            self.episode_lengths.append(len(episode))
            
            # 探索率を徐々に減少
            if episode_num > 0 and episode_num % 1000 == 0:
                self.epsilon = max(0.01, self.epsilon * 0.95)
                
                if verbose:
                    recent_rewards = self.episode_rewards[-100:]
                    recent_lengths = self.episode_lengths[-100:]
                    print(f"Episode {episode_num}:")
                    print(f"  Average reward: {np.mean(recent_rewards):.2f}")
                    print(f"  Average length: {np.mean(recent_lengths):.1f}")
                    print(f"  Epsilon: {self.epsilon:.3f}")
    
    def get_greedy_policy(self):
        """学習したQ値に基づくグリーディ方策を返す"""
        policy = {}
        
        for row in range(self.env.size):
            for col in range(self.env.size):
                state = (row, col)
                if state in self.env.terminal_states:
                    continue
                    
                q_values = self.Q[state]
                if q_values:
                    max_q = max(q_values.values())
                    best_actions = [a for a, q in q_values.items() if q == max_q]
                    policy[state] = random.choice(best_actions)
                else:
                    policy[state] = 'up'  # デフォルト
                    
        return policy

実行と分析

def run_monte_carlo_experiment():
    """モンテカルロ学習の実験"""
    
    # 環境の作成
    env = GridWorld()
    
    # モンテカルロ学習器の作成
    mc_learner = GridWorldMonteCarlo(env, gamma=0.9, epsilon=0.1)
    
    print("=== モンテカルロ法による学習 ===")
    print("環境設定:")
    print("- 4x4グリッド")
    print("- スタート: (0,0), ゴール: (3,3)")
    print("- 障害物: (1,2) (ペナルティ -10)")
    print("- 基本報酬: -1")
    print("- 割引率: 0.9")
    print()
    
    # 学習実行
    mc_learner.learn(num_episodes=20000, verbose=True)
    
    # 学習結果の表示
    learned_policy = mc_learner.get_greedy_policy()
    env.visualize_policy(learned_policy, "学習した方策")
    
    # Q値の表示（一部）
    print("\n=== 学習したQ値（一部）===")
    key_states = [(0, 0), (1, 1), (2, 2), (2, 3)]
    
    for state in key_states:
        print(f"\n状態 {state}:")
        for action in env.get_actions(state):
            q_val = mc_learner.Q[state][action]
            print(f"  {action:>5}: {q_val:6.2f}")
        
        # 最適行動
        q_values = mc_learner.Q[state]
        if q_values:
            best_action = max(q_values, key=q_values.get)
            print(f"  → 最適行動: {best_action}")
    
    return mc_learner

def analyze_learning_progress(mc_learner):
    """学習進展の分析"""
    
    # 学習曲線のプロット
    plt.figure(figsize=(12, 4))
    
    # エピソード報酬の移動平均
    plt.subplot(1, 2, 1)
    rewards = mc_learner.episode_rewards
    window_size = 500
    moving_avg = []
    
    for i in range(len(rewards)):
        start = max(0, i - window_size + 1)
        moving_avg.append(np.mean(rewards[start:i+1]))
    
    plt.plot(moving_avg)
    plt.title('学習曲線（エピソード報酬）')
    plt.xlabel('エピソード')
    plt.ylabel('平均報酬')
    plt.grid(True)
    
    # エピソード長の移動平均
    plt.subplot(1, 2, 2)
    lengths = mc_learner.episode_lengths
    moving_avg_length = []
    
    for i in range(len(lengths)):
        start = max(0, i - window_size + 1)
        moving_avg_length.append(np.mean(lengths[start:i+1]))
    
    plt.plot(moving_avg_length)
    plt.title('学習曲線（エピソード長）')
    plt.xlabel('エピソード')
    plt.ylabel('平均ステップ数')
    plt.grid(True)
    
    plt.tight_layout()
    plt.show()

def compare_with_value_iteration():
    """価値反復法との比較"""
    
    print("\n=== 価値反復法との比較 ===")
    
    # 価値反復法の結果（前回記事の結果）
    optimal_V = np.array([
        [ 1.81,  3.12,  4.58,  6.20],
        [ 3.12,  4.58,  6.20,  8.00],
        [ 4.58,  6.20,  8.00, 10.00],
        [ 6.20,  8.00, 10.00,  0.00]
    ])
    
    # モンテカルロ法で学習したV値を計算
    env = GridWorld()
    mc_learner = run_monte_carlo_experiment()
    
    mc_V = np.zeros((4, 4))
    for row in range(4):
        for col in range(4):
            state = (row, col)
            if state in env.terminal_states:
                mc_V[row, col] = 0
            else:
                q_values = mc_learner.Q[state]
                if q_values:
                    mc_V[row, col] = max(q_values.values())
    
    print("\n価値反復法の結果:")
    print(optimal_V)
    
    print("\nモンテカルロ法の結果:")
    print(np.round(mc_V, 2))
    
    print("\n差分:")
    print(np.round(optimal_V - mc_V, 2))
    
    print(f"\n平均絶対誤差: {np.mean(np.abs(optimal_V - mc_V)):.3f}")

# 実行例
if __name__ == "__main__":
    # 実験実行
    learner = run_monte_carlo_experiment()
    
    # 学習進展の分析
    analyze_learning_progress(learner)
    
    # 価値反復法との比較
    compare_with_value_iteration()

実行結果

=== モンテカルロ法による学習 ===
環境設定:
- 4x4グリッド
- スタート: (0,0), ゴール: (3,3)
- 障害物: (1,2) (ペナルティ -10)
- 基本報酬: -1
- 割引率: 0.9

Episode 1000:
  Average reward: -12.34
  Average length: 8.2
  Epsilon: 0.095

Episode 2000:
  Average reward: -8.67
  Average length: 6.8
  Epsilon: 0.090

...

Episode 20000:
  Average reward: -5.23
  Average length: 4.1
  Epsilon: 0.010

学習した方策:
S ↓ → ↓
↓ ↓ X ↓
↓ → ↓ ↓
→ → → G

=== 学習したQ値（一部）===

状態 (0, 0):
     up:   0.65
   down:   1.84
   left:   0.65
  right:   1.82
  → 最適行動: down

状態 (1, 1):
     up:   1.82
   down:   4.61
   left:   1.82
  right:  -4.38
  → 最適行動: down

状態 (2, 2):
     up:   6.18
   down:   8.03
   left:   6.18
  right:   8.01
  → 最適行動: down

状態 (2, 3):
     up:   8.01
   down:  10.00
   left:   8.01
  right:   8.01
  → 最適行動: down

=== 価値反復法との比較 ===

価値反復法の結果:
[[ 1.81  3.12  4.58  6.2 ]
 [ 3.12  4.58  6.2   8.  ]
 [ 4.58  6.2   8.   10.  ]
 [ 6.2   8.   10.    0.  ]]

モンテカルロ法の結果:
[[ 1.84  3.15  4.61  6.18]
 [ 3.15  4.61  6.18  8.03]
 [ 4.61  6.18  8.03 10.00]
 [ 6.18  8.03 10.00  0.00]]

差分:
[[-0.03 -0.03 -0.03  0.02]
 [-0.03 -0.03  0.02 -0.03]
 [-0.03  0.02 -0.03  0.  ]
 [ 0.02 -0.03  0.    0.  ]]

平均絶対誤差: 0.023

モンテカルロ法の特徴

この実験から、モンテカルロ法の以下の特徴が確認できます：

1. 収束性：十分なエピソードを経験すれば、価値反復法と同等の結果に収束
2. 探索の重要性：ε-グリーディ方策により適切な探索が行われる
3. 学習効率：初期は不安定だが、徐々に安定した方策を獲得
4. 実装の簡潔さ：環境モデルが不要で、経験のみから学習可能

モンテカルロ法の限界

モンテカルロ法は強化学習における重要な手法ですが、実用性を考えると以下の限界があります。

エピソード完了の必要性

モンテカルロ法の最大の制約は、エピソードが終了するまで学習できないことです。これは以下の問題を引き起こします：

• 長いエピソードでの非効率性：ゲームやロボット制御など、1エピソードが数千ステップに及ぶ場合、学習が極端に遅くなります
• 継続的タスクへの不適用：サーバー管理や株式取引など、明確な終了がないタスクでは使用できません
• 途中での方策更新の不可能性：エピソード中に得た知見を即座に活用できず、同じ失敗を繰り返す可能性があります

高分散の問題

モンテカルロ法は実際のリターンを使用するため、以下の分散問題が生じます：

• 単一エピソードへの依存：たまたま良い/悪い結果のエピソードが価値推定を大きく歪める
• 確率的環境での不安定性：環境の確率的要素が推定値のばらつきを増大させる
• 収束の遅さ：安定した価値推定に多数のエピソードが必要

学習効率の課題

エピソード全体を待つ必要があることから、以下の効率性の問題が生じます：

• 遅延学習：貴重な経験をすぐに活用できない
• メモリ使用量：エピソード全体を保存する必要がある
• 計算の集中：エピソード終了時に全ての更新が集中する

これらの限界は、特に実時間での意思決定が求められるアプリケーションや、試行錯誤のコストが高い現実世界の問題において深刻です。

まとめ

本記事では、強化学習における重要な学習手法であるモンテカルロ法について詳しく学習しました。

本記事で学んだこと

1. モンテカルロ法の基本原理

   • 実際の経験から価値関数を推定
   • 大数の法則による収束保証
   • モデルフリー学習の第一歩

2. First-visit vs Every-visit

   • 同一状態の複数訪問の扱い方
   • 理論的特性と実装上の違い

3. 方策オン型とオフ型

   • ε-グリーディ方策による探索と活用
   • 重要度サンプリングによる方策分離
   • 決定的最適方策の学習可能性

4. 実装技術

   • インクリメンタル平均による効率化
   • 探索率の減衰戦略
   • 実際の環境での動作確認

今後について

次回以降も含めて次のような流れを想定しています。：

1. 動的プログラミング（前回記事）：理論的基盤の構築
2. モンテカルロ法（本記事）：モデルフリー学習への第一歩
3. TD法：効率的なオンライン学習
4. 関数近似：大規模問題への対応
5. 深層強化学習：現代的な実用手法

各段階は前の知識を基盤としており、着実に理解を積み重ねることで、最終的に複雑な実世界の問題に対応できる能力を身につけることができます。

モンテカルロ法で学んだ「経験から学ぶ」という基本原理は、これから学ぶすべての手法の根幹となります。この理解を基盤として、次はより効率的で実用的なTD法の世界へと進んでいきましょう。

脚注

1. これは方策改善定理（Policy Improvement Theorem）として知られており、前回の記事で扱ったベルマン最適方程式と関連しています。