Adaptable Hindsight Experience Replay for Search-Based Learning

Alexandros Vazaios, Jannis Brugger, Cedric Derstroff, Kristian Kersting, Mira MeziniarXiv 2025 · DOI · arXiv

Introduction

Reinforcement Learning (RL) algorithms like AlphaZero have demonstrated remarkable success in complex games, yet they often struggle in environments with sparse rewards. In such domains, an agent may perform hundreds of actions without receiving any feedback until a task is either perfectly completed or failed. This lack of high-quality data during early training stages often leads to stagnation, as the neural network has virtually no successful examples to learn from.

While Hindsight Experience Replay (HER) was introduced to mitigate this by relabeling failed states as intended goals, its application to search-based learning has remained rigid. Standard HER typically focuses on the final path taken, overlooking the rich data generated during Monte Carlo Tree Search (MCTS). This paper introduces Adaptable Hindsight Experience Replay (AHER), a flexible framework designed to integrate HER into AlphaZero-style systems by leveraging the full breadth of the search process.

The AHER Framework

AHER wraps around the standard AlphaZero training loop, offering a customizable suite of parameters to optimize learning from failed trajectories. Unlike traditional HER, AHER can extract hindsight samples not just from the executed path, but from the entire MCTS search tree—a "multi-trajectory" approach that significantly increases data efficiency.

The AHER architecture integrates with the AlphaZero loop, allowing for hindsight sampling from both episode trajectories and the broader search tree.

The framework provides four primary "knobs" for customization:

  1. Goal Selection Strategy: Choosing between "future" (relabeling states visited later) or "final" (relabeling only terminal states) strategies.
  2. Trajectory Selection: Sampling from the played path versus a subset of the entire MCTS search tree.
  3. Sample Density: Controlling the volume of HER samples added to the replay buffer per trajectory.
  4. Policy Learning Targets: Defining what the network should predict for artificial samples, such as "one-hot" targets for successful actions versus original MCTS probabilities.

Experimental Results

The authors evaluated AHER across three distinct environments: Bit-Flipping, Point Maze (physics-based navigation), and Equation Discovery (symbolic regression).

Performance of AHER across Equation Discovery, Bit-flipping, and Point Maze environments compared to AlphaZero and Supervised Learning (SL) baselines.

The results demonstrate that AHER-augmented AlphaZero consistently outperforms standard RL and supervised learning baselines. In Equation Discovery, AHER significantly reduced the number of states visited before finding a perfect match. In Bit-Flipping and Point Maze, specific configurations (e.g., using 4 to 8 "future" goals) enabled the agent to reach high success rates where the baseline AlphaZero failed entirely.

A key insight from these experiments is that the "search tree is a goldmine." Sampling goals from the tree is particularly powerful in structured tasks like equation discovery. However, the optimal configuration is task-dependent; for instance, "future" goal strategies are ideal for navigation but inapplicable to symbolic tasks where only terminal states represent valid equations.

Conclusion and Future Work

AHER provides a robust, modular framework for enhancing search-based learning in sparse-reward environments. By allowing researchers to tune how hindsight data is generated and utilized, it bridges the gap between exploration and exploitation in complex domains. While currently limited to discrete actions and deterministic environments, future work will focus on extending AHER to continuous action spaces and investigating its performance in noisy, probabilistic settings.

Summary updated

Abstract

AlphaZero-like Monte Carlo Tree Search systems, originally introduced for two-player games, dynamically balance exploration and exploitation using neural network guidance. This combination makes them also suitable for classical search problems. However, the original method of training the network with simulation results is limited in sparse reward settings, especially in the early stages, where the network cannot yet give guidance. Hindsight Experience Replay (HER) addresses this issue by relabeling unsuccessful trajectories from the search tree as supervised learning signals. We introduce Adaptable HER (\ours{}), a flexible framework that integrates HER with AlphaZero, allowing easy adjustments to HER properties such as relabeled goals, policy targets, and trajectory selection. Our experiments, including equation discovery, show that the possibility of modifying HER is beneficial and surpasses the performance of pure supervised or reinforcement learning.
BibTeX
@misc{vazaios2025adaptable,
  author = {Alexandros Vazaios and Jannis Brugger and Cedric Derstroff and Kristian Kersting and Mira Mezini},
  title = {{Adaptable Hindsight Experience Replay for Search-Based Learning}},
  year = {2025},
  eprint = {2511.03405},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.03405},
}
Figure