# Noise, overestimation and exploration in Deep Reinforcement Learning

Rafael Stekolshchik

###### Abstract.

We will discuss some statistical noise related phenomena, that were
investigated by different authors in the framework of Deep Reinforcement
Learning algorithms. The following algorithms are touched: DQN, Double DQN,
DDPG, TD3, Hill-Climbing. Firstly, we consider overestimation, that is the
harmful property resulting from noise. Then we deal with noise used for
exploration, this is the useful noise. We discuss setting the noise parameter
in TD3 for typical PyBullet environments associated with articulate bodies
such as HopperBulletEnv and Walker2DBulletEnv. In the appendix, in relation
with the Hill-Climbing algorithm, we will look at one more example of noise:
adaptive noise.

##  1\. Introduction

In 1993, Thrun and Schwartz in [TS93] gave an example in which the
overestimation (caused by noise) asymptotically lead to suboptimal policies.
In the other hand, adding noise to the action space helps algorithms in more
efficient exploration, which is not correlated to something unique, see
[OpenAI]. We will look at Deep Reinforcement Learning algorithms in terms of
issues related to noise. In this article, we will touch the following
algorithms: DQN, Double DQN, DDPG, TD3, Hill-Climbing.

In Section 2, we will see how researchers tried to overcome overestimation in
models. First step is decoupling of the action selection from action
evaluation. It was realized in Double DQN model. The second step relates to
the Actor-Critic architecture: here we decouple the value neural network
(critic) from the policy neural network (actor). In essence, this is a
generalization of what was done in Double DQN, on the continuous action spaces
case. DDPG and TD3 algorithms use this architecture, [Lil15, Fu18]. A very
significant advantage of the TD3 in overcoming overestimation is the use of
Auto-Critic with two critics architecture.

In Section 3, we consider how exploration is implemented in DQN, Double DQN,
DDPG and TD3. Exploration is a major challenge of learning. The main issue of
Section 3 is exploration noise. Neural network models using some noise
parameters have more capabilities for exploration and are more successful in
Deep Reinforcement Learning (Deep RL) algorithms. There is a certain problem
to find the true noise parameter for exploration. We discuss setting of this
parameter in TD3 for PyBullet environments associated with articulate bodies
such as HopperBulletEnv and Walker2DBulletEnv.

In the Appendix, we consider the Hill-Climbing, the simple gradient-free
algorithm. This algorithm adds adaptive noise directly to input variables,
namely to the weight matrix determining the neural network.

##  2\. In efforts to overcome overestimation

Deep Q-Network (DQN) and Double Deep Q-Network (Double DQN) algorithms turned
out to be very successful in the case of discrete action spaces. However, it
is known that these algorithms suffer from overestimation. This harmful
property is much worse than underestimation, because underestimation does not
accumulate. Let us see how researchers tried to overcome overestimation.

###  2.1. Overestimation in DQN

Let us consider the operator used for the calculation of the target value
$G_{t}$ in the key $Q$-learning equation (a.k.a Sarsamax equation). This
operator is called maximization operator:

$G_{t}=R_{t+1}+\gamma\max_{a}Q(S_{t+1},a)\\\ $

Suppose, the evaluation value for $Q(S_{t+1},a)$ is already overestimated.
Then, the agent observes that error also accumulates for $Q(S_{t},a)$:

$\begin{split}&Q(S_{t},a)\longleftarrow
Q(S_{t},a)+\alpha(R_{t+1}+\gamma\max_{a}Q(S_{t+1},a)-Q(s_{t},a_{t})),\text{
or}\\\ &Q(S_{t},a)\longleftarrow
Q(S_{t},a)+\alpha(G_{t}-Q(s_{t},a_{t})).\end{split}$

Here, $R_{t}$ is the reward at time $t$, $G_{t}$ is the cumulative reward also
know as $TD$-target; $Q(s,a)$ is the $Q$-value table of the shape [space x
action], [St20a].

In 1993, Thrun and Schwartz observed that using function approximators (i.e,
neural networks) instead of just lookup tables (this is the basic technique of
Q-learning) causes some noise on the output predictions. They gave an example
in which the overestimation asymptotically lead to suboptimal policies,
[TS93].

###  2.2. Decoupling in Double DQN

