論文の概要: Projected Exploitability Descent for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games

• arxiv url: http://arxiv.org/abs/2606.29169v1
• Date: Sun, 28 Jun 2026 03:25:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-30 18:07:15.820992
• Title: Projected Exploitability Descent for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
• Title（参考訳）: マルチプレイヤー不完全情報ゲームにおけるナッシュ平衡計算のための投射可能性の予測
• Abstract要約: 我々はPED(Projected exploitability descend)と呼ばれる新しいアルゴリズムを導入する。 PEDは、一般化された利用可能性関数を最小限に抑える段階的な降下を実行することで機能する。 PEDは全走行を通して一貫したほぼ単調な改善が得られることがわかった。 このことがFP-PEDのハイブリッド化を刺激し、FPを初期燃焼期間からPEDに切り替えて安定な長期精製を行う。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many important games have more than two players and imperfect information. Existing approaches for computing Nash equilibrium, the central game-theoretic solution concept, in such games either lack scalability or obtain poor performance. In this paper we introduce a new algorithm called projected exploitability descent (PED) for approximating Nash equilibria in multiplayer games of imperfect information. The algorithm works by running projected subgradient descent minimizing a proxy for the multiplayer generalized exploitability function. The objective is nonconvex and nonsmooth, but can be represented as the sum of the maxima of linear functions, for which a subgradient can easily be computed and projected to the polytope of feasible sequence-form strategies. We explore performance of PED on a generalized version of the well-studied benchmark game three-player Kuhn poker. No prior exact algorithms scale to the version of the game with deck size larger than 4, and we compare performance to the popular algorithms of fictitious play (FP) and counterfactual regret minimization (CFR). We find that PED obtains a consistent near-monotonic improvement throughout all runs, though both FP and CFR perform significantly better in the initial iterations. This inspires a hybrid algorithm FP-PED that runs FP for an initial burn-in period before switching to PED for stable long-run refinement. We can alternatively view this as a multi-step algorithm that runs FP as a pre-processing step to obtain a strong initialization for PED.
• Abstract（参考訳）: 多くの重要なゲームは2人以上のプレイヤーと不完全な情報を持っている。 ゲーム理論の中心的な概念であるナッシュ均衡を計算するための既存のアプローチは、スケーラビリティが欠如しているか、性能が劣っているかのいずれかである。 本稿では,不完全な情報を持つマルチプレイヤーゲームにおいて,Nash平衡を近似するために,PED(Projected exploitability descent)と呼ばれる新しいアルゴリズムを提案する。 このアルゴリズムは、マルチプレイヤー一般化されたエクスプロイラビリティ関数のプロキシを最小限に抑えるために、プロジェクテッドな下位降下を実行することで機能する。 目的は非凸かつ非平滑であるが、線形関数の最大値の和として表すことができ、その次数は容易に計算され、実行可能なシーケンス形式戦略のポリトープに投影される。 我々は、よく研究されたベンチマークゲーム「クーンポーカー」の一般化版上でのPEDの性能について検討する。 既定の正確なアルゴリズムはデッキサイズが4より大きいゲームにスケールしないので,FP(Factitious Play)やCFR(Countfactual regret minimization)といった一般的なアルゴリズムと比較する。 PEDは全走行において一貫したほぼ単調な改善が得られたが、FPとCFRはいずれも初期イテレーションにおいて大幅に改善されている。 これはFP-PEDというハイブリッドアルゴリズムにインスピレーションを与え、FPはPEDに切り替えて安定な長期改良を行う。 我々は、これをFPを前処理ステップとして実行し、PEDの強力な初期化を得るマルチステップアルゴリズムとみなすことができる。

関連論文リスト

• Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games [0.0]
  本稿では,非線形近似に基づく2次制約付きプログラムを解くマルチプレイヤー不完全情報ゲームにおける近似手法を提案する。 また,マルチプレイヤー戦略型ゲームにおけるナッシュ均衡の計算手法も提案した。
  論文  参考訳（メタデータ） (2025-09-30T00:28:21Z)
• Reevaluating Policy Gradient Methods for Imperfect-Information Games [94.45878689061335]
  我々は,不完全情報ゲームにおけるDRLアルゴリズムの最大利用可能性比較を行う。 FP-、DO-、CFR-ベースのアプローチは、一般的なポリシー勾配法を上回りません。
  論文  参考訳（メタデータ） (2025-02-13T03:38:41Z)
• Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation [52.16923999754027]
  そこで我々は,Stackelbergの大規模相関平衡の計算アルゴリズムを提案する。 また,大域的相関平衡を近似計算するアルゴリズムも提案する。 ほぼ最適なEFCEのアルゴリズムは、私たちの知る限り、3つのデシラタを同時に達成した最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2024-12-22T09:12:05Z)
• Planning and Learning with Adaptive Lookahead [74.39132848733847]
  ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。 近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。 本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
  論文  参考訳（メタデータ） (2022-01-28T20:26:55Z)
• Anytime Optimal PSRO for Two-Player Zero-Sum Games [17.821479538423155]
  Policy Space Response Oracles (PSRO) は、継続的なアクションを扱うことができるゲームのための強化学習アルゴリズムである。 AODOは、ナッシュ均衡に収束する2プレイヤーゼロサムゲームのための二重オラクルアルゴリズムである。 提案手法は, DOやPSROよりもはるかに低いエクスプロイザビリティを実現し, エクスプロイザビリティを向上しないことを示す。
  論文  参考訳（メタデータ） (2022-01-19T16:34:11Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
  我々は、この問題に対して全く異なるアプローチを示し、それは競争力があり、しばしば、以前の最先端技術よりも桁違いに優れている。 ポーカーエンドゲームの実験により、現代の線形プログラムソルバは、ゲーム固有のCFRの現代的な変種でさえも競合することを示した。
  論文  参考訳（メタデータ） (2020-06-05T13:48:26Z)

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

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