Asynchronous stochastic approximation and Q-learning
Machine LearningPublished 1 September 1994Open access
John N. Tsitsiklis
Citations455
SJR quartileQ1
SJR score1.15
SNIP2.14
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The Q-learning algorithm, a reinforcement learning method for solving Markov decision problems, is studied to establish its convergence under conditions more general than previously available.
Abstract
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.
Keywords
Computer ScienceDecision Sciences
IEEE Transactions on Automatic ControlDistributed asynchronous deterministic and stochastic gradient optimization algorithms
2,021 Citations1986John N. Tsitsiklis, Dimitri P. Bertsekas +1 more
Applied mathematical sciencesStochastic Approximation Methods for Constrained and Unconstrained Systems
1,482 Citations1978Harold J. Kushner, Dean S. Clark
The Robbins-Monro and Kiefer-Wolfowitz Algorithm for Inequality Constraints and the Weak Convergence of Probability Measures, a simple example, and the Convergence Theorem, a proof of the Main Theorem.
Mathematics of Operations ResearchAn Analysis of Stochastic Shortest Path Problems
498 Citations1991Dimitri P. Bertsekas, John N. Tsitsiklis
A stochastic version of the classical shortest path problem whereby for each node of a graph, the authors must choose a probability distribution over the set of successor nodes so as to reach a certain destination node with minimum expected cost is considered.
IEEE Transactions on Automatic ControlDistributed dynamic programming
218 Citations1982Dimitri P. Bertsekas
SIAM Journal on Control and OptimizationAsymptotic Properties of Distributed and Communicating Stochastic Approximation Algorithms
129 Citations1987Harold J. Kushner, Gang Yin
The asymptotic properties of extensions of the type of distributed or decentralized stochastic approximation proposed in [1] are developed and have numerous potential applications in decentralized estimation, detection and adaptive control, or in decentralized Monte Carlo simulation for system optimization.
StochasticsStochastic approximation algorithms for parallel and distributed processing
52 Citations1987Harold J. Kushner, Gang Yin
An interesting class of "distributed" recursive stochastic algorithms that arises when parallel processing methods are used for the Monte Carlo optimization of systems, as well as in applications such as decentralized and asynchronous on-line optimization of the flows in communication networks are treated.
IEEE Transactions on Automatic ControlAsymptotic agreement and convergence of asynchronous stochastic algorithms
37 Citations1987Shu Li, Tamer Başar
Results are presented on the convergence and asymptotic agreement of a class of asynchronous distributed algorithms which are in general time-varying, memorydependent, and not necessarily associated with the optimization of a common cost functional.
Robot learning.Memory-based Reinforcement Learning: Converging with Less Data and Less Real Time
27 Citations1993Andrew Moore, Christopher G. Atkeson
This work compares Prioritized Sweeping with other reinforcement learning schemes for a number of different stochastic optimal control problems and successfully solves large state-space real time problems with which other methods have difficulty.