A linear programming approach to constrained nonstationary infinite-horizon Markov decision processes
dc.contributor.author | Lee, Ilbin | |
dc.contributor.author | Epelman, Marina A | |
dc.contributor.author | Romeijn, H. Edwin | |
dc.contributor.author | Smith, Robert L | |
dc.date.accessioned | 2014-12-20T22:26:36Z | |
dc.date.available | 2014-12-20T22:26:36Z | |
dc.date.issued | 2013-03-06 | |
dc.identifier.uri | https://hdl.handle.net/2027.42/109729 | |
dc.description.abstract | Constrained Markov decision processes (MDPs) are MDPs optimizing an objective function while satisfying additional constraints. We study a class of infinite-horizon constrained MDPs with nonstationary problem data, finite state space, and discounted cost criterion. This problem can equivalently be formulated as a countably infinite linear program (CILP), i.e., a linear program (LP) with a countably infinite number of variables and constraints. Unlike finite LPs, CILPs can fail to satisfy useful theoretical properties such as duality, and to date there does not exist a general solution method for such problems. Specifically, the characterization of extreme points as basic feasible solutions in finite LPs does not extend to general CILPs. In this paper, we provide duality results and a complete characterization of extreme points of the CILP formulation of constrained nonstationary MDPs with finite state space, and illustrate the characterization for special cases. As a corollary, we obtain the existence of a K-randomized optimal policy, where K is the number of constraints. | en_US |
dc.description.sponsorship | National Science Foundation grant CMMI-1333260 and CMMI-0926508 | en_US |
dc.language.iso | en_US | en_US |
dc.relation.ispartofseries | Industrial and Operation Engineering Technical Report 13-01 | en_US |
dc.title | A linear programming approach to constrained nonstationary infinite-horizon Markov decision processes | en_US |
dc.type | Technical Report | en_US |
dc.subject.hlbsecondlevel | Industrial and Operations Engineering | |
dc.subject.hlbtoplevel | Engineering | |
dc.contributor.affiliationumcampus | Ann Arbor | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/109729/1/TR13-01.pdf | |
dc.identifier.source | Technical Report | en_US |
dc.owningcollname | Industrial and Operations Engineering, Department of (IOE) |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.