SVRG for Policy Evaluation with Fewer Gradient Evaluations

1 Introduction

Policy evaluation is an important problem in reinforcement learning (RL) whose goal is to estimate the value function, a function which measures the long-term expected return at any given state. Theoretically well-studied linear methods for policy evaluation fall into two categories: least square approaches [Bradtke and Barto, 1996; Boyan, 2002] and gradient based approaches [Baird, 1995; Sutton et al., 2008; Sutton et al., 2009; Liu et al., 2015]. In large data settings, least square approaches are not efficient because they compute matrix inverses, and gradient based approaches are preferable.

One of objective functions used by gradient-based methods for policy evaluation is Mean Squared Projected Bellman Error (MSPBE). Existing methods such as TD [Sutton, 1988], GTD2 and TDC [Sutton et al., 2009] have sublinear convergence rates when solving this objective as shown in [Bhandari et al., 2018; Touati et al., 2018; Dalal et al., 2019]. Du et al. [2017] applied SVRG [Johnson and Zhang, 2013] to solve MSPBE, leading to a linear convergent method. An important and computationally heavy step of SVRG is to compute a full gradient at the beginning of every epoch.

∗Equal contribution. † Work done while at Facebook AI research.

In this paper, we address the computational bottleneck of SVRG for policy evaluation, by extending batching SVRG [Harikandeh et al., 2015] and SCSG [Lei and Jordan, 2017] to solve MSPBE. Both methods were originally designed for convex minimization problems. These are significantly different from our objective, a convex-concave saddlepoint problem without strong convexity in the primal variable 1 . The convergence analysis in [Harikandeh et al., 2015; Lei and Jordan, 2017] does not apply in our settings and we establish new convergence results of batching SVRG and SCSG for solving MSPBE. In this work, we make the following key contributions:

1. We show that both batching SVRG and SCSG achieve linear convergence rates for policy evaluation while yielding considerable savings in the number of gradient computations. To the best of our knowledge, this is the first result for batching SVRG and SCSG in the saddle-point setting.
2. While our analysis of SCSG builds on the ideas of [Lei and Jordan, 2017], our proofs end up quite different and also a lot simpler because we exploit the structure of our problem.
3. Our experimental results demonstrate that batching SVRG and SCSG are efficient in large data settings.

2 Background

In RL, a Markov Decision Process (MDP) is typically used to model the interaction between an agent and its environment. An MDP is defined by a tuple (S, A, P, r, γ), where S is the set of possible states, A is the set of actions,the transition probability function P : S × A → (S → [0, 1]) maps stateaction pairs to distributions over next states. r denotes the reward function: (S,A) → R, which returns the immediate reward that an agent will receive after performing an action a at state s and γ ∈ (0, 1) is the discount factor used to discount rewards received farther in the future. For simplicity, we will assume S and A are finite.

1 A general convex-concave saddle-point problem can be solved with a linear convergence rate [Balamurugan and Bach, 2016], but the method requires strong convexity in the primal variable and the access to a proximal operator.

A policy π : S → (A → [0, 1]) is a mapping from states to distributions over actions. The value function for policy π, denoted V π : S → R, represents the expected sum of discounted rewards along the trajectories induced by the policy in the MDP: V π (s) = E[∑∞t=0 γ t rt | s0 = s, π]. V π can be obtained as the fixed point of the Bellman operator over the action-value function T π V = rπ + γP π V where rπ is the expected immediate reward and P π is defined as P π (s′ |s) ≜ ∑a∈A π(a | s)P(s′ | s, a).

In this paper, we are concerned with the policy evaluation problem [Sutton and Barto, 1998] i.e. estimation of V π for a given policy π. In order to obtain generalization between different states, V π should be represented in a functional form. In this paper, we focus on linear function approximation of the form: V (s) ≜ θ⊤φ(s) where θ ∈ Rd is a weight vector and φ : S → Rd is a feature map from states to a given d-dimensional feature space.

3 Objective Functions

We assume that the Markov chain induced by the policy π is ergodic and admits a unique stationary distribution, denoted by dπ , over states. We write Dπ for the diagonal matrix whose diagonal entries are (dπ (s))s∈S.

If Φ = (φ(s))s∈S ∈ R|S|×d denotes the matrix obtained by stacking the state feature vectors row by row, then it is known [Bertsekas, 2011] that Φθ⋆ is the fixed point of the projected Bellman operator :

