Sample Complexity of On-Policy RLVR Algorithms: A Generic Analysis using Non-Uniform Smoothness and Aligned Features

We establish a generic analysis of the sample complexity of three on-policy policy-gradient algorithms for post-training large language models with verifiable rewards including RLOO, GRPO, and log-RLOO under a single framework. This framework transforms the empirical success rate of a sampled group of responses through a surrogate reward function $F$, and then perform gradient ascent to maximize the expected value of $F$. Despite the practical ubiquity of RLVR algorithms, the sample-complexity guarantees that hold \emph{uniformly across} different choices of $F$ remain limited, and recent analyses of closely related log-linear post-training models incur an unavoidable constant failure probability, so that perfect accuracy on all prompts is unattainable. Our generic analysis that covers RLOO, GRPO and log-RLOO as special cases of one weighted REINFORCE-baseline estimator, under a log-linear data model and a \emph{feature alignment condition} on the feature-difference vectors. We first show that, under this feature alignment condition, a single gradient step on one prompt never decreases the model's success probability on \emph{any} other prompt. This monotonicity lets us derive $O(1/\eps)$ iteration-complexity bounds for RLOO, GRPO, and log-RLOO, where the target accuracy $\eps \to 0$, showing convergence to perfect accuracy on \emph{every} prompt with no residual failure probability. We next construct a lower bound instance with two prompts where this alignment condition is not satisfied, and prove that on-policy REINFORCE becomes trapped in a bad region with strictly positive probability, so that convergence provably fails. These results together demonstrate the role of feature alignment in the convergence theory of post-training algorithms whose surrogate objective might be non-convex.