ETGL-DDPG: A Deep Deterministic Policy Gradient Algorithm for Sparse Reward Continuous Control

## Abstract

Abstract We consider deep deterministic policy gradient (DDPG) in the context of reinforcement learning with sparse rewards. To enhance exploration, we introduce a search procedure, ϵ ⁢ t italic-ϵ 𝑡 {\epsilon}{t} italic_ϵ italic_t -greedy , which generates exploratory options for exploring less-visited states. We prove that search using ϵ ⁢ t italic-ϵ 𝑡 \epsilon t italic_ϵ italic_t -greedy has polynomial sample complexity under mild MDP assumptions. To more efficiently use the information provided by rewarded transitions, we develop a new dual experience replay buffer framework, GDRB , and implement longest n-step returns . The resulting algorithm, ETGL-DDPG , integrates all three techniques: ϵ ⁢ t italic-ϵ 𝑡 \epsilon t italic_ϵ italic_t -greedy, G DRB, and L ongest n 𝑛 n italic_n -step, into DDPG. We evaluate ETGL-DDPG on standard benchmarks and demonstrate that it outperforms DDPG, as well as other state-of-the-art methods, across all tested sparse-reward continuous environments. Ablation studies further highlight how each strategy individually enhances the performance of DDPG in this setting.

## 1 Introduction

Deep deterministic policy gradient (DDPG) (Lillicrap et al., ) is one of the representative algorithms for reinforcement learning (RL) (Sutton & Barto, ), alongside other prominent approaches (Haarnoja et al., ; Fujimoto et al., ; Andrychowicz et al., ). The method has been extensively used for continuous control environments with dense reward signals (Duan et al., ). However, its performance degrades significantly when the reward signals are sparse and are only observed upon reaching the goal (Matheron et al., ).

In sparse-reward environments where success depends on reaching a goal state, DDPG’s deficiency can be explained from three perspectives. The first one is its lack of *directional exploration*. Like other off-policy RL algorithms, DDPG employs a *behavior policy* for exploring the environment. The standard choices are either an $\epsilon$-greedy behavior policy that samples a random action with probability $\epsilon$ (e.g., $0.1$), or the main policy with artificial noise. As argued in (Dabney et al., ), these one-step *noise augmented greedy* strategies are ineffective for exploring large sparse-reward state spaces due to the lack of temporal abstraction. To improve $\epsilon$-greedy, Dabney et al. () propose a temporally extended $\epsilon z$-greedy policy that expands exploration into multiple steps, controlled by a distribution $z$. $\epsilon z$-greedy represents an advancement from the option framework for reinforcement learning (Sutton et al., ). Theoretically, an option $O$ is defined as a tuple $O=\langle I,\pi,\beta\rangle$, where $I$ is the set of states where an option can begin, $\pi$ is the option policy that determines which actions to take while executing the option, and $\beta$ is the termination condition. In $\epsilon z$-greedy, each option repeats a primitive action for a specific number of time steps which is sampled from a distribution $z$ (e.g., a uniform distribution). The option can begin at any state with probability $\epsilon$ and terminates whenever their length reaches a limit that is decided by $z$. While $\epsilon z$-greedy improves over $\epsilon$-greedy, it is also *directionless*: for exploratory action, the agent does not use any information from its experience for more informed exploration.

Figure: (a) $\epsilon t$-greedy: greedy or tree search
Refer to caption: x1.png

The second drawback of DDPG is its uniform treatment of zero and non-zero rewards in the replay buffer. For most off-policy RL algorithms, a replay buffer is used to store and sample transitions of the agent’s interactions with the environment. By default, DDPG uses a uniform sampling strategy that assigns an equal probability of being chosen to all transitions in the buffer. In sparse-reward environments, uniform sampling therefore rarely chooses rewarded transitions. In general, RL algorithms can be improved by prioritizing transitions based on the associated rewards or TD error (Schaul et al., ). For problems with well-defined goals, a replay buffer can be further enhanced to exploit the strong correlation of rewards and goals.
The third weakness of DDPG is its slow information propagation when updating its learning policy. Since only the last transition in a successful episode (i.e., goal reached) gets rewarded, in standard DDPG, the agent must achieve the goal many times to make sure that the reward is eventually propagated backward to early states. It is known that one way to achieve this is to provide intermediate rewards with reward shaping methods (Laud, ). However, effective reward shaping is usually problem-specific and does not generalize to a wide range of tasks.

In this paper, we enhance DDPG (Lillicrap et al., ) to address all three aforementioned problems. Our first contribution is *$\epsilon t$-greedy*, a new temporally version of $\epsilon$-greedy that utilizes a light-weight search procedure, similar to Laud (), to enable more directional exploration based on the agent’s previous experience data. We show that similar to $\epsilon z$-greedy, $\epsilon t$-greedy has polynomial sample complexity in related parameters of the MDP. Our second contribution is a new *goal-conditioned dual replay buffer* (GDRB), that uses two replay buffers along with an adaptive sampling strategy to differentiate goal-reached and goal-not-reached experience data. These two buffers differ in retention policy, size, and the transitions they store. Our third enhancement is to replace the one-step update in DDPG with the longest $n$-step return for all transitions in an episode. Figure 1 illustrates the innovations of ETGL-DDPG. In Section 4, we evaluate the performance of ETGL-DDPG through extensive experiments on 2D and 3D continuous control benchmarks. We show that each of the three strategies individually improves the performance of DDPG. Furthermore, ETGL-DDPG outperforms current state-of-the-art methods across all tested environments.

## 2 Background

We consider a Markov decision process (MDP) defined by the tuple $(S,A,\mathcal{T},r,\gamma,\rho)$. $S$ is the set of states, $A$ is the set of actions, $\mathcal{T}(s^{\prime}|s,a)$ is the transition distribution, $r:S\times A\times S\rightarrow\mathbb{R}$ is the reward function, $\gamma\in[0,1]$ is the discount factor, and $\rho(s_{0},s_{g})$ is the distribution from which initial and goal states are sampled for each episode.
Every episode starts with sampling a new pair of initial and goal states.
At each time-step $t$, the agent chooses an action using its policy and considering the current state and the goal state $a_{t}=\pi(s_{t},s_{g})$ resulting in reward $r_{t}=(s_{t},a_{t},s_{g})$. The next state is sampled from $\mathcal{T}(.|s_{t},a_{t})$. The episode ends when either the goal state or the maximum number of steps $T$ is reached. The return is the discounted sum of future rewards $R_{t}=\sum^{T}_{i=t}\gamma^{i-t}r_{i}$. The Q-function and value function associated with the agent’s policy are defined as $Q^{\pi}(s_{t},a_{t},s_{g})=\mathbb{E}[R_{t}|s_{t},a_{t},s_{g}]$ and $V^{\pi}(s_{t},s_{g})=max_{a}Q^{\pi}(s_{t},a_{t},s_{g})$. The agent’s objective is to learn an optimal policy $\pi^{*}$ that maximizes the expected return $\mathbb{E}_{s_{0}}[R_{0}|s_{0},s_{g}]$.

### 2.1 Deep Deterministic Policy Gradient (DDPG)

To ease presentation, we adopt our notation with explicit reference to the goal state for both the critic and the actor networks in DDPG. DDPG maintains an actor $\mu(s,s_{g})$ and a critic $Q(s,a,s_{g})$. The agent explores the environment through a stochastic policy $a\sim\mu(s,s_{g})+w$, where $w$ is a noise sampled from a normal distribution or an Ornstein-Uhlenbeck process (Uhlenbeck & Ornstein, ). To update both actor and critic, transition tuples are sampled from a replay buffer to perform a mini-batch gradient descent. The critic is updated by a loss $L$,

$$ $L=\mathbb{E}[Q(s_{t},a_{t},s_{g})-y_{t}]^{2}$ (1) $$

where $y_{t}=r_{t}+\gamma Q^{\prime}(s_{t+1},\mu^{\prime}(s_{t+1},s_{g}),s_{g})$. $Q^{\prime}$ and $\mu^{\prime}$ are the target critic and actor, respectively; their weights are soft-updated to the current weights of the main critic and actor, respectively. The actor is updated by the deterministic policy gradient algorithm (Silver et al., ) to maximize the estimated Q-values of the critic using loss $-\mathbb{E}_{s}[Q(s,\mu(s,s_{g}),s_{g})]$.

### 2.2 Locality-Sensitive Hashing

Our approach discretizes the state space with a hash function $\phi:\mathbb{S}\rightarrow\mathbb{M}$, that maps states to buckets in $\mathbb{M}$. When we encounter a state $s$, we increment the visit count for $\phi(s)$. We use $n(\phi(s))$ as the visit counts of all states that map to the same bucket $\phi(s)$. Clearly, the *granularity* of the discretization significantly impacts our exploration method. The goal for the granularity is that “distant” states are in separate buckets while “similar” states are grouped into one.

