Asynchronous stochastic approximation and Q-learning

By John N. Tsitsiklis. 1993

We provide some general results on the convergence of a class of stochastic approximation algorithms and their parallel and asynchronous variants. We then use these results to study the Q-learning algorithm, a reinforcement learning method for solving Markov decision problems, and establish its convergence under conditions more general than previously available.

Subfields: Reinforcement Learning, Statistical Learning Theory

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

In Statistical Learning Theory

Citations in the corpus

A unified framework for stochastic optimization (2019, methodology): “Building on work developing in computer science under the mbrella of “reinforcement learning” (reviewed below), Tsitsiklis 1994) and Jaakkola, Jordan, and Singh (1994) were the first to ecognize that the basic algorithms being developed under the mbrella of reinforcement learning represented…”
Evolutionary game theory and multi-agent reinforcement learning (2005, background): “Amongst others, Tsitsiklis [ Tsi93 ] has proved that under very reasonable assumptions Q-learning is guaranteed to converge to the optimal policy.”
Feature-based methods for large scale dynamic programming (1995, unknown): “Whitt (1978) and Reetz (1977) analyzed approaches of reducing state space sizes, which lead to compact representations.”
An Intelligent Battery Controller Using Bias-Corrected Q-learning (2012, unknown): “For this reason, Q-learning, given by equations (1) -(2), is an attractive algorithmic strategy , and is supported by powerful convergence theory (Tsitsiklis 1994; Jaakkola, Jordan, and Singh 1994).”
An Analysis of Temporal-Difference Learning with Function Approximation (1998, unknown): “With a lookup table representation, the operator is easily shown to be a maximum norm contraction, the projection operator is simply the identity matrix, and general results on stochastic approximation methods based on maximum norm contractions [4], [5] become applicable.”
Reinforcement Learning: An Introduction (1998, unknown): “Convergence with probability 1 for general λ was proved by several researchers at about the same time (Peng, 1993; Dayan and Sejnowski, 1994; Tsitsiklis, 1994; Gurvits, Lin, and Hanson, 1994).”
Using deep Q-learning to understand the tax evasion behavior of risk-averse firms (2018, methodology): “One advantage of reinforcement learning which will be useful to us is that, unlike DP, the process can be set to update the value of the cost-to-go function for the states that are most often visited (Tsitsiklis, 1994).”