Playing Super Mario Bros with Deep Reinforcement Learning

In recent years, deep reinforcement learning (RL) has emerged as a powerful approach for building AI agents that can master complex tasks, from robotic control to game-playing. By combining the representational power of deep neural networks with the sequential decision-making of RL, deep RL algorithms have achieved remarkable successes, such as attaining superhuman performance on Atari games and beating world champions at Go and StarCraft.

One classic gaming benchmark that has garnered significant interest from the deep RL community is Super Mario Bros, the iconic platformer game that has captivated players for decades. On the surface, Super Mario Bros may seem like a relatively simple game—guide Mario to the end of each level while avoiding enemies and obstacles. However, from an AI perspective, Super Mario Bros presents several challenges that make it a useful test bed for deep RL:

1. Complex visual state space: The game screen constitutes a high-dimensional input of raw pixels, requiring the agent to learn useful visual representations.

2. Sparse rewards: The main reward signal is for completing a level, which may require thousands of individual steps. The agent must learn to reason over long time horizons.

3. Precision gameplay: Certain actions, like jumps, require precise timing and positioning. The game dynamics also vary across levels.

In this article, we‘ll explore how deep RL can be used to build agents that can master Super Mario Bros. Specifically, we‘ll focus on the Double Deep Q-Network (DDQN) algorithm, a variant of the popular DQN algorithm that addresses the overestimation bias in Q-learning. We‘ll describe the key components of the DDQN algorithm, present experiments comparing it to vanilla DQN, and analyze the results. Along the way, we‘ll highlight practical tips and lessons learned for applying deep RL to other gaming tasks.

Background: Deep Q-Networks

Before diving into DDQN, let‘s briefly review the basics of the DQN algorithm. DQN belongs to the family of value-based RL methods, which estimate the expected cumulative reward, or value, of each state-action pair. The core idea is to use a deep neural network (called the Q-network) to approximate the optimal value function Q*(s, a), which maps a state s and action a to the expected cumulative reward starting from s, taking action a, and following the optimal policy thereafter.

The Q-network is trained to minimize the mean-squared Bellman error between its predicted Q-value and a bootstrap target based on the Bellman equation:

Q(s, a) = r + γ max_a‘ Q(s‘, a‘)

where r is the immediate reward, γ is a discount factor, and s‘ is the next state. The target Q-value is estimated using a separate "target network" whose parameters are periodically updated to match the main Q-network. This helps stabilize training.

To select actions, the agent follows an epsilon-greedy policy based on the Q-values. With probability epsilon, it takes a random action; otherwise, it takes the action with the highest Q-value. The epsilon probability is decayed over time to transition from exploration to exploitation.

DQN also uses an experience replay buffer to store transitions (s, a, r, s‘) experienced by the agent. During training, mini-batches of transitions are sampled from the buffer to update the Q-network. This helps break correlations between sequential experiences and makes more efficient use of past data.

While DQN achieved impressive results on Atari games, it suffers from several issues. One key problem is overestimation bias—because the max operator is used to select the bootstrap action a‘, the Q-network tends to overestimate the values of certain actions, especially early in training when the estimates are noisy.

Double DQN

The Double DQN algorithm addresses the overestimation bias by decoupling action selection and value estimation. The key idea is to use the main Q-network to select the bootstrap action, but the target network to estimate its value. Concretely, the target Q-value is computed as:

Q(s, a) = r + γ Q‘(s‘, argmax_a‘ Q(s‘, a‘))

where Q‘ is the target network. Intuitively, DDQN reduces overestimation by using a separate network to evaluate the greedy policy induced by the main network. It has been shown to significantly improve stability and performance on several benchmarks.

For our Super Mario Bros agent, we use a convolutional neural network for the Q-network, consisting of three convolutional layers followed by two fully connected layers. The input is a stack of four grayscale game screens, downsampled to 84×84 pixels. The output is a vector of Q-values for each action.

We consider three different action spaces:

1. Right only (5 actions): Walk right, jump right, do nothing
2. Simple movement (7 actions): Walk right/left, jump right/left, do nothing
3. Complex movement (12 actions): Walk/run/jump right/left, do nothing

The hyperparameters used for training are:

• Learning rate: 2.5e-4
• Batch size: 32
• Replay buffer size: 100,000
• Target network update frequency: 1000 steps
• Discount factor: 0.99
• Initial exploration (epsilon): 1.0
• Final exploration: 0.1
• Exploration decay: 0.99

