acceptodds
Under review as a conference paper at ICLR 2027

Learning to Shape the Reward for Agentic Reinforcement Learning via Bilevel Optimization

Abstract

Reinforcement learning for agentic systems often relies on trajectory-level rewards, leading to poor credit assignment in multi-turn tasks. A common approach is to introduce turn-level rewards, such as heuristic signals, LLM judges, or learned rewards, to provide dense feedback. However, existing reward learning approaches typically optimize the reward based on trajectories generated by the current policy, while treating the trajectory distribution as independent of the learned reward. In reality, the learned reward determines how the policy is optimized, which in turn affects the trajectories generated by the policy. Ignoring this dependency results in an incomplete gradient for reward learning. This paper proposes Bilevel Agentic Reward Shaping (BARS), a framework that explicitly captures this reward-policy-trajectory dependency through bilevel optimization. The upper level learns a turn-level reward from outcome feedback, while the lower level optimizes the policy under the learned reward. We develop an efficient algorithm that alternates between reward learning and policy updates, and establish a convergence rate of . Empirical results demonstrate that BARS achieves higher accuracy and improved training stability compared with baseline methods.

Primary area:
reinforcement learning
Keywords:
Agentic reinforcement learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_rArwOpenReview ↗
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

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⁡πθ(at∣st)πref(at∣st)r_\theta(s_t,a_t)=r_{\text{succ}}(s_t,a_t)+\gamma^{1-t}\log\frac{\pi_\theta(a_t\mid s_t)}{\pi_{\text{ref}}(a_t\mid s_t)}.Here, rsuccr_{\text{succ}} is the fixed terminal reward, whereas hθ(st,at)≜γ1−tlog⁡πθ(at∣st)πref(at∣st)h_\theta(s_t,a_t)\triangleq \gamma^{1-t}\log\frac{\pi_\theta(a_t\mid s_t)}{\pi_{\text{ref}}(a_t\mid s_t)} is the learnable shaping reward. For a trajectory y=(y1,…,yT)y=(y_1,\ldots,y_T), let z=rsucc(x,y)∈0,1z=r_{\text{succ}}(x,y)\in\\{0,1\\}. The cumulative reward can be expressed as

Rθ(x,y)=∑t=1Tγt−1rθ(st,at)=γT−1z+Hθ(x,y),R_\theta(x,y)=\sum_{t=1}^{T}\gamma^{t-1}r_\theta(s_t,a_t)=\gamma^{T-1}z+H_\theta(x,y),

where Hθ(x,y)≜∑t=1Tlog⁡πθ(at∣st)πref(at∣st).H_\theta(x,y)\triangleq\sum_{t=1}^{T}\log\frac{\pi_\theta(a_t\mid s_t)}{\pi_{\text{ref}}(a_t\mid s_t)}.

First, the terminal reward does not eliminate the learning signal. For the upper-level CE loss lce=−zlog⁡σ(Rθ)−(1−z)log⁡(1−σ(Rθ))l_{\text{ce}}=-z\log\sigma(R_\theta)-(1-z)\log(1-\sigma(R_\theta)), the gradient with respect to θ\theta is

∇θℓce=[σ(γT−1z+Hθ)−z]∇θHθ.\nabla_\theta\ell_{\text{ce}}=\left[\sigma(\gamma^{T-1}z+H_\theta)-z\right]\nabla_\theta H_\theta.

