View in EDS HTML Full Text PDF Full Text

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

Saved in:
Bibliographic Details
Authors: Pakiman, Parshan1 (AUTHOR) ppakim2@uic.edu, Nadarajah, Selvaprabu1 (AUTHOR) selvan@uic.edu, Soheili, Negar1 (AUTHOR) nazad@uic.edu, Lin, Qihang2 (AUTHOR) qihang-lin@uiowa.edu
Source: Management Science (INFORMS). Apr2025, Vol. 71 Issue 4, p3384-3404. 21p.
Subject Terms: *Linear programming, *Markov processes, *Inventory control, *Dynamic programming, Reinforcement learning
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. [ABSTRACT FROM AUTHOR]
Database: Entrepreneurial Studies Source
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: ent
DbLabel: Entrepreneurial Studies Source
An: 184475664
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Pakiman%2C+Parshan%22">Pakiman, Parshan</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> ppakim2@uic.edu</i><br /><searchLink fieldCode="AR" term="%22Nadarajah%2C+Selvaprabu%22">Nadarajah, Selvaprabu</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> selvan@uic.edu</i><br /><searchLink fieldCode="AR" term="%22Soheili%2C+Negar%22">Soheili, Negar</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> nazad@uic.edu</i><br /><searchLink fieldCode="AR" term="%22Lin%2C+Qihang%22">Lin, Qihang</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> qihang-lin@uiowa.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Management+Science+%28INFORMS%29%22">Management Science (INFORMS)</searchLink>. Apr2025, Vol. 71 Issue 4, p3384-3404. 21p.
– Name: Subject
  Label: Subject Terms
  Group: Su
  Data: *<searchLink fieldCode="DE" term="%22Linear+programming%22">Linear programming</searchLink><br />*<searchLink fieldCode="DE" term="%22Markov+processes%22">Markov processes</searchLink><br />*<searchLink fieldCode="DE" term="%22Inventory+control%22">Inventory control</searchLink><br />*<searchLink fieldCode="DE" term="%22Dynamic+programming%22">Dynamic programming</searchLink><br /><searchLink fieldCode="DE" term="%22Reinforcement+learning%22">Reinforcement learning</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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. [ABSTRACT FROM AUTHOR]
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=ent&AN=184475664
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1287/mnsc.2020.00038
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 21
        StartPage: 3384
    Subjects:
      – SubjectFull: Linear programming
        Type: general
      – SubjectFull: Markov processes
        Type: general
      – SubjectFull: Inventory control
        Type: general
      – SubjectFull: Dynamic programming
        Type: general
      – SubjectFull: Reinforcement learning
        Type: general
    Titles:
      – TitleFull: Self-Guided Approximate Linear Programs: Randomized Multi-Shot Approximation of Discounted Cost Markov Decision Processes.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Pakiman, Parshan
      – PersonEntity:
          Name:
            NameFull: Nadarajah, Selvaprabu
      – PersonEntity:
          Name:
            NameFull: Soheili, Negar
      – PersonEntity:
          Name:
            NameFull: Lin, Qihang
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 04
              Text: Apr2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 00251909
          Numbering:
            – Type: volume
              Value: 71
            – Type: issue
              Value: 4
          Titles:
            – TitleFull: Management Science (INFORMS)
              Type: main
ResultId 1