ML10.2 · LESSON 2 OF 6

MDPs and returns

Distinguish sequential decision-making, temporal prediction, recommendation and causal estimation.

THE IDEA

From one choice to a sequence of states

A Markov decision process adds what a bandit lacks: a state. At each step the agent sees a state, picks an action, receives a reward and lands in a new state. The Markov part means the next state and reward depend only on the current state and action, not on the whole history.

Actions now have consequences that last. Walking toward a distant goal may cost a little reward every step, and the payoff only arrives at the end, so you must compare rewards that arrive at different times.

Return and discounting

The return is the total reward collected from a time step onward. With a discount factor gamma between 0 and 1, later rewards count for less:

return

G = r0 + gamma * r1 + gamma^2 * r2 + ...

rewards 1 then 2, gamma = 0.5:   G = 1 + 0.5 * 2 = 2

Gamma near 0 makes the agent short-sighted, since only the immediate reward matters. Gamma near 1 makes it patient. Discounting also keeps the sum finite for tasks that could go on forever.

Presets:

gamma0.9

t	move	reward r	gamma^t	gamma^t r	running G
0	↑	-0.04	1	-0.04	-0.04
1	↑	-0.04	0.9	-0.036	-0.076
2	→	-0.04	0.81	-0.0324	-0.1084
3	→	-0.04	0.729	-0.0292	-0.1376
4	→	1	0.6561	0.6561	0.5185

Return G = 0.5185 (the episode ended) · with gamma 1: 0.84 · with gamma 0: -0.04

Walk a path on the grid and watch the return build up reward by reward. Change gamma and compare two paths.

Predict first. With gamma = 0, which rewards does the return include?

Value iteration: planning when you know the rules

If the transitions and rewards are known, you can compute how good each state is. The value of a state is the best return reachable from it. Value iteration repeatedly applies one rule to every state until nothing changes:

one sweep

V(s) = max over actions a of  sum over outcomes of  prob * (reward + gamma * V(next state))
terminal states keep V = 0

sweep 0

gamma0.9step reward-0.04

Click a non-terminal cell to see how its next value is built from the current numbers. Green arrows show the best moves given the current values. Terminal cells are worth 0 afterwards because the episode ends.

Press Sweep +1 to run one sweep, or run to convergence. Values spread outward from the goal like ripples, and the arrows show the best action in each state.

Chapter context

These topics change the structure of the learning problem. Their first lesson is to identify what a prediction or action is allowed to depend on and how feedback is produced. Each section is a bridge to a larger specialist subject.

TRY IT YOURSELF

Part 1. Do it hands-on

Two knobs, gamma and the cost per step, decide which exit the greedy agent heads for. Use them to build the behaviours the tasks ask for.

gamma0.9step reward-0.04

values after 6 sweeps (stops when the largest change is under 1e-10)

first move from S: ↑ or → (tie = several arrows)

greedy walk (lowest index on ties): ends at the exit worth 1

To do: Make the agent short-sighted: set gamma so the greedy walk from the start ends at the near +0.3 exit
To do: Make the agent reach the far +1 exit even though every step costs at least 0.2 (step reward -0.20 or lower)
To do: Find a positive step reward at which the greedy agent never leaves the grid within 30 steps
To do: Set gamma to 0 and confirm all four first moves tie (the agent only values the very next reward)

Part 2. Do it in code

Write discounted_return(rewards, gamma): r0 + gamma r1 + gamma^2 r2 + ... An empty list gives 0. gamma 0 keeps only the first reward and gamma 1 is the plain sum.
Write returns_to_go(rewards, gamma): the list of returns G_t from each time step to the end, using G_t = r_t + gamma G_(t+1).
Write value_iteration(P, gamma, theta=1e-9). P[s] maps an action to a list of (prob, next_state, reward, done). A state with no actions (empty dict) is terminal and has value 0. Repeat sweeps V(s) = max over actions of the sum prob * (reward + gamma * V(next) unless done) until the largest change is below theta (at most 1000 sweeps). Return the list V.

def discounted_return(rewards, gamma):
    pass

def returns_to_go(rewards, gamma):
    pass

def value_iteration(P, gamma, theta=1e-9):
    pass

print(discounted_return([1, 2], 0.5))

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

With rewards 1 then 2 and gamma=.5, what is the two-step return?

A1.5; the return is 0.5 × (1 + 2).B3; the return is 1 + 2, with no discount.C2; the return is 1 + 0.5 × 2.

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

G_t=\sum_{k\ge0}\gamma^k r_{t+k+1},\quad Q(s,a)\leftarrow Q(s,a)+\alpha[r+\gamma\max_{a'}Q(s',a')-Q(s,a)].

For a terminal transition the continuation term is zero. A policy-gradient estimator uses a term proportional to $\nabla\log\pi_\theta(a\mid s)$ times a return or advantage estimate.

Worked example

For a nonterminal transition, current Q=2, reward=1, discount=0.9 and best next Q=4 give target 1+0.9×4=4.6. With alpha=0.5, updated Q is 2+0.5×(4.6−2)=3.3. Reusing the same target for a terminal transition would be incorrect.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
q, reward, discount, next_q, rate = 2, 1, .9, 4, .5
target = reward + discount*next_q
assert isclose(target, 4.6)
assert isclose(q+rate*(target-q), 3.3)
terminal_target = reward
assert q+rate*(terminal_target-q) == 1.5

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Prediction is not intervention. Randomly splitting overlapping time windows can leak future information. An environment reward is a modeling choice and may omit important real-world consequences.