On $\mathcal{O}(1/K)$ Convergence and Low Sample Complexity for Single-Timescale Policy Evaluation with Nonlinear Function Approximation
Authors: Zhuqing Liu
Xin Zhang
Jia Liu
Zhengyuan Zhu
Songtao Lu
Venue: Submitted to ICLR 2023 (2023)

Abstract: 	Learning an accurate value function for a given policy is a critical step in solving reinforcement learning (RL) problems. So far, however, the convergence speed and sample complexity performances of most existing policy evaluation algorithms remain unsatisfactory, particularly with {\em non-linear} function approximation. This challenge motivates us to develop a new variance-reduced primal-dual method (VRPD) that is able to achieve a fast convergence speed for RL policy evaluation with nonlinear function approximation. To lower the high sample complexity limitation of variance-reduced approaches (due to the periodic full gradient evaluation with all training data), we further propose an enhanced VRPD method with an adaptive-batch adjustment (VRPD$^+$). The main features of VRPD include: i) VRPD allows the use of {\em{constant}} step sizes and achieves the $\mathcal{O}(1/K)$ convergence rate to the first-order stationary points of non-convex policy evaluation problems; ii) VRPD is a generic {\em{single}}-timescale algorithm that is also applicable for solving a large class of non-convex strongly-concave minimax optimization problems; iii) By adaptively adjusting the batch size via historical stochastic gradient information, VRPD$^+$ is more sample-efficient in practice without loss of theoretical convergence rate. Our extensive numerical experiments verify our theoretical findings and showcase the high efficiency of the proposed VRPD and VRPD$^+$ algorithms compared with the state-of-the-art methods.

Under review as a conference paper at ICLR 2023
ON O(1/K) CONVERGENCE AND Low SAMPLE COM- PLEXITY FOR TION WITH NONLINEAR FUNCTION APPROXIMATION
POLICY EVALUA-
Anonymous authors Paper under double-blind review
ABSTRACT
Learning an accurate value function for given policy is critical step in solving reinforcement learning (RL) problems. So far, however, the convergence speed and sample complexity performances of most existing policy evaluation algorithms remain unsatisfactory, particularly with non-linear function approximation. This challenge motivates us develop a new variance-reduced primal-dual method (VRPD) that is able to achieve a fast convergence speed for RI. policy evaluation with nonlinear function approximation. To lower the high sample complexity limi- approaches (due to the periodic full gradient evaluation
tation of variance-reduce with all training data), we further propose an enhanced VRPD method with an adaptive-batch adjustment (VRPD*). ). The main features of VRPD include: i) vRPD allows the use of constant step sizes and achieves the O(1/K) K) convergence to the first-order stationary points of non-convex policy evaluation problems; ii) VRPD is generic single-timescal algorithm that is also applicable for solving large class of non-convex strongly-concnt minimax optimization problems; iii) By adaptively adjusting the batch size via historical stochastic gradient information, VRPD is more sample-efficient empirically without loss of theoretical conver- gence rate. Our extensive numerical experiments verify our theoretical findings and showcase the high efficiency of the proposed VRPD and VRPD* algorithms compared with the state-of-the-arr methods.
INTRODUCTION
In recent years, advances in reinforcement learning (RL) have achieved enormous successes in large number of areas, including healthcare (Petersen et al. 2019, Raghu et al., 20176), financial recommendation (Theocharous et al. 2015), resources management [Mao et al. 2016 Tesauro et al. 2006) and robotics (Kober et al. 2013) Levine et al., 2016; Raghu et a 2017aa) to name just a few. In RL applications, current state, performing a policy-basee based action, receiving a reward, and transition to the next state. A key step in many RL algorithms is the policy evaluation (PE) problem, which aims to learn the value function that estimates the expected long-term accumulative reward for a given policy. Value functions not only explicitly provide the agent's accumulative rewards, but could also be utilized to update the current policy so that the agent can visit valuable states more frequently (Bertsekas) Tsitsikli 1995 Lagoudakis & Parr 2003). In RL policy evaluation, two of the most important performance metrics are convergence rate and sample complexity. First, since policy evaluation subroutine of an overall RL task, developing convernng policy evaluation algorithms is of critical importance to the overall efficiency of RI.. Second, due to the challenges in collecting a large number of training samples (trajectories of state-action pairs) for policy evaluations RI,, reducing the number of samples (i.c., sample complexity) can significantly alleviate the burden of data collection for solving policy evaluation problems. These two important aspects motivate us to pursue fast-converging policy evaluation algorithm with low sample-complexity in this paper.
agent interacts with an environment and repeats the tasks of observing the
Among various algorithms for policy evaluation, one of the simplest and most effective methods is the temporal difference (TD) learning approach (Sutton (988). Instead of focusing the predicted and actual outcomes, the key idea the TD learning is to make the difference between temporally successive predictions small. Specifically, the TD learning approach learns the value function by

---

Under review as a conference paper at ICLR 2023
using the Bellman equation to bootstrap from the current estimated value function. To date, there have been many algorithms proposed within the family of TD learning (Dann et al.] 2014). However, most of these methods suffer from either unstable convergence performance, (c.g., TD(A) (Sutton 1988) for off-policy training) or a high computational complexity (e.g.. least-squares temporal difference (LSTD) (Boyan 2002) Bradtke & Barto 1996)) in training with massive features. The limitation of these early attempts is largely due to the fact that they do not leverage the gradient-oracle in policy evaluation. Thus, in recent years, gradient-based policy evaluation algorithms have become increasingly prevalent. However, the design of efficient gradient-basee policy evaluation algorithm is a non-trivial task. On one hand, as an RL task becomes more sophisticated, it is more appropriate to utilize nonlinear function approximation (e.g., deep neural network (DNN)) to model the value function. However, when working with nonlinear DNN models, the convergence performance the conventional single-timescale TD algorithms may not be guaranteed (isitsiklis & Van Roy| 1997). To address this issue, some convergent wwo-timescale algorithms (Bhatnagar et al. 2009; Chhng et al., 2018) have been proposed the expense of higher implementation complexity. On the other hand, modern policy evaluation tasks could involve a large amount of state transition data. To perform policy evaluation, algorithms typically need to calculate full gradients that require all training data (e.g., gradient temporal difference (GTD) (Sutton et al. 2008) and TD with gradient correction (TDC) (Sutton al., 2009b)), which entails high sample complexity. So far, existing works on PE are either focus on linear approximation (GTD2 (Sutton et al., 2009b), PDBG (Du et al. 2017). SVRG (Du al. 2017). D. SAGA (Du et al., 2017)) or have such a slower convergence performance (STSG QQu et al. 2020 VR-STSG (Qiu et al. 2020), nPD-VR (Wai et al. 2019)) (see detailed discussions in Section. 2 In light of the above limitations, in this paper, we ask the following question: Could
we develop an efficient single- -ieesslle gradient-base algorithm for policy evaluation based on nonlinear function approximation?
In this paper, we give an affirmative answer the above question. Specifically, we propose an efficient gradient-based variance-reduced primal-dual algorithm (VRPD) to tackle the policy evaluation problem with nonlinear function approximation, which we recast minimax optimization problem. Our VRPD algorithm admits a simple and elegant single- iinle-timescale algorithmic structure. Then, we further enhance VRPD by proposing VRPD* which uses adaptive batch sizes to relax the periodic full gradient evaluation to further reduce sample complexity. The main contribution of this paper is that our proposed algorithms achieve an (1/K)) K) convergence rate (K is the number of iterations) with constant step-sizes for policy evaluation with nonlinear function approximation, which is the best-known result in the literature thus far. Our main results are highlighted follows:
By utilizing variance reduction technique, our VRPD algorithm allows constant step-sizes and enjoys a low sample complexity. We show that, under mild assumptions and appropriate parameter choices, VRPD achieves ( / K) convergence rate the first-order stationary point of class of nonconvex-stronglly wwwrronglyycoccvveCCSS..
minimax problems, which is the best-known result in the literature. To achieve this result, our convergence rate analysis introduces new proof techniques and resolves an open question and clarifies an ambiguity in the of-te-of-the-ar convergence analysis of VR-based policy evaluation methods (see 2nd paragraph in Section 2.1 for more discussions).
VRPD+ significantly improves the sample complexity of the VRPD algorithm for policy evaluation with massive datasets. Our VRPD* siaaptive-bacch VRPD) algorithm incorporates historical information along the optimization path, but does not involve backtracking and condition verifica- tion. We show that our VRPD+ algorithm significantly reduces the number of samples and the computation loads of gradients, thanks to our proposed adaptive batch size technique that is able to avoid full gradient evaluation.
Our extensive experimental results also confirm that our algorithms outperform the state-of-the ohe art condiinttbaseed policy evaluation algorithms, and our VRPD + can further reduce the sample complexity compared to the VRPD algorithm. It is worth noting that, although the focus of our work is on RL policy evaluation, our algorithmic design and proof techniques contribute to the area of minimax optimization and could be of independent theoretical interest.
2 RELATED WORK
1) TD Learning with Function Approximation for Policy Evaluation: TD learning with function approximation plays vital role in policy evaluation for RL. The key idea of TD learning is to
2

