Robust Value Function Approximation by Working Backwards

In this paper, we examine the intuition that TD() is meant to operate by approximating asynchronous value iteration. We note that on the important class of discrete acyclic stochastic tasks, value iteration is inefficient compared with the DAG-SP algorithm, which essentially performs only one sweep instead of many by working backwards from the goal. The question we address in this paper is whether there is an analogous algorithm that can be used in large stochastic state spaces requiring function approximation. We present such an algorithm, analyze it, and give comparative results to TD on several domains. 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 X, the expected cumulative reward when starting in state x and acting optimally thereafter. It is also the unique solution to..