The Role of Baselines in Policy Gradient Optimization
Authors: Jincheng Mei
Wesley Chung
Valentin Thomas
Bo Dai
Csaba Szepesvari
Dale Schuurmans
Venue: NeurIPS 2022 Accept (2022)
Keywords: reinforcement learning
policy optimization
policy gradient
global convergence

Abstract: We study the effect of baselines in on-policy stochastic policy gradient optimization, and close the gap between the theory and practice of policy optimization methods. Our first contribution is to show that the \emph{state value} baseline allows on-policy stochastic \emph{natural} policy gradient (NPG) to converge to a globally optimal policy at an $O(1/t)$ rate, which was not previously known. The analysis relies on two novel findings: the expected progress of the NPG update satisfies a stochastic version of the non-uniform \L{}ojasiewicz (N\L{}) inequality, and with probability 1 the state value baseline prevents the optimal action's probability from vanishing, thus ensuring sufficient exploration. Importantly, these results provide a new understanding of the role of baselines in stochastic policy gradient: by showing that the variance of natural policy gradient estimates remains unbounded with or without a baseline, we find that variance reduction \emph{cannot} explain their utility in this setting. Instead, the analysis reveals that the primary effect of the value baseline is to \textbf{reduce the aggressiveness of the updates} rather than their variance. That is, we demonstrate that a finite variance is \emph{not necessary} for almost sure convergence of stochastic NPG, while controlling update aggressiveness is both necessary and sufficient. Additional experimental results verify these theoretical findings.


