マルコフ決定過程とは?

Weblio 辞書 > 同じ種類の言葉 > 人文 > 高等数学 > 過程 > マルコフ決定過程の意味・解説 

マルコフ決定過程

読み方まるこふけっていかてい
【英】:Markov decision process

概要

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

詳説

 マルコフ決定過程 (Markov Decision Process: MDP) は, 待ち行列システム制御, 在庫管理や, 信頼性システム保全など, 確率システム動的最適化問題定式化する能力優れた数学モデルであり, 制御マルコフ過程 (controlled Markov process) とも呼ばれる. MDP1960 年ハワード (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.


マルコフ決定過程

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2017/01/29 00:17 UTC 版)

マルコフ決定過程 (マルコフけっていかてい、Markov Decision Process; MDP) は、状態遷移が確率的に生じる動的システム(確率システム)の確率モデルであり、状態遷移がマルコフ性を満たすものをいう。 MDP は不確実性を伴う意思決定のモデリングにおける数学的枠組みとして、強化学習など動的計画法が適用される幅広い最適化問題の研究に活用されている。 MDP は少なくとも1950年代には知られていた[1]が、研究の中核は1960年に出版された Ronald A. Howard の "Dynamic Programming and Markov Processes" に起因する[2]。 MDP はロボット工学や自動制御、経済学製造業を含む幅広い分野で用いられている。




「マルコフ決定過程」の続きの解説一覧



マルコフ決定過程と同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

「マルコフ決定過程」の関連用語

マルコフ決定過程のお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング



マルコフ決定過程のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2019 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのマルコフ決定過程 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2019 Weblio RSS