はじめに
強化学習における動的計画法、TD学習(Sarsa、Q学習）、モンテカルロ法についての記事です。
マルコフ決定過程
マルコフ決定過程とはある状態があった時に今の状態や行動だけで次の行動を選ぶことできることを言います。過去の状態や過去からの報酬は気にしないということです。
なので迷路問題などでは右側に壁がある状態があったときにゴール付近でもスタート付近にいてもどちらでも同じ状態だと認識してしまいます。（過去の状態を考慮しないため）
動的計画法
最適化の１つで問題をいくつかに分割して行う手法のこと。
モンテカルロ法
モンテカルロ法はエピソードがすべて終わってから報酬を受け取れる。なのでエピソードが終了してから方策や報酬の更新が行われる。
TD学習
目標と現在の状態の価値のずれを修正することによって価値関数を改善することを指す。この現在のずれのことをTD誤差といいます。
TD学習はモンテカルロ法や動的計画法のようにエピソードが終了せずとも方策や報酬を受け取ることができる。
具体的にはSarsaとQ学習がある。
Sarsa
Q(s_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]
Sarsaは安全な経路を選択していきます。つまり方策オン型の更新式です。行動価値を更新するときはQ学習に比べて行動価値が小さい探索が結果として反映しれやすい。
Q学習
Q(s_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma max_{\alpha'} Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]
Q学習は方策オフ型の探索を行う。いわゆるmaxなので最短経路を選択します。Sarsaは崖など最短経路上に何かしらの障害物があればそれを避けて通ります。しかしＱ学習はmaxなので最短経路となる場所を選択して行ないます。
ちなみにɤは割引率を表しています。この式をより具体的に説明すると今の価値Ｑは状態Ｓのときに行動Ａを選んだ価値です。そして次の報酬がＲになっています。そこに割引率ɤを掛けた次の価値が最大になるような行動と状態を選ぶことが目標です。TD学習は目標と現在の状態の誤差のTD誤差を最小にするような価値をみつける学習です。なので[]の中身を最小目標に近づけるような学習が必要です。
ちなみにＱ学習は行動を決定する方策と行動価値関数の更新に利用される方策が異なります。