概要
| CFR | |
| 英名 | CounterFactual Regret Minimization |
| 別名 | 反実仮想後悔最小化 |
CFRとは、ナッシュ均衡を求めるゲーム理論のアルゴリズムの一種。これ自体が強化学習ではないが、後続の深層強化学習系の手法では強化学習手法を取り入れている。
歴史
表形式CFRの歴史
2007年、Regret Matchingを展開型ゲームに適用した「CFR」が発表された。当時のCFRには、ゲーム木の全探索が必要なため、大規模なゲームには適用できないという課題があった。
2009年には、ゲーム木全体を走査するのではなく、一部をサンプリングして計算する「MCCFR」が発表された。
2014年には、CFRの高速化手法として「CFR+」が登場する。翌2015年には、このCFR+を組み込んだ手法によって、ヘッズアップ・リミット・ホールデム（Heads-up limit hold’em poker）が完全に解決された。
2018年には、MCCFRの分散を低減する「VR-MCCFR」が発表された。
2019年には、さらなる高速化手法として「Linear CFR」および「DCFR」が発表された。なお、Linear CFRはDCFRの特殊なケースとして位置づけられる。
2020年には、鏡像降下法とRegret Matchingのアイデアを融合させた「PCFR+」が発表された。
2024年には、これまでのCFR+、DCFR、PCFR+の各手法を組み合わせた「DCFR+/PDCFR+」が発表されている。
ニューラルCFRの歴史
従来の表形式CFRでは、計算量を抑えるためにゲーム木のサイズを縮小する「抽象化」技術が不可欠であった。しかし、抽象化にはゲームに対する深い専門知識が必要であり、不適切な抽象化は戦略の質を低下させるという問題があった。また、特定のゲームに特化した抽象化は汎用性にも欠けていた。
2019年に発表された「Deep CFR」は、ニューラルネットワークによる関数近似を用いることで、手動の抽象化を不要にした。Deep CFRは、累積リグレットを近似するネットワークと、最終的な戦略を近似する平均戦略ネットワークの2つで構成されていた。同年、平均戦略ネットワークを廃止し、一つのネットワークに統合した「SD-CFR」も発表されている。
2020年の「DREAM」は、シミュレータに依存していたDeep CFRに分散削減技術を導入した手法である。これにより、モデルフリーでの安定した学習が可能となった。DREAMは重要度サンプリングにより、学習の不安定化が起こるという問題が残っていた。
2022年に発表された「ESCHER」は、固定されたサンプリング用方策を使うことで、重要度サンプリングを廃止して、学習を安定化させた。
2025年には、「VR-DeepDCFR+/VR-DeepPDCFR+」が発表された。これまでの手法は、LinearCFRを近似していたが、この手法では、DCFR+やPDCFR+といった最新の表形式CFRを近似することで、性能を向上させた。
参考になる文献
- CFRの原論文
- Regret minimization in games with incomplete information
