title: A unified analysis of value-function-based reinforcement- learning algorithms.
abstract: Reinforcement learning is the problem of generating optimal behavior in a sequential decision-making environment given the opportunity of interacting with it. Many algorithms for solving reinforcement-learning problems work by computing improved estimates of the optimal value function. We extend prior analyses of reinforcement-learning algorithms and present a powerful new theorem that can provide a unified analysis of such value-function-based reinforcement-learning algorithms. The usefulness of the theorem lies in how it allows the convergence of a complex asynchronous reinforcement-learning algorithm to be proved by verifying that a simpler synchronous algorithm converges. We illustrate the application of the theorem by analyzing the convergence of Q-learning, model-based reinforcement learning, Q-learning with multistate updates, Q-learning for Markov games, and risk-sensitive reinforcement learning.
authors.affiliation: Mindmaker, Ltd., Budapest 1121, Konkoly Thege M. U. 29-33, Hungary.
authors.forename: C
authors.initials: C
authors.lastname: Szepesvári
authors.forename: M L
authors.initials: ML
authors.lastname: Littman
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D007858:Learning; D012054:Reinforcement, Psychology