Duality in Markov Decision Problems with Countable Action and State Spaces

John P. Evans
Additional contact information
John P. Evans: The University of Chicago

Management Science, 1969, vol. 15, issue 11, 626-638

Abstract: The recent literature contains several papers which explore mathematical programming formulations of particular Markov sequential decision problems. Each of these papers deals with finite state and action spaces; thus, the corresponding programming formulations yield dual finite linear programs. In this paper these investigations are extended to include countable action and/or state spaces for finite horison problems. Of particular interest are the duality aspects of the mathematical programming formulations. In addition, employing conditions analogous to fundamental concepts of Haar semi-infinite dual programming, we provide sufficient conditions for the existence of optimal rules for countable action spaces. Guided by the semi-infinite duality theory we explore mathematical programming formulations for two cases: 1) Countable action space and finite state space--the result is a pair of dual semi-infinite programs; and 2) Finite action space and countable state space--we obtain a pair of infinite programs. In the latter case we show that no duality gap occurs and obtain duality results comparable to those of finite linear programming.

Date: 1969
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.15.11.626 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:15:y:1969:i:11:p:626-638

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().