Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 10 von 24
Zurück zur Trefferliste

LP-Based Local Approximation for Markov Decision Problems

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-9131
  • 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.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Stefan Heinz, Volker Kaibel, Matthias Peinhardt, Jörg Rambau, Andreas Tuchscherer
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:Markov decision problem; column generation; linear programming
MSC-Klassifikation:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Wxx Algorithms (For numerical algorithms, see 65-XX; for combinatorics and graph theory, see 05C85, 68Rxx) / 68W25 Approximation algorithms
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C40 Markov and semi-Markov decision processes
CCS-Klassifikation:F. Theory of Computation / F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY (B.6-7, F.1.3) / F.2.2 Nonnumerical Algorithms and Problems (E.2-5, G.2, H.2-3)
G. Mathematics of Computing / G.2 DISCRETE MATHEMATICS / G.2.1 Combinatorics (F.2.2)
Datum der Erstveröffentlichung:18.04.2006
Schriftenreihe (Bandnummer):ZIB-Report (06-20)
ZIB-Reportnummer:06-20
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.