On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimization
Authors: Ling Liang
Haizhao Yang
Venue: Accepted by TMLR ()

Abstract: We consider a regularized expected reward optimization problem in the non-oblivious setting that covers many existing problems in reinforcement learning (RL). In order to solve such an optimization problem, we apply and analyze the classical stochastic proximal gradient method. In particular, the method has shown to admit an $O(\epsilon^{-4})$ sample complexity to an $\epsilon$-stationary point, under standard conditions. Since the variance of the classical stochastic gradient estimator is typically large, which slows down the convergence, we also apply an efficient stochastic variance-reduce proximal gradient method with an importance sampling based ProbAbilistic Gradient Estimator (PAGE). Our analysis shows that the sample complexity can be improved from $O(\epsilon^{-4})$ to $O(\epsilon^{-3})$ under additional conditions. Our results on the stochastic (variance-reduced) proximal gradient method match the sample complexity of their most competitive counterparts for discounted Markov decision processes under similar settings. To the best of our knowledge, the proposed methods represent a novel approach in addressing the general regularized reward optimization problem.

Published in Transactions on Machine Learning Research (8/2024)
On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimization
Ling Liang
fiang.ling&enn nus. edu
Deportment of Mathematics University of Moryland at College Pork
Haizhao Yang
hayang edu
Department of Mathematics and Department of Compuler Science University of Moryland at College Pork
Reviewed OpenReview: https: // o/penreveee.. net/ permf id= Ve4Puj2LVI
Abstract
We consider a regularized expected reward optimization problem in the non-oblivious setting that covers many existing problems in reinforcement learning (RL). In order to solve such an optimization problem, we apply and analyze the classical stochastic proximal gradient method. In particular, the method has shown to admit O(e-²) sample complexity to an e-stationary point, under standard conditions. Since the variance of the classical stochastic gradient estimator is typically large, which slows down the convergence, we also apply an efficient stochastic variance-reduce proximal gradient method with an importance sampling based ProbAbilistic Gradient Estimator (PAGE). Our analysis shows that the sample com- plexity can improved from O(e to O(e under additional conditions. Our results on the stochastic (variance-reducel) proximal gradient method match the sample complexity of their most competitive counterparts for discounted Markov decision processes under similar settings. To the best of our knowledge, the proposed methods represent novel approach in addressing the general regularized reward optimization problem.
1 Introduction
Reinforcement learning (RL) (Sutton & Barto 2018 has recently become a highly active research area of machine learning that learns to make sequential decisions via interacting with the environment. Tn recent years, RL has achieved tremendous success so far in many applications such control, job scheduling, online advertising, and game-playing (Zhang & Dietterich, 1995 Pednault al.) 2002. Mnih et al. 2013). to mention a few. One of the central tasks of RI. is to solve certain (expected) reward optimization problem for decision-making. Following the rescarch theme, we consider the following problem of maximizing the regularized expected reward:
max F(0) := Egwno [Ro())] G(()), DERA
(1)
where G: RR. - TU [+o0] closed proper convex (possibly nonsmooth) function, x E Rdd, Rg Rd R is the reward function depending on the parameter 0, and no denotes the probability distribution over a given subset. S d parameterized by E R". By adapting the convention in RL, we call ma policy parameterized by 0. Moreover, for the rest of this paper, we denote J(0) := Es-no [Re(z)] the expected reward function in the non-oblivious setting. The learning objective is to learn decision rule via finding the policy parameter 0 that maximizes the regularized expected reward. To the best of our knowledge, the study on the general model [ has been limited in the literature. Hence, developing and analyzing algo frameworks for solving the problem is great interest.
There are large body of works in supervised learning focusing on the oblivious setting Zhang 2004 Hastie
et al. 2009 Shapiro et al. 2021 i.e., [(0) = Ex-r [Ro(r)); where is sampled from an invariant distri-

---

Published in Transactions on Machine Learning Research (8/2024)
bution Clearly, problem []] can be viewed as generalization of those machine learning problems with oblivious objective functions. In the literature, an RL problem is often formulated as discrete-time and discounted Markov decision processes (MDPs) (Sutton & Barto 2018) which aims to learn an optimal policy via optimizing the (discounted) cumulative sum of rewards. We can also see that the learning objective of an MDP can be covered by the problem | with the properly that the function R(x) does not depend on 0 (see Example 3.3 Recently, the application of RL for solving combinatorial optimization (CO) problems which are typically NP-hard has attracted much attention. These CO problems may include the traveling salesman problem and related problems (Bello et al. 2016 Mazyavkina et al., 2021), the reward optimiza- tion problem arising from the finite expression method (Liag & Yang 2022, Song et al. 2023), and the general binary optimization problem (Chen et al. 2023). to name just a few. The common key component of the aforementioned applications is the reward optimization, which could also be formulated as problem [ There also exist problems with general reward functions that are outside the scope of cumulative sum of rewards of trajectories that are used in MDPs. An interesting example is the MDP with general utilitics;
see, e.g., (Zhang et al. 2020a Kumar et al. 2022: Barakat et al.) 2023 and references therein.
Adding regularizer to the objective function is commonly used technique to impose desirable structures to the solution and/or to greatly enhance the expression power and applicability of RL (Lan 2023 Zhan et al. 2023). When one considers the street/simplex parameterization (Agarwal et al. 2021 | of Ta. a regularization function using the indicator function for the standard probability simplex is needed. Moreover, by using other indicator functions for general convex sets, one is able to impose some additional constraints on the parameter& 8. For the softmax parameterization, one may also enforce a bounded constraint to @ to prevent it taking values that are too large. This can avoid potential numerical issues, including the overflow error floating point system. On the other hand, there incomplete parametric policy classes, such as the log-linear and neural policy classes, that are often formulated as {Ta] }), where θ is closed convex set (Agarwal et al., 2021p. In this case, the indicator function is still necessary and useful. Some recent works (see, o.g., (Ahmed et al. 2019: Agarwal et al.) 2020 Mei et al. 2020 Cen et al. 2022) have investigated the impact of the entropy regularization for MDPs Systematic st stids on general convex regularization for MDPs
have been limited until the recent. works (Pham et al. 2020 Lan 2023 Zhan et al. 2023 Finally, problem
[ takes the same form as the stochastic optimization problem with decision-dependdent distributions (see o.g.: (Drusvyatskiy & Xiao 2023) and references therein). , loading to numerous nol-world applications such
as perlormative prediction (Mendler-Dünner et al. 2020 Perdomo et. al.. 2020 concept drift (Gama el al.
2014), strategic classification (Tirtssis et al.) 2024 Milli et al.) 2019). and casual inference (Yao et al.) 2021)
Consequently, we can see that problem ① is in fact quite general and has promising modeling power, as it
covers many existing problems in the literature.
The purpose of this paper to leverage existing tools and results in MDPs and nonconvex optimization for solving the general regularized expected reward optimization problem [1 with general policy parameteri- zation, which, to the best of our knowledge, has not been formally considered in the RL literature. It is well known that the policy gradient method (Williams) 1992 Sutton et al. 1999: Baxter & Bartleti 2001). which lies in the heart of RL, is one of the most competitive and efficient algorithms due to its simplicity and versatility. Moreover, the policy gradient method is readily implemented and can be paired with other effective techniques. In this paper, we observe that the stochastic proximal gradient method, which shares the same spirit of the policy gradient method, can be applicd directly for solving the targeted problem (1) with convergence guarantees to a stationary point. Since the classical stochastic gradient estimator typically introduces a large variance, there is also a need to consider designing advanced stochastic gradient estimators with smaller variances. To this end, we shall also look into a certain stochastic variance-reduced proximal gradient method and analyze its convergence properties. In particular, the contributions of this paper are summarized as follows.
We consider a novel and general regularized reward optimization model 1 that covers many existing important models in the machine learning and optimization literature. Thus, problem admits a promising modeling power which encourages potential applications.
In order to solve our targeted problem, we consider applying the classical stochastic proximal gradient method and analyze its convergence properties. We first demonstrate that the gradient of J()) is Lipschitz continuous under standard conditions with respect to the reward function Ro(-) and
2

---

Published in Transactions on Machine Learning Research (8/2024)
the parameterized policy Te(:). Using the L-smoothness of J(),, we then show that the classical stochastic proximal gradient method with a constant step-size (depending only on the Lipschitz
constant for V-J(-)) for solving problem ( outputs an e-stationary point (see Definition 3.4 within T := 3 iterations, and the sample size for cach iteration is O(e=²), where > 0 is a given lolerance. Thus, the total sample complexity becomes O(e=)) which matches the current
statc-of-the-art sample complexity of the classical stochastic policy gradient for MDPs; see e.g.,
WWiliams 1992
Baxter & Bartlett 2001; Zhang al. 2020b Xiong al.) 2021 Yuan et al. 2022
Moreover, in order to further reduce the variance of the stochastic gradient estimator, we utilize an importance sampling based probabilistic gradient estimator which leads to an efficient single-looped variance reduced method. The application of this probabilistic gradient estimator is motivated by the recent progress in developing efficient stochastic variance-reduees gradient methods for solving stochastic optimization (Li et al. 2021b) and (unregularized) MDPs [Gargiani et al.) 2022 We show that, under additional tochnical conditions, the total sample complexity is improved from O(e to O This result again matches the results of some existing compelitive variance-reduced methods
for MDPs (Papini et al. 2018 Xu al.) 2019 Pham et al. 2020 Huang et al. 2021 Yang et all, 2022; Gargiani al. 2022). Moreover, to the best of our knowledge, the application of the above probabilistic gradient estimator is new for solving the regularized expected reward optimization
The rest of this paper is organized as follows. We first summarize some relative works in Section 2 Next, in Section 3 we present some background information that are needed for the exposition of this paper. Then, in Section we descríbe the classical stochastic proximal gradient method for solving (1) and present the convergence properties of this mothod under standard technical conditions. Soction 5 is dedicated to
describing and analyzing the stochastic variance-reduced proximal gradient method with an importance sampling based probabilistic gradient estimator. Finally, we make some concluding remarks, and list certain limitations and future rescarch directions of this paper in Section 0
2 Related Work
The policy gradient method. One of the most influential algorithms for solving RL problems is the policy gradient method, built upon the foundations established in (Williams) 1992 Sutton et al. 1999: Baxter & Bartlett 2001). Motivated by the empirical success of the policy gradient method and its variants, analyzing the convergence properties for these methods has long been one of the most active research topics
in RL. Since the objective function [0) is generally nonconcave, early works (Sutton et al. 1999 Pirotta
ctt al. 2015) focused on the asymptotic convergence propertics to a stationary point. By utilizing the special
structure in (entropy regularized) MDPs, recent works (Liu el. al., 2019 Mei el al. 2020 Agarwal el al.
2021 Li et al. 2021a Xiao 2022 Cen et al. 2022 Lan 2023 Fatkhullin et al.) (023) provided some exciting results on the global convergence. Mcanwhile, since the exact gradient of the objective function can hardly be computed, sampling- based
saarrmmattedstchhaattt gradients have gained much attention. Therefore, many works investigated the convergence properties, including the iteration and sample complexities, for
these algorithms with inexact gradients; see e.g., (Zhang et al.) |0200b] Liu et al. 2020 Zhang et al. 2021b
Xiong et al., 2021 Yuan et al. 2022 Lan 2023 and references therein.
Variance reduction. While the classical stochastic gradient estimator is straightforward and simple to implement, one of its most critical issues is that the variance of the inexact gradient estimator can be large, which generally slows down the convergence of the algorithm. To alleviate this issue, attractive approach is to pair the hample-based policy gradient methods with certain variance-reduced techniques. Varianco-roduced methods were originally developed for solving (oblivious) stochastic optimization problems (Johnson & Zhang 2013 Nguyen el al.) 2017 Fang et al., 20188: Li el al., 2021b) typically arising from supervised learning tasks. Motivated by the superior theoretical properties and practical performance of the stochastic variance-reducod gradient mothods, similar algorithmic frameworks have recently been applied for
solving MDPs (Papini et al. 2018 Xu et al. 2019 Yuan et al. 2020 Pham et al. 2020 Huang et al.) 2021 Yang et al.
2022
Gargiani et al. 2022
3

