Learning Rates for Q-learning

By Eyal Even-Dar, Yishay Mansour. 2004

554 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

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

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Taming the Noise in Reinforcement Learning via Soft Updates (2015, background): “8 , which is within the range suggested in [37].”
Learning to Act by Predicting the Future (2016, background): “While the understanding of the convergence of both types of methods has since improved (Szepesv´ari & Littman, 1999; Tsitsiklis, 2002; Even-Dar & Mansour, 2003), the argument for TD versus Monte Carlo is to this day empirical (Sutton & Barto, 2017).”
Dynamic policy programming (2010, methodology): “(Even-Dar and Mansour, 2003) (QL) and a model-based Q-value iteration (VI) (Kearns and Singh, 1999).”
A survey and critique of multiagent deep reinforcement learning (2018, background): “Q-learning is proven to converge to Q∗ if state and action spaces are discrete and finite, the sum of the learning rates goes to infinity (so that each state-action pair is visited infinitely often) and that the sum of the squares of the learning rates is finite (which is required to show that the c”
Averaged-DQN: Variance Reduction and Stabilization for Deep Reinforcement Learning (2016, methodology): “These methods are often analyzed in the setup of linear function approximation, where convergence is guaranteed under mild assumptions (Tsitsiklis, 1994; Jaakkola et al., 1994; Tsitsiklis & Van Roy, 1997; Even-Dar & Mansour, 2003). In practice, real-world problems usually involve high-dimensional in”
Algorithms for Reinforcement Learning (2010, background): “…t ≥ 0) is indeed known to converge to Q∗ when appropriate local learning rates are used (Tsitsiklis, 1994; Jaakkola et al., 1994).15 The rate of convergence of Q-learning was studied by Szepesvári (1997) in an asymptotic setting and later by Even-Dar and Mansour (2003) in a finite-sample setting.”
Adaptive stepsizes for recursive estimation with applications in approximate dynamic programming (2006, methodology): “The parameter η for the polynomial learning rate is set to the numerically optimal (as demonstrated in Even-Dar and Mansour (2004) ) value of 0.85.”
Is Q-learning Provably Efficient? (2018, background): “The majority of these results focus on an inﬁnite-horizon MDP with discounted reward [e.g., 2, 3, 8, 16, 23].”
Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction (2020, methodology): “Even-Dar and Mansour (2003) [20] (tcover) 1 1−γ (1−γ)4ε2 linear: 1 t”
Regularization in reinforcement learning (2011, methodology): “To our best knowledge this (and its conference version [Farahmand et al., 2009b]) alongside our other work on Regularized Fitted Q-Iteration [Farahmand et al., 2008, 2009a] and Chapter 5 are the first work that address the finite-sample performance of a regularized RL algorithm. Nevertheless, there ”
Learning and Using Models (2012, background): “2 Q-LEARNING, which was developed before E(3), was not proved to converge in polynomial time until after the development of E(3) (Even-dar and Mansour, 2001).”
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].”
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].”
A unifying framework for computational reinforcement learning theory (2009, background): “A related class is called typed dynamics (see, e.g., Leffler et al. [2007]), where the transition functions depends on a type τ(s) assigned to each state s and action a.”
PAC model-free reinforcement learning (2006, background): “Even-Dar and Mansour (2003) studied the convergence rate of Q-learning. They showed that, under a certain assumption, Q-learning converges to a near-optimal value function in a polynomial number of timesteps. The result requires input of an exploration policy that, with high probability, tries every”
Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems (2006, background): “Generic convergence rate bounds for stochastic approximation (e.g., Borkar and Meyn, 2000) or speciﬁc rates for Q-learning (see, Kearns and Singh, 1998, Even-Dar and Mansour, 2003) are somewhat disappointing.”
Learn What Not to Learn: Action Elimination with Deep Reinforcement Learning (2018, methodology): “The Q-function was initially set to 0, the learning rates were chosen according to (Even-Dar and Mansour, 2003), and we set γ = 1.”
PAC Bounds for Multi-armed Bandit and Markov Decision Processes (2002, background): “The learning algorithm in the MDP is based on Phased Q-learning [15].”