acceptodds
Under review as a conference paper at ICLR 2027

Follow the Improvement: Guaranteed Policy Optimization by Tracking Proximal Ascent Targets

Abstract

Modern policy optimization approaches are mainly built on two theoretical paradigms: constrained optimization and tracking a target policy. Constrained methods (PPO, TRPO) maximize a surrogate objective within a trust region, but their monotonic improvement guarantees hold only for an idealized procedure, not for its practical implementation. Target-tracking methods (SAC, AWR, MPO) construct a target with improved performance and approach it by minimizing a regression loss; a small tracking loss however does not guarantee improvement. We propose *Follow-the-Improvement RL (FIRL)*, a framework that *unifies* these two main classes of policy optimization paradigms. First, FIRL defines a general proximal ascent target, , where aligns with the improvement direction and has constrained scale. Second, FIRL characterizes a class of *tracking loss functions* that can bound the performance gap between policies. Then we show that, with a constrained step size, minimizing idealized tracking losses toward the target , evaluated under the data distribution from , is sufficient to *guarantee performance improvement* over . The framework unifies PPO, SPO, and on-policy variants of AWR and MPO, while identifying *new promising instances* motivated by the theory: a clipped-linear target paired with advantage-weighted total variation/hinge (ATV/AH) losses. Across MuJoCo, IsaacLab, Atari, and LLM fine-tuning on mathematical reasoning, we evaluate different design combinations, show that the proposed instances perform competitively, and identify more effective target–loss combinations for each task category.

Primary area:
reinforcement learning
Keywords:
Deep reinforcement learning, Policy optimization, Policy improvement guarantees, Robotics

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_a9iLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Follow-the-Improvement RL (FIRL), a framework that decomposes on-policy policy optimization into two design choices.

  1. Proximal ascent target. The target is a multiplicative tilt of the behavior policy, π* = (1 + εg)π₀. The direction g is required to be centered, to have bounded second moment (E_{π₀}[g²] ≤ 1), to be aligned with the advantage, and to keep the target non-negative.
  2. Certified tracking loss. The tracking loss L(π*, π_θ) must upper-bound the performance gap between π* and π_θ. Candidates include hinge, TV, χ²/MSE and KL, and advantage-weighted versions of the first three.

Under the step-size condition γ(1+ε²) < 1, the improvement η(π_θ) − η(π₀) is lower-bounded by the analytic gain of the target minus a monotone function of the tracking loss. This loss is evaluated under the behavior state distribution d_{π₀}. The transfer from d_{π*} to d_{π₀} goes through a χ² bound on occupancy measures (Lemma 5) combined with the Hammersley–Chapman–Robbins inequality. A finite-horizon variant without the step-size condition is also given.

Under this view, PPO/GRPO (sign target + advantage-weighted hinge), SPO (sign + weighted MSE), BPO (sign + weighted TV) and on-policy AWR/MPO (exponential target + KL) are recovered as instances. Motivated by a Cauchy–Schwarz argument and an ordering of loss tightness, the authors propose two new instances: a clipped, standardized-advantage target paired with advantage-weighted TV (CLinear_ATV) or advantage-weighted hinge (CLinear_AH).

These are evaluated on MuJoCo (3 tasks), IsaacLab (2), Atari (3) and LLM math fine-tuning (AIME/AMC). The paper reports that the clipped-linear target achieves the best average rank, and that the best loss is regime-dependent. Ablations cover the step size, the weight offset σ, normalization, centering and the loss type.

Critical strengths

1. A clean, useful unifying lens with a guarantee stated in terms of an on-distribution loss.

  • The "target × tracking loss" decomposition places PPO/GRPO, SPO, BPO and on-policy AWR/MPO in a single family. It also makes design choices orthogonal and testable.
  • The key technical step is Lemma 5: a χ²-divergence bound on discounted occupancies under a per-step χ² trust region, combined with an HCR change of measure.
  • This replaces unverifiable data-coverage assumptions with a checkable step-size condition. It also lets the bound be expressed through the loss that is actually minimized on behavior data.

2. Theory-driven design space with broad empirical coverage.

  • The analysis motivates concrete design choices: a clipped-linear target close to the Cauchy–Schwarz optimum, and the tightest certified losses (ATV/AH).
  • These are evaluated across quite different regimes, including large-scale IsaacLab and LLM fine-tuning, with targeted ablations (step size, normalization, loss type, centering).
Critical weaknesses

1. The guarantee does not cover the algorithm that is actually run. This is the same criticism the paper levels at TRPO/PPO.

Several conditions of Theorem 1 are violated or rendered vacuous in the reported experiments:

  • Weighted losses with σ = 0.
    • Certification of the weighted losses requires w ≥ |A_{π_θ}|.
    • Remark 1 shows that w = |A_{π₀}| + σ is certified only with C_L inflated by (1+γ)σ_V/σ. This factor diverges as σ → 0.
    • All benchmark experiments use σ = 0 (Section 4.3). For the headline methods CLinear_ATV and CLinear_AH, the certificate therefore does not hold as stated.
  • Step-size condition. Assumption 2 requires ε < √((1−γ)/γ). Many selected hyperparameters (Table 6) violate it:
    • Atari CLinear_ATV uses ε = 0.2 with γ = 0.99, where the bound is ≈ 0.1005.
    • Anymal CLinear_ATV uses ε = 0.2 with γ = 0.99.
    • Ant PPO uses ε = 0.2 and Exp uses ε = 0.3, both with γ = 0.99.
    • G1 CLinear_TV uses ε = 0.3 with γ = 0.96, where the bound is ≈ 0.204.
  • Vacuous constants where the condition does hold. For the Swimmer setting (γ = 0.9999, ε = 0.01), C_ε = √(γε²/(1−γ(1+ε²))) ≈ 100. For Ant (γ = 0.99, ε = 0.1), C_ε ≈ 10. The bound is then very unlikely to be informative.
  • Per-state moment conditions. Centering and normalization must hold per state, but the implementation enforces them only at the batch level. With continuous actions and one sampled action per state, per-state moments cannot even be estimated. Lemma 5 relies precisely on the per-state bound E_{π₀}[ρ²|s] ≤ 1+ε².
  • Remaining modeling gaps.
    • The discount factor in the theory is a tuned hyperparameter, while evaluation uses undiscounted episode return.
    • Advantage-estimation error (GAE) is not modeled.

The limitations section acknowledges some of these points. But together they mean the empirical section does not validate the theory, and the theory does not certify the proposed algorithms. This undercuts the central claim of "guarantees after imperfect fitting … for the practical procedure".

In addition, the claim of "no irreducible worst-case constants" is overstated:

  • The unweighted losses carry A_∞ and Ā, both suprema over states.
  • Corollary 1 uses L_max = sup_s L.
  • The weighted certificates need a sup-norm bound on V_{π_θ} − V_{π₀}.

2. Empirical evidence for the proposed instances is limited and not statistically convincing.

  • Few informative tasks. There are 10 tasks in total, but Swimmer and Pong are saturated: all methods score 362 ± 0, and Pong is around 20.5. Effectively about 6 RL tasks plus 2 LLM evaluations carry the comparison.
  • Small margins, against PPO in particular.
    • On Anymal, PPO (16.8) beats CLinear_ATV (14.7).
    • On LLM fine-tuning, GRPO has the best average rank.
    • Most other differences fall within the reported spreads.
  • Statistical reporting conflates sources of variance.
    • "Mean ± std over the last 100 evaluations pooled across 5 seeds" mixes within-run fluctuation with between-seed variance. No confidence intervals or tests are provided.
    • The Asterix result (15198 ± 9390) suggests a single-seed outlier that drives the Atari ranking.
    • I recommend per-seed final performance with bootstrap CIs or IQM (e.g., the rliable protocol).
  • Tuning protocol and rank aggregation.
    • Hyperparameters are tuned on a single seed (seed 1) by final performance. It is unclear whether that seed is among the 5 evaluation seeds.
    • The "CLinear_AH/ATV best average rank" in Figure 2 selects the better of two losses per environment. That is itself a form of per-environment tuning.
  • LLM setup is under-specified.
    • The base model is not reported, and neither are seeds or variances.
    • Training uses TTRL, i.e., test-time RL on the evaluation questions, as the "AIME-TTT" / "AMC-TTT" labels suggest. This differs from the "trained with verifiable rewards" framing in the main text.
    • Differences such as 0.497 vs 0.508 are likely within noise.

On the novelty of the proposed instances:

  • The clipped standardized-advantage target is close to standard advantage normalization.
  • CLinear_AH differs from PPO mainly in replacing the sign by a clipped standardized advantage inside the hinge target.
  • The algorithmic contribution is therefore incremental, so the paper's value rests largely on the theory, which has the gaps noted in Weakness 1.
Questions for authors
  1. Bound tightness. For which of the reported runs do Assumptions 1–2 actually hold? Can you numerically estimate the right-hand side of Theorem 1 / Corollary 1 on at least one task (e.g., Hopper), to show the bound is ever non-vacuous during training?
  2. Certificate under σ = 0. With σ = 0 as used in all benchmarks, what certificate, if any, applies to CLinear_ATV and CLinear_AH? Can the span-based correction in Appendix A.2 be made practical?
  3. Lemma 1 statement. Lemma 1 in the main text states the condition with A_{π₀}, while the proof uses A_{π_θ}. Please confirm the intended statement. With A_{π₀} the lemma would not yield the gap bound.
  4. PPO equivalence and centering. PPO's clipping corresponds to the uncentered sign target (ρ* = 1 ± ε), whereas Assumption 1 requires the centered target. Is PPO strictly an instance of the certified family?
  5. Per-state vs batch statistics. How large is the violation of the per-state conditions (E_{π₀}[g²|s] ≤ 1) in practice? Is there an argument that batch-level normalization suffices for Lemma 5?
  6. Evaluation protocol. Is the tuning seed included in the 5 evaluation seeds? Can you report per-seed results with confidence intervals, in particular for Asterix?
  7. LLM experiments. Which base model, how many seeds, and what variance? Are AIME/AMC scores obtained by training on the test questions with pseudo-labels (TTRL)?
9 comments

We thank the reviewer for the detailed and insightful review.

Before addressing the reviewer’s individual concerns, we would like to highlight the positioning and scope of our results. Our main contribution is a theoretical framework for an algorithmic principle shared by several existing policy-optimization methods: constructing an improving target policy and fitting a parameterized policy to that target. We characterize choices of targets and tracking losses that admit a common conditional improvement guarantee, explicitly accounting for residual tracking error. This framework also motivates new algorithmic instances, which we have evaluated empirically.

The theory does not provide an end-to-end guarantee for the neural implementation used in our experiments. In particular, errors in advantage estimation and finite-sample estimation are not covered by our analysis. Our aim is rather to provide theoretical justification for the shared algorithmic principle and use it to guide algorithm design. We agree that the original manuscript did not distinguish these claims sufficiently clearly, and we will revise the contribution and guarantee statements accordingly.

We now address the reviewer’s individual concerns in turn.

W1: Gap between theory and practice

We address the specific discrepancies identified by the reviewer individually below: the correction coefficients, the step-size restriction, the magnitude of the bound’s constants, per-state moment conditions, and errors or mismatches arising from advantage estimation and the evaluation objective. Our additional results relax some of the original assumptions but they do not eliminate all of these limitations. We will make this distinction explicit in the revised manuscript and clarify the claims connecting the theoretical framework to its practical implementations.

W1.1 / Q2: Weighted losses with σ = 0

We thank the reviewer for this careful observation, and we agree that our theorem only certifies cases with σ,σ2>0\sigma, \sigma_2>0.

Empirically, our ablations (Fig. 3 in Section 4.3 and Fig. 5 in Appendix A.6) show that small values σ = 0.1 and σ₂ = 0.1 (certifiable by our theorem) perform close to σ = σ₂ = 0, while larger values gradually reduce performance. For instance, σ₂ = 0.1 retains 95–101% of the return of σ₂ = 0 on G1-rough, Hopper and Breakout in the revised Fig. 5. We therefore use σ = σ₂ = 0 as the practical default, and we will add this analysis to Appendix A.2.

