PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Variance-Reduced Policy Gradient

Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, Marcello Restelli

arXiv:1806.05618v1cs.LGstat.ML

TL;DR

Policy-gradient methods face non-concave objectives, approximate full gradients, and policy-dependent sampling, making direct adaptation of SVRG nontrivial. The paper proposes SVRPG, which uses importance weighting to preserve unbiased gradient correction and provides convergence guarantees under stated assumptions. It also discusses practical variants and evaluates them on continuous reinforcement-learning tasks.

  • Problem

    Adapting SVRG to policy gradients requires handling non-concave objectives, approximate full-gradient computation, and non-stationary sampling induced by changing policies.

  • Method

    SVRPG adapts SVRG to policy gradients and uses importance weighting to preserve the unbiasedness of the corrected gradient.

  • Results

    SVRPG has convergence guarantees under the stated assumptions, including an O(1/T) iteration dependence and error terms associated with full-gradient approximation and importance weighting.

  • Takeaways & Limitations

    Importance weighting can address policy-dependent sampling while preserving unbiased corrected gradients, and practical SVRPG variants were evaluated on continuous reinforcement-learning tasks.

  • Takeaways & Limitations

    Plain policy-gradient estimators have high variance, and increasing batch sizes is costly because samples require interaction with the environment.

Abstract

from arXiv · show

In this paper, we propose a novel reinforcement- learning algorithm consisting in a stochastic variance-reduced version of policy gradient for solving Markov Decision Processes (MDPs). Stochastic variance-reduced gradient (SVRG) methods have proven to be very successful in supervised learning. However, their adaptation to policy gradient is not straightforward and needs to account for I) a non-concave objective func- tion; II) approximations in the full gradient com- putation; and III) a non-stationary sampling pro- cess. The result is SVRPG, a stochastic variance- reduced policy gradient algorithm that leverages on importance weights to preserve the unbiased- ness of the gradient estimate. Under standard as- sumptions on the MDP, we provide convergence guarantees for SVRPG with a convergence rate that is linear under increasing batch sizes. Finally, we suggest practical variants of SVRPG, and we empirically evaluate them on continuous MDPs.

1. Introduction

The paper adapts stochastic variance reduction to policy gradients, where non-concavity, approximate full gradients, and policy-dependent sampling complicate direct use of supervised-learning methods. It proposes SVRPG and establishes an O(1/T) convergence dependence under suitable conditions.

  • Motivation: Policy-gradient sampling is costly because data must be collected through interaction with an initially unknown environment.This makes variance control especially relevant when comparing stochastic optimization methods.
  • Motivation: Policy-gradient reinforcement learning must address non-concave objectives, unavoidable gradient approximations, and sampling distributions that change with policy parameters.These difficulties distinguish reinforcement-learning optimization from standard finite-sum supervised-learning settings.
  • Contribution: SVRPG is introduced as a stochastic variance-reduced policy-gradient method designed to address these reinforcement-learning difficulties.The method is presented as a policy-gradient variant of SVRG.
  • Contribution: O(1/T) is the stated convergence-rate dependence for SVRPG under the paper’s assumptions and suitable parameter choices.The convergence guarantee is given after T iterations.

2. Preliminaries

The preliminaries formulate continuous-state, continuous-action reinforcement learning as an MDP and describe policy-gradient optimization alongside stochastic variance-reduced gradient methods. They emphasize high estimator variance, changing policy-induced sampling distributions, and SVRG’s variance-control mechanism.

  • Policy Gradient: An MDP is specified by state and action spaces, transitions, rewards, discounting, and an initial-state distribution, with behavior represented by a policy.The paper considers continuous state and action spaces in this formulation.
  • Policy Gradient: Plain policy-gradient analysis includes a random episode duration, with the optimal policy reaching an absorbing target state in fewer than H steps.This condition is distinguished from a finite-horizon problem with a non-stationary optimal policy.
  • Policy Gradient: Policy-gradient methods optimize differentiable parametrized policies by gradient ascent on expected performance.The policy class is written as Πθ = {πθ : θ ∈ R^d}.
  • Policy Gradient: The gradient distribution is induced by the current policy, so online updates require resampling trajectories or using importance weighting as the policy changes.This creates nonstationarity in the sampling process.
  • Policy Gradient: High variance is the main limitation of plain policy-gradient estimators, while increasing batch sizes is costly because samples require environment interaction.Baselines are used for variance reduction but must themselves be estimated from data.
  • Stochastic Variance-Reduced Gradient: The SVRG setup maximizes a finite-sum objective whose component functions are commonly assumed smooth and concave.The paper notes that its optimization formulation is a maximization problem rather than the classical minimization form.
  • Stochastic Variance-Reduced Gradient: SVRG alternates full-gradient snapshots with corrected stochastic updates, reusing past gradient computations to reduce sampling variance.Snapshots are taken every m = O(N) iterations, and the corrected gradient is unbiased.
  • Stochastic Variance-Reduced Gradient: O(1/T) is the stated stochastic-gradient convergence rate under the non-concave smooth-objective setting, requiring T = O(1/ϵ^2) iterations to reach the given gradient criterion.SVRG is reported to achieve the same O(1/T) rate as full-gradient ascent in this setting when the output is selected appropriately.

3. SVRG in Reinforcement Learning

Applying SVRG directly to reinforcement learning is difficult because trajectories are costly to collect, the dataset is effectively infinite, sampling is non-stationary, and objectives are non-concave. SVRPG addresses these issues with an approximate snapshot gradient and importance-weighted corrections.

  • Motivation: RL trajectories must be collected through environment interaction, making variance reduction important for limiting sampling costs.Unlike supervised learning, samples are not fixed in advance and must be gathered after policy changes.
  • Challenges: Direct SVRG application fails because RL uses an infinite trajectory dataset and a sampling distribution controlled by changing policy parameters.The objective is an expectation over trajectory density pθ(τ), while policy updates alter that density over time.
  • SVRPG: SVRPG uses a snapshot gradient from trajectories sampled under a snapshot policy and corrects subsequent estimates with importance weighting.The correction addresses distribution shift while retaining an on-policy algorithm overall.
  • Estimator properties: The full gradient and correction term have the same expected value, supporting an unbiased SVRPG gradient estimator.Mini-batches of size B are used to average the importance-weighted correction.
  • Estimator properties: SVRPG’s variance properties hold for both REINFORCE and G(PO)MDP estimators, enabling more parameter updates without additional asymptotic variance.The randomized return value is used as a theoretical tool rather than affecting online learning.

4. Convergence Guarantees of SVRPG

The convergence analysis extends non-concave SVRG to SVRPG under smoothness, bounded gradient-estimator variance, and bounded importance-weight variance assumptions. The resulting bound separates optimization, full-gradient approximation, and importance-weighting effects.

  • Analysis: SVRPG convergence is analyzed for REINFORCE and G(PO)MDP estimators using non-concave SVRG techniques.The analysis requires additional assumptions because each of the three RL-specific challenges can prevent convergence.
  • Assumptions: The objective is assumed L-smooth, with derivative conditions sufficient for common Gaussian and softmax policy classes.This addresses the non-concavity challenge in the convergence proof.
  • Assumptions: The analysis assumes bounded variance for the full-gradient estimator and bounded variance for importance weights.These assumptions control errors from approximate snapshot gradients and non-stationary sampling.
  • Guarantee: O(1/T) is the optimization term in the convergence bound, while O(1/N) reflects full-gradient approximation and O(1/B) reflects importance weighting.The constants depend on problem quantities and the step size and epoch length.
  • Implications: Asymptotic convergence requires batch size N and mini-batch size B to increase over time, although sufficiently large fixed values can be practical.The paper also gives an error-complexity expression involving B, N, m, and ϵ.

5. Remarks on SVRPG

