Variance Reduced Smoothed Functional REINFORCE Policy Gradient Algorithms
Authors: Shalabh Bhatnagar
Deepak H R
Venue: Accepted by TMLR ()

Abstract: We revisit the REINFORCE policy gradient algorithm from the literature that works with reward (or cost) returns obtained over episodes or trajectories. We propose a major enhancement to the basic algorithm where we estimate the policy gradient using a smoothed
functional (random perturbation) gradient estimator obtained from direct function measurements. To handle the issue of high variance that is typical of REINFORCE, we propose two independent enhancements to the basic scheme: (i) use the sign of the increment instead
of the original (full) increment that results in smoother convergence and (ii) use clipped gradient estimates as proposed in the Proximal Policy Optimization (PPO) based scheme. We prove the asymptotic convergence of all algorithms and show the results of several experiments on various MuJoCo locomotion tasks wherein we compare the performance of our algorithms with the recently proposed ARS algorithms in the literature as well as other well known algorithms namely A2C, PPO and TRPO. Our algorithms are seen to be competitive
against all algorithms and in fact show the best results on a majority of experiments.

Published in Transactions on Machine Learning Research (08/2025)
Variance Reduced Smoothed Functional REINFORCE Policy Gradient Algorithms
Shalabh Bhatnagar
shalobh www.c.c.iicccc.ci
Department of Computer Science and Automation, Indian Institute of Science, Bengaburu 560012, India
Deepak Ramachandra
deepakh Wiisc. ac.
Department of Computer Science and Automation, Indian Institute of Science, Bengaburu 560012, India
Reviewed on OpenReview: https: /// openreview. net/ forum? id= yagagSJ66
Abstract
We revisit the REINFORCE policy gradient algorithm from the literalure that works with reward (or cost) returns obtained over episodes or trajectories. We propose a major en- hancement to the basic algorithm where we estimate the policy gradient using a smoothed functional (random perturbation) gradient estimator obtained from direct function measure- ments. To handle the issue of high variance that is typical of REINFORCE, we propose two independent euhancements to the basic scheme: (i) use the sign of the increment instead of the original (full) increment that results in smoother convergence and (ii) use clipped gradient estimates as proposed in the Proximal Policy Optimization (PPO) based scheme. We prove the asymptotic convergence of all algorithms and show the results of several ex- periments on various MuJoCo locomotion tasks wherein we compare the performance of our algorithms with the recently proposed ARS algorithms in the literature as well as other well known algorithms namely A2C, PPO and TRPO. Our algorithms are seen be competitive against all algorithms and in fact show the best results majority of experiments.
Key Words: smoothed functional REINFORCE policy gradient algorithms, stochastic shortest path Markov decision processes, signed updates, objective function clipping.
1 Introduction
Policy gradient methods (Sutton et al., 1999; Sutton & Barto, 2018) are popular class of approaches in re- inforcement learning (Bertsekas, 2019; Meyn, 2022). Parameter-dependeutt randomized policies are normally used in these approaches and one updates the policy parameter along a gradient search direction. The policy gradient theorem (Sutton et al., 1999; Marbach & Tsitsiklis, 2001; Cao, 2007), which is a fundamental result in these approaches, relics on an interchange of the gradient and expectation operators and in such cases turns out be the expectation of the gradient of noisy performance functions, much like the perturbation analysis- based methods studied previously for simulation optimization (Ho & Cao, 1991; Chong & Ramadge, 1993).
The REINFORCE algorithm (Williams, 1992; Sutton & Barto, 2018) is a noisy gradient scheme for which the updates of the policy parameter are obtained once after the full return on an episode has been found. Actor-critic algorithms (Sutton & Barto, 2018; Konda & Borkar, 1999; Konda Tsitsiklis, 2003; Bhatnagar et al., 2009; 2007) have been presented in the literature as alternatives to the REINFORCE algorithm they perform incremental parameter updates every instant.

---

Published in Transactions on Machine Learning Research (08/2025)
We revisit the REINFORCE algorithm in this paper and present modified zeroth order algorithms as alter- natives to it. While REINFORCE type algorithms are trajectory-based methods, they are single timescale algorithrs unlike actor-critic schemes that involve two timescales. REINFORCE is a first-order gradient search algorithm that is based on direct gradient measurements. Finst-order gradient search algorithms in data-driven optimization work well in situations where the gradient of the expected (noisy) performance objective can be shown equal to the expectation of the gradient of the (noisy) performance function. REIN- FORCE is one such scheme but because it is trajectory-based method, suffers usually from high variance.
In many real-life situations, particularly those involving infinite state spaces, interchanging the gradient and expectation operators (mentioned above) may not be justified without additional roquirements related to the smoothness of the (noisy) performance objective as well as other restrictions on the system dynamics (Chong & Ramadge, 1994; 1993). Zeroth-ordes algorithms, on the other hand, do not suffer from this problem as the expectation of the noisy sample performance functions directly obtained from the effects of the stochastic approximation scheme and the gradient (in the limit) is then estimated from the converged expected values, thereby invalidating the need for an interchange between the gradient and expectation operators. This motivates propose an efficient zeroth-order algorithm as an alternative to REINFORCE. Our algorithms are devised for episodic tasks, also referred to as the stochastic shortest path sctting, and perform paramcter updates upon termination of episodes, that is when the goal or terminal states are reached (Cao, 2007; Marbach & Tsitsiklis, 2001). We may however mention that our gradient estimation procedure would work even for continuing task settings such as those involving the infinite horizon discounted reward criterion. A policy gradient procedure for this setting is described in Paternain et al. (2022), see Algorithms 1-2 there. The gradient estimator there involves the computation of complex matrix-valued function. Zeroth-order methods can potentially help in this procoss one would not need to compute such quantities.
Our first algorithm is based on a single function measurement or simulation at a perturbed parameter value where the perturbations are obtained using independent Gaussian random variates. The problem, however, is that it suffers from a large bias in the gradient estimator. We show analytically the reason for the large bias here. Subsequently, we also present the two-function measurement variant of this scheme which we show, in a result, has lower bias. Our algorithms rely on a diminishing sensitivity parameter sequence { that appears in the denominator of an increment term in our algorithms. This can result in high variance at least in the initial iterates. To tackle this problem, introduce the signed analogs of these algorithms where we only consider the sign of the increment terms (the ones that multiply the learning rates in the updates).
Subsequently, we also incorporate variants that use gradient clipping as with the proximal policy optimiza- tion (PPO) algorithm (Schulman et al., 2017). A similar scheme as our first (single-measuremenn) algorithm is briefly presented in Bhatnagar (2023) that, however, does not present any analysis of convergence or exper- iments. Our paper not only provides detailed analysis and experiments with the mne-meauurement scheme, but also analyzes several other related algorithms both for their convergence and empirical performance. We do not analyze, however, the finite-time convergence of our algorithms. We refer the reader to Yuan et al. (2022) for a sample complexity analysis in the discounted reward setting of REINFORCE with regular PG estimates. Gradient estimation in our algorithm is performed using the smoothed functional (SF) technique for gradient estimation (Rubinstein, 1981; Bhatnagar & Borkar, 2003; Bhatnagar, 2007; Bhatnagar et al., 2013). The basic problem in this sctting is the following: Given an objective function J R² + R such that (0)= Feg ()), where 0 Rd is the parameter to be tuned and & is the noise element, the goal is to find 0+ E Rd such that J(0)) = max (0). Since the objective function J(-) can be highly nonlinear, one often RER"
settles for a lesser goal- that of finding a local instead of a global maximum.
In Salimans et al. (2017), evolutionary strategy (ES), also sometimes referred to as basic random search (BRS) based zeroth order gradient estimation algorithms involving one and two measurement smoothed functional estimators have been proposed as alternatives to the REINFORCE algorithm. One of the measurements in the two-meesurement estimator is the running parameter making the estimalor one-sided (instead of the two-sided estimator that we use). During each run of the algorithm, in the ES or BRS procedure, a certain number (k) of gradient estimates is obtained by randomly sampling the search directions and an average over the gradient estimates is then used in the procedure. In Mania al. (2018a;b), the augmented random
2

---

Published in Transactions on Machine Learning Research (08/2025)
search (ARS) procedures are proposed as modifications to the ES scheme where the best b out of the k directions are used and the average over these samples is further divided by the standard deviation of the 26 returns. These algorithms are seen to show good results. We also implement the ARS algorithms in our work. Further, in prior work, asymptotic convergence analyses of ES or ARS had not been provided. We thus also provide the first asymptolic convergence analysis of ES/ARS algorithms.
In Malik al. (2020), smoothed functional algorithms (both one and two simulation) are applied for pol- icy optimization in the setting of lincar quadratic regulator (LQR) problem linear policies and non- asymptotic regret bounds are obtained. The cost function in this setting is seen to satisfy nice properties such as the Polyak-Lojasiiwiezz (PI) condition. Unlike Malik et al. (2020), we do not restrict ourselves to linear policies or to linear state evolution dynamics as our state process follows general nonlinear dynam- ics and our cost function can be highly nonlinear and non-convex with multiple local optima. We provide asymptotic analyses of all algorithms including ARS in this setting. Most of our analysis is based on just two assumptions, namely Assumptions and 2. In fact, we prove all the basic requirements such as the parameterized value function being differentiable with Lipschitz continuous gradient (Lemma 4). This is unlike papers on ES/ARS that make much stronger assumptions but do not show whether such assumptions are valid in the settings they consider.
Random search methods such as simultaneous perturbation stochastic approximation (SPSA) (Spall, 1992; 1997; Bhatnagar, 2005), smoothed functional (SF) (Katkovnik & Kulchitsky, 1972; Bhatnagar & Borkar, 2003; Bhatnagar, 2007) or random directions stochastic approximation (RDSA) (Kushner & Clark, 1978; Prashanth al., 2017) have the advantage that they typically require only one or two system simulations to estimate the objective function gradient regardless of the parameter dimension d. Textbook treatments of random search approaches for stochastic optimization are available in (Spall, 2005; Bhatnagar et al., 2013; Prashanth & Bhatnagar, 2025).
In addition to proving the asymptotic convergence, we empirically study the performance of our algorithms along with their clipped and signed variants with the ARS algorithms on four different MuJoCo locomotion tasks, namely, Swimmer, Hopper, HallCheetah and Walker2d, respectively. Tt has been observed in the past (Mania et al., 2018a;b) that ARS algorithms show significantly better performance on most tasks than other model-free algorithms such as PPO, TRPO and A2C. We thus focus mainly on empirical comparisons of our algorithms with ARS and we also show such comparisons with these other algorithms on some of the tasks.
1.1 Our Contributions
1. We present zeroth order versions of the REINFORCE policy gradient algorithm that are based smoothed functional gradient estimators (SFR) and require one or two function measurements at each update. While SF gradient estimates have been proposed in the past, they have only so far been studied in the context of the ARS/ES algorithms.
2. Our basic scheme is similar to ARS except that ARS requires multiple simulations for a given parameter update as opposed to just one or two simulations for the algorithms that we present.
3. For improved accuracy and lower variance, we propose variants of our algorithm with clipped gradient estimates as well as signed updates.
4. We prove the asymptotic convergence of all algorithms including ARS as well as those with signed updates and clipped gradient estimators. Most of our analysis is based on just two assumptions, namely Assumptions 1 and 2. In fact, we prove all the basic requirements such the parameterized value function being differentiable with a Lipschitz continuous gradient (Lemma 4). This is unlike papers on ES/ARS that make much stronger assumptions but do not show whether such assumptions are valid in the settings they consider.
5.
We show empirical results on four different MuJoCo environments as well as on a gridworld environ- ment with varying grid sizes. Our experiments demonstrate that our algorithms with the clipped and signed updates perform better than ARS on more than half of the settings. Our algorithm SFR-2 shows uniformly better performance than A2C, PPO and TRPO on all the gridworld set- tings. On the MuJoCo environments, SFR-2 shows the best performance on two of the four MuJoCo
3

---

