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