We use Locality-Sensitive Hashing (LSH) as our hashing function, a popular class of hash functions for querying nearest neighbors based on a similarity metric (Bloom, ). SimHash (Charikar, ) is a computationally efficient LSH method that calculates similarity based on angular distance. SimHash retrieves a binary code of state $s\in S$ as

$$ $\phi(s)=sgn(Af(s))\in\{-1,1\}^{k},$ (2) $$

where $f:S\rightarrow\mathbb{R}^{D}$ is a preprocessing function and $A$ is a $k\times D$ matrix with i.i.d. entries drawn from a standard Gaussian distribution $\mathcal{N}(0,1)$. The parameter $k$ determines the granularity of the hash: larger values result in fewer collisions, thereby enhancing the ability to distinguish between different states.

## 3 The ETGL-DDPG Method

In this section, we describe three strategies in ETGL-DDPG for improving DDPG in sparse-reward tasks. The full pseudocode for ETGL-DDPG is presented in Supplementary Algorithm 3.

### 3.1 ϵ ⁢ t italic-ϵ 𝑡 \epsilon t italic_ϵ italic_t -Greedy: Exploration with search

In principle, exploration should be highest at the beginning of training, as discovering rewarded transitions during early steps is essential for escaping local optima (Matheron et al., ). Motivated by the success of the fast exploration algorithms RRT (LaValle, ) and $\epsilon z$-greedy (Dabney et al., ), we introduce *$\epsilon t$-greedy*, which combines $\epsilon$-greedy with a *tree search* procedure. Like $\epsilon$-greedy, $\epsilon t$-greedy selects a greedy action with probability $1-\epsilon$, and an exploratory action with probability $\epsilon$. However, instead of exploring uniformly at random, the exploratory action in $\epsilon t$-greedy is the first step of an *option* generated via a search with time budget $N$.

To execute the search process, the agent requires access to the environment’s transition function $\mathcal{T}$ of the corresponding MDP. This is used to generate new nodes within the search tree. However, since our exploration strategy is built on DDPG, the model-free algorithm, the transition function $\mathcal{T}$ is not known. Instead, the agent utilizes its replay buffer to advance the search. We briefly discuss the impact of having access to $\mathcal{T}$ on the exploration process in Supplementary Material A.2. We also assume that the agent has a SimHash function $\phi$, which discretizes the large continuous environment. For each state $s$, $n(\phi(s))$ serves as an estimate of the number of visits to a neighbourhood of $s$ throughout the entire learning process.

The replay buffer contains transitions observed during training. It can be used as a transition model for observed transitions and an approximate one for transitions similar to those already seen. For simplicity, we identify each bucket with its hash code $\phi(s)$. We use a buffer $B_{M}$ which stores observed transitions based on the hash of their states $\phi(s)$. If the agent makes a transition $(s_{t},a_{t},r_{t},s_{t+1})$ in the environment, the transition is stored in bucket $b=\phi(s_{t})$. All transitions are assigned to their buckets upon being added to the replay buffer. As training may take a long time, we limit the number of transitions in each bucket, and randomly replace one of the old transitions in a full bucket with the new transition.

The function next_state_from_replay_buffer in Algorithm 1 shows how new nodes can be added to the search: assuming we are at node $s_{x}$, we randomly select a transition $(s^{\prime},a,r,s{{}^{\prime\prime}})$ in bucket $\phi(s_{x})$ and create a new child $s_{x{\prime}}$ for $s_{x}$ by using following approximation:

$$ $\mathcal{T}(s_{x},a)\approx\mathcal{T}(s^{\prime},a)$ (3) $$

Algorithm 1 explains how the search generates an exploratory option. Initially, at state $s$, we create a list of frontier nodes consisting of only the root node $s$. If bucket of state $s$ in $B_{M}$ is empty: $b_{\phi(s)}=\varnothing$, there is no transition to approximate $\mathcal{T}(s,a)$. In this case, $\epsilon t$-greedy as in $\epsilon$-greedy generates a random action at $s$. Otherwise, when $b_{\phi(s)}\neq\varnothing$, $\epsilon t$-greedy conducts a tree search iteratively, with a maximum of $N$ iterations. At each iteration, a node $s_{x}$ is sampled uniformly from the frontier nodes, and a *child* for $s_{x}$, noted as $s_{x^{\prime}}$, is generated using next_state_from_replay_buffer function. If $n(\phi(s_{x^{\prime}}))=0$, we terminate and return the action sequence from the root to $s_{x^{\prime}}$; otherwise, we repeat this process until we have added $N$ nodes to the tree. We then return the action sequence from the root to a least-visited node $s_{min}$:

$$ $s_{min}=\min_{s\ \in\ frontier\ nodes}n(\phi(s))$ (4) $$

To justify this exploration method, we adopt the conditions outlined in Liu & Brunskill () to validate the sample efficiency of $\epsilon t$-greedy. We begin by introducing the relevant terms and then present the main theorem. Detailed definitions and proofs are provided in Appendix A.1. The key idea is to define a measure that captures the concept of visiting all state-action pairs, as outlined in Definition 1.

###### Definition 1 ( Covering Length ) .

The covering length (Even-Dar & Mansour, ) represents the minimum number of steps an agent must take in an MDP, starting from any state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$, to visit all state-action pairs at least once with a probability of at least 0.5.

Our objective is to find a near-optimal policy, as defined in Definition 2.

###### Definition 2 ( $\epsilon$ -optimal Policy ) .

A policy $\pi$ is called $\delta$-optimal if it satisfies $V^{\pi^{*}}(s)-V^{\pi}(s)\leq\epsilon$, for all $s\in S$, where $\epsilon>0$.

Next, we define the concept of sample efficiency, which is captured through the notion of polynomial sample complexity in Definition 3.

###### Definition 3 ( PAC-MDP Algorithm ) .

Given a state space $\mathcal{S}$, action space $\mathcal{A}$, suboptimality error $\epsilon>0$ (from Definition 2) and $0<\delta<1$, an algorithm $\mathcal{A}$ is called PAC-MDP (Kakade, ), if the number of time steps required to find a $\epsilon$-optimal policy is less than some polynomial in the relevant quantities $(|\mathcal{S}|,|\mathcal{A}|,\frac{1}{\epsilon},\frac{1}{1-\gamma},\frac{1}{
\delta})$ with probability at least $1-\delta$.

For simplicity, when we say an algorithm $\mathcal{A}$ has polynomial sample complexity, we imply that $\mathcal{A}$ is PAC-MDP. The work by Liu & Brunskill () establishes polynomial sample complexity for a uniformly random exploration by bounding the covering length defined in Definition 1. Using this, and considering a limited tree budget $N$, we show that $\epsilon t$-greedy is PAC-MDP. Let’s denote the search tree by $\mathcal{X}$, and the distribution over the generated options in $\mathcal{X}$ as $\mathcal{P}_{\omega}$. The following Theorem provides a lower bound on option sampling in tree $\mathcal{X}$ under certain condition.

###### Theorem 1 ( Worst-Case Sampling ) .

Given a tree $\mathcal{X}$ with $N$ nodes ($s_{1}$ to $s_{N}$), for any $\omega\in\Omega_{\mathcal{X}}$, the sampling probability satisfies:

$$ $\displaystyle\mathcal{P}_{\mathcal{X}}[\omega]\geq\frac{1}{N!(\max_{i\in[N]}| \phi(s_{i})|)^{N-1}}\geq\frac{1}{\Theta(|\mathcal{S}||\mathcal{A}|)}$ (5) $$

, if $N\leq\frac{\log(|\mathcal{S}||{\mathcal{A}}|)}{\log\log(|\mathcal{S}||{
\mathcal{A}}|)}$.
Here, $\mathcal{S}$ and $\mathcal{A}$ represent the state space and action space, respectively.

To prove Theorem 1, we examine the construction of the “hardest option”, $\hat{\omega}\in\Omega_{\mathcal{X}}$, which has the lowest sampling probability in the tree $\mathcal{X}$. Since $\mathcal{P}_{\mathcal{X}}$ is an unknown distribution, we cannot directly exploit it. Instead, we construct a worst-case scenario to approximate the minimum option sampling probability. Now, we present the following Theorem on the sample complexity of $\epsilon t$-greedy.

###### Theorem 2 ( $\epsilon t$ -greedy Sample Efficiency ) .

Given a state space $\mathcal{S}$, action space $\mathcal{A}$, and a set of options $\Omega_{\mathcal{X}}$ generated by $\epsilon t$-greedy for each tree $\mathcal{X}$, if $\mathcal{P}_{\mathcal{X}}[\omega]\geq\frac{1}{\Theta(|\mathcal{S}||\mathcal{A}
|)}$, $\epsilon t$-greedy achieves polynomial sample complexity or i.e. is PAC-MDP.

