Q学習で迷路を学習

昔、授業でQ学習を習ったの思い出したのでQ学習使って迷路学習させるスクリプトrubyで書いた

github.com

Q学習とは

Q学習は機械学習手法の方策オフ型TD学習の一つである。概念自体は古くから存在するが、Q学習(Q-learning)という名前で今日の手法がまとめられたのは、1989年のクリス・ワトキンズ(Chris Watkins)の論文に端を発する。
Q学習は有限マルコフ決定過程において全ての状態が十分にサンプリングできるようなエピソードを無限回試行した場合、最適な評価値に収束することが理論的に証明されている。実際の問題に対してこの条件を満たすことは困難ではあるが、この証明はQ学習の有効性を示す要素の一つとして挙げられる。
Q学習 - Wikipedia

なんか難しい感じだけど、マルコフ条件の元で状態遷移する場合(ある状態は直前の状態からのみ影響を受ける場合)、無限回試行すると、最適な行動を学習出来るってことらしい。たぶん

Q値の更新

Q学習のきもはQ値の更新で
f:id:ogidow:20151124001819p:plain
でQ値をどんどん更新していく
Q学習で迷路を学習するときのイメージは複数回試行することで報酬(ゴール)がどんどん伝搬していって各状態におけるQ値が決まっていく感じ

実験

こんな感じの迷路を学習させてみた

#####################
#S   0   0    0    0#
#0 -10   0    0    0#
#0   0 -10    0  -10#
#0 -10   0    0    0#
#0   0   0  -10   50#
#####################

Sが初期位置で右下の50がゴールになっている

この迷路を5000ステップ学習して、学習したQ値を使って迷路を解いた
学習時の行動選択は、ある小さな確率εでランダムに選択し、それ以外では Q値の最大の行動を選択するε-グリーディ法を利用した。

学習したQ値を利用して迷路を解いたところ、以下のような結果になった

x: 0 y: 0
   @   0   0   0   0
   0 -10   0   0   0
   0   0 -10   0 -10
   0 -10   0   0   0
   0   0   0 -10  50

x: 1 y: 0
   0   @   0   0   0
   0 -10   0   0   0
   0   0 -10   0 -10
   0 -10   0   0   0
   0   0   0 -10  50

x: 2 y: 0
   0   0   @   0   0
   0 -10   0   0   0
   0   0 -10   0 -10
   0 -10   0   0   0
   0   0   0 -10  50

x: 2 y: 1
   0   0   0   0   0
   0 -10   @   0   0
   0   0 -10   0 -10
   0 -10   0   0   0
   0   0   0 -10  50

x: 3 y: 1
   0   0   0   0   0
   0 -10   0   @   0
   0   0 -10   0 -10
   0 -10   0   0   0
   0   0   0 -10  50

x: 3 y: 2
   0   0   0   0   0
   0 -10   0   0   0
   0   0 -10   @ -10
   0 -10   0   0   0
   0   0   0 -10  50

x: 3 y: 3
   0   0   0   0   0
   0 -10   0   0   0
   0   0 -10   0 -10
   0 -10   0   @   0
   0   0   0 -10  50

x: 4 y: 3
   0   0   0   0   0
   0 -10   0   0   0
   0   0 -10   0 -10
   0 -10   0   0   @
   0   0   0 -10  50

ちゃんと解けてるっぽい

結構楽しかったので、これを気に機械学習とかちゃんと勉強してみたい