Theory paper: REINFORCE suffers coverage collapse needing exponential steps
nanjiang_cs · x · 2026-11-11
An arXiv paper by Audrey Huang, Nan Jiang, Sham Kakade, Sadhika Malladi, Akshay Krishnamurthy and Dylan J. Foster builds a theory of policy optimization in post-training:
- Coverage collapse: REINFORCE (basis of PPO/GRPO) can drive the probability of optimal responses to near zero even as reward improves. Assuming coverage only at t=0, convergence can require exponentially many steps; the failure persists under KL regularization and even with exact gradients.
- Reference resets: repeatedly resetting the KL reference to the most recent policy mitigates collapse. The authors formalize this as Approximate Policy Mirror Descent (APMD), a meta-algorithm solving a sequence of KL-regularized RL subproblems with convergence to global optimality.
- The paper characterizes "coverage-preserving" algorithms whose sample and gradient complexity is governed by the base model's response coverage — amplifying capabilities accessible by sampling from the base model.
The accompanying figure contrasts REINFORCE (long plateau, coverage collapse) with APMD (smooth convergence).
More from Research
- Guidelight AI publishes 10 categories of AI misbehavior for developers to detect and report — sjgadler · 2026-11-12
- CoRL 2026: papers say teleop is optional, but demo-floor humanoids still rely on it — jonstephens85 · 2026-11-12
- Probing Qwen3-8B: Action Embeddings Land on the Right Body Parts, Up to 100% — Sauers_ · 2026-11-12
- Parallel experimentation beats picking one path in AI-powered math formalization, argue researchers — xennygrimmato_ · 2026-11-12
- Structure prediction agent: an agent picks the best protein folding model and learns over time — nlarusstone · 2026-11-12
- Pretraining in the agentic era: inject multi-turn tool patterns into CPT, don't rely on NLL alone — rdesh26 · 2026-11-12