逐次意思決定（MDP）

逐次意思決定は、確率的な環境においてエージェントが時間とともにどのように行動すべきかを形式化するものであり、行動が報酬をもたらし、確率的に状態を変化させるマルコフ決定過程を用いて、長期的な期待報酬を最大化する方策を計算する。

Definition

マルコフ決定過程は、状態、行動、遷移確率関数、および報酬関数によって定義される。逐次意思決定は、モデルが与えられた場合に、期待累積（通常は割引された）報酬を最大化する、状態を行動にマッピングする方策を求める。

Scope

このトピックでは、時間を通じた意思決定理論的計画について扱う。具体的には、状態、行動、遷移確率、報酬、割引率からなるマルコフ決定過程（MDP）モデル、方策と価値関数、最適行動を特徴付けるベルマン方程式、および既知のモデルを解くための価値反復法と方策反復法という動的計画法アルゴリズムである。また、部分観測マルコフ決定過程（POMDP）と信念状態計画についても紹介する。焦点は、モデルが与えられた場合の計画にあり、既知のモデルなしに経験から方策を学習することは強化学習に属し、機械学習のサブフィールドである。

Core questions

• 確率的遷移下での時間を通じた行動は、状態、行動、遷移、報酬としてどのようにモデル化されるか？
• ベルマン最適方程式は、最適方策の価値について何を述べているか？
• モデルが既知の場合、価値反復法と方策反復法はどのように最適方策を計算するか？
• 部分観測性はどのようにPOMDPと信念状態上の計画につながるのか？

Key concepts

• 状態、行動、遷移、報酬
• 方策
• 価値関数
• 割引因子
• ベルマン方程式
• 価値反復法
• 方策反復法
• POMDPと信念状態

Key theories

ベルマン最適方程式

ある状態の最適価値は、最良の即時報酬と、次の状態の割引された期待最適価値の合計に等しい。この再帰的な関係は、最適な逐次行動を特徴付け、動的計画法による解法の基礎となる。

価値反復法と方策反復法

既知のMDPの場合、価値反復法は収束するまでベルマン更新を繰り返し適用し、方策反復法は方策評価と改善を交互に行う。どちらも最適方策を見つけることが保証されている。

部分観測マルコフ決定過程

状態が直接観測できない場合、計画は観測から更新される信念状態（状態の分布）上で行われる。このようなPOMDPを解くことは、完全に観測可能な場合よりもはるかに困難であるが、現実的なセンシングの限界を捉えている。

Clinical relevance

MDPおよびPOMDPに基づく意思決定は、ロボットのナビゲーションと制御、自動対話管理、保守および在庫の決定、資源配分などの基盤となり、環境モデルを学習する必要がある場合に強化学習が構築される意思決定理論的計画の基礎を提供する。

History

逐次意思決定は、ベルマンの動的計画法（1957年）とハワードの方策反復法（1960年）から発展した。プッターマンの1994年のモノグラフはマルコフ決定過程の理論を統合し、カエルブリング、リットマン、カサンドラ（1998年）は、不確実な知覚下での行動モデルとして部分観測マルコフ決定過程を主流のAIにもたらした。

Key figures

• Richard Bellman
• Ronald A. Howard
• Martin L. Puterman
• Leslie P. Kaelbling
• Michael L. Littman

Seminal works

• bellman1957
• puterman1994
• kaelbling1998

Frequently asked questions

これは強化学習とどう違うのか？

MDPを用いた逐次意思決定では、遷移モデルと報酬モデルが既知であると仮定されるため、動的計画法によって最適方策を直接計算できる。強化学習は、モデルが未知であり、エージェントが経験から良い方策を学習しなければならないケースを扱い、その基礎となる形式主義としてMDPを使用する。

POMDPにおける信念状態とは何か？

部分観測マルコフ決定過程では、エージェントは真の状態を直接見ることができないため、信念状態、つまり可能な状態の確率分布を維持し、行動を取り観測を受け取るたびにこれを更新する。計画は、隠れた状態を直接扱うのではなく、これらの信念状態上で行われる。