An Analysis of Reinforcement Learning with Function Approximation

Abstract

We address the problem of computing the optimal Q-function in Markov decision problems with infinite state-space. We analyze the convergence properties of several variations of Q-learning when combined with function approximation, extending the analysis of TD-learning in Tsitsiklis and Van Roy (1996) to stochastic control settings. We identify conditions under which such approximate methods converge with probability 1. We conclude with a brief discussion on the general applicability of our results and compare them with several related works.

arXiv commentThis version of the paper corrects the one that was presented at the 25th International Conference on Machine Learning. We corrected condition (7) of Theorem 1 and its proof, as well as the importance-sampling update (11). We also made the assumptions of Theorems 1 and 2 more precise and revised the proof of Theorem 2, adding an appendix with the auxiliary results it uses

Cited by in corpus (39)

• A Survey and Critique of Multiagent Deep Reinforcement Learning
• Mean Field Multi-Agent Reinforcement Learning
• Towards Characterizing Divergence in Deep Q-Learning
• Projective simulation with generalization
• State of the Art Control of Atari Games Using Shallow Reinforcement Learning
• Sample-Optimal Parametric Q-Learning Using Linearly Additive Features
• An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods
• Scalable Bilinear $\pi$ Learning Using State and Action Features
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• Online Transfer Learning in Reinforcement Learning Domains
• A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation
• Feature-Based Q-Learning for Two-Player Stochastic Games
• Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
• Finite-time Analysis of Approximate Policy Iteration for the Linear Quadratic Regulator
• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants
• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima
• A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithms
• Zap Q-Learning With Nonlinear Function Approximation
• Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noise
• Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
• Local Stochastic Approximation: A Unified View of Federated Learning and Distributed Multi-Task Reinforcement Learning Algorithms
• Multi-timescale memory dynamics in a reinforcement learning network with attention-gated memory
• Breaking the Deadly Triad with a Target Network
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms
• Nonparametric Stochastic Compositional Gradient Descent for Q-Learning in Continuous Markov Decision Problems
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
• Convex Q-Learning, Part 1: Deterministic Optimal Control
• Deep Reinforcement Learning via L-BFGS Optimization
• Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm
• Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity
• Efficient Ridesharing Order Dispatching with Mean Field Multi-Agent Reinforcement Learning
• Truncated Emphatic Temporal Difference Methods for Prediction and Control
• Temporal-difference learning with nonlinear function approximation: lazy training and mean field regimes
• Multi-Armed Bandits for Correlated Markovian Environments with Smoothed Reward Feedback
• Asymptotic Theory for IV-Based Reinforcement Learning with Potential Endogeneity
• Predictor-Corrector(PC) Temporal Difference(TD) Learning (PCTD)
• Multi-Fidelity Reinforcement Learning with Gaussian Processes
• Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation