論文の概要: Learning to Compute Approximate Nash Equilibrium for Normal-form Games

• arxiv url: http://arxiv.org/abs/2108.07472v1
• Date: Tue, 17 Aug 2021 07:06:46 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-18 13:04:42.615713
• Title: Learning to Compute Approximate Nash Equilibrium for Normal-form Games
• Title（参考訳）: 正規形ゲームに対する近似ナッシュ平衡計算の学習
• Authors: Zhijian Duan, Yali Du, Jun Wang, Xiaotie Deng
• Abstract要約: 有限$n$-playerの正規形式ゲームに対して,Nash平衡を近似的に計算するための一般的なメタ学習手法を提案する。 ゲーム毎のナッシュ均衡をスクラッチから近似あるいは学習する既存の解とは異なり、メタソルバはゲームユーティリティ行列からジョイント戦略プロファイルへの写像を直接構築する。
• 参考スコア（独自算出の注目度）: 15.321036952379488
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose a general meta learning approach to computing approximate Nash equilibrium for finite $n$-player normal-form games. Unlike existing solutions that approximate or learn a Nash equilibrium from scratch for each of the games, our meta solver directly constructs a mapping from a game utility matrix to a joint strategy profile. The mapping is parameterized and learned in a self-supervised fashion by a proposed Nash equilibrium approximation metric without ground truth data informing any Nash equilibrium. As such, it can immediately predict the joint strategy profile that approximates a Nash equilibrium for any unseen new game under the same game distribution. Moreover, the meta-solver can be further fine-tuned and adaptive to a new game if iteration updates are allowed. We theoretically prove that our meta-solver is not affected by the non-smoothness of exact Nash equilibrium solutions, and derive a sample complexity bound to demonstrate its generalization ability across normal-form games. Experimental results demonstrate its substantial approximation power against other strong baselines in both adaptive and non-adaptive cases.
• Abstract（参考訳）: 本稿では,有限のn$-player正規形ゲームに対する近似ナッシュ均衡を計算するための一般的なメタラーニング手法を提案する。 ゲーム毎にnash平衡をスクラッチから近似または学習する既存の解とは異なり、我々のメタソルバはゲームユーティリティマトリックスからジョイント戦略プロファイルへのマッピングを直接構築する。 マッピングはパラメータ化され、Nash平衡を知らせる基底真理データなしで提案されたNash平衡近似計量によって自己教師型で学習される。 このようにして、同一のゲーム分布下で、未知の新しいゲームに対するナッシュ均衡を近似するジョイント戦略プロファイルを即座に予測することができる。 さらに、反復更新が可能であれば、メタソルバはさらに微調整され、新しいゲームに適応することができる。 理論上,我々のメタソルバはnash平衡解の非スムース性に影響されないことを証明し,正規形式ゲーム間の一般化能力を示すためのサンプル複雑性を導出する。 実験結果は,適応例と非適応例の両方において,他の強基線に対して相当な近似力を示す。

関連論文リスト

• Nash Equilibria via Stochastic Eigendecomposition [4.190518009892366]
  ナッシュ均衡は、パラメータへの純粋呼び出し、値分解とパワーの反復的変動によって近似できることを示す。 一般のゲームにおけるすべての平衡を、容易に利用できる線形代数ツールのみを用いて解くことを証明する擬符号と実験を提供する。
  論文  参考訳（メタデータ） (2024-11-04T17:32:21Z)
• Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
  ゼロサムマルコフゲームにおいて、2人のプレイヤーが望ましいナッシュ均衡、すなわち仲裁を誘導する報酬を摂動する方法を研究する。 低いレベルでは、与えられた報酬関数の下でのナッシュ均衡の解決が必要であり、それによって全体的な問題をエンドツーエンドで最適化することが難しくなる。 上層階の勾配フィードバックを提供するナッシュ平衡を微分するバックプロパゲーション方式を提案する。
  論文  参考訳（メタデータ） (2023-02-20T16:05:04Z)
• Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
  Nayyar et al. (2013) は、プレイヤーがプレイ中にポリシーを公に発表することで、不完全な情報を共通のペイオフゲームから抽象化できることを示した。 この研究は、ある正規化された平衡が上記の非対応問題を持たないことを示している。 これらの正規化された平衡はナッシュ平衡に任意に近づくことができるので、この結果は2つのプレイヤーゼロサムゲームを解くための新たな視点への扉を開く。
  論文  参考訳（メタデータ） (2023-01-22T16:54:06Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。 ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。 本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
  論文  参考訳（メタデータ） (2022-11-29T05:16:41Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• Safe Equilibrium [1.7132914341329848]
  標準的なゲーム理論解の概念であるナッシュ均衡は、すべてのプレイヤーが合理的に振る舞うことを仮定する。 我々は,特定の確率で合理的に行動する相手をモデル化する,セーフ均衡と呼ばれる新しい解の概念を提案する。 我々は、全ての戦略形式ゲームに安全な平衡が存在することを証明し、その計算がPPADハードであることを証明する。
  論文  参考訳（メタデータ） (2022-01-12T01:45:51Z)
• Multiplayer Performative Prediction: Learning in Decision-Dependent Games [18.386569111954213]
  本稿では,マルチプレイヤー演奏予測のための新たなゲーム理論の枠組みを定式化する。 我々は、(i)パフォーマンス的に安定な平衡と(ii)ゲームのナッシュ平衡という、2つの異なる解の概念に焦点を当てる。 軽微な仮定の下では、様々なアルゴリズムにより、性能的に安定な平衡を効率的に見つけることができることを示す。
  論文  参考訳（メタデータ） (2022-01-10T15:31:10Z)
• 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)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。 本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
  論文  参考訳（メタデータ） (2021-02-23T05:11:07Z)

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

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