【強化学習】第2回 - ベルマン方程式と方策反復法(PI)、価値反復法(VI)について解説

はじめに

第2回である本稿では、まずベルマン方程式を説明します。その後、前回導入した価値関数を最大化する手法である方策反復法(PI)、価値反復法(VI)といった有名なアルゴリズムを紹介します。なお、強化学習にはSutton & Bartoによるバイブル的な参考書"Reinforcement Learning: An Introduction"があり、この記事もここに書かれている内容を元に作成しています。すべて英語ですが、参考にしてください。

前回 ▶ 【強化学習】第1回 - 強化学習の概要とマルコフ過程について解説
次回 ▶ 【強化学習】第3回 - モンテカルロ法とTD学習について解説

ベルマン方程式

マルコフ報酬過程において、時刻 $t$ におけるReturn $G_t$ は以下の式で定義されました。

$$
\begin{align*}
G_t=r_t+\gamma r_{t+1}+\gamma^2 r_{t+2}+\gamma^3 r_{t+3}+\cdots \tag{1}
\end{align*}
$$

また、状態価値関数はこれを用いて以下のように定義されました。

$$
\begin{align*}
V(s)=\mathbb{E}[\,G_t\,|\,s_t=s\,]
\end{align*}
$$

前回は各エピソードについてのReturnである $G_t$ を計算しましたが、各状態における将来的な報酬の見込みである $V(s)$ についてはどう計算するのでしょうか。

時刻 $t$ における状態の確率分布を考えることでも計算できそうですが、ここでは少し視点を変えて、$V(s)$ が仮に求まったとしたときに、$V(s)$ が満たすべき式について考えてみます。

そうすると式(1)から、$V(s)$ は以下を満たすことが分かりますね。

