- Rating
- 2(+1)
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper proposes BARS, a bilevel framework for learning dense turn-level rewards in agentic RL. The main gripe is that existing methods like PRIME and iStar treat the trajectory distribution as fixed, ignoring how reward updates actually shift the policy and change the trajectories you then learn from. BARS fixes this by splitting the problem: the upper level learns a shaping reward from outcome feedback while the lower level optimises the policy under that reward. They derive the full hypergradient, use an alternating algorithm, and prove an O(1/ K ) convergence rate for an idealised case. Experiments on NQ-Search and NQ-HotpotQA with Qwen2.5-3B and Llama3.1-8B show it beats OR, LLM-judge, PRIME, and iStar baselines, plus it plays nice with PPO and RLOO.
Critical strengths
The paper spots a genuine coupling between reward learning, policy optimisation, and the trajectory distribution in agentic RL. Framing this as a bilevel problem is a sensible way to expose that dependency.
Critical weaknesses
-
The biggest problem is that the reward function leaks the answer. The final success signal is built directly into the turn-level reward formula. This means the trajectory score used in the upper-level training losses (CE and DPO) already contains the outcome label. Instead of learning a dense reward that genuinely explains success from intermediate steps, the model can just exploit the outcome term that's already baked into the score. This defeats the whole purpose of learning turn-level rewards from outcome feedback. It also makes the "linear reward model" ablation unfair unless they handle the outcome term the same way.
-
Theorem 1 proves convergence for an idealised algorithm using one-step soft policy iteration, presumably with exact hypergradients. But the actual experiments use GRPO/PPO/RLOO with an efficient hypergradient approximation. The authors admit this gap, yet the abstract and intro still tout the convergence guarantee without clearly saying it doesn't apply to their practical method. They should either prove guarantees for the actual approximation used, or tone down the theoretical claims.
Questions for authors
-
In the upper-level CE/DPO losses, does r_θ(x,y) include the terminal success term r_succ(x,y)? If yes, how do you prevent the loss from trivially exploiting the label? If no, please correct Eq. (3) and the surrounding text.
-
Is πθ the same model as the lower-level policy, a separate reward model, or a frozen reference? How is θ trained in the practical algorithm?
-
How are the correction terms estimated in practice? What is the additional compute and memory cost relative to PRIME/iStar?
-
What exactly does "best before training collapse" mean? Are all methods trained for the same number of steps and with the same rollout budget? Please report final and best numbers for all methods.
-
Does the "linear parameterization" ablation also include the terminal success term in the reward score? If so, is the comparison isolating reward parameterization or label leakage?
Can you provide direct diagnostics of the learned turn-level rewards, e.g., calibration or correlation with eventual success?
10 comments
2. Connection to existing reward-shaping literature.
Retaining the original task reward while learning additional shaping rewards is a standard practice in reinforcement learning. Classical potential-based reward shaping [C1] augments the original reward with a shaping term. More recent works [C2,C3,C4,C5] optimize the shaping reward in the form of where is the original task reward and is the shaping reward. BARS follows this established additive reward-shaping principle by retaining the original terminal reward while learning additional turn-level rewards. We emphasize that this literature motivates the additive reward construction.
3. Additional empirical validation.
To further investigate whether the terminal success reward undermines the learning of dense rewards, we conduct additional ablations on NQ-Search using Qwen2.5-3B with GRPO as the RL optimizer. Specifically, we compare the proposed log-ratio parameterization and a linear reward parameterization, each with and without the terminal success reward in the upper-level CE/DPO scores. The lower-level reward and all other training configurations remain unchanged, isolating the effect of including the terminal outcome in the upper-level objective.
| Reward parameterization | Outcome term included | Success rate (%) |
|---|---|---|
| Log-ratio | ✓ | 47.8 |
| Log-ratio | × | 47.4 |
| Linear | ✓ | 46.1 |
| Linear | × | 45.8 |
The results show that removing the terminal success term from the upper-level objective leads to only minor performance decreases of 0.4 and 0.3 percentage points for the log-ratio and linear parameterizations, respectively. Moreover, the log-ratio parameterization consistently outperforms the linear parameterization, regardless of whether the terminal reward is included. These findings demonstrate that the performance gains primarily stem from the learned shaping reward rather than the inclusion of the outcome label in the upper-level objective.
Weakness 2: Theorem 1 proves convergence for an idealised algorithm using one-step soft policy iteration, presumably with exact hypergradients. But the actual experiments use GRPO/PPO/RLOO with an efficient hypergradient approximation. The authors admit this gap, yet the abstract and intro still tout the convergence guarantee without clearly saying it doesn't apply to their practical method. They should either prove guarantees for the actual approximation used, or tone down the theoretical claims.
Answer: Thank you for this suggestion. In the newly uploaded version, we have revised the abstract and introduction (highlighted in blue) to explicitly clarify that the convergence guarantee in Theorem 1 applies to the idealized BARS algorithm using one-step soft policy iteration, rather than the practical implementation with GRPO/PPO/RLOO and the efficient hypergradient approximation. As already acknowledged in Section 5 (Practical Implementation), the theoretical guarantee does not directly extend to these practical modifications. The revised presentation now clearly distinguishes the theoretical guarantee for the idealized algorithm from the empirical validation of the practical implementation in the abstract and introduction.
Question 1: In the upper-level CE/DPO losses, does include the terminal success term ? If yes, how do you prevent the loss from trivially exploiting the label? If no, please correct Eq. (3) and the surrounding text.
Answer: Yes, includes the terminal success reward, as defined in Eq. (3). However, as clarified in our response to Weakness 1, including this fixed, parameter-independent outcome term does not allow the model to bypass learning the shaping reward. The upper-level CE/DPO losses continue to optimize the learned shaping component, and the terminal reward does not directly contribute to intermediate turn-level rewards. Furthermore, our additional ablations show that removing the terminal term from the upper-level objective leads to only minor performance decreases (0.4 and 0.3 percentage points for the log-ratio and linear parameterizations, respectively). These results indicate that BARS does not rely on the outcome term to achieve its performance gains. Please refer to our response to Weakness 1 for the mathematical derivations and detailed results.
Question 2: Is the same model as the lower-level policy, a separate reward model, or a frozen reference? How is trained in the practical algorithm?
Answer: We clarify that BARS involves three distinct models: the reward model , the lower-level policy , and the reference model , each with its own parameters. Specifically, parameterizes the learned shaping reward, is the policy optimized under this reward, and is a frozen reference model. Importantly, is not directly parameterized by ; it has its own trainable parameters, and the notation emphasizes its implicit dependency on through lower-level policy optimization.
All three models share the same architecture and are initialized from the same pretrained checkpoint. For example, in the Qwen2.5-3B experiments, all three are initialized from Qwen2.5-3B, with the reward parameterized as
During training, is updated by minimizing the upper-level CE/DPO objective using the approximated hypergradient, while the lower-level policy is separately updated using GRPO/PPO/RLOO. The reference model remains frozen throughout training.
Question 3: How are the correction terms estimated in practice? What is the additional compute and memory cost relative to PRIME/iStar?
Answer: Thank you for this question. The original paper includes the answer in the appendix.
Correction-term estimation. As detailed in Appendix C in the original version (i.e., Appendix D in the newly uploaded version),
the exact correction terms involve conditional expectations of cumulative future reward gradients from intermediate states. Directly estimating these expectations would require additional trajectory rollouts from intermediate states, incurring substantial computational cost. Instead, our practical implementation approximates these expectations using the trajectories already generated from each initial prompt. Specifically, we use the remaining reward gradients along each sampled trajectory to approximate the state-action-conditioned term, and average the corresponding gradients across the trajectories to approximate the state-conditioned term. The DPO correction terms are estimated similarly using successful and unsuccessful trajectories. Consequently, BARS reuses the same rollout data for policy updates and reward learning, without requiring additional environment interactions.
Computational overhead. As reported in Table 5 of Appendix D.2 in the original submission (Appendix E.2 in the newly uploaded version), under identical training configurations (Qwen2.5-3B, NQ-Search, GRPO, batch size 512, and 8 rollouts
per prompt), BARS requires 441 seconds per iteration and 76 GB of peak GPU memory, compared with 417 seconds and 77 GB for PRIME, and 429 seconds and 75 GB for iStar. This corresponds to only 5.8% and 2.8% additional runtime relative to PRIME and iStar, respectively, with comparable memory consumption.
The modest runtime overhead arises because policy rollouts dominate the computational cost of each iteration and are identical across methods under the same rollout budget. Thus, the additional computation of reward optimization in BARS introduces only a small overhead relative to the overall training cost. Regarding GPU memory, BARS does not introduce additional trainable models compared with PRIME and iStar, as all three methods use a policy model and a reward model with the same architecture. Furthermore, our implementation offloads inactive model parameters to the CPU, limiting the peak GPU memory required for reward optimization. Consequently, BARS achieves comparable peak GPU memory consumption.
Thank you for your constructive reviews. We believe that our discussion will lead to a better paper. We address your comments in a point-by-point manner, and we integrate the revisions in the newly uploaded version.
Weakness 1: The biggest problem is that the reward function leaks the answer. The final success signal is built directly into the turn-level reward formula. This means the trajectory score used in the upper-level training losses (CE and DPO) already contains the outcome label. Instead of learning a dense reward that genuinely explains success from intermediate steps, the model can just exploit the outcome term that's already baked into the score. This defeats the whole purpose of learning turn-level rewards from outcome feedback. It also makes the "linear reward model" ablation unfair unless they handle the outcome term the same way.
Answer: Thank you for this comment. We respectfully clarify that including the terminal success reward does not allow BARS to bypass learning meaningful dense rewards. The terminal reward is fixed and independent of the shaping parameters. Although it contributes to the trajectory score, it does not eliminate the optimization of the learned shaping component nor directly provide intermediate turn-level rewards. In this response, we will (1) clarify this mathematically, (2) discuss that this addition of outcome reward is standard in reward shaping literature, and (3) provide additional empirical comparisons.
1. Mathematical justification.
Recall that Eq. (3) defines rθ(st,at)=rsucc(st,at)+γ1−tlogπref(at∣st)πθ(at∣st).Here, rsucc is the fixed terminal reward, whereas hθ(st,at)≜γ1−tlogπref(at∣st)πθ(at∣st) is the learnable shaping reward. For a trajectory y=(y1,…,yT), let z=rsucc(x,y)∈0,1. The cumulative reward can be expressed as
Rθ(x,y)=∑t=1Tγt−1rθ(st,at)=γT−1z+Hθ(x,y),
where Hθ(x,y)≜∑t=1Tlogπref(at∣st)πθ(at∣st).
First, the terminal reward does not eliminate the learning signal. For the upper-level CE loss lce=−zlogσ(Rθ)−(1−z)log(1−σ(Rθ)), the gradient with respect to θ is
∇θℓce=[σ(γT−1z+Hθ)−z]∇θHθ.
Since z is independent of θ, the gradient acts entirely through the learned shaping component Hθ. For finite Rθ=γT−1z+Hθ, the coefficient σ(Rθ)−z is nonzero. Thus, whenever ∇θHθ=0, the CE objective continues to optimize the shaping component.
Similarly, for the DPO loss, let y+ and y− denote successful and unsuccessful trajectories, respectively, and define ΔHθ≜Hθ(x,y+)−Hθ(x,y−). We have ldpo=−logσ(γT−1+ΔHθ). Its gradient is ∇θℓdpo=−σ(−γT−1−ΔHθ)∇θΔHθ.
Therefore, the outcome reward contributes a fixed offset to the CE/DPO scores, but the optimization gradients continue to act on the learned shaping component.
Second, the terminal reward alone cannot minimize the upper-level losses. Both the CE and DPO losses have an infimum of zero. Consider the case where where the learned shaping component is zero Hθ(x,y)=0. The CE loss reduces to lce=−logσ(γT−1) when z=1 and lce=log2 when z=0, which is strictly positive in both cases. Likewise, when ΔHθ=0, the DPO loss becomes ldpo=−logσ(γT−1)>0. Therefore, the terminal reward alone does not attain the infimum of either loss. Further lossreduction can be achieved by optimizing the learned shaping component Hθ to increase the scores of successful trajectories and decrease those of unsuccessful ones. Hence, the terminal reward does not trivially solve the upper-level reward-learning problem.
Third, the dense intermediate rewards come exclusively from the learned shaping component. Since the success reward is terminal, rsucc(st,at)=0 for every t<T. Consequently, rθ(st,at)=hθ(st,at),t<T.
Thus, the terminal outcome is not directly assigned to intermediate turns. Their rewards are determined entirely by the learned log-ratio component, whose parameters are optimized using outcome supervision. Retaining the terminal reward therefore does not replace the learning of dense turn-level feedback.