Titlebar

Export bibliographic data
Literature by the same author
plus on the publication server
plus at Google Scholar

 

Local Approximation of Discounted Markov Decision Problems by Mathematical Programming Methods

URN to cite this document: urn:nbn:de:bvb:703-opus-8615

Title data

Heinz, Stefan ; Rambau, Jörg ; Tuchscherer, Andreas:
Local Approximation of Discounted Markov Decision Problems by Mathematical Programming Methods.
Bayreuth , 2011

[img] PDF
Policy_LocalEvaluation_Foundations.pdf - Published Version
Available under License Creative Commons BY 3.0: Attribution .

Download (338kB)

Abstract

We develop a method to approximate the value vector of discounted Markov decision problems (MDP) with guaranteed error bounds. It is based on the linear programming characterization of the optimal expected cost. The new idea is to use column generation to dynamically generate only such states that are most relevant for the bounds by incorporating the reduced cost information. The number of states that is sufficient in general and necessary in the worst case to prove such bounds is independent of the cardinality of the state space. Still, in many instances, the column generation algorithm can prove bounds using much fewer states. In this paper, we explain the foundations of the method. Moreover, the method is used to improve the well-known nearest-neighbor policy for the elevator control problem.

Further data

Item Type: Preprint, postprint
Additional notes (visible to public): msc: 90C05; msc: 90C06; msc: 90C40
Keywords: Lineare Optimierung; Diskrete Optimierung; Dynamische Optimierung; Markov Decision Problem; Linear Programming; Column Generation; Performance Guarantees
DDC Subjects: 500 Science > 510 Mathematics
Institutions of the University: Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics
Faculties
Faculties > Faculty of Mathematics, Physics und Computer Science
Language: English
Originates at UBT: Yes
URN: urn:nbn:de:bvb:703-opus-8615
Date Deposited: 25 Apr 2014 08:32
Last Modified: 28 Mar 2019 10:10
URI: https://epub.uni-bayreuth.de/id/eprint/345

Downloads

Downloads per month over past year