不完全情報下のRegret最小化(CFR)の論文を読む

ランニングできず 英語できず

(1) 不完全情報下のRegret最小化(CFR:Counterfactual Regret Minimization)の論文を読む

  「An Introduction to Counterfactual Regret Minimization」 http://modelai.gettysburg.edu/2013/cfr/cfr.pdf

  現状の強化学習は「完全情報下のReret最小化」と看做せます。

 何故なら強化学習は、情報が完全に見え累計した罰則の最小化モデルだからです。

 しかしポーカの様な相手の情報が一部見えない強化学習は

 「不完全情報下のRegret最小化」となります。このモデルはCFR(反作用的後悔最小化)

 と呼ばれています。

  現在モデルは下図の様に本格的Porkerゲームのプロに勝つレベルに達しており、

 モデルの正しさが実証されています。(Libratusがモデル)

f:id:mabonki0725:20171111112816p:plain

                   http://triblive.com/local/allegheny/11865933-74/rematch-aaron-aupperlee

  この論文はCFRの理論をToy Porkerでのプログラムで解説をしたものでです。

 この論文の貴重な点は、下記の様なCFRの理論記述が強化学習に比べ格段に難解である所を         

         R_i^T = \frac{1}{T} max_{\sigma_i^* \in \Sigma_i} \sum_{t=1}^T (u_i(\sigma_i^*,\sigma_{-i}^t) - u_i(\sigma^t))

         \hat{\sigma}_i^t (I)(a) = \frac{\sum_{t=1}^T \pi_i^{\sigma^t}(I) \sigma^t(I)(a)}{\sum_{t=1}^T \pi_i^{\sigma^t}(I)}

         ここで

             R_i^T:累計最大Regret

             \sigma_i^*:自分の最適戦略

     \sigma_{-1}^t:自分以外の戦略

             u_i(\sigma^t):戦略の価値

     \sigma_i^t(I)(a):情報Iで行動aを採った戦略

             \pi_i^{\sigma^t}(I):情報Iで戦略\sigma^tでの方策 

 プログラムで具体的に解説しています。

      現在のプロPorkerでは10^{16}に達する場合が存在しており、この成功は

 モデルの高速化と効率化がある程度旨く行っているからです。

 本論文ではJavaでのソースコードを解説していますが、C言語で書き直しました。

    GitHubに入れました。

 https://github.com/mabonki0725/regret_cfr

(2)デモ結果の説明

 ・ゲームの内容

  2人での対戦 カード1~3までの内各々がランダムにカードを取る

        大きいカードを持つ方が勝つ

  bit と poseが選択でき、bitして勝てば +2点 負ければ -2点

        双方がposeの場合、cardを見せ 勝てば +1点 負ければ -1 点

  相手がbit時にposeを選ぶと -1 点で負ける

  上記のルールでは下記の遷移図になる

  

         配布 --  pose -- pose (開示)

                  |             --  bit  -- pose (降りる)

                  |                        -- bit (勝負)

                  -   bit      -- pose (降りる)

                                 - bit (勝負)

       ・デモ結果

   自分のcardの値と各遷移での次の選択での得点できる価値を示している。

   例えば下記の3poseは 自分のカードが3で相手がposeの場合で

   自分がposeを選ぶと価値は79%でbitを選ぶと21%となっている。

   何故なら、3は最強のカードなので安心してbitしても相手が降りる可能性があり

   その場合は1点しか獲得できないからである。ならば確実に得点できるposeの方が

   価値が高い

 

3
 action=Pose avrage=0.000491
 action=Bet avrage=0.999509
3pose
 action=Pose avrage=0.788462
 action=Bet avrage=0.211538
3pose - bit
 action=Pose avrage=0.153846
 action=Bet avrage=0.846154
3bit
 action=Pose avrage=0.000076
 action=Bet avrage=0.999924
1
 action=Pose avrage=0.999848
 action=Bet avrage=0.000152
1pose
 action=Pose avrage=0.999924
 action=Bet avrage=0.000076
1pose - bit
 action=Pose avrage=0.999924
 action=Bet avrage=0.000076
1bit
 action=Pose avrage=0.500000
 action=Bet avrage=0.500000
2
 action=Pose avrage=0.056895
 action=Bet avrage=0.943105
2pose
 action=Pose avrage=0.998704
 action=Bet avrage=0.001296
2pose - bit
 action=Pose avrage=0.998704
 action=Bet avrage=0.001296
2bit
 action=Pose avrage=0.000078
 action=Bet avrage=0.999922

   

                   

           

 ・