論文の概要: 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.07181v1
• Date: Mon, 14 Mar 2022 15:21:18 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-15 14:37:59.436877
• 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要約: 様々な種類の最適相関平衡を求める問題について検討する。 本稿では,特定の解の概念に依存する相関戦略の空間の表現である相関DAGを紹介する。 また、カードゲームブリッジのエンドゲームフェーズをエミュレートするトリックテイクゲームと、ライドシェアリングゲームという2つの新しいベンチマークゲームも導入した。
• 参考スコア（独自算出の注目度）: 99.00383370823839
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of finding optimal correlated equilibria of various sorts: normal-form coarse correlated equilibrium (NFCCE), extensive-form coarse correlated equilibrium (EFCCE), and extensive-form correlated equilibrium (EFCE). This is NP-hard in the general case and has been studied in special cases, most notably triangle-free games, which include all two-player games with public chance moves. However, the general case is not well understood, and algorithms usually scale poorly. First, we introduce the correlation DAG, a representation of the space of correlated strategies whose size is dependent on the specific solution concept. It extends the team belief DAG of Zhang et al. to general-sum games. For each of the three solution concepts, its size depends exponentially only on a parameter related to the game's information structure. 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 to compute optimal correlated strategies. 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. Our techniques outperform the prior state of the art for computing optimal general-sum correlated equilibria. For team games, the two-sided column generation approach vastly outperforms standard column generation approaches, making it the state of the art algorithm when the parameter is large. Along the way we also introduce two new benchmark games: a trick-taking game that emulates the endgame phase of the card game bridge, and a ride-sharing game.
• Abstract（参考訳）: 本研究では, 正規形粗相関平衡 (NFCCE) , 広範形粗相関平衡 (EFCCE) , 広範形粗相関平衡 (EFCE) の3種類の最適相関平衡を求める問題について検討した。 これは一般的な場合ではnp-hardであり、特に三角形のないゲームで研究されている。 しかし、一般的なケースはよく理解されておらず、アルゴリズムは通常、不十分にスケールする。 まず,特定の解の概念に依存する相関戦略の空間の表現である相関DAGを紹介する。 これは Zhang らのチーム信念 DAG を一般ゲームに拡張する。 3つの解の概念それぞれについて、その大きさはゲームの情報構造に関連するパラメータに指数関数的にのみ依存する。 nfcceのサイズ境界はzhangらによるチームゲームで達成されたものと似ているが、標準的な複雑性仮定の下で他の2つの概念で達成することは不可能である。 次に,最適相関戦略を計算するための2面列生成手法を提案する。 このアルゴリズムは,従来サポートに追加された相関計画に関して,プレイヤーがシーケンシャルな戦略を再最適化することを可能にする相関戦略の新たな分解によって,farinaら片面的アプローチを改善している。 本手法は,最適一般対等平衡計算における先行技術よりも優れている。 チームゲームでは、双方向コラム生成アプローチは標準的なコラム生成アプローチを大きく上回り、パラメータが大きい場合はartアルゴリズムの状態となる。 その過程で、カードゲームブリッジのエンドゲームフェーズをエミュレートするトリックテイクゲームと、ライドシェアリングゲームという、2つの新しいベンチマークゲームも導入しました。

関連論文リスト

• 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)

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

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