論文の概要: Decentralized Policy Gradient for Nash Equilibria Learning of
General-sum Stochastic Games
- arxiv url: http://arxiv.org/abs/2210.07651v2
- Date: Tue, 18 Oct 2022 05:23:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-19 10:50:22.129808
- Title: Decentralized Policy Gradient for Nash Equilibria Learning of
General-sum Stochastic Games
- Title（参考訳）: 一般サム確率ゲームのnash平衡学習のための分散政策勾配
- Authors: Yan Chen and Tao Li
- Abstract要約: 遷移確率密度関数の未知な一般サムゲームのナッシュ平衡学習について検討する。
正確な擬似勾配を持つ場合、ナッシュ平衡と変分不等式の問題の等価性による2ループアルゴリズムを設計する。
- 参考スコア（独自算出の注目度）: 8.780797886160402
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study Nash equilibria learning of a general-sum stochastic game with an
unknown transition probability density function. Agents take actions at the
current environment state and their joint action influences the transition of
the environment state and their immediate rewards. Each agent only observes the
environment state and its own immediate reward and is unknown about the actions
or immediate rewards of others. We introduce the concepts of weighted
asymptotic Nash equilibrium with probability 1 and in probability. For the case
with exact pseudo gradients, we design a two-loop algorithm by the equivalence
of Nash equilibrium and variational inequality problems. In the outer loop, we
sequentially update a constructed strongly monotone variational inequality by
updating a proximal parameter while employing a single-call extra-gradient
algorithm in the inner loop for solving the constructed variational inequality.
We show that if the associated Minty variational inequality has a solution,
then the designed algorithm converges to the k^{1/2}-weighted asymptotic Nash
equilibrium. Further, for the case with unknown pseudo gradients, we propose a
decentralized algorithm, where the G(PO)MDP gradient estimator of the pseudo
gradient is provided by Monte-Carlo simulations. The convergence to the k^{1/4}
-weighted asymptotic Nash equilibrium in probability is achieved.
- Abstract（参考訳）: 遷移確率密度関数が未知な一般確率ゲームにおけるナッシュ平衡学習について検討する。
エージェントは現在の環境状態において行動し、その共同行動は環境状態の遷移と即時報酬に影響を与える。
各エージェントは、環境状態とその即時報酬のみを観察し、他人の行動や即時報酬について不明である。
重み付き漸近的ナッシュ均衡の概念を確率1および確率で導入する。
正確な擬似勾配を持つ場合、ナッシュ平衡と変分不等式の問題の等価性による2ループアルゴリズムを設計する。
外ループでは、構成された変分不等式を解決するために、内部ループに1つの呼び出し外勾配アルゴリズムを用いて、近似パラメータを更新し、構築された強い単調変分不等式を逐次更新する。
関連するMinty変分不等式が解を持つならば、設計アルゴリズムはk^{1/2}-重み付けされた漸近的ナッシュ平衡に収束する。
さらに、未知の擬似勾配の場合、擬似勾配のG(PO)MDP勾配推定器がモンテカルロシミュレーションによって提供される分散化アルゴリズムを提案する。
k^{1/4}-重み付き漸近ナッシュ平衡への確率の収束が達成される。
関連論文リスト
- PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
論文 参考訳（メタデータ） (2023-03-02T05:08:15Z) - Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
ゼロサムマルコフゲームにおいて、2人のプレイヤーが望ましいナッシュ均衡、すなわち仲裁を誘導する報酬を摂動する方法を研究する。
低いレベルでは、与えられた報酬関数の下でのナッシュ均衡の解決が必要であり、それによって全体的な問題をエンドツーエンドで最適化することが難しくなる。
上層階の勾配フィードバックを提供するナッシュ平衡を微分するバックプロパゲーション方式を提案する。
論文 参考訳（メタデータ） (2023-02-20T16:05:04Z) - Global Convergence of Over-parameterized Deep Equilibrium Models [52.65330015267245]
ディープ均衡モデル(Deep equilibrium model, DEQ)は、入射を伴う無限深度重み付きモデルの平衡点を通して暗黙的に定義される。
無限の計算の代わりに、ルートフィンディングで直接平衡点を解き、暗黙の微分で勾配を計算する。
本稿では,無限深度重み付きモデルの非漸近解析における技術的困難を克服する新しい確率的枠組みを提案する。
論文 参考訳（メタデータ） (2022-05-27T08:00:13Z) - Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games [16.09467599829253]
本研究では,2プレーヤゼロサムゲームにおけるナッシュ平衡を求める問題について検討する。
我々の主な貢献は、正規化パラメータの適切な選択の下で、勾配が元の非正規化問題のナッシュ平衡に傾くことを示すことである。
論文 参考訳（メタデータ） (2022-05-27T03:24:12Z) - First-Order Algorithms for Nonlinear Generalized Nash Equilibrium
Problems [88.58409977434269]
非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。
我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。
これらのアルゴリズムに対する漸近的理論的保証を提供する。
論文 参考訳（メタデータ） (2022-04-07T00:11:05Z) - On the Nash equilibrium of moment-matching GANs for stationary Gaussian
processes [2.25477613430341]
我々は、一貫したナッシュ均衡の存在は、判別器ファミリーの選択に大きく依存していることを示す。
さらに、一貫した平衡に向けた勾配降下法における局所安定性と大域収束について検討する。
論文 参考訳（メタデータ） (2022-03-14T14:30:23Z) - Provably convergent quasistatic dynamics for mean-field two-player
zero-sum games [10.39511271647025]
我々は、ある確率分布がワッセルシュタイン勾配の流れに従うような準静的ワッセルシュタイン勾配流れのダイナミクスを考察し、他方の確率分布は常に平衡状態にある。
確率分布の連続力学に着想を得て、内外反復を伴う擬静的なランゲヴィン勾配降下法を導出する。
論文 参考訳（メタデータ） (2022-02-15T20:19:42Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - Learning Nash Equilibria in Zero-Sum Stochastic Games via
Entropy-Regularized Policy Approximation [18.35524179586723]
ゼロサムゲームにおけるナッシュ均衡学習の計算コストを削減するためのポリシー近似の利用について検討する。
我々は,Nashポリシーを近似するために,エントロピー規則化されたソフトポリシーのシーケンスを利用する新しいQ-ラーニング型アルゴリズムを提案する。
一定の条件下では、正規化されたQ-関数を更新することにより、アルゴリズムはナッシュ平衡に収束する。
論文 参考訳（メタデータ） (2020-09-01T01:03:44Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳（メタデータ） (2020-04-09T17:54:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。