913
eng
reportzib
0
2006-04-18
2006-04-18
--
LP-Based Local Approximation for Markov Decision Problems
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.
06-20
914
urn:nbn:de:0297-zib-9131
Stefan Heinz
Volker Kaibel
Matthias Peinhardt
Jörg Rambau
Andreas Tuchscherer
ZIB-Report
06-20
eng
uncontrolled
Markov decision problem
eng
uncontrolled
linear programming
eng
uncontrolled
column generation
Informatik, Informationswissenschaft, allgemeine Werke
Nonnumerical Algorithms and Problems (E.2-5, G.2, H.2-3)
Combinatorics (F.2.2)
Approximation algorithms
Markov and semi-Markov decision processes
ZIB Allgemein
Heinz, Stefan
MATHEON-B14:Comb-Log
https://opus4.kobv.de/opus4-zib/files/913/ZR-06-20.pdf
https://opus4.kobv.de/opus4-zib/files/913/ZR-06-20.ps