強化学習の基本 Qラーニングを直観的に理解するためのアニメーションによる可視化

経路探索問題を強化学習で解き、その過程をアニメーションで可視化しました。
↑↓で速度調節、Spaceで最速の学習、ドラッグ or タップで障害物の追加ができます。
これにより、強化学習で何をしているのか直観的に分かりやすくなりました。

問題設定

本アニメーションで可視化している問題の設定は、下記の通りです。

• 条件

  • $n\times n$のマスからなる離散的なフィールド
    • 固定の初期位置と目標位置(⭐)、障害物が配置されている
  • 障害物（🔴）は、踏んだら死ぬ。初期位置からやり直し
  • 自機(👾)は単位時間に8方向のいずれかへ1マス移動できる
    • 横移動と斜め移動のコストは同じ

• 得たい出力

  • 初期位置から目標位置までの、障害物を回避した最短経路

この問題を強化学習のフレームワークに落とし込み、Qラーニングで求解しています。
詳細は後述します。

各インジケータの意味

本可視化の見方を説明します。
前節で述べた問題をQラーニングで解く過程を可視化しています。

詳細

上記の可視化で表現したかった数式などを説明します。

問題を強化学習のフレームワークに落とし込む

強化学習の用語を先に説明した経路探索問題に当てはめると、下記の対応となります：

• 状態 $s$ : 自機のいるマスの位置
• 行動 $a$ : 上下左右斜め8方向の内、進む方向
• 方策 $\pi(a|s)$ : あるマス目$s$において、どの方向$a$へ進むか = 進むべき経路を示す
• 報酬 $R(s, a)$ : あるマス目$s$において、ある方向$a$に移動した結果の評価
  • 障害物を踏んだ → -100 の報酬を与える
  • 目標位置に到達した → +50 の報酬を与える
  • それ以外 → -1 の報酬を与える

この設定で強化学習を行うと、問題の解を得ることができます。
本可視化では、Qラーニングを用いて解いています。

数式で見る

各マスに表示されている緑パックマンのようなものは、行動価値関数$Q(s,a)$の値の大きさを示します。
本問題においては、状態$s$はマス目の位置、行動$a$は8方向のどれかを示します。

行動価値関数$Q$とは、ある時刻において状態が$s$のとき行動$t$を取ったときに以後得られるリターンの期待値を表します（なるほどわからん）。
とにかく、$Q(s,a)$が最大となる$a$こそが、今後のリターンが一番大きいということで、$s$における最適の行動であると言って良いでしょう。

実際、最適な行動価値関数$Q^*(s,a)$が求まれば、最適方策$\pi^*(a|s)$は直ちに

\def\argmax{\mathop{\rm arg~max}\limits}

\pi^*(a|s)= 
  \left\{
    \begin{array}{l}
      1\quad \mathrm{if}\; a=\argmax_a Q^*(s,a) \\
      0\quad \mathrm{otherwise}
    \end{array}
  \right.

と求めることができます。
方策 $\pi(a|s)$ とは、状態$s$のときに行動$a$を取る確率を表すものなので、全ての$s$についてそれぞれ行動価値関数が最大となる行動$a$を常に（確率=1）取ることが最適な方策というわけです。

実際、本可視化における$Q(s,a)$を見れば、進むと死ぬ方向や目標から遠ざかる方向は$Q$が小さく（薄く）なり、一方最短経路に従う方向は$Q$が大きく（濃く）評価されていることが見て取れますね。

ではどうすれば最適な$Q$を得られるんだという話になりますが、その一つの方法として下式に示すQラーニングを利用できます。

Q(s_t,a_t)+=\alpha[r+\gamma \max_a Q(s_{t+1},a)-Q(s_t,a_t)]

Qラーニングの解説記事はネットに沢山あるので、ここでは詳細を割愛することにします。
上式を実装してエピソードを重ねるうちに、$Q(s,a)$は最適な値へ収束していきます。
収束した後はただ最適経路をなぞるのみということは、もう見ていただけたでしょう。

この行動価値関数$Q$を学習していくというイメージを持っていれば、強化学習の話題がもう少しとっつきやすくなるはずです。
一般に多くの問題では$s$や$a$の空間が広大なので、今回のような$Q$のテーブルに頼った手法は使えません。
代わりに$Q$を連続な関数として扱い、その関数を近似します。その関数近似に深層ニューラルネットワークを用いたのがDQNです。
つまり、結局原理は同じなわけですね！

まとめ

• 強化学習の一種であるQラーニングを用いて、経路探索問題を解いた
• 解く過程をアニメーションで可視化することで、仕組みが分かりやすくなった（はず！）
• ここで得られた強化学習のイメージは、古典的なQラーニングから割と最新のDQNにまで適用可能です

参考文献

• UCLの講義資料
  • ゼロから説明されていて、分かりやすいです
  • Q学習に関連する話は第2回と第6回にあります