論文の概要: Finite-sample Analysis of Greedy-GQ with Linear Function Approximation
under Markovian Noise
- arxiv url: http://arxiv.org/abs/2005.10175v1
- Date: Wed, 20 May 2020 16:35:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-01 04:54:49.187811
- Title: Finite-sample Analysis of Greedy-GQ with Linear Function Approximation
under Markovian Noise
- Title(参考訳): マルコフ雑音下での線形関数近似によるGQの有限サンプル解析
- Authors: Yue Wang and Shaofeng Zou
- Abstract要約: 本稿では,Greedy-GQアルゴリズムの最初の有限サンプル解析法を提案する。
本稿では,2つの時間スケール強化学習アルゴリズムの有限サンプル解析を拡張した。
- 参考スコア(独自算出の注目度): 23.62008807533706
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Greedy-GQ is an off-policy two timescale algorithm for optimal control in
reinforcement learning. This paper develops the first finite-sample analysis
for the Greedy-GQ algorithm with linear function approximation under Markovian
noise. Our finite-sample analysis provides theoretical justification for
choosing stepsizes for this two timescale algorithm for faster convergence in
practice, and suggests a trade-off between the convergence rate and the quality
of the obtained policy. Our paper extends the finite-sample analyses of two
timescale reinforcement learning algorithms from policy evaluation to optimal
control, which is of more practical interest. Specifically, in contrast to
existing finite-sample analyses for two timescale methods, e.g., GTD, GTD2 and
TDC, where their objective functions are convex, the objective function of the
Greedy-GQ algorithm is non-convex. Moreover, the Greedy-GQ algorithm is also
not a linear two-timescale stochastic approximation algorithm. Our techniques
in this paper provide a general framework for finite-sample analysis of
non-convex value-based reinforcement learning algorithms for optimal control.
- Abstract(参考訳): Greedy-GQは、強化学習における最適制御のためのオフポリティクス2時間スケールアルゴリズムである。
本稿では,マルコフ雑音下での線形関数近似を用いたGreedy-GQアルゴリズムの最初の有限サンプル解析法を開発する。
有限サンプル解析は、この2つの時間スケールアルゴリズムのステップ選択の理論的正当化を提供し、収束率と得られたポリシーの品質のトレードオフを示唆する。
本稿では,2つの時間スケール強化学習アルゴリズムの有限サンプル解析を,政策評価から最適制御まで拡張する。
具体的には、GTD、GTD2、TDCという2つの時間スケールの手法に対する既存の有限サンプル解析とは対照的に、Greedy-GQアルゴリズムの目的関数は非凸である。
さらに、greedy-gqアルゴリズムは線形2時間スケール確率近似アルゴリズムではない。
本稿では,非凸値に基づく強化学習アルゴリズムの有限サンプル解析のための汎用フレームワークを提案する。
関連論文リスト
- Reinforcement Learning with Unbiased Policy Evaluation and Linear
Function Approximation [11.345796608258434]
マルコフ決定プロセスを制御するためのシミュレーションベースのポリシーイテレーションの変種に対して,性能保証を提供する。
第一のアルゴリズムは最小二乗アプローチを伴い、各反復において、特徴ベクトルに関連する新しい重みの集合が少なくとも二乗によって得られる。
第2のアルゴリズムは、最小二乗解への勾配降下を数ステップ行う2段階の近似アルゴリズムを含む。
論文 参考訳(メタデータ) (2022-10-13T20:16:19Z) - Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
We show that Greedy-GQ algorithm converges fast-time error。
我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
論文 参考訳(メタデータ) (2022-09-06T15:04:57Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - Average-Reward Off-Policy Policy Evaluation with Function Approximation [66.67075551933438]
平均報酬MDPの関数近似によるオフポリシ政策評価を検討する。
ブートストラップは必要であり、オフポリシ学習とFAと一緒に、致命的なトライアドをもたらす。
そこで本研究では,勾配型tdアルゴリズムの成功を再現する2つの新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-08T00:43:04Z) - Smoothed functional-based gradient algorithms for off-policy reinforcement learning: A non-asymptotic viewpoint [8.087699764574788]
政治外の強化学習コンテキストにおける制御問題の解法として,2つのポリシー勾配アルゴリズムを提案する。
どちらのアルゴリズムも、スムーズな関数的勾配推定スキームを取り入れている。
論文 参考訳(メタデータ) (2021-01-06T17:06:42Z) - Sample Complexity Bounds for Two Timescale Value-based Reinforcement
Learning Algorithms [65.09383385484007]
2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。
本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
論文 参考訳(メタデータ) (2020-11-10T11:36:30Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - Differentially Private Accelerated Optimization Algorithms [0.7874708385247353]
微分プライベート最適化アルゴリズムの2つのクラスを示す。
最初のアルゴリズムはPolyakのヘビーボール法にインスパイアされている。
アルゴリズムの第2のクラスは、ネステロフの加速勾配法に基づいている。
論文 参考訳(メタデータ) (2020-08-05T08:23:01Z) - Finite-Sample Analysis of Proximal Gradient TD Algorithms [43.035055641190105]
アルゴリズムの勾配時間差分学習(GTD)ファミリーの収束速度を解析する。
また、GTD2とGTD2-MPという2つの修正アルゴリズムも提案されている。
理論解析の結果,GTDファミリーのアルゴリズムは,非政治的な学習シナリオにおける既存のLSTD手法と同等であることがわかった。
論文 参考訳(メタデータ) (2020-06-06T20:16:25Z) - Second-Order Guarantees in Centralized, Federated and Decentralized
Nonconvex Optimization [64.26238893241322]
単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。
いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。
これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
論文 参考訳(メタデータ) (2020-03-31T16:54:22Z) - Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
適応性は現代最適化理論において重要であるが、研究されていない性質である。
提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
論文 参考訳(メタデータ) (2020-02-13T05:42:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。