Protected Group-Relative Policy Gradients: Convergence with Informative Completion Times

Parallel policy optimization can discard slow trajectories to reduce the time per update. If completion time and the learning signal are statistically dependent, discarding slow trajectories can make the expected update differ from the true policy gradient. At each iteration, we generate trajectories using the current policy and use both the earliest completions and all trajectories independently protected from cancellation. After these trajectories finish, we update the policy using a group- relative gradient corrected for the probability of retaining each pair. We derive a variance bound separating full-group sampling noise from selective-observation error, and an exact distribution for the duration of a protected group. These yield bounds on the number of iterations and the expected computation time needed to obtain an approximately stationary point. Extensions cover gradient-dependent noise and explicitly bounded probability-estimation error. The iteration rate is the standard stochastic-gradient rate. We study how trajectory selection affects gradient variance and computation time. An experiment with fixed Qwen3-0.6B parameters compares gradient estimates and uses generated-token steps to quantify completion cost, without measuring online training speed. Extending the theory to updates made while other trajectories are still running, and quantifying the data and computation needed to estimate pair-retention probabilities, remain open problems.