Since zz is independent of θ\theta, the gradient acts entirely through the learned shaping component HθH_\theta. For finite Rθ=γT−1z+HθR_\theta=\gamma^{T-1}z+H_\theta, the coefficient σ(Rθ)−z\sigma(R_\theta)-z is nonzero. Thus, whenever ∇θHθ≠0\nabla_\theta H_\theta\neq 0, the CE objective continues to optimize the shaping component.
Similarly, for the DPO loss, let y+y^+ and y−y^- denote successful and unsuccessful trajectories, respectively, and define ΔHθ≜Hθ(x,y+)−Hθ(x,y−)\Delta H_\theta\triangleq H_\theta(x,y^+)-H_\theta(x,y^-). We have ldpo=−log⁡σ(γT−1+ΔHθ)l_{\text{dpo}}=-\log\sigma\left(\gamma^{T-1}+\Delta H_\theta\right). Its gradient is ∇θℓdpo=−σ(−γT−1−ΔHθ)∇θΔHθ.\nabla_\theta\ell_{\text{dpo}}=-\sigma\left(-\gamma^{T-1}-\Delta H_\theta\right)\nabla_\theta\Delta H_\theta.

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)=0H_\theta(x,y)=0. The CE loss reduces to lce=−log⁡σ(γT−1)l_{\text{ce}}=-\log\sigma(\gamma^{T-1}) when z=1z=1 and lce=log⁡2l_{\text{ce}}=\log2 when z=0z=0, which is strictly positive in both cases. Likewise, when ΔHθ=0\Delta H_\theta=0, the DPO loss becomes ldpo=−log⁡σ(γT−1)>0l_{\text{dpo}}=-\log\sigma(\gamma^{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θH_\theta 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)=0r_{\text{succ}}(s_t,a_t)=0 for every t<Tt<T. Consequently, rθ(st,at)=hθ(st,at),t<T.r_\theta(s_t,a_t)=h_\theta(s_t,a_t),\qquad 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.

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 r(s,a)+rθ(s,a)r(s,a)+r_\theta(s,a) where rr is the original task reward and rθr_\theta 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 parameterizationOutcome term includedSuccess 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 rθ(x,y)r_\theta(x,y) include the terminal success term rsucc(x,y)r_\text{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.
Answer: Yes, rθ(x,y)r_\theta(x,y) 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 πθ\pi_\theta the same model as the lower-level policy, a separate reward model, or a frozen reference? How is θ\theta trained in the practical algorithm?
Answer: We clarify that BARS involves three distinct models: the reward model πθ\pi_\theta, the lower-level policy πrθ\pi_{r_\theta}, and the reference model πref\pi_{\text{ref}}, each with its own parameters. Specifically, πθ\pi_\theta parameterizes the learned shaping reward, πrθ\pi_{r_\theta} is the policy optimized under this reward, and πref\pi_{\text{ref}} is a frozen reference model. Importantly, πrθ\pi_{r_\theta} is not directly parameterized by θ\theta; it has its own trainable parameters, and the notation πrθ\pi_{r_\theta} emphasizes its implicit dependency on θ\theta 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 rθ(st,at)=rsucc(st,at)+γ1−tlog⁡πθ(at∣st)πref(at∣st).r_\theta(s_t,a_t)=r_{\text{succ}}(s_t,a_t)+\gamma^{1-t}\log\frac{\pi_\theta(a_t\mid s_t)}{\pi_{\text{ref}}(a_t\mid s_t)}. During training, θ\theta 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 mm 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 mm 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.

Reviewer_Go5wOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Bilevel Agentic Reward Shaping (BARS) for learning dense turn-level rewards from sparse outcome feedback in agentic reinforcement learning. BARS formulates reward learning as a bilevel optimization problem: the lower level optimizes the policy under the learned reward, while the upper level updates the reward using outcome feedback, explicitly accounting for the reward-policy-trajectory dependency through a hypergradient. The paper analyzes an idealized BARS algorithm based on soft policy iteration and establishes a sublinear convergence guarantee under regularity conditions. The practical algorithm uses standard RL optimizers and an approximate hypergradient. Experiments on NQ-Search and NQ-HotpotQA with Qwen2.5-3B and Llama3.1-8B show improvements over the considered baselines, alongside analyses of training stability, compatibility with different RL methods, and sensitivity to design choices.

Critical strengths
  • The paper addresses an important and practically relevant problem: improving learning efficiency in agentic RL under sparse outcome feedback.
  • The bilevel formulation is intuitive and clearly exposes the dependency between learned rewards, policy optimization, and the resulting trajectory distribution.
  • The paper is well written and technically rigorous, including theoretical analysis of an idealized version of BARS.
  • The experimental setup is clear and goes beyond final performance by examining training stability, compatibility across RL methods, and sensitivity to key design choices.
Critical weaknesses

My main concern is that the paper does not sufficiently discuss closely related work on bilevel reward shaping and learned intrinsic rewards in RL, including:

  • Sorg et al., Reward Design via Online Gradient Ascent, NeurIPS 2010.
  • Zheng et al., On Learning Intrinsic Rewards for Policy Gradient Methods (LIRPG), NeurIPS 2018.
  • Hu et al., Learning to Utilize Shaping Rewards: A New Approach of Reward Shaping (BiPaRS), NeurIPS 2020.
  • Memarian et al., Self-Supervised Online Reward Shaping in Sparse-Reward Environments (SORS), IROS 2021.
  • Devidze et al., Exploration-Guided Reward Shaping for Reinforcement Learning under Sparse Rewards (ExploRS), NeurIPS 2022.

This omission is important for assessing novelty. In particular, LIRPG, BiPaRS, and ExploRS already study learning reward/shaping functions by differentiating through policy optimization. Thus, the bilevel formulation and hypergradient-based reward optimization in BARS appear closely related to existing methodology. The main distinction seems to be the particular outer objective and its application to agentic LLM training. This distinction should be articulated much more precisely. For example, BiPaRS and ExploRS use expected return under the original/task reward as the outer objective; it is unclear how fundamentally this differs from the outcome-based objective used here. ExploRS also considers approximate hypergradient estimation, which warrants a direct comparison with the approximation proposed in BARS. Similarly, the LDPOL_{\mathrm{DPO}} objective appears related to the reward-shaping perspective of SORS.

Consequently, I find the methodological novelty somewhat limited in its current presentation. I view the contribution primarily as an adaptation and practical instantiation of bilevel reward shaping for modern agentic LLM RL, together with theoretical and empirical analysis, rather than a fundamentally new bilevel reward-learning principle. The paper would benefit from clearly delineating what is technically new relative to these prior methods.

The experimental evaluation also lacks comparisons against these closely related approaches. LIRPG, BiPaRS, and/or ExploRS appear sufficiently general that they could potentially be adapted to the agentic RL setting. Such comparisons would help establish whether the gains arise from specific innovations in BARS rather than from applying bilevel reward shaping to this setting. If these methods are impractical at LLM scale, the paper should explain the concrete computational or algorithmic limitations.

Questions for authors

How does BARS differ mathematically from LIRPG, BiPaRS, and ExploRS beyond the choice of outer objective and application to agentic RL? In particular, how does the outcome-based outer objective differ conceptually from optimizing expected return under the original/task reward?

ExploRS also considers approximate hypergradient estimation. How does the approximation used by BARS differ from prior estimators, both algorithmically and computationally?

Can LIRPG, BiPaRS, or ExploRS be instantiated in the environments considered here? If so, comparisons would substantially strengthen the evaluation. If not, what specifically makes these approaches unsuitable or impractical for agentic LLM training?

Reward-model parameterization: Are the reward and policy represented by separate networks, or do they share parameters/a backbone? If separate, what is the architecture and capacity of the reward model, and does it use the same base-model initialization as the policy?

Computational cost: What additional training-time and memory overhead does BARS introduce relative to the corresponding RL baseline when accounting for reward optimization and hypergradient estimation?

6 comments

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: Methodology novelty and comparison to previous methods.
Answer: Thank you for highlighting these important related works. The fundamental distinction of our method (BARS) lies in how it characterizes the reward–policy dependency. This fundamental distinction leads to differences in problem formulation, hypergradient derivation, and theoretical analysis. While prior studies have also explored bilevel reward shaping and meta-gradient optimization, BARS has a different bilevel formulation and hypergradient derivation to capture the different reward-policy dependency. We have revised Appendix A in the newly uploaded version to discuss these references and clarify our methodological contributions. We elaborate on these distinctions below.
1. Distinctions in problem formulation and characterization of the reward–policy dependency.
The cited references can be broadly categorized into two groups:

  • PGRD ("Reward Design via Online Gradient Ascent") and SORS do not explicitly capture the reward-policy dependency and do not formulate reward learning as bilevel optimization. PGRD optimizes reward parameters through their influence on a bounded planning agent, while SORS learns dense rewards from trajectory rankings without differentiating through policy optimization.

  • LIRPG, BiPaRS, and ExploRS account for the reward–policy dependency through bilevel or meta-gradient-based optimization. LIRPG and ExploRS derive reward gradients using one-step policy-gradient updates or surrogate policy-learning operators. BiPaRS formulates a policy-optimization lower level but assumes access to predefined shaping rewards and employs explicit or iterative meta-gradient approximations.

Among these studies, LIRPG, BiPaRS, and ExploRS are particularly relevant because they account for the influence of shaping rewards on policy learning. The central distinction lies in how this reward–policy dependency is characterized.
Specifically, LIRPG and the surrogate formulation employed by ExploRS consider

max⁡θJext(w′(θ)),s.t.w′(θ)=w+η∇wJshaped(w,θ),\max_{\theta}\quad J_{\text{ext}}(w'(\theta)),\quad \text{s.t.}\quad w'(\theta)=w+\eta\nabla_wJ_{\text{shaped}}(w,\theta),

where ww denotes the policy parameters and θ\theta denotes the shaping-reward parameters. Thus, the reward–policy dependency is characterized through a particular policy-gradient update. In contrast, BARS considers

min⁡θLCE(θ,πrθ)+λLDPO(θ,πrθ),s.t.πrθ∗=arg⁡max⁡πJKL(π,rθ),\min_{\theta}\quad\mathcal L_{\text{CE}}(\theta,\pi_{r_\theta}^{})+\lambda\mathcal L_{\text{DPO}}(\theta,\pi_{r_\theta}^{}),\quad\text{s.t.}\quad\pi_{r_\theta}^{*}=\arg\max_{\pi}J_{\text{KL}}(\pi,r_\theta), where JKLJ_{\text{KL}} denotes the KL-regularized expected shaped return.
The key distinction is that LIRPG and ExploRS characterize the effect of the shaping reward on a specified policy-update step, while BARS characterizes its effect on the optimal policy induced by that reward. Consequently, BARS captures the dependency of the lower-level optimal solution on the shaping reward, rather than only the local dependency induced by one policy-gradient step.
We acknowledge that BiPaRS also formulates its lower level as a policy optimization problem. However, its objective is to learn weights for predefined shaping signals, and its practical methods use explicit or iterative meta-gradient approximations. BARS instead directly learns a dense reward model and derives its sensitivity using the optimality structure of KL-regularized RL.
2. Distinctions in hypergradient analysis. The different characterizations of the reward–policy dependency in the lower-level formulations lead to different hypergradient derivations.
One-step meta-gradient methods (LIRPG and ExploRS). These approaches differentiate through a one-step policy-gradient update: Denoting the policy parameters by ww and the reward parameters by θ\theta, the policy update is w′(θ)=w+η∇wJshaped(w,θ).w'(\theta)=w+\eta\nabla_w J_{\text{shaped}}(w,\theta). The upper-level gradient is then computed using the chain rule:

∇θJext(w′(θ))=(∂w′∂θ)⊤∇w′Jext(w′)ηˉ∇θw2Jshaped(w,θ)∇w′Jext(w′).\nabla_\theta J_{\text{ext}}(w'(\theta))=\left(\frac{\partial w'}{\partial\theta}\right)^\top\nabla_{w'}J_{\text{ext}}(w')\=\eta\nabla_{\theta w}^{2}J_{\text{shaped}}(w,\theta)\nabla_{w'}J_{\text{ext}}(w').

Therefore, the reward–policy dependency is captured through the sensitivity of a single policy-gradient update ∂w′/∂θ\partial w'/\partial\theta.

BARS: implicit differentiation of the optimal policy. In contrast, BARS formulates the lower level as a KL-regularized RL optimization problem: arg⁡max⁡πJKL(π,rθ)\arg\max_\pi J_{\text{KL}}(\pi,r_\theta). The optimal policy π∗\pi^{*} satisfies the first-order optimality condition ∇πJKL(π∗,rθ)=0\nabla_\pi J_{\text{KL}}(\pi^{*},r_\theta)=0. Applying the implicit function theorem yields ∂π∗∂θ=−[∇ππ2JKL]−1∇πθ2JKL\frac{\partial \pi^{*}}{\partial \theta}=-\left[\nabla_{\pi\pi}^{2}J_{\text{KL}}\right]^{-1}\nabla_{\pi\theta}^{2}J_{\text{KL}}, where the derivatives of JKLJ_{\text{KL}} are evaluated at (π∗,rθ)(\pi^{*},r_\theta). Consequently, the upper-level hypergradient is ∇θL(θ,πrθ)=∇θL(θ,πrθ)−∇θπ2JKL[∇ππ2JKL]−1∇πL(θ,πrθ).\nabla_\theta\mathcal L(\theta,\pi_{r_\theta})=\nabla_\theta\mathcal L(\theta,\pi_{r_\theta})-\nabla_{\theta\pi}^{2}J_{\text{KL}}\left[\nabla_{\pi\pi}^{2}J_{\text{KL}}\right]^{-1}\nabla_\pi\mathcal L(\theta,\pi_{r_\theta}^{}).

The first term captures the direct dependency of the upper-level objective on the shaping reward, while the second term captures its indirect dependency through the optimal policy. Unlike one-step meta-gradients, the indirect term characterizes the sensitivity of the lower-level optimal solution rather than that of a single policy update. Although the general implicit-differentiation expression involves the inverse policy Hessian [∇ππ2JKL]−1[\nabla_{\pi\pi}^{2}J_{\text{KL}}]^{-1}, BARS avoids explicitly computing it by exploiting the structure of KL-regularized RL and derive the hypergradient without the Hessian term in Lemma 1 and Lemma 2.
Therefore, the central algorithmic distinction is that LIRPG and ExploRS derive reward gradients from one-step policy-update sensitivity, whereas BARS derives the sensitivity of the optimal-policy solution and exploits KL-regularized RL to compute hypergradient efficiently.
3. Distinctions in theoretical guarantees. Among the cited methods, PGRD establishes a convergence guarantee for online reward-parameter optimization through a single-level optimization, while LIRPG, BiPaRS, SORS, and ExploRS do not provide comparable convergence guarantees for their reward-learning algorithms. In contrast, BARS establishes convergence guarantees for the coupled reward-learning and policy-optimization process. Since BARS characterizes the reward–policy dependency through the lower-level optimal solution but performs only one soft-policy-iteration update per iteration, our analysis explicitly accounts for the discrepancy between the iteratively updated policy and the induced optimal policy.
4. Additional empirical comparison. We agree that comparison against prior bilevel reward-shaping approaches would strengthen the evaluation. Given the limited computational resources and rebuttal period, we additionally adapt LIRPG to the agentic RL setting and evaluate it using Qwen2.5-3B on NQ-Search with GRPO.
For a controlled comparison, we employ the same reward parameterization and base-model initialization as BARS, while replacing the reward-update mechanism with an adapted one-step LIRPG meta-gradient. We use the same training data, rollout budget, and policy-training configuration.

MethodSuccess Rate (%)
LIRPG44.6
BARS47.8

As shown in the above table, BARS achieves a success rate of 47.847.8\\%, outperforming the adapted LIRPG baseline 44.644.6\\% by 3.23.2 percentage points. This result provides additional empirical support for the effectiveness of BARS's reward-learning approach compared with one-step meta-gradient optimization.

Question 1: How does BARS differ mathematically from LIRPG, BiPaRS, and ExploRS beyond the choice of outer objective and application to agentic RL? In particular, how does the outcome-based outer objective differ conceptually from optimizing expected return under the original/task reward?
Answer: The main methodological distinction lies in how BARS formulates and differentiates the reward–policy dependency. Specifically, while LIRPG and ExploRS derive reward gradients through one-step policy-gradient updates or surrogate policy-learning operators, BARS models the induced policy as the optimal solution of a KL-regularized lower-level optimization problem. This leads to a different hypergradient derivation based on implicit differentiation of the optimal-policy solution, rather than differentiation through a prescribed policy-update step. We also clarify the relationship to BiPaRS, which formulates an optimal-policy lower level but learns weights for predefined shaping rewards. The outcome-alignment objective is not the major distinction. Please refer to our response to the Weaknesses for the detailed mathematical formulations and comparisons.

Question 2: ExploRS also considers approximate hypergradient estimation. How does the approximation used by BARS differ from prior estimators, both algorithmically and computationally?
Answer: Algorithmically, the key difference lies in the underlying policy-sensitivity derivation. ExploRS derives its estimator from a one-step surrogate policy-gradient update, whereas BARS derives the sensitivity of the KL-regularized optimal policy through implicit differentiation. Please refer to our response to the Weakness for the algorithmic distinction.
Computationally, both ExploRS and BARS reuse collected trajectories and require reward-model gradient computations, without additional environment rollouts or explicit policy-Hessian inversion. However, their additional computational requirements differ.
ExploRS estimates its intrinsic-reward gradient using an extrinsic-advantage-weighted term of the form

(GR(ξt)−VRπ(st))∇θ[Rθ(st,at)−Ea∼π(⋅∣st)Rθ(st,a)],\left(G_R(\xi_t)-V_R^\pi(s_t)\right)\nabla_\theta\left[R_\theta(s_t,a_t)-\mathbb E_{a\sim\pi(\cdot\mid s_t)}R_\theta(s_t,a)\right],

where ξt\xi_t denotes the trajectory suffix starting from state sts_t, GR(ξt)G_R(\xi_t) is its cumulative extrinsic return, VRπ(st)V_R^\pi(s_t) is the extrinsic state-value function, and RθR_\theta is the learned intrinsic reward parameterized by θ\theta. The original ExploRS implementation trains an auxiliary critic to estimate VRπ(st)V_R^\pi(s_t), introducing additional training and memory overhead. Its full algorithm also maintains exploration bonuses and visitation statistics.
BARS does not require an auxiliary critic or exploration-bonus estimation. Instead, its additional computations involve CE/DPO outcome-alignment losses and trajectory-based sensitivity corrections constructed from cumulative shaping-reward gradients. These corrections are estimated using existing rollout batches without explicitly evaluating alternative actions at intermediate states. This difference makes BARS naturally compatible with critic-free agentic RL optimizers such as GRPO.

Question 3: Can LIRPG, BiPaRS, or ExploRS be instantiated in the environments considered here? If so, comparisons would substantially strengthen the evaluation. If not, what specifically makes these approaches unsuitable or impractical for agentic LLM training?
Answer: BiPaRS cannot be directly applied to our setting because it requires a predefined, manually designed shaping signal, whereas our goal is to learn dense rewards solely from sparse outcome feedback. In contrast, LIRPG and ExploRS can be adapted to our setting, as both learn intrinsic rewards and derive meta-gradients through one-step policy-gradient-based surrogates. We implement LIRPG as a representative baseline using Qwen2.5-3B on NQ-Search with GRPO. Please refer to our response to the Weakness for experimental details.

Question 4: Reward-model parameterization: Are the reward and policy represented by separate networks, or do they share parameters/a backbone? If separate, what is the architecture and capacity of the reward model, and does it use the same base-model initialization as the policy?
Answer: The reward model and policy model are separate networks with independent parameters, but they are all initialized from the same pretrained base model. Specifically, our turn-level reward is parameterized as rsucc(st,at)+γ1−tlog⁡πθ(at∣st)πref(at∣st)r_{\text{succ}}(s_t,a_t)+\gamma^{1-t}\log\frac{\pi_\theta(a_t\mid s_t)}{\pi_{\text{ref}}(a_t\mid s_t)}, where πθ\pi_\theta is the trainable reward model and πref\pi_{\text{ref}} is the fixed reference model. For example, in the Qwen2.5-3B experiments, πθ\pi_\theta, πref\pi_{\text{ref}}, and the policy model are all initialized from the same pretrained Qwen2.5-3B checkpoint. During training, the reward and policy models are updated independently, while the reference model remains frozen.

Reviewer_vxJmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes BARS, a bilevel method for learning rewards in agentic reinforcement learning. The upper level learns rewards from task outcomes. The lower level uses these rewards to train the policy.The method also adds an indirect gradient term to consider how rewards affect the policy and trajectory distribution. The main experiments show that this method improves performance on search tasks.

Critical strengths

The paper studies the relationship between reward models, policy optimization, and trajectory distribution. The idea is reasonable. The experiments use different language models, RL algorithms, and environments. The ablation results also show that adding the gradient correction term improves model performance and makes training more stable.

Critical weaknesses

The paper states that the convergence guarantee does not directly apply to the actual algorithm. However, it mainly uses hypergradient theory to explain the performance gains. The ablation results show that the indirect gradient term helps improve performance. But they do not show how close the computed gradients are to the theoretical ones. I think the paper should better explain the link between the theory and the actual algorithm.

Some baseline methods show large performance drops during training. The tables report their best results before these drops. However, the paper does not clearly explain how these results were selected. It is also unclear whether all methods used the same tuning process. The paper should explain the comparison setup more clearly to make the results more convincing.

Some inequalities in the convergence proof are not well justified. The paper directly uses the difference between two expectations without loss weights to bound the difference with loss weights. However, these weights may affect the results for different samples. I think a bounded loss function alone is not enough to support this step. The paper should provide a more complete proof.

Questions for authors
  1. Can the authors further clarify the relationship between the theoretical hypergradient and the gradient used in actual training?
  2. How were the best results in Table 1 selected? Were the same hyperparameter tuning standards used for all methods?
  3. Can the authors further justify the inequalities used in the convergence proof and explain whether the claimed convergence rate still holds?
5 comments

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 (highlighted in blue) in the newly uploaded version.

Weakness 1: The paper states that the convergence guarantee does not directly apply to the actual algorithm. However, it mainly uses hypergradient theory to explain the performance gains. The ablation results show that the indirect gradient term helps improve performance. But they do not show how close the computed gradients are to the theoretical ones. I think the paper should better explain the link between the theory and the actual algorithm.
Answer: Thank you for this important comment. We have revised Appendix D in the newly uploaded version to include the mathematical bound and empirical measurement of the discrepancy between the theoretical gradient and the empirical approximation. In this response, we will first introduce what the approximation is, and then mathematically bound the approximation discrepancy. Finally, we provide an empirical measurement of the approximation discrepancy.
Theoretical and practical hypergradients. Recall that the hypergradient consists of a direct term and an indirect term. Our practical implementation preserves the direct term and only approximates the indirect term. To clarify the approximation, we take the CE hypergradient in Lemma 1 as an example: gce(θk)=1Bm∑n=1B∑j=1m[∇θlce(θk;(x(n),y(n,j)))+lce(θk;(x(n),y(n,j)))Δce(n,j,k)].g_{\text{ce}}(\theta_k)=\frac{1}{Bm}\sum_{n=1}^{B}\sum_{j=1}^{m}\Big[\nabla_\theta l_{\text{ce}}(\theta_k;(x^{(n)},y^{(n,j)}))+l_{\text{ce}}(\theta_k;(x^{(n)},y^{(n,j)}))\Delta_{\text{ce}}^{(n,j,k)}\Big]. where the first term is the direct gradient and Δce(n,j,k)\Delta_{\text{ce}}^{(n,j,k)} is the indirect correction. For simplicity, define the cumulative reward gradient from turn tt as Ht(y)≜∑i=tTγi−t∇θrθk(si,ai).H_t(y)\triangleq\sum_{i=t}^{T}\gamma^{i-t}\nabla_\theta r_{\theta_k}(s_i,a_i). According to Lemma 1, the theoretical indirect correction is Δce(n,j,k)=1β∑t=1T[Eπk[Ht(Y)∣St=st(n,j),At=at(n,j)]−Eπk[Ht(Y)∣St=st(n,j)]]\Delta_{\text{ce}}^{(n,j,k)}=\frac{1}{\beta}\sum_{t=1}^{T}\Big[\mathbb E^{\pi_k}[H_t(Y)\mid S_t=s_t^{(n,j)},A_t=a_t^{(n,j)}]-\mathbb E^{\pi_k}[H_t(Y)\mid S_t=s_t^{(n,j)}]\Big] To compute the two conditional expectations in Δce(n,j,k)\Delta_{\text{ce}}^{(n,j,k)} accurately, we would need to generate additional trajectory continuations from each intermediate state-action pair (st(n,j),at(n,j))(s_t^{(n,j)},a_t^{(n,j)}). However, this requires additional rollouts at every intermediate turn, resulting in substantial computational overhead.
To avoid this overhead, our practical implementation borrows the approximation idea from GRPO [A1] and reuses the mm trajectories already generated from the same initial prompt x(n)x^{(n)}. Specifically, we approximate the two conditional expectations in Δce(n,j,k)\Delta_{\text{ce}}^{(n,j,k)} as \begin{align*} &\mathbb E^{\pi_k} [H_t(Y)\mid S_t=s_t^{(n,j)},A_t=a_t^{(n,j)}] \approx H_t(y^{(n,j)}), \ &\mathbb E^{\pi_k} [H_t(Y)\mid S_t=s_t^{(n,j)}] \approx \frac{1}{m} \sum_{j'=1}^{m}H_t(y^{(n,j')}). \end{align*} Substituting these approximations into Δce(n,j,k)\Delta_{\text{ce}}^{(n,j,k)}, we obtain the practical indirect correction Δ^ce(n,j,k)=1β∑t=1T[Ht(y(n,j))−1m∑j′=1mHt(y(n,j′))].\widehat\Delta_{\text{ce}}^{(n,j,k)}=\frac{1}{\beta}\sum_{t=1}^{T}\left[H_t(y^{(n,j)})-\frac{1}{m}\sum_{j'=1}^{m}H_t(y^{(n,j')})\right]. The approximation error arises from Δ^ce(n,j,k)\widehat\Delta_{\text{ce}}^{(n,j,k)}. Although the mm trajectories share the same initial prompt, they may reach different intermediate states due to previous actions and environment feedback. Consequently, their trajectory suffixes are not necessarily sampled from the desired state-conditioned distribution.
Approximation error analysis. We now characterize the discrepancy between the theoretical and practical hypergradients. For each sampled trajectory, define ϵce(n,j,k)≜∥Δce(n,j,k)−Δ^ce(n,j,k)∥.\epsilon_{\text{ce}}^{(n,j,k)}\triangleq\left\|\Delta_{\text{ce}}^{(n,j,k)}-\widehat\Delta_{\text{ce}}^{(n,j,k)}\right\|. Since the direct terms remain unchanged, the hypergradient approximation error satisfies \begin{align*} |g_{\text{ce}}(\theta_k)-\widehat g_{\text{ce}}(\theta_k)|=\left|\frac{1}{Bm}\sum_{n=1}^{B}\sum_{j=1}^{m}l_{\text{ce}}(\theta_k;(x^{(n)},y^{(n,j)}))\left(\Delta_{\text{ce}}^{(n,j,k)}-\widehat\Delta_{\text{ce}}^{(n,j,k)}\right)\right|\leq\frac{1}{Bm}\sum_{n=1}^{B}\sum_{j=1}^{m}\left|l_{\text{ce}}(\theta_k;(x^{(n)},y^{(n,j)}))\right|\epsilon_{\text{ce}}^{(n,j,k)}. \end{align*} Under Assumption~1, ∣rθ(s,a)∣≤C~|r_\theta(s,a)|\leq\widetilde C. Therefore, defining Rmax⁡≜C~∑t=1Tγt−1,R_{\max}\triangleq\widetilde C\sum_{t=1}^{T}\gamma^{t-1}, the pointwise CE loss satisfies 0≤lce(θ;(x,y))≤Lce≜log⁡(1+exp⁡(Rmax⁡)).0\leq l_{\text{ce}}(\theta;(x,y))\leq L_{\text{ce}}\triangleq\log(1+\exp(R_{\max})). Let ϵˉce(k)≜1Bm∑n=1B∑j=1mϵce(n,j,k).\bar\epsilon_{\text{ce}}^{(k)}\triangleq\frac{1}{Bm}\sum_{n=1}^{B}\sum_{j=1}^{m}\epsilon_{\text{ce}}^{(n,j,k)}. We obtain ∥gce(θk)−g^ce(θk)∥≤Lceϵˉce(k).\|g_{\text{ce}}(\theta_k)-\widehat g_{\text{ce}}(\theta_k)\|\leq L_{\text{ce}}\bar\epsilon_{\text{ce}}^{(k)}.