---

Published in Transactions on Machine Learning Research (8/2024)
Stochastic optimization with decision-dependent distributions. Stochastic optimization is the core of modern machine learning applications, whose main objective is to learn a decision rule from a limited data sample that is assumed to generalize well to the entire population Drusvyatskiy & Xiao 2023). In the classical supervised learning framework (Zhang, 2004 Hastic et al. 2009 Shapiro et al. 2021), the underlying data distribution is assumed to be static, which turns out be crucial assumption when analyzing the convergence properties of the common stochastic optimization algorithms. On the other hand, there are problems where the distribution changes over the course of iterations of specific algorithm, and these are closely related to the concept of performative prediction (Perdomo et al.) 2020 In this case, understanding the convergence properties of the algorithm becomes more challenging. Toward this, some recent progress has been made on (strongly) convex stochastic optimization with decision-depender distributions (Mendler- Dünner et al. 2020: Perdomo et al. 2020) Drusvyalskiy & Xiao 2023). Moreover, other works have also
considered nonconvex problems and obtained some promising results; see (Dong et al., 2023 Jagadeesan ct al. 2022) and references therein. Developing thcoretical foundation for these problems has become very aclive field nowadays.
RL with general utilities. It is known that the goal of an agent associated with MDP is to seek optimal policy via maximizing the cumulative discounted reward (Sutton & Barto 2018). However, there are decision problems of interest having more general forms. Beyond the scope of the expected cumulative reward in MDPs, some recent works also looked into RT. problems with general utilities; see e.g., (Zhang et al. 2020a Kumar et al. 2022 Barakat et al. 2023 as mentioned previously, Global convergence results can also be derived via investigating the hidden convex structure (Zhang al. 2020a) inherited from the MDP.
3 Preliminary
In this paper, we assume that the optimal objective value for problem D denoted by F², is finite and attained, and the reward function Re(-) satisfies the following assumption. Assumption 3.1. The following three conditions with respect to the function Ro(-) hold:
There exists constant U such that
sup PER" ZERd
[Ro(r)) U.
Ro(-) twice continuously differentiable with respect to 0, and there exist positive constants C and Ön such that
sup OER", ZERd [o S Cg.
[V)Ro(>)]1> & Ōn.
sup OER* DERS
The first condition on the boundedness of the function Ro(-), which is commonly assumed in the literature (Sutton& & Barto 2018), ensures that. (0) is well-defined. And the second condition will be used to guarantee the well-definiteness and T-smoothness of the gradient VoJ(O). We remark here that when the reward function Rx)x) does not depend on (see e.g., Example 3.3), then the second assumption holds automatically.
To determine the (theoretical) learning rate in our algorithmic frameworks, we also need to make some standard assumptions to establish the T-smoothness of J(.).
Assumption 3.2 (Lipschitz and smooth policy assumption). The function log To(x:) is twice differential with respect to 0 E R.n and there erist posilive constants C and C₁ such that
sup *ER*, BER
(ollggo(z)) S Cg:
sup EER4, BER"
[[/ Ch.
This assumption is a standard one and commonly employed the litcrature when studying the convergence properties of the policy gradient method for MDPs; see e.g., (Pirotta al. 2015 Papini et al. 2018 Xu al. 2020 Pham et al. 2020 Zhang al. 2021a Yang et al. 2022 and references therein.
4

---

Published in Transactions on Machine Learning Research (8/2024)
Under Assumption 3.1 and Assumption 3.2 it is easy verify that the gradient for the expected reward
function (0) can be written as:
VoJ Vo (F - -
(VoRo(t) + Ro(Ø)
VoTo(T) To( To (x)
= Exwar (Ro(z)Volog=eel) + VoRo(z)).
We next present an example on the discrete-time discounted MDP, which can be covered by the general model ①
Example 3.3 (MDP). We denole a discrele-time discounted MDP as M: P, y.P)) where S and A denote the state space and the action space, respectively, P(s'|s,a) a) is the stote transition probability from s to s' after selecting the action a, R: S x A + [0,0] is the reward function that is assumed to be uniformly bounded by a constant U > 0, E [0, 1) the discount factor, and pu is the initial state distribution.
The agent selects actions according a stationary random policy to (-1-) A S [0,1] parameterized by E I. Given an initial state so S, a trajectory = {st, De, Te+10=0 11-1 can then be generated, where Su P, a4 #t(-(s:), r1+1 R(st, 0i), $1+1 P(.)st,.)) and H > 0 is finite horizon, and the accumulated discounted reward of the trajectory
be defined R(T) Σ r Then, the learning objective is
(=0
to compute optimal porameter 0r that mazimizes the expected reward function J(0) i.c.,
0r argmaxę I(0) Er~pe [R(T)],
(2)
where po(T) po(sa) I P(s at [o(ar|))) denotes the probability distribution of a trajectory т being sampled from pa that is parameterized by 0.
In the special case when S = {s} (t.e., |S| = 1) and y 0, the MDP reduced to multi- bandit problem (Robbins, 1952) with reward function simplified as R A + R. Particularly, trajectory T = {s, with the horizon H, = O is generated, where ~ (.) == No (-1s), and the accumulated discounted reward reduces to R(x)= = R(a)- As a consequence, problem 2 can be simplified as
max [(0) Ea-ps [[(a)].
PER
By adding a conver regularizer G()) to problem we get the following regularized MDP:
max BER"
ET-pp [R(T)] G(0),
which was considered in (Pham et al. 2020 However, it is clear that R(T) does not depend on 0. Hence, the above regularized MDP is a special case of the proposed regularized reward optimization problem (1]
One can check that the gradient V [0) has the sollowing form
(uuan el al. 2022
Ø-1
VoJ = E Errop
Σ t=
R's, a.)
Σ Vo log fo((r)ss))
#=0
Being a composite optimization problem, problem admits the following first-order stationary condition
0 E VoJ +g(().
(3)
Here, ag(-) denotes the subdifferential of the proper closed and convex function g(-) which defined as 0g(0) p G(0') 2 G(0) (g. 0' 0), v0).
It is well-known that ag(0) is a nonemply closed convex subset. of TR for any 0 E RD such that ((0)
(see e.g., (Rockafellar 1997 ). Note that any optimal solution of problem [ satisfies the condition 3
while the reverse statement is generally not valid for nonconcave problems, including the problem ( The
condition 3 leads to the following concept of stationary points for problem
Here, the trajectory 7 and the distribution Ae correspand and Æe respectively.
5

---

Published in Transactions on Machine Learning Research (8/2024)
Definition 3.4. A point 0 E R is called stationary point for problem 11 if it satisfies the condition (3) Given lolerance > O, slochastic oplimizalion method allains an (expected) e-slalionary point, denoled as 0 R", if
Er dist (0.
se,
where the expectation is laken with respect to all the randomness caused by the algoritim, after rumning it T iterations, and C) denotes the distance between point x and a closed convex set
Remark 3.5 (Gradient mapping). Note that the optimality condition
3 can rewritten as
0 = G,) = Proxng (0 (V+N)) -
for some v) > O, where
Prox, (0) argming { (0(0))
1 2n
110 01p)
denotes the prozimal mapping of the function G(-). The mapping G.(.) is called the gradient mapping in the field of optimization Beck 2017). It is easy to verify that if for a R", it holds that
dist (0,-vo](0)) 0g(0)) se
then there erists vector d satisfying |d]| S e such that
+ E
which is equivalent to saying that
= Prox, (nd + 1 VoJ
Moreover, we can verify that (by using the firm noneryansiveness of (-)x, see e.g., BBck 2017))
[0), 1 1 ||rrox,g (0 (V+ All = |d S.
Therefore, we can also characterize an (erpected) e-stationary point by using the following condition
Er [0, se.
The main objective this paper is to study the convergence propertics, including iteration and sample complexities, of the stochastic (variance-reducee)) proximal gradient method to a e-slationary point with pre-specified > 0. Note that all proofs of our results are presented in the appendix. Moreover, we acknowledge that analysis is drawn upon classical results in the literature.
4 The stochastic proximal gradient method
In this section, present and analyze the stochastic proximal gradient method for solving the problem The fundamental idea of the algorithm is to replace the true gradient VoJ(O), which are not available for most of the time, with stochastic gradient estimator in the classical proximal gradient method (Beck 2017). The method can be viewed as extensions to the projected policy gradient mothod with direct parameterization
(Agarwal et al. 2021] and the stochastic policy gradient method for unregularized MDPs (Wlliams 1992
The detailed description the algorithm is presented in Algorithm
For notational simplicity, we denote
g 0) = Vo log (x)))(() (o))())
From Algorithm 1 we see that at each iteration, data points, namely {a* ..........a NNN are sample according to the current probability distribution mac. Using these data points, construct REINFORCF-type

---

Published in Transactions on Machine Learning Research (8/2024)
Algorithm The stochastic proximal gradient method
1: Input: initial point 00, sample size N and the learning rate 1) > 0. for t= ..... do
Compute the stochastic gradient estimator:
g' Σ 2g(00,00 0²),
N
where {a wf.,), are sampled independently according to wee Update
0++ = Proxxs (0' + =gng)
5: end for
6: Output: Hr selected randomly from the generated sequence {0') YT-
stochastic gradient estimator g²- Then, the algorithm just performs a proximal gradient ascent updating. Let T > 0 be the maximal number of iterations, then a sequence {0') ) can be generated, and the output solution is selected randomly from this sequence. Next, we shall proceed to answer the questions that how to choose the learning rate 0, how large the sample size N should be, and how many iterations for the algorithm to output an c-stationary point for a given c >> 0. theoretically. The next lemma establishes the L-smoothness of (.) whose proof is given at Appendix A.1
Lemma 4.1. Under Assumptions and 3.2 the gradient of J is L-smooth, i.e.,
[VoT(0) - VoJ( $ =00 0'1l. v0,0' E RR"
with L := U(C CC)) Cn + 2C,0, >
Remark 4.2 (L-smoothness in MDPs). For an MDP with finite action space and state space as in Eaample 3.3 the Lipschitz constant of V.J(.)) can be expressed in terms of |A), |S] and 7, We refer the reader to (Agarwal et al. 2021- Xiao 2022) for more details.
As a consequence of the L-smoothness of the function J()), we next show that the learning rate can be chosen as positive constant upper bounded by a constant depends only on the Lipschitz constant of V VeJ()) (-). For notational complicity, denote A := F F(00) 0 for the rest of this paper.
Theorem 4.3. Under Assumptions 3.1 and 3.2 if we set 17 E (0, ) then Algorithm outputs a point 0 satisfying
Er dist (0, - VV-JJ + 0G( 2
)
2
2
Σ
Er 1lo'
+
A 2 4 T
nl((1 2nI.))
T
7(1 2l21.)
where Er is defined in Definition
3.4
The proof of the above theorem is provided in Appendix A.2 From this theorem, if one sets g' = VOT()) i.e., l|g VoJ(O'))] 0, then there is no randomness along the iterations and the convergence property is reduced to
min dist (o.-v=7()+ 181ST
1 )
which is implied by classical results on proximal gradient method (see e.g., [Bekk 2017 However, since the exact full gradient VoJ(()) is rarely computable, it is common to require the variance (i.e., the trace of the covariance matrix) of the stochastic estimator to be bounded. The latter condition plays an essential role in analyzing stochastic first-order methods for solving nonconvex optimization problems, including RL
applications; see, e.g., [Beck 2017 Papini et al. 2018 Shen et. al. 2019
Lan 2020
Yang et al. 2022
7

---

Published in Transactions on Machine Learning Research (8/2024)
Lemma 4.4. Under Assumptions 3.1 and 3.2. there erists a constant 0 such that for any 0
Bg [10(2; 0) V VoJ(O)] s
The proof of Lemma 4.4 is given in Appendix
By choosing suitable sample size N, we rely Lemma 4.4 to make the term Er llg VeJ VeJ (+)) || in Theorem 4.3 small, for every t I T. Then, Theorem
4.3 implies that Algorithm admits an expected O(T convergence rate to stationary point. These results are summarized in the following theorem; see Appendix A.4 for a proof.
Theorem 4.5. Suppose that Assumptions 3.1 and 3.2 hold. Let > 0 be a given accuracy. Running the
Algorithm for
A
4
) - -0(E
T
11
711
2TyL)
iterations with the learning rate 7
and the sample size
21
o²
) =((E2)
ML(1 2nL 2
N
4
22
outputs a point 0" satisfying
Er dist (o. + - Se.
Moreover, the sample complexity is 4)e
As already mentioned in the introduction, the total sample complexity of Algorithm [ to an e-stationary point is shown to be O)e=A), which matchos the most competitive sample complexity of the classical stochastic policy gradient for MDPs (Williams) 1992. Baxter & Bartleit 2001 Zhang el al. 2020b Xiong et al. 2021 Yuan et al. 2022).
Remark 4.6 (Sample size). Note that the current state-of-the-ar iteration complecity for the (small-batch) stochastic gradient descent method is T = O(=²) with := min O(T-1/2)); see, e.g., (Ghadima & Lan 2013). The reason for requiring larger batch-size in Theorem 4.5 is to allow a constant learning rate. To the best of our knowledge, to get the same convergence properties as Theorem 4.5 under the same conditions for problem ① the large batch-size is required.
Remark 4.7 (Global convergence). As mentioned in introduction, some recent progress has been made for analyzing the global convergence properlies of the policy gradient methods for MDPs, which greatly rely the concepts of gradient domination and its extensions [Agarwal et al. 2021 Mei et al. 2020: Xiao 2022-- Yuan et al.) 2022 Gargiani et al.) 2022). This concept is also highly related to the classical Pt-condition (Polyak] 1963) and KL-condition Bolte et al.) (2007) in the field of optimization. One of the key ideas is to assume or verify that the difference between the optimal objective function value, namely F*, and F(0) can be bounded by the quantity depending on the norm of the gradient mapping at an arbitrary point. In particular, suppose that there exists a posilive constant w such that
(F = VOER". |G,,
where G. is defined in Remark 3.5 (sce e.g., iterations, one can easily check that
Xiao 2022 ). Then, after running Algorithm 2 for 0(e-?
Er
F - -(02)) S 2/
As a conclusion, by assuming or verifying stronger conditions, one can typically show that any stationary point of the problem (1) is also a globally optimal solution. This shares the same spirit of [Zhang et al.) 2020a)) for MDPs with general utilities. We leave it a future research to analyze the global convergence of the problem 1
8

