2021

Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs

Agarwal, Naman, Chaudhuri, Syomantak, Jain, Prateek et al.

Understand

Q-learning is a popular Reinforcement Learning (RL) algorithm which is widely used in practice with function approximation (Mnih et al., 2015).

In contrast, existing theoretical results are pessimistic about Q-learning.
For example, (Baird, 1995) shows that Q-learning does not converge even with linear function approximation for linear MDPs.
Furthermore, even for tabular MDPs with synchronous updates, Q-learning was shown to have sub-optimal sample complexity (Li et al., 2021;Azar et al., 2013).

Built on

Stochastic approximation with cone-contractive operators: Sharp ℓ ∞ \ell_{\infty} -bounds for q q -learning
Original
Martin J Wainwright · 1905
Earlier work this paper cites.
Variance-reduced q q -learning is minimax optimal
Original
Martin J Wainwright · 1906
Earlier work this paper cites.
On tail probabilities for martingales
David A Freedman · 1975
Earlier work this paper cites.
Maximal coupling
Sheldon Goldstein · 1979
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.
Self-improving reactive agents based on reinforcement learning, planning and teaching
Long-Ji Lin · 1992
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.
Generalization in reinforcement learning: Safely approximating the value function
Justin Boyan and Andrew W Moore · 1995
Earlier work this paper cites.
Feature-based methods for large scale dynamic programming
John N Tsitsiklis and Benjamin Van Roy · 1996
Earlier work this paper cites.
An analysis of temporal-difference learning with function approximation
John N Tsitsiklis and Benjamin Van Roy · 1997
Earlier work this paper cites.
Finite-sample convergence rates for q-learning and indirect algorithms
Michael Kearns and Satinder Singh · 1999
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.
Learning rates for q-learning
Eyal Even-Dar, Yishay Mansour, and Peter Bartlett · 2003
Earlier work this paper cites.
Interpolation-based q-learning
Csaba Szepesvári and William D Smart · 2004
Earlier work this paper cites.

Similar

Neural fitted q iteration–first experiences with a data efficient neural reinforcement learning method
Martin Riedmiller · 2005
Cited alongside, same era.
Finite-time bounds for fitted value iteration
Rémi Munos and Csaba Szepesvári · 2008
Cited alongside, same era.
Toward off-policy learning control with function approximation
Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, and Richard S. Sutton · 2010
Cited alongside, same era.
Dynamic programming and optimal control 3rd edition, volume ii
Dimitri P Bertsekas · 2011
Cited alongside, same era.
Speedy q-learning
Mohammad Ghavamzadeh, Hilbert Kappen, Mohammad Azar, and Rémi Munos · 2011
Cited alongside, same era.
Error bounds for constant step-size q-learning
Carolyn L Beck and Rayadurgam Srikant · 2012
Cited alongside, same era.
Minimax pac bounds on the sample complexity of reinforcement learning with a generative model
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen · 2013
Cited alongside, same era.
Human-level control through deep reinforcement learning
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al · 2015
Cited alongside, same era.
Concentration inequalities for markov chains by marton couplings and spectral methods
Daniel Paulin · 2015
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.
Reinforcement learning: An introduction
Richard S Sutton and Andrew G Barto · 2018
Cited alongside, same era.
High-dimensional probability: An introduction with applications in data science , volume 47
Roman Vershynin · 2018
Cited alongside, same era.

Then

Finite-time error bounds for linear stochastic approximation andtd learning
Rayadurgam Srikant and Lei Ying · 2019
Later among the works it cites.
Sample-optimal parametric q-learning using linearly additive features
Lin Yang and Mengdi Wang · 2019
Later among the works it cites.
Finite-sample analysis for sarsa with linear function approximation
Shaofeng Zou, Tengyu Xu, and Yingbin Liang · 2019
Later among the works it cites.
Model-based reinforcement learning with a generative model is minimax optimal
Alekh Agarwal, Sham Kakade, and Lin F Yang · 2020
Later among the works it cites.
Least squares regression with markovian data: Fundamental limits and algorithms
Original
Guy Bresler, Prateek Jain, Dheeraj Nagaraj, Praneeth Netrapalli, and Xian Wu · 2020
Later among the works it cites.
A new convergent variant of q-learning with linear function approximation
Diogo Carvalho, Francisco S. Melo, and Pedro Santos · 2020
Later among the works it cites.
Finite-sample analysis of contractive stochastic approximation using smooth convex envelopes
Original
Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam · 2020
Later among the works it cites.
Convergence rates of accelerated markov gradient descent with applications in reinforcement learning
Original
Thinh T Doan, Lam M Nguyen, Nhan H Pham, and Justin Romberg · 2020
Later among the works it cites.
A theoretical analysis of deep q-learning
Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang · 2020
Later among the works it cites.
Provably efficient reinforcement learning with linear function approximation
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan · 2020
Later among the works it cites.
Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen · 2020
Later among the works it cites.
Finite-time analysis of asynchronous stochastic approximation and q q -learning
Guannan Qu and Adam Wierman · 2020
Later among the works it cites.
Momentum q-learning with finite-sample convergence guarantee
Original
Bowen Weng, Huaqing Xiong, Lin Zhao, Yingbin Liang, and Wei Zhang · 2020
Later among the works it cites.
A finite-time analysis of q-learning with neural network function approximation
Pan Xu and Quanquan Gu · 2020
Later among the works it cites.
Learning near optimal policies with low inherent bellman error
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill · 2020
Later among the works it cites.
Is q-learning minimax optimal? a tight sample complexity analysis
Original
Gen Li, Changxiao Cai, Yuxin Chen, Yuantao Gu, Yuting Wei, and Yuejie Chi · 2021
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…