強化学習：モンテカルロ法とQ-Learning

【what is this】強化学習に関するさらなる続編です。前回のレンタカーショップ問題とは異なり、環境モデルが分からない場合の例としての迷路問題をとりあげます。そして、その解法としての、モンテカルロ法とQ-Learningの性能を観察します。

■迷路問題とレンタカーショップ問題
　先のレンタカーショップ問題では、ある状態Sにおいて行動aを取った場合に、得られる報酬rと次の状態S'が起こる条件付き確率が分かっている（計算できる）必要がありました。しかし、現実の問題ではそれを満たさない場合も多いです。以下に述べる迷路問題（開始点から終点までの最短経路を求める）もその一つです。

■モンテカルロ法とQ-Learning
　ここでは、迷路問題に対する解法として、モンテカルロ法とQ-Learningなどを検討しています。本記事は、実際のところ、これまでと同じく、中井悦司著[1]の第４章を学んだ成果を簡単に書いたものです。

　モンテカルロ法では、上に述べたような条件付き確率に頼るのではなく、シミュレーションによって、行動aに対して得られる結果の情報にもとづいて学習を行います。この方法では、シュミレーションのエピソード（episode：開始点から終了点に達する）が完了した情報が必要です。これに対して、Q-Learningと呼ばれる方法は、エピソードの完了を待たずに、１ステップ分の新しい情報を使って学習を進められる点が特徴です。

　手法の詳細は、参考文献[1]などをお読みいただきたいのですが、ここでは結果だけを示して、さらに知識を深める手掛かりとしたいと思います。図１は、両方法による迷路の最短経路の探索結果です。開始点(S)からゴール(G)を目指して、壁(#)を避けながら、上下左右のいずれかへ進みます。両方法で辿ったパスは違っていますが、ともに最適解になっているはずです。注目すべきは、学習に要した時間です。Q-Learningの方が圧倒的な高性能を示しました。

　これらの性能をさらに明確に示しているのが、図２です。学習中にどれだけの長さのepisodeを得たかを比較しています。モンテカルロ法では、初期の段階では、非常に長いepisodeを取得しながら学習しています。つまり、長いパスをさまよってなかなかゴールへ辿り着かない状況となっています。これに対して、Q-Learningでは、開始まもなく、急激に短いパスとなり、効率的に学習が行われていること示しています。

■感想

　冒頭に述べた中井悦司著[1]では、今回の第４章（Q-Learningあたり）がクライマックスと言えましょう。しかし、書籍全体の約６割を占める第３章「環境が分かっている場合」の状態価値関数による（ベルマン方程式に基づく）統計学的な厳密解の求め方までで、それに必要な基礎は出来上がっています。つまり、第３章まで熟読すれば、第４章はスムーズに理解できるはずです。この書では、非常に丁寧な叙述が特色であることを強く感じます。また、確認のためのPythonコードについても詳しい説明がついていますので、少なくとも、Pythonの初級を終えていれば、理解にはほとんど困らないと思います。

[参考文献]

[1] 中井悦司：ITエンジニアのための強化学習理論入門、技術評論社、2020年７月