Answers.Body: <p><span class="math-container">$\mathcal S$</span> is just a set of all possible states. It doesn't matter if it's agents perceived state or true environment state, they are within the same set of states. Agent cannot perceive itself to be in some &quot;middle&quot; state that's not in <span class="math-container">$\mathcal S$</span>, it might think that's in the state that's not the actual environment state but that state is also in set of all states.</p>
  <p>To give an example, if the car can be blue or red, then the agent might think that the state is blue car or red car, but it cannot think that car is purple because that's not one of the possible states. It might wrongly think that the car is blue when the actual car is red, but that's ok because blue is one of the possible car states. Of course, it might also correctly think that the car state is red.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-08T21:16:03.550Z
Answers.Text: Ok, so what you are saying is that all states that an agent can be in are embedded in the environment state itself. For example, if the agent state is a hidden state of RNN, then this internal agent state vector is part of the environment state (as the agent is part of the environment as well)? If this is the case, then $\mathcal{S}$ is set of all environment states (as environment state space contains agent state space in one of it's subspaces)? After reading your answer, this is my conclusion. Did I get it right?
Answers.UserDisplayName: Stanko Kovacevic
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-28T10:10:02.480Z
Answers.Text: @StankoKovacevic whenever we talk of MDP or POMDP, we are always concerned about the agent's internal state, not the environment's. I don't know what the answer above means when it talking of S, but it is possible for the set of possible environment state and the set of possible agent state to be completely disjoint. Consider the case of an Atari game. Then the agent's state can be the screen while the environment state is the memory (which includes the code itself) in the emulator. So we are always talking about the agent's state. It's quite late but hope it helps.
Answers.UserDisplayName: Quantum Sphinx
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-28T10:19:21.307Z
Answers.Text: @StankoKovacevic As to the reason why all environments are said to be Markov, I am not entirely certain, but I can guess. For any agent that is run on a PC entirely (like Atari), we can easily say that the environment state is the entire memory and it becomes Markov. In other cases, like a Robot trying to learn how to walk, the environments state is the entire universe, including the robot of course. Classically, if we know the mass, location, velocity and acceleration of every particle, then we can predict what will happen at every future instant - again it becomes an MDP.
Answers.UserDisplayName: Quantum Sphinx
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-28T10:19:44.530Z
Answers.Text: I don't know enough about quantum mechanics to say anything about it.
Answers.UserDisplayName: Quantum Sphinx
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-28T10:29:43.890Z
Answers.Text: @QuantumSphinx This answers my question perfectly.
Answers.UserDisplayName: Stanko Kovacevic
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-24T12:35:34.877Z
Answers.Text: @StankoKovacevic If this answers your question perfectly, [you should accept it](https://meta.stackexchange.com/a/5235).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-24T12:41:54.143Z
Answers.Text: @StankoKovacevic You may also consider upvoting this answer if you found it useful and you think it's orrect.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-24T12:44:09.373Z
Answers.Text: When you say "Agent cannot perceive itself to be in some "middle" state that's not $S$". Consider, for instance, DQN. In that case, we're approximating states with sequences of observations. So, those approximate states may actually be not really states in $S$. Right? So, you may want to edit this answer to point this out, i.e. in practice, the agent may perceive some state that is not in $S$. It depends on how you define $S$ too, though.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-07T20:21:28.437Z
Answers.LastActivityDate: 2021-04-07T20:21:28.437Z
Answers.UserDisplayName: Brale
Body: <p>I'm going through the David Silver RL course on YouTube. He talks about environment internal state <span class="math-container">$S^e_t$</span>, and agent internal state <span class="math-container">$S^a_t$</span>.</p>
  <p>We know that state <span class="math-container">$s$</span> is Markov if</p>
  <p><span class="math-container">$$\mathbb{P}\{S_t=s|S_{t-1}=s_{t-1},...,S_1=s_1\}=\mathbb{P}\{S_t=s|S_{t-1}=s_{t-1}\}.$$</span></p>
  <p>When we say that Decision Process is Markov Decision Process, does that mean:</p>
  <ol>
  <li>All environment states must be Markov states</li>
  <li>All agent states must be Markov states</li>
  <li>Both (All environment states and all agent states must be Markov states)</li>
  </ol>
  <p>and according to this, if we specify corresponding MDP as <span class="math-container">$(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma, T)$</span>, <em>is <span class="math-container">$\mathcal{S}$</span> the state space of environment states or agent states?</em></p>
  <p>Why I'm confused by this? He claims that environment states are Markov (I'm also confused why, but I'll make another post for this), and then claims that if the agent can directly see environment internal state <span class="math-container">$S^e_t$</span>, then observations <span class="math-container">$O_t=S^e_t$</span>, and agent constructs its state trivially as <span class="math-container">$S^a_t=O_t=S^e_t$</span>. Now, both environment and agent states are Markov (since they are the same), so this makes sense. If we specify MDP as <span class="math-container">$(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma, T)$</span>, it's clear that state space <span class="math-container">$\mathcal{S}$</span> is state space of both agent internal states and environment internal states (again, since they are the same).</p>
  <p>Now consider the case when the environment is not fully observable. Now <span class="math-container">$O_t\ne S^e_t$</span>, and agent must construct it's state <span class="math-container">$S^a_{t}=f(S^a_{t-1}, H_t)$</span>, where <span class="math-container">$H_t=(O_0, A_0, R_1, O_1,...,O_{t-1}, A_{t-1}, R_t, O_t)$</span> is history until time step <span class="math-container">$t$</span>, and <span class="math-container">$f$</span> is some function (such as Recurrent Neural Network for example). In the case of <span class="math-container">$f$</span> being a recurrent neural network, we have that both environment internal states are Markov (by this hypothesis), and agent internal states are Markov (approximately), so again, the process is an MDP <span class="math-container">$(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma, T)$</span>, but state space of agent states is different to that of environment states, so I'm confused about what is <span class="math-container">$\mathcal{S}$</span> here. <em>Is it environment state-space or agent state space?</em></p>
  <p>Lastly, what if <span class="math-container">$f(S^a_t, H_t)=O_t$</span>? That is, the agent's internal state is simply the last observation. Considering that environment states are always Markovian (again, don't know why we can claim this), but agent states are not, this is the case of POMDP. Even here I don't know what <span class="math-container">$\mathcal{S}$</span> stands for in specification of POMDP. Is it environment state-space or action state space?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-24T12:46:06.207Z
Comments.Text: To have more context, could you please provide the link to the specific video lesson where D. Silver talks about this topic (maybe also the specific part of the video lesson, minute, where he says that)?
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><terminology><markov-decision-process><state-spaces><markov-property>
Title: What is the difference between environment states and agent states in terms of Markov property?
UserDisplayName: Stanko Kovacevic
ThreadText: # What is the difference between environment states and agent states in terms of Markov property?
  
  (Asked by: username_0 on 2021-04-06)
  
  I'm going through the David Silver RL course on YouTube. He talks about environment internal state $S^e\_t$, and agent internal state $S^a\_t$.
  
  We know that state $s$ is Markov if
  
  $$\mathbb{P}\{S\_t=s|S\_{t-1}=s\_{t-1},...,S\_1=s\_1\}=\mathbb{P}\{S\_t=s|S\_{t-1}=s\_{t-1}\}.$$
  
  When we say that Decision Process is Markov Decision Process, does that mean:
  
  1. All environment states must be Markov states
  2. All agent states must be Markov states
  3. Both (All environment states and all agent states must be Markov states)
  
  and according to this, if we specify corresponding MDP as $(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma, T)$, *is $\mathcal{S}$ the state space of environment states or agent states?*
  
  Why I'm confused by this? He claims that environment states are Markov (I'm also confused why, but I'll make another post for this), and then claims that if the agent can directly see environment internal state $S^e\_t$, then observations $O\_t=S^e\_t$, and agent constructs its state trivially as $S^a\_t=O\_t=S^e\_t$. Now, both environment and agent states are Markov (since they are the same), so this makes sense. If we specify MDP as $(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma, T)$, it's clear that state space $\mathcal{S}$ is state space of both agent internal states and environment internal states (again, since they are the same).
  
  Now consider the case when the environment is not fully observable. Now $O\_t\ne S^e\_t$, and agent must construct it's state $S^a\_{t}=f(S^a\_{t-1}, H\_t)$, where $H\_t=(O\_0, A\_0, R\_1, O\_1,...,O\_{t-1}, A\_{t-1}, R\_t, O\_t)$ is history until time step $t$, and $f$ is some function (such as Recurrent Neural Network for example). In the case of $f$ being a recurrent neural network, we have that both environment internal states are Markov (by this hypothesis), and agent internal states are Markov (approximately), so again, the process is an MDP $(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma, T)$, but state space of agent states is different to that of environment states, so I'm confused about what is $\mathcal{S}$ here. *Is it environment state-space or agent state space?*
  
  Lastly, what if $f(S^a\_t, H\_t)=O\_t$? That is, the agent's internal state is simply the last observation. Considering that environment states are always Markovian (again, don't know why we can claim this), but agent states are not, this is the case of POMDP. Even here I don't know what $\mathcal{S}$ stands for in specification of POMDP. Is it environment state-space or action state space?
  
  **Tags:** reinforcement-learning, terminology, markov-decision-process, state-spaces, markov-property
  
  > **Comments:**
  > **username_1**: To have more context, could you please provide the link to the specific video lesson where D. Silver talks about this topic (maybe also the specific part of the video lesson, minute, where he says that)?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-04-07. Score: 0 | Accepted answer
  
  $\mathcal S$ is just a set of all possible states. It doesn't matter if it's agents perceived state or true environment state, they are within the same set of states. Agent cannot perceive itself to be in some "middle" state that's not in $\mathcal S$, it might think that's in the state that's not the actual environment state but that state is also in set of all states.
  
  To give an example, if the car can be blue or red, then the agent might think that the state is blue car or red car, but it cannot think that car is purple because that's not one of the possible states. It might wrongly think that the car is blue when the actual car is red, but that's ok because blue is one of the possible car states. Of course, it might also correctly think that the car state is red.
  
  > **Comments:**
  > **username_0**: Ok, so what you are saying is that all states that an agent can be in are embedded in the environment state itself. For example, if the agent state is a hidden state of RNN, then this internal agent state vector is part of the environment state (as the agent is part of the environment as well)? If this is the case, then $\mathcal{S}$ is set of all environment states (as environment state space contains agent state space in one of it's subspaces)? After reading your answer, this is my conclusion. Did I get it right?  
  > **username_3**: @username_0 whenever we talk of MDP or POMDP, we are always concerned about the agent's internal state, not the environment's. I don't know what the answer above means when it talking of S, but it is possible for the set of possible environment state and the set of possible agent state to be completely disjoint. Consider the case of an Atari game. Then the agent's state can be the screen while the environment state is the memory (which includes the code itself) in the emulator. So we are always talking about the agent's state. It's quite late but hope it helps.  
  > **username_3**: @username_0 As to the reason why all environments are said to be Markov, I am not entirely certain, but I can guess. For any agent that is run on a PC entirely (like Atari), we can easily say that the environment state is the entire memory and it becomes Markov. In other cases, like a Robot trying to learn how to walk, the environments state is the entire universe, including the robot of course. Classically, if we know the mass, location, velocity and acceleration of every particle, then we can predict what will happen at every future instant - again it becomes an MDP.  
  > **username_3**: I don't know enough about username_3 mechanics to say anything about it.  
  > **username_0**: @username_3 This answers my question perfectly.  
  > **username_1**: @username_0 If this answers your question perfectly, [you should accept it](https://meta.stackexchange.com/a/5235).  
  > **username_1**: @username_0 You may also consider upvoting this answer if you found it useful and you think it's orrect.  
  > **username_1**: When you say "Agent cannot perceive itself to be in some "middle" state that's not $S$". Consider, for instance, DQN. In that case, we're approximating states with sequences of observations. So, those approximate states may actually be not really states in $S$. Right? So, you may want to edit this answer to point this out, i.e. in practice, the agent may perceive some state that is not in $S$. It depends on how you define $S$ too, though.  
  
  ---
  
  