Answers.Body: <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-03T18:01:57.503Z
Answers.LastActivityDate: 2019-01-03T18:01:57.503Z
Answers.UserDisplayName: Brale
Answers.Body: <p>In addition to <a href="https://ai.stackexchange.com/a/9830/2444">this answer</a>, here's a more formula-based answer, which attempts to clarify the difference between the <strong>dimensionality</strong> of a state and the <strong>size</strong> of the state space.</p>
  <p>Let's denote our state space, i.e. the space of states, by <span class="math-container">$\mathcal{S}$</span>. Let's say that <span class="math-container">$\mathcal{S}$</span> is a subset of <span class="math-container">$\mathbb{R}^N$</span>, i.e. <span class="math-container">$\mathcal{S} \subseteq \mathbb{R}^N$</span>. So, in this case, a state <span class="math-container">$s \in \mathcal{S}$</span> is a vector of <span class="math-container">$N$</span> real numbers. Depending on <span class="math-container">$N \in \mathbb{N}$</span>, the dimensionality of the states can be big or not. If <span class="math-container">$N = 1$</span>, then a state is a real number, so the dimensionality of the state is small. If <span class="math-container">$N = 10^{40}$</span>, the dimensionality of the state is huge.</p>
  <p>To be more concrete, let <span class="math-container">$\mathcal{S} = \{a, b \}$</span>, <span class="math-container">$a, b \in \mathbb{R}^N$</span> and <span class="math-container">$N= 10^{40}$</span>, then the state space is small, i.e. it contains only 2 states (<span class="math-container">$a$</span> and <span class="math-container">$b$</span>), but the dimensionality of <span class="math-container">$a$</span> and <span class="math-container">$b$</span> is huge.</p>
  <p>You could also have <span class="math-container">$\mathcal{S} = \{a, b \}$</span>, but <span class="math-container">$a, b \in \mathbb{R}$</span>. In that case, both the state space and the dimensionality of the states is small.</p>
  <p>In machine learning (and in the case of DQN), images, unless they are very small (e.g. <span class="math-container">$5 \times 5$</span>), are typically considered high dimensional <em>feature vectors</em> (or <em>observations</em> in the case of the DQN). <a href="https://storage.googleapis.com/deepmind-media/dqn/DQNNaturePaper.pdf" rel="nofollow noreferrer">In the case of DQN (figure 1)</a>, the input was a <span class="math-container">$84 \times 84 \times 4$</span> multi-dimensional array, so each state was relatively high dimensional (i.e. you need <span class="math-container">$28224$</span> real numbers to represent each state).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-03T18:59:20.890Z
Answers.LastActivityDate: 2021-02-04T11:00:31.317Z
Answers.LastEditDate: 2021-02-04T11:00:31.317Z
Answers.UserDisplayName: nbro
Answers.Body: <p>Usually when people write about having a high-dimensional state space, they are referring to the state space actually used by the algorithm.</p>
  
  <blockquote>
    <p>Suppose my state is a high dimensional vector of <span class="math-container">$N$</span> length where <span class="math-container">$N$</span> is a huge number. Let's say I solve this task using <span class="math-container">$Q$</span>-learning and I fix my state space to <span class="math-container">$10$</span> vectors each of <span class="math-container">$N$</span> dimensions. <span class="math-container">$Q$</span>-learning can easily work with these settings as we need only a table of dimensions <span class="math-container">$10$</span> x number of actions. </p>
  </blockquote>
  
  <p>In this case, I'd argue that the "feature vectors" of length <span class="math-container">$N$</span> are quite useless. If there are effectively only <span class="math-container">$10$</span> unique states (which may each have a very long feature vector of length <span class="math-container">$N$</span>)... 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 <span class="math-container">$N$</span>).</p>
  
  <blockquote>
    <p>Let's also say I have a state space of infinite vectors but each vector is now of length <span class="math-container">$2$</span> 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 ? </p>
  </blockquote>
  
  <p>This would typically be referred to as having a low-dimensional state space. Note that I'm saying low-<strong>dimensional</strong>. The <strong>dimensionality</strong> of your state space / input space is low, because it's <span class="math-container">$2$</span> 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 <strong>size</strong> (that's a different word from <strong>dimensionality</strong>).</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-05T13:36:55.897Z
Answers.Text: I have seen some examples where people map their low dimensional vectors to high dimensions by using [kernel approximation techniques](https://scikit-learn.org/stable/modules/generated/sklearn.kernel_approximation.RBFSampler.html) before feeding it to the neural net.  Do you think this is a good approach ?
Answers.UserDisplayName: Siddhant Tandon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-05T14:10:19.780Z
Answers.Text: @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.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-04T16:20:14.967Z
Answers.LastActivityDate: 2019-01-04T16:20:14.967Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>In <a href="https://storage.googleapis.com/deepmind-media/dqn/DQNNaturePaper.pdf" rel="nofollow noreferrer">the DQN paper</a>, it is written that the state-space is high dimensional. I am a little bit confused about this terminology.</p>
  <p>Suppose my state is a high dimensional vector of length <span class="math-container">$N$</span>, where <span class="math-container">$N$</span> is a huge number. Let's say I solve this task using <span class="math-container">$Q$</span>-learning and I fix the state space to <span class="math-container">$10$</span> vectors, each of <span class="math-container">$N$</span> dimensions. <span class="math-container">$Q$</span>-learning can easily work with these settings as we need only a table of dimensions <span class="math-container">$10$</span> x number of actions.</p>
  <p>Let's say my state space can have an infinite number of vectors each of <span class="math-container">$N$</span> 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.</p>
  <p>Let's also say I have a state space of infinite vectors, but each vector is now of length <span class="math-container">$2$</span>, 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?</p>
  
Tags: <reinforcement-learning><q-learning><dqn><terminology><state-spaces>
Title: What is a high dimensional state in reinforcement learning?
UserDisplayName: Siddhant Tandon
ThreadText: # What is a high dimensional state in reinforcement learning?
  
  (Asked by: username_0 on 2019-01-03)
  
  In [the DQN paper](https://storage.googleapis.com/deepmind-media/dqn/DQNNaturePaper.pdf), 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?
  
  **Tags:** reinforcement-learning, q-learning, dqn, terminology, state-spaces
  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_3 on 2019-01-04. Score: 4 | Accepted answer
  
  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.
  
  > **Comments:**
  > **username_0**: I have seen some examples where people map their low dimensional vectors to high dimensions by using [kernel approximation techniques](https://scikit-learn.org/stable/modules/generated/sklearn.kernel_approximation.RBFSampler.html) before feeding it to the neural net.  Do you think this is a good approach ?  
  > **username_3**: @username_0 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.  
  
  ---
  
  ### Answer by username_1 on 2019-01-03. Score: 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 by username_2 on 2021-02-03. Score: 0
  
  In addition to [this answer](https://ai.stackexchange.com/a/9830/2444), 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)](https://storage.googleapis.com/deepmind-media/dqn/DQNNaturePaper.pdf), 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).
  
  
  ---
  
  