Q学習_Q-Learning(Vol.12)

はじめに

前回は、麻里ちゃんの「Q-LearningのＱってなんの略なの？」という質問にうろたえてしまい、PからQへの統計の説明に終始してしまいました。でも、おかげでＱ値が「検定結果が有意と判断される最小のFDR(false discovery rate)のこと」であることが理解できたと思います。今回は、いよいよQ-Learningという学習法について説明します。

海戦ゲーム

Q-Learningの仕組みは、”海戦ゲーム”と似ています。え、知りませんか？ 私の地元では”波高し”という名前で、子供のころ授業中に友達とよくやったものです。さすがにテレビゲームやスマホゲームの時代に、こんな手書きのゲームは見捨てられたでしょうか。でも、Wikipediaにもきちんと載っている由緒あるゲームなので、Wikiの記載例を使って簡単に説明します。

これは2人でやる対戦型ゲームです。紙に図1(R)のようなマスを書き、そこにお互いが自分の艦隊を相手にわからないように配置します。今回は、戦艦と巡洋艦と潜水艦の3隻の艦隊とします。

図1：海戦ゲーム（波高し）の2つのボード

相手が先攻だとしましょう。相手が「３のＣ」と魚雷を当てる位置を指定して攻撃してきた場合、そこに艦があったなら「命中」と伝えて艦は沈没します。今回は命中ではなく、S（潜水艦）の周囲でしたので、「波高し」とヒントを答えて惜しかったことを相手に伝えます。

さて、次はこっちの攻撃です。「２のD」を攻撃してみたところ「波高し」という応答があったので、戦略ボード（相手の艦隊）の2Dに「波」のマークを記載していきます。これで、相手の艦はこの周囲にあることがわかります。

こんな形で相互に攻撃し合うのですが、度重なる攻撃により、戦略ボード(Q)の情報がリッチになって、しだいに相手の残り艦の位置が見えてきます。そして、先に相手を全滅させた方が勝つというゲームです。パソコンもスマホもない時代、紙と鉛筆さえあれば簡単にできた、男の子のハートをくすぐる遊びなのでした。

Q-Learningとは

さて、海戦ゲームを理解したところで本題のQ-Learningの説明に入ります。Q-Learningの考え方を理解するのに有名な5つ部屋のチュートリアルがあるのですが、ここではそれをオマージュした6部屋からなる「麻里ちゃん救出ミッション」を使って説明することにします（図2）。

図2：麻里ちゃん救出ミッション

場面はＡからＦまでの部屋がある館です。エージェントはAの部屋からスタートして、Fの部屋に監禁されている麻里ちゃんを助け出しに行くものとします（わくわく）。部屋から部屋への移動の関係を表すと図3のようになります。このとき、”麻里ちゃんに会える”という移動に対しては報酬値100を与え、それ以外は報酬値0とします。麻里ちゃんのいるF部屋からF部屋への移動（つまり、ステイ）もアリとします。

さらに、これを行列風にアレンジしたものが図4Rです。状態（今いる部屋）とアクション（移動先）のマトリクスで、どこからどこに移動すれば即時報酬が得られるかの関係を表しています。

図3：部屋の移動と報酬フロー

図4R：部屋の移動と即時報酬(R)

Q-Learningでは、トレーニングによってどこに移動すればゴールに近づくかという情報を記憶して行きます。報酬はFの部屋に到達して麻里ちゃんを救出することです。そのため状態を表す(R)表のほかに、経験（探索）して得た知識を記録する戦略ボード(Qボード)を用意します。初期状態では、まだ何も経験していないのでQボードは図4Qのように全て0です。学習するにつれてこのQボードに有効な情報が書き込まれていき、その結果、Qボードを見ながらプレイすることによって、効率よく最大の報酬を得ることができるのです（海戦ゲームと同じですね）。

図4Q：部屋の移動戦略ボード0 (Q)

Qボードへの情報書込みルール

