Variance-reduced gradient

Overview

A gradient estimated from a few sampled trajectories is noisy, and the number of samples needed to reach an approximate stationary point grows with that noise. Variance-reduced methods keep a running estimate and update it with a correction: a large batch refreshes it now and then, and a small batch of paired samples, evaluated at the new and the old parameters, corrects it in between 2610.03165 §1, alg. 1.

The invariant all variants share is that each weighted term is unbiased for the gradient at its own parameters 2610.03165 §4, Lemma 4. The difference between variants lies in how the paired samples are obtained. Trajectories drawn from one policy must be reweighted to estimate the gradient of another, and the weights can have unbounded variance 2610.03165 §2.

Variants

Plain large-batch estimator (REINFORCE, GPOMDP)

No reuse. Each estimate is built from fresh trajectories at the current parameters. The paper's analysis of this route gives O(eps^-4) stopped trajectories to reach an eps-first-order stationary point [arxiv:2610.03165 §4, Prop. 3]. The paper's black-box lower bound for one-policy feedback is also Omega(eps^-4), so this rate is tight in that model 2610.03165 §5, Thm. 9. Card: DEF-PG.

Reweighted recursive estimator (SVRPG, SRVR-PG, STORM-PG, PAGE-PG)

These methods reuse old-policy trajectories through importance weights and reach O(eps^-3). Their analyses assume that the variance of the ordinary importance weight is bounded by a constant W for all pairs of parameters 2610.03165 §2, Assumption 0. The paper gives a simple Gaussian policy with a constant mean where this can fail 2610.03165 §2, Example 1. The card names these methods as prior work and does not reproduce their analyses 2610.03165 §1. Card: DEF-PG.

Defensive mixture sampling (DEF-PG)

The paired batch is drawn from a mixture q = alpha p(. | theta_1) + (1 - alpha) p(. | theta_2) 2610.03165 §3. Each weight is then a ratio against this mixture, so it is bounded by construction. For any alpha in (0, 1], the variance of p/q is at most (1 - alpha)/alpha 2610.03165 §3. Under bounded rewards and bounded, mean-square continuous policy scores, the method reaches O(eps^-3) with no assumption on the ordinary weights 2610.03165 §4, Thm. 6. The score condition generally fails for Gaussian policies 2610.03165 §4, Rem. 2. Card: DEF-PG.

When to use which

The defensive method needs two density evaluations per paired trajectory and scores each trajectory at both parameter values 2610.03165 alg. 2. Budget for that cost before choosing it over a plain estimator.

Implementation sketch

The core of the defensive variant is one recursive step with a refresh branch and a correction branch. The helper functions are in the card's pseudocode 2610.03165 alg. 2. The reweighted variants share this outer loop and differ only in how the correction is weighted.

# One variance-reduced step, shared core  [arxiv:2610.03165 alg. 2]
# Inputs: theta, the stored estimate v, refresh probability p, batches N, B

def vr_step(theta, v, eta, p, N, B, alpha):
    # Move along the stored estimate  [alg. 2, line 5]
    theta_next = theta + eta * v
    if bernoulli(p) == 1:
        # Large on-policy refresh at the new parameters  [alg. 2, lines 7-9]
        v = mean_gpomdp(theta_next, sample_trajectories(theta_next, N))
    else:
        # Correction from paired trajectories  [alg. 2, lines 11-12]
        v = v + defensive_correction(theta_next, theta, B, alpha)
    return theta_next, v

Contradictions

None known among the cards on this page. The paper's related-work footnote questions a proof in Yang et al. (2022) 2610.03165 §6. That is the authors' view, and the cited paper has no card here.

Papers

• DEF-PG: defensive mixture sampling removes the uniform importance-weight variance assumption and gives O(eps^-3) under score conditions, with matching lower bounds in a black-box model.