Lecture 1��Overview of introductory reinforcement learning

1

Instructor: Ercan Atam

Course: DSAI 642- Advanced Reinforcement Learning

2

List of contents for this lecture

​

​

• Syllabus

​

• Overview of introductory reinforcement learning

​

3

Relevant readings for this lecture

​

​

• My DSAI542 (Introductory RL) lecture slides:

​

​

https://sites.google.com/view/ercanatam/teaching/past-teaching/dsai-542?authuser=0

​

4

Branches of machine learning

5

What is reinforcement learning? (1)

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

order to maximize a reward-based metric through interaction with environment :

​

​

​

​

​

​

​

​

​

​

​

​

​

6

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.

7

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.

8

Return (2)

9

Some remarks on discounted rewards

(*)

10

State-value function

• 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.

11

State-action-value (action-value) function

12

Model (1)

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”.

13

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.

​

14

More general framework of reinforcement learning

15

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.

16

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

17

Categorizing reinforcement learning agents (1)

• Value-based
• No policy (implicit)
• Value function

​

​

• Policy-based
• Policy
• No value function

​

​

• Actor-Critic
• Policy
• Value function

18

Categorizing reinforcement learning agents (2)

• Model-free
• Policy and/or value function
• No model

​

​

​

• Model-based
• Policy and/or value function
• Model

19

Reinforcement agent taxonomy

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

20

Markov Decision Processes (MDPs)

21

• The goal of the agent is to find a way of controlling the system (finding a strategy or plan), which is called a policy, in order to maximize the expected value of the return at every time step.

We differentiate between two kinds of policies:

Remarks:

• A policy fully defines the behavior of an agent.
• MDP policies depend on the current state (not the history). I.e., policies are stationary (time-independent):

​

Policy (1)

22

Value functions for MDPs

23

The state-value function can be decomposed into immediate reward plus discounted value of successor state:

Bellman expectation equation for state-value function of MDPs

24

The action-value function can similarly be decomposed as:

Bellman expectation equation for action-value function of MDPs

25

Summary Bellman expectation equations and backup diagrams

26

Optimal policy in an MDP

27

Deterministic optimal policy in an MDP

28

Summary of “Bellman Optimality Equations” and backup diagrams

29

Monte Carlo methods (1)

​

​

• That is, we assume that experience is divided into episodes, and that all episodes eventually

terminate no matter what actions are selected.

​

​

​

• In Monte Carlo methods, only on the completion of an episode value function estimates and

policies are changed.

​

​

​

• Monte Carlo methods can thus be incremental in an episode-by-episode sense, but not in a

step-by-step (online) sense.

30

Monte Carlo methods (2)

​

• Monte Carlo methods can be used in two ways:

​

• Model-free: No model necessary and still attains optimality.

​

• Simulated: Needs only a simulation, not a “full” model. Simulation model needs only to generate sample transitions, not the complete probability distribution.

​

​

31

Monte Carlo methods (3)

32

Monte Carlo methods vs dynamic programming

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

Dynamic programming:

​

• Model-based prediction and control

​

• Planning for known MDPs

​

​

Monte Carlo methods:

​

• Model-free prediction and control

​

• Estimating value functions and optimize policies for unknown MDPs

​

• But: still assuming a finite MDP structure (or problems close to that)

​

• They represent, in general, a broad class of computational algorithms relying on repeated random sampling to obtain numerical results

33

Monte Carlo prediction (1)

34

Monte Carlo prediction (2)

35

Monte Carlo prediction (3)

36

First-visit and every-visit MC prediction methods

Definition: first-visit MC prediction method

In the first-visit MC prediction method, when you are at state “s” you start to sum the rewards

until the end of the episode.

​

If the state “s” appears again during a transition, you ignore re-appearance and don't start

counting again. For state “s”, we have maximum one sum per episode.

​

Then, the value of state “s” is taken as the average of the sums corresponding to all episodes

where “s” appears.

In the every-visit MC prediction method, for every re-appearance of “s” in an episode you

start a new sum.

​

For state “s”, we can have multiple sums per episode.

​

Then, the value of state “s” is taken as the average of all sums corresponding to all episodes

where “s” appears.

37

Pseudocode for every-visit MC prediction

​

38

Pseudocode for first-visit MC prediction

​

39

Incremental implementation (1)

​

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

40

Incremental implementation (2)

​

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

41

Statistical properties of MC-based prediction (1)

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

42

Statistical properties of MC-based prediction (2)

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

• State-value estimates for each state are independent.

​

​

​

• One estimate does not rely on the estimate of other states (no bootstrapping compared to DP).

​

​

​

• This makes MC particularly attractive when one requires state-value knowledge of only one or few states.

​

• Hence, generating episodes starting from the state(s) of interest.

43

​

• Whereas the DP diagram shows all possible transitions, the Monte Carlo diagram shows only those sampled on the episodes.

​

​

