Q-learning is not a lookup table from states to actions. It's a learned mapping (using any method you want, such as neural networks) from agent history (i.e. th

Q-learning is not a lookup table from states to actions. It's a learned mapping (using any method you want, such as neural networks) from agent history (i.e. the agent is allowed to consider the past) & action pairs, to estimates of future reward, learned through temporal differences between the prediction at time step t, and the sum of new prediction plus immediate reward at time step t+1. In this way, information can flow back in time as the agent learns that some observation is predictive of reward, and then learns some observation is predictive of that observation, and so on until it connects the reward with some action K time steps ago. So long-term planning is definitely possible. This does require that some relevant information be available at each intermediate time step to connect the actions with the ultimate reward. The nice thing about these Atari games is you can usually judge value just by what's immediately on the screen, and in this paper they only use the last three frames' worth of state. In a game requiring a memory for past sensory information (e.g. where information appears on the screen then disappears), this might not do so well, but that's more a matter of working memory than long-term planning, and a different Q-learning system could contain a working memory (e.g. if it was RNN-based).