L'agent d'exploitation minimax : une méthode d'apprentissage efficace des données pour l'autojeu compétitif

Contexte et préambules

Le renforcement profond (Reinforcement Learning, RL) a fait la preuve de son utilité en résolvant de manière fiable les problèmes du chariot de montagne et du poteau sur chariot, où le problème et son environnement sont fixes. Toutefois, les environnements compétitifs comme le morpion ou les échecs rajoutent un nouveau problème : choisir un rival adéquat. Un adversaire trop fort peut limiter sensiblement la capacité d'apprentissage d'un agent, alors qu'un adversaire trop faible risque de ne déboucher sur aucun apprentissage utile.

Si les premiers prototypes de RL en environnement compétitif tentaient de créer manuellement des adversaires adaptés à l'agent --- une approche valable, quoiqu'inefficace et laborieuse ---, les récentes avancées se sont axées sur une solution élégante à ce dilemme. 

De fait, cette réflexion sur les solutions potentielles est une expérience de pensée intéressante pour les lecteurs de ce blog. Admettons, par exemple, que vous vouliez apprendre à jouer aux échecs : comment avoir la certitude de trouver un adversaire de votre niveau, sans connaître précisément ledit niveau ? En outre, il faudrait que cet adversaire s'améliore au même rythme que vous, faute de quoi il finirait par ne plus pouvoir vous opposer un niveau de jeu adapté.

Ce problème peut paraître insoluble à première vue, mais une réponse aussi simple qu'élégante nous tend les bras : l'adversaire idéal est en réalité... vous-même ! Vous avez en effet la garantie mathématique d'être précisément de votre niveau, sans même savoir au juste (voire tout court) de quoi vous êtes capable. L'idée peut paraître inattaquable en théorie, mais sa mise en pratique implique un concept appelé « League Training », entraînement en ligue. Avec le League Training, vous jouez exclusivement contre vous-même --- de multiples versions passées de vous-même --- à l'aide d'un système de classement comparable à celui des saisons de ligues sportives. Il est donc possible de classer les versions précédentes de vous-même en fonction de leurs performances face à votre moi actuel, puis de vous apparier l'adversaire le plus adapté de cette ligue pour mieux accélérer votre entraînement.

Ce modèle d'entraînement plus spécifique, appelé autojeu compétitif (Competitive Self Play, CSP), est décrit en profondeur dans la recherche fondatrice d'Alphastar, qui applique le CSP à Starcraft jusqu'à déboucher sur des performances surhumaines. Il est important de bien comprendre ce modèle, car les concepts d'agent principal et d'agents d'exploitation constituent le cœur de notre recherche. Pour résumer, notre agent principal cherche à apprendre des stratégies, tandis que ceux d'exploitation sont des agents spéciaux qui cherchent à apprendre des contre-stratégies. 

Motivation

Dans le cadre décrit ci-dessus, notre objectif est d'améliorer l'efficacité des données du CSP. Puisque nous nous entraînons face à nous-mêmes, nous avons accès à notre propre réseau de neurones, autrement dit le cerveau de l'agent. Dans un CSP traditionnel, l'adversaire est traité comme une boîte noire, dont les actions sont observées uniquement en réaction aux nôtres. Or, nous proposons quant à nous d'ouvrir cette boîte noire, pour exploiter activement la logique qui a conduit à ces actions, afin de mieux déterminer si nos propres actions ont été utiles ou non. En termes de RL, un CSP traditionnel se concentre uniquement sur la stratégie de l'adversaire, tandis que nous proposons d'analyser à la fois leurs réseaux stratégiques et évaluatifs.

La mise en œuvre de notre idée est simple, puisque nous pouvons accéder aux réseaux évaluatifs et Q de l'adversaire, afin d'évaluer notre action de son point de vue. Revenons à notre scénario d'échecs simple. Supposons que vous ayez joué un coup et que ce soit maintenant au tour de votre adversaire : puisque nous avons accès à ses réseaux évaluatifs, nous pouvons voir comment il évalue sa position actuelle avant de jouer, et puisque cette position actuelle est le résultat direct de notre coup précédent, nous pouvons évaluer par procuration l'efficacité de notre action selon son point de vue. Concrètement, imaginez une position d'échecs équilibrée dans laquelle vous commettez une erreur cruciale, que vous n'identifiez pas comme telle mais qui vous fera forcément perdre la partie d'ici cinq coups. Votre adversaire va profiter de cette erreur dès que vous la commettez, et va certainement évaluer sa position comme « gagnante », ce que refléteront ses réseaux évaluatifs. Avec le RL traditionnel, votre erreur cruciale n'aboutirait qu'à une récompense négative à la fin de la partie ; ce serait alors à l'algorithme RL de revenir propager cette information depuis la fin de la partie jusqu'à cet instant crucial. Au lieu d'attendre que la partie prenne fin pour que l'agent s'améliore, nous pouvons aussi analyser directement la façon dont l'adversaire évalue l'échiquier et en conclure aussitôt qu'il s'agissait d'un mauvais coup.

