utsubo’s blog

競技プログラミングとか.

Q-Learningで迷路を解く

はじめに

強くなるロボティック・ゲームプレイヤーの作り方 プレミアムブックス版 ~実践で学ぶ強化学習~

↑これを読みながら強化学習の基礎と雰囲気を学んでいるのですが,
読んでるだけで飽きてきたので,実際に実装してみました.
chainerRLとか使えば簡単にできるのだろうなと思いつつ,初めてなのでC++で適当に書きました.

Q-Learningとは?

詳しくは本を読むか,色々な人が解説記事を上げているのでそちらに.
ゼロからDeepまで学ぶ強化学習 - Qiita
強化学習で迷路を探索する - Qiita

方針

報酬 R(s_t,a_t)をゴールしたとき1,壁に移動したとき-1,その他0で設定.
探索する時の行動選択にε-greedyを用いていたのですが,上手く行かなかったため,
UCB1アルゴリズム*1を使って探索しました.

UCB1については下記リンク参照.
モンテカルロで二人ゲーム - ustimawのブログ

実装

実行環境
概要

競プロ形式で迷路を標準入力から読み込み.
高さH,幅Wの次の行から,各セルの情報が空白区切りで与えられる.(0:通路,1:壁,2:スタート,3:ゴール)

エピソード数(num_episodes=10000)の学習の後,1回テストが実行されます.

実行結果

テスト実行時の動画です.'x'が現在地を表しています.

Q-Learningの更新式についてメモ

説明できるほど理解できてないのですが一応.(中途半端かつ正確ではないです.)
状態 s_tの時行動 a_tを取った場合の価値関数 Q(s_t,a_t)がある.
 Q(s_t, a_t)を展開すると,期待報酬関数 Rと次ステップの価値関数 Q(s_{t+1},a_{t+1})の漸化式っぽくかける.

Q(s_t,a_t) = \sum γ^tR(s_t,a_t) = R(s_t,a_t) + γQ(s_{t+1},a_{t+1})


これを,Rイコールの式にすると,

R(s_t,a_t) = Q(s_t,a_t) - γQ(s_{t+1},a_{t+1})
となる.


報酬関数 R(s_t, a_t)を近似する関数 \hat{R}(s_t,a_t)と実際の報酬 r_tは,大体一致して欲しい.
そこで,誤差 \Delta R(s_t, a_t) \equiv \frac{1}{2} (r_t - \hat{R}(s_t,a_t))^2と定義し,これを最小化する.


最小化するように Q(s,a)を更新するために,TD法が提案されていて,これは大体勾配法.
TD法では, d = \frac{\partial \Delta R}{\partial \hat{Q}}として, \hat{Q}(s_t,a_t) = \hat{Q}(s_t,a_t) - \alpha dで更新.
 \alphaは学習率.


で, dは下式のように求まるので,
 d = \frac{\partial \Delta R}{\partial \hat{Q}} \propto -r + R(s,a)
近似価値関数は次の式で更新するといい感じになりそう.
 \hat{Q}(s_t,a_t) \leftarrow \hat{Q}(s,a) + \alpha (r_t - \hat{Q}(s_t,a_t) + \gamma \hat{Q}(s_{t+1},a_{t+1}))

(正確にはここまでのQには肩に政策関数 \pi が乗ります.)


Q-Leaningでは
 \hat{Q}(s_t,a_t) \leftarrow \hat{Q}(s,a) + \alpha (r_t - \hat{Q}(s_t,a_t) + \gamma \max_{a'}{\hat{Q}(s_{t+1},a'))}
で更新.

*1:雰囲気実装なので合ってない