こんにちは、らくとあいすです。

先日VRChatワールド"UDON AI -tic tac toe-"をパブリック化しました。今回はその内部で使われている強化学習と、UdonSharp*1を用いたVRChatでの実装の要点を記事にしたいと思います。公開されているワールドではでは三目並べを題材としていますが、単純なサンプルとして経路探索を題材としたものをGitHubにて公開しました。実装の詳細などはこちらを併せて見て頂ければと思います。 MITライセンスにて公開しておりますので、改変等行って頂いても構いません。

VRChatの中で学習できる強化学習をつくりました！
三目並べをAI同士で対戦させたり人と戦ったりして段々強くなります。
ワールド名"UDON AI -tic tac toe-"で公開していますので、ぜひ遊んで行ってください！#MadeWithUdon #VRChat #UDONAI #強化学習 pic.twitter.com/1x3SYa1jsM
— らくとあいす (@rakuraku_vtube) 2020年4月13日

github.com

強化学習

囲碁や将棋など、勝敗が付くまで今の行動が良かったのか悪かったのかわからないといった問題に直面した時、最適な行動を選択するにはどうしたら良いでしょうか？人は、このような問題に対して過去の経験を頼りに最も良さそうな選択を選んでいくことが多いと思います。機械(AI)で同じことをやろうと思うと、この"経験"や"良さそう"や"悪そう"をうまく教えてあげる必要があります。強化学習は、過去に得られた良い経験、悪い経験から、今どのような行動をすべきかを学習する枠組みです。以降では簡単のために次のような単純な状況を考えます：

f:id:Raku_Phys:20200425205708p:plain — シンプルなダンジョン

Playerは地点0からスタートし、1-1から2-4の地点に移動していきます。各地点には正または負の得点が用意されており、通過した段階でPlayerは得点を手に入れます。ただし、Playerは事前に得点を知ることは出来ません。以降ではPlayerのいる地点を状態 $s$ 、どちらの分岐に進むかの選択を行動 $a$ 、手に入れる得点を報酬 $r$ と呼ぶことにします。

マルコフ決定過程

強化学習はマルコフ決定過程と呼ばれる環境のもとに定義されます。マルコフ決定過程とは、遷移後の状態 $s'$ 及び得られる報酬 $r$ は、直前の状態と行動の組 $(s,a)$ にのみに依存することを表します。ダンジョンの例で言えば、次の状態と得られる報酬は、「今どこにいて」「どちらの道を選ぶのか」にのみ依存するということです。ここで、時間と共に報酬が減っていったり、予期しない敵の襲来で違う地点に飛ばされたりする場合、これはマルコフ決定過程ではなくなります。もちろん、これらの要因を状態 $s$ に含めて $s=(地点,時刻,敵の位置)$ 　などとすれば、上記の例もマルコフ決定過程となります。すなわち、マルコフ決定過程は、結果に影響を与えるあらゆる条件がすべて観測可能である(=状態として表現されている) ことを表しています。

行動価値関数

マルコフ決定過程に従う時、現在の状態 $s$ においてどのような行動 $a$ を取るかによって得られる報酬 $r$ は決められます。では、最終的に最も多い報酬を得られる選択をするには、どのように考えるのが良いでしょうか？その指標となるのが行動価値関数 $Q(s,a)$ です。 $Q$ は、ある状況 $s$ において行動 $a$ を取ることの価値を表します。ダンジョンの例で言えば、地点0から地点1-2(down) を選んだ場合、直近の報酬は最大となります。しかし、次の手まで見通すと最終的に得うる報酬は地点1-1(up) を選んだ場合に最大となります。従って、地点0における $Q$ は

$Q(0,up)>Q(0,down)$

を満たすべきと考えられます。このように、直近の報酬だけではなく、遠くの報酬も見越して行動の価値 $Q$ を設計する必要があります。

ベルマン方程式

最終的に得られる報酬を最大とする行動価値関数 $Q(s,a)$ は、次のベルマン方程式を満たすことが知られています*2 *3：

$Q(s_t,a_t) = r_{t+1} + \gamma Q(s_{t+1},a_{t+1})$

すなわち現在の行動の価値は、直近の報酬と次の行動の価値に割引率 $\gamma$ を乗じたものの和として与えられます。式を見るとわかるように、 $\gamma$ は未来の報酬の価値を減衰させる効果があり、例えば $\gamma=0$ とすると直近の報酬のみを見て行動を選択するような行動価値関数となります。ダンジョンの例において、ベルマン方程式に従う $Q$ を記入すると次のようになり、 $Q$ の大きい行動を選択することによって、正しく報酬+10の地点にたどり着けることがわかります。

f:id:Raku_Phys:20200425230738p:plain — ベルマン方程式を満たす $Q$ (割引率 $\gamma=0.9$ )

Q学習

ベルマン方程式を満たすように $Q$ を設計することで、 $Q$ のより大きい行動を選択することが最終的な報酬を最大にすることがわかりました。しかし、ベルマン方程式に従う $Q$ は漸化式であるため、それ以降のすべての状態及び報酬を知らなければ計算することが出来ません。例えば、はじめに地点0を出発するPlayerにとってupを選択すべきかdownを選択すべきかを決める手がかりは何もありません。そこで、強化学習では実際に何度も行動してみて得られた報酬から、段階的に $Q$ の値をベルマン方程式で表される最適な値に少しずつ近づけていく(学習する) ことを考えます。その手法のひとつがQ学習です。Q学習では現在の $Q(s_t,a_t)$ を、行動後に得られる報酬 $r _{t+1}$ 及び、次の状態における $Q$ の最大値 $\underset{a}{{\rm max}}Q(s_{t+1},a_{t+1})$ を用いて次のように更新します：

$Q(s_t,a_t)\leftarrow Q(s_t,a_t) + \alpha(r_{t+1}+\gamma\underset{a}{{\rm max}}Q(s_{t+1},a_{t+1})-Q(s_t,a_t))$

ここで $\alpha$ は学習率と呼ばれる量です。例えば $\alpha=0$ においては、あらたに得られた経験によって $Q(s_t,a_t)$ が変化せず全く学習が進みません。一方で $\alpha=1$ においては、今までに得られた経験のみから $Q(s_t,a_t)$ をベルマン方程式に従う形に急激に変化させます。ダンジョンの例でQ学習の様子を示したのが次の図です。

f:id:Raku_Phys:20200426151415p:plain — Q学習の様子(学習率 $\alpha=0.3$ 、割引率 $\gamma=0.9$ )

Q学習の様子(学習率 $\alpha=0.3$ 、割引率 $\gamma=0.9$ )

まず初期状態では①のようにランダムなQ値がふられています(いわば初期の思いこみ・勘です)。その後Q値のより大きい1-2に進む選択をすると、そこで得られた報酬 $r_{t+1} =1$ 及び、次の行動で得うる最大のQ値(=0.1)により、Q値が更新されます。次もQ値のより大きい2-4に進む選択をすると、ここでは－10の報酬を得ます。次に取りうる行動はないので、ここでは報酬のみを用いてQ値を更新します。この時点で2-3に進むQ値と2-4に進むQ値が逆転したため、以降は2-4に進まないようになりました。このように行動を繰り返すことで、Q値を更新していきます。

$\epsilon$ -greedy法

ダンジョンの例では、一度目の探索の結果、2-4にたどり着くという最悪の結果を避けることが出来るようになりました。さて、ここでもう一度④を見てみましょう。

f:id:Raku_Phys:20200426154654p:plain — 1度目の学習終了時点のQ値の割り当て

これを見ると、二回目の行動では[0→1-2→2-3]という経路を通り再びQ値が更新されます。そして三回目以降も同じルートを辿り続けることがわかります。一方で、Playerにとって最も高い報酬を得ることが出来るルートは、[0→1-1→2-1]です。このように、Q学習においては、より高い報酬を得る行動が存在するにも関わらず別の行動に囚われてしまうといった問題が生じることがあります。

そこで、確率 $\epsilon$ でランダムな行動を取り、確率 $1-\epsilon$ でQ値を最大にする行動を取ることを考えます。すると、ランダムな行動においてはいかなるルートも選択されうるため[0→1-1→2-1]のようなルートも探索されうることが期待されます。言い換えれば

"ちょっと向こうも見にいってみようぜ！" "危ないけど $\epsilon$ の確率でなら君の意見をきこう。"

ということです。このような手法を $\epsilon-$ greedy法といいます。

UdonSharpを用いた実装の要点