En substance, nous offrons une récompense à notre agent en fonction de l'évaluation de l'adversaire ; nous l'appelons récompense minimax, puisqu'elle est inspirée de l'algorithme éponyme. L'algorithme minimax est l'une des techniques les plus répandues des débuts de l'intelligence artificielle pour résoudre les jeux à somme nulle à deux joueurs. Pour rappel, un jeu à somme nulle à deux joueurs désigne toute forme de jeu à deux joueurs dont la somme des résultats est toujours égale à zéro : la partie se termine soit par la défaite d'un joueur (-1) et la victoire d'un autre (+1), soit par un match nul (+/-0), comme le morpion, les échecs, le go, etc.

L'algorithme minimax analyse toutes les actions que nous pouvons effectuer dans une situation donnée, suivies de toutes les actions que l'adversaire peut effectuer en réponse, et ainsi de suite jusqu'à atteindre une situation finalisée, c'est-à-dire la fin de la partie. À chaque étape, quand c'est notre tour, l'algorithme cherche à maximiser le résultat (choisir les actions qui déboucheront sur une victoire) et quand c'est le tour de l'adversaire, à minimiser le résultat (empêcher une défaite) : d'où le nom minimax. 

Le problème principal de l'algorithme minimax est que l'investissement en temps augmente exponentiellement selon le nombre d'actions à prendre en compte dans chaque situation : il s'agit du facteur de ramification. S'il peut être efficace dans des environnements relativement simples comme le morpion, cet algorithme devient vite ingérable face à des problèmes plus complexes comme les échecs, qui comportent en moyenne 30 à 40 coups légaux envisageables par tour. 

La récompense minimax

Puisqu'il n'est pas possible d'appliquer l'algorithme minimax à des environnements comportant un nombre de dimensions élevé, et vu que dans les environnements compétitifs entraînés par CSP, nous avons accès aux réseaux qui contrôlent nos adversaires (dans la mesure où ils ne sont autres que nous-mêmes), nous proposons la formule suivante pour la récompense minimax :

Riminimax (st, at) = Ri(st, at) - (1-d)aQj(st+1, a)

Où Ri représente la récompense environnementale qu'observe notre agent, Qj est la fonction Q de l'adversaire, [0, 1] est un coefficient qui module le signal de l'adversaire et d{0, 1} correspond au signal émis. Pour faire simple, cette récompense effectue une pondération entre la récompense environnementale et la fonction Q de l'adversaire. L'idée est ici de pénaliser notre agent à chaque étape, selon l'évaluation de notre adversaire à chaque étape suivante. Pour schématiser, nous demandons à notre agent de trouver l'action, à l'étape t, qui minimise l'évaluation à l'étape suivante t+1, du point de vue de notre adversaire, tout en maximisant la récompense environnementale. 

Remarque concernant le reward shaping

L'idée de donner à notre agent une source de récompense supplémentaire pour accélérer l'entraînement n'est pas nouvelle. On parle souvent de « reward shaping » (ou « reward engineering ») : c'est-à-dire que vous, en tant que concepteur, modifiez la fonction de récompense de l'agent afin de rendre le processus d'apprentissage plus facile à gérer. Pour reprendre l'exemple des échecs, la fonction de récompense la plus simple que vous pouvez donner à votre agent est un +1 pour une victoire, -1 pour une défaite et 0 pour toutes les autres actions. On parle alors d'une fonction de récompense parcimonieuse, puisque comme son nom l'indique, l'agent observe seulement un signal à la fin de la partie : les actions intermédiaires ne sont pas récompensées et c'est à l'algorithme d'apprentissage de les évaluer correctement. Même si cette approche fonctionne en théorie, les fonctions de récompenses parcimonieuses nécessitent beaucoup d'expérience pour pouvoir converger vers la bonne solution. Une autre solution consiste à décomposer le problème, en laissant un fil d'Ariane à l'agent pour apprendre la tâche : il s'agit alors d'une fonction de récompense dense. Par exemple, chaque fois que votre agent d'échecs prend un pion, il gagne +1 ; s'il perd un pion, -1 ; s'il prend un cavalier, +3, et ainsi de suite. Le problème de taille que représentent les échecs est ainsi décomposé en objectifs bien plus simples et faciles à accomplir. Seul inconvénient : vous, en tant que concepteur, êtes en train d'injecter vos idées préconçues dans l'évaluation de l'agent. Pourquoi un pion vaut-il +1 ? Pourquoi un chevalier vaut-il +3 ? La bonne façon d'apprendre les échecs est-elle vraiment d'évaluer chaque pièce séparément plutôt que tout l'échiquier collectivement ?

La différence fondamentale entre le reward shaping traditionnel et la récompense minimax, c'est que si tous deux finissent par densifier le signal de récompense, nous le faisons sans injecter de parti pris humain dans la fonction de récompense. Si le parti pris qu'injecte le reward shaping peut se révéler très utile pour les tâches simples, il est en revanche loin d'être facile de trouver la récompense dense la plus adaptée aux tâches complexes. En outre, il est quasiment impossible de trouver une récompense dense évidente pour certains environnements. Si vous entraînez un agent à jouer au morpion ou à Puissance 4 par exemple, comment créeriez-vous une fonction de récompense dense ?

