🤖 machine learning

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance

Cet article présente le premier résultat positif pour l'apprentissage PAC décentralisé et privé dans les jeux stochastiques à tours avec des objectifs de raggiungibilité en introduisant une généralisation de type théorie des jeux du paramètre de distance conditionnelle attendue afin d'établir des bornes de complexité d'échantillonnage polynomial sans nécessiter d'informations ou d'algorithmes partagés.

Auteurs originaux : Ali Asadi, Krishnendu Chatterjee, Pavol Kebis

Publié 2026-07-17

📖 9 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ali Asadi, Krishnendu Chatterjee, Pavol Kebis

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'apprendre à deux personnages de jeux vidéo rivaux comment jouer à un nouveau jeu de société mystérieux. L'un des personnages, appelons-le « Max », veut atteindre un coffre au trésor le plus rapidement possible. L'autre, « Min », veut l'en empêcher, peut-être en l'entraînant dans un piège ou en le faisant errer en cercles indéfiniment. Ce n'est pas seulement un simple jeu de hasard ; c'est une bataille d'esprit où chaque mouvement change les probabilités. Dans le monde de l'informatique, c'est ce qu'on appelle un « Jeu Stochastique à Ture de Jeu » (Turn-Based Stochastic Game). C'est une façon sophistiquée de décrire une situation où deux adversaires se relaient pour prendre des décisions, mais où le résultat de ces décisions implique un lancer de dés.

Habituellement, quand nous apprenons aux ordinateurs à jouer à des jeux, nous supposons qu'ils peuvent tout voir : les règles, le plateau et ce que l'autre joueur pense. Mais dans le monde réel, les choses sont plus complexes. Souvent, l'ordinateur ne connaît pas du tout les règles ; il doit les apprendre en jouant, en faisant des erreurs et en observant ce qui se passe. C'est ce qu'on appelle l'« Apprentissage par Renforcement » (Reinforcement Learning). Le but est de trouver une stratégie qui soit « Probablement Approximativement Correcte » (PAC). C'est un terme un peu pompeux, mais cela signifie simplement : « Pouvons-nous concevoir une méthode d'apprentissage qui, après un certain temps de pratique raisonnable, trouvera presque certainement une stratégie aussi bonne que la meilleure possible ? »

La partie délicate, c'est que pour certains types d'objectifs — comme « atteindre le trésor éventuellement » — l'apprentissage est mathématiquement impossible si le jeu peut durer éternellement et si les joueurs sont véritablement adverses. Si l'adversaire essaie de vous tromper, il pourrait faire semblant de vous aider à apprendre, pour ensuite révéler un piège plus tard. Ce papier s'attaque à une version spécifique et difficile de ce problème : peut deux joueurs apprendre à bien jouer à ce jeu s'ils ne peuvent pas se parler, ne peuvent pas voir les mouvements de l'autre et ne connaissent pas les règles ?

Le Grand Jeu de Cache-cache avec des Dés

Dans ce papier, les auteurs — Ali Asadi, Krishnendu Chatterjee et Pavol Kebis — relèvent un défi qui ressemble à un paradoxe. Ils veulent apprendre à deux joueurs rivaux, Max et Min, comment jouer à un jeu où Max veut atteindre une cible et Min veut l'en empêcher. Le hic ? Ils jouent dans le noir. Ils ne connaissent pas les règles du plateau, ils ne peuvent pas partager de notes, et ils ne savent même pas ce que fait l'autre joueur à un instant donné.

Dans de nombreuses tentatives précédentes pour résoudre cela, les chercheurs ont fait deux hypothèses importantes et irréalistes. Premièrement, ils supposaient que les joueurs pouvaient partager un « carnet de notes public » où ils écrivaient tout ce qu'ils apprenaient. Deuxièmement, ils supposaient que les joueurs utilisaient exactement le même algorithme d'apprentissage, comme deux étudiants copiant sur le même manuel. Les auteurs de ce papier disent : « Attendez, ce n'est pas ainsi que le monde réel fonctionne. » En réalité, les joueurs ont souvent des informations privées et utilisent des méthodes différentes pour apprendre. Ils voulaient savoir : pouvons-nous toujours apprendre à bien jouer si chacun garde ses propres secrets et utilise son propre cerveau ?

Le Problème du « Jeu de l'Attente »

Pour comprendre pourquoi c'est si difficile, imaginez un jeu où le trésor est caché derrière une porte qui ne s'ouvre qu'une fois tous les millions d'années. Si les joueurs ne font que deviner, ils pourraient attendre éternellement. Dans le monde des mathématiques, c'est ce qu'on appelle un problème d'« horizon infini ». Si le jeu peut durer indéfiniment, et que l'adversaire est assez intelligent pour retarder la fin, vous ne pourrez jamais être sûr si vous apprenez la bonne chose ou si vous attendez simplement un miracle qui pourrait ne jamais arriver.

