2
$\begingroup$

Going through the DQN paper, it said the state-space is high dimensional. I am a little bit confused here. 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.

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. Meanwhile on the other hand DQN would easily work as neural networks can generalize for any vector 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. 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?



See: Human-level control through deep reinforcement learning (Nature, 2015)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have seen some examples where people map their low dimensional vectors to high dimensions by using kernel approximation techniques before feeding it to the neural net. Do you think this is a good approach ? $\endgroup$ – Siddhant Tandon Jan 5 at 13:36
  • $\begingroup$ @SiddhantTandon That kind of stuff can be done in RL yes (see e.g. chapter 9 of 2nd edition of Sutton and Barto's book)... but I don't have a lot of experience with that personally. That should typically only be necessary with linear function approximation though, not with DNNs. DNNs should already be powerful enough to work with raw features, as long as they're large/deep enough. $\endgroup$ – Dennis Soemers Jan 5 at 14:10
  • $\begingroup$ Dennis, do you know offhand the paper the OP refers to? (I'd like to link it in the question.) $\endgroup$ – DukeZhou Nov 14 at 21:12
  • 2
    $\begingroup$ @DukeZhou "the DQN paper" should usually be this one: nature.com/articles/nature14236 $\endgroup$ – Dennis Soemers Nov 15 at 9:42
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.