はじめに

今回は、強化学習における最も重要な考え方の１つであるマルコフ決定過程について整理していきます．

目標

マルコフ決定過程の概要を理解する

マルコフ決定過程（Markov Decision Processes）

強化学習の枠組み（再掲）

f:id:shirakonotempura:20190122035140p:plain

マルコフ決定過程の説明に先立ち、強化学習フレームワークにおける用語とその意味について再度示します．

エージェントと環境は、 $t = 0, 1, 2, \dots$ において、相互に影響を及ぼします

エージェントはステップ $t$ ごとに状態 $S_t$ を獲得
ステップtにおける行動 $A_t$ を実行する
行動 $A_t$ によって、報酬 $R_{t+1}$ を得る
行動 $A_t$ によって、状態が $S_t$ から $S_{t+1}$ に変化する

強化学習のシステムは以下のように表されます． f:id:shirakonotempura:20190126033017p:plain

マルコフ決定過程

強化学習のタスクが、マルコフ性を満たす場合、そのタスクはマルコフ決定過程（Markov decision process，MDP）と呼ばれます．もし、行動と状態が有限であるなら、有限マルコフ決定過程と呼ばれます（Finite MDP）．

マルコフ決定過程のタスクにおいて、次の状態は、現在の状態Sと行動Aによって確率的に決定されます．その確率は、エージェントが状態sにおいて行動aを決定したとき、状態sが状態s'に遷移する確率として以下の用に表されます．

$$P(s' | s, a)$$

例えば、マルコフ決定過程のもとではt+1ステップ目における状態 $S_{t+1}$ はtステップ目の状態 $S_t$ と、その状態で選ばれた行動 $A_t$ により、以下のように求めることができます．

$$S_{t+1} \sim P(s' | S_t, A_t)$$

このとき[tex:S{t+1}]は[tex:S{t-1}]や $A_{t-1}$ などには依存せず、 $S_t$ と $A_t$ のみに依存して定まることに注意が必要です．このように直前の状態によってのみ遷移確率が決まる性質のことをマルコフ性（The Markov Property）と言います．（この性質があるタスクは、マルコフ決定過程のタスクとして考えられるといった方が正しいと思います．）

また、現在の状態 $S_t$ と行動 $A_t$ および次の状態[tex:S{t+1}]に応じて、報酬[tex:R{t+1}]を次のように定めます．

$$R_{t+1} = r (S_t, A_t, S_{t+1})$$

報酬と収益（Rewards and Returns）

以前述べたように、強化学習の目的は長期的な報酬を最大化することである．すなわち、[tex: R{t+1}, R{t+2}, R_{t+3} \dots]を最大にする行動 $A_t$ を選択することです．

しかし、将来的に得られるであろう報酬と、今得られる報酬では後者に重みをおく方が現実的だと言えます．そこで、割引率（discount rate）を用いて、将来得られる報酬を割り引く方法がよく用いられます．割引率 $\gamma$ （ $\gamma \in [0, 1)$ ）を考慮した時刻tの収益 $G_t$ は以下のように表されます．