Les chercheurs d'Amii à NeurIPS 2023

La trente-septième édition annuelle de Systèmes de traitement de l'information neuronale (NeurIPS) débute cette semaine à la Nouvelle-Orléans, et Amii est fier de partager certaines des recherches que nos boursiers, les chaires CIFAR d'IA du Canada et les étudiants affiliés présentent à l'événement de cette année.

Lancée en 1987, NeurIPS est devenue une conférence de premier plan sur l'apprentissage automatique et les neurosciences cognitives. Chaque année, elle attire des chercheurs de nombreuses disciplines différentes, dont la théorie de l'information, la vision par ordinateur et la linguistique.

Vous trouverez ci-dessous 16 articles co-rédigés par les boursiers Amii, Canada CIFAR et des chercheurs en début de carrière qui ont été acceptés à NeurIPS.

Vous souhaitez être tenu au courant des dernières recherches de la communauté Amii ? Inscrivez-vous à notre lettre d'information mensuelle!

Apprentissage par renforcement général de Munchausen avec la divergence de Tsallis Kullback-Leibler

*Lingwei Zhu, Zheng Chen, *Matthew Schlegel, *Martha White

Résumé :
De nombreuses approches d'optimisation des politiques d'apprentissage par renforcement intègrent une divergence de Kullback-Leilbler (KL) par rapport à la politique précédente, afin d'éviter que la politique ne change trop rapidement. Cette idée a été initialement proposée dans un article fondateur sur l'itération conservatrice de la politique, avec des approximations données par des algorithmes comme TRPO et l'itération de la valeur de Munchausen (MVI). Nous poursuivons cette ligne de travail en étudiant une divergence KL généralisée, appelée divergence KL de Tsallis. La KL de Tsallis définie par le logarithme q est une généralisation stricte, car q = 1 correspond à la divergence KL standard ; q > 1 offre un éventail de nouvelles options. Nous caractérisons les types de politiques apprises dans le cadre de la KL de Tsallis et expliquons quand q > 1 pourrait être bénéfique. Pour obtenir un algorithme pratique qui intègre la régularisation KL de Tsallis, nous étendons le MVI, qui est l'une des approches les plus simples pour intégrer la régularisation KL. Nous montrons que ce MVI(q) généralisé permet d'obtenir des améliorations significatives par rapport au MVI(q = 1) standard sur 35 jeux Atari.

Configuration de l'algorithme utilitaire

Devon Graham, *Kevin Leyton-BrownTim Roughgarden

Résumé :

Nous présentons la première procédure non triviale pour configurer les algorithmes heuristiques afin de maximiser l'utilité fournie à leurs utilisateurs finaux tout en offrant des garanties théoriques sur la performance. Les procédures existantes recherchent des configurations qui minimisent la durée d'exécution prévue. Cependant, des travaux théoriques très récents soutiennent que la minimisation de la durée d'exécution attendue ne tient pas compte des préférences des concepteurs d'algorithmes. Nous montrons ici que l'objectif utilitaire confère également des avantages algorithmiques significatifs. Intuitivement, cela s'explique par le fait que la durée d'exécution moyenne est dominée par des exécutions extrêmement longues, même lorsqu'elles sont incroyablement rares ; en effet, même lorsqu'un algorithme ne donne jamais lieu à de telles exécutions longues, les procédures de configuration qui minimisent de manière prouvée la durée d'exécution moyenne doivent réaliser un très grand nombre d'expériences pour démontrer ce fait. En revanche, l'utilité est limitée et décroît de façon monotone en fonction de la durée d'exécution, ce qui permet d'établir des limites empiriques significatives sur les performances d'une configuration. Cet article s'appuie sur cette idée pour décrire des procédures de configuration efficaces et solides d'un point de vue théorique. Nous prouvons des limites supérieures sur la durée d'exécution de ces procédures qui sont similaires aux limites inférieures théoriques, tout en démontrant leur performance de manière empirique.

Ne soyez pas si monotone : Relaxer la recherche stochastique de lignes dans les modèles sur-paramétrés

Leonardo Galli, Holger Rauhut, *Mark Schmidt

Résumé :

