論文の概要: Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization

• arxiv url: http://arxiv.org/abs/2204.05466v1
• Date: Tue, 12 Apr 2022 01:34:02 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-13 14:29:21.368227
• Title: Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization
• Title（参考訳）: 潜在ゲームに対する独立自然政策勾配法:エントロピー正規化を伴う有限時間大域収束
• Authors: Shicong Cen, Fan Chen, Yuejie Chi
• Abstract要約: 本研究では,独立エントロピー規則化自然ポリシー勾配法(NPG)の有限時間収束について検討する。 提案手法は, 作用空間の大きさに依存しないサブ線形速度で量子応答平衡(QRE)に収束することを示す。
• 参考スコア（独自算出の注目度）: 28.401280095467015
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A major challenge in multi-agent systems is that the system complexity grows dramatically with the number of agents as well as the size of their action spaces, which is typical in real world scenarios such as autonomous vehicles, robotic teams, network routing, etc. It is hence in imminent need to design decentralized or independent algorithms where the update of each agent is only based on their local observations without the need of introducing complex communication/coordination mechanisms. In this work, we study the finite-time convergence of independent entropy-regularized natural policy gradient (NPG) methods for potential games, where the difference in an agent's utility function due to unilateral deviation matches exactly that of a common potential function. The proposed entropy-regularized NPG method enables each agent to deploy symmetric, decentralized, and multiplicative updates according to its own payoff. We show that the proposed method converges to the quantal response equilibrium (QRE) -- the equilibrium to the entropy-regularized game -- at a sublinear rate, which is independent of the size of the action space and grows at most sublinearly with the number of agents. Appealingly, the convergence rate further becomes independent with the number of agents for the important special case of identical-interest games, leading to the first method that converges at a dimension-free rate. Our approach can be used as a smoothing technique to find an approximate Nash equilibrium (NE) of the unregularized problem without assuming that stationary policies are isolated.
• Abstract（参考訳）: マルチエージェントシステムにおける大きな課題は、エージェントの数とアクションスペースのサイズによって、システムの複雑さが劇的に増加することだ。 したがって、各エージェントの更新は、複雑な通信/コーディネート機構を導入することなく、そのローカルな観測に基づいてのみ行われる、分散化または独立したアルゴリズムをすぐに設計する必要がある。 本研究では,一側偏差によるエージェントの効用関数の差が共通のポテンシャル関数と正確に一致するような,独立エントロピー規則化自然ポリシー勾配法(NPG)のポテンシャルゲームに対する有限時間収束について検討する。 提案したエントロピー正規化NPG法により,各エージェントは,それぞれのペイオフに応じて対称的,分散的,乗算的更新をデプロイできる。 提案手法は, 量子応答平衡(QRE) – エントロピー正則化ゲームに対する平衡 – に収束し, 作用空間のサイズによらず, エージェント数にほぼ準線形に成長することを示す。 興味深いことに、収束率はさらに、同じ興味を持つゲームの重要な特別な場合のエージェントの数と独立になり、次元自由率で収束する最初の方法につながる。 本手法は,定常政策が孤立していると仮定することなく,非正規化問題の近似nash平衡(ne)を求めるための平滑化手法として利用できる。

関連論文リスト

• A Single Online Agent Can Efficiently Learn Mean Field Games [16.00164239349632]
  平均場ゲーム (MFGs) は大規模人口システムの振る舞いをモデル化するための有望なフレームワークである。 本稿では,オンラインサンプルを用いてMFNEを学習できるオンライン単エージェントモデルフリー学習方式を提案する。
  論文  参考訳（メタデータ） (2024-05-05T16:38:04Z)
• Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularization [12.612009339150504]
  本研究は,マルチエージェント強化学習におけるエントロピー規則化独立自然政策勾配(NPG)アルゴリズムに焦点を当てる。 十分なエントロピー正則化の下では、この系の力学は線形速度で量子応答平衡(QRE)に収束することを示す。
  論文  参考訳（メタデータ） (2024-05-04T22:48:53Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。 本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。 マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
  論文  参考訳（メタデータ） (2023-05-01T06:46:22Z)
• Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games [63.60117916422867]
  本稿では,対戦型マルチエージェントRLの最も基本的な設定,すなわち2プレーヤゼロサムマルコフゲームに焦点を当てる。 両エージェントから対称更新を施した単一ループポリシー最適化手法を提案し,この手法はエントロピー規則化楽観的乗算重み更新法(OMWU)によって更新される。 我々の収束結果は、最もよく知られた複雑性を改善し、競合するマルコフゲームにおけるポリシー最適化をよりよく理解する。
  論文  参考訳（メタデータ） (2022-10-03T16:05:43Z)
• Low-rank Optimal Transport: Approximation, Statistics and Debiasing [51.50788603386766]
  フロゼットボン2021ローランで提唱された低ランク最適輸送(LOT)アプローチ LOTは興味のある性質と比較した場合、エントロピー正則化の正当な候補と見なされる。 本稿では,これらの領域のそれぞれを対象とし,計算OTにおける低ランクアプローチの影響を補強する。
  論文  参考訳（メタデータ） (2022-05-24T20:51:37Z)
• Multi-Agent MDP Homomorphic Networks [100.74260120972863]
  協調型マルチエージェントシステムでは、エージェントの異なる構成とそれらの局所的な観察の間に複雑な対称性が生じる。 単エージェント強化学習における既存の対称性の研究は、完全に集中した環境にのみ一般化できる。 本稿では,ローカル情報のみを用いた分散実行が可能なネットワークのクラスであるマルチエージェントMDPホモモルフィックネットワークを提案する。
  論文  参考訳（メタデータ） (2021-10-09T07:46:25Z)
• Dimension-Free Rates for Natural Policy Gradient in Multi-Agent Reinforcement Learning [22.310861786709538]
  協調型マルチエージェント強化学習のためのスケーラブルなアルゴリズムを提案する。 このアルゴリズムは,次元自由な統計量と計算量とで,グローバルな最適ポリシーに収束することを示す。
  論文  参考訳（メタデータ） (2021-09-23T23:38:15Z)
• Decentralized Local Stochastic Extra-Gradient for Variational Inequalities [125.62877849447729]
  我々は、不均一(非IID)で多くのデバイスに分散する問題データを持つ領域上での分散変分不等式(VIs)を考察する。 我々は、完全に分散化された計算の設定を網羅する計算ネットワークについて、非常に一般的な仮定を行う。 理論的には, モノトン, モノトンおよび非モノトンセッティングにおける収束速度を理論的に解析する。
  論文  参考訳（メタデータ） (2021-06-15T17:45:51Z)
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization [40.21627891283402]
  本稿では,競争ゲームの均衡の計算問題について考察する。 エントロピー正則化のアルゴリズム的役割に動機付けられ、我々は証明可能な効率の良い指数関数法を開発した。
  論文  参考訳（メタデータ） (2021-05-31T17:51:15Z)
• Dealing with Non-Stationarity in Multi-Agent Reinforcement Learning via Trust Region Decomposition [52.06086375833474]
  非定常性は多エージェント強化学習における厄介な問題である。 ポリシーシーケンスの定常性を明示的にモデル化するための$delta$-stationarity測定を導入する。 共同政策の分岐を推定するために,メッセージパッシングに基づく信頼領域分解ネットワークを提案する。
  論文  参考訳（メタデータ） (2021-02-21T14:46:50Z)
• Calibration of Shared Equilibria in General Sum Partially Observable Markov Games [15.572157454411533]
  我々は、異なるタイプのエージェントが単一のポリシーネットワークを共有する、一般的な可観測マルコフゲームを考える。 本稿は,そのようなエージェントが到達した平衡を形式的に理解すること,および,そのような平衡の創発的な現象を現実のターゲットに合わせることを目的としている。
  論文  参考訳（メタデータ） (2020-06-23T15:14:20Z)

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

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