論文の概要: A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous
Q-Learning and TD-Learning Variants
- arxiv url: http://arxiv.org/abs/2102.01567v1
- Date: Tue, 2 Feb 2021 15:48:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-03 19:01:51.122257
- Title: A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous
Q-Learning and TD-Learning Variants
- Title（参考訳）: 非同期Q-LearningとTD-Learningの有限サンプル保証に対するリアプノフ理論
- Authors: Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan
Shanmugam
- Abstract要約: 本稿では,値に基づく非同期強化学習(RL)アルゴリズムのクラスにおいて,有限サンプル収束を保証するための統一フレームワークを開発する。
我々は、Q$-learning、$n$-step TD、TD$(lambda)$、V-traceを含む非政治的なTDアルゴリズムなどのRLアルゴリズムに対して、有限サンプル平均二乗収束境界を確立する。
- 参考スコア（独自算出の注目度）: 37.65565099740316
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper develops an unified framework to study finite-sample convergence
guarantees of a large class of value-based asynchronous Reinforcement Learning
(RL) algorithms. We do this by first reformulating the RL algorithms as
Markovian Stochastic Approximation (SA) algorithms to solve fixed-point
equations. We then develop a Lyapunov analysis and derive mean-square error
bounds on the convergence of the Markovian SA. Based on this central result, we
establish finite-sample mean-square convergence bounds for asynchronous RL
algorithms such as $Q$-learning, $n$-step TD, TD$(\lambda)$, and off-policy TD
algorithms including V-trace. As a by-product, by analyzing the performance
bounds of the TD$(\lambda)$ (and $n$-step TD) algorithm for general $\lambda$
(and $n$), we demonstrate a bias-variance trade-off, i.e., efficiency of
bootstrapping in RL. This was first posed as an open problem in [37].
- Abstract（参考訳）: 本稿では,大規模な値ベース非同期強化学習(RL)アルゴリズムの有限サンプル収束を保証する統一フレームワークを開発する。
我々は、まずRLアルゴリズムをマルコフ確率近似(SA)アルゴリズムとして再構成し、不動点方程式を解く。
次に、Lyapunov解析を開発し、マルコフSAの収束に関する平均二乗誤差境界を導出する。
この中心的な結果に基づいて,$Q$-learning,$n$-step TD,TD$(\lambda)$,V-traceを含む非政治的なTDアルゴリズムなどの非同期RLアルゴリズムに対して,有限サンプル平均二乗収束境界を確立する。
副産物として、TD$(\lambda)$(および$n$-step TD)アルゴリズムの性能境界を一般の$\lambda$(および$n$)に対して解析することにより、RLにおけるブートストラップの効率というバイアス分散トレードオフを実証する。
これは[37]で最初にオープンな問題として提起された。
関連論文リスト
- Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Model-Based Reinforcement Learning with Multinomial Logistic Function
Approximation [12.36108042107798]
マルコフ決定過程におけるモデルに基づく強化学習について検討する。
我々は,多項ロジスティックモデルにより状態遷移が与えられるMPPに対して,証明可能な効率のよいRLアルゴリズムを確立する。
本稿では,提案アルゴリズムが既存の手法より一貫して優れていることを示す。
論文 参考訳（メタデータ） (2022-12-27T16:25:09Z) - Simple and optimal methods for stochastic variational inequalities, II:
Markovian noise and policy evaluation in reinforcement learning [9.359939442911127]
本稿ではマルコフ雑音下での変分不等式(VI)のリセットに着目する。
我々のアルゴリズム開発における顕著な応用は、強化学習における政策評価問題である。
論文 参考訳（メタデータ） (2020-11-15T04:05:22Z) - Stochastic Hard Thresholding Algorithms for AUC Maximization [49.00683387735522]
分散分類におけるAUCのためのハードしきい値決定アルゴリズムを開発した。
提案アルゴリズムの有効性と有効性を示す実験を行った。
論文 参考訳（メタデータ） (2020-11-04T16:49:29Z) - 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) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳（メタデータ） (2020-06-24T07:40:31Z) - Non-asymptotic Convergence of Adam-type Reinforcement Learning
Algorithms under Markovian Sampling [56.394284787780364]
本稿では、ポリシー勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して、最初の理論的収束解析を行う。
一般の非線形関数近似の下では、PG-AMSGradは定常点の近傍に収束し、$mathcalO(log T/sqrtT)$である。
線形関数近似の下では、一定段階のTD-AMSGradは$mathcalO(log T/sqrtT)の速度で大域的最適化の近傍に収束する。
論文 参考訳（メタデータ） (2020-02-15T00:26:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。