マルコフ決定過程と仲良くなりたい。一昨日書いた記事ではベルマン方程式の話をした。本を読んで理論を理解したつもりでも、自分で実装してみて初めて見える世界ってのもある。ってことで簡単なゲームを作って、マルコフ決定過程問題を解くアルゴリズムを実装してみた。

ベルマン方程式については前回の記事を参照のこと。

問題設定

典型的なマルコフ決定過程の問題を解くだけでは面白さが足りないので自分でゲームを考えてみた。その名も、邪魔してくる人を避けながら部屋を脱出するゲーム。

ゲーム画面はこんな感じ。

f:id:t-keita:20210701222747g:plain:w300 　

ゲームの設定を説明しよう。主役は A さんで、ゲーム画面上に黄色い文字で「A」って書かれているやつ。A さんは５マス × ５マスの部屋に閉じ込められていて、すぐにでも部屋から脱出したい。部屋の出口は赤い文字で「G」って書かれたところである。A さんは左上のマスからスタートして出口の G を目指す。これだけなら何の難しさもないゲームである。

ここで登場するのが A さんの移動を邪魔する B さんである。ゲーム画面上で黄緑色の文字で「B」って書かれたイヤなヤツである。B さんは A さんの右下からスタートして、その後は A さんの動きをマネし続ける。A さんが右に動けば B さんも右に動くし、A さんが下に動けば B さんも下に動く。ただし、B さんが壁際にいるときに A さんが壁の方向に動くとさすがに A さんのマネはできない。こういうときは B さんは動かない。一方で、A さんだけが壁際にいて壁の方向に動こうとすると、B さんはつられて同じ方向に動いてしまうものとする。要するにフェイントである。

お分かりのとおり、B さんがいる限りは A さんは G に到達できない。これではゲームとして成立しない。もうひと工夫しよう。

f:id:t-keita:20210701224448g:plain:w300

そこで導入するのが「柱」であり、ゲーム画面上にある白い長方形である。マスに柱があると、A さんも B さんもそのマスに移動できなくなる。もちろん、B さんが A さんの動きをマネして動こうとした先に柱がある場合は B さんは動けない。この柱があれば A さんは B さんを回避して出口 G まで辿り着けそうである。ゲームの設定は以上である。

なんとかして A さんを部屋から出してあげたい。もっというと 出口 G に到達するための最善の動き方 を A さんに学習してほしい。これが今回の最終的な目標である。

マルコフ決定過程として定式化する

このゲーム設定をマルコフ決定過程（MDP）として定式化し、それを解くことで A さんの最善の動きを求めよう。前回の記事でも載せた MDP のベイジアンネットワークを以下に示しておく。 $s \in \mathcal{S}$ が状態で、 $a \in \mathcal{A}$ が行動であり、 $r \in \mathcal{R}$ が報酬である。

f:id:t-keita:20210630021132p:plain:w400

MDP として以下のように定式化した。MDP の構成要素については Wikipedia のページを参照のこと。

状態は A さんの座標と B さんの座標の組とした。すなわち、状態集合 $\mathcal{S}$ は２人の座標のすべての組み合わせである。
行動 $\mathcal{A}$ は、A さんが「左」「右」「上」「下」に移動するという４つからなる。
状態遷移確率 $p(s' \mid s, a)$ は A さんと B さんの移動に対応する決定論的な遷移とした。たとえば、A さんと B さんの座標がそれぞれ (2, 3), (3, 4) である状態を $s$ として、行動 $a$ を「右」とすると、遷移後の状態 $s'$ は (3, 3), (4, 4) となる。これは $p(s' \mid s, a) = 1$ とすることで意図する遷移を表現できる。
報酬関数 $g(r \mid s, a)$ は、A さんが G 以外の場所にいるときは -1、G にいるときは 0 とした。この報酬は毎時間ごとに発生するので、A さんが G 以外の場所にいる時間が長くなるほど報酬が小さくなってしまう。この報酬の設計を通して、なるべく早く G に到達したほうがよいことを A さんに教えてあげている。
目的関数は $G_t = R_{t+1} + R_{t+2} + R_{t+3} + \dots$ とした。

この MDP 問題を解くことで、A さんの移動を決める方策 $\pi(a \mid s)$ を最適化する。すなわち最適方策を求める。A さんがどの状態にいても最善の行動が取れるようになるわけである。

価値反復法を実装する

前回の記事の通り、MDP を解くにはベルマン最適方程式を利用して価値関数を繰り返し更新すればよい。以下のそのコードを示す。言語は Kotlin である。

    // Initialize the value function
    val values = mutableMapOf<State, Int>().apply {
        allStates().forEach { this[it] = 0 }
    }
    // Value iteration using Bellman optimality equation
    do {
        var delta = 0
        allStates().forEach { state ->
            val vTmp = values[state]!!
            // update the value of a state
            values[state] = Action.all().maxOf { action ->
                reward(state, action) + values[nextState(state, action)]!!
            }
            delta = max(delta, abs(vTmp - values[state]!!))
        }
        println(delta)
    } while (delta > 0)

なんの工夫もなく価値反復法を実装している。このコードの全体は Gist 上に置いた。

コードを実行してみる

それでは A さんの最終的な行動を見てみよう。頼むぞ、A さん。

柱を真ん中に置いた場合

柱を真ん中において MDP を解いた結果得られた最適方策は以下の通りである。

f:id:t-keita:20210701234124g:plain:w300

見事に A さんは B さんを柱に引っかけて出口 G に到達できている。A さんは寄り道することもなく、最短経路で G に到達している。自分の報酬設計は間違っていなかった。ありがとう、A さん。

柱を端に置いた場合

次は柱を端っこの方に置いたときの A さんの行動を見てみよう。さっきより一筋縄では行かなそうな雰囲気があるぞ。

f:id:t-keita:20210701224352g:plain:w300

こちらも見事に B さんを柱の陰に封印して出口 G に到達できてる。最初に B さんだけが左に移動したのは、A さんが左に移動しようとしたからである。いわばフェイントを使って B さんを壁際に移動させたのである。やるなぁ、A さん。

所感

今回は適当なゲーム設定を作ってマルコフ決定過程として定式化し、それを解くアルゴリズムを実装してみた。状態遷移をどう設定するか、報酬をどう設定するか、いざ考えてみると少し悩ましかった。それゆえけっこう勉強になった。

MDP を解くアルゴリズムの実装は全体で100行くらい。最適化計算には1秒もかからなかった。こんなちょっとしか書いてないのに一瞬でスマートに振る舞う A さんが誕生するのはスゴい。MDP として定式化できる問題は理論上なんでも同じように解けるんだから、この仕組み考えたベルマンさんマジで天才。

あと別の気付きとして MDP の解法が Dynamic Programming と呼ばれている意味を理解した。不動点を近似計算するのは DP の要件ではないので、これまでなぜこの種のアルゴリズムが DP と呼ばれているのが理解できていなかった。結局のところ、価値が最大になる行動を greedy に選べば最適方策が得られるという構造が DP になっている。これはダイクストラ法の構造とまったく同じ。価値関数の計算が DP なのではなく、価値関数の使い方が DP ってことなんだよなきっと。 f:id:t-keita:20210702000458p:plain:w0