The paper proposes practical choices and variants for SVRPG’s step size, epoch length, and importance weighting. These methods target the computational cost and variance trade-offs identified by the convergence analysis.

  • Practical variants: The practical section introduces automatic selection of step size α and epoch length m, plus a variance-reduction variant for importance weights.The importance-weight variant lacks theoretical guarantees but is reported to outperform baseline SVRPG empirically.
  • Practical implementation: The practical implementation replaces a redundant snapshot correction with an approximate full-gradient update using the N snapshot trajectories.This avoids wasting B trajectories when the correction term is zero at the start of an epoch.
  • Meta-parameters: Small m reduces importance-weight variance but requires frequent full-gradient computations, whereas large m can move the policy far from its snapshot.The authors jointly select α and m to balance these effects.
  • Adaptive updates: ADAM is incorporated to adapt update sizes separately for snapshot full-gradient updates and corrected sub-iterations.The two estimators use different trajectory counts and have different variance scales.
  • Adaptive updates: The adaptive epoch-length rule takes a new snapshot when corrected sub-iteration updates become noisier than the full-gradient update.Batch sizes are included to balance update quality against trajectory-collection cost.
  • Normalized importance sampling: Self-normalization can reduce importance-weight variance at the cost of bias, and its benefit depends on the task.The paper reports that self-normalization can improve performance empirically.

6. Related Work

Prior RL uses of SVRG mainly address policy evaluation or provide practical optimization methods, whereas this work targets policy-gradient control. Related policy-gradient variance reduction also includes unbiased baselines and importance-weighting techniques.

  • SVRG in RL: Du et al. apply SVRG to policy evaluation by minimizing MSPBE with a linear value-function approximation.Their problem has a finite-sum convex-concave saddle-point formulation with convergence guarantees.
  • SVRG in RL: Xu et al. use SVRG as a practical method for an RL optimization problem, distinct from the policy-gradient control setting addressed here.The supplied passage identifies this as the second prior SVRG application in RL.
  • Policy-gradient variance reduction: Policy-gradient methods can incorporate baselines without affecting gradient unbiasedness, although estimating baselines from data can reduce their effectiveness.The literature often studies baselines designed to minimize gradient-estimate variance.
  • Importance weighting: In SVRPG, importance weighting is an on-policy statistical correction used to preserve unbiasedness, not an off-policy learning method.This distinguishes its role from importance weighting in off-policy RL.

7. Experiments

The experiments compare SVRPG with G(PO)MDP on continuous-control tasks, finding faster learning and, in actor-critic Half-Cheetah, lower variance.

  • Experimental setup: SVRPG is evaluated against G(PO)MDP on Cart-pole, Swimmer, and actor-critic Half-Cheetah tasks.The experiments use continuous reinforcement-learning benchmarks and compare online performance over sampled trajectories.
  • Cart-pole: SVRPG shows faster convergence than G(PO)MDP on Cart-pole despite using more trajectories per parameter update.The authors attribute this to better-quality updates from variance reduction.
  • Swimmer: Self-normalized SVRPG improves performance on Swimmer, although its improvement over SVRPG is not statistically significant.The longer horizon and more complex dynamics make importance-weight variance more problematic on this task.
  • Swimmer: Self-normalized SVRPG outperforms G(PO)MDP through almost the entire Swimmer learning process, with statistically significant improvement toward the end.The experiments also report increased speed in early iterations.
  • Actor-critic: On Half-Cheetah, combining baseline usage with SVRG-like variance reduction improves performance beyond either technique alone and yields noticeably lower variance.The comparison uses self-normalized SVRPG and G(PO)MDP with the same critic.

8. Conclusion

The paper concludes that SVRPG addresses policy-dependent sampling through importance weighting, preserving unbiasedness and enabling convergence guarantees. Practical variants outperform classical actor-only approaches, while baseline integration remains an open design opportunity.

  • SVRPG is a variant of SVRG designed explicitly for reinforcement-learning problems.
  • Policy-dependent sampling is the main reinforcement-learning difficulty because the distribution underlying the objective changes as the policy is optimized.
  • Importance weighting overcomes sampling non-stationarity while preserving the unbiasedness of the corrected gradient.
  • Under mild assumptions often verified in reinforcement-learning applications, SVRPG admits convergence guarantees.
  • Practical SVRPG variants empirically outperform classical actor-only approaches on benchmark tasks, with preliminary support for effectiveness alongside a commonly used baseline.
  • The paper leaves designing a baseline explicitly for SVRPG as a potential way to jointly exploit reinforcement-learning structure and the SVRG idea.

