論文の概要: Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games

• arxiv url: http://arxiv.org/abs/2312.04905v1
• Date: Fri, 8 Dec 2023 08:39:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-11 15:34:17.271491
• Title: Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games
• Title（参考訳）: ゼロサム確率ゲームにおける関数近似を用いた2時間Q-Learning
• Authors: Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar, Asuman Ozdaglar, and Adam Wierman
• Abstract要約: そこで本稿では,関数近似を用いた2時間スムーズなQ$学習アルゴリズムを提案する。 2時間スケールの$Q$ラーニングでは、高速スケールは勾配降下に精力的に更新され、より遅いスケールは、前回と最新の高速スケールのコンベックスを組み合わせて更新される。 重要な新規性は、遅い時間スケールの進化を捉えるために有効なリャプノフ函数を構築することである。
• 参考スコア（独自算出の注目度）: 31.554420227087043
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider two-player zero-sum stochastic games and propose a two-timescale $Q$-learning algorithm with function approximation that is payoff-based, convergent, rational, and symmetric between the two players. In two-timescale $Q$-learning, the fast-timescale iterates are updated in spirit to the stochastic gradient descent and the slow-timescale iterates (which we use to compute the policies) are updated by taking a convex combination between its previous iterate and the latest fast-timescale iterate. Introducing the slow timescale as well as its update equation marks as our main algorithmic novelty. In the special case of linear function approximation, we establish, to the best of our knowledge, the first last-iterate finite-sample bound for payoff-based independent learning dynamics of these types. The result implies a polynomial sample complexity to find a Nash equilibrium in such stochastic games. To establish the results, we model our proposed algorithm as a two-timescale stochastic approximation and derive the finite-sample bound through a Lyapunov-based approach. The key novelty lies in constructing a valid Lyapunov function to capture the evolution of the slow-timescale iterates. Specifically, through a change of variable, we show that the update equation of the slow-timescale iterates resembles the classical smoothed best-response dynamics, where the regularized Nash gap serves as a valid Lyapunov function. This insight enables us to construct a valid Lyapunov function via a generalized variant of the Moreau envelope of the regularized Nash gap. The construction of our Lyapunov function might be of broad independent interest in studying the behavior of stochastic approximation algorithms.
• Abstract（参考訳）: 2人のプレイヤーのゼロサム確率ゲームについて検討し,2つのプレイヤー間のペイオフベース,収束,有理,対称な関数近似を用いた2時間スケールの$Q$学習アルゴリズムを提案する。 2度スケールの$q$-learningでは、高速スケールのイテレートは確率的勾配降下に精神的に更新され、遅いタイムスケールのイテレート(ポリシーの計算に使用する)は、以前のイテレートと最新の高速スケールイテレートのコンベックスの組み合わせによって更新される。 遅い時間スケールの導入と、その更新方程式は、我々の主要なアルゴリズムの新規性を示す。 線形関数近似の特別な場合において、我々が知る限りでは、これらのタイプのペイオフに基づく独立学習力学に対する最後の有限サンプル境界である。 この結果は、そのような確率ゲームにおいてナッシュ均衡を求める多項式サンプルの複雑さを意味する。 結果を確立するため,提案アルゴリズムを2時間確率近似としてモデル化し,リャプノフ法を用いて有限サンプルを導出する。 重要な新規性は、遅い時間スケールの反復の進化を捉えるために有効なリャプノフ函数を構築することである。 具体的には、変数の変化を通じて、遅い時間スケールのイテレートの更新方程式は、正規化ナッシュギャップが有効なリアプノフ関数として機能する古典的な滑らかな最応答ダイナミクスに似ていることを示す。 この洞察により、正規化されたナッシュギャップのモロー包絡の一般化された変種を通して、有効なリアプノフ関数を構築することができる。 Lyapunov関数の構築は、確率近似アルゴリズムの振る舞いを研究するために広く独立した関心を持つかもしれない。

関連論文リスト

• Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving $O(1/k)$ Finite-Sample Complexity [2.5382095320488665]
  本稿では,2つの結合非線形作用素の根を探すために,2時間スケールのモノトン近似の新しい変種を開発することを提案する。 私たちのキーとなるアイデアは、古典的なRuppert-Polyak平均化技術を活用して、それらのサンプルを通して演算子を動的に推定することです。 これらの平均ステップの見積値は、望まれる解を見つけるために、2時間スケールの近似更新で使用される。
  論文  参考訳（メタデータ） (2024-01-23T13:44:15Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。 双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-10T14:21:54Z)
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions [0.0]
  本稿では,ギブス分割関数を線形時間で推定する新しい量子アルゴリズムを提案する。 これは、vStefankovivc, Vempala, Vigodaの半周期的なほぼ直線時間で得られる最初のスピードアップである。
  論文  参考訳（メタデータ） (2022-07-18T14:41:48Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems [2.0305676256390934]
  連立勾配降下指数アルゴリズムの連続時間変動の有限時間特性を特徴付ける。 連続時間アルゴリズムの挙動に関する結果は、離散時間アルゴリズムの収束特性を高めるために用いられる。
  論文  参考訳（メタデータ） (2021-12-17T15:51:04Z)
• Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
  大規模2プレーヤワイドフォームゲームの計算平衡問題に対する反復的な一階法の適用について検討する。 正則化器を用いて一階法をインスタンス化することにより、相関平衡と元アンティー座標のチーム平衡を計算するための最初の加速一階法を開発する。
  論文  参考訳（メタデータ） (2021-05-27T06:10:24Z)
• Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance [1.52292571922932]
  非線形2時間スケール近似の収束と有限時間解析について検討する。 特に,本手法は期待値の収束を$mathcalO (1/k2/3)$で達成し,$k$は反復数であることを示す。
  論文  参考訳（メタデータ） (2020-11-03T17:43:39Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。 同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-09-29T18:48:21Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)

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

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