Stochastic Variance Reduction Methods for Policy Evaluation

Simon S. Du; Jianshu Chen; Lihong Li; Lin Xiao; Dengyong Zhou

Source-linked AI summary

Stochastic Variance Reduction Methods for Policy Evaluation

Simon S. Du, Jianshu Chen, Lihong Li, Lin Xiao, Dengyong Zhou

arXiv:1702.07944v2Feb 25, 2017cs.LGcs.AIeess.SYmath.OCstat.ML

TL;DR

Policy evaluation with linear approximation must estimate value functions efficiently from fixed finite datasets, but EM-MSPBE does not directly have the finite-sum structure required by standard variance reduction. The paper reformulates the problem as a convex-concave saddle point and develops batch-gradient, SVRG, and SAGA solvers. These methods achieve linear convergence even without primal strong convexity, remain effective in off-policy settings, and are more efficient than other convergent gradient methods when sample size and feature dimension are large.

Problem
Efficient and accurate policy evaluation is important for reinforcement learning, but EM-MSPBE lacks the finite-sum structure needed to apply standard stochastic variance-reduction methods directly.
Method
The paper reformulates empirical MSPBE minimization as a convex-concave saddle-point problem and proposes a primal-dual batch gradient method plus SVRG- and SAGA-based variance-reduction methods.
Results
The proposed algorithms achieve linear convergence despite lacking strong convexity in primal variables, and the stochastic methods are more efficient than other gradient-based methods convergent in off-policy settings for large n and d.
Takeaways & Limitations
The results support efficient policy evaluation with linear approximation over fixed datasets, including off-policy learning and TD with eligibility traces.
Takeaways & Limitations
The paper identifies extending stochastic variance reduction to nonlinear approximation, especially deep neural networks, and applying it to policy optimization as open problems.

Abstract

from arXiv · show

Policy evaluation is a crucial step in many reinforcement-learning procedures, which estimates a value function that predicts states' long-term value under a given policy. In this paper, we focus on policy evaluation with linear function approximation over a fixed dataset. We first transform the empirical policy evaluation problem into a (quadratic) convex-concave saddle point problem, and then present a primal-dual batch gradient method, as well as two stochastic variance reduction methods for solving the problem. These algorithms scale linearly in both sample size and feature dimension. Moreover, they achieve linear convergence even when the saddle-point problem has only strong concavity in the dual variables but no strong convexity in the primal variables. Numerical experiments on benchmark problems demonstrate the effectiveness of our methods.

1 Introduction

The paper studies batch policy evaluation with linear approximation by reformulating EM-MSPBE minimization as a convex-concave saddle-point problem. It develops gradient and variance-reduction algorithms that converge linearly under weaker curvature conditions and are effective empirically.

Motivation: Policy evaluation estimates long-term state values under a fixed policy and supports policy improvement in reinforcement learning.Value functions predict expected cumulative reward and provide information for optimizing policies.
Problem setting: The paper minimizes MSPBE with linear value-function approximation in a batch setting using a fixed finite dataset.This setting enables optimization methods designed for finite-sum problems, although EM-MSPBE itself lacks the required finite-sum objective structure.
Methods: The authors transform empirical MSPBE minimization into an equivalent convex-concave saddle-point problem and propose batch gradient, SVRG, and SAGA methods.The model parameters are primal variables coupled bilinearly with dual variables.
Theory: Linear convergence holds in both primal and dual spaces when the coupling matrix is full rank, despite no strong convexity in the primal variables.The result contrasts with prior guarantees requiring strong convexity in the primal and strong concavity in the dual.
Experiments: The proposed methods are evaluated on Random MDP and Mountain Car datasets, with experiments demonstrating their effectiveness.The paper also states that its results extend to off-policy learning and TD with eligibility traces.

2 Preliminaries

The preliminaries define policy evaluation through value functions and MSPBE, then formulate its empirical finite-data objective. The paper motivates stochastic variance reduction as a lower-cost alternative to direct least-squares computation.