where Ππ = Φ(Φ⊤Dπ Φ)-1Φ⊤Dπ is the orthogonal projection onto the space S = {Φθ | θ ∈ Rd } with respect to the weighted Euclidean norm ||.||Dπ . Rather than computing a sequence of iterates given by the projected Bellman operator, another approach for finding θ∗ is to directly minimize [Sutton et al., 2009; Liu et al., 2015] the Mean Squared Projected Bellman Error (MSPBE):

By substituting the definition of Ππ into (2), we can write MSPBE as a standard weighted least-squares problem (See [Sutton et al., 2009] for a complete derivation):

where A, b and C are defined as follows:

where the expectations are taken with respect to the stationary distribution.

Empirical MSPBE: We focus here on the batch setting where we collect a dataset of n transitions {(st, at, rt, st+1)}t∈[n] generated by the policy π. We replace the quantities A, b and C in (3) by their empirical estimates:

where for all t ∈ [n], for a given transition (st, at, rt, st+1)

Therefore we consider the empirical MSPBE defined as follows:

Finite sum structure: We aim at using stochastic variancereduction techniques to our problem. These methods are designed for problem with finite sum structure as follows:

Unfortunately, even by replacing quantities A, b and C by their finite-sample estimates, the obtained empirical objective in (6) could not be written in such form (7). However, Du et al. [2017] convert the empirical MSPBE minimization in (6) into a convex-concave saddle point problem which presents a finite sum structure. To this end, Du et al. [2017] use the convex-conjugate trick, and the empirical MSPBE minimization is shown to be equivalent to:

The obtained objective, we denote by f(θ, ω), in (8) could be written as f(θ, ω) = 1n ∑nt=1 ft(θ, ω) where ft(θ, ω) = 〈ˆbt - ˆ Atθ, ω〉 - 12 ||ω||2ˆ Ct

4 Existing Optimization Algorithms

Before presenting our new methods, we first review briefly existing algorithms that solve the saddle-point problem (8). Let's define the vector F (θ, ω) obtained by stacking the primal and negative dual gradients:

Gradient temporal difference: GTD2 algorithm [Sutton et al., 2009], when applied to the batch setting, consists of the following update: for a uniformly sampled t ∈ [n]:

where σθ and σω are step sizes on θ and ω. GTD2 has a low computation cost per iteration but only a sublinear convergence rate [Touati et al., 2018].

SVRG for policy evaluation: Du et al. [2017] applied SVRG to solve the saddle-point problem (8). The idea is to alternate between full and stochastic gradient updates in two layers of loops. In the outer loop, a snapshot (˜ θ, ˜ω) of the current variables is saved together with its full gradients vector F (˜ θ, ˜ω). Between snapshots, the variables are updated with a gradient estimate corrected using the stochastic gradient:

where t ∈ [n] is uniformly sampled. Du et al. [2017] showed that the algorithm has a linear convergence rate although the objective (8) is not strongly convex in the primal variable θ. However, the algorithm remains inefficient in term of computations as it requires to compute a full gradient using the entire dataset in the outer loop. In the rest of the paper, "an epoch" means an iteration of the outer loop. In the sequel, we introduce two variants of SVRG for policy evaluation that alleviate the computational bottleneck in SVRG while preserving the linear convergence rate.

5 Batching SVRG and SCSG for Policy Evaluation

Both batching SVRG [Harikandeh et al., 2015] and SCSG [Lei and Jordan, 2017] were initially introduced for convex minimization. Here, we apply them to our convex-concave saddlepoint objective function. Algorithm 1 shows the pseudo-code of our methods.

Batching SVRG for policy evaluation estimates full primal and dual gradients in each epoch m using only a subset B (a mini-batch) of size |B| = Bm of training examples: µm = 1 Bm ∑t∈Bm Ft(˜ θ, ˜ω). In each iteration j of the inner loop, it uses vm,j to update θ and ω. vm,j is the usual SVRG update, except that the full gradients is replaced with the mini-batch gradients µm. vm,j = Ftj (θm,j, ωm,j) - Ftj (˜ θ, ˜ω) + µm where tj is sampled uniformly in [n].

SCSG for policy evaluation implements the gradient computation on a subset B of training examples at each epoch. Unlike batching SVRG, the mini-batch size is fixed in advance and not varying. Moreover, instead of being fixed, the number of iteration for the inner loop in SCSG is sampled from a geometrically distributed random variable: Km ∼ Geom( B B+1 ) for each epoch m.

6 Convergence Analysis

6.1 Notations and Preliminary

