Freshness-Aware Prioritized Experience Replay for LLM/VLM Reinforcement Learning

1. Problem Statement

Reinforcement Learning (RL) has become the dominant paradigm for post-training Large Language Models (LLMs) and Vision-Language Models (VLMs), particularly for complex agentic tasks (e.g., web search, tool use, reasoning). However, current state-of-the-art methods rely on on-policy algorithms (PPO, GRPO, REINFORCE++), which suffer from two critical inefficiencies:

1. Poor Sample Efficiency: These methods discard all collected trajectories after a single gradient update. In agentic tasks where environment interactions (e.g., API calls, search queries) are expensive and multi-turn, this leads to massive computational waste.
2. Failure of Standard Experience Replay: While Prioritized Experience Replay (PER) is standard in classical RL to reuse past data, directly applying it to LLMs fails due to Priority Staleness.
   • The Mechanism of Failure: LLM policies evolve rapidly due to large gradient updates on billion-parameter models. A trajectory collected by an old policy ($\pi_\mu$) becomes "stale" as the current policy ($\pi_\theta$) diverges.
   • The Consequence: Standard PER assigns fixed priorities based on initial metrics (e.g., TD error or reward). As the policy diverges, the Effective Sample Size (ESS) of these old, high-priority trajectories decays exponentially. Consequently, the model wastes training time on outdated data that is no longer informative or is even detrimental, causing performance degradation compared to on-policy baselines.

2. Methodology: FreshPER

The authors propose FreshPER, a novel framework that augments standard PER with a freshness-aware age decay mechanism grounded in importance sampling theory.

Core Innovation: Exponential Age Decay

The key insight is that the utility of a trajectory decays exponentially with the number of gradient steps ($\Delta$) elapsed since its collection, driven by the divergence between the behavior policy and the current policy.

• Theoretical Foundation:
  • The authors derive that the Effective Sample Size (ESS) is bounded by the KL divergence between policies: $ESS \leq n \cdot \exp(-D_{KL})$.
  • They approximate the KL divergence growth as linear with respect to training steps ($\Delta$), leading to an exponential decay in sample utility.
• The Priority Function:
  The new priority $p_i$ for a trajectory $i$ is calculated as:
  $$p_i = p_i^{\text{base}} \times \exp\left(-\frac{\Delta_i}{\tau}\right)$$
  Where:
  • $p_i^{\text{base}}$: The standard base priority (e.g., reward magnitude $|r_i|$, advantage, or TD error).
  • $\Delta_i$: The age of the trajectory (current step $t$ minus collection step $t_i$).
  • $\tau$: A tunable hyperparameter (age decay constant) controlling the "half-life" of the priority.

Implementation Details

• Hybrid Training Pipeline: The system integrates an on-policy loop (collecting fresh data) with an off-policy loop (replaying stored data).
• Async Priority Refresh: An asynchronous CPU thread continuously updates the priorities of all entries in the replay buffer by recalculating the age decay factor, ensuring the priority queue reflects the current policy's state without blocking GPU training.
• Base Priority Flexibility: The method is modular. It can use reward magnitude (for critic-free methods like REINFORCE++), advantage magnitude, or TD error as the base priority, simply multiplying them by the age decay term.
• System Architecture: Built on the ROLL framework, utilizing DeepSpeed for training and vLLM for inference, with the replay buffer managed on a CPU controller to pipeline efficiently with GPU operations.

3. Key Contributions

1. First Successful Application of PER to LLM/VLM RL: The paper identifies "priority staleness" as the primary failure mode of standard PER in LLMs and provides the first working solution.
2. Theoretical Justification for Age Decay: Derives the exponential decay of sample utility based on the relationship between Effective Sample Size (ESS), importance weights, and policy divergence (KL/Chi-squared divergence).
3. Modular Framework: Introduces a drop-in mechanism (FreshPER) that can be combined with any existing PER base priority (reward, advantage, TD error) and any on-policy algorithm.
4. Comprehensive Evaluation: Validates the approach across 8 diverse environments (text-only LLM and multimodal VLM) using models ranging from 0.5B to 7B parameters.

4. Experimental Results

The authors evaluated FreshPER against On-Policy baselines and Standard PER (without age decay) across tasks including NQ Search, AIME, Sokoban, FrozenLake, and GeoQA.

• Performance Gains: FreshPER significantly outperformed both baselines.
  • NQ Search (Agentic): +46% improvement over on-policy.
  • Sokoban (Planning): +367% improvement over on-policy.
  • VLM FrozenLake: +133% improvement.
  • AIME (Math): +18% improvement.
• Failure of Standard PER: Standard PER without age decay consistently degraded performance compared to on-policy training, often catastrophically (e.g., Sokoban score dropped from 0.49 to -0.90), confirming that stale high-priority data harms learning.
• Ablation Studies:
  • $\tau$ Sensitivity: The decay constant $\tau$ is task-dependent. Rapidly evolving tasks (Sokoban) require aggressive decay ($\tau=500$), while slower tasks (FrozenLake) benefit from gentler decay ($\tau=1000$).
  • Stability: While Importance Sampling (IS) correction alone did not boost peak performance, it significantly improved training stability in the late stages, preventing performance collapse.
  • Task Difficulty: The benefits of FreshPER scale with task difficulty. On simple tasks where on-policy training converges quickly (e.g., GSM8K, CliffWalking), replay offered little advantage.

5. Significance and Conclusion

• Bridging Classical and Modern RL: The paper demonstrates that classical sample-efficiency techniques (like PER) remain highly effective for LLMs, provided they are adapted to handle the unique, rapid distribution shifts of billion-parameter models.
• Cost Reduction: By enabling the reuse of expensive multi-turn agentic trajectories, FreshPER drastically reduces the computational cost and time required for RL post-training.
• Generalizability: The method works seamlessly across text-only and multimodal (VLM) settings, suggesting the "freshness" principle is fundamental to sequence-based RL regardless of modality.
• Future Directions: The authors suggest future work on automatic tuning of $\tau$ based on observed policy divergence rates and scaling to even larger models (70B+).

In summary, FreshPER solves the critical bottleneck of sample inefficiency in LLM RL by introducing a mathematically grounded "freshness" mechanism that prevents the model from being misled by outdated, high-priority data.