Stochastic Variance Reduction Methods for Policy Evaluation

Abstract

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.

arXiv commentAccepted by ICML 2017

Cited by in corpus (40)

• DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections
• Variance-reduced $Q$-learning is minimax optimal
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• Scalable Bilinear $\pi$ Learning Using State and Action Features
• Reinforcement Learning via Fenchel-Rockafellar Duality
• Off-Policy Evaluation via the Regularized Lagrangian
• Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity
• Actor-Critic Provably Finds Nash Equilibria of Linear-Quadratic Mean-Field Games
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach
• Reanalysis of Variance Reduced Temporal Difference Learning
• Improved Algorithms for Convex-Concave Minimax Optimization
• An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Newton-type Methods for Minimax Optimization
• On the Suboptimality of Negative Momentum for Minimax Optimization
• Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
• Stochastic Variance Reduction for Policy Gradient Estimation
• Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization
• Average-Reward Off-Policy Policy Evaluation with Function Approximation
• Exponential Stability of Primal-Dual Gradient Dynamics with Non-Strong Convexity
• Optimality and Stability in Non-Convex Smooth Games
• Breaking the Deadly Triad with a Target Network
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence
• Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation
• Variance Reduction for Deep Q-Learning using Stochastic Recursive Gradient
• An $O(s^r)$-Resolution ODE Framework for Understanding Discrete-Time Algorithms and Applications to the Linear Convergence of Minimax Problems
• Truncated Emphatic Temporal Difference Methods for Prediction and Control
• Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds
• A Generalized Projected Bellman Error for Off-policy Value Estimation in Reinforcement Learning
• SVRG for Policy Evaluation with Fewer Gradient Evaluations
• On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction
• Voting-Based Multi-Agent Reinforcement Learning for Intelligent IoT
• On Convergence of Gradient Expected Sarsa($\lambda$)
• $O\left(1/T\right)$ Time-Average Convergence in a Generalization of Multiagent Zero-Sum Games
• Conditional Importance Sampling for Off-Policy Learning
• Breaking the $O(1/\epsilon )$ Optimal Rate for a Class of Minimax Problems
• Scalable Projection-Free Optimization