論文の概要: Finite time analysis of temporal difference learning with linear
function approximation: Tail averaging and regularisation
- arxiv url: http://arxiv.org/abs/2210.05918v2
- Date: Mon, 11 Sep 2023 04:22:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-12 23:11:12.462848
- Title: Finite time analysis of temporal difference learning with linear
function approximation: Tail averaging and regularisation
- Title(参考訳): 線形関数近似による時間差学習の有限時間解析:末尾平均化と正規化
- Authors: Gandharv Patil, Prashanth L.A., Dheeraj Nagaraj, Doina Precup
- Abstract要約: そこで本研究では,TD学習アルゴリズムの時間的有限性について検討した。
ステップサイズ選択の下で、テール平均TDのパラメータ誤差に基づいて有限時間境界を導出する。
- 参考スコア(独自算出の注目度): 44.27439128304058
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We study the finite-time behaviour of the popular temporal difference (TD)
learning algorithm when combined with tail-averaging. We derive finite time
bounds on the parameter error of the tail-averaged TD iterate under a step-size
choice that does not require information about the eigenvalues of the matrix
underlying the projected TD fixed point. Our analysis shows that tail-averaged
TD converges at the optimal $O\left(1/t\right)$ rate, both in expectation and
with high probability. In addition, our bounds exhibit a sharper rate of decay
for the initial error (bias), which is an improvement over averaging all
iterates. We also propose and analyse a variant of TD that incorporates
regularisation. From analysis, we conclude that the regularised version of TD
is useful for problems with ill-conditioned features.
- Abstract(参考訳): 一般時間差学習アルゴリズム(popular temporal difference:td)の有限時間挙動をテール平均化と組み合わせて検討した。
予測された td の不動点の下にある行列の固有値に関する情報を必要としないステップサイズの選択の下で、テール平均 td のパラメータ誤差の有限時間境界を求める。
我々の分析は、テール平均TDは期待値と高い確率の両方で最適な$O\left(1/t\right)$レートで収束することを示している。
加えて、我々の境界は初期誤差(bias)に対してより鋭い減衰率を示し、全てのイテレートの平均よりも改善されている。
また,正規化を組み込んだtdの変種を提案し,解析する。
分析の結果,TDの正規化バージョンは不条件特徴の問題に有用であることがわかった。
関連論文リスト
- Distributed TD(0) with Almost No Communication [15.321579527891457]
線形関数近似を用いた時間差分学習の非漸近解析法を提案する。
分散過程の収束時間がTD(0)の収束時間よりもN$の係数である線形時間高速化現象のバージョンを実証する。
論文 参考訳(メタデータ) (2023-05-25T17:00:46Z) - Non-stationary Online Convex Optimization with Arbitrary Delays [55.13328423837296]
本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。
まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。
DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-05-20T07:54:07Z) - Policy evaluation from a single path: Multi-step methods, mixing and
mis-specification [45.88067550131531]
無限水平$gamma$-discounted Markov rewardプロセスの値関数の非パラメトリック推定について検討した。
カーネルベースの多段階時間差推定の一般的なファミリーに対して、漸近的でない保証を提供する。
論文 参考訳(メタデータ) (2022-11-07T23:15:25Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - PER-ETD: A Polynomially Efficient Emphatic Temporal Difference Learning
Method [49.93717224277131]
PEriodically Restarted-ETD(PEriodically Restarted-ETD)と呼ばれる新しいETD手法を提案する。
PER-ETD は ETD と同じ所望の固定点に収束するが, 指数的なサンプルの複雑性は向上する。
論文 参考訳(メタデータ) (2021-10-13T17:40:12Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳(メタデータ) (2021-06-28T00:17:01Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳(メタデータ) (2021-02-05T14:02:20Z) - 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) - Bounding the expected run-time of nonconvex optimization with early
stopping [2.7648976108201815]
本研究は,検証関数に基づく早期停止を用いた勾配に基づく最適化アルゴリズムの収束性について検討する。
我々は、この停止規則が適切に定義されていることを保証する条件を導出し、この基準を満たすのに必要なイテレーション数と勾配評価の期待値のバウンダリを提供する。
論文 参考訳(メタデータ) (2020-02-20T16:43:37Z) - Reanalysis of Variance Reduced Temporal Difference Learning [57.150444843282]
Korda と La が提案した分散還元型TD (VRTD) アルゴリズムは,マルコフサンプルを用いたオンラインTD学習に直接適用する。
我々は,VRTDが線形収束速度でTDの固定点解の近傍に収束することが保証されていることを示す。
論文 参考訳(メタデータ) (2020-01-07T05:32:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。