論文の概要: Learning Zero-Sum Linear Quadratic Games with Improved Sample Complexity
- arxiv url: http://arxiv.org/abs/2309.04272v1
- Date: Fri, 8 Sep 2023 11:47:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-11 13:31:18.585672
- Title: Learning Zero-Sum Linear Quadratic Games with Improved Sample Complexity
- Title(参考訳): サンプル複雑性を改善したゼロサム線形二次ゲーム学習
- Authors: Jiduan Wu and Anas Barakat and Ilyas Fatkhullin and Niao He
- Abstract要約: Zero-sum Linear Quadratic(LQ)ゲームは最適制御の基本であり、(i)リスク感受性やロバスト制御のダイナミックゲーム、(ii)マルチエージェント学習のベンチマークとして使用できる。
- 参考スコア(独自算出の注目度): 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, or (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. discovered an
implicit regularization property of natural policy gradient methods which is
crucial for safety-critical control systems since it preserves the robustness
of the controller during learning. Moreover, in the model-free setting where
the knowledge of model parameters is not available, Zhang et al. proposed the
first polynomial sample complexity algorithm to reach an
$\epsilon$-neighborhood of the Nash equilibrium while maintaining the desirable
implicit regularization property. In this work, we propose a simpler nested
Zeroth-Order (ZO) algorithm improving sample complexity by several orders of
magnitude. Our main result guarantees a
$\widetilde{\mathcal{O}}(\epsilon^{-3})$ sample complexity under the same
assumptions using a single-point ZO estimator. Furthermore, when the estimator
is replaced by a two-point estimator, our method enjoys a better
$\widetilde{\mathcal{O}}(\epsilon^{-2})$ sample complexity. Our key
improvements rely on a more sample-efficient nested algorithm design and finer
control of the ZO natural gradient estimation error.
- Abstract(参考訳): Zero-sum Linear Quadratic (LQ)ゲームは最適制御の基本であり、使用できる
(i)リスクに敏感な、または堅牢な制御のための動的ゲーム定式化
(ii)連続状態制御空間における2つの競合エージェントによるマルチエージェント強化学習のベンチマーク設定
良く研究された単エージェント線型二次規制問題とは対照的に、ゼロサムのLQゲームは、保磁力に欠ける目的関数を持つ挑戦的な非凸非凸 min-max 問題を解く。
近年、Zhangらは、学習中のコントローラの堅牢性を維持するため、安全クリティカルな制御システムにとって重要な、自然政策勾配法の暗黙の正規化特性を発見した。
さらに、モデルパラメータの知識が得られないモデルフリー環境では、Zhangらは、暗黙の正規化特性を維持しながら、Nash平衡の$\epsilon$-Nighborhoodに達する最初の多項式サンプル複雑性アルゴリズムを提案した。
本研究では,サンプルの複雑さを数桁改善するより単純なネスト型ゼロ次(zo)アルゴリズムを提案する。
我々の主な結果は、単一点ZO推定器を用いて同じ仮定の下で、$\widetilde{\mathcal{O}}(\epsilon^{-3})$サンプル複雑性を保証する。
さらに、推定器を2点推定器に置き換えると、より優れた$\widetilde{\mathcal{O}}(\epsilon^{-2})$サンプル複雑性が得られる。
我々の重要な改善点は、よりサンプリング効率の良いネストアルゴリズムの設計とZO自然勾配推定誤差のより細かい制御に依存している。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。