強化学習(Reinforcement Learning)は数式が多く一見難しそうに見えますが、統計学の確率分布の表記に慣れていれば実はそれほど難しくありません。そこで何回かにわけて強化学習の基本トピックに関して取り扱いを行います。
第$2$回は最適ベルマン方程式の導出にあたって用いる「動的計画法(Dynamic Programming)」を取り扱います。Richard S. Suttonの”Reinforcement Learning, second edition: An Introduction“のChapter$4$を参考に作成を行いました。
Contents
基本的な理論の確認
概要
動的計画法(Dynamic Programming)はマルコフ決定過程(MDP; Markov Decision Process)の完全な環境モデル(perfect model of environment)が与えられるとき最適方策(optimal policy)を計算するのに用いられる手法である。
ここで「完全な環境モデル(perfect model of environment)」は、第$1$回で取り扱った状態遷移確率(state-transition probabilities)の$p(s’,r|s,a) = P(S_{t+1}=s’,R_{t+1}=r|S_t=s,A_{t}=a)$が対応すると考えておけば良い。要するに状態$S_t$とエージェントの行動$A_t$が定まった際に、次の状態$S_{t+1}$と同時に発生する報酬$R_{t+1}$の確率分布が既知である場合をこのように考える。
この環境モデル(environment model)の考え方は「モデルフリー(model free)強化学習」と「モデルベース(model based)強化学習」にも関連する。「モデルベース(model based)強化学習」は近年ではalpha Goやalpha Zeroなどのボードゲームにおける強化学習でよく研究されており、環境モデルから最適方策を導出する方法をプランニング(planning)と表すことも抑えておくと良い。
動的計画法を考える際の主要な考え方は価値関数(value function)を「良い方策(good policy)」を探索する際に用いるということである。ここで用いる価値関数は第$1$回で確認したベルマン方程式(Bellman equation)の数式の形を用いる。
$$
\large
\begin{align}
v_{\pi}(s) &= \mathbb{E}_{\pi} [G_{t}|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) \left[ r + \gamma v_{\pi}(s’) \right] \quad (1)
\end{align}
$$
動的計画法のアルゴリズムは上記で表したベルマン最適方程式の式を用いて表現を行う。式の中に出てきた$\pi(a|s)$と$p(s’,r|s,a)$は期待値を考える際の確率分布と同様に理解しておくと良い。
より具体的には「動的計画法」に基づいて「方策評価」を行い、その「方策評価」に基づいて「方策反復法(Policy Iteration)」や「価値反復法(Value Iteration)」を構築し、繰り返し計算によって「最適方策」の計算を行う。
動的計画法の再確認
前項では「強化学習」における「動的計画法」の活用にあたっての概要を確認を行なったが、「強化学習」に関連して「動的計画法(Dynamic Programming)」の解説がなされることは少ないように思われる。
「動的計画法(Dynamic Programming)」に関してはWikipediaを元に考えるが、「対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称」と記載されている。
この具体例に「フィボナッチ数列」が紹介されているが、$a_5 = a_4 + a_3 = (a_3+a_2) + (a_2+a_1) = …$のように考えるのではなく、$a_2 = a_1 + a_0, a_3 = a_2 + a_1$のように考えることを動的計画法を用いたプログラムに挙げられている。
要するに、漸化式を元に$a_0, a_1, a_2, a_3, …$のように順に値を計算していくことを動的計画法(Dynamic Programming)と総称していると理解すると良いように思われる。
ここで次項で扱う「反復方策評価」は漸化式を元に値を順に計算する手法であるので、動的計画法に基づくと考えられる。
一方で「動的計画法」は多義的な表現であり、もう少し適切な表現の方があるようにも思われる。これに関しては、「ベルマン方程式」を考案したベルマン(Richard Ernest Bellman)が「動的計画法」も同時に発表していたことに起因すると思われる。
動的計画法に関しては「トップダウン方式(分割統治法)」と「ボトムアップ方式」の二つがあり、「分割統治法」をメインで紹介されることも多いのでこの辺はミスリードになる場合もあるように思われた。「ボトムアップ方式」は漸化式に関連する問題の解法を考えるにあたって直感的にそのまま用いる解法であるので、「動的計画法」に関して学ぶ際には既知である場合も多いと考えられるが、強化学習の動的計画法は単にシンプルな「ボトムアップ方式」を用いていると考えれば良いと思われる。
当項は単に筆者の考察であり、出典が存在しないのでご注意ください。また、関連する文献をご存知の方がおられたらご指摘ください。
反復方策評価(Iterative Policy Evaluation)
反復方策評価(Iterative Policy Evaluation)は$1.1$節の$(1)$式に対して動的計画法の考え方に基づいて繰り返し演算を適用する手法である。
$$
\large
\begin{align}
v_{k+1}(s) & \equiv \mathbb{E}_{\pi} [R_{t+1} + \gamma v_{k}(S_{t+1})|S_{t}(s)] \\
&= \sum_{a} \pi(a|s) \sum_{s’,r} p(s’,r|s,a) \left[ r + \gamma v_{k}(s’) \right] \quad (2)
\end{align}
$$
反復方策評価は具体的には上記で表した繰り返し演算に基づいて価値関数の$v_{\pi}(s)$の近似を行う。ここで$S_{t}=s \to S_{t+1}=s’$が状態の変化を表す一方で、$k \to k+1$は価値関数の変化を表すことに注意が必要である。
方策改善(Policy Improvement)
反復方策評価によって価値関数$v_{\pi}$が収束した際に、価値関数に基づいて方策を改善することが必要になる。この一連の流れを方策改善(Policy Improvement)という。
方策改善は方策改善定理(Policy Improvement Theorem)に基づいており、価値関数に基づいて方策を改善することは既存の方策が最適でない限りは既存のものよりもより良い方策が得られるという考え方である。
方策反復法(Policy Iteration)
方策反復法は方策評価(Policy Evaluation)と方策改善(Policy Improvement)を繰り返す手法である。アルゴリズムは下記のように表される。
上記の一連の処理を方策反復法(Policy Iteration)という。一連の流れは下記のようにも概略を表すことができる。
$$
\large
\begin{align}
\pi_0 \to v_{\pi_0} \to \pi_1 \to v_{\pi_1} \to … \to \pi_{*} \to v_{\pi_{*}}
\end{align}
$$