論文の概要: Finite-Sample Analysis of the Temporal Difference Learning
- arxiv url: http://arxiv.org/abs/2310.14286v1
- Date: Sun, 22 Oct 2023 12:37:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-25 00:43:21.169754
- Title: Finite-Sample Analysis of the Temporal Difference Learning
- Title(参考訳): 時間差学習における有限サンプル解析
- Authors: Sergey Samsonov, Daniil Tiapkin, Alexey Naumov, Eric Moulines
- Abstract要約: 一般化された, インスタンスに依存しないステップサイズを持つ単純なアルゴリズムは, ほぼ最適分散とバイアス項を得るのに十分であることを示す。
本手法は, 線形近似のための洗練された誤差境界と, ランダム行列の積に対する新しい安定性結果に基づく。
- 参考スコア(独自算出の注目度): 19.41392852257322
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we consider the problem of obtaining sharp bounds for the
performance of temporal difference (TD) methods with linear functional
approximation for policy evaluation in discounted Markov Decision Processes. We
show that a simple algorithm with a universal and instance-independent step
size together with Polyak-Ruppert tail averaging is sufficient to obtain
near-optimal variance and bias terms. We also provide the respective sample
complexity bounds. Our proof technique is based on refined error bounds for
linear stochastic approximation together with the novel stability result for
the product of random matrices that arise from the TD-type recurrence.
- Abstract(参考訳): 本稿では,割引マルコフ決定過程における政策評価のための線形関数近似を用いた時間差法(td)の性能向上のための鋭い境界を求める問題を考える。
本稿では,Polyak-Rupperttail averagingと組み合わせた,普遍的かつインスタンスに依存しないステップサイズを持つ単純なアルゴリズムが,ほぼ最適分散とバイアス項を得るのに十分であることを示す。
それぞれのサンプル複雑性境界も提供します。
提案手法は, 線形確率近似のための洗練された誤差境界と, TD型再帰から生じるランダム行列の積に対する新しい安定性結果に基づいている。
関連論文リスト
- SCAFFLSA: Quantifying and Eliminating Heterogeneity Bias in Federated
Linear Stochastic Approximation and Temporal Difference Learning [15.398826197774083]
異種エージェントを用いた局所訓練で導入されたバイアスを明示的に定量化する。
本稿では,FedLSAの新たな変種であるSCAFFLSAを提案する。
論文 参考訳(メタデータ) (2024-02-06T16:06:59Z) - Sharp high-probability sample complexities for policy evaluation with
linear function approximation [99.51752176624818]
本研究では,2つの広く利用されている政策評価アルゴリズムに対して,最適線形係数の予め定義された推定誤差を保証するために必要なサンプル複素量について検討する。
高確率収束保証に縛られた最初のサンプル複雑性を確立し、許容レベルへの最適依存を実現する。
論文 参考訳(メタデータ) (2023-05-30T12:58:39Z) - Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both
Worlds in Stochastic and Deterministic Environments [48.96971760679639]
マルコフ決定過程(MDP)の分散依存的後悔境界について検討する。
環境の微細な分散特性を特徴付けるための2つの新しい環境規範を提案する。
モデルに基づく手法では、MVPアルゴリズムの変種を設計する。
特に、この境界は極小かつ決定論的 MDP に対して同時に最適である。
論文 参考訳(メタデータ) (2023-01-31T06:54:06Z) - Asymptotically Unbiased Instance-wise Regularized Partial AUC
Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。
既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。
本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文 参考訳(メタデータ) (2022-10-08T08:26:22Z) - Linear Convergence for Natural Policy Gradient with Log-linear Policy
Parametrization [18.072051868187934]
正規化されていない自然政策アルゴリズムの収束速度を対数線形ポリシーパラメトリゼーションを用いて解析する。
このアルゴリズムは、決定論の場合と同じ線形保証を誤差項まで楽しむことを示す。
論文 参考訳(メタデータ) (2022-09-30T11:17:44Z) - Accelerated and instance-optimal policy evaluation with linear function
approximation [17.995515643150657]
既存のアルゴリズムはこれらの下界の少なくとも1つと一致しない。
我々は,両下界を同時に一致させる高速時間差分アルゴリズムを開発し,インスタンス最適性という強い概念を実現する。
論文 参考訳(メタデータ) (2021-12-24T17:21:04Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳(メタデータ) (2020-12-09T20:19:32Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳(メタデータ) (2020-07-07T21:26:35Z) - Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。
我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
論文 参考訳(メタデータ) (2020-03-16T17:15:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。