arXiv CS open access

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

Leonardo Cesani et al. · arxiv_cs

arXiv CS · Papers

deep-learning machine-learning neural-networks

Standard Policy Gradient (PG) algorithms suffer from high estimation variance because they rely on Monte Carlo updates. While off-policy variance reduction mitigates this problem, establishing optimal sample complexity currently requires either restrictive assumptions, such as uniformly bounded impo

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

Leonardo Cesani1 Politecnico di Milano

Matteo Papini Università degli Studi di Milano

arXiv:2610.13692v1 [cs.LG] 9 Oct 2026

Abstract Standard Policy Gradient (PG) algorithms suffer from high estimation variance because they rely on Monte Carlo updates. While offpolicy variance reduction mitigates this problem, establishing optimal sample complexity currently requires either restrictive assumptions, such as uniformly bounded importance weights, or impractical second-order operations. In this work, we introduce Loopless Variance-Reduced PG (LVR-PG), a unified theoretical framework that abstracts a class of first-order estimators that integrate recursive updates with defensive importance sampling, including known estimators such as PAGE-PG and STORM-PG. We prove that this algorithmic class achieves Õ(ϵ−2 ) lastiterate global convergence under weak gradient domination for general parametric policies. We establish this guarantee using purely first-order updates, with minimal assumptions and without gradient preconditioners. By extending state-of-the-art lower bounds to continuous parametric policies, we establish an Ω(ϵ−2 ) sample complexity limit, confirming our framework is minimax-optimal up to logarithmic factors and horizon terms.

INTRODUCTION

In recent years, Reinforcement Learning (RL, Sutton et al., 1998) has been used as the central tool for aligning and scaling the reasoning capabilities of Large Language Models (LLMs, Brown et al., 2020; Achiam et al., 2023). Methods based on Proximal Policy Optimization (PPO, Schulman et al., 2017; Ouyang et al., 2022) and, more recently, Group Relative Policy Optimization (GRPO, Shao et al., 2024) have achieved enormous success on reasoning tasks (Guo et al., 2025) and aligning model outputs with human 1

Correspondence to: leonardo.cesani@polimi.it.

Marcello Restelli Politecnico di Milano

preferences (Ziegler et al., 2019; Bai et al., 2022). At their core, the algorithms powering these methods reduce to the Policy Gradient (PG, Deisenroth et al., 2013) framework. Despite the empirical success, their learning efficiency is a matter of debate (Rafailov et al., 2023). Standard PG methods estimate the gradient of the expected return using sampled trajectories (Sutton et al., 1999), and the resulting Monte Carlo estimates can exhibit high estimation variance (Zhao et al., 2011). Actorcritic algorithms (Konda and Tsitsiklis, 2000) address this difficulty through a learned critic, whose approximation error can introduce bias. For LLMs, maintaining and updating an additional critic also entails substantial memory and computational costs, motivating actor-only methods that avoid a separate critic network (Yuan et al., 2023; Ahmadian et al., 2024). Improving trajectory efficiency without introducing a learned critic is therefore relevant to scalable policy optimization. Reducing gradient-estimation variance has long motivated theoretical research on the sample complexity of PG methods, defined as the number of trajectories n required to learn an ϵ-optimal policy, where ϵ is the required accuracy. Recent actor-only applications give this established problem renewed practical relevance. A central theoretical objective is to determine whether purely first-order, actor-only methods can achieve the optimal Ω(ϵ−2 ) sample-complexity lower bound (Azar et al., 2013). However, the existing guarantees for such methods do not match this lower bound and require additional assumptions on the Hessian of the log-policy or on the variance of the importance weights. Within the class of actor-only PG methods, variance reduction seeks to improve sample complexity by reusing historical gradient information while retaining gradient-only updates. Unlike in standard stochastic optimization, the trajectory distribution depends on the policy parameters and therefore changes over the course of optimization. To account for this distribution shift, these methods employ Importance Sampling (IS), weighting trajectory-based estimates by likelihood ratios between the target and sampling

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

Table 1: Comparison of sample complexities and theoretical assumptions used for variance-reduced PG algorithms. Complexity denotes the number of trajectories required to reach the global optimal policy. Convergence Type, last-iterate or average-iterate guarantees, denotes the necessary number of trajectories for any algorithm to return an ϵ-optimal policy. Gradient Only denotes an algorithm that does not use second-order or Fisher information. No 2nd-Order Asm. denotes algorithms which do not require assumptions on the Hessian matrix of the log-policy. No Bounded IW Asm. indicates algorithms not requiring an assumption on the boundedness e of the variance of the importance weights. † The O(·) hides dependencies on γ, C1 , LS , χ and ψ, O(·) hides ‡ logarithmic factors. Requires an additional second-order smoothness assumption. Algorithm

GPOMDP (Montenegro et al., 2024) SRVR-PG (Liu et al., 2020) STORM-PG-S (Ding et al., 2022) ‡

N-PG-IGT (Fatkhullin et al., 2023) HARPG‡ (Fatkhullin et al., 2023) ANPG (Mondal and Aggarwal, 2024) LVR-PG (Theorem 5.1) Lower Bound (Theorem 3.1)

Complexity† Õ(ϵ−3 )

Convergence Type

Gradient Only

No 2nd-Order Asm.

No Bounded IW Asm.

Last-iterate

✓

✗

✓

Average-iterate

✓

✗

Average-iterate

✓

✗

)

Last-iterate

✓

✗

✓

Õ(ϵ−2 )

Last-iterate

✗

✓

✗

✓

O(ϵ−3 ) −3

O(ϵ

)

−2.5

