【強化学習】Q学習のアルゴリズムをExcelに実装して迷路問題を解いてみた。
Q学習はAlphaGoで有名な強化学習の基本
強化学習は機械学習の一分野で、管理人がサプライチェーンマネジメントに最も有用と考えている手法です。
なぜなら、それは最適化を目的とする手法で、人間を凌ぐ判断ができる可能性があるためです。
一つの例は、霊長類最強と言われた棋士を破り号泣させたという「AlphaGo」です。
これはプロ棋士が与えた教師データによる知識だけではなく、自己対戦による強化学習も行いながら、人間を超える判断ができるようになりました。
強化学習は不確かな将来の価値を最大化させるような最適化が得意で、同じような特性を持つサプライチェーンマネジメントで人間以上の判断ができるようになる可能性があります。
ピッキングロボット等のように単に人間が行っていることを機械で代替するAIではなく、人間以上に賢い判断ができるようになる可能性を秘めたAIなのです。
今回は、そんな強化学習の中で最も基本となるQ学習について、その考え方を理解した上で実際にExcelに実装して簡単な迷路問題を解いてみたいと思います。
Q学習のアルゴリズム
Q学習は秘宝マップをアップデートすること
Q学習とはファンシーな名前ですが、考え方もファンシーです。
秘宝の見つけ方を描いた秘宝マップをアップデートしていく作業に似ているからです。
見知らぬお爺さんから次のような秘宝マップを貰ったとします。
但し、お爺さんは詐欺師で、この秘宝マップもガラクタかもしれません。
それでもあなたは本当かもしれないと思い、秘宝を求めて旅に出ます。
S1からは東か南しか行けませんが、東へ行く方が多くの幸せがあると書いてあります。
あなたはS2へ進みますが、そのまま秘宝マップを信じて行ったら爆弾がありました。
一命は取り留めましたが、あなたはこの秘宝マップは間違いだったことに気づき、子孫のために
「S1から東へ進むと20の幸福がある」
という記述を
「S1から東へ進むと5の幸福がある」
という記述に修正します。
このように実際に探検してみて、秘宝マップを子孫のためにアップデートして行くのです。
Q学習はこのやり方にとても良く似ています。
それでは、具体的なアップデート方法を見ていきましょう。
Q学習では秘宝マップのことをQテーブルといいます。
Qテーブルとはある状態でとるアクションの価値（Q値）を一覧表にしたものです。
例えば、次のような表です。
縦軸に状態、横軸にアクションを書いて、Q値をマトリクス状に書いています。
この表では、S1にいる時には南へ行く方がQ 値が大きいので、あなたは南へ行きます。
するとS4に着きます。
S4の状態に着いた時のQ値を調べてみると、東へ行くことが30、南へ行くことが40、北へ行くことが50と書いてあります。
ここでも、Q値が一番大きなアクションを取るのが自然ですので、あなたは北へ行くことになります。
ということは、S4に行くことはQ値でいうと50の価値があることになります。
S1にいる時の一番大きなQ値は20でしたから、S4に行くとQ値は30増えると考えられます。
S1から南へ行くQ値は20でしたが、実際に行ったら50だったのです。
ですので、あなたはS1から南へ行くQ値を50に書き換えます。
そしてこれを繰り返してめでたくS9まで辿り着ければ、更新したQ値はそれなりに意味あるものと言えます。
ゴールへ向かうために報酬を与える
しかしこれをコンピュータにやらせるには、S9に辿り着くことに対して、何らかの報酬を与えておかないといけません。
あなたは秘宝を手に入れるという不純な動機がありますが、コンピュータにはその動機がないためです。
そこで、S9に辿り着いたらQ値換算で100が貰えるようにします。
そうすれば、S9に向かうルートのQ値が大きくなり、コンピュータのアルゴリズムはそっちへ向かおうという気になります。
その他の報酬は下記の通りとしましょう。
この場合、Q値にはこの報酬も加えて、次のように更新します。
学習率と割引率で更新のスピードを調整する
後は、勾配降下法やニューラルネットワークでも設定したようなハイパーパラメータで、更新のスピードを調整します。
Q学習のハイパーパラメータは2種類あります。
学習率と割引率です。
学習率は、新しく発見したQ値を何％反映させて、今のQ値を残り何％反映させるかを表します。
先の例でいうと、今のQ値が20で、新しく発見したQ値が51ですから、学習率が30%の場合は
更新後のQ値＝51×30%＋20×70%＝29.3
となります。
あまり急激には変えないということです。
割引率は新しく行った先のQ値をどれくらい割り引くかを表します。
新しく行った先のQ値の中から最大値を取って、前の場所のQ値を更新しますので、もしこの割引率がないと下図のようなことになってしまいます。
つまりS9へ通ずるルートのQ値は、いずれすべて100になってしまいます。
こうなると数学的に最適値に収束しないことが知られています。
またQ値は最終目的を達成することにどれだけ貢献するかを示す価値ですので、S9に近いほど大きく、S9から離れるほど小さくなるはずです。
そうなるためには、新しく行った先の最大Q値で元のQ値を書き換える際に、１未満の数字を掛けて割り引く必要があります。
これが割引率γです。
Q学習の計算アルゴリズム
以上の考え方をまとめて数式にすると、下記のようになります。
Q値は状態(state)とアクション(action)の関数ですのでQ(s,a)のように表し、現在を表すためにtを、次の状態を表すためにt+1を添え字として付けます。
実際のプログラミングでは、上式を少し式変形した次式を使うことが多いようです。
Q学習をExcelに実装して迷路問題を解いてみる
ε-greedy法により探索もさせる
それでは、このアルゴリズムをExcelに実装して、冒頭の迷路問題を解いてみましょう。
その前に、ε-greedy法についても触れておきます。
Q学習ではQ値の大きい方向へ進みながらQテーブルを更新していくわけですが、初期値はテキトーに決めます。
そのテキトーに決めたQ値によっては、悪い方向へ進むQ値が大きくなっていることも十分にあり得ます。
しかしそうすると、罠にはまって抜けられなくなってしまい、いつまで経ってもゴールに辿り着けませんので、たまにはQ値を無視したアクションを取ってもいいようにしてあげます。
遺伝的アルゴリズムにおける突然変異と同じ考え方です。
具体的には予め0から1で割合を決めておいた上で0から1の乱数を発生させ、乱数が予め決めておいた値より小さければ、Q値を無視してランダムなアクションをとる（ランダムな方向へ行く）ようにします。
このランダムなアクションのことを探索といいます。
これに対して、Q値に基づいて取るアクションのことを利用とか活用といいます。
Excelシートに計算式を入力する
それではExcelに実装していきましょう。
まず、各種設定値やハイパーパラメータを入力します。
左側の設定値は問題ないと思います。
右側の探索表は、ε-greedy法で探索をする場合にどのアクションを取るかを決めるための表です。
各状態で取れるアクションの種類は限られていますので、その限られたアクションが同じ確率で選択されるようにしきい値を予めこのように設定しておきます。
その上で、0から1までの乱数を発生させれば、しきい値と比べることにより各アクションが同じ確率でランダムに選択されるようになります。
Qテーブルについては、新しい状態に移る度に更新しますので、更新前後のテーブルを用意しておきます。
そして再び次の状態に移る場合には、その前に更新後のテーブルを更新前のテーブルにコピペすることをVBAで行わせます。
その他の計算式は次のように入力しました。
収束するまでエピソードを繰り返す
その他の特記事項は以下の通りです。
- 10回アクションする（移動する）ことを何度も繰り返します。10回のアクションを1エピソードと呼び、収束するまでVBAで何回もエピソードを繰り返します。
- 10回のアクション（1エピソード）でS9に辿り着けた場合には、その結果出来上がったQテーブル（10回更新したことになる）を次のエピソード開始のQテーブルとして使います。
- 10回のアクションでS9に辿り着けなかった場合には、そのエピソードで更新したQテーブルは棄却して、次のエピソードでは今回のエピソード開始時と同じQテーブルからやり直します。
- ε-greedy法におけるεの設定値は学習開始時には1とし、1回S9に辿り着く度にその辿り着いた回数で割ります。例えば2回S9に辿り着いた場合には、次にS9に辿り着くまでεは1/2=0.5とします。こうすることにより、学習開始時にはQ値によらずすべて探索でアクションを決定し、学習が進むにつれて探索の割合を減らしていくことができます。
- S9に辿り着くエピソードが20回連続続いたら収束と判定しました。
- Qテーブルの初期値は下記のようにテキトーに設定しました。
学習結果を確認
学習した結果、下図のように25エピソード目で収束しました。
うち、S9まで到達したエピソード数は22です。
S1からスタートする秘宝マップは、Q値の大きい方向へ進んで行けば確実にS9まで辿り着けるように更新されました。
尚、強化学習でQ値を更新するアルゴリズムには、今回紹介したQ学習の他にモンテカルロ法があります。
こちらは、ステップごとにQ値を更新するのではなく、エピソードが終わるまで待って一気に更新する方法です。
こちらで解説しています。
【強化学習】モンテカルロ法をExcelに実装して迷路問題を解いてみた。