In order to characterize the convergence rates of proposed algorithms, we need to introduce some new notations and state new assumptions.

We denote by ‖A‖ ≜ sup‖x‖=1 ‖Ax‖ the spectral norm of the matrix A and by κ(A) = ‖A‖‖A-1 ‖ its condition number. If the eigenvalues of a matrix A are real, we use λmax(A) and λmin(A) to denote respectively the largest and the smallest eigenvalue.

If we set σω = βσθ for a positive constant β, it is possible to write the inner loop update (line 11) as an update for the Algorithm 1 Batching SVRG and SCSG for policy evaluation. Line 3 and 6 are steps only in batching SVRG. Line 4 and 7 are steps only in SCSG.

Batching SVRG's input: initial point (θ, ω), σθ, σω, M, K SCSG's input: initial point (θ, ω), σθ, σω, M, K and B Output: (θ, ω)

• 1: for m = 0 to M-1 do
• 2: Set (˜ θ, ˜ω) and (θm,0, ωm,0) to (θ, ω).
• 3: Batching SVRG's step: choose a mini-batch size Bm. Sample a set B with Bm elements uniformly from [n]
• 4: SCSG's step: sample a set BwithB elements uniformly from [n]
• 5: Compute µm = 1 |B| ∑t∈B Ft(˜ θ, ˜ω)
• 6: Batching SVRG's step: Km =K
• 7: SCSG's step: Km ∼ Geom( B B+1 )
• 8: for j = 0 to Km - 1 do
• 9: Sample tj uniformly randomly from [n]

11:

• 12: end for
• 13: (θ, ω) = (θm,Km , ωm,Km )
• 14: end for
• 15: return (θ, ω)

where:

and their corresponding averages over the mini-batch Bm:

Let's now define the matrix G (the vector g) as the average of matrices Gt (vectors gt) over the entire dataset:

To simplify notations, we overload the notation λmin = λmin(G). Another important quantity that characterizes smoothness of our problem is L2G defined below as:

The matrix G will play a key role in the convergence analysis of both batching SVRG and SCSG. Du et al. [2017] have already studied the spectral properties of G as it was critical for the convergence of SVRG for policy evaluation. The following lemma, restated from [Du et al., 2017], shows the condition β should satisfy so that G is diagonalizable with all its eigenvalues real and positive.

Assumption 1. ˆ A nonsingular and ˆ C is definite positive. This implies that the saddle-point problem admits a unique solution (θ⋆ , ω⋆ ) = ( ˆ A-1ˆb, 0) and we define z⋆ ≜ (θ⋆ , 1 √β ω⋆ ).

Lemma 1. [Du et al., 2017] Suppose assumption 1 holds and if we choose β = σω σθ = 8λmax( ˆ AT ˆ C-1 ˆ A) λmin( ˆ C) , then the matrix G is diagonalizable with all its eigenvalues real and positive.

If assumptions of lemma 1 hold, we can write G as G = QΛQ-1 where Λ is a diagonal matrix whose diagonal entries are the eigenvalues of G, and Q consists of it eigenvectors as column. We define the residual vector ∆m = zm - z⋆ . To study the behaviour of our algorithms, we use the potential function ∥∥Q-1∆m∥∥2 . As ‖Q‖2 ∥∥Q-1∆m∥∥2 ≥ ‖∆m‖2 ≥ ‖θ - θ⋆ ‖2 , the convergence of ∥∥Q-1∆m∥∥2 implies the convergence of ‖θ - θ⋆ ‖2 .

6.2 Convergence of Batching SVRG for Policy Evaluation

In order to study the behavior of batching SVRG for policy evaluation, we defined em as the error occurred at epoch m. This error comes from computing the gradients over a minibatch Bm instead of the entire dataset.

The stochastic update of the inner loop could be written as follows:

Theorem 1. Suppose assumption 1 holds and if we choose σθ = λmin 6κ(Q)2L2G , β = 8λmax( ˆ AT ˆ C-1 ˆ A) λmin( ˆ C) , σω = βσθ and K = 2 σθλmin = 12κ(Q)2L2G λ2min , then E ∥∥Q-1∆m+1∥∥2 is upper bounded by:

Full proof of theorem 1 is in [Peng et al., 2019].

Note that if Bm = n ∀m, the error is zero and we recover the convergence rate of SVRG in theorem 1. Moreover, we could still maintain the linear convergence rate if the error term vanishes at an appropriate rate. In particular, the corollary below provides a possible batching strategy to control the error term.

