論文の概要: Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games

• arxiv url: http://arxiv.org/abs/2310.09727v2
• Date: Fri, 27 Oct 2023 16:28:19 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-30 16:40:34.779723
• Title: Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games
• Title（参考訳）: マルコフポテンシャルゲームにおける独立自然政策勾配の高速収束
• Authors: Youbang Sun, Tao Liu, Ruida Zhou, P. R. Kumar, Shahin Shahrampour
• Abstract要約: 本研究はマルコフポテンシャルゲームにおけるマルチエージェント強化学習問題に対する独立自然ポリシー勾配(NPG)アルゴリズムについて研究する。 技術的に微妙な仮定では、正確なポリシーを提供するオラクルを持つ独立したNPG法は、$mathcalO(1/epsilon)$イテレーション内で$epsilon$-Nash Equilibrium (NE)に達することが示されている。
• 参考スコア（独自算出の注目度）: 18.11805544026393
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work studies an independent natural policy gradient (NPG) algorithm for the multi-agent reinforcement learning problem in Markov potential games. It is shown that, under mild technical assumptions and the introduction of the \textit{suboptimality gap}, the independent NPG method with an oracle providing exact policy evaluation asymptotically reaches an $\epsilon$-Nash Equilibrium (NE) within $\mathcal{O}(1/\epsilon)$ iterations. This improves upon the previous best result of $\mathcal{O}(1/\epsilon^2)$ iterations and is of the same order, $\mathcal{O}(1/\epsilon)$, that is achievable for the single-agent case. Empirical results for a synthetic potential game and a congestion game are presented to verify the theoretical bounds.
• Abstract（参考訳）: 本研究はマルコフポテンシャルゲームにおけるマルチエージェント強化学習問題に対する独立自然ポリシー勾配(NPG)アルゴリズムの研究である。 微妙な技術的仮定と『textit{suboptimality gap} 』の導入により、厳密な政策評価を提供するオラクルを持つ独立NPG法は、$\mathcal{O}(1/\epsilon)$反復において$\epsilon$-Nash Equilibrium (NE) に達することが示されている。 これは$\mathcal{O}(1/\epsilon^2)$イテレーションの前の最良の結果を改善し、同じ順序である$\mathcal{O}(1/\epsilon)$で、これは単項の場合で達成可能である。 合成ポテンシャルゲームと渋滞ゲームに対する実験結果を示し、理論的境界を検証した。

関連論文リスト

• Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
  そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。 我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
  論文  参考訳（メタデータ） (2024-06-04T15:23:29Z)
• Sample-Efficient Constrained Reinforcement Learning with General Parameterization [35.22742439337603]
  エージェントの目標は、無限の地平線上で期待される割引報酬の和を最大化することである。 我々は,世界最適性ギャップを$epsilon$で保証し,制約違反を$epsilon$で保証するPrimal-Dual Accelerated Natural Policy Gradient (PD-ANPG)アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-05-17T08:39:05Z)
• Provable Policy Gradient Methods for Average-Reward Markov Potential Games [15.136494705127564]
  無限水平平均報酬基準の下でマルコフポテンシャルゲームを研究する。 我々は、独立政策勾配と独立自然政策勾配に基づくアルゴリズムが、平均報酬基準に対するナッシュ均衡にグローバルに収束することを証明した。
  論文  参考訳（メタデータ） (2024-03-09T00:20:33Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。 本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
  論文  参考訳（メタデータ） (2023-10-21T18:38:13Z)
• Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
  モデルフリーのステージベースQ-ラーニングアルゴリズムはモデルベースアルゴリズムと同じ$H$依存の最適性を享受できることを示す。 本アルゴリズムは,楽観的値関数と悲観的値関数のペアとして参照値関数を更新するキーとなる新しい設計を特徴とする。
  論文  参考訳（メタデータ） (2023-08-17T08:34:58Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)
• High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
  本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。 我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。 我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
  論文  参考訳（メタデータ） (2022-04-06T13:50:33Z)
• Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximation [15.319335698574932]
  The first efficient convergence result with primal-dual actor-critic with a convergence of $mathcalOleft ascent(Nright)Nright)$ under Polyian sample。 Open GymAI連続制御タスクの結果。
  論文  参考訳（メタデータ） (2022-02-28T15:16:23Z)
• Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence [30.084357461497042]
  状態空間と/またはプレイヤーの数が非常に大きいMPGのナッシュ均衡を学習する。 我々は,すべてのプレイヤーがタンデムで実行する独立ポリシー勾配アルゴリズムを提案する。 我々は、ゼロサムマルコフゲームとマルコフ協調ゲームの両方の収束性を楽しむ独立ポリシー勾配アルゴリズムのクラスを、ゲームの種類によらないプレイヤーと同定する。
  論文  参考訳（メタデータ） (2022-02-08T20:09:47Z)
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play [49.88233710867315]
  マルチエージェントマルコフゲームのためのモデルベースセルフプレイアルゴリズムのシャープな解析を行う。 我々は,2プレイヤーゼロサムマルコフゲームのための最適化ナッシュ値イテレーション(Nash-VI)を設計する。 我々はさらに、ゼロサムマルコフゲームに対する証明可能な効率的なタスク認識アルゴリズムの設計に我々の分析を適用した。
  論文  参考訳（メタデータ） (2020-10-04T15:27:39Z)

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

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