2016-01-17 (Sun.) 01:31:22 JST
本文書ではまず Q-learning (Q学習) の概要を述べ、次に 二人完全情報ゲームである tic-tac-toe (三目並べ) への適用について説明する. 実際の実装は cympfh/tic-tac-toe にある.
状態 \(s\) のときにアクション \(a\) をしてみた. エージェントは、その結果として状態が \(s'\) に変化したことと、環境から報酬 \(r\) が来たことを観測できる.
我々の目的は、エージェントがいい感じに報酬を得るような意思決定機械 \(f\) を設計することである. いい感じ、というのは、例えば初期状態から数えて受け取った報酬を順に \(r_1, r_2, \ldots\) としたときに
\[\max \sum_{t=1}^N \gamma^{N-t} r_t (0 < \gamma < 1)\]
基本的には、こういう状態にときにこういうアクションをしたら報酬がめっちゃ来た、というのを覚えておいて、再び同じ状態になったらそれを再実践する、ということが取られる. あんまりそういうのばっかりをすると局所解に陥るので、上手い学習が必要になる. Q学習は、理論的に最適解に落ちることが保証されている.
Q-learning は強化学習の一手法である. Q-learning ではある時点の状態 \(s\) と、その時点から取ることのできるアクション \(a\) の組 \((s, a)\) に対して良さのようなものを数値として表現する. これは \(s\) の時点でアクション \(a\) を取ることが自分をどれだけ有利にするかの指標である. これを Q 値と呼び \(Q(s, a)\) と書く (quality の "q"?). 初め全ての Q 値は適当に初期化をし、十分回数、ゲームをシミュレーションを繰り返す中でこの Q を最適な値に更新していく. 遷移関数はこの Q 値を使って確率的な振る舞いを与える. すなわち、状態 \(s\) の時点でアクション \(a\) を取る確率を
\[\pi(s, a) = \frac{\exp \left( Q(s,a) / T \right)}{\sum_{a' \in \mathcal{A}} \exp \left( Q(s, a') / T \right)}\]
で与える. ただしここで \(T\) は温度と呼ばれるパラメータで、通常、初めは大きな値にしておき学習が進む中で下げることにする (\(T_0 \to 1\)). これは Q 値が大きくなるほど大きな確率でそのアクションを選択するような関数となっている. ただし \(T\) が大きい場合は Q 値の差がそれほど顕著に反映されないようになっている. 従って学習が十分でない間は、Q 値の低いアクションも積極的に選択できるように設計されている.
Q 値は次のように更新 (学習) する. 状態 \(s\) の時点でアクション \(a\) を選び、状態 \(s'\) に遷移し、報酬 \(r\) を受け取ったとする (報酬はアクションの遷移直後に受け取ることに註意). このアクション選択の良さ \(Q(s, a)\) とは、 \(r\) 及び、\(s'\) からとり得る最大の Q 値に凡そ比例すべきである. 従って、学習率 \(\alpha, \gamma\) という2つのパラメータを以って
\[Q(s, a) \leftarrow (1 - \alpha) Q(s, a) + \alpha \left[ r + \gamma \max_{a'} Q(s', a') \right]\]
と、このように更新をする. \(\gamma\) は \(0 \leq \gamma \leq 1\) であるような定数である. \(\alpha\) は学習につれて小さくなるような変数であることが求められる. すなわち時刻 \(t\) の関数 \(\alpha = \alpha(t)\) であって、しかも次の2条件が満たされる時、Q 値は最適解に収束することが保証されている.
さて、Q学習という素晴らしい古典手法が既に存在するので、意思決定機械はQ学習によって作ることにして、今度の我々の目的は、解きたいタスクを見つけて、それに適した報酬を設定することである. 報酬というのは基本的に、状態 (とアクション) をうまく評価するものでなければならない. ちゃんと数値として決まるようなタスクばかりではない.
tic-tac-toe (三目並べ) を学習させることを考えた.
しかしこれは、先ほどの枠組みがそのままは使えない. 先ほどの枠組みは、エージェントは自分一人で、ただ自分がアクションを続けさえすればよかった. これは謂わば、一人用ゲームである. 今度は二人用ゲームである.
普通に考えて、状態とは、3x3の盤面のことである. 初期状態は何も書かれてない3x3であって、マルかバツかが少しずつ埋まってくそれぞれが状態である. 普通に考えて、アクションとは自分一人が打つ手 (マルかバツかを一つ書く行為) のことである. そうすると状態は一つ進む. その状態に対してアクションを行うのは、今度は自分ではなく、相手になる. 報酬は？ どれに対して？
多少AIに甘く、設計した. 上の木はゲームツリーである. ノードは一つの状態を表す. A と書かれたノードは、「次に手を打つのはAIである」盤面に相当する. ノードから生えてるエッジは打てる手に相当する. 3本生えてるのは、打てる手が3つあって、それぞれ、打つとその先の状態に遷移する. 遷移先は黒いノードである. これは、相手の手番であることを意味する. 相手が手を打つと、また自分の手番になる.
本来、報酬を決定するはずの「遷移後の状態」を、次 (黒) と次の次 (A) で決定することにした. 具体的には
AIの負けが決定するのは、相手の手が決定したあとだからである. しかしながら、プログラムの設計上、相手の手まで待つのは嫌なので、さらに甘い設計をした.
ゲームツリーでいうところの、2ステップ先まですべてシミュレートして、予め報酬を受け取ってしまう. 本来、Q学習の枠組みでは、実際にアクションをとってしまわないと報酬がいくらか知り得ないのだが、まあ、先に報酬を知ったって、学習がスピードアップするだけだし、いいでしょ.
報酬の設定で技巧的な点としては、引き分けでもプラスの報酬があるところである. このゲームは本来、両者が最善を尽くせば引き分けで終わるゲームなのである. また、このゲームは、先手のほうが一手多く打てることが期待できるのでは、ランダムな手を打っていると先手のほうが後手より二倍程度有利でもある. 引き分けについて何も学習をしない場合、先手ばかり勝ち方を学習し、後手は何も学習できず、初手から結局どの手を打っても負けるのだと諦めてしまう.
Q学習というのはゲームツリーの上のDPだと感じた. つまりQ (quality) 関数というのは、ノードから生えてるエッジの重みである. エージェントはその重みに従った確率にしたがって勝手に手を打つので、我々はエッジの重みを正しく設定したい. しかしそのためのヒントは実際にAIが今いるノードと、その2ステップ先までしか分からない. しかもそのノードがゲームの終了状態にあるかどうかだけである (すなわち勝ち負けか引き分けかが決定する状態). 実際にすぐ先にゲームの終了状態があるエッジについては、 さっそくその重みを大幅に調整すればよい. それよりもっと上のエッジについては、何のヒント (報酬) がないので、 更に下のエッジをヒントに、重みを調整する. 逆伝播っぽいし、動的計画法ぽいなと思った.
報酬という形で、あまりにも当たり前なルールは教えてしまうことになる. つまり、今の場合、即座に自分が勝てる手があるなら打て (リーチがあるなら). そこに打った後に即座に相手が勝てる手がある場合、そこには打つな.
この程度のルールは教えることになってしまう. なので、何も学習してなくても、ランダムなAIにはかなり勝ててしまう. それでバグがあることに気づかずに数日放置していた... 学習していく過程を調べようと思い当たって初めて、何も学習していないということに気づいて、3つ以上の致命的なバグを発見し、この土曜日を潰した.
引き分けについて報酬を与えることは、かなり恣意的だ. 「勝つならそれは良い手だ」という事実を教えることとかなり程遠い. 将棋AIでは、定石を教えこむということが、たぶん今も、ある. あれは人間が発見した方法を教えることであるが、その人間が正しいとは限らない. 本当に良い方法は、相手の玉を取るのが良い手で、自分の王を取られるのが悪い手である、という2つの事実と、あとは細々とした例外的な禁じ手を教える以外のことをしないで、自然に勝ち筋を発見させることである. もちろん人間を信用するなら定石を教えたほうが早いけど.
引き分けも悪いものではないと教えたのは、このゲームを学習した収束値が引き分けだと私が偶然知っていたからである. しかしそれは人間の思い違いかもしれないのだ.