Prendre des décisions optimales sans avoir toutes les cartes en main, 1/2 : la genèse d’un papier scientifique

Publié le 09 mai 2025 par binaire
Prendre des décisions optimales sans avoir toutes les cartes en main, 1/2 : la genèse d’un papier scientifique

Les chercheurs ont toujours du mal à expliquer comment la recherche progresse dans un cadre international, pluridisciplinaire et collaboratif. Nous allons illustrer cela avec la genèse d’un article scientifique « Revelations : A Decidable Class of POMDP with Omega-Regular Objectives ». Cet article a été primé par le « Outstanding Paper Award » à la conférence AAAI 2025, la plus prestigieuse conférence internationale en intelligence artificielle (https://aaai.org/). Quatre des auteurs, Marius Belly, Nathanaël Fijalkow, Hugo Gimbert et Pierre Vandenhove, sont au laboratoire bordelais de recherche en informatique (LaBRI). Ils ont collaboré avec des chercheurs à Paris (Florian Horn) et Anvers (Guillermo Pérez). L’article est consultable librement à l’adresse https://arxiv.org/abs/2412.12063. Les auteurs racontent ici pour binaire l’histoire de ce travail. L’intérêt de l’article est d’observer la recherche en train de se faire. Il n’est pas nécessaire de comprendre même leurs résultats. Dans un second article, ils donneront plus de détails sur les contributions scientifiques. Serge Abiteboul et Chloé Mercier.

La question originale a été posée pendant le workshop « Gamenet » sur la théorie des jeux mêlant informaticiens, mathématiciens et économistes à Maastricht (Pays-Bas) en 2022. Les résultats mathématiques présentés par Guillaume Vigeral et Bruno Ziliotto sur les phénomènes de “révélations” dans les modèles de jeux à information imparfaite ont suscité la curiosité de Hugo et Florian au sujet des propriétés algorithmiques de ces jeux.

Le poker est un exemple classique de jeu à information imparfaite : chaque joueur possède à tout moment une information partielle de la partie, à savoir il connaît sa main et ce que les autres joueurs ont annoncé, mais pas la main des autres joueurs. Les jeux à information imparfaite sont extrêmement durs à comprendre d’un point de vue algorithmique, et l’on peut même prouver que, dans des modèles très simples, ils sont “indécidables”, ce qui signifie qu’il n’existe pas d’algorithme permettant de construire une stratégie optimale. Analyser algorithmiquement les jeux à information imparfaite est un vaste programme de recherche, très actif dans le monde académique mais également dans l’industrie : Google DeepMind s’est par exemple attaqué à StarCraft. Son succès a été mitigé puisque, si l’IA a initialement battu les meilleurs joueurs mondiaux, des stratégies imprévisibles contrant l’IA ont ensuite été découvertes.

Informellement, une “révélation” dans un jeu à information imparfaite correspond à un instant où les joueurs possèdent une connaissance complète de l’état du jeu. Par exemple au poker, lorsque tous les joueurs révèlent leurs cartes. Mais le mécanisme du jeu peut introduire après ce moment à nouveau des incertitudes, par exemple si un joueur pioche une nouvelle carte et ne la révèle pas. A son retour à Bordeaux, Hugo a posé à Nathanaël cette question fascinante : les jeux qui impliquent “régulièrement” des révélations sont-ils plus faciles à analyser d’un point de vue algorithmique ? Intuitivement, la difficulté d’analyser les jeux à information imparfaite est due à la multiplication des possibilités. Mais s’il y a “souvent” des révélations, ce nombre de possibilités devrait être réduit. Nous avons commencé à plancher sur ce sujet à trois : Nathanaël, Hugo, et Florian.

Hugo et Florian ont rendu visite à Nathanaël pendant son année sabbatique à l’Université de Varsovie (en 2023), et l’hiver polonais leur a permis de faire une première découverte : ils ont prouvé que ces jeux n’étaient pas plus faciles à analyser que le cas général. Au lieu d’abandonner, ils ont décidé de se focaliser sur les processus de décisions Markoviens (MDP), cas particulier des jeux où il n’y a qu’un seul joueur. Dans ce nouveau cadre, ils ont formulé des conjectures et conçu un algorithme pour résoudre ces MDP, mais ils n’avaient pas encore de preuve complète.

Encouragé par ces résultats, Hugo a proposé à Marius, alors étudiant en Master, d’effectuer son stage de recherche sur cette question au printemps 2023. Après de longs mois à manipuler des outils probabilistes et topologiques et après deux visites à Paris pour travailler avec Florian, les premières preuves ont été couchées sur papier. Le stage a en particulier permis de formaliser une distinction importante : il a distingué entre deux notions différentes de “révélations”, dites “faible” et “forte”. Malgré les progrès, de nombreuses questions restaient ouvertes.

Pierre a alors commencé un post-doctorat dans l’équipe bordelaise en septembre 2023, peu après la fin du stage de Marius. Il a dévoré son rapport de stage, relançant encore une fois la machine : l’espoir fait vivre et nourrit la recherche. Nous avons alors fait de grands pas en avant, et obtenu des résultats positifs dans le cas de révélations fortes ainsi que des résultats négatifs pour les révélations faibles. Plus précisément, nous avons construit un algorithme permettant d’analyser les jeux avec des révélations fortes, et montré que cela était impossible (indécidable) en cas de révélations faibles. C’est aussi une expérience classique en recherche : lorsque l’on se lance dans un nouveau problème, on commence par faire de tout petits pas. Plus on avance dans la compréhension des objets, et plus on fait de grands pas, jusqu’à résoudre le problème (ou pas). Faire de la recherche, c’est ré-apprendre à marcher à chaque nouveau problème !

Pour valider nos résultats empiriquement, nous avons collaboré avec Guillermo, expert des méthodes statistiques et exactes pour les jeux stochastiques. L’intérêt de l’algorithme que nous avions construit était d’être conceptuellement très simple et facile à implémenter. Il s’est avéré qu’il permet également en pratique de construire des stratégies plus performantes !

Un article de recherche se doit d’être tourné vers le futur, d’ouvrir des pistes. Notre algorithme permet d’analyser les jeux avec des révélations (fortes). Une perspective intéressante est de retourner le problème : on peut se demander plus généralement ce que fait l’algorithme lorsqu’il est utilisé pour n’importe quel jeu, avec ou sans révélations. Cela permet d’envisager d’analyser tous les jeux, même les plus compliqués, mais en restreignant plutôt le type de stratégie que les joueurs utilisent, ou la quantité d’informations qu’ils sont capables de traiter.

Marius Belly, Nathanaël Fijalkow, Hugo Gimbert, Florian Horn, Guillermo A. Pérez et Pierre Vandenhove