Variance reduced policy evaluation with smooth function approximation

Hoi To Wai, Mingyi Hong, Zhuoran Yang, Zhaoran Wang, Kexin Tang

Research output: Contribution to journalConference articlepeer-review

22 Scopus citations


Policy evaluation with smooth and nonlinear function approximation has shown great potential for reinforcement learning. Compared to linear function approximation, it allows for using a richer class of approximation functions such as the neural networks. Traditional algorithms are based on two timescales stochastic approximation whose convergence rate is often slow. This paper focuses on an offline setting where a trajectory of m state-action pairs are observed. We formulate the policy evaluation problem as a non-convex primal-dual, finite-sum optimization problem, whose primal sub-problem is non-convex and dual sub-problem is strongly concave. We suggest a single-timescale primal-dual gradient algorithm with variance reduction, and show that it converges to an e-stationary point using O(m/e) calls (in expectation) to a gradient oracle.

Original languageEnglish (US)
JournalAdvances in Neural Information Processing Systems
StatePublished - 2019
Event33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019 - Vancouver, Canada
Duration: Dec 8 2019Dec 14 2019

Bibliographical note

Funding Information:
H.-T. Wai is supported by the CUHK Direct Grant #4055113. M. Hong is supported in part by NSF under Grant CCF-1651825, CMMI-172775, CIF-1910385 and by AFOSR under grant 19RT0424.

Publisher Copyright:
© 2019 Neural information processing systems foundation. All rights reserved.


Dive into the research topics of 'Variance reduced policy evaluation with smooth function approximation'. Together they form a unique fingerprint.

Cite this