Section 3.4.
1 showed how using (s, a, r, s′, ) to update the
parameters of would be incorrect.
However, if we are using DQN then neither or are used
when calculating . Since the next state s′ is the
same in both cases, each experience results in the same value
for , and so both
are valid. Even though different policies were used to gather
each sequence of data, is the same.
If the transition and rewards functions are stochastic then
choosing action a in state s multiple times may result in a
different r and s′. Qπ accounts for this because it is defined as
the expected future return from taking action a in state s, so it is
still valid to use (s, a, r, s′, ) to update . Another
way of looking at this is that the environment is responsible for
the reward r and transition into the next state s′. This is external
to the agent and the agent’s policy, so is still
independent of the policy used to gather experiences.
If does not depend on the policy used to
gather the data, then what policy does it correspond to? It is the
optimal policy as defined by Sutton and Barto[36].
TODO - check if we can quote this
“A policy π′ is defined to be better than or equal to a policy π if
its expected return is greater than or equal to that of π for all
states. In other words, π′ ≥ π if and only if Vπ′(s) Vπ(s) for all s
∈ . There is always at least one policy that is better, than or
equal to all other policies. This is an optimal policy, π*.”
The optimal Q-function is defined as taking action a in state s
*
WOW! eBook
[Link]
and afterwards following the optimal policy π*. This is shown in
Equation 4.5.
Let’s reconsider in light of Equation 4.5. If the
estimates for Qπ were correct, then selecting the action which
maximizes Qπ(s′, a′) is optimal. It is is the best an agent could
possibly do. This implies that the policy that
corresponds to is the optimal policy π*.
It is important to note that just because DQN’s objective is to
learn the optimal Q-function doesn’t mean that it will. There
may be many reasons for this. For example, the hypothesis
space represented by the neural network may not actually
contain the optimal Q-function, non-convex optimization
methods are imperfect and might not find a global minimum,
and computation and time constraints place a limit on how long
we can train an agent for. However, we can say that the upper
bound on performance with DQN is optimal, compared to a
potentially sub-optimal upper bound for SARSA resulting from
learning the Q-function under an ∊-greedy policy.
4.2 ACTION SELECTION IN DQN
Even though DQN is an off-policy algorithm, how a DQN agent
gathers experiences still matters. There are two important
factors to consider.
First, an agent still faces the exploration-exploitation trade-off
WOW! eBook
[Link]
discussed in Chapter 3. An agent should rapidly explore the
state-action space at the beginning of training to increase the
chances of discovering good ways to act in an environment. As
training progresses and the agent learns more, an agent should
gradually decrease the rate of exploration and spend more time
exploiting what it has learned. This improves the efficiency of
training as the agent focuses on better actions.
Second, if the state-action space is very large because it consists
of continuous values or is discrete with high dimensionality1,
then it will be intractable to experience all (s, a) pairs, even
once. In these cases Q-values for the unvisited (s, a) pairs may
be no better than random guessing.
1
For example if the state space is described using digital representations of
images. Pixels values are typically discrete, between 0 and 255, but a single image
can have thousands or millions of pixels, each of which can take one of 256 values.
Fortunately function approximation with neural networks
mitigate this problem because they are able generalize from
visited (s, a) pairs to similar2 states and actions, as discussed in
Box 4.1. However this does not completely solve the problem.
There may still be parts of the state-action space that are far
away and very different to the states and actions an agent has
experienced. A neural network is unlikely to generalize well in
these cases and the estimated Q-values may be inaccurate.
2
There are many ways to define what a similar state or action means and is a
large topic in its own right. A simple measure of similarity is the L2 distance. The
smaller the distance the more similar two states or actions are. However for high
dimensional states such as images, the L2 distance in pixel space may not capture
important similarities, for example similar game states which look visually
different. Other approaches try to deal with this problem, for example by first
learning a lower dimensional representation of states then measuring the L2
distance between state representations.
WOW! eBook
[Link]
Box 4.1: Generalization and Neural Networks
An important property of function-approximation methods is
how well they generalize to unseen inputs. For example, how
good is a Q-function estimate for unvisited (s, a) pairs?
Linear (e.g. linear regression) and non-linear function
approximation methods (e.g. neural networks) are both
capable of some generalization, where as tabular methods are
not.
Let’s consider a tabular representation for .
Suppose the state-action space is very large with millions of
(s, a) pairs and at the beginning of training each cell
representing a particular is initialized to 0. During
training an agent visits (s, a) pairs and the table is updated
but the unvisited (s, a) pairs continue to have .
Since the state-action space is large, many (s, a) pairs will
remain unvisited and their Q-value estimates will remain at 0
even if (s, a) is desirable, with Qπ(s, a) >> 0. The main issue
is that a tabular function representation does not learn
anything about how different states and actions relate to each
other.
In contrast, neural networks can extrapolate from Q-values
for known (s, a) to unknown (s′, a′) because they learn how
different states and actions are related to each other. This is
very useful when (s, a) is large or has infinitely many
elements because it means an agent does not have to visit all
(s, a) to learn a good estimate of the Q-function. An agent
only need visit a representative subset of the state-action
space.
WOW! eBook
[Link]
There are limitations to how well a network will generalize,
and there are two common cases where it often fails. First, if a
network receives inputs that are significantly different to the
inputs it has been trained on, it is unlikely to produce good
outputs. Generalization is typically much better in small
neighborhoods of the input space surrounding the training
data. Second, neural networks are likely to generalize poorly
if the function they are approximating has sharp
discontinuities. This is because neural networks implicitly
assume that the input space is locally smooth. If the inputs x
and x′ are similar, then the corresponding outputs y and y′
should also be similar.
Consider the example shown in Figure 4.1. It represent a one
dimensional environment in which an agent walks around a
flat mountain top. The state is the agent’s position on the x-
axis, the action is the change in x per time step x, and the
reward is shown on the y-axis. There is a cliff in this
environment, as shown by the vertical drop in the reward
when the agent reaches state s = x = 1. “Falling off” the cliff by
moving from s = x = 0.99 to s′ = x′ = 1.0 will lead to a sharp
drop in the reward received even though s and s′ are close to
each other. Moving the same distance in other parts of the
state space do not lead to such a significant change in reward.
WOW! eBook
[Link]