Des travaux récents ont montré que les méthodes de recherche linéaire peuvent accélérer la descente stochastique du gradient (SGD) et Adam dans des contextes modernes sur-paramétrés. Cependant, les recherches linéaires existantes peuvent prendre des mesures qui sont plus petites que nécessaire puisqu'elles exigent une diminution monotone de la fonction objective (mini-)batch. Nous explorons des méthodes de recherche linéaire non monotone pour assouplir cette condition et éventuellement accepter des pas plus importants. Malgré l'absence de diminution monotone, nous prouvons que les taux de convergence sont aussi rapides que dans le cas monotone. Nos expériences montrent que les méthodes non monotones améliorent la vitesse de convergence et les propriétés de généralisation de SGD/Adam, même au-delà des recherches linéaires monotones précédentes. Nous proposons une méthode POlyak NOnmonotone Stochastique (PoNoS), obtenue en combinant une recherche linéaire non monotone avec une taille de pas initial Polyak. En outre, nous développons une nouvelle technique de réinitialisation qui, dans la majorité des itérations, réduit le nombre de retours en arrière à zéro tout en conservant une taille de pas initiale importante. À notre connaissance, une première comparaison du temps d'exécution montre que l'avantage des méthodes basées sur la recherche linéaire se reflète dans le temps de calcul global.

Recherche de tailles de pas optimales par coordonnée à l'aide d'un backtracking multidimensionnel

Frederik Kunstner, Victor Sanches Portella, *Mark SchmidtNicholas Harvey

Résumé :

La taille du pas de recul est une technique efficace pour ajuster automatiquement la taille du pas dans l'optimisation lisse. Elle garantit des performances similaires à l'utilisation de la taille de pas théoriquement optimale. De nombreuses approches ont été développées pour ajuster les tailles de pas par coordonnée, également connues sous le nom de préconditionneurs diagonaux, mais aucune des méthodes existantes n'est compétitive par rapport aux tailles de pas optimales par coordonnée. Nous proposons le backtracking multidimensionnel, une extension de la recherche linéaire backtracking pour trouver de bons préconditionneurs diagonaux pour les problèmes convexes lisses. Notre principale idée est que le gradient par rapport aux tailles de pas, également connu sous le nom d'hypergradients, produit des hyperplans de séparation qui nous permettent de rechercher de bons préconditionneurs à l'aide de méthodes de plan de coupe. Comme les méthodes de plan de coupe de boîte noire comme la méthode de l'ellipsoïde sont prohibitives sur le plan informatique, nous développons un algorithme efficace adapté à notre contexte. Le backtracking multidimensionnel est manifestement compétitif par rapport au meilleur préconditionneur diagonal et ne nécessite aucun réglage manuel.

Apprendre les politiques universelles par la génération de vidéos guidées par le texte

Yilun Du, Sherry Yang, Bo Dai, Hanjun Dai, Ofir Nachum, Josh Tenenbaum, *Dale Schuurmans, Pieter Abbeel

Résumé :

L'un des objectifs de l'intelligence artificielle est de construire un agent capable de résoudre une grande variété de tâches. Les progrès récents dans le domaine de la synthèse d'images guidée par le texte ont donné naissance à des modèles dotés d'une capacité impressionnante à générer de nouvelles images complexes, faisant preuve d'une généralisation combinatoire à travers les domaines. Motivés par ce succès, nous cherchons à savoir si de tels outils peuvent être utilisés pour construire des agents plus polyvalents. Plus précisément, nous présentons le problème de la prise de décision séquentielle comme un problème de génération de vidéo conditionnée par du texte, où, étant donné une spécification codée en texte d'un objectif souhaité, un planificateur synthétise un ensemble d'images futures décrivant ses actions prévues dans le futur, après quoi les actions de contrôle sont extraites de la vidéo générée. En tirant parti du texte comme spécification sous-jacente de l'objectif, nous sommes en mesure de généraliser naturellement et de manière combinatoire de nouveaux objectifs. La formulation proposée de la politique en tant que vidéo peut en outre représenter des environnements avec différents espaces d'état et d'action dans un espace unifié d'images, ce qui, par exemple, permet l'apprentissage et la généralisation à travers une variété de tâches de manipulation de robots. Enfin, en tirant parti de l'intégration de langues préformées et de vidéos largement disponibles sur Internet, l'approche permet le transfert de connaissances par la prédiction de plans vidéo très réalistes pour des robots réels.

Gestion de la résolution temporelle dans l'estimation continue de la valeur : Un compromis fondamental

*Zichen Zhang, *Johannes Kirschner, *Junxi Zhang, *Francesco Zanini, *Alex Ayoub, *Masood Dehghan, *Dale Schuurmans,

Résumé :