今回のQボードへの情報書込み基本ルールを以下の通りとします。

①初期状態でQボードはすべて0とする

②Qを求める計算式を設定する

  Q(状態、アクション)=R(状態、アクション）+ γ ×Max(Q(次の状態、すべてのアクション))

③γ（ガンマ）パラメータと報酬を決める

　γは割引率と呼ばれるもので範囲は0～1です。
　0に近いほど目先の報酬を重視する傾向となります。

　γ=0.8

 　報酬＝100

④エピソード（学習）を何回も繰り返して、エピソード終了ごとにQボードに値を記録していく。

⑤1つのエピソードは、ランダムに指定された状態（部屋）から始まり、最大の報酬（F部屋）に到着した時点で終了する。

⑥1つのエピソードは次のような処理で進行する（図5）。

　1.ランダムに6つの部屋のどこかを探索開始位置とする。

　2.現在の部屋から移動できるアクションの中から1つを選択する。

　3.Qの値を③の式で計算して、Qボードを更新する。

　4.移動先がF部屋ならエピソード終了。そうでない場合は移動先の部屋を現在の部屋にする。

　5.上記2番から繰り返す。

図5：エピソードnの処理フロー

エピソード1

では、⑥の手順（図5）に従い、エピソード1のシミュレーションを行ってみましょう。

1.ランダムに初期状態を選択。

　今回はルームCを初期状態とします。

2.現在の状態から移動できるアクションを1つ選択する。

　ルームCから移動できるのは、ルームBかルームFです。
　今回は、このうちルームFを選択したとします。

3.Q計算式に基づいて、Qの値を計算してQボードに書き込む

　ルームFにおいて可能なアクションは、ルームC、ルームE、ルームFの3つです。

　Q計算式に当てはめてみると、次のようになります。

　Q(C,F)=R(C,F) + 0.8 ×Max( Q(F,C),Q(F,E),Q(F,F))

　まだ最初なのでQボードは図4Qのようにすべて0となっています。

　つまり Q(F,C)もQ(F,E)もQ(F,F)も値が0ですのでMax( Q(F,C),Q(F,E),Q(F,F))は0です。

　図4Rを見ると、R(C,F)は100となっていますので、

　Q(C,F)=R(C,F) + 0.8 ×Max( Q(F,C),Q(F,E),Q(F,F))

　Q(C,F)=100+ 0.8 ×Max( 0,0,0)=100

　となり、この値をQボードに書き込むと図6Qのようになります。

4,移動先がゴール（F部屋）なら終了、そいうでなければ移動先の部屋を現在の部屋にする。

　今回は移動先がFなのでエピソード1は終了です。

エピソード2

続いてエピソード2をやってみましょう。

1.ランダムに初期状態を選択。

　今度はルームBを初期状態とします。

2.現在の状態から移動できるアクションを1つ選択する。

　ルームBから移動できるのは、ルームAかルームCかルームEです。
　今回は、このうちルームCを選択します。

3.Q計算式に基づいて、Qの値を計算してQボードに書き込む

　ルームCにおいて可能なアクションは、ルームBとルームFです。

　Q計算式に当てはめてみると、次のようになります。

　Q(B,C)=R(B,C) + 0.8 ×Max( Q(C,B),Q(C,F))

　図6Qによると、Q(C,B)は0でQ(C,F)が100なので

　Q(B,C)=0+ 0.8 ×Max( 0,100)=80

　となり、この値をQボードに書き込むと図7Qのようになります。

4,移動先がゴール（F部屋）なら終了、そいうでなければ移動先の部屋を現在の部屋にする。

　今回は移動先がCなので、再び2の状態からスタートします。

図6Q：部屋の移動戦略ボード１（Q)

図7Q：部屋の移動戦略ボード2（Q)

エピソード2の続き

2.現在の状態から移動できるアクションを1つ選択する。

　ルームCから移動できるのは、ルームBかルームFです。
　今回は運よくルームFを選択したとしましょう。

