acceptodds
Under review as a conference paper at ICLR 2027

BRACE: Anchored Bellman-Residual Correction for Stale Critics in Asynchronous RL

Abstract

Asynchronous reinforcement learning has become the standard way to scale training for large language models (LLM), but the resulting policy lag biases the critic toward the stale behavior policy. Existing work on asynchronous LLM training corrects the actor and leaves this bias unaddressed, while the off-policy value correction of classical RL does not carry over to long-horizon agentic tasks, since a short correction horizon leaves the regression target free of the reward and a long one lets the product of importance ratios drift exponentially with the trajectory length. We propose BRACE, an anchored Bellman-residual correction for stale value models. BRACE bounds the correction horizon to a prefix of policy tokens and anchors a constant-weight Monte-Carlo tail beyond it, which separates policy correction from reward propagation. BRACE delivers a relative improvement in mean@1 on BrowseComp-Plus over the strongest baseline, runs faster per step than synchronous training, and remains stable updates off-policy.

Primary area:
reinforcement learning
Keywords:
Asynchronous Reinforcement Learning, Off-Policy Critic Correction, Bellman Residual Correction

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

The paper targets the critic in asynchronous PPO-style RL for LLMs: because the behaviour policy µ lags the target π, GAE regression converges to V^µ rather than V^π, and the paper argues that V-trace cannot provide both terminal-reward coverage and controlled weights. BRACE caps the importance-ratio product at k tokens and gives the remaining residuals a constant weight so they telescope into the behaviour-policy Monte-Carlo return. On four tasks against five actor-side baselines, BRACE is best on 13 of 16 metrics, with BrowseComp-Plus mean@1 rising from 0.245 (AReaL) to 0.269 (+9.8% relative).

Critical strengths

A simple, well-specified critic-side target with the right diagnostics. The target (Eq. 26) is one line on top of PPO and is evaluated in a production-style async pipeline across four tasks and five actor-side baselines. The paper also proposes measurable diagnostics and shows BRACE moving them in the predicted direction.

Critical weaknesses

The headline gains are not statistically supported, and the BrowseComp-Plus protocol is undisclosed. No seeds or variance are reported, so every Table 1 entry appears to be a single run. The BrowseComp-Plus number is mean@1 of one greedy sample.

The "does not transfer" claim is argued, not tested, and the closest prior constructions are neither cited nor ablated. The natural control, bootstrapped k-step V-trace (Eq. 8 with n = k), is absent, so the first stated contribution and the necessity of the Monte-Carlo tail are unsupported.

Questions for authors
  1. What is the BrowseComp-Plus training prompt set, does it overlap the evaluation questions, and is Fig. 3b's "BrowseComp-Plus accuracy" a held-out evaluation or the per-step training-batch score?
  2. How many seeds per Table 1 entry, and can you report run-to-run variance or evaluation CIs where margins over the best baseline are 0.001–0.024?
  3. Add the bootstrapped k-step V-trace control (Eq. 8 with n=k) to Fig. 4c, and PPO and the strongest actor-side baseline at S=15–50 to Fig. 4d.
2 comments
AuthorsOpenReview ↗

We would be grateful for your feedback on the added experimental controls.

Thank you again for the time you have devoted to carefully reviewing our paper. Your suggestion to include bootstrapped kk-step V-trace was particularly helpful: it made us recognize that the original ablation did not fully answer the question about the tail design. Your comments gave us a concrete direction for the additional experiments, and we have added the following controls in our response:

  • Fig. 4c adds bootstrapped V-trace with k=100k=100. Under the displayed training budget, it learns more slowly early on and continues improving later, but finishes below BRACE, providing a direct comparison relevant to the Monte-Carlo tail design.
  • Fig. 4d adds high-staleness comparisons with PPO and AReaL. In the displayed runs, PPO's training score collapses at S=15S=15; AReaL shows pronounced instability at S=30S=30 and a score collapse at S=40S=40, while BRACE maintains overall learning progress across its tested settings.

The updated figures and first-80-step view are available in our anonymous supplement. We also clarify the non-overlapping BrowseComp-Plus split of 747 training and 83 evaluation questions, confirm that Fig. 3b reports held-out accuracy, and provide four-seed BRACE statistics on BrowseComp-Plus and Search-R1 in Table R1.

