Q学習-最良経路を学習するスクリプト書いた (powered by Python)

Programming Python

概要

講義の課題でQ学習について実装してみたので、スクリプト等を晒してみる.

          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   0 100   #
          #   #   #   #   #   #   #

こんな感じの迷路において、S(start地点)からより良い報酬("100")までの経路をQ学習を用いて学習させるという話.


Q学習-概要

Q学習（-がくしゅう、英: Q-learning）は、機械学習分野における強化学習の一種である。Q学習は機械学習手法の方策オフ型TD学習の一つである。Q学習は有限マルコフ決定過程において全ての状態が十分にサンプリングできるようなエピソードを無限回試行した場合、最適な評価値に収束することが理論的に証明されている。実際の問題に対してこの条件を満たすことは困難ではあるが、この証明はQ学習の有効性を示す要素の一つとして挙げられる。

http://ja.wikipedia.org/wiki/Q%E5%AD%A6%E7%BF%92

強化学習で有名な手法らしい. TD(Temporal difference:時間差分)学習の一つらしい.

参考

キモはQ値の更新式！

Q(s_t, a) \leftarrow Q(s_t, a) + \alpha\left[r_{t+1} + \gamma\max_pQ(s_{t+1}, p) - Q(s_t,a)\right]
この式を掴めれば、Q学習はものにできたようなものだと勝手に思っている.

簡単に、この式がどういったことを表しているのかを書いてみる. ( \alpha が学習率、 \gamma が割引率と言われている.)
この式の目的は、ある状態 s_t における最良な行動 a を選ぶための基準を、各状態における各行動での評価値 Q(s_t, a) を更新するような処理をしたい. 行動の重みづけをするようなイメージ.
基本的なアイディアは、良い報酬につながるような行動を選ぶようにしたいので、良い報酬を得られる行動 a は良い行動. その報酬を得られる行動ができる状態に行けるための行動もちょっぴり良い行動といったような感じで良い報酬に近づいていく行動に対して、良い重みづけをしていくようなイメージ. 悪い行動に対しても同様に悪い重みを与える.

学習率 \alpha

\alphaが大きくなるほど、更新時の影響が強くなる.

割引率 \gamma

\gamma次の行動の影響度を表す. 値が大きいほど、次の状態での行動が効いてくる.


学習させた結果

1エピソードを報酬が得られるまでの行動遷移として、1000エピソードの全行動分、Q値を更新させた.
その時の行動選択アルゴリズムはε-greedy法を用いた. (スクリプトは長くなってしまったので記事の後ろの方に載せました.)

以下の図は、その1000エピソード分学習したQ値を用いて、今度はgreedy法を適用して行動選択させてみた様子.
ちゃんとスタート地点から最短距離で最高の報酬100ポイントに向かっているのがわかる.
ちなみに実行のたびに経路は変わる.(ε-greedyのランダム性のため。)

--- 盤面情報 "#": 壁, "S": スタート地点, "@": 今いる座標, "数値": その座標での報酬 ---

----- Dump Field:  -----
          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   0 100   #
          #   #   #   #   #   #   #

----- Dump Field: (2, 1) -----
          #   #   #   #   #   #   #
          #   S   @   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   0 100   #
          #   #   #   #   #   #   #
        state: (1, 1) -> action:(2, 1)

----- Dump Field: (3, 1) -----
          #   #   #   #   #   #   #
          #   S   0   @ -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   0 100   #
          #   #   #   #   #   #   #
        state: (2, 1) -> action:(3, 1)

----- Dump Field: (3, 2) -----
          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   @   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   0 100   #
          #   #   #   #   #   #   #
        state: (3, 1) -> action:(3, 2)

----- Dump Field: (3, 3) -----
          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   @ -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   0 100   #
          #   #   #   #   #   #   #
        state: (3, 2) -> action:(3, 3)

----- Dump Field: (3, 4) -----
          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   @ -10   0   #
          #   0 -10   0   0 100   #
          #   #   #   #   #   #   #
        state: (3, 3) -> action:(3, 4)

----- Dump Field: (3, 5) -----
          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   @   0 100   #
          #   #   #   #   #   #   #
        state: (3, 4) -> action:(3, 5)

----- Dump Field: (4, 5) -----
          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   @ 100   #
          #   #   #   #   #   #   #
        state: (3, 5) -> action:(4, 5)

----- Dump Field: (5, 5) -----
          #   #   #   #   #   #   #
          #   S   0   0 -10   0   #
          #   0 -10   0   0   0   #
          #   0 -10   0 -10   0   #
          #   0   0   0 -10   0   #
          #   0 -10   0   0   @   #
          #   #   #   #   #   #   #
        state: (4, 5) -> action:(5, 5)

スクリプトを晒す

スクリプトの処理内容:
  1. 最初に盤面情報を出力
  2. LEARNING_COUNT(1000回)分 エピソード経過させ、Q値を学習.
  3. 学習後、Q値の情報を出力.
  4. greedy法で学習したQ値の観点で1 エピソードの行動選択をさせ、その遷移を出力.
スクリプト

最後にスクリプト170行ほど。冗長になってしまった感は否めない。もっとスマートに書けるアドバイス等していただけると嬉しいです。

続きを読む