Nagoya University, Fall 2023

Lecture 9
Reinforcement Learning: Q-Learning II
This week Tutorial: Friday 8th Dec. 6th period
https://www.henrikbachmann.com/mml2023.html

Recall Reinforcement learning: Basic idea
Action(move a chess piece, take a step, turn the wheel,…)Agent(the program,machine, robot, …)

Reward(win/lose the game, achieving a goal,falling over, crashing against a wall, …)

New state(new position, new chessboard state, …)

Environment(the opponent,another agent, thereal world, …)

Markov decision process
Sometimes

As forInterpretation:each ses

Markov decision process: Example
5WFTICMarkov decision process: Dynamics

Markov decision process: Dynamics

Total reward: Car example

Markov decision process: Policy

Interpretation: A policy suggests the action you shouldtake when being in a certain state.
Goal: Find the optimal policy which increases the(discounted) total reward.

Markov decision process: Value of a policy

Goal: Find the optimal policy which increases the (discounted) total reward.

Our policy

fFCC

What isTLW

ITIO3JGETAFE
Söao tlcl

NÄfq

TIWI.rscjfgTISTHISI.RU
TIsIi

JEgTISTH

S'I.VIIS
Our policy

Farexample

ICC

f

TLWSVADTEIÄHRIGEN1RKF.IO

TIEREN

t

TKQ

HIC
TEEN HIWI
STIEG

TEE
J

Ekd

2

Filarforso

ViKloaW

VAW

W

TINI
C R WITHTCW

IT

IHN Ryu Iftar
TLW

S C

VC

8T

W S W VIN

In total

fVlc

2Hcd

Kfw

Valwl

1Ikea

Hlu

Hcd

KIWI

2

VAW

1410

Markov decision process: Value of a policy

Goal: Find the optimal policy which increases the (discounted) total reward.

Goal rephrased: Find a policy which has maximalvalue at each state.

Markov decision process: Value of a policy

Goal: Find the optimal policy which increases the (discounted) total reward.

Notice that we haveOptimal policy

Optimal policy & State-action value function

SICH

VHS

Optimal policy & State-action value function

Goal: Find the values of the state-action value function

In

carexample

FifOptimal policy & State-action value function

Goal: Find the values of the state-action value function

Goal rephrased: Find a good approximation of thestate-action value function. “Learn” the function Q.

Q-learning: Basic idea & Car example
In the car Example:
S = {C,W,O}
A = {f,s}
The (approximated) state-action value function Q can be thought of as a table
ActionC (Cool)State
W (warm)

O (overheat)f (fast)?

?

?

s (slow)?

?

?

where each entry tells us the expected (best) total reward
when taking an action in a certain state.
Q-learning: Algorithm to learn the entries of this tableQ-learning: Basic idea & Car example
Step 1: Start with some values, e.g. choose random values (or all 0):

ActionC (Cool)StateW (warm)

O (overheat)f (fast)320s (slow)

140

Q-learning: Basic idea & Car example
Step 1: Start with some values, e.g. choose random values (or all 0):

ActionC (Cool)StateW (warm)

O (overheat)f (fast)320s (slow)

1

40

Step 2: Choose a starting state, e.g. s0 = C.

Q-learning: Basic idea & Car example
Step 0: Start with some values, e.g. choose random values (or all 0):

ActionC (Cool)State
W (warm)

O (overheat)f (fast)3

20s (slow)

140

Step 1: Choose a starting state, e.g. s0 = C.
Step 2: Choose the current best action according to the table,
i.e. find the maximal entry and set the first action a0 to theaction of the corresponding row.
C (Cool)a0 = fW (warm)

O (overheat)f (fast)3

20s (slow)

140

Q-learning: Basic idea & Car example
Step 3: Take action a0 = f and receive a reward r0 and a new state s1
from the environment. For example
a0 = f

r0= 2
s1= W

Environment

This happened in our case

Question: How could we update the value Q(C,f) now?
s0 = CC (Cool)a0 = fs1 = W
W (warm)

O (overheat)f (fast)320s (slow)

140

Q-learning: Basic idea & Car example
s0 = CC (Cool)a0 = fs1 = W
W (warm)

O (overheat)f (fast)320s (slow)

140

r0= 2

Step 4: Update Q(C,f)
We know that Q(C,f)=3 is random and might not be a good value.
But in later steps, we should assume that this is the currently best possible
approximation. We should therefore also not overwrite it completely.

Idea:new value

old value

some number based onwhat just happenedQ-learning: Basic idea & Car example

Should give an approximation of Q(C,f) just based on what happened:• We received a reward r0= 2• We ended in state s1 = W
Question: Based on this information what would be a good guess for Q(C,f)? Assume
that the other values in the table below are good approximations.
Recall: Q(C,f) tells us the expected total reward we get when taking action f in state C(and afterwards following the best possible policy).

a0 = fs0 = C

s1 = W

C (Cool)

W (warm)

O (overheat)f (fast)320s (slow)

140

Q-learning: Basic idea & Car example

s0 = CC (Cool)a0 = fs1 = W
W (warm)

O (overheat)f (fast)320s (slow)

140

For example, if

we get

And the new table
C (Cool)

W (warm)

O (overheat)f (fast)420s (slow)

140From here continue with Step 2…

Q-learningQ-learning + Epsilon-Greedy

Combini & Lecture Example
Goal: Find the nearest Combini to get food. Avoid lecture halls so the professor does
not know that you are actually on campus!

States: 7 * 8 = 56 positions(terminal states:)
Actions:
Rewards:•••

Reaching Combini: +1
Reaching Lecture hall: -1
Making a step to an empty position: -0.1

Optimal policy: Gives the direction we should go ateach state to get to the nearest Combini

Lecture hallCombini

Combini & Lecture Example: Possible optimal policy
Goal: Find the nearest Combini
to get food. Avoid lecture halls
so the professor does notknow that you are actually oncampus!

Optimal policy: Gives thedirection we should go ateach state to get to thenearest Combini

Lecture hallCombini