Modified monotone policy iteration for interpretable policies in Markov decision processes and the impact of state ordering rules.
Saved in:
| Title: | Modified monotone policy iteration for interpretable policies in Markov decision processes and the impact of state ordering rules. |
|---|---|
| Authors: | Lee, Sun Ju1 (AUTHOR) julee@gatech.edu, Gong, Xingyu1 (AUTHOR) xgong75@gatech.edu, Garcia, Gian-Gabriel1 (AUTHOR) giangarcia@gatech.edu |
| Source: | Annals of Operations Research. Apr2025, Vol. 347 Issue 2, p783-841. 59p. |
| Subjects: | Markov processes, Random sets, Dynamic programming, Algorithms, Integers |
| Abstract: | Optimizing interpretable policies for Markov decision processes (MDPs) can be computationally intractable for large-scale MDPs, e.g., for monotone policies, the optimal interpretable policy depends on the initial state distribution, precluding standard dynamic programming techniques. Previous work has proposed monotone policy iteration (MPI) to produce a feasible solution for warm starting a mixed integer linear program that finds an optimal monotone policy. However, this prior work did not investigate the convergence and optimality of this algorithm, nor did they investigate the impact of state ordering rules, i.e., the order in which policy improvement steps are performed in MPI. In this study, we analytically characterize the convergence and optimality of the MPI algorithm, introduce a modified MPI (MMPI) algorithm, and show that our algorithm improves upon the MPI algorithm. To test MMPI numerically, we conduct experiments in two settings: (1) perturbations of a machine maintenance problem wherein the optimal policy is guaranteed to be monotone or near-monotone and (2) randomly generated MDPs. We propose and investigate 19 state ordering rules for MMPI based on each state's value function, initial probability, and stationary distribution. Computational results reveal a trade-off between computational time and optimality gap; in the structured machine maintenance setting, the fastest state ordering rules still yield high quality policies while the trade-off is more pronounced in the random MDP setting. Across both settings, the random state ordering rule performs the best in terms of optimality gap (less than approximately 5% on average) at the expense of computational time. [ABSTRACT FROM AUTHOR] |
| Copyright of Annals of Operations Research is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 185037601 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Modified monotone policy iteration for interpretable policies in Markov decision processes and the impact of state ordering rules. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Lee%2C+Sun+Ju%22">Lee, Sun Ju</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> julee@gatech.edu</i><br /><searchLink fieldCode="AR" term="%22Gong%2C+Xingyu%22">Gong, Xingyu</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> xgong75@gatech.edu</i><br /><searchLink fieldCode="AR" term="%22Garcia%2C+Gian-Gabriel%22">Garcia, Gian-Gabriel</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> giangarcia@gatech.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Annals+of+Operations+Research%22">Annals of Operations Research</searchLink>. Apr2025, Vol. 347 Issue 2, p783-841. 59p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Markov+processes%22">Markov processes</searchLink><br /><searchLink fieldCode="DE" term="%22Random+sets%22">Random sets</searchLink><br /><searchLink fieldCode="DE" term="%22Dynamic+programming%22">Dynamic programming</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Integers%22">Integers</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Optimizing interpretable policies for Markov decision processes (MDPs) can be computationally intractable for large-scale MDPs, e.g., for monotone policies, the optimal interpretable policy depends on the initial state distribution, precluding standard dynamic programming techniques. Previous work has proposed monotone policy iteration (MPI) to produce a feasible solution for warm starting a mixed integer linear program that finds an optimal monotone policy. However, this prior work did not investigate the convergence and optimality of this algorithm, nor did they investigate the impact of state ordering rules, i.e., the order in which policy improvement steps are performed in MPI. In this study, we analytically characterize the convergence and optimality of the MPI algorithm, introduce a modified MPI (MMPI) algorithm, and show that our algorithm improves upon the MPI algorithm. To test MMPI numerically, we conduct experiments in two settings: (1) perturbations of a machine maintenance problem wherein the optimal policy is guaranteed to be monotone or near-monotone and (2) randomly generated MDPs. We propose and investigate 19 state ordering rules for MMPI based on each state's value function, initial probability, and stationary distribution. Computational results reveal a trade-off between computational time and optimality gap; in the structured machine maintenance setting, the fastest state ordering rules still yield high quality policies while the trade-off is more pronounced in the random MDP setting. Across both settings, the random state ordering rule performs the best in terms of optimality gap (less than approximately 5% on average) at the expense of computational time. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Annals of Operations Research is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=185037601 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10479-024-06158-3 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 59 StartPage: 783 Subjects: – SubjectFull: Markov processes Type: general – SubjectFull: Random sets Type: general – SubjectFull: Dynamic programming Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Integers Type: general Titles: – TitleFull: Modified monotone policy iteration for interpretable policies in Markov decision processes and the impact of state ordering rules. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Lee, Sun Ju – PersonEntity: Name: NameFull: Gong, Xingyu – PersonEntity: Name: NameFull: Garcia, Gian-Gabriel IsPartOfRelationships: – BibEntity: Dates: – D: 15 M: 04 Text: Apr2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 02545330 Numbering: – Type: volume Value: 347 – Type: issue Value: 2 Titles: – TitleFull: Annals of Operations Research Type: main |
| ResultId | 1 |
