Markov Decision Process (MDP)

マルコフ決定過程 (MDP) は、逐次的な意思決定問題の数学的モデルです。エージェントが状態を観測し、行動を選択して報酬を受け取り、選択と偶然の両方に左右される次の状態へ移ります。形式的には、MDPは状態の集合、行動の集合、遷移確率P(s′ | s, a)、報酬関数R(s, a)、通常0～1の割引率γで構成されます。MDPを解くとは、各状態で行動を選ぶルールであるポリシーを見つけ、将来の報酬の割引合計の期待値を最大化することです。MDPは1950年代のオペレーションズリサーチから生まれました。Richard Bellmanの動的計画法が解法を提供し、強化学習 (RL)の標準的な問題設定になっています。

マルコフ性#

定義の前提となるのはマルコフ性です。次の状態と報酬は現在の状態と行動だけに依存し、そこに至る経路には依存しません。そのため、状態は関連情報をすべて含むエージェントの要約となります。移動物体の場合、カメラの単一フレームでは位置は分かっても速度は分からないため、この前提を満たしません。そこでDeepMindのAtari向けDQNは、動きを捉えられるように直近4フレームを重ねてネットワークに入力しました。

ノイズや遮蔽のあるセンサーを持つロボットのように、エージェントが完全な状態を観測できない場合、問題は部分観測マルコフ決定過程 (POMDP)になります。エージェントは状態そのものではなく、フィルターやリカレントネットワークで維持する状態の信念に基づいて行動します。

MDPの構成要素#

• 状態: エージェントが取り得る状況です。たとえば、ロボットの関節角度や、手を伸ばしている対象物の位置などです。
• 行動: 各状態で選択できる行動です。行動空間は離散（左折、右折）または連続（度数で表した操舵角）です。
• 遷移確率: 行動後にそれぞれの次の状態へ移る確率です。車輪のスリップ、他のドライバー、その他すべてのランダム要因を表します。
• 報酬: 遷移に対する即時の数値フィードバックです。報酬の設計によってタスクが決まり、不注意な設計は報酬ハッキングを招きます。
• 割引率: 即時の報酬に対して、将来の報酬をどの程度重視するかを表します。γ = 0.9の場合、10ステップ後の報酬の価値は、同じ報酬を今受け取る場合の0.9¹⁰ ≈ 0.35です。

エピソードが終了するまで、各タイムステップで同じやり取りを繰り返します。

MDPを解く#

状態価値とは、あるポリシーに従った場合にその状態から得られるリターンの期待値であり、最適価値はベルマン方程式を満たします。各状態の価値は、最良の行動による即時報酬と、その行動が導く状態の価値を割引率と確率で重み付けした値の合計です。遷移確率と報酬が分かっている場合、動的計画法でこの方程式を直接解けます。価値反復法（Bellman、1957）は価値が変化しなくなるまで方程式を繰り返し適用し、方策反復法（Howard、1960）はポリシーの評価と改善を交互に行います。

このNumPyの例では、SuttonとBartoのReinforcement Learning: An Introductionに登場するリサイクルロボットを使って価値反復法を実行します。このロボットは、バッテリー残量が多い場合と少ない場合に、缶を探す、待機する、充電する、という選択を行います。

import numpy as np

# リサイクルロボットのMDP: 状態0 = バッテリー残量多、1 = バッテリー残量少; 行動0 = 探索、1 = 待機、2 = 充電
gamma = 0.9  # 割引率
P = np.zeros((2, 3, 2))  # P[s, a, s'] = sでaを実行した後にs'へ到達する確率
P[0, 0] = [0.7, 0.3]  # バッテリー残量が多い状態での探索は、残量を少なくする可能性があります
P[1, 0] = [0.4, 0.6]  # バッテリー残量が少ない状態での探索は、バッテリーを使い切る可能性があります（ロボットは救助され、充電されます）
P[:, 1] = np.eye(2)  # 待機するとバッテリー残量は変わりません
P[:, 2] = [1.0, 0.0]  # 充電すると常にバッテリー残量が多い状態に戻ります
R = np.array([[2.0, 1.0, 0.0], [0.0, 1.0, 0.0]])  # 期待値R[s, a]; バッテリー残量が少ない状態での探索: 0.6 * 2 + 0.4 * -3 = 0

# 価値反復法: 価値が変化しなくなるまでベルマン最適性更新を適用します
V = np.zeros(2)
for _ in range(500):
    Q = R + gamma * P @ V  # 各状態における各行動の価値
    V = Q.max(axis=1)

actions = ["search", "wait", "recharge"]
print("Optimal values:", V.round(2))
print("Optimal policy:", {s: actions[a] for s, a in zip(["high", "low"], Q.argmax(axis=1))})

バッテリー残量が多い状態で15.75、少ない状態で14.17の価値と、残量が多い場合は探索し、少ない場合は充電するポリシーが出力されます。バッテリー残量が少ない状態で探索すると40%の確率で−3の救助ペナルティを受けるため、その価値は充電を下回ります。

遷移確率が不明な場合、強化学習は経験から同じ価値を推定します。Q学習はサンプリングした遷移から行動価値を更新し、方策勾配法はポリシーを直接調整します。また、状態空間を列挙するには大きすぎる場合、深層強化学習ではニューラルネットワークを使用します。モンテカルロ木探索などの計画アルゴリズムは、現在の状態から到達可能な将来だけをシミュレーションし、大規模なMDPをオンラインで解きます。

MDPと関連モデルの比較#

• マルコフ連鎖: 行動も報酬もない、ランダムな状態の系列です。MDPでは選択肢と目的が加わります。
• 隠れマルコフモデル (HMM): ノイズのある信号を通じてのみ状態が観測されるマルコフ連鎖です。POMDPとMDPの関係もこれと同様です。
• 多腕バンディット: 単一の状態を持つMDPで、各行動の成果は過去に依存しません。
• 強化学習: 遷移確率を与えられずに、インタラクションからMDPで適切に行動する方法を学習する手法群です。

用途#

• ロボティクスと制御: 物体の把持、歩行、ナビゲーションはMDPとして定式化され、そのポリシーはシミュレーションでトレーニングされることがよくあります。カメラベースの制御では、Ultralytics YOLO26などの検出器から状態を得られます。各フレームを物体クラスとボックス座標の短いリストに変換することで、生のピクセルよりもはるかに小さい入力でポリシーを処理できます。
• 言語モデルのトレーニング: RLHFとRLVRでは、テキスト生成をMDPとして扱います。状態はプロンプトとそれまでに生成したトークン、行動は次のトークンであり、応答が完成したときに報酬を受け取ります。
• オペレーションズリサーチ: 在庫の再発注、設備の保守、動的価格設定は典型的なMDPです。Ronald Howardは、Searsのカタログ郵送を最適化する中で方策反復法を開発しました。