language: en

A Unified Analysis of Value-Function-Based Reinforcement-Learning Algorithms

Csaba Szepesvari
Research Group on Artificial Intelligence "Jozsef Attila" University
Szeged 6720, Aradi vrt tere 1. Hungary
szepes@sol.cc.u-szeged.hu
Michael L. Littman
Department of Computer Science Duke University
Durham, NC 27708-0129
mlittman@cs.duke.edu October 27, 1998

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 value-function-based reinforcement-learning algorithms. The usefulness of the theorem lies in how it allows the asynchronous convergence of a complex reinforcement-learning algorithm to be proven 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 multi-state updates, Q-learning for Markov games, and risk-sensitive reinforcement learning.

1 Introduction