Self-guided Approximate Linear Programs

Parshan Pakiman; Selvaprabu Nadarajah; Negar Soheili; Qihang Lin

doi:10.48550/arxiv.2001.02798

Back

Preprint

Open access

Self-guided Approximate Linear Programs

Parshan Pakiman, Selvaprabu Nadarajah, Negar Soheili and Qihang Lin

ArXiv.org

01/08/2020

DOI: 10.48550/arxiv.2001.02798

Files and links (1)

url

https://doi.org/10.48550/arxiv.2001.02798View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

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 these choices are typically heuristic: basis function selection relies on domain knowledge while the state-relevance distribution is specified using the frequency of states visited by a heuristic 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. Self-guided ALPs mitigate the need for domain knowledge during basis function selection as well as the impact of the initial choice of the state-relevance distribution, thus significantly 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.

Details

Title: Subtitle: Self-guided Approximate Linear Programs
Creators: Parshan Pakiman - University of Illinois at Chicago
Selvaprabu Nadarajah - University of Illinois at Chicago
Negar Soheili - University of Illinois at Chicago
Qihang Lin - University of Iowa
Resource Type: Preprint
Publication Details: ArXiv.org
DOI: 10.48550/arxiv.2001.02798
ISSN: 2331-8422
Language: English
Date posted: 01/08/2020
Academic Unit: Business Analytics
Record Identifier: 9984380713702771

Metrics

26 Record Views