Algorithms for Approximating Optimal Value Functions in Acyclic Domains (1996)
Tags
Markov Decision Processes, Optimization, Reinforcement Learning
Abstract
Some of the most successful recent applications of reinforcement learning have used neural networks and the TD() algorithm to learn evaluation functions. In this paper, we examine the intuition that TD() operates by approximating asynchronous value iteration. We note that on the important subclass of acyclic tasks, value iteration is inefficient compared with another graph algorithm, DAG-SP, which assigns values to states by working strictly backwards from the goal. We then present ROUT, an algorithm analogous to DAG-SP that can be used in large stochastic state spaces requiring function approximation. We close by comparing the behavior of ROUT and TD on a simple example domain and on two domains with much larger state spaces.
Full text
Download (application/pdf, 217.9 kB)
Approximate BibTeX Entry
@inproceedings{boyan-algorithms,
Year = {1996},
Publisher = {Morgan Kaufmann},
Booktitle = {Machine Learning: Proceedings of the Thirteenth International Conference},
Editor = {L. Saitta},
Author = {
Justin Boyan, Andrew
Moore
},
Title = {Algorithms for Approximating Optimal Value Functions in Acyclic Domains}
}