OpenAI GymのFrozenLakeをQ学習で解く
前回はFrozenLakeを自前のアルゴリズムで解いてみました。今回はQ学習をやってみようと思います。
その前に、前回変な結論を出してたので訂正しておきます。前回8x8が通らなかったのは明らかに試行回数不足だと思います。1エピソードあたりの成功報酬が1なので、平均報酬はそのまま勝率を表すことになりますが、通算勝率が 0.88 なら100回中99回勝つ確率は 0.00004 程度なので、10000回では明らかに試行回数が足りないです。実際に1000000回試行したものを提出したら約10万回で通りました(ついでに初手だけ修正)。通算勝率がもう少し悪くてもこれだけ試行すれば通るはずなので、この問題に関してはいい所取り100回より通算勝率を見る方がいいかも?
また、提出前に要求水準を満たしているか調べる方法がないのかと思ってモニタのソースを読んだりしたのですが、よくわからなかったので自前で通算/いい所取り平均報酬を計算するスクリプトを書きました。使い方はモニタが出力したjsonを食わせるだけです。
今回はOpenAI Gymの本来の趣旨通りに強化学習で解いてみることにします。学習法はとりあえずQ学習にします(今のところこれくらいしか知りません)。
前提として、学習ができるためにはある程度の成功体験が必要ということがあります。学習中は何らかの方策に従って探索を行いますが、その探索でゴールに辿り着ける確率があまりに低いと学習が進みにくいと考えられます。簡単な基準として4x4, 8x8それぞれに対し完全なランダムプレイを100000エピソード行い、平均報酬を調べてみました:
| 環境 | 平均報酬 |
|---|---|
| 4x4 | 0.014 |
| 8x8 | 0.002 |
どちらもかなり低い値なので、学習中もゴールに辿り着きやすくなるように方策を工夫するか、もしくは単純に学習回数を増やすなどの対処が必要かもしれないと考えられます。
本題のQ学習に入ります。理論的なことは私より詳しい方がたくさんネット上に資料を上げてくれているので省略しますが、学習の大まかな流れは以下のようになると思います:
- 行動価値関数 Q(s,a) を任意に初期化(テーブルとして保持)
- 以下を一定エピソード数繰り返す:
- 状態 state を初期化
- 以下を一定ステップ数繰り返す(ここではターン制限まで):
- 何らかの方策により行動 act を決定
- act を実行し、次状態 state_next, 報酬 reward を得る
- Q(state,act) := (1-alpha) * Q(state,act) + alpha * (reward + gamma * max_a(Q(state_next,a)))
- state := state_next
- state が終端状態なら break
少し難しい問題になると状態空間が大きかったりして Q(s,a) をテーブルで持つことが不可能になって関数近似…とかいう話になるようですが、この問題では状態数16, 行動数4なのでそのままテーブルで持てます(というか、この問題を選んだ理由がそれだったりします)。
ここで alpha は学習率、gamma は割引率です。割引率は Q(s,a) が発散するのを防ぐとともに、同じ報酬なら遠い未来より近い未来のものを優先するといった効果をもたらすようです。
学習中の行動は「何らかの方策」により決定されるとしていますが、Q学習ではこの方策は任意ということみたいです。要は状態と行動の全ての組み合わせを網羅できるような方策であれば十分学習を繰り返せば Q(s,a) は正しく収束するということです。
実装ですが、とりあえずシンプルにしたいので「何らかの方策」はランダムプレイでやってみることにします。前述の通りこれだとなかなか成功しないので学習が遅くなりそうですが、そこは回数でカバーすることにします。
パラメータはとりあえず alpha=0.1, gamma=0.99 としました。多少実験はしましたがほとんど野生の勘で決めてます。一応学習自体はできてるっぽいのであまり深く考えない方向で。
以上の設定で106回学習後に106回テストしたところ4x4は問題なく解けました(スクリプト添付)。
同じ設定で8x8も106回学習後に106回テストしてみましたが、通算勝率 0.85, いい所取り100エピソードの平均勝率 0.98 でわずかに足りませんでした。通算勝率 0.85 だと100回中99回勝てる確率は 0.0000015 程度なので、確かに106回のテストでは通らない可能性もあります。そこで同じ設定で学習回数を107に増やしてみましたが、なぜか通算勝率 0.82, いい所取り 0.97 と成績が落ちてしまいました。原因はよくわかりませんが、ブレるということはまだ収束しきっていないのかもしれません。
学習率や割引率をいじったりしてみましたがほとんど成績が落ちるだけだったので、やはり学習時の探索がランダムプレイなせいで成功体験が少ないのが問題なのかと考えました。ということで、学習中にもQ関数を使って行動を決定するようにして、ある程度の探索を保証するためにε-greedy法(確率εでQ関数を無視してランダム選択を行う)を使うようにしてみました。
alpha=0.1, gamma=0.99, epsilon=0.1 で106回学習後に106回テストしてみたところ、一応8x8も解けました(スクリプト添付)。通算勝率は 0.864 で、自前のアルゴリズムに比べると少し劣るのでまだ改善の余地はあるのかもしれませんが、とりあえず通ったのでよしとしておきます。
