論文の概要: A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation

• arxiv url: http://arxiv.org/abs/2403.02476v1
• Date: Mon, 4 Mar 2024 20:40:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-06 16:58:54.428688
• Title: A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation
• Title（参考訳）: 線形関数近似を用いたTD学習の簡易有限時間解析
• Authors: Aritra Mitra
• Abstract要約: マルコフサンプリングの下で線形関数近似を用いたTD学習の有限時間収束について検討する。 提案アルゴリズムでは,プロジェクションステップを実際に実行することなく,プロジェクションに基づく解析の単純さを維持することができることを示す。
• 参考スコア（独自算出の注目度）: 2.44755919161855
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the finite-time convergence of TD learning with linear function approximation under Markovian sampling. Existing proofs for this setting either assume a projection step in the algorithm to simplify the analysis, or require a fairly intricate argument to ensure stability of the iterates. We ask: \textit{Is it possible to retain the simplicity of a projection-based analysis without actually performing a projection step in the algorithm?} Our main contribution is to show this is possible via a novel two-step argument. In the first step, we use induction to prove that under a standard choice of a constant step-size $\alpha$, the iterates generated by TD learning remain uniformly bounded in expectation. In the second step, we establish a recursion that mimics the steady-state dynamics of TD learning up to a bounded perturbation on the order of $O(\alpha^2)$ that captures the effect of Markovian sampling. Combining these pieces leads to an overall approach that considerably simplifies existing proofs. We conjecture that our inductive proof technique will find applications in the analyses of more complex stochastic approximation algorithms, and conclude by providing some examples of such applications.
• Abstract（参考訳）: マルコフサンプリングの下で線形関数近似を用いたTD学習の有限時間収束について検討する。 この設定の既存の証明は、解析を単純化するためにアルゴリズムの投影ステップを仮定するか、イテレートの安定性を確保するためにかなり複雑な引数を必要とする。 アルゴリズムで実際にプロジェクションステップを実行することなく、プロジェクションベースの分析の単純さを維持することは可能ですか? } 私たちの大きな貢献は、新しい二段階引数でこれを可能にすることです。 最初のステップでは、帰納法を用いて、一定のステップサイズ$\alpha$の標準的な選択の下で、TD学習によって生成される反復が期待通りに一様に有界であることを証明する。 2番目のステップでは、マルコフサンプリングの効果を捉えた$O(\alpha^2)$の順序で有界摂動まで TD 学習の定常力学を模倣する再帰を確立する。 これらの部品を組み合わせると、既存の証明をかなり単純化する全体的なアプローチに繋がる。 我々の帰納的証明手法はより複雑な確率近似アルゴリズムの解析に応用が見出され、そのような応用のいくつかの例を提示して結論付ける。

関連論文リスト

• Analysis of Off-Policy Multi-Step TD-Learning with Linear Function Approximation [5.152147416671501]
  本稿では,線形関数近似,オフポリシー学習,ブートストラッピングを特徴とする多段階TD学習アルゴリズムを解析する。 2つのnステップのTD学習アルゴリズムが提案され分析され、このアルゴリズムは勾配と制御理論のモデルなし強化学習とみなすことができる。
  論文  参考訳（メタデータ） (2024-02-24T10:42:50Z)
• Provably Faster Gradient Descent via Long Steps [0.0]
  短期的な目的値を増加させる長いステップは、長期的収束を確実に速くすることを示す。 勾配降下のより高速な$O(1/Tlog T)$レートを証明するための予想も、単純な数値検証と共に動機付けられる。
  論文  参考訳（メタデータ） (2023-07-12T17:41:07Z)
• Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers [90.45898746733397]
  本研究では拡散生成モデルに用いる決定論的サンプリング器の非漸近解析のためのフレームワークを開発する。 確率フローODEに沿った1ステップは,1) 条件付き対数線上を無限に先行して上昇する回復ステップ,2) 雑音を現在の勾配に向けて前向きに進行する劣化ステップの2段階で表すことができる。
  論文  参考訳（メタデータ） (2023-03-06T18:59:19Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• 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)
• 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)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Proximal Gradient Temporal Difference Learning: Stable Reinforcement Learning with Polynomial Sample Complexity [40.73281056650241]
  本稿では,真の勾配時間差学習アルゴリズムを設計・解析する原理的な方法として,近位勾配時間差学習を導入する。 本研究では, 従来の目的関数からではなく, 主目的関数から始めることによって, 勾配性TD強化学習法を公式に導出する方法を示す。
  論文  参考訳（メタデータ） (2020-06-06T21:04:21Z)
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping [69.9674326582747]
  そこで本研究では,重み付き分散雑音を用いたスムーズな凸最適化のための,クリップ付きSSTMと呼ばれる新しい1次高速化手法を提案する。 この場合、最先端の結果を上回る新たな複雑さが証明される。 本研究は,SGDにおいて,ノイズに対する光細かな仮定を伴わずにクリッピングを施した最初の非自明な高確率複雑性境界を導出した。
  論文  参考訳（メタデータ） (2020-05-21T17:05:27Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。