PaperlayerView exact revision on arXiv

Source-linked AI summary

Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds

Gabor Paczolay, Matteo Papini, Alberto Maria Metelli, Istvan Harmati, Marcello Restelli

arXiv:2610.03165v1cs.LG

TL;DR

Variance-reduced REINFORCE methods offer faster sample-complexity rates but rely on an unrealistic importance-weight variance assumption. The paper introduces DEF-PG using defensive importance sampling and establishes lower bounds in a generalized black-box model, providing oracle-level evidence for the faster rate while not proving minimax optimality under primitive MDP assumptions.

  • Problem

    Faster variance-reduced policy-gradient methods rely on an unrealistic assumption about ordinary importance-weight variance.

    Source: §1 · p. 3

  • Method

    The paper introduces first-order variance-reduced DEF-PG using defensive importance sampling, without requiring Assumption 0 on ordinary importance-weight variance.

    Source: §7 · p. 33

  • Results

    Under standard policy-regularity conditions, REINFORCE and DEF-PG realize their respective oracle conditions, supporting evidence that DEF-PG's faster rate is separated from REINFORCE's.

    Source: §7 · p. 33

  • Takeaways & Limitations

    The matching oracle rates provide evidence that variance-reduced policy gradient's faster rate is optimal and separated from REINFORCE's.

    Source: §7 · p. 33

    The lower bounds do not establish minimax optimality under the primitive MDP assumptions used by the concrete algorithms.

    Source: §7 · pp. 33–34

Abstract

from arXiv · show

Several variance-reduced versions of REINFORCE based on importance sampling achieve an improved $O(\epsilon^{-3})$ sample complexity to find an $\epsilon$-stationary point, under an unrealistic assumption on the variance of the importance weights. In this paper, we propose the \algo (Defensive Policy Gradient) algorithm, based on defensive importance sampling, which achieves the same rate without any assumption on the variance of ordinary importance weights. We also establish lower bounds in a generalized black-box policy-optimization model that hides states and actions and permits parameter-dependent rewards. In this model, the optimal rates are $\Theta(\epsilon^{-4})$ with bounded-variance one-policy feedback and $\Theta(\epsilon^{-3})$ with mean-square-smooth coupled two-policy feedback. Under standard policy-regularity conditions, REINFORCE and \algo realize the corresponding oracle conditions and attain the $O(\epsilon^{-4})$ and $O(\epsilon^{-3})$ upper bounds, respectively. Although the lower bounds do not apply directly to the classical MDP interaction model in which these algorithms operate, this correspondence provides oracle-level evidence that the faster rate of \algo is optimal and genuinely separated from that of vanilla policy gradient.

1 Introduction

Policy-gradient sample complexity matters because interaction data can be costly, while nonconvex objectives generally make local stationarity the target. The paper proposes DEF-PG to avoid the ordinary importance-weight variance assumption behind faster variance-reduced rates and studies matching lower bounds in a generalized black-box model.

1 Introduction

  • Existing variance-reduced policy-gradient methods reach O(ϵ^-3) sample complexity, but their bounds rely on an importance-weight variance assumption that can fail in relevant cases.REINFORCE has O(ϵ^-4) sample complexity; the cited O(ϵ^-3) lower bound from nonconvex stochastic optimization is not directly comparable to policy optimization.Source: §1 · p. 3
  • DEF-PG applies defensive importance sampling to variance-reduced policy gradients, introducing a naturally bounded-variance alternative to ordinary importance weighting.The paper identifies continuity of the defensive importance weights' variance as a technical challenge for proving the upper bound.Source: §1 · p. 4
  • The paper establishes lower bounds in a generalized black-box policy-optimization model where learners observe rewards and policy scores but not states or actions.The reward mechanism may also depend explicitly on the queried policy.Source: §1 · p. 4
  • Under standard policy-regularity conditions, REINFORCE and DEF-PG realize the respective oracle conditions, supporting a genuine rate separation between them.The lower bounds do not apply directly to the classical observed-trajectory MDP model.Source: §1 · p. 4

2 Preliminaries

This section sets up the policy-optimization and gradient-estimation framework, including the variance limitation of off-policy importance weighting. It defines bounded-variance one-policy and coupled two-policy oracle feedback models and explains how oracle calls are counted, including the defensive importance-sampling realization.

