State

In reinforcement learning, the state $S_t$ is a summary of the environment at time $t$ that contains everything needed to predict what happens next. When the agent cannot see the full state and receives only an observation, the problem becomes a partially observable MDP (POMDP).

The Markov property

A state signal is Markov if the future is independent of the past given the present:

In words, once you know $S_t$ and the action $A_t$, the earlier history adds nothing. The full history $H_t=(S_0,A_0,R_1,\dots ,S_t)$ is always Markov, so the question in practice is whether a compact representation is.

State vs observation

A single video frame of a ball game is an observation, not a Markov state: it shows where the ball is but not where it is going. A common fix is to stack the last few frames so velocity can be inferred. Recurrent networks and transformers do the same job more generally, by compressing the observation history into an internal state. For a language model generating text, the natural state is the prompt plus all tokens generated so far, which is Markov by construction.

POMDPs and belief states

A POMDP adds an observation function $O(o\mid s^{\prime })$. The agent can track a belief, a probability distribution over hidden states, updated by Bayes' rule after each action $a$ and observation $o$:

The belief is itself a Markov state, so a POMDP can be turned into an MDP over beliefs, at the price of a continuous state space.

Worked example

A tiger is behind the left or right door with equal probability, and listening reports the correct side 85% of the time. After hearing "left" once, the belief in left is $0.85$. After hearing "left" twice it is $\frac{0.85^2}{0.85^2+0.15^2}\approx 0.970$. The agent's best action depends on this number, not on any single observation.

Why it matters

Every guarantee for value functions and the Bellman equation assumes the state is Markov. When it is not, value estimates are biased, and a policy can look good in training while relying on information it will not have at deployment. Choosing what goes into the state, and checking that it is sufficient, is often the most consequential design decision in an RL system.

Related terms

• Markov decision process
• Action
• Policy
• Value function
• Model-based reinforcement learning

Sources

1. Richard S. Sutton, Andrew G. Barto. Reinforcement Learning: An Introduction (2nd edition), 2018. incompleteideas.net
2. Leslie Pack Kaelbling, Michael L. Littman, Anthony R. Cassandra. Planning and acting in partially observable stochastic domains, 1998. doi.org