Expériences et résultats

Nous lançons l'agent d'exploitation minimax dans quatre environnements différents : morpion, Puissance 4, Atari Boxing et enfin For Honor ! 

Morpion et Puissance 4

Nos deux premiers environnements sont des jeux de société simples au tour par tour, morpion et Puissance 4. Nous entraînons nos agents avec l'algorithme minimax et utilisons l'évaluation de ce dernier pour créer indirectement une fonction Q. Pour le morpion, nous exécutons l'algorithme minimax jusqu'au bout, tandis que pour Puissance 4, nous limitons sa profondeur de parcours à seulement 3 coups ; cela afin de simuler deux scénarios, l'un avec une stratégie parfaite de l'adversaire, l'autre imparfaite. Nous comparons l'entraînement des agents DQN traditionnels avec et sans la récompense minimax. Nous entraînons par ailleurs un autre agent appelé agent gamma-0, pour lequel nous définissons le gamma (dans la règle de mise à jour du Temporal difference learning) à 0, ce qui clone l'inverse du minimax de l'adversaire en tant que fonction Q. Rappelons la règle de mise à jour du TD learning : Q(st, at)  Q(st, at) +  [R(st, at) + maxaQ(st+1, a)]

En définissant le gamma à 0, la règle de mise à jour est alors basée exclusivement sur la récompense immédiate, ce qui, dans le cas de l'agent gamma-0, correspond à la fonction Q de l'adversaire. Cet agent gamma-0 nous permet d'estimer la quantité d'informations contenues uniquement dans la fonction Q de l'adversaire, et si cette fonction est inexacte, pouvons-nous quand même en extraire des informations pour accélérer l'entraînement ?

Nous constatons que l'agent d'exploitation minimax s'entraîne plus vite que l'agent DQN standard, même quand la fonction Q n'est pas assez probante, comme pour Puissance 4. Pour les deux expériences suivantes, puisque nous constatons que l'agent d'exploitation minimax peut être efficace même quand la fonction Q à elle seule n'est pas probante, nous déterminons l'efficacité de la récompense minimax face au reward shaping traditionnel.

Atari Boxing

Pour Atari Boxing, nous entraînons trois agents comme précédemment. Un agent DQN classique qui observe une récompense parcimonieuse de +1 pour une victoire, -1 pour une défaite et 0 partout ailleurs, que nous appelons DQN-Sparse. Un DQN qui observe une récompense dense de +1 chaque fois qu'il parvient à toucher son adversaire, que nous appelons DQN-Dense. Et pour finir, l'agent d'exploitation minimax.

Il ressort des graphiques d'entraînement que dans ce cas précis, le reward engineering simple est plus efficace que la récompense minimax pour entraîner un agent face au même adversaire fixe. C'est toutefois un résultat attendu, car il n'y a pas de malus quand on encaisse un coup dans Atari Boxing. Il s'agit d'un cas spécial où le reward engineering simple aboutit à une solution optimale. 

Toutefois, comme nous le verrons dans la dernière expérience sur For Honor, le reward engineering simple montre vite ses limites. 

For Honor

L'expérience finale sur For Honor est la plus approfondie : nous entraînons tout un framework de league training CSP pendant 24 h avant de comparer l'entraînement en fonction de deux mesures. La première est le nombre d'agents d'exploitation concluants générés à la fin de l'entraînement. La deuxième est l'ensemble des agents principaux issus de chaque entraînement, que nous apparions pour déterminer le plus robuste. Nous entraînons ici 4 types d'agents d'exploitation différents. L'agent d'exploitation de base qui observe une fonction de récompense parcimonieuse de +10 par victoire, -10 par défaite ; l'agent d'exploitation minimax, qui observe la récompense minimax ; l'agent d'exploitation défensif, qui observe +10 par victoire, -10 par défaite et un malus pour chaque coup subi ; et enfin l'agent d'exploitation agressif, qui observe +10 par victoire, -10 par défaite et un bonus pour chaque coup infligé à l'adversaire.

D'après le graphique ci-dessus, c'est l'agent d'exploitation minimax qui génère régulièrement le plus d'agents d'exploitation parfaitement concluants après 24 h d'entraînement sur trois seeds. Nous avons ensuite apparié les agents principaux des meilleurs seeds pour chaque situation et comparé leurs taux de victoires à l'issue de 1 000 duels. 

Nous constatons que l'agent minimax est le plus solide de tous avec un taux de victoires de plus de 66 % contre tous les agents. 

Conclusion

L'agent d'exploitation minimax donne lieu à une méthode d'apprentissage efficace des données pour l'autojeu compétitif en mettant à profit la fonction Q de l'adversaire. Cette approche fournit une façon inédite d'évaluer vos actions en temps réel pour apprendre en adoptant le point de vue de votre adversaire. Les expériences et résultats présentés ici démontrent l'efficacité de l'agent d'exploitation minimax dans divers environnements de jeu et mettent en exergue sa faculté à accélérer l'entraînement en améliorant les performances des agents. Cette approche représente un pas de plus vers la création d'agents d'apprentissage intelligents et adaptatifs dans les jeux vidéo AAA.