Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
Authors: Alessandro Montenegro
Marco Mussi
Matteo Papini
Alberto Maria Metelli
Venue: ICML 2025 poster (2025)
Keywords: reinforcement learning
policy gradients
convergence
deterministic policies
Primary area: reinforcement_learning->policy_search
TL;DR: Study of last-iterate convergence guarantees to the optimal deterministic policy of policy gradients dynamically adjusting the stochasticity of the (hyper)policy.

Abstract: *Policy gradient* (PG) methods are effective *reinforcement learning* (RL) approaches, particularly for continuous problems. While they optimize stochastic (hyper)policies via action- or parameter-space exploration, real-world applications often require deterministic policies. Existing PG convergence guarantees to deterministic policies assume a fixed stochasticity in the (hyper)policy, tuned according to the desired final suboptimality, whereas practitioners commonly use a dynamic stochasticity level.
This work provides the theoretical foundations for this practice. We introduce PES, a phase-based method that reduces stochasticity via a deterministic schedule while running PG subroutines with fixed stochasticity in each phase. Under gradient domination assumptions, PES achieves last-iterate convergence to the optimal deterministic policy with a sample complexity of order $\widetilde{\mathcal{O}}(\epsilon^{-5})$.
Additionally, we analyze the common practice, termed SL-PG, of jointly learning stochasticity (via an appropriate parameterization) and (hyper)policy parameters. We show that SL-PG also ensures last-iterate convergence with a rate $\widetilde{\mathcal{O}}(\epsilon^{-3})$, but to the optimal stochastic (hyper)policy only, requiring stronger assumptions compared to PES.

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
Alessandro Montenegro'
Marco Mussi!
Matteo Papini' Alberto Maria Metelli
Abstract
expert knowledge in the policy design phase (Ghavamzadeh & Engel. 2006), improving the efficacy, safety, and inter- pretability of the learned policy (Peters & Schaal, 2008).
Policy gradient (PG) methods are effective re- inforcement learning (RI.) approaches, particu- larly for continuous problems. While they op- timize stochastic (hyper)policies via action- or parameter-space exploration, real-world applica- tions often require deterministic policies. Exist- ing PG convergence guarantees deterministic policies assume fixed stochasticity in the (hy- per)policy, tuned according to the desired final suboptimality, whereas practitioners commonly use a dynamic stochasticity level. This work pro- vides the theoretical foundations for this practice. We introduce PES, a phase- based method that re- duces stochasticity via deterministic schedule while running PG subroutines with fixed stochas- ticity in each phase. Under gradient domination assumptions, PES achieves last-iterate conver- gence to the optimal deterministic policy with a sample complexity of order Ö( 5). Addition- ally, we analyze the common practice, termed SL-PG, of jointly learning stochasticity (via an appropriate parameterizzaion) and (hyper)policy parameters. We show that SL-PG also ensures last-iterate convergence with rate Ö(e-3), but to the optimal stochastic (hoper)policy only, re- quiring stronger assumptions compared to PES.
PG methods optimize directly over the parameter space of parametric policces in order to improve a performance function (e.g., the expected return). In RL, addressing the exploration problem is crucial. Agents must try different actions to gather information on long-term outcomes, rather than solely maximizing immediate rewards. In PGs, explo- ration is typically achieved by injecting noise into either the agent's 's actions or the policy parameters. These two exploration strategies are known as action- (AB) and purameter-based (PB) exploration (Metelli et al., 2018), respectively. In particular. AB exploration, whose proto- typical algorithms are REINFORCE (Williams, 1992) and GPOMDP (Baxter & Bartlett, 2001), keeps the exploration at the action level by leveraging stochastic policies (e.g.. Gaussian). Instead, PB approaches, whose prototype is PGPE (Sehnke et al., 2010), explore at the parameter level via stochastic hyperpolicies, used to sample the parameters of an underlying (typically deterministic) policy.
From a theoretical perspective, significant work has focused the convergence guarantees of PG methods, particularly for AB exploration (Zhao et al., 2011; Papini et al., 201 8; Yuan et al., 2022; Fatkhullin et al., 2023; Bhandari & Russo, 2024). However, these methods produce parameters of stochastic (hyper)policies' that often fail to meet reliability, safety, and traceability requirements in real-world applica- tions. The PG literature traditionally addressed learning deterministic policies through deterministic policy gradient algorithms (DPG, Silver et al., 2014), which inspired suc- cessful deep RL methods (e.g., DDPG, Lillicrap et al., 2016; Fujimoto et al., 2018). However, these approaches are inher- ently off-policy and rely on actor-critic architectures. These algorithmic complexities make their convergence guarantees difficult to establish and currently available under demand- ing assumptions only (Xiong et al., 2022).
1. Introduction
Among reinforcement learning (RL, Sutton & Barto, 2018)
approaches. policy gradient (PG, Deisenroth et al., 2013) methods achieved significant success in addressing real- world scenarios thanks to their ability to handle continuous state and action spaces (Peters & Schaal, 2006), resilience to sensor and actuator noise (Gravell et al., 2020), and robust- environments (A (Azizzadenesheli
ness in cartially-observer et al., 2018). Additionally, they enable the incorporation of
Recently, Montenegro et al. (2024) introduced a general framework for assessing last-iterate global convergence to the optimal deterministic policy using stochastic (hy- per)policies. Similarly to much of the PG literature, they
'Politecnico di Milano, Piazza Leonardo Da Vinci 32, 20133, Milan, Italy. Correspondence to: Alessandro Montenegro "alessandro.monnteggroo eotiiiennngo@pllmiii.......
Proceedings of the nrnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
'The term (hyper)policy refers jointly to AB and PB explo- rations.

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
consider the simplest form of exploration that injects noise from white noise distribution (e.g.. zero-mean Gaussian) with static stochasticity parameter a (i.e., fixed throughout learning). By setting a proportional to the desired subop- timality 6, convergence to the optimal deterministic policy is achieved. However, this approach has the drawback of requiring to use a very small a from the sturt of learning. This limits the practicality of static stochasticity methods.
2. White Noise Exploring Policy Gradients
Notation. For a measurable set X. we denote with A(x) the set of probability measures over X. For P A(X), we denote with p its density function. For n, m N with n > m, we denote [[:] == {1, ..... n) and [m, n] = {m, m +
1, .... n). For x IR, we denote (a)+ := (0.
Lipschitz Continuous and Smooth Functions. A function f : X = Rd - R is L Lipischhi continuous (L1-LC) if [[(x) - f(x') & Lı||x x'I2 for every x,x' e X. Similarly, f is Lz-Lipschitz smooth (I-zLL)) if it is contin- uously differentiable and its gradient Vxf is L2-LC, i.e. V fxf(x') & L2|[x x'122 for every x, x' X.
Static stochasticity conflicts with the common practice of dynamically adjusting stochasticity during learning. In AB exploration, deep RL methods (Schulman et al., 2015; Duan et al., 2016) typically address this by jointly optimizing the policy parameters and variance (via a suitable parameteriza- tion) through gradient ascent. Additionally, entropy regular- ization (Haarnoja et al., 2018; Ahmed et al., 2019) further promotes exploration by modifying the reward function to favor more stochastic policies. In PB exploration, Gaus- sian hyperpolicies are often used, with the variance learned alongside the hyperpolicy mean via gradient ascent (e.g., Wierstra et al., 2014; Likmeta et al., 2020).
Markov Decision Processes. The environment is mod- eled as a Markov Decision Process (MDP, Puterman, 1990). An MDP is represented by M == (S, p. T; Po. 7)), where S = Rdds and A = Rd are the measurable state and ac- tion spaces; p S x A A(S) is the transition model, where p(s"|s, a) specifies the probability density of land- ing in state s' E S by playing action a A in state s E S; r S x A - [-Rmaxe Rmax] is the reward function, where r(s, a) specifies the reward the agent gets when playing action a in state 8; Po E ASS) is the initial- state distribution; 7 E [] is the discount factor. A trajectory
Although dynamically adjusting stochasticity has been suc- cessful in practical RL applications, its theoretical under- standing remains limited. This theory-practice gap raises the question: Can PG methods guarantee convergence to the optimal deterministic policy when using dynamic stochas- ticity? In this paper, we answer this question positively.
of length T E N u (+00) is a sequence of T state-action pairs. The discounted return of trajectory T is given by:
(Sr,u. ar,u. 11,
Original Contribution. In this work, we make a step to- wards the theoretical understanding of employing dynamic stochasticity in PGs. The main contributions are:
R(T)
Σ (r((.,,, T-1
In Section 3. we present PES (Phased Exploration Sched- ule), a phase-based algorithm reducing stochasticity through pre-determined schedule across phases, in which a PG subroutine with fixed stochasticity is run. After outlining the convergence conditions for PG subrou- tines in Section 4, we discuss in Section 5 the impact of varying stochasticity on the performance index. Finally, in Section 6, we demonstrate that, under these conditions and gradient domination assumption, PES achieves last- iterate global convergence to the optimal deterministic policy with an (c-5)) sample complexity.
We admit y = 1 only when T < +00.
Deterministic Parametric Policies. We consider a para- metric deterministic policy μ4 :S - A, where 0 s d is the parameter vector belonging to the parameter space O The performance of μ4l is assessed via the ex- pected return JD θ - R, defined as:
E [((T)], ( (1)
where PD(T;; 0) (o((r.)) Ih p( |s.,, (s()).))) is the density of trajectory t induced by policy Mgg The agent's 's goal consists of finding an optimal parameter O e arg max (f) and we denote Jß = (D())
In Section 7, we analyze the convergence for the com- mon practice of jointly learning (hyper)policy parameters and stochasticity, referred to as SL-PG (Stochasticity- Learning Policy Gradient). We show that last-iterate global convergence is achievable with a sample complex- ity of Ō()-),, but stochastic (hyper)policies only and requiring stronger assumptions than PES. We conclude by discussing the possibility of achieving convergence to deterministic policies at the same rate as PF.S.
White Noise Exploration. Similarly to Montenegro et al. (2024), we introduce the notion of white noise that we will employ define white-noise-basee exploration.
Definition 2.1 (White Noise). Let d E N. A family of probability distributions \ c A(Rd) is a white nosse if for every a E Izn:
In Section 9, we numerically validate the proposed algo- rithm. Related work is discussed in Section 8. The proofs of the results are deferred to the appendix.
E c-4-.0
[<]= 0s and
c- [| < do²
Unlike Montenegro et al. (2024), which assumes static
2

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
stochasticity, we consider families of distributions parame- terized by a, referred to as the stochasticity amount. Def- inition 2.1 enables the analysis of algorithms that dynam- ically vary a during learning. This includes, for example, zero-mean Gaussian distributions 6 ~ (Oaa,, A) with A A) & I, where [|]|[|[] = o² tr(A) & da². This noise is assumed to be while across exploration steps.
of every trajectory. Formally, we consider the following definition of white noise hyperpolicies.
Definition (Whhte Noise Hyperpolicies). Let 0 E O a Reo, and μ4g S - be a parametric deterministic policy and let Ddg.o be a white-noise distribution (Def. 2.1). A white noise hyperpolicy Ve, E A(0) is such that, for every parameterization E O, the parameterization O ~ Ve,a satisfies 0' 0 + c, where e ~ Ddg, which is sampled independently for every trajectory.
Action-Based (AB) Exploration. In AB exploration, we consider a parametric stochastic policy To, : - A(A) built upon an underlying deterministic policy μ4o by perturb- ing each action suggested by ert with white-noise random vector. The policy is used to sample actions a, ~ (- played in state s for every step t of interaction. Formally, we consider the following definition of white noise policies.
This definition justifies the name for PB exploration, since the exploration carried out at the parameter level. Note that, differently from AB exploration, in PB one, before starting to collect each trajectory, the current parametriza- tion for the deterministic policy 0 is perturbed with noise vector e ~ 4 di then the deterministic policy Ho+e is used for the entire trajectory. From now on, we focus on this kind of stochastic hyperpolicies, calling a the stochasticity amount for Vo.a-
Definition 2.2 (White Noise Policies). Let 0 E O, 0 Ry0 and pao S A be a parametric deterministic policy and let Da be a white noise distribution (Def. 2. A white noise policy na.a : S - ((A) is such that, for every state s E S, the action a ~ Te (-1s) satisfies a = ps(s) + e, where e ~ Da which sampled independently at every step (i.e., whenever an action is sampled).
The performance index of ve.a is Jp : θ x R=0 R, that is the expectation over O' of JD(0") defined as:
Jp(0,
E [Jb(0']-
This definition justifies the name for AB exploration since the exploration is carried out at the action level. From now on, we refer to this kind of stochastic policies, calling a the stochasticity amount of ne.a.
0r-vo.-
Whenever a > 0, PB exploration aims learning 0% (ar arg maXgee Jp(0, o). If Jp(0, о) is differentiable w.r.t. O. PGPE (Sehnke et al., 2010) updates the hyperparameter O by gradient ascent: 0.+1 - O, + (o (0) PGPE uses an estimator of VoJr(O, o) which employs N inde- pendent parameter-traaector pairs {(0,, m))) collected with hyperpolicy V8.a. that is, 0, ~ 1/, and 7. ~ pD(: 0,). Also in this case, N is called batch size. More details on PB exploration are presented in Appendix B.
The performance of To. is assessed via the expected return JA θ x R500 R., defined as:
(0 == E
[R(T)],
(-p)
being (T 0) the density of trajectory t induced by me.a- In AB exploration, whenever a > O, we aim to learn (a) E arg max a)) Given a (0, a) differ- entiable w.r.t. 0, PG methods (Peters & Schaal, 2008) update the parameter O via gradient ascent: 0.+1
Exploration-Agnostie Framework. In this work, we con- sider both AB and PB explorations and present the re- sults using a unified notation. We define J. with t e (P, A} as the aggnootiion-agnostic objective and (a) e arg maxg.e J4(0, a) as the corresponding optimal parame- terization for a given stochasticity amount σ. This notation is also applied to other quantities, mapped their respective exploration (either AB or PB) in Appendix C.
0, + &. (V,,)( where Se > 0 is the step size and (o,A σ) is an estimator of VoJa(0. In particular, we consider the GPOMDP estimator (Baxter & Bartlett, 2001) which employs N independent trajectories (Ta) collected with policy Te,a (i.e., Ti PA(:; O)), where N is called batch size. In this paper, we just consider GPOMDP, since REINFORCE, which is conceptually similar, suffers from larger variance (Williams, 1992; Baxter & Bartlett, 2001). More details on AB exploration are presented in Appendix B.
3. PES: Algorithm Description
In this section, we present Phased Exploration Schedule (PES) a phase-based algorithm with PG subroutines which aims to output deterministic policy. The algorithm, whose pseudo-code is presented in Algorithm 1, in each phase p E [0, P - 1] runs PB or an AB policy gradient method (i.e., a PG subroutine) with a fixed stochasticity amount op to learn in K, iterations a parameterization Op starting from the output of the previous phase, 6p-1-
Parameter-Bass (PB) Exploration. In PB exploration, we use a parametric stochastic hyperpolicy v0.- E A(O) built upon an underlying deterministic policy μeg by perturb- ing the parameter vector with a white-noise random vector. The hyperpolicy is used to sample parameters 6' ~ Va.a to be plugged in the deterministic policy par at the beginning
When starting a new phase, PES updates the stochasticity
3

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
Algorithm 1 PES.
Assumptions for PG Subroutines Convergence. Mon- tenegro et al. (2024) show that ensure last-iterate global convergence of PG subroutine with fixed stochasticity op. the objective J+(;, (p)) has to fulfill three properties: (i) smoothness of Jf(s, (p) w.r.t. 0, (fi) weak gradient domi- nation (WGD) on Jp(:.0p) w.r.t. 0, and (iti) bounded vari- ance of the employed estimator. This set of assumptions is standard in the PG convergence literature (Papini et al., 2018; 8; Agarwal et al., 2021; Yuan al., 2022; Fatkhullin et al., 2023; Bhandari & Russo, 2024). In our dynamic exploration scenario, we need such conditions to hold for every oy. Condition (i) holds for both Jp and JA for every exploration amount Op under the following assumption.
Input :Number of phases P. Iterations per phase (K,) Initial parameter 0, Stochasticity schodule (o,))==, Learning rate schedule (G))E1. Batch size NV
Initialize 0g -
for p E [P] do
0, < Run for Kp iterations PB or AB PG from O,- with fixed stochasticity Ty. learning rate Sp. batch size N
end
Retur 0p
according to a decreasing deterministic schedule. This al- lows the algorithm begin with high stochasticity max aiding in the discovery of a good parameterization l,. and then gradually reduces σ. As we will show, this process ensures that the final parameterization 0p-1 is nearly opti- mal for the final stochasticity Op-1, which can be set to the desired suboptimality c for deterministic policy deployment. This approach avoids the issues of using a fixed stochasticity of c, as discussed in Section
Assumption 4.1 (Jn is L2-LS w.r.t. O). There exists L2 R30 such that for every 0 E Rde, the following holds:
V Jn(0)2 $ L2.
Indeed, the smoothness of JD w.r.t. the parameter 0 is inherited by the stochastic objectives.
In particular, PES employs the following deterministic schedule to update the stochasticity:
Lemma 4.1 (J+ Inherited Smoothness). Under Assump- tion 4. for every O E θ and a Rz0, it holds:
pp max (p- 1)-",
(V, & Lz2
with max y E R2.0 and p E [0. P- 1]. As we shall discuss later, this choice, besides fulfilling the previously mentioned desiderata, enables last-iterate convergence guarantees to the optimal deterministic policy.
Condition (ii) can be inherited by both J/p and JA under the assumption that WGD holds for JD-
Assumption 4.2 (WGD on JD). There exist op > 0 and Sp 2 0 such that, for every 0 E θ the following holds:
Theoretical Motivation. From a theoretical perspective, since each PG subroutine is run with a fixed exploration amount p. under appropriate assumptions, following (Mon- tenegro et al., 2024), it is possible to assess the sample complexity NK, (i.e., the number of trajectories needed for phase p) to ensure global last-iterate convergence of J+(:,ap) op) to desired accuracy
J - (D) < ap (e + Sp.
We highlight that, if 3p O. then we are in the presence of the so-called strong gradient domination, meaning that the objective Jp has no local optima. When 3p > 0, WGD holds and Jn may admit local optima. Before showing the WGD inheritance, we need introduce further assumption the MDP and μ4 regularity, needed for the AB case.
J+ (op), - (l,,(Op, E
recalling that the optimal (hyper)policy parameterization 0* (a)) depends on the stochasticity itself. As we will show, by (i) using the PES deterministic schedule for stochasticity op and (ii) satisfying the conditions for last-iterate conver- gence of each PG subroutine, it suffices to determine the number of phases P ensure convergence to determinis- tie policy. Before presenting PES' last-iterate convergence guarantees the optimal deterministic policy (Sec. 6), we first outline the assumptions required for state-of-the last-iterate convergence of PG subroutines (Sec. 4) and then examine the impact of reducing stochasticity on J+ (Sec. 5).
Assumption 4.3 (MDP and pa Regularity). Let 8, s' S. The log transition model log (p(s'(ss') is Lp-LC and L2,p" LS, and the reward function r(s.-) is L,-LC and L2, w.E.t. the action. Moreover, the deterministic policy pe((s) is L.y-I.C and - w.r.f. its parameters.
Further details for this assumption are provided in Ap- pendix D. Next, we show the inheritance of WGD properties by JA and Jp.
Theorem 4.2 (Inherited WGD for Jr. Montenegro et al. 2024). Considering a (hyper)policy complying with Defi- nitions 2.2 or 2.3, under Assumptions 4.2 and 4.3.for any RS0 and 0 E θ the following holds:
4. PG Subroutines Convergence
In this section, we recall the assumptions needed to guaran- tee state-of-the-art last-iterate convergence results for each PG subroutine of P3S. A more detailed discussion is pre- sented in Appendix D.
11(0" ()),a) (, )) & V (0,(0))) (000)))22 Br(a),
with (4 := 9D + WYo, for some W3 > 0.
Notice that the multiplier op of the norm of the gradient

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
that of Assumption 4.2, whereas the term (+(a) acquires dependence on the exploration amount
sumptions 4.1, 4.2, 4.3, and 4.4, by selecting an appropriate constant step size Ep and a sample complexity N K satisfy- ing:
Remark 4.1 (When does WGD hold?). We remark that the WGD property depends on both the policy parameteriza- tion class and the environment. For instance, Bhandari & Russo (2024) show that, for AB exploration in tabular envi- ronments and using natural policy parameterizations, the Lojysa--jjsiiiiiz (PL) condition holds. This is a stronger condition than WGD, requiring JA (o) - J,(0,a) & ( for some Rz00 Moreover, Mei et al. (2020) show that, for AB exploration in tabular environ- ments and using softmax policy parameterization, i.e., To.o(a (a 8) 8)x exp(@(ss a)), the WGD property holds for JA with BA- = 0. Finally, Ding et al. (2022) prove a more general result, still in the context of AB exploration, show- ing that WGD holds whenever: (i) the Fisher informa- tion matrix induced by the policy To. is non-degenerate for every O E O i.e., F(O,o) = E. (Vo log To (a s) Vo log Te,-(a s) Z I for some po > 0; and (ii) a "compatible function approximation bias" is upper bounded by Ebiar- Under these conditions, WGD holds on JA with constants OA = GPF and Ba = =(1=(11- (1->-1) Webuas where G is such that Vo log To [a s)]l2 & G. Finding a hyperpolicy class that induces WGD on Jr, in the sense of (Ding et al., 2022), remains an open problem.
(
a (obLav10)
NK Ö
then (O0), o ap)l c 3,(op)) where the notation (-) hides logarithmic terms.
In Section 6, we will use the assumptions and the results presented in this section to ensure the convergence of each PG subroutine, and study the convergence of the whole phased process of PES to the optimal deterministic policy.
5. The Effects of Dynamic Stochasticity
In this section, we diseuss the effects on J+ when varying the stochasticity Specifically, we seek to understand under which assumptions a small variation of the stochasticity a attains a small variation of the expected return J+(,, Intuitively, this is a minimal requirement for the design of algorithms like PES aiming to dynamically change the stochasticity during the learning process.
As highlighted in Section 2, we recall that the optimal (hy- per)policy parameterization 0* (a) depends on the stochas- ticity itself, i..., (a)) E arg max J (0,0))
Finally, condition (iit), requiring the variance of the estima- tor (0,, σr) to be bounded, is granted by the following assumption on the scores of the stochastic (hyper)policy.
Assumptions. Before presenting the results, we introduce regularity assumptions on the deterministic objective Jp. The following assumption, needed in the analysis of the PB case, requires the Jn to be LC in the policy parameters.
Assumption 4.4 (Bounded Scores). Let &d A (IR)) be white-noise distribution complying with Definition 2.1 with a Rx and density Qá.0- &d.a is differentiable in its argument and there exists a constant c >> 0 such that:
Assumption 5.1 (Jn is Ly-Lipschitz w.r.t. 0). Jn is Lr- Lipschitz w.r.t. parameterization 0, i.e. for every 0, 0' O:
jJ - JD(0')) & T, 0'1|2-
E. 22,0
[/ log $ ( & eda
i
E ? log da (e) & c
For analyzing the AB case, we need a similar assumption on the non-stationary (NS) deterministic objective. Let c (et)T= 4 2 be a sequence of independently sampled noise vectors. Let ft (1) be NS deterministic policy, where, at time step / the deterministic policy 14 S - A is played, with μ4 = p4 + E,. The objective for this kind of policy is (1) = Er- uب [R(])] where (T(()))) is the density of a trajectory T induced by the NS policy.
As an example, this assumption is fulfilled by zero-mean Gaussian noise e ~ NN(O,, A). Under such an assumption, the variance of the estimator (o,+ a) is bounded.
Lemma 4.3 (Bounded Estimator Variance). Considering a (hyper)policy complying with Definitions 2.2 (PB) or 2.3 (AB), under Assumptions 4.3 and 4.4 the following holds:
Assumption 5.2 (Ju is LI -Lipschitz w.r.t. μ)). The per- formance Jo of the NS deterministic policy ps is E- Lipschitz w.r.t. the non stationary policy, for every p.
Vi.0 No2'
for some Vi.0 20 O.
PG Subroutines Convergence. Under the assumptions discussed so far, a PG subroutine with fixed stochasticity op enjoys the following convergence guarantee.
T L sup (((()) (1(())22
(Jا( - Jo((z') &
Σ
1=
seS
Theorem 4.4 (PG Global Ltst-Iterate Convergence, Mon- tenegro et al. 2024). Consider running for K₂ iterations a PG algorithm with a (hyper)policy satisfying Definitions 2.2 or 2.3 with an exploration amount ap E Ry Under As-
Moreover, we denote I Et= L.
In the following, we consider (hyper)policies complying with Definitions 2.2 (PB) or 2.3 (AB). Unfortunately, this,
5

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
combined with the assumptions presented above, is not enough to ensure the desired regularity, shown in Exam- ple 5.1.
ity amounts (points (ii)-(iii).
6. PES: Convergence
Example 5.1. Consider one-state MDP with 1=1-1, r(a) max a). T = 1, and constant deterministic pol- icy, = 0. fulfilling Assumptions 5.1 and 5.2. We consider the following white noise, fulfiliing Definition 2.1:
In this section, we demonstrate that PES achieves last-iterate convergence guarantees to the globally optimal determinis- tic policy. Specifically, we require that each PG subroutine p E [[o, P - 1], run under a stochasticity op. exhibits last- iterate convergence to the optimal (hyper)policy 0, with suboptimality i..., J (0*
_ + 50
ifo <σ
11 =
Uniform (I-v3o, V30])
otherwise
(0 (op). op) (pp+ op)] & e.
where o > O. We compute the expected return, which is just the expected reward, in our case:
Given the decreasing deterministic schedule employed by PES, if these guarantees are satisfied, the algorithm en- sures that the next phase is initialized with an c-optimal parameterization from the previous phase. This allows us to leverage the results of Theorem 5.1 control the perfor- mance loss when switching from phase p to phase p. i.., J+ (op), J((0p-1.0p)
ifo<D
J(o)
2
33 Jo
otherwise
4
We immediately observe that (o) is discontinuous in the point T.
Thus, we introduce the following assumption that ensures form of regularity in the way the noise is generated.
Given the convergence of PG subroutines at each phase (The- orem 4.4) and the regularity of the objective Jn with respect to stochasticity (Theorem 5.1), we just need to carefully select the number of phases P to establish the last-iterate convergence of PES to the optimal deterministic policy.
Assumption 5.3 (Scale-invariant Noise). Let { be a family of white noise distributions (Def. 2.1). For every E R let c ~ az and 22,1- It holds that: _ oe, where" D denotes equality in distribution.
Theorem 6.1 (PES Convergence). Employing a (hy- per)policy complying with Definitions 2.2 (PB) or 2.3 (AB), under Assumptions 5.1 (PB) or 5.2 (AB), 5.3, and under the assumptions for the convergence of PG subroutines (Sec. 4), if PES is run for P (e/Omax) parameterization 0p is such that:
Assumption 5.3 establishes that we can generate the noise random variable associated with a certain stochastic- ity by generating a noise random variable e associated with a conventional stochasticity (e.g.. 1, but other choices are possible) and multiplying the variable by a. This as- sumption is fulfilled, for instance, by zero-mean Gaussian distributions (O2,, o² A). In particular, under Assump- tion 5.3, for any stochasticity a and function y. it holds E []()))] This represents the key observation to prove that the expected return J+(,, or) is LC w.r.t. the stochasticity a, and subsequent results on the optimal performance, as illustrated in the following theorem.
phases, the output
J [[JD((Pp-)]] (1 + 2D, + WAje + 3D. with a sample complexity:
L2 +
NK δ
6
that E.- [g(e]] [c(e).,[
where K EP- Kp.
Notice that, by setting the number of phases P (e/dmax) we set the final stochasticity ap-1 In Theorem 6.1, we recover the Ō(e=5) rate of Montenegro et al. (2024) for last-iterate convergence to the optimal deter- ministic policy, with fixed stochasticity amount c. As highlighted in Section I, keeping a static stochasticity a as small as e has practical limitations. Instead, PES takes ad- vantage of scaling the exploration amount op at each phase and starting from a good parameterization for the previous exploration amount ap-1- These benefits will be further discussed in Section 9.
Theorem 5.1. If the (hyper)policy complies with Defini- tions 2.2 (PB) or 2.3 (AB), under Assumptions 5.1 (PB) or 5.2 (AB), and Assumption 5.3, for every 0 E O and 01, 02 E Rgo, it holds that:
(1) - (+() < D+l01 - 02l
(i) (((0 & 2D+ 0z2
(ii) [J((0%(r)), - 1, 02) (z))))))) & D+ - 02 where t E (P.A), DA LI..VT. and Dp Lyvde, des
Moreover, the convergence results of PES highlight a trade- off between the parameters Taax and y. Specifically, maax controls the stochasticity of the first phase and the number of phases required to output the optimal deterministic policy. A large value of Tmax makes PES to learn starting from a highly stochastic objective, requiring more phases to con-
Theorem 5.1 will be crucial for establishing the convergence guarantees of PES. Indeed, besides bounding the loss when varying the stochasticity a while keeping the same param- eterization 0 (point (i)), it also quantifies the distance in expected return between optima under different stochastic-
6

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
verge, while small max needs less phases converge, but limits the range of the stochasticity. Furthermore, y determines the number of phases and the smoothness of the schedule. A small value of y results in a large number of phases P, making the reduction of stochasticity smoother.
(0T,E) as the joint parameteriza- tion, SL-PG aims to optimize the objective J+(() == ((,))(()) by updating the parameterization dk via stochastic gradient ascent Uk++1 - Us + 6g (vv)).
Considering
where 6% 0 is a step size and V..)(.) is an unbiased estimator of V. (e.g. GPOMDP for AB and PGPE for PB) computed from a batch of N trajectories.
Finally, by plugging the constants for PB (f = P) or AB (f A) exploration into the results of Theorem 6.1, we recover the standard trade-off's between the two exploration strategies (see Metelli et al., 2018). Specifically, PB ex- ploration suffers from high-dimensional parameterizations (i.e., large de), while AB struggles with long-lasting inter- actions with the environment and with high-dimensional action spaces (i.e., large T and d'A)
Convergence Conditions. We anticipate that SL-PG ex- hibits last-iterate convergence guarantees to the optimal stochastic (hyper)policy characterized by a joint param- eterization v* E arg max J+()). We also denote J = J.(+). To achieve such guarantees, we need similar conditions to the ones required for the convergence of PGs with fixed stochasticity (Section 4). In particular, the ob- jective J+(v) has to fulfill three properties: (i) smoothness of J+(+) w.r.t. V, (it) weak gradient domination (WGD) of J+(+) w.r.t. V, and (iti) bounded variance of the gra- dient estimator. To ensure these properties for the joint parametrization v if the conditions of Section 4 hold for the parametrization O (with fixed σ), we only need to guarantee analogous conditions for the parameter Ç.
Remark 6.1 (On employing Hessian-aided PG subroutines). We remark that the PG subroutines used within PES are not limited to vanilla PG methods, as considered in this paper. For instance, one could employ Hessian-aidee al- gorithms such as HARPG ( (Fatkhullin et al., 2023), which enjoy faster last- isst-iterate global convergence guarantees of order Ō(e= In our setling, this translates into a rate of Ö(-2a- when using a fixed a, due to the bound on the policy scores (Assumption 4.4), which scales O(o=²). 2). As a consequence, PES with HARPG converges to the optimal deterministic policy with a sample complexity of Ö(E improving upon our current result at the cost of relying on PG subroutines that incorporate Hessian information.
Condition (i) requires an additional assumption on the smoothness of the deterministic objective with respect to the NS policy, which is necessary for the AB case due to the inherent nature of this type of exploration.
Assumption 7.2 ( (Jb is L w.r.t. μ)) The performance Jn of the non-stationary deterministic policy is (T2,)) T-1 LC in the non-stationary policy, i.e., for every
7. SL-PG: Convergence Analysis
evverry μs pt::
In this section, we discuss the convergence of PG methods jointly learning parameters I and stochasticity a (via suit- able parameterization {) of (hyper)policies. From now on, we refer to this common practice as SL-PG (Stochasticity- Learning Policy Gradients). As discussed in Section 1, this approach has proven to be very successful in practical sce- narios (Schulman et al., 2015; Duan et al., 2016; Likmeta et al., 2020), since it potentially allows PGs to adapt the stochasticity level to exit from local optima when needed. However, the literature on PG convergence guarantees only considers a static stochasticity (Yuan et al., 2022; Bhandari & Russo, 2024; Montenegro et al., 2024).
- voJolel) <
Σ Lupsup |[((s) - (4())) BES
Furthermore, we denote Lz := 2i= L2
Then, condition (i) is inherited from the deterministic ob- jective by both Jp and JA. establishing, in addition to Lemma 4.1, that (+(O, ((E) is L1g,--LC and LLS w.r.t.
& (details in Appendix G).
Lemma 7.1 (Je is LLC and L2t.5-LS w.n.t E). Under Assumptions 4.1, 5.1, 5.2, 7.1, and 7.2 it holds that:
Ô ((E, ~5
62 π
SL-PG learns, in addition to the (hyper)policy parameters 0, certain scalar parameterization & E R.. of a e R2 employ- ing a stockasticity mapping function f R + [aminn ma with minn maa E R2., to map & to o as a =((). To as- sess the convergence of SL-PG, the stochasticity mapping function f has to fulfill the following condition.
< Livge and
J, (0, & L2r.e
When Lemmas 4.1 and 7.1 hold, then [VzJ(())] < L L2t.5 + L2-
To meet condition (it). we introduce directly WGD on J w.r.t. the optimization variable v.
Assumption 7.1 (f Regularity). There exist L,, > 0 and L2,, 20 such that, for every Eι, E2 E IR, we have:
Assumption 7.3 (WGD on Jr w.n.t v). There exist au > 0
If((E) - f({z)] < Li.rkE E21, a
and 3o 2 O such that, for every e Rdd++1 it holds:
- J((v) < av V V By.
25 25 ((()
25 f(2) & 12,1151 - Ezl-
7

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
Notice that the meaning of this assumption is the same
PES vs. SL-PG. SL-PG is similar to PES in its dynamic handling of stochasticity a, but instead of following fixed decreasing schedule, it adapts o, potentially aiding in es- caping local optima. However, this adaptability requires stronger assumptions. In practice, PES may also get stuck in local optima if parameters y and Kp are not chosen care- fully. While PES offers theoretical guarantees on perfor- mance loss when deploying a deterministic policy, SL-PG provides no such assurance, the convergence behavior of remains an open problem without additional assumptions. These aspects will be further discussed in Section 9.
of Assumption 4.2 explained in Section 4. Moreover, in Appendix G, we demonstrate that this can be inherited by other assumptions and results introduced previously.
Finally, condition (iit) holds for both JA and Jp under the same assumptions needed for the boundedness of the vari- ance of V ( r). In particular, we have the following result on the boundedness of the variance of (4,,
Lemma 7.2 (Bounded Jr0 f(E)). the (hyperipolicy satisfees Definitions 2.2 or 2.3, under Assumptions 4.4 and 5.3, using an exploration mapping f()) fulfilling As- sumption 7.1, for any parameterization &, it holds that: V4. (1 & NN(())²'
8. Related Work
In this section, we discuss related work on convergence rates. Further related literature is provided in Appendix A.
The convergence of PGs to stationary points at rate of O(c")) has been known at least since the work of Sutton et al. (1999). However, the recent analysis by Yuan et al. (2022) and Montenegro et al. (2024) provide further clarifi- cation on key aspects and required assumptions. Faster vari- ants of REINFORCE, leveraging stochastic variance reduc- tion techniques, were introduced much later (Papini et al., 2018; Xu et al., 2019). These methods achieved improved convergence rates, with the ((-33) rate of (Xu et al., 2020) now considered optimal, supported by lower bounds from non-convex stochastic optimization (Arjevani et al., 2023). The same optimality applies to second-order methods (Shen et al., 2019; Arjevani et al., 2020). While the convergence propenties of PGPE are similar to those of PG, they have received comparatively less attention. Notably, (Xu et al., 2020) proved the Oee rate for variance-reduced ver- sion of PGPE. More recently, the focus has shifted toward studying the global convergence of PG to optimal policies under additional assumptions. Pioneering works in this di- rection include Scherrer Geist (2014), Fazel et al. (2018), and Bhandari & Russo (2024). These works introduced the concept of gradient domination (also known as the Polyak- Lojasiewicz condition), which has a long-standing history in optimization (Lojasiewicz, 1963; Polyak, 1963; Karimi et al., 2016). Several studies have analyzed the iteration complexity of PG with exact gradients for specific policy classes, such as softmax or direct tabular parametrization, where gradient domination is guaranteed (c.g., Agarwal et al., 2021; Mei et al., 2020: Li al., 2021). An exception is the sample-based natural policy gradient, which has been studied for general smooth policies (Agarwal et al., 2021). Regarding vanilla sample-based PG (e.g., GPOMDP), Liu et al. (2020) were the first to investigate its sample complex- ity for global optimality. They also introduced the concept of Fisher-non sather--o--degneercay (Ding et al., 2022), enabling the use of gradient domination for broader class of policies. Under weaker assumptions, Yuan et al. (2022) and Mon-
Then, the variance of (o)+()) is bounded by (V+.0 (())) (further details in Appendix G).
Convergence Results. We now study the last-iterate con- vergence of SL-PG to the optimal stochastic (hyper)policy, characterized by a total parameterization u*
Theorem 7.3 ISL-PG Convergence), the (hyperipolicy satisfies Definitions 2.2 or 2.3, under Assumptions 4.1, 4.3, 4.4, 5.1 (PB) or 5.2 (AB), 5.3, 7.1, 7.2, and 7.3, running SL-PG for K iterations, with a suitable constant choice for the learning rate 8n the oulput purameterization UK is such that:
- [[+ & c + Bo,
with total sample complexity of:
NK= = δ ( 16 (602)L2),,D11100
cd02 Puin
where L27,0 L2 + L2t.8 and V4.0 == 14.00 + V4.5-
It is worth noticing that, under more demanding assump- tions of the ones reported in Section 4, we recover the same rate of Theorem 4.4 for what concerns the last-iterate con- vergence to the optimal stochastic (hyper)policy. More- over, in Appendix G, we recover the same result without of Assumption 7.3. However, if one wants to recover the convergence guarantees to the optimal deterministic pol- icy by employing the result of Theorem 5.1, one has to assume that all the c-optiall stochastic (hyper))pliciess are such that they have a stochasticity of at most c, i.e., [+x]]] & e + Br = ок = -[Ex) & Oe)). Then, would be possible to employ a stochasticity mapping f such that amin c, recovering the same rate Oc of PES for last-iterate deterministic convergence, being sure that the learned stochasticity f({x) would be at most 6.
Also in this case, by plugging into the results of Theorem 7.3 the constants for PB (f = P) or AB (t = A) exploration, we recover the usual trade-offs between the two paradigms.
8

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
PRF-A
managed by the Adam (Kingma & Ba, 2014) optimizer.
SL-FF 712-0
0.4
For both PB and AB, present PES with two different schedules, both starting with = 1. The first (A) schedule consists of P = 25 phases. each lasting Kp = 200 itera- tions, with a schedule exponent of = 1. The second (B) schedule includes = 5000 phases, each lasting K = 1 iteration, with a schedule exponent of y = 0.5. SL-PG is ex- ecuted for K 5000 iterations, using the common exponen- tial parameterization for o (i.e., et). The static stochas- ticity counterparts are also run for K 5000 iterations, em- ploying stochasticity levels E {1. 0.5, 0.04, 0.014). Here, o 1 represents the maximum stochasticity in the PES schedules, while o = 0.04 and o = 0.014 correspond to the minima of the first and second PESS schedules, respectively.
0.4
5L-7G
201
782- B
0.4
0.5
0.04
11
0.013
1.000
2,000
3,0000
6.000)
3,000
1,000
2,000
3,000
4.000
5.000
Itanction
Beraatin
(a) Parameter-based.
FRB A
51-70
01.8
782-8 B
20
0.4-
0.2
Parameter-based Figure la shows that PES-B outper- forms the other methods in convergence to optimal per- formance, while presenting a similar behavior to SL-PG. PES-A shows a slower convergence due to the longer phases length. For the deterministic deployment PES-A, mimick- ing what prescribed by theory, scores a higher performance w.r.t. PES-B, showing similar results SL-PG (Tab. 1).
1000
2,000
2000
4.000
5,000
1,000
2,000
3,000
4,000
5,000
Bieniion
Donation
(b) bction-based.
Figure 1. Jt and behavior for and AB Swimmer-v5 (5 runs, mean +95% C.I.)
Method
PB
Ap
AB
AA
Aaaion- This pattern does not hold under AB. Fig- ure lb shows the main drawback of PES, consisting of the possibility of getting stuck in local optima when Kp does not suffice. This is avoided by SL-PG, which has the ability to adapt a to face this situation. This can be noticed also in deterministic deployment scores (Tab. 1).
PES-A
1.1
-0.12
28.93
9.89
0.44
SL-PG
61.43 1.733
-021
49.83 + 13.38
- 1.19
PFS-B
60.40 + 2.31
-0.27
29.24 + 8.74
0.33
Table 1. Deterministic deployment performance (5 runs over 100
traeectories, mean + std). A (b()x) ) (0x).
Final σ. In general, while the final stochasticity of PES controlled by the imposed schedule, the final stochasticity of SL PG is unknown until the end of the learning process, as it is learned via stochastic gradient ascent. This has the effect that the loss incurred when switching off the noise is smaller w.r.t. that incurred when using SL-PG (Tab. I).
tenegro et al. (2024) achieved an improved Ö() sample complexity. More sophisticated methods, such as variance- reduced approaches, have pushed the sample complexity further. The current state of the art is (Fatkhullin et al., 2023), achieving Ö(E -2.5) for Hessian-free methods and Ö(E for second-order algorithms, with the latter being optimal up to logarithmic terms (Azar et al., 2013). In the case of Gaussian policies, all the aforementioned works implicitly assume that covariance parameters remain fixed.
10. Conclusion
This work studied last-iterate convergence guarantees for PGs with dynamic stochasticity, bridging theory and prac- tice. We introduced PES, a phase-based approach that deter- ministically scales down stochasticity, enjoying last-iterate convergence to the optimal deterministic policy with a rate of Ö(c-5), Additionally, we analyzed the common practice of jointly learning (hyper)policy parameters and stochas- ticity, showing its last-iterate convergence to the optimal stochastic (hyper)policy with rate of Ō(-330_ under stronger assumptions than PES. Future work should further narrow the theory-practin gap by exploring guarantees for single-iteration phases (i.c., K, = 1 for all p), relaxing as- sumptions for SL-PG convergence, and analyzing the learn- ing dynamics of the stochasticity value in SL-PG. More- over, it would be interesting determine SL-PG conver- gence employing stochasticity mapping f letting 0.
9. Experiments
In this section, we numerically validate the presented re- sults. Additional details and experiments are provided in Appendix H.2 Here, we analyze the behavior of PES and SL-PG in both AB and PB explorations, comparing them with their static stochasticity counterparts (GPOMDP and PGPE). We conduct the evaluations in the Swimmer-vS envi- ronment, part of the MuJoCo (Todorov et al., 2012) control suite, using a horizon of T = 200. All learning rates are
'The code is available at https: http:///tthubbbhooo

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
Impact Statement
Bolland, A., Louppe, G., and Erist, D. Policy gradient algo-
rithms implicitly optimize by continuation. Transactions Machine Learning Research, 2023.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Deisenroth, M. P. and Rasmussen, C. E. PILCO: A model- based and data-efficient approach to policy search. In Proceedings of the International Conference on Machine Learning (ICML), pp. 465-472. Omnipress, 2011.
Acknowledgments
Deisenroth, M. P., Neumann, G., and Peters, J. A survey on policy search for robotics. Foundations and Trends in Robotics, (1-2):11-433 2013.
Funded by the European Union - Next Generation EU within the project NRPP M4C2, Investment 1.3 DD. 341 15 March 2022- FAIR Future Artificial Intelligence Research Spoke 4 PE00000013 DS3C22002380006
Ding, Y., Zhang, J., and Lavaei, J. On the global optimum policy gradient. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 151 of Proceedings of Ma- chine Learning Research, pp. 1910-1934. PMLR, 2022.
convergence of momentum-
References
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98);1-76, 2021.
Duan, Y., Chen, X., Houthooft, R., Schulman, J., and Abbeel, P. Benchmarking deep reinforcement learn- ing for continuous control. In Proceedings of the In- ternational Conference Machine Learning (ICML), pp. 1329-1338. PMLR, 2016.
Ahmed, Z., Le Roux, N., Norouzi, M., and Schuurmans, D. Understanding the impact of entropy on policy optimiza- tion. In Proceedings of the International Conference on Machine Learning (ICML), pp. 151-160. PMLR, 2019.
Fatkhullin, I., Barakat, A., Kireeva, A., and He, N. Stochas- tic policy gradient methods: Improved sample complexity for fisher-non leteer-oon-eegee non-deeenerate policies. Proceedings of the International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Re- search, pp. 9827-9869. PMLR, 2023.
Allgower, E. L. and Georg, K. Numerical continuation methods- an introduction, volume 13 of Springer series in computational mathematics. Springer, 1990.
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Sekhari, A., and Sridharan, K. Second-order information non- convex stochastic optimization: Power and limitations. In Proceedings of the Annual Conference on Learning Theory (COLT), volume 125 of Proceedings of Machine Learning Research, pp. 242-29929999 299. PMLR, 2020.
Fazel, M., Ge, R., Kakade, S. M., and Mesbahi, M. Global convergence of policy gradient methods for the linear quadratic regulator. In Proceedings of the International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pp. 1466- 1475. PMLR, 2018
Arjevani, Y. Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B. E. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199 (1):165-211) 214, 2023.
Fujimoto, S., van Hoof, H., and Meger, D. Addressing function approximation error in actor-critic methods. In Proceedings of the International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pp. 1582-1591. PMLR, 2018.
Azar, M. G., Munos, R., and Kappen, H. J. Minimax PAC bounds on the sample complexity of reinforcement leam- ing with a generative model. Machine Learning, 91)3): 325-349, 2013.
Ghavamzadeh, M. and Engel, Y. Bayesian policy gradient algorithms. Advances in Neural Information Processing Systems (NeurIPS), 19, 2006.
Azizzadenesheli K., Yue, Y., and Anandkumar, A. Policy gradient in partially observable environments: Approximation and convergence. arXiv preprint arXiv:1810.07900. 2018
Gravell, B., Esfahani, P. M., and Summers, T. Learning optimal controllers for linear systems with multiplicative noise via policy gradient. IEEE Transactions on Auto- matic Control, 66 1):22335228. 2020.
Baxter, J. and Bartlett, L.
gradiett
Haarooja, T., Zhou, A., Abbeel, P., and Levine, S. Soft actor- critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proceedings of the International Conference on Machine Learning (ICML), pp. 1861-1870. PMLR, 2018
estimation. Journal of Artificial Intelligence Research, 15:319-350, 2001.
Bhandari, and Russo, D. Global optimality guarantees for policy gradient methods. Operations Research, 2024.
10

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
Karimi, H., Nutini, J., and Schmidt, M. Linear conver- gence of gradient and proximal-gradien methods under the balyykk-oojsiewicce condition. In Machine Learning and Knowledge Discovery in Databases: European Con- ference (ECMI. PKDD), pp. 795-811. Springer, 2016.
In AAAI Conference on Artificial Intelligence (AAAT), pp. 8958 8966. AAAI Press, 2021.
Mobahi, H. and Fisher, J. W. On the link between gaussian homotopy continuation and convex envelopes. In Energy Minimization Methods in Computer Vision and Pattern Recognition, pp. 43-56. Springer, 2015.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv: 14XXxi:141..69800 2014.
Montenegro, A., Mussi, M., Metelli, A. M., and Papini, M. Learning optimal deterministic policies with stochastic policy gradients. In Proceedings of the International Conference on Machine Learning (ICML), volume 235 of Proceedings of Machine Learning Research, pp. 36160- 36211. PMLR, 2024.
Lee, J. C. and Valiant, P. Optimizing star-convex functions. In IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 603-614. IEEE, 2016.
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. Softmax policy gradient methods can take exponential time to converge. In Proceedings of the Annual Conference on Learning Theory (COLT), volume 134 of Proceedings of Machine Learning Research, pp. 3107-3110. PMLR, 2021.
Papini, M., Binaghi, D., Canonaco, G., Pirotta, M., and Restelli, M. Stochastic variance-reduced policy gradi- ent. In Proceedings of the International Conference on Machine Learning (ICML., volume 80 of Proceedings of Machine Learning Research, pp. 4023 4032. PMLR, 2018.
Likmeta, A., Metelli, A. M., Tirinzoni, A., Giol, R., Restelli, M., and Romano, Combining reinforcement learning with rule-based controllers for transparent and general decision-makiin in autonomous driving. Robotics and Autonomous Systems, 131:103568, 2020.
Papini, M., Battistello, A., and Restelli, M. Balancing learning speed and stability in policy gradient via adaptive exploration. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pp.
Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. Continuous con- trol with deep reinforcement learning. In International Conference on Learning Representations (ICLR), 2016.
1188-1199 PMLR, 2020.
Papini, M., Pirotta, M., and Restelli, M. Smoothing policies and safe policy gradients. Machine Learning. 111(11): 4031-4137, 2022.
Liu, Y., Zhang, K., Basar, T., and Yin, W. An improved analysis of (variance-reduced) policy gradient and nat- ural policy gradient methods. In Advances in Neural Information Processing Systems (NeurlPS), 2020.
Peters, J. and Schaal, S. Policy gradient methods for robotics. In IEEE International Conference on Intelligent Robots and Systems, pp. 2219-2225. IEEE, 2006.
Lojasiewicz, S. Une propriété topologique des sous- ensembles analytiques réels. Les équations aux dérivées partielles, 11:877889, 1963.
Peters, and Schaal, S. Reinforcement learning of motor skills with policy gradients. Neural Networks, 21): 682-697,4 2008
Mei, J., Xiao, C., Szepesvári, C., and Schuurmans, D. On the global convergence rates of softmax policy gradient methods. In Proceedings of the International Confer- ence on Machine Learning (ICML), volume 119 of Pro- ceedings of Machine Learning Research, pp. 6820-6829. PMLR, 2020.
Polyak, B. T. Gradient methods for minimizing functionals. USSR Computational Mathematics and Mathematical Physies, 3(4):643-6) -533, 1963.
Puterman, M. L. Markov decision processes. Handbooks in operations research and management science, 2:331-4364 1990.
Metelli, A. M., Papini, M., Faccio, F., and Restelli, M. Pol- icy optimization via importance sampling. In Advances in Neural Information Processing Systems (NeurIPS), pp- 5447-5459, 2018
Saleh, F., Ghaffari, S., Bretl, T., and West, M. Truly de- terministic policy optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Metelli, A. M., Papini, M., Montali, N., and Restelli, M.
Scherrer, B. and Geist, M. Local policy search in a convex space and conservative policy iteration as boosted policy search. In Machine Learning and Knowledge Discovery in Databases: European Conference (ECML PKDD), volume 8726 of Lecture Notes in Computer Science, pp. 35-50. Springer, 2014.
Importance sampling techniques for policy optimization. Journal of Machine Learning Research, 21:141:1-111:75 2020.
Metelli, A. M., Papini, M., D'oro, P., and Restelli, M. Policy optimization as online learning with mediator feedback.

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
Schulman, J., Levine, S., Abbeel, P., Jordan, M. I., and Moritz, P. Trust region policy optimization. In Proceed- ings of the International Conference Machine Learn- ing (ICML), volume 37 of JMLR Workshop and Confer- ence Proceedings, pp. 1889-1897.. J.I..orgg 2015.
Xu, P., Gao, E., and Gu, Q. An improved convergence analysis of stochastic aariance-reduced policy gradient. In Uncertainty in Artificial Intelligence (UAI), volume 115 of Proceedings of Machine Learning Research, pp. 541-551 AUAI Press, 2019.
Schwefel, H.-P. P. Evolution and optimum seeking: the sixth generation. John Wiley & Sons, Inc., 1993.
Xu, P., Gao, F., and Gu, Q. Sample efficient policy gradient methods with recursive variance reduction. In Interna- tional Conference on Learning Representations (ICLR), OpenReview.net, 2020.
Sehnke, F., Osendorfer, C., Rtcckstieß, T., Graves, A., Pe- ters, J.. and Schmidhuber, J. Parameter-exploring pol- icy gradients. Neural Networks, 23(4):551-555 2010. International Conference on Artificial Neural Networks (ICANN).
Yuan, R., Gower, R. M., and Lazaric, A. A general sample complexity analysis of vanilla policy gradient. In Proceed- ings of International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 3332-3380, PMLR, 2022.
Shani, L.., Efroni, Y., and Mannor, Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In AAAI, pp. 5668 5675. AAAI Press, 2020.
Zhao, T., Hachiya, H., Niu, G., and Sugiyama, M. Anal- ysis and improvement of policy gradient estimation. In Advances in Neural Information Processing Systems (NeurIPS), pp. 262-270, 2011.
Shen, Z., Ribeiro, A., Hassani, H., Qian, H., and Mi, C. Hessian aided policy gradient. In Proceedings of the International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pp. 5729-5738. PMLR, 2019.
Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D., and Riedmiller, M. Deterministic policy gradient algo- rithms. In Proceedings of the International Conference on Machine Learning (ICML), pp. 387-395. PMLR, 2014.
Sutton, R. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018.
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. Advances in Neural Information Processing Systems (NeurIPS), 12, 1999.
Todorov, E., Erez, T., and Tassa, Y. Mujoco: A physics engine for mosel-based control. In IEEE/RSJ interna- tional conference on intelligent robots and systems, pp- 5026-5033. IEEE, 2012.
Wierstra, D., Schaul, T., Glasmachers, T., Sun, Y., Peters, J., and Schmidhuber, J. Natural evolution strategies. Journal of Machine Learning Research, 15(1):949-98 980, 2014.
Williams, J. Simple statistical madient-following algo- rithms for connectionist reinforcement learning. Machine Learning, 8:229-255 -256, 1992.
Xiong, H., Xu, T., Zhao, L.., Liang. Y., and Zhang, W. De- terministic policy gradient: Convergence analysis. In Uncertainty in Artificial Intelligence (UAI), volume 180 of Proceedings of Machine Learning Research, pp. 2159- 2169. PMLR, 2022.
12

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
A. Additional Related Work
In this appendix, we discuss additional related work w.r.t. the literature on convergence rates, discussed in Section 8.
Deterministic Policies. Value-based RL algorithms, such as Q-learning, naturally deliver deterministic policies as their final solution. In contrast, most PG methods are designed to search within the space of non-degenerate stochastic policies. As noted by Sutton et al. (1999), this characteristic is often seen as an advantage rather than a limitation, as the optimal policy is frequently stochastic in partially observable environments. The ability to deploy deterministic policies is one of the key advantages of PGPE and related evolutionary techniques (Schwefel, 1993; Wierstra et al., 2014), as well as model-based approaches like PILCO (Deisenroth & Rasmussen, 2011). In the domain of action- policy search, the Deterministic Policy Gradient (DPG) algorithm introduced by Silver et al. (2014) was the first to explicitly focus on searching in the space of deterministic policies. Unlike PGPE, DPG uses stochastic policies during the learning process for exploration,simin similarly to value-based methods, while largely ignoring distribution mismatch caused by off off-policy sampling. Despite this, DPG served as the foundation for popular deep RL algorithms, including (Lillicrap et al., 2016; Fujimoto et al., 2018). In (Xiong et al., 2022), the convergence of on-policy DPG (fully deterministic) to a stationary point was established with sample complexity of order *). However, their analysis relies on an explorability assumption (Asm. 4 in their paper), which is standard for stochastic policies but very demanding for deterministic ones. A more practical approach to achieving fully deterministic DPG was proposed by Salch et al. (2022), who also discuss the benefits of deterministic policies. As expected, fully deterministic learning only feasible under strong assumptions about the regularity of the environment. Recently, (Montenegro et al., 2024) consider for both parameter-based and action-based PGs the more common scenario of evaluating stochastic policies at training time, only to deploy good deterministic policy in the end. The authors show that, under weak gradient dominance assumptions, this practice enjoys last-iterate global convergence guarantees to the optimal deterministic policy with rate of order Ö(e=²), requiring to maintain fixed right from the beginning of the learning process the (hyper)policy variance at a quantity which is (c), limiting the practicality of this approach.
Policy Variance. When optimizing Gaussian policies using policy-gradient methods, the scale parameters (such as the variance or, more generally, the covariance matrix of the policy) are often assumed to be fixed in theoretical analyses but are typically optimized via gradient descent in practice. To the best of our knowledge, there is no comprehensive theory addressing the impact of varying policy (or hyperpolicy) variance the convergence rates of PGs. Ahmed et al. (2019) were among the first to seriously examine how policy stochasticity influences the geometry of the objective function, although their focus was on entropy regularization. Papini et al. (2020) addressed the issue from a different point of view, proposing the use of second-order information to avoid the greediness of gradient updates, which they argue is particularly problematic for scale parameters. Their work emphasizes monotonic improvement rather than convergence guarantees. Bolland et al. (2023) and Mobahi & Fisher (2015) studied PG with Gaussian policies through the framework of optimization by continuation (Allgower & Georg, 1990), treating the process as a sequence of smoothed versions of the deterministic policy optimization problem. Unfortunately, the theoretical foundation for optimization by continuation remains sparse, even if this approach presents similarities with our proposal PES. It is important to note that the common practice of learning (Wierstra et al., 2014; Schulman et al., 2015; Duan et al., 2016; Likmeta et al., 2020) the exploration parameters alongside the other policy parameters invalidates all known convergence results for GPOMDP. This is because the smoothness of the stochastic objective is inversely proportional to the policy variance (Papini et al., 2022). In contrast, entropy- ruguoay-regllarived policy optimization is better analyzed through mirror descent theory rather than traditional stochastic gradient descent theory (Shani et al., 2020).
Comparing AB and PB Exploration. A foundational work on this topic is the paper by Zhao al. (2011), which provides upper bounds on the variance of the REINFORCE and PGPE estimators. Their analysis highlights the better dependence of PGPE on the task horizon compared to REINFORCE. The idea that variance reduction alone does not fully capture the efficiency of policy gradient methods has emerged more recently (A (Ahmed et al., 2019). Montenegro et al. (2024) revisited the comparison between action- -asee (AB) and parameter-based (PB) methods through the lens of modern sample complexity theory, arriving at similar conclusions but offering, in our view, more comprehensive understanding of the subject. Another set of works that extensively compares AB and PB exploration includes (Metelli et al., 2018: 2020; 2021). These studies analyze the trade-off between the task horizon and the number of policy parameters, both theoretically and experimentally, but in the specific context of trust-region methods.
13

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
B. Stochastic Policy Gradients
Deterministic Parametric Policies. We consider a parametric deterministic policy pe : - A, where 0 E θ = Rda the parameter vector belonging to the parameter space θ The performance of μo assessed via the expected return Jp θ IR, defined as:
JD(0)= = E T-po(-10)
[R(T)],
where
T-1 IT t=0
PD[T: 0) == po
p( (8,1 (S(,))))
is the density of trajectory I induced by policy 14g- arg max (0) and we denote J == (0))
The agent's goal consists of finding an optimal parameter 0
White Noise Exploration. As it is standard for papers concerning PG convergence (Papini et al., 2018; Yuan et al., 2022; Fatkhullin et al., 2023), in this paper consider white-noise- nosse-based undirected exploration. As discussed in Montenegro et al. (2024), this kind of exploration is just characterization of stochastic (hyper)policies which is particularly intuitive when one has to deal with selecting the exploration amount. Before formally defining action-based and parameter-based exploration, we provide preliminary definition of white noise.
Definition B.1 (White Noise), Let d N and > probability distribution Pd,a E A(R)) a white noise if:
[ = 022 and em-BR.
E
E e~aaa
[[e|[]] & do
Definition 2.1 includes also zero-mean gaussian distributions é (O,, 2.) where Ee-,((,,
tr(x)) < do²
Note that the noise is intended to be white among different time (or iteration) steps, while the noise vector for a particular realization may not be white. For instance, the distribution at hand Gaussian, it may be non-isotropic. Moreover, in principle is possible to employ different white noise distributions throughout the exploration steps.
Action-Based (AB) Exploration. In AB exploration, we consider a parametric stochastic policy Tp S A(A), where P E P = Rd is the parameter vector. The policy is used to sample actions a, < to be played in state 8, for every step t of interaction. Stochastic policies Tp can be considered as built upon an underlying deterministic policy μe (over the same parameter space θ), by perturbing each action suggested by μi with a white-noise random vector. Formally, we consider the following definition of white noise policies:
Definition B.2 (White noise policies). Let O E O, a > and μ4a S - A be parametric deterministic policy and let dá be white noise distribution compliant with Definition 2.1. A white noise policy Te S A(A) is such that, for every state s e S, the action a ~ (-(s( satisfies a (s(s) + c, where e Dd which is sampled independently at every step (i.e., whenever an action is sampled).
Note that (1) policy complying with Definition 2.2 is a standard stochastic policy and (ii) this definition of white noise policy justifies the name for AB exploration, since the exploration is carried out at the action level. From on, we refer to this kind of stochastic policies, referring to as the exploration amount for T
The performance of To is assessed via the expected return JA 1 R - R. defined as:
JA (0,
E
[R(T)]
T-PA1-10)
where
T-1
Pa(T; (o(().0)
To (0:
is the density of trajectory induced by policy me.a-
Given that we consider white-noise policies, another definition of JA is possible. Let μa (H)T_O be stationay deterministic policy, where, at time step / the deterministic policy μ4 : S - A is played. The objective for this kind of policy is (D(H)= = Eo- (- (n) [.]]], with (D(T(m) = Pu(*7,0) I p(5 (s).))) Now, let = (et)T= D7 be
a sequence of independently sampled noise vectors. We can denote no + E (no + a) Thus, the AB performance
14

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
index be expressed as:
Jx(0,0)
E E
[Jb(μo + =
In AB exploration, whenever a O, we aim learn (a) E arg max JA (0 o). JA (0, differentiable w.r.t. O, PG methods (Peters & Schaal, 2008) update the parameter 0 via gradient ascent: 0 - O₂ + G (0,, where > is the step size and VeJa(0,o)) is an estimator of Va. In particular, the GPOMDP estimator (Baxter & Bartlett, 2001) is:
N ME
(0))(0,0)= N
Σ
Ve log no. (2s.))))..))) 7 "rss,,,,
where N is the number of independent trajectories (T:) collected with policy T0.o (T; pa(:; called batch size. In this paper, we just consider GPOMDP, and we will not present REINFORCE, given that these two solutions are conceptually similar, and the estimator considered in the latter suffers from larger variance (Williams, 1992; Baxter & Bartlett, 2001).
Parameter-Basee (PB) Exploration. PB exploration, we use a parametric stochastic hyperpolicy up E (0)), where P S Rd is the parameter vector. The hyperpolicy used to sample parameters ~ "p to be plugged in the deterministic policy μo at the beginning of every irajectory. As for the case, stochastic hyperpolicies Up can be considered as built upon an underlying deterministic policy μe (over the same parameter space θ). by perturbing the parameter vector 0 with white-noise random vector. Formally, consider the following definition of white noise hyperpolicies:
Definition B.3 (White noise hyperpolicies). Let 0 E O a O, and pa - A be parametric deterministic policy and let dde.o be white-noise distribution compliant with Definition 2.1. A white noise hyperpolicy V8,o A(O) is such that, for every parameterization 0 E θ, the parameterization 6' Vo.a satisfies O' = 0 + where e ~ &d which is sampled independently at every trajectory.
Also in this case, (i) a hyperpolicy complying with Definition 2.3 is standard stochastic hyperpolicy and (ii) this definition of white noise hyperpolicy justifies the name for PB exploration, since the exploration is carried out at the parameter level. is worth noticing that, differently from what happens AB exploration. in PB exploration, before starting to collect each trajectory, the current parametrization for the deterministic policy perturbed with a noise vector a (a), then the deterministic policy po+e used for the entire trajectory. From now on, we focus on this kind of stochastic hyperpolicies, referring to the exploration amount for V8.a-
The performance index of vo.a is Jp Rdd R - IR, that is the expectation over 0' of JD(0") defined as:
Jp(0, = E [JD(O']]
0'-22g0
Leveraging on the definition of white noise hyperpolicy, we can provide the following additional definition for the PB performance index Jp:
Jp(0.
E [b + +)] e-
Whenever > 0, PB exploration aims learning (a) arg maX (p. If J))0, is differentiable w.r.t. PGPE (Sehnke et al., 2010) updates the hyperparameter by gradient ascent: 0 - 0, + (o PGPE uses an estimator of V Jp0,0 a) defined as:
N Vo log Uo v0. (0,)
vo = N
where the butch size N is the number of independent parameter-trnjectory pairs (0,, T.) collected with hyperpolicy 1/,.s that is, 0, ~ v and Tę ~ PD(:;0)).
15

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
C. Exploration Mapping Quantities
In this section, we present a mapping table of various quantities, often expressed in their exploration-agnostic form along this work, the specific expression they have the Parameter-baset and Action-based exploration paradigms.
Constant
Parameter-based
Action-based
D,
Ljvde
LINVVA
W
aDlavde, + Lyvdø
ADVVVA + LLAVVA
I2. Ruass cde N(1-7)2
ed N(1-7}3
V4.0
Lit
L.gl,,vVo
I I.
L2t.s
L2 + L
12 TdA TdA + LI
Lists
L2hn./Vda
L2ghI,/Vdd
Re Annredlle L. N11-91
R Re
Vt.s
N(1-7)²
As can be noticed from the table, there is a trade-off between PB and AB explorations, as already highlighted in previous works (Metelli et al., 2018; Montenegro et al., 2024). Indeed, PB exploration may suffer from large parameterizations (i.e., de large), while AB exploration may suffer from long-lasting interactions with the environment and from highly- dimensioned actions spaces (i.e., T d large). In particular, for AB exploration, when we are in an infinite horizon setting (i.e., 7 and T +00) we identify the length of trajectory with the effective horizon T ((1((1 This approximation only affects logarithmic terms in the sample complexity (Yuan et al., 2022).
16

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
D. Details the Convergence of PG Subroutines
As highlighted in Section 4, order guarantee last-iterate global convergence of PG subroutine employing a (hyper)policy complying with Definitions 2.2 and 2.3 with J+(0,0) σ) w.r.t. 0, (ii) WGD on J+(0, w.r.t. 0, and (tix) bounded variance of the estimator (o,+(0,
exploration amount, three conditions are needed: (i) smoothness of
D.I. Inherited Smoothness
The smoothness of Jp and JA is simply inherited by the smoothness of Jp.
Lemma 4.1 (J+ Inherited Smoothness). Under Assumption 4. for every 0 and a E Rz0, it holds;
(V & L2.
Proof. See Lemmas D.3 and D.7 by Montenegro et al. (2024).
D.2. Inherited Weak Gradient Domination
WGD on Jp and JA can be inherited by WGD on JD. with additional characterization of the MDP and the deterministic policy μi. Such an assumption, that has already been stated in the main paper (Asm 4.3), rewritten here in Assumptions D. and D.2 for the sake of rigor and clarity.
Assumption D.1 (MDP Regularity). The log transition model log logp(s'|s; (. -) is T-p-IC and I22,-1LS, and the reward function r(s,)) is LC and LLS w.r.. the action for every s, S, te..foor every a' E A:
logp(s'{ss, a) log p(s'(s a')l & Lplla a'l2
IV (lsgp(s'la a) V. logp's'sss,'"))
L aaa--a1 a'12
[n(s, a) r(s, a')l < Lr a'l2
[|r(s, a) - r(s, a' )[2 & T2, la a- a'12-
Assumption D.2 (ng Regularity). The deterministic policy (e(s) is L, LC and 2 w.r. parameter for every s S, fer every 0, 6' O:
(HO()) (8) & 1 0'
(o)o(s) - Velor & 12 0 0'1
Under Assumptions D.I and D.2, WGD can be inherited by Jp and JA when also Assumption 4.2 holds (i.e., WGD on Jn w.r.t. 0). We stress that these two assumptions are needed for the AB case. Thus, they are unavoidable when one wants to consider an exploration-agun aggossic setting.
Theorem 4.2 (Inherited WGD for J,. Montenegro al. 2024). Considering a (hyperipolicy complying with Definitions 2.2 or 2.3, under Assumptions 4.2 and 4.3, any E R=00 and 0 O, the following holds:
Jj (0*()))))0) o0, anl (oJ4(0, (r(a),
with (+(o) = 3p W4,, for some W 0.
Proof. See Theorems 7.1 and 7.2 by Montenegro et al. (2024).
For what concerns the quantity 8y(a) 3D Wio, have the following mapping to PB and AB explorations:
PB: Wp up La de L.ydo:
AB: WA = aDuvdA LVdd, with vi = ((11)))-4) In particular:
Ri + (LpLp + Rmax 12,p + Lg bybr + L2,r (1-7)4
$ = L,
(1 (1-72).
(1 71-
1-7)
as can be seen in Lemma D.11 by Montenegro et al. (2024).
17

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
D.3. Bounded Variance of the Estimators
Lemma 4.3 (Bounded Estimator Variance). Considering (hyper)policy complying with Definitions 2.2 (PB) or 2.3 (AB), under Assumptions 4.3 and 4.4 the following holds:
Var Var(voJ+(0.o)) < V+.0
for some some V4.0 2 O.
No2
Proof. See Lemmas D.2 and D.6 by Montenegro et al. (2024).
It is worth noticing that for PB exploration with hyperpolicy complying with Definition 2.3, it suffices to be under Assumption 4.4 to obtain the result of Lemma 4.3.
D.4. PG Global Last-Iterate Convergence
Theorem 4.4 (PG Global Last-lterate Convergence, Montenegro et al. 2024). Consider running for Kp iterations PG algorithm with a (hyperipolicy satisfying Definitions 2.2 or 2.3 with an exploration amount E RR Under Assumptions 4.1, 4.2, 4.3, and 4.4, by selecting an appropriate constant step size Sp and sample complexity Kp satisfying:
(obL2V1.
NK, > Ō
-007
then - < Bt(op)) where the notation Ō()) hides logarithmic terms.
Proof. This result follows directly from Theorem 6.1 by Montenegro et al. (2024). However, in the original result, the term op2 is hidden inside the variance bound term. here, we explicitly show it because we need to take care of the dependence on the specific exploration amount since we have to consider be dynamic.
18

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
E. Proofs of Section 5
Theorem 5.1. If the (hyper)policy complies with Definitions 2.2 (PB) or 2.3 (AB), under Assumptions 5.1 (PB) or 5.2 (AB), and Assumption for every 0 and ,2 02 R30, it holds that:
(1) [J((0, - J,(0, & D+j01 02l
(i) (
2D - 02l
(iii) (1((0())). 1, (0* (02), 02)l & Dy 02
where & E (P.A), DA In Lv and Dp Lyvde-
Proof. To prove result (i), we have consider the specific exploration strategies exploit the additional noise characteriza- tion provided by Assumption 5.3.
Result (i): bassed Jp(0, .)
The objective Jp has the form:
E engag o
[Jr(O + c,
E
[JD(O + c)]
(2)
Bdgg
for any parameterization 0 O and exploration amount Rso-
Thus, we have the following:
(r(0, Jr(0,
(3)
E
[JD(O + 61]
E
[Jb(O E2)]
(4)
e2 0d
Since are under Assumption 5.3, write the following:
[Jr(0, 01) Jz(),
(5)
[Jr(O + 016) Jn( o23)]
(6)
[]b(0 016) - Jp + o
(7)
where we applied Jensen's 's inequality. By applying Assumption 5.1, we obtain:
(p(0,a)) - Jp(0,
(8)
E
[[ + σ1ē) Jp + o2č]]
(9)
$ T.
E
[|0 o 0 - σ2ē 2
(10)
LJ
E
(11)
& LJ
E
| 02t 2
2
(12)
LJ V2
E
|a]] (02 - 02)
(13)
$ T. dela: 02),
(14)
where we applied the Cauchy-Schwartz inequality and Definition 2.1.
Result (i): Action- The proof for this point is similar to the one for result (1) (PB). Here, we express JA
JA (0,
Joly + +
(15)
5
for every parameterization e θ and exploration amount a E +
19

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
Since are under Assumption 5.3, we can write the following (with little abuse of notation):
(0, - 02)]
(16)
JolLLo + +
E
JoliA + E0)
(17)
d4.09
By applying Assumption 5.1, we obtain:
[Ja - J2)(
(18)
E 6- Hail
JolIy + - + 025)
(19)
E
JOlHH + +IE)) - Jo(H1 + +22
(20)
where we employed Jensen's inequality.
Now, by applying Assumption 5.2, we obtain:
(0,
(21)
E
JolLg +15) Jblu, + 025
(22)
E-OT
dail
T-1
E
Σ 1-0
L sup aES
44 + + - 1o
(g(s) (8) - 020
(23)
8- dail
2
T4
E
[ - 226
(24)
L
E
|o
0
(25)
< L d
(26)
where we applied the Cauchy-Schward inequality and Definition 2.1
Result (M.. Here, we exploit the result (i). In particular, we sum and subtract the quantity (+ o2), and then we
exploit the fact that (0 (o2), 02) & (a1)), 02). We start by summing and subtracting the quantity J, (0)())))0)) 02).
- ((0
(27)
-()
(28)
J( = (0))
(29)
Now, we exploit the fact that Jj (1(0) J (1000
- ((()))))((000)))))))))))))))))))
(30)
< J (1)) (0 (0)) + + (00 -200)))0)))))))) (12),
(31)
Now, we apply twice result (i), obtaining:
(40)))))(00))))0)) < 2D
(32)
Result (iii). To prove this result, we separately consider the cases in which (+10) > (02)) or (, (1)),a)) & oz2).
In the first case, we consider
> (=00
Thus, we have what follows:
(())))
(33)
= -1)0(())))))-11(((1111))) 11(0"))))))
(34)
= --100(())))))11((1101)))))))))))
11(0 + (,(00(r)), 02) (02))
(35)
20
20

---

Convergence of Policy Gradient Methods with Dynamic Stochasticity
(36)
Now, we use result (t). obtaining:
The remaining case is (100))))) (1000 & Dyloi - 02).
(37)
With a similar result, we have:
oz)) - J(((0
(38)
= -12(0(02))))) =1)
(39)
-12) -1)(0) +
-10
(40)
<0
(420) (12)).
(41)
As for the previous case, result (i), obtaining:
J1 (22), -()(0)))) & Dyloi 02
(42)
21

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
PES
i
Ko 0o
0
00
K1
01
OP-1
0p-2
Kp-1
Pp-1
Figure Graphical representation of FES.
F. Proofs of Section 6
Theorem 6.1 (PES Convergence). Employing (hyperipolicy complying with Definitions 2.2 (PB) or 2.3 (AB), under Assumptions 5.1 (PB) or 5.2 (AB), 5.3, and under the assumptions for the convergence of PG subroutines (Sec. 4), if PES is run for P = (e/omax) -1/9 phases, the outpul parameterization 0p-1 is such that:
JØ - [[JD(PP-)]] & 2D, + Wi)e+ + BD.
with sample complexity:
[2azVV10022 + W+)
NK > δ
where K = -EP Kp.
Proof. Outline. To asses the converge of PES need apply:
Theorem F.1 by Montenegro et al. (2024) to every phase p [0 - 1] to ensure the last-iterate global convergence to the pth phase's optimum:
Theorem 5.1 to quantify the distance between (1 (op), - B[J+(Op-1,,
each time we initialize a phase
with the output of the preceding one. To use this theorem, we need to be under Assumptions 5.1 (PB) or 5.2 (AB) and Assumption 5.3. Moreover, the employed (hyper)policy has to compliant with Definitions 2.2 and 2.3.
In the following, we 0 indicate the initialization for the parameters and we define 0 0.
Convergence of PG Subroutines. In order to apply Montenegro al. (Theorem F.1, 2024) every phase p [0 P- 1]] the following conditions must hold:
The objective Jt(:,ap) has to be L2-LS w.r.t. the parameterization 0. This is obtained under Assumption 4.1 (Lemma 4.1); WGD holds for (+( w.r.t. O. Under Assumption 4.2 and other regularity assumptions on the deterministic policy and on the MDP (see Appendix D), this can be obtained (Thr. 4.2) as:
(10") - (0, o,) < ap Lap/Vee a + (t(ap),
with (T(o,) = 9D + Whop:
Bounded variance of estimators, which obtained under Assumption 4.4 and other regularity assumptions on deterministic policy and the MDP (see Appendix D and Lemma 4.3) as:
V4.0 No
Varl op)]
We recall that the constant Vi does not depend on the quantity reported in Lemma 4.3.
Being in a generic phase E [[O, P - 1]. we can apply Theorem F.1 by Montenegro et al. (2024) to assess the minimum number of iterations K, needed to ensure last-iterate global convergence of the 7t PG subroutine. In particular, running the subroutine with a constant learning rate
No
(43)
L2
22

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
for Kp iterations such that
Kp 160 L2V1.0 log Ne
3x(ap))*
(44)
e
then the output parameterization Op is such that
J+(0 B(p- [p)] -((1
< B+(pp)
(45)
Total Iteration Complexity. The total amount of iterations don by PES is given by:
P-1
K= Σ
(46)
1=0
By requiring each step size Si to satisfy Equation (43) and K, to satisfy Equation (44), then each PG subroutine enjoys last-iterate convergence guarantees as Equation (45). Thus, we can require the following condition on K:
K
=
K
(47)
1-0
P-1
Ko +
Σ
K:
(48)
160g 1,2 log
(J+(0*( maxx) - mmax) (0 )
(49)
Ne
16a L.vo oo
log
(50)
By construction of PES, and by the fact that each PG subroutine enjoys last-iterate convergence guarantees, we can quantify Indeed, except for the first phase i O, we have:
the term (a;)) o5) [;) - (a.).
(4(a;)
(51)
< (1(0)0))) - -[1((0,1,,,1-1]] - --1l=-
(52)
< (110))))) - ((100))))) + Dylo,
- o,-1l + + - 224 0--l + - (0-10-1- o.) +
(53)
(54)
(o,)),
(55)
where we employed Theorem 5.1, we considered that PES employs a non-inereasing d; schedule, and we exploited the fact that each final parameterization of each phase satisfies Equation (45).
Moreover, since ()t) fp + Woo,, we have the following:
1 (a.), o.) (0_1,, - 3a(a,) & (2D+ WA)(o-1- +
(56)
Exploiting this last result, can enforce stronger but simpler condition to hold for K:
16 log (J+ (F mmax) - J+(0,, mmax) - By (Fmaa))
K3
(57)
Ne max
16a L V.. log 1 (20, + MA) -1)(0-1-05)) o.l) Ne
(58)
Now, considering the specific a; schedule employed by PES, we have that:
0:-1 o; maa (i (i + 1) 1)-
(59)
thus recovering the following condition on the iteration complexity:
16afL2V4
log (J+(0"(Omaz) maxx) - (0, - By (4(omax))
K
(60)
2 max
23

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
16ajL2y N
log (1+ mmxx (2Dx + (i) - (i+ 1)
(61)
Before going on with the proof, we notice that x > log(1 + x) for any x > -1. We shall apply this with x c2 Wa) 1-0 which is positive. In light of this, we enforce even stronger condition to hold for K:
160BL2V1. (J((0((mmx)) maxx) - (+ max)) By (T
K
log
(62)
Ne Max ,2D, + W+) W4)
Σ - (i+
(63)
Ne
11+1)-2
where we also substituted the value o₂ with mix (i 1)2y, given the schedule employed by PES.
Now, we calculate the convergence value of the summation:
(i (VV-(i+)77
(64)
(1+1)-2
((1 (1+1))= -10) i (1+1) V
(65)
$ 2"
((i + 1)0
(66)
i=1
(P - 1) Pd
(67)
This result suggests particular choice for the number of phases P and exponent y. Indeed, we select these quantities such that py Tmax E since this choice leads to ap-1 E. Having made such choice, we can write:
1)+1) (i+1) 2y
2 max
(68)
Considering pa mmax/e, we can require the total iteration complexity to satisfy the even stronger condition:
160 log (J+ (dmax), maxx (O, mmax) 34(( 12,, + WA)
(69)
Neso max
No5
The latter is the number of iterations ensuring, together with the choices of learning rates (5) (Eq. 43), the (o
schedule, and the number of phases P = (c/0max)) -1/y, that the final parameterization satisfies Equation (45):
(((0(()))))))p) (1 < + B+(ar-1).
(70)
In particular, since dp- E, have the following:
J
(71)
-[[(()))))-[[((())---)))))) c St(c).
(72)
Finally, to prove the convergence to deterministic global optimum, we the results of Theorem 5.1:
(c),)) E[J(OP-1,cc] (c), [[Jr(Op-1]] Die
(73)
(74)
(0))
(0)) - Die
(75)
> (0)) -
(76)
All in all, we have:
J - ([D((()))))) & 11+22D,e++ By(c) (1+ 2D, + Wa)e Bp.
(77)
with total sample complexity NK- (6)-))
24

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
G. Proofs of Section 7
G.1. SL-PG Stochasticity Estimators
Here, we present the estimators to update & in SL-PG. It worth noticing that they have a similar form to the ones presented
in Section but the scores of the (hyper)policies has be computed w.r.t. &. In the following, we consider o f(E).
Parameter-based
V Jp(,0,,
N NV
25 -
lo ((T))(TT)
Action-based
(A,,0,)) = # 2 XTT (2%-o
& log ne, aeaaaaaaaaaa (an, 7 /r((s an,))
G.2. Inherited Smoothness of J4 w.r.t the Stochasticity Parameterization
Lemma G.1. (Jp Inherited Smoothness w.r. σ) If the hyperpolicy satisfies Definition 2.3, under Assumptions 4.1 and 5.3, for every f E Rde and a E Rt, the second derivative of Jp w.r.t a is bounded as follows:
δ²
802 00, < daL2.
Proof. Given the fact that the hyperpolicy vo.a satisfies Definition 2.3 and that Assumption 5.3 holds, write the following:
6
0
0))
[Jb(O + re)]
(78)
002
Oa² c- couig
02
JD + σ6)
(79)
e C
da
We now need to apply the chain rule to the term
d02
82
(p oc):
22
i
JD
Jo
oE)
(D +oe)
(80)
d02
d0
do
20 + oE)
v, Jo(n)) 0+oe
(81)
do
(v,, Jo(n)) no
(82)
do
V Jn(n) 1-0+
(83)
Thus, applying the absolute value the quantity follows:
2² Jp0,,o) and recalling that Assumption 4.1 holds, we have what
22
Ø2 ( + σε)
Jp(0,o)
<
E
(84)
202
en
0a
E
T JD JD(n))
(85)
en
[|e12]
E endaag1
(86)
< L2do.
(87)
Lemma G.2. (Jp Inherited Smoothness w.r.t. {) If the hyperpolicy satisfies Definition 2.3, under Assumptions 4.1, 7.1, 5.1,
25

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
and 5.3. every 0 Rdd and R+, the second derivative of Jp w.rdd & is bounded as follows:
0²
(p()
L2P
where L2P.E = L2L2, + L5L2,vVe.
Proof. The proof is similar to the one of Lemma G.I.
We start by exploiting Definition 2.3 and Assumption 5.3:
0²
02
= ((E))
E
[Jb(0 + [())))
(88)
0
85²
2
E
Ju f(E)e)
(89)
2E2
dg
We now need to apply the chain rule the term á²
Jn + f(E)e):
02
6
Ju
f(E)c)
Ju
+(()c)
(90)
8(0 + f(5)))
v Ju(n)) 7 --+
(91)
oc
2
v, Jb( -
((E)
(92)
06
22
(v, Jo(n) -
(f) + vn Jb(n)) f
r(E)
(93)
052
02
e T Jn(n)) o f(Cee
(()2 V, ( 052 (())
(94)
0
Thus, applying the absolute value to the quantity follows:
Jr f()), and considering Assumptions 4.1 and 7.1, we have what
02
S(E))
Jo
(95)
2E2
σ2
E ev
0 (D f(E)e)
(96)
02
& 1n
c V2 Jn( n o+
o5 (()))
+ E eng 1
Vn Jol Jo((n) (
(97)
& L2bli,de + Lyb2,vds
(98)
Lemma G.3. (Jp Inherited LC w.r.t. E) If the hyperpolicy satisfies Definition 2.3, under Assumptions 5.1, 7.1, and 5.3, for every A E R and a R+ the derivative of Jp w.r.t. & is bounded as follows:
I(E) & LIP.s
where Ling = Ly LIIn,yVde.
Proof. The proof is similar to the of Lemma G.2.
We start by exploiting Definition 2.3 and Assumption 5.3:
à
E e
[Jb(0 + [(E)))
(99)
= こ
(D + f(E)
(100)
26

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
We now need to apply the chain rule the term & JD (()))):
a JD + f({)e) = _ Jp 0 + f(E)e)
2
(101)
o
o
a + f(()))
Vn (
(102)
2g
vn J f()).
(103)
Thus, applying the absolute value to the quantity & f(E, and considering Assumptions 5.1 and 7.1, we have what follows:
Or f(E))
(104)
Jn(0 + S(A)e)
<
(105)
enda
& end
Vn, JD((n) o4
((5)
(106)
Elghi.yVee
(107)
Lemma G.4 (Jp Inherited Lipschitz Gradient w.r.t. {). If the hyperpolicy satisfies Definition 2.3, under Assumptions 4.1 and for every 0,, O2 and E R. it holds:
à Jo f(E)) ag
a
Jr ((E) L2y dol0, 02112-
(108)
Proof. Under Assumption 4.1, it holds that:
(VoJb(O,) VoJb((2)1 < L2 02112-
(109)
Under Assumption 5.3, by definition of Jp using hyperpolicy satisfying Definition 2.3, it holds:
f((0 emPag. [Jb(0+ + f({)e)]
(110)
Moreover, by applying the chain rule, we have:
à
à Vn,b(nn)) 1(5) 2 f(E)e.
.p(O,
(111)
Thus, the following derivation holds:
(0, (())
(112)
26
0
0
E
[Jp(O= + f(()))]
E 0E c-
[Jb(02 f(E)E)
(113)
2
c-
1
E
(D S(E)E)
E
JD(2 S(E)E)
(114)
ā
E
(b( f(()e)
Jb
f(E)E)
(115)
é e
2
à
(n( f(E)E)
Jn + S(E)E)
(116)
em 1
2
VnJo(m)) 0===
f(E)E VnTD(122) (p=b( f(S) ह5 (()
(117)
27

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
E 1
(E)
| vn-h(n))==
(118)
05
< L del0, 02112.
(119)
where, in the first inequality, we employed the Jensen's 's inequality, and, for the last passage, we exploited Assumption 4.1.
Lemma G.5. (J4 Inherited Smoothness w.r.t. σ) If the policy satisfies Definition 2.2, under Assumption 7.2 and 5.3, for every 0 Rd and RR+, the second derivative of Ja w.r.t. is bounded as follows:
6²
0o (0,0)) & &ddaL2
Proof. The proof of this lemma follows the same reasoning of the one of Lemma G.I. The only difference is the fact that the noise vector has dimension Td,.-
Indeed, given the fact that the policy Na,a satisfies Definition 2.2 and that Assumption 5.3 holds, can write the following:
6²
6²
(0, = do²
Jo os)
(120)
002
emot
02
Jo2 toe)
(121)
5
We now need to apply the chain rule to the term
d0
82
(D
u oE):
22
ē Jb + +oe)
JoH
oc)
(122)
d02
80 do
A1g + oE
Vn Jo(n)) T-,,-0 -05
(123)
do
vv, Jb(n) (0
(124)
c V Jo(n)
nー tag C.
(125)
Thus, applying the absolute value the quantity follows:
02 20 (20,,0) and recalling that Assumption 7.2 holds, we have what
02
22
&
E
Jn
(14 + +0
(126)
da2
e
E
V2 JD nー too
(127)
e 1
L2
|
(128)
5-OP dAil
& TdA
(129)
Lemma G.6. (Ja Inherited Smoothness w.r.t. {) the policy satisfies Definition 2.2, under Assumption 7.2, 7.1, 5.2, and 5.3, for every gds and a E R+, the second derivative of JA w.r.t & is bounded as follows:
02
ō (A, F(E)
< L2
where Tax. T22 T2, In Ia
Proof. The proof of this lemma follows the same reasoning of the one of Lemma G.2. The only difference is the fact that the noise vector has dimension Td. as shown also in the proof of Lemma G.5.
28

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
Indeed, given that (() and that / satisfies Assumption 7.1, and given the fact that the policy me, satisfies Definition 2.2 and that Assumption 5.3 holds, write the following:
6²
6²
((())
E
JolU, f(E)e)
(130)
2
ev#
02
Jul + f(()
(131)
252
We now need to apply the chain rule the term
2ς J [(E)E):
0²
a
Jolno
[(E))
Jo + +((EE)
(132)
252
a
aH + f(E)
vn Jn ( n--
(133)
06
a
v, Jb(n) n- +(E
_
à
f(E)E)
(134)
6²
e v2 T
Jp(n)
~- f(5) c 05
f()) + Vn Jo(n))nu, +S(E) a5 f(E).
(135)
Thus, applying the absolute value to the quantity (0, and recalling that Assumptions 7.2 and 5.2 hold, we have what follows:
a²
(O.
(136)
0
02
ōg2 JolHI + f(()
(137)
111l
2²
f V Jb(n) Jo(n)) n= + 1e'e oe f(5)
+
E C-07 dail
Vn Jo(n) Jb(n)) +[(()e - c रहअ f(E)
(138)
5- 11.1
p L L TdA
(139)
Lemma G.7. (JA Inherited w.r.& E) the policy satisfies Definition 2.2, under Assumption 5.2, 7.1, and 5.3, every 0 e Rdd and R+, the derivative of JA w.r.t & bounded as follows:
Ja(0,f(E)
LIn.
a
where LIAEE = In
Proof. The proof of this lemma follows the same reasoning of the one of Lemma G.3. The only difference is in the fact that the noise vector has dimension TdA. shown also in the proof of Lemma G.5.
Indeed, given that = f() and that f satisfies Assumption 7.1, and given the fact that the policy ne.- satisfies Definition 2.2 and that Assumption 5.3 holds, we can write the following:
((E)
E
Jolly + (())
(140)
o g
E
Jo {(E)))
(141)
2
We now need to apply the chain rule to the term
JolHy + f(E)e):
â
Ju f(E)c)
Jolm, f(()c
(142)
ag
a
29

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity i(4 + f(()))
Vn Jo(n)) Jo(n))nn1, +/10l
(143)
Vn Jo(n)) ( - 05
(()
(144)
Thus, applying the absolute value to the quantity à follows:
ag JA(O, f(E)), and recalling that Assumption 5.2 holds, we have what
(A f(E))
(145)
E
JD(Ho f(E)e)
(146)
e A:1
o5
a Vn JD(n)) n- ((0) o
E
f(E)
(147)
ex 2,11
(148)
Lemma G.8 (Ja Inherited Lipschitz Gradient w.r.t. {). If the policy satisfies Definition 2.2, under Assumptions 7.2 and 7.1,
for every 0 02 ④ and & R, it holds:
JA (010 f(E) a
JA J2 f(E) & Ln Tdal 02112.
(149)
a
Proof. The proof of this lemma follows the same reasoning of the one of Lemma G.8. The only difference is in the fact that the noise vector has dimension Tdl as shown also in the proof of Lemma G.5.
Under Assumption 5.3, by definition of JA using a hyperpolicy satisfying Definition 2.2, it holds:
(A, = ل diيl
Jo f(t)e)
(150)
Moreover, by applying the chain rule, we have:
à S(E)) vnnb(n))nngg n-2 +((5) ह
_ (()e.
(151)
Thus, the following derivation holds:
JA (01. JA (2. (A(
(152)
o
E OE
JOlHO + +f(E)e]
E oc enty
Jolme + f(()e)
(153)
JolHo + +(()))
JolHu, + +((E)e)
(154)
o
0 f(E)e (n>D((e))mmmp, +s(E)e a f(E)E
Vn-o(m)))) -o, +f(8)e o
(155)
f(E) 2
|el2 (n -H, +/[Sie
VnDD( - Mag + +(E))e
(156)
2
T A 0
Ozl2:
(157)
where, in the first inequality, we employed the Jensen's inequality, and, for the last passage, we exploited Assumption 7.2. Lemma 7.1 (Je is Lit.-LCC and L2t.5 w.r.t {). Under Assumptions 4.1. 5.1, 5.2, 7.1, and 7.2 holds that:
82 (())
((E) & Lit,e and
Lzrge-
30

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
Proof. This lemma is the ensemble of Lemmas G.6, G.7, G.2, and G.3.
Lemma G99 (J, Inherited Lipschitz Gradient w.r.t. {). If the (hyperipolicy satisfies Definition 2.2 (AB) or 2.3 (PB), under Assumptions 4.1 and 7.1, for every 0,, 2 O and & e R, it holds that:
(((O,,((E)) 6
J+ (+( & Listsl1e -02112-
o
Proof. This lemma is the ensemble of Lemmas G.4 and G.8.
G.3. Bounded Variance of the Estimators V J., f(E))
Lemma G.10 (Bounded Hyperpolicy Scores). If the hyperpolicy Vo.a satisfies Definition 2.3, under Assumption 5.3 and 4.4 and using an exploration mapping function f(-) such that Assumption 7.1 is fulfilled, then the following holds:
a
log vo (00)
& cd 10,
o
where o = f(E).
Proof. From Definition 2.3 and from Assumption 5.3, we know that if 0' ~ ve.a, then
0' = + oe = 0 [{))e,
(158)
where ē ~ 4 I.
Moreover, we know that
(0') o (6'--) = Ode. (f() (f(E)
(159)
Thus, we can write what follows:
a
log (0)) log dd (f(E)c) Ve log @ (c)e. ag f(E)e.
(160)
ag
By applying the expectation w.r.t. the sampled parameter 0' to the square of è log vo (0'), we obtain:
a log v (0))
|1
2
E
V log log (c) (-))) 05
f(E)
(161)
6' ~'-
8'-
(())
(162)
where we exploited Assumptions 4.4 and 7.1.
Lemma G.11 @ Jp Bounded Variance). If the hyperpolicy Va.a satisfies Definition 2.3, under Assumption 5.3 and 4.4 and using an exploration mapping function f()) such that Assumption 7.1 is fulfilled and a parameterization for the exploration amount a, then the following holds:
R2 R Caa L
[GEJo(0',o)]
Var 0'-
< N(1 202
where -((E).
Proof. We recall that the estimator hand is:
1 2 N
V Jo (0,
Σ
log Vo.- (..) R(T.)
where N is the number of parameter configuration tested (on one trajectory) at each iteration and f({). Thus, compute the variance of such an estimator as:
War 8'~100-
V (EJo(0',
1
War v
log Vo.- 00)) R(m)
(163)
N
o
31

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
d 2
E 0'mu
log vo)) R(m)²
(164)
N
We can conclude the proof by applying Lemma G.10 and by considering the fact that, given trajectory т, R(()) is defined as:
R(T)) Σ
t=
with r(s, a) E [- Rmax, Rmax] for every s S and E A.
Lemma G.12 (Bounded Policy Scores). the policy we.a satisfies Definition 2.2, under Assumption 5.3 and 4.4 and using an exploration mapping function f()) such that Assumption 7.1 is fulfilled, then the following holds for every state S:
2
E a n- (115)
log n0.- (als)
Lo
where a f(E).
Proof. From Definition 2.2 and from Assumption 5.3, we know that if a ~ no, (-Is), then
a (s(()) + oe (a(()) + f({),,
(165)
where ē ~ L
Moreover, we know that
(als) = (a- = 0d (f(E)E..
(166)
Thus, we can write what follows:
a
à ag
log (als)
log of Ve log o (c)le- "g f()cc.
(167)
ag
By applying the expectation w.r.t. the sampled action the 2-norm squared of Ve log na. (als), we obtain:
à f(()
log no To. (als))
Ve (o)
(168)
a- (+1s)
6' 8'-
(169)
where we exploited Assumptions 4.4 and 7.1.
Lemma G.13 V Bounded Variance). If the policy ne.o satisfies Definition 2.2, under Assumption 5.3 and 4.4 and using an exploration mapping function f()) such that Assumption 7.1 is fulfilled and a parameterization & for the exploration amount a, then the following holds:
R2 R Ld
(GEJA00,0)]
Var T-PA(-((..))
< N(1 303
where a f(E).
Proof. We recall that the estimator at hand is:
EJ = M
Σ
a
log no. (a (an.)))).)t)) o 7' ar.r),
o
k=0
where N is the number of trajectories tested at each iteration and a f(E). Thus, we can compute the variance of such an estimator as:
Var Pxpx-
(EJA(B,,))
(170)
Var
Σ
Σ h-0
log no. (a,, (a,, (Bm of ((
(171)
N
32

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
2
i
log no (a,0(ann. (an,
7 7t ant an,t))
(172)
N (-Pa(1(0,a))
d
Σ
2 rs ar..)?
Σ
7
log ne (a (ar1.))511.)))
(173)
p-111-1(0,0)
Aim0
R max
T-1
1
27
E N(1 - 7) (-).0)((.0)))
log 1o (a,
(174)
o
R Rmaaxd ..L.t.
(175)
N(1 002
where the second inequality is
and the last one is by Lemma G.12.
Lemma 7.2 (Bounded V (0, f(g)), If the (hyper)policy satisfies Definitions 2.2 or 2.3, under Assumptions 4.4 and 5.3, using an exploration mapping f(-) fulfiling Assumption 7.1.for any parameterization &, it holds that:
Vt
(eE) & NS(E)²
Proof. This lemma is the ensemble of Lemmas G.11 and G.13.
G.4. Last-Iterate Convergence Guarantees of SL-PG to Optimal Stochastic Policies
G.4.1, ADDITIONAL NOTATION
Before delving into the details of SL-PG last-iterate convergence guarantees, we introduce additional notation that will be used the subsequent proofs.
Being in the context of Section 7, consider the total parameterization Rdo+1.
v = (0,
(176)
where 0 is the vector of dimension de representing the parameterization of the (hyper)policy.
SL-PG aims to maximize the objective:
JT(v) = ((E)),
(177)
where / R [aminn max is a stochasticity mapping satisfying Assumption 7.1.
The SL-PG algorithm updates u as
Uk+1 ((V)).
(178)
where 6 > 0 is the step size and V (T)) is an unbiased estimator of V (T(( (e.g. GPOMDP (AB) or PGPE (PB)).
In this context, intend V.J+(v) to be (de 1)-dimensional vector:
VoJ((v)= = (oJ((v) aJr(v) aT₁(v)
(20, 20, ... 60as 8E
(179)
Moreover, we intend (v) and Ve)((v) as
oJ((c) )) and veJ((v) Od oJ₁(v) T
voJ(vv= = (J)(())
(
(180)
202
20de
og
noticing that both of them have the same dimension of V (+(e)
33

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
G.4.2. CONVERGENCE
Theorem 7.3 (SL-PG Convergence). the (hyper)policy satisfies Definitions 2.2 or 2.3, under Assumptions 4.1, 4.3, 4.4, 5.1 (PB) or 5.2 (AB), 5.3, 7.1, 7.2, and 7.3, running SL-PG for K iterations, with suitable constant choice for the learning rate ok. the output parameterization UK is such that:
J [[J+(UK)) & Bos
with total sample complexity of:
NK δ ( (160g 16007122,0111000
200 min
where L2t,0 L2 + Let and V4,0 V4.0 + V4.5
Proof. Here, the goal is to find the minimum amount of trajectories N needed, together with appropriate choice of the learning rate 8, to guarantee that the parameterization that SL-PG outputs in the last iterate 2k is such that the following quantity is bounded:
J - [
(181)
The first step is to bound the difference between (1 and Jf(vx).
(1(+1) - (1)) (UEHI- Uk. voJi(us)
(182)
L2t
Uk++1
Uxl12
(183)
2
(VoT((U))) voJ((
12 82 (ooj((sse)
2
(184)
8 (oo)(())) + (tj((
VoJ((v))) (e. L2t 82
[ VeJi(uz) 2 |
(185)
8 (GoJ(( (V..((v)) + (VeJi(u)) V.J((on)) (V.J(())),V.T(((())) L2w (oJ
L2t L2 ( 2' (186)
2
where in the first inequality we used the quadratic bound and then we just used the particular form of the vectors V (.),()). (.)+()), and V.)+(.). Before carrying on with the proof, we recall that the holding of Lemmas 4.3 and 7.2 implies (1)) L2t = L2 + L2t.g as explained Section 7.
Let F& denote o-algebra representing all information available at the beginning of the 1tth iteration, and let E&[-] be short for [x]] Now consider the filtration F (F and let K=o be F-adapted process.
We now apply the conditional expectation E+I-J:
E ((( -y(1)))
(187)
E k
[((0+t)) -
(188)
> E ( (FaJi(uu), VoJ((en)) 0 ( (FeJ)(en), VoJi(ua))
L2t 82 (oJ)(uz)
12 L2t 82 (ez(
(2
2
2
(189)
=8 -1(1- Lahoo) [oi (0 (2t (1-)))e0) VeJo(cn) 2
2
V2 (Ex
Lzt 12
(190)
2N
where we employed the unbiasedness of the estimator and the variances bounds (Lemmas 4.3 and 7.2). Now define Vr. = V1.0 Vr.g. Thus, we rewrite the previous result as:
E [+((R+z]] J+(vz) (1 _127000 \ooT(ou))
To,,00V
(191)
2N (Ex))
34

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
Now that we bounded the improvement E,
[+(++11) I(((m) we can start handling the desired quantity:
J+(0*) E (1
(192)
= -i²") E Jr [1x)
E -(
F1(v1z))
(193)
< (1() E (vx)
8
L2t
V VorJ( (2x))
12
L2t V4, V4.88
(194)
2N f(Ex)
L v
L21 11.0882
= J1((²) E [(((w))
1
E
Ve.J (2x)
+ IE
(195)
2
2N f(Ex) )2
< (v*) - E [v
L
E
V
(2))
1/]
+ L V..
(196)
2
2No min
where we employed the fact that the stochasticity mapping function f allows the mapped & to assume as minimum value min-
We can now employ Assumption 7.3 as:
Voti(
1
max (0. (++*) - -T(()) - -Bu
(197)
au
Thus, we have the following result:
[+())) E' (1k+1))
(198)
< J+((t) - [T((v))
- uu
[ L2t.00
E max fo. fo. (o.) - J(((v)) - -
+
L2t V..u2
(199)
2
2No
I++*) - E [J((u))] u
(1
[
L20
L
max f E [:((²) - - - 30 13
+
L2 V.
(200)
2
2 min
where we applied twice the Jensen's ' incquality and where defined a,? 2
We now define = [1() - E [+((ux) Se. thus we can rewrite the previous result as:
Th+1 & Th nd (1 122 max r0)
L v2.1022 2 min
(201)
2
2
Selecting 5 & 1/ we have the following recursion:
μ
Vt..0. max 10, rx, +
Tk+1 <
(202)
2
2No2 2
min
From this point on, the proof is the same as the one of Theorem F.1 by Montenegro et al. (2024). In particular, selecting a constant step size of
NNo min
(203)
4L21 V,o
and running SL-PG for number of iterations K such that
16L27,0 log K
J1(1))- - -T(vo)
(204)
N min
it is guaranteed that
J1(1²) - [T((vx))] E &ct Bo.
(205)
35

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
G.4.3. ON THE INHERITANCE WEAK GRADIENT DOMINATION ON J
Instead of assuming Assumption 7.3 to holds, is possible recover the same result by exploiting Theorem 4.2. However, it is necessary introduce the following assumptions.
Assumption G.1 (WGD J4 w.I.t. {). With stochasticity mapping f()) satisfying Assumption 7.1, there exist A, > 0 and By 2 such that, for every & I. the following holds:
J - -J) & As
(1) + B,
0
2
where a = f(E) and J = m (, f(E)).
Assumption G.2 (Bounded Distance of the optimal 0). There exists 3 such that, for every 0 E θ, the following holds:
1* (o) 0 2 & (0), σ) J ()))
Sufficient conditions are requiring that the function J+(:,) is quasi-convex its optimum (*(o) (e.g., star-convex functions, Lee & Valiant 2016).
The following result shows that under Assumptions G.1 and G.2, and the assumptions of Theorem 4.2 and Lemma G.9, it is possible to recover the same condition imposed by Assumption 7.3.
Theorem G.14 ((O,g) E) Joint Weak Gradient Domination). Consider (hyper)policy complying with Definitions 2.2 (AB) or 2.3 (PB), and assume to be under regularity assumptions for the MDP (Asm. D.1) and the deterministic policy po
(Asm. D.2). Under Assumptions 4.1, 4.2, 5.1 (PB) 5.2 (AB), 7.1, G.I, G.2, and 7.2, for every parameterization 0 O and exploration parameterization E E, it holds that:
Jí((*)- - (1( & A V VoJi(w) (f(.))
where A. == 2ap (1 Lst,,)) and Bi $D B+(((E) (1+ L3t,)))
Proof. Under this set of Assumptions, have that Theorem 4.2 holds, that is: (+) o+, < ap (0))l1 + Bt(a),
(206)
where 3y(a) 3p + Dia, and op and 3D are the WGD constants of Assumption 4.2. Moreover, report Assumption G.I:
à
(0*)))))) (,(00 -((M))))))) & A
(10)
By,
(207)
where we use & 1 (a), as a shortcut for 10,, -
Our goal is to find an upper bound to the quantity:
JT( JT(v) = J,(00 ((("))) -(
(208)
for every Rd
Thus, we can start from the latter quantity:
(f(E)) -((0))
(209)
(210)
0 J (0 (f(E), f())) + ao ( + Bb (+(((E).
A
f())
(211)
aE
where we just applied Assumption G.1 and the result of Theorem 4.2.
Now, we focus on the quantity
(0 (f(E)).f(E)
In particular, the following holds:
2c
(
(J(S),
(212)
0
à J+ ((())
à J+ ((5))
2 J((0, +
(213)
06
36

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
< Laie (((() 0 + 05 ((())
(214)
&
- J+(0, +
J (0, (()))
(215)
< L3I
+ L3),)43 +
(216)
0
where in the second inequality we employed Lemma G.9, in the third inequality we employed Assumption G.2, and the last inequality we exploited the result of Theorem 4.2.
Given this last result, we have what follows:
(+(0*((EE)) (f((*)), f).(()(()))))))))))))))(())))( f(E))
(217)
à (1(0)) + on [[oJ((0, + 9D (T((E)))
A
(218)
à
< A
(4. f(E)) + (AAL3t,g + [o))) + 9D + (t(((E) + ()L3),
(219)
o
(22 f()) + [ + 3p (1+
< aD (1+ AFLor
(220)
The last step to conclude the proof is to bound the term
((. + VoJ+(0, To this end, we recall that 8c
(0,E) and that:
VoJr(v)= > ( (o) ... 20d0
(Ji(v) sdf(o)
VoJ((v) = (oii(o) ,., 0lag
al(e))
.)²
VeJ+(u) = (0de: 2 T
Thus, the following hold:
à J, (0, f()) - - -
VoJi(1))
(221)
because of the form of the treated gradients. Analogously, we have:
VVJ- VoJi(uil < /
(222)
In light of these results, conclude what follows:
]=(0"((((")) ((0, = -
(223)
(224)
< <p (1 + Lss (1 (0s J400, f(E)) + (V.0((000)))) + BD (+((())) A
(225)
& 2op (1 + A ())
/uJr(1s)) + +pb
(226)
which concludes the proof.
G.4.4. CONVERGENCE UNDER THE CONDITIONS FOR WGD INHERITANCE ON Jr
Theorem G.15 PGGPG Convergence Under WGD Inheritance). the (hyper)policy satisfies Definitions 2.2 or 2.3, the out-
put parameterization uk of SL-PG is such that: under Assumptions 4. I, 4.2, 4.3, 4.4, 5.1 (PB) or 5.2 (AB), 5.3, 7.1, 7.2, G.I, I, and G.2, running SL for K. iterations, with suitable choice for the learning rate 5, the output parameterization Ug such that:
--EJi((KK] < (
with total sample complexity of:
NK- δ
2
min
37

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
where L2t,0 L2 + L and V1,u V4.0 V4.5
Proof. The proof is the same as the one of Theorem 7.3, except for the fact that, instead employing Assumption 7.3 bound [v)]( use the result of Theorem G.14
V Vonc( 2
max (0, J - -T(())- B).v,
(227)
Ag,
0, J+ - - 5
max
(228)
Ar,
having exploited the fact that, by definition, the stochasticity mapping function f(-) ensures that the maximum allowed value for is max Now, by defining 7ą == J [[x+( B the proof continues the one of Theorem 7.3.
Comment. It is worth noticing that this result comes the cost of the very demanding Assumption G.2. Moreover, the result suggests that in the final suboptimality there is always term which is directly proportional to the maximum value that the a can assume due to the mapping f(-). With this analysis, this term, which comes from Theorems 4.2 and G.14, would not disappear even under the assumption that all the e-optimal stochastic (hyper) have the stochasticity less than e, thus setting min = e. To make this additional quantity disappear, one has to assume the (very) demanding strong gradient domination on J+ w.r.t both A and g.
38

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
AB and PB Configurations for Swimmer-vS
Environment
Swimmer-v5 (Todorov et al., 2012)
Horizon
=0200
Dimensions
A = ds
de = 16
(Hyper)policy
Linear Gaussian
Learning rates (Adam, Kingma & Ba 2014)
0.01
Batch size
N 100
PES Schedule A
max
y 1
P = 25
Kp 200
PES Schedule B
max
y = 0.5
P P= 5000
Kp = 1
SL-PG
max
Omin = 0
K = 5000
Static (AB and PB)
a {1, 0.5, 0.04, 0.0144
K 5000
Table 2. Experimental details for the numerical validation presented in Section 9.
H. Additional Experiments
H.1. Employed Policies and Hyperpolicies
Linear Deterministic Policy. A linear parametric deterministic policy pe S - A samples the actions as ag = 0 8,. where 8, is the observed state at time and is the parameter vector.
0',,
Linear Gaussian Policy.
A linear parametric gaussian policy Te.o : S x A - A(A) with variance o² samples the actions as a ~ OOT 8t, TTaT), where 8; is the observed state at time and 0 is the parameter vector. Notice that in this case we consider 0 [&dx xda, For this policy, the scores are the following:
Ve (a) (aa-TT))=T)
log (a)) 1a-0" la-0"al3-a0 alp-dio"
log (a) 1a-00-000 a| -dyd ag
a²
where the considered parameterization for the stochasticity, i.e., o ef,
Gaussian Hyperpolicy. parametric gaussian hyperpolicy vo. E A(0) with variance 0² samples the parameters 0' for the underlying linear deterministic parametric policy μe 0' NO0 o² ldg), where 0 is the parameter vector for the hyperpolicy. For this hyperpolicy, the scores the following:
V log (0)) (0') / do log (0") 10'-013 da0?
à
log (0') -0'-00 dog
where the considered parameterization for the stochasticity, i.e., o= = os.
H.2. Experiment: Swimmer (Details of Section 9)
Here, report the details for the experiment presented in Section 9. In particular, Table 2 reports the experimental details, Table 3 report the deterministic policy deployment scores, and Figures 3a and 3b report the values of Jr and a during the learning process.
H.3. Experiment: Inverted Pendulum
Here, we present similar experiment w.r.t. the one shown in Section 9. In particular, we analyze the behavior of PES and SL-PG in both the AB and PB exploration domains, comparing them with their static stochasticity counterparts (GPOMDP and PGPE) the context of deploying deterministic policies. We conduct the evaluations in the InvertedPendullmnus5 environment, which is part of the MuJoCo (Todorov et al., 2012) control suite, using a horizon of = 200. All learning rates are managed by the Adam (Kingma Ba, 2014) optimizer.
39

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
PES-A
60
SL-PG
0.8
PES-B
40
0.6
PES A
SL-PG
PES-B B
0.4
σ =
0.5
0.2
σ 0.04
0
0.014
1,000
2,000
3,000
4,000
5,000
1,000
2,000
3,000
4,000
5,000
Iteration
Iteration
(a) Parameter-based
60
PES-A
SL PG
PES-1 B
0.8
40
0.6
0.4
20
PES-1
SL-PG
PE3-B
0.2
0.04
0
1,000
2,000
3,000
4,000
5,000
1,000
2,000
3,000
4,000
5,000
Iteration
Ieration
(b) Action-based.
Figure 3. Jr and a behavior for PB and AB in Swimmer-vy (5 runs, mean 1.55 C.I.).
Method
PB
Ap
AB
A
PES-A
61.14 + 1.1
-0.12
28.93 + 9.89
0.44
SL-PG PG
61.43 + 2.73
- 0..1
49.83 + 13.38
1.19
PES-B
60.40 2.31
0.27
29.24
8.74
0.33
Table Swimmer-v5: deterministic deployment performance (5 runs over 100 trajectories, mean + std). A, Jp(Ok) (+(x)).
For both exploration paradigms, we present PES with two different schedules, both starting with a 1. The first (A)
schedule consists of P 25 phases, each lasting K, = 50 iterations, with a schedule exponent of y = 1. The second
(B) schedule includes = 1250 phases, each lasting K, = 1 iteration, with a schedule exponent y = 0.5. SL-PG executed for K 1250 iterations, using the common exponential parameterization for (i.e., stochasticity counterparts are also run for K 1250 iterations. employing stochasticity levels {1, 0.5, 0.04, 0.028). Here, represents the maximum stochasticity in the PES schedules, while 0.04 and 0.028 correspond the minima of the first and second PES schedules, respectively.
ef). The static
Parsmeter-based. As shown by Figure 4a, in the PB exploration domain, PES-B (the one with the continuous schedule) outperforms the other methods in terms of convergence to optimal performance, while PES-A (the one who mimics what
40

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
AB and PB Configurations for InvertedPennaalum-s5
Environment
InvertedPendalum--55 (Todorov et al., 2012)
Horizon
= =0200
Dimensions
da = ds = 4 de =4
(Hyper)policyy
Linear Gaussian
Learning rates (Adam, Kingma Ba 2014)
0.01
Batch size
N
100
PES Schedule A
max
1
y = 1
P = 25
Kg 50
PES Schedule B
Fmax
1
= 0.5
P = 1250
Kp = 1
SL-PO
max
Omin = 0
K = 1250
Static a (AB and PB)
a {1, 0.5, 0.04, 0.028)
K 1250
Table Experimental details for the numerical validation presented in Appendix H.3.
Method
PB
Ap
AB
A
PES-A
200 0
0.08
200 + 0
0.21
SL-PC
199.97 + 0.06
0.6
200 + 0
0.018
PES-B
198.37 + 2.3
0.53
200 + 0 0
Table 5. InvertedPendullmm-S:: deterministic deployment performance (5 runs over 100 trajectories, mean + std). Setting of Table 4. A Ju(0x) - J..0x).
prescribed by theory) exhibits similar behavior to SL-PG. In terms of deterministic deployment, PES-A is the one outputting the best performing deterministic policy. In this case, the worst performing one PES-B, which employs a schedule not compliant with what prescribed by the PES theoretical tractation.
Action-based. This pattern does not hold in the AB exploration domain, as illustrated in Figure 4b. In this case, the GPOMDP instances with the lowest static stochasticity levels converge faster than their dynamic counterparts. However, this faster convergence comes at the expense of manually tuning the stochasticity levels, which is not required for approaches that employ dynamic For what concerns deterministic deployment, all the dynamic stochasticity methods reach the optimal deterministic policy (see Table 5).
Final a. In general, while the final stochasticity level of PES is controlled by the imposed schedule, the final stochasticity of SL-PG remains uncertain until the end of the learning process, as it is learned via stochastic gradient ascent. this specific case, the final parameterization learned by PES-A, that follows what suggested by theory since Kp > 1, ensures that the loss incurred when switching off the noise is smaller compared to that incurred when using SL-Pe PG or PES-B, This difference, which surprisingly is not holding for the AB case, is highlighted in Table 5.
H.4. Reacher-v5 Study
Similarly what done in Section 9, here analyze the behavior of PFS and SL-PG in both the AB and PB exploration domains, comparing them with their static stochasticity counterparts (GPOMDP and PGPE) in the context of deploying deterministic policies. This time, the evaluations are conducted in the Reucher-y5 environment, always part of the MuJoCo (Todorov et al., 2012) control suite, using its default horizon T 50. All learning rates are managed by the Adam (Kingma& Ba, 2014) optimizer.
For both exploration paradigms, we present PES with two different schedules, both starting with a = 0.5. The first schedule (A) consists of 25 phases, each lasting K, 200 iterations, with a schedule exponent of y The second schedule (B) includes P 5000 phases, each lasting K, = 1 iteration, with schedule exponent of y = 0.5. SL-PG is executed for K 5000 iterations, using the common exponential parameterization for (i.e., =). The static stochasticity

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
200
PES-A
SL-PG
0.8
PES-A
150
PES-A A
100
SL-PG
PES- B
0.4
0 =
0.5
0.2
50
0.04
0.028
200
400
600
800
1,000
1,200
0
200
100
600
800
1,000
1,200
Iteration
Iteration
(a) Parameter-based.
200
PES- A
SL-PG
0.8
PES B
150
0.6
PES-A
100
SL-PG
PES-B
0.4
=
50
0.2
0.04
0.028
0
200
400
600
800
1,000
1,200
0
200
400
600
800
1,000
1,200
Iteration
Iteration
(b) Action-based.
Figure 4. Jt and a behavior for PB and AB in InvertedPendulam--55 (5 runs, mean +95% C.I.).
counterparts are also run for K 5000 iterations, employing stochasticity levels {0.5, 0.08, 0.002). Here, a 1 represents the maximum stochasticity in the PES schedules, while 0.002 correspond the minimum of the first PES schedule. All the experimental details are presented in Table 6.
Parameter-based. As shown in Figure 5a, in the PB exploration domain, PES-B (with the continuous schedule) outperforms the other methods in terms of convergence to optimal performance, but the PGPE instance with fixed stochasticity = a Also in this scenario, PES-A cxhibits slower performance convergence, this can be explained by the fact that, by construction of the stochasticity schedule, keeps the same value fore more iterations. This behavior is more similar to the one prescribed by theoretical algorithm construction (Sec. 3). is worth noticing that SL-PG outputs parameterization associated with ok which is 12 times larger than the final stochasticity of PES-AA and 35 times the final of PES-B. BB
Action-based. Figure 5b shows the same results in the AB exploration context. The figure highlights the need of having dynamic stochasticity schedule, since GPOMDP instances with fixed stochasticity levels do not manage to optimize the parameters the linear policy, except the one with a 0.02. This last instance shows a similar hehavior to PES-B, which, at the end the learning procedure, ensures to have good parameterization for smaller stochasticity o = 0.007. The algorithm reaching the largest performance is PES-A, which benefits from keeping the stochasticity level fixed for more than one iteration, however resulting good parameterization for a stochasticity o 0.02. The slowest one converge SL-PG, which output good parameterization for stochasticity 0.08.
Final In general, while the final stochasticity level of PES is controlled by the imposed schedule, the final stochasticity
42

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
AB and PB Configurations for Reacher-v5
Environment
Reacher-v5 (Todorov et al., 2012)
Horizon
= 50
Dimensions
dA = ds 10 de = 20
(Hyper)policy
Linear Gaussian
Learning rates (Adam, Kingma Ba 2014)
0.001
Batch size
N 100
PES Schedule A
max = 0.5
P 25
K = 200
PES Schedule B
max 0.5
= 0.5
P = 5000
Kp 1
SL-PG
mmax
0.5 Omin = 0
K = 5000
Static a (AB and PB)
a E {0.5, 0.08, 0.002)
5000
Table 6. Experimental details for the numerical validation presented in Appendix H.4.
Method
PB
Ap
AB
A
PES-A
-11.47 + 0.35
0.37
-7.38
0.2
0.02
SL-PG
-102.85 + 8.1
187.13
6.83 + 0.34
0.66
PES-B
8.733 + 0.29
0.06
9.66 + 0.74
-0.01
Table Deterministic deployment performance (5 runs over 100 trajectories, mean + std). Setting of Table 6. A = Jo(Ox) ((()
of SL-PG remains uncertain until the end of the learning process, as it is learned via stochastic gradient ascent. Table 7 shows the deterministic deployment performances of the learned parameterization by PES-A, PES-B, and SL-PG. For the AB case the best performing is PES-B, which ensures the lowest level of stochasticity at the end of the learning process. Switching to the AB scenario, the best performing is SL-PG. This fact enforces the consideration that SL-PG cannot ensure always to converge to particular value of the stochasticity level, which can crucial for the deterministic deployment performance, as the case for this environment.
On the Semantic Difference between PB and AB. Finally, in this experiment it is possible appreciate the semantic difference between the PB and AB exploration paradigms. Indeed, Figures 5a and 5b highlight the different scale of performance values Jp and JA corresponding to hyperpolicies and policies w.r.t. the same stochasticity level a.
H.5. PES Sensitivity Analysis: y Parameter
In this section, conduct experiment on the sensitivity of PES to the y parameter. We run PES in the InvertedPendulune v5 environment with horizon T 100. The PES instances employ schedule with 0max 1, Kp 40, and P 25. Learning rates are managed by Adam and initialized at Ç = 0.01. We recall that the parameter y controls the smoothness of the schedule, determining, having fixed Kp, P. and max the final value for the a. In these experiments, we employed three schedules, differing in the value: (A) has y = 1, (B) has y = 0.5, finally (C) has 0.1. The details for this experimental setting are summarized Table
Figures 6a and 6b show that, in both AB and PB exploration domains, it is possible see that PES-C is the one showing the poorest convergence speed. Moreover, its final performance is the lowest one. The best performing one PES-A, which mimics the behavior prescribed by theory. As also observed in the experiments conducted in Section 9, and Appendices H.3 and H.4, a smaller value for y should be associated with phases running a smaller amount of iterations. This is in order to provide a final value for a that the same across schedules, given a total amount of iterations K = Ep- Kp
43

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
-10*
0.5
PES- A
SL-PG
0.4
PES- B
0.3
-4
PES-A
SL-PG
0.2
PES-B
6 0.5
0.1
0.08
-8
0.002
0
1,000
2,000
3,000
4,000
5,000
1,000
2,000
3,000
4,000
5,000
Iteration
Iteration
Parameter-based.
0.5
PES- A
-10
SL-PG
0.4
PES-B B
PES-A
0.3
-20
SL-PG
PES-B
0.2
a = 0.5
-30
0.002
0.1
0
1,000
2,000
3,000
4,000
5,000
1,000
2,000
3,000
4,000
5,000
Iteration
Iteration
(b) Action-based.
Figure 5. Jj and bchavior for PB and AB in Reacher-v5 (5 runs, mean +95% C.I.).
AB and PB Configurations for PES Sensitivity Study on
Environment
InvertedPendulum.v55 (Todorov et al., 2012)
Horizon
= 100
Dimensions
d 1 ds 4 de = 4
(Hyper)policy
Linear Gaussian
Learning rates (Adam, Kingma & Ba 2014)
0.01
Batch size
100
PES Schedule
Tmax
P 25
K₂
PES Schedule
Tmax
y 0.5
P 25
K₂ 40
PES Schedule
Tmax
y 0.1
P 25
K₂ 40
Table 8. Experimental details for the numerical validation presented in Appendix H.5.
44

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
100
0.5
0.8
y
0.1
0.6
60
0.4
40
y
0.5
0.1
0
200
400
600
800
1,000
0
200
400
600
800
1,000
Iteration
Ieraaion
Parameter-based.
100
1
y 0.5
80
0.8
0.1
60
0.6
40
0.4
V
0.2
20
= 0.5
y 0.1
0
200
400
600
800
1,000
0
200
400
600
800
1,000
Iteration
Iteration
(b) Action-based.
Figure 6. Jr and behavior
AB in InvertedPendalum-v5 runs, mean 195% C.I.).
H.6. PES Sensitivity Analysis: K₃ and P Parameters
In this section, we conduct an experiment on the sensitivity of PES to the Kp and P parameters. We run PES in the InvertedPendulum--S environment with a horizon T' 100. The PES instances employ a schedule with 0 = 1 and = 1. Learning rates are managed by Adam and initialized at = 0.01. We recall that the parameters K, and P control the total amount iterations done by the algorithm. Specifically, Kp specifies the number of iterations which PG subroutines are run with fixed value of stochasticity a. Such parameters, together with the selection of y and mmax regulate the smoothness of the schedule and the final value for the a. In these experiments, we employed three schedules, differing in the (Kp, P) values: (A) has (40, 25), (B) has (10, 100), finally (C) has (1, 1000). The details for this experimental setting summarized in Table 9.
Figures 7a and 7b show that, in both AB and PB exploration domains, it is possible to see that PES-C ASsC is the one showing the poorest convergence speed. In particular, such a schedule presents an unstable behavior at convergence. The best performing one PES-A, which mimics the behavior prescribed by theory. As also observed in the experiments conducted Section Appendices H.3 and H.4, a smaller value for K, should be paired with smoother schedule (i.e., smaller y). Indeed, by frequently reducing the stochasticity, it has to be reduced smoothly, since PF.S has not the opportunity to find good parameterization for every fixed o.
45

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
AB and PB Configurations for PES Sensitivity Study on Kp and P
Environment
InvertedPendulum-55 (Todorov et al., 2012)
Horizon
= 100
Dimensions
da
ds = 4 de =
(Hyper)policy
Linear Gaussian
Learning rates (Adam, Kingma & Ba 2014)
0.01
Batch size
N
100
PES Schedule A
max =
y = 1
P = 25
K = 40
PES Schedule B
max =
= 1
P = 10
Kp 100
PES Schedule C
mmax =
P 1000
Kp =
Table Experimental details for the numerical validation presented in Appendix H.6.
100
P 25, K 10
P 10, K, 100
0.8
P 1000, Kp
0.6
60
0.4
40
P = 25, Kp 40 10, Kp
0.2
P 1000, K, 1
400
800
1,000
400
800
1,000
Iteration
Iteration
Parameter-based
100
25, K, 40
P 10. p 100
0.8
1000, K,
60
0.6
0.4
40
P 25, K,
0.2
P 10, Kp 100
P 1000, K, 1
0
200
400
600
800
1,000
0
200
400
600
800
1,000
Iteration
Iteration
(b) Action-based.
Figure 7. J4 and a behavior for PB and AB in InvertedPendalum--55 (5 runs, mean +95% C.I.).
46

---

Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity
H.7. Computational Resources
All the experiments were run on 2019 16-inches MacBook Pro.
The machine was equipped follows:
CPU
RAM
GPU
Intel Core 17 cores, 2.6 GHz) 16 GB 2667 MHz DDR4
Intel UHD Graphics 630 1536 MB
In particular, 100 trajectories of the MuJoCo environments with T 100 scored & 2 iterations per second, All the performances are to be considered with parallelization over CPU cores.
47


Reviews:
[{"review_id": "gTw75ln6f8", "reviewer": "Reviewer_UaJQ", "summary": "The paper focuses on the convergence analysis of policy gradient methods in RL with dynamic stochasticity. It introduces PES, a phase-based algorithm that reduces stochasticity through a deterministic schedule while running policy gradient subroutines with fixed stochasticity in each phase. The paper demonstrates that PES achieves last-iterate convergence to the optimal deterministic policy. Additionally, it analyzes the common practice of jointly learning stochasticity and policy parameters (SL-PG), showing that this approach also ensures last-iterate convergence but to the optimal stochastic policy only, requiring stronger assumptions compared to PES. Experimental results on a toy simulation environment demonstrate that the theoretical claims are indeed satisfied.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for reviewing our work and for recognizing the strengths of our theoretical analysis, and the relevance of addressing an open problem in the convergence of PG methods with dynamic stochasticity. Below, we address the Reviewer’s concerns.\n\n### 1. Comparison against SOTA Deep RL techniques\nWe wish to emphasize that the **exploration schedules** adopted in PES (i.e., a deterministic decay of $\\sigma$) and SL-PG (i.e., learning $\\sigma$ via gradient ascent) can, in principle, be **applied to any PG method** (also actor-critic).\nThus, we can consider deep PG methods, as PPO, to be incorporated with the dynamic stochasticity methods of PES and SL-PG.\nWe stress that the convergence analyses of PES and SL-PG over actor-critic methods require different analyses. \nNonetheless, we now present an **empirical comparison of three variants of PPO**: $(i)$ the version with a fixed $\\sigma$; $(ii)$ a PES-inspired version deterministically decreasing $\\sigma$; $(iii)$ an SL-PG-inspired version where $\\sigma$ is learned.\n(https://drive.google.com/file/d/1149yLdiUaLudIfGEA8yRZK6FjHmY9fJG/view?usp=sharing) As shown in the paper, **PES and SL-PG perform at least as well as their static $\\sigma$ counterparts**, without requiring prior tuning. With PES, the final $\\sigma$ is predefined, yielding an **almost deterministic policy**. As predicted by theory, parameter-based methods may struggle with large parameter spaces.\n\n### 2. On the selection of schedule's parameters\nFor PES, the selection of the schedule's parameters is crucial. In general, following the theory, Theorems 4.4 and 6.1 suggest that longer phases allow to better converge to the optimum of a specific $\\sigma$, while a higher number of phases $P$ allows a smooth transition among objective functions ($\\sigma$-dependent). When designing the actual schedule, considering equal length phases, the user may decide the total number of iterations $K$ and the desired final $\\sigma$. Then, selecting the smoothness of the schedule $y$, $P$ is identified by inverting $\\sigma_P = \\sigma_{\\max}P^{-y}$. If $y$ is large, then the schedule will not be smooth and $P$ will be small, while $K_p$ large. As $y\\to0$, then the schedule will be smoother and $P \\to K$, leading to a continuous schedule ($K_p=1$) which often works properly (Fig. 1a, 4a, 4b, 5a, 5b). SL-PG may overcome these by adapting $\\sigma$ automatically, avoiding manual tuning. However, since the final $\\sigma$ is not controlled, **no guarantees can be provided on the resulting deterministic policy** after switching off the noise.\n\n### 3. Differences with [1]\nOur paper **builds upon the foundation established by [1]**, which consider fixed $\\sigma$ throughout their analysis. [1] show that the convergence to the optimal deterministic policy is achieved with $\\tilde{\\mathcal{O}}(\\epsilon^{-5})$, by setting $\\sigma = \\mathcal{O}(\\epsilon)$. This is impractical since it means to keep $\\sigma$ fixed to a small value for the whole training, leading to slow convergence in practice, and requiring to run multiple trainings to tune $\\sigma$. In contrast, for the first time in theory, we consider a setting in which $\\sigma$ is variable, studying methods eliminating the issues of [1] and managing to provide the same convergence guarantees for PES and similar for SL-PG.\nWe explicitly **include the results of [1]** (Sec.4, Apx. D), as their framework introduces key concepts necessary to fully appreciate our contribution. Nevertheless, **all additional results that explicitly model and analyze the role of varying stochasticity are novel**:\n1. The design of PES (Sec. 3);\n2. The characterization of the loss incurred in the objectives $J_A$ and $J_P$ when the stochasticity level is changed (Thr. 5.1);\n3. The derivation of the sample complexity required by PES to guarantee last-iterate global convergence to the optimal deterministic policy (Thr. 6.1);\n4. The study on the conditions and the sample complexity under which SL-PG ensure last-iterate global convergence to the optimal stochastic policy (Lem. G.1--G.12, 7.1, 7.2, Thr. 7.3);\n5. The study on whether the weak gradient domination (WGD) is inherited by $J_A$ and $J_P$ considering also the additional learning variable related to the $\\sigma$ (Thr. G.14) and the resulting sample complexity of SL-PG under WGD inheritance (Thr. G.15).\n\n### 4. Relevance of white-noise-based exploration\nWhite-noise (hyper)policies encompass a large variety of controllers. Indeed **most stochastic (hyper)policies used in continuous control**, such as Gaussian with fixed variance, **fall in this class** [2,3,4].\n\n### 5. On the clarity of the manuscript\nWe agree that moving the **related works section to the main text** will improve clarity, and we plan to do so in the final version. We also aim to better highlight the core ideas of each result to enhance readability.\n\n**References**\n[1] Montenegro et al. (2024)\n[2] Duan et al. (2016)\n[3] Schulman et al. (2017)\n[4] Tirinzoni et al. (2024)", "claims_and_evidence": "The claims regarding convergence of PG algorithms under dynamic stochastic noises are proven thoroughly with theoretical proofs.", "methods_and_evaluation_criteria": "This is more of a theoretical paper for convergence analysis of PG approaches in RL. Experiments and evaluation are conducted on toy simulation setting just to demonstrate the theoretical properties.", "theoretical_claims": "The paper is theoretically very strong. Although majority of the ideas are derived from Montenegroetal. (2024), the authors have proved the convergence properties step by step with several theorems.", "experimental_designs_or_analyses": "Experiments are conducted on a toy simulation environment to demonstrate the impact of different number of phases and their duration, and to compare between proposed PES and SL-PG. While these analysis makes sense to demonstrate the theoretical properties, a detailed analysis by comparing the performance with existing deep PG algorithms would have been more appreciated.", "relation_to_broader_scientific_literature": "While policy gradient in RL is an important and broader topic, the convergence analysis under white noise hyper-policies would of interest to a smaller portion.", "essential_references_not_discussed": "Distinction between the proposed work and Montenegroetal. (2024) [from which most of the theories are derived] could have been explained better.", "other_strengths_and_weaknesses": "The paper is theoretically strong and solves an important problem of convergence analysis of PG algorithms through a novel phase-based iterative algorithm. It also analyzes common practices of Stochasticity-Learning Policy Gradient (SL-PG). Most importantly, the paper provides a solid theoretical foundation for the use of dynamic stochasticity in policy gradient methods, bridging the gap between theory and practice. Having said that, there are a few concerns in terms of practical application:\n1. Complexity of PES: While PES provides strong convergence guarantees, its phase-based approach and deterministic schedule might be complex to implement and tune in practice. The need to carefully select parameters such as the number of phases and the learning rate schedule adds to this complexity. How to select the optimal parameter configuration needs to be explained in more details. \n2. Limited Practical Validation: The paper primarily focuses on theoretical analysis and does not provide extensive practical validation of the proposed methods. More empirical results and experiments in real-world scenarios would strengthen the paper's contributions. Furthermore, benchmarking the performance against SOTA deep PG methods would be a nice addition.", "other_comments_or_suggestions": "Majority of the space is allocated towards theorem and analysis. The paper is convoluted with symbols and theorems which is hard to follow in the current format. Some restructuring would be helpful for the readers. For example, adding related work section in main body, and highlighting the high-level takeaways from each theorem.", "questions_for_authors": "1. Why PES and SL-PG are not compared with SOTA deep PG algorithms?\n2. How to identify optimal number of phases and their length in a practical setting?\n2. What is the main difference between the proposed analysis and the work of Montenegroetal. (2024)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nsnskgq2jH", "reviewer": "Reviewer_vEmL", "summary": "This paper provides a global last-iterate convergence analysis for a widely used class of reinforcement learning algorithms, specifically deterministic policy gradient methods with dynamic stochasticity. It considers two common types of dynamic stochasticity: phased exploration scheduling (PES) and stochasticity learning scheduling. The paper establishes global convergence under standard assumptions and offers a thorough discussion of theoretical connections with prior work. Additionally, experimental results are presented to support the analysis.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for reviewing our work, and for recognizing that we address a highly relevant scenario in RL, providing valuable insights for both theorists and practitioners, and offering a strong theoretical analysis. Below, we address the Reviewer’s concerns.\n\n### 1. Relation between theoretical results and empirical learning curves\nWe are happy to clarify this point. Our aim is to provide, for the first time, a **theoretical foundation to the common practice of reducing the (hyper)policy stochasticity** during the learning process. To this end, we analyze the practice of learning $\\sigma$, named in our work as SL-PG, and we propose PES, which decreases deterministically $\\sigma$. The former converges to the **optimal stochastic policy** with a rate $\\tilde{\\mathcal{O}}(\\epsilon^{-3} \\sigma_{\\min}^{-2})$, the latter converges to the **optimal deterministic policy** with a rate $\\tilde{\\mathcal{O}}(\\epsilon^{-5})$, both matching SOTA results employing a fixed stochasticity during the whole learning [1,2,4] whose prescribe, for deterministic convergence, to set $\\sigma=\\mathcal{O}(\\epsilon)$, resulting in an impractical setting. In general, we expect that methods showing a small dominating term in the sample complexity bound to converge fast also in practice. Here, PES and SL-PG **provide the same guarantees of the ones employing a static $\\sigma$**. This happens since in the theoretical analysis the dominant term in the variance of the estimator is the one related to the smallest $\\sigma$ seen during training, thus providing guarantees as if we use a static $\\sigma=\\sigma_{\\min}$ for the entire learning. However, as seen in our numerical validation, PES and SL-PG **may perform better in practice since they expand the exploration possibilities by employing various $\\sigma$ values, without requiring to select one and to keep it for the whole learning.** We conclude by stressing that by employing PES there is the additional advantage of knowing the final $\\sigma$ which can be set small as the user wants, guaranteeing a proportional loss in performance when deploying a deterministic policy.\n\n### 2. Experiments on high-dimensional environments\nWe emphasize that the **primary focus** of our work is **theoretical**. Indeed, our goal is to **provide formal foundations for practices** that are already common in the use of **SL-PG** [6,7,8], and to propose **PES** as an alternative when the user aims to **obtain an almost deterministic final policy.**\nThis is why our experiments remain close to the theoretical setting, while, regarding the **learning of** $\\sigma$, the **practical literature has already adopted this approach**, and most experiments in the deep PG field involve learning the stochasticity.\nThat said, for the purpose of this rebuttal, we have also **conducted additional experiments using deep RL** methods to assess the behavior of PES and SL-PG in high-dimensional settings.\n(https://drive.google.com/file/d/1149yLdiUaLudIfGEA8yRZK6FjHmY9fJG/view?usp=sharing)\nAs shown in the paper, **PES and SL-PG perform at least as well as their static $\\sigma$ counterparts**, without requiring prior tuning. With PES, the final $\\sigma$ is predefined, yielding an **almost deterministic policy**. As predicted by theory, parameter-based methods may struggle with large parameter spaces. \n\n### 3. Weak gradient domination (WGD) and its derivation\nWGD is a **customary assumption** in the PG literature when establishing convergence guarantees [1,2,3,4]. Fundamentally, it enables **last-iterate convergence guarantees** by **characterizing the objective function without requiring concavity** in the parameters and while allowing for the presence of (at most $\\beta$-near) local optima.\nIn the same setting we adopt, [1] show that WGD is **inherited by both AB and PB objectives**, denoted respectively by $J_A$ and $J_P$, whenever it is **assumed to hold for the deterministic** objective $J_D$.\nAdditionally, [5] show that, for AB exploration, **WGD is induced on the objective** $J_A$ when the **stochastic policy satisfies the Fisher non-degeneracy condition**, i.e., when there exists $\\lambda > 0$ s.t. $\\mathbb{E}[\\nabla \\log \\pi_{\\theta}(a|s) \\nabla \\log \\pi_{\\theta}^{\\top}(a|s)] \\succeq \\lambda I$ for any $\\theta, a, s$. While this result is well established for AB exploration, it **remains an open question** whether WGD **can be similarly induced** on $J_P$ through a specific class of hyperpolicies **in the PB setting**.\nFinally, for **SL-PG**, we show in Appendix G.4.3 how WGD **can be inherited by the stochastic objectives** $J_A$ and $J_P$, even when **including the additional learning variable** associated with $\\sigma$, provided it holds for $J_D$, along with supplementary assumptions.\n\n**References**\n[1] Montenegro et al. (2024)\n[2] Yuan et al. (2021)\n[3] Fathkullin et al. (2023)\n[4] Bhandari & Russo (2024b)\n[5] Liu et al. (2020)\n[6] Duan et al. (2016)\n[7] Schulman et al. (2017)\n[8] Tirinzoni et al. (2024)", "claims_and_evidence": "The claims made in the submission are well supported by evidence.", "methods_and_evaluation_criteria": "Methods And Evaluation Criteria make sense for the problem.", "theoretical_claims": "I reviewed the overall structure of the theories (though I did not check the proof details line by line) and found that the theory is well-written and sound.", "experimental_designs_or_analyses": "Some of the experiments are unclear. Please refer to the questions for more details.", "relation_to_broader_scientific_literature": "This work addresses a common and highly relevant scenario in reinforcement learning, offering valuable insights for both theorists and practitioners. It is particularly pertinent to those utilizing deterministic policy gradient methods with noise-based exploration, such as in DDPG.", "essential_references_not_discussed": "No specificly.", "other_strengths_and_weaknesses": "Strengths:\nBroad Scenarios: The paper considers both action-based stochasticity and parameter-based stochasticity for phased-based dymanic and learning-based dynamic.\nThe theoretical analysis is robust and effectively compared with prior work.\n\nWeaknesses:\nPlease refer to the questions.", "other_comments_or_suggestions": "Please see questions.", "questions_for_authors": "Overall, I find this paper to be well-written and solid. However, I have a few questions:\n\n1. How do the experimental results help to illustrate the theoretical findings? While reviewing the results for Swimmer-v5 and InvertedPendulum-v5, the connection between the global convergence rate and the levels of stochasticity is not clear.\n\n2. Given that dynamic stochasticity is a common scenario in practice and of interest to a broader audience, I would appreciate seeing more experimental results from environments with higher dimensions.\n\n3. While the Weak Gradient Domination is addressed as assumptions (4.2) in this paper, I wonder if this WGD can be derived by other assumptions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Jbc2jsRHDY", "reviewer": "Reviewer_Uuyp", "summary": "The studies effects of exploration on the convergence of the policy gradient in RL. It proposes PES method that reduces the stochasticity with iteration, allowing sufficient exploration in the beginning and the convergence to the the optimal policy in the end. Further, it proposes another SL-PG method, and shows sample complexity of both the methods.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for reviewing our work and for recognizing its practical relevance. Next, we address the reviewer’s questions.\n\n### 1. Clarification on the paper contribution\nOur paper focuses on **actor-only PG methods** in **continuous state and action spaces**, using (hyper)policies with **dynamically varying stochasticity**, as commonly done in practice. Our goal is to provide a **theoretical foundation** to this practice, which had not been rigorously analyzed before.\nWe study **SL-PG**, where $\\sigma$ is learned via gradient ascent. Under a gradient domination assumption, we prove convergence to the **optimal stochastic policy** with a rate $\\tilde{\\mathcal{O}}(\\epsilon^{-3} \\sigma_{\\min}^{-2})$, but SL-PG does not allow to quantify the final $\\sigma$, hence no guarantee on the deployed deterministic policy.\nTo address this, we propose **PES**, which **deterministically decreases $\\sigma$** within phases. This allows control over the final stochasticity and guarantees **last-iterate convergence to the optimal deterministic policy** with rate $\\tilde{\\mathcal{O}}(\\epsilon^{-5})$, matching [1], but without requiring to fix $\\sigma = \\epsilon$ for the entire training.\n\n### 2. Lack of comparison with [2]\nWe acknowledge the relevance of the contribution of [2], but we believe it lies **outside the scope of our study**, since their **framework is different from the one adopted in our work**.\nSpecifically, [2] analyze **finite state and action spaces and employ a softmax policy parameterization**. Their theoretical results establish last-iterate global convergence guarantees for **actor-critic methods with AB exploration**.\nIn contrast, our setting considers **continuous state and action spaces and general (hyper)policy parameterization**. We address **both AB and PB explorations for actor-only PG methods**, and, most importantly, we explicitly analyze scenarios in which the **stochasticity $\\sigma$ varies during the learning** process, being interested in providing guarantees on the goodness of the **deployed deterministic policy**.\nFor these reasons the methodology of [2] is not directly comparable to ours, either in terms of assumptions or scope.\nHowever, we thank the reviewer for highlighting the lack of discussion on the actor-critic convergence literature, which we plan to include in the paper.\n\n### 3. Answer to Q1\nAs previously said, our setting is different w.r.t. the one of [2,3]. Specifically for [3], we highlight the following:\n1. We are in **continuous state and action spaces**, [3] consider finite actions;\n2. We provide **last-iterate global convergence to the optimal stochastic (SL-PG) and deterministic (PES) policies** for actor-only PG methods, [3] provide convergence to the stationary point under stochastic policies for actor-critic methods;\n3. We consider **both PB and AB explorations**, [3] only AB one;\n4. We consider a setting in which the **(hyper)policy stochasticity varies** while learning, [3] consider static stochasticity;\n5. We are interested in **deploying deterministic policies**, [3] stochastic ones;\n6. For convergence, we need **$J_D$ to be smooth, the variance of the estimators to be finite, and weak gradient domination (WGD) on $J_D$**, [3] assume sufficient exploration ($A$ matrix to be negative definite, e.g., in tabular MDPs this requires to the policy to explore all the state-action pairs), uniform ergodicity of the stationary distribution, and the regularity of the policy.\n\nOur set of assumptions is more general, which is required by the more general setting of our work. Notice that the kind of exploration we propose combined with the WGD do not require to assume sufficient state coverage, allowing to treat continuous spaces and general parameterizations, permitting to ensure last-iterate convergence (stronger w.r.t. the one to stationary points).\n\n### 4. Why assuming weak gradient domination (WGD)\nIn general settings, as the one considered in our work, WGD does not hold and has to be assumed [1,7,8,9]. [4] prove it in **tabular MDPs** with **direct policy parameterization only**. However, WGD can be derived under different sets of assumptions. For instance, [5] show that, in **AB exploration**, **WGD is induced** on $J_A$ when the **policy satisfies the Fisher non-degeneracy condition**, while it remains an open question whether a similar result holds for PB exploration. In our framework, [1] show that **if it holds for** $J_D$, then it is **inherited by both $J_A$ and $J_P$**.\nSimilarly, for **SL-PG**, we show in Appendix G.4.3 that **WGD is inherited by $J_A$ and $J_P$**, even when including the additional learned variable $\\sigma$, provided it holds for $J_D$ and under additional assumptions.\n\n**References**\n[1] Montenegro et al. (2024)\n[2] Kumar et al. (2024)\n[3] Chen and Zhao (2024)\n[4] Agrawal et al. (2020)\n[5] Liu et al., (2020) \n[6] Mei et al. (2022)\n[7] Yuan et al. (2021) \n[8] Fathkullin et al. (2023)\n[9] Bhandari & Russo (2024b)", "claims_and_evidence": "I didn't verify the results, but it seems believable.", "methods_and_evaluation_criteria": "I am not completely satisfied with comparison of the methods with existing litreature.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "To my understanding, exploration in RL is a very central topic. The theoretical understanding of effects of exploration on convergence is of great importance to the community.", "essential_references_not_discussed": "[1] is not discussed.", "other_strengths_and_weaknesses": "Strengths: The paper studies the exploration in policy gradient algorithms which are close to the practice. And provides theoretical bounds.\n\nWeakness: The paper is difficult to read and understand. The advantages of PES algorithm over vanilla actor-critic algorithm (global convergence with sample complexity O(\\epsilon^{-4}), see Proposition 1 of [1] ) is not clear. . \n\n\n[1] @misc{kumar2024improvedsamplecomplexityglobal,\n      title={Improved Sample Complexity for Global Convergence of Actor-Critic Algorithms}, \n      author={Navdeep Kumar and Priyank Agrawal and Giorgia Ramponi and Kfir Yehuda Levy and Shie Mannor},\n      year={2024},\n      eprint={2410.08868},\n      archivePrefix={arXiv},\n      primaryClass={cs.LG},\n      url={https://arxiv.org/abs/2410.08868}, \n}", "other_comments_or_suggestions": "Suggestions: SL-PG algorithm is crucial to the paper, a peudocode would be helpful for the reader.", "questions_for_authors": "Q1: We can obtain global convergence of PG (actor-critic) with an sample complexity of $O(\\epsilon^{-4}$ ( local convergence in [1] combined with gradient dominal lemma, see Proposition 1 of [2]). However, it requires mis-match coefficient to be finite, equivalent it assumes sufficient state-space coverage.  \nI assume, the paper in the review, wants to alleviate this issue with adding exploration in policy?   However, I see, the paper still makes sufficient coverage assumptions? Could the author compare and contrast the results and setting, with [1], what are theoretical benefits of adding exploration, how does this explorations relaxes the assumptions in [1] ? \n\n\nQ2: The return in RL satisfies gradient domination condition (Agrawal et. al.), then why it is taken as a assumption in the paper?\n\n\n\n\n\n\n[1] @misc{chen2024finitetimeanalysissingletimescaleactorcritic,\n      title={Finite-time analysis of single-timescale actor-critic}, \n      author={Xuyang Chen and Lin Zhao},\n      year={2024},\n      eprint={2210.09921},\n      archivePrefix={arXiv},\n      primaryClass={cs.LG},\n      url={https://arxiv.org/abs/2210.09921}, \n}\n\n\n[2] @misc{kumar2024improvedsamplecomplexityglobal,\n      title={Improved Sample Complexity for Global Convergence of Actor-Critic Algorithms}, \n      author={Navdeep Kumar and Priyank Agrawal and Giorgia Ramponi and Kfir Yehuda Levy and Shie Mannor},\n      year={2024},\n      eprint={2410.08868},\n      archivePrefix={arXiv},\n      primaryClass={cs.LG},\n      url={https://arxiv.org/abs/2410.08868}, \n}", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "C9u0IQv0Og", "reviewer": "Reviewer_TELj", "summary": "This paper introduces PES, a phase-based policy gradient algorithm for optimizing (hyper-)policies. Throughout the phases, the stochasticity required for exploration is gradually reduced. However, within a single phase, the stochasticity level remains constant. This allows existing convergence analyses for constant stochasticity to be leveraged to establish convergence within each phase of the PES algorithm. Subsequently, phase-wise convergence to the optimal deterministic policy is proven.\nFurthermore, the widely used SL-PG algorithm is examined. In this approach, the stochasticity level is introduced as an additional parameter in the policy gradient algorithm and is optimized jointly with the deterministic policy. Under stronger assumptions, convergence is also demonstrated, but to the optimal stochastic policy. Both algorithms are evaluated in different simulation studies and compared to algorithms with static stochasticity.\n\n## update after rebuttal: Thanks for the answers to clarify some questions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for reviewing our work and for recognizing that the proposed algorithms are practically relevant, have not been analyzed before, and appear theoretically well-founded. Below, we address the reviewer’s concerns.\n\n### 1. On the dependence on $T$\nFor the AB results, the correct quantity that should appear is the **effective horizon $\\overline{T} = (1-\\gamma^T)/(1-\\gamma)$**. We will clarify this point and correct the notation accordingly.\n\n### 2. Theoretical comparison with static stochasticity PGs\nWe provide a detailed comparison on this in **Appendix A**, which we plan to move and expand in the main paper, leveraging the additional page.\nThe best known rate is achieved by HARPG [2] , a momentum-aided PG method, converging to the **optimal stochastic policy** (AB only) with $\\tilde{\\mathcal{O}}(\\epsilon^{-2})$. However, HARPG differs from vanilla PG due to a Hessian correction step and performs poorly (Fig. 1 of [2]).\nOur focus is on **vanilla PG methods**, thus a comparison with [1,3] is more appropriate. Both provide convergence to the **optimal stochastic (hyper)policy** with rate $\\tilde{\\mathcal{O}}(\\epsilon^{-3} \\sigma^{-2})$, and only the latter considers the PB setting.\nThat being said, **SL-PG** achieves a rate $\\tilde{\\mathcal{O}}(\\epsilon^{-3} \\sigma_{\\min}^{-2})$, where $\\sigma_{\\min}$ is the minimum value for $\\sigma$ ensured by its parameterization.\nIn contrast, **PES** is designed to guarantee convergence to the **optimal deterministic policy**, with a rate $\\tilde{\\mathcal{O}}(\\epsilon^{-5})$, matching [3] but without requiring a fixed $\\sigma = \\epsilon$.\n\n### 3. Differences with [3] and technical novelty\nWhile our analysis builds upon the framework of [3], we introduce several **non-trivial contributions** that go beyond their results. For a summary on the key contributions and the differences with [3], please refer to the answer to Reviewer UaJQ. Here we focus on the technical novelty which is mainly represented by:\n1. Theorem 5.1: there we **quantify the loss incurred in terms of performance index $J$ when varying $\\sigma$.** This represents the first result of this kind and it highlights the need of employing an additive noise as presented in Section 2 which maintains the same distribution over the training.\n2. Theorem 6.1: there we assess the **convergence rate of PES**, leveraging the results of [3] for each phase, but introducing a deterministic schedule leading to a final $\\sigma$ allowing for a safe deterministic deployment.\n3. Lemmas G.1--G.12, 7.1, 7.2: there we characterize **crucial quantities for proving Theorem 7.3 (SL-PG convergence)** which relies on standard procedures for convergence study. However, the preliminary results, which we believe are of independent interest, help in better understanding the conditions under which SL-PG converges, especially concerning the kind of $\\sigma$ parameterization to be employed.\n4. Theorems G.14 and G.15: there we study **whether and under which conditions WGD can be inherited by the SL-PG objective**, additionally deriving its sample complexity under WGD inheritance.\n\nIn conclusion, we believe our contribution is *not a mere simple extension, providing for the first time a formal foundation for the common practice of dynamically adjusting the stochasticity in PG methods*.\n\n### 4. Examples of parameterizations\nAll the assumptions solely regarding the policy parameterization and the AB and PB noise are met by linear parameterized deterministic policies $\\mu_{\\theta}(s) = \\theta^{\\top} s$ with noises sampled from $0$-mean gaussians:  (AB) $\\varepsilon \\sim \\mathcal{N}(0, \\sigma I_{d_{\\mathcal{A}}})$; (PB) $\\varepsilon \\sim \\mathcal{N}(0, \\sigma I_{d_{\\theta}})$. Assumptions regarding the $\\sigma$ parameterization are met by $\\sigma = \\sigma_{\\min} + 1/(1 + e^{-\\xi})$, being $\\xi$ the optimization variable. An example of MDP allowing to meet also the remaining MDP-dependent assumptions is LQR, in which the chosen parameterization exhibit WGD (Asm. 4.2, 7.3) [4, Lemma 3].\n\n### 5. PES and SL-PG over momentum-based PGs\nRecovering the convergence result HARPG (Thr. 3 of [2]), it exhibits a sample complexity of order $\\tilde{\\mathcal{O}}(\\epsilon^{-2})$. In our setting, this translates into a rate $\\tilde{\\mathcal{O}}(\\epsilon^{-2} \\sigma^{-2})$, when considering a fixed $\\sigma$ (we have the bound to the policy score being $\\mathcal{O}(\\sigma^{-2})$).\nThus, **PES over HARPG** converges to the **optimal deterministic policy** with a rate $\\tilde{\\mathcal{O}}(\\epsilon^{-4})$, thus improving our current result at the cost of considering PG subroutines leveraging Hessian estimation. Similarly, **SL-PG over HARPG** converges to the **optimal stochastic policy** with a rate $\\tilde{\\mathcal{O}}(\\epsilon^{-2} \\sigma_{\\min}^{-2})$, with the same issue. We will add a comment on this.\n\n**References**\n[1] Yuan et al. (2021)\n[2] Fatkhullin et al. (2023)\n[3] Montenegro et al. (2024)\n[4] Fazel et al. (2019)", "claims_and_evidence": "All Theorems, Lemmas and Corollaries are proven in the appendix. I could not find unclear claims or statements in the text.", "methods_and_evaluation_criteria": "In theoretical analyses of PG algorithms, a static stochasticity level has almost always been considered. PES is one of the first approaches where stochasticity is gradually reduced, reflecting a common practice in real-world applications. Additionally, SL-PG investigates an algorithm in which the stochasticity is trained alongside the policy and automatically adapted. In my view, this represents a practically relevant algorithm whose convergence rates had not been analyzed before. Therefore, both methods appear well-founded.\nThe algorithms were evaluated in various examples in Appendix H, which can be considered standard for comparing PG-based methods.", "theoretical_claims": "The authors include the case $T=\\infty$ when introducing the setting in Sec. 2. However, the convergence results in Sec. 7 sometimes rely on the constant $T$. The authors should explain how this can be possible or delete the possibility of $T=\\infty$. Claims in Sec. 4 are all based on Montenegro et.al. 2024, I did not check the correctness in this reference. I checked the Claims in Sec. 5, 6 and 7. They seem solid.", "experimental_designs_or_analyses": "I did not implement the experiments to check the correctness. But the design seems fine to me.", "relation_to_broader_scientific_literature": "No direct comparisons is made regarding the convergence rate with previously analyzed algorithms that use static stochasticity. The (upper bound) convergence rates of PES with O(\\epsilon{-5}) and SL-PG with O(\\epsilon{-3}) are not as favorable as, for example, O(\\epsilon^{-2}) in Fatkhullin et.al. 2023 using HARPG. \n\nThe authors should address this aspect in more detail in the main part of the paper.", "essential_references_not_discussed": "None. But parts of the paper are very close (also in words) to Montenegro et.al. 2024.", "other_strengths_and_weaknesses": "Strengths:\n* The authors analyze two different versions of PG methods with a non-static stochasticity setting \n* They verify the performance of the theoretically analyzed algorithms in various applications\n\nWeaknesses:\n* The authors do not present examples of policy parametrizations which verify the assumptions in Sec. 4 or Sec. 7.\n* The proofs are primarily based on already known methods and results. No new proof strategy is evident.", "other_comments_or_suggestions": "My judgement is in the middle between weak accept and weak reject. The article is interesting but a pretty close continuation of Montenegra et al. I rated weak accept but note that it is a rather weak weak accept.", "questions_for_authors": "* Could you provide some examples of common policy parametrizations such that the assumptions in Sec. 4 and Sec. 7 are verified?\n* Could you compare your convergence results with the known rates for constant stochasticity?\n* Would applying momentum-based methods, as in Fatkhullin et al. (2023), also lead to a faster convergence rate in your case?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None"}}]

Author rebuttal:

Meta-review: This paper analyzes the convergence of the deterministic policy gradient method when exploration noise is systematically decreased across multiple phases. The reviewers assessed the paper as a valuable contribution to the understanding of related algorithms, and I concur with their evaluation.
Decision: Accept (poster)