Theorem 1 asserts that the sampling bound condition from Theorem 2 is satisfied when $N\leq\frac{\log(|\mathcal{S}||{\mathcal{A}}|)}{\log\log(|\mathcal{S}||{
\mathcal{A}}|)}$. Theorem 2 establishes the necessary lower bound on the sampling probability of an option $\omega\in\Omega_{{\mathcal{X}}}$ for any given exploration tree ${\mathcal{X}}$, ensuring that the $\epsilon t$-greedy strategy is PAC-MDP under this criterion.

Figure: Algorithm 1 Generating exploratory option with tree search

###### Definition 1 ( Covering Length ) .

###### Definition 2 ( ϵ italic-ϵ \epsilon italic_ϵ -optimal Policy ) .

###### Definition 3 ( PAC-MDP Algorithm ) .

###### Theorem 1 ( Worst-Case Sampling ) .

###### Theorem 2 ( ϵ ⁢ t italic-ϵ 𝑡 \epsilon t italic_ϵ italic_t -greedy Sample Efficiency ) .

### 3.2 GDRB: Goal-conditioned Dual Replay Buffer

The experience replay buffer is an indispensable part of deep off-policy RL algorithms. It is common to use only one buffer to store all transitions and use FIFO as the retention policy, with the most recent data replacing the oldest data (Mnih et al., ). As an alternative, in the reservoir sampling (Vitter, ) retention policy, each transition in the buffer has an equal chance of being overwritten. This maintains coverage of some older data over training. *RS-DRB* (Zhang et al., ) uses two replay buffers, one for exploitation and the other for exploration. The transitions made by the agent’s policy are stored in the exploitation buffer, and the random exploratory transitions are stored in the exploration buffer. For the retention policy, the exploration buffer uses reservoir sampling, while the exploitation buffer uses FIFO.

Inspired by this dual replay buffer framework, we propose a *Goal-conditioned Double Replay Buffer (GDRB)*. The first buffer $D_{\beta}$ stores all transitions during training, and the second buffer $D_{e}$ stores the transitions that belong to successful episodes (i.e., goal reached). $D_{\beta}$ uses reservoir sampling, and $D_{e}$ uses FIFO. Since $D_{\beta}$ needs to cover transitions from the entire training process, it is larger than $D_{e}$. We balance the number of samples taken from the two buffers with an adaptive sampling ratio. Specifically, in a training process of $E$ episodes, at current episode $i$, the sampling ratios $\tau_{e}$ and $\tau_{\beta}$ for $D_{e}$ and $D_{\beta}$ are set as follows: $\tau_{e}=\frac{i}{E},\tau_{\beta}=1-\tau_{e}.$
To select $C$ mini-batches, $\max(\left\lfloor\tau_{\beta}*C\right\rfloor,1)$ mini-batches are chosen from $D_{\beta}$ and the rest from $D_{e}$. Later stages of training still sample from $D_{\beta}$ to not forget previously acquired knowledge, as we assume the policy is more likely to reach the goal as the training progresses. In case that $D_{e}$ is empty, since there are no successful episodes yet, we draw all mini-batches from $D_{\beta}$.

### 3.3 Using Longest n 𝑛 n italic_n -step return

In standard DDPG, $Q$-values are updated using one-step TD. In goal-reaching tasks with sparse rewards, only one rewarded transition per successful episode is added to the replay buffer. The agent needs rewards provided by these transitions to update its policy toward reaching the goal. With few rewarded transitions, the agent should exploit a successful path to the goal many times so the reward is propagated backward quickly. Multi-step updates can accelerate this process by looking ahead several steps, resulting in more rewarded transitions in the replay buffer (Meng et al., ; Hessel et al., ). For example, Meng et al. () utilize $n$-step updates in DDPG with $n$ ranging from $1$ to $8$. In our design, to share the reward from the last step of a successful episode for all transitions in the episode, we use *longest $n$-step return* (Mnih et al., ), shown in Equation 6.

$$ $Q(s_{t},a_{t})=\begin{cases}\sum^{T-t}_{k=0}\gamma^{k}r_{t+k},\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{$s_{T}$ is a goal state}\\ \\ \sum^{T-t-1}_{k=0}\gamma^{k}r_{t+k}+\gamma^{T-t}Q(s_{T},a_{T}),\ \ \ \ \ \text {otherwise}\end{cases}$ (6) $$

Here, $s_{T}$ is the last state in the episode. Using the longest n-step return for each transition from a successful episode, the reward is immediately propagated to all $Q$-value updates. In unsuccessful episodes, using the longest $n$-step return reduces the overestimation bias in Q-values (Thrun & Schwartz, ). Meng et al. () empirically show that using multi-step updates can improve the performance of DDPG on robotic tasks mostly by reducing overestimation bias — they demonstrate that the larger the number of steps, the lower the estimated target Q-value and overestimation bias.

## 4 experiments

In this section, we show the details of how ETGL-DDPG improves DDPG for sparse-reward tasks using its three strategies. We use experiments to answer the following questions: 1) Can ETGL-DDPG outperform state-of-the-art methods in goal-reaching tasks with sparse rewards? 2) How does each of these three innovations impact the performance of DDPG? 3) Can $\epsilon t$-greedy explore more efficiently than $\epsilon z$-greedy and other common exploration strategies?

Figure: (a) Wall-maze
Refer to caption: x3.png

Figure: (a) Wall-maze
Refer to caption: x9.png

We consider two types of tasks: *navigation* and *manipulation*. We use three sparse-reward continuous environments for navigation. The first environment is a 2D maze called *Wall-maze* (Trott et al., ), where a reward of -1 is given at each step, and a reward of 10 is given if the goal is reached. The start and goal states for each episode are randomly selected from the blue and green regions, respectively, as shown in Figure 2a. The agent’s action (dx,dy) determines the amount of movement along both axes. The environment contains a gradient cliff feature (Lehman et al., ), where the fastest way to reach the goal results in a deadlock close to the goal. Our second and third 3D environments are *U-maze* (Figure 2b) and *Point-push* (Figure 2c) (Kanagawa, ), designed using the MuJoCo physics engine (Todorov et al., ). In both environments, a robot (orange ball) seeks to reach the goal (red region). In Point-push, the robot must additionally push aside the two movable red blocks that obstruct the path to the goal. A small negative reward of -0.001 is given at each step unless the goal is reached, where the reward is 1. In each episode, the robot starts near the same position with slight random variations, but the goal region remains fixed.

We also employ three manipulation tasks: *window-open*, *soccer*, and *button-press* (Figures 2d, e, and f) (Yu et al., ). In window-open, the goal is to push the window open; in soccer, the goal is to kick the ball into the goal; and in button-press, the aim is to press the top-down button. Each episode begins with the robot’s gripper in a randomized starting position, while the positions of other objects remain constant. The original versions of these tasks employ a uniquely shaped reward function for each task. However, these versions offer limited challenges for exploration, as standard baselines, such as SAC, demonstrate strong performance (Yu et al., ). We modified the original reward function to be sparse, transforming these tasks into challenging exploration problems.

The maximum number of steps per episode is set to 100 for Wall-maze and 500 for all other environments. Across all methods, the neural network architecture consists of 3 hidden layers with 128 units each, using ReLU activation functions. For standard baselines, we utilize the implementations from OpenAI Gym (Dhariwal et al., ), and for other baselines, we rely on their publicly available implementations. After testing various configurations, we found that $\epsilon t$-greedy and $\epsilon z$-greedy perform best with budgets of $N=40$ and $N=15$, respectively, across these environments. Additional details about the environments and experimental setup are provided in Appendix A.3.

### 4.1 Overall Performance of ETGL-DDPG

We evaluate the performance of ETGL-DDPG compared to state-of-the-art methods. We compare with SAC (Haarnoja et al., ), TD3 (Fujimoto et al., ), DDPG, and DOIE (Lobel et al., ). DOIE demonstrates state-of-the-art performance in challenging sparse-reward continuous control problems by drastically improving the exploration. While both DOIE and $\epsilon t$-greedy use a similarity measure between new and observed states, DOIE applies this to compute an optimistic value function rather than solely guiding the agent to unexplored areas. The results are shown in Figure 3. In the navigation environments, ETGL-DDPG and DOIE demonstrate superior performance compared to other methods, with ETGL-DDPG achieving a success rate of 1 faster than DOIE. Notably, Wall-maze presents a more challenging task among navigation environments, where only ETGL-DDPG and DOIE are able to achieve a success rate above zero. In manipulation tasks, the press-button poses the hardest challenge as none of the methods achieve a success rate of 1. ETGL-DDPG still outperforms all other approaches, while DOIE underperforms compared to SAC, indicating its limitations in adapting to high dimensional environments.