Published in Transactions on Machine Learning Research (08/2025)
environments (when ARS is also considered) and it is better than A2C, TRPO and PPO on three of these environments.
1.2 Paper Organization
The rest of the paper is organized as follows. Section 2 presents the Markov decision process (MDP) framework for the episodic setting and recalls the policy gradient theorem from Sutton & Barlo (2018). Section presents the basic one-simulation SFR algorithm (SFR-1). Section 4 then presents the two- simulation SFR algorithm (SFR-2) as well as its signed and clipped counterparts. We also prove a couple of Jemmas here that show that SFR-2 has better bias guarantees than SFR-1 and the signed and clipped variants have better variance guarantees than the original algorithm. We also present here the two evolutionary strategy (ES) algorithms from the literature and briefly describe the ARS algorithms. Section 5 provides the main results in the convergence analysis of all algorithms. Proofs of these results are given in Appendix A. Section provides detailed numerical results and Section 7 provides the concluding remarks. Appendix A has all the proofs of the various convergence results, Appendix B contains details of the ARS algorithm and qualitative comparisons with SFR, and Appendix C contains details of the setting parameters for the various numerical experiments.
2 The MDP Framework
By a Markov decision process (MDP), we mean controlled stochastic process {X,} whose evolution is governed by an associated control-valued sequence {Zn}- It is assumed that X,,, n 2 0 takes values in a set S called the state-space. Let A(s) be the set of feasible actions in stale 8 E S and A _ UsE)((s) denote the set of all actions. When the state say s and a feasible action a is chosen, the next state seen is s' with a probability p(s'|s, a) A P(Xm+1 = X, = 8, 7n a), Vn. Such process satisfies the controlled Markov property, i..,, P(X,+1 s' Xn, Zn...., Xo, Zo) = p(s' Xn, Zn.) a.s., Vn 2 0.
By admissible policy simply policy, Pk S + A, k 2 0, such that (*(8) E A(s), Vs E S. When following policy x, decision maker selects action (s)s) at instant k, when the state is A stationary policy is one for which fa = 1r _ (a time-invariant function), Vk, = 0, l..... Associated with any transition to a state s' from a state s under action is a "single-stage" cost s(s,a,8') where g S x A x + R is called the cost function. The goal of the decision maker to select actions ax: k 2 0 in response to the system states sy k 2 0, observed one at a time, so as to minimize a long-term cost objective. We assume here that the number of states and actions finite.
mean sequence of functions
{no, Pl, P2,...), with
2.1 The Episodic or Stochastic Shortest Path Setting
We consider here the episodic or the stochastic shortest path problem where decision making terminates once a goal or terminal state is reached. We let 1,..., denote the set of non-terminal or regular states and be the terminal state. Thus, S = (1,2,.... t denotes the state space for this problem (Bertsekas, 2019).
Our basic setting here is similar to Chapter of Bertsekas (2012) (see also Bertsekas (2019)), where is assumed that under any policy there is positive probability of hitting the goal state in most p steps starting from any initial (non-terminal) state, that would in turn signify that the problem would terminate in finite though random amount of time.
Under a given deterministic policy n. define
V=(s) = E. Σ Po(X Xo
(1)
where T > O is a finite random time at which the process enters the terminal state t. Here Ex[:] indicates that all actions are chosen according to policy я depending on the system state any instant. We assume that there is no action that is feasible in the state & and the process terminates once it reaches t.
4

---

Published in Transactions on Machine Learning Research (08/2025)
Let II denote the set of all admissible policies. The goal here is to find the optimal value function V*(1), E S where
(1 = min (i) V (i), i S,
fell
with x² being the optimal policy, A related goal then would be to search for the optimal policy x². turns out that in these problems, there exist stationary policies that are optimal, and it is sufficient restrict the search to the class of stationary policies.
A stationary policy æ is called proper policy (ef. pp.174 of Bertsekas (2012)) if
Pr
- max s=....P
P(X, +1 X, = π) <1
In other words, regardless of the initial state there is positive probability of termination after at most p stages when using a proper policy π and moreover P(T < oo) = 1 under such a policy. An admissible policy (and so also stationary policy) can be randomized as well. A randomized admissible policy or simply a randomized policy is the sequence vi {do, .1,...} } with each di S + P(A) being distribution A(s) for the action to be chosen in the ith stage in state s. A stationary randomized policy is one for which 0j- Φx - Φ, Vj,k 0, 1, ..... Here and in the rest of the paper, we shall assume that the policies are stationary randomized and are parameterized via certain parameter 0 C C R compact and convex set. We make the following assumption:
di(s) = (0,
Assumption 1 All slationary randomized policies dn paramelerized by 0 E C are proper.
In practice, one might be able to relax this assumption (as with the model- based analysis Bertsekas (2012))
by (a) assuming that for policies that are not proper, V=(i) = oo for at least one non-terminal state i and (b) there exists a proper policy. The optimal value function satisfies the Bellman equation: For s I.....P.
(*())= = min
A(s) ((s,a)+ + Σ pli (ills,aVV()
(3)
where a(s,a)=
(aa))=((lee Eplil, + p(1ss, a)g(s, 1) is the expected single-stage cost in non-terminal
state when a feasible action a chosen. can be shown, see Bertsekas (2012), that an optimal stationary proper policy exists.
2.2 The Policy Gradient Theorem
Policy gradient methods perform gradient search within the prescribed class of parametorized policies. Let ④o(s,a) denote the probability of selecting action E A(s) when the state E S and the policy parameter is 0 C. We assume that (o(s,a) is continuously differentiable in O. A common example here is of the parameterized Boltzmann softmax policies. Tet (s(s) 2 (oo(s,,),, E A(8)), s E and do (oo(s), E S).
We assume that trajectories of states and actions are available either as real data or from simulation. Let T-1
G = Σ 9j denote the sum of costs until termination (likely when a goal state is reached) on a trajectory
starting from instant k. Note that if all actions are chosen according to policy o, then the value and Q-value functions (under Φ) would be Vo(s) = Eg GR X = and Qs(s, a) = Eg (G X = s, 2z = a). respectively. In what follows, for ease of notation, we let Vo = Va. and Qo = Qaor respectively.
The policy gradient theorem for episodic problems has the following form, ef. Chapter 13, pp.325, of Sutton & Barto (2018):
VVo(50) = Em(s)
((s)) Σ Vo=(s,a)Qo(s.0)
(4)
#ES
(EA(s)
5

---

Published in Transactions on Machine Learning Research (08/2025)
7(8)
where p S is defined as pls) Eves nis')
where ((s) Σ
r (s|so, Φu), & E S, with p (s)so, Φ0)
k=0
being the k-step transition probability of going to state from under the policy do.
The REINFORCE algorithm (Sutton & Barto (2018); Williams (1992)) makes use of the expression in (4). In what follows, we present an alternative algorithm based on REINFORCE that incorporates one and two measurement (zeroth order) SF gradient estimators. Since our algorithm caters to episodic tasks, it performs updates whenever certain prescribed recurrent state is visited, see Cao (2007); Marbach & Tistt siklis (2001). We refer to ono-simulation (resp. two-simulation) algorithm the (SFR-1) (resp. TWw-ST-RFINFORCE. (SFR-2)) algorithm.
3 The One-Simulation SF REINFORCE (SFR-1) Algorithm
We assume that data on the ath trajectory is represented in the form of the tuples (sh. of 9 & 0, b.l....,7y, Tn -1 with T, being the termination instant on the nth trajectory, instant j in the nth trajectory. Further, ag and gk are the action chosen and the cost incurred, respectively, at instant & in the nth trajectory. Let I Rd + C' denote projection operator that projects any (Z) E Rd to its nearest point in C. For case of exposition, we assume that C' is d-dimensional d
1. Also, 5y the state
reclangle having the form C
I min; Gimaxx] where -xi < Ci,min < Ci,max < 00, Vi I....,d. Then
2=1
I(x) (T'((z)),... ..... (C((=))....,(((xx)))) with r, R - [Cimina (t,aax] such that r((x;;) min( (q. max, (M i == Also, let C(C) denote the space of all continuous functions from C' to Rd.
In what follows, we present a procedure that incrementally updates the parameter 0. Let 0(n) denote the parameter value obtained after the nth update of this procedure which depends on the nth episode and which is run using the policy parameter π(θ(n- 1) + 6 An( - 1)). Here, for n 2 O, where 8(n) = Rd, 5n > 0 vn with on - 0 as n + oo and ((n) (A) Aa(n))" n 2 0, where A,(n), 1, d, 2 0 are independent random variables distributed according to the N 1) distribution.
(0: (n)......
Algorithm (5) below is used to update the parameter 0 E C C Rd. Let x" denote the nthh state-action trajectory x" = { ai: aj........... - - sT,, n 2 0 where the actions .f...., a7 in x" are obtained using the policy parameter ((n) + 5, (n). The instant T denotes the termination instant in the trajectory x" and corresponds to the instant when the terminal or goal state t reached. Note that the various actions in the trajectory x" are chosen according to the policy +o. The initial state is assumed to be
T-1
sampled from a given initial distribution = (v(i), E S) over states. Let G" = = gh denote the sum of
k=0
costs until termination on the trajectory X" with of = gi ob (+1) The update rule that we consider here is the following: For n 2 0, I.....d,
0,(n + 1) =r, (D((n) - a(n) (Ar()) G") 1):
5, )
(5)
aan)) (((n))
2
Assumption 2 The step-size sequence {a(n) satisfies a(n) > 0, Vn, Ea(n) =00 00, Σ
< c0.
8,
After the (n - 1)st episode, ((n) is computed using (5). The perturbed parameter 0(m) + 8, An) is then obtained after sampling ((n) from the multivariate Gaussian distribution as explained previously and there- after a new trajectory governed by this perturbed parameter is generated with the initial state in each episode sampled according to given distribution

---

Published in Transactions on Machine Learning Research (08/2025)
4 Variants for Improved Performance
We present here variants of this algorithm that result in improved bias and/or variance performance. We show the convergence results for all the algorithms and also test their performance empirically.
4.1 ino-Simulation SF REINFORCE (SFR-2) Algorithm
The idea here is to use two system simulations instead of one in order to reduce the estimator bias. As with SFR-1, we assume that we have access to trajectories of data that are used for performing the parameter updates. Let X x and x" denole two state-action trajectories or episodes generated after the mth update of the parameter. These correspond the actions 4 2+ ..... ,....,.. aT-1 are obtained using the policy parameter 8(z) + 6nL( Likewise, the actions 0g ....,, 47 in x are obtained using the policy parameter ((,)),,)(mm) As before, a new random vector ((n) is generated after ((n) is obtained using the algorithm but the same A(n) is used in both the policy parameters used to generate the two trajectories. The initial state in both these episodes is independently
x"* {sa aij , " ..... 87 17 a+
where
T-1
sampled from the same initial distribution v (u(i), E S) over states Let G Σ
9k denote the
return or the sui of costs until termination on the trajectory x"*, with ut = g(sk g
n+ s
Similarly,
we let G
9 denote the return the sum of costs until termination on the trajectory x" with
9 g(8h m- 0k (41)) The update rule that we consider here the following: For 2 0, =1, I,....d,
0n + 1)+ (0,(m) a(n) a(n) (i(m)) (G G"h
(6)
26,
One may view (5)-(6) as zeroth order policy gradient algorithms involving one and two measurement gradient estimators where the performance gradient is estimated using direct function measurements.
Lemma 1
The gradient estimator in SFR-2 has lower estimator bias than the one in SFR-1.
Proof: We show the proof of this result in Appendix A.3.
4.2 SF REINFORCE with Signed Updates
As expected and (also) reported in the literature (Sutton & Barto (2018)), REINFORCE typically suffers from high ilerate-variance. We observe this problem even when SF-REINFORCE used. To counter the problem of high iterate-variance, we use the sign function sgn(-) in the updates defined follows: szn(x)= +1 if and sgn(z) 1 otherwisc.
4.2.1 SFR-1 with Signed Updates
The update rule is exactly the same as (5) except that only the sign of the increment is used in the update:
Vi = 1, I,..,dd
(( =1; (0:(0)-a(m))) a(n)sgn (A.(m) G" (-))) )))
(7)
4.2.2 SFR-2 with Signed Updates
As with the SFR-1 case, the update rule here is the same as (6) excopt that the update rule involves the sign of the update increment. Thus, we have, Vi = I,...,d,
(1n+1)=T,, -0.(0, - a(n)sgg (A(m)) (G++ (Gtht)(aat G
(8)
28,,

---

Published in Transactions on Machine Learning Research (08/2025)
4.3 ino-Simulation SF REINFORCE with Clipped Updates
We present here updates obtained after using norm-wise (Zhang et al., 2020) or component-wise (Pascanu et al., 2013) clipping on the gradients. Norm clip fm : Rd + R of a vector in R is defined as the projection of x onto the ball of radius m, centered at the origin, i.c., fm( = min(m, || ||=|| Similarly, component-clip fe: Rd Rd of vector x Rd is defined as the projection of x onto the box contered at origin of side 2c. That is, for x (..,,..,;. Ta), we let fe(x) (max (mmax(mnn(z))) c)2 -c),.., max (mi, c), -c))
Then, for f {fe: fmi, the updates will be of the form
0. -r; ((())))a())( a a(n)f ( (,(m))
(Gr+ G (catt
(9)
28n
We have the following basic result on variance of the signed well as clipped updates.
Lemma 2
(i) Let Y sgn(X) be random variable that is the sign of another random variable X. Then Var(Y) < regardless of Var(X).
(i)) Let U be random vector in Rd, and V f(U) E Rd, E {fer fmJ. then
Tr(CovV) = ElIV - EUI & EI EUI| = Tr(CovU).
Proof:
The proof of this result is given in Appendix A.4.
Remark 1
(i) It follows from Lemma 2(1) that Var (gnn (A) G" 8n 1, vO, for Signed SFR-2. Notice that the estimators without the sign function, namely SFR-1 and SFR-2, are expected to have higher variance as G",, G and G are the returns or sum of rewards on the trajectories that are then divided by a small quantily on- Clearby, wnlike Signed SFR-1 and Signed SFR-2, one cannol provide uniform bound the variance of the estimators in SPR-1 and SFR-2 and their variance is expected to be much higher than the signed versions. This is also validated through experiments.
S 1, 40, for Signed SFR-1 and
similarly, Var (sgn (Ai(n) (G"
(6"h)""T))) -G" )))
28..
(w) It. follows from Lemma 2(ii) that the total variance of the gradient, must decrease after projection in SF Reinforce with Clipped Updates. This is because
(G (m" S TrCov (A((M) (G++ ((mht-""))
TrCovf Ai(n)
28n
20n
4.4 Evolutionary Strategies (ES) Algorithms
We recall the evolutionary strategies (ES) algorithms, see (Flaxman et al., 2005; Salimans et al., 2017; Mania et al., 2018a). There are two versions of this update rule that are popular in the literature. These are based on one and two simulation SF. We refer to these as ES-v1 and ES-v2, respectively, depending on whether the gradient estimator used SFR-1 or SFR-2. Let A (n), m = I,..., A be independent random vectors (n) (n), (n)........ ( (n))" with the (n"(),, I,...,d, d, m 1....,k, k, 2 0 being ii.d random variables with each having the distribution N(0,1). 1).
4.4.1 ES-v1
Let = m = l,...,,k denote & state-action trajectories run with parameters 0(n) +6,)+8,444 respectively, and Gm.m denote the return the mth trajectory starting from time 0. Here, k: 2 1 is a given fixed integer. The update rule then is follows: For i = I,...,d,
m 10=1,... 1,...,k ('n),,, +
0,(n + 1)=11)11 = r, (0.()) a(n) kōn
Σ AT (m))mmm)))
(10)
m=1
This algorithm requires function measurements for one update. The value of is chosen by the user. Note k corresponds to SFR-1 in this case.
8

---

Published in Transactions on Machine Learning Research (08/2025)
4.4.2 ES-v2
Let x and x x m = ........ k denote 2k state-action trajectories run with parameters {(n) + 5 and f(n)- - 5n (n), m = 1,....,k hi respectively. Let Gm.m+ and Gm. denote the returns obtained on xnmut and x".",, respectively, starting from time O. The update rule here is the following; For i I,..., d,
A0 (n)
1) TT; (.(1) a(n)
(0(())a(()) 2kdn Σ (n) (G (%-m))
(11)
As before, k is priori chosen. The algorithm requires 2k function measurements for any given parameter update, and for = 1, we recover the SFR-2 update. We present an asymptotic convergence analysis of ES-vl and ES-v2.
Remark 2 The ARS algorithms of Mania et al. (2018a;b) that we implement, make use of best b out of k directions over which the above sample averuges are taken, see Appendir B for details of ARS. We show the asymptotic analysis of the ES variants. The same for the ARS voriants is not shown as it follows along the same lines as the ES algorithms with the average laken over (best directions) instead of all l directions.
5 Convergence Analysis
We present here the main convergence results for all the algorithms considered. The detailed proofs of all of these results are provided in Appendix A. The convergence analysis follows the ordinary differential equation (ODE) method. The itcrates in all the algorithms are seen to be stable, i.c., uniformly bounded almost surely, because of the projection. The sequence of steps below are described for SFR-1 but similar steps are followed for the other algorithms as well.
We first show that the noisy increment term in each update rule can be written as the sum of a performance function (that is an expectation over the noisy sample function) and a zero-mean noise term that we show forms a martingale difference sequence over varions iterations, see for instance, (12) and Lemma 3. We then show that the martingale sequence obtained by summing over the products of the martingale differences and the corresponding learning rates over recursions is almost surely convergent, for instance, see Lemma 6. We also show important result namely that the parameter-dependent value function Vo is differentiable abd its gradient is Lipschitz continuous satisfying a lincar growth bound, see for instance, Lemma 4. The remainder of the proof then shows that the algorithm corresponds to a noisy Euler discretization of the associated ODE and so tracks the set of internally chain recurrent points of the ODE (see for instance, Theorem 1). We prove the asymptotic convergence of SFR-1 and SFR-2 under just two assumptions, namely Assumptions 1 and 2. In fact, we prove all the basic requirements such as the parameterized value function being differentiable with a Lipschitz continuous gradient (Lemma 4). This is unlike papers on FS/ ES/ARS (Malik et al., 2020) that make much stronger assumptions but do not prove whether these assumptions are valid in the settings that they consider.
Similar steps are followed for SFR-2 except that we also show that the bias in the gradient estimator for SFR-2 is smaller than the corresponding bias in SFR-1. This results in overall better accuracy of the procedure. In Section 5.3, we prove the convergence of Signed SFR-2. Our first observation towards proving convergence of such a scheme is that it can be written as a difference between two indicator functions whose expectation would be the probability of the mentioned event. We again show that the scheme tracks the stable fixed points of another associated ODE but which (the stable fixed points) are the same as those of the earlier ODE. We also show here that the variance of the iterates in this scheme is lower than in the previous recursion. Indeed the signed version of SFR type algorithms has not been previously studied.
Finally, for proving the convergence of the ES algorithms, we first define a suitable mean squared difference function whose gradient evaluated to zero results in the form of the corresponding ES gradient estimator that is a sample average over i or 2k different function measurements depending on whether the algorithm used is ES-v1 or ES-v2. Suitable Taylor's expansions and the relevant properties on the perturbations then show that the said estimators indeed approximate the gradient in the expectation. Suitable martingale difference
9

---

Published in Transactions on Machine Learning Research (08/2025)
sequences then derived. The rest of the proof then follows using similar set of arguments for the other algorithms.
5.1 Convergence of SFR-1
The detailed proofs of the various results here are given in Appendix A.1.
We begin by rewriting the recursion (5) as follows:
G" Fn A 0n(n + 1) rT (.(n)) - (((m))((nFFF)) (((n)
+ Mitt):
(12)
on
where M - An E (m) n 2 0, with Fr - (00(m), m S n, A(m), x", m < n),n 2 1,
being sequence of incrcasing sigma fields with Fo (0(0)) Let M, - (M, M 2 0.
Lemma 3 (M,, Fa), 0 is martingale difference sequence.
Proposition 1 We have
G (n)
E
Fn
Σ v(s) (o))))))) 0(8n) a.s.
8n
In the light of Proposition 1, we can rewrite (5) follows:
8(n - 1) = r(((m) - a(n) Σ v(s) + Ma+1 + B(n))).
(13)
with 3e(n)= = E (n) Gn tion 1, it then follows that ((n) = o(6n).
where B(n) =
F - -.
From Proposi-
Lemma 4 The function (s) is Lipschilz continuuus in 0. Further, 3 constand K such that
(s) Is (1(++ 0| II).
Lemma 5 The sequence (Mn, Fn), n 2 0 satisfies M |Fl S L for some constant i > 0.
52
Define now a sequence Zn n 2 0 according to Z,
Σ
((m))MMmtt Mm+1, n 2 1, with Zo =
m
Lemma 6 Fn), 2 is an almost surely convergent martingale sequence.
Consider now the following ODE:
((t) -i- Σ v(s)VVo(ss).
(14)
where :CC(C) - C(R²) is defined according to
[(x + np((x) - x
f(v(x)) = lim 7-
(15)
1
Let H 2 (0 -(1 = 0} denote the set of all equilibria of (14). By Lemma 11.1 of Borkar (2022), the only possible w- w-limit sets that can occur as invariant sets for the ODE (14) are subsets of H. Let C H be the set of all internally chain recurrent points the ODE (14). Our main result below is based on Theorem 5.3.1 of Kushner & Clark (1978) for projected stochastic approximation algorithms. We state this theorem in Appendix A along with the assumptions needed there that we verify for our analysis.
Theorem The iterates ((1), governed by (5) converge almost surely to H.
10

---

Published in Transactions on Machine Learning Research (08/2025)
5.2 Convergence of SFR-2
The proofs of the results below are given in Appendix A.2. The analysis proceeds in similar manner here for the one-simulation SF, Let
(Vot))t(i))(()) VV(n)- )
(((((m),(()) As(n)
28(n)
Proposition
G G
E (m)
Fr
Σ (6)))))(00))))))))
[.(s) E())) ((ā)) a.s.
28n
.ES
The main result on convergence of the stochastic recursions is the following:
Theorem 2 The iterates 8(n), 2 0 governed by (7) converge almost surely to H.
5.3 Convergence of Signed SFR-2
We present here the convergence analysis of the two-simulation signed SF REINFORCE algorithm (or Signed SFR-2). The analysis of the one-simulation counterpart is analogous and hence is not provided.
Let (n) _ ((()), A(m)) V.Va(n) Further, let (((e = P(e.(n) < elO(n) = 0) be the conditional distribution of (n))) given ((n) = 0. We make the following assumptions:
(A1) P(e((n) S el0(m), m S n) (i(e)((n)) independent n.
(A2) The maps (e, 0) 1 (e and 0 V.Vo Lipschitz continuous.
(A3) For all and i = 1,....d,, d, P.(0 = 1/2.
(A4) (n) > 0, Vn, a(( = co, Σ [((n)
< 20.
8n
Consider the following ODE associated with the above recursion:
(,(t)= = T(t)) -1 2F,(- Σ ((())V1o()))0)) 12 i == =......,d
(16)
For x = (ZI...., let (a)) (((a)))) Also, let F(-VV)) -
V V
.... Fa(- Σ, vVsoVoVVss))0)) and let K (0 2F VVs) 0)) = 0) denote the set of
equilibria of (16). Further, let K K (0] -2 ((s)VVV((())0)) Σ. v(s))Vo(ss)) 0} denote the largest invariant set contained in K.
Theorem (Convergence of Signed SFR-2) {0(n)) governed as per (8) converyes oc almost surely to K.
Proof: The proof is given in Appendix A.5.
Remark 3 Suppose E K. such that is in the interior of the constraint set. Then, from Assump- tions (A2)-(A3) and Theorem 3, E. v(s) (Vo(s)VVo(s) O or VV))V( + but in the latter case, r(E, ((),(s)VVo(s spurioos fixed points that occur at the boundary of the constraint set, see Kushner & Yin (1997).
0. For on the boundary of the constraint set, either
0). The latter are
11

---

Published in Transactions on Machine Learning Research (08/2025)
5.4
Convergence of Two-Siiulation SF REINFORCE with Clipped Gradients
Theorem 4 (Convergence of SFR-2 with Clipped Gradients) {0(n)} governed as per (9) converges + almost surely to K, for each of the settings (i) f fe and (ti) f = fm.
Proof:
The proof is given in Appendix A.6.
5.5 Convergence of ES-v1
Theorem (Convergence of ES-v1) The iterates 0(n), n 2 0 governed according (10) converge al-
most surely to H o0.
Proof: The proof is given in Appendix A.7.
5.6 Convergence of ES-v2
Theorem (Convergence of ES-v2) The iterates f(n), n 2 0 governed according to (11) converge al- most surely to H as n + co.
Proof: The proof is available in Appendix A.8.
6 Numerical Results
We show the results of experiments on various settings. The first set of experiments are simple 2D gridworld enviromment with different state sizes?. Subsequently, we show the results of experiments on four different continuous control MuJoCo environments?.
6.1
Stochastic Gridworld Environment
6.1.1 Setup
tny
gri
0:33
0.21
-2.30
0:20
4..75
0.23
4.00
4.21
425
<23
0.20
417
315
4.30
4.25
473
4:20
4025
.32
8:23
1117
1.
10
300
4.20
0.15
0.12
4:05
4325
221
4/17
40
4.15
3:15
-0.0
Figure 1: Stochastic Gridworld problem
The gridworld environment consists of an L x L grid where the agent starts in the top-left corner and aims to reach the terminal state at the bottom-right. Rewards are structured to penalize the agent based on the Manhattan distance to the goal, with penaltics decreasing as the agent moves closer, as shown in Figure 1. The agent can move all four cardinal directions, but action execution stochastic: with probability
httree///gchhu...cmm/daaaaatttts Phttps://github.. com/deeaathr11999 AR///RRS-SSS lorked from modestyachts/ ARS implement SFR and compare with ARS.
12

---

Published in Transactions on Machine Learning Research (08/2025)
1 1-p=0.9, the agent moves intended, and with probability p 0.1, it moves in a perpendicular direction, introducing uncertainty in the transition dynamics. An episode terminates upon reaching the goal or after maximum number of steps to ensure bounded returns. Full details of the environment configuration, hyperparameters, and policy architectures for each algorithm are provided in Appendix C.
6.1.2 Results
002
600
407
1930
2013
506
300L
500
15/6
200
Eppiddss
(a) S - 16
(b) S - 100
(c) S |- 2500
Figure 2: Plots showing performance of iterates of algorithms on various grid sizes.
Gridsize
SFR-1
SFR-2
PPO
TRPO
A2C
REINFORCE
4x4
12.12 0.5
14.28
0.0
12.72 0.2
12.48 + 0.1
14.20 + 0.0
13.90 0.1
10x10
72.66 = 3.6
79.53
0.1
75.38 0.3
75.77 + 0.3
-9.60 + 29.7
76.90 4.9
50x50
677.55 + 233.1
824.96 + 5.6
682.97 + 12.9
741.81 + 10.7
-28.75 + 5.4
-18.79 8.4
Table 1: Total reward (higher is better) (mean + standard error) of algorithms on different grid sizes.
Gridsize / Algo
Thresholds
SFR-1
SFR-2
PPO
TRPO
A2C
REINFORCE
4x4
10
19071
164
16554
20889
16654
1863
10x10
60
30380
344
30098
33656
NaN
28837
50x50
600
42680
2177
98462
74272
NaN
NaN
Table 2: Steps taken (less is better) by average training curves of algorithms to cross reward thresholds on grids of various sizes. "NaN' means the algorithm never achieved this cumulative reward.
We evaluate the performance of six algorithms: SFR-1, SFR-2, REINFORCE, A2C, PPO, and TRPO on Gridworld environments of varying sizes. For each grid size, we report the best results obtained across different hyperparameter settings, averaging outcomes over 10 random seeds and rumning each algorithm for a fixed number of interactions (see Appendix C.1 for details). As expected, SFR-2 consistently achieves the best performance and exhibits the lowest variance across all grid sizes, as seen Table 1. From Table it also learns the optimal policy with the fewest number of steps. PPO and TRPO follow closely, demonstrating competitive performance with low variance. SFR-1, while effective, suffers from higher variance due to the bias introduced by one-sided updates, validating Lemma 1. REINFORCE and A2C perform reasonably well smaller grids (4x4 and 10x10), but struggle to scale to larger environments such as the 50x50 grid. The training curves can be seen in Figure? 2. Across 10 seeds, we plot the average reward as the thick line and shade the standard deviation around it. Overall, SFR-2 emerges as the most reliable and sample-efiicient method in this sctting, highlighting its potential for fast and stable learning in online reinforcement lcarning scenarios. For our subsequent experiments, we therefore just show performance comparisons of the various algorithms with SFR-2.
13

---

Published in Transactions on Machine Learning Research (08/2025)
6.2
MuJoCo Locomotion
6.2.1 Setup
We evaluate first the performance of SFR-2 and its signed and clipped variants on MuJoCo locomotion lasks (Todorov et al., 2012), comparing them to the ARS (Augmented Random Search) algorithm (Mania al,, 2018b). We also subsequently show comparisons with other well known algorithms, namely TRPO, PPO and A2C. Beyond convergence, we focus on how efficiently each algorithm uses environment interactions.
We choose to include ARS for two reasons. Firstly, they show that with just linear policies, one could achieve competitive results even in such complex tasks. Secondly, ARS is very similar to our SFR-2 algorithm, but with a few key differences. A detailed comparison ARS with our SFR-2 algorithm, along with the full ARS pseudo-code is provided in Appendix B. Fssentially, ARS employs multiple workers to evaluate k perturbed policies along & directions and selects the top b directions to estimate gradient, which then normalized using the standard deviation of returns. Thus, ARS consumes 2kH environment interactions per update, where H is the horizon size (considered constant for the purpose of this argument). In rast, SFR-2 simplifies this by setting k = b = 1 and normalizes the gradient using the standard deviation of perturbations, resulting in the consumption of only 2H interactions per update.
While ARS leverages a greater number of trajectories per update to reduce variance in its gradient estimates, this leads to fewer updates under a fixed interaction budget. In contrast, SFR-2 updates its policy more frequently, albeit with noisier gradients due to limited trajectory usage per update. For fair comparison, we fix the total number of environment interactions (Table 3) and evaluate performance under that con- straint. To address this trade-off in our SFR-2, we investigate the extent to which variance-control techniques such as gradient clipping and signed updates can mitigate instability and enhance performance across both a algorithms.
6.2.2 Comparison with Augmented Random Search (ARS)
We conduct experiments with various hyperparameter settings: k, b, a, and v. Initially, optimization algo- rithms are run using a grid search over all hyperparameter combinations with a single seed per combination. From this, the best-performing hyperparameter configuration is selected and further evaluated across four additional soods (five seeds in total). Table 4 reports the mcan standard deviation for these five seeds. The hyperparameter grids, along with the optimal hyperparameters for each task can be found in Appendix C.2.
Task
State Dimension
Action Dimension
Max Timesteps
Swimmer
8
2
10,000,000
Hopper
11
3
30,000,000 000,000
HallCheetah
17
6
50,000,000
Walker2d
17
6
50,000,000
Table 3: Task specifications used in our experiments. For cach environment, we report the dimensionality of the state and action spaces, along with the maximum number of timesteps used for training. State vectors lie in Rd, while each component of the action vector is bounded within the interval [-1,1]-
From Table 4, as expected, the unmodified ARS-vit and ARS-v2t algorithms outperform the unmodified SFR-2 across most tasks. However, when modifications such as Component Clip, Norm Clip, and Signed Update introduced, the variance in policy updates is reduced. This is particularly beneficial for SFR-2, which performs a larger number of updates within a fixed environment interaction budget. As result, SFR- 2 shows notable performance gains. On the Swimmer and HalfChectah tasks, it consistently outperforms both ARS variants across all three modifications. For Hopper, the modified versions of SFR-2 surpass ARS-vit but remain slightly behind ARS-v2t. In the Walker2d environment, SFR-2 with Component Clip outperforms ARS-v2t, though still trails ARS-vit. Overall, these results suggest that SFR-2 benefits more from the introduced vartanco-control techniques, making it highly competitive with ARS when the number of interactions with the environment is held fixed across algorithms.
14

---

Published in Transactions on Machine Learning Research (08/2025)
HalfCheetah: ARS
HallChretah: ARS v2
HalfCheetah: SFR
21337
3033
5400
Reowrrd
Rewerrd
2000
1000
5033
Total Env enterctiions
Totel Env Interettionss
Total Ern Internctions
Figure 3: Comparison of different variants on the HalfCheetah environment.
Hopper: ARS-v1
Hopper:
Hoppen SFR-2
4..2
3530
3000
23.00
Heward
Reward
2531-
2300
2032
1500
1000
agnod
1031-
500
compaseent...
I0M
201
204
10M
20M
200
10M
1.MM
20M4
20M
Tetal Env Interactions
Env Interactions
Total Interactions
Figure 4: Comparison of different variants the Hopper environment.
Swimmen. ARS-v1
Swimmen: ARS-22
Swimmer: SFR-2
1174
352
300
757-
232
Heward
280
200
332
332
382
sigrod
nol
XigRic nom dip
component..lp
Total Interactions
Total Enw Interactions
Eny Interactions
Figure 5: Comparison of different variants on the Swimmer environment.
WelkerZd: ARS v1
We Vbllte22: ARSiv2
Walker2d: SFR-2
6000
4000
Reowrrd
Reeward
2000
-033
1000
Totel Eny Interections
Total Ery Interections
Total Enn Interactions
Figure 6: Comparison of different variants on the Walker2d environment.
15

---

Published in Transactions on Machine Learning Research (08/2025)
Task
Algo
Algo with
Original Algo
Algo with
Algo with
used
Component Clip
Norm Clip
Signed Update
Swimmer
vRS
356.83 0.35
356.82 + 0.80
356.52 E 0.54
356.10 0.56
ARS-v2t
345.57 + 27.36
357.60 1: 1.17
356.54 + 0.55
354.95 2.39
SFR-2 (ours)
357.19 1.85
268.55 121.01
357.4 1.26
357.89 1.36
HallCheelah
ARS-vit
4097.17 156.33
3889.75 1 601.84
3786.04 1 140.15
3345.06 + 518.20
ARS-v2L
4849.18 = 1094.69
4621.09
908.41
4377.46 1 724.93
4110.96
846.69
SFR-2 (ours)
5762.27 + 499.75
2977.42 + 929 .5
5082.51 + 605.8
5042.62 + 341.89
Hopper
ARS-vIt
2312.74 817.09
2603.87
591.21
1924.58 i 752.77
2612.73
307.14
ARS-v2t
3639.82 = 52.60
3719.36 + 110.70
3511.56 + 151.94
3518.42 + 103.51
SFR-2 (ours)
3256.43 = 698.7
3215.54 757.42
3123.01 = 422.79
3194.95 410.85
Walker2d
ARS-vit
3354.91 + 567.67
2822.74 + 700.24
2295.12 12 = 687.07
2234.53 - 578.97
ARS-v2t
2652.87 1594.69
2689,
1121.71
2179.55 810.47
2028.
441.79
SFR-2 (ours)
2718.52 = 1875.69
1640.73 1072.84
1382.85 + 1051.86
1310.45 + 1560.97
Table 4: Average reward and standard error performance on each task (across 5 seeds), constraining total environment interactions as per Table 3.
Swimmer
Hopper
3500
350
SFR-2 [ours]
SFR-2 lours)
ARS-221
3000
ARS-v21
A2C
A2C
2500
HNPO
Reward
Reward
200
130
1500
1000
0-
0-
0.8M
Total Env Interactions
Total Env Interactions
HalfCheetah
Walker2d
4000
3000
SFR-2 (ours)
SFR-2 lours)
3500
ARS v2t
v2t
3000
MPO
PPO
2000
TRPO
2500
Reward
Reward
2000
1500
1000
500
Total Env Interactions
Total Env Interactions
Figure Performance plots across different environments.
6.2.3 Comparison with other benchmark algorithms
We compare now SFR-2 against ARS-v2t, TRPO, A2C, and PPO on MuJoCo tasks over a fixed budget of million environment steps. For SFR-2 and ARS-v2t, we use the same hyperparameter grid from Ap- pendix C.2. Thus, the best performing variants of both SFR-2 and ARS-v2t are used for comparison. For
16

---

Published in Transactions on Machine Learning Research (08/2025)
the other baseline algorithms, use the implementation and default hyperparameters provided in Ji et al. (2024). Our results are broadly consistent with prior findings in Mania et al. (2018a). Table 5 summarizes the final performance, and Figure 7 shows the learning curves.
SFR-2 achieves the highest reward in two the four environments (Swimmer and HalfCheetah), and performs competitively and consistently across the remaining tasks.
task
SFR-2 (ours)
ARS-v2t
PPO
A2C
TRPO
Swimmer
355.37 + 2.21
340.61 + 4.71
111.29 + 2.45
39.32 + 4.79
39.02 + 1.05
Hopper
2749.79 + 428.79 79
3164.38 + 112.17
530.77 +: 69.75
924.99 + 54.49
2234.73 + 156.64
HalfCheetah
3392.27 + 289.96
810.55 + 396.24
1824.04 + 686.48
523.73 + 26.0
1962.55 + 453.94
Walker2d
1040.4 + 792.8
428.32 + 20.25
636.83 201.27
643.65 = 119.77
2023.76 + 1258.39
Table 5: Average reward and standard error performance (across three seeds), constraining total environment interactions be million steps.
7 Conclusions
We presented model-free smoothed functional algorithms as suitable Monte-Card based alternatives to REINFORCE for the sctting of cpisodic tasks. We also presented the clipped and signed variants of the algorithms and analysed the convergence all the presented algorithms. We showed detailed empirical results of our algorithms, first simple gridworld problem before scaling them the MuJoCo locomotion tasks, We showed performance comparisons with other algorithms, in particular, the ARS algorithms that have been investigated recently. For a fixed number of environment interactions, our algorithms are competitive against ARS and in fact their signed and clipped variants are superior to ARS on more than half the settings tried. With the incorporation of variance reduction techniques, SFR-2 establishes itself as a strong candidate algorithm for online learning settings that demand low per-update cost and rapid learning. As future work, it would be of interest theoretically study the asymptotic rate of convergence results of the algorithms presented here. Such results for all algorithms including ES/ARS are not currently available.
Acknowledgements
The authors wish to thank the Editor and anonymous reviewers for their comments that helped improve the overall quality of this paper. This work was supported in part by Project No. /21///022//////////// 1M/04/ARR-00 ATR-04 from DRDO under DIA-RCÕE, by J. C. Bose Research Grant with No. ANRF/JBG/200 /0100//00//00/000000000 /0002000//////// / from ANRF, Government of India, and by the Walmart Centre for Tech Excellence, Indian Institute of Science, Bengaluru.
References
D. P. Bertsekas. Dynamic Programming and Optimal Control, Vol.I. Athena Scientific, 2012.
Dimitri Bertsckas. Reinforcement learning and optimal control, volume Athena Scientific, 2019.
S. Bhatnagar. Adaptive multivariate three-timescale stochastic approximation algorithms for simulation based optimization. ACM Transactions Modeling and Computer Simulation, 15(1):74-107, 2005.
S. Bhatnagar. Adaptive Newton-based smoothed functional algorithms for simulation optimization. ACM Transactions on Modeling and Computer Simulation, 18(1):2:1-2:31 2007.
S. Bhatnagar. The reinforce policy gradient algorithm revisited. In 2023 Ninth Indian Control Conference (ICC), pp. 177 177. IEEE, 2023.
S. Bhatnagar and V.S. Borkar. Multiscale chaotic SPSA and smoothed functional algorithms for simulation optimization. Simudation, 79(10):568 580, 2003.
17

---

Published in Transactions on Machine Learning Research (08/2025)
S. Bhatnagar, R.S. Sutton, M. Ghavamzadeh, and M. Lec. Incremental natural actor-critic algorithms. Aduances in neural information processing systems, 20, 2007.
S. Bhatnagar, R.S. Sutton, M. Ghavamzadeh, and M. Lee. Natural actor critic algorithms. Automatica, 45 (11):2471-244) 24822 2009.
Bhatnagar, H. L. Prasad, and L. A. Prashanth. Stochastic Recursive Algorithms for Optimization: Simal- tancous Perturbation Methods (Lecture Notes Control and Information Sciences), volume 434. Springer, 2013.
V. S. Borkar. Probability Theory: An Advanced Course. Springer, New York, 1995.
V. S. Borkar. Stochastic Approzimation: A Dynamical Systems Vieupoint, 2'nd Edition. Cambridge Uni- versity Press, 2022.
X.-R. Cao. Stochastic Learning and Optimization: A Sensitivity-Based Approach. Springer, 2007.
E. K. P. Chong and P. J. Ramadge. Optimization of quenes using an infinitesimal perturbation analysis-based stochastic algorithm with general update times. SIAM Cont. and Optim., 31(3):698 732, 1993.
Edwin KP Chong and Peter J Ramadge. Stochastic optimization of regenerative systems using infinitesimal perturbation analysis. IEEE transactions on automatic Control, 39(7):1400 1410, 1994.
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. In SODA, pp. 385 394, 2005.
T. Furmston, G. Lever, and D. Barber. Approximate Newton methods for approximate policy scarch Markov decision processes. Journal of Machine Leurning Research, 17:1-5 17:1-51, 2016.
Y. C. Ho and X. R. Cao. Perturbation Analysis of Discrete Event Dynamical Systems. Kluwer, Boston, 1991.
Jiaming Ji, Jiayi Zhou, Borong Zhang, Juntao Dai, Xuehai Pan, Ruiyang Sun, Weidong Huang, Yiran Geng, Mickel Liu, and Yaodong Yang. Omnisafe: An infrastructure for accelerating safe reinforcement learning research. Journal of Machine Learning Research, 25(285):1 6, 2024. URL http://jmlr... org org/papers/ v25/23-0681. .ttml.
V. Ya Katkovnik and Yu Kulchitsky. Convergence of a class of random search algorithms. Automation Remote Control, 8:1321-3326, 1972.
V.R. Konda and V.S. Borkar. Actor-critic type learning algorithms for markov decision processes. SIAM Journal on control and Optimization, 38(1):94-123, 1999.
V.R. Konda and J.N. Tsitsiklis. Onactor-critic algorithms. SIAM journal on Control and Optimizatiin, 42 (4):1143-1166) 1166 2003.
J. Kushner and D. S. Clark. Stochastic Approzination Methods for Constrained and Unconstruined Systems. Springer Verlag, 1978.
H. J. Kushner and G. G. Yin. Stochastic Approzimation Algorithmms and Applications. Springer Verlag, New York, 1997.
Dhruv Malik, Ashwin Pananjady, Kush Bhatia, Koulik Khamaru, Peter I, Bartlett, and Martin J Wainwright. Derivative-free methods for policy optimization: Guarantecs for lincar quadratic systems. Journal of Machine Learning Research, [21): 51, 2020.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random scarch provides a competitive approach to reinforcement learning. arXio preprinl ar Xii:1803.0F1 2018a.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies competitive for reinforcement. learning. Advances in neural information processing systems, 31, 2018b.
18

---

Published in Transactions on Machine Learning Research (08/2025)
P. Marbach and J.N. Tsitsiklis. Simulation-based optimization of Markov reward processes. IEEE Transac- tions on Aulomatic Control, (6(2):1111200)) 2001.
Sean Meyn. Control systems and reinforcement learning. Cambridge University Press, 2022.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. Proceedings of the 30th International Conference on International Conference on Machine Learning Volume 28, ICML'13, pp. 1310 1318. JMLR.org, 2013.
Santiago Paternain, Juan Andrés Bazerque, and Alejandro Ribeiro. Policy gradient for continuing tasks in discounted markov decision processes. IEEE Transactions on Automatic Control, 67(9):4467 4482, 2022.
L A Prashanth, S. Bhatnagar, M.C. Fu, and S.I. Marcus. Adaptive system optimization using random directions stochastic approximation. IEEE Transactions Aulomalic Control, 62(5):2223 2238, 2017.
L.A Prashanth and S. Bhatnagar. Gradient-based algorithms for zeroth-order optimization. Foundations and Trendso in Optimization, NOW Publishers, 8(1-3):1 2025.
Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanorvisto, Maximilian Ernestus, and Noah Dormann. Stable-baselines:: Reliable reinforcement learning implementattions. Journal of Machine Learning Re- search, 22(268):1-8, 2021. URL http://jmlr. http:///jiiloooooapprreeeeee wrg/paperrs/22222-1166 html.
Y. Rubinstein. Simulation and the Monte Carlo Method. Wiley, New York, 1981.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Tlya Sutskever. Evolution Strategies Scalable Alternative to Reinforcement Learning, September 2017. URL
J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXi::1707.063. 2017.
James C Spall. Introduction to stochastic search and oplimization: estimation, simulation, and control. John
Wilcy & Sons, 2005.
J.C. Spall. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Transactions on Automotic Control, 37(3):332-344 341- 1992.
J.C. Spall. A one-measurement form of simultaneous perturbation stochastic approximation. Automatica, 33(1)109-1112, 1997.
R. S. Sutton and A. W. Barto. Reinforcement Learning, 2'nd Edition. MIT Press, 2018.
R. S. Sutton, D. A. McAllester, S. P. Singh, and Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. In NIPS, volume 99, pp. 1057-1063, 1999.
Emanuel Todorov, Tom Frez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026 5033. IEEE, 2012. doi: 10.1109/IROS. 2012.6386109
R.J.. Willians. Simple statistical Pradient-following algorithms for connectionist reinforcement learning. Reinforcement learning, pp. 5-32, 1992.
Rui Yuan, Robert M Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In International Conference Artificial Intelligence and Statistics, pp. 3332 3380. PMLR, 2022.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A chal justification for adaptivity. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.no net, 2020. URL https:: httpa:////pereeee.eeeee forum? wii.umddd-BBggXXW.....
19

---

Published in Transactions on Machine Learning Research (08/2025)
A Details of the Convergence Analysis
We present here the details of the convergence analysis and give the proofs of the various results. We begin first with the results for the One-Simulation SF REINFORCE algorithm. We will subsequently sketch the analysis of the two-simulation SF algorithm. Finally, we shall discuss the convergence analysis of the algorithms with signed updates.
A.1 Convergence of SFR-1
Proof of Lemma 3: Notice that
G
G 8n-1
M A.(n 1)
E
Ai(n 1)
F Fn-11
8n-1
The first term on the RHS above clearly measurable Fn while the second term is measurable Fn-1 and hence measurable Fn well. Further, from Assumption 1, each M, is integrable. Finally, it is easy to verify that
E Fxl =0, Vi.
The claim follows.
Proof of Proposition 1: Note that
G 8n
G
E (1(
F
E E (m
In
Fr
on
where In A (0(m), A(m), n, m
n, m n),n 1 is sequence of increasing sigma fields with Go
A(0))))(0))) It is clear that Fn C Gns Vn 2 0. Now,
Gm (n)
(n E|G" 9.).
E
In
on
8n
Let sh = s denote the initial state in the trajectory x". Recall that the initial state s is chosen randomly from the distribution v. Thus,
E|G" Gal Σ ((s) s. =.000))t8
= Σ (())))))+
Thus, with probability one,
Gh 8n
Σv<os v(s) Ar(n) ((mn))
F
(m)
In
8n
Hence, it follows almost surely that
G" (n) |F =
Voln)ts.
U()E Am(n)
Fm
8n
5n
Using Taylor's expansion of Ve(n)+6,, (8) around f(n) gives us
82 + -h
(sn)))))) = (8())(8n) + 6, (n)) T V (o(nn)
(v)cn 0((8)
2
Now recall that (nn) = (Ai(n), = 1,.... d). Thus,
A(n) (()))) 1 A(n)Vo(n)(s)))
8n
8n
20

