A software laboratory and comparative study of computational methods for Markov decision processes

Persistent Link:
http://hdl.handle.net/10150/290578
Title:
A software laboratory and comparative study of computational methods for Markov decision processes
Author:
Choi, Jongsup, 1956-
Issue Date:
1996
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
Dynamic programming (DP) is one of the most important mathematical programming methods. However, a major limitation in the practical application of DP methods to stochastic decision and control problems has been the explosive computational burden. Significant amounts of research have been focused on improving the speed of convergence and allowing for larger state and action spaces. The principal methods and algorithms of DP are surveyed in this dissertation. The rank-one correction method for value iteration (ROC) recently proposed by Bertsekas was designed to increase the speed of convergence. In this dissertation we have extended the ROC method proposed by Bertsekas to problems with multiple policies. This method is particularly well-suited to systems with substochastic matrices, e.g., those arising in shortest path problems. In order to test, verify, and compare different computational methods we developed a FORTRAN software laboratory for Stochastic s (YS)tems (CO)ntrol and (DE)cision algorithms for discrete time, finite Markov decision processes (SYSCODE). This is a user-friendly, interactive software laboratory. SYSCODE provides the user with a choice of 39 combinations of DP algorithms for testing and 1 comparison. SYSCODE has also been endowed with sophisticated capabilities for random problem data generation. We present a comprehensive computational comparison of many of the algorithms provided by SYSCODE using well-known test problems as well as randomly generated problem data.
Type:
text; Dissertation-Reproduction (electronic)
Keywords:
Engineering, Industrial.; Engineering, System Science.; Operations Research.
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Systems and Industrial Engineering
Degree Grantor:
University of Arizona
Advisor:
Fernandez-Gaucherand, Emmanuel

Full metadata record

DC FieldValue Language
dc.language.isoen_USen_US
dc.titleA software laboratory and comparative study of computational methods for Markov decision processesen_US
dc.creatorChoi, Jongsup, 1956-en_US
dc.contributor.authorChoi, Jongsup, 1956-en_US
dc.date.issued1996en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractDynamic programming (DP) is one of the most important mathematical programming methods. However, a major limitation in the practical application of DP methods to stochastic decision and control problems has been the explosive computational burden. Significant amounts of research have been focused on improving the speed of convergence and allowing for larger state and action spaces. The principal methods and algorithms of DP are surveyed in this dissertation. The rank-one correction method for value iteration (ROC) recently proposed by Bertsekas was designed to increase the speed of convergence. In this dissertation we have extended the ROC method proposed by Bertsekas to problems with multiple policies. This method is particularly well-suited to systems with substochastic matrices, e.g., those arising in shortest path problems. In order to test, verify, and compare different computational methods we developed a FORTRAN software laboratory for Stochastic s (YS)tems (CO)ntrol and (DE)cision algorithms for discrete time, finite Markov decision processes (SYSCODE). This is a user-friendly, interactive software laboratory. SYSCODE provides the user with a choice of 39 combinations of DP algorithms for testing and 1 comparison. SYSCODE has also been endowed with sophisticated capabilities for random problem data generation. We present a comprehensive computational comparison of many of the algorithms provided by SYSCODE using well-known test problems as well as randomly generated problem data.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
dc.subjectEngineering, Industrial.en_US
dc.subjectEngineering, System Science.en_US
dc.subjectOperations Research.en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineSystems and Industrial Engineeringen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorFernandez-Gaucherand, Emmanuelen_US
dc.identifier.proquest9706160en_US
dc.identifier.bibrecord.b34277936en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.