If you have time to revisit our response, we would greatly appreciate your perspective on whether these additions address your concerns about the missing direct comparisons. If we have misunderstood any part of your comments or left an important point unanswered, we would welcome the opportunity to clarify it and improve the revision accordingly. Thank you again for helping us identify these gaps and for the time you have devoted to the discussion.

AuthorsOpenReview ↗

We provide additional multi-seed baseline comparisons on BrowseComp-Plus.

Our previous supplementary statistics covered only BRACE and did not fully characterize run-to-run variation in the baselines. To address this concern more directly, we have now added multi-seed statistics for PPO, PPO-EWMA, AReaL, KPop, and IcePop under the asynchronous training setup of Table 1. Each method is evaluated across four independent training seeds, and BRACE uses the four-seed statistics reported previously.

Table R3. Multi-seed comparisons on BrowseComp-Plus, measured by mean@1. "Original" refers to the single-run scores in Table 1. Sample variances use the denominator n−1n-1. The two-sided 95% Student-t CIs for the means assume approximately normal scores from independent training runs, with 3 degrees of freedom. CIs are approximate, computed from the rounded means and sample variances.

MethodOriginalTraining seedsMeanSample SDSample variance95% CI for mean
PPO0.20640.2070.0230.0005[0.171, 0.243]
PPO-EWMA0.19940.2000.0190.0003[0.172, 0.228]
AReaL0.24540.2370.0290.0008[0.192, 0.282]
KPop0.18340.1850.0250.0006[0.146, 0.224]
IcePop0.23140.2280.0220.0005[0.192, 0.264]
BRACE0.26940.2670.0220.0005[0.231, 0.303]

In this four-seed comparison, BRACE achieves the highest mean@1 among all methods, at 0.267. AReaL remains the strongest baseline by mean score, at 0.237. Based on the four-seed means, BRACE's relative improvement is approximately 12.7%, numerically higher than the 9.8% in the original single-seed comparison. The mean-score advantage therefore remains when the comparison is expanded to multiple seeds.

BRACE also has a lower sample standard deviation than AReaL, at 0.022 versus 0.029. In this set of independent training runs, BRACE thus achieves both a higher mean score and lower observed run-to-run variability. Thank you for encouraging us to complete the baseline experiments and present a fuller comparison of the methods.

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

The authors proposed an anchored Bellman-residual correction algorithm for asynchronous RL that can be used to train LLMs.

Critical strengths

BRACE outperforms existing baselines in multiple benchmarks.

Critical weaknesses

I sincerely apologize to the authors that I am unable to provide meaningful feedback on this manuscript. My primary expertise is in offline reinforcement learning, and I lack the necessary background knowledge in asynchronous LLM training. Despite my best efforts, I found myself unable to grasp the core ideas presented in the paper—a rare and surprising experience for me, as it has been quite a while since I last encountered a paper outside my domain that proved this challenging to interpret.

Questions for authors

Providing a rigorous mathematical formulation of the asynchronous RL problem would be helpful for the readers. Also, the notation VV is used without definition.

1 comment
AuthorsOpenReview ↗

We would appreciate your feedback on the clarified problem setting.

Thank you again for carefully reading our paper and openly sharing the difficulties you encountered. Your feedback helped us recognize the need to explain the connection between asynchronous training and critic learning more clearly. Our response above provides an explicit formulation of policy-version lag and clarifies the meaning of the value model VV.

From an off-policy value-learning perspective, the central problem is that training data come from an earlier policy, while the critic needs to evaluate the current policy. BRACE adjusts the critic’s training target to mitigate the value-estimation bias arising from this mismatch. We hope this explanation makes the motivation more accessible.

If you have an opportunity to revisit our response, we would be grateful to hear whether these clarifications make the problem setting and BRACE’s role clearer. If any part remains difficult to follow, please let us know which step needs further explanation. We would welcome the opportunity to clarify it and improve the presentation accordingly. Thank you for your time during the discussion.

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

