2 of 60

List of contents for this lecture

Syllabus

Introduction to reinforcement learning

Application examples and a short historic review

Elements of reinforcement learning

Categorizing reinforcement learning agents

Exploration and exploitation

3 of 60

Relevant readings for this lecture

Chapter 1 of “Reinforcement Learning: An Introduction”, Richard S. Sutton and Andrew G. Barto, Second Edition, MIT Press, Cambridge, MA, 2018

4 of 60

Topics to be covered in this course

Introduction to reinforcement learning

Multi-armed bandits

Finite Markov decision processes

Dynamic programming

Monte Carlo methods

Temporal-difference learning

n-step bootstrapping

Planning and learning with tabular methods

On-policy prediction with approximation

On-policy control with approximation

We will cover the first 10 chapters of the textbook:

5 of 60

Textbook

Our main book to follow

Richard S. Sutton and Andrew G. Barto, "Reinforcement learning: An introduction", Second Edition, MIT Press, 2019

Available freely online:

http://incompleteideas.net/book/the-book-2nd.html

6 of 60

Reference books (1)

Dimitri Bertsekas, “A Course on Reinforcement Learning”, Athena Scientific, 2023.

7 of 60

Reference books (2)

Dimitri P. Bertsekas, "Reinforcement learning and Optimal Control", First Edition, Athena Scientific, 2019

8 of 60

Reference books (3)

Lucian Busoniu, Robert Babuska, Bart De Schutter, Damien Ernst, “Reinforcement Learning and Dynamic

Programming Using Function Approximators”, CRC Press, 2010.

9 of 60

Reference books (4)

Shengbo Eben Li, “Reinforcement Learning for Sequential Decision and Optimal Control”, Springer, 2023.

10 of 60

Reference books (5)

Stefano V. Albrecht, Filippos Christianos, Lukas Schäfer, “Multi-Agent Reinforcement Learning:

Foundations and Modern Approaches”, MIT Press, 2024.

11 of 60

Reference books (6)

Laura Graesser and Wah Loon Keng, “Foundations of Deep Reinforcement Learning: Theory and Practice in Python”, Addison-Wesley Professional, 2019.

12 of 60

Some good reinforcement learning courses at other institutions (1)

Introduction to Reinforcement Learning with David Silver

Introduction to Reinforcement Learning with David Silver:

https://www.deepmind.com/learning-resources/introduction-to-reinforcement-learning-with-david-silver

🡺 Both lecture videos and slides are available

13 of 60

Some good reinforcement learning courses at other institutions (2)

Introduction to Reinforcement Learning with David Silver

Reinforcement Learning at Paderborn University:

https://github.com/upb-lea/reinforcement_learning_course_materials

🡺 Both lecture videos and slides are available

14 of 60

Some good reinforcement learning courses at other institutions (3)

Introduction to Reinforcement Learning with David Silver

Reinforcement learning lecture series by DeepMind :

https://www.deepmind.com/learning-resources/reinforcement-learning-lecture-series-2021

🡺 Both lecture videos and slides are available

15 of 60

Some good reinforcement learning courses at other institutions (4)

Introduction to Reinforcement Learning with David Silver

Reinforcement Learning by by Emma Brunskill at Stanford University :

https://web.stanford.edu/class/cs234/

🡺 Both lecture videos and slides are available

16 of 60

Do not forget “Stackexchange” as another online source

https://ai.stackexchange.com

with the tag “Reinforcement learning”

17 of 60

Prerequisites for this course

Basics foundations of machine learning

Fundamental knowledge of probability and statistics

Fundamental knowledge of linear algebra

Control systems background (useful if you have, but will not be a problem if you do not have!)

Proficiency in Python or Matlab

18 of 60

Branches of machine learning

19 of 60

What is reinforcement learning? (1)

The learner is not told which actions to take, but instead must discover which actions yield the most reward by trying them.

Reinforcement learning is the training of machine learning models to make a sequence of decisions in

order to maximize a reward metric through interaction with environment :

20 of 60

What is reinforcement learning? (2)

21 of 60

Key characteristics of reinforcement learning

What makes reinforcement learning different from other machine learning paradigms?

There is no supervisor, only a reward signal

It is data-driven with discrete time steps

Feedback is delayed, not instantaneous

Sequential data stream (not i.i.d. data)

Agent's actions affect the subsequent data it receives

22 of 60

Context around reinforcement learning

Figure: Disciplines of machine learning and the context around reinforcement learning.

(source, W. Kirchgässner, M. Schenke, O. Wallscheid and D. Weber, RL Course Material, Paderborn University, 2020)

Oliver

23 of 60

Many faces of reinforcement learning

Figure: Reinforcement learning and its related domains (source: D. Silver, Reinforcement Learning, 2016)

24 of 60

Methodical origins of reinforcement learning

Ivan Pavlov (1849-1936)

