Approximate Dynamic Programming via a Smoothed Linear Program
From MaRDI portal
Publication:4648262
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 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 substantially 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.
Recommendations
- The Linear Programming Approach to Approximate Dynamic Programming
- A linear programming methodology for approximate dynamic programming
- Approximation of dynamic programs
- Approximate linear programming for average cost MDPs
- Perspectives of approximate dynamic programming
- Approximate dynamic programming by practical examples
- Approximate dynamic programming. Solving the curses of dimensionality
- scientific article; zbMATH DE number 4174799
- Approximate linear programming for first-order MDPs
Cited in
(23)- Approximate linear programming for average cost MDPs
- Shape constraints in economics and operations research
- Data-driven optimal control with a relaxed linear program
- Approximate linear programming for networks: average cost bounds
- Quadratic approximate dynamic programming for input-affine systems
- On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming
- scientific article; zbMATH DE number 6318818 (Why is no real title available?)
- Tetris: A study of randomized constraint sampling
- A kernel-based approximate dynamic programming approach: theory and application
- Relationship between least squares Monte Carlo and approximate linear programming
- Approximate policy iteration: a survey and some new methods
- The Linear Programming Approach to Approximate Dynamic Programming
- A linear programming methodology for approximate dynamic programming
- Nonparametric Approximate Dynamic Programming via the Kernel Method
- A Cost-Shaping Linear Program for Average-Cost Approximate Dynamic Programming with Performance Guarantees
- State partitioning based linear program for stochastic dynamic programs: an invariance property
- Approximate dynamic programming via iterated Bellman inequalities
- Network-based approximate linear programming for discrete optimization
- Relaxations of Weakly Coupled Stochastic Dynamic Programs
- New approximate dynamic programming algorithms for large-scale undiscounted Markov decision processes and their application to optimize a production and distribution system
- Control of diffusions via linear programming
- A sequential smoothing algorithm with linear computational cost
- Approximate dynamic programming for stochastic linear control problems on compact state spaces
This page was built for publication: Approximate Dynamic Programming via a Smoothed Linear Program
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4648262)
