Near-Optimal Algorithms for Sequential Information-Gathering Decision Problems

Des algorithmes presque optimaux pour les problèmes de décision séquentielle à des fins de collecte d'information

Mauricio Araya-López (1)

1 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications

The purpose of this dissertation is to study sequential decision problems where acquiring information is an end in itself. More precisely, it first covers the question of how to modify the POMDP formalism to model information-gathering problems and which algorithms to use for solving them. This idea is then extended to reinforcement learning problems where the objective is to actively learn the model of the system. Also, this dissertation proposes a novel Bayesian reinforcement learning algorithm that uses optimistic local transitions to efficiently gather information while optimizing the expected return. Through bibliographic discussions, theoretical results and empirical studies, it is shown that these information-gathering problems are optimally solvable in theory, that the proposed methods are near-optimal solutions, and that these methods offer comparable or better results than reference approaches. Beyond these specific results, this dissertation paves the way (1) for understanding the relationship between information-gathering and optimal policies in sequential decision processes, and (2) for extending the large body of work about system state control to information-gathering problems

Cette thèse s'intéresse à des problèmes de prise de décision séquentielle dans lesquels l'acquisition d'information est une fin en soi. Plus précisément, elle cherche d'abord à savoir comment modifier le formalisme des POMDP pour exprimer des problèmes de collecte d'information et à proposer des algorithmes pour résoudre ces problèmes. Cette approche est alors étendue à des tâches d'apprentissage par renforcement consistant à apprendre activement le modèle d'un système. De plus, cette thèse propose un nouvel algorithme d'apprentissage par renforcement bayésien, lequel utilise des transitions locales optimistes pour recueillir des informations de manière efficace tout en optimisant la performance escomptée. Grâce à une analyse de l'existant, des résultats théoriques et des études empiriques, cette thèse démontre que ces problèmes peuvent être résolus de façon optimale en théorie, que les méthodes proposées sont presque optimales, et que ces méthodes donnent des résultats comparables ou meilleurs que des approches de référence. Au-delà de ces résultats concrets, cette thèse ouvre la voie (1) à une meilleure compréhension de la relation entre la collecte d'informations et les politiques optimales dans les processus de prise de décision séquentielle, et (2) à une extension des très nombreux travaux traitant du contrôle de l'état d'un système à des problèmes de collecte d'informations

Mots clés: Information-Gathering; Optimistic Transitions; POMDP; Bayesian Reinforcement Learning; MDP Model Learning; Sequential Decision Problems; Bayesian Models

Mots clés: Collecte d'informations; Transitions optimistes; Apprentissage par renforcement bayésien; Apprentissage du modèle d'un MDP; Problèmes de prise de décision séquentielle; Modèles bayésiens; Systèmes experts (informatique); Systèmes d'aide à la décision; Statistique bayésienne; Algorithmes optimaux

Domaines: Autre [cs.OH]

Mauricio Araya-López. Near-Optimal Algorithms for Sequential Information-Gathering Decision Problems. Other [cs.OH]. Université de Lorraine, 2013. English. ⟨NNT : 2013LORR0002⟩. ⟨tel-01749452v1⟩