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 $\epsilon$-stationary point using $O(m/\epsilon)$ calls (in expectation) to a gradient oracle.

Overall, the paper made significant contribution to both the reinforcement learning community and optimization community. The proposed algorithm is a variant of non-convex SAGA algorithm introduced by [1]. The novelty comes from their proof for the non-convex but strongly concave case. There are several issues which should be addressed: 1, Recasting the policy evaluation as a primal-dual optimization via the Fenchel duality technique is not new. In fact, [2,3,4] have already exploit this reformulation. First, these related work should be referred appropriately.

The main contribution of this paper is in solving the finite-sum minimax problem arising from off-line policy evaluation with nonlinear function approximation. The minimax problem is non-convex in the primal variable and strong convexity in the dual subproblem, and a single time-scale algorithm is proposed to find an approximate stationary point. Although it does not address the full stochastic TD learning problem, the progress in the finite-sum off-line version is quite meaningful.

Policy evaluation with smooth and nonlinear function approximation has shown great potential for reinforcement learning. Compared to linear function approxi- mation, 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.

Policy evaluation with smooth and nonlinear function approximation has shown great potential for reinforcement learning. Compared to linear function approxi- mation, 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.