論文の概要: Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation

• arxiv url: http://arxiv.org/abs/2412.16934v1
• Date: Sun, 22 Dec 2024 09:12:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-24 15:52:37.051150
• Title: Efficiently Solving Turn-Taking Stochastic Games with Extensive-Form Correlation
• Title（参考訳）: 急激な形式相関を伴うターンテイキング確率ゲームの有効性
• Authors: Hanrui Zhang, Yu Cheng, Vincent Conitzer,
• Abstract要約: そこで我々は,Stackelbergの大規模相関平衡の計算アルゴリズムを提案する。 また,大域的相関平衡を近似計算するアルゴリズムも提案する。 ほぼ最適なEFCEのアルゴリズムは、私たちの知る限り、3つのデシラタを同時に達成した最初のアルゴリズムである。
• 参考スコア（独自算出の注目度）: 52.16923999754027
• License:
• Abstract: We study equilibrium computation with extensive-form correlation in two-player turn-taking stochastic games. Our main results are two-fold: (1) We give an algorithm for computing a Stackelberg extensive-form correlated equilibrium (SEFCE), which runs in time polynomial in the size of the game, as well as the number of bits required to encode each input number. (2) We give an efficient algorithm for approximately computing an optimal extensive-form correlated equilibrium (EFCE) up to machine precision, i.e., the algorithm achieves approximation error $\varepsilon$ in time polynomial in the size of the game, as well as $\log(1 / \varepsilon)$. Our algorithm for SEFCE is the first polynomial-time algorithm for equilibrium computation with commitment in such a general class of stochastic games. Existing algorithms for SEFCE typically make stronger assumptions such as no chance moves, and are designed for extensive-form games in the less succinct tree form. Our algorithm for approximately optimal EFCE is, to our knowledge, the first algorithm that achieves 3 desiderata simultaneously: approximate optimality, polylogarithmic dependency on the approximation error, and compatibility with stochastic games in the more succinct graph form. Existing algorithms achieve at most 2 of these desiderata, often also relying on additional technical assumptions.
• Abstract（参考訳）: 両プレーヤーのターンテイキング確率ゲームにおいて,広範な形式相関による平衡計算について検討した。 1)ゲームサイズで時間多項式を演算するスタックルバーグ拡張形式相関平衡(SEFCE)の計算アルゴリズムと,各入力数をエンコードするために必要なビット数を与える。 2) ゲームサイズにおける時間多項式の近似誤差$\varepsilonおよび$\log(1 / \varepsilon)$。 我々のSEFCEのアルゴリズムは、そのような一般確率ゲームにおけるコミットメントを伴う平衡計算のための最初の多項式時間アルゴリズムである。 既存のSEFCEのアルゴリズムは、通常、チャンス移動のないようなより強い仮定をし、より簡潔なツリー形式で広義のゲーム用に設計されている。 ほぼ最適なEFCEのアルゴリズムは、近似最適性、近似誤差への多対数依存、より簡潔なグラフ形式での確率ゲームとの整合性という3つのデシラタを同時に達成した最初のアルゴリズムである。 既存のアルゴリズムはこれらのデシダータのうち、少なくとも2つのデシダータを達成しており、しばしば追加の技術的仮定にも依存している。

関連論文リスト

• A Generalized Extensive-Form Fictitious Play Algorithm [0.0]
  両プレイヤー・ゼロサムゲームの平衡を求めるための単純な拡張形式アルゴリズムを提案する。 我々は,その性能を,類似の広義の虚偽プレイアルゴリズムと反実的後悔最小化アルゴリズムとを比較した。
  論文  参考訳（メタデータ） (2023-10-14T20:18:49Z)
• 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)
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
  ワイドフォームゲームにおいて,様々な種類の最適平衡を求める問題について検討する。 これら3つの概念のすべてに最適な平衡を計算するための新しいアルゴリズムを導入する。
  論文  参考訳（メタデータ） (2022-03-14T15:21:18Z)
• Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
  大規模2プレーヤワイドフォームゲームの計算平衡問題に対する反復的な一階法の適用について検討する。 正則化器を用いて一階法をインスタンス化することにより、相関平衡と元アンティー座標のチーム平衡を計算するための最初の加速一階法を開発する。
  論文  参考訳（メタデータ） (2021-05-27T06:10:24Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
  我々は、この問題に対して全く異なるアプローチを示し、それは競争力があり、しばしば、以前の最先端技術よりも桁違いに優れている。 ポーカーエンドゲームの実験により、現代の線形プログラムソルバは、ゲーム固有のCFRの現代的な変種でさえも競合することを示した。
  論文  参考訳（メタデータ） (2020-06-05T13:48:26Z)

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

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