Markov Decision Process (MDP)

• 別名: MDP
• カテゴリ: Learning & autonomy › RL & simulation
• タグ: reinforcement-learning, decision-making, dynamic-programming, probability, robot-learning

逐次意思決定の標準的な数理モデル。状態、行動、遷移確率、報酬、割引率からなり、次の状態は現在の状態と行動だけで決まる。

定義

マルコフ決定過程（Markov decision process、MDP）は、状態を観測し、行動を選び、報酬を受け取って新しい状態へ移る、ということを繰り返すエージェントを記述する。通常はタプル (S, A, P, R, γ) として書かれ、多くの場合これに初期状態分布 ρ₀ が加わる。それぞれ、状態空間、行動空間、遷移確率 P(s′ | s, a)、報酬関数 R(s, a)、そして将来の報酬を即時の報酬に対してどれだけ重視するかを決める 0 から 1 の間の割引率 γ である。決定的な仮定はマルコフ性であり、次の状態の分布は現在の状態と行動だけで決まり、そこに至るまでの履歴には依存しない。1950 年代の Richard Bellman による動的計画法の研究がこの枠組みを確立した。

MDP における目標は、割引報酬和の期待値を最大化するポリシー、すなわち状態から行動（または行動上の分布）への写像である。価値関数 V(s) と行動価値関数 Q(s, a) は、あるポリシーのもとで、ある状態から、またはある状態と行動から得られる期待収益を与える。これらはベルマン方程式を満たし、この方程式はある状態の価値を、即時報酬と後続状態の割引価値の和として表す。P と R が既知で状態空間が小さい場合、価値反復法と方策反復法によって MDP を厳密に解ける。それらが未知である場合や、空間が大きく連続的な場合には、強化学習がサンプリングした経験から価値とポリシーを推定する。

MDP は強化学習のほぼすべて、そして不確実性下のプランニングの大部分の形式的な基盤である。多くの派生形はいずれかの仮定を緩める。部分観測 MDP（POMDP）はエージェントが真の状態を見られるという仮定を外し、制約付き MDP はコストの上限を加え、セミ MDP（semi-MDP）は所要時間が可変の行動を許し、マルコフゲームのようなマルチエージェントへの拡張は複数の意思決定者をモデル化する。状態に何を含めるかはエンジニアリング上の判断である。速度、接触状態、他のエージェントの意図といった重要な情報を除外すると、エージェントの視点からはその過程はもはやマルコフではなくなる。

重要な理由

強化学習の論文はどれも、またロボティクスにおける意思決定手法の大半も、問題を MDP またはその派生形として定式化している。タプルの各要素と、各手法がどの仮定に依存しているかを知っていれば、そうした論文を読み、実機ロボットの状態と報酬を設計し、問題が実際には部分観測であることに気づけるようになる。

主な用途

• マニピュレーションとロコモーションのための強化学習問題の定式化
• 価値反復法と方策反復法による不確実性下のプランニング
• R を推定または整形する報酬設計と逆強化学習
• 遷移関数 P を学習するモデルベース強化学習
• マルコフゲームと潜在的な意図変数による他エージェントとの相互作用のモデル化

実際の使われ方

ロボットアームでブロックを目標位置まで押すタスクを訓練するチームが、このタスクを MDP として定式化する。状態には関節角度と関節速度、ブロックの姿勢、目標位置が含まれ、行動は制御ステップごとのエンドエフェクタ位置の変化量、報酬はブロックから目標までの距離の負値に成功時のボーナスを加えたもので、タスクが多数のステップにわたるため γ は 1 に近い値に設定する。初期のテストでは、ブロックが動いているときにポリシーの挙動が不安定になる。状態にブロックの姿勢は含まれているが、速度が含まれていないためである。ブロックの速度を加えるか、直近の数回分の観測を積み重ねることで、SAC や PPO といった標準的なアルゴリズムが安定して学習できる程度にマルコフ性が回復する。

よくある誤解

• MDP には離散的な状態と行動が必要である — ロボティクスでは連続的な状態空間と行動空間が一般的であり、和は積分に、表形式の手法は関数近似に置き換えられる
• マルコフ性は世界についての事実である — これは選んだ状態の性質であり、速度や隠れ変数を除外すると、物理システムがエージェントの視点からは非マルコフになりうる
• 割引率はせっかちさを表すだけである — 無限ホライズン問題では収益を有界にし、学習の分散と安定性にも影響するため、ハイパーパラメータのように調整されることが多い
• MDP を解くには P のモデルが必要である — 強化学習の手法は、P を書き下すことなく、サンプリングした遷移から良いポリシーを見つける

知っておくべき人

• 強化学習の実務者と研究者
• 状態、行動、報酬を設計するロボット学習エンジニア
• プランニングと意思決定の研究者
• ロボット学習を学び始めたロボティクスの学生

関連技術

• ベルマン方程式（Bellman Equation）
• 価値反復法（Value Iteration）
• 方策反復法（Policy Iteration）
• Q-Learning
• Gymnasium
• 動的計画法（Dynamic Programming）

関連用語

• Reinforcement Learning
• Partially Observable Markov Decision Process (POMDP)
• Hamilton-Jacobi-Bellman Equation (HJB)
• Inverse Reinforcement Learning
• Offline Reinforcement Learning
• Proximal Policy Optimization

関連プロジェクト

• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• MuJoCo: DeepMind physics engine for robotics and ML research
• PyBullet: Python physics simulator for robotics and RL research with fast CPU-based simulation
• OpenPI: Physical Intelligence VLA foundation models for general robot control
• Microduck: Pollen Robotics' $399 walking duck robot: open-source software, closed hardware
• Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim

動画

• Markov Decision Processes - Computerphile: Computerphile