Why does it make sense to study MDPs with finite state and action spaces?

Question

In the standard Markov Decision Process (MDP) formalization of the reinforcement-learning (RL) problem (Sutton & Barto, 1998), a decision maker interacts with an environment consisting of finite state and action spaces.

This is an extract from this paper, although it has nothing to do with the paper's content per se (just a small part of the introduction).

Could someone please explain why it makes sense to study finite state and action spaces?

In the real world, we might not be able to restrict ourselves to a finite number of states and actions! Thinking of humans as RL agents, this really doesn't make sense.

Answer 1

In addition to the reason outlined in the comment, also note that if the state-space and action-space are both finite and of feasible size, tabular methods can be used, and there are some advantages to them (like the existence of convergence guarantees and generally a smaller number of hyperparameters to tune).

Answer 2

Note: I assume you mean, countable Action and State Sets by 'Finite'.

MDP(s) are not exclusive to finite spaces only. They can be used in Continuous/uncountable sets of Action and States too.

Markov Decision Process (MDP) is a tuple $(\mathcal S, \mathcal A, \mathcal P^a_s, \mathcal R^a_{ss'}, \gamma, \mathcal S_o)$ where $\mathcal S$ is a set of States, $\mathcal A$ is the set of actions, $\mathcal P_{s}^a: \mathcal A \times \mathcal S \rightarrow [0, 1]$ is a function that denotes Probability distribution over the states if action $a$ is execuited at state $s$. [1][2]

Where, Q-function is defined as:

$$ Q^\pi (s,a) = \mathbb E_\pi \left [ \sum \limits_{t=0}^{+\infty} \gamma(t)r_t | s_o = s, a_o = a \right] \tag{*}$$

Note that $r_t$ is just special case of Reward function $\mathcal R^a_{ss'}$.

Now, if states and actions are discrete, then, the Q-Table Method[3] which is a state-action matrix helps us to evaluate $Q$ function and optimize efficiency.

Whereas, in cases where the state/action sets are infinite or continuous, Deep Networks are preferred to Approximate $Q$ function. [4].

Q-Learning is Off-Policy method, doesn't require $\pi$ policy function

---

References:

1. R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998.
2. Alborz Geramifard, Thomas J. Walsh, Stefanie Tellex, Girish Chowdhary, Nicholas Roy and Jonathan P. How. A Tutorial on Linear Function Approximators for Dynamic Programming and Reinforcement Learning. Foundations and Trends (R) in Machine Learning Vol. 6, No. 4 (2013) 375–454
3. Andre Violante. Simple Reinforcement Learning: Q-learning, Create a q-table, https://towardsdatascience.com, 2019.
4. Alind Gupta. Deep Q-Learning, Deep Q-Learning, https://www.geeksforgeeks.org/deep-q-learning/, 2020.

---

Edit: I'd like to thank @nbro for editing suggestions.

Answer 3

To my knowledge you can't compute or solve an uncountably large MDP numerically. It will need to be discretized in some capacity. The same applies for classic control: you can't optimize over the true functional so you use a discrete approximation to the system and solve that.