---

Published in Transactions on Machine Learning Research (08/2025)
+1(n)A(n) (V (S)))
8n (n) n) V2 (o +
Now observe from the properties of (n),, Vi, ni that [[A(n)] = 0 (the zero-vector), Vn, since (,(n) ~ NO, 1), vi,n. (the identity matrix), Vn.
(ii) E (n))")
(iii
E
Σ (m))))(m))m())
=
Property (iii) follows from the facts that (a) (1A,()) 0, æボ (b) (A) = 0. Vi # (this pertains to the case where i # j but j k above) and (c) []] = (for the case when ==j= = k above). These propertics follow from the independence of the random variables (n(n), i......, and n 2 0, as well as the fact that they are all distributed N(0, 1). The claim now follows from (i)-tii) above.
Recall that from Proposition 1, it follows that 8(n) o(6n)-
Proof of Lemma 4: It can be seen from (4) that Vo(s) is continuously differentiable in O. Tt also be shown as in Theorem 3 of Furmston et al. (2016) that (²V)(s)) exists and is continuous. Since f takes values in C, a compact set, it follows that Vo(ss) is bounded and thus (V((s) is Lipschilz continuous.
Finally, let L > O denote the Lipschitz constant for the function (s). Then, for a given 0g E C,
VVo(s) 11
Vv (s) ||ا|| VVa(s) VV, (s)
$ L7 0 0o
11 0 || +1 1 11
Thus, || VVo(s) | max(K, Li,S E S). Thus, || (v)(s) well. The claim follows.
(s) || +L
0. +L || 0
Let K, - VV (s)]l - Lilloo and K1 -
- KG(++ || I]).
Note here that since [S] < 00, K₁ < 00 as
Proof of Lemma 5: Note that
MMa+1 2
Σ
(M (M²+1)²
1=1
(Gm)²
(n)
+ [[A,(n) F.l
82
52
m -24:(n) (l),()) Fil)).
02
Thus,
E Ma |1]
82
-E"IA,(n)G"' (Fl)).
The claim now follows from Assumption 1 and the fact that all single-stage costs are bounded (cf. 17.174, Chapter 3 Bertsekas (2012)).
Proof of Lemma is easy see that Zn is Feaauauuablle Vn. Further, is integrable for each n and moreover E Z F.] Zn, almost surely since (M++1, 2 martingale difference sequence by
21

---

Published in Transactions on Machine Learning Research (08/2025)
Lemma 3. It is also square integrable from Lemma 5. The quadratic variation process of this martingale will be convergent almost surely if
8 Σ ==0
Bl| Zn+1 - Znl1 1nl < oo a.s.
Frl
(17)
Note that
E Zn+1 - Znll² 1 = =a(n)² Mn+1 Fr...
Thus,
Σ n=0
Elll
Zn | Σ
[r
M Ful
n=U
[an)
i
by Lemma 5. (17) now follows consequence of Assumption 2. Now FZ), 2 0 can be to be convergent from the martingale convergence theorem for square integrable martingales Borkar (1995).
Our main result below is based on Theorem 5.3.1 of Kushner & Clark (1978) for projected stochastic approximation algorithms. Before we proceed further, we recall that result below.
Let C' C Rd be a compact and convex set as before and r Rd + C denote the projection operator that projects any x z4)" Rd to its nearest point in C.
Consider now the following the d-dimensional stochastic recursion
Xn+1 r(X, + a(n)(h(X,)) En Br)),
(18)
under the assumptions listed below. Also, consider the following ODE associated with (18);
(t) = ((h(X(tt)
(19)
As mentioned before, let C(C) denote the space of all continuous functions from C to Rd. The operator D: C(C) + C(R.) is defined according to (15). The limit in (15) exists and is unique since C is convex set (the way it is defined). If C' is not convex and the limit is not unique, one may consider the set of all limit points of (15). Note also that from its definition, [(v(z)) = v(x)
E Co (the interior of C). This is because for such an F, one can find rj > sufficiently small so that x + qu(()) E C as well and hence T(x + nu(x))
y)o(x). On the other hand, if x OC (the boundary of C) is such that + nu(x)) C, for any small 7 > 0, then [(v(x)) is the projection of v(x:) to the tangent space of 00 at Consider now the assumptions listed below.
(B1) The function h: Rd + Rd is continuous.
(B2) The step-sizes ann), n 2 0 satisfy
((n) > OVn, a oo, a(n) - as n + 00.
(B3) The sequence Bn, 0 is bounded random sequence with B, ++ 0 almost surely
(B4) There exists T > 0 such that Ve 0,
m(JT+0--1
lim P
sup max
Σ
a(i)E: 2e = 0.
n0 900
j2n 1ST
L=m(yT)
22

---

Published in Transactions on Machine Learning Research (08/2025)
(B5) The ODE (19) has compact subset K of RV its set of asymptotically stable equilibrium points.
Let {(n), n 2 0 be a sequence of positive real numbers defined according to t(0) 0 and for 2 1, n-1
t(n) Σ a(j). By Assumption (B2), t(n) + oc as + co. Let m(t) = max(n t(n) S t). Thus, m(t) + o0 j=0
oo. Assumptions (B1)-(B3) correspond to A5.1.3-A5.1.5 of Kushner & Clark (1978) while (B4)-(B5)
correspond to A5.3.1-A5.3.2 there.
(Kushner & Clark, 1978, Theorem 5.3.1 (pp. 191-196)) essentially says the following:
Theorem (Kushner and Clark Theorem:) Under Assumplions (B1)-(B3) almost surely, Xn - K
48 n + 00.
Finally, we come to the proof of our main result.
Proof of Theorem In lieu of the foregoing, we rewrite (5) according to
0,(n + 1) = r. (0(())) a(n) Σ v(s) V, (s()((s)
(nn)3,((m) + M Mi+1):
(20)
where 3i(n) is in (13). We shall proceed by verifying Assumptions (B1)-(B5) and subsequently appeal to Theorem 5.3.1 of Kushner & Clark (1978) (i.e., Theorem above) to claim convergence of the scheme. Note that Lemma 4 ensures Lipschitz continuity of VVo(s) implying (B1). Next, from (B2), since 6, + 0, it follows that a(n) - as n + xo. Thus, Assumption (B2) holds as well. Now from Lemma 4, it follows that Σ. VVs)VVo())) is uniformly bounded since 0 E C, a compact set. Assumption (B3) is now verified from Proposition Since C' convex and compact set, Assumption (B4) holds trivially. Finally, Assumption (B5) is also easy to see a consequence of Lemma Now note that for the ODE (14), F(0) E. (os) serves associated Lyapunov function and in fact
VF(O)TI( [((s)VVo(s))
(3))VoV(()) Σ (()))V(((s) SO.
For E C (the interior of C), it is easy to see that
= ((s)VvVV((()) and VF(O)T(( [((s)VVo(s)) Oif0E
= 0o..
For 0 E 8C' (the boundary of C), there additionally be spurious attractors, see Kushner & Yin (1997), that are also contained in H. The claim now follows from Theorem 5.3.1 of Kushner & Clark (1978).
A.2 Convergence of SFR-2
The analysis proceeds in a similar manner as for the one-simulation SF except with G - -
in place of
25,n
Gm
8,
Proof of Proposition 2:
A similar calculation as with the proof of Proposition 1 would show that
G
-
Fn = Σ E())E Ai(n) (Voln)55. (m Fr
E (inn)
28,
28,
23

---

Published in Transactions on Machine Learning Research (08/2025)
Using Taylor's expansions of (o. and Vo(n) (()) around 0(n) gives
((n) (Vointtsa ((o (. = VVanna)) o(6)).
25,
The zero order and second order terms directly cancel above instead of being zero-mean, thereby resulting in lower gradient estimator bias. The rest follows from properties (i)-(ii) mentioned previously for the one-simulation gradient SF. In particular, ([)(
Proof of Theorem 2:
In the light of Proposition 2, the proof here follows in similar manner as one-simulation SF.
A.3 Proof that SFR-2 has Lower Bias than SFR-1
Proof of Lemma
We show as part of the proof of Proposition that
G"
((m) = Σ E(S (m(n) Vo00)),. 0(m))
(n)
(21)
on
6n
Using a Taylor's expansion of Vo(m)+o,, (8) around ((n) gives us
V((m)+ (8())(8n) (n)) (S()))(s)) + on A(n) Voo + o(5.).
on
Now recall that A(n) = (Ai(n), 1, l,....,d'
d)=. Thus,
((m)))),,))))88 1 An))am (Vannai 8n Vann (s)) 2
(nn)
8n
on
(22)
Taking now the conditional expectation as required in the RHS of (21), it can seen that
Volm))s. ((m) = (sVo + O(r,).
E (n)
6n
Now in the SFR-2 case, we require one more Taylor's expansion, namely of Vo(n)- around the point ((n). Here, like (22), one obtains
(n)) (, 8n
A(M) An))))) VVocn) (8,) &n (())((n) V (8 (mo)
5n
(23)
As part of the proof of Proposition 2, observe with Proposition that
E (A)()) (G"
(0"T--" G"
Σ (() A,(n) ((,)))) - Vo(m)-6,
Fr
F
(24)
28n
28,
From (22) and (23), one then gets
E (n) ((n()) - Vo(n) - (()(())))))
Fx
V.Vo(n) + o(6,)-
28p
The important difference to note between the Taylor's expansions in the case of SFR-1 and SFR-2 is that in 8n
SFR-2, there is a direct cancellation of the bias terms (onn and O/ (m) (Vo))) (s))))))
1
5m
that does not happen in SFR-1. The second term above does not contribute as much to the bias as the first term because the latter term has 8, in the denominator that is expected to be small, in fact, ó, + 0 as n co. This term averages out to zero eventually SFR-1. In SFR-2, this term simply does not exist. This results in lower bias SFR-2 opposed to SFR-1 and eventually results improved performance of SFR-2 over SFR-1.
24

