Local evaluation of policies for discounted Markov decision problems [Elektronische Ressource] / vorgelegt von Andreas Tuchscherer

Local Evaluation of Policiesfor Discounted Markov Decision Problemsvorgelegt vonDipl.-Math. oec. Andreas TuchschererVon der Fakultat II { Mathematik und Naturwissenschaftender Technischen Universitat Berlinzur Erlangung des akademischen GradesDoktor der Naturwissenschaften{ Dr. rer. nat. {genehmigte DissertationBerichter: Prof. Dr. Dr. h.c. mult. Martin GrotschelProf. Dr. Jorg RambauVorsitzender: Prof. Dr. Fredi TroltzschTag der wissenschaftlichen Aussprache: 8. Dezember 2010Berlin 2010D 83ZusammenfassungDas Bestimmen realistischer Indikatoren fur die Gute von Online-Algorith- men fur gegebene Online-Optimierungsprobleme ist eine schwierige Aufga-be. Bisher ubliche Ansatze, wie die kompetitive Analyse, weisen erhebliche Nachteile auf. Sofern stochastische Informationen uber zukunftige Anfragen zur Verfugung stehen, konnten Markov-Entscheidungs-Probleme (MPDs) ei-ne geeignete Alternative darstellen. Da jedoch die Anzahl an Zustanden inMDPs, die aus praktischen Anwendungen hervorgehen, ublicherweise expo-nentiell in den ursprunglichen Eingabeparametern ist, sind Standardverfah-ren zur Analyse von Strategien bzw. Online-Algorithmen nicht anwendbar.In dieser Arbeit wird ein neues algorithmisches Verfahren zur lokalenEvaluierung der Gute von Strategien fur diskontierte MDPs vorgestellt.