論文の概要: On the convergence of policy gradient methods to Nash equilibria in general stochastic games

• arxiv url: http://arxiv.org/abs/2210.08857v1
• Date: Mon, 17 Oct 2022 08:51:59 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-18 22:08:48.629668
• Title: On the convergence of policy gradient methods to Nash equilibria in general stochastic games
• Title（参考訳）: 一般確率ゲームにおける政策勾配法のナッシュ平衡への収束について
• Authors: Angeliki Giannou and Kyriakos Lotidis and Panayotis Mertikopoulos and Emmanouil-Vasileios Vlatakis-Gkaragkounis
• Abstract要約: ナッシュ均衡政策に関する政策勾配法の長期的挙動について検討する。 本稿では,REINFORCEアルゴリズムによって得られる勾配推定値を持つ政策勾配軌跡を$mathcalO (1/sqrtn)$ distance-squared convergence rate とする。
• 参考スコア（独自算出の注目度）: 33.786186304912
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning in stochastic games is a notoriously difficult problem because, in addition to each other's strategic decisions, the players must also contend with the fact that the game itself evolves over time, possibly in a very complicated manner. Because of this, the convergence properties of popular learning algorithms - like policy gradient and its variants - are poorly understood, except in specific classes of games (such as potential or two-player, zero-sum games). In view of this, we examine the long-run behavior of policy gradient methods with respect to Nash equilibrium policies that are second-order stationary (SOS) in a sense similar to the type of sufficiency conditions used in optimization. Our first result is that SOS policies are locally attracting with high probability, and we show that policy gradient trajectories with gradient estimates provided by the REINFORCE algorithm achieve an $\mathcal{O}(1/\sqrt{n})$ distance-squared convergence rate if the method's step-size is chosen appropriately. Subsequently, specializing to the class of deterministic Nash policies, we show that this rate can be improved dramatically and, in fact, policy gradient methods converge within a finite number of iterations in that case.
• Abstract（参考訳）: 確率ゲームで学ぶことは、互いの戦略的な決定に加えて、プレイヤーはゲーム自体が時間とともに進化するという事実と、おそらく非常に複雑な方法で競合するため、非常に難しい問題である。 このため、一般的な学習アルゴリズム(ポリシー勾配やその変種など)の収束特性は、特定のゲームのクラス(ポテンシャルゲームや2プレイヤーゲーム、ゼロサムゲームなど)を除いては理解されていない。 そこで本研究では,2次定常状態(SOS)であるナッシュ均衡政策に対する政策勾配法の長期的挙動を,最適化に使用される充足条件のタイプに類似した意味で検討する。 最初の結果は、SOSのポリシーは高い確率で局所的に引き寄せられていることを示し、この方法のステップサイズが適切に選択された場合、REINFORCEアルゴリズムによって得られる勾配推定によるポリシー勾配軌跡が$\mathcal{O}(1/\sqrt{n})$距離2乗収束率を達成することを示す。 その後、決定論的nashポリシーのクラスに特化することで、このレートが劇的に改善できることを示し、実際、ポリシー勾配法は、その場合の有限個のイテレーション内に収束する。

関連論文リスト

• A Policy-Gradient Approach to Solving Imperfect-Information Games with Iterate Convergence [21.195897792629548]
  政策勾配法は, シングルエージェント強化学習ツールボックスの基盤となっている。 政策勾配法が自己プレイにおける正規化ナッシュ均衡に証明可能なベストイテレート収束をもたらすことを初めて示す。
  論文  参考訳（メタデータ） (2024-08-01T17:54:01Z)
• Learning Optimal Deterministic Policies with Stochastic Policy Gradients [62.81324245896716]
  政策勾配法(PG法)は連続強化学習(RL法)問題に対処する手法として成功している。 一般的には、収束(ハイパー)政治は、決定論的バージョンをデプロイするためにのみ学習される。 本稿では,サンプルの複雑性とデプロイされた決定論的ポリシのパフォーマンスのトレードオフを最適化するために,学習に使用する探索レベルの調整方法を示す。
  論文  参考訳（メタデータ） (2024-05-03T16:45:15Z)
• The equivalence of dynamic and strategic stability under regularized learning in games [33.74394172275373]
  有限ゲームにおける正規化学習の長時間動作について検討する。 戦略的安定性と動的安定性の等価性を得る。 エントロピー正則化に基づく手法は幾何速度で収束することを示す。
  論文  参考訳（メタデータ） (2023-11-04T14:07:33Z)
• Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs [107.28031292946774]
  無限水平割引マルコフ決定過程(拘束型MDP)の最適ポリシの計算問題について検討する。 我々は, 最適制約付きポリシーに反復的に対応し, 非漸近収束性を持つ2つの単一スケールポリシーに基づく原始双対アルゴリズムを開発した。 我々の知る限り、この研究は制約付きMDPにおける単一時間スケールアルゴリズムの非漸近的な最後の収束結果となる。
  論文  参考訳（メタデータ） (2023-06-20T17:27:31Z)
• Policy Gradient for Rectangular Robust Markov Decision Processes [62.397882389472564]
  我々は,長方形ロバストなマルコフ決定過程(MDP)を効率的に解く政策ベース手法であるロバストなポリシー勾配(RPG)を導入する。 結果のRPGは、非ロバストな等価値と同じ時間のデータから推定することができる。
  論文  参考訳（メタデータ） (2023-01-31T12:40:50Z)
• On the Convergence Rates of Policy Gradient Methods [9.74841674275568]
  有限状態部分空間における幾何的に割引された支配問題を考える。 試料中の直交勾配のパラリゼーションにより、勾配の一般的な複雑さを解析できることが示される。
  論文  参考訳（メタデータ） (2022-01-19T07:03:37Z)
• Convergence and Optimality of Policy Gradient Methods in Weakly Smooth Settings [17.437408088239142]
  我々は不透明な条件に頼らずに政策勾配法の明確な収束率を確立する。 また, ニアリニアMDPのエルゴディディディティに対する十分条件を特徴付ける。 収束政策の最適性に関する条件と分析を提供する。
  論文  参考訳（メタデータ） (2021-10-30T06:31:01Z)
• Independent Policy Gradient Methods for Competitive Reinforcement Learning [62.91197073795261]
  2つのエージェントによる競争強化学習環境における独立学習アルゴリズムに対するグローバル・非漸近収束保証を得る。 本研究は,両選手がタンデムで政策勾配法を実行すると,学習率を2回ルールに従えば,その政策はゲームの最小均衡に収束することを示す。
  論文  参考訳（メタデータ） (2021-01-11T23:20:42Z)
• Policy Gradient for Continuing Tasks in Non-stationary Markov Decision Processes [112.38662246621969]
  強化学習は、マルコフ決定プロセスにおいて期待される累積報酬を最大化するポリシーを見つけることの問題を考える。 我々は、ポリシーを更新するために上昇方向として使用する値関数の偏りのないナビゲーション勾配を計算する。 ポリシー勾配型アルゴリズムの大きな欠点は、定常性の仮定が課せられない限り、それらがエピソジックなタスクに限定されていることである。
  論文  参考訳（メタデータ） (2020-10-16T15:15:42Z)
• Provable Fictitious Play for General Mean-Field Games [111.44976345867005]
  静止平均場ゲームのための強化学習アルゴリズムを提案する。 目標は、ナッシュ均衡を構成する平均場状態と定常政策のペアを学ぶことである。
  論文  参考訳（メタデータ） (2020-10-08T18:46:48Z)

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

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