Eliciting preferences sequentially using partially observable Markov decision processes

Decision Support systems have been gaining in importance recently. Yet one of the bottlenecks of designing such systems lies in understanding how the user values different decision outcomes, or more simply what the user preferences are. Preference elicitation promises to remove the guess work of designing decision making agents by providing more formal methods for measuring the `goodness' of outcomes. This thesis aims to address some of the challenges of preference elicitation such as the high dimensionality of the underlying problem. The problem is formulated as a partially observable Markov decision process (POMDP) using a factored representation to take advantage of the structure inherent to preference elicitation problems. Moreover, simple preference knowledge on problem attributes are used to acquire more accurate preferences without increasing the burden on the user. Sparse terminal actions are defined to allow a flexible trade-off between speed and accuracy of the elicited preference function. Empirical simulations are used to validate the proposed methodology. The result is a framework that is flexible enough to be applied to a wide range of domains that addresses some of the challenges facing preference elicitation methodsLes systèmes d'aide à la décision ont gagné en importance récemment. Pourtant, un des problèmes importants liés au design de tels systèmes demeure: comprendre comment l'usager évalue les différents résultats, ou plus simplement, déterminer quelles sont ses préférences. L'extraction des préférences vise à éliminer certains aspects arbitraires du design d'agents de décision en offrant des méthodes plus formelles pour mesurer la qualité des résultats. Cette thèse tente de résoudre certains problèmes ayant trait à l'extraction des préférences, tel que celui de la haute dimensionnalité du problème sous-jacent. Le problème est formulé en tant que processus de décision markovien partiellement observable (POMDP), et utilise une représentation factorisée afin de profiter de la structure inhérente aux problèmes d'extraction des préférences. De plus, des connaissances simples quant aux caractéristiques de ces problèmes sont exploitées afin d'obtenir des préférences plus précises, sans pour autant augmenter la tâche de l'usager. Les actions terminales "sparse" sont définies de manière à permettre un compromis flexible entre vitesse et précision. Le résultat est un système assez flexible pour être appliqué à un grand nombre de domaines qui ont à faire face aux problèmes liés aux méthodes d'extraction des préférences