---

Published in Transactions on Machine Learning Research (08/2025)
A.4 Proof of Lower Variance in the Signed and Clipped Variants
Proof of Lemma 2:
(i) Note from definition, Y² thereby E[y?] = and E[Y]² < 1. Thus, Var(Y) S
(ii) Recall f E (Ser Jm is a projection map from R to C c Rd, where C' is compact and convex set. We first show that this map is nonexpansive. In other words, we show that
[I(x)) - s(u)ll & || oll, Vx,y E Rd.
Note that since C' is convex and compact,
(o - ((x) [(x)) SO, E.
Now since f(y) E C, we have
(x - (()) - f(x)) $o.
(25)
Similarly, we also have Changing the sign in both terms above gives us
(y f() - f(w)) 20.
(f(u) - y, f(y) f(x)) SO.
(26)
Adding (25) and (26) gives
f(x) + f(y) v. fly f(x)) so.
In other words,
(x 1r v(v) [()) (f(1) - ((x). f(x)) S O.
Thus,
(1f(r) f(x)11 s ( - x, f(v) f(x))
S 11y-= (l) - s(x))l.
by the Cauchy-Schwarz inequality. now follows that
(1(()) - f())] S by x||-
Thus, U 2 2 El]((t)=f(BU)1 The claim now follows since Ef(U) (lgmin,E]f(())
0
A.5 Convergence of Signed SFR-2
Recall that have
H:(0(n), A:(n) (o())+6(m)(())
Vo(n) (()))))())(())) 25(n)
As explained previously,
ElH,( (n))FFl = V.Va(n) + o(5(n)).
Also, recall the 'error' in the ith component is given by
(n) = (.(((m). (nn) - V.Vo()) = An) + o(8()))
3
Proof of Theorem 3:
25

