Chapter 2: Markov Decision Processes
Formalize sequential decision-making as a Markov decision process: states, actions, transition dynamics, the Markov property, and the Bellman equations that every RL algorithm is ultimately trying to solve.
Chapter Overview
Chapter 1 described reinforcement learning informally — an agent acts, the environment responds, rewards accumulate. That picture is intuitive but too loose to build algorithms on. The Markov decision process (MDP) is the formalism that makes it precise. An MDP says exactly what a state is, what the environment is allowed to do in response to an action, and what quantity the agent is trying to maximize.
The payoff for this formality is the Bellman equations. They express the value of a state in terms of the values of the states that follow it, turning an infinite-horizon optimization over trajectories into a system of equations over states. Almost every algorithm in the rest of this course — dynamic programming, TD learning, Q-learning, actor-critic — is a different strategy for solving or approximating those equations.
Chapter Roadmap
Click any topic to jump in
Markov Property
The future depends only on the current state, not the history that produced it. This is the assumption that makes value functions well defined.
MDP Definition
The tuple of states, actions, transition dynamics, reward function and discount factor that formally specifies an RL problem.
Averaging over a fixed policy gives its value; maximizing over actions gives the best achievable value.
Transition Dynamics
The conditional distribution p(s', r | s, a) that describes how the environment responds to actions — known in planning, unknown in learning.
Bellman Expectation
Recursive equations that relate the value of a state under a fixed policy to the values of its successors.
Bellman Optimality
Replacing the policy average with a maximum yields equations whose unique solution is the optimal value function.
A state is Markov if it captures everything from the past that matters for the future. Formally, the probability of the next state and reward depends on the current state and action alone, and adding the entire history changes nothing. The subtlety that trips people up is that this is a property of the state representation, not of the world. The same corridor, the same robot and the same physics can be Markov or not depending on what you decide to call the state — a camera image alone may fail while the same image plus a compass heading succeeds. That matters because the property is what licenses writing the value of a state as a single number. If the future depended on how the agent arrived, two visits to the same nominal state would have different prospects, and a value function indexed by state alone would be ill-defined. Nearly all of the theory ahead assumes this property holds, so knowing when it fails tells you exactly when the guarantees stop applying and why partially observable problems need extra machinery.
Definition
A state is Markov when the distribution of the next state and reward depends only on the current state and action, so that conditioning additionally on the whole history adds no information. Because it depends on what the agent observes, it is a property of the chosen representation rather than of the environment itself.
In this topic
What the Property Actually Says
The Markov property is a conditional independence claim: given the present state, the future is independent of the past. It is what licenses writing the value of a state as a single number rather than as a function of history. If the future depended on the route taken, two visits to the same nominal state could have genuinely different prospects, and a value function indexed by state alone would be ill-defined — the same table entry would need to hold two different answers. Almost all of RL theory assumes this, so when it fails the algorithms do not error, they simply converge to something that averages over the ambiguity.
Everything to the left of the conditioning bar on the right-hand side is the entire history. The equality says that history adds no information once and are known — so the agent may discard it.
A robot navigates a corridor using only a forward-facing camera. Two different junctions look identical from that camera. Is the camera image a Markov state?
State Is a Design Decision
Because the property depends on the representation, choosing the state is part of formulating the problem rather than something the environment hands you. Adding information can restore the property but enlarges the state space, and a larger space needs proportionally more experience to fill, so the fix is never free. Much of applied RL is a search for a representation close enough to Markov to be learnable while small enough to be tractable. The failure mode is quiet: an insufficient representation produces an agent that plateaus at mediocre performance rather than one that visibly breaks, which makes it easy to misdiagnose as a learning-rate problem.
In Atari games, a single frame does not reveal whether the ball is moving up or down. What did the original DQN paper do about this?