論文の概要: A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2109.14756v4
- Date: Fri, 23 Aug 2024 22:16:10 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-28 20:36:52.059990
- Title: A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning
- Title（参考訳）: 制御・強化学習における2段階確率最適化フレームワーク
- Authors: Sihan Zeng, Thinh T. Doan, Justin Romberg,
- Abstract要約: 最適化問題の解法として,新しい2段階勾配法を提案する。
最初の貢献は、提案した2時間スケール勾配アルゴリズムの有限時間複雑性を特徴づけることである。
我々は、強化学習における勾配に基づく政策評価アルゴリズムに適用する。
- 参考スコア（独自算出の注目度）: 13.908826484332282
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a new two-time-scale stochastic gradient method for solving optimization problems, where the gradients are computed with the aid of an auxiliary variable under samples generated by time-varying MDPs controlled by the underlying optimization variable. These time-varying samples make gradient directions in our update biased and dependent, which can potentially lead to the divergence of the iterates. In our two-time-scale approach, one scale is to estimate the true gradient from these samples, which is then used to update the estimate of the optimal solution. While these two iterates are implemented simultaneously, the former is updated "faster" than the latter. Our first contribution is to characterize the finite-time complexity of the proposed two-time-scale stochastic gradient method. In particular, we provide explicit formulas for the convergence rates of this method under different structural assumptions, namely, strong convexity, PL condition, and general non-convexity. We apply our framework to various policy optimization problems. First, we look at the infinite-horizon average-reward MDP with finite state and action spaces and derive a convergence rate of $O(k^{-2/5})$ for the online actor-critic algorithm under function approximation, which recovers the best known rate derived specifically for this problem. Second, we study the linear-quadratic regulator and show that an online actor-critic method converges with rate $O(k^{-2/3})$. Third, we use the actor-critic algorithm to solve the policy optimization problem in an entropy regularized Markov decision process, where we also establish a convergence of $O(k^{-2/3})$. The results we derive for both the second and third problem are novel and previously unknown in the literature. Finally, we briefly present the application of our framework to gradient-based policy evaluation algorithms in reinforcement learning.
- Abstract（参考訳）: 最適化問題を解くための新しい2時間スケール確率勾配法について検討し、基礎となる最適化変数によって制御される時間変化MDPによって生成されたサンプルの下で、補助変数の助けを借りて勾配を計算する。
これらの時間変化のサンプルは、アップデートの勾配方向を偏り、依存しているため、イテレーションのばらつきにつながる可能性がある。
2時間スケールのアプローチでは、これらのサンプルから真の勾配を推定し、最適解の見積もりを更新する。
これら2つのイテレートは同時に実装されるが、前者は後者よりも高速に更新される。
最初の貢献は、提案した2時間スケール確率勾配法の有限時間複雑性を特徴づけることである。
特に、強い凸性、PL条件、一般の非凸性といった異なる構造的仮定の下で、この手法の収束率について明確な式を提供する。
様々な政策最適化問題に我々の枠組みを適用する。
まず、有限状態と作用空間を持つ無限水平平均逆 MDP を考察し、関数近似に基づくオンラインアクター批判アルゴリズムに対して$O(k^{-2/5}) の収束率を導出する。
第2に,オンラインアクター批判法が$O(k^{-2/3})$と収束することを示す。
第三に、エントロピー正規化マルコフ決定過程におけるポリシー最適化問題の解法としてアクター批判アルゴリズムを用い、ここでは$O(k^{-2/3})$の収束を確立する。
第2問題と第3問題の両方から導かれる結果は、新しいものであり、これまで文献で知られていなかったものである。
最後に、強化学習における勾配に基づく政策評価アルゴリズムへの我々のフレームワークの応用について概説する。
関連論文リスト
- Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning [5.325297567945828]
本稿では,従来の手法よりもはるかに高速な収束を実現する2段階最適化手法を提案する。
提案アルゴリズムは,様々な条件下で特徴付けられ,オンラインサンプルベース手法に特化していることを示す。
論文 参考訳（メタデータ） (2024-05-15T19:03:08Z) - Stochastic Dimension-reduced Second-order Methods for Policy
Optimization [11.19708535159457]
各イテレーションにおいて勾配とヘシアンベクトル積のみを必要とするポリシー最適化のための新しい2次アルゴリズムを提案する。
具体的には、投影された2次元信頼領域のサブプロブレムを繰り返す次元還元二階法(DR-SOPO)を提案する。
DR-SOPOはおよそ1次定常状態に到達するために$mathcalO(epsilon-3.5)$の複雑さが得られることを示す。
さらに,拡張アルゴリズム (DVR-SOPO) を提案する。
論文 参考訳（メタデータ） (2023-01-28T12:09:58Z) - Formal guarantees for heuristic optimization algorithms used in machine
learning [6.978625807687497]
グラディエント・Descent(SGD)とその変種は、大規模最適化機械学習(ML)問題において支配的な手法となっている。
本稿では,いくつかの凸最適化手法の形式的保証と改良アルゴリズムの提案を行う。
論文 参考訳（メタデータ） (2022-07-31T19:41:22Z) - Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes [13.908826484332282]
そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。
本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
論文 参考訳（メタデータ） (2021-10-21T18:05:40Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - A Unified Analysis of First-Order Methods for Smooth Games via Integral
Quadratic Constraints [10.578409461429626]
本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。
我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。
一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
論文 参考訳（メタデータ） (2020-09-23T20:02:00Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。