Corollary 1. Suppose that assumptions of theorem 1 hold. If the sample variance of the norms of the vectors Ft is bounded by a constant Ξ2 : 1 n-1 ∑nt=1 ‖Gtz - gt‖2 - ‖Gz - g‖2 ≤ Ξ2 ∀z and we set Bm = nΞ2 Ξ2+nαρm < n for some constants α > 0 and ρ < 2/3 then E ∥∥Q-1∆M ∥∥2 is upper bounded by:

We conclude that an exponentially-increasing schedule of mini-batch sizes achieves linear convergence rate for batching SVRG. This batching strategy saves many gradient computations in early stages of the algorithm comparing to vanilla SVRG.

6.3 Convergence of SCSG for Policy Evaluation

Before stating the convergence result, we introduce the complexity measure defined as follows:

This quantity is equivalent to the complexity measure that is introduced by [Lei and Jordan, 2017] to analyze SCSG for convex minimization problems, and is defined as H(f) = infx⋆∈argminf(x) 1n ∑ni=1 ‖∇fi(x∗ )‖2 .

Theorem 2. Suppose assumption 1 holds. Set σθ ≤ min{ λmin 20κ(Q)2L2G , 5 28Bλmax }, σω = βσθ and B ≥ 70κ(Q)2L2G λ2min . The E ‖θM-1 - θ⋆ ‖2 is upper bounded by:

Full proof of theorem 2 is in [Peng et al., 2019].

Proof sketch: We first take the squared two norms and expectations on SCSG's update, then use the property of geometric random variables. We have:

Since assumption 1 holds, we can derive two inequalities by applying lemma 1: E ∥∥Q-1∆m+1∥∥2 ≤ 1 λmin E∆⊤m+1Q-⊤ΛQ-1∆m+1 and E ∥∥ΛQ-1∆m+1∥∥2 ≤ λmax E 〈ΛQ-1∆m+1, Q-1∆m+1 〉 where λmin and λmax are the smallest and largest eigenvalues of Λ. Moreover, using the technical lemma B.1 in [Lei and Jordan, 2017], we show that E ∥∥Q-1 em∥∥2 is upper bounded by:

Plugging theses bounds to (18), we arrive at:

where c1 = (1 + 0.8σθBλmin) and c2 = 0.7σθB. Values of c1 and c2 come from our settings of σθ and B. We prove the theorem after enrolling the above inequality from m = 0 to M - 1 and doing some algebraic manipulations.

Corollary 2. Suppose assumption 1 holds. Set σθ = min { λmin 20κ(Q)2L2G , 5 28Bλmax }, σω = βσθ and B = min {max { 70κ(Q)2L2G λ2min , 120κ(Q)2H λ2min ϵ } , n}. Let ϵ > 0, the computational cost in expectations that SCSG required to obtain E ‖θM-1 - θ⋆ ‖2 ≤ ϵ is:

Table 1 lists computational costs of our methods and other related methods. GTD2 is the cheapest computationally but it has a sublinear convergence rate. Both SVRG and SCSG achieve linear convergence rates. When the dataset size n is small, SVRG and SCSG have an equivalent computational cost. However, when n is large and the required accuracy ϵ is low, SCSG saves unnecessary computations and is able to achieve the target accuracy with potentially less than a single pass through the dataset.

We compare the computational costs of batching SVRG and SVRG. In epoch m, batching SVRG's computational cost is O(Bm + Km), where Bm is the batch size and Km is the number of inner loop iteration. According to theorem 1, Km is set as O( κ(Q)2L2G λ2min ) for all m. If we use an exponentially increasing sequence of batch sizes that we considered in corollary 1, Bm is strictly less than n, for all m. Since batching SVRG converges linearly, it takes O(ln(1/ϵ)) epochs to reach an ϵ-optimal solution. The overall computational cost of batching SVRG is O ((n′ + κ(Q)2L2G λ2min ) d × ln(1/ϵ)) as shown in table 1, where n′ < n, so batching SVRG is computationally more efficient than the vanilla SVRG.

7 RelatedWorks

GTD2 [Sutton et al., 2009] converges to the TD fixed point with linear function approximation. Although derived using MSPBE, GTD2 actually performs stochastic gradient updates on the saddle point formulation of MSPBE [Liu et al., 2015]. Finite sample analysis [Wang et al., 2017; Touati et al., 2018] and accelerations [Liu et al., 2015; Du et al., 2017] on GTD2 becomes possible by using the saddle point formulation of MSPBE. Du et al. [2017] applied SVRG [Johnson and Zhang, 2013] and SAGA [Defazio et al., 2014] to policy evaluation.

