Stratégies optimales : des chercheurs primés lors de la prestigieuse conférence AAAI 2025

Trois articles primés pour 12 000 soumis. À la prestigieuse conférence AAAI 2025 – l’une des plus importantes au monde en intelligence artificielle – des chercheurs du LaBRI, de l’IRIF et de l’University of Antwerp ont décroché cet honneur rare. En effet, quatre membres du LaBRI : Marius Belly, ingénieur technicien de l’Université de Bordeaux, Nathanaël Fijalkow et Hugo Gimbert, tous deux chargés de recherche CNRS et Pierre Vandenhove, post-doctorant à l’Université de Bordeaux, ainsi que Florian Horn, chargé de recherche CNRS à l’IRIF et Guillermo A. Pérez, maître de conférence à University of Antwerp ont été distingués pour leur publication en synthèse de programmes dans le cadre de la théorie des jeux.

Tout commence en 2022 lors du workshop européen Gamenet à Maastricht. Économistes, mathématiciens et informaticiens s’y réunissent autour d’un intérêt commun : la théorie des jeux. Alors que les idées fusent, une question émerge : comment modéliser et exploiter les révélations dans les jeux à information imparfaite ? Dans ces derniers, les participants disposent d’une vision partielle des éléments en jeu. Le Cluedo en est un bon exemple : chacun connaît sa main, mais ignore celles des autres ainsi que les trois cartes cachées dans l’enveloppe du crime. Résoudre ces jeux est un casse-tête pour l’intelligence artificielle tant le nombre de possibilités est vertigineux.

« Dans certains cas, on peut même prouver qu’aucun algorithme ne peut garantir de construire une stratégie optimale, précise Nathanaël Fijalkow, responsable de l’équipe. Nous avons donc restreint notre champ d’étude aux processus de décision markoviens ». Ces modèles décrivent des jeux où un joueur prend des décisions successives en fonction d’informations partielles. Encore une fois, le Cluedo illustre bien ce mécanisme : à chaque tour de jeu, le joueur, fort des informations déjà récoltées pose une question à un adversaire, dont la réponse lui révèle une nouvelle information. Selon les cas, cette révélation peut être forte (des indices obtenus régulièrement) ou faible (aucune certitude sur l’arrivée d’un nouvel indice).

C’est sur cette distinction que reposent les avancées récompensées. Les chercheurs ont conçu un algorithme capable d’identifier systématiquement la stratégie optimale lorsque les révélations sont fortes. En revanche, si les révélations sont faibles, le problème demeure aussi insoluble qu’un jeu totalement opaque, empêchant toute résolution exacte.

Traditionnellement, deux grandes familles d’algorithmes traitent ces situations : les méthodes statistiques qui sont efficaces, mais sans garantie absolue sur la qualité des solutions, et les approches exactes qui garantissent une solution optimale, mais au prix d’un coût de calcul élevé. « Notre algorithme appartient à cette seconde catégorie. Nous avons pu démontrer, en le comparant à d’autres méthodes, qu’il était plus performant à ressources égales tout en garantissant une solution optimale », souligne Pierre Vandenhove.

Cette avancée dépasse largement le cadre ludique et s’applique principalement à la synthèse de contrôleurs, où les processus de décision markoviens abondent. Dans l’industrie, de nombreuses applications d’IA doivent prendre des décisions optimales malgré une connaissance imparfaite du système. C’est notamment le cas pour des drones et des robots autonomes, où chaque décision repose sur des informations limitées et évolutives.

Récompensé par les pairs, ce travail illustre le dynamisme de la recherche française en intelligence artificielle. « C’est le fruit d’un effort collectif et au long cours, impliquant des chercheurs confirmés et de jeunes scientifiques. Il met en lumière l’excellence et la vitalité de notre équipe », conclut Hugo Gimbert.