Markov decision processes
Weeks 2 and 3 described how an agent is built. This page makes "choosing well" precise: a world where actions have random outcomes and consequences that arrive later, written down as five things.
Kind: not an agent: the problem every week 4 agent solves.
Week: 4 (slides 5 to 15).
Book: not in Wooldridge. 2.5 “purely reactive agents” (p. 36) is the closest idea. Sutton and Barto 3.1 to 3.3, or Russell and Norvig 17.1, if you want a second explanation.
Techniques on this page: the MDP tuple, the Markov property, the gridworld’s noisy transitions, where policies come from.
The problem it solves
STRIPS planning (week 2) assumed every action has one certain outcome. Real actions don’t: a robot’s wheels slip, a message might not arrive. And some consequences only show up later: the route past the cliff edge is as short as the safe one, it’s just riskier.
A Markov decision process (MDP) is the standard way to describe that kind of problem precisely, so that “the best thing to do” has a definite meaning and can be computed (value iteration) or learned (Q-learning).
The lecture makes one big simplifying assumption until the last part: the agent sees the true state (\(o_t = s_t\)) and needs no memory beyond it (\(m_t = s_t\)). POMDPs drop it.
Words you’ll hear
| Word or symbol | Plain meaning |
|---|---|
| \(s_t \in S\) | the state of the world at time \(t\) |
| \(a_t \in A\) | the action the agent takes at time \(t\) |
| \(P(s' \mid s, a)\) | the chance of landing in \(s'\) if you do \(a\) in \(s\) |
| \(R(s, a, s')\) | the reward for that step; it arrives as \(r_{t+1}\), together with \(s_{t+1}\) |
| \(\gamma\) (gamma) | the discount factor: how much a reward one step later counts |
| policy \(\pi\) | the agent’s rule: what to do in each state. The solution, not part of the problem |
| stationary | the same policy at every time step |
| terminal state | the episode ends there |
| living cost | the small negative reward for every step that doesn’t end the episode |
Technique 1: the MDP tuple
Problem it solves: pins down exactly what the agent faces.
An MDP is \(\langle S, A, P, R, \gamma\rangle\). One tick of the loop (slide 6): the agent sees \(s_t\) and picks \(a_t\) with its policy; the world draws \(s_{t+1}\) from \(P(\cdot \mid s_t, a_t)\) and hands back \(r_{t+1} = R(s_t, a_t, s_{t+1})\); repeat.
Week 1’s vocabulary collapses onto it (slide 8): \(o_t = s_t\), \(m_t = s_t\), the goal \(g_t\) is absorbed into \(R\) (reach the goal and you get +1), and \(a_t = \pi(m_t, g_t)\) becomes \(a_t \sim \pi(\cdot \mid s_t)\).
Keep two things apart: \(P\) is what the world does. \(\pi\) is what the agent does. The MDP is the problem; the policy is the answer.
Technique 2: the Markov property
Problem it solves: justifies deciding from the current state alone.
\[P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \ldots, s_0) = P(s_{t+1} \mid s_t, a_t)\]
“The future depends on the past only through the present.” Then \(s_t\) is a sufficient statistic: knowing how you got here adds nothing.
Slide 9’s key point: it’s a modelling claim, not a fact. It depends on what the designer put into \(s_t\).
Worked example. A ball rolling along a track, with \(s_t\) = its position. Two balls at the same spot, one rolling left and one right, have different futures. Not Markov. Add velocity: \(s_t = (\text{position}, \text{velocity})\), and it is.
A delivery robot with \(s_t\) = the room it’s in: not Markov if the right move depends on whether it’s carrying the parcel. \(s_t = (\text{room}, \text{carrying?})\) fixes it.
This is why an MDP policy can be purely reactive (\(\pi: S \to A\), Wooldridge’s \(Ag: E \to Ac\), book p. 36) without losing anything: if the state is Markov, there’s nothing extra in the history to use.
Technique 3: the gridworld’s noisy transitions
Problem it solves: turns “actions sometimes go wrong” into numbers.
The 4 × 3 gridworld (Russell and Norvig, slides 12 to 14). Cells \(s_{x,y}\), column \(x\) = 1 to 4, row \(y\) = 1 to 3:
| s1,3 | s2,3 | s3,3 | +1 |
| s1,2 | wall | s3,2 | −1 |
| s1,1 | s2,1 | s3,1 | s4,1 |11 states (the wall isn’t one), two terminal. The intended move happens with probability 0.8; the agent slips 90° left or right with 0.1 each; bumping into the wall or edge leaves it in place. Each step costs −0.04; entering a terminal gives +1 or −1.
Recipe: list the three directions (intended, and the two at right angles), find where each lands, add up the probabilities of directions that land in the same cell.
Worked example. From \(s_{3,2}\), action North: North to \(s_{3,3}\) (0.8); slip East into the −1 (0.1); slip West into the wall, stay in \(s_{3,2}\) (0.1).
From \(s_{1,1}\), action West: West hits the edge (0.8, stay); slip North to \(s_{1,2}\) (0.1); slip South into the edge (0.1, stay). So \(P(s_{1,1} \mid s_{1,1}, W) = 0.9\).
Because a plan can be wrecked by the first slip, the answer to an MDP is a policy (an action for every state), not a plan (a fixed sequence). That’s the big difference from STRIPS.
Technique 4: where policies come from
Problem it solves: connects this week’s maths to the architectures of weeks 2 and 3.
| Source | How | Example |
|---|---|---|
| hand-designed | the designer writes condition–action rules | teleo-reactive programs, subsumption |
| planned | computed from a known \(P\) and \(R\) | value iteration |
| learned | estimated from experience when \(P\), \(R\) are unknown | Q-learning |
All three produce the same object, a map from states to actions (slide 15). They differ only in how they get it.
Worked example. How many deterministic policies does the gridworld have? 9 non-terminal states, 4 actions each: \(4^9 = 262{,}144\). Same counting as week 1’s \(|Ac|^{|E|}\) reactive agents.
The Markov discussion (slide 10). No real state representation is exactly Markov; the question is whether it’s “Markov enough”. You can test it: does adding the previous state or action improve your predictions of \(s_{t+1}\)? If so, your state is missing something, and every later guarantee (optimal values, convergence) is about the model, not the world.
What to read
| Source | Read? | Why |
|---|---|---|
| Wooldridge 2.5 “Purely reactive agents”, p. 36 | Read | Slide 11 cites it: \(Ag: E \to Ac\) and the thermostat |
| Wooldridge, rest of Ch. 2 | Done in week 1 | |
| Sutton and Barto 3.1 to 3.3 (free online) | Optional | the agent–environment loop and the Markov property |
| Russell and Norvig 17.1 | Optional | where the gridworld comes from |
Page numbers are the book’s; in the scanned PDF add 21.
Practice prompt
I'm studying CS5940 Intelligent Agents, week 4 (MDPs and reinforcement learning). I want practice on MARKOV DECISION PROCESSES:
- the tuple <S, A, P, R, gamma> and what each part means; why the policy is not part of the MDP
- why the reward for acting at time t is written r_{t+1}
- the Markov property, and deciding whether a given state representation is Markov (and how to fix it)
- transition probabilities in the 4x3 gridworld (0.8 intended, 0.1 slip each side at 90 degrees, walls leave you in place)
- why the solution is a policy, not a plan; counting deterministic policies
- hand-designed vs planned vs learned policies, with examples from teleo-reactive programs, value iteration and Q-learning
Please:
1. Use plain, everyday language and explain any symbol in one short sentence.
2. Give me ONE question at a time, easy first, then harder, with friendly numbers.
3. Wait for my answer, then mark it and show the full working.
4. If I get it wrong, explain the mistake and give me a similar question.
5. Every 5 questions, summarise my strengths and what to practise.