2020

The Mean-Squared Error of Double Q-Learning

Weng, Wentao, Gupta, Harsh, He, Niao et al.

Understand

In this paper, we establish a theoretical comparison between the asymptotic mean-squared error of Double Q-learning and Q-learning.

Our result builds upon an analysis for linear stochastic approximation based on Lyapunov equations and applies to both tabular setting and with linear function approximation, provided that the optimal policy is unique and the algorithms converge.
We show that the asymptotic mean-squared error of Double Q-learning is exactly equal to that of Q-learning if Double Q-learning uses twice the learning rate of Q-learning and outputs the average of its two estimators.
We also present some practical implications of this theoretical observation using simulations.

Built on

Neuronlike adaptive elements that can solve difficult learning control problems
Andrew G Barto, Richard S Sutton, and Charles W Anderson · 1983
Earlier work this paper cites.
Learning to predict by the methods of temporal differences
Richard S Sutton · 1988
Earlier work this paper cites.
Learning from delayed rewards
Christopher John Cornish Hellaby Watkins · 1989
Earlier work this paper cites.
Q-learning
Christopher JCH Watkins and Peter Dayan · 1992
Earlier work this paper cites.
Residual algorithms: Reinforcement learning with function approximation
Leemon Baird · 1995
Earlier work this paper cites.
Neuro-dynamic programming
Dimitri P Bertsekas and John N Tsitsiklis · 1996
Earlier work this paper cites.
Analysis of temporal-diffference learning with function approximation
John N Tsitsiklis and Benjamin Van Roy · 1997
Earlier work this paper cites.
Linear system theory and design
Chi-Tsong Chen · 1998
Earlier work this paper cites.
The ode method for convergence of stochastic approximation and reinforcement learning
Vivek S Borkar and Sean P Meyn · 2000
Earlier work this paper cites.
Stochastic approximation and recursive algorithms and applications
Harold Kushner and G George Yin · 2003
Earlier work this paper cites.
An analysis of reinforcement learning with function approximation
Francisco S Melo, Sean P Meyn, and M Isabel Ribeiro · 2008
Earlier work this paper cites.
Stochastic approximation: a dynamical systems viewpoint
Vivek S Borkar · 2009
Earlier work this paper cites.

Similar

Double q-learning
Hado V Hasselt · 2010
Cited alongside, same era.
Adaptive algorithms and stochastic approximations
Albert Benveniste, Michel Métivier, and Pierre Priouret · 2012
Cited alongside, same era.
A tutorial on linear function approximators for dynamic programming and reinforcement learning
Alborz Geramifard, Thomas J Walsh, Stefanie Tellex, Girish Chowdhary, Nicholas Roy, and Jonathan P How · 2013
Cited alongside, same era.
Openai gym
Original
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba · 2016
Cited alongside, same era.
Deep reinforcement learning with double q-learning
Hado Van Hasselt, Arthur Guez, and David Silver · 2016
Cited alongside, same era.
Averaged-dqn: Variance reduction and stabilization for deep reinforcement learning
Oron Anschel, Nir Baram, and Nahum Shimkin · 2017
Cited alongside, same era.
Fastest convergence for q-learning
Original
Adithya M Devraj and Sean P Meyn · 2017
Cited alongside, same era.
Weighted double q-learning
Zongzhang Zhang, Zhiyuan Pan, and Mykel J Kochenderfer · 2017
Cited alongside, same era.
A finite time analysis of temporal difference learning with linear function approximation
Jalaj Bhandari, Daniel Russo, and Raghav Singal · 2018
Cited alongside, same era.
Finite sample analyses for td(0) with function approximation
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor · 2018
Cited alongside, same era.
Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor · 2018
Cited alongside, same era.
Linear stochastic approximation: How far does constant step-size and iterate averaging go?
Chandrashekar Lakshminarayanan and Csaba Szepesvari · 2018
Cited alongside, same era.

Then

Reinforcement learning: An introduction
Richard S Sutton and Andrew G Barto · 2018
Later among the works it cites.
Performance of q-learning with linear function approximation: Stability and finite-time analysis
Original
Zaiwei Chen, Sheng Zhang, Thinh T Doan, Siva Theja Maguluri, and John-Paul Clarke · 2019
Later among the works it cites.
Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning
Harsh Gupta, R Srikant, and Lei Ying · 2019
Later among the works it cites.
Characterizing the exact behaviors of temporal difference learning algorithms using markov jump linear system theory
Bin Hu and Usman Syed · 2019
Later among the works it cites.
Target-based temporal-difference learning
Donghwan Lee and Niao He · 2019
Later among the works it cites.
A unified switching system perspective and ode analysis of q-learning algorithms
Original
Donghwan Lee and Niao He · 2019
Later among the works it cites.
Finite-time error bounds for linear stochastic approximation and td learning
R Srikant and Lei Ying · 2019
Later among the works it cites.
Explicit mean-square error bounds for monte-carlo and linear stochastic approximation
Original
Shuhang Chen, Adithya M Devraj, Ana Bušić, and Sean Meyn · 2020
Closest in time.
Finite-sample analysis of stochastic approximation using smooth convex envelopes
Original
Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam · 2020
Closest in time.
Q-learning with uniformly bounded variance: Large discounting is not a barrier to fast learning
Original
Adithya M Devraj and Sean P Meyn · 2020
Closest in time.
OpenAI Gym’s cart-pole balancing using q-learning
MC.AI · 2020
Closest in time.
Finite-time analysis of asynchronous stochastic approximation and q q -learning
Original
Guannan Qu and Adam Wierman · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…