TY - GEN
A1 - Heinz, Stefan
A1 - Kaibel, Volker
A1 - Peinhardt, Matthias
A1 - Rambau, Jörg
A1 - Tuchscherer, Andreas
T1 - LP-Based Local Approximation for Markov Decision Problems
N2 - The standard computational methods for computing the optimal value functions of Markov Decision Problems (MDP) require the exploration of the entire state space. This is practically infeasible for applications with huge numbers of states as they arise, e.\,g., from modeling the decisions in online optimization problems by MDPs. Exploiting column generation techniques, we propose and apply an LP-based method to determine an $\varepsilon$-approximation of the optimal value function at a given state by inspecting only states in a small neighborhood. In the context of online optimization problems, we use these methods in order to evaluate the quality of concrete policies with respect to given initial states. Moreover, the tools can also be used to obtain evidence of the impact of single decisions. This way, they can be utilized in the design of policies.
T3 - ZIB-Report - 06-20
KW - Markov decision problem
KW - linear programming
KW - column generation
Y1 - 2006
UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/913
UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-9131
ER -