機械学習
強化学習
機械学習入門
More than 1 year has passed since last update.

推敲してたら長くなりそうなので、一旦投稿しておきます。

内容

今回は、価値関数を用いた最適行動学習としてQ学習、SARSA、Expected SARSAを説明します。それらの導入として、非同期式価値反復・方策反復を紹介します。上記のアルゴリズム達は、非同期式価値反復・方策反復の確率近似版として理解されます。その後、適格度トレースについて説明します。適格度トレースは、方策反復と価値反復を繋ぐようなダイナミックプログラミングの手法として紹介します。(長くなるので次回にします。)これは、Sutton等の本ではなく、Bertsekas等の本(Neuro-Dynamic Programming)に紹介されています。というより、前回の記事も後者の本を参考にしています。Bertsekas等の新しい本も欲しいのでボスに最近おねだりしました。その本が来たら、記事たちもアップデートするかもしれません。あと、間違いがあったら指摘お願いします。編集リクエスト?の使い方が分からないですが、直接記事を編集していきますので。

価値関数を用いた最適行動学習については、ダイナミックプログラミングとの関係を重視しながら説明します。また、テーブル方式の価値関数学習もパラメータを持つ関数の学習として捉えます。これにより、関数近似における価値関数学習が、何故、テーブル方式の価値関数学習の拡張であるのかを説明します。また、混乱しやすいのがOff方策とOn方策の違いです。そこで、それも説明します。

あと、全然関係ないですが、今夏のインターンシップ先を探しています。もし強化学習を使ったオススメインターンシップ先をご存知でしたら教えてください。TheanoとLasagneを使って、基本的なディープラーニングアルゴリズム(DQNやVAE)位なら実装できます。コツメカワウソが所属しているパークで深層強化学習をやっているフレンズがいないので、深層強化学習をやってるフレンズが居るパークに行きたいです。けものフレンズおもしろーい!

価値関数を用いた最適行動学習

今回のテーマに入る前に少しだけ注意を述べておく。前回、行動価値関数を $\mathbf{q}$ というベクトルで表した。これは、関数が先に存在し、それをベクトルにしたと考える人が居るかもしれない。実際には逆として捉えたほうがいい。つまり、ベクトルが先にあり、その要素を $q(s,a)$ と表記していると捉えたほうがいい。より抽象的に言うと、 $\mathbf{q}$ とは関数空間の元であり、 $q(s,a)$ はその一部分を見ているに過ぎない。前回の仮定では、状態空間と行動空間がともに有限だからベクトルとして表記出来ただけだ。この辺りの話は、すこし込み入ってくるので行わない。気になる場合は、私が個人的に崇拝しているRemi Munos様やCsaba Szepesvari様の論文を読んでいけば詳しい。

それでは、本題に入る。前回、ダイナミックプログラミングについて説明した。そこで出てきたのが、ベルマン作用素 $\mathbf{T}^\pi$ と呼ばれるものであり、任意のベクトル $\mathbf{q}$ に対して $\mathbf{T}^\pi$ を何度も作用させることで $\mathbf{q}^\pi$ が得られた。ここで思い出して欲しいのが、ベルマン作用素は、任意のベクトル $\mathbf{q}$ を