Policy optimization.

  • Policy optimization uses parametric stationary stochastic policies to maximize expected discounted return in an episodic Markov decision process, under standard likelihood-ratio regularity conditions.The setup treats the performance objective as an expectation under the policy-induced trajectory distribution.Source: Policy optimization · pp. 5–6
  • Geometric stopping gives an equivalent finite-trajectory representation without approximation or truncation bias, while GPOMDP provides an unbiased on-policy gradient estimator.The estimator requires trajectories sampled under the same policy parameters whose gradient is being estimated.Source: Policy optimization · pp. 6–8

Off-policy policy gradient.

  • Importance weighting makes off-policy gradient estimates unbiased, but their variance can be unbounded, motivating the strong assumption of uniformly bounded importance-weight variance.The variance of importance weights can be infinite even for simple policy classes (Metelli et al, 2020; Zhang et al, 2021), and Zhang et al (2021) note that the bounded-variance assumption can fail for simple policy classes.Source: Off-policy policy gradient · pp. 9–10

Policy-gradient oracle models.

  • The paper abstracts policy-gradient estimators into bounded-variance one-policy feedback and coupled two-policy feedback for maximizing a smooth performance function.The first model captures vanilla policy gradient; the second captures the correlation exploited by variance-reduced methods.Source: Policy-gradient oracle models · p. 10
  • The one-policy oracle returns an unbiased gradient estimate at a queried parameter, with bounded variance and conditionally independent randomness across calls.Source: Policy-gradient oracle models · p. 11
  • Variance-reduced methods require coupled unbiased estimates whose difference shrinks as queried parameters approach each other, a property independent one-policy calls need not provide.Source: Policy-gradient oracle models · p. 11
  • The coupled two-policy oracle returns unbiased estimates of both queried gradients; outputs within a call may be dependent, while separate calls use conditionally independent randomness.Source: Policy-gradient oracle models · pp. 11–12
  • Each one-policy or coupled two-policy oracle call counts as one call, and in the defensive importance-sampling realization either call costs one trajectory.Source: Policy-gradient oracle models · p. 12

3 Algorithm

Variance reduction in policy optimization faces distribution shift because trajectories depend on the changing policy parameters. DEF-PG uses defensive importance sampling to avoid the ordinary importance-weight variance assumption while implementing coupled recursive updates.

3 Algorithm

  • The PAGE-style recursion combines infrequent full-gradient estimates with frequent smaller-batch stochastic updates to stabilize the latter.The correction term in the recursive update controls the bias–variance tradeoff.Source: §3 · pp. 12–13
  • Policy-dependent trajectory distributions create distribution shift, and prior importance-weighted corrections require an assumed uniform bound on importance-weight variance.The target policy is an earlier policy, while samples come from the current behavior policy.Source: §3 · p. 13
  • Defensive importance sampling mixes target and behavior policies, using the accessible older policy to avoid Assumption 0 and bound importance-weight variance for α > 0.The target policy is available from the previous iteration, unlike in settings where target-policy data cannot be obtained.Source: §3 · pp. 13–14
  • Coupled-PAGE uses a bounded-variance one-policy oracle for large-batch refreshes and a coupled two-policy oracle for recursive updates.DEF-PG instantiates these oracles with GPOMDP and defensive importance sampling.Source: §3 · pp. 15, 17
  • DEF-PG and Coupled-PAGE share the same recursion, with one stopped trajectory realizing each oracle call in DEF-PG.The coupled call samples from a mixture of policies and returns weighted gradient estimates.Source: §3 · pp. 15–17

4 Sample Complexity Upper Bounds

The section establishes sample-complexity upper bounds for vanilla and variance-reduced policy gradients, then gives policy conditions under which GPOMDP and DEF-PG realize the needed oracle guarantees. DEF-PG matches the O(ϵ^-3) rate without Assumption 0 or second-order information.

4 Sample Complexity Upper Bounds

  • The section frames these results as oracle-level upper bounds and identifies their concrete policy-gradient realizations.Table 1 summarizes upper and lower bounds for the two oracle regimes; concrete assumptions are used only for upper bounds.Source: §4 · p. 17, Table 1 · p. 23