This paper studies critic-side bias in asynchronous reinforcement learning for large language models. The authors argue that standard value regression on trajectories generated by stale behavior policies leads the critic to estimate the behavior-policy value function rather than that of the current policy. They further argue that conventional off-policy corrections such as V-trace face difficulties in long-horizon tasks with sparse terminal rewards, since short correction windows do not directly incorporate terminal rewards, while long windows suffer from importance-weight attenuation.

To address this, the paper proposes BRACE, which combines a bounded importance-weighted Bellman-residual correction over the first (k) policy tokens with an anchored Monte Carlo tail. This separates the horizon used for policy correction from the propagation of terminal rewards. The method is evaluated on four settings. Search-R1, BrowseComp-Plus, DAPO-Math, and tool-augmented GSM8K. BRACE outperforms the compared methods on 13 of 16 reported metrics. Ablations investigate the correction horizon, Monte Carlo tail, truncation thresholds, and policy staleness. The method preserves most of the throughput benefits of asynchronous training.

Critical strengths

The paper draws attention to critic-side policy staleness in asynchronous LLM reinforcement learning, whereas much of the existing work focuses on actor-side corrections. BRACE offers a relatively simple way to combine local off-policy correction with terminal-reward propagation without accumulating importance ratios over the entire trajectory. This looks like a great contribution because it targets an important practical setting involving long trajectories and sparse rewards.

Also, the method is evaluated on four settings covering retrieval-augmented reasoning, mathematical reasoning, and tool use. It achieves the strongest results on most reported metrics, including a 9.8% relative improvement on BrowseComp-Plus over the strongest baseline. The component ablations and staleness experiments provide additional evidence that the method is useful in practice. These results suggest that the proposed estimator deserves consideration despite the theoretical limitations discussed below.

Critical weaknesses

A central argument is that short-horizon V-trace targets fail to incorporate sparse terminal rewards. However, the analysis establishes only that the terminal reward has zero direct contribution to the current target when bootstrap values are held fixed. This does not imply that short-horizon bootstrapped methods cannot propagate terminal rewards through repeated updates or converge to the desired value function.

Furthermore, Appendix C.3 shows that BRACE generally retains behavior-policy suffix bias and truncation bias. Although I think Proposition 3 bounds a one-step operator displacement that decreases with the correction horizon, Equation (65) involves the inverse operator (I−Ak)−1(I - A_{k})^{-1}, so the result does not establish that the BRACE fixed point becomes progressively closer to the desired target-policy value. Am I missing something here? These limitations weaken the theoretical justification for the method and its claimed advantage over conventional corrections.

Additionally, despite identifying V-trace as a principal alternative, the experiments do not include a direct comparison with conventional V-trace targets across different correction horizons. All five main baselines use ordinary critic regression, making it difficult to determine whether the improvements result from BRACE's specific construction or from introducing critic-side off-policy correction more generally.

The paper does not report independent training-seed variability or confidence intervals for its main results, despite several relatively small performance differences. The proposed critic-bias diagnostics are indirect, and the paper does not directly measure critic error against independently estimated on-policy returns at matched states. Consequently, the experiments demonstrate promising downstream improvements but do not convincingly establish the proposed explanation for those improvements. I understand the computational constraints, but I would suggest selecting a subset of tasks and reporting the mean and standard deviation across multiple independent runs for the main experiments.

Questions for authors
  1. One of the main motivations for BRACE is that short-horizon V-trace targets do not directly incorporate terminal rewards. However, bootstrapped methods can propagate reward information through repeated updates, even when the terminal reward is not explicitly present in the current target. Could the authors clarify why this represents a fundamental limitation of V-trace in this setting, rather than an issue of sample efficiency or convergence speed? I think this distinction is important for understanding the motivation behind BRACE.

  2. The paper uses k=100k=100 across all tasks and reports that k=20k=20 performs similarly on BrowseComp-Plus. However, it is not clear why a fixed number of policy tokens should be appropriate across tasks with different trajectory lengths, reward structures, and levels of staleness. Is there a principled relationship between the optimal correction horizon, policy divergence, and the remaining trajectory length? Could the authors provide more insight into when a fixed kk is expected to work well?

  3. BRACE uses two separate truncation thresholds, ρˉ\bar\rho and cˉ\bar c, which influence the effective target policy and the trace weights differently. Appendix F shows that increasing either threshold can reduce performance. How should these thresholds be selected in practice, particularly as policy staleness increases? Is the observed improvement primarily due to correcting the stale-policy bias, or could much of it come from the additional regularization introduced by aggressive truncation?

  4. I think since BRACE is specifically motivated by critic bias caused by asynchronous training, I would expect its relative benefit to depend on the degree of policy mismatch. How does BRACE compare with standard GAE when the behavior and target policies are identical or nearly identical? Could the authors clarify whether the method is expected to provide any benefit in the on-policy setting, beyond differences arising from the critic optimization procedure?