Similarly, for the DPO hypergradient in Lemma 2, define the discrepancy for preference pair pp of prompt nn as ϵdpo(n,p,k)≜∥Δdpo(n,p,k)−Δ^dpo(n,p,k)∥.\epsilon_{\text{dpo}}^{(n,p,k)}\triangleq\left\|\Delta_{\text{dpo}}^{(n,p,k)}-\widehat\Delta_{\text{dpo}}^{(n,p,k)}\right\|. Let NnN_n denote the number of valid preference pairs for prompt nn, and define ϵˉdpo(k)≜1B∑n=1B1Nn>0max⁡Nn,1∑p=1Nnϵdpo(n,p,k).\bar\epsilon_{\text{dpo}}^{(k)}\triangleq\frac{1}{B}\sum_{n=1}^{B}\frac{\mathbf{1}\\{N_n>0\\}}{\max\\{N_n,1\\}}\sum_{p=1}^{N_n}\epsilon_{\text{dpo}}^{(n,p,k)}. Since the pointwise DPO loss satisfies 0≤ldpo(θ;(x,y+,y−))≤Ldpo≜log⁡(1+exp⁡(2Rmax⁡)),0\leq l_{\text{dpo}}(\theta;(x,y^+,y^-))\leq L_{\text{dpo}}\triangleq\log(1+\exp(2R_{\max})), the same argument gives ∥gdpo(θk)−g^dpo(θk)∥≤Ldpoϵˉdpo(k).\|g_{\text{dpo}}(\theta_k)-\widehat g_{\text{dpo}}(\theta_k)\|\leq L_{\text{dpo}}\bar\epsilon_{\text{dpo}}^{(k)}. Combining the CE and DPO results, we obtain ∥g(θk)−g^(θk)∥≤Lceϵˉce(k)+λLdpoϵˉdpo(k).\|g(\theta_k)-\widehat g(\theta_k)\|\leq L_{\text{ce}}\bar\epsilon_{\text{ce}}^{(k)}+\lambda L_{\text{dpo}}\bar\epsilon_{\text{dpo}}^{(k)}. The bound explicitly relates the hypergradient approximation error to the discrepancies introduced by the indirect corrections. The discrepancies of the indirect corrections depend on the current policy's stochasticity and the distributions of intermediate states and trajectory continuations, making their magnitudes difficult to characterize tightly in general. We therefore directly assess the approximation quality empirically through cosine similarity and relative gradient error against a caclculated theoretical hypergradient using additional conditional rollouts.
Empirical validation of hypergradient approximation. To evaluate the accuracy of the practical hypergradient approximation, we conduct additional experiments using Qwen2.5-3B with GRPO (as the base RL algorithm) on NQ-Search. We select three checkpoints at training iterations 50, 250, and 450, representing early, middle, and late training stages, respectively. At each checkpoint, we compute the theoretical hypergradient using 8 additional conditional rollouts at each intermediate state and denote the computed hypergradient by gindrefg_{\text{ind}}^{\text{ref}}. We compare gindrefg_{\text{ind}}^{\text{ref}} with the practical indirect gradient g^ind\widehat{g}_{\text{ind}}. We report cosine similarity (CosSim):

