Approximate dynamic programming via a smoothed linear program
We present a novel linear program for the approximation of the dynamic programming cost-to-go function in high- dimensional stochastic control problems. LP approaches to approximate DP have typically relied on a natural “projection” of a well-studied linear program for exact dynamic programming. Such programs restrict attention to approximations that are lower bounds to the optimal cost-to-go function.