Jouer à Connect Four avec Deep Q-Learning

De Sarsa au Deep Q-Learning

Pour accomplir cette tâche, nous étendons notre cadre sur plusieurs dimensions importantes.

Tout d’abord, nous passons de mises à jour en ligne à un configuration de formation par lots. Dans notre mise en œuvre antérieure de Sarsanous avons mis à jour le modèle après chaque transition. Tout en étant fidèle à l’algorithme original [1]cette approche est inefficace sur le plan informatique : chaque étape de l’optimiseur entraîne un coût non négligeable, et le matériel moderne, en particulier les GPU, est conçu pour fonctionner par lots avec une surcharge supplémentaire marginale.

Pour résoudre ce problème, nous introduisons un tampon de relecture. Au lieu de mettre à jour immédiatement, nous stockons les transitions au fur et à mesure qu’elles surviennent, soit jusqu’à une capacité fixe, soit, dans notre cas, jusqu’à ce qu’un ou plusieurs jeux soient terminés. Nous effectuons ensuite une mise à jour par lots sur cette expérience collectée. Cela améliore non seulement l’efficacité des calculs, mais stabilise également l’apprentissage en réduisant la variance des mises à jour individuelles.

À ce stade, un changement conceptuel important se produit. En s’appuyant sur l’expérience passée plutôt qu’en suivant strictement la politique actuelle, nous nous éloignons du Sarsa – un sur la politique méthode – vers Q-apprentissagece qui est hors politique. Bien que nous n’ayons pas formellement réintroduit ici le Q-learning dans le paramètre d’approximation des fonctions, l’extension du cas tabulaire est en grande partie simple. Cette combinaison de tampons de relecture et de Q-learning constitue la base de Réseaux Q profonds (DQN)popularisé par DeepMind dans son travail fondateur sur les jeux Atari [2].

Enfin, nous nous tournons vers évolutivité. L’apprentissage par renforcement est intrinsèquement gourmand en données, il est donc crucial d’augmenter le débit. Pour cela, nous mettons en œuvre un wrapper d’environnement vectorisé cela nous permet de simuler plusieurs jeux de Connect Four en parallèle. Concrètement, un seul appel à step(a) traite désormais un lot d’actions et fait progresser tous les environnements simultanément.

En pratique, cependant, parvenir à un véritable parallélisme en Python n’est pas trivial. Le Global Interpreter Lock (GIL) garantit qu’un seul thread exécute le bytecode Python à la fois, ce qui limite l’efficacité du multithreading pour les charges de travail liées au processeur telles que la progression de l’environnement. Nous avons également expérimenté le multitraitement, mais avons constaté que la surcharge supplémentaire (par exemple, la communication entre processus) compensait largement les gains dans notre contexte. Pour le lecteur intéressé, je recommande un message précédent du mien.

Malgré ces limitations, la combinaison de mises à jour par lots et de vectorisation de l’environnement entraîne une amélioration substantielle du débit, augmentant les performances à environ 50 à 100 jeux par seconde.

Mise en œuvre

Dans cet article, j’évite délibérément d’entrer trop dans les détails sur la vectorisation de l’environnement et me concentre plutôt sur les aspects RL. Cela est dû en partie au fait que la vectorisation elle-même n’est « qu’ » un détail d’implémentation, mais aussi parce que, en toute honnêteté, notre configuration actuelle n’est pas idéale. Cela est dû en grande partie aux limitations imposées par l’environnement PettingZoo que nous utilisons.

Dans les prochains articles, nous explorerons différents environnements et revisiterons ce sujet en mettant davantage l’accent sur évolutivité-un aspect crucial de l’apprentissage par renforcement moderne. Pour une discussion plus détaillée sur la façon dont nous structurons les environnements multi-joueurs, gérons les agents et maintenons un pool d’adversaires, je fais référence à mon article précédent sur RL multijoueur. La configuration vectorisée utilisée ici est simplement une extension de ce framework à plusieurs jeux exécutés en parallèle. Comme toujours, la mise en œuvre complète est disponible sur GitHub.

Revisiter Q-Learning

Revenons brièvement sur Q-learning et connectons-le à notre implémentation.

La règle de base de mise à jour est donnée par :

Contrairement à Sarsa, qui utilise l’action réellement entreprise dans l’état suivant, Q-learning utilise un opérateur maximum sur toutes les prochaines actions possibles. Cela fait hors politiquecar la mise à jour ne dépend pas de la politique de comportement utilisée pour générer les données. En pratique, cela conduit souvent à une propagation plus rapide des informations sur les valeurs, notamment dans des environnements déterministes tels que les jeux de société.

Combinée aux réseaux de neurones, cette approche est communément appelée Apprentissage Q profond. Au lieu de maintenir une table de valeurs, nous formons un réseau neuronal $Q_\thêta(s,a)$ pour approximer la fonction action-valeur. La mise à jour est ensuite implémentée comme un problème de régression, minimisant la différence entre l’estimation actuelle et une cible bootstrapée :

Dans notre implémentation, cela correspond directement à la batch_update fonction. Étant donné un lot de transitions $(s, a, r, s’, \text{done})$nous calculons d’abord les valeurs Q prédites pour les actions entreprises :

q = self.q(batch.states, ...)
q_sa = q.gather(1, batch.actions.unsqueeze(1)).squeeze(1)

Ensuite, nous construisons la cible en utilisant la valeur Q maximale de l’état suivant. Puisque toutes les actions ne sont pas légales dans Connect Four, nous appliquons un masque pour garantir que seuls les mouvements valides sont pris en compte :