Training iterationCosSim
50 (Early)0.87
250 (Middle)0.91
450 (Late)0.94

The table above demonstrates high similarity between the calculated theoretical gradient and empirical approximation. Importantly, the table shows increasing similarity between the theoretical gradient and empirical approximation throughout training. One possible explanation is that policy becomes less random and thus produces more consistent trajectories over time, reducing discrepancies between intermediate states of different trajectories with the same prompt. Since the practical approximation uses trajectory suffixes originating from potentially different intermediate states to approximate state-conditioned expectations, increased trajectory consistency improves approximation accuracy.

Weakness 2: Some baseline methods show large performance drops during training. The tables report their best results before these drops. However, the paper does not clearly explain how these results were selected. It is also unclear whether all methods used the same tuning process. The paper should explain the comparison setup more clearly to make the results more convincing.
Answer: Thank you for raising this concern. We clarify the checkpoint selection and hyperparameter tuning protocols to demonstrate the fairness of our experimental comparisons. We include the revision in Appendix E in the newly uploaded version.
Checkpoint selection. All methods are trained for 450 iterations, with checkpoints evaluated every 50 iterations. We adopt a consistent checkpoint-selection criterion across all methods: for methods that do not experience training collapse, we report the performance at the final checkpoint (iteration 450); for methods that experience training collapse, we report their best observed test performance before collapse. As shown in Figure 2 and Appendix E.1 in the newly uploaded version, BARS maintains stable performance throughout training without experiencing collapse, and therefore its final-checkpoint performance is reported. This criterion is deliberately favorable to baselines that experience collapse, as it allows them to be evaluated at their peak observed performance rather than their substantially degraded final performance. Consequently, BARS outperforms these baselines even when their best observed performance is considered, demonstrating that its advantage does not arise from penalizing unstable baselines.

