Suche nach Personen

plus im Publikationsserver
plus bei Google Scholar

Bibliografische Daten exportieren
 

Local Approximation of Discounted Markov Decision Problems by Mathematical Programming Methods

URN zum Zitieren der Version auf EPub Bayreuth: urn:nbn:de:bvb:703-opus-8615

Titelangaben

Heinz, Stefan ; Rambau, Jörg ; Tuchscherer, Andreas:
Local Approximation of Discounted Markov Decision Problems by Mathematical Programming Methods.
Bayreuth , 2011

Volltext

[thumbnail of Policy_LocalEvaluation_Foundations.pdf]
Format: PDF
Name: Policy_LocalEvaluation_Foundations.pdf
Version: Veröffentlichte Version
Verfügbar mit der Lizenz Creative Commons BY 3.0: Namensnennung
Download (338kB)

Abstract

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.

Weitere Angaben

Publikationsform: Preprint, Postprint
Zusätzliche Informationen (öffentlich sichtbar): msc: 90C05; msc: 90C06; msc: 90C40
Keywords: Lineare Optimierung; Diskrete Optimierung; Dynamische Optimierung; Markov Decision Problem; Linear Programming; Column Generation; Performance Guarantees
Themengebiete aus DDC: 500 Naturwissenschaften und Mathematik > 510 Mathematik
Institutionen der Universität: Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut
Fakultäten
Fakultäten > Fakultät für Mathematik, Physik und Informatik
Sprache: Englisch
Titel an der UBT entstanden: Ja
URN: urn:nbn:de:bvb:703-opus-8615
Eingestellt am: 25 Apr 2014 08:32
Letzte Änderung: 28 Mrz 2019 10:10
URI: https://epub.uni-bayreuth.de/id/eprint/345

Downloads

Downloads pro Monat im letzten Jahr