TY - INPR
A1 - Heinz, Stefan
A1 - Rambau, Jörg
A1 - Tuchscherer, Andreas
T1 - Local Approximation of Discounted Markov Decision Problems by Mathematical Programming Methods
N2 - 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.
KW - Lineare Optimierung
KW - Diskrete Optimierung
KW - Dynamische Optimierung
KW - Markov Decision Problem
KW - Linear Programming
KW - Column Generation
KW - Performance Guarantees
Y1 - 2011
UR - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:703-opus-8615
UR - http://opus4.kobv.de/opus4-ubbayreuth/frontdoor/index/index/docId/678
ER -