Une hypothèse par défaut dans l'apprentissage par renforcement (RL) et le contrôle optimal est que les observations arrivent à des points temporels discrets sur un cycle d'horloge fixe. Pourtant, de nombreuses applications impliquent des systèmes à temps continu où la discrétisation du temps peut, en principe, être gérée. L'impact de la discrétisation temporelle sur les méthodes RL n'a pas été entièrement caractérisé dans la théorie existante, mais une analyse plus détaillée de son effet pourrait révéler des possibilités d'amélioration de l'efficacité des données. Nous comblons cette lacune en analysant l'évaluation de la politique de Monte-Carlo pour les systèmes LQR et nous découvrons un compromis fondamental entre l'approximation et l'erreur statistique dans l'estimation de la valeur. Il est important de noter que ces deux erreurs se comportent différemment en fonction de la discrétisation temporelle, ce qui conduit à un choix optimal de la résolution temporelle pour un budget de données donné. Ces résultats montrent que la gestion de la résolution temporelle peut améliorer de manière prouvée l'efficacité de l'évaluation des politiques dans les systèmes LQR avec des données finies. Empiriquement, nous démontrons le compromis dans des simulations numériques d'instances LQR et de repères RL standard pour le contrôle continu non linéaire.

Conditions de convergence globale des méthodes de gradient de politique basées sur l'ordre

Jincheng Mei, Bo Dai, Alekh Agarwal, Mohammad Ghavamzadeh, *Csaba Szepesvari, *Dale Schuurmans

Résumé :

Nous prouvons que, pour les bandits à bras finis avec approximation de fonction linéaire, la convergence globale des méthodes de gradient de politique (PG) dépend de propriétés interdépendantes entre la mise à jour de la politique et la représentation. Tout d'abord, nous établissons quelques observations clés qui encadrent l'étude : La convergence globale peut être atteinte dans le cadre d'une approximation de fonction linéaire sans politique ou réalisabilité de récompense, à la fois pour le PG Softmax standard et le gradient de politique naturel (NPG). L'erreur d'approximation n'est pas une quantité clé pour caractériser la convergence globale dans l'un ou l'autre algorithme. Les conditions de la représentation qui impliquent une convergence globale sont différentes entre ces deux algorithmes. Dans l'ensemble, ces observations remettent en question l'erreur d'approximation en tant que quantité appropriée pour caractériser la convergence globale des méthodes PG dans le cadre de l'approximation de fonctions linéaires. \Deuxièmement, motivés par ces observations, nous établissons de nouveaux résultats généraux : La NPG avec approximation de fonction linéaire atteint une convergence globale si et seulement si la projection de la récompense sur l'espace représentable préserve le rang de l'action optimale, une quantité qui n'est pas fortement liée à l'erreur d'approximation. La convergence globale de Softmax PG se produit si la représentation satisfait à une condition de non-domination et peut préserver le rang des récompenses, ce qui va bien au-delà de la réalisabilité de la politique ou de la récompense. Nous fournissons des résultats expérimentaux à l'appui de ces conclusions théoriques.

DISCS : une référence pour l'échantillonnage discret

Katayoon Goshvadi, Haoran Sun, Xingchao Liu, Azade Nova, Ruqi Zhang, Will Grathwohl, *Dale SchuurmansHanjun Dai

Résumé :

L'échantillonnage dans les espaces discrets, avec des applications critiques dans la simulation et l'optimisation, a récemment été stimulé par des avancées significatives dans les approches basées sur le gradient qui exploitent les accélérateurs modernes tels que les GPU. Cependant, deux défis majeurs entravent les progrès de la recherche sur l'échantillonnage discret. Premièrement, comme il n'y a pas de consensus sur les paramètres expérimentaux et les dispositifs d'évaluation, les résultats empiriques des différents documents de recherche ne sont souvent pas comparables. Deuxièmement, la mise en œuvre d'échantillonneurs et de distributions cibles nécessite souvent un effort non négligeable en termes de calibrage et de parallélisme. Pour relever ces défis, nous proposons DISCS (DISCrete Sampling), un package sur mesure et un benchmark qui supporte une implémentation unifiée et efficace des expériences et des évaluations pour l'échantillonnage discret dans trois types de tâches : l'échantillonnage à partir de modèles graphiques classiques et de modèles génératifs basés sur l'énergie, et l'échantillonnage pour la résolution de l'optimisation combinatoire. Tout au long des évaluations complètes de DISCS, nous avons acquis de nouvelles connaissances sur l'extensibilité, les principes de conception des distributions de propositions et les leçons pour la conception d'un échantillonnage adaptatif. DISCS implémente efficacement des échantillonneurs discrets représentatifs des travaux de recherche existants en tant que lignes de base et offre une interface simple qui permet aux chercheurs d'ajouter de nouveaux échantillonneurs discrets et de comparer directement leurs performances avec les résultats de référence dans une configuration calibrée.

