Bellman Policy Optimization

AI summary

Overview

Research area: Reinforcement learning for large language models, specifically reinforcement learning with verifiable rewards (RLVR) applied to mathematical reasoning.

Technical level: Advanced. The paper is grounded in Policy Mirror Descent, Bellman equations, and KL-divergence-based policy optimization. Readers unfamiliar with MDP formalism or trust-region policy methods will find the derivations dense, though the core intuition is accessible.

Scope: The paper derives a new critic-free policy optimization objective for RLVR and validates it empirically against four strong baselines on mathematical reasoning benchmarks.

What This Paper Is About

Training LLMs to reason with RLVR typically requires estimating how good each intermediate token is, which usually means training a separate value model that is expensive and unreliable. This paper asks whether that intermediate value estimation can be eliminated entirely by reformulating the update rule at the level of whole trajectories. The authors derive such a reformulation from first principles and turn it into a practical, implementable loss.

Key Contributions

1. A critic-free, trajectory-level reformulation of Policy Mirror Descent. For autoregressive generation with terminal rewards, the authors use the Bellman equations to show that per-token advantages telescope along a response, leaving only the terminal reward and the initial value. This yields an objective that never requires estimating values or advantages at intermediate states.

2. A proof of equivalence to the original PMD problem. Theorem 1 establishes that the reformulated objective and the advantage-based PMD objective share the same unique optimal solution on states reachable under the rollout policy, so nothing is lost in the reformulation.

3. A practical BPO loss derived through explicit approximations. Starting from the trajectory-level objective, the authors linearize it, estimate the initial value from grouped rollouts, approximate the full KL divergence with a binary KL divergence, and add smoothing plus clipping. The resulting per-token loss keeps the GRPO form but swaps the importance-sampling ratio for a smoothed mismatch-correction weight based on complementary token probabilities.

4. Empirical validation on a 30B-parameter model. Trained on Qwen3-30B-A3B-Base, BPO reaches 50.5% peak average accuracy across AIME 2024–2026, beating GRPO-ClipHigher, GSPO, CISPO, and DPPO.

Main Findings

• BPO outperforms all four baselines. Peak average accuracy of 50.5% versus 39.5% (GRPO-ClipHigher), 43.5% (GSPO), 47.4% (CISPO), and 46.4% (DPPO) — gains of 11.0, 7.0, 3.1, and 4.1 percentage points respectively.

• Best on every individual benchmark. BPO achieves 57.4% on AIME24, 41.0% on AIME25, and 53.0% on AIME26, leading all baselines in each column.

• Highest final accuracy, not just peak. After 400 training steps BPO maintains 49.4% average accuracy versus 45.5% for DPPO, the strongest baseline at the end of training.

• The weight replaces importance sampling. Rather than the rollout-to-current probability ratio used in GRPO, BPO scales each token's gradient by a smoothed ratio of complementary probabilities, (1 + ε − μ) / (1 + ε − π), capped at a constant C.

• Accuracy gains come from a change in policy loss alone. All other experimental knobs — prompts, batch sizes, response lengths, rollout-router replay — were held fixed across methods.

• Hyperparameters are not fragile. Ablations on Qwen3-4B-Base show similar performance across a broad range of smoothing and truncation settings.

Methodology in Plain English

The starting point is Policy Mirror Descent, a classical reinforcement learning update that moves the policy toward higher-value actions while penalizing how far it strays from the previous policy. Applying PMD directly to language generation is awkward because the "value" of a partial sentence is what you would need to estimate, and estimating it accurately on reasoning tasks is hard.

The authors' trick is to look at the advantage of each token — how much better taking that token is than the average token at that position. Because rewards only arrive at the end of a response, each token's advantage is just the difference in value between the next state and the current state. When you sum these differences across all tokens in a response, almost everything cancels out. What survives is the terminal reward minus the initial value of the prompt. This turns a per-state problem into a per-trajectory one.

