Answers.Body: <p>Whilst engineering solutions in reinforcement learning, I think it is common to discuss the concept of state space loosely, in terms of what the search space looks like for the algorithm, and what compromises are OK even though they technicaly make the problem a POMDP.</p>
  <p>In terms of definitions relating to the MDP, the state space has well-defined meaning. It is the set of all state values that can occur in the environment. That set/space can be mapped into different domains, but it remains the same size of space in terms of the set for any bidirectional mapping.</p>
  <p>Once you start to implement a state representation in a real system, in a practical agent, you often need to compromise regarding this definition. Even in purely mathematical treatments, it may not be convenient to determine all the theoretically reachable states. Determining them can be more complex than the optimal control problem. So it is very common to over-specify the state space.</p>
  <p>Atari games don't reach states where they produce arbitrary images. Their output during gameplay is on a relatively small manifold embedded in image space. Despite this, the over-specification in image space is useful, because we have good toolkits for working with it, including CNNs for learning generalising function outputs when images are used as inputs.</p>
  <p>Another compromise seen in the original Atari DQN is missing state. Only using the image, even when stacked, can mean a certain amount of state is not being used. Depending on the game, this state could be important enough that a POMDP would make a better model, and the images would move from a state space representation to an observation space representation (as an aside, stacking images to include velocity information could be replaced by a sequence-aware model such as RNN, and this is similar to POMDP approach, building an internal state representation separate from observations).</p>
  <p>In both cases - over-specified state space, and missing state - the state space of the <em>problem</em> is not changed. When implementing the agent, you know the representation space you are using, and expect it to have good <em>coverage</em> of all possible states, but often do not know the precise underlying state space of the MDP.</p>
  <p>This further gets confounded by feature engineering. I would treat the embedding by pre-trained CNN as a form of feature engineering. In theory it could reduce the dimensionality of the optimisation problem significantly, speeding up learning, but there is always a risk that the pre-training misses key features due to differences that are important in RL context having a low weighting in unsupervised learning of the embeddings.</p>
  <p>So does converting an RL problem that works with images from vision-based observations, to work with embeddings of those images reduce the state space? I would say no, the problem definition is not changed, it has the same state space as before. However, the separation of concerns (vision processing vs policy or value prediction), and lower dimension space for generalising has still done something useful. It may help with generalisation, as similar states may be be closer in the embedding space than they are in the larger image space.</p>
  <p>Loosely speaking you <em>could</em> say that CURL &quot;reduces state space&quot; and most people would understand what you meant in practical terms. I would personally caveat that with e.g. &quot;<em>effectively</em> reduces state space&quot; or perhaps &quot;makes it easier for the agent to generalise its experience across the state space&quot;.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-25T21:47:36.720Z
Answers.Text: thanks for this Neil, a great answer as always!
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-25T17:59:34.693Z
Answers.LastActivityDate: 2022-01-25T19:07:04.267Z
Answers.LastEditDate: 2022-01-25T19:07:04.267Z
Answers.UserDisplayName: Neil Slater
Body: <p>In the classic Atari environments, like that introduced in the <a href="https://www.datascienceassn.org/sites/default/files/Human-level%20Control%20Through%20Deep%20Reinforcement%20Learning.pdf" rel="nofollow noreferrer">original DQN paper</a>, the state space is the set of all possible images that the Atari emulator can produce (or more generally just any RGB image, potentially stacked to better represent the environment). This makes sense as the CNN in the DQN is trained end-to-end with the RL signal, and so the Q-Fuction looks directly at the image as input.</p>
  <p>Now, in methods such as <a href="https://arxiv.org/pdf/2004.04136" rel="nofollow noreferrer">CURL</a> that look to pre-train the CNN and treat it as an encoder, does the state space change here? My thinking is that, if the pre-trained encoder is a function <span class="math-container">$\psi: \mathcal{I} \rightarrow \mathbb{R}^d$</span>, where <span class="math-container">$\mathcal{I}$</span> is the space of images, then the state space is now <span class="math-container">$\mathbb{R}^d$</span>. The rationale for my thinking is that now the agent directly observes the vector in <span class="math-container">$\mathbb{R}^d$</span> rather than the image from the encoder, and the state space should be what the agent observes (even though this vector is a representation for the image).</p>
  
