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
- Relaxations of Weakly Coupled Stochastic Dynamic Programs
- Relationship between least squares Monte Carlo and approximate linear programming
- Control of diffusions via linear programming
- Shape constraints in economics and operations research
- Network-based approximate linear programming for discrete optimization
- Data-driven optimal control with a relaxed linear program
- Approximate dynamic programming for stochastic linear control problems on compact state spaces
- scientific article; zbMATH DE number 6318818 (Why is no real title available?)
- Approximate dynamic programming via iterated Bellman inequalities
- A Cost-Shaping Linear Program for Average-Cost Approximate Dynamic Programming with Performance Guarantees
- Quadratic approximate dynamic programming for input-affine systems
- On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming
- New approximate dynamic programming algorithms for large-scale undiscounted Markov decision processes and their application to optimize a production and distribution system
- Nonparametric Approximate Dynamic Programming via the Kernel Method
- Approximate linear programming for networks: average cost bounds
- Tetris: A study of randomized constraint sampling
- State partitioning based linear program for stochastic dynamic programs: an invariance property
- A kernel-based approximate dynamic programming approach: theory and application
- A sequential smoothing algorithm with linear computational cost
- Approximate policy iteration: a survey and some new methods
- A linear programming methodology for approximate dynamic programming
- The Linear Programming Approach to Approximate Dynamic Programming
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)
