Journal article
Revisiting Approximate Linear Programming: Constraint-Violation Learning with Applications to Inventory Control and Energy Storage
Management science, Vol.66(4), pp.1544-1562
04/2020
DOI: 10.1287/mnsc.2019.3289
Abstract
Approximate linear programs (ALPs) are well-known models for computing value function approximations (VFAs) of intractable Markov decision processes (MDPs). VFAs from ALPs have desirable theoretical properties, define an operating policy, and provide a lower bound on the optimal policy cost. However, solving ALPs near-optimally remains challenging, for example, when approximating MDPs with nonlinear cost functions and transition dynamics or when rich basis functions are required to obtain a good VFA. We address this tension between theory and solvability by proposing a convex saddle-point reformulation of an ALP that includes as primal and dual variables, respectively, a vector of basis function weights and a constraint violation density function over the state-action space. To solve this reformulation, we develop a proximal stochastic mirror descent (PSMD) method that learns regions of high ALP constraint violation via its dual update. We establish that PSMD returns a near-optimal ALP solution and a lower bound on the optimal policy cost in a finite number of iterations with high probability. We numerically compare PSMD with several benchmarks on inventory control and energy storage applications. We find that the PSMD lower bound is tighter than a perfect information bound. In contrast, the constraint-sampling approach to solve ALPs may not provide a lower bound, and applying row generation to tackle ALPs is not computationally viable. PSMD policies outperform problem-specific heuristics and are comparable or better than the policies obtained using constraint sampling. Overall, our ALP reformulation and solution approach broadens the applicability of approximate linear programming.
Details
- Title: Subtitle
- Revisiting Approximate Linear Programming: Constraint-Violation Learning with Applications to Inventory Control and Energy Storage
- Creators
- Qihang Lin - Tippie College of Business, The University of Iowa, Iowa City, Iowa 52242Selvaprabu Nadarajah - College of Business Administration, University of Illinois at Chicago, Chicago, Illinois 60607Negar Soheili - College of Business Administration, University of Illinois at Chicago, Chicago, Illinois 60607
- Resource Type
- Journal article
- Publication Details
- Management science, Vol.66(4), pp.1544-1562
- DOI
- 10.1287/mnsc.2019.3289
- ISSN
- 0025-1909
- eISSN
- 1526-5501
- Language
- English
- Date published
- 04/2020
- Academic Unit
- Business Analytics
- Record Identifier
- 9984066332902771
Metrics
21 Record Views