- 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.
- 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.
- 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
- 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?
- 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?
- 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.
- 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?
- 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?
- 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?
- 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
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 in Assumption 1(ii) and the step-size condition in Assumption 2 as follows.
Assumption 1(ii′) (bounded second moment). There exists a finite constant such that at every state .
Assumption 2 (relaxed step size). We just need to pick an order such that . Such order exists for every , finite , and admissible step size .
Since only the product defines the target, the normalization merely fixes a scale. Under Assumption 1(ii′), set and , so that and . Applying Theorem 1 to preserves both the target and the improvement term, but requires . The following result removes this restriction and extends Corollary 1 in the main text to arbitrary admissible step sizes, retaining the nonnegativity condition 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 for every , and let satisfy . Let be any non-negative certified loss satisfying Eq. (4) with constant and . Then, with ,
where and .
For every , finite , and admissible step size , holds when 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 . With and uniformly bounded, the penalty still vanishes as approaches zero. When , Corollary 1, applied after the rescaling above, gives a tighter bound than Corollary 2 evaluated at .
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 . After every update, we compute the true improvement and the right-hand side of each bound, including the additional correction discussed under W1.1. We vary , 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.
| Setting | Ours | TRPO |
|---|---|---|
| , | 58–79% | 0% |
| , – | 14–26% | 0–1% |
| ≤ 2% | 0% |
Our bound certifies improvement substantially more often than the TRPO bound at , when both are evaluated on the same policy updates. At , certification remains rare for both bounds, illustrating their remaining conservatism at longer effective horizons.
W1.3: Large constants
We agree that can be large when 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, 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 . For the clipped-linear direction, clipping ensures , even when the normalization statistics are estimated from a batch. Its per-state centered counterpart 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".
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.
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.
We thank the reviewer for this careful observation, and we agree that our theorem only certifies cases with σ,σ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 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.