【強化学習】モンテカルロ法を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値を推定していくためモンテカルロ法と呼ばれています。
ブラックジャックの必勝法をExcelモンテカルロ法で強化学習したらこうなった。
またモンテカルロ法は、強化学習の他にも様々な所で使われています。
興味のある方は、こちらのモンテカルロ法シリーズもどうぞ。
モンテカルロ法で円周率πと任意の図形の面積を求める方法をExcelで実演！
【モンテカルロ積分】難しい積分をExcelで簡単に計算する方法を実演！
無限区間のモンテカルロ積分は被積分関数の選び方が重要である理由
モンティホール問題をベイズ推定で解いてExcelシミュレーションで検証する
重点サンプリングによるモンテカルロ積分をExcelで試して効果を見てみた。
分散の加法性で安全在庫が削減されることをモンテカルロシミュレーション
モンテカルロ法で保管効率を確率的にシミュレーション【サンプル付き】