Vanilla policy gradient.

  • O(ϵ^-4) is the vanilla policy-gradient upper-bound rate under smoothness and a bounded-variance one-policy oracle with finite initial gap.At the oracle level, this bound requires Assumptions 1 and 2.Source: Vanilla policy gradient · pp. 17–18
  • Bounded rewards and bounded score second moment let GPOMDP realize the bounded-variance one-policy oracle.The section gives a variance bound for the geometrically stopped GPOMDP estimator under these conditions.Source: Vanilla policy gradient · p. 18

Variance-reduced policy gradient.

  • Assumption 6 ensures the bounded-variance one-policy oracle and, with Assumptions 4 and 6, defensive estimates realize the coupled oracle.The proof of the defensive oracle property requires neither Assumption 0 nor bounds on second derivatives of policy scores.Source: Variance-reduced policy gradient · pp. 20–21
  • Under Assumptions 1, 4, and 6, DEF-PG matches the best known O(ϵ^-3) first-order rate without Assumption 0 or access to second-order information.Source: Variance-reduced policy gradient · p. 22
  • The stated DEF-PG upper bound is minimized by choosing defensive parameter α = 1/2.The paper relates this choice to the symmetry of the gradient bound.Source: Variance-reduced policy gradient · p. 22

5 Sample Complexity Lower Bounds

This section establishes sample-complexity lower bounds in a black-box policy-optimization model, distinguishes one-policy and coupled two-policy feedback, and shows how Gaussian policies and, under standard regularity conditions, REINFORCE and DEF-PG realize the corresponding oracle regimes and upper bounds. The matching oracle-level rates do not establish lower bounds or a minimax separation for the classical observed-trajectory MDP model.

5 Sample Complexity Lower Bounds

  • These lower bounds apply to the black-box feedback model, not directly to the classical observed-trajectory MDP protocol, though the model captures feedback structures underlying REINFORCE and DEF-PG.The rate correspondence provides evidence that their different complexities reflect a distinction between one-policy and coupled first-order feedback.Source: §5 · p. 23

Feedback models.

  • The black-box model hides states and actions, allows parameter-dependent rewards, and distinguishes single-policy feedback from coupled two-policy feedback using shared randomness.Learners receive reward and policy-score feedback; under coupled queries, the two policy experiments share internal randomness.Source: Feedback models · pp. 24–25

Gaussian policy realization.

  • The Gaussian reward-score construction embeds the stochastic-gradient oracle associated with f in black-box policy optimization and preserves shared-seed coupling needed for variance reduction.Its one-policy samples satisfy Assumption 2 with ν2 = σ2.Source: Gaussian policy realization · pp. 26–27

Sample complexity.

  • Θ(ϵ^-4) is the optimal rate for bounded-variance one-policy feedback in this black-box model, matching the corresponding oracle-level upper bound.The lower bound allows the hard-instance dimension to grow as ϵ decreases; under additional concrete assumptions, GPOMDP and REINFORCE realize the bounded-variance oracle.Source: Sample complexity · pp. 27–28
  • For coupled two-policy feedback, fewer than cMSSϵ^-3 black-box calls cannot guarantee an ϵ-stationary point, establishing an Ω(ϵ^-3) lower bound.A one-policy experiment or a coupled two-policy experiment each counts as one black-box call.Source: Sample complexity · pp. 27–29
  • Under standard policy-regularity conditions, REINFORCE and DEF-PG realize their respective oracle conditions and attain the corresponding upper bounds.Source: Sample complexity · p. 29
  • The correspondence is at the oracle level and does not establish a minimax separation under the classical MDP interaction model, which reveals states and actions and permits direct importance-weight computation.Source: Sample complexity · p. 29
  • The black-box model captures the one-policy and coupled first-order feedback structures underlying REINFORCE and DEF-PG, and the matching rates support a genuine benefit of DEF-PG’s off-policy feedback.Source: Sample complexity · p. 29

6 Related Works

The related work traces variance reduction for policy gradients from methods requiring bounded importance-weight variance to DEF-PG’s defensive-sampling approach. It also distinguishes local first-order rates, second-order alternatives, black-box lower bounds, and global-optimality results.

