HAEPO: History-Aggregated Exploratory Policy Optimization

Gaurish Trivedi, Alakh Sharma, Kartikey Singh Bhandari, Dhruv Kumar, Pratik Narang, Jagat Sesh ChallaarXiv 2025 · DOI · arXiv

TL;DR

This paper introduces HAEPO, a novel reinforcement learning algorithm that improves exploration and stability in long-horizon tasks by aggregating entire trajectories into a single score. By leveraging listwise ranking principles and adding entropy and KL regularization, HAEPO achieves faster convergence and more robust learning compared to existing methods.

What Problem Does This Paper Address?

Reinforcement learning (RL) agents need to balance exploring new actions with exploiting known good ones to find optimal policies. However, traditional methods often struggle with long-horizon tasks where rewards are delayed or sparse. Per-step policy gradients can suffer from high variance and poor credit assignment, while existing trajectory-level methods might still limit exploration or lose fine-grained information. This paper addresses the challenge of achieving stable, efficient, and thorough exploration in RL, particularly for tasks with extended timelines and infrequent rewards.

Methods

HAEPO builds upon existing policy gradient methods by introducing a "history-aware" approach. The core idea is to compress each entire trajectory (a sequence of states, actions, and rewards) into a single cumulative log-likelihood score. This score is then used to weight trajectories using a Plackett-Luce softmax, effectively giving more importance to trajectories that are consistent with the current policy and have higher returns.

To ensure stability and prevent premature convergence, HAEPO incorporates two regularization terms:

  1. Entropy Bonus: Encourages broader exploration by adding an entropy term to the objective, preventing the policy from collapsing onto a few dominant trajectories.
  2. KL Penalty: Acts as a trust-region constraint, penalizing large deviations from a reference policy (typically the previous policy update) to maintain stability.

The paper also discusses reward normalization techniques (Sum-Normalization and Z-Score Normalization) to further improve stability and adapt to different task characteristics.

Datasets

The paper evaluates HAEPO on several standard RL benchmarks:

  • Multi-armed Bandit: Used to test exploration and convergence speed with varying numbers of arms.
  • Random Walk: A sparse, long-horizon environment to assess HAEPO's ability to handle delayed rewards.
  • CartPole (Gymnasium): A classic control task for evaluating learning speed and stability.
  • LLM TL;DR: A task involving summarizing Reddit posts, used to evaluate HAEPO's performance in fine-tuning large language models with human preferences.

Key Insights and Ideas

  • Trajectory-level credit assignment is crucial for long horizons: By collapsing an entire trajectory into a single score, HAEPO captures long-range dependencies that per-step methods miss, leading to better credit assignment.
  • Listwise ranking principles can enhance exploration: Applying Plackett-Luce weighting to trajectories, inspired by information retrieval, allows HAEPO to amplify diverse, high-return trajectories more effectively than simple aggregation.
  • Balancing exploration and stability is key: The combination of entropy regularization for exploration and KL penalty for stability is essential for robust performance, especially in challenging environments.
  • Reward normalization matters: The choice between Sum-Normalization and Z-Score Normalization significantly impacts performance depending on the task's reward structure and horizon. Z-score normalization is particularly beneficial for high-variance, sparse-reward tasks.

Key Results

  • Multi-armed Bandit: HAEPO showed increased exploration with more arms and gained stability as the number of arms increased, converging at a similar speed to PPO and DPO.
  • Random Walk: HAEPO achieved near-optimal returns faster than PPO and DPO, demonstrated improved stability with scale, and was more compute-efficient.
  • CartPole: HAEPO achieved comparable performance to PPO but with a smoother learning curve and more stable convergence, especially when regularization was applied.
  • LLM TL;DR: HAEPO achieved higher human preference ratings and more consistent alignment with human judgments compared to GRPO and DPO, while also training faster and with favorable GPU efficiency.

Limitations and Future Work

  • Hyper-parameter Sensitivity: HAEPO's performance can be sensitive to the settings of its regularization scalars (entropy and KL penalties). The authors suggest exploring automated tuning or adaptive schedules.
  • Extremely Long Horizons: While HAEPO was tested on horizons up to ~10^3 steps, real-world domains can be much longer. Future work could incorporate memory-efficient buffering or hierarchical decomposition.
  • Computational Overhead: The listwise softmax introduces O(M) computational overhead per update, which might be significant for very large batch sizes.
  • Single-Agent Focus: Current experiments are limited to single-agent settings. Extending HAEPO to multi-agent or competitive environments presents new challenges.
  • Large-Scale LLM Benchmarks: Due to resource constraints, the authors could not evaluate HAEPO on benchmarks like AlpacaEval or MT-Bench. Future work aims to incorporate these.

Summary updated

BibTeX
@misc{trivedi2025haepo,
  author = {Gaurish Trivedi and Alakh Sharma and Kartikey Singh Bhandari and Dhruv Kumar and Pratik Narang and Jagat Sesh Challa},
  title = {{HAEPO: History-Aggregated Exploratory Policy Optimization}},
  year = {2025},
  eprint = {2508.18884},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.18884},
}
Figure