What does the world need to remember?

A delivery robot works in a building with four locations, and it must collect a parcel and leave it at the door. A ten-step record of locations alone has 4^10 = 1,048,576 realisations. A ten-step history also records the ten actions, so it has 16^10 realisations, more than a thousand times as many. Only eight situations matter: four places times two answers to "am I carrying the parcel?"

The section asks what the world needs to remember, and the answer is the facts that change what happens next and nothing else, because a record can be long and still useless while a short summary can be exactly enough. !Ten moves in a four-place building leave 4 to the tenth, 1,048,576, possible records, but only eight situations change what happens next: four places times the parcel bit. Drop that bit and the two visits to location 2 share one state, so one arrow must serve both, and one of the two uses is wrong. A summary is enough when every action has the same consequences in both histories it merges. The figure is schematic. Status: schematic.

The full [[term:history]]history is everything observed and done so far, and a [[term:state]]state is a summary of that history, chosen so that the future depends on the summary and not on the details behind it. The choice of state is a modelling decision, not a property of the building.

An environment has the [[term:markov-property]]Markov property when the next state and reward depend only on the current state and action, not on the earlier history [S:83:71]. When that holds, the state is said to have the Markov property [S:83:71]. The condition is about the summary, not about the world's hidden machinery, so a world with memory can still have a Markov state as long as the memory is written into the state.

An observation is what the agent senses at a step, while a state is what the decision needs, and the two are not the same. A robot may observe a wall but need to know its own battery charge, and a camera may observe a thousand pixels while the decision needs one bit.

A Markov decision process is the formal package of states, actions, rewards, and transitions [S:83:69]. A transition is one step from a state and an action to a next state and a reward. The Markov property supplies the first word of the name; the decision process is the part the agent controls. The process is a description of the problem, meant as a framing of learning from interaction to reach a goal [S:83:69].

The Markov condition is a restriction on the state, not on the process [S:83:71]. The process may have all the memory it likes, but the agent needs a state that carries whatever part of that memory can change the next step. A state that carries too little is wrong, while a state that carries everything is merely expensive.

The test for a state is a question: if two histories share this state, would every action have the same consequences in both? If yes the summary is enough, and if no something is missing, with the missing piece belonging in the state.

Remembering everything is not free, because a table with one entry per history needs evidence for every entry and the count multiplies with each step. A table here is a lookup: one row per situation and one number in each row. The eight-state table needs eight numbers, so each visit teaches something about every situation that shares the state.

Worked example. The robot stands at location 2, where with the parcel the right move is to the door and without it the right move is back to the depot. A state that records only "location 2" cannot tell the two cases apart, so any policy must choose the same action for both.

If the two cases are equally likely, such a policy is right exactly half the time; in general it is right max(p, 1−p), which is at least half. If the robot carries the parcel on nine visits out of ten, a location-only policy that always heads for the door is right nine times out of ten. The coarse state fails on the rarer branch, not on half the visits. Adding the parcel bit splits each location in two, giving 4 × 2 = 8 states, so the 1,048,576 location records collapse to eight states with no loss of foresight. A table with one row per location record would need 1,048,576 rows, while a table with eight rows fits on a postcard.

Think of a passport and a diary: the passport carries the few facts a border needs, while the diary carries everything. The comparison breaks because you often do not know which facts the next border will ask for, and then the passport is too short.

The cost is that the Markov property is an assumption, not a guarantee [S:83:71], because when important information is hidden the state must carry a memory of the past, and the number of possible memories can grow without bound. Methods that do not rely on the assumption exist, and later chapters take them up [S:83:71].

The formal statement. The history at a step is the sequence of states, actions and rewards up to that step [S:83:70]. A state is a function of that history. The environment has the Markov property when the next state and reward depend on the current state and action alone, and on nothing earlier [S:83:71]. Written as a conditional probability, the distribution of the next pair given the whole history equals the distribution given the current state and action. The book calls this a restriction on the state, not on the process [S:83:71].

The derivation. Let $f$ map a history to a summary. The summary is a Markov state exactly when, for every action $a$ and every pair of histories $h,h^{\prime }$ with $f(h)=f(h^{\prime })=s$, $p(s^{\prime },r\mid h,a)=p(s^{\prime },r\mid h^{\prime },a)$; the common value then defines $p(s^{\prime },r\mid s,a)$. Necessity is immediate. Sufficiency follows from the tower property: $p(s^{\prime },r\mid s,a)={\sum }_{h:f(h)=s}p(s^{\prime },r\mid h,a)P(h\mid s)$, and every term in the sum is the same. Markovness of the full history is not the hypothesis that does the work: the full history is a sufficient state by construction.

The edge case. A policy that cannot separate two cases is right $\max (p,1-p)$ of the time, where $p$ is the probability of the branch it always chooses. The worst case is one half, attained when the two cases are equally likely. If the robot carries the parcel on nine visits out of ten, a location-only policy is right nine times out of ten. The coarse state is not half useless. It fails on the branch that matters least, and that is a different failure.

What L1 hid. L1 compared the long records with eight states and called the collapse lossless. The collapse is lossless because location and the parcel bit together determine the next step. Drop the bit and the summary fails. Add a bit that never changes the transition and the summary still works, but the table grows. So the count is not the point. Sufficiency is the point, and sufficiency is a property of the summary together with the action set.

Where the analogy breaks. A passport answers a fixed list of questions asked at a border. A state must answer every question the agent's own policy can ask, including actions the agent has not tried yet. A passport is sufficient for a known procedure. A state must be sufficient for an unknown one, which is why the diary is sometimes the honest choice.

Original sources. The Markov property as a condition on the state is stated in Sutton and Barto §3.1 [S:83:71]. Partial observability is formalised as a POMDP, a controlled hidden Markov model with an observation distribution [S:60:219]. In that model the agent never sees the state, only a noisy observation of it [S:60:219]. The belief state is the conditional distribution of the hidden state given the observations and actions. That distribution is itself Markov, so a POMDP becomes an MDP over beliefs [S:60:221]. A belief-state MDP is an ordinary MDP whose states are beliefs, so the value-function machinery applies unchanged [S:60:221].

An open question. Constructing a sufficient state from raw observations is not solved in general. Sutton and Barto promise methods that learn a Markov state from non-Markov observations, and they assume the property everywhere else [S:83:71]. No method guarantees sufficiency without assumptions on the observation process. Evidence that would settle a method: a sample-complexity bound showing that the learned summary is sufficient for optimal control, with the assumptions named, on a task where the observations provably hide a needed variable.

A frontier result. Dreamer learns a compact latent state from images and then learns behaviour inside that latent space by imagination: a policy and a state-value function are trained by propagating analytic gradients of the learned value back through imagined latent trajectories [S:293:1]. It does not plan online; the paper contrasts its analytic-gradient approach with the online planning and derivative-free optimisation used in earlier model-based agents [S:293:1]. The latent state makes the modelling choice explicit: the agent decides what to remember, then learns values in the remembered space. A belief is a probability distribution, and the space of distributions is infinite, so a table with one row per belief is impossible [S:60:221]. The learned state is the repair.

What to read next. Read §3.1 of Sutton and Barto for the restriction on the state [S:83:71], and Chapter 17 for the construction of a Markov state from observations [S:83:71]. Read §10.4 of Krause and Hübotter for the POMDP definition [S:60:219] and the belief update [S:60:221]. Then read the Dreamer introduction for a learned state at scale [S:293:1].