Both methods can be inefficient when the size of the data set is large. We proposed two variants of SVRG with computational costs independent of the size of the data set, while preserving a linear convergence rate.

In control settings, [Papini et al., 2018] and [Xu et al., 2019] adapted SVRG to policy gradient. Their objectives are nonconvex while our objective is a convex-concave. Our methods are policy evaluation algorithms, but they can be applied in control settings by combining with LSTDQ [Lagoudakis and Parr, 2003].

Variance reduction techniques have been applied to temporal difference learning [Korda and L.A., 2015; Xu et al., 2020]. They considered an online setting where the value function is updated as data arrives. We consider a batch setting, where we use the policy to collect a batch of data and then learn the value function.

8 Experiments

Our proposed methods, batching SVRG and SCSG 2 , are evaluated with LSTD, SVRG, SAGA and GTD2 on 4 tasks: Random MDP [Dann et al., 2014], MountainCar-v0, CartPole-v1 and Acrobot-v1 [Brockman et al., 2016]. Detailed experiment setups are in [Peng et al., 2019].

8.1 Comparing Batching SVRG and SVRG

We show empirically that batching SVRG converges as fast as SVRG while using less amount of data. Figure 1 shows policy evaluation results of SVRG and batching SVRG in different environments, and table 2 shows computational costs of SVRG and batching SVRG. Given same number of epochs, batching SVRG achieves same level of performances with SVRG while taking fewer passes through the dataset. The empirical performance of batching SVRG is expected because our theoretical result suggests that having an approximation error of the full gradient will not affect the overall convergence speed if the error decreases properly.

8.2 Control Performances

We run gradient based methods and LSTD for policy evaluation and apply the learned policy on control tasks. This lets us test the practicality of our methods. We also intend to test our proposed methods' performances in large datasets. In Mountain Car (large data), Cart Pole (large data) and Acrobot (large data), the dataset contains 1 million data samples and each method is only allowed to use the dataset once. We run all methods with small datasets as well. In Mountain Car, Cart Pole and Acrobot, the dataset contains 20000 data samples. In all control experiments, we first use a random policy to generate data, then apply policy evaluation algorithms to learn the value function, and finally use the learned policy to control.

2 Code of our experiments can be found at: https://github.com/ zilunpeng/svrg_for_policy_evaluation_with_fewer_gradients

Table 3 shows control performances of all methods. We observe that gradient based methods outperform LSTD in experiments when the dataset is small. In large-data experiments, LSTD's performances improve. We run gradient based methods for a single pass through the dataset in large-data experiments. Since SVRG and SAGA need to compute full gradients at the beginning, they cannot solve the control tasks. GTD2, batching SVRG and SCSG do not rely on full gradients, so they make progress instantly. In particular, batching SVRG and SCSG achieve the same level of performance with LSTD in Cart Pole (large data) and Acrobot (large data). Our proposed methods and LSTD both use the dataset once and solve the control tasks, while other gradient based methods need more than one pass of the data set. More importantly, unlike LSTD, our methods are first order methods and do not need to invert matrices, which makes our methods practical when both the size of the dataset and the number of state's features are large.

8.3 Policy Evaluation in Large Data Settings

To test our methods' performances on a very large dataset, we generate 10 million data samples from a policy that performs random actions in Random MDP. Figure 2 shows policy evaluation performances of all gradient based methods in Random MDP. We run all methods for a single pass through the dataset. SVRG and SAGA do not make progress because they need to compute full gradients. We observe that batching SVRG and SCSG converge much faster than GTD2, because batching SVRG and SCSG have linear convergence rates, while GTD2 has a sublinear convergence rate. This experiment shows again that our proposed methods have good performances in large data settings.

9 Conclusion

We show that batching SVRG and SCSG converge linearly when solving the saddle-point formulation of MSPBE. This problem is convex-concave and is not strongly convex in the primal variable, so it is very different from the original objective function that batching SVRG and SCSG attempt to solve. Our algorithms are very practical because they require much fewer gradient evaluations than the vanilla SVRG for policy evaluation. There is a lot of room for applying more efficient optimization algorithms to problems in reinforcement learning, in order to obtain better theoretical guarantees and to improve sample and computational efficiency. We think the present work is a valuable contribution in that direction.