Counterfactual Regret Minimaization(CFR)の基礎

ポーカーAIのアルゴリズムを調べていたら、CFRというアルゴリズムが基礎であることが分かった。元論文を読んでCFRについてまとめながら理解した。これはその記録である。

CFRは、 $\epsilon$ ナッシュ均衡を実現する平均戦略 $\bar\sigma$ を繰り返し計算で求めるアルゴリズムである。

CFR の提案論文(だと思っているが違うかもしれない) [Regret Minimization in Games with Incomplete Information](http://martin.zinkevich.org/publications/regretpoker.pdf)のアルゴリズムの基礎部分を中心に解説する。論文中の証明は省略する。定理番号は元論文と異なることに注意。

この文章は不十分な箇所が多い。この記事を足がかりに次に進んでいただければ幸い。

## そもそもなぜ $\epsilon$ ナッシュ均衡を求めるのか

そもそもナッシュ均衡を求める理由について先に述べる。この節の説明は[Counterfactual Regret Minimization – the core of Poker AI beating professional players](https://int8.io/counterfactual-regret-minimization-for-poker-ai/)]を参考にした。

- ナッシュ均衡とは

  > **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$ を以下のように定義する。

```math 
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 を以下のように定義する。

```math
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の収束が保証されていない([らしい](https://www.slideshare.net/KenshiAbe/ai-165308197)が、文献はどこだろうか。)

## CFRの効率化と他の手法との組み合わせ

実際には上記で説明した生のCFRは使われず、CFRの改良や他の手法との組み合わせが使われる。

CFRの改良として例えば以下があるようだ。

- [CFR+](https://poker.cs.ualberta.ca/publications/2015-ijcai-cfrplus.pdf) 

- [linear CFR](https://arxiv.org/pdf/1809.04040.pdf) (平均戦略をほんの一部変えたもの)
- [Deep CFR](https://arxiv.org/pdf/1811.00164.pdf)

また、CFRと組み合わせて使われる手法として以下があるようだ。

- abstraction 
- blueprint strategy
- nested subgame solving
- self improvement during the event
  - これらは libratus で使われている。

## 参考情報

### コードレベルでのCFRの解説

CFRの実験コードは、例えば以下で解説されている。

- [An Introduction to Counterfactual Regret Minimization
](http://modelai.gettysburg.edu/2013/cfr/cfr.pdf)
- [Vanilla Counterfactual Regret Minimization for Engineers](https://justinsermeno.com/posts/cfr/)
  - CFR は基礎なので、Vanilla(一番ノーマルなもの)と言っている。

### その他の応用例

- ポーカーのほかにも[花札](https://adtech.cyberagent.io/research/archives/2522)を解くためにも使われているようだ。
  - またこの方の[このスライド](https://www.slideshare.net/KenshiAbe/ai-165308197)は、調査の初めに雰囲気を知るためにとても参考になった。

## 数式
- 見出し中の数式をレンダリングする方法が分からなかった。
- 下付き文字が入っているとうまくレンダリングしてくれず、_を\\_に書き換えるとレンダリングが通ったりした(しなくても通ることがある)。