---

Published in Transactions on Machine Learning Research (08/2025)
We rewrite the algorithm as follows:
(n + 1) 1)=+1)=[;(000))0) (F()))
= - a(n) > - = 20)),
where I(.) is the indicator function. Thus, we have
1) [10+4])--00000--oo0022-111100100 0))
= -1(0k))-idhN11-PPPP0000004441100 M + 1))),
where
M(nn + 1) = -10----777PP771110000-0000--01-0 2P(e.(n) S Σ Vos (s) - 2I(e((n) S E v1s V.)
S 50),
= 22((e(()) S E Ve)
2T(e(() S Σ Vos)
by (A1). It is casy to see that (M) 2 0 is martingalc difference sequence. Since sup,, (n)] & 1, and under (A4), it follows from an application of the martingale convergence theorem
that
Σ a(m) Mm+1, , n 2 1 is an almost surely convergent martingale.
m=0
Tt easy to verify that ((0) V(sVV(s)))) itself is Lyapunov function for the ODE (16) since
dW = - Σ v(s))Vo(s))0), Σ v(s)VVV(s))
(
dt
Σ TT((1 -2F(( Σ [v(s)V.V(())10)) Σ (.VoVVVV))))..
From (A3), if Σ, (V) > 0, (1 -2F(- Σ. u(8) (() 2 0 and dW(0)
dt s 0. Similarly, if < 0. Further, when VVs) dVe
o, dW 0.
V.Vo < 0, (1 - 2F((VVVV10) < 0 and di
di
From Lasalle's invariance theorem in conjunction with Theorem 2 of Chapter 2 of Borkar (2022), it follows that ((n,, n 2 0 converges almost surely to the largest invariant set K c K C {0]T(((1 2F( Σ. u(8) VV ()): E. VVs()) = =3. The claim follows.
A.6
Convergence of SFR-2 with Clipped Gradients
Proof of Thcorem 4
Recall that the projection operator f E {m). Further, both f = Sa and f= fm are continuous functions. Thus, observe that f(VV)) + f(VV)), v0, where Vogi denotes the gradient estimate obtained from the two-simmlation SF.
Following the same sequence of steps as Theorem 2, can be seen that the underlying ODE tracked by the algorithm is
0( -()= Σ (ss)s(VV(s)))
(27)
Note also that by construction in either case, namely (i) fo and (ii) f = fm. we have that f(VVo(s)) if and only if (s)
26

---

Published in Transactions on Machine Learning Research (08/2025)
A.7 Convergence of ES-v1
Proof of Theorem 5
Denote by Fly) the mean squared difference function in variable R2 defined as below:
Vo(n) o" A())) 2 [(m)
1 Fly) 2
6n
Then,
Vo ( ( A()) A(m))(())
vyF(y) = E
-y"
8n
Note now that
El (M))) = (m) 0/ = y,
since [[A(n)A(m"]]= =1 (the identity matrix). Equating v,F(y) to zero gives us upon simplification
4. Am))((())
= E
8n
thereby resulting in the gradient estimate
((1)
kd maml
where the (n), m = I,...,k k are independent, having the multivariate Gaussian distribution with mean 0 and covariance matrix One may write
((n) (..
where
k Σ
(m(n)
(m
i = 1.... d. Thus, in the ES procedure, instead of using one sample of multivariate Gaussian, one calls k samples of the same and takes the sample average of these. can be seen that using a Taylor's expansion of (mm))))) around ((n) gives us
(m)))))) = Vo(n) (sa) + 8n (n) (Vocn) + 82 A(n) ('n)nnTT V Vo(nn) + o(.2)) 2
Now recall that A Am(n) (A) 1, d), Thus,
A (n) (lm))t,Ammm)(e
A A (n)(n((()))
8n
8n
+A n (VVamnn
6n 2
V Vo( +
Now observe from the properties of (n), Vm, that (i) [AA"(n)) 0 (the zecoor,, Vn, Vm = 1,..., k since (T) ~ N(0, 1), n. = 1 (the identity matrix), Vn, Vm 1,..., k.
(ii) E[A
(iii) Σ AT (T( 0.
1.j.==1
Property (iii) follows from the facts that (a) ((AT))))())M)M))) O, Wi * #1, Vm 1, 1,..., (b)
27

---

Published in Transactions on Machine Learning Research (08/2025)
(TA)")) = vi Vi J. Vm = k,k..,k (this pertains to the case where i + j but k above for any given m ,,...,k) kt) and (c) ([(A)")(m)] follow from the independence of the random variables (m),), i 1,...,..... d, m .,..., A and 2 O, as well as the fact that they are all distributed (0, 1). As with Proposition 1, it can be seen that
(for the case when i = j above). These properties
F(((n) 0(n)) VV (8) + 0(x)).
Now rewrite (10) as
=1 ((;+1)=1;;0(m - - a(n)N.(n)
(28)
where
Mi(n) = De(n)) - ((0((N))((M)
and
N:(n) kō Σ (T) - Vo(n)+o.Amm))
As in Proposition 1, it can also be seen that Ni(n), 2 0 is martingale difference sequence under the sequence of sigma. algebras Gn, 1, redefined under: 9n _ (((()),AT(())))) S n, 1i n, m I....,k),y k), n 2 is sequence of increasing sigma fields with Go o0(0), A()). The rest of the proof now follows via an application of the Kushner-Clate lemma as with SFR-1.
A.8 Convergence of ES-v2
As with the case of ES-v1, define in this case
2 E ( ((()))-) - 6..())))))))()))) - - A(m) 10(m)
F(y) =
26
Finding now Fy) and setting it to zero gives us
y = E (
Vo(n) (((m))) -
(.lo))))))))) ) A(m))0m))
25
resulting in the gradient estimate
((n) 2k.5 m=1
Σ (Vo(n)+6, - (mt))
and as with Proposition using a similar sequence of steps as in Theorem 5 above, we obtain
Elg(n) ((n)] = Vo (s) + o(6.).
Note that one obtains 06,)) above as against O(8x) in similar expansion in Theorem 5. This is because each epoch as opposed to one and which results in a direct
of the use of two function measurements cancellation of the first term on the RHS of the Taylor's expansions of Vo(n)=6.A and A.. around (n), see Proposition 2. The rest of the proof now follows along the same lines as Theorem 5.
B Augmented Random Search (ARS) and Comparisons
We first describe the ARS algorithm from (Mania et al., 2018abb) and the various versions of it in detail as we incorporate this for purposes of comparison.
The ARS paper (Mania et al., 2018a) has ARS-v1 and ARS-v2, given in the above algorithm. It uses only two-sided measurements since they result in more stable gradient estimates. Note from here on, in terms of
28

