COMP3270 Chapter 2 · Animated Student Slides

C2: Markov Decision Processes

Most materials in this chapter are based on materials fromhttps://ai.berkeley.edu

An agent deciding how to cross a grid world

C2

Markov Decision Processes

COMP3270

Introduction to Artificial Intelligence

1

Chapter 2: Roadmap

Model Uncertainty

States, actions, transitions, and rewards

Compare Decisions

Policies, returns, and values

Compute a Policy

Value iteration and policy iteration

2

Uncertain Outcomes

C1: one action fixes the next state

C2: one action, several possible states

Outcome probabilities guide decisions

3

A Grid World with Noisy Actions

	1	2	3	4
3
2
1	●Agent

xy

State (x, y)

Agent at (1, 1)

x increases right; y increases up

	1	2	3	4
3
2
1	●Agent

xy

Regular states

Available actions: North, East, South, West

	1	2	3	4
3
2
1	●Agent

xy

Wall at (2, 2)

A move into the wall leaves the agent in place

	1	4
3		+1Exit
2		−1Exit
1	●Agent

xy

Exit states

Only available action: Exit

Exit pays +1 or −1, then the episode ends

	1	4
3		+1Exit
2		−1Exit
1	●Agent

xy

Movement reward

Every compass action pays $-0.1$

Including blocked moves and moves into exit squares

	1	4
3		+1Exit
2		−1Exit
1	●Agent

xy

Noisy movement

Intended direction: 0.8

Each sideways direction: 0.1

The agent observes its actual square after every action

4

Deterministic Grid World

	1	4
3		+1Exit
2		-1Exit
1	●Agent

xy

Choose a move

Last reward: 0.0

Total reward: 0.0

5

Stochastic Grid World

	1	4
3		+1Exit
2		-1Exit
1	●Agent

xy

Click an available action

Intended direction: 0.8

Each sideways direction: 0.1

6

Task: North, Then North

North, Then North

TASK

1234

321

xy

+1Exit

−1Exit

Start at (1, 1)

Choose North twice

What is the probability of
ending at (1, 2)?

7

The Transition Model and the Markov Property

The Transition Model
and the Markov Property

1234

321

xy

+1Exit

0.8

−1Exit

0.1

A: (1, 1) → (2, 1) → (3, 1)

B: (3, 3) → (3, 2) → (3, 1)

Same state: (3, 1)
Same action: North

Different histories
Same next-state probabilities

T(s,a,s^{\prime})=P(s^{\prime}\mid s,a)

Current state, action, next state

The current state and action suffice
Earlier history adds nothing

P(s_{t+1}\mid s_t,a_t,s_{t-1},a_{t-1},\ldots)=P(s_{t+1}\mid s_t,a_t)

8

Defining a Markov Decision Process

s\in S

The possible states

a\in A(s)

The actions available in state

s

T(s,a,s^{\prime})

The probability of each next state

R(s,a,s^{\prime})

The reward for that transition

Objective

Maximise expected cumulative reward

Also specify the initial state or distribution and any terminal states

9

A Fixed Plan Cannot Respond to a Slip

Plan1. North2. North3. East…

Start at (1, 1)

Follow a fixed list of actions

First action: North

We intend to move up

Dashed arrow: intended direction

Chosen action: North

Actual move: East

The agent lands at (2, 1)

A sideways slip, probability 0.1

Next on the list: North

North now points into the wall

This move leaves the agent in place

The plan still says North

But we are in a different square

We need an action for
where we are now

10

An MDP Solution Is a Policy

Original comic: a robot holds a map with one action arrow for each square

	1	2	3	4
3	→	→	→	+1Exit
2	↑		↑	−1Exit
1	↑	→	↑	←

xy

A policy $\pi$ determines
what to do for each state

After the slip, we are at (2, 1)

\pi(2,1)=\mathrm{East}

Observe the state, then use its action

11

Which Policy Is Better?

Policy A

	1	2	3	4
3	→	→	→	+1Exit
2	↑		↑	−1Exit
1	↑	→	↑	←