Figure: (a) Wall-maze
Refer to caption: x16.png

### 4.2 Environment Coverage through Exploration

We now examine how effective $\epsilon t$-greedy is in covering the environment. To do so, we discretize the navigation environments into small cells. A cell is considered visited if the agent encounters a sufficient number of distinct states within it, and the overall environment coverage is quantified as the fraction of visited cells. Figure 4 presents a comparison of environment coverage across different exploration strategies. All strategies except DOIE, which uses Radial Basis Function Deep Q-Network (RBFDQN) (Asadi et al., ), use DDPG as their underlying algorithm. RBFDQN is an enhanced DQN variant that incorporates Radial Basis Functions (RBF) to achieve more accurate Q-value approximations in continuous environments. In Wall-maze, $\epsilon t$-greedy is the only method capable of fully covering the environment, while DOIE achieves 90% coverage. $\epsilon z$-greedy covers approximately half of the environment, whereas the remaining methods manage to explore only around 30%. In U-maze, all strategies are successful, covering 80% or more of the environment. Even so, both $\epsilon t$-greedy and DOIE reach full coverage faster than other methods. In Point-push, none of the methods can fully cover the environment. However, $\epsilon t$-greedy still outperforms all baselines, and among the baselines, DOIE explores more than the others. We also investigate the distribution of final states reached in the episodes to determine the order in which the agent visits different regions of the environment (see Appendix A.5).

The tree budget $N$ upper bounds the option length of $\epsilon t$-greedy due to the fact that the longest path between nodes in the tree is shorter or equal to the number of nodes in the tree. This is analogous to the role of $N$ in $\epsilon z$-greedy, where a uniform distribution $z(n)=\mathbbm{1}_{n\leq N}/N$ is used. To evaluate both methods, we assess environment coverage under varying budget sizes, calculating the coverage after 1 million training frames. Table 1 shows the results: $\epsilon t$-greedy consistently achieves greater coverage than $\epsilon z$-greedy across all environments and budget sizes. Additionally, $\epsilon t$-greedy demonstrates improved the coverage as the budget increases. In contrast, increasing the budget for $\epsilon z$-greedy does not consistently improve coverage and can even decrease it in some cases. This highlights the advantages of directed exploration over undirected methods, particularly in complex environments with numerous obstacles, such as Wall-maze.

### 4.3 Effectiveness of Each New Component in ETGL-DDPG

We evaluated the performance of ETGL-DDPG, and now we assess the impact of each component on DDPG separately. Figure 5 presents the results for all environments. $\epsilon t$-greedy demonstrates the most improvement across all environments and is the only method that enhances the performance of DDPG in the Wall-maze, highlighting the critical role of our exploration strategy. GDRB shows a positive impact on DDPG performance in all environments, except for soccer, where DDPG alone outperforms all baselines. Additionally, we replaced reservoir sampling with FIFO as the retention policy in GDRB and observed similar results. The longest n-step return has a positive effect only in U-maze and press-button tasks, while it negatively impacts performance in soccer and Point-push. We attribute this to the inherently high variance of multi-step updates. A comparison of Figures 3 and 5 across all environments shows that ETGL-DDPG consistently outperforms the use of each component individually, supporting the effectiveness of their combination.

**Table 1: Analysis of the impact of budget N on the environment coverage.**
| budget $N$ | $\epsilon z$-greedy | $\epsilon t$-greedy |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
|  | Wall-maze | U-maze | Point-push | Wall-maze | U-maze | Point-push |
| 5 | 0.36 | 0.55 | 0.36 | 0.76 | 0.94 | 0.40 |
| 10 | 0.38 | 0.91 | 0.38 | 0.97 | 0.91 | 0.41 |
| 15 | 0.34 | 0.85 | 0.39 | 0.65 | 0.94 | 0.42 |
| 20 | 0.30 | 0.84 | 0.40 | 0.83 | 0.94 | 0.48 |
| 25 | 0.28 | 0.86 | 0.40 | 1 | 0.95 | 0.47 |
| 30 | 0.27 | 0.83 | 0.39 | 1 | 0.97 | 0.51 |
| 35 | 0.25 | 0.82 | 0.40 | 1 | 0.95 | 0.53 |
| 40 | 0.24 | 0.82 | 0.40 | 1 | 0.97 | 0.55 |
| 45 | 0.22 | 0.85 | 0.41 | 1 | 0.96 | 0.64 |
| 50 | 0.22 | 0.79 | 0.40 | 1 | 0.97 | 0.73 |

Figure: (a) Wall-maze
Refer to caption: x20.png

## 5 Related work

Exploration. Intrinsic motivation methods  (Burda et al., ; Pathak et al., ; Ostrovski et al., ; Tang et al., ) provide a reward bonus for unexplored areas of the state space. These methods make the reward function non-stationary, which breaks the Markov assumption of MDP. Decoupled RL algorithms (Schäfer et al., ; Badia et al., ) resolve the non-stationarity of the reward function by training two separate policies for exploration and exploitation. However, such methods require double the computation cost. Colas et al. () use a policy search process to generate diverse data for training of DDPG. Liu et al. () introduce a competition-based exploration method where two agents (A and B) compete with each other. Agent A is penalized for visiting states visited by B, while B is rewarded for visiting states discovered by A. Plappert et al. () directly inject noise into the policy’s parameter space instead of the action space. Eysenbach et al. () build a graph using states in the replay buffer, allowing the agent to navigate distant regions of the environment by applying Dijkstra’s algorithm. Lobel et al. () present Deep Optimistic Initialization for Exploration (DOIE), which improves exploration in continuous control tasks by maintaining optimism in state-action value estimates. Lobel et al. () demonstrate that DOIE can estimate visit counts by averaging samples from the Rademacher distribution instead of using density models. Dey et al. () present COIN, a continual optimistic initialization strategy that extends DOIE to stochastic and non-stationary environments.

Experience Replay Buffer and Reward Propagation. Rather than uniformly sampling from the buffer, Prioritized Experience Replay (PER) (Schaul et al., ) prioritizes transitions in the buffer based on reward, recency, or TD error at the expense of $O(\log N)$ per sample, where $N$ is the buffer size. CER (Zhang & Sutton, ) includes the last transition from the buffer to each sampled batch with $O(1)$ complexity. Zhang et al. () learn a conservative value regularizer only from the observed transitions in the replay buffer to improve the sample efficiency of DQN. Pan et al. () theoretically show why PER has a better convergence rate than uniform sampling policy when minimizing mean squared error. Furthermore, Pan et al. () identify two limitations of PER: outdated priorities and insufficient coverage of the state space. Reward shaping (Laud, ; Hu et al., ) creates artificial intermediate rewards to facilitate reward propagation. However, designing appropriate intermediate rewards is hard and often problem-specific. Trott et al. () address this issue by introducing  *self-balancing reward shaping* in the context of on-policy learning. To extract more information from an unsuccessful episode, Andrychowicz et al. () introduce *imaginary goals*. An imaginary goal for state $s$ is a state that is encountered later in the episode. Devidze et al. () introduce a novel reward informativeness criterion that adaptively designs interpretable reward functions based on an agent’s current policy in sparse-reward tasks.

## 6 Conclusions and Future Work

We have introduced the ETGL-DDPG algorithm with three components that improve the performance of DDPG for sparse-reward goal-conditioned environments. $\epsilon t$-greedy is a temporally-extended version of $\epsilon$-greedy using options generated by search. We prove that $\epsilon t$-greedy achieves a polynomial sample complexity under specific MDP structural assumptions. GDRB employs an extra buffer to separate successful episodes. The longest $n$-step return bootstraps from the Q-value of the final state in unsuccessful episodes and becomes a Monte Carlo update in successful episodes. ETGL-DDPG uses these components with DDPG and outperforms state-of-the-art methods, at the expense of about 1.5x wall-clock time w.r.t DDPG. The current limitation of our work is that we approximate visit counts through static hashing. For image-based problems such as real-world navigation, the future direction is to leverage dynamic hashing techniques such as *normalizing flows* (Papamakarios et al., ) as these tasks demand more intricate representation learning.

## Appendix A Appendix

### A.1 ϵ ⁢ t italic-ϵ 𝑡 \epsilon t italic_ϵ italic_t -greedy Sample Efficiency : Proofs

In this section, we first provide an overview of the proof, presenting the key ideas at a high level. Then, we present the detailed formal proof of Theorem 1 and Theorem 2.

#### Proof Overview.

