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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/75033 https://orcid.org/0000-0002-5856-9246 |
| _version_ | 1811092581892751360 |
|---|---|
| author | Desai, Vijay V. Farias, Vivek F. Moallemi, Ciamac C. |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Desai, Vijay V. Farias, Vivek F. Moallemi, Ciamac C. |
| author_sort | Desai, Vijay V. |
| collection | MIT |
| description | 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. Our program—the “smoothed approximate linear program”—is distinct from such approaches and relaxes the restriction to lower bounding approximations in an appropriate fashion while remaining computationally tractable. Doing so appears to have several advantages: First, we demonstrate bounds on the quality of approximation to the optimal cost-to-go function afforded by our approach. These bounds are, in general, no worse than those available for extant LP approaches and for specific problem instances can be shown to be arbitrarily stronger. Second, experiments with our approach on a pair of challenging problems (the game of Tetris and a queueing network control problem) show that the approach outperforms the existing LP approach (which has previously been shown to be competitive with several ADP algorithms) by a substantial margin. |
| first_indexed | 2024-09-23T15:20:29Z |
| format | Article |
| id | mit-1721.1/75033 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:20:29Z |
| publishDate | 2012 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/750332022-09-29T14:20:08Z Approximate Dynamic Programming via a Smoothed Linear Program Desai, Vijay V. Farias, Vivek F. Moallemi, Ciamac C. Sloan School of Management Farias, Vivek F. 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. Our program—the “smoothed approximate linear program”—is distinct from such approaches and relaxes the restriction to lower bounding approximations in an appropriate fashion while remaining computationally tractable. Doing so appears to have several advantages: First, we demonstrate bounds on the quality of approximation to the optimal cost-to-go function afforded by our approach. These bounds are, in general, no worse than those available for extant LP approaches and for specific problem instances can be shown to be arbitrarily stronger. Second, experiments with our approach on a pair of challenging problems (the game of Tetris and a queueing network control problem) show that the approach outperforms the existing LP approach (which has previously been shown to be competitive with several ADP algorithms) by a substantial margin. 2012-11-27T17:44:05Z 2012-11-27T17:44:05Z 2012-05 2010-07 Article http://purl.org/eprint/type/JournalArticle http://hdl.handle.net/1721.1/75033 Desai, V. V., V. F. Farias, and C. C. Moallemi. “Approximate Dynamic Programming via a Smoothed Linear Program.” Operations Research 60.3 (2012): 655–674. https://orcid.org/0000-0002-5856-9246 en_US http://dx.doi.org/ 10.1287/opre.1120.1044 Operations Research Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) MIT web domain |
| spellingShingle | Desai, Vijay V. Farias, Vivek F. Moallemi, Ciamac C. Approximate Dynamic Programming via a Smoothed Linear Program |
| title | Approximate Dynamic Programming via a Smoothed Linear Program |
| title_full | Approximate Dynamic Programming via a Smoothed Linear Program |
| title_fullStr | Approximate Dynamic Programming via a Smoothed Linear Program |
| title_full_unstemmed | Approximate Dynamic Programming via a Smoothed Linear Program |
| title_short | Approximate Dynamic Programming via a Smoothed Linear Program |
| title_sort | approximate dynamic programming via a smoothed linear program |
| url | http://hdl.handle.net/1721.1/75033 https://orcid.org/0000-0002-5856-9246 |
| work_keys_str_mv | AT desaivijayv approximatedynamicprogrammingviaasmoothedlinearprogram AT fariasvivekf approximatedynamicprogrammingviaasmoothedlinearprogram AT moallemiciamacc approximatedynamicprogrammingviaasmoothedlinearprogram |