概要
Atcoder双子コン3のH: 爆弾ゲーム839点解法を、強化学習で自動的に編みだすプログラムを書きました。具体的には、マルコフ決定過程(MDP)を構築し、Bellman Equationを動的計画法で解きました。計算量は$O(h^4 w^4 2^{hw})$ です。副次的な貢献として、解説$839$点解法（http://s8pc-3.contest.atcoder.jp/data/other/s8pc-3/editorial.pdf) が$2 \times 2$の盤面において厳密最適解であることを証明しました。
実装が面倒だったので、「解法を編み出す」ところまではやりましたが、実際に839点取るところまではやっていません。$4\times 4$などで同じことをしようとしたかったのですが、計算量が計算量なので、厳密解を求めるアプローチは諦めました。今後はDeep Learningを併用して、スコアを上げていきたいなと思います。
プロコン界に最近流行りの機械学習とかDeep Learningを持ち込みたいと思っています。
その提出はこれです: http://s8pc-3.contest.atcoder.jp/submissions/1218337
問題
$h \times w$の二値盤面$b_{ij}$を特定したい。クエリ$(h_1, w_1, h_2, w_2)$を投げると、$\displaystyle
\sum_{i=h_1}^{h_2} \sum_{j=w_1}^{w_2} b_{ij}$が帰ってくる。投げるクエリ回数を最小化せよ。
制約: $\displaystyle h=w=50, \sum_{i=0}^{h-1} \sum_{j=0}^{w-1} b_{ij} = 250$
どうして強化学習で解けそうか
強化学習は、以下のような枠組みの問題の厳密最適解を計算できます。「ある状態$s$で行動$a$をおこなったら、確率$\mathcal{P}^{a}_{ss'}$で状態$s'$に遷移するという。実際に$s$が行動$a$で$s'$に遷移したら、報酬$\mathcal{R}^{a}_{ss'}$をもらう。未来に渡って得られる報酬の和の期待値を最大化するような、確率的方策$\pi(s, a): \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$を求めよ。」
ここで、$\mathcal{S}$はエージェントが取りうる状態集合、$\mathcal{A}$はエージェントがおこなえる行動集合、$\pi(s, a)$は、状態$s$で行動$a$を確率$\pi(s, a)$でおこなう、という意味です。
爆弾ゲームでは、同じ状態で同じ質問をしても真の盤面はわからないので、返答が一意とは限りません。したがって、爆弾ゲームで期待値の厳密最適解を求めたいならば、このような確率的モデルを構築することが不可欠となります。この枠組みは確率的遷移や確率的戦略を許容しているので、自然なモデル化と言えます。
状態と行動の定義
爆弾ゲームの状態を、「『今までにした質問とその応答のペア』の集合」と定義します。また、行動を「可能な質問」と定義します。
たとえば、$2 \times 2$の盤面を想定します。何も質問していない時は状態$s=\{\}$です。この状態から、行動(0, 0, 1, 1)の質問をして2が帰ってきた時、その状態は$s'=\{((0, 0, 1, 1), 2)\}$となります。更に、行動(0, 1, 0, 1)の質問をして1が帰ってきた時、その状態は$s'=\{((0, 0, 1, 1), 2), ((0, 1, 0, 1), 1)\}$となります。
報酬の定義
報酬$\mathcal{R}^{a}_{ss'}$はどのように定義するべきでしょうか？今回の場合、エージェントの目的は、盤面を一意に定めるためのクエリ回数の最小化でした。したがって、遷移先状態$s'$の質問集合によって、盤面が一意に定まらなければ、クエリを無駄に使ったエージェントに罰則$-1$を与えればよいです。逆に一意に定まった場合は、罰則を与えずに$0$とすればいいです。整理すると、
\displaystyle \mathcal{R}^{a}_{ss'} = (s'\ determines\ unique\ board\ pattern\ ?\ 0 : -1)
遷移確率の計算
確率$\mathcal{P}^{a}_{ss'}$は、どのように計算できるでしょうか？これは、ある状態$s$で行動$a$をおこなったら、状態$s'$に遷移する確率です。まず、真の盤面は、一様分布していると仮定します。すると、状態$s$＝ある質問集合をすでに聞きおえた状態で、クエリ$a$を投げた時に、サーバからのクエリ返答が何になるのかは、全探索的に予測できます。状態$s$に対して、状態$s$に矛盾しない真の盤面の場合の数を$f(s):\mathcal{S} \rightarrow \mathbb{R}$とします。整理すると、
\forall x\ s' = s \cup {(a, x)} \land \mathcal{P}^{a}_{ss'} = \frac{f(s')}{f(s)}
強化学習
ここまでで、「状態$s_t$で行動$a_t$を行うと、確率$\mathcal{P}^{a}_{ss_{t+1}}$で状態$s_{t+1}$に遷移して、報酬$r_t=\mathcal{R}^{a}_{ss_{t+1}}$を手に入れられる」というモデル化が終わりました。
強化学習では、時刻$t$で「未来に渡って得られる報酬の和」の期待値を最大化したいのでした。「未来に渡って得られる報酬の和」は、時刻$t$での収益$R_t$と呼ばれます。$r_t$を時刻$t$で得られる報酬の確率変数とします。すると、
\begin{align}
\displaystyle R_t &= r_{t+1} + \gamma r\_{t+2} + \gamma^2 r_{t+3} + \cdots \\ &= \sum^{\infty}_{k=0} \gamma^k r_{t+k+1}
\end{align}
ここで$ \gamma$は割引率と言われる、0.9のような1に近い1未満の正定数です。一般には、マルコフ決定過程がループ構造を持ち、永遠に終わらない可能性があるので、発散を防ぐために入れられます。今回の爆弾ゲームでは、マルコフ決定過程はDAGなので、$\gamma=1$として問題ありません。
また、ある状態から始めた時の、収益の期待値を状態価値ベクトル$\mathbf{V}^{\pi} \in \mathbb{R}^{\mathcal{S}}$を定義します。同様に、ある状態である行動を行った後の、収益の期待値を行動価値ベクトル$\mathbf{Q}^{\pi} \in \mathbb{R}^{\mathcal{S} \times \mathcal{A}}$を定義します。
状態価値ベクトルと行動価値ベクトルは、定義に従い、以下のように表記できます。
$ V_s^{\pi} = E\{R_t | s_t = s\}$
$ Q_{s,a}^{\pi} = E\{R_t | s_t = s, a_t = a\}$
ここで、$R_t$の添字を一つずらすことによって、以下の関係を導くことができます。
$ \displaystyle V_s^{\pi} = \sum_{a \in \mathcal{A}(s)} \pi(s, a) \sum_{s' \in \mathcal{S}} \mathcal{P}^{a}_{ss'} (\mathcal{R}^{a}_{ss'} + \gamma V_{s'}^{\pi})$
この式をよく見ると、ただの$|\mathcal{S}|$次元連立方程式であることがわかります。これを解くことによって、$\mathbf{V}^{\pi} \in \mathbb{R}^{\mathcal{S}}$を計算できます。
また、定義から状態価値ベクトルと行動価値ベクトルには以下の関係があります。
$\displaystyle V_s^{\pi} = \sum_{a \in \mathcal{A}(s)} \pi(s, a) Q^{\pi}_{s, a}$
$\displaystyle Q_{s,a}^{\pi} = \sum_{s' \in \mathcal{S}} \mathcal{P}^{a}_{s'}(\mathcal{R}^{a}_{ss'} + \gamma V^{\pi}_{s'})$
これまでで、「ある状態である行動をした」時の収益の期待値を計算することができました。今やりたかったことは、$\mathbf{V}^{\pi}$の各値を最大化するような方策$\pi(s, a)$を探すことでした。これは直感的には、ある状態$s$にいたら、$Q^{\pi}_{s,a}$を最大にするような行動$a$の確率を1にすれば良いように思います。これは実際に方策改善定理というものが証明されていて、これによって必ず$\mathbf{V}^{\pi}$を最大化できるらしいです。
以上を用いることで、マルコフ決定過程において、クエリ回数を最小化するような方策を最適化することができました。実装上は、価値反復法というやつを使いました。
盤面が大きくなると…？
計算量が${O(h^4 w^4 2^{hw})}$ なので無事宇宙が終わります。(´°ω°)ﾁｰﾝ
盤面が大きくなると…？（真面目に、そしてDeep Learningへ）
今回は、状態と確率モデルを完全に書き下しました。しかし、状態と遷移が多くなると、計算量が爆発して現実的な時間に終わりません。ではどうすればよいでしょうか？
ひとつは、確率モデルを構築しない、という選択肢です。構築しないと$Q$などを具体的に計算できなくなりますが、これは「試して動いてみる」方法によって推定できます。具体的は、モンテカルロEC法、SARSA法、Q-learningなどが提案されています。
しかし、結局この問題ではやはり状態が多すぎて、必要なサンプルが爆発して使い物にならないことが予想されます。ボトルネックは状態数なので、状態の特徴量をうまく抽出して低次元化し、Q(s, a)を近似する方法が考えられます。これをDeep Learningでやる方法がDeep Q-learningと呼ばれていて、これを使えばもう少しまともになると思われます。
もしこれを実装したとしても、もう一点問題があります。今回の状態の持ち方では、解の復元に大きな時間計算量がかかってしまうという点です。「一意に定まるようなクエリ群を生成せよ」だけなら、まだできたのかもしれません。この問題はどうやって解決すればいいのでしょうか…？