Contribution à la résolution des processus de décision markoviens décentralisés

The subject of this thesis is the optimal resolution of decentralized Markov decision processes (DEC-POMDPs). The DEC-POMDP model has been introduced in 2000 and constitutes a formal framework for describing cooperative distributed decision problems under uncertainty. We present a first generalized overview for solving DEC-POMDPs optimally, including game theory, multi-agent planning and reinforcement learning. Our contributions constitute a theoretical approach for building optimal multi-agent systems. Solving DEC-POMDPs can be separated into two categories. If the underlying model of the system is known in advance, the optimal solution can be planned prior execution in a centralized way. We introduce two new planning algorithms. The first one is a point-based multi-agent dynamic programming approach, which constitutes a synthesis of classical multi-agent dynamic programming, and point-based dynamic programming for single-agent POMDPs. Our approach is hence able to concentrate the computational effort on the relevant regions of the policy space. The second approach is an entirely new way of applying heuristic search techniques, such as A*, to decentralized decision problems. We introduce multi-agent A* (MAA*), the first heuristic search algorithm for solving DEC-POMDPs, both over finite and infinite horizons. If the underlying model is not known, an optimal policy can be obtained by a trial-and-error approach based on reinforcement learning methods. We analyse the additional constraints in multi-agent learning vs. planning, before introducing a new multi-agent reinforcement learning algorithm based on mutual notifications of changes in the value function.Nous abordons dans cette thèse la résolution optimale des processus de décision markoviens décentralisés (DEC-POMDPs). Le modèle DEC-POMDP constitue un formalisme théorique pour la description de problèmes de prise de décision distribuée et coopérative, et cette thèse est l'une des premières à proposer des algorithmes exactes de recherche de politiques optimales. Les avancées qui en découlent nous permettent en particulier de proposer un cadre théorique pour la construction des systèmes multi-agents. Nous distinguons deux familles d'approches pour la résolution des DEC-POMDPs. Lorsqu'un modèle a priori est disponible, une solution optimale peut-être obtenue de manière centralisée et hors ligne par un processus de planification. Nous proposons dans ce cadre un nouvel algorithme de programmation dynamique à base de points, synthèse de la programmation dynamique multi-agent et de la programmation dynamique à base de points mono-agent. Il présente l'avantage de concentrer l'effort de calcul dans les régions pertinentes de l'espace des politiques. Nous introduisons aussi et pour la première fois un algorithme de recherche heuristique pour la planification optimale de comportements décentralisés, basé sur la recherche A* du meilleur d'abord. Lorsque le modèle n'est pas connu, la politique globale peut être obtenue par un processus d'essai erreur au sein de chaque agent. Il s'agit alors de l'apprentissage, et plus particulièrement de l'apprentissage par renforcement. Nous analysons les contraintes supplémentaires dans le cas de l'apprentissage multi-agent, et nous introduisons un nouvel algorithme d'apprentissage par renforcement multi-agent par notifications réciproques