Asynchronous Stochastic Approximation and Q-Learning

By John N. Tsitsiklis. 1994

How researchers see this paper

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

In Reinforcement Learning

Citations in the corpus

Asynchronous Methods for Deep Reinforcement Learning (2016, methodology): “(Tsitsiklis, 1994) studied convergence properties of Qlearning in the asynchronous optimization setting.”
RUDDER: Return Decomposition for Delayed Rewards (2018, methodology): “then perform TD updates with the Bellman error using the estimated r(s;a) [95]. Q-learning [127] is an off-policy TD algorithm which is proved to converge [128, 14]. The proofs were later generalized [53,120]. Q-learning uses E s0;a0[^q ˇ(s0;a0)] ˇmax a q^(S t+1;a) : (A27) The action-value function ”
On Convergence of Emphatic Temporal-Difference Learning (2015, methodology): “Using this and (Tsitsiklis, 1994, Lemma 1), we can conclude that Wt+1 − W̃t+1 a.s.→ 0.17 Since W̃t a.s.→ 0, this implies Wt a.s.→ 0.”
Reinforcement Learning with Replacing Eligibility Traces (2005, methodology): “The asymptotic convergence of accumulate TD( ) for general is well known (Dayan, 1992; Jaakkola, Jordan & Singh, 1994; Tsitsiklis, 1994; Peng, 1993).”
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”
Adaptive Control of Epileptic Seizures using Reinforcement Learning (2010, background): “The early theoretical analysis of Q-learning is presented in [71].”
Game Theory and Multi-agent Reinforcement Learning (2012, background): “Many of these systems can be treated as advanced exploration techniques for standard reinforcement learning and are still covered by the single agent theoretical frameworks, such as the framework described in (Tsitsiklis, 1994).”
Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms (2000, background): “…work has shown that there are off-policy RL algorithms that converge to optimal value functions (Watkins & Dayan, 1992; Dayan, 1992; Jaakkola et al., 1994; Tsitsiklis, 1994; Gullapalli & Barto, 1994; Littman & Szepesvári, 1996); we prove convergence results for several related on-policy algorithms.”
A Tour of Reinforcement Learning: The View from Continuous Control (2018, background): “(3.7) forms the basis of Q-learning algorithms [81, 85].”
An Evolutionary Dynamical Analysis of Multi-Agent Learning in Iterated Games (2005, methodology): “The reader who is interested in more details, we refer to [42].”
Analytical Mean Squared Error Curves for Temporal Difference Learning (1996, background): “Tsitsiklis (1994) , Barnard (1993); and for convergence of replace TD, first-visit MC, and everyvisit MC, see Singh & Sutton (1996).”
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.”
Neuro-Dynamic Programming (2009, methodology): “While there is convergence analysis of TD(λ) and Q-learning for the case of lookup table representations (see Tsitsiklis, 1994; Jaakkola et al., 1994), the situation is much less clear in the case of compact representations.”
Q-learning with Nearest Neighbors (2018, methodology): “Note that traditional results from stochastic approximation rely on unbiased updates and asymptotic analysis [35, 43].”
Randomized Ensembled Double Q-Learning: Learning Fast Without a Model (2021, background): “The stochastic approximation noise term is given by It is straightforward to show As in Lan et al. (2020), it follows from the contraction property and (2) that REDQ converges with probability 1 to the optimal Q function (Tsitsiklis, 1994; Bertsekas & Tsitsiklis, 1996).”