Learning Evaluation Functions for Large Acyclic Domains

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. 1 LEARNING CONTROL BACKWARDS Computing an accurate value function is the key to dynamic-programming-based algorithms for optimal sequential control in Markov Decision Processes. The optimal value function V (x) specifies, for each state x in the state space ...