---

Published in Transactions on Machine Learning Research (8/2024)
5 Variance reduction via PAGE
Recall from Theorem 4.3 that, there is a trade-off between the sample complexity and the itcration complexity of Algorithm In particular, while there is little room for us to improve the term _
2 + 5( 1T
which corresponds to the iteration complexity, it is possible to construct g in an advanced manner to improve the sample complexity. Thercfore, our main goal this section to reduce the expected sample
complexity while keeping the term Σ Er [[VoJ(0') - s'I]]] small. We achieve this goal by considering
the stochastic variance-reduced gradient methods that have recently attracted much attention. Among these ceriance-reduced mel hods, as argued in (Gargiani et al. 2022), the ProbAbilistic Gradient Estimator (PAGE) proposed in (Li et al., 2021b) has a simple structure, and can lead to optimal convergence properties. These appcaling fcatures make attractive in machine learning applications. Therefore, in this section, we also consider the stochastic variance-reduced proximal gradient method with PAGE for solving the problem
PAGE is originally designed for the stochastic nonconvex minimization in the oblivious setting:
min f(0) EE-~ (1 (z)
where π is a fixed probability distribution and F: R2 x R + IR is a certain differentiable (and possibly nonconvex) loss function. For stochastic gradient-typp type methods, a certain stochastic gradient estimator for f is required for performing the optimization. At the f-th iteration, given a probability Pt [0, 1] and the current gradient estimator g", PAGE proposed replace the vanilla mini-batch gradient estimator with the following unbiased stochastic estimator:
V VoF(1 (10,001))))
with probability Pt.
N1
x g
N₂ Σ Vol (ee, with probability Pts 5=1
VoF(x (0,1
N
where {2²} are sampled from n, N1, N2 denote the sample sizes. Some key advantages of applying PAGE are summarized follows. First, the algorithm is single-lopped, which admit simpler implementation pared with existing double-looped variance reduced methods. Second, the probability Pt can be adjusted dynamically, leading to more flexibilities. Third, one can choose N₂ to be much smaller than N1 to guarantee the same iteration complexity as the vanilla SGD. Thus, the overall sample complexity can be significantly reduced. However, the application PAGE to our setting neods significant modifications and extensions, which we shall demonstrate below. To the best of our knowledge, the application of PAGE for solving the general regularized reward optimization problem in the non-oblivious setting considered in this paper new.
For notational simplicity, for the rest of this section, denote
(T(x) To (xr) g(x, 0),
Ia (x, 0,0)
for 8 E R", Rd, where =a(x) no (2)
denotes the importance weight between my and nø. Note also that
To())) 1.
E
Teg (x)
The description of the proposed PAGE variance-reduced stochastic proximal gradient method is given in A Algorithm
It is clear that the only difference between Algorithm | and Algorithm 2 the choice of the gradient estimator. At each iteration of the latter algorithm, we have two choices for the gradient estimator, where, with probability p, one chooses the same estimator as in Algorithm T with sample size N1, and with
9

---

Published in Transactions on Machine Learning Research (8/2024)
Algorithm 2 The variance-reducel stochastic proximal gradient method with PAGE
1: Input: initial point 00, sample sizes N1 and N2, a probability p P (0, 1], and the learning rate 1) > 0. Compute
1 N 8 == N1
Σ
g(
where {xo0)) are sampled independently according to Tga.
3: for = o...., 1 do
4: Update
8 Prox, (0' ng")
Compute
1
(1
Oc+1),
with probability p.
N
g++l=
N2
No Iw +1 0², 0c+)) + ggg, with probability -
1
2
N₂
where (attld] are sampled independently according to a8111.
6: end for Output: 0r selected randomly from the generated sequence {0m)
probability 1-21 p, one constructs the estimator in clever way which combines the information of the current
iterate and the previous one. Since the data set (af+1,1 ...., + ( is sampled according to the current probability distribution Tot,i, we need to rely on the importance weight between of and 0t+1 and construct
N₂
the gradient estimator
Iwl (x 10, 00, which is an unbiased estimator for VoJ(O") so that g N2 Σ
becomes unbiased estimator of VoJ(H Indeed, one can easily verify that for any 0,0' R", it holds that
Exwny (a, (o)(
(4)
i.e. g(r,0, 0,0') is an unbiased estimator for VoJ provided that Tgr.
Next, we shall analyze the convergence properties of Algorithm 2 Our analysis relies on the following assumption the importance weight, which essentially controls the change of the distributions.
Assumption 5.1. Let 0,0' R", the importance weight between va and ag. is well-defined and there crists conslant C > O such that
(
- 1) -1
[T To (x)
C
Clearly, the significance of the constant Cg (if exists) may depend sensitively on and 0', To see this, let us assume that for any E R Th = 0 is discrete distribution over a set of finite points {æx Hi= for which To (xx) = f > for all = 1...., n. Now, suppose that = 8' + Ao with A < 1. Then, a simple calculation shows that
( [e(()) - 1) ]1
2
8
2
a O A
0 0
Egwnstr
0
To (x)
However, it is possible that there exists certain 0% 0 tiny. In this case, C. can be huge even infinity. Fortunately, the regularization term G(0) can help to avoid such undesired situations via imposing
the constraints 0₂ 2 > 0 for all k. In this case, we see that Σx= d < < " =
0f
10

---

Published in Transactions on Machine Learning Research (8/2024)
Remark 5.2. Note that Assumption 5.1 is also employed in many cristing works (Papini et al. 2018 Xu
et al. 2019: Phom el al.) 2020: Yuan el al. 2020; Garriann el al. 2022). However, this assumplion could be too strong, and it is not checkable in general. Addressing the relaration of this assumption through the development of a more sophisticated algorithmic framework is beyond the scope of this paper. Here, we would like to mention some recent progress on relazing this stringent condition for MDPs. By constructing addi- tional stochastic estimators for the Hessian matrix of the objective function, (Shen et al.) 2019) proposed a fression-aided woliey-gradient-uype method that improves the sample compleziity from Ole 1) to O(E without assuming Assumption 5.1 Later, by explicitly controlling changes in the parameter 0, (Zhang et al., 2021a) developed a truncated stochastic incremental variance-rrducct policy gradient method to prevent the variance of the importance weights from becoming excessively large leading to the O(E-5) sample complex- ily. By ulilizing general Bregman divergences, Yuuan el al. (022) proposed a double-looped variance-reduced mirror policy optimization opproach and established an O(e ") sample complexity, without requiring Hessian information or Assumption 5.1 Recently, following the research theme as (Shen et all, 2019), (Salehka- leybur et al., (2022) also incorporated second-order information inlo the stochastic gradient estimator. By using momentum, the reduced algorithm proposed in (Salchkoleybar et al.) 2022) has some ap- pealing features, including the small batch-size and parameter-free implementation.. Recently, by imposing additional conditions, including the Lipschitz continuity of the Hessian of the score function Vo Volog ao and the noneer-noo--eeeeerace condition of the policy, (Falkhullin el al. 2023) derived improved (global) con- vergence guarantees for solving MDPs. We think that the above ideas can also be exploved for solving the generol model
The bounded variance of the importance weight implies that the (expected) distance between g( 0') and 9i (z, 0, ) is controlled by the distance between and 0', for any given 0, 0' E Rdd In particular, we have the following lemma, whose proof is provided in Appendix A..
Lemma 5.3. Under Assumplion
3.1 Assumption
3.2 and Assumplion 5.1 then it holds that
Bx [llots,0) 0')
I (x, (x,000)) < -0100-0011 ===0000))))= 011,
where C is a constant defined as
C = GU + GC +66 + (AU2Og + +00%) (20% + Cn) + 1).
Under the considered assumptions, we are able to provide an estimate for the term T-1
Σ ET ||g't VoJ(0')] which plays an essential role in deriving an improved sample complexity t=o of Algorithm The results are summarized in the following Lemma 5.4 Appendix A.6 for proof which shares the same spirit as (Li et al. 2021b Temma 3 & 4).
Lemma 5.4. Suppose that Assumption be the sequences generated by Algorithm
Assumption 3.2 and Assumption 5.1 hold. Let {g'} and {0}} then it holds that
(1-
(1-p)Cn PN2T(11 - 2T
T
po T 0² 2n(1 - 2n(1-p)CA pN2(1 - (17
Σ
NN1 +
We are now ready to present the main result on the convergence property of the Algorithm 2 by showing how to select the sample sizes N₃ and N2, probability p, and the learning rate 77. Intuitively, Ni is typically a large number and one does not want to perform samplings with N1 samples frequently, thus the probability p and the sample size N2 should both be small. Given N1, N2 and p, we can then determine the value of n such that 7 < 2r.- Consequently, the key estimate in Theorem 4.3 can be applied directly. Our results are summarized in the following theorem. Reader is referred to Appendix A.7 for the proof of this result.
Theorem 5.5. Suppose that Assumption 3.1 Assumption 3.2 and Assumption 5.1 hold. For a given e e N₂ (0, 1), we set p == N. with N₁ : O(e 2) and N₂ == VN O(1-)). Choose learning rate v salisfying
11

---

Published in Transactions on Machine Learning Research (8/2024)
n (2, + +213]] Then, running Algorithm 2 for := O(e iterations outputs point 0T satisfying
Er dist (o.- sea
Moreover, the total expected sample complexity is 3).
By using the stochastic variance-reduce gradient estimator with PAGE and the importance sampling tech- nique, we have improved the total sample complexity from O(e to (c--),, under the considered conditions. This result matches with the current competitive results established in (Xu al.) 2019 Yuan al., 2020; Pham et al. 2020 Gargiani et al. 2022) for solving MDPs and is applicable to the general model (1). Finally, as mentioned in Remark 4.7] by assuming or verilying stronger conditions, such the gradient domination and its extensions, it is also possible to derive some global convergence results. Again, such possibility is left to a future research direction.
6 Conclusions
We have studied the stochastic (variance-reduced) proximal gradient method addressing a general regularized expected reward optimization problem which covers many existing important problem in reinforcement learning. We have established the O(e*t) sample complexity of the classical stochastic proximal gradient method and the (()-)) sample complexity of the stochastic variance-reduced proximal gradient method with importance sampling based probabilistic gradient estimator. Our results match the sample complexity of their most competitive counterparts under similar settings for Markov decision processes.
Meanwhile, we have also suspected some limitations in the current paper. First, due to the nonconcavity of the objective function, we found challenging derive global convergence propertics the stochastic prox- imal gradient method and its variants without imposing additional conditions. On the other hand, analyzing the sample complexity for achieving convergence to second-order stationary points-theen
avoiding saddle points-may be more realistic and feasible (Arjevani et al. 2020). Second, the bounded variance condition for the importance weight turns out to be quitc strong and can not be verified in general. How to relax this condition for our general model deserves further investigation. Last but not least, since we focus more on the theoretical analysis in this paper and due to the space constraint, we did not conduct any numerical simulation to examine the practical efficiency of the proposed methods. We shall try to delve into these challenges and get better understandings of the proposed problem and algorithms in future research.
Finally, this paper has demonstrated the possibility of pairing the stochastic proximal gradient method with efficient variance reduction techniques (Li et al.) 2021b) for solving the reward optimization problem ① Beyond variance-reduced methods, there are other possibilities that allow one deriving more sophisticated algorithms. For instance, one can also pair the stochastic proximal gradient method with the ideas of the actor-critic method (Konda & Tsitsiklis 1999), the natural policy gradient method (Kakade) 2001), policy mirror descent methods (Tomar al.) 20200] Lan 2023), trust-region methods (Schulman et al. 2015 Shani et al. 2020), and the variational policy gradient methods (Zhang et al. 2020a). We think that these possible generalizations can lead to more exciting results and make further contributions to the literature.
Acknowledgments
We thank the action editor and reviewers for their valuable comments and suggestions that helped to improve the quality of the paper. The authors were partially supported by the US National Science Foundation under awards DMMS2244988,, DMMS-2006333, and the Office of Naval Research Award 400017-23-1-2007.
References
Alckh Agarwal, Sham M Kakade, Jason Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pp. 64-66. PMI.R, 2020.
12

---

Published in Transactions on Machine Learning Research (8/2024)
Alckh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431 4506, 2021.
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understanding the impact of entropy on policy optimization. In International conference machine learning, pp. 151-160. PMLR, 2019.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Ayush Sekhari, and Karthik Sridharan. Second- order information in non-convex stochastic optimization: Power and limitations. In Conference Learning Theory, pp. 242-299. PMLR, 2020-
Anas Barakat, llyas Fatkhullin, and Niao He. Reinforcement learning with general utilities: Simpler variance reduction and large stato-action space. arXiv preprint (XXw:2306.0183) 2023.
Jonathan Baxter and Peter L Bartlett. Infinitehhorizon policy-gradient estimation. journal of artificial intelligence research, 15:319 350, 2001.
Amir Beck. First-order methods in optimization. SIAM, 2017.
Irwan Bello, Hien Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial opti- mization with reinforcement learning. arXiv preprint urXiv:1611.09940, 2016.
Jérôme Bolte, Aris Daniilidis, and Adrian Lewis. The lojasiewicz incquality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM Journal on Optimization, 17(4): 1205-1223, 2007.
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4):2563 2578, 2022.
Cheng Chen, Ruitao Chen, Tianyou Li, Ruichen Ao, and Zaiwen Wen. Monte carlo policy gradient method for binary optimization. arXiv preprint 0ab::2307.007860 2023.
Roy Dong, Heling Zhang, and Lillian Ratliff. Approximate regions of attraction in learning with decision- dependent distributions. In International Conference on Artificial Intelligence and Statistics, pp. 11172- 11184. PMLRR, 2023.
Dmitriy Drusvyatskly and Lin Xiao. Stochastic optimization with decision-dependent distributions. Mathe- matics of Operations Research, 48(2):954499) 998, 2023.
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.
Tyas Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao He. Stochastic policy gradiont methods: Im- proved sample complexity for fisher-non-deggnnrrate policies. In International Conference on Machine Learning, pp. 9827-9869, PMLR, 2023.
João Gama, Indré Žliobaité, Albert Bifet, Mykola Pechenizkly, and Abdelhamid Bouchachia. A survey on concept drift adaptation. ACM computing surveys (CSUR), 46(4):1-37, 2014.
Matilde Gargiani, Andrea Zanelli, Andrea Martinelli, Tyler Summers, and John Lygeros. Page-pg: A simple and loopless varianco-roduced policy gradient method with probabilistic gradient estimation. International Conference on Machine Learning, pp. 7223-7240. PMLR, 2022.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and weroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23(4))2341-228) 2013.
Trevor Hastie, Robert Tibshirani, Jerome Friedman, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009.
13

