Fastest Convergence for Q-learning

Abstract

The Zap Q-learning algorithm introduced in this paper is an improvement of Watkins' original algorithm and recent competitors in several respects. It is a matrix-gain algorithm designed so that its asymptotic variance is optimal. Moreover, an ODE analysis suggests that the transient behavior is a close match to a deterministic Newton-Raphson implementation. This is made possible by a two time-scale update equation for the matrix gain sequence. The analysis suggests that the approach will lead to stable and efficient computation even for non-ideal parameterized settings. Numerical experiments confirm the quick convergence, even in such non-ideal cases. A secondary goal of this paper is tutorial. The first half of the paper contains a survey on reinforcement learning algorithms, with a focus on minimum variance algorithms.

Cited by in corpus (12)

• From self-tuning regulators to reinforcement learning and back again
• Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes
• Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation
• Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning
• Zap Q-Learning With Nonlinear Function Approximation
• Instance-dependent ${\ell }_{\infty }$-bounds for policy evaluation in tabular reinforcement learning
• Optimal Matrix Momentum Stochastic Approximation and Applications to Q-learning
• Optimal Rate of Convergence for Quasi-Stochastic Approximation
• Convex Q-Learning, Part 1: Deterministic Optimal Control
• Zap Q-Learning for Optimal Stopping Time Problems
• Momentum-based Accelerated Q-learning
• Accelerated Target Updates for Q-learning