マルコフ決定過程

【まるこふけっていかてい (Markov decision process)】

概要

状態遷移にマルコフ性をもつ確率システムの動的最適化のための数学モデル. 1960 年にハワードの著書が出版されたことで, 広く知られるようになり, その後, 理論・応用両面で様々な研究がなされている. 最適政策を求める計算アルゴリズムに関しても, 政策反復法, 値反復法(逐次近似法), 線形計画問題として定式化し単体法を用いる解法など, かなり大規模な問題にも耐え得るアルゴリズムが開発されている.

詳説

　マルコフ決定過程 (Markov Decision Process: MDP) は, 待ち行列システムの制御, 在庫管理や, 信頼性システムの保全など, 確率システムの動的な最適化問題を定式化する能力に優れた数学モデルであり, 制御マルコフ過程 (controlled Markov process) とも呼ばれる. MDP は 1960 年にハワード (R. A. Howard) による名著 [3] が出版されたことにより, 広く知られるようになり, その後, 理論・応用・アルゴリズムの各面で膨大な数の多様な研究がなされてきている.

有限マルコフ決定過程　ここでは, 簡単のため, 離散時間の有限 MDP, すなわち状態数およびアクション数が有限のMDP を考える. 有限 MDP$\{{X}_{t}\}\,$ は以下の要素で構成される:

i)　$S:=\{1,2,\cdots ,M\}\,$: 有限状態空間,

ii)　$A(i),i\in S\,$: 状態 $i\,$ でとり得るアクションの有限集合, $\textstyle A:=\bigcup _{i\in S}A(i)\,$: 有限アクション空間,

iii)　$p(j|i,a)\,$, $i\in S\,$; $a\in A(i)\,$: 状態 $i\,$ でアクション $a\,$をとったとき, つぎの時刻で状態 $j\,$ に遷移する確率,

iv)　$c(i,a)\,$, $i\in S\,$; $a\in A(i)\,$: 状態 $i\,$ でアクション $a\,$ をとったときの期待即時コスト.

　各状態でとるべきアクションを規定する規則, すなわち $S\,$ から $A\,$ への写像 $f\,$ で $f(i)\in A(i)\,$, $i\in S\,$ を満たすもの, を政策という. ここでは定常政策, すなわち写像 $f\,$ が時刻 $t\,$ に依存しないもの, だけを考えるが, 下で述べる最適政策は非定常な政策を含む全ての政策の中で最適なものである. 定常政策の全体を $F\,$ で表す.

　最適化すべき計画期間には, 有限計画期間と無限計画期間の2種類があるが, ここでは無限計画期間を考える. また, 政策の評価規範として最も多く採用され, よく研究されているのは, 下で定義される割引きコストと平均コストの 2 種類である. 以下で, $X_{t},A_{t}\,$, $t=0,1,2,\cdots \,$ はそれぞれ時刻 $t\,$ における状態とアクションを表す確率変数とし, $\mathrm {E} _{i,f}[\cdot ]\,$ は初期状態 $i\in S\,$, 政策 $f\in F\,$ のもとでの期待値を表すものとする.

割引きコスト問題　割引き因子を $\beta \in [0,1)\,$ とする無限計画期間上の期待総割引きコスト ($\beta \,$-割引きコスト) :

$u_{\beta ,f}(i):=\mathrm {E} _{i,f}\left[\sum _{t=0}^{\infty }\beta ^{t}c(X_{t},A_{t})\right],\quad i\in S$

を, すべての初期状態 $i\in S\,$ に対し, 最小化する政策 $f\in F\,$ ($\beta \,$-割引き最適政策) を求めよ.

平均コスト問題　無限計画期間における長時間平均の単位時間当り期待コスト (平均コスト) :

$g_{f}(i):=\limsup _{T\to +\infty }{\frac {1}{T+1}}\mathrm {E} _{i,f}\left[\sum _{t=0}^{T}c(X_{t},A_{t})\right]$

を, すべての初期状態 $i\in S\,$ に対し, 最小化する政策 $f\in F\,$ (平均最適政策) を求めよ.

　以下では, 割引きコスト問題において, よく知られている結果を概説しよう. いま最適 $\beta \,$-割引きコスト関数を

$u_{\beta }^{*}(i):=\min _{f\in F}u_{\beta ,f}(i),\quad i\in S$

と定義すると, これは最適性方程式と呼ばれるつぎの関数方程式の一意的な解である:

$u_{\beta }^{*}(i)=\min _{a\in A(i)}\left\{c(i,a)+\beta \sum _{j\in S}p(j|i,a)u_{\beta }^{*}(j)\right\},\quad i\in S.$　　　　　$(1)\,$

各状態 $i\in S\,$ に対して, 最適性方程式 (1) の右辺の $\min \,$ を達成する (任意の) アクションを $f^{*}(i)\in A(i)\,$ で表すと, それらで構成される政策 $f^{*}:=(f^{*}(i);i\in S)\in F\,$ は $\beta \,$-割引き最適政策である.

　最適性方程式 (1) の標準的な数値解法としては, a. ハワードの提案による政策反復アルゴリズム (policy iteration method), b. 値反復アルゴリズム (逐次近似アルゴリズム), c. 線形計画による解法, などが挙げられる. 割引きコスト問題に対する政策反復アルゴリズムは以下の通りである.

[政策反復アルゴリズム]

ステップ 0 (初期化) :　初期政策 $f_{0}\in F\,$ を与える.

ステップ 1 (政策評価) :　現在の政策 $f_{n}\in F\,$ のもとでの $\beta \,$-割引きコスト関数 $u_{\beta ,f_{n}}=(u_{\beta ,f_{n}}(i);i\in S)\,$ を, つぎの線形方程式系を解くことで計算する:

$u_{\beta ,f_{n}}(i)=c(i,f_{n}(i))+\beta \sum _{j\in S}p(j|i,f_{n}(i))u_{\beta ,f_{n}}(j),\quad i\in S.$　　　　　$(2)\,$

ステップ 2 (政策改良) :　不等式

$u_{\beta ,f_{n}}(i)\geq c(i,f(i))+\beta \sum _{j\in S}p(j|i,f(i))u_{\beta ,f_{n}}(j)$　　　　　$(3)\,$

を, すべての状態 $i\in S\,$ に対して成立させ, なおかつ, 少なくとも 1 つの状態では狭義の不等号で成立させる政策 $f\in F\,$ があれば, $f_{n+1}\leftarrow f\,$, $n\leftarrow n+1\,$ としてステップ 1 へ, さもなくば停止. 停止したとき, 最終の $f_{n}\,$ は $\beta \,$-割引き最適な政策である.

　通常, ステップ 2 (政策改良) では, 各状態 $i\in S\,$ において式 (3) の右辺を最小化するアクションをとる政策が新しい政策 $f_{n+1}\,$ として選ばれる.

　政策反復アルゴリズムは高速な解法として広く認められており, その収束に要する反復回数は, 経験的に, 問題の規模にあまり依存しない. この性質は非線形方程式系に対する数値解法であるニュートン・ラフソン法 (Newton-Raphson method) と共通のものであり, この政策反復アルゴリズムはニュートン・ラフソン法を適用することと等価であることが示されている. 政策反復アルゴリズムの弱点はステップ 1 (政策評価) において状態数だけの変数を持つ線形方程式系を解かなければならないことにある. したがって問題の規模が大きくなるにつれてその実行が負担となる. その弱点を克服するため, ステップ 1 を有限回の反復の逐次近似で代用する方法 (修正政策反復アルゴリズム) も提案されている.

　ここでは離散時間の有限 MDP の割引きコスト問題のみを概説したが, a) 他の様々な評価規範, b) 状態空間/アクション空間の一般化, c) 状態遷移の時間間隔が確率的なセミマルコフ決定過程, についても多くの研究がなされている. 実際問題への適用の際に現れる情報の不完全性を明示的に考慮した, d) 不完全観測マルコフ決定過程, e) 遷移確率が未知パラメータを含む適応マルコフ決定過程, に関する研究も歴史が長い. また最近, 複数の評価規範を考慮し, f) すべての評価規範を目的関数として同時に最適化する多目的マルコフ決定過程, g) 一部の評価規範を制約条件に取り入れた制約付きマルコフ決定過程, なども関心を集め, 理論・応用・アルゴリズムの各面に関する活発な研究がなされている.

---

参考文献

[1] D. P. Bertsekas, Dynamic Programming and Optimal Control, Vols. I, II, Athena Scientific, Belmont, Massachusetts, 1995.

[2] O. Hernández-Lerma and J. B. Lasserre, Discrete-Time Markov Control Processes, Basic Optimality Criteria, Springer-Verlag, New York, 1995.

[3] R. A. Howard, Dynamic Programming and Markov Processes, The MIT Press, Cambridge, Massachusetts, 1960.

[4] M. L. Puterman, Markov Decision Processes, John Wiley & Sons, New York, 1994.

[5] S. M. Ross, Introduction to Stochastic Dynamic Programming, Academic Press, New York, 1983.

[6] P. Whittle, Optimization over Times: Dynamic Programming and Stochastic Control, Vols. I, II, John Wiley & Sons, New York, 1983.