先読みに基づいたプランニング、学習化シミュレータとモンテカルロ木探索

本記事はロボットとAI技術の専門誌『日経Robotics』のデジタル版です

［画像のクリックで別ページへ］

　先読みに基づいたプランニングは強力なエージェントを作る上で重要である。例えばチェス、将棋や囲碁などではトッププレーヤーをはるかに超える強さを実現したAIシステムが先読みによって実現されている。

著者の岡野原大輔氏

　先読みを行う際、環境で未知の部分があれば予測を必要とする。環境シミュレータといってもよいだろう。しかし、一般に予測は非常に難しい。例えば対戦ゲームでは先読みする上で相手の挙動は未知である。幸い、この相手の挙動の予測に限っては学習途中の自分自身を相手に設定することで少なくとも最善な手を選ぶ相手を作ることができる。

　さらにチェスや将棋などの対戦ボードゲームでは環境の完璧なシミュレーション（選択した行動に対し環境がどう変わるかが分かっている）が使える。そのため、対戦ボードゲームに限っては正確な予測ができ、先読みに基づいたプランニングできる。そのため他の分野に先駆けて非常に強いシステムができたといえる。

　しかし世の中の多くの問題ではシミュレータが存在せず難しい予測問題を解く必要があり、正確な先読みができない。この場合、先読みに基づくプランニングを諦め、別のアプローチをとる必要がある。

　このように正確な先読みできる問題かどうかによってプランニングは大きく2つの問題に分けられてきた。先読みできる場合は状態が列挙できれば動的計画法で解け、問題が特別な構造を持っている場合は最適化で解くこともできる。これらを満たさない場合でも強力なモンテカルロ木探索（MCTS）を使える。このMCTSについて簡単に説明しよう。

　MCTSでは、今後取る行動と状態の可能性を木の形で表現する。現在の状態が根に対応し、状態$s$で行動$a$を選択した結果、状態$s'$に遷移した場合は、節点$s$に$a$のラベルが付随した枝にぶら下がる形で節点$s'$が子となる。この木の表現上で有望そうな状態（節点）を順に展開して行き、最適な行動（列）を絞り込んでいく。具体的には毎回根から後述する基準に従って子を順に選択して行き子をもたない節点（葉）までたどり着く。そこでプレイアウトと呼ばれる最終結果が出るまで行う高速なシミュレーションを行って報酬（ゲームであれば勝ち負け）を計算し、それをその節点の評価値（強化学習における価値と同じ）とする。最後の状態まで行かなくても報酬が貰える場合はプレイアウトではなく途中までの累積報酬を使う場合もある。子を選択する際に使う基準は節点の評価値と不確実ボーナスの合計が大きいものを選択する。節点の評価値はその子孫の評価値の平均である。このように各節点の評価値をサンプルからモンテカルロ推定していることからこの名がついている。また不確実性ボーナスはまだ十分探索されていない節点を選択するよう加えられるものであり、節点の訪問回数が多くなるほどボーナスは減っていくように設計しておく。この展開とシミュレーションを時間が許すまで行い、最終的に最初の手の中で訪問回数が最も多いものを選択する。このMCTSは強力であり多くの問題で成功を収めている。

　それに対し先読みできない問題ではこのように実際試して評価することができない。そのため過去の経験から現在の状態や行動がどのぐらいの価値（期待される累積報酬）があるのかを推定する。これらは状態価値関数や状態行動価値関数として表される。状態が無数にある場合、これらの関数はニューラルネットワーク（NN）などを使って表し、その関数を特徴付けるパラメーターを、TD目標（現在の時刻の価値が即時報酬と次の時刻の価値の和に一致するようにする）などを使って更新していく。この更新によって関数近似誤差がなければこれら価値関数は真の期待累積報酬に収束することが分かっている。

　このように先読みできる問題とできない問題は棲み分けされ独立に発展してきた。しかし、近年のモデルベース強化学習はその境界を曖昧にしている。

