からっぽのしょこ

読んだら書く!書いたら読む!同じ事は二度調べ(たく)ない

4.3:方策反復法【ゼロつく4のノート】

はじめに

 『ゼロから作るDeep Learning 4 ――強化学習編』の独学時のまとめノートです。初学者の補助となるようにゼロつくシリーズの4巻の内容に解説を加えていきます。本と一緒に読んでください。

 この記事は、4.3節の内容です。方策反復法の計算式を確認します。

【前節の内容】

www.anarchive-beta.com

【他の記事一覧】

www.anarchive-beta.com

【この記事の内容】

4.3 方策反復法

 前節では、反復方策評価によりある方策における状態価値関数を求めました(方策を評価しました)。この節では、状態価値関数が最大となる行動を取るような方策を得る(方策を改善する)ことを考えます。また、状態価値関数と方策の更新(方策の評価と改善)を繰り返して最適方策を得るアルゴリズム(方策反復法)を確認します。

4.3.1 方策の改善

 方策反復法における方策の更新式を確認します。最適方策については「3.5.2:最適方策【ゼロつく4のノート】 - からっぽのしょこ」を参照してください。

 最適方策$\mu_{*}(s)$は、最適行動価値関数(最適方策における行動価値関数)$q_{*}(s, a)$が最大となる行動$a$を取る関数で、次の式でした(3.5.2項)。

$$ \begin{align} \mu_{*}(s) &= \mathop{\mathrm{argmax}}\limits_a q_{*}(s, a) \tag{3.20}\\ &= \mathop{\mathrm{argmax}}\limits_a \sum_{s'} p(s' | s, a) \Bigl\{ r(s', a, s) + \gamma v_{*}(s') \Bigr\} \tag{3.21} \end{align} $$

 ここで、$v_{*}(s')$は最適価値関数(最適方策における状態価値関数)です。しかし、真の最適方策や真の最適価値関数を直接得ることはできません。

 そこで、現在の方策$\mu(s)$における状態価値関数$v_{\mu}(s)$を用いて、新たな方策$\mu'(s)$を求めます。

$$ \mu'(s) = \mathop{\mathrm{argmax}}\limits_a \sum_{s'} p(s' | s, a) \Bigl\{ r(s', a, s) + \gamma v_{\mu}(s') \Bigr\} \tag{4.7} $$

 この更新式によって、方策を$\mu(s)$から$\mu'(s)$に更新します。この計算(更新手法)は、状態価値関数(または行動価値関数)という「手元にある情報から最善の手を選ぶ」ことから、greedy化と呼ぶことにします(1.3.3項)。また、状態価値関数をgreedy化して得られた方策を、greedyな方策と呼びます。

4.3.2 評価と改善を繰り返す

 「4.1:動的計画法と方策評価【ゼロつく4のノート】 - からっぽのしょこ」や「4.2.3:反復方策評価の実装【ゼロつく4のノート】 - からっぽのしょこ」で確認した「反復方策評価による状態価値関数の更新(方策の評価)」と、4.3.1項で確認した「状態価値関数のgreedy化による方策の更新(方策の改善)」を繰り返すことで、最適方策を求めます。このアルゴリズムを方策反復法と言います。
 この項では、方策反復法の計算を数式で確認します。

 全ての行動で等しい確率などを設定した「確率論的方策の初期値$\pi_0(a | s)$」と、全ての状態で0などを設定した「状態価値関数の初期値$V_0(s)$」を用いて、反復方策評価アルゴリズムによって、状態価値関数の更新値$V_1(s)$を求めます(状態価値関数を更新します)。これを、方策$\pi_0(a | s)$を評価するとも表現します。

$$ V_1(s) = \sum_a \pi_0(a | s) \sum_{s'} p(s' | s, a) \Bigl\{ r(s, a, s') + \gamma V_0(s') \Bigr\} $$

 続いて、1回更新した状態価値関数$V_1(s)$を用いて、greedy化した方策$\mu_1(s)$を求めます(方策を更新します)。これを、方策を改善するとも表現します。

$$ \mu_1(s) = \mathop{\mathrm{argmax}}\limits_a \sum_{s'} p(s' | s, a) \Bigl\{ r(s', a, s) + \gamma V_1(s') \Bigr\} $$

 ここまでが1ステップです。

 2ステップ目では、$a = \mu_1(s)$として(1回更新した決定論的方策$\mu_1(s)$によって行動$a$が決まるとして)、状態価値関数を更新します($\mu_1(s)$を評価します)。

$$ V_2(s) = \sum_{s'} p(s' | s, a) \Bigl\{ r(s, a, s') + \gamma V_1(s') \Bigr\} $$

 1ステップと同様に、更新した状態価値関数を用いて、方策を更新します(改善します)。

$$ \mu_2(s) = \mathop{\mathrm{argmax}}\limits_a \sum_{s'} p(s' | s, a) \Bigl\{ r(s', a, s) + \gamma V_2(s') \Bigr\} $$

 この「方策の評価と改善」の計算を、方策が更新されなくなる($\mu_{k+1}(s) = \mu_k(s)$となる)まで繰り返すことで、最適方策$\mu_{*}(s)$と最適状態価値関数$v_{*}(s)$が得られます。(図4-14での$\pi_k, V_k$の添字$k$の関係とズレてるけど、実装上はこっち↑のようになってると思う。)

 この節では、方策反復法のアルゴリズムの数式上の計算を確認しました。次節では、プログラム上の計算を確認します。

参考文献


おわりに

 数式弄り(変形や導出)はさて置いて、計算式とプログラムって一緒なんだなと感じられると色々楽になれるので、その手助けができれば思ってるのですが中々難しいです。

 例えば、状態価値関数を数式で$V(s)$と書いてきました。これは、状態$s$の価値を表す関数で、$s = L1$や$s = L2$で値が変わりました。プログラムではディクショナリVとして扱い、state = 'L1'のときの状態価値はV[state]で取り出せました。関数と変数の違いはありますが、使ってる記号までほぼ同じです。
 続いて、確率的方策について数式では$\pi(a | s)$と書きました。これは、状態$s$のときに行動$a$を取る確率で、$a = \mathrm{Up}$や$a = \mathrm{Left}$となります。プログラムでは全ての状態の確率がディクショナリpiに格納されており、action_porbs = pi[state]で状態stateのときの各行動の確率を取り出せました。

 こんな感じでプログラムと数式を共通のものとして、プログラミングで数式を理解したり、数式でプログラミングを理解したりできるとより理解が深まるというか深めやすい思います。あぁ数学を味方にしたい、数学の見方をしたい。

【次節の内容】

www.anarchive-beta.com