---

Published in Transactions on Machine Learning Research (08/2025)
Algorithm Augmented Random Search (): four versions V1, Vl-t, V2 and V2-t
1: Hyperparameters: step-size a, number of directions sampled per iteration k, standard deviation of the exploration noise V, number of lop-performing directions to use b (b < k allowed only for VI-t and V2-t)
Initialize: Mo E R No e R", and Σg I, E R =
while ending condition not satisfied do
4: Sample ô1, .. 6 in Rex* with i.i.d. standard normal entries.
5: Collect 2k rollouts of horizon H and their corresponding rewards using the 2k policies
-x)-(2) (M, voj)a x
V1:
Tsd,- (x) (M, voj)ar
TTu,-() (M, v51) diag (E,) -//)~1// (x pb)
V2:
(x), (M, -môj) diag (2i,) -//((x p1)
for I E (1.2....,A))
6: Sort the directions ó; by max(r(Tza,++ ((())))) denote by d0g the 1-th largest direction, and by ",,0,+ and -,,(),, the corresponding policies.
7: Make the update step:
M,+1 = Mj +
onn
where OR is the standard deviation of the 26 rewards used in the update step.
V2 Set PJ+1, Ej+1 to be the mean and covariance of the 2k + 1) states encountered from the start of training.
jtj+1
10: end while
ARS and our experiments, we do not deal with the one-sided version at all. Only two-sided is used. When we say reward, we refer to the total return of the episode. This is as per the terminology used in the original paper.
The authors use M2 for the weights of the linear policy at iteration j. They sample N perturbations and perturb the policy in two ways (+ and -) and obtain the total episodic reward against cach perturbed policy (total of N episodes are run through). As we read through the algorithm, the policy function of our SFR-1 and SFR-2 are similar to ARS-v1 from the line 5 of the algorithm mentioned below. ARS-v2 uses additional normalization for the states. We confirm from line 8 that they are calculating the mean and covariance of all states encountered by the algorithm upto that point and using it in line 5 for normalization. As an enhancement, the authors select only b out of the N directions.
In line 7, the update step is very similar to SFR, except the authors, the denominator, use OR = standard deviation of returns from each perturbed policy. Instead, in our implementation, we just use the standard deviation of perturbations The update step at line 7 then becomes the following.
Mf+1 M, a - 8(m)-
29

