---
kind: concept
slug: variance-reduced-gradient
title: Variance-reduced gradient
summary: >-
  Lowering the sample cost of a stochastic gradient by reusing an earlier estimate and correcting it with a small paired batch. Variants differ in how they reuse old samples: plain estimators need O(eps^-4) trajectories, reweighted recursions need a bounded-weight assumption, and defensive mixture sampling drops it at O(eps^-3) under score conditions.
tags: [reinforcement-learning, optimization, variance-reduction]
papers: ["2610.03165"]
related: [policy-gradient, importance-weighting]
status: draft
updated_at: 2026-10-19
---

## 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 [arxiv:2610.03165 §1, alg. 1].

The invariant all variants share is that each weighted term is unbiased for the
gradient at its own parameters [arxiv: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 [arxiv: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 [arxiv:2610.03165 §5, Thm. 9].
Card: [DEF-PG](/papers/2610.03165).

### 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
[arxiv:2610.03165 §2, Assumption 0]. The paper gives a simple Gaussian policy
with a constant mean where this can fail [arxiv:2610.03165 §2, Example 1]. The
card names these methods as prior work and does not reproduce their analyses
[arxiv:2610.03165 §1]. Card: [DEF-PG](/papers/2610.03165).

### Defensive mixture sampling (DEF-PG)

The paired batch is drawn from a mixture q = alpha p(. | theta_1) +
(1 - alpha) p(. | theta_2) [arxiv: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 [arxiv: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
[arxiv:2610.03165 §4, Thm. 6]. The score condition generally fails for Gaussian
policies [arxiv:2610.03165 §4, Rem. 2]. Card: [DEF-PG](/papers/2610.03165).

## When to use which

| Situation | Use | Why |
|---|---|---|
| Only one policy's trajectories are available per call, and the rate must hold in the black-box model | Plain large-batch estimator | The paper proves Omega(eps^-4) for this feedback, so no method in that model beats the plain rate [arxiv:2610.03165 §5, Thm. 9] |
| Two parameter values can be evaluated on shared randomness, rewards are bounded, and scores are bounded and continuous | Defensive mixture sampling | The paper's O(eps^-3) result holds under these conditions [arxiv:2610.03165 §4, Thm. 6]; the lower bound for this feedback is Omega(eps^-3) [arxiv:2610.03165 §5, Thm. 10] |
| Gaussian or other policies whose score is not uniformly bounded | No guarantee in this card | The score condition of the defensive method generally fails [arxiv:2610.03165 §4, Rem. 2], and the reweighted analyses assume a bound that can fail [arxiv:2610.03165 §2, Example 1] |
| Need a tuned, practical method | No recommendation from this card | The paper reports no experiments and gives theoretical settings only [arxiv:2610.03165 §7] |
| Need the step size computed from the paper alone | Not possible from this card | The step-size rule needs L and L_pair, which the paper does not estimate [arxiv:2610.03165 §4, Lemma 5] |

The defensive method needs two density evaluations per paired trajectory and
scores each trajectory at both parameter values [arxiv: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
[arxiv:2610.03165 alg. 2]. The reweighted variants share this outer loop and
differ only in how the correction is weighted.

```pseudocode
# 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) [arxiv:2610.03165 §6]. That is the
authors' view, and the cited paper has no card here.

## Papers

- [DEF-PG](/papers/2610.03165): 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.