Paper deep dive
Variance-Reduced Policy Gradient is Nearly Minimax-Optimal
Leonardo Cesani, Matteo Papini, Marcello Restelli
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 10/13/2026, 2:56:04 AM
Summary
This paper introduces Loopless Variance-Reduced Policy Gradient (LVR-PG), a unified framework for first-order policy gradient algorithms that integrates recursive updates with defensive importance sampling. The authors prove that LVR-PG achieves nearly minimax-optimal sample complexity of O~(epsilon^-2) for last-iterate global convergence under weak gradient domination, without requiring second-order operations or bounded importance weight assumptions. They also establish a matching Omega(epsilon^-2) lower bound for continuous parametric policies.
Entities (7)
Relation Signals (7)
LVR-PG → achievessamplecomplexity → O~(epsilon^-2)
confidence 95% · We prove that this algorithmic class achieves O~(epsilon^-2) last-iterate global convergence
LVR-PG → isa → Variance-Reduced Policy Gradient
confidence 95% · In this work, we introduce Loopless Variance-Reduced PG (LVR-PG), a unified theoretical framework that abstracts a class of first-order estimators
LVR-PG → isminimaxoptimal → True
confidence 92% · confirming our framework is minimax-optimal up to logarithmic factors and horizon terms
STORM-PG → isincludedin → LVR-PG
confidence 90% · including known estimators such as PAGE-PG and STORM-PG
PAGE-PG → isincludedin → LVR-PG
confidence 90% · including known estimators such as PAGE-PG and STORM-PG
Policy Gradient → suffersfrom → High Estimation Variance
confidence 90% · Standard Policy Gradient (PG) algorithms suffer from high estimation variance because they rely on Monte Carlo updates
LVR-PG → usestechnique → Defensive Importance Sampling
confidence 90% · abstracts a class of first-order estimators that integrate recursive updates with defensive importance sampling
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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 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 $\tilde{\mathcal{O}}(\epsilon^{-2})$ last-iterate 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 $\Omega(\epsilon^{-2})$ sample complexity limit, confirming our framework is minimax-optimal up to logarithmic factors and horizon terms.
Tags
Links
- Source: https://arxiv.org/abs/2610.13692v1
- Canonical: https://arxiv.org/abs/2610.13692v1
Trouble viewing inline? Open PDF directly →
Full Text
202,618 characters extracted from source content.
Expand or collapse full text
Variance-Reduced Policy Gradient is Nearly Minimax-Optimal Leonardo Cesani11 1 Correspondence to: leonardo.cesani@polimi.it. Matteo Papini Marcello Restelli Politecnico di Milano Università degli Studi di Milano Politecnico di Milano 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 of the variance of the importance weights. † The (⋅)O(·) hides dependencies on γ,C1,LS,χγ,C_1,L_S,χ and ψ, ~(⋅) O(·) hides logarithmic factors. ‡ Requires an additional second-order smoothness assumption. Algorithm Complexity† Convergence Type Gradient Only No 2nd-Order Asm. No Bounded IW Asm. GPOMDP (Montenegro et al., 2024) ~(ϵ−3) O(ε^-3) Last-iterate ✓ ✗ ✓ SRVR-PG (Liu et al., 2020) (ϵ−3)O(ε^-3) Average-iterate ✓ ✗ ✗ STORM-PG-S (Ding et al., 2022) (ϵ−3)O(ε^-3) Average-iterate ✓ ✗ ✗ N-PG-IGT‡ (Fatkhullin et al., 2023) ~(ϵ−2.5) O(ε^-2.5) Last-iterate ✓ ✗ ✓ HARPG‡ (Fatkhullin et al., 2023) ~(ϵ−2) O(ε^-2) Last-iterate ✗ ✗ ✓ ANPG (Mondal and Aggarwal, 2024) (ϵ−2)O(ε^-2) Average-iterate ✗ ✗ ✓ LVR-PG (Theorem 5.1) ~(ϵ−2) O(ε^-2) Last-iterate ✓ ✓ ✓ Lower Bound (Theorem 3.1) Ω(ϵ−2) (ε^-2) ✓ ✓ ✓ Abstract 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 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 ~(ϵ−2) O(ε^-2) last-iterate 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) (ε^-2) sample complexity limit, confirming our framework is minimax-optimal up to logarithmic factors and horizon terms. 1 Introduction In recent years, Reinforcement Learning (Sutton et al., 1998, RL, ) has been used as the central tool for aligning and scaling the reasoning capabilities of Large Language Models (Brown et al., 2020; Achiam et al., 2023, LLMs, ). Methods based on Proximal Policy Optimization (Schulman et al., 2017; Ouyang et al., 2022, PPO,) and, more recently, Group Relative Policy Optimization (Shao et al., 2024, GRPO, ) have achieved enormous success on reasoning tasks (Guo et al., 2025) and aligning model outputs with human preferences (Ziegler et al., 2019; Bai et al., 2022). At their core, the algorithms powering these methods reduce to the Policy Gradient (Deisenroth et al., 2013, PG, ) 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). Actor-critic 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) (ε^-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 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 double-loop 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. 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 ~(ϵ−2.5) 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 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. The question is therefore whether existing gradient-only 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. 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) (ε^-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 last-iterate global convergence with a sample complexity of ~(ϵ−2) O(ε^-2), matching our lower bound 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. 2 Preliminaries Notation. For a measurable set X, we denote by Δ _X the set of probability measures over X. For P∈ΔP∈ _X, if it admits a density, we denote it by p. We will use x∼Px P to express that the random variable x is distributed according to P. For n∈ℕn , we let ⟦n⟧≔1,…,n n \1,…,n\. Vectors are indicated with bold letters. Given two symmetric matrices A and B, we say that A⪰BA B if the matrix A−BA-B is positive semidefinite. Interaction Protocol. We consider an agent interacting with a Markov Decision Process (Puterman, 2014, MDP, ) ℳ=(,,p,r,ρ0,γ)M= (S,A,p,r, _0,γ ) over independent, indefinite-length episodes. In each timestep h=0,1,…h=0,1,…, the agent observes a state h∈⊆ℝd s_h ^d_S, where 0∼ρ0 s_0 _0 is the initial state and ρ0∈Δ _0∈ _S is the initial-state distribution, and executes an action h∈⊆ℝd a_h ^d_A sampled from a parametric stochastic policy π:→Δ _ θ:S→ _A. Here, ∈Θ⊆ℝdΘ θ∈ ^d_ is the parameter vector defining the policy space ΠΘ=π∣∈Θ _ =\ _ θ θ∈ \. The agent then receives a reward rh+1≔r(h,h)∈[−Rmax,Rmax]r_h+1 r( s_h, a_h)∈[-R_ ,R_ ] and transitions to a next state h+1∼p(⋅∣h,h)∈Δ s_h+1 p(· s_h, a_h)∈ _S. For a discount factor γ∈[0,1)γ∈[0,1), the performance of θ is assessed via the expected discounted return under the assumption that ↦π θ _ θ is differentiable. The latter is defined as: J()≔[∑h≥0γhr(h,h)|π], J( θ) [ _h≥ 0γ^hr( s_h, a_h)\, |\, _ θ ], 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:Θ→ℝJ: as the performance function, which is generally non-convex. Because the per-step rewards are bounded, it satisfies |J()|≤Rmax/(1−γ)|J( θ)|≤ R_ /(1-γ) for all ∈Θ θ∈ . We denote the optimal performance as J∗≔max∈ΘJ()J^* _ θ∈ J( θ). Policy Gradients. We consider learning algorithms that iteratively update a sequence of policies π1,…,πK _ θ_1,…, _ θ_K. At each iteration k, the agent collects a dataset k=τ1k,…,τnkkD_k=\ _1^k,…,τ^k_n_k\ of nkn_k independent trajectories drawn from the trajectory distribution induced by the policy pk(τ)p_ θ_k(τ). To accommodate structural or safety constraints common in practical applications, we consider PG methods that restrict the parameter space to a closed convex set Θ⊆ℝdΘ ^d_ and, similarly to Xu et al. (2019), update the parameters via projected stochastic gradient ascent: k+1←Θ(k+η∇^J(k)) θ_k+1 _ ( θ_k+η ∇_ θJ( θ_k) ). Here, η>0η>0 is the learning rate, and ∇^J(k) ∇_ θJ( θ_k) is an unbiased estimator of the true gradient ∇J(k) _ θJ( θ_k). We formalize the optimization geometry over the parameter domain Θ using the generalized gradient mapping η()≔1η(Θ(+η∇J())−)G_η( θ) 1η (P_ ( θ+η∇ J( θ))- θ ). This mapping acts as the projected gradient at θ, recovering the standard gradient ∇J() _ θJ( θ) in the unconstrained case Θ=ℝdΘ =R^d_ . To compute the stochastic gradient estimator ∇^J() ∇_ θJ( θ) from finite interaction data 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−γ1-γ, independently of the interaction history. For each trajectory τi _i, let Hγ,i∈1,2,…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 [Hγ,i]=(1−γ)−1E[H_γ,i]=(1-γ)^-1, and, since Pr(Hγ,i>h)=γh (H_γ,i>h)=γ^h, the expected undiscounted return accumulated before stopping matches the infinite-horizon discounted objective function J()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γ,iH_γ,i, the estimate ∇^J(k) ∇_ θJ( θ_k) is computed from the on-policy dataset kD_k via the GPOMDP (Baxter and Bartlett, 2001) estimator: ∇^J(k) ∇_ θJ( θ_k) =1nk∑i=1nk(τi∣k), = 1n_k _i=1^n_k g( _i θ_k), (1) (τi∣) g( _i θ) ≔∑h=0Hγ,i−1(∑l=0h∇logπ(l∣l))rh+1. _h=0^H_γ,i-1 ( _l=0^h _ θ _ θ( a_l s_l) )r_h+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 (Metelli et al., 2020, IS, ). Given a trajectory τ∼p(⋅∣′)τ p(· θ ), the off-policy GPOMDP estimator is defined as ∇^J()=1n∑i=1nω(,τi)(τi∣) ∇_ θJ( θ)= 1n _i=1^nω( θ, _i) g( _i θ), where ω(,τi)ω( θ, _i) is the importance weight defined by the trajectory density ratio: ω(,τi)≔p(τi)p′(τi)=∏h=0Hγ,i−1π(h∣h)π′(h∣h), ω( θ, _i) p_ θ( _i)p_ θ ( _i)= _h=0^H_γ,i-1 _ θ( a_h s_h) _ θ ( a_h s_h), 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χ^2-divergence between the trajectory distributions induced by θ and ′ θ (Cortes et al., 2010). Since the χ2χ^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). 3 Learning Framework 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. Assumption 3.1 (Regularity). The policy class admits finite constants C1,LS>0C_1,L_S>0 such that, for all ,′∈Θ θ, θ ∈ , and for any ∈ s , we have: (i)sup∈‖∇logπ(∣)‖2≤C1, (i)~~ _ a \| _ θ _ θ( a s) \|_2≤ C_1, (i)∼π[‖∇logπ(∣)−∇logπ′(∣)‖22] (i)~ E_ a _ θ [ \| _ θ _ θ( a s)- _ θ _ θ ( a s) \|_2^2 ] ≤LS2‖−′‖22. ≤ L_S^2\| θ- θ \|_2^2. Assumption 3.1 (i), 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()J( θ) and its stochastic gradient estimator are smooth and have bounded variance, respectively, as formalized in the following proposition (proof in Appendix D). Proposition 3.1. Under Assumption 3.1, the following properties hold. (i)ar((τ∣))≤4Rmax2C12(1−γ)3≕ν2; (i)~~Var ( g(τ θ) )≤ 4R_ ^2C_1^2(1-γ)^3 ν^2; (i)‖∇2J()‖2≤Rmax(C12+LS)(1−γ)2≕L. (i)~\| _ θ^2J( θ)\|_2≤ R_ (C_1^2+L_S)(1-γ)^2 L. 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χ>0 and ψ≥0ψ≥ 0 such that, for every ∈Θ θ∈ and a step size η≤1/Lη≤ 1/L, it holds that: J∗−J()≤χ‖η()‖2+ψ J^*-J( θ)≤χ\|G_η( θ)\|_2+ψ 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 Θ=ℝdΘ =R^d_ , the mapping strictly recovers the true gradient η()=∇J()G_η( θ)= _ θJ( θ), meaning this condition reduces to the standard WGDassumption on the gradient norm. When ψ=0ψ=0, we recover the (strong) gradient domination (GD) property: J∗−J()≤χ‖η()‖2J^*-J( θ)≤χ\|G_η( θ)\|_2. GD is stricter than WGD since it requires that the constrained performance function J()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). Lower Bound for Policy Optimization. Having established the learning framework, we now investigate the statistical limits of the policy optimization problem. Theorem 3.1 (Sample Complexity Lower Bound). For any discount factor γ∈[2/3,1)γ∈[2/3,1) and sufficiently small target accuracy 0<ϵ<(Rmaxγ(1−γ))0<ε<O ( R_ γ(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∗−[J(K)]≤ϵJ^*-E[J( θ_K)]≤ε must collect a number of trajectories n satisfying: n n =Ω(Rmax2(1−γ)2ϵ−2). = ( R_ ^2(1-γ)^2ε^-2 ). Theorem 3.1 establishes an Ω(ϵ−2) (ε^-2) statistical barrier under our regularity and WGD assumptions. In the 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) (ε^-2) statistical barrier. This accuracy dependence is consistent with variance-reduced stochastic optimization under GD, where an (ϵ−2)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) (ε^-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 first-order policy optimization methods attain the optimal accuracy dependence. In non-convex stochastic optimization under WGD, Masiha et al. (2026) establishes an Ω(ϵ−3) (ε^-3) lower bound for the gradient-only, bounded-variance 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 ~(ϵ−2.5) O(ε^-2.5) guarantee, whereas HARPG and ANPG attain the ϵ−2ε^-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. 4 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 last-iterate global convergence with a sample complexity matching the Ω(ϵ−2) (ε^-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(τ)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 _ θ_k+1 with probability ξ∈[0,1]ξ∈[0,1] and from the previous policy πk _ θ_k with probability 1−ξ1-ξ. This yields a mixture trajectory distribution, defined as qξ(τ)=ξpk+1(τ)+(1−ξ)pk(τ)q_ξ(τ)=ξ p_ θ_k+1(τ)+(1-ξ)p_ θ_k(τ). To estimate the gradient at either k+1 θ_k+1 or k θ_k using trajectories sampled from qξq_ξ, we use the defensive IS weight ωξ(,τ)≔p(τ)/qξ(τ) _ξ( θ,τ) p_ θ(τ)/q_ξ(τ), where ∈k+1,k θ∈\ θ_k+1, θ_k\. For ξ∈(0,1)ξ∈(0,1), each target trajectory density enters qξ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/ξ _ξ( θ_k+1,τ)≤ 1/ξ, and similarly ωξ(k,τ)≤1/(1−ξ) _ξ( θ_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]p∈[0,1], which we call refresh probability parameter. At iteration k∈⟦K⟧k∈ K , the evaluation of the target policy k+1 θ_k+1 and the construction of the new gradient estimator ∇^†J(k+1) ∇ _ θJ( θ_k+1) depend on a Bernoulli realization ck∼ℬ(p)c_k (p). If ck=1c_k=1, the framework executes a full refresh, sampling N trajectories directly from the target policy πk+1 _ θ_k+1 to compute a full-batch gradient estimate with Equation (1) with nk=Nn_k=N. If ck=0c_k=0, the framework bypasses the full-batch estimation in favor of a recursive mini-batch update. To evaluate the gradients of both πk+1 _ θ_k+1 and πk _ θ_k simultaneously, LVR-PG collects B≪NB N trajectories independently drawn from the mixture behavior distribution qξ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]α∈[0,1] to control off-policy variance: ∇^†J(k+1)=Bωξ(k+1)+(1−α)[∇^†J(k)−Bωξ(k)], split ∇ _ θJ( θ_k+1)&= g_B _ξ( θ_k+1)\\ & +(1-α) [ ∇ _ θJ( θ_k)- g_B _ξ( θ_k) ], split (2) where Bωξ()≔1B∑i=1Bωξ(,τi)(τi∣) g_B _ξ( θ) 1B _i=1^B _ξ( θ, _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α=0 and p∈[0,1]p∈[0,1] recovers the update rule of PAGE-PG (Gargiani et al., 2022), while setting α>0α>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 estimator ∇^†J(k) ∇_ θ J( θ_k), we update the policy parameters via projected stochastic gradient ascent. The algorithm aims to find a parameter ∈Θ θ∈ that maximizes the performance function subject to this constraint. Algorithm 1 LVR-PG Input: K,N,B,p,α,ξ,η,Θ,0K,N,B,p,α,ξ,η, , θ_0 1 Init. ∇^J(0) ∇_ θJ( θ_0) using N trajectories from π0 _ θ_0; 2 for k=0,…,K−1k=0,…,K-1 do 3 k+1←Θ(k+η∇^†J(k)) θ_k+1 _ ( θ_k+η ∇ _ θJ( θ_k) ); 4 Draw refresh variable ck∼ℬ(p)c_k (p); 5 if ck=1c_k=1 then 6 Sample N trajectories τ1:N∼πk+1 _1:N _ θ_k+1; 7 Estimate gradient with Equation (1); 8 else 9 Sample B trajectories τ1:B _1:B from qξq_ξ; 10 Estimate gradient with Equation (2); 11 Return K θ_K 5 Convergence and Optimality In this section, we establish the sample complexity required by an instantiation of the LVR-PG framework to 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. Theorem 5.1 (Global Convergence of LVR-PG). Under Assumptions 3.1 and 3.2, for any target accuracy ϵ>0ε>0 and fixed mini-batch size B≥1B≥ 1, let the batch sizes be N,N0=Θ(ϵ−2)N,N_0= (ε^-2) and the learning rate be η=Θ(Bϵ)η= (Bε). For appropriately chosen hyperparameters satisfying p,α=(Bϵ2)p,α=O(Bε^2) and p+α=Ω(Bϵ2)p+α= (Bε^2) and choosing ξ=1/2ξ=1/2, LVR-PG guarantees an expected suboptimality gap J∗−[J(K)]≤ψ+ϵJ^*-E[J( θ_K)]≤ψ+ε with a total expected sample complexity of at most: n=~(χ3Rmax2(1−γ)4ϵ2), n= O ( χ^3R_ ^2(1-γ)^4ε^2 ), where ~(⋅) O(·) hides logarithmic factors. Proof Sketch. The proof establishes the minimax-optimal 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≔[‖∇^†J(k)−∇J(k)‖22] _k [\| ∇ _ θJ( θ_k)- _ θJ( θ_k)\|_2^2]. Lemma D.4 quantifies how this error propagates through recursive updates. Letting λ≔1−(1−p)(1−α)2λ 1-(1-p)(1-α)^2 and Ψk≔[‖k+1−k‖22] _k [\| θ_k+1- θ_k\|_2^2 ] we have: Δk+1≤(1−λ)Δk+2(1−λ)C†,ωBΨk+Cν. _k+1≤(1-λ) _k+ 2(1-λ)C_ ,ωB _k+C_ν. Here, C†,ω>0C_ ,ω>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νC_ν combines the contributions of full-batch refreshes and recursive mini-batch updates, weighted by p and α2α^2, respectively. From the L-smoothness of the objective obtained in Proposition 3.1, letting rk≔[~∗−(k)]r_k [ J^*-J( θ_k)], we obtain the recursion of the suboptimality gap: rk+1≤rk−η8[‖η(k)‖22]+3η4Δk−(14η−L2)Ψk. r_k+1≤ r_k- η8E [\|G_η( θ_k)\|_2^2 ]+ 3η4 _k- ( 14η- L2 ) _k. To establish convergence, we study the potential Φk≔rk+cΔk _k r_k+c _k, combining suboptimality and estimation error. Choosing c=3η2λc= 3η2λ and a sufficiently small step size η yields a recursion in which both objective improvement and estimator-error decay contribute to reducing Φk _k. Part I: WGD and Recurrence. Because ‖η(k)‖22\|G_η( θ_k)\|_2^2 provides only local stationarity guarantees, we use Assumption 3.2 to bound the global suboptimality gap directly by the gradient mapping norm. Evaluating the invariant sequence xk≔max0,Φkx_k \0, _k\ reveals a dual-regime dynamical system: xk+1≤xk−minμη32xk2,λ4xk+3ηCν2λ. x_k+1≤ x_k- \ μη32x_k^2, λ4x_k \+ 3η C_ν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λ)3η C_ν/(2λ) accounts for stochastic gradient-estimation error. When the additive term is sufficiently small, Lemma H.2 bounds the iterations required to reach and remain within the target accuracy: K≥⌈max32μηϵ,4λlog(2Φ0ϵ)⌉. K≥ \ 32μηε, 4λ \ ( 2 _0ε ) . Part I: Selection of α,pα,p and η. We now choose the hyperparameters to satisfy the accuracy condition Cν=(μλϵ2)C_ν=O(μλε^2) while controlling the sample cost. Setting N=Θ(ϵ−2)N= (ε^-2) and p=(Bϵ2)p=O(Bε^2) keeps the expected cost of full-batch refreshes comparable to that of mini-batch updates. Choosing α=(Bϵ2)α=O(Bε^2) controls the momentum-dependent contribution to CνC_ν, while requiring p+α=Ω(Bϵ2)p+α= (Bε^2) ensures sufficient estimator-error decay through λ=Ω(Bϵ2)λ= (Bε^2). With a suitable step size η=Θ(Bϵ)η= (Bε), these choices yield K=~((Bϵ2)−1)K= O((Bε^2)^-1) iterations and a total sample complexity n=~(ϵ−2)n= O(ε^-2). ∎ 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ϵ)η= (Bε), and the convergence guarantee applies directly to the last-iterate parameter K θ_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 two-dimensional region of hyperparameter configurations (p,α)(p,α) for which the nearly optimal sample complexity is guaranteed. As illustrated in Figure 1, the conditions p=(Bϵ2)p=O(Bε^2), α=(Bϵ2)α=O(Bε^2), and p+α=Ω(Bϵ2)p+α= (Bε^2), together with the batch-size and learning-rate choices established in the proof, provide sufficient conditions for this guarantee. Remark 5.1 (Unification of Existing Algorithms). Existing variance-reduced estimators emerge as boundary limits of this optimal space: setting α=0α=0 or p=0p=0 recovers DEF-PAGE-PG and DEF-STORM-PG, respectively, both strictly preserving the ~(ϵ−2) O(ε^-2) sample complexity. Setting p=1p=1 forces full-batch evaluations at every step, recovering vanilla GPOMDP. This choice violates the computational boundary p=(Bϵ2)p=O(Bε^2), shifting the algorithm outside the optimal manifold and correctly degrading its complexity to the standard ~(ϵ−3) O(ε^-3) rate (Montenegro et al., 2024). 1Bϵ2 1Bε^2LVR-PG~(ϵ−2) O(ε^-2)p+α=Ω(Bϵ2)p+α= (Bε^2)α=(Bϵ2)α=O(Bε^2)p=(Bϵ2)p=O(Bε^2)DEF-STORM-PG(Corollary E.2)DEF-PAGE-PG(Corollary E.1)//\!/\!/\!GPOMDP(ϵ−3)O(ε^-3)p/(Bϵ2)p/(Bε^2)α/(Bϵ2)α/(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,α)(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=1p=1. 5.1 On Fisher-Non-Degeneracy We specialize Theorem 5.1 to Fisher-Non-Degenerate (FND) policies in the unconstrained setting Θ=ℝdΘ =R^d_ . 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 η()=∇J()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 Θ=ℝdΘ =R^d_ , when the FIM induced by π _ θ is uniformly non-degenerate, i.e., ()=π[∇logπ(∣)∇logπ(∣)⊤]⪰μF F( θ)=E_ _ θ[ _ θ _ θ( s) _ θ _ θ( s) ] _F I for some μF>0 _F>0 and every ∈Θ θ∈ , WGD follows provided that the compatible function approximation error (Agarwal et al., 2021) is bounded. This condition requires π[(Aπ(,)−(1−γ)⊤∇logπ(∣))2]≤ϵbiasE_ _ θ[(A _ θ( s,)-(1-γ) w _ θ _ θ( s))^2]≤ _bias, where =()−1∇J() w= F( θ)^-1 _ θJ( θ) and AπA _ θ is the advantage function of the policy π _ θ. Under these conditions, WGD holds with χ=C1/μFχ=C_1/ _F and ψ=ϵbiasκ/(1−γ)ψ= _biasκ/(1-γ). Here, κ=sup∈ℝdΘ‖νπ∗/νπ‖∞κ= _ θ ^d_ \|ν^π^*/ν _ θ\|_∞ 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 under νπ∗ν^π^* 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 Θ=ℝdΘ =R^d_ , letting χ=C1/μFχ=C_1/ _F and ψ=ϵbiasκ/(1−γ)ψ= _biasκ/(1-γ), assuming κ<∞κ<∞, LVR-PG achieves a suboptimality gap J∗−[J(K)]≤ϵbiasκ1−γ+ϵJ^*-E[J( θ_K)]≤ _biasκ1-γ+ε with a total sample complexity of: n=~(Rmax2C13(1−γ)4μF3ϵ2). n= O ( R_ ^2C_1^3(1-γ)^4 _F^3ε^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. (a) CartPole-v1 (b) Swimmer-v4 DEF-STORM-PG 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. 6 Experimental Results To evaluate the empirical sample efficiency of our framework, we consider CartPole-v1 and Swimmer-v4, 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=0p=0, α>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. 7 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 variance-reduction 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. 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 Achiam et al. (2023) J. Achiam, S. Adler, S. Agarwal, L. Ahmad, I. Akkaya, F. L. Aleman, D. Almeida, J. Altenschmidt, S. Altman, S. Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774. Cited by: §1. Agarwal et al. (2021) A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan On the theory of policy gradient methods: optimality, approximation, and distribution shift. Journal of Machine Learning Research 22 (98), p. 1–76. Cited by: Appendix C, Appendix C, §5.1. Ahmadian et al. (2024) A. Ahmadian, C. Cremer, M. Gallé, M. Fadaee, J. Kreutzer, O. Pietquin, A. Üstün, and S. 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), p. 12248–12267. Cited by: §1. Azar et al. (2013) M. G. Azar, R. Munos, and H. J. Kappen Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Mach. Learn. 91 (3), p. 325–349. Cited by: Appendix G, 1st item, §1, §3. Bai et al. (2022) Y. Bai, A. Jones, K. Ndousse, A. Askell, A. Chen, N. DasSarma, D. Drain, S. Fort, D. Ganguli, T. Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arxiv. arXiv preprint arXiv:2204.05862. Cited by: §1. Baxter and Bartlett (2001) J. Baxter and P. L. Bartlett Infinite-horizon policy-gradient estimation. journal of artificial intelligence research 15, p. 319–350. Cited by: Appendix I, Appendix I, §2. Brown et al. (2020) T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. Language models are few-shot learners. Advances in neural information processing systems 33, p. 1877–1901. Cited by: §1. Cesani et al. (2026) L. Cesani, M. Papini, and M. Restelli How log-barrier helps exploration in policy optimization. External Links: 2603.15001, Link Cited by: Appendix C. Cortes et al. (2010) C. Cortes, Y. Mansour, and M. Mohri Learning bounds for importance weighting. Advances in neural information processing systems 23. Cited by: §2. Deisenroth et al. (2013) M. P. Deisenroth, G. Neumann, and J. Peters A survey on policy search for robotics. Foundations and Trends® in Robotics 2 (1-2), p. 1–142. Cited by: §1. Ding et al. (2022) Y. Ding, J. Zhang, and J. Lavaei On the global optimum convergence of momentum-based policy gradient. External Links: 2110.10116, Link Cited by: Appendix C, Appendix C, Appendix C, Appendix C, Appendix C, Table 1, §1, §1, §3, §5.1, §5.1, §5. Fatkhullin et al. (2023) I. Fatkhullin, A. Barakat, A. Kireeva, and N. He Stochastic policy gradient methods: improved sample complexity for fisher-non-degenerate policies. In International Conference on Machine Learning, p. 9827–9869. Cited by: Appendix C, Appendix C, Appendix I, Appendix I, Table 1, Table 1, §1, §3, §3, §3, §5.1, §5.1. Fatkhullin et al. (2022) I. Fatkhullin, J. Etesami, N. He, and N. Kiyavash Sharp analysis of stochastic optimization under global kurdyka-lojasiewicz inequality. Advances in Neural Information Processing Systems 35, p. 15836–15848. Cited by: §3. Gargiani et al. (2022) M. Gargiani, A. Zanelli, A. Martinelli, T. Summers, and J. Lygeros Page-pg: a simple and loopless variance-reduced policy gradient method with probabilistic gradient estimation. In International conference on machine learning, p. 7223–7240. Cited by: Table 2, Appendix A, Appendix I, 2nd item, §1, §3, §4, §4, §4. Guo et al. (2025) D. Guo, D. Yang, H. Zhang, J. Song, P. Wang, Q. Zhu, R. Xu, R. Zhang, S. Ma, X. Bi, et al. Deepseek-r1: incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948. Cited by: §1. Kakade (2001) S. M. Kakade A natural policy gradient. Advances in neural information processing systems 14. Cited by: Appendix C. Konda and Tsitsiklis (2000) V. R. Konda and J. N. Tsitsiklis Actor-critic algorithms. External Links: Link Cited by: §1. Liu et al. (2020) Y. Liu, K. Zhang, T. Basar, and W. Yin An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems 33, p. 7624–7636. Cited by: Table 1, §1, §5.1, §5. Masiha et al. (2026) S. Masiha, N. Kiyavash, and P. Thiran Sharp first-order lower bounds under sublevel \α α-polyak-lojasiewicz conditions. arXiv preprint arXiv:2606.28278. Cited by: §3, §3. Masiha et al. (2022) S. Masiha, S. Salehkaleybar, N. He, N. Kiyavash, and P. Thiran Stochastic second-order methods improve best-known sample complexity of sgd for gradient-dominated functions. Advances in Neural Information Processing Systems 35, p. 10862–10875. Cited by: §3. Metelli et al. (2020) A. M. Metelli, M. Papini, N. Montali, and M. Restelli Importance sampling techniques for policy optimization. Journal of Machine Learning Research 21 (141), p. 1–75. Cited by: §2. Mondal and Aggarwal (2024) W. U. Mondal and V. 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, p. 3097–3105. Cited by: Table 1, §1, §3. Montenegro et al. (2024) A. Montenegro, M. Mussi, A. M. Metelli, and M. Papini Learning optimal deterministic policies with stochastic policy gradients. arXiv preprint arXiv:2405.02235. Cited by: Table 1, §3, §3, Remark 5.1. Ouyang et al. (2022) L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems 35, p. 27730–27744. Cited by: §1. Owen and Zhou (2000) A. Owen and Y. Zhou Safe and effective importance sampling. Journal of the American Statistical Association 95 (449), p. 135–143. Cited by: Appendix B, §1, §4. Paczolay et al. (2024) G. Paczolay, M. Papini, A. M. Metelli, I. Harmati, and M. Restelli Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds. Machine Learning 113, p. 1–36. External Links: Document Cited by: Table 2, Table 2, Appendix B, Appendix B, Appendix D, 2nd item, §1, §3, §4, §4. Papini et al. (2018) M. Papini, D. Binaghi, G. Canonaco, M. Pirotta, and M. Restelli Stochastic variance-reduced policy gradient. In International conference on machine learning, p. 4026–4035. Cited by: §1, §3. Papini et al. (2022) M. Papini, M. Pirotta, and M. Restelli Smoothing policies and safe policy gradients. Machine Learning 111 (11), p. 4081–4137. Cited by: §2. Puterman (2014) M. L. Puterman Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons. Cited by: §2. Rafailov et al. (2023) R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn Direct preference optimization: your language model is secretly a reward model. Advances in neural information processing systems 36, p. 53728–53741. Cited by: §1. Schulman et al. (2017) J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. Cited by: §1. Shao et al. (2024) Z. Shao, P. Wang, Q. Zhu, R. Xu, J. Song, X. Bi, H. Zhang, M. Zhang, Y. Li, Y. Wu, et al. Deepseekmath: pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300. Cited by: §1. Sutton et al. (1998) R. S. Sutton, A. G. Barto, and A. Barto Reinforcement learning: an introduction. Vol. 1, MIT press Cambridge. Cited by: §1. Sutton et al. (1999) R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems 12. Cited by: §1. Todorov et al. (2012) E. Todorov, T. Erez, and Y. Tassa Mujoco: a physics engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, p. 5026–5033. Cited by: §6. Xu et al. (2019) P. Xu, F. Gao, and Q. Gu Sample efficient policy gradient methods with recursive variance reduction. arXiv preprint arXiv:1909.08610. Cited by: §E.1, §E.1, §1, §2, §3. Yuan et al. (2020) H. Yuan, X. Lian, J. Liu, and Y. Zhou Stochastic recursive momentum for policy gradient methods. arXiv preprint arXiv:2003.04302. Cited by: Table 2, Appendix A, Appendix D, Appendix I, 2nd item, §1, §3, §4, §4, §4. Yuan et al. (2022) R. Yuan, R. M. Gower, and A. Lazaric A general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, p. 3332–3380. Cited by: §3, §3. Yuan et al. (2023) Z. Yuan, H. Yuan, C. Tan, W. Wang, S. Huang, and F. Huang Rrhf: rank responses to align language models with human feedback without tears. arXiv preprint arXiv:2304.05302. Cited by: §1. Zhang et al. (2021) J. Zhang, C. Ni, C. Szepesvari, M. Wang, et al. On the convergence and sample efficiency of variance-reduced policy gradient method. Advances in Neural Information Processing Systems 34, p. 2228–2240. Cited by: §2. Zhao et al. (2011) T. Zhao, H. Hachiya, G. Niu, and M. Sugiyama Analysis and improvement of policy gradient estimation. Advances in Neural Information Processing Systems 24. Cited by: §1, §2. Ziegler et al. (2019) D. M. Ziegler, N. Stiennon, J. Wu, T. B. Brown, A. Radford, D. Amodei, P. Christiano, and G. Irving Fine-tuning language models from human preferences. arXiv preprint arXiv:1909.08593. Cited by: §1. 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. Algorithm 2 Loopless Variance-Reduced Policy Gradient (LVR-PG) Input: Iterations K; batch size N=N0N=N_0; mini batch size B; algorithmic parameters: p∈[0,1]p∈[0,1], α∈[0,1]α∈[0,1], mixture coefficient ξ∈[0,1]ξ∈[0,1], IS operator ω, discount factor γ; initial parameters 0∈Θ θ_0∈ ; step size η; constraint set Θ . 1 for i=1,…,Ni=1,…,N do 2 τi←CollectTrajectory(π0,γ) _i ( _ θ_0,γ); 3 ∇^J†(0)←1N0∑i=1N0(τi∣0) ∇J ( θ_0)← 1N_0 _i=1^N_0 g( _i θ_0); 4 for k=0,…,K−1k=0,…,K-1 do 5 k+1←Θ(k+η∇^†J(k)) θ_k+1 _ ( θ_k+η ∇ _ θJ( θ_k) ); 6 Draw ck∼ℬ(p)c_k (p); 7 if ck=1c_k=1 then 8 for i=1,…,Ni=1,…,N do 9 τi←CollectTrajectory(πk+1,γ) _i ( _ θ_k+1,γ); 10 ∇^†J(k+1)←1N∑i=1N(τi∣k+1) ∇ _ θJ( θ_k+1)← 1N _i=1^N g( _i θ_k+1); 11 else 12 for i=1,…,Bi=1,…,B do 13 Draw mixture variable u∼ℬ(ξ)u (ξ); 14 if u=1u=1 then 15 τi←CollectTrajectory(πk+1,γ) _i ( _ θ_k+1,γ); 16 else 17 τi←CollectTrajectory(πk,γ) _i ( _ θ_k,γ); 18 ∇^†J(k+1)←1B∑i=1Bω(k+1,τi)(τi∣k+1)+(1−α)[∇^†J(k)−1B∑i=1Bω(k,τi)(τi∣k)] ∇ _ θJ( θ_k+1)← 1B _i=1^Bω( θ_k+1, _i) g( _i θ_k+1)+(1-α) [ ∇ _ θJ( θ_k)- 1B _i=1^Bω( θ_k, _i) g( _i θ_k) ]; 19 Return K θ_K Algorithm 3 CollectTrajectory(π,γ)CollectTrajectory(π,γ) Input: Policy π, discount factor γ∈(0,1)γ∈(0,1). 1 Initialize trajectory τ←∅τ← , time step h←0h← 0; 2 Sample initial state 0∼ρ0 s_0 _0; 3 while True do 4 Sample action ∼hπ(⋅∣h)_h π(· s_h); 5 Observe reward rh+1r_h+1 and next state h+1∼p(⋅∣h,h) s_h+1 p(· s_h,_h); 6 Append (h,h,rh+1)( s_h,_h,r_h+1) to τ; 7 Draw stopping condition z∼ℬ(1−γ)z (1-γ); 8 if z=1z=1 then Return τ∪h+1τ∪\ s_h+1\ ; 9 h←h+1h← h+1; Appendix A 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−γ1-γ. This guarantees that the trajectory length follows a geometric distribution with expectation (1−γ)−1(1-γ)^-1. Algorithm 2 outlines the generic LVR-PG template, which tracks and updates a recursive gradient estimator ∇^†J(k) ∇_ θ 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∼ℬ(p)c_k (p) that dictates the estimator’s update rule. When ck=1c_k=1, the historical variance is discarded, and the estimator undergoes a full-batch refresh using N trajectories. Conversely, when ck=0c_k=0, the algorithm computes a variance-reduced update using a smaller mini-batch of B trajectories, modulated by a momentum decay parameter α∈[0,1]α∈[0,1] and an importance sampling operator ω. By specifically choosing the hyperparameters (p,α,ξ)(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α=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=0p=0) and instead uses a momentum parameter α to incrementally discount past gradient errors Yuan et al. (2020). Crucially, the parameter ξ∈(0,1)ξ∈(0,1) activates the defensive importance sampling mechanism. As detailed in the recursive branch of Algorithm 2, drawing the Bernoulli mixture variable u∼ℬ(ξ)u (ξ) physically constructs the defensive trajectory distribution qξ(τ)=ξpk+1(τ)+(1−ξ)pk(τ)q_ξ(τ)=ξ p_ θ_k+1(τ)+(1-ξ)p_ θ_k(τ). Under this regime, the IS operator ω(,τ)ω( θ,τ) evaluates precisely to the density ratio p(τ)/qξ(τ)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ξ=0), throughout the theoretical analysis and empirical evaluations of this paper, we strictly consider the defensive setting (ξ∈(0,1)ξ∈(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λ 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. Table 2: Instantiations of the LVR-PG Framework Algorithm Refresh Prob. p Momentum α Defensive Parameter ξ PAGE-PG Gargiani et al. (2022) p∈(0,1)p∈(0,1) α=0α=0 ξ=0ξ=0 STORM-PG Yuan et al. (2020) p=0p=0 α∈(0,1)α∈(0,1) ξ=0ξ=0 DEF-PAGE-PG Paczolay et al. (2024) p∈(0,1)p∈(0,1) α=0α=0 ξ∈[0,1]ξ∈[0,1] DEF-STORM-PG Paczolay et al. (2024) p=0p=0 α∈(0,1)α∈(0,1) ξ∈[0,1]ξ∈[0,1] Appendix B 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 θ_k and a previous policy k−1 θ_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: τ[‖ω(k,τ)(τ∣k)−ω(k−1,τ)(τ∣k−1)‖22]≤C†,ω‖k−k−1‖22, _τ [ \|ω( θ_k,τ) g(τ θ_k)-ω( θ_k-1,τ) g(τ θ_k-1) \|_2^2 ]≤ C_ ,ω\| θ_k- θ_k-1\|_2^2, (3) where C†,ω>0C_ ,ω>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ξ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ξ(τ)=ξpk(τ)+(1−ξ)pk−1(τ)q_ξ(τ)=ξ p_ θ_k(τ)+(1-ξ)p_ θ_k-1(τ) with parameter ξ∈(0,1)ξ∈(0,1), the unified mean-squared smoothness constant CDEF,ωC_ DEF,ω is strictly bounded. Letting mξ≔minξ,1−ξm_ξ \ξ,1-ξ\ and Mr≔[Hγr]M_r [H_γ^r] denote the moments of the geometrically distributed trajectory length, under Assumption 3.1 and bounded rewards, it holds that: τ∼qξ[‖ω(k,τ)(τ∣k)−ω(k−1,τ)(τ∣k−1)‖22]≤C†,ω‖k−k−1‖22, _τ q_ξ [ \|ω( θ_k,τ) g(τ θ_k)-ω( θ_k-1,τ) g(τ θ_k-1) \|_2^2 ]≤ C_ ,ω\| θ_k- θ_k-1\|_2^2, where the unified mean-squared smoothness constant is: C†,ω=Rmax2mξ(C14M5+2LS2M4). C_ ,ω= R_ ^2m_ξ (C_1^4M_5+2L_S^2M_4 ). Setting ξ=1/2ξ=1/2 minimizes the variance bound, yielding m1/2=1/2m_1/2=1/2 and the optimized mean-squared smoothness constant for both algorithms: C†,ω=2Rmax2(C14M5+2LS2M4)=((1−γ)−5). C_ ,ω=2R_ ^2 (C_1^4M_5+2L_S^2M_4 )=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 L2L_2 norm of the difference between the defensive gradient estimators evaluated at consecutive iterates k θ_k and k−1 θ_k-1. For brevity, we drop the trajectory dependency and denote pk=pk(τ)p_ θ_k=p_ θ_k(τ), k=(τ∣k) g_k= g(τ θ_k), and ωk=pkqξ _ θ_k= p_ θ_kq_ξ. We decouple the gradient difference algebraically by adding and subtracting ωk−1k _ θ_k-1 g_k: ωkk−ωk−1k−1=(ωk−ωk−1)k+ωk−1(k−k−1). _ θ_k g_k- _ θ_k-1 g_k-1=( _ θ_k- _ θ_k-1) g_k+ _ θ_k-1( g_k- g_k-1). Applying the inequality ‖x+y‖22≤2‖x‖22+2‖y‖22\|x+y\|_2^2≤ 2\|x\|_2^2+2\|y\|_2^2, we can bound the expectation by isolating the importance weights from the on-policy gradients: τ∼qξ[‖ωkk−ωk−1k−1‖22]≤2τ∼qξ[‖(ωk−ωk−1)k‖22]+2τ∼qξ[‖ωk−1(k−k−1)‖22]. _τ q_ξ [ \| _ θ_k g_k- _ θ_k-1 g_k-1 \|_2^2 ]≤ 2E_τ q_ξ [ \|( _ θ_k- _ θ_k-1) g_k \|_2^2 ]+2E_τ q_ξ [ \| _ θ_k-1( g_k- g_k-1) \|_2^2 ]. We evaluate the two terms independently. For the first term, we substitute ωk−ωk−1=pk−pk−1qξ _ θ_k- _ θ_k-1= p_ θ_k-p_ θ_k-1q_ξ and use the definition of the defensive mixture qξ(τ)≥mξ(pk(τ)+pk−1(τ))q_ξ(τ)≥ m_ξ(p_ θ_k(τ)+p_ θ_k-1(τ)) to bound the density ratio: (pk−pk−1)2qξ≤1mξ(pk−pk−1)2pk+pk−1=1mξ(pk−pk−1)2(pk+pk−1)2pk+pk−1≤2mξ(pk−pk−1)2. (p_ θ_k-p_ θ_k-1)^2q_ξ≤ 1m_ξ (p_ θ_k-p_ θ_k-1)^2p_ θ_k+p_ θ_k-1= 1m_ξ( p_ θ_k- p_ θ_k-1)^2 ( p_ θ_k+ p_ θ_k-1)^2p_ θ_k+p_ θ_k-1≤ 2m_ξ( p_ θ_k- p_ θ_k-1)^2. By bounded rewards and Assumption 3.1, the pathwise GPOMDP gradient is bounded by ‖k‖2≤RmaxC1Hγ2\| g_k\|_2≤ R_ C_1H_γ^2. Expanding the expectation of the first term yields: τ∼qξ[‖(ωk−ωk−1)k‖22] _τ q_ξ [ \|( _ θ_k- _ θ_k-1) g_k \|_2^2 ] =∫(pk−pk−1)2qξ‖k‖22τ = (p_ θ_k-p_ θ_k-1)^2q_ξ\| g_k\|_2^2dτ ≤2Rmax2C12mξ∫Hγ4(pk−pk−1)2τ. ≤ 2R_ ^2C_1^2m_ξ H_γ^4( p_ θ_k- p_ θ_k-1)^2dτ. Applying Lemma D.3 with r=4r=4 we obtain: τ∼qξ[‖(ωk−ωk−1)k‖22]≤Rmax2C14M52mξ‖k−k−1‖22. _τ q_ξ [ \|( _ θ_k- _ θ_k-1) g_k \|_2^2 ]≤ R_ ^2C_1^4M_52m_ξ\| θ_k- θ_k-1\|_2^2. For the second term, we use the property qξ≥(1−ξ)pk−1≥mξpk−1q_ξ≥(1-ξ)p_ θ_k-1≥ m_ξp_ θ_k-1 to convert the expectation under the defensive mixture back to the behavior policy distribution: τ∼qξ[‖ωk−1(k−k−1)‖22] _τ q_ξ [\| _ θ_k-1( g_k- g_k-1)\|_2^2 ] =∫pk−12qξ‖k−k−1‖22τ = p_ θ_k-1^2q_ξ\| g_k- g_k-1\|_2^2dτ ≤1mξτ∼pk−1[‖k−k−1‖22]. ≤ 1m_ξE_τ p_ θ_k-1 [\| g_k- g_k-1\|_2^2 ]. 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: τ∼pk−1[‖k−k−1‖22]≤Rmax2LS2M4‖k−k−1‖22. _τ p_ θ_k-1 [\| g_k- g_k-1\|_2^2 ]≤ R_ ^2L_S^2M_4\| θ_k- θ_k-1\|_2^2. Substituting this back bounds the second term by: τ∼qξ[‖ωk−1(k−k−1)‖22]≤Rmax2LS2M4mξ‖k−k−1‖22. _τ q_ξ [\| _ θ_k-1( g_k- g_k-1)\|_2^2 ]≤ R_ ^2L_S^2M_4m_ξ\| θ_k- θ_k-1\|_2^2. Finally, summing the two bounds with their respective factor of 2 recovers the exact unified estimation constant: τ∼qξ[‖ωkk−ωk−1k−1‖22] _τ q_ξ [ \| _ θ_k g_k- _ θ_k-1 g_k-1 \|_2^2 ] ≤2(Rmax2C14M52mξ)‖k−k−1‖22+2(Rmax2LS2M4mξ)‖k−k−1‖22 ≤ 2 ( R_ ^2C_1^4M_52m_ξ )\| θ_k- θ_k-1\|_2^2+2 ( R_ ^2L_S^2M_4m_ξ )\| θ_k- θ_k-1\|_2^2 =Rmax2mξ(C14M5+2LS2M4)‖k−k−1‖22. = R_ ^2m_ξ (C_1^4M_5+2L_S^2M_4 )\| θ_k- θ_k-1\|_2^2. ∎ DEF-PAGE-PG, DEF-STORM-PG (CDEF,ωC_ DEF,ω). 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ξ(τ)=ξpk(τ)+(1−ξ)pk−1(τ)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: ∇^†J(k+1) ∇ _ θJ( θ_k+1) =(1−α)1B∑i=1Bω(k+1,τi)(τi∣k+1)+α1B∑i=1Bω(k+1,τi)(τi∣k+1) =(1-α) 1B _i=1^Bω( θ_k+1, _i) g( _i θ_k+1)+α 1B _i=1^Bω( θ_k+1, _i) g( _i θ_k+1) +(1−α)[∇^†J(k)−1B∑i=1Bω(k,τi)(τi∣k)]. +(1-α) [ ∇ _ θJ( θ_k)- 1B _i=1^Bω( θ_k, _i) g( _i θ_k) ]. Substituting this back into the update rule allows us to group the gradient difference directly: ∇^†J(k+1) ∇ _ θJ( θ_k+1) =(1−α)∇^†J(k)+(1−α)[1B∑i=1B(ω(k+1,τi)(τi∣k+1)−ω(k,τi)(τi∣k))] =(1-α) ∇ _ θJ( θ_k)+(1-α) [ 1B _i=1^B (ω( θ_k+1, _i) g( _i θ_k+1)-ω( θ_k, _i) g( _i θ_k) ) ] +α1B∑i=1Bω(k+1,τi)(τi∣k+1). +α 1B _i=1^Bω( θ_k+1, _i) g( _i θ_k+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. Appendix C On Fisher-non-Degeneracy Assumption C.1 (Fisher-non-degeneracy). There exists some constant μF>0 _F>0, such that for every ∈ℝd θ ^d, the FIM F(θ)F(θ) induced by the policy π _ θ satisfies: F()=(,)∼νπ[∇logπ(∣)∇logπ(∣)⊤]⪰μF⋅. F( θ)=E_( s,) ν _ θ [ _ θ _ θ( s) _ θ _ θ( s) ] _F· I. (4) Assumption C.1 requires the FIM to be uniformly lower-bounded by a strictly positive constant μF>0 _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 Kullback-Leibler (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. Gaussian Policies. In continuous action spaces, consider a Gaussian policy with a linearly parameterized mean and a fixed covariance matrix, π(a∣s)=(ϕ()⊤,Σ) _ θ(a s)=N(φ( s) θ, ). The FIM is proportional to the uncentered covariance of the state features: F()=νπ[ϕ(s)Σ−1ϕ(s)⊤]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)φ(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 _ θ(a s)→ 0 for suboptimal actions), the corresponding entries in the FIM vanish, driving the minimum eigenvalue μF _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 _bias>0, such that for every ∈ℝd θ ^d, the transferred compatible function approximation error satisfies νπ[(Aπ(,)−(1−γ)∗⊤∇logπ(∣))2]≤ϵbias, E_ν _ θ [ (A _ θ( s,)-(1-γ) u^* _ θ _ θ( s) )^2 ]≤ _bias, (5) where νπν _ θ is the state-action distribution induced by a policy π _ θ and ∗≔F()−1∇J() u^* F( θ)^-1 _ θJ( θ) is the solution of min∈ℝdνπ[(Aπ(,)−(1−γ)⊤∇logπ(∣))2]. _ w ^d E_ν _ θ [ (A _ θ( s,)-(1-γ) w _ θ _ θ( s) )^2 ]. Assumption C.2 bounds the error incurred when approximating the advantage function Aπ(s,a)A _ θ(s,a) using the score function ∇logπ(∣) _ θ _ θ( s) as a linear feature representation. The vector ∗≔F()−1∇J() 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 _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 state-action 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 Θ=ℝdΘ =R^d_ . Assume additionally that sup∈Θ‖νπ∗/νπ‖∞<∞ _ θ∈ \|ν _ θ^*/ν^π_ θ \|_∞<∞, where the ratio denotes the Radon–Nikodym derivative. Then, we have: J(∗)−J()≤ϵbias1−γ‖νπ∗νπ‖∞+C1μF‖∇J()‖2. J( θ^*)-J( θ)≤ _bias1-γ \| ν _ θ^*ν^π_ θ \|_∞+ C_1 _F\| _ θJ( θ)\|_2. 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 and perform a change of distribution: J(∗)−J() J( θ^*)-J( θ) =11−γ(,)∼νπ∗[Aπ(,)] = 11-γE_( s,) ν^π^* [A _ θ( s,) ] =11−γ(,)∼νπ[Aπ(,)νπ∗(,)νπ(,)]. = 11-γE_( s,) ν _ θ [A _ θ( s,) ν _ θ^*( s,)ν _ θ( s,) ]. By introducing the optimal compatible weights u∗:=F()−1∇J()u^*:=F( θ)^-1 _ θJ( θ) and adding and subtracting (1−γ)u∗⊤∇logπ(∣)(1-γ)u^* _ θ _ θ( s), we obtain: J(∗)−J() J( θ^*)-J( θ) =11−γ(,)∼νπ[(Aπ(,)−(1−γ)u∗⊤∇logπ(∣))νπ∗(,)νπ(,)] = 11-γE_( s,) ν _ θ [ (A _ θ( s,)-(1-γ)u^* _ θ _ θ( s) ) ν _ θ^*( s,)ν _ θ( s,) ] +(,)∼νπ∗[u∗⊤∇logπ(∣)]. +E_( s,) ν _ θ^* [u^* _ θ _ θ( s) ]. To bound the right-hand side, we evaluate the two terms independently. Applying Hölder’s inequality to the first term, followed by the Cauchy–Schwarz inequality, gives: |(,)∼νπ[(Aπ(,)−(1−γ)u∗⊤∇logπ(∣))νπ∗(,)νπ(,)]| |E_( s,) ν _ θ [ (A _ θ( s,)-(1-γ)u^* _ θ _ θ( s) ) ν _ θ^*( s,)ν _ θ( s,) ] | ≤‖νπ∗νπ‖∞(,)∼νπ[|Aπ(,)−(1−γ)u∗⊤∇logπ(∣)|] ≤ \| ν _ θ^*ν _ θ \|_∞E_( s,) ν _ θ [ |A _ θ( s,)-(1-γ)u^* _ θ _ θ( s) | ] ≤‖νπ∗νπ‖∞(,)∼νπ[(Aπ(,)−(1−γ)u∗⊤∇logπ(∣))2] ≤ \| ν _ θ^*ν _ θ \|_∞ E_( s,) ν _ θ [ (A _ θ( s,)-(1-γ)u^* _ θ _ θ( s) )^2 ] ≤ϵbias‖νπ∗νπ‖∞, ≤ _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: (,)∼νπ∗[u∗⊤∇logπ(∣)] _( s,) ν _ θ^* [u^* _ θ _ θ( s) ] ≤∥u∗∥2(,)∼νπ∗[∥∇logπ(∣)∥2] ≤\|u^*\|_2E_( s,) ν _ θ^* [\| _ θ _ θ( s)\|_2 ] ≤C1‖u∗‖2 ≤ C_1\|u^*\|_2 =C1‖F()−1∇J()‖2 =C_1\|F( θ)^-1 _ θJ( θ)\|_2 ≤C1μF‖∇J()‖2. ≤ C_1 _F\| _ θJ( θ)\|_2. Combining the two bounds yields: J(∗)−J()≤ϵbias1−γ‖νπ∗νπ‖∞+C1μF‖∇J()‖2. J( θ^*)-J( θ)≤ _bias1-γ \| ν _ θ^*ν _ θ \|_∞+ C_1 _F\| _ θJ( θ)\|_2. ∎ 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 _bias under the data-generating 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 κ=‖νπ∗νπ‖∞κ= \| ν^π^*ν _ θ \|_∞. Appendix D 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: ar(g(τ∣))≤4Rmax2C12(1−γ)3≕ν2. (g(τ θ) )≤ 4R_ ^2C_1^2(1-γ)^3 ν^2. Proof. Let the gradient estimator for a single trajectory τ of length HγH_γ be defined as g(τ∣)=∑t=0Hγ−1rt+1∑h=0t∇logπ(h∣h)g(τ θ)= _t=0^H_γ-1r_t+1 _h=0^t _ θ _ θ(_h s_h). The variance is upper-bounded by the uncentered second moment: ar(g(τ∣))≤τ[‖g(τ∣)‖22]Var (g(τ θ) ) _τ [\|g(τ θ)\|_2^2 ]. First, we condition on a HγH_γ. Using the Cauchy-Schwarz inequality, we decouple the rewards from the score functions: ‖g(τ∣)‖22 \|g(τ θ)\|_2^2 =‖∑t=0H−1rt+1∑h=0t∇logπ(h∣h)‖22 = \| _t=0^H-1r_t+1 _h=0^t _ θ _ θ(_h s_h) \|_2^2 ≤(∑t=0H−1rt+12)(∑t=0H−1‖∑h=0t∇logπ(h∣h)‖22). ≤ ( _t=0^H-1r_t+1^2 ) ( _t=0^H-1 \| _h=0^t _ θ _ θ(_h s_h) \|_2^2 ). (6) Because the rewards are uniformly bounded, the first term is bounded by HRmax2HR_ ^2. 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: τ[‖∑h=0t∇logπ(h∣h)‖22∣Hγ] _τ [ \| _h=0^t _ θ _ θ(_h s_h) \|_2^2 H_γ ] =∑h=0tτ[∥∇logπ(h∣h)∥22∣Hγ] = _h=0^tE_τ [ \| _ θ _ θ(_h s_h) \|_2^2 H_γ ] ≤(t+1)C12, ≤(t+1)C_1^2, (7) where the inequality follows directly from Assumption 3.1(i). Substituting Equation (7) back into Equation (6) yields: τ[‖g(τ∣)‖22∣Hγ]≤HγRmax2∑t=0Hγ−1(t+1)C12=Rmax2C12Hγ2(Hγ+1)2. _τ [\|g(τ θ)\|_2^2 H_γ ]≤ H_γR_ ^2 _t=0^H_γ-1(t+1)C_1^2=R_ ^2C_1^2 H_γ^2(H_γ+1)2. (8) Finally, we take the expectation over the geometric stopping time HγH_γ, which follows a geometric distribution with success probability p=1−γp=1-γ. Using the standard bounds for the moments of a geometric distribution, we have [Hγ3]≤6/p3E[H_γ^3]≤ 6/p^3 and [Hγ2]≤2/p2E[H_γ^2]≤ 2/p^2. Thus: Hγ[Rmax2C12Hγ3+Hγ22] _H_γ [R_ ^2C_1^2 H_γ^3+H_γ^22 ] ≤Rmax2C122(6(1−γ)3+2(1−γ)2) ≤ R_ ^2C_1^22 ( 6(1-γ)^3+ 2(1-γ)^2 ) ≤4Rmax2C12(1−γ)3, ≤ 4R_ ^2C_1^2(1-γ)^3, where the final inequality assumes γ is sufficiently close to 11, yielding the standard ((1−γ)−3)O((1-γ)^-3) variance bound for the GPOMDP estimator. ∎ Lemma D.2 (Smoothness of the expected return). Let |R(,)|≤Rmax|R( s,)|≤ R_ for all ∈,∈ s , and Θ convex. Under Assumption 3.1, we have: Then, for all ,′∈Θ θ, θ ∈ , ‖∇J()−∇J(′)‖≤Rmax(LS+C12)(1−γ)2‖−′‖.\|∇ J( θ)-∇ J( θ )\|≤ R_ (L_S+C_1^2)(1-γ)^2\| θ- θ \|. Proof. For u∈[0,1]u∈[0,1], let u=u+(1−u)′ θ_u=u θ+(1-u) θ , which belongs to Θ by convexity. For h≥0h≥ 0, let h(u)=∑ℓ=0h∇logπu(ℓ∣ℓ) Z_h(u)= _ =0^h∇ _ θ_u(_ s_ ). Let τ0:h _0:h denote the trajectory prefix up to timestep h included, and php_ θ^h its law under policy π _ θ. Let: h(u)=τ0:h∼puh[rh+1h(u)], G_h(u)=E_ _0:h p_ θ_u^h [r_h+1 Z_h(u) ], so that ∇J(u)=∑h=0∞γhh(u)∇ J( θ_u)= _h=0^∞γ^h G_h(u). Let ϵ>0ε>0 be such that u+ϵ∈[0,1]u+ε∈[0,1]. By adding and subtracting τ0:h∼pu+ϵh[rh+1h(u)]E_ _0:h p_ θ_u+ε^h[r_h+1 Z_h(u)]: h(u+ϵ)−h(u)=τ0:h∼pu+ϵh[rh+1(h(u+ϵ)−h(u))]⏟(A)+∫(pu+ϵh(τ0:h)−puh(τ0:h))rh+1h(u)dτ0:h⏟(B). G_h(u+ε)- G_h(u)= E_ _0:h p_ θ_u+ε^h [r_h+1( Z_h(u+ε)- Z_h(u)) ]_(A)+ (p_ θ_u+ε^h( _0:h)-p_ θ_u^h( _0:h) )r_h+1 Z_h(u)d _0:h_(B). (9) We bound the first term using Jensen’s inequality and the second assumption on the policy scores: ‖(A)‖ \|(A)\| ≤Rmax∑ℓ=0hτ0:ℓ∼pu+ϵℓ[‖∇logπu+ϵ(ℓ∣ℓ)−∇logπu(ℓ∣ℓ)‖] ≤ R_ _ =0^hE_ _0: p_ θ_u+ε [ \|∇ _ θ_u+ε(_ s_ )-∇ _ θ_u(_ s_ ) \| ] =Rmax∑ℓ=0hτ0:ℓ∼pu+ϵℓ[∼πu+ϵ(⋅|ℓ)[‖∇logπu+ϵ(ℓ∣ℓ)−∇logπu(ℓ∣ℓ)‖]] =R_ _ =0^hE_ _0: p_ θ_u+ε [E_ _ θ_u+ε(·| s_ ) [ \|∇ _ θ_u+ε(_ s_ )-∇ _ θ_u(_ s_ ) \| ] ] ≤Rmax(h+1)LSϵ‖−′‖, ≤ R_ (h+1)L_Sε\| θ- θ \|, so lim supϵ↓0‖(A)‖ϵ≤Rmax(h+1)LS‖−′‖ _ε 0 \|(A)\|ε≤ R_ (h+1)L_S\| θ- θ \|. As for the second term, note that, for ℓ<k≤h <k≤ h, τ0:k∼puk[∇logπu(ℓ∣ℓ)⊤∇logπu(k∣k)] _ _0:k p_ θ_u^k [∇ _ θ_u(_ s_ ) ∇ _ θ_u(_k s_k) ] =τ0:k∼puk[∇logπu(ℓ∣ℓ)⊤∼πu(⋅∣k)[∇logπu(∣k)]]=0, =E_ _0:k p_ θ_u^k [∇ _ θ_u(_ s_ ) E_ _ θ_u(· s_k) [∇ _ θ_u( s_k) ] ]=0, so, by the first assumption on the policy scores: τ0:h∼puh[∥h(u)∥2]=∑ℓ=0hτ0:ℓ∼puℓ[∥∇logπu(ℓ∣ℓ)∥2]≤(h+1)C12.E_ _0:h p_ θ_u^h[\| Z_h(u)\|^2]= _ =0^hE_ _0: p_ θ_u [\|∇ _ θ_u(_ s_ )\|^2]≤(h+1)C_1^2. Then: limϵ↓0(B)ϵ _ε 0 (B)ε =∫limϵ↓0pu+ϵh(τ0:h)−puh(τ0:h)ϵrh+1h(u)dτ0:h = _ε 0 p_ θ_u+ε^h( _0:h)-p_ θ_u^h( _0:h)εr_h+1 Z_h(u)d _0:h =∫∇puh(τ0:h)⊤(−′)rh+1h(u)dτ0:h = ∇ p_ θ_u^h( _0:h) ( θ- θ )r_h+1 Z_h(u)d _0:h =τ0:h∼puh[h(u)h(u)⊤(−′)rh+1], =E_ _0:h p_ θ_u^h [ Z_h(u) Z_h(u) ( θ- θ )r_h+1 ], and ‖limϵ↓0(B)ϵ‖ \| _ε 0 (B)ε \| ≤Rmaxτ0:h∼puh[‖h(u)‖2]∥−′∥ ≤ R_ E_ _0:h p_ θ_u^h [ \| Z_h(u) \|^2 ]\| θ- θ \| ≤Rmax(h+1)C12‖−′‖. ≤ R_ (h+1)C_1^2\| θ- θ \|. Now, from Equation (9): lim supϵ↓0‖h(u+ϵ)−h(u)‖ϵ _ε 0 \| G_h(u+ε)- G_h(u) \|ε ≤lim supϵ↓0‖(A)‖ϵ+lim supϵ↓0‖(B)‖ϵ ≤ _ε 0 \|(A)\|ε+ _ε 0 \|(B)\|ε =lim supϵ↓0‖(A)‖ϵ+‖limϵ↓0(B)ϵ‖ = _ε 0 \|(A)\|ε+ \| _ε 0 (B)ε \| ≤Rmax(h+1)(LS+C12)‖−′‖. ≤ R_ (h+1)(L_S+C_1^2)\| θ- θ \|. The same decomposition shows that h G_h is continuous on [0,1][0,1]. By Lemma H.1: ‖h(1)−h(0)‖≤Rmax(h+1)(LS+C12)‖−′‖.\| G_h(1)- G_h(0)\|≤ R_ (h+1)(L_S+C_1^2)\| θ- θ \|. Finally: ‖∇J(′)−∇J()‖ \|∇ J( θ )-∇ J( θ)\| ≤∑h=0∞γh‖h(1)−h(0)‖ ≤ _h=0^∞γ^h\| G_h(1)- G_h(0)\| ≤Rmax(LS+C12)‖−′‖∑h=0∞γh(h+1) ≤ R_ (L_S+C_1^2)\| θ- θ \| _h=0^∞γ^h(h+1) =Rmax(LS+C12)(1−γ)2‖−′‖. = R_ (L_S+C_1^2)(1-γ)^2\| θ- θ \|. ∎ Lemma D.3 (Weighted Hellinger continuity). Suppose that Assumption 3.1(1) holds. For every integer r≥0r≥ 0 and every 1,2∈Θ θ_1, θ_2∈ , ∫Hγ(τ)r(p(τ∣1)−p(τ∣2))2τ≤C12Mr+14‖1−2‖2. _TH_γ(τ)^r ( p(τ θ_1)- p(τ θ_2) )^2dτ≤ C_1^2M_r+14 \| θ_1- θ_2 \|^2. Proof. We recall a result by Paczolay et al. (2024), proved here for completeness Let t=(1−t)2+t1,=1−2,t∈[0,1]. θ_t=(1-t) θ_2+t θ_1, = θ_1- θ_2, t∈[0,1]. Convexity of Θ guarantees that t∈Θ θ_t∈ . Because the stopping rule and the environment are independent of the policy parameters, ∇logp(τ∣t)=∑h=0Hγ(τ)−1∇logπt(a∣h).∇ p(τ θ_t)= _h=0^H_γ(τ)-1∇ _ θ_t(_a s_h). Consequently, dtp(τ∣t)=12p(τ∣t)⟨,∇logp(τ∣t)⟩. ddt p(τ θ_t)= 12 p(τ θ_t) ,∇ p(τ θ_t) . By the fundamental theorem of calculus and Cauchy–Schwarz, (p(τ∣1)−p(τ∣2))2 ( p(τ θ_1)- p(τ θ_2) )^2 ≤‖24∫01p(τ∣t)‖∇logp(τ∣t)‖2t. ≤ \| \|^24 _0^1p(τ θ_t) \|∇ p(τ θ_t) \|^2dt. Multiplying by Hγ(τ)rH_γ(τ)^r and integrating over τ yields ∫Hγ(τ)r(p(τ∣1)−p(τ∣2))2τ _TH_γ(τ)^r ( p(τ θ_1)- p(τ θ_2) )^2dτ ≤‖24∫01τ∼p(⋅∣t)[Hγr‖∑h=0Hγ−1∇logπt(a∣h)‖2]dt. ≤ \| \|^24 _0^1E_τ p(· θ_t) [H_γ^r \| _h=0^H_γ-1∇ _ θ_t(_a s_h) \|^2 ]dt. The score increments are martingale differences. Conditionally on HγH_γ, Assumption 3.1(i) therefore gives τ∼p(⋅∣t)[‖∑h=0Hγ−1∇logπt(a∣h)‖2|Hγ]≤C12Hγ.E_τ p(· θ_t) [ \| _h=0^H_γ-1∇ _ θ_t(_a s_h) \|^2\, |\,H_γ ]≤ C_1^2H_γ. Since the distribution of HγH_γ is independent of t θ_t, [Hγr‖∇logp(τ∣t)‖2]≤C12Mr+1.E [H_γ^r \|∇ p(τ θ_t) \|^2 ]≤ C_1^2M_r+1. Substitution proves the claim. ∎ Lemma D.4 (Estimation Error for LVR-PG). Under Assumption 3.1, let Δk:=[‖∇^†J(k)−∇J(k)‖22] _k:=E[\| ∇ _ θJ( θ_k)- _ θJ( θ_k)\|_2^2] be the estimation error of the LVR-PG estimator. Letting λ≔1−(1−p)(1−α)2λ 1-(1-p)(1-α)^2 and letting C†,ω>0C_ ,ω>0 denote the bound on the variance of the (defensive) importance weights, the following recurrence holds for all k∈⟦K⟧k∈ K : Δk+1≤(1−λ)Δk+2(1−λ)C†,ωB[‖k+1−k‖22]+Cν, _k+1≤(1-λ) _k+ 2(1-λ)C_ ,ωBE[\| θ_k+1- θ_k\|_2^2]+C_ν, where Cν≔(pN+4α2(1−p)B)ν2C_ν ( pN+ 4α^2(1-p)B )ν^2. Proof. We analyze the estimation error conditioned on the Bernoulli random variable ck∼ℬ(p)c_k (p). By the law of total expectation, the expected estimation error Δk+1 _k+1 decomposes as follows: Δk+1 _k+1 =p⋅[‖∇^†J(k+1)−∇J(k+1)‖22∣ck=1] =p·E [\| ∇ _ θJ( θ_k+1)- _ θJ( θ_k+1)\|_2^2 c_k=1 ] +(1−p)⋅[∥∇^†J(k+1)−∇J(k+1)∥22∣ck=0]. +(1-p)·E [\| ∇ _ θJ( θ_k+1)- _ θJ( θ_k+1)\|_2^2 c_k=0 ]. When ck=1c_k=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: [‖∇^†J(k+1)−∇J(k+1)‖22∣ck=1]≤ν2N. [\| ∇ _ θJ( θ_k+1)- _ θJ( θ_k+1)\|_2^2 c_k=1 ]≤ ν^2N. When ck=0c_k=0, the estimator applies the momentum update. Following the proof of Lemma 8 of Yuan et al. (2020), we condition on the history ℱkF_k available after computing k+1 θ_k+1 and before drawing ckc_k and the fresh trajectories. Under this conditioning, k θ_k, k+1 θ_k+1, and ∇^†J(k) ∇ _ θJ( θ_k) are fixed, while the fresh trajectories τii=1B\ _i\_i=1^B are independent samples from ξpk+1+(1−ξ)pkξ p_ θ_k+1+(1-ξ)p_ θ_k. Substituting the momentum update and adding and subtracting the corresponding gradients gives: ∇^†J(k+1)−∇J(k+1) ∇ _ θJ( θ_k+1)- _ θJ( θ_k+1) =(1−α)(∇^†J(k)−∇J(k)) =(1-α)( ∇ _ θJ( θ_k)- _ θJ( θ_k)) +(1−α)[1B∑i=1B(ωξ(k+1,τi)(τi∣k+1)−ωξ(k,τi)(τi∣k))−∇J(k+1)+∇J(k)] +(1-α) [ 1B _i=1^B ( _ξ( θ_k+1, _i) g( _i θ_k+1)- _ξ( θ_k, _i) g( _i θ_k) )- _ θJ( θ_k+1)+ _ θJ( θ_k) ] +α[1B∑i=1Bωξ(k+1,τi)(τi∣k+1)−∇J(k+1)]. +α [ 1B _i=1^B _ξ( θ_k+1, _i) g( _i θ_k+1)- _ θJ( θ_k+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\|u+v\|_2^2≤ 2\|u\|_2^2+2\|v\|_2^2 to these two fresh error terms, and using independence across trajectories, yields [∥∇^†J(k+1)−∇J(k+1)∥22∣ℱk,ck=0] [\| ∇ _ θJ( θ_k+1)- _ θJ( θ_k+1)\|_2^2 _k,c_k=0 ] ≤(1−α)2‖∇^†J(k)−∇J(k)‖22 ≤(1-α)^2\| ∇ _ θJ( θ_k)- _ θJ( θ_k)\|_2^2 +2(1−α)2Bτ∼ξpk+1+(1−ξ)pk[‖ωξ(k+1,τ)(τ∣k+1)−ωξ(k,τ)(τ∣k)−∇J(k+1)+∇J(k)‖22] + 2(1-α)^2BE_τ ξ p_ θ_k+1+(1-ξ)p_ θ_k [ \| _ξ( θ_k+1,τ) g(τ θ_k+1)- _ξ( θ_k,τ) g(τ θ_k)- _ θJ( θ_k+1)+ _ θJ( θ_k) \|_2^2 ] +2α2Bτ∼ξpk+1+(1−ξ)pk[‖ωξ(k+1,τ)(τ∣k+1)−∇J(k+1)‖22]. + 2α^2BE_τ ξ p_ θ_k+1+(1-ξ)p_ θ_k [ \| _ξ( θ_k+1,τ) g(τ θ_k+1)- _ θJ( θ_k+1) \|_2^2 ]. The factors 1/B1/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 τ∼ξpk+1+(1−ξ)pk[‖ωξ(k+1,τ)(τ∣k+1)−ωξ(k,τ)(τ∣k)−∇J(k+1)+∇J(k)‖22] _τ ξ p_ θ_k+1+(1-ξ)p_ θ_k [ \| _ξ( θ_k+1,τ) g(τ θ_k+1)- _ξ( θ_k,τ) g(τ θ_k)- _ θJ( θ_k+1)+ _ θJ( θ_k) \|_2^2 ] ≤τ∼ξpk+1+(1−ξ)pk[‖ωξ(k+1,τ)(τ∣k+1)−ωξ(k,τ)(τ∣k)‖22] _τ ξ p_ θ_k+1+(1-ξ)p_ θ_k [ \| _ξ( θ_k+1,τ) g(τ θ_k+1)- _ξ( θ_k,τ) g(τ θ_k) \|_2^2 ] ≤C†,ω‖k+1−k‖22. ≤ C_ ,ω\| θ_k+1- θ_k\|_2^2. Here, the first inequality uses the fact that the expectation of the weighted gradient difference is ∇J(k+1)−∇J(k) _ θJ( θ_k+1)- _ θJ( θ_k). The second inequality is the mean-squared error bound provided by Lemma B.1. For the current-gradient error, we similarly obtain: τ∼ξpk+1+(1−ξ)pk[‖ωξ(k+1,τ)(τ∣k+1)−∇J(k+1)‖22] _τ ξ p_ θ_k+1+(1-ξ)p_ θ_k [ \| _ξ( θ_k+1,τ) g(τ θ_k+1)- _ θJ( θ_k+1) \|_2^2 ] ≤τ∼ξpk+1+(1−ξ)pk[‖ωξ(k+1,τ)(τ∣k+1)‖22] _τ ξ p_ θ_k+1+(1-ξ)p_ θ_k [ \| _ξ( θ_k+1,τ) g(τ θ_k+1) \|_2^2 ] =τ∼pk+1[ωξ(k+1,τ)‖(τ∣k+1)‖22] =E_τ p_ θ_k+1 [ _ξ( θ_k+1,τ)\| g(τ θ_k+1)\|_2^2 ] ≤1ξτ∼pk+1[‖(τ∣k+1)‖22]≤ν2ξ. ≤ 1ξE_τ p_ θ_k+1 [\| g(τ θ_k+1)\|_2^2 ]≤ ν^2ξ. The equality follows by canceling one importance weight against the mixture distribution. The final inequalities use ωξ(k+1,τ)≤1/ξ _ξ( θ_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: [∥∇^†J(k+1)−∇J(k+1)∥22∣ℱk,ck=0] [\| ∇ _ θJ( θ_k+1)- _ θJ( θ_k+1)\|_2^2 _k,c_k=0 ] ≤(1−α)2‖∇^†J(k)−∇J(k)‖22+2(1−α)2C†,ωB‖k+1−k‖22+2α2ν2ξB. ≤(1-α)^2\| ∇ _ θJ( θ_k)- _ θJ( θ_k)\|_2^2+ 2(1-α)^2C_ ,ωB\| θ_k+1- θ_k\|_2^2+ 2α^2ν^2ξ B. Taking expectation over the preceding history, and using the independence of ckc_k from that history, yields, [‖∇^†J(k+1)−∇J(k+1)‖22∣ck=0] [\| ∇ _ θJ( θ_k+1)- _ θJ( θ_k+1)\|_2^2 c_k=0 ] ≤(1−α)2Δk+2(1−α)2C†,ωB[‖k+1−k‖22]+2α2ν2ξB. ≤(1-α)^2 _k+ 2(1-α)^2C_ ,ωBE [\| θ_k+1- θ_k\|_2^2 ]+ 2α^2ν^2ξ B. Summing the two branches, we obtain, Δk+1 _k+1 ≤p(ν2N)+(1−p)[(1−α)2Δk+2(1−α)2C†,ωB[‖k+1−k‖22]+2α2ν2ξB] ≤ p ( ν^2N )+(1-p) [(1-α)^2 _k+ 2(1-α)^2C_ ,ωBE [\| θ_k+1- θ_k\|_2^2 ]+ 2α^2ν^2ξ B ] =(1−p)(1−α)2Δk+2(1−p)(1−α)2C†,ωB[‖k+1−k‖22]+pν2N+2α2(1−p)ν2ξB. =(1-p)(1-α)^2 _k+ 2(1-p)(1-α)^2C_ ,ωBE [\| θ_k+1- θ_k\|_2^2 ]+ pν^2N+ 2α^2(1-p)ν^2ξ B. Recognizing that (1−p)(1−α)2=1−λ(1-p)(1-α)^2=1-λ, and plugging our choice of ξ=1/2ξ=1/2 from Lemma B.1, this yields the recurrence: Δk+1≤(1−λ)Δk+2(1−λ)C†,ωB[‖k+1−k‖22]+(pN+4α2(1−p)B)ν2. _k+1≤(1-λ) _k+ 2(1-λ)C_ ,ωBE [\| θ_k+1- θ_k\|_2^2 ]+ ( pN+ 4α^2(1-p)B )ν^2. ∎ Appendix E 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. See 5.1 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( θ) J( θ)-I_ ( θ). We formally define the generalized gradient mapping as η()≔1η(Θ(+η∇J())−)G_η( θ) 1η(P_ ( θ+η∇ J( θ))- θ). Note that the mapping ηG_η serves as a generalized projected gradient at θ. By definition, in the unconstrained setting where Θ=ℝdΘ =R^d_ , this recovers the standard gradient, yielding η()=∇J()G_η( θ)= _ θJ( θ). According to the definition of Θ()I_ ( θ): Θ()=0,if∈Θ+∞otherwise, _ ( u)= cases0,&if~ u∈ \\ +∞&otherwise cases, we have argmax∈ℝdΘ()=argmax∈ΘJ()≔∗arg _ θ ^d_ J( θ)=arg _ θ∈ J( θ) θ^*. Letting ~∗≔∗−ψ J^* ^*-ψ and defining μ≔1/χ2μ 1/χ^2, we reformulate the WGD condition (Assumption 3.2) over the bounded domain using this gradient mapping: μmax0,~∗−(k)≤‖η(k)‖2 μ \0, J^*-J( θ_k)\≤\|G_η( θ_k)\|_2 Considering an iteration k∈⟦K⟧k∈ K , the parameter update applies projected stochastic gradient ascent: k+1=Θ(k+η∇^†J(k)) θ_k+1=P_ ( θ_k+η ∇ _ θJ( θ_k)). By expanding the Euclidean projection and discarding terms independent of the optimization variable, this is equivalent to: k+1=argmin∈ℝdΘ()+12η‖−k‖22−⟨∇^†J(k),⟩. θ_k+1= _ u ^d \I_ ( u)+ 12η\| u- θ_k\|_2^2- ∇ _ θJ( θ_k), u \. We define the stochastic gradient mapping as ~k≔1η(k+1−k) G_k 1η( θ_k+1- θ_k). Let ∈∂Θ(k+1) g∈ _ ( θ_k+1) be a subgradient of the indicator function. According to the optimality condition of the projection step, we have +1η(k+1−k)−∇^†J(k)=0 g+ 1η( θ_k+1- θ_k)- ∇ _ θJ( θ_k)=0. By the convexity of ΘI_ , it follows that: Θ(k+1) _ ( θ_k+1) ≤Θ(k)+⟨,k+1−k⟩ _ ( θ_k)+ g, θ_k+1- θ_k =Θ(k)−⟨1η(k+1−k)−∇^†J(k),k+1−k⟩. =I_ ( θ_k)- 1η( θ_k+1- θ_k)- ∇ _ θJ( θ_k), θ_k+1- θ_k . From the L-smoothness of J()J( θ) obtained in Lemma D.2, we can write the ascent lemma as follows: J(k+1)≥J(k)+⟨∇J(k),k+1−k⟩−L2‖k+1−k‖22. J( θ_k+1)≥ J( θ_k)+ _ θJ( θ_k), θ_k+1- θ_k - L2\| θ_k+1- θ_k\|_2^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: (k+1) ( θ_k+1) ≥(k)+⟨∇J(k)−∇^†J(k),k+1−k⟩+1η‖k+1−k‖22−L2‖k+1−k‖22 ( θ_k)+ _ θJ( θ_k)- ∇ _ θJ( θ_k), θ_k+1- θ_k + 1η\| θ_k+1- θ_k\|_2^2- L2\| θ_k+1- θ_k\|_2^2 =(k)+η⟨∇J(k)−∇^†J(k),~k⟩+η‖~k‖22−L2‖k+1−k‖22. =J( θ_k)+η _ θJ( θ_k)- ∇ _ θJ( θ_k), G_k +η\| G_k\|_2^2- L2\| θ_k+1- θ_k\|_2^2. Applying Young’s inequality ⟨x,y⟩≥−12‖x‖22−12‖y‖22 x,y ≥- 12\|x\|_2^2- 12\|y\|_2^2 to the inner product, we bound the relation: (k+1) ( θ_k+1) ≥(k)−η2‖∇J(k)−∇^†J(k)‖22+η2‖~k‖22−L2‖k+1−k‖22 ( θ_k)- η2\| _ θJ( θ_k)- ∇ _ θJ( θ_k)\|_2^2+ η2\| G_k\|_2^2- L2\| θ_k+1- θ_k\|_2^2 =(k)−η2‖∇J(k)−∇^†J(k)‖22+η4‖~k‖22+(14η−L2)‖k+1−k‖22. =J( θ_k)- η2\| _ θJ( θ_k)- ∇ _ θJ( θ_k)\|_2^2+ η4\| G_k\|_2^2+ ( 14η- L2 )\| θ_k+1- θ_k\|_2^2. By expanding the definitions of the gradient mappings and applying the property of the Euclidean projection operator ‖Θ(x)−Θ(y)‖2≤‖x−y‖2\|P_ (x)-P_ (y)\|_2≤\|x-y\|_2, we bound the difference between the exact and stochastic gradient mappings: ‖η(k)−~k‖2 \|G_η( θ_k)- G_k\|_2 =1η‖Θ(k+η∇J(k))−Θ(k+η∇^†J(k))‖2 = 1η \|P_ ( θ_k+η _ θJ( θ_k))-P_ ( θ_k+η ∇ _ θJ( θ_k)) \|_2 ≤1η‖(k+η∇J(k))−(k+η∇^†J(k))‖2 ≤ 1η \|( θ_k+η _ θJ( θ_k))-( θ_k+η ∇ _ θJ( θ_k)) \|_2 =‖∇J(k)−∇^†J(k)‖2. =\| _ θJ( θ_k)- ∇ _ θJ( θ_k)\|_2. Utilizing the inequality ‖η(k)‖22≤2‖~k‖22+2‖η(k)−~k‖22\|G_η( θ_k)\|_2^2≤ 2\| G_k\|_2^2+2\|G_η( θ_k)- G_k\|_2^2, which follows from adding and subtracting the stochastic gradient mapping and applying Young’s inequality, we bound the remaining mapping term: η4‖~k‖22≥η8‖η(k)‖22−η4‖∇J(k)−∇^†J(k)‖22. η4\| G_k\|_2^2≥ η8\|G_η( θ_k)\|_2^2- η4\| _ θJ( θ_k)- ∇ _ θJ( θ_k)\|_2^2. Substituting this lower bound yields the final single-step proximal descent inequality: (k+1)≥(k)−3η4‖∇J(k)−∇^†J(k)‖22+η8‖η(k)‖22+(14η−L2)‖k+1−k‖22. ( θ_k+1) ( θ_k)- 3η4\| _ θJ( θ_k)- ∇ _ θJ( θ_k)\|_2^2+ η8\|G_η( θ_k)\|_2^2+ ( 14η- L2 )\| θ_k+1- θ_k\|_2^2. (10) Reversing the sign, applying the total expectation, and substituting the suboptimality rk≔[~∗−(k)]r_k [ J^*-J( θ_k)] and the estimation error Δk≔[‖∇^†J(k)−∇J(k)‖22] _k [\| ∇ _ θJ( θ_k)- _ θJ( θ_k)\|_2^2], we obtain the projected suboptimality recurrence: rk+1≤rk−η8[‖η(k)‖22]+3η4Δk−(14η−L2)[‖k+1−k‖22]. r_k+1≤ r_k- η8E [\|G_η( θ_k)\|_2^2 ]+ 3η4 _k- ( 14η- L2 )E [\| θ_k+1- θ_k\|_2^2 ]. (11) From Lemma D.4, the unified variance recurrence uses the effective decay rate λ≔1−(1−p)(1−α)2λ 1-(1-p)(1-α)^2 and noise floor Cν≔(pN+4α2(1−p)B)ν2C_ν ( pN+ 4α^2(1-p)B )ν^2. The variance recurrence is: Δk+1≤(1−λ)Δk+(1−λ)C†,ωB[‖k+1−k‖22]+Cν. _k+1≤(1-λ) _k+ (1-λ)C_ ,ωBE [\| θ_k+1- θ_k\|_2^2 ]+C_ν. (12) We introduce the potential function Φk≔rk+cΔk _k r_k+c _k with a coupling constant c>0c>0. Because the estimation error Δk _k is intrinsically non-negative, the potential strictly upper-bounds the suboptimality (Φk≥rk _k≥ r_k). Consequently, establishing the convergence of Φk _k is sufficient to guarantee the convergence of rkr_k. Combining equations (11) and (12), we construct the unified recurrence: Φk+1 _k+1 ≤rk−η8[‖η(k)‖22]+3η4Δk−(14η−L2)[‖k+1−k‖22] ≤ r_k- η8E [\|G_η( θ_k)\|_2^2 ]+ 3η4 _k- ( 14η- L2 )E [\| θ_k+1- θ_k\|_2^2 ] +c((1−λ)Δk+2(1−λ)C†,ωB[‖k+1−k‖22]+Cν) +c ((1-λ) _k+ 2(1-λ)C_ ,ωBE [\| θ_k+1- θ_k\|_2^2 ]+C_ν ) =Φk−η8[‖η(k)‖22]−(cλ−3η4)Δk = _k- η8E [\|G_η( θ_k)\|_2^2 ]- (cλ- 3η4 ) _k −(14η−L2−c2(1−λ)C†,ωB)[‖k+1−k‖22]+cCν. - ( 14η- L2-c 2(1-λ)C_ ,ωB )E [\| θ_k+1- θ_k\|_2^2 ]+cC_ν. To simplify the recurrence, we determine the constant c by requiring the Δk _k coefficient to retain an exact −3η4- 3η4 residual descent rate: cλ−3η4=3η4⇒c=3η2λ. cλ- 3η4= 3η4 c= 3η2λ. Substituting this choice of c, we require the sequence distance coefficient to remain non-negative to eliminate it from the upper bound: 14η−L2−3η(1−λ)C†,ωλB≥0. 14η- L2- 3η(1-λ)C_ ,ωλ B≥ 0. To ensure the sequence distance coefficient provides sufficient slack to absorb the variance accumulation, we tighten the standard smoothness restriction. By rigorously restricting the baseline learning rate to η≤14Lη≤ 14L, we enforce the bound L2≤18η L2≤ 18η, which guarantees the strictly positive residual 14η−L2≥14η−18η=18η 14η- L2≥ 14η- 18η= 18η. Substituting this residual isolates the maximum stable learning rate required to absorb the variance accumulation: 18η≥3η(1−λ)C†,ωλB⇒η≤λB24(1−λ)C†,ω. 18η≥ 3η(1-λ)C_ ,ωλ B η≤ λ B24(1-λ)C_ ,ω. Under these stability conditions, the recurrence simplifies to: Φk+1≤Φk−η8[‖η(k)‖22]−3η4Δk+3ηCν2λ. _k+1≤ _k- η8E [\|G_η( θ_k)\|_2^2 ]- 3η4 _k+ 3η C_ν2λ. (13) Substituting the modified gradient domination condition and applying Jensen’s inequality for both the maximum and square operations yields: Φk+1≤Φk−μη8max0,rk2−3η4Δk+3ηCν2λ. _k+1≤ _k- μη8 \0,r_k \^2- 3η4 _k+ 3η C_ν2λ. (14) 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≔max0,Φkx_k \0, _k\ and show it unconditionally satisfies a unified descent recurrence. We evaluate the transition for xkx_k based on the sign of Φk _k. If Φk≤0 _k≤ 0, we have xk=0x_k=0. From Equation (13), dropping the non-positive descent terms yields Φk+1≤Φk+3ηCν2λ≤3ηCν2λ _k+1≤ _k+ 3η C_ν2λ≤ 3η C_ν2λ. Taking the positive part of both sides guarantees xk+1≤3ηCν2λx_k+1≤ 3η C_ν2λ, which satisfies the target recurrence evaluated at xk=0x_k=0. Conversely, if Φk>0 _k>0, we have xk=Φkx_k= _k. Because Φk≤max0,rk+cΔk _k≤ \0,r_k\+c _k, it follows that at least one of the following conditions must hold: either max0,rk≥Φk2 \0,r_k\≥ _k2, or cΔk≥Φk2c _k≥ _k2. If the first case holds (max0,rk≥Φk2 \0,r_k\≥ _k2), we bound the suboptimality descent while discarding the negative variance term: −μη8max0,rk2≤−μη8(xk2)2=−μη32xk2. - μη8 \0,r_k \^2≤- μη8 ( x_k2 )^2=- μη32x_k^2. If the second case holds (cΔk≥Φk2c _k≥ _k2), utilizing our choice of c=3η/2λc=3η/2λ yields Δk≥λxk3η _k≥ λ x_k3η. Discarding the suboptimality term bounds the variance descent term: −3η4Δk≤−3η4(λxk3η)=−λ4xk. - 3η4 _k≤- 3η4 ( λ x_k3η )=- λ4x_k. Bounding the descent in Equation (14) by the minimum of these two rates, and observing that taking the maximum operator xk+1=max0,Φk+1x_k+1= \0, _k+1\ on the left preserves the inequality because the right-hand side is inherently non-negative or bounded safely by 00, we obtain the final unconditional recurrence: xk+1≤xk−minμη32xk2,λ4xk+3ηCν2λ. x_k+1≤ x_k- \ μη32x_k^2, λ4x_k \+ 3η C_ν2λ. We directly apply Lemma H.2 to the invariant sequence xkx_k with a=μη32a= μη32, b=λ4b= λ4, and e=3ηCν2λe= 3η C_ν2λ. Because λ≤1λ≤ 1 structurally, we inherently satisfy the lemma’s contraction requirement ρϵ≤b=λ4<1 _ε≤ b= λ4<1. Hence, from Lemma H.2, the iteration complexity is described by: K≥max32μηϵ,4λlog+2Φ0ϵ. K≥ \ 32μηε, 4λ \ _+ 2 _0ε. (15) To guarantee convergence to the target accuracy ϵε, the noise term must satisfy two conditions. The first condition e≤aϵ22e≤ a ε^22 requires 3ηCν2λ≤μηϵ264 3η C_ν2λ≤ μηε^264, which simplifies to bounding the noise floor Cν≤μλϵ296C_ν≤ μλε^296. The second condition e≤bϵ2e≤ b ε2 requires 3ηCν2λ≤λϵ8 3η C_ν2λ≤ λε8, which dictates the maximum stable learning rate η≤λ2ϵ12Cνη≤ λ^2ε12C_ν. We satisfy the first accuracy condition Cν≤μλϵ296C_ν≤ μλε^296 by configuring the algorithmic parameters such that each of the two additive terms in Cν=(pN+4α2(1−p)B)ν2C_ν= ( pN+ 4α^2(1-p)B )ν^2 is independently bounded by half of the target limit, μλϵ2192 μλε^2192. With the unified decay rate λ=p+(1−p)(2α−α2)λ=p+(1-p)(2α-α^2), we evaluate both terms to define the feasible geometric region. First Term of CνC_ν and Batch Size. Observing that 2α−α2≥02α-α^2≥ 0, we establish the lower bound λ≥pλ≥ p. It is therefore sufficient to enforce: pν2N≤μpϵ2192⟹N≥192ν2μϵ2. pν^2N≤ μ pε^2192 N≥ 192ν^2με^2. To minimize sample cost while satisfying this requirement, we select a full batch size N=Θ(ϵ−2)N= (ε^-2) and initialize with N0=N=Θ(ϵ−2)N_0=N= (ε^-2). Second Term of CνC_ν and Momentum. Observing that 2α−α2=α(2−α)≥α2α-α^2=α(2-α)≥α for any α∈(0,1]α∈(0,1], and dropping the positive p term from λ, we obtain the lower bound λ≥(1−p)αλ≥(1-p)α. Substituting this lower bound into the right-hand side, it is strictly sufficient to require: 4α2(1−p)ν2B≤μ(1−p)αϵ2192. 4α^2(1-p)ν^2B≤ μ(1-p)αε^2192. Because α>0α>0, we divide both sides by the common factor α(1−p)α(1-p) to directly isolate α: 4αν2B≤μϵ2192⟹α≤μBϵ2768ν2. 4αν^2B≤ με^2192 α≤ μ Bε^2768ν^2. This establishes the strict upper bound α=(Bϵ2)α=O(Bε^2). Expected Sample Cost and Refresh Probability. We choose p,α≥0p,α≥ 0 such that p+α=μBϵ2768ν2. p+α= μ Bε^2768ν^2. This ensures the momentum constraint established above. For sufficiently small ϵε, we have p+α≤1/2p+α≤ 1/2, and hence p+α≤λ=p+(1−p)(2α−α2)≤p+2α≤2(p+α). p+α≤λ=p+(1-p)(2α-α^2)≤ p+2α≤ 2(p+α). Therefore, λ=Θ(μBϵ2/ν2)λ= (μ Bε^2/ν^2), with universal implicit constants. Moreover, since p≤μBϵ2/(768ν2)p≤μ Bε^2/(768ν^2), pN+(1−p)B pN+(1-p)B ≤μBϵ2768ν2(192ν2μϵ2+1)+B ≤ μ Bε^2768ν^2 ( 192ν^2με^2+1 )+B ≤5B4+12=(B). ≤ 5B4+ 12=O(B). Learning Rate. To achieve the optimal total sample complexity n=~(ϵ−2)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 ((Bϵ2)−1)O((Bε^2)^-1). This bound limits the total number of optimization steps to guarantee that the cumulative sample cost of the (B)O(B) per-iteration updates does not breach the optimal ~(ϵ−2) O(ε^-2) global sample complexity. Given the initial batch N0=Θ(ϵ−2)N_0= (ε^-2) and an expected per-iteration sample cost bounded by (B)O(B), the number of iterations must satisfy K⋅(B)≤~(ϵ−2)K·O(B)≤ O(ε^-2), which mandates K≤((Bϵ2)−1)K ((Bε^2)^-1). The sufficient iteration budget in Equation (15) contains the estimator-decay term 4/λ4/λ. To keep this term within the desired iteration budget ((Bϵ2)−1)O((Bε^2)^-1), we impose λ=Ω(Bϵ2)λ= (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λ=1-(1-p)(1-α)^2=p+2α-α^2-2pα+pα^2. Since the upper bounds p=(Bϵ2)p=O(Bε^2) and α=(Bϵ2)α=O(Bε^2) are established, the higher-order terms α2α^2, pαpα, and pα2pα^2 scale as (B2ϵ4)O(B^2ε^4) or smaller. Consequently, for sufficiently small target accuracy ϵ→0ε→ 0, the decay rate is dominated by its linear components, reducing asymptotically to λ=p+2α−(B2ϵ4)λ=p+2α-O(B^2ε^4). To satisfy the λ=Ω(Bϵ2)λ= (Bε^2) decay floor, these dominant terms must jointly fulfill the geometric condition p+α=Ω(Bϵ2)p+α= (Bε^2). For any configuration (p,α)(p,α) satisfying this combined system of bounds, the decay rate and noise floor scale precisely as λ=Θ(Bϵ2)λ= (Bε^2) and Cν=Θ(Bϵ4)C_ν= (Bε^4), respectively. We evaluate the remaining step-size restrictions using these asymptotic rates. The last-iterate stability condition η≤λ2ϵ12Cνη≤ λ^2ε12C_ν resolves to η≤Θ(Bϵ)η≤ (Bε). Concurrently, the variance recurrence threshold evaluates to λB12(1−λ)C†,ω=Θ(Bϵ) λ B12(1-λ)C_ ,ω= (Bε). By explicitly selecting the step size η to match this scaling alongside the L-smoothness limit, all stability requirements are unconditionally satisfied: η=min14L,λ2ϵ12Cν,λB24(1−λ)C†,ω=Θ(Bϵ). η= \ 14L, λ^2ε12C_ν, λ B24(1-λ)C_ ,ω \= (Bε). Sample Complexity. With these conditions established, Lemma H.2 guarantees that it suffices to choose the number of iterations as: K=⌈max32μηϵ,4λlog+2Φ0ϵ⌉. K= \ 32μηε, 4λ \ _+ 2 _0ε . Substituting our choice of η into the iteration bound gives: K=⌈max128Lμϵ,384Cνμλ2ϵ2,3224(1−λ)C†,ωμϵλB,4λlog+2Φ0ϵ⌉. K= \ 128Lμε, 384C_νμλ^2ε^2, 32 24(1-λ)C_ ,ωμε λ B, 4λ \ _+ 2 _0ε . The noise constraint Cν≤μλϵ2/96C_ν≤μλε^2/96 implies 384Cνμλ2ϵ2≤384μλ2ϵ2μλϵ296=4λ. 384C_νμλ^2ε^2≤ 384μλ^2ε^2 μλε^296= 4λ. Thus, this term is absorbed by the estimator-decay term. Moreover, the established bound λ≥μBϵ2/(768ν2)λ≥μ Bε^2/(768ν^2) yields 4λ≤3072ν2μBϵ2. 4λ≤ 3072ν^2μ Bε^2. Using the same lower bound on λ and 1−λ≤11-λ≤ 1, the variance-stability term satisfies 3224(1−λ)C†,ωμϵλB 32 24(1-λ)C_ ,ωμε λ B ≤3224C†,ωμϵ768ν2μB2ϵ2 ≤ 32 24C_ ,ωμε 768ν^2μ B^2ε^2 =30722νC†,ωμ3/2Bϵ2. = 3072 2\,ν C_ ,ωμ^3/2Bε^2. Combining these bounds, absorbing numerical constants and logarithmic factors, and accounting for the ceiling, we obtain: K=~(1+Lμϵ+ν2μBϵ2+νC†,ωμ3/2Bϵ2). K= O (1+ Lμε+ ν^2μ Bε^2+ ν C_ ,ωμ^3/2Bε^2 ). The expected total sample complexity n is determined by the initial batch size N0N_0 plus the sum of the expected batch sizes drawn over the K iterations: n=N0+K(pN+(1−p)B). n=N_0+K(pN+(1-p)B). By substituting N0=⌈192ν2/(μϵ2)⌉N_0= 192ν^2/(με^2) , the iteration bound above, and the bounded per-iteration cost pN+(1−p)B=(B)pN+(1-p)B=O(B), we obtain: n=~(1+B+BLμϵ+ν2μϵ2+νC†,ωμ3/2ϵ2). n= O (1+B+ BLμε+ ν^2με^2+ ν C_ ,ωμ^3/2ε^2 ). Thus, for fixed B and fixed positive problem-dependent constants, the complexity is n=~(ϵ−2)n= O(ε^-2) as ϵ→0ε→ 0. To establish the asymptotic dependence on the reward bounds and the effective horizon, we substitute the problem-dependent constants. From Lemma D.1, the GPOMDP second-moment bound scales as ν2=(Rmax2(1−γ)−3)ν^2=O(R_ ^2(1-γ)^-3). From Lemma B.1, the defensive mean-squared smoothness constant scales as C†,ω=(Rmax2(1−γ)−5)C_ ,ω=O(R_ ^2(1-γ)^-5). Substituting these bounds into the terms proportional to ϵ−2ε^-2, and using μ=χ−2μ=χ^-2, yields: n=~(Rmax2ϵ2[χ2(1−γ)3+χ3(1−γ)4]), n= O ( R_ ^2ε^2 [ χ^2(1-γ)^3+ χ^3(1-γ)^4 ] ), where the policy-regularity and defensive-mixture constants are treated as fixed. This establishes the minimax-optimal dependence on ϵε, up to logarithmic factors, while retaining the explicit dependence on the WGD constant and the effective horizon. ∎ 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≥1B≥ 1 and sufficiently small target accuracy ϵ>0ε>0, through an appropriate choice of the algorithmic parameters (full batch size N, initial batch size N0N_0, refresh probability p, and learning rate η), DEF-PAGE-PG with α=0α=0 guarantees J∗−[J(k)]≤ψ+ϵJ^*-E[J( θ_k)]≤ψ+ε with a sample complexity of at most: n n =N0+K(1+B−BN) =N_0+K (1+B- BN ) =~(Rmax2ϵ2[χ2(1−γ)3+χ3(1−γ)4]). = O ( R_ ^2ε^2 [ χ^2(1-γ)^3+ χ^3(1-γ)^4 ] ). Here, ~(⋅) O(·) hides logarithmic factors, and B, the policy-regularity constants, and the defensive-mixture parameter are treated as fixed. Proof. Setting the momentum parameter to α=0α=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νC_ν simplify to: λ=p,Cν=pν2N. λ=p, C_ν= pν^2N. For p>0p>0, the noise constraint Cν≤μλϵ2/96C_ν≤μλε^2/96 reduces to: pν2N≤μpϵ296⟹N≥96ν2μϵ2. pν^2N≤ μ pε^296 N≥ 96ν^2με^2. Accordingly, we select N0=N=⌈96ν2/(μϵ2)⌉N_0=N= 96ν^2/(με^2) and p=1/Np=1/N. For sufficiently small ϵε, we have 96ν2/(μϵ2)≥196ν^2/(με^2)≥ 1, so that 96ν2μϵ2≤N≤192ν2μϵ2. 96ν^2με^2≤ N≤ 192ν^2με^2. Next, we evaluate the stability constraints on the learning rate. For the variance stability requirement η≤λB/[24(1−λ)CDEF,ω]η≤ λ B/[24(1-λ)C_ DEF,ω], using λ=1/Nλ=1/N and 1−λ≤11-λ≤ 1, it suffices to enforce: η≤μB4608ν2CDEF,ωϵ≤B24NCDEF,ω. η≤ μ B4608ν^2C_ DEF,ωε≤ B24NC_ DEF,ω. For the accuracy requirement η≤λ2ϵ/(12Cν)η≤λ^2ε/(12C_ν), substitution gives: λ2ϵ12Cν=pNϵ12ν2=ϵ12ν2. λ^2ε12C_ν= pNε12ν^2= ε12ν^2. Defining cη≔min112ν2,μB4608ν2CDEF,ω, c_η \ 112ν^2, μ B4608ν^2C_ DEF,ω \, we therefore select η=min1/(4L),cηϵη= \1/(4L),c_ηε\. The sufficient iteration budget established in the proof of Theorem 5.1 is K≥max32/(μηϵ),4/λlog+(2Φ0/ϵ)K≥ \32/(μηε),4/λ\ _+(2 _0/ε). Using 4/λ=4N≤768ν2/(μϵ2)4/λ=4N≤ 768ν^2/(με^2) and substituting the full learning-rate choice, we select: K=⌈max128Lμϵ,768ν2μϵ2,15362νCDEF,ωμ3/2Bϵ2log+2Φ0ϵ⌉. K= \ 128Lμε, 768ν^2με^2, 1536 2\,ν C_ DEF,ωμ^3/2 Bε^2 \ _+ 2 _0ε . Since an iteration draws N trajectories with probability p=1/Np=1/N and B trajectories otherwise, the expected per-iteration cost is 1+(1−1/N)B1+(1-1/N)B. Consequently: n=N0+K(1+B−BN). n=N_0+K (1+B- BN ). Substituting the selected values of N0N_0 and K,and using 1+B−B/N≤1+B1+B-B/N≤ 1+B, yields: n=~(1+B+(1+B)Lμϵ+(1+B)ν2μϵ2+(1+B)νCDEF,ωμ3/2Bϵ2). n= O (1+B+ (1+B)Lμε+ (1+B)ν^2με^2+ (1+B)ν C_ DEF,ωμ^3/2 Bε^2 ). For fixed B and fixed positive problem-dependent constants, the terms proportional to ϵ−2ε^-2 dominate as ϵ→0ε→ 0. Substituting ν2=(Rmax2(1−γ)−3)ν^2=O(R_ ^2(1-γ)^-3), CDEF,ω=(Rmax2(1−γ)−5)C_ DEF,ω=O(R_ ^2(1-γ)^-5), and μ=χ−2μ=χ^-2 gives: n=~(Rmax2ϵ2[χ2(1−γ)3+χ3(1−γ)4]), n= O ( R_ ^2ε^2 [ χ^2(1-γ)^3+ χ^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≥1B≥ 1 and sufficiently small target accuracy ϵ>0ε>0, through an appropriate choice of the algorithmic parameters (momentum α, initial batch size N0N_0, and learning rate η), DEF-STORM-PG with p=0p=0 and defensive-mixture parameter ξ=1/2ξ=1/2 guarantees J∗−[J(k)]≤ψ+ϵJ^*-E[J( θ_k)]≤ψ+ε with a sample complexity of at most: n n =N0+KB =N_0+KB =~(Rmax2ϵ2[χ2(1−γ)3+χ3(1−γ)4]). = O ( R_ ^2ε^2 [ χ^2(1-γ)^3+ χ^3(1-γ)^4 ] ). Here, ~(⋅) O(·) hides logarithmic factors, and B and the policy-regularity constants are treated as fixed. Proof. Setting the refresh probability to p=0p=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ξ=1/2, the decay rate λ and the corrected noise floor CνC_ν simplify to: λ=2α−α2,Cν=4α2ν2B. λ=2α-α^2, C_ν= 4α^2ν^2B. Since λ≥αλ≥α for α∈[0,1]α∈[0,1], a sufficient condition for Cν≤μλϵ2/96C_ν≤μλε^2/96 is: 4α2ν2B≤μαϵ296⟹α≤μBϵ2384ν2. 4α^2ν^2B≤ μαε^296 α≤ μ Bε^2384ν^2. We therefore select α=μBϵ2/(384ν2)α=μ Bε^2/(384ν^2) and N0=⌈96ν2/(μϵ2)⌉N_0= 96ν^2/(με^2) . For sufficiently small ϵε, this choice satisfies α∈(0,1)α∈(0,1). For the variance stability requirement η≤λB/[24(1−λ)CDEF,ω]η≤ λ B/[24(1-λ)C_ DEF,ω], using λ≥αλ≥α and 1−λ≤11-λ≤ 1, we enforce: η≤αB24CDEF,ω=μB29216ν2CDEF,ωϵ. η≤ α B24C_ DEF,ω= μ B^29216ν^2C_ DEF,ωε. For the last-iterate accuracy requirement, λ≥αλ≥α gives: λ2ϵ12Cν≥α2ϵ12(4α2ν2/B)=Bϵ48ν2. λ^2ε12C_ν≥ α^2ε12(4α^2ν^2/B)= Bε48ν^2. Consequently, defining cη≔minB48ν2,μB29216ν2CDEF,ω, c_η \ B48ν^2, μ B^29216ν^2C_ DEF,ω \, we select η=min1/(4L),cηϵη= \1/(4L),c_ηε\. Using the sufficient iteration budget established in the proof of Theorem 5.1, together with 4/λ≤4/α=1536ν2/(μBϵ2)4/λ≤ 4/α=1536ν^2/(μ Bε^2), we select: K=⌈max128Lμϵ,1536ν2μBϵ2,3072νCDEF,ωμ3/2Bϵ2log+2Φ0ϵ⌉. K= \ 128Lμε, 1536ν^2μ Bε^2, 3072ν C_ DEF,ωμ^3/2Bε^2 \ _+ 2 _0ε . Here, the terms proportional to ϵ−1ε^-1 and ϵ−2ε^-2 follow by substituting the full learning-rate choice into 32/(μηϵ)32/(μηε). Because p=0p=0, the algorithm draws a fixed mini-batch of size B at every iteration. Consequently, the total sample complexity is: n=N0+KB. n=N_0+KB. Substituting the selected values of N0N_0 and K gives: n=~(1+B+BLμϵ+ν2μϵ2+νCDEF,ωμ3/2ϵ2). n= O (1+B+ BLμε+ ν^2με^2+ ν C_ DEF,ωμ^3/2ε^2 ). For fixed B and fixed positive problem-dependent constants, the terms proportional to ϵ−2ε^-2 dominate as ϵ→0ε→ 0. Substituting ν2=(Rmax2(1−γ)−3)ν^2=O(R_ ^2(1-γ)^-3), CDEF,ω=(Rmax2(1−γ)−5)C_ DEF,ω=O(R_ ^2(1-γ)^-5), and μ=χ−2μ=χ^-2 yields: n=~(Rmax2ϵ2[χ2(1−γ)3+χ3(1−γ)4]), n= O ( R_ ^2ε^2 [ χ^2(1-γ)^3+ χ^3(1-γ)^4 ] ), where the policy-regularity constants are treated as fixed. ∎ Appendix F 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 Θ=ℝd =R^d. See 5.1 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 Domination condition holds with the constants χ=C1/μFχ=C_1/ _F and ψ=ϵbiasκ/(1−γ)ψ= _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. ∎ Appendix G Lower-Bound See 3.1 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 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−α]θ∈[α,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χ=4/3 and ψ=0ψ=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, ℳ1M_1 and ℳ2M_2. 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) (δ(1-γ)^-1). By tuning this ”wrong-action” penalty to perfectly match our target accuracy threshold ϵε, we isolate the required perturbation scale to δ=(ϵ(1−γ)2)δ=O(ε(1-γ)^2). Because a valid A must guarantee ϵε-optimality across all instances, it is forced to determine whether it is interacting with ℳ1M_1 or ℳ2M_2. 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 (nδ2(1−γ)−2)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 distinguish the instances, and thus avoid the sub-optimality penalty, is exactly Ω((1−γ)−2Rmax2ϵ−2) ((1-γ)^-2R_ ^2ε^-2). 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, ℳ∈ℳ1,ℳ2M∈\M_1,M_2\, with state space =s,s¯S=\s, s\ and action space =a0,a1A=\a_0,a_1\. The state s¯ s is an absorbing state where any action a∈a yields a deterministic self-transition with zero reward, meaning P(s¯|s¯,a)=1P( s| s,a)=1 and R(s¯,a,s¯)=0R( s,a, s)=0. In the initial state s, taking an action a triggers a self-transition to s with probability pap_a, yielding a reward of RmaxR_ , and transitions to the absorbing state s¯ s with probability 1−pa1-p_a, yielding RmaxR_ . The two instances differ strictly in the transition probabilities from the initial state s. For the instance ℳ1M_1, we set pa0=p+δp_a_0=p+δ and pa1=p_a_1=p, making a0a_0 the optimal action. Conversely, for the instance ℳ2M_2, we set pa0=p_a_0=p and pa1=p+δp_a_1=p+δ, making a1a_1 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−γp=1- 1-γ. Consequently, to satisfy the requirement that p+δ≤1p+δ≤ 1, the perturbation parameter δ is strictly bounded by δ≤1−γ2γδ≤ 1-γ2γ. s¯ sa0:p+δ,Rmaxa_0:p+δ,R_ a1:p,Rmaxa_1:p,R_ a0:1−(p+δ),Rmaxa_0:1-(p+δ),R_ a1:1−p,Rmaxa_1:1-p,R_ ∀a:1,0∀ a:1,0 Figure 3: Transition dynamics for instance ℳ1M_1. s¯ sa0:p,Rmaxa_0:p,R_ a1:p+δ,Rmaxa_1:p+δ,R_ a0:1−p,Rmaxa_0:1-p,R_ a1:1−(p+δ),Rmaxa_1:1-(p+δ),R_ ∀a:1,0∀ a:1,0 Figure 4: Transition dynamics for instance ℳ2M_2. We consider a direct policy parametrization in which the scalar parameter θ determines the probability of selecting the action a0a_0 in the initial state s. For the binary action space =a0,a1A=\a_0,a_1\, the policy is defined as: πθ(a∣s) _θ(a s) =θif a=a0,1−θotherwise. = casesθ&if a=a_0,\\ 1-θ&otherwise. cases Part I: 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−α] =[α,1-α] for a strictly positive constant α∈(0,1/2)α∈(0,1/2). The score function is given by: ∇θlogπθ(a∣s) _θ _θ(a s) =1θif a=a0,−11−θotherwhise. = cases 1θ&if a=a_0,\\ - 11-θ&otherwhise. cases Condition (i) requires the score norm to be bounded. Since θ∈[α,1−α]θ∈[α,1-α], the probability of any action is bounded strictly away from zero, uniformly bounding the score. We establish the constant C1C_1 as the supremum of the score function over the parameter space and action space: supa∈‖∇θlogπθ(a∣s)‖2 _a \| _θ _θ(a s) \|_2 =maxθ∈[α,1−α]max1θ,11−θ=1α. = _θ∈[α,1-α] \ 1θ, 11-θ \= 1α. Thus, condition (i) is satisfied with C1≤1/αC_1≤ 1/α. To verify condition (i), we must establish that the score function is Lipschitz continuous in expectation. We first calculate the Hessian of the log-policy: ∇θ2logπθ(a∣s) ∇^2_θ _θ(a s) =−1θ2if a=a0,−1(1−θ)2otherwise. = cases- 1θ^2&if a=a_0,\\ - 1(1-θ)^2&otherwise. cases The restricted domain Θ guarantees that the Hessian norm is uniformly bounded by 1/α21/α^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 : ‖∇θlogπθ(a∣s)−∇θlogπθ′(a∣s)‖22 \| _θ _θ(a s)- _θ _θ (a s) \|_2^2 ≤(supθ~∈Θ‖∇θ2logπθ~(a∣s)‖2)2‖θ−θ′‖22 ≤ ( _ θ∈ \|∇^2_θ _ θ(a s) \|_2 )^2\|θ-θ \|_2^2 ≤(1α2)2‖θ−θ′‖22 ≤ ( 1α^2 )^2\|θ-θ \|_2^2 =1α4‖θ−θ′‖22. = 1α^4\|θ-θ \|_2^2. Because this upper bound holds deterministically for all actions a∈a , taking the expectation over a∼πθ(⋅∣s)a _θ(· s) preserves the inequality. Thus, condition (i) is satisfied with the constant LS=1/α2L_S=1/α^2: a∼πθ[‖∇θlogπθ(a∣s)−∇θlogπθ′(a∣s)‖22] E_a _θ [ \| _θ _θ(a s)- _θ _θ (a s) \|_2^2 ] ≤1α4‖θ−θ′‖22. ≤ 1α^4\|θ-θ \|_2^2. We now verify the validity of Assumption 3.2 with ψ=0ψ=0 in our setting. We start computing the expected return J(i)(θ)J^(i)(θ), its optimal value J∗,(i)J^*,(i) within the restricted domain Θ=[α,1−α] =[α,1-α], and the gradient norm ‖∇θJ(i)(θ)‖2\| _θJ^(i)(θ)\|_2 for both instances i∈1,2i∈\1,2\. By assigning a reward of RmaxR_ to any action taken in state s prior to reaching the zero-reward absorbing state s¯ s, the expected immediate reward at time t, given st=s_t=s, is exactly RmaxR_ . The expected discounted return resolves to a standard geometric series: J(θ) J(θ) =∑t=0∞γtP(st=s∣s0=s)Rmax=Rmax∑t=0∞(γpθ)t=Rmax1−γpθ. = _t=0^∞γ^tP(s_t=s s_0=s)R_ =R_ _t=0^∞(γ p_θ)^t= R_ 1-γ p_θ. For the specific instances ℳ1M_1 and ℳ2M_2, the effective self-transition probabilities under the policy πθ _θ are: pθ(1) p_θ^(1) =θ(p+δ)+(1−θ)p=p+θδ, =θ(p+δ)+(1-θ)p=p+θδ, pθ(2) p_θ^(2) =θp+(1−θ)(p+δ)=p+(1−θ)δ. =θ p+(1-θ)(p+δ)=p+(1-θ)δ. Because the expected return monotonically increases with the self-transition probability, the optimal returns J∗,(i)J^*,(i) over the constrained domain Θ=[α,1−α] =[α,1-α] are achieved by maximizing pθ(i)p_θ^(i). For ℳ1M_1, this occurs at θ=1−αθ=1-α, and for ℳ2M_2, this occurs at θ=αθ=α. In both cases, the maximum self-transition probability evaluates to p+(1−α)δp+(1-α)δ. Differentiating the objective function with respect to θ cleanly isolates the gradient of the transition probability: ∇θJ(i)(θ) _θJ^(i)(θ) =γRmax(1−γpθ(i))2∇θpθ(i). = γ R_ (1-γ p_θ^(i))^2 _θp_θ^(i). Table 3: Values for J(i)(θ)J^(i)(θ), J∗,(i)J^*,(i), and ‖∇θJ(i)(θ)‖2 \| _θJ^(i)(θ) \|_2 for the ℳM instances. Instance J(i)(θ)J^(i)(θ) J∗,(i)J^*,(i) ‖∇θJ(i)(θ)‖2 \| _θJ^(i)(θ) \|_2 ℳ1M_1 Rmax1−γ(p+θδ) R_ 1-γ(p+θδ) Rmax1−γ(p+(1−α)δ) R_ 1-γ(p+(1-α)δ) γδRmax(1−γ(p+θδ))2 γδ R_ (1-γ(p+θδ))^2 ℳ2M_2 Rmax1−γ(p+(1−θ)δ) R_ 1-γ(p+(1-θ)δ) Rmax1−γ(p+(1−α)δ) R_ 1-γ(p+(1-α)δ) γδRmax(1−γ(p+(1−θ)δ))2 γδ R_ (1-γ(p+(1-θ)δ))^2 Applying this to both instances yields the values defined in Table 3. We establish the constant χ by first evaluating the ratio with respect to the unconstrained gradient, J∗,(i)−J(i)(θ)‖∇θJ(i)(θ)‖2≤χ J^*,(i)-J^(i)(θ)\| _θJ^(i)(θ)\|_2≤χ. As we will formalize in Remark G.1, bounding this unconstrained ratio is sufficient to satisfy Assumption 3.2 for the generalized mapping ηG_η. Starting with ℳ1M_1, the sub-optimality gap reduces to: J∗,(1)−J(1)(θ) J^*,(1)-J^(1)(θ) =Rmax1−γ(p+(1−α)δ)−Rmax1−γ(p+θδ) = R_ 1-γ(p+(1-α)δ)- R_ 1-γ(p+θδ) =γRmax((p+(1−α)δ)−(p+θδ))(1−γ(p+(1−α)δ))(1−γ(p+θδ)) = γ R_ ((p+(1-α)δ)-(p+θδ))(1-γ(p+(1-α)δ))(1-γ(p+θδ)) =γRmax(1−α−θ)δ(1−γ(p+(1−α)δ))(1−γ(p+θδ)). = γ R_ (1-α-θ)δ(1-γ(p+(1-α)δ))(1-γ(p+θδ)). Dividing this gap by the gradient norm causes both γ and RmaxR_ to cancel out: J∗,(1)−J(1)(θ)‖∇θJ(1)(θ)‖2 J^*,(1)-J^(1)(θ) \| _θJ^(1)(θ) \|_2 =γRmax(1−α−θ)δ(1−γ(p+(1−α)δ))(1−γ(p+θδ))⋅(1−γ(p+θδ))2γδRmax = γ R_ (1-α-θ)δ(1-γ(p+(1-α)δ))(1-γ(p+θδ))· (1-γ(p+θδ))^2γδ R_ =(1−α−θ)1−γ(p+θδ)1−γ(p+(1−α)δ). =(1-α-θ) 1-γ(p+θδ)1-γ(p+(1-α)δ). Applying the definitions p=2γ−1γp= 2γ-1γ (requiring γ>1/2γ>1/2) and δ≤1−γ2γδ≤ 1-γ2γ, the baseline effective horizon evaluates to 1−γp=2(1−γ)1-γ p=2(1-γ). We bound the denominator from below: 1−γ(p+(1−α)δ) 1-γ(p+(1-α)δ) ≥1−γp−γδ≥2(1−γ)−1−γ2=32(1−γ). ≥ 1-γ p-γδ≥ 2(1-γ)- 1-γ2= 32(1-γ). Leveraging θδ>0θδ>0, the numerator is bounded from above: 1−γ(p+θδ) 1-γ(p+θδ) ≤1−γp=2(1−γ). ≤ 1-γ p=2(1-γ). Because the domain restriction ensures (1−α−θ)≤1(1-α-θ)≤ 1, we obtain the uniform bound for ℳ1M_1: J∗,(1)−J(1)(θ)‖∇θJ(1)(θ)‖2 J^*,(1)-J^(1)(θ) \| _θJ^(1)(θ) \|_2 ≤1⋅2(1−γ)32(1−γ)=43. ≤ 1· 2(1-γ) 32(1-γ)= 43. We repeat the exact procedure for ℳ2M_2. The optimal parameter for ℳ2M_2 is θ∗=αθ^*=α. The sub-optimality gap is: J∗,(2)−J(2)(θ) J^*,(2)-J^(2)(θ) =Rmax1−γ(p+(1−α)δ)−Rmax1−γ(p+(1−θ)δ) = R_ 1-γ(p+(1-α)δ)- R_ 1-γ(p+(1-θ)δ) =γRmax((p+(1−α)δ)−(p+(1−θ)δ))(1−γ(p+(1−α)δ))(1−γ(p+(1−θ)δ)) = γ R_ ((p+(1-α)δ)-(p+(1-θ)δ))(1-γ(p+(1-α)δ))(1-γ(p+(1-θ)δ)) =γRmax(θ−α)δ(1−γ(p+(1−α)δ))(1−γ(p+(1−θ)δ)). = γ R_ (θ-α)δ(1-γ(p+(1-α)δ))(1-γ(p+(1-θ)δ)). Dividing by the gradient norm for ℳ2M_2 yields: J∗,(2)−J(2)(θ)‖∇θJ(2)(θ)‖2 J^*,(2)-J^(2)(θ) \| _θJ^(2)(θ) \|_2 =(θ−α)1−γ(p+(1−θ)δ)1−γ(p+(1−α)δ). =(θ-α) 1-γ(p+(1-θ)δ)1-γ(p+(1-α)δ). The denominator bound remains identical to ℳ1M_1. For the numerator, since (1−θ)δ>0(1-θ)δ>0: 1−γ(p+(1−θ)δ) 1-γ(p+(1-θ)δ) ≤1−γp=2(1−γ). ≤ 1-γ p=2(1-γ). The parameter restriction θ∈[α,1−α]θ∈[α,1-α] enforces (θ−α)≤1−2α<1(θ-α)≤ 1-2α<1. Substituting these bounds yields the limit for ℳ2M_2: J∗,(2)−J(2)(θ)‖∇θJ(2)(θ)‖2 J^*,(2)-J^(2)(θ) \| _θJ^(2)(θ) \|_2 ≤(1−2α)⋅2(1−γ)32(1−γ)<43. ≤(1-2α)· 2(1-γ) 32(1-γ)< 43. The preceding computations establish J∗,(i)−J(i)(θ)≤43‖∇θJ(i)(θ)‖2,i∈1,2. J^*,(i)-J^(i)(θ)≤ 43\| _θJ^(i)(θ)\|_2, 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−α] =[α,1-α], we must verify that Assumption 3.2 also holds when projection clips the update. The optimal parameters are θ∗,(1)=1−αθ^*,(1)=1-α and θ∗,(2)=αθ^*,(2)=α. For both instances, the gradient points toward the corresponding optimum, so projection gives ‖Gη(i)(θ)‖2=min‖∇θJ(i)(θ)‖2,|θ∗,(i)−θ|η. \|G_η^(i)(θ)\|_2= \\| _θJ^(i)(θ)\|_2, |θ^*,(i)-θ|η \. If the update is not clipped, the generalized mapping equals the gradient, and the previously established inequality J∗,(i)−J(i)(θ)≤43‖∇θJ(i)(θ)‖2J^*,(i)-J^(i)(θ)≤ 43\| _θJ^(i)(θ)\|_2 applies directly. Otherwise, the projected update reaches θ∗,(i)θ^*,(i), yielding |θ∗,(i)−θ|=η‖Gη(i)(θ)‖2|θ^*,(i)-θ|=η\|G_η^(i)(θ)\|_2. By the mean value theorem, J∗,(i)−J(i)(θ) J^*,(i)-J^(i)(θ) ≤supθ′∈Θ‖∇θJ(i)(θ′)‖2|θ∗,(i)−θ| ≤ _θ ∈ \| _θJ^(i)(θ )\|_2|θ^*,(i)-θ| =ηγδRmax[1−γ(p+(1−α)δ)]2‖Gη(i)(θ)‖2. = ηγδ R_ [1-γ(p+(1-α)δ)]^2\|G_η^(i)(θ)\|_2. The regularity constants established above, C1=1/αC_1=1/α and LS=1/α2L_S=1/α^2, give L=2Rmax/[α2(1−γ)2L=2R_ /[α^2(1-γ)^2]. Using η≤1/Lη≤ 1/L, 1−γ(p+(1−α)δ)≥32(1−γ)1-γ(p+(1-α)δ)≥ 32(1-γ), and γδ≤(1−γ)/2γδ≤(1-γ)/2, the coefficient in the last display is at most α2(1−γ)/9≤4/3α^2(1-γ)/9≤ 4/3. Thus, J∗,(i)−J(i)(θ)≤43‖Gη(i)(θ)‖2J^*,(i)-J^(i)(θ)≤ 43\|G_η^(i)(θ)\|_2 also holds when projection clips the update. At the optimum, both sides vanish. Consequently, Assumption 3.2 holds throughout Θ , for every 0<η≤1/L0<η≤ 1/L, with ψ=0ψ=0 and χ=4/3χ=4/3. Part I: 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ϵ4ε. In instance ℳ1M_1, the optimal parameter is θ∗=1−α>1/2θ^*=1-α>1/2. The algorithm outputs a highly sub-optimal policy if it incorrectly favors action a1a_1, which occurs when θ≤1/2θ≤ 1/2. We evaluate the sub-optimality gap for ℳ1M_1 given θ≤1/2θ≤ 1/2 to find a strict lower bound. From the previous derivation, the gap is: J∗,(1)−J(1)(θ) J^*,(1)-J^(1)(θ) =γRmax(1−α−θ)δ(1−γ(p+(1−α)δ))(1−γ(p+θδ)). = γ R_ (1-α-θ)δ(1-γ(p+(1-α)δ))(1-γ(p+θδ)). To lower-bound this gap, we lower-bound the numerator and upper-bound the denominator. Because θ≤1/2θ≤ 1/2, the term (1−α−θ)(1-α-θ) is bounded below by (1/2−α)(1/2-α). Furthermore, since we established the condition γ≥1/2γ≥ 1/2 to ensure valid transition probabilities, we substitute γ=1/2γ=1/2 to strictly lower-bound the numerator and remove its dependence on γ: γRmax(1−α−θ)δ γ R_ (1-α-θ)δ ≥12Rmax(12−α)δ=Rmax(1−2α)δ4. ≥ 12R_ ( 12-α )δ= R_ (1-2α)δ4. For the denominator, since θδ≥0θδ≥ 0 and (1−α)δ≥0(1-α)δ≥ 0, the effective horizon terms are strictly upper-bounded by the baseline effective horizon 1−γp=2(1−γ)1-γ p=2(1-γ): (1−γ(p+(1−α)δ))(1−γ(p+θδ)) (1-γ(p+(1-α)δ))(1-γ(p+θδ)) ≤(2(1−γ))(2(1−γ))=4(1−γ)2. ≤(2(1-γ))(2(1-γ))=4(1-γ)^2. Combining these bounds, the sub-optimality gap for any parameter θ≤1/2θ≤ 1/2 is bounded from below: J∗,(1)−J(1)(θ) J^*,(1)-J^(1)(θ) ≥Rmax(1−2α)δ44(1−γ)2=Rmax(1−2α)δ16(1−γ)2. ≥ R_ (1-2α)δ44(1-γ)^2= R_ (1-2α)δ16(1-γ)^2. To enforce that this misidentification penalty is at least 4ϵ4ε, we equate this lower bound to 4ϵ4ε and solve for the perturbation parameter δ: Rmax(1−2α)δ16(1−γ)2 R_ (1-2α)δ16(1-γ)^2 =4ϵ⟹δ=64ϵ(1−γ)2Rmax(1−2α). =4ε δ= 64ε(1-γ)^2R_ (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γδ≤ 1-γ2γ, the target accuracy ϵε must be sufficiently small: 64ϵ(1−γ)2Rmax(1−2α)≤1−γ2γ⟹ϵ≤Rmax(1−2α)128γ(1−γ). 64ε(1-γ)^2R_ (1-2α)≤ 1-γ2γ ε≤ R_ (1-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 ℳiM_i, i∈1,2i∈\1,2\, collects a possibly random number of trajectories N_A, and subsequently outputs a parameter estimate θ^∈Θ θ∈ . The algorithm is not informed whether the underlying environment is ℳ1M_1 or ℳ2M_2, 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 ,ℳi[J∗,(i)−J(i)(θ^)]≤ϵ,i∈1,2, _A,M_i [J^*,(i)-J^(i)( θ) ]≤ε, i∈\1,2\, where J∗,(i)=maxθ∈ΘJ(i)(θ)J^*,(i)= _θ∈ J^(i)(θ). We define the worst-case expected trajectory budget as n:=maxi∈1,2,ℳi[N]. n:= _i∈\1,2\E_A,M_i[N_A]. We may assume that n<∞n<∞, since otherwise the claimed lower bound holds trivially. Using the suboptimality bound derived in Part I, any output θ^<1/2 θ<1/2 under ℳ1M_1 incurs a gap of at least 4ϵ4ε. Therefore, ϵ ε ≥,ℳ1[J∗,(1)−J(1)(θ^)] _A,M_1 [J^*,(1)-J^(1)( θ) ] ≥4ϵℙ,ℳ1(θ^<12), ≥ 4ε\,P_A,M_1 ( θ< 12 ), which implies: ℙ,ℳ1(θ^<12)≤14. _A,M_1 ( θ< 12 )≤ 14. By symmetric reasoning under ℳ2M_2, any output θ^≥1/2 θ≥ 1/2 incurs a gap of at least 4ϵ4ε, yielding, ℙ,ℳ2(θ^≥12)≤14. _A,M_2 ( θ≥ 12 )≤ 14. Summing these error probabilities gives: ℙ,ℳ1(θ^<12)+ℙ,ℳ2(θ^≥12)≤12. _A,M_1 ( θ< 12 )+P_A,M_2 ( θ≥ 12 )≤ 12. Let ℙ,ℳ1P_A,M_1 and ℙ,ℳ2P_A,M_2 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, and its final output θ θ. Interpreting θ^≥1/2 θ≥ 1/2 as selecting ℳ1M_1, Le Cam’s inequality gives: ℙ,ℳ1(θ^<12)+ℙ,ℳ2(θ^≥12) _A,M_1 ( θ< 12 )+P_A,M_2 ( θ≥ 12 ) ≥1−dTV(ℙ,ℳ1,ℙ,ℳ2). ≥ 1-d_TV\! (P_A,M_1,P_A,M_2 ). Consequently, the total variation distance must be at least 1/21/2. Applying Pinsker’s inequality, we obtain, 12 12 ≤dTV(ℙ,ℳ1,ℙ,ℳ2) ≤ d_TV\! (P_A,M_1,P_A,M_2 ) ≤12DKL(ℙ,ℳ1∥ℙ,ℳ2), ≤ 12D_KL\! (P_A,M_1\, \|\,P_A,M_2 ), and hence: DKL(ℙ,ℳ1∥ℙ,ℳ2)≥12. D_KL\! (P_A,M_1\, \|\,P_A,M_2 )≥ 12. 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 ℳ1M_1 and ℳ2M_2. Consequently, only the environment transition kernels contribute to the conditional KL divergence. We first bound the divergence contributed by a single transition. Since s¯ s is absorbing and possesses identical transition dynamics in both instances, DKL(P(1)(⋅∣s¯,a)∥P(2)(⋅∣s¯,a))=0. D_KL\! (P^(1)(· s,a)\, \|\,P^(2)(· s,a) )=0. At the active state s, the Bernoulli parameters under (ℳ1,ℳ2)(M_1,M_2) are (p+δ,p)(p+δ,p) for a0a_0 and (p,p+δ)(p,p+δ) for a1a_1. Using the standard inequality dKL(x∥y)≤(x−y)2/[y(1−y)]d_KL(x\|y)≤(x-y)^2/[y(1-y)], we obtain, dKL(p+δ∥p) d_KL(p+δ\|p) ≤δ2p(1−p), ≤ δ^2p(1-p), dKL(p∥p+δ) d_KL(p\|p+δ) ≤δ2(p+δ)(1−p−δ). ≤ δ^2(p+δ)(1-p-δ). Recall that p=(2γ−1)/γp=(2γ-1)/γ, γ≥2/3γ≥ 2/3, and δ≤(1−γ)/(2γ)δ≤(1-γ)/(2γ). These conditions imply: p≥12,1−p=1−γ,1−p−δ≥1−γ2γ. p≥ 12, 1-p= 1-γ, 1-p-δ≥ 1-γ2γ. Thus, both variance terms are bounded below by (1−γ)/(4γ)(1-γ)/(4γ), yielding, maxa∈a0,a1DKL(P(1)(⋅∣s,a)∥P(2)(⋅∣s,a))≤4γδ21−γ≤4δ21−γ. _a∈\a_0,a_1\D_KL\! (P^(1)(· s,a)\, \|\,P^(2)(· s,a) )≤ 4γδ^21-γ≤ 4δ^21-γ. This bound holds uniformly over the selected action. Next, we bound the number of informative transitions within each trajectory. Let HjH_j denote the number of observed transitions in trajectory j, and define: Tj:=∑t=0Hj−1sj,t=s, T_j:= _t=0^H_j-11_\s_j,t=s\, where sj,ts_j,t and aj,ta_j,t denote the state and action at time t of trajectory j. Thus, TjT_j counts the observed transitions from the active state. Each trajectory starts at s and follows the independent geometric termination protocol. We set Tj=0T_j=0 when trajectory j is not collected. Let ℱj−1F_j-1 denote the history immediately before trajectory j, including the algorithm’s decision whether to collect it. In particular, N≥j\N_A≥ j\ is ℱj−1F_j-1-measurable. On this event, the conditional probability of remaining in s after any active transition is at most p+δp+δ, regardless of the selected action. The geometric termination mechanism can only reduce the number of observed active transitions. Consequently, ℙ,ℳ1(Tj>t∣ℱj−1) _A,M_1 (T_j>t _j-1 ) ≤(p+δ)t,t≥0, ≤(p+δ)^t, t≥ 0, ,ℳ1[Tj∣ℱj−1] _A,M_1 [T_j _j-1 ] ≤∑t=0∞(p+δ)t ≤ _t=0^∞(p+δ)^t =11−p−δ≤2γ1−γ≤21−γ. = 11-p-δ≤ 2γ1-γ≤ 21-γ. The conditional expectation bound also holds when the trajectory is not collected, since then Tj=0T_j=0. For a history at which trajectory j is collected, let Qi,j(⋅∣ℱj−1)Q_i,j(· _j-1) denote its conditional law under ℳiM_i, and define: Kj:=DKL(Q1,j(⋅∣ℱj−1)∥Q2,j(⋅∣ℱj−1)). K_j:=D_KL\! (Q_1,j(· _j-1)\, \|\,Q_2,j(· _j-1) ). We set Kj=0K_j=0 at histories where trajectory j is not collected. Applying the conditional chain rule within a collected trajectory gives: Kj K_j =,ℳ1[∑t=0Hj−1DKL(P(1)(⋅∣sj,t,aj,t)∥P(2)(⋅∣sj,t,aj,t))|ℱj−1] =E_A,M_1 [ _t=0^H_j-1D_KL\! (P^(1)(· s_j,t,a_j,t)\, \|\,P^(2)(· s_j,t,a_j,t) )\, |\,F_j-1 ] ≤4δ21−γ,ℳ1[Tj∣ℱj−1] ≤ 4δ^21-γE_A,M_1 [T_j _j-1 ] ≤8δ2(1−γ)2. ≤ 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(ℙ,ℳ1∥ℙ,ℳ2) D_KL\! (P_A,M_1\, \|\,P_A,M_2 ) =∑j=1∞,ℳ1[N≥jKj] = _j=1^∞E_A,M_1 [1_\N_A≥ j\K_j ] ≤8δ2(1−γ)2∑j=1∞ℙ,ℳ1(N≥j) ≤ 8δ^2(1-γ)^2 _j=1^∞P_A,M_1(N_A≥ j) =8δ2(1−γ)2,ℳ1[N] = 8δ^2(1-γ)^2E_A,M_1[N_A] ≤8nδ2(1−γ)2. ≤ 8nδ^2(1-γ)^2. 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, 12≤DKL(ℙ,ℳ1∥ℙ,ℳ2)≤8nδ2(1−γ)2. 12≤ D_KL\! (P_A,M_1\, \|\,P_A,M_2 )≤ 8nδ^2(1-γ)^2. This yields the trajectory budget requirement: n≥(1−γ)216δ2. n≥ (1-γ)^216δ^2. Substituting the perturbation parameter selected in Part I, δ=64ϵ(1−γ)2Rmax(1−2α), δ= 64ε(1-γ)^2R_ (1-2α), we obtain: n n ≥(1−γ)216Rmax2(1−2α)24096ϵ2(1−γ)4 ≥ (1-γ)^216 R_ ^2(1-2α)^24096ε^2(1-γ)^4 =Rmax2(1−2α)265536ϵ2(1−γ)2. = R_ ^2(1-2α)^265536ε^2(1-γ)^2. In particular, fixing α=1/4α=1/4 gives: maxi∈1,2,ℳi[N]≥Rmax2262144ϵ2(1−γ)2. _i∈\1,2\E_A,M_i[N_A]≥ R_ ^2262144ε^2(1-γ)^2. Thus, for γ∈[2/3,1)γ∈[2/3,1) and 0<ϵ≤Rmax256γ(1−γ), 0<ε≤ R_ 256γ(1-γ), any algorithm guaranteeing ϵε-optimality on both possible unknown instances requires a worst-case expected number of trajectories satisfying n=Ω(Rmax2(1−γ)2ϵ2). n= \! ( R_ ^2(1-γ)^2ε^2 ). This establishes the claimed trajectory complexity lower bound for adaptive algorithms, including algorithms whose number of collected trajectories is random. ∎ Appendix H Technical Lemmas Lemma H.1. Let :[0,1]→ℝd G:[0,1] ^d be continuous on [0,1][0,1]. If, for any u∈[0,1)u∈[0,1), lim supϵ↓0‖(u+ϵ)−(u)‖ϵ≤C, _ε 0 \| G(u+ε)- G(u)\|ε≤ C, then ‖(1)−(0)‖≤C\| G(1)- G(0)\|≤ C. Proof. If (1)=(0) G(1)= G(0) there is nothing to prove, so assume ‖(1)−(0)‖>0\| G(1)- G(0)\|>0. By contradiction, suppose ‖(1)−(0)‖>C\| G(1)- G(0)\|>C and choose c∈ℝc such that ‖(1)−(0)‖>c>C\| G(1)- G(0)\|>c>C. Let ≔(1)−(0)‖(1)−(0)‖, v G(1)- G(0)\| G(1)- G(0)\|, and define f:[0,1]→ℝf:[0,1] as f(u)≔⊤(u)−cuf(u) v G(u)-cu. Then, f(1)−f(0)=‖(1)−(0)‖−c>0f(1)-f(0)=\| G(1)- G(0)\|-c>0. Since f is continuous on [0,1][0,1], it attains its minimum at some u⋆∈[0,1]u ∈[0,1]. Since f(1)>f(0)f(1)>f(0), u⋆<1u <1. For sufficiently small ϵε, f(u⋆+ϵ)−f(u⋆)≥0f(u +ε)-f(u )≥ 0, so: lim supϵ↓0f(u⋆+ϵ)−f(u⋆)ϵ≥0. _ε 0 f(u +ε)-f(u )ε≥ 0. On the other hand, since ‖=1\| v\|=1, lim supϵ↓0f(u⋆+ϵ)−f(u⋆)ϵ _ε 0 f(u +ε)-f(u )ε =lim supϵ↓0⊤((u⋆+ϵ)−(u⋆))ϵ−c = _ε 0 v ( G(u +ε)- G(u ))ε-c ≤lim supϵ↓0‖(u⋆+ϵ)−(u⋆)‖ϵ−c ≤ _ε 0 \| G(u +ε)- G(u )\|ε-c ≤C−c<0. ≤ C-c<0. ∎ Lemma H.2 (Recurrence). Let xkk=0∞\x_k\_k=0^∞ be a non-negative sequence satisfying the following recurrence relation for all k≥0k≥ 0: xk+1≤xk−minaxk2,bxk+e, x_k+1≤ x_k- \ax_k^2,bx_k \+e, where a>0a>0, b>0b>0, and e>0e>0. For a given target accuracy ϵ>0ε>0, define the effective contraction rate ρϵ≔minaϵ,b _ε \aε,b\. Assume the algorithmic parameters are configured such that ρϵ∈(0,1) _ε∈(0,1). If the noise term e satisfies e≤aϵ22e≤ a ε^22 and e≤bϵ2e≤ b ε2, then, it suffices to choose a number of iterations K satisfying: K≥max1aϵ,1blog+(2x0ϵ), K≥ \ 1aε, 1b \ _+ ( 2x_0ε ), where log+(a)≔logmax1,a _+(a) \1,a\, to ensure that xk≤ϵx_k≤ε for every k≥Kk≥ K. Proof. We first establish that the sequence remains within the target neighborhood once it reaches it. By the stated noise conditions, we have: e≤minaϵ22,bϵ2=ρϵϵ2. e≤ \ aε^22, bε2 \= _ε2. Suppose that xk≤ϵx_k≤ε. If xk≤ϵ/2x_k≤ε/2, dropping the non-negative descent term yields: xk+1≤xk+e≤ϵ2+ρϵϵ2≤ϵ, x_k+1≤ x_k+e≤ ε2+ _ε2≤ε, where the final inequality follows from ρϵ∈(0,1) _ε∈(0,1). Conversely, if ϵ/2<xk≤ϵε/2<x_k≤ε, we lower-bound the descent term as follows: minaxk2,bxk \ax_k^2,bx_k\ =xkminaxk,b =x_k \ax_k,b\ ≥xkminaϵ2,b ≥ x_k \ aε2,b \ ≥ρϵ2xk. ≥ _ε2x_k. Substituting this bound into the recurrence gives: xk+1 x_k+1 ≤(1−ρϵ2)xk+e ≤ (1- _ε2 )x_k+e ≤(1−ρϵ2)ϵ+ρϵϵ2=ϵ. ≤ (1- _ε2 )ε+ _ε2=ε. Consequently, the target neighborhood [0,ϵ][0,ε] is invariant: if xk≤ϵx_k≤ε at any iteration, then xj≤ϵx_j≤ε for every j≥kj≥ k. We now evaluate the sequence using a hitting-time argument. Let Tϵ:=infk≥0∣xk≤ϵT_ε:= \k≥ 0 x_k≤ε\ denote the first iteration at which the sequence reaches the target accuracy, with inf∅:=+∞ :=+∞. If x0≤ϵx_0≤ε, the invariance established above directly guarantees the claim for every iteration. Assume therefore that x0>ϵx_0>ε. By the definition of the hitting time, xk>ϵx_k>ε for every k<Tϵk<T_ε. This allows us to lower-bound the descent rate prior to reaching the target neighborhood. For any k<Tϵk<T_ε, factoring out xkx_k yields: minaxk2,bxk=xkminaxk,b≥xkminaϵ,b. \ax_k^2,bx_k \=x_k \ax_k,b \≥ x_k \aε,b \. Substituting the definition of the effective contraction rate ρϵ≔minaϵ,b _ε \aε,b\ into the original inequality yields a standard linear recurrence: xk+1≤(1−ρϵ)xk+e. x_k+1≤(1- _ε)x_k+e. To set the hyperparameters so that the target xK≤ϵx_K≤ε is reached, we partition the error budget equally, requiring the asymptotic bias to be bounded by ϵ2 ε2 and the transient term to be bounded by ϵ2 ε2. Bounding the asymptotic bias requires eρϵ≤ϵ2 e _ε≤ ε2, which rearranges to e≤ρϵϵ2e≤ _ε ε2. Because ρϵ _ε evaluates to the minimum of two regimes, this condition must hold for both possible values. If ρϵ=aϵ _ε=aε, the constraint dictates e≤aϵ22e≤ a ε^22. If ρϵ=b _ε=b, the constraint dictates e≤bϵ2e≤ b ε2. Satisfying both of these stated hyperparameter conditions ensures the asymptotic bias remains strictly bounded by ϵ2 ε2. Consequently, as long as xk≥ϵ>0x_k≥ε>0, we can rewrite the linear recurrence as: xk+1−ϵ2≤(1−ρϵ)(xk−ϵ2). x_k+1- ε2≤(1- _ε) (x_k- ε2 ). For any integer K<TϵK<T_ε, unrolling this recursive inequality over K steps yields: xK x_K ≤ϵ2+(1−ρϵ)K(x0−ϵ2) ≤ ε2+(1- _ε)^K (x_0- ε2 ) ≤ϵ2+exp(−ρϵK)x0, ≤ ε2+ (- _εK)x_0, where the final bound applies the standard logarithmic inequality 1−x≤exp(−x)1-x≤ (-x), valid for ρϵ∈(0,1) _ε∈(0,1). Bounding the remaining transient term by ϵ/2ε/2 requires: K K ≥1ρϵlog+(2x0ϵ) ≥ 1 _ε _+ ( 2x_0ε ) =max1aϵ,1blog+(2x0ϵ). = \ 1aε, 1b \ _+ ( 2x_0ε ). Fix an integer K satisfying this bound. If Tϵ>KT_ε>K, the preceding estimate gives xK≤ϵx_K≤ε, contradicting the definition of TϵT_ε. Hence, Tϵ≤KT_ε≤ K. By the invariance of the target neighborhood, it follows that xk≤ϵx_k≤ε for every k≥Kk≥ K, completing the proof. ∎ Appendix I Experimental Details We evaluate the empirical sample efficiency of the LVR-PG framework on CartPole-v1, Swimmer-v4, HalfCheetah-v4, 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 (i) 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 44. The continuous-control tasks use Gaussian policies with two hidden layers of width 3232. 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 1010 episodes, with evaluations every 1010 collected training trajectories and at the final updated policy. 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 396.05±34.56396.05± 34.56 481.90±7.85481.90± 7.85 417.34±37.96417.34± 37.96 482.39±5.49482.39± 5.49 380.03±39.46380.03± 39.46 Swimmer 24.19±6.1524.19± 6.15 40.86±7.9440.86± 7.94 26.39±5.4626.39± 5.46 33.90±13.2833.90± 13.28 26.22±1.0126.22± 1.01 Half-Cheetah 13.49±30.1613.49± 30.16 105.76±51.57105.76± 51.57 24.08±32.6724.08± 32.67 55.82±41.7655.82± 41.76 87.67±23.3187.67± 23.31 Hopper 201.90±21.68201.90± 21.68 369.94±89.62369.94± 89.62 233.65±28.36233.65± 28.36 309.13±44.92309.13± 44.92 368.81±23.97368.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 500500 5050 55 10−210^-2 – Swimmer-v4 500500 100100 1010 10−310^-3 11 HalfCheetah-v4 100100 256256 1616 10−410^-4 0.3 0.3 Hopper-v4 100100 256256 1616 10−410^-4 0.30.3 Algorithms We consider DEF-STORM-PG (α>0α>0, p=0p=0), DEF-PAGE-PG (α=0α=0, p>0p>0), and a hybrid configuration (α>0α>0, p>0p>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ξ=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. Table 6: Algorithmic settings for the return comparisons. (∗The hybrid uses p=0.5p=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 Refresh probability p – 00 0.50.5 0.1∗0.1^* – Recursive parameter α – 0.90.9 00 0.90.9 0.90.9 Defensive parameter ξ – 0.50.5 0.50.5 0.50.5 – 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 (⊂ℝ4S ^4) and two discrete actions (=0,1A=\0,1\). Figure 5 compares the five algorithms using the settings in Tables 5 and 6. 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. DEF-STORM-PG and LVR-PG reach returns close to the maximum episodic return of 500500 after approximately 10310^3 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. I.2 Swimmer-v4 Swimmer-v4 is a locomotion task with an eight-dimensional state space (⊂ℝ8S ^8) and a two-dimensional action space (⊂ℝ2A ^2). The policy controls an articulated swimmer moving through a fluid environment. 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 2727. I.3 HalfCheetah-v4 HalfCheetah-v4 has a 1717-dimensional state space (⊂ℝ17S ^17) and a six-dimensional action space (⊂ℝ6A ^6). The policy controls the locomotion of an articulated agent. 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 10510^5 trajectories. I.4 Hopper-v4 Hopper-v4 is a locomotion task with an 1111-dimensional state space (⊂ℝ11S ^11) and a three-dimensional action space (⊂ℝ3A ^3). 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×1042× 10^4 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 mkm_k trajectories, let k,ig_k,i denote the unweighted, baseline-free GPOMDP contribution evaluated at the current policy parameters. We compute the trace of their sample covariance, ar^(∇^†J(k)) Var ( ∇ _ θJ( θ_k) ) =1mk−1∑i=1mk‖k,i−¯k‖22, = 1m_k-1 _i=1^m_k \|g_k,i- g_k \|_2^2, ¯k g_k =1mk∑i=1mkk,i. = 1m_k _i=1^m_kg_k,i. We plot the mean of log10ar^(∇^†J(k)) _10 Var ( ∇ _ θJ( θ_k) ) across independent runs. The contributions are evaluated at the 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. Figure 9: Per-trajectory gradient-variability diagnostic on CartPole-v1 over 5×1035× 10^3 training trajectories. Values are shown on a base-1010 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 We examine the sensitivity of DEF-PAGE-PG to p∈0.1,0.5,0.9p∈\0.1,0.5,0.9\ and of DEF-STORM-PG to α∈0.1,0.5,0.9α∈\0.1,0.5,0.9\. Both studies use the CartPole-v1 environment with the configuration presented in Tables 5 and 6. Figure 10: Hyperparameter ablations on CartPole-v1 over 10410^4 training trajectories. Left: Refresh probability p∈0.1,0.5,0.9p∈\0.1,0.5,0.9\ for DEF-PAGE-PG. Right: Recursive-update parameter α∈0.1,0.5,0.9α∈\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.5p=0.5 and p=0.9p=0.9 reach returns close to 500500, whereas p=0.1p=0.1 settles near 400400. The configuration p=0.9p=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α=0.9 rapidly reaches returns close to 500500, while α=0.5α=0.5 requires substantially more trajectories, and α=0.1α=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−α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α∈\0.01,0.5,0.9\ and p∈0.05,0.3,0.5p∈\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. Panel (a): Normalized AUC.Refresh Probability (p)Momentum parameter (α)0.050.050.30.30.50.50.010.010.50.50.90.912.712.7±2.4± 2.4212.8212.8±131.3± 131.3379.3379.3±60.9± 60.9343.9343.9±48.8± 48.8422.3422.3±26.5± 26.5438.8438.8±20.1± 20.1415.1415.1±55.3± 55.3399.4399.4±95.9± 95.9453.5453.5±7.2± 7.2Panel (b): Last-Iterate ReturnRefresh Probability (p)Momentum parameter (α)0.050.050.30.30.50.50.010.010.50.50.90.99.39.3±0.2± 0.2129.1129.1±186.3± 186.3336.4336.4±202.4± 202.4381.9381.9±176.2± 176.2500.0500.0±0.0± 0.0490.3490.3±19.0± 19.0500.0500.0±0.0± 0.0422.8422.8±151.3± 151.3500.0500.0±0.0± 0.0 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.05p=0.05, increasing α raises the mean AUC from 12.712.7 to 379.3379.3 and the mean terminal return from 9.39.3 to 336.4336.4. More frequent refreshes substantially improve the low-α configuration. Three configurations, (0.5,0.3)(0.5,0.3), (0.01,0.5)(0.01,0.5), and (0.9,0.5)(0.9,0.5), attain a mean terminal return of 500500 at the displayed precision, while their mean AUC values differ. The configuration (α,p)=(0.9,0.5)(α,p)=(0.9,0.5) achieves the largest mean AUC in the grid, 453.5±7.2453.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. I.8 Computational Resources All the experiments were run on a 2023 14-inch MacBook Pro equipped with an Apple M2 Pro chip and 16GB16~GB of RAM.