さて、これまでに見てきたことをUdonSharp(U#)を用いて実装することで、VRChat上での強化学習を可能にすることを考えます。とはいえ、U#が大変すばらしいために、ほとんどC#で書けば良いというだけになっていますので、ここでは要点のみ解説することにします。実装の詳細はGitHubで公開しているコードを参照いただければと思います*4。以降では、比較的シンプルに実装出来る次のようなタスク "From Corner To Corner"を題材とします:

$4\times4$ の16マスの盤面で行われる
Player(青丸) はGoal(赤丸) を出来るだけ短い手順で目指す
Player(青丸) は上下左右の４方向に移動できる。
盤面の外に出たら失格

f:id:Raku_Phys:20200426174732p:plain — From Corner To Corner

このルールにおいて、Playerの持っている状態 $s$ は盤面上での位置であり、行動 $a$ は上下左右の4択となります。これらはすべて観測可能である(=マルコフ決定過程に従う) ので、このタスクは強化学習で学習可能であると考えられます。

Qtable

Q学習の学習結果は、各行動と状態の組 $(s_t,a_t)$ に対応するQ値です。これは最もシンプルには、 $s_t\times a_t$ の行列 (二次元配列)に値を詰めていくことで実装可能です。ただしU#(およびUdon) では(2020/04/26) 現在、多次元配列に対応していないため一次元配列で実装する必要があります。ここではこの一次元配列をQtableと呼びます。取りうる状態と行動の組の数は状態数16と行動数4の積で64なので*5 *6 *7、Qtableを次のように宣言できます:

private float[] qTable = new float[64]; //(s,a)=>s*4 + a

ここで、特定の状態 $s$ と行動 $a$ に対するQ値は、 $Q(4s+a)$ と定めておくこととします。

Start処理

学習の開始地点としてQ値を乱数で初期化する必要がありますが、U#においてStart関数が呼ばれるタイミングなどに不安定性があるので、Update関数内で一度だけ呼ばれる処理をしておいた方が安定するようです*8。次のコードはその一例です:

void Update()
    {
        if (first)
        {
            boardMat = boardObj.GetComponent<MeshRenderer>().material;
            InitQTable();
            first = false;
        } 
    ...
    ...
    }

学習部分

Q学習を行うにあたり、まずは報酬を定義する必要がありますが、今回は次のように報酬を定めました：

ゴールに到達→1点
盤面を外れる→－1点
毎ステップ→－0.1点

これによって盤面を外れず・ゴールを目指すような行動が優先されるようになります。さらに毎ステップ弱い罰則を科すことで、なるべく短い手順でゴールを目指すような行動が優先されるようになります。次にこの報酬に従い、Q学習の更新式を実装します。Q学習の更新式は次に取りうる行動がある(ゴールや失敗をしていない) 場合と、次に取りうる手がない場合で変わるので、そこに注意して次のように実装します。

private void Train()
    {
        float reward = GetReward();
        int Qid = lastState * 4 + act;//Q(st,at)=>Q(st*4+at)
        
        if (goal | fail)
        {
            qTable[Qid] = qTable[Qid] + alpha * (reward - qTable[Qid]);
        }
        else
        {
            int nextQid = state * 4 + QTableSelect();//max(Q(st+1,at+1))
            qTable[Qid] = qTable[Qid] 
                         + alpha * (reward + gamma * qTable[nextQid] - qTable[Qid]);
        }
}

行動の選択

行動の選択は $\epsilon-$ greedy法で行います。0から1の間の乱数が $\epsilon$ よりも小さい場合にはランダムな行動を選択し、そうでない場合にはQ値を最大とする行動を選択します。ただし本実装では、 $\epsilon$ は学習の経過とともに小さくする $\epsilon$ -decayという手法を用い、段々とランダム性を弱めていくようにしました*9。

private int GetAct()
    {
        //epsilon-greedy
        int a = 0;
        if (Random.Range(0.0f, 1.0f) < epsilon)
        {
            a = Random.Range(0, 3);//ランダムで行動を選択
        }
        else
        {
            a = QTableSelect();//最も高いQ値となる行動を選択
        }
        return a;
    }

おわりに

本記事では、強化学習の一手法であるQ学習の概要を紹介し、U#を用いた実装例について要点を解説しました。強化学習は、状態・行動・報酬をうまく設計することが出来れば様々なタスク・ゲームに応用することが可能です。今回公開した経路探索のサンプルでも、途中に障害物をおいてそれを避けるような構成にしたり、妨害者がランダムに表れるようにしたりといったように色々な拡張を考えることが出来ます。たかだか数十～数十万の数字の組み合わせにより、"知性"を獲得していく様子は、個人的に大変面白いと感じました。本記事が、VRChat上に様々な"知性"を生み出すきっかけとなれば幸いです。

*1:https://github.com/Merlin-san/UdonSharp

*2:簡単のためPlayerは常にQ値が最大の行動を確率1で選択することを仮定しています

*3:簡単のため $(s_t,a_t)$ に対して確率1で次の状態が決まることを仮定しています

*4:https://github.com/RakuPhys/Udon-Sharp-Scripts/tree/master/FromCornerToCorner

*5:ちなみに三目並べの場合、取りうる状態数は $3^9=19683$ 、行動数は9なので一次元Qtableの長さは177147となります