Technical Summary: MDP-GRPO

Problem Statement

Large Language Models (LLMs) often struggle with multi-constraint instruction following, where a single prompt requires adherence to multiple explicit, deterministic rules (e.g., specific formatting, forbidden words, exact endings). While Reinforcement Learning with Verifiable Rewards (RLVR) offers a promising solution by using rule-based checkers to provide reliable, bias-free signals, standard Group Relative Policy Optimization (GRPO) becomes unstable in this regime.

The core issue arises because multi-constraint rewards are discrete and frequently low-variance. In early training or with strict constraints, groups of sampled completions often yield homogeneous rewards (all samples satisfy or violate the same constraints). Under these conditions, standard GRPO's z-score group normalization suffers from three specific pathologies:

1. Low-Variance Amplification: Minor reward fluctuations are inflated into disproportionately large advantages, causing brittle updates.
2. Mean-Centering Blindness: Z-score normalization discards absolute reward levels, making it impossible to distinguish between a group that consistently fails and one that consistently succeeds if their relative distributions are similar.
3. Zero-Variance Collapse: When all samples in a group receive identical rewards, the group standard deviation ($\sigma_{group}$) approaches zero. This causes the advantage signal to collapse to zero or become undefined, eliminating the learning signal entirely.

Methodology: MDP-GRPO

To address these instabilities, the authors propose MDP-GRPO, a stabilized variant of GRPO that integrates three complementary mechanisms:

1. Multi-Temperature Sampling (Prevention)

To prevent the formation of homogeneous groups, the method replaces fixed-temperature sampling with a temperature schedule ($T = [\tau_1, \dots, \tau_G]$) for the group of $G$ completions.

• Mechanism: Lower temperatures encourage exploitation (high-quality baselines), while higher temperatures induce exploration.
• Goal: This mixes high-quality and exploratory completions within a single group, ensuring sufficient reward dispersion ($\sigma_{group} > 0$) even with small batch sizes, without altering the underlying RL objective.

2. Dual-Anchor Advantages (Signal Restoration)

To address zero-variance collapse and mean-centering blindness, the method introduces a goal-aware anchor alongside the standard group-relative advantage.

• Mechanism: A neutral baseline is modeled as a binomial process where constraints are satisfied with probability $p=0.5$. This yields a fixed "goal-aware" advantage ($\delta_i$) that scales with the number of constraints.
• Integration: The final advantage ($A_i$) is a weighted interpolation between the shaped group-relative advantage ($\tilde{z}_i$) and the shaped goal-aware advantage ($\tilde{\delta}_i$):
  $$A_i = (1 - \alpha)\tilde{z}_i + \alpha\tilde{\delta}_i$$
• Benefit: Even when group variance is zero, the goal-aware anchor provides a valid learning signal, preventing training stagnation.

3. Prospect-Theoretic Shaping (Stabilization)

Inspired by Prospect Theory (Kahneman & Tversky, 1979), the method applies a bounded, asymmetric shaping function to the raw advantages before mixing.

• Mechanism: A scaled tanh transformation bounds the advantages and enforces loss aversion ($\lambda_- > \lambda_+$).
• Goal: This ensures that constraint violations (negative outcomes) result in larger gradient updates than equivalent successes, heavily penalizing regression. Simultaneously, the bounding function prevents unbounded gradients caused by low variance, stabilizing training.

4. Asymmetric KL Regularization

The objective includes an asymmetric KL penalty where the penalty coefficient is higher ($\beta_{high}$) when the advantage is negative (performance dropping) and lower ($\beta_{low}$) when positive, further constraining the model during regression.

Key Contributions

1. Formalization of Pathologies: The paper identifies and formalizes three failure modes of group-relative policy updates in discrete, low-dispersion reward regimes: low-variance amplification, mean-centering blindness, and zero-variance collapse.
2. Prevention via Sampling: Introduction of multi-temperature group sampling to artificially increase reward diversity in small-batch settings without changing the objective function.
3. Signal Recovery: Proposal of dual-anchor advantages to restore learning signals in zero-variance groups and recover absolute performance information lost in standard normalization.
4. Robust Shaping: Application of prospect-theoretic shaping to bound update magnitudes and prioritize the correction of constraint violations.
5. Empirical Validation: Demonstration that these components collectively improve stability and performance on multi-constraint tasks while preserving general capabilities.

Experimental Results

The method was evaluated on IFEval, FollowBench, and a curated multi-constraint dataset using Gemma-2-2B and Llama-3.2-3B models.

• Performance Gains: MDP-GRPO consistently outperformed standard GRPO and the zero-shot baseline. On Llama-3.2-3B, it improved strict constraint satisfaction (HSR) by up to 5.0% on the custom dataset.
• Small-Batch Efficiency: The method proved particularly effective with reduced group sizes ($G=4$). Multi-temperature sampling allowed MDP-GRPO to approach the performance of standard GRPO trained with larger groups ($G=8$), demonstrating its utility under tight compute budgets.
• Difficulty Scaling: Stabilized variants (specifically those with Dual Anchors) degraded more slowly than baselines as the number of constraints increased, maintaining higher success rates on complex prompts (Difficulty 5-6).
• General Capabilities: Evaluations on MMLU and ARC confirmed that gains in instruction following did not come at the expense of general reasoning or knowledge retention.
• Training Dynamics: Diagnostics showed that the proposed methods successfully reduced the frequency of zero-variance groups and controlled KL divergence drift compared to standard GRPO.

Significance and Claims

The authors claim that MDP-GRPO provides a stable and reliable framework for RLVR in multi-constraint settings, a domain where standard group-normalization methods often fail due to reward sparsity. By explicitly addressing the mathematical pathologies of z-score normalization, the method enables:

• Stable convergence even with small group sizes.
• Effective learning from discrete, rule-based rewards without requiring learned reward models or human preference labels.
• Robustness against the "brittleness" of standard GRPO updates when faced with homogeneous reward distributions.

The paper concludes that while the approach is specifically designed for deterministic, verifiable constraints, its core components (dual anchoring and prospect shaping) are agnostic to the reward source and could be adapted to other RL settings. However, the authors modestly note that the method relies on automatic checkers and may not directly extend to subjective or stylistic constraints without learned reward models.