We aim to show that the $\epsilon t$-greedy algorithm falls into the PAC-MDP category. According to Liu & Brunskill (), an algorithm $\mathcal{A}$ is PAC-MDP if the covering time induced by $\mathcal{A}$ is polynomially bounded. In Liu & Brunskill (), the authors further demonstrate that bounding the covering time requires bounding both the Laplacian eigenvalues and the stationary distribution over the states induced by the random walk policy. This is presented as Proposition A.1. According to Theorem 2, two conditions are satisfied: $N\leq\Theta(|\mathcal{S}||\mathcal{A}|)$ and a lower bound on the probability of the sampled option, $\mathcal{P}_{\mathcal{X}}\geq\frac{1}{\Theta(|\mathcal{S}||\mathcal{A}|)}$. These two conditions are necessary and are met by our problem setting and the exploration algorithm (Algorithm 1). To prove that $\mathcal{P}_{\mathcal{X}}\geq\frac{1}{\Theta(|\mathcal{S}||\mathcal{A}|)}$, we construct a worst-case tree structure $\mathcal{X}$, where we aim to identify the option induced by the tree $\mathcal{X}$ with the lowest probability, referred to informally as the “hardest option”. We then show that this lower bound satisfies the condition specified in Theorem 1.

We now proceed with the proof of Theorem 1, as demonstrated below.

###### Theorem 1 ( Worst-Case Sampling ) .

Given a tree $\mathcal{X}$ with $N$ nodes ($s_{1}$ to $s_{N}$), for any $\omega\in\Omega_{\mathcal{X}}$, the sampling probability satisfies:

$$ $\displaystyle\mathcal{P}_{\mathcal{X}}[\omega]\geq\frac{1}{N!(\max_{i\in[N]}| \phi(s_{i})|)^{N-1}}\geq\frac{1}{\Theta(|\mathcal{S}||\mathcal{A}|)}$ (7) $$

where $N\leq\frac{\log(|\mathcal{S}||{\mathcal{A}}|)}{\log\log(|\mathcal{S}||{
\mathcal{A}}|)}$
Here, $\mathcal{S}$ and $\mathcal{A}$ represent the state space and action space, respectively.

###### Proof.

As outlined in the proof overview, we need to construct an option with the lowest sampling probability. Given a tree $\mathcal{X}$, we define $\mathcal{X}_{i}$ (for $1\leq i\leq N$) as the tree constructed up to the $i$-th time step. At each step $\mathcal{X}_{i}$, we track the tuple of added states, denoted by $\mathcal{S}_{i}^{\mathcal{X}}$, the uniformly sampled state $s_{x}$ from $\mathcal{S}_{i}^{\mathcal{X}}$, and the state with the fewest visits, $s_{min}$. The notation $s_{x}$ and $s_{min}$ follows Algorithm 1. Without loss of generality, we assume that each next state $s_{x^{\prime}}$ in line 9 of Algorithm 1 satisfies $n(\phi(s_{x^{\prime}}))\neq 0$. Specifically, we consider a worst-case tree $\mathcal{X}$ fully populated with states from $s_{1}$ to $s_{N}$. Therefore, at time step $N$, $\mathcal{S}_{N}^{\mathcal{X}}=(s_{1},s_{2},\dots,s_{N})$, and we have the following relation:

$$ $\displaystyle n(\phi(s_{1}))\geq n(\phi(s_{2}))\geq n(\phi(s_{3}))\dots\geq n( \phi(s_{N})).$ (8) $$

Equation 8 provides a decreasing sequence of visitations for newly added nodes in tree $\mathcal{X}$, emphasizing line 15 of Algorithm 1, which causes the state $s_{min}$ to change over $N$ iterations.
We assume a specific structure for each $\phi(s_{i})$, where for all $i\in[N]$, at each bucket $\phi(s_{i})$, there exists only one state denoted by $s_{i+1}$, such that $n(\phi(s_{i+1}))\leq n(\phi(s_{i}))$. Additionally, we assume that at each time step in $\mathcal{X}_{t}$, the newly added node connects only to the most recently added node in the tree. The two key stochastic events are summarized as follows:

- •
$\mathcal{E}_{1}$: The event in which nodes are sampled in Line 24 from buckets satisfying the increasing sequence above.
- •
$\mathcal{E}_{2}$: The event in which nodes are selected in Line 8.

We now define the probability of interest, which we aim to bound:

$$ $\displaystyle\mathcal{P}[\text{option returned from }s_{\text{root}}\text{ to }s_{N}|\mathcal{E}_{1}\text{ and }\mathcal{E}_{2}].$ (9) $$

We expand this probability as follows:

$$ $\displaystyle\mathcal{P}[\text{option returned from }s_{\text{root}}\text{ to }s_{N}\mid\mathcal{E}_{1}\text{ and }\mathcal{E}_{2}]$ $\displaystyle=\prod_{i=2}^{N}\mathcal{P}[\text{(State }s_{i}\text{ added to tree }\mathcal{X})\wedge(s_{i}=s_{min})\wedge(s_{x}=s_{i-1}\text{ in Line 8})]$ $\displaystyle=\prod_{i=2}^{N}\frac{1}{(i-1)|\phi(s_{i-1})|}$ $\displaystyle=\frac{1}{(N-1)!}\times\frac{1}{|\phi(s_{1})||\phi(s_{2})|\dots| \phi(s_{N})|}$ $\displaystyle>\frac{1}{N!}\times\frac{1}{(\max_{i\in[N]}|\phi(s_{i})|)^{N-1}}$ $\displaystyle>\frac{1}{|\mathcal{S}||\mathcal{A}|}.$ $$

To prove the final inequality, note that $N\leq\frac{\log(|\mathcal{S}||\mathcal{A}|)}{\log\log(|\mathcal{S}||\mathcal{A
}|)}$. Since the size of the sets $\mathcal{S}$ and $\mathcal{A}$ is large and $N$ is sub-logarithmic in $|\mathcal{S}||\mathcal{A}|$, i.e., $N\ll\log(|\mathcal{S}||\mathcal{A}|)$, we can say $N\leq\frac{\log(|\mathcal{S}||\mathcal{A}|)}{\log(N)}$. Let us denote $\log(\max_{i\in[N]}|\phi(s_{i})|)$ as a constant $c_{0}$.

Now by the series of following inequalities we prove that $\frac{1}{N!}\times\frac{1}{(\max_{i\in[N]}|\phi(s_{i})|)^{N-1}}>\frac{1}{|
\mathcal{S}||\mathcal{A}|}$.

$$ $\displaystyle N$ $\displaystyle\leq\frac{\log(|{\mathcal{S}}||{\mathcal{A}}|)}{\log(N)} \Rightarrow N\log(N)\leq\log(|{\mathcal{S}}||{\mathcal{A}}|)$ (10) $\displaystyle\Rightarrow N\log(N)+(N-1)c_{0}-N\leq\log(|{\mathcal{S}}||{ \mathcal{A}}|)\quad\quad\quad\text{(since $|{\mathcal{S}}||{\mathcal{A}}|\gg N ,c_{0}$)}$ (11) $\displaystyle\Rightarrow\log(N!)+(N-1)c_{0}\leq\log(|{\mathcal{S}}||{\mathcal{ A}}|)\quad\quad\quad\text{(Based on the Moivre–Stirling approximation)}$ (12) $\displaystyle\Rightarrow\log(N!)+(N-1)c_{0}\leq\log(|{\mathcal{S}}||{\mathcal{ A}}|)$ (13) $\displaystyle\Rightarrow\log(N!)+\log\left((\max_{i\in[N]}|\phi(s_{i})|)^{N-1} \right)\leq\log(|{\mathcal{S}}||{\mathcal{A}}|)$ (14) $\displaystyle\Rightarrow\log\left(N!\cdot(\max_{i\in[N]}|\phi(s_{i})|)^{N-1} \right)\leq\log(|{\mathcal{S}}||{\mathcal{A}}|)$ (15) $\displaystyle\Rightarrow\frac{1}{N!\cdot(\max_{i\in[N]}|\phi(s_{i})|)^{N-1}} \geq\frac{1}{|{\mathcal{S}}||{\mathcal{A}}|}$ (16) $$

∎

Now we provide the main proof which demonstrates polynomial sample complexity under certain criteria.

###### Theorem 2 ( $\epsilon t$ -greedy Sample Efficiency ) .

Given a state space $\mathcal{S}$, action space $\mathcal{A}$, and a set of options $\Omega_{\mathcal{X}}$ generated by $\epsilon t$-greedy for each tree $\mathcal{X}$, if $\mathcal{P}_{\mathcal{X}}[\omega]\geq\frac{1}{\Theta(|\mathcal{S}||\mathcal{A}
|)}$, $\epsilon t$-greedy achieves polynomial sample complexity or i.e. is PAC-MDP.

###### Proof.

