Atari games solved by Go-Explore

demo by Uber AI Labs, 2020-04-30

Explanation in video (https:// www.youtube.com/watch?v=EbFosdOi5SY), by Yannic Kilcher :

This algorithm solves the hardest games in the Atari suite and makes it look so easy! This modern version of Dijkstra's shortest path algorithm is outperforming everything else by orders of magnitude, and all based on random exploration.

[source code](https://github.com/uber-research/go-explore)

[full paper](https://arxiv.org/abs/1901.10995), last revised 26 Feb 2021

<https://openai.com/blog/learning-montezumas-revenge-from-a-single-demonstration/>

Model-free RL methods like policy gradients and Q-learning explore by taking actions randomly. If, by chance, the random actions lead to a reward, they are reinforced, and the agent becomes more likely to take these beneficial actions in the future. This works well if rewards are dense enough for random actions to lead to a reward with reasonable probability. However, many of the more complicated games require long sequences of very specific actions to experience any reward, and such sequences are extremely unlikely to occur randomly.

Montezuma’s Revenge Solved by Go-Explore, a New Algorithm for Hard-Exploration Problems (Sets Records on Pitfall, Too)

Problems with infrequent rewards are hard because random actions are unlikely to ever produce reward, making it impossible to learn. Montezuma’s Revenge is one such “sparse reward problem.” Even harder is when the rewards are deceptive, meaning that maximizing rewards in the short term teaches an agent the wrong thing to do with respect to achieving a much higher score overall. Pitfall is deceptive in this way, because many actions lead to small negative rewards (like hitting an enemy), so most algorithms learn not to move at all and as a result never learn to collect hard-to-get treasures. Many challenging real-world problems are both sparse and deceptive.

To be tractable in high-dimensional state spaces like Atari, Go-Explore needs a lower-dimensional cell

representation with which to form its archive. Thus, the cell representation should conflate states that are similar enough to not be worth exploring separately (and not conflate states that are meaningfully different). Importantly, we show that game-specific domain knowledge is not required to create such a representation. We found that what is perhaps the most naive possible cell representation worked pretty well: simply downsampling the current game frame.

Atari is resettable, so for efficiency reasons we return to previously visited cells by loading the game state. On Montezuma’s Revenge, this optimization allows us to solve the first level 45 times faster than by replaying trajectories. However, such access to the emulator is not required for Go-Explore to work; it just makes it faster.

With the downsampled image cell representation, on Montezuma’s Revenge Go-Explore reaches an average of 37 rooms and solves level 1 (which contains 24 rooms, not all of which need to be visited) 65 percent of the time. The previous state of the art [3] explored 22 rooms on average.

In this work, after the agent returns to a cell it explores simply by taking random actions (with a high probability of repeating the previous action). Note that such exploration does not require a neural network or other controller, and all of the exploration in the experiments that follow do not use one (although neural networks are used for robustification). That entirely random exploration works so well highlights the surprising power of simply returning to interesting cells.

The ability of an algorithm to integrate easy-to-provide domain knowledge can be an important asset. Go-Explore provides the opportunity to leverage domain knowledge in the cell representation (though the final neural network still plays directly from pixels only). In particular, we tested a domain-knowledge version of Go-Explore on Montezuma’s Revenge, wherein cells were defined as unique combinations of the x-y position of the agent, the current room, the current level, and the current number of keys held. We wrote simple code to extract this information directly from pixels.

With this improved state representation, Phase 1 of Go-Explore finds a staggering 238 rooms, solves over 9 levels on average, and does so in half the number of emulator steps vs. the downscaled image cell representation.

We believe Go-Explore performs so well on hard-exploration problems because of three key principles:

1. Remember good exploration stepping stones (interestingly different states visited so far)

2. First return to a state, then explore

3. First solve a problem, then robustify (if necessary)

These principles do not exist in most RL algorithms, but it would be interesting to weave them in. As discussed above, contemporary RL algorithms do not do number 1. Number 2 is important because current RL algorithms explore by randomly perturbing the parameters or actions of the current policy in the hope of exploring new areas of the environment, which is ineffective when most changes break or substantially change a policy such that it cannot first return to hard-to-reach states before further exploring from them. This problem becomes worse the longer, more complex, and more precise the sequence of actions required to reach a state is.