3.Q計算式に基づいて、Qの値を計算してQボードに書き込む

　ルームFにおいて可能なアクションは、ルームC、ルームE、ルームFの3つです。

　Q計算式に当てはめてみると、次のようになります。

　Q(C,F)=R(C,F) + 0.8 ×Max( Q(F,C),Q(F,E),Q(F,F))

　図7Qを参照するとQ(F,C)もQ(F,E)もQ(F,F)も値が0ですので、
　Max( Q(F,C),Q(F,E),Q(F,F))は0です。

　図4Rを見ると、R(C,F)は100となっていますので、

　Q(C,F)=R(C,F) + 0.8 ×Max( Q(F,C),Q(F,E),Q(F,F))

　Q(C,F)=100+ 0.8 ×Max( 0,0,0)=100

　すでにQ(C,F)=100なので、今回はQボードの値を変化させない結果になりました。

4,移動先がゴール（F部屋）なら終了、そいうでなければ移動先の部屋を現在の部屋にする。

　今回は移動先がFなのでエピソード2は終了です。

エピソードｎ

エピソード（経験）を積み重ねるうちにＱボードに値が次々と書き込まれ、戦略ボードとしての役割を果たすようになります。

今回は、単純なモデルなので、エピソードを繰り返すうちに収束し、最終的にＱボードは図8Ｑのようになります。

図8Q：部屋の移動戦略ボード最終（Q)

図8Qの値をパーセントにしてみましょう。最大値500で除算すると図9Qのようにパーセントで表せます。

この情報を図3のフローに当てはめると図10のようになります。学習によりこのような情報が得られていれば、エージェントがAの部屋にいたとしても最短経路で麻里ちゃんのいるF部屋にたどり着けるのです。

図9Q：部屋の移動戦略ボード最終（%表記）

図10Q：部屋の移動と報酬フロー最終（%表記）

強化学習とは

はい、チュートリアルで強化学習のイメージがつかめたでしょうか。強化学習は図11のように、ある環境において、エージェントが今の状態から行動した結果で与えられる報酬を最大化するためにエピソードを繰り返す学習法です。上記のチュートリアルでは、環境は6つの部屋ゲームで、状態は今いる部屋、行動が移動する部屋、そして報酬が麻里ちゃんに会うです。

図11：強化学習の主要素

図11の関係を将棋に置き換えてみるとどうなるでしょうか。まず、環境は将棋で、エージェントは自分ですね。そして、将来にわたる最大の価値（報酬）は将棋に勝つことです。今の状態から次の一手（行動）を指すのに、目先の利益（即時報酬）にとらわれると、捨て駒をするような手がさせません。あくまでも最後に勝つ（将来の価値）を最大化するための一手を指すのです。その道しるべを得るために、自分対自分で何百万回も対戦し、エピソードごとに結果を丹念にQボードに記憶してゆくわけです。

強化学習では、目先の報酬（Immediaterewards：即時報酬）ではなく、将来に得られる価値を最大化させるように行動します。そのため、「ある状態において、ある行動をとったときの価値」を探索（エピソード）によって求めていきます。この価値のことをQ値（状態行動価値）と呼び、得られた情報（価値の期待値）をQボードに記憶しておきます。Q値はQ(s.a)という関数で表され、sは状態、aはアクションです。例えば、図9QでQ(E,D)は64という期待値が記されています。

強化学習のアルゴリズム

強化学習にはいくつかのアルゴリズムがあります。ここでは図12のQ-Learning（Q学習）、Sarsa（サルサ）、モンテカルロ法について簡単に説明しましょう。

図12：強化学習のアルゴリズム

(1)Q-Learning

上記の「麻里ちゃん救出ミッション」では、期待値Qを求めるのに式1のような計算をしました。

