# What is the difference between environment states and agent states in terms of Markov property?

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?

## 1 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.

• 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? – Stanko Kovacevic Apr 8 at 21:16
• @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. – Quantum Sphinx Apr 28 at 10:10
• @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. – Quantum Sphinx Apr 28 at 10:19
• I don't know enough about quantum mechanics to say anything about it. – Quantum Sphinx Apr 28 at 10:19
• @QuantumSphinx This answers my question perfectly. – Stanko Kovacevic Apr 28 at 10:29