PILOT: An $\mathcal{O}(1/K)$-Convergent Approach for Policy Evaluation with Nonlinear Function Approximation
Authors: Zhuqing Liu
Xin Zhang
Jia Liu
Zhengyuan Zhu
Songtao Lu
Venue: ICLR 2024 spotlight (2024)
Keywords: min-max optimization
adaptive batch size
policy evaluation.
Primary area: optimization

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 non-linear function approximation. This challenge motivates us to develop a new path-integrated primal-dual stochastic gradient (PILOT) method, that is able to achieve a fast convergence speed for RL policy evaluation with nonlinear function approximation. To further alleviate the periodic full gradient evaluation requirement, we further propose an enhanced method with an adaptive-batch adjustment called PILOT$^+$. The main advantages of our methods include: i) PILOT allows the use of {\em{constant}} step sizes and achieves the $\mathcal{O}(1/K)$ convergence rate to first-order stationary points of non-convex policy evaluation problems; ii) PILOT 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, PILOT$^+$ is more sample-efficient empirically without loss of theoretical convergence rate. Our extensive numerical experiments verify our theoretical findings and showcase the high efficiency of the proposed PILOT and PILOT$^+$ algorithms compared with the state-of-the-art methods.

Published as a conference paper at ICLR 2024
PILOT: AN O(1/K)-COVVERGENT APPROACH FOR POLICY EVALUATION WITH NONLINEAR FUNCTION AP- PROXIMATION
Zhuqing Liu', Xin Zhang', Jia Liu', Zhengyuan Zhu Songtao Lu'
i Department of Electrical and Computer Engineering, The Ohio State University
$ Departmeent of Statistics, Iowa State University
*IBM Research, IBM Thomas J. Watson Research Center
1iu. 938 osuu.. edu, xinzhang ate edu, liußece. osu. edu, zhuz astate. edu, songtao lmm. com,
ABSTRACT
Learning an accurate value function for given policy is critical step in solving reinforcement learning (RI.) 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
develop new path-integrated primal-dual stochastic gradient (PILOT) method, that is able to achieve a fast convergence speed for RL policy evaluation with nonlinear function approximation. To further alleviate the enhanced periodic full gradient evaluation requirement, we further propose method with an adaptive-
adjustment called PILOOT+ The main advantages of our methods include: i) PILOT allows the use of constant step sizes and achieves the (1/ K) convergence rate to first-order stationary points of non-convex policy evaluation problems; ii) PILOT is generic singletimesccle algorithm that is also applicable for solving a large class of non-convex strongly-concan minimax optimization problems; iii) By adaptively adjusting the batch size via historical stochastic gradient information, PILOT+ is more sample-efficient empirically without loss of theoretical convergence rate. Our extensive numerical experiments verify our theoretical findings and showcase the high efficiency of the proposed PILOT and P algorithms compared with the oafe--o-thh-ann methods.
INTRODUCTION
In recent years, reinforcement learning (RL) has achieved enormous successes in large number of areas, including healthcare (Petersen ct al. 2019: Raghu et al. 2017b), financial recommendation (Theocharous al. 2015), ranking system (Wen al. (223) resources management (Mao et al. 2016) and robotics (Levine et al. 2016 Raghu et al. 2017a). to name just a few. In RL, an agent interacts with environment and repeats the tasks of observing the current state, performing policy- based action, receiving a reward, and transitioning to the next state. Upon collecting a trajectory of action-reward sample pairs, the agent updates its policy with the aim of maximizing its long-term accumulative reward. In this RL framework, a key step is the policy evaluation (PE) problem, which aims 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 's accumulative rewards, but are also able to update the current policy so that the agent can visit valuable states more frequently (Lagoudakis Parr 2003). Regarding PE, two of the most important performance metrics are convergence rafe and sample complexity. First, since PE a subroutine of an overall RL task, developing fast-converging PE algorithms is of critical importance to the overall efficiency of RL. Second, due to the challenges in collecting a large number of training samples (trajectories of state-action pairs) for PEs RL, reducing the number of samples (i.e., sample complexity) of data collection for solving PE problems. These two important aspects motivate us to pursue a fast-converging PE algorithm with low sample complexity in this work.
significantly alleviate the burden

---

Published as a conference paper at ICLR 2024
Among various algorithms for PE, one of the simplest and most effective methods is the temporal difference (TD) learning approach (Sutton 1988). In TD learning, instead of focusing on the predicted and actual outcomes, the key idea is to make the difference between temporally successive predictions small. Specifically, the TD learning approach learns the value function using the Bellman equation to bootstrap from the currently 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, (e.g., TD(A) (Sutton 1988) for off-policy training) or high computational complexity (e.g., the least-squares temporal difference (LSTD) (Boyan) 2002) in training with massive features. One reason of the unstable convergence performance of these early attempts is that they do not leverage the gradient-oracle in PE. Thus, in recent years, gradient-based PE algorithms have attracted increasing attention.
However, when working with nonlinear DNN models, the convergence performance of the con- ventional single-timescale TD algorithms may not be guaranteed (Tsitsiklis & Van Roy 1996). To address this issue, some convergent two-timescale algorithms (Maei et al. 2009: Chung al. 2018) have been proposed at the expense of higher implementation complexity. Second, modern PE tasks could involve large amount of state transition data. To perform PE, algorithms typically need to calculate full gradients that require all training data (e.g., gradient temporal difference (GTD) (Suttonn al., 2008) and TD with gradient correction (TDC) (Sutton al., [009)]] which entails high sample complexity. To the best of our knowledge, all existing works on PR either focus on linear approximation, such as GTD2 (Sutton al. (009)., PDBG (Du al., 2017), SVRG (Du et al. 2017). SAGA (Du et al. 2017) or they exhibit slower theoretical convergence performance, as observed in STSG QQu et al. 2020), VR-STSG (Qiu et al., 2020). nPD-VR (Wai et al., 2019) in the sense of achieving convergence rate that is slower than O(1/K), where K is the number of iterations. In light of the above limitations, in this paper, we ask
Please see detailed discussions in Section. 2
the following critical question:
Can we develop a fast-converging single-timescale algorithm for PE with nonlinear function approximation?
In this paper, we give an affirmative answer to the above question. Specifically, we propose an efficient path-jntegrated primal-dual stochastic gradient algorithm (PILOT) to tackle the PE problem with nonlinear function approximation, which we recast as a minimax optimization problem. The proposed PILOT algorithm admits simple and elegant single-timescee further enhance PILOT by proposing PILOT+, which uses adaptive batch sizes to avoid the periodic full gradient evaluation to further reduce sample complexity. The major contribution of this paper is that our proposed algorithms achieve the first O(1/K) convergence rate (K is the number of iterations) with constant step-sizes for PE with nonlinear function approximation, which is the best result in the literature so far. Our main results are highlighted below:
algorithmic structure. Besides,
Utilizing a variance reduction technique, our PILOT algorithm facilitates the use of constant step-sizes while maintaining a low sample complexity. We demonstrate that, under reasonable mild assumptions and suitable parameter selections, PILOT attains an O(1/K) K) convergence rate (NCX-SCV) minimax
to a first-order stationary point for class of nonconvex www.eeesssttoooooooooooee problems encountered in RL. To establish this outcome, our convergence analysis employs new proof techniques and resolves an ambiguity present in the current state-of-the-art convergence analyses of Variance Reduction bVRe-based PE methods.
Our PILOT algorithm leverages adaptive batch sizes, effectively integrating historical information throughout the optimization process without necessitating backtracking or condition verification. We demonstrate that PIIOOT+ leads to substantial reduction in both sample requirements and gradient computation loads. This reduction made possible by our innovative adaptive batch size technique, which climinates the need for full gradient evaluation.
Our comprehensive experimental results provide strong evidence of the superior performance of our algorithms compared to state-of-the-art gradient-based PE methods. Additionally, PILOT+ exhibits the capability to further reduce the sample complexity of the PILOT algorithm. It is worth noting that while our primary focus is on PE, the design of our algorithms and the proof techniques developed also hold potential significance in the broader domain of minimax optimization, presenting independent theoretical interest.
2

