- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper proposes Bellman Policy Optimization (BPO), a critic-free policy optimization method for RLVR. The starting point is Policy Mirror Descent (PMD), whose update requires advantage estimates at every intermediate token. Using the Bellman equation and the terminal-reward structure of autoregressive generation, the authors rewrite PMD as a trajectory-level least-squares objective that only involves the final reward and the prompt-level value, and prove that it has the same unique optimal solution as PMD. They then derive a practical loss through a sequence of approximations. Experiments demonstrate the effectiveness of the proposed method.
Critical strengths
- The derivation builds on two fairly elementary observations: the log-partition function can be replaced by , and the token-level advantages telescope to . Similar likelihood-ratio reparameterizations already appear in the direct-alignment literature (e.g., DPO and its token-level variants), so these steps are not new in themselves. The interesting part is the martingale argument in the necessity part of Theorem 1. Note that a zero trajectory-level residual does not by itself imply a zero residual at each token, since positive and negative terms may cancel along a response. This point is handled by observing that, under the rollout policy , each token-level residual has zero conditional mean given the preceding tokens, so that the partial sums of the token-level residuals form a martingale. Because the response length is bounded by , the martingale property implies that every partial sum equals the terminal value, which is zero, and hence every token-level residual vanishes. In this sense, the trajectory-level objective recovers the PMD update at each token, rather than only on average over a response.
- From an implementation perspective, the resulting method is simple. Compared with GRPO, the importance-sampling ratio is replaced by the weight , truncated at a constant , while the group-normalized advantage and the clipping mask are kept unchanged. In practice this amounts to modifying only a few lines of code. Note that no value model is introduced and no additional forward pass is required, since the weight depends only on the probabilities of the sampled token, which are already available in GRPO. Therefore, the method can be readily incorporated into existing RLVR pipelines and compared against GRPO under identical settings.
Critical weaknesses
-
Relation to Kimi k1.5 and VIMPO. Objective (18) is nearly identical in form to two existing methods, neither of which is compared against. Written side by side (with and the group-mean reward), the residuals are:
- Kimi k1.5 (arXiv:2501.12599):
- VIMPO (arXiv:2606.20008, cited as [11]):
- BPO, Eq. (18):
All three minimize the squared residual over sampled responses. Thus BPO differs from Kimi k1.5 only by the per-token KL term, and from VIMPO mainly in the anchor policy ( versus ) and the direction of the KL term. The authors should explain what these differences bring, both in theory (e.g., whether they change the target policy, and whether Theorem 1 would still hold without them) and in practice (whether these differences survive the linearization in Section 3.2, since BPO ultimately optimizes a linearized surrogate, whereas Kimi k1.5 and VIMPO optimize the squared loss directly). Both methods should also be included as baselines under the same settings.
-
Binary KL approximation. Most approximations in Section 3.2 are standard, but replacing the full KL with its binary version is, at least to me, less common, and this is the step that yields the weight . The only justification is that the binary KL lower-bounds the full KL, which says little about how close their gradients are. The authors should justify this step and compare it with a more faithful alternative, e.g., a top- approximation of the full KL.
Questions for authors
see weakness
5 comments
Response to Reviewer FBwz (Part 2)
W2
Binary KL approximation. Most approximations in Section 3.2 are standard, but replacing the full KL with its binary version is, at least to me, less common, and this is the step that yields the weight . The only justification is that the binary KL lower-bounds the full KL, which says little about how close their gradients are. The authors should justify this step and compare it with a more faithful alternative, e.g., a top- approximation of the full KL.
Thank you for this comment.
Efficiency. Our primary consideration for the binary KL approximation is efficiency. The binary KL approximation only requires and of the sampled token . It requires neither storing the top-k tokens of the rollout engine nor computing the KL divergence over the full vocabulary.
Instability of both approximations. Both the top-k and the binary approximations involve ratios that can become very large. The top-k approximation keeps and the most probable tokens under , and aggregates all remaining tokens into a single category "other". The gradient of involves the ratio , which can become very large when and introduce large noise into the update. Similarly, the weight given by the binary approximation can become very large when , and we have observed this value above for some tokens.
Binary KL approximation fits the unified framework. An advantage of the binary approximation is that it gives a single ratio. We mitigate its instability by the smoothing, and by substituting the smoothed weight for the importance-sampling ratio in the unified RLVR framework , where is the clipping mask and caps the ratio. GRPO, CISPO, and DPPO are instances of the unified framework that differ only in and
In contrast, the gradient of the top-k KL divergence involves the ratio for every token in the top-k set and for "other", together with the gradients of the log-probabilities of all tokens in the top-k set. It is therefore not of the form of the unified framework, where a single weight multiplies . How to apply smoothing and clipping to the top-k KL divergence is not straightforward, and we leave it for future study
Moreover, the top-k approximation requires storing the top-k tokens of the rollout engine, which adds computation and storage cost. On Qwen3-30B-A3B-Base with 32 GPUs, the wall-clock time to reach step 199 is 33.8 hours for BPO, compared with 56.8 hours for BPO (Top-16 KL Approx) and 152.6 hours for BPO (Top-128 KL Approx). Therefore, we choose the binary KL approximation
Ablation on . We train Qwen3-4B-Base in the same setting as in W1 and report Avg@32 after 200 training steps. BPO () denotes the practical BPO loss with
| AIME24 | AIME25 | AIME26 | AIME24-26 Avg. | |
|---|---|---|---|---|
| BPO | 25.3 | 21.9 | 24.3 | |
| BPO () | 27.0 | |||
| GRPO-ClipHigher | 19.0 | 18.4 | 13.6 | 17.0 |
Appendix H.1 and H.2 of our original submission further vary over and over . These results show that BPO is insensitive to and , and the smoothing slightly improves the average accuracy. We therefore keep the smoothing in the large-scale experiments on Qwen3-30B-A3B-Base
Comparison with the top-k approximation. Our original submission already compares BPO with the top-k approximation on Qwen3-30B-A3B-Base (Appendix H.5, Table 9). The table below reports Avg@32 after 200 steps
| AMC23 | AIME24 | AIME25 | AIME26 | HMMT25 | HMMT26 | Avg. | |
|---|---|---|---|---|---|---|---|
| BPO | 93.5 | 53.2 | 35.8 | 45.7 | 16.6 | 11.8 | 42.8 |
| BPO (Top-16 KL Approx) | 84.7 | 45.7 | 31.9 | 39.0 | 11.3 | 8.6 | 36.9 |
| BPO (Top-128 KL Approx) |
These results are expected from the above analysis. The binary approximation fits the unified framework, whose clipping improves stability, and the smoothing slightly improves the average accuracy (in the ablation on Qwen3-4B-Base). The top-k approximation does not fit the unified framework, and it is unclear how to apply smoothing and clipping to it, so the noise from the tail probability is harder to remove
In summary, considering both performance and efficiency, we choose the binary KL approximation
Thank you for clarification
Response to Reviewer FBwz (Part 1)
Thank you for your comments. We have addressed all your concerns below.
W1
Thank you for this comment.
Experiments. Following the reviewer's suggestion, we compare BPO with Kimi k1.5 and VIMPO on Qwen3-4B-Base (batch size 128, group size 16, maximum response length 8k, i.e., the setting in Table 3). BPO (PMD equivalent) denotes the unlinearized critic-free objective, which has the same optimal solution as PMD (Theorem 1). For VIMPO, we compare with two variants. VIMPO denotes the main algorithm of VIMPO (Eq. (12) of VIMPO) with cA=5×10−3, the setting used in VIMPO. VIMPO (cA=0) denotes the operational form of the value-loss component of VIMPO (Eq. (8) of VIMPO), which is equivalent to the main algorithm of VIMPO with cA=0. We report Avg@32 after 200 training steps
BPO achieves the highest average accuracy, 2.0 percentage points higher than Kimi k1.5. Both BPO and BPO (PMD equivalent) outperform Kimi k1.5, VIMPO, and VIMPO (cA=0) in average accuracy.
Theory: BPO, Kimi k1.5, and VIMPO have fundamentally different theoretical foundations. For notational simplicity, let η=1/τ.
The key difference lies in the log-partition function. Kimi k1.5 has a single sequence-level term τlogZ(x) and approximates it by the group-mean reward Rˉ, which is accurate only as τ→∞. BPO has a log-partition function logZμ(st) at every state, and we show in our submission that logZμ(st)=KL(μ(⋅∣st)∥π+(⋅∣st)). In VIMPO, the corresponding term −βsg[KL(π∥πref)] is defined with respect to πref, and has the opposite sign and the opposite KL direction to the BPO term +KL(μ∥π).
Therefore, BPO is fundamentally different from Kimi k1.5 and VIMPO in theory.