強化学習④ - Q関数の評価
強化学習の基礎についてまとめたノートの第四回です。
具体的なアルゴリズム
前回までに、最適な方策$\pi^*$は最適な行動価値関数$\mathsf{Q}^*$を最大化するような行動を採ることで与えられることがわかりました。さらに、最適な行動価値関数$\mathsf{Q}^*$は、Bellman方程式を解くことで求めることができることもわかりました。
すなわち、最適な方策$\pi^*$を求める問題は、Bellman方程式を解くことに帰着されたわけです。
見ればわかるように、一般にBellman方程式は非線形な再帰方程式です。これを解くための1つの処方箋が動的計画法(Dynamic Programming)です。
そこでここでは、Value iterationやPolicy iterationなどといったアルゴリズムに基づいて実際に動的計画法を用いてBellman方程式を解くことで、Q関数の値を求めることを考えます。
Value iteration
iterationという名のつくとおり、これらのアルゴリズムは反復計算を行うことで、逐次的に最適解を得ようというものです。
Value iterationでは、Q関数の出力値を繰り返し更新することで最適解を得ることを考えます。やることは簡単で、
- まずQ関数をランダムに初期化して$\mathsf{Q}_{old}$とする。
- こうして得た$\mathsf{Q}_{old}$から、新たな$\mathsf{Q}_{new}$を計算して、Q関数の値を更新する。
- これを再び$\mathsf{Q}_{old}$として繰り返しQ関数を更新する。
$$ \mathsf{Q}_{new}(a,s) \leftarrow \mathsf{R}_a(s) + \gamma \sum_{s' \in S} P^{ss'}_a\max_{a’ \in A_{s'}} \mathsf{Q}_{old}(a’,s’) $$
この操作によって、最適なQ関数$\mathsf{Q}^*(a,s)$が漸近的に得られることが証明されています。最後に、得られた$\mathsf{Q}^*(a,s)$から、$a=\underset{a \in A_s}{\mathrm{argmax}}\mathsf{Q}^*(a,s)$に基づいて次の行動を決定します。これがValue iterationです。
Value iterationにおいて真っ先に問題となるのは、エピソードの終了時点がはっきりと決まっていない問題に対して、Q関数の更新が終わることを保証できないということです。計算途中のQ関数の値は一般にどの方策にも対応しないので、値が収束する前に計算を打ち切ったとしても、そのようなQ関数の値を行動の選択に用いることに正当性がありません。
もちろん頑張って計算をして最適なQ関数を得ることができれば、長期間継続する環境も学習することはできます。しかし各状態での最善の価値関数への収束は漸近的であるため、最善の方策を得られるようなQ関数のしきい値を解析的に見極めることも困難なのです。
したがって、現実的な問題でValue iterationが使われることはまずありません。
次に紹介するPolicy iterationは、Value iterationのもつ欠点を克服し、不確定な期間を持つ環境を学習することが可能で、なおかつiterationを繰り返す毎に確実に方策の向上が期待できる手法です。
Policy iteration
policy iterationはvalue-based methodとpolicy-based methodに大別されます。これらを厳密に区別する定義があるわけではありませんが、前者はその名の通り価値関数を積極的に利用しながら最適な方策を求めようとするもので、後者は方策関数を積極的に利用しながら最適な方策を求めようとするものというような思想を感じます。
value-based policy iterationでは、主に次の2つのステップによって最適な方策を見つけることを目指します。
- Policy evaluation ある方策$\pi$の下で$\mathsf{Q}_{\pi}$を計算する。
- Policy improvement $\mathsf{Q}_{\pi}$に基づいて、$\pi' \geq \pi$となるようなより良い方策$\pi'$を見つける。
policy evaluationでは、厳密な行列解法や、value iterationで用いた反復解法などを用いることで、どうにかしてある方策$\pi$の下でのQ関数$\mathsf{Q}_{\pi}$を計算します。
policy improvementでは、例えば計算した$\mathsf{Q}_{\pi}$を使って$a=\underset{a \in A_s}{\mathrm{argmax}}\mathsf{Q}_{\pi}(a,s)$を$s$の下での新たな方策として採用することによって方策$\pi$を(暗黙に)更新します。
これはvalue iterationとは異なり、エピソードの終了時点がはっきりと決まっていない問題に対しても適用可能です。また、ステップ毎に確実に方策を向上させることができる点もこの方法の強みです。これを繰り返すことで、漸近的に最善な方策$\pi^*$が得られることが証明されています。
1エピソードが数ステップで構成されているような場合はvalue iterationを使って直接最適なQ関数を求めてしまうのが手っ取り早いですが、このような問題を計算機で解くことにはあまり興味が持たれないので、ほとんどの実用的な強化学習アルゴリズムはこのpolicy iterationに基づいています。
さて、安直に考えてみると、Q関数さえ正しく計算できてしまえば単にQ関数を最大化するような行動を採ることで良い意思決定ができるはずだということになるので、これ以降は、具体的に「どのようにQ関数を計算するのか？」(policy evaluation)という点に的を絞って解説をしていこうと思います。
さて、計算機によって調べたいような(計算し甲斐のある)問題というのは、大まかに2つに分類できます。
- 系のモデルが未知であり、Q関数が正確に計算できない
- モデルは分かっているが系が取りうる状態のなす空間が広大で、現実的な時間ではQ関数が計算できない
上で挙げたように、われわれは多くの場合、正確にQ関数を計算することができないのです。
これまでは以下のような価値関数によって方策$\pi$を評価してきましたが、これを実行するにはいずれも系のモデル$P^{ss'}_a$が既知であり、系の状態数が十分に小さい必要がありました。
$$ \mathsf{V}_\pi(s) = \mathsf{R}_\pi(s) + \gamma \sum_{s' \in S} \underline{P^{ss'}_\pi}\mathsf{V}_\pi(s') $$
$$ \mathsf{Q}_\pi(a,s) = \mathsf{R}_a(s) + \gamma \sum_{s' \in S} \underline{P^{ss'}_a} \sum_{a' \in A_{s'}} \pi_{a'}(s') \mathsf{Q}_\pi(a',s') $$
では、このような問題を解くにはどうすればいいか？それは、実際に行動をしてみて、その結果得られた報酬から、Q関数を推定することです。
このようなアプローチでQ関数を計算しようとするのが、Monte-Carlo(MC)学習やTemporal-Difference(TD)学習などの手法です。これらはmodel-freeな解法と呼ばれていて、系のモデルに関する事前知識を知らずに問題を解くことが可能なアルゴリズムになっています。
Monte-Carlo Learning
Monte-Carlo Learningでは環境の中で実際に行動を選択して状態・行動・報酬の列${s_1,a_1,V_1,s_2,a_2,V_2,\cdots}$をサンプリングしていくことで、この列からQ関数を推定しようとします。このような方策の評価をMonte-Carlo policy evaluationとよびます。
まず、Q関数が次のような形で書けることに注目します。
$$ \mathsf{Q}_\pi(a,s) = \mathsf{R}_a(s) + \gamma \mathbb{E}_\pi\left[V(s_{t+1})\right] $$
本来ならば期待値$\mathbb{E}_\pi\left[V(s_{t+1})\right]$を、上のようにモデル$P^{ss'}_{a}$と方策$\pi$を用いて具体的に書き下すところですが、系のモデルが未知である場合は却って厄介です。そこで、Monte-Carlo policy evaluationでは、この$\mathbb{E}_\pi\left[V(s_{t+1})\right]$を経験分布の期待値として計算します。
すなわち、
- エッジ$(a,s)$を訪れた回数(visit count) : $N(a,s)$
- $(a,s)$から遷移した状態$s'$の下で得られる経験的な状態価値 : $V(s')=\left.\sum_{k=0}^\infty \gamma^k R^{s_{t+k}~s_{t+k+1}}_{a_{t+k}}\right|_{s_t=s'}$
を計測し、$V(s')$の平均報酬を$\mathsf{Q}_\pi(a,s)$とみなします:
$$ \mathsf{Q}_\pi(a,s) \sim \mathsf{R}_a(s) + \gamma \frac{1}{N(a,s)}\sum_{s'|a,s\rightarrow s'} V(s') $$
ここで$\sum_{s'|a,s\rightarrow s'}$は、エッジ$(a,s)$を経てある状態$s'$に到達した全ての試行に関し、到達した状態$s'$の下で得た経験的な状態価値$V(s')$の総和をとることを意味します。
さらに、$n$個のサンプルの相加平均が
$$ \bar{x}^{(n)} = \frac{1}{n}\sum_{i=1}^n x_i $$
で表されることに注目すると、
$$ \begin{array}{l} \bar{x}^{(n+1)} &\displaystyle= \frac{1}{n+1}\sum_{i=1}^{n+1} x_i \\ &\displaystyle= \frac{1}{n}\sum_{i=1}^{n} x_i + \frac{1}{n+1}\left( x_{n+1} - \frac{1}{n}\sum_{i=1}^{n} x_i \right) \\ &\displaystyle= \bar{x}^{(n)} + \frac{1}{n+1}\left(x_{n+1} - \bar{x}^{(n)}\right)\ \end{array} $$
となるので、結局$N(a,s)$および$\mathsf{Q}_\pi(a,s)$の更新は次のように行われます。
$$ N_{new}(a,s) \leftarrow N_{old}(a,s) + 1 $$
$$ \mathsf{Q}_{new}(a,s) \leftarrow \mathsf{Q}_{old}(a,s) + \frac{1}{N_{new}(a,s)}\left( V(s') - \mathsf{Q}_{old}(a,s) \right) $$
ここで注意しなければならない点は、「経験的な状態価値」としてサンプリングするのは、状態$s'$の下で得られる即時報酬でも、状態$s'$の下で得られる状態価値の期待値でもないので、一連の行動と状態遷移(エピソード)が終端に達するまではQ関数を更新することはできないということです。
したがって、経験した報酬はエピソードが終端に達した後に初めて、すべてのエッジ$(a,s)$にフィードバックすることになります。
このようにして得られた経験的なQ値は$N \rightarrow \infty$の極限で、期待される$\mathsf{Q}_\pi(a,s)$に近づいていくと考えられます。当然、これはモデル$P^{ss'}_\pi$に依ることなく計算できるので、あとは既存の方法などを組み合わせてpolicy improvementを行うことで、これまでと同様に最適な方策$\pi^*$を計算することができるはずです。
このように、MC学習には
- エピソードが終わるまで、Q関数を更新できない
- 有限ステップでエピソードが終わることが保証されているような環境を学習するのに適している
- 長期的な価値を比較的素早く学習できる
といった特徴があります。
Temporal-Difference Learning
さて、モデルに依らずに価値関数を計算するもう一つの方法が時間差学習(Temporal-Difference Learning)と呼ばれる手法です。
MC学習では実際に一連の行動と状態遷移によるサンプリングを行うことで、モデルに依ることなく正しいQ関数を推定することを試みました。
一方TD学習では、現時点で期待している行動価値$\mathsf{Q}_\pi(a,s)$と、実際に行動してから分かった行動価値$R^{s~s_{t+1}}_a + \gamma \mathsf{Q}_\pi(a_{t+1},s_{t+1})$との差(TD誤差)を最小化することで、正しいQ関数を推定することを試みます。
これは、次のような更新を繰り返し行うことで達成できると考えられます。
$$ \mathsf{Q}_{new}(a,s) \leftarrow \mathsf{Q}_{old}(a,s) + \alpha\left( R^{ss'}_a + \gamma \mathsf{Q}_{old}(a',s') - \mathsf{Q}_{old}(a,s)\right) $$
ただし、$s'$はエッジ$(a,s)$を経た後に実際に達した状態で、$a'$は状態$s'$の下で選択する行動を意味します。
$\alpha$は学習係数です。言ってみれば、これが0に近いほど、「保守的な」評価になり、1に近いほど「ミーハーな」評価になります。
さて、状態$s'$に達した時点では$a'$はまだ決まっていないので、式の中で$a'$をどのように定めるかで一つの選択肢が生じます。
例えば、これを何らかの方策に基づいて予め行動$a'$を決定したあとに評価するような方法は、$(s,a,R,s',a')$をQ関数の学習に用いることから、SARSA学習と呼ばれています。
一方$a'$を、現在の行動価値$\mathsf{Q}_{old}$を最大化するようなもの、すなわち$a'=\underset{a' \in A_{s'}}{\mathrm{argmax}}\mathsf{Q}_{old}$として選んだ上で$\mathsf{Q}_{new}$を計算する手法をQ学習とよび、更新式は次のようにシンプルに表すことができます。
$$ \mathsf{Q}_{new}(a,s) \leftarrow \mathsf{Q}_{old}(a,s) + \alpha\left( R^{ss'}_a + \gamma \max_{a'} \mathsf{Q}_{old}(a',s') - \mathsf{Q}_{old}(a,s)\right) $$
