This dissertation is set in the context of a widely used framework for formalizing autonomous decision-making, namely Markov decision processes (MDPs). One of the key problems that arise in MDPs is that of evaluating a decision-making strategy, typically called a policy. It is often the case that data collected under the policy one wishes to evaluate is difficult or even impossible to obtain. In this case, data collected under some other policy needs to be used, a setting known as off-policy evaluation. The main goal of this dissertation is to offer new insights into the properties of methods for off-policy evaluation. This is achieved through a series of novel theoretical results and empirical illustrations. The first set of results concerns the bandit setting (single state, single decision step MDPs). In this basic setting, the bias and variance of various off-policy estimators can be computed in closed form without resorting to approximations. We also compare the bias-variance trade-offs for the different estimators, both theoretically and empirically. In the sequential setting (more than one decision step), a comparative empirical study of different off-policy estimators for MDPs with discrete state and action spaces is conducted. The methods compared include three existing estimators, and two new ones proposed in this dissertation. All of these estimators are shown to be consistent and asymptotically normal. The empirical study illustrates how the relative behaviour of the estimators is affected by changes in problem parameters. The analysis for discrete MDPs is completed by recursive bias and variance formulas for the commonly used model-based estimator. These are the first analytic formulas for finite-horizon MDPs, and are shown to produce more accurate results than bootstrap estimates. The final contribution consists of introducing a new framework for bounding the return of a policy. The framework can be used whenever bounds on the next state and reward are available, regardless of whether the state and action spaces are discrete or continuous. If the next-state bounds are computed by assuming Lipschitz continuity of the transition function and using a batch of sampled transitions, then our framework can lead to tighter bounds than those proposed in previous work. Throughout this dissertation, the empirical performance of the estimators being studied is illustrated on several computational sustainability problems: a model of food-related greenhouse gas emissions, a mallard population dynamics model, and a fishery management domain. / Cette thèse se situe dans le contexte d'un cadre largement utilisé pour formaliser les méchanismes autonomes de décision, à savoir les processus de décision markoviens (MDP). L'un des principaux problèmes qui se posent dans les MDP est celui de l'évaluation d'une stratégie de prise de décision, généralement appelée une politique. C'est souvent le cas qu'obtenir des données recueillies dans le cadre de la politique qu'on souhaite évaluer est difficile, ou même impossible. Dans ce cas, des données recueillies sous une autre politique doivent être utilisées, une situation appelée "évaluation hors-politique". L'objectif principal de cette thèse est de proposer un nouvel éclairage sur les propriétés des méthodes pour l'évaluation hors-politique. Ce résultat est obtenu grâce à une série de nouveaux résultats théoriques et illustrations empiriques. La première série de résultats concerne des problèmes de type bandit (des MDP avec un seul état et une seule étape de décision). Dans cette configuration, le biais et la variance de divers estimateurs hors-politique peuvent être calculés sous forme fermée sans avoir recours à des approximations. Nous comparons également le compromis biais-variance pour les différents estimateurs, du point de vue théorique et empirique. Dans le cadre séquentiel (plus d'une étape de décision), une étude empirique comparative des différents estimateurs hors-politique pour les MDP avec des états et des actions discrètes est menée. Les méthodes comparées sont trois estimateurs existants, ainsi que deux nouveaux proposés dans cette thèse. Tous ces estimateurs se sont avérés convergents et asymptotiquement normaux. L'étude empirique montre comment le comportement relatif des estimateurs est affecté par des changements aux paramètres du problème. L'analyse des MDP discrets est complétée par des formules récursives pour le biais et la variance pour l'estimateur basé sur le modèle. Ce sont les premières formules analytiques pour les MDP à horizon fini, et on montre qu'ils produisent des résultats plus précis que les estimations "bootstrap".La contribution finale consiste à introduire un nouveau cadre pour délimiter le retour d'une politique. Le cadre peut être utilisé chaque fois que des bornes sur le prochain état et la récompense sont disponibles, indépendamment du fait que les espaces d'état et d'action soient discrètes ou continues. Si les limites du prochain état sont calculées en supposant la continuité Lipschitz de la fonction de transition et en utilisant un échantillon de transitions, notre cadre peut conduire à des bornes plus strictes que celles qui sont proposées dans des travaux antérieurs.Tout au long de cette thèse, la performance empirique des estimateurs étudiés est illustrée sur plusieurs problèmes de durabilité: un modèle de calcul des émissions de gaz à effet de serre associées à la consommation de nourriture, un modèle dynamique de la population des mallards, et un domaine de gestion de la pêche.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.117008 |
| Date | January 2013 |
| Creators | Paduraru, Cosmin |
| Contributors | Doina Precup (Supervisor1), Joelle Pineau (Supervisor2) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0088 seconds