モンテカルロ法と学習更新式の一般化：強化学習コース(4/N)

はじめに

前回の記事では、環境モデルが既知の場合のプランニング問題として価値反復法について解説しました。本記事では、強化学習の現実的な設定であるモデルフリー学習に焦点を当て、その第一歩となるモンテカルロ法について詳しく解説します。

これまでのシリーズで学んだ内容は以下の通りです。

• 第1回 - 強化学習の全体像と問題設定
• 第2回 - 環境側の定式化（マルコフ決定過程）
• 第3回 - エージェント側の概念とプランニングアルゴリズム（価値反復法）
• 第4回（本記事）- モデルフリー学習とモンテカルロ法

モデルベース vs モデルフリー

環境モデルとは

前回の価値反復法では、以下の情報が既知でした。

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

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

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

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

例1：自動運転システム

• 天候、路面状況、他の車の動きなど無数の要因
• 物理シミュレーションはあっても、現実との差（Reality Gap）が存在
• 地域や時間帯による交通パターンの変化

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

• 市場参加者の心理、政治情勢、経済指標など予測困難な要因
• 過去のデータから未来を完全に予測することは不可能
• 自分の行動自体が市場に影響を与える

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

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

アプローチの分類

強化学習では、環境モデルとの関係により以下の3つのアプローチに分類されます。

強化学習のアプローチ分類

プランニング（Planning）

• 環境モデル$P$と$R$が完全に既知
• 最適方策を計算で求める問題
• 例 価値反復法、方策反復法（前回記事）

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

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

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

• 環境モデルを一切仮定しない
• 経験から直接、価値関数や方策を学習
• 例 モンテカルロ法、TD学習、Q学習

モデルベース vs モデルフリーの特徴

モデルベース学習の特徴

• 利点 - サンプル効率が良い、学習したモデルで将来の計画立案が可能
• 欠点 - モデルの誤差が方策の性能に直接影響、複雑な環境ではモデル化自体が困難

モデルフリー学習の特徴

• 利点 - 複雑な環境でも適用可能、モデル化の誤差を考慮する必要がない
• 欠点 - 多くの経験（サンプル）が必要、環境が変化すると再学習が必要

本記事では、実世界の多くの問題に適用可能なモデルフリー学習の基本手法であるモンテカルロ法を学習します。

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

基本的なアイデア

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

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

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

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

エピソードと価値推定

エピソードの定義

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

エピソード（Episode）

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

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

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

モンテカルロ法はエピソード的タスク（明確な終了条件がある問題）を前提とした手法です。

価値推定の原理

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

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

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

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

モンテカルロ推定の原理

状態$s$について、多数のエピソードを経験し、状態$s$を実際に訪問した回数を$n$回とする。これらの訪問で得られた累積報酬を$G_1, G_2, ..., G_n$とすると、

$$V^{\pi}(s) \approx \frac{1}{n} \sum_{i=1}^{n} G_i$$

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

First-visit vs Every-visit

同じ状態が1つのエピソード中に複数回出現する場合の扱い方により、2つの手法があります。

First-visit Monte Carlo

• 各エピソードにおいて、状態$s$が最初に出現した時点からのリターンのみを使用
• 統計的独立性が保証される

Every-visit Monte Carlo

• 各エピソードにおいて、状態$s$が出現するすべての時点からのリターンを使用
• より多くのデータを活用できる

実用的には、Every-visit MCの方がデータ効率が良く、実装もシンプルなため、より頻繁に使用されます。

学習更新式の発展

基本的な平均更新

モンテカルロ法では、新しいリターン$G$が得られるたびに価値関数を更新します。基本的な更新式は、

$$V_{n+1}(s) = \frac{1}{n+1} \sum_{i=1}^{n+1} G_i$$

これをインクリメンタル更新の形で書き直すと、

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

学習率パラメータα

実用的な学習では、固定の学習率$\alpha$を使用することが多くあります。

一般化された更新式

$$V(s) \leftarrow V(s) + \alpha[G - V(s)]$$

ここで

• $\alpha \in (0, 1]$は学習率（ステップサイズ）
• $\alpha = \frac{1}{n+1}$とすると従来の平均更新と同じ
• 固定の$\alpha$（例 $\alpha = 0.1$）を使うことも多い

学習率の選択

$\alpha = \frac{1}{n+1}$（減衰学習率）の特徴

• すべてのサンプルが等しい重みを持つ
• 収束保証がある（確率的近似理論）
• 学習の後期では更新が小さくなりすぎる可能性

固定$\alpha$の特徴

• 最近のサンプルにより大きな重みを与える
• 環境が変化する場合に適応しやすい
• 収束は近似的（バイアスが残る可能性）

この学習率パラメータ$\alpha$の概念は、次回学習予定のTD（Temporal Difference）学習でも中心的な役割を果たします。

方策制御 探索と活用

ε-グリーディ方策

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

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

