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.

本文提出了一种基于线性函数逼近的政策评估算法，将经验政策评估问题转化为一个凸凹优化鞍点问题，并通过一些批量梯度方法和随机方差约减方法解决问题，在实验中取得了良好的效果。

策略评估的随机方差缩减方法

Stochastic Variance Reduction Methods for Policy Evaluation

We consider convex-concave saddle-point problems where the objective
functions may be split in many components, and extend recent stochastic
variance reduction methods (such as SVRG or SAGA) to provide the first
large-scale linearly convergent algorithms for this class of problems which is
common in machine learning. While the algorithmic extension is straightforward,
it comes with challenges and opportunities: (a) the convex minimization
analysis does not apply and we use the notion of monotone operators to prove
convergence, showing in particular that the same algorithm applies to a larger
class of problems, such as variational inequalities, (b) there are two notions
of splits, in terms of functions, or in terms of partial derivatives, (c) the
split does need to be done with convex-concave terms, (d) non-uniform sampling
is key to an efficient algorithm, both in theory and practice, and (e) these
incremental algorithms can be easily accelerated using a simple extension of
the "catalyst" framework, leading to an algorithm which is always superior to
accelerated batch algorithms.

提出了一种新的随机优化算法，可以高效地解决凸 - 凹二次问题，并适用于更广泛类别的问题，该算法以局部更新的形式实现，可以使用非均匀采样来加速算法。