$$
\begin{align*}
V(s)=R(s)+\gamma\sum_{s'\in S}P(s'\,|\,s)V(s')
\end{align*}
$$

これを(マルコフ報酬過程に対する)ベルマン方程式と呼びます。日本語でいえば、状態 $s$ における将来的な報酬の見込みは、「その場で得られる報酬 $R(s)$」と、「次の状態に遷移したあとに得られる将来的な報酬の見込み」の2つに分解できるということです。

ベルマン方程式の別の形を見てみましょう。$n$ 個の状態 $s_1,\,s_2,\,\cdots,\,s_n$ を持つマルコフ報酬過程について、$V(s_i),\,R(s_i),\,P(s_i\,|\,s_j)$ をそれぞれ以下のようにベクトルや行列で表してみます。

$$
\begin{align*}
V\,=\,
\begin{pmatrix}
V(s_1)\\
V(s_2)\\
\vdots\\
V(s_n)
\end{pmatrix}\quad
R\,=\,
\begin{pmatrix}
R(s_1)\\
R(s_2)\\
\vdots\\
R(s_n)
\end{pmatrix}\quad
P\,=\,
\begin{pmatrix}
P(s_1\,|\,s_1) & \cdots & P(s_n\,|\,s_1)\\
P(s_1\,|\,s_2) & \cdots & P(s_n\,|\,s_2)\\
\vdots & \ddots & \vdots \\
P(s_1\,|\,s_n) & \cdots & P(s_n\,|\,s_n)
\end{pmatrix}
\end{align*}
$$

すると、ベルマン方程式は以下の形でも表現することができますね。

$$
V=R+\gamma PV
$$

これを満たすベクトル $V$ を見つけられれば、全状態について $V(s)$ が求まる、というわけです。この式をいかに解くか、というのが次の話題になります。

報酬関数の計算

それでは具体的にどのような方法でベルマン方程式を満たすベクトル $V$ を見つけられるのでしょうか。まずは式変形して $V$ について解いてみましょう。

$$
\begin{align}
&V=R+\gamma PV\\
&V-\gamma PV=R\\
&(1-\gamma P)V=R\tag{2}\\
&V=(1-\gamma P)^{-1}R\tag{3}
\end{align}
$$

式(3)から分かるように、$V$ を直接求めるためには $(1-\gamma P)^{-1}$ を計算する必要があります。しかし、一般に$n\times n$行列の逆行列を計算するのには $O(n^3)$ の計算時間が必要です。将棋や囲碁を考えてもらえば分かりやすいかと思いますが、実際の強化学習における状態数は $10^3$ や $10^4$ 程度には収まらないことも多く、$O(n^3)$ の時間をかけるのはあまり嬉しくありません。

チェスの盤面は $10^{128}$ 種類程度だそうです¹。

そこで、先程のベルマン方程式を数値的に解く以下のようなアルゴリズムを採用します。

1. $k=0$ とし、$\forall s\in S,\,V_k(s)=0$と初期化する。
2. 以下を繰り返す
   1. $k=k+1$ とする。
   2. すべての状態 $s\in S$ について、$V_k=R(s)+\gamma\sum_{s'\in S}P(s'\,|\,s)V_{k-1}(s')\quad$と更新する。
   3. $V$ が収束していたら終了。そうでなければ 2.1 に戻る。

$V$ の実際の値はよくわからないですが、満たしてほしい式の形に沿うよう半ば強引に更新を重ねていけば、いつかは所望の式を満たす $V$ に収束する、というようなイメージです。

ところで先程ベルマン方程式を変形した過程で登場した式(2)をよく見てみると、このアルゴリズムは

$$
A=(1-\gamma P),\,B=R,\,x=V
$$

としたときの、連立一次方程式

$$Ax=B$$

を解いていることと全く等価であることがわかりますね。連立一次方程式を近似的に解くヤコビ法をご存知の方は、おなじみのアルゴリズムだと思います。

方策評価

できる限り高い報酬が見込めるような方策(Policy)を考えることが強化学習のゴールです。多くの報酬が獲得できるような方策を見つけるためには、一つ一つの方策について「その方策の良さ」を求める必要があります。与えられたある方策 $\pi$ に従う際、どの程度の報酬を見込めるのかを状態ごとに計算するのが、方策評価とです。以下、方策 $\pi$ に従う際の、状態 $s$ の将来的な報酬の見込みを $V^{\pi}(s)$ と表します。

方策評価は以下のような流れで行います。

1. $k=0$ とし、$\forall s\in S,\,V^{\pi}_k(s)=0$と初期化する。
2. 以下を繰り返す
   1. $k=k+1$ とする。
   2. すべての状態 $s\in S$ について、 $V^{\pi}_k=r(s,\,\pi(s))+\gamma\sum_{s'\in S}P(s'\,|\,s,\,\pi(s))V^{\pi}_{k-1}(s')$ と更新する。
   3. $V$ が収束していたら終了。そうでなければ 2.1 に戻る。

具体的な更新の様子を見てみます。再び火星探索ロボットに登場してもらいましょう。状態② から左へ動こうとする確率が60%、右へ動こうとする確率が40%とします。さらに、左へ動こうとしたときに行動が成功して状態① へ遷移する確率を70%、失敗して状態③ へ遷移する確率を30%、右へ動こうとしたときに行動が成功して状態③ へ遷移する確率を100%とします。前回の記事の「マルコフ決定過程＆方策」で紹介したものと全く同じです。割引率は $\gamma=0.5$ とします。

また、ここまで方策評価を実施した結果として

$$
V^{\pi}_k=[1,\,0,\,0,\,2,\,5]
$$

が求まっているとします。さらに、ここからは簡単のため状態①を $s_1$、状態②を $s_2,\,\cdots$ と表しましょう。このとき、現在の方策に従ったときの状態②の状態価値関数 $V_{k+1}^{\pi}(s_2)$ は以下の式で更新することができます。

$$
\begin{align*}
V_{k+1}^{\pi}(s_2)&=r\,(s_2,\,\pi(s_2))+\gamma\sum_{s'\in S}p\,(s'\,|\,s_2,\,\pi(s_2))V_{k-1}^{\pi}(s')\\
&=0+\gamma\,\{p\,(s_1\,|\,s_2,\,\pi(s_2))V_{k}^{\pi}(s_1)+p\,(s_3\,|\,s_2,\,\pi(s_2))V_{k}^{\pi}(s_3)\}\\
&=\gamma\,(0.42\cdot1+0.58\cdot0)\\
&=0.5\cdot0.42\\
&=0.21
\end{align*}
$$

なお、$r(s_2\,|\,\pi(s_2))=0$ というのは、状態2において得られる報酬は $0$ であるということです。また、1行目から2行目の式変形にかけて、明らかに移動できない状態を表す項は省略しました。

方策反復法（Policy Iteration）

さて、いよいよ最適な方策 $\pi$ を求めるアルゴリズムについて考えてみましょう。ここでは、遷移確率 $P$ や報酬 $R$ が既知であるものとします。実際に強化学習を適用する際はこれらが未知のケースもありますが、それは次回扱います。

まず、方策 $\pi$ に対する状態行動価値 $Q^{\pi}(s,\,a)$ を以下で定義します。

$$
Q^{\pi}(s,\,a)=R(s,\,a)+\gamma\sum_{s'\in S}P(s'\,|\,s,\,a)V^{\pi}(s')
$$

すなわち $Q^{\pi}(s,\,a)$ は、「状態 $s$ のときにまずアクション $a$ を取り、その後は方策 $\pi$ に従う」とした場合に得られる報酬を表しています。

$Q^{\pi}(s,\,a)$ を用いながら、以下の要領で最適な方策を求めるのが方策反復法です。最初はランダムに方策を決定し、それをあとから改善していくイメージです。

1. $i=0$ とし、$\forall s\in S$について $\pi_0(s)$ をランダムに初期化する。
2. 以下を繰り返す
   1. $i=i+1$ とする。
   2. 方策評価を用いて、$\forall s\in S$ について $V^{\pi_i}(s)$ を求める。
   3. $\forall s\in S$ について、$\pi_{i+1}(s)=\arg\max_{a\in A}Q^{\pi_i}(s,\,a)$ と更新する。
   4. $\pi$ が収束していたら終了。そうでなければ 2.1 に戻る

3.に登場する $\arg\max_{a\in A}Q^{\pi_i}(s,\,a)$ とは、「$Q^{\pi_i}(s,\,a)$ の最大値を与える $a$」という意味です。また、4.の収束判定では各状態ごとに $\pi_{i}$ と $\pi_{i+1}$ を比較していき、両者の返す行動が異なる状態が一つも存在しなければ収束、そうでなければ収束していない、と判断します。

ステップ2.3から分かるように、方策反復を繰り返しても方策が改善されないということはあり得ますが、方策が悪化するということはありません。ただし、毎回の繰り返しで $V^{\pi_i}(s)$ を求める必要があるためループが二重入れ子構造になっており、計算効率は悪いです。

価値反復法（Value Iteration）

方策反復法はより良い方策を得る上で有用な方法ですが、先述したように計算効率が悪いです。各状態についての価値と方策を同時に決定する方法はないのでしょうか。

価値反復法は各状態に対し、状態価値関数 $V_{k+1}(s)$ を用いて方策 $\pi(s)$ を決定する方法です。価値反復法は以下の要領で行います。

1. $i=0$ とし、$\forall s\in S$について $V_0(s)=0$ と初期化する。
2. 以下を繰り返す
   1. $i=i+1$ とする。
   2. $\forall s\in S$ について $V_{i}(s)=\max_{a\in A}\{R(s,\,a)+\gamma\sum_{s'\in S}P(s'\,|\,s,\,a)V_{i-1}(s')\}$ とする。
   3. $\forall s\in S$ について方策 $\pi(s)$ を以下のように更新する。
      $$
      \pi(s)={\arg\max}_{a\in A}\{R(s,\,a)+\gamma\sum_{s'\in S}P(s'\,|\,s,\,a)V(s')\}
      $$
   4. $V(s)$ が収束していたら終了。そうでなければ 2.1 に戻る

すなわちあらゆる状態において、求まった価値の見積もりが最大となるような行動を選択するのが最適な方策ということになります。このようにその場その場における最大を選んでいくような戦略を、貪欲(Greedy)な方策や、貪欲な方策といいます。また、価値反復法は方策反復法とは異なり、収束を待つループが2重にはなっていません。

ベルマン演算

あまり紹介されている文献がなかったので、最後にベルマン演算について簡単に触れておきます。
Bellman backup operator² $B$ は、状態価値関数 $V$ に対して以下のように定義されます。

$$
BV(s)=\max_{a}[R(s,\,a)+\gamma\sum_{s'\in S}p(s'\,|\,s,\,a)V(s')]
$$

状態価値関数についてベルマン演算を行うと、それぞれの状態について最適な選択を行った際の報酬の見積もりを $V(s)$ を用いて計算し直した状態価値関数が返ってくる、ということです。また、特定の方策に対するベルマン演算も同様に以下で定義されます。

$$
B^{\pi}V(s)=\max_{a}[R^{\pi}(s,\,a)+\gamma\sum_{s'\in S}P^{\pi}(s'\,|\,s)V(s')]
$$

これを用いれば、先程紹介した方策評価は「$V$ が変化しなくなるまでベルマン演算を適用し続ける操作」として、以下のように表現できますね。

$$
V^{\pi}=B^{\pi}B^{\pi}B^{\pi}B^{\pi}\cdots B^{\pi}V
$$

おわりに

前回定義した状態報酬関数や方策を具体的に計算する手法について扱いました。ベルマン方程式や方策反復法、価値反復法について理解していただけたでしょうか。ここまでの内容を知るだけでも、簡単な迷路を解く強化学習のプログラム程度なら実装できるようになります。次回はモンテカルロ法とTD学習について扱う予定です。

訳出について

専門用語は、以下のように訳出しています。機械学習分野はしっかりとした和訳が確立されていないものも多いので、そのようなものは英語のままにしました。

日本語	英語
ベルマン方程式	Bellman Equation
方策評価	Policy Evaluation
方策反復法	Policy Iteration
価値反復法	Value Iteration
ベルマン演算	Bellman Operation

参考文献

1. Sutton & Barto, "Reinforcement Learning: An Introduction", http://incompleteideas.net/book/the-book.html （最終閲覧: 2022/11/03）
2. 星野孝総 亀井且有, "ファジィ環境評価ルールを用いた強化学習の提案とチェスへの応用", 日本ファジィ学会誌（2001)
3. icoxfog417, "ゼロからDeepまで学ぶ強化学習", https://qiita.com/icoxfog417/items/242439ecd1a477ece312 （最終閲覧: 2022/11/03）
4. (画像素材) Unsplash, https://unsplash.com/ （最終閲覧: 2022/11/03）

1. 星野孝総 亀井且有, "ファジィ環境評価ルールを用いた強化学習の提案とチェスへの応用", 日本ファジィ学会誌（2001) ↩

2. ベルマン補助演算子、とでも訳すのでしょうか。 ↩