論文の概要: Normal-Form Correlation in Markov Games

• arxiv url: http://arxiv.org/abs/2610.03621v1
• Date: Fri, 02 Oct 2026 17:18:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:14:30.511173
• Title: Normal-Form Correlation in Markov Games
• Title（参考訳）: マルコフゲームにおける正規形式相関
• Abstract要約: 我々は,一定数のプレイヤーを持つ有限ホライゾンゲームにおいて,NFCEの最初の効率的なアルゴリズムを確立する。 PPAD完全性(PPAD-completeness)、すなわち、多人数ゲームにおいて、あるいは指数的に精度が小さい場合に、ナッシュ平衡と計算等価性を示す。
• 参考スコア（独自算出の注目度）: 87.25174053648612
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: There has been a surge of recent work on correlated equilibrium concepts in Markov games. However, existing results focus on concepts weaker than normal-form correlated equilibria (NFCEs), leaving open the more challenging question of computing such equilibria, which goes back to the seminal work of Papadimitriou and Roughgarden (JACM'08). Here, we establish the first efficient algorithm for NFCEs in finite-horizon Markov games with a fixed number of players $n$. In particular, with $S$ states, horizon $H$, and at most $A$ actions per player, it computes an $ε$-NFCE in time $S(AH/ε)^{O(n)}$. This is the first algorithm polynomial in $1/ε$ and the description of the game for NFCEs in an interesting class of problems beyond the normal-form setting. Moreover, under the usual assumption that recommendations are independent across states, we show PPAD-completeness---that is, computational equivalence to Nash equilibria---either in many-player games or when the precision is exponentially small. The key idea behind our approach is to run backward induction on a sequence of auxiliary stage games, but with the twist that in each step we compute a constant-expectation correlated equilibrium. This is a natural refinement of correlated equilibrium in which the conditional expected payoff from obeying is independent of the recommendation. In fact, our reduction goes both ways, establishing an equivalence between constant-expectation CEs and NFCEs in Markov games. For a fixed number of players, we observe that a constant-expectation CE can be computed approximately by combining linear programming with suitable discretization. In contrast, it is PPAD-hard in i) polymatrix (many-player) games at constant precision, and ii) two-player games at exponentially small precision. The latter result follows from an unexpected connection to rank-2 two-player games.
• Abstract（参考訳）: マルコフゲームにおける相関平衡の概念に関する最近の研究が急増している。 しかし、既存の結果は通常の形式相関平衡(NFCEs)よりも弱い概念に焦点が当てられており、パパディミトリオとラフガルデン(JACM'08)の独創的な研究に遡る、そのような平衡の計算に関するより難しい問題を解き放つ。 ここでは、一定数のプレイヤーを持つ有限水平マルコフゲームにおいて、NFCEsのアルゴリズムを初めて確立する。 特に、$S$状態、平らな$H$、少なくともプレイヤー当たりの$A$アクションでは、時間$S(AH/ε)^{O(n)}$で$ε$-NFCEを計算する。 これは1/ε$で最初のアルゴリズム多項式であり、NFCEsのゲームの説明は、通常の形式設定を超えた興味深い問題のクラスである。 さらに、レコメンデーションが各州で独立であるという通常の仮定の下では、PPAD完全性、すなわち、多くのプレイヤーゲームにおいて、あるいは指数関数的に精度が小さい場合に、ナッシュ均衡に対する計算的等価性を示す。 このアプローチの背景にある重要な考え方は、補助的なステージゲーム列上で後方誘導を実行することであるが、各ステップで一定の相関均衡を計算するというツイストがある。 これは相関均衡の自然な洗練であり、従うことによる条件付き期待された支払いは推奨とは無関係である。 実際、当社の削減は両方向に進み、マルコフゲームにおける一定の観測CEとNFCEの等価性を確立する。 一定数のプレイヤーに対して、線形プログラミングと適切な離散化を組み合わせることで、定数探索CEを近似的に計算できることを観察する。 対照的にPPADハードである。 一 一定精度の多面体ゲーム(多人数遊技者)及び 二 指数的に小精度の2人プレイヤゲーム。 後者の結果は、ランキング2の2プレイヤーゲームとの予期せぬつながりによるものである。

関連論文リスト

• Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
  乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。 結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
  論文  参考訳（メタデータ） (2024-11-04T00:39:52Z)
• $\widetilde{O}(T^{-1})$ Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Games [8.215874655947335]
  楽観的フォロー・ザ・レギュラライズド・リーダー・アルゴリズムは,フル情報汎用マルコフゲームにおいて,$widetildeO(T-1)$-approximate iterationsを$T$内で見つけることができることを示す。
  論文  参考訳（メタデータ） (2024-02-02T20:40:27Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。 我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
  論文  参考訳（メタデータ） (2023-12-19T11:34:10Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Learning Stationary Nash Equilibrium Policies in $n$-Player Stochastic Games with Independent Chains [2.132096006921048]
  我々は、プレイヤーがペイオフ機能を介して結合されている間、内部の状態/行動空間を持つ、$n$プレイヤゲームのクラスを考える。 このクラスのゲームに対して、報奨関数を仮定せずに定常ナッシュ(NE)ポリシーを見つけることは、対話可能であることを示す。 我々は,2重平均化と2重ミラー降下に基づくアルゴリズムを開発し,これを$epsilon$-NEポリシーの集合に収束させる。
  論文  参考訳（メタデータ） (2022-01-28T16:27:21Z)
• When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently? [10.397170312149067]
  本稿では,m$-player General-sum Markovゲームの設定において,学習目標がより優れたサンプル複雑性を許容するものについて検討する。 まず,$epsilon$-Coarse Correlated Equilibrium (CCE)を$widetildemathcalO(H5Smax_ile m A_i / epsilon2)$ episodesで学習するアルゴリズムを設計する。 第二に、マルコフポテンシャルゲームの重要な特別な場合を考え、$widet内で$epsilon$-approximate Nash平衡を学ぶアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-10-08T15:06:22Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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