ε-グリーディ方策は、この問題を確率的に解決します。

ε-グリーディ方策

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

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

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

rl_srcでの実装とTD学習への準備

実装アーキテクチャ

本シリーズで継続して開発しているrl_srcライブラリでは、モンテカルロ法も前回の価値反復法と統一されたアーキテクチャで実装されています。

🔗 rl-src: 強化学習ライブラリ

First-visit Monte Carlo戦略の実装

モンテカルロ法の核心となるFirst-visit MC戦略の実装を見てみましょう。

class FirstVisitMonteCarloStrategy(ModelFreeStrategy)
    """
    First-visit Monte Carlo方法による価値関数学習
    
    エピソードを生成して、各状態行動ペアの初回訪問時のリターンから
    Q値を学習する。
    """
    
    def __init__(self, environment, epsilon=0.1, gamma=1.0, random_seed=None):
        super().__init__(gamma=gamma)
        self.environment = environment
        self.epsilon = epsilon
        
        # Q値とカウンタ
        self.Q = defaultdict(float)
        self.returns = defaultdict(list)
        self.visit_counts = defaultdict(int)
    
    def get_policy(self, observation, available_actions):
        """ε-greedy方策による行動分布を取得"""
        state = self._observation_to_state(observation)
        
        # Q値から最適行動を決定
        best_action = None
        best_q_value = float('-inf')
        
        for action in available_actions:
            q_value = self.Q.get((state, action), 0.0)
            if q_value > best_q_value:
                best_q_value = q_value
                best_action = action
        
        # ε-greedy方策の確率分布
        action_probs = {}
        explore_prob = self.epsilon / len(available_actions)
        
        for action in available_actions:
            if action == best_action:
                # 最適行動 (1-ε) + ε/|A|
                action_probs[action] = (1.0 - self.epsilon) + explore_prob
            else:
                # その他の行動 ε/|A|
                action_probs[action] = explore_prob
        
        return action_probs

インクリメンタル更新の実装

記事で説明した学習率パラメータαによる更新は、実装では以下のようになります。

@staticmethod
def incremental_update(current_value float, new_return float, count int) -> float
    """
    インクリメンタル平均更新
    
    Args:
        current_value 現在の値
        new_return 新しいリターン
        count これまでの観測回数
        
    Returns
        更新された値
    """
    # V(s) ← V(s) + α[G - V(s)] where α = 1/count
    return current_value + (new_return - current_value) / count

このcountパラメータが学習率α = 1/(n+1)に対応し、固定学習率αに変更することで次回学習するTD学習への自然な拡張が可能になります。

デモンストレーション

実際の動作はrl_src/examples/monte_carlo_demo.pyで確認できます。主な機能は以下の通りです。

• First-visit Monte Carlo - 基本的なMC学習
• Monte Carlo Control - ε-グリーディ方策による最適方策学習
• 方策評価 - 固定方策の価値推定
• 価値反復法との比較 - 理論値との差分確認

デモを実行すると、以下のような学習過程が観察できます。

=== First-visit Monte Carlo方法 ===
環境設定
  グリッドサイズ 3x3
  ゴール位置 (2, 2)

エピソード 100
  平均エピソード長 8.2
  平均報酬 -0.234
  学習したQ値の数 28
  総訪問回数 147

学習された方策
  ↓   →   ↓
  ↓   →   ↓
  →   →   G

このように、実際の経験からQ値を学習し、最適方策に収束していく過程を確認できます。

次回予告 TD学習への発展

モンテカルロ法は強化学習における重要な基礎ですが、以下の限界があります。

エピソード完了の必要性

• エピソードが終了するまで学習できない
• 長いエピソードでは学習が非効率
• 継続的タスクには適用不可能

高分散の問題

• 実際のリターンを使用するため分散が大きい
• 確率的環境での不安定性

次回の記事では、これらの限界を克服するTD（Temporal Difference）学習について解説します。

TD学習の特徴

• ブートストラッピング - 推定値を使って推定値を更新
• オンライン学習 - 各ステップで即座に更新可能
• 低分散 - 推定値を使うことで分散を削減

特に、モンテカルロ法で導入した学習率パラメータ$\alpha$を用いた更新式が、TD学習でどのように活用されるかに注目してください。

まとめ

本記事では、モデルフリー強化学習の基礎となるモンテカルロ法について学習しました。

1. モデルベース vs モデルフリー - 現実的な問題設定の理解
2. モンテカルロ法の原理 - 経験から価値を推定する基本概念
3. 学習更新式の一般化 - $\frac{1}{n+1}$から$\alpha$への拡張
4. 探索と活用 - ε-グリーディ方策による最適方策学習

特に重要なのは、学習更新式における学習率パラメータ$\alpha$の導入です。この概念は次回学習するTD学習、さらにはQ学習や方策勾配法など、現代の強化学習アルゴリズムの基礎となります。

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