EUVIMEDEUVIMED entdecken
Crossref

Self-Guided Approximate Linear Programs: Randomized Multi-Shot Approximation of Discounted Cost Markov Decision Processes

Parshan Pakiman, Selvaprabu Nadarajah, Negar Soheili, Qihang Lin

Management Science · 2025-04 · 71 (4) · 3384-3404

DOI: 10.1287/mnsc.2020.00038 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Management Science, 2025-04. Verfasst von Parshan Pakiman und 3 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 57 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 .

Zitieren

APA

Pakiman, P., Nadarajah, S., Soheili, N., & Lin, Q. (2025). Self-Guided Approximate Linear Programs: Randomized Multi-Shot Approximation of Discounted Cost Markov Decision Processes. Management Science, 71(4), 3384-3404. https://doi.org/10.1287/mnsc.2020.00038

Vancouver

Pakiman P, Nadarajah S, Soheili N, Lin Q. Self-Guided Approximate Linear Programs: Randomized Multi-Shot Approximation of Discounted Cost Markov Decision Processes. Management Science. 2025;71(4):3384-3404. doi:10.1287/mnsc.2020.00038

BibTeX
@article{Pakiman2025,
  author = {Pakiman, Parshan and Nadarajah, Selvaprabu and Soheili, Negar and Lin, Qihang},
  title = {Self-Guided Approximate Linear Programs: Randomized Multi-Shot Approximation of Discounted Cost Markov Decision Processes},
  journal = {Management Science},
  year = {2025},
  volume = {71},
  number = {4},
  pages = {3384--3404},
  doi = {10.1287/mnsc.2020.00038}
}
Kostenlos starten →