Hyperparameter tuning. We use a consistent hyperparameter tuning protocol across all methods. All methods share the same training datasets, base models, RL optimizers, batch size of 512, rollout number of 8, and maximum training budget of 450 iterations. For the optimization-sensitive hyperparameters, we consider the same candidate sets whenever applicable. Specifically, the policy learning rate is selected from 5×10−7,10−6,2×10−6\\{5\times10^{-7},10^{-6},2\times10^{-6}\\}, and the KL regularization coefficient is selected from 0.001,0.005,0.010\\{0.001,0.005,0.010\\}. For reward-learning methods (PRIME, iStar, and BARS), the reward-model learning rate is selected from 5×10−7,10−6,2×10−6\\{5\times10^{-7},10^{-6},2\times10^{-6}\\}. We select the configuration with the highest training accuracy.

Weakness 3: Some inequalities in the convergence proof are not well justified. The paper directly uses the difference between two expectations without loss weights to bound the difference with loss weights. However, these weights may affect the results for different samples. I think a bounded loss function alone is not enough to support this step. The paper should provide a more complete proof.
Answer: Thank you for this comment. The O(1/K)O(1/\sqrt{K}) convergence rate in Theorem 1 still holds. The key is to bound these differences directly through the discrepancy between the trajectory distributions induced by the current policy and the optimal lower-level policy. Specifically, the original proof uses the boundedness of the CE and DPO losses to separate their weights from differences of expectations. As the reviewer correctly observes, this step is not generally valid because the loss depends on the sampled trajectories. We replace it with a distribution-based bound that retains these trajectory-dependent weights.
Taking the CE loss as an example, let Pk(⋅∣x)P_k(\cdot|x) and Pk∗(⋅∣x)P_k^*(\cdot|x) denote the trajectory distributions induced by πk\pi_k and πrθk\pi_{r_{\theta_k}}, respectively. Define hk(x,y)≜∇θlog⁡πrθ(y∣x)∣θ=θkh_k(x,y)\triangleq \left.\nabla_\theta \log\pi_{r_\theta}(y|x)\right|_{\theta=\theta_k}. The term involving the trajectory-dependent CE loss can be bounded directly as