Filtrage historique dans les jeux à information imparfaite : Algorithmes et complexité

*Christopher Solinas, *Doug Rebstock, *Nathan Sturtevant, Michael Buro

Résumé :

Historiquement appliquée exclusivement aux jeux à information parfaite, la recherche limitée en profondeur avec des fonctions de valeur a joué un rôle clé dans les progrès récents de l'IA pour les jeux à information imparfaite. La plupart des approches les plus importantes présentant des garanties théoriques solides nécessitent une décomposition du sous-jeu - un processus dans lequel un sous-jeu est calculé à partir des informations publiques et des croyances des joueurs. Cependant, la décomposition du sous-jeu peut elle-même nécessiter des calculs non triviaux, et sa tractabilité dépend de l'existence d'algorithmes efficaces pour l'énumération complète ou la génération des historiques qui forment la racine du sous-jeu. Malgré cela, aucune analyse formelle de la tractabilité de ces calculs n'a été établie dans les travaux antérieurs, et les domaines d'application ont souvent consisté en des jeux, tels que le poker, pour lesquels l'énumération est triviale sur le matériel moderne. L'application de ces idées à des domaines plus complexes nécessite de comprendre leur coût.

Dans ce travail, nous présentons et analysons les aspects informatiques et la traçabilité du filtrage des historiques pour la décomposition du sous-jeu. Nous montrons que la construction d'un historique unique à partir de la racine du sous-jeu est généralement irréalisable, puis nous fournissons une condition nécessaire et suffisante pour une énumération efficace. Nous présentons également un nouvel algorithme de génération basé sur la chaîne de Markov et Monte Carlo pour les jeux de cartes à ruse - un domaine où l'énumération est souvent d'un coût prohibitif. Nos expériences démontrent l'amélioration de l'évolutivité de cet algorithme dans le jeu de cartes truqué Oh Hell. Ces contributions précisent quand et comment la recherche limitée en profondeur via la décomposition du sous-jeu peut être un outil efficace pour la prise de décision séquentielle dans des contextes d'information imparfaite.

Améliorer la généralisation compositionnelle à l'aide de l'apprentissage itéré et des emboîtements simplifiés

Yi Ren, Samuel Lavoie, Michael Galkin, *Danica J. SutherlandAaron Courville

Résumé :

La généralisation compositionnelle, la capacité d'un agent à généraliser à des combinaisons inédites de facteurs latents, est facile pour les humains mais difficile pour les réseaux neuronaux profonds. Un courant de recherche en sciences cognitives a émis l'hypothèse d'un processus, l'"apprentissage par itération", pour expliquer comment le langage humain a développé cette capacité ; la théorie repose sur des pressions simultanées vers la compressibilité (lorsqu'un agent ignorant apprend d'un agent informé) et l'expressivité (lorsqu'il utilise la représentation pour des tâches en aval). Inspirés par ce processus, nous proposons d'améliorer la généralisation compositionnelle des réseaux profonds en utilisant l'apprentissage itéré sur des modèles avec des encastrements simpliciaux, qui peuvent approximativement discrétiser les représentations. Cette approche est également motivée par une analyse de la compositionnalité basée sur la complexité de Kolmogorov. Nous montrons que cette combinaison de changements améliore la généralisation compositionnelle par rapport à d'autres approches, en démontrant ces améliorations à la fois sur des tâches de vision avec des facteurs latents bien compris et sur des tâches réelles de prédiction de graphes moléculaires où la structure latente est inconnue.

Le RL en ligne dans les PDM linéairement q^\pi-réalisables est aussi facile que dans les PDM linéaires si vous savez ce qu'il faut ignorer.

Gellert Weisz, András György, *Csaba Szepesvari

Résumé :

