4.5.1：価値反復法の導出【ゼロつく4のノート】

はじめに

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

　この記事は、4.5.1節の内容です。価値反復法のアルゴリズムを導出します。

【前節の内容】

www.anarchive-beta.com

【他の記事一覧】

www.anarchive-beta.com

【この記事の内容】

4.5.1 価値反復法の導出

　前節の方策反復法では、1回の評価と改善において、全ての状態価値関数を収束するまで(最大限)更新して方策を更新しました。価値反復法では、1つの状態価値関数を1回(最小限)更新して方策を更新します。4.5.2項で実装するプログラムでは、全ての状態価値関数を1回更新して方策を更新ます。
　この項では、価値反復法を用いて最適方策を得るためのアルゴリズムを導出します。反復方策評価アルゴリズムについては「4.1：動的計画法と方策評価【ゼロつく4のノート】 - からっぽのしょこ」や「4.2.3：反復方策評価の実装【ゼロつく4のノート】 - からっぽのしょこ」、greedyな方策と方策反復法の計算式については「4.3：方策反復法【ゼロつく4のノート】 - からっぽのしょこ」を参照してください。

　反復方策評価アルゴリズムによる状態価値関数の更新式は、次の式でした(4.1.1項)。

$$ V(s) = \sum_a \pi(a | s) \sum_{s'} p(s' | s, a) \Bigl\{ r(s, a, s') + \gamma V_0(s') \Bigr\} \tag{4.9} $$

　ここで、$\gamma$は割引率で、状態価値関数の初期値を$V_0(s)$で表します。
　次の式で、状態価値関数$V(s)$をgreedy化して方策を得ます(4.3.1項)。

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

　$\mathrm{argmax}_a$は、右辺が最大となる$a$を意味します。
　greedyな方策(決定論的方策)$\mu(s)$を用いると状態価値関数の更新式は、次の式になります。

$$ \begin{aligned} a &= \mu(s) \\ V'(s) &= \sum_{s'} p(s' | s, a) \Bigl\{ r(s, a, s') + \gamma V(s') \Bigr\} \end{aligned} \tag{4.10} $$

　ここまでは、方策反復法と同じ計算です。

　greedyな方策により行動が1つに固定されたことで、状態価値関数は行動価値関数

$$ q_{\mu}(s, a) = \sum_{s'} p(s' | s, a) \Bigl\{ r(s, a, s') + \gamma V(s') \Bigr\} \tag{3.13} $$

と同じ式になります(3.3節)。また、方策の更新式(4.8)の一部とも一致します。
　よって、方策$\mu(s)$の計算式(4.8)は、$\mu(s)$を取るときの行動価値関数$q_{\mu}(s, a)$で表せます。

$$ \mu(s) = \mathop{\mathrm{argmax}}\limits_a q_{\mu}(s, a) \tag{4.8'} $$

　この式は、$q_{\mu}(s, a)$が最大となる行動$a$を取ることを意味します。
　同様に、状態価値関数の(2つの)計算式(4.10)も、$q_{\mu}(s, a)$に置き換えられます。

$$ \begin{aligned} a &= \mu(s) \\ V'(s) &= q_{\mu}(s, a) \end{aligned} \tag{4.10'} $$

　改善フェーズ(4.8')では$q_{\mu}(s, a)$が最大となる$a$を取り、評価フェーズ(4.10')ではその$a$を使って$q_{\mu}(s, a)$を計算します。$q_{\mu}(s, a)$が最大となる$a$で$q_{\mu}(s, a)$を計算するので、更新後の状態価値関数$V'(s)$は$q_{\mu}(s, a)$の最大値になります。よって、改善と評価フェーズの計算をまとめて、次の式で表わせます。

$$ \begin{align} V'(s) &= \max_a q_{\mu}(s, a) \\ &= \max_a \sum_{s'} p(s' | s, a) \Bigl\{ r(s, a, s') + \gamma V(s') \Bigr\} \tag{4.11} \end{align} $$

　$\max_a$は、右辺の最大値を意味します。
　状態価値関数は、行動価値関数の最大値で計算できることが分かりました。以上が、価値反復法で行う計算です。価値反復法では、評価と改善を1つの式(計算)で行います。

　状態価値関数についてのベルマン最適方程式は、次の式でした(3.4.1項)。

$$ v_{*}(s) = \max_a \sum_{s'} p(s' | s, a) \Bigl\{ r(s, a, s') + \gamma v_{*}(s') \Bigr\} \tag{3.16} $$

　式(4.11)は、この式と対応しているのが分かります。

　式(4.11)を、価値反復法における状態価値関数の更新式として利用します。

$$ V_{k+1}(s) = \max_a \sum_{s'} p(s' | s, a) \Bigl\{ r(s, a, s') + \gamma V_k(s') \Bigr\} \tag{4.11'} $$

　この式で状態価値関数を無限回(収束するまで)更新を繰り返すと、最適状態価値関数$V_{*}(s)$が得られます。また、$V_{*}(s)$をgreedy化することで、最適方策$\mu_{*}(s)$が得られます。

$$ \mu_{*}(s) = \mathop{\mathrm{argmax}}\limits_a \sum_{s'} p(s' | s, a) \Bigl\{ r(s', a, s) + \gamma V_{*}(s') \Bigr\} \tag{4.12} $$

　以上が、価値反復法のアルゴリズムです。

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

参考文献

ゼロから作るDeep Learning ❹ ―強化学習編

おわりに

　次でやる実装の中で行動価値関数を表す変数名action_valuesが出てくるので、数式でも行動価値関数を噛ませておきました。

【次節の内容】

www.anarchive-beta.com