マルコフ決定過程（Markov Decision Process, MDP）は、エージェントが状態の遷移と報酬を通じて環境と相互作用する逐次的意思決定問題を数学的にモデル化した枠組みである。状態、行動、遷移確率、報酬関数、割引率の五つの要素から構成され、エージェントは累積報酬を最大化する最適政策を探索する。強化学習やオペレーションズリサーチの基礎として広く応用される。
1 定義と基本要素
マルコフ決定過程は、強化学習や逐次的意思決定問題の数学的基盤を提供するフレームワークである。以下の五つの要素によって定義される。
1.1 状態空間と行動空間
状態空間はエージェントが認識可能なすべての状態の集合であり、行動空間は各状態においてエージェントが選択可能な行動の集合である。状態空間と行動空間は有限または無限であり、離散または連続であり得る。エージェントは現在の状態に基づいて行動を選択する。
1.2 遷移確率
| 遷移確率は、現在の状態と選択された行動に基づいて、次の状態が決定される確率的な分布を表す。マルコフ性により、次の状態は現在の状態と行動のみに依存し、過去の履歴には依存しない。遷移確率はP(s' | s, a)と表記される。 |
|---|
1.3 報酬関数
報酬関数は、エージェントがある状態で行動を実行した直後に得られる即時的な報酬を定義する。報酬は実数値で与えられ、エージェントの目標は累積報酬を最大化することである。報酬関数はR(s, a)またはR(s, a, s')として表現される。
1.4 割引率とエピソード長
割引率は将来の報酬の現在価値を調節するパラメータであり、0から1の間の値をとる。割引率が0に近いほど即時報酬を重視し、1に近いほど将来の報酬を重視する。エピソード長は、問題が有限時間のエピソードで構成されるか、無限時間の継続的タスクであるかを示す。
2 政策と価値関数
政策はエージェントの行動選択の戦略を規定する。価値関数は、ある政策に従った場合の期待累積報酬を評価する。
2.1 政策の定義と種類
政策は、各状態においてエージェントがどの行動を選択するかのルールである。政策は状態から行動への写像として定義される。
2.1.1 決定論的政策と確率論的政策
決定論的政策は、各状態に対して一意の行動を割り当てる。一方、確率論的政策は、各状態において行動の確率分布を返し、複数の行動を確率的に選択することを許容する。
2.2 状態価値関数
状態価値関数V(s)は、状態sから開始し、政策πに従った場合の期待累積報酬を表す。これは政策の性能を評価する指標として用いられる。
2.2.1 ベルマン方程式
| ベルマン方程式は、状態価値関数に関する再帰的な関係式である。V(s) = Σ_a π(a | s) Σ_{s'} P(s' | s,a) [R(s,a,s') + γ V(s')] と表される。この方程式は動的計画法や強化学習アルゴリズムの基礎となる。 |
|---|
2.3 行動価値関数
| 行動価値関数Q(s, a)は、状態sで行動aを選択し、その後政策πに従った場合の期待累積報酬を表す。Q(s, a) = Σ_{s'} P(s' | s,a) [R(s,a,s') + γ V(s')] と定義される。 |
|---|
3 最適性の概念
最適性は、エージェントが達成可能な最大の累積報酬を得るための基準を提供する。
3.1 最適政策
最適政策π*は、すべての状態において他のどの政策よりも高い価値関数を与える政策である。最適政策は一意であるとは限らないが、最適価値関数は一意に定まる。
3.2 ベルマン最適方程式
| ベルマン最適方程式は、最適価値関数V*に関する自己無撞着的な方程式である。V*(s) = max_a Σ_{s'} P(s' | s,a) [R(s,a,s') + γ V*(s')] と表される。この方程式は最適政策の導出に用いられる。 |
|---|
3.3 価値反復法
価値反復法は、ベルマン最適方程式を用いて価値関数を反復的に更新し、最適価値関数に収束させるアルゴリズムである。各更新で最大値を取るため、計算効率が良い。
3.4 政策反復法
政策反復法は、政策評価と政策改善を交互に繰り返すアルゴリズムである。政策評価で現在の政策の価値関数を計算し、政策改善でより良い政策を導出する。このプロセスは最適政策に収束する。
4 解法とアルゴリズム
マルコフ決定過程の解法には様々なアルゴリズムが存在する。
4.1 動的計画法
動的計画法は、遷移確率と報酬関数が既知の環境で最適政策を計算する手法である。価値反復法や政策反復法が代表例であり、モデルベースの解法として分類される。
4.2 モンテカルロ法
モンテカルロ法は、実際の経験から報酬の平均を計算することで価値関数を推定する手法である。完全なエピソードのデータを必要とし、モデルフリーな学習が可能である。
4.3 時間差学習法
時間差学習法は、モンテカルロ法と動的計画法の中間的な手法であり、ブートストラッピングを用いて価値関数を逐次的に更新する。SARSAやQ学習が代表的なアルゴリズムである。
4.4 線形計画法による解法
線形計画法は、マルコフ決定過程を線形制約付き最適化問題として定式化し、線形計画ソルバーを用いて最適政策を求める手法である。状態空間や行動空間が小規模な場合に有効である。
5 応用分野
マルコフ決定過程は多様な実世界の問題に応用されている。
5.1 ロボティクス
ロボティクス分野では、MDPは環境と相互作用するロボットの意思決定をモデル化するために用いられる。
5.1.1 経路計画
経路計画では、ロボットが障害物を回避しながら目標位置に到達するための行動系列をMDPとして定式化する。遷移確率には動作の不確実性が考慮される。
5.2 ゲーム理論と人工知能
ゲーム理論において、MDPは複数のエージェントが相互作用する環境での戦略学習に利用される。人工知能では、AlphaGoなどのシステムがMDPの枠組みを応用している。
5.3 オペレーションズリサーチ
オペレーションズリサーチでは、資源配分や生産計画などの最適化問題にMDPが適用される。
5.3.1 在庫管理
在庫管理では、需要の不確実性を考慮した発注量の最適化をMDPとしてモデル化し、期待利益を最大化する政策が導かれる。
6 発展的トピック
マルコフ決定過程は様々な拡張が研究されている。
6.1 部分観測マルコフ決定過程
部分観測マルコフ決定過程は、エージェントが状態を直接観測できず、観測に基づいて信念状態を更新する拡張である。これにより、不完全情報下での意思決定が可能となる。
6.2 多エージェントマルコフ決定過程
多エージェントマルコフ決定過程は、複数のエージェントが同時に環境と相互作用する状況を扱う。
6.2.1 協調と競合
多エージェント設定では、エージェント間の協調または競合が問題となる。協調では共有報酬を最大化し、競合では各エージェントが個別の報酬を最大化する。
6.3 深層強化学習との関連
深層強化学習は、深層ニューラルネットワークを用いて価値関数や政策を近似することで、高次元の状態空間や行動空間を扱う。MDPは深層強化学習の理論的基盤を提供している。