DEPPO: Dual Experience Pool Policy Optimization for Long-Horizon Reinforcement Learning¶
Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Reasoning
Keywords: Reinforcement Learning, Credit Assignment, Long-Horizon Reasoning, Dual Experience Pools, Advantage Reweighting
TL;DR¶
Addressing the severe credit assignment mismatch caused by outcome-level reward broadcasting in long-horizon agents and complex multi-step reasoning, DEPPO maintains structured dual experience pools for historical successes and failures to compute state-conditioned success–failure preference log-ratios, adaptively reweighting step-level advantages under support-aware gating and asymmetric memory updates without any external critic or process supervision.
Background & Motivation¶
Reinforcement learning (RL) has emerged as an essential paradigm for eliciting multi-step reasoning and autonomous planning capabilities in large language models. However, in quintessential long-horizon and high-uncertainty decision-making tasks such as embodied interaction, web navigation, and symbolic planning, environmental feedback is notoriously sparse, typically consisting solely of a single scalar outcome reward received at the termination of a multi-turn trajectory. Consequently, standard policy optimization algorithms are forced to uniformly broadcast this terminal outcome signal across all intermediate decision steps. This crude credit assignment mechanism inevitably over-reinforces incidental, suboptimal, or exploratory redundant actions present in overall successful trajectories, while undesirably penalizing highly effective, logically sound early decisions that were unfortunately terminated by an isolated late-stage misstep, thereby inducing high gradient variance and severe policy instability.
Prior literature attempts to tackle this credit assignment dilemma along multiple distinct lines, each burdened with inherent trade-offs. Critic-based value networks estimate intermediate state-action values to reduce variance, yet they introduce substantial training overhead, architectural complexity, and persistent value approximation bias in complex sequential text environments. Critic-free frameworks (such as PPO, GRPO, DAPO, and GiGPO) improve sample efficiency via intra-group ranking or state-aware baselines, but they fundamentally remain anchored to trajectory-level returns. Meanwhile, process-supervised reward models (PRMs, such as Math-Shepherd, OmegaPRM, and ThinkPRM) provide granular step-level verification, but they demand exorbitant step-level annotations or expensive tree-search synthetic rollouts that struggle to generalize across diverse operational environments. Critically, nearly all existing RL frameworks treat training trajectories as transient isolated rollouts, discarding rich historical experiences and failing to exploit the statistical regularities accumulated across preceding successful and failed trajectories.
This fundamental observation prompts a compelling inquiry: can historical trajectories be structured into state-conditioned contrastive signals to govern reliable step-level credit assignment? Under identical task conditions and environmental states, evaluating whether a specific intermediate action statistically correlates with final task success versus failure provides an objective, empirical ground truth for credit assignment. Core idea: construct structured dual experience pools modeling task-conditioned success and failure statistics, adaptively derive step-level success–failure preference signals via smoothed action likelihood log-ratios, and reweight policy advantages through support-aware gating paired with asymmetric freshness-and-risk memory evolution.
Method¶
DEPPO (Dual Experience Pool Policy Optimization) is a critic-free, purely experience-driven policy optimization framework. Rather than evaluating intermediate actions within the isolated scope of the current rollout trajectory, DEPPO dynamically maintains two separate memory pools tracking action occurrences across past successful and failed episodes. At each training iteration, before committing the newly sampled rollout batch into memory (preventing self-leakage), the framework queries both pools using the exact task-state key to compute an additive-smoothed conditional probability ratio. When empirical support criteria are satisfied, the resulting log-ratio score modulates the baseline advantage function in an outcome-aware manner. Following policy updates, the trajectories are written into the pools via an asymmetric update rule—rewarding fresh exploration in success trajectories while penalizing fatal and recurrent errors in failure trajectories—regulated by periodic exponential decay and memory pruning.
Overall Architecture¶
During each training iteration, the policy \(\pi_\theta\) rolls out a batch of interactive trajectories across sampled tasks, acquiring terminal outcome indicators \(y_i \in \{+1, -1\}\). For every intermediate step within a trajectory, DEPPO extracts the normalized task-state tuple \((u, s_t)\) and queries the historical success pool \(\mathcal{D}^+\) and failure pool \(\mathcal{D}^-\) to retrieve empirical action counts. After applying additive smoothing over the unified observed action set, the system computes the relative success–failure preference score \(\Delta_t\). A support-aware activation gate checks whether historical evidence is sufficiently dense and confident. If activated, the base advantage (derived from state-aware group baselines like GiGPO) is adaptively scaled according to the trajectory outcome and preference direction. Subsequently, PPO-clipped policy optimization is executed, followed by asymmetric pool insertion, exponential decay, and multi-tier pruning to maintain bounded, non-stale memory.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Task Sampling & Interactive Trajectory Rollout<br/>agent generates trajectory batch with terminal reward"] --> B["Dual Experience Pools & Likelihood-Ratio Query<br/>retrieve task-state action statistics from D+ and D-"]
B --> C["Support-Aware Gating & Advantage Reweighting<br/>filter low-support noise and rescale step advantage"]
C --> D["Critic-Free Policy Optimization<br/>update policy via PPO-clipped surrogate objective"]
D --> E["Asymmetric Experience Pool Insertion<br/>freshness-aware success and risk-weighted failure updates"]
E --> F["Exponential Decay & Compact Capacity Pruning<br/>deprecate stale entries and bound state-action memory"]
F -.->|closed-loop guidance for subsequent iterations| B
Key Designs¶
1. Dual Experience Pools & Likelihood-Ratio Query: Statistical Preference Modeling without Value Networks To circumvent the training fragility and computational overhead of neural critic networks, DEPPO organizes past trajectories into two structured experience pools: \(\mathcal{D}^+\) for successful episodes and \(\mathcal{D}^-\) for failed ones. Each entry is indexed by a compound task-state key \((u, s) \to c(u, s, a)\), preserving task-conditioned semantics across structurally identical environmental observations. To reliably estimate probabilities from sparse early empirical counts, DEPPO aggregates the union of historical actions and the current action \(\mathcal{A}_{u, s_t}\) and applies additive smoothing with parameter \(\alpha > 0\): $\(P^{\pm}(a_t \mid u, s_t) = \frac{c_{u}^{\pm}(s_t, a_t) + \alpha}{N_u^{\pm}(s_t) + \alpha |\mathcal{A}_{u, s_t}|}\)$ where \(N_u^{\pm}(s_t) = \sum_a c_u^{\pm}(s_t, a)\) represents the cumulative visit count within the respective pool. The relative success–failure preference score is formulated as the logarithmic ratio: $\(\Delta_t = \log \frac{P^+(a_t \mid u, s_t) + \epsilon}{P^-(a_t \mid u, s_t) + \epsilon}\)$ This symmetric formulation measures the relative empirical evidence of success versus failure: \(\Delta_t > 0\) signifies that under this exact task-state condition, action \(a_t\) is predominantly associated with historical successes, whereas \(\Delta_t < 0\) reveals an association with historical failure modes.
2. Support-Aware Gating & Advantage Reweighting: Noise-Resilient Step-Level Credit Modulation Because empirical frequency estimates in sparsely visited states suffer from high variance, DEPPO introduces an explicit support-aware gate \(g_t\) to prevent premature and noisy credit distortion. Gating requires that the cumulative support satisfies \(S_{u, s_t} \ge S_{\min}\), individual pool supports satisfy \(S_{u, s_t}^+ \ge S_{\text{each}}^{\min}\) and \(S_{u, s_t}^- \ge S_{\text{each}}^{\min}\), and the magnitude of the preference signal meets \(|\Delta_t| \ge \tau_\Delta\). If the condition is met, \(g_t = 1\); otherwise, \(g_t = 0\) and the base advantage is preserved without adjustment. With \(g_t = 1\), the advantage is modulated using the trajectory outcome label \(y_i \in \{+1, -1\}\): $\(\tilde{A}_{i, t} = \text{clip}\left(\exp(\beta \cdot y_i \Delta_t), w_{\min}, w_{\max}\right)^{g_t} \cdot A_{i, t}\)$ where \(\beta\) controls the reweighting sharpness and \([w_{\min}, w_{\max}]\) strictly constrains the scaling range (defaulting to \([0.2, 1.8]\)). This design achieves targeted bidirectional error correction: for a successful trajectory (\(y_i = +1\)), actions aligned with historical success patterns (\(\Delta_t > 0\)) receive boosted positive advantages, while incidental bad actions (\(\Delta_t < 0\)) are attenuated; conversely, for a failed trajectory (\(y_i = -1\)), fatal actions (\(\Delta_t < 0\)) receive amplified penalties, whereas productive intermediate actions (\(\Delta_t > 0\)) are protected from undeserved suppression.
3. Asymmetric Experience Pool Insertion: Balancing Innovative Exploration and Fatal Pattern Avoidance Successful and failed experiences serve fundamentally different functional objectives during policy improvement. Success trajectories must not only reinforce established winning strategies but also actively foster novel discoveries; failure trajectories, by contrast, must concentrate heavily on chronic failure modes, invalid execution attempts, and catastrophic final moves. For a successful step (\(y_i = +1\)), DEPPO applies a freshness-aware insertion weight: $\(\psi_t^+ = \psi_0^+ \left(1 + \gamma_f \max\left(0, \eta - P^+(a_t \mid u, s_t)\right)\right)\)$ which grants larger updates to valid actions that remain underrepresented in \(\mathcal{D}^+\), preventing policy collapse onto trivial sub-optimal paths. For a failed step (\(y_i = -1\)), insertion weight is scaled by three multiplicative risk factors: $\(\psi_t^- = \psi_0^- \left(1 + \gamma_{\text{late}} \frac{t - 1}{T_i - 1}\right) \left(1 + \gamma_{\text{rep}} \log(1 + c_u^-(s_t, a_t))\right) \left(1 + \gamma_{\text{invalid}} \mathbb{I}[a_t = \text{INVALID}]\right)\)$ which explicitly prioritizes actions executed close to trajectory termination, actions with high recurrence across past failures, and environment-invalid actions.
4. Exponential Decay & Compact Capacity Pruning: Maintaining Policy-Synchronized Bounded Memory As training advances, early trajectories produced by an immature policy become outdated and irrelevant. To prevent unbounded memory expansion and catastrophic retrieval delays, DEPPO applies periodic exponential decay: $\(c_u^{\pm}(s, a) \leftarrow \lambda c_u^{\pm}(s, a), \quad \lambda \in (0, 1)\)$ Entries with decayed counts falling below \(\delta_a\) are removed, and each task-state pair retains only its top-\(K_a\) (e.g., 32) actions. If total state visits drop below \(\delta_s\), the entire state entry is pruned. Furthermore, each task enforces a maximum state budget \(K_s\), expelling states with low visitation and stale timestamps first. This pruning pipeline maintains the active CPU dictionary footprint within 3–8 MB (serialized disk footprint of 1.02 MB) with zero GPU memory utilization.
Loss & Training¶
DEPPO builds on top of GiGPO's state-aware group optimization strategy, preserving the standard clipped PPO objective while seamlessly substituting the adaptive advantage \(\tilde{A}_t\): $\(\mathcal{L}_{\text{DEPPO}}(\theta) = -\mathbb{E}_t \left[ \min\left( r_t(\theta) \tilde{A}_t, \, \text{clip}(r_t(\theta), 1 - \varepsilon_{\text{clip}}, 1 + \varepsilon_{\text{clip}}) \tilde{A}_t \right) \right]\)$ where \(r_t(\theta) = \frac{\pi_\theta(a_t \mid s_t)}{\pi_{\theta_{\text{old}}}(a_t \mid s_t)}\) and \(\varepsilon_{\text{clip}} = 0.2\). Standard training hyperparameters comprise a learning rate of \(1 \times 10^{-6}\), mini-batch size of 256, KL divergence penalty coefficient of 0.01, 8 rollouts per prompt, training batch size of 16, and prompt/response length limits of 4096 and 512 tokens across 150 training epochs on 8 GPUs. For DEPPO memory components, \(\alpha = 0.1\), \(\tau_\Delta = 0.03\), \(S_{\min} = 8\), \(S_{\text{each}}^{\min} = 8\), \([w_{\min}, w_{\max}] = [0.2, 1.8]\), and \(\lambda = 0.995\).
Key Experimental Results¶
Main Results¶
DEPPO is systematically evaluated on two primary sparse-reward long-horizon benchmarks: ALFWorld (multi-step embodied household interaction across Pick, Look, Clean, Heat, Cool, and Pick2 subtasks) and WebShop (web browsing and product retrieval under delayed rewards), utilizing Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct backbones.
| Model / Regime | Method | ALFWorld Avg. Success (%) | WebShop Score | WebShop Success (%) |
|---|---|---|---|---|
| Qwen2.5-1.5B-Instruct | ||||
| Prompting | Base Qwen2.5 Policy | 4.7 | 23.1 | 5.2 |
| Prompting | ReAct | 11.6 (+6.9) | 40.1 (+17.0) | 11.3 (+6.1) |
| Prompting | Reflexion | 19.3 (+14.6) | 55.8 (+32.7) | 21.9 (+16.7) |
| Standard RL | PPO | 52.8 (+48.1) | 73.8 (+50.7) | 51.5 (+46.3) |
| Trajectory RL | RLOO | 66.4 (+61.7) | 73.9 (+50.8) | 52.1 (+46.9) |
| Trajectory RL | GRPO | 69.1 (+64.4) | 75.8 (+52.7) | 56.8 (+51.6) |
| Trajectory RL | DAPO | 58.6 (+53.9) | 78.0 (+54.9) | 58.2 (+53.0) |
| Advanced Agent RL | EMPG | 69.7 (+65.0) | 80.4 (+57.3) | 60.8 (+55.6) |
| Advanced Agent RL | RewardFlow | 66.6 (+61.9) | 78.3 (+55.2) | 60.9 (+55.7) |
| Advanced Agent RL | GiGPO (Baseline) | 84.5 (+79.8) | 83.1 (+60.0) | 65.0 (+59.8) |
| Advanced Agent RL | HCAPO | 85.1 (+80.4) | 83.8 (+60.7) | 68.5 (+63.3) |
| Ours | DEPPO | 92.2 (+87.5) | 86.5 (+63.4) | 73.1 (+67.9) |
| Qwen2.5-7B-Instruct | ||||
| Prompting | Base Qwen2.5 Policy | 14.5 | 26.4 | 7.8 |
| Prompting | ReAct | 27.9 (+13.4) | 46.2 (+19.8) | 19.5 (+11.7) |
| Prompting | Reflexion | 39.9 (+25.4) | 58.1 (+31.7) | 28.8 (+21.0) |
| Standard RL | PPO | 81.2 (+66.7) | 81.4 (+55.0) | 68.7 (+60.9) |
| Trajectory RL | RLOO | 75.9 (+61.4) | 80.3 (+53.9) | 65.7 (+57.9) |
| Trajectory RL | GRPO | 76.4 (+61.9) | 79.3 (+52.9) | 66.1 (+58.3) |
| Trajectory RL | DAPO | 75.5 (+61.0) | 80.2 (+53.8) | 67.2 (+59.4) |
| Advanced Agent RL | EMPG | 78.0 (+63.5) | 81.0 (+54.6) | 69.3 (+61.5) |
| Advanced Agent RL | RewardFlow | 80.2 (+65.7) | 84.4 (+58.0) | 73.4 (+65.6) |
| Advanced Agent RL | GiGPO (Baseline) | 88.6 (+74.1) | 86.2 (+59.8) | 75.2 (+67.4) |
| Advanced Agent RL | HCAPO | 90.2 (+75.7) | 85.1 (+58.7) | 73.8 (+66.0) |
| Ours | DEPPO | 95.7 (+81.8) | 90.1 (+63.7) | 84.3 (+76.5) |
In addition, on the vision-language planning benchmark Sokoban, DEPPO achieves an 80.8% success rate on Qwen2.5-VL-3B (vs. 11.7% for GRPO and 67.1% for GiGPO) and 93.3% on Qwen3-VL-8B (vs. 21.9% for GRPO and 82.9% for GiGPO). When benchmarked against external skill-augmented agent methods distilled from OpenAI o3 (Skill-SD, SDAR, SkillRL), DEPPO outperforms SkillRL on ALFWorld 7B (95.7% vs. 89.1%) and WebShop (84.3% vs. 76.5%) without requiring any external teacher models.
Ablation Study¶
The contribution of each individual design component is dissected across both model scales:
| Component Variant | ALFWorld SC (%) | ALFWorld Score | WebShop SC (%) | WebShop Score | Note |
|---|---|---|---|---|---|
| Qwen2.5-1.5B with GiGPO | 84.5 | 47.6 | 65.0 | 83.1 | Baseline group-in-group policy optimization |
| + Positive Experience Pool \(\mathcal{D}^+\) | 90.4 | 58.3 | 69.7 | 85.2 | Reusable positive behavior reinforcement |
| + Negative Experience Pool \(\mathcal{D}^-\) | 91.3 | 64.4 | 71.9 | 85.8 | Dual-pool contrastive high-risk suppression |
| + Dynamic Pool Update (Full DEPPO) | 92.2 | 68.0 | 73.1 | 86.5 | Freshness, risk weights, decay & pruning |
| Qwen2.5-7B with GiGPO | 88.6 | 55.7 | 75.2 | 86.2 | 7B baseline without memory credit assignment |
| + Positive Experience Pool \(\mathcal{D}^+\) | 93.5 | 68.3 | 79.8 | 88.5 | High-potential success trajectory guidance |
| + Negative Experience Pool \(\mathcal{D}^-\) | 95.1 | 71.1 | 82.7 | 89.6 | Elimination of recurrent failure patterns |
| + Dynamic Pool Update (Full DEPPO) | 95.7 | 73.2 | 84.3 | 90.1 | Full framework yields top performance |
Key Findings¶
- Stage-Wise Transition of Dual Pools: Training dynamics indicate an instructive temporal shift: early training is heavily guided by the failure pool, which prunes volatile exploration and suppresses high-risk choices (at step 40, 9,320 action entries are pruned for the 1.5B model vs. 531 for the 7B model); as policy competence matures, the positive pool expands and takes over, transitioning the optimization from risk-mitigation to constructive pattern reinforcement.
- Support-Aware Gating is Essential for Stability: In the absence of threshold-based gating (unfiltered variant), the gated ratio expands aggressively, injecting volatile scaling multipliers derived from low-count actions that disrupt training; with support-aware filtering, only roughly 20% of confident steps receive reweighting, producing smooth delta statistics and rapid convergence on complex subtasks such as Heat, Cool, and Pick2.
- Negligible Computational and Memory Footprint: Lookups in CPU-based dictionaries require 42.21 ms/step, updates take 34.91 ms/step, and advantage reweighting takes only 0.04 ms/step, producing an amortized overhead of 85.12 ms/step (adding a mere 0.04%–0.07% to overall training wall-clock time over GiGPO). Live memory usage is restricted to 3–8 MB on CPU with zero GPU memory overhead.
Highlights & Insights¶
- Cross-Trajectory Statistical Grounding: Bypasses the fragile balance of training auxiliary neural value estimators by anchoring step credit directly in empirical state-conditioned occurrence frequencies across historical runs, establishing an interpretable and unbiased contrastive credit baseline.
- Asymmetric Learning Mechanics: Recognizes that success and failure carry inherently asymmetric information: positive updates must incentivize novelty to prevent premature policy collapse, while negative updates must heavily penalize near-terminal, recurrent, or illegal actions to eliminate hazardous decision deadlocks.
- Model-Agnostic and Architecture-Free: Functions as a plug-and-play advantage modulator decoupled from the underlying neural architecture, seamlessly complementing diverse base RL algorithms (PPO, GRPO, GiGPO) across both textual and multimodal vision-language agents.
Limitations & Future Work¶
- Reliance on Structured State Representations: The framework currently indexes memory using normalized environmental text observations and discrete executable action strings; extending it to unconstrained, continuous, or long free-form CoT reasoning paths will necessitate robust semantic representation clustering or vector state quantization.
- Cold-Start Sensitivity in Ultra-Sparse Regimes: In environments with near-zero baseline success rates, the positive experience pool remains empty during initial epochs, temporarily degrading the framework into a pure failure-avoidance mechanism until the first viable trajectory is discovered. Incorporating offline warm-up demonstrations could overcome this hurdle.
Related Work & Insights¶
- vs. GiGPO / GRPO (Critic-Free Group RL): While GRPO and GiGPO compute group-relative baselines across parallel rollouts within the same batch, they discard all historical experience across iterations. DEPPO integrates long-term memory across batches, allowing immediate decisions to be informed by aggregated historical statistics.
- vs. Process Reward Models (PRMs / Math-Shepherd): PRMs require training an independent verifier model on costly human or synthetic step-level labels, suffering from out-of-distribution hallucinations. DEPPO achieves fine-grained step-level credit assignment entirely critic-free and annotation-free through simple dynamic memory counting.
Rating¶
- Novelty: ⭐⭐⭐⭐⭐ [Brilliant transformation of historical rollouts into structured contrastive likelihood-ratio credit signals without auxiliary neural networks]
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ [Extensive evaluations spanning ALFWorld subtasks, WebShop, Sokoban vision-language planning, runtime benchmarks, and internal dynamics]
- Writing Quality: ⭐⭐⭐⭐⭐ [Exceptionally clear mathematical formalization, comprehensive algorithmic descriptions, and rigorous empirical validation]
- Value: ⭐⭐⭐⭐⭐ [Provides a practical, lightweight, and highly effective credit assignment paradigm for long-horizon agent RL and multi-step reasoning]