🤖 machine learning

Reinforcement Learning in Super Mario Bros: Curriculum, Pedagogy, and Optimal Level Design in World 1-1

Cet article valide empiriquement l'efficacité pédagogique du design canonique de Super Mario Bros. World 1-1 en démontrant qu'un agent d'apprentissage par renforcement de type Monte Carlo atteint une efficacité d'apprentissage supérieure et zéro échec catastrophique uniquement lorsque les segments du niveau sont présentés dans leur ordre progressif original plutôt que dans des permutations aléatoires.

Auteurs originaux : Jesse Ponnock, Lucas Ho

Publié 2026-06-30

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jesse Ponnock, Lucas Ho

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 apprenez à un robot à jouer à Super Mario Bros. Vous voulez savoir deux choses :

Quelle méthode d'apprentissage fonctionne le mieux ? (Le robot doit-il mémoriser chaque étape ou utiliser un « cerveau de réseau neuronal » qui devine des motifs ?)
L'ordre du niveau est-il important ? (Le célèbre niveau World 1-1 est-il réellement conçu pour vous apprendre à jouer, ou est-ce juste un heureux hasard ?)

Les auteurs de ce papier ont construit une version numérique simplifiée de World 1-1 et ont laissé quatre différents « robots » essayer de le terminer. Voici ce qu'ils ont découvert, expliqué simplement.

Les quatre robots (Algorithmes)

Les chercheurs ont testé quatre façons différentes pour le robot d'apprendre :

Q-Learning & SARSA : Considérez-les comme des super-mémorisateurs. Ils gardent un immense carnet de notes où ils écrivent exactement ce qui se passe s'ils sautent à un endroit précis. Ils ne devinent pas ; ils se souviennent.
Monte Carlo : C'est le conteur. Il ne met pas à jour ses connaissances après chaque étape. Au lieu de cela, il attend la fin de toute la partie (l'épisode), regarde tout le voyage, et dit : « D'accord, toute cette course était bonne, donc chaque étape que j'ai franchie était probablement une bonne idée. »
DQN (Deep Q-Network) : C'est le devineur de motifs. Il utilise un cerveau complexe (un réseau neuronal) pour deviner quoi faire en se basant sur ce qu'il a vu auparavant. Il est conçu pour gérer des mondes vastes et désordonnés, mais les chercheurs voulaient voir si c'était excessif pour un niveau simple.

Les trois niveaux de difficulté

Ils ont testé ces robots sur trois versions du même niveau :

Niveau 1 (Statique) : Juste du sol, des tuyaux et des fossés. Pas d'ennemis.
Niveau 2 (+Blocs) : Ajout de briques cassables et de blocs de question.
Néeveau 3 (+Ennemis) : Des Goombas et des Koopas ont été ajoutés. C'est le vrai truc, complet.

Les grandes surprises

1. Le « Conteur » a gagné la course

Lorsque le niveau est devenu difficile (avec des ennemis), le robot Monte Carlo a été le grand vainqueur. Il a battu le niveau 95 % du temps.

Pourquoi ? Les autres robots (comme le Q-Learning) ont essayé de trouver le chemin le plus rapide vers la ligne d'arrivée. Ils ont ignoré les petits bonus (comme frapper les blocs de question) parce qu'ils étaient concentrés sur l'objectif.
Le robot Monte Carlo, cependant, a regardé toute l'histoire. Il a réalisé que frapper les blocs de question en chemin lui donnait des points supplémentaires et rendait son voyage plus sûr. Il a appris à être un joueur « riche », collectant tout sur son passage, plutôt qu'un simple joueur « rapide ».

2. Le « Devineur de motifs » (DQN) a fait une crise de nerfs

Le robot DQN, qui est habituellement célèbre pour être le plus intelligent, a échoué lamentablement sur le niveau le plus facile (Niveau 1). Il n'a gagné que 10 % du temps.

L'analogie : Imaginez un étudiant qui essaie d'apprendre les mathématiques, mais chaque fois qu'il se trompe, il reçoit un énorme « Échec » (une grosse note négative), et il obtient rarement un « A » (une victoire). L'étudiant a tellement peur de l'« Échec » qu'il arrête d'essayer de résoudre les problèmes et finit par abandonner.
Sur le Niveau 1, le robot tombait sans cesse dans des fossés et recevait de lourdes pénalités. Comme il ne frappait pas beaucoup de blocs de question (qui donnent de petits bonus), sa « banque de mémoire » était remplie d'échecs. Il s'est retrouvé coincé dans une boucle de peur.
La solution : Lorsqu'on a ajouté les blocs de question (Niveau 2), le robot a soudainement commencé à gagner 93 % du temps. Les petits bonus des blocs ont équilibré la peur de tomber, lui permettant d'apprendre.

3. La conception du niveau est une classe de maître

La partie la plus excitante du papier est l'Expérience de Curriculum.