D _k &\triangleq \Big\lVert \mathbb{E} _{x\sim\mathcal{D},y\sim P _k}[l _{\mathrm{ce}}(\theta _k;(x,y))h _k(x,y)]-\mathbb{E} _{x\sim\mathcal{D},y\sim P _k^{\ast}}[l _{\mathrm{ce}}(\theta _k;(x,y))h _k(x,y)]\Big\rVert \\\\ &=\Big\lVert \mathbb{E} _{x\sim\mathcal{D}}\sum _y(P _k(y|x)-P _k^{\ast}(y|x))l _{\mathrm{ce}}(\theta _k;(x,y))h _k(x,y)\Big\rVert \\\\ &\leq\mathbb{E} _{x\sim\mathcal{D}}\sum _y|P _k(y|x)-P _k^{\ast}(y|x)|\\,|l _{\mathrm{ce}}(\theta _k;(x,y))|\\,\lVert h _k(x,y)\rVert \\\\ &\leq\frac{2\log(1+e^{T\widetilde{C}})CT^2}{\beta}\mathbb{E} _{x\sim\mathcal{D}}\sum _y|P _k(y|x)-P _k^{\ast}(y|x)|. \end{aligned}$$ The last inequality follows from the bounded CE loss in Lemma 5 and $\|h_k(x,y)\|\leq 2CT^2/\beta$ in Lemma 8. We next bound the trajectory-distribution difference. Since the two policies interact with the same environment transition kernel, a telescoping argument over the $T$ policy decisions gives $$\begin{aligned} &\sum _y|P _k(y|x)-P _k^{\ast}(y|x)| \\\\ &\leq \sum _{t=1}^{T}\sup _{s\in\mathcal S}\sum _{a\in\mathcal A}|\pi _k(a|s)-\pi _{r _{\theta _k}}(a|s)| \\\\ &\leq T\sum _{s\in\mathcal S}\sum _{a\in\mathcal A}|\pi _k(a|s)-\pi _{r _{\theta _k}}(a|s)| \\\\ &\leq T\sum _{s\in\mathcal S}\sum _{a\in\mathcal A}|\log\pi _k(a|s)-\log\pi _{r _{\theta _k}}(a|s)|. \end{aligned}$$ where the last inequality uses $|p-q|\leq|\log p-\log q|$ for $p,q\in(0,1]$. Therefore, we obtain $$D_k\leq\frac{2L_{\text{ce}}CT^3}{\beta}\sum_{s\in\mathcal S}\sum_{a\in\mathcal A}|\log\pi_k(a|s)-\log\pi_{r_{\theta_k}}(a|s)|.$$ **Preservation of the convergence order.** We next show that $\frac{1}{K}\sum_{k=0}^{K-1}D_k$ preserves the convergence rate of $O(1/\sqrt{K})$. For any $(s,a)$ and $k\geq1$, the triangle inequality gives $$|\log\pi_k(a|s)-\log\pi_{r_{\theta_k}}(a|s)|\leq|\log\pi_k(a|s)-\log\pi_{r_{\theta_{k-1}}}(a|s)|+|\log\pi_{r_{\theta_{k-1}}}(a|s)-\log\pi_{r_{\theta_k}}(a|s)|.$$ The first term is controlled by the lower-level tracking analysis in Appendix B.4, which establishes $$\frac{1}{K}\sum_{k=0}^{K-1}|\log\pi_{k+1}(a|s)-\log\pi_{r_{\theta_k}}(a|s)|=O(1/\sqrt{K}).$$ For the second term, Claim 4 establishes the sensitivity of the optimal action-value function to the reward parameters: $$\|Q_{r_{\theta_1}}^{*}-Q_{r_{\theta_2}}^{*}\|_\infty\leq CT\|\theta_1-\theta_2\|.$$ Recall that the soft-policy representation is, $$\log\pi_{r_\theta}(a|s)=\log\pi_{\text{ref}}(a|s)+\frac{Q_{r_\theta}^{*}(s,a)}{\beta}-\log Z_\theta(s),$$ where $$Z_\theta(s)=\sum_{a'\in\mathcal A}\pi_{\text{ref}}(a'|s)\exp\left(\frac{Q_{r_\theta}^*(s,a')}{\beta}\right).$$ Since the log-sum-exp function is $1$-Lipschitz with respect to the $\ell_\infty$ norm, we have that

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.