The authors package this telescoping identity as a squared-residual objective over trajectories and prove that minimizing it gives the same optimal policy as the original PMD problem. To make it trainable, they linearize the gradient, plug in the group-mean reward as an estimate of the initial value, normalize by the group reward standard deviation (which reproduces the GRPO advantage), and replace the full reverse KL divergence with a cheaper binary approximation over the chosen token versus its complement. That last step is what produces the mismatch-correction weight, since the gradient of the binary KL term collapses neatly into a ratio of complementary probabilities. A small additive constant and a hard cap keep the weight from blowing up when the current policy assigns nearly unit probability to the chosen token.

Why This Matters

Impact on research. RLVR is currently dominated by GRPO-style methods and their variants, all of which live within the PPO clipping paradigm. BPO offers a principled derivation from mirror descent that lands on a loss of the same functional form but with a different weighting mechanism. This reframes the design space: instead of tuning clipping thresholds and importance-ratio treatments, researchers can ask what the underlying mirror-descent problem implies about the correct weight. The proof that the trajectory-level residual has the same unique optimum as advantage-based PMD also gives the RLVR community a cleaner theoretical anchor than the heuristic gradients that many current methods use.

Real-world applications.

• Mathematical and scientific reasoning assistants that need to solve competition-level problems, where BPO's AIME improvements are directly relevant.
• Code generation and verification, since reward-verifiable tasks like unit-test-passing have the same terminal-reward structure.
• Agentic tool-use pipelines, where verifiers score complete trajectories and intermediate credit assignment is hard.
• Any post-training pipeline using RLVR that currently pays the memory and compute cost of maintaining a value model alongside the policy.

Industry relevance. Removing the critic eliminates an entire model's worth of memory and engineering overhead, which matters at 30B+ parameter scale. The fact that BPO is a drop-in change to the policy loss — no new infrastructure beyond what GRPO already needs — makes adoption low-friction for teams already running RLVR. The rollout-router replay compatibility is also a practical signal that the method was designed with production training stacks in mind.

Future Directions

• Scaling beyond 30B parameters. The experiments use a single base model; whether the gains persist at 100B+ scale, or on models with different architecture families, remains open.

• Extending beyond terminal rewards. The derivation depends on intermediate rewards being zero. Domains with dense or stepwise rewards — process supervision, multi-turn interactions — would need a modified reformulation.

• Understanding why CISPO is the closest competitor. The 3.1-point gap over CISPO is the smallest of the four, and the paper does not analyze what CISPO's clipping scheme shares with the mismatch-correction weight. A theoretical comparison could illuminate which component drives the gain.

• Tuning the cap C and smoothing ε more systematically. The current ablations cover robustness on a 4B model, but a principled rule for setting these from rollout statistics — rather than grid search — would strengthen the method's practical story.

• Comparison with learned-critic methods. The paper argues critics are expensive and inaccurate on reasoning tasks but does not include a value-model baseline in the experiments, leaving the critic-free claim untested against a strong critic-based alternative.

Target Audience

Researchers and engineers working on post-training for large language models, particularly those implementing or extending GRPO-style RLVR pipelines. The theoretical sections will be most valuable to readers comfortable with Markov decision processes, mirror descent, and policy gradient derivations. Practitioners who mainly care about outcomes can focus on Section 3's loss definition, the hyperparameter guidance, and the experimental results, since the practical BPO loss is a small, self-contained modification of the GRPO per-token loss.

Authors’ abstract

Reinforcement learning with verifiable rewards (RLVR) improves the reasoning capabilities of large language models (LLMs). We introduce Bellman Policy Optimization (BPO), a critic-free method derived from Policy Mirror Descent (PMD). For autoregressive generation with terminal rewards, BPO uses the Bellman equations to reformulate PMD as a trajectory-level objective. The reformulation avoids estimating state values at intermediate states. We prove that it has the same unique optimal solution as the original PMD objective. We derive the practical BPO loss by approximating this objective. Its mismatch-correction weight is a smoothed ratio of complementary token probabilities. Experiments on mathematical reasoning benchmarks demonstrate the effectiveness of BPO.