今更ながら方策反復（Policy iteration）を勉強（実装）してみた

　こんばんは，大学院に進学してから本格的に機械学習の勉強をし始めました．その学習記録を残そうかなと思います．まぁ，自分で実装したアルゴリズムとかだけを書いていくつもりです．
　今回は，強化学習をやっている人なら誰しも目を通したことがあるはずのSutton本から方策反復（※方策勾配法じゃないよ）の説明と実装を共有しようと思います．なんで方策反復かというと調べてパッと出て来なかったっていう理由です（笑）
　強化学習の基礎はわかっているという前提で話を進めていきます．強化学習については調べたら色々Webページが出てくるので，それを見てください．下記の記事なんかいいじゃないでしょうか？方策反復(Policy iteration)についてざっくり触れられています．

qiita.com

方策反復(Policy iteration)とは？
用語の定義
方策反復(Policy iteration)の手続き
- 方策評価とは？
- 方策更新とは？
実装コード
実行結果
おわりに
参考文献

方策反復(Policy iteration)とは？

　有限MDP（マルコフ決定過程）が与えられた時に，方策の評価と方策の更新を繰り返し行い，最適な方策を得るアルゴリズムのことです．動的計画法の一種で，計算結果をメモリで保持しながら繰り返し計算を行います．現在の一般的な強化学習は，MDPに関する情報を完全には必要としないのですが，今回の方策反復はMDPの情報を完全に必要とします．Model-basedな手法であるとも言えます（最近よく聞くModel-basedな手法はモデルの完全な情報が所与ではなく，モデル自体の学習と方策の学習の両方を行うので，区別してください）．有限MDPの情報を完全に必要とするということがどういうことかというと，報酬関数 $R(s,a,s')$ と状態遷移関数 $P(s,a,s')$ が完全にわかっている（入力として与えられる）ということを意味しています．これらの情報が自明であれば，動的計画法を用いて最適な方策を求めることができます．
　今回はエピソード的タスクで，特殊な状態（終端状態）をもつタスクを考え，強化学習の文脈で（昔は）よく使われた迷路問題を扱います．

用語の定義

　アルゴリズムの説明の前に今後使用する変数や関数を表す表記，タスクの定義をしておきます．まず，変数や関数の定義は以下の通りです．

表記	意味
$a \in A$	行動集合 $A$ に含まれる行動
$s \in S$	状態集合 $S$ に含まれる状態
$s' \in S^{+}$	終端状態を含む状態集合[tex: S^{+}から得られる状態
$r_{t}$	$t$ ステップで得られた報酬
$\pi(a\|s)$	状態 $s$ で行動 $a$ を取る確率．これが方策
$\mathbb{E}_{\pi}$	方策 $\pi$ の元での期待値
$v$	状態価値関数

　次に，タスクについてです．扱う迷路問題は以下のような迷路です．Sutton本に書かれているのと同じ形式です．

f:id:kerneltyu:20180610235202p:plain

　上図に示した通り，行動は上下左右の4つが可能であり，各マスが状態を示しており，1-14が各状態の識別子として割り振られています．色付きのマスが終端状態であり，図には書かれていませんが，それぞれ0と15とナンバリングをします．Sutton本では，全ての遷移（状態からの行動）に対して-1の報酬が獲得されるという設定です．しかし，今回は終端状態への遷移で+1の報酬が獲得され，それ以外は報酬が獲得されないという設定にします．どちらの報酬設定でも良いのですが，ちょっと変えてみました．方策は決定的であるとします．
　さて，この迷路問題タスクにおいてそれぞれの（終端状態以外の）状態から終端状態に到達するまでの最短経路を導く方策を導きます．

方策反復(Policy iteration)の手続き

　方策反復の具体的な手続きについて見ていきます．早速いかに，疑似コードを示します．Sutton本からの引用です．

f:id:kerneltyu:20180611194211p:plain

