How do the Atari games constitute a finite MDP?

Question

I am still new to Deep-RL. I was reading DeepMind's paper "Playing Atari with Deep Reinforcement learning" and am having trouble understanding how these games can be represented as a finite markov decision process. Don't these games technically have an infinite number of possible states and possible actions?

The paper explains that:

Since the agent only observes images of the current screen, the task is partially observed and many emulator states are perceptually aliased, i.e. it is impossible to fully understand the current situation from only the current screen x_t. We therefore consider sequences of actions and observations, s_t = x₁,a₁,x₂,...,a_t-1,x_t, and learn game strategies that depend upon these sequences. All sequences in the emulator are assumed to terminate in a finite number of time-steps. This formalism gives rise to a large but finite Markov decision process (MDP) in which each sequence is a distinct state. As a result, we can apply standard reinforcement learning methods for MDPs, simply by using complete sequence s_t, as the state representation at time t.

I fail to see the correlation between the sequences terminating in a finite number of time-steps to the rise of finite MDP. Is it saying that the finite MDP, in this instance, is just an insanely large chain that has "info" on almost all the possible sequences? Therefore, it can make predictions on the best action for any given state that the emulator sees? If possible could you give me an example of games which are continuous state spaces and explain why? Thanks!

DeepMind Paper: Link

Answer 1

Suppose that a screen $x_t$ can be encoded as a vector of $P$ pixels and each pixel can take on $R$ possible values. Also assume $A$ possible actions.

(In Atari games the action space is discrete and finite -- our actions at each timestep are the buttons "UP/DOWN/LEFT/RIGHT/...".)

Then there are $PR \cdot A$ possible pairs $(x_t, a_t)$, and with an upper bound of $T$ timesteps, there are $PR + PR \cdot A \cdot (1 + 2 + \dots + T-1)$ possible sequences, ie states. So we have a finite number of states and a finite number of actions (and therefore a finite MDP).

Later in the paper the authors reduce the size of these inputs by using a feature-extracting function φ:

Since using histories of arbitrary length as inputs to a neural network can be difficult, our Q-function instead works on fixed length representation of histories produced by a function φ.

The Deep Q-learning network used in this paper predicts the Q-value of each action from the state features. So in other words, the neural net assigns a score to each action that the agent can take. After an exploration phase, the agent will always choose the action that has the highest predicted Q-value.