q_next = self.q(batch.next_states, ...)
q_next_masked = q_next.masked_fill(~legal, float("-inf"))
max_next = q_next_masked.max(dim=1).values

Enfin, nous combinons la récompense et la valeur actualisée de l’état suivant, en prenant soin de gérer correctement les états terminaux :

target = batch.rewards + gamma * (~batch.dones).float() * max_next

Le réseau est ensuite entraîné en minimisant la perte de Huber (une variante plus robuste de l’erreur quadratique moyenne) :

loss = F.smooth_l1_loss(q_sa, target)

Cette formulation par lots nous permet de réutiliser efficacement l’expérience collectée à partir de plusieurs jeux parallèles, ce qui est crucial pour l’évolution vers des environnements plus complexes. Dans le même temps, cela met en évidence un défi clé du Deep Q-Learning : les cibles elles-mêmes dépendent du réseau actuel, ce qui peut conduire à une instabilité lors de la formation.

Pour une référence supplémentaire, le didacticiel officiel PyTorch sur Deep Q-Learning fournit une perspective complémentaire utile.

Résultats

Cela étant dit, passons aux résultats. Pour les mettre en perspective, rappelons d’abord comment méthodes tabulaires effectué sur cette tâche. Après 100 000 étapes, la plupart des politiques étaient encore étroitement regroupées en termes de taux de réussite. En particulier, même une politique aléatoire aboutit à peu près 50 % de taux de victoireindiquant qu’aucune des politiques apprises n’a réussi à surpasser le hasard de manière significative.

Dans l’expérience suivante, nous nous concentrons sur deux agents : notre DQN et une ligne de base aléatoire. En raison de la configuration « zoo » introduite précédemment, le DQN n’est pas une politique fixe unique mais un pool d’agents évolutifs. Nous ajoutons continuellement de nouvelles versions et élaguons les plus faibles, ce qui augmente progressivement la force globale du pool adverse.

Cela a une implication importante pour l’interprétation des métriques :
le taux de victoire de « DQN contre DQN » oscille naturellement 50%puisque des agents de force similaire se font concurrence. Un signal plus informatif est donc la performance du politique aléatoire. À mesure que le DQN s’améliore, l’agent aléatoire devrait gagner moins fréquemment.

Dans cette optique, regardons la courbe de performance :

Nous observons plusieurs effets intéressants. Plus particulièrement, le taux de réussite de la politique aléatoire tombe beaucoup plus vite que dans le cadre tabulaire – preuve claire que le DQN est effectivement en train d’apprendre le jeu. Cependant, après environ un million de pasles plateaux d’amélioration, la politique aléatoire gagnant toujours à peu près 20% des jeux.

Pour mieux comprendre ce que cela signifie en pratique, nous pouvons évaluer la politique apprise par rapport à un acteur humain. Dans l’exemple suivant, je prends le rôle du joueur rouge en premier :

Le résultat est assez révélateur. L’agent a clairement appris à jouer offensivement– il poursuit activement son propre quadruple rang. Cependant, il a du mal à jeu défensifne parvenant pas à anticiper et à bloquer les menaces simples de l’adversaire.

C’est sans doute un peu décevant, mais : nous y reviendrons. Dans les prochains articles, nous apprendrons comment mieux évoluer, apprendre plus vite et battre les humains (dans de nombreux domaines). Écrire cette série d’articles sur le grand livre de Sutton a été un voyage incroyable (même s’il reste encore quelques articles) – mais nous avons simplement dépassé le cadre très général avec lequel nous avons commencé pour présenter tous les algorithmes disponibles dans le livre de Sutton, couvrant à la fois les méthodes de résolution tabulaire et approchée. La spécialisation est donc la voie à suivre – et c’est exactement ce que nous ferons à l’avenir, en écrivant des méthodes hautement efficaces et personnalisées pour différents problèmes.

Conclusion

Dans cet article, nous sommes passés du Sarsa tabulaire à Apprentissage Q profondintroduisant des tampons de relecture, des mises à jour par lots et une approximation des fonctions. Nous avons appliqué cela à Connect Four, un jeu multijoueur que nous n’avions pas réussi à résoudre avec des méthodes tabulaires, avec un résultat clair : notre agent n’est plus bloqué au niveau du hasard : il apprend, s’améliore et surpasse systématiquement une politique aléatoire.

Mais ce qui est tout aussi important, nous en voyons également les limites.

Même après une formation approfondie, l’agent stagne et présente toujours des faiblesses évidentes, notamment dans le jeu défensif. Il ne s’agit pas simplement de « davantage de formation ». Dans les environnements multijoueurs, le problème lui-même devient plus difficile : les adversaires évoluent, l’environnement n’est plus stationnaire et les objectifs d’apprentissage ne cessent de changer.

C’est là que commence le véritable défi.

Jusqu’à présent, notre cadre, suivant vaguement [1] – a donné la priorité à la généralité et à la clarté. Mais pour aller plus loin, cela ne suffit plus. La performance nécessite une spécialisation.

Dans les prochains articles, nous continuons d’abord à suivre [1] – et se concentrera ensuite précisément sur cela : créer des systèmes plus rapides, plus stables et plus évolutifs, en allant au-delà des simples lignes de base vers des agents réellement compétitifs.

Autres articles de cette série

Références

[1] http://incompleteideas.net/book/RLbook2020.pdf

[2] https://arxiv.org/abs/1312.5602