　Q(状態、アクション)=R(状態、アクション）+ γ ×Max(Q(次の状態、すべてのアクション)) …(式1)

これにαというパラメータを加えると式2となり、これがQ-Learningの基本的な計算式となります。

　Q(状態、アクション)=(1-α) Q(状態、アクション) +  α(R(状態、アクション + γ ×Max(Q(次の状態、すべてのアクション))) …(式2)

αは学習率と呼ばれ、Q値の更新度合いの緩急を決めるパラメータです。この式を単純に書くと次のようになります。

　Q（現在値）=(1-α) Q(現在値) +  αQ(新しい値) 

αは0に近いほど緩慢に、1に近いほど急激に新しいQ値を反映します。式1ではα=1として1項目を省略し、最も急激にQ値を更新していたわけです。

(2)Sarsa

Sarsa（サルサ）の計算式は、式2からMax関数を取っ払った式3となります。

　Q(状態、アクション)=(1-α) Q(状態、アクション) +  α(R(状態、アクション）+ γ Q(次の状態、すべてのアクション))  …(式3)

Q-Learningでは、次の状態で取り得る（移動可能な）選択肢の中で最大の期待値を新しいQ値としていましたが、Sarsaは実際に1つずつ行動した結果でQ値を更新します。

(3)モンテカルロ法

モンテカルロ法はVol.10でもさらりと紹介しましたね。え~と、確か「ランダムに試してみて、その結果から近似値を求めるシミュレーション法」という説明でしたね。AlphaGoの指し手評価にも使われている重要な手法ですので、上記2方式との違いをもとにもう少し詳しく説明します。

モンテカルロ法もQ値（戦略ボード）を更新してゆくのは同じですが、上記２つとは違い「次の状態のQ値」という値を使いません。その代わりに報酬配列を用意します。

①とにかく報酬を得るまで行動する（図2の例ならFの部屋にたどり着くまで移動しまくる）

②そこに至るまでのアクションと得られた報酬を報酬配列にすべて記録する。

③報酬にたどり着いたら、それまでに記録した配列の平均値でQ値を式4で更新する

   Q(状態、アクション)=Ave（配列(状態、アクション))  …(式4)

モンテカルロ法は、アクションごとにQ値を更新する上記2法と違い、報酬にたどり着いた時点でそこにたどり着くまでに得た価値（配列に格納した情報）を使って一気にＱ値を更新します。「ちゃんと結果が出ない限り、あなたの日頃行った働きに対して一切評価をしないわよ」という成果主義の権化のような鬼上司なのです。

状態行動空間の爆発

麻里ちゃん救出ミッションでは、状態とアクションのマトリクス（Qボード）が小さいのでQ値も限られた数で済みました。しかし、この方法をそのまま囲碁に適用しようとするとそううまくはいきません。囲碁はマス目が19×19と大きいので、数手指しただけでも「もう、これは過去に同じ局面はないですね」などと解説者が解説します。なので、”ある局面から次の一手”という組み合わせが膨大にあり過ぎて、Qボードに保存するQ値が無限大になってしまい破綻します。この問題は、状態行動空間の爆発（The state and action space explosionploblem)と呼ばれています。

この問題を解決するために、Q値を直接求める代わりに関数で近似する方法が考えられました。ある程度Q値を取得したところで非線形関数近似を行い、すべてのQ値をプロットしなくても関数でQ値を推定できるようにするわけです（Vol.8の回帰曲線をイメージしてください）。そして、この関数近似にニューラルネットワーク技術を適用して、近似精度を向上したものがDQNなのです。

まとめ

さて、強化学習の仕組みが海戦ゲームのようなもので、どのように戦略ボードのQ値を取得してゆくかというイメージは掴めたでしょうか。強化学習は将棋や囲碁などで人間をはるかに超えられることを実証しており、金融取引でも威力を発揮しつつあるようです。今後の発展が楽しみでもあり、ちょっぴりSF的な不安も感じさせられる技術ですね。

梅田弘之株式会社システムインテグレータ：Twitter@umedano