ETGL-DDPG: A Deep Deterministic Policy Gradient Algorithm for Sparse Reward Continuous Control
Authors: Ehsan Futuhi
Shayan Karimi
Chao Gao
Martin Müller
Venue: Accepted by TMLR ()

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, \emph{${\epsilon}{t}$-greedy}, which generates exploratory options for exploring less-visited states. We prove that search using $\epsilon 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, \emph{GDRB}, and implement \emph{longest n-step returns}. The resulting algorithm, \emph{ETGL-DDPG}, integrates all three techniques: \bm{$\epsilon t$}-greedy, \textbf{G}DRB, and \textbf{L}ongest $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.

Shayan Karimi Published in Transactions on Machine Learning Research (05/2025)
ETGL-DDPG: A Deep Deterministic Policy Gradient Algo- rithm for Sparse Reward Continuous Control
Ehsan Futuhi
Department of Computing Science, University of Alberta
Department Compuling Science, University of Alberta
Chao Gao
Huowei Conada Research Center, Edmonton, Canada
Martin Müller
Department of Computing Science, University of Alberta
Reviewed on OpenReview: https: // optp///veeeevveeeeee net/ htl//forurt forum? id= 6g1W155W51
Abstract
We consider deep deterministic policy gradient (DDPG) the context of reinforcement learning with sparse rewards. To enhance exploration, we introduce search procedure, greedy, which generates exploratory options for exploring less-visited states. We prove that search using et-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 lechniques: et-greedy, GDRB, and Longest n-step, into DDPG. We evaluate ETGL-DDPG on standard benchmarks and demonstrate that outperforms DDPG, as well as other statc-of-the-art methods, across all lested 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) (Lilicrap et al. 2015 is one of the representative algorithms for reinforcement learning (RL) Sutton & Barto 2018 alongside other prominent approaches (Haarnoja
et al. 2018 Fujimoto et al. 2018: Andrychowicz et al. 2017). In recent years, DDPG has served as the backbone algorithm for introducing novel ideas in robotics and RL Barth-Maron et al. (2018); ; Pan et al.
(2020); Liu et al. (2023): Wang et al. (2023); Tiapkin et al. (202g). While DDPG demonstrates strong
performance continuous control tasks with dense reward signals (Duan et al., 2016; Kiran et al., 2021 effectiveness diminishes significantly in sparso-reward settings where rewards are only observed upon
reaching the goal (Matheron et al., 2019: Luck et. al.) 2019).
In sparse-reward environments where success depends reaching 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 algorithrss, DDPG employs a behavior policy for exploring the environment. The standard choices are either an e- e-greedy behavior policy that samples a random action with probability e (e.g., 0.1), or the main policy with artificial noise. As argued in (Dabney al. 2020), these one-stop noise augmented greedy strategics are ineffoctive for exploring large sparso-reward state spaces due to the lack of temporal abstraction. To improve e-greedy, Dabney et al. (0200) propose a temporally extended ez-greedy policy that expands exploration

---

Published in Transactions on Machine Learning Research (05/2025)
Mass) > 6iss)
Atore
kn
Dg
(oedy
200 scarch
store n in
cherwise
with prob
Wh Tha 7 + 1ha +
(a) el-greedy: greedy or tree search
(b) GDRB and the longest n-step return
Figure 1: (a): et-greedy exploration strategy. The agent creates tree from the current state St with probability. Otherwise, it uses its policy to determine the next action ar n. The tree é to estimate the visit counts to states. If the newly added node & to the tree is located in unvisited area n(((s.)) = O, the path from the root to that node is returned as option O. The tree helps in avoiding obstacles, discovering unexplored areas, and staying away from highly-visited regions (middle red area). (b): GDRB and the longest n-step return for Q-value updates. T reaches the goal (a successful episode), and T2 is truncated by time limit (an unsuccessful episode). The first buffer D3 stores both trajectories but De only stores successful trajectories. The target Q-value for state 8, shown for both trajectories below the figure. In successful episodes, the target Q-value is the episode return. ST represents the last state in each episode, which is the goal state indicated by a star in T1.
hash function
into multiple steps, controlled by distribution éz-greedy represents an advancement. from the option framework for reinforcement learning (Sutton et al. 1999). Theoretically, option O is defined tuple O = (I, T,, B), where I is the set of states where an option can begin, is the option policy that determines which actions to lake while executing the option, and B is the termination condition. In ez-greedy, each option repeats a primitive action for a specific number of time steps which is sampled from a distribution = (e.g., uniform distribution). The option can begin at any state with probability e and terminates whenever their length reaches a limit that decided by 2. While ez-greedy improves over e-greedy, it also directionless: for exploratory action, the agent does not use any information from its experience for informed exploration.
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 '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., 2015). For problems with well-defined goals, 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. is known that one way to achieve this to provide intermediate rewards with reward shaping methods [Laud] 2004). However, effective reward shaping usually problem-specific and does not generalize to wide range of tasks.
In this paper, we enhance DDPG (Lillicrap et al. 2015 to address all three aforementioned problems. We choose DDPG over SAC, as SAC's maximum entropy framework already provides advanced exploration, and combining it with our components would introduce extra complexity, making it harder to isolate and analyze our contributions. Our first contribution is et-greedy, a new temporally version e-greedy that utilizes light- search procodure, similar to Laud (2004), enable more dircctional exploration basod on the agent's previous experience data. We show that similar ez-greedy, et-greedy has polynomial sample complexity in related parameters of the MDP. Our second contribution is a gonl-conditionee dual replay
2

---

Published in Transactions on Machine Learning Research (05/2025)
buffer (GDRB), that uses two replay buffers along with 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 T the innovations of ETGL-DDPG. In Section we evaluate the performance of ETGL-DDPG through extensive experiments on 2D and 3D continuous control benchmarks. As the proposed strategies are orthogonal, we show that each of the three strategies individually improves the performance of DDPG via thorough ablation study. Furthermore, ETGL-DDPG outperforms current state-of-the-art methods across all tested environments.
2
Background
We consider Markov decision process (MDP) defined by the tuple (S, is the set of actions, T(s'|s, (s, a) is the transition distribution, r: 5x IR. is the reward function, y [0, 1] is the discount factor, and p(so, 9g) is the distribution from which initial and goal states are sampled for each episode. Every episode starts with sampling new pair of initial and goal states. At cach time-step t, the agent chooses an action using its policy and considering the current state and the goal state = ((5,, 8g) resulting in reward r; = (st, Qt, 8y). The next state is sampled from T(Iss,, az). The episode ends when either the goal state or the maximun number of steps is reached. The return the discounted sum of future rewards R₂ EL ? The Q-function and value function associated with the agent's policy are defined Q" (,, ut 5g) [[[ Oz 8y and V (st; 8y) max, (8t, a:: 8g)- The agent's objective is to learn optimal policy n² that maximizes the expected return Eg RR Sgl--
S the set of states, A
2.1 Deep Deterministic Policy Gradient (DDPG)
To ease presentation, we adopt our notation with explicit reference the goal state for both the critic and the actor networks in DDPG. DDPG maintains an actor (((s,8)) and critic Q(s, a, 8g). The agent explores the environment through stochastic policy a p(8, 8g) + w, where is noise sampled from a normal distribution or an Ornstein- Uhlenbeck process (Uhlenbeck & Ornstein 1930). To update both actor and critic, transition tuples are sampled from a replay buffer to perform mini-batch gradient descent. The critic is updated by a loss L,
L R[Q(st, (e, y
(1)
where i t ul (8441, 8g). Q' and p¹ 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. 2014) to maximize the estimated Q-values of the critic using loss [Q, u(s, sp),
2.2 Lecssity-Sensitivee Hashing
Our approach discretizes the state space with a hash function o: 8 >> M,, that maps states to buckets in M. When we encounter a state s, we increment the visit count for @(s). We use n(((s)) as the visit counts all states that map the same bucket ((s). Clearly, the granularity of the discretization significantly impacts our exploration method. The goal for the granularity that "distant" states are in separate buckets while "similar" states are grouped into one.
We use Locality-Sensitive Hashing (LSH) our hashing function, popular class of hash functions for querying nearest neighbors based on a similarity metric (Bloom) 1970). SimHash (Charikar) 2002) is a computationally efficient LSH mothod that calculates similarity based on angular distance. SimHash retrieves a binary code state E S as
((s) sgn (A)()) E (-,,
(2)
3

---

Published in Transactions on Machine Learning Research (05/2025)
where f - R is preprocessing function and A is k x D matrix with i..d. entries drawn from standard Gaussian distribution 1). The parameter & 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 strategics in ETGL-DDPG for improving DDPG in sparso-reward tasks. The full pseudocode for ETGL-DDPG is presented in Supplementary Algorithm 3
3.1 et-Greedy: Exploration With Search
In principle, exploration should be highest at the beginning of training, as discovering rewarded transitions during carly steps is essential for escaping local optima (Matheron et al. 2019). Motivated by the success of the fast exploration algorithms RRT (La 1998) and ez-greedy (Dabney et al. 2020 we introduce et-greedy, which combines e-greedy with a tree search procedure. Like e-greedy, et et-greedy selects a greedy action with probability uniformly at random, the exploratory action in el-greedy is the first step of an option generated via search with time budget. N.
6, and an exploratory action with probability c. However, instead of exploring
To execute the search process, the agent requires access to the environment's transition function 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 T is not known. Instead, the agent utilizes its replay buffer to advance the search. We briefly discuss the impact of having access to T on the exploration process in Supplementary Material A.4 We also assume that the agent has SimHash function Φ, which discretizes the large continuous environment. For each state s, n(ő(s)) serves estimate of the number of visits to neighbourhood of throughout the entire learning process.
The replay buffer contains transitions observed during training. It can be used observed transitions and an approximate one for transitions similar to those already seen. For simplicity, we identify each bucket with its hash code ((s). We use a buffer Bas which stores observed transitions based on the hash of their states d(s). If the agent makes a transition (st, at Ft, 8:41) in the environment, the transition is stored in bucket b = (s:)). All transitions are assigned their buckets upon being added 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 full bucket with the new transition.
transition model for
buffer in Algorithm | shows how new nodes can be added to the search: assuming we are at node $a, we randomly select transition (s', s") in bucket Φ(sx) and create a new child Sgr for 8z by using following approximation:
The function fext_state_fete from_rrr____ee
T(s,: = T(5
Algorithm [ explains how the search generates an exploratory option. Initially, at state s, create list of frontier nodes consisting of only the root node s. If bucket of state in By is empty: bo(a) = Ø there is no transition to approximate a(s, In this case, et-greedy as in e-greedy generates random action at 8. Otherwise, when bo(s) # Ø, el-greedy conducts a tree search iteratively, with a maximum of iterations. At each iteration, a node se is sampled uniformly from the frontier nodes, and a child for 82: noted as sw' is buffer function. If n()(s=)) = 0, we terminate and return the action sequence from the root to 82' otherwise, we repeat this process until we have added N nodes to the tree. We then return the action sequence from the root to least-visited node smin:
generated using pext_state___ lrr___tttttt__________ rrufer
Smin frontier nodes
min
n(((s))
(4)
To justify this exploration method, we adopt the conditions outlined in Liu Brunskill (0188) validate the sample efficiency of el-greedy. We begin by introducing the relevant terms and then present. the main
4

---

Published in Transactions on Machine Learning Research (05/2025)
theorem. Detailed definitions and proofs are provided in Appendix A.1 The key idea is to define 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 8 Mansour 2004) represents the mini- mum number of steps an agent must take in an MDP, starting from any state-action pair (s, E 8 x A, to visit all state-action poirs at least once with a probability of at least 0.5. We define the covering length only for discrete MDPs; for continuous MDPs, we consider a discretization of the action space S x A.
Our objective is to find near-optimal policy, as defined in Definition
2
Definition 2 (r-optimal Policy). A policy a called e-oplimal if it satisfies V* (8) - V*(() S6, for all S, where <>
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 S, action space A, suboplimalily ervor >> O (from Definition and 0 < 8 < 1, algorithm A is called PAC-MDP (Kokade) (003)), if the number of time steps required to find c-optimal policy is less than some polynomial in the relevant quantities (1,, 1-7-7) 2) with probabilily at least 1 1-5.
For simplicity, when we say an algorithm A has polynomial sample complexity, we imply that A is PAC- MDP. The work by Liu & Brunskill (2018) establishes polynomial sample complexity for a uniformly random exploration by bounding the covering length defined in Definition [I] Using this, and considering a limitod free budget N, we show that el-greedy is PAC-MDP. Let's denote the search tree by X, and the distribution over the generated options in X' as Pxx The following Theorem provides lower bound option sampling in tree X under certain condition.
Theorem 1 (Worst-Case Sampling). Given tree X with N nodes (si to SN), for any E Qxx the sampling probability satisfies:
Px|w] 2 NI(maxie[M) lo(s.))) 2 @((i)|A))
(5)
if N
log(l (AA)) log log( STTAT] Here, S and A represent the state space and action space, respectively.
To prove Theorem D we examine the construction of the "hardest option", a E U2x which has the lowest sampling probability in the tree X. Since Px is an unknown distribution, we cannot directly exploit it. Instead, we construct worst-case scenario to approximate the minimum option sampling probability. Now, we present the following Theorem on the sample complexity of et-greedy.
Theorem 2 (et-greedy Sample Efficiency). Given a state space S, action space A, and a set of op- tions Qx generaled by el-greedy for each tree X, Px(w]= 2 eाii|clis el-greedy achieves polynomial sample complenity or í.e. is PAC-MDP.
Theorem asserts that the sampling bound condition from Theorem is satisfied when N log log( 3 ATI Theorem 2 establishes the necessary lower bound on the sampling probability of an option w E 2x for any given exploration tree X, ensuring that the el-greedy strategy is PAC-MDP under this criterion.
log([S]|A[)
3.2 GDRB: Goal-conditioned Dual Replay Buffer
The experience replay buffer is indispensable part of deep off- off-policy RL algorithms. It is common to use only one buffer to store all transitions and use FIFO the retention policy, with the most recent data replacing the oldest data (Muih et al.) 2013). As an alternative, in the reservoir sampling [Vitter 1985) retention policy, each transition in the buller has an equal chance of being overwritten. This maintains coverage of some older data over training. RS-DRB [Zang et al., 2019) 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
5

---

Published in Transactions on Machine Learning Research (05/2025)
Algorithm Generating exploratory option with tree search
1: function generate (ttprttttt_piootttttteeee hash function 6, budget N)
2: frontier modes t- [
3: Initialize root using s: real 4- Tree:odel(s)
4: frontier nodes + frontier nodes {root};
5: Smin 4 root
6: i i
while i < do
8:
8, ~ UnfoommHannoomfrrntier _ndess)
=, next state from bbuf__uffrrrss)
10:
if n((()==))== then For state to be in the replay bulfer, it must have been visited at least once.
Extract option o by actions root 8, return end
12:
14:
if n(((s.))) < n(((smm))) then
15:
8min=8r
16:
end if
17:
--111
18:
end while
19:
Extract option o by actions root to 8min
return
21:
end function
fatte___roommuffrrf..... frontier (roniee__ndees) 23: function UnifromRendom((eC
(s', (',,,,,&"))
25: Se -
add )
27: frontier nodes +- frontier nodes U {82r}
return 85'
29: end function
Inspired by this dual replay buffer framework, we propose Goal-conditioned Double Replay Buffer (GDRB). The first buffer Dg stores all transitions during training, and the second buffer D. stores the transitions that belong to successful episodes (i.e., goal reached). D3 uses reservoir sampling, and De uses FIFO. Since D3 needs to cover transitions from the entire training process, it is larger than D.- We balance the mumber of samples taken from the two buffers with an adaptive sampling ratio. Specifically, process E episodes, current episode the sampling ratios тę and т3 for De and D3 are as follows: To ; Tg 1 Te- To select C mini-batches, max( [Ty CJ, 1) mini-batches are chosen from D3 and the rest from D.. Later stages of training still sample from Dg to not forget previously acquired knowledge, assume the policy is more likely to reach the goal the training progresses. In case that D, is empty, since there are no successful episodes yet, we draw all mini- batches from Dg.
a training
3.3 Using Longest 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 succossful 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.) 2021 Hessel et al. 2018). For example, Meng et al. (2021) utilize n-stop updates DDPG with n ranging from to 8. In our design, share the reward from the last step of successful episode for all transitions the episode, we use longest n-step return (Mnih et al. 2016). shown in Equation 6

---

Published in Transactions on Machine Learning Research (05/2025)
(a) Wall-maze
(b) U-maze
(c) Point-push
(d) soccer
window-open
press-button
Figure 2: The environments used in our experiments.
Exeo 7 retk.
sT a goal slate
Q(sc. =
(6)
Ei-t-igh rre + +
otherwise
Here, ST is the last state in the episode. Using the longest n-step return for each transition from successful episode, the reward is immodiately propagated to all Q-value updates. In unsuccossful episodes, using the longest n-step return reduces the overestimation bias in Q-values TTrun & Schwartz 1993). Meng et al. (2021) 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, 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 maate-ofthheart methods in goal-reaching tasks with sparse rewards? 2) How does each of these three in- novations impact the performance DDPG? 3) Can el-greedy explore more efficiently than e2-greedy and other common exploration strategies?
We consider two types of tasks: navigation and manipulation. We use three sparso-reward continuous environments for navigation. The first environment is 2D maze called Wall-maze (Trott et al. 2019). where reward of -1 is given at cach step, and 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, shown in Figure 2h. The agent's action (dx,dy) determines the amount of movement along both axes. The environment contains a gradient cliff fcature (Lchman et al., 2018), where the fastest way to reach the goal results a deadlock close to the goal. Our second and third environments are U-maze (Figure (b) and Point-push (Figure : [Kanagawa] 2021), designed using the MuJoCo physics engine (Todorov et al. 2012)) In both environments, 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 2H, e, and f) Yu et al. 2020). In window-open, the goal is to push the window open; in soccer, the goal is to kick the ball the goal; and in button-press, the aim is to press the top-down button. Each episode begins with the robot's gripper in randomized starting position, while the positions of other objects remain constant. The original versions of these tasks employ uniquely shaped reward function for each task. However, these versions offer limited challenges for exploration, standard baselines, such as SAC, demonstrate strong performance YYu et al. 2020). We modified the original reward function to be sparse, transforming these tasks into challenging exploration problems.
The maximum number of steps per episode to 100 for Wall-maze and 500 for all other environments. Across all methods, the neural network architecture consists of hidden layers with 128 units each, using ReLU activation functions. For standard baselines, utilize the implementations from OpenAT Gym

---

Published in Transactions on Machine Learning Research (05/2025)
success rate
success rate
success rate
1.0
1.0
1.0
0.8-
0.8
0.8
0.6
0.4
0.2
0.2
0.2
0.0
0.0
0.0
100
200
300
400
500
600
6
100
200
300
400
sdo
600
100
200
300
400
500
60D
checkpoints
checkpoints
checkpoints
(a) Wall-maze
(b) U-maze
(c) Point-push
success rate
success rate
success rate
1.0
0.8-
0.8
0.8
0.6
0.6
0.6
0.2
0.0
0.0
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
0
25
50
75
100
125
150
175
200
checkpoints
checkpoints
checkpoints
(d) soccer
(e) window-open
(f) press-button
ETGL-DDPG
DOIE
SAC
TD3
DDPG
Figure The success rates across environments, averaged over 5 runs with different random seeds. Shaded areas represent one standard deviation. We trained all methods for million frames in the navigation environments and 2 million frames in the manipulation environments, with success rates reported at every 1te-step checkpoint. A moving average with window size of 10 is applied to all methods for better readability.
DDhriwal et al. 2017), and for other baselines, rely their publicly available implementations. After testing various configurations, we found that el-greedy and ez-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.5
4.1 Overall Performance ETGL-DDPG
We evaluate the performance of ETGL-DDPG compared to state-of-the-art methods. We compare with SAC (Haarnoja et al.] 2018), TD3 (Fujimoto al.] 2018), DDPG, and DOTE (Lobel et al. (022)- DOIE demonstrates state-of-theeat performance in challenging sparse-reward continuous control problems by dras- tically improving the exploration. While both DOIE and et-greedy observed states, DOIE applies this to compute optimistic value function rather than solely guiding the agent to unexplored areas. The results are shown in Figure B In the navigation environments. ETGL-DDPG and DOIE demonstrate superior performance compared lo 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 achieve a success rate above zero. In manip- poses the hardest challenge as none of the methods achieve a success of 1. ETGL-DDPG still outperforms all other approaches, while DOTE underperforms compared to SAC, indi-
similarity measure between new and
ulation tasks, the

---

Published in Transactions on Machine Learning Research (05/2025)
environment coverage
environment coverage
environment coverage
1.0
10
1.0
0.8
0.8
0.8
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.0
0.0
0.0
100
100
checkpoints
checkpoints
checkpoints
(a) Wall-maze
(b) U-maze
(c) Point-push
DDPG ezigreedy
DDPG
DDPG + rt-greedy
DDPG intrinsic motivation
DOIE
Figure 4: The environment coverage for exploration strategies in navigation environments. On the graph, the y-axis indicates the portion of the environment that has been covered, and the checkpoints occur every 10 steps shown on the x-axis. The results are given for the average of 10 runs with random seeds. The shaded region represents one standard deviation.
cating its limitations in adapting to high dimensional environments, Regarding training time, we observed that ETGL-DDPG requires approximately 1.5 times the training time of DDPG. This extended training duration can be attributed lo two main components: el-greedy and the longest n-step return. Among these, et et-greedy has greater effect, each step necessitates local search.
4.2 Enviromment Coverage through Exploration
We now examine how effective et-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 quantified the fraction of visited cells. Figure 4 presents comparison of environment coverage across different exploration strategies. All strategies except DOIE, which uses Radial Basis Function Deep Q-Network (RBFDQN) (Asadi et al. 2021), 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, et-greedy achieves 80% coverage, whereas DOIE reaches 60%. ez-greedy covers approximately half of the environment, whereas the remaining methods manage to explore only around 30%. In U-maze, strategies are successful, covering 80% or more of the environment. Even so, ez-greedy reaches full coverage faster than other methods. In Point-push, none of the methods can fully cover the environment and ultimately achieve nearly the same coverage. The tree budget N serves an upper bound on the option length in et- et-greedy, analogous to its role in ez-greedy when using uniform distribution 2(n) 1.5N// /N. We evaluate environment coverage under varying values of N in Section A.7 where results indicate that et-greedy achieves improved coverage as N increases. In contrast, ez-greedy does not exhibit a consistent improvement in coverage and, in some cases, experiences a decline. This highlights the advantages of directed exploration over undirected approaches. Finally, we present the distribution of final states reached in the episodes illustrate the order in which the agent visits different regions of the environment (soe Appendix A.8
In ez-greedy, various distributions be used to select options based their length. Although uniform distribution is straightforward choice, alternative distributions such the zeta distribution 2(n) x n
(where controls the decay ratc) can also be employed. Empirical results by (Dabney et al. 2020) show that the zeta distribution slightly outperforms the uniform distribution, and moreover, produces a pattern akin to Lévy flights observed in certain ecological foraging models (Baronchelli & Radicchi] 2013). Figure 5 shows the distribution of option lengths generated by ct-rrodyy during training across all environments, revealing two main observations: (1) moderate-length options have the highest probability of being selected, and (2) probabilities decay option length increases. While this decay pattern resembles that of the zeta

---

Published in Transactions on Machine Learning Research (05/2025)
0.25
0.20
probabilty
probability
probability
0.10
0.10
0.05
0.05
0.05
0.00
0.00
0.00
Option length
Option length
Option length (c) Point-push
(a) Wall-maze
(b) U-maze
0.20
probabiityy
probability
0.16-
probability
0.16
0.12
0.12
0.88
0.05
0.04
0.00
12
15
0.00
15
16
0.00
Option length
Option length
Option length
(d) soccer
(e) window-open
(f) press-button
Figure The distribution of options chosen training. The x-axis represents the length the options and the y-axis indicates the probability of each length, calculated based on how oflen each length chosen across all options.
success rate
success rate
success rate
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
100
200
300
100
500
600
0
100
200
300
400
500
600
100
200
300
400
500
600
checkpoints
checkpoints
checkpoints
(a) Wall-maze
(b) U-maze
(c)
Point-push
GDRB + longest n-step return
el-greedy GDRB
El-greedy + longest n-step return
DDPG
Figure 6: The ablation study for two wwo-oompn combinations in navigation environments. The success rates are averagod over 5 runs with different random seeds and the shadod arcas represent one standard deviation.
distribution (where length most likely), el-greedy instead favors moderate lengths. Note that Although options longer than 12 do occur, their frequency is extremely low and thus visible in Figure
4.3 Effectiveness Each New Component ETGL-DDPG
We evaluated the performance of ETGL-DDPG, and now we assess the impact of cach component on DDPG separately. Figure presents the results for environments. et-greedy demonstrates the most improvement. across all environments and is the only method that enhances the performance of DDPG in
10

---

Published in Transactions on Machine Learning Research (05/2025)
the Wall-maze, highlighting the critical role of our exploration strategy. GDRB shows a positive impact 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 negalively impacts performance in soccer and Point-push. We attribule this to the inherently high variance of multi-step updates. A comparison of Figures X and 7 across all environments shows that ETGL- DDPG consistently outperforms the use of each component individually, supporting the effectiveness of their combination.
To conclude the analysis of cach component, we conduct three additional experiments in this section. First, we perform an ablation study by considering all possible two-component combinations, where the omitted component in each combination is replaced with its DDPG counterpart. The results, shown in Figure G for the navigation environments, indicate that all combinations outperform DDPG in every environment except Wall-maze, where the agent fails to achieve a non-zero success rate without c-greedy exploration. Moreover, in Poinl-push, omilting the longest n-step return while following the original DDPG strategy causes noticeable decline in success rates during the later stages of training.
Second, we compare the longest n-step return with the method proposed by Meng et al. 2022 J, who exper- imented with n ranging from 1 to 8 and tested both the minimum of the n-step returns and their average. In their experiments, MMDDPG, which computes the average return over to 8 steps (avgs-step), outper- forms other variants in robotic tasks. Here, we replace the longest n-step return in ETGL-DDPG with the step return to evaluate its effectiveness in reward propagation. The results, presented in Appendix A.2, show that both methods perform similarly across most environments, except in Wall-maze, where the longest n-step return outperforms the avgê-step approach. Notably, the avg8-step method converges more rapidly, likely due to the stabilizing effect of averaging multiple updates.
Lastly, we compare GDRB with Hindsight Experience Replay (HER) Andrychowicz et al. 2017), a method for sparse-reward tasks that increases feedback to the agent by treating certain states in unsuccessful episodes as imaginary goals. By assigning rewards to these artificially generated goals, HER can leverage unsuccessful episodes more effectively. Figure g in Appendix A..3 compares the impact of GDRB and HER on DDPG in navigation environments. In Wall-maze, HER enables the agent to learn from previously unsuccossful trajectories, allowing il to achieve success rales above zero. In the other two environments, both GDRB and HER exhibit similar performance, although HER converges more quickly due to its reward-reshaping mechanism, which provides stronger guidance in the initial stages of training.
5 Related Work
Intrinsic Motivation. Intrinsic motivation mothods (Burda et al. 2018 Pathak et al. 2017 Ostrovski eet al.] 2017 Tang el al., 2017) provide a reward bonus for unexplored areas of the state space, enabling the agent to receive more feedback in sparse-reward scenarios. However, since a transition can receive varying rewards at different time steps, these methods make the reward function non-stationary, violating the Markov assumption of MDPs. They are also sensitive to hyperparameters, requiring extensive tuning for each environment (Schäfer et al.] 2021). Decoupled RT algorithms (Schafer et al. 2021 Badia et al. 2019) address this issue by training separate policies for exploration and exploitation, where the exploitation policy optimizes sparse rewards while leveraging data collected by the exploration policy. Although this resolves the non-stationarrty issue, it doubles the computational cost. el-greedy is similar to /Tang et al. (2017) in identifying less-cxplored states using the SimHash function. However, unlike intrinsic motivation mothods, el-greedy does not modify the reward function. Instead, it directs the agent toward less-explored states, preserving the stationarity of the reward function while avoiding the need for additional computation.
Other Exploration Techniques. There are also other strategics to improve exploration without using reward bonuses. Colas et al. (0018) use a policy search process to generate diverse data to improve training of DDPG. Liu et al. (2018) 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 is rewarded for visiting states discovered by A. Plappert et al. (2018) directly inject noise into the policy's parameter space instead of the action space. Eysenbach et al. (2019) build graph using states in the replay buffer, allowing
11

---

Published in Transactions on Machine Learning Research (05/2025)
success rate
success rate
success rate
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.4-
0.4
0.2
0.2
0.2
0.0
0.0
100
200
300
400
500
600
6
100
200
300
400
50o
600
100
200
300
400
500
60D
checkpoints
checkpoints
checkpoints
(a) Wall-maze
(b) U-maze
(c) Point-push
success rate
success rate
success rate
1.0
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
25
50
75
100 125 150 175 200
0
25
50
100
125
150
175
200
25
50
75
100
125
150
175 200
checkpoints
checkpoints
checkpoints
(d) soccer
(e) window-open
(f) press-button
DDPG + et-greedy
DDPG + GDRB
DDPG longest n-step return
DDPG
Figure 7: Analyzing the individual impact of three components on DDPG: et-greedy, GDRB, and longest n-slep return.
the agent to navigate distant regions of the enviromment by applying Dijkstra's algorithm. et-greedy shares similaritios with Eysenbach et al. (2019) in constructing a tree structure within the state spaco. However, while Eysenbach el al. (2019) builds single global graph to connect the start state to the goal state, el- greedy generates local trees dynamically, focusing on accessing less-explored areas. Ecoffet et al. (2021) introduce Go- Explore which separates exploration and policy optimization into two distinct phases. During archive of
the exploration phase, the algorithm systematically explores the environment by maintaining visited states along with their corresponding trajectories. In the robustiifcatiinn phase, these trajectories are leveraged to train a robust policy using standard reinforcement learning methods, such as PPO. However, a key limitation of Go-Explore is its reliance on resetting trajectories to return to previously visited states, a feature that is often unavailable many real-world scenarios. Lobel et al. 2022 present Deep Optimistic Initialization for Exploration (DOTE), which improves exploration continuous control tasks by maintaining optimism in state-action value estimates. Lobel et al. (2023) demonstrate that DOIE can estimate visit counts by averaging samples from the Rademacher distribution instead of using density models. [Dey et al.) (2024) present COIN, continual optimistic initialization strategy that extends DOIE to stochastic and non- stationary environments. Chakraborty et al. (2023) leverage hcavy-tailed action distributions to enhance exploration in continuous control lasks. Waan et al. (2022) propose a framework in which learned high- level policies select among a set of pre-designed low-level base controllers, allowing the agent to decompose complex long-horizon tasks into simpler control primitives. [Dawood et al. (2023) use model predictive control (MPC), where learned high-level policy proposes goals or waypoints, and MPC used to generate low-level actions that guide the agent toward those goals.
12

---

Published in Transactions on Machine Learning Research (05/2025)
Experience Replay Buffer. Rather than uniformly sampling from the buffer, Prioritized Experience
Replay (PER) (Schaul et, al. 2015) prioritizes transitions in the bulfer based on reward, recency, or TD error at the expense of (log N) per sample, where N is the buffer size. CER (Zhang & Sutton 2017 includes the last transition from the buffer to each sampled batch with O(1) complexity, [hhan et al. (2022)
learn a conservalive value regularizer only from the observed transitions in the replay bulfer to improve the sample efficiency of DQN. Pan et al. (2022) thcoretically show why PER has a better convergence rate than uniform sampling policy when minimizing mean squared error. Furthermore, Pan et al. (2022) identify two limitations of PER: outdated priorities and insufficient coverage of the state space. Kompella et al. (2023) propose Stratified Sampling from Event Tables (SSET), method that partitions the experience replay buffer into distinet Event Tables. Each Event Table captures significant subsequences of optimal behavior, allowing for more targeted sampling during training. GDRB aligns conceptually with SSET if achieving a goal is defined as the sole event. However, SSET employs FIFO for inserting new data into its buffers, whereas GDRB uses reservoir sampling for its success-ovent buffer. Morcover, in SSET, the sampling ratios between buffers are fixed, while GDRB dynamically adjusts these ratios over time favor the smaller buffer.
Reward Propagation. Reward shaping (Laud 2004 Hu et al. 2020) creates artificial intermediate rewards to facilitate reward propagation. However, designing appropriate intermediate rewards is hard and often problem-specific. [Trott et al. (2019) address this issue by introducing self-balancing reward shaping in the context of on-policy learning. Their approach defines the local optimum as the closest visited state to the goal and calculates the reward for each state based on its distance from the local optimum and the goal. By dynamically adjusting the local optimum, the agent is guided toward the optimal behavior. To extract more information from an unsuccessful episode, [Andyychowicz et al. (2017) introduce imaginary goals. An imaginary goal for state s is a state that is encountered later in the episode. Learning to achieve these imaginary goals helps the agent understand the structure of the enviromment. Memarian et al.) propose Self-Supereised Online Reward Shaping (SORS), a method that alternates between ranking trajectorics using sparse rewards and training a classifier to infer a dense reward function from these rankings. The inferred dense rewards are then utilized to update the agent's policy. Devidze et al. (2024) present a reward informativeness criterion that adaptively constructs interpretable reward functions based on the agent's current policy. |Wilexx et al. (2022) propose a Monte Carlo Augmented Actor-Critic (MCA2C) framework that integrates Monte Carlo returns from suboptimal demonstration trajectories into the critic update to improve value estimation in sparse-reward settings. By combining lemporal-difference largets with demonstration--ast based Monte Carlo returns, the method provides more informative learning signals during early training, enabling the agent to better propagate sparse rewards. BBath--Maro et al. (2018) propose D4PG by utilizing distributional critic updates, n-step returns, and distributed training across multiple agents, which leads to improvements in wall-clock training time and data efficiency.
6 Conclusions and Future Work
We have introduced the ETGL-DDPG algorithm with three orthogonal components that improve the per- formance of DDPG for sparse-reward goal-conditioned environments. el-greedy is a temporally-exteedded version of e-greedy using options generated by search. We prove that et-gre achieves a polynomial sample complexity under specific MDP structural assumptions. GDRB employs an extra buffer to separate success- ful episodes. The longest n-step return bootstraps from the Q-value of the final state in unsuccessful episodes and becomes Monte Carlo update in successful episodes. ETGL-DDPG uses these components with DDPG and outperforms satte-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 imago-basod problems such as real-world navigation, the future direction is to leverage dynamic hashing techniques such as normalizing flows [Papamakarios et al.) 2021) as these tasks demand more intricate representation learning, Additionally, dt-reedy and GDRB are designed for deterministic domains and would require adaptation for stochastic environments. Extending these components stochastic domains represents another promising direction for future research.
13

---

Published in Transactions on Machine Learning Research (05/2025)
References
Marcin Andrychowiez, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Picter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. Advances in Newral Information Processing Systems, 30, 2017.
Kavosh Asadi, Neev Parikh, Ronald E Parr, George Konidaris, and Michael L Littman. Deep radial-basi value functions for continuous control. In Proceedings of the AA Conference on Artificial Intelligence, volume 35, pp. 6696 6704, 2021.
Adríà Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martin Arjovsky, Alexander Pritzel, Audrew Bolt, et al. Never give up: Learning directed exploration strategies. In International Conference on Learaing Representations, 2019.
Andrea Baronchelli and Filippo Radicchi. Lévy flights in human behavior and cognition. Chaos, Solilons & Fractals,
2013.
Gabriel Barth-Maron, Matthew W Hoffman, David Budden, Will Dabney, Dan Horgan, TB Dhruva, Alistair Muldal, Nicolas Heess, and Timothy Lillicrap. Distributed distributional deterministic policy gradients. In International Conference on Learning Representations, 2018.
Gabriel Barth-Maron, Matthew W. Hoffman, David Budden, Will Dabney, Dan Horgan, Dhruva TB, Alistair Muldal, Nicolas Heess, and Timothy P. Lillicrap. Distributed distributional deterministic policy gradients. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.nen net, 2018. URL /tt/forrummdd-SSy1pp000
Burton H Bloom. Space/time trade-offs in hash coding with allowable errors. 13(7):422 426, 1970.
Communications of the ACM,
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference on Learning Representations, 2018.
Souradip Chakraborty, Amrit Singh Bedi, Kasun Weerakoon, Prithvi Poddar, Alec Koppel, Pratap Tokekar, and Dinesh Manocha. Dealing with sparse rewards in continuous control robotics via heavy-tailed policy optimization. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pp. 989 -995995.
IEEE, 2023.
Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry- fourth anmual ACM symposium on Theory of computing, pp. 380-388, 2002.
Cédric Colas, Olivier Sigaud, and Pierre-Yves Oudeyer. GEP-PG: Decoupling exploration and exploitation in deep reinforcement learning algorithms. In International Conference on Machine Learning, pp. 1039 1048. PMLR, 2018
Will Dabney, Georg Ostrovski, and Andre Barreto. Temporally-extendel e-greedy exploration. In Interna- tional Conference on Learning Representations, 2020.
Murad Dawood, Nils Dengler, Jorge de Heuvel, and Maren Bennewitz. Handling sparse rewards in reinforce- ment learning using model predictive control. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pp. 879-885, 885. IEEE, 2023.
Rati Devidze, Parameswaran Kamalaruban, and Adish Singla. Informativeness of reward functions in re- inforcement learning. In 23nd International Conference Autonomous Agents and Multiagent Systems, pp. 444-452. ACM, 2024.
Shoclabhadra Dey, James Ault, and Guni Sharon. Continual optimistic initialization for valuo-based re- inforcement learning. In Proceedings of the 23rd International Conference on Autonomous Agents and Mullingent Systems, pp. 453 462, 2024.
14

---

Published in Transactions on Machine Learning Research (05/2025)
Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford, John Schulman, Szymon Sidor, Yuhuai Wu, and Peter Zhokhov. OpenAT baselines. https://github..co openai/baselines/ 2017.
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International conference machine leorning, pp. 1338. PMLR, 2016.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clunc. First return, then explore. Nalure, 590(7847):5500 586, 2021.
Eyal Even-Dar and Yishay Mansour. Learning rales for q-learning, J. Mach. Learn. Res., 5:1 25, December 2004. ISSN 1532-4435.
Ben Eysenbach, Russ R Salakhutdinov, and Sergey Levine Search on the replay buffer: Bridging planning and reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In International Conference Machine Learning, pp. 1587-1596. PMLR, 2018.
Tuomas Haarnoja, Aurick Zhou, Picter Abbeol, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Conference on Machine Learning, pp. 1861-1870. PMLR, 2018
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Yujing Hu, Weixun Wang, Hangtian Jia, Yixiang Wang, Yingfeng Chen, Jianye Hao, Feng Wu, and Changjie Fan. Learning to utilize shaping rewards: A new approach of reward shaping. Advances in Neural Information Processing Systems, 03:15931-159444 2020.
Sham M. Kakade. On the sample complexity of reinforcement learning. 2003. URL https://api
semanticscholar, Semaatttecccollarr.oo///oogooppa crrpa/rrrrrorpppo0D022633333333
Yuji Kanagawa. mujoco-maze.
2021.
B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey, IEEE Transactions on Intelligent Transportation Systems, 23(6):4909-4922) 4926, 2021.
Varun Raj Kompella, Thomas Walsh, Samuel Barrett, Peter R. Wurman, and Peter Stone. Event tables for efficient experience replay. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL
Adam Daniel Laud. Theory and application of reward shaping in reinforcement learning. University of Illinois at Urbana- Urbana-Champaige Champaign, 2004.
Steven LaValle, Rapidly random trees: new tool for path planning. Research Report 9811, 1998.
Joel Lehman, Jay Chen, Jell Clune, and Kenneth O Stanley. ES is more than just traditional finite-difference approximator. In Proceedings of the genetic and evolutionary computation conference, pp. 450-457, 2018.
Timothy Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint AXXi:1509.0297/1 2015.
Bo Liu, Yihao Feng, Qiang Liu, and Peter Stone. Metric residual network for sample efficient goal-conditioned reinforeement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 8799 8806, 2023.
15

---

Published in Transactions on Machine Learning Research (05/2025)
Hao Liu, Alexander Trott, Richard Socher, and Caiming Xiong. Competitive experience replay. In Interna- tional Conference on Learning Representalions, 2018.
Yao Liu and Emma Brunskill. When simple exploration is sample efficient: Identifying sufficient conditions for random exploration to yield PAC RL algorithms. CoRR, (bss/1805.0004 2018.
Sam Lobel, Omer Gottesman, Cameron Allen, Akhil Bagaria, and George Konidaris. Optimistic initialization for exploration in continuous control. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
volume 36, pp.
Sam Lobel, Akhil Bagaria, and George Konidaris. Flipping coins to estimate pseudocounts for exploration in reinforcement. learning. In International Conference Machine Learning, pp. 22594-22613 PMT.R, 2023.
Kevin Sebastian Luck, Mel Vocerik, Simon Stepputtis, Heni Ben Amor, and Jonathan Scholz. Improved ex-
ploration through latent trajectory optimization deep deterministic policy gradient. In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3704 37113 IEEE, 2019.
Guillaume Matheron, Nicolas Perrin, and Olivier Sigaud. The problem with DDPG: understanding failures in deterministic environments with sparse rewards. arXiv preprint arXiv:1911. 11679, 2019.
Farzan Memarian, Wonjoon Goo, Rudolf Lioutikov, Scott Niekum, and Ufuk Topeu. Self-supervised online reward shaping in sparse-reward reward environments. in 2021 ieee. In RSJ International Conference on Intelligent Robols and Systems (IROS), pp. 2369-2375.
Lingheng Meng, Rob Gorbet, and Dana Kulić. The effect of multi-step methods on overestimation in deep reinforcement learning. In 2020 25th International Conference on Pattern Recognition (ICPR), pp. 347- 353. IEEE, 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglon, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXie preprint arXiv:1312.5600 2013.
Volodymyr Mnih, Adria Puigdomenech Badia, Mchdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Inter- national Conference on Machine Learning, pp. 1928 1937. PMLR, 2016.
Georg Ostrovski, Marc G Bellemare, Aäron Oord, and Rémi Munos. Count-based exploration with neural density models. In International Conference on Machine Learning, pp. 2721 2730. PMLR, 2017.
Ling Pan, Qingpeng Cai, and Longbo Huang. Softmax deep double deterministic policy gradients. Advances in neural information processing systems, 33:11767 -1777, 2020.
Yangchen Pan, Jincheng Mei, Amir-massoud Farahmand, Martha White, Hengshuai Yao, Mohsen Rohani, and Jun Luo. Understanding and mitigating the limitations of prioritized experience replay. In Uncertainty in Artificial Intelligence, pp. 1561- 1571. PMLR, 2022.
George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshmi- narayanan. Normalizing flows for probabilistic modeling and inference. The Journal of Machine Learning Research,
2021.
Deepak Pathak, Pulkit Agrawal, Alexei Efros, and Trevor Darrell. Curiosity-driven exploration by self- supervised prediction. In International Conference on Machine Learning, pp. 2778-277777 7778-7777 PMLR, 2017.
Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Y Chen, Xi Chen, Tamin Asfour, Pieter Abbeel, and Marcin Andrychowicz. Parameter space noise for exploration. In International Conference on Learning Representations, 2018.
Lukas Schäfer, Filippos Christianos, Josiah P Hanna, and Stefano V Albrecht. Decoupled reinforcement learning to stabilise intrinsically-motivaie exploration. arXiv preprint ar 3rXi:22107.08966 2021.
16

---

Published in Transactions on Machine Learning Research (05/2025)
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv:1511.05055 2015.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Determin- istic policy gradient algorithms. In International Conference Machine Learning, pp- 387-395. PML.R, 2014.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, Doina Precup, and Satinder Singh. Between MDPs and semi-MDPs: framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181-211 1999.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAT Xi Chen, Yan Duan, John Schulman, Filip DeTurek, and Picter Abbeel. # exploration: A study of count-based exploration for deep reinforcement learning. Advances in neural information processing systems, 30, 2017.
Sebastian Thrun and Anton Schwartz. Issues in using function approximation for reinforcement learning. In Proceedings of the Fourth Connectionist Models Summer School, volume 255, pp. 263. Hillsdale, NJ, 1993.
Daniil Tiapkin, Nikita Morozov, Alexey Naumov, and Dmitry P Vetrov. Generative flow networks as entropy- regularized rl. In International Conference Artificial Intelligence and Stalistics, pp. 4213 -221. PML.R, 2024.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026 5033. IEEE, 2012.
Alexander Trott, Stephan Zheng, Caiming Xiong, and Richard Socher, Keeping your distance: Solving sparse reward tasks using self-balancing shaped rewards. Advances in Neural Information Processing Systems, 32, 2019.
George E Uhlenbeck and Leonard S Ornstein. On the theory of the Brownian motion. Physical review, 36 (5): 1930.
Jelfrey S Vitter. Random sampling with reservoir. ACM Transactions Mathemalical Soflware (TOMS), 11(1):37-51) 57, 1985.
Guangming Wang, Minjian Xin, Wenhua Wu, Zhe Liu, and Hesheng Wang. Learning of long-horizon sparse- reward robotic manipulator tasks with base controllers. IEEE Transactions Newral Networks and Learning Systems, 35(3))4072-4081, 2022.
Tongzhou Wang, Antonio Torralba, Phillip Isola, and Amy Zhang. Optimal goal-reaching reinforcement learning via quasimetric learning. In International Conference on Machine Learning, pp. 36411-36430.
PMLR, 2023.
Albert Wilcox, Ashwin Balakrishna, Jules Dedieu, Wyame Benslimane, Daniel Brown, and Ken Goldberg. Monte carlo augmented actor-critic for sparse reward deep reinforcement learning from suboptimal demon- strations. Advances in neural information processing systems, 35:2254 2267, 2022.
Tianhe Yu, Deirdre Quillen, Zhanpeng He, Ryan Julian, Karol Hausman, Chelsca Finn, and Sergey Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning. In Conference on Robot Learning, pp. 1094-1100 PMLR, 2020.
Hongming Zhang, Chenjun Xiao, Han Wang, Jun Jin, Martin Müller, et al. Replay memory as an empirical mdp: Combining conservative estimation with experience replay. In The Eleventh International Conference on Learning Representations, 2022.
Linjing Zhang, Zongzhang Zhang, Zhiyuan Pan, Yingfeng Chen, Jiangeheng Zhu, Zhaorong Wang, Meng Wang, and Changjic Fan. A framework of dual replay buffer: balancing forgetting and generalization in reinforcement learning. In Proceedings of the 2nd Workshop on Scaling Up Reinforcement Learning (SURL), International Joint Conference on Artificial Intelligence (IJCAT), 2019.
17

---

Published in Transactions on Machine Learning Research (05/2025)
Shangtong Zhang and Richard S Sutton. A deeper look at experience replay. arXiv: 111200175, 2017.
arXiv preprint
18

---

Published in Transactions on Machine Learning Research (05/2025)
A Appendix
A.1 el-greedy Sample Efficiency Proofs
In this section, we first provide an overview of the proof, presenting the key ideas at high level. Then, we present the detailed formal proof of Theorem and Theorem 2
Proof Overview. We aim to show that the el-greedy algorithı falls into the PAC-MDP category. Accord- ing to Liu & Brunskill (2018), an algorithm A is PAC-MDP if the covering time induced by A is polynomially bounded. In Liu & Brunskill 2018), the authors further demonstrate that bounding the covering time re- quires bounding both the Laplacian eigenvalues and the stationary distribution over the states induced by the random walk policy. This presented as Proposition A.1 According Theorem 2 two conditions are satisfied: N (([S]AA)) and a lower bound on the probability of the sampled option, Px 2 T[[S|]ATT These two conditions are necessary and are met by our problem setting and the exploration algorithm (Algorithm D. To prove that Px 2 क[ we construct a worst-case tree structure X, where we aim to identify the option induced by the tree 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
We now proceed with the proof of Theorem demonstrated below.
Theorem (Worst-Case Sampling). Given a tree X with N nodes (s1 to SN); for any w E Ωx the sampling probability satisfies:
Px(w] 2 NI(max (o(s:))) ((A))AA))
(7)
|og(|S||A|)
where N S log (()(())
Here, S and 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 tree X, we define X; (for S i N) the tree constructed up to the i-th time step. At each step N,, we track the tuple of added states, denoted by S; the uniformly sampled state 8, from S and the state with the fewest visits, Smin- The notation 8r and Smin follows Algorithm [ Without loss of generality, we assume that each next state 8y' in line 9 of Algorithm [ satisfies n(((s=)) o 0. Specifically, we consider a worst-case tree X' fully populated with states from 81 to 8N. Therefore, at time step N, S (s1, :NN,, and we have the following relation:
n(o(s))) 2 m(((s2)) 2 n(((s))) n(d(sN)).
(8)
Equation provides a decreasing sequence of visitations for newly added nodes in tree X', emphasizing line Algorithm [ which causes the state Smin to change over N iterations. We assume a specific structure for each dss;), where for all E [N], at cach bucket ((s;), there exists only one state denoted by 8141, such that n()(s:-1)) < n(((s:)). Additionally, we assume that at each time step in X, the newly added node connects only to the most recently added node in the tree. The two key stochastic events are summarized as follows:
Es: The event in which nodes are sampled in Line 24 from buckets satisfying the increasing sequence above.
E2: The event in which nodes are selected in Line
We now define the probability of interest, which we aim to bound:
Ploption returned from Stoot to sN and Ez).
(9)
19

---

Published in Transactions on Machine Learning Research (05/2025)
We expand this probability follows:
N (( 8 added to tree 2) A (8: Smin) n (8x 81-1 in Line 8)]
P Ploption returned from Sroot to SN | & and &g]
II
1=2
(i 1)(((8i-1)
1=2
1
(N 1)! x
(0(s))l((s2) lo(x))
1
N!
[maxie[N] (0(s:)))N-1
To prove the final inequality, note that N and N is sub-logarithmic in [S||A], ie., log(max:etN) (d(s))) as constant co-
Tog log( (PS((())AA))) Since the size of the sets S and A large
log( (| LAI)
(og((S||AA) we can say I loR([S]|Al) lng(N)
Let us denote
Now by the series of following inequalities prove that N! X (maxie(N] [ [S|||]]
N < log([S|[AA)
log(N) = N (V) < log([S][LA))
(10)
N log(N) + (N 1)co - N S log(1S(1411
(since |S|| > N,co)
(11)
= log(N!) + (N - 1)co - log([S) ||A))
(Based on the Moivre Moivre-Stirling approximation)
(12)
+ log(N + (N - -10c0 S log((S|(AA)
(13)
+ log((V)) + log
(max ( :E(N)
S log([S]|AA)
(14)
log
N! (max (6(s:))) [E[N]
< log([S((14g
(15)
1
(16)
N!. (max,e[N]
[0(5:)))N-I
S
Now we provide the main proof which demonstrates polynomial sample complexity under certain criteria.
Theorem 2 (et-greedy Sample Efficiency). Given state space S, action space A, and set of op- tions 2x generated by ct-greedy for each tree X, Px|w] Z भाा(ाc|ा. ct-greedy achieves polynomial sample complesity or i.e. is PAC-MDP.
Proof. First note that if Px|w] 2 भाशা then based on Theorem 1 we need to have N < (og((S||A)
(8 and this implies that N < (()))AA) Based on the paper by (Liu & Brunskill 2018), and the analysis of the covering length when following a random policy, have the following preposition:
Preposition A.1 Liu & Brunskill (2018)). For any irreducable MDP M, we define Prnw as a transition matriz induced by random walk policy TRw over M and L(Panw denoted as the Laplacian of this transition matria. Suppose
the smallest non-zero eigenvalue of L and (s) is the stationary distribution over states which is induced by random walk policy, then Q-learning with random walk exploration is PAC RL algoritlm if: X min, V(8) are Pl).
20

---

Published in Transactions on Machine Learning Research (05/2025)
Note that Preposition A.1 is not limited to MDP with primitive actions. Therefore, can broaden its scope by incorporating options into this proposition and demonstrate that both x and min, V(s) can be polynomially bounded in terms of MDP parameters in this case, states and actions in approach.
Let's begin by examining the upper-bound for V(s Suppose we are at exploration tree X. Without loss of generality, we consider that capacity of tree X is full, and have N states. In this tree, lct's designate Groot the stale assigned the rool of the tree during the exploration phase. Now, consider another random state (excluding Sroot) within this tree structure, denoted as Srand- We acknowledge that, when considering the entire state space, there can be multiple options constructed from rooo to Brand- Each tree X provides one of these options. (s) is defined over all states, and w is the option with a limited size because of the constrained tree budget.
we can calculate the upper-bound for min, V(s) as follows:
(Srand)
Σ
Px(w (Sroot) = (srandd) 2 (sroot)
WEEx
(17)
1
((S|[A)
V (8rand)
P(w] (Sroot)
ND (Srand)
V (8root)
Since Srand 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:
((S[[A))
((S)[AA) (Sroo)
L (Sroot) min, (s) S
(18)
L (Srond)
So, min, v(jj is polynomially bounded. Now, we need to demonstrate that 1 is also polynomially bounded. To bound X, we first need to recall the definition of the Cheeger constant, h. Drawing from graph theory, if we denote V(G) and ((G) as the set of vertices and edges of an undirected graph G, respectively, and considering the subset vertices denoted by Va, we can define vV, as follows:
vV. == ((11 E E(G): n1 E Vo, E V(G) \ V.)
(19)
So, VV2, can be regarded collection of all edges going from V, to the vertex set outside of V,, In the define Cheeger constant:
above definition, (n1, n2) is considered graph edge. Now,
loV.
M(G) min
V. S [V(G), V. < VGG V.
(20)
We are aware that h 2 x x2 and by polynomially bounding h, we can ensure that À is also boundod. In related work (Liu & Brunskill 2018), an alternative variation of the Cheeger constant is utilized, which is based the flow F induced by the stationary distribution v of random walk the graph. Suppose for nodes ni, 12 and subset of nodes Ni in the graph, have:
F(n1, (e (nn))
(21)
F(oN)) Σ F(n1,12),
(22)
F(N1) = Σ V(n))
(23)
miN,
Building upon the aforementioned definition, the Cheeger constant. is defined
21

---

Published in Transactions on Machine Learning Research (05/2025)
F(aN1)
:: inf Ni (in(F(N))
(24)
Suppose Nrand {srooth; will now demonstrate that zo can be polynomially bounded
F(oN)) N1 min(F(N.,,
F(on))
E Exteroat 1 (s Parw (Sroot: s)
inf
min (Nrana); P ((Nrand))
(88oot)
Σ
1 PRAR (Brott 8) 2 Px(w] 5 (((S)A))
Stf-root
We demonstrate that both terms stated in Preposition are polynomially bounded, and thus, the proof is complete.
Algorithm Generating exploratory option with tree search using perfect model
function generate _ppiionssattee hash function 6, budget N)
2:
frontier nodes + 0
Initialize root using root +- Tree:odee(s)
4: frontier nodes +- frontier nodes U (root);
Smin root
6:
i
5-0
while i< N do
8:
8x ~ Unijorm.Randomffontee _nddesnoosssss_eee 8, next___ttaee state from env(s))
10:
if ((n(s=:))=0 then
Extract option o by actions rool to Sz return
12:
13:
end
14:
if n(((s.)) < n(d(Smin)) then
15:
8min=8g
16:
end if
17:
1-i+1
end while
19:
Extract option o by actions root to 8min
return
21:
end function
23: function next state from env frontier frontier_nodeee _ndee)
24: a (nnforra(endo((((s)))
25:
&- T(sr: a)
26: s..add child (82r)
hontier_nodes_eee 28: return Sz'
27: frontier nodes + frontier nodes U {sar)
end function
A.2 n-step Methods Comparison
In this section, we compare two update rules for Q-values in DDPG: the longest n-step return and the average return over to 8 steps (avg8-step). The results are shown in Figure 9 Both methods performed similarly overall; however, in the Wall-maze environment, the longest n-step return outperformed the avg8-stop ap- proach. The avg8-step method converged more quickly in U-maze and Point-push due to the stabilizing effect of averaging multiple updates.
22

---

Published in Transactions on Machine Learning Research (05/2025)
success rate
success rate
success rate
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.2
0.2
0.2
0.0
0.0
100
200
300
400
500
600
6
100
200
300
400
5do
600
100
200
300
400
500
6DD
checkpoints
checkpoints
checkpoints
(a) Wall-maze
(b) U-maze
(c) Point-push
DDPG GDRB
DDPG HER
Figure 8: The comparison between two replay buffer strategies:
GDRB and HER.
success rate
success rate
success rate
1.0
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.0
0.0
0.0
160
260
300
400
500
600
à
160
200
300
400
sóo
660
100
200
300
400
s0o
600
checkpoints
checkpoints
checkpoints
(a) Wall-maze
(b) U-maze
(c) Point-push
average of 1 to 8 steps (avg8-step)
longest n-step return
Figure 9: The comparison between two update rules for Q-values: the longest n-step return and the average return over 8 steps (avg8-step).
A.3 Comparison of GDRB and Hindsight Experience Replay (HER)
In this section, compare Figure shows the results in the navigation environments. In Wall-maze, HER achieves success rates above zero during the carly stages of training; however, it fails to maintain any success in later stages. This observation is consistent with the results reported by TTrott et al. (2019) in the same environment. In the other two environments, both methods exhibit comparable performance, but HER discovers paths to the goal more quickly, as leverages reward shaping in unsuccessful episodes to provide additional information about the structure of the environment.
strategies for storing transitions in the replay buffer: GDRB and HER.
A.4 Exploration with Perfect Model
Since the DDPG algorithm is model-free, we utilize the replay buffer lo construct the tree for el-greedy. However, et-greedy can also take advantage of a perfect model when available. The pseudocode for option generation using a perfoct model is provided Algorithm 2 The key difference from Algorithm [ is the use of the next next_state_feeeeeeeeettetteeeeee from_ent env function instead of next next_state_____ gexx__stateffoo_rrooee buffer generate child nodes. In this case, action is uniformly sampled from the action space, and the environment's transition
23

---

Published in Transactions on Machine Learning Research (05/2025)
function T is directly used to determine the next state (line 25). Figure 10 compares the performance of ETGL-DDPG in navigation environments using perfect model versus replay bulfer. The results show a clear advantage when using a perfect model, as the agent reaches success rate of more quickly and with less deviation.
BUCCOUAN Fate
SUCONES TOSM
Fuccuss rote
0.-
0.5
63-
150
210
(a) Wall-maze
(b) U-maze
Point-push
perfect model
replay buffer
Figure 10: Comparison of ETGL-DDPG performance in navigation environments using a perfect model vs.
replay buffer.
A.5 Implementation Details and Experimental Hyperparameters
Here, we describe the implementation details and hyperparameters for methods used in this paper. All experiments were run on system with 5 vCPU on cluster of Intel Xcon E5-2650 v4 2.2GHz CPUs and one 2080Ti GPU, Table displays utilized in ETGL-DDPG and the baselines.
dibledissllays the details for environments, Tables
and showcase the hyperparameters
Table 1: 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
opsilon decay rate
0.9999988
O. 0.9999992
exploration budget
20
40
60
SimHash dimension
k
9
16
soft target updates discount factor y warmup period exploration buffer size exploitation buffer size actor learning rate critic learning rate
10-2
0.99
10" steps
10"
10
10-4
10
24

---

Published in Transactions on Machine Learning Research (05/2025)
Table Environment details.
environment
S E
G
A E
Max steps per episode
Wall-maze
R²
0.95, 0.95]²
100
U-maze
R6
R²
-1. *
0.25, 0.25
500
Point- push
RI
R²
[-1, 1
*
0.25, 0.25
500
window-open
12
R
-1,1]
500
soccer
R
R
1, 1]
500
button-press
1230
I33
1,
500
Table 3: 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
10a
actor learning rate
10
critic learning rate
10
discount factor ? action scaling
0.99
0.01
environment scaling
0.1 for each dimension polynomial
knownness mapping lype
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
updale frequency per step action noise
12
2
0.2))
N(0, (0.3, 0.05))
N(0, (0.15))
warmup period
2 10 steps
replay buffer size learning rate soft target updates 7 discount factor ?
10"
3 10-1
5 x 10-3
0.99
A.6 ETGL-DDPG Algorithm
In this section, we introduce ETGL-DDPG, as detailed in Algorithm which is organized into three primary functions:
train, run sun_epssde, and update. The train function is called once at the start of the training process. For each training episode, the run_ _en_eeddddee 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.7 Analyzing the Impact of N on ct-greedy and ez-greedy Exploration
The budget N upper bounds the option length of et-greedy due to the fact that the longest path between nodes in the tree is shorter equal to the number of nodes in the tree. This is analogous to the
25

---

Published in Transactions on Machine Learning Research (05/2025)
Table 5: Analysis of the impact of budget N on the environment coverage.
ez-greedy
et-greedy
budget N
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.40
0.94
0.48
25
0.28
0.86
0.40
0.95
0.47
30
0.27
0.83
0.39
0.97
0.51
35
0.25
0.82
0.40
0.95
0.53
40
0.24
0.82
0.40
0.97
0.55
45
0.22
0.85
0.41
0.96
0.64
50
0.22
0.79
0.40
0.97
0.73
role of N in e2-groedy, where uniform distribution z(n) IngN/N is used. To evaluate both methods, assess environment coverage under varying budget sizes, calculating the coverage after million training frames. Table 5 shows the results: el-greedy consistently achieves greater coverage than ez-greedy across all environments and budget sizes. Additionally, et-greedy demonstrates improved coverage as the budget increases. contrast, increasing the budget for e2-greody docs not consistently improve coverage and can even decrease it some cases. This highlights the advantages of directed exploration over undirected methods, particularly complex environments with numerous obstacles, such as Wall-maze.
A.8 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 the episodes. To make more visually appcaling and casy to interpret, we only sample some of the episodes. The results for Wall-maze, U-maze, and Point-pust can be found in Figures II 12 and 13 respectively. Tn Wall-maze, only et-greedy and DOTE 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 mothods can explore the majority of the environment. However, during the final stages training, methods such as DDPG, SAC, and DDPG + intrinsic motivation have lower success rates and may end up locations other than the goal areas. In Point-push, et-greedy, ez-greedy, and DOIE first visit the lower section of the environment in the carly 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. To further illustrate how the policy evolves during training and how closely it approximates the optimal policy, we present the agent's trajectories across episodes, For clarity, we sample a fow representative episodes from different stages of training. Figure 14 presents the results for U-maze and Point-push. In both environments, the agent initially becomes trapped in suboptimal regions. As training progresses, the policy gradually improves, and by the end, the agent consistently follows a trajectory that closely approximates the shortest path to the goal.
26

---

Published in Transactions on Machine Learning Research (05/2025)
Algorithm 3 ETGL-DDPG
Randomly initialize critic network Q(s, a. g|0Q) and actor a(s.g100 with weights d2 and A" Initialize target networks Q' and p' with weights 09' + 09, Ou AH Initialize replay buffers Da. Des hash function o, exploration budget N
function train(Q, 6)
for cpisodes=1,M do
Receive initial observation state $1 and goal g run rin__pisode(ss, g)
update(success)
end for end function
function run episode(s, g)
success t false, I +
while 2 T and not(success) do
if (==0 then if random()<< then
Exploratory option + _oteratt__ootions.. 6, N)
Assign action t w
/ + lengh((()
else
Greedy action : at + u(st.
end if
else
Assign action a 1-1-1 end if
Execute action ag and observe reward rs and next state 8t11 if goal(>;41) then
success t true
end if end while end function
function update(success)
F' success 0.W
success
bootstrap
0.W
for (t 1,..r do
R +- r-r; r- if success then
store transition (st, g, ass R, bootstrap) in D3, De
clse
store transition (si, g, ais R, 8t, boolstrap) Dg
end if end for
Sample C random mini-batches of k transitions (s), Ij. aj. 8141, bootstrop;) by To and To ratios from D3 and D.
(sj+1, set yj = Tj + bootstrap, *"Q Bjr p² pl(s ($j41 +1, 11,,,, 10' )09¹)
update critic by minimizing the loss: L 2/4 Σ, (3/ Q(5) 9j a)(9)
update the actor: V E vaQ(s, g, a 0 ) )==e,,
a (1 g(0
update the target networks: 0º 70 + (1 7000 0 70 + 0F end function
27

---

Published in Transactions on Machine Learning Research (05/2025)
10
10
8000
8000
6000
4000
2000
(a) DDPG + et- et-greedy
(b) DOIE
10
10
8000
8000
4000
(c) DDPG + ea-greedy
(d) SAC
10
10
8000
8000
4000
(e) DDPG + intrinsic motivation
(f) TD3
10
8000
6000
4000
(g) DDPG
Figure 11: The agent's location at the end of episodes throughout the training in Wall-maze.
28

---

Published in Transactions on Machine Learning Research (05/2025)
500
500
300
500
100
100
(a) DDPG + et et-greedy
(b) DOIE
500
500
300
300
100
300
(c) DDPG + ez-greedy
(d) SAC
S 
500
500
400
300
300
100
100
(e) DDPG + intrinsic motivation
(f) TD3
500
300
100
(g)
DDPG
Figure 12: The agent's location at the end of episodes throughout the training in U-maze.
29

---

Published in Transactions on Machine Learning Research (05/2025)
2000
1520
1500
1900
1000
(a) DDPG + et- et-greedy
(b) DOIE
2000
1500
1500
1000
1000
(c) DDPG + ez-greedy
(d) SAC
2000
2000
1520
1500
1000
(e) DDPG + intrinsic motivation
(f) TD3
2000
1590
1000
500
(g)
DDPG
Figure 13: The agent's 's location at the end of episodes throughout the training in Point-push.
30

---

Published in Transactions on Machine Learning Research (05/2025)
50
20
10
2
(a) U-maze
(b) Point-push
Figure 14: The agent's policy during training, illustrated by the paths taken in each episode. Episodes are sampled from different stages of training to show how the policy evolves over time.
31


Reviews:
[{"review_id": "Ln6IOW3CsS", "reviewer": "Reviewer_ST7N", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": ">Strength\n1. the $\\epsilon t$ greedy exploration implements a tree search procedure which looks novel\n2. the sample complexity analysis is promising\n\n>Weakness\n1.  Both tree search and dual buffer mechanism will increase the overall computation cost. The computation cost has not been addressed in this paper. Can Auther compare the wall-clock training time?\n2. The paper utilizes a hash function to group numerically similar states into the same bucket. However, in continuous control tasks, states that appear numerically close can still demand different optimal controls. For example, in a cartpole scenario, once the pole is near upright, even a slight tilt to the left versus the right can require entirely different control strategies despite the underlying state values being very similar.\n3. For longest n-step return, for longer n, it will reduce the estimation error. However, it will also introduce a huge variance as n increases. How this will affect the stability and robustness of the method?\n4. Auther claim SOTA performance and D4PG [1] is another famous DRL algorithm which improves DDPG to SOTA. Can auther compare them?\n5. Can Auther also provide some figures that compare the quality of the policy? For example, plot steps from initial state to reach terminal state\n\n[1] Barth-Maron, Gabriel, et al. \"Distributed distributional deterministic policy gradients.\" arXiv preprint arXiv:1804.08617 (2018).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduce ETGL-DDPG method which enhance the DDPG algorithm by three key component (1 $\\epsilon t$ greedy exploration that enhance the exploration by implement a tree search procedure 2. GDRB replay buffer use two buffer to ensuring informative goal-reaching transitions are used in training 3. Longest n-step Return to reduce estimation error.) The ETGL-DDPG outperform SOTA method across selected environments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Auther lack some of the related work comparision:\nFor count based exploration idea: I found auther did cite [1] but does not discuss about it. [1] does have similar idea as this paper which both used Count-based exploration through static hashing,using SimHash and they use it as reward shaping.\n\nFor n step method: [2] also uses n step method with very long n. [3] use very long reward trejectory and average the reward.\n\n[1] Tang, Haoran, et al. \"# exploration: A study of count-based exploration for deep reinforcement learning.\" Advances in neural information processing systems 30 (2017).\n\n[2] Zhong, Junmin, Ruofan Wu, and Jennie Si. \"A Long $ N $-step Surrogate Stage Reward for Deep Reinforcement Learning.\" Advances in Neural Information Processing Systems 36 (2023): 12733-12745.\n\n[3] Naik, A., Wan, Y., Tomar, M., & Sutton, R. S. (2024). Reward centering. arXiv preprint arXiv:2405.09999.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NKouOMA2D5", "reviewer": "Reviewer_FeXX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper is well organized and most parts of the method are easy to follow.\n2. The proposed $\\epsilon t$-greedy is interesting and works very well on sparse reward environments.\n3. The overall performance of ETGL-DDPG looks good, outperforming other stochastic approaches.\n\nWeaknesses:\n1. If the authors want to address sparse reward environments, why don't you add proposed strategies to stochastic algorithms like SAC (which should make more sense)?\n2. In this work, actions are taken by considering both the current state and the goal state. But what if the goal state is unknown? In particular, what if the environment is partially observable?\n3. I'm wondering if n-step return would increase the training and inference time. Can the authors provide a time comparison between standard 1-step and the proposed n-step return?\n4. As an important baseline, the DDPG should also be added to Figure 3.\n5. In the left of Figure 6, it would be great to add the other two results (i.e., GBRB + n-step return and DDPG).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work presents a novel framework for continuous action environments with sparse rewards. The key contributions are an $\\epsilon t$-greedy algorithm for more directional exploration, a goal-conditioned dual replay buffer for adaptive sampling, and a longest n-step return for better policy learning. The authors evaluate their method on several sparse reward environments. The results show that the proposed ETGL-DDPG achieves the best performance compared to other approaches. Moreover, additional experiments are conducted to illustrate the proposed three contributions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please add the experiments according to \"Weaknesses\". Moreover, it would be great if the author could tune the figures (font sizes and resolutions) to make them easier to read.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "AyZhEvEuFg", "reviewer": "Reviewer_mVRz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. The tree-search-based method for generating multi-step options ($\\epsilon t$-greedy) is a noteworthy contribution. It provides directional exploration, moving beyond standard random noise or single-step $\\epsilon$-greedy. Moreover, the paper includes a theoretical discussion on the polynomial sample complexity of the $\\epsilon t$-greedy exploration method.\n\n2. The proposed method shows consistent gains over some commonly used baselines (DDPG, TD3, SAC) in multiple sparse-reward tasks.\n\n**Weakness**\n\n1. While the exploration component is novel, the dual replay buffer design and longest $n$-step return enhancement are incremental extensions of well-established ideas in reinforcement learning. The paper might benefit from a clearer framing of how these standard techniques are adapted or combined distinctively.\n\n2. The experimental baselines do not include some more recent approaches that specifically address sparse rewards and long-horizon control (Please see the detailed list in the \"Requested Changes\" section). Including these or discussing why they are less suitable as baselines would make the evaluation more comprehensive and convincing.\n\n3. The paper suggests a small-scale search tree during exploration. However, the additional overhead--especially for higher-dimensional tasks--could be further elaborated. There is also limited discussion on how well the tree-search approach scales or how one would tune the budget $𝑁$ in more complex environments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper tackles the well-known challenge of sparse rewards in continuous control tasks by proposing ETGL-DDPG, which extends DDPG with three enhancements: (1) a tree-search-based exploration mechanism ($\\epsilon t$-greedy) that constructs temporally extended exploration options, (2) a dual replay buffer framework to prioritize successful episodes, and (3) a longest $n$-step return to speed up reward propagation. The main novelty lies in the first enhancement, where a small-scale search tree approximates transitions via a hash-based similarity to promote better coverage of the state space. The authors present theoretical results showing polynomial sample complexity for the proposed exploration strategy and validate their approach on multiple continuous control tasks with sparse rewards.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please compare with or cite recent methods that also deal with sparse rewards in continuous control. A direct empirical comparison or at least a discussion of how ETGL-DDPG differs from these would strengthen the paper’s relevance and soundness. The list of recent works is as follows:\n\n$~~~~~~$ (1). Chakraborty, Souradip, et al. \"Dealing with sparse rewards in continuous control robotics via heavy-tailed policy optimization.\" 2023 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2023.\n\n$~~~~~~$ (2). He, Xiangkun, and Chen Lv. \"Robotic control in adversarial and sparse reward environments: A robust goal-conditioned reinforcement learning approach.\" IEEE Transactions on Artificial Intelligence 5.1 (2023): 244-253.\n\n$~~~~~~$ (3). Wang, Guangming, et al. \"Learning of long-horizon sparse-reward robotic manipulator tasks with base controllers.\" IEEE Transactions on Neural Networks and Learning Systems 35.3 (2022): 4072-4081.\n\n$~~~~~~$ (4). Dawood, Murad, et al. \"Handling sparse rewards in reinforcement learning using model predictive control.\" 2023 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2023.\n\n$~~~~~~$ (5). Wilcox, Albert, et al. \"Monte carlo augmented actor-critic for sparse reward deep reinforcement learning from suboptimal demonstrations.\" Advances in neural information processing systems 35 (2022): 2254-2267.\n\n2. The authors may provide more details on how the budget for tree search ($N$) is chosen or tuned and offer insights on the computational cost. If possible, include an ablation or analysis on higher-dimensional tasks to illustrate how the method scales.", "broader_impact_concerns": "No ethical concerns for this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is a very good fit for TMLR: an interesting, incremental advance that is of interest to at least some people in the TMLR community.

I am requesting the following changes in the minor revision.

1. The experimental section should be updated to use performance profiles (https://github.com/google-research/rliable). This is an empirical paper and performance profiles are the gold standard for evaluating empirical papers.
2. You should evaluate (at least on one small toy environment) all $2^3$ possibilities of combining your 3 innovations (n step returns, new experience replay and et-greedy exploration) so that each combination of switching each of the 3 components on or off is evaluated. This will better illuminate better how they work together.
3. You should make it clear that your theory discusses the discrete case only and doesn't talk about the continuous MDP, only its discretisation. This means that your theory isn't useful for determining $k$ (where $2^k$ is the size of the discretised state space).
4. You should make it clear that the et-greedy exploration will only pursue less-visited states with visit counts >= 1, not >=0. This is because a state has to be in the replay buffer before it is considered by the exploration policy.

If you make these changes, I am OK with accepting the paper. If you think that my requests above are unfair or that I misunsderstood your claims, please let me know and I will reconsider.
Decision: Accept (poster)