この論文の面白いところ

非強調ゲームにはPotential gameというものとHamiltonian gameというもの(および両方の側面を併せ持つもの)がある。

特に、じゃんけんの三すくみやポケモンのタイプ相性のように"相性"があるゲームはHamiltonian gameになっていることが多い。

Potential gameは勾配降下法で簡単に最適化(=局所Nash均衡になる点を求めること)ができる一方、Hamiltonian gameでは勾配降下法を使っても最適化がうまく行かないという問題が知られていた。

じゃんけんを例に出すと、最適化の初期値としてプレイヤー1もプレイヤー2もチョキを100%出すという戦略から始める時、最適化のステップ1の後では学習の結果二人ともグーを100%出すという戦略になり、ステップ2の後ではパーを100%出すと言う戦略になり、...と言う感じでぐるぐると解の空間の中を回ってしまうという問題が知られていた。

この論文では、実際の目的関数に勾配ベクトルの長さを加えることでHamiltonian gameであってもうまく最適化できるようにする手法を提案している。頭よすぎ。

問題設定

Gameは、次の二つによって定義されるとする。

(1)n人のプレイヤー。

(2)n人のプレイヤーそれぞれについて設定された二回微分可能な損失関数。

それぞれのプレイヤーはモデルパラメータ $w_i$ の調整を行なって、それぞれに対して設定された損失関数をなるべく小さくすることを目指す。

これになぞらえると、GAN学習問題は「プレイヤーが二人いて、一方が識別器のパラメータを調整して識別器の損失を、もう一方が生成器のパラメータを調整することで識別器の損失に負の定数をかけたものを小さくすることを目指す」ゲームであると説明できる。

なおこの論文ではそれぞれのプレイヤーの損失関数をそれぞれのプレイヤーが制御できるパラメータで微分したものを次の記号で表現する:

ここで、 $l_i$ はi番目のプレイヤーに対して設定された損失関数、 $w_i$ はi番目のプレイヤーが制御できるモデルパラメータである。

また、以降ではi番目のプレイヤー以外のパラメータはまとめて $w_{-i}$ と表記する。

局所Nash均衡

パラメータ $w_i$ の近傍を $U_i$ と定義する。局所Nash均衡とはN個のパラメータ $w_1,..., w_N$ が全て次の条件を満たす場合のことである:

[tex: l_i(\hat{w_i}, w{-i}) \geq l_i(w_i, w{-i}) for \hat{w_i} \in U_i ]

Potential GameとHamiltonian Game

GameのHessianを次のように定義する (通常のHessianとは微妙に異なるので注意):

もしくは

Hessianは通常の行列と同様に次のように対称行列S (S=S^T)と交代行列A (A=-A^T)の和に分解できる:

Aが零行列のときは特にPotential Gameと呼ばれるものであり、過去によく研究されてきた。一方でSが零行列のときはあまり研究がされてこなかった。この論文ではSが零行列のときをHamiltonian Gameと呼ぶこととしている。

Potential Game

Potential Gameとは任意のtex: w_i, w'i, w''iに対して次の条件を満たすような関数φとN個の正の数 $\alpha_1,...\alpha_N$ (この論文の中では $\alpha_i=1$ と考えて良い)が存在するGameのことである:

これは次と等価であることが示されている:

(こちらのPDFもPotential gameについて解説しており、よりわかりやすい) https://www.jstage.jst.go.jp/article/sicejl/55/11/55_996/_pdf

Potential Gameの例としては、N人のプレイヤーが同じモデルのパラメータを同じ目的関数についてそれぞれ独立して最適化する場合などが挙げられる(N人が別々に識別器を学習させる場合など)。

Potential Gameではξを用いた勾配降下法によってφの局所最適解にたどり着けることが容易に示せる。

Hamiltonian Game

Hamiltonian Gameの例としては以下のものが挙げられる。

Hamiltonian GameはPotential Gameとはかなり性質の異なる概念である。 Potential Gameの場合と同様にプレイヤーにξを用いた勾配降下法によってパラメータを最適化させたいところだが、そうすると以下の図の左ようにくるくる回ってしまう場合もあり、局所Nash均衡に行き着くと限らない。