---

Under review as a conference paper at ICLR 2023
Table 1: Algorithms comparison for solving policy evaluation. M the size of the dataset; K is the
total iteration.
Algorithm
Function Approx.
Problem
Step-size
Convergence Rate
GTD2 Sutton et al.
2009b)
Linear
((1)
PDBG Du et al. 2017
Linear
Convex-Concan
((1)
O(/K)
SVRG Du et al. 2017
Linear
Convex-Concave
0(1)
O(1KK)
SAGA Du al. 2017)
Linear
Convex-Concane
0(1)
O(1/K)
STSG Qiu et al. 2020)
Nonlinear
Stochastic/NCSC
((1)
(11/K)/)
VR-STSG Qiu et al.
(2020)
Nonlinear
Stochastic/ NCSC
0(1)
(L/K3//3)
nPD-VR Wai et al.
(2019)
Nonlinear
Finte-Sum / (CSCOO(1/M)) Conjectured O(1/K)
[RrD
Nonlinear
Finte-Sume NCSC
O(1)
O(1/K)
VRPD+ [Ours.]
Nonlinear
Finte-Sum NCSC O(1)
O(1/K)
Whether nPD-VE -D achieves O(1/K) convergence rate remains an open question. See the detailed discussions in Sections and
minimize the Bellman error for approximating the value function. So far, most existing TD learning
algorithms with theoretical guarantees focus on the linear setting (e.g., (Sutton et al., 2009a Srikant
& Ying 2019 Xu et al. 2020b; Stankovic & Stankovic, 2016 Touati et al. 2018 Doan al.)
(201)). Liu ct al. (2015), Macua et al. (2014). and Zhang & Xiao (2019) provided a finite-time
analysis for the proposed distributed TD(O) and showed that the convergence rate of their algorithm is
((1/K). It was shown in Du et al. (2017) that policy evaluation with linear function approximation by TD(O) can be formulated as a strongly convex-concave or convex-concave problem, and can be solved by primal-dual method with a linear convergence rate. However, the linearity assumption cannot be applied in a wide range of policy evaluations with nonlinear models. TD learning with nonlinear (smooth) function approximation is far more complex. Maci et al. (2009) was among the first to propose a general framework for minimizing the generalized mean- mean-squaree suuarnd projected Bellman error (MSPBE) with smooth and nonlinear value functions. However, they adopted two- timescale step-sizes but only obtained a slow convergence performance. Other TD methods with nonlinear function approximations for policy evaluations include (Wang et al. 2017 2016). Qiu et al. (2020) also investigated nonlinear TD learning and proposed two single-timescale first-order stochastic algorithms. However, the convergence rate of their STSG and VR-STSG are ((1/K//4) and O(1 ((1//K//3), while our VRPD algorithm achieves a much faster (1/KK) convergence rate.
In policy evaluation with loneir function approximation, the state-of of-the-art and the most related work to ours is (Wai et al. 2019), which showed that minimizing the generalized MSPBE problem equivalent solving
(NCSC) minimax optimization problem via the Fenchel's duality. However, their best convergence results only hold when the step-size is O(+) ). where M the size of the dataset. This is problematic for modern RL problems with a large state-action transition dataset. More importantly, although their convergence theorem appears to have 1/2 factor (K being the total number of iterations), their convergence rate bound is in the
form of p(N) Constant1 (cf. Theorem 1, Eq. (26) in Wai et al. (2019)). Notably, the F(K) term in K. K-Cossiant2
the denominator in Eq. (26) inherently depends on the primal and dual values g(K) and (K) in the K-th iteration, respectively.
is unclear whether w (K) can be bounded in (Wai et al., 2019). hence leading to an ambiguity in guaranteeing an (1/KK) convergence rate. Thus, whether an O(1/K) convergence rate is achievable in single-timescale policy evaluation with nonlinear function approximation and constant step-sizes remains an open question thus far. The key contribution and novelty in this paper is that we resolve the above open question by proposing two new algorithms, both achieving an (1/ convergence rate. To establish this result, we propose a new convergence metric (cf. Eq. (9) in Section 4... which necessitates new proof techniques and analysis. For easy comparisons, we summarize our algorithms and the related works in Table
2) Relations with NCSC Minimax Optimization: Although the focus of our paper is on RL policy evaluation, our algorithmic techniques are also related to the area of NCSC minimax optimization due to the primal-dual MSPBE formulation (cf. Eq. 2 in Section 3). Early attempts in (Nouiehed et al.) 2019 Lin et al. 2020b) developed gradient descent-ascent algorithms to solve the NCSC minimax problems. However, these methods suffer from a high sample complexity and slow convergence rate. To overcome this limitation, two variance- reeducttoo algorithms named SREDA (Luo et al.) 2020) are proposed for solving NCSC minimax problems, which shares some similarity our work.
3

---

Under review as a conference paper at ICLR 2023
Later, Xu et al. (2020a) enhanced SREDA to allow bigger step-sizes. However, our algorithms still differ from SREDA in the following key aspects: (i) Our algorithms are single-timescale algorithms, which are much easier to implement. In comparison, SREDA is two-timescale algorithm, where solving an inner concave maximization subproblem is needed. Thus, to a certain extent, SREDA can be viewed as a triple-loop structure, and hence the computational complexity of SREDA is higher than ours; (ii) In the initialization stage, SREDA uses the PiSARAH, which is a subroutine that aims help the SREDA algorithm achieve the desired accuracy at the initialization step and can be seen as an additional step to solve an inner concave maximization subproblem. Thus, SREDA has a higher computation cost than our paper. (iii) The number of parameters in SREDA are far more than ours and it requires the knowledge of the condition number to set the algorithm's 's parameters for good convergence performance. By contrast, our algorithms only require step-sizes a and /3 to be sufficiently small, which is easier to tune in practice. (iv) SREDA does not provide an explicit convergence rate in their paper (it is unclear what their convergence rate is from their proof cither). Yet, we show that our VRPD in theory has lower sample complexity than that of SREDA.
Another related work in terms of NCSC minimax optimization is Zhang et al. 202T), which also provided sample complexity upper and lower bounds. However, there remains gap between the sample complexity lower and upper bounds in (Zhang et al., (02T). By contrast. the sample complexity of our VRPD algorithm matches the lower bound O(M + 2 in (Zhang et al. 2021). which is the first in the literature. Furthermore, the algorithm contains subproblem (cf. Line 6 of Algorithm I in Zhang et al. (202I)). Solving such a subproblems in the inner loop incurs high computational costs. Due this reason, the algorithm in (Zhang al. 2021) had to settle for an inexact solution, which hurts the convergence performance in practice. In contrast, our algorithm does not have such a limitation.
inner minimax
3 PRELIMINARIES AND PROBLEM STATEMENT
We start from introducing the necessary background of reinforcement learning, with a focus on the policy evaluation problem based on nonlinear function approximation.
1) Policy Evaluation with Nonlinear Approximation: RL problems are formulated using the Markov decision process (MDP) framework defined by a five-tuple the state space and A is the action space; P S x A - S represents the transition function, which specifies the probability of one state transitioning to another after taking an action; R denotes the space of the received reward upon taking an action a E A under state 8 E S (in this paper, we assume that the state and action spaces are finite, but the numbers of states and actions could be large); and 7 E [0, 1) is time-discount factor.
R], where S denotes
For RL problems over an infinite discrete-time horizon {1 E N), the learning agent executes an action a, according to the state st and some policy S - A. The system then transitions into new random state St+1 in the next time-slot. Also, the agent receives a random reward R (st, az). The trajectory generated by a policy æ is sequence of state-action pairs denoted as (51.01-5202.--- The goal of the agent is to learn an optimal policy x" to maximize the long-term discounted total reward. Specifically, for a policy æ (could be a randomized policy), the expected reward received by the agent at state in any given time-slot can be computed as 18t (*+) = Ea-x(-le) | (st, a)] The value function V (sp)= = E 1E 7 R (st) So. π indicates the long-term discounted reward of policy π over an infinite horizon with the initial state at so E S. Also, the Bellman equation implies that
V=(-): ((s)-TVV Vs)),, (s), where T [(s A E[RT + >ss(') ~ T(-(s), s' P(-ls, a)] denotes the Bellman operator. In RL, the agent's ' goal is to determine an optimal policy πt that maximizes the value function V (s) from any initial state s.
However, the first obstacle in solving RL problems stems from evaluating V=(-) for given π since P(-Is,a) is unknown. Moreover, it often infeasible to store V since the state space S could be large. To address these challenges, one popular approach in RL is to approximate V* (-) using a family of parametric and smooth functions in the form of VT(() A3 Vg- (-), where 0= E IRd a d-dimensional parameter vector. Here, θ is a compact subspace. For notational simplicity, we will omit all superscripts "T" whenever the policy π is clear from the context. In this paper, we focus on nonlinear function approximation, i.c., Vo(+) S R is nonlinear function with respect to (w.I..)) 0. For example, V-)-) could be based on a 0 parameterized nonlinear DNN. We assume that the gradient and Hessian of Vo(+) exist and are denoted as: g)) VoVo(s) E Rd. Ho(s)) Vo((s) E Rdddd
4

---

Under review as a conference paper at ICLR 2023
Our goal is to find the optimal parameter 0* R that minimizes the error between Vo- (+) and V(-).
This problem can be formulated as minimizing the mean-squared projected Bellman error (MSPBE) of the value function as follows (Liu et al. 2018):
M) 2 (
TI 2- Do ge( - (w, E (T Vol
max WEB!
(I)
where (.) is the stationary distribution of under policy л and D Eg (go(() ($) (s)] Rdxd
2) Primal-Dual Optimization for MSPBE: It is shown in (Liu et al. 2018) (cf. Proposition 1) that
minimizing M) in (I) is equivalent to solving a primal-dual dual minimax optimization problem:
min max ((O,w), GER WERd
(2)
where L(O, w) A (wo, (g)D)))))) (7* - (o) 1>>=EE=D=0000 ( Since the
distribution (+) is unknown and the expectation cannot be evaluated directly, one often considers the following empirical minimax problem by replacing the expectation in L(O, w) with a finite sample average approximation in the stochastic objective function based on an M-step trajectory, i.e.,
minger max L(O, w) minggee max M E L; w). where
(,(0,w) == (w. [R(s a,, 8,41) + (V (o( x go( 2
ge()))).
(3)
Solving the above empirical minimax problem for MSPBE constitutes the rest of this paper.
4 SOLUTION APPROACH
As mentioned in Section 3
based on an M- -tee trajectory {$1, a ... SM, aM, SM+1} generated by
some policy r,, our goal is to solve the empirical primal-dud and finite-sum optimization problem:
M Σ
1
min max OER WEW M
(,,,w)
min max ((O, w),
OER WEW
where W is assumed to be a convex constrained set (Problem becomes Problem 2 when W = )d. In our Appendix, we also discussed the min-max problem while 0 E θ. θ convex constrained set. See details in Appendix. [2] Note that Problem (4) could be non-convex (e.g.,
DNN-based nonlinear approximation). Let (()) A mmaxwew L(O, w) Then, we can equivalently rewrite Problem as follows: mingeRs max L(0, w) min J()).
Note from that C(O, w) is strongly concave w.r.t. w, which guarantees the existence and unique- ness of the solution the problem max L(0, w), v0 R Then, given 0 E Ed, we define the following notation: w w0() := argmax L(B, w). Thus, J(0) can be further written as:
WEW
((0) = [(0, w*) = max C(0, w). WEW
(5)
The function J(0) can be viewed as a finite empirical version of MSPBE. We aim to minimize (()) by finding the stationary point of L(O, w). To simplify the notaion, use w" to denote w" w0)). Note that if D in Eq. (1) is positive definite, Problem (4) is strongly concave in w, but non-convex in 0 in general due the non-convexity of function Vo. Thus, the stated primal-dual objective function is NCSC optimization problem. In this paper, we make the following assumptions:
Assumption (μ--Strongly Concavity). The differentiable function L(O, w) is ju-strongly concave in w: if L(O, w) & L(A, w') + VuL(f, w') T (w - -²) / || - w'1 Vw, w' E Rdd. 1u > and any
fixed 0 E Rdd The above mentioned condition is equivalent to: : V (0,w))
C w w/)ll 2
ul|w w'll, Yw, w' E Rdd Similar proofs can be found in Lemma 2 and 3 in Zhou (0118)
Assumption 2 (mootththhssss) For i 1, ..... M. both gradient VeC.(0, w) and V (0,,w) are -mosoh. That is, for all 0,0 O' IRd and w, w' E Rdd there exists constant L, such that [V, VL, w'll < Ly (I10 -00 0'll |||
||I -wll).
5

---

Under review as a conference paper at ICLR 2023
Algorithm 1 The Variance-Reduced Primal-Dual Stochastic Gradient Method (VRPD).
Input: An M -tsppp trajectory of the state-action pairs {s1, 01 82, 02 SM. aM, SM+1) generated from a given policy; step sizes a; B 2 0; initialization points 0 E R.. w E W.
Output: (O(K), (()), where K is independently and uniformly picked from {1, K]; do
1: for k= 0, 1, 2, ...
If mod k. q) = O, compute full gradients G G as in Eq. 66
2:
3: Otherwise, select S samples independently and uniformly from [MT. and compute gradients as
in Eq. 7
4:
Perform the primal-dual updates to obtain the next iterate ((++1), (k++)) as in Eq. (8)
5: end for
Assumption 3 (Bounded Variance). There exists a constant σ > 0 such that for all 0 IR w E Rd N E VoL. (o)( ? < a² and 37 E [V
w))l - a².
In the above assumptions, Assumption D satisfied if the number of samples M is sufficiently large and coupling with the fact that the matrix D is positive definite. To see that, note that μ Amin (D) > 0, E Rddd and D tends be full-rank M increases. Thus, as soon as we find μ > when M is sufficiently large, this is independent of M as M continues to increase. Assumption is standard in the optimization literature. Assumption i also commonly adopted for proving convergence results of SGD- and VR VR-based algorithms, or algorithms that draw mini-batch of samples instead of all samples. Assumption set condition and common for stochastic approximation algorithms for minimax optimization (Qiu (ct al., 2020; Lin et al. 2020a). Assumptions [H3 are also general assumptions often used in temporal difference (TD) problems (see, e.g., (Qiu al. 2020 Wai et al. 2019). With these assumptions, we are now in position to present our algorithms and their convergence performance results.
where D E, Vo
3 is guaranteed to hold under the compact
4.1 THE VARIANCE- RRDDUCED PRIMAL-DUAL METHOD
In this section, first present the variance-reduced primal-dual (VRPI)) algorithm for solving policy evaluation problems, followed by the theoretical convergence results. Due to space limitation, we provide proof sketch in the main text and relegate the proof to the supplementary material.
1) Algorithm Description:
The full description of VRPD is illustrated in Algorithm 1 for every q iterations, the algorithm calculates the full gradients as follows:
In VRPD,
G
Σ (eL,(O
(k));;
G
Σ
(O(k( (()))
(8)).
(6)
M
M
iEM
In all other iterations, VRPD selects batch of samples S and computes variance-reduced gradient estimators as:
G( 1
[S] Lies (O(K) (())) - VoL, 1), w(k-)) + 1)
(7a)
G(h)
1 3. Eies ((((k) w(l)) (Olk()())) (1=-1)) G 1))
(7b)
The estimators in are constructed iteratively based on the previous update information (0(k())-11) 1)) (resp. (V=L,(0(k-1) w(k-1)) ) and ((--1) (resp. Gle-1)), VRPD up- dates the primal and dual variables as follows:
@(k+1) = (k)) BG
(8a)
((++l) = (w( + aaGl)) = argmin| - (k) k) + DR
(8b)
wen
where the parameters and B are constant learning rates for primal and dual updates, respectively. 2) Convergence Performance: this paper, we propose a new metric for convergence analysis:
(k) := ()(((()) 2| + (k) w (
The first term in (9) measures the convergence of the primal variable 0. As common in non- convex optimization analysis, [[]]|2 indicates that 0 is first-order stationary point

---

Under review as a conference paper at ICLR 2023
(FOSP) of Problem 4. The second term in 9 measures the convergence of (h) to the unique maximizer w for L(Ok,-) Note that if Problem (4) is unconstrained in dual (i.e., w E IR&))
it follows from Assumption and [V w ())? = 0 that M) 2 [[VJ(O(k)) 1|2
17 vl ((0()) (11 We now introduce the notion of the approximate first-order stationary
points. We say that point {0, w) is an e-stationary point of function L(O, w) if 2T S é satisfied.
Remark. Several important remarks on the connections between metric () and the conven- tional convergence metrics in the literature are in order. A conventional convergence metric in the
literature for NCSC minimax optimization is (((()) I|2 (Lin et al. 2020a Luo et al. 2020 Zhang et al. 2021), which is the first term of (*) and measures the convergence of the primal variable under given dual variable w. This is because [[ 0 implies that 0 is a FOSP. The novelty
in our convergence metric is the second term in (1)),, which measures the convergence of wy to the unique maximizer w for :),,
Another conventional convergence metric in the literature of minimizing the empirical MSPBE problem is ([ strong-concave minimax optimization problem is unconstrained in dual (i.e., w R"), it follows from
[Vw, w) (Tsitsiklis & Van Roy 1997). Since the nonconvex-
Lipschitz-smmoothness in Assumption 2 and (()(k))) w (0(())) 1|2 = 0 that (((()) )12
(0(
T. (() (1) Therefore, the second term in our (k) (2]lw( ((((())))((()))))) (0(+)) is an upper
bound of the second term in this conventional metric ([V w|) Thus, (/) w (0())) is stronger metric than [(, w) in the sense that an O(1/K) convergence rate under (D((k) implies an (11/K) convergence rate of the conventional metric, but the converse is not true. Moreover, the benefit of using ( - w (1² in our ()()) is that its special structure allows us to prove the O(1/K) convergence, while the second term in the conventional metric fails.
With proposed convergence metric in p have the following convergence result:
Theorem 1. Under Assumptions
choose step-sizes: a S min (,t, 3417
2y } and 33 S
min
Let q= VM and S v M, it holds that:
Th 2(h 11777)
8/1727
8.3413
1
K
E
pon
(k)
1
16L7
C2 +
2 C1 0
2
1 (
K
K min (1, 1.3.)
app
k=0
where C1 4 [[J((())] E[J(O(())] and C2 e (0(l)(((()) w 1011)))
Corollary 2. The overall stochastic sample complexity is O(VM + M). Note that L denotes the condition number.
Remark. Theorem states that VRPD achieves an ((1/K) convergence rate to an c-FOSP. The most challenging part in proving Theorem [ stems from the fact that one needs to simultancously evaluate the progresses of the gradient descent in the primal domain and the gradient ascent in the dual domain of the minimax problem.
Toward this end, the nPD-VR method in Wai et al. 2019) employs || (((())))))) (A) in their metric to evaluate convergence. However, this approach yields term F(K) e E(C(O()) (") L(O(K), (KK) in their convergence upper bound in the form of ((F(K)/K (cf. Theorem 1, Eq. (26) in Wai et al. 2019). Since F(K) depends on K, it is unclear whether or not the 4PD-VR 2019 can achieve an (L/K)) convergence rate. This unsatisfactory result (9) to evaluate the convergence of our VRPD algorithm. The first part of our convergence metric | ((((k)) I|2 measures the stationarity gap of the primal variable, while the second part 2 (k) w (O(k)) measures the dual optimality gap. Consequently, we bound per-iteration change J()) instead of the function (()(M), (k)). This helps us avoid the technical limitations of (Wai et al.) 2019) and successfully establish the O(1/K) convergence rate, hence resolving an open problem this area.
method in Wai et al.
motivates us to propose a new metric (k) in Eq.
Remark. VRPD adopts large (11) (i.e., constant) step-size compared the O(1/M) step-size of nPDDVV VR (Wai et al. 2019), where M is the dataset size. This also induces a faster convergence. Also, VRPD's estimator uses fresher information from the previous iteration, while VR-STSG QQui
7

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Adaptive-batch VRPD method (VRPD*).
Input: trajectory of the state-action pairs {s1, di, 82, az.... SM.UM, given policy; step sizes a, B 2 0; initialization points 0 θ w R
uM, 8M+1] generated from
Output: (Ø(K), w ))), where K independently and uniformly picked from f1,.... .K}; K - do
1: for k = 0. 1, 2,
2: If mod(k; q) = 0, select NV, indices independently and uniformly from [M] as in Eq. 10
and calculate stochastic gradients as in Eq. (II);
3: Otherwise, seleet S independently and uniformly from [M]] Compute gradients as in Eq.
4:
Perform the primal-dual updates in Eq.
5: end for
et al. 2020) and nPD-VR (Wai et al. 2019) only use the information from the beginning of q-sized windows. Collectively, VRPD makes a considerably larger progress than state-of-the-ar algorithms
QQuu et al.] 2020 Wai et al. 2019).
4.2 THE SRAPIVE--ATCH VRPD METHOD (VRPD*)
Note that VRPD still requires full gradients every q iterations, which may entail a high sample complexity. Upon closer observations, we note that accurate gradient estimation plays important role only in the later stage of the convergence process. This motivates us to further lower the sample complexity of VRPD by using adaptive batch sizes. Toward this end, we propose adaptive-bated batch VRPD method (VRPD*) to lower the sample complexity of the VRPD algorithm in Algorithm
Algorithm Description: The full description of VRPD* is illustrated in Algorithm 2 In VRPD*, our key idea is to use the gradients calculated in the previous loop to adjust the batch size N, of the next loop. Specifically, VRPD+ chooses N₂, in the k-th iteration
N₂ () -,00 --ccc-cc1-__00 MM.
(10)
where Cy, Ce > c for certain constant c, M denotes the size of the dataset and a² is the variance bound, |
is the stochastic gradients calculated in the previous iterations. In VRPD*, for every q iterations, we select N₂ samples independently and uniformly from [M] and compute gradient estimators as follows:
and ((++11 = Ei=
GB
VoL.( )
G(k)
1
Σ (O (t)) S,,
(11)
A
LV
For other iterations, VRPD+ is exactly the same as VRPD. Next, we will theoretically show that such an adaptive batch-size scheme still retains the same convergence rate, while achieving an improved sample complexity.
2) Convergence Performance: For VRPD*, we have the following convergence performance result:
Theorem 3. Under Assumptions 3
choose step-sizes: a S min
1 at,," 342; +2pa } and , s
2r
min L # 8/1717 8/3413
Let y = v M,S S VM and e z (2881) + 8) in
VRPD*, where cy 2 c for some constant B[J(0()) and C. (Bill=((00)) w () it holds that:
4K +
G8 Sp
With constants C₁ e [O)
(1) < K (1,
K 2
16L3
C2 -
= - 1 + 2
K
K
Corollary 4. The overall stochastic sample complexity is O(v OW M). k = L5/1 denotes the condition number.
Remark. From Theorem 3 can be seen that VRPD achieves the same convergence rate as that of VRPD. Since we choose the subsample set N,, instead of full gradient calculation in V achieves a much lower sample complexity compared to VRPD. Additionally, the convergence performance of VRPD* is affected by the constant Ke which is due to the use of the adaptive batch size in each outer-loop of VRPD*. Also, it can be observed that the algorithm convergence rate is affected by the carefully chosen step-sizes a and 8. because either a too small or too large step-size may have negative impact on the convergence of the algorithm.
8

---

Under review as a conference paper at ICLR 2023
5193
BTed
(P0 VR
VR 57935790
nRDvV
VR50153
2
VR-ST5G
5150
VR-ST83
VAPO
Ep
Eprooee
Epeoder
Figure MountainCar-v0 environment.
Figure Cartpole-vo environment.
YPPO
VIPО
(19 .I,, LRwn
VRPD
VRPD
a of
Figure 3: MountainCar-vO environment.
Figure 4: Cartpole-vO environment.
Remark, The proof of Theorem 3 follows from a similar approach to the proof of Theorem The key difference and most challenging part of proving Theorem B stem from the relaxation (V))(((()) (K) - k Assumption 3 and the selected NN in Eq. (10), are able to derive outer-loop bounds for primal and dual gaps, respectively. We refer readers to the Appendix for the details of the complete proof.
112 and [ w(()) - > ||2.
Thanks to the bounded variance in
EXPERIMENTAL RESULTS
In this section, we conduct numerical experiments to verify our theoretical results. We compare
work with the basic stochastic gradient (SG) method (Lin et al., 20206) and three state-of-the-ar
algorithms for PE: nPD-VR (Wai et al. 2019), STSG (Qiu al. (020) and VR-STSG (Qiu et al.
2020). Due to space limitation, we provide our detailed experiment setting
Mountaincar.v0
Numerical Results: We set the constant learning rates a 10-3, 8
0.175
0.150
10-1, mini-batch size q [VM], constant c 32 and solution accuracy
0.125
é = 10-3 First, we compare the loss value and gradient norm per- formance based on MountainCar-voe and Cartpole-vO with nPD-VR, SG, STSG, and VR-STSG in Figs. [ We the constraint W = [0, 10]" and initialize all algorithms at the same point, which generated ran- domly from the normal distribution. We can see that VR-STSG and
0.100
0.075
Trojectory length
Cartpole VD
0.25
Lecar
nPD-VR slowly converge after 40 epochs, while STSG and SG fail to converge. VRPD converges faster than all the other algorithms with the same step-size values. As for Cartpole-vO, we clearly see a trend of approaching zero-loss with VRPD. These results consistent with our theoretical result that one can use a relatively large step-size with VRPD, which leads to faster convergence. Also, we compare the sample complexity of VRPD and VRPD in MountainCar-vOl and Cartpole-vO, and the results are shown in Figs. 3 and 4 respectively. We can see that VRPD+ converges to the same level with much fewer samples than VRPD does. Next, we compared the mean squared error(MSE) between the ground truth value function and the estimated value function over 10 independent runs with linear approximation and nonlinear approximation. In Fig. 5 with the same amount of parameter size, nonlinear approximation always achieves smaller MSE than linear approximation (Du et al. 2017). Further experiments on the performance of J (0) are shown the supplementary material.
0.20
0.15
0.10
600 1000 Trajectory length
200
Figure 5: MSE compari- son with 10 trials.
6 CONCLUSION
In this paper, we proposed and analyzed two algorithms called VRPD and VRPD+ for policy evaluation with nonlinear approximation. The VRPD algorithm is based on simple single-timescale framework by utilizing variance reduction techniques. The VRPD algorithm allows the use of constant step-sizes and achieves an O(1/K) convergence rate. The VRPD* + algorithm improves VRPD by further applying an adaptive batch size based on historical stochastic gradient information. Our experimental results also confirmed our theoretical findings in convergence and sample complexity.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Reza Babanezhad, Mohamed Osama Ahmed, Alim Virani, Mark Jakub Schmidt, and Scott Sallinen. Stop wasting my gradients: Practical svrg. arXiv preprint arXiv:1511.01942. 2015.
Dimitri P Bertsekas and John Tsitsiklis. Neuro-dynamic programming: an overview. In Proceedings of 1995 34th IEEE Conference Decision and Control, volume 1, pp. 560-564. IEEE, 1995.
Shalabh Bhatnagar, Doina Precup, David Silver, Richard Sutton, Hamid Maei, and Csaba Szepesvári. Convergent temporal-differtt -inforal-differrece learning with arbitrary smooth function approximation. In Advances Neural Information Processing Systems, pp. 1204-1212, 2009.
Justin A Boyan. Technical update: Least-squares temporal difference learning. Machine learning, 49
(2-3):233-244) 246, 2002.
Steven J Bradtke and Andrew Barto. Linear squares algorithms for temporal difference learning. Machine learning, 22(1-3):33-57, 1996.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint 1606.01406 2016.
Wesley Chung, Somjit Nath, Ajin Joseph, and Martha White. Two-timescale networks for nonlinear value function approximation. In International Conference on Learning Representations, 2018
Christoph Dann, Gerhard Neumann, Jan Peters, et al. Policy evaluation with temporal differences: A survey and comparison. Jourmal of Machine Learning Research, 15:809-88: -839, 2014.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1478, 2021.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. arXiv preprint arXiv: 1407.0202. 2014.
Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-time analysis of distributed (0) with linear function approximation on multi-agent reinforcement learning. In International Conference Machine Learning, pp. 1626-1633 PMLR, 2019.
Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou Stochastic variance reduction methods for policy evaluation. arXiv preprini (00iv:/772.0994 2017.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex opti- mization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pp. 689-699, 2018
Kaiyi Ji, Zhe Wang, Bowen Weng, Yi Zhou, Wei Zhang, and Yingbin Liang. History-grradien aided batch size adaptation for variance reduced algorithms. In International Conference on Machine Learning, pp. 4762 4772. PMLR, 2020.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in noncomvex-noncomcaa minimax optimization? In International conference on machine learning, pp. 4880 4889. PMLR, 2020.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pp. 315-323, 2013.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in roboties: A survey. The International Journal of Robotics Research, 12111:113811274, 2013.
Michail G Lggoudaiss and Ronald Parr. Least-squares policy iteration. Journal of machine learning research, 4(Dec): 107-1149, 2003.
Lihua Lei and Michael Jordan. On the adaptivity stochastic gradient- gradient-basedd optimization. SIAM Journal Optimization, 30(2):14331500, 2020.
10

---

Under review as a conference paper at ICLR 2023
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum sum optimization via Scsg methods. In Guyon, U. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30, pp. 3348-23555 Curran Associates, Inc., 2017.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 17(1):13341333, 2016.
Xiangru Lian, Mengdi Wang, and Ji Liu. Finite-sum composition optimization via variance reduced gradient descent. In Artificial Intelligence and Statistics, pp. 1159-1167. PMLR, 2017.
Tianyi Lin, Chengyou Fan, Mengdi Wang, and Michael I Jordan. Improved sample complexity for stochastic compositional variance reduced gradient. In 2020 American Control Conference (ACC), pp. 126-131. 131. IEEE, 2020a.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning, pp. 6083-6093. PMLR, 2020b.
Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Finite-sample analysis of proximal gradient td algorithms. UAL, pp. 504-513. Citeseer, 2015.
Bo Liu, Ian Gemp, Mohammad Ghavamzadeh, Ji Liu, Sridhar Mahadevan, and Marek Petrik. Proximal gradient temporal difference learning: Stable reinforcement learning with polynomial sample complexity. Journal of Artificial Intelligence Research, 63:461-494, 2018.
Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive ap- proximation for one-sided non-convex min-max problems: algorithms and applications. IEEE Transactions on Signal Processing, 68:3676-3691, 2020.
Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex -ertonnve--troolly--eee -trongly-coneave minimax problems. arXiv preprint arXiv:2001.03774 2020.
Sergio Valcarcel Macua, Jianshu Chen, Santiago Zazo, and Ali H Sayed. Distributed policy evaluation under multiple behavior strategies. IEEE Transactions on Automatic Control, 60(5):1260-122) 2014.
Hamid Reza Maei, Csaba Szepesvari, Shalabh Bhatnagar, Doina Precup. David Silver, and Richard S Sutton. Convergent temporal-difee -differennce learning with arbitrary smooth function approximation. In NIPS, pp. 1204-1212, 2009.
Oren Mangoubi and Nisheeth Vishnoi. Greedy adversarial equilibrium: an efficient alternative to nonconvex-nonconcee min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 896-909, 2021.
Hongzi Mao, Mohammad Alizadeh, Ishai Menache, and Srikanth Kandula. Resource management with deep reinforcement learning. Proceedings of the 15th ACM Workshop on Hot Topics in Networks, pp. 50-56, 2016.
Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
Maher Nouiched, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
Brenden Petersen, Jiachen Yang, Will S Grathwohl, Chase Cockrell, Claudio Santiago, Gary An, and Daniel M Faissol. Deep reinforcement learning and simulation path toward precision medicine. Journal of Computational Biology, 26(6):597-604, 2019.
Shuang Qiu, Zhuoran Yang, Xiaohan Wei, Jieping Ye, and Zhaoran Wang. tingle-timescale stochastic nonconvex-coneet optimization for smooth nonlinear td learning. arXiv preprint arXiv:2008. 10103, 2020.
11

---

Under review as a conference paper at ICLR 2023
Aniruddh Raghu, Matthieu Komorowski, Imran Ahmed, Leo Celi, Peter Szolovits, and Marzyeh Ghassemi. Deep reinforcement learning for sepsis treatment. arXiv preprint arXiv: 1.06602 2017a.
Aniruddh Raghu, Matthieu Komorowski, Leo Anthony Celi, Peter Szolovits, and Marzyeh Ghassemi. Continuous state-space models for optimal sepsis treatment-a deep reinforcement learning approach. arXiv preprint arXiv: 00420, 2017b.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
Scott Sievert. Improving the convergence of sgd via adaptive batch sizes. 1rXiv: 2019.
arXiv preprini
Chaobing Song, Zhengyuan Zhou, Yichao Zhou, Yong Jiang, and Yi Ma. Optimistic dual extrapolation for coherent non-monotone variational inequalities. Advances in Neural Information Processing Systems, 33:14303-14314, 2020.
Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation andtd learning. Conference on Learning Theory, pp. 2803-2830. PMLR, 2019.
Milos S Stankovic and Srdjan S Stankovic. Multi-agent temporal-difference learning with linear function approximation: Weak convergence under time-varying network topologies. In 2016 American Control Conference (ACC), pp. 167-172. IEEE, 2016.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, (1):9-44, 1988.
Richard S Sutton. Csaba Szepesvári, and Hamid Reza Maei. convergent o (n) algorithm for off-policy temporal-difference learning with linear function approximation. Advances in neural information processing systems, 21(21): 21(21):1609-16)
2008
Richard S Sutton, Hamid R Maci, and Csaba Szepesvári. A convergent o(n) temporal-difference algorithm for oof-po learning with linear function approximation. In Advances neural information processing systems, pp. 1609-1616, 2009a.
Richard S Sutton, Hamid Reza Maei, Doina Precup. Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast dradient-descent methods for temporal-differene learning with linear function approximation. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 993-1000, 2009b.
Gerald Tesauro, Nicholas K Jong, Rajarshi Das, and Mohamed Bennani. A hybrid reinforcement learning approach to autonomic resource allocation. In 2006 IEEE International Conference Autonomic Computing, pp. 65-73. IEEE, 2006.
Georgios Theocharous, Philip S Thomas, and Mohammad Ghavamzadeh. Personalized ad recommen- dation systems for life-time value optimization with guarantees. In Twenty-Fourth International Joint Conference Artificial Intelligence, 2015.
Ahmed Touati, Pierre-Luc Bacon, Doina Precup, and Pascal Vincent. Convergent tree backup and retrace with function approximation. In International Conference Machine Learning, pp. 4955-4964 PMLR, 2018.
John N Tsitsiklis and Benjamin Van Roy. Analysis of temporal-difiie difffree- learning with function approximation. In Advances in neural information processing systems. pp. 1075-1081, 1997.
Hoi-To Wai, Mingyi Hong, Zhuoran Yang, Zhaoran Wang. and Kexin Tang. Variance reduced policy evaluation with smooth function approximation. In Advances in Neural Information Processing Systems, pp- 5784-5795, 2019.
Mengdi Wang, Liu, and Ethan Fang. Accelerating stochastic composition optimization. arXiv preprint /607.070000000 2016.
12

---

Under review as a conference paper at ICLR 2023
Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-valle functions. Mathematical Programming, 161(1-2): 419-449, 2017.
Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A follow-the-ridge approach. arXiv preprint
2019.
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost: A class of faster variance-reduced algorithms for nonconvex optimization. arXiv preprint arXiv:1810. 10690, 2018.
Tengyu Xu, Zhe Wang, Yingbin Liang, and H Vincent Poor. Enhanced first and zeroth order variance reduced algorithms for min-max optimization. 2020a.
Tengyu Xu, Zhe Wang, Yi Zhou, and Yingbin Liang. Reanalysis of variance reduced temporal difference learning. arXiv preprint arXiv:2001.0189 2020b.
Junyu Zhang and Lin Xiao. A stochastic composite gradient method with incremental variance reduction. arXiv preprint arXiv:1906, 10186, 2019.
Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of minimax optimization. arXiv preprint arXiv:2103.15888, 2021.
arXiv preprint nonconvex--trooglyycoom
Xingyu Zhou. On the fenchel duality between strong convexity and lipschitz continuous gradient. 2018
13


Reviews:
[{"review_id": "xPqYC-9ioV", "reviewer": "Reviewer_vYTZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes two variance-reduced (VR) algorithms for a specific nonconvex strongly concave min-max problem obtained after reformulating the policy evaluation problem as a min-max game with nonlinear function approximation for the value function of the policy. They provide the first O(1/K) convergence and the possibility of removing the full gradient computation required in VR methods in certain iterations. ", "summary_of_the_review": "Overall, the paper makes some new contributions to both areas: VR algorithms for minmax problems and Policy evaluation in RL. Although, the paper does lack significantly in terms of literature review. It ignores the first area completely. The single-timescale part is fuzzy at best. The order of condition number in the sample complexity seems wrong to me. ", "strength_and_weaknesses": "The convergence results are provided for the first time and they look theoretically sound to me. \n\nWeakness:\n1. I am not sure about the role of \\Theta in the paper. It seems that it is mentioned in the last paragraph on page 4 and then dropped subsequently in the min-max formulation (2) or (4). Would the analysis work if such \\Theta is explicitly imposed on the min-max problem? Note that in such a case, the \\|J(\\theta)\\| may not converge to zero.\n\n2. The maximization over \\omega \\in R^d of equation (2) changes to \\omega \\in \\mathcal{W} in equation (4). Does that change the policy evaluation problem? There is no justification provided for this abrupt change. Is compactness of \\mathcal{W} necessary for convergence?\n\n3. Why does the paper say it is a single timescale algorithm? I see two timescales \\alpha and \\beta in the algorithm. Are they set the same in the implementation? \n\n4. I don't see how the sample complexity is O(\\kappa/\\eps) in Theorem 1. Based on the step-size policy, I believe it should be a larger power of \\kappa. E.g., \\kappa^3/\\eps. \n\n3. Since the main technical thrust of the paper is VR algorithms for the min-max problem, I was expecting some literature review of such algorithms, at least for nonconvex settings. It is important to put this result in the context of such literature and show the novelty of their work over the state-of-the-art in the optimization literature. I recommend that the authors include papers/articles working on VR algorithms for smooth nonconvex (note that J(\\theta) is a smooth nonconvex function) and nonconvex-concave minx-max problems. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "l1_94LP5ws", "reviewer": "Reviewer_Mbzc", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors developed a new efficient, single-timescale variance-reduced primal-dual method (VRPD) with an emphasis on the feasibility of solving non-convex policy evaluation problem in reinforcement learning (RL) with nonlinear function approximation, also known as the value function estimation or on-policy learning with nonlinear function approximations. VRPD is a single-timescale algorithm that meets an $\\mathcal{O}(1/K)$-rate of convergence to a first-order stationary point for general non-convex-strongly-concave (NCSC) minimax optimiztion, under mild assumptions and appropriate parameter choices. The authors claim that they provide the best-known result in the literature. An enhanced VRPD method is also proposed, namely VRPD${}^{+}$, to allow adaptive batch sizes using historical information while maintaining the theoretical convergence rate. The authors empirically validated the proposed method and concluded higher sample efficiency over comparable methods including VRPD.", "summary_of_the_review": "In summary, the authors did a satisfactory job introducing the single-timescale method that solves an important practical problem (policy evaluation in RL), achieving sharp convergence rates matching the lower bound under certain regimes ($\\kappa=O(1)$). With that said, the paper potentially admits some issues of overclaiming their results. Plus, the author seems to have solved a much broader problem but applied it to a very specific problem (of policy evaluation with nonlinear function approximation). Extending such a framework to wider application instances as the next step might be a good idea. As of the current form I give my rating of borderline inclining rejection and encourage the authors to address these main points in their revised version.", "strength_and_weaknesses": "Page 2, middle part.\nI am confused when the authors indicate \"new proof techniques in convergence rate analysis\". To quote words in your paper it \"resolves an open question and clarifies an ambiguity in the state-of-the-art convergence analysis ...\". Can you clarify what was the ambiguity and how did you clean it?\n\nPage 3, middle part (related work).\nMy understanding is that Du et al. (2017) study the TD(0) formulation of policy evaluation with linear function approximation, which can be re-cast as a strongly-convex-concave problem. What is the true novelty of this work, in comparison with Du et al. (2017)? Du et al. (2017) solved this problem via VR-based methods and achieves a linear convergence rate via the gradient descent-ascent type method. Is it correct that nonlinear function approximation leads to possible non-concavity?\n\nPage 4, first paragraph.\nSREDA adopts \"PiSARAH\" subroutine but the latter is not detailed.\n\nPage 4, second paragraph.\nIt should be desirable if the dependency on *all* problem-dependent constants should be considered when discussing matching the lower bounds. At first glance, it seems that the method is not sharp in terms of $\\kappa$, and this is natural due to that no acceleration method is adopted. In my opinion, even if the resulting upper bound failed to match the lower bound by Zhang et al. (2021) in certain regimes, some discussions in fine-grained angles should be added.\n\nPage 7, middle part (Remark after Theorem 1).\nThe author wrote \"Theorem 1 states that VRPD achieves an $\\mathcal{O}(1/K)$ convergence rate to an $\\epsilon$-FOSP\". The complexity and rate of convergence have been awkwardly mixed together and caused confusion. One should modify it accordingly. I like the more detailed stochastic sample complexity of $\\mathcal{O}(M + \\sqrt{M}\\kappa\\epsilon^{-1})$ where $\\kappa$ denotes the condition number of the strongly convex part. Also, \"The most challenging part in proving Theorem 1 stems from the fact that one needs to simultaneously evaluate the progress of the gradient descent in the primal domain and the gradient ascent in the dual domain of the minimax problem\". This is merely a standard technique and is well-known in recent minimax optimization.\n\nSome reference bibitems are duplicated, e.g. Sutton et al. Authors are encouraged to clean them when preparing their next version.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "T9eUZotFirU", "reviewer": "Reviewer_iPgL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies policy evaluation with nonlinear function approximation. It proposes and analyzed two algorithms called VRPD and VRPD+ to optimize the primal-dual form of the MSBPE. The VRPD algorithm utilizes variance reduction techniques to achieve $O(1/K)$ convergence rate.", "summary_of_the_review": "Currently, the paper shows strong theoretical results compared with previous literature. Some concerns still need to be addressed. Thus I recommend weak acceptance.", "strength_and_weaknesses": "Strength:\n1. Paper is well-written and easy to follow.\n2. Compared with previous work on the non-convex-strongly-concave minimax optimization problem, the convergence rate of this work achieves $O(1/K)$, which is the same as before and has fewer constraints.\n\nWeakness:\n1. The convergence metric is unconventional. The first term in Eqn (9) is the full gradient w.r.t. $\\theta$, which (I believe) includes both the partial derivative of the first input and the chained gradient w.r.t. $\\theta$ via the second input. This first term already suffices to guarantee a first-order stationary point, rendering the second term redundant. On the other hand, bounding the partial gradient of both inputs is also acceptable. I wonder why the analysis of this paper fails to provide a guarantee for either of these metrics.\n2. The technical novelty of the minimax optimization technique used here is not clearly stated and compared with previous works. I believe it helps to also make a list to compare with previous NCSC minimax optimization algorithms.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "GKr8a7p20c", "reviewer": "Reviewer_ZMya", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers the policy evaluation problem of reinforcement learning. Based on a primal-dual formulation of the objective, the authors apply a variance reduction technique to solve the problem under the nonlinear function approximation. They claim that the algorithm attains $O(\\frac{1}{K})$ iteration complexity.", "summary_of_the_review": "The paper’s motivation is not clearly centered. The optimization objective is not justified and the algorithm is not explained. There are many typos and technical flaws which make the paper hard to understand. Thus, I believe the work is not finished and is far from its fine shape for publication in ICLR.", "strength_and_weaknesses": "Strength:\n\n- The paper proposes a variance reduction method for solving a problem that seems to have a connection with the policy evaluation problem. They obtain the $O(\\frac{1}{K})$ iteration complexity.\n\nWeakness:\n- The considered finite-sum objective differs from the original MSPBE objective. In fact, the objective cannot even be viewed as an unbiased substitute, as the sample from a trajectory doesn’t follow the stationary distribution. Such an objective is not justified.\n- The algorithm’s update is poorly explained. From my view, it’s just SPIDER’s update [1], which is a popular variance reduction approach. However, there is no discussion with existing variance reduction methods.\n- The projection step in (8) is not explained.\n- There are too many typos and unprecise claims, making the paper hard to read. Here are examples:\n1. The last $g_\\theta(s)$ in (1) should not have a transpose.\n2.  The strongly-concavity definition in assumption 4.2 is wrong; the function should also be additionally concave.\n3.  The L_f-smoothness definition in assumption 4.3 is unprecise; theta and omega should be in the same norm.\n\n[1] Spider: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject