Understanding the Effect of Stochasticity in Policy Optimization
Authors: Jincheng Mei
Bo Dai
Chenjun Xiao
Csaba Szepesvari
Dale Schuurmans
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
policy optimization
policy gradient
global convergence

Abstract: We study the effect of stochasticity in on-policy policy optimization, and make the following four contributions. \emph{First}, we show that the preferability of optimization methods depends critically on whether stochastic versus exact gradients are used. In particular, unlike the true gradient setting, geometric information cannot be easily exploited in the stochastic case for accelerating policy optimization without detrimental consequences or impractical assumptions. \emph{Second}, to explain these findings we introduce the concept of committal rate for stochastic policy optimization, and show that this can serve as a criterion for determining almost sure convergence to global optimality. \emph{Third}, we show that in the absence of external oracle information, which allows an algorithm to determine the difference between optimal and sub-optimal actions given only on-policy samples, there is an inherent trade-off between exploiting geometry to accelerate convergence versus achieving optimality almost surely. That is, an uninformed algorithm either converges to a globally optimal policy with probability $1$ but at a rate no better than $O(1/t)$, or it achieves faster than $O(1/t)$ convergence but then must fail to converge to the globally optimal policy with some positive probability. \emph{Finally}, we use the committal rate theory to explain why practical policy optimization methods are sensitive to random initialization, then develop an ensemble method that can be guaranteed to achieve near-optimal solutions with high probability.

Understanding the Effect of Stochasticity in Policy Optimization
Jincheng Mei 1
Bo Dai 3
Chenjun Xiao
Csaba Szepesvári 2 If
Dale Schuurmans' 3
University of Alberta DDepMinnd
"Google Research, Brain Team Tequa advising
Abstract
We study the effect of stochasticity in on-policy policy optimization, and make the following four contributions. First, we show that the preferability of optimization methods depends critically whether stochastic versus exact gradients used. In particular, unlike the true gradient setting, geometric information cannot be easily exploited in the stochastic case for accelerating policy optimization without detrimental consequences or impractical assumptions. Second, to explain these findings introduce the concept of committal rate for stochastic policy opti- mization, and show that this can serve as a criterion for determining almost sure convergence global optimality. Third, we show that in the absence of external oracle information, which allows an algorithm to determine the difference between optimal and sub-optimal actions given only on-policy samples, there is an inherent trade-off between exploiting geometry to accelerate convergence versus achieving optimality almost surely. That is, an uninformed algorithm either converges a globally optimal policy with probability 1 but at a rate no better than ((1/t), or it achieves faster than ((1/t) convergence but then must fail to converge to the globally optimal policy with some positive probability. Finally, we use the committal rate theory explain why practical policy optimization methods are sensitive random initialization, then develop an ensemble method that can be guaranteed to achieve near-optimal solutions with high probability.
Introduction
Policy optimization is central problem in reinforcement learning (RL) that provides foundation for both policy-based and actor-critic RL methods. Until recently it had generally been assumed that methods based on following the policy gradient (PG) [1] could not be guaranteed converge to globally optimal solutions, given that the policy value function is not concave. However, this assumption has been contradicted by recent findings that policy gradient methods can indeed prove to converge to global optima, at least in the tabular setting. In particular, the standard softmax PG method with a constant learning rate has been shown converge globally optimal policy at (11/t) rate for finite MDPs [2], albeit with challenging problem and initialization dependent constants [3, 4]. Several techniques have been developed further improve standard PG and achieve better rates and constants. For example, adding entropy regularization has been shown to produce faster ( =f convergence (c > 0) to the optimal regularized policy [2, 5, 6]. By exploiting natural geometries based on Bregman divergences, natural PG (NPG) mirror descent (MD) have been shown to achieve better constants than standard PG [7, 5] and faster O rates, with [5, 6) and without regularization [8]. Alternative policy parameterizations. such the escort parameterization. have been shown to improve the constants achieved by softmax and yield faster plateau escaping [3].
Coorespondence to: Jincheng Mei and Csaba Szepesvári {jmei2, www.ssseaaaaaaaeeeeeeeeee
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

More recently, geometry- normalized PG (GNPG) approach has been proposed to exploit the non-uniformity of the value function, achieving faster O eft rates with improved constants [9].
A key observation is that each of these four techniques- (i) entropy regularization, (ii) NPG (or MD), (iii) alternative policy parameterization, and (iv) standard softmax PG by better exploiting the geometry of the optimization landscape. In particular, entropy regularization makes the regularized objective behave more like quadratic [2. 5, 6], which significantly improves the near-linear character of the softmax policy value [2]. Natural PG (or MD) performs non-Euclidean updates in the parameter space, which is quite different from the Euclidean geometry characterizing standard softmax PG updates 57 8]. The escort policy paramcterization induces an alternative policy-pai parammeer relation [3]. GNPG exploits the non- uniform smoothness in the optimization landscape via a simple gradient normalization operation [9].
acceleraass the convergence of
However, these advantages have only been established for the true gradient setting. A natural question therefore is whether geometry can also be exploited to accelerate convergence to global optimality in stochastic gradient settings. In this paper, we show that in certain fundamental sense, the answer is no. That is, there exists a fundamental trade-off between leveraging geometry to accelerate convergence and overcoming the noise introduced by stochastic gradients (possibly infinite); in particular, no uninformed algorithm can improve the (1/(t) convergence rate without incurring a positive probability of failure (i.e. diverging or converging
sub-optimal stationary point).
The conditions used in vanilla stochastic gradient convergence analysis, i.e., unbiased and variance- bounded gradient estimator [10], has been exploited to attempt explain such trade-off in policy gradients [11, 6]. However, the bounded variance requires the sample policy to be bounded away from zero everywhere, which is impractical. Meanwhile, variant of NPG can converge even with unbounded variance [12]. These gaps raise the question that if not the bounded variance, then what is the key factor to ensure the convergence of stochastic policy optimization algorithms? Motivated by this question, we introduce the concept committal rate to characterize the update behaviors, which significantly affect whether convergence to a correct solution can be guaranteed in the stochastic on- on-policy setting. In particular, we make the following contributions.
First, we illustrate the anomaly that the preferability of policy optimization algorithms (softmax PG vs. NPG and GNPG) changes dramatically depending on whether true versus on-policy stochastic gradients are considered, and reveal the impracticality and unnecessity of a bounded variance requirement in Section 2;
Second, we introduce the concept of the committal rate in Section 3 to characterize the aggressive- ness of update, which provide us tools for analyzing the stochasticity effect convergences; the committal rate to study general stochastic policy optimization behaviors
Third,
rigorously and reveal the inherent geomelry--oovergencc trade-off in Section 4;
Finally, we explain the sensitivity to random initialization in practical policy optimization algorithms. From these results, then develop an ensemble method that can achieve fast convergence to global optima with high probability in Section
2 Understanding Algorithm Preferability in On-line Policy Optimization
To illustrate the key aspects of policy optimization methods and their comparative preferability, it suffices to consider deterministic, single-state, finite-action Markov decision processes (MDPs). The main results extend to general finite MDPs, but for clarity of exposition we restrict attention to one-state MDPs.
A deterministic, single-state, Umite-action MDP can be simply be specified by action space is [K] == {1, 2....A K} and a K-ddmmnsional reward vector r e @ The problem to maximize the expected reward of parametric policy mo.
max E 6: K R am)))))
[r(a)]-
where is parameterized by 0 using the standard softmax transform,
cxp(O(a))
Te = EnrE(K) exp()(a'))
for all a E [K].
(2)
2

---

Without loss of generality, we assume there exists a unique optimal action a" arg ue r(a), hence there exists a unique optimal deterministic policy x¹ such that x' SuPøER* T. - r(a"). We make the following assumption on the reward.
Assumption (Positive reward). r(a) E (0, 11. Va E [K].
2.1 Exact Gradient Setting
is known that Eq. (I) is a non-concave maximization over the policy parameter 0 [2]. Nevertheless, it has recently become better understood how policy gradient (PG) methods still converge to global optima for Eq. (1) when exact gradients are used. To illustrate the main considerations, we focus on the following three representative algorithms that have recently been proved to achieve convergence to global optima but at different rates: softmax policy gradient (PG), natural PG (NPG), and geometry- aware normalized PG (GNPG), while similar conclusions can be drawn for other variants [12, 13].
2.1.1 Softmax PG
The standard softmax PG method specified by the following update.
Update 1 (Softmax PG, true gradient). B.41 t 0 + 17- d0, where dsg
dxa,"
(diag(#o) (
and thus
dx,r
(a(a) (r(a) T. r) for all E [K]. ab(a)
As shown in Mei et al. [2], the convergence of this update to a globally optimal policy, given exact gradients, can be established by considering the following non non-uniform Lojasiewicz (NE) inequality,
Lemma (NL, [2].
ds
z To (a") (TT -m0) Tr. r.
do
By considering smoothness of nh r. Mei et al. [2] shows that the progress in each iteration of PG can be lower bounded by the squared norm of the gradient,
drg." do. 2 which leads to a O(1/t) rate.
Proposition 1 (PG upper bound [2]). Using Update I with 17 2/5, we have (m* S (c(-tt for all t 2 1, such that c = inf No, (a") > 0 is a constant that depends on r and 02, but it does not depend on the time t. In particular, if To, (a) 1/K Ya then 2 1/K.
Proposition 2 (PG lower bound [2]). For sufficiently large 1. 2 1, Update with 1) E (0. 1] exhibits (6-t), t), where A = r(aa) max r(a)= > 0 is the reward gap of (I* - 2 A 16-6/666
Remark 1. The constant dependence of PG follows a (((1/c) lower bound for one-state MDPs [3].
while e can be exponentially small in terms of the number of states for general finite MDPs [4].
To summarize, using !) E O()), softmax PG achieves convergence global optima, but with ((1/l) rate that exhibits poor constant dependence.
2.1.2 Natural PG (NPG)
An alternative method, natural PG (NPG) [14], provides the prototype for many practical policy optimization methods, such as TRPO and PPO [15, 16]. NPG is based on the following update.
Update 2 (Natural PG (NPG), true gradient). 0.+1 + 0g + rr..
For softmax policies, it turns out that Update 2 is identical to mirror descent (MD) with Kullback- Leibler (KI.) divergence. Therefore a standard MD analysis shows that Update 2 achieves convergence to global optimum at rate of ((1/t) [7]. Very recently, work concurrent to this submission [8] has shown that Update actually enjoys a much faster ((e-ot) rate. In fact, here too we can establish the same O rate, but using simpler argument based the following variant of the NL inequality for natural gradients. These results are new to this paper. Due to space limitation, we postpone all the proofs to the appendix.
Lemma (Natural Nł. inequality, continuous).
dd do 2 TO (a() A (IT - mo) TT.
Lemma (Natural NE, discrete), Let ा. (a) Ee a(a') re
V E [K]. where n7 > 0. Then, ((r()
( T) r
(T ④) r.
(3)
T(a)) (e - 1
3

---

In particular, by using non- Euclidean update and analysis, the progress of each iteration of NPG can
be lower bounded by the larger bound < dre,"" do, r) instead of the weaker bound
dma
established
de
for standard PG. Based on this inequality, one can easily establish a much faster O(e (e) convergence
to globally optimal solution for NPG, making it far preferable to PG if true gradients are available.
Theorem (NPG upper bound). Using Update with any vi > O, we have, for all 2 1,
(T -
)o.) -mB.)
S (TT -mo,) ree e-
(4)
where c log (To, (a*) (e 1) + > for any and r(aa) maxa r(a) >
2.1.3 Geometry-aware Normalized PG (GNPG)
The Geometry-aware Normalized PG (GNPG) update is investigated in [9] to accelerate the conver- gence of PG by exploiting local smoothness properties of the optimization landscape.
dr,
Update 3 (Geometry-awan) Normalized PG (GNPG), true gradient). 0.+1 < 0,+1
db,
d0
The analysis in [9] focuses exploiting non-uniform smoothness (NS) rather than improving the NE inequality as for NPG above.
Lemma (NS, (9). The spectral radius of Hessian matrix d'z.r do²
is upper bounded by 3 d=
Given this NS property, [9] shows that the progress in GNPG can be lower bounded by the larger d
instead of the weaker d for standard PG. Then, using the same Nł dec
quantity de:
inequality as for PG, GNPG also converges to a globally optimal solution at rate O(e-at). Again, one naturally concludes that GNPG is preferable to PG if exact gradients are used.
Proposition 3 (GNPG upper bound [9)). Using Update 3 with vi = 1/6, we have, for all L 2 1,
To. TT. S (TT To.) r- -0
(5)
where c inf: ne, (a*) > does not depend on I. To, (a) = 1/K, Va, then e 2 1/K.
2.2 The Anomalous Behaviour of Some On-policy Stochastic Gradient Updates
Although the above results show that exploiting geometric information can allow linear convergence an optimal solution given true gradients-obvioute O represents an exponential speedup over the (2(1/t) lower bound for standard PG-it is critical to understand whether such advantages can also be obtained in the more natural stochastic gradient setting. Given the previous results, would seem natural to prefer accelerated algorithms over PG in practice, and there is some evidence that such thinking has become mainstream based on the popularity of TRPO and PPO over PG. Indeed, TRPO and PPO are often interpreted as instances of NPG and the faster convergence of NPG used to explain their empirical success. However, by more closely examining the behavior of these algorithms when true gradients are replaced by on-policy stochastic estimates, serious shortcomings begin to emerge, as empirically observed in Chung et al. [12], and it is far from obvious that similar advantages from the true gradient case might be recoverable in the more practical stochastic scenario.
We begin by examining the behavior of the previous algorithms in the context of on-policy stochastic gradients. To enable this analysis, first note that each of the above PG methods, Updates 1 to 3, can be adapted to the stochastic setting by using on-policy importance sampling (IS) provide an unbiased estimate of the true reward. We do not make assumptions like each action is sufficiently explored, since ne is the behaviour policy as well as the policy to be optimized. It is possible that wo, approaches near deterministic policy, ruling out positive results based on such assumptions [1 [1]].
Definition (On-policy IS). At iteration t, sample one action ag ~ (.) The IS reward estimator A is constructed as Pa(a) 1(a;=a) .r(a) for all a E [K].
(a)(a)
We consider sampling one action in each iteration, but the results continue to hold for sampling a constant B > 0 mini-batch of actions. A significant limitation of our results is that the reward is observed without noise, which is an idealized case. remains to seen which conclusions of this work can be extended to the more general case when the rewards are observed in noise.
Remark 2.

---

In the next subsections we consider the mentioned three on on-policy update rules. As we shall see, only the first update rule, vanilla policy gradient with softmax parameterization is sound.
2.2.1 Softmax PG
dug. Fr Update 4 (Softmax PG, on-policy stochastic gradient). Oc+1 + Oc + 17 do, Tg, (a) (fr(a) - ft) for all a E [K].
where da (a)
Using the IS reward estimate, the softmax PG is unbiased and bounded by constant:
Lemma 5. Let be the IS estimator using on-policy sampling a ~ TT(.). The stochastic so sofimax PG estimator is unbiased and bounded, i.e., Ba
da
dagr
and (a-To(() db
dmg
F
2.
do
These observations imply that stochastic softmax PG converges to a global optimum in probabil- ity. which also proved by Chung et al. [12]. Here use the non-uniform smoothness in O(L/Vt) + 0 as f + oc, which implies that lim Pr (TT" To.) r>0) - 0, i.e., sub-optimality converges to in probability.
Lemma 4 to prove that LE (a))),, (T* )
Theorem 2. Using Update 4, (n* Te.) T r- 0 as t - oo in probability.
2.2.2 NPG
Similarly, we can use on-policy IS estimation to adapt NPG the stochastic setting.
Update 5 (NPG, on-policy stochastic gradient). 0++1 + 0₂ + -
Although the NPG is unbiased, its variance can be possibly unbounded in the on-policy setting, Lemma 6. For NPG, we have, Ea-rs() [F] and Ex ||A]|2 = Ene(K] r(a)² ma(a)'
The variance becomes unbounded (a) O, which predicts trouble when using the standard analysis for stochastic gradient methods (e.g.. [10]). fact, we provide a more direct result showing that stochastic NPG has positive probability of converging
sub-optimal deterministic policy.
Theorem 3. Using Update 5, we have: (i) with positive probability, Enja. To, (a) + 1 as t + oo; (ii) Va [K]. with positive probability, (a) + 1, as t + oc.
This result extends the result of [12] for the two-action (K 2) case only. The intuition is that the stochastic NPG accumulates too much probability on sampled sub-optimal actions and cannot recover due to the "vicious circle" between sampling and updating.
2.2.3 GNPG
Finally, we consider the stochastic version of GNPG.
dx P4 d0,
d
Update 6 (GNPG, on-policy stochastic gradient). 0.+1 +- 0g + 17
Unfortunately, this estimator involves a ratio of random variables, and its bias can be large. As for NPG show that stochastic GNPG fails with positive probability in the stochastic case.
Theorem 4. Using Update 6, we have, Va E [K], with positive probability, To, (a) + 1, as a oc.
2.3
Why Consider the On-policy Stochastic Setting?
The findings of the previous sections are summarized in Table 1. The two methods that converge faster when the exact gradient available are exactly those that fail in the worse possible way in the on-policy setting. This raises the question of should one even consider the on-policy setting?
One possible reason consider this setting because on-policy sampling is the simplest and most straightforward approach to extend algorithms developed for the "exact gradient" setting and with
'Standard treatment of stochastic approximation algorithms does deal with unbounded noise in controlled way to still get positive results [17], which means that bounded variance is far from being necessary.
5

---

Softmax PG
NPG
GNPG
converges Ole (()-
converges O )
True gradient
converges (1/()
V/V
Stochastic on-policy
converges in prob. fails w.p. 0X
fails w.p. 0x
Table Convergence properties of softmax PG, NPG and GNPG in the alternative settings.
minor twist, Occam's 's razor dictates that one should consider simple solutions before considering more complex ones. Indeed, off-policy algorithms are more complex with many more choices to be made and while having the extra freedom may ultimately be useful (and even perhaps necessary), it is worthwhile to first thoroughly examine whether this complexity can be avoided. Indeed, there is some empirical evidence that the simple, on-policy approach may sometimes be reasonable one: The method PPO [16] uses on-policy sampling and yet, remarkably, it achieved outstanding results on challenging tasks, a good example of which is to learn dexterous in-hand manipulation [18].
second reason is that the on-policy setting presents unique challenges and as such is interesting on its own for learning about how to design and reason about stochastic methods. Indeed, the standard approach in analyzing stochastic update rules, such as SGD, is to start with the assumption that the unbiased and have uniformly bounded variance. This has been used both in the analysis of SGD [10], and later adopted to policy gradient methods [11, 6. 19, 20]. However, such conditions are only sufficient and not necessary the numerous results in the literature of the analysis and design of stochastic approximation methods also show [17]. In fact, the bounded variance assumption can be difficult to satisfy. For example, in the problems studied here this assumption requires that the probabilities induced by a behaviour policy are bounded away from 0 everywhere [12], which is impractical for large state and action spaces and impossible when they are infinite.
gradient estimates
Another observation that suggests that it is worthwhile to consider methods which potentially unbounded variance is made by Chung et al. [12] who explored the role of baselines in policy opti- mization. They show that variance reduction techniques are not able to overcome unbounded variance, while NPG can still achieve global convergence almost surely with a judicious choice of baseline even though its variance remains unbounded (see Update 7 for details). This is another example that shows that bounded variance is not necessary for convergence, and some other factors rather than variance account for the convergence behaviour of stochastic policy optimization algorithms.
This leave us important question to be answered to bridge the gap between theory and practice,
What are the key factors determining the convergence of stochastic policy optimization?
As an answer to this question we propose new notion, the committal rate of policy optimization methods and will demonstrate that small committal rates are necessary to ensure the convergent behavior of policy optimization methods.
3 Committal Rate of Stochastic Policy Optimization Algorithms
Although the baseline study [12] only focuses on two- and three-action bandits primarily, it develops useful intuition that stochastic policy optimization in practical settings consists of separate "sampling" and "updating" steps that become coupled in the on-policy setting. Building from this observation, and seeking to explain the outcomes in Section 2, we formalize the following "committal rate" function of a policy optimization algorithm. The main idea is to decouple the "sampling" and "updating" by fixing sampling one action and characterizing the aggressiveness of an update in a deterministic way. Thus, in what follows, by policy optimization algorithm A we mean a mapping from all sequences of pairs of action-reward pairs to the set of parameter vectors.
Definition (Committal Rate). Fix reward function E 10, and an initial parameter vector 01 E R Consider policy optimization algorithm A. Let action a be the sampled action action,foreve forever after initialization and let Og the resulting parameter vector obtained by using A on the first t. observations. The committal rate of algorithm A on action a (given r and 02) is then defined as
x(A,a) = sup 2 20: supt t 11- [a) <00
(6)
t-000
Note that in the definition we have suppressed the dependence of k on the rewards and the initial parameter vector. Definition 2 accounts for how aggressive an update rule is: An algorithm with

---

committal rate a will make тo, (a) approach 1 at the polynomial rate of 1/t" provided that the sampling rule only chooses action a. Thus, a larger value of x(AA, a) indicates an algorithm that quickly commits to the action a. For example, if no, (a) = 1 1/(L log (4)), then k(A, a) = 1. Similarly, if To, (a) = 1 - 1/e", then s(A..) a) = oc, which means no, (a) approaches extremely quickly. On the other hand, if 1 Te, (a) E (1))). then x(A,, a) = 0, implying that To, never becomes committal, since Te, (a) never approaches 1.
Our next results shows that a small committal rate with respect to sub-optimal actions is necessary for almost sure convergence to globally optimal policy.
Theorem 5 (Committal rate main theorem). Consider a policy optimization method A, together with r E (0, 1] and an initial parameter vector 01 E IRK, Then,
max a: a <r(a" 1, (a)>0
a(A,a) 1
is a necessary condition for ensuring the almost sure convergence of the policies obtained using A and online sampling to the global optimum starting from 01.
In words, Eq. (7) shows that slow reaction to constantly sampling sub-optimal actions is necessary for the success of policy optimization methods when they are used with online sampling.
Using this result, we can now interrogate the committal rates of the previously listed algorithms. Theorem 6. Let Assumption holds. For the stochastic updates NPG and GNPG from Updates 5 and 6 we obtain k(NPG, a) = co and k[GNPG, a) 5o for all a E [K] respectively.
Theorem 6 explains why stochastic NPG and GNPG have a non-zero failure probability in the on- policy stochastic setting: they do not obey a necessary condition for almost sure global convergence. Intuitively, these algorithms can fail by prematurely allocating too much probability to a sub-optimal action: each sampling of an action E [K] increments its parameter by ((1), so if is sampled t times successively, then we have 1 - no, (a) E O(e-ot), which means x(AA, a) = oc. According to Theorem 5, there is a positive probability that single sub-optimal action can receive a long enough sampling run to ensure the other actions will never again be sampled.
By contrast, we can compare these outcomes to the committal rate of the softmax PG algorithm. Theorem 7. Let r(a)= and iTa (a) O. Sofimax PG obtains x(PG, a) for all a [K].
Theorems 5 and 7 provide (partial) explanations of the observations Section 2: stochastic NPG and GNPG can fail while PG almost surely converges to global optimum, but their committal rates lie on different sides of the necessary condition. Since x(GG, a) = for softmax PG, follows that Ih no, (a) = 0 (see Lemma 18), hence it is not possible to sample sub-optimal actions forever, and the optimal action a" always has a sufficient chance to be sampled, which ensures learning.
Next, following [12], we consider NPG using an "oracle baseline", which assumes the knowledge of the gap A. Chung et al. [12] considered this baseline to point out that convergence in on-policy stochastic gradient methods can happen even if the variance of the gradient estimates "explodes":
Update 7 (NPG with oracle baseline). 0,t1 + 0₂ + n7 (fa- bb.), where (a = ([aa==a) - 1)
(0) (a)
for all a E [K] and E (r(a*) - r,r(()))
Theorem 8. Using Update 7, (TT - TT.) r 0 as L - x with probubility 1.
As noted, while the variance of the updates provably explodes [12], the necessary condition in Theorem 5 satisfied. Indeed, if or * a", Te, (a;) < Te, (at), while the optimal action's probability always increases after any update. Therefore, we have x(A,a") for all a * a. This example shows that the committal rate gives useful information regardless of whether the variance of the update stays bounded.
and k(A, a) 0
4 The Eeooetry-Convenn
Trade-off in Stochastic Policy Optimization
Theorem 7 raises the question of whether x(A, a) S for all sub-optimal actions a E [K] is sufficient to ensure an algorithm A converges to optimal policy almost surely. Unfortunately, this is not the case, and the complete picture of global optimality in stochastic policy optimization more complex and requires detailed study of different iteration behaviors.
7

---

4.1 Iteration Behaviours
Remark 3. The condition that k(A.,) o) S for all sub-optimal actions a E [K] is not sufficient for ensuring almost sure convergence to global optimality. In addition to "convergence to sub-optimal policy with positive probability" and "convergence to a globally optimal policy with probability 1" there exist other possible optimization behaviours, such as "not converging to any policy".
In partieular, consider the following update behaviors.
Staying. For the stationary update A: : lc+1 t- 0g we obtain x(AA, a) = =0 1 for all a E [K], yet To, n0, does not converge the optimal policy nor any sub-optimal deterministic policy.
Wandering (NPG with a large baseline). Consider A Oc+1 + 02 + (fr - b1) with by(a)
[ar=a) -1) b for all a E [K]. b > r(a"). then we have 1 (at) < 00, (at), i.e., selected [ay(a)
action's 's probability will decrease after updating, hence k(A,,) a) = 0 for all a E [K] However, Te, To,(a) (a) A 1 as oc for all e [K]. therefore Te, will wander within the simplex forever.
The above examples show that not converging to a sub-optimal policy does not necessarily imply converging optimal policy almost surely, and stronger condition is needed to eliminate unreasonable behaviors like 0.+1 + 6,. We leave it as an open question to identify necessary and sufficient conditions for almost sure convergence global optimum.
4.2
Geometry-Convergenn Trade-off
In Section 2 we see that NPG and GNGP can use true gradients to significantly accelerate PG by better exploiting geometry. However, in the stochastic setting, any estimated geometry might be inaccurate, and intuitively, accelerated methods risk leveraging inaccurate information too aggressively. On the one hand, if progress is sufficiently fast (i.e., with large committal rate), then an algorithm might never recover from aggressive yet inaccurate updates (Theorem 5). On the other hand, large progress is necessary for fast convergence. The tension between these observations suggest that there might be an inherent trade-off between exploiting geometry and avoiding premature convergence in stochastic policy optimization. We formalize this intuition with the following results. For the first result, need to restrict to the class of policy optimization methods that do not decrease the probability of the optimal action whenever that action is chosen: In particular, policy optimization method is said to be optimality obtained when a" is chosen in every time step, starting at 01. while 0g is any parameter vector that can be obtained with updates (regardless of the action sequence chosen), but also starting from 01. Theorem 9. Let A be optimality- aptimality-smart smart and pick bandit instance. If A together with on-policy sampling leads to h12) such that {Te, J121 converges to a globally optimal policy at a rate O(1/19) with positive probability, for a >> O, then k(A,,a) 2 a.
if for any 2 1, TT. (a") 2 To, Ta,(a") holds where 6g is the parameter vector
This theorem implies that a large committal rate for the optimal action is necessary for achieving fast convergence to the globally optimal policy, since the sub-optimality dominates how close the optimal action's probability is 1, i.e., (x* Te. ) r 2 (1- ne, (a*)) A. Therefore (л* Te, ) r O(1/t)) implies 1 Te, (a") E O(1 Combining this result with Theorem 5 formally establishes the following inherent trade-off between exploiting geometry to accelerate convergence versus achieving global optimality almost surely (aggressiveness vs. stability).
optimality-sman and <(A, a²) = k(A, a) for at least one + a², then A with on-policy sampling can only exhibit at most one of the following two behaviors: (i) A converges to a globally optimal policy almost surely; (ii) A converges to a deterministic policy at a rate faster than O(/[l) with positive probability.
Theorem 10 Cecometry-Convergenee
trade-off). If an algorithm
In other words, if has chance to converge to a global optimum, then either A converges to the globally optimal policy with probability (.A is stable) but at rate no better than O(1/t), or it achieves a faster than ((1/t) convergence rate (AA aggressive) but fails to converge to the globally optimal policy with some positive probability. This trade-off between the geometry and convergence faced by any stochastic policy optimization algorithm that is not informed by external oracle information that allows it to distinguish optimal and sub-optimal actions based on on-policy samples.
8

---

Remark 4. Theorem 10 implies that an algorithm can achieve at most one of the mentioned two results. It possible that an algorithm achieves neither (e.g., staying or wandering).
4.3 Exploiting External Information
In Theorem 10, the condition of k(AA, x(A,,) a) for least one sub-optimal action a E [K] is necessary for the trade-off to hold. If this condition can somehow be bypassed, then it is possible to simultaneously achieve faster rates and almost sure convergence to a global optimum. For example, consider Update 7. As mentioned before, we have k(A, a²) = oc and s(A,a) = O for all o a", breaking the mentioned condition, which allows A to enjoy almost sure global convergence as well as O(e rate. Of course, such fortuitous outcome required very specific bascline that is aware of both the optimal reward and the reward gap. Without introducing external mechanisms that inform an on-policy algorithm it appears that such information cannot be recovered sufficiently quickly from sample data alone [21]. Nevertheless, remains an open question to prove that this is not possible, or whether some other strategy might allow on on-policy stochastic policy optimization algorithm to avoid the condition of Theorem 10 and achieve both fast rates and almost sure global convergence.
Property I
x(A,a) >1
<(A, a) $
all sub optimal action
[K]
NPG
Softmax PG
Staying
Algorithm
Wandering
NPG cenci lassiin
GNPG
SAMBA
(NPG laage baseinc))
Property 11
<(A.at) x(A,a). for at least one sub-optimal action a [K] <(A,a") *(A.a))
Figure I: Different algorithmic behaviours subdivided by two properties of committal rate. SAMBA [13] does not use parametric policies and is discussed in the appendix.
Figure summarizes all the iteration behaviours we studied this paper, organized by two properties of committal rate: (i) possible failure if x(AA, a) > 1 for at least one sub-optimal action o; and (ii) an inherent geometry-convergent
trade-off if x(AA, a²) = x(A, a) for at least one sub-optimal action a. It remains open to study where other algorithms suit themselves in this diagram.
Initialization Sensitivity and Ensemble Methods
We use the committal rate to further reveal mystery observed in practice about the initialization sensitivity [22]. With the understanding of this unavoidable phenomenon, we introduce ensemble method and quantitatively characterize the successful rate in terms of number of trials.
5.1 Initialization Sensitivity
has been observed empirically that RL algorithms are sensitive to initialization in practice: the same algorithm can produce remarkably different performance given different random seeds [22]. Some existing work has attempted to explain initialization sensitivity due to the softmax transform [3], but such results only hold for true gradients and apply to standard PG methods.
Using the committal rate theory developed above, we can provide new explanation and additional understanding of the initialization sensitivity of practical policy optimization algorithms. Most well- performing policy optimization algorithms in practice, such TRPO and PPO [15, 16], are based on NPG, which exploits geometry to accelerate PG in true gradient settings. However, according to Theorem 10, such fast convergence must incur a positive probability of failing to reach global optimum, even in bandit settings. Therefore, the need to attempt multiple random seeds to achieve success is an unavoidable consequence of using these algorithms according to this theory.
5.2 Ensemble Methods
The committal rate theory also explains why ensemble methods [23-25], iee, running policy optimization algorithm in multiple parallel threads and picking the best performing one, can provably work well. This is because fast algorithm for the true gradient setting can have positive probability of success or failure across different initializations while always converging quickly. In which case,

---

multiple independent runs can then be used to reduce the failure probability to any desired positive value, while retaining efficiency (if full parallelism can be maintained).
Theorem 11. With probability 1 - ó, the best single run among O(log (1/6)) independent runs of NPG (GNPG) converges to a globally optimal policy at an O -et) rate.
It is known that softmax PG can get stuck on long plateaus for even true gradient settings [3, 4], which means almost sure global convergence does not necessarily imply good practical performance. Therefore, it is reasonable choice to perform well with the compromise of small failure probability. Here we consider simply best selection, and it remains open to understand other practical training tricks, such as proximal update [16, 26] and regularization [27] under stochastic settings.
6 Discussions
6.1 Sufficient and Necessary Conditions for Almost Sure Global Convergence
We make the following conjecture with some intuitions for the sufficient and necessary condition for global convergence, a question left open in Section 4.
Conjecture 1. Given stochastic policy optimization algorithum A, x((, x(A,,) a) for at least one sub-optimal action a, then st(A, a²) E (0, is a sufficient and necessary condition for global convergence x= with polynomial convergence rate of (1/11)) where a 0.
The necessary condition is from Theorem 5. For the sufficient condition, Theorem 9 can potentially be strengthened to x(,A,,' a²) is sufficient and necessary condition for global convergence rate O(1/t²) (a > 0). The observation here is that Assumption leads to (TT* -x,)) S To, (a*). This suggests that if =a, (a") E O (1)))), then (x* - To,) r E 0(1/(9). However, a gap here is m(A, a²) 2 means "1 Te, (a*) E 0(1/19) if we fix sampling a" forever", and it is not clear if this implies "1 - Te, (a*) ) E O(1/t") if we run the algorithm A using on-policy sampling ne, (.)".
6.2 Lower Bounds in Bandit Literature
In the bandit literature [28]. the 2(og 7') result implies that the convergence speed in terms of sub- optimality ("average regret") cannot be faster than O(1/t). However, the lower bound construction there holds for stochastic reward settings. Theorem 10 holds for simpler optimization setting: the reward is fixed and deterministic, but the policy gradient is estimated by on-policy sampling. There- fore, the difficulty and trade-off are from the restriction the action-selection scheme (balancing the aggressiveness and the stability), not from estimating or tracking the reward signal.
6.3 General MDPs
The one-state MDP results already show the main findings, since large portion is about constructing counterexamples showing that the stochastic policy optimization algorithms do not perform well as in the true gradient setting. A counterexample for one-state MDPs is also a counterexample for general MDPs. Therefore, there is no loss of generality by establishing negative results using one-state MDPs. We include extensions to general finite MDPs in Appendix E for completeness.
7 Conclusion and Future Work
This paper introduces the committal rate theory, which not only explains why faster policy optimiza- tion algorithms in the true gradient setting become dominated by slower counterparts in the on-policy stochastic setting, but also reveals an inherent optimization. The theory also explains empirical observations of sensitivity random initialization for practical policy optimization algorithms as well as the effectiveness of ensemble methods.
trade-off in stochastic policy
One interesting future direction is to study necessary and sufficient conditions for almost sure global convergence, which could weaker than the bounded variance assumption. Another important direction is to investigate whether other techniques might be used in on-policy settings to break the condition of Theorem to achieve almost sure global convergence with a fast rate. One also expects that some generalized versions of committal rate would be meaningful in stochastic reward settings.
10

---

Acknowledgments and Disclosure of Funding
The authors would like to thank anonymous reviewers for their valuable comments. Jincheng Mei, Bo Dai and Dale Schuurmans would like to thank Lihong Li for helpful early discussions. Jincheng Mei and Bo Dai would like to thank Nicolas Le Roux for providing feedback on a draft of this manuscript. Jincheng Mei would like to thank Michael Bowling for carefully checking the paper draft in thesis chapter. Csaba Szepesvári and Dale Schuurmans gratefully acknowledge funding from the Canada CIFAR AI Chairs Program, Amii and NSERC.
References
[1] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, pages 1057-1063, 2000.
[2] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global con- vergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pages 6820-6822 PMLR, 2020.
[3] Jincheng Mei, Chenjun Xiao, Bo Dai, Lihong Li, Csaba Szepesvári, and Dale Schuurmans. Escaping the gravitational pull of softmax. Advances in Neural Information Processing Systems, 33, 2020.
[4] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Softmax policy gradient methods can take exponential time to converge. arXiv preprint arXiv:2102.11270, 2021.
[5] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. arXiv preprint arXiv:2007.06558, 2020.
[6] Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. arXiv preprint arXiv:2 2021.
[7] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approxi- mation with policy gradient methods in markov decision processes. In Conference Learning Theory, pages 64-66. PMLR, 2020.
[8] Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and Siva Theja Maguluri. On the linear convergence of natural policy gradient algorithm. arXiv preprint 1.XXi:2105.0144: 2021.
[9] Jincheng Mei, Yue Gao, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. Leveraging non- uniformity in first-order non-convex optimization. arXiv preprint arXiv:2105.06072 2021.
[10] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4): 1574-1609, 2009.
[11] Yasin Abbasi- Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. In International Conference on Machine Learning, pages 3692-3702. PMLR, 2019.
[12] Wesley Chung, Valentin Thomas, Marlos C Machado, and Nicolas Le Roux. Beyond variance reduction: Understanding the true impact baselines on policy optimization. arXiv preprint arXiv:2008. /3773, 2020.
[13] Denis Denisov and Neil Walton. Regret analysis of markov policy gradient algorithm for multi-arm bandits. arXiv preprint arXiv:2007. 10229, 2020.
[14] Sham M Kakade. A natural policy gradient. In Advances Neural Information Processing Systems, pages 1531-1538, 2002.

---

[15] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pages 1897, 2015.
[16] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
[17] Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive Algorithms and Stochastic Approximations, volume 22. Springer, 1990.
[18] OpenAl: Marcin Andrychowicz. Bowen Baker, Maciek Chociej, Rafal Jozefowicz, Bob Mc- Grew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, et al. Learning dexterous in-hand manipulation. The International Journal of Robotics Research, 39(1)33-20, 2020.
[19] Junzi Zhang, Jongho Kim, Brendan O'Donoghue, and Stephen Boyd, Sample efficient rein- forcement learning with reinforce. arXiv preprint arXiv:2010.11364 2020.
[20] Junyu Zhang, Chengzhuo Ni, Zheng Yu, Csaba Szepesvari, and Mengdi Wang. On the con- vergence and sample efficiency of variance-reduued policy gradient method. arXiv preprint arXiv:2102.08607, 2021.
[21] George Tucker, Surya Bhupatiraju, Shixiang Gu, Richard Turner, Zoubin Ghahramani, and Sergey Levine. The mirage of action-dependent baselines in reinforcement learning. In International Conference on Machine Learning, pages 5015-5024, 2018.
[22] Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
[23] Marco A Wiering and Hado Van Hasselt. Ensemble algorithms in reinforcement learning. IEEE Transactions Systems, Man, and Cybernetics, Part B (Cybernetics), 38(4):930-3))) 2008
[24] Whiyoung Jung, Giseung Park, and Youngchul Sung. Population- guided parallel policy search for reinforcement learning. In International Conference on Learning Representations, 2020.
[25] Jack Parker-Holder, Aldo Pacchiano, Krzysztof Choromanski, and Stephen Roberts. Effective diversity in population- based reinforcement learning. arXiv preprint arXiv:2002.006332 2020.
[26] Nevena Lazié, Botao Hao, Yasin Yadkor, Dale Schuurmans, and Csaba Szepesvári. Opti- mization issues in kl-constrained approximate policy iteration. arXiv preprint arXiv:2 2021.
[27] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap. Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforce- ment learning. In International conference machine learning, pages 1937. PMLR, 2016.
[28] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[29] Jalaj Bhandari and Daniel Russo. A note on the linear convergence of policy gradient methods. arXiv preprint arXiv:2007. / /20, 2020.
[30] Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58 (6):3586-3612, 2020.
[31] Konrad Knopp. Theory and Application of Infinite Series. Hafner Publishing Company, New York. 1947.
[32] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning.
In ICML, volume 2, pages 267-274, 2002.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "kg_oknCM-ix", "reviewer": "Reviewer_JR5d", "summary": "Summary\n\nThe authors show how the convergence rates of stochastic policy gradient algorithms can differ from the full-information/expected case. Even before diving into the stochastic case they prove a linear convergence rate for NPG in the expected setting. Then for the stochastic setting they show convergence of vanilla PG with probability 1. For NPG (and GNPG) they show that there is a strictly positive probability of converging to a suboptimal solution. To do so they introduce the notion of committal rate, a useful tool, not without some limitations that they discuss.\nMore generally they explicit the tradeoff between geometry and noise for RL which is a very important topic.\nFinally they propose a method using ensembles to show how we can still find the optimal policy for committal algoritms in high probabablity.\n\n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Clarity\n---\nI found the paper clear and well written.\n\nSignificance\n---\nI think this is a very important topic as we are seeing more and more convergence results in RL theory, mostly limited to\nthe expected case. This paper stresses how the stochastic case can be fundamentally different, and how convergence of the expectation does not translate to convergence in probability.\n\nMain review\n---\n\nHere are some thoughts and questions I would like the authors to discuss.\n\n1) I think I am missing something about the proof of Thm 7. You show in the appendix that kappa = 1 by showing it is both bigger and smaller than 1. \nThm5 only informs you that if kappa > 1, then probability of sampling any suboptimal action an infinity of times is > 0.\n(i) Where is the proof that this is 0 for the case kappa = 1?\n(ii) And once this is proven, how do you get to the result that the optimal action will be taken an\ninfinite number of times? \n\n2) Do you think the 1/t lower bound, was, in some way very unsurprising? For instance, we know that for bandit the regret is Omega(log(t)).\nLet us assume that V* - V_t = o(1/t) (small o notation), then we would have by\nsummation that regret = o(log t) which contradicts the lower bound on regret,\nhence V* - V_t = Omega(1/t).\nThis is a pretty handwavy proof (for bandits), but I suspect it might easy to\nformalize and extend to MDPs (as you ust need to extract a bandit problem from\nthe MDP to show the impossibility).\n\nUnder that light, could you then discuss the link between your lower bound result and the one on\nregret in bandits?\n\n3) In RL, contrary to supervised learning, the data distribution changes after each action taken, and this introduces new dependencies.\nThe variance of the parameter theta_t, will be composed of the variance of the gradients, but also of the different covariances between the gradients. \nIntuitively, the results of Chung and Thomas et al. even if not formalized that way, could be understood that choosing some baselines can guarantee convergence by ensuring this variance/spread is small (negative correlations) while some other baselines (including potentially the one that minimizes the variance of the gradient) cannot. \nI don't think committal rates in their current form can capture this accurately, this difference, do you have any idea how it could be extended to capture these effects?\n\n4) Could you clarify the following point: In the setting where we have a 2-arm bandit with deterministic rewards -1 and 1, then natural policy gradient will be guaranteed to increase the probability of the right action at each time step, and the convergence will be exponential. Therefore are your results about the O(1/t) rate for all MDPs?\n\nI will change my score accordingly depending on how these questions are answered.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Theoretical work, no societal impact to foresee.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Z8aeHMyY9k0", "reviewer": "Reviewer_FFTX", "summary": "This paper studied how stochasticity of on-policy evaluation affects the convergence speed of various policy optimization methods. The paper demonstrated an inherent trade-off between fast convergence versus achieving optimality almost surely.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper studied how stochasticity of on-policy evaluation affects the convergence speed of various policy optimization methods and demonstrated an inherent trade-off between fast convergence versus achieving optimality almost surely.\n\nIn particular, the authors proposed \"committal rate\" to characterize how fast the probability $\\pi(a|s)$ converges to 1 under some algorithm. When a sub-optimal state action pair has a committal rate greater than 1, the sub-optimal may be sampled forever and hence leads to sub-optimality. On the other hand, the convergence speed to the optimal policy is also characterized by the committal rate of the best state-action pairs. Therefore, any algorithm that fails to give highest committal rate to best actions must face the trade-off between fast convergence versus achieving optimality almost surely.\n\nHowever, the reviewer has some doubts when verifying some Theorems and the proofs:\n1. Theorem 3 says \"there is a positive probability that $\\pi_{\\theta_t}(a) \\to 1$, $\\forall a\\in [K]$\". Does it mean to say \"$\\forall a\\in [K]$, there is a positive probability that $\\pi_{\\theta_t}(a) \\to 1$\"?\n\n2. At the first glance, the proof of Theorem 3 seems to be saying \"When $a$ is always sampled, then with a positive probability $a$ is always sampled\". Reorganizing the proofs would fix the issue.\n\n3. The lower bound of the probability of \"$a$ is always sampled\" (173) is roughly at the order $O(\\exp(-|A|/\\eta))$. Is it reasonable to say that the event is negligible when $|A|$ is large or $\\eta$ is small? If so, the discussion in section 5.1 can be misleading, since the \"positive probability\" can be fairly small.\n\nTypos:\nLine 60, \"the a\";", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "6OXwl_gZc6", "reviewer": "Reviewer_RnW5", "summary": "This paper studies the convergence of various policy gradient methods. The authors introduce a novel conception, the committal rate, to characterize the convergence speed and convergence quality of policy gradient methods, which is defined as the speed of the policy on a particular action converges to 1. For a simple MDP with 1 state, the authors show that the committal rate can explain the phenomenon that faster convergent algorithms using true policy gradients can be dominated by slower ones in the stochastic setting.   \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In general, the paper is well written and easy to understand. The insight on the committal rate is also novel and very helpful for researchers to understand the connections and differences among different policy gradient methods. One drawback is the paper did not provide the discussion on the generalization to more common MDPs with more than one state. Another point that could be potentially more interesting as stated in the conclusion part is to identify the sufficient conditions and necessary conditions for such type of methods to converge using the committal rate theory. \n\nWhy do we need the importance sampling estimator since the action is chosen from the same policy we want to evaluate?\n\nIn Definition 2, is it correct that you need to specify that kappa (or equivalently alpha) is a constant that does not depend on t? Otherwise, it is easy to construct counter examples by setting $\\kappa(A,a)$ to be a function of t, where the examples presented in Line 233-236 are not true. Moreover, in Line 235, it should be “if $1-\\pi_{\\theta_t}(a) \\in O(1)$, then $\\kappa(A,a)=0$”, since $\\pi_{\\theta_t}(a)$ itself can be O(1), just like in the previous two examples you mentioned. \n\nIn the proof of Theorem 5, at the last line, how do you guarantee that $\\pi_{\\theta_t}(a)>0$ for all t? Does this mean the general algorithm A here should not have any truncation procedures? \n\nTheorem 6 claims that $\\kappa(A,a)=\\infty$ for all actions. By the definition of kappa, does this mean $\\pi_{\\theta_t}(a)$ converges to 1 for all actions? However, this obviously seems wrong.\n\nTypos:\nLine 60: “the a variant ...”\nLine 129: “can *be* lower bounded”\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "One drawback is the lack of discussion of how the proofs of Section 3 can be generalized to more common MDPs, which have more than 1 state. It is unclear whether the conclusions made in Section 3 about the committal rates of PG and NPG hold in more general cases. \n\nI do not see any potential negative societal impact directly related to this work\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "5oUCAvwgCR", "reviewer": "Reviewer_ha89", "summary": "This paper aims to answer a fundamental question: what is the key factor that ensures the convergence of stochastic policy gradient (PG) methods? This question is built on the fact that bounded variance appears to be only a sufficient condition for convergence of the PG methods. To begin with, the paper starts by summarizing the existing convergence results of three PG methods, namely Softmax PG, Natural PG (NPG), and Geometry-aware Normalized PG (GNPG), in both the exact and stochastic gradient settings. Then, the paper proposes the notion of “committal rate” as an indicator for characterizing the convergence behavior of the PG methods. Accordingly, for one-state MDPs, the authors show that $\\kappa\\leq 1$ for all sub-optimal actions serves as a necessary condition for ensuring convergence as well as provide the committal rates of the three PG methods.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem studied in this paper is important and interesting, but I find the overall contribution of this paper quite limited due to the following issues with the theoretical results and presentation:\n\n- The theoretical results are not strong: Most of the main theoretical contributions are established only for one-state MDPs (Theorems 5-8 and 10). While it is okay to present the results in the main text using one-state MDPs for didactic purposes, these results are quite limited as the PG methods are typically used in the context of general MDPs. It remains unknown whether the results of the committal rate and their proof techniques can be extended to the case of general MDPs. On the other hand, the convergence results of Theorems 2-4 are mostly adapted from [12] (with some direct extensions).\n\n- The definition of committal rate in (6) seems problematic: Since $\\kappa$ involves $\\pi_{\\theta_t}(a)$ which is itself a random quantity and could vary with the sample path, then $\\kappa$ shall also depend on the underlying sample path. However, throughout the paper, $\\kappa$ is viewed as a deterministic value that depends only on the arm and the update scheme. Moreover, in Line 228, it is stated that “Let $t$ denote the number of times action $a$ is sampled after initialization.” This appears inconsistent with the notation of $\\pi_{\\theta_t}$, where $t$ is the total number of samples. Could the authors comment on this?\n\n- While the committal rate might provide some high-level intuition, it is unclear whether it offers any new insight into the characterization of the convergence behavior. Based on the definition in (6), the committal rate seems a bit tautological when being used to state “convergence to a sub-optimal policy”.\n\n- Regarding the presentation, I find Sections 4.2 and 4.3 not very informative. For example, Theorem 9 follows directly from the definition of the committal rate. Similarly, Theorem 10 also appears quite straightforward and provides very little new insight. As a result, this part can be greatly simplified for clarity.\n\n- In Section 2, it is mentioned that “The main results below extend to general finite MDPs, but for clarity of exposition we move details for general cases to the appendix.” This is a bit misleading as that a large portion of the theoretical results (cf. Theorems 5-8) are established only for one-state MDPs.\n\n- In Section 4.1, two examples are provided to show that $\\kappa$ does not serve as a necessary condition, but the examples are a bit artificial. Built on this, another interesting question is: Under which (non-trivial) class of algorithms does $\\kappa$ offer a necessary and sufficient condition for convergence? \n\nOther minor comments:\n- Line 178: Theorem 2 is adapted from [12]. It would be good to clearly mention this in the main text.\n- Line 813: It would be nice to directly provide the proof of Lemma 8 here for completeness. \n\n----- Post-rebuttal updates -----\n\nI’d like to thank the authors for the response. I have raised my score because the authors addressed my main concerns by:\n\n- Clarifying the definition of the committal rate for one-state MDPs\n\n- Clarifying the main results (i.e., Theorems 5, 9, and 10)\n\n- Extending the main result (i.e., Theorems 5) from one-state MDPs to general MDPs\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In the checklist, this paper mentions that it has described the limitations, but I did not see this part mentioned in any section.\t", "review_text": "", "extra_scores": {"ethical_concerns": "This paper does not raise any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the effect of stochastic on policy optimization in Reinforcement Learning, i.e., the impact of not having the true gradient. The paper argues that there are significant differences between the case of true gradient and a stochastic version. While this is not surprising, the reviewers agree that the paper makes a good contribution to the literature by pointing out the differences. There was some concern that many of the results are for a one-state MDP, but the reviewers felt that the paper makes some interesting points which can  potentially stimulate further work.  
Decision: Accept (Poster)