In 2015, Haselt et. al. shown that estimation errors can drive the estimates
up and away from the true optimal values. They supposed the solution that
reduces the overestimation in the discrete case: Double DQN, [Has15]. The
important thing that has been done in Double DQN is decoupling of the action
selection from action evaluation. Let us make this clear.

  * •

$G^{DQN}_{t}$ ($G_{t}$ for DQN): the $Q$-value $Q(S_{t+1},a)$ used for the
action selection (red underline) and the $Q$-value $Q(S_{t+1},a)$ used for the
action evaluation (blue underline) are determined by the same neural network
with the weight vector $\theta_{t}$.

  * •

$G^{DoubleDQN}_{t}$ ($G_{t}$ for Double DQN): the $Q$-value used for the
action selection and the $Q$-value used for the action evaluation are
determined by two different neural networks with weight vectors $\theta_{t}$
and $\theta^{\prime}_{t}$. These networks are called current and target.

However, due to the slowly changing policy, estimates of the value of the
current and target neural networks are still too similar, and this still
causes a consistent overestimation, [Fu18].

###  2.3. Actor-Critic architecture in DDPG

DDPG is one of the first algorithms that tried to use the $Q$-learning
technique of DQN models for continuous action spaces. DDPG stands for Deep
Deterministic Policy Gradient, [Spi]. In this case, we cannot use the
maximization operator of $Q$-values over all actions. However, we can use the
function approximator, a neural network representing $Q$-values. We presume
that there exists a certain function $Q(s,a)$ which is differentiable with
respect to the action $a$. However, finding

$\operatorname*{argmax}_{a}(Q(S_{t},a))$

on all actions $a$ for the given state $S_{t}$ means that we must solve the
optimization problem at every time step. This is a very expensive task. To
overcome this obstacle, a group of researchers from DeepMind used the Actor-
Critic architecture, [Lil15]. They used two neural networks: one, as before,
in DQN: $Q$-network representing $Q$-values; another one is the actor function
$\pi(s)$ supplying the action which gives the maximum of the value function
$Q(s,a)$. For the current state $s=s_{t}$ we have

$\pi(s_{t})=a^{*}\text{, where }a^{*}=\operatorname*{argmax}_{a}Q(s_{t},a)$

For any state $s$,

$\max_{a}Q(s,a)\approx Q(s,\pi(s))$

###  2.4. A pair of independently trained critics in TD3

The actor-critic Double DQN as well as DDPG suffer from overestimation. In
[Fu18, p.5], it was suggested that a failure can occur due to the interplay
between the actor and critic updates. Overestimation occurs when the policy is
poor, “and the policy will become poor if the value estimate itself is
inaccurate”. In [Fu18], authors suggested using a pair of critics
($Q_{\theta_{1}}$, $Q_{\theta_{2}}$), and taking the minimum value between
them to limit overestimation. It was originally supposed that there would also
be $2$ actors ($\pi_{1}$, $\pi_{2}$) with cross updating: $Q_{\theta_{1}}$
with $\pi_{2}$, , $Q_{\theta_{2}}$ with $\pi_{1}$ (where $\pi_{i}$ is
optimized with respect $Q_{\theta_{i}}$).

$\begin{split}&y_{1}=r+\gamma
Q_{\theta_{2}}(s^{\prime},\pi_{1}(s^{\prime}))\\\ &y_{2}=r+\gamma
Q_{\theta_{1}}(s^{\prime},\pi_{1}(s^{\prime}))\\\ \end{split}$

By [Fu18], due to the computational costs, the single actor can be used. This
reduction in the number of actors does not cause an additional bias. The
method of two critic outperforms many other algorithms including DDPG.

##  3\. Exploration as a major challenge of learning

###  3.1. Why explore?

In addition to overestimation, there is another problem in Deep RL, no less
difficult. This is exploration. We cannot unconditionally believe in maximum
values of the $Q$-table or in action function $\pi(s)$ supplying the best
actions. Why not? Firstly, at the beginning of training, the corresponding
neural network is still “young and stupid”, and its maximum values or best
actions are far from reality. Secondly, perhaps not the maximum values and not
the best actions will lead us to the optimal strategy after hard training.

$\begin{split}&\emph{ In life, we often have to solve the following problem:
}\\\ &\emph{ to follow the beaten path -- there is little risk and }\\\
&\emph{ little reward; or to take a new unknown path with }\\\ &\emph{ great
risk -- but, with some probability,a big win is }\\\ &\emph{ possible there.
Maybe it will be just super, you don’t know.}\end{split}$

###  3.2. Exploration vs. exploitation

Exploitation means, that the agent uses the accumulated knowledge to select
the following action. In our case, this means that for the given state, the
agent finds the following action that maximizes the $Q$-value. The exploration
means that the following action will be selected randomly. There is no rule
that determines which strategy is better: exploration or exploitation. The
real goal is to find a true balance between these two strategies. As we can
see, the balance strategy changes in the learning process.

###  3.3. Exploration in DQN and Double DQN

One way to ensure adequate exploration in DQN and Double DQN is to use the
annealingε-greedy mechanism, [St20b]. For the first episodes, exploitation is
selected with a small probability, for example, $0.02$ (i.e., the action will
be chosen very randomly) and the exploration is selected with a probability
$0.98$. Starting from a certain number of episode $M_{\varepsilon}$, the
exploration will be performed with a minimal probability $\varepsilon_{m}$.
For example, if $\varepsilon_{m}=0.01$, the exploitation is chosen with
probability $0.99$. The probability formula of exploration $\varepsilon$ can
be realized as follows:

$\varepsilon=\max(\frac{\varepsilon_{m}-1}{M_{\varepsilon}}i+1,\varepsilon_{m}),$

where $i$ is the episode number. Let $M_{\varepsilon}=100$,
$\varepsilon_{m}=0.01$. Then, the probability $\varepsilon$ of exploration
looks as follows:

$i$ | $0$ | $1$ | $2$ | $3$ | $\dots$ | $98$ | $99$ | $\geq 100$
---|---|---|---|---|---|---|---|---
$\varepsilon$ | $1$ | $0.9901$ | $0.9802$ | $0.9703$ | $\dots$ | $0.0298$ | $0.0199$ | $0.01$

###  3.4. Exploration in DDPG

In RL models with continuous action spaces, instead of $\varepsilon$-greedy
mechanism undirected exploration is applied. This method is used in DDPG , PPO
and other continuous control algorithms. Authors of DDPG algorithm, [Lil15],
constructed undirected exploration policy $\pi’$ by adding noise sampled from
a noise process $N$ to the actor policy $\pi(s)$:

$\pi^{\prime}(s_{t})=\pi(s_{t}|\theta_{t})+N,$

where $N$ is the noise given by Ornstein-Uhlenbeck, correlated noise process,
, [OU]. In the TD3 paper, [Fu18], authors proposed to use the classic Gaussian
noise, this is the quote:

$\begin{split}&\emph{ \ldots we use an off-policy exploration strategy, adding
Gaussian noise }\\\ &\emph{ N(0; 0:1) to each action. Unlike the original
implementation of DDPG,}\\\ &\emph{ we used uncorrelated noise for exploration
as we found noise drawn}\\\ &\emph{ from the Ornstein-Uhlenbeck (Uhlenbeck \&
Ornstein, 1930) process}\\\ &\emph{ offered no performance benefits.
}\end{split}$

The usual failure mode for DDPG is that the learned $Q$-function begins to
overestimate $Q$-values, then the policy (actor function) leads to significant
errors.

###  3.5. Exploration in TD3

The name TD3 stands for Twin Delayed Deep Deterministic. TD3 algorithm retains
the Actor-Critic architecture used in DDPG, and adds $3$ new properties that
greatly help to overcome overestimation:

  * •

TD3 maintains a pair of critics $Q1$ and $Q2$ (hence the name “twin”) along
with a single actor. For each time step, TD3 uses the smaller of the two
$Q$-values.

  * •

TD3 updates the policy (and target networks) less frequently than the
$Q$-function updates (one policy update (actor) for every two $Q$-function
(critic) updates).

  * •

TD3 adds exploration noise to the target action. TD3 uses Gaussian noise, not
Ornstein–Uhlenbeck noise as in DDPG.

###  3.6. PyBullet trained agents: Hopper and Walker2D

PyBullet is a Python module for robotics and Deep RL using PyBullet
environments is based on the Bullet Physics SDK, [Pyb20, Pyb]. Let us look at
the trained agents for HopperBulletEnv and Waker2DBulletEnv, typical PyBullet
environments associated with articulated bodies:

HopperBulletEnv and Walker2DBulletEnv trained agents

###  3.7. Exploration noise in trials with PyBullet Hopper

The HopperBulletEnv environment is considered solved if the achieved score
exceeds $2500$. In TD3 experiments with the HopperBulletEnv environment, I
got, among others, the following training curves for $std=0.1$ and $std=0.3$:

Here, std is the standard deviation of exploration noise in TD3. In both
trials, threshold $2500$ was not reached. However, I noticed the following
features:

  * •

In the experiment with $std=0.3$, there are a lot of values near $2500$ (but
less than 2500) and at the same time, the average score decreases all the
time. This is explained as follows: the number of small score values prevails
over the number of large score values, and the difference between these
numbers increases.

  * •

In the experiment with $std=0.1$, the average score values reach large
values but in general, the average scores decrease. The reason of this, as
above, is that the number of small score values prevails over the number of
large score values.

  * •

It seemed to me that the prevalence of very small values is associated with
too big noise standard deviation. Then, I decide to reduce $std$ to $0.02$, it
was enough to solve the environment.

Hopper and Walker2D are solved with TD3, see [TD3a, TD3b]

##  Appendix A Hill-Climbing algorithm with adaptive noise

###  A.1. Forerunner of tensors

We illustrate the properties of the Hill-Climbing algorithm applied to the
Cartpole environment, [St20a]. Here, the neural network model is so simple
that does not use tensors (no PyTorch, no Tensorflow). Only the simplest
matrix of shape [4 x 2] is used here, that is the forerunner of tensors. The
Hill-Climbing algorithm seeks to maximize a target function $G_{0}$, which in
our particular case is the cumulative discounted reward:

$G_{0}=R_{1}+\gamma
R_{2}+\gamma^{2}R_{3}+\dots=\sum_{k=0}^{\infty}{\gamma}^{k}R_{k+1}$

where $\gamma$ is the discount factor, $0<\gamma<1$, and $R_{k}$ is the reward
obtained at the time step $k$ of the episode. The target function $G_{0}$
looks in Python as follows:

$\begin{split}&\text{ discounts = [gamma** i {\bf for} i in {\bf range}({\bf
len}(rewards) + 1)] }\\\ &\text{ Gt = {\bf sum}([a*b {\bf for} a,b in {\bf
zip}(discounts, rewards)]) }\end{split}$

###  A.2. Two Cartpole environmens

What is $Cartpole$ ? A pole is attached by an joint to a cart, which moves
along a track. The system is controlled by applying a force of +1 or -1 to the
cart. The pendulum starts upright, and the goal is to prevent it from falling
over. A reward of +1 is provided for every timestep that the pole remains
upright. The episode ends when the pole $>15$ degrees from vertical, or the
cart moves $>2.4$ units from the center, [St20b]. The differences between
Cartpole-v0 (resp. Cartpole-v1) are in two parameters: threshold = $195$
(resp. $475$) and max episode steps = $200$ (resp $500$). Solving the
environment Cartpole-v0 (resp. Cartpole-v1) require an average total reward
that exceeds threshold for $100$ consecutive episodes.

For github projects that solve both Cartpole-v0 and Cartpole-v1 environments
with DQN and Double DQN, see [Cp20a] and [Cp20b].

###  A.3. Weight matrix in Hill-Climbing model

Hill-Climbing is a simple gradient-free algorithm. We try to climb to the top
of the curve by only changing the arguments of the target function $G_{0}$
using a certain adaptive noise. The argument of $G_{0}$ is the weight matrix
determining the neural network that underlies in our model.

###  A.4. Adaptive noise scale

The adaptive noise scaling for our model is realized as follows. If the
current value of the target function is better than the best value obtained
for the target function, we divide the noise scale by $2$, and the
corresponding noise is added to the weight matrix. If the current value of the
target function is worse than the best obtained value, we multiply the noise
scale by $2$, and the corresponding is added to the best obtained value of the
weight matrix. In both cases, a noise scale is added with some random factor
different for any element of the matrix.

The Cartpole-v0 environment is solved in 113 episodes, Cartpole-v1 is solved
in 112 episodes. For more information on Cartpole-v0/Cartpole-v1 with adaptive
noise scaling, see jupyter notebooks [Cp20a, Cp20b].

###  A.5. A more generic formula for the noise scale

As we saw above, the noise scale adaptively increases or decreases depending
on whether the target function is lower or higher than the best obtained
value. The noise scale in this algorithm is $2$. In [Pl17], authors considers
more generic formula:

$\sigma_{k+1}=\left\\{\begin{array}[]{ll}&\alpha\sigma_{k}\text{ if
}d(\pi,\widetilde{\pi})<\delta,\\\ &\\\ &\frac{1}{\alpha}\sigma_{k}\text{
otherwise },\end{array}\right.\\\ $

where $\alpha$ is a noise scale, $d$ is a certain distance measure between
perturbed and non-perturbed policy, and $\delta$ is a threshold value. In
[Pl17, App. C], authors consider the possible forms of the distance function
$d$ for algorithms DQN, DDPG and TPRO.

## References

  * []
  * [TS93] S.Thrun and A.Schwartz, Issues in Using Function Approximation for Reinforcement Learning, (1993), Carnegie Mellon University, The Robotics Institute
  * [Has15] H.van Hasselt et. al., Deep Reinforcement Learning with Double Q-learning, (2015), arXiv:1509.06461
  * [Lil15] T.P.Lillicrap et.al., Continuous control with deep reinforcement learning, (2015), arXiv:1509.02971
  * [YL18] Yuxi Li, Deep Reinforcement Learning: An Overview (2018), arXiv:1701.07274v6
  * [Fu18] S.Fujimoto et.al, Addressing Function Approximation Error in Actor-Critic Methods, (2018), arXiv: arXiv:1802.09477v3
  * [OpenAI] M.Plappert, R.Houthooft, P.Dhariwal, S.Sidor, P.Abbeel, M.Andrychowicz, R.Y.Chen, Xi Chen, T.Asfour, Better Exploration with Parameter Noise, OpenAI.com, (2017).
  * [Pl17] M.Plappert, R.Houthooft, P.Dhariwal, S.Sidor, R.Y.Chen, Xi Chen, T.Asfour, P.Abbeel, M.Andrychowicz, Parameter Space Noise for Exploration, OpenAI, arXiv:1706.01905v2, ICLR (2018),
  * [Ma19] B.Mahyavanshi, Introduction to Hill Climbing — Artificial Intelligence, Medium (2019).
  * [Spi] Deep Deterministic Policy Gradient, OpenAI, Spinning Up, Revision 038665d6 (2018), https://spinningup.openai.com/en/latest/algorithms/ddpg.html
  * [MLM19] What Does Stochastic Mean in Machine Learning? (2019), Machine Learning Mastery, https://machinelearningmastery.com/stochastic-in-machine-learning/
  * [OU] Ornstein-Uhlenbeck process, Wikipedia, https://en.wikipedia.org/wiki/Ornstein-Uhlenbeck_process
  * [Lin19] E.Lindwurm, Intuition: Exploration vs Exploitation (2019), TowardsDataScience.
  * [Pyb20] Bullet Real-Time Physics Simulation (2020), https://pybullet.org/wordpress/
  * [Pyb] Pybullet, Project description (2020), https://pypi.org/project/pybullet/
  * [St20a] R.Stekolshchik, How does the Bellman equation work in Deep RL? (2020), TowardsDataScience.
  * [St20b] R.Stekolshchik, A pair of interrelated neural networks in Deep Q-Network (2020), TowardsDataScience.
  * [St20c] R.Stekolshchik, Three aspects of Deep RL: noise, overestimation and exploration (2020), TowardsDataScience.
Refernces to github projects

  * [Cp20a] R.Stekolshchik, Cartpole with DQN (2020), https://github.com/Rafael1s/Deep-Reinforcement-Learning-Udacity/tree/master/Cartpole-Deep-Q-Learning
  * [Cp20b] R.Stekolshchik, Cartpole with Double Deep Q-Network (2020),
https://github.com/Rafael1s/Deep-Reinforcement-Learning-
Udacity/tree/master/Cartpole-Double-Deep-Q-Learning

  * [TD3a] R.Stekolshchik, HopperBulletEnv with Twin Delayed DDPG (TD3), (2020)
https://github.com/Rafael1s/Deep-Reinforcement-Learning-
Udacity/blob/master/HopperBulletEnv_v0-TD3

  * [TD3b] R.Stekolshchik, Walker2DBulletEnv with Twin Delayed DDPG (TD3), (2020)
https://github.com/Rafael1s/Deep-Reinforcement-Learning-
Udacity/blob/master/Walker2DBulletEnv-v0_TD3

  * []