Local Approximation of Discounted Markov Decision Problems by Mathematical Programming Methods

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 ofWe 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.show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS
  • frontdoor_exportcitavi

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Institutes:Mathematik
Author: Stefan Heinz, Jörg Rambau, Andreas Tuchscherer
Contributing Corporation:Zuse-Institut Berlin
Year of Completion:2011
SWD-Keyword:Diskrete Optimierung; Dynamische Optimierung; Lineare Optimierung
Tag:Column Generation; Linear Programming; Markov Decision Problem; Performance Guarantees
Dewey Decimal Classification:510 Mathematik
MSC-Classification:90C05 Linear programming
90C06 Large-scale problems
90C40 Markov and semi-Markov decision processes
URN:urn:nbn:de:bvb:703-opus-8615
Document Type:Preprint
Language:English
Date of Publication (online):24.05.2011