La configuration : Le niveau World 1-1 est composé de 6 sections distinctes (A, B, C, D, E, F). Le jeu original joue ces sections dans l'ordre : A → B → C → D → E → F. Cela commence facile (un seul ennemi) et devient plus difficile (groupes d'ennemis).
Le test : Les chercheurs ont mélangé l'ordre. Ils ont fait jouer les parties difficiles en premier (F → E → D...) ou dans des ordres aléatoires.
Le résultat :
- Ordre Original (A→F) : Le robot a appris rapidement, a gagné presque à chaque fois, et n'a jamais complètement échoué.
- Ordre Inversé (F→A) : Le robot a terriblement lutté. Il tombait constamment dans des fossés au début, avait peur, et de nombreux robots n'ont jamais appris à jouer.
- Ordres Aléatoires : Certains ordres aléatoires fonctionnaient assez bien, mais aucun n'était aussi parfait que l'original.

La conclusion : Pourquoi l'ordre compte

Le papier prouve que World 1-1 n'est pas seulement un niveau amusant ; c'est un enseignant parfaitement conçu.

Si vous jetez un étudiant dans le feu (les parties difficiles en premier), il panique et abandonne.
Si vous le laissez pratiquer dans un bac à sable (les parties faciles en premier), il gagne en confiance.
Lorsqu'il arrive enfin face au feu, il sait exactement comment gérer la situation.

Les chercheurs ont découvert que le robot Monte Carlo était très sensible à cet ordre car il apprend à partir de l'histoire entière. Si l'histoire commence par un désastre, le robot pense que tout le jeu est un désastre. Le robot DQN, en revanche, ne se souciait pas de l'ordre. Parce qu'il utilise une « banque de mémoire » qui mélange toutes ses expériences passées (bonnes et mauvaises), il ne pouvait pas faire la différence entre un niveau qui commençait facile ou un niveau qui commençait dur.

Résumé

Meilleur apprenant : Le « Conteur » (Monte Carlo) était le meilleur pour battre le jeu complet car il a appris à apprécier le voyage, et pas seulement la ligne d'arrivée.
Meilleur enseignant : La conception originale de World 1-1 est scientifiquement prouvée comme étant la meilleure façon d'enseigner. Elle introduit les défis progressivement, ce qui empêche l'apprenant d'être submergé.
La leçon : En IA (et peut-être dans la vie), la manière dont vous introduisez un problème est tout aussi importante que ce que est le problème. Si vous commencez trop difficilement, même les algorithmes les plus intelligents peuvent échouer.

Résumé Technique : Apprentissage par Renforcement dans Super Mario Bros

Énoncé du Problème
Le niveau 1-1 de Super Mario Bros est largement célébré dans la littérature du game design comme un chef-d'œuvre d'enseignement progressif, où la structure même du niveau introduit les mécaniques (tubes, fossés, ennemis) selon un ordre sûr et à faible enjeu avant d'exiger leur intégration. Cependant, la question de savoir si cette structure constitue un véritable curriculum pédagogique mesurable empiriquement ou simplement un récit convaincant n'a jamais été formellement testée. Ce document cherche à valider l'efficacité pédagogique de la conception canonique du monde 1-1 en utilisant l'Apprentissage par Renforcement (RL) comme prisme empirique. Plus précisément, les auteurs examinent deux questions : (1) quel algorithme de RL apprend le niveau le plus efficacement et cela dépend-il de la complexité et (2) si l'ordonnancement canonique des segments accélère l'apprentissage par rapport aux permutations aléatoires.

Méthodologie
Les auteurs ont implémenté le monde 1-1 à partir de zéro comme un environnement entièrement discret, évitant les bibliothèques de jeux ou de RL standards pour garantir une représentation fidèle basée sur des tuiles.

Environnement : Le niveau est une grille de 212 × 14 tuiles. Trois versions de complexité croissante ont été créées :
- v1 (Statique) : Sol, tuyaux, fossés et escaliers.
- v2 (+Blocs) : Ajoute des briques cassables et des blocs "?" (question blocks).
- v3 (+Ennemis) : Ajoute 17 ennemis (Goombas et un Koopa) avec une physique fidèle à la NES, incluant les mécaniques de saut sur la tête.
Espace d'États : Représenté par des tuples incluant la colonne, la ligne, la phase de saut et une « fenêtre de vue » (un tuple de codes de tuiles dans la fenêtre de l'écran). L'espace d'états passe de 3 dimensions pour v1 à 115 dimensions pour v3.
Algorithmes : Quatre algorithmes ont été comparés : Q-Learning, SARSA, Monte Carlo (MC) et Deep Q-Network (DQN). Tous utilisaient une exploration $\epsilon$ $ϵ$ -greedy avec un calendrier de décroissance partagé.
- Les méthodes tabulaires (Q-Learning, SARSA, MC) utilisaient des tables Q exactes (defaultdict), enregistrant les valeurs des états visités sans approximation.
- DQN utilisait un MLP PyTorch (128-128-3) avec un replay buffer d'expérience (50k) et une synchronisation du réseau cible.
Expérience de Curriculum : Le niveau a été partitionné en six segments canoniques (A–F). Douze conditions ont été testées : l'ordre canonique (A→F), l'ordre inversé (F→A) et dix permutations aléatoires. L'agent Monte Carlo a été sélectionné pour cette expérience en raison de sa sensibilité aux trajectoires par épisode.

