We consider a general asynchronous Stochastic Approximation (SA) scheme featuring a weighted infinity-norm contractive operator, and prove a bound on its finite-time convergence rate on a single trajectory.
Reading the bibliography…
Martin J Wainwright · 1905
Earlier work this paper cites.
Variance-reduced q q -learning is minimax optimal
Martin J Wainwright · 1906
Earlier work this paper cites.
A stochastic approximation method
Herbert Robbins and Sutton Monro · 1951
Earlier work this paper cites.
Q-learning
Christopher JCH Watkins and Peter Dayan · 1992
Earlier work this paper cites.
Convergence of stochastic iterative dynamic programming algorithms
Tommi Jaakkola, Michael I Jordan, and Satinder P Singh · 1994
Earlier work this paper cites.
Asynchronous stochastic approximation and Q-learning
John N Tsitsiklis · 1994
Earlier work this paper cites.
Neuro-dynamic programming , volume 5
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.
The asymptotic convergence-rate of Q-learning
Csaba Szepesvári · 1998
Earlier work this paper cites.
Finite-sample convergence rates for Q-learning and indirect algorithms
Michael J Kearns and Satinder P Singh · 1999
Earlier work this paper cites.
Actor-critic algorithms
Vijay R Konda and John N Tsitsiklis · 2000
Earlier work this paper cites.
Learning rates for Q-learning
Eyal Even-Dar and Yishay Mansour · 2003
Cited alongside, same era.
Linear stochastic approximation driven by slowly varying markov chains
Vijay R Konda and John N Tsitsiklis · 2003
Cited alongside, same era.
PAC model-free reinforcement learning
Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman · 2006
Cited alongside, same era.
An analysis of reinforcement learning with function approximation
Francisco S Melo, Sean P Meyn, and M Isabel Ribeiro · 2008
Cited alongside, same era.
Stochastic approximation: a dynamical systems viewpoint , volume 48
Vivek S Borkar · 2009
Cited alongside, same era.
Double Q-learning
Hado V Hasselt · 2010
Cited alongside, same era.
Speedy Q-learning
Mohammad Gheshlaghi Azar, Rémi Munos, Mohammad Ghavamzadeh, and Hilbert Kappen · 2011
Cited alongside, same era.
Error bounds for constant step-size Q-learning
Carolyn L Beck and Rayadurgam Srikant · 2012
Cited alongside, same era.
Adaptive algorithms and stochastic approximations , volume 22
Albert Benveniste, Michel Métivier, and Pierre Priouret · 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.
Zap Q-learning
Adithya M Devraj and Sean Meyn · 2017
Cited alongside, same era.
Near-optimal time and sample complexities for solving markov decision processes with a generative model
Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye
Cited in the paper.
Markov chains and mixing times , volume 107
David A Levin and Yuval Peres · 2017
Later among the works it cites.
Is Q-learning provably efficient?
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan · 2018
Later among the works it cites.
Q-learning with nearest neighbors
Devavrat Shah and Qiaomin Xie · 2018
Later among the works it cites.
Performance of Q-learning with linear function approximation: Stability and finite-time analysis
Zaiwei Chen, Sheng Zhang, Thinh T Doan, Siva Theja Maguluri, and John-Paul Clarke · 2019
Later among the works it cites.
Finite-time analysis and restarting scheme for linear two-time-scale stochastic approximation
Thinh T Doan · 2019
Later among the works it cites.
Q-learning with UCB exploration is sample efficient for infinite-horizon MDP
Kefan Dong, Yuanhao Wang, Xiaoyu Chen, and Liwei Wang · 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.
A unified switching system perspective and ODE analysis of Q-learning algorithms
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.
Model-free reinforcement learning in infinite-horizon average-reward markov decision processes
Chen-Yu Wei, Mehdi Jafarnia-Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain · 2019
Later among the works it cites.
Two time-scale off-policy td learning: Non-asymptotic analysis over markovian samples
Tengyu Xu, Shaofeng Zou, and Yingbin Liang · 2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…