Andrei Markov (1856-1922)

Richard Bellman (1920-1984)

Classical conditioning

Stochastic process

formalism

Dynamic programming

Figure: Big scientists establishing the methodical foundations of reinforcement learning .

(source, derivative of W. Kirchgässner, M. Schenke, O. Wallscheid and D. Weber, RL Course Material, Paderborn University, 2020)

25 of 60

History of reinforcement learning

RL is a huge and very rich field with many interconnections to other areas. For historical development of this amazing field the interested readers are referred to:

Chapter 1.7 of the textbook

The talk “A History of Reinforcement Learning”, by Prof. A.G. Barto (YouTube link)

Survey papers on more recent developments:

Arulkumaran et al., “A Brief Survey of Deep Reinforcement Learning”, arXiv link, 2017

Wang et al., “Deep Reinforcement Learning: A Survey”, journal link, 2022

26 of 60

Application examples of reinforcement learning

Playing games like Go

Self-driving cars

Personalised product recommendation systems

Ad recommendation systems

Personalised chatbot response

Personalized medication dosing

Control of a power station

Making a humanoid robot walk

Automated calibration of engines and other machines

Energy-efficient building control

27 of 60

Reinforcement learning vocabulary (1)

Policy

Action

State

Reward

Return

Value function

Model

Exploration and exploitation

Markov processes

Dynamic programming

RL includes the use of the following vocabulary:

28 of 60

Reinforcement learning vocabulary (2)

In the next slides, some of these vocabulary will be defined mainly “verbally” and their mathematical

definitions will be given in next lectures.

29 of 60

State (1)

30 of 60

State (2)

32 of 60

State space & action space

State space: The state space is the set of all possible states.

Action space: The set of all possible actions the learning agent can take in the environment.

33 of 60

Remark on state and action spaces

Evaluation of the nature of state space and action space (e.g., finite vs infinite, discrete vs

continuous) of a given RL problem should always be one of the the first steps in order to choose

the appropriate solution strategies.

34 of 60

Reward

Definition

A reward signal defines the goal of a reinforcement learning problem. On each time

step, the environment sends to the reinforcement learning agent a single number called

the reward.

Basically, reward indicates how well agent is doing at step t.

The agent’s sole objective is to maximize the total reward it receives over the long run.

In a biological system, we might think of rewards as analogous to the experiences of

pleasure or pain.

The reward signal is the primary basis for altering the policy:

if an action selected by the policy is followed by low reward, then the policy may be changed to select some other action in that situation in the future.

In general, reward signals may be stochastic functions of the state of the environment and the actions taken.

35 of 60

Examples of rewards

Playing games like Go

positive reward for winning a game
negative reward for losing a game

Control of a power station

positive reward for producing power
negative reward for exceeding safety thresholds

Making a humanoid robot walk

positive reward for forward motion
negative reward for falling over

36 of 60

Some remarks on reward

Disturbances (exogenous inputs which cannot be controlled) might introduce stochastic reward components.

Example: A strong wind causing a plane crush

Agent’s learning is strongly dependent on reward variation over time. As a result, designing an effective reward function is very important for successfully applying RL to the given problem.

For a given RL-based learning problem, often there is no predefined way to design the best “reward function”.

37 of 60

Return (1)

Episodic tasks

Episodic tasks are tasks that have a beginning and an end.

Example: games

The return for an episodic task at time step k is defined as the finite sum of random reward variables:

Here, it is assumed that the episode ends at its terminal step k=N.

38 of 60

Return (2)

39 of 60

Some remarks on discounted rewards

(*)

40 of 60

Policy

Definition

41 of 60

Deterministic policy example

Assume that you are a goalkeeper in a football team.

The opposing team wins a penalty.

Your coach instructs you as follows:

If the player taking the penalty shoots with his left foot, you should dive to the left.

On the other hand, if the player taking the penalty shoots with his right foot, you should dive to the right.