---

Published in Transactions on Machine Learning Research (8/2024)
Feihu Huang, Shangqian Gao, and Heng Huang. Bregman gradient policy optimization. orXiv preprint arXiv:2166.12) 12112, 2021.
Meena Jagadeesan, Tijana Zrnie, and Celestine Mendler-Dünner. Regret minimization with performative feedback. In International Conference on Machine Learning, pp. 9760 9785. PMLR, 2022.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
Navdeep Kumar, Kaixin Wang, Kfir Levy, and Shie Mannor. Policy gradient for reinforcement learning with general utilities. orXiv preprint arXiv:2210.0090 2022.
Guanghui Lan. Pirst-order and stochastic optimization methods for machine learning, volume 1. Springer, 2020.
Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling com- plexity, and generalized problem classes. Mathemalical programming, 198(1):1059-111) 1106, 2023.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Softmax policy gradient methods can take exponential time to converge. In Conference on Learning Theory, pp. 3107 3110. PMLR, 2021a.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International conference on machine learning, pp. 6286-668 6295. PMLR, 2021b.
Senwei Liang and Haizhao Yang. Finite expression method for solving high-dimensional partial differential equations. arXie preprint 2xXiv22266101221 2022.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural proximal/trus region policy optimization allains globally optimal policy. arXie preprinl 1906. 10306, 2019.
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-redueed)) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33: 7624-7636, 2020.
Nina Mazyavkina, Sergey Sviridov, Sorgei Ivanov, and Evgeny Burnaev. Reinforcement learning for combi- natorial optimization: A survey. Computers Operations Research, 134:105400, 2021.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference Machine Learning, pp. 6820-6820 PMLR, 2020.
Celostine Mendler-Dünner Juan Perdomo, Tijana Zrnic, and Moritz Hardt. Stochastic optimization for performative prediction. Advances in Newral Information Processing Systems, 33:4929 4939, 2020.
Smitha Milli, John Miller, Anca D Dragan, and Moritz Hardt. The social cost of strategic classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 230-23- 2019.
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, Ioannis Antonoglon, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXie preprint arXiv:1312.5602 2013.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: novel method for machine learning problems using stochastic recursive gradient. In International conference on mochine learning, pp. 2613- 2621. PMLR, 2017.
14

