Source-linked AI summary
Learning Montezuma's Revenge from a Single Demonstration
Tim Salimans, Richard Chen
TL;DR
Hard exploration tasks require reinforcement learning to discover long, precise action sequences despite sparse rewards. The paper uses a single demonstration to initialize episodes from demonstration states and gradually moves those starts backward while optimizing returns directly. This reduces the toy task’s exploration complexity from exponential to quadratic and yields a 74,500 score on Montezuma’s Revenge, while performance remains sensitive to perturbations, hyperparameters, and state-matching challenges.
Problem
Sparse rewards make long, precise action sequences extremely unlikely to arise through random exploration, limiting reinforcement learning on tasks such as Montezuma’s Revenge.
Method
The method uses off-the-shelf reinforcement learning from demonstration-state resets, gradually moving the reset point from the demonstration’s end toward the game’s beginning while optimizing returns directly.
Results
The method reduces blind cliff walk exploration complexity from exponential to quadratic and achieves a final score of 74,500 on Montezuma’s Revenge.
Takeaways & Limitations
Resetting from demonstration states converts difficult exploration into a curriculum and enables solutions that can exceed the demonstrator’s score rather than merely imitate its behavior.
Takeaways & Limitations
Performance depends on careful hyperparameter tuning and does not yet generalize robustly to perturbed gameplay or reliably match later demonstration states from earlier ones.
Abstract
from arXiv · showhide
We propose a new method for learning from a single demonstration to solve hard exploration tasks like the Atari game Montezuma's Revenge. Instead of imitating human demonstrations, as proposed in other recent works, our approach is to maximize rewards directly. Our agent is trained using off-the-shelf reinforcement learning, but starts every episode by resetting to a state from a demonstration. By starting from such demonstration states, the agent requires much less exploration to learn a game compared to when it starts from the beginning of the game at every episode. We analyze reinforcement learning for tasks with sparse rewards in a simple toy environment, where we show that the run-time of standard RL methods scales exponentially in the number of states between rewards. Our method reduces this to quadratic scaling, opening up many tasks that were previously infeasible. We then apply our method to Montezuma's Revenge, for which we present a trained agent achieving a high-score of 74,500, better than any previously published result.
1 Introduction
Sparse-reward tasks can make model-free reinforcement learning impractical because success requires long, precise action sequences that random exploration rarely discovers. Montezuma’s Revenge exemplifies this difficulty, with reward probabilities multiplying across required subtasks.
- Exploration difficulty: Model-free reinforcement learning works well with frequent rewards but struggles when success requires long sequences of specific actions.Random actions are reinforced only after reaching a reward, making sparse-reward exploration especially difficult.
- Exploration difficulty: A task requiring a precise sequence of N actions to reach its first reward can require exploration time scaling as exp(N).The first reward is unlikely until the entire sequence occurs successfully.
- Montezuma’s Revenge: In Montezuma’s Revenge, reaching the first key requires navigating chambers while avoiding opponents and traps, with success decomposed into multiple subtasks.The decomposition includes actions such as descending ladders, moving along a rope, jumping over a skull, and climbing another ladder.
- Montezuma’s Revenge: Uniformly random actions in Montezuma’s Revenge produce a reward only about once every half million steps.Multiplying the probabilities of N required actions makes the overall success probability exponentially smaller than each individual probability.
- Motivation: Existing methods for exploration have produced only limited gains on hard tasks such as Montezuma’s Revenge.The paper therefore considers using a single successful demonstration to aid exploration.
2 Method
The method turns sparse-reward exploration into a curriculum by initializing episodes from demonstration states and gradually moving those reset points toward the game’s beginning. Standard reinforcement-learning optimizers then improve the policy until it succeeds without demonstration assistance.
- Curriculum construction: The method decomposes difficult exploration into subtasks by starting each reinforcement-learning episode from a state in a successful demonstration.It uses a distributed setup with parallel rollout workers and a centralized optimizer applying an off-the-shelf RL method.
- Curriculum construction: Episodes initially begin near the demonstration’s end, then reset points gradually move backward as training succeeds.The central optimizer advances this curriculum when rollouts beat or tie the demonstrator’s score often enough.
- Rollout initialization: Each rollout worker samples a nearby local starting point and initializes the recurrent policy using the preceding demonstration segment.The demonstration segment is masked from policy-training data so it does not contribute to the policy-update gradient.
- Training completion: Training ends when the reset point reaches the beginning of the game, indicating that the agent succeeds without using the demonstration at all.At that point, the trained agent beats or ties the human expert demonstration over the entire game.
- Complexity: The curriculum changes the required learning time for a sequence of N actions from exponential to quadratic scaling.Moving the starting state backward ensures each stage presents an easier exploration problem, which the authors interpret as dynamic programming.
- Illustration: Figure 1 illustrates learning from a one-jump start near the key before progressively restoring earlier states until the agent reaches the key from the original start.The intermediate states include the ladder, the skull jump, and the rope leading to the room floor.
3 Related work
Related work addresses difficult exploration through demonstration-based curricula or imitation learning. This paper instead uses demonstration states to construct a dynamically adjusted curriculum while optimizing game returns directly.
- Demonstration-based curricula: Prior work used demonstration states to start episodes, but did not gradually move the starting state backward as a curriculum.The authors report that this gradual curriculum was vitally important for obtaining benefit from the demonstration.
- Demonstration-based curricula: Another curriculum approach iteratively perturbed starting states with random actions and selected states at the desired difficulty.Unlike that approach, this paper selects states from a demonstration.
- Demonstration-based curricula: Concurrent work constructed a similar demonstration-state curriculum, but predefined it for each task rather than dynamically learning it.The paper contrasts that predefined schedule with its dynamically adjusted curriculum.
- Imitation learning: Imitation-learning approaches seek to overcome exploration problems by encouraging behavior that matches a human expert’s demonstration.Examples combine imitation objectives with reinforcement learning or use demonstrations to supervise action selection.
- Imitation learning: Unlike imitation methods, this approach directly optimizes game score and can learn from a single demonstration without overfitting to its behavior.The authors also identify potential benefits when optimizing against opponents different from those in the demonstration.
4 Experiments
Experiments show that demonstration-based resets reduce exploration complexity in blind cliff walk and enable strong Montezuma’s Revenge performance. The experiments also expose evaluation, generalization, computational, and tuning limitations.
- The method was evaluated on blind cliff walk and Montezuma’s Revenge.These environments test scaling on a sparse-reward toy problem and performance on a hard Atari exploration task.
- 4.1 Blind cliff walk: Quadratic rather than exponential runtime scaling was observed when blind cliff walk episodes began from demonstration states.Starting progressively earlier in the demonstration lets the agent learn each state with roughly O(N) steps, for total quadratic scaling.
- 4.2 Montezuma’s Revenge: The demonstration score was 71,500, while the trained Montezuma’s Revenge agent achieved 74,500 over approximately 12 minutes.The agent exceeded the demonstration by collecting more diamonds and using a key-reappearance feature.
- 4.2 Montezuma’s Revenge: Score comparisons are difficult because Montezuma’s Revenge is deterministic and published methods use different amounts of action-selection noise.The reported policy used low entropy, producing small noise comparable to previous best results.
- 4.2 Montezuma’s Revenge: The policy scored 10,000 with sticky actions and 8,400 with random-action perturbations, indicating weaker generalization than a human player.Starting with 0–30 random no-ops did not significantly reduce results.
- 4.2 Montezuma’s Revenge: Training required 128 GPUs for two weeks, preventing a quantitative assessment of consistency across runs.The authors leave systematic reliability analysis for future work, and report difficulty transferring the curriculum to Gravitar and Pitfall.
5 Conclusion
The method replaces imitation-focused learning from demonstrations with direct return optimization, using demonstration-state resets to create a curriculum of subtasks. It does not exactly mimic the demonstrator and achieved a higher Montezuma’s Revenge score than previously published approaches.
- The method optimizes returns directly rather than encouraging behavior identical to a demonstration.
- Demonstration-state resets decompose difficult exploration into a curriculum of subtasks.
- The agent can find solutions that differ from the human demonstrator’s behavior.
- The method achieved a higher Montezuma’s Revenge score than previously published approaches.