Local Evaluation of Policies for Discounted Markov Decision Problems
| dc.contributor.advisor | Grötschel, Martin | en |
| dc.contributor.author | Tuchscherer, Andreas | en |
| dc.contributor.grantor | Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften | en |
| dc.date.accepted | 2010-12-08 | |
| dc.date.accessioned | 2015-11-20T20:02:00Z | |
| dc.date.available | 2010-12-15T12:00:00Z | |
| dc.date.issued | 2010-12-15 | |
| dc.date.submitted | 2010-12-15 | |
| dc.description.abstract | Das Bestimmen realistischer Indikatoren für die Güte von Online-Algorithmen für gegebene Online-Optimierungsprobleme ist eine schwierige Aufgabe. Bisher übliche Ansätze, wie die kompetitive Analyse, weisen erhebliche Nachteile auf. Sofern stochastische Informationen über zukünftige Anfragen zur Verfügung stehen, könnten Markov-Entscheidungs-Probleme (MPDs) eine geeignete Alternative darstellen. Da jedoch die Anzahl an Zuständen in MDPs, die aus praktischen Anwendungen hervorgehen, üblicherweise exponentiell in den ursprünglichen Eingabeparametern ist, sind Standardverfahren zur Analyse von Strategien bzw. Online-Algorithmen nicht anwendbar. In dieser Arbeit wird ein neues algorithmisches Verfahren zur lokalen Evaluierung der Güte von Strategien für diskontierte MDPs vorgestellt. Der Ansatz basiert auf einem Spaltengenerierungsalgorithums zur Approximation der gesamten erwarteten diskontierten Kosten einer unbekannten optimalen Strategie, einer gegebenen Strategie oder einer einzelnen Entscheidung. Der Algorithmus bestimmt eine $\varepsilon$-Approximation, indem lediglich ein relativ kleiner lokaler Teil des gesamten Zustandsraumes untersucht wird. Es wird gezeigt, dass die Anzahl der zur Approximation erforderlichen Zustände unabhängig von der Gesamtzahl an Zuständen ist. Die berechneten Approximationen sind normalerweise deutlich besser als die theoretische Schranken, die andere Ansätze liefern. Neben dem Pricing-Problem wird die Struktur der linearen Programme untersucht, die in der Spaltengenerierung auftreten. Darüber hinaus werden verschiedene Erweiterungen des Algorithmus vorgeschlagen und analysiert. Diese zielen darauf ab, gute Approximationen schnell berechnen zu können. Das Potential des Verfahrens wird beispielhaft anhand von diskontierten MDPs untersucht, die aus Online-Optimierungsproblemen hervorgehen. Bei diesen handelt es sich um das Bin-Coloring-Problem, ein Terminvergabe-Problem und ein Aufzugssteuerungs-Problem. Das Verfahren ist zumeist in der Lage, Indikatoren für die Güte von Online-Algorithmen zu bestimmen, die Beobachtungen aus Simulationen deutlich besser widerspiegeln als die kompetitive Analyse. Außerdem lassen sich Schwachstellen der betrachteten Online-Algorithmen aufdecken. Dadurch konnte ein neuer Online-Algorithmus für das Bin-Coloring-Problem entwickelt werden, der auch in Simulationen besser abschneidet als bisher existierende Algorithmen. | de |
| dc.description.abstract | Providing realistic performance indicators of online algorithms for a given online optimization problem is a difficult task in general. Due to significant drawbacks of other concepts like competitive analysis, Markov decision problems (MDPs) may yield an attractive alternative whenever reasonable stochastic information about future requests is available. However, the number of states in MDPs emerging from real applications is usually exponential in the original input parameters. Therefore, the standard methods for analyzing policies, i.e., online algorithms in our context, are infeasible. In this thesis we propose a new computational tool to evaluate the behavior of policies for discounted MDPs locally, i.e., depending on a particular initial state. The method is based on a column generation algorithm for approximating the total expected discounted cost of an unknown optimal policy, a concrete policy, or a single action (which assumes actions at other states to be made according to an optimal policy). The algorithm determines an $\varepsilon$-approximation by inspecting only relatively small local parts of the total state space. We prove that the number of states required for providing the approximation is independent of the total number of states, which underlines the practicability of the algorithm. The approximations obtained by our algorithm are typically much better than the theoretical bounds obtained by other approaches. We investigate the pricing problem and the structure of the linear programs encountered in the column generation. Moreover, we propose and analyze different extensions of the basic algorithm in order to achieve good approximations fast. The potential of our analysis tool is exemplified for discounted MDPs emerging from different online optimization problems, namely online bin coloring, online target date assignment, and online elevator control. The results of the experiments are quite encouraging: our method is mostly capable to provide performance indicators for online algorithms that much better reflect observations made in simulations than competitive analysis does. Moreover, the analysis allows to reveal weaknesses of the considered online algorithms. This way, we developed a new online algorithm for the online bin coloring problem that outperforms existing ones in our analyses and simulations. | en |
| dc.identifier.uri | urn:nbn:de:kobv:83-opus-28752 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/2958 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-2661 | |
| dc.language | English | en |
| dc.language.iso | en | en |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | Gütegarantien | de |
| dc.subject.other | Lineare Optimierung | de |
| dc.subject.other | Markov-Entscheidungs-Probleme | de |
| dc.subject.other | Spaltengenerierung | de |
| dc.subject.other | Column generation | en |
| dc.subject.other | Linear programming | en |
| dc.subject.other | Markov decision problems | en |
| dc.subject.other | Performance guarantees | en |
| dc.title | Local Evaluation of Policies for Discounted Markov Decision Problems | en |
| dc.title.translated | Lokale Evaluierung von Strategien für diskontierte Markov-Entscheidungs-Probleme | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | publishedVersion | en |
| tub.accessrights.dnb | free | * |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.identifier.opus3 | 2875 | |
| tub.identifier.opus4 | 2722 | |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1