Non-deterministic search formalised: states, actions, a transition function, rewards, discounting, the Bellman equations, value iteration, policy evaluation, policy extraction and policy iteration.
Printed copy: all task answers below are revealed. On screen they are hidden behind a click, which is how you should use them first. Printing also reveals every hidden answer automatically.
the theory exam... tests both for factual knowledge as well as for synthetic knowledge... we also want to see that you can uh bring things across different chapters uh together because as you know by now uh the course is largely incremental.(Lecturer, T9). The links above are examinable content, not decoration. This Part is the one that joins Part 8's expectimax to a formalism you can actually solve.
Deck p.4 is the Part 8 expectimax recap. It gives three reasons why you might not know the result of an action: explicit randomness (dice), unpredictable opponents (ghosts that respond randomly), and actions that fail (a robot's wheels slip). Its last line is the hinge into this Part: "Later, we'll learn how to formalize the underlying uncertain-result problems as Markov Decision Processes". Page 5 is the section divider, and it names the whole topic: Non-Deterministic Search.
Two things are wrong with using plain expectimax for such a world, and both are stated later in the deck on p.29. First, the same states come back again and again, so the tree recomputes the same quantity many times. Second, the tree never ends, because there is no goal test that always fires. An MDP is the data structure that fixes both: instead of a tree of paths you keep one number per state, and you update those numbers until they stop moving.
Deck p.6 sets up the example that carries most of the Part. A 4 by 3 grid, columns numbered 1 to 4 left to right and rows 1 to 3 bottom to top. The agent starts at (1,1). There is a wall at (2,2). The square (4,3) is worth +1 and the square (4,2) is worth −1. Movement is noisy: the intended direction happens 80 percent of the time, and the two perpendicular directions each happen 10 percent of the time. If the direction the agent would have been taken is blocked by a wall or by the edge of the grid, the agent stays put. Rewards arrive every time step: a small living reward that may be negative, and big rewards at the end. The goal is stated on the slide as "maximize sum of rewards".
The agent is in the START cell (1,1), the bottom-left corner, and takes the action West. Write out the full transition distribution T((1,1), West, ·): every reachable next state with its probability. Then say how many entries it has.
Two entries, not three. West itself (probability 0.8) walks off the left edge, so the agent stays at (1,1). The perpendicular directions for West are North and South. North (0.1) reaches (1,2). South (0.1) walks off the bottom edge, so the agent stays at (1,1) again. The two stay-put outcomes merge:
T((1,1), West, (1,1)) = 0.8 + 0.1 = 0.9 T((1,1), West, (1,2)) = 0.1
Why it matters: whenever an outcome bounces off a wall you must add its probability to the self-transition rather than writing a second row for the same successor. The distribution has to sum to 1 over distinct successors. This is the same bookkeeping the exercise sheet does with min and max in the creature-in-cave transition model (exercise session 6, question 4.1).
The left panel has one arrow leaving the action; the right panel has three. Of the six components of a problem definition you are about to meet on p.8, exactly one differs between the two panels. Which one, and how many non-zero entries does T(s, North, ·) have in each panel?
Only T changes. The state set, the action set, the reward function, the start state and the terminal states are identical in both panels. On the left T(s, North, ·) has one non-zero entry with probability 1.0; on the right it has three, 0.8 and 0.1 and 0.1.
Why it matters: this is exactly what the creature exercise asks at part 4d, "would the optimal policy have been different if the creature was moving in a deterministic way", and the published answer is yes, the deterministic creature walks past the lava toward the diamond while the clumsy one does not. Same states, same rewards, different T, different optimal policy.
Exercise session 6, question 4.4d, verbatim (archetype A17)
"Imagine the player could upgrade the creature to allow it to move less clumsy. Would the optimal policy have been different if the creature was moving in a deterministic way?"
if this is confusing just go back to the... water jug example which is the exact same thing without the probabilities.(Lecturer, T10 exercise session). The advice attached to this is to write the transition model by grouping the 80/10/10 outcomes per action, one action at a time. A deterministic transition function you already know how to write; a stochastic one is the same object with a probability column added.
Deck p.8 gives the definition. An MDP is defined by:
The slide then says the sentence that positions the whole Part: "MDPs are non-deterministic search problems. One way to solve them is with expectimax search. We'll have a new tool soon."
The slide says the reward is "sometimes just R(s) or R(s')". In the micro-blackjack exercise the published reward function is R(s, Stop, Done) = s, and 0 otherwise. Which of the three forms is that, and why can it not be rewritten as R(s')?
It is the general form, and it depends on s and a but not on s'. It cannot be written as R(s') because every Stop action lands in the same successor, Done, while paying a different amount (2, 3, 4 or 5) depending on where it came from. A function of s' alone would have to give Done one single value.
Why it matters: the exercise sheet's other MDP, the creature in the cave, hints the opposite way, "Focus on s' in your rewards", because there the payoff belongs to the square you land on. Read the word problem before choosing the form. Writing R(s, a, s') always works; the shorter forms are conveniences.
Exercise session 6, questions 4.1 and 4.2, verbatim (archetype A17)
"Imagine your creature is currently in a small cave, which is three by five blocks. The basic form of the creature is supposed to be rather clumsy, and will only be able to walk into the intended direction 80% of the time, and to either left or right (with respect to its intended direction) of its original position with an equal probability. The creature stays in the same position when it bumps into a wall. How would you define the set of states S, set of actions A and transition model T(s, a, s')?"
"If the player could assign the values −10, −3, 3 and 10 as possible reward values for goal states, what would be a sensible reward function R(s, a, s')? (Hint: Focus on s' in your rewards)"
S: one state per block of the cave, so 15 states, S = {(x, y) : 1 ≤ x ≤ 5, 1 ≤ y ≤ 3}. Nothing else belongs in the state: not the path taken, not the number of steps so far.
A: {North, East, South, West} in every non-goal state; the resource and hazard blocks are goal states with no continuation.
T: 0.8 to the intended neighbour and 0.1 to each of the two neighbours perpendicular to the intended direction. Any outcome that would leave the cave or hit a wall leaves the creature in s, and its probability is added to T(s, a, s) rather than written as a separate row, so that the distribution still sums to 1 over distinct successors.
R: indexed on s', exactly as the hint says. R(s, a, s') = 10 if s' is the diamond (rare), 3 if s' is iron or wood (common), −3 if s' is the pit (damages the creature), −10 if s' is lava (destroys it), and 0 for every other transition.
What earns the marks: one for a state set with no history in it, one for a T that sums to 1 per (s, a) with the wall bounces merged into the self-transition, one for a reward function whose argument is named. "The creature gets 10 for the diamond" without saying which argument of R carries the 10 is the version that loses the mark, because R(s) and R(s') are different models and only one of them can express "you are paid for arriving here".
This is exercise archetype A17 and it is the first thing an exercise question about this Part is likely to ask. The scoring instruction on the sheet is explicit: "try to keep the number of states as small as possible".
dependent on how you defined each of these aspects, how you formulated the problem, the problem will be easier or will be harder to solve. And that's something very important to realize.(Lecturer, T1). Said about search problems in Part 3, and it transfers directly: a bad state design turns a six-state MDP into a combinatorial one.
The problem: you repeatedly draw a card with replacement from a deck containing only 2, 3 and 4, each equally likely. While your total is below 6 you may Draw or Stop. Stopping pays your final score (at most 5) and ends the game. A score of 6 or more pays zero and ends the game.
The published formulation:
Exercise session 6, question 2, verbatim (archetype A17, MDP formulation)
"Formulate this problem as an MDP. 1. What are the states and the actions for this MDP? (try to keep the number of states as small as possible) 2. What is the transition function T(s,a,s')? 3. What is the reward function R(s,a,s')? 4. What is the discount factor γ?" The creature-in-cave question 4 is the same archetype on a grid.
The five bullets above this box are the published answer, compressed: S = {0, 2, 3, 4, 5, Done}, A = {Draw, Stop}, T(s, Stop, Done) = 1 with Draw spreading 1/3 to each of s+2, s+3, s+4 and collapsing anything at or above 6 into Done, R(s, Stop, Done) = s for s ≤ 5 and 0 otherwise, and γ = 1.
What earns the marks: the state set (six states, the running sum plus Done, with no state 1 because no combination of 2s, 3s and 4s makes 1), a transition function whose rows sum to 1, a reward function with its argument named, and a one-line justification for γ. The published justification is worth copying: sooner rewards are not better here, only the score at the end of the round matters. A γ given without a reason scores less than a γ given with one, because the sheet asks four separate numbered questions and each carries its own mark.
Classic mistake: using the card sequence as the state instead of the running sum, which makes S infinite for no gain. Second classic mistake: writing R as a function of s when the payoff belongs to the square you arrive at. The sheet hints "Focus on s' in your rewards" for the creature precisely because the iron, diamond, lava and pit values sit on the destination square.
Also asked in this archetype: justify γ. The published creature answer rules out 1.5 and −0.5 as nonsensical, reads γ = 1 as indifference to distance, γ = 0.9 as "close iron is more useful than far diamonds", and γ = 0 as caring only about the current square.
Deck p.9 is one idea. "Markov" generally means that given the present state, the future and the past are independent. For MDPs it means specifically that action outcomes depend only on the current state. The slide then anchors it to something you already have: "This is just like search, where the successor function could only depend on the current state (not the history)."
The practical consequence is the one that makes the algorithms in this Part legal at all: because T and R depend on s alone, a single number per state is enough to summarise the entire future from that state, and you may store it and reuse it. In Part 4 a node in the search tree stood for a whole path; here a state stands for itself.
Deck p.10 draws the contrast sharply. In deterministic single-agent search you wanted an optimal plan, a sequence of actions from start to goal. For an MDP you want an optimal policy π*: S → A, which "gives an action for each state". An optimal policy is one that maximises expected utility if followed. The slide adds two remarks worth memorising: "An explicit policy defines a reflex agent", and "Expectimax didn't compute entire policies. It computed the action for a single state only."
A sequence is useless here because you cannot predict where you will be after three steps. A policy is a lookup table, so it has an answer wherever the noise dumps you.
Page 10 also prints one grid, labelled "Optimal policy when R(s, a, s') = −0.03 for all non-terminals s". Page 11 prints four grids for four values of the living reward.
In the bottom-right grid, R(s) = −2.0, the cell immediately below the −1 exit points North, straight into the −1. In the top-left grid, R(s) = −0.01, that same cell points away from it. Explain why walking into a penalty can be optimal, in terms that mention only the two numbers involved.
Because with a living reward of −2.0 per step, staying alive is more expensive than the penalty. Taking the −1 exit costs one step, then 1. Walking round the wall to the +1 takes four steps, along the bottom and up the third column, so it costs three extra steps before any reward arrives. At R(s) = −2.0 those three steps cost −6, which is far worse than the −1. At R(s) = −0.01 they cost −0.03, so the detour is worth it and the arrow turns away from the −1.
Reading the four grids as a sequence: at −0.01 the agent takes the long safe route round the far side of the −1 and is willing to bump walls to avoid risk; at −0.03 it still avoids the −1 but takes shorter routes; at −0.4 it takes the short risky route past the −1; at −2.0 it dives into whichever exit is nearest, including the bad one.
2023 sample theory exam, multiple choice 1.7, verbatim
"For an MDP (S, A, T, γ, R) if we only change the reward function R the optimal policy is guaranteed to remain the same."
Deck p.12 introduces the second running example, and it is the one the deck computes with. A robot car wants to travel far, quickly. Three states: Cool, Warm, Overheated. Two actions: Slow, Fast. Going faster gets double reward. The graph on the slide gives:
| State | Action | Outcomes | Reward |
|---|---|---|---|
| Cool | Slow | Cool with probability 1.0 | +1 |
| Cool | Fast | Cool 0.5, Warm 0.5 | +2 |
| Warm | Slow | Cool 0.5, Warm 0.5 | +1 |
| Warm | Fast | Overheated 1.0 | −10 |
| Overheated | terminal, no actions | ||
Three states and two actions. How many q-states, that is pairs (s, a), does this MDP have? Give the number and the reason.
Four, not six. Overheated is terminal, so it has no available actions and contributes no q-states. The four are (Cool, Slow), (Cool, Fast), (Warm, Slow) and (Warm, Fast).
Why it matters: the q-table you would fill in for this MDP has four rows, and the terminal state gets a V of 0 for ever but no Q entries at all. Miscounting here is the same error as forgetting that the terminal row of a value-iteration table stays 0.
Four of the green circles in this tree have a single outgoing arrow instead of two. Identify which q-states they are, and say what a single child does and does not tell you about the MDP.
Three of them are (Cool, Slow), whose only outcome is Cool with probability 1.0: the left circle under the root, and the left circle under each of the two Cool cars on the next level. The fourth is (Warm, Fast), the right circle under the Warm car, whose only outcome is Overheated with probability 1.0. Since the same q-state can occur at several places in a tree, one q-state can account for several single-child circles, which is the redundancy p.29 complains about.
A single child means that this particular transition distribution happens to be degenerate. It does not make the MDP deterministic: the remaining q-states still fan out 0.5 and 0.5. This is worth watching in the exam, because a question that says "the transitions are deterministic" (the sample exercise exam Q2 says exactly that) removes the expectation everywhere, whereas a single-child chance node removes it in one place only.
Map each of the three labelled objects on this slide onto its Part 8 name, then say what the new name buys you that the Part 8 name did not.
The blue triangle s is a max node. The green circle (s, a) is a chance node, here renamed a q-state. The edge (s, a, s') is a transition, and the slide attaches two functions to it, T(s,a,s') = P(s'|s,a) and R(s,a,s').
What the new name buys: a chance node in Part 8 existed once per path and was discarded once the value was propagated. A q-state exists once per (state, action) pair in the whole problem, so it can carry a stored number Q*(s,a) that you reuse everywhere that pair occurs. That reuse is the entire difference between expectimax and value iteration.
Deck p.15 asks what preferences an agent should have over reward sequences, with two comparisons: [1,2,2] against [2,3,4] (more or less?) and [0,0,1] against [1,0,0] (now or later?). Page 16 answers the second: it is reasonable to prefer rewards now, and one solution is that "values of rewards decay exponentially". A reward is worth 1 now, γ next step and γ2 in two steps.
The diamonds shrink from left to right. What would γ = 1.5 do to this picture, and which two things break? The published creature answer names one of them.
With γ = 1.5 the diamonds would grow, so later rewards would be worth more than the same reward now, which reverses the stated preference. Two things break. First, the modelling intent: the published exercise answer calls 1.5 a "Nonsensical γ value: Creature prefers long walks over short walks, and policies might even be pointing away from high rewards eventually". Second, the mathematics: with γ ≥ 1 the infinite sum need not converge, which is the problem p.20 is about, and the convergence bound γk max|R| on p.49 no longer shrinks.
The same published answer rules out γ = −0.5 as well, because a negative discount makes the agent prefer walks with an even number of steps to positive goals.
Exercise session 6, question 4.3, verbatim (archetype A17)
"It is more interesting that the creature collects nearby common resources rather than spend a long time collecting further, rarer resources. How do you define your value function to reflect this? Which of the following γs would be most sensible: 1.5, 1, 0.9, 0 or −0.5?"
![Slide explaining how and why to discount, with the worked line U([1,2,3]) = 1*1 + 0.5*2 + 0.25*3](assets/part09/08-c4dc7f10.jpg)
The slide asserts U([1,2,3]) < U([3,2,1]) with a discount of 0.5. Compute both numbers and confirm it. Then state the general rule in one sentence: a reward collected by the n-th action in a sequence is multiplied by what?
U([1,2,3]) = 1·1 + 0.5·2 + 0.25·3 = 1 + 1 + 0.75 = 2.75.
U([3,2,1]) = 1·3 + 0.5·2 + 0.25·1 = 3 + 1 + 0.25 = 4.25. So 2.75 < 4.25, as claimed.
General rule: the reward of the n-th action is multiplied by γn−1. The very first reward is undiscounted. The deck's own wording on p.17 is "Each time we descend a level, we multiply in the discount once", and the second reason it gives for discounting at all is that it "helps our algorithms converge".
Deck p.18 is the theory slide. If preferences are stationary, that is if prefixing both of two reward sequences with the same reward leaves your preference between them unchanged, then there are only two ways to define utilities: additive utility and discounted utility. Additive utility is the special case γ = 1.
Deck p.18 prints the theorem and then, in brackets, "proof: out of scope". Know the statement, the two resulting forms, and that additive is discounted with γ = 1. Do not spend time on the proof.
This little corridor is the closest thing in the deck to the sample exercise exam question, so work it properly. Five states a, b, c, d, e in a row. Exiting from a pays 10; exiting from e pays 1. The actions are East, West and Exit, with Exit available only in a and e, and all transitions deterministic. The slide is reproduced immediately below, and on that rendered page the three quizzes appear with empty answer boxes and no worked values, so the answers given here were derived and checked numerically rather than copied.
(1) For γ = 1, what is the optimal action in each of b, c, d, and in e? (2) For γ = 0.1, same question. (3) The one the slide leaves open: for which γ are West and East equally good in state d?
Use the rule from p.17. From a state, walking k steps and then exiting collects the exit reward as the (k+1)-th action, so its value is γk times that reward.
Quiz 1, γ = 1: nothing decays, so 10 always beats 1. West in b, c and d, and also West in e, because from e walking four steps west and exiting still pays the full 10 against 1 for exiting on the spot. In a, Exit.
Quiz 2, γ = 0.1: from b, West gives 0.1·10 = 1 against East giving 0.13·1 = 0.001, so West. From c, West gives 0.12·10 = 0.1 against East 0.12·1 = 0.01, so West. From d, West gives 0.13·10 = 0.01 against East 0.1·1 = 0.1, so East. In e, Exit (1 against 0.14·10 = 0.001). In a, Exit.
Quiz 3: from d, West is three steps then Exit, worth γ3·10; East is one step then Exit, worth γ·1. Setting them equal: 10γ3 = γ, so 10γ2 = 1 and γ = 1/√10 ≈ 0.3162. Check: 10·(0.31623)3 = 0.31623 = 0.31623·1.
Why it matters: this is the same shape of reasoning the sample exercise exam Q2 part 2 wants, "is there a value for γ such that this policy is strictly better than the other two". Set two policy values equal, solve for γ, and then check which side of the crossing point each policy wins on.
Deck p.20 asks the question directly: what if the game lasts for ever, do we get infinite rewards? If every non-terminating branch is worth infinity then all of them are equally good and nothing can be chosen. The slide lists three solutions:
the discounting approach is the most important one here. So that's the one we will keep on working with.(Lecturer, T8), said immediately after listing the three fixes. Know all three by name and one line each; expect to use only discounting. Note also what racing does not give you: Overheated is a terminal state, but p.20's absorbing-state fix requires a terminal state to be reached eventually under every policy, and the policy that always plays Slow at Cool never leaves Cool. So racing at γ = 1 is not rescued by Overheated, and indeed its values keep climbing (sections 14 and 15). The p.48 example gets away with no discount only because it stops at k = 2.
Constructed, in the sample paper's format (the 2023 theory MC block is entirely true or false, one item per lecture)
"The racing MDP has a terminal state, Overheated, so by the absorbing-state solution of p.20 its utilities are finite under every policy and no discount is needed."
Put this recap next to the definition on p.8. One item appears here that was not on p.8, and one item from p.8 is not repeated here. Name both, and say why the new one had to wait until now.
New here: the discount γ, printed on the rewards line as "Rewards R(s,a,s') (and discount γ)". Not repeated: "maybe a terminal state"; p.21 lists states, start state, actions, transitions, rewards and discount.
Why γ waited: it is not part of the world, it is part of the objective. Pages 15 to 20 were needed to explain what problem it solves. The exam consequence is that γ is something you may be asked to choose and justify (exercise session 6 question 4.3, and the sample exam Q2 part 2), whereas S, A, T and R are given by the problem.
The same slide also summarises the two quantities defined so far: "Policy = Choice of action for each state" and "Utility = sum of (discounted) rewards".
Deck p.23 defines the three objects that the rest of the Part computes:
V*(s) and Q*(s,a) differ in exactly one respect. State it in one sentence, then write the equation that follows from it.
Q* has the first action forced to a and behaves optimally only from the second step onward; V* behaves optimally from the very first step. Therefore
V*(s) = maxa Q*(s,a)
which is the first of the three Bellman equations printed on p.26. The immediate corollary, also on p.26, is π*(s) = argmaxa Q*(s,a): same maximisation, you just keep the argument instead of the value.
Pages 24 and 25 are the pair of screenshots that separate the two objects visually, both taken from the same run with noise 0.2, discount 0.9 and living reward 0. This is the pair to burn in, because reading the wrong one is a cheap way to lose an exercise mark.
The top row reads 0.64, 0.74, 0.85, 1.00 and the cell below the 0.85 reads 0.57. Cover the 0.85 and rebuild it. The action drawn there is East, the noise is 0.2 (so 0.8 intended, 0.1 to each side) and γ = 0.9. Careful: North from that cell is the top wall.
East from that cell: 0.8 into the +1 square (value 1.00), 0.1 North which bumps the top wall and stays (value 0.85), 0.1 South into the cell below (value 0.57). The living reward is 0, so
Q = 0.8·(0 + 0.9·1.00) + 0.1·(0 + 0.9·0.85) + 0.1·(0 + 0.9·0.57) = 0.7200 + 0.0765 + 0.0513 = 0.8478, which prints as 0.85.
The other three actions, computed from the exact converged values rather than the two-decimal numbers printed on the slide (the exact values are 0.8478 here, 0.7444 to the west and 0.5719 below), come out at
North 0.7674 West 0.6637 South 0.5687
so East at 0.8478 is indeed the maximum and the printed arrow is right. Those three round to 0.77, 0.66 and 0.57, which are exactly the three q-values printed for this cell on p.25, so the check closes.
Why it matters: this is the check that catches a wrong wall rule, and West is where it bites. West itself leads to the 0.74 cell; the perpendiculars for West are South and North, so the 0.1 South slip lands on the 0.57 cell below and only the 0.1 North slip bounces off the top wall and stays put:
Q(West) = 0.8·(0.9·0.7444) + 0.1·(0.9·0.5719) + 0.1·(0.9·0.8478) = 0.6637
Sending both slips back to the current cell instead gives 0.686, which contradicts the 0.66 printed on p.25. Read the perpendiculars off the action, not off the picture.
The cell immediately left of the −1 exit is split into four triangles reading 0.57 on top (North), 0.53 on the left (West), −0.60 on the right (East) and 0.30 at the bottom (South). Give π*(s) and V*(s) for that cell, and then say which number on p.24 you have just predicted.
π*(s) = North, because 0.57 is the largest of the four. V*(s) = 0.57, the same number, because V* is the max over the q-values. Turn to p.24 and that cell does read 0.57 with a North arrow.
That is the whole relationship between the two slides: p.24 is p.25 with the max already taken. Four numbers per cell collapse to one number plus one arrow. Nothing else differs, the run is the same.
An exercise question that hands you V values (exercise session 6 question 1, and the creature question 4c) needs a full one-step lookahead for every action before you can name the best action. A question that hands you Q values needs one comparison. Check which you have before you start computing, and say which you assumed.
Constructed, in the sample paper's format (the 2023 theory MC block is entirely true or false)
"Given the table of Q*(s,a) values for an MDP, you still need the transition function T and the reward function R in order to work out the optimal action in a state."
Deck p.26 prints all three. The heading of the slide is a summary in itself: computing the value of a state is "just what expectimax computed", the expected utility under optimal action, that is the average sum of discounted rewards.
V*(s) = maxa Q*(s,a)
Q*(s,a) = Σs' T(s,a,s') [ R(s,a,s') + γ V*(s') ]
V*(s) = maxa Σs' T(s,a,s') [ R(s,a,s') + γ V*(s') ]
π*(s) = argmaxa Q*(s,a)
The third line is the first two substituted into each other, and it is the line everything else in this Part is a variation on. Read it out loud in words, because that is how you will reconstruct it under exam pressure: for each action, for each possible successor, take the probability of landing there times the reward you get for landing there plus the discounted value of being there; add those up; then take the best action.
A very common wrong version moves R outside the sum: R(s,a) + γ Σs' T(s,a,s') V(s'). Construct the smallest possible case where the two differ, using the published creature-in-cave arithmetic.
They differ as soon as R depends on s'. In the creature exercise, one of the published one-step updates is
V'(s) = 0.8·[0 + 0.9·0] + 0.1·[0 + 0.9·0] + 0.1·[−10 + 0.9·0] = −1
Here the reward is 0 for two of the three outcomes and −10 for the third (a 10 percent slip into lava). The wrong grouping needs a single R for the whole action, and there is no such number: pulling out −10 gives −10, pulling out 0 gives 0, and the correct answer is −1. In micro-blackjack the two groupings happen to agree, because R(s, Stop, Done) = s does not depend on s'; that coincidence is what makes the mistake survive undetected until a grid question.
Say it as a rule: the reward lives inside the expectation, because which reward you get depends on which successor you land in.
Constructed, in the sample paper's format (the 2023 theory MC block is entirely true or false)
"If the reward never depends on the successor, that is if R(s,a,s') takes the same value for every s', then R(s,a) + γ Σs' T(s,a,s') V(s') is the same number as Σs' T(s,a,s') [ R(s,a,s') + γ V(s') ]."
Pages 27 to 29 redraw the racing tree and then state the two objections.
The slide states two problems and two ideas, plus a note. Write the pairs, and explain in one sentence why the note is what makes the second idea safe.
Problem 1: states are repeated. Idea 1: "Only compute needed quantities once", which is the V table: one number per state, reused wherever that state appears in the tree.
Problem 2: the tree goes on for ever. Idea 2: "Do a depth-limited computation, but with increasing depths until change is small", which is value iteration.
The note: "deep parts of the tree eventually don't matter if γ < 1". Without it, "until change is small" would be wishful thinking, because a reward arbitrarily far away could still swing the answer. With γ < 1 the contribution of level k is bounded by γk max|R|, which is exactly the convergence sketch on p.49.
Deck p.30 gives the definition that makes the animation readable. Vk(s) is the optimal value of s if the game ends in k more time steps. Equivalently, it is what a depth-k expectimax would return from s. Pages 31 to 44 then run k from 0 to 12 and jump to 100 on the same grid world, with noise 0.2, discount 0.9, living reward 0 printed on every frame.
The +1 and −1 squares behave as states whose only available action is an exit to a terminal state, paying +1 or −1. That is why they read 0.00 at k = 0 and only turn into 1.00 and −1.00 at k = 1. With that reading, plus 0.8 intended and 0.1 to each side, walls bouncing the agent back to where it stood, living reward 0 and γ = 0.9, every printed number on pp.31 to 34, p.44, p.24 and p.25 reproduces exactly. This reconstruction is stated here so you can check your own arithmetic against the slides; the parameters printed on the slides themselves are the noise, the discount and the living reward.
From the definition alone, what is V0(s) for every state s, and what is Vk(terminal) for every k? Give the reason, not just the number.
V0(s) = 0 for every s, because with zero time steps remaining no action can be taken and therefore no reward can be collected. Page 47 says this in words: "no time steps left means an expected reward sum of zero".
Vk(terminal) = 0 for every k, for the same reason applied at a state with no available actions. This is the row of the table that people forget to keep filling in, and it is a named classic mistake for archetype A18.
Constructed, in the sample paper's format (the 2023 theory MC block is entirely true or false)
"In the grid-world run of pp.31 to 44 (noise 0.2, γ = 0.9, living reward 0), the +1 exit square already reads 1.00 in the frame labelled VALUES AFTER 0 ITERATIONS."
Every cell reads 0.00, including the +1 and −1 squares. Why is the +1 square not already showing 1.00 at k = 0?
Because the +1 is collected by an action, not by occupancy. Standing on the good square is worth nothing; taking the exit action from it is worth +1, and that action costs a time step. With zero steps left there is no action, so the value is 0.
Why it matters: in the sample exercise exam Q2 the teleport is worth 20 and moving right is worth 10, and both are rewards for taking an action. If you treat rewards as belonging to states rather than to transitions, your discount exponents will all be off by one.
Exactly two cells changed at k = 1: the +1 square to 1.00 and the −1 square to −1.00. The cell immediately to the left of the +1 square is still 0.00. Show why, with the numbers.
Its best action is East, which succeeds with probability 0.8 and lands on the +1 square. But the update uses V0 for the successor, and V0(+1 square) = 0:
Q = 0.8·(0 + 0.9·0) + 0.1·(0 + 0.9·0) + 0.1·(0 + 0.9·0) = 0
Reward reaches a cell one sweep at a time, and it takes two sweeps to travel one square here because collecting the +1 itself consumes one of them. That is why the good news spreads outward from the exits like a slow wave through pp.32 to 44.
At k = 2 the cell left of the +1 square shows 0.72. Derive it from V1.
V1 is 1.00 on the +1 square, −1.00 on the −1 square and 0 everywhere else. From the cell left of the +1, action East: 0.8 to the +1 square, 0.1 North which bumps the top wall and stays, 0.1 South into the cell below.
Q = 0.8·(0 + 0.9·1.00) + 0.1·(0 + 0.9·0) + 0.1·(0 + 0.9·0) = 0.72
Note what the 0.72 is made of: 0.8 for the chance of actually going where you meant, and 0.9 for one step of discounting. Neither factor is optional.
(a) Compute the 0.43 in the middle row (the cell below the 0.78, left of the −1 exit) from V2. Its North neighbour is the 0.72 cell of p.33, its West neighbour is the wall, its East neighbour is the −1 square. (b) Now recompute it as though you had already overwritten the top row with its new k = 3 value of 0.78, and report the number you get.
(a) Correct, simultaneous update. Best action North. 0.8 North to the cell whose V2 is 0.72; perpendicular for North is West and East; West is the wall so the agent stays (V2 = 0); East is the −1 square (V2 = −1.00).
Q = 0.8·(0 + 0.9·0.72) + 0.1·(0 + 0.9·0) + 0.1·(0 + 0.9·(−1.00)) = 0.5184 + 0 − 0.09 = 0.4284, printed as 0.43.
(b) In-place update, the wrong way. Using the fresh V3(top cell) = 0.7848 instead:
0.8·(0.9·0.7848) + 0.1·(0.9·0) + 0.1·(0.9·(−1.00)) = 0.565056 − 0.09 = 0.475056, that is 0.4751
You would write 0.48 and every later row would drift. This is the single most common way to fail archetype A18. Keep two columns, Vk and Vk+1, and never read from the column you are writing.
For completeness, the other two changed cells at k = 3: the top-row 0.52 is 0.8·0.9·0.72 = 0.5184, and the 0.78 is 0.8·0.9·1.00 + 0.1·0.9·0.72 = 0.7848.
In the bottom row the cells read 0.49, 0.43, 0.48 and 0.28. The 0.28 sits directly below the −1 exit and is much lower than its left neighbour 0.48. Its arrow points West. Explain both the low number and the direction, using the q-values from p.25 (North −0.65, South 0.27, East 0.13, West 0.28).
The cell is adjacent to the −1 exit, and noise means that any action with a 0.1 sideways component towards it carries real risk. North is catastrophic here (−0.65) because it walks into the penalty 0.8 of the time. West is best at 0.28, and V* is that maximum, hence 0.28.
The gap to 0.48 next door is the price of proximity to the penalty. The four grids on p.11 are the same phenomenon read the other way: change the living reward and this cell's arrow is one of the first to flip.
Deck p.47 states the algorithm. Start with V0(s) = 0 for all s. Given the vector of Vk(s) values, do one ply of expectimax from each state:
Vk+1(s) ← maxa Σs' T(s,a,s') [ R(s,a,s') + γ Vk(s') ]
Repeat until convergence. The slide gives the cost per iteration as O(S2A), states the theorem that it converges to unique optimal values, and adds the observation that pays off later: "Policy may converge long before values do".
The left side carries k+1 and the right side carries k. Translate that into two rules for a pen-and-paper table, and state where the O(S2A) comes from, factor by factor.
Rule 1: one whole row of the table is computed from the previous row, all states at once. No cell of row k+1 may be used while computing row k+1.
Rule 2: the terminal row stays 0 for ever, since the max over an empty action set is defined to be 0 here.
The complexity: one factor of S because you update every state; one factor of A because you try every action at that state; one more factor of S because each action's sum runs over every possible successor. S · A · S = O(S2A). Remember this decomposition, because dropping the max in section 17 removes exactly the A and leaves O(S2), which is the argument on p.71.
The slide stops at V2 = (3.5, 2.5, 0) for (Cool, Warm, Overheated), with no discount. Compute V3. Show both q-values at each state, not just the winner.
With γ = 1 and V2 = (3.5, 2.5, 0):
So V3 = (5, 4, 0). Continuing, V4 = (6.5, 5.5, 0) and V5 = (8, 7, 0): with no discount and an escapable absorbing state the values keep climbing by 1.5 each sweep and never converge. That is p.20's infinite-utility problem happening in front of you, and it is why the slide has to say "Assume no discount!" as a special dispensation for a two-row illustration rather than as a normal setting.
Check the earlier rows too, since they are the ones printed: V1(Cool) = max(1.0·(1+0), 0.5·(2+0)+0.5·(2+0)) = max(1, 2) = 2, and V1(Warm) = max(0.5·1+0.5·1, −10) = 1. Then V2(Cool) = max(1·(1+2), 0.5·(2+2)+0.5·(2+1)) = max(3, 3.5) = 3.5 and V2(Warm) = max(0.5·(1+2)+0.5·(1+1), −10) = 2.5.
Exercise session 6, question 2.5, verbatim (archetype A18, value iteration for k steps)
"Perform value iteration (until convergence) on this problem."
Expect it as a table with a row per k and a column per state, sometimes with a second block of columns for πk. The worked illustration on the 2023-2025 exercise sheet is a six-state one-dimensional grid world with γ = 0.9, and it prints seven numbered rows (k = 0 to 6), then a row of dots, then a V* row.
Over the states (0, 2, 3, 4, 5, Done) with γ = 1, computing each row entirely from the row above:
V0 = (0, 0, 0, 0, 0, 0)
V1 = (0, 2, 3, 4, 5, 0)
V2 = (3, 3, 3, 4, 5, 0)
V3 = (10/3, 3, 3, 4, 5, 0)
V4 = V3, so it has converged.
The one cell that decides the answer is state 2: Q(2, Draw) = (1/3)·4 + (1/3)·5 + (1/3)·0 = 3 against Q(2, Stop) = 2, so you draw even though a third of draws bust. At state 3 it flips, Q(3, Draw) = (1/3)·5 = 5/3 against Q(3, Stop) = 3. The full table and the same run for the one-dimensional grid world are printed immediately below this box.
What earns the marks: showing the two-column discipline (row k+1 built only from row k), keeping the Done column at 0 in every row, and stating the stopping reason ("V4 equals V3, so the values have converged"). The policy is then read off with an argmax on the last row: "Draw" if s ≤ 2, "Stop" otherwise.
The three named classic mistakes: (1) updating in place instead of computing the whole of Vk+1 from Vk; (2) forgetting that the terminal state stays 0; (3) pulling the reward out of the expectation, that is writing R + γΣTV instead of ΣT[R + γV].
Extracting the policy: the published micro-blackjack answer says it plainly, the optimal policy "is given by taking the argmax instead of max, in the final iteration of value iteration".
Both of these are course material and both are worth reproducing by hand once. The arithmetic below was re-run from the problem definitions. It agrees with the published tables everywhere except one cell, which is explained in the footnote.
Micro-blackjack, γ = 1. Converged after three sweeps.
| 0 | 2 | 3 | 4 | 5 | Done | |
|---|---|---|---|---|---|---|
| V0 | 0 | 0 | 0 | 0 | 0 | 0 |
| V1 | 0 | 2 | 3 | 4 | 5 | 0 |
| V2 | 3 | 3 | 3 | 4 | 5 | 0 |
| V3 | 10/3 | 3 | 3 | 4 | 5 | 0 |
| π* | Draw | Draw | Stop | Stop | Stop | Stop |
The interesting cell is state 2. Q(2, Draw) = (1/3)·V(4) + (1/3)·V(5) + (1/3)·0 = (4 + 5)/3 = 3, against Q(2, Stop) = 2, so drawing wins even though a third of draws bust. At state 3 it flips: Q(3, Draw) = (1/3)·5 + (2/3)·0 = 5/3 against Q(3, Stop) = 3. Hence the published one-sentence policy: "Draw" if s ≤ 2, "Stop" otherwise.
The one-dimensional grid illustration, γ = 0.9. Six states A, B, C, D, E and terminal Z, Exit from A pays +10 and from E pays +6, moves succeed with 0.8 and reverse with 0.2, and walking off the end leaves you where you were. Recomputed exactly, the sequence is:
| k | A | B | C | D | E | Z | policy from Vk |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | all tied |
| 1 | 10 | 0 | 0 | 0 | 6 | 0 | B left, D right |
| 2 | 10 | 7.2 | 0 | 4.32 | 6 | 0 | B, C left; D right |
| 3 | 10 | 7.2 | 5.962 | 4.32 | 6 | 0 | B, C left; D right |
| 4 | 10 | 8.273 | 5.962 | 5.393 | 6 | 0 | B, C left; D right |
| 5 | 10 | 8.273 | 6.927 | 5.393 | 6 | 0 | B, C, D all left |
| … | 10 | 8.507 | 7.260 | 6.307 | 6 | 0 | Exit, left, left, left, Exit |
The published table prints one decimal and rounds correctly everywhere except column C: 8.3 for 8.2731, 5.4 for 5.3931, 6.9 for 6.9274, 8.4 for 8.4469, 6.1 for 6.0677 and the V* row 8.5, 7.3, 6.3 all round as printed. The single exception is C, printed as 5.9 where the exact value is 5.962, and the reason is visible in the sheet's own worked line: it computes V3(C) = 0.8·(0 + 0.9·7.2) + 0.2·(0 + 0.9·4.3) = 5.958 from the already rounded V2 entries, whereas the unrounded V2(D) = 4.32 gives 5.962. Either is acceptable in an exam as long as you say which you did. Notice also that state D points right for four sweeps and only flips left at k = 5, once the value of B has propagated through C. A policy that has not stopped changing is not the optimal policy.
Case 2 of the sketch bounds |Vk+1 − Vk| by γk max|R|. What does that bound become at γ = 1, and which of p.20's three fixes is the one that still saves you? Point at a worked example in this chapter where it does save you.
At γ = 1 the bound becomes max|R| for every k, so it never shrinks and proves nothing. The fix that still works is Case 1 on this same slide, restated: guarantee that the process terminates, either by a finite horizon or by an absorbing state that every policy eventually reaches.
Where it saves you: micro-blackjack runs at γ = 1 and converges in three sweeps, because every action eventually reaches Done. The racing example at γ = 1 does not converge, because Slow at Cool can be repeated for ever, which is exactly what the V3, V4, V5 continuation above shows.
The slide title carries an asterisk, and the lecturer says of it, We won't go uh into this uh in more depth
(Lecturer, T8). What to carry: the shape of the argument (Vk and Vk+1 are nearly identical trees differing only in the bottom layer, which is discounted by γk), the bound γk max|R|, and the two cases. Not the proof.
Deck p.51 opens the second half of the Part with three complaints about value iteration (VI):
Pages 52 to 65 then replay the grid world animation. Compare p.31 with p.52, and p.32 with p.53: the frames are identical, the same run at the same settings. What changes is what you are being asked to look at. In the first run you watched the numbers spread; here you watch the small arrows.
Put p.31 and p.52 side by side. What differs between them, and what does that tell you about why the deck shows the animation twice?
Nothing differs. Same numbers, same arrows, same settings line. The deck replays the identical animation because the point being made has changed: p.51 has just claimed that the policy converges before the values, and pp.52 to 65 are the evidence. The reader is being asked to re-watch the same frames tracking a different quantity.
Practical consequence for revision: you do not need to learn pp.52 to 65 as new content. You need one sentence, "the arrows stop moving well before the numbers do", plus the reason.
Nine of the twelve cells still read 0.00, yet three arrows have moved since k = 0. Compare this frame with p.52 and find those three. Then say which arrows on this frame carry information and which do not.
The three that moved are the three neighbours of a lit square: the top-row third cell now points East, the cell left of the −1 points West, and the cell below the −1 points South. Every other cell still shows the default upward arrow.
Those three are strictly determined, not tie-breaks, and this is the point worth taking away: a cell can display 0.00 and still have q-values that differ, because the displayed number is the maximum, not the whole row. Taking the successor values from V1 (1.00 on the +1 square, −1.00 on the −1 square, 0 elsewhere):
The other six non-exit cells genuinely have four q-values of 0, so their arrows are arbitrary tie-breaks fixed by the order in which the implementation scanned the actions, and they carry no information at all.
Implication: "the policy converged" is only meaningful once you fix a tie-breaking rule, and the arrows worth watching are the ones that have already been forced by a nearby reward. In an exam answer, say which tie-break you used, exactly as you would when writing a search frontier in Part 4.
For this grid world (noise 0.2, γ = 0.9, living reward 0), estimate how many sweeps the policy needs and how many the values need. Then say why that gap is the entire argument for policy iteration.
Running the sweeps and extracting the greedy policy after each one, with ties broken in a fixed order: the policy stops changing after sweep 10. At that point the values are still moving by about 0.018 per sweep. They are still moving by about 2 × 10−5 per sweep at sweep 20 and about 5 × 10−9 at sweep 30, and the first sweep that changes nothing at all in double precision is sweep 51.
So the arrows are settled at sweep 10 while the numbers grind on for another forty sweeps, and every sweep after 10 spends O(S2A) work to confirm a decision that was already made. Policy iteration attacks exactly that waste: it makes most sweeps cheap by fixing the action, and only pays the max when it looks for an improvement.
The final policy visible on this frame: the whole top row points East toward the +1; both cells of the middle row point North; and the bottom row alternates, North, West, North, West, from left to right. The two Wests have different causes. The right-hand one sits directly below the −1 and points West because that is the only action with no chance of touching the penalty: its q-values are West 0.277, South 0.267, East 0.135, North −0.652. The left-hand one is nowhere near the −1; there North is a wall and the choice is simply between the 0.49 cell to its left and the 0.48 cell to its right, giving West 0.431 against East 0.420.
This is the centre of gravity of the whole Part for exam purposes. Deck p.67 sets it up with two trees side by side.
How many q-states does each tree expose at the root, and what does that do to the per-iteration complexity you decomposed in section 14?
Left: |A| q-states, one per action, because the tree "maxes over all actions". Right: exactly one, namely (s, π(s)), because the policy has already chosen.
The complexity was S · A · S. Fixing the action deletes the A, leaving O(S2) per iteration, which is the figure printed on p.71. The slide adds the caveat that matters: the tree's value now "depend[s] on which policy we fixed", so what you compute is Vπ, not V*.
Deck p.68 defines the object: Vπ(s) is the expected total discounted reward starting in s and following π. Its recursive relation is the Bellman equation with the max deleted and the action pinned to π(s).
The corridor runs up the middle of the grid; the +100 sits at the top of that corridor and every cell to the left and right of the corridor is a −10. Which of the two policies has the higher value at the bottom of the corridor, and roughly how large is the gap: a few percent, a factor of two, or a change of sign?
Always Go Forward, and the gap is a change of sign. Going Right from inside the corridor aims the agent at a −10 on 0.8 of steps, so the policy is not merely worse, it is actively suicidal. Page 70 gives 33.30 for Forward at the bottom of the corridor against −8.69 for Right.
The exam point this figure exists to make: policy evaluation is defined for policies that are terrible. There is no max in the equation, so nothing rescues a bad choice. That is precisely what makes it useful inside policy iteration, where you evaluate the current, non-optimal policy honestly and only then look for something better.
The Forward column reads 100.00, then 70.20, then 48.74, then 33.30. The noise is 0.2 (0.8 intended, 0.1 to each side), the side cells are −10 and the living reward is 0. Recover γ, then use it to predict 48.74 from 70.20.
From the cell just below the +100, going Forward: 0.8 into the +100 (value 100), 0.1 into the left −10 and 0.1 into the right −10 (value −10 each). So
70.20 = γ·[0.8·100 + 0.1·(−10) + 0.1·(−10)] = γ·78 ⇒ γ = 0.9
Prediction for the next cell down: 0.9·[0.8·70.20 + 0.2·(−10)] = 0.9·54.16 = 48.744, printed as 48.74. And once more: 0.9·[0.8·48.744 − 2] = 33.295, printed as 33.30.
The Right column checks out too, and it needs the full simultaneous system because the three corridor cells depend on each other: solving V2 = 1.8 + 0.09V3, V3 = −7.2 + 0.09V2 + 0.09V4, V4 = −7.2 + 0.09V3 + 0.09V4 gives 1.09, −7.88, −8.69, exactly the printed numbers.
Put this equation next to the value-iteration update on p.47. Exactly one symbol has been deleted. Which, and what two consequences does the slide draw from deleting it?
The deleted symbol is maxa, and with it the action argument is replaced by π(s) everywhere:
Vπ0(s) = 0
Vπk+1(s) ← Σs' T(s, π(s), s') [ R(s, π(s), s') + γ Vπk(s') ]
Consequence 1 (Idea 1 on the slide): the recursion is still a Bellman update, so you can iterate it exactly as in value iteration, at O(S2) per iteration instead of O(S2A).
Consequence 2 (Idea 2 on the slide): "Without the maxes, the Bellman equations are just a linear system", so you could instead solve |S| linear equations in |S| unknowns directly.
This is the most important way that you need to know for this course. There is also um another way uh which is very elegant(Lecturer, T8), said about Idea 1, the iterated Bellman update, before mentioning Idea 2, the system of linear equations. The iterative method with the policy fixed is the required one. Know that the linear-system route exists and why it exists (no max means the equations are linear), but practise the iteration to a stated tolerance, because that is what the exercise sheet asks for.
2023 sample exercise exam, question 2 (2 points), verbatim
"Pacman finds itself in a small bonus maze. The dimensions of this maze are 5 × 1 and there are no ghosts. The cells are numbered 1 to 5. In cells 1 to 4 the following actions are available: move to the right (R), and teleport out of the bonus maze (T). Moving to the right acts deterministically and causes Pacman to end up in the cell to the right of its current position (where Pacman then also consumes the dot). The teleport action also functions deterministically and causes Pacman to end up in a terminal position that causes the game to terminate. In cell 5, the only available action is teleportation. Eating a dot gives a reward of 10, while teleporting out of the maze gives a reward of 20. Pacman starts out in the leftmost cell (cell 1). Consider an MDP for this problem that associates states with the cell in which Pacman is present, and that utilizes a discount factor γ. Consider then the following policies:"
"1. Assume that γ = 1.0. Fill in: Vπ0(1) = ......... Vπ1(1) = ......... Vπ2(1) = ......... V*(1) = ........."
"2. Consider a freely chosen value for γ. (a) Is there a value for γ such that π0 is strictly better than π1 en π2? If yes, specify an appropriate value, if no, write No. (b) Is there a value for γ such that π1 is strictly better than π0 en π2? (c) Is there a value for γ such that π2 is strictly better than π0 en π1?"
Part 1, γ = 1.0. With deterministic transitions this is policy evaluation by addition, no expectation and no sweeps:
Vπ0(1) = 20 Vπ1(1) = 10 + 10 + 10 + 20 = 50 Vπ2(1) = 10·4 + 20 = 60 V*(1) = 60
V*(1) is the best of all stopping points: stopping after n moves right is worth 10n + 20, maximised at n = 4, which is what π2 does.
Part 2. As functions of γ, using the rule that the n-th action's reward carries γn−1: Vπ0 = 20, Vπ1 = 10 + 10γ + 10γ2 + 20γ3, Vπ2 = 10 + 10γ + 10γ2 + 10γ3 + 20γ4. All three curves meet at γ = 1/2, where every policy is worth exactly 20.
(a) Yes, any γ < 1/2, for example γ = 0.25, where the values are 20, 13.4375 and 13.359375.
(b) No. π1 beats π2 only when γ < 1/2, and in exactly that range it loses to π0; at γ = 1/2 all three tie, which is not strictly better.
(c) Yes, any γ > 1/2, for example γ = 1 (20, 50, 60) or γ = 0.6 (20, 23.92, 24.352).
What earns the marks: in part 1, four numbers and the observation that V*(1) is achieved by one of the given policies. In part 2 you do not need the factorisations; two or three trial values of γ plus the argument is enough: a small γ makes the far-off teleport bonus worthless so grabbing 20 now wins, a large γ makes every dot worth nearly its face value so collecting all four wins, and π1 is never best because it is a strict compromise, beaten on the impatient side by π0 and on the patient side by π2. Do not start a Vk table: the transitions are deterministic and the question is about γ, not about sweeps.
Section 21 below works this same question line by line, including the factorisations and the check at γ = 1/2. To watch the three values cross, open viz-mdp.html and set γ near 0.5 on the corridor.
Exercise session 6, question 3. Four states s0, s1, s2, s3 in a row, s3 is the end state, only Left and Right are available, γ = 0.5. The agent reaches the intended state with probability 0.9 (or stays put, if the action would take it off the grid) and moves the opposite way with probability 0.1. Landing in any of the three left-most states pays −0.05; landing in the rightmost state pays +1. The initial policy π0 is Left in all three non-terminal states. The stopping rule is |Vk+1(s) − Vk(s)| ≤ 0.01 for all s.
| s0 | s1 | s2 | s3 | max |Vk − Vk−1| | |
|---|---|---|---|---|---|
| V0 | 0 | 0 | 0 | 0 | n/a |
| V1 | −0.050 | −0.050 | +0.055 | 0 | 0.055 |
| V2 | −0.075 | −0.070 | +0.032 | 0 | 0.025 |
| V3 | −0.087 | −0.082 | +0.024 | 0 | 0.012 |
| V4 | −0.093 | −0.088 | +0.018 | 0 | 0.006 |
Recomputed at full precision; the published table truncates to three decimals, so it prints −0.069 for V2(s1) against −0.0698 exact, and +0.023 for V3(s2) against +0.0236 exact. The stopping decision is unaffected: the first sweep whose maximum change is at or below 0.01 is sweep 4, which is where the published table stops. Note s2 is positive from the first sweep even under the Left policy, because 0.1 of the time the agent slips right into the +1 end state.
Derive V1(s0) and V1(s2) from V0 = 0, using π0 = Left. Say why they differ in sign.
V1(s0): Left from s0 would leave the grid, so with probability 0.9 the agent stays in s0, which is a left-most state and pays −0.05; with probability 0.1 it slips right into s1, also −0.05.
0.9·(−0.05 + 0.5·0) + 0.1·(−0.05 + 0.5·0) = −0.05
V1(s2): Left from s2 reaches s1 with 0.9 (paying −0.05), and slips right into the end state s3 with 0.1 (paying +1).
0.9·(−0.05 + 0) + 0.1·(1 + 0) = −0.045 + 0.1 = +0.055
They differ in sign because s2 is the only non-terminal state from which the noise can accidentally deliver the +1. Follow that through the table and it is the reason the whole policy is about to flip.
Constructed example, built on the deck's own racing MDP (p.12). Fix the policy π(Cool) = Slow, π(Warm) = Fast, and set γ = 0.5. Evaluate it. Overheated is terminal, so Vπ(Overheated) = 0 for ever, and Warm settles immediately because Fast from Warm is deterministic:
| k | Cool | Warm | Overheated | max |ΔV| |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | n/a |
| 1 | 1 | −10 | 0 | 10 |
| 2 | 1.5 | −10 | 0 | 0.5 |
| 3 | 1.75 | −10 | 0 | 0.25 |
| 4 | 1.875 | −10 | 0 | 0.125 |
| 5 | 1.9375 | −10 | 0 | 0.0625 |
| 6 | 1.96875 | −10 | 0 | 0.03125 |
| 7 | 1.984375 | −10 | 0 | 0.015625 |
| 8 | 1.9921875 | −10 | 0 | 0.0078125 |
Constructed example, using the course's racing MDP with a fixed policy of my choosing. Stopping at tolerance 0.01 means stopping after sweep 8. The exact fixed point is Vπ(Cool) = 2, from V = 1 + 0.5V, and Vπ(Warm) = −10. Two things to notice. First, the change halves at every sweep, which is γ = 0.5 in action and is the p.49 bound γk max|R| made concrete. Second, the value of Warm is −10 and no amount of iteration improves it, because policy evaluation has no max: fixing a bad action means living with it.
Deck p.73 poses the question that the V table does not answer by itself: suppose we have the optimal values V*(s), how should we act? The slide's own comment is "It's not obvious!". You need a mini-expectimax of one step:
π*(s) = argmaxa Σs' T(s,a,s') [ R(s,a,s') + γ V*(s') ]
The slide names this policy extraction, "since it gets the policy implied by the values".
Why is the answer not simply "point at the neighbouring cell with the largest value"? Use the published creature-in-cave numbers: at the cell in question the neighbour above is worth 2.82, the neighbour to the left 2.10 and the neighbour below 1.83, and the neighbour to the right is lava worth −10. Movement is 80 percent intended and 10 percent to each side, γ = 0.9.
Because the sideways slips have to be paid for. The published evaluation of all four actions at that cell:
The largest neighbour is 2.82, upwards. The optimal action is Left, at 1.93 against 1.22, because Up carries a 10 percent chance of sliding into the lava on the right, and Left carries none. The published conclusion is that the creature goes Left "and thus avoid the possibility of falling into lava".
Named classic mistake for archetype A20: with stochastic transitions you must compute the weighted sum for each of the four actions rather than pointing at the largest neighbour.
Exercise session 6, question 1, verbatim (archetype A20, read the policy off V)
"Which is the best action an agent can execute if he is currently in the center state of the grid world? Justify your answer." You are given eight surrounding V* values (top row 8, 15, 12; then 2 and 10 beside the centre; bottom row 7, 16, 11) and a 0.7 / 0.2 / 0.1 noise model with γ = 1 and no rewards.
Compute all four one-step lookaheads. With no rewards and γ = 1 each is just a weighted average of three neighbouring values, 0.7 to the intended cell, 0.2 to the right of the intended direction and 0.1 to the left:
North 0.7·15 + 0.2·12 + 0.1·8 = 13.7 East 0.7·10 + 0.2·11 + 0.1·12 = 10.4
South 0.7·16 + 0.2·7 + 0.1·11 = 13.7 West 0.7·2 + 0.2·8 + 0.1·7 = 3.7
North and South tie at 13.7, so both are optimal, which is the published answer word for word: "Both going North and going South results in 13.7, so both actions are the best actions when being in the center."
What earns the marks: the four sums written out, the tie named rather than silently broken, and one sentence saying which neighbour the 0.2 went to. "Justify your answer" is the instruction that turns this from a one-word answer into a marked one. Pointing at the largest neighbour, 16, happens to name a correct action here and would still lose marks, because the reasoning is wrong and the 0.2 flank is what actually decides it.
The published solution computes all four: North 0.7·15 + 0.2·12 + 0.1·8 = 13.7; East 0.7·10 + 0.2·11 + 0.1·12 = 10.4; South 0.7·16 + 0.2·7 + 0.1·11 = 13.7; West 0.7·2 + 0.2·8 + 0.1·7 = 3.7. North and South tie at 13.7, so both are optimal.
Why this question exists: the single largest neighbour is 16, which sits South. A student who points at the biggest number gets the right answer for the wrong reason and would have been wrong had the 16 been flanked differently. Compute all four, say the tie out loud, and note that the 0.2 goes to the right of the intended direction and the 0.1 to the left, not the other way round.
The cell immediately left of the −1 exit shows q-values 0.76 (North), 0.89 (West), −0.62 (East) and 0.70 (South). West runs straight into the wall, so the agent mostly does not move. Why is that the best action here?
Because West is the only action with zero probability of touching the −1. Aiming West sends the agent into the wall with 0.8 (it stays), North with 0.1 and South with 0.1. Aiming North instead sends it North with 0.8, but its two perpendicular slips are West (the wall, harmless) and East, which is the −1 exit. That 10 percent chance of a −1 is worth more than the 0.8 chance of one step of progress, so 0.76 loses to 0.89.
These numbers come from a different setting than pp.24 and 25: reconstructing them gives noise 0.2, discount 1.0 and living reward −0.01, which reproduces all nine printed V values on p.73 and all 36 printed q-values on p.74 to two decimals (nine non-exit cells, four actions each). With a living reward of only −0.01, waiting is almost free, so caution wins.
The slide's own summary line is the one to memorise: "Important lesson: actions are easier to select from q-values than values!" From Q it is one comparison; from V it is the four-line computation of the previous task.
if you are moving towards machine learning, you learn the Q values and not the V values because it is much easier to determine your policy based on the Q values.(Lecturer, T8), said immediately after the two extraction slides. This is also the boundary marker for the course: the lecturer places reinforcement learning immediately beyond this point and says of it
we don't cover here. If your Machine Learning course asks you to fill a Q-table from observed episodes, that is the other course's algorithm and it does not use T at all. See "What this sets up" below.
Deck p.76 states the loop, and the method it defines is policy iteration (PI). Step 1, policy evaluation: calculate utilities for some fixed policy, "not optimal utilities!", until convergence. Step 2, policy improvement: update the policy using one-step lookahead with the resulting "converged (but not optimal!)" utilities as future values. Repeat until the policy converges. The slide adds two claims: "It's still optimal!" and "Can converge (much) faster under some conditions".
The evaluation formula carries a subscript k and a superscript πi; the improvement formula carries a subscript i+1. What does each index count, and which of the two formulas contains a maximisation?
k counts the sweeps of the inner loop, the repeated Bellman updates that evaluate one fixed policy to convergence. i counts the outer loop, the policy improvements. So a full run looks like: evaluate π0 over k = 0, 1, 2, … until the values settle; improve once to get π1; evaluate π1 over a fresh k = 0, 1, 2, …; and so on.
Only the improvement formula has a maximisation, and it is an argmax rather than a max because it produces an action, not a number. The evaluation formula has no max at all, which is the whole reason it is cheap.
Practical rule for the exam: if you find yourself writing "max" inside a policy evaluation step, you have merged the two loops and are doing value iteration by accident.
Exercise session 6, question 3, verbatim (archetype A19, one full iteration of policy iteration)
"Consider the grid world on Figure 2, and let γ = 0.5 and let there be only the actions Left and Right. The rightmost state is the end state. With probability 0.9 the agent reaches the intended state (or stays where he was, if the action would move him out of the grid), and with probability 0.1 he moves in the opposite direction. If an action results in one of the three left-most states, the reward is −0.05. If the action results in the rightmost state, the reward is +1. The initial policy π0 is given by the arrows in the states. Perform one iteration of the policy-iteration algorithm. Run the policy-evaluation part until |Vk+1(s) − Vk(s)| ≤ 0.01 for all s."
Step 1, evaluation of π0 = Left everywhere. The four sweeps are tabulated in section 17 just above: V1 = (−0.050, −0.050, +0.055), V2 = (−0.075, −0.070, +0.032), V3 = (−0.087, −0.082, +0.024), V4 = (−0.093, −0.088, +0.018) over (s0, s1, s2), with s3 = 0 throughout. The largest change at sweep 4 is 0.006, which is the first sweep at or below the tolerance, so you stop there.
Step 2, improvement. One argmax per non-terminal state, using V4 as the future values: at s0 Left = −0.09642 against Right = −0.09430; at s1 Left = −0.09111 against Right = −0.04655; at s2 Left = +0.01537 against Right = +0.89060. So π1 is Right in s0, s1 and s2, and s3 needs no action because it is the end state.
What earns the marks: the evaluation table with a change column so the stopping rule is visible, the tolerance applied to all states rather than one, both q-values written at each state in the improvement step, and one sentence saying that a second iteration would be needed before you may declare convergence. Writing a max inside the evaluation step is the mistake that turns this answer into value iteration.
Continuing the table of section 17, improvement from V4 = (−0.093, −0.088, +0.018, 0) with γ = 0.5:
These six numbers use the unrounded V4 = (−0.093363, −0.088076, +0.018044, 0). Feeding in the three-decimal values as printed in the table gives −0.09625 against −0.09425 at s0, −0.09095 against −0.04655 at s1 and +0.01540 against +0.89060 at s2. Every comparison points the same way, so the improved policy is the same either way; just say which precision you carried.
So π1 is Right everywhere, which is the published answer. The published note is worth carrying into the exam: "It is not needed to compute the optimal action in s3 since this is the goal state", and "it will take another iteration of policy iteration to realise that the algorithm converged". Convergence is detected by a full iteration that changes nothing, so a question asking for "one iteration" wants evaluate-then-improve, and does not want you to declare victory.
Named classic mistakes: putting a max in the evaluation step; applying the tolerance test to one state instead of all of them; forgetting that the terminal state has no action to improve.
"Value iteration computes values but not a policy, which is why we need policy iteration." True or false, and correct it if false, citing this slide.
False. The slide says "Every iteration updates both the values and (implicitly) the policy. We don't track the policy, but taking the max over actions implicitly recomputes it." Every max is an argmax you chose not to record.
The real difference is in where the work goes. Value iteration pays for a max at every state on every sweep. Policy iteration does several cheap passes with the action fixed (each O(S2)) and only occasionally pays for a full max pass (O(S2A), "slow like a value iteration pass"). The slide's closing line is the unifying one: "Both are dynamic programs for solving MDPs".
they are different algorithms but the final effect is that both will result in the optimal policy.(Lecturer, T8), also printed on p.78 as "Both value iteration and policy iteration compute the same thing (all optimal values)". Emphasised in the lecture as "very important to note". If a theory question asks whether VI and PI can disagree about π*, the answer is no, up to ties between equally good actions.
Deck p.79 is the slide to reread the night before. Three tasks, three tools, one mechanism:
| So you want to… | Use | Does it have a max? |
|---|---|---|
| Compute optimal values | value iteration or policy iteration | Yes, over all actions, every sweep |
| Compute values for a particular policy | policy evaluation | No. The action is pinned to π(s) |
| Turn your values into a policy | policy extraction (one-step lookahead) | Yes, as an argmax, once |
The slide's own commentary: "These all look the same! They basically are, they are all variations of Bellman updates. They all use one-step lookahead expectimax fragments. They differ only in whether we plug in a fixed policy or max over actions."
That last sentence is the most compact revision aid in the Part. If you can write the one-step lookahead fragment Σs' T(s,a,s')[R(s,a,s') + γV(s')] from memory, then value iteration is that fragment with max over a, policy evaluation is that fragment with a = π(s), and policy extraction is that fragment with argmax over a. Three algorithms, one formula, three wrappers.
This is question 2 of the August 2023 exercise exam, worth 2 of the 10 exercise marks. It is the best single predictor of what an exercise question on this Part looks like.
Setup. A 5 by 1 bonus maze, no ghosts, cells numbered 1 to 5. In cells 1 to 4 two actions are available: move Right (R) and Teleport out (T). Both act deterministically. Moving right puts Pacman in the next cell and he consumes the dot there. Teleporting ends the game. In cell 5 only teleporting is available. A dot is worth 10, a teleport is worth 20. Pacman starts in cell 1. Three policies are given:
The transitions here are deterministic. There is no expectation to take, no 0.8 and 0.1 to juggle, and no value-iteration sweep to run. What is being tested is policy evaluation (following a fixed policy and adding up its discounted rewards) and reasoning about γ. If you start building a Vk table you have misread the question and will run out of time.
Part 1, γ = 1.0. Just add the rewards along each policy's path from cell 1.
Part 2, a freely chosen γ. Write the three values as functions of γ, using the rule that the n-th action's reward carries γn−1:
Vπ0(1) = 20
Vπ1(1) = 10 + 10γ + 10γ2 + 20γ3
Vπ2(1) = 10 + 10γ + 10γ2 + 10γ3 + 20γ4
2023 sample exercise exam, question 2 part 2, verbatim (the same question is set out in full in section 17)
"Consider a freely chosen value for γ. (a) Is there a value for γ such that π0 is strictly better than π1 en π2? If yes, specify an appropriate value, if no, write No. (b) Is there a value for γ such that π1 is strictly better than π0 en π2? (c) Is there a value for γ such that π2 is strictly better than π0 en π1?"
Sub-question (b) is the one that separates the answers. Commit to it before opening the full working.
The three curves all cross at exactly one point, γ = 1/2, where all three are worth 20. The differences factor cleanly:
Vπ1 − Vπ0 = 10(2γ − 1)(γ2 + γ + 1)
Vπ2 − Vπ0 = 10(2γ − 1)(γ + 1)(γ2 + 1)
Vπ1 − Vπ2 = 10γ3(1 − 2γ)
Every second factor is strictly positive for γ in (0, 1), so all three differences are governed by the sign of (2γ − 1).
(a) Yes. Any γ < 1/2, for example γ = 0.25: the values are 20, 13.4375 and 13.359375, so π0 wins.
(b) No. π1 beats π2 only when γ < 1/2, and in exactly that range it loses to π0. At γ = 1/2 all three tie, which is not "strictly better". A scan over γ in [0,1] in steps of 0.0001 finds no point where π1 is strictly best.
(c) Yes. Any γ > 1/2, for example γ = 1 (values 20, 50, 60) or γ = 0.6 (values 20, 23.92, 24.352).
How to say it in the exam. You do not need the factorisations. It is enough to compute the three values at two or three trial values of γ, notice that the ordering flips at 0.5, and argue: a small γ makes the far-away teleport bonus worthless so grabbing 20 now wins; a large γ makes every dot worth nearly its face value so collecting all four wins; and π1 is never best because it is a strict compromise, beaten on the impatient side by π0 and on the patient side by π2.
the slides and the material for the exercise sessions uh are the main source of reference. So that's the basis of what you need to know uh for the evaluation.(Lecturer, T1). Also stated on the Part 1 slides. For this Part that means the 80 deck pages plus exercise session 6 (the one-dimensional grid illustration, micro-blackjack, the four-state policy iteration and the creature in the cave), and nothing beyond them.
| Term | Precise definition | Plain paraphrase | Exam phrasing |
|---|---|---|---|
| Markov decision process (MDP) | A tuple of states S, actions A, transition function T(s,a,s'), reward function R(s,a,s'), a start state and possibly terminal states (p.8), plus a discount γ (p.21). "Markov" means action outcomes depend only on the current state, not on the history (p.9). | A stochastic world with rewards, in which the present state tells you everything you need. | "Formulate this problem as an MDP" (exercise session 6 §2, §4) |
| Transition function T(s,a,s') | P(s' | s, a). Also called the model or the dynamics (p.8). Sums to 1 over s' for each (s,a). | The probability that doing a in s lands you in s'. | "What is the transition function T(s, a, s')?" (exercise session 6 §2.2) |
| Reward function R(s,a,s') | The reward for the transition (s,a,s'); "sometimes just R(s) or R(s')" (p.8). Paid for taking an action, not for occupying a state. | What that particular move pays you. | "What is the reward function R(s, a, s')?" (exercise session 6 §2.3); "what would be a sensible reward function R(s,a,s')? (Hint: Focus on s' in your rewards)" (exercise session 6 §4.2) |
| Living reward | The small per-step reward, possibly negative, paid on every non-terminal transition (p.6). Set against the big terminal rewards, it fixes how much impatience the agent has. | The rent you pay for still being in the world. | "Optimal policy when R(s, a, s') = −0.03 for all non-terminals s" (p.10); "R(s) = −2.0" (p.11) |
| q-state | The pair (s, a), drawn as the green node between a state and its successors (pp.14, 23). The MDP analogue of Part 8's chance node, but stored once per pair rather than once per path. | "I am in s and have committed to a, but the dice have not been rolled." | "(s, a) is a q-state" (p.14) |
| Policy π | A mapping S → A giving an action for each state (p.10). An optimal policy π* maximises expected utility if followed. An explicit policy defines a reflex agent. | A lookup table of what to do wherever you end up, not a plan. | "Describe the optimal policy in one sentence" (exercise session 6 §2.6) |
| Discount factor γ | The per-step multiplier on future rewards; the n-th action's reward carries γn−1 (pp.16-17). Normally 0 < γ < 1. Smaller γ means a shorter effective horizon (p.20). | How much less a reward is worth for arriving one step later. | "Is there a value for γ such that π0 is strictly better than π1 en π2?" (sample exercise exam Q2.2); "Which of the following γs would be most sensible: 1.5, 1, 0.9, 0 or −0.5?" (exercise session 6 §4.3) |
| Stationary preferences | Prefixing two reward sequences with the same reward does not change which you prefer. If preferences are stationary, utilities must be additive or discounted, and additive is the γ = 1 case (p.18). | Your taste in futures does not depend on when you are asked. | "Theorem: if we assume stationary preferences... there are only two ways to define utilities (proof: out of scope)" (p.18) |
| V*(s) | Expected utility starting in s and acting optimally (p.23). Satisfies V*(s) = maxa Q*(s,a) and the full Bellman equation on p.26. | What this square is worth if you play perfectly from here. | "The values in each cell are the V*(s) values calculated by the value-iteration algorithm" (exercise session 6 §1) |
| Q*(s,a) | Expected utility having taken a from s and acting optimally thereafter (p.23). Q*(s,a) = Σs' T(s,a,s')[R(s,a,s') + γV*(s')]. | What this square is worth if you make this one move first, then play perfectly. | "Important lesson: actions are easier to select from q-values than values!" (p.74) |
| Time-limited value Vk(s) | The optimal value of s if the game ends in k more steps; equivalently what a depth-k expectimax returns from s (p.30). V0(s) = 0 for all s. | The best you can do with only k moves left. | "VALUES AFTER 3 ITERATIONS" (p.34) |
| Value iteration (VI) | Repeat Vk+1(s) ← maxa Σs' T(s,a,s')[R(s,a,s') + γVk(s')] from V0 = 0 until convergence. O(S2A) per iteration; converges to unique optimal values (p.47). | Fill a whole new column of the table from the old one, taking the best action everywhere. | "Perform value iteration (until convergence) on this problem" (exercise session 6 §2.5) |
| Policy evaluation | The same update with the action fixed to π(s) and no max: Vπk+1(s) ← Σs' T(s,π(s),s')[R(s,π(s),s') + γVπk(s')], from Vπ0 = 0. O(S2) per iteration (p.71). Also solvable as a linear system. | How good is this policy, good or bad, with no second-guessing allowed. | "Run the policy-evaluation part until |Vk+1(s) − Vk(s)| ≤ 0.01 for all s" (exercise session 6 §3); "Vπ0(1) = ........" (sample exercise exam Q2.1) |
| Policy extraction | π*(s) = argmaxa Σs' T(s,a,s')[R(s,a,s') + γV*(s')] from values (p.73), or the trivial argmaxa Q*(s,a) from q-values (p.74). A one-step mini-expectimax. | Turning a table of numbers into a table of arrows. | "Which is the best action an agent can execute if he is currently in the center state of the grid world? Justify your answer." (exercise session 6 §1) |
| Policy iteration (PI) | Alternate policy evaluation of πi to convergence with one policy-improvement step πi+1(s) = argmaxa Σs' T(s,a,s')[R(s,a,s') + γVπi(s')], until the policy stops changing (pp.76-77). Still optimal; often faster. | Score the current plan properly, then improve it once, then repeat. | "Perform one iteration of the policy-iteration algorithm" (exercise session 6 §3) |
Constructed, in the sample paper's format (the 2023 theory fill-ins 2.1 and 2.2 have exactly this shape)
Fill in, one short line per blank. Quote 13: the answer boxes "give an indication of the expected length given a regular written font size", so a clause per blank is what is wanted, not a paragraph.
1. Policy evaluation; the deleted symbol is maxa (the action is pinned to π(s)); O(S2) per iteration.
2. Value iteration (policy iteration also computes them, by a different route); O(S2A) per iteration, the extra factor A being the max over actions.
3. Policy extraction; you need the transition function T and the reward function R, because it runs the one-step lookahead argmaxa Σs' T(s,a,s')[R(s,a,s') + γV*(s')]. From a Q* table instead you would need neither.
4. Q* has the first action forced to a and acts optimally only from the second step onward; therefore V*(s) = maxa Q*(s,a).
What earns the marks: the names exactly as the deck writes them, the complexity with its factor explained if there is room, and for item 3 the fact that T and R are needed, which is the whole content of quote 26. Every one of these blanks is a sentence you can already find in the table above; the drill is producing it without the table.
Chapter index: index.html · Previous: Part 8, Game Trees with Uncertainty · Next: Part 10, SAT Solving and Beyond · Drill: viz-mdp.html · Search by question: question-index.html