DeepMind has produced a few agents playing well classic games. When the authors of this paper are saying that these games are NP-hard, they're taking some "poe

DeepMind has produced a few agents playing well classic games. When the authors of this paper are saying that these games are NP-hard, they're taking some "poetic license": complexity classes are defined for problems that have instances of increasing sizes (as the complexity is defined as a function of the size). Super Mario is only one instance. So they analyze generalizations of the game, and as the game size grows to infinity it becomes very hard to play it. For the real games, DL does pretty well (and even simpler agents do well).