🤖 machine learning

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

This paper empirically validates the pedagogical efficacy of Super Mario Bros. World 1-1's canonical design by demonstrating that a Monte Carlo reinforcement learning agent achieves superior learning efficiency and zero catastrophic failures only when the level's segments are presented in their original, progressive order rather than in random permutations.

Original authors: Jesse Ponnock, Lucas Ho

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jesse Ponnock, Lucas Ho

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to play Super Mario Bros. You want to know two things:

Which learning method works best? (Should the robot memorize every single step, or should it use a "neural network" brain that guesses patterns?)
Does the order of the level matter? (Is the famous World 1-1 level actually designed to teach you how to play, or is that just a happy accident?)

The authors of this paper built a simplified, digital version of World 1-1 and let four different "robots" try to beat it. Here is what they found, explained simply.

The Four Robots (Algorithms)

The researchers tested four different ways for the robot to learn:

Q-Learning & SARSA: Think of these as super-memorizers. They keep a giant notebook where they write down exactly what happens if they jump at a specific spot. They don't guess; they remember.
Monte Carlo: This is the storyteller. It doesn't update its knowledge after every single step. Instead, it waits until the end of the whole game (the episode), looks back at the entire journey, and says, "Okay, that whole run was good, so every step I took was probably a good idea."
DQN (Deep Q-Network): This is the pattern guesser. It uses a complex brain (a neural network) to guess what to do based on what it has seen before. It's designed to handle huge, messy worlds, but the researchers wanted to see if it was overkill for a simple level.

The Three Levels of Difficulty

They tested these robots on three versions of the same level:

Level 1 (Static): Just ground, pipes, and gaps. No enemies.
Level 2 (+Blocks): Added breakable bricks and question blocks.
Level 3 (+Enemies): Added Goombas and Koopas. This is the full, real deal.

The Big Surprises

1. The "Storyteller" Won the Race

When the level got hard (with enemies), the Monte Carlo robot was the clear winner. It beat the level 95% of the time.

Why? The other robots (like Q-Learning) tried to find the fastest path to the finish line. They ignored the little bonuses (like hitting question blocks) because they were focused on the goal.
The Monte Carlo robot, however, looked at the whole story. It realized that hitting question blocks along the way gave it extra points and made the journey safer. It learned to be a "rich" player, collecting everything on the way, rather than just a "fast" player.

2. The "Pattern Guesser" (DQN) Had a Meltdown

The DQN robot, which is usually famous for being the smartest, failed miserably on the easiest level (Level 1). It only won 10% of the time.

The Analogy: Imagine a student trying to learn math, but every time they get a question wrong, they get a huge "F" (a big negative score), and they rarely get an "A" (a win). The student gets so scared of the "F" that they stop trying to solve problems and just give up.
On Level 1, the robot kept falling into pits and getting huge penalties. Because it didn't hit many question blocks (which give small rewards), its "memory bank" was full of failures. It got stuck in a loop of fear.
The Fix: When they added question blocks (Level 2), the robot suddenly started winning 93% of the time. The small rewards from the blocks balanced out the fear of falling, allowing it to learn.

3. The Level Design is a Masterclass in Teaching

The most exciting part of the paper is the Curriculum Experiment.

The Setup: The World 1-1 level is made of 6 distinct sections (A, B, C, D, E, F). The original game plays them in order: A → B → C → D → E → F. This starts easy (just one enemy) and gets harder (groups of enemies).
The Test: The researchers scrambled the order. They made the robot play the hard parts first (F → E → D...) or random orders.
The Result:
- Original Order (A→F): The robot learned fast, won almost every time, and never completely failed.
- Reversed Order (F→A): The robot struggled terribly. It fell into pits constantly in the beginning, got scared, and many robots never learned to play at all.
- Random Orders: Some random orders worked okay, but none were as perfect as the original.

The Takeaway: Why the Order Matters

The paper proves that World 1-1 isn't just a fun level; it's a perfectly designed teacher.

If you throw a student into a fire (the hard parts first), they panic and quit.
If you let them practice in a sandbox (the easy parts first), they build confidence.
By the time they reach the fire, they know exactly how to handle it.

The researchers found that the Monte Carlo robot was very sensitive to this order because it learns from the whole story. If the story starts with a disaster, the robot thinks the whole game is a disaster. The DQN robot, however, didn't care about the order. Because it uses a "memory bank" that mixes up all its past experiences (good and bad), it couldn't tell the difference between a level that started easy and one that started hard.

Summary

Best Learner: The "Storyteller" (Monte Carlo) was the best at beating the full game because it learned to enjoy the journey, not just the finish line.
Best Teacher: The original World 1-1 design is scientifically proven to be the best way to teach a player. It introduces challenges slowly, which prevents the learner from getting overwhelmed.
The Lesson: In AI (and maybe in life), how you introduce a problem is just as important as what the problem is. If you start too hard, even the smartest algorithms can fail.

Technical Summary: Reinforcement Learning in Super Mario Bros