　モデルベース強化学習では環境のシミュレータをNNなどでモデル化し、そのモデルを実際の経験から学習する。このシミュレータは世界モデルとも呼ばれる。世界モデルは一般に現在の状態と行動から将来の観測を復元するように学習する。しかし前述のように予測はとても難しい問題である。そのため世界モデルもかなり単純化された状況以外は成功していなかった。

　そのため予測を完全に解くのではなくプランニングに関係する要素だけ正確に予測できるようにする手法がこの数年登場している。たとえばプランニングに背景や見た目が関係なければ、シミュレータはそれらを無視して予測するようにする。例えばレースゲームで大部分の背景はプランニングに影響ないが、次にカーブがあるという看板はプランニングに影響があり、そうした要素だけを予測できるようにする。

　この代表がMuZero^1）である。MuZeroはデータからシミュレータを学習し、そのシミュレータを使ってMCTSでプランニングする。このシミュレータは将来の観測を復元することは目標としない。代わりに現在の状態と今後取る行動列を入力として任意ステップ後の報酬、価値、方策（状態から行動を返す関数）が実際の環境を使った場合と一致することを目標とする。方策が一致するということは別の言い方をすれば実際の環境でプランニングした結果とシミュレータ上でプランニングした結果（選択する行動）が一致するようにシミュレータを学習する。シミュレータはプランニングに影響がない部分は予測する必要がないため予測問題は簡単になる。

　またMuZeroはAlphaZeroと同様に、方策の学習においてMCTSを実施して得られた最適行動を目標として方策を更新する。先読みした結果は先読みしない方策より常に強いので、良い学習目標となる。このMCTSで得られる目標はQ学習に使われるTD目標に比べて良い学習シグナルであることが分かっており、高速に学習できるだけでなく、最終結果で大きな差がつくことが分かっている。

　MuZeroによってシミュレータを持たない問題にもMCTSでプランニングできるようになる。この結果、これまで価値関数（DQNや最新のRainbowなど）ベースの手法が使われていたAtariゲームなどの問題もMCTSが使えるようになった。この両者を比較した実験結果では従来の価値関数を使った手法と比較しMCTSを使った手法が性能で大きく上回った。これまで多くの改良がなされてきた価値関数ベースの手法をMCTSの手法が一気に凌駕したことは大きなインパクトがある。

　学習化シミュレータとMCTSの組み合わせは有望だが、まだ多くの問題が残されている。MCTSの一番大きな問題は並列化が難しい点である。シミュレーション自体は独立に並列にできるが、どの節点を展開するかを決めるには他の結果を待つ必要があり、それを無視して独立に並列に実行すると皆同じような節点を探索してしまうという問題が起きる。この問題に対し、シミュレーション結果を待たずに先に不確実性ボーナスだけを減らすという単純な工夫が有効であることが分かっている^2）。また並列にシミュレーションといっても独立であり、現在のチップ（GPUやTPUなど）の性能を生かすためのベクトル化も難しい。

　もう1つはMCTSは通常、離散的な状態、行動が対象だが、連続的な状態、行動の場合、節点をどのように定義するかが問題となる。今後学習化シミュレータの適用範囲が増え、連続な状態、行動を持つ問題を扱う場合が増えるだろう。部分的にしか予測しない世界モデルを学習した場合、誤った因果推論をしてしまい、モデル化していない観測の影響を受けて誤ったプランニングをしてしまうことが分かっている^3）。これらの問題を解決できればより広い問題を強力な先読みを使って汎用的に解けるようになるだろう。

岡野原 大輔（おかのはら・だいすけ）
Preferred Networks 代表取締役副社長

2006年にPreferred Infrastructureを共同創業。2010年、東京大学大学院博士課程修了。博士（情報理工学）。未踏ソフト創造事業スーパークリエータ認定。東京大学総長賞。