Les auteurs ont réalisé que pour que l'apprentissage soit possible, ils avaient besoin d'un filet de sécurité. Ils ont introduit un concept appelé la Distance Conditionnelle Attendue (ECD - Expected Conditional Distance). Voyez cela comme un « compteur de patience » pour le jeu. Il mesure : « Si la cible est atteignable, combien de temps faut-il en moyenne pour y arriver ? » Si l'ECD est petit, cela signifie que le jeu ne traîne pas indéfiniment ; le trésor est généralement trouvé relativement vite. Si l'ECD est énorme, cela signifie que le jeu pourrait rester bloqué dans une boucle d'attente incroyablement longue.

Le papier prouve que si ce « compteur de patience » est borné (ce qui signifie que le jeu ne dure pas éternellement), alors l'apprentissage est possible, même dans le noir. Ils ont montré qu'en connaissant ce nombre, vous pouvez effectivement transformer le jeu infini en un jeu fini, comme en coupant le jeu après un certain nombre de mouvements parce que vous savez que le trésor aurait dû être trouvé d'ici là. Il est important de noter que sans une telle hypothèse (comme l'ECD, ou d'autres contraintes similaires trouvées dans la littérature précédente), l'apprentissage est impossible en général pour ces types de jeux. Le papier ne prétend pas que l'ECD est la seule façon, mais c'est la clé spécifique qu'ils ont utilisée pour débloquer le problème dans ce nouveau cadre.

La Recette Secrète : Apprendre par Étapes

Alors, comment enseignent-ils réellement aux joueurs ? Les auteurs ont conçu une paire d'algorithmes d'apprentissage ingénieux (un pour Max, un pour Min) qui fonctionnent comme une équipe d'explorateurs cartographiant une grotte.

L'Expansion de la Carte : Au lieu de simplement penser à « État A » ou « État B », les joueurs imaginent une carte en 3D où la troisième dimension est le « Temps ». Ils décomposent le jeu en paires « État-Étape ». C'est comme dire : « À l'étape 1, je suis dans la cuisine ; à l'étape 2, je suis dans le couloir. » Cela les aide à planifier à rebours depuis la fin.
L'Astuce du « Meilleur Bras » (Best Arm) : À chaque endroit de leur carte, les joueurs doivent choisir une action. Ils utilisent une technique issue d'un domaine appelé « Bandit Learning » (imaginez un joueur de casino essayant de trouver la meilleure machine à sous). Ils testent différents mouvements, voient lequel fonctionne le mieux, et s'y tiennent. Mais ils font cela avec une grande confiance, en s'assurant qu'ils ne sont pas simplement chanceux.
La Boucle d'Exploration : Les joueurs commencent par explorer les parties « inexplorées » de la carte. Ils traitent ces endroits inconnus comme de nouveaux « trésors » à trouver. Une fois qu'ils ont déterminé le meilleur mouvement pour un endroit spécifique, ils marquent cet endroit comme « exploré » et passent à la suite. Ils continuent ainsi, construisant une stratégie étape par étape, jusqu'à ce qu'ils aient un plan pour l'ensemble du jeu.
L'Accord Privé : Voici la magie. Même s'ils ne se parlent jamais, ils suivent tous deux un rythme similaire. Ils continuent de jouer jusqu'à ce qu'ils aient tous deux le sentiment d'avoir suffisamment exploré. Quand aucun des deux joueurs ne trouve de nouveaux points « inexplorés » dans sa propre vue privée, ils signalent tous deux au simulateur de jeu : « Nous avons fini ! Voici notre stratégie. »

Le Résultat : Un Nouveau Type d'Apprentissage

