マルコフ決定過程（MDP）は、結果が不確実な状況での逐次的意思決定のための数学的モデルである。これは確率的決定過程の一種であり、しばしば確率的動的計画法の手法を用いて解かれる。1950年代のオペレーションズ・リサーチに起源を持ち、その後、生態学、経済学、医療、電気通信、強化学習などの分野で認識を得てきた。強化学習において、MDPフレームワークは学習エージェントと環境との相互作用をモデル化し、状態、行動、報酬によって特徴づけられ、人工知能の主要な要素である因果関係、不確実性、明示的な目標の簡略化された表現を提供する。
この名称は、ロシアの数学者アンドレイ・マルコフによって開発されたマルコフ連鎖との関連に由来する。「マルコフ」という性質は、状態遷移が現在の状態と行動のみに依存し、過去の履歴には依存しないという構造を指す。「決定過程」と呼ばれるのは、これらの遷移に影響を与える決定を行うことを含むためであり、マルコフ連鎖を不確実性の下での意思決定に拡張したものである。
正式な定義
MDPは通常、4つの組 \((S, A, P_a, R_a)\) として定義される。ここで：
- \(S\) は状態空間であり、離散または連続（例えば、実数の集合）であり得る。
- \(A\) は行動空間であり、状態 \(s\) から利用可能な行動の集合 \(A_s\) を持つ。この集合も離散または連続であり得る。
- \(P_a(s, s')\) は、時刻 \(t\) に状態 \(s\) で行動 \(a\) を取ったときに、時刻 \(t+1\) で状態 \(s'\) に遷移する確率である。離散状態の場合、\(P_a(s, s') = \Pr(s_{t+1} = s' \mid s_t = s, a_t = a)\) と表される。連続状態空間の場合、確率はルベーグ測度に関する積分として定義されることが多い。
- \(R_a(s, s')\) は、状態 \(s\) から \(s'\) への遷移で行動 \(a\) を取った後に得られる即時報酬（または期待報酬）である。報酬は一般に確率変数である。
方策関数 \(\pi\) は、状態空間から行動空間への（潜在的に確率的な）写像であり、各状態でどの行動を取るかを指定する。
最適化の目的
MDPの目標は、累積報酬の関数、典型的には無限期間にわたる期待割引報酬和 \(\mathbb{E}[\sum_{t=0}^{\infty} \gamma^t R_{a_t}(s_t, s_{t+1})]\) を最大化する方策 \(\pi\) を見つけることである。ここで \(\gamma \in [0, 1)\) は割引因子である。方策が固定されると、MDPはマルコフ連鎖のように振る舞う。なぜなら、各状態での行動が \(\pi(s)\) によって決定されるからである。
一般的な解法には、値反復法や方策反復法などの動的計画法の手法があり、これらは最適な価値関数や方策を計算する。これらの手法は、Q学習やSARSAなどの強化学習アルゴリズムの基礎となっている。
応用
MDPはさまざまな分野で広く応用されている。経済学では、最適な消費・投資決定をモデル化する。医療では、慢性疾患管理などの不確実性の下での治療計画を導く。電気通信では、リソース割り当てやネットワークルーティングを最適化する。生態学では、種の管理のための保全戦略を提供する。機械学習では、MDPは強化学習の中心であり、ロボット工学、ゲームプレイ、自動運転などの応用において、エージェントが環境との相互作用から学習することを可能にする。
強化学習との関係
強化学習（RL）は、MDPフレームワークを使用してエージェントと環境の相互作用を形式化する。RLでは、エージェントは遷移確率や報酬関数を事前に知らない。代わりに、環境からのサンプルを用いた試行錯誤を通じて最適な方策を学習する。これは、モデルパラメータが既知であると仮定する古典的なMDP解法とは異なる。現代のRLは、深層強化学習を含み、MDPをニューラルネットワーク関数近似器と組み合わせて、大規模な状態空間を扱う。これは、ゲームプレイや自動運転などの応用で実証されている。
拡張と変種
基本的なMDPの限界に対処するためのいくつかの拡張が存在する。部分観測マルコフ決定過程（POMDP）は、エージェントが完全な状態を直接観測できない状況を扱う。因子化MDPは、状態変数の構造を利用してスケーラビリティを向上させる。マルチエージェントMDPは、相互作用する複数の意思決定者を持つフレームワークに拡張する。これらの変種は、コアのマルコフ性を保持しつつ、より複雑な現実世界の問題に適応する。
歴史的文脈
MDPの形式化は、1950年代にリチャード・ベルマンによってなされ、彼は動的計画法も開発した。アンドレイ・マルコフによる確率過程に関する初期の研究は理論的基盤を提供した。それ以来、MDPはオペレーションズ・リサーチと人工知能の基礎となり、逐次的意思決定における理論的および応用的研究の両方に影響を与えてきた。