We train the agent for 1 million steps using a standard epsilon-greedy approach. The main Q-network is updated every 4 steps by sampling a mini-batch from the replay buffer. The exploration rate is decayed by a factor of 0.99 every 10,000 steps.

Experiments and Results

We evaluated the DDQN agent on the first level of Super Mario Bros, comparing it to a vanilla DQN agent across the three action spaces. The agents were trained for 1 million steps (roughly 2,500 episodes) and evaluated on 100 test episodes with epsilon set to 0.01.

The main results are shown in the figures below. We plot the average reward per episode achieved by each agent over the course of training. The shaded region represents the standard deviation across 3 random seeds.

As we can see, DDQN consistently outperforms DQN on all three action spaces, both in terms of learning speed and final performance. DDQN reaches a higher average reward in substantially fewer episodes compared to DQN. This demonstrates the importance of addressing overestimation bias, especially in a high-dimensional environment like Super Mario Bros.

Comparing across action spaces, both agents perform best with the right-only action space and struggle the most with the complex movement space. This is somewhat expected, as the complex action space is much larger (12 vs 5 actions) and requires more precise coordination (e.g. to execute a running jump). Nevertheless, DDQN is able to make progress and achieve a reasonable score even with complex movements.

In terms of qualitative performance, the learned agents are able to navigate through the level and reach the flag pole roughly 70% of the time with the simple action space. They have learned nuanced behaviors like timing jumps over gaps and enemies, and even discovering "warp zones" that skip portions of the level. While not quite superhuman, the agents have mastered many of the key skills required to beat the level.

Conclusion and Future Work

In this article, we explored how deep reinforcement learning can be used to build AI agents for Super Mario Bros. We described the Double DQN algorithm, which addresses overestimation bias in Q-learning, and showed that it outperforms vanilla DQN on three different action spaces. Our experiments demonstrate that DDQN is a powerful and robust algorithm for learning complex behavior from high-dimensional visual inputs.

There are many exciting directions for future work. One is to scale up the approach to harder Mario levels or even other platformer games like Mega Man or Sonic the Hedgehog. This may require innovations in network architecture, reward shaping, or hierarchical RL to deal with the increased complexity.

Another direction is to incorporate more advanced RL algorithms that have shown promise in recent years. For example, Rainbow DQN combines several extensions to DQN (e.g. prioritized replay, dueling networks) and achieves state-of-the-art performance on Atari. The Agent57 architecture utilizes a meta-controller to adapt its exploration and learning strategy over the course of training. And MuZero learns a model of the game dynamics and uses it to plan future actions. These methods could potentially lead to even stronger Mario agents.

Finally, while beating games is a useful benchmark for AI, we should strive to develop agents that can transfer their knowledge and skills to related problems. Exciting applications of deep RL include robotic control, autonomous driving, and even automated game design. By studying the learning dynamics and representations acquired by our Mario agent, we may gain insights into how to build more general and adaptive AI systems.

We‘ve only scratched the surface of what‘s possible with deep RL and gaming. As algorithms and hardware continue to improve, we can expect to see AI agents tackling ever more complex challenges, from mastering esports to assisting in open-ended game design. Deep RL offers a promising path towards building intelligent agents that can perceive, reason, and act in complex virtual worlds—and perhaps, one day, the real world as well.

Resources

The code for the DDQN Mario agent is available here: [GitHub link]

For more background on deep RL and its applications, we recommend the following resources:

• Sutton and Barto, "Reinforcement Learning: An Introduction": The classic textbook on RL, covering key concepts and algorithms
• Mnih et al., "Human-level control through deep reinforcement learning": The original DQN paper that launched the field of deep RL
• OpenAI, "Spinning Up in Deep RL": A free online educational resource with in-depth tutorials and code for various deep RL algorithms
• DeepMind, "AlphaGo, AlphaZero, and MuZero": Blog posts and papers on DeepMind‘s groundbreaking work on RL for Go, chess, and Atari

We also recommend exploring the thriving open-source ecosystem of RL libraries and environments, such as OpenAI Gym, Stable Baselines, and TensorFlow Agents. These provide a great starting point for applying deep RL to new problems.

Happy learning, and may your Mario agents conquer many levels!