PaperlayerView exact revision on arXiv

Source-linked AI summary

Bellman Policy Optimization

Zhuoqing Song, Haotian Xu, Xikun Zhang, Lidong Bing

arXiv:2609.15987v1cs.LGcs.CLmath.OC

TL;DR

Policy optimization choices affect RLVR reasoning performance and training stability, while directly applying PMD to language generation requires intermediate-state value estimates. BPO uses Bellman equations to derive a critic-free trajectory objective and a practical approximated loss; on AIME 2024–2026 it reaches 50.5% peak average accuracy, outperforming four baselines.

  • Problem

    Policy optimization choices affect reasoning performance and training stability, while directly applying PMD to language generation requires intermediate-state value estimates.

    Source: §1 · p. 1

  • Method

    BPO uses Bellman equations to reformulate PMD as a critic-free trajectory-level objective, then approximates it with a practical loss using a smoothed mismatch-correction weight.

    Source: §1 · pp. 1–2

  • Results

    50.5% peak average accuracy across AIME 2024–2026, exceeding GRPO-ClipHigher, GSPO, CISPO, and DPPO by 3.1–11.0 percentage points.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The reformulation avoids intermediate-state value estimates while retaining the original PMD objective’s unique optimum on states reachable under the rollout policy.

    Source: §1 · pp. 2–3

    The analysis assumes a uniform prompt distribution for simplicity, though it extends to more general prompt distributions, and assumes terminal rewards satisfy |R(x, y)| ≤ 1.

    Source: §2.2 · pp. 3–4

Abstract

from arXiv · show

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.

1 Introduction

BPO reformulates Policy Mirror Descent for terminal-reward language generation without intermediate-state value estimates, then approximates the objective with a practical loss. On mathematical reasoning benchmarks, it outperforms four policy-loss baselines.

1 Introduction

  • Policy-optimization choices can substantially affect reasoning performance and training stability, while directly applying PMD to language generation requires intermediate-state value estimates.Learned value models add memory and computational costs and can be inaccurate on reasoning tasks.Source: §1 · p. 1
  • BPO uses Bellman equations to reformulate PMD as a trajectory-level objective, avoiding intermediate-state value estimates while retaining the same unique optimum on rollout-reachable states.The reformulation is for autoregressive generation with terminal rewards.Source: §1 · pp. 1–3
  • 50.5% peak average accuracy across AIME 2024–2026; BPO exceeds GRPO-ClipHigher, GSPO, CISPO, and DPPO by 3.1–11.0 percentage points.The comparison uses Qwen3-30B-A3B-Base; Figure 1 plots accuracy during training.Source: Figure 1 · p. 2, §1 · pp. 2–3
  • The practical BPO loss approximates this objective and replaces GRPO’s importance-sampling ratio with a smoothed ratio of complementary token probabilities.The weight uses additive smoothing for numerical stability.Source: §1 · pp. 2–3

2 Preliminaries

The preliminaries define the token-sequence and episodic-MDP setting, review GRPO and terminal-reward Bellman values, and introduce PMD and a binary-KL approximation to full KL divergence.

2.1 Notation

  • The notation treats prompts and responses as token sequences, with y_{t:u} denoting a response subsequence and concatenation written as a tuple.Response length may vary across responses.Source: §2.1 · p. 3

2.2 RLVR as an Episodic MDP

  • RLVR is modeled as a finite-horizon episodic MDP: states are prompts plus generated prefixes, tokens are actions, and a verifier assigns terminal rewards.The prompt distribution is assumed uniform for simplicity, and the analysis extends to more general prompt distributions.Source: §2.2 · pp. 3–4

2.3 Group-Relative Policy Optimization

  • GRPO samples response groups per prompt, normalizes rewards into group-relative advantages, and applies PPO-style clipping to token-level importance ratios.Under outcome supervision, all tokens in a response share the same advantage.Source: §2.3 · p. 4

2.4 Bellman Equations with Terminal Rewards

  • With zero intermediate rewards, Bellman equations relate intermediate values to expected downstream rewards and set the complete response’s terminal value to its verifier reward.The initial value is the expected reward for the prompt under the policy.Source: §2.4 · pp. 4–5