Besides, the additional loss term σLTV\sigma\mathcal L_{TV} is reducible, since it is itself an expected tracking loss that can be minimized explicitly whenever σ > 0. This contrasts with existing improvement bounds, which either contain worst-case terms that do not decrease with the training loss, or require a penalty coefficient that is too large for practical use. Accordingly, in the revised paper we have changed the statement that our guarantee covers PPO, BPO and SPO to state that it covers their close variants with an additional small and reducible loss term.

Regarding the span-based correction in Appendix A.2, it yields a tighter constant for the ATV loss, but it still depends on the change in the value function, which is not observable from the data of a single update. We therefore do not regard it as practical at present.

W1.2 / Q1: Step size and tightness of the bound

Regarding the step size, we first note that, with the hyperparameters selected in the paper (Table 6), Assumption 2 holds for CLinear_AH in all six RL settings and for CLinear_ATV in four of the six. We derive a new result that holds for arbitrary admissible step sizes. It relaxes the normalization Eπ0[g2∣s]≤1\mathbb E_{\pi_0}[g^2\mid s]\le1 in Assumption 1(ii) and the step-size condition γ(1+ϵ2)<1\gamma(1+\epsilon^2)<1 in Assumption 2 as follows.

Assumption 1(ii′) (bounded second moment). There exists a finite constant B≥1B\ge1 such that Eπ0[g2∣s]≤B2\mathbb E_{\pi_0}[g^2\mid s]\le B^2 at every state ss.

Assumption 2 (relaxed step size). We just need to pick an order p∈(1,2]p\in(1,2] such that γ(1+ϵ2B2)p−1<1\gamma(1+\epsilon^2B^2)^{p-1}<1. Such order pp exists for every γ<1\gamma<1, finite BB, and admissible step size ϵ\epsilon.

