Skip to content

DPEPO: Diverse Parallel Exploration Policy Optimization for LLM-based Agents

🕒 Published (v1): 2026-04-27 11:09 UTC · Source: Arxiv · Venue: ACL 2026 · link

Why this paper was selected

Parallel diverse exploration with policy optimization for broader agentic task coverage

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

DPEPO introduces a parallel exploration paradigm for LLM-based agents, enabling simultaneous interaction with multiple environments rather than single-path ReAct. It combines SFT cold-start with a hierarchical RL reward scheme that penalizes redundant actions and state transitions, achieving state-of-the-art success rates on ALFWorld (98.2%) and ScienceWorld (61.4%) with comparable or better inference efficiency than sequential baselines.

Problem

Standard ReAct-based LLM agents are constrained to sequential single-environment interaction, resulting in narrow, linear environmental understanding and limited exploration breadth. Naive multi-sampling across independent trajectories fails to promote true diversity and wastes tokens by running trials sequentially without cross-trajectory experience sharing. Existing RL methods (GRPO, GiGPO, RLVMR) improve reward granularity but remain locked in the sequential ReAct paradigm.

Method

DPEPO formalizes a parallel agent exploration framework where, at each step \(t\), an agent selects a subset \(E'_t \subseteq \{E_1, \ldots, E_K\}\) of \(K\) shared-initial-state environments and generates parallel actions \(A_t = \{(E_i, a_t) \mid E_i \in E'_t\}\) executed simultaneously. Training has two stages:

  1. SFT cold start: ~500–1000 human-annotated parallel-exploration trajectories (synthesized via DeepSeek-V3.2) teach the agent structured parallel output format.

  2. RL with hierarchical rewards:

  3. Parallel trajectory-level success reward \(R_\text{traj}(\tau) = 1\) if any environment reaches the goal state.
  4. Diverse Action Reward (DAR): penalizes action repetition both depth-wise (within an environment) and width-wise (across environments at the same step): $\(R_\text{action}(A_t) = \frac{1}{|E'_t|} \sum_{E_i \in E'_t} \alpha^{C_\text{depth}(E_i, a_t)} + \omega^{C_\text{width}(A_t)}\)$
  5. Diverse State Transition Reward (DTR): similarly penalizes repeated state-action transition pairs \(p_t = s_t \to a_t\) at depth and width levels.
  6. Step composite reward: \(R_\text{step}(A_t) = (R_\text{action} + R_\text{transition}) / 2\).

Step-level advantage is conditioned on trajectory-level advantage \(\Phi_\text{traj}\): positive trajectories receive the step reward directly; negative ones receive \(2 - R_\text{step}\). The final combined advantage \(\Phi(A_{i,t}) = \Phi_\text{step}(A_{i,t}) \cdot \Phi_\text{traj}(\tau_i)\) is optimized via a GRPO-style critic-free objective.

Key Contributions

  • Parallel agent exploration formulation: agent dynamically selects and acts in multiple environments simultaneously, sharing cross-trajectory observations.
  • Parallel trajectory-level success reward extending rule-based RL to concurrent multi-environment settings.
  • Two novel step-level diversity rewards (DAR, DTR) operating at both depth (within-env) and width (cross-env) granularities to penalize behavioral redundancy.
  • Hierarchical advantage combining trajectory- and step-level signals, enabling multi-granularity policy optimization without a critic model.
  • SOTA results on ALFWorld and ScienceWorld with inference time faster than GiGPO and DeepSeek-R1 despite higher token usage.

Results

  • ALFWorld (Qwen2.5-7B): DPEPO 98.2% vs. RLVMR 91.6%, GiGPO 90.5%, GRPO 77.5%.
  • ScienceWorld (Qwen2.5-7B): DPEPO 61.4% vs. RLVMR 47.5%, GiGPO 34.8%, GPT-4o 45.2%.
  • DPEPO-1.5B outperforms RLVMR-7B on ALFWorld by 2.53% while completing tasks in fewer steps.
  • Inference time on ALFWorld: DPEPO 44.7s vs. GiGPO 70.8s, DeepSeek-R1 237.0s (despite DPEPO using 2283.4 tokens vs. GiGPO's 1115.1).
  • Ablation: removing DAR degrades ScienceWorld avg from 61.4% to ~59.0%; removing DTR similarly degrades; removing both approaches ColdStart (50.7% ScienceWorld avg).
  • As \(K\) (parallel environments) increases, DPEPO token usage grows sub-linearly while GiGPO's grows approximately linearly.

Limitations

  • Token consumption per inference is roughly 2× GiGPO and 2.4× DeepSeek-V3, trading tokens for wall-clock speed.
  • Evaluation is limited to two text-based simulation benchmarks (ALFWorld, ScienceWorld); generalization to visual or web environments is undemonstrated.
  • The SFT cold-start requires manually annotated parallel trajectories (500–1000 per benchmark), introducing a non-trivial human-prior dependency.
  • Maximum environment count \(K=4\) during training; behavior at larger \(K\) or different \(K\) at inference than training is analyzed but the optimal configuration is environment-dependent.
  • The approach assumes environments sharing the same initial state, which may not hold in real-world multi-environment deployment.

Relevance to Agentic AI / LLM Agents

DPEPO directly advances the core RL training paradigm for LLM agents by breaking the sequential ReAct bottleneck—a fundamental constraint shared by GRPO, GiGPO, and RLVMR—through structured parallel environment interaction. The hierarchical reward design (trajectory + step-level diversity penalties) offers a general template for reward shaping that combats a well-known failure mode: mode collapse in exploration under entropy-based sampling. The finding that parallel execution yields faster wall-clock inference despite higher token counts is practically significant for deployment, suggesting that compute-per-token efficiency is not the right metric when parallelism is available. This work connects directly to the line of RLVR-based agent training (GRPO → GiGPO → RLVMR) and suggests parallel environment interaction as the next axis of improvement beyond reward granularity.