Nous considérons l'apprentissage par renforcement en ligne (RL) dans les processus de décision markoviens épisodiques (MDP) sous l'hypothèse de réalisabilité linéaire q^\pi, où il est supposé que les valeurs d'action de toutes les politiques peuvent être exprimées comme des fonctions linéaires des caractéristiques d'action de l'état. Cette classe est connue pour être plus générale que les PDM linéaires, où le noyau de transition et la fonction de récompense sont supposés être des fonctions linéaires des vecteurs de caractéristiques. Notre première contribution consiste à montrer que la différence entre les deux classes réside dans la présence d'états dans les PDM réalisables linéairement q^\pi où, pour toute politique, toutes les actions ont des valeurs approximativement égales, et le fait de sauter ces états en suivant une politique arbitrairement fixée dans ces états transforme le problème en un PDM linéaire. Sur la base de cette observation, nous dérivons un nouvel algorithme d'apprentissage (inefficace en termes de calcul) pour les PDM linéairement q^\pi réalisables, qui apprend simultanément quels états doivent être ignorés et exécute un autre algorithme d'apprentissage sur le PDM linéaire caché dans le problème. La méthode renvoie une politique optimale epsilon après des interactions polylog(H,d)epsilon^2 avec le MDP, où H est l'horizon temporel et d la dimension des vecteurs de caractéristiques, ce qui donne le premier algorithme RL en ligne de complexité polynomiale pour ce cadre. Les résultats sont prouvés pour le cas mal spécifié, où il est démontré que la complexité de l'échantillon se dégrade gracieusement avec l'erreur de mauvaise spécification.

Minimisation des regrets par l'optimisation du point de selle

*Johannes Kirschner, *Alireza Bakhtiari, *Kushagra Chandak, *Volodymyr Tkachuk,

Résumé :

Une longue série de travaux caractérise la complexité d'échantillonnage de la minimisation du regret dans la prise de décision séquentielle par des programmes min-max. Dans le jeu du point selle correspondant, le joueur min optimise la distribution d'échantillonnage contre un joueur max adverse qui choisit des modèles confus conduisant à des regrets importants. L'instanciation la plus récente de cette idée est le coefficient d'estimation de la décision (DEC), dont il a été démontré qu'il fournissait des limites inférieures et supérieures presque étroites sur le pire cas de regret attendu dans les bandits structurés et l'apprentissage par renforcement. En re-paramétrant le DEC offset avec le rayon de confiance et en résolvant le programme min-max correspondant, nous dérivons une variante à tout moment de l'algorithme Estimation-To-Decisions (Anytime-E2D). Il est important de noter que l'algorithme optimise le compromis exploration-exploitation en ligne plutôt que par le biais de l'analyse. Notre formulation conduit à un algorithme pratique pour des classes de modèles finies et des modèles de rétroaction linéaires. Nous illustrons les résultats en dérivant des taux améliorés pour les bandits linéaires à haute dimension. Enfin, nous soulignons les liens avec le ratio d'information, le coefficient de découplage et le PAC-DEC, et nous évaluons numériquement les performances de l'E2D sur des exemples simples.

Bandits stochastiques contextualisables

Chung-Wei Lee, Qinghua Liu, Yasin Abbasi Yadkori, Chi Jin, Tor Lattimore, *Csaba Szepesvari

Résumé :

