Approximate Dynamic Programming Based on Expansive Projections

We present a general method to obtain convergent approximate value iteration algorithms with function approximation. The result is applicable to any arbitrary approximation architecture and generalizes existing results in the literature derived for particular approximation schemes. Additionally, we show how to obtain a convergent approximate mapping whose fixed point is the projection in the approximation space of a fixed point of the exact dynamic programming mapping with regards to a suitable subset norm. This result relies on evaluating the difference between successive iterates in the selected subset norm, which provides convergent procedures for any arbitrary approximation architecture.

I. Introduction

It is a well known fact that the process of finding the optimal solution to large scale Markov Decision Processes (MDP) is generally very demanding [9]. Approximate Dynamic Programming (ADP) algorithms [11] offer a plausible alternative of finding approximate solutions to MDP problems that would otherwise be intractable. One appealing ADP technique consists of incorporating a function approximation scheme into the problem in order to artificially reduce its complexity and searching for an approximate solution in a lower dimensional space [3], [11], [12]. Even though this approach has proved successful in practical applications, e.g. [14], there exist divergent counter-examples that make a strong case against the robustness of the technique [4].