Tags: <reinforcement-learning><markov-decision-process><state-spaces>
Title: Does the state space of an MDP change in these two examples?
UserDisplayName: David
ThreadText: # Does the state space of an MDP change in these two examples?
  
  (Asked by: username_0 on 2022-01-25)
  
  In the classic Atari environments, like that introduced in the [original DQN paper](https://www.datascienceassn.org/sites/default/files/Human-level%20Control%20Through%20Deep%20Reinforcement%20Learning.pdf), the state space is the set of all possible images that the Atari emulator can produce (or more generally just any RGB image, potentially stacked to better represent the environment). This makes sense as the CNN in the DQN is trained end-to-end with the RL signal, and so the Q-Fuction looks directly at the image as input.
  
  Now, in methods such as [CURL](https://arxiv.org/pdf/2004.04136) that look to pre-train the CNN and treat it as an encoder, does the state space change here? My thinking is that, if the pre-trained encoder is a function $\psi: \mathcal{I} \rightarrow \mathbb{R}^d$, where $\mathcal{I}$ is the space of images, then the state space is now $\mathbb{R}^d$. The rationale for my thinking is that now the agent directly observes the vector in $\mathbb{R}^d$ rather than the image from the encoder, and the state space should be what the agent observes (even though this vector is a representation for the image).
  
  **Tags:** reinforcement-learning, markov-decision-process, state-spaces
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-01-25. Score: 2 | Accepted answer
  
  Whilst engineering solutions in reinforcement learning, I think it is common to discuss the concept of state space loosely, in terms of what the search space looks like for the algorithm, and what compromises are OK even though they technicaly make the problem a POMDP.
  
  In terms of definitions relating to the MDP, the state space has well-defined meaning. It is the set of all state values that can occur in the environment. That set/space can be mapped into different domains, but it remains the same size of space in terms of the set for any bidirectional mapping.
  
  Once you start to implement a state representation in a real system, in a practical agent, you often need to compromise regarding this definition. Even in purely mathematical treatments, it may not be convenient to determine all the theoretically reachable states. Determining them can be more complex than the optimal control problem. So it is very common to over-specify the state space.
  
  Atari games don't reach states where they produce arbitrary images. Their output during gameplay is on a relatively small manifold embedded in image space. Despite this, the over-specification in image space is useful, because we have good toolkits for working with it, including CNNs for learning generalising function outputs when images are used as inputs.
  
  Another compromise seen in the original Atari DQN is missing state. Only using the image, even when stacked, can mean a certain amount of state is not being used. Depending on the game, this state could be important enough that a POMDP would make a better model, and the images would move from a state space representation to an observation space representation (as an aside, stacking images to include velocity information could be replaced by a sequence-aware model such as RNN, and this is similar to POMDP approach, building an internal state representation separate from observations).
  
  In both cases - over-specified state space, and missing state - the state space of the *problem* is not changed. When implementing the agent, you know the representation space you are using, and expect it to have good *coverage* of all possible states, but often do not know the precise underlying state space of the MDP.
  
  This further gets confounded by feature engineering. I would treat the embedding by pre-trained CNN as a form of feature engineering. In theory it could reduce the dimensionality of the optimisation problem significantly, speeding up learning, but there is always a risk that the pre-training misses key features due to differences that are important in RL context having a low weighting in unsupervised learning of the embeddings.
  
  So does converting an RL problem that works with images from vision-based observations, to work with embeddings of those images reduce the state space? I would say no, the problem definition is not changed, it has the same state space as before. However, the separation of concerns (vision processing vs policy or value prediction), and lower dimension space for generalising has still done something useful. It may help with generalisation, as similar states may be be closer in the embedding space than they are in the larger image space.
  
  Loosely speaking you *could* say that CURL "reduces state space" and most people would understand what you meant in practical terms. I would personally caveat that with e.g. "*effectively* reduces state space" or perhaps "makes it easier for the agent to generalise its experience across the state space".
  
  > **Comments:**
  > **username_0**: thanks for this username_1, a great answer as always!  
  
  ---
  
  