　方策反復は大きく3つのステップに分かれます．初期化(Initialization)と方策評価(Policy evaluation)と方策更新(Policy improvement)です．初期化では，状態価値関数と方策の初期化を行います．実装ではどちらとも $\mathbf{0}$ で初期化しました．方策反復では，方策の更新がされなくなるまで繰り返し，方策評価と方策更新を繰り返します．方策評価では，更新量 $\delta$ が $\theta$ よりも小さくなるまで，全状態の状態価値関数 $V(s)$ の更新を繰り返し行います．方策更新では，すべての状態に対して，行動の価値 $\sum_{s',r} p(s',r|s,a)[r+\gamma V(s')$ ] が最も大きい行動を状態 $s$ における行動 $a$ として更新を行います．

方策評価とは？

f:id:kerneltyu:20180611214141p:plain
　方策評価とは字面の通り，方策を評価する手続きのことを指します．方策の評価は，状態価値関数$V(s)$を更新することによって行います．なぜ状態価値関数の更新が方策の評価になるのかというと，方策が状態価値関数によって決定づけられるからです．これについては方策更新の項目で説明をします．
　ここでは，方策評価における状態価値関数の導出について説明します．そもそも強化学習は期待報酬を最大化するような方策を学習することが目的である枠組みです．期待報酬は，状態価値関数 $V(s)$ や行動価値関数 $Q(s,a)$ （いわゆるQ値）の形で表されます．ここで方策 $\pi$ で得られる状態価値関数を $v_{\pi}(s)$ とすると，
$$ \begin{align} v_{\pi}(s) &= \mathbb{E}_{\pi}[G_t|S_t=s] \\ &= \mathbb{E}_{\pi}[R_{t+1}+\gamma G_{t+1}|S_t=s] \\ &= \mathbb{E}_{\pi}[R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_t=s] \\ &= \sum_{a} \pi(a|s) \sum_{s',r} p(s', r|s,a)[r+\gamma v_{\pi}(s')] \end{align} $$

　上記のような式を得ることができます．ここで，決定的でない方策 $\pi(a|s)$ の場合は確率値をとるのですが，今回は決定的な方策 $\pi(s)$ を考えるので，導出した式は以下のように書き変わります． $$ \begin{align} v_{\pi}(s) &= \mathbb{E}_{\pi}[R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_t=s] \\ &= \sum_{s',r} p(s', r|s,a)[r+\gamma v_{\pi}(s')] \end{align} $$ 　期待値計算で行動の確率値を考える必要がなくなったということです．この式が先ほど示した状態価値関数の更新で用いられている式を表しています．ここでこの更新の意味を考えてみると方策を更新する前の状態価値関数を更新後の方策 $\pi(s)$ を取った時に得られる状態価値関数に更新するために繰り返し計算していることになります．

方策更新とは？

f:id:kerneltyu:20180611214145p:plain
　方策更新は，先ほど説明した方策評価で得られた状態価値関数 $v_{\pi}(s)$ でgreedyになるような方策に更新する手続きです．ここで，行動価値関数について少しふれておきます．行動価値はある行動 $a$ をとった時の期待報酬を表しています．状態価値との違いとしては，行動 $a$ をとった時というところです．状態価値は，状態 $s$ でとれる行動すべてを考慮しなければなりませんでしたが，行動価値は，状態 $s$ で行動 $a$ を取った時のみを考慮します．すなわち状態 $s$ で行動 $a$ を取った時の期待報酬を表しています．この行動価値によって行動 $a$ がどれほど良いかを測ることができます．行動価値関数 $q(s,a)$ を以下に示します． $$ \begin{align} q_{\pi}(s,a) &= \mathbb{E}[R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_t=s, A_{t}=a] \\ &= \sum_{s',r} p(s', r|s,a)[r+\gamma v_{\pi}(s')] \end{align} $$ 実はさっき示した決定的な方策をとった時の状態価値関数とほとんど同じなんですよね(笑)．でも，行動 $a$ か方策 $\pi(s)$ かが違います．よく見てください．この行動価値関数が，方策更新では使われます．方策を更新している個所を見ると，状態 $s$ において可能な行動 $a$ の行動価値関数で最も大きい行動価値を得ることのできる $a$ を方策として採用しています．
　これでなんで最適な方策が得られるのとかはSuttonの本を読んでください．参考文献で示します．

実装コード

実装では，下記のページでOpenAiGymをベースにした迷路問題を用いていたのでそれを参考にさせていただきました．というよりここで方策反復が触れられてなかったからこのブログ書いたまである．

qiita.com

コードは僕のGitHubにあります！

実行結果

f:id:kerneltyu:20180611230343p:plain

　上記のような結果が得られるかと思います．迷路問題と初期の状態価値関数，初期の方策，学習後の状態価値関数，学習後の方策を示しています．学習後の状態価値関数を見ると終端状態に近いほど高い状態価値が得られていることがわかります．学習後の方策ではどの状態からスタートしたも終端状態に最短距離で到達することが確認できると思います．
　コードを少しいじれば5×5迷路問題と拡張できると思います．更新で全状態と全行動に対して計算を行うので少なくとも $O(|S||A|)$ の計算量がかかるので迷路のサイズをあまり大きくしすぎると計算が終わらないと思います．

おわりに

以上，方策反復について解説してみました．疲れた...けど楽しいですね！今後も書いていけたらなと思います．間違いとかあれば気軽に指摘してください(^^)b

参考文献

[1] Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction Second edition, http://incompleteideas.net/book/bookdraft2017nov5.pdf, 2018/6/11参照.
[2] @neka-nat, 逆強化学習を理解する, https://qiita.com/neka-nat@github/items/aaab6184aea7d285b103, 2018/6/11 参照.

kerneltyu’s tech blog

理系学生です．