• MC goes all the way to the end of episodes (whereas, DP includes only one-step transition).

​

Backup diagrams: DP vs MC

​

44

​

• With a model, state values alone are sufficient to improve an existing policy: one simply looks ahead

one step and chooses whichever action leads to the best combination of reward and next state, as we

did in the DP lectures of the RL course:

​

​

​

​

​

​

​

Monte Carlo estimation of action values (1)

45

Monte Carlo estimation of action values (2)

46

Remarks:

Monte Carlo estimation of action values (3)

47

Complications in Monte Carlo estimation of action values (1)

48

Complications in Monte Carlo estimation of action values (2)

​

​

A must:

​

• For policy evaluation to work for action values, instead of just one action at a state, we must assure continual exploration for all other possible actions at that state as well!

​

49

​

• One option for assuring continual exploration is by specifying that the episodes start in a state–action

pair, and that every pair has a nonzero probability of being selected as the start. This assumption is

called “exploring starts”.

​

• The assumption of exploring starts guarantees that all state–action pairs will be visited an infinite

number of times in the limit of an infinite number of episodes.

​

• But the assumption of exploring starts doesn’t always work. For example, if we learn directly from the

interaction with the environment, exploring starts may not be possible to satisfy.

​

• A more common way to go about it, is to only consider stochastic policies where the probability of every

action in every state is non-zero.

​

• We will discuss two important variants of this approach later on.

​

• For now, we retain the assumption of exploring starts and complete the presentation of a full MC control

method.

A remedy to complications in Monte Carlo estimation of action values

50

Objective: To use Monte Carlo estimation methods for approximation of optimal policies under the assumption of exploring starts.

Monte Carlo control with exploring starts (1)

51

First, we will consider the MC version of classical policy iteration:

Monte Carlo control with exploring starts (2)

52

Monte Carlo control with exploring starts (3)

53

Monte Carlo control with exploring starts (4)

54

​

• Note that we made two unlikely assumptions in order to easily obtain the guarantee of convergence for the Monte Carlo methods:

​

• Assumption 1: episodes have exploring starts.

​

• Assumption 2: policy evaluation could be done with an infinite number of episodes.

​

​

​

• To obtain a “practical” algorithm, we will have to remove both assumptions. We postpone the removal of the first assumption (exploring starts) until later. I.e., we keep Assumption1 for a while.

​

​

• Next, we will relax Assumption 2.

​

​

Monte Carlo control with exploring starts (5)

55

Monte Carlo control with exploring starts (6)

56

• For Monte Carlo-based policy iteration, it is natural to alternate between policy evaluation and

policy improvement on an episode-by-episode basis.

​

​

​

• After each episode, the observed returns are used for policy evaluation, and then the policy is

improved at all the states visited in the episode.

​

​

​

• A complete algorithm based on this principle is given next.

Monte Carlo control with exploring starts (7)

57

First-visit MC control with exploring starts algorithm

58

​

​

Advantages of MC learning methods

​

59

59

MC control without exploring starts: Behavior and Target policies

60

Note: The Monte Carlo control with exploring starts method is an example of an on-policy method.

​

MC control without exploring starts: On-policy vs Off-policy methods

​

61

Before developing a “MC control without exploring starts” approach, we need some definitions...

Note: In on-policy control methods without exploring starts, the soft policy is gradually shifted closer

and closer to a deterministic optimal policy.

​

MC control without ES: on-policy methods (1)

​

62

​

MC control without ES: on-policy methods (2)

​

63

​

MC control without ES: on-policy methods (3)

​

64

​

We need a mechanism to derive “target policy” from “behaviour policy”

​

Derive/test new (preferably optimal) policies from old data: Evaluate a target policy using logs from a

different policy—no risky deployments.

Fix distribution mismatch: Reweight samples from the behavior policy so that estimates reflect the target policy.

Reuse data efficiently: Learn from past experience by applying “adaptation” ratios.

All these call for “Importance Sampling”.

65

​

Importance sampling (1)

​

66

​

Importance sampling (2)

​

67

​

Importance sampling (3)

​

68

• Recall the definition of state-value function:

• In DP methods:

• In MC methods:

Note that the general form of MC-based every-visit incremental state-value update rule suitable for

non-stationary environments is:

​

​

TD prediction (1)

69

This new every-visit incremental state-value update rule is called TD learning rule:

TD prediction (2)

70

TD prediction vs MC prediction

71

​

One-step TD prediction

​

72

​

TD off-policy control: Q-learning (1)

​

Remember the “Bellman Optimality Equation” for the state-action value function:

For a deterministic optimal policy (remember that it always exists for an MDP), we have:

73

Update rule:

​

TD off-policy control: Q-learning (2)

​

Q-learning is based on approximating the optimal action-value function iteratively by making use of the “Bellman Optimality Equation” corresponding to the action-value function.

74

​

Requirements for Q-learning

​

75

​

Q-learning algorithm

​