Robot Learning · Theory · M4
M4-T1 — Markov Decision Processes
An MDP is the contract of reinforcement learning: what the robot can see, what it can do, what happens next with what probability, and what each outcome pays.
Module 1 gave Scout a reward and a return, but it left the world itself as a black box. Reinforcement learning needs a sharper statement: a precise description of the decision problem that says what a state is, what an action does, how uncertain the result is, and what it pays. That description is a Markov decision process, and every method in this module (dynamic programming, Q-learning, SARSA) is a way of solving one. This lesson writes the definition, says honestly what its key assumption requires, and then turns Scout’s ward into a concrete MDP with real transition numbers.
Learning objectives
After this lesson, you should be able to:
- Write a task as an MDP tuple (S, A, P, R, γ) and read a transition table for one state and action.
- State the Markov property, and name two ways a real robot task breaks it.
- Distinguish deterministic from stochastic policies, and episodic from continuing tasks.
- Say what reinforcement learning assumes about the agent, and what “model-free” means.
The intuition
Picture Scout in the ward grid used throughout this module. At each moment it is in one cell and picks one of four moves: up, right, down or left. The floor is polished, so about one move in five slips sideways. After the move Scout is in a new cell, and a number comes back: a small cost for the time spent, a bonus at the pharmacy door, a heavy penalty at the stairwell edge. Then it chooses again.
Everything that matters for the next choice is meant to be in one thing: the state, here the cell. The world answers “where will I be next, and what will I be paid?” from the state and the action alone, with the same probabilities every time, no matter how Scout got there. That is the Markov property. It is a statement about the description, not about reality: if the state leaves out something that matters, such as a door that is sometimes locked, the property fails and the agent will be surprised in ways it cannot explain.
Written down carefully, the pieces are the states, the actions, the transition probabilities (the chance of each next state), the rewards and a discount. The picture shows exactly one row of that table for the ward: the start cell and the action “right”.
The mathematics
The tuple
A (finite) Markov decision process is a tuple of five things:
- S
- The set of states. In the ward, the 25 open cells.
- A
- The set of actions. Here four: 0 up, 1 right, 2 down, 3 left.
- P(s′ | s, a)
- Probability of arriving in s′ after taking a in s. Each row sums to 1.
- R(s, a, s′)
- The reward paid for that transition (or its expectation r(s, a)).
- γ
- The discount factor in [0, 1) (lesson M4-T2). Together with R it says how much the future is worth.
The Markov property
The probability of the next state and reward depends on the present state and action only, not on the earlier history:
This is an assumption about how the state is defined. If you can add something to the state that makes the future independent of the past, the task can be made Markov again. A common repair is to stack information into the state: the last few observations, a velocity estimate, a belief about a hidden quantity.
What breaks it
- Partial observability. The robot sees a noisy lidar scan, not the map. Two different places can give the same scan, and what comes next depends on which one it is. The right model then is a partially observable MDP, which is harder; a practical fix is to feed a short history, or a recurrent memory, to the policy.
- Hidden state with memory. A battery that drains, a door someone locked an hour ago, a patient who is asleep. The present observation does not contain it, but the future depends on it.
- Time. If the reward depends on how long the episode has run (a time limit, a deadline), the step counter has to be part of the state.
- Non-stationary world. If the slip probability changes with the weather, the rows of P change over time and no single table describes the task.
Policies
A policy tells the agent what to do. A deterministic policy is a map a = π(s). A stochastic policy is a distribution π(a | s) with Σa π(a | s) = 1. Stochastic policies matter for exploration (lesson M4-T7), for games against an adversary, and when the state is not fully observed. For a fully observed MDP with a known discount there is always an optimal policy that is deterministic (a result in Puterman, 1994), which is why the exact solutions in the next lessons are tables of one action per state.
Episodic and continuing tasks
An episodic task has terminal states: reaching the pharmacy door or falling at the stairwell ends the episode and the value of a terminal state is 0 from then on. Scout’s reach task in module 1 is episodic. A continuing task has no end (a delivery robot that runs all day, a thermostat), and it needs γ < 1 so that the total reward stays finite. A time limit imposed on a continuing task is an artificial cut, and as noted above it makes time part of the state.
What reinforcement learning assumes
- The agent can act, and the action changes what happens next.
- The agent observes a reward after each step (and the next state, or an observation from which it can be built).
- The task can be repeated, in simulation or in the real world, enough times to learn from. For a hospital robot that is a serious constraint: failures are not free.
Model-based methods know, or learn, P and R, and plan with them (lesson M4-T4 does the planning). Model-free methods never write P down: they improve a policy or a value estimate directly from sampled transitions (lessons M4-T5 and M4-T6). The task is the same MDP in both cases; what differs is what the agent is allowed to see of it.
A worked example
Scout’s ward as an MDP. The layout is a 7 × 9 grid with walls, 25 open cells and two terminal cells (the pharmacy door, +10, and the stairwell edge, −10). We use the standard settings of the module: slip 0.2, step cost −0.1, goal +10, stairwell edge −10 with the episode ending there, and γ = 0.95. The numbers below come from RLCore.gridworld(RLCore.layouts.ward, …), not from a hand sketch.
| Piece | In the ward | Value |
|---|---|---|
| States S | open cells (walls are not states) | 25, of which 2 are terminal |
| Actions A | up, right, down, left | 4 |
| Non-terminal (s, a) pairs | 23 states × 4 actions | 92 rows of the table P |
| Non-zero entries of P | distinct (next state, reward) outcomes over those 92 rows | 234 |
| Reward R | step cost, goal bonus, stairwell penalty | −0.1 per step; +10 at the door; −10 at the edge, plus the step cost |
| Discount γ | set by the designer | 0.95 |
One row of P. Scout starts in the top-left cell, row 1, column 1. Take the action “right”. With probability 0.8 it moves to (1,2); with probability 0.1 the move turns to “down” and Scout reaches (2,1); with probability 0.1 it turns to “up”, hits the wall and stays. Each outcome pays the step cost −0.1:
| s′ | P(s′ | s, right) | Reward | Terminal? |
|---|---|---|---|
| (1,2) | 0.8 | −0.1 | no |
| (2,1) | 0.1 | −0.1 | no |
| (1,1) (stays) | 0.1 | −0.1 | no |
The row sums to 1, so it is a valid distribution. For comparison, the action “up” from the same cell has only two outcomes: with probability 0.9 Scout stays (bumping the wall or slipping up into it) and with probability 0.1 the move turns right and Scout reaches (1,2). Walls make the rows asymmetric, which is why a table beats a formula here.
A row next to the hazard. The stairwell edge is the cell (3,6). From the cell (3,5), just to its left, the action “right” is a gamble: with probability 0.8 Scout moves onto the edge and receives −10.1 (the step cost plus the penalty) and the episode ends; with probability 0.1 it slips down to (4,5) and with probability 0.1 it stays at (3,5). The action “down” from the same cell is not safe either: it still has a 0.1 chance of turning into “right”. Even a cautious action here carries risk, because the slip is not under the agent’s control.
A policy and its meaning. The policy that always moves right is a legitimate deterministic policy; it is also a poor one, with an exact discounted value of −1.317 at the start (it keeps bumping into walls). The optimal policy, found in lessons M4-T3 and M4-T4 and in lab M4-L1, has a value of 3.314 at the start. Following it, Scout reaches the door in 88.9% of episodes (exactly 8/9, computed by solving the absorption probabilities) and falls in the other 11.1%; the slip makes a perfect score impossible. Whether 11.1% is acceptable is a decision about the reward, not something the MDP can answer.
What the simulation simplifies. The ward MDP is fully observed and exactly Markov by construction: Scout knows its cell, and the slip is a fixed 0.2 everywhere. On a real floor the slip depends on the surface and the load, the position is estimated rather than known, and the transition table is not available at all. The grid shows the structure; it does not show how hard it is to obtain the numbers.
Engineering implications and limitations
Write the MDP before choosing the algorithm
List what the state contains, what an action is, how long a step lasts, what ends an episode and what each event pays. Most failed RL projects have an unclear answer to one of these, not a bad optimiser. Lab M4-L4 shows a symptom that comes from mishandling terminal states, which is exactly this item.
Check the Markov property on purpose
A quick test: could a person who sees only the state predict the next state as well as someone who also sees the last ten steps? If the history helps, the state is missing something. Add velocities, previous actions or a short window of observations before blaming the learner.
Keep the time step honest
The discount and the horizon count steps, not seconds. If the control loop runs at 20 Hz one day and 10 Hz the next, the same γ means different amounts of future time (lesson M4-T2).
Model-free does not mean model-less
A model-free learner still lives in a world that has dynamics. It simply pays for not knowing them with samples, which may be real hours on a real robot. Decide whether a simulator, a learned model or direct experience will supply those samples (module 7 returns to this).
Common misconceptions
“Markov means the world has no memory.”
It means the state contains everything relevant. A world with memory can still be an MDP if the memory is put in the state; the property is about the description.
“An MDP requires known transition probabilities.”
The definition has them, but the agent need not: model-free methods learn from samples without ever seeing P. The MDP is the problem; knowing it is a choice of solution method.
“A stochastic environment needs a stochastic policy.”
For a fully observed MDP a deterministic policy can be optimal despite random transitions. Stochastic policies are for exploration, adversaries, or hidden state.
“Continuing and episodic tasks are solved the same way.”
The updates are similar, but a continuing task needs γ < 1 for finite returns, and an episodic one must treat terminal states as having value 0 (lab M4-L4).
Engineering takeaways
- An MDP is (S, A, P, R, γ): states, actions, the probability of each next state, rewards and a discount.
- The Markov property says the present state and action determine the next-state distribution; partial observability and hidden memory break it, and stacking history in the state repairs it.
- A policy maps states to actions, deterministically or with probabilities; a fully observed MDP has an optimal deterministic one.
- Scout’s ward is 25 states, 4 actions and a table of 92 rows; one row from the start cell is 0.8 to (1,2), 0.1 to (2,1), 0.1 stays.
- Reinforcement learning assumes an agent that acts and sees reward; model-free methods learn without the transition table, model-based ones use it.
References and further reading
Chapter 3 of the textbook defines the finite MDP; the monograph is the formal treatment of existence of optimal policies. Section numbers inside Chapter 3 are not cited because I am not certain of them.
- R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018, Chapter 3 (finite Markov decision processes).
- M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, 1994.
Knowledge check
Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.
Question 1
In the ward, Scout is at the start cell and takes “right”. What are the possible next states and their probabilities?
Explanation
(1,2) with probability 0.8, (2,1) with 0.1 (slip down), and (1,1) with 0.1 (slip up into the wall, so it stays). The row sums to 1.
Question 2
Scout’s observation is a noisy lidar scan, and two corridors give almost the same scan. Which assumption fails, and name one repair.
Explanation
The Markov property fails because the observation is not a full state (partial observability). Repairs: feed the last few observations or actions as the state, or use a policy with memory.
Question 3
What does model-free mean, and does it change the MDP?
Explanation
The learner never uses or builds the transition table P; it improves from sampled transitions. The MDP is unchanged; only what the agent is given of it differs.
What’s next
Next: the return and the discount factor, and what the discount does to the route Scout chooses.
Related content
Nothing below is required to finish this lesson.
- LabM4-L1: Solve an MDP by Value Iteration
Plan Scout's route through a hospital grid with slippery floors by computing optimal values and the greedy policy.
Get notified when the next lesson and new labs are released.
One email per new lesson or lab.