2.5 Policy Mirror Descent

  • PMD optimizes a policy separately at each state using a real-valued state-action function, a behavior policy, and a positive step size; the stated solution is unique.Source: §2.5 · p. 5

2.6 Binary KL Divergence

  • Binary KL partitions the action space into a selected token and its complement, yielding a lower bound on the full KL divergence.Computing full KL can require logits for the entire vocabulary and be costly.Source: §2.6 · p. 6

3 Bellman Policy Optimization

BPO derives a critic-free, trajectory-level reformulation of PMD for terminal-reward generation, then approximates it to produce a practical token-level loss. The reformulation avoids intermediate-state value estimates while preserving PMD’s unique optimal solution on reachable states.

3 Bellman Policy Optimization

  • The BPO token-level loss retains GRPO’s form but replaces its importance-sampling ratio with a truncated mismatch-correction weight.The practical approximation also uses a binary KL approximation, smoothing, masking, and clipping.Source: §3 · p. 6, §3.2 · p. 9

3.1 Critic-Free Reformulation of Policy Mirror Descent

  • Bellman telescoping yields a trajectory-level PMD objective using terminal reward and prompt-level expected reward, without intermediate-state value estimates.The objective and original PMD have the same unique optimal solution, inducing the same completion distribution for each prompt.Source: §3.1 · pp. 7–8

3.2 Practical Approximation

  • The practical approximation linearizes the squared-residual objective and estimates the initial value and prompt-dependent scaling from grouped rollouts.It also replaces full reverse KL with binary KL and applies smoothing, masking, and clipping.Source: §3.2 · p. 9

4 Experiments

Experiments compare BPO with four methods on Qwen3-30B-A3B-Base trained on DAPO-Math-17k, using identical settings. BPO leads the reported AIME averages at peak mean accuracy and after 400 training steps.

4.1 Experimental Setup

  • The controlled comparison trains Qwen3-30B-A3B-Base on the English subset of DAPO-Math-17k and varies only the policy loss.Evaluation covers AIME24, AIME25, and AIME26; reported average accuracy is the arithmetic mean of their Avg@32 scores.Source: §4.1 · p. 10

4.2 Main Results

  • 50.5% average accuracy for BPO versus 39.5% for GRPO-ClipHigher and 47.4% for CISPO, the strongest baseline; BPO also leads all three benchmarks.Table 1 reports scores at each method’s checkpoint with the highest mean accuracy across the three benchmarks.Source: §4.2 · p. 10, Table 1 · p. 11
  • 49.4% average accuracy for BPO versus 45.5% for DPPO, the strongest baseline after 400 training steps.BPO has the highest final accuracy in Figure 1.Source: §4.2 · p. 10

5 Conclusion

The conclusion presents BPO as a critic-free PMD method whose Bellman-based trajectory objective avoids intermediate value estimation while retaining PMD’s unique optimum. It reports higher AIME accuracy than four baselines and similar performance across several smoothing and truncation settings in a smaller-model ablation.

5 Conclusion

  • BPO uses a critic-free, trajectory-level PMD reformulation for terminal-reward generation, avoiding intermediate state values while preserving the unique optimum on reachable states.Its practical token-level loss uses a smoothed mismatch-correction weight instead of the importance-sampling ratio.Source: §5 · p. 11
  • 50.5% peak average accuracy across AIME 2024–2026 on Qwen3-30B-A3B-Base, exceeding GRPO-ClipHigher, GSPO, CISPO, and DPPO by 3.1–11.0 percentage points.The conclusion also reports similar performance across smoothing and truncation settings in Qwen3-4B-Base ablations.Source: §5 · p. 11

A.1 Proof of Theorem 1

The proof establishes a zero-valued minimum for the trajectory-level objective and develops the necessity argument on states reachable under the rollout policy. It also introduces a binary KL divergence in the proof of identity (27).

