論文の概要: Pure Monte Carlo Counterfactual Regret Minimization
- arxiv url: http://arxiv.org/abs/2309.03084v3
- Date: Fri, 13 Oct 2023 06:01:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-16 17:16:57.558321
- Title: Pure Monte Carlo Counterfactual Regret Minimization
- Title(参考訳): モンテカルロ対実レギュレット最小化
- Authors: Ju Qi, Ting Feng, Falun Hei, Zhemei Fang, Yunfeng Luo
- Abstract要約: 本稿ではCFRに基づくPure CFR(PCFR)と呼ばれる新しいアルゴリズムを提案する。
CFRとFPの組み合わせとして見ることができ、CFRから反実的後悔(値)の概念を継承している。
1つのイテレーションの時間と空間の複雑さを著しく減らすことができます。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Counterfactual Regret Minimization (CFR) and its variants are the best
algorithms so far for solving large-scale incomplete information games.
However, we believe that there are two problems with CFR: First, matrix
multiplication is required in CFR iteration, and the time complexity of one
iteration is too high; Secondly, the game characteristics in the real world are
different. Just using one CFR algorithm will not be perfectly suitable for all
game problems.
For these two problems, this paper proposes a new algorithm called Pure CFR
(PCFR) based on CFR. PCFR can be seen as a combination of CFR and Fictitious
Play (FP), inheriting the concept of counterfactual regret (value) from CFR,
and using the best response strategy instead of the regret matching strategy
for the next iteration. This algorithm has three advantages. First, PCFR can be
combined with any CFR variant. The resulting Pure MCCFR (PMCCFR) can
significantly reduce the time and space complexity of one iteration. Secondly,
our experiments show that the convergence speed of the PMCCFR is 2$\sim$3 times
that of the MCCFR. Finally, there is a type of game that is very suitable for
PCFR. We call this type of game clear-game, which is characterized by a high
proportion of dominated strategies. Experiments show that in clear-game, the
convergence rate of PMCCFR is two orders of magnitude higher than that of
MCCFR.
- Abstract(参考訳): 対実回帰最小化(CFR)とその変種は、大規模な不完全情報ゲームの解決に最適なアルゴリズムである。
しかし、CFRには2つの問題があると我々は信じている。まず、行列乗算はCFRイテレーションで必要であり、1つのイテレーションの時間的複雑さは高すぎる。
1つのCFRアルゴリズムを使用するだけでは、すべてのゲーム問題に完全に適合しない。
これら2つの問題に対して,CFRに基づくPure CFR(PCFR)と呼ばれる新しいアルゴリズムを提案する。
PCFR は CFR と Fictitious Play (FP) の組み合わせと見なすことができ、CFR から反実的後悔 (value) の概念を継承し、次のイテレーションの後悔マッチング戦略の代わりに最良の反応戦略を使用する。
このアルゴリズムには3つの利点がある。
まず、PCFRは任意のCFR変種と組み合わせることができる。
その結果、PMCCFR(Pure MCCFR)は、1イテレーションの時間と空間の複雑さを著しく減少させる。
第2に,PMCCFRの収束速度がMCCFRの2$\sim$3であることを示す。
最後に、PCFRに非常に適したタイプのゲームが存在する。
この種のゲームクリアゲームと呼び、支配的な戦略の比率が高いのが特徴です。
実験の結果,PMCCFRの収束速度はMCCFRよりも2桁高いことがわかった。
関連論文リスト
- CFR-p: Counterfactual Regret Minimization with Hierarchical Policy
Abstraction, and its Application to Two-player Mahjong [2.741266294612776]
ゲーム理論解析を行い、勝利ポリシーに基づいてCFRに階層的な抽象化を施すことにより、2人のプレイヤー・マヒョンについて研究する。
このフレームワークは、他の不完全な情報ゲームに一般化することができる。
論文 参考訳(メタデータ) (2023-07-22T14:38:47Z) - Equivalence Analysis between Counterfactual Regret Minimization and
Online Mirror Descent [67.60077332154853]
反実的回帰最小化(英: Counterfactual Regret Minimization, CFR)は、局所的反実的後悔を最小化することにより、全遺を最小化する後悔最小化アルゴリズムである。
FTRL(Follow-the-Regularized-Lead)アルゴリズムとOMD(Online Mirror Descent)アルゴリズムは,オンライン凸最適化における最小化アルゴリズムである。
本稿では,CFR と Regret Matching+ の CFR が FTRL および OMD の特別な形式であることを証明し,CFR を解析・拡張する新しい方法を提案する。
論文 参考訳(メタデータ) (2021-10-11T02:12:25Z) - Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。
これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
論文 参考訳(メタデータ) (2021-06-27T22:02:26Z) - NNCFR: Minimize Counterfactual Regret with Neural Networks [4.418221583366099]
本稿では, textitDeep CFRの改良版である textitNeural Network Counterfactual Regret Minimization (NNCFR) を紹介する。
textitNNCFRは、TextitDeep CFRよりも早く収束し、より安定して動作する。
論文 参考訳(メタデータ) (2021-05-26T04:58:36Z) - Model-free Neural Counterfactual Regret Minimization with Bootstrap
Learning [10.816436463322237]
現在のCFRアルゴリズムは、累積的後悔をニューラルネットワークで近似する必要がある。
新しいCFR変種であるRecursive CFRが提案され、Recursive Substitute Values (RSVs) によって累積的後悔が回復される。
新しい再帰的CFRはナッシュ平衡に収束することが証明されている。
実験の結果、新しいアルゴリズムは最先端のニューラルCFRアルゴリズムと一致できるが、トレーニングのオーバーヘッドは少ないことがわかった。
論文 参考訳(メタデータ) (2020-12-03T12:26:50Z) - Recurrent Feature Reasoning for Image Inpainting [110.24760191732905]
Recurrent Feature Reasoning (RFR) は主にプラグアンドプレイの Recurrent Feature Reasoning モジュールと Knowledge Consistent Attention (KCA) モジュールで構築されている。
RFRモジュールは、畳み込み特徴写像の穴の境界を反復的に推論し、さらに推論の手がかりとして利用する。
RFRの特徴マップ内の離れた場所からの情報を取得するため、我々はさらにKCAを開発し、RFRに組み込む。
論文 参考訳(メタデータ) (2020-08-09T14:40:04Z) - Faster Game Solving via Predictive Blackwell Approachability: Connecting
Regret Matching and Mirror Descent [119.5481797273995]
FTRL (Follow-the-regularized-leader) とオンラインミラー降下 (OMD) は、オンライン凸最適化における最も一般的な後悔の最小化手法である。
RMとRM+はFTRLとOMDをそれぞれ実行し、ブラックウェルのアプローチ性ゲームにおいて、ハーフスペースを常に強制的に選択するアルゴリズムであることを示す。
18の共通ゼロサムワイドフォームベンチマークゲームを対象とした実験では,予測的RM+と反ファクト的後悔の最小化が,最速のアルゴリズムよりもはるかに高速に収束することを示した。
論文 参考訳(メタデータ) (2020-07-28T16:49:55Z) - Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
我々は、この問題に対して全く異なるアプローチを示し、それは競争力があり、しばしば、以前の最先端技術よりも桁違いに優れている。
ポーカーエンドゲームの実験により、現代の線形プログラムソルバは、ゲーム固有のCFRの現代的な変種でさえも競合することを示した。
論文 参考訳(メタデータ) (2020-06-05T13:48:26Z) - Stochastic Regret Minimization in Extensive-Form Games [109.43344748069933]
Monte-Carlo counterfactual regret minimization (MCCFR) は、完全な木には大きすぎるシーケンシャルゲームを解くための最先端のアルゴリズムである。
後悔の最小化手法を開発するための新しい枠組みを開発する。
MCCFRよりも優れた方法がいくつかある3つのゲームについて広範な実験を行った。
論文 参考訳(メタデータ) (2020-02-19T23:05:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。