---

Published in Transactions on Machine Learning Research (08/202))
C Numerical Experiments:
Setting Parameters
C.1 Gridworld Details
To enable a finite horizon setup, we limit the number steps that can be taken in the environment. A large limit results in increased runtime, so we sot values as so.
Grid size
Max episode length
Max Interactions Limit
50
50000
10 10
100
150000
50 50
200
200000
Table Maximum steps allowed in an episode for a given grid-size (L)
C.1.1 Policy function
Boltzmann Policy
State
Faster karacer
12
13
14
15
Features
Line
Feature Extactor for grid
Probaballiss
Features from state
(b) Policy architecture
Figure 8:
Boltzmann Policy used across all algorithms
The input to the policy consists of polynomial and modulo features of the agent's position in the grid. Both algorithms utilize the same policy function, which computes logits for the available actions using a linear function. The logits are converted into probabilitics via softmax. Figure illustrates the same.
C.1.2 Algorithm Parameters
For the SF-REINFORCE algorithm chose the parameters 8(n) do 50000 )a and a(n) og 550000 where n the episode number. Here, we set a(0) Qg different schemes a decay scheme where vary d and set
50000++ 10 6 In this sctting, d < 0.5 is required
for convergence. We experiment with 8(0) ón = and a constant scheme with d = 0 and with varying dg. To reduce the variance, measure G. as the average over 10 trials. The two sided version uses 5 trials for each side, allowing fair comparison.
We also include the PPO, TRPO and A2C algorithms from Rallin el al. (2021) for our comparison. We use the same policy architecture along with a linear layer for the value function. For REINFORCE and PPO algorithms, the policy is updated using the policy gradient via an ADAM optimizer with its learning ratc set 0.0003. To ensure the results are reproducible, we run every setting 10 times with different seeds, and plot the mean the dark line, and shade using the standard deviation around it.
30

---

Published in Transactions on Machine Learning Research (08/2025)
C.2 MuJoCo Details
C.2.1 Optimal Hyperpameters
delta
std
deltas used
directions
transform step
size
0.020
20
120
0.020
component clip
0.020
20
120
0.020
none
0.020
20
40
0.020
norm clip
0.020
20
80
0.020
signed
Table 7: ARS-v1 best hyperparameters for HalfCheetah
delta
std
deltas used
n directions
step _size
transform
0.020
80
0.020
component clip
0.020
20
80
0.020
none
0.020
20
80
0.020
norm clip
0.020
20
40
0.020
signed
Table 8: ARS-v2 best hyperparameters for HalfCheetah
delta std
deltas used
directions
step size
transform
0.030
32
0.020
component clip none
0.030
16
0.020
0.020
32
0.020
norm clip
0.020
16
0.020
signed
Table 9: ARS-v1 best hyperparameters for Hopper
delta std
deltas used
n directions
step size
transform
0.030
32
0.020
component _cip
0.030
32
0.020
none
0.030
16
0.020
norm clip
0.020
32
0.020
signed
Table 10: ARS-v2 best hyperparameters for Hopper
delta
std
deltas
used
directions
step
size
transform
0.020
30
30
0.020
component clip
0.020
10
50
0.020
none
0.020
30
30
0.020
norm clip
0.020
10
30
0.020
signed
Table 11: ARS-v1 best hyperparameters for Swimmer
delta std
deltas used
directions
size step
transform
0.020
10
30
0.020
component clip
0.020
10
50
0.020
none norm clip
0.020
30
30
0.020
0.020
50
0.020
signod
Table 12: ARS-v2 best hyperparameters for Swimmer
31