Problem Statement
Super Mario Bros. World 1-1 is widely celebrated in game design literature as a masterclass in progressive teaching, where the level structure itself introduces mechanics (pipes, gaps, enemies) in a safe, low-stakes order before demanding their integration. However, whether this structure constitutes a genuine, empirically measurable pedagogical curriculum or merely a compelling narrative has never been formally tested. This paper seeks to validate the pedagogical efficacy of World 1-1's canonical design using Reinforcement Learning (RL) as an empirical lens. Specifically, the authors investigate two questions: (1) which RL algorithm learns the level most effectively and whether this depends on complexity, and (2) whether the canonical segment ordering accelerates learning compared to randomized permutations.

Methodology
The authors implemented World 1-1 from scratch as a fully discrete environment, avoiding standard game or RL libraries to ensure a faithful, tile-based representation.

Environment: The level is a 212 × 14 tile grid. Three versions of increasing complexity were created:
- v1 (Static): Ground, pipes, gaps, and stairs.
- v2 (+Blocks): Adds breakable bricks and question blocks.
- v3 (+Enemies): Adds 17 enemies (Goombas and a Koopa) with NES-accurate physics, including stomp mechanics.
State Space: Represented as tuples including column, row, jump phase, and a "viewport" (a tuple of tile codes within the screen window). The state space grows from 3 dimensions in v1 to 115 dimensions in v3.
Algorithms: Four algorithms were compared: Q-Learning, SARSA, Monte Carlo (MC), and Deep Q-Network (DQN). All used $\epsilon$ $ϵ$ -greedy exploration with a shared decay schedule.
- Tabular methods (Q-Learning, SARSA, MC) used exact Q-tables (defaultdict), recording values for visited states without approximation.
- DQN utilized a PyTorch MLP (128-128-3) with experience replay (50k buffer) and target network synchronization.
Curriculum Experiment: The level was partitioned into six canonical segments (A–F). Twelve conditions were tested: the canonical order (A→F), the reversed order (F→A), and ten random permutations. The Monte Carlo agent was selected for this experiment due to its sensitivity to episode-level trajectories.

Key Contributions

Custom Implementation: A Python-based, NES-faithful discrete environment of World 1-1 with three complexity levels, built without external game engines.
Algorithm Benchmarking: A comprehensive comparison of 60 training runs (4 agents × 3 levels × 5 seeds) evaluating tabular vs. function-approximation methods.
Curriculum Validation: A systematic experiment (60 additional runs) sampling the permutation space of the level's segments to test the hypothesis of pedagogical structure.

Results

Algorithm Performance:
- Monte Carlo (MC) emerged as the strongest agent, achieving a 94.9% ± 1.5% win rate on the full level (v3). MC outperformed DQN (76.4%) and tabular TD methods by learning to maximize intermediate rewards (breaking blocks, hitting question blocks) along winning paths rather than taking the most direct route.
- DQN exhibited a "reward-density" dependency. It suffered catastrophic failure on v1 (10.6% win rate) because the replay buffer was flooded with death penalties (−50) relative to sparse positive signals. However, it recovered on v2 (93.4%) when intermediate rewards (question blocks) diversified the signal. On v3, DQN achieved the lowest win rate (76.4%) due to over-generalization, learning to avoid enemies entirely rather than risking stomp rewards (+5).
- Tabular Methods converged on all levels. MC converged fastest on v1 and v2, while SARSA and Q-Learning showed slightly slower convergence on v1 due to exploration conservatism.
Curriculum Learning:
- Canonical Ordering (A→F) was the fastest and most robust condition, achieving a 94.7% win rate with zero catastrophic failures across 10 seeds. It converged to a 50% win rate in ~2,771 episodes.
- Reversed Ordering (F→A) was severely penalized, with a 48.5% win rate and 4 out of 10 seeds failing completely.
- Random Permutations clustered between the two extremes (89.0% mean win rate) but exhibited high variance; no single random permutation matched all three of the canonical condition's criteria (highest win rate, fastest convergence, zero failures).
Mechanism of Sensitivity: The curriculum effect was specific to the update mechanism. DQN showed a null curriculum effect (no significant difference between canonical, reversed, and random orders) because its experience replay buffer uniformly samples transitions, erasing the temporal ordering of easy-to-hard segments. MC, which updates only after full episodes, is highly sensitive to the order of segments.

Significance and Claims
The paper provides the first empirical validation that World 1-1's canonical design encodes a genuine pedagogical structure that measurably accelerates learning and cannot be replicated by chance. The results demonstrate that:

Pedagogical Structure is Real: The specific ordering of segments in World 1-1 is not arbitrary; it optimizes learning efficiency and robustness for agents that rely on trajectory-based signals.
Algorithm Selection Criteria: The choice between tabular methods and DQN should not rely solely on state space size. In discrete, non-uniform environments with sparse rewards, tabular methods (specifically MC) can outperform DQN. DQN's success is contingent on reward density to stabilize the experience replay buffer.
Update Mechanism Sensitivity: The sensitivity to curriculum ordering is driven by the update mechanism. Episode-level learners (MC) benefit from progressive difficulty, while replay-based learners (DQN) are insensitive to temporal ordering due to uniform sampling.

The authors conclude that World 1-1's design is a functional curriculum, not just a narrative, and that its effectiveness is contingent on the agent's ability to utilize the temporal structure of the learning signal.