- FR
- EN
Les jeux stochastiques partiellement observables constituent un modèle fondamental pour analyser les interactions stratégiques entre des joueurs disposant d'une information incomplète. Dans le cadre à deux joueurs, nous nous intéressons à la valeur uniforme, c'est-à-dire le gain moyen limite que chaque joueur peut garantir pour des horizons suffisamment grands. De précédents travaux ont montré que cette valeur peut ne pas exister et que, même lorsqu'elle existe, aucun algorithme ne permet de la calculer ou de l'approximer. Pour contourner ce problème, nous introduisons la classe des jeux stochastiques aveugles ergodiques. Nous démontrons que la valeur uniforme existe, que son approximation est décidable, tandis que son calcul demeure indécidable. Nous considérons ensuite le cadre partiellement observable, dans lequel une extension directe de l'ergodicité ne suffit pas à garantir l'existence de la valeur uniforme. En imposant des conditions de Doeblin, nous prouvons que la valeur uniforme existe et que le problème d'approximation est décidable. Dans le cadre à un joueur, c'est-à-dire celui des processus de décision markoviens partiellement observables (POMDPs), nous étudions des objectifs de parité. Pour ces objectifs, les analyses limite-sûre et quantitatives sont généralement indécidables. Nous nous concentrons donc sur les POMDP révélateurs, où chaque état visité est annoncé avec une probabilité strictement positive. Nous montrons que l'analyse limite-sûre est EXPTIME-complète et que l'analyse quantitative peut être réalisée en EXPTIME. Dans le cadre multi-joueurs, nous définissons les notions de monitorabilité et de monitorabilité robuste. Nous observons que, si les chaînes de Markov aveugles sont monitorables, cette propriété disparaît dès qu'un joueur ou des signaux sont ajoutés. Cela nous amène à introduire une condition spécifique, l'atteignabilité approximativement bornée, sous laquelle la monitorabilité est retrouvée. Enfin, nous identifions des conditions suffisantes, l'ergodicité et la primitivité, qui impliquent l'atteignabilité approximativement bornée et garantissent la monitorabilité robuste.
Partially observable stochastic games provide a central model for studying strategic interaction between players under partial observation. We first investigate the uniform value, i.e., a limiting average payoff that both players can guarantee for sufficiently large horizons, in the two-player setting. Prior work showed that the uniform value may fail to exist and that, even when it does, no algorithm may compute or approximate it. We therefore introduce the class of ergodic blind stochastic games and prove that the uniform value exists, its approximation is decidable, while its computation remains undecidable. We then consider the hidden setting, where a direct extension of ergodicity is still insufficient to ensure existence. By considering Doeblin conditions, we prove that the uniform value exists and its approximation problem is decidable. Turning to the one-player setting of partially observable Markov decision processes (POMDPs), we study parity objectives, for which both limit-sure and quantitative analyses are undecidable in general. We consider revealing POMDPs, where each visited state is announced with positive probability. We establish that the limit-sure analysis is EXPTIME-complete and that the quantitative analysis can be achieved in EXPTIME. In the multi-player setting, we introduce the concepts of monitorability and robust monitorability. While blind Markov chains are shown monitorable, this property breaks when adding either a player or signals. This motivates the introduction of a structural condition, termed approximate bounded reachability, under which monitorability is recovered, although robustness may still fail. Finally, we show that classical mixing conditions, namely ergodicity and primitivity, imply approximate bounded reachability and guarantee robust monitorability.
M. Guillaume VIGERAL, Professeur des universités, Université Paris 1 Panthéon-Sorbonne, Directeur de thèse
M. Eilon SOLAN, Professeur, Tel-Aviv University, Rapporteur
M. Stefan KIEFER, Professeur, Oxford University, Rapporteur
M. Bruno ZILIOTTO, Chargé de recherche, Toulouse School of Economics, Directeur de thèse
M. Pierre CARDALIAGUET, Professeur des universités, Université Paris Dauphine-PSL, Examinateur
M. Janos FLESCH, Associate professor, Maastricht University, Examinateur
Mme Patricia BOUYER-DECITRE, Directeur de recherche, Université Paris-Saclay, Examinatrice
M. Stéphane LEGENDRE, NyxAir, Invité
