Blackwellの接近可能性定理
数理最適化 Advent Calendar 2020 20日目の記事です．昨日はyappy0625さんの『天体ショーを整数計画問題で解いてみた。』，明日はshuhei_fさんのSVMの話です．
今回紹介するのはBlackwellの接近可能性定理という定理です．一言でいうと，von Neumannのミニマックス定理の拡張なのですが，オンライン最適化（リグレット最小化）と深いつながりがあります．最近研究で使って非常に面白いと思ったので，ここで紹介することにします．
von Neumannのミニマックス定理
まずはvon Neumannのミニマックス定理の復習から．$A$を$m \times n$行列とし，$\Delta_m $, $\Delta_n$をそれぞれ $m $, $n$次元確率単体，つまり
\[
\Delta_m = \{ x \in [0,1]^m : \sum_i x_i = 1 \}
\]
とします．このとき
von Neumannのミニマックス定理
\[
\max_{x \in \Delta_m}\min_{y \in \Delta_n} x^\top A y = \min_{y \in \Delta_n} \max_{x \in \Delta_m} x^\top A y
\]
が成り立ちます*1．maxとminが交換できるという意味で興味深い定理ですが，ここでゲーム的な視点からこの定理を眺めてみましょう．\[
\max_{x \in \Delta_m}\min_{y \in \Delta_n} x^\top A y = \min_{y \in \Delta_n} \max_{x \in \Delta_m} x^\top A y
\]
$m $個の手をもつプレーヤー$X$ と $n$ 個の手を持つプレイヤー $Y$ との二人ゲームで，$X$ が手 $i$，$Y$ が $j$ を出したときの $X$ の利得が $A_{ij}$ で与えられるゲームを考えます（双行列ゲーム）．ジャンケンのようなものを考えればイメージしやすいと思います．ここでは，双方とも確率的に手を選ぶこと（混合戦略）を許すとしましょう．各プレイヤーの混合戦略を $x \in \Delta_m $, $y \in \Delta_n$ として，期待利得 $x^\top A y$ が非負であれば $X$ の勝ち*2，そうでなければ $Y$ の勝ちとします．
さて，von Neumannのミニマックス定理の両辺を眺めると，
- 左辺 $\max_{x \in \Delta_m}\min_{y \in \Delta_n} x^\top A y$ は$X$ が先手で混合戦略 $x$ を選び，それを見た後に $Y$ が後手で最適な混合戦略 $y$ を選ぶ場合に，$X$ が得られる最大の利得
- 右辺 $\min_{y \in \Delta_n} \max_{x \in \Delta_m} x^\top A y$ は逆に，$Y$ が先手で選んだ混合戦略 $y$ を見た後に $X$ が後手で最適な混合戦略 $x$ を選べる場合の最大の利得
を表しており，von Neumannのミニマックス定理はこの2つの状況で最適な期待利得が等しいことを示しています．
ベクトル値ゲーム
さて，von Neumannのミニマックス定理はスカラー値の双行列ゲームについて，（混合戦略を考えると）先手・後手の利得に差がないことを示したものでした．Blackwellの定理ではこれをベクトル値のゲームに拡張します．このゲームは
- 閉凸集合 $\mathcal{X} \subseteq \mathbb{R}^m $, $\mathcal{Y} \subseteq \mathbb{R}^n$
- ベクトル値双線形写像 $\ell : \mathcal{X} \times \mathcal{Y} \to \mathbb{R}^d$
- 閉凸集合 $\mathcal{S} \subseteq \mathbb{R}^d$
によって記述されます．プレイヤー$X, Y$ はそれぞれ自分の手として $x \in \mathcal{X}$, $y \in \mathcal{Y}$ を選びます．その上で， $\ell(x, y) \in \mathcal{S}$ となれば $X$の勝ち， そうでなければ $Y$ の勝ちです．以下，四つ組 $(\mathcal{X}, \mathcal{Y}, \ell, \mathcal{S})$ をBlackwellゲームと呼ぶことにします．
例えば，双行列ゲームは $d = 1$ の特別な場合，
- $\mathcal{X} = \Delta_m $, $\mathcal{Y} = \Delta_n$
- $\ell(x, y) = x^\top A y$
- $\mathcal{S} = [0, +\infty)$
に対応するので，Blackwellゲームは双行列ゲームを一般化しています．
さて，双行列ゲームでは先手でも後手でも利得（すなわち勝てるかどうか）に差がなかったわけですが，Blackwellゲームではどうでしょうか．それを調べるため，まずは先手で勝てる・後手で勝てるということを正確に定義します．
定義
- Blackwellゲームがsatisfiableである ⇔ $\exists x \in \mathcal{X} \forall y \in \mathcal{Y} : \ell(x, y) \in \mathcal{S}$
- Blackwellゲームがresponse-satisfiableである ⇔ $\forall y \in \mathcal{Y} \exists x \in \mathcal{X} : \ell(x, y) \in \mathcal{S}$
$\forall$ と $\exists$ の順番に注意してください．簡単に言うと，satisfiableとは，「ある万能の手 $x$ があって，これを出しておけばどのような $y$ が来ても必ず勝てる」場合で，先手で勝てる場合に相当します．一方， response-satisfiableは「どのような手 $y$ に対しても，それに勝つ手 $x$ が存在する」場合で，後手で勝てる場合に相当します．
双行列ゲームの場合，von Neumannのミニマックス定理から，satisfiable⇔response-satisfiable でした．しかし，Blackwellゲームではこれは成り立ちません．
反例（「対角線ゲーム」）
- $\mathcal{X} = \mathcal{Y} = [0,1]$
- $\ell(x, y) = [x, y]^\top \in \mathbb{R}^2$
- $\mathcal{S} = \{ [p_1, p_2]^\top \in [0,1]^2 : p_1 = p_2 \}$
を考えます．図で示すと，以下のような感じで，$X$ が $x$ 座標，$Y$ が $y$ 座標を選べる点があって，対角線上にこの点を乗せることができれば $X$ の勝ちというゲームです．
明らかにこのゲームはresponse-satisfiableですが，satisfiableではありません．
Blackwellの接近可能性定理
さて，satisfiable⇔response-satisfiableという単純な一般化は，Blackwellゲームでは成り立たないことが分かりました．実は，Blackwellゲームを何度も何度も繰り返し行った“平均”を考えるとうまく一般化できる，というのがBlackwellの定理の主張です．定理を正確に述べるために，satisfiableを緩和したapproachableという性質を考えます．
定義
かなり抽象的な定義ですが，それまでの履歴から次の手を決めるアルゴリズムが存在し，利得 $\ell(x_t, y_t)$ の平均を $\mathcal{S}$ に近づけることができる，すなわち平均的にはいくらでも勝ちに近づくことができるという気持ちです．このような $x_t$ を接近列ということにします．Blackwellの接近可能性定理は以下の主張です．
Blackwellの接近可能性定理
任意のBlackwellゲームに対して response-satisfiable ⇔ approachable が成り立つ．
任意のBlackwellゲームに対して response-satisfiable ⇔ approachable が成り立つ．
上の「対角線ゲーム」でBlackwellの定理を確かめてみましょう．「対角線ゲーム」はresponse-satisfiableだったので，Blackwellの定理によると，平均的に勝てるアルゴリズム $\mathcal{A}$ が存在するはずです．実際，$x_t = y_{t-1}$ とすると，
\[
\frac{1}{T} \sum_{t=1}^T \ell(x_t,y_t) = \frac{1}{T}\begin{bmatrix}
y_1 + \dots + y_{T-1} \\ y_1 + \dots + y_{T-1}
\end{bmatrix}
+ \frac{1}{T} \begin{bmatrix} x_1 \\ y_T \end{bmatrix}
\to \mathcal{S}
\]
となり，$T \to \infty$ で$ \mathcal{S} $ に限りなく近づくことがわかります．
Blackwellの定理とオンライン最適化
実は，Blackwellの定理とオンライン凸最適化には深い関係があります．オンライン凸最適化とは，学習者(learner)と敵対者(adversary)の間の繰り返しゲームとして最適化を捉える枠組みです．具体的には，凸集合 $\mathcal{K} \subseteq \mathbb{R}^n$ が与えられ，各時刻 $t = 1, \dots, T$ において
- 学習者 は $x_t \in \mathcal{K}$ を選び，敵対者は凸関数 $f_t: \mathcal{K} \to [0,1]$ を選ぶ
- $x_t$ を選んだ後に，学習者は $f_t$ の情報（例えば関数値 $f_t(x_t)$ や勾配 $\nabla f_t(x_t)$ など）を得る
という枠組みです．目標はリグレット
\[
\sum_{t=1}^T f_t(x_t) - \min_{x^* \in \mathcal{K}} \sum_{t=1}^T f_t(x^*)
\]
を小さくする学習者のアルゴリズムの設計です．典型的には $O(\sqrt{T})$ など，$T$ に関して劣線形のリグレットが達成できます．
実は，リグレット最小化とBlackwellの定理はある意味で等価であることが知られています．正確な主張は元論文*3を参照してほしいのですが，非常に大雑把にいうと，Blackwellゲームの接近列を生成するアルゴリズムが与えられれば，オンライン最適化のアルゴリズムを構成することができ，逆にオンライン最適化のアルゴリズムからBlackwellゲームの接近列を生成するアルゴリズムを構成することもできます．オンライン凸最適化には様々なアルゴリズムが知られているので，この関係を使うことで，Blackwellゲームに対して統一的に接近列を計算するアルゴリズムを構成できます．
また，Blackwellの定理は変則的なリグレットを考える際にも役に立ちます．例えば，スワップリグレットという，普通のリグレットの亜種があるのですが，実はこれもBlackwellの定理で捉えることができ，上の帰着を使うと結局オンライン凸最適化でスワップリグレットも $O(√T)$ を達成するアルゴリズムが設計できたりします．もっと奇妙な形をしたリグレットらしき量*4であっても，Blackwellの定理の形にさえ落とし込めれば，オンライン凸最適化で効率的なアルゴリズムを設計できます．
まとめ
Blackwellの接近可能性定理という，あまり知られていないけど強力な定理を紹介しました．いつか，不思議な形のリグレットっぽい量を抑えたくなったら，使ってみるといいかもしれません．
