Essentially: NFL says the performance (1 / number of trials are required to find a solution), when averaged over all fitness functions, will be the same for all optimisation algorithms. However, most fitness functions require more computational power than the Universe to evaluate; making even a single trial impossible to perform.
Since those problems are already impossible, it doesn't matter how many trials our optimisation algorithm would require when tackling them. We can use this unobservable bad performance to offset some observable good performance, to remain within the average dictated by NFL whilst still becoming objectively better.
In fact, one of this paper's authors (Shane Legg) has used this fact to define a general intelligence test which favours performance on simple functions http://arxiv.org/abs/0712.3329
Did it really? I think they reset it and retrained it for each game.
I'd like to know how much more is needed to make one instance of the AI that can successfully play any of the games. To play all 49 games that it could learn, does it need to be an extra level deep? Or 49 times larger? Or 2^49 times more?
Having a single instance of an algorithm learn to perform well on many different tasks is really a separate problem than what they're dealing with here.
If they have similar features (which they undoubtedly would), the size could drop a lot.
Of course, I have no training in neural nets, and so my conclusions are reached from general understanding/reasoning.
A person that's played all the other games in the list can win Montezuma's Revenge on the first try; this AI can't play Montezuma's Revenge at all.
This is huge. It shows that the algorithm was able to generalize across multiple problem sets within the same domain of "playing Atari 2600 games", and not simply a "lucky" choice of algorithm, network architecture, or hyperparameters that a random search for each game might choose. This is also not a violation of the No Free Lunch (NFL) Theorem [1], because the domain is limited to playing Atari 2600 games, which share many characteristics.
[1]: https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_op...