First note that if $\mathcal{P}_{\mathcal{X}}[\omega]\geq\frac{1}{\Theta(|\mathcal{S}||\mathcal{A}
|)}$ then based on Theorem 1 we need to have $N\leq\frac{\log(|\mathcal{S}||{\mathcal{A}}|)}{\log\log(|\mathcal{S}||{
\mathcal{A}}|)}$, and this implies that $N\leq\Theta(|{\mathcal{S}}||{\mathcal{A}}|)$.
Based on the paper by (Liu & Brunskill, ), and the analysis of the covering length when following a random policy, we have the following preposition:

###### Preposition A.1 ( Liu & Brunskill ( 2018 ) ) .

: For any irreducable MDP M, we define $P_{\pi_{RW}}$ as a transition matrix induced by random walk policy $\pi_{RW}$ over $M$ and $L(P_{\pi_{RW}})$ is denoted as the Laplacian of this transition matrix. Suppose $\lambda$ is the smallest non-zero eigenvalue of $L$ and $\Psi(s)$ is the stationary distribution over states which is induced by random walk policy, then Q-learning with random walk exploration is a PAC RL algorithm if: $\frac{1}{\lambda}$,$\frac{1}{\min_{s}\Psi(s)}$ are Poly($|{\mathcal{S}}||{\mathcal{A}}|$).

Note that Preposition A.1 is not limited to an MDP with primitive actions. Therefore, we can broaden its scope by incorporating options into this proposition and demonstrate that both $\frac{1}{\lambda}$ and $\frac{1}{\min_{s}\Psi(s)}$ can be polynomially bounded in terms of MDP parameters—in this case, states and actions in our approach.

Let’s begin by examining the upper-bound for $\frac{1}{\min_{s}\Psi(s)}$. Suppose we are at exploration tree ${\mathcal{X}}$. Without a loss of generality, we consider that capacity of tree ${\mathcal{X}}$ is full, and we have $N$ states. In this tree, let’s designate $s_{root}$ as the state assigned as the root of the tree during the exploration phase. Now, consider another random state (excluding $s_{root}$) within this tree structure, denoted as $s_{rand}$. We acknowledge that, when considering the entire state space, there can be multiple options constructed from $s_{root}$ to $s_{rand}$. Each tree ${\mathcal{X}}$ provides one of these options. $\Psi(s)$ is defined over all states, and $\omega$ is the option with a limited size because of the constrained tree budget.

we can calculate the upper-bound for $\frac{1}{\min_{s}\Psi(s)}$ as follows:

$$ $\displaystyle\Psi(s_{rand})=\sum_{\omega\in\Omega_{{\mathcal{X}}}}{\mathcal{P} }_{{\mathcal{X}}}[\omega]\Psi(s_{root})\Rightarrow\Psi(s_{rand})\geq{\mathcal{ P}}[\omega]\Psi(s_{root}),$ (17) $\displaystyle\frac{1}{\Psi(s_{rand})}\leq\frac{1}{{\mathcal{P}}[\omega]}\frac{ 1}{\Psi(s_{root})}\Rightarrow\frac{1}{\Psi(s_{rand})}\leq\frac{\Theta(|{ \mathcal{S}}||{\mathcal{A}}|)}{\Psi(s_{root})}$ $$

Since $s_{rand}$ can represent any of the states encountered in the tree, we can regard it as the state assigned the least probability in the stationary distribution. Therefore, we have:

$$ $\frac{1}{\Psi(s_{rand})}\leq\frac{\Theta(|{\mathcal{S}}||{\mathcal{A}}|)}{\Psi (s_{root})}\Rightarrow\frac{1}{\min_{s}\Psi(s)}\leq\frac{\Theta(|{\mathcal{S}} ||{\mathcal{A}}|)}{\Psi(s_{root})}$ (18) $$

So, $\frac{1}{\min_{s}\Psi(s)}$ is polynomially bounded. Now, we need to demonstrate that $\frac{1}{\lambda}$ is also polynomially bounded. To bound $\lambda$, we first need to recall the definition of the Cheeger constant, $h$. Drawing from graph theory, if we denote $V(G)$ and $E(G)$ as the set of vertices and edges of an undirected graph $G$, respectively, and considering the subset of vertices denoted by $V_{s}$, we can define $\sigma V_{s}$ as follows:

$$ $\sigma V_{s}:=\{(n_{1},n_{2})\in E(G):n_{1}\in V_{s},n_{2}\in V(G)\setminus V_ {s}\}$ (19) $$

So, $\sigma V_{s}$ can be regarded as a collection of all edges going from $V_{s}$ to the vertex set outside of $V_{s}$. In the above definition, $(n_{1},n_{2})$ is considered as a graph edge. Now, we can define a Cheeger constant:

$$ $h(G):=\min\{\frac{|\sigma V_{s}|}{|V_{s}|}:V_{s}\subseteq V(G),0<V_{s}\leq \frac{1}{2}|V(G)|\}$ (20) $$

We are aware that $h\geq\lambda\geq\frac{h^{2}}{2}$, and by polynomially bounding $h$, we can ensure that $\lambda$ is also bounded. In a related work (Liu & Brunskill, ), an alternative variation of the Cheeger constant is utilized, which is based on the flow $F$ induced by the stationary distribution $\Psi$ of a random walk on the graph. Suppose for nodes $n_{1},n_{2}$ and subset of nodes $N_{1}$ in the graph, we have:

$$ $\displaystyle F(n_{1},n_{2})=\Psi(n_{1})P(n_{1},n_{2}),$ (21) $\displaystyle F(\sigma N_{1})=\sum_{n_{1}\in N_{1},n_{2}\notin N_{1}}F(n_{1},n _{2}),$ (22) $\displaystyle F(N_{1})=\sum_{n_{1}\in N_{1}}\Psi(n_{1})$ (23) $$

Building upon the aforementioned definition, the Cheeger constant is defined as:

$$ $h:=\inf_{N_{1}}\frac{F(\sigma N_{1})}{\min\{F(N_{1}),F(\bar{N_{1}})\}}$ (24) $$

Suppose $N_{rand}=\{s_{root}\}$; we will now demonstrate that $\frac{1}{h}$ can be polynomially bounded :

$$ $\displaystyle h=\inf_{N_{1}}\frac{F(\sigma N_{1})}{\min\{F(N_{1}),F(\bar{N_{1} })\}}\geq\frac{F(\sigma N_{rand})}{\min\{F(N_{rand}),F(\overline{N_{rand}})\}} \geq\frac{\sum_{s\neq s_{root}}\Psi(s_{root})P_{\pi_{RW}}(s_{root},s)}{\Psi(s_ {root})},$ $\displaystyle=\sum_{s\neq S_{root}}P_{\pi_{RW}}(s_{root},s)\geq{\mathcal{P}}_{ {\mathcal{X}}}[\omega]\Rightarrow\frac{1}{h}\leq\Theta(|{\mathcal{S}}||{ \mathcal{A}}|)$ $$

We demonstrate that both terms stated in Preposition A.1 are polynomially bounded, and thus, the proof is complete.
∎

Figure: Algorithm 2 Generating exploratory option with tree search using a perfect model

Figure: Algorithm 3 ETGL-DDPG

###### Theorem 1 ( Worst-Case Sampling ) .

###### Proof.

###### Theorem 2 ( ϵ ⁢ t italic-ϵ 𝑡 \epsilon t italic_ϵ italic_t -greedy Sample Efficiency ) .

###### Proof.

###### Preposition A.1 ( Liu & Brunskill ( 2018 ) ) .

### A.2 Exploration with a perfect model

Since the DDPG algorithm is model-free, we utilize the replay buffer to construct the tree for $\epsilon t$-greedy. However, $\epsilon t$-greedy can also take advantage of a perfect model when available. The pseudocode for option generation using a perfect model is provided in Algorithm 2. The key difference from Algorithm 1 is the use of the next_state_from_env function instead of next_state_from_replay_buffer to generate child nodes. In this case, an action is uniformly sampled from the action space, and the environment’s transition function $\mathcal{T}$ is directly used to determine the next state (line 25). Figure 6 compares the performance of ETGL-DDPG in navigation environments using a perfect model versus a replay buffer. The results show a clear advantage when using a perfect model, as the agent reaches a success rate of 1 more quickly and with less deviation.

Figure: (a) Wall-maze
Refer to caption: x27.png

### A.3 Implementation Details and Experimental Hyperparameters

Here, we describe the implementation details and hyperparameters for all methods used in this paper. All experiments were run on a system with 5 vCPU on a cluster of Intel Xeon E5-2650 v4 2.2GHz CPUs and one 2080Ti GPU. Table 3 displays the details for environments. Tables 2, 4, and 5 showcase the hyperparameters utilized in ETGL-DDPG and the baselines.

