Approximate Dynamic Programming via Linear Programming

The curse of dimensionality gives rise to prohibitive computational requirements that render infeasible the exact solution of large- scale stochastic control problems. We study an efficient method based on linear programming for approximating solutions to such prob(cid:173) lems. The approach "fits" a linear combination of pre- selected basis functions to the dynamic programming cost- to- go function. We develop bounds on the approximation error and present experi(cid:173) mental results in the domain of queueing network control, providing empirical support for the methodology.