La conclusion principale du papier est un « Oui » retentissant. Ils ont prouvé qu'avec cette méthode, les joueurs peuvent apprendre une stratégie qui est presque parfaite (avec une marge d'erreur infime) avec une haute probabilité de succès. Crucialement, le nombre de fois où ils doivent jouer le jeu (la « complexité d'échantillonnage ») croît de manière polynomiale et gérable. Cela signifie que le temps d'apprentissage n'explose pas vers l'infini ; il reste raisonnable même lorsque le jeu s'agrandit.

C'est un événement majeur car c'est la première fois que quelqu'un démontre que l'on peut apprendre à jouer à ces jeux complexes et adverses dans un cadre décentralisé (pas de cerveau partagé) et privé (pas de notes partagées). Avant cela, on pensait qu'il fallait partager des informations pour apprendre efficacement. Les auteurs ont montré qu'en utilisant le « compteur de patience » (ECD) et une stratégie de planification à rebours ingénieuse, on peut apprendre dans le noir.

Ils ont également clarifié que l'apprentissage de ce type de jeu sans hypothèses supplémentaires (comme la borne ECD) est impossible en général. Si le jeu peut durer éternellement sans limite sur le temps nécessaire pour atteindre la cible, aucun algorithme d'apprentissage ne peut garantir le succès. Le papier est très clair : vous avez besoin de cette borne de temps pour que les mathématiques fonctionnent.

Pourquoi Devriez-vous Vous Y Intéresser ?

Vous pourriez vous demander : « Qui se soucie de deux joueurs lançant des dés dans un jeu théorique ? » Eh bien, cela ne concerne pas seulement les jeux de société. Ce genre de mathématiques est le pilier de la construction d'IA sûres pour des choses comme les voitures autonomes, la sécurité des réseaux et le trading automatisé. Dans ces scénarios réels, différents systèmes (ou hackers) interagissent constamment, souvent sans pleine connaissance de ce que fait l'autre.

Ce papier nous offre une nouvelle boîte à outils. Il nous dit que même si nous ne pouvons pas forcer tous nos agents d'IA à partager leurs secrets, et même s'ils essaient de se surpasser mutuellement, nous pouvons toujours leur apprendre à être intelligents et sûrs, à condition de savoir que les « mauvaises choses » ne se produiront pas après un temps infini. C'est une étape vers la création d'une IA capable de naviguer dans un monde chaotique et incertain sans avoir besoin d'un chef central pour lui dire quoi faire.

En bref, les auteurs ont pris un problème qui semblait impossible — apprendre un jeu dans le noir face à un rival — et ont trouvé un moyen d'allumer la lumière, étape par étape, en utilisant une mesure de patience ingénieuse et beaucoup de réflexion à rebours.

Résumé Technique : Apprentissage PAC dans les Jeux Stochastiques à Tours avec Objectifs de Réachabilité

Énoncé du Problème
L'article traite du problème de l'apprentissage PAC (Probably Approximately Correct) pour les jeux stochastiques à tours (TBSGs - Turn-Based Stochastic Games) avec des objectifs de réachabilité. Dans les TBSGs, deux joueurs adverses (Max et Min) interagissent sur un espace d'états fini avec des transitions stochastiques. L'objectif est pour Max de maximiser, et pour Min de minimiser, la probabilité d'atteindre éventuellement un ensemble d'états cibles.

Les auteurs soulignent un résultat de dureté fondamental : l'apprentissage PAC pour les objectifs de réachabilité est généralement impossible dans les TBSGs (et même dans les processus de décision markoviens - MDP) sans hypothèses supplémentaires. Cette impossibilité découle du fait que la réachabilité est une propriété non bornée, et que le comportement adverse durant la phase d'apprentissage peut rendre l'apprentissage futile (par exemple, un adversaire pourrait choisir une action sous-optimale qui atteint la cible immédiatement, masquant ainsi la véritable stratégie optimale).

Les résultats positifs précédents pour les TBSGs reposaient sur deux hypothèses fortes :

Information Publique : Les deux joueurs partagent toutes les informations (états, actions, transitions).
Apprentissage Centralisé : Les deux joueurs utilisent le même algorithme d'apprentissage.

Ce travail vise à relaxer ces hypothèses pour parvenir à un apprentissage dans un cadre décentralisé où les joueurs utilisent des algorithmes distincts et possèdent des informations privées (spécifiquement, l'état actuel n'est connu que par le joueur possédant cet état).

Méthodologie
L'approche proposée implique une réduction en deux étapes et un nouvel algorithme d'apprentissage :

Généralisation de la Distance Conditionnelle Attendue (ECD - Expected Conditional Distance) :
Les auteurs introduisent une généralisation de la théorie des jeux du paramètre ECD, défini à l'origine pour les MDP.
- Définition : L'ECD d'un jeu est définie comme la suprématie sur toutes les stratégies de Min de l'infimum sur les meilleures réponses de Max de l'espérance du temps pour atteindre la cible, conditionnellement au fait que la cible soit atteinte.
- Justification : Plusieurs généralisations naturelles de l'ECD aux jeux ont été montrées comme défaillantes (par exemple, elles pourraient être faibles même lorsque l'horizon requis pour l'approximation est grand). La définition proposée garantit que si l'ECD est bornée par $L$ , le problème de réachabilité à horizon infini peut être réduit à un problème à horizon fini avec un horizon $H \approx 2(L+1)/\epsilon$ . Ce tronquage convertit le problème insoluble à horizon infini en un problème soluble à horizon fini.
Expansion d'Horizon Fini :
Pour résoudre le problème de réachabilité à horizon fini, les auteurs définissent un jeu expansé $G'$ . Ce jeu déroule l'horizon temporel dans l'espace d'états, créant des paires état-étape $(s, \ell)$ où $\ell$ représente l'étape actuelle. Cette transformation permet l'utilisation de l'induction par l'arrière (backward induction), car le jeu devient équivalent à une structure de type MDP à horizon fini où des stratégies positionnelles sont suffisantes.
Algorithme d'Apprentissage Décentralisé (LeTuReGa) :
L'article présente une paire d'algorithmes, LeTuReGaMax et LeTuReGaMin, conçus pour le cadre décentralisé d'information privée.
- Mécanisme : Les algorithmes opèrent par étapes. À chaque étape, un joueur construit une stratégie par induction par l'arrière de l'horizon $L$ jusqu'à l'étape 0.
- Apprentissage Local : À chaque état-étape $(s, \ell)$ , le joueur emploie une routine d'Identification du Meilleur Bras (BAI - Best-Arm Identification) pour identifier une action $\epsilon$ -optimale avec une grande confiance. Cela évite la nécessité d'estimer l'intégralité des probabilités de transition (ce qui est irréalisable dans des contextes privés) et se concentre directement sur l'identification des actions optimales.
- Exploration : Les algorithmes maintiennent un ensemble d'états-étapes "inexplorés". Ces ensembles inexplorés agissent comme des ensembles cibles auxiliaires pour inciter les joueurs à visiter de nouvelles parties de l'espace état-étape.
- Terminaison : Le processus d'apprentissage se termine lorsque les deux joueurs proposent un profil de stratégie au simulateur, ce qui se produit lorsqu'aucun des deux joueurs ne peut découvrir de nouveaux états-étapes en utilisant sa stratégie actuelle.

Contributions Clés

Apprentissage RL PAC Décentralisé et Privé : Ce travail fournit le premier résultat positif pour l'apprentissage par renforcement (RL) PAC dans les TBSGs sous des conditions décentralisées et d'information privée. Les joueurs ne partagent ni algorithmes ni informations sur les états.
Généralisation de l'ECD : L'article établit une généralisation subtile et correcte du paramètre ECD aux TBSGs, prouvant qu'un ECD borné permet la réduction de la réachabilité à horizon infini vers la réachabilité à horizon fini.
Complexité d'Échantillonnage Polynomiale : Les auteurs établissent une borne de complexité d'échantillonnage polynomiale. La complexité dépend polynomialement du nombre d'états ( $|S|$ ), des actions ( $|A|$ ), du paramètre ECD ( $L$ ), et des inverses de la tolérance d'erreur ( $1/\epsilon$ ) et de la probabilité d'échec ( $1/p$ ).
Conception Algorithmique : L'introduction d'une procédure d'apprentissage qui combine l'induction par l'arrière, l'identification du meilleur bras et l'exploration dynamique des états-étapes sans nécessiter l'estimation des probabilités de transition.

Résultats
Le principal résultat théorique (Corollaire 16) stipule que la paire d'algorithmes (LeTuReGaMax, LeTuReGaMin) est PAC-RL pour les objectifs de réachabilité avec l'hypothèse ECD. La complexité d'échantillonnage est :
$O\left( \frac{|S|^3 L^7 |A| \log(|S|^2 L^2 / (p \epsilon^2))}{\epsilon^{10}} \right)$
où $L$ est la borne sur le paramètre ECD.

La preuve repose sur la démonstration que :

La simulation d'apprentissage se termine en $|S'|$ étapes (où $S'$ est l'ensemble des états expansés).
Avec une haute probabilité, le profil de stratégie construit est $\epsilon$ -optimal pour le jeu à horizon fini.
En raison de la borne ECD, l' $\epsilon$ -optimalité dans le jeu à horizon fini se traduit par une $\epsilon$ -optimalité dans le jeu original à horizon infini.

Signification
L'article revendique sa signification principalement par la relaxation des hypothèses fortes des travaux précédents. Les résultats d'apprentissage PAC précédents pour les TBSGs exigeaient une information publique et un apprentissage centralisé. Ce travail démontre qu'un apprentissage est possible même lorsque les joueurs agissent de manière indépendante et possèdent des informations d'état privées, à condition que le paramètre ECD soit borné. De plus, contrairement aux algorithmes "anytime" précédents pour les TBSGs qui manquaient de garanties de complexité d'échantillonnage, ce travail fournit des bornes polynomiales explicites. Les auteurs notent que c'est le premier résultat positif pour l'apprentissage RL PAC à information privée décentralisée dans les TBSGs avec des objectifs de réachabilité.