---

Published in Transactions on Machine Learning Research (8/2024)
Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reduced policy gradient. In International conference on machine learning, pp. 4026 4035. PMT.R, 2018.
Edwin Pednault, Naoki Abe, and Bianca Zadrozny. Sequential cost-sensitive decision making with rein- forcement learning. In Proceedings of the eighth ACM SIGKDD international conference Knowledge discovery and data mining, pp. 259-268, 2002.
Juan Perdomo, Tijana Zrnie, Celestine Goadler-Dünnees and Moritz Hardt. Performative prediction. In International Conference on Machine Learning, pp. 7599-7609. PMLR, 2020.
Nhan Pham, Lam Nguyen, Dzung Phan, Phuong Ha Nguyen, Marten Dijk, and Quoc Tran-Dinh. hybrid stochastic policy gradient algorithm for reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 374 385. PMLR, 2020.
Matteo Pirotta, Marcello Restelli, and Luca Bascetta. Policy gradient in lipschitz markov decision processes.
Machine Learning, 100:255 283, 2015.
Boris T Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics, 3(4):864 878, 1963.
Herbert Robbins. Some aspects of the sequential design of experiments. 1952.
R Tyrrell Rockafellar. Convez analysis, volume 11. Princeton university press, 1997.
Saber Salehkaleybar, Sadegh Khorasani, Negar Kiyavash, Niao He, and Patrick Thiran. Momentum-bass based policy gradient with second-order information. arXiv preprint 2255:220500825. 2022.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global con- vergence and faster rates for regularized mdps. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 5668-5675, 2020.
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski. Lectures on stochastic programming: modeling and theory. SIAM, 2021.
Zebang Shen, Alejandro Ribeiro, Hamed Hassani, Hui Qian, and Chao Mi. Hessian aided policy gradient. In International conference on machine learning, pp. 5729 5738. PMLR, 2019.
Zezheng Song, Maria K Cameron, and Haizhao Yang. A finite expression method for solving high-dimensional committor problems, arXiv preprint crXiv:2306.1223 2023.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Manan Tomar, Lior Shani, Yonathan Efroni, and Mohammad Ghavamzadch. Mirror descent policy opti- mization. arXiv preprinl arXiv:2005.095: 09814, 2020.
Stratis Tsirtsis, Behzad Tabibian, Mocin Khajehnejad, Adish Singla, Bernhard Schölkopf, and Manuel Gomez-Rodriguez. Optimal decision making under strategic behavior. Management Science, 2024.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8:229 256, 1992.
Lin Xiao. On the convergence rates of policy gradient methods. The Journal of Machine Learning Research, 23(1):12887-122)) 12922, 2022.
15