B. Proofs

The proofs establish unbiasedness and variance-related properties of SVRPG under stated assumptions, then bound gradient quantities using smoothness, Lipschitz continuity, and variance inequalities.

  • Basic lemmas: The SVRG estimate is unbiased regardless of the mini-batch size B when the underlying estimator is unbiased.
  • Basic lemmas: Importance weights are necessary for unbiasedness because trajectories are sampled from the current policy rather than the snapshot policy.
  • Basic lemmas: Using the same trajectories in the relevant terms is necessary for the variance to vanish.
  • Regularity properties: Under the assumptions, J(θ) is L-smooth and the REINFORCE and G(PO)MDP estimators are Lipschitz continuous.The estimator bounds additionally hold when a bounded baseline is used.
  • Gradient bounds: The proofs bound the expected squared norms of both the SVRPG gradient estimate and the true gradient using the stated assumptions and auxiliary lemmas.

Main theorem

The main theorem gives a convergence guarantee for SVRPG using REINFORCE or G(PO)MDP estimators under Assumptions 4.1–4.3 and suitable step-size and epoch choices.

  • SVRPG returns a parameter vector θA after T = m × S iterations with a theorem-level convergence property under Assumptions 4.1, 4.2, and 4.3.
  • The guarantee applies when SVRPG uses either the REINFORCE or G(PO)MDP gradient estimator.
  • The convergence result requires appropriate choices of the step size α and epoch size m.
  • The theorem’s constants ψ, ζ, and ξ depend only on G, F, V, W, α, and m.

C. Applicability to Gaussian Policies

The section examines when the paper’s Gaussian-policy assumptions hold and describes practical SVRPG variants, including adaptive optimization and critic-based baselines.

  • Gaussian-policy assumptions: For bounded actions, linear means, and fixed variance, the Gaussian policy satisfies the paper’s on-policy derivative assumption under bounded features.The analysis uses a bounded feature vector and constrains the policy mean to the bounded action space.
  • Gaussian-policy assumptions: Fixed-variance Gaussian policies satisfy the required finite-variance condition for importance weights because the source and target variances are equal.The cited Gaussian result requires the latter variance to exceed the former; equal fixed variances are treated as automatically satisfying the paper’s condition.
  • Generalizations: Factored Gaussian policies extend the analysis to multi-dimensional actions, while fully multivariate Gaussians require additional calculations.The paper does not expect substantially different results for actual multivariate Gaussian distributions.
  • Generalizations: Nonlinear means such as deep neural networks fall beyond the paper’s analysis of first- and second-order log-derivatives.This limits the formal applicability analysis for complex continuous-control policies.
  • Practical variants: SVRPG practical variants use ADAM with separate moment histories for snapshot and sub-iteration gradients, exploiting larger snapshot batches to control variance.A critic can also be fitted by least squares and updated only at snapshots when used with SVRPG.

E. Experimental Details

The experiments evaluate SVRPG on three continuous-control tasks with different state and action dimensions, horizons, and reward definitions. Experimental parameters are tabulated, and supplementary videos show final-agent behavior.

  • Tasks: The evaluation covers Cart-Pole Balancing, Mujoco Swimmer, and Mujoco Half Cheetah continuous-control tasks.The tasks involve balancing an inverted pendulum, moving a snake-like robot forward, and moving a planar biped forward.
  • Cart-Pole Balancing: Cart-Pole uses a 4-dimensional state and 1-dimensional action, with episodes ending at failure thresholds or after 100 time steps.Its reward combines upright-pole performance with a small action penalty.
  • Mujoco Swimmer: Mujoco Swimmer uses a 13-dimensional state and 2-dimensional action, with episodes ending after more than 500 time steps.The reward is forward velocity minus an action penalty.
  • Configuration and materials: The experimental parameter settings, including neural-network architectures, are reported in Table 1, while supplementary videos show final SVRPG-agent behavior.Some meta-parameters are shared between G(PO)MDP and SVRPG.
Loading 1806.05618v1…