Header menu link for other important links
X
A smoothed approximate linear program
, Farias V.F., Moallemi C.C.
Published in
2009
Pages: 459 - 467
Abstract
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 naturally restrict attention to approximations that are lower bounds to the optimal cost-to-go function. Our program - the 'smoothed approximate linear program' - relaxes this restriction in an appropriate fashion while remaining computationally tractable. Doing so appears to have several advantages: First, we demonstrate superior bounds on the quality of approximation to the optimal cost-to-go function afforded by our approach. Second, experiments with our approach on a challenging problem (the game of Tetris) show that the approach outperforms the existing LP approach (which has previously been shown to be competitive with several ADP algorithms) by an order of magnitude.
About the journal
JournalAdvances in Neural Information Processing Systems
Open AccessNo