---

Published as a conference paper at ICLR 2024
Table 1: PE algorithms comparison: M is the size of the dataset and K is the total iteration.
Algorithm
Function Approx.
Problem
Step-size
Convergence Rate
GTD2 Sutton et al.
2009
Linear
(1))
PDBG Du ct al. 2017
Linear
Conex--Concave
((1)
O(1/K)
SVRG
Du et aL
2017
Linear
O(1)
O(1KK)
SAGA Du et al.
2017
Linear
Convex-Concave
O(1)
O(1/K)
TATD
Patil et al.
22023
Linear
((1/K)
STSG Qiu et al.
2020
Nonlinear
Stochastic/ NCX-SCV
((1) ((1/K1/²)
VR-STSG Qiu ct al.
(2020)
Nonlincar
Stochastic/ NCX-SCV
O(1)
((1/K2/a)
nPD- Wai et al.
(2019)
Nonlinear
Finte-Sum NCX-SCV ((1AM)
Slower than ((/KK)
PILOTTOurs.
Nonlincar
Finte-Sum / NCX-SCV O(1)
((1/K)
PILOT [Ours.]
Nonlinear
Finte-Sum/ NCX-SCV O(1)
O(1/K)
The convergence rate of nPD-VR is ambiguous. See the detailed discussions in Sections 2 below and 4
2 RELATED WORK
TD learning with function approxima- tion plays vital role in PE. The key idea of TD learning to minimize the Bellman error for approximating the value function. However, most existing TD learning a algorithms with theoretical
1) TD Learning with Function Approximation for PE:
guarantees focus on the linear approximation setting (e.g.. (Sutton et al. 2008 [Srikant& & Ying 2019)
Xu et al. 2019: Touati et al., [018]] Patill et al. [023]] Li et al. (021)) Existing works in (Doan
cet al. 2019 Liu et al.) 2015; Macua et al. 2014 Zhang & Xiao 2019; Patil et al. 2023 Li et al.
2021 provided finite-time analysis for the distributed TD()) and showed that the convergence rates of their algorithms are () It was shown in (Du et al. 2017) that PE with linear function approximation by TD()) can be formulated as strongly convex-concave
convex-concave problem, and can be solved by a primal-dual method with a linear convergence rate. Unfortunately, the linearity assumption cannot be applied to a wide range of PE problems with nonlinear models. TD learning with nonlinear (smooth) function approximation is far more complex. The work in (Maei et al.. 2009) was among the first to propose a general framework for minimizing the generalized mean-squared projected Bellman error (MSPBE) with smooth and nonlinear value functions. Despite their use of two-timescale step-sizes, it's important to note that this approach yielded slow convergence per- formance. Other TD methods with nonlinear function approximations for PE include ( (Wang et al., 2017 2016). Nonlinear TD learning was also investigated in Qiu et al. (2020), which proposed two single-timescale first-order stochastic algorithms. However, the convergence rates of their STSG and VR-STSG methods are (11/3//4) and (11/2//5), while our PILOT algorithm achieves a much faster (I1/K) convergence rate, matching the standard one in the linear case.
In PE with non-linear function approximation, the lfte-oof-hhe-an and the most related work is (Wai al. 2019), which showed that minimizing the generalized MSPBE problem is equivalent to solving a ron--conee--tronlyy--ooo the Fenchel's duality. However, their best convergence results only hold for a small step-size that is (L/M), where M denotes the size of the dataset. This will be problematic for RL problems with a large state-action transition dataset. Furthermore, it is worth highlighting that their convergence rate bound takes the form of +Constant K K-Constan12
(NCX-SCV) minimax optimization problem by applying
(cf. Theorem 1, Eq. (26) in Wai et al. (211))). Here, the term (K) in the denominator inherently relies on the primal and dual values ((R) and (K) at the K-th iteration. However, the bounding of (K) in (Wai et al. 2019) remains unclear, leading to ambiguity when attempting guarantee an O(1/K) convergence rate. Therefore, whether an (L/K) convergence rate is achievable in sinle-timescale PE 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/K) convergence rate. To establish this result, we propose new convergence metric (cf. Eq. (6) in Section 4) which necessitates new proof techniques and analysis. For easy comparisons, we summarize our algorithms in comparison with the related existing works in Table
2) Relations with NCX-SCV minimax Optimization: Although the focus of our paper is on PE, our algorithmic techniques are also related to the general area of NCX-SCV minimax optimization due to the primal-dual MSPBE formulation (cf. Eq. (T) in Section
Early attempts in (Nouiched
We note that solving the MSPeE- PE problem is one of the most fitting motivating applications for NCX-SCV minimax optimization problems. As discussed Section 3 the MSPRE-based PE problem
3

---

Published as a conference paper at ICLR 2024
et al. 2019 Lin et al. 2020b Lu al. 2019) developed gradient descent-ascent algorithms to solve the NCX-SCV minimax problems. However, these methods suffer from a high sample complexity and slow convergence rate. To overcome this limitation, two variance-reduction algorithms named SREDA (Luo et al. 2020) are proposed for solving NCX-SCV minimax problems, which share some similarities to work. SREDA was later enhanced in Xu et al. (2020) to allow larger step-sizes. However, our algorithms differ from SREDA in the following key aspects: (i) Our algorithms are single-timescale algorithms (see Section 4 for the notions of single-timescale and two-timescale algorithms), which are much easier to implement. In comparison, SREDA is a wo-tiimescale algorithm that also requires solving an inner concave maximization subproblem. To a certain extent, SREDA can be viewed as a triple-loop structure, and hence the implementation complexity of SREDA higher than ours; (ii) In the initialization stage, SREDA uses subroutine called PiSARAH to 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 algorithm. (iii) The number of hyperparameters in SREDA is 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, sufficiently small (smaller than the upper bounds we provide in our theorems), which is easier to tune in practice. (iv) SREDA does not provide an explicit convergence rate in their paper (it is also unclear what their convergence rate is from their proof). Yet, we show that our PILOT algorithm has a lower sample complexity than that of SREDA.
algorithms only require step-sizes and / to be
Another related work in NCX-SCV minimax optimization is (Zhang et al. 2021), which provided sample complexity upper and lower bounds. However, there remains gap between the sample complexity lower and upper bounds in (Zhang et al. (021). By contrast, the sample complexity of
our PILOT algorithm is the first to match the lower bound O(M + VM in (Zhang et al. 2021 Furthermore, the algorithm in (Zhang et al. (02T) contains an inner minimax subproblem (cf. Line of Al Algorithm in Zhang et al. (2021)). Solving such subproblem in the inner loop incurs high computational costs. Due to this reason, the algorithm in (Zhang et al., 202I) had to settle for an inexact solution, which hurts the convergence performance in practice. In contrast, our algorithm does not have such a limitation.
3 PRELIMINARIES AND PROBLEM STATEMENT
We start by introducing the necessary background of RI., with focus the PE problem based on nonlinear function approximation.
1) Policy Evaluation with Nonlinear Function Approximation: RL problems are formulated using the Markov decision process (MDP) framework defined by five-tuple (S, P. 7, RJ. where S denotes the state space and A is the action space; P : S x A + S represents state transition probabilities after taking actions; R denotes the space of the received rewards, where each reward corresponds the agent taking specific action a E .A from the set of possible actions when the system is in particular state in the state space E S (in this paper, we assume that the state and action spaces are finite but their dimensionality could be large); and 7 E [0, 1) is a time- discount factor. For RI. problems over an infinite discrete-time horizon {t E N). the learning agent executes an action a, according to the state 8t and some policy π S x A + [0, 1]. The system then transitions into new state 81+1 I in the next time slot, and the agent receives a reward R(st, a.) through its interaction with the environment. The trajectory generated by a policy и is sequence of state-action pairs denoted as {$1, 01, $2, ....... Specifically, for a policy (could be a randomized policy), the expected reward received by the agent at state s in any given time slot can be computed as RdT (st) = Buwnttlaa) [ (8t, (st,a).. a)]- The value function V (so)
1 y¹ RR (st) so, π indicates the long-term discounted reward of policy क over an infinite horizon with the initial state at E S. Also, the Bellman equation implies that V--) satisfies : ((s)=T*((s)) where TT A E[R" + + ~ s( ~ P(-ls, a)] denotes the Bellman operator. In RI., the agent's goal to determine an optimal policy T" that maximizes the value function V* (s) from any initial state
can be reformulated as an NCX-SCV minimax problem, which can be solved by our proposed VR-based single-timescale method efficiently.
Here, the rate of O(E -2) measured the size of the primal objective function is equivalent to O(1K)).
4

---

Published as a conference paper at ICLR 2024
However, the first obstacle in solving RL problems stems from evaluating (T(.) for given x since P(-|s, a) is unknown. Moreover, it is often infeasible to store (*(s) since the state space S could be extremely 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 V-(() ~ Vo- (.), where lT E E C Rd is d-dimensional parameter vector. Here, θ is a compact subspace. For notational simplicity, we will omit all superscripts "x" whenever the policy π is clear from the context. In this paper, we focus on nonlinear function approximation, i.e., (- : S R a nonlinear function with respect to (w.r.t)) 0. For example, V-(-) could be based on a 0 ---aamtteerzedd nonlinear DNN. We assume that the gradient and Hessian of (-(+) exist and are denoted as: go(s) := (o) E R", Ho(s) := V2 (o) E BRddd Our goal is to find the optimal parameter 0" E R that minimizes the error between Vo- (-) and V(.). has been shown in (Liu et al. 2018) that this problem can be formulated as minimizing the mean-squared projected Bellman error (MSPBE) of the value function
(Liu et al. 2018 Proposition 1) as follows:
1
MSPBE(0) = 2 ( Va()
1 (-
max WERd
- 90(s)) (w [ (
(I)
where (-) the stationary distribution under policy ι and D ف D- (5)gg (s)] e Raxd and w is referred to as the dual variable.
2) Primal-Dual Optimization for MSPBE: Minimizing MSPBE in I is equivalent to solv- ing primal-dual minimax optimization problem: mingeg max L(B, w)) where L(0, w) & (w, (E ((T'Vo (e (9))))))))))))))))) }> - -- (w (s)))) Since the distribution DT is unknown and the expectation cannot be evaluated directly, most existing work in the literature (see, e.g. [iu e.g.,Liu et al. (2055): Wai et al. (2019) Du et al. (2017)) considered the following empirical minimax problem by replacing the expectation in L(O, w) by a finite-sum sum sample average approximation based on an M-step trajectory (51,01... ... 8. aas, 8 generated by some policy n, i.e.,
1 M M
min max
Σ
C,(,w)) min max C(O, w),
OER WER'
BER' WER!
where C. w) == (w, [R(s;, ai $1+1) + Vo((st1) Vo(ss)] (o ( go())) In Appendix
F we will also discuss the minimax problem with @ E O.w E W, where θ, W are convex constrained sets. Solving Problem (2) for MSPBE constitutes the rest of this paper.
Note that Problem 2 is non-convex in general (e.g.. DNN-based nonlinear approximation). Let J(Ø) & max L(),w). Then, we can equivalently rewrite Problem ( as follows: minger max C(O.w) w)
mingeg J(0). Note from (2) that ((),w) is strongly con- cave w.r.t. w. which guarantees the existence and uniqueness of the solution to the problem max L(0,w), v0 E Rdd Then, given 0 E Rd, we define the following notation: w=( := TrgmaxweRR<L(O.. w). Subsequently, (0) can be further written as J(0) L(O. w (0)). We aim to minimize J(0) by finding the stationary point of C(O, w). For the sake of simplicity in notation, we use w" to denote w²(0). Note that if D in Eq. ( is positive definite, Problem (2 is strongly concave in w, but non-convex in in general due to the non-convexity of function Vo. Thus, the
Problem is an NCX-SCV optimization problem.
3) Sample Complexity: In this paper, we adopt the following sample complexity metric to measure the dat efficiency of an optimization algorithm, which is widely used in the literature (e.g.. (uo et al. (2020): Zhang et al. 2022 Xu et al. (2020))
Definition 1 (Sample Complexity). The sample complexity is defined as the total number of re- quired samplings from the dataset to evaluate incremental first-order oracle (IFO) until an algorithm converges, where one IFO call evaluates a pair of (C, w), V L., w)), i E [M].
AAthhough the finite-sum empirical loss is an approximation the expected loss function for PE, as shown Chen et al. (2021), under the conditions of bounded instantaneous loss and bounded derivatives (satisfied for
most applications in practice), the approximation error of using empirical loss is small with high probability (cf.
(Chen et al. 2021 Lemma 2)). Thus, the empirical loss has been widely used as proxy for the expected loss in
the literature Liu al. 2 Wai al. (2019) Du al. 2017)
5

---

Published as a conference paper at ICLR 2024
Algorithm 1 The path-integrated primal-dual stgchastic gradient (PILOT).
Input: An M -tstep trajectory of the statc-action pairs {$1, a1, $2, a2. MM. aMs SM+1) generated from given policy; step sizes a, 5 0; initialization points 0 E R2 w E R²
Output: (0(K), (K))), where K is independently and uniformly picked from {1,... K}; K 1 do
1: for k = 0, 1,2,
2: If mod(k, k, q) = O, compute full gradients Gb GL as in Eq. (3 Otherwise, select [V]
3: samples independently and uniformly from [M], and compute gradients as in Eq.
4: Perform the primal-dual updates obtain the next iterate ((*+1), (k+1) as in Eq.
5: end for
4
THE VARIANCE- PRIMAL-DUAL METHOD (PILOT)
In this section, first present the uuriance-reduced primal-dual (PILOT) algorithm for PE, followed by the theoretical convergence results. Due to space limitation, we provide a proof sketch in the main text and relegate the detailed proofs the supplementary material.
Algorithm Description: The full description of PILOT illustrated in Algorithm ! In PILOT, for every iterations, the algorithm calculates the full gradients as follows:
1 M
(oLi(O (F)),
C
(.C.(()) ),)),, if mod(k, 0.
M
REM
EEM
all other iterations, PILOT selects batch N and computes variance-reduced gradient estimators:
G
1
(oC.(0
())) VoL.(0' (w (it-")), if mod q) * 0,
(4a)
N
IEN
1
Ca (#))) vuLi(a(t-1) ( (1-1))) -(-"")) if (k, 2) + 0.
(4b)
W
EEN
The estimators in (oC,(0(k-1), (k--1)) (resp. (O(k))))))) w(k-1)) and Go Gffk-)) (resp. G(--1), PILOT up- dates the primal and dual variables as follows:
constructed iteratively based on the previous update information
(k++1) x*)) , w (k+1) (K) al
(5)
where parameters a and | are the constant learning rates for the primal and dual updates.
Remark 1. Single-Timescale Algorithm: Our PILOT algorithm a tinleel algorithm, which is much simpler to implement in practice compared to the two-timescale algorithms shown in Maei al. (2009); Lin et al. (2020b). To see this, we first restate the notions of single- and two-timescale algorithms in the literature (see, e.g., (Dalal et al.) 2018)). Let a₁ 2 0 and 8r 2 0 represent the step-sizes at iteration for outer- and inner-variable updates, respectively. An algorithm called a two-tinescale algorithm if 8 + 0 a + +00 as t + co. On the other hand, an algorithm is called a single-timg angle-timescale algorithm if < C < / C" as + oo, where 0 < C,C" < too are two positive constants. In our proposed PILOT algorithm, since the step-sizes a and 3r constants, our PILOT algorithm is clearly tinleetimescale algorithm.
2) Assumptions: Before showing the theoretical results, we first make the following assumptions: A Assumption (μ-Sttrong Concavity). We assume that L(O, w) is differentiable and p-strongly concave in w, where for any 0 E Rd, L(O, w) < ((0,w") + V.C(O, (w - w²) - wlwlw w'11? ww,u w' E Rd, p 0.
It can be shown that the condition in Assumption is equivalent to
u||l - w'll Yw, w' E nd (see proof' in (Zhou 2018 Lemmas 2 and 3)).
Assumption - Smooothnesss We assume that for i = 1,2,.... M, both gradient (0,,(0,w) and (O, w) are -mmooth. That is, for all 0, 0' e Rd and w, w' E Rdd, there exists a constant L, > such that || VL, w) - VL, w')ll S Ly (110 - -0'l |W - -'ll).
Assumption 3 (Boundness from Below). There exists finite lower bound J = info J(0) > -00.
Assumption 4 (Bounded Variance). There exists a constant o > 0 such that for all 0 E Rd w E Rd
M M VoL. VoL(O, w2 < 2² and 1 EM [,, VI)( < o².

---

Published as a conference paper at ICLR 2024
We note that Assumption I satisfied if the number of samples M is sufficiently large and the matrix D is positive definite" Assumption B standard in the optimization literature. Assumption 4 is also commonly adopted for proving convergence results of SGD- and VR-based algorithms, or
algorithms that draw a mini-batch of samples instead of all samples. Assumption 4 is guaranteed to hold under the compact condition and common for stochastic approximation algorithms for
minimax optimization (Qiu et al. 2020) Lin et al. (022a)). Assumptions TH4 are also often used
in temporal difference (TD) problems (see, e.g., (Qiu et al. 2020 Wai et al. 2019)). With these
assumptions, we are now in position to present our convergence performance results of PILOT.
3) Convergence Performance: this paper, we propose a new metric for convergence analysis:
20(0, w) == (() ||a + 2 - w (0)]1
The first term in (6) measures the convergence of the primal variable 0. As common in non-convex optimization analysis, [0)]( 0 indicates that 0 is a first-order stationary point (FOSP) of Problem 2 The second term in 6 measures the convergence of (k)) to the unique maximizer w (0(x) for [(),.)). Based on this new convergence metric, we can now introduce the notion of the approximate first-order stationary points.
Definition 2. The point {0, } is an e-stationary point of function C(O,w) w) if 20, w) S.
Several important remarks on the connections between our metric (x(()) and the conventional conver- gence metries in the literature are in order. A conventional convergence metric in the literature for
NCX-SCV minimax optimization is ((((() 1 (Lin et al. 2020a Luo et al. 2020 Zhang et al.
2021
Wu al. 2023 Huang et al. 2021 Wu et al. 2023), which is the first term of 207(k) This is because [[)
0 implies that is a FOSP. Another conventional convergence metric in the + I C( w (Tiit minimax optimization problem is
literature of minimizing the empirical MSPBE problem is |V,,( w)
siklis & Van Roy 1996). Since the nonconvex--ttron-ccomee unconstrained in dual (i.e., w R2), it follows from Lipschitz-smoothness in Assumption 2 and ((V))))(()) w (0(K))
that (|0( (0(()) 2 I. (()(())) m (1) Therefore, the second term in our ()) (i.e., 2/ - w (0(()) is an upper bound of the second term in this conventional metric (i.e., C(,, )))l) Thus, 21(w(() - ~ (0(*)) ] is a stronger metric than [ w) )l² in the sense that an O(1KK) convergence rate under (4) implies an ()1/K) convergence rate of the conventional metric, but the converse is not true. Moreover, the benefit of using (|) (8) w (0(*)) )12 in our (7()) is that its special structure allows us prove the O(1 K) convergence, while the second term in the conventional metric does not enjoy such a salient feature.
With our proposed convergence metric in 6 have the following convergence result:
Theorem 1. Under Assumptions
choose step-sizes: S minn 4b, 3417+ and
< min
1 { 1b, 2(L,+13/M)
2a q= [ = [VM], holds that:
8/17
8/3413
11 -
161.
C2+ + 3
2 C₁ = -o ((k)
K
K min(1 L7}
ap
where C A [[J - [[)(())) C2 - [ ((ll)((0))) - (0)) and 0r = ming ((O).
Theorem |
Iimmediately implics the following result:
Corollary 1. The overall sample complexity of PILOT is O(VMR3 + M), where = L//M
denotes the condition number.
Theorem I states that PILOT achieves an ((/K) convergence rate an c-FOSP. The most chal- lenging part in proving Theorem [ stems from the fact that one needs to simultaneously evaluate the progresses of the gradient descent in the primal domain and the gradient ascent the dual domain of the minimax problem.
"To see this, recall that D = E, (VoVo(s)V E gdddd Note that μ= Amin (D) > 0 since D is positive definite and D tends to be full-rank as M increases. Thus, as soon find 0 when M is sufficiently large, this y is independent of M M continues increase.
7

---

Published as a conference paper at ICLR 2024
Remark 2. It is worth noting that the nPD-VR method in (Wai et al., 2019) employs (1)) in their metric to evaluate convergence. However, this approach yields term F(K) A EE[(( (D)) [(O(K) w(k))] in their convergence upper bound in the form of ((F(K) /K) (cf. Theorem I, Eq. (26) in (Wai et al. 2019)). Since F(K) depends on K, it is unclear whether the nPD-VR method in (Wai et al.
w (V)
2019) can achieve an (1/KK) convergence rate or not. This ambiguous result motivates us to propose this new metric ())(k) in Eq. (6) to evaluate the convergence of our PILOT algorithm. Consequently, we bound per-iteration change in J()) instead of the function (() w())), This helps avoid the technical limitations of (Wai et al. 2019) and
successfully establish the ((1/K) convergence rate. In addition to the (1/K) convergence rate, our PILOT algorithm also enjoys the following salient features:
a) Large and Constant Step-Sizes: is worth noting that PILOT adopts a large ((1) (i.e., constant) step-size compared to the (1)MM) step-size of nPD-VR (Wai et al., 2019), where M represents the dataset size. This also induces a faster empirical convergence speed. Besides, PILOT's estimator uses fresher information from the previous iteration (see Feature c) below), while VR-STSG (Qiul et al. 2020) and nPD-VR (Wai et al.] 2019) only use the information from the beginning of q-sized windows. Collectively, PILOT makes considerably larger progress than state-of-the-arr algorithms (Quu et al. 2020 Wai et al. 2019).
b) Recursive Path-Following VR Approach for minimax Problems: In the literature, most existing single-timescale methods adopt vanilla stochastic gradients as gradient estimators Gø. and Gw,,, which suffer from slow convergence rates. To the best of our knowledge, the only VR-based single-timescale method is (Qiu et al. 2020). However, (Qiu et al. 2020) is based on the SVRG-type VR technique. which achieves a slower (31/33/3) convergence rate. In comparison, our work is based on an advanced recursive path-following VR-based update, which enables the use of constant step-sizes to achieve the first O(1/K) K)) convergence rate in the literature.
5 THE ADAPTIVE-BATCH PILOT METHOD (PILOT*)
Note that PILOT still requires full gradients every q iterations. This motivates us to propose an adaptive-bated batch method called PILOT to further lower the sample complexity.
1) Algorithm Description: The full description of PILOTT is illustrated in Algorithm 2 In PILOT+, our key idea is to the gradients calculated in the previous loop to adjust the batch size M, of the next loop. Specifically, PILOT+ chooses N₂ at the k-th iteration as:
[W = min(c,, (7(h)) _.. .M).
(7)
where Cr, Ce c for certain constant c, M denotes the size of the dataset, and 7 (k+1)
E (1g |G/ 1/0/ is the stochastic gradients calculated in the previous iterations. In PILOT+, for every q iterations, select N₂ samples independently and uniformly from [M] and compute gradient estimators as follows:
(OL.( ()) SEN
G
Σ (O VEN,
(8)
I.
For other iterations, PILOT is exactly the same as PILOT. Next, we will theoretically show that such an adaptive batch-size scheme still retains the same convergence rate, while achieving an improved
complexity Performance: For PILOT we have the following theoretical convergence result:
Theorem 2. Under Assumptions
choose step-sizes: S min aL,' 3417 +2p and B < min n 2(14+13/05 8V1717 3V3117 }. Let [N1 min(c,," (1))) -.000--- 1,M q [VM, 1. [W = [VM] and C2 2 (288L + 8) in PILOT where o, 2 c for Pp With constants C₁ A [[J()[))) - E[J(0*) and C2 -
2p
some constant e > 4K + 68K (BllI>* (010)) (0))))))) holds that:
c 16L
Ca + 201 =0
1 c K
K
+
K A=
K min 123
2 ag
Theorem immediately implies the following result:
8

---

Published as a conference paper at ICLR 2024
Algorithm 2 Adaptive-batchh PILOT method (PILOT*).
Input: A trajectory of the state-action pairs (81, 0i, 82, 02 ... 8M, a., SM+1} generated from given policy; step sizes a, B 2 0; initialization points 0 θ, w R
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) = O, select |N;] indices independently and uniformly from [M] as in Eq.
and calculate stochastic gradients as in Eq. (8)
3: If mod ; q) o 0, select [W[ samples independently and uniformly from [M]] Compute
gradients in Eq.
4: Perform the primal-dual updates as in Eq.
5: end for
Corollary 2. The overall sample complexity of PILOT is O(VMR +M, where k Ls/H denotes the condition number.
EXPERIMENTAL RESULTS
In this section, we conduct our numerical experiments to verify our theoretical results. We compare our work with the basic stochastic gradient (SG) method (Lin al. (020b) and three state-of-the-an algorithms for PE: nPD-VR (Wai et al., (211),, STSG (Qiu et al. (2220) and VR-STSG (Qiu et al. 2020 Due to space limitation, we provide our detailed experiment settings the Appendix.
80
ST56
45.
SPE/AR
VISSTSG
/PO-V
VA 81B0
Wi-stee
WrssreG PLO
Eprocees
Figure I: MountainCar-V environment.
Figure 2: Cartpole-vO environment.
Teumi tee unwllf
IF WPR HF un-aff
P1.OF
Rich
grad
200
200
Figure 3: MountainCar-V environment.
Figure
Cartpole-vo environment.
First, we compare the loss value and gradient norm performance based on MountainCar-vO and Cartpole-v0 with nPD-VR, SG, STSG, and VR-STSG in Figs. [ndd] 2 We initialize all algorithms at the same point, which is generated randomly from the normal distribution. We can that VR-STSG and nPD-VR slowly converge after 40 epochs, while STSG and SG fail to converge. PILOT converges faster than all the other algorithms with the same step-size values. As for Cartpole-vO, we clearly see trend of approaching zero-loss with PILOT. These results are consistent with our theoretical result that one can use relatively large step-size with PILOT, which leads to faster convergence performance. Also, we compare the sample complexity of PILOT and PILOT+ in MountainCar-v) and Cartpole-vO, and the results are shown in in Figs. and respectively. We can see that P converges to the same level with much fewer samples than PILOT docs.
Numerical Results:
CONCLUSION
In this paper, we proposed two algorithms called PILOT and PILOT for PE with nonlinear approx- imation and performed the theoretical analysis of their convergence and sample complexity. The PILOT algorithm is based on single-timescale framework by utilizing VR techniques. The PILOT algorithm allows the use of constant step-sizes and achieves an O(1KK) convergence rate. The P algorithm improves the sample complexity of PILOT by further applying adaptive batch size based on historical stochastic gradient information. Our experimental results also confirmed our theoretical findings in convergence and sample complexity.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
This work has been supported in part by NSF grants CAREER CNS-2110259 and CNS-211247L.
REFERENCES
Justin A Boyan. Technical update: Least-squares temporal difference learning. Machine Learning. 49:233-246, 2002.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint
2016.
Tianyi Chen, Kaiqing Zhang, Georgios B Giannakis, and Tamer Basar. Communication-efficinn policy gradient methods for distributed reinforcement learning. IEEE Transactions on Control of Network Systems, 9(2):917-929) 2021.
Wesley Chung, Somjit Nath, Ajin Joseph, and Martha White. Two-timescale networks for nonlinear value function approximation. In International Conference on Learning Representations, 2018.
Gal Dalal, Gugan Thoppe, Balázs Szörényi, and Shie Mannor. Finite sample analysis of two-timescale stochastic approximation with applications reinforcement learning. In Conference Learning Theory, pp. 1199-1220 1233. PMLR, 2018.
Christoph Dann, Gerhard Neumann, Jan Peters, et al. Policy evaluation with temporal differences: A survey and comparison. Journal of Machine Learning Research, 15:809-8888 883, 2014.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp- 1466-1478, 2021.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in Neural Information Processing Systems, 27, 2014.
Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-tima analysis of distributed td (0) with linear function approximation on multi-agen reinforcement learning. In International Conference on Machine Learning, pp. 1626-1635. PMLR, 2019.
Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference Machine Learning, pp. 1049-1058. PMLR, 2017.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. Advances in Neural Information Processing Systems, 31, 2018
Feihu Huang, Xidong Wu, and Heng Huang. Efficient mirror descent ascent methods for nonsmooth minimax problems. NeurIPS 21:Advescss in Neural Information Processing Systems, 34: 10:304 10443, 2021.
Kaiyi Ji, Zhe Wang, Bowen Weng, Yi Zhou, Wei Zhang, and Yingbin Liang. History-gradien aided batch size adaptation for variance reduced algorithms. In International Conference on Machine Learning, pp. 4762-4772. PMLR, 2020.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems, 26, 2013.
Michail G Lagoudakis and Ronald Parr. Least-squares policy iteration. Journal of Machine Learning Research, 4(Dec): 107-1 1499 2003.
Lihua Lei and Michael Jordan. On the adaptivity stochastic gradient- gradient-based optimization. SIAM Journal Optimization, 30(2):173-1500, 2020.
10

---

Published as a conference paper at ICLR 2024
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum sum optimization via scsg methods. Advances in Neural Information Processing Systems, 30, 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):1334-137) 2016.
Tianjiao Li, Guanghui Lan, and Ashwin Pananjady. Accelerated and instance-optimal policy evalua- tion with linear function approximation. arXiv preprint 1rXiv:21/2.13//000 2021.
Xiangru Lian, Mengdi Wang, and Ji Liu. Finite-sum composition optimization via variance reduced gradient descent. In Artificial Intelligence and Statistics, pp. 1159-1167. PMIR, 2017.
Tiayy Lin, Chengyou Fan, Mengdi Wang, and Michael I Jordan. Improved sample complexity for stochastic compositional variance reduced gradient. In American Control Conference (ACC), pp. 126-131. IRRE, 2020a.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concat minimax problems, In International Conference on Machine Learning, pp. 6083-6093, PMLR, 2020b.
Bo Liu, Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Finite-sample analysis of proximal gradient td algorithms. In Uncertainty in Artificial Intelligence, pp. 504-513, 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 4944, 2018.
Songtao Lu, Joannis Tsaknakis, and Mingyi Hong. Block alternating optimization for non-convex min-max problems: algorithms and applications in signal processing and communications. In IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 4754-4758, 2019.
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 Signal Processing, 68:3676-3691, 2020.
Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent minimax problems. Advances in Neural Information
for stochastic nonconvex- seteveex-stoongyycooeee Processing Systems, 33, 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 Maei, Csaba Szepesvari, Shalabh Bhatnagar, Doina Precup, David Silver, and Richard Sutton. Convergent temporal- -iffeereed learning with arbitrary smooth function approximation. Advances in Neural Information Processing Systems, 22, 2009.
Oren Mangoubi and Nisheeth Vishnoi. Greedy adversarial equilibrium: an efficient alternative to sanconvex-noncconee min-max optimization. In the 53rd Annual ACM SIGACT Symposium Theory of Computing, pp. 896-909, 2021.
Hongzi Mao, Mohammad Alizadeh, Ishai Menache, and Srikanth Kandula. Resource management with deep reinforcement learning. 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 Nouiehed, 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.
Gandharv Patil, LA Prashanth, Dheeraj Nagaraj, and Doina Precup. Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation. In International Conference Artificial Intelligence and Statisties, pp.
PMLR, 2023.
11

---

Published as a conference paper at ICLR 2024
Brenden K Petersen, Jiachen Yang, Will S Grathwohl, Chase Cockrell, Claudio Santiago, Gary An, and Daniel M Faissol. Deep reinforeement learning and simulation as a path toward precision medicine. Journal of Computational Biology, 26(6):597- 604, 2019.
Shuang Qiu, Zhuoran Yang, Xiaohan Wei, Jieping Ye, and Zhaoran Wang. Single-timescale stochastic nonconvex-concave optimization for smooth nonlinear td learning. arXiv preprint arXiv:2008. 10103, 2020.
Aniruddh Raghu, Matthieu Komorowski, Imran Ahmed, Leo Celi, Peter Szolovits, and Marzyeh Ghassemi. Deep reinforcement learning for sepsis treatment. arXiv preprint arXiv: 1.09002, 2017a.
Aniruddh Raghu, Matthieu Komorowski, Leo Anthony Celi, Peter Szolovits, and Marzyeh Ghas- semi. Continuous state-space models for optimal sepsis treatment: deep reinforcement learning approach. In Machine Learning for Healthcare Conference, 147-163, PMLR, 2017b.
Herhert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pp. 400-407, 1951.
Dan Simon. game theory approach constrained minimax state estimation, IEEE Transactions on Signal Processing, 54(2):405-412, 2006.
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, 13:14303-1431 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.
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. A convergent o(n) algorithm for off-policy lemporal-difference learning with linear function approximation. Advances Neural Information Processing Systems, 21, 2008
Richard S Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for ing with linear function approximation. the 26th Annual International Conference on Machine Learning, pp. 993-1000, 2009.
learn-
Georgios Theocharous, Philip Thomas, and Mohammad Ghavamzadeh. Personalized ad recom- mendation systems for life-time value optimization with guarantees. In the 24th International Joint Conference on Artificial Intelligence, 2015.
Ahmed Touati, Pierre-Luc Bacon, Doina Precup, and Pascal Vincent. Convergent tree backup and retrace with function approximation. International Conference on Machine Learning, pp. 4955-4964 PMLR, 2018
John Tsitsiklis and Benjamin Van Roy. Analysis temporal-difffereee learning with function approximation. Advances in Neural Information Processing Systems, 9, 1996.
Hoi-To Wai, Mingyi Hong, Zhuoran Yang, Zhaoran Wang, and Kexin Tang. Variance reduced policy evaluation with smooth function approximation. Advances in Neural Information Processing Systems, 32, 2019.
Mengdi Wang. Ji Liu, and Ethan Fang. Accelerating stochastic composition optimization. Advances in Neural Information Processing Systems, 29, 2016.
Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-valie functions. Mathematical Programming, 161(1-2): 419-449, 2017.
12

---

Published as a conference paper at ICLR 2024
Zhe Wang. Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. Advances in Neural Information Processing Systems, 32, 2019.
Wei Wen, Kuang-Hung Liu, Igor Fedorov, Xin Zhang, Hang Yin, Weiwei Chu, Kaveh Hassani, Mengying Sun, Jiang Liu, Xu Wang, al. Rankitect: Ranking architecture search battling world-class engineers at meta scale. arXiv preprini arXiv:231 1.08430, 2023.
Xidong Wu, Zhengmian Hu, and Heng Huang. Decentralized riemannian algorithm for nonconvex minimax problems. AAAI 23: Proceedings of the AAAI Conference on Artificial Intelligence, 2023.
Xidong Wu* Jianhui Sun*, Zhengmian Hu, Aidong Zhang, and Heng Huang. Solving class of non-convex minimax optimization in federated learning. NewrIPS 23: Advances in Neural Information Processing Systems, 2023.
Tengyu Xu, Zhe Wang, Yi Zhou, and Yingbin Liang. Reanalysis of variance reduced temporal difference learning. In International Conference on Learning Representations, 2019.
Tengyu Xu, Zhe Wang, Yingbin Liang, and H. Vincent Poor. Enhanced first and zeroth order variance reduced algorithms for min-max optimization. ArXiv, htbps/200.0936... 2020. URL
Junyu Zhang and Lin Xiao. A stochastic composite gradient method with incremental variance reduction. Advances in Neural Information Processing Systems, 32, 2019.
Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of nonconvex-strowe wwweeee-stoogyyyooeeeeo crongly-conccve minimax optimization. In Uncertainty Artificial Intelligence, pp- 482-492. PMLR, 2021.
Xingyu Zhou. On the fenchel duality between strong convexity and lipschitz continuous gradient. arXiv preprint arXiv: 1803.06533, 2018.
13


Reviews:
[{"review_id": "mcBOKpPeV0", "reviewer": "Reviewer_V3H9", "summary": "This work investigates policy evaluation with nonlinear function approximation. The work proposes path-integrated primal-dual stochastic gradient (PILOT), and PILOT+. It shows that PILOT converges to stationary point with a convergence rate of $O(1/K). The theoretical results are based on the assumption of strong concavity and bounded variance. With adaptive batch size, PILOT+ achieves some empirical results that demonstrates some sample efficiency. The algorithms demonstrate some efficiency on simple simulation tasks like Mountain Car and Cartpole.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The work proposes a pair of algorithms, PILOT and PILOT+, which are good in theory and in practice, respectively. It is nice to have variants of the algorithm to excel in both perspectives. The results on stationary point convergence and a convergence rate of $O(1/K)$ seem relevant.", "weaknesses": "The work is based on very strong assumptions, which do not hold in RL tasks in general. It is of course valid to argue that some previous works are also based on such assumptions, but with the assumptions the work offers less relevance and less technical contribution to the community.", "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": "", "extra_scores": {}}, {"review_id": "bDOJkvkmwE", "reviewer": "Reviewer_XRvu", "summary": "The authors develop a single-timescale version of the non-linear policy evaluation algorithm (PILOT). The algorithm allows for instance-independent stepsize choice and relies on the primal-dual optimization with additional variance reduction for gradient computations. The authors also provide a modification of their approach with adaptive batch size selection in order to avoid the preiodic full gradient computations.", "questions": "a)If time permits, I would suggest the authors to complement the experimental section. \n\nb) The authors could also complement the bibliography on linear policy evaluation methods (TD(0) with modifications) by the following papers:\n1. Li, Tianjiao, Guanghui Lan, and Ashwin Pananjady. \"Accelerated and instance-optimal policy evaluation with linear function approximation.\" arXiv preprint arXiv:2112.13109 (2021) - https://arxiv.org/abs/2112.13109\n2. Patil, Gandharv, et al. \"Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023. - https://arxiv.org/abs/2210.05918\nThe first one concerns instance-optimal guarantees for Polyak-Ruppert averaged iterates of TD(0). The authors also use SPIDER-type variance reduction. The second paper concerns TD(0) with realizable step size.\n\nc) I am also a bit surprised by the fact that the mixing time of the original chain $(s_1,a_1,s_2,\\ldots)$ does not pop up explicitly in the bounds. This would be a typical behavior for the optimization problems with dependent data. What is the explanation?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The introduced algorithm, PILOT, provides an explicit convergence rate under the choice of small and constant step sizes. Moreover, the obtained convergence rate matches the previous minimax bound. Convergence rates are studied under the assumptions, which are classical in the optimization literature. The authors present a comprehensive framework for their theoretical analysis, and the exposition of the paper is accessible.", "weaknesses": "The only weakness is the experimental section, which contains rather simple scenarios. At the same time, for the paper which is primarily theoretical, the proposed illustration is sufficient.", "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": "", "extra_scores": {}}, {"review_id": "aCxv9l5TH3", "reviewer": "Reviewer_sDVM", "summary": "The paper introduces two algorithms, PILOT and PILOT+, designed for Policy Evaluation (PE) with non-linear function approximation. Theoretical analysis shows that PILOT, a single-timescale algorithm using VR techniques, achieves an $O(1/K)$ convergence rate with constant step sizes. PILOT+ enhances sample efficiency by adapting batch sizes based on historical stochastic gradient information. Experimental results validate the theoretical findings regarding convergence and sample complexity.", "questions": "1. From Corollary 1, the sample complexity of PILOT is $O(\\sqrt{M}\\kappa^3\\epsilon^{-1} +M)$, where $M$ is the number of state-action pairs sampled by the evaluated policy, and $\\epsilon$ measures the error under the new metric of convergence performance in this paper. Intuitively, to get a accurate estimate of the $V^{\\pi}$, we need a sufficient number of samples (a big $M$). However, it seems that this $\\epsilon$ has nothing to do with $M$. Additionally, I have noticed that the Assumption 1 needs $M$ to be sufficiently large. Can authors give the detailed justification of this explanation? I would like to see how $M$ will affect the accuracy of the policy evaluation.\n\n\n2. For the sample complexity of the algorithm, the first term $O(\\sqrt{M}\\kappa^3\\epsilon^{-1})$ seems redundant, because the total number of samples is fixed, i.e., $M$, and in this paper the first term of sample complexity comes from sampling from this dataset, and this operation does not increase the sample complexity (it will not interact with the environment). Therefore, I think PILOT+ accually saves the computational cost, not sample complexity of PILOT. Can authors explain this concept more carefully?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is fairly well organized and the results provided are impressive.\n\n2. The related work and comparison with other algorithms and techniques are comprehensive.\n\n3. The theoretical guarantee is solid and the paper also demonstrates the effectiveness of the algorithm in practice.", "weaknesses": "1. Since the paper claims the algorithms they propose achieve the first $O(1/K)$ convergence rate ($K$ is the number of\niterations) with constant step-sizes for PE with nonlinear function approximation, it is better to give some brief statistical intuition of achieving this result.  \n\n2. The paper proposes a new metric for convergence performance, and gives the abundant explanation for using this concept, but it is hard to be applied to other performance metric, for example, $|\\widehat{V}^{\\pi}(s) - V^{\\pi}(s)|$, where $\\widehat{V}^{\\pi}$ is the estimate you get from a policy evaluation problem.", "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": "", "extra_scores": {}}, {"review_id": "kj2PXIfNhr", "reviewer": "Reviewer_b5y9", "summary": "This paper introduces a new algorithm (PILOT) to estimate value function with non-linear function approximation. Under appropriate choices of step sizes, the algorithm achieves O(1/K) error after K iterations.", "questions": "* What is K in the paragraph before the questions “ can we develop … ” on page 2? Suppose this the K defined after the question. In that case, the phrasing “ more than O(K) number of iterations to achieve the convergence ” seem to suggests that the algorithm terminates with the exact value function after O(K) iterations, which is probably not the case. Please clarify.\n\n* Point (ii), paragraph (2) of the literature reivew: “our algorithms only require the stepsizes to be sufficiently small, which is easier to tune in practice” —this is not very clear, what does sufficiently small  ? In the previous paragraph a method with O(1/M) step size is criticized so the authors need to be more accurate here.\n\n* Paragraph 1, Section 3: The notation $\\pi: \\mathcal{S} \\rightarrow \\mathcal{A}$ is only for deterministic policies. Please introduce randomized policies properly.\n\n* Algorithm 1 refers to Eq. (4) and Eq. (5) who appear a page later.\n\n* Why do the authors use arrows+name for Figures 1-4 and not just a legend?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is well-written and easy to follow. The literature review is quite complete.\n\n* The results are interesting and the author adequately motivate the problem.\n\n* The numerical experiments are convincing (although they could be polished, see below).", "weaknesses": "* No significant weakness. See my questions below.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)