Soutenance de thèse : Aurélien DELAGE

Theoretical foundations of planning in partially observable stochastic games

Doctorant : Aurélien DELAGE

Laboratoire INSA : CITI
École doctorale : ED512 : InfoMaths (Informatique et Mathématiques de Lyon)

Une théorie récente suggère de reformuler les POSG à gain commun en des problèmes non observables via l’introduction d’une statistique suffisante appropriée, ce qui offre des leviers supplémentaires pour rechercher des plans optimaux. Montrer que le principe d’optimalité de Bellman s’applique sur le jeu non-observable permet l’application d’algorithmes efficaces conçus pour les jeux complètement observables (tels que heuristic search value iteration). Les algorithmes exploitant les leviers découverts (par exemple la division des problèmes en sous-problèmes; la généralisation des connaissances entre les sous-problèmes) offrent une garantie de convergence théorique et des résultats compétitifs sur le plan empirique. Cependant, bien que cette approche ait réussi dans des sous-classes de jeux stochastiques partiellement observables à somme nulle et à deux joueurs (zs-POSG), comment l’appliquer dans le cas général reste une question ouverte. De plus, reformuler le problème original en un problème non-observable introduit des problèmes de décision à chaque étape, dont les complexités temporelle et mémorielle deviennent prohibitives pour les jeux de grande envergure. Dans la première contribution de ce manuscrit, nous abordons la première préoccupation et proposons pour la première fois un solveur de type heuristic search value iteration dont nous démontrons qu’il converge vers une solution ε-optimale en temps fini pour n’importe quel zs-POSG. Cela ouvre la voie à une nouvelle famille d’approches prometteuses et complémentaires à celles reposant sur la programmation linéaire ou les méthodes itératives. Dans une deuxième contribution de ce manuscrit, nous examinons des jeux impliquant n joueurs et en supposant (i) qu’ils partagent tous la même fonction de récompense et (ii) que les joueurs sont organisés selon une structure de connaissance hiérarchique (c.-à-d. chaque agent sait ce que son subordonné sait, et ainsi de suite). Nous montrons qu’une spécialisation du schéma algorithmique point-based value iteration tire efficacement parti des leviers offerts par cette sous-classe. Ce travail ouvre la voie à de multiples extensions de la structure hiérarchique proposée tout en conservant le passage à l’échelle du schéma algorithmique proposé. Dans la dernière contribution de ce manuscrit, nous présentons une contribution connexe, bien qu’annexe, aux problèmes d’optimisation min-max avec des propriétés de continuité faibles.