The Role of Baselines in Policy Gradient Optimization
Jincheng Mei
Wesley Chung? 2
Valentin Thomas 3
Bo Dai
Csaba Szepesvári 5, 5,
Dale Schuurmans 1,5
Google Research, Brain Team Mila, McGill University MMila, University of Montreal
*DeepMind
Amii, University of Alberta
(jcmei, bodai,
(wesley.chung2, vltn. thomas Hgmmal..ommi.ccom
Abstract
We study the effect of baselines in on-policy stochastic policy gradient optimization, and close the gap between the theory and practice of policy optimization methods. Our first contribution is to show that the state value baseline allows on-policy stochastic natural policy gradient (NPG) to converge to a globally optimal policy at novel
(1/tt) rate, which not previously known. The analysis relies findings: the expected progress of the NPG update satisfies a stochastic version of the non-uniform Eojasiewicz (NL) inequality, and with probability the state value baseline prevents the optimal action's probability from vanishing, thus ensuring sufficient exploration. Importantly, these results provide a new understanding the role of baselines in stochastic policy gradient: by showing that the variance of natural policy gradient estimates remains unbounded with or without a baseline, we find that variance reduction cannot explain their utility in this setting. Instead, the analysis reveals that the primary effect of the value baseline is reduce the aggressiveness of the updates rather than their variance. That is, we demonstrate that finite variance is not necessary for almost sure convergence of stochastic NPG, while controlling update aggressiveness is both necessary and sufficient. Additional experimental results verify these theoretical findings.
Introduction
The policy gradient (PG) 29 is key concept in reinforcement learning (RL), lying the foundation of policy-based and actor-critic methods, and responsible for some of the most prominent practical achievements in RL 27
28 However, progress in the theoretical understanding of PG methods is recent, and a number of the techniques used in practice still lack rigorous support, particularly in the online stochastic regime where an action is sampled from the current policy each iteration. We study stochastic policy optimization in more detail to close this gap between theory and practice.
In stochastic policy optimization, the two most common techniques for improving the basic algorithm are to include on-policy importance sampling (IS) and subtract a baseline. Including on-policy IS provides unbiased gradient estimates, but introduces high variance when action's sampling probability close to 0. Meanwhile, subtracting a baseline remains a heuristic (26) that has strong empirical but limited theoretical support. One possible benefit of a baseline is that provides variance reduction 10), which has motivated work on designing alternative baselines that further reduce
variance [30 20 31]. However, other work (7) has shown that variance reduction is necessarily aligned with policy learning quality. To date, it has remained unclear how a baseline impacts the quality of the ultimate solution found by policy gradient optimization. We resolve this question in this work.
Coorespondence to: Jincheng Mei and Csaba Szepesvári
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Recent progress in the theory of deterministic PG has shown that, given exact gradients, softmax policy gradient is able to converge globally optimal policy at ((1/t) rate (24. Unfortunately, despite this guarantee, the constants in this rate can be extremely large 19 due to initialization sensitivity and poor performance at escaping sub-optimal plateaus [23. Therefore, in the exact gradient setting, several techniques have been considered for mitigating the weaknesses of softmax PG, leading to better constants [2] or even exponentially faster rates of O for c > 0. Such improvements include adding entropy regularization [24 6 normalizing the gradients [22], or applying natural policy gradient (NPG) 21.
However, in the on-policy stochastic optimization case, recent studies 21 7 show that naively apply- ing the above techniques. such as normalization or NPG, leads unexpectedly worse performance than stochastic PG. That is, techniques that accelerate convergence in the exact policy gradient setting become unsound in the stochastic gradient setting, by inducing a non-zero probability of failure (i.e., failing to converge to a globally optimal solution) [21]. Such failures occur even when stochastic PG can still converge to a global optimum in probability. Previous work has indicated that one key reason behind the failure of these acceleration strategies arises from their "over-committal behaviour" in the stochastic setting, which occurs independently of the variance of the gradient estimates [7]. That is, baseline techniques with higher variance can still better avoid over-committal behaviour (i.e.. premature convergence) and ultimately achieve better policy optimization 77.
To resolve this issue, we develop a deeper understanding of the role of baselines in stochastic policy optimization based on the following contributions. First, we establish a new result that combining on-policy IS with a value function baseline and natural policy gradient (NPG) can achieve almost sure convergence to globally optimal policy at a ((1/t) rate. This result is based on two novel findings: (i) At any iteration É, the conditional expected progress of the algorithm's 's next iterate obeys stochastic non-uniform Lojasiewicz (NE) inequality. (ii) The use of the state value baseline (with appropriate learning rate control) almost surely prevents the probability of the optimal action from vanishing. These findings show that a key role of the value baseline to automatically ensure "sufficient exploration" during on-policy stochastic optimization. Next, we provide a detailed understanding of how baselines modulate the circular interaction between stochastic action sampling and updating. Although baseline has effect exact gradients, it can play major role in stochastic gradients. In this respect, we first show that the PG estimator variance is unbounded with or without baseline, hence variance reduction cannot be the primary effect. Instead, our analysis reveals that the key role the baseline plays in ensuring global convergence is to reduce the aggressiveness of updates. That is, finite variance of the gradient estimates is not necessary for ensuring global convergence, while properly controlling update aggressiveness is both necessary and sufficient.
The remainder of the paper is organized as follows. Section 2 provides the main results that establish the almost sure (1/ll) convergence rate of stochastic NPG with on-policy and state value baseline to globally optimal policy. Section B then develops the new understanding of the role of the baseline by going beyond standard variance reduction arguments. Section 4 provides some simulations to verify the results, and Section concludes
concludes the paper with brief discussion.
2 On-policy Stochastic Natural Policy Gradient
We first consider a one-state Markov Decision Process (MDP) defined by a finite action space [K] == {1, 2, .... K) where the true mean reward vector E [0, 1].. The policy optimization problem is to maximize the expected reward.
max E 01K]-3 )-)
[r(a)].
where the policy na is parameterized by 0 using the standard softmax parameterization, (xp()(a))
(a
Eeeekyy exp])(a()) all E [K].
Our focus in this paper is on on-policy optimization, where at each iteration t > the current policy Tg, is used to sample one action and perform one update.
For the sampled action de, noisy reward observation (ax) E R is drawn from unknown distribution with expected value r(a.). We make the following assumption that the observed reward Ie (a(a) is sampled from bounded distribution: zz(a) E --mmax, Rmax] with probability one.

---

Assumption 1 (Bounded sampled reward), For each action a E [K], the true mean reward r(a) is the expectation of a bounded reward distribution, i.e.,
Biax
r(a)
x P.(2)u(d))
(3)
-Bmax Rmaax
where μ is finite measure over |- Rmmax: Bmax], and (a(x) is the probability density function with respect to and Rmax > 0 is the reward range. We let Rg denote the reward distribution for action a defined by the density Pa and base measure jr.
Then, given a sampled reward observation (r(a) Ra. unbiased estimate of the expected reward vector r can be formed by on-policy importance sampling (IS).
Definition (On-policy importance sampling (IS)), At iteration i, sample one action at To, (-) and observe one reward sample zz (at) ~ Bay Let (a)aa = 0 for all o a, Then the IS reward [a=aae] xz(a) for all [K].
estimate is constructed as fe(a) ne, (a)
If the true mean reward r(az) is observed for sampled actions a,, have the simplified IS estimator. Definition 2 (Simplified on-policy importance sampling (IS)), At iteration t, sample one action
ag (.). The IS reward estimate then constructed as fc(a) [a)
[ayma) -r(a) for all a E [K].
Definition 2 will be used for illustrating ideas and new understandings in Section while the main results in Section 2 are based on Definition
2.1 Failure Without Baseline
First, to establish context, we review an existing negative result for the representative algorithm, natural policy gradient (NPG) [13), which for the softmax parameterization defined as follows.
Update 1 (NPG with on-policy stochastic gradient). 0,41 < 0₂ + 17. ft. where To(a) is by Eq.
is known that NPG behaves problematically with on-policy IS, even if the true mean reward r(a,) is observed. In particular, NPG converges to a sub-optimal deterministic policy with a constant positive probability in this case, shown by 21)
Proposition 1 (Theorem 3 of (21).. Using Update 1 where fg is from Definition 2 and r E (0, 1]K, we have with positive probability, Eayar Tq, (a) as + co.
Essentially Proposition T asserts that Update Ti is too aggressive: if sub-optimal actions are sampled times successively, their probabilities will become exponentially close to 1; i... Eo TT. (a) e
O(e-ot follows that IT= Euta. To, (a) > 0: that is, the on-policy sampling process ae Te, (.) has a non-zero probability of sampling sub-optimal actions forever, which implies that there positive probability that ne, fails to converge an optimal deterministic policy.
2.2 Global Convergence with a Value Baseline
Despite the above failure, we now prove that subtracting a value baseline rectifies the problem for NPG. Consider the modified update that includes baseline.
Update 2 (NPG, on-policy stochastic gradient with value baseline). 0c+1 <- 02 + (fz bz). where Te(a) is by Eq.
-1) by for all a E [K], and be == TT.r.. 2 be(a) = -foo Fo,(0) (a)
[[fa,=a]
Since softmax (0) softmax + 1) for all c E R, Update 2 is equivalent to the following update ft by Definition ! Given the same Te., Updates and produce the same next policy Te
Update 3. (a) (a) + [(ar=a) (xa(a) n..r). ie. (ct)(as) +- Oc(a.)) +n (a)
(a(a)) a ma, (ar)
and (1+1(a) + ( all # az-
Unfortunately, the variance of this update is not uniformly bounded whenever no, (a) is close to 0 for at least one action a E [K] (Proposition 3), therefore standard stochastic gradient analysis

---

for bounded variance estimators 25 33
cannot be applied. Instead, we develop two new techniques to establish global convergence results, both of which rely heavily on using baselines.
32
Lemma 1 provides the first key technique, which we refer to as the stochastic Nt. inequality.
Lemma (Stochastic non-uniform t.ojasiewciz (Nt.)). Suppose Assumption
7 holds. Let E [0, 1]
a" = arg [[]]] r(a), and A == r((a) maxaza" r(a). Using Update with on-policy sampling
ag (.) and IS estimator ft.
(1) if is from Definition
then with constant learning rate 1 >
have, for all t 2 1,
BB To.² 2 0,
almost surely (a.s.).
and
(4)
E. (T r] no." 147
y To, =o,(aa)) (r(aa) r0,r)²²
(5)
where [+[]] is on randomness from on ooplll sampling at Te. TO. (2) if ft is from Definition 7 then with learning rate,
1 no. (a+) |I((a)) To.
(6)
Rinxx
we have, for all t 1,
K To.
Ed [(( r] To. 2
-Tō,rl"
(7)
16. R
i=1
TH, (a (r(a') ((,'"))TT,r)"" 16 R2 K
nT.r)²
(8)
where E.I-] is on randomness from on on-policy sampling (-) and reward sampling x ~ Re." Remark 1. We have 1j E O(1/t) in Eq. (6) after knowing the convergence rate later.
We refer to Te, (a*)² in Eq. the stochastic NL coefficient. Lemma I is stochastic generalization of the NE inequality, which has been widely used in proving global convergence of softmax PG variants (24 23 22 34 It is stochastic since Eq. contains expectation. It is non-unifore because Eq. (8) depends on Or, which cannot be uniformly lower bounded away from O across the entire domain of A E RRK (that is, one can always find @ such that no ra(" is arbitrarily close to 0).
The key idea of Lemma is follows. If P3 is from Definition
2
then by algebra we have,
-00-x x
(r(1) To.r)
K
exp 1)
(3)
Ei (e r] no. Σ To. (1)
(9)
r())
-g mo, (4)
exp
No,
Since (e-v-1) 1) y 2 0 for all y E and c 0, Eq. (9) is non non-negative (letting y = r(i No.-" and = n/To, (6)). However, this is not true if is from Definition where we have.
x - exp
1
(r((t) =T.r)
Ryuax
(c) (4)
E, [T)) r] no.r E na. (1)
P.(x)u(de). (10)
Rmax
exp {n-
x-a ag Tu
1-
Ju
Note that (6ew/ - 11) 20 y 0 and c > 0 (letting y' == -...--]].---
= no.r. r. and
c 7/5o, (i)) For "good" action (r(1)= म.. 0), if unfortunately its sampled reward is "bad" (x -T.1 r < 0), then the update will make negative progress. Similar things happen for a "bad" action (r(1)= - < 0) with "good" sampled reward (r -Ø. > 0). It is then necessary to use 7) like Eq. (6. to control the non-linear sigmoid-like functions in the progress by piecewise linear functions
(Lemma 155 to get non-negative expected progresses. According to Eq. (8), we have
E, IT [T_ r] TT,1 2 0.
(11)
which implies that Update 2 Jacchieves non-negative progress in expectation. Combining Lemma with Doob's supermartingale convergence theorem then leads the following result. Corollary 1. The sequence [म]. r221 converges with probability one.

---

Corollary| asserts that, the random sequence TØ." produced by Update asympiotically approaches some finite value (since ng. r [o, 1),, ruling out the possibility of divergence (oscillating forever). However, this does not necessarily imply that Tg. r r(a*) - A subtlety arises in bounding the stochastic NL coefficient in Eq. ① away from O, which requires a second key technique.
Lemma (Non-vanishing stochastic NL coefficient/ "automatic exploration"), Using Update with for an arbitrary initialization 01 E RR we have,
conditions in Lemmal i and i from Definition [
== inf To. To,((a) O,
almost surely (a.s.).
(12)
Lemmas and 2 logether guarantee that Tg. + r(a") as t - oc. In fact, using the "variance-like" expected progress (Eq. (7) Corollary D iimples that To, approaches "generalized one-hot policy" as + oo. Lemma 2 then argues by contradiction that me cannot approach a sub-optimal "generalized
one-hot policy" as t + oc, which will imply that the optimal action's 's probability must approach 1 and achieve Eq. (12). Proof details in the appendix and intuitions in Section reveal that Update 2 achieves form of "automatic exploration" by using a baseline, i.c., maintaining To, (a) decay faster than (t)) such that every action will be sampled infinitely many times in long run. Finally, combining Lemmas [ and 2] we establish not only asymptotic convergence of NPG to global optimum, but also a global convergence rate of O(/tt) in terms of the sub-optimality gap.
reveeal
Theorem (Almost sure global convergence rate), Using Update 2 with on-policy sampling a
Te,()) (-), the IS estimator f; in Definition 1 in Eq. (6). and any initialization 01 E R2 we have,
16 R Rmmxx
K-1
[[[(TT ) r] S
and
(13)
A E[ca]
t.
A c
limsup (21
(TT -To) r]
< 00,
a.s.,
(14)
16
R K-1
where x²
== arg ma π Tr is the optimal policy, Rmax is the sampled reward range from
Assumption 7
A ===r(a") maXapaa r(a) is the reward gup of r, and >> 0 is from Lemma
2.3 General MDPs
Next, we generalize these results to finite Markov decision processes (MDPs). Given finite set X, let ( denote the set of all probability distributions on X. A finite MDP is defined as tuple M = (S, A. r, P.7). where S and A are finite state and action spaces, respectively. r: X A + R is the expected reward function, P : S x A + A(S) is the probability transition function, and E 10. is the discount factor. We also extend Assumption
I to every (s. a) S x A and assume there is reward distribution Raa with expectation r(s, a), uniformly bounded within
[- Bmmax Rmax] Given a policy π S + (AA), at each time / 2 0, an agent is given a state E S, takes an action
(-));,,, then receives a scalar reward observation rr5t, ae) Ra and next-state $1+1 ~ P(.))),,)). a.). The value function of π at state s is defined as
E ae (lach P(-eea)))
Σ y (r(sss L
Su
(15)
The policy optimization problem for general MDP is to maximize the expected value of the policy,
max 0:SKA-R
TT (p)
max E O.S -~p()) (s)),
(16)
where p A(S) is an initial state distribution, and To softmax(((s,.)), )),
exp(O(s,a)} (als) Evee exp(O(s,a')] for all (s, ESXA
(17)
Given policy its state-action value is defined Q (=(,,a)==ss,0)) r E. P(s'ls,a) (s'), and its advantage function is defined as ( a) = (=(ss)) V=((), for (s.a) E S x A.
The state distribution of is defined as d (s) == (1 11-2) -7) - Pr(st s|su, P). We
also denote (s) = Esaxp()) (s)]. Given p. there exists an optimal policy ग¹ such that
V= (p)
(p). We denote (*(p)= = ya (p) for conciseness.
For general MDP, we assume the initial state distribution μ is "sufficiently exploratory" 2 24 1
5

---

Assumption 2 (Sufficient exploration). The initial state distribution satisfies min, ( > 0.
At iteration t, the NPG method uses the current state distribution to sample one state 8 th (-). then uses on-policy sampling sample one action d Te, (-(s). For the sampled state action pair (st, dz) S x A, the state-action value QT=, (st, at) is then used to perform update. The current state value function * (s+) is used as the baseline, as shown in Algorithm
Algorithm 1 NPG, on-policy stochastic natural gradient
Input: Learning rate 17 > 0.
Output:
Policies Te, = (0))
Initialize parameter (s, a) for all (s,a) E E x A.
while & 2 do
Sample St ~ dfi" (-). and at Te. (1(st).
0et1 (s),as) 4 0e(st, ar) +1 2= (a). --V (st)
na, (0e 86)
end while
According to the performance difference lemma, we have, V (w)- - v (1)
1 - Σ dp
(s) Σ (Toe (a|s) [ol(a)))) (=
(18)
where the inner summation over actions is similar to (#e To.) one-state MDPs. This connection allows us generalize Lemma the following result.
Lemma 3 (Stochastic NL). Using Algorithm
2 with constant > O, we have, for all t 2 I,
T (8p) 5 (8o) 2 O,
a.s.
Ysp E,
and
(19)
[ (11] Vro 2:11 p((->)) -min. pie)
min, la (s)la))
(V* (1)) (20)
where EdH] is randomness from state sampling St oi (-), on-policy sampling at no, ( (s)) and a" (8) is the action selected by the optimal policy n² under state 8.
Next, similar Lemma 2 we can develop set of contradictions that establish the following result.
Lemma 4 (Non-vanishing stochastic Nł. coefficient / "automatic exploration"). Using Algorithm 7 with the conditions in Lemma 3
with arbitrary initialization 01 E RSSAA, we have,
inf T.EES
To, (a"(aa()) (s)[s) > 0, a.s.
(21)
By combining Lemmas 3 and we obtain the following result that generalizes Theorem I
Theorem (Almost sure global convergence rate). Using Algorithm Sartimmm@ier with any initialization 0 under the same assumptions Lemmas 3 there exists C > 0 such that for all t > 1,
RK
1+7
di
S
1
B[V (4) - vTH (4)] S
and
(22)
7. (1 7)
min, m(8)
00
B[ca]
7'
( (1 7)t min, u(s))
di
(V) V= (w)) } 0c, a.s.
lim sup 121
(23)
1
s
where n" the global optimal policy, is the state number, min, pus) by Assumption 2 and = infe2Lses TT, (a" (a)(s)ss > 0 is from Lemma 4
3
Understanding Baselines in On-policy Stochastic Policy Optimization
Section sishows that using value function baseline in on on-policy stochastic NPG can ensure con- vergence to globally optimal policy. However, the mechanism behind this finding requires further elucidation. Preliminary studies 7 21 have observed that subtracting a baseline can reduce the committal behavior of PG-based estimators, suggesting that this effect might be more important than variance reduction. mathematical characterization of "committal behavior" is from using the following concept of "committal rate" [2]].

---

Definition 3 (Committal Rate, Definition 2 of (2I)). r E [0.1]* and 81 E RK Consider policy optimization algorithm A. Let action be the sampled action forever after initialization and let Or be produced by A on the first observations. The committal rate of algorithm A on action (given r and 02) is,
1020: 0: sumsuppt t [o) < 20).
a(A,a) sup a
(24)
(1+20
The larger the committal rate i. is, the more aggressive one update is. In this section, we provide new, deeper understanding of how baseline improves the convergence behaviour of stochastic PG based method using Definition 3 However, [21] only studied the deterministic reward setting i.e., fr is from Definition 2
We follow the same settings in this section.
3.1 Baselines Do Not Control Update Variance in NPG
We begin from the well known result that value baselines have no effect on exact policy gradients. Proposition 2 (Unbiasedness of NPG). For NPG with and without a state value baseline, corre- sponding to Updates and respectively, we have Earwno, (-) [ft] Barno, (-) [f+ bb]
According to Proposition Updates I and become identical if the exact policy gradient is available,
hence both enjoy an ( <f convergence rate to a global optimum (c 0) [14]1]] [1]. Therefore, a
state value baseline can only have effect if the policy gradient has to be estimated from stochastic sample. However, we find that the variance the NPG updates remains unbounded in the stochastic setting, regardless of whether state value baseline is used.
Proposition (Unboundedness of NPG). For NPG without a baseline, Update we have
E (-) A 1 EaEjK]
r(a)² Fo, (a) For NPG with state value baseline, Update we have
E. B (+) ||A b.112 = E(e(K)
(r(a)-a0,)) To, (a)
K (m,,))) +2 (TT (I..
According to Proposition 3
whenever TT, nears a one-hot probability distribution over [K] (which
it must converge to), there exists at least one action a E [K] such that both r(a)²
and (r(a)-a2,1 r)
[a]
no. (a)
become unbounded, implying unbounded scale for both Updates [ and Yet we know from Proposition that not using a baseline fails with positive probability, while from Theorem ( subbrract- ing state value baseline ensures almost convergence variance both updates is unbounded suggests that it difficult to draw conclusions on the effect of the baseline from variance reduction perspective alone. An alternative analysis is required to explain the fundamental difference between Updates andd]
global optimum. The fact that the
3.2 Coupled Sampling and Updating
In on-policy stochastic policy optimization, sampling and updating coupled as shown in Fig- ure [] At iteration f, the data collected depends on the current policy, since on-policy sampling used o, TH. while the policy is updated from the observations collected based ar- This coupling introduces complexity in the optimization process as well as in the analysis. However, this coupling is also fundamental to understanding the circular interaction created by any on-policy stochastic optimization method. That is, on-policy stochastic op- timization faces an pepooratioo-exlliiaatiii dilemma: a learning algorithm can improve the policy and increase the probability of choosing actions that yield higher rewards (exploitation), but it must not do so too aggressively lest fail to identify possibly higher- reward actions (exploration). Striking a proper balance between exploration and exploitation is key to achieving good convergence properties. Different levels of update aggression create different circular effects between sampling and updating, which is central determining almost sure convergence global optimum.
Sampling ar To, (-)
Updating
Aci1 A(9,, oc,
Figure 1: Coupled on-policy sampling and updating [2] Figure 2].
7

---

3.3 The "Vicious Circle" of Being Too Aggressive
First we illustrate negative effect, the "vicious circle" of being too aggressive.
Lemma (Bad sampling). Let Te, (a) E (0, 1) be the probability of sampling action a using online sampling at To, (-), for all t 2 1. If 1 Te, (a) E O(1/t+t)) where >> 0, then Te
ne. (a) > 0.
Note that Lemma characterizes sampling behaviour under general conditions that do not otherwise depend on specific updates. However, according to Lemma 5 if an action's 's probability approaches 1 strictly faster than (L)/t), by whatever means, it becomes possible to not sample any other action forever, which creates a "lack of exploration" phenomenon as it is known in RL. In particular, on-policy stochastic NPG without baseline can produce such sequence of {To, (a))-21
Lemma (NPG aggressiveness), Fix sampling a, a a all 2 1, using Update ? with constant learning rate >> 0, where it is from Definition where c > 0.
we have 1 - Te. (a) E O(e e for all t 2 1,
According to Definition we have x(NPG a) oc, meaning that NPG without baseline is very aggressive. Note that Lemma only characterizes the aggressiveness of Update || with the sampling fixed to be ag = a for all 2 1. Lemmas [ and together describe the "vicious circle" between sampling and updating that can be created by overly aggressive updates. First, in on-policy sampling, there will always be a non-zero probability of "bad luck"; that is, with positive probability a set of sub-optimal actions can be sequentially sampled for multiple steps. Second, an overly aggressive update will only exaggerate the weakness of the sampling procedure by increasing the sampled sub-optimal actions' probabilities rapidly (Lemmaa 6). Third, this exaggeration can worsen data collection for subsequent updating by further increasing the prevalence of sub-optimal actions. Such vicious circular interaction between sampling and updating can happen repeatedly, and its self- relf-reinforcing nature can create a non-zero probability that the cycle occurs forever (Lemma [5). resulting in convergence to a sub-optimal deterministic policy (a stationary point for both sampling and updating).
3.4 The "Virtuous Circle" of Not Being Too Aggressive
Next, we demonstrate a positive effect, the "virtuous circle" of not being too aggressive.
Lemma 7 (Good sampling). Let to, (a) E (0, 1) and ae (.) all i 2 1. 1E (1- (a)) = 00 (e.g., 1 - To, (a) E (2(1/t)), then I (a) = 0.
As in Lemma 5 Lemma 7 only characterizes the effect of sampling behaviour under general conditions that do not otherwise depend on specific updates. Here we see that if an action's 's probability approaches 1 no faster than (11/t), it is no longer possible to avoid sampling any other action forever; that is, sufficiently slow modification of the sampling probabilities forces persistent exploration such that every action is sampled within some finite time with probability 1. In particular, subtracting a value baseline in on- on-policy stochastic NPG produces such a sequence (To, (a))
Lemma 8 (Value baselines reduce NPG aggressiveness). Fix sampling a; = for all 2 1. Then using Update 2 with constant learning rale 1) > 0 and i. from Definition 2 Obtains 1 no. (a)
(11/t) for all T 1.
According to Definition 3 with value baselines, we have k: NNGG a) = 1, meaning that the aggres- siveness of NPG update is reduced. As in Lemma 6 Lemma LenmaBoonly characterizes the conservativeness of Update 2 with fixed sampling of a, = a for all 2 1. Lemmas and now describe a "virtuous circle" between sampling and updating that is created by using not too aggressive updates. First, even in a worst case situation (e.g., an adversarial initialization). where a sub-optimal action has a dominant probability Te, (a) 1, under on-policy sampling all actions will eventually be sampled. Second, conservative updating will mitigate the effect of the extreme sampler by not increasing the sub-optimal action's 's probability too rapidly (Lemma ( Third, sustained diversity in sampling will eventually draw better action than the current dominating sub-optimal action (Lemma 7 Finally, once better actions are sampled, the update will improve subsequent sampling by decreasing the probability of the dominating sub-optimal action. In particular, this is achieved by increasing value baselines to be larger than the dominating sub-optimal action's true mean reward, such that the dominating sub-optimal action will start losing probabilities. This virtuous circular interaction between sampling and updating ensures sufficient exploration, which prevents the iteration from converging to sub-optimal deterministic policy.
8

---

3.5
How a State Value Baseline Reduces Update Aggressiveness
Based on Lemmas 5 and 7 the boundary between "too aggressive" and "not too aggressive" is precisely (1/tt.. We now explain how a state value baseline in NPG will control update aggres- siveness. First, without baseline, sampling sub-optimal action E [K] for t times makes its parameter behave as (+(a) E ((t), since r(a) E (1). On the other hand, other action parameters will behave as (a)) (1) if they are only sampled a constant number of times. Under the softmax parameterization Eq. (2). this will imply that - Ta, (a) E O which is far too aggressive. Second, using state value baseline, under repeated sampling the parameter increase for a sub-optimal action [K] will be damped. In particular, whenever the policy is close to deterministic. say To, (a) R 1, we also have T0, r = r(a). Therefore, since
r(a) - T=== Σ (d) (r((a) (r(a)-r(a') r((')) S - _T, (a), e'za
(25)
the closer 1- ma, (a) is to O, the smaller r(a) - _b will be. This means even a is sampled repeatedly for times, we obtain (a) E Ollgg) and na, (o,(a) (a) E (211t) (Lemma B Thus, the the boundary of being good enough.
effect of baseline is to modify the sampling to lie exactly From this argument the key role of the value baseline is to reduce update aggressiveness to achieve particular effect on long-term sampling, rather than simply reduce variance. It also shows how using an appropriately un-aggressive update is both necessary (Lemma 5 and sufficient (Lemma) 7 to achieve almost sure convergence to global optimum in on-policy stochastic policy optimization.
4 Simulations
We conducted simulations verify the two main results above: asymptotic convergence toward globally optimal policy x' in Lemma 2 and the O(1/t) convergence rate in Theorem
4.1 Asymptotic Convergence
We first consider a one-state MDP with K = 20 actions and true mean reward vector E (0, 1)x1 where the optimal action is a* action's 's true mean reward r(2) z 0.95. The sampled reward is observed with large noise, e.g.. x -2.03 and
with true mean reward r(1) 0.97 and best sub-optimal
3.97 with both 0.5 probability for the optimal action, such that r(1) R 0.5 (-2.03) + 0.5 3.97. Details about r and the reward distributions can be found in the appendix.
To verify asymptotic convergence a globally optimal policy in Lemma 2 we consider the iteration behaviors of Update 2 under an adversarial initialization, where ne, (2) Rd 0.88, i.e. a sub-optimal action starts with a dominating probability. This the worst case scenario for Lemma 2 where the optimal action only has a small chance to be sampled, while the sampled reward noise is very large.
As shown in Figure 2a the expected reward np."" quickly approaches and remains stuck around r(2) 0.95 initially, as expected. However, after about x 10 iterations, the policy ne, finally escapes the sub-opun cub-optimal plateau and approaches the optimal reward r(1) z 0.97. This simulation result is consistent with Lemma [ i.e., for an arbitrary initialization, the introduction of value baseline eventually makes ne, approach globally optimal policy within finite time, while additionally the optimal action's 's probability never vanishes, inf no, (a") > O, as shown in Figure 2b
4.2 Convergence Rate
We run Update 2 with a uniform initialization, i.e., no, (a) = 1/K for all a E [K]. and calculate averaged sub-optimality gap (T* Te. across 20 independent runs, using deterministic reward settings where A, is from Definition 2 As shown in Figure 2c] where both axes are in log scale,
the slope is approximately -1, indicating that log To.) r - log t + C. or equivalently
(IT" - == =C'/ Ct/t, which is consistent with Theorem

---

Stachantic Smord
Suathastic Roward
Determinaaic Reward
0.2
0.
pepected Bowad
00
10
60
00
23
20
60
(a) To.
(b) no, (a")
(c) log (n"
mo,)
Figure 2: Adversarial initialization (a) and (b); uniform initialization (c).
5
Conclusion
This work clarifies some of the longstanding mysteries those have separated the theory and practice of policy gradient optimization. The major finding is a state value baseline reduces the aggressiveness of the on-policy stochastic NPG update, which turns out be necessary and sufficient for achieving almost sure convergence to a global optimum. The deeper understanding of the circular dependence between on-policy sampling and updating also dispels common misconception about variance reduction, showing that bounded variance estimators are not necessary for achieving global conver- gence. The main technical innovation the stochastic NL inequality, and the subsequent arguments that establish global convergence, both of which depend critically on the value baseline.
This work leaves open number of interesting questions. First, the (1 convergence rate contains an initialization dependent constant in Lemma resulting from plateaus as observed in Figure [2a which does not appear in results that the direct parameterization [8. Thus the difficulty appears due to the non-linear softmax transform. Removing or improving this constant would impact practical performance, so investigating other techniques, such regularization, optimism or momentum might be helpful. Second, the results in this paper use the true state values as the baselines. It would be interesting consider the effect of estimating the value baseline or using alternative baselines in policy optimization. Finally, the O /t) last iteration convergence rate implies an optimal Ollog T)) regret in stochastic bandit problems [16). The explanation of the circular dependence between sampling and updating is specific to on-policy PG optimization, but it is also consistent with the exploration exploitation dilemma RI. In other words, this work suggests a completely new approach to the pnllortioo-exploiaaaiin tra achieving provable bounds with ever requiring explicit uncertainty estimates, nor any concrete instantiation of the principle of optimism under uncertainty.
Acknowledgments and Disclosure of Funding
The authors would like to thank anonymous reviewers for their valuable comments. Jincheng Mei thanks Alekh Agarwal for reviewing a draft of this work. Csaba Szepesvári and Dale Schuurmans gratefully acknowledge funding from the Canada CIFAR AI Chairs Program, Amii and NSERC.
References
[1] Yasin Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for lincar stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Alekh Agarwal, Sham Kakade, Jason D Lee, and Gaurav Mahajan. On theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
[3] Krishna B Athreya and Soumendra Lahiri. Measure Theory and Probability Theory. Springer, New York, NY, 2006.
Shalahh Bhatnagar, Mohammad Ghavamzadeh, Mark Lee, and Richard S Sutton. Incremental natural actor-critic algorithms. Advances neural information processing systems, 20, 2007.
[5] Leo Breiman. Probability. SIAM, 1992.
10

---

[6] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 2021.
[7] Wesley Chung, Valentin Thomas, Marlos C. Machado, and Nicolas Le Roux. Beyond variance reduction: Understanding the true impact of baselines policy optimization. arXiv preprint arXiv:2008. 13773, 2020.
[8] Denis Denisov and Neil Walton. Regret analysis of a markov policy gradient algorithm for multi-arm bandits. arXiv preprint Xiiv:20077110229 2020.
[9] Joseph Doob. Measure theory, volume 143. Springer Science & Business Media, 2012.
[10] Evan Greensmith, Peter L Bartlett, and Jonathan Baxter. Variance reduction techniques for gradient estimates reinforcement learning. Journal Machine Learning Research, 5(9), 2004.
[11] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- maximum entropy deep reinforcement learning with a stochastic actor. In International Conference on Machine Learning, pages 1861-1870, 2018.
[12] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning, In ICML, volume 2, pages 267, 2002.
[13] Sham Kakade. natural policy gradient. In Advances Nearul Information Prucessing Syxtems, pages 1531-1538, 2002.
[14] Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and Siva Theja Maguluri. On the linear convergence of natural policy gradient algorithm. arXiv preprint arXiv:2 2021.
[15] Konrad Knopp. Theory and Application of Infinite Series. Hafner Publishing Company, New York, 1947.
[16] Tze Leung Lai, Herbert Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
[17] Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. arXiv preprint arXiv:2102.001 35, 2021.
[18] Romain Laroche and Remi Tachet des Combes. Dr jekyll mr hyde: the strange case of off off-policy policy updates, Advances in Neurul Information Processing Systems, 34:24442-2444 2021.
[19] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Softmax policy gradient methods can take exponential time to converge. In Conference Learning Theory, pages 3107-3110 10. PMLR, 2021.
[20] Hongzi Mao, Shaileshh Bojja Venkatakrishnan, Malte Schwarzkopf, and Mohammad Alizadeh. Variance reduction for reinforeement learning in input-driven environments. arXiv preprint arXiv: (eee:10077000000 02264, 2018.
[21] Jincheng Mei, Bo Dai, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. Understanding the effect of stochasticity in policy optimization. arXiv preprint vrXiv:2110.15521 2021.
[22] Jincheng Mei, Yue Gao. Bo Dai, Csaba Szepesvari, and Dale Schuurmans. Leveraging non-unifornity in first-order non-convex optimization. In International Conference Machine Learning, pages 7555-7564. PMLR, 2021.
[23] Jincheng Mei, Chenjun Xiao, Bo Dai, Lihong Li, Csaba Szepesvári, and Dale Schuurmans. Escaping the gravitational pull of softmax. Advances Neural Information Processing Systems, 18:21130-21144 140, 2020.
[24] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pages 1820-6829 PMLR, 2020.
[25] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic ap- proximation approach to stochastic programming. SIAM Journal on optimization, 1944)11744-169, 2009.
[26] Ben Recht. Updates policy gradients. http://www.arrmmii..ee///2211113
2018.
[27] John Schulman, Sergey Levine, Pieter Abhcel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pages 1889-1897, 2015.
[28] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 2017.

---

[29] Richard S Sutton. David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, pages 1057-1063, 2000.
[30] George Tucker. Surya Bhupatiraju, Shixiang Gu, Richard Turner, Zoubin Ghahramani, and Sergey Levine. The mirage of action-dependent baselines reinforcement learning. International conference on machine learning, pages 5015-5024. PMLR, 2018.
[31] Cathy Wu, Aravind Rajeswaran, Yan Duan, Vikash Kumar, Alexandre Bayen, Sham Kakade, Igor Mordatch, and Pieter Abbeel. Variance reduction for policy gradient with action-dependent factorized baselines. arXiv preprint arXiv: 2018.
[32] Junyu Zhang, Chengzhuo Ni, Zheng Yu, Csaba Szepesvari, and Mengdi Wang. On the convergence and sample efficiency of variance-rcduced policy gradient method. arXiv preprint wwXiv:2102.08000 2021.
[33] Junzi Zhang, Jongho Kim. Brendan O' Donoghue, and Stephen Boyd. Sample efficient reinforcement learning with reinforce. arXiv preprini arXiv:0010.11644 2020.
[34] Runyu Zhang, Jincheng Mei, Bo Dai, Dale Schuurmans, and Na Li. On the effect of log-barrier regular- ization in decentralized softmax gradient play in multiagent systems. arXiv preprint arXiv:2202.00877.
2022.
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)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(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": "sxsn2h61hao", "reviewer": "Reviewer_C7pU", "summary": "*The Role of Baselines in Policy Gradient Optimization* is a submission that studies the impact of substracting baselines in the natural policy gradient updates. While in expectation (or with exact gradients), both updates are equivalent, the authors show that their stochastic updates behave differently, in particular with respect to the aggressivity of convergence.", "questions": "Please address my questions in the previous section.", "limitations": "No potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a well rounded study on a phenomenon that has not been investigated before. While I think that the paper deserves to be published, I am bothered by several points (this explains my low recommendation):\n* The claims made in the abstract and the introduction are too strong: the convergence to global optimality relies on Assumption 2 in MDPs in order to ensure exploration of all states. This is true even with exact gradients, when the updates are online PG [Laroche2021].\n* Aggressiveness of updates is not a well defined concept and the reader has not a good grasp of what the authors mean before Section 3. I would rather call it speed of convergence that prevent a proper exploration of actions (exploration of states being handled by Assumption 2).\n* Update 2 relies on the knowledge of $r$? Same for the learning rate? How is it a practical algorithm? \n* I don't like the learning rate to be dependent on $\\theta_t$. I don't feel that the update should be called NPG anymore. (this was already something that bothered me in the escort paper [Mei2020]) Could you justify your choice to keep calling it NPG?\n* Lemma 1 would hold with $\\eta$ being defined lesser than the right hand side of eq (4), wouldn't it?\n* Converging faster than $O(1/t)$ in a stochastic setting is not possible, otherwise MAB could be solved with regret in $O(1)$. The authors spend more than 1 page and 4 lemmas on it. Could you please help me understand better why your arguments in 3.2-3.5 are necessary?\n* I find it very surprising that introducing a baseline (basically IS on the advantage rather than the value) allows to obtain this dampening of the convergence as the authors claim. Isn't it rather granted by the adaptive learning rate? Wouldn't the same result be obtainable without baseline? (I don't really buy the explanation in Section 3.5)", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "rOnO-esmI4z", "reviewer": "Reviewer_6WdT", "summary": "This paper discusses the effect of baselines in stochastic policy gradient optimization, i.e., the subtracted term in the advantage function. Previous approaches have demonstrated that by subtracting a state value baseline would stabilize the learning of RL empirically, however, few researches focus on explaining this theoretically. Considering natural policy gradient (NPS), the paper demonstrated that using a state value baseline can prevent the probability of the optimal action from vanishing almost for sure, and the NPG can converge to a globally optimal policy at rate of O(1/t). The paper further discusses more on the variance reduction effect of using baselines for stochastic gradients. Results show that the PG estimator is unbounded neither with nor without a baseline, and the key effect of baseline is ensuring convergence and reduce the aggressiveness of updates. Some simulation results in simple one-state MDP toy example are provided to support the proposed theories.", "questions": "Are there any connections between the theories in this paper and existing variance reducation baselines, e.g., the input-dependent baseline [1]? Could the used techniques to applied to explain such baselines in the effect of variance reduction and global convergence?\n\n[1] Mao H, Venkatakrishnan S B, Schwarzkopf M, et al. Variance reduction for reinforcement learning in input-driven environments[J]. arXiv preprint arXiv:1807.02264, 2018.\n", "limitations": "Insufficient empirical studies of stochastic NPG with baseline.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\nThe proposed discussion and analyses indeed provide me new insights for the effect of baselines in stochastic PG. I think the used techniques in analyzing the global optimality convergence for stochastic PG is informative for future research. Moreover, the relationship between using value baselines and variance reduction is discussed and the results tell that there might not exist directly.\n\n\nCons:\nThe experimental results are far insufficient and general MDPs are not studied for Algorithm 1, which, I think, is the most critical part for RL applications. The only concern I have is the practical performance that whether on-policy stochastic NPG matches the theoretical convergence results.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "l_47Ol5sZIW", "reviewer": "Reviewer_aDcz", "summary": "This work studies the role of baselines in natural policy gradients (NPG). Earlier it has been argued that baselines are effective for reducing variance of the updates. They first study the one-state MDP. They argue theoretically that NPG updates without baseline might converge to sub-optimal action and it is not so with the baseline. More importantly they provide results on a.s. global convergence rates for the baseline case. They then extend these results to general MDP. They argue that the variance maybe unbounded in the NPG with baseline case and therefore it is unfair to draw conclusions from a variance reduction perspective alone. The explain the vicious and virtuous cycle of update aggressiveness. Finally, they provide experiments in a simplified setting to evaluate their theoretical results.", "questions": "**Questions and suggestions for the authors**:\n1. I think \"the variance is unbounded\" and therefore \"Baselines Do Not Control Update Variance\" is a leap I am still not convinced of after reading the main body of the paper. I was wondering if the authors could comment on how the two values of interest in Proposition 3 ($\\frac{r(a)^2}{\\pi_{\\theta}(a)}$ and $\\frac{(r(a) - \\pi_{\\theta_t}^Tr)^2}{\\pi_{\\theta}(a)}$) evolve through time $t$ (and not only the convergence)? Please point me to the result if it already dealt with in the paper or previous work. This might give us an idea of how baselines effect the variance through time.\n\n2.  In the abstract you claim that for the NPG setting \"finite variance is not necessary\" (line 15)  and in Section 3.1 you claim \"there exists at least one action such that $\\frac{r(a)^2}{\\pi_{\\theta}(a)}$ and $\\frac{(r(a) - \\pi_{\\theta_t}^Tr)^2}{\\pi_{\\theta}(a)}$ become unbounded\" (line 244). Can you please explain in what case the variance is finite? My reading is that this necessitates variance being unbounded. \n\n3. I am curious why the optima is stuck in a plateau in Fig 2(a)? Kakade [4] had asserted that NPG overcomes the plateau phenomena, in principle, effectively. I hope the authors can comment on this.\n\n4. Can you present empirical results for a more general MDP case as well? That would make the argument stronger although I wouldn't reject the paper for this reason since the results for single state example serve as a good example.\n\n5. Some additional background on NPG in section 2 and how it differs from vanilla PG would be helpful for the reader. Update 2 being NPG and where it comes from might not be apparent to most readers in the community.\n\n6. How is committal behavior different from the standard exploration exploitation problem? I am curious if some of the effects of the baseline are similar to that of adding noise (or policy gradient version of $\\epsilon$-greedy exploration) to the policy? \n\nMinor: Title mismatch between the submission and paper.\n\n[4] A Natural Policy Gradient, Sham M. Kakade, NIPS.", "limitations": "Apart from the limitations mentioned above I don't see any limitations in terms of addressing the ethical guidelines.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n1. The paper is very well written and goes through various concepts very carefully despite it being dealing with topics that are very complicated.\n2. The new perspective on update aggressiveness is both intuitive and technically sound from what I understand. The clear dichotomy between the \"vicious circle\" and \"virtuous circle\" of updates is deeply insightful and very well presented!\n3. Their experiment on convergence rate illustrates the practical outcome of Theorem 1 very clearly.\n\n**Weaknesses**:\n1. My primary concern is that the authors have not very well positioned their work in light of past work, to the best of my knowledge. This hinders my understanding of how exactly their analysis is novel and stands apart from previous work. For example, Lemma 2 by Bhatnagar et al [1] is a well known result on how the value function is the minimum variance baseline (to the best of my knowledge) which is also for the more general linear setting. How is this different from your results or how is the setting different? My best guess is that lines 237-239 hint at this but I am unsure how this works in light of previous results. Also, the difference is that your work considers on-policy NPG? Also please see other citations [2,3].\n\n2. My second concern is the lack of explanation of the constants in the convergence rate results. The constants $C$ in Theorems 1 and 2 are not explained. Are they the same or similar? I see that the constant does not depend on $t$ but as a reader I would like to know what this constant does depend on? What properties of the MDP effect these constants? Therefore, in my opinion, a corresponding empirical study of how this convergence rate changes with the MDP would also be warranted for a complete understanding of the theoretical results in addition to the explanations.\n\n**Overall**: I am currently reluctant to reject the paper and would recommend an accept if my concerns above and below are addressed. This is primarily because the results formalise \"committal behavior\" and open up avenues for future research which could impact the practice of RL.\n\n[1] Natural actor-critic algorithms, Shalabh Bhatnagar and Richard S. Sutton and Mohammad Ghavamzadeh and Mark Lee, 2009\n\n[2] Variance Reduction Techniques for Gradient Estimates in Reinforcement Learning, Evan Greensmith and Peter L. Bartlett and Jonathan Baxter, 2004\n\n[3] Variance Reduction for Policy Gradient with Action-Dependent Factorized Baselines, Cathy Wu and Aravind Rajeswaran and Yan Duan and Vikash Kumar and Alexandre M. Bayen and Sham M. Kakade and Igor Mordatch and P. Abbeel, 2018", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PgS5ZQl-Zkd", "reviewer": "Reviewer_24yz", "summary": "The authors consider the well-known policy gradient algorithm (PG) of reinforcement learning\nand study the effect of the baselines, which is frequently used in practice with PG to improve the sample efficiency and the stability.\nTo this end, the authors study the asymptotic behavior of the exemplary algorithm, namely\nthe softmax policy + on-policy importance sampling + the natural policy gradient (NPG), with and without the baseline.\nAs a result, it is shown that NPG + baseline is sufficient to achieve the convergence to global optimum, which is not possible with the NPG only.\nMoreover, the authors show that the convergence rate achieved with the baseline is O(1/t) in expectation, which is not improvable without compromising the global convergence property.\nThey also give intuitive explanation why baselines lead to global convergence while pointing out a flaw of the conventional explanation via variance reduction.\nFinally, these theoretical results (the global convergence and the convergence rate) are confirmed with numerical simulations.\n", "questions": "Please address the above questions.", "limitations": "I think some aspects of the limitation are further addressed by answering the above questions.\n", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of this work is that it gives one clear explanation on the effectiveness of the commonly-used baseline technique and thus promotes our understanding of reinforcement learning.\nHowever, there are some concerns with the clarity of the technical details and the presentation style:\n\n- In the stochastic NL inequalities, a variable learning rate (eq. 4) is used and its dependency on $\\pi\\_{\\theta\\_t}(a\\_t)$ seems important there to reduce agressiveness of the updates. How can it be adopted by the fixed-learning-rate regime of Update 2?\n- In Theorem 1 and 2, there seems no assumption on the learning rate $\\eta$, but at least it should satisfy $\\eta>0$. Is that all?\n- With regard to Remark 1, it reads for me that Theorem 1 and 2 are only valid with the noiseless bandit feedback model. Is it true? If so, it should be clarified in the statement of the theorems.\n- The problematic agressiveness of Update 1 seems to be largely attributed to the computation of the natural gradient rather than the absence of baseline. Could you discuss the benefits of baseline compared to just computing the naive softmax policy gradient?\n- What exactly is your assumption on the distribution of $\\hat{Q}$ in Algorithm 1? How can we estimate the Q function to satisfy it?\n- The explanation with Section 3 focuses too much on narrative intuitions and seems to be disconnected with the theoretical results presented in Section 2. Organizing these explanations in a form of more structured proof sketch would be very helpful to make the paper more coherent as a whole. Specifically, how are those lemmas in Section 3 connected with the proof of Theorem 1 and 2?\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept