The problem with DDPG: understanding failures in deterministic environments with sparse rewards
Authors: Guillaume Matheron
Olivier Sigaud
Nicolas Perrin
Venue:  (2020)
Keywords: ddpg
reinforcement learning
deep learning
policy gradient

Abstract: In environments with continuous state and action spaces, state-of-the-art actor-critic reinforcement learning algorithms can solve very complex problems, yet can also fail in environments that seem trivial, but the reason for such failures is still poorly understood. In this paper, we contribute a formal explanation of these failures in the particular case of sparse reward and deterministic environments. First, using a very elementary control problem, we illustrate that the learning process can get
stuck into a fixed point corresponding to a poor solution. Then, generalizing from the studied example, we provide a detailed analysis of the underlying mechanisms which results in a new understanding of one of the convergence regimes of these algorithms. The resulting perspective casts a new light on already existing solutions to the issues we have highlighted, and suggests other potential approaches.

Under review as a conference paper at ICLR 2020
THE PROBLEM WITH DDPG: UNDERSTANDING FAIL- URES IN DETERMINISTIC ENVIRONMENTS SPARSE REWARDS
WITH
Anonymous authors Paper under double-bling review
ABSTRACT
environments with continuous state and action spaces, state-of-the-art actor-critic reinforcement learning algorithms can solve very complex problems, yet can also fail in environments that seem trivial, but the reason for such failures is still poorly understood. In this paper, we contribute formal explanation of these failures in the particular case of sparse reward and deterministic environments. First, using very elementary control problem, illustrate that the learning process can get stuck into a fixed point corresponding to a poor solution. Then, generalizing from the studied example, we provide detailed analysis of the underlying mechanisms which results in a new understanding of one of the convergence regimes of these algorithms. The resulting perspective casts a new light on already existing solutions to the issues we have highlighted, and suggests other potential approaches.
INTRODUCTION
The Deep Deterministic Policy Gradient (DDPG) algorithm (Lillicrap al. (2013) is one of the earliest deep Reinforcement Learning (RL) algorithms designed to operate on potentially large continuous state and action spaces with a deterministic policy, and is still one of the most widely used. However, it is often reported that DDPG suffers from instability in the form of sensitivity to hyper-parameters and propensity to converge to very poor solutions or even diverge. Various algorithms have improved stability by addressing well identified issues, such the over-estimation bias in TD3 (Fujimoto et al., 2018b) but, because fundamental understanding of the phenomena underlying these instabilities still missing, it is unclear whether these ad hoc remedies truly address the source of the problem. Thus, better understanding why these algorithms can fail even very simple environments is pressing question.
To investigate this question, we introduce in Section 4 a very simple one-dimensional environment with sparse reward function where DDPG sometimes fails. Analyzing this example allows to provide a detailed account of these failures. We then reveal the existence of a cycle of mechanisms operating in the sparse reward and deterministic case, leading to the quick convergence to a poor policy. In particular, we show that, when the reward is not discovered early enough, these mechanisms can lead to a deadlock situation where neither the actor nor the critic can evolve anymore. Critically, this deadlock persists even when the agent is subsequently trained with rewarded samples.
The study of these mechanisms is facked-up with formal proofs in simplified context where the effects of function approximation is ignored. Nevertheless, the resulting understanding helps analyzing the practical phenomena encountered when using actors and critics represented as neural networks. From this new light, we revisit in Section a few existing algorithms whose components provide an alternative to the building blocks involved in the undesirable cyclic convergence process, and we suggest alternative solutions to these issues.
RELATED WORK
Issues when combining RL with function approximation have been studied for long time (Baird & Klopf T993 Boyan & Moore 1995 Tsitsiklis & Van Roy 1997). In particular, it is well known that

---

Under review as a conference paper at ICLR 2020
deep RL algorithms can diverge when they meet three conditions coined as the "deadly triad" (Sutton & Barto 2018), that is when they use (1) function approximation, (2) bootstrapping updates and (3) mostly studied in the continuous state, discrete action case. For instance, several recent papers have studied the mechanism of this instability using DQN (Mnih al. (013). In this context, four failure modes have been identified from theoretical point of view by considering the effect of a linear approximation of the deep-Q updates and by identifying conditions under which the approximate updates of the critic are contraction maps for some distance over Q Q-functions (Achiam et al. 2019). Meanwhile, van Hasselt et al. (2018) shows that, due to its stabilizing heuristics, DQN does not diverge much in practice when applied to the ATARI domain.
off-policy learning. However, these questions
In contrast to these papers, here we study failure mode specific to continuous action actor-critic algorithms. It hinges on the fact that one cannot take the maximum over actions, and must rely on the actor as a proxy for providing the optimal action instead. Therefore, the failure mode identified in this paper cannot be reduced any of the ones that affect DQN. Besides, the theoretical derivations provided in the appendices show that the failure mode we are investigating does not depend on function approximation errors, thus it cannot be directly related to the deadly triad.
More related to our work, several papers have studied failure to gather rewarded experience from the environment due poor exploration (Colas et al. 2018 Fortunato et al. 2017: Plappert et al. 2017). but we go beyond this issue by studying case where the reward is actually found but not properly exploited. Finally, like us the authors of Fujimoto et al. (2018a) study failure mode which is specific to DDPG-like algorithms, but the studied failure mode is different. They show under batch learning regime that DDPG suffers from an extrapolation error phenomenon, whereas we are in the more standard incremental learning setting and focus on deadlock resulting from the shape of the Q-function in the sparse reward case.
BACKGROUND: DEEP DETERMINISTIC POLICY GRADIENT
The DDPG algorithm (Lillicrap al. 2015) is a deep RL algorithm based on the Deterministic Policy Gradient theorem (Silver et al. 2014). It borrows the use of replay buffer and target networks from DQN (Mnih al.] 2015). DDPG is an instance of the Actor-Critic model. It learns both an actor function Te (also called policy) and a critic function Qe. represented as neural networks whose parameters are respectively noted & and 0.
The deterministic actor takes a state E S as input and outputs an action E A. The critic maps each state-action pair (s, a) value in R. The reward S x A + R, the termination function t: S x A- + {0, 1} and the discount factor < 1 are also specified as part of the environment.
The actor and critic are updated using stochastic gradient descent on two losses Ly and Lg. These losses are computed from mini-batches of samples (si, a,, Ti, f,, 9;-1), where each sample corre- sponds to a transition 8; + 8;-1 resulting from performing action a; state 8,, with subsequent reward r; = r(s;, a;) and termination index f; = t(s;, a.).
Two target networks Ti. and Qø are also used in DDPG. Their parameters &f and 6' respectively track s and 0 using exponential smoothing. They are mostly useful to stabilize function approximation when learning the critic and actor networks. Since they do not play a significant role the phenomena studied in this paper, we ignore them in the formal proofs given in appendices.
Equations I and 2 define Ly and Lg:
L =
Σ Qo (St, To (st)
Vi, v1 7(1 +t) (s1+1,
Toy Thy (s++1)
La = Σ Qo (st, -Vi
(2)
Training for the loss given in (1) yields the parameter update in 3 with the learning rate:
2

---

Under review as a conference paper at ICLR 2020
(si) O
QaQo(s; a) a=m(())))
As DDPG uses a replay buffer, the mini-batch samples are acquired using behaviour policy / which may be different from the actor и. Usually, 3 is defined as и plus noise distribution, which in the case of DDPG is either Gaussian function the more sophisticated KinsteinUUhlenbed noise.
Importantly this paper, the behaviour of DDPG can characterized as an intermediate between two extreme regimes:
When the actor is updated much faster than the critic, the policy becomes greedy with respect to this critic, resulting into behaviour closely resembling that of the Q-LEARNING algorithm. When it is close to this regime, DDPG can be characterized as off-policy.
When the critic is updated much faster than the actor, the critic tends towards Q7 a). The problems studied in this paper directly come from this second regime.
A more detailed characterization of these regimes in given in Appendix A
A NEW FAILURE MODE
In this section, introduce simplistic environment which we call ID-TOY. is one-dimensional, discrete- time, continuous state and action problem, depicted in Figure [
90
0.1
0.1
S 0. 1]
(4a)
A = -0.1,
(4b)
So 0
(4c)
=
left
right
S1+1 = min (1, max (0, +a))
(4d)
Tt = t t..
(4e)
Figure 1: The 1D-TOY environment
Despite its simplicity, DDPG fail on ID-TOY. We first show that DDPG fails reach 100% success. We then show that learning policy does not succeed soon enough, the learning process get stuck. Besides, show that the initial actor be significantly modified in the initial stages before finding the first reward. We explain how the combination of these phenomena can result into deadlock situation. We generalize this explanation any deterministic and sparse reward environment by revealing and formally studying a undesirable cyclic process which arises in such cases. Finally, explore the consequences of getting into this cyclic process.
4.1 EMPIRICAL STUDY
In all experiments, set the maximum episode length N to 50, but the observed phenomena persist with other values.
Residual failure converge using different noise processes We start by running DDPG on the ID-TOY environment. This environment is trivial as one infinitesimal step to the left is enough to obtain the reward, end the episode and succeed, thus we might expect quick 100% success. However, the first attempt using 94% cases, see Figure 2a
(OU) noise process shows that DDPG succeeds in only
These failures might come from exploration problem. Indeed, at the start of each episode the OU noise process reset to zero and gives little noise in the first steps of the episode. In order to remove this potential source of failure, replace the OU noise process with an exploration strategy similar to e-greedy which we call "probabilistic noise". For some < < 1, with probability p. the action is randomly sampled (and the actor ignored), and with probability p no noise used

---

Under review as a conference paper at ICLR 2020
100
100
% of suocessful runs
98
95
90
Probabilistic noise
% of
94
Baseline
85
OU noise
Switch to after 20k steps
92
0
20k
40k
60k
80k
100k
20k
40k
60k
80k
100k
Simulation steps
Simulation steps
(a) Success rate of DDPG with Orstein-Uhllebbed (OU) and probabilistic noise. Even with probabilis- and a variant in which the behaviour policy is set to the tie noise, DDPG fails on about 1% of the seeds.
(b) Comparison between DDPG with prohabilistic noise
optimal policy a' after 20k steps.
Figure 2:
Success rate of variants of DDPG on ID-TOY over learning steps, averaged over 10k seeds. More details on learning algorithm and success evaluation are given in Appendix
and the raw action returned. In our tests, we used p = 0.1. This guarantees at least 5% chance of success at the first step of each episode, for any policy. Nevertheless, Figure [ shows that even with probabilistic noise, about 1% of seeds still fail to converge to successful policy in ID-TOY, even after 100k training steps. All the following tests are performed using probabilistic noise.
We now focus on these failures. On all failing seeds, we observe that the actor has converged to a saturated policy that always goes the right (Vs, (Ts) 0.1). However, some mini-batch samples have non-zero rewards because the agent still occasionally moves to the left, due to the probabilistic noise applied during rollouts. The expected fraction of non-zero rewards slightly more than 0. % Figure 3a shows the occurrence of rewards in minibatches taken from the replay buffer when training DDPG on D-TOY. After each rollout (episode) of steps. the critic and actor networks are trained times on minibatches of size 100. So for instance, a failed episode of size 50 is followed by a training on a total of 5000 samples, out of which we expect more than in average are rewarded transitions. More details about the implementation are available in Appendix E
The constant presence of rewarded transitions in the minibatches suggests that the failures of DDPG on this environment are not due to insufficient exploration by the behaviour policy.
Correlation between finding the reward early and finding the optimal policy We have shown that DDPG can get stuck in ID-TOY despite finding the reward regularly. Now we show that when DDPG finds the reward early in the training session, it is also more successful in converging to the optimal policy.
the other hand, when the first reward is found late, the learning process more often gets stuck with sub-optimal policy.
From Figure 3b the early steps appear to have a high influence on whether the training will be successful or not. For instance, if the reward is found in the first 50 steps by the actor noise (which happens in 63% of cases), then the success rate of DDPG is 100%. However, the reward is first found after more than 50 steps, then the success rate drops to 96%. Figure 33b shows that finding the reward later results lower success rates, down to 87% for runs which the reward was not found in the first 1600 steps. Therefore, we claim that there exists critical time frame for finding the reward in the very early stages of training.
Spontancous actor drift At the beginning of each training session, the actor and critic of DDPG initialized represent respectively close-to-zero state-action values and close-to-zero actions. Besides, as long as the agent does not find a reward, it does not benefit from any utility gradient. Thus we might expect that the actor and critic remain constant until the first reward is found. Actually, we
'10% of steps are governed by probabilistic noise, of which at least 2% are the first episode step, of which 50% steps going the left and leading the reward.
4

---

Under review as a conference paper at ICLR 2020
Reward samples used in training
% failed runs after 100k steps
Normalized occurrence rate
10
15%
15
10
10%
5
10
5%
10-5
0%
0
25k
50k
75k
100k
102
10a
Steps
Step of earliest reward found
(a)
(b)
Figure 3: (a) Number of rewards found in mini-batches during training. After a rollout of n steps, the actor and critic are both trained on minibatches of size 100. The red dotted line indicates average of 6.03 rewarded transitions present in these n minibatches. (b) red, normalized probability of finding the earliest reward this step. In blue, for each earliest reward bin, fraction of these episodes that fail to converge to good actor after 100k steps. Note that when the reward is found after one or two episodes, the convergence successful actor is certain.
show that even in the absence of reward, training the actor and critic triggers non-negligible updates that cause the actor to reach a saturated state very quickly.
To investigate this, we use variant of 1D-TOY called DRIFT where the only difference is that no rewarded or terminal transitions are present the environment. We also use stripped-down version of DDPG, removing rollouts and using random sampling of states and actions minibatches for training.
0.10
0.10
muxx (Q]
0.05
0.05
0.00
50
100
150
200
50
100
150
200
Step
Step
(a)
(b)
Figure 4: Drift of max IQ] and max |r| in the DRIFT environment, for 10 different seeds. In the absence of reward, the critic oscillates briefly before stabilizing. However, the actor very quickly reaches saturated state, at either Vs, π (s) 0.1 or -0.1.
Figure 4b shows that even in the absence of reward, the actor function drifts rapidly (notice the horizontal scale in steps) to saturated policy, in number of steps comparable to the "critical time frame" identified above. The critic also has transitive phase before stabilizing.
In Figure 4a| the fact that maxş,a [Q(s, a) can increase in the absence of reward can seem counter- intuitive, since in the loss function presented in Equation 2 [3:| can never be greater than max,,a Q( a.). However, it should be noted that the changes made Q are not local to the minibatch points, and increasing the value of Q for one input (s, a) may cause its value to increase for other inputs too, which may cause increase in the global maximum of Q. This phenomenon is at the heart of the iver-estimation bias when learning a critic (Fujimoto et al.] 2018b), but this bias does not play key role here.

---

Under review as a conference paper at ICLR 2020
010.al
7.ll
1.5
0.1
-0.1
0.0
0.0
(a) Critic values the deadlock configuration. The critic is non-zero only in the region that immedi- ately leads to reward (s < 0)
(b) Two snapshots of the critic for different states in a failed run. The high Q values in the s + a < 0 region propagated.
Figure 5: Visualization of the critic a failing run, in which the actor is stuck to Vs, (s) = 0.1.
Vo, VaQlo, a=nt
init.
drif:
(s, 0.1
((s,a) converges to
a
(ssa))(s,a)
does not change)
Figure 6: Deadlock observed in ID-TOY, represented as the cycle of red arrows.
4.2 EXPLAINING THE DEADLOCK SITUATION FOR DDPG ON ID-TOY
Up have shown that DDPG fails about 1% of times ID-TOY, despite the simplicity of this environment. We have now collected the necessary elements to explain the mechanisms of this deadlock in ID-TOY.
Figure shows the value of the critic in a failed run of DDPG on ID-TOY. We see that the value of the reward is not propagated correctly outside of the region in which the reward is found in a single step {(s, a) 8 a < 0}. The key of the deadlock is that once the actor has drifted to Vs, (s) 0.1, is updated according V.Qo a))a=z,(ss) (Equation (3)) Figure 5b shows that for a = (s)) = 0.1, this gradient is zero therefore the actor is not updated. Besides, the critic is updated using 1/4 r(s,,a) a,) + QQ(s (s{))
target. Since Q(s,, 0.1) is zero, the critic only needs to be non-zero for directly rewarded actions, and for all other samples the target value remains zero. In this state the critic loss given in Equation (2) is minimal, there is further update of the critic and no further propagation of the state-action values. The combination of the above two facts clearly results deadlock.
Importantly, the constitutive elements of this deadlock do not depend on the batches used to perform the update, and therefore do not depend on the experience selection method. We tested this experi- mentally by substituting the behaviour policy for the optimal policy after 20k training steps. Results are presented in Figure 2b and show that, once stuck, even when it given ideal samples, DDPG stays stuck in the deadlock configuration. This also explains why finding the reward early results in better performance. When the reward is found early enough, π (so) has not drifted too far, and the gradient of Q(50, a) at л (*0) drives the actor back into the correct direction.
Note however that even when the actor drifts to the right, DDPG does not always fail. Indeed, because of function approximators the shape of the critic when finding the reward for the first time varies, and sometimes converges slowly enough for the actor to updated before the convergence of the critic.
Figure 6 summarizes the above process. The entry point is represented using green dot. First, the actor drifts to Vs, (s)) = 0.1, then the critic converges to Q" which is a piecewise-constee function (Experiment in Figure 5 proof in Theorem I in Appendix [B), which in turn means that the critic provides no gradient, therefore the actor is not updated (as seen Equation 3 more details in Theorem
4.3
GENERALIZATION
Our study of DD-TOY revealed how DDPG can get stuck in this simplistic environment. We now generalize to the broader context of more general continuous action actor critic algorithms, including
Note that Figure shows critic state which is slightly different from the one presented in Figure 6 due to the limitations of function approximators.

---

Under review as a conference paper at ICLR 2020
Inil: reward nol found
Deterministic policy gradient update
drifts to pour policy
Q (s.4))a))) =
x barely changes
=
+10(0(x(6))
2i piecewise-coustaan
tends towards Q"
sparse reward
pissewiie-ccosslaut
Figure 7: A cyclic view of the undesirable convergence process in continuous action actor-criti algorithms, in the deterministic and sparse reward case.
at least DDPG and TD3, and acting in any deterministic and sparse reward environment. The generalized deadlock mechanism is illustrated in Figure 7 and explained hereafter in the idealized context of perfect approximators, with formal proof's rejected in appendices.
Entry point: As shown in the previous section, before the behaviour policy finds any reward, training the actor and critic can still trigger non-negligible updates that may cause the actor to quickly reach a poor state and stabilize. This defines our entry point the process.
Q tends towards Q A first step into the cycle is that, if the critic is updated faster than the policy, the update rule of the critic Q given in Equation makes Q converge to Q". This presented in detail in Appendix C
QT is piecewise-constant: In Appendix D we then show that, in deterministic environment with sparse terminal rewards, Q" is piecewise-constant because V=(s") only depends two things: the (integer) number of steps required to reach rewarded state from 8', and the value of this reward state, which is itself precewise-constart rewards, by making the stronger hypothesis on the actor that Vss, r(s, (s)) = 0. Notably, this is the case for the actor Vs, (s) 0.1 on ID-TOY.
Note that we can reach the same conclusion with non non-termin terminal
Q is approximately piecewise-constane and Va Q (ss. R 0: Quite obviously, from Q" is piecewise-constant and Q tends towards Q*, we can infer that Q progressively becomes almost as the cyclic process unfolds. Actually, the Q function estimated by a function approximator which is never truly discontinuous. The impact of this fact is studied in Section 4.5 However, we can expect Q to have mostly flat gradients since it is trained to match a piecewise- constant function. We can thus infer that, globally, VaQ(s, a)la= & 0. And critically, the gradients in the flat regions far from the discontinuities give little information to how to reach regions of higher values.
barely changes: DDPG uses the deterministic policy gradient update, as seen in Equation (3) This is an analytical gradient that does not incorporate any stochasticity, because Q is always differentiated exactly (s, (s)). Thus the actor update is stalled, even when the reward is regularly found by the behaviour policy. This closes the loop of our process.
4.4 CONSEQUENCES OF THE CONVERGENCE CYCLE
As illustrated with the red arrows in Figure 7 the more the critic tends to be piccewise-constan this cyclic convergence process is triggered as soon as the changes on the policy drastically slow down or stop. What matters for the final performance is the quality of the policy reached before
the more loops performed in the convergence process,
and the less the actor tends change. Importantly,

---

Under review as a conference paper at ICLR 2020
0.032
0.032
Q" dd
1.0.7.)
Q
0.030
0.030
030.8)
0.026
-0.1
0.0
0.1
0.0 0.1
"T"""
(a)
(b)
Figure 8: (a) Example a monotonous function approximator. (b) Simply changing the vertical scale of the graphs presented in re that the function approximator is not perfectly flat, and has many unwanted local extrema. Specifically, continuously moving from π (0)) = 0.1 to (0) < 0 requires crossing a significant valley in Q(0, a), while x (0) 0.1 is strong local maximum.
this convergence loop is triggered. Quite obviously, if the loop is triggered before the policy gets consistently rewarded, the final performance is deemed to be poor.
The key of this undesirable convergence cycle lies in the use of the deterministic policy gradient update given in Equation (3). Actually, rewarded samples found by the exploratory behaviour policy 99 tend to be ignored by the conjunction of two reasons. First, the critic is updated using Q(s', ((s') and not (s,, (s)), thus if differs much from 33 the values brought by 3 are not properly propagated. Second, the actor being updated through (3), i.c. using the analytical gradient of the critic with respect to the actions of IT, there no room for considering other actions than that of Besides, the actor update involves only the state of the sample taken from the replay buffer, and not the reward found from this sample r(s, a) or the action performed. For each sample state s, the actor update is intended to make (s) converge to argmax, π (s, a) but the experience of different actions performed for identical or similar states only available through Q(s, :). and DDPG is only exploited through the gradient of (s,,.) at (T)), so the process can easily get stuck in local optimum, especially if the critic tends towards a piecewise-constaal function, which as we have shown happens when the reward is sparse. Besides, since TD3 also updates the actor according to and the critic according to 2 it is susceptible to the same failures as DDPG.
4.5 IMPACT OF FUNCTION APPROXIMATION
We have just explained that when the actor has drifted to incorrect policy before finding the reward, an undesirable convergence process should result in DDPG getting stuck to this policy. However, in 1D-TOY, we measured that the actor drifts to a policy moving to the right in 50% of cases, but the learning process only fails 1% of times. More generally, despite the issues discussed in this paper, DDPG has been shown to be efficient many problems. This setter-than-prediicee success can be attributed to the impact of function approximation.
Figure Sa shows a case in which the critic approximates Q" while keeping monotonous slope between the current policy value and the reward. In this case, the actor is correctly updated towards the reward (if is close enough to the discontinuity). This is the most often observed case, and naturally expect approximators to smooth out discontinuities in target functions in a monotonous way, which facilitates gradient ascent. However, the critic is updated not only in state-action pairs where Q" (s, a) is positive, but also points where Q" (s, a) O, which means that the bottom part of the curve also tends to flatten. As this happens, we can imagine phenomena that are common when trying approximate discontinuous functions, such the overshoot observed in Figure 8b In this case, the gradient prevents the actor from improving.
5 POTENTIAL SOLUTIONS
In the previous section, we have shown that actor-critic algorithms such as DDPG and TD3 could not recover from early convergence poor policy due the combination of three factors whose
8

