The Asymptotic Convergence-Rate of Q-learning

By Csaba Szepesvari. 1997

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Dynamic policy programming (2010, background): “…is an important diﬀerence since it is known that the convergence rate of incremental RL methods like Q-learning is very sensitive to the choice of learning step (Even-Dar and Mansour, 2003; Szepesv´ari, 1997) and a bad choice of the learning step may lead to signiﬁcantly slow rate of convergence.”
Algorithms for Reinforcement Learning (2010, methodology): “Certainly, there are some cases when systematic exploration is not needed (e.g., Szepesvári, 1997; Nascimento and Powell, 2009).”
Comparing Value-Function Estimation Algorithms in Undiscounted Problems (2012, background): “As it was noted in [7], such a model-based learning clearly satis es the law of iterated logarithm.”
Q-learning with Nearest Neighbors (2018, methodology): “The behaviors of standard Q-learning in finite state-action problems have by now been reasonably understood; in particular, both asymptotic and finite-sample convergence guarantees have been established [43, 22, 41, 18].”
Zap Q-Learning (2017, methodology): “This conclusion is complementary to the finite-n analysis of [25]: Theorem 2.”
Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction (2020, methodology): “[24, 42, 43]); these results, however, did not lead to non-asymptotic sample complexity bounds.”
Bias-corrected Q-learning to control max-operator bias in Q-learning (2013, background): “The asymptotic rate of convergence of Q-learning has been studied in [13], [14], [15].”
A Unified Analysis of Value-Function-Based Reinforcement-Learning Algorithms (1999, background): “If some a priori knowledge of the "smoothness" of the optimal Q value is available, then one can make the updates of Q-Iearning more efficient by introducing a so-called :'spreading mechanism, : ' which updates the Q values of state-action pairs in the vicinity of the actual state-action pair as…”
Speedy Q-Learning (2011, background): “The main reason for the slow convergence of Q-learning is the combination of the sample-based stochastic approximation (that makes use of a decaying learning rate) and the fact that the Bellman operator propagates information throughout the whole space (specially when γ is close to 1 ).”
Reinforcement Learning in Finite MDPs: PAC Analysis (2009, background): “These convergence results make no performance guarantee after only a finite amount of experience, although more recent work has looked at convergence rates (Szepesvári, 1998; Kearns and Singh, 1999; Even-Dar and Mansour, 2003).”
Bias in Natural Actor-Critic Algorithms (2014, background): “Smaller values of γ are known to result in faster convergence of value function estimates (Szepesvari, 1997), however larger γ typically result in smoother value functions that may be easier to approximate accurately with few features.”
Double Q-learning (2010, background): “The convergence rate of Q-learning can be exponential in the number of experiences [13], although this is dependent on the learning rates and with a proper choice of learning rates convergence in polynomial time can be obtained [14].”
SINR-Based DoS Attack on Remote State Estimation: A Game-Theoretic Approach (2017, background): “The details are similar to [32] and we omit here.”