(Source: derivative of https://medium.com/@mohannadrateb84/reinforcement-learning-deterministic-policy-vs-stochastic-policy-eabae430916b)

42 of 60

Stochastic policy example

Assume that you are a goalkeeper in a football team.

The opposing team wins a penalty.

Your coach instructs you as follows:

You can dive to the left or left randomly.

(Source: derivative of https://medium.com/@mohannadrateb84/reinforcement-learning-deterministic-policy-vs-stochastic-policy-eabae430916b)

43 of 60

State-value function

Definition

Whereas the reward signal indicates what is good in an immediate sense, a value function

specifies what is good in the long run.

Whereas rewards determine the immediate, intrinsic desirability of environmental states, values determine the long-term desirability of states after taking into account the states that are likely to follow and the rewards available in those states.

For example, a state might always yield a low immediate reward but still have a high value

because it is regularly followed by other states that yield high rewards.

Note: A value function is used to evaluate the goodness/badness of states.

44 of 60

State-action-value (action-value) function

Definition

45 of 60

Rewards versus values

Rewards are in a sense primary, whereas values, as long-term predictions of rewards, are secondary.

Without rewards there could be no values, and the only purpose of estimating values is to

achieve more accumulated reward.

Nevertheless, it is values with which we are most concerned when making and evaluating

decisions.

Action choices are made based on value judgments:

we seek actions that bring about states of highest value, not highest reward, because these

actions obtain the greatest amount of reward for us over the long run.

Unfortunately, it is much harder to determine values than it is to determine rewards.

In fact, the most important component of almost all reinforcement learning algorithms we consider is a method for efficiently estimating values.

46 of 60

Model (1)

Definition

A model predicts what the environment will do for a given input.

Examples (of models for probabilistic transitions):

Note: Both of the above forms will be used in the lectures.

Data-based model fitting is a learning problem of its own called “system identification”.

47 of 60

Model (2)

Models are used for planning: “planning” is coming up with future actions before they are

actually experienced (simulated experience) .

Methods for solving reinforcement learning problems that use models and planning are called “model-based methods”, as opposed to simpler “model-free” methods that are explicitly trial-and-error learners—viewed as almost the opposite of planning.

Modern reinforcement learning spans the spectrum from low-level, trial-and-error learning to

high-level, deliberative planning.

48 of 60

Time to see a practical example

Next, we will show an example solved by different RL algorithms...

49 of 60

Maze example

Objective: Move from “Start” to “Goal” in minimum time

(Source: D. Silver, Reinforcement Learning, 2016)

Note: The problem is a deterministic problem.

Fig: maze setup for RL problem

50 of 60

Maze example: policy-based solution

Fig: policy-based solution for the maze problem

(Source: D. Silver, Reinforcement Learning, 2016)

Key characteristics:

51 of 60

Maze example: value function-based solution

Fig: value function-based solution for the maze problem

(Source: D. Silver, Reinforcement Learning, 2016)

Key characteristics:

52 of 60

Maze example: model evaluation-based solution

Key characteristics:

Fig: model evaluation-based solution for the maze problem.

(Source: D. Silver, Reinforcement Learning, 2016)

53 of 60

More general framework of reinforcement learning

54 of 60

Fully/partially observable environments

Full observability: agent directly observes environment state. I.e.,

Partial observability: agent indirectly observes environment state. I.e.,

Example: A poker playing agent only observes public cards.

55 of 60

Exploration and exploitation

In reinforcement learning, in general, environment is initially unknown.

(if we have no perfect model of it)

Reinforcement learning is like trial-and-error learning.

The agent should discover a good policy:

from its experiences of the environment

without losing too much reward along the way

Exploration finds more information about the environment.

Exploitation exploits known information to maximise reward.

It is usually important to explore as well as exploit by having

a split between both strategies!

(source, W. Kirchgässner, M. Schenke,

O. Wallscheid and D. Weber, RL Course Material,

Paderborn University, 2020)

Fig: The exploration- exploitation dilemma

56 of 60

Examples of exploration and exploitation

Restaurant selection

Exploitation: Go to your favourite restaurant
Exploration: Try a new restaurant

Online banner advertisements

Exploitation: Show the most successful advert
Exploration: Show a different advert

Oil drilling

Exploitation: Drill at the best known location
Exploration: Drill at a new location

Game playing

Exploitation: Play the move you believe is the best
Exploration: Play an experimental move

57 of 60

Categorizing reinforcement learning agents (1)

Value-based

No policy (implicit)
Value function

Policy-based

Policy
No value function

Actor-Critic

Policy
Value function

58 of 60

Categorizing reinforcement learning agents (2)

Model-free

Policy and/or value function
No model

Model-based

Policy and/or value function
Model

59 of 60

Reinforcement agent taxonomy

Fig: RL categories (source, D. Silver, Reinforcement Learning, 2016)

60 of 60

References �(utilized for preparation of lecture notes or Matlab code)

1 of 60

2 of 60

3 of 60

4 of 60

5 of 60

6 of 60

7 of 60

8 of 60

9 of 60

10 of 60

11 of 60

12 of 60

13 of 60

14 of 60

15 of 60

16 of 60

17 of 60

18 of 60

19 of 60

20 of 60

21 of 60

22 of 60

23 of 60

24 of 60

25 of 60

26 of 60

27 of 60

28 of 60

29 of 60

30 of 60

31 of 60

32 of 60

33 of 60

34 of 60

35 of 60

36 of 60

37 of 60

38 of 60

39 of 60

40 of 60

41 of 60

42 of 60

43 of 60

44 of 60

45 of 60

46 of 60

47 of 60

48 of 60

49 of 60

50 of 60

51 of 60

52 of 60

53 of 60

54 of 60

55 of 60

56 of 60

57 of 60

58 of 60

59 of 60

60 of 60