**Table 2: Implementation details for ETGL-DDPG.**
| Hyperparameter | wall-maze | U-maze | Point-push | window-open | soccer | button-press |
| --- | --- | --- | --- | --- | --- | --- |
| batch size | 128 | 512 |  |  |  |  |
| number of updates per episode | 20 | 200 |  |  |  |  |
| epsilon decay rate | 0.9999988 | 0.9999992 |  |  |  |  |
| exploration budget N | 20 | 40 | 60 |  |  |  |
| SimHash dimension | $k=9$ | $k=16$ |  |  |  |  |
| soft target updates $\tau$ | $10^{-2}$ |  |  |  |  |  |
| discount factor $\gamma$ | 0.99 |  |  |  |  |  |
| warmup period | $2*10^{5}$ steps |  |  |  |  |  |
| exploration buffer size | $10^{6}$ |  |  |  |  |  |
| exploitation buffer size | $5*10^{4}$ |  |  |  |  |  |
| actor learning rate | $10^{-4}$ |  |  |  |  |  |
| critic learning rate | $10^{-3}$ |  |  |  |  |  |

**Table 3: Environment details.**
| environment | $S\in$ | $G\in$ | $A\in$ | Max steps per episode |
| --- | --- | --- | --- | --- |
| Wall-maze | $\mathbb{R}^{2}$ | $\mathbb{R}^{2}$ | $[-0.95,0.95]^{2}$ | 100 |
| U-maze | $\mathbb{R}^{6}$ | $\mathbb{R}^{2}$ | $[-1,1]*[-0.25,0.25]$ | 500 |
| Point-push | $\mathbb{R}^{11}$ | $\mathbb{R}^{2}$ | $[-1,1]*[-0.25,0.25]$ | 500 |
| window-open | $\mathbb{R}^{39}$ | $\mathbb{R}^{3}$ | $[-1,1]^{4}$ | 500 |
| soccer | $\mathbb{R}^{39}$ | $\mathbb{R}^{3}$ | $[-1,1]^{4}$ | 500 |
| button-press | $\mathbb{R}^{39}$ | $\mathbb{R}^{3}$ | $[-1,1]^{4}$ | 500 |

**Table 4: Implementation details for SAC, TD3, and DDPG.**
| Hyperparameter | wall-maze | U-maze | Point-push | window-open | soccer | button-press |
| --- | --- | --- | --- | --- | --- | --- |
| batch size | 128 | 512 |  |  |  |  |
| update frequency per step | 12 | 2 |  |  |  |  |
| action noise | $\sim N(0,0.2)$ | $\sim N(0,(0.3,0.05))$ | $\sim N(0,(0.15))$ |  |  |  |
| warmup period | $2*10^{5}$ steps |  |  |  |  |  |
| replay buffer size | $10^{6}$ |  |  |  |  |  |
| learning rate | $3*10^{-4}$ |  |  |  |  |  |
| soft target updates $\tau$ | $5*10^{-3}$ |  |  |  |  |  |
| discount factor $\gamma$ | 0.99 |  |  |  |  |  |

**Table 5: Implementation details for DOIE.**
| Hyperparameter | wall-maze | U-maze | Point-push | window-open | soccer | button-press |
| --- | --- | --- | --- | --- | --- | --- |
| batch size | 256 |  |  |  |  |  |
| number of updates per episode | 100 |  |  |  |  |  |
| replay buffer size | $5*10^{5}$ |  |  |  |  |  |
| actor learning rate | $10^{-4}$ |  |  |  |  |  |
| critic learning rate | $5*10^{-3}$ |  |  |  |  |  |
| discount factor $\gamma$ | 0.99 |  |  |  |  |  |
| action scaling | 0.01 |  |  |  |  |  |
| environment scaling | 0.1 for each dimension |  |  |  |  |  |
| knownness mapping type | polynomial |  |  |  |  |  |

### A.4 ETGL-DDPG Algorithm

In this section, we introduce ETGL-DDPG, as detailed in Algorithm 3, which is organized into three primary functions: train, run_episode, and update. The train function is called once at the start of the training process. For each training episode, the run_episode function is invoked to perform a training episode within the environment, followed by the update function to adjust the networks based on the experience gained from the episode.

### A.5 Terminal states distribution

We analyze the order in which the agent visits different parts of the environment by examining the distribution of the last states in the episodes. To make it more visually appealing and easy to interpret, we only sample some of the episodes. The results for Wall-maze, U-maze, and Point-push can be found in Figures 7, 8, and 9, respectively. In Wall-maze, only $\epsilon t$-greedy and DOIE can effectively navigate to different regions of the environment and ultimately reach the goal area. Other methods often get trapped in one of the local optima and are unable to reach the goal. The reason some methods, such as TD3, have fewer points is that the agent spends a lot of time revisiting congested areas instead of exploring new ones. In U-maze, most methods can explore the majority of the environment. However, during the final stages of training, methods such as DDPG, SAC, and DDPG + intrinsic motivation have lower success rates and may end up in locations other than the goal areas. In Point-push, $\epsilon t$-greedy, $\epsilon z$-greedy, and DOIE first visit the lower section of the environment in the early stages. After that, they push aside the movable box and proceed to the upper section to visit the goal area. For the other methods, the pattern is almost the same, with occasional visits to the lower section.

Figure: (a) DDPG + $\epsilon t$-greedy
Refer to caption: x31.png

Figure: (a) DDPG + $\epsilon t$-greedy
Refer to caption: x38.png

Figure: (a) DDPG + $\epsilon t$-greedy
Refer to caption: x45.png

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 5
presentation: 2
questions: Please see weakness.
soundness: 3
strengths: 1. This work aims to enhance the most fundamental algorithms in RL, which I believe is very important.
2. The paper points out the important issue that DDPG is not suitable for sparse rewards settings and specifically identifies three drawbacks of DDPG.
3. The three improvements proposed in ETGL-DDPG sound effective to me in the sparse reward setting.
4. The benchmark experiments and ablation studies demonstrate the effectiveness of ETGL-DDPG.
summary: This paper addresses the limitations of the DDPG algorithm in sparse-reward environments. It identifies three main deficiencies: lack of directional exploration, uniform treatment of rewards in the replay buffer, and slow information propagation during policy updates. To tackle these issues, the authors propose three enhancements to DDPG, including $\epsilon t$-greedy, goal-conditioned dual replay buffer (GDRB), and longest n-step return. Empirical results demonstrate that each individual strategy enhances DDPG’s performance.
weaknesses: 1. This study proposes three improvements to DDPG in the context of sparse rewards, but I am uncertain about the degree of originality of each of these improvements. There is a substantial amount of related work on this topic (sparse reward, exploration, improving DDPG), and there are likely several studies closely related to each of the proposed enhancements, as some of them are straightforward and may be easy to conceive. Thus, a thorough literature review would be necessary to determine the novelty of the improvements. If these improvements (or some of them) have suffient innovation, I believe they would be valuable contributions.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: * What does the shaded portion in Figures 3 and 5 signify? Perhaps add it to the caption of the figure.

Other questions have been asked as part of the critique and feedback in previous section. Please refer to those.
soundness: 2
strengths: * This paper shows strong empirical results. The effect of the different components is clear from the experiments.
* The explanation of the three components is also fairly clear. Figure 1 was helpful in understanding the proposed techniques
* Some of the analysis figures are also well done. I particularly like Section A.5, which shows how the terminal state distribution for the different algorithms evolve over training.
* Training details are also extensive, and I believe the results in this paper could be reproduced
* The presented exploration strategy $\epsilon t$-greedy, is a combination of good ideas, and shows great promise.
* The sample complexity analysis adds theoretical depth to the paper.
summary: This paper presents three components that can be added to deep deterministic policy gradients (DDPG) algorithm to improve its performance. These components are (a) a new exploration strategy $\epsilon t$-greedy that performs exploration by building a tree to find the states at the frontier of its exploration and a path to get to those states, (b) a divided replay buffer to keep special track of successful episodes, and (c) changing the critic update to use T-step updates, turning the successful episode targets into Monte Carlo returns. The paper evaluates these techniques on three navigation and three manipulation tasks that require continuous-space actions, and show that the proposed method, ETGL-DDPG, outperforms some of the baselines compared to.
weaknesses: * While the results in the paper appear strong empirically, there is some worry that methods that seem very similar to those proposed in the paper are not being compared to.
* The proposed $\epsilon t$-greedy exploration looks a lot like Go-Explore [1]. While there are certain differences (no behavioral cloning of the exploration policy), the similarities are close enough that they should be addressed in the paper or the method should be compared to. Additionally, the LSH method is very similar to #-exploration [2]. While perhaps comparing to the method itself might not be relevant since the results might not be state-of-the-art any longer, and the paper itself is cited, more detailed comparison to this technique in the related work would add depth to the paper.
* The use of two replay buffers, with one buffer used to store data leading to successes, sounds very much like [3]. Apart from the different replacement schemes (reservoir sampling vs FIFO), they seem like very similar ideas. Attribution and comparison (if relevant) would be good to have here.
* The longest n-step return is basically Monte Carlo updates for successes and very long N-step returns for failures. The change makes it (a) not use bootstrapping for successes, and (b) not bootstrap from the agent's current Q-values efficiently.  Could the authors justify this change would be better? Specifically, why the high variance updates from successes are preferred to bootstrapping, and why the very long n-step returns are preferred for failures? The ablations (Figure 5) seem to bear out that these long returns are actually not helping.
* Overall I feel like the exploration component is the main and helpful part of the paper. I would prefer the paper focus on this idea, and bring the analysis, such as Section A.5 into the main paper. That would be a much more impactful contribution, in my opinion.

