論文の概要: Approximating Nash Equilibria in General-Sum Games via Meta-Learning

• arxiv url: http://arxiv.org/abs/2504.18868v1
• Date: Sat, 26 Apr 2025 09:33:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-02 19:15:54.026006
• Title: Approximating Nash Equilibria in General-Sum Games via Meta-Learning
• Title（参考訳）: メタラーニングによる一般サムゲームにおけるナッシュ平衡の近似
• Authors: David Sychrovský, Christopher Solinas, Revan MacQueen, Kevin Wang, James R. Wright, Nathan R. Sturtevant, Michael Bowling,
• Abstract要約: 我々はメタラーニングを用いて、後悔の最小化による戦略の相関を最小化する。 我々のアルゴリズムは、最先端の後悔最小化手法よりも、ナッシュ平衡の近似がはるかに優れている。
• 参考スコア（独自算出の注目度）: 18.688759383834345
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Nash equilibrium is perhaps the best-known solution concept in game theory. Such a solution assigns a strategy to each player which offers no incentive to unilaterally deviate. While a Nash equilibrium is guaranteed to always exist, the problem of finding one in general-sum games is PPAD-complete, generally considered intractable. Regret minimization is an efficient framework for approximating Nash equilibria in two-player zero-sum games. However, in general-sum games, such algorithms are only guaranteed to converge to a coarse-correlated equilibrium (CCE), a solution concept where players can correlate their strategies. In this work, we use meta-learning to minimize the correlations in strategies produced by a regret minimizer. This encourages the regret minimizer to find strategies that are closer to a Nash equilibrium. The meta-learned regret minimizer is still guaranteed to converge to a CCE, but we give a bound on the distance to Nash equilibrium in terms of our meta-loss. We evaluate our approach in general-sum imperfect information games. Our algorithms provide significantly better approximations of Nash equilibria than state-of-the-art regret minimization techniques.
• Abstract（参考訳）: ナッシュ均衡はおそらくゲーム理論における最もよく知られた解概念である。 このような解決策は、一方的に逸脱するインセンティブのない各プレイヤーに戦略を割り当てる。 ナッシュ均衡は常に存在することが保証されているが、一般のゲームでそれを見つける問題はPPAD完全であり、一般に難解であると考えられている。 レグレト最小化(Regret Minimization)は、2プレイヤゼロサムゲームにおけるナッシュ平衡を近似するための効率的なフレームワークである。 しかし、一般的なサムゲームでは、そのようなアルゴリズムはプレイヤーが戦略を相関できる解の概念である粗相関平衡(CCE)に収束することが保証されている。 本研究では,メタラーニングを用いて,後悔の最小化による戦略の相関を最小化する。 このことは、後悔の最小化者がナッシュ均衡に近い戦略を見つけることを奨励する。 メタ学習型後悔最小化器は依然としてCCEに収束することが保証されているが、メタロスの観点からはナッシュ平衡までの距離に制限を与える。 汎用不完全な情報ゲームにおける我々のアプローチを評価する。 我々のアルゴリズムは、最先端の後悔最小化手法よりも、ナッシュ平衡の近似がはるかに優れている。

関連論文リスト

• Meta-Learning in Self-Play Regret Minimization [10.843705580746397]
  両プレイヤーゼロサムゲームにおけるナッシュ均衡を近似する多くのアルゴリズムにおいて,オンライン最適化に対する一般的なアプローチを提案する。 これに基づいてフレームワークを、最先端の平衡近似アルゴリズムの基盤である、より困難なセルフプレイ設定に拡張する。 私たちのメタ学習アルゴリズムは、他の最先端の後悔の最小化アルゴリズムよりもかなり優れています。
  論文  参考訳（メタデータ） (2025-04-26T13:27:24Z)
• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  非コンケーブゲームにおいて、抽出可能な$Phi$-equilibriaについて検討する。 Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2024-03-13T01:51:30Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
  ゼロサムマルコフゲームにおいて、2人のプレイヤーが望ましいナッシュ均衡、すなわち仲裁を誘導する報酬を摂動する方法を研究する。 低いレベルでは、与えられた報酬関数の下でのナッシュ均衡の解決が必要であり、それによって全体的な問題をエンドツーエンドで最適化することが難しくなる。 上層階の勾配フィードバックを提供するナッシュ平衡を微分するバックプロパゲーション方式を提案する。
  論文  参考訳（メタデータ） (2023-02-20T16:05:04Z)
• ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
  連続的なアクションセットを持つゲームの近似的ナッシュ均衡を求める問題について検討する。 本稿では,戦略プロファイルに対するエクスプロイラビリティの近似を最小化する2つの新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-01-20T23:55:30Z)
• Regret Minimization and Convergence to Equilibria in General-sum Markov Games [57.568118148036376]
  汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。 我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
  論文  参考訳（メタデータ） (2022-07-28T16:27:59Z)
• Safe Equilibrium [1.7132914341329848]
  標準的なゲーム理論解の概念であるナッシュ均衡は、すべてのプレイヤーが合理的に振る舞うことを仮定する。 我々は,特定の確率で合理的に行動する相手をモデル化する,セーフ均衡と呼ばれる新しい解の概念を提案する。 我々は、全ての戦略形式ゲームに安全な平衡が存在することを証明し、その計算がPPADハードであることを証明する。
  論文  参考訳（メタデータ） (2022-01-12T01:45:51Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。 我々はNash equilibria(NE)の解の概念に焦点をあてる。 このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
  論文  参考訳（メタデータ） (2021-11-07T21:15:35Z)
• Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
  有限$n$-playerの正規形式ゲームに対して,Nash平衡を近似的に計算するための一般的なメタ学習手法を提案する。 ゲーム毎のナッシュ均衡をスクラッチから近似あるいは学習する既存の解とは異なり、メタソルバはゲームユーティリティ行列からジョイント戦略プロファイルへの写像を直接構築する。
  論文  参考訳（メタデータ） (2021-08-17T07:06:46Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。 私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。 エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
  論文  参考訳（メタデータ） (2021-03-08T04:03:24Z)
• No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
  我々はFTRL(Follow-the-regularized-leader)のダイナミクスについて検討する。 厳密でないナッシュ均衡は、FTRLの下で安定して引き寄せることは不可能である。 この結果は,学習過程の結果を予測する上で重要な意味を持つ。
  論文  参考訳（メタデータ） (2020-10-19T13:49:06Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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