Nagoya University, Fall 2023

Lecture 8
Reinforcement Learning: Q-Learningth period
This week Tutorial: Wednesday
29thNov.
5KomNov
6ᵗʰ
30th
Thursdayhttps://www.henrikbachmann.com/mml2023.html

OverviewSupervised learning
Classification (discrete output)

Output = category (e.g. “dog”, “cat” or “1”,”2”,…,”9”)”2”
Handwriting recognition

Regression (continuous output)

Output = real number (like “price”, “weight”,…)
Size: 70#!
Rooms: 3

Examples in this lecture so far• Linear regression (Tebasaki)• Logistic regression (Passing exam)• Neural Network (digit recognition)
90.000 Yen

Apartment price prediction

Supervised learning is not always possible•••••

Games: Chess, Go, RTS,…
Movement of robots
Selfdriving cars
Google data center cooling….

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, …)Reinforcement learning: Walking example

https://www.youtube.com/watch?v=gn4nRCC9TwQ

Another example: https://www.youtube.com/watch?v=L_4BPjLBF4E

Markov decision process

Markov decision process

Interpretation:

Markov decision process: ExampleSA

TCW sic

REINEls

VIEL

YamPermeatedf
IWF 01RUFF

0OF

TIC FINI

1

Markov decision process: Dynamics

Markov decision process: Dynamics

Total reward: Car example
8WE
Er

RCGF.CI

0.1

oRICA
0

So 51,52
aoia.azf

IR WifO

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.

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 maximal
value at each state.

Optimal policy

Optimal policy

Optimal policy
TECfTLW

5IFOS

Optimal policy & State-action value function

QIS.TTIncarinexample

QK.SE

TTICiSOIRICis OEEEfRii

JIEHIC

Optimal policy & State-action value function

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

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)State
W (warm)

O (overheat)f (fast)3

20s (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)

1

40

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)320s (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)

1

40

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 = Cs1 = 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)

1

40

For example, if

we get

And the new table
C (Cool)

W (warm)

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

1

40

From 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: -1Making 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 hall
Combini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 hall
Combini