---

Under review as a conference paper at ICLR 2020
Por deiiii
63-
DOPGa SPERS
DEPGaggaa
DEIG
64-
30-
1000
231
1000
1.00
Simclation
(a)
(b)
(C)
(d)
Figure 9: (a) Applying DDPG- argmax to ID-TOY. (b) Applying SAC to ID-TOY. In both cases, the success rate reaches 100% quickly. (c) Applying DDPG and DDPG-argmax to sparse-reward variant of the REACHER-V2 environment. (d) Applying DDPG and DDPG-argmax to a sparse-reward variant of the HALFCHEFTAH-V2 environment. Details on the changes made to REACHER-V2 V2 and HALFCHBETAH-V2 v2 are available in Appendix F2
dependence is highlighted in Figure 7 the use of the deterministic policy gradient update, the use of Q(s', (s')) in the critic update, and the attempt to address sparse reward in deterministic environments. In this section, we categorize existing or potential solutions to the above issue in terms of which of the above factor they remove.
Avoiding sparse rewards: Transforming a sparse reward problem into a dense one can solve the above issue as the critic should not converge piecewise-constan function anymore. This can be achieved for instance by using various forms of shaping (Konidaris & Barto 2006) or by adding auxiliary tasks (Jaderberg et al. 2016, Riedmiller et al., 2018). We do not further investigate these solutions here, as they are mainly problem-dependers and may introduce bias when the reward transformation results in deceptive gradient or modifies the corresponding optimal policy.
Replacing the policy-based critic update: As explained above, if some transition (s, a, s') leading to a reward is found in the replay buffer, the critic update corresponding to this transition uses Q(s', (ss"),, therefore not propagating the next state value that the behaviour policy may have found. Of course, when using the gradient from the critic, the actor update should tend to update π to reflect the better policy such that (s") + a', but the critic does not always provide an adequate gradient as shown before.
If performing maximum of Q(s', ,ss')) would solve the issue Several works start from this insight. Some methods directly sample the action space and look for such approximate maximum (Kalashnikov et al., 2018 Simmons-Edde et al.) 2019). To show that this approach can fix the above issue, we applied it to the ID-TOY environment. We take straightforward implementation where the policy gradient update in DDPG is replaced by sampling 100 different actions, finding the argmax over these actions of Q(s,a), a), and regressing the actor towards the best action we found. We call the resulting algorithm DDPG-argmax, and more details are available in Appendix F.1 Results are shown in Figure Ya in which we see that the success rate quickly reaches 100%.
continuous action space was possible, using max, Q(s', a) instead
Quite obviously, even if sampling can provide good enough baseline for simple enough benchmarks, these methods do not scale well to large actions spaces. Many improvements to this can be imagined by changing the way the action space is sampled, such as including ((s) in the samples, to prevent picking a worse action than the one provided by the actor, sampling preferentially around T(s). or around (s + +), just using actions taken from the replay buffer.
Interestingly, using stochastic actor such as the Soft Actor Critic (SAC) algorithm (Haarnoja al. 2018a b) can be considered as sampling preferentially around rTss + e) where is driven by the entropy regularization term. In Figure 9b] we show that SAC also immediately solves ID-TOY.
Another approach relies representing the critic as the V function rather than the Q function. The same way (s)) tends to approximate argmax, ((s, a). V tends to approximate max, Q(s, a), and is updated when finding transition that raises the value of state. Using V. performing maximum in the critic update is not necessary anymore. The prototypical actor-critic algorithm using a model of V as critic is CACLA (Van Hasselt & Wiering 2007). However, approximating V with neural

---

Under review as a conference paper at ICLR 2020
networks can prove more unstable than approximating Q, function approximation can be sensitive to the discontinuities resulting form the implicit maximization over Q values.
Replacing the deterministic policy gradient update: Instead of relying on the deterministic policy gradient update, one can rely on a stochastic policy to perform different actor update. This is the case of SAC, as mentioned just above. Because SAC does not use Q xss)) in its update rule, it does not suffer from the undesirable convergence process described here.
Another solution consists in completely replacing the actor update mechanism. using regression to update π (s) towards any action better than the current onc. This could be achieved by updating the actor and the critic simultaneously: when sampling higher-than--xpectel critic value ys > Q(1;, dz), one may update r(ss) towards Og using:
L Σ yy Q(sn(((()))) (I((;) a.)
(5)
This is similar to the behaviour of CACLA, as analyzed in Zimmer & Weng (2019)
Larger benchmarks Whether the deadlock situation investigated so far occurs more in more complex environments is an important question. To investigate this, we performed additional experiments based on more complex environments, namely sparse versions of REACHER-V v2 and HALFCHEETAH- V2. Results are depicted Figure 9c and 9d and more details are presented in Appendix F2 One can see that DDPG-argmas outperforms DDPG, which seems to indicate that the failure mode we are studying is also at play. However, with higher-dimensional and more complex environments, the analysis becomes more difficult and other failures modes such as the ones related to the deadly triad, the extrapolation error or the over-estimation bias might come into play, so becomes harder to quantitatively analyze the impact of the phenomenon we focusing on. On one hand, this point showcases the importance of using very elementary benchmarks in order to study the different failure modes in isolation. On the other hand, trying to sort and quantify the impact of the different failure modes in more complex environments is our main objective for future work.
CONCLUSION AND FUTURE WORK
In RL, continuous action and sparse reward environments are challenging. In these environments, the fact that a good policy cannot be learned if exploration is not efficient enough to find the reward well-known and trivial. In this paper, we have established the less trivial fact that, if exploration does find the reward consistently but not early enough, an actor-critic algorithm can get stuck into a configuration from which rewarded samples are just ignored. We have formally characterized the reasons for this situation and we have outlined existing and potential solutions. Beyond this, we believe our work sheds new light on the convergence regime of actor-critic algorithms.
Our study was mainly built on a simplistic benchmark which made it possible to study the revealed deadlock situation in isolation from other potential failure modes such as exploration issues, the over-estimation bias, extrapolation eтror or the deadly triad. The impact of this deadlock situation in more complex environments the impact of these different failure modes. Using new tools such as the ones provided in Ahmed ct al. (2019), recent analyses of the deadly triad such as Achiam et al. (2019) as well as simple, casily visualized benchmarks and our tools, for future work we aim to conduct deeper and more exhaustive analysis of all the instability factors of DDPG-like algorithms, with the hope to contribute in fixing them.
pressing question. For this, we need to sort out and quantify
7 ACKNOWLEDGEMENTS
Anonymized for submission.
REFERENCES
Joshua Achiam, Ethan Knight, and Pieter Abbeel. Towards Characterizing Divergence in Deep O-Learning arXiv: 08899 [cs], March 2019. URL httt:: http:///xxxxv.xxx/abbba
08894 arXiv: 1903.08894.
10

---

Under review as a conference paper at ICLR 2020
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understanding the impact of entropy on policy optimization. In International Conference on Machine Learning, pp. 151-160, 2019.
L. C. Baird and A. H. Klopf. Reinforcement learning with high-dimensional, continuous actions. Technical report, Wright-Patterss Air Force Base Ohio: Wright Laboratory. (Available from the Defense Technical Information Center, Cameron Station, Alexandria, VA 22304-6145), 1993.
Justin A. Boyan and Andrew W. Moore. Generalization in reinforcement learning: Safely approxi- mating the value function. In Advances in neural information processing systems, pp. 369-376, 1995.
Cédric Colas, Olivier Sigaud, and Pierre-Yve Oudeyer. GEP-PG:
Decoupling Exploration and Exploitation in Deep Reinforcement Learning Algorithms. In International Conference in Machine Learning (ICML), February 2018. URL https:/ http//aaxvvvvvv org/ abs/ 0t0.://rri....////////88000000 05054
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, Charles Blundell, and Shane Legg. Noisy Networks for Exploration. arXiv: 170. 10295 [cs, staf], June 2017. httthhtt:///att
org/abs/ 706. 10295
arXiv: 1706. 10295.
Scott Fujimoto, David Meger, and Doina Precup. Off-Policy Deep Reinforcement Learning without Exploration. arXiv: 18 02900 [cs, stat), December 2018a. htt.htttp://arx/w.orrg///// 1812. 02900
arXiv: 1812.02900.
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing Function Approximation Error in Actor-Critic Methods. http:://arxivvorr/aas////// 094704777 February 2018b.
M. Geist and O. Pietquin. Parametric value function approximation: A unified view. In 2011 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL), pp. 9-16, April 2011. 1. doi: 10.1 00.100//DDPRL.2011.55666
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with Stochastic Actor, arX.v:1801.01290 [cs, star], January 2018a. URL /RLL:tt////a/xivcooo
abs wwt../111....00 01290
arXiv: 1801.01290.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and applications. arXiv preprint arXiv: 2018b.
Max Jaderberg, Volodymyr Mnih, Wojeiech Marian Czarnecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. arXiv preprint 1..3397 05397, 2016.
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et al. Qt-Opt: Scalable deep reinforcement learning for vision-based robotic manipulation. arXiv preprint arXiv: 1806.10233 2018.
George Konidaris and Andrew Barto. Autonomous shaping: learning. In Proceedings of the 23rd international conference on Machine learning, pp. 489-496. ACM, 2006.
Knowledge transfer in reinforcement
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learn- ing. 1.Xiv:1509.022 [cs, stat), September 2015. httl:ttpp//aaxx.oo///aa..////// 02971
arXiv: 1509.02971.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou. Daan Wier- stra, and Martin Riedmiller. Playing Atari with Deep Reinforcement Learning. arXiv:1312.5600 /cs/, December 2013. htttepp//aaxiiv.oo//ab/////////
5602 arXiv: 1312.5602.

---

Under review as a conference paper at ICLR 2020
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. RUsu, Joel Veness, Mare G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, loannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529 533, February 2015. ISSN 1476-4687. doi: 0.11038/ntture14233 URL
wttp::::www.natueee. www.raatuue... com/ http://www..aurrrooooooaaaaaaaaa
Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Y. Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marcin Andrychowicz. Parameter space noise for exploration. arXiv preprint arXiv: /706.0/90, 2017.
Martin Riedmiller, Roland Hafner, Thomas Lampe, Michael Neunert, Jonas Degrave, Tom Van de Wiele, Volodymyr Mnih, Nicolas Heess, and Jost Tobias Springenberg. Learning by Playing Solving Sparse Reward Tasks from Scratch. arXiv: 802. /0567 [cs, stat], February 2018. URL
10567
arXiv: 1802. 10567.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic Policy Gradient Algorithms. In International Conference on Machine Learning. pp. 387-395, January 2014. URR.hhtpp:/pprceeeiiiii ml ptwps/rss/sssssse wttp://////m..rrrp///////3
1ver14
html
Riley Simmons-Edde Ben Eisner, Eric Mitchell, Sebastian Seung, and Daniel Lee. Q-learning for continuous actions with crosspentropy guided policies. arXiv preprint arXiv: 2019.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, November 2018. ISBN 978-0-262-03924-6 Google-Books-ID: 6DKPIQEACAAJ.
John N. Tsitsiklis and Benjamin Van Roy. Analysis of -iffffreence learning with function approximation. In Advances neural information processing systems, pp. 1075 1081, 1997.
Hado Van Hasselt and Marco A. Wiering. Reinforcement learning continuous action spaces. In IEEE International Symposium Approximate Dynamic Programming and Reinforcement Learning (ADPRL), pp. 272-279,2000
Hado van Hasselt, Yotam Doron, Florian Strub, Matteo Hessel, Nicolas Sonnerat, and Joseph Modayil. Deep Reinforcement Learning and the Deadly Triad. arXiv: 026488 [cs], December 2018. URL http::ttt///xiii org 1812. 02648 arXiv: 1812.02648.
Christopher J. C. H. Watkins. Learning with Delayed Rewards. PhD thesis, Psychology Department, University of Cambridge, England, 1989.
Matthicu Zimmer and Paul Weng. Exploiting the sign of the advantage function to learn deterministic policies in continuous domains. arXiv preprint 1eXiv:1906.044 2019.
12

---

Under review as a conference paper at ICLR 2020
A TWO REGIMES OF DDPG
In this section, we characterize the behavior of DDPG as an intermediate between two extremes, that respectively call the critic-centric view, where the actor is updated faster, resulting in an algorithm close to Q-LEARNING, and the actor-centric view, where the critic is updated faster, resulting in a behaviour more similar to Policy Gradient.
A.1 ACTOR UPDATE: THE CRITIC- VIEW
The Q-LEARNING algorithm (Watkins 1989) and its continuous state counterpart DQN (Mnih et al. 2013) rely on the computation of policy which is greedy with respect to the current critic every time step, as they simply take the maximum of the Q-values over set of discrete actions. In continuous action settings, this amounts an intractable optimization problem if the action space is large and nontrivial.
We get a simplified vision of DDPG by considering an extreme regime where the actor updates are both fast enough and good enough so that Vs, (s) a argmax, Q(s,a) a). We call this the crific-centric vision of DDPG, since the actor updates are assumed to ideal and the only remaining training is performed on the critic.
In this regime, by replacing (s) with argmax, Q(s, a) in Equation (2,, we get = ri + 7(1 4;) max, (8s, a). which corresponds to the update of the critic in Q-LEARNING and DQN. A key property of this regime is that, since the update in based on a maximum over actions, the resulting algorithm is truly off off-policy. We can thus infer that most of the off off-policiness property of DDPG comes from keeping close to this regime.
A.2 CRITIC UPDATE: THE ACTOR ACTOR-CENTRIC VIEW
Symmetrically the previous case, if the critic is updated well and faster than the actor, tends represent the critic of the current policy, Q". Furthermore, if the actor tends to change slowly enough, critic updates can be both fast and good enough that it reaches the fixed point of the Bellman equation, that is v(s, a, r, s'), Q(s, a) = r + 7(1 t)Q(s', (ss)).
In this case, the optimization performed in ( mostly consists in updating the actor so that it exploits the corresponding critic by applying the deterministic policy gradient on the actor. This gives rise to a actor-centric vision of DDPG.
B DEADLOCK IN 1D-TOY
In this section, we prove that there exists state of DDPG that is a deadlock in the ID-TOY environment. This proof directly references Figure Let us define two functions Q and FΦ. such that:
((s, a), Q(s a) 1.+a<0
(6)
Vs E T 0.1
From now we will use notation π Tw. Theorem 1. (Q. is fixed point for the critic update.
Proof. The critic update is governed by Equation
Let (8i, ae, ri, 4i, 8)) be a sample from the replay buffer. The environment dictates that r; = 4 = 1s
8/ = ri + 71 (1(11+))010 (s
8/1 = mi + 7(1 (t)+-t))000 (s/,
by
y/
by
y/ = 1a+ta.00
y/ Q(si,
by
13

---

Under review as a conference paper at ICLR 2020
Therefore, for each sample y/1 Q(s:: a;), and L is null and minimal. Therefore 0 will not be updated during the critic update.
Theorem 2. (Q.TT) is fixed point for the actor update.
Proof. The actor update governed by Equation 3
Let {s1 04; Ta, 4, 8()) be set of samples from the replay buffer. The environment dictates that Vi, T4 t2 = 10.to.c0-
(Tp(
1b 1/ +
Oip
Since Q(8;, a) sttaco VaQ(s;, a) = 0, so 1a will not be updated during the actor update.
In this section, we assume that Q is any function, however in implementations Q is often parametric neural network Qo. which cannot be discontinuous. Effects of this approximation are discussed in Section 4.5
C
CONVERGENCE OF THE CRITIC TO Q"
Notation For state-action pair s, a, we define $1 as the result of applying action state in the deterministic environment. For given policy т, we define a1 as π (s1)). Recursively, for any 2 1, we define 8 as the result of applying action a state 8;, and ag as n (s:).
Definition 1. Let (s, a) E S A. If (s, a) terminal. then we set N the number of subsequent transitions with policy ı to reach a terminal state. Therefore, the transition (sN, ( is always terminal. We generalize by setting N oo when no terminal transition is ever reached.
Otherwise, we to
We define the state-action value function of policy क as:
N
( Σ (r)(s,
Note that when N oc, the sum converges under the hypothesis that rewards are bounded and y < 1.
If is fixed, Q is updated regularly via approximate dynamic programming with the Bellman operator
for the policy æ. Under strong assumptions, or assuming exact dynamic programming. it is possible to prove (Geist & Pietquin (201T)) that the iterated application of this operator converges towards unique function Q", which corresponds to the state-action value function of т as defined above. usually done by proving that the Bellman operator is contraction mapping, and also applies in deterministic cases.
However, when using approximators such neural nets, theroretical results of convergence exists, to the best of our knowledge. In this paper we assume that this convergence is true, and in the experimental results did observe any failures converge towards Q=, On the contrary, observe that this converge occurs, and can be what starts the deadlock cycle studied in Section 4.3
D PROOF THAT Q" PIECEWISE-CONSTANT
In this section, show that in deterministic environments with terminal sparse rewards, Q" is piecewise-constan.
Definition 2. this article, for C. RR" we say a function f + RR is piecewise-constant
Van 7, either V. (w)) 0, has no gradient at 20-
14

---

Under review as a conference paper at ICLR 2020
1.5
1.0
0.5
0.0
00.
-1.0
-1.5
-1.0
-0.5
0.0
0.5
1.0
Figure 10: Example of non-continuous function f with values in (())" n N). approximating the identity function. However, this function is not differentiable because the difference quotient does not converge but instead oscillates between two values.
Theorem 3. In deterministic environment with terminal sparse rewards, for any æ, Q" is piecewise- constant.
Proof. Note that this proof can be trivialized by assuming that around any point where the gradient defined, there exists neighbourhood in which the function is continuous. In this case, the intermediate value theorem yields an uncountable set of values of the function this neighbourhood. which contradicts the countable number of possible discounted rewards.
The crux of the following proof is that even when no such neighbourhood exists, the gradient either null of non- existentt... This behavior is shown in Figure I0
Using the notations Definition and the theorem hypothesis that rewarded transitions are also terminal, write Q"I (s, a) as:
a(),a) 7 ((N,,
N
(s
if N is finite otherwise.
We promote N to function S A NU [+oO), and we define function u: 5 A -> R as given in Equation 8
r(8,a) a) r (SN(a.a), AN().))
if =
a(s
if N > 0 finite otherwise.
(8)
Now have a(s E A, (s, = N(s,0)((ss))
Let R be the finite set possible reward values.
Therefore values of Q" in set M {>"r E R}. Let M M n R be the set of positive values of M. Since R C finite, we order all non-zero positive possible rewards in increasing order F1, r2, Tk-
Let M = "r n MEN, E R&) where R4 = (r1, r
We prove the following by recurrence the number of possible non-zero rewards:
H(k) Fv,
vg 0, consecutive b, E Mt. duz < bb and b <
15

---

Under review as a conference paper at ICLR 2020
Initialization
When 1, M+
frin" n Let v -
Let 0. Let n
[logy A + 1. We have:
8
log.
< S log,
7
8
5
log,
< n < log,
+ log, (1- + log, -))
11
7l
8
8(1 7)
logy
< n < log,
+ +log, V
71
8
dv(1 - 7)
log,
< log,
11
50(1 -1) <7" <
6v(1 - 7) < <ri 7) 8(1 - 7)
óv < knn" - n+1 and ri7" <
Let a r17" E M and = rny E M+ du < a- and b < a < é therefore H(1 is verified.
Recurrence Let k 2 1, and assume (kk) is true. Let va be the chosen for Hk). Let Uk+1 Let 8 > Let bk, dg a consecutive pair chosen in M such that dug < 04 by and by < ag <
Since R&+1 contains only one more element than Re: which is larger than all elements in Rg. we know that there is either one or zero elements
M that are strictly between ag and by- If by then let 0x+11 C and b by. otherwise 0x+1 ag and b&+1 c. If ag and by are still consecutive in M then d&+1 = ag and bx+1 = by.
ag
This guarantees that [k++1, ax+1] as at least half as big as [be, ax). Therefore, [ax - bk) < ak+1 bk+1, which means that 0v4+1 < 0k+1 bb+1 and by ak < 8.
Therefore ((k + 1) is verified.
[R] This also gives the general expression of v, valid for all k: v - I-
Main proof Using the result above, prove that Q" a) cannot have any non-null derivatives.
Trivially, Q" cannot have a non-null derivative at point (s, a) where (T a) = qu * 0. Indeed, there exists neighbourhood of go M in which there is single value.
Let To = (s, a) such that (s,, a) = 0. Let e be a vector of the space x A. Let f R - be defined as f [h) Q* (xu hv). In the following, we show that f(h) cannot converge to a non-null value when h 0.
We use the (c, 8) definition of limit. If f had a non-null derivative at 0, we owould have Ve > 0, 36 > 0, Vh, |/| < 8
1 < E.
Instead, we will show the opposite: 3e > 0, 4A > 0, 3h, [4] <
and
f(h) [6
2 6.
Using the candidate derivative and the value computed above that only depends on y and R), we iv set 2
Let 8 > 0.
There exists consecutive in M such that 8lv S and 81.
Note that a+d 2 < 81 therefore h < 8. We set h a+b 21
f(h) is in M, but At is the center of the segment [b, al of consecutive points of M. Therefore, the distance between ((h) and hl is at least a-b
16

---

Under review as a conference paper at ICLR 2020
a b
8ly
(S(h)
h|] 2
2
2
Since 8, 1/2
5(h)
1v
2
E IMPLEMENTATION DETAILS
Here the complete rollout and training algorithm, taken from the Spinup implementation DDPG.
Result: Policy Ty. number of steps before success
Tg. Q6 t Xavier uniform initializer
env steps <- 0
for t to 10000 do
a - Tul (s) rand() < 0.1 then rand(-0.1,001)
end
Step the environment using action get transition (s,,, Store (s, a, (,, in the replay buffer
env_steps <- env env_steps if' or env_steps >> N then
Reset the environment for k to env steps do Sample mini batch of size 100 from the replay buffer
Train Th and Qo this replay buffer with losses (1) and 2 end
env_ste sneesteps <-
end
mod 1000 = 0 then
if last 20 epixodes successes then
Terminate the algorithm, and return success steps
end
end
end
F PROPOSED SOLUTION TO THE DEADLOCK PROBLEM
F.I DESCRIPTION OF DDPG-ARGMAX
In this paper, we identified a deadlock problem and tracked its origin to the actor update described in Equation ( In Section we proposed new actor update mechanism in an algorithm called DDPG-argmax, which we describe in more details here.
Instead of relying on the differentiation of Qo (st, Ty. (st) to update v in order to maximize Qs,, (s)), we begin by selecting a set of N potential actions (by)osj<N. Then, we compute Qo (st, by) for each sample s; and each potential action by. and for each sample s; we find the best potential action G bargmax, Qo(s.,b)). Finally, we regress Tp towards the goal This process summarized in Equation (9) where Uni stands for uniform sampling in A.
17

---

Under review as a conference paper at ICLR 2020
DDPGGrgrox
DDPG
Avemag splende Md:nr
1500
1000
stan Mour Autoo aa 00000000000000000000000
500
2009
400%
Go0l
8009
1M
Siaunlation streps
Figure 11: Performance of DDPG and DDPG-argmax on sparse variant of HALFCHEETAH-V2 To ensure exploration of the state space is not problem, the policy is replaced with good pre-trained policy in one episode over 20.
(b (b)ossie ~ (A)
G Dargmax, Qa(s.,b))
(9)
minimize Σ (s:) - c2) w.r.t.
F.2 EXPERIMENTS ON LARGER BENCHMARKS
In order to test the relevance of using DDPG-argmax on larger benchmarks, constructed sparse reward versions of REACHER-V2 and HALFCHEETAH-V2.
REACHER-V v2 modified by generating step reward of when the distance between the arm and the target is less than 0.06, and otherwise. The distance to the target was removed from the observations, and the target fixed to position of (0.19, 0), instead of changing each episode. We also removed the control penalty.
modified by generating step reward of 2 when the component of the speed of the cheetah is more than 2. We also removed the control penalty. Since the maximum episode duration 1000, the maximum possible reward in this modified environment is 2000.
HALFCHEFTAH-V2
In both cases, the actor noise uses the default implementation of the Spinup implementation of DDPG, which is added uniform noise with an amplitude of 0.1.
Running DDPG and DDPG-argmax on these environments yields the results shown in Figures 9c and 9d Experiments on HALFCHEETAII-V v2 have been conducted using six different seeds. Figure 9d the main curves are smoothed using a moving average covering 10 episodes (10k steps), and the shaded area represents the average plus or minus one standard deviation.
On HALFCHEETAH-V2 both DDPG and DDPG-argmax are able to find rewards despite its sparsity. However, arggaxx outperforms DDPG in this environment. Since the only difference between these algorithms is the actor update, we conclude that even in complex environments, the actor update the main weakness of DDPG. We have shown that replacing with brute-force update improves performance dramatically, and further research aiming to improve the performance of deterministic actor-critic algorithms in environments with sparse rewards should concentrate on improving the actor update rule.
Figure 9d shows that DDPG is able to find the reward without the help of any exploration except the uniform noise built in the algorithm itself. However, to prove that state-space exploration is not the issue here, we constructed variant in which the current actor is backed up and replaced with pre-trained good actor every 20 episodes. This variant achieves episode returns above 1950 (as
18

---

Under review as a conference paper at ICLR 2020
reminder, the maximum episode return is 2000). In the next episode, the backed up policy is restored. This guarantees that the replay buffer always contains all the transitions necessary to learn a good policy. We call this technique priming.
Notice that DDPG performs much better than without priming, but the performance of DDPG-argmax is unchanged. However, DDPG still fails to completely solve the environment, proving that even when state-space exploration is made trivial, DDPG underperforms on sparse-reward environments due its poor actor update.
Results this variant are presented Figure II
19


Reviews:
[{"review_id": "rkgSYPB5Yr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis work studies the instability problem of DDPG in the setting of a deterministic\nenvironment and sparse reward. This work designed a toy environment to showcase\nthe potential issues of leading to the instability of DDPG. The observations, such as the correlation between the early access of good trajectory leads to more stable performance later, the deadlock of training could be beneficial. \nIt is essential to analyze and understand the intrinsic properties of the classic algorithms, and it would benefit the research community a lot if the empirical study is appropriately designed and conducted. Overall, this paper studied an essential problem\nof the vulnerability of the classic DRL algorithm (DDPG), which should attract more attention and efforts\nfrom the research community. \n\n\nDetailed comments:\nMethodology:\nThe experiments conducted cannot support the conclusions in this paper.\nI can not fully understand the conclusion from the subsection \"Residual failure to converge using different noise processes\". The DDPG agent is finding the reward regularly while it couldn't converge to the 100% optimal performance. In my opinion, this is an observation,\ninstead of giving any useful conclusion. The convergent issues when using the combination of off-policy\nlearning, function approximation, and bootstrapping are known (Sutton and Barto, Chap 11, 2018). \n\nThe increasing of Q value seems natural to me due to the overestimation of Q learning,\neven with the zero reward setting, which is one of the motivations of Double DQN. \n\nSeveral potential solutions are discussed while no empirical evidence or theoretical\njustification is provided, even in the designed 1D-Toy example.\n\nIt would be more convincing that the conclusions can be validated on more challenging\ntasks such as regular continuous action benchmarks (mujoco, etc.)\n\nWriting:\nThe presentation of this work is not ready for publication, given its current form. \nWhat is the definition of reward function? The formula as shown in Eq 4e is not clear. \nWhat is the optimal performance of 1D-TOY example? ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Syxwmy2nFB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overview: This paper describes a shortfall with the DDPG algorithm on a continuous state action space with sparse rewards. To first prove the existence of this shortfall, the authors demonstrate its theoretical possibility by reviewing the behavior of DDPG actor critic equations and the “two-regimes” proofs in the appendices. They then demonstrate the occurrence of the critic being updated faster than the actor, leading to a sub-optimal convergence from which the model can never recover. In this demonstration, they use a very simple environment they created, “1D-Toy”. The 1D-Toy environment is a one-dimensional, discrete-time, continuous state and action problem. Moving to the left at all in 1D-Toy results in a reward and episode end. Episode length was set at 50, as the agent could move to the right forever and never stop the episode. The authors demonstrate how the failure of the agent to obtain 100% success in this simple environment was, in fact, due to the phenomenon mentioned earlier. If the agent managed to obtain a reward very early on in training, it was highly likely the agent would converge on an optimal solution. If not, the actor would drift to a state were it no longer updates, and the critic would similarly no longer update either, resulting in a deadlock and suboptimal policy. The authors then generalize their findings using a helpful figure (Figure 7) which describes the cyclical nature of the phenomenon and how it can happen in any environment. Finally, the authors mention potential solutions to prevent the training failure from occurring, such as avoiding sparse rewards, replacing the critic update to avoid loss, etc.\n\nContributions: the discovery and review of a potential training failure for DDPG due to the nature of the critic update being reliant on the policy, and the deterministic policy gradient update\n\nQuestions and Comments:\nI believe that this work is relevant to ICLR and to the field. The paper is well-written, the theory is sound, and the experiment is sufficient to describe the stated deadlock situation that DDPG can contain during training. I believe this paper should be accepted because of these reasons. I have a few comments/questions for the authors which I have written below.\n\nI’m interested to see how likely this deadlock situation is on more complex environments. Did you run experiments on common benchmarks and analyze them?\nYou mention several potential solutions, one of them being the avoidance of sparse rewards. Of course this is problem-dependent which you stated yourself. The other two involve replacing two of the update functions. In the policy-based critic update, both of the mentioned solutions in this section have drawbacks mentioned. Would using a stochastic policy gradient update affect the networks ability to learn successfully in more complex environments? Would this make training less stable?\n\nI’m curious to see in which directions you see this work being extended. You briefly mention in the conclusion that there would be more formal studies: how do you imagine these being?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1lHCnA3tB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper investigates why DDPG can sometimes fail in environments with sparse rewards. It presents a simple environment that helps the reader build intuition and supports the paper's empirical investigation. First, the paper shows that DDPG fails on the simple environment in ~6% of cases, despite the solution being trivial—go left from the start state. The paper then augments DDPG with epsilon-greedy-style exploration to see if the cause of these failures is simply inadequate exploration. Surprisingly, in 1% of cases DDPG still fails. The paper shows that even in these failure cases there were still rewarded transitions that could have been learned from, and investigates relationships between properties of individual runs and the likelihood of failure. The paper then explains how these failures occur: the policy drifts to always going right, and the critic converges to a piecewise constant function whose gradient goes to zero and prevents further updates to the policy. The paper then generalizes this deadlock mechanism to other continuous-action actor-critic algorithms like TD3 and discusses how function approximation helps mitigate this issue. Finally, the paper gives a brief overview of some existing potential solutions.\n\nCurrently, I recommend rejecting this paper; while it is very well-written and rigorously investigates a problem with a popular algorithm, the paper does not actually present a novel solution method. It does a great job of clearly defining and investigating a problem and shows how others have attempted to solve it in the past, but stops there. It doesn't propose a new method and/or compare the existing methods empirically, nor does it recommend a specific solution method.\n\nA much smaller concern is that the problem investigated is somewhat niche; it happens in a very small percentage of runs and is mitigated by the type of function approximation commonly used. This lowers its potential impact a little.\n\nThe introduction does a great job of motivating the paper. I would've liked the related work section to elaborate more on the relationships between the insights in this paper and those of Fujimoto et al. (2018a), since the paper says the insights are related. Section 3 gave a very clear overview of DDPG. The simple environment described in section 4 was intuitive and explained well, and the empirical studies were convincing.\n\nHowever, after section 4 established the existence of the deadlock problem in DDPG, I was expecting the rest of the paper to present a solution method and empirically validate it. Instead, section 5 generalizes the findings from section 4 to include other environments and algorithms. I felt that section 4 and 5 could have been combined and shortened, and the extra space used to explain and empirically test a novel solution method. For example, figures 6 and 7 seem to be conveying similar information, but figure 7 takes up almost half a page.\n\nCurrently this paper seems like a good candidate for a workshop. It convincingly establishes the existence of a problem and shows what causes the problem to occur, but doesn't contribute a solution to the problem. Submitting it to a workshop could be a good opportunity for discussion, feedback, and possible collaboration, all of which might help inspire a solution method.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides an extensive investigation of the robustness of Deep Deterministic Policy Gradient algorithm.

Papers providing extensive and qualitative empirical studies, illustrative benchmark domains, identification of problems with existing methods, and new insights can be immensely valuable, and this paper is certainly in this direction, if not quite there yet. 

The vast majority of this paper investigates one deep learning algorithm in designed domain. There is some theory but it's relegated to the appendix. There are a few issues with this approach: (1) there is no concrete evidence that this is a general issue beyond the provided example (more on that below). (2) Even in the designed domain the problem is extremely rare. (3) The study and perhaps even the issue is only shown for one particular architecture (with a whole host of unspecified meta-parameter details). Why not just use SAC it works? DDPG has other issues, why is it of interest to study and fix this particular architecture? The motivation that it is the first and most popular algorithm is not well developed enough to be convincing. (4) There is really no reasoning to suggest that the particular 1D is representative or interesting in general.

The authors including Mujoco results to address #1. But the error bars overlap, its completely unclear if the baseline was tuned at all---this is very problematic as the domains were variants created by the authors. If DDPG was not tuned for the variant then the plots are not representative. In general, there are basically no implementation details (how parameters were tested, how experiments were conducted)or general methodological details given in the paper. Given the evidence provided in this paper its difficult to claim this is a general and important issue. 

I encourage the authors to look at John Langfords hard exploration tasks, and broaden their view of this work general learning mechanisms. 
Decision: Reject