xy

Policy B

	1	2	3	4
3	→	→	→	+1Exit
2	↑		↑	−1Exit
1	→	→	↑	←

xy

Start: (1, 1). Move: −0.1. Exit: +1 or −1.
Intended direction: 0.8; each sideways direction: 0.1

TASK

12

Living Rewards and the Optimal Policy

	1	2	3	4
3	→	→	→	+1Exit
2	↑		←	−1Exit
1	↑	←	←	↓

xy

Living reward $-.01$

Reward received on every move

Intended direction: 0.8
Each sideways direction: 0.1
Exit rewards: +1 and −1

13

Racing Car

The car wants to travel quickly

Actions: Slow or Fast

Temperature changes what happens next

14

Racing-Car State Diagram

T(s,a,s')

: transition probability ·

R(s,a,s')

: reward

15

What Is the Optimal Action Here?

Slow: reward +1 · Fast: reward +2; overheating: −10 · T: transition probability

16

Choose an Action, Average the Outcomes

At a state: choose

Take the action with the
highest expected return

After an action: average

Weight each possible
outcome by its probability

Fast: equal weights, 0.5 and 0.5

T(s,a,s')

is the transition probability

Choose the best action; average over chance outcomes

17

Q-State

The agent has committed to the action but has not done it yet

$s$ is the current state
$a$ is the chosen action

$(s,a)$ is a Q-state

Original robot comic: the robot has chosen a move but its outcome is still uncertain

$s'$ is the next state

$T(s,a,s')$

Probability of reaching $s'$ after taking $a$ in $s$

18

A Corridor MDP

$T(s,a,s')$ : probability of next state $s'$ after action $a$ in current state $s$

+10 Exita

b

c

d

+1 Exite

East and West

0.8: move to the neighbour

Failed Movement

0.2: stay in the same square

Movement Reward

0 for every move

Exit at a or e

+10 or +1, then the episode ends

19

Where Can We Land?

Choose East from c

Transition	Probability
$T(c,\mathrm{East},d)$
$T(c,\mathrm{East},c)$
Any other state

TASK

20

Probability and Reward

+10 Exita

b

c

d

+1 Exite

At a, compare East with Exit

State $s$	Action $a$	Next State $s'$	Probability $T(s,a,s')$	Reward $R(s,a,s')$
a	East
a	East
a	Exit

TASK

21

From d, West or East?

+10 Exita

b

c

d

+1 Exite

West toward +10

Three successful moves, then Exit

East toward +1

One successful move, then Exit

A larger reward later, or a smaller reward sooner?

How much should waiting reduce a reward’s value?

Same model: 0.8 move, 0.2 stay · Movement reward 0

22

Comparing Reward Sequences

Original comic: a robot compares jewels along two possible routes

More reward?

[1,2,2]\quad\text{or}\quad[2,3,4]

Earlier reward?

[0,0,1]\quad\text{or}\quad[1,0,0]

How should we compare whole reward sequences?

23

Discounting

Prefer rewards now to the same rewards later

1

Now

\gamma

One step later

\gamma^2

Two steps later

Each extra step multiplies the reward’s value by $\gamma$

0<\gamma<1

24

Which State Sequence Is Better?

Return from the start: $G_0=R_1+\gamma R_2+\gamma^2R_3$

	Without Discounting ( $\gamma=1$ )	With $\gamma=0.5$
A
B

TASK

Calculate both returns for γ = 1 and γ = 0.5

25

Discounted Return

Example

1

2

3

Reward

R_{t+1}

R_{t+2}

R_{t+3}

Weight

1

\gamma

\gamma^2

G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots

A smaller $\gamma$ gives less weight to later rewards

0\leq\gamma\leq1

for finite reward sequences

26

Discounting and the Preferred Route

+10 Exita

b

c

d

+1 Exite

Start at d · Movement reward 0 · 0.8 move, 0.2 stay

Discount	West to +10	East to +1	Preferred
0.1	0.005	0.082	East
0.9	6.769	0.878	West

Expected discounted returns include failed-move delays and a separate Exit action

27

Infinite Reward Sequences

At $\gamma=0.9$ : Fast when Cool, Slow when Warm

A racing car driving around an infinity-shaped track

The optimal policy keeps driving without overheating

Slow earns +1; Fast from Cool earns +2

The agent earns +1 on every move, forever

No discount

1+1+1+\cdots\to\infty

With $\gamma=0.5$

1+\frac12+\frac14+\cdots=2

An endless reward sequence can have a finite discounted return

Every reward has magnitude at most $R_{\max}$ ; $0\leq\gamma<1$

|G_t|\leq\sum_{k=0}^{\infty}\gamma^k|R_{t+k+1}|\leq R_{\max}(1+\gamma+\gamma^2+\cdots)=\frac{R_{\max}}{1-\gamma}

28

State Values and Action Values

$V^*(s)$

Best expected return
starting in $s$

$Q^*(s,a)$

Take $a$ in $s$ , then act optimally

Includes the reward from the first action

V^*(s)=\max_a Q^*(s,a)

s

is the current state;

a

is the first action

29

A Backup Combines Reward and Future Value

Choose Fast at Cool

Reward from This Action

2

Average Future Value

0.5(15.5)+0.5(14.5)=15

2+0.9(15)=15.5

Q^*(\mathrm{Cool},\mathrm{Fast})=0.5[2+0.9V^*(\mathrm{Cool})]+0.5[2+0.9V^*(\mathrm{Warm})]

Discount 0.9 · Supplied optimal continuation values

30

The Bellman Optimality Equations

Q^*(s,a)=\sum_{s^{\prime}}T(s,a,s^{\prime})\bigl[R(s,a,s^{\prime})+\gamma V^*(s^{\prime})\bigr]

V^*(s)=\max_a Q^*(s,a)

\pi^*(s)\in\operatorname*{arg\,max}_a Q^*(s,a)

Average over outcomes, then maximise over actions

31

Bellman in Gridworld

	1	2	3	4
3	0.31	0.51	0.72	+11.00
2	0.15		0.36	-1-1.00
1	0.01	0.01	0.15	-0.09

xy

Choose East at (3, 3)

Next State	Probability	Value
(4, 3)	0.80	1.00
(3, 3)	0.10	0.72
(3, 2)	0.10	0.36

Q^*((3,3),\mathrm{East})\approx 0.72

Each term: probability × (transition reward + discounted next-state value)

Movement reward −0.1 · Discount 0.9 · Initial Classic configuration

32

Value Iteration

$V_k(s)$ is the best expected return with $k$ actions remaining

V_0(s)=0

V_{k+1}(s)=\max_{a\in A(s)}\sum_{s^{\prime}}T(s,a,s^{\prime})[R(s,a,s^{\prime})+\gamma V_k(s^{\prime})]

One action now, then $k$ actions remain; Exit also counts as an action

33

Value Iteration in Gridworld

V_{k+1}(s)=\max_a\sum_{s^{\prime}}T(s,a,s^{\prime})[R(s,a,s^{\prime})+\gamma V_k(s^{\prime})]

	2	3	4
3	0.00	0.72	+11.00
2		0.00	-1-1.00
1	0.00	0.00	0.00

xy

V_0(s)=0

One action: Exit gives +1 or −1

Two actions: move, then Exit

V_2((3,3))=0.8[0+0.9(1)]+0.2[0+0.9(0)]=0.72

Every update reads the previous sweep

Movement reward 0.00 · Discount 0.90 · Two-action snapshot

34

Q-Value Iteration

$Q_k(s,a)$ is the best expected return with $k$ actions remaining

Take action $a$ first, then act optimally

Q_0(s,a)=0

Q_{k+1}(s,a)=\sum_{s^{\prime}}T(s,a,s^{\prime})[R(s,a,s^{\prime})+\gamma\max_{a^{\prime}}Q_k(s^{\prime},a^{\prime})]

V_k(s)=\max_a Q_k(s,a)

35

Q-Value Iteration in Gridworld

	2	3	4
3	0.00	0.72	+11.00
2		0.00	-1-1.00
1	0.00	0.00	0.00

xy

Two actions remaining at (3, 3)

First Action	$Q_2$
North	0.09
East	0.72
South	0.09
West	0.00

V_2((3,3))=\max_a Q_2((3,3),a)=0.72

Each row keeps one action value; the maximum gives the state value

Movement reward 0.00 · Discount 0.90 · Two-action snapshot

36

Convergence

V_k\longrightarrow V^*,\qquad Q_k\longrightarrow Q^*

Stop when the largest change is below a tolerance

\max_s|V_{k+1}(s)-V_k(s)|<\varepsilon

\max_{s,a}|Q_{k+1}(s,a)-Q_k(s,a)|<\varepsilon

Finite states and actions, bounded rewards,

0\leq\gamma<1

37

Quiz: Value Iteration

V_{k+1}(s)=\max_a\sum_{s^{\prime}}T(s,a,s^{\prime})[R(s,a,s^{\prime})+\gamma V_k(s^{\prime})]

Round	Cool	Warm	Overheated
$V_0$	$0$	$0$	$0$
$V_1$
$V_2$

\gamma=1

· Find

V_1

and

V_2

TASK

38

Evaluate a Fixed Policy

Given this policy, how do we determine its values?

	1	2	3	4
3	→0.31	→0.39	↑0.45	Exit1.00
2	→0.00		→-0.72	Exit-1.00
1	→-0.31	→-0.39	→-0.45	→-0.47

xy

V^\pi_{k+1}(s)=\sum_{s^{\prime}}T(s,\pi(s),s^{\prime})[R(s,\pi(s),s^{\prime})+\gamma V^\pi_k(s^{\prime})]

Movement reward 0.00 · Discount 0.90 · 80% intended direction · Exit rewards +1 / −1

39

Choose Actions from Values

Given these optimal values $V^*$ , which actions should we choose?

	1	2	3	4
3	→0.64	→0.74	→0.85	Exit1.00
2	↑0.57		↑0.57	Exit-1.00
1	↑0.49	←0.43	↑0.48	←0.28

xy

\pi^*(s)\in\operatorname*{arg\,max}_{a}\sum_{s^{\prime}}T(s,a,s^{\prime})[R(s,a,s^{\prime})+\gamma V^*(s^{\prime})]

Movement reward 0.00 · Discount 0.90 · 80% intended direction · Exit rewards +1 / −1

40

Choose a Machine

Which machine would you choose for the next 100 plays?

Blue: $1 every play

Red: $2 with probability 0.75

$0 with probability 0.25

41

The Machines as an MDP

Always Blue or always Red, starting from either state

V^{\pi_{\mathrm{Blue}}}_{100}(s)=100(1)=100

V^{\pi_{\mathrm{Red}}}_{100}(s)=100[0.75(2)+0.25(0)]=150

$V^*_{100}(W)=V^*_{100}(L)=150$ → Choose Red

100 plays remain ·

\gamma=1

· Compare two fixed policies

42

What If the Transition Probabilities Are Unknown?

We can no longer solve this MDP
from the given information alone

We must act, observe rewards,
and learn the missing probabilities

In reinforcement learning, transitions, rewards, or both may be unknown

43

Learn by Playing

Choose a machine on each of 10 turns

Blue: $1 every play

Red: $2 or $0, odds unknown

Illustrative 10-play record

Machine	Observed rewards	Sample average
Blue	1, 1, 1, 1	$1.00
Red	0, 0, 0, 0, 0, 2	$0.33

Each action earns a reward and may teach us something

44

Main Ideas in Reinforcement Learning

We needed to act to learn about the machines

Idea	What It Means
Exploration	Try uncertain actions to gain information
Exploitation	Use the best action according to current estimates
Regret	Expected reward lost compared with choosing the best action
Sampling	Repeat observations because outcomes vary by chance

Learning can be harder than solving a known MDP

45