Fugu-MT 論文翻訳(概要): Learning in Zero-Sum Linear Quadratic Games with Last-Iterate Convergence

論文の概要: Learning in Zero-Sum Linear Quadratic Games with Last-Iterate Convergence

arxiv url: http://arxiv.org/abs/2309.04272v2
Date: Sun, 29 Oct 2023 21:02:23 GMT
ステータス: 処理完了
システム内更新日: 2023-10-31 20:11:46.709801
Title: Learning in Zero-Sum Linear Quadratic Games with Last-Iterate Convergence
Title（参考訳）: 最終Iterate Convergenceを用いたゼロサム線形二次ゲームにおける学習
Authors: Jiduan Wu and Anas Barakat and Ilyas Fatkhullin and Niao He
Abstract要約: Zero-sum Linear Quadratic (LQ) ゲームは最適制御の基本である。本研究では,より単純な入れ子ゼロ階法 (NPG) アルゴリズムを提案する。
参考スコア（独自算出の注目度）: 19.779044926914704
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Zero-sum Linear Quadratic (LQ) games are fundamental in optimal control and can be used (i)~as a dynamic game formulation for risk-sensitive or robust control and (ii)~as a benchmark setting for multi-agent reinforcement learning with two competing agents in continuous state-control spaces. In contrast to the well-studied single-agent linear quadratic regulator problem, zero-sum LQ games entail solving a challenging nonconvex-nonconcave min-max problem with an objective function that lacks coercivity. Recently, Zhang et al. showed that an~$\epsilon$-Nash equilibrium (NE) of finite horizon zero-sum LQ games can be learned via nested model-free Natural Policy Gradient (NPG) algorithms with poly$(1/\epsilon)$ sample complexity. In this work, we propose a simpler nested Zeroth-Order (ZO) algorithm improving sample complexity by several orders of magnitude and guaranteeing convergence of the last iterate. Our main results are two-fold: (i) in the deterministic setting, we establish the first global last-iterate linear convergence result for the nested algorithm that seeks NE of zero-sum LQ games; (ii) in the model-free setting, we establish a~$\widetilde{\mathcal{O}}(\epsilon^{-2})$ sample complexity using a single-point ZO estimator. For our last-iterate convergence results, our analysis leverages the Implicit Regularization (IR) property and a new gradient domination condition for the primal function. Our key improvements in the sample complexity rely on a more sample-efficient nested algorithm design and a finer control of the ZO natural gradient estimation error utilizing the structure endowed by the finite-horizon setting.
Abstract（参考訳）: Zero-sum Linear Quadratic (LQ)ゲームは最適制御の基本であり、使用できる (i)〜リスク感受性またはロバスト制御のための動的ゲーム定式化と (ii)~連続状態制御空間における2つの競合エージェントによるマルチエージェント強化学習のベンチマーク設定。良く研究された単エージェント線型二次規制問題とは対照的に、ゼロサムのLQゲームは、保磁力に欠ける目的関数を持つ挑戦的な非凸非凸 min-max 問題を解く。 Zhangらは最近、有限地平線ゼロサムLQゲームの~$\epsilon$-Nash平衡(NE)が、ポリ$(1/\epsilon)$サンプル複雑性を持つネストされたモデル自由自然ポリシー勾配(NPG)アルゴリズムによって学習可能であることを示した。本研究では,サンプルの複雑さを数桁削減し,最後の反復値の収束を保証する,より単純なネスト型ゼロ次(zo)アルゴリズムを提案する。主な結果は2つです。 (i)決定論的設定において、ゼロサムlqゲームのneを求めるネストアルゴリズムに対する最初の大域的ラストイテレート線形収束結果を確立する。 (ii) モデルフリー環境では, 単一点ZO推定器を用いて, a~$\widetilde{\mathcal{O}}(\epsilon^{-2})$サンプル複雑性を確立する。最終項目収束結果に対し,本分析ではImplicit Regularization(IR)特性と主関数に対する新しい勾配支配条件を利用する。サンプル複雑性における重要な改善は,よりサンプル効率のよいネストアルゴリズムの設計と,有限ホリゾン設定により付与された構造を利用したゾウ自然勾配推定誤差の微調整による。

関連論文リスト

Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文参考訳（メタデータ） (2024-10-03T15:04:01Z)
Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文参考訳（メタデータ） (2024-06-28T02:56:22Z)
Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
We show that Greedy-GQ algorithm converges fast-time error。我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
論文参考訳（メタデータ） (2022-09-06T15:04:57Z)
Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulator [43.13238243240668]
我々は、$epsilon$-optimal Solutionへのグローバル収束を確立するための新しい分析フレームワークを開発する。これは、LQRを大域的最適で解くための単一のサンプル2時間スケールACに対する最初の有限時間収束解析である。
論文参考訳（メタデータ） (2022-08-18T09:57:03Z)
Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文参考訳（メタデータ） (2022-07-18T12:03:26Z)
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文参考訳（メタデータ） (2020-10-31T21:35:42Z)
A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization [25.73397307080647]
本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。我々は,新しい数値スケール問題の有効性を実証する。
論文参考訳（メタデータ） (2020-10-23T05:24:05Z)
Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。本研究の結果は, 同時一次および二重側収束の形で表される。
論文参考訳（メタデータ） (2020-08-23T20:36:49Z)
Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文参考訳（メタデータ） (2020-06-24T07:40:31Z)
SGD with shuffling: optimal rates without component convexity and large epoch requirements [60.65928290219793]
我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
論文参考訳（メタデータ） (2020-06-12T05:00:44Z)
Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities [21.13934071954103]
本稿では,非インワンテキスト変数 Descent に対する決定論的アルゴリズムを提案する。 SGC仮定の下では,アルゴリズムの複雑さが既存のアルゴリズムの複雑さと一致していることが示される。結果はオラクル・テキストZO-GDMSAで示され、数値実験により理論的結果が裏付けられる。
論文参考訳（メタデータ） (2020-01-22T00:05:14Z)

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

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