強化学習③ - Bellman方程式
強化学習の基礎についてまとめたノートの第三回です。
実用上の課題
前回までに、確かに最適な方策$\pi^*$が求まることがわかったのですが、このようなMDPの解法には、実用上の問題があります。
というのも、最適な方策を知るためには最適な状態価値関数$\mathsf{V}_{\pi^*}$を知る必要があり、これを知るには、各々の方策$\pi$に対する状態価値関数$\mathsf{V}_{\pi}$を解いて、それぞれを比較していかなければならないからです。
ところが、逆行列の計算量はおよそ$\mathrm{O}\left(n^3\right)$であることから、系のとりうる状態のサイズが大きくなると、状態価値関数を求めるためのコストは急激に増大します。ただでさえ計算量が多いのに、これをあらゆる方策に関して試していたらいくら時間があっても足りません。
このようにMDPのナイーブな行列解法というのは実用的ではないので、$\pi^*$を効率的に求めるためのアルゴリズムについて、ずっと以前から研究が行われてきました。
Q関数
具体的なアルゴリズムを提示する前に、一つだけ新しい概念を導入しておきます。
これまで用いてきた状態価値関数$\mathsf{V}_\pi$というのは実はあまり使い勝手のいいものではありません。なぜなら、例え最適な状態価値関数$\mathsf{V}_{\pi^*}$がわかったとしても、そこから直ちに最適な方策$\pi^*$を求める術がないからです。
ここまで、すべての行動を方策$\pi$に沿って決めてきたがために、その他の行動を採る余地が失われていました。そこで、次に採ろうとしている行動の価値を評価するために、新たに次のような関数を定義します:
$$ Q(a,s) = \left.\sum_{k=0}^\infty \gamma^k R^{s_{t+k}~s_{t+k+1}}_{a_{t+k}}\middle|_{a_t=a\\s_t=s}\right. $$
これは合計報酬$V(s)$に対し、新たに状態$s$の下で採る行動$a$を引数として加えたものです。
この期待値は方策$\pi$に対して$V(s)$と同様に求めることができて、
$$ \begin{array}{ll} \mathsf{Q}_\pi(a,s) &\displaystyle \equiv \mathbb{E}_\pi\left[ Q(a,s)\right]\\ &\displaystyle= \mathbb{E}_\pi\left[\left. \sum_{k=0}^\infty \gamma^k R^{s_{t+k}~s_{t+k+1}}_{a_{t+k}} \middle| _{a_t = a \\ s_t = s}\right. \right]\\ &\displaystyle= \mathbb{E}_\pi\left[ R^{s~s_{t+1}}_{a} + \gamma V(s_{t+1})\right]\\ &\displaystyle= \sum_{s' \in S} P^{ss'}_{a}\left[R^{ss'}_{a} + \gamma \mathbb{E}_\pi\left[ V(s')\right]\right]\\ &\displaystyle= \mathsf{R}_a(s) + \gamma \sum_{s' \in S} P^{ss'}_a\mathsf{V}_\pi(s') \end{array} $$
となります。この期待値$\mathsf{Q}_\pi(a,s)$を行動価値関数(action-value function)とよびます。ある状態$s$の下で採る行動$a$の価値を合計報酬の期待値として与えるからです。
先ほどの状態価値関数$\mathsf{V}_\pi(s)$の表式と比較すると、状態価値関数と行動価値関数との間には次の関係があることがわかります。
$$ \mathsf{V}_\pi(s) = \sum_{a \in A_s} \pi_{a}(s) \mathsf{Q}_\pi(a,s) $$
つまり、行動価値関数の入力として、いま一度方策$\pi$に沿った行動を採用すれば、それは再び状態価値関数になるはずです。
これを用いることで、$\mathsf{V}_\pi(s)$と同様に$\mathsf{Q}_\pi(a,s)$に関する再帰的な方程式が得られます:
$$ \mathsf{Q}_\pi(a,s) = \mathsf{R}_a(s) + \gamma \sum_{s' \in S} P^{ss'}_a \sum_{a' \in A_{s'}} \pi_{a'}(s') \mathsf{Q}_\pi(a',s') $$
実は、この$\mathsf{Q}_\pi$を用いると、最適な方策$\pi^*$に関する重要な事実が見出されます。つまり、何らかの手続きによって最適な行動価値関数$\mathsf{Q}_{\pi^*}$が得られているとしたときに、ある状態$s$の下で最適な行動価値関数$\mathsf{Q}_{\pi^*}$を最大化するような行動$a$を選べば、それは最適な方策$\pi^*$になっているはずです:
$$ \pi^*_a(s) = \left\{\begin{array}{ll} 1 & (a=\underset{a' \in A_s}{\mathrm{argmax}}\mathsf{Q}_{\pi^*}(a', s) )\\ 0 & (otherwise) \end{array}\right. $$
ここで最適な行動価値関数$\mathsf{Q}_{\pi^*}$というのを、前回定義した最適な状態価値関数と同様に、次のような半順序で定まる極大元として定義します。
$$ \mathsf{Q}_{\pi_1} \geq \mathsf{Q}_{\pi_2} \Leftrightarrow \forall a \in A_s,\forall s \in S, ~ \mathsf{Q}_{\pi_1}(a, s) \geq \mathsf{Q}_{\pi_2}(a, s) $$
このような$\mathsf{Q}_{\pi^*}$は必ずしも一意に定まるとは限りませんが、そのようなものが少なくとも1つは存在するはずです。
例え状態遷移が確率的であっても、合計報酬の期待値を考える限りは最適な行動が決定的に定まるということが、先の関係式から今や明らかです。
驚くべき(？)ことに、ここまでの結果から、$\mathsf{V}_{\pi^*}$および$\mathsf{Q}_{\pi^*}$は実は方策$\pi^*$に陽に依存することなく、再帰的に書き下すことができることがわかります。
実際
$$ \mathsf{V}_{\pi^*}(s) = \max_{a \in A_s} \mathsf{Q}_{\pi^*}(a,s) $$
$$ \mathsf{Q}_{\pi^*}(a,s) = \mathsf{R}_a(s) + \gamma \sum_{s' \in S} P^{ss'}_a\mathsf{V}_{\pi^*}(s') $$
の関係から、直ちに
$$ \mathsf{V}_{\pi^*}(s) = \max_{a \in A_s}\left[ \mathsf{R}_a(s) + \gamma \sum_{s' \in S} P^{ss'}_a\mathsf{V}_{\pi^*}(s') \right] $$
$$ \mathsf{Q}_{\pi^*}(a,s) = \mathsf{R}_a(s) + \gamma \sum_{s' \in S} P^{ss'}_a\max_{a’ \in A_{s'}} \mathsf{Q}_{\pi^*}(a’,s’) $$
がわかります。これらを一般に最適制御問題におけるBellman方程式といいます。
すなわち、2つの価値関数が互いに異なる最適な方策$\pi^*$から定義されたものであったとしても、これらは同じBellman方程式の解になっており、
したがって実際のところ、最適な価値関数は$\pi$という記号を省略して、$\mathsf{V}^*$や$\mathsf{Q}^*$と書いてしまっても問題ないのです。
これらの方程式は、各々の状態$s$で最適な方策を採用する(行動価値関数を最大化するような行動を選択する)ことが、
最終的には全体を通しての最適な方策となる(合計報酬の期待値を最大化する)ということを示唆しています。
つまり、わたしたちは1つの大きな学習問題を、より簡単で小さな部分問題に分割して解くことが許されるのです。
最適制御問題におけるこのような性質はBellmanの最適性原理(Bellman's Principle of Optimality)とよばれています。
この性質のおかげで、強化学習問題を解く際には次の回で見るような動的計画法が有効になってきます。
そして、いくつもある動的計画法のうち今もっとも成功を収めているのが、今巷で話題になっている深層強化学習というわけです。