Õ(ϵ

−2

O(ϵ

)

Average-iterate

✗

−2

Õ(ϵ

)

Last-iterate

✓

Ω(ϵ−2 )

policies. Inspired by stochastic non-convex optimization, early methods such as SVR-PG (Papini et al., 2018) and SRVR-PG (Xu et al., 2019) employ doubleloop architectures. These compute large-batch gradient estimates at a fixed anchor policy to correct subsequent inner-loop mini-batch updates, making the refresh schedule dependent on the chosen epoch length. Loopless methods instead incorporate historical information through recursive momentum updates or probabilistic refreshes, as in STORM-PG (Yuan et al., 2020; Ding et al., 2022) and PAGE-PG (Gargiani et al., 2022), respectively.

geometry (Mondal and Aggarwal, 2024). Despite their theoretical appeal, these approaches require additional computational overhead beyond policy-gradient estimation, motivating the study of gradient-only methods. Their analyses also impose regularity assumptions on policy derivatives, as summarized in Table 1.

Existing analyses of these importance-sampling-based methods impose strong statistical assumptions, notably a uniform bound on the variance of Importance Weights (IW) (Liu et al., 2020; Ding et al., 2022). This condition is not generally guaranteed in continuous state-action spaces, where trajectory-level likelihood ratios accumulate the distribution shifts induced by policy updates. Paczolay et al. (2024) addresses this by using defensive IS (Owen and Zhou, 2000), but it only studies convergence to a first-order stationary point. In contrast, N-PG-IGT (Fatkhullin et al., 2023) circumvents the IW assumption through implicit gradient transport, retaining historical gradient information without using importance sampling. Its established sample complexity of Õ(ϵ−2.5 ), however, does not attain the optimal accuracy dependence. Other approaches attain this dependence through different information mechanisms. HARPG uses Hessian-vector products (Fatkhullin et al., 2023), whereas ANPG estimates natural-gradient directions through an auxiliary stochastic optimization problem involving Fisher

Original Contributions. We study a unified theoretical framework encompassing existing gradient-only PG estimators equipped with defensive IS. In the remainder of the paper, we present our main contributions as follows: • In Section 3, we adapt the hard-instance construction of Azar et al. (2013) to continuously parameterized policies satisfying WGD, establishing that any algorithm guaranteeing expected ϵ-optimality requires Ω(ϵ−2 ) trajectories in the worst-case. • In Section 4, we introduce the unified LVR-PG framework, abstracting loopless estimators like PAGE-PG (Gargiani et al., 2022) and STORM-PG (Yuan et al., 2020). By integrating defensive importance sampling (Paczolay et al., 2024) to control off-policy variance, we avoid assumptions on the variance of the importance weights. • In Section 5, we prove LVR-PG achieves lastiterate global convergence with a sample complexity of Õ(ϵ−2 ), matching our lower bound

The question is therefore whether existing gradientonly PG methods can achieve last-iterate global convergence with the optimal accuracy dependence, without assuming uniformly bounded importance-weight variance or additional second-order regularity.

Cesani, Papini, Restelli

up to logarithmic factors, without assuming uniformly bounded importance-weight variance or additional second-order regularity. • In Section 6, we empirically benchmark the LVR-PG framework against state-of-the-art baselines, identifying the defensive variant of STORM-PG as the dominant algorithmic configuration with superior sample efficiency. The full experimental evaluation is provided in Appendix I.

PRELIMINARIES

Notation. For a measurable set X , we denote by ∆X the set of probability measures over X . For P ∈ ∆X , if it admits a density, we denote it by p. We will use x ∼ P to express that the random variable x is distributed according to P . For n ∈ N, we let JnK := {1, . . . , n}. Vectors are indicated with bold letters. Given two symmetric matrices A and B, we say that A ⪰ B if the matrix A − B is positive semidefinite. Interaction Protocol. We consider an agent interacting with a Markov Decision Process (MDP, Puterman, 2014) M = (S, A, p, r, ρ0 , γ) over independent, indefinite-length episodes. In each timestep h = 0, 1, . . . , the agent observes a state sh ∈ S ⊆ RdS , where s0 ∼ ρ0 is the initial state and ρ0 ∈ ∆S is the initial-state distribution, and executes an action ah ∈ A ⊆ RdA sampled from a parametric stochastic policy πθ : S → ∆A . Here, θ ∈ Θ ⊆ RdΘ is the parameter vector defining the policy space ΠΘ = {πθ | θ ∈ Θ}. The agent then receives a reward rh+1 := r(sh , ah ) ∈ [−Rmax , Rmax ] and transitions to a next state sh+1 ∼ p(· | sh , ah ) ∈ ∆S . For a discount factor γ ∈ [0, 1), the performance of θ is assessed via the expected discounted return under the assumption that θ 7→ πθ is differentiable. The latter is defined as:   X J(θ) := E  γ h r(sh , ah ) πθ  , h≥0

where the expectation is taken over the trajectory distribution induced by the policy and the environment dynamics. In the following, we will refer to J : Θ → R as the performance function, which is generally nonconvex. Because the per-step rewards are bounded, it satisfies |J(θ)| ≤ Rmax /(1 − γ) for all θ ∈ Θ. We denote the optimal performance as J ∗ := maxθ∈Θ J(θ). Policy Gradients. We consider learning algorithms that iteratively update a sequence of policies πθ1 , . . . , πθK . At each iteration k, the agent collects a dataset Dk = {τ1k , . . . , τnkk } of nk independent trajectories drawn from the trajectory distribution induced by the policy pθk (τ ). To accommodate struc-

tural or safety constraints common in practical applications, we consider PG methods that restrict the parameter space to a closed convex set Θ ⊆ RdΘ and, similarly to Xu et al. (2019), update the parametersvia projected stochastic gradient ascent: θk+1 ← b PΘ θk + η ∇θ J(θk ) . Here, η > 0 is the learning rate, b θ J(θk ) is an unbiased estimator of the true graand ∇ dient ∇θ J(θk ). We formalize the optimization geometry over the parameter domain Θ using the generalized gradient mapping Gη (θ) := η1 (PΘ (θ + η∇J(θ)) − θ). This mapping acts as the projected gradient at θ, recovering the standard gradient ∇θ J(θ) in the unconstrained case Θ = RdΘ . To compute the stochastic b θ J(θ) from finite interaction data gradient estimator ∇ without introducing approximation or truncation bias, we evaluate the infinite-horizon discounted objective using a randomized geometric stopping rule, in which the interaction with the environment is terminated after each transition with probability 1 − γ, independently of the interaction history. For each trajectory τi , let Hγ,i ∈ {1, 2, . . .} denote the number of executed transitions, with stopping randomness independent across trajectories. In this way, the expected length of each trajectory is E[Hγ,i ] = (1 − γ)−1 , and, since Pr(Hγ,i > h) = γ h , the expected undiscounted return accumulated before stopping matches the infinitehorizon discounted objective function J(θ). For theoretical analysis, we adopt the geometric stopping rule to obtain unbiased estimates of the infinite-horizon objective. In the empirical evaluation, we use a fixed horizon. Using the geometric horizons Hγ,i , the estib θ J(θk ) is computed from the on-policy dataset mate ∇ Dk via the GPOMDP (Baxter and Bartlett, 2001) estimator: nk X b θ J(θk ) = 1 ∇ g(τi | θk ), nk i=1 Hγ,i −1

g(τi | θ) :=

h=0

h X l=0

(1) !

∇θ log πθ (al | sl ) rh+1 .

While the variance of this on-policy estimator is bounded under standard regularity conditions (Zhao et al., 2011; Papini et al., 2022), it is often very large in practice, compromising learning efficiency. Off-Policy Gradient Estimation. To mitigate large variance of the estimator, variance-reduced algorithms reuse historical data to improve sample efficiency, requiring the evaluation of the gradient at a target policy θ using trajectories collected by a different behavioral policy θ ′ . To maintain an unbiased gradient estimate, these methods rely on Importance Sampling (IS, Metelli et al., 2020). Given a trajectory τ ∼ p(· | θ ′ ), the off-policy GPOMDP estimator is

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

b θ J(θ) = 1 Pn ω(θ, τi )g(τi | θ), where defined as ∇ i=1 n ω(θ, τi ) is the importance weight defined by the trajectory density ratio: Hγ,i −1

ω(θ, τi ) :=

Y πθ (ah | sh ) pθ (τi ) = , pθ′ (τi ) πθ′ (ah | sh ) h=0

where the environment transition dynamics and the trajectory’s stopping probability cancel out. While this off-policy estimator is unbiased, its variance scales with the χ2 -divergence between the trajectory distributions induced by θ and θ ′ (Cortes et al., 2010). Since the χ2 -divergence is generally unbounded, the importance-weight variance can easily diverge even for simple continuous policy classes, such as Gaussians (Zhang et al., 2021).

LEARNING FRAMEWORK

Proposition 3.1. Under Assumption 3.1, the following properties hold. 2 4Rmax C12 =: ν 2 ; (1 − γ)3 Rmax (C12 + LS ) (ii) ∥∇2θ J(θ)∥2 ≤ =: L. (1 − γ)2

(i) Var (g(τ | θ)) ≤

Finally, to ensure global convergence and prevent the learning trajectory from getting trapped in suboptimal solutions, we impose a standard geometric assumption on the objective landscape (Yuan et al., 2022; Montenegro et al., 2024). Assumption 3.2 (Weak Gradient Domination (WGD)). There exist χ > 0 and ψ ≥ 0 such that, for every θ ∈ Θ and a step size η ≤ 1/L, it holds that: J ∗ − J(θ) ≤ χ∥Gη (θ)∥2 + ψ

Assumption 3.1 (Regularity). The policy class admits finite constants C1 , LS > 0 such that, for all θ, θ ′ ∈ Θ, and for any s ∈ S, we have:

Assumption 3.2 is the standard for global convergence of constrained stochastic optimization (Yuan et al., 2022; Masiha et al., 2022; Ding et al., 2022; Fatkhullin et al., 2023; Montenegro et al., 2024). Note that in the unconstrained setting, where Θ = RdΘ , the mapping strictly recovers the true gradient Gη (θ) = ∇θ J(θ), meaning this condition reduces to the standard WGDassumption on the gradient norm. When ψ = 0, we recover the (strong) gradient domination (GD) property: J ∗ − J(θ) ≤ χ∥Gη (θ)∥2 . GD is stricter than WGD since it requires that the constrained performance function J(θ) has no suboptimal stationary points within the feasible domain. Instead, WGD admits local maxima as long as their performance is ψclose to the global optimum (Montenegro et al., 2024).

(i) sup ∇θ log πθ (a | s) 2 ≤ C1 , a∈A h i 2 (ii) E ∇θ log πθ (a | s) − ∇θ log πθ′ (a | s) 2

Lower Bound for Policy Optimization. Having established the learning framework, we now investigate the statistical limits of the policy optimization problem.

To study the sample complexity of learning a globally optimal policy, we must define the structural and geometric properties of the objective landscape and establish the statistical limits of policy optimization. Assumptions. To study variance-reduced PG algorithms within a unified framework, we define the structural and geometric properties of the objective landscape that we will use in our analysis. First, we enforce the following standard regularity conditions on the policy parametrization.

a∼πθ

≤ L2S ∥θ − θ ′ ∥22 .

Assumption 3.1 (ii), introduced by Paczolay et al. (2024), relaxes the uniform Lipschitz score condition standard in prior literature (Papini et al., 2018; Xu et al., 2019; Yuan et al., 2020; Gargiani et al., 2022; Fatkhullin et al., 2023) by requiring only mean-squared smoothness under the on-policy distribution, rather than a worst-case bound across all state-action pairs. Condition (i) requires bounded score gradients, which softmax policies satisfy, for example. Under these regularity conditions, the performance function J(θ) and its stochastic gradient estimator are smooth and have bounded variance, respectively, as formalized in the following proposition (proof in Appendix D).

Theorem 3.1 (Sample Complexity Lower Bound). For any discount factor γ ∈ [2/3,1) andsufficiently

Rmax small target accuracy 0 < ϵ < O γ(1−γ) , there exists a class of MDPs M and a policy parametrization satisfying Assumptions 3.1 and 3.2, such that any algorithm guaranteeing an expected sub-optimality gap J ∗ − E[J(θK )] ≤ ϵ must collect a number of trajectories n satisfying:

n=Ω

2 Rmax −2 ϵ . (1 − γ)2

Theorem 3.1 establishes an Ω(ϵ−2 ) statistical barrier under our regularity and WGD assumptions. In the

Cesani, Papini, Restelli

context of RL, however, our result shows that these geometric properties do not trivialize the learning problem. Even when WGD holds with zero bias, so that GD excludes suboptimal stationary points, it cannot eliminate the irreducible estimation variance induced by the stochastic transition dynamics, thereby preserving the Ω(ϵ−2 ) statistical barrier. This accuracy dependence is consistent with variance-reduced stochastic optimization under GD, where an O(ϵ−2 ) sample complexity is achievable Fatkhullin et al. (2022). However, existing lower bounds do not directly show this barrier in our setting. First, lower bounds for bounded-variance stochastic-gradient oracles concern algorithms that observe stochastic gradients Masiha et al. (2026), whereas MDP interaction provides additional information through states, actions, and rewards, enabling importance-weighted gradient evaluations across different policies using the same trajectories. Second, the tabular lower bound of Azar et al. (2013) does not automatically apply after restricting the MDP and policy class to satisfy GD. Theorem 3.1 addresses these limitations by establishing an Ω(ϵ−2 ) sample complexity lower bound for policy optimization under the stated regularity and WGD assumptions. Finally, Theorem 3.1 establishes a statistical limit for policy optimization, independently of the update rule. Although existing methods achieve near-optimal sample complexity using Hessian or Fisher information, the lower bound does not imply that such information is necessary to reach this statistical limit. Matching the Lower Bound. Theorem 3.1 establishes the statistical limit, leaving open whether firstorder policy optimization methods attain the optimal accuracy dependence. In non-convex stochastic optimization under WGD, Masiha et al. (2026) establishes an Ω(ϵ−3 ) lower bound for the gradient-only, boundedvariance oracle model. Improving this dependence requires additional oracle structure, which recursive variance-reduction methods exploit through “double sampling”: gradient evaluations at distinct parameters using shared randomness. In PG, implementing this coupling requires correcting the distribution shift induced by policy updates. Alternative approaches avoid importance sampling: N-PG-IGT provides a Õ(ϵ−2.5 ) guarantee, whereas HARPG and ANPG attain the ϵ−2 dependence through Hessian-vector products and Fisher geometry, respectively (Fatkhullin et al., 2023; Mondal and Aggarwal, 2024). We therefore investigate whether we can establish the optimal accuracy dependence of this first-order recursive framework without relying on Hessian-vector products or Fisher-based updates, potentially without assuming uniformly bounded importance-weight variance.

THE LVR-PG FRAMEWORK

To address the limitations identified in Section 3, we introduce Loopless Variance-Reduced Policy Gradient (LVR-PG), a unified framework for analyzing loopless, gradient-only PG estimators. By suitably setting its parameters, LVR-PG recovers state-of-the-art estimators such as STORM-PG (Yuan et al., 2020) and PAGE-PG (Gargiani et al., 2022), equipped with the defensive IS scheme of Paczolay et al. (2024), bounding the IW and removing the need to assume their variance to be uniformly bounded. Our goal is to establish that, with an appropriate choice of hyperparameters, an algorithm within LVR-PG achieves lastiterate global convergence with a sample complexity matching the Ω(ϵ−2 ) lower bound of Theorem 3.1, up to logarithmic factors and horizon terms. Defensive Importance Sampling Classical variance-reduced PG evaluates past policies using on-policy data, leading to IW to diverge exponentially over the trajectory horizon. To avoid this blow-up in the IW, we sample trajectories from a mixture trajectory distribution and employ defensive IS (Owen and Zhou, 2000; Paczolay et al., 2024). Let pθ (τ ) be the probability density of a trajectory τ induced by a policy πθ . During off-policy estimation at iteration k, the algorithm collects a mini-batch of B trajectories. Instead of drawing these exclusively from the current policy, each trajectory is independently drawn from the target policy πθk+1 with probability ξ ∈ [0, 1] and from the previous policy πθk with probability 1 − ξ. This yields a mixture trajectory distribution, defined as qξ (τ ) = ξpθk+1 (τ ) + (1 − ξ)pθk (τ ). To estimate the gradient at either θk+1 or θk using trajectories sampled from qξ , we use the defensive IS weight ωξ (θ, τ ) := pθ (τ )/qξ (τ ), where θ ∈ {θk+1 , θk }. For ξ ∈ (0, 1), each target trajectory density enters qξ with a positive coefficient, so its importance weight is bounded by the reciprocal of that coefficient. In particular, when evaluating the current policy, we have ωξ (θk+1 , τ ) ≤ 1/ξ, and similarly ωξ (θk , τ ) ≤ 1/(1 − ξ). One can easily show that the gradient estimate computed using this mixture distribution remains unbiased. The Unified Estimator. Building upon the loopless variance reduction principles introduced in Yuan et al. (2020) and Gargiani et al. (2022), our framework regulates full-batch and mini-batch updates through a randomized mechanism governed by p ∈ [0, 1], which we call refresh probability parameter. At iteration k ∈ JKK, the evaluation of the target policy θk+1 and the b † J(θk+1 ) construction of the new gradient estimator ∇ θ depend on a Bernoulli realization ck ∼ B(p). If ck = 1,

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

obtain an ϵ-approximate global optimum. Specifically, we demonstrate that the LVR-PG framework defines a class of minimax–optimal first-order algorithms, up to logarithmic factors. The proofs for the results presented in this section are deferred to Appendix E.

Algorithm 1: LVR-PG Input: K, N, B, p, α, ξ, η, Θ, θ0 b θ J(θ0 ) using N trajectories from πθ ; 1 Init. ∇ 0 2 for k = 0, . . . , K − 1 do b † J(θk ) ; 3 θk+1 ← PΘ θk + η ∇ θ

4 5

6 7 8 9 10 11

Draw refresh variable ck ∼ B(p); if ck = 1 then Sample N trajectories τ1:N ∼ πθk+1 ; Estimate gradient with Equation (1); else Sample B trajectories τ1:B from qξ ; Estimate gradient with Equation (2);

Return θK

the framework executes a full refresh, sampling N trajectories directly from the target policy πθk+1 to compute a full-batch gradient estimate with Equation (1) with nk = N . If ck = 0, the framework bypasses the full-batch estimation in favor of a recursive mini-batch update. To evaluate the gradients of both πθk+1 and πθk simultaneously, LVR-PG collects B ≪ N trajectories independently drawn from the mixture behavior distribution qξ . This allows us to compute the Defensive IS operator ωξ (θ, τ ) via the density ratio. Using this mini-batch and the mixture IS operator, the gradient estimator is recursively updated using a momentum parameter α ∈ [0, 1] to control off-policy variance: b † J(θk+1 ) = g ωξ (θk+1 ) ∇ B θ h i b † J(θk ) − g ωξ (θk ) , + (1 − α) ∇ B θ

(2)

PB ω where gBξ (θ) := B1 i=1 ωξ (θ, τi )g(τi | θ).

The momentum parameter α regulates the degree to which past gradient errors are discounted, and enables to control of the variance-reduction strategy to use: setting α = 0 and p ∈ [0, 1] recovers the update rule of PAGE-PG (Gargiani et al., 2022), while setting α > 0 yields the momentum update of STORM-PG (Yuan et al., 2020). In the rest of the paper, we will refer to the defensive versions of these two algorithms as DEF-PAGE-PG and DEF-STORM-PG, respectively. Finally, once we compute the variance-reduced estib † J(θk ), we update the policy parameters via mator ∇ θ projected stochastic gradient ascent. The algorithm aims to find a parameter θ ∈ Θ that maximizes the performance function subject to this constraint.

CONVERGENCE AND OPTIMALITY

In this section, we establish the sample complexity required by an instantiation of the LVR-PG framework to

Theorem 5.1 (Global Convergence of LVR-PG). Under Assumptions 3.1 and 3.2, for any target accuracy ϵ > 0 and fixed mini-batch size B ≥ 1, let the batch sizes be N, N0 = Θ(ϵ−2 ) and the learning rate be η = Θ(Bϵ). For appropriately chosen hyperparameters satisfying p, α = O(Bϵ2 ) and p + α = Ω(Bϵ2 ) and choosing ξ = 1/2, LVR-PG guarantees an expected suboptimality gap J ∗ − E[J(θK )] ≤ ψ + ϵ with a total expected sample complexity of at most: 3 2 χ Rmax e , n=O (1 − γ)4 ϵ2 e hides logarithmic factors. where O(·)

Proof Sketch. The proof establishes the minimaxoptimal sample complexity for LVR-PG by coupling the policy’s suboptimality descent with the variance recurrence of the gradient estimator. Part I: The Descent Mechanics. We begin by characterizing the estimation error ∆k := b † J(θk )−∇θ J(θk )∥2 ]. Lemma D.4 quantifies how E[∥∇ 2 θ this error propagates through recursive updates. Let- ting λ := 1−(1−p)(1−α)2 and Ψk := E ∥θk+1 − θk ∥22 we have: ∆k+1 ≤ (1 − λ)∆k +

2(1 − λ)C†,ω Ψk + C ν . B

Here, C†,ω > 0 is the mean-squared smoothness constant from Lemma B.1, which controls the estimation error induced by policy updates. The additive variance term Cν combines the contributions of full-batch refreshes and recursive mini-batch updates, weighted by p and α2 , respectively. From the L-smoothness of the objective obtained in Proposition 3.1, letting rk := E[J˜∗ − J (θk )], we obtain the recursion of the suboptimality gap: 3η 1 L η rk+1 ≤ rk − E ∥Gη (θk )∥22 + ∆k − − Ψk . 8 4 4η 2

To establish convergence, we study the potential Φk := rk + c∆k , combining suboptimality and estimation er3η ror. Choosing c = 2λ and a sufficiently small step size η yields a recursion in which both objective improvement and estimator-error decay contribute to reducing Φk .

Part II: WGD and Recurrence. Because ∥Gη (θk )∥22 provides only local stationarity guarantees, we use Assumption 3.2 to bound the global suboptimality gap directly by the gradient mapping norm.

Cesani, Papini, Restelli

= Ω (B

p = O(Bϵ2 ) GPOMDP O(ϵ−3 )

2 )

Remark 5.1 (Unification of Existing Algorithms). Existing variance-reduced estimators emerge as boundary limits of this optimal space: setting α = 0 or p = 0 recovers DEF-PAGE-PG and DEF-STORM-PG, respece −2 ) sample comtively, both strictly preserving the O(ϵ plexity. Setting p = 1 forces full-batch evaluations at every step, recovering vanilla GPOMDP. This choice violates the computational boundary p = O(Bϵ2 ), shift-

e −2 ) O(ϵ

Theorem 5.1 establishes that LVR-PG attains the minimax-optimal sample complexity in the learning framework described in Section 3, up to logarithmic factors and horizon terms, using exclusively first-order updates. Notably, this rate is achieved using a fixed step size η = Θ(Bϵ), and the convergence guarantee applies directly to the last-iterate parameter θK , bypassing the need for trajectory averaging or random iterate selection commonly required in previous works (Liu et al., 2020; Ding et al., 2022). Furthermore, the analysis identifies a continuous twodimensional region of hyperparameter configurations (p, α) for which the nearly optimal sample complexity is guaranteed. As illustrated in Figure 1, the conditions p = O(Bϵ2 ), α = O(Bϵ2 ), and p + α = Ω(Bϵ2 ), together with the batch-size and learning-rate choices established in the proof, provide sufficient conditions for this guarantee.

LVR-PG

Part III: Selection of α, p and η. We now choose the hyperparameters to satisfy the accuracy condition Cν = O(µλϵ2 ) while controlling the sample cost. Setting N = Θ(ϵ−2 ) and p = O(Bϵ2 ) keeps the expected cost of full-batch refreshes comparable to that of mini-batch updates. Choosing α = O(Bϵ2 ) controls the momentum-dependent contribution to Cν , while requiring p + α = Ω(Bϵ2 ) ensures sufficient estimator-error decay through λ = Ω(Bϵ2 ). With a suitable step size η = Θ(Bϵ), these choices yield K = Õ((Bϵ2 )−1 ) iterations and a total sample complexity n = Õ(ϵ−2 ).

α = O(Bϵ2 )

This recurrence yields linear contraction for large values of the Lyapunov potential and a WGD-induced quadratic decrease for smaller values. The additive term 3ηCν /(2λ) accounts for stochastic gradientestimation error. When the additive term is sufficiently small, Lemma H.2 bounds the iterations required to reach and remain within the target accuracy: 2Φ0 32 4 , log . K ≥ max µηϵ λ ϵ

α/(Bϵ2 )

DEF-STORM-PG (Corollary E.2)

Evaluating the invariant sequence xk := max{0, Φk } reveals a dual-regime dynamical system: µη 2 λ 3ηCν xk+1 ≤ xk − min x , xk + . 32 k 4 2λ

DEF-PAGE-PG (Corollary E.1)

1 Bϵ2

p/(Bϵ2 )

Figure 1: The continuous algorithmic design space of LVR-PG in normalized coordinates. The shaded region delineates the manifold of hyperparameter configurations (p, α) that satisfy the stability thresholds derived in Theorem 5.1. In this region, a configuration of LVR-PG is nearly optimal. GPOMDP falls out of this region, since p = 1. ing the algorithm outside the optimal manifold and core −3 ) rectly degrading its complexity to the standard O(ϵ rate (Montenegro et al., 2024). 5.1

On Fisher-Non-Degeneracy

We specialize Theorem 5.1 to Fisher-Non-Degenerate (FND) policies in the unconstrained setting Θ = RdΘ . This setting allows us to apply the ordinary-gradient domination inequality induced by FND under suitable approximation and concentrability assumptions (Liu et al., 2020; Ding et al., 2022; Fatkhullin et al., 2023), since Gη (θ) = ∇θ J(θ). Although FND can also be imposed on constrained parameter sets, projection can remove gradient components, so the gradient bound does not imply the mapping-based WGD condition required by Assumption 3.2. In the unconstrained setting Θ = RdΘ , when the FIM induced by πθ is uniformly non-degenerate, i.e., F (θ) = Eπθ [∇θ log πθ (a | s)∇θ log πθ (a | s)⊤ ] ⪰ µF I for some µF > 0 and every θ ∈ Θ, WGD follows provided that the compatible function approximation error (Agarwal et al., 2021) is bounded. This condition requires Eπθ [(Aπθ (s, a) − (1 − γ)w⊤ ∇θ log πθ (a | s))2 ] ≤ ϵbias , where w = F (θ)−1 ∇θ J(θ) and Aπθ is the advantage function of the policy πθ . Under these conditions, WGD holds with χ = C1 /µF and ∗ √ ψ = ϵbias κ/(1 − γ). Here, κ = supθ∈RdΘ ∥ν π /ν πθ ∥∞

500

Expected Return J(θ)

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

400 300 200 100

40 20 0

0 0

0.2

4 0.6 Trajectories (×104 )

0.8

0.0

(a) CartPole-v1 DEF-STORM-PG

0.2

0.4 0.6 Trajectories (×104 )

0.8

(b) Swimmer-v4 DEF-PAGE-PG

N-PG-IGT

GPOMDP

Figure 2: Comparison of DEF-STORM-PG, DEF-PAGE-PG, N-PG-IGT, and GPOMDP. Shaded regions indicate the estimated standard error of the mean. is a concentrability coefficient, and ν πθ denotes the state-action distribution induced by πθ . Note that, differently from previous works (Ding et al., 2022; Fatkhullin et al., 2023), we define the expected compatible function approximation error with respect to the current state-action distribution ν πθ rather than ∗ the optimal distribution ν π . Bounding the error un∗ der ν π is unverifiable because the optimal policy is unknown a priori. Conversely, evaluating this error under ν πθ requires the parametrization to be expressive along the realized optimization trajectory, a verifiable formulation that inherently incurs the statistical penalty κ within the irreducible bias. Corollary 5.1 (Sample complexity under FND). In the unconstrained setting where Θ = RdΘ , letting χ = √ C1 /µF and ψ = ϵbias κ/(1 − γ), assuming κ < ∞, LVR-PG achieves a suboptimality gap J ∗ −E[J(θK )] ≤ √ ϵbias κ 1−γ + ϵ with a total sample complexity of: 2 Rmax C13 e n=O . (1 − γ)4 µ3F ϵ2 Corollary 5.1 confirms that when policies satisfy FND, the minimax optimal sample complexity established by Theorem 5.1 is robustly preserved without degradation. We refer the reader to Appendix C for a detailed discussion.

EXPERIMENTAL RESULTS

To evaluate the empirical sample efficiency of our framework, we consider CartPole-v1 and Swimmerv4, covering classic control and MuJoCo locomotion tasks Todorov et al. (2012). The comparisons, hyperparameter ablations, and grid search reported in Appendix I motivate selecting the STORM gradient estimator as the primary representative of LVR-PG, given

its better sample efficiency. This configuration uses momentum-based recursive gradient estimates with defensive IS and no full-batch refreshes (p = 0, α > 0). Figure 2 also includes DEF-PAGE-PG for completeness, showing its lower sample efficiency in the tested settings. Hybrid configurations are examined in Appendix I. We compare DEF-STORM-PG with GPOMDP, which uses fresh on-policy gradient estimates, and N-PG-IGT, which combines normalized updates with implicit gradient transport without importance sampling. These comparisons assess whether recursive variance reduction with defensive IS improves empirical sample efficiency relative to the two baselines. Across both environments, DEF-STORM-PG reaches high returns with fewer trajectories than GPOMDP and DEF-PAGE-PG. On CartPole-v1 DEF-STORM-PG exhibits fewer oscillations than N-PG-IGT, while in Swimmer-v4, the latter converges quickly to a local optimum.

CONCLUSIONS

We established that purely first-order PG methods can achieve minimax-optimal sample complexity up to logarithmic factors and horizon terms, with minimal assumptions and without second-order assumptions. Our findings suggest several directions for future research. First, the defensive IS mechanism requires evaluating trajectories under a mixture distribution, which inherently requires storing both the current and previous policy parameters. Developing variancereduction mechanisms that avoid this explicit double sampling would significantly reduce memory overhead. Second, extending the LVR-PG theoretical framework to encompass adaptive gradient methods would bridge the gap between our convergence guarantees and the practical optimization dynamics prevalent in deep RL.

Cesani, Papini, Restelli

AI use statement In this work, we used generative AI tools for text polishing, proof assistance, and code generation. We have not used generative AI tools to generate research ideas or to conduct the literature review, and generating figures or data synthesis is not applicable to this work. Additionally, we used generative AI tools to correct grammar and improve readability. We have reviewed all AI-assisted work. Specifically, the core ideas and initial proofs were developed manually by the authors, and AI was subsequently used to polish the presentation of the mathematical proofs. All AI-assisted proofs were checked line by line, and the authors thoroughly reviewed and tested any AI-assisted code for correctness. We take responsibility for the final content of this work, including text, claims, or artifacts produced with the aid of generative AI. References Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023. Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1–76, 2021. Arash Ahmadian, Chris Cremer, Matthias Gallé, Marzieh Fadaee, Julia Kreutzer, Olivier Pietquin, Ahmet Üstün, and Sara Hooker. Back to basics: Revisiting reinforce-style optimization for learning from human feedback in llms. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 12248–12267, 2024. Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J. Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Mach. Learn., 91(3):325–349, 2013. Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arxiv. arXiv preprint arXiv:2204.05862, 2022. Jonathan Baxter and Peter L Bartlett. Infinite-horizon policy-gradient estimation. journal of artificial intelligence research, 15:319–350, 2001. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal,

Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901, 2020. Leonardo Cesani, Matteo Papini, and Marcello Restelli. How log-barrier helps exploration in policy optimization, 2026. URL https://arxiv.org/ abs/2603.15001. Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Learning bounds for importance weighting. Advances in neural information processing systems, 23, 2010. Marc Peter Deisenroth, Gerhard Neumann, and Jan Peters. A survey on policy search for robotics. Foundations and Trends® in Robotics, 2(1-2):1– 142, 2013. Yuhao Ding, Junzi Zhang, and Javad Lavaei. On the global optimum convergence of momentum-based policy gradient, 2022. URL https://arxiv. org/abs/2110.10116. Ilyas Fatkhullin, Jalal Etesami, Niao He, and Negar Kiyavash. Sharp analysis of stochastic optimization under global kurdyka-lojasiewicz inequality. Advances in Neural Information Processing Systems, 35:15836–15848, 2022. Ilyas Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao He. Stochastic policy gradient methods: Improved sample complexity for fisher-nondegenerate policies. In International Conference on Machine Learning, pages 9827–9869. PMLR, 2023. Matilde Gargiani, Andrea Zanelli, Andrea Martinelli, Tyler Summers, and John Lygeros. Page-pg: A simple and loopless variance-reduced policy gradient method with probabilistic gradient estimation. In International conference on machine learning, pages 7223–7240. PMLR, 2022. Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, et al. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948, 2025. Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001. Vijay R. Konda and John N. Tsitsiklis. Actor-critic algorithms, 2000. URL http://papers.nips.cc/ paper/1786-actor-critic-algorithms. Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33:7624–7636, 2020.

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

Saeed Masiha, Saber Salehkaleybar, Niao He, Negar Kiyavash, and Patrick Thiran. Stochastic secondorder methods improve best-known sample complexity of sgd for gradient-dominated functions. Advances in Neural Information Processing Systems, 35:10862–10875, 2022.

Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in neural information processing systems, 36:53728– 53741, 2023.

Saeed Masiha, Negar Kiyavash, and Patrick Thiran. Sharp first-order lower bounds under sublevel \α-polyak-lojasiewicz conditions. arXiv preprint arXiv:2606.28278, 2026.

John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.

Alberto Maria Metelli, Matteo Papini, Nico Montali, and Marcello Restelli. Importance sampling techniques for policy optimization. Journal of Machine Learning Research, 21(141):1–75, 2020.

Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Yang Wu, et al. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300, 2024.

Washim U Mondal and Vaneet Aggarwal. Improved sample complexity analysis of natural policy gradient algorithm with general parameterization for infinite horizon discounted reward markov decision processes. In International Conference on Artificial Intelligence and Statistics, pages 3097–3105. PMLR, 2024. Alessandro Montenegro, Marco Mussi, Alberto Maria Metelli, and Matteo Papini. Learning optimal deterministic policies with stochastic policy gradients. arXiv preprint arXiv:2405.02235, 2024. Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730–27744, 2022. Art Owen and Yi Zhou. Safe and effective importance sampling. Journal of the American Statistical Association, 95(449):135–143, 2000. Gabor Paczolay, Matteo Papini, Alberto Maria Metelli, Istvan Harmati, and Marcello Restelli. Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds. Machine Learning, 113:1–36, 06 2024. doi: 10.1007/ s10994-024-06573-4. Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reduced policy gradient. In International conference on machine learning, pages 4026–4035. Pmlr, 2018. Matteo Papini, Matteo Pirotta, and Marcello Restelli. Smoothing policies and safe policy gradients. Machine Learning, 111(11):4081–4137, 2022. Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.

Richard S Sutton, Andrew G Barto, and Andrew Barto. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998. Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999. Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, pages 5026–5033. IEEE, 2012. Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recursive variance reduction. arXiv preprint arXiv:1909.08610, 2019. Huizhuo Yuan, Xiangru Lian, Ji Liu, and Yuren Zhou. Stochastic recursive momentum for policy gradient methods. arXiv preprint arXiv:2003.04302, 2020. Rui Yuan, Robert M Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 3332–3380. PMLR, 2022. Zheng Yuan, Hongyi Yuan, Chuanqi Tan, Wei Wang, Songfang Huang, and Fei Huang. Rrhf: Rank responses to align language models with human feedback without tears. arXiv preprint arXiv:2304.05302, 2023. Junyu Zhang, Chengzhuo Ni, Csaba Szepesvari, Mengdi Wang, et al. On the convergence and sample efficiency of variance-reduced policy gradient method. Advances in Neural Information Processing Systems, 34:2228–2240, 2021.

Cesani, Papini, Restelli

Tingting Zhao, Hirotaka Hachiya, Gang Niu, and Masashi Sugiyama. Analysis and improvement of policy gradient estimation. Advances in Neural Information Processing Systems, 24, 2011. Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint arXiv:1909.08593, 2019.

CHECKLIST 1. For all models and algorithms presented, check if you include: (a) A clear description of the mathematical setting, assumptions, algorithm, and/or model. Yes, the paper describes the framework in Sections 2, 3 and 4. (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. Yes, the paper proves the complexity properties of a class of algorithms. (c) (Optional) Anonymized source code, with specification of all dependencies, including external libraries. Yes, the anonymized code is provided in the supplemental material. 2. For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. Yes, we define the assumptions in Section 3. (b) Complete proofs of all theoretical results. Yes, the proofs of the theoretical results are provided in the appendix (c) Clear explanations of any assumptions. Yes, the explanation of the assumptions is provided in both the main paper and the appendix. 3. For all figures and tables that present empirical results, check if you include: (a) The code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL). Yes, the code to run the experiments is in the supplementary material. (b) All the training details (e.g., data splits, hyperparameters, how they were chosen). Yes, the training details are provided in Appendix I (c) A clear definition of the specific measure or statistics and error bars (e.g., with respect to the random seed after running experiments

multiple times). Yes, each plot includes a description of the specific measures included. (d) A description of the computing infrastructure used. (e.g., type of GPUs, internal cluster, or cloud provider). Yes, in Appendix I 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator If your work uses existing assets. Yes. (b) The license information of the assets, if applicable. Not Applicable. (c) New assets either in the supplemental material or as a URL, if applicable. Yes, the code can be found in the supplementary materials. (d) Information about consent from data providers/curators. Not Applicable. (e) Discussion of sensible content if applicable, e.g., personally identifiable information or offensive content. Not Applicable. 5. If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to participants and screenshots. Not Applicable. (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. Not Applicable. (c) The estimated hourly wage paid to participants and the total amount spent on participant compensation. Not Applicable.

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

Algorithm 2: Loopless Variance-Reduced Policy Gradient (LVR-PG) Input: Iterations K; batch size N = N0 ; mini batch size B; algorithmic parameters: p ∈ [0, 1], α ∈ [0, 1], mixture coefficient ξ ∈ [0, 1], IS operator ω, discount factor γ; initial parameters θ0 ∈ Θ; step size η; constraint set Θ. 1 for i = 1, . . . , N do 2 τi ← CollectTrajectory(πθ0 , γ); b † (θ0 ) ← 1 PN0 g(τi | θ0 ); 3 ∇J N0

i=1

for k = 0, . . . , K − 1 do b † J(θk ) ; 5 θk+1 ← PΘ θk + η ∇

8 9 10 11 12 13 14 15 16 17 18

Draw ck ∼ B(p); if ck = 1 then for i = 1, . . . , N do τi ← CollectTrajectory(πθk+1 , γ); † b J(θk+1 ) ← 1 PN g(τi | θk+1 ); ∇ θ

i=1

else for i = 1, . . . , B do Draw mixture variable u ∼ B(ξ); if u = 1 then τi ← CollectTrajectory(πθk+1 , γ); else τi ← CollectTrajectory(πθk , γ);

h i b † J(θk+1 ) ← 1 PB ω(θk+1 , τi )g(τi | θk+1 ) + (1 − α) ∇ b † J(θk ) − 1 PB ω(θk , τi )g(τi | θk ) ; ∇ i=1 i=1 θ θ B B

Return θK

Algorithm 3: CollectTrajectory(π, γ) Input: Policy π, discount factor γ ∈ (0, 1). 1 Initialize trajectory τ ← ∅, time step h ← 0; 2 Sample initial state s0 ∼ ρ0 ; 3 while True do 4 Sample action ah ∼ π(· | sh ); 5 Observe reward rh+1 and next state sh+1 ∼ p(· | sh , ah ); 6 Append (sh , ah , rh+1 ) to τ ; 7 Draw stopping condition z ∼ B(1 − γ); 8 if z = 1 then Return τ ∪ {sh+1 } ; 9 h ← h + 1;

LOOPLESS VARIANCE-REDUCED POLICY GRADIENT (LVR-PG)

Algorithm 3 details the interaction protocol used to evaluate the policies. To ensure that the gradient estimates remain unbiased with respect to the infinite-horizon objective without introducing arbitrary truncation, the algorithm relies on a randomized geometric stopping rule. At each time step, the agent samples an action, observes the corresponding reward and state transition, and terminates the episode with probability 1 − γ. This guarantees that the trajectory length follows a geometric distribution with expectation (1 − γ)−1 .

Algorithm 2 outlines the generic LVR-PG template, which tracks and updates a recursive gradient estimator b † J(θk ) at each iteration k. The mechanism allowing for switching between full-batch and mini-batch updates ∇ θ relies on a Bernoulli random variable ck ∼ B(p) that dictates the estimator’s update rule. When ck = 1, the historical variance is discarded, and the estimator undergoes a full-batch refresh using N trajectories. Conversely,

Cesani, Papini, Restelli

when ck = 0, the algorithm computes a variance-reduced update using a smaller mini-batch of B trajectories, modulated by a momentum decay parameter α ∈ [0, 1] and an importance sampling operator ω. By specifically choosing the hyperparameters (p, α, ξ), we can instantiate multiple variance-reduced PG algorithms, as summarized in Table 2. By selecting these parameters, the framework dynamically shifts its algorithmic behavior. PAGE-PG eliminates the recursive momentum term (α = 0), relying entirely on the probabilistic refresh rate p to bound the accumulation of estimation error alongside standard importance sampling Gargiani et al. (2022). STORM-PG avoids full-batch refreshes entirely (p = 0) and instead uses a momentum parameter α to incrementally discount past gradient errors Yuan et al. (2020). Crucially, the parameter ξ ∈ (0, 1) activates the defensive importance sampling mechanism. As detailed in the recursive branch of Algorithm 2, drawing the Bernoulli mixture variable u ∼ B(ξ) physically constructs the defensive trajectory distribution qξ (τ ) = ξpθk+1 (τ ) + (1 − ξ)pθk (τ ). Under this regime, the IS operator ω(θ, τ ) evaluates precisely to the density ratio pθ (τ )/qξ (τ ), intrinsically bounding the variance of the off-policy estimator without requiring arbitrary structural constraints on the policy class. While the generic LVR-PG template accommodates standard importance sampling (ξ = 0), throughout the theoretical analysis and empirical evaluations of this paper, we strictly consider the defensive setting (ξ ∈ (0, 1)). We utilize the LVR-PG framework to unify the theoretical analysis of these diverse algorithms. By defining an effective decay rate λ := 1 − (1 − p)(1 − α)2 , we encapsulate the error discounting effects of both probabilistic refreshes and continuous momentum into the exact same mathematical recurrence. This unified rate establishes the variance bound evaluated in Lemma D.4, allowing us to prove last-iterate global convergence in Theorem 5.1.

Algorithm

Table 2: Instantiations of the LVR-PG Framework Refresh Prob. p Momentum α Defensive Parameter ξ

PAGE-PG Gargiani et al. (2022) STORM-PG Yuan et al. (2020) DEF-PAGE-PG Paczolay et al. (2024) DEF-STORM-PG Paczolay et al. (2024)

p ∈ (0, 1) p=0

α=0

ξ=0

α ∈ (0, 1)

ξ=0

α=0

α ∈ (0, 1)

ξ ∈ [0, 1]

MEAN-SQUARED SMOOTHNESS

Because algorithms recursively update their gradient estimators using historical information, they must evaluate the difference between stochastic gradients at the current policy θk and a previous policy θk−1 using a shared batch of trajectories. To correct for the shift in the trajectory distribution, these methods evaluate the gradients using an importance sampling (IS) operator ω. The mean-squared smoothness isolates the expected squared error of this gradient difference, taking the generic form: h i 2 Eτ ∥ω(θk , τ )g(τ | θk ) − ω(θk−1 , τ )g(τ | θk−1 )∥2 ≤ C†,ω ∥θk − θk−1 ∥22 , (3) where C†,ω > 0 is a unified bounding constant. In the following, we provide the mean-squared smoothness constants for different instantiations of Algorithm 2. To avoid the unrealistic assumption of bounded variance for standard importance weights, which is frequently violated in continuous policy spaces, our framework relies entirely on defensive importance sampling (Owen and Zhou, 2000; Paczolay et al., 2024). Consequently, we evaluate the mean-squared smoothness strictly under the defensive mixture distribution qξ , which intrinsically bounds the variance without requiring arbitrary structural constraints. Lemma B.1 (Mean-Squared Smoothness for LVR-PG). For the LVR-PG framework, sampling from a defensive mixture distribution qξ (τ ) = ξpθk (τ ) + (1 − ξ)pθk−1 (τ ) with parameter ξ ∈ (0, 1), the unified mean-squared smoothness constant CDEF,ω is strictly bounded. Letting mξ := min{ξ, 1 − ξ} and Mr := E[Hγr ] denote the moments of the geometrically distributed trajectory length, under Assumption 3.1 and bounded rewards, it holds

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

that:

h i 2 Eτ ∼qξ ∥ω(θk , τ )g(τ | θk ) − ω(θk−1 , τ )g(τ | θk−1 )∥2 ≤ C†,ω ∥θk − θk−1 ∥22 ,

where the unified mean-squared smoothness constant is: C†,ω =

2 Rmax C14 M5 + 2L2S M4 . mξ

Setting ξ = 1/2 minimizes the variance bound, yielding m1/2 = 1/2 and the optimized mean-squared smoothness constant for both algorithms: 2 C†,ω = 2Rmax C14 M5 + 2L2S M4 = O (1 − γ)−5 .

Proof. We recall a result by Paczolay et al. (2024), proved here for completeness. To establish the mean-squared smoothness bound for both algorithms, we must bound the expected squared L2 norm of the difference between the defensive gradient estimators evaluated at consecutive iterates θk and θk−1 . For brevity, we drop the p trajectory dependency and denote pθk = pθk (τ ), gk = g(τ | θk ), and ωθk = qθξk . We decouple the gradient difference algebraically by adding and subtracting ωθk−1 gk : ωθk gk − ωθk−1 gk−1 = (ωθk − ωθk−1 )gk + ωθk−1 (gk − gk−1 ). Applying the inequality ∥x + y∥22 ≤ 2∥x∥22 + 2∥y∥22 , we can bound the expectation by isolating the importance weights from the on-policy gradients: h i h i h i 2 2 2 Eτ ∼qξ ωθk gk − ωθk−1 gk−1 2 ≤ 2Eτ ∼qξ (ωθk − ωθk−1 )gk 2 + 2Eτ ∼qξ ωθk−1 (gk − gk−1 ) 2 . pθ −pθ

We evaluate the two terms independently. For the first term, we substitute ωθk − ωθk−1 = k qξ k−1 and use the definition of the defensive mixture qξ (τ ) ≥ mξ (pθk (τ ) + pθk−1 (τ )) to bound the density ratio: √ √ ( pθk + pθk−1 )2 (pθk − pθk−1 )2 1 (pθk − pθk−1 )2 1 √ 2 √ √ √ ≤ ( pθk − pθk−1 )2 ( pθk − pθk−1 )2 . = ≤ qξ mξ pθk + pθk−1 mξ pθk + pθk−1 mξ

By bounded rewards and Assumption 3.1, the pathwise GPOMDP gradient is bounded by ∥gk ∥2 ≤ Rmax C1 Hγ2 . Expanding the expectation of the first term yields: h i Z (p − p 2 2 θk θk−1 ) Eτ ∼qξ (ωθk − ωθk−1 )gk 2 = ∥gk ∥22 dτ qξ Z 2 C12 2Rmax √ √ ≤ Hγ4 ( pθk − pθk−1 )2 dτ. mξ Applying Lemma D.3 with r = 4 we obtain: Eτ ∼qξ

i R2 C 4 M 2 5 (ωθk − ωθk−1 )gk 2 ≤ max 1 ∥θk − θk−1 ∥22 . 2mξ

For the second term, we use the property qξ ≥ (1 − ξ)pθk−1 ≥ mξ pθk−1 to convert the expectation under the defensive mixture back to the behavior policy distribution: Z p2 θk−1 Eτ ∼qξ ∥ωθk−1 (gk − gk−1 )∥22 = ∥gk − gk−1 ∥22 dτ qξ 1 ≤ Eτ ∼pθk−1 ∥gk − gk−1 ∥22 . mξ

Applying the mean-square continuity of the policy scores (Assumption 3.1) and the Cauchy-Schwarz inequality over the sequence of rewards, the expected squared difference of the gradients is bounded by: 2 Eτ ∼pθk−1 ∥gk − gk−1 ∥22 ≤ Rmax L2S M4 ∥θk − θk−1 ∥22 .

Cesani, Papini, Restelli

Substituting this back bounds the second term by: R2 L2 M4 Eτ ∼qξ ∥ωθk−1 (gk − gk−1 )∥22 ≤ max S ∥θk − θk−1 ∥22 . mξ

Finally, summing the two bounds with their respective factor of 2 recovers the exact unified estimation constant: 2 2 h i Rmax C14 M5 Rmax L2S M4 2 2 Eτ ∼qξ ωθk gk − ωθk−1 gk−1 2 ≤ 2 ∥θk − θk−1 ∥2 + 2 ∥θk − θk−1 ∥22 2mξ mξ R2 = max C14 M5 + 2L2S M4 ∥θk − θk−1 ∥22 . mξ DEF-PAGE-PG, DEF-STORM-PG (CDEF,ω ). Although DEF-PAGE-PG and DEF-STORM-PG employ different outer recursive mechanisms, their consecutive estimation bounds are identical. This equivalence arises because both algorithms utilize the exact same GPOMDP gradient estimator and rely on the defensive mixture distribution qξ (τ ) = ξpθk (τ ) + (1 − ξ)pθk−1 (τ ) to control the variance of the importance weights. Since the mean squared smoothness isolates only the expected squared error between gradient estimates at consecutive policies, it is strictly independent of the outer update rule. We can verify this by algebraically splitting the update in the recursive branch of Algorithm 2: B B X 1 X b † J(θk+1 ) = (1 − α) 1 ω(θ , τ )g(τ | θ ) + α ω(θk+1 , τi )g(τi | θk+1 ) ∇ k+1 i i k+1 θ B i=1 B i=1 " # B 1 X † b + (1 − α) ∇θ J(θk ) − ω(θk , τi )g(τi | θk ) . B i=1

Substituting this back into the update rule allows us to group the gradient difference directly: # " B X 1 † † b J(θk+1 ) = (1 − α)∇ b J(θk ) + (1 − α) ∇ (ω(θk+1 , τi )g(τi | θk+1 ) − ω(θk , τi )g(τi | θk )) θ θ B i=1 B

+α

1 X ω(θk+1 , τi )g(τi | θk+1 ). B i=1

Hence, adding the continuous momentum does not alter the underlying variance of the defensive gradient differences. By exploiting the mean-square continuity of the scores (Assumption 3.1), defensive importance sampling strictly bounds the mean-squared smoothness without relying on unbounded uniform assumptions or arbitrary Hessian limits.

ON FISHER-NON-DEGENERACY

Assumption C.1 (Fisher-non-degeneracy). There exists some constant µF > 0, such that for every θ ∈ Rd , the FIM F (θ) induced by the policy πθ satisfies: F (θ) = E(s,a)∼ν πθ ∇θ log πθ (a | s)∇θ log πθ (a | s)⊤ ⪰ µF · I. (4)

Assumption C.1 requires the FIM to be uniformly lower-bounded by a strictly positive constant µF > 0. This means that the FIM acts as a well-behaved preconditioner in the natural PG update (Kakade, 2001; Ding et al., 2022) Geometrically, the FIM characterizes the local curvature of the policy manifold measured via the KullbackLeibler (KL) divergence. This condition mathematically implies that the parameterization contains no redundant or ”flat” directions: any non-zero update in the parameter space θ must induce a strictly positive change in the statistical behavior of the policy. The validity of the FND assumption fundamentally depends on the chosen policy architecture and the underlying feature representation.

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

Gaussian Policies. In continuous action spaces, consider a Gaussian policy with a linearly parameterized mean and a fixed covariance matrix, πθ (a | s) = N (ϕ(s)⊤ θ, Σ). The FIM is proportional to the uncentered covariance of the state features: F (θ) = Eν πθ [ϕ(s)Σ−1 ϕ(s)⊤ ]. Here, FND holds globally if and only if the feature covariance matrix is strictly positive definite. This requires the basis functions ϕ(s) to be linearly independent and the state distribution to provide sufficiently rich coverage. When the mean of the gaussian policy µθ (s) is nonliner in θ, as in the case of (deep) neural networks, Assumption C.1 can be satisfied under assumptions on the Jacobian ∇θ µθ (s) similar to the ones for the linear case (Fatkhullin et al., 2023). Softmax Policies. For discrete action spaces using a softmax parameterization, the elements of the FIM depend directly on the policy’s action probabilities. If the policy approaches determinism (i.e., πθ (a | s) → 0 for suboptimal actions), the corresponding entries in the FIM vanish, driving the minimum eigenvalue µF toward zero (Ding et al., 2022). In this case, strict global FND cannot hold without specific architectural constraints or regularization (Cesani et al., 2026). The FND setting contains more than (linear) Gaussians: in addition, Assumption C.1 holds for every full-rank exponential parametrization with their mean parametrized with µθ (s) if µθ (s) is full rank for all θ ∈ Θ. We refer to Section 8 of Ding et al. (2022) and Appendix B of Fatkhullin et al. (2023) for a detailed discussion of FND. Assumption C.2 (Compatible Function Approximation Error). There exist a constant ϵbias > 0, such that for every θ ∈ Rd , the transferred compatible function approximation error satisfies h 2 i πθ ∗⊤ A (s, a) − (1 − γ)u ∇ log π (a | s) ≤ ϵbias , (5) E θ θ π ν θ

where ν πθ is the state-action distribution induced by a policy πθ and u∗ := F (θ)−1 ∇θ J(θ) is the solution of h 2 i πθ ⊤ min E A (s, a) − (1 − γ)w ∇ log π (a | s) . θ θ π w∈Rd ν θ

Assumption C.2 bounds the error incurred when approximating the advantage function Aπθ (s, a) using the score function ∇θ log πθ (a | s) as a linear feature representation. The vector u∗ := F (θ)−1 ∇θ J(θ) is exactly the minimizer of this weighted least-squares regression problem. As established by (Agarwal et al., 2021), this assumption characterizes the expressivity of the parameterized policy class. If the policy class is sufficiently rich, e.g., highly parameterized neural networks or softmax tabular policies, this transferred approximation error ϵbias is small. A critical theoretical distinction must be done between Assumption C.2 and analogous assumptions utilized in the recent variance-reduced policy optimization literature. For instance, the analysis of STORM-PG-S by (Ding et al., 2022) requires the compatible function approximation error to be bounded under the state-action ∗ distribution of the optimal policy, ν π . In contrast, our formulation strictly evaluates the expectation under the state-action distribution of the current policy, ν πθ . ∗

This difference is motivated by the fact that assuming a bounded approximation error under ν π means requiring that the agent has information about the optimal policy, which is not possible. This is because it is not possible to guarantee that the current parametrization accurately fits the advantage function over regions of the stateaction space visited by an optimal policy π ∗ , which is is entirely unknown. By defining the expectation over ν πθ , Assumption C.2 is entirely related to the policy that is being optimized, from which we can gather information about its state-action distribution. Lemma C.1 (Fisher-induced Gradient Domination). Let us consider a general Fisher-non-degenerate policy πθ satisfying Assumptions C.1, 3.1, and C.2 in the unconstrained parameter space Θ = RdΘ . Assume additionally that supθ∈Θ ∥ν πθ∗ /νθπ ∥∞ < ∞, where the ratio denotes the Radon–Nikodym derivative. Then, we have: ∗

J(θ ) − J(θ) ≤

√

ϵbias 1−γ

ν πθ∗ νθπ

+ ∞

C1 ∥∇θ J(θ)∥2 . µF

Proof. The proof follows the one provided by Ding et al. (2022), with the expectation of Assumption C.2 defined w.r.t. the current policy πθ instead of the optimal policy π ∗ . We begin with the performance-difference lemma

Cesani, Papini, Restelli

and perform a change of distribution: 1 πθ E (s, a)] π ∗ [A 1 − γ (s,a)∼ν ν πθ∗ (s, a) 1 πθ π E(s,a)∼ν θ A (s, a) π . = 1−γ ν θ (s, a)

J(θ ∗ ) − J(θ) =

By introducing the optimal compatible weights u∗ := F (θ)−1 ∇θ J(θ) and adding and subtracting (1 − γ)u∗⊤ ∇θ log πθ (a | s), we obtain: ν πθ∗ (s, a) 1 J(θ ∗ ) − J(θ) = E(s,a)∼ν πθ Aπθ (s, a) − (1 − γ)u∗⊤ ∇θ log πθ (a | s) 1−γ ν πθ (s, a) ∗⊤ + E(s,a)∼ν πθ∗ u ∇θ log πθ (a | s) .

To bound the right-hand side, we evaluate the two terms independently. Applying Hölder’s inequality to the first term, followed by the Cauchy–Schwarz inequality, gives: ν πθ∗ (s, a) π ∗⊤ θ E(s,a)∼ν πθ A (s, a) − (1 − γ)u ∇θ log πθ (a | s) ν πθ (s, a) πθ ∗ ν ≤ E(s,a)∼ν πθ Aπθ (s, a) − (1 − γ)u∗⊤ ∇θ log πθ (a | s) π θ ν ∞ r h i πθ ∗ ν πθ (s, a) − (1 − γ)u∗⊤ ∇ log π (a | s))2 πθ ≤ E (A θ θ (s,a)∼ν ν πθ ∞ √ ν πθ ∗ , ≤ ϵbias ν πθ ∞

where the final inequality follows from Assumption C.2. For the second term, the bounded score condition in Assumption 3.1 and Fisher-non-degeneracy give: E(s,a)∼ν πθ∗ u∗⊤ ∇θ log πθ (a | s) ≤ ∥u∗ ∥2 E(s,a)∼ν πθ∗ [∥∇θ log πθ (a | s)∥2 ] ≤ C1 ∥u∗ ∥2

= C1 ∥F (θ)−1 ∇θ J(θ)∥2 C1 ≤ ∥∇θ J(θ)∥2 . µF

Combining the two bounds yields: ∗

J(θ ) − J(θ) ≤

√

ϵbias 1−γ

ν πθ ∗ ν πθ

+ ∞

C1 ∥∇θ J(θ)∥2 . µF

As discussed in Agarwal et al. (2021), analyzing PG methods requires carefully analyzing distinct sources of error: the statistical regression error and the mismatch in state-action visitations. By adopting the formulation in Assumption C.2, the representational capacity of the model is captured entirely by ϵbias under the datagenerating distribution ν πθ . Consequently, the structural penalty for not visiting optimal states is explicitly isolated and paid later in the Fisher-induced Gradient Domination Lemma, manifesting as the concentrability π∗ coefficient κ = νν πθ . ∞

INTERMEDIATE RESULTS

Here, the lemmas used in the proofs of the main results are presented. Lemma D.1 (Variance of the Geometrically-Stopped GPOMDP Estimator). Under Assumption 3.1(i), the variance of the on-policy gradient estimator is strictly bounded. For all θ ∈ Θ, it holds that: Var (g(τ | θ)) ≤

2 4Rmax C12 =: ν 2 . (1 − γ)3

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

Proof. Let the gradient estimator for a single trajectory τ of length Hγ be defined as g(τ | θ) = PHγ −1 Pt t=0 rt+1 h=0 ∇ θ log πθ (ah | sh ). The variance is upper-bounded by the uncentered second moment: Var (g(τ | θ)) ≤ Eτ ∥g(τ | θ)∥22 .

First, we condition on a Hγ . Using the Cauchy-Schwarz inequality, we decouple the rewards from the score functions: ∥g(τ | θ)∥22 =

H−1 X

≤

H−1 X

rt+1

t=0

t X

∇θ log πθ (ah | sh )

h=0

2  ! H−1 t 2 X X 2  rt+1 ∇θ log πθ (ah | sh )  . t=0

h=0

(6)

2 Because the rewards are uniformly bounded, the first term is bounded by HRmax . For the second term, we take the expectation over the trajectory conditioned on H. By the martingale difference property of the score function, the cross-terms of the gradients vanish in expectation:   2 t t h i X X 2 ∇θ log πθ (ah | sh ) | Hγ  = Eτ ∇θ log πθ (ah | sh ) 2 | Hγ Eτ  h=0

h=0

≤ (t + 1)C12 ,

(7)

where the inequality follows directly from Assumption 3.1(i). Substituting Equation (7) back into Equation (6) yields: H −1

γ X Hγ2 (Hγ + 1) 2 2 Eτ ∥g(τ | θ)∥22 | Hγ ≤ Hγ Rmax (t + 1)C12 = Rmax C12 . 2 t=0

(8)

Finally, we take the expectation over the geometric stopping time Hγ , which follows a geometric distribution with success probability p = 1 − γ. Using the standard bounds for the moments of a geometric distribution, we have E[Hγ3 ] ≤ 6/p3 and E[Hγ2 ] ≤ 2/p2 . Thus: " # H 3 + Hγ2 R2 C 2 6 2 2 2 γ EHγ Rmax C1 ≤ max 1 + 2 2 (1 − γ)3 (1 − γ)2 ≤

2 C12 4Rmax , (1 − γ)3

where the final inequality assumes γ is sufficiently close to 1, yielding the standard O((1 − γ)−3 ) variance bound for the GPOMDP estimator. Lemma D.2 (Smoothness of the expected return). Let |R(s, a)| ≤ Rmax for all s ∈ S, a ∈ A and Θ convex. Under Assumption 3.1, we have: Then, for all θ, θ ′ ∈ Θ, ∥∇J(θ) − ∇J(θ ′ )∥ ≤

Rmax (LS + C12 ) ∥θ − θ ′ ∥. (1 − γ)2

Proof. For u ∈ [0, 1], let θu = uθ + (1 − u)θ ′ , which belongs to Θ by convexity. For h ≥ 0, let Zh (u) = Ph h ℓ=0 ∇ log πθu (aℓ | sℓ ). Let τ0:h denote the trajectory prefix up to timestep h included, and pθ its law under policy πθ . Let: Gh (u) = Eτ0:h ∼phθ [rh+1 Zh (u)] , u P∞ h so that ∇J(θu ) = h=0 γ Gh (u). Let ϵ > 0 be such that u + ϵ ∈ [0, 1]. By adding and subtracting Eτ0:h ∼phθ [rh+1 Zh (u)]: u+ϵ

Z Gh (u + ϵ) − Gh (u) = Eτ0:h ∼phθ [rh+1 (Zh (u + ϵ) − Zh (u))] + phθu+ϵ (τ0:h ) − phθu (τ0:h ) rh+1 Zh (u)dτ0:h . (9) u+ϵ | {z } | {z } (A)

(B)

Cesani, Papini, Restelli

We bound the first term using Jensen’s inequality and the second assumption on the policy scores: ∥(A)∥ ≤ Rmax = Rmax

h X

Eτ0:ℓ ∼pℓθ

ℓ=0

h X

Eτ0:ℓ ∼pℓθ

ℓ=0

u+ϵ

∇ log πθu+ϵ (aℓ | sℓ ) − ∇ log πθu (aℓ | sℓ )

Ea∼πθu+ϵ (·|sℓ )

≤ Rmax (h + 1)LS ϵ∥θ − θ ′ ∥,

∇ log πθu+ϵ (aℓ | sℓ ) − ∇ log πθu (aℓ | sℓ )

so, by the first assumption on the policy scores: Eτ0:h ∼phθ [∥Zh (u)∥2 ] = u

h X ℓ=0

Eτ0:ℓ ∼pℓθ [∥∇ log πθu (aℓ | sℓ )∥2 ] ≤ (h + 1)C12 . u

Then: (B) lim = ϵ↓0 ϵ

Z Z

lim

phθu+ϵ (τ0:h ) − phθu (τ0:h ) ϵ

ϵ↓0

rh+1 Zh (u)dτ0:h

∇phθu (τ0:h )⊤ (θ − θ ′ )rh+1 Zh (u)dτ0:h = Eτ0:h ∼phθ Zh (u)Zh (u)⊤ (θ − θ ′ )rh+1 ,

and

h i (B) 2 ≤ Rmax Eτ0:h ∼phθ ∥Zh (u)∥ ∥θ − θ ′ ∥ u ϵ↓0 ϵ

lim

≤ Rmax (h + 1)C12 ∥θ − θ ′ ∥.

Now, from Equation (9): lim sup ϵ↓0

∥Gh (u + ϵ) − Gh (u)∥ ∥(A)∥ ∥(B)∥ ≤ lim sup + lim sup ϵ ϵ ϵ ϵ↓0 ϵ↓0 = lim sup ϵ↓0

∥(A)∥ (B) + lim ϵ↓0 ϵ ϵ

≤ Rmax (h + 1)(LS + C12 )∥θ − θ ′ ∥. The same decomposition shows that Gh is continuous on [0, 1]. By Lemma H.1: ∥Gh (1) − Gh (0)∥ ≤ Rmax (h + 1)(LS + C12 )∥θ − θ ′ ∥. Finally: ′

∥∇J(θ ) − ∇J(θ)∥ ≤

∞ X

h=0

γ h ∥Gh (1) − Gh (0)∥

≤ Rmax (LS + C12 )∥θ − θ ′ ∥

∞ X

h=0

Rmax (LS + C12 ) ∥θ − θ ′ ∥. = (1 − γ)2

γ h (h + 1)

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

Lemma D.3 (Weighted Hellinger continuity). Suppose that Assumption 3.1(1) holds. For every integer r ≥ 0 and every θ1 , θ2 ∈ Θ, Z

Hγ (τ )r

p(τ | θ1 ) −

2 p C 2 Mr+1 2 p(τ | θ2 ) dτ ≤ 1 ∥θ1 − θ2 ∥ . 4

Proof. We recall a result by Paczolay et al. (2024), proved here for completeness Let θt = (1 − t)θ2 + tθ1 ,

∆ = θ1 − θ2 ,

t ∈ [0, 1].

Convexity of Θ guarantees that θt ∈ Θ. Because the stopping rule and the environment are independent of the policy parameters, Hγ (τ )−1

∇ log p(τ | θt ) = Consequently,

h=0

∇ log πθt (aa | sh ).

dp 1p p(τ | θt ) = p(τ | θt ) ⟨∆, ∇ log p(τ | θt )⟩ . dt 2

By the fundamental theorem of calculus and Cauchy–Schwarz, p

2 p p(τ | θ1 ) − p(τ | θ2 ) Z ∥∆∥2 1 2 p(τ | θt ) ∥∇ log p(τ | θt )∥ dt. ≤ 4 0

Multiplying by Hγ (τ )r and integrating over τ yields Z

2 p(τ | θ2 ) dτ   2 Hγ −1 2 Z 1 X ∥∆∥   ≤ Eτ ∼p(·|θt ) Hγr ∇ log πθt (aa | sh )  dt. 4 0

Hγ (τ )r

p(τ | θ1 ) −

h=0

The score increments are martingale differences. Conditionally on Hγ , Assumption 3.1(i) therefore gives 

Hγ −1

 X Eτ ∼p(·|θt )  ∇ log πθt (aa | sh ) h=0

Since the distribution of Hγ is independent of θt ,

Substitution proves the claim.



 Hγ  ≤ C12 Hγ .

h i 2 E Hγr ∥∇ log p(τ | θt )∥ ≤ C12 Mr+1 .

b † J(θk ) − ∇θ J(θk )∥2 ] be Lemma D.4 (Estimation Error for LVR-PG). Under Assumption 3.1, let ∆k := E[∥∇ 2 θ 2 the estimation error of the LVR-PG estimator. Letting λ := 1 − (1 − p)(1 − α) and letting C†,ω > 0 denote the bound on the variance of the (defensive) importance weights, the following recurrence holds for all k ∈ JKK: ∆k+1 ≤ (1 − λ)∆k + where Cν :=

4α2 (1−p) p N + B

ν2.

2(1 − λ)C†,ω E[∥θk+1 − θk ∥22 ] + Cν , B

Cesani, Papini, Restelli

Proof. We analyze the estimation error conditioned on the Bernoulli random variable ck ∼ B(p). By the law of total expectation, the expected estimation error ∆k+1 decomposes as follows: h i b † J(θk+1 ) − ∇θ J(θk+1 )∥2 | ck = 1 ∆k+1 = p · E ∥∇ 2 θ h i b † J(θk+1 ) − ∇θ J(θk+1 )∥2 | ck = 0 . + (1 − p) · E ∥∇ 2 θ

When ck = 1, the estimator executes a full-batch refresh. Because this relies on a new batch of N on-policy trajectories, the conditional error is bounded by the variance of the standard GPOMDP estimator obtained in Lemma D.1: h i 2 b † J(θk+1 ) − ∇θ J(θk+1 )∥22 | ck = 1 ≤ ν . E ∥∇ θ N When ck = 0, the estimator applies the momentum update. Following the proof of Lemma 8 of Yuan et al. (2020), we condition on the history Fk available after computing θk+1 and before drawing ck and the fresh b † J(θk ) are fixed, while the fresh trajectories {τi }B are trajectories. Under this conditioning, θk , θk+1 , and ∇ i=1 θ independent samples from ξpθk+1 + (1 − ξ)pθk . Substituting the momentum update and adding and subtracting the corresponding gradients gives: b † J(θk+1 ) − ∇θ J(θk+1 ) = (1 − α)(∇ b † J(θk ) − ∇θ J(θk )) ∇ θ θ # " B 1 X (ωξ (θk+1 , τi )g(τi | θk+1 ) − ωξ (θk , τi )g(τi | θk )) − ∇θ J(θk+1 ) + ∇θ J(θk ) + (1 − α) B i=1 " # B 1 X +α ωξ (θk+1 , τi )g(τi | θk+1 ) − ∇θ J(θk+1 ) . B i=1 The three terms represent the previous estimation error, the error in estimating the consecutive-gradient difference, and the current-gradient estimation error, respectively. The latter two have zero conditional expectation by unbiasedness of the weighted estimates. Consequently, their cross terms with the previous estimation error vanish in conditional expectation. Applying ∥u + v∥22 ≤ 2∥u∥22 + 2∥v∥22 to these two fresh error terms, and using independence across trajectories, yields h i b † J(θk+1 ) − ∇θ J(θk+1 )∥2 | Fk , ck = 0 E ∥∇ 2 θ

b † J(θk ) − ∇θ J(θk )∥22 ≤ (1 − α)2 ∥∇ θ h i 2(1 − α)2 2 + Eτ ∼ξpθk+1 +(1−ξ)pθk ∥ωξ (θk+1 , τ )g(τ | θk+1 ) − ωξ (θk , τ )g(τ | θk ) − ∇θ J(θk+1 ) + ∇θ J(θk )∥2 B h i 2α2 2 + Eτ ∼ξpθk+1 +(1−ξ)pθk ∥ωξ (θk+1 , τ )g(τ | θk+1 ) − ∇θ J(θk+1 )∥2 . B

The factors 1/B follow because the centered contributions from distinct trajectories are conditionally independent. For the consecutive-gradient error, removing the centering and applying Lemma B.1 gives h i 2 Eτ ∼ξpθk+1 +(1−ξ)pθk ∥ωξ (θk+1 , τ )g(τ | θk+1 ) − ωξ (θk , τ )g(τ | θk ) − ∇θ J(θk+1 ) + ∇θ J(θk )∥2 h i 2 ≤ Eτ ∼ξpθk+1 +(1−ξ)pθk ∥ωξ (θk+1 , τ )g(τ | θk+1 ) − ωξ (θk , τ )g(τ | θk )∥2 ≤ C†,ω ∥θk+1 − θk ∥22 .

Here, the first inequality uses the fact that the expectation of the weighted gradient difference is ∇θ J(θk+1 ) − ∇θ J(θk ). The second inequality is the mean-squared error bound provided by Lemma B.1. For the current-

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

gradient error, we similarly obtain: i h 2 Eτ ∼ξpθk+1 +(1−ξ)pθk ∥ωξ (θk+1 , τ )g(τ | θk+1 ) − ∇θ J(θk+1 )∥2 i h 2 ≤ Eτ ∼ξpθk+1 +(1−ξ)pθk ∥ωξ (θk+1 , τ )g(τ | θk+1 )∥2 = Eτ ∼pθk+1 ωξ (θk+1 , τ )∥g(τ | θk+1 )∥22 ≤

ν2 1 Eτ ∼pθk+1 ∥g(τ | θk+1 )∥22 ≤ . ξ ξ

The equality follows by canceling one importance weight against the mixture distribution. The final inequalities use ωξ (θk+1 , τ ) ≤ 1/ξ and the uncentered second-moment bound established in the proof of Lemma D.1. Substituting these bounds into the conditional estimation error inequality gives: h i b † J(θk+1 ) − ∇θ J(θk+1 )∥22 | Fk , ck = 0 E ∥∇ θ 2

2 2

b † J(θk ) − ∇θ J(θk )∥2 + 2(1 − α) C†,ω ∥θk+1 − θk ∥2 + 2α ν . ≤ (1 − α)2 ∥∇ 2 2 θ B ξB

Taking expectation over the preceding history, and using the independence of ck from that history, yields, h i b † J(θk+1 ) − ∇θ J(θk+1 )∥2 | ck = 0 E ∥∇ 2 θ ≤ (1 − α)2 ∆k +

2α2 ν 2 2(1 − α)2 C†,ω E ∥θk+1 − θk ∥22 + . B ξB

Summing the two branches, we obtain, 2 2α2 ν 2 ν 2(1 − α)2 C†,ω 2 2 ∆k+1 ≤ p + (1 − p) (1 − α) ∆k + E ∥θk+1 − θk ∥2 + N B ξB 2 2 pν 2(1 − p)(1 − α) C†,ω 2α2 (1 − p)ν 2 = (1 − p)(1 − α)2 ∆k + E ∥θk+1 − θk ∥22 + + . B N ξB

Recognizing that (1 − p)(1 − α)2 = 1 − λ, and plugging our choice of ξ = 1/2 from Lemma B.1, this yields the recurrence: 2(1 − λ)C†,ω p 4α2 (1 − p) 2 ∆k+1 ≤ (1 − λ)∆k + E ∥θk+1 − θk ∥2 + + ν2. B N B

CONVERGENCE

In this section, the last-iterate global-convergence guarantee for the LVR-PG algorithm is provided. In particular, Theorem 5.1 provides the sample-complexity for the LVR-PG framework, and while Corollaries E.1 and E.2 provide the sample complexities DEF-PAGE-PG and DEF-STORM-PG as instantiations of LVR-PG. Finally, Corollary 5.1 provides the convergence result for LVR-PG when instantiated for Fisher-non-degenerate policies. The lemmas used to prove the results of this section are provided in Appendix D and H. E.1

Proof of Theorem 5.1

Here, the proof of Theorem 5.1 is provided. Leveraging the proof technique in Theorem 4.5 of Xu et al. (2019) for projected gradient ascent, we construct a recurrence that depends on both the sub-optimality gap and the variance of the estimator. We show that this recurrence achieves minimax-optimal sample complexity up to logarithmic factors and horizon terms. Theorem 5.1 (Global Convergence of LVR-PG). Under Assumptions 3.1 and 3.2, for any target accuracy ϵ > 0 and fixed mini-batch size B ≥ 1, let the batch sizes be N, N0 = Θ(ϵ−2 ) and the learning rate be η = Θ(Bϵ). For appropriately chosen hyperparameters satisfying p, α = O(Bϵ2 ) and p + α = Ω(Bϵ2 ) and choosing ξ = 1/2,

Cesani, Papini, Restelli

LVR-PG guarantees an expected suboptimality gap J ∗ − E[J(θK )] ≤ ψ + ϵ with a total expected sample complexity of at most: 3 2 χ Rmax e , n=O (1 − γ)4 ϵ2

e hides logarithmic factors. where O(·)

Proof. Following the proof of Theorem 4.5 by Xu et al. (2019), we start by redefining the objective function to incorporate the constraint set via the non-smooth indicator function IΘ (θ), introducing J (θ) := J(θ) − IΘ (θ). We formally define the generalized gradient mapping as Gη (θ) := η1 (PΘ (θ +η∇J(θ))−θ). Note that the mapping Gη serves as a generalized projected gradient at θ. By definition, in the unconstrained setting where Θ = RdΘ , this recovers the standard gradient, yielding Gη (θ) = ∇θ J(θ). According to the definition of IΘ (θ): ( 0, if u ∈ Θ IΘ (u) = , +∞ otherwise we have arg maxθ∈RdΘ J (θ) = arg maxθ∈Θ J(θ) := θ ∗ . Letting J˜∗ := J ∗ − ψ and defining µ := 1/χ2 , we reformulate the WGD condition (Assumption 3.2) over the bounded domain using this gradient mapping: √ µ max{0, J˜∗ − J (θk )} ≤ ∥Gη (θk )∥2 Considering an iteration k ∈ JKK, the parameter update applies projected stochastic gradient ascent: θk+1 = b † J(θk )). By expanding the Euclidean projection and discarding terms independent of the optimizaPΘ (θk + η ∇ θ tion variable, this is equivalent to: 1 b † J(θk ), u⟩ . θk+1 = arg min IΘ (u) + ∥u − θk ∥22 − ⟨∇ θ 2η u∈Rd

We define the stochastic gradient mapping as G̃k := η1 (θk+1 − θk ). Let g ∈ ∂IΘ (θk+1 ) be a subgradient of the indicator function. According to the optimality condition of the projection step, we have g + η1 (θk+1 − θk ) − b † J(θk ) = 0. By the convexity of IΘ , it follows that: ∇ θ

IΘ (θk+1 ) ≤ IΘ (θk ) + ⟨g, θk+1 − θk ⟩ 1 † b = IΘ (θk ) − (θk+1 − θk ) − ∇θ J(θk ), θk+1 − θk . η

From the L-smoothness of J(θ) obtained in Lemma D.2, we can write the ascent lemma as follows: J(θk+1 ) ≥ J(θk ) + ⟨∇θ J(θk ), θk+1 − θk ⟩ −

L ∥θk+1 − θk ∥22 . 2

We construct the one-step descent for the constrained objective J (θ) by subtracting the indicator function upper bound from the smoothness lower bound. Expanding the inner product isolates the quadratic penalty, yielding: b † J(θk ), θk+1 − θk ⟩ + 1 ∥θk+1 − θk ∥22 − L ∥θk+1 − θk ∥22 J (θk+1 ) ≥ J (θk ) + ⟨∇θ J(θk ) − ∇ θ η 2 b † J(θk ), G̃k ⟩ + η∥G̃k ∥2 − L ∥θk+1 − θk ∥2 . = J (θk ) + η⟨∇θ J(θk ) − ∇ 2 2 θ 2

Applying Young’s inequality ⟨x, y⟩ ≥ − 21 ∥x∥22 − 12 ∥y∥22 to the inner product, we bound the relation: η b † J(θk )∥22 + η ∥G̃k ∥22 − L ∥θk+1 − θk ∥22 J (θk+1 ) ≥ J (θk ) − ∥∇θ J(θk ) − ∇ θ 2 2 2 η η 1 L † 2 2 b = J (θk ) − ∥∇θ J(θk ) − ∇θ J(θk )∥2 + ∥G̃k ∥2 + − ∥θk+1 − θk ∥22 . 2 4 4η 2

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

By expanding the definitions of the gradient mappings and applying the property of the Euclidean projection operator ∥PΘ (x) − PΘ (y)∥2 ≤ ∥x − y∥2 , we bound the difference between the exact and stochastic gradient mappings: 1 b † J(θk )) PΘ (θk + η∇θ J(θk )) − PΘ (θk + η ∇ θ η 2 1 b † J(θk )) ≤ (θk + η∇θ J(θk )) − (θk + η ∇ θ η 2 † b = ∥∇θ J(θk ) − ∇ J(θk )∥2 .

∥Gη (θk ) − G̃k ∥2 =

Utilizing the inequality ∥Gη (θk )∥22 ≤ 2∥G̃k ∥22 + 2∥Gη (θk ) − G̃k ∥22 , which follows from adding and subtracting the

stochastic gradient mapping and applying Young’s inequality, we bound the remaining mapping term: η η η b † J(θk )∥2 . ∥G̃k ∥22 ≥ ∥Gη (θk )∥22 − ∥∇θ J(θk ) − ∇ 2 θ 4 8 4 Substituting this lower bound yields the final single-step proximal descent inequality: 3η b † J(θk )∥2 + η ∥Gη (θk )∥2 + 1 − L ∥θk+1 − θk ∥2 . J (θk+1 ) ≥ J (θk ) − ∥∇θ J(θk ) − ∇ 2 2 2 θ 4 8 4η 2

(10)

Reversing the sign, applying the total expectation, and substituting the suboptimality rk := E[J˜∗ − J (θk )] and b † J(θk ) − ∇θ J(θk )∥2 ], we obtain the projected suboptimality recurrence: the estimation error ∆k := E[∥∇ 2 θ 3η 1 L η 2 − E ∥θk+1 − θk ∥22 . (11) rk+1 ≤ rk − E ∥Gη (θk )∥2 + ∆k − 8 4 4η 2 2 From Lemma unified variance recurrence uses the effective decay rate λ := 1 − (1 − p)(1 − α) and noise D.4, the 4α2 (1−p) p floor Cν := N + ν 2 . The variance recurrence is: B

∆k+1 ≤ (1 − λ)∆k +

(1 − λ)C†,ω E ∥θk+1 − θk ∥22 + Cν . B

(12)

We introduce the potential function Φk := rk + c∆k with a coupling constant c > 0. Because the estimation error ∆k is intrinsically non-negative, the potential strictly upper-bounds the suboptimality (Φk ≥ rk ). Consequently, establishing the convergence of Φk is sufficient to guarantee the convergence of rk . Combining equations (11) and (12), we construct the unified recurrence: 3η 1 L η 2 − Φk+1 ≤ rk − E ∥Gη (θk )∥2 + ∆k − E ∥θk+1 − θk ∥22 8 4 4η 2 2(1 − λ)C†,ω 2 + c (1 − λ)∆k + E ∥θk+1 − θk ∥2 + Cν B η 3η 2 = Φk − E ∥Gη (θk )∥2 − cλ − ∆k 8 4 1 L 2(1 − λ)C†,ω − − −c E ∥θk+1 − θk ∥22 + cCν . 4η 2 B To simplify the recurrence, we determine the constant c by requiring the ∆k coefficient to retain an exact − 3η 4 residual descent rate: 3η 3η 3η cλ − = ⇒c= . 4 4 2λ Substituting this choice of c, we require the sequence distance coefficient to remain non-negative to eliminate it from the upper bound: 1 L 3η(1 − λ)C†,ω − − ≥ 0. 4η 2 λB

Cesani, Papini, Restelli

To ensure the sequence distance coefficient provides sufficient slack to absorb the variance accumulation, we 1 tighten the standard smoothness restriction. By rigorously restricting the baseline learning rate to η ≤ 4L , we L 1 1 L 1 1 1 enforce the bound 2 ≤ 8η , which guarantees the strictly positive residual 4η − 2 ≥ 4η − 8η = 8η . Substituting this residual isolates the maximum stable learning rate required to absorb the variance accumulation: s 3η(1 − λ)C†,ω λB 1 ≥ ⇒η≤ . 8η λB 24(1 − λ)C†,ω Under these stability conditions, the recurrence simplifies to: 3η η 3ηCν Φk+1 ≤ Φk − E ∥Gη (θk )∥22 − ∆k + . 8 4 2λ

(13)

µη 3η 3ηCν 2 max {0, rk } − ∆k + . 8 4 2λ

(14)

Substituting the modified gradient domination condition and applying Jensen’s inequality for both the maximum and square operations yields: Φk+1 ≤ Φk −

To establish a last-iterate guarantee, we must prove that the algorithm does not leave the target accuracy region once it enters it. We explicitly define the non-negative sequence xk := max{0, Φk } and show it unconditionally satisfies a unified descent recurrence. We evaluate the transition for xk based on the sign of Φk . If Φk ≤ 0, we 3ηCν ν have xk = 0. From Equation (13), dropping the non-positive descent terms yields Φk+1 ≤ Φk + 3ηC 2λ ≤ 2λ . 3ηCν Taking the positive part of both sides guarantees xk+1 ≤ 2λ , which satisfies the target recurrence evaluated at xk = 0. Conversely, if Φk > 0, we have xk = Φk . Because Φk ≤ max{0, rk } + c∆k , it follows that at least one of the following conditions must hold: either max{0, rk } ≥ Φ2k , or c∆k ≥ Φ2k . If the first case holds (max{0, rk } ≥ Φ2k ), we bound the suboptimality descent while discarding the negative variance term: µη xk 2 µη µη 2 max {0, rk } ≤ − = − x2k . − 8 8 2 32 k If the second case holds (c∆k ≥ Φ2k ), utilizing our choice of c = 3η/2λ yields ∆k ≥ λx 3η . Discarding the suboptimality term bounds the variance descent term: 3η 3η λxk λ − ∆k ≤ − = − xk . 4 4 3η 4

Bounding the descent in Equation (14) by the minimum of these two rates, and observing that taking the maximum operator xk+1 = max{0, Φk+1 } on the left preserves the inequality because the right-hand side is inherently non-negative or bounded safely by 0, we obtain the final unconditional recurrence: µη 2 λ 3ηCν xk+1 ≤ xk − min xk , xk + . 32 4 2λ 3ηCν λ We directly apply Lemma H.2 to the invariant sequence xk with a = µη 32 , b = 4 , and e = 2λ . Because λ ≤ 1 λ structurally, we inherently satisfy the lemma’s contraction requirement ρϵ ≤ b = 4 < 1. Hence, from Lemma H.2, the iteration complexity is described by:

K ≥ max

32 4 , µηϵ λ

log+

2Φ0 . ϵ

(15)

To guarantee convergence to the target accuracy ϵ, the noise term must satisfy two conditions. The first condition 2 µηϵ2 µλϵ2 ν e ≤ a ϵ2 requires 3ηC 2λ ≤ 64 , which simplifies to bounding the noise floor Cν ≤ 96 . The second condition λϵ λ2 ϵ ν e ≤ b 2ϵ requires 3ηC 2λ ≤ 8 , which dictates the maximum stable learning rate η ≤ 12Cν . We satisfy the first 2

accuracycondition Cν ≤ µλϵ 96 by configuring the algorithmic parameters such that each of the two additive terms

in Cν =

4α2 (1−p) p N + B

ν 2 is independently bounded by half of the target limit, µλϵ 192 . With the unified decay

rate λ = p + (1 − p)(2α − α2 ), we evaluate both terms to define the feasible geometric region.

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

First Term of Cν and Batch Size. therefore sufficient to enforce:

Observing that 2α − α2 ≥ 0, we establish the lower bound λ ≥ p. It is µpϵ2 192ν 2 pν 2 . ≤ =⇒ N ≥ N 192 µϵ2

To minimize sample cost while satisfying this requirement, we select a full batch size N = Θ(ϵ−2 ) and initialize with N0 = N = Θ(ϵ−2 ). Second Term of Cν and Momentum. Observing that 2α − α2 = α(2 − α) ≥ α for any α ∈ (0, 1], and dropping the positive p term from λ, we obtain the lower bound λ ≥ (1 − p)α. Substituting this lower bound into the right-hand side, it is strictly sufficient to require: µ(1 − p)αϵ2 4α2 (1 − p)ν 2 ≤ . B 192 Because α > 0, we divide both sides by the common factor α(1 − p) to directly isolate α: 4αν 2 µϵ2 µBϵ2 . ≤ =⇒ α ≤ B 192 768ν 2 This establishes the strict upper bound α = O(Bϵ2 ). Expected Sample Cost and Refresh Probability.

We choose p, α ≥ 0 such that

µBϵ2 . 768ν 2 This ensures the momentum constraint established above. For sufficiently small ϵ, we have p + α ≤ 1/2, and hence p+α=

p + α ≤ λ = p + (1 − p)(2α − α2 ) ≤ p + 2α ≤ 2(p + α).

Therefore, λ = Θ(µBϵ2 /ν 2 ), with universal implicit constants. Moreover, since p ≤ µBϵ2 /(768ν 2 ), µBϵ2 192ν 2 +1 +B pN + (1 − p)B ≤ 768ν 2 µϵ2 5B 1 ≤ + = O(B). 4 2 Learning Rate. To achieve the optimal total sample complexity n = Õ(ϵ−2 ), and match the lower-bound established by Theorem 3.1 up to logarithmic factors, the iteration complexity K must be bounded by O((Bϵ2 )−1 ). This bound limits the total number of optimization steps to guarantee that the cumulative sample cost of the O(B) per-iteration updates does not breach the optimal Õ(ϵ−2 ) global sample complexity. Given the initial batch N0 = Θ(ϵ−2 ) and an expected per-iteration sample cost bounded by O(B), the number of iterations must satisfy K · O(B) ≤ Õ(ϵ−2 ), which mandates K ≤ O((Bϵ2 )−1 ). The sufficient iteration budget in Equation (15) contains the estimator-decay term 4/λ. To keep this term within the desired iteration budget O((Bϵ2 )−1 ), we impose λ = Ω(Bϵ2 ). This condition controls the iteration complexity of our analysis; it does not establish that configurations with smaller λ necessarily require more iterations to reach the target accuracy. Expanding the definition of the decay rate yields: λ = 1 − (1 − p)(1 − α)2 = p + 2α − α2 − 2pα + pα2 . Since the upper bounds p = O(Bϵ2 ) and α = O(Bϵ2 ) are established, the higher-order terms α2 , pα, and pα2 scale as O(B 2 ϵ4 ) or smaller. Consequently, for sufficiently small target accuracy ϵ → 0, the decay rate is dominated by its linear components, reducing asymptotically to λ = p + 2α − O(B 2 ϵ4 ). To satisfy the λ = Ω(Bϵ2 ) decay floor, these dominant terms must jointly fulfill the geometric condition p + α = Ω(Bϵ2 ). For any configuration (p, α) satisfying this combined system of bounds, the decay rate and noise floor scale precisely as λ = Θ(Bϵ2 ) and Cν = Θ(Bϵ4 ), respectively. We evaluate the remaining step-size restrictions using these asymptotic rates. The last-iterate λ2 ϵ stability condition η ≤ 12C resolves to η ≤ Θ(Bϵ). Concurrently, the variance recurrence threshold evaluates to ν q λB 12(1−λ)C†,ω = Θ(Bϵ). By explicitly selecting the step size η to match this scaling alongside the L-smoothness limit, all stability requirements are unconditionally satisfied: s ( ) 1 λ2 ϵ λB η = min , , = Θ(Bϵ). 4L 12Cν 24(1 − λ)C†,ω

Cesani, Papini, Restelli

Sample Complexity. With these conditions established, Lemma H.2 guarantees that it suffices to choose the number of iterations as: 32 4 2Φ0 log+ . K = max , µηϵ λ ϵ Substituting our choice of η into the iteration bound gives: ) ' & ( p 2Φ0 128L 384Cν 32 24(1 − λ)C†,ω 4 √ , , log+ . K = max , µϵ µλ2 ϵ2 λ ϵ µϵ λB The noise constraint Cν ≤ µλϵ2 /96 implies 384Cν 384 µλϵ2 4 ≤ = . 2 2 µλ ϵ µλ2 ϵ2 96 λ Thus, this term is absorbed by the estimator-decay term. Moreover, the established bound λ ≥ µBϵ2 /(768ν 2 ) yields 3072ν 2 4 ≤ . λ µBϵ2 Using the same lower bound on λ and 1 − λ ≤ 1, the variance-stability term satisfies s p p 32 24C†,ω 768ν 2 32 24(1 − λ)C†,ω √ ≤ µϵ µB 2 ϵ2 µϵ λB √ p 3072 2 ν C†,ω = . µ3/2 Bϵ2 Combining these bounds, absorbing numerical constants and logarithmic factors, and accounting for the ceiling, we obtain: ! p ν C†,ω L ν2 e K =O 1+ + + 3/2 2 . µϵ µBϵ2 µ Bϵ The expected total sample complexity n is determined by the initial batch size N0 plus the sum of the expected batch sizes drawn over the K iterations: n = N0 + K(pN + (1 − p)B). By substituting N0 = 192ν 2 /(µϵ2 ) , the iteration bound above, and the bounded per-iteration cost pN + (1 − p)B = O(B), we obtain: ! p ν C†,ω BL ν2 e n=O 1+B+ + 2 + 3/2 2 . µϵ µϵ µ ϵ

e −2 ) as ϵ → 0. Thus, for fixed B and fixed positive problem-dependent constants, the complexity is n = O(ϵ To establish the asymptotic dependence on the reward bounds and the effective horizon, we substitute the 2 problem-dependent constants. From Lemma D.1, the GPOMDP second-moment bound scales as ν 2 = O(Rmax (1 − −3 2 γ) ). From Lemma B.1, the defensive mean-squared smoothness constant scales as C†,ω = O(Rmax (1 − γ)−5 ). Substituting these bounds into the terms proportional to ϵ−2 , and using µ = χ−2 , yields: 2 χ2 χ3 e Rmax + , n=O ϵ2 (1 − γ)3 (1 − γ)4 where the policy-regularity and defensive-mixture constants are treated as fixed. This establishes the minimaxoptimal dependence on ϵ, up to logarithmic factors, while retaining the explicit dependence on the WGD constant and the effective horizon.

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

E.2

Corollaries of Theorem 5.1

Here, we consider the sample complexity of two specific instantiations of LVR-PG: DEF-PAGE-PG and DEF-STORM-PG. First, we show how the parameter λ, defined in Lemma B.1, changes setting the α and p parameters. Then, we study the batch size N , mini-batch size B and learning rate η to recover the desired sample complexity. Corollary E.1 (Sample Complexity of DEF-PAGE-PG). Under Assumptions 3.1–3.2, for a fixed mini-batch size B ≥ 1 and sufficiently small target accuracy ϵ > 0, through an appropriate choice of the algorithmic parameters (full batch size N , initial batch size N0 , refresh probability p, and learning rate η), DEF-PAGE-PG with α = 0 guarantees J ∗ − E[J(θk )] ≤ ψ + ϵ with a sample complexity of at most: B n = N0 + K 1 + B − N 2 2 χ χ3 e Rmax + . =O ϵ2 (1 − γ)3 (1 − γ)4 e hides logarithmic factors, and B, the policy-regularity constants, and the defensive-mixture parameter Here, O(·) are treated as fixed. Proof. Setting the momentum parameter to α = 0 specializes the generic variance recurrence used in the proof of Theorem 5.1 to the DEF-PAGE-PG estimator. Under this configuration, the effective decay rate λ and Cν simplify to: λ = p,

Cν =

pν 2 . N

For p > 0, the noise constraint Cν ≤ µλϵ2 /96 reduces to: µpϵ2 96ν 2 pν 2 ≤ =⇒ N ≥ . N 96 µϵ2 Accordingly, we select N0 = N = 96ν 2 /(µϵ2 ) and p = 1/N . For sufficiently small ϵ, we have 96ν 2 /(µϵ2 ) ≥ 1, so that 96ν 2 192ν 2 ≤N ≤ . 2 µϵ µϵ2

Next, we evaluate the stability constraints on the learning rate. For the variance stability requirement η ≤ p λB/[24(1 − λ)CDEF,ω ], using λ = 1/N and 1 − λ ≤ 1, it suffices to enforce: s s µB B η≤ ϵ≤ . 4608ν 2 CDEF,ω 24N CDEF,ω For the accuracy requirement η ≤ λ2 ϵ/(12Cν ), substitution gives: pN ϵ ϵ λ2 ϵ = = . 2 12Cν 12ν 12ν 2 Defining cη := min

(

1 , 12ν 2

µB 4608ν 2 CDEF,ω

)

we therefore select η = min{1/(4L), cη ϵ}. The sufficient iteration budget established in the proof of Theorem 5.1 is K ≥ max{32/(µηϵ), 4/λ} log+ (2Φ0 /ϵ). Using 4/λ = 4N ≤ 768ν 2 /(µϵ2 ) and substituting the full learning-rate choice, we select: & ( ) ' √ p 128L 768ν 2 1536 2 ν CDEF,ω 2Φ0 √ K = max , , log+ . µϵ µϵ2 ϵ µ3/2 Bϵ2

Cesani, Papini, Restelli

Since an iteration draws N trajectories with probability p = 1/N and B trajectories otherwise, the expected per-iteration cost is 1 + (1 − 1/N )B. Consequently: B . n = N0 + K 1 + B − N Substituting the selected values of N0 and K,and using 1 + B − B/N ≤ 1 + B, yields: ! p (1 + B)ν CDEF,ω (1 + B)L (1 + B)ν 2 e √ + + n=O 1+B+ . µϵ µϵ2 µ3/2 Bϵ2

For fixed B and fixed positive problem-dependent constants, the terms proportional to ϵ−2 dominate as ϵ → 0. 2 2 Substituting ν 2 = O(Rmax (1 − γ)−3 ), CDEF,ω = O(Rmax (1 − γ)−5 ), and µ = χ−2 gives: 2 χ2 χ3 Rmax e + , n=O ϵ2 (1 − γ)3 (1 − γ)4 where B, the policy-regularity constants, and the defensive-mixture parameter are treated as fixed.

Corollary E.2 (Sample Complexity of DEF-STORM-PG). Under Assumptions 3.1–3.2, for a fixed mini-batch size B ≥ 1 and sufficiently small target accuracy ϵ > 0, through an appropriate choice of the algorithmic parameters (momentum α, initial batch size N0 , and learning rate η), DEF-STORM-PG with p = 0 and defensive-mixture parameter ξ = 1/2 guarantees J ∗ − E[J(θk )] ≤ ψ + ϵ with a sample complexity of at most: n = N0 + KB 2 χ2 χ3 e Rmax =O + . ϵ2 (1 − γ)3 (1 − γ)4

e hides logarithmic factors, and B and the policy-regularity constants are treated as fixed. Here, O(·)

Proof. Setting the refresh probability to p = 0 specializes the generic variance recurrence used in the proof of Theorem 5.1 to the DEF-STORM-PG estimator. Under the defensive-mixture choice ξ = 1/2, the decay rate λ and the corrected noise floor Cν simplify to: λ = 2α − α2 ,

Cν =

4α2 ν 2 . B

Since λ ≥ α for α ∈ [0, 1], a sufficient condition for Cν ≤ µλϵ2 /96 is: 4α2 ν 2 µαϵ2 µBϵ2 ≤ =⇒ α ≤ . B 96 384ν 2 We therefore select α = µBϵ2 /(384ν 2 ) and N0 = 96ν 2 /(µϵ2 ) . For sufficiently small ϵ, this choice satisfies p α ∈ (0, 1). For the variance stability requirement η ≤ λB/[24(1 − λ)CDEF,ω ], using λ ≥ α and 1 − λ ≤ 1, we enforce: s s αB µB 2 η≤ = ϵ. 24CDEF,ω 9216ν 2 CDEF,ω For the last-iterate accuracy requirement, λ ≥ α gives: λ2 ϵ α2 ϵ Bϵ ≥ = . 12Cν 12(4α2 ν 2 /B) 48ν 2 Consequently, defining cη := min

(

B , 48ν 2

µB 2 9216ν 2 CDEF,ω

)

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

we select η = min{1/(4L), cη ϵ}. Using the sufficient iteration budget established in the proof of Theorem 5.1, together with 4/λ ≤ 4/α = 1536ν 2 /(µBϵ2 ), we select: ) ' & ( p 2Φ0 128L 1536ν 2 3072ν CDEF,ω , log+ . K = max , µϵ µBϵ2 ϵ µ3/2 Bϵ2 Here, the terms proportional to ϵ−1 and ϵ−2 follow by substituting the full learning-rate choice into 32/(µηϵ). Because p = 0, the algorithm draws a fixed mini-batch of size B at every iteration. Consequently, the total sample complexity is: n = N0 + KB. Substituting the selected values of N0 and K gives: ! p 2 ν C ν BL DEF,ω e 1+B+ . + 2+ n=O µϵ µϵ µ3/2 ϵ2

For fixed B and fixed positive problem-dependent constants, the terms proportional to ϵ−2 dominate as ϵ → 0. 2 2 Substituting ν 2 = O(Rmax (1 − γ)−3 ), CDEF,ω = O(Rmax (1 − γ)−5 ), and µ = χ−2 yields: 2 Rmax χ2 χ3 e n=O + , ϵ2 (1 − γ)3 (1 − γ)4 where the policy-regularity constants are treated as fixed.

SAMPLE COMPLEXITY UNDER FISHER-NON-DEGENERACY

While Theorem 5.1 establishes the sample complexity bounds under the abstract weak gradient domination condition, we apply Assumptions C.2 and C.1 to apply Lemma C.1. Note that, in the FND setting, we consider the unconstrained parameter space Θ = Rd . Corollary 5.1 (Sample complexity under FND). In the unconstrained setting where Θ = RdΘ , letting χ√= C1 /µF √ ϵbias κ +ϵ and ψ = ϵbias κ/(1 − γ), assuming κ < ∞, LVR-PG achieves a suboptimality gap J ∗ − E[J(θK )] ≤ 1−γ with a total sample complexity of: 2 C13 Rmax e . n=O (1 − γ)4 µ3F ϵ2 Proof. The result follows directly from Theorem 5.1 by applying the Fisher-induced Gradient Domination Lemma. Specifically, the lemma establishes that under Assumptions C.2 and C.1, the Weak Gradient Dom√ ination condition holds with the constants χ = C1 /µF and ψ = ϵbias κ/(1 − γ). Substituting these specific values into the optimality gap and the general sample complexity bound of Theorem 5.1 immediately yields the stated result.

LOWER-BOUND

Theorem 3.1 (Sample Complexity Lower Bound). For any discount factor γ ∈ [2/3, 1) and sufficiently small target accuracy 0 < ϵ < O

Rmax γ(1−γ)

, there exists a class of MDPs M and a policy parametrization satisfying

Assumptions 3.1 and 3.2, such that any algorithm guaranteeing an expected sub-optimality gap J ∗ −E[J(θK )] ≤ ϵ must collect a number of trajectories n satisfying: 2 Rmax −2 n=Ω ϵ . (1 − γ)2

Before starting with the proof of Theorem 3.1, we describe it and its difference from previous works. The proof relies on the information-theoretic framework for minimax lower bounds and uses Le Cam’s two-point

Cesani, Papini, Restelli

method. While the hard instance construction shares topological similarities with the absorbing MDPs introduced by Azar et al. (2013), we accommodate the specific geometry of policy optimization. While Azar et al. (2013) establishes lower bounds for unconstrained tabular reinforcement learning, in our proof, we consider a constrained continuous policy parametrization, θ ∈ [α, 1 − α]. This domain restriction is the critical mechanism that enforces Assumption 3.1. Furthermore, we demonstrate that this constrained geometry satisfies Assumption 3.2 with χ = 4/3 and ψ = 0, avoiding vanishing gradients at the optimal boundaries. To establish a fundamental lower bound on the sample complexity of any learning algorithm, we must construct an adversarial scenario in which making the correct decision is statistically difficult, yet an incorrect guess incurs a penalty. We achieve this by designing two nearly identical MDPs, M1 and M2 . These instances differ strictly by a small perturbation δ in the transition probabilities, making them difficult to distinguish, yet they require mutually exclusive optimal policies. We first quantify the sub-optimality gap to show that if an algorithm A fails to identify the true underlying MDP and selects a parameter favouring the wrong action, it suffers a performance penalty of at least Ω(δ(1 − γ)−1 ). By tuning this ”wrong-action” penalty to perfectly match our target accuracy threshold ϵ, we isolate the required perturbation scale to δ = O(ϵ(1 − γ)2 ). Because a valid A must guarantee ϵ-optimality across all instances, it is forced to determine whether it is interacting with M1 or M2 . If it collects too few samples, the trajectory distributions of the two MDPs remain virtually identical, and the algorithm will inevitably guess wrong with high probability, thereby suffering the tuned ϵ penalty. We formalize this through Le Cam’s method, which implies that, to reliably distinguish the two instances, the total Kullback-Leibler divergence between their n-trajectory distributions must exceed a given threshold. Finally, we establish how much data is required to cross this threshold by analytically upper-bounding the KL divergence. We show that the divergence accumulates to at most O(nδ 2 (1 − γ)−2 ). Substituting our chosen δ into this upper bound and solving for the sample size n reveals that the minimum amount of data required to 2 ϵ−2 ). distinguish the instances, and thus avoid the sub-optimality penalty, is exactly Ω((1 − γ)−2 Rmax

Proof. The proof is subdivided into several parts. Part I: Construction of the Hard Instance. We consider a class of MDPs consisting of two instances, M ∈ {M1 , M2 }, with state space S = {s, s̄} and action space A = {a0 , a1 }. The state s̄ is an absorbing state where any action a ∈ A yields a deterministic self-transition with zero reward, meaning P (s̄|s̄, a) = 1 and R(s̄, a, s̄) = 0. In the initial state s, taking an action a triggers a self-transition to s with probability pa , yielding a reward of Rmax , and transitions to the absorbing state s̄ with probability 1 − pa , yielding Rmax . The two instances differ strictly in the transition probabilities from the initial state s. For the instance M1 , we set pa0 = p + δ and pa1 = p, making a0 the optimal action. Conversely, for the instance M2 , we set pa0 = p and pa1 = p + δ, making a1 the optimal action. To ensure the transition probabilities remain valid while capturing the lower-bound complexity dependence on the effective horizon, we define the base transition probability as p = 1 − 1−γ γ . Consequently, to satisfy the requirement that p + δ ≤ 1, the perturbation parameter δ is strictly bounded by δ ≤ 1−γ 2γ . a0 : p, Rmax

a0 : p + δ, Rmax a0 : 1 − (p + δ), Rmax s

a0 : 1 − p, Rmax s̄

∀a : 1, 0

a1 : 1 − p, Rmax

s̄

∀a : 1, 0

a1 : 1 − (p + δ), Rmax

a1 : p, Rmax

a1 : p + δ, Rmax

Figure 3: Transition dynamics for instance M1 .

Figure 4: Transition dynamics for instance M2 .

We consider a direct policy parametrization in which the scalar parameter θ determines the probability of

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

selecting the action a0 in the initial state s. For the binary action space A = {a0 , a1 }, the policy is defined as: ( θ if a = a0 , πθ (a | s) = 1 − θ otherwise. Part II: Verification of the Assumptions. Here, we check that the policy class we have choosen satisfies Assumptions 3.1 and 3.2. To ensure the policy space satisfies the regularity constraints of Assumption 3.1, we restrict the parameter domain to Θ = [α, 1 − α] for a strictly positive constant α ∈ (0, 1/2). The score function is given by: ( 1 if a = a0 , ∇θ log πθ (a | s) = θ 1 − 1−θ otherwhise. Condition (i) requires the score norm to be bounded. Since θ ∈ [α, 1 − α], the probability of any action is bounded strictly away from zero, uniformly bounding the score. We establish the constant C1 as the supremum of the score function over the parameter space and action space: 1 1 1 , = . sup ∇θ log πθ (a | s) 2 = max max θ 1−θ α θ∈[α,1−α] a∈A Thus, condition (i) is satisfied with C1 ≤ 1/α. To verify condition (ii), we must establish that the score function is Lipschitz continuous in expectation. We first calculate the Hessian of the log-policy: ( − θ12 if a = a0 , 2 ∇θ log πθ (a | s) = 1 − (1−θ) otherwise. 2 The restricted domain Θ guarantees that the Hessian norm is uniformly bounded by 1/α2 . By the Mean Value Theorem, the squared difference in the score function for any two parameters θ, θ′ ∈ Θ is bounded by the squared supremum of the Hessian. For any action a ∈ A: !2 2

sup ∇2θ log πθ̃ (a | s) 2

∇θ log πθ (a | s) − ∇θ log πθ′ (a | s) 2 ≤

θ̃∈Θ

∥θ − θ′ ∥22

2 1 ∥θ − θ′ ∥22 α2 1 = 4 ∥θ − θ′ ∥22 . α ≤

Because this upper bound holds deterministically for all actions a ∈ A, taking the expectation over a ∼ πθ (· | s) preserves the inequality. Thus, condition (ii) is satisfied with the constant LS = 1/α2 : h i 1 2 ∇θ log πθ (a | s) − ∇θ log πθ′ (a | s) 2 ≤ 4 ∥θ − θ′ ∥22 . E α a∼πθ We now verify the validity of Assumption 3.2 with ψ = 0 in our setting. We start computing the expected return J (i) (θ), its optimal value J ∗,(i) within the restricted domain Θ = [α, 1 − α], and the gradient norm ∥∇θ J (i) (θ)∥2 for both instances i ∈ {1, 2}. By assigning a reward of Rmax to any action taken in state s prior to reaching the zero-reward absorbing state s̄, the expected immediate reward at time t, given st = s, is exactly Rmax . The expected discounted return resolves to a standard geometric series: J(θ) =

∞ X t=0

γ t P (st = s | s0 = s)Rmax = Rmax

∞ X

(γpθ )t =

t=0

Rmax . 1 − γpθ

For the specific instances M1 and M2 , the effective self-transition probabilities under the policy πθ are: (1)

pθ = θ(p + δ) + (1 − θ)p = p + θδ, (2)

pθ = θp + (1 − θ)(p + δ) = p + (1 − θ)δ.

Cesani, Papini, Restelli

Table 3: Values for J (i) (θ), J ∗,(i) , and ∇θ J (i) (θ) 2 for the M instances. Instance M1 M2

J (i) (θ)

J ∗,(i)

∇θ J (i) (θ) 2

Rmax 1−γ(p+θδ) Rmax 1−γ(p+(1−θ)δ)

Rmax 1−γ(p+(1−α)δ) Rmax 1−γ(p+(1−α)δ)

γδRmax (1−γ(p+θδ))2 γδRmax (1−γ(p+(1−θ)δ))2

Because the expected return monotonically increases with the self-transition probability, the optimal returns (i) J ∗,(i) over the constrained domain Θ = [α, 1 − α] are achieved by maximizing pθ . For M1 , this occurs at θ = 1 − α, and for M2 , this occurs at θ = α. In both cases, the maximum self-transition probability evaluates to p + (1 − α)δ. Differentiating the objective function with respect to θ cleanly isolates the gradient of the transition probability: ∇θ J (i) (θ) =

γRmax (i) (1 − γpθ )2

(i)

∇ θ pθ .

Applying this to both instances yields the values defined in Table 3. We establish the constant χ by first evaluating ∗,(i) (i) (θ) ≤ χ. As we will formalize in Remark G.1, the ratio with respect to the unconstrained gradient, J∥∇θ J−J (i) (θ)∥ 2 bounding this unconstrained ratio is sufficient to satisfy Assumption 3.2 for the generalized mapping Gη . Starting with M1 , the sub-optimality gap reduces to: Rmax Rmax − 1 − γ(p + (1 − α)δ) 1 − γ(p + θδ) γRmax ((p + (1 − α)δ) − (p + θδ)) = (1 − γ(p + (1 − α)δ))(1 − γ(p + θδ)) γRmax (1 − α − θ)δ = . (1 − γ(p + (1 − α)δ))(1 − γ(p + θδ))

J ∗,(1) − J (1) (θ) =

Dividing this gap by the gradient norm causes both γ and Rmax to cancel out: J ∗,(1) − J (1) (θ) (1 − γ(p + θδ))2 γRmax (1 − α − θ)δ = · (1 − γ(p + (1 − α)δ))(1 − γ(p + θδ)) γδRmax ∇θ J (1) (θ) 2 = (1 − α − θ)

1 − γ(p + θδ) . 1 − γ(p + (1 − α)δ)

Applying the definitions p = 2γ−1 (requiring γ > 1/2) and δ ≤ 1−γ γ 2γ , the baseline effective horizon evaluates to 1 − γp = 2(1 − γ). We bound the denominator from below: 1 − γ(p + (1 − α)δ) ≥ 1 − γp − γδ ≥ 2(1 − γ) −

1−γ 3 = (1 − γ). 2 2

Leveraging θδ > 0, the numerator is bounded from above: 1 − γ(p + θδ) ≤ 1 − γp = 2(1 − γ). Because the domain restriction ensures (1 − α − θ) ≤ 1, we obtain the uniform bound for M1 : J ∗,(1) − J (1) (θ) 2(1 − γ) 4 ≤1· 3 = . (1) 3 ∇θ J (θ) 2 2 (1 − γ)

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

We repeat the exact procedure for M2 . The optimal parameter for M2 is θ∗ = α. The sub-optimality gap is: Rmax Rmax − 1 − γ(p + (1 − α)δ) 1 − γ(p + (1 − θ)δ) γRmax ((p + (1 − α)δ) − (p + (1 − θ)δ)) = (1 − γ(p + (1 − α)δ))(1 − γ(p + (1 − θ)δ)) γRmax (θ − α)δ = . (1 − γ(p + (1 − α)δ))(1 − γ(p + (1 − θ)δ))

J ∗,(2) − J (2) (θ) =

Dividing by the gradient norm for M2 yields: 1 − γ(p + (1 − θ)δ) J ∗,(2) − J (2) (θ) = (θ − α) . (2) 1 − γ(p + (1 − α)δ) ∇θ J (θ) 2 The denominator bound remains identical to M1 . For the numerator, since (1 − θ)δ > 0: 1 − γ(p + (1 − θ)δ) ≤ 1 − γp = 2(1 − γ). The parameter restriction θ ∈ [α, 1 − α] enforces (θ − α) ≤ 1 − 2α < 1. Substituting these bounds yields the limit for M2 : J ∗,(2) − J (2) (θ) 4 2(1 − γ) < . ≤ (1 − 2α) · 3 (2) 3 ∇θ J (θ) 2 2 (1 − γ) The preceding computations establish J ∗,(i) − J (i) (θ) ≤

4 ∥∇θ J (i) (θ)∥2 , 3

i ∈ {1, 2}.

We now verify the corresponding inequality for the generalized gradient mapping. Remark G.1 (Boundary Conditions and the Gradient Mapping). Because the policy space is restricted to Θ = [α, 1 − α], we must verify that Assumption 3.2 also holds when projection clips the update. The optimal parameters are θ∗,(1) = 1 − α and θ∗,(2) = α. For both instances, the gradient points toward the corresponding optimum, so projection gives ∥G(i) η (θ)∥2 = min

∥∇θ J

(i)

|θ∗,(i) − θ| (θ)∥2 , η

If the update is not clipped, the generalized mapping equals the gradient, and the previously established inequality J ∗,(i) − J (i) (θ) ≤ 43 ∥∇θ J (i) (θ)∥2 applies directly. Otherwise, the projected update reaches θ∗,(i) , yielding |θ∗,(i) − (i) θ| = η∥Gη (θ)∥2 . By the mean value theorem, J ∗,(i) − J (i) (θ) ≤ sup ∥∇θ J (i) (θ′ )∥2 |θ∗,(i) − θ| θ ′ ∈Θ

ηγδRmax ∥G(i) (θ)∥2 . [1 − γ(p + (1 − α)δ)]2 η

The regularity constants established above, C1 = 1/α and LS = 1/α2 , give L = 2Rmax /[α2 (1 − γ)2 ]. Using η ≤ 1/L, 1 − γ(p + (1 − α)δ) ≥ 23 (1 − γ), and γδ ≤ (1 − γ)/2, the coefficient in the last display is at most (i) α2 (1 − γ)/9 ≤ 4/3. Thus, J ∗,(i) − J (i) (θ) ≤ 34 ∥Gη (θ)∥2 also holds when projection clips the update. At the optimum, both sides vanish. Consequently, Assumption 3.2 holds throughout Θ, for every 0 < η ≤ 1/L, with ψ = 0 and χ = 4/3. Part III: Value Gap and Choice of Perturbation. To establish the statistical hardness, we must ensure that failing to identify the correct MDP results in a substantial performance penalty. Specifically, we require that if an algorithm A outputs a policy that favors the wrong action, the sub-optimality gap is at least 4ϵ.

Cesani, Papini, Restelli

In instance M1 , the optimal parameter is θ∗ = 1 − α > 1/2. The algorithm outputs a highly sub-optimal policy if it incorrectly favors action a1 , which occurs when θ ≤ 1/2. We evaluate the sub-optimality gap for M1 given θ ≤ 1/2 to find a strict lower bound. From the previous derivation, the gap is: J ∗,(1) − J (1) (θ) =

γRmax (1 − α − θ)δ . (1 − γ(p + (1 − α)δ))(1 − γ(p + θδ))

To lower-bound this gap, we lower-bound the numerator and upper-bound the denominator. Because θ ≤ 1/2, the term (1 − α − θ) is bounded below by (1/2 − α). Furthermore, since we established the condition γ ≥ 1/2 to ensure valid transition probabilities, we substitute γ = 1/2 to strictly lower-bound the numerator and remove its dependence on γ: 1 Rmax (1 − 2α)δ 1 −α δ = . γRmax (1 − α − θ)δ ≥ Rmax 2 2 4 For the denominator, since θδ ≥ 0 and (1 − α)δ ≥ 0, the effective horizon terms are strictly upper-bounded by the baseline effective horizon 1 − γp = 2(1 − γ): (1 − γ(p + (1 − α)δ))(1 − γ(p + θδ)) ≤ (2(1 − γ))(2(1 − γ)) = 4(1 − γ)2 . Combining these bounds, the sub-optimality gap for any parameter θ ≤ 1/2 is bounded from below: J ∗,(1) − J (1) (θ) ≥

Rmax (1−2α)δ 4 4(1 − γ)2

Rmax (1 − 2α)δ . 16(1 − γ)2

To enforce that this misidentification penalty is at least 4ϵ, we equate this lower bound to 4ϵ and solve for the perturbation parameter δ: Rmax (1 − 2α)δ 64ϵ(1 − γ)2 = 4ϵ =⇒ δ = . 16(1 − γ)2 Rmax (1 − 2α) This specific choice of δ enforces the required value gap while controlling the statistical indistinguishability of the instances. To satisfy the transition probability constraint δ ≤ 1−γ 2γ , the target accuracy ϵ must be sufficiently small: 64ϵ(1 − γ)2 1−γ Rmax (1 − 2α) ≤ =⇒ ϵ ≤ . Rmax (1 − 2α) 2γ 128γ(1 − γ) Part IV: Statistical Test and Information-Theoretic Lower Bound. We formulate the learning process as a statistical testing problem. Suppose an algorithm A interacts with an unknown instance Mi , i ∈ {1, 2}, collects a possibly random number of trajectories NA , and subsequently outputs a parameter estimate θb ∈ Θ. The algorithm is not informed whether the underlying environment is M1 or M2 , and its policies may depend on all previously observed trajectories. For A to be considered a successful ϵ-optimal algorithm on these instances, its expected suboptimality gap must satisfy h i b ≤ ϵ, EA,Mi J ∗,(i) − J (i) (θ) i ∈ {1, 2},

where J ∗,(i) = maxθ∈Θ J (i) (θ). We define the worst-case expected trajectory budget as n := max EA,Mi [NA ]. i∈{1,2}

We may assume that n < ∞, since otherwise the claimed lower bound holds trivially. Using the suboptimality bound derived in Part III, any output θb < 1/2 under M1 incurs a gap of at least 4ϵ. Therefore, h i b ϵ ≥ EA,M1 J ∗,(1) − J (1) (θ) 1 b , ≥ 4ϵ PA,M1 θ < 2

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

which implies: PA,M1

1 θb < 2

≤

1 . 4

By symmetric reasoning under M2 , any output θb ≥ 1/2 incurs a gap of at least 4ϵ, yielding, 1 1 PA,M2 θb ≥ ≤ . 2 4 Summing these error probabilities gives:

PA,M1

1 θb < 2

+ PA,M2

1 1 θb ≥ ≤ . 2 2

Let PA,M1 and PA,M2 denote the probability measures over the complete stopped interaction transcript under the two instances. This transcript includes the algorithm’s internal randomization, the observed trajectories, b Interpreting θb ≥ 1/2 as selecting M1 , Le Cam’s inequality gives: and its final output θ. 1 1 b b + PA,M2 θ ≥ PA,M1 θ < 2 2 ≥ 1 − dTV (PA,M1 , PA,M2 ) .

Consequently, the total variation distance must be at least 1/2. Applying Pinsker’s inequality, we obtain, 1 ≤ dTV (PA,M1 , PA,M2 ) 2 r 1 ≤ DKL (PA,M1 ∥ PA,M2 ), 2 and hence: DKL (PA,M1 ∥ PA,M2 ) ≥

1 . 2

To translate this information requirement into a trajectory complexity lower bound, we next upper-bound the divergence in terms of the expected number of collected trajectories. Part V: Upper Bound on the KL Divergence. We upper-bound the KL divergence of the complete interaction transcript through the conditional chain rule for relative entropy. Conditional on the same realized history, the algorithm uses the same action-selection and stopping rules under both instances. Moreover, the initial state, reward function, and independent geometric termination mechanism are identical under M1 and M2 . Consequently, only the environment transition kernels contribute to the conditional KL divergence. We first bound the divergence contributed by a single transition. Since s̄ is absorbing and possesses identical transition dynamics in both instances, DKL P (1) (· | s̄, a) P (2) (· | s̄, a) = 0. At the active state s, the Bernoulli parameters under (M1 , M2 ) are (p + δ, p) for a0 and (p, p + δ) for a1 . Using the standard inequality dKL (x∥y) ≤ (x − y)2 /[y(1 − y)], we obtain, δ2 , p(1 − p) δ2 dKL (p∥p + δ) ≤ . (p + δ)(1 − p − δ)

dKL (p + δ∥p) ≤

Recall that p = (2γ − 1)/γ, γ ≥ 2/3, and δ ≤ (1 − γ)/(2γ). These conditions imply: p≥

1 , 2

1−p=

1−γ , γ

1−p−δ ≥

1−γ . 2γ

Cesani, Papini, Restelli

Thus, both variance terms are bounded below by (1 − γ)/(4γ), yielding,

4δ 2 4γδ 2 DKL P (1) (· | s, a) P (2) (· | s, a) ≤ ≤ . 1−γ 1−γ a∈{a0 ,a1 } max

This bound holds uniformly over the selected action. Next, we bound the number of informative transitions within each trajectory. Let Hj denote the number of observed transitions in trajectory j, and define: Hj −1

Tj :=

1{sj,t =s} ,

t=0

where sj,t and aj,t denote the state and action at time t of trajectory j. Thus, Tj counts the observed transitions from the active state. Each trajectory starts at s and follows the independent geometric termination protocol. We set Tj = 0 when trajectory j is not collected. Let Fj−1 denote the history immediately before trajectory j, including the algorithm’s decision whether to collect it. In particular, {NA ≥ j} is Fj−1 -measurable. On this event, the conditional probability of remaining in s after any active transition is at most p + δ, regardless of the selected action. The geometric termination mechanism can only reduce the number of observed active transitions. Consequently, PA,M1 (Tj > t | Fj−1 ) ≤ (p + δ)t , ∞ X EA,M1 [Tj | Fj−1 ] ≤ (p + δ)t

t ≥ 0,

t=0

2γ 2 1 ≤ ≤ . 1−p−δ 1−γ 1−γ

The conditional expectation bound also holds when the trajectory is not collected, since then Tj = 0. For a history at which trajectory j is collected, let Qi,j (· | Fj−1 ) denote its conditional law under Mi , and define: Kj := DKL (Q1,j (· | Fj−1 ) ∥ Q2,j (· | Fj−1 )) . We set Kj = 0 at histories where trajectory j is not collected. Applying the conditional chain rule within a collected trajectory gives:   Hj −1 X DKL P (1) (· | sj,t , aj,t ) P (2) (· | sj,t , aj,t ) Fj−1  Kj = EA,M1  t=0

4δ EA,M1 [Tj | Fj−1 ] 1−γ 8δ 2 ≤ . (1 − γ)2 ≤

Therefore, the same upper bound applies to every collected trajectory, uniformly over the preceding history and the algorithm’s policy choices. Finally, applying the conditional chain rule across trajectories yields: DKL (PA,M1 ∥ PA,M2 ) ∞ X = EA,M1 1{NA ≥j} Kj j=1

≤

∞ 8δ 2 X PA,M1 (NA ≥ j) (1 − γ)2 j=1

8δ 2 EA,M1 [NA ] (1 − γ)2 8nδ 2 ≤ . (1 − γ)2 =

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

The chain-rule identities for random trajectory lengths and the complete interaction history follow by padding observations with zeros after termination, applying the chain rule to finite prefixes, and passing to the limit. The algorithm’s internal randomization has the same distribution under both instances, while its action-selection, continuation, and output rules coincide conditional on the same history. Hence, only the environment transition dynamics contribute to the KL divergence. Part VI: Sample Complexity Lower Bound. Combining the results from Parts IV and V, any algorithm achieving an expected suboptimality gap bounded by ϵ on both instances must satisfy, 8nδ 2 1 . ≤ DKL (PA,M1 ∥ PA,M2 ) ≤ 2 (1 − γ)2 This yields the trajectory budget requirement: n≥

(1 − γ)2 . 16δ 2

Substituting the perturbation parameter selected in Part III, δ=

64ϵ(1 − γ)2 , Rmax (1 − 2α)

we obtain: 2 (1 − γ)2 Rmax (1 − 2α)2 16 4096ϵ2 (1 − γ)4 R2 (1 − 2α)2 = max 2 . 65536ϵ (1 − γ)2

n≥

In particular, fixing α = 1/4 gives: max EA,Mi [NA ] ≥

i∈{1,2}

2 Rmax . 262144ϵ2 (1 − γ)2

Thus, for γ ∈ [2/3, 1) and 0<ϵ≤

Rmax , 256γ(1 − γ)

any algorithm guaranteeing ϵ-optimality on both possible unknown instances requires a worst-case expected number of trajectories satisfying 2 Rmax n=Ω . (1 − γ)2 ϵ2 This establishes the claimed trajectory complexity lower bound for adaptive algorithms, including algorithms whose number of collected trajectories is random.

TECHNICAL LEMMAS

Lemma H.1. Let G : [0, 1] → Rd be continuous on [0, 1]. If, for any u ∈ [0, 1), lim sup ϵ↓0

∥G(u + ϵ) − G(u)∥ ≤ C, ϵ

then ∥G(1) − G(0)∥ ≤ C. Proof. If G(1) = G(0) there is nothing to prove, so assume ∥G(1) − G(0)∥ > 0. By contradiction, suppose ∥G(1) − G(0)∥ > C and choose c ∈ R such that ∥G(1) − G(0)∥ > c > C. Let v :=

G(1) − G(0) , ∥G(1) − G(0)∥

Cesani, Papini, Restelli

and define f : [0, 1] → R as f (u) := v ⊤ G(u) − cu. Then, f (1) − f (0) = ∥G(1) − G(0)∥ − c > 0. Since f is continuous on [0, 1], it attains its minimum at some u⋆ ∈ [0, 1]. Since f (1) > f (0), u⋆ < 1. For sufficiently small ϵ, f (u⋆ + ϵ) − f (u⋆ ) ≥ 0, so: f (u⋆ + ϵ) − f (u⋆ ) ≥ 0. lim sup ϵ ϵ↓0 On the other hand, since ∥v∥ = 1, lim sup ϵ↓0

f (u⋆ + ϵ) − f (u⋆ ) v ⊤ (G(u⋆ + ϵ) − G(u⋆ )) = lim sup −c ϵ ϵ ϵ↓0 ≤ lim sup ϵ↓0

∥G(u⋆ + ϵ) − G(u⋆ )∥ −c ϵ

≤ C − c < 0. Lemma H.2 (Recurrence). Let {xk }∞ k=0 be a non-negative sequence satisfying the following recurrence relation for all k ≥ 0: xk+1 ≤ xk − min ax2k , bxk + e,

where a > 0, b > 0, and e > 0. For a given target accuracy ϵ > 0, define the effective contraction rate ρϵ := min{aϵ, b}. Assume the algorithmic parameters are configured such that ρϵ ∈ (0, 1). If the noise term e 2 satisfies e ≤ a ϵ2 and e ≤ b 2ϵ , then, it suffices to choose a number of iterations K satisfying: 2x0 1 1 , log+ , K ≥ max aϵ b ϵ where log+ (a) := log max{1, a}, to ensure that xk ≤ ϵ for every k ≥ K. Proof. We first establish that the sequence remains within the target neighborhood once it reaches it. By the stated noise conditions, we have: 2 aϵ bϵ ρϵ ϵ e ≤ min , = . 2 2 2 Suppose that xk ≤ ϵ. If xk ≤ ϵ/2, dropping the non-negative descent term yields: xk+1 ≤ xk + e ≤

ϵ ρϵ ϵ + ≤ ϵ, 2 2

where the final inequality follows from ρϵ ∈ (0, 1). Conversely, if ϵ/2 < xk ≤ ϵ, we lower-bound the descent term as follows: min{ax2k , bxk } = xk min{axk , b} n aϵ o ≥ xk min ,b 2 ρϵ ≥ xk . 2 Substituting this bound into the recurrence gives: ρϵ xk+1 ≤ 1 − xk + e 2 ρϵ ρϵ ϵ ≤ 1− ϵ+ = ϵ. 2 2

Consequently, the target neighborhood [0, ϵ] is invariant: if xk ≤ ϵ at any iteration, then xj ≤ ϵ for every j ≥ k. We now evaluate the sequence using a hitting-time argument. Let Tϵ := inf{k ≥ 0 | xk ≤ ϵ} denote the first iteration at which the sequence reaches the target accuracy, with inf ∅ := +∞. If x0 ≤ ϵ, the invariance

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

established above directly guarantees the claim for every iteration. Assume therefore that x0 > ϵ. By the definition of the hitting time, xk > ϵ for every k < Tϵ . This allows us to lower-bound the descent rate prior to reaching the target neighborhood. For any k < Tϵ , factoring out xk yields: min ax2k , bxk = xk min {axk , b} ≥ xk min {aϵ, b} . Substituting the definition of the effective contraction rate ρϵ := min{aϵ, b} into the original inequality yields a standard linear recurrence: xk+1 ≤ (1 − ρϵ )xk + e. To set the hyperparameters so that the target xK ≤ ϵ is reached, we partition the error budget equally, requiring the asymptotic bias to be bounded by 2ϵ and the transient term to be bounded by 2ϵ . Bounding the asymptotic bias requires ρeϵ ≤ 2ϵ , which rearranges to e ≤ ρϵ 2ϵ . Because ρϵ evaluates to the minimum of two regimes, this 2

condition must hold for both possible values. If ρϵ = aϵ, the constraint dictates e ≤ a ϵ2 . If ρϵ = b, the constraint dictates e ≤ b 2ϵ . Satisfying both of these stated hyperparameter conditions ensures the asymptotic bias remains strictly bounded by 2ϵ . Consequently, as long as xk ≥ ϵ > 0, we can rewrite the linear recurrence as: ϵ ϵ xk+1 − ≤ (1 − ρϵ ) xk − . 2 2 For any integer K < Tϵ , unrolling this recursive inequality over K steps yields: ϵ ϵ xK ≤ + (1 − ρϵ )K x0 − 2 2 ϵ ≤ + exp(−ρϵ K)x0 , 2 where the final bound applies the standard logarithmic inequality 1−x ≤ exp(−x), valid for ρϵ ∈ (0, 1). Bounding the remaining transient term by ϵ/2 requires: 1 2x0 K≥ log+ ρϵ ϵ 1 1 2x0 = max , log+ . aϵ b ϵ Fix an integer K satisfying this bound. If Tϵ > K, the preceding estimate gives xK ≤ ϵ, contradicting the definition of Tϵ . Hence, Tϵ ≤ K. By the invariance of the target neighborhood, it follows that xk ≤ ϵ for every k ≥ K, completing the proof.

EXPERIMENTAL DETAILS

We evaluate the empirical sample efficiency of the LVR-PG framework on CartPole-v1, Swimmer-v4, HalfCheetahv4, and Hopper-v4. The experiments have two objectives: (i) to compare the framework’s configurations with GPOMDP (Baxter and Bartlett, 2001) and N-PG-IGT (Fatkhullin et al., 2023), and (ii) to examine sensitivity to the recursive-update parameter α and refresh probability p. We first describe the experimental protocol, then present the environment comparisons, the gradient-variability diagnostic, and the hyperparameter studies. Policies and Implementation CartPole-v1 uses a softmax policy with two hidden layers of width 4. The continuous-control tasks use Gaussian policies with two hidden layers of width 32. All hidden layers use tanh activations, with Xavier-uniform weight initialization and zero biases. Gaussian policies learn a scalar log standard deviation shared across action coordinates, initialized to the values in Table 5. The experiments use fixed trajectory horizons. Return comparisons and hyperparameter studies use Adam, whereas the gradient-variability diagnostic uses a constant scalar step size. Training and evaluation use separate random-number streams. Evaluation returns are undiscounted and obtained from stochastic-policy rollouts; evaluation trajectories are excluded from the training sample count. For the environment comparisons, each evaluation averages 10 episodes, with evaluations every 10 collected training trajectories and at the final updated policy.

Cesani, Papini, Restelli

Table 4: Mean normalized area under the learning curve (AUC) across the four environments; the ± indicate the estimated standard error of the mean. Bold entries indicate the largest mean AUC in each environment. Environment GPOMDP DEF-STORM-PG DEF-PAGE-PG LVR-PG N-PG-IGT Cart-Pole Swimmer Half-Cheetah Hopper

396.05 ± 34.56 24.19 ± 6.15

13.49 ± 30.16

201.90 ± 21.68

481.90 ± 7.85

417.34 ± 37.96

482.39 ± 5.49

380.03 ± 39.46

105.76 ± 51.57

24.08 ± 32.67

55.82 ± 41.76

87.67 ± 23.31

40.86 ± 7.94

369.94 ± 89.62

26.39 ± 5.46

233.65 ± 28.36

33.90 ± 13.28

309.13 ± 44.92

26.22 ± 1.01

368.81 ± 23.97

Table 5: Environment-specific hyperparameter choices for the experiments. Environment Horizon T Batch N Mini-batch B Learning rate η Initial std σ CartPole-v1

500

10−2 −3

–

Swimmer-v4

500

100

HalfCheetah-v4

100

256

10−4

1 √ 0.3

Hopper-v4

100

256

10−4

0.3

Algorithms We consider DEF-STORM-PG (α > 0, p = 0), DEF-PAGE-PG (α = 0, p > 0), and a hybrid configuration (α > 0, p > 0). The first two are the defensive-IS versions of STORM-PG (Yuan et al., 2020) and PAGE-PG (Gargiani et al., 2022), respectively. In the comparison tables and figures, LVR-PG denotes the best hybrid configuration, hence the configuration of α and p that allow LVR-PG to obtain the maximum performance (please refer to Section I.7 to an example of ablation study). The parameter p determines the probability of refreshing the gradient estimator with N new trajectories. The parameter α controls the recursive momentum update; increasing α therefore reduces the weight of this correction. All three configurations use defensive IS with ξ = 0.5, as suggested by the theory. We compare these configurations with GPOMDP (Baxter and Bartlett, 2001) and N-PG-IGT Fatkhullin et al. (2023). GPOMDP computes a fresh on-policy gradient estimate at each update. N-PG-IGT combines normalized updates with implicit gradient transport, using neither importance sampling nor second-order information. The algorithms use an average baseline for gradient estimation. Table 6 summarizes the algorithmic settings used in the environment comparisons. Performance Measures Learning curves report mean evaluation returns over five independent runs. Shaded regions indicate the estimated standard error of the mean. We summarize performance over the training budget using normalized Area under the Curve (AUC). Higher AUC indicates that high returns are reached earlier and maintained over a larger part of the budget. Table 4 reports the mean AUC and its confidence interval, showing that the momentum-only configuration of LVR-PG performs consistently better than the competitors in almost all the environments. I.1

CartPole-v1

CartPole-v1 has a four-dimensional state space (S ⊂ R4 ) and two discrete actions (A = {0, 1}). Figure 5 compares the five algorithms using the settings in Tables 5 and 6. DEF-STORM-PG and LVR-PG reach returns close to the maximum episodic return of 500 after approximately 103 trajectories. Both improve more rapidly than GPOMDP and DEF-PAGE-PG. This shows that, empirically, momentum behaves better than probabilistic refreshes. N-PG-IGT attains high returns but exhibits larger training variance.

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

Table 6: Algorithmic settings for the return comparisons. (∗ The hybrid uses p = 0.5 on CartPole-v1.) For N-PG-IGT, α denotes its gradient-transport momentum parameter. Hyperparameter GPOMDP DEF-STORM-PG DEF-PAGE-PG LVR-PG N-PG-IGT –

0.5

0.1∗

–

Recursive parameter α

–

0.9

Defensive parameter ξ

–

0.5

–

Expected Return J(θ)

Refresh probability p

500 400 300 200

N-PG-IGT GPOMDP DEF-STORM-PG DEF-PAGE-PG LVR-PG

100 0 0

0.2

4 0.6 Trajectories (×104 )

0.8

Figure 5: Learning curves on CartPole-v1. Curves show mean evaluation returns over five runs; shaded regions indicate the estimated standard error of the mean.

I.2

Swimmer-v4

Swimmer-v4 is a locomotion task with an eight-dimensional state space (S ⊂ R8 ) and a two-dimensional action space (A ⊂ R2 ). The policy controls an articulated swimmer moving through a fluid environment.

Expected Return J(θ)

60 40 20 N-PG-IGT GPOMDP DEF-STORM-PG DEF-PAGE-PG LVR-PG

0.0

0.2

0.4 0.6 Trajectories (×104 )

0.8

Figure 6: Learning curves on Swimmer-v4. Curves show mean evaluation returns over five runs; shaded regions indicate the estimated standard error of the mean. Figure 6 shows that DEF-STORM-PG achieves the highest returns over the evaluated training budget. In this environment, the momentum-only configuration of LVR-PG provides the strongest empirical sample efficiency among the tested configurations. While learning faster in the initial part of the training, N-PG-IGT gets stuck in a suboptimal solution around a cumulative reward of 27.

Cesani, Papini, Restelli

I.3

HalfCheetah-v4

Expected Return J(θ)

HalfCheetah-v4 has a 17-dimensional state space (S ⊂ R17 ) and a six-dimensional action space (A ⊂ R6 ). The policy controls the locomotion of an articulated agent. 200 150 100 50 0 GPOMDP DEF-PAGE-PG LVR-PG

−50 −100

0.0

0.2

DEF-STORM-PG N-PG-IGT

0.4 0.6 Trajectories (×105 )

0.8

Figure 7: Learning curves on HalfCheetah-v4. Curves show mean evaluation returns over five runs; shaded regions indicate the estimated standard error of the mean. In Figure 7, DEF-STORM-PG reaches the best return compared to the other algorithms. Again, N-PG-IGT learns faster in the first part of the learning, but early saturates to a lower cumulative reward compared to DEF-STORM-PG. The experiment also shows that DEF-PAGE-PG, and GPOMDP learn slower in the environment, and achieve a lower cumulative return after observing 105 trajectories. I.4

Hopper-v4

Expected Return J(θ)

Hopper-v4 is a locomotion task with an 11-dimensional state space (S ⊂ R11 ) and a three-dimensional action space (A ⊂ R3 ). 500 400 300 200

GPOMDP DEF-STORM-PG DEF-PAGE-PG LVR-PG N-PG-IGT

100 0 0.0

0.2

0.4 0.6 Trajectories (×105 )

0.8

Figure 8: Learning curves on Hopper-v4. Curves show mean evaluation returns over five runs; shaded regions indicate the estimated standard error of the mean. Figure 8 shows that DEF-STORM-PG and N-PG-IGT achieve better performance compared to the other algorithms. Again, this shows that momentum updates are empirically more efficient. Here, we see how DEF-PAGE-PG and GPOMDP learn consistently slower than the algorithms that implement momentum, as they start collecting reward after observing 2 × 104 trajectories. I.5

Gradient-Estimator Variability on CartPole-v1

We complement the return comparisons with a diagnostic of per-trajectory gradient variability on CartPole-v1. For a batch of mk trajectories, let gk,i denote the unweighted, baseline-free GPOMDP contribution evaluated at

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

the current policy parameters. We compute the trace of their sample covariance, mk mk X 1 X 1 2 d ∇ b † J(θk ) = , g ∥ g = Var ∥g − gk,i . k,i k 2 k θ mk − 1 i=1 mk i=1 d ∇ b † J(θk ) across independent runs. The contributions are evaluated at the We plot the mean of log10 Var θ current policy parameters using the batches collected by each algorithm: on-policy batches for GPOMDP and N-PG-IGT, and defensive-mixture batches for the configurations of LVR-PG. Thus, the statistic summarizes the variability of the per-trajectory gradient contributions used in this diagnostic. The experiment uses the configurations of Tables 5 and 6.

ˆ︃ ∇ ˆ︁ θ J(θ)) log10 Var(

5 0

−5

DEF-STORM-PG LVR-PG N-PG-IGT GPOMDP DEF-PAGE-PG

−10 −15

0.0

0.1

0.2 0.3 Trajectories (×104 )

0.4

0.5

Figure 9: Per-trajectory gradient-variability diagnostic on CartPole-v1 over 5 × 103 training trajectories. Values are shown on a base-10 logarithmic scale and averaged over five independent runs; shaded regions indicate the estimated standard error of the mean. Figure 9 shows lower per-trajectory gradient variability for DEF-STORM-PG and the hybrid LVR-PG configuration than for the baselines over much of training. DEF-PAGE-PG also achieves lower values than GPOMDP, while the values for N-PG-IGT increase over the observed budget. I.6

Hyperparameter Ablations on CartPole-v1

500

Expected Return J(θ)

We examine the sensitivity of DEF-PAGE-PG to p ∈ {0.1, 0.5, 0.9} and of DEF-STORM-PG to α ∈ {0.1, 0.5, 0.9}. Both studies use the CartPole-v1 environment with the configuration presented in Tables 5 and 6.

400 300 200 100 DEF-PAGE-PG (p = 0.1) DEF-PAGE-PG (p = 0.5) DEF-PAGE-PG (p = 0.9)

0 −100

0.2

0.4 Trajectories (×104 )

0.8

500 400 300 200 100 DEF-STORM-PG (α = 0.1) DEF-STORM-PG (α = 0.5) DEF-STORM-PG (α = 0.9)

0 −100

0.2

0.4 0.6 Trajectories (×104 )

0.8

Figure 10: Hyperparameter ablations on CartPole-v1 over 104 training trajectories. Left: Refresh probability p ∈ {0.1, 0.5, 0.9} for DEF-PAGE-PG. Right: Recursive-update parameter α ∈ {0.1, 0.5, 0.9} for DEF-STORM-PG. Curves show mean evaluation returns over five runs, shaded regions indicate the estimated standard error of the mean. Figure 10 (left) shows that DEF-PAGE-PG is not much less sensitive to the choice of p, although frequent refreshes improve its final performance. Both p = 0.5 and p = 0.9 reach returns close to 500, whereas p = 0.1 settles

Cesani, Papini, Restelli

near 400. The configuration p = 0.9 maintains high returns while selecting recursive mini-batch updates with small probability. This suggests that, without momentum, relying heavily on recursive mini-batch updates is less effective in the tested setting. The improvement with more frequent full-batch refreshes is consistent with using larger on-policy batches to control gradient-estimation variance. Figure 10 (right) shows that DEF-STORM-PG is very sensitive to the choice of α. The configuration α = 0.9 rapidly reaches returns close to 500, while α = 0.5 requires substantially more trajectories, and α = 0.1 exhibits persistent fluctuations and lower returns, failing to solve the task in the environment. Thus, a large α substantially improves empirical sample efficiency in this setting. Since the historical correction is weighted by 1 − α, the best-performing configuration retains a smaller correction from the previous estimate.

I.7

Hyperparameter Grid Search for LVR-PG on CartPole-v1

We evaluate hybrid configurations of LVR-PG with α ∈ {0.01, 0.5, 0.9} and p ∈ {0.05, 0.3, 0.5}. The policy architecture and training settings match the ablation study in Section I.6. Each configuration uses five independent runs. Figure 11 summarizes normalized AUC and terminal return, with terminal return computed as the mean of the last three evaluations in each run.

0.05

12.7 ±2.4

212.8 ±131.3

379.3 ±60.9

0.3

343.9 ±48.8

422.3 ±26.5

438.8 ±20.1

0.5

415.1 ±55.3

399.4 ±95.9

453.5 ±7.2

0.01

0.5

0.9

Momentum parameter (α)

Panel (b): Last-Iterate Return

Refresh Probability (p)

Panel (a): Normalized AUC.

0.05

9.3 ±0.2

129.1 ±186.3

336.4 ±202.4

0.3

381.9 ±176.2

500.0 ±0.0

490.3 ±19.0

0.5

500.0 ±0.0

422.8 ±151.3

500.0 ±0.0

0.01

0.5

0.9

Momentum parameter (α)

Figure 11: Hybrid hyperparameter grid on CartPole-v1. Left: Mean normalized AUC. Right: Mean terminal return, averaged over the last three evaluations in each run. Entries summarize five independent runs; shaded regions indicate the estimated standard error of the mean. The grid shows sensitivity to both parameters. At p = 0.05, increasing α raises the mean AUC from 12.7 to 379.3 and the mean terminal return from 9.3 to 336.4. More frequent refreshes substantially improve the low-α configuration. Three configurations, (0.5, 0.3), (0.01, 0.5), and (0.9, 0.5), attain a mean terminal return of 500 at the displayed precision, while their mean AUC values differ. The configuration (α, p) = (0.9, 0.5) achieves the largest mean AUC in the grid, 453.5 ± 7.2, combining high terminal performance with the strongest performance over the training budget. These results identify effective choices within the hybrid configuration and show that its performance depends on the interaction between α and p. Together with the experiments presented in Appendix I.6, they motivate selecting DEF-STORM-PG as the primary representative of LVR-PG, since it achieves consistently high mean AUC across the tested environments without periodic full-batch refreshes.

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

I.8

Computational Resources

All the experiments were run on a 2023 14-inch MacBook Pro equipped with an Apple M2 Pro chip and 16 GB of RAM.

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

Analyze & explore related research in Conceptio

Related documents