A Linear Programming Approach to Approximate Dynamic Programming

Ben Van Roy, Stanford Unversity:

Thursday, February 20, 2003, 4:30 PM, Princeton University, Friend Center 006

The curse of dimensionality gives rise to prohibitive computational requirements that render infeasible the exact solution of large-scale stochastic control problems. I will discuss an approach to approximating dynamic programming value functions based on a linear programming formulation. The approach ``fits'' a linear combination of pre-selected basis functions to the dynamic programming cost-to-go function. I will present some theoretical results on the approach and experimental results involving queueing problems and the game of Tetris.