面白いデータを探して

適当に書く。間違えていたら教えてください。

Q学習で迷路を解く

自分の趣味は将棋なのですが、GoogleDeepmindが発表したAlphaZeroの棋譜を見て、自分でも試してみたいと思ったのがきっかけ。強化学習は詳しくないし、いきなりDQN(Deep Q-Network)とかよくわからないのでとりあえずQ学習やってみましょうということでやってみた。
具体的にやったことは

  1. 強化学習の手法の1つであるQ学習について勉強した
  2. せっかくなので、Q学習で迷路を解いてみた

強化学習はあまり詳しくないため、間違いがある可能性があります。もしも間違いなどを見つけたらコメントなどで指摘いただけると非常に助かります。

Q学習について

詳しい説明は他のサイトでもたくさんなされているので省略。自分用なのでかなりざっくり。

概要

Q学習は強化学習の手法の1つ。

現在の状況 s_tでアクション aをとった場合の有効性を表す数値をQ値 Q(s_t, a)と呼ぶ。Q学習ではQ値が高い行動=価値の高い行動になるようにQ値を学習していく。

具体的には次のように値を更新する。
\begin{equation}
Q(s_t, a) = Q(s_t, a) + \alpha \left(R_{t+1} + \gamma \max_p Q(s_{t+1}, p) - Q(s, a) \right)
\end{equation}
 \alphaは学習率。 \gammaは割引率。 \max_p Q(s_{t+1}, p)は次の状態 s_{t+1}で可能なアクションのうち最もQ値が大きい値。次の状態で価値が高い行動を取ることが出きるなら、そのアクションの価値も高くしようということ。

学習

常にQ値が高いアクションばかりを選択していると、学習がうまく行かないらしい。(確かに局所解に陥る気はする)そこで、どのアクションを選択するかをQ値に比例した確率に変換したり、一定確率でランダムにアクションを選択するようにして回避するらしい(epsilon-greedy)。今回実装したのは後者。

やってみる

今回は迷路を解いてみる。
各マスごとにQtableとか準備するのも面倒くさかったので、迷路をグラフ構造にしてしまって各辺にQ値をのせるような実装をした。(状態遷移図的なイメージ)可視化もnetworkxとmatplotlibでやってくれるし、、、。また、迷路自体は棒倒し法で適当に生成している。

結果

30*30と100*100の迷路についてやってみたときのゴールまでのステップ数。
30*30だと大体80エポック、100*100で170エポック前後で最短距離でゴールに向かうようになった。ルートの可視化ははなぜかgifが保存できなかったので割愛。学習時間は30*30で2分弱、100*100で15分くらいかかった。

f:id:netres:20181224220959p:plain
30*30の迷路の実行結果

f:id:netres:20181224221031p:plain
100*100の迷路での実行結果

まとめ

Q学習を実装してやってみた。やってみての感想としては

  1. それなりにうまくいくっぽい
  2. 状態の遷移数が多いと実装やばそう

このあとはDQNあたりを実装してみたい