ポーカーAIのアルゴリズムを調べていたら、CFRというアルゴリズムが基礎であることが分かった。元論文を読んでCFRについてまとめながら理解した。これはその記録である。
CFRは、 $\epsilon$ ナッシュ均衡を実現する平均戦略 $\bar\sigma$ を繰り返し計算で求めるアルゴリズムである。
CFR の提案論文(だと思っているが違うかもしれない) Regret Minimization in Games with Incomplete Informationのアルゴリズムの基礎部分を中心に解説する。論文中の証明は省略する。定理番号は元論文と異なることに注意。
この文章は不十分な箇所が多い。この記事を足がかりに次に進んでいただければ幸い。
そもそもなぜ $\epsilon$ ナッシュ均衡を求めるのか
そもそもナッシュ均衡を求める理由について先に述べる。この節の説明はCounterfactual Regret Minimization – the core of Poker AI beating professional players]を参考にした。
-
ナッシュ均衡とは
Nash Equilibrium is a strategy profile (set of strategies for all players involved) such that no single player has incentive to deviate.
-
ナッシュ均衡戦略は強いのか。
playing Nash Equilibrium will in practice result in zero payoff then (you will not lose playing it in expectation). Exploitability of a strategy from a Nash Equilibrium pair is zero – it means that if you play it, your opponent best exploit strategy will have a zero payoff in expectation. You are guaranteed to draw in worst case.
-
完全情報ゲームでは、強化学習によって期待利得を最大化する戦略を求める。しかし、不完全情報ゲームではナッシュ均衡を満たす戦略を求めるらしく、少し雰囲気が違うようだ。
regret と $\epsilon$ ナッシュ均衡の関係
ラウンド $T$ におけるプレイヤー $i$ の average overall regret $R^T_i$ を以下のように定義する。
R_i^T = \frac{1}{T}{\rm max}_{\sigma_i^{\ast}\in\Sigma_i}\sum_{t=1}^T(u_i(\sigma_i^{\ast},\sigma_{-i}^t)-u_i(\sigma^t))
average overall regret $R^{T}_{i}$ の説明
- $\sigma^t$ はラウンド t での、全プレイヤーがとる行動の確率分布。$\sigma$ のことを単純に戦略という。
- $u_i(\sigma^t)$ はプレイヤー $i$ の効用(utilityの訳)の期待値で、$u_i(\sigma^t)=\sum_{h\in Z} u_i(h)\pi^{\sigma}(h)$ と表される。
- $Z$はゲーム終了までいった行動のヒストリーの集合で$h$はその元。
- $u_i(h)$ はヒストリー $h$ でゲーム終了したときの、プレイヤー $i$ の効用。
- $\pi^{\sigma}(h)$ は戦略 $\sigma$ のもとで、$h$ が起こる確率。
- ${\rm max}_{\sigma_i^{\ast}\in\Sigma_i}\sum_{t=1}^Tu_i(\sigma_i^{\ast},\sigma_{-i}^t)$ は、$i$ に可能な戦略の集合 $\Sigma_i$ の元$\sigma_i^{\ast}$ を動かしたときに、$T$回のゲームを通した効用の和の最大。
- 以上より、(1) は現在の戦略を $\sigma_i^{\ast}$ にしておけば、$T$ 回の平均でこれだけ儲かっていた、という後悔を表す。
また、平均戦略 $\bar\sigma^T_i$ を$t=1\sim T$ でのプレイヤー $i$ の平均戦略と定義する。特に 情報集合 $I\in\mathcal{I_i}$ のもとでの、とりえる各行動 $a\in A(I)$ の平均戦略(確率値)は以下のように書ける。(論文では$\bar\sigma_i^t$と書いてあるが、$t$ではなく$T$の方が良いと思う。この文章では$T$でいく。)
$$
\bar\sigma^T_i(a|I) = \frac{\sum_{t=1}^T\pi_i^{\sigma^t}(I)\sigma^t(a|I)}{\sum_{t=1}^T\pi_i^{\sigma^t}(I)}
$$
$R_i^T$ と $\bar\sigma^T_i$ には以下の関係が知られている。
定理1 「ゼロサムゲームにおいて、ラウンド Tで両プレイヤーの average overall regret が $\epsilon$ 未満ならば、 $\bar\sigma^T$ は 2$\epsilon$ 均衡戦略である。 」
つまり、i=1,2 について、$R_i^t$ が 収束するような収束アルゴリズムを用いれば、$\epsilon$ ナッシュ均衡に収束する平均戦略 $\bar\sigma$ が得られるということ！
CFRの導入～～どのように average overall regret を収束させるのか
immediate counterfactual regret を以下のように定義する。
R^T_{i,imm}(I) = \frac{1}{T}{\rm max}_{a\in A(I)}\sum_{t=1}^T\pi_{-i}^{\sigma^t}(I)(u_i(\sigma^t|_{I\to a},I)-u_i(\sigma^t,I))
上式の説明
- $u_i(\sigma^t,I)$: counterfactual utility.
- the expected utility given that information set I is reached and all players play using strategy σ except that player i plays to reach I.
- This can be thought of as a “counterfactual” as it is the value to player i of be a strategy profile identical to σ except that player i always chooses action a when in information reaching information set I ifthe player had tried to do so.
$R^{T,+}_{i,imm}={\rm max}(R^T_{i,imm},0)$ とする。immediate counterfactual regret と average overall regret について以下の関係がある。
定理2 $R^{T}_{i} \leq \sum_{I\in \mathcal{I}} R^{T,+}_{i,imm}(I)$
つまり、右辺 $\sum_{I\in \mathcal{I}} R^{T,+}_{i,imm}(I)$ を最小化できれば、 $R^{T}_{i}$ を最小化することができ、定理1から $\epsilon$ ナッシュ均衡戦略が求まるということですね！
immediate counterfactual regret の重要な特徴は、$\sigma_i(I)$ だけを操作して最小化ができる点であることである。
Blackwell のアルゴリズムを用いて各情報集合ごとに独立に regret を更新する。
$$
R^T_i(I,a)=\frac{1}{T}\sum_{t=1}^T\pi_{-i}^{\sigma^t}(I)(u_i(\sigma^t|_{I\to a},I)-u_i(\sigma^t,I))
$$
とし(記法がややこしいがaverage over all regret とは別物)、$R_i^{T,+}(I,a)={\rm max}(R_i^T,0)$ と定義すると、$T+1$ の戦略を以下のように更新する。
$$
\sigma_i^{T+1}(a|I) = \begin{cases}
\frac{R_i^{T,+}(I,a)}{\sum_{a\in A(I)}R_i^{T,+}(I,a)} & {\rm if\ } \sum_{a\in A(I)} R_i^{T,+}(I,a)>0 \\
\frac{1}{|A(I)|} & {\rm otherwise.}
\end{cases}
$$
行動は、その行動を選択しなかったことによる正のcounterfactual regret に比例して選択される。
定理3 プレイヤー $i$ が上式に従って行動を選択するならば、$R^T_{i,imm}\leq\Delta_{u,i}\sqrt{|A_i|}/\sqrt{T}$となり、したがって $R_i^T\leq\Delta_{u,i}|\mathcal{I_i}|\sqrt{|A_i|}/\sqrt{T}$ となる。ここで、$|A_i|={\rm max}_{h:P(h)=i}|A(h)|$。
よってこの繰り返しアルゴリズム(これがCFRそのもの！)を用いれば、average oveall regret は0に収束し、ナッシュ均衡戦略が求まる！
TODO: 心(counterfactual の嬉しさ)をもっと説明する。
CFRの課題
課題1
CFR はそのままではポーカーなどの大きな情報空間を持つゲームには適応できない。
TODO: 詳細を調査してまとめる。
課題2
3人以上のゲームではCFRの収束が保証されていない(らしいが、文献はどこだろうか。)
CFRの効率化と他の手法との組み合わせ
実際には上記で説明した生のCFRは使われず、CFRの改良や他の手法との組み合わせが使われる。
CFRの改良として例えば以下があるようだ。
-
linear CFR (平均戦略をほんの一部変えたもの)
また、CFRと組み合わせて使われる手法として以下があるようだ。
- abstraction
- blueprint strategy
- nested subgame solving
- self improvement during the event
- これらは libratus で使われている。
参考情報
コードレベルでのCFRの解説
CFRの実験コードは、例えば以下で解説されている。
- An Introduction to Counterfactual Regret Minimization
-
Vanilla Counterfactual Regret Minimization for Engineers
- CFR は基礎なので、Vanilla(一番ノーマルなもの)と言っている。
その他の応用例
数式
- 見出し中の数式をレンダリングする方法が分からなかった。
- 下付き文字が入っているとうまくレンダリングしてくれず、_を\_に書き換えるとレンダリングが通ったりした(しなくても通ることがある)。