【強化学習】モンテカルロ法をExcelに実装して迷路問題を解いてみた。
モンテカルロ法とQ学習との違い
強化学習は、最終目的を達成するために、今とるべき最適な行動を学習する機械学習の一手法です。
テトリスで一列ずつ崩すのではなく、溜めて一気に何列も崩すような手を学習します。
小さな魚をチマチマ釣るより、大魚を狙う方法を学習するとも言えます。
前回はそんな強化学習の中のQ学習について理解し、Excelに実装して迷路問題を解いてみました。
>> 【はじめての強化学習】Q学習の式をExcelに実装して迷路問題を解いてみた
Q学習は与えられたQテーブルに従ってエージェントが行動し、行動の価値（Q値）を新しい状態における最大のQ値＋報酬に置き換えていくことで、Qテーブルを最適なものに更新していく方法でした。
そして、この更新は次の状態へ進むたび（ステップが進むたび）に行います。
これに対して、もう一つの代表的な方法であるモンテカルロ法では、ステップが最後まで進んで一つのエピソードが終了するまでQ値の更新を行いません。
今回は、このモンテカルロ法について理解し、Excelに実装して迷路問題で試してみます。
モンテカルロ法のアルゴリズム
モンテカルロ法では報酬しか考慮しない
まずモンテカルロ法におけるQ値の更新式を見てみましょう。
これを見て、すぐに式の意味を理解できる人はそういないでしょう。
Q学習の更新式と比べての大きな違いは、Q関数の変数sとaにtの添え字がないことです。
なぜないのでしょうか？
それはモンテカルロ法ではQ値の更新に報酬しか考慮しないためです。
Q学習では次の状態に行ったら、その状態における最大Q値＋報酬で現在のQ値を置き換えましたが、モンテカルロ法では報酬しか考慮しないのです。
そのため、今の状態のQ値と次の状態のQ値を区別する必要がありません。
一連のステップの集まりが1つのエピソードでしたね。
例えば、1番目のエピソードでは4ステップでゴールし、次のエピソードでは6ステップでゴールしたとします。
すると、1番目のエピソードではtは1から6、2番目のエピソードではtは1から6までできます。
このように、Q学習ではtを添え字に使うことによって各ステップのQ値を区別しますが、モンテカルロ法ではその必要がありません。
モンテカルロ法の報酬は各ステップの報酬の割引合計
但し、モンテカルロ法では各ステップでの報酬をQ値の更新に使いますので、rにはtの添え字が付きます。
そして、あるステップから最終ステップ（ゴール）までの報酬を割引率を考慮して合計したものがGtです。
このようにGは1つの式で書かれていますが、4ステップでゴールする場合には4つの式をまとめて表現していることに注意が必要です。
S1からゴールまでのGは、S4の状態に行った時の報酬がr1、S5の状態に行った時の報酬がr2、、、となります。
そしてS1から見るとS5はS4に比べて未来のことで不確かですので、S5での報酬に割引率γを掛けます。
このようにモンテカルロ法では各エピソードごとに1つの式でQ値を更新する式になっていますが、実際にはそのエピソードで通ったすべてのステップにおけるQ値を更新します。
最初のステップからゴールに向かってエージェントが進む方策は、Q学習と同じです。
各ステップにおいて、基本的にはQ値が最も大きな行動をとりますが、局所にはまって抜けられなくなることを避けるために、たまにQ値を無視したランダムな行動を許します。
これはε-greedy法と呼びましたね。
モンテカルロ法をExcelに実装する
前回、Q学習用のExcelシートを作りましたのでそれを元に変更します。
一つ目の変更点は、Q学習では次ステップのQ値＋報酬を求めましたが、モンテカルロ法では報酬だけを求める点です。
これについては下記のように変更します。
すると、各ステップにおける次ステップの期待報酬がP27セルに入りますので、これをコピペして別の表に記録しておきます。
各ステップでは、次ステップの期待報酬、次々ステップの期待報酬、次々々ステップの期待報酬、、、最終ステップの期待報酬を割引率を掛けて合計した値をGとして計算しますので、下記のような表をVBAで作るようにします。
そして、上で計算したα(G-Q(s,a))をQテーブルに反映させるために、一旦下図のようにQ値の変化量として別表にバッファーし、その後、元のQテーブルに反映させます。
Q値の変化量を別表に移す際には、同じ状態(s)から同じ行動(a)をとった場合のα(G-Q(s,a))は、下記のようにまとめて合計して移すようにします。
このQテーブルの更新を何エピソードも繰り返しますので、VBAで上記の操作を行いました。
Qテーブルの初期値はQ学習で行ったのと同じ全くデタラメな数値を設定しました。
また割引率は0.9、学習率は0.1としました。
100エピソード繰り返すこととし、ε-greedy法の設定値は1から1エピソード終了するごとに1%ずつ減少させました。
実行した結果、下図のようにQテーブルが更新されました。
全くデタラメなQ値からスタートしたため、最初はゴールまで到達できなかったエピソードが多かったはずですが、徐々に更新され正確なQテーブルが出来上がりました。
なぜモンテカルロ法というのか？
このように、どの状態(s)からどの行動(a)を取る場合のQ値が全く分からない状況から、エージェントを多数回ランダムに行動させることによって、どのように行動すればQ値が高くなるかを数値化し、その数値を元にQ値を推定していくためモンテカルロ法と呼ばれています。
またモンテカルロ法は、強化学習の他にも様々な所で使われています。
興味のある方は、こちらのモンテカルロ法シリーズもどうぞ。
Udemyの関連講座
データ分析シリーズ① AI数学-文系でも理解できる!高校から始めるデータ分析、AIのための数学-
データ分析、機械学習に関わる数学に絞り、効率的に学習できるようカリキュラムを構成しました。文系でも理解できるよう丁寧な説明をしています。Pythonエンジニア育成推進協会認定スクールによる高品質な数学コースです。
数学アレルギーでも大丈夫／やさしく丁寧な解説／コード無し キーワード:基礎／数学／行列／線形代数／ベクトル／微分／データサイエンス／AI／機械学習／ディープラーニング／データドリブン／人工知能
【キカガク流】人工知能・機械学習 脱ブラックボックス講座 – 初級編 –
1000人以上が受講している（株）キカガクの『脱ブラックボックスセミナー』が遂に登場！機械学習の参考書を「閉じてしまった人」への再入門に最適な講座です。微分・線形代数といった数学の基礎からPythonでの実装まで短時間で習得しましょう。