強化学習におけるマルコフ決定過程 (MDP) とは？

マルコフ決定過程 (MDP) とは？
マルコフ決定過程の要素
マルコフ決定過程の流れ
割引報酬の概念
ポリシーと価値関数
具体例：迷路問題
Pythonで簡単なMDPの例
まとめ

マルコフ決定過程 (MDP) とは？

マルコフ決定過程 (Markov Decision Process, MDP) は、エージェントがある環境内で行動し、最適な行動方針（ポリシー）を見つけるための数学的枠組みです。
特に、強化学習で頻繁に使われ、将来的な報酬を最大化するための意思決定モデルを提供します。

以前の記事で紹介したバンディット問題は、毎回同じ条件の問題（どのスロットを選ぶか）を解くため、状態の変化はありませんが、迷路を解くなどといった問題の場合、エージェントの行動によって、状態が変わり、適切な行動も変化します。
このような問題に対応するためにはMDPの考え方が必要になります。

404 NOT FOUND | lifetechia

テクノロジーを活用して人生をより豊かに

マルコフ決定過程の要素

MDP は以下の 4 つの要素から構成されます：

状態 (State, $S$ )
– エージェントが現在いる環境の状況を表します。例：迷路内での位置
行動 (Action, $A$ )
– エージェントが取れる選択肢（行動）です。例：上、下、左、右に移動する。
遷移確率 (Transition Probability, $P(s'|s, a)$ )
– ある状態 $s$ で行動 $a$ を取ったとき、次の状態 $s'$ に遷移する確率。
→ MDP の “マルコフ性” とは、「次の状態は現在の状態と行動だけに依存する」という性質を意味します。
報酬 (Reward, $R(s, a, s')$ )
– エージェントが特定の行動を取り、状態が変わったときに得られる報酬。
例：ゴールにたどり着くと +10 点。

マルコフ決定過程の流れ

エージェントは現在の状態 $s_t$ に基づいて行動 $a_t$ を選択。
選択した行動の結果、次の状態 $s_{t+1}$ に遷移し、報酬 $r_t$ を受け取る。
エージェントはこれを繰り返し、長期的な報酬の合計を最大化する行動方針（ポリシー）を見つける。

割引報酬の概念

MDP では、未来の報酬の価値は現在の報酬よりも低く見積もられます。
割引率 ( $\gamma$ ) を使って、将来の報酬を徐々に割り引いて評価します。

$G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots$

$\gamma \in [0, 1]$
$\gamma$ が 1 に近いほど、将来の報酬を重視する。
$\gamma$ が 0 に近いほど、即時の報酬を重視する。

ポリシーと価値関数

ポリシー (Policy, $\pi(s)$ ):
状態 $s$ において、どの行動 $a$ を選ぶかを決める戦略。
状態価値関数 (State Value Function, $V(s)$ ):
特定の状態 $s$ から将来得られる期待報酬の合計。

$V(s) = \mathbb{E}\left[ \sum_{t=0}^{\infty} \gamma^t r_t \mid s_0 = s \right]$

行動価値関数 (Action Value Function, $Q(s, a)$ ):
状態 $s$ で行動 $a$ を取ったときの期待報酬。

具体例：迷路問題

迷路を解くエージェントを考えます：

状態 (S): エージェントの位置（例： $(x, y)$ ）。
行動 (A): 上、下、左、右の 4 つの移動。
遷移確率 (P): 行動を選んだ結果、次の状態に移動する確率。
報酬 (R): ゴールにたどり着いたら +10 点、それ以外は -1 点。

エージェントはゴールにたどり着くまでの報酬を最大化するポリシーを学習します。

Pythonで簡単なMDPの例

以下は、迷路のような環境で MDP を実装する簡単なコード例です。

import numpy as np

# 状態と行動を定義
states = ["A", "B", "C", "D"]  # 4つの状態
actions = ["left", "right"]     # 2つの行動

# 遷移確率と報酬の定義 (状態, 行動) -> (次の状態, 報酬)
transition_probs = {
    "A": {"left": ("A", 0), "right": ("B", 1)},
    "B": {"left": ("A", 0), "right": ("C", 2)},
    "C": {"left": ("B", 1), "right": ("D", 3)},
    "D": {"left": ("C", 2), "right": ("D", 0)},  # Dは終端状態
}

# 割引率の設定
gamma = 0.9  # 将来の報酬を割り引くための係数

# 状態価値関数を初期化
V = {s: 0 for s in states}  # 各状態の価値を0で初期化

# 価値反復法 (Value Iteration) の実装
for _ in range(10):  # 10回の反復
    new_V = V.copy()
    for state in states:
        action_values = []
        for action in actions:
            next_state, reward = transition_probs[state][action]
            value = reward + gamma * V[next_state]
            action_values.append(value)
        new_V[state] = max(action_values)  # 最大価値の行動を選択
    V = new_V

# 結果を表示
print("各状態の価値関数:")
for state, value in V.items():
    print(f"状態 {state}: {value:.2f}")

遷移確率と報酬の設定:
各状態から行動を取ったときに、次の状態と報酬を定義しています。

transition_probs = {
    "A": {"left": ("A", 0), "right": ("B", 1)},
    "B": {"left": ("A", 0), "right": ("C", 2)},
    "C": {"left": ("B", 1), "right": ("D", 3)},
    "D": {"left": ("C", 2), "right": ("D", 0)},  # Dは終端状態
}

状態 “A”
– “left” 行動を取る → 次の状態: “A”, 報酬: 0
- 状態 “A” に留まり、報酬は 0 です。つまり、何も進展がない行動です。
- “right” 行動を取る → 次の状態: “B”, 報酬: 1
- エージェントは「B」に移動し、1 点の報酬を得ます。
状態 “B”
– “left” 行動を取る → 次の状態: “A”, 報酬: 0
- 「B」から「A」に戻り、報酬は 0 点です。
- “right” 行動を取る → 次の状態: “C”, 報酬: 2
- 「B」から「C」へ進み、2 点の報酬を得ます。
状態 “C”
– “left” 行動を取る → 次の状態: “B”, 報酬: 1
- 状態「B」に戻って 1 点の報酬を得ます。
- “right” 行動を取る → 次の状態: “D”, 報酬: 3
- ゴール状態「D」にたどり着き、3 点の報酬を獲得。
状態 “D” (ゴール状態)
– “left” 行動を取る → 次の状態: “C”, 報酬: 2
- 状態「C」に戻り、2 点の報酬を得ます。
- “right” 行動を取る → 次の状態: “D”, 報酬: 0
- 「D」に留まり、報酬は 0 点。エージェントはここで終了します。