論文の概要: Provable Policy Gradient Methods for Average-Reward Markov Potential Games

• arxiv url: http://arxiv.org/abs/2403.05738v1
• Date: Sat, 9 Mar 2024 00:20:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-13 12:41:53.053783
• Title: Provable Policy Gradient Methods for Average-Reward Markov Potential Games
• Title（参考訳）: 平均逆マルコフポテンシャルゲームのための確率的ポリシー勾配法
• Authors: Min Cheng, Ruida Zhou, P. R. Kumar and Chao Tian
• Abstract要約: 無限水平平均報酬基準の下でマルコフポテンシャルゲームを研究する。 我々は、独立政策勾配と独立自然政策勾配に基づくアルゴリズムが、平均報酬基準に対するナッシュ均衡にグローバルに収束することを証明した。
• 参考スコア（独自算出の注目度）: 15.136494705127564
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study Markov potential games under the infinite horizon average reward criterion. Most previous studies have been for discounted rewards. We prove that both algorithms based on independent policy gradient and independent natural policy gradient converge globally to a Nash equilibrium for the average reward criterion. To set the stage for gradient-based methods, we first establish that the average reward is a smooth function of policies and provide sensitivity bounds for the differential value functions, under certain conditions on ergodicity and the second largest eigenvalue of the underlying Markov decision process (MDP). We prove that three algorithms, policy gradient, proximal-Q, and natural policy gradient (NPG), converge to an $\epsilon$-Nash equilibrium with time complexity $O(\frac{1}{\epsilon^2})$, given a gradient/differential Q function oracle. When policy gradients have to be estimated, we propose an algorithm with $\tilde{O}(\frac{1}{\min_{s,a}\pi(a|s)\delta})$ sample complexity to achieve $\delta$ approximation error w.r.t~the $\ell_2$ norm. Equipped with the estimator, we derive the first sample complexity analysis for a policy gradient ascent algorithm, featuring a sample complexity of $\tilde{O}(1/\epsilon^5)$. Simulation studies are presented.
• Abstract（参考訳）: 無限水平平均報酬基準の下でマルコフポテンシャルゲームを研究する。 これまでの研究はほとんどが割引報酬だった。 独立政策勾配と独立自然政策勾配に基づく2つのアルゴリズムが、平均報酬基準のnash平衡にグローバルに収束することを証明する。 勾配に基づく手法の段階を設定するために,まず,平均報酬は方針の円滑な関数であり,エルゴード性およびマルコフ決定過程(mdp)の第2の固有値の条件下で,微分値関数に対する感度境界を与える。 3つのアルゴリズム、ポリシーグラデーション、近位q、自然政策グラデーション(npg)が、勾配/微分q関数oracleの与えられた時間複雑性$o(\frac{1}{\epsilon^2})$を持つ$\epsilon$-nash平衡に収束することを証明する。 政策勾配を見積もる必要があるとき、$\tilde{O}(\frac{1}{\min_{s,a}\pi(a|s)\delta})$サンプル複雑さを$\delta$近似誤差w.r.t~$\ell_2$ノルムを達成するアルゴリズムを提案する。 推定器を組み込んだポリシ勾配上昇アルゴリズムの最初のサンプル複雑性解析を導出し,サンプル複雑性を$\tilde{O}(1/\epsilon^5)$とする。 シミュレーション研究を行う。

関連論文リスト

• Convergence of a model-free entropy-regularized inverse reinforcement learning algorithm [6.481009996429766]
  逆強化学習(IRL)は、専門家が最適である報酬を回復することを目的としている。 本研究では,エントロピー規則化IRL問題を解くためのモデルフリーアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-25T14:54:42Z)
• Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes [41.61653528766776]
  本稿では, 自然政策勾配を求めるために, 加速勾配降下過程を利用する自然促進政策勾配(PGAN)アルゴリズムを提案する。 繰り返しは$mathcalO(epsilon-2)$サンプル複雑性と$mathcalO(epsilon-1)$複雑さを達成する。 Hessian-free および IS-free アルゴリズムのクラスでは、ANPG は $mathcalO(epsilon-frac12)$ の係数で最もよく知られたサンプルの複雑さを破り、それらの状態と同時に一致する。
  論文  参考訳（メタデータ） (2023-10-18T03:00:15Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。 我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。 我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
  論文  参考訳（メタデータ） (2023-03-17T17:53:28Z)
• Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies [19.779044926914704]
  我々は、フィッシャー非退化パラメタライズドポリシーの一般クラスに対する改善されたグローバルコンバージェンス保証を開発する。 本研究では,Implicit Gradient Transport (N-PG-IGT) を用いた正規化政策勾配法を提案し,この手法のサンプル複雑性を$tildemathcalO(varepsilon-2.5)$とする。 我々はこの複雑さをさらに改善し、ヘッセン支援再帰政策勾配を考慮し、$tilde MathcalmathcalO (varepsilon-2)$に改善する。
  論文  参考訳（メタデータ） (2023-02-03T13:50:23Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexity [40.2022466644885]
  有限状態と作用空間を持つ割引・無限水平型MDPを解くホモトピーポリシーミラー降下法(HPMD)法。 政策勾配法に関する文献では, 新たな3つの特性が報告されている。
  論文  参考訳（メタデータ） (2022-01-24T04:54:58Z)
• A New Framework for Variance-Reduced Hamiltonian Monte Carlo [88.84622104944503]
  分散還元型ハミルトン・モンテカルロ法 (HMC) の新たなフレームワークを提案し,$L$-smooth および $m$-strongly log-concave 分布からサンプリングする。 本研究では,SAGA法やSVRG法をベースとした非バイアス勾配推定器を用いて,バッチサイズを小さくすることで,高い勾配効率が得られることを示す。 総合的および実世界のベンチマークデータによる実験結果から、我々の新しいフレームワークは、完全な勾配と勾配HMCアプローチを著しく上回っていることが示された。
  論文  参考訳（メタデータ） (2021-02-09T02:44:24Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)
• On the Global Convergence Rates of Softmax Policy Gradient Methods [45.1868906130788]
  真の勾配では、ソフトマックスパラメトリゼーションによるポリシー勾配が$O(e-c cdot t)$レートで収束することを示す。 第2に,エントロピー規則化政策勾配を解析し,より高速な線形収束率を示す。 第3に、エントロピー正則化が真の勾配であっても、政策最適化をどのように改善するかを説明する。
  論文  参考訳（メタデータ） (2020-05-13T16:01:39Z)
• Reward-Free Exploration for Reinforcement Learning [82.3300753751066]
  探索の課題を分離する「逆フリーなRL」フレームワークを提案する。 我々は,$tildemathcalO(S2Amathrmpoly(H)/epsilon2)$の探索を効率的に行うアルゴリズムを提案する。 また、ほぼ一致する$Omega(S2AH2/epsilon2)$ lower boundを与え、この設定でアルゴリズムのほぼ最適性を示す。
  論文  参考訳（メタデータ） (2020-02-07T14:03:38Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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