論文の概要: Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation

• arxiv url: http://arxiv.org/abs/2203.07181v2
• Date: Fri, 11 Oct 2024 01:10:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-14 13:29:02.473214
• Title: Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation
• Title（参考訳）: 一般集中型ゲームにおける最適相関平衡:固定パラメータアルゴリズム、硬度および2次元カラム生成
• Authors: Brian Zhang, Gabriele Farina, Andrea Celli, Tuomas Sandholm,
• Abstract要約: ワイドフォームゲームにおいて,様々な種類の最適平衡を求める問題について検討する。 これら3つの概念のすべてに最適な平衡を計算するための新しいアルゴリズムを導入する。
• 参考スコア（独自算出の注目度）: 78.48747645545944
• License:
• Abstract: We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games: normal-form coarse correlated equilibrium (NFCCE), extensive-form coarse correlated equilibrium (EFCCE), and extensive-form correlated equilibrium (EFCE). We make two primary contributions. First, we introduce a new algorithm for computing optimal equilibria in all three notions. Its runtime depends exponentially only on a parameter related to the information structure of the game. We also prove a fundamental complexity gap: while our size bounds for NFCCE are similar to those achieved in the case of team games by Zhang et al., this is impossible to achieve for the other two concepts under standard complexity assumptions. Second, we propose a two-sided column generation approach for use when the runtime or memory usage of the previous algorithm is prohibitive. Our algorithm improves upon the one-sided approach of Farina et al. by means of a new decomposition of correlated strategies which allows players to re-optimize their sequence-form strategies with respect to correlation plans which were previously added to the support. Experiments show that our techniques outperform the prior state of the art for computing optimal general-sum correlated equilibria.
• Abstract（参考訳）: 広角形ゲームにおいて,正規形式粗相関平衡(NFCCE),広角形粗相関平衡(EFCCE),広角形粗相関平衡(EFCE)の様々な種類の最適平衡を求める問題について検討した。 主な貢献は2つある。 まず,3つの概念のすべてにおいて最適な平衡を計算するための新しいアルゴリズムを提案する。 その実行時間は、ゲームの情報構造に関連するパラメータのみに指数関数的に依存する。 NFCCEのサイズ境界は、Zhangらによるチームゲームの場合と似ているが、標準的な複雑性仮定の下では、他の2つの概念では達成できない。 第2に,従来のアルゴリズムの実行時やメモリ使用が禁じられている場合に使用する2面列生成手法を提案する。 提案アルゴリズムはFarinaらの一方的なアプローチを改善するために,従来サポートに追加された相関計画に関して,プレイヤーがシーケンス形式の戦略を再最適化することのできる,新たな相関戦略の分解を行う。 実験により,本手法は最適一般相対相関平衡計算における先行技術よりも優れていることが示された。

関連論文リスト

• Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games [44.95137108337898]
  我々は、相関平衡を計算するために、ほぼ最適の$tildeO(T-1)$収束率を得る未結合のポリシー最適化アルゴリズムを提供する。 我々のアルゴリズムは2つの主要素(スムーズな値更新)と(楽観的で規則化されたリーダーアルゴリズムとログバリア正規化器)を組み合わせることで構築される。
  論文  参考訳（メタデータ） (2024-01-26T23:13:47Z)
• ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
  ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。 本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
  論文  参考訳（メタデータ） (2023-12-04T19:00:07Z)
• The Computational Complexity of Single-Player Imperfect-Recall Games [37.550554344575]
  本研究では,不完全なリコールを伴う広義のゲーム,例えばスリーピングビューティー問題やAbsent Driverゲームについて検討する。 そのようなゲームに対して、2つの自然な平衡概念が、最適解の代替概念として提案されている。
  論文  参考訳（メタデータ） (2023-05-28T19:41:25Z)
• Offline Learning in Markov Games with General Function Approximation [22.2472618685325]
  マルコフゲームにおけるオフラインマルチエージェント強化学習(RL)について検討する。 マルコフゲームにおけるサンプル効率のよいオフライン学習のための最初のフレームワークを提供する。
  論文  参考訳（メタデータ） (2023-02-06T05:22:27Z)
• Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games [63.60117916422867]
  本稿では,対戦型マルチエージェントRLの最も基本的な設定,すなわち2プレーヤゼロサムマルコフゲームに焦点を当てる。 両エージェントから対称更新を施した単一ループポリシー最適化手法を提案し,この手法はエントロピー規則化楽観的乗算重み更新法(OMWU)によって更新される。 我々の収束結果は、最もよく知られた複雑性を改善し、競合するマルコフゲームにおけるポリシー最適化をよりよく理解する。
  論文  参考訳（メタデータ） (2022-10-03T16:05:43Z)
• Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
  大規模2プレーヤワイドフォームゲームの計算平衡問題に対する反復的な一階法の適用について検討する。 正則化器を用いて一階法をインスタンス化することにより、相関平衡と元アンティー座標のチーム平衡を計算するための最初の加速一階法を開発する。
  論文  参考訳（メタデータ） (2021-05-27T06:10:24Z)
• Polynomial-Time Computation of Optimal Correlated Equilibria in Two-Player Extensive-Form Games with Public Chance Moves and Beyond [107.14897720357631]
  本研究では,公的なチャンス移動を伴う2人プレイヤゲームにおいて,最適相関平衡が時間内に計算可能であることを示す。 この結果、10年以上にわたる広範な形式の相関を取り巻く最大の正の複雑性結果が得られた。
  論文  参考訳（メタデータ） (2020-09-09T14:51:58Z)

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

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