Please also refer to the Critical Weaknesses section for the main questions and concerns I would like the authors to address.

5 comments
AuthorsOpenReview ↗

We would be grateful for your feedback on the added controls and clarifications.

Thank you again for the time and care you have devoted to reviewing our paper. Your comments helped us recognize where our explanation needed greater precision and where direct experimental evidence was missing. In response to your suggestions, we have added the following controls:

  • Section 1 and Fig. 4c: the added bootstrapped V-trace control with k=100k=100 achieves a lower final training score than BRACE under the evaluated budget, providing a direct comparison relevant to the MC-tail design.
  • Section 4 and Table R2: the four-seed synchronous BrowseComp-Plus comparison gives mean scores of 0.297 for GAE and 0.296 for BRACE, showing no additional mean-score advantage for BRACE in this setting.

We also provide four-seed BRACE statistics on BrowseComp-Plus and Search-R1 in Table R1. Regarding the theoretical concerns, Sections 1 and 6 clarify that our motivation concerns finite-budget learning and value tracking; we do not claim that V-trace cannot propagate terminal rewards or that Proposition 3 guarantees decreasing fixed-point error.

If you have an opportunity to revisit our response, we would be grateful for your view on whether the added V-trace comparison and theoretical clarifications address your concern about BRACE's motivation. If we have not fully addressed a concern, we would appreciate knowing which specific point still needs clarification, so that we can respond more directly. Thank you again for helping us improve the paper.

Thanks for the detailed response! Most of my concerns are addressed but one is now sharper than before. The 4-seed BrowseComp-Plus statistics undercut the abstract claim rather than supporting it. I would like to keeping my rating.

AuthorsOpenReview ↗

We provide additional multi-seed baseline comparisons on BrowseComp-Plus.

Thank you for highlighting the statistical reliability of the BrowseComp-Plus improvement. Our previous supplementary statistics covered only BRACE and did not fully characterize run-to-run variation in the baselines. To address this concern more directly, we have now added multi-seed statistics for PPO, PPO-EWMA, AReaL, KPop, and IcePop under the asynchronous training setup of Table 1. Each method is evaluated across four independent training seeds, and BRACE uses the four-seed statistics reported previously.

Table R3. Multi-seed comparisons on BrowseComp-Plus, measured by mean@1. "Original" refers to the single-run scores in Table 1. Sample variances use the denominator n−1n-1. The two-sided 95% Student-t CIs for the means assume approximately normal scores from independent training runs, with 3 degrees of freedom. CIs are approximate, computed from the rounded means and sample variances.

MethodOriginalTraining seedsMeanSample SDSample variance95% CI for mean
PPO0.20640.2070.0230.0005[0.171, 0.243]
PPO-EWMA0.19940.2000.0190.0003[0.172, 0.228]
AReaL0.24540.2370.0290.0008[0.192, 0.282]
KPop0.18340.1850.0250.0006[0.146, 0.224]
IcePop0.23140.2280.0220.0005[0.192, 0.264]
BRACE0.26940.2670.0220.0005[0.231, 0.303]

In this four-seed comparison, BRACE achieves the highest mean@1 among all methods, at 0.267. AReaL remains the strongest baseline by mean score, at 0.237. Based on the four-seed means, BRACE's relative improvement is approximately 12.7%, numerically higher than the 9.8% in the original single-seed comparison. The mean-score advantage therefore remains when the comparison is expanded to multiple seeds.

BRACE also has a lower sample standard deviation than AReaL, at 0.022 versus 0.029. In this set of independent training runs, BRACE thus achieves both a higher mean score and lower observed run-to-run variability. Thank you for encouraging us to complete the baseline experiments and present a fuller comparison of the methods.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.