A finite time analysis of temporal difference learning with linear function approximation
From MaRDI portal
Abstract: Temporal difference learning (TD) is a simple iterative algorithm used to estimate the value function corresponding to a given policy in a Markov decision process. Although TD is one of the most widely used algorithms in reinforcement learning, its theoretical analysis has proved challenging and few guarantees on its statistical efficiency are available. In this work, we provide a simple and explicit finite time analysis of temporal difference learning with linear function approximation. Except for a few key insights, our analysis mirrors standard techniques for analyzing stochastic gradient descent algorithms, and therefore inherits the simplicity and elegance of that literature. Final sections of the paper show how all of our main results extend to the study of TD learning with eligibility traces, known as TD(), and to Q-learning applied in high-dimensional optimal stopping problems.
Recommendations
- On the convergence of temporal-difference learning with linear function approximation
- Proximal gradient temporal difference learning: stable reinforcement learning with polynomial sample complexity
- Least squares temporal difference methods: An analysis under general conditions
- TD(λ) learning without eligibility traces: a theoretical analysis
- An analysis of temporal-difference learning with function approximation
Cites work
- Acceleration of Stochastic Approximation by Averaging
- An analysis of temporal-difference learning with function approximation
- Convergence Results for Some Temporal Difference Methods Based on Least Squares
- Convex optimization: algorithms and complexity
- Distributed Policy Evaluation Under Multiple Behavior Strategies
- General state space Markov chains and MCMC algorithms
- How Much Does Your Data Exploration Overfit? Controlling Bias via Information Usage
- scientific article; zbMATH DE number 1095138 (Why is no real title available?)
- scientific article; zbMATH DE number 1972910 (Why is no real title available?)
- scientific article; zbMATH DE number 7246284 (Why is no real title available?)
- Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path
- Linear least-squares algorithms for temporal difference learning
- Non-convex optimization for machine learning
- On the Averaged Stochastic Approximation for Linear Regression
- On the worst-case analysis of temporal-difference learning algorithms
- Optimal stopping of Markov processes: Hilbert space theory, approximation algorithms, and an application to pricing high-dimensional financial derivatives
- Optimization methods for large-scale machine learning
- Policy evaluation with temporal differences: a survey and comparison
- Pricing American Options: A Duality Approach
- Robust Stochastic Approximation Approach to Stochastic Programming
- Stochastic optimal control. The discrete time case
- The Linear Programming Approach to Approximate Dynamic Programming
- The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning
Cited in
(23)- Concentration bounds for temporal difference learning with linear function approximation: the case of batch data and uniform sampling
- Fundamental design principles for reinforcement learning algorithms
- A concentration bound for \(\operatorname{LSPE}( \lambda )\)
- Chaotic dynamics and convergence analysis of temporal difference algorithms with bang-bang control
- An emphatic approach to the problem of off-policy temporal-difference learning
- True online temporal-difference learning
- TD(λ) learning without eligibility traces: a theoretical analysis
- Asymptotic analysis of value prediction by well-specified and misspecified models
- Proximal gradient temporal difference learning: stable reinforcement learning with polynomial sample complexity
- AN ANALYSIS OF EXPERIENCE REPLAY IN TEMPORAL DIFFERENCE LEARNING
- Finite-time performance of distributed temporal-difference learning with linear function approximation
- Finite-time analysis and restarting scheme for linear two-time-scale stochastic approximation
- Convergence of Recursive Stochastic Algorithms Using Wasserstein Divergence
- Some limit properties of Markov chains induced by recursive stochastic algorithms
- Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis
- Generalized TD learning
- Asymptotic analysis of temporal-difference learning algorithms with constant step-sizes
- Provably Efficient Reinforcement Learning with Linear Function Approximation
- Target Network and Truncation Overcome the Deadly Triad in \(\boldsymbol{Q}\)-Learning
- Neural Temporal Difference and Q Learning Provably Converge to Global Optima
- Stochastic approximation and reinforcement learning: the interface and a little beyond
- Concentration of contractive stochastic approximation: additive and multiplicative noise
- Reward-directed score-based diffusion models via q-learning
This page was built for publication: A finite time analysis of temporal difference learning with linear function approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5003727)
