Markov Decision Processes
P9.rl-foundations.03 · Audience: guest, it-ml, language-pro · Prerequisites: Bandits & Explore/Exploit
A bandit makes one decision, over and over, in a world that never changes. Real problems are not like that: the move you make now changes the situation you face next, and the reward for a good decision may not arrive until many moves later. A chess move, a step across a room, a sentence in a negotiation — each reshapes what comes next. To reason about acting in sequence, reinforcement learning uses one framework, the Markov decision process. This module builds it from the bandit by adding the one thing the bandit lacked: states.
A Markov decision process (MDP) is the standard way to describe an agent acting in a world that changes in response to what it does. Where the bandit had just arms and rewards, an MDP adds the idea that you are always in some state — a situation — and your action moves you to a new one. It has five pieces:
| Piece | What it is |
|---|---|
| States | The situations the agent can be in (a square on a grid, a board position, a page of a form) |
| Actions | The choices available in a state (move up/down/left/right) |
| Transitions | Which state an action leads to (move right → the cell to the right) |
| Rewards | The number the environment pays for a transition (+1 for reaching the goal) |
| Discount (γ) | How much a future reward is worth compared with an immediate one |
Our running example is a gridworld: an agent on a grid of cells, moving one step at a time, with a reward at a goal cell. Gridworlds are the fruit fly of reinforcement learning — small enough to trace on paper, rich enough to show every core idea. The simplest useful one is a 1×3 corridor: three cells in a row, with a +1 goal in the rightmost cell, and the only actions being to step left or right.
ⓘ Concept: The MDP: states turn a choice into a plan
Why it matters — The moment actions move you between states, a single decision is no longer enough — you need a plan that accounts for where each action leaves you. A good move is one that leads to good situations, which lead to good situations in turn. The MDP is the bookkeeping that makes this precise, and every method in the rest of the pillar is a way of finding a good plan inside one.
Ask the mentor about this module
Ask a question about this content. The mentor explains and grounds its answer in what you are studying; asking is recorded as a learning signal, not a grade.
Try it yourself
A scratch console for this page's ideas — ungraded, nothing you run here is recorded.
Scratch console
A scratch console with the scientific stack (pandas, numpy, scikit-learn). Runs on the server — no network, resource-limited and measured.
Output appears here.
Where next?
Later in RL Foundations
Go up a level