FEATURE-BASED METHODS FOR LARGE-SCALE DYNAMIC-PROGRAMMING

We develop a methodological framework and present a few different ways in which dynamic programming and compact representations can be combi ned to solve large scale stochastic control problems. In particular, w e develop algorithms that employ two types of feature-based compact re presentations; that is, representations that involve feature extractio n and a relatively simple approximation architecture. We prove the con vergence of these algorithms and provide bounds on the approximation e rror. As an example, one of these algorithms is used to generate a str ategy for the game of Tetris. Furthermore, we provide a counterexample illustrating the difficulties of integrating compact representations with dynamic programming, which exemplifies the shortcomings of certai n simple approaches.