Most practical policy-optimization methods for reinforcement learning follow the same loop. They collect a batch of experience, then run a few gradient steps on a "surrogate" objective built from that batch, and repeat. The number of inner steps is almost always fixed by hand. It is 10 in Mirror Descent Policy Optimization, and some fixed number of epochs in PPO. This note proposes a different rule. Keep taking inner steps only while the batch still contains a statistically detectable improvement direction, and stop once the remaining gradient is indistinguishable from sampling noise. The test uses only per-sample gradients that the learner already computes, so it needs no extra environment interaction and no held-out data.
The reason this bears on sample efficiency is simple. If the learner takes too few inner steps, each costly batch of environment interaction goes under-used. If it takes too many, the policy fits the noise in that particular batch, gets worse, and the next batches are spent repairing the damage. The right number of steps plausibly varies across environments and across training. A fixed count, or a fixed limit on how far the policy may move, cannot follow that variation. We borrow the central idea of inexact optimization, that each inner problem should be solved only to a tolerance matched to the errors elsewhere in the algorithm. We then set that tolerance to the one error that dominates in reinforcement learning: the statistical noise of the batch.
Core Claim
Treat each policy update as an inexact solve of a proximal subproblem, meaning a problem that rewards improvement while penalizing distance from the current policy. Stop the inner solve once the batch gradient's norm falls to the level of its own estimated noise. On continuous-control benchmarks, this should match or beat the best per-environment hand-tuned inner step count, with no tuning. It should also beat PPO's early stopping on a target KL divergence (a measure of how far the policy has moved), at equal environment steps.
The stopping rule is a gradient "norm test." Let $\hat L_k$ be the empirical surrogate at outer iteration $k$, built from $n$ samples: the linearized advantage objective plus a KL proximity term, as in MDPO. Let $\theta_j$ be the policy parameters after $j$ inner steps, and let $\hat\Sigma_j$ be the empirical covariance of the per-sample gradients of $\hat L_k$ at $\theta_j$. We stop at the first $j$ satisfying
$$\|\nabla \hat L_k(\theta_j)\|^2 \le c\,\frac{\operatorname{tr}(\hat\Sigma_j)}{n},$$
where $c$ is a single constant near 1. The right-hand side is the expected squared norm of a pure-noise mean gradient over $n$ samples. The rule therefore says: stop when the remaining gradient is about as large as noise alone would produce. The tolerance changes automatically across training. When the critic is poor and advantages are noisy, $\hat\Sigma_j$ is large and the update stops early. When the batch is informative, the update runs longer.
Relation to Prior Work
Three papers motivate the proposal. Mirror Descent Policy Optimization casts policy iteration as a sequence of trust-region subproblems solved approximately by $m$ inner gradient steps. It reports $m=10$ as a "sweet spot" for on-policy tasks, and it also notes that too few steps under-improve while too many degrade performance. That degradation is what we interpret as fitting batch noise. We keep MDPO's subproblem and replace the fixed $m$ with the noise-matched test.
Policy Mirror Descent for Regularized Reinforcement Learning proves, for tabular problems, linear convergence to an error floor set by the sum of policy-evaluation error and policy-update error. Its result implies that solving the update far more precisely than evaluation is accurate buys nothing. We turn that observation into an online rule; that paper states no rule of this kind.
The classical inexact-optimization results supply the method's logic. Inexact first-order primal-dual algorithms keeps optimal rates by tying the inner tolerance to the outer iteration count. New inertial proximal gradient methods requires the errors to be summable. Both assume the inexactness criterion can be checked, and Global complexity analysis of inexact successive quadratic approximation methods points out that such checks are often impossible when the true minimizer is unknown. Our criterion avoids that difficulty because it refers only to observable per-sample gradient statistics, not to the unknown minimizer.
We do not claim summable errors. The tolerance tracks the statistical floor, which need not decay. This is a deliberate departure, justified by the error-floor result above.
Two further papers constrain and neighbor the design. Generalized Proximal Policy Optimization with Sample Reuse adapts the learning rate so that an estimated total-variation distance stays near a target. That rule controls how far the policy moves, not whether the movement is supported by the data. ESPO stops rollouts early, based on the critic's value estimates, to save tokens in language-model reasoning. That is early stopping on the data-collection side, whereas ours is on the optimization side.
On the theory side, Sample Complexity of Neural Policy Mirror Descent on low-dimensional manifolds bounds sample complexity for neural actors with discrete actions. It controls update error through network size, not inner stopping. Our continuous-action setting and our stopping rule are both outside its analysis.
Research Program
The work has three parts.
Mechanism. We implement noise-matched stopping inside MDPO with a KL proximity term, and inside PPO in place of its fixed epoch count. Per-sample gradient norms are cheap for the small policy networks used on MuJoCo. We compute them either exactly, through per-example gradients, or from a trace estimate over minibatches.
Diagnostic study. We test the premise directly. At a set of checkpoints, we run long inner loops and measure the true surrogate improvement after each inner step, using a large fresh batch collected from the same policy. This yields the empirical curve of step count versus true improvement. We then ask whether the stopping point chosen by the rule falls near the peak of that curve, and whether the peak moves across environments and across training stages. If the peak barely moves, a fixed $m$ is adequate and the proposal loses its reason to exist. We would report that outcome as a finding.
Analysis. In the tabular and linear-function-approximation settings covered by the generalized policy mirror descent analysis, we would plug the noise-matched tolerance into its error-floor bound. The goal is to show that the update error stays within a constant factor of the evaluation error, so the rule never raises the floor. We also want to show that the expected number of inner steps is bounded by the batch's signal-to-noise ratio. Deriving full neural sample-complexity rates is out of scope.
Baselines
Naive reference: MDPO with $m=1$. This is a single gradient step per batch, the plain regularized policy gradient. It sets the floor for how much a batch can yield with no inner solve at all.
Fixed-count MDPO: $m=10$ and oracle-tuned $m$. The first is MDPO at its published setting of 10 inner steps, from Mirror Descent Policy Optimization. The second is MDPO with $m$ tuned separately for each environment over $\{2, 5, 10, 20, 40\}$. The oracle-tuned version is the strongest competitor on this question, because any adaptive rule must at least recover the best fixed choice. We give it that grid of five settings, and we tune the constant $c$ in our rule over a grid of the same size, $\{0.5, 1, 2, 4, 8\}$. Both methods share one global value across environments, except that the oracle is allowed its per-environment choice. MDPO reports outperforming baselines on Humanoid-v2 and matching or beating PPO on 15 of 21 Atari games. No reported return number for MDPO on MuJoCo was found on Lacuna, so we re-run it ourselves with identical implementation details.
PPO with target-KL early stopping. This is the most common adaptive stopping heuristic in practice. We tune the target KL over five values.
GePPO. From Generalized Proximal Policy Optimization with Sample Reuse, it is the strongest sample-efficiency method in the file. It reports "requiring only 23% to 85% of the data PPO needed" and return improvements "from 8% on Hopper to … 65% on Swimmer". Because sample reuse is orthogonal to stopping, we also run GePPO combined with our rule.
Matched-compute random-$m$ ablation. Here $m$ is drawn at random each iteration, so that its mean equals the mean inner-step count our rule actually used. This isolates whether the gain comes from adapting to noise or merely from a different total amount of computation.
Held-out-validation stopping ablation. This rule splits the batch and stops when surrogate improvement on the held-out part stalls. It tests whether the variance test is a good proxy, at the cost of the data it withholds.
Criterion for success. All methods get the same environment-step budget, 1M steps on MuJoCo, and 10 seeds each. Beating the baselines means reaching equal or higher area under the learning curve, and equal or fewer environment steps to reach PPO's final return, than oracle-tuned MDPO on at least four of six tasks. It also means clearly beating target-KL PPO and the random-$m$ ablation.
Why not just…?
Why not just fix $m=10$? MDPO itself reports that performance is sensitive to $m$ and that the best value changes across environments. The oracle-tuned baseline measures exactly how much a single fixed $m$ loses. If fixed $m=10$ comes within noise of the oracle and of our rule, the diagnostic study will show a flat, stable peak. We would then conclude that tuning is unnecessary and that our rule mainly saves compute rather than samples.
Why not just use PPO's target-KL early stopping? This is the most serious alternative, because it is already an adaptive stopping rule. Its limitation is that KL measures distance travelled, not whether the travel is justified by the data. A noisy batch can overfit well inside the KL limit, and a clean batch is cut off early for no reason. The diagnostic study distinguishes the two rules directly. For each rule, we measure how far its stopping point lands from the true-improvement peak under deliberately varied noise levels, created by shrinking the batch size and by corrupting the critic. If target-KL tracks the peak as well as our rule does, the proposal's central claim fails.
Why not just use natural gradients with Kronecker-factored curvature? ACKTR, Scalable trust-region method for deep reinforcement learning using Kronecker-factored approximation, reports "a 2x to 3x improvement in sample efficiency over A2C". Better curvature, however, changes the direction of each step, not how long the inner loop should run on a noisy batch. The two questions are complementary. We include ACKTR as a reference curve on MuJoCo but do not claim to beat it on its own axis.
Proposed Experiments
The main suite is MuJoCo Swimmer, Hopper, HalfCheetah, Walker2d, Ant and Humanoid. To check that the rule transfers to discrete actions and pixel inputs, we add the six Atari games used by ACKTR (Beamrider, Breakout, Pong, Q-bert, Seaquest, Space Invaders).
The metrics are:
- area under the return-versus-environment-steps curve;
- environment steps needed to reach the final return of target-KL PPO;
- mean and variance of the inner-step count across training;
- total gradient computations.
The decisive checks are four. First, the rule's stopping point should correlate with the true-improvement peak measured on fresh data, and should do so more closely than target-KL's stopping point. Second, halving the batch size should make the rule take fewer inner steps and should degrade it less than fixed-$m$ MDPO. Third, the gain over the random-$m$ ablation should be significant. Fourth, adding the rule to GePPO should reduce environment steps beyond GePPO's reported savings. If the first check fails, the mechanism is wrong, whatever the returns show.
References
- Mirror Descent Policy Optimization
- Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
- Inexact first-order primal-dual algorithms
- New inertial proximal gradient methods for unconstrained convex optimization problems
- Global complexity analysis of inexact successive quadratic approximation methods for regularized optimization under mild assumptions
- Generalized Proximal Policy Optimization with Sample Reuse
- ESPO: Early-Stopping Proximal Policy Optimization
- Sample Complexity of Neural Policy Mirror Descent for Policy Optimization on Low-Dimensional Manifolds
- Scalable trust-region method for deep reinforcement learning using Kronecker-factored approximation