Stochastic Variance Reduction Methods for Policy Evaluation

By Simon Shaolei Du, Jianshu Chen, Lihong Li, Lin Xiao, Dengyong Zhou. 2017

170 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Reinforcement Learning via Fenchel-Rockafellar Duality (2020, methodology): “Typically, the Q-values are estimated by minimizing squared Bellman residuals (or some variation on this) (Sutton et al., 2008, 2009; Liu et al., 2015; Dai et al., 2016; Du et al., 2017); i.”
DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections (2019, background): “As shown in [11], under Assumption 8 and set ρ = 8λmax(ACA) λmin(C) , the matrix Q := E [ Q̂ ]”
Smoothed Dual Embedding Control (2017, methodology): “A similar result is also presented in Fox et al. (2015); Asadi and Littman (2016).”
Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, methodology): “This technique is later brought into reinforcement learning for handling policy evaluation (Du et al., 2017) and policy optimization problems (Sidford et al.”
Scalable Bilinear π Learning Using State and Action Features (2018, background): “It should be noted that there is another line of research that studies saddle-point formulations that result from the ﬁxed-point (as opposed to LP) view of the Bellman equation for ﬁxed policy evaluation (Mahadevan et al., 2014; Macua et al., 2015; Du et al., 2017; Dai et al., 2017).”
Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation (2019, background): “Du et al. (2017) introduce ridge regularization to improve the convexity of the objective.”
Off-Policy Evaluation via the Regularized Lagrangian (2020, methodology): “In one line of literature, it was used to solve the Bellman equation, whose fixed point is the value function [6, 7, 16].”
Online Off-policy Prediction (2018, methodology): “Several of the accelerations mentioned above, such as the use of stochastic variance reduction strategies (Du et al., 2017), assume a batch learning setting.”
Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems (2020, methodology): “This minimax optimization formulation includes many machine learning applications such as regularized empirical risk minimization [41, 52], AUC maximization [39, 48], robust optimization [14, 46], adversarial training [16, 17, 40] and reinforcement learning [13, 43].”
Stabilizing Adversarial Nets With Prediction Methods (2017, methodology): “Similar optimization algorithms have been studied for reinforcement learning (Wang & Chen, 2016; Du et al., 2017).”
On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach (2019, background): “, 2018) and primal-dual reinforcement learning (Du et al., 2017; Dai et al., 2018), explicitly specify the order of moves between players and the order of which player acts first is crucial for the problem.”
Provably Convergent Off-Policy Actor-Critic with Function Approximation (2019, background): “Du et al. (2017) introduce ridge regularization to improve the convexity of the objective.”
SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation (2017, methodology): “led to novel, faster, and more robust algorithms by adopting sophisticated optimization techniques (Du et al., 2017).”
Stochastic Variance-Reduced Policy Gradient (2018, methodology): “The ﬁrst approach (Du et al., 2017) aims to exploit SVRG for policy evaluation.”
Multiagent Fully Decentralized Value Function Learning With Linear Convergence Rates (2018, methodology): “This article is related to [13] in that we too use a variance-reduced strategy; however, we use the AVRG strategy [14] which is more convenient for distributed implementations because of an important balanced gradient calculation feature.”
Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems (2020, background): “…found application in the study of generative adversarial networks (GANS) (e.g. Goodfellow et al. (2014); Arjovsky et al. (2017)), adversarial examples (e.g. Madry et al. (2019)), robust optimization (e.g. Ben-Tal et al. (2009)), and reinforcement learning (e.g. Du et al. (2017); Dai et al. (2018)).”
Linear Lower Bounds and Conditioning of Differentiable Games (2019, methodology): “in reinforcement learning to learn a linear value function from the mean squared projected Bellman error (Du et al., 2017) where we assume that M12 is a wide or square matrix (if it is a tall matrix, we use μ(2)12 ≤ |σ(M > 12M12)| ≤ L(2)12 to define μ12 and L12 instead of the last inequality of eq.”