MDP framework: An MDP specifies states, actions, transitions, rewards, and discounting; a policy seeks to maximize long-term reward.The exposition assumes finite state spaces, although the paper states that its results do not rely on this assumption.
Value functions: A policy’s value function is the expected discounted cumulative reward and is the unique fixed point of its Bellman operator.The Bellman operator combines the policy’s expected reward vector with its induced transition matrix.
MSPBE: Linear approximation represents the value function as φ(s)^T θ, enabling policy evaluation when the state space is large or infinite.The parameter θ is chosen by minimizing the mean squared projected Bellman error, or MSPBE.
Empirical MSPBE: With finite data, replacing unknown population statistics by sample estimates yields the empirical MSPBE, optionally including ℓ2 regularization.The resulting objective is a regularized weighted least-squares problem when the relevant covariance matrix is invertible.
Computational cost: Direct LSTD computation costs O(nd^2) to form sample matrices and O(d^3) for the final calculation, making it expensive for large n and d.Rank-one updates avoid explicit matrix formation but still cost O(nd^2) overall.
Efficient optimization: The proposed variance-reduction algorithms sample one feature transition per update, avoid precomputing the matrices, use O(d) work per iteration, and depend logarithmically on accuracy.Their convergence rate has log(1/ϵ) dependence on the desired accuracy ϵ.

3 Saddle-Point Formulation of EM-MSPBE

The paper reformulates EM-MSPBE minimization as a convex-concave saddle-point problem with finite-sum structure, enabling variance-reduction methods despite the original objective’s incompatible form.

Motivation: EM-MSPBE cannot be directly expressed as minimizing a finite sum of convex component functions.Although its matrices have finite-sum structure, extending standard variance reduction is therefore not straightforward.
Saddle-point reformulation: Conjugate-function machinery converts EM-MSPBE minimization into an equivalent convex-concave saddle-point problem.The resulting formulation is convex in primal variable θ and concave in dual variable w.
Saddle-point reformulation: The saddle-point formulation retains a finite-sum structure suitable for stochastic optimization methods.This structure parallels the finite-sum form used by variance-reduction techniques.
Assumptions: The fast convergence analysis assumes full rank of bA, positive definiteness of bC, and uniformly bounded feature vectors.Under regularity conditions, these empirical assumptions are typically satisfied when the corresponding population statistics are nonsingular or positive definite and enough samples are available.
Assumptions: Under these assumptions, EM-MSPBE has a unique minimizer even without strongly convex regularization on θ.When ρ = 0, the coupling matrix can transfer implicit strong convexity to the primal variables.

4 A Primal-Dual Batch Gradient Method

The primal-dual batch gradient method solves the saddle-point formulation using batch gradients, with convergence controlled by problem conditioning and the primal-dual coupling.

Algorithm: PDBG solves the saddle-point problem by updating primal and dual variables with the stacked primal and negative dual gradients.The batch gradient operator can be computed either from precomputed matrices or as finite sums over samples.
Convergence: Under Assumption 1, suitable step sizes give an iteration bound for reaching squared-error tolerance ϵ² in both θ and w.The theorem specifies σθ = 1/[9Lρκ(bC)] and σw = 8/[9λmax(bC)].
Convergence: The linear rate depends on both the primal regularization parameter ρ and positive definiteness of bA^T bC^-1 bA.The latter reflects transfer of dual strong concavity through the full-rank bilinear coupling.
Convergence: PDBG retains linear convergence when ρ = 0, although the saddle-point objective is then strongly concave only in the dual variables.Positive definiteness of bA^T bC^-1 bA supplies the relevant primal-side effect.
Computational cost: PDBG costs O(d²) per iteration with precomputed matrices or O(nd) per iteration when gradients are formed from finite sums.Precomputation costs O(nd²), while each sample-level gradient costs O(d).

5 Stochastic Variance Reduction Methods

The paper adapts SVRG and SAGA to the saddle-point policy-evaluation problem, achieving low per-update cost and linear convergence without requiring primal strong convexity.