Principales Contributions

Implémentation Personnalisée : Un environnement discret basé sur Python et fidèle à la NES du monde 1-1 avec trois niveaux de complexité, construit sans moteurs de jeu externes.
Benchmarking d'Algorithmes : Une comparaison exhaustive de 60 sessions d'entraînement (4 agents × 3 niveaux × 5 graines/seeds) évaluant les méthodes tabulaires versus les méthodes d'approximation de fonction.
Validation du Curriculum : Une expérience systématique (60 sessions supplémentaires) échantillonnant l'espace des permutations des segments du niveau pour tester l'hypothèse de la structure pédagogique.

Résultats

Performance des Algorithmes :
- Monte Carlo (MC) s'est imposé comme l'agent le plus performant, atteignant un taux de victoire de 94,9 % ± 1,5 % sur le niveau complet (v3). MC a surpassé DQN (76,4 %) et les méthodes TD tabulaires en apprenant à maximiser les récompenses intermédiaires (casser des blocs, frapper des blocs "?" ) le long des chemins gagnants plutôt que de prendre la route la plus directe.
- DQN a montré une dépendance à la « densité de récompense ». Il a subi un échec catastrophique sur v1 (taux de victoire de 10,6 %) car le replay buffer était inondé de pénalités de mort (−50) par rapport aux signaux positifs épars. Cependant, il s'est rétabli sur v2 (93,4 %) lorsque les récompenses intermédiaires (blocs ?) ont diversifié le signal. Sur v3, DQN a obtenu le taux de victoire le plus bas (76,4 %) en raison d'une sur-généralisation, apprenant à éviter totalement les ennemis plutôt qu'à risquer les récompenses de saut (+5).
- Les Méthodes Tabulaires ont convergé sur tous les niveaux. MC a convergé le plus rapidement sur v1 et v2, tandis que SARSA et Q-Learning ont montré une convergence légèrement plus lente sur v1 en raison d'un conservatisme d'exploration.
Apprentissage de Curriculum :
- L'Ordre Canonique (A→F) était la condition la plus rapide et la plus robuste, atteignant un taux de victoire de 94,7 % avec zéro échec catastrophique sur 10 graines. Il a convergé vers un taux de victoire de 50 % en environ 2 771 épisodes.
- L'Ordre Inversé (F→A) a été sévèrement pénalisé, avec un taux de victoire de 48,5 % et 4 échecs sur 10 graines.
- Les Permutations Aléatoires se sont regroupées entre ces deux extrêmes (moyenne de 89,0 %) mais présentaient une variance élevée ; aucune permutation aléatoire unique n'a égalé les trois critères de la condition canonique (taux de victoire le plus élevé, convergence la plus rapide, zéro échec).
Mécanisme de Sensibilité : L'effet de curriculum était spécifique au mécanisme de mise à jour. DQN a montré un effet de curriculum nul (aucune différence significative entre les ordres canonique, inversé et aléatoire) car son replay buffer échantillonne uniformément les transitions, effaçant l'ordre temporel des segments faciles vers difficiles. MC, qui ne met à jour qu'après des épisodes complets, est hautement sensible à l'ordre des segments.

Signification et Revendications
Ce document fournit la première validation empirique que la conception canonique de World 1-1 encode une véritable structure pédagogique qui accélère mesurablement l'apprentissage et ne peut être reproduite par hasard. Les résultats démontrent que :

La Structure Pédagogique est Réelle : L'ordonnancement spécifique des segments dans World 1-1 n'est pas arbitraire ; il optimise l'efficacité de l'apprentissage et la robustesse pour les agents qui dépendent de signaux basés sur les trajectoires.
Critères de Sélection d'Algorithme : Le choix entre les méthodes tabulaires et DQN ne doit pas reposer uniquement sur la taille de l'espace d'états. Dans des environnements discrets et non uniformes avec des récompenses éparses, les méthodes tabulaires (spécifiquement MC) peuvent surpasser DQN. Le succès de DQN est tributaire de la densité de récompense pour stabiliser son replay buffer.
Sensibilité du Mécanisme de Mise à Jour : La sensibilité à l'ordre du curriculum est dictée par le mécanisme de mise à jour. Les apprenants par épisode (MC) bénéficient d'une difficulté progressive, tandis que les apprenants basés sur le replay (DQN) sont insensibles à l'ordre temporel en raison de l'échantillonnage uniforme.

Les auteurs concluent que la conception de World 1-1 est un curriculum fonctionnel, et non un simple récit, et que son efficacité est contingente sur la capacité de l'agent à utiliser la structure temporelle du signal d'apprentissage.