What is a high dimensional state in reinforcement learning?

Question

In the DQN paper, it is written that the state-space is high dimensional. I am a little bit confused about this terminology.

Suppose my state is a high dimensional vector of length $N$, where $N$ is a huge number. Let's say I solve this task using $Q$-learning and I fix the state space to $10$ vectors, each of $N$ dimensions. $Q$-learning can easily work with these settings as we need only a table of dimensions $10$ x number of actions.

Let's say my state space can have an infinite number of vectors each of $N$ dimensions. In these settings, Q-learning would fail as we cannot store Q-values in a table for each of these infinite vectors. On the other hand, DQN would easily work, as neural networks can generalize for other vectors in the state-space.

Let's also say I have a state space of infinite vectors, but each vector is now of length $2$, i.e., small dimensional vectors. Would it make sense to use DQN in these settings? Should this state-space be called high dimensional or low dimensional?

Answer 1

Usually when people write about having a high-dimensional state space, they are referring to the state space actually used by the algorithm.

Suppose my state is a high dimensional vector of $N$ length where $N$ is a huge number. Let's say I solve this task using $Q$-learning and I fix my state space to $10$ vectors each of $N$ dimensions. $Q$-learning can easily work with these settings as we need only a table of dimensions $10$ x number of actions.

In this case, I'd argue that the "feature vectors" of length $N$ are quite useless. If there are effectively only $10$ unique states (which may each have a very long feature vector of length $N$)... well, it seems like a bad idea to make use of those long feature vectors, just using the states as identity (i.e. a tabular RL algorithm) is much more efficient. If you end up using a tabular approach, I wouldn't call that a high-dimensional space. If you end up using function approximation with the feature vectors instead, that would be a high-dimensional space (for large $N$).

Let's also say I have a state space of infinite vectors but each vector is now of length $2$ i.e. very small dimensional vectors. Would it make sense to use DQN in these settings ? Should this state-space be called high dimensional or low dimensional ?

This would typically be referred to as having a low-dimensional state space. Note that I'm saying low-dimensional. The dimensionality of your state space / input space is low, because it's $2$ and that's typically considered to be a low value when talking about dimensionality of input spaces. The state space may still have a large size (that's a different word from dimensionality).

As for whether DQN would make sense in such a setting.. maybe. With such low dimensionality, I'd guess that a linear function approximator would often work just as well (and be much less of a pain to train). But yes, you can use DQN with just 2 input nodes.

Answer 2

Yes, it makes sense to use DQN in state space with small number of dimensions as well. It doesn't really matter how big your state dimension is, but if you have state with 2 dimensions for instance you wouldn't use convolutional layers in your neural net like its used in the paper you mentioned, you can use ordinary fully connected layers, it depends on the problem.

Answer 3

In addition to this answer, here's a more formula-based answer, which attempts to clarify the difference between the dimensionality of a state and the size of the state space.

Let's denote our state space, i.e. the space of states, by $\mathcal{S}$. Let's say that $\mathcal{S}$ is a subset of $\mathbb{R}^N$, i.e. $\mathcal{S} \subseteq \mathbb{R}^N$. So, in this case, a state $s \in \mathcal{S}$ is a vector of $N$ real numbers. Depending on $N \in \mathbb{N}$, the dimensionality of the states can be big or not. If $N = 1$, then a state is a real number, so the dimensionality of the state is small. If $N = 10^{40}$, the dimensionality of the state is huge.

To be more concrete, let $\mathcal{S} = \{a, b \}$, $a, b \in \mathbb{R}^N$ and $N= 10^{40}$, then the state space is small, i.e. it contains only 2 states ($a$ and $b$), but the dimensionality of $a$ and $b$ is huge.

You could also have $\mathcal{S} = \{a, b \}$, but $a, b \in \mathbb{R}$. In that case, both the state space and the dimensionality of the states is small.

In machine learning (and in the case of DQN), images, unless they are very small (e.g. $5 \times 5$), are typically considered high dimensional feature vectors (or observations in the case of the DQN). In the case of DQN (figure 1), the input was a $84 \times 84 \times 4$ multi-dimensional array, so each state was relatively high dimensional (i.e. you need $28224$ real numbers to represent each state).