Some minor nitpicks:
* Line 462: "except for soccer, where DDPG alone outperforms all baselines." The results show that $\epsilon t$-greedy outperforms DDPG there.
* Algorithm 1, line 24: typo: UnifromRandom($\phi(s_x)$)
* Algorithm 1, line 9: frontier nodes not being passed.
* Algorithm 1, line 10, counting function $n$ is not specified as an input, nor initialized.

References:

[1] Ecoffet, A., Huizinga, J., Lehman, J., Stanley, K.O. and Clune, J., 2021. First return, then explore. Nature, 590(7847), pp.580-586.

[2] Tang, H., Houthooft, R., Foote, D., Stooke, A., Xi Chen, O., Duan, Y., Schulman, J., DeTurck, F. and Abbeel, P., 2017. # exploration: A study of count-based exploration for deep reinforcement learning. Advances in neural information processing systems, 30.

[3] Kompella, V.R., Walsh, T., Barrett, S., Wurman, P.R. and Stone, P., Event Tables for Efficient Experience Replay. Transactions on Machine Learning Research.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Default exploration in DDPG is based on the OU noise, which is a temporally-correlated noise. As such, I'm curious if the "DDPG" baseline in, e.g., Fig. 5 is based on $\epsilon$-greedy or the standard OU noise? (And does your answer hold for all results for DDPG in the paper?) 

2. Have you performed any leave-1-out ablations as well? I.e. similar to Fig. 5 but with the full algorithm minus one addition.

3. Do you have any comment on including DDPG + PER + N-step returns as a baseline?

4. Regarding the options generated by your tree-search approach: Will they remain valid in stochastic domains?

5. Why is there no Importance Sampling correction (similar to PER) to reduce the bias of sampling from successful episodes more frequently?

6. Why are there no experiments / detailed discussions around Hindsight Experience Replay?

7. Could you comment on connection of your approach wrt. count-based exploration techniques in DRL?

8. Is the discretization of "states" really discretizing the true state of the problem or just the 2/3 spatial locations?


### Minor comments:
L252: Comma should move to the end of equation.
soundness: 3
strengths: - The proposed recipe will be useful for those interested in similar problem scenarios, e.g. using DDPG for tackling physical control problems.

- Paper is generally well-written, and ideas are mostly easy to grasp.
summary: This paper introduces a recipe of additions to DDPG that would make it particularly suitable for addressing sparse-reward (in particular, those with informative rewards only on the last transition of successful episodes). The recipe involves three main components: (1) $\epsilon t$-greedy exploration, (2) an additional episodic buffer only containing successful episodes, and (3) Monte Carlo updates on successful episodes instead of 1-step TD. 

The most involved component of the approach is (1), which involves tree-search for finding a good option to execute. This process requires a model of environment's transition dynamics in principle, which the authors circumvent by using the replay buffer as a model and utilizing a SimHash model on a discretized variant of the 2D or 3D environments.

They evaluate the performance of this approach on several sparse reward testbeds: physics based 2D point-mass and 3D robotic manipulation tasks, as well as non-physical maze problems. The results show full coverage of discretized 2D or 3D spaces due to addition (1). Also, reaching success rates close to 1 on all tasks (on average), and generally well above other baselines.
weaknesses: - Several related works are not sufficiently discussed in the context of the contributions:
    - Count-based methods in DRL: e.g. Ostrovski et al. (2017) is referenced but not discussed to any extent in connection to the SimHash method. 
    - Hindsight Experience Replay is a relevant line of work, as it's addressing the same type of problems while remaining simpler and broader in applicability. While the paper is referenced, it is not used as a baseline nor discussed to an appropriate extent. 

- Baselines are unfortunately somewhat weak; e.g. D3PG (non-distributed variant of D4PG) would be an important baseline to build on and/or to compare against. Specifically, DDPG + PER (as in D3PG) would have allowed to better assess the impact of the dual-memory approach. DDPG + N-step return (as in D3PG) would have allowed to better assess the difference between with a standard approach beyond 1-step TD updates. I wouldn't even worry about the distributional component of D3PG/D4PG, but combinations with PER and N-step returns are quite important to test against.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 3
questions: Following the previous paragraph,
- Can the author provide a comparison to HER?
- Why is the proposed graph search procedure is more appropriate than existing ones? Does it outperform them?
- Are the three proposed techniques orthogonal?

Moreover, some minor questions and comments:
- Why is DDPG chosen as the base deep reinforcement learning algorithm, instead of relatively more modern algorithms such as TD3 [5] or SAC [6]?
- line 83: authors state that "the agent must achieve the goal many times to make sure that the reward is eventually propagated backward to early states". I am not coninced this statement holds. To the best of my knowledge, rewards are propagated when optimizing the TD loss for a given batch; therefore, it is sufficient to sample sufficient batches as long as the goal is achieved a single time in the buffer. I would ask the authors to comment on this.
- n-step returns are on-policy. It could be helpful to acknowledge this.
- line 88: typo (new temporally version) to (new temporally extended version)
- line 206: typo ($\delta$-optimal) to ($\epsilon$-optimal)
- line 246: typo, I believe ($\mathcal{P_W}$) to ($\mathcal{P_X}$)
- line 315: the chosen baselines are arguably not state-of-the-art for sparse-reward environments, see comments above.

**References:**

[1] Andrychowicz et al., Hindsight Experience Replay, NIPS 2017

[2] Ecoffet et al., First return, then explore, Nature 2021

[3] Gallouedec et al., Cell-Free Latent Go-Explore, arXiv 2023

[4] Eysenbach et al., Bridging Planning and Reinforcement Learning, NeurIPS 2019

[5] Fujimoto et al., Addressing Function Approximation Error in Actor-Critic Methods, ICML 2018

[6] Haarnoja et al., Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor, ICML 2018
soundness: 2
strengths: - The paper is well written and easy to follow. Contributions are outlined clearly and supported by experimental evidence.
- The limitations of hashing are acknowledged in the final discussion.
summary: This work combines three algorithmic ideas to improve the performance of DDPG in sparse-reward tasks. Fist, the authors propose $\epsilon$t-greedy exploration, which consists in building a graph-based representation of the environment, and navigating to nodes with a low visitation count. This method is accompanied by a formal analysis. Additionally, a buffer sampling technique is used to prioritize transitions with non-zero rewards, and longest n-step returns help quickly propagating values across trajectories. The resulting method, named ETGL-DDPG, outperforms simple algorithms in six continuous control tasks, demonstrating that each of the three components positively affects performance.
weaknesses: - Related works and missing baselines: this works does not sufficiently mention established methods for exploration in sparse reward settings. To the best of my knowledge, the standard method for sparse-reward RL is HER [1], which is only quickly mentioned in Section 5. Explaining why HER is not a relevant baseline would be very important. Otherwise, a comparison to it is expected. Moreover, the core exploration technique relies on a graph-search procedure. Similar ideas have been proposed in the past, both in the context of exploration [2, 3] and general value estimation [4]. Methods involving graph-search are very powerful, but require non-trivial implementation efforts and introduce complexity. None of the baselines considered relies on a graph; I would encourage the authors to clearly argue why the proposed graph search procedure is more appropriate than existing ones, or show how it outperforms them. More in general, the selection of baselines includes simple methods designed for the general RL problem, and not specialized to sparse-rewards.
- Novelty and orthogonality: the second and third technique (the dual replay buffer and longest n-step rewards) are not entirely novel, as acknowledged in lines 273 and 298. They appear to be applied without further analysis or changes. Moreover, the graph-based technique seems to work well $independently$ from the other two. It thus seems that the three proposed techniques are rather orthogonal. Why is it important to combine all three techniques? How do they relate to each other? In the current state, I do not appreciate the novelty in the second and third techniques, and thus wonder why the authors would not focus on the first one.