Motivation: Replacing PDBG’s batch gradient with a stochastic gradient recovers GTD2, which has low per-iteration cost but sublinear convergence.The proposed SVRG and SAGA methods retain stochastic updates while targeting linear convergence.
SVRG: SVRG computes a full gradient once per outer loop and uses corrected stochastic gradients in an inner loop.Its correction remains unbiased while reducing variance.
SVRG: Each SVRG outer loop costs O(nd + Nd), combining one full-gradient computation with N inner updates.The full gradient costs O(nd), and each inner iteration costs O(d).
SAGA: SAGA stores component-gradient information, updates one sampled component at a time, and maintains a variance-reduced batch estimate.Its rank-one structure reduces storage and keeps each iteration at O(d) computation.
Convergence: SVRG and SAGA achieve linear convergence even when ρ = 0 and the saddle-point problem lacks primal strong convexity.The result relies on positive definiteness of bA^T bC^-1 bA and full-rank coupling.
Implementation: The methods require only stochastic gradients of the dual quadratic term rather than an efficiently computable proximal mapping.This avoids a limitation of proximal SVRG and SAGA for the policy-evaluation formulation.

6 Comparison of Different Algorithms

The complexity comparison finds that SVRG and SAGA scale linearly in feature dimension and can be more efficient than competing methods when the dataset or feature dimension is large.

Complexity comparison: Table 1 compares computational complexities of representative policy-evaluation algorithms for minimizing EM-MSPBE.The comparison uses dataset size n and feature dimension d, along with condition-number terms.
Complexity comparison: The table’s upper group contains algorithms whose complexity is linear in feature dimension d, including the proposed methods.This provides the relevant scaling regime for large feature representations.
Comparison with GTD2: GTD2 has O(d) cost per iteration but sublinear convergence, yielding O(κ′nd) overall complexity when target accuracy is ϵ = Ω(1/n).The paper reports that SVRG/SAGA’s effective condition numbers vanish as n becomes large, unlike this GTD2 comparison.
Complexity comparison: SVRG and SAGA are more efficient than other algorithms when either d or n is very large.They can have lower complexity than LSTD when d exceeds the stated condition, and lower complexity than PDBG-(I) when n is sufficiently large.
Related algorithms: Several other algorithms scale linearly with n and d but require 1/ϵ or worse iterations to reach accuracy ϵ.CTD is described as having a similar linear convergence rate in a separate online Markov-data setting.

7 Extensions

The paper extends its policy-evaluation algorithms to off-policy learning and eligibility traces by modifying sample statistics while preserving the algorithmic framework and fast convergence guarantees.

Off-policy learning: Despite behavior-target policy mismatch, the proposed gradient-based algorithms remain convergent with the same fast convergence rate.This contrasts with stochastic-approximation methods that can diverge in the off-policy setting.
Off-policy learning: Off-policy learning changes A_t, b_t, and C_t using importance ratios, while Algorithms 1–3 remain unchanged.The importance ratio is ρ_t = π(a_t|s_t)/π_b(a_t|s_t).
Eligibility traces: With eligibility traces, z_t is pre-computed and uniformly sampled with φ_t, φ′_t, and r_t to compute stochastic gradients.The algorithms immediately apply to this setting after using the trace-specific definitions.
Eligibility traces: Eligibility traces preserve a similar linear convergence rate and O(n d) complexity, with additional O(n d) preprocessing and storage for z_t.The preprocessing and storage do not change the total asymptotic complexity of SVRG/SAGA.

8 Experiments

Experiments on a Random MDP and Mountain Car show that the proposed variance-reduction methods converge faster than other first-order baselines, especially under better conditioning and larger datasets.

Random MDP: On the Random MDP, the stochastic variance-reduction methods converge much faster than the other evaluated algorithms and achieve linear convergence.The task uses 400 states, 201-dimensional features, γ = 0.95, and n = 20000.
Random MDP: As ρ increases, PDBG, SVRG, and SAGA improve significantly on the Random MDP because of better conditioning.This trend matches the paper’s theoretical predictions.
Mountain Car: On Mountain Car, the proposed stochastic variance-reduction methods dominate the other first-order methods.The experiments use d = 300 CMAC features and datasets with n = 5000 and n = 20000.
Mountain Car: With larger ρ, PDBG, SVRG, and SAGA converge faster on Mountain Car, while increasing n further accelerates SVRG and SAGA.The latter observation verifies the theoretical finding that SVRG/SAGA need fewer epochs for large n.

9 Conclusions

The paper reformulates empirical MSPBE policy evaluation as a saddle-point problem and develops batch-gradient and variance-reduction algorithms with linear convergence under weaker primal curvature conditions.