---

Published in Transactions on Machine Learning Research (8/2024)
Huaqing Xiong, Tengyu Xu, Yingbin Liang, and Wei Zhang. Non-asymptotic convergence of adam-type reinforcement learning algorithms under markovian sampling. In Proceedings of the AAAT Conference Artificial Intelligence, volume 35, pp. 10460 10468, 2021.
Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recursive variance reduction. Xiv preprint arXit:1909.08611 2019.
Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic varianco-roduced policy gradient. In Uncertainty in Artificial Intelligence, pp. 541-551. PMLR, 2020.
Long Yang, Yu Zhang, Gang Zheng, Qian Zheng, Pengfei Li, Jianhang Huang, and Gang Pan. Policy opti- mization with stochastic mirror descent. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 8823 8831, 2022.
Liuyi Yao, Zhixman Chu, Sheng Li, Yaliang Li, Jing Gao, and Aidong Zhang, A survey on causal inference. ACM Transactions on Knowledge Discovery from Data (TKDD), 15(5):1-46, 2021.
Huizhuo Yuan, Xiangru Lian, Ji Liu, and Yuren Zhou. Stochastic recursive momentum for policy gradient methods. arXvv preprint ar Xiv::2003 04302, 2020.
Rui Yuan, Robert M Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, pp. 3332 3380. PMLR, 2022.
Wenhao Zhan, Shicong Cen, Baihe Huang, Yuxin Chen, Jason D Lee, and Yuejic Chi. Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence. SIAM Journal on Optimization, 33(2)_101111091, 2023.
Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gra- dient method for reinforcement learning with general utilities. Advances in Neural Information Processing Systems, 33:4572 4583, 2020a.
Junyu Zhang, Chengzhuo Ni, Csaba Szepesvari, Mengdi Wang, et al. On the convergence and sample efficiency of variance-reduced policy gradient method. Advances in Neural Information Processing Systems, 34:2228 14:2228-2240,, 2021a.
Junzi Zhang, Jongho Kim, Brendan O'Donoghue, and Stephen Boyd. Sample efficient reinforcement learning with reinforce. In Proceedings of the AAAT conference on artificial intelligence, volume 35, pp. 10887- 10895, 2021b.
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58(6):3586 3612, 2020b.
Tong Zhang. Solving large scale lincar prediction problems using stochastic gradient descent algorithms. In Proceedings of the twenty-firtt international conference on Machine learning, pp. 116, 2004.
Wei Zhang and Thomas G Dietterich. A reinforcement learning approach to job-shop scheduling. In IJCAI, volume 95, pp. 1114-1120. Citeseer, 1995.
A Proofs
A.1 Proof of Lemma 411
Proof of Lemma 4.1 One could establish the L-smoothness of J()) via bounding the spectral norm of the
Hessian (.J(.). To this end, we first calculate the Hessian of J as follows:
(2J(0) = VoRzaro (Ro Volg (x))
Vo / (o + (o
16

---

Published in Transactions on Machine Learning Research (8/2024)
/ Ro(x))o(a) (( tog (olo dx
/ (iRo(I) 23) + 2 Ro( ( dx
= E
Ro x V log To (x)) Ex Ro Vo xo Vo log xx(x)
+ B
V (x)) 2B Vog
log
Then, by the triangular inequality, it holds that
[ mo))l + sup V8J(0)112 v sup
R Vo log o [og
FERS, DER"
EER*, BER"
+ sup
1i +2 sup DERY DER
VoRa Voloo (o)
zERd, dERn
SU(C C.) Cr + +2C,C..
Thus, I is L-smooth with : UC; + C.) + Cn + 20,0,, and the proof is completed.
A.2 Proof of Theorem 4.3
Proof of Theorem 4.3 From Lemma 4.1
that
J(O J(0') (VoJ()),
2 11 -0112 09112
(5)
By the updating rule of g++1, we see that
(0',0e+2 0²) + 21
100t2 - 0913 + g( s $9(0"),
(6)
J² (0++1 0¹) E a0((0))).
(7)
Combining 5 and 66
we see that
I(0(+1) + (g', 00',0'11 -0011-00)
1 - 10++1
-0111- -g(0
-0 2n
2 J(0) + (VoJ(0') gc+1 - -0)) 10'+1 00112 C(00).
Rearranging terms, we can rewrite the above inequality as
- nL ||0e+1 - 0-1 =(0+)) + VoJ 00)
(8)
2m
By the Canchy-Schwarz inequality, we see that
1 119 VoJ(1))12 L |1 - -0112
1
( - VoJ(0') 0 00) )
21
which together with g implies that
1
10 - 0/112 < - +
21 |19 20J(0
1
2m
Summing the above incquality across t = 0,... 1, we get
1 - 24L T
T- 1
| 00112 < xF(0") F((O) 2T
Σ
lg - VoJ(0
2n
1=0
1=
17

---

Published in Transactions on Machine Learning Research (8/2024)
T-1
$ A + 2L t=
Σ 11 -
(9)
Here, we recall that = - On the other hand,
-F(6)) > 0.
g also implics that
00) )} 1-1% 10 - 0212
2 VoJ(Or+1) - g', 1)
(0it1 (01t1- -001-00)
1/2
1 (F(tht1) - -F(0') + (VoJ((tt)) - (ot(t)), gr+ 8²)
2
(10)
Notice that
1 2 Vootott1) - - 10+t1 - 04)
VoT(ot+1) gr +
1 (8tt1 04)
||
|| VoJ - g²1
1 172 09|
| 110tt--01
77
Then by substituting the above equality into 10 and rearranging terms, we see that
V ( g6 + 17
(8t+1 84)
(oT() - -//12= + 1 ||0 119----091" 00112 1 - 17
- 1
172
172
2 _ ( - -F(O') + - (Vo - VOJ (00)) 0e+1 - -0')
2 VoJ |lll? +2 22/ - voJ(0))12 + L +110412 0912
11
2 (5(0+))) - F(OO) 2 (V VoJ(0') 10+01 -011 0'1
2
< VoJ g//l²== + 22L2+ + 3L ||0ct1 | 2 (F(o+))) -
77
"
where the second incquality is due to the Cauchy-Schwarz incquality and fact that [[++ g' 0²| 2 VoJ(0') - -' + VoJ(o'+1)- 2
and the third inequality is implied by Lemma 4.1
Summing the above inequality across t = 0.......2 T 1, we get
1
(0ct1 -00] ||
VOJ - -9¹ + 11
2
VoJ - -/112= 2222 + 31.
31.)
Σ
T-1
10c+1
2 (F(0²) - -F((O))
17
"
T-1
2 T-1
< 22)
VoJ(00) - 0²1² +
Σ
| -
00112
+
24
(11)
where the last incquality is obtained from the fact that L consequence of the choice of the learning rale.
27
Consequently, we have that
( Ey dist (0, (oT + (((()))))))))) )
18

---

Published in Transactions on Machine Learning Research (8/2024)
Br dist + a
VoJ(O!t1) gg' + (0 - 0²) |
ET
-00+11-0))
7
2
Σ
Er
2 Σ Er -
-011²]=
24
7
n12T
T/T
4
1
Σ
T-1
Br
||st
- voJ(0)11()
2 Σ
2 T-1
ET || [io - r/19]]
24 T/T
1/T(1 - 24)L)
2L
T
1=0
T
= 2 nI(1 - 2mL)
2
Σ
ET
||] - 2|1"
+ -
+
4
T
711 - 27
t=0
where the first inequality is because of the second inequality is due to derived from 9 Thus, the proof is completed.
11 and the third inequality is
A.3 Proof of Lemma 4.4
Proof of Lemma 4-4 We first estimate Exwrr ( (x)
VoRa as follows
E Egent
Vo (x( + (o s 2E
(x))) + 2E [1VoRo(=)11]
2 +20g
Then, by the fact that E [[x =[X])² < E x for all random variable X, we have
E Exego
VeJ(0)]1 s ExNTO [I(2(() log VoRo
$ 2 +20g
which completes the proof.
A.4 Proof of Theorem 4.5
Proof of Theorem 4.5 From Theorem
4.3
in order to ensure that 0T is a e-stationary point, we can require
2
2
ET
||g*
-oJ
S 2c, =t= O...,
(12)
nL(1 2nL)
A
2
(13)
1 21L)
It is easy to verify that g¹ is unbiased estimator of VoJ(Ht). Then, Lemma 4.4 implies that
Er [lle* VoJ
N
4 As consequence, if one chooses N = + 4 + 7 (1 then 12 holds.
On the other hand, 13 holds if one sets T A m
Moreover, that the sample complexity be computed TN 40. Therefore, the proof is completed.
19

---

Published in Transactions on Machine Learning Research (8/2024)
A.5
Proof of Lemma 5.3
Proof of Lemma 5.3 Finst, recall that
TT(x))
E Bg
1.
Tee (a:)
Then, by the definitions of g and Iwe, we can verify that
EENTA [1 6¹) (w, 8, 8
< 2R B [10(0,00) g(x, 1)] 21 [1,(2, 0) 1000)-9wh) 00)0)
=2 2 / (2) log To - (r) log To (x) + VoRer - (oRa(x)]1 To (x)dr
2 / Ro((z) (ellogo(x)-
(x) n
Ta(x)
V log mo)) + VoRo(x)
V (o)
Te (z)dr
(x)
6 / [R To - Volog no (x)) (x)dr +6 / [[(Ro - (Ro()((z)) Vo log log (x)) Ter (x)da
/
+6 / (VoRo (o) To (x))x
(Ro(o) (1
T (x+)
Vo log
Tor (x)dr
Te (x)
+4 / VoRO(()) 1
mo(x))
|
T (x)
(x)
(
(T)( -1)
< 0f + 60202 + 660% 110 10-681 8'112 + (2U? + +4c%) Bowny
(6U%C) + +cg02/ + 60%) 110 0'112 + C1 + +40g) (/
(TT(()))² dur -1) 1).
xo (xt)
(ar) dr. Taking the derivative of f with respect to 0, we get We next consider the function f(0) = ʃ (mo()))²
Vol(o)= /
2 VoTo da. x (x)
Moreover, since
V (x()) (TT( V (
(am Vo log ne (x) (o))
(T())
we see that the Hessian of ff with respect to 0 can be computed as
Vār(0)= / To (I)
(VoTa() + (o(=)\ de
/ Tor (TT (2 log To (2) (2) + V log Te (x)) da.
Notice that f(0") = 1 and Vof(O') = 0. Therefore, by the Mcan Value Theorem, we get
f(0) = 1+ 1 -2)0000-00).0--0
where Ō is a point between 0 and 0'. Now, from the expression of the Hessian matrix, we see that for any R",
v3f(0)11 < / 2(TT(())) (x) |/2 log Na ( (x) log (x) T + v log dx
20

---

Published in Transactions on Machine Learning Research (8/2024)
$ 22(202 + +Cn) / (ma(x))) (T)( dx
To Toor (z) -1)
)
2(20g + +Ca)
11 1+EENNTO
S 22(202 + C+)(C++1)
As consequence, we have
Eanao
9m -
& (OU2OR + 6C20 + 60%) |0 - 8112 + (102 + (10 (ʃ (To(2))) [T((() dx -1 1
& (OURCR + O + σ, + (AU2C2 + +00) (20g) + CNC +1)) 110 - 8¹11.
which completes the proof.
0
A.6 Proof of Lemma 5.4
Proof of Lemmal 5.4 By the definition of the stochastic gradient estimator given in Algorithm 2 can see
that for t 2 O,
E++1 110
VoJ a
1
g 14 ,(t - VOLT
plE+11
N1
27
N₂
+ (1 -
(1-1) p)1111
1
(9( gl+1)
Iw (z 0r, ((+))) + + - (
N2
N₁
= pEE+1
g(xtt13,80 g(+1) VOJ(OLH))
N1
N2
+ (1 - Ex)
(g( ,0tt1
- Im (x t. ,0,000+01 0(11) + VoJ(0") - VoJ(O + VoJ
2₂
1
< plE4+1
g(a 0t+11) VoJ(OCt))
N
1
+ (1 - E)41
(0(x0-15,00 ,c+1)
Iw (x 00, ((+))) + o VoJ(0))
N₂
?
+ (1 (1-21) -T)
||00* VoJ(O)))
(1
N₂
E E
(ec(0tt1,,0011) Ii (1ttl3,00 (+
N,
N₂
< 2o²
N₁ +11 V -
(1-p)C
||0t+1 - -
N₂
where in the first inequality, we the facts that E (X -X--(XX) S E [X2] for all random variable X
and g¹ is unbiased estimator for VoJ(O') for all & 2 0, in the second inequality, rely on the fact that
21

---

Published in Transactions on Machine Learning Research (8/2024)
{x'=la} is independent, and the last inequality is due Lemma 5.3
By summing the above relation across
= 0, o,.... T 2, we see that
Σ RS |Il"--
-o'-vo -VoT(O))
po² (T -1
+ (1 p) Σ
T-2
Be+1 - + (1 p)C
T-2
Σ Er
| | 091""]
N1
N2
which implies that
T-1 Σ Er (800-VJ((89)))
po + 0²
(1- P)C T-1
+
Σ
Er
| - 0011"]] -0'1)-
(14)
PN1
2=
t=
Recall from 9 that
2
Σ 1 10
|1gt - VoJ(O))
2nL
L(1 L)
which together with
14 implics that
(1-
(1-p)
Σ 1=U
Br |110* VoJ -
p + 02
2n(1 - p)CA
(1
PN
pN2(1 )
Thus, the proof is completed.
A.7 Proof Theorem 5.5
Proof Theorem 5.5 Since p
N₂
10 and
Ni+
PN2L
N
11
2(1 C)C + 2p
2N,C + 22
can readily check that
1
1 1 (1-)) 1
E
0, 2L
(15)
N2L 2nL) 2
Then, we can see that
Er dist
<
2
2
1
T-1
Σ
Er
||9" - -Vo
+
1
2A
4A
nL(1 2nL)
T
T 17
11 (1-2210 2nL
1=0
2
(1 (1-p)Cn
p 0²
21y(1 - pPCA
<
2 + 11L(1 - -2nL)
+
T
PN2L(1 - 2nL)
NN
pN2 - 2nL)
22 + '1( - 21/1.)
4A
+ T
4
(1
1
To2
(N + N2)0² Nr
21
2A
2
< T L L)
+
+ n/ 2y
N₂
N
2mL)
T
where A F(80) is constant, the first inequality is due to Theorem is derived from Lemma 5.4 and the third inequality is implied by 115
4.3 the second inequality
22

---

Published in Transactions on Machine Learning Research (8/2024)
Then, in order to have Er dist (o. 10.-Vo12 -o- + (0.-V)((0)+00(00))) set N2 = VN1.
S for a given tolerance e 0, we can simply
N
L
" - 2N1C + 22
2C + 212
and require that
1+ nLL11 - 2nL) )
0²
2
N1 S
3
4
1
(Ni + N2)02
2
1+
T
nL(11 2nL)
N1N2
24
T (1+
An,
2
6²
+
nL(11 2nL)
N2 (1 2mL)
17(1 2nL)
Therefore, suffices to set N1 = O), N2 = /N = O and T = 2) (We ignore deriving the
concrete expressions of T, N1 and N2, terms of and other constants, but only give the big-O notation here for simplicity.)
Finally, verify that the sample complexity can be bounded
Ni + T (pNi (1 p) = N1 +T N Ni + N₂
N1 + 2TN = 3)
Therefore, the proof is completed.
23


Reviews:
[{"review_id": "YNLuHF50id", "reviewer": "Reviewer_LAnA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n* The problem setup introduced in this paper seems to be novel and not discussed in prior literature\n* The presentation of the problem, assumptions on the problem setup, method to solve the problem and related theoretical results are presented clearly and the paper is fairly easy to follow\n\nWeaknesses\n\n* Since the problem setup is novel (which seems to be one of the main contributions of the paper) and not discussed in prior literature, the problem setup should be well motivated with several application setups and/or examples, which seems to be lacking.\n* Related to previous point, it is unclear when one would need to optimize the policy and the reward function which shares the same parameter. In general, it seems like this kind of setup might lead to learning a meaningless reward function which the policy learn to maximize.\n* The assumption of the boundedness of the norm of the gradient and the Hessian of the reward function seems to need more discussion and justification, since this kind of assumption is new and seems to be related to the novel problem setup introduced in this paper.\nThe example provided in the paper as a illustration of the setup is a special case of the proposed problem setup, which is not illustrative of the novel setup and widely discussed in reinforcement learning (RL) literature.\n* There are some strong assumptions used for analyzing the variance reduced method, and the paper lacks practical application of the proposed method which might bolster the validity of the novel setup introduced in the paper. The authors acknowledge these limitations in the paper.\n\nMinor Weaknesses:\n\n* $\\theta^* =$ might be incorrect in Equation (2) since the solution to problem in Equation (2) might not be unique.\n* The subsequent simplifications of the original problem used in Example 3.3 use $\\min$ operator, which is inconsistent with the original problem formulation.\n* The definition of sub gradient given after Equation (3) seems to be the definition of a subdifferential.\n* The function $\\text{dist}(\\cdot, \\cdot)$ used in Definition 3.4 is not properly introduced/defined.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors introduce formally a general problem setup for reward optimization. Authors introduce the problem setup, establish the smoothness for part of the objective under some assumptions, propose to solve the problem using existing proximal gradient descent methods and provide a convergence guarantee for the algorithm, with a sample complexity of $O(\\epsilon^{-4})$ to attain a $\\epsilon-$stationary point. The paper also provide a  stochastic variance reduced version by applying existing variance reduction method PAGE, which has an improved sample complexity of $O(\\epsilon^{-3})$.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As mentioned in the Weaknesses section, it seems important to better motivate the general problem setup introduced in the paper, with motivating practical applications and/or some illustrative example that demonstrate the general problem setup introduced in this paper, which seems to be a critical requirement for the paper. Please refer to Minor Weaknesses for minor changes needed in the paper.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "71Ghf6pSmf", "reviewer": "Reviewer_fETn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "S:\n\n- The paper is well-written and includes relevant related works after all assumptions and results.\n\nW:\n\nAs this paper mentions, stochastic variance-reduced gradient approaches exists in optimization by Li et al. (2021b) and MDPs by Gargiani et al. (2022). The results in Section 5 mostly follow the analyses by Gargiani et al. (2022). The additional challenges in this work are the analyses adapted with the parameterized reward functions ($R_\\theta$) and regularization function $\\mathcal{G}_\\theta$. These challenges are mostly overcome by the uniform boundedness assumptions on rewards (and its twice-differentiable functions) and log-policies. So, I'd be more curious about practical implications of this result. That is, showcasing failure of PAGE-PG (Gargiani et al. 2022) in certain toy-problems where adapting to parameterized reward functions and the regularized optimization becomes a necessity.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the regularized expected reward optimization problem that subsumes many RL settings (MDPs, bandits, etc). They analyze the standard stochastic proximal gradient approach to get $\\epsilon^{-4}$ sample complexity bound. They make further assumptions to show an improved sample complexity bound $\\epsilon^{-3}$ for the stochastic variance-reduced proximal gradient approach.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "na", "broader_impact_concerns": "na", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ih1QPBvoaa", "reviewer": "Reviewer_HEbZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- The setting it considers is more general compared to some other related work, as it considers general convex regularizers, general policy parameterizations, and the non-oblivious setting.\n\n- The sample complexity of $O(\\epsilon^{-3})$ analyzed in this paper matches the sample complexity in existing competitive works.\n\n- The proof is well-written and easy to follow.\n\nMajor Weaknesses\n\n- The results derived via Algorithm 2 rely on a strong assumption on the importance weight (Assumption 5.1). However, there are papers that achieve the same sample complexity without this assumption (e.g., Fatkhullin et al. 2023, Shen et al. 2019, Yuan et al. 2022). Moreover, although the setting considered in this paper is general, it would be better to compare and discuss the techniques, assumptions, and results in this paper under specific instantiated settings with other works.\n\n- The novelty of the proof techniques is limited, as they are mostly adapted from classical results. For example, the proofs of Lemma 4.1 and Lemma 4.4 are based on the boundedness assumptions; the proof of Theorem 4.4 is based on a standard analysis of the stochastic proximal gradient method; and the proof of Lemma 5.3 is based on the proof of Lemma 4 in Li et al. 2021b. However, I am aware that the TMLR community does not consider novelty a necessary criterion for acceptance.\n\nMinor Weaknesses\n\n- In addition to analyzing global convergence with additional mild assumptions as mentioned in Conclusions, I think it would also be beneficial to analyze the sample complexity for convergence to second-order stationary points, which avoids getting stuck at saddle points.\n\n- The choices of notations $\\pi_{\\theta}$ (probability density of a single trajectory) and $x$ (a trajectory) are a bit misleading. \n\n- It would be better to present a derivation of $\\nabla_{\\theta} \\mathcal{J}(\\theta)$ at the bottom of page 4.\n\n- It would be better if numerical experiments were provided.\n\n- There are assumptions on the Lipschitzness and smoothness of both the reward function(Assumption 3.1) and the score function (Assumption 3.2), whereas most other works with general policy parameterization have at most one of these assumptions for one Theorem.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the sample complexity of stochastic gradient methods. In particular, it considers the regularized expected reward optimization problem with general policy parameterization. The paper first analyzes the stochastic proximal gradient method and provides a sample complexity of $O(\\epsilon^{-4})$. Then it proposes an efficient stochastic variance-reduced proximal gradient method utilizing an importance sampling-based Probabilistic Gradient Estimator (PAGE), which improves the sample complexity to $O(\\epsilon^{-3})$.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the issues I discussed above.", "broader_impact_concerns": "There are no broader impact concerns for this theoretical work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: We have one Accept and two Leaning Accepts among reviewers. I also read the paper before closely reading their reviews, and I agree with them that this is a reasonably good paper: it has some non-trivial contributions, it is generally well-written, and according to reviewers, sufficient evidence is provided for its claims (I have not verified the proofs myself).

A major novelty of this work is that it considers a new class of problems in which both the policy and the reward function are parameterized. To solve this problem, a policy gradient-based approach, specifically the stochastic proximal gradient algorithm, is proposed to solve the regularized objective. The convergence rate to the stationary point is established. Furthermore, the paper suggests the use of a variance-reduction algorithm, PAGE. This leads to an improved convergence rate, under extra assumptions.

It is notable that these types of convergence analysis for policy gradient-based methods have become relatively common in the past few years, but since this is a new problem setup, I would consider it a sufficiently novel and interesting contribution, even if some of the proof techniques have been used in the past.

The authors have revised the paper to address several of the reviewers comments. I believe they have done a reasonable job. 

I recommend **acceptance with minor revisions**. Before accepting this paper, I would like to ask the authors to do a few other minor revisions in order to improve the readability of this work:

- Please clarify the use of x a bit further. Specifically, is $x$ the same as $\tau$ in Example 3.3?

- Assumption 5.1 is strong, as Remark 5.2 already explains. What is not clear is how strong it is. It would be very helpful if the authors provide an analysis of the size of constant $C_w$ in that assumption. This can be done for a simple concrete example, if a general characterization is difficult.
For MDPs, this constant seems to depend on the ratio of probability of actions according to each policy along the whole trajectory. I can see that if there is no restriction over $\theta$ and $\theta’$, that is, they can be far from each other, this ratio can be very large, but if they happen to be in the same neighbourhood, they may be bounded, perhaps under some smoothness of the policy as a function of parameter theta (this might already be implied by Assumption 3.2). A discussion and a worked out example should not be very difficult but goes a long way.

- Even though PAGE is not introduced in this work, its use is one of the contributions of this paper. Currently there is not much intuition of why PAGE helps. This makes the paper a bit mysterious to a reader who has not read the original PAGE paper. I’d ask the authors to provide some intuition behind that algorithm, so that this paper would be more self-contained.
Decision: Accept (poster)