A.1 Proof of Theorem 1

  • The PMD update preserves rollout-policy support, making it feasible for objective (18); nonnegativity then gives a minimum value of zero.Source: §A.1 · p. 14
  • The proof sets the termination time τ and defines a filtration from generated tokens through t∧τ, with states S_t=(x,Y_<t) when t≤τ.Source: §A.1 · p. 15
  • The necessity argument uses positive-probability state-action events and almost-sure vanishing of D_t to derive a condition that is independent of the action.Source: §A.1 · pp. 15–16

A.2 Proof of the Identity (27)

  • The proof of identity (27) introduces the binary KL divergence associated with action y at a fixed state.Source: §A.2 · p. 16

B Experimental Details

The experiments use shared optimization settings across methods, evaluate checkpoints periodically on three AIME benchmarks, and report selected best-checkpoint results. Baseline-specific configurations and BPO’s default hyperparameters are also specified.

B Experimental Details

  • All methods share AdamW settings, centered and normalized advantages, seq-mean-token-mean aggregation, and no KL penalty or entropy bonus.The learning rate is 10^-6, with gradient clipping threshold 1.0.Source: B Experimental Details · p. 17
  • Evaluation estimates Pass@1 with Avg@32 on AIME24, AIME25, and AIME26, averaging the three benchmark scores and selecting the checkpoint with the highest mean.Evaluation occurs every ten rollout batches; ties select the earlier step.Source: B Experimental Details · p. 17
  • The baselines use specified clipping or importance-weight settings, while BPO uses default ϵ = 0.1 and C = 3.0 in the main experiments.Source: B Experimental Details · p. 17

C Ablation Studies

The ablations vary one BPO hyperparameter at a time on Qwen3-4B-Base, using a shared training setup and GRPO-ClipHigher baseline.

C Ablation Studies

  • Each sweep changes only one hyperparameter on Qwen3-4B-Base over 1000 training steps, with 128 prompts and 16 responses per prompt, and shares the GRPO-ClipHigher baseline.The 2048 responses are split into four minibatches; the maximum response length is 8192 tokens.Source: C Ablation Studies · p. 17

C.1 Sensitivity to ϵ

With C fixed at 3.0, BPO’s average accuracy is similar across ϵ values from 0.05 to 0.2 and exceeds GRPO-ClipHigher at all four tested settings. At ϵ = 0.3, accuracy is lower but remains above the baseline.

C.1 Sensitivity to ϵ

  • The sweep fixes C = 3.0 and varies ϵ over {0.05, 0.1, 0.2, 0.3}.Source: §C.1 · p. 17
  • 25.4%–25.8% average accuracy is reported for ϵ ∈ {0.05, 0.1, 0.2}; at ϵ = 0.3, accuracy is 24.1%, still 3.6 percentage points above GRPO-ClipHigher.BPO outperforms the baseline at all four settings.Source: §C.1 · p. 17
  • Figure 2 plots mean Avg@32 across AIME24–26 for each ϵ setting, with dashed lines marking each curve’s peak.Source: Figure 2 · p. 18
  • Table 2 reports AIME Avg@32 (%) by ϵ, with each row taken at the checkpoint with the highest mean accuracy across the three benchmarks.Source: Table 2 · p. 18

C.2 Sensitivity to C

With ϵ fixed at 0.1, the section tests BPO’s sensitivity to truncation parameter C and reports only a 0.5-percentage-point spread in average accuracy across the three tested values.

C.2 Sensitivity to C

  • The ablation fixes ϵ at 0.1 and tests C values of 2.0, 3.0, and 4.0.Source: §C.2 · p. 19
  • Figure 3 plots mean Avg@32 across AIME24–26, with dashed lines marking each curve’s peak.Source: Figure 3 · p. 19
  • Table 3 reports AIME Avg@32 (%) at each setting’s highest-mean checkpoint, with the best result in each column bolded.Source: Table 3 · p. 19
  • 25.3%–25.8% average accuracy across C=2.0, 3.0, and 4.0 is a 0.5-percentage-point spread.The results show BPO is insensitive to C over this range.Source: §C.2 · p. 19

Related papers

Loading 2609.15987v1…