Contributions: The EM-MSPBE minimization problem is reformulated as an empirical saddle-point problem, yielding a batch-gradient method and two stochastic variance-reduction methods.The methods target policy evaluation with the reformulated objective.
Contributions: Linear convergence holds even when the saddle-point problem lacks strong primal convexity and has only strong dual concavity.The result applies to the proposed algorithms under the paper’s stated coupling conditions.
Conclusions: When feature dimension d and sample size n are large, the stochastic variance-reduction methods are more efficient than other gradient-based methods convergent in off-policy settings.This is the paper’s stated efficiency conclusion for large-scale problems.
Future work: Extending stochastic variance reduction to nonlinear approximation, especially deep neural networks, and to policy optimization remains open.These directions define the paper’s stated scope boundary.

A.2 Analysis of eigenvectors

The eigenvector analysis constructs a positive-definite matrix H related to G, then bounds its conditioning to control the eigenvector condition number when G is diagonalizable.

Eigenvector conditioning: The analysis represents G through its eigenvalues and eigenvectors and seeks to bound κ(Q), the condition number of its eigenvector matrix.The matrix Q contains unit-norm eigenvectors as columns.
Eigenvector conditioning: A theorem connects H and G: if H is symmetric positive definite and HG is symmetric, then G has an H-orthonormal eigenvector basis.This yields H = Q^-⊤Q^-1 and κ(H) = κ_2(Q).
Positive definiteness: The constructed H is positive definite when δ − ρ > 0 and β Ĉ − δI − β/(δ − ρ) ÂÂ^⊤ is positive definite.A Schur decomposition establishes the condition through a positive-definite block matrix.
Conditioning bounds: The analysis selects β and δ to satisfy the positivity conditions, then derives upper and lower eigenvalue bounds for H and its condition number.These bounds support control of κ(Q).
Eigenvalue analysis: For the eigenvalues of G, the chosen β ensures diagonalizability and positive real eigenvalues through the discriminant condition p^2 ≥ 4q.The eigenvalue bounds follow from the resulting quadratic equation.
Eigenvector conditioning: Because G is non-normal, its condition number cannot be bounded directly using eigenvalue bounds alone.The separate H- and Q-based analysis addresses this issue.

B Linear convergence of PDBG

The PDBG analysis establishes linear convergence for the saddle-point policy-evaluation method under positive-definiteness and full-rank assumptions, using a scaled potential based on the dynamics matrix. The resulting iteration bound follows from the real positive spectrum of that matrix.

The optimal solution is characterized by the first-order conditions under positive-definite bC and full-rank bA assumptions.
The PDBG method iterates on the primal and dual parameters using gradients of the Lagrangian.
The convergence proof tracks a scaled residue vector and a potential function defined through the eigenvectors of G.
Choosing β sufficiently large makes G diagonalizable with real, positive eigenvalues, enabling the convergence analysis.
The analysis yields an ϵ-close solution after a logarithmic number of PDBG iterations, with the condition-number factor entering the logarithmic term.
Replacing eigenvalue bounds in the step-size expressions changes the contraction factor while preserving the same complexity order.

C Analysis of SVRG

The SVRG analysis proves linear convergence by combining finite-sum structure, variance-reduced inner updates, and Lyapunov potentials. Its complexity includes full-gradient costs, inner iterations, and an additional dependence on the eigenvector condition number.

The SVRG proof establishes linear convergence for the policy-evaluation algorithm described in Algorithm 2.
The analysis exploits the finite-sum structure of bA, bb, and bC to organize full-gradient and stochastic computations.
SVRG uses outer and inner loops, with updates analyzed through residue recursions involving the matrix G_tj.
A potential function based on the eigenvector decomposition tracks the transformed error, while variance bounds control stochastic cross terms.
Nonorthogonal eigenvectors introduce an additional dependence on the condition number of Q in the SVRG iteration complexity.
The resulting computational cost combines O(nd) full-gradient work per outer iteration with O(d) inner iterations and logarithmic outer convergence.The stated inner-loop count depends on condition and smoothness quantities.
The SAGA analysis similarly uses stored gradients, auxiliary quantities, and a Lyapunov function to derive its iteration complexity.