Introduction

The first article said that an agent observes the current state $S_t$ and chooses an action $A_t$. Reading it again, however, I realized that it passed over one of the most important questions rather casually.

What exactly should a state contain?

A single game screen may be a state. A robot's camera feed and joint angles together may be a state. In the lunch example, the state grouped the weather, remaining time, current location, and recently eaten meals. From these examples alone, a state can look like a box that simply collects whatever information is currently known.

If the box is too small, however, the agent mistakes different situations for the same one. If we instead cram in everything that has ever happened, we avoid missing information but force the agent to carry an enormous record into every decision. Choosing lunch today probably does not require remembering the temperature of a coffee from a Tuesday three years ago.

This article organizes the problem in four steps.

1. How do observation, history, and state differ?
2. Why should a state summarize history?
3. What does the Markov-property equation mean in practice?
4. What can we do when the entire environment is not visible?

The formal definition of an MDP and its transition probabilities can wait until the next article. We begin by asking what qualifications the $S_t$ in our equations should have.

What Is Visible Is Not Necessarily the Actual Situation

Let us begin with the observation. Observation $O_t$ is the information the agent actually observes at time $t$. For a person, it resembles what is currently arriving through the eyes and ears.

Suppose we stand in front of an elevator whose display reads the fifth floor.

$$O_t = \text{5F}$$

Can this visible number alone tell us where the elevator will go next? No. If it was moving upward, the sixth floor is likely to come next. If it was moving downward, the fourth floor is more likely.

The exact same fifth-floor display can therefore correspond to different actual situations.

$$\begin{aligned} \text{State 1} &= (5\text{F}, \uparrow) \\ \text{State 2} &= (5\text{F}, \downarrow) \end{aligned}$$

To infer the upward arrow, it helps to know that the display showed the fourth floor just before. We use the current observation together with part of the preceding record.

History Is the Playlist of Everything So Far

History $H_t$ contains every observation, action, and reward the agent has experienced so far. Using the indexing convention from the first article, it can be written roughly as

$$H_t = (O_1, A_1, R_2, O_2, A_2, R_3, \ldots, O_t).$$

The long notation looks complicated, but it is simply a chronological playlist.

• $O_1$: what the agent first observed
• $A_1$: the action it took then
• $R_2$: the reward received after the action
• $O_2$: what it observed as a result
• and the record continuing through the present $O_t$

Some textbooks index a reward as $R_t$, while others use $R_{t+1}$. The central idea is the same despite the notational difference: history is the complete chronological record of what the agent has experienced.

Why not use the entire history as the state?

In theory, we can. Because nothing observed so far has been discarded, missing information is less likely. But the history grows with the episode. It is excessive to reread every floor displayed since morning merely to predict the elevator's next floor. The recent floor and direction are enough.

A state therefore usually extracts from the history the information needed for future decisions.

$$S_t = f(H_t)$$

This equation need not be read in a complicated way.

Feed the record so far, $H_t$, into a function $f$ to produce a summary $S_t$ used for decision-making.

Making the state short is not the objective by itself. It must retain the information required to predict future rewards and situations. In the elevator example, we can discard every old floor, but if we discard the direction too, it becomes difficult to tell whether the fifth floor will be followed by the fourth or sixth.

The same principle applies when compressing an image. The goal is the smallest file that still retains the information we need. If we need to recognize a face but blur away the eyes, nose, and mouth, we obtain a small file at the cost of useful information. A state representation should be compact and sufficient.

Environment State and Agent State

David Silver's first lecture divides the word “state” more carefully. The extra terminology felt cumbersome at first, but the distinction is simple when we ask who possesses the information.

Environment State

This is the internal information the environment uses to produce the next observation and reward. In a real elevator, it may include the current position, speed, motor condition, pressed floor buttons, and whether the doors are open.

The agent usually cannot observe all of it. It can also contain information irrelevant to the next decision. The serial number of a ceiling light exists inside the environment, but contributes almost nothing to predicting the next floor.

Agent State

This is the internal information the agent actually uses to select an action. The agent constructs it from its observations and past experience.

$$S_t^{\text{agent}} = f(H_t)$$

A robot may use one camera frame as input, or pass the latest ten frames through a neural network to infer its direction of motion. Either representation is an agent state if it is used for decision-making.

In short, the environment state is the world's internal situation. The agent state is the summary carried by the agent for judgment. They may be equal, but are not always the same.

Markov Property: The Present Is Enough

Now let us add a desirable property of a state. State $S_t$ has the Markov property when

$$P(S_{t+1} \mid S_t) = P(S_{t+1} \mid S_1, S_2, \ldots, S_t).$$

At first glance, the repeated symbols make it difficult to see what is being compared. Read the two sides separately.

• Left: the probability of next state $S_{t+1}$ when only current state $S_t$ is known
• Right: the probability of next state $S_{t+1}$ when every state from the beginning through the present is known

Equality means that after we already know the current state, revealing the older past does not change the prediction of the next state.

If an elevator's current state contains only “fifth floor,” it is unlikely to have this property. Learning whether the previous floor was the fourth or sixth changes the next-floor prediction.

Now suppose the current state includes both position and direction: $(5\text{F}, \uparrow)$. In a simplified elevator, this information is enough to predict the next motion. Older floor records are unnecessary because their useful information has already been summarized by the direction.

