Discovery of Optimal Solution Horizons in Non-Stationary Markov Decision Processes with Unbounded Rewards

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

34 Downloads (Pure)

Abstract

Infinite-horizon non-stationary Markov decision processes provide a general framework to model many real-life decision-making problems, e.g., planning equipment maintenance. Unfortunately, these problems are notoriously difficult to solve, due to their infinite dimensionality. Often, only the optimality of the initial action is of importance to the decision-maker: once it has been identified, the procedure can be repeated to generate a plan of arbitrary length. The optimal initial action can be identified by finding a time horizon so long that data beyond it has no effect on the initial decision. This horizon is known as a solution horizon and can be discovered by considering a series of truncations of the problem until a stopping rule guaranteeing initial decision optimality is satisfied. We present such a stopping rule for problems with unbounded rewards. Given a candidate policy, the rule uses a mathematical program that searches for other possibly optimal initial actions within the space of feasible truncations. If no better action can be found, the candidate action is deemed optimal. Our rule runs faster than comparable rules and discovers shorter, more efficient solution horizons.
Original languageEnglish
Title of host publicationProceedings of the 29th International Conference on Automated Planning and Scheduling, ICAPS 2019
EditorsJ. Benton, Nir Lipovetzky, Eva Onaindia, David E. Smith, Siddharth Srivastava
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages292-300
Number of pages9
Volume29
ISBN (Electronic)9781577358077
Publication statusPublished - 2019
Event29th International Conference on Automated Planning and Scheduling - Berkeley, United States
Duration: 11 Jul 201915 Jul 2019
Conference number: 29

Publication series

NameProceedings International Conference on Automated Planning and Scheduling, ICAPS
ISSN (Print)2334-0835
ISSN (Electronic)2334-0843

Conference

Conference29th International Conference on Automated Planning and Scheduling
Abbreviated titleICAPS
CountryUnited States
CityBerkeley
Period11/07/1915/07/19

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care

Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Fingerprint

Dive into the research topics of 'Discovery of Optimal Solution Horizons in Non-Stationary Markov Decision Processes with Unbounded Rewards'. Together they form a unique fingerprint.

Cite this