7 concepts27 worked examples32 exercises5 exam-level7 figures
What are you here for?
14 Reinforcement learning: returns, Markov decision processes, value iteration and Q-learning
Start with this
One question before you read anything. Getting it wrong is the point: it shows you what this section is for.
§14.1 — take the +1 now or walk for the +10?
A delivery robot stands in a corridor. One step left is a charging pad that pays $+1$ and ends the run. Going right, it pays $1$ for each of the next two moves and then collects $+10$ at the drop point, which also ends the run. are discounted by $\gamma=0.9$ per step.
Find(a) Which plan has the larger discounted total, and what is it worth?
Given
left: $+1$, then the run ends
right: $-1$, $-1$, then $+10$, then the run ends
$\gamma=0.9$: the reward $k$ steps after the first one is multiplied by $0.9^k$
Hint 1/4
Write each plan as a list of rewards and give each reward its weight.
Hint 2/4
$G_0=R_1+\gamma R_2+\gamma^2R_3$; the first reward has weight $1$.
Hint 3/4
Left: $G_0=1$. Right: $R_1=-1$, $R_2=-1$, $R_3=10$ with $\gamma=0.9$, so $G_0=-1-0.9+0.81\cdot10$.
Hint 4/4
Right is worth $6.2$ against $1$: go right.
Show solution
Both plans are fixed sequences of rewards, so each is one weighted sum.
Weighted sums
$$G_0^{\text{left}}=1$$
A single reward at weight 1.
$$G_0^{\text{right}}=-1-0.9+0.81\cdot10=6.2$$
The rewards arrive $0$, $1$ and $2$ steps after the first, so they get $\gamma^0$, $\gamma^1$ and $\gamma^2$.
Answer $$\boxed{\text{right: }6.2>1}$$
Check
Backwards: the last cell is worth $10$, the one before $-1+9=8$, the start $-1+7.2=6.2$.
Comparing only the first rewards picks the pad; the discounted total picks the drop. The section starts from exactly this gap.
A delivery robot stands in a corridor. One step to its left is a charging pad that pays $+1$ and ends the run; three steps to its right is the drop point that pays $+10$, and each of the two moves before it costs $1$. Which way should it go, and what single number decides it?
By the end you can show that the right plan is worth $6.2$ against $1$ when each later reward is discounted by $0.9$ per step, find the $0.5$ at which the two plans tie, and reach the same decision by and by .
In 60 seconds
An picks actions to maximize the discounted return $G_t=\sum_k\gamma^kR_{t+k+1}$; in a Markov decision process the best values satisfy the Bellman optimality equations, value iteration solves them when $p(s'|s,a)$ is known, and Q-learning learns $q_*$ from observed transitions when it is not.
Discounting the first reward. $R_{t+1}$ has weight $1$ and $R_{t+k+1}$ has weight $\gamma^k$; writing $\gamma R_{t+1}+\gamma^2R_{t+2}+\dots$ shrinks every term by an extra factor $\gamma$.
Putting the max in the wrong place. $v_*(s)=\max_a\sum_{s'}p(s'|s,a)[\dots]$ chooses the action before the landing state is known; $\sum_{s'}p\max_a[\dots]$ pretends the agent sees $s'$ first.
Forgetting that ε-greedy's random draw can land on the greedy action: with $\epsilon=0.1$ and $4$ actions the greedy action has probability $0.9+0.1/4=0.925$, not $0.9$.
Two course documents give different weights:
Chapter 1 slides, undergraduate line: midterm 25, final 25, four quizzes 20, two-phase project 30.
STARS syllabus page printed on 21 September 2026: midterm 30, final 30, problem sets and quizzes 20, project 20. It is the later document; confirm which split applies.
The STARS weekly list has as its thirteenth item; the lecture slides number it chapter 14.
How much time do you have?
10 minutes
The return, one value iteration sweep and one Q-learning update: the three hand computations the rest of the section is built on.
The 60-second card · The return: one number for a stream of rewards · Value iteration · Q-learning: learning q* from experience · Formula card
45 minutes
Every block once with its first worked example, then value iteration from a full solution down to a bare problem.
The 60-second card · The return: one number for a stream of rewards · Markov decision processes · Policies and their values · The optimal policy and the Bellman optimality equations · Value iteration · Q-learning: learning q* from experience · Choosing actions while learning · Scaffolding comes off · Formula card
full read
Adds the look-alike pairs, a full exam-style question and mixed practice where you choose the method yourself.
The opening pages · Recall first · The return: one number for a stream of rewards · Markov decision processes · Policies and their values · The optimal policy and the Bellman optimality equations · Value iteration · Q-learning: learning q* from experience · Choosing actions while learning · Method boxes · Look-alike pairs · Scaffolding comes off · Full exam-style question · Practice set · Check yourself
By the end of this section
Compute discounted returns of finite and infinite reward streams, directly and with the recursion $G_t=R_{t+1}+\gamma G_{t+1}$.
Model a decision problem as a Markov decision process, with states, action sets, $p(s'|s,a)$ and $r(s,a,s')$, and test whether a chosen state is Markov.
Evaluate a given policy: compute $v_\pi$ and $q_\pi$ in small examples and link them through $v_\pi(s)=\sum_a\pi(a|s)\,q_\pi(s,a)$.
Apply the Bellman optimality equations: write them for a small MDP, test claimed optimal values against them and read off $\pi^*(s)=\arg\max_aq_*(s,a)$.
Run value iteration by hand in its v and q forms, apply the stopping rule and extract the greedy policy.
Carry out Q-learning updates from observed transitions and state when the table converges to $q_*$.
Compute action probabilities under greedy, ε-greedy and , and explain why a purely greedy learner can get stuck.
Syllabus coverage
covered
Reinforcement learning — covered
Agent and environment, rewards, the discount rate and the return
policies and the
Markov decision processes
state and
optimal policies and the Bellman optimality equations
value iteration in v and q form
Q-learning
greedy, ε-greedy and Boltzmann exploration
the idea
The lecturer's chapter title and the thirteenth item of the STARS weekly list, which the slides number chapter 14. The weekly line names no chapter of the textbook, so no section numbers are cited.
covered
Markov decision process — covered
Finite states and state-dependent action sets
transition probabilities
expected rewards of transitions
the Markov property
how to repair a state that is not Markov
One of the slides' four headings. The slides' own example is replaced here by an original machine-maintenance example.
covered
Value iteration — covered
The v form and the q form
the stopping rule
reading off the greedy policy
deterministic against stochastic robots
The slides' grid robot with slippery moves appears here as the ledge example.
covered
Q learning — covered
The table
the one-sample target
the
the convergence condition
greedy
ε-greedy and Boltzmann action selection
The action-selection rules have their own block right after it.
covered
Deep Q network — covered
Why a table cannot hold the values of screen images, and the idea of replacing it by a network trained with gradient steps toward the same target.
The slides show it as a video; one worked example gives the idea. Training details are not covered.
off syllabus
Bellman equation for a fixed policy — off syllabus
The one-step equation that turns the definitions of v and q for a given policy into linear equations.
Further reading, not on the slides, which give one-step equations only for the optimal values. Used to evaluate given policies in small examples.
off syllabus
How fast value iteration converges — off syllabus
Each sweep shrinks the largest error by at least the factor γ.
Further reading: the slides say 'repeat until convergence'. It appears in the box and one figure caption, in no exercise.
off syllabus
Learning-rate condition for Q-learning — off syllabus
Why the standard convergence theorem also asks each pair's learning rate to shrink.
Further reading: the slide states the visiting condition only. Used in one worked example and one interleaved question.
off syllabus
Temperature in Boltzmann exploration — off syllabus
Dividing the entries by a temperature before the exponential.
Further reading, mentioned only: the slide's rule has no temperature and no exercise uses one.
Recall first
Expectation and total expectation
$\mathbb E[X]=\sum_xx\,p(x)$, expectation is linear, and $\mathbb E[X]=\sum_y\mathbb E[X\mid Y=y]\,P(Y=y)$.
Value functions are expectations of returns, split by the next state.
Geometric series
$\sum_{k=0}^{\infty}\gamma^k=\frac{1}{1-\gamma}$ for $0\le\gamma<1$, and $\sum_{k=0}^{n-1}\gamma^k=\frac{1-\gamma^n}{1-\gamma}$.
Returns of constant and repeating reward streams.
Law of large numbers
For i.i.d. $X_i$ with finite mean, $\bar X_n=\frac1n\sum_{i\le n}X_i\to\mathbb E[X]$. For independent $X_i$ with variance $\sigma^2$, $\operatorname{Var}(\sum_iw_iX_i)=\sigma^2\sum_iw_i^2$, so $\operatorname{Var}(\bar X_n)=\sigma^2/n$.
Q-learning with $\alpha=1/n$ keeps a running sample mean.
Waiting for a first success
If every trial succeeds independently with probability $p$, the expected number of trials up to and including the first success is $1/p$.
How long ε-greedy takes, on average, to try a given action.
Softmax
$e^{v_k}/\sum_je^{v_j}$ turns $K$ scores into $K$ probabilities that add to $1$.
Boltzmann exploration is a softmax of the table entries.
Stochastic gradient descent
$w(n+1)=w(n)-\eta\,\nabla l$, with $l$ the loss of one example and $\eta$ the learning rate.
The Q-learning update is one such step, and a deep Q network is trained with it.
Markov blanket
In a directed graph: a node's parents, its children and its children's other parents. A node is independent of its non-descendants given its parents.
One interleaved question reads the Markov property off a graph.
Try it yourself first (2 questions)
1§14.5 — a sure 8 or a risky move
A robot can take a risky move that reaches the goal ($+10$) with probability $0.8$ and falls into a pit ($-10$) with probability $0.2$, or a detour that surely earns $8$. It wants the larger expected reward.
Find(a) Which choice has the larger expected reward?
Given
risky move: $+10$ with probability $0.8$, $-10$ with probability $0.2$
detour: $8$ for sure
Hint 1/4
Replace each choice by one number, its average reward.
Hint 2/4
$\mathbb E[X]=\sum_xx\,p(x)$.
Hint 3/4
Risky: $0.8\cdot10+0.2\cdot(-10)$. Detour: $8$ with probability $1$.
Hint 4/4
$6<8$: the detour.
Show solution
An expectation weighs every outcome by its probability, the bad one included.
The ratio $0.9$ is below $1$, so the series converges.
Answer $$\boxed{G_t=10}$$
Check
Recursion check: a constant return must satisfy $G=1+0.9\,G$, which gives $G=10$.
A constant reward $r$ forever is worth $r/(1-\gamma)$.
Notation
symbol
reads as
means
watch out
$S_t,\ A_t,\ R_{t+1}$
S t, A t, R t plus one
state and action at step $t$, and the reward they produce
The reward of step $t$ carries the index $t+1$.
$\gamma$
gamma
discount rate, $0\le\gamma\le1$
Not the step size of the GLM section.
$G_t$
G t
return from step $t$: $\sum_k\gamma^kR_{t+k+1}$
Starts with $R_{t+1}$ at full weight.
$\mathcal H_t$
script H t
history: everything up to and including $S_t$ and $A_t$
A general policy may use all of it; a uses only the current state.
$\mathcal S,\ \mathcal A(s)$
script S, script A of s
the finite state set; the actions allowed in $s$
Action sets can differ from state to state.
$p(s'|s,a)$
p of s prime given s and a
probability of landing in $s'$
Adds to $1$ over $s'$, not over $s$.
$r(s,a,s'),\ r(s,a)$
r of s, a, s prime; r of s, a
expected reward of a transition; of an action
$r(s, \allowbreak a)=\sum_{s'}p(s'|s, \allowbreak a)\,r(s, \allowbreak a, \allowbreak s')$.
$\pi(a|s),\ \pi(s)$
pi of a given s; pi of s
a stationary Markov policy; the action of a deterministic one
Here $\pi$ is a policy, not $3.14$.
$v_\pi(s),\ q_\pi(s,a)$
v pi, q pi
expected return from $s$ under $\pi$; the same with the first action fixed to $a$
$q_\pi$ fixes only the first action.
$v_*,\ q_*,\ \pi^*$
v star, q star, pi star
optimal values and an optimal policy
$\pi^*$ can always be taken deterministic.
$v_k,\ q_k,\ k^*$
v k, q k, k star
value iteration tables after $k$ sweeps; the sweep at which it stops
From $v_0=0$, $v_k$ looks only $k$ steps ahead.
$Q(s,a),\ \hat Q$
Q, Q hat
Q-learning's table entry; the one-sample target
Capital $Q$ is an estimate, lowercase $q_*$ the true function.
$\alpha$
alpha
learning rate of Q-learning
The role that $\eta$ played for neural networks.
$\epsilon,\ C_t$
epsilon, C t
probability and the coin of ε-greedy; also the stopping tolerance of value iteration
The slides use the same letter for both; the context decides.
$a^\circ$
a greedy
the greedy action $\arg\max_aQ(s,a)$
Shorthand of this page, not of the slides.
Conventions used here
Reward index.
The action at step $t$ earns $R_{t+1}$, and $G_t=\sum_{k\ge0}\gamma^kR_{t+k+1}$. The first slide writes the total from the start as $G_1=R_1+\gamma R_2+\dots$; with the later general definition this sum is $G_0$.
The two slides index the same sum differently; answers here use the general definition.
Discount rate.
$\gamma<1$ unless every ends; the existence theorem and value iteration are stated for $\gamma<1$.
With no end and no discount a return can be infinite.
.
A terminal state has value $0$ and no actions, so $\max_{a'}Q(s',a')=0$ there; its reward is paid on the move into it.
The pad and the drop of the corridor work this way.
Ties between actions.
When two actions score the same, take the one listed first unless a problem says otherwise.
Hand traces of greedy choices need a fixed rule.
Synchronous sweeps.
Value iteration computes all of $v_{k+1}$ from $v_k$. Updating in place also converges, but gives different numbers at each sweep.
The slides write $v_{k+1}$ in terms of $v_k$.
Stopping rule.
$\lVert v_k-v_{k-1}\rVert$ is the largest absolute change over the states.
The slides leave the norm open; the maximum is the usual choice.
Letters reused from earlier sections.
$\gamma$ is the discount rate, not the GLM step size; $\alpha$ is the learning rate that $\eta$ was for neural networks; $\epsilon$ is both the stopping tolerance and the exploration probability, as on the slides.
The same letter means different things in different chapters.
Rounding.
Intermediate values keep full precision; results are rounded at the end, to three or four significant digits.
Rounded values drift over many sweeps or updates.
14.1The return: one number for a stream of rewards
Adds a reward stream into one number, weighting the reward $k$ steps after the first by $\gamma^k$.
Every earlier section learned from examples that came with the right answer attached; here the only feedback is a reward, and the reward for a good move may arrive several steps later.
Solvable with what we have
Predict a price from features with least squares.
Classify an email from labelled examples with logistic regression.
Split unlabelled sensor readings into clusters with EM.
Estimate an average reward from repeated trials with a sample mean.
Not solvable yet
Decide whether a robot should take $+1$ now or walk three steps for $+10$.
Say which of forty moves in a game earned the final win.
Plan repairs whose cost comes today and whose benefit comes over the next weeks.
Learn from data that the learner's own actions select.
The obvious rule: in every cell, take the move with the larger immediate reward. At the robot's start, left pays $+1$ and right pays $-1$, so the rule goes left and collects $1$ in total.
Why it fails
The rule looks one step ahead. Going right costs $1$ twice and then pays $10$; shrinking each later reward by a factor $0.9$ per step, the total is $-1-0.9+8.1=6.2$, six times what the rule collects.
DefinitionDefinition 14.1: Return and discount rate
Conditions
$0\le\gamma\le1$ as on the slides; with $\gamma=1$ the sum stays finite only if every episode ends
rewards are bounded, $\lvert R_t\rvert\le R_{\max}$, so for $\gamma<1$ the return obeys $\lvert G_t\rvert\le R_{\max}/(1-\gamma)$
The return at time $t$ is the next reward at full value, plus the one after it scaled by $\gamma$, plus the one after that scaled by $\gamma^2$, and so on. Everything after the first reward is itself a return, one step later, scaled by $\gamma$.
Where the recursion comes from
Split off the first term.$G_t=R_{t+1}+\sum_{k\ge1}\gamma^kR_{t+k+1}$.
Shift the index. With $j=k-1$ the tail is $\gamma\sum_{j\ge0}\gamma^jR_{(t+1)+j+1}=\gamma\,G_{t+1}$.
Bounded. If $\lvert R\rvert\le R_{\max}$ and $\gamma<1$, then $\lvert G_t\rvert\le R_{\max}\sum_k\gamma^k=R_{\max}/(1-\gamma)$.
The right plan at $\gamma=0.9$: each $\textcolor{#d1690a}{\text{reward as it arrives}}$ and the $\textcolor{#1f6feb}{\text{amount it adds to }G_0}$ after weighting $R_{k+1}$ by $0.9^k$. The $+10$ two steps after the first reward still counts $8.1$, so the plan is worth $6.2$ against $1$ for going left.
Looks like this, but is not
The return $G_t$ looks as if it starts with $R_t$, the reward carrying the same index.
On the slides the action taken at time $t$ earns $R_{t+1}$, so $G_t$ starts there. $R_t$ was earned by the previous action and belongs to $G_{t-1}$.
$\gamma$
$\sum_{k\ge0}\gamma^k=1/(1-\gamma)$
$\gamma^{10}$, the weight ten steps after the first reward
$0.5$
$2$
$0.001$
$0.9$
$10$
$0.349$
$0.99$
$100$
$0.904$
A small $\gamma$ makes the agent short-sighted: at $0.5$ a reward ten steps later keeps a thousandth of its value, at $0.99$ still nine tenths.
Left for +1 now or right for +10 later, at γ = 0.9 and at the break-even γ
In the opening corridor, going left pays $+1$ and ends the run. Going right pays $-1$, then $-1$, then $+10$ at the drop point, which also ends the run. Compare the two plans at $\gamma=0.9$, then find the $\gamma$ at which they tie.
Find$G_0$ of each plan at $\gamma=0.9$, and the $\gamma$ at which the two are equal.
Given
left: $R_1=+1$, then the run ends
right: $R_1=-1$, $R_2=-1$, $R_3=+10$, then the run ends
$\gamma=0.9$ first, then $\gamma$ unknown
Solution
Both plans are fixed reward sequences, so the definition of the return applies directly; nothing is random yet.
Return of each plan at γ = 0.9
$$G_0^{\text{left}}=1$$
One reward at weight $\gamma^0=1$; after the pad every reward is $0$.
At $\gamma=0.5$: $-1-0.5+0.25\cdot10=1$, exactly the left plan. At $\gamma=0.3$: $-1-0.3+0.9=-0.4<1$, so below the break-even the pad wins.
This settles the opening: at $\gamma=0.9$ the robot goes right, and below $\gamma=0.5$ it should take the $+1$. The discount rate is part of the problem, not a detail.
+2 forever against +5 for three steps, at γ = 0.9
Plan A pays $+2$ at every step forever. Plan B pays $+5$ at each of the next three steps and nothing afterwards. Which has the larger return at $\gamma=0.9$?
Find$G_t$ of both plans.
Given
A: $R_{t+k+1}=2$ for every $k\ge0$
B: $R_{t+1}=R_{t+2}=R_{t+3}=5$, later rewards $0$
$\gamma=0.9$
Solution
Both are geometric sums, so $\sum_{k\ge0}\gamma^k=\frac1{1-\gamma}$ and $\sum_{k=0}^{n-1}\gamma^k=\frac{1-\gamma^n}{1-\gamma}$ replace adding term by term.
An infinite geometric series with ratio $0.9<1$ converges.
Plan B
$$G_t^{B}=5\,(1+0.9+0.81)=5\cdot2.71=13.55$$
Three terms are short enough to add directly.
Answer $$\boxed{G_t^{A}=20>G_t^{B}=13.55}$$
Check
Closed form for B: $5\cdot\frac{1-0.9^3}{0.1}=5\cdot2.71=13.55$. A's partial sums are $20(1-0.9^n)$: $13.03$ after $10$ steps, $13.72$ after $11$, so A overtakes B only at step $11$.
A constant reward $r$ forever is worth $r/(1-\gamma)$, which at $\gamma=0.9$ is ten times $r$.
Returns of every step of one episode, computed backwards
An episode produces the rewards $R_1=0$, $R_2=0$, $R_3=-1$, $R_4=5$ and then ends. With $\gamma=0.8$, find $G_0$, $G_1$, $G_2$ and $G_3$.
Find$G_3$, $G_2$, $G_1$ and $G_0$.
Given
$R_1=0,\ \allowbreak R_2=0,\ \allowbreak R_3=-1,\ \allowbreak R_4=5$; the episode ends after $R_4$
$\gamma=0.8$
Solution
Computing each return from scratch repeats work; the recursion $G_t=R_{t+1}+\gamma G_{t+1}$ gives all four with one multiplication each, starting from the end.
Start at the end
$$G_3=R_4=5$$
After the episode ends every reward is $0$, so $G_4=0$.
Step backwards
$$G_2=R_3+0.8\,G_3=-1+4=3$$
The recursion at $t=2$.
$$G_1=R_2+0.8\,G_2=0+2.4=2.4$$
Same step; a zero reward only passes the discounted tail on.
Once you know the present state and action, the rest of the history adds nothing about what comes next. So two tables describe the environment: $p(s'|s,a)$, where each action can lead and how likely each landing state is, and $r(s,a,s')$, the average reward that transition pays. Averaging over the landing state gives the expected reward $r(s,a)$ of the action.
The machine as a Markov decision process. Circles are states, $\textcolor{#8250df}{\text{dots are actions}}$: $\mathcal A(\text{good})=\{\text{run}\}$ and $\mathcal A(\text{worn})=\{\text{run},\text{repair}\}$. Each arrow out of a dot carries $p(s'|s,a)$ and the $\textcolor{#d1690a}{\text{reward}}$ of that transition; the arrows out of one dot add up to probability $1$.
Looks like this, but is not
A cart on a track whose state is its position alone looks Markov: the next position seems to depend only on the position and the push.
If the cart carries momentum, two visits to the same position move differently depending on how the cart got there. Position plus velocity is Markov; position alone is not. The property belongs to the state you choose.
The machine-maintenance problem written as an MDP
A machine is good or worn at the start of each day. Write the problem as an MDP.
A good machine wears out during the day with probability $0.5$. Running it yields $7$ units if it ends the day good and $5$ if it wore out.
A worn machine can run for $2$ units and stays worn.
Or it can be repaired for a cost of $1$ unit and is good the next day.
Find$\mathcal S$, $\mathcal A(s)$, the transition probabilities, $r(s,a,s')$ and $r(s,a)$.
Given
a good machine wears out during a day with probability $0.5$
rewards: $7$ or $5$ for running a good machine, $2$ for running a worn one, $-1$ for a repair
Solution
Name the states first, since everything else is indexed by them; then list each state's actions, then where each action leads.
States and actions
$$\mathcal S=\{\text{good},\text{worn}\}$$
The machine's condition is all that matters for tomorrow.
Each of the three rows adds to $1$: $0.5+0.5$, $1$ and $1$. The expected reward $6$ lies between $5$ and $7$, as an average must.
Write an MDP as a list of rows, $(s,a)\to$ landing states with $p$ and $r$; every later computation reads from that list.
Fixing a state that is not Markov: an elevator
An elevator serves floors $1$, $2$ and $3$. It moves one floor per step and keeps its direction until it reaches floor $1$ or $3$, where it turns around. A student takes the floor number as the state. Check the Markov property at floor $2$ and repair the state.
Find$\Pr(S_{t+1}=3\mid\cdot)$ for two histories that end at floor $2$, and a state that is Markov.
Given
floors $1,2,3$; one floor per step
the direction reverses only at floors $1$ and $3$
Solution
One counterexample, two histories with the same present but different futures, is enough to show that the property fails.
Two histories ending at floor 2
$$\Pr(S_{t+1}=3\mid S_{t-1}=1,\ S_t=2)=1$$
Coming from floor $1$ the elevator is going up, so it continues to $3$.
$$\Pr(S_{t+1}=3\mid S_{t-1}=3,\ S_t=2)=0$$
Coming from floor $3$ it is going down, so it continues to $1$.
With the direction in the state the present fixes the next state; at an end floor the direction flips.
Answer $$\boxed{\text{floor alone: not Markov;}\qquad(\text{floor},\text{direction}):\ \text{Markov}}$$
Check
The four states $(1,\uparrow)$, $(2,\uparrow)$, $(3,\downarrow)$, $(2,\downarrow)$ form one cycle with a single successor each, so every is $0$ or $1$ and no history can change it.
When something from the past changes the future, put it into the state.
Checkpoint
§14.2 — two days of the machine
A machine is good this morning. Running a good machine wears it out during the day with probability $0.5$; a worn machine that is run stays worn. The machine is run today and tomorrow.
Find(a) What is the probability that it is worn the morning after tomorrow?
Split the two days by the machine's state in between.
Hint 2/4
Markov property and total probability: $\Pr(S_{t+2}=w)=\sum_{s}\Pr(S_{t+1}=s)\,p(w|s,\text{run})$.
Hint 3/4
Here $\Pr(S_{t+1}=\text{worn})=0.5$ with $p(\text{worn}|\text{worn},\text{run})=1$, and $\Pr(S_{t+1}=\text{good})=0.5$ with $p(\text{worn}|\text{good},\text{run})=0.5$.
Hint 4/4
$0.5\cdot1+0.5\cdot0.5=0.75$.
Show solution
The Markov property lets the second day depend only on the state after the first day, so condition on that state.
Total probability over the two possible middle states.
$$=0.5\cdot1+0.5\cdot0.5=0.75$$
A worn machine stays worn; a good one gets a second chance to wear out.
Answer $$\boxed{0.75}$$
Check
The complement: it stays good only if it survives both days, $0.5\cdot0.5=0.25$, and $1-0.25=0.75$.
For several steps, condition on the states in between; the Markov property makes each factor a one-step probability.
⚠ Adding the transition table over the wrong index
Both indices are states, and the bar in $p(s'|s,a)$ is easy to read backwards.
wrong$$\sum_{s}p(s'|s,a)=1$$
right$$\sum_{s'}p(s'|s,a)=1\ \text{for every pair }(s,a)$$
⚠ Using the likeliest landing state's reward as the action's reward
The likeliest outcome feels like what the action pays.
wrong$$r(s,a)=r(s,a,s'_{\text{likeliest}})$$
right$$r(s,a)=\sum_{s'}p(s'|s,a)\,r(s,a,s')$$
14.3Policies and their values
Scores a policy by its expected return: $v_\pi(s)$ from a state, $q_\pi(s,a)$ from a state with the first action fixed.
A policy says what to do in each state; its value says how much return that earns on average, which lets us compare two policies state by state.
DefinitionDefinition 14.3: Stationary Markov policy and value functions
Conditions
general policy: $A_t\sim\pi(\cdot\mid\mathcal H_{t-1},R_t,S_t)$, using everything that happened so far
stationary Markov policy: $A_t\sim\pi(\cdot\mid S_t)$, the same rule at every step; deterministic if it puts probability $1$ on one action, written $\pi(s)$
$\mathbb E_\pi$: expectation when actions follow $\pi$ and transitions follow $p$
$v_\pi(s)$ is the average return from $s$ when every action is chosen by $\pi$. $q_\pi(s,a)$ is the same average when the first action is forced to be $a$ and $\pi$ takes over from the next step. Averaging $q_\pi(s,\cdot)$ with $\pi$'s own action probabilities gives back $v_\pi(s)$.
The one-step equation for a fixed policy (further reading)
Not on the slides. It turns the definitions into equations you can solve. Start from $G_t=R_{t+1}+\gamma G_{t+1}$.
Condition on the landing state. By the Markov property the expected $G_{t+1}$ given $S_{t+1}=s'$ is $v_\pi(s')$, whatever happened before.
Result.$q_\pi(s,a)=\sum_{s'}p(s'|s,a)\,[r(s,a,s')+\gamma v_\pi(s')]$. With the third line of the box this is one linear equation per state.
Values of the policy that always moves right, at $\gamma=0.9$. Each cell's $\textcolor{#1f6feb}{v_\pi}$ is the $\textcolor{#d1690a}{\text{reward}}$ of its $\textcolor{#8250df}{\text{move}}$ plus $0.9$ times the value of the cell it lands in: $\textcolor{#1f6feb}{8}=\textcolor{#d1690a}{-1}+0.9\cdot\textcolor{#1f6feb}{10}$.
Looks like this, but is not
$v_\pi(s)$ looks like the return you will collect if you start in $s$ and follow $\pi$.
It is an average over random transitions and random action choices. For the machine, one day-by-day run from good can earn far more or far less than $v_\pi(\text{good})$; only the mean over many runs equals it.
Values of 'always right' and 'always left' in the corridor
In the corridor, find $v_\pi$ in S0, S1 and S2 for the policy that always moves right and for the one that always moves left.
Find$v_{\text{right}}$ and $v_{\text{left}}$ in S0, S1 and S2.
Given
cells: pad, S0, S1, S2, drop; pad and drop are terminal
entering the pad: $+1$; entering the drop: $+10$; any other move: $-1$
$\gamma=0.9$
Solution
Moves are deterministic, so each policy produces one fixed reward sequence from each cell; start next to the terminal ends, where the sequences are shortest.
Always right
$$v_{\text{right}}(\text{S2})=10$$
One move into the drop.
$$v_{\text{right}}(\text{S1})=-1+0.9\cdot10=8$$
One move to S2, then S2's return scaled by the discount.
$$v_{\text{right}}(\text{S0})=-1+0.9\cdot8=6.2$$
The same step once more; it matches the $6.2$ of the opening.
Directly for left from S2: rewards $-1,-1,+1$ give $-1-0.9+0.81=-1.09$. Right is better in all three cells.
In a deterministic world a policy's value is one reward sequence summed with discounts; work backwards from the ends.
Value of 'repair when worn' for the machine, from two linear equations
For the machine with $\gamma=0.8$, the policy $\pi_R$ runs a good machine and repairs a worn one. Find $v_{\pi_R}(\text{good})$ and $v_{\pi_R}(\text{worn})$.
Find$v(\text{good})$ and $v(\text{worn})$ under $\pi_R$.
Given
good, run: to good ($0.5$, reward $7$) or to worn ($0.5$, reward $5$)
worn, repair: to good ($1$, reward $-1$)
$\gamma=0.8$
Solution
The reward sequence is now random, so there is no single sequence to sum. Two linear equations are more work than adding a few numbers, and here they are the only way: the one-step equation (further reading, in the box) gives one per state.
Plug back: $6+0.8\,(0.5\cdot20+0.5\cdot15)=6+14=20$ and $-1+0.8\cdot20=15$. Both equations hold.
For a fixed policy the value equations are linear: one unknown per state and no max.
From action values to a state value under a random policy
In a state $s$ with three actions, $q_\pi(s,\cdot)=(4,\ 1,\ -2)$ and the policy picks the actions with probabilities $(0.8,\ 0.1,\ 0.1)$. Find $v_\pi(s)$.
The third line of the box averages the action values with the policy's own probabilities; nothing else is needed.
Average over the policy
$$v_\pi(s)=0.8\cdot4+0.1\cdot1+0.1\cdot(-2)$$
Weight each action value by the chance that the policy picks that action.
$$=3.2+0.1-0.2=3.1$$
The two rarely chosen actions nearly cancel: $+0.1$ and $-0.2$.
Answer $$\boxed{v_\pi(s)=3.1}$$
Check
The value must lie between the smallest and largest action values, $-2$ and $4$, and close to $4$ because $a_1$ carries most of the weight; $3.1$ does.
A state's value under a policy is an average of its action values, not their maximum.
Checkpoint
§14.3 — the corridor at a smaller discount
In the corridor, the policy moves right in every cell. From S0 it pays $-1$, $-1$ and then $+10$ as it enters the drop, which ends the run. Now $\gamma=0.5$.
Find(a) What is $v_{\text{right}}(\text{S0})$?
Given
rewards from S0 under always right: $-1,\ -1,\ +10$, then the run ends
$\gamma=0.5$
Hint 1/4
Write the reward sequence from S0 and give each reward its weight.
Hint 2/4
$v(\text{S0})=R_1+\gamma R_2+\gamma^2R_3$ for this deterministic sequence.
Hint 3/4
Here $R_1=-1$, $R_2=-1$, $R_3=10$ and $\gamma=0.5$: $-1-0.5+0.25\cdot10$.
Hint 4/4
$v_{\text{right}}(\text{S0})=1$.
Show solution
A in a deterministic corridor gives one reward sequence, so the value is that sequence's return.
Weights 1, 0.5, 0.25
$$v=-1+0.5\cdot(-1)+0.25\cdot10=1$$
The third reward is two steps after the first, so it gets $0.5^2$.
The best value of a state is the value of its best first action. That action's value is its expected reward plus $\gamma$ times the average best value of where it lands. Substituting one line into the other gives the two equations on the slides, and the optimal policy takes the action with the largest $q_*$.
Why the equations hold (sketch)
Any first action, then optimal play. Taking $a$ in $s$ and acting optimally afterwards earns, by $G_t=R_{t+1}+\gamma G_{t+1}$ and the Markov property, $r(s,a)+\gamma\sum_{s'}p(s'|s,a)\,v_*(s')$ on average.
No policy beats the best first action. A policy that randomizes in $s$ earns a weighted average of these numbers, which is at most their maximum.
So $v_*(s)$ is that maximum, and picking an action that attains it in every state is a deterministic stationary policy.
The optimality equation at the worn machine, $\gamma=0.8$. Each action's $\textcolor{#1f6feb}{q_*}$ is its $\textcolor{#d1690a}{\text{reward}}$ plus $0.8$ times the optimal value where it lands; $\textcolor{#1f6feb}{v_*(\text{worn})}$ takes the larger one, so $\textcolor{#8250df}{\pi^*(\text{worn})=\text{repair}}$.
Looks like this, but is not
Picking the action with the largest immediate reward looks like the optimal policy in disguise, since $v_*$ also takes a max over actions.
The max in $v_*$ is over reward plus $\gamma$ times the value of the landing state. In the corridor left pays more now, $+1$ against $-1$, but $q_*(\text{S0},\text{right})=6.2>q_*(\text{S0},\text{left})=1$.
Checking claimed optimal values in the corridor
A classmate claims that in the corridor with $\gamma=0.9$ the optimal values are $6.2$ in S0, $8$ in S1 and $10$ in S2. Check the optimality equation in each cell and give $\pi^*$.
FindWhether each equation holds, and $\pi^*$.
Given
cells in a row: pad, S0, S1, S2, drop; S0, S1 and S2 each have a left and a right move
moves cost $1$; entering the pad pays $+1$ and entering the drop $+10$; both end the run and have value $0$
$\gamma=0.9$
claimed $v_*=(6.2,\ 8,\ 10)$ in S0, S1, S2
Solution
Values that satisfy the optimality equations in every state are the optimal values (for $\gamma<1$ the solution is unique), so three checks settle the claim without searching over policies.
Answer $$\boxed{v_*=(6.2,\ 8,\ 10);\qquad\pi^*=\text{right in S0, S1 and S2}}$$
Check
Independently, these are the values of always right found by summing its reward sequences, so that policy attains the claimed optimum.
To test claimed optimal values, score every action with them and check that the best score reproduces the claim.
Optimal action values of the machine and the decision when worn
For the machine with $\gamma=0.8$ it is known that $v_*(\text{good})=20$ and $v_*(\text{worn})=15$. Find $q_*$ for all three state-action pairs and $\pi^*$.
Find$q_*(\text{good},\text{run})$, $q_*(\text{worn},\text{run})$, $q_*(\text{worn},\text{repair})$ and $\pi^*$.
Given
good, run: to good ($0.5$, reward $7$) or worn ($0.5$, reward $5$)
worn, run: to worn ($1$, reward $2$); worn, repair: to good ($1$, reward $-1$)
$\max_aq_*(s,a)$ gives back $20$ and $15$, the given optimal values, as the first line of the box requires. These are also the values of $\pi_R$ found by solving its linear equations.
Knowing $v_*$ turns the policy question into one look-ahead per action; knowing $q_*$ makes it a plain argmax.
A randomized first move cannot beat the best action
At the worn machine, a policy repairs with probability $\theta$ and runs otherwise, then acts optimally. Using $q_*(\text{worn},\text{repair})=15$ and $q_*(\text{worn},\text{run})=14$, show that its value at worn is at most $15$.
FindThe value of the mixed first move as a function of $\theta$.
14.5Value iteration: solving the optimality equations by repeated look-ahead
Computes $v_*$ when $p$ and $r$ are known: sweep $v_{k+1}(s)=\max_a[r(s,a)+\gamma\sum_{s'}p(s'|s,a)v_k(s')]$ until the values settle, then act greedily.
The optimality equations hide a max inside, so they are not a linear system we can solve in one go; value iteration uses them as an update rule instead.
MethodAlgorithm 14.1: Value iteration, in v form and in q form
Conditions
$p(s'|s,a)$ and $r(s,a,s')$ are known and $\gamma<1$
synchronous sweep: every $v_{k+1}(s)$ is computed from $v_k$ only
stop at the first $k^*$ with $\max_s\lvert v_{k^*}(s)-v_{k^*-1}(s)\rvert\le\epsilon$; terminal states keep value $0$
the slides write the look-ahead as $\sum_{s'}p(s'|s,a)[r(s,a,s')+\gamma v_k(s')]$, which is the same number as below
Start from $v_0=0$. In each sweep, give every state the value of its best action, scoring an action by its expected reward plus $\gamma$ times the average old value of where it lands. Stop when no value moves by more than $\epsilon$, and act greedily with the last values. The q form keeps one number per pair and does the same.
Why it converges (further reading)
A sweep shrinks distances. For any two value tables $v$ and $w$, one sweep applied to each gives tables that differ by at most $\gamma\max_s\lvert v(s)-w(s)\rvert$, because a max of averages moves no more than the values it averages.
Apply it to $v_k$ and $v_*$. A sweep leaves $v_*$ unchanged, so $\max_s\lvert v_{k+1}(s)-v_*(s)\rvert\le\gamma\max_s\lvert v_k(s)-v_*(s)\rvert$.
Geometric decay. After $k$ sweeps the error is at most $\gamma^k$ times the first one; with $\gamma=0.8$ each sweep removes at least a fifth of what is left.
Value iteration on the machine, $\gamma=0.8$, from $v_0=0$. Both $\textcolor{#1f6feb}{v_k}$ curves climb toward $v_*=(20,\ 15)$, and the gap to each dashed line shrinks by a factor of about $0.8$ per sweep: after $10$ sweeps it is still $1.8$.
Looks like this, but is not
After $k$ sweeps, $v_k$ looks like the value of the greedy policy of that sweep.
From $v_0=0$, $v_k(s)$ is the best expected discounted reward over the next $k$ steps only. For the machine $v_1(\text{worn})=2$, while its greedy policy, run forever, is worth $2/(1-0.8)=10$ at worn.
Two sweeps of value iteration on the machine
Run value iteration on the machine with $\gamma=0.8$ from $v_0=0$ for two sweeps. After each sweep, give the greedy action in the worn state.
Find$v_1$, $v_2$ and the greedy action in worn after each sweep.
Given
good, run: to good ($0.5$, reward $7$) or worn ($0.5$, reward $5$), so $r(\text{good},\text{run})=6$
worn, run: to worn ($1$, reward $2$); worn, repair: to good ($1$, reward $-1$)
With the slides' form, rewards inside the sum: $v_2(\text{g})=0.5\,(7+0.8\cdot6)+0.5\,(5+0.8\cdot2)=5.9+3.3=9.2$, the same.
Two sweeps, three look-aheads each.
Keep the old table fixed during a sweep and fill a new one; the greedy action can change from one sweep to the next.
The same two sweeps in q form
Run two sweeps of value iteration in q form on the machine with $\gamma=0.8$, keeping the table $q_k(s,a)$ and starting from $q_0=0$.
Find$q_1$ and $q_2$ for the three pairs, and $\max_aq_2(s,a)$.
Given
the machine: $r(\text{g},\text{run})=6$ with landing states good and worn ($0.5$ each); $r(\text{w},\text{run})=2$, stays worn; $r(\text{w},\text{repair})=-1$, lands in good
$\gamma=0.8$, $q_0=0$ for all three pairs
Solution
The q form replaces $v_k(s')$ by $\max_{a'}q_k(s',a')$: the max is taken at the landing state, before averaging.
The q form must reproduce the v form sweep by sweep, and it does: the previous example gave $v_2=(9.2,\ 3.8)$.
The q form stores one number per pair instead of per state, but then the policy is a plain argmax with no look-ahead.
A slippery robot takes the long way
From its start cell a robot can walk along a ledge straight into the goal, or take a detour: one step to a safe cell for $-1$, then into the goal. The goal pays $+10$ and ends the run. On the ledge the robot slips with probability $q$ into a pit that pays $-10$ and ends the run.
FindThe optimal first move for $q=0$ and $q=0.2$, and the $q$ at which the two moves tie.
Given
ledge: goal with probability $1-q$ ($+10$), pit with probability $q$ ($-10$); both end the run
detour: safe cell ($-1$), then goal ($+10$)
$\gamma=0.9$
Solution
Both landing cells of the ledge are terminal and the safe cell has one move, so one optimality look-ahead per action at the start settles everything.
An average over two terminal landing cells, so no $\gamma$ term.
$$q=0:\ 10>8;\qquad q=0.2:\ 6<8$$
The deterministic robot takes the ledge; the slippery one takes the detour.
Tie
$$10-20q=8\iff q=0.1$$
Above one slip in ten, the detour wins.
Answer $$\boxed{q=0:\ \text{ledge};\qquad q=0.2:\ \text{detour};\qquad\text{tie at }q=0.1}$$
Check
Picture $100$ slippery robots on the ledge: $80$ collect $+10$ and $20$ lose $10$, a total of $600$, or $6$ each. $100$ robots on the detour collect $8$ each, $800$ in all.
Noise in the moves pushes the optimal path away from hazards; this is the difference between the deterministic and the stochastic grid robot on the slides.
Checkpoint
§14.5 — what the first sweep computes
Value iteration starts from $v_0(s)=0$ in every state of an MDP with expected rewards $r(s,a)$.
Find(a) True or false: after one sweep, $v_1(s)=\max_ar(s,a)$, the best expected immediate reward.
Step through value iteration on the corridor, $\gamma=0.9$. Each frame shows $\textcolor{#1f6feb}{v_k}$ in every cell and the $\textcolor{#8250df}{\text{greedy move}}$: the $+10$ travels one cell per sweep, and S0 switches from the pad to the drop at sweep $3$.
At the edges
sweep 1 S0 goes left
With one step of look-ahead the pad's $+1$ beats the $-1$ of moving right, exactly the one-step rule of the opening.
sweep 3 converged
Sweep $4$ changes no value, so the stopping rule fires for any $\epsilon>0$.
14.6Q-learning: learning q* from experience
Learns $q_*$ without $p$ or $r$: after each observed step, move $Q(S_t,A_t)$ a fraction $\alpha$ toward $R_{t+1}+\gamma\max_{a'}Q(S_{t+1},a')$.
Value iteration needs $p(s'|s,a)$ and $r(s,a,s')$; a robot in a new building or a recommender facing new users knows neither, but it can act and watch what happens.
MethodAlgorithm 14.2: Q-learning
Conditions
a table $Q(s,a)$ for every pair, for example all $0$ at the start
learning rate $0<\alpha\le1$; the target reads the table before the update, and $\max_{a'}Q(s',a')=0$ at a terminal $s'$
as on the slides: if every pair is tried infinitely often, $Q(s,a)\to q_*(s,a)$ with probability $1$
further reading: the standard theorem also needs each pair's learning rate to shrink, for example $\alpha=1/n$ at its $n$th update
After each step, form a one-sample guess of $q_*(S_t,A_t)$: the reward just received plus $\gamma$ times the best current entry at the state just reached. Keep a fraction $1-\alpha$ of the old entry and add $\alpha$ of the guess. Only the entry of the pair just tried changes.
One update with $\alpha=0.25$: the entry moves from $\textcolor{#1f6feb}{2}$ a quarter of the way toward the target $\textcolor{#d1690a}{\hat Q=6}$ and lands at $\textcolor{#1f6feb}{3}$. With $\alpha=1$ it would jump to the target and forget the past; with $\alpha$ near $0$ it would barely move.
Looks like this, but is not
Q-learning seems to need the action the agent takes next, $A_{t+1}$, to form its target.
The target uses $\max_{a'}Q(S_{t+1},a')$, the best entry at the next state, whatever the agent does there. Exploratory moves therefore do not drag the table toward the value of exploring; it still aims at $q_*$.
Three episodes of Q-learning in the corridor
In the corridor, start with $Q=0$ for every pair, $\alpha=0.5$ and $\gamma=0.9$. Three episodes each move right from S0 to the drop. Update the table after every move.
Find$Q(\text{S0},\text{R})$, $Q(\text{S1},\text{R})$ and $Q(\text{S2},\text{R})$ after each episode.
Given
cells in a row: pad, S0, S1, S2, drop; the pad and the drop end the run
moves: S0 to S1 and S1 to S2 pay $-1$; S2 to the drop pays $+10$ and ends the run
every cell also has a left action: S0 to the pad pays $+1$ and ends the run, S1 to S0 and S2 to S1 pay $-1$; left is never taken here, so its entries stay $0$ but still count in the max
$Q(s,a)=0$ for all pairs at the start
$\alpha=0.5$, $\gamma=0.9$
Solution
Apply the update in the order the moves happen, reading the table as it stands at that moment; the untried left entries stay 0 and still take part in the max.
The drop's entry follows $Q\leftarrow\frac12(Q+10)$, so its gap to $10$ halves each episode: $10,\ 5,\ 2.5,\ 1.25$, and $10-1.25=8.75$.
Nine updates; only the three right entries ever changed.
The final reward travels backwards one cell per episode; early cells stay wrong until the cells after them have learned.
Q-learning on the machine from four observed days
A plant does not know the machine's probabilities. It starts with $Q=0$, uses $\alpha=0.5$ and $\gamma=0.8$, and records four days as $(S_t,A_t,R_{t+1},S_{t+1})$: (good, run, $7$, good), (good, run, $5$, worn), (worn, repair, $-1$, good), (good, run, $7$, good).
Find$Q(\text{good},\text{run})$ and $Q(\text{worn},\text{repair})$ after the four days.
Given
the four transitions in the order observed
$Q=0$ for all three pairs at the start
$\alpha=0.5$, $\gamma=0.8$
Solution
Each day is one update of that day's pair; no probability is needed because every landing state is observed.
Each new entry must lie between the old entry and its target: $3.5\in[0,7]$, $4.25\in[3.5,5]$, $1.2\in[0,2.4]$, $7.325\in[4.25,10.4]$. All four do.
The order of the days matters: swap days 3 and 4 and $Q(\text{w},\text{rep})$ comes out $2.43$ instead of $1.2$.
A shrinking learning rate turns Q-learning into a running average
One pair always ends the episode, so its target is just the reward. Its first four rewards are $4$, $0$, $8$, $4$. Track $Q$ from $0$ with $\alpha=1/n$ at the $n$th update, and with a constant $\alpha=0.5$.
Find$Q$ after each update under both learning rates, and what each one estimates.
Given
targets $\hat Q=4,\ 0,\ 8,\ 4$ (the next state is terminal)
$Q=0$ at the start
Solution
With a terminal next state there is no max term, so the update is a pure averaging rule and the two learning rates can be compared cleanly.
Unrolled, the constant-rate estimate is $0.5\cdot4+0.25\cdot8+0.125\cdot0+0.0625\cdot4=4.25$.
A fixed learning rate tracks the recent past instead of settling, which is why the standard convergence theorem asks it to shrink.
Why the Atari player cannot keep a table
A game screen is shrunk to $10\times10$ pixels, each black or white, and the player has $4$ actions. How many entries would a Q table need, and what does a deep Q network do instead?
FindThe number of table entries, and the idea that replaces the table.
Given
$100$ pixels with $2$ values each
$4$ actions
Solution
Count the states first; the size alone shows why the Atari demo on the slides uses a network.
Step through Q-learning on the corridor with $\alpha=0.5$, $\gamma=0.9$, every episode moving right from S0 to the drop. The $\textcolor{#1f6feb}{Q(s,\text{right})}$ entries start at $0$; the $+10$ reaches one more cell per episode and the column settles on $q_*=(6.2,\ 8,\ 10)$.
At the edges
episode 3 S0 still negative
$Q(\text{S0},\text{right})=-0.2$ is below the untried $Q(\text{S0},\text{left})=0$, so a purely greedy agent would now walk to the pad.
episode 40 settled
The corridor's moves and rewards are deterministic, so even a constant $\alpha$ lets the entries settle; by episode $40$ they agree with $q_*$ to three decimals.
14.7Choosing actions while learning: greedy, ε-greedy and Boltzmann
Turns the current entries $Q(S_t,\cdot)$ into an action: exploit the best entry, or explore so that every pair keeps being tried.
Q-learning converges only if every pair keeps being tried, yet the agent also wants reward now; the rule that picks the next action has to balance the two.
DefinitionDefinition 14.4: Greedy, ε-greedy and Boltzmann action selection
Conditions
$\lvert\mathcal A\rvert$ actions in the current state; $a^\circ=\arg\max_aQ(S_t,a)$ is the greedy action
ε-greedy: a coin $C_t$ shows heads with probability $\epsilon$; heads draws uniformly from all actions, $a^\circ$ included
Boltzmann as on the slides, with no temperature; dividing $Q$ by a temperature $\tau$ is a common extension (further reading)
Greedy always takes the current best entry and never checks the others. ε-greedy does the same most of the time, but with probability $\epsilon$ it draws an action at random, so every action gets at least $\epsilon/\lvert\mathcal A\rvert$. Boltzmann gives each action a share that grows exponentially with its entry: close competitors are tried often, clearly worse actions rarely.
Three rules for the same entries $Q(s,\cdot)=(2,\ 1,\ 0)$. Greedy puts everything on the $\textcolor{#8250df}{\text{greedy action}}$; ε-greedy with $\epsilon=0.3$ leaves $0.1$ on each other action; Boltzmann leaves more on the close second, $0.245$, than on the clearly worse third, $0.090$.
Looks like this, but is not
With $\epsilon=0.1$ and $4$ actions, ε-greedy looks as if it takes the greedy action with probability $0.9$.
The random draw can land on the greedy action too, so its probability is $0.9+0.1/4=0.925$, and each of the other three gets $0.025$.
Action probabilities under ε-greedy and Boltzmann for the same entries
In state $s$ the table holds $Q(s,a_1)=2$, $Q(s,a_2)=1$ and $Q(s,a_3)=0$. Find the action probabilities under ε-greedy with $\epsilon=0.3$ and under Boltzmann exploration.
Find$\Pr(A_t=a_i\mid S_t=s)$ for $i=1,2,3$ under both rules.
Given
$Q(s,\cdot)=(2,\ 1,\ 0)$
$\epsilon=0.3$, three actions
$e\approx2.718$, $e^2\approx7.389$
Solution
Both rules are explicit formulas of the entries; the only trap is the greedy action's share under ε-greedy.
Both rows add to $1$. Boltzmann's ratio $\Pr(a_1)/\Pr(a_2)$ must be $e^{2-1}=2.718$, and $0.665/0.245=2.71$.
ε-greedy treats all non-greedy actions alike; Boltzmann ranks them by their entries.
Pure greedy gets stuck at the charging pad
In the corridor, $Q=0$ at the start, $\alpha=0.5$ and $\gamma=0.9$, and ties are broken toward left. The agent acts greedily in S0. Follow the first two episodes and say what happens next.
FindThe action chosen in S0 and the entries $Q(\text{S0},\cdot)$ over the episodes.
Given
S0: left onto the pad ($+1$, the run ends); right to S1 ($-1$)
$Q=0$ for every pair, $\alpha=0.5$, $\gamma=0.9$
ties go to left
Solution
Trace the rule literally: the greedy choice depends only on the two entries at S0, and only the chosen entry is ever updated.
Right is never tried, so its entry never moves; left's entry creeps toward 1 and stays ahead.
Answer $$\boxed{\text{greedy: left forever, worth }1;\qquad\text{optimal: right, worth }6.2}$$
Check
The slides' guarantee needs every pair tried infinitely often; greedy tries (S0, right) zero times, so the guarantee does not apply, and the result is indeed wrong.
An untried action whose entry looks worse can stay untried forever; some exploration is required, not optional.
How often ε-greedy explores, and how the scale of Q changes Boltzmann
(a) In S0 with two actions, left is greedy and $\epsilon=0.2$. On average, how many visits until ε-greedy first tries right? (b) Under Boltzmann exploration, what probability does the second action get when the entries are $(2,\ 1)$, and when they are $(20,\ 10)$?
Find(a) The expected number of visits. (b) The second action's probability in both cases.
Given
(a) $\epsilon=0.2$, two actions, left greedy
(b) entries $(2,\ 1)$ and $(20,\ 10)$
Solution
(a) Each visit is an independent trial with the same chance, so the wait is geometric. (b) Boltzmann depends on the difference of the entries, so compare the two gaps.
(a) Chance per visit
$$\Pr(\text{right})=\epsilon/2=0.1$$
Only heads can choose right, and then with probability $1/2$.
$$\mathbb E[\text{visits}]=1/0.1=10$$
Mean of a geometric waiting time with success probability $0.1$.
(a) In $1000$ visits ε-greedy tries right about $1000\cdot0.1=100$ times. (b) The odds are $e^{\text{gap}}$: $e^1=2.72$ and $e^{10}=22026$, matching $0.731/0.269=2.72$ and $1/(4.54\times10^{-5})\approx22\,000$.
Rewards measured in larger units make Boltzmann exploration nearly greedy; that is why a temperature is often added (further reading).
Checkpoint
§14.7 — the share of a non-greedy action
An agent uses ε-greedy with $\epsilon=0.2$ in a state with four actions, and $a_1$ is the greedy action.
Find(a) What is $\Pr(A_t=a_3\mid S_t)$?
Given
$\epsilon=0.2$
$\lvert\mathcal A\rvert=4$; greedy action $a_1$
Hint 1/4
Decide in which branch of the coin $a_3$ can be chosen at all.
Hint 2/4
Heads, with probability $\epsilon$, draws uniformly from all $\lvert\mathcal A\rvert$ actions; tails takes $a_1$.
Hint 3/4
Here $\epsilon=0.2$ and $\lvert\mathcal A\rvert=4$, so $\Pr(a_3)=0.2\cdot\frac14$.
Hint 4/4
$\Pr(A_t=a_3\mid S_t)=0.05$.
Show solution
A non-greedy action can only come from the uniform draw, so multiply the two probabilities.
The problem gives $p(s'|s,a)$ and the rewards and asks for values after some sweeps, for the optimal values or for the optimal policy.
Tabulate the model
For each pair $(s,a)$ list the landing states with $p$ and $r$, and $r(s,a)$.
Freeze the old table
Copy $v_k$; nothing computed during this sweep is used before the sweep ends.
Score every action
$r(s,a)+\gamma\sum_{s'}p(s'|s,a)\,v_k(s')$; terminal states have value $0$.
Max and argmax
$v_{k+1}(s)$ is the largest score; record the action that attains it.
Stopping check
Stop when $\max_s\lvert v_{k+1}(s)-v_k(s)\rvert\le\epsilon$; the policy is the last argmax.
Where it goes wrong
Reading a value computed earlier in the same sweep.
Multiplying the immediate reward by $\gamma$.
Giving a terminal state a value other than $0$.
One Q-learning update by hand
The problem gives an observed transition $(S_t,A_t,R_{t+1},S_{t+1})$, a table, $\alpha$ and $\gamma$.
Best entry at the next state
$\max_{a'}Q(S_{t+1},a')$ from the table as it is now; $0$ if $S_{t+1}$ is terminal.
Target
$\hat Q=R_{t+1}+\gamma\max_{a'}Q(S_{t+1},a')$.
Blend
$Q(S_t,A_t)\leftarrow(1-\alpha)Q(S_t,A_t)+\alpha\hat Q$; no other entry changes.
Sanity check
The new entry lies between the old entry and the target.
Where it goes wrong
Using $Q(S_{t+1},A_{t+1})$ instead of the max.
Swapping $\alpha$ and $1-\alpha$.
Updating an entry of the next state instead of the current one.
A: value iteration updates q(good, run) with the model
For the machine ($\gamma=0.8$), value iteration in q form holds $q_1=(6;\ 2,\ -1)$ for (good, run), (worn, run), (worn, repair). Compute $q_2(\text{good},\text{run})$.
Find$q_2(\text{good},\text{run})$.
Given
good, run: good ($0.5$, $7$) or worn ($0.5$, $5$)
$q_1=(6;\ 2,\ -1)$, $\gamma=0.8$
Solution
The model is known, so average over both landing states and overwrite the entry.
The expected-reward form gives the same: $6+0.8\,(0.5\cdot6+0.5\cdot2)=9.2$.
No learning rate: the new entry replaces the old one.
B: Q-learning updates Q(good, run) from one observed day
A plant without the model of the machine holds $Q(\text{good},\text{run})=6$, $Q(\text{worn},\text{run})=2$ and $Q(\text{worn},\text{repair})=-1$, and observes (good, run, $5$, worn). With $\alpha=0.5$ and $\gamma=0.8$, update $Q(\text{good},\text{run})$.
$6.3$ lies between the old $6$ and the target $6.6$.
A learning rate blends; one sample replaces the average over landing states.
Both targets add a reward to $\gamma$ times the best entry of a landing state. Value iteration averages over both landing states with the known $p$ and overwrites the entry, $9.2$; Q-learning uses the one landing state it saw and moves only a fraction $\alpha$ toward it, $6.3$.
How to tell them apart
If the problem gives $p(s'|s,a)$, sum over $s'$ and overwrite. If it gives an observed transition $(s,a,r,s')$ and a learning rate, update that one entry with $\alpha$.
A: the value of 'keep running when worn' at γ = 0.8
For the machine with $\gamma=0.8$, evaluate the policy that runs the machine in both states.
Find$v_{\pi_N}(\text{good})$ and $v_{\pi_N}(\text{worn})$.
Given
good, run: expected reward $6$; good or worn with $0.5$ each
worn, run: $+2$, stays worn
worn, repair: $-1$, lands in good (not used by this policy)
$\gamma=0.8$
Solution
A given policy: plug in its actions and solve linear equations, with no max.
$v_*\ge v_{\pi_N}$ in both states: $20\ge16.667$ and $15\ge10$, as optimality requires.
The optimal values are the largest values any policy can reach, state by state.
A given policy's values solve linear equations with its own actions plugged in; the optimal values solve the same equations with a max over actions, and they are at least as large in every state: $16.667\le20$ and $10\le15$.
How to tell them apart
'Value of this policy' means plug in the policy's actions, with no max. 'Optimal value' or 'best policy' means a max over actions, or value iteration.
Scaffolding comes off
The common skeleton
List, for each state and each allowed action, the landing states with $p(s'|s,a)$ and the reward.
Score each action with the old values: $r(s,a)+\gamma\sum_{s'}p(s'|s,a)\,v_k(s')$.
Take the max over actions to get $v_{k+1}(s)$; the action that attains it is the greedy action.
Compare $\max_s\lvert v_{k+1}(s)-v_k(s)\rvert$ with $\epsilon$ to decide whether to sweep again.
1 · fully worked
One sweep of the study plan from v1 = (3, 1)
A student is fresh or tired each evening. Fresh: study pays $+3$ and leaves the student fresh or tired with probability $0.5$ each; rest pays $0$ and stays fresh. Tired: study pays $+1$ and stays tired; rest pays $0$ and returns to fresh. With $\gamma=0.9$ and $v_1=(3,\ 1)$ for (fresh, tired), do one sweep with $\epsilon=0.5$.
Find$v_2$, the greedy actions and whether to stop.
Given
fresh: study ($+3$; fresh $0.5$, tired $0.5$), rest ($0$; fresh)
Monotonicity: $v_1=(3,\ 1)$ is itself one sweep from $v_0=0$ (the best immediate rewards), and with non-negative rewards every later sweep can only raise the values; $4.8\ge3$ and $2.7\ge1$ hold.
The skeleton is the same in every value iteration question; only the table of landing states changes.
2 · you write the reasoning
Easier, and this time you write the reasons. States A and B with deterministic moves and $\gamma=0.5$; the current values are $v_k(A)=2$ and $v_k(B)=6$. In A, stay pays $+1$ and stays in A, go pays $0$ and moves to B. In B, back pays $+4$ and moves to A. Do one sweep with $\epsilon=0.5$.
Each action is scored with the old values $v_k$: reward plus $0.5$ times the value of the cell it moves to.
$v_{k+1}(A)=\max(2,\ 3)=3\quad(\text{go})$
reasoning
The new value is the larger score; go attains it, so go is the greedy action in A.
$v_{k+1}(B)=4+0.5\cdot2=5$
reasoning
B has one action, so there is no max; it uses the old $v_k(A)=2$, not the new $3$.
$\max(\lvert3-2\rvert,\ \lvert5-6\rvert)=1>0.5$
reasoning
The largest change is $1$, above $\epsilon$, so another sweep is needed.
3 · find the buried error
Harder, with two errors buried in the solution. A student does one sweep with $\gamma=0.8$ from $v_k=(4,\ 2,\ 6)$ for (X, Y, Z). Which two steps are wrong?
X: action a pays $+2$ and lands in X or Y with probability $0.5$ each; action b pays $0$ and lands in Z.
Y: action a pays $-1$ and lands in X; action b pays $+1$ and lands in Y with probability $0.8$ or Z with $0.2$.
Z: its only action c pays $+5$ and lands in X.
Step 1. X, a: $2+0.8\,(0.5\cdot4+0.5\cdot2)=4.4$.
Step 2. X, b: $0+0.8\cdot6=4.8$, so $v_{k+1}(X)=4.8$ with b greedy.
Step 3. Y, a: $-1+0.8\cdot4.8=2.84$.
Step 4. Y, b: $1+0.8\,(0.8\cdot2+0.2\cdot6)=3.24$, so $v_{k+1}(Y)=3.24$ with b greedy.
Step 5. Z, c: $0.8\cdot5+0.8\cdot4=7.2$, so $v_{k+1}(Z)=7.2$.
Step 6. The largest change is $\max(0.8,\ 1.24,\ 1.2)=1.24$.
the two buried errors (2)
⚠ step 3
It uses $v(X)=4.8$, computed in step 2 of this same sweep; a synchronous sweep must use the old $v_k(X)=4$.
Filling the table from top to bottom, the fresh number sits right above the line being written.
right
$-1+0.8\cdot4=2.2$. The value $v_{k+1}(Y)=3.24$ survives only because b wins either way.
⚠ step 5
It multiplies the immediate reward by $\gamma$: $0.8\cdot5$ instead of $5$.
Discounting every reward, the first one included, is the most common slip with returns.
right
$5+0.8\cdot4=8.2$, and the largest change becomes $\lvert8.2-6\rvert=2.2$.
4 · the bare problem
§14.5 — one sweep for a server
A server is busy or idle. Busy: serve pays $+2$ and stays busy with probability $0.6$ or becomes idle with $0.4$; shed pays $-1$ and becomes idle. Idle: serve pays $+1$ and becomes busy with probability $0.3$ or stays idle with $0.7$; sleep pays $0$ and stays idle. With $\gamma=0.9$ the current values are $v_k(\text{busy})=5$, $v_k(\text{idle})=10$.
Find
(a) Find $v_{k+1}$ and the greedy action in each state.
(b) Should the iteration stop with $\epsilon=0.5$?
Every score lies between its reward plus $0.9\cdot5$ and its reward plus $0.9\cdot10$, the smallest and largest old values; all four do.
Nothing in the skeleton depends on the story; tabulate, score with old values, max, check.
Full exam-style question
An ad server: optimality equations, two sweeps, a Q-learning step and ε-greedyexam format
A website shows either an ad or an article to a visitor who is interested (I) or annoyed (A). Use $\gamma=0.9$.
Ad to an interested visitor: earns $4$; the visitor is then interested or annoyed with probability $0.5$ each.
Article to an interested visitor: earns $0$; the visitor stays interested.
Ad to an annoyed visitor: earns $1$, and the visitor leaves (terminal, value $0$).
Article to an annoyed visitor: earns $0$; the visitor is then interested or annoyed with probability $0.5$ each.
Find(a) The optimality equations. (b) Two sweeps of value iteration from $v_0=0$, with the greedy actions. (c) A check that $v_*=(22,\ 18)$ solves (a), and $\pi^*$. (d) The Q-learning update of $Q(I,\text{ad})=20$ after $(I,\text{ad},4,A)$, with $Q(A,\text{ad})=1$, $Q(A,\text{article})=16$, $\alpha=0.1$. (e) Under ε-greedy with $\epsilon=0.1$ and that table, the chance of an ad to an annoyed visitor.
Given
I, ad: $+4$; I or A with probability $0.5$ each. I, article: $0$; stays I
A, ad: $+1$; the visitor leaves (value $0$). A, article: $0$; I or A with probability $0.5$ each
$\gamma=0.9$
Solution
Each part uses one box of the section: (a) and (c) the optimality equations, (b) value iteration, (d) the Q-learning update, (e) the ε-greedy rule. Doing them in order reuses the numbers.
For (c), $v_*(I)-v_*(A)=4$, and sweep 2 in (b) shows the same gap: $6.25-2.25=4$. Once the greedy actions are ad in I and article in A, both values share the continuation $0.9\,(0.5\,v(I)+0.5\,v(A))$, and I adds the ad's $4$ on top.
The five parts chained four boxes of this section, and later parts reused earlier numbers; keep every intermediate result.
Practice
A · concept 4 questions
1§14.6 — what Q-learning needs to know
A team wants to train a warehouse robot with Q-learning but has no model of how often its wheels slip.
Find(a) True or false: Q-learning cannot be used unless the transition probabilities $p(s'|s,a)$ are known.
The difference of the shifts: right collects $-5\,(1+0.9+0.81)=-13.55$, left only $-5$, and $6.2-13.55=-7.35$.
In a task that never ends every policy collects $c/(1-\gamma)$ extra and the policy is safe; with terminal states, longer plans collect more of the shift.
B · computation 7 questions
1§14.1 — returns of one episode
An episode produces the rewards $R_1=2$, $R_2=0$, $R_3=-1$ and $R_4=4$, and then ends. The discount rate is $\gamma=0.9$.
Find
(a) Find $G_2$.
(b) Find $G_0$.
Given
$R_1=2,\ \allowbreak R_2=0,\ \allowbreak R_3=-1,\ \allowbreak R_4=4$; the episode ends after $R_4$
$\gamma=0.9$
Hint 1/4
Work backwards from the end of the episode.
Hint 2/4
$G_t=R_{t+1}+\gamma\,G_{t+1}$, with $G_4=0$ after the episode ends.
Hint 3/4
With $R_4=4$, $R_3=-1$, $R_2=0$, $R_1=2$ and $\gamma=0.9$: $G_3=4$, then $G_2=-1+0.9\cdot4$.
Hint 4/4
$G_2=2.6$, $G_1=2.34$ and $G_0=4.106$.
Show solution
The recursion reuses each return for the next one, so four short steps replace four separate sums.
Backwards, each return costs one multiply and one add.
2§14.1 — a reward every other step
Stream A pays $+3$, $0$, $+3$, $0$, and so on forever, starting now. Stream B is the same but starts with the $0$: $0$, $+3$, $0$, $+3$, and so on. The discount rate is $\gamma=0.8$.
Group the rewards so that the stream becomes one geometric series.
Hint 2/4
The nonzero rewards of A have weights $1,\gamma^2,\gamma^4,\dots$, and $\sum_j(\gamma^2)^j=\frac{1}{1-\gamma^2}$.
Hint 3/4
With $\gamma^2=0.64$: $G^A=\frac{3}{1-0.64}$, and B is A delayed by one step, so $G^B=0.8\,G^A$.
Hint 4/4
$G^A=8.333$ and $G^B=6.667$.
Show solution
Every other weight is zero, so the ratio of the series is $\gamma^2$, not $\gamma$.
Stream A
$$G^A=3\sum_{j\ge0}0.64^j=\frac{3}{0.36}=8.333$$
Only every second reward is nonzero, so each nonzero term is $\gamma^2=0.64$ times the one before and the sum is geometric.
Stream B
$$G^B=0+0.8\,G^A=6.667$$
B's first reward is $0$ and the rest is A one step later: the recursion $G_t=R_{t+1}+\gamma G_{t+1}$.
Answer $$\boxed{G^A=8.333,\qquad G^B=6.667}$$
Check
The two together pay $3$ every step, worth $3/(1-0.8)=15$, and $8.333+6.667=15$.
A delay of one step multiplies a return by the discount rate.
3§14.2 — expected reward from a transition table
Taking action $a$ in state $s$ leads to $s_1$, $s_2$ or $s_3$. The table gives $p(s_1|s,a)=0.2$ and $p(s_2|s,a)=0.5$; the entry for $s_3$ is smudged. The rewards are $r(s,a,s_1)=10$, $r(s,a,s_2)=2$ and $r(s,a,s_3)=-4$.
As a series from A: $4+0\cdot0.5+4\cdot0.25+0+4\cdot0.0625+\dots=\frac{4}{1-0.25}=5.333$.
Deterministic cycles give geometric series with ratio equal to the discount rate to the power of the cycle length.
5§14.5 — one more sweep in q form
For the machine with $\gamma=0.8$, value iteration in q form has reached $q_2(\text{good},\text{run})=9.2$, $q_2(\text{worn},\text{run})=3.6$ and $q_2(\text{worn},\text{repair})=3.8$.
Find
(a) Compute $q_3$ for the three pairs.
(b) Give the greedy action in worn and $\max\lvert q_3-q_2\rvert$ over the three pairs.
Given
good, run: expected reward $6$; lands in good or worn with probability $0.5$ each
worn, run: reward $2$, stays worn; worn, repair: reward $-1$, lands in good
The v form gives $v_3=(11.2,\ 6.36)$ for the same sweep, and $\max_aq_3$ reproduces it.
In q form, compute each landing state's best entry once and reuse it in every pair that lands there.
6§14.6 — two updates in a row
A robot moves between rooms A and B with actions go and stay. Its table holds $Q(A,\text{go})=2$, $Q(A,\text{stay})=1$, $Q(B,\text{go})=5$ and $Q(B,\text{stay})=3$. It observes $(A,\text{go},0,B)$ and then $(B,\text{stay},1,B)$; $\alpha=0.2$, $\gamma=0.9$.
Find
(a) Find $Q(A,\text{go})$ after the first update.
(b) Find $Q(B,\text{stay})$ after the second update.
Both rows add to $1$ up to rounding, and Boltzmann's $\Pr(a_2)/\Pr(a_4)$ must be $e^{1}=2.718$; unrounded, $0.10248/0.03770=2.718$.
Tied entries always get tied probabilities under Boltzmann; ε-greedy ties everything that is not greedy.
C · exam level 5 questions
1§14.4 — does repairing still pay at γ = 0.5?
The machine of this section is operated with a smaller discount rate, $\gamma=0.5$. Two policies both run a good machine; $\pi_R$ repairs a worn one and $\pi_N$ keeps running it.
Find
(a) Compute $v_{\pi_R}$ in both states.
(b) Compute $v_{\pi_N}$ in both states.
(c) Use the optimality equation at worn to decide which policy is optimal.
Given
good, run: to good ($0.5$, reward $7$) or worn ($0.5$, reward $5$); expected reward $6$
Consistency: $\pi_N$ is at least as good as $\pi_R$ in both states, $9.333\ge9.2$ and $4\ge3.6$, as an optimal policy must be.
A repair costs now and pays later, so a small discount rate makes it lose; at $\gamma=0.8$ it won.
2§14.6 — three updates, then act
A cleaning robot moves between the hall and a room. Its table holds $Q(\text{hall},\text{move})=0$, $Q(\text{hall},\text{wait})=2$, $Q(\text{room},\text{move})=4$, $Q(\text{room},\text{wait})=0$. It observes, in order, (hall, move, $1$, room), (room, move, $3$, hall), (hall, wait, $0$, hall). Here $\alpha=0.5$ and $\gamma=0.9$.
Find
(a) Give the table after the three updates.
(b) Give the greedy action in each of the two states, hall and room.
(c) Under ε-greedy with $\epsilon=0.2$, what is the probability of wait in the hall?
Update 1 lands in the room, whose max is $4$. Update 2 lands in the hall, whose max is then $\max(\text{new move entry},\ 2)$. Update 3 also lands in the hall.
Hint 4/4
Table: hall move $2.3$, hall wait $2.035$, room move $4.535$, room wait $0$; greedy: move in both; wait in the hall has probability $0.1$.
Show solution
Order matters because each target reads the latest table, so go transition by transition.
Each new entry lies between its old value and its target: $2.3\in[0,4.6]$, $4.535\in[4,5.07]$, $2.035\in[2,2.07]$.
In a trace, reread the table before every target; an entry changed one line earlier can change the max.
3§14.7 — why the table never reaches q*
An engineer runs Q-learning on a robot with the greedy rule and a constant $\alpha=0.1$. After $10\,000$ steps many entries are still exactly at their starting value $0$, and the learned policy is poor.
Find(a) Which single change addresses the cause?
Given
action rule: greedy, $A_t=\arg\max_aQ(S_t,a)$
$\alpha=0.1$ constant
many entries never changed from $0$
Hint 1/4
Ask why an entry would stay exactly at its starting value.
Hint 2/4
An entry changes only when its pair is tried; the convergence result needs every pair tried infinitely often.
Hint 3/4
Greedy tries only the current best action in each state, so pairs that look worse are never tried.
Hint 4/4
Add exploration, for example ε-greedy, so every pair keeps being tried.
Show solution
The symptom, entries exactly at their start value, points to pairs that were never updated, which is a visiting problem, not a step size problem.
The slides' condition, every pair infinitely often, fails.
Answer $$\boxed{\text{add exploration, e.g. }\epsilon\text{-greedy}}$$
Check
The corridor example: greedy with ties to left never tries (S0, right) and settles on the value $1$ instead of $6.2$.
Step sizes decide how fast tried entries settle; exploration decides which entries are tried at all.
4§14.5 — a ledge, a longer detour and value iteration
From the start cell a robot can take the ledge, which reaches the goal ($+10$) with probability $1-q$ and the pit ($-10$) with probability $q$, both ending the run. Or it takes a two-step detour: start to D1 ($-1$), D1 to D2 ($-1$), then D2 into the goal ($+10$). The discount rate is $\gamma=0.9$.
Find
(a) Find the slip probability $q$ at which the two first moves tie.
(b) For $q=0.3$, run value iteration from $v_0=0$ and find the first sweep after which the greedy action at the start is the detour.
Answer $$\boxed{q=0.19;\qquad\text{detour greedy from sweep }3}$$
Check
At $q=0.3$ the ledge is worth $0.7\cdot10+0.3\cdot(-10)=4<6.2$, so the detour must be optimal, and sweep 3 is the first time the start can see the goal through two detour cells.
Value iteration from zero needs as many sweeps as the path to the reward is long before distant rewards can change a decision.
5§14.6 — the first wrong line of a Q-learning trace
A student processes two transitions with Q-learning, $\alpha=0.5$ and $\gamma=0.9$, starting from the table in the given list, and writes four steps.
Target of $(s_1,a,2,s_2)$: $2+0.9\max(2,\ 6)=7.4$.
$Q(s_1,a)=0.5\cdot1+0.5\cdot7.4=4.2$.
Target of $(s_2,a,-1,s_1)$: $-1+0.9\max(1,\ 3)=1.7$.
$Q(s_2,a)=0.5\cdot2+0.5\cdot1.7=1.85$.
Find(a) Which step is the first one that is wrong?
$2.39$ lies between the old entry $2$ and the corrected target $2.78$; the student's $1.85$ moved the entry down, toward a target read from a table that no longer existed.
An error in one target spreads: every later update that reads the wrong entry inherits it.
D · interleaved 5 questions
1§14.6 — a news app keeps one number
A news app shows a sports story to new users; each showing ends the session and pays the reading time in minutes. The first five showings paid $3$, $7$, $5$, $9$ and $6$ minutes. The app keeps one number and after the $n$th showing replaces it by $(1-\frac1n)\cdot\text{old}+\frac1n\cdot\text{new}$, starting from $0$.
Find
(a) What is the number after five showings?
(b) What is its standard deviation after 100 showings?
(c) What does the number converge to, and why?
Given
payoffs: $3,\ 7,\ 5,\ 9,\ 6$
update after showing $n$: $(1-\frac1n)\,\text{old}+\frac1n\,\text{new}$
reading times: independent, mean $6$, standard deviation $2$
Hint 1/4
Find out what this update computes, then use what you know about that quantity.
Hint 2/4
With weight $\frac1n$ the update keeps the running sample mean $\bar X_n=\frac1n\sum_{i\le n}X_i$; $\operatorname{Var}(\bar X_n)=\sigma^2/n$.
Hint 3/4
Here the payoffs add to $3+7+5+9+6=30$ over $5$ showings; $\sigma=2$ and $n=100$.
Hint 4/4
(a) $6$. (b) $2/\sqrt{100}=0.2$. (c) $6$, by the law of large numbers.
Show solution
Unrolling the update shows it is the sample mean, whose variance and limit are known from the probability review.
Variance of a mean of independent variables: $\sigma^2/n$.
$$\bar X_n\to\mathbb E[X]=6$$
Law of large numbers.
Answer $$\boxed{6;\quad0.2;\quad\to6}$$
Check
$(3+7+5+9+6)/5=6$ directly, matching the last unrolled value.
Q-learning with $\alpha=1/n$ on a pair whose next state is terminal is exactly a sample mean.
2§14.6 — two classmates, one table entry
A table entry is $3$ and a new target value is $7$. Student A takes one gradient-descent step of size $0.25$ on the loss $\ell(Q)=\frac12(7-Q)^2$. Student B computes $(1-\alpha)Q+\alpha\cdot7$ with $\alpha=0.25$.
Find
(a) Compute both results.
(b) Show that the two rules agree for every $Q$, $T$ and step size.
(c) In the neural network update $w(n+1)=w(n)-\eta\nabla l$, what plays $w$, $\eta$ and $l$?
Given
entry $Q=3$, target $T=7$
A: $Q\leftarrow Q-0.25\,\frac{d\ell}{dQ}$ with $\ell=\frac12(T-Q)^2$
Check the identity at another point: $Q=0$, $T=10$, $\eta=0.5$ gives $5$ both ways.
This is why a deep Q network can be trained with ordinary gradient steps: each update is SGD on a squared error toward the target.
3§14.7 — an energy view of action choice
An agent chooses among three actions with probability proportional to $e^{Q(s,a)}$, where $Q(s,\cdot)=(1,\ 0,\ -1)$. A restricted Boltzmann machine assigns a configuration the probability $e^{-E}/Z$.
Find
(a) What plays the energy $E$, and what is $Z$ here?
(b) Compute the three probabilities.
(c) If every entry of $Q(s,\cdot)$ increases by $5$, what happens to the probabilities?
These are the same probabilities as for $Q=(2,\ 1,\ 0)$ in the worked example: that table is this one shifted by $1$.
Only differences of entries matter to this rule, just as only energy differences matter in a Boltzmann machine.
4§14.2 — a trajectory as a directed graph
An agent follows a stationary Markov policy. Consider the variables $S_0,\ A_0,\ S_1,\ A_1,\ S_2$, with an arrow into each variable from each variable it is drawn from directly.
Find
(a) List the arrows.
(b) Find the Markov blanket of $S_1$.
(c) Is $S_2$ independent of $S_0$ given $S_1$ and $A_1$?
Given
$A_t$ is drawn from $\pi(\cdot\mid S_t)$
$S_{t+1}$ is drawn from $p(\cdot\mid S_t,A_t)$
Markov blanket in a directed graph: parents, children and the children's other parents
Hint 1/4
Draw one arrow per 'is drawn from' relation, then read the blanket off the graph.
Hint 2/4
Parents of a node are what it is drawn from; the blanket adds children and co-parents; a node is independent of its non-descendants given its parents.
Blocking check: every path from $S_0$ to $S_2$ passes through $S_1$ or $A_1$ as a chain or fork, and both are observed, so all paths are blocked.
The Markov property of an MDP is a conditional independence statement that the chain-shaped graph makes visible.
5§14.6 — a steady estimate or a quick one
The targets observed for one state-action pair are independent with mean $10$ and variance $9$. One agent uses $\alpha=1/n$; another uses a constant $\alpha=0.2$, whose estimate, once its start value is forgotten, is $\sum_{j\ge0}\alpha(1-\alpha)^jX_{n-j}$.
Find
(a) Find the variance of agent 1's estimate after 100 updates.
(b) Find the variance of agent 2's estimate.
(c) Which agent should be used if the mean never changes, and which if it drifts over time?
Both estimates are weighted sums of independent targets; add the squared weights.
Hint 2/4
$\operatorname{Var}(\sum_jw_jX_j)=\sigma^2\sum_jw_j^2$; for agent 2, $\sum_{j\ge0}\alpha^2(1-\alpha)^{2j}=\frac{\alpha^2}{1-(1-\alpha)^2}=\frac{\alpha}{2-\alpha}$.
$a^\circ$ the greedy action; other actions get $\epsilon/\lvert\mathcal A\rvert$ under ε-greedy
Check yourself
Close the page and write from memory: the return and its recursion, the definitions of $v_\pi$ and $q_\pi$, the Bellman optimality equations, one value iteration sweep, the Q-learning update and the ε-greedy probabilities. Then compare with the formula card.
Compute $G_0$ for the rewards $-1,-1,+10$ at $\gamma=0.9$ and say why $R_{t+1}$ is undiscounted?
c-return
Write the machine example as an MDP and fix a state that is not Markov?
c-mdp
Solve the two linear equations for a given policy and average $q_\pi$ with $\pi$'s probabilities?
c-policy-value
Check claimed optimal values state by state and read off $\pi^*$?
c-bellman
Do two value iteration sweeps from zero, in both forms, without reading a value from the current sweep?
c-value-iteration
Update a Q table from a list of observed transitions and say what the convergence result needs?
c-q-learning
Give every action's probability under ε-greedy and under Boltzmann, and explain why greedy alone can get stuck?
c-exploration
Glossary (28 terms)
reinforcement learningpekiştirmeli öğrenme
Learning to choose actions from the rewards that follow them, where the learner's own actions decide what it observes and the goal is the largest expected return.
agentajan
The learner and decision maker: it observes the state, picks an action and receives a reward.
environmentortam
Everything outside the agent: it answers each action with a reward and a next state.
rewardödül
The number $R_{t+1}$ the environment returns after the action taken at step $t$; costs are negative rewards.
return
The discounted sum of future rewards, $G_t=\sum_k\gamma^kR_{t+k+1}$.
discount rate
The factor $\gamma$ by which a reward loses weight for every step it arrives later.
episode
One run from a start state until a terminal state.
terminal state
A state that ends the episode; its value is $0$ and it has no actions.
policypolitika
A rule that maps what the agent knows to a distribution over actions.
stationary Markov policy
A policy $\pi(a|s)$ that uses only the current state, in the same way at every step.
deterministic policy
A policy that puts probability $1$ on one action in each state, written $\pi(s)$.
Markov propertyMarkov özelliği
Given the current state and action, the next state and reward do not depend on the earlier history.
Markov decision processMarkov karar süreci
A model with finite states, actions allowed in each state, transition probabilities $p(s'|s,a)$ and expected rewards $r(s,a,s')$.
transition probabilitygeçiş olasılığı
$p(s'|s,a)$, the probability that one step from state $s$ with action $a$ moves the process to $s'$.
durum değer fonksiyonu
$v_\pi(s)$, the expected return from $s$ when actions follow $\pi$.
action value functioneylem değer fonksiyonu
$q_\pi(s,a)$, the expected return after taking $a$ in $s$ and following $\pi$ afterwards.
optimal policyen iyi politika
A policy whose value is at least that of every other policy in every state.
Bellman optimality equation
$v_*(s)=\max_a[r(s,a)+\gamma\sum_{s'}p(s'|s,a)v_*(s')]$: the best value is that of the best first action followed by optimal play.
value iterationdeğer iterasyonu
Repeating the Bellman optimality update on a value table until it stops changing, then acting greedily.
Q-learning
A method that learns the optimal action values from observed transitions, without a model, by moving each tried entry toward a one-sample target.
learning rateöğrenme oranı
The step size $\alpha$ that sets how far each update moves an entry toward its target; $\eta$ in the neural networks section.
model-free
Learning that uses observed transitions instead of known transition probabilities.
explorationkeşif
Trying actions that do not look best at the moment, to learn their values.
sömürü
Taking the action that looks best according to the current estimates.
greedyaçgözlü
Always taking $\arg\max_aQ(s,a)$, with no exploration.
ε-greedy
With probability $\epsilon$ pick an action uniformly at random, otherwise the greedy one.
Boltzmann exploration
Pick action $a$ with probability proportional to $e^{Q(s,a)}$.
deep Q network
A neural network that replaces the Q table and is trained toward the Q-learning target with gradient steps.
What comes next
§15 · Multi-armed bandits and online learning
Here actions moved the agent between states, and a reward could pay off many steps later. Next there is one situation met over and over, such as choosing a route or an item to recommend, and the whole question is how to balance trying options against using the best one so far.
Sources
textbookT. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, Springer (course textbook) The weekly line names no chapter of the book, so no section numbers are cited here.
course materialEEE 485 lecture slides, chapter 14: Reinforcement learning Scope, order of topics and notation (S_t, A_t, R_{t+1}, γ, G_t, the history H_t, π, p(s′|s,a), r(s,a,s′), v_π, q_π, v_*, q_*, π*, v_k, q_k, ε, Q, Q̂, α and the coin C_t) follow the slides; all explanations, examples, figures and exercises here are original.
course materialEEE 485 syllabus page on STARS, Fall 2026-27, printed 21 September 2026 Assessment weights, the weekly topic list and the recommended books.
standard resultM. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, 1994 Cited on the slides for the existence of a deterministic stationary optimal policy.