Journal article
Self-Guided Approximate Linear Programs: Randomized Multi-Shot Approximation of Discounted Cost Markov Decision Processes
Management science, Vol.71(4), pp.3384-3404
04/2025
DOI: 10.1287/mnsc.2020.00038
Abstract
Approximate linear programs (ALPs) are well-known models based on value function approximations (VFAs) to obtain policies and lower bounds on the optimal policy cost of discounted-cost Markov decision processes (MDPs). Formulating an ALP requires (i) basis functions, the linear combination of which defines the VFA, and (ii) a state-relevance distribution, which determines the relative importance of different states in the ALP objective for the purpose of minimizing VFA error. Both of these choices are typically heuristic; basis function selection relies on domain knowledge, whereas the state-relevance distribution is specified using the frequency of states visited by a baseline policy. We propose a self-guided sequence of ALPs that embeds random basis functions obtained via inexpensive sampling and uses the known VFA from the previous iteration to guide VFA computation in the current iteration. In other words, this sequence takes multiple shots at randomly approximating the MDP value function with VFA-based guidance between consecutive approximation attempts. Self-guided ALPs mitigate domain knowledge during basis function selection and the impact of the state-relevance-distribution choice, thus reducing the ALP implementation burden. We establish high-probability error bounds on the VFAs from this sequence and show that a worst-case measure of policy performance is improved. We find that these favorable implementation and theoretical properties translate to encouraging numerical results on perishable inventory control and options pricing applications, where self-guided ALP policies improve upon policies from problem-specific methods. More broadly, our research takes a meaningful step toward application-agnostic policies and bounds for MDPs. This paper was accepted by Chung Piaw Teo, optimization. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2020.00038 .
Details
- Title: Subtitle
- Self-Guided Approximate Linear Programs: Randomized Multi-Shot Approximation of Discounted Cost Markov Decision Processes
- Creators
- Parshan Pakiman - University of Illinois ChicagoSelvaprabu Nadarajah - University of Illinois ChicagoNegar Soheili - University of Illinois ChicagoQihang Lin - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Management science, Vol.71(4), pp.3384-3404
- DOI
- 10.1287/mnsc.2020.00038
- ISSN
- 0025-1909
- eISSN
- 1526-5501
- Language
- English
- Electronic publication date
- 07/23/2024
- Date published
- 04/2025
- Academic Unit
- Business Analytics
- Record Identifier
- 9984688444102771
Metrics
5 Record Views