Aspects algorithmiques dans les jeux stochastiques partiellement observables
17/04/2026 à 15h00
M. David LURIE présente ses travaux en soutenance le 17/04/2026 à 15h00
À l'adresse suivante : Place du Maréchal de Lattre de Tassigny, 75016 Paris Salle des thèses - D520
En vue de l'obtention du diplôme : Doctorat en Sciences
La soutenance est publique
Titre des travaux
Aspects algorithmiques dans les jeux stochastiques partiellement observables
École doctorale
École doctorale Dauphine SDOSE
Équipe de recherche
UMR 7534 - Centre de Recherche en Mathématiques de la Décision
Section CNU
1 - Mathematiques et leurs interactions
Directeur(s)
Guillaume VIGERAL
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. Guillaume VIGERAL | Professeur des universités | Université Paris 1 Panthéon-Sorbonne | Directeur de these |
| 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 these |
| M. Pierre CARDALIAGUET | Professeur des universités | Université Paris-Dauphine | Examinateur |
| M. Janos FLESCH | Associate professor | Maastricht University | Examinateur |
| Mme Patricia BOUYER-DECITRE | Directeur de recherche | Université Paris-Saclay | Examinateur |
Résumé
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.