論文の概要: Efficient Last-iterate Convergence Algorithms in Solving Games
- arxiv url: http://arxiv.org/abs/2308.11256v2
- Date: Tue, 18 Mar 2025 08:31:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-19 14:12:54.897937
- Title: Efficient Last-iterate Convergence Algorithms in Solving Games
- Title（参考訳）: 問題解決ゲームにおける効率的な最終項目収束アルゴリズム
- Authors: Linjian Meng, Youzhi Zhang, Zhenxing Ge, Shangdong Yang, Tianyu Ding, Wenbin Li, Tianpei Yang, Bo An, Yang Gao,
- Abstract要約: 近年の研究では、元のEFGのNEを、(摂動された)正規化されたEFGの列のNEを学ぶように再構成している。
本稿では,古典的パラメータフリーなRMベースのCFRアルゴリズムであるCFR$+$が,摂動正規化EFGのNEを学習する際の最終点収束を実現することを証明する。
- 参考スコア（独自算出の注目度）: 29.25745562794961
- License:
- Abstract: To establish last-iterate convergence for Counterfactual Regret Minimization (CFR) algorithms in learning a Nash equilibrium (NE) of extensive-form games (EFGs), recent studies reformulate learning an NE of the original EFG as learning the NEs of a sequence of (perturbed) regularized EFGs. Consequently, proving last-iterate convergence in solving the original EFG reduces to proving last-iterate convergence in solving (perturbed) regularized EFGs. However, the empirical convergence rates of the algorithms in these studies are suboptimal, since they do not utilize Regret Matching (RM)-based CFR algorithms to solve perturbed EFGs, which are known the exceptionally fast empirical convergence rates. Additionally, since solving multiple perturbed regularized EFGs is required, fine-tuning across all such games is infeasible, making parameter-free algorithms highly desirable. In this paper, we prove that CFR$^+$, a classical parameter-free RM-based CFR algorithm, achieves last-iterate convergence in learning an NE of perturbed regularized EFGs. Leveraging CFR$^+$ to solve perturbed regularized EFGs, we get Reward Transformation CFR$^+$ (RTCFR$^+$). Importantly, we extend prior work on the parameter-free property of CFR$^+$, enhancing its stability, which is crucial for the empirical convergence of RTCFR$^+$. Experiments show that RTCFR$^+$ significantly outperforms existing algorithms with theoretical last-iterate convergence guarantees.
- Abstract（参考訳）: 大規模ゲーム(EFG)のナッシュ均衡(NE)を学習する際のCFRアルゴリズムの最終的な収束を確立するため、近年の研究では、(摂動)正規化されたEFGの列のNEを学習する際、元のEFGのNEを学習するように再構成している。
その結果、元のEFGを解く際の最終点収束の証明は、(摂動された)正規化されたEFGを解く際の最終点収束の証明に還元される。
しかし、これらの研究におけるアルゴリズムの経験的収束速度は、非常に高速な経験的収束速度として知られる摂動EFGを解くためにレギュレットマッチング(RM)ベースのCFRアルゴリズムを使わないため、準最適である。
さらに、複数の摂動正規化EFGを解く必要があるため、そのようなゲームにまたがる微調整は不可能であり、パラメータフリーなアルゴリズムが極めて望ましい。
本稿では,古典的パラメータフリーなRMベースのCFRアルゴリズムであるCFR$^+$が,摂動正規化EFGのNEを学習する際の最終点収束を実現することを証明する。
摂動正規化EFGを解くために CFR$^+$ を利用すると、 Reward Transformation CFR$^+$ (RTCFR$^+$) が得られる。
重要なことは、CFR$^+$のパラメータフリー性に関する先行研究を拡張し、その安定性を高め、RTCFR$^+$の経験的収束に不可欠である。
実験により、RTCFR$^+$は理論上最後の収束保証で既存のアルゴリズムを著しく上回っていることが示された。
関連論文リスト
- Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent [44.080852682765276]
本研究は,楽観的オンラインミラードライザー(OMD)による重み付き反事実的後悔の最小化を探求する。
PCFR+とDiscounted CFR(DCFR)を原則的に統合し、支配的な作用の負の効果を迅速に緩和する。
PDCFR+は不完全情報ゲームにおいて高速収束を示す実験結果が得られた。
論文 参考訳（メタデータ） (2024-04-22T05:37:22Z) - Last-Iterate Convergence Properties of Regret-Matching Algorithms in
Games [72.43065138581589]
RM$+$ の様々な一般的な変種の最後の点収束特性について検討する。
本稿では, RM$+$の同時適用, RM$+$の交互化, RM$+$の予測, 最終項目収束保証の欠如など, 実用的バリエーションのいくつかを数値的に示す。
そして、スムーズな手法に基づく最近のアルゴリズムの変種は、最終点収束を楽しむことを証明した。
論文 参考訳（メタデータ） (2023-11-01T17:34:58Z) - 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) - 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) - HessianFR: An Efficient Hessian-based Follow-the-Ridge Algorithm for
Minimax Optimization [18.61046317693516]
HessianFR は理論的な保証を持つ効率的な Hessian-based Follow-the-Ridge アルゴリズムである。
合成および実世界の大規模画像データセットを用いてGAN(Generative Adversarial Network)のトレーニング実験を行った。
論文 参考訳（メタデータ） (2022-05-23T04:28:52Z) - 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) - 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) - Stochastic Regret Minimization in Extensive-Form Games [109.43344748069933]
Monte-Carlo counterfactual regret minimization (MCCFR) は、完全な木には大きすぎるシーケンシャルゲームを解くための最先端のアルゴリズムである。
後悔の最小化手法を開発するための新しい枠組みを開発する。
MCCFRよりも優れた方法がいくつかある3つのゲームについて広範な実験を行った。
論文 参考訳（メタデータ） (2020-02-19T23:05:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。