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?


$\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.

  • $\begingroup$ 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? $\endgroup$ – Stanko Kovacevic Apr 8 at 21:16

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.