マルコフ決定過程 マルコフ決定過程の概要

ウィキペディア

マルコフ決定過程

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/06 03:52 UTC 版)

概要

3つの状態と2つの行動をもつ簡単な MDP の例

マルコフ決定過程は離散時間における確率制御過程 (stochastic control process) である。 各時刻において過程 (process) はある状態 (state) を取り、意思決定者 (decision maker) はその状態において利用可能な行動 (action) を任意に選択する。 その後過程はランダムに新しい状態へと遷移し、その際に意思決定者は状態遷移に対応した報酬 (reward) を受けとる。

遷移後の状態 ${\displaystyle s'}$ 、および得られる報酬の値 ${\displaystyle r}$ は現在の状態 ${\displaystyle s}$ と行動 ${\displaystyle a}$ のみに依存し、${\displaystyle s}$ と ${\displaystyle a}$ が与えられたもとでそれより過去の状態および行動と条件付き独立となる。 言い換えると、マルコフ決定過程の状態遷移はマルコフ性を満たす。

マルコフ決定過程はマルコフ連鎖に（選択可能な）行動、および（行動を計画する動機を与える）報酬を追加し拡張したものであると解釈できる。 逆に言えば、各ステップにとる行動がそのステップにおける状態のみ依存するとき、マルコフ決定過程は等価なマルコフ連鎖に置き換えることが出来る。

定義

有限マルコフ決定過程 (finite Markov decision process; finite MDP) は4つの要素の組 ${\textstyle {\big \langle }S,A,T,R{\big \rangle }}$で表される。ここで各要素はそれぞれ次を意味する。

• ${\displaystyle S=\{s^{1},s^{2},\ldots ,s^{N}\}}$ : 状態の有限集合
• ${\displaystyle A=\{a^{1},a^{2},\ldots ,a^{K}\}}$ : 行動の有限集合
• ${\displaystyle T:S\times A\times S\to [0,1]}$ : 遷移関数 (transition function)
• ${\displaystyle R:S\times A\times S\to \mathbb {R} }$ : 報酬関数 (reward function)

遷移関数 ${\displaystyle T(s,a,s')}$ は状態 ${\displaystyle s}$ にあり行動 ${\displaystyle a}$ を取ったときの状態 ${\displaystyle s'}$ への状態遷移確率 ${\displaystyle T(s,a,s')=\Pr(s_{t+1}=s'|s_{t}=s,a_{t}=a)}$ である。 また報酬関数 ${\displaystyle R(s,a,s')}$ は状態 ${\displaystyle s}$ から ${\displaystyle s'}$ に行動 ${\displaystyle a}$ を伴い遷移する際に得られる即時報酬 (immediate reward) 、またはその期待値 ${\displaystyle \mathbb {E} [r_{t+1}|s,a,s']}$ を表す。

問題設定

MDP における基本的な問題設定は、現在の状態が ${\displaystyle s}$ が与えられたときに意思決定者の取る行動 ${\displaystyle a\in A}$ を既定する方策 (policy) を求めることである。 方策は通常 ${\displaystyle s,a}$ の条件付き分布 ${\displaystyle P(a|s)}$ として規定され、状態 ${\displaystyle s}$ に 行動 ${\displaystyle a}$ を取る確率を ${\displaystyle \pi (s,a)}$ と表記する。

方策を求める際に用いられるゴール（目的関数）は、典型的には現在時刻から無限区間先の未来までにおける「割引された」報酬の累積値が用いられる:

$${\displaystyle \sum _{t=0}^{\infty }\gamma ^{t}r_{t+1}\quad {\text{where}}\ a_{t}=\pi (s_{t})}$$

ここで ${\displaystyle \gamma \in [0,1]}$ は割引率 (discount rate) と呼ばれる値であり、現在の報酬と未来の報酬との間における重要度 (importance) の差異を表している。 状態が確率的に遷移することから上の値は確率変数となるため、通常はその期待値が用いられる。