論文の概要: Asynchronous Predictive Counterfactual Regret Minimization$^+$ Algorithm in Solving Extensive-Form Games

• arxiv url: http://arxiv.org/abs/2503.12770v1
• Date: Mon, 17 Mar 2025 03:07:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-18 15:59:24.858700
• Title: Asynchronous Predictive Counterfactual Regret Minimization$^+$ Algorithm in Solving Extensive-Form Games
• Title（参考訳）: 指数型ゲームの解法における非同期予測逆レギュレット最小化$^+$アルゴリズム
• Authors: Linjian Meng, Youzhi Zhang, Zhenxing Ge, Tianpei Yang, Yang Gao,
• Abstract要約: 予測的 CFR$+$ (PCFR$+$) は特に強力で、非常に高速な経験的収束率を達成する。 そこで我々は,ステップサイズの適応的非同期化を用いた新しい変種 Asynchronous PCFR$+$ (APCFR$+$) を提案する。 APCFR$+$がロバスト性を高める理由を理論的に示す。
• 参考スコア（独自算出の注目度）: 16.13246414155694
• License:
• Abstract: Counterfactual Regret Minimization (CFR) algorithms are widely used to compute a Nash equilibrium (NE) in two-player zero-sum imperfect-information extensive-form games (IIGs). Among them, Predictive CFR$^+$ (PCFR$^+$) is particularly powerful, achieving an exceptionally fast empirical convergence rate via the prediction in many games. However, the empirical convergence rate of PCFR$^+$ would significantly degrade if the prediction is inaccurate, leading to unstable performance on certain IIGs. To enhance the robustness of PCFR$^+$, we propose a novel variant, Asynchronous PCFR$^+$ (APCFR$^+$), which employs an adaptive asynchronization of step-sizes between the updates of implicit and explicit accumulated counterfactual regrets to mitigate the impact of the prediction inaccuracy on convergence. We present a theoretical analysis demonstrating why APCFR$^+$ can enhance the robustness. Finally, we propose a simplified version of APCFR$^+$ called Simple APCFR$^+$ (SAPCFR$^+$), which uses a fixed asynchronization of step-sizes to simplify the implementation that only needs a single-line modification of the original PCFR+. Interestingly, SAPCFR$^+$ achieves a constant-factor lower theoretical regret bound than PCFR$^+$ in the worst case. Experimental results demonstrate that (i) both APCFR$^+$ and SAPCFR$^+$ outperform PCFR$^+$ in most of the tested games, as well as (ii) SAPCFR$^+$ achieves a comparable empirical convergence rate with APCFR$^+$.
• Abstract（参考訳）: 対実回帰最小化(CFR)アルゴリズムは、2つのプレイヤーゼロサム不完全情報拡張形式ゲーム(IIG)におけるナッシュ均衡(NE)を計算するために広く用いられている。 その中でも予測的 CFR$^+$ (PCFR$^+$) は特に強力であり、多くのゲームにおいて予測によって非常に高速な経験的収束率を達成する。 しかし、PCFR$^+$の実証収束速度は、予測が不正確であれば著しく低下し、特定のIIGに対して不安定な性能をもたらす。 そこで我々は,PCFR$^+$のロバスト性を高めるために,暗黙的および明示的累積的反事実的後悔の更新の間に,ステップサイズを適応的に同化することにより,予測不正確さが収束に与える影響を緩和する新しい変種 Asynchronous PCFR$^+$ (APCFR$^+$) を提案する。 APCFR$^+$がロバスト性を高める理由を理論的に示す。 最後に, APCFR$^+$ と呼ばれる APCFR$^+$ (SAPCFR$^+$) の簡易版を提案する。 興味深いことに、SAPCFR$^+$ は、最悪の場合 PCFR$^+$ よりも定数要素の低い理論的後悔を達成する。 実験の結果 (i)APCFR$^+$、SAPCFR$^+$ともに、ほとんどのテストゲームにおいてPCFR$^+$を上回る。 (ii) SAPCFR$^+$ は APCFR$^+$ と同等な経験的収束率を達成する。

関連論文リスト

• Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent [44.080852682765276]
  本研究は,楽観的オンラインミラードライザー(OMD)による重み付き反事実的後悔の最小化を探求する。 PCFR+とDiscounted CFR(DCFR)を原則的に統合し、支配的な作用の負の効果を迅速に緩和する。 PDCFR+は不完全情報ゲームにおいて高速収束を示す実験結果が得られた。
  論文  参考訳（メタデータ） (2024-04-22T05:37:22Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。 本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
  論文  参考訳（メタデータ） (2023-10-21T18:38:13Z)
• Finite Time Regret Bounds for Minimum Variance Control of Autoregressive Systems with Exogenous Inputs [10.304902889192071]
  多くの適応型コントローラが経験した重要な課題は、学習の初期段階における経験的パフォーマンスの低下である。 本稿では,探索に探索入力を利用するCertainty Equivalence (CE)適応制御器の修正版を提案する。 ガウス下雑音の場合、T$の時間ステップとClog2の時間ステップの後の後悔に基づいて$C log T$と$Clog2 T$を持つことを示す。
  論文  参考訳（メタデータ） (2023-05-26T14:29:33Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• The Power of Regularization in Solving Extensive-Form Games [22.557806157585834]
  本稿では,ゲームにおける支払関数の正規化に基づく新しいアルゴリズムを提案する。 特に、拡張された楽観的ミラー降下(DOMD)が高速な$tilde O(T)$ last-iterate convergenceを達成できることを示す。 また、Reg-CFRは、楽観的ミラー降下アルゴリズムの変形を最小化して、$O(T1/4)$ベストイテレート、$O(T3/4)$平均イテレート収束率を達成できることを示した。
  論文  参考訳（メタデータ） (2022-06-19T22:10:38Z)
• 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)
• LSDAT: Low-Rank and Sparse Decomposition for Decision-based Adversarial Attack [74.5144793386864]
  LSDATは、入力サンプルのスパース成分と対向サンプルのスパース成分によって形成される低次元部分空間における摂動を加工する。 LSDは画像ピクセル領域で直接動作し、スパース性などの非$ell$制約が満たされることを保証します。
  論文  参考訳（メタデータ） (2021-03-19T13:10:47Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  ディスカウント型MDPのための2倍堅牢なオフポリチックAC(DR-Off-PAC)を開発した。 DR-Off-PACは、俳優と批評家の両方が一定のステップで同時に更新される単一のタイムスケール構造を採用しています。 有限時間収束速度を研究し, dr-off-pac のサンプル複雑性を特徴とし, $epsilon$-accurate optimal policy を得る。
  論文  参考訳（メタデータ） (2021-02-23T18:56:13Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。