Deep Mind Playing Montezuma's Revenge with Intrinsic Motivation [video] | Hacker News Reader

Deep Mind Playing Montezuma's Revenge with Intrinsic Motivation [video]

youtube.com

If you end up blocked by a popup blocker, or just don't feel like reading fluff, or like me you've got the browser locked down too tightly for their integrated video player to work, the paper is at https://arxiv.org/pdf/1606.01868v1.pdf and the video mentioned is (probably, since I didn't see the original) at https://www.youtube.com/watch?v=0yI2wJ6F8r0 .

Thanks. We've changed the URL from http://www.wired.co.uk/article/google-ai-montezuma-revenge. At first to https://arxiv.org/abs/1606.01868, but since everyone's going to want to watch the video, that seems a bit too abstruse. Hopefully someone will say meaningful things about the paper too.

I look forward to the day when you are taunted on the Starcraft boards for playing "like an AI" :-)

That said, game theory has always been an excellent way to analyze AI systems. And using "modern" games (which generally provide attractive skins over a classic mechanic) certainly makes it easier to watch/sit through. When DeepMind starts beating people playing Diplomacy then we'll know we're in a whole new game.

Indeed, I can't wait for the day we see DeepMind (or its ilk) playing games like StarCraft, I expect it'll be quite uncanny.

Is it really true that Montezuma's Revenge is more challenging for DeepMind than Go, as they mention in the article?

Isn't DeepMind just an umbrella term like Watson? I would guess that AlphaGo and the software that learns games like this are distinct.

DeepMind is the name of an AI company that was acquired by Google.

https://deepmind.com/

AlphaGo is the program that beat Go. These game playing algorithms are variations of Deep Q Learning Reinforcement Learning algos.

And here's the related paper, "Unifying Count-Based Exploration and Intrinsic Motivation": https://arxiv.org/abs/1606.01868

Tech journalism isn't at its best when it can't distinguish between WOPR and a team of researchers.

DeepMind's main intellectual property, the reason why it was acquired, was DeepMind's reinforcement algorithm. The present paper, like the work on AlphaGo, is about improving this reinforcement algorithm.

I don't believe that's the case. The Atari results were achieved via Q-Learning with neural networks (DQN stands for Deep Q-Networks), both of which have been around for decades. The basic algorithm is something you can implement yourself fairly easily, but (as with most things involving neural nets) getting it to really perform takes a bit of expertise.

So, DeepMind's greatest asset is they employ some really excellent people and have a substantial head start in terms of actually implementing AIs and getting them to work.

Since Deepmind hasn't beaten Montezuma's Revenge yet, and has been cracking away at it along with a number of other researchers for years, empirically, the answer would seem to be yes.

(I know the article says that it's been beaten, but it's wrong: it's improving over DQN by being able to explore 15 rooms rather than 2 rooms, but it hasn't cleared the first level, much less the whole game. An interesting breakthrough in how to define novelty in the ALE but not something as striking as AlphaGo.)

Montezuma's Revenge, Castle Wolfenstein (not the shooter), and puzzle games in general have a problem of long term credit assignment and sparse reward. This "intrinsic reward" approach form the paper, based on pseudo counts seems to be one way to get an intermediate reward which helps the model learn toward an overall goal (winning/progress) which happens rarely. The previous best work had to pre-define the intrinsic rewards as I understand it [0], and DeepMind has been tracking this general problem for a while [1] along with a whole bunch of earlier work from the 70s/80s/90s (cited in the background of this new paper).

Credit assignment in a nutshell is "what actions helped me get reward"? For action games this is fairly easy - there are only a few moves between rewards. For puzzlers, something like left, up, right, up, left, left, left, left, up, up could get a reward. We can see there is a cycle in there which is probably not necessary, but maybe this was a much longer path than the ideal as well. Deciding which moves should get credit is a hard problem, but an important one. [2]

If you look at the results of the original DQN paper [3] you will see the games they fared best were ones where there were frequent rewards (e.g. Breakout). Things that are puzzle-like (such as Q-Bert) fared much worse versus human benchmarks, whereas action games like Breakout (which is fully observable given 4 frame context IIRC) were generally better than the human benchmark.

This paper seems to be a big step toward deep RL for more than just short term decisions and a huge jump towards goal oriented planning.

[0] Kulkarni et. al https://arxiv.org/abs/1604.06057

[1] Mohamed, Rezende https://arxiv.org/pdf/1509.08731.pdf

[2] http://www.scholarpedia.org/article/Reinforcement_learning#....

[3] Nature results are better but paywalled :/ NIPS paper here https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf . http://www.nature.com/nature/journal/v518/n7540/abs/nature14... - Figure 3

Thank you, that was an excellent summary!

On a somewhat related note, it seems clear that AI research and breakthroughs are occurring at breakneck speed. I wish there was a place where you could see expert commentary like your in layman terms on interesting or important papers that stand out.

The reddit r/machinelearning subreddit has generally higher quality technical discussion than HN, although kastnerkyle's comment is really great.

To be fair, DeepMind spent 2 years with millions of resources and a whole team of researchers and programmers on Go. I'm pretty sure they could solve Montezuma's Revenge in less than a year with the same resources (but there's no need to).

I'd be surprised if it isn't, in many ways. Go is highly different from our normal reality so we have to learn how a series of very specific rules interact with each other and learn useful patterns.

Games like Montezuma's Revenge allow us to re-use huge amounts of already known information. We recognise there's a little person, and that's who we're controlling. We have expectations around what a jump might mean and that we probably shouldn't touch the skulls. We expect that moving off the screen to the next room then back goes to the first screen again. The game, in many ways, acts similarly to our normal reality (object persistence, motion, etc). We know we want to survive. We can even read the text on the screen and focus on increasing the numbers.

The AI has just has pixel values, and none of this information. It doesn't know about jumping, reality or skulls. It has a grayscale 42x42 view of something and is given a few ways of poking this world.

Edit - Perhaps another way of looking at it is this:

In go, you have 19x19 positions which can be in one of just 3 states. You must choose a move to make out of a large number of possibilities. This is repeated and the world changes very slowly.

In this game, you have 42x42 positions which can each be in a much larger number of possible states (somewhere between 8 and 128 I think). You have only a few possible moves but the world changes rapidly and sometimes completely. The interactions between the way the world changes in response to your actions are significantly more complicated.

One thing is that for this kind of research, the goal seems to be "learn to play a game from scratch without any prior knowledge of the rules, physics, map, etc.". If you just wanted an AI that could beat Montezuma's Revenge, you could probably write one quite easily by giving it explicit knowledge of physics, hazards, goals, and strategy.

For example, last year an AI beat NetHack (an incredibly complicated game that I think gamers can agree is "harder" than Montezuma's Revenge, although it's turn-based rather than real-time) for the first time. But the NetHack-winning AI didn't learn to play NetHack like a human would, and the prospect of that is incredibly remote.

Instead, the NetHack AI was hard-coded full of extremely detailed domain knowledge about NetHack items, maps, commands, monsters, goals, etc., and used search strategies to explore the dungeon and perform specified tasks given that knowledge. So it was barely doing any learning at all (although the dungeon map, starting inventory, and item descriptions are randomized on every play, so it did have to learn those things each time, and had explicit strategies for doing so).

The from-scratch success at video games is what most impressed people about DeepMind's original work; they were able to beat a whole lot of Atari games without telling the AI how to play. But if you see the level of complexity of those Atari games, writing an AI to play them would not have been such an impressive feat in itself. Although Montezuma's Revenge is a lot more complicated than something like Breakout, I think exactly the same consideration applies here. A computer could easily be the best Montezuma's Revenge player in the world already, but getting it there without encoding knowledge of the game calls for substantive new research.

This is interesting but it's still far from how a human would learn how to play the game. Humans don't have inbuilt rewards for Montezuma's Revenge, they acquire them culturally. How much of what was learned (by the machine, not the researchers) in playing Montezuma's Revenge could be applied to a game like Zelda? A human would instantly notice many of the connections between the two games: enemies that follow simple patterns and harm the player on contact, rooms that connect to one another laid out on a grid pattern, single use consumable keys that open doors, valuable gems to collect. Is the machine able to make any of these connections on its own?

I think if you watch a child play anything, even a video game, you'll see that when it's not immediately obvious what to do, a human will just 'mess around' and 'try stuff out' to 'just to see what happens'. As the paper says, the idea of novelty bonuses in reinforcement learning draws directly from discussions of curiosity and play and intrinsic motivation in animals and humans.

Initially, yes, but then as a human learns more about the game they begin to make plans at a much higher level than just the basic mechanics of moving around. In the video, the machine continues to die in very basic ways even after a hundred million iterations. A human who had played the game even a tiny fraction of that many times would be expected to complete an entire play-through flawlessly.

And this still doesn't address my original question. A human who was able to master Montezuma's Revenge would have a dramatic advantage in learning and mastering the game Zelda compared to somebody who had played neither game before. What experience, if any, could this machine be expected to bring to Zelda, assuming no modification by the researchers?

You would get some boost if you use a NN factored to have game-specific module feeding into a universal game-playing NN: https://arxiv.org/abs/1511.06342 " Actor-Mimic: Deep Multitask and Transfer Reinforcement Learning", Parisotto et al 2015

> The ability to act in multiple environments and transfer previous knowledge to new situations can be considered a critical aspect of any intelligent agent. Towards this goal, we define a novel method of multitask and transfer learning that enables an autonomous agent to learn how to behave in multiple tasks simultaneously, and then generalize its knowledge to new domains. This method, termed "Actor-Mimic", exploits the use of deep reinforcement learning and model compression techniques to train a single policy network that learns how to act in a set of distinct tasks by using the guidance of several expert teachers. We then show that the representations learnt by the deep policy network are capable of generalizing to new tasks with no prior expert guidance, speeding up learning in novel environments. Although our method can in general be applied to a wide range of problems, we use Atari games as a testing environment to demonstrate these methods.

   A human would instantly notice many ...

But isn't that exactly what Schmidthuberian intrinsic motivation is about? In Schmidthuber's account, which inspired the paper under discussion, intrinsic motivation is measured by the improvements (= better compression) to a predictive world model made by the learning algorithm.

[1] J. Schmidhuber. Formal theory of creativity, fun, and intrinsic motivation.

This ability to apply knowledge gained in one domain to another is called transfer learning, and it's not really known how to do it well for AI. My layman's understanding of memory-augmented neural-networks (e.g. neural turing machines) suggests that this is a promising avenue, but there are no clear answers yet.

I think this technique -- in the title of the paper -- would transfer somewhat to other games, because it essentially encourages the player to go places it hasn't been [without simultaneously having it explore everything thoroughly].

So you use existing tools to encourage the player to survive, and then you add additional motivation to encourage the player to learn what it needs to do [ie explore]. And exploration is a common theme in games like Zelda.

I actually think that this technique will generalize to learning lots of games [eg the same engine might play Zelda & Montezuma's Revenge], but I don't think techniques in this vein alone will allow it to learn how to play one game and then immediately understand how to play the other.

[but "transfer learning" is a separate, challenging problem in AI]

That's a shame. For a human, each game played helps to make the person better at all games. Play enough adventure games, for example, and one begins to recognize so many of the patterns and tropes at work that the solutions to puzzles jump out obviously and immediately in a single play-through.

Moreover, we already have machines that are extremely proficient at solving very complex games when given enough context: expert systems. One very notable example is the bot which successfully completed the game NetHack [0]. Would DeepMind's novelty-based reward technique work for NetHack?

[0] https://github.com/krajj7/BotHack

Agreed. I think it's a pretty big open problem for ML / AI. How can learning about one thing help you do better at a related thing?

Because you're absolutely right that a human who is good at one platformer will take very little time to adjust to a new one.

I don't know much about NetHack, but seeing that it's a Roguelike, I think these new techniques should definitely be tried on it or something similar.

On behalf of all who have "played" Montezuma's Revenge for real, let me say we look forward to the day when it can be outsourced to the Cloud.

https://en.wikipedia.org/wiki/Montezuma%27s_Revenge

It might be a interesting future if computers become powerful enough to be able to run this kind of IA. Then games companies might be able to use directly a generic IA like this instead of developing specific ones. But I suppose it will be hard to do and won't happen (if it does) before a long time.

So lets say I take the trained network, and flip the color of the pixels, and make some other cosmetic changes (keeping the game intact). Will the network then solve it in the first try?

The ALE agents are almost always using grey-scale pixels in the first place (to save on processing and NN space requirements), so flipping the color makes no difference.

Is it learning the specific level layout or can it adapt when the screens are different and order swapped?

DQN is stateless, so at every point it's reacting to just the current frame (technically, the average of the last 4 frames IIRC) being fed into a CNN and outputing a motion. It doesn't care about ordering all that much because it has no memory. In this case, it's probably learning stuff like 'if there's a key, go towards it' and 'if you have a key, go towards a barrier'. If each screen keeps working the same way, then I guess it would achieve about the same performance as it does now. New screens with new layouts/patterns of enemies will test how well its learned heuristics generalize, though.

Personally, I think that someone should be trying a DQN with an RNN rather than CNN in it to see if that helps on the harder levels. Or better yet, combine it with some of the memory mechanisms and see if it can start doing some real long-term planning.

I believe the input state is the past 4 frames stacked or concatenated.

I think in general these types of neural networks are flexible enough to be resistant to trivial changes like this- Whether that specific change for this specific NN would affect results would likely need to be checked empirically.

I have a feeling DeepMind AI will specialize in playing video games

Here's one impressive counterexample: https://arxiv.org/abs/1604.08772

Once it gets really good at video games, you can then put it into a robot. How is the real world different than a video game? Navigating a 3d environment, planning, etc, are all important skills needed in "real life" AI. And deepmind has been making great progress on some of them.

I'm confused by the subtitle of the linked article, which says "The AI system was able to solve the complex game in just four tries". But the video shows the AI dying many more times than that, and not ultimately winning the game, just learning to explore a portion of it successfully.

What did the Wired editor mean by "solve" and "four tries"? (Or, for that matter, "complete"?)

Given that this is what the paper (linked by jerf) says:

within a fraction of the training time, our agent explores a significant portion of the first level and obtains significantly higher scores than previously published agents

... it's probably just the usual hype.

Oh, I think I get it now. I think they mean that in one play [ie 4 lives], it solves significantly more than any previous network.

The text of the article is cut in half for me. Can anyone else confirm the same rendering behavior?

http://i.imgur.com/FfcXAmi.png

I am on Windows 7 using Chrome 51.0.2704.79 m and the text issue occurs in incognito mode as well.

Works for me on Windows 7 with Chrome 51.0.2704.84 m.

Win7 using Firefox. Text issue for me, I can't read it.

Super confused.

Mon·te·zu·ma's re·venge (noun, informal)

Diarrhea suffered by travelers, especially visitors to Mexico.

It's a video game for Apple II which is named after the illness.

https://en.wikipedia.org/wiki/Montezuma's_Revenge_%28video_g...

Reply on news.ycombinator.com