Local convergence of first-order algorithms.

  • Prior variance-reduced policy-gradient analyses generally assume uniformly bounded ordinary importance-weight variance, alongside policy-score regularity and bounded on-policy gradient-estimator variance.The passage says that under bounded rewards and a bounded score second moment, the on-policy estimator variance condition follows.Source: Local convergence of first-order… · p. 30
  • DEF-PG gives a guarantee without a variance assumption on ordinary importance weights or gradient truncation, for policy classes satisfying boundedness and mean-square-continuity conditions.Zhang et al.’s TSIVR-PG instead truncates gradients and is tailored to softmax policies, which the passage says are unsuitable for continuous control.Source: Local convergence of first-order… · p. 31

Local convergence of second order algorithms.

  • Second-order methods avoid importance weights, while their per-iteration computational cost can remain linear in the dimension and horizon.The text also notes a suspected proof oversight in Yang et al.’s claimed O(ϵ^-3) result; it attributes this suspicion to ignored distribution shift.Source: Local convergence of second order… · p. 31

Lower bounds for local convergence.

  • The paper’s lower bounds are for a generalized black-box model; analogous bounds with parameter-independent rewards under the standard observed-trajectory protocol remain open.The cited construction uses likelihood-ratio scores from a state-dependent Gaussian policy, but the reward mechanism may depend explicitly on the queried policy parameter.Source: Lower bounds for local convergence · p. 32

Global convergence.

  • Global-optimality rates are not directly comparable with rates for finding an ϵ-FOSP because ε and ϵ measure performance gaps and gradient norms, respectively.The text notes that N-PG-IGT’s rate to an ϵ-FOSP is O(ϵ^-3.5), even though its global-optimum rate is O(ε^-2.5).Source: Global convergence · pp. 32–33

7 Conclusion

The paper introduces DEF-PG, using defensive importance sampling to avoid assumptions on ordinary importance-weight variance, and establishes lower bounds in a black-box policy-optimization model. The corresponding oracle rates are realized by REINFORCE and DEF-PG under standard policy regularity, while the lower bounds leave the classical MDP setting unresolved.

7 Conclusion

  • DEF-PG is a first-order variance-reduced policy-gradient algorithm based on defensive importance sampling and requires no ordinary importance-weight variance assumption.At the oracle level, its recursion is an instance of a coupled-feedback method.Source: §7 · p. 33
  • The black-box model yields lower bounds for bounded-variance one-policy feedback and mean-square-smooth coupled two-policy feedback.For discounted policy gradient, bounded rewards and bounded, mean-square-continuous policy scores suffice to realize these oracle conditions.Source: §7 · p. 33
  • Under standard policy-regularity conditions, REINFORCE and DEF-PG realize the respective oracle conditions and attain the corresponding upper bounds.The matching exponents provide oracle-level evidence that variance-reduced policy gradient’s faster rate is optimal and separated from REINFORCE’s.Source: §7 · p. 33
  • The lower bounds do not establish minimax optimality under the primitive MDP assumptions used by the concrete policy-gradient upper bounds.Whether the rates are necessary under standard observed-trajectory interaction with parameter-independent transitions and rewards remains open.Source: §7 · pp. 33–34
  • Further directions include lower bounds under the concrete reward and score assumptions and studying DEF-PG’s global-convergence properties.The conclusion also identifies more natural policy classes and second-order algorithms as possible settings for extending lower bounds.Source: §7 · p. 34

A.1 Proofs of Propositions

The appendix proves estimator and sample-complexity claims used for the paper’s upper bounds, including an expected-gradient-norm guarantee from averaged one-policy oracle calls.

A.1 Proofs of Propositions

  • Choosing m=max{1,⌈2ν^2/ϵ^2⌉} and T=⌈4L∆/ϵ^2⌉, the proof averages m independent OBV calls per iteration and obtains an expected-norm guarantee.The estimator error is conditionally unbiased with squared error at most ν^2/m.Source: §A.1 · p. 40
  • A stopped GPOMDP estimator is analyzed using the stopping rule’s independence from the trajectory and the on-policy score increments’ martingale-difference property.The proof combines these conditions with bounded rewards to establish its estimator bound.Source: §A.1 · p. 41

A.2 Proof of Lemma 5

The appendix establishes the coupled-estimator and algorithmic guarantees used for the upper bound, then relates stochastic-optimization lower bounds to black-box policy-optimization feedback.

