0% found this document useful (0 votes)

10 views227 pages

Value Function Methods in AI

The document outlines Lecture 8 on Value Function Methods, focusing on algorithms for state value estimation, including Sarsa and Q-learning with function approximation. It discusses the transition from tabular representation to function representation, highlighting advantages and disadvantages in handling state and action values. The lecture also emphasizes the importance of storage efficiency and generalization ability in large or continuous state spaces.

Uploaded by

liang

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

10 views227 pages

Value Function Methods in AI

Uploaded by

liang

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

Lecture 8: Value Function Methods

Shiyu Zhao

Department of Artificial Intelligence

Westlake University
Outline

Algorithms/Methods

Chapter 4: Chapter 5: Chapter 6:

with model Stochastic
Value Iteration & to Monte Carlo
Policy Iteration Methods Approximation
without model

Chapter 7:
Chapter 3: Temporal-Difference
Chapter 2: Methods
Bellman Optimality
Bellman Equation
Equation
tabular representation
to
function representation
Chapter 1:
Basic Concepts
Chapter 8:
Value Function
Fundamental tools
Methods

Chapter 10: policy-based

Chapter 9:
Actor-Critic plus Policy Gradient
Methods value-based Methods

Shiyu Zhao 1 / 69
Outline

1 Motivating examples: from table to function

2 Algorithm for state value estimation

Objective function
Optimization algorithms
Selection of function approximators
Illustrative examples
Summary of the story
Theoretical analysis (optional)

3 Sarsa with function approximation

4 Q-learning with function approximation

5 Deep Q-learning

6 Summary

Shiyu Zhao 2 / 69
Outline

1 Motivating examples: from table to function

2 Algorithm for state value estimation

Objective function
Optimization algorithms
Selection of function approximators
Illustrative examples
Summary of the story
Theoretical analysis (optional)

3 Sarsa with function approximation

4 Q-learning with function approximation

5 Deep Q-learning

6 Summary

Shiyu Zhao 3 / 69
Motivating examples: from table to function

So far in this book, state and action values are represented by tables.

• For example, state value:

State s1 s2 ··· sn
Value vπ (s1 ) vπ (s2 ) ··· vπ (sn )

• For example, action value:

a1 a2 a3 a4 a5
s1 qπ (s1 , a1 ) qπ (s1 , a2 ) qπ (s1 , a3 ) qπ (s1 , a4 ) qπ (s1 , a5 )
. . . . . .
. . . . . .
. . . . . .
s9 qπ (s9 , a1 ) qπ (s9 , a2 ) qπ (s9 , a3 ) qπ (s9 , a4 ) qπ (s9 , a5 )

• Advantage: intuitive and easy to analyze

• Disadvantage: difficult to handle large or continuous state or action spaces.
Two aspects: 1) storage; 2) generalization ability

Shiyu Zhao 4 / 69
Motivating examples: from table to function

So far in this book, state and action values are represented by tables.

• For example, state value:

State s1 s2 ··· sn
Value vπ (s1 ) vπ (s2 ) ··· vπ (sn )

• For example, action value:

• Advantage: intuitive and easy to analyze

• Disadvantage: difficult to handle large or continuous state or action spaces.
Two aspects: 1) storage; 2) generalization ability

Shiyu Zhao 4 / 69
Motivating examples: from table to function

So far in this book, state and action values are represented by tables.

• For example, state value:

State s1 s2 ··· sn
Value vπ (s1 ) vπ (s2 ) ··· vπ (sn )

• For example, action value:

• Advantage: intuitive and easy to analyze

• Disadvantage: difficult to handle large or continuous state or action spaces.
Two aspects: 1) storage; 2) generalization ability

Shiyu Zhao 4 / 69
Motivating examples: from table to function

So far in this book, state and action values are represented by tables.

• For example, state value:

State s1 s2 ··· sn
Value vπ (s1 ) vπ (s2 ) ··· vπ (sn )

• For example, action value:

• Advantage: intuitive and easy to analyze

• Disadvantage: difficult to handle large or continuous state or action spaces.
Two aspects: 1) storage; 2) generalization ability

Shiyu Zhao 4 / 69
Motivating examples: from table to function

So far in this book, state and action values are represented by tables.

• For example, state value:

State s1 s2 ··· sn
Value vπ (s1 ) vπ (s2 ) ··· vπ (sn )

• For example, action value:

• Advantage: intuitive and easy to analyze

• Disadvantage: difficult to handle large or continuous state or action spaces.
Two aspects: 1) storage; 2) generalization ability

Shiyu Zhao 4 / 69
Motivating examples: from table to function

Consider an example:
• There are n states: s1 , . . . , sn .
• The state values are vπ (s1 ), . . . , vπ (sn ), where π is a given policy.
• n is very large!
• We hope to use a simple curve to approximate these values.

Shiyu Zhao 5 / 69
Motivating examples: from table to function

For example, we can use a simple straight line to fit the dots.

v̂(s) = as + b
v̂(s)

s1 s2 s3 s4 · · · sn s

Suppose the equation of the straight line is

" #
a
v̂(s, w) = as + b = [s, 1] = φT (s)w
| {z } b
φT (s) | {z }
w

w is the parameter vector; φ(s) the feature vector of s; v̂(s, w) is linear in w.

Shiyu Zhao 6 / 69
Motivating examples: from table to function

For example, we can use a simple straight line to fit the dots.

v̂(s) = as + b
v̂(s)

s1 s2 s3 s4 · · · sn s

Suppose the equation of the straight line is

" #
a
v̂(s, w) = as + b = [s, 1] = φT (s)w
| {z } b
φT (s) | {z }
w

w is the parameter vector; φ(s) the feature vector of s; v̂(s, w) is linear in w.

Shiyu Zhao 6 / 69
Motivating examples: from table to function

For example, we can use a simple straight line to fit the dots.

v̂(s) = as + b
v̂(s)

s1 s2 s3 s4 · · · sn s

Suppose the equation of the straight line is

" #
a
v̂(s, w) = as + b = [s, 1] = φT (s)w
| {z } b
φT (s) | {z }
w

w is the parameter vector; φ(s) the feature vector of s; v̂(s, w) is linear in w.

Shiyu Zhao 6 / 69
Motivating examples: from table to function

For example, we can use a simple straight line to fit the dots.

v̂(s) = as + b
v̂(s)

s1 s2 s3 s4 · · · sn s

Suppose the equation of the straight line is

" #
a
v̂(s, w) = as + b = [s, 1] = φT (s)w
| {z } b
φT (s) | {z }
w

w is the parameter vector; φ(s) the feature vector of s; v̂(s, w) is linear in w.

Shiyu Zhao 6 / 69
Motivating examples: from table to function

Difference between the tabular and function methods:

Difference 1: How to retrieve the value of a state

• When the values are represented by a table, we can directly read the value in
the table.
• When the values are represented by a function, we need to input the state
index s into the function and calculate the function value.

For example, s → φ(s) → φT (s)w = v̂(s, w)

- Benefit: storage. We do not need to store |S| state values. We only need
to store a lower-dimensional w.

Shiyu Zhao 7 / 69
Motivating examples: from table to function

Difference between the tabular and function methods:

Difference 1: How to retrieve the value of a state

For example, s → φ(s) → φT (s)w = v̂(s, w)

- Benefit: storage. We do not need to store |S| state values. We only need
to store a lower-dimensional w.

Shiyu Zhao 7 / 69
Motivating examples: from table to function

Difference between the tabular and function methods:

Difference 1: How to retrieve the value of a state

For example, s → φ(s) → φT (s)w = v̂(s, w)

- Benefit: storage. We do not need to store |S| state values. We only need
to store a lower-dimensional w.

Shiyu Zhao 7 / 69
Motivating examples: from table to function

Difference between the tabular and function methods:

Difference 1: How to retrieve the value of a state

s v̂(s, w)
w

function

For example, s → φ(s) → φT (s)w = v̂(s, w)

- Benefit: storage. We do not need to store |S| state values. We only need
to store a lower-dimensional w.

Shiyu Zhao 7 / 69
Motivating examples: from table to function

Difference between the tabular and function methods:

Difference 1: How to retrieve the value of a state

s v̂(s, w)
w

function

For example, s → φ(s) → φT (s)w = v̂(s, w)

- Benefit: storage. We do not need to store |S| state values. We only need
to store a lower-dimensional w.

Shiyu Zhao 7 / 69
Motivating examples: from table to function

Difference between the tabular and function methods:

Difference 1: How to retrieve the value of a state

s v̂(s, w)
w

function

For example, s → φ(s) → φT (s)w = v̂(s, w)

- Benefit: storage. We do not need to store |S| state values. We only need
to store a lower-dimensional w.

Shiyu Zhao 7 / 69
Motivating examples: from table to function

Difference between the tabular and function methods:

Difference 2: How to update the value of a state

• When the values are represented by a table, we can directly rewrite the value
in the table.
• When the values are represented by a function, we must update w to change
the values indirectly.
- How to update w will be addressed in detail later.

Shiyu Zhao 8 / 69
Motivating examples: from table to function

Difference between the tabular and function methods:

Difference 2: How to update the value of a state

Shiyu Zhao 8 / 69
Motivating examples: from table to function

Difference between the tabular and function methods:

Difference 2: How to update the value of a state

Shiyu Zhao 8 / 69
Motivating examples: from table to function

Difference between the tabular and function methods:

Difference 2: How to update the value of a state

Shiyu Zhao 8 / 69
Motivating examples: from table to function

Difference between the tabular and function methods:

Difference 2: How to update the value of a state

v̂(s) v̂(s)
update v̂(s3 )

s1 s2 s3 s s1 s2 s3 s

(a) Tabular method

v̂(s) v̂(s)
update w for s3

s1 s2 s3 s s1 s2 s3 s

(b) Function method

Benefit: generalization ability. When we update v̂(s, w) by changing w, the

values of the neighboring states are also changed.
Shiyu Zhao 9 / 69
Motivating examples: from table to function

Difference between the tabular and function methods:

Difference 2: How to update the value of a state

v̂(s) v̂(s)
update v̂(s3 )

s1 s2 s3 s s1 s2 s3 s

(a) Tabular method

v̂(s) v̂(s)
update w for s3

s1 s2 s3 s s1 s2 s3 s

(b) Function method

Benefit: generalization ability. When we update v̂(s, w) by changing w, the

values of the neighboring states are also changed.
Shiyu Zhao 9 / 69
Motivating examples: from table to function

The benefits are not free. It comes with a cost: the state values can not be
represented accurately. This is why this method is called approximation.

We can fit the points more precisely using high-order curves:

 
a
v̂(s, w) = as2 + bs + c = [s2 , s, 1]  b  = φT (s)w.
 
| {z }
φT (s) c
| {z }
w

In this case,
• The dimensions of w and φ(s) increase; the values may be fitted more
accurately.
• Although v̂(s, w) is nonlinear in s, it is linear in w. The nonlinearity is
contained in φ(s).

Shiyu Zhao 10 / 69
Motivating examples: from table to function

The benefits are not free. It comes with a cost: the state values can not be
represented accurately. This is why this method is called approximation.

We can fit the points more precisely using high-order curves:

 
a
v̂(s, w) = as2 + bs + c = [s2 , s, 1]  b  = φT (s)w.
 
| {z }
φT (s) c
| {z }
w

Shiyu Zhao 10 / 69
Motivating examples: from table to function

The benefits are not free. It comes with a cost: the state values can not be
represented accurately. This is why this method is called approximation.

We can fit the points more precisely using high-order curves:

 
a
v̂(s, w) = as2 + bs + c = [s2 , s, 1]  b  = φT (s)w.
 
| {z }
φT (s) c
| {z }
w

Shiyu Zhao 10 / 69
Motivating examples: from table to function

The benefits are not free. It comes with a cost: the state values can not be
represented accurately. This is why this method is called approximation.

We can fit the points more precisely using high-order curves:

 
a
v̂(s, w) = as2 + bs + c = [s2 , s, 1]  b  = φT (s)w.
 
| {z }
φT (s) c
| {z }
w

Shiyu Zhao 10 / 69
Motivating examples: from table to function

Quick summary:
• Idea: Approximate the state and action values using parameterized
functions: v̂(s, w) ≈ vπ (s) where w ∈ Rm is the parameter vector.
• Key difference: How to retrieve and change the value of v(s)
• Advantages:
1) Storage: The dimension of w may be much smaller than |S|.
2) Generalization: When a state s is visited, the parameter w is updated
so that the values of some other unvisited states can also be updated.

