Learning Montezuma’s Revenge from a Single Demonstration

OpenAI has developed a reinforcement learning (RL) agent capable of achieving a high score of 74,500 on the Atari game Montezuma’s Revenge, surpassing all previously published results. The agent achieves this by optimizing the game score using Proximal Policy Optimization (PPO) while utilizing a single human demonstration to bypass the inherent difficulties of exploration in sparse-reward environments.

The Exploration Problem in Sparse-Reward Games

Reinforcement learning agents typically struggle with games like Montezuma’s Revenge because they rely on random exploration to find rewards. In environments where rewards are sparse and require long, precise sequences of actions, the probability of randomly stumbling upon a reward scales exponentially with the length of the sequence (exp(N)).

For example, obtaining the first key in Montezuma’s Revenge requires a specific sequence of actions: descending ladders, crossing ropes, and jumping over obstacles. The total probability of success is the product of the probabilities of each individual action, making the likelihood of a random agent succeeding extremely low.

Simplifying Exploration via Demonstration-Based Curricula

To solve the exploration problem, OpenAI disentangled exploration from learning by using a human demonstration to construct a curriculum of subtasks. Instead of starting every episode from the beginning of the game, the agent starts from carefully chosen states within the demonstration.

The Reverse Curriculum Process

The agent follows a reverse-order learning process:

End-State Initialization: The agent begins training by starting episodes near the end of the human demonstration.
Incremental Regression: Once the agent can beat or tie the demonstrator's score for the remaining portion of the game in at least 20% of rollouts, the starting point is moved backward in time.
Full Game Mastery: This process continues until the agent can start from the original beginning of the game and reach the goal independently.

This approach transforms an exponential exploration problem into one that scales linearly with the number of actions (N), effectively treating the RL problem as a form of dynamic programming.

Comparison to Imitation Learning

Unlike imitation-based approaches—which train agents to mimic specific states or actions from a demonstration—OpenAI's method directly optimizes the game score. This distinction provides several advantages:

Avoids Overfitting: The agent is not bound to a potentially sub-optimal human demonstration.
Performance Optimization: The agent can discover new solutions that the human demonstrator may not have considered.
Versatility: The method is better suited for multi-player games where the goal is to outperform opponents rather than simply imitating a specific player.

Technical Challenges and Generalization

Despite the simplified exploration, the agent faces several technical hurdles:

State Generalization

The agent often cannot reach the exact state from the demonstration due to differences in frameskip and inherent randomness in actions. Consequently, the agent must be able to generalize between states that are very similar but not identical. While this worked for Montezuma’s Revenge, it proved less effective for games like Gravitar and Pitfall, which OpenAI attributed to harder vision problems.

Hyperparameter Tuning

Achieving the high score required precise tuning of the PPO entropy bonus coefficient, learning rate, and reward scaling. The algorithm still exhibits significant random variation, with some runs failing to converge.

Robustness and Perturbations

To test generalization, OpenAI applied perturbations to the policy:

Sticky Actions: Repeating the last action with a 0.25 probability resulted in an average score of 10,000.
Random Actions: Introducing random actions with a 0.01 probability led to an average score of 8,400.

While these perturbations reduce the score, the results remain superior to previously published benchmarks.