論文の概要: Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex
Envelopes
- arxiv url: http://arxiv.org/abs/2002.00874v6
- Date: Wed, 30 Jun 2021 13:09:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-04 08:38:48.446764
- Title: Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex
Envelopes
- Title(参考訳): Smooth Convex Envelopes を用いた確率近似の有限サンプル解析
- Authors: Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan
Shanmugam
- Abstract要約: 一般化エンベロープを用いて滑らかなリャプノフ函数を構築し、そのリャプノフ函数に対してSAの反復体が負のドリフトを持つことを示す。
特に、政治以外のTD学習において、Vトレースアルゴリズムの最初の既知収束率を確立するためにこれを用いる。
また、TD学習を現場で研究し、既存の最先端の成果を$Q$ラーニングで回収する。
- 参考スコア(独自算出の注目度): 40.31139355952393
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Stochastic Approximation (SA) is a popular approach for solving fixed-point
equations where the information is corrupted by noise. In this paper, we
consider an SA involving a contraction mapping with respect to an arbitrary
norm, and show its finite-sample error bounds while using different stepsizes.
The idea is to construct a smooth Lyapunov function using the generalized
Moreau envelope, and show that the iterates of SA have negative drift with
respect to that Lyapunov function. Our result is applicable in Reinforcement
Learning (RL). In particular, we use it to establish the first-known
convergence rate of the V-trace algorithm for off-policy TD-learning. Moreover,
we also use it to study TD-learning in the on-policy setting, and recover the
existing state-of-the-art results for $Q$-learning. Importantly, our
construction results in only a logarithmic dependence of the convergence bound
on the size of the state-space.
- Abstract(参考訳): 確率近似 (stochastic approximation, sa) は、情報がノイズによって腐敗する不動点方程式を解く一般的な手法である。
本稿では、任意のノルムに対する縮約写像を含むSAを考察し、異なる段数を用いて有限サンプル誤差境界を示す。
この考え方は、一般化されたモローエンベロープを用いて滑らかなリャプノフ函数を構築し、SA の反復体がそのリャプノフ函数に対して負のドリフトを持つことを示す。
この結果は強化学習(RL)に適用できる。
特に,オフポリシーtd学習におけるvトレースアルゴリズムの初見収束率の確立に使用する。
さらに,td-learningをオン・ポリシー・セッティングで研究し,q$-learningのために既存の最新結果を復元する。
重要なことに、我々の構成は状態空間のサイズに縛られた収束の対数依存だけをもたらす。
関連論文リスト
- Approximation of Convex Envelope Using Reinforcement Learning [0.0]
最適停止のためのQ-ラーニングの変種を用いて凸エンベロープを近似する強化学習手法を開発した。
一連のテスト問題に関して非常に有望な結果を示します。
論文 参考訳(メタデータ) (2023-11-24T11:47:08Z) - Finite-Sample Analysis of the Temporal Difference Learning [19.41392852257322]
一般化された, インスタンスに依存しないステップサイズを持つ単純なアルゴリズムは, ほぼ最適分散とバイアス項を得るのに十分であることを示す。
本手法は, 線形近似のための洗練された誤差境界と, ランダム行列の積に対する新しい安定性結果に基づく。
論文 参考訳(メタデータ) (2023-10-22T12:37:25Z) - Sample-Efficient Reinforcement Learning for POMDPs with Linear Function
Approximations [130.66193083412716]
本稿では,関数近似と部分観測可能性の緊張に対処する。
最適ポリシーと値関数は有限メモリヒルベルト・ベルマン作用素の列によって特徴づけられることを示す。
本稿では、カーネル空間(RKHS)の埋め込みを再現することで、これらの演算子の楽観的な推定値を構成するRLアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-04-20T21:15:38Z) - Whiplash Gradient Descent Dynamics [2.0508733018954843]
凸関数に対するWhiplash系に対するシンプレクティック収束解析を導入する。
本研究では,アルゴリズムの性能を様々なコストで検討し,収束率を解析するための実践的方法論を提供する。
論文 参考訳(メタデータ) (2022-03-04T05:47:26Z) - On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
本稿では,カーネル手法のコンテキストにおいて,現象を正確に特徴付けることができることを示す。
分離可能なヒルベルト空間における2次対象の最小化を考慮し、早期停止の場合、学習速度の選択が得られた解のスペクトル分解に影響を及ぼすことを示す。
論文 参考訳(メタデータ) (2022-02-28T13:01:04Z) - A Boosting Approach to Reinforcement Learning [59.46285581748018]
複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。
このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
論文 参考訳(メタデータ) (2021-08-22T16:00:45Z) - Behavior of linear L2-boosting algorithms in the vanishing learning rate
asymptotic [0.0]
学習速度が0に収束し、繰り返し回数が再スケールされるとき、勾配向上アルゴリズムの挙動について検討する。
消滅する学習速度の限界を証明し、無限次元関数空間における線形微分方程式のユニークな解として限界を特徴づける。
論文 参考訳(メタデータ) (2020-12-29T08:37:54Z) - On the Convergence Rate of Projected Gradient Descent for a
Back-Projection based Objective [58.33065918353532]
我々は、最小二乗(LS)の代替として、バックプロジェクションに基づく忠実度項を考える。
LS項ではなくBP項を用いることで最適化アルゴリズムの繰り返しを少なくすることを示す。
論文 参考訳(メタデータ) (2020-05-03T00:58:23Z) - SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for
Gaussian Process Regression with Derivatives [86.01677297601624]
本稿では,2次フーリエ特徴に基づく導関数によるGP回帰のスケーリング手法を提案する。
我々は、近似されたカーネルと近似された後部の両方に適用される決定論的、非漸近的、指数関数的に高速な崩壊誤差境界を証明した。
論文 参考訳(メタデータ) (2020-03-05T14:33:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。