A.2 Proof of Lemma 5

  • The defensive estimator pair realizes the coupled oracle, and Coupled-PAGE returns a parameter with expected gradient norm at most ϵ under its stated assumptions.Its expected total oracle-call bound is stated in Lemma 5; the supplied passage does not include the bound’s expression.Source: §A.2 · pp. 44, 47
  • The defensive upper bound in Theorem 6 is minimized at α=1/2.The proof identifies its dependence on α through 1/min{α,1−α}.Source: §A.2 · p. 50

Appendix B Proofs of the Lower Bounds

  • The lower-bound proof represents stochastic-optimization oracle feedback exactly through reward-score experiments from Propositions 7 and 8.The construction uses genuine likelihood-ratio scores from a state-dependent Gaussian policy, with a reward mechanism that may depend on the queried policy parameter.Source: Appendix B · p. 51

B.1 Source stochastic-optimization lower bounds

  • The source results give hard-instance distributions for one-policy bounded-variance feedback and shared-seed two-policy feedback, with the corresponding lower bounds stated for each regime.The passages identify the regimes but do not show the lower-bound expressions.Source: §B.1 · p. 52

B.2 Proofs of the Gaussian realization results

The proofs construct policy feedback records that decode to stochastic gradients and show how reward-score responses can be simulated as complete records. These constructions establish the one-policy and coupled-sample properties used in the oracle results.

B.2 Proofs of the Gaussian realization results

  • The one-policy decoder returns ∇f(θ, Z) almost surely, yielding an unbiased sample with mean-square error at most σ2.The proof uses P(ξ = 0) = 0; the expectation and error bound establish Assumption 2.Source: §B.2 · p. 54
  • For a coupled query, the decoded samples are ∇f(θ, Z) and ∇f(θ′, Z) almost surely, and their mean-square difference is controlled by Proposition 8.The proof invokes the assumed mean-square-smoothness inequality.Source: §B.2 · p. 54
  • The coupled samples are unbiased, and Proposition 8 controls their mean-square difference, verifying the coupled-feedback conditions.The one-policy sample separately satisfies Assumption 2.Source: §B.2 · p. 54

B.3 Simulation of complete reward-score feedback

  • Lemma 13 simulates complete reward-score records from source responses (J(θ), g(θ, Z)) using Gaussian noise and a payment-state reward.The source response is recoverable as J(θ) = γR2; shared-seed responses use the same ξ for both parameters.Source: §B.3 · p. 55

B.4 Proof of Theorem 9

Theorem 9 establishes a one-policy oracle lower bound by simulating policy-feedback records from stochastic-optimization oracle responses. The proof transfers the algorithm’s output and expected gradient norm to that source problem.

B.4 Proof of Theorem 9

  • Theorem 9 establishes a distributional lower bound for algorithms using one-policy feedback, with constants independent of ϵ.The theorem states that for every such algorithm there is an instance in the constructed distribution’s support.Source: §B.4 · p. 56
  • The constructed Gaussian policy instances satisfy the stated smoothness, initial-gap, and bounded-variance oracle conditions.The proof cites Proposition 12 for smoothness and the initial gap, and Corollary 2 for bounded variance.Source: §B.4 · p. 56
  • The reduction simulates each policy response from a source-oracle response, preserving the interaction history and the algorithm’s expected gradient norm.At most one additional source-oracle round is used to query the output if required by the source protocol.Source: §B.4 · p. 57

B.5 Proof of Theorem 10

Theorem 10 establishes a coupled two-policy oracle lower bound by reducing Gaussian policy feedback to a shared-seed stochastic-optimization oracle. The appendix also provides pseudocode for three DEF-PG variants.

B.5 Proof of Theorem 10

  • Theorem 10 establishes a distributional lower bound for algorithms using coupled two-policy feedback, with constants independent of ϵ.For every such algorithm, the theorem gives an instance in the constructed distribution’s support.Source: §B.5 · p. 58
  • The reduction simulates each policy-feedback call with one K = 2 shared-seed oracle round, preserving the complete reward-score records.At most one additional round is needed to query the algorithm’s output.Source: §B.5 · p. 59

Variants

  • The appendix provides pseudocode for DEF-PG variants based on SVRPG, SRVR-PG, and STORM-PG.The displayed algorithms specify inputs including batch sizes, step size, and defensive parameter α.Source: Variants · pp. 60–61
Loading 2610.03165v1…