Q-Learningで迷路を解く
はじめに
強くなるロボティック・ゲームプレイヤーの作り方 プレミアムブックス版 ~実践で学ぶ強化学習~
↑これを読みながら強化学習の基礎と雰囲気を学んでいるのですが,
読んでるだけで飽きてきたので,実際に実装してみました.
chainerRLとか使えば簡単にできるのだろうなと思いつつ,初めてなのでC++で適当に書きました.
Q-Learningとは?
詳しくは本を読むか,色々な人が解説記事を上げているのでそちらに.
ゼロからDeepまで学ぶ強化学習 - Qiita
強化学習で迷路を探索する - Qiita
方針
報酬をゴールしたとき1,壁に移動したとき-1,その他0で設定.
探索する時の行動選択にε-greedyを用いていたのですが,上手く行かなかったため,
UCB1アルゴリズム*1を使って探索しました.
UCB1については下記リンク参照.
モンテカルロで二人ゲーム - ustimawのブログ
実装
概要
競プロ形式で迷路を標準入力から読み込み.
高さH,幅Wの次の行から,各セルの情報が空白区切りで与えられる.(0:通路,1:壁,2:スタート,3:ゴール)
エピソード数(num_episodes=10000)の学習の後,1回テストが実行されます.
実行結果
テスト実行時の動画です.'x'が現在地を表しています.
一応ゴールしました(ブログ用) pic.twitter.com/tA2EVmQqtw
— うつぼ (@utsubo_21) 2017年12月30日
Q-Learningの更新式についてメモ
説明できるほど理解できてないのですが一応.(中途半端かつ正確ではないです.)
状態の時行動を取った場合の価値関数がある.
を展開すると,期待報酬関数と次ステップの価値関数の漸化式っぽくかける.
これを,Rイコールの式にすると,
となる.
報酬関数を近似する関数と実際の報酬は,大体一致して欲しい.
そこで,誤差と定義し,これを最小化する.
最小化するようにを更新するために,TD法が提案されていて,これは大体勾配法.
TD法では,として,で更新.
は学習率.
で,は下式のように求まるので,
近似価値関数は次の式で更新するといい感じになりそう.
(正確にはここまでのQには肩に政策関数が乗ります.)
Q-Leaningでは
で更新.
*1:雰囲気実装なので合ってない