We consider a contextual bandit problem with S contexts and K actions. In each round t = 1, 2 ... the learner observes a random context and chooses an action based on its past experience. The learner then observes a random reward whose mean is a function of the context and the action for the round. Under the assumption that the contexts can be lumped into r < min (K, S) groups such that the mean reward for the various actions is the same for any two contexts that are in the same group, we give an algorithm that outputs an epsilon-optimal policy after using at most O~(sqrt{(r (S +K )/epsilon^2)} samples with high probability and provide a matching Omega(r (S +K )/epsilon^2) lower bound. In the regret minimization setting, we give an algorithm whose cumulative regret up to time T is bounded by O~(\sqrt{r ^3(S +K )T})$ To the best of our knowledge, we are the first to show the near-optimal sample complexity in the PAC setting and O~{\sqrt{\text{poly}(r)(S+K)T}} minimax regret in the online setting for this problem. We also show our algorithms can be applied to more general low-rank bandits and get improved regret bounds in some scenarios.

Optimistic Natural Policy Gradient : a Simple Efficient Policy Optimization Framework for Online RL (Gradient naturel optimiste de la politique : un cadre simple et efficace d'optimisation de la politique pour la RL en ligne)

Qinghua Liu, Gellert Weisz, András György, Chi Jin, *Csaba Szepesvari

Résumé :

Bien que les algorithmes d'optimisation des politiques aient joué un rôle important dans le succès empirique récent de l'apprentissage par renforcement (RL), la compréhension théorique existante de l'optimisation des politiques reste plutôt limitée - ils sont soit limités aux MDP tabulaires, soit souffrent d'une complexité d'échantillonnage hautement sous-optimale, en particulier dans le RL en ligne où l'exploration est nécessaire. Cet article propose un cadre d'optimisation de politique simple et efficace, la NPG OPTIMISTIQUE, pour la RL en ligne. La NPG OPTIMISTIQUE peut être considérée comme une simple combinaison de l'algorithme classique du gradient naturel de politique (NPG) [Kakade, 2001] et d'un sous-programme d'évaluation optimiste de la politique visant à encourager l'exploration. Pour les PDM linéaires à d dimensions, OPTIMISTIC NPG est efficace sur le plan des calculs et apprend une politique ϵ-optimale en O˜(d 2/ϵ3 ) échantillons, ce qui constitue le premier algorithme efficace sur le plan des calculs dont la complexité de l'échantillon a la dépendance de dimension optimale Θ( ˜ d 2 ). Il améliore également les résultats de pointe des algorithmes d'optimisation des politiques [Zanette et al., 2021] d'un facteur d. Pour l'approximation de fonction générale qui englobe les PDM linéaires, OPTIMISTIC NPG, à notre connaissance, est également le premier algorithme d'optimisation des politiques qui atteint une complexité d'échantillon polynomiale pour l'apprentissage de politiques quasi-optimales.

L'ignorance est un bonheur : Contrôle robuste via l'élimination de l'information

*Manan Tomar, Riashat Islam, *Matthew E. TaylorSergey Levine, Philip Bachman

Résumé :

La parcimonie informationnelle - c'est-à-dire l'utilisation de l'information minimale requise pour une tâche - constitue un biais inductif utile pour l'apprentissage de représentations qui permettent une meilleure généralisation en étant résistantes au bruit et aux corrélations parasites. Nous proposons le filtrage de l'information dans l'espace des pixels comme moyen d'apprendre des représentations plus parcimonieuses. Le filtrage de l'information fonctionne par l'apprentissage de masques qui ne capturent que l'information minimale requise pour résoudre une tâche donnée. Intuitivement, nos modèles apprennent à identifier les indices visuels qui comptent réellement pour une tâche donnée. Nous utilisons une paramétrisation différentiable du rapport signal/bruit, qui peut être appliquée à des valeurs arbitraires dans un réseau, par exemple en masquant les pixels de la couche d'entrée. Nous appliquons notre approche, que nous appelons InfoGating, à divers objectifs tels que : la dynamique avant et inverse à plusieurs étapes, l'apprentissage Q, le clonage de comportement et les tâches auto-supervisées standard. Nos expériences montrent que l'apprentissage de l'identification et de l'utilisation d'informations minimales peut améliorer la généralisation dans les tâches en aval - par exemple, les politiques basées sur des images infogérées sont considérablement plus robustes aux caractéristiques visuelles distrayantes ou non pertinentes.

Garanties pour l'auto-jeu dans les jeux multijoueurs via la décomposabilité des polymatrices

*Revan MacQueen, *James Wright

Résumé :

L'auto-apprentissage est une technique d'apprentissage automatique dans les systèmes multi-agents où un algorithme d'apprentissage apprend en interagissant avec des copies de lui-même. L'auto-apprentissage est utile pour générer de grandes quantités de données pour l'apprentissage, mais présente l'inconvénient que les agents auxquels l'apprenant sera confronté après l'entraînement peuvent avoir un comportement radicalement différent de celui auquel l'apprenant s'attendait en interagissant avec lui-même. Dans le cas particulier des jeux à somme constante à deux joueurs, l'auto-apprentissage qui atteint l'équilibre de Nash est garanti pour produire des stratégies qui donnent de bons résultats contre n'importe quel adversaire après l'apprentissage. Nous montrons que dans les jeux qui se décomposent approximativement en un ensemble de jeux à somme constante à deux joueurs (appelés jeux polymatrix) où les équilibres ϵ-Nash globaux sont limitativement éloignés des équilibres de Nash dans chaque sous-jeu, tout algorithme sans regret externe qui apprend par auto-apprentissage produira une stratégie dont la vulnérabilité est limitée. Pour la première fois, nos résultats identifient une propriété structurelle des jeux multi-joueurs qui permet de garantir la performance des stratégies produites par une large classe d'algorithmes d'auto-apprentissage. Nous démontrons nos conclusions à l'aide d'expériences sur le poker Leduc.