---

Published in Transactions on Machine Learning Research (08/2025)
delta std
deltas used
I directions
stop_siie size
transform
0.025
40
80
0.030
component clip
0.025
80
0.020
none
0.025
100
0.020
norm norm_clip
0.025
40
80
0.020
signed
Table 13: ARS-v1 best hyperparameters for Walker2d
delta std
deltas used
directions
step_ size
transform
0.025
80
0.030
component clip
0.025
40
80
0.030
none norm clip
0.025
40
80
0.030
0.025
40
100
0.020
signed
Table 14: ARS-v2 best hyperparamcters for Walker2d
delta std
step size
transform
0.020
0.005
component clip
0.020
0.005
no no_transform
0.020
0.010
norm_ norm_clip
0.020
0.040
signed
Table 15: SFR best hyperparameters for HalfCheetah
delta std
step_stt ssze
transform
0.020
0.005
component_ _cip
0.020
0.005
no. transform
0.020
0.005
norm clip
0.020
0.005
signed
Table 16: SFR best hyperparameters for Hopper
delta std
step size
transform
0.020
0.020
component clip
0.020
0.020
transform norm clip signed
0.020
0.020
0.020
0.020
Table 17: SFR best hyperparameters for Swimmer
delta. std
step size
transform
0.025
0.003
component_ clip
0.025
0.003
no transform norm clip
0.025
0.003
0.025
0.003
signed
Table 18: SFR best hyperparameters for Walker2d
C.2.2 All hyperparameters
32

---

Published in Transactions on Machine Learning Research (08/2025)
Parameter
Value
k
[40, 80, 120] [40, 80, 20, 120)
a
0.02
0.02
transform
[orm clip, component clip, signed, none]
Table 19: ARS all hyperparameters for HalfCheetah
Parameter
Value
k
332 16
[8, 16, 32]
0.02
[0.02, 0.03]
transform
[norm_clip, component clip, signed, none]
Table 20: ARS all hyperparamcters for Hopper
Parameter
Value
k
[00 30]
[10, 50, 30]
a
0.02
V
[0.02, 0.01]
transform
(component clip, signed, none, norm clip]
Table 21: ARS all hyperparameters for Swimmer
Parameter
Value
[80, 100] [40, 80, 100]
a
[0.03, 0.02]
0.025
transform
[component clip, signed, none, norm clip]
Table 22: ARS all hyperparameters for Walker2d
Parameter
Value
(0.04, 0.01, 0.005, 0.03]
0.02 [norm clip, component. clip, signed, none]
transform
Table 23: SFR-2 all hyperparameters for HalfCheetah
Parameter
Value
00.001, 0.005, 0.01]
[0.02, 0.025]
transform
[norm clip, component clip, signed, none]
Table 24: SFR-2 all hyperparameters for Hopper
Parameter
Value
0.02
[0.02, 0.01]
transform
chim, component clip, signed, none]
Table 25: SFR-2 all hyperparameters for Swimmer
33

---

Published in Transactions on Machine Learning Research (08/2025)
Parameter
Value
a
[0.003, 0.01]
" transform
[0.025, 0.02]
[component plip, signed, none, norm clip]
Table 26: SFR-2 all hyperparameters for Walker2d
34


Reviews:
[{"review_id": "CXliC4EDgd", "reviewer": "Reviewer_Mkv4", "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 paper offers asymptotic convergence analysis for the proposed algorithms.\n\n+ Incorporating signed gradients and clipping into the SF-REINFORCE framework is shown to leads to improvements in stability and sample efficiency. While this is probably to be expected, it is nice to demonstrate empirically.\n\n+ The paper compares their approach with ARS on multiple MuJoCo benchmarks. The results suggest that the proposed variants, particularly SFR-2 with clipping or signed updates, are competitive or even superior in certain environments.\n\n+ Good motivation and connection to existing literature on random search, policy gradient, and zero-order optimization.\n\nWeaknesses:\n\n- The paper is mathematically dense, especially in the convergence analysis sections, which may hinder accessibility for broader RL audiences. Furthermore, it uses notation that is non-standard compared to most machine learning papers on RL.\n\n- A lot of the formalization in section 2 seems overly dense and unnecessary. The paper assumes \"that the policies are stationary randomized and are parameterized via a certain parameter θ\" so I think things would be more succinct and accessible if a lot of the earlier notation was dropped and standardized. For example, why use $\\phi_\\theta(s, a)$ when $\\pi(a|s)$ is much more common in the literature. \n\n- The paper primarily reports final return values in tables; learning curves or training dynamics over time or other visuals would provide more insight into stability and convergence behavior.\n\n- It's unclear what the main contributions are and what recommendations should be taken from the paper in terms of which algorithms to use and when. From the paper it seems the theory is the main stated contribution, but what about the theory is important? Is it just the fact that the paper shows asymptotic convergence? Was this believed to not be true? What are the main benefits of having this new theory?", "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 revisits the REINFORCE policy gradient algorithm and proposes a family of smoothed functional (SF) variants to reduce gradient estimator variance and improve convergence in episodic reinforcement learning tasks. The authors discuss two main estimators: a one-simulation variant (SFR-1) and a two-simulation variant (SFR-2), and augment them with signed gradient updates and clipping techniques inspired by PPO. The paper provides rigorous asymptotic convergence proofs for all proposed algorithms and empirically benchmarks them against the Augmented Random Search (ARS) baseline across several MuJoCo environments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Suggestions for Improvement:\n\n- Clarify contributions: Clearly differentiate what is new (e.g., convergence analysis, signed/clipped variants in an RL context) versus what is a known technique (e.g., SF gradient estimators). It seems that all the algorithms considered are well known and well studied. Please clarify the impact of the theoretical and empirical results.\n\n- The tables are dense. To make them easier to read, I recommend bolding the highest performing numbers to make it easier to see trends in which algorithms work best. In particular, it is hard to tell which method is the best or in which cases an algorithm should be recommended.\n\n- Improve accessibility by possibly adding a diagram summarizing the algorithm family, include intuitive explanations before/after formal results to emphasize why the theory is valuable/interesting, and simplify notation where possible.\n\n- A summary of the convergence results at the end of section 5 would be very beneficial. In particular, what would we expect in terms of performance based on the theory? Does the theory match what is seen in the empirical results of section 6? What is learned from section 5 that was previously unknown?\n\n- Plot cumulative rewards vs. environment interactions to visualize convergence dynamics and variance across seeds.\n\n- Minor comment, but I found the citations to be awkward and I think they should be fixed and made consistent. On the second page parenthetical citations are used as nouns:\nFor example: \"In (Salimans et al., 2017), evolutionary...\" I would recommend something like \"In Salimans et al. (2017), evolutionary...\" which you should be able to get with \\citet. \nIn the first couple paragraphs the opposite happens where citations that are usually parentheticals are used without parentheses.\nFor example: \"The policy gradient theorem, cf. Sutton et al. (1999); Marbach & Tsitsiklis (2001); Cao (2007),\nwhich is a fundamental result...\" \nI would recommend just putting these as \\citep. For example: \"The policy gradient theorem (Sutton et al. 1999; Marbach & Tsitsiklis 2001; Cao 2007), which is a fundamental result...\"\nI think this will make the citations more standard.\n\n- The figures above Table 1 should have a caption and be referenced in the text.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "csGY1bwPQr", "reviewer": "Reviewer_Me2L", "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\nThe convergence analysis of the algorithms is rigorous.\n\n## Weaknesses\n\n- The write-up has a number of typos, e.g., in Sec 3 *run using the policy parameter* n -> n-1.\n- The structure of the paper could be improved, e.g., subsections in intro and related work section.\n- Notation consistency, e.g., i Sec 3 mth trajectory at first nth trajectory a bit later, and then m is used again to denote a set as well as enumeration.\n- Better presentation overall, e.g., caption inf figure is missing/bold the table where values are best\n- Proposed algorithms and modifications are not motivated or intuitevely explained. E.g. why the +- in SFR-2 and not two different \\Deltas? What is the reasoning behind this? Or why update rule (6) specifically?\n- Empirical results are marginal. Even for the cases where SFR approaches have some gain the signal is not strong.", "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": "The paper revisits the REINFORCE algorithm, proposing two variants based on single and two function measurements at a perturbed parameter value. They also propose two modifications to these algorithms for reducing their variance. The asymptotic convergence of all algorithms is shown, and extensive evaluation through simulation experiments is performed.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weaknesses above.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BjXpv74obO", "reviewer": "Reviewer_VHbd", "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\n1. This paper provides theoretical convergence proofs using stochastic approximation theory for all algorithmic variants. \n\n2. Proposed algorithms address variance reduction using signed and clipped variants that yield empirical performance gains. \n\n3. Empirical results compare sample efficiency over prior baselines with evaluations under a fixed budget of environment interactions in MuJoCo continuous control environments. \n\n\n**Weaknesses**:\n\n1. This paper does not quite motivate why an alternative approach to REINFORCE-style policy gradients is being studied, when there are well established algorithms like PPO, A2C etc. It would improve the quality of the paper to include some intuitive toy examples that provide insights into the differences between SF and PG methods and conditions under which one paradigm outshines the other. \n\n2. The clarity of presentation of the results should be improved. For example, Table 2 does not highlight the best-performing algorithm in each case, making it harder to follow along with the authors' description of the results.\n\n3. I have briefly skimmed the proofs in the Appendix. It would help improve the appeal of the techniques proposed in this paper to a wider audience if there were additional proof sketches that intuitively explain the overall flow of how the proof proceeds. \n    - Possible typo in page 19: fourth line from the end of the page says \"\\delta_n in the denominator\" - should it be \"numerator\" instead?  \n\n\n4. This paper stops at proving asymptotic convergence. Finite-time or sample complexity guarantees are left for future work, despite claiming improved sample efficiency with proposed algorithms.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 proposes a family of smoothed functional (SF) estimators to replace REINFORCE style policy gradients for policy optimization in episodic reinforcement learning tasks. Following are the main contributions in this work. \n\n1. Two main smoothed functional estimators are introduced:\n\n    - SFR-1: A one-sample SF estimator.\n    - SFR-2: A two-sample central-difference-style SF estimator using perturbations in opposite directions.\n\n    These variants require only one or two state-action-cost trajectory simulations per update, making them sample-efficient.\n\n2. To reduce the variance of parameter updates arising from noisy return estimates, SFR-1 and SFR-2 are further modified as follows: \n\n    - Signed updates: Use only the sign of the estimated gradient components.\n    - Clipped gradients: Clip the total or component wise gradient norm to control the magnitude of the update and handle outliers.\n\n3. This paper provides asymptotic convergence proofs for all the algorithmic variants, including signed and clipped forms, as well as batched versions (ES-style).\n\n4. Experiments are conducted on four MuJoCo continuous control tasks: Swimmer, Hopper, HalfCheetah, and Walker2d.\nGiven a fixed budget of environment interactions, SFR-2 (especially with component-wise clipped updates) is shown to be competitive with or superior to ARS, particularly in HalfCheetah and Swimmer.\nThe results suggest that frequent updates with low-variance estimators can be more effective than infrequent but high-precision updates (as in ARS).\n\nThe algorithms in this paper do not require gradient computation or critic training.\nThey are applicable to general episodic MDPs and nonlinear policies, making them suitable for a wide range of RL problems.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Following requests are critical for positive recommendation: \n\n1. *Clarify motivation for proposed approaches*. Authors should explicitly discuss why REINFORCE is still relevant in light of more modern policy gradient methods. For instance, highlight benefits like simplicity, parallelizing ability, or test-time usage.\n\n2. Even if the computational cost is higher, authors should include at least one run of PPO or A2C to demonstrate how proposed methods compare with widely adopted standards in continuous control.\n\n3. Discuss applicability to other settings, for example non-episodic (discounted) MDPs or partially observable tasks.\n\n4. Discuss possible limitations in high dimensional spaces. For example, are there certain conditions in the optimization landscape that especially disadvantage or favor SFR-2 over ARS or PG?", "broader_impact_concerns": "N.A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)