Since only the product ϵg\epsilon g defines the target, the normalization merely fixes a scale. Under Assumption 1(ii′), set g′=g/Bg'=g/B and ϵ′=ϵB\epsilon'=\epsilon B, so that Eπ0[(g′)2∣s]≤1\mathbb E_{\pi_0}[(g')^2\mid s]\le1 and ϵ′g′=ϵg\epsilon'g'=\epsilon g. Applying Theorem 1 to (g′,ϵ′)(g',\epsilon') preserves both the target and the improvement term, but requires γ(1+ϵ2B2)<1\gamma(1+\epsilon^2B^2)<1. The following result removes this restriction and extends Corollary 1 in the main text to arbitrary admissible step sizes, retaining the nonnegativity condition 1+ϵg≥01+\epsilon g\ge0 and the other assumptions on the target; we will include it, with its full proof, in Appendix A.4.

Corollary 2 (arbitrary admissible step sizes). Let Assumptions 1(i), 1(ii′), 1(iii), 1(iv) hold. Let πθ(⋅∣s)≪π0(⋅∣s)\pi_\theta(\cdot|s)\ll\pi_0(\cdot|s) for every ss, and let p∈(1,2]p\in(1,2] satisfy γ(1+ϵ2B2)p−1<1\gamma(1+\epsilon^2B^2)^{p-1}<1. Let L\mathcal L be any non-negative certified loss satisfying Eq. (4) with constant CLC_\mathcal L and Lmax⁡:=sup⁡sL(θ;s)<∞\mathcal L_{\max}:=\sup_s\mathcal L(\theta;s)<\infty. Then, with Lˉ:=Edπ0[L]\bar{\mathcal L}:=\mathbb E_{d_{\pi_0}}[\mathcal L],

(1−γ)(η(πθ)−η(π0))≥ϵEdπ⋆,π0[gAπ0]−CL(Lˉ+DpLmax⁡1/pLˉ(p−1)/p),(1-\gamma)\bigl(\eta(\pi_\theta)-\eta(\pi_0)\bigr)\ge\epsilon\mathbb E_{d_{\pi^\star},\pi_0}[gA_{\pi_0}]-C_\mathcal L\bigl(\bar{\mathcal L}+D_p\mathcal L_{\max}^{1/p}\bar{\mathcal L}^{(p-1)/p}\bigr),

where Dp=(1+Mp)1/pD_p=(1+M_p)^{1/p} and Mp=1−γ1−γ(1+ϵ2B2)p−1M_p=\frac{1-\gamma}{1-\gamma(1+\epsilon^2B^2)^{p-1}}.

For every γ<1\gamma<1, finite BB, and admissible step size ϵ\epsilon, γ(1+ϵ2B2)p−1<1\gamma(1+\epsilon^2B^2)^{p-1}<1 holds when p>1p>1 is chosen sufficiently close to 1. Corollary 2 therefore removes the original step-size restriction while retaining the other assumptions on the target and loss. The price is a weaker dependence on the population mean tracking loss, through the fractional power Lˉ(p−1)/p\bar{\mathcal L}^{(p-1)/p}. With CLC_{\mathcal L} and Lmax⁡\mathcal L_{\max} uniformly bounded, the penalty still vanishes as Lˉ\bar{\mathcal L} approaches zero. When γ(1+ϵ2B2)<1\gamma(1+\epsilon^2B^2)<1, Corollary 1, applied after the rescaling above, gives a tighter bound than Corollary 2 evaluated at p=2p=2.

Regarding tightness, we evaluate the bounds, including Corollary 2, on random MDPs with 20 states and 4 actions, where all quantities can be computed exactly. We run the practical algorithm as in our benchmarks, with sampled data, batch-level normalization, no per-state statistics, and σ=0\sigma=0. After every update, we compute the true improvement (1−γ)(η(πθ)−η(π0))(1-\gamma)(\eta(\pi_\theta)-\eta(\pi_0)) and the right-hand side of each bound, including the additional correction discussed under W1.1. We vary γ∈{0.9,0.99}\gamma\in\{0.9,0.99\}, ϵ∈{0.05,0.1,0.2,0.3}\epsilon\in\{0.05,0.1,0.2,0.3\} and the number of epochs, with 5 seeds and 30 updates per setting.

Across all 7,200 updates, no bound exceeded the true improvement. The table below reports the fraction of updates of CLinear_ATV for which the bound certifies improvement (right-hand side is positive), together with the improvement bound of TRPO (Schulman et al., 2015, Thm. 1) evaluated on the same updates.

SettingOursTRPO
γ=0.9\gamma=0.9, ϵ≤0.1\epsilon\le0.158–79%0%
γ=0.9\gamma=0.9, ϵ=0.2\epsilon=0.2–0.30.314–26%0–1%
γ=0.99\gamma=0.99≤ 2%0%

Our bound certifies improvement substantially more often than the TRPO bound at γ=0.9\gamma=0.9, when both are evaluated on the same policy updates. At γ=0.99\gamma=0.99, certification remains rare for both bounds, illustrating their remaining conservatism at longer effective horizons.

W1.3: Large constants

We agree that CϵC_\epsilon can be large when γ\gamma is close to 1. However, it enters the bound differently from the constants of existing improvement bounds. In conservative policy iteration and TRPO-type bounds (Kakade & Langford, 2002; Schulman et al., 2015), a worst-case constant multiplies the divergence between the new and the old policy, typically its maximum over all states. With its theoretical coefficient, this penalty is too conservative to be used in practice, which is why TRPO replaces it by a KL constraint.

In our bound, CϵC_\epsilon multiplies only the tracking loss under the behavior distribution, which is minimized during training. Consequently, as the training loss approaches zero, the penalty vanishes and the bound recovers the full target gain.

W1.4 / Q5: Per-state moment conditions

We agree with the reviewer that Algorithm 1 estimates moments at the batch level. Per-state statistics are required by two conditions of Assumption 1, namely centering (i) and normalization (ii). We address both conditions below.

Normalization. Our new Corollary 2 above replaces the normalization condition by the bounded second moment Eπ0[g2∣s]≤B2\mathbb E_{\pi_0}[g^2\mid s]\le B^2. For the clipped-linear direction, clipping ensures ∣g~∣≤1/(2ϵ)|\tilde g|\le1/(2\epsilon), even when the normalization statistics are estimated from a batch. Its per-state centered counterpart g=g~−Eπ0[g~∣s]g=\tilde g-\mathbb E_{\pi_0}[\tilde g\mid s] therefore satisfies

=\operatorname{Var}_{\pi_0}(\tilde g\mid s) \le\frac{1}{4\epsilon^2}.$$ Thus Assumption 1(ii′) holds with $B=\max\{1,1/(2\epsilon)\}$, without requiring per-state normalization. **Centering.** With $\sigma>0$, the loss to the centered target can be bounded by a multiple of the loss to the uncentered target used in practice. For the ATV loss, $$\mathcal L^w_{TV}(\pi_\theta,\pi^\star) \le\left(1+\frac{\mathbb E_{\pi_0}[w]}{\sigma}\right) \mathcal L^w_{TV}(\pi_\theta,\tilde\pi),$$ where $\tilde\pi$ denotes the uncentered target. This follows from the triangle inequality and Jensen’s inequality. An analogous bound holds for the regularized hinge loss when $\sigma,\sigma_2>0$, with a multiplicative constant that additionally depends on $\sigma_2$. The uncentered tracking loss therefore controls an upper bound on the certified population loss, without requiring explicit per-state centering during training. We will include the proof in the appendix. Consistently, our centering ablation (Appendix A.6, Fig. 5) shows nearly the same performance with and without centering. Errors in advantage estimation remain outside our analysis, as discussed under W1.5. > **W1.5: Discount factor and GAE** We agree with the reviewer on both points. As is standard for policy improvement bounds (Schulman et al., 2015; Achiam et al., 2017), our analysis assumes exact advantages and does not model the estimation error of the critic or the bias of GAE. Likewise, optimizing a discounted objective while evaluating the undiscounted return is common practice in deep RL, and its mismatch has been discussed by Thomas (2014) and Nota & Thomas (2020). We will state this in the limitations. > **W1.6: Claim on worst-case constants** We thank the reviewer and agree that our wording was ambiguous. By "no irreducible worst-case constants", we mean that the bound contains no standalone worst-case term. Worst-case constants do appear, including $A_\infty$, $\bar A$, $\mathcal L_{\max}$ and $\|V_{\pi_\theta}-V_{\pi_0}\|_\infty$, but each of them only multiplies a reducible term, namely the tracking loss that is minimized during training. As this loss approaches zero, all such terms vanish and the bound recovers the full target gain. In the revised version, we will rephrase the claim as "no standalone worst-case terms: worst-case constants only multiply reducible terms of the tracking loss".
Reviewer_VCc5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper constructs proximal ascent target policies, fits them with tracking losses, and connects the ideal tracking loss to policy return through an occupancy-distribution error bound. The question of whether sustained reduction of a practical training loss improves the true return is important. The framework separates a target direction from a tracking loss, covering sign, clipped-linear, and exponential targets and hinge, TV, MSE, and KL-style fitting losses. The analysis explicitly allows imperfect fitting. However, the main empirical instances do not satisfy the stated certification conditions, which weakens the paper's central practical message.

Critical strengths
  1. A useful framework for separating target directions from tracking losses. Section 3 organizes the target policy and the tracking objective independently, which gives a helpful perspective on existing policy-optimization methods and on possible new combinations.

  2. A clear treatment of imperfect target fitting. Appendix A.3 derives a chi-square occupancy-distribution bound from second moments of stepwise policy ratios and then transfers the result to tracking losses. This makes the allowed target-fitting error explicit rather than assuming exact optimization.

  3. Broad empirical coverage and relevant ablations. Section 4 evaluates four task families and studies step size, normalization, and loss components, showing that different target-loss combinations can have different empirical value across tasks.

Critical weaknesses
  1. The main experiments do not directly inherit the advertised certification. The advantage-weight substitution in Remarks 1-2 and the old-advantage-sign hinge guarantee require positive correction coefficients, whereas Section 4.3 and Appendix A.6 set sigma = sigma_2 = 0 in the final configuration. The primary ATV/AH instances therefore cannot directly receive the stated certificate.

  2. The theoretical assumptions and the practical estimator operate at different granularities. Algorithm 1 uses batch moments and estimated advantages, while Assumption 1 requires per-state centering, normalization, and alignment with the true advantage. A low observed training loss is consequently not, by itself, the operational improvement certificate emphasized by the paper.

  3. Lemma 1 appears to use the wrong advantage subscript. It controls the expectation of A_pi0 under pi*, whereas the performance-difference expression in Appendix A.2 requires the expectation of A_pi_theta under pi*. As written, the lemma does not establish the stated result.

Questions for authors
  1. Can the authors compare instances satisfying sigma > 0 and sigma_2 > 0 with the final default instances, and state whether the latter has an alternative guarantee that does not rely on these correction terms?

  2. On a small MDP where advantages can be computed exactly, can the paper jointly measure the per-state constraints, the theoretical lower bound, and the actual return change to test when empirical tracking loss predicts improvement?

  3. Can the authors reconcile the advantage-function subscripts in Lemma 1 and Appendix A.2 and provide the complete dependency chain for the corrected conclusions?

  4. After correcting the Pinsker coefficient and retaining all C_L constants, under what conditions does the proposed ordering of tighter certificates for ATV, AH, MSE, and KL remain valid?

  5. Can the paper first average terminal evaluations within each seed, then report paired seed-level differences and intervals, while also stating the number of independent LLM training runs?

7 comments

We thank the reviewer for the thorough and constructive review.

Before addressing the reviewer’s individual concerns, we would like to highlight the positioning and scope of our results. Our main contribution is a theoretical framework for an algorithmic principle shared by several existing policy-optimization methods: constructing an improving target policy and fitting a parameterized policy to that target. We characterize choices of targets and tracking losses that admit a common conditional improvement guarantee, explicitly accounting for residual tracking error. This framework also motivates new algorithmic instances, which we have evaluated empirically.

The theory does not provide an end-to-end guarantee for the neural implementation used in our experiments. In particular, errors in advantage estimation and finite-sample estimation are not covered by our analysis. Our aim is rather to provide theoretical justification for the shared algorithmic principle and use it to guide algorithm design. We agree that the original manuscript did not distinguish these claims sufficiently clearly, and we will revise the contribution and guarantee statements accordingly.

We now address the reviewer’s individual concerns in turn.

W1 / Q1: The case σ = 0

We thank the reviewer for the question, and we agree that our theorem only certifies cases with σ,σ2>0\sigma, \sigma_2>0.

Comparison. Our ablations compare such instances with the default σ = σ₂ = 0 on G1-rough, Hopper and Breakout (Fig. 3 in Section 4.3 for σ, Fig. 5 in Appendix A.6 for σ₂). Small values σ = 0.1 and σ₂ = 0.1 (certifiable by our theorem) perform close to σ = σ₂ = 0. For instance, σ₂ = 0.1 retains 95–101% of the return of σ₂ = 0 on all three tasks in the revised Fig. 5. We therefore use σ = σ₂ = 0 as the practical default.

Scope of the guarantee. We do not claim an alternative guarantee for the zero-offset defaults. Positive offsets introduce additional tracking terms that ensure the loss satisfies the certification conditions, subject to the remaining assumptions of our analysis. These terms can be minimized as part of the training objective. Accordingly, our guarantee applies to regularized close variants of PPO, BPO and SPO. The zero-offset implementations are practical simplifications motivated by the framework and assessed empirically. We will make this distinction explicit in the revised paper.

Compare to existing works. Note that our additional loss term σLTV\sigma\mathcal L_{TV} can be reduced in a practical way, since it is itself an expected tracking loss that can be minimized explicitly whenever σ > 0. This contrasts with existing improvement bounds, which either contain worst-case terms that do not decrease with the training loss, or require a penalty coefficient that is too large for practical use.

W2: Batch versus per-state statistics

We agree with the reviewer that batch level estimation is different from per-state statistics. Per-state statistics are originally required by two conditions of Assumption 1, namely centering (i) and normalization (ii). We address both conditions below.

Normalization. We derive a new result that relaxes the normalization Eπ0[g2∣s]≤1\mathbb E_{\pi_0}[g^2\mid s]\le1 in Assumption 1(ii) and the step-size condition γ(1+ϵ2)<1\gamma(1+\epsilon^2)<1 in Assumption 2 as follows.

Assumption 1(ii′) (bounded second moment). There exists a constant B≥1B\ge1 such that Eπ0[g2∣s]≤B2\mathbb E_{\pi_0}[g^2\mid s]\le B^2 at every state ss.

Assumption 2 (relaxed step size). We just need to pick an order p∈(1,2]p\in(1,2] such that γ(1+ϵ2B2)p−1<1\gamma(1+\epsilon^2B^2)^{p-1}<1. Such order pp always exists for every γ<1\gamma<1, finite BB.

Since only the product ϵg\epsilon g defines the target, the normalization merely fixes a scale. Under Assumption 1(ii′), set g′=g/Bg'=g/B and ϵ′=ϵB\epsilon'=\epsilon B, so that Eπ0[(g′)2∣s]≤1\mathbb E_{\pi_0}[(g')^2\mid s]\le1 and ϵ′g′=ϵg\epsilon'g'=\epsilon g. Applying Theorem 1 to (g′,ϵ′)(g',\epsilon') preserves both the target and the improvement term, but requires γ(1+ϵ2B2)<1\gamma(1+\epsilon^2B^2)<1. The following result removes this restriction and extends Corollary 1 in the main text to arbitrary admissible step sizes, retaining the nonnegativity condition 1+ϵg≥01+\epsilon g\ge0 and the other assumptions on the target. We will include it, with its full proof, in Appendix A.4.

Corollary 2 (arbitrary admissible step sizes). Let Assumptions 1(i), 1(ii′), 1(iii), 1(iv) hold. Let πθ(⋅∣s)≪π0(⋅∣s)\pi_\theta(\cdot|s)\ll\pi_0(\cdot|s) for every ss, and let p∈(1,2]p\in(1,2] satisfy γ(1+ϵ2B2)p−1<1\gamma(1+\epsilon^2B^2)^{p-1}<1. Let L\mathcal L be any non-negative certified loss satisfying Eq. (4) with constant CLC_\mathcal L and Lmax⁡:=sup⁡sL(θ;s)<∞\mathcal L_{\max}:=\sup_s\mathcal L(\theta;s)<\infty. Then, with Lˉ:=Edπ0[L]\bar{\mathcal L}:=\mathbb E_{d_{\pi_0}}[\mathcal L],

(1−γ)(η(πθ)−η(π0))≥ϵEdπ⋆,π0[gAπ0]−CL(Lˉ+DpLmax⁡1/pLˉ(p−1)/p),(1-\gamma)\bigl(\eta(\pi_\theta)-\eta(\pi_0)\bigr)\ge\epsilon\mathbb E_{d_{\pi^\star},\pi_0}[gA_{\pi_0}]-C_\mathcal L\bigl(\bar{\mathcal L}+D_p\mathcal L_{\max}^{1/p}\bar{\mathcal L}^{(p-1)/p}\bigr),

where Dp=(1+Mp)1/pD_p=(1+M_p)^{1/p} and Mp=1−γ1−γ(1+ϵ2B2)p−1M_p=\frac{1-\gamma}{1-\gamma(1+\epsilon^2B^2)^{p-1}}.

For every γ<1\gamma<1, finite BB, and admissible step size ϵ\epsilon, γ(1+ϵ2B2)p−1<1\gamma(1+\epsilon^2B^2)^{p-1}<1 holds when p>1p>1 is chosen sufficiently close to 1. Corollary 2 therefore removes the original step-size restriction while retaining the other assumptions on the target and loss. The price is a weaker dependence on the population mean tracking loss, through the fractional power Lˉ(p−1)/p\bar{\mathcal L}^{(p-1)/p}. With CLC_{\mathcal L} and Lmax⁡\mathcal L_{\max} uniformly bounded, the penalty still vanishes as Lˉ\bar{\mathcal L} approaches zero. When γ(1+ϵ2B2)<1\gamma(1+\epsilon^2B^2)<1, Corollary 1, applied after the rescaling above, gives a tighter bound than Corollary 2 evaluated at p=2p=2.

For the clipped-linear direction, clipping ensures ∣g~∣≤1/(2ϵ)|\tilde g|\leq 1/(2\epsilon), even when the normalization statistics are estimated from a batch. Its per-state centered counterpart g=g~−Eπ0[g~∣s]g=\tilde g-\mathbb E_{\pi_0}[\tilde g\mid s] therefore satisfies

Eπ0[g2∣s]=Var⁡π0(g~∣s)≤14ϵ2.\mathbb E_{\pi_0}[g^2\mid s]=\operatorname{Var}_{\pi_0}(\tilde g\mid s)\leq\frac{1}{4\epsilon^2}.

Thus Assumption 1(ii′) holds with B=max⁡{1,1/(2ϵ)}B=\max\{1,1/(2\epsilon)\}, without requiring per-state normalization.

Centering. With σ > 0, the loss to the centered target is upper bounded by the loss to the uncentered target used in practice. For the ATV loss, LTVw(πθ,π⋆)≤(1+Eπ0[w]/σ)LTVw(πθ,π~)\mathcal L^w_{TV}(\pi_\theta,\pi^\star)\le\bigl(1+\mathbb E_{\pi_0}[w]/\sigma\bigr)\mathcal L^w_{TV}(\pi_\theta,\tilde\pi), where π~\tilde\pi denotes the uncentered target. This follows from the triangle inequality and Jensen’s inequality. An analogous bound holds for the regularized hinge loss when σ,σ2>0\sigma,\sigma_2>0, with a multiplicative constant that additionally depends on σ2\sigma_2. The uncentered tracking loss therefore controls an upper bound on the certified population loss, without requiring explicit per-state centering during training. Consistently, our centering ablation experiments (Appendix A.8, Fig. 5) show nearly the same performance between the runs with and without centering.

W3 / Q3: Subscripts in Lemma 1

We thank the reviewer for spotting this typo. The condition in Lemma 1 should read CLL(π⋆,πθ;s)≥Ea∼π⋆[Aπθ]C_\mathcal L\mathcal L(\pi^\star,\pi_\theta;s)\ge\mathbb E_{a\sim\pi^\star}[A_{\pi_\theta}], since the lemma follows from applying the performance-difference lemma to the pair (π⋆,πθ)(\pi^\star,\pi_\theta).

This correction does not affect any other result, because the proofs in Appendix A.2 and all constants in Table 2 are already stated in terms of AπθA_{\pi_\theta}.

Q2: Experiment on a small MDP

We thank the reviewer for this valuable suggestion and have conducted the proposed experiment. We evaluate the bound on random MDPs with 20 states and 4 actions, where all quantities can be computed exactly, and we run the practical algorithm as in our benchmarks, with sampled data, batch-level normalization, no per-state statistics, and σ = 0. After every update, we compute the true improvement (1−γ)(η(πθ)−η(π0))(1-\gamma)(\eta(\pi_\theta)-\eta(\pi_0)) and the right-hand side of each bound, including the additional term discussed under W1. We vary γ ∈ {0.9, 0.99}, ε ∈ {0.05, 0.1, 0.2, 0.3} and the number of epochs, with 5 seeds and 30 updates per setting.

Across all 7,200 updates, no bound exceeded the true improvement. The table below reports the fraction of updates of CLinear_ATV for which the bound certifies improvement (right hand side is positive), together with the improvement bound of TRPO (Schulman et al., 2015, Thm. 1) evaluated on the same updates.

SettingOursTRPO
γ = 0.9, ε ≤ 0.158–79%0%
γ = 0.9, ε = 0.2–0.314–26%0–1%
γ = 0.99≤ 2%0%

Our bound certifies improvement substantially more often than the TRPO bound at γ = 0.9, when both are evaluated on the same policy updates. At γ = 0.99, certification remains rare for both bounds, illustrating their remaining conservatism at longer effective horizons.

Q4: Pinsker constant and ordering

We thank the reviewer for this correction: Appendix A.2 applies Pinsker's inequality correctly, LTV≤2LKL\mathcal L_{TV}\le\sqrt{2\mathcal L_{KL}}, but the factor 2\sqrt2 was dropped in Eq. (9) and Table 2. The corrected constant for the KL loss is CL=2AˉC_\mathcal L=\sqrt2\bar A. With all constants retained, the ordering AH ≤ ATV ≤ AMSE still holds exactly, whereas the comparison between ATV and KL holds up to a factor of 2 in the worst case, since Aˉ≥A∞/2\bar A\ge A_\infty/2.

Q5: Seed-level statistics and LLM runs

We agree with the reviewer's suggestion. For the RL benchmarks, the table reports the interquartile mean (IQM) of the PPO-normalized score over the eight benchmarks and 5 seeds, with 95% stratified bootstrap confidence intervals.

MethodIQM [95% CI]
CLinear_ATV1.02 [1.01, 1.04]
CLinear_AH1.02 [1.01, 1.03]
PPO1.00 [0.99, 1.01]
CLinear_TV/MSE0.99 [0.99, 1.00]
Sign_ATV/AMSE0.98 [0.97, 0.99]
Exp_ATV/AMSE0.97 [0.96, 0.99]

For the LLM experiments (base model Qwen2.5-Math-1.5B), we have conducted four independent training runs per method; the table reports the mean ± standard deviation of the final accuracy, which we will also include in the revised version.

MethodAMCAIME
CLinear_ATV0.508 ± 0.0120.267 ± 0.027
Sign_ATV0.520 ± 0.0090.258 ± 0.014
GRPO0.513 ± 0.0080.268 ± 0.028
CLinear_AH0.522 ± 0.0150.279 ± 0.025

These results show that CLinear_AH is competitive with GRPO, with the highest observed mean accuracy on both benchmarks. We will also revise the experiment section acccordingly.

We hope that these responses address the reviewer's concerns, and we would be glad to clarify any further questions.

Reviewer_xvrVOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Follow-the-Improvement RL, a framework that unifies two popular classes of on-policy reinforcement learning algorithms based on trust regions and target policies, respectively. The paper introduces a class of target policies for improvement, combined with a policy improvement bound that depends on a loss function that is directly minimized during training. The bound is used to motivate algorithmic implementations using different target policies and loss functions, which are evaluated in experiments across MuJoCo, Isaac Lab, Atari, and LLM domains.

Critical strengths
  • [S1]: The paper proposes a framework that unifies existing on-policy algorithms based on trust regions and target policies, respectively. The framework applies to popular on-policy algorithms such as PPO, offering an alternative explanation of their performance compared to existing policy improvement bounds.
  • [S2]: The proposed policy improvement bound does not contain irreducible constant terms that typically appear in existing policy improvement bounds used to motivate popular algorithms such as PPO. Instead, it only contains a non-negative term and a term based on the loss function that is minimized during training.
  • [S3]: Experiments consider a range of benchmark domains, including realistic Isaac Lab and LLM benchmark tasks (although each domain only considers a small number of tasks).
Critical weaknesses
  • [W1]: It is not clear to me if Lemma 1 requires an assumption that uses the advantage w.r.t. π0\pi_0 or πθ\pi_\theta, and if that has implications for the rest of the analysis. See [Q1].
  • [W2]: It appears that several choices of hyperparameters used in the experiments violate the step size assumption (Assumption 2) required for the theoretical results to hold, but the ablation studies only analyze the impact of step size for Hopper and Swimmer.
  • [W3]: The experimental results do not demonstrate a dominant choice of target / loss combination.
Questions for authors
  • [Q1]: Please provide a proof for Lemma 1 based on the assumption that uses the advantage w.r.t. π0\pi_0 as stated in line 178. If the assumption is supposed to reference the advantage w.r.t. πθ\pi_\theta instead, what implications would that have for the rest of the analysis including the constants in Table 2 (it seems like that assumption would be difficult to verify using available data, which would weaken the paper’s contribution)?
  • [Q2]: Can the framework be extended to provide insight about off-policy algorithms?
2 comments

We thank the reviewer for the positive assessment and the helpful questions, which we address below.

W1 / Q1: Lemma 1

We thank the reviewer for spotting this typo. The condition in Lemma 1 should indeed read CLL(π⋆,πθ;s)≥Ea∼π⋆[Aπθ]C_\mathcal L\mathcal L(\pi^\star,\pi_\theta;s)\ge\mathbb E_{a\sim\pi^\star}[A_{\pi_\theta}], with θ\theta instead of 00, since the lemma follows from applying the performance-difference lemma to the pair (π⋆,πθ)(\pi^\star,\pi_\theta). This correction does not affect any other result, because the proofs in Appendix A.2 and all constants in Table 2 are already stated in terms of AπθA_{\pi_\theta}.

We also note that the condition is an analytic property of each loss, proven in Appendix A.2, rather than an assumption that needs to be verified on data. For example, for the weighted TV loss with w≥∣Aπθ∣w\ge|A_{\pi_\theta}|, since Ea∼πθ[Aπθ]=0\mathbb E_{a\sim\pi_\theta}[A_{\pi_\theta}]=0, we have

Ea∼π⋆[Aπθ]=Ea∼π0[(ρ⋆−ρθ)Aπθ]≤Ea∼π0[w∣ρθ−ρ⋆∣]=LTVw,\mathbb E_{a\sim\pi^\star}[A_{\pi_\theta}]=\mathbb E_{a\sim\pi_0}\bigl[(\rho^\star-\rho_\theta)A_{\pi_\theta}\bigr]\le\mathbb E_{a\sim\pi_0}\bigl[w|\rho_\theta-\rho^\star|\bigr]=\mathcal L^w_{TV},

so that the condition holds with CL=1C_\mathcal L=1 for every policy πθ\pi_\theta.

W2: Step size

We thank the reviewer for raising this point. With the hyperparameters selected in the paper (Table 6), Assumption 2 holds for CLinear_AH in all six RL settings and for CLinear_ATV in four of the six, so that the violations concern CLinear_ATV on Anymal and Atari as well as several other instances.

During the rebuttal stage, we discovered a new result that holds for arbitrary admissible step sizes. It relaxes the normalization Eπ0[g2∣s]≤1\mathbb E_{\pi_0}[g^2\mid s]\le1 in Assumption 1(ii) and the step-size condition γ(1+ϵ2)<1\gamma(1+\epsilon^2)<1 in Assumption 2 as follows.

Assumption 1(ii′) (bounded second moment). There exists a constant B≥1B\ge1 such that Eπ0[g2∣s]≤B2\mathbb E_{\pi_0}[g^2\mid s]\le B^2 at every state ss.

Assumption 2 (relaxed step size). We just need to pick an order p∈(1,2]p\in(1,2] such that γ(1+ϵ2B2)p−1<1\gamma(1+\epsilon^2B^2)^{p-1}<1. Such order pp always exists for every γ<1\gamma<1, finite BB.

Since only the product ϵg\epsilon g defines the target, the normalization merely fixes a scale. Under Assumption 1(ii′), set g′=g/Bg'=g/B and ϵ′=ϵB\epsilon'=\epsilon B, so that Eπ0[(g′)2∣s]≤1\mathbb E_{\pi_0}[(g')^2\mid s]\le1 and ϵ′g′=ϵg\epsilon'g'=\epsilon g. Applying Theorem 1 to (g′,ϵ′)(g',\epsilon') preserves both the target and the improvement term, but requires γ(1+ϵ2B2)<1\gamma(1+\epsilon^2B^2)<1. The following result removes this restriction and extends Corollary 1 in the main text to arbitrary admissible step sizes, retaining the nonnegativity condition 1+ϵg≥01+\epsilon g\ge0 and the other assumptions on the target. We will include it, with its full proof, in Appendix A.4.

Corollary 2 (arbitrary admissible step sizes). Let Assumptions 1(i), 1(ii′), 1(iii), 1(iv) hold. Let πθ(⋅∣s)≪π0(⋅∣s)\pi_\theta(\cdot|s)\ll\pi_0(\cdot|s) for every ss, and let p∈(1,2]p\in(1,2] satisfy γ(1+ϵ2B2)p−1<1\gamma(1+\epsilon^2B^2)^{p-1}<1. Let L\mathcal L be any non-negative certified loss satisfying Eq. (4) with constant CLC_\mathcal L and Lmax⁡:=sup⁡sL(θ;s)<∞\mathcal L_{\max}:=\sup_s\mathcal L(\theta;s)<\infty. Then, with Lˉ:=Edπ0[L]\bar{\mathcal L}:=\mathbb E_{d_{\pi_0}}[\mathcal L],

(1−γ)(η(πθ)−η(π0))≥ϵEdπ⋆,π0[gAπ0]−CL(Lˉ+DpLmax⁡1/pLˉ(p−1)/p),(1-\gamma)\bigl(\eta(\pi_\theta)-\eta(\pi_0)\bigr)\ge\epsilon\mathbb E_{d_{\pi^\star},\pi_0}[gA_{\pi_0}]-C_\mathcal L\bigl(\bar{\mathcal L}+D_p\mathcal L_{\max}^{1/p}\bar{\mathcal L}^{(p-1)/p}\bigr),

where Dp=(1+Mp)1/pD_p=(1+M_p)^{1/p} and Mp=1−γ1−γ(1+ϵ2B2)p−1M_p=\frac{1-\gamma}{1-\gamma(1+\epsilon^2B^2)^{p-1}}.

For every γ<1\gamma<1, finite BB, and admissible step size ϵ\epsilon, γ(1+ϵ2B2)p−1<1\gamma(1+\epsilon^2B^2)^{p-1}<1 holds when p>1p>1 is chosen sufficiently close to 1. Corollary 2 therefore removes the original step-size restriction while retaining the other assumptions on the target and loss. The price is a weaker dependence on the population mean tracking loss, through the fractional power Lˉ(p−1)/p\bar{\mathcal L}^{(p-1)/p}. With CLC_{\mathcal L} and Lmax⁡\mathcal L_{\max} uniformly bounded, the penalty still vanishes as Lˉ\bar{\mathcal L} approaches zero. When γ(1+ϵ2B2)<1\gamma(1+\epsilon^2B^2)<1, Corollary 1, applied after the rescaling above, gives a tighter bound than Corollary 2 evaluated at p=2p=2.

W3: No dominant combination

We agree with the reviewer, and we acknowledge this limitation in the conclusion of the paper. Our main contribution is to identify the design space of RL methods that share one improvement guarantee (with idealization), and we hope that it will guide future work in exploring this space. This framework describes PPO, BPO and SPO as combinations of a target and a tracking loss, and the guarantee applies to their close variants. The experiments are therefore intended to show that new members of this class are competitive, rather than to identify a single best combination.

Within this class, the results nevertheless suggest a useful default. With the loss fixed, the clipped-linear target achieves a higher average rank than the sign target on most suites (Fig. 2), while the better choice always depends on the domain.

Q2: Off-policy extension

We thank the reviewer for this interesting question. A natural extension is to retain the latest policy π0\pi_0 as the reference and apply Lemma 4 with the replay buffer’s population state distribution (q). This yields Edπ⋆[L]≤Eq[L]+χ2(dπ⋆∥q)Var⁡q(L),\mathbb E_{d_{\pi^\star}}[\mathcal L]\le\mathbb E_q[\mathcal L]+\sqrt{\chi^2(d_{\pi^\star}\Vert q)}\sqrt{\operatorname{Var}_q(\mathcal L)},

provided the required coverage and integrability conditions hold. This route preserves the comparison against the latest policy, while introducing an explicit replay-distribution mismatch term. A useful off-policy guarantee would therefore require controlling this mismatch and accounting for the action-distribution mismatch when estimating the tracking loss from replay data. We will clarify this extension and its additional requirements in the revised discussion, and leave its full theoretical and algorithmic development to future work.

We hope that these responses address the reviewer's concerns, and we would be glad to clarify any further questions.

Comments on the paper

1 comment

Dear Reviewers,

The authors have provided rebuttals to your review. Could you please check their responses and provide any further feedback or questions for the authors to address at your convenience?

Thank you for your time and contribution.

Regards,

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.