Technical Summary: Gated-BEPO

Problem Statement

Training Large Language Model (LLM) agents in long-horizon environments requires effective credit assignment: mapping sparse terminal rewards (success/failure) back to individual actions taken during the trajectory. Existing critic-free methods, such as GRPO, typically assign the same trajectory-level outcome advantage to every step. This coarse attribution reinforces ineffective actions in successful trajectories and penalizes useful actions in failed ones, slowing learning and limiting final performance.

Recent step-level methods attempt to refine this by constructing groups of steps via state or history matching (e.g., GiGPO, HGPO) or by using graph-based distance metrics (e.g., GraphGPO). However, these approaches face specific limitations:

1. They often rely on fixed-weight fusion of step and episode credits without adaptive mechanisms.
2. Graph-based methods can suffer from perceptual aliasing, where identical observations correspond to different underlying hidden states, leading to brittle value estimates.
3. They lack an evidence-based mechanism to determine when local step-level comparisons are reliable enough to override or supplement coarse trajectory outcomes.

Methodology: Gated-BEPO

Gated-BEPO (Confidence-Gated Bellman Credit Assignment) is a critic-free method that derives step-level credit from empirical rollout graphs and adaptively fuses it with trajectory-level credit based on local confidence.

1. Empirical Graph Construction

For each rollout group (a set of trajectories generated from the same initial task), the method merges identical observed states into a shared state graph. This graph retains the multiplicities of observed transitions (edges). Terminal states (success, failure, truncation) are treated as absorbing states with zero value.

2. Bellman Fixed-Point Value Estimation

Instead of learning a critic network, Gated-BEPO estimates state values directly from the empirical graph using a mean-backup Bellman fixed point.

• Initialization: Values are initialized with Monte-Carlo returns.
• Update: The value of a non-terminal state $s$ is updated by averaging the returns of its observed outgoing transitions:
  $$V^{(k+1)}(s) = \frac{1}{|E(s)|} \sum_{(r, s') \in E(s)} [r + \gamma V^{(k)}(s')]$$
  where $E(s)$ is the multiset of outgoing transitions. This operator is a contraction, ensuring a unique fixed point that reflects the empirical action distribution of the current policy.
• Temporal-Difference (TD) Residuals: Once the fixed point is reached, the method computes TD residuals for each transition: $\delta_i = r_i + \gamma V(s'_i) - V(s_i)$. These residuals measure whether a specific transition is better or worse than the empirical average of outgoing edges from that state.

3. Generalized Advantage Estimation (GAE)

The TD residuals are propagated backward along each original trajectory using GAE to capture both immediate and downstream effects:
$$\hat{A}^{FP}_i = \delta_i + \gamma \lambda \hat{A}^{FP}_{next(i)}$$
This yields a fixed-point step advantage ($\hat{A}^{FP}$) that is standardized across the rollout group.

4. Confidence-Gated Credit Mixing

The core innovation is an adaptive gating mechanism that determines how much to trust the local Bellman signal versus the global trajectory outcome.

• Gate Definition: A binary gate $\rho(s)$ is activated only if the state $s$ has sufficient local evidence:
  1. Repeated visits ($n(s) \ge n_{min}$).
  2. Observed branching ($|Succ(s)| \ge b_{min}$, i.e., multiple distinct successors).
• Mixing Rule: The final advantage $\hat{A}_i$ is a weighted sum of the outcome advantage ($\hat{A}^{out}$) and the fixed-point advantage ($\hat{A}^{FP}$):
  $$\hat{A}_i = \eta_i \hat{A}^{out}_i + w \rho(s_i) \hat{A}^{FP}_i$$
  • Untrusted States ($\rho=0$): The method relies entirely on the outcome advantage ($\eta_i = 1$).
  • Trusted States ($\rho=1$): The fixed-point advantage is activated, and the outcome advantage is down-weighted ($\eta_i = \eta_{min}$) to prevent it from overwhelming the more informative step signal.

Key Contributions

1. Critic-Free Bellman Fixed-Point Estimator: A method to derive state values and step-level advantages directly from empirical rollout graphs without training a separate value network, reducing noise and sensitivity to perceptual aliasing compared to graph-distance methods.
2. Confidence-Gated Mixing: A mechanism that uses local graph evidence (branching and repetition) to gate the application of step-level credit. This prevents unsupported local estimates from corrupting policy updates while ensuring reliable step signals are not drowned out by coarse trajectory outcomes.
3. Empirical Validation: Demonstration of consistent improvements across text-based (WebShop, ALFWorld) and vision-language (Sokoban) environments using various LLM backbones (Qwen2.5, Qwen3).

Experimental Results

Experiments were conducted on WebShop, ALFWorld, and Visual Sokoban using Qwen2.5 (1.5B, 7B) and Qwen3 (1.7B) models.

• Performance Gains: Gated-BEPO consistently outperformed strong baselines including GRPO, GiGPO, HGPO, and GAGPO.
  • On ALFWorld (1.5B), it improved success rates by 2.78% over HGPO.
  • On WebShop (1.5B), it improved success by 3.51% over HGPO and task scores by 6.9% over GRPO.
  • On Visual Sokoban, it achieved 80.03% success, surpassing GRPO and GiGPO by significant margins.
• Learning Speed: Training curves indicate faster convergence and higher final success rates compared to trajectory-level methods.
• Robustness to Aliasing: In a controlled experiment on ALFWorld using raw observations (without augmented state information), GraphGPO failed to learn due to perceptual aliasing, whereas Gated-BEPO remained effective. This is attributed to its use of transition-specific TD residuals rather than shortest-path distances on merged graphs.
• Ablation Studies:
  • All three components (Fixed-Point credit, Confidence Gate, Outcome Down-weighting) contributed positively to performance.
  • The "Mean" Bellman backup was found superior to "Max" or "Softmax" backups, which amplified rare transitions.
  • The binary gate requiring distinct successors was more effective than continuous confidence scores or gates based solely on repetition.

Significance

The paper posits that Gated-BEPO addresses the fundamental trade-off in critic-free RL for agents: balancing the stability of trajectory-level outcomes with the granularity of step-level learning. By deriving values from empirical graphs and gating their application based on local evidence, the method provides a more reliable signal for policy optimization in long-horizon tasks. It demonstrates that fine-grained credit assignment can be achieved without the computational cost or instability of learned critics, provided that the system can distinguish between states where local comparison is empirically supported and those where it is not.