Operations Research · 2021 · 29 citations · 22 references
BusinessComputer ScienceAlgorithmsMachine LearningMarkov Decision ProcessesOptimal StoppingPolicy IterationPolicy LearningReinforcement LearningReinforcement Learning FoundationsStochastic ControlConvergenceConvergence TimeFinite TimeGradient DescentLinear ApproximationLinear Function ApproximationQ-learningTemporal-difference Learning
Temporal difference learning (TD) is a simple iterative algorithm widely used for policy evaluation in Markov reward processes. Bhandari et al. prove finite time convergence rates for TD learning with linear function approximation. The analysis follows using a key insight that establishes rigorous connections between TD updates and those of online gradient descent. In a model where observations are corrupted by i.i.d. noise, convergence results for TD follow by essentially mirroring the analysis for online gradient descent. Using an information-theoretic technique, the authors also provide results for the case when TD is applied to a single Markovian data stream where the algorithm’s updates can be severely biased. Their analysis seamlessly extends to the study of TD learning with eligibility traces and Q-learning for high-dimensional optimal stopping problems.
22
Human-level control through deep reinforcement learning
Volodymyr Mnih, Koray Kavukcuoglu, David Silver et al. · Nature · 2015 · 30K citations
Reinforcement Learning: An Introduction
Richard S. Sutton, Andy Barto · IEEE Transactions on Neural Networks · 1998 · 27.1K citations
Learning to predict by the methods of temporal differences
Richard S. Sutton · Machine Learning · 1988 · 2.8K citations · Full text
Robust Stochastic Approximation Approach to Stochastic Programming
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan et al. · SIAM Journal on Optimization · 2009 · 2.1K citations