\left( \mathbf{T}^\pi \mathbf{q} \right) (s,a) = r(s,a) + \gamma \sum_{s',a'} p(s'|s,a) \pi(a'|s') q(s',a')

に変換するものだった。実際の応用では、残念なことにこの更新は二つの理由で難しい。まず、$\mathbf{T}^\pi$ を $\mathbf{q}$ に作用させるということは、全ての状態-行動対を一斉に更新していること相当する(このような方式を同期式更新と呼ぶことにする)。同期式更新は、実際応用上の多くの場合で難しい。なぜなら実際には、エージェントが環境と相互作用するごとに、状態-行動対とそれに対する結果を得る。そのため、全ての状態-行動対に対して一斉に更新するには、多くのデータを保持し、それが得られるまで待たなければならない。

二つ目の理由として、実際応用においては $r(s,a)$ と $\sum_{s',a'} p(s'|s,a) \pi(a'|s') q(s',a')$ のどちらも得られないということだ。そのため、報酬と状態遷移から推定する必要がある。

非同期式価値反復

そこでまず、非同期式に行動価値関数をアップデートするアルゴリズムの非同期式価値反復を紹介しよう(Neuro-Dynamic Programmingより)。非同期式価値反復は、次のように行われる:今、 $k$ 番目の行動価値関数 $\mathbf{q}_k$ を持っていると仮定しよう。更新は、状態-行動対 $(s_i,a_j)$ を選び、行動価値関数を

\begin{aligned}
q_{k+1}(s,a) = \begin{cases}
r(s,a) + \gamma \sum_{s'} p(s'|s,a) \max_{a'} q_{k}(s',a')\ &\text{if $(s,a)=(s_i,a_j)$}\\
q_{k}(s,a)\ &\text{otherwise}
\end{cases}
\end{aligned}

として更新する。非同期式価値反復は、全ての状態-行動対が無限回多く(infinitely oftenの和訳ってなんですかね)選ばれるならば収束する。ここで、無限回多く選ばれるというのは、(イメージとして)任意の $n$ に対し $n$ 番目の更新より後の更新に選ばれる状態-行動対の集合が必ず全ての状態-行動対を含む事だ。

これの収束証明(Neuro-Dynamic Programming)を噛み砕いて説明しよう。まず、 $\mathbf{q}_1 \leq \mathbf{q}_2$ となっているとき、両辺に対し同じ非同期式更新を行っても不等式は守られる事に注意しよう。次に、 $\mathbf{q}^*$ を最適方策の行動価値関数とする。そして、行動価値関数の初期値 $\mathbf{q}^+ = \mathbf{q}^* + \delta \mathbf{1}$ (ただし $\mathbf{1}$ はすべての要素が $1$ のベクトルで $\delta$ は正の数)に対して非同期式更新を適用しよう。その場合、選ばれた状態-行動対は

r(s,a) + \gamma \sum_{s'} p(s'|s,a) \max_{a'} \left[ q^*(s',a') + \delta \right] = q^*(s,a) + \gamma \delta

となるので、少し小さくなる。また、同期更新の場合、 $T \mathbf{q}^+ = \mathbf{q}^* + \gamma \delta \mathbf{1}$ となる。

今、全ての状態-行動対が無限回多く選ばれる。そこで、 $k$ 番目の行動価値関数 $\mathbf{q}_k$ に対し、 $\mathbf{q}_{k+1}$ を、全ての状態-行動対が少なくとも一度は更新された後の行動価値関数としよう。ここで、少し考えると分かるが

\mathbf{q}^+ = \mathbf{q}_0 \geq T \mathbf{q}_0 \geq \mathbf{q}_1 \geq \mathbf{q}^*

となる。ここで、ある $k$ に対して $T^k \mathbf{q}_0 = \mathbf{q}^* + \gamma^k \delta \mathbf{1} \geq \mathbf{q}_{k}$ とする( $\gamma^k \delta$ を $\delta$ と読みかえる事で、上記の不等式と同様のことが成立することに気づいて欲しい)。前述の注意より、両辺に非同期更新を行うことで、 $T^{k+1} \mathbf{q}_0 \geq \mathbf{q}_{k+1}$ が得られる。よって、任意の $k$ に対して

T^k \mathbf{q}^+ \geq \mathbf{q}_k \geq \mathbf{q}^*

が得られる。 $\lim_{k \rightarrow \infty} T^k \mathbf{q}^+ = \mathbf{q}^*$ なので、 $\mathbf{q}_k$ が収束するのは明らかである。同様の議論が $\mathbf{q}^- = \mathbf{q}^* - \delta \mathbf{1}$ に対しても成立する。

今、行動価値関数の初期値として $\mathbf{q}^- \leq \mathbf{q}_0 \leq \mathbf{q}^+$ となるものを選ぶ。すると、証明の最初に述べた注意から、非同期更新によって $\mathbf{q}^*$ に収束することが分かる。

非同期式方策反復

次に非同期式方策反復を紹介しよう(Neuro-Dynamic Programmingのものとは異なります)。非同期式価値反復とほぼ同様の更新式だが

\begin{aligned}
q_{k+1}(s,a) = \begin{cases}
r(s,a) + \gamma \sum_{s',a'} p(s'|s,a) \pi(a'|s') q_{k}(s',a')\ &\text{if $(s,a)=(s_i,a_j)$}\\
q_{k}(s,a)\ &\text{otherwise}
\end{cases}
\end{aligned}

として更新する。収束の証明は、非同期式価値反復と同様に行われる。そして、ある方策に対する行動価値関数が得られれば、それを使って方策の改善が可能となる。

SARSA

よって、非同期更新に関する問題は回避可能であることが分かった。一方、ベルマン作用素の推定はどうか?非同期更新時のベルマン作用素の推定として、もっとも簡単に思いつくものは、実際のサンプル $s$, $a$, $s'$, $a'$ を用いて

\left( \mathbf{T}^\pi \mathbf{q} \right) (s,a) \approx r(s,a,s') + \gamma q(s',a')

とするものだろう。そして、現在の行動価値関数の推定値 $q(s, a)$ を

q(s, a) \leftarrow q(s, a) + \alpha \left\{ r(s,a,s') + \gamma q(s',a') - q(s, a) \right\}

というように更新する方法だ。ただし、 $\alpha$ は学習率で通常は $1$ よりも小さくしなければならない。この式に現れる $r(s,a,s') + \gamma q(s',a') - q(s, a)$ をTemporal Difference (TD)誤差と呼び、通常 $\delta$ と表記する。この更新方法は、大変直感的だ。というのも、 $r(s,a,s') + \gamma q(s',a')$ が $q(s,a)$ より大きければ $q(s,a)$ を大きくして、小さいなら $q(s,a)$ も小さくしようというだけだ。この学習則をTD学習と呼ぶ。

では、TD学習を数学的にはどう解釈すればよいのか?それにはまず、 $\mathbf{q}$ を以下に示すような関数と考える必要がある。

q(s,a) = \sum_{s_i, a_j} \theta_{s_i, a_j} \mathbf{1}_{s_i=s,a_j=a}

ただし、 $\theta_{s_i, a_j}$ がパラメータで、 $\mathbf{1}_{s_i=s,a_j=a}$ は $s_i$ が $s$ と $a_j$ が $a$ と等しい時のみ $1$ でその他は $0$ という関数(指示関数)。そして、TD誤差の二乗を( $r(s,a,s') + \gamma q(s',a')$ が回帰を行うときの目標値と考え) $\theta_{s_i, a_j}$ について微分すると

\begin{align}
0.5 \frac{\partial \delta^2}{\partial \theta_{s_i, a_j}} 
&= - \left\{ r(s,a,s') + \gamma q(s',a') - q(s, a) \right\} \frac{\partial q(s,a)}{\partial \theta_{s_i, a_j}}\\
&= - \left\{ r(s,a,s') + \gamma q(s',a') - q(s, a) \right\} \mathbf{1}_{s_i=s,a_j=a}
\end{align}

となる。つまり、 $s$ と $a$ に対応するパラメータのみ $- \left\{ r(s,a,s') + \gamma q(s',a') - q(s, a) \right\}$ という勾配を持ち、その他は $0$ となる。なので、先ほどの学習則は、勾配法を用いた学習を行っていると考えられる。つまり、TD学習の学習則をより一般的な形として書くと

\theta \leftarrow \theta + \alpha \delta \nabla_{\theta} q(s,a;\theta)

となる。ただし今、 $\theta$ というパラメータを持つ関数 $q(\cdot,\cdot;\theta)$ を用いて行動価値関数の学習を行っているものとする。そして、 $\nabla_{\theta}$ は勾配を意味する。

こうして、ある方策 $\pi$ の行動価値関数を求める(実際には、完全に求める必要はなく、あるところで止めてよい)。そして、その行動価値関数を用いて、方策を改善する。しかし、頻繁に使われる方法は、方策を次のようなものに決めておいて、 $\beta$ の値を行動価値関数の学習と共に少しずつ大きくする方法である。

\pi(a|s) = \frac{\exp \left\{\beta q(a|s) \right\} }{\sum_{a'} \exp \left\{\beta q(a'|s) \right\}}

$\beta$ を大きくすることは、 $q(a|s)$ が高い行動を選ぶ確率を大きくすることにつながる。そのため、方策が少しだけ改善される。そこで、 $\beta$ の値を十分にゆっくりと変更していけば収束が期待される。例えば、 $\beta$ を固定して行動価値関数を学習・ $\beta$ を少しだけ大きくするという事にすれば方策反復である(かのように見えるが、以下の注意を参照)。

ただし、上記の方策を用いたとき、行動価値関数が一意の値に収束する事は保証されない。証明されてないのではなく、収束しない例が存在する。というのも、上記の方策を用いて価値関数の学習を行うことは、ダイナミックプログラミングで言うところのベルマン最適作用素を何度も作用させていることに相当する。なぜなら、方策が行動価値関数によって決まっており、学習に従って方策も変わるからだ。そう考えた時、上記の方策から定義される作用素は収縮性と呼ばれるベルマン作用素の重要な要素を満たさない。そのため、複数の固定点が存在し得る。この辺りの話は、Michael L. LittmanのPhD. Thesisと最近のA new softmax operator for reinforcement learningに書いてあるので、気になる人はそれを参照して欲しい。

そして最後に、SARSAの収束性だが、これはSutton等の本の新刊(草稿がOnline版として存在する)に記述がある。彼らによると、収束は証明されるが論文としてその結果が出ているわけではないそうだ。その後、出版されてるんですかね?

Expected SARSA

SARSAの学習則をよく見ると $a'$ は必要ないことに気付く。というのも

\left( \mathbf{T}^\pi \mathbf{q} \right) (s,a) \approx r(s,a,s') + \gamma \sum_{a'} \pi(a'|s') q(s',a')

とすれば良いからだ。そして、学習則として

\theta \leftarrow \theta + \alpha \left\{ r(s,a,s') + \gamma \sum_{a'} \pi(a'|s') q(s',a';\theta) - q(s,a;\theta) \right\} \nabla_{\theta} q(s,a;\theta)

としてしまえば良い。これをExpected SARSAと呼ぶ。

Q学習

Expected SARSAの特殊な場合として、完全にgreedy方策を用いることが考えられる。つまり

\left( \mathbf{T}^\pi \mathbf{q} \right) (s,a) \approx r(s,a,s') + \gamma \max_{a'} q(s',a')

そして、学習則として

\theta \leftarrow \theta + \alpha \left\{ r(s,a,s') + \gamma \max_{a'} \pi(a'|s') q(s',a';\theta) - q(s,a;\theta) \right\} \nabla_{\theta} q(s,a;\theta)

としてしまえば良い。これをQ学習と呼ぶ。このQ学習については収束が証明されている(関数近似を使わない場合)。

On方策とOff方策

SARSAでは、遷移先での行動が必要となる。一方、Expected SARSAとQ学習では、遷移先での行動は必要ではない。これらの違いは、行動のための方策と評価されている方策が異なることに起因する。Expected SARSAの更新則は

\left( \mathbf{T}^\pi \mathbf{q} \right) (s,a) \approx r(s,a,s') + \gamma \sum_{a'} \pi(a'|s') q(s',a')

であった。この $\pi(a'|s')$ は任意のもので良い。つまり、ある方策 $\rho$ に従って行動しながら $\pi$ に対する行動価値関数学習が可能となる。このような、行動方策と評価方策が異なる手法を Off方策手法と呼ぶ。利点は、もしかしたら良い事が起こるかも知れないが現在の評価方策が選ばない行動も学習中に使用できる。そのため、様々な探索手法が使用可能になるし、評価方策の変更後もこれまでのデータを使用できる。その代わり、学習の安定性が悪くなる事がある。On方策手法は行動方策と評価方策が同じもので、学習が比較的安定している。