Shiyu Zhao 11 / 69
Motivating examples: from table to function

Shiyu Zhao 11 / 69
Outline

1 Motivating examples: from table to function

2 Algorithm for state value estimation

Objective function
Optimization algorithms
Selection of function approximators
Illustrative examples
Summary of the story
Theoretical analysis (optional)

3 Sarsa with function approximation

4 Q-learning with function approximation

5 Deep Q-learning

6 Summary

Shiyu Zhao 12 / 69
Outline

1 Motivating examples: from table to function

2 Algorithm for state value estimation

Objective function
Optimization algorithms
Selection of function approximators
Illustrative examples
Summary of the story
Theoretical analysis (optional)

3 Sarsa with function approximation

4 Q-learning with function approximation

5 Deep Q-learning

6 Summary

Shiyu Zhao 13 / 69
Objective function

Introduce in a more formal way:

• Let vπ (s) and v̂(s, w) be the true state value and the estimated state value,
respectively.
• Our goal is to find an optimal w so that v̂(s, w) can best approximate vπ (s)
for every s.
• This is a policy evaluation problem. Later we will extend to policy
improvement.

To find the optimal w, we need two steps.

• The first step is to define an objective function.
• The second step is to derive algorithms for optimizing the objective function.

Shiyu Zhao 14 / 69
Objective function

Introduce in a more formal way:

To find the optimal w, we need two steps.

• The first step is to define an objective function.
• The second step is to derive algorithms for optimizing the objective function.

Shiyu Zhao 14 / 69
Objective function

Introduce in a more formal way:

To find the optimal w, we need two steps.

• The first step is to define an objective function.
• The second step is to derive algorithms for optimizing the objective function.

Shiyu Zhao 14 / 69
Objective function

Introduce in a more formal way:

To find the optimal w, we need two steps.

• The first step is to define an objective function.
• The second step is to derive algorithms for optimizing the objective function.

Shiyu Zhao 14 / 69
Objective function

Introduce in a more formal way:

To find the optimal w, we need two steps.

• The first step is to define an objective function.
• The second step is to derive algorithms for optimizing the objective function.

Shiyu Zhao 14 / 69
Objective function

Introduce in a more formal way:

To find the optimal w, we need two steps.

• The first step is to define an objective function.
• The second step is to derive algorithms for optimizing the objective function.

Shiyu Zhao 14 / 69
Objective function

Introduce in a more formal way:

To find the optimal w, we need two steps.

• The first step is to define an objective function.
• The second step is to derive algorithms for optimizing the objective function.

Shiyu Zhao 14 / 69
Objective function

The objective function is

J(w) = E[(vπ (S) − v̂(S, w))2 ].

• Our goal is to find the best w that can minimize J(w).

• The expectation is with respect to the random variable S ∈ S.
What is the probability distribution of S?
- This is new. We have not discussed the probability distribution of states
so far.
- There are several ways to define the probability distribution of S.

Shiyu Zhao 15 / 69
Objective function

The objective function is

J(w) = E[(vπ (S) − v̂(S, w))2 ].

• Our goal is to find the best w that can minimize J(w).

Shiyu Zhao 15 / 69
Objective function

The objective function is

J(w) = E[(vπ (S) − v̂(S, w))2 ].

• Our goal is to find the best w that can minimize J(w).

Shiyu Zhao 15 / 69
Objective function

The objective function is

J(w) = E[(vπ (S) − v̂(S, w))2 ].

• Our goal is to find the best w that can minimize J(w).

Shiyu Zhao 15 / 69
Objective function

The objective function is

J(w) = E[(vπ (S) − v̂(S, w))2 ].

• Our goal is to find the best w that can minimize J(w).

Shiyu Zhao 15 / 69
Objective function

The first way is to use a uniform distribution.

• That is to treat all the states to be equally important by setting the
probability of each state as 1/|S|.
• In this case, the objective function becomes
1 X
J(w) = E[(vπ (S) − v̂(S, w))2 ] = (vπ (s) − v̂(s, w))2 .
|S| s∈S

• Drawback:
- The states may not be equally important. For example, some states may
be rarely visited by a policy. Hence, this way does not consider the real
dynamics of the Markov process under the given policy.

Shiyu Zhao 16 / 69
Objective function

The first way is to use a uniform distribution.

Shiyu Zhao 16 / 69
Objective function

The first way is to use a uniform distribution.

Shiyu Zhao 16 / 69
Objective function

The first way is to use a uniform distribution.

Shiyu Zhao 16 / 69
Objective function

The second way is to use the stationary distribution.

• Stationary distribution is an important concept that will be frequently used
in this course. It describes the long-run behavior of a Markov process.
• Let {dπ (s)}s∈S denote the stationary distribution of the Markov process
P
under policy π. By definition, dπ (s) ≥ 0 and s∈S dπ (s) = 1.
• The objective function can be rewritten as
X
J(w) = E[(vπ (S) − v̂(S, w))2 ] = dπ (s)(vπ (s) − v̂(s, w))2 .
s∈S

This function is a weighted squared error.

• Since more frequently visited states have higher values of dπ (s), their weights
in the objective function are also higher than those rarely visited states.

Shiyu Zhao 17 / 69
Objective function

The second way is to use the stationary distribution.

This function is a weighted squared error.

• Since more frequently visited states have higher values of dπ (s), their weights
in the objective function are also higher than those rarely visited states.

Shiyu Zhao 17 / 69
Objective function

The second way is to use the stationary distribution.

This function is a weighted squared error.

• Since more frequently visited states have higher values of dπ (s), their weights
in the objective function are also higher than those rarely visited states.

Shiyu Zhao 17 / 69
Objective function

The second way is to use the stationary distribution.

This function is a weighted squared error.

• Since more frequently visited states have higher values of dπ (s), their weights
in the objective function are also higher than those rarely visited states.

Shiyu Zhao 17 / 69
Objective function

The second way is to use the stationary distribution.

This function is a weighted squared error.

• Since more frequently visited states have higher values of dπ (s), their weights
in the objective function are also higher than those rarely visited states.

Shiyu Zhao 17 / 69
Objective function – Stationary distribution

More explanation about stationary distribution:

• Distribution: Distribution of the state
• Stationary: Long-run behavior
• Summary: after the agent runs a long time following a policy, the probability
that the agent is at any state can be described by this distribution.
Remarks:
• Stationary distribution is also called steady-state distribution, or limiting
distribution.
• It is critical to understand the value function method.
• It is also important for the policy gradient method in the next lecture.

Shiyu Zhao 18 / 69
Objective function – Stationary distribution

More explanation about stationary distribution:

Shiyu Zhao 18 / 69
Objective function – Stationary distribution

More explanation about stationary distribution:

Shiyu Zhao 18 / 69
Objective function – Stationary distribution

More explanation about stationary distribution:

Shiyu Zhao 18 / 69
Objective function - Stationary distribution

Illustrative example:
• Given a policy shown in the figure.
• Let nπ (s) denote the number of times that s has been visited in a very long
episode generated by π.
• Then, dπ (s) can be approximated by

nπ (s)
dπ (s) ≈ P
s0 ∈S nπ (s0 )

1 2

Shiyu Zhao 19 / 69
Objective function - Stationary distribution

nπ (s)
dπ (s) ≈ P
s0 ∈S nπ (s0 )

1 2

Shiyu Zhao 19 / 69
Objective function - Stationary distribution

nπ (s)
dπ (s) ≈ P
s0 ∈S nπ (s0 )

1 2
0.8

Percentage of each state visited

0.6
1
s1
s2
0.4
s3
s4

0.2
2

0
0 200 400 600 800 1000
Step index

Figure: Long-run behavior of an -greedy policy with = 0.5.

Shiyu Zhao 19 / 69
Objective function - Stationary distribution

The converged values can be predicted because they are the entries of dπ :

dTπ = dTπ Pπ

For this example, we have Pπ as

 
0.3 0.1 0.6 0
 0.1 0.3 0 0.6 
Pπ =  .
 
 0.1 0 0.3 0.6 
0 0.1 0.1 0.8

It can be calculated that the left eigenvector for the eigenvalue of one is
h iT
dπ = 0.0345, 0.1084, 0.1330, 0.7241

A comprehensive introduction can be found in my book.

Shiyu Zhao 20 / 69
Objective function - Stationary distribution

The converged values can be predicted because they are the entries of dπ :

dTπ = dTπ Pπ

For this example, we have Pπ as

 
0.3 0.1 0.6 0
 0.1 0.3 0 0.6 
Pπ =  .
 
 0.1 0 0.3 0.6 
0 0.1 0.1 0.8

It can be calculated that the left eigenvector for the eigenvalue of one is
h iT
dπ = 0.0345, 0.1084, 0.1330, 0.7241

A comprehensive introduction can be found in my book.

Shiyu Zhao 20 / 69
Objective function - Stationary distribution

The converged values can be predicted because they are the entries of dπ :

dTπ = dTπ Pπ

For this example, we have Pπ as

 
0.3 0.1 0.6 0
 0.1 0.3 0 0.6 
Pπ =  .
 
 0.1 0 0.3 0.6 
0 0.1 0.1 0.8

It can be calculated that the left eigenvector for the eigenvalue of one is
h iT
dπ = 0.0345, 0.1084, 0.1330, 0.7241

A comprehensive introduction can be found in my book.

Shiyu Zhao 20 / 69
Objective function - Stationary distribution

The converged values can be predicted because they are the entries of dπ :

dTπ = dTπ Pπ

For this example, we have Pπ as

 
0.3 0.1 0.6 0
 0.1 0.3 0 0.6 
Pπ =  .
 
 0.1 0 0.3 0.6 
0 0.1 0.1 0.8

It can be calculated that the left eigenvector for the eigenvalue of one is
h iT
dπ = 0.0345, 0.1084, 0.1330, 0.7241

A comprehensive introduction can be found in my book.

Shiyu Zhao 20 / 69
Outline

1 Motivating examples: from table to function

2 Algorithm for state value estimation

Objective function
Optimization algorithms
Selection of function approximators
Illustrative examples
Summary of the story
Theoretical analysis (optional)

3 Sarsa with function approximation

4 Q-learning with function approximation

5 Deep Q-learning

6 Summary

Shiyu Zhao 21 / 69
Optimization algorithms

While we have the objective function, the next step is to optimize it.
• To minimize the objective function J(w), we can use the gradient-descent
algorithm:

wk+1 = wk − αk ∇w J(wk )

The true gradient is

∇w J(w) = ∇w E[(vπ (S) − v̂(S, w))2 ]

Shiyu Zhao 22 / 69
Optimization algorithms

While we have the objective function, the next step is to optimize it.
• To minimize the objective function J(w), we can use the gradient-descent
algorithm:

wk+1 = wk − αk ∇w J(wk )

The true gradient is

∇w J(w) = ∇w E[(vπ (S) − v̂(S, w))2 ]

Shiyu Zhao 22 / 69
Optimization algorithms

While we have the objective function, the next step is to optimize it.
• To minimize the objective function J(w), we can use the gradient-descent
algorithm:

wk+1 = wk − αk ∇w J(wk )

The true gradient is

∇w J(w) = ∇w E[(vπ (S) − v̂(S, w))2 ]

Shiyu Zhao 22 / 69
Optimization algorithms

While we have the objective function, the next step is to optimize it.
• To minimize the objective function J(w), we can use the gradient-descent
algorithm:

wk+1 = wk − αk ∇w J(wk )

The true gradient is

∇w J(w) = ∇w E[(vπ (S) − v̂(S, w))2 ]

= E[∇w (vπ (S) − v̂(S, w))2 ]

Shiyu Zhao 22 / 69
Optimization algorithms

While we have the objective function, the next step is to optimize it.
• To minimize the objective function J(w), we can use the gradient-descent
algorithm:

wk+1 = wk − αk ∇w J(wk )

The true gradient is

∇w J(w) = ∇w E[(vπ (S) − v̂(S, w))2 ]

= E[∇w (vπ (S) − v̂(S, w))2 ]
= 2E[(vπ (S) − v̂(S, w))(−∇w v̂(S, w))]

Shiyu Zhao 22 / 69
Optimization algorithms

While we have the objective function, the next step is to optimize it.
• To minimize the objective function J(w), we can use the gradient-descent
algorithm:

wk+1 = wk − αk ∇w J(wk )

The true gradient is

∇w J(w) = ∇w E[(vπ (S) − v̂(S, w))2 ]

= E[∇w (vπ (S) − v̂(S, w))2 ]
= 2E[(vπ (S) − v̂(S, w))(−∇w v̂(S, w))]
= −2E[(vπ (S) − v̂(S, w))∇w v̂(S, w)]

Shiyu Zhao 22 / 69
Optimization algorithms

While we have the objective function, the next step is to optimize it.
• To minimize the objective function J(w), we can use the gradient-descent
algorithm:

wk+1 = wk − αk ∇w J(wk )

The true gradient is

∇w J(w) = ∇w E[(vπ (S) − v̂(S, w))2 ]

= E[∇w (vπ (S) − v̂(S, w))2 ]
= 2E[(vπ (S) − v̂(S, w))(−∇w v̂(S, w))]
= −2E[(vπ (S) − v̂(S, w))∇w v̂(S, w)]

The true gradient above involves the calculation of an expectation.

Shiyu Zhao 22 / 69
Optimization algorithms

We can use the stochastic gradient to replace the true gradient:

wk+1 = wk + αk E[(vπ (S) − v̂(S, w))∇w v̂(S, w)]

⇓
wt+1 = wt + αt (vπ (st ) − v̂(st , wt ))∇w v̂(st , wt )

where st is a sample of S. Here, 2αt is merged to αt .

• The samples are expected to satisfy the stationary distribution. In practice,
they may not satisfy.
• This algorithm is not implementable because it requires the true state value
vπ , which is the unknown to be estimated.
• We can replace vπ (st ) with an approximation so that the algorithm is
implementable.

Shiyu Zhao 23 / 69
Optimization algorithms

We can use the stochastic gradient to replace the true gradient:

wk+1 = wk + αk E[(vπ (S) − v̂(S, w))∇w v̂(S, w)]

⇓
wt+1 = wt + αt (vπ (st ) − v̂(st , wt ))∇w v̂(st , wt )

where st is a sample of S. Here, 2αt is merged to αt .

Shiyu Zhao 23 / 69
Optimization algorithms

We can use the stochastic gradient to replace the true gradient:

wk+1 = wk + αk E[(vπ (S) − v̂(S, w))∇w v̂(S, w)]

⇓
wt+1 = wt + αt (vπ (st ) − v̂(st , wt ))∇w v̂(st , wt )

where st is a sample of S. Here, 2αt is merged to αt .

Shiyu Zhao 23 / 69
Optimization algorithms

We can use the stochastic gradient to replace the true gradient:

wk+1 = wk + αk E[(vπ (S) − v̂(S, w))∇w v̂(S, w)]

⇓
wt+1 = wt + αt (vπ (st ) − v̂(st , wt ))∇w v̂(st , wt )

where st is a sample of S. Here, 2αt is merged to αt .

Shiyu Zhao 23 / 69
Optimization algorithms

In particular,
• First, Monte Carlo learning with function approximation
Let gt be the discounted return starting from st in the episode. Then, gt can
be used to approximate vπ (st ). The algorithm becomes

wt+1 = wt + αt (gt − v̂(st , wt ))∇w v̂(st , wt ).

• Second, TD learning with function approximation

By the spirit of TD learning, rt+1 + γv̂(st+1 , wt ) can be viewed as an
approximation of vπ (st ). Then, the algorithm becomes

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt ).

Shiyu Zhao 24 / 69
Optimization algorithms

wt+1 = wt + αt (gt − v̂(st , wt ))∇w v̂(st , wt ).

• Second, TD learning with function approximation

By the spirit of TD learning, rt+1 + γv̂(st+1 , wt ) can be viewed as an
approximation of vπ (st ). Then, the algorithm becomes

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt ).

Shiyu Zhao 24 / 69
Optimization algorithms

wt+1 = wt + αt (gt − v̂(st , wt ))∇w v̂(st , wt ).

• Second, TD learning with function approximation

By the spirit of TD learning, rt+1 + γv̂(st+1 , wt ) can be viewed as an
approximation of vπ (st ). Then, the algorithm becomes

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt ).

Shiyu Zhao 24 / 69
Optimization algorithms

wt+1 = wt + αt (gt − v̂(st , wt ))∇w v̂(st , wt ).

• Second, TD learning with function approximation

By the spirit of TD learning, rt+1 + γv̂(st+1 , wt ) can be viewed as an
approximation of vπ (st ). Then, the algorithm becomes

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt ).

Shiyu Zhao 24 / 69
Optimization algorithms

wt+1 = wt + αt (gt − v̂(st , wt ))∇w v̂(st , wt ).

• Second, TD learning with function approximation

By the spirit of TD learning, rt+1 + γv̂(st+1 , wt ) can be viewed as an
approximation of vπ (st ). Then, the algorithm becomes

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt ).

Shiyu Zhao 24 / 69
Optimization algorithms

Pseudocode: TD learning of state values with function approximation

Initialization: A function v̂(s, w) that is differentiable in w. Initial parameter w0 .

Goal: Learn the true state values of a given policy π.
For each episode {(st , rt+1 , st+1 )}t generated by π, do
For each sample (st , rt+1 , st+1 ), do
In the general case,
wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt )

It can only estimate the state values of a given policy, but it is important to
understand other algorithms introduced later.

Shiyu Zhao 25 / 69
Optimization algorithms

Pseudocode: TD learning of state values with function approximation

Initialization: A function v̂(s, w) that is differentiable in w. Initial parameter w0 .

It can only estimate the state values of a given policy, but it is important to
understand other algorithms introduced later.

Shiyu Zhao 25 / 69
Optimization algorithms

Pseudocode: TD learning of state values with function approximation

Initialization: A function v̂(s, w) that is differentiable in w. Initial parameter w0 .

It can only estimate the state values of a given policy, but it is important to
understand other algorithms introduced later.

Shiyu Zhao 25 / 69
Outline

1 Motivating examples: from table to function

2 Algorithm for state value estimation

Objective function
Optimization algorithms
Selection of function approximators
Illustrative examples
Summary of the story
Theoretical analysis (optional)

3 Sarsa with function approximation

4 Q-learning with function approximation

5 Deep Q-learning

6 Summary

Shiyu Zhao 26 / 69
Selection of function approximators

An important question that has not been answered: How to select the function
v̂(s, w)?
• The first approach, which was widely used before, is to use a linear function

v̂(s, w) = φT (s)w

Here, φ(s) is the feature vector, which can be a polynomial basis, Fourier
basis, ... (see my book for details). We have seen in the motivating example
and will see again in the illustrative examples later.
• The second approach, which is widely used nowadays, is to use a neural
network as a nonlinear function approximator.
- For example, the input is s, the output is v̂(s, w), and the parameter is w.

Shiyu Zhao 27 / 69
Selection of function approximators

An important question that has not been answered: How to select the function
v̂(s, w)?
• The first approach, which was widely used before, is to use a linear function

v̂(s, w) = φT (s)w

Shiyu Zhao 27 / 69
Selection of function approximators

An important question that has not been answered: How to select the function
v̂(s, w)?
• The first approach, which was widely used before, is to use a linear function

v̂(s, w) = φT (s)w

Shiyu Zhao 27 / 69
Selection of function approximators

An important question that has not been answered: How to select the function
v̂(s, w)?
• The first approach, which was widely used before, is to use a linear function

v̂(s, w) = φT (s)w

Shiyu Zhao 27 / 69
Selection of function approximators

An important question that has not been answered: How to select the function
v̂(s, w)?
• The first approach, which was widely used before, is to use a linear function

v̂(s, w) = φT (s)w

Shiyu Zhao 27 / 69
Selection of function approximators

An important question that has not been answered: How to select the function
v̂(s, w)?
• The first approach, which was widely used before, is to use a linear function

v̂(s, w) = φT (s)w

Shiyu Zhao 27 / 69
Linear function approximation

In the linear case where v̂(s, w) = φT (s)w, we have

∇w v̂(s, w) = φ(s).

Substituting the gradient into the TD algorithm

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt )

yields

wt+1 = wt + αt rt+1 + γφT (st+1 )wt − φT (st )wt φ(st ),

which is the algorithm of TD learning with linear function approximation.

It is called TD-Linear in our course.

Shiyu Zhao 28 / 69
Linear function approximation

In the linear case where v̂(s, w) = φT (s)w, we have

∇w v̂(s, w) = φ(s).

Substituting the gradient into the TD algorithm

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt )

yields

wt+1 = wt + αt rt+1 + γφT (st+1 )wt − φT (st )wt φ(st ),

which is the algorithm of TD learning with linear function approximation.

It is called TD-Linear in our course.

Shiyu Zhao 28 / 69
Linear function approximation

In the linear case where v̂(s, w) = φT (s)w, we have

∇w v̂(s, w) = φ(s).

Substituting the gradient into the TD algorithm

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt )

yields

wt+1 = wt + αt rt+1 + γφT (st+1 )wt − φT (st )wt φ(st ),

which is the algorithm of TD learning with linear function approximation.

It is called TD-Linear in our course.

Shiyu Zhao 28 / 69
Linear function approximation

In the linear case where v̂(s, w) = φT (s)w, we have

∇w v̂(s, w) = φ(s).

Substituting the gradient into the TD algorithm

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt )

yields

wt+1 = wt + αt rt+1 + γφT (st+1 )wt − φT (st )wt φ(st ),

which is the algorithm of TD learning with linear function approximation.

It is called TD-Linear in our course.

Shiyu Zhao 28 / 69
Linear function approximation

In the linear case where v̂(s, w) = φT (s)w, we have

∇w v̂(s, w) = φ(s).

Substituting the gradient into the TD algorithm

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt )

yields

wt+1 = wt + αt rt+1 + γφT (st+1 )wt − φT (st )wt φ(st ),

which is the algorithm of TD learning with linear function approximation.

It is called TD-Linear in our course.

Shiyu Zhao 28 / 69
Linear function approximation

• Disadvantages of linear function methods:

- Difficult to select appropriate feature vectors.

• Advantages of linear function methods:

- The theoretical properties of the TD algorithm in the linear case can be
much better understood than in the nonlinear case.
- Linear function approximation is still powerful in the sense that the tabular
representation is a special case of linear function representation.

Shiyu Zhao 29 / 69
Linear function approximation

• Disadvantages of linear function methods:

- Difficult to select appropriate feature vectors.

• Advantages of linear function methods:

Shiyu Zhao 29 / 69
Linear function approximation

• Disadvantages of linear function methods:

- Difficult to select appropriate feature vectors.

• Advantages of linear function methods:

Shiyu Zhao 29 / 69
Linear function approximation

We next show that tabular representation is a special case of linear function

representation. Hence, the tabular and function representations are unified!

• Consider a special feature vector for state s:

φ(s) = es ∈ R|S| ,

where es is a vector with the sth entry as 1 and the others as 0.

• In this case,
v̂(s, w) = φT (s)w = eTs w = w(s),

where w(s) is the sth entry of w.

Shiyu Zhao 30 / 69
Linear function approximation

We next show that tabular representation is a special case of linear function

representation. Hence, the tabular and function representations are unified!

• Consider a special feature vector for state s:

φ(s) = es ∈ R|S| ,

where es is a vector with the sth entry as 1 and the others as 0.

• In this case,
v̂(s, w) = φT (s)w = eTs w = w(s),

where w(s) is the sth entry of w.

Shiyu Zhao 30 / 69
Linear function approximation

We next show that tabular representation is a special case of linear function

representation. Hence, the tabular and function representations are unified!

• Consider a special feature vector for state s:

φ(s) = es ∈ R|S| ,

where es is a vector with the sth entry as 1 and the others as 0.

• In this case,
v̂(s, w) = φT (s)w = eTs w = w(s),

where w(s) is the sth entry of w.

Shiyu Zhao 30 / 69
Linear function approximation

Recall that the TD-Linear algorithm is

wt+1 = wt + αt rt+1 + γφT (st+1 )wt − φT (st )wt φ(st ),

• When φ(st ) = es , the above algorithm becomes

wt+1 = wt + αt (rt+1 + γwt (st+1 ) − wt (st )) est .

This is a vector equation that merely updates the st th entry of wt .

• Multiplying eTst on both sides of the equation gives

wt+1 (st ) = wt (st ) + αt (rt+1 + γwt (st+1 ) − wt (st )) ,

which is exactly the tabular TD algorithm (which is called TD-Table here).

Summary: TD-Linear becomes TD-Table if we select a special feature vector.

Shiyu Zhao 31 / 69
Linear function approximation

Recall that the TD-Linear algorithm is

wt+1 = wt + αt rt+1 + γφT (st+1 )wt − φT (st )wt φ(st ),

• When φ(st ) = es , the above algorithm becomes

wt+1 = wt + αt (rt+1 + γwt (st+1 ) − wt (st )) est .

This is a vector equation that merely updates the st th entry of wt .

• Multiplying eTst on both sides of the equation gives

wt+1 (st ) = wt (st ) + αt (rt+1 + γwt (st+1 ) − wt (st )) ,

which is exactly the tabular TD algorithm (which is called TD-Table here).

Summary: TD-Linear becomes TD-Table if we select a special feature vector.

Shiyu Zhao 31 / 69
Linear function approximation

Recall that the TD-Linear algorithm is

wt+1 = wt + αt rt+1 + γφT (st+1 )wt − φT (st )wt φ(st ),

• When φ(st ) = es , the above algorithm becomes

wt+1 = wt + αt (rt+1 + γwt (st+1 ) − wt (st )) est .

This is a vector equation that merely updates the st th entry of wt .

• Multiplying eTst on both sides of the equation gives

wt+1 (st ) = wt (st ) + αt (rt+1 + γwt (st+1 ) − wt (st )) ,

which is exactly the tabular TD algorithm (which is called TD-Table here).

Summary: TD-Linear becomes TD-Table if we select a special feature vector.

Shiyu Zhao 31 / 69
Linear function approximation

Recall that the TD-Linear algorithm is

wt+1 = wt + αt rt+1 + γφT (st+1 )wt − φT (st )wt φ(st ),

• When φ(st ) = es , the above algorithm becomes

wt+1 = wt + αt (rt+1 + γwt (st+1 ) − wt (st )) est .

This is a vector equation that merely updates the st th entry of wt .

• Multiplying eTst on both sides of the equation gives

wt+1 (st ) = wt (st ) + αt (rt+1 + γwt (st+1 ) − wt (st )) ,

which is exactly the tabular TD algorithm (which is called TD-Table here).

Summary: TD-Linear becomes TD-Table if we select a special feature vector.

Shiyu Zhao 31 / 69
Outline

1 Motivating examples: from table to function

2 Algorithm for state value estimation

Objective function
Optimization algorithms
Selection of function approximators
Illustrative examples
Summary of the story
Theoretical analysis (optional)

3 Sarsa with function approximation

4 Q-learning with function approximation

5 Deep Q-learning

6 Summary

Shiyu Zhao 32 / 69
Illustrative examples

Consider a 5x5 grid-world example:

1 2 3 4 5

• Given a policy: π(a|s) = 0.2 for any s, a

• Our aim is to estimate the state values of this policy (policy evaluation
problem).
• There are 25 state values in total. We next show that we can use less than
25 parameters to approximate 25 state values.
• Set rforbidden = rboundary = −1, rtarget = 1, and γ = 0.9.

Shiyu Zhao 33 / 69
Illustrative examples

Consider a 5x5 grid-world example:

1 2 3 4 5

• Given a policy: π(a|s) = 0.2 for any s, a

Shiyu Zhao 33 / 69
Illustrative examples

Consider a 5x5 grid-world example:

1 2 3 4 5

• Given a policy: π(a|s) = 0.2 for any s, a

Shiyu Zhao 33 / 69
Illustrative examples

Consider a 5x5 grid-world example:

1 2 3 4 5

• Given a policy: π(a|s) = 0.2 for any s, a

Shiyu Zhao 33 / 69
Illustrative examples

Consider a 5x5 grid-world example:

1 2 3 4 5

• Given a policy: π(a|s) = 0.2 for any s, a

Shiyu Zhao 33 / 69
Illustrative examples

Ground truth:
• The true state values and the 3D visualization
1 2 3 4 5 1 2 3 4 5

1 1 -3.8 -3.8 -3.6 -3.1 -3.2

2 2 -3.8 -3.8 -3.8 -3.1 -2.9

3 3 -3.6 -3.9 -3.4 -3.2 -2.9

4 4 -3.9 -3.6 -3.4 -2.9 -3.2

5 5 -4.5 -4.2 -3.4 -3.4 -3.5

Experience samples:
• 500 episodes were generated following the given policy.
• Each episode has 500 steps and starts from a randomly selected state-action
pair following a uniform distribution.

Shiyu Zhao 34 / 69
Illustrative examples

Ground truth:
• The true state values and the 3D visualization
1 2 3 4 5 1 2 3 4 5

1 1 -3.8 -3.8 -3.6 -3.1 -3.2

2 2 -3.8 -3.8 -3.8 -3.1 -2.9

3 3 -3.6 -3.9 -3.4 -3.2 -2.9

4 4 -3.9 -3.6 -3.4 -2.9 -3.2

5 5 -4.5 -4.2 -3.4 -3.4 -3.5

Experience samples:
• 500 episodes were generated following the given policy.
• Each episode has 500 steps and starts from a randomly selected state-action
pair following a uniform distribution.

Shiyu Zhao 34 / 69
Illustrative examples

Ground truth:
• The true state values and the 3D visualization
1 2 3 4 5 1 2 3 4 5

1 1 -3.8 -3.8 -3.6 -3.1 -3.2

2 2 -3.8 -3.8 -3.8 -3.1 -2.9

3 3 -3.6 -3.9 -3.4 -3.2 -2.9

4 4 -3.9 -3.6 -3.4 -2.9 -3.2

5 5 -4.5 -4.2 -3.4 -3.4 -3.5

Experience samples:
• 500 episodes were generated following the given policy.
• Each episode has 500 steps and starts from a randomly selected state-action
pair following a uniform distribution.

Shiyu Zhao 34 / 69
Illustrative examples

TD-Table:
• For comparison, the results by the tabular TD algorithm (called TD-Table
here):

4
TD-Table: =0.005

State value error (RMSE)

0
0 100 200 300 400 500
Episode index

Shiyu Zhao 35 / 69
Illustrative examples

TD-Linear:
• How to apply the TD-Linear algorithm?
- Feature vector selection:
 
1
φ(s) =  x  ∈ R3 .
 

- In this case, the approximated state value is

 
w1
v̂(s, w) = φT (s)w = [1, x, y]  w2  = w1 + w2 x + w3 y.
 

Remark: φ(s) can also be defined as φ(s) = [x, y, 1]T , where the order of
the elements does not matter.

Shiyu Zhao 36 / 69
Illustrative examples

TD-Linear:
• How to apply the TD-Linear algorithm?
- Feature vector selection:
 
1
φ(s) =  x  ∈ R3 .
 

- In this case, the approximated state value is

 
w1
v̂(s, w) = φT (s)w = [1, x, y]  w2  = w1 + w2 x + w3 y.
 

Remark: φ(s) can also be defined as φ(s) = [x, y, 1]T , where the order of
the elements does not matter.

Shiyu Zhao 36 / 69
Illustrative examples

TD-Linear:
• How to apply the TD-Linear algorithm?
- Feature vector selection:
 
1
φ(s) =  x  ∈ R3 .
 

- In this case, the approximated state value is

 
w1
v̂(s, w) = φT (s)w = [1, x, y]  w2  = w1 + w2 x + w3 y.
 

Remark: φ(s) can also be defined as φ(s) = [x, y, 1]T , where the order of
the elements does not matter.

Shiyu Zhao 36 / 69
Illustrative examples

TD-Linear:
• How to apply the TD-Linear algorithm?
- Feature vector selection:
 
1
φ(s) =  x  ∈ R3 .
 

- In this case, the approximated state value is

 
w1
v̂(s, w) = φT (s)w = [1, x, y]  w2  = w1 + w2 x + w3 y.
 

Remark: φ(s) can also be defined as φ(s) = [x, y, 1]T , where the order of
the elements does not matter.

Shiyu Zhao 36 / 69
Illustrative examples

TD-Linear:
• Results by the TD-Linear algorithm:

5
TD-Linear: =0.0005

State value error (RMSE)

0
0 100 200 300 400 500
Episode index

• The trend is right, but there are errors due to limited approximation ability!
• We are trying to use a plane to approximate a non-plane surface!

Shiyu Zhao 37 / 69
Illustrative examples

TD-Linear:
• Results by the TD-Linear algorithm:

5
TD-Linear: =0.0005

State value error (RMSE)

0
0 100 200 300 400 500
Episode index

• The trend is right, but there are errors due to limited approximation ability!
• We are trying to use a plane to approximate a non-plane surface!

Shiyu Zhao 37 / 69
Illustrative examples

To enhance the approximation ability, we can use high-order feature vectors

and hence more parameters.
• For example, we can consider

φ(s) = [1, x, y, x2 , y 2 , xy]T ∈ R6 .

In this case,

v̂(s, w) = φT (s)w = w1 + w2 x + w3 y + w4 x2 + w5 y 2 + w6 xy

which corresponds to a quadratic surface.

• We can further increase the dimension of the feature vector:

φ(s) = [1, x, y, x2 , y 2 , xy, x3 , y 3 , x2 y, xy 2 ]T ∈ R10 .

Shiyu Zhao 38 / 69
Illustrative examples

To enhance the approximation ability, we can use high-order feature vectors

and hence more parameters.
• For example, we can consider

φ(s) = [1, x, y, x2 , y 2 , xy]T ∈ R6 .

In this case,

v̂(s, w) = φT (s)w = w1 + w2 x + w3 y + w4 x2 + w5 y 2 + w6 xy

which corresponds to a quadratic surface.

• We can further increase the dimension of the feature vector:

φ(s) = [1, x, y, x2 , y 2 , xy, x3 , y 3 , x2 y, xy 2 ]T ∈ R10 .

Shiyu Zhao 38 / 69
Illustrative examples

To enhance the approximation ability, we can use high-order feature vectors

and hence more parameters.
• For example, we can consider

φ(s) = [1, x, y, x2 , y 2 , xy]T ∈ R6 .

In this case,

v̂(s, w) = φT (s)w = w1 + w2 x + w3 y + w4 x2 + w5 y 2 + w6 xy

which corresponds to a quadratic surface.

• We can further increase the dimension of the feature vector:

φ(s) = [1, x, y, x2 , y 2 , xy, x3 , y 3 , x2 y, xy 2 ]T ∈ R10 .

Shiyu Zhao 38 / 69
Illustrative examples

To enhance the approximation ability, we can use high-order feature vectors

and hence more parameters.
• For example, we can consider

φ(s) = [1, x, y, x2 , y 2 , xy]T ∈ R6 .

In this case,

v̂(s, w) = φT (s)w = w1 + w2 x + w3 y + w4 x2 + w5 y 2 + w6 xy

which corresponds to a quadratic surface.

• We can further increase the dimension of the feature vector:

φ(s) = [1, x, y, x2 , y 2 , xy, x3 , y 3 , x2 y, xy 2 ]T ∈ R10 .

Shiyu Zhao 38 / 69
Illustrative examples

Results by the TD-Linear algorithm with higher-order feature vectors:

5
TD-Linear: =0.0005

State value error (RMSE)

0
0 100 200 300 400 500
Episode index

The above figure: φ(s) ∈ R6

More examples and features are given in the book.

Shiyu Zhao 39 / 69
Illustrative examples

Results by the TD-Linear algorithm with higher-order feature vectors:

5
TD-Linear: =0.0005

State value error (RMSE)

0
0 100 200 300 400 500
Episode index

The above figure: φ(s) ∈ R6

3.5
TD-Linear: =0.0005

State value error (RMSE)

2.5

1.5

0.5

0
0 100 200 300 400 500
Episode index

The above figure: φ(s) ∈ R10

More examples and features are given in the book.

Shiyu Zhao 39 / 69
Illustrative examples

Results by the TD-Linear algorithm with higher-order feature vectors:

5
TD-Linear: =0.0005

State value error (RMSE)

0
0 100 200 300 400 500
Episode index

The above figure: φ(s) ∈ R6

3.5
TD-Linear: =0.0005

State value error (RMSE)

2.5

1.5

0.5

0
0 100 200 300 400 500
Episode index

The above figure: φ(s) ∈ R10

More examples and features are given in the book.

Shiyu Zhao 39 / 69
Outline

1 Motivating examples: from table to function

2 Algorithm for state value estimation

Objective function
Optimization algorithms
Selection of function approximators
Illustrative examples
Summary of the story
Theoretical analysis (optional)

3 Sarsa with function approximation

4 Q-learning with function approximation

5 Deep Q-learning

6 Summary

Shiyu Zhao 40 / 69
Summary of the story

Up to now, we finished the story of TD learning with value function

approximation.
1) This story started from the objective function:

J(w) = E[(vπ (S) − v̂(S, w))2 ]

The objective function suggests that it is a policy evaluation problem.

2) The gradient-descent algorithm is

wt+1 = wt + αt (vπ (st ) − v̂(st , wt ))∇w v̂(st , wt )

3) The true value function, which is unknown, in the algorithm is replaced by

an approximation, leading to the algorithm:

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt )

Although this story is very helpful to understand the basic idea, it is not
mathematically rigorous.
Shiyu Zhao 41 / 69
Summary of the story

Up to now, we finished the story of TD learning with value function

approximation.
1) This story started from the objective function:

J(w) = E[(vπ (S) − v̂(S, w))2 ]

The objective function suggests that it is a policy evaluation problem.

2) The gradient-descent algorithm is

wt+1 = wt + αt (vπ (st ) − v̂(st , wt ))∇w v̂(st , wt )

3) The true value function, which is unknown, in the algorithm is replaced by

an approximation, leading to the algorithm:

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt )

Although this story is very helpful to understand the basic idea, it is not
mathematically rigorous.
Shiyu Zhao 41 / 69
Summary of the story

Up to now, we finished the story of TD learning with value function

approximation.
1) This story started from the objective function:

J(w) = E[(vπ (S) − v̂(S, w))2 ]

The objective function suggests that it is a policy evaluation problem.

2) The gradient-descent algorithm is

wt+1 = wt + αt (vπ (st ) − v̂(st , wt ))∇w v̂(st , wt )

3) The true value function, which is unknown, in the algorithm is replaced by

an approximation, leading to the algorithm:

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt )

Although this story is very helpful to understand the basic idea, it is not
mathematically rigorous.
Shiyu Zhao 41 / 69
Summary of the story

Up to now, we finished the story of TD learning with value function

approximation.
1) This story started from the objective function:

J(w) = E[(vπ (S) − v̂(S, w))2 ]

The objective function suggests that it is a policy evaluation problem.

2) The gradient-descent algorithm is

wt+1 = wt + αt (vπ (st ) − v̂(st , wt ))∇w v̂(st , wt )

3) The true value function, which is unknown, in the algorithm is replaced by

an approximation, leading to the algorithm:

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt )

Although this story is very helpful to understand the basic idea, it is not
mathematically rigorous.
Shiyu Zhao 41 / 69
Summary of the story

Up to now, we finished the story of TD learning with value function

approximation.
1) This story started from the objective function:

J(w) = E[(vπ (S) − v̂(S, w))2 ]

The objective function suggests that it is a policy evaluation problem.

2) The gradient-descent algorithm is

wt+1 = wt + αt (vπ (st ) − v̂(st , wt ))∇w v̂(st , wt )

3) The true value function, which is unknown, in the algorithm is replaced by

an approximation, leading to the algorithm:

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt )

Although this story is very helpful to understand the basic idea, it is not
mathematically rigorous.
Shiyu Zhao 41 / 69
Outline

1 Motivating examples: from table to function

2 Algorithm for state value estimation

Objective function
Optimization algorithms
Selection of function approximators
Illustrative examples
Summary of the story
Theoretical analysis (optional)

3 Sarsa with function approximation

4 Q-learning with function approximation

5 Deep Q-learning

6 Summary

Shiyu Zhao 42 / 69
Theoretical analysis (optional)

• The algorithm

wt+1 = wt + αt [rt+1 + γv̂(st+1 , wt ) − v̂(st , wt )] ∇w v̂(st , wt )

does not minimize the following objective function:

J(w) = E[(vπ (S) − v̂(S, w))2 ]

Shiyu Zhao 43 / 69
Theoretical analysis (optional)

Different objective functions:

• Objective function 1: True value error

JE (w) = E[(vπ (S) − v̂(S, w))2 ] = kv̂(w) − vπ k2D

• Objective function 2: Bellman error

.
JBE (w) = kv̂(w) − (rπ + γPπ v̂(w))k2D = kv̂(w) − Tπ (v̂(w))k2D ,
.
where Tπ (x) = rπ + γPπ x
• Objective function 3: Projected Bellman error

JP BE (w) = kv̂(w) − M Tπ (v̂(w))k2D ,

where M is a projection matrix.

- The TD-Linear algorithm minimizes the projected Bellman error.
More details are omitted here. Interested readers can check my book.

Shiyu Zhao 44 / 69
Theoretical analysis (optional)

Different objective functions:

• Objective function 1: True value error

JE (w) = E[(vπ (S) − v̂(S, w))2 ] = kv̂(w) − vπ k2D

• Objective function 2: Bellman error

.
JBE (w) = kv̂(w) − (rπ + γPπ v̂(w))k2D = kv̂(w) − Tπ (v̂(w))k2D ,
.
where Tπ (x) = rπ + γPπ x
• Objective function 3: Projected Bellman error

JP BE (w) = kv̂(w) − M Tπ (v̂(w))k2D ,

where M is a projection matrix.

- The TD-Linear algorithm minimizes the projected Bellman error.
More details are omitted here. Interested readers can check my book.

Shiyu Zhao 44 / 69
Theoretical analysis (optional)

Different objective functions:

• Objective function 1: True value error

JE (w) = E[(vπ (S) − v̂(S, w))2 ] = kv̂(w) − vπ k2D

• Objective function 2: Bellman error

.
JBE (w) = kv̂(w) − (rπ + γPπ v̂(w))k2D = kv̂(w) − Tπ (v̂(w))k2D ,
.
where Tπ (x) = rπ + γPπ x
• Objective function 3: Projected Bellman error

JP BE (w) = kv̂(w) − M Tπ (v̂(w))k2D ,

where M is a projection matrix.

- The TD-Linear algorithm minimizes the projected Bellman error.
More details are omitted here. Interested readers can check my book.

Shiyu Zhao 44 / 69
Theoretical analysis (optional)

Different objective functions:

• Objective function 1: True value error

JE (w) = E[(vπ (S) − v̂(S, w))2 ] = kv̂(w) − vπ k2D

• Objective function 2: Bellman error

.
JBE (w) = kv̂(w) − (rπ + γPπ v̂(w))k2D = kv̂(w) − Tπ (v̂(w))k2D ,
.
where Tπ (x) = rπ + γPπ x
• Objective function 3: Projected Bellman error

JP BE (w) = kv̂(w) − M Tπ (v̂(w))k2D ,

where M is a projection matrix.

- The TD-Linear algorithm minimizes the projected Bellman error.
More details are omitted here. Interested readers can check my book.

Shiyu Zhao 44 / 69
Theoretical analysis (optional)

Different objective functions:

• Objective function 1: True value error

JE (w) = E[(vπ (S) − v̂(S, w))2 ] = kv̂(w) − vπ k2D

• Objective function 2: Bellman error

.
JBE (w) = kv̂(w) − (rπ + γPπ v̂(w))k2D = kv̂(w) − Tπ (v̂(w))k2D ,
.
where Tπ (x) = rπ + γPπ x
• Objective function 3: Projected Bellman error

JP BE (w) = kv̂(w) − M Tπ (v̂(w))k2D ,

where M is a projection matrix.

- The TD-Linear algorithm minimizes the projected Bellman error.
More details are omitted here. Interested readers can check my book.

Shiyu Zhao 44 / 69
Theoretical analysis (optional)

Different objective functions:

• Objective function 1: True value error

JE (w) = E[(vπ (S) − v̂(S, w))2 ] = kv̂(w) − vπ k2D

• Objective function 2: Bellman error

.
JBE (w) = kv̂(w) − (rπ + γPπ v̂(w))k2D = kv̂(w) − Tπ (v̂(w))k2D ,
.
where Tπ (x) = rπ + γPπ x
• Objective function 3: Projected Bellman error

JP BE (w) = kv̂(w) − M Tπ (v̂(w))k2D ,

where M is a projection matrix.

- The TD-Linear algorithm minimizes the projected Bellman error.
More details are omitted here. Interested readers can check my book.

Shiyu Zhao 44 / 69
Outline

1 Motivating examples: from table to function

2 Algorithm for state value estimation

Objective function
Optimization algorithms
Selection of function approximators
Illustrative examples
Summary of the story
Theoretical analysis (optional)

3 Sarsa with function approximation

4 Q-learning with function approximation

5 Deep Q-learning

6 Summary

Shiyu Zhao 45 / 69
Sarsa with function approximation

So far, we merely considered state value estimation. That is

v̂(s) ≈ vπ (s), s∈S

To search for optimal policies, we need to estimate action values.

The Sarsa algorithm with value function approximation is

h i
wt+1 = wt + αt rt+1 + γ q̂(st+1 , at+1 , wt ) − q̂(st , at , wt ) ∇w q̂(st , at , wt ).

This is the same as the algorithm we introduced previously in this lecture

except that v̂ is replaced by q̂.

Shiyu Zhao 46 / 69
Sarsa with function approximation

So far, we merely considered state value estimation. That is

v̂(s) ≈ vπ (s), s∈S

To search for optimal policies, we need to estimate action values.

The Sarsa algorithm with value function approximation is

h i
wt+1 = wt + αt rt+1 + γ q̂(st+1 , at+1 , wt ) − q̂(st , at , wt ) ∇w q̂(st , at , wt ).

This is the same as the algorithm we introduced previously in this lecture

except that v̂ is replaced by q̂.

Shiyu Zhao 46 / 69
Sarsa with function approximation

So far, we merely considered state value estimation. That is

v̂(s) ≈ vπ (s), s∈S

To search for optimal policies, we need to estimate action values.

The Sarsa algorithm with value function approximation is

h i
wt+1 = wt + αt rt+1 + γ q̂(st+1 , at+1 , wt ) − q̂(st , at , wt ) ∇w q̂(st , at , wt ).

This is the same as the algorithm we introduced previously in this lecture

except that v̂ is replaced by q̂.

Shiyu Zhao 46 / 69
Sarsa with function approximation

So far, we merely considered state value estimation. That is

v̂(s) ≈ vπ (s), s∈S

To search for optimal policies, we need to estimate action values.

The Sarsa algorithm with value function approximation is

h i
wt+1 = wt + αt rt+1 + γ q̂(st+1 , at+1 , wt ) − q̂(st , at , wt ) ∇w q̂(st , at , wt ).

This is the same as the algorithm we introduced previously in this lecture

except that v̂ is replaced by q̂.

Shiyu Zhao 46 / 69
Sarsa with function approximation

To search for optimal policies, we can combine policy evaluation and policy
improvement.

Pseudocode: Sarsa with function approximation

Initialization: Initial parameter w0 . Initial policy π0 . αt = α > 0 for all t. ∈ (0, 1).
Goal: Learn an optimal policy to lead the agent to the target state from an initial state s0 .
For each episode, do
Generate a0 at s0 following π0 (s0 )
If st (t = 0, 1, 2, . . . ) is not the target state, do
Collect the experience sample (rt+1 , st+1 , at+1 ) given (st , at ): generate
rt+1 , st+1 by interacting with the environment; generate at+1 following πt (st+1 ).
Update q-value (updateh parameter): i
wt+1 = wt + αt rt+1 + γ q̂(st+1 , at+1 , wt ) − q̂(st , at , wt ) ∇w q̂(st , at , wt )
Update policy:
ε
πt+1 (a|st ) = 1 − |A(s (|A(st )| − 1) if a = arg maxa∈A(st ) q̂(st , a, wt+1 )
t )|

πt+1 (a|st ) = |A(s )| otherwise
t
st ← st+1 , at ← at+1

Shiyu Zhao 47 / 69
Sarsa with function approximation

To search for optimal policies, we can combine policy evaluation and policy
improvement.

Pseudocode: Sarsa with function approximation

Shiyu Zhao 47 / 69
Sarsa with function approximation

Illustrative example:
• Sarsa with linear function approximation: q̂(s, a, w) = φT (s, a)w
• γ = 0.9, = 0.1, rboundary = rforbidden = −10, rtarget = 1, α = 0.001.

1 2 3 4 5
0
Total reward

1
-500

-1000 2

0 100 200 300 400 500

3
Episode length

500
4

5
0
0 100 200 300 400 500
Episode index

For details, please see the book.

Shiyu Zhao 48 / 69
Outline

1 Motivating examples: from table to function

2 Algorithm for state value estimation

Objective function
Optimization algorithms
Selection of function approximators
Illustrative examples
Summary of the story
Theoretical analysis (optional)

3 Sarsa with function approximation

4 Q-learning with function approximation

5 Deep Q-learning

6 Summary

Shiyu Zhao 49 / 69
Q-learning with function approximation

Similar to Sarsa, tabular Q-learning can also be extended to the case of value
function approximation.

The q-value update rule is

h i
wt+1 = wt + αt rt+1 + γ max q̂(st+1 , a, wt ) − q̂(st , at , wt ) ∇w q̂(st , at , wt ),
a∈A(st+1 )

which is the same as Sarsa except that q̂(st+1 , at+1 , wt ) is replaced by

maxa∈A(st+1 ) q̂(st+1 , a, wt ).

Shiyu Zhao 50 / 69
Q-learning with function approximation

Similar to Sarsa, tabular Q-learning can also be extended to the case of value
function approximation.

The q-value update rule is

h i
wt+1 = wt + αt rt+1 + γ max q̂(st+1 , a, wt ) − q̂(st , at , wt ) ∇w q̂(st , at , wt ),
a∈A(st+1 )

which is the same as Sarsa except that q̂(st+1 , at+1 , wt ) is replaced by

maxa∈A(st+1 ) q̂(st+1 , a, wt ).

Shiyu Zhao 50 / 69
Q-learning with function approximation

Pseudocode: Q-learning with function approximation (on-policy version)

Initialization: Initial parameter w0 . Initial policy π0 . αt = α > 0 for all t. ∈ (0, 1).
Goal: Learn an optimal path to lead the agent to the target state from an initial state s0 .

For each episode, do

If st (t = 0, 1, 2, . . . ) is not the target state, do
Collect the experience sample (at , rt+1 , st+1 ) given st : generate at following
πt (st ); generate rt+1 , st+1 by interacting with the environment.
Update value (update parameter): h
wt+1 = wt + αt rt+1 + γ maxa∈A(st+1 ) q̂(st+1 , a, wt ) −
i
q̂(st , at , wt ) ∇w q̂(st , at , wt )
Update policy:
ε
πt+1 (a|st ) = 1 − |A(s (|A(st )| − 1) if a = arg maxa∈A(st ) q̂(st , a, wt+1 )
t )|
ε
πt+1 (a|st ) = |A(s )|
otherwise
t

Shiyu Zhao 51 / 69
Q-learning with function approximation

Illustrative example:
• Q-learning with linear function approximation: q̂(s, a, w) = φT (s, a)w
• γ = 0.9, = 0.1, rboundary = rforbidden = −10, rtarget = 1, α = 0.001.

1 2 3 4 5
0
Total reward

-2000
2
-4000
0 100 200 300 400 500
3
Episode length

1000 4

5
0
0 100 200 300 400 500
Episode index

Shiyu Zhao 52 / 69
Outline

1 Motivating examples: from table to function

2 Algorithm for state value estimation

Objective function
Optimization algorithms
Selection of function approximators
Illustrative examples
Summary of the story
Theoretical analysis (optional)

3 Sarsa with function approximation

4 Q-learning with function approximation

5 Deep Q-learning

6 Summary

Shiyu Zhao 53 / 69
Deep Q-learning

Deep Q-learning or deep Q-network (DQN):

• One of the earliest and most successful algorithms that introduce deep neural
networks into RL.
• The role of neural networks is to be a nonlinear function approximator.
• Different from the following algorithm:
h i
wt+1 = wt + αt rt+1 + γ max q̂(st+1 , a, wt ) − q̂(st , at , wt ) ∇w q̂(st , at , wt )
a∈A(st+1 )

because of the way of training a network.

Shiyu Zhao 54 / 69
Deep Q-learning

Deep Q-learning or deep Q-network (DQN):

because of the way of training a network.

Shiyu Zhao 54 / 69
Deep Q-learning

Deep Q-learning or deep Q-network (DQN):

because of the way of training a network.

Shiyu Zhao 54 / 69
Deep Q-learning

Deep Q-learning or deep Q-network (DQN):

because of the way of training a network.

Shiyu Zhao 54 / 69
Deep Q-learning

Deep Q-learning aims to minimize the objective function/loss function:

h i
wt+1 =wt + αt rt+1 + γ max q̂(st+1 , a, wt ) − q̂(st , at , wt ) ∇w q̂(st , at , wt )
a∈A(st+1 )

⇓
" 2 #
0
J(w) = E R + γ max0 q̂(S , a, w) − q̂(S, A, w)
a∈A(S )

where (S, A, R, S 0 ) are random variables.

Shiyu Zhao 55 / 69
Deep Q-learning

How to minimize the objective function? Gradient-descent!

• How to calculate the gradient of the objective function? Tricky!
• That is because, in this objective function
" 2 #
0
J(w) = E R + γ max0 q̂(S , a, w) − q̂(S, A, w) ,
a∈A(S )

the parameter w not only appears in q̂(S, A, w) but also in

.
y = R + γ max0 q̂(S 0 , a, w)
a∈A(S )

• Since the optimal a depends on w,

∇w y 6= γ max0 ∇w q̂(S 0 , a, w)
a∈A(S )

• To solve this problem, we can assume that w in y is fixed (at least for a
while) when we calculate the gradient.

Shiyu Zhao 56 / 69
Deep Q-learning

How to minimize the objective function? Gradient-descent!

• How to calculate the gradient of the objective function? Tricky!
• That is because, in this objective function
" 2 #
0
J(w) = E R + γ max0 q̂(S , a, w) − q̂(S, A, w) ,
a∈A(S )

the parameter w not only appears in q̂(S, A, w) but also in

.
y = R + γ max0 q̂(S 0 , a, w)
a∈A(S )

• Since the optimal a depends on w,

∇w y 6= γ max0 ∇w q̂(S 0 , a, w)
a∈A(S )

• To solve this problem, we can assume that w in y is fixed (at least for a
while) when we calculate the gradient.

Shiyu Zhao 56 / 69
Deep Q-learning

How to minimize the objective function? Gradient-descent!

• How to calculate the gradient of the objective function? Tricky!
• That is because, in this objective function
" 2 #
0
J(w) = E R + γ max0 q̂(S , a, w) − q̂(S, A, w) ,
a∈A(S )

the parameter w not only appears in q̂(S, A, w) but also in

.
y = R + γ max0 q̂(S 0 , a, w)
a∈A(S )

• Since the optimal a depends on w,

∇w y 6= γ max0 ∇w q̂(S 0 , a, w)
a∈A(S )

• To solve this problem, we can assume that w in y is fixed (at least for a
while) when we calculate the gradient.

Shiyu Zhao 56 / 69
Deep Q-learning

How to minimize the objective function? Gradient-descent!

• How to calculate the gradient of the objective function? Tricky!
• That is because, in this objective function
" 2 #
0
J(w) = E R + γ max0 q̂(S , a, w) − q̂(S, A, w) ,
a∈A(S )

the parameter w not only appears in q̂(S, A, w) but also in

.
y = R + γ max0 q̂(S 0 , a, w)
a∈A(S )

• Since the optimal a depends on w,

∇w y 6= γ max0 ∇w q̂(S 0 , a, w)
a∈A(S )

• To solve this problem, we can assume that w in y is fixed (at least for a
while) when we calculate the gradient.

Shiyu Zhao 56 / 69
Deep Q-learning

How to minimize the objective function? Gradient-descent!

• How to calculate the gradient of the objective function? Tricky!
• That is because, in this objective function
" 2 #
0
J(w) = E R + γ max0 q̂(S , a, w) − q̂(S, A, w) ,
a∈A(S )

the parameter w not only appears in q̂(S, A, w) but also in

.
y = R + γ max0 q̂(S 0 , a, w)
a∈A(S )

• Since the optimal a depends on w,

∇w y 6= γ max0 ∇w q̂(S 0 , a, w)
a∈A(S )

• To solve this problem, we can assume that w in y is fixed (at least for a
while) when we calculate the gradient.

Shiyu Zhao 56 / 69
Deep Q-learning

To do that, we can introduce two networks.

• One is a main network representing q̂(s, a, w)
• The other is a target network q̂(s, a, wT ).
The objective function in this case degenerates to
" 2 #
0
J =E R + γ max0 q̂(S , a, wT ) − q̂(S, A, w) ,
a∈A(S )

where wT is the target network parameter.

When wT is fixed, the gradient of J can be easily obtained as

∇w J = E R + γ max0 q̂(S 0 , a, wT ) − q̂(S, A, w) ∇w q̂(S, A, w) .
a∈A(S )

• The basic idea of deep Q-learning is to use the gradient-descent algorithm to

minimize the objective function.
• However, such an optimization process evolves some important techniques
that deserve special attention.
Shiyu Zhao 57 / 69
Deep Q-learning

To do that, we can introduce two networks.

where wT is the target network parameter.

When wT is fixed, the gradient of J can be easily obtained as

∇w J = E R + γ max0 q̂(S 0 , a, wT ) − q̂(S, A, w) ∇w q̂(S, A, w) .
a∈A(S )

• The basic idea of deep Q-learning is to use the gradient-descent algorithm to

minimize the objective function.
• However, such an optimization process evolves some important techniques
that deserve special attention.
Shiyu Zhao 57 / 69
Deep Q-learning

To do that, we can introduce two networks.

where wT is the target network parameter.

When wT is fixed, the gradient of J can be easily obtained as

∇w J = E R + γ max0 q̂(S 0 , a, wT ) − q̂(S, A, w) ∇w q̂(S, A, w) .
a∈A(S )

• The basic idea of deep Q-learning is to use the gradient-descent algorithm to

minimize the objective function.
• However, such an optimization process evolves some important techniques
that deserve special attention.
Shiyu Zhao 57 / 69
Deep Q-learning

To do that, we can introduce two networks.

where wT is the target network parameter.

When wT is fixed, the gradient of J can be easily obtained as

∇w J = E R + γ max0 q̂(S 0 , a, wT ) − q̂(S, A, w) ∇w q̂(S, A, w) .
a∈A(S )

• The basic idea of deep Q-learning is to use the gradient-descent algorithm to

minimize the objective function.
• However, such an optimization process evolves some important techniques
that deserve special attention.
Shiyu Zhao 57 / 69
Deep Q-learning

To do that, we can introduce two networks.

where wT is the target network parameter.

When wT is fixed, the gradient of J can be easily obtained as

∇w J = E R + γ max0 q̂(S 0 , a, wT ) − q̂(S, A, w) ∇w q̂(S, A, w) .
a∈A(S )

• The basic idea of deep Q-learning is to use the gradient-descent algorithm to

minimize the objective function.
• However, such an optimization process evolves some important techniques
that deserve special attention.
Shiyu Zhao 57 / 69
Deep Q-learning

To do that, we can introduce two networks.

where wT is the target network parameter.

When wT is fixed, the gradient of J can be easily obtained as

∇w J = E R + γ max0 q̂(S 0 , a, wT ) − q̂(S, A, w) ∇w q̂(S, A, w) .
a∈A(S )

• The basic idea of deep Q-learning is to use the gradient-descent algorithm to

minimize the objective function.
• However, such an optimization process evolves some important techniques
that deserve special attention.
Shiyu Zhao 57 / 69
Deep Q-learning - Two networks

Technique 1: Two networks, a main network and a target network.

Why is it used?
• The mathematical reason has been explained when we calculate the gradient.
Implementation details:
• Let w and wT denote the parameters of the main and target networks,
respectively. They are set to be the same initially.
• In every iteration, we draw a mini-batch of samples {(s, a, r, s0 )} from the
replay buffer (will be explained later).
• For every (s, a, r, s0 ), we can calculate the desired output as
.
yT = r + γ max0 q̂(s0 , a, wT )
a∈A(s )

Therefore, we obtain a mini-batch of data:

{(s, a, yT )}

• Use {(s, a, yT )} to train the network so as to minimize (yT − q̂(s, a, w))2 .

Shiyu Zhao 58 / 69
Deep Q-learning - Two networks

Technique 1: Two networks, a main network and a target network.

Therefore, we obtain a mini-batch of data:

{(s, a, yT )}

• Use {(s, a, yT )} to train the network so as to minimize (yT − q̂(s, a, w))2 .

Shiyu Zhao 58 / 69
Deep Q-learning - Two networks

Technique 1: Two networks, a main network and a target network.

Therefore, we obtain a mini-batch of data:

{(s, a, yT )}

• Use {(s, a, yT )} to train the network so as to minimize (yT − q̂(s, a, w))2 .

Shiyu Zhao 58 / 69
Deep Q-learning - Two networks

Technique 1: Two networks, a main network and a target network.

Therefore, we obtain a mini-batch of data:

{(s, a, yT )}

• Use {(s, a, yT )} to train the network so as to minimize (yT − q̂(s, a, w))2 .

Shiyu Zhao 58 / 69
Deep Q-learning - Two networks

Technique 1: Two networks, a main network and a target network.

Therefore, we obtain a mini-batch of data:

{(s, a, yT )}

• Use {(s, a, yT )} to train the network so as to minimize (yT − q̂(s, a, w))2 .

Shiyu Zhao 58 / 69
Deep Q-learning - Two networks

Technique 1: Two networks, a main network and a target network.

Therefore, we obtain a mini-batch of data:

{(s, a, yT )}

• Use {(s, a, yT )} to train the network so as to minimize (yT − q̂(s, a, w))2 .

Shiyu Zhao 58 / 69
Deep Q-learning - Experience replay

Technique 2: Experience replay

Question: What is experience replay?
Answer:
• After we have collected some experience samples, we do NOT use these
samples in the order they were collected.
.
• Instead, we store them in a set, called replay buffer B = {(s, a, r, s0 )}
• Every time we train the neural network, we can draw a mini-batch of random
samples from the replay buffer.
• The draw of samples, or called experience replay, should follow a uniform
distribution.

Shiyu Zhao 59 / 69
Deep Q-learning - Experience replay

Technique 2: Experience replay

Shiyu Zhao 59 / 69
Deep Q-learning - Experience replay

Technique 2: Experience replay

Shiyu Zhao 59 / 69
Deep Q-learning - Experience replay

Technique 2: Experience replay

Shiyu Zhao 59 / 69
Deep Q-learning - Experience replay

Technique 2: Experience replay

Shiyu Zhao 59 / 69
Deep Q-learning - Experience replay

Technique 2: Experience replay

Shiyu Zhao 59 / 69
Deep Q-learning - Experience replay

Question: Why is experience replay necessary in deep Q-learning? Why does

the replay must follow a uniform distribution?
Answer: The answers lie in the objective function.
" 2 #
J =E R + γ max0 q̂(S 0 , a, w) − q̂(S, A, w)
a∈A(S )

• R ∼ p(R|S, A), S 0 ∼ p(S 0 |S, A): R and S are determined by the system
model.
• (S, A) ∼ d: (S, A) is an index and treated as a single random variable
• The distribution of the state-action pair (S, A) is assumed to be uniform.
- Why uniform distribution? Because no prior knowledge.
- Can we use stationary distribution like before? No, since no policy is given.

Shiyu Zhao 60 / 69
Deep Q-learning - Experience replay

Question: Why is experience replay necessary in deep Q-learning? Why does

the replay must follow a uniform distribution?
Answer: The answers lie in the objective function.
" 2 #
J =E R + γ max0 q̂(S 0 , a, w) − q̂(S, A, w)
a∈A(S )

Shiyu Zhao 60 / 69
Deep Q-learning - Experience replay

Question: Why is experience replay necessary in deep Q-learning? Why does

the replay must follow a uniform distribution?
Answer: The answers lie in the objective function.
" 2 #
J =E R + γ max0 q̂(S 0 , a, w) − q̂(S, A, w)
a∈A(S )

Shiyu Zhao 60 / 69
Deep Q-learning - Experience replay

Question: Why is experience replay necessary in deep Q-learning? Why does

the replay must follow a uniform distribution?
Answer: The answers lie in the objective function.
" 2 #
J =E R + γ max0 q̂(S 0 , a, w) − q̂(S, A, w)
a∈A(S )

Shiyu Zhao 60 / 69
Deep Q-learning - Experience replay

Question: Why is experience replay necessary in deep Q-learning? Why does

the replay must follow a uniform distribution?
Answer: The answers lie in the objective function.
" 2 #
J =E R + γ max0 q̂(S 0 , a, w) − q̂(S, A, w)
a∈A(S )

Shiyu Zhao 60 / 69
Deep Q-learning - Experience replay

Question: Why is experience replay necessary in deep Q-learning? Why does

the replay must follow a uniform distribution?
Answer: The answers lie in the objective function.
" 2 #
J =E R + γ max0 q̂(S 0 , a, w) − q̂(S, A, w)
a∈A(S )

Shiyu Zhao 60 / 69
Deep Q-learning - Experience replay

Answer (continued):
• However, the samples are not uniformly collected because they are generated
consequently by certain policies.
• To break the correlation between consequent samples, we can use the
experience replay technique by uniformly drawing samples from the replay
buffer.
• This is the mathematical reason why experience replay is necessary and why
the experience replay must be uniform.

Shiyu Zhao 61 / 69
Deep Q-learning - Experience replay

Revisit the tabular case:

• Question: Why does not tabular Q-learning require experience replay?
- Answer: Because it does not require any distribution of S or A.
• Question: Why does Deep Q-learning involve distributions?
- Answer: Because we need to define a scalar objective function
J(w) = E[∗], where E is for all (S, A).
- The tabular case aims to solve a set of equations for all (s, a) (Bellman
optimality equation), whereas the deep case aims to optimize a scalar
objective function.
• Question: Can we use experience replay in tabular Q-learning?
- Answer: Yes, we can. And more sample efficient (why?)

Shiyu Zhao 62 / 69
Deep Q-learning - Experience replay

Revisit the tabular case:

Shiyu Zhao 62 / 69
Deep Q-learning - Experience replay

Revisit the tabular case:

Shiyu Zhao 62 / 69
Deep Q-learning - Experience replay

Revisit the tabular case:

Shiyu Zhao 62 / 69
Deep Q-learning - Experience replay

Revisit the tabular case:

Shiyu Zhao 62 / 69
Deep Q-learning - Experience replay

Revisit the tabular case:

Shiyu Zhao 62 / 69
Deep Q-learning - Experience replay

Revisit the tabular case:

Shiyu Zhao 62 / 69
Deep Q-learning

Pseudocode: Deep Q-learning (off-policy version)

Initialization: A main network and a target network with the same initial parameter.
Goal: Learn an optimal target network to approximate the optimal action values from the
experience samples generated by a given behavior policy πb .

Store the experience samples generated by πb in a replay buffer B = {(s, a, r, s0 )}

For each iteration, do
Uniformly draw a mini-batch of samples from B
For each sample (s, a, r, s0 ), calculate the target value as yT = r +
γ maxa∈A(s0 ) q̂(s0 , a, wT ), where wT is the parameter of the target network
Update the main network to minimize (yT − q̂(s, a, w))2 using the mini-batch of
samples
Set wT = w every C iterations

Remarks:
• Why no policy update?
• The network input and output are different from the DQN paper.

Shiyu Zhao 63 / 69
Deep Q-learning

Pseudocode: Deep Q-learning (off-policy version)

Store the experience samples generated by πb in a replay buffer B = {(s, a, r, s0 )}

Remarks:
• Why no policy update?
• The network input and output are different from the DQN paper.

Shiyu Zhao 63 / 69
Deep Q-learning

Pseudocode: Deep Q-learning (off-policy version)

Store the experience samples generated by πb in a replay buffer B = {(s, a, r, s0 )}

Remarks:
• Why no policy update?
• The network input and output are different from the DQN paper.

Shiyu Zhao 63 / 69
Deep Q-learning

Illustrative example:
• We need to learn optimal action values for every state-action pair.
• Once the optimal action values are obtained, the optimal greedy policy can
be obtained immediately.

Shiyu Zhao 64 / 69
Deep Q-learning

Setup:
• One single episode is used to train the network.
• This episode is generated by an exploratory behavior policy shown in Fig. (a).
• The episode only has 1,000 steps! The tabular Q-learning requires 100,000
steps.
• A shallow neural network with one single hidden layer is used as a nonlinear
approximator of q̂(s, a, w). The hidden layer has 100 neurons.
See details in the book.

Shiyu Zhao 65 / 69
Deep Q-learning

1 2 3 4 5

The behavior policy. An episode of 1,000 steps. The obtained policy.

The TD error converges to zero. The state estimation error converges to zero.

Shiyu Zhao 66 / 69
Deep Q-learning

1 2 3 4 5

The behavior policy. An episode of 1,000 steps. The obtained policy.

The TD error converges to zero. The state estimation error converges to zero.

Shiyu Zhao 66 / 69
Deep Q-learning

1 2 3 4 5 1 2 3 4 5

1 1

2 2

3 3

4 4

5 5

The behavior policy. An episode of 1,000 steps. The obtained policy.

The TD error converges to zero. The state estimation error converges to zero.

Shiyu Zhao 66 / 69
Deep Q-learning

1 2 3 4 5 1 2 3 4 5

1 1

2 2

3 3

4 4

5 5

The behavior policy. An episode of 1,000 steps. The obtained policy.

5
TD error / loss function

0
0 200 400 600 800 1000
Iteration index

The TD error converges to zero. The state estimation error converges to zero.

Shiyu Zhao 66 / 69
Deep Q-learning

1 2 3 4 5 1 2 3 4 5

1 1

2 2

3 3

4 4

5 5

The behavior policy. An episode of 1,000 steps. The obtained policy.

5 10

State value error (RMSE)

TD error / loss function

4 8

3 6

2 4

1 2

0 0
0 200 400 600 800 1000 0 200 400 600 800 1000
Iteration index Iteration index

The TD error converges to zero. The state estimation error converges to zero.

Shiyu Zhao 66 / 69
Deep Q-learning

What if we only use a single episode of 100 steps? Insufficient data

1 2 3 4 5

The behavior policy. An episode of 100 steps. The final policy.

The TD error converges to zero. The state error does not converge to zero.
Shiyu Zhao 67 / 69
Deep Q-learning

What if we only use a single episode of 100 steps? Insufficient data

1 2 3 4 5 1 2 3 4 5

1 1

2 2

3 3

4 4

5 5

The behavior policy. An episode of 100 steps. The final policy.

The TD error converges to zero. The state error does not converge to zero.
Shiyu Zhao 67 / 69
Deep Q-learning

What if we only use a single episode of 100 steps? Insufficient data

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

1 1 1

2 2 2

3 3 3

4 4 4

5 5 5

The behavior policy. An episode of 100 steps. The final policy.

The TD error converges to zero. The state error does not converge to zero.
Shiyu Zhao 67 / 69
Deep Q-learning

What if we only use a single episode of 100 steps? Insufficient data

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

1 1 1

2 2 2

3 3 3

4 4 4

5 5 5

The behavior policy. An episode of 100 steps. The final policy.

6
TD error / loss function

0
0 200 400 600 800 1000
Iteration index

The TD error converges to zero. The state error does not converge to zero.
Shiyu Zhao 67 / 69
Deep Q-learning

What if we only use a single episode of 100 steps? Insufficient data

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

1 1 1

2 2 2

3 3 3

4 4 4

5 5 5

The behavior policy. An episode of 100 steps. The final policy.

7 8

State value error (RMSE)

6
TD error / loss function

5 7

4
6
3

2
5
1

0 4
0 200 400 600 800 1000 0 200 400 600 800 1000
Iteration index Iteration index

The TD error converges to zero. The state error does not converge to zero.
Shiyu Zhao 67 / 69
Outline

1 Motivating examples: from table to function

2 Algorithm for state value estimation

Objective function
Optimization algorithms
Selection of function approximators
Illustrative examples
Summary of the story
Theoretical analysis (optional)

3 Sarsa with function approximation

4 Q-learning with function approximation

5 Deep Q-learning

6 Summary

Shiyu Zhao 68 / 69
Summary

This lecture introduces the method of value function approximation.

• First, understand the basic idea.
• Second, understand the basic algorithms.

Shiyu Zhao 69 / 69

Value Function Approximation Techniques
No ratings yet
Value Function Approximation Techniques
72 pages
Function Approximation in RL
No ratings yet
Function Approximation in RL
39 pages
State Variable Representation Overview
No ratings yet
State Variable Representation Overview
38 pages
State Space Analysis Basics Explained
No ratings yet
State Space Analysis Basics Explained
38 pages
L8 - Value Function Approximation
No ratings yet
L8 - Value Function Approximation
71 pages
Function Approximators in Reinforcement Learning
No ratings yet
Function Approximators in Reinforcement Learning
35 pages
3 Visualization and Plotting
No ratings yet
3 Visualization and Plotting
22 pages
Understanding Multivariable Functions
No ratings yet
Understanding Multivariable Functions
12 pages
11 - Chapterr 1
No ratings yet
11 - Chapterr 1
44 pages
11 - Chapterrr 1
No ratings yet
11 - Chapterrr 1
44 pages
MATLAB Basics for Macroeconomics
No ratings yet
MATLAB Basics for Macroeconomics
41 pages
Function Approximation in RL
No ratings yet
Function Approximation in RL
58 pages
Consequences of Skipping Classes
No ratings yet
Consequences of Skipping Classes
8 pages
2025 - 10 - Linear Value Function Approximation
No ratings yet
2025 - 10 - Linear Value Function Approximation
46 pages
EECS I: Modeling System Behavior
No ratings yet
EECS I: Modeling System Behavior
88 pages
FROST Tutorial by Ayonga Hereid
No ratings yet
FROST Tutorial by Ayonga Hereid
42 pages
Companion Form in State-Space Control
No ratings yet
Companion Form in State-Space Control
9 pages
User-Defined vs Built-in Functions in C
No ratings yet
User-Defined vs Built-in Functions in C
49 pages
Bellman Equations: A Comprehensive Guide
No ratings yet
Bellman Equations: A Comprehensive Guide
6 pages
Unit 1 State Variables Analysis
No ratings yet
Unit 1 State Variables Analysis
36 pages
Understanding State Space Models
No ratings yet
Understanding State Space Models
72 pages
Chap 01 S
No ratings yet
Chap 01 S
27 pages
Controllability
No ratings yet
Controllability
111 pages
MATLAB Control Systems Basics Guide
No ratings yet
MATLAB Control Systems Basics Guide
7 pages
State Space Representation in Control Systems
No ratings yet
State Space Representation in Control Systems
17 pages
RLC Circuit State-Space Analysis
No ratings yet
RLC Circuit State-Space Analysis
34 pages
Fuzzy Logic Controller Overview
No ratings yet
Fuzzy Logic Controller Overview
41 pages
State Space Representation Overview
No ratings yet
State Space Representation Overview
6 pages
Introduction to MATLAB Basics
No ratings yet
Introduction to MATLAB Basics
40 pages
State Space Representation Overview
No ratings yet
State Space Representation Overview
29 pages
Introduction to Matlab Basics
No ratings yet
Introduction to Matlab Basics
52 pages
State-Space Representation - Wikipedia, The Free Encyclopedia
No ratings yet
State-Space Representation - Wikipedia, The Free Encyclopedia
9 pages
Inverse Laplace Transform Methods
No ratings yet
Inverse Laplace Transform Methods
20 pages
2D Function Visualization in MATLAB
No ratings yet
2D Function Visualization in MATLAB
18 pages
Electric Vehicle Transfer Function Modeling
No ratings yet
Electric Vehicle Transfer Function Modeling
38 pages
Introduction to Vector Calculus
No ratings yet
Introduction to Vector Calculus
19 pages
Observable Canonical Form in Control Systems
No ratings yet
Observable Canonical Form in Control Systems
12 pages
Understanding State Variables in Control Systems
No ratings yet
Understanding State Variables in Control Systems
4 pages
State Space Modeling Analysis-Pages
No ratings yet
State Space Modeling Analysis-Pages
65 pages
Understanding Linear Transformations
No ratings yet
Understanding Linear Transformations
15 pages
Eee1002 L09
No ratings yet
Eee1002 L09
32 pages
Functional Analysis in Probability Theory
No ratings yet
Functional Analysis in Probability Theory
51 pages
Vector Operators in Engineering Analysis
No ratings yet
Vector Operators in Engineering Analysis
12 pages
Gain Scheduling in Adaptive Control
100% (1)
Gain Scheduling in Adaptive Control
39 pages
Understanding State Space Analysis
No ratings yet
Understanding State Space Analysis
17 pages
CS03
No ratings yet
CS03
46 pages
Functional Programming in Mathematica
100% (1)
Functional Programming in Mathematica
39 pages
State Space Analysis of Control Systems
No ratings yet
State Space Analysis of Control Systems
30 pages
Introduction to MATLAB Basics
No ratings yet
Introduction to MATLAB Basics
45 pages
MATLAB Programming Basics Guide
No ratings yet
MATLAB Programming Basics Guide
17 pages
Cognition and Philosophy in Computing
No ratings yet
Cognition and Philosophy in Computing
7 pages
State Space Analysis Techniques
No ratings yet
State Space Analysis Techniques
24 pages
Linear State Space Systems Overview
No ratings yet
Linear State Space Systems Overview
29 pages
Understanding Functions in Programming
No ratings yet
Understanding Functions in Programming
8 pages
State Space Analysis and Design
No ratings yet
State Space Analysis and Design
20 pages
EE 4443/4329 - Control Systems Design Project: Updated:Tuesday, June 15, 2004
No ratings yet
EE 4443/4329 - Control Systems Design Project: Updated:Tuesday, June 15, 2004
6 pages
MATLAB Functions for Engineering Applications
No ratings yet
MATLAB Functions for Engineering Applications
40 pages
OSPF Deployment and Dijkstra Overview
No ratings yet
OSPF Deployment and Dijkstra Overview
45 pages
ISP Network Design Framework Guide
No ratings yet
ISP Network Design Framework Guide
28 pages
Understanding Border Gateway Protocol (BGP)
No ratings yet
Understanding Border Gateway Protocol (BGP)
16 pages
BGP for Interdomain Routing Explained
No ratings yet
BGP for Interdomain Routing Explained
66 pages
Understanding Multicast BGP (MBGP)
No ratings yet
Understanding Multicast BGP (MBGP)
44 pages
IS-IS vs OSPF: Protocol Comparison Guide
No ratings yet
IS-IS vs OSPF: Protocol Comparison Guide
48 pages
BGP Soft Reset Enhancement Guide
No ratings yet
BGP Soft Reset Enhancement Guide
14 pages
Introduction to Border Gateway Protocol
No ratings yet
Introduction to Border Gateway Protocol
59 pages
BGP Configuration Guide for Networks
No ratings yet
BGP Configuration Guide for Networks
60 pages
BGP QoS Policy Propagation Guide
No ratings yet
BGP QoS Policy Propagation Guide
16 pages
BGP MED Churn Explained
No ratings yet
BGP MED Churn Explained
19 pages
Multihoming Strategies for Internet Connectivity
No ratings yet
Multihoming Strategies for Internet Connectivity
45 pages
BGP4: Concepts and Route Selection
No ratings yet
BGP4: Concepts and Route Selection
162 pages
BGP and Routing Table Analysis
No ratings yet
BGP and Routing Table Analysis
100 pages
BGP-4: Internet Routing Protocol Standard
No ratings yet
BGP-4: Internet Routing Protocol Standard
58 pages
BGP Deployment Guide and Best Practices
No ratings yet
BGP Deployment Guide and Best Practices
51 pages
Multicast BGP (MBGP) Overview and Guide
No ratings yet
Multicast BGP (MBGP) Overview and Guide
44 pages
BGP Configuration and Operation Guide
No ratings yet
BGP Configuration and Operation Guide
24 pages
Trans-Oceanic Internet Backbone Configurations
No ratings yet
Trans-Oceanic Internet Backbone Configurations
7 pages
BGP Configuration and Troubleshooting Guide
No ratings yet
BGP Configuration and Troubleshooting Guide
85 pages
BGP4 Design and Terminology Guide
No ratings yet
BGP4 Design and Terminology Guide
88 pages
Benefits of Internet Exchange Peering
No ratings yet
Benefits of Internet Exchange Peering
37 pages
BGP Route Optimization Techniques for ISPs
No ratings yet
BGP Route Optimization Techniques for ISPs
55 pages
BGP Attributes and Policy Control Guide
No ratings yet
BGP Attributes and Policy Control Guide
59 pages
深度学习与强化学习入门
No ratings yet
深度学习与强化学习入门
2 pages
IXP Design and Implementation Guide
No ratings yet
IXP Design and Implementation Guide
63 pages
下载程序与文件指南
No ratings yet
下载程序与文件指南
12 pages
深度强化学习文献综述
No ratings yet
深度强化学习文献综述
2 pages
EPEAT Network Equipment Criteria - FINAL April 2021
No ratings yet
EPEAT Network Equipment Criteria - FINAL April 2021
75 pages
计算机连接互联网指南
No ratings yet
计算机连接互联网指南
11 pages
Mathematical Language and Symbols Explained
No ratings yet
Mathematical Language and Symbols Explained
17 pages
Alevel Ut p1 U6 Markscheme
No ratings yet
Alevel Ut p1 U6 Markscheme
8 pages
General Mathematics: Quarter 1 - Module 6
100% (1)
General Mathematics: Quarter 1 - Module 6
33 pages
Riesz Potential Equations in Lp-Spaces
No ratings yet
Riesz Potential Equations in Lp-Spaces
29 pages
AP Calculus BC: Infinite Series Unit
No ratings yet
AP Calculus BC: Infinite Series Unit
22 pages
Graphing Real-World Problems
No ratings yet
Graphing Real-World Problems
3 pages
B.Tech IT Syllabus 2020-21 Overview
No ratings yet
B.Tech IT Syllabus 2020-21 Overview
41 pages
Grade 12 General Mathematics Exam
No ratings yet
Grade 12 General Mathematics Exam
8 pages
Control Barrier Functions for Safety Systems
No ratings yet
Control Barrier Functions for Safety Systems
16 pages
Unit 10 FRQ Scoring Guide
No ratings yet
Unit 10 FRQ Scoring Guide
8 pages
KCET 2019 Mathematics Question Paper
No ratings yet
KCET 2019 Mathematics Question Paper
33 pages
Integration Techniques and Examples
No ratings yet
Integration Techniques and Examples
10 pages
Inverse Trigonometric Functions Guide
No ratings yet
Inverse Trigonometric Functions Guide
10 pages
Fault Detection in Induction Motor Simulink
No ratings yet
Fault Detection in Induction Motor Simulink
9 pages
Set Theory and Matrix Fundamentals
No ratings yet
Set Theory and Matrix Fundamentals
9 pages
Understanding Induced Metrics and Open Sets
No ratings yet
Understanding Induced Metrics and Open Sets
3 pages
Logic and Discrete Mathematics A Computer Science - 1
No ratings yet
Logic and Discrete Mathematics A Computer Science - 1
11 pages
Unmixing Frequencies Project Guide
No ratings yet
Unmixing Frequencies Project Guide
2 pages
Discontinuity and Continuity in Functions
No ratings yet
Discontinuity and Continuity in Functions
8 pages
Python Lambda Functions Explained
No ratings yet
Python Lambda Functions Explained
5 pages
Basic Excel Formulas and Functions
No ratings yet
Basic Excel Formulas and Functions
6 pages
Adding and Subtracting Radicals
No ratings yet
Adding and Subtracting Radicals
27 pages
Understanding Calculus and Geometry Concepts
No ratings yet
Understanding Calculus and Geometry Concepts
8 pages
G11 BasicCal Q3 MELC8 Determines Whether A Function Is Continuous at A Point or Not
No ratings yet
G11 BasicCal Q3 MELC8 Determines Whether A Function Is Continuous at A Point or Not
8 pages
COMP1010 Lab 07: Python Programming
No ratings yet
COMP1010 Lab 07: Python Programming
7 pages
Test Bank For Calculus For AP 1st Edition by Ron Larson
No ratings yet
Test Bank For Calculus For AP 1st Edition by Ron Larson
61 pages
Numerical Engineering Software Overview
No ratings yet
Numerical Engineering Software Overview
13 pages
Texts in Applied Mathematics: Springer
No ratings yet
Texts in Applied Mathematics: Springer
15 pages