This property is often phrased as “the future is independent of the past given the present.” The condition “given the present” is essential.

It does not say that the past was meaningless. The fact that the elevator passed the fourth floor was used to create the upward arrow in the current state. The past has already entered the state. The Markov property is not a command to forget the past; it is closer to a requirement that the past needed for judging the future be summarized correctly in the current state.

For this reason, a Markov state is sometimes called a sufficient statistic. Carrying the state instead of the entire history still preserves enough information to predict the future.

A State Is Not Created Merely Because the World Is Naturally Markov

I initially had the following misconception.

Are some environments naturally Markov and others naturally non-Markov?

The characteristics of the environment matter, but so does what we choose to call the state. For the same elevator, defining the state as only a floor number is insufficient, while including both position and direction produces a much better Markov state.

Predicting the direction of a moving ball in a video is similar. One frame shows position but not velocity. Two consecutive frames allow us to estimate how far and in which direction the ball moved.

$$S_t = (O_{t-1}, O_t)$$

When one observation is insufficient, we can combine several observations into a state. The same intuition explains why early DQN systems for Atari stacked several consecutive frames. A single current screen makes it difficult to tell whether an object is moving upward or downward.

This does not mean that stacking a few frames always creates a perfect Markov state. The necessary memory length depends on the environment, and in some cases hidden information cannot be reconstructed exactly from past observations.

Fully and Partially Observable Environments

An environment is fully observable if the agent can directly observe the entire environment state. In that case, the observation can simply be used as the state.

$$O_t = S_t$$

In chess, for example, we can see every piece's position, whose turn it is, and rule-relevant information such as castling rights. Think of the complete game state required by the rules to determine the future, rather than one photograph of the chessboard.

An environment is partially observable if the agent sees only part of the environment state.

$$O_t \neq S_t$$

In poker, we can see our own cards and the public cards, but not an opponent's hand. A robot can see a wall in front of its camera but may not know its absolute position or an obstacle behind the wall. A trading agent can observe current prices but cannot directly see every participant's intent or future news.

In a partially observable environment, the current observation alone is difficult to use as the agent state. The agent can estimate the hidden situation in several ways.

1. Use the entire history.
2. Group recent observations and actions into a fixed-length window.
3. Maintain a belief state, a probability distribution over possible hidden states.
4. Use a model such as an RNN that accumulates past information in internal memory.

Such a problem is called a Partially Observable Markov Decision Process, or POMDP. The name is long, but for now it is enough to understand it as “a problem in which the actual state is not fully visible, so the agent must estimate it from the visible record.”

What Goes Wrong When a State Is Poorly Constructed?

When a state representation is insufficient, different situations look identical to the agent.

Suppose the elevator state stores only “fifth floor.” Experience in which the elevator should move up and experience in which it should move down are mixed in one entry. The agent repeatedly observes contradictory outcomes from what it believes is the same state, making the next state or value difficult to predict accurately.

Conversely, adding too much irrelevant information makes the number of possible states explode. Situations that should share the same decision are treated as different states, so experience cannot be shared. If today's date, tiny differences in wall color, and meaningless sensor noise each create a separate state, the agent may learn every similar situation as if seeing it for the first time.

A good state balances two conditions.

• Preserve information needed to predict the future and choose an action.
• Discard as much information as possible that is irrelevant to the same decision.

Defining a state is not simple data preprocessing. It determines how the agent divides the world into same and different situations. Even a strong algorithm cannot magically recover information that the state has already discarded.

Reading the Equations in Words Once More

Let us place the two most important equations of this article together.

$$S_t = f(H_t)$$

Select from the history the information needed for future decisions and use it to construct the current state.

$$P(S_{t+1} \mid S_t) = P(S_{t+1} \mid S_1, \ldots, S_t)$$

If that state sufficiently summarizes the past, predicting the next state from the current state is equivalent to predicting it from the entire past.

The equations are not separate ideas. The first describes how to construct a state. The second provides a criterion for whether that state is sufficient.

What to Remember

The central idea of this article is

A state includes more than the screen visible now. It summarizes the history needed to judge the future.

More specifically:

1. An observation is the information the agent actually observes now.
2. History is the chronological record of observations, actions, and rewards so far.
3. An agent state is an internal representation for decision-making constructed from history.
4. The Markov property means that once the current state is known, the older past provides no additional information for predicting the future.
5. In a partially observable environment, hidden states must be estimated using history, a belief state, memory, or a related mechanism.

The first article casually called $S_t$ the current situation. We can now ask more demanding questions: “is the current observation truly enough?” and “is information that must be derived from the past, such as direction or speed, missing?”

The next article adds rewards and actions to this Markov state to construct a Markov Reward Process and Markov Decision Process formally. Despite the long names, it simply adds transition probabilities and rewards one by one to the elevator diagram from this article.

References

• David Silver, UCL Reinforcement Learning Course
• David Silver, Lecture 1: Introduction to Reinforcement Learning
• David Silver, Lecture 2: Markov Decision Processes
• Seoul National University DSBA Lab, Introduction of Reinforcement Learning
• Sutton & Barto, Reinforcement Learning: An Introduction, 2nd Edition