HERDT: Hindsight Experience Replay with Evolutionary Decision Trees

HERDT Architecture & Two-Stage Framework

Constructing Grid Environment from Robotic Environment

Figure 1: The HERDT curriculum generation workflow. Left: Discretizing continuous 7-DOF Fetch manipulator tasks into a clean grid world representation preserving initial and target goal boundaries. Right: Grammatical Evolution (GE) optimizes binary Decision Trees in the grid world using Q-learning updates on leaf nodes, creating an interpretable navigational policy that outputs intermediate curriculum waypoints.

Abstract & Key Contributions

Reinforcement learning (RL) algorithms often require a significant number of experiences to learn a policy capable of achieving desired goals in multi-goal robot manipulation tasks with sparse rewards. Hindsight Experience Replay (HER) is an existing method that improves learning efficiency by using failed trajectories and replacing the original goals with hindsight goals that are uniformly sampled from the visited states. However, HER has a limitation: the hindsight goals are mostly near the initial state, which hinders solving tasks efficiently if the desired goals are far from the initial state.

To overcome this limitation, we introduce a curriculum learning method called HERDT (HER with Decision Trees). HERDT uses binary DTs to generate curriculum goals that guide a robotic agent progressively from an initial state toward a desired goal. During the warm-up stage, DTs are optimized using the Grammatical Evolution algorithm. In the training stage, curriculum goals are then sampled by DTs to help the agent navigate the environment. Since binary DTs generate discrete values, we fine-tune these curriculum points by incorporating a feedback value (i.e., the \(Q\)-value). This fine-tuning enables us to adjust the difficulty level of the generated curriculum points, ensuring that they are neither overly simplistic nor excessively challenging. We evaluate our proposed approach on different sparse reward robotic manipulation tasks and compare it with the state-of-the-art HER approach. Our results demonstrate that our method consistently outperforms or matches the existing approach in all the tested tasks.

Grammatical Evolution DTs

Evolves interpretable binary Decision Trees using Grammatical Evolution (GE) with Q-learning on leaf nodes within a discrete grid abstraction of the robot workspace.

\(Q\)-Value Feedback Tuning

Dynamically scales discrete DT curriculum waypoints using the continuous critic \(Q\)-value (\(\nu = \kappa \cdot |c - Q'|\)), ensuring appropriate task difficulty.

5x Faster Convergence

Accelerates policy training up to 5x over vanilla HER in complex long-horizon tasks like FetchPickAndPlace (75 epochs vs. 400 epochs to reach optimal success).

Grammar Rules & Continuous \(Q\)-Value Refinement

In the warm-up stage, Grammatical Evolution maps integer codon strings to binary Decision Trees following Backus-Naur grammar rules:

Rule	Production	Description
`dt`	`<if>`	Root condition of the decision tree
`if`	`if <condition> then <action> else <action>`	Binary branch splitting on spatial coordinates
`condition`	`input_var <comp_op> <const>`	Compares coordinate against discrete threshold
`comp_op`	`lt \| gt`	Less-than (`<`) or greater-than (`>`) comparison
`const`	`[0, 20) with step 1`	Integer bounds in discrete grid coordinate frame
`action`	`leaf \| <if>`	Terminal directional step or sub-tree condition

Discrete Actions to Continuous Waypoint Calibration

The DT policy outputs discrete directional steps \(a \in \{0, 1, 2, 3, 4, 5\}\) representing cardinal directions (\(\pm x, \pm y, \pm z\)). Direct addition would cause rigid jumps. To align curriculum points with the robot's evolving capabilities, HERDT refines the raw goal \(\kappa\) using the critic \(Q\)-value:

Q' = \begin{cases} -1 & \text{if } Q < -1 \\ 0 & \text{if } Q > 0 \\ Q & \text{otherwise} \end{cases} \qquad\Longrightarrow\qquad \nu = \kappa \cdot |c - Q'|

When the critic evaluates a high \(Q\)-value (state-action pair is well mastered), \(|c - Q'|\) enlarges the step size, advancing the curriculum farther toward the final goal. When \(Q\) is low, the step size shortens, keeping intermediate targets within reachable range.

Figure 2: Evolved Decision Tree for FetchPush (left) and step-by-step waypoint execution graph (right), demonstrating interpretable branching logic from initial configuration to target coordinate.

Benchmark Results on MuJoCo Manipulation Environments

We benchmarked HERDT against standard HER across 4 standard continuous control robotic manipulation tasks from OpenAI Gym / MuJoCo, tested across 10 random seeds.

FetchReach

Converged in 5 epochs (vs 6)

FetchPickAndPlace

5.3x Faster Convergence (75 vs 400 epochs)

FetchPush

1.8x Faster (35 vs 65 epochs)

FetchSlide

6x Faster Convergence (50 vs 300 epochs)

Figure 3: Test success rate across training epochs for the 4 manipulation benchmarks. Solid curves show mean performance and shaded regions show inter-quartile range across 10 independent runs.

Curriculum Goal Progression Visualizations

Visualization of curriculum waypoints generated throughout the training process for FetchPush. Colors ranging from red to light blue represent intermediate goals sampled across successive training episodes, guiding the object smoothly from the initial position to the target zone (gray).

FetchPush Overview: Global view of generated waypoints bridging the distance between start configuration and goal area.

FetchPush Detail View: High-resolution closeup of curriculum clustering along optimal pushing trajectories.

Evaluated 7-DOF Fetch Robot Manipulation Environments

FetchReach (3D Gripper Control)

FetchPush (2D Table Surface)

FetchPickAndPlace (3D Grasp & Move)

FetchSlide (Dynamic Object Impulse)

Ablation Studies: Feedback & Recursive Sampling

Impact of \(Q\)-Value Feedback Calibration

Comparing HERDT with vs. without continuous \(Q\)-value scaling. Without feedback, the discrete nature of DT steps leads to suboptimal waypoint step sizing and degraded policy learning.

FetchReach

FetchPickAndPlace

FetchPush

FetchSlide

Impact of Recursively Generated Goals (\(n\)-Step)

Evaluating multi-step recursive sampling \(g_{t+n} = \frac{1}{n}\sum_{i=1}^n g_i\) for \(n \in \{1, 2, 4, 8\}\):

FetchPush: Success rates under varying recursion horizons \(n\).

FetchPickAndPlace: Balancing intermediate goal step length against task complexity.

BibTeX Citation

@incollection{Sayar_2024_HERDT,
  title     = {Hindsight Experience Replay with Evolutionary Decision Trees for Curriculum Goal Generation},
  author    = {Sayar, Erdi and Vintaykin, Vladislav and Iacca, Giovanni and Knoll, Alois},
  booktitle = {Applications of Evolutionary Computation (EvoApplications 2024)},
  series    = {Lecture Notes in Computer Science},
  volume    = {14634},
  pages     = {3--18},
  year      = {2024},
  publisher = {Springer Nature Switzerland},
  doi       = {10.1007/978-3-031-56855-8_1},
  url       = {https://link.springer.com/chapter/10.1007/978-3-031-56855-8_1}
}