Bellman Policy Optimization

Bellman Policy Optimization. By Zhuoqing Song and three others, from Apodex and Princeton University. Published on the fourteenth of September. No code repository is linked to it.

Reinforcement learning with verifiable rewards, or RLVR, improves the reasoning of large language models. Policy Mirror Descent, or PMD, offers one principled route for that kind of optimization. But when a model generates text token by token and is rewarded only at the end, a direct treatment would involve estimating how good each intermediate state is, and that is the step this work sets out to avoid.

Bellman Policy Optimization, or BPO, is a critic-free method derived from PMD. For autoregressive generation with terminal rewards, it uses the Bellman equations to reformulate the PMD objective at the level of whole trajectories. Working at the trajectory level is what removes the need to estimate values at intermediate states, and it is why no critic is required.

The authors prove that this trajectory-level objective has the same unique optimal solution as the original PMD objective, so the reformulation changes how the problem is posed without changing its answer. The practical BPO loss is then derived by approximating that objective. One detail of the loss is stated explicitly: its mismatch-correction weight is a smoothed ratio of complementary token probabilities.

Experiments on mathematical reasoning benchmarks demonstrate the method's effectiveness.

The path from principle to practice is short and each step is named. Start from PMD, rewrite it with the Bellman equations so it lives at the level of trajectories, show nothing about the optimum was lost, then approximate for a usable loss. The payoff is an RLVR method with no critic and no intermediate value estimates.