REINFORCE Converges to Optimal Policies with Any Learning Rate
Authors: Samuel McLaughlin Robertson
Thang D. Chu
Bo Dai
Dale Schuurmans
Csaba Szepesvari
Jincheng Mei
Venue: NeurIPS 2025 poster ()
Keywords: Reinforcement learning
Policy gradient
Convergence
Bandits
Primary area: reinforcement_learning

Abstract: We prove that the classic REINFORCE stochastic policy gradient (SPG) method converges to globally optimal policies in finite-horizon Markov Decision Processes (MDPs) with $\textit{any}$ constant learning rate. To avoid the need for small or decaying learning rates, we introduce two key innovations in the stochastic bandit setting, which we then extend to MDPs. $\textbf{First}$, we identify a new exploration property of SPG: the online SPG method samples every action infinitely often (i.o.), improving on previous results that only guaranteed at least two actions would be sampled i.o. This means SPG inherently achieves asymptotic exploration without modification. $\textbf{Second}$, we eliminate the assumption of unique mean reward values, a condition that previous convergence analyses in the bandit setting relied on, but that does not translate to MDPs. Our results deepen the theoretical understanding of SPG in both bandit problems and MDPs, with a focus on how it handles the exploration-exploitation trade-off when standard optimization and stochastic approximation methods cannot be applied, as is the case with large constant learning rates.

REINFORCE Converges to Optimal Policies with Any Learning Rate
Samuel Robertson
Thang D. Chu
Bo 2
Dale Schuurmans
Csaba Szepesvári 12
Jincheng Mei
University of Alberta
Google DeepMind
GGorggia Institute of Technology
{smrobert, Qualerraa... ca {bodai, schuurmans, szepi, cmei /ggogle.g
Abstract
We prove that the classic REINFORCE stochastic policy gradient (SPG) method converges globally optimal policies in finite-horizon Markov Decision Processes (MDPs) with any constant learning rate. To avoid the need for small or decaying learning rates, we introduce two key innovations in the stochastic bandit setting, which we then extend to MDPs. First, we identify a new exploration property: the online SPG method samples every action infinitely often, improving previous results that only guaranteed at least two actions would be sampled infinitely often. This means SPG inherently achieves asymptotic exploration without modification. Second, we eliminate the assumption of unique mean reward values, a condition that previous convergence analyses in the bandit setting relied on, but that does not translate to MDPs. Our results deepen the theoretical understanding of SPG both bandit problems and MDPs, with focus how it handles the exploration- exploitation trade-off when standard analysis techniques for optimization and stochastic approximation methods cannot be applied, is the case with large constant learning rates.
Introduction
Policy gradient (PG) methods constitute one the most popular classes of algorithms for reinforce- ment learning (RL). In the PG paradigm, learner acts according to a parameterized policy; the expected return is directly optimized by computing its gradient with respect to the policy parameters and performing stochastic gradient ascent. PG methods have played key role in the advancements of deep RI. (Lillicrap et al. 2019 Schulman et al., 2017a b): combined with deep neural networks, PG algorithms have shown strong empirical performance across many domains, including robotics Akkaya et al. (2019), games Vinyals et al. (2019), and large language model training (Rafailov et al.. Ouyang al. 2022).
2024
Despite PG methods' conceptual simplicity and rich set of practical applications, known theoretical guarantees their performance
with restrictive assumptions. In particular, convergence proofs either require oracle access to the exact gradient (Liu et al. 2024 Agarwal et al. 2020), which is akin to demanding that the reward function and dynamics of the environment or they impose harsh constraints on the learning rate used for stochastic gradient ascent (Mei et al. 2024b Klein et al. 2024). Both of these assumptions are violated in typical applications. In the stochastic setting, where the rewards and transition probabilities are unknown and must be estimated from interaction with the environment, convergence of the classic REINFORCE algorithm (Williams)
known to the learner.
Equual contributions
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

1992) has only been shown under the assumption that the learning rate is either sufficiently small KKlein al. 2024) or decaying (Zhang et al. (020a). In this work we study REINFORCE with the standard softmax parameterization, and narrow the gap between theory and practice by providing the first proof in the stochastic setting that REINFORCE will globally converge an optimal policy in tabular finite-horizon Markov Decision Processes (MDPs) with any constant learning rate. Along the way we show new results about the stochastic gradient bandit algorithm (Sutton and Barto 2018) Mei et al. 2024a), which is the special case induced by applying REINFORCE to a bandit problem. Specifically, l, we show that the stochastic gradient bandit algorithm automatically achieves sufficient exploration for global convergence with an arbitrary constant learning rate; in doing so we remove key assumption in prior work, and thus resolve an open problem posed by Mei et al. (002a)). Our results in the bandit setting extend to more general "nonstationary bandit problem', where the reward function is allowed to drift mildly across timesteps. This extension is then embedded into the RI setting where, with some additional arguments, derive the convergence of REINFORCE. In summary, the main contributions of this work are threefold:
i) We show that the stochastic gradient bandit algorithm will select every arm infinitely often (i.o.) in any bandit problem and with any learning rate. We find surprising that this strong property emerges from such a simple algorithm, without any explicit hacks to encourage exploration. We obtain a counterpart result in the RL setting, but the bandit case is independently interesting, and also critical for our second contribution:
ii) In the bandit setting we remove the central assumption of Mei et al. (2024a), that no two arms have the same expected reward, and prove that the stochastic gradient bandit algorithm still converges to an optimal policy. For bandits this assumption is impossible verify without access to the true reward function (at which point the bandit problem is already solved), but more importantly it renders the extension to RL virtually impossible.
iii) In RL we provide the first proof that REINFORCE converges with large learning rates the stochastic setting. This requires the first two contributions: the exploration result is applied directly to RL, and the bandit result is extended to a nonstationary bandit problem that can be embedded into an MDP.
Positioning our work, to our best knowledge, we note that existing convergence results for stochastic policy gradient (SPG) methods typically suffer from one of the following drawbacks: (i) they rely on decaying learning rate schedules for convergence guarantees (Zhang et al., 2020a Ding et al. 2022 2024, et al.] (023), requirement not aligned with the constant rates commonly used in practice; (ii) they study constant learning rates (Mei al., [2024b] Klein et al.) 2024). but provide guarantees only for rates considered impractically small; or (iii) they are restricted to the simplest bandit settings by assumptions on the reward structure (Mei et al., (0244)), preventing extensions to RI. Filling this gap, our work provides rigorous convergence guarantees for SPG using practical learning rates in MDPs, without requiring uniqueness of the optimal policy.
2 Related Work
In the exact gradient setting, where the rewards and transition probabilities of the MDP are known,
Agarwal et al. (2020) exploited the notion of gradient dominance (Polyak, 1963) show that PG algorithms with the tabular softmax parameterization can attain asymptotic convergence towards globally optimal policy. Mei et al. (2020b) leveraged k.jasieeweez-like inequalities to show a O /t) convergence rate, where 7 is the number of update iterations. Moreover, (Zaang,//gggga et al. (2020b) exploited the "hidden convexity" property of MDPs to establish a global optimality result. In summary, these works exploited a variety of conditions for global convergence results of vanilla PG algorithms in the exact gradient setting.
There have also been several techniques developed to improve the convergence rate of PG algorithms, including entropy regularization (Mei al. (0220)). normalization (Mei et al., 2022), natural gradients (Cen et al. [002 Lan 2022, Khodadadian et al. 2021: Xiao, 2022). and accelerated learning rates (Chen et al. 2024). ). Some of these techniques have known convergence rates in the exact setting
(Liu et al. 2024). but the results are unlikely to carry over to the stochastic setting. Indeed, all of these techniques except accelerated learning rates have been shown not to globally converge in
the stochastic setting due to "over-committal" behavior in the update rule (Mei et al. 2021), and

---

accelerated learning rates have no convergence guarantee; the noise in the gradient causes these methods commit overzealously to suboptimal policies.
PG algorithms for the stochastic setting, or SPG algorithms, have also received theoretical attention. The common approach is pair decaying or sufficiently small learning rates with SPG in order to control the noise in the gradient estimates. In particular, Zhang et al. (2020a) showed that REINFORCE Williams 1992) with a ((1/Vž) learning rate converges to an c-optimal policy at a Ō(-2) rate. Ding et al. 2024) demonstrated that SPG algorithms with softmax parameterizations, entropy regularization, and O(1/t) learning rate enjoy O(E-2) sample complexity. In addition to controlling the learning rates, variance reduction techniques have been developed to reduce the effect of noisy estimates (Masiha et al. [2023] Fatkhullin et al. (202)). The main drawbacks of these
approaches are that they introduce decaying learning rates (Zhang et al., [020a] Ding et al., 2024]
Mei et al. 2023), incur expensive subroutines (Masiha et al. (023), or assume prior knowledge of the true staue-value function (Mei al. 2023).
Recently, Mei et al. (2024b) analyzed softmax SPG in the bandit setting and proved that it converges to the optimal policy with a sufficiently small constant learning rate. However, their learning rate depends on prior knowledge of the reward gap between the optimal and next-best arm, which is typically unknown. Klein et al. (2024) proved global convergence for SPG algorithms with constant learning rates in finite-horizon MDPs, but their technique strongly requires the learning rate to be sufficiently small in order to induce a smoothness property of the objective function. The most relevant work to ours is that of Mei et al. (2024a), who recently showed that SPG algorithms with arbitrarily large learning rates converge to an optimal policy in the bandit setting. The major caveat the assumption that there are no ties in the mean reward among arms
among suboptimal ones. This strong assumption raises concerns about convergence in a bandit problem with any equally good arms (e.g. any bandit problem with its worst arm duplicated), and also hinders the extension to RL, since the analogous assumption would be that no state has ties in Q-values under any policy.
3 Challenges of Non-Unique Solutions
3.1 Non-Uniqueness of Policies in RL
In standard optimization, it is well known that gradient-based algorithms can exhibit non-convergence of their parameters (or iterates) when multiple optimal solutions exist (Absil et al. (005). To avoid this challenge, existing results for the SPG algorithm in the K-armed bandit setting (Mei et al. 2024b)a) rely on the following assumption, which implies the uniqueness of the globally optimal policy.
Assumption 3.1 (True mean reward has no ties). For all a, b E [K], if a of b. then r(a) # r(b).
In Assumption 3.1 K := {1.... K} denotes the set of K arms and r(a) is the true mean reward for arm E [K] J. Assumption 3.1 implies that there is unique optimal arm, which we denote a² == arg max r(a). This results in a unique one-hot globally optimal policy T" with n "(a") = 1 and o (a) = 0 for all a & a*.
P=2
9g
54
r=0.5
m2
ma,5
m1
m0.5
m0.5
m0
00.5
m
S1
0m5
0-0
re.0.5
54
r=7
T2
(a) Tree MDP
(b) Chain MDP
Figure 1: Classical examples of finite-horizon MDPs. Transitions are labelled with (deterministic) rewards, and double circles indicate terminal states.
However, extending to the RL setting presents the challenge of multiple optimal policies, a scenario which is not prevented by the straightforward extension of Assumption 3.1 to each state, since
3

---

Assumption 3.1 only constrains immediate rewards. In contrast to bandits, RL involves sequential decisions, and different action sequences (trajectories) can yield the same (maximal) cumulative reward. This situation is common in tasks like navigation with alternative optimal paths; consider the tree-structured MDP shown in Fig. (state space (
{81,...; 813), action space A {a1, 02 (33)
Here, both 81 + $2 - 85 and
$3 + 8g are optimal paths with total reward 3. Because previous bandit convergence analyses (Mei et al. 2024b a) critically rely on the assumption a unique optimal
policy, they cannot be directly applied to RL problems exhibiting such non-uniqueness.
3.2 SPG Policy Non-Convergemn in the Presence of Ties
On the other hand, Mei al. 2024b. Remark 5.3) conjectured that the SPG algorithm could still achieve convergence even without Assumption 3.1 Their conjecture was based on the idea that SPG has "self-reinforeing" property, causing the probability of only one arm eventually become dominant and converge to 1, thus resulting in stationary one-hot optimal policy as + oo. That is, Te (a") + for only one optimal arm - oo, almost surely, even when multiple optimal arms exist. If this behavioral property holds, the latter part of the convergence proof can utilize the contradiction- based arguments presented in (Mei al., 20246 Theorem 5.1, Claim 2).
Our first major finding, supported by both empirical evidence and theoretical analysis, that the aforementioned conjecture incorrect: SPG-like algorithms do not necessarily converge a single policy in the presence of multiple solutions. To demonstrate this, we designed a bandit experiment with two optimal arms (mean 0.2) and one suboptimal arm (mean -0.1). Fig. shows typical runs of the stochastic gradient bandit algorithm (Algorithm [ with initial parameters On == (0, 0, 0) and learning rates 7) E {1, 10} for 10sh iterations, revealing that, while the total probability of optimal arms converges to (EeeA Tz(a) + 1). the probabilities of individual optimal arms (1 and 2) display non-stane -tasttationayy behavior. We observed analogous behavior tree-structured MDP using REINFORCE (Williams) 1992) with 7) E {0.1, 0.5), shown in Fig, 2b where optimal action probabilities from state s fail converge a unique action. Moreover, prove the following theorem, which supports the phenomena observed in simulation.
similar experiment on
Proposition 3.2 (Non-Stationary Convergence). Consider a K Kaareed bandit with all arms being equally good, i.e. A [K], and at least one arm has a nonzero probability of generating nonzero reward. Running Algorithm with any 1j > O leads
lim Te (e(a) < a.s,
for all a E [K]. Therefore (Te)ı2 does not converge any one-hot policy.
Proof sketch We first argue that the sequence of parameters (0s (0z)c20 does not converge to a fixed finite vector in IR K Since all arms are equally good, (0:) a martingale, and we can use the fact finite value and standard martingale results to show that it will undergo
that it doesn't 't converge unbounded oscillations, implying the result.
1-05
2050
1000
(a) Bandit
(b) RL
Figure 2: Fig. shows that the total probability of optimal arms converges to 1. but the probabilities of individual optimal arms are non non-stationary (i.c. тy (a1) oscillates). Fig. 2b shows similar non- stationary behavior for optimal actions in an RL setting with multiple optimal trajectories.
3.3 Limitations of Standard Analysis
Global convergence for SPG algorithms is typically established through a two-stage proof: (i) establish convergence to stationary point, and (ii) demonstrate (often contradiction) that the

---

attained stationary point is globally optimal. This methodology originates from seminal work on PG in the exact gradient setting (Agarwal et 2020 Theorem 5.1).
Our findings demonstrate two key points: (i) ties in trajectory or policy value can exist in RI. settings regardless of assumptions on immediate rewards; and (ii) the typical two-stage proof strategy for arguing global convergence of SPG cannot be directly extended to RL. However, as shown in the next section and suggested by the above simulations, convergence results can be obtained even with ties, but this requires new analysis. This is primarily because our approach needs to carefully reason about the per-timestep expected progress distinguishing optimal from suboptimal actions despite the presence of these ties. Specifically, we prove that the learned policy eventually converges to assign all probability mass to the optimal set (a form of "generalized one-hot policy"), ) i.e. Eoe TT(a) as + DO.
4 An Illustrative Bandit Setting
This section presents new insights into the exploration properties of the SPG algorithm. We first analyze the simplest bandit setting for illustration and then extend the results to RI.
4.1 Stochastic Gradient Bandit
We consider stochastic multi-armed bandit problem with K 2 arms and rewards bounded in [-R, It] (where Rt > 0). At each iteration 2 1, the learner selects an arm d, E [K] == {I,.... K} and observes a reward ri sampled from fixed distribution Pa, MMi(--, R The true mean reward for arm a E [K] is r(a) == __x (d(d). arg [a) r(a).
The set of optimal arms denoted A ==
The learner aims to find a policy т E ([K)) that maximizes expected reward. We use the softmax parameterization over K for 0 E R and a E [K],
exp(E(a))
(a(a)= = ΣBe[K] exp(O(6))
(2)
The optimization problem the learner is solving thus has the objective
max To r. DERK
We study the stochastic gradient bandit algorithm (Algorithm D. which performs stochastic gradient ascent on Eq. (3) (uttoon and Barto 2018 Mei et al. 2024b). Given On and learning rate 1) > 0 the algorithm iteratively updates parameters using the information it receives from single interactions. The stream of parameters generated will be referred to (0,) and we will use π. for the policy used to select a++1-
Algorithm 1 Stochastic gradient bandit algorithm
I: input 6g E RRK .7 0
2: for t 2 0 do
3: Select 0r41 Te, and observe Te+1 Paysa
4: (1+1(0r+1) + 0,(0++1) + 17(1 - Te(ae+1))re4
5: for [K], & at+1 do
6: (1+1(a) + 0z(a) - m7)(a))441
7: end for
8: end for
4.2 A Novel Exploration Lemma
We detail the reason why existing results (Mei et al. 2024a) do not generalize, even to bandit settings with reward ties. Mei et al. (2024a Lemma 2) establishes an exploration property for SPG, showing
Where (S) denotes the collection of probability distributions the set S.
5

---

that at least two distinct arms are sampled i.o. Their subsequent convergence proof (Mei et al. 2024a Theorem 2) relies on the argument that at least one of these i.o. sampled actions must be optimal. However, in the presence of reward ties, it is possible for two actions to share the same reward value (the sub-optimal action's 's interval from (Mei et al., 2024a| Eq. (15)) no longer exists). Consequently, the arguments that construct a contradiction to show "at least one of these i.o. sampled actions must be optimal" are no longer valid.
Given the failure of existing approaches with reward ties, new analytical results are required for convergence proofs, even in the bandit setting. Our second key finding is generalized exploration property for SPG: we establish that despite reward ties, every arm is sampled i.o. To formalize this, we define (a) as the number of times action a E [K] has been sampled up to iteration 2 1, i.e.
Ni(a)= = Σ Iaa = =a.. 8=1
(4)
The asymptotic count is No. (a) := 1i Na).). which is either finite or infinite. If oo oc, action a is only sampled finitely many times; if (a) = oo, action a is sampled i...
Lemma 4.1 (Bandit Exploration). Using Algorithm 7 with any constant learning rate 1j E ((),, every arm is almost surely played infinitely often. That is, Va E [K] (a)
almost surely.
Proof sketch 2. For any arm a' {_KK] such that Noo(a') < co, the Extended Borel-Cantelli (Breiman 1992) Lemma implies Er= (a(a") < cc. Since such an arm is sampled only finitely many times, Its parameter (a(a') remains bounded, sup, (0,(a') < co, and its probability con- verges to zero: lim Ty (a)) = O. Without loss of generality, let a E [K] be an arm with (a) < xc. The condition lim (a) = 0 requires that some parameter grows unboundedly, Le. limy-+co ea (aa) = co. To preserve the total probability mass, this necessitates that some parameter must diverge to negative infinity: lim m [K]] 0((a') = -oo. Thus, there exists at least one arm b E [K] such that lim inf O₂ (b) = -C. Furthermore, since the sum of probabilities for finitely sampled arms is finite, any arm b with lim inf (b( = -oo must be sampled infinitely often (b) = oo).
We use these properties of arms (finitely sampled, bounded parameter) and b (infinitely sampled, parameter unbounded below) to construct proof by contradiction. The fact that arm b sampled infinitely often despite its parameter repeatedly dropping to arbitrarily low values implies that 0, (b) must periodically increase become larger than (a) (and other bounded parameters) infinitely often. Consider the event C. == (b) < (a), a, b). We first show that if (b) S. (a) and the parameter update causes 0 (b) > (a), this implies a, = b. We then prove that the event Ce occurs only finite number of times. However, for arm b to be sampled infinitely often (N~ (b) oo) while lim inf (b)
oo and (a) is bounded, it must be sampled infinitely often during periods when (b) < (a). This contradicts the finding that C₁ occurs only finitely often, proving our initial assumption (Noo (a) < do for some arm a) false.
4.3 Convergence Without the Assumption of Unique Rewards
allows us remove an assumption necessary for the results of prior work (Mei et al., b)). namely that there are no ties in the true mean rewards of the arms (Assumption 3.1). However, this requires new analysis beyond the exploration proof. In this section we sketch out the steps used to show our central result in the bandit setting: that Algorithm contergges almost surely regardless of the learning rate.
Our new result about the exploration of SPG in the bandit setting, Lemma 4.1
Theorem 4.2 (Convergence in Bandits), In the bandit setting of Section 4.1 without Assumption 3.1
Algorithm 7 with any 17 E O(1) almost surely converges to playing optimal arms,
lim Σ (a) = a.s. 1-000
55)
GEAA"
The proof of this theorem breaks into two propositions, the first of which being that the sum of parameters of optimal arms tends to infinity (excluding the trivial case where all arms are equally good and Section 4. holds vacuously).
Proposition 4.3 (Infinite Optimal Parameters). Af + [K] then lim Eeer 0c(a) = oc

---

The second proposition states that all finite arms individually have their parameters diverge to negative infinity.
Proposition 4.4 (Negative Infinite Suboptimal Parameters). For every suboptimal arm E [K] lim 0, (b)
\ A",
a.s.
Equipped with these propositions, the proof of Theorem 4.2 becomes straightforward enough that we need not resort to proof sketch:
(T) EeEA)T((O) holds vacuously. Henceforth suppose A' * [K]. We have that lim EaE TT(a) 1 - lim;-so L (b)),, so it suffices to show that, for all b E [K] A", lim,-xc TT(b) = 0.
Proof of Theorem 4.2 If A [K] then EPEA.
1 for all t 2 0 and the result
To this end fix be E [K] A". We have the following bound from expanding the definition of .y:
cxp()r(b))
lim (x(b)=
lim
(Eq. (6)
1-000
1-00
ZeE|K] exp(O.(a))
(b)(
lim
(exp (z) 2 x A" C [K] (7)
t000 EPEA' (:(a)
litlle ex)(O:(b))
(8)
lim
Eae (a)
Proposition 4.4 implies that the upper limit in Eq. approaches 0 and Proposition 4.3 implies that
the lower limit goes to infinity. Thus lim ne (b) O, concluding the proof.
The proofs of Propositions and 4.4 are long and technical, and refer the reader the appendix for the details.
Reinforcement Learning
The results in RL depend on the results of Section 4 but in order to apply them we will need to port them to a slightly generalized bandit problem. We describe the necessary modifications in the following subsection, before proceeding to MDPs.
5.1 Nonstationary Bandit Setting
We still consider K K-armed bandit, with K > 2 and rewards in [- R). The interaction between the learner and the environment is much the same as in Section 4.1 with the exception that now the reward distributions are allowed to change across timesteps. That is, change out the distribution Pa E ([-[RR, R, R)) of rewards given that arm a is played with a sequence of such distributions (P.)21 and the reward at each iteration 2 is sampled from Pt, E MM R. Rl); we also allow the expected rewards given that we have E/y, (4 = a) = (a).
is played vary time, so r(a) becomes (r'(a))e21 and
However, we constrain the setting in two ways. First, we suppose that there exists filtration (Fi)c20 such that pt, yd are measuuaale and a,, F; are F--measurable. Intuitively, F, contains the information available to the learner iteration f, and this assumption means that the reward distributions (and thus their means) may only depend on the arms played and rewards observed up to the current timestep, well as additional sources of randomness that independent of the future. The second constraint on the environment that we assume the existence of a "true" mean reward vector E | R. R K and suppose that there exists some random timestep such that, for all t 12 r and all a E [K] Iraa) r' (a) < A/3, where A = min, be[K] =n())=r(()) Ir(a) r(b) is the minimum nonzero gap in the "true" mean reward between any two arms. This says that eventually the expected reward of playing arm a will settle down to a neighbourhood of r(a). and in particular that the arms in A == arg max r(a) have the highest expected reward after iteration J. Given these modifications to the bandit setting, we can extend the results of Section 4 with minimal changes. The algorithm stays exactly the same, with the only modification to Algorithm I Teing that, at line T++1 Par. becomes r2+1 p-+1
After extending all the bandit results to the nonstationary bandit setting, we can finally apply them for result in RL.
7

---

5.2 Reinforcement Learning Setting
We consider a finite-horizon MDP, defined by the tuple M = (H,S, ( where H A = Ao U... U - are finite state and action spaces, respectively, with Sn (A, = Uses, A., being the sets of possible states and (actions) at step h E H. and A, the set of possible actions from state S; Yy Sh x AA - I-R, Rl is a reward function that is bounded by R > 0; Ph Sn An + Mi(SA+) is the transition function; and p So + ()) is the initial state distribution. We denote := (x as a time-dependent policy where x² Sp, + (1 is the policy in the horizon h. An episode proceeds under the following protocol. At the beginming of the episode, the learner selects non-stationary policy æ. The episode then evolves through so ~ P and ~ (-(88) 8h+1 ~ Ph ( 88h an), Th (a 8t)) for all h E H. We define the trajectory 7 = (80; ao, ro, .1..... - an -1 -H-1). Therefore, the probability of a given trajectory is
1H-1 (Pr) --111111 p).
H -1 }} is the index set of timesteps in episode; 8 = So U....USHH and
Pr(r) p(su) ाT ( so )u su m -0-
(9)
We also define the value functions and oction-value functions for H
11
(s) E
The
Sh =
(10)
R'=h
H
(7(s,)) := == E"
TW
Sh =
an
(11)
km=h
The goal is to find time-dependent policy कt that maximizes the state-value function time 0, i.e. V0T (p) == -E-p-VV (s)]:
π arg max (p).
(12)
We also define optimal state and state-action value function, V := V and Q% =- QK In this paper, we focus on softmax parameterized policies. Specifically, we parameterize each x" by 0h for all h H by
exp(O"(ss a)) The (als) EN exp(("
(13)
(s, d'))
where 8h A with An Exes, AAl for all h H. To improve the readability, we will sometimes write Ti in place of To, and T/ in place of Ty.. The true gradient of the Eq.
12
is
(s) = ET (s,a)
log ग. (an (s) (s.
H-1
Σ rm = 1 [Alaa = a] - क. (als))
Σ h=
H-1 1
Th
(14)
h=
where Iaa a] is the indicator function of whether action is played in the horizon h. for all 8 E Sn, a E An, h E H. Since we are in the stochastic setting, we will use REINFORCE estimator estimate the gradient and update the parameters
(V.
1 Σ The -'=h
(T(aR: =a] - ., (alss)
(15)
(8,
The REINFORCE algorithm is shown Algorithm
Algorithm 2 REINFORCE
1: for each episode do
2: Sample a trajectory T using , !=
H-1
3: for all [AI, s E [S] do
4: Use Eq. 115) to update 0(8,a) a)
5: end for
6:
end for
We first show an exploration result, the counterpart to the exploration result shown above in the bandit setting, before sketching the proof of our main theorem in RL.
8

---

5.3 RL Exploration Lemma
Lemma 5.1. Running REINFORCE with any E (1) in a fiitt-horizon MDP M. for all h E H. for all reachable s E S₁, and for all E A, we have, almost surely, that every reachable state action pair will be visited i.,, i.e (s, = oc.
Proof sketch 3. First, we show that for all horizon h H. if E Sn. is reachable and played i.o, then all actions E S are also played i.o by Lemma 4.1 Next, we use induction to show that for all horizon h E H. if E Sn reachable visited i.o, then s' E Sh+1 is also visited i.o. Therefore, for all h E H. all reachable state-action pairs (s, a) E S x AA will be played i.o.
5.4 Convergence in finite-horizon MDP
Theorem 5.2 (Convergence in RL). For the MDP defined as above, using REINFORCE with constant learning rate 1) E ((1), we have, almost surely, for all 8 E So. (*) + Vo (s) as i + do
Proof sketch 4. We show the convergence theorem using the backward induction. Suppose for all 1 for all Sh, want to show that EaEA; "6 1-1 (u|s) + 1 for all Sa-1. Since EeEA; m/ (als) + 1 for all E Sn, where h E (N',.... H - 1}. we know that there exists time step r s.t (s) ( S 8 minimum non-zero gap between two Q-values. For all a E A there exists minimum gap of 3 in the Q-value. Therefore, applying the bandit convergence result, we know that ExEA; me = + as t + for all E Sh-1. Recursively, we know that for all So. EnEA; T0, (als) - 1 as t + co.
horizon h E {h'...., H 1}. we have EuEA; T/ (als)
3. where 5 is the
We also provide the statement and proof of convergence rate in the appendix (Theorem E.3
5.5 Simulations
We conduct several experiments illustrate the convergence behavior of REINFORCE algorithm in the finite-horizon setting. Experiments are performed using a chain MDP (Fig. lb with state space S {50. ... $3, Ti, ]2 where Ti and T2 are terminal states, and action space A {ag. a Taking action du in any state yields a mean reward of 0.5 and transitions to terminal state Ti. Taking action 01 in state s, (i E {0, 1, 2)) yields a mean reward of -0.5 and transitions state 8,+1- In state $3, action yields a mean reward of 7 and transitions to a terminal state T, The policy is parameterized using a softmax function, and parameters are initialized to E IR S1x|A|, For each learning rate 17. the REINFORCE algorithm run for 10a episodes across 30 seeds. Performance is evaluated by measuring the average suboptimality gap from the initial state distribution defined as Vi V0" (p), over the 30 seeds. Our first experiment (Fig. Ba demonstrates the benefits of using a large learning rate. Previous convergence analysis of REINFORCE (Theorem 4.1 Klein et al., 2024) relies on small constant learning rates, which can significantly impede practical training speed. For instance, the analysis in Klein et al. (2024) guarantees convergence with 17 S/ERT
1 where T
is the number of training episodes. our environment (H = 4, R = 7, T = 10"), ), this corresponds to an extremely small learning rate 17 10-? Therefore, we evaluated REINFORCE algorithm with larger learning rates E (0.00001, 0.001, 0.1). Fig. shows that the suboptimality gap remains nearly constant for 7 0.00001, whereas it decreases substantially faster as v) increases from 0.001 to 0.1. This demonstrates the practical benefit of employing larger learning rates for accelerated convergence, supported by our theoretical guarantees. We further explore the effect of even larger learning rates E {0.5, 1,2], presented in Fig. 3b These rates, while potentially accelerating learning if updates are favorable, generally slow down convergence compared the moderately large rates. The suboptimality curves exhibit more abrupt changes and show less consistent improvement over episodes. The large shaded regions indicate significantly higher variance with these very large learning rates. This suggests that large steps can easily push parameters away from optimal configurations, leading to prolonged exploration of suboptimal regions until corrective update is sampled. Finally, Fig. 2 iillustrates the evolution of the learned policy for optimal actions at each selecting optimal
horizon. For all learning rates, we observe, on average, that the probability actions converges first for the last horizon, then for the second-to-last, and so on, proceeding backward through the horizon. This backward convergence pattern in policy probabilities consistent with our proof strategy for the convergence of the REINFORCE algorithm, which relies on backward

---

induction approach. We also extend our experiments to demonstrate the relationship between the algorithm'ss 's performance and different learning rates. Details on the experimental setups and results can be found in the section Appendix D Overall, we consistently find a "bowl-shaped" relationship between the learning rate and performance, meaning both exessively small and exessively large learning rates lead to high suboptimality, while middling values achieve the smallest suboptimality. The specific shape and optimal point of this bowl vary significantly with the environment's 's structure. Remark 5.3. It worth noting that not all environments exhibit this specific backward convergence pattern in learning optimal policy.
$11400
(a) Benefits of using larger learning rates.
(b) Drawbacks of using exessively large learning rales.
Figure 3: Fig, 3a shows that using a larger learning rate can improve the performance REINFORCE, while Fig. shows that excessively large learning rates have substantial variance, which can slow down the convergence rate.
Conclusions and Future work
This work enhances our understanding of the convergence properties the widely used REINFORCE algorithm. Our novel proof offers deeper insights into the exploration effects of stochastic gradient methods and raises new research questions. Notably, recent findings by Mei et al. (2024a) indicate a convergence rate of Ollo((t)/t) for stochastic gradient bandit algorithms. As demonstrated in Fig. 3b REINFORCE with excessively large learning rates exhibits high variance, impeding convergence. Future work could explore optimal learning schedules to harness the initial benefits of larger rates while subsequently mitigating variance.
7 Acknowledgement and Disclosure of funding
The authors would like to thank Jeffrey Rosenthal for pointing out relevant results and materials regarding non-convergence results. Csaba Szepesvári and Dale Schuurmans gratefully acknowledge funding from the Canada CIFAR AI Chairs Program, Amii and NSERC.
04
Figure 4: These figures show the convergence rate of the optimal policy in each horizon for different learning rates. In particular, we observe that the optimal policy the last horizon will converge first, then the second-to- last one until the first horizon. This observation aligns with our analysis.
10

---

References
P.-A. Absil, R. Mahony, and B. Andrews. Convergence of the iterates of descent methods for analytic cost functions. SIAM Journal on Optimization, 16(2):331-547) 2005.
A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation. and distribution shift, 2020. URL https://arxii org/ at/aabb//1999 2tbbb//9.9000211111
I. Akkaya, M. Andrychowicz, M. Chociej. M. Litwin, B. McGrew, A. Petron, A. Paino, M. Plappert, G. Powell, R. Ribas, et al. Solving rubik's cube with a robot hand. arXiv preprint arXiv: 2019.
M. Bramson, J. Quastel, and J. S. Rosenthal. When can martingales avoid ruin? preprint, 2004.
Breiman. Probability. SIAM, 1992.
S. Cen, C. Cheng, Y. Chen, Y. Wei, and Y. Chi. Fast global convergence of natural policy gradient methods with entropy regularization, 2021. URL httpp://arriii wtwp/bg/////o.oo./////// 06558
Y.-J Chen, N.-C. Huang. C. pei Lee, and P.-.. Hsieh. Accelerated policy gradient: On the convergence rates of the nesterov momentum for reinforcement learning, In Forty-first International Conference on Machine Learning, 2024. URL htttips:/oppnrevviee wwt.:/wwww......./e/aaaaeeeea.aa
B. Davis. Divergence properties of some martingale transforms. The Annals of Mathematical Statistics, 40(5): 1852-1854, 1969.
Y. Ding, J. Zhang, and J. Lavaci. On the global optimum convergence of momentum camentum-bbaed policy gradient, 2022. URL https://arxiv org/ wtng/abs/2110. 10116
Y. Ding, J. Zhang, H. Lee, and J. Lavaci. Beyond exact gradients: Convergence of stochastic soft-max policy gradient methods with entropy regularization, 2024. URL https://arxiv wwwpsxwwwww..r.aeoo.ee aa//a/bs//111 2atps//211...1.111
J. L. Doob. Measure theory, volume 143. Springer Science & Business Media, 2012.
Fatkhullin, A. Barakat, Kireeva, and N. Hc. Stochastic policy gradient methods: Improved sample complexity for fisher-non-degenerate policies, 2023. httpssttss//arxxi org/ www.ab/2......e 01734
D. A. Freedman. On tail probabilities for martingales. the Annals Probability, pages 100-118, 1975.
S. Khodadadian, P. R. Jhunjhunwala, S. M. Varma, and S. T. Maguluri. On the linear convergence of natural policy gradient algorithm, 2021. (tRls.ttts:://eet //axivv.///rvvaaaaa org/ abs/2105..50 01424
S. Klein, S. Weissmann, and L. Döring, Beyond stationarity: Convergence analysis of stochastic softmax policy gradient methods, 2024. URL
G. Lan. Policy mirror descent for reinforcement Icamnngg: Linear convergence, new sampling complexity, and generalized problem classes, 2022. URL http:/ttts/:/xxiiii wttp//og//abbabaao/oo 200220011115155
Lillicrap, J. Hunt, A. Pritzel, Heess, T. Erez, Y. Tassa, D. Silver, D. Wierstra. Continuous control with deep reinforcement learning. 2019. URL testps://arxiv org/ars./////..oooo.ooo...o //////b//// 1109, 02971
Liu, W. Li, and K. Wei. Elementary analysis of policy gradient methods. arXiv preprint arXiv:2404.03372 2024. http/://////xxx ortp:///////ab//////////// 03372
S. Masiha, S. Salehkaleybar, N. He. N. Kiyavash, and Thiran. Stochastic second-order methods improve best-known sample complexity of sgd for gradient-dominater function, 2023. URLL/tttp:///ariv org/ aba/ 12856
J. Mci, Xiao, B. Dai, L. Li, C. Szepesvári, and D. Schuurmans. Escaping the gravitational pull of softmax. Advances Neural Information Processing Systems, 13:21130-2111 140, 2020a.
J. Mei, C. Xiao, C. Szepeswari, and D. Schuurmans. On the global convergence rates of softmax policy gradient http://axxvv..rr///////00/00
methods, 2020b.
J. Mci, B. Dai, C. Xiao, C. Szepesvari, and D. Schuurmans, Understanding the effect of stochasticity in policy bttttp:://axxii.orr///aae
optimization, 2021.
15572
J. Mei, Y. Gao, B. Dai, C. Szepesvari, and D. Schuurmans. Leveraging non con-uniformity in first-order non-convex optimization, 2022. URL httts:ttttaaiiii /ttp:///ALtta////aaaar////////// 06072
J. Mei, W. Chung, V. Thomas, B. Dai, C. Szepesvari, and D. Schuurmans. The role of baselines in policy gradient optimization, 2023. URL htttp:://arri: org/

---

J. Mei, B. Dai, A. Agarwal, S. Vaswani, A. Raj. C. Szepesvari. and D. Schuurmans. Small steps more: Global convergence of stochastic gradient bandits for arbitrary learning rates. In The Thiriy-eighth Annual Conference on Neural Information Processing Systems, 2024a. URLhhtpps:///// htaetpp://peenreiii..eeetttt net/forum Id id=qsdKvIAKG)
Mei, Zhong. Dai, A. Agarwal, C. Szepesvari. and D. Schuurmans. Stochastic gradient succeeds for bandits, 2024b. UtLhhtss::/// //appxi////xxii//////paarrarmv http://rggaabb//sgeee 17235
Ouyang, J. Wu, X. Jiang, D. Almeida, L. Wainwright, P. Mishkin, C. Zhang, Agarwal, K. Slama, A. Ray. J. Schulman, J. Hilton, F. Kelton, L. Miller, M. Simens, A. Askell, P. Welinder, P. Christiano, J. Leike, and R. Lowe. Training language models to follow instructions with human feedback, 2022. URL https://arxiv org/ abs///////// /203. 2203.02156
B. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics, 3(4):664 878, 1963. ISSN 0041 -553. doi: http:///bb..rg//11.11100000 90382-3. URL https: www. www.eeedeeeeeee.ccccocoooo cttetttooccccccceoo//eecccoe http:/sccennceeeeeee /ttps//coooarccc//////0015513300
R. Rafailov, A. Sharma, E. Mitchell, S. Ermon, C. D. Manning, and C. Finn. Direct preferrccc optimiiaaonnoooiiiiiiiaiiiion Your language model is secretly reward model, 2024. URL http:://aaax....rr//aaa/////////
18290
J. Schulman, S. Levine, P. Moritz, M. I. Jordan, and P. Abbeel. Trust region policy optimization, 2017a. URL https://arxiy, http://w...g.////e////e/ooes 1ttp//552..000 05477
J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms, 2017b. URL httpss:/arxii...ee. http:///aaaii..ooooa//////////// 063477
R. Sutton and A. Barto. Reinforcement Learning, second edition: An Introduction. Adaptive Computation and Machine Learning series. MIT Press, 2018, ISBN 9780262039246. URL htttt::/ttoooosse/ google. ca/
books?idd=3WWOsaMPP...
Vinyals, Babuschkin, M. Czamecki, M. Mathieu, Dudzik, J. Chung, D. Choi, Powell, T. Ewalds, P. Georgiev, et al. Grandmaster level in starcraft using multi-agent reinforcement learning. nature, 575 (7782):350-354, 2019.
R. J. Williams. Simple statistical gradient-followngg algorithms for connectionist reinforcement learning. Machine learning, 8:229-256 1992.
L. Xiao. On the convergence rates of policy gradient methods, 2022. URL httLlpp/////xxt.or//ab////// 07443
J. Zhang, Kim, B. D'onogguu, and S. Boyd. Sample efficient reinforcement learning with reinforce, 2020a. URL https:://aakii wwwg/o/g/aa...oooooooooooooooee. abs/2010. 11364
J. Zhang. A. Koppel, A. S. Bedi, C. Szepesvari, and M. Wang. Variational policy gradient method for reinforce- ment lcarning with general utilities, 2020b. URL httph:t/////e //arxiv org/ abs www.ab//0... 200100211100
12

---

In this appendix will deal repeatedly with almost events, ie. events that occur with probability 1. We typically mention this throughout the proofs, except for in one important case where "a.s." is omitted to reduce clutter: whenever statements involving conditional expectations (by extension conditional probabilities, variances) do not have explieit probabilistic quantification, they understood to hold almost surely. Of course, this the only possible interpretation for such statements, since conditional expectations are only defined up to set of measure 0.
A Technical Tools
We begin with some fundamental results from probability theory. The first is generalization of the Borel-Cantelli Lemma.
Lemma A.1 (Extended Borel-Cantelly Cantelli Lemma, Corollary 5.29 of Breiman 1992)). Given a filtration (Fi)ezo and sequence of events (At)120 with A, E for all
Σ [[A = 0
Σ ((A =
(16)
120
120
That is, (At)120 occurs i.o. if and only if E ((A is infinite, to a set of measure zero.
Our analysis relies critically and repeatedly on the celebrated incquality of Freedman. The version we will use is similar to the one stated by Mei et al. (2024a b Since require a general filtration, we include the original statement by Freedman below in Lemma A.2 followed by the statement and derivation of the form most convenient to in Lemma A.3 Whenever mention "Freedman's 's
inequality" elsewhere this work it shall refer to the latter.
Lemma A.2 ((Original) Freedman's 's Incquality, Theorem 1.6 of Freedman 1975)). Given a filtered probability space with filtration (Fr).20, an adapted sequence of random variables (X1)121 and constants a, > O, Vt 2 1 F[x,
and [Xel then
P 1 2
Σ X, 2 a, Σ Var Va <b S exp
- a
(17)
2(a + b)
Lemma A.3 (Freedman's 's Inequality). Let (Xt)t21 be random sequence adapted to the filtration
(Fi) B 2 0 be a constant such that Vt 2 0 : [X1] S B, and denote V₁ == Eie(t] FRr1X
For any 8 (0, 1), it holds with probability 5 that
1/+ + 2
Vt #21:: Σ - < 20
log
(18)
xE(()
Remark A.4. The derivation of Lemma A.3 closely follows the proof of Theorem C.3 of Mei et al. (2024b). We aimed for simple bound rather than tight one.
Proof. Fix e E (0, 1), and let S, = Σieu X, and V := Eiejo [ar[X,]FF-]].. First we will suppose that [= = 0 and [x| < for all t > 1, and show that
(Vi++) e
Ve 2
P 3t 1 S. > 10 log
sc.
(19)
For 2 1 let g(x) log((= + 2)2 and we have
0(x) + V((zx
(20)
S Glog((> + 2)/e) + (3e//og((x+2))) +
((x + 223 s (x + 2)2 (21)
Glog((> + 2)/{) + 3/3llo(( + 2)2/()
(log((2 + 2)%/)) 2 log(4) 2 1) (22)
6log((> + 2)/c) 22/3rlog((e 2)/e)
((x+2)2 s (x+2)²/63 2)2 (23)
s 6llg((( + +4 1
log( + +))r)
(24)
< 10 2)/c).
(25)
13

---

Setting x : V/2 in Eq. 25 yields
Vi +
P P S, 2 10 10 1log
(26)
S 21:11:::0 2: + VV(V)VV
(27)
P(3 2,20(()) + Vo(V,,, is
(28)
120
Σ i20
P(3 2 1: 0 + Vo(ii, V3 ((++)
(g, v. are increasing) (29)
(o(1) + Vg(iii
exp
( (1)i +i+
120
(Lemma A.2 with a g(i) Vg(iti and b : i+ 1) (30)
To control the term appearing in the exp above, we will use the following inequality, which holds for
2 2 and i 2 0:
u(u 2v 2v +i)
(31)
2(u + ui + +
2(u + Vui + +i+1)
u 2u Gy uu + 3i fi
(32)
3 2u 2/ wi + +
2 u/3.
(u 2) (33)
Since g(i) 2 3 1og(
4) 2 2, we can combine the above two displays by setting == g(i) and conclude
Vi + 2
P P( 1: S, 10 + 1log
exp( (1(()3)
(34)
120
1
(35)
(i + 2)²
é
Σ
i-2
(36)
122
c(T² /6 - 1)
Ens1 = n² /6) (37)
S.
(38)
We are finished showing Eq. (99. We can apply this result to both (Xt) and (-X,) setting E : 5/2 in each application, whence a union bound guarantees that, with probability at least - 8,
V1 +
Vt 2 1
Σ | 10 1log
(39)
8/2
Ve +2
< 10 100V++10 log
- +log(2)
(40)
V
$ 20 Vi + log
(41)
Given random sequence (X))221 that satisfies the sequence (x/B)
X,
B for some
2 1, we can apply Eq. (41 to
V1/B² +
Yt 1
Σ iE(t]
X,/B| < 20 + 1og
(42)
8
12+2
$ 20 20 + log
(V//3² < V,) (43)
V.+2
Σ
X1 < 20 20 Bd B2
(44)
SE/d
14

---

with probability 1- - 6. Combining Eq. 41 which holds for [X, S 1, and Eq. 44 which holds for |x,| < B where 2 1, and upper bounding max [B 1) < B +1 we can remove the requirement
that B 2 and conclude that, if [
0 and Xx S B for all / 2 1, with probability 1
V 8
121: ::
Σ EE
X S
20 V + B + log
(45)
To remove the assumption that Vt Eq. (45) to (Xt - [[[x))==- noting that if Xel S B then X, - EX S 2B.
1 1
[i-1
and get the desired result, we apply
The following result applies Freedman's Inequality
sequence of bounded, and eventually (condi- tionally) boff-bounded, random variables. It says that if the conditional expectations are not summable then the variables themselves will not be summable. We expect that the result folklore, but cannot find a reference.
Lemma A.5 (Freedman Divergence Trick). Let (Xt)121 be a random sequence adapted to the [Xel S B. Suppose
filtration (Fi)a2 and B 2 be constant such that Vt. 2 Σiz1 TE [[ = oc and, for some random (a.s. finite) index t 2 1 and constant C 2 0,
for all I 2 T, Var(Xx]FF-11] S cE(X, Then Σ1>1 X oo a.s.
Remark A.6. Note that the result does not require T to be stopping time.
Proof. For t 2 0 let S. == Eieny X,, S. = Eiej B| and V = Eie(y] Var[X,]Fii-] For any d E (0, 1]. with probability
apply Freedman's 's Inequality (Lemma A.3) to (X1))21 This gives that, 8, for any t T,
V 8
2, 20 V1 4B² + 1log
(46)
V1 V, + V, +2
=3, - 20 / V, + V, 4B3 1log
(47)
V1 V, TB2 +2
25, - 5, - - 20 V V, (4+ + +1
8
(X111 S B) (48)
C(S. - S,) + TB² +2
2 2 - 20 C(S. - ST) 4T + log
(Var[X, S CE[X,[FF-1] for 2 T) (49)
By ussumption lim, 3, oo, so lim, 3. S, oc as well. Clearly, the subtrahend in the display above is o(5, 5.). Hence, taking the limit of t + co, we have lim, S, = oo with probability Since 8 was arbitrary, this also holds with probability one (by taking 6 + 0).
Finally, we will need a classic result of Doob.
Lemma A.7 (Doob's Martingale Convergence Theorem (Doob, 2012 ). Given a random se- quence (Xi)221 adapted to the filtration (Fi)zo. if Vt 2 I E[X, F(-1] I X(-1 and supezo E|- mnin(X,,0) 0)] < oc, then (X1)21 converges a.s. In particular, X, - X a.s. as t + oo, where := lim sup, X, and [[[x[] < 0C.
B Bandits
In this section all results are stated in the bandit setting described in Section 4.1 The first subsection
establishes the results needed for the proof of convergence bandits, Theorem 4.2
The second
subsection proves that convergence is not always one-hot policy, Proposition 3.2
B.1 Convergence
We begin with simple but crucial property of Algorithm I which follows from a symmetry of the update rule.
15

---

Lemma B.1 (Conservation of mass), For all 2 0, EmE[K] 8i(a) = EmE(K] Oo(a).
Proof. Proceeding by induction, the base is tautological; recalling that a, is the arm played at time t, we have
(a) = (a+1
Σ
(2+1(a)
(50)
aE [K]
aa(K]Mat)
- -O((as) + n1(1 - =r(at))rr((n)) +
(O:(a) - (m((a)))(aa))
(51)
aE
-mri(ae)+ + Σ [Or(a) (mT(())c((a)
(52)
aE[K]
= =mr((a))+ +
Σ
0z(a) - mpr(as) Σ x((a)
(53)
aE[K]
aE[K]
Σ 0c(a).
Eee(K] Te(a) 1) (54)
KE[K]
The rest of the proofs in this section will refer to the filtration (Fi) defined by J; ==:==(((e a((a,, ri) r))ee))
and we adopt the shorthands [. == E [F, and Varz[ == Varl [F.). The following result is a stronger version of Lemma 2 of Mei et al. (2024)), and it guarantees that Algorithm I explores enough to keep trying all arms forever regardless of the observations.
Lemma 4.1 (Bandit Exploration). Using Algorithm 7 with any constant learning rate nj @(1), every arm is almost swrely played infinitely often. That is, Va E [K] (a) = 0o almost surely.
Proof. The first step is show that, for any arm b E [K], if K > 0 : a. b} 00 then
sup, [b)( < co a.s. Picking b E [K] and setting m == sup [0] U (1 2 0 G2 = b)). without
assuming |L 2 0 a. = bb] Do we have the bound
sup [0x(b] < (b) + sup
(b) (b)l
(triangle inequality) (55)
iE(1]
S 10)(b) + Σ
(b(b)) 0,-1(b]
Ei 0.-1(6) 0) (56)
121
= 10o(b) + Σ
(b) - 0 0,-1
+
Σ 10.(6) - (b-1
(57)
.E(m]
(0b(b) + Σ nR + Σ
RRT, (b)
(update rule of Algorithm I
(58)
km/m]
12m
- (0b(b) + RnRmm m + Σ
(b))
E RTo, (b) > 0) (59)
120
ab))
(60)
Also, the Extended Borel-Cantelli Lemma (Lemma A.I applied to (Fi) with the event sequence
A. {a+ = b} implies
IIa, b] 00- 120
(b) < 00.
(61)
120
If (1 0::00000 0: =b=b) < 0o then m < 0o and E
T(a = b) < oo, and the latter inequality together
with Eq. 661) implies E Σ1>0 Te (b) < xo a.s, thus Eq. (60) yields sup, [b)( < a(b) < co a.s. A
union bound over b E [K] implies that almost surely
Yb E [
|[t 2 : at = b) <0 a(b) xo.
(62)
We are ready to fix an arm a E [K] and show that the event E = {1( 2 : ot = a}l < xc] has probability O. For the remainder of the proof until the almost the very end we will work under the
16

---

assumption that & occurs. On & we have a(a) < oo a.s, which implies Σiso Te(a) < oo a.s, which in turn implies lim, (a) 0 a.s. The definition of (e(a) gives us exp(O((a))
(a)) = lim
(Eq. ② (63)
t [be[k] (xp(O.(6))
lim exp(-a(a))
(a(a) 2 (a)(a))) (64)
DME[K] exp(O:(b))
exp(-a(a))
2 lim 1 K exp(maxxe11]] (t)) Ebe(k) ex)(()())) S K exp(max6е(ι] (b)) (65)
so from lim, (T(aa) 0 a.s. we get lim, [M] (c( oc a.s. Then conservation of mass (Lemma B.1) implies that lim, minse[k] (b( 00 as. By Eq. (62) all arms that are selected only finitely often have parameters bounded away from -00 a.s, so there is a.s. an arm that is played i.o. with lirm inf, (b) -00 We will refer to such an arm b for the remainder of the proof. However, because b is played i.,, another application
the Extended Borel-Cantelli Lemma (to < oo a.s, have that (b) > (a), and equivalently 0, > (a), for infinitely many t >> 0 a.s. In summary, (b) oscillates from being arbitrarily low to being larger than (a(a) 2 (a)
(Fi)o20 with events A, == {a= b)) yields Σ.20 To (b)
a.s. Since Ei>0 (T(a)
We will now argue that, for sufficiently large t, if (b) S (a) but 0c+1 (b) > O (a) then o = b. Let be the minimum timestep such that, for all 2 T.
max (c) 2 log(n + a(a), and a, + aa. cE(K]
(66)
Since we are working on the event & we have a = a for only finitely many t, log(n + a(a) < co
a.s, and lim, [a] (c(c) oo a.s; taken together, these observations imply that T < 0o exists a.s.
For L 2 T. suppose 0r(b)= < (a) and at f b, and we must show (b+) S (a)
(67)
0c(b) - (b))((((a)) S 0.(a) - (ma(()rr(aa))
(ar $ {a, b))
(68)
(T)(a) [b)) - 0.(a) - (b).
(69)
Since (b) S ((()) we have (b) S (a).. and standard inequalities yield
(T) - mb(b)) S (a) - Ne (b))
(0 S (((a) (b)) (70)
n/R exp(0x(a)) (b))
(71)
E (0
exp(O:(a)) (x)(
S R/R exp(max,G|K) [K] (c))
(EeE[K) exp( 2 exp(max.e(K) (c(c)) (72)
exp(O((a)) - (x)((O(()))
(Eq. 66 a(a) 2 (a())) (73)
= 1 - exp(O.(a))
-
(74)
< 1 (1 + (b) (.()))
(exp(x) 2 1 x:) (75)
Thus Eq. (69 holds and we have established that, for all 2 T, Of < (a(a) and (b+1 >
0.+1 (a) then a₂ b. Since (b) fluctuates from below (a) to above ito we have that the events in the sequence (B:)c20 defined by B, := (b) < (a))), a =b} E Fi+1 occur i.o, a.s. Applying the Extended Borel-Cantelli Lemma to (Fi)120 and (B:):20 implies that Eizo P(B. x a.s.
However,
P(B.)F,) ((O, < (())) S (a),)
(76)
so EizO P(B.).)) S Tia) < a.s.
At this point we have that, on event E, both Σ P(B.FF)) < x a.s. and Ei20 P(B. = co a.s. Since these events are mutually exclusive they both occur with probability O, and since they are jointly exhaustive we have P(E)= = O.
It is easy to that (b) must also become arbitrarily large i., but this is not necessary for the proof.
17

---

The proof of our main result in the bandit setting, that lim EOE TT(a) 1, is broken into two propositions: the first guarantees that lim EncA- 0((a)) = xc, in particular that as the time steps get large at least one a E A" will have an arbitrarily large paramete the second proposition says that ci (b) oc for all b E [K] \A" Taken together, the propositions imply that eventually some (potentially time step dependent) optimal arm dominates every suboptimal arm, establishing Convergence Bandits (Theorem 4.2 We now turn to proving the two propositions.
The subsequent proofs will go a little smoother with some extra notation; we define A := men [K ((((()))))( Ir(a) r(6]] to be the minimum nonzero gap between expected rewards of arms and r(A") aa r(a) be the maximum attainable expected reward. Finally, over- load (-).) to take sets as input, i.e, given S C [K] we let n. (S) := Eaes (e(a) be the probability
that an arm in S is selected. With these abbreviations in hand, the first proposition is as follows.
Proposition 4.3 (Infinite Optimal Parameters). A" + [K] then lim EnEs 0z(a) oc a.s.
Proof. Fort 2 0, let X (41(4))0((c) (a), such that Ei=o X, =cEe 0141(0) Bo(a).
-
By the update rule of Algorithm note also that
= Σ (T/a a) :Te(a))re.
(77)
DEA'
The conditional expectation of X, given Fe can be lower bounded by
Σ KE[K]
[ = x]
Eee(K) Ia. = a] 1) (78)
Σ
Eg Maa a)n(1 (rr))) +
[Ta = (e((-m((A"))rr
a
BE[KTTA
(Eq. (77)) (79)
71(1 ax(A")) Σ
E.[l(a, a]ri] (A*)
Σ
[[aa b]ri]
a
bEiKTiA
(Te is F--masurralle (80)
= (1(1 (A())) "EA'
Σ Te(a)r(a) - (A-)
Σ
(bbr((b)
BE KE
(E, . 1 [o]==,h zz()(())) (81)
2 n1(1 (a(A)) Σ Te(o)((A)) (A
Σ (+()(r((A)) -A)
BEAL
BEIKTRA
(r(a) = =((A'), r(b) Sr(At) A) (82)
= = - (AAA)) (((A))-)) EAEA TT(a) (e(A'), EBERRIAA (b( =1 11 - m. (A²)) (83)
(84)
Excluding the trivial case where A" [K]. i.c. all arms equally good.
18

---

and the conditional variance can be upper bounded by
Vari[Xa] S BB [X
(85)
= Σ
E, [, = a
EuE(K) Maa = a] = 1) (86)
aE[K]
Σ
T [aa =a((1(1 - me(A4))))
Es Ma b]( 17t4 ()Tr((A))aa)
aEA-
BE[K]]
(Eq. (77) (87)
1 - ( (((A))) R2 Σ
B.|1[a, = a]] + (()
E, [1 = b]]
"EAA
bE[K]
(r² - R (88)
n7(11 Th (A'))) R2
Σ Te(a) + m))))( R2
(b)
DEAL"
6E[K]
(E, [1[e = [] = TT(-)) (89)
(1))((((AA'))) (Ar) + TT (1 - mT(Adt)) =fp R2 (112((1 (e(A)))
EnEA Te(a) =T(A"), EBE[KTIA- (((b)= = - (A²)) (90)
R²² (A))(( - (1("(()))))))
(91)
Thus for all t 2 0 we have Var:[Xo] S E S nR, and X, is F -easuuaba........
Setting == nR, == O, and c == T we need only to prove that Σ.zo [x 00, at which point we can apply the Freedman Divergence Trick (Lemma A.5 to conclude
lim Σ (c+i(a)= -Oo(a) Σ X₂ = 00 a.s, "EA*
(92)
lim
Σ 0,(a) = 00 a.s. aE
EnEA Bo(a) < 00) (93)
Thus in the remainder of the proof we turn our attention to showing Σ1z0 E, [X,] = 00. Applying
Eq. 84 and v/ > 0, we need only show that
Σ
T. (1 - (1AA()))) = 00.
(94)
120
Lemma 4.1 together with + A + [K] implies that
Σ 1aa E A- = Σ 1aa $ A- = 00 a.s. $20
(95)
120
= 1 (Ar). the Extended Borel-Cantelll Since P(a, E F.) = (AA)) and P(a, & A)
Lemma (Lemmal A. applied to Eq. (95) furnishes Σi (A*) E1 (At)) xo a.s.
We now break into cases to show that Eq. (94) holds regardless of the behavior of (AA)).
If T. (A*) 2 1/2 only finitely often then we can set u max 2 0 (A*) 2 1/2] for
Ne (A*)
Σ (144)(1T((A)))))
2 = 00.
(96)
120
t>a
Similarly, if (A*) < 1/2 only finitely often then u = max (1 2 0 : (A(A < 1/23 gives us
n, (A*) = xc
Σ
(1(4)((1
(97)
2
220
t>a
We can narrow our focus to the case where Te. (AA)) is both above and below 1/2 i.o. In particular, there must be infinitely many 2 0 such that Te (A*) < 1/2 but To.., (A*) 2 1/2, and for such t we have
EAEA- exp(0++1(a))
1 (A')
(Eq. (98)
=EEA exp(0++1(a)) + E EoE(K)ar- exp(0c+1(b))
19

---

The above equation is of the form 2/(x + y), where 2 == EBEA. exp(fe+1(a)) and y == ENEIKTAA- (b))))+1(b)). Since z/(x + y) is increasing in I and decreasing in y for x, y > 0, and (2+1(c) - Oe(c)) S nR for all c E [K], we can maximize the right hand side for the upper bound
EMEr- exp(0r(a) + +ftt
To (A4) S
(99)
EeEh exp(O:(a)) + RR) EBELKRA exp(Or(b) R))
Also, me(Aa) 1/2 yields EMEA- exp(Or(a)) < EnE(KTAA exp(O so
EnEr exp(Ox(a) +
(100)
EeEs- exp(0x(a) + R) EDE[KTLA- exp(O:(b) 111
exp(1) EXEA' (x)(
(101)
exp(nR) Σ EaEr' exp(O((a)) + exp(-nRR)
-n ΣbE:K]A exp(9((b))
exp(n EeEA- (x)(
(exp(nR) + exp(-nnRR
CEE exp(Oi(a))
CuEA- exp(6r(a)) < EbE(KTAA ex)( (102)
exp(nR)
exp(2nR)
(103)
exp(1)l) + exp(-n118)
exp(2nll) +1
Connecting the above displays, there are infinitely many t 0 with n. (Ar) < 1/2 and TT, (A') > 1/2, and for such we have Te, (A*) > (txp((2))((ex(((2)) +1) = (exp(2n) + +1)
Therefore No.. (A)) TB._, (A-)) 2 (2exp(2n + 2)- i.o establishing Eq. (94).
The second proposition has more complicated proof, due the technical difficulty added by having multiple suboptimal arms with the same expected value. Controlling the suboptimal arms will be much more convenient with the following extra notation. Letting n == (r(a) : a [K]]] be the size of the range of the expected reward vector we partition the arms into (L.)ve(n). where Φ := arg m (K] r(a). Thus & is the set of arms with minimal expected reward, 42 is the set of arms with the second lowest expected reward, and so forth, culminating with $ A Given E [rz]. we will use the shorthands 4;- == Ujcro and Φ == Dy Note that Φ; and $ the sets of arms with lower, respectively higher, expected reward than the arms in Φ First will conjure up couple bound that hold for the increments of suboptimal parameters.
Lemma B.2 (Bounds on the Expectation and Variance Increments for Suboptimal Arms). For any i [n 1), for any b E &; we have the bounds:
E, (0(+1 - 0,(b
I (1-((((11)())))00) (r(b) + ()T)())) + (RT((1))) (104)
Var, (b)) (T(((6(1--
(105)
20

---

Proof.
Eg E,(0r41(b) - 0.(b)]
Σ
Ea[ = (0(0+11 0,(b))]
EeeKKy Ma - aj = 1) (106)
aE(K]
E.[ = b)n(1 - Te (b))rr+) +
E, [[a (x)
ac a
(update rule of Algorithm
T (107)
-1(1- - Te(6)) - -)m
Σ
HL a|rel
aE(K]](0)
(IT, is F:-meauurable) (108)
= -1 - - (p)
Σ Te(a)r(a) (E = -rral = m((-)r()) (109)
= mmm((6 (1 (1-
Σ m=(a)(())-
Σ nt(c)((c) - Σ ne(d)r(d))
dE
(110)
$ ()m((b) (11 (b))(())) r(b)
Σ
(t(a) (r(b) + A) Σ Ti(c) + Σ (d(d)
d
(r(c) 2 r(()
A r(d)
R)
(111)
(1- - (r(b) + ()=(( + Rm, RT, (07))
(112)
Varz(0++1(0) -Oe(b)] S (e(((1+1(0)) - (b)))
(113)
Σ
E.[I[a = al(0(+1 -
Ene[K]] Iaa = a] = 1) (114)
<E(K]
< R, [Ta, = b)1 R2 (b)))] +
E, = = R² (b)
[c(K]](b) (update rule of Algorithm ! (115)
- (T + ( - -
(E, -] m (-)) (116)
= R²2 (b)(1 - (b))
(117)
The next proposition will be applied inductively to control the relationship between the expectation and variance of arbitrary suboptimal arms.
Lemma B.3. For constants C, C' 2 0 and i E [n 11, if all b E Φ7 satisfy som 0,(b) 00 a.s. then there a.s. exists a finite timestep 7 such that, for all c E BiF E.EA- (a(a) 2 CC+C'
Proof. Without loss of generality suppose C' 2 1. Throughout the proof we will use the following two constants, which depend on C. and C":
U1 C'(KnR + Klog(SRK/A+ + K)) C, and
(118)
U2 = nu + log(BoKK/))) + 1).
(119)
Fix E (0, 1), and define
+ 4n1l2//A e/K
D = sup II -up--t x20
20 1 4K R2 ///3 log
(120)
noting that D < oc Proposition 4.3 says that lim, Ene (a(a) xo a.s, and we have by assumption that lim, (b) -00 a.s. for all b E ④, Together these observations guarantee an a.s. finite
21

---

timestep j such that
Σ 04(a) 2 U1 + D2 - 2 max 0p(b) "EAA
(121)
Consider the collection of sequences ((x))) 1>> : :be E +. defined by X; : (b( - (b), and
the sequence (Yz) defined by Y; := =EEEA (a) - -,-11 (a). For each b E ΦT (X)) satisfies the requirements of Freedman's 's Inequality (Lemma A.3 with B : n/t; also, (Ye)ssa does with := KnR. Therefore we can apply Freedman's 's Inequality with 8 =- e/ K all of these sequences simultaneously and take union bound conclude that, with probability - < . 1)/K S -e,
2 Encker Vark- (v:)
Σ (((a) - 0m((a)= 2 Σ
E
20
1+ 1 +
Vark-1 [ log
e/K
"EAA
MEASI
(122)
22+ Σ
_ucksr Vark- (xx]
vb E 27: : 0cbb) V E
Ex
1 + 20
1 + 41/2 +
Var=-1 log
e/K
pskkt
askgt
(123)
for all t > nr. Let & denote the event that both Eqs. 122 and 123)
hold at all such t. We will argue
that, on E,
Σ (,(a)) 2 U, 2
max (b)
(124)
DE
"EA'
for all 2 by strong induction. Thus let t 2 p. and suppose that Eq. 124 holds with k in place of I, for all y S k < 4, noting that it holds for k = y by the definition of μ.. Eqs. (84) and 991 together imply that
RR S
Rn V
Vark-1 [V&)
S
1
(125)
A
A
for l > 14, so the assumption that event & holds implies
Σ (,(a) 2 Σ 0a(a)= - DD a
(126)
"E
D
(Eq.
121
(127)
Now pick an arbitrary E Φ Without loss of generality, say b E D some j < i. For μ S k < t the inductive hypothesis implies that there exists E A such that (a(a) 2 U1/K. K. Thus
The (0)) Z Fx (1))
(0 C o7 a E 4)) (128)
2 //)
m (b( I 0) (129)
11+ 4R/A,
(130)
where the final inequality above follows from U, 2 K log(K (K 4K/A)). Defining the constant
= (A/2 + r(b) + R) + r(b) + Rt,, we have < (A + 4 (2A + 4/t),, which implies
< < ne ())m/(())))))) Therefore
Tx 2 -
(T))) (
7
(131)
= イイ(()) 2 (Tt (b)) (
(132)
+ (r) +=((0)(A++0)++ 2 (A/2+r(1)) +
TI (o,))
(133)
* (A+
R(1 T/
(x (1)) (0))) 2 (0]++(0)[1
(134)
+ -11 - n ()22 2 (1 (1) -
(A + r(6)) + (
(135)
Combining Eqs.
104) and (35) produces
7
E, [ <
2 T (b) Tx (
(136)
22

---

From Eq. 130 we have TA (a)
2 (T,
2 Th& (T)) so TT(2,) 2 1/2. Thus Eqs. (105)
and T36p together provide
n
1
S
(b)(b)
(137)
4
A
Vark-1
(138)
Rn
Eqs. 123 and [38 imply
(b) ((( - 0,( 02( - (b)++ + < <-D+D=0
(139)
(140)
(141)
Since 4;, was arbitrary, this concludes the inductive argument. We have shown that, on E,
Eq. (24) holds.
Define the stopping time v by
v:= min t2 (vb :.(()) < U2)
Σ (:(a) <Ui) "EA
max 8,( > 0) })}
(,(b)>)
bE
(142)
and define (Z)) by Ze == Eseo, max minn(t)))) (b), 0). We will show that (Z))zza is a super-
martingale, i.c. for all t 2 μ., E, Z,+1 Z,] <. 0. If 2 y then we have Ee[Ze+1 - 2,] = 0, so
assume < v. Let B {b E $ (.(b) 2 R and C : {c E $ 0e(c) < nR), so
E, Zı] =
Eg (fmax((14110 0) max 0)]
(t < 12) (143)
b
[m (b), (ax, 0)] + Σ
Eg [max((00_(()))0)) max(0
BEB
cEC
(144)
The terms in the sum on the left of Eq. 144) can bounded by
E [m(max((++1(b)
max(O. 0)] = E, (0 (b) (r(b))
(00+1 (b) (b) nR, (,(b) 2 0 R)) (145)
2 ne (b) -T.(+)))
(146)
where the last incquality above comes from Eq. (36 and the fact that t For the sum on the right of Eq. (144) we can bound the terms by
E, (c) (c(e)] E, [aa c](0 0r(c)) + E, + c((0+11(c) (c(c))
(147)
< E, [aa = cn + [[,, + cc)
(update rule of Algorithm I
(148)
< 2n (c)
(149)
Combining Eqs. (14).. (16) and [149) produces
7
E, 1241 - Z,] <
(1
-T(()))) Σ (b) + 2/ Σ Tc(c)
(150)
2
bEB
CEC
7 (1
11-
( (T) + (C)
(151)
2
'Specifically, v > & implies the inductive hypothesis that was used to prove Eq. 136 and dy can be replaced with e..
23

---

If (C) = 0 then the above is negative, so we may assume Ti (C) > 0. Since V/ > t, there is some
b E D, with (b) 2 U/ 2 nR so
Te (B) (C) 2 (bbb/ cxp(Ox(b))
(152)
(153)
ExEc exp(Or(c))
exp(U22
(definitions of B and C)) (154)
nexp(1|
exp(U2 - nt)/KK
(155)
(8RK/A)/K
(U2 n + log (ogg/8K//40 (156)
(156)
8R/A.
(157)
Also from have that EMEA- Oc(a) U1 at least one A" satisfies (a 2 U1/K.
Fixing such an a gives
(1 n. (f.))//.(C))
2 nt(a)/=e(( (C
(158)
2 exp(U1/H RR)KKK
(like Eq. [15
(159)
2 (8Rn/ A K)/K
(U1 2 KnR + K Klgg(KKK/A K()
(160)
-8R/A +1.
(161)
We will break into two cases, first assuming that Ty (.)) 1/2. In this case upper bound
Eq. [5T) by
74
n
2 (1 (B)
2 (C) v Ti (B) + (T,
(162)
4
S -2n 2n (C) )) + 27
(Eq. 157
(163)
0.
(164)
On the other hand, if TT. (4;)) > 1/2 then
1/2 < (B) (C)
(165)
1 (B) + A/8R)
(Eq. 157
(166)
2R
S (B).
(167)
4R + A/2
Starting once more from the right hand side of Eq.
111 we have
7 (1 ne (T. + 2n (C)
A
2
Te (T()))) + RT.
4R + A/2
(Fq. (167) (168)
A/2
< 22
(8R/A + (C) + 2n Rm,(C)
4R A/2
(Eq. [66 (169)
=0. In concert, Eqs. 164) and (170) together with Eq. 151 imply that E. (2+1 y S < v. Therefore (Z))z2 is a submartingale, and is clear from its definition that 2, is bounded below by 0 at all times. We can apply Lemma A.7 and conclude that (Zz)zz converges a.s. to random variable with B|[Z]] S co.
(170)
7 < 0 when
We will again break into two cases, first assuming that v = oc, i.e. the stopping time never stops. In this case lim, Ze lim, Eves, max 0), and this quantity will a.s. converge to a finite value; because each summand nonnegative, this implies that all b $ satisfy lim sup, (.(b) < co. From the assumption that Ve Φ lim, (r(c) -oo, L U, lim sup, (b) < op. By Proposition
have that, for all b 2 4.3 there a.s. exists a finite timestep such that EcEA. (a) C' C" maxcev; lim (c) C' + O' max 0, (c). as desired.
The other case that < oo; this implies either the event & fails to occur (since E implies Eq. 124 or vo E 4, (b) < Uz. On event E, for all b E 4-
C'O, +5 CU < Σ (a),
(0+C, C'U2+ + (171)
A
24

---

and setting : / gives the desired result. Therefore. regardless of whether or not v/ < oo, the only way we don't 't have the desired result is if & fails occur, which happens with probability at most e. Since e was arbitrary, it can be taken to O, and the desired result will hold a.s.
Having shown the above lemma, we are ready to establish that the parameters of suboptimal arms diverge to DC.
Proposition 4,4 (Negative Infinite Suboptimal Parameters). For every suboptimal arm b E [K] \ A", lim;-xo 0, ())
a.s.
Proof. Since 4, = A and UsE|m) 0. = [K]. the set of suboptimal arms UsE[n-1] D1 Thus we will
perform induction over E [n 1], proving that all 2 satisfy lim, 0,(b) -0 a.s. from the inductive hypothesis that
Ve E 27 c
lim 0e(c) 00 a.s.
(172)
Note that Eq. 172 is vacuously satisfied for i = Fix an arbitrary e (0, 1], and define
D = sup -I + 20 1 4K2 4n/12x/ log 22+ 4n #20
(173)
e/ K
noting that D < co. Let be the first timestep such that
(a) > (K + 1)D K log(K K + 4K/A) + K max (b),)
(174)
be o ++
G
and note that is stopping time. Also T < 00 a.s. by applying Lemma B.3 (which is applicable due to the inductive hypothesis in Eq. 172) with : (K + 1)D + K log( 4K/A) and C' := K.
now can apply freedman's 's lemma to both the suboptimal arm and optimal sum, and conclude that the suboptimal arm goes to -oo wp 1 - 5. since 5 was arbitrary the result becomes a.s, and the induction goes through meaning that the whole thing does.
Consider the collection of sequences {(x))s>> b 2,+1} defined by X; := (b) - (b)) and the sequence (Yr) defined by Y, : -. 0e(a)-0--1(0 (a). For each b E 2 (X!))>> satisfies the requirements of Freedman's Inequality (Lemma A.3) with B == n/: also, (Y:)s>r does with B R. Therefore can apply Freedman's 's Inequality with 5 == e/ K all of these sequences
simultaneously and take union bound to conclude that, with probability 1 e 4 7 + 1)/K I 1 1-E,
2 Ercket Vark 1
Σ 0.(a) - 0a(a) N
20
+ R2 +
Vark- (Y)) log
c/K
a
T<kSt
T<kEt
(175)
2 Ereket Vark [X
vb 2, 0,(6)) - 0,) 5 Σ
Ex-1 + 20
1 472
Var&- log
e/K
T<ckt
Tcctt
(176)
for all > Let E denote the event that both Eqs. (175) and 176) hold at all such We will argue that, on E,
0,(a)² > ((log(K + 4K/A) + max (+(b) D) 2 K (logg(K + 4K/A) max 0,(b))
bE0 ++
be 041
a
(177)
for 2 T by strong induction. Thus let 2 т. and suppose that Eq. 117 holds with l: in place of
I, for all T < k < I, noting that it holds for ls = 7 by the definition of Eqs. 84 and 91 together imply that
n A
Rn
E
M
E.
[Y).
(178)
A
25

---

for & > T, so the assumption that event & holds implies
Σ A
(c(a)= 2 Σ (r( D
(179)
"EA*
2 K (log( + 4K/A) max (((b) + D). bE
(180)
Now pick an arbitrary E $ Pi+1- Without loss of generality, say b $ where j [i]. For T S k <t the inductive hypothesis implies that there exists a AA' such that 0x(a) log(K 4K//A) (b). Thus
Th (m 2 TA (2)a/T((((T/))
(aE C 2) (181)
exp(Ox(a))
(182)
K exp(mmaxE47, (s(b))
exp(log(1 + (K/A))/K
(183)
2 2144R/A.
(184)
Defining the constant y
+ R), we have y S (A+ (
which implics 7/(11 7) - 1 48/44 TM (T) Therefore
Tx(2)) 2 1-7
7 2 (x(
(185)
+ *x(())) 2 (=x +))
Tx (
(186)
7 rb)) R 2 (4/2 rrb)+ R1 (T,)
(187)
+ (A
R(1 - TA (0,) nz (95) 2 (A/2+ - (2,))
(188)
+ ( - ( (1-ma TH (0)) + r())) + Row ($7)
(189)
Combining Eqs. 104) and 1189 produces
7
E 1 [x]] <
T (0) - xT()))
(190)
2
From Eg. 184) we have (a) 2 (T( [+11 2 T
( so 1 - Tx (T()) 2 1/2. Thus Eqs. 105
and (90) together provide
7/
E
[x]]
<
(b)
(191)
4
A
S
Vark [XX]
(192)
R2
Eqs. (176) and 192 imply
(b) (b) - (b) + (+) (b)))
(193)
< D + max (b),
(194)
6E
and multiplying both sides of Eq. 194) by K before adding K log(K + AK/A) implies the second inequality of Eq. (177) (since d P,u was arbitrary) This concludes the inductive argument over f > т. We have shown that, on E, Eq. (177) holds. In fact, on event E, we can also use
Eqs. 176 and (192) together with the fact that Et>1 Vart-1[X]]
(using Eq. (105) ) to
conclude that lim, (b) = -o for an arbitrary E P This finishes off the inductive argument over E [n 1].
The above results are all that is needed for the proof of Theorem 4.2
26

---

B.2 Non-stationary Convergence
Here show that, in general, the stochastic gradient bandit algorithm (Algorithm I only converges to "generalized one-hot policies", i.c. EuEA- T((a) = 1, and not "true one-hot policies", ie. Ea E A" (T)a) = Among the optimal arms, there will be permanent non non-stationary behavior.
Proposition 3.2 (Non-Stationary Convergence). Consider a K K-armed bandit with all arms being equally good, i.e. A = [K], and at least one arm has a nonzero probability of generating a nonzero reward. Running Algorithm with any dj > leads
lif (e(a) < 1 a.s.
(1)
for all E [K]. Therefore (Te)120 does not converge any one-hot policy.
Proof. We will first argue that (0z) does not converge to fixed vector. By way of contradiction, suppose lim, 0e(a) = E RK Let a E [K] be an arm such that P(r, + 0la, = a) O, which exists by assumption. Without loss of generality, there exist 8 0 such that P([re cla, a) > 6. Since 0, + 9,, we have that maX (b) (b)l - Also, convergence implies that lim E (0, 1), in particular there exists 3 E (0, 1) such that eventually me (a < B. Since selected i.o. and every time is selected [r++1] > with fixed probability 8 0, we have that
(0+1(a) - 0a(a)) 2 s7(1 =z(a))e
(195)
17(1 3)e
(196)
i.o. This constant lower bound on the step taken contradicts the assumption of convergence.
We will now argue that, for all R and [K], (a) < x occur i.o. or else (z(a) will converge. By conservation of mass this implies the desired result. Since the mean reward is the same across all arms, (l)(2)) is martingale. Given any (possibly random) time т, the stopped random process induced by running (0e(a) 0, (a))ezr until the time it hits the set [x 0, (a). -oo) is thus a martingale bounded below, and Doob's 's martingale convergence theorem implies it will converge. Either the value converges without hitting the set, in which case (a) converges, or else (a) dips below x i.o.
C Nonstationary Bandit Setting
Proposition C.1 (Infinite Optimal Parameters), If A" [K] then lim EoEr 0.(a) almost surely.
Proof. Fort 2 Xet E.EA (141(a)-6 (a). such that Ei=o X, = Encs (44(0))8o600 By the update rule of Algorithm note also that
= Σ (Iaa a) - Te(a))
(197)
27

---

The conditional expectation of X, given Fi can be lower bounded by
[x = Σ
Ee [[a xx]
EeE(K] Ma: a] = 1) (198)
aE(K]
Σ
Ea[l(as - adn(1 - ((()))) +
Σ
E1 = (T())m)
=
aEA"
bE[K](A
(Eq. 197 (199)
=n(1 - tT(("))
Σ
Be = aa]ra] - (A*)
[M = b]r
"EA'
DE[AT]AA
(TT is F. F--maauurable) (200)
=n(11- - -T((AA))
Σ
(a)))((aa- (A")
Σ (b)r(((b
"EAA
BE[KTTAA-
(E, [aa = |m]== = -))((((r(()) (201)
7111 2 n11 - Te(A"))
Σ ((a)(((a)- - A/3)- (A7)
Σ (r(b)rr(b)+ + A/3)
"EA"
BEIKILA
(Va E [K], Vt 2 T,
- r(a) S 4/3) (202)
- 2 n1(1 - ne(A-)) Σ m(()(r(44) - (A')
2
E (bb)r((AA) - 22/3)
"EAA
BE[KTEA
(r((a) =r(At), , r(b) S sr(At)- - A) (203)
-m (r)))) - 4/33)))-/3((41")))
(r(A")- - 22/33)
C CREA- (a) = (A(), Ebe(K)) (A- (x) =1 - TH (Ar)) (204)
- (0)(4"((1=<(A4")))
(205)
and the conditional variance can be upper bounded by
[arr[X,] S [x{[
(206)
= =Σn
E, [[a, = a|x
Eee[K] May = a) = 1) (207)
[E(K]
Σ
E. [l (1)7))-)(4))))))
E, [[a = b]( - -7Tee ()T )r:)
a
bE[KTTA
(Eq. (208)
S 1 - ग. (A'))
Σ
E, = a] + TT (A*)
E, [1, b]]
"EA'
( < R²²) (209)
= =1 - Te (1
Σ Te(a) + 1m 12
(b(
be bE A-
(E, = = ())= (210)
= =12 =R²2 (11 - =xA()))) Ne (A*) + TT - me(A")))
EOEA =((a) = Te(A"), EDE(KTVA- (b(b)= = =1- -(((((A)) (211)
= R2 nT (1 Te, (A*)).
(212)
Thus for all t. 2 J we have Var [ S P3RA--EE [, X < RR and X, is -eassurure.
Setting : R and c R2 A we need only to prove that Σiz, E, = oc, at which point we can apply the Freedman Divergence Trick (Lemma A.5) to conclude
lim Σ (a)1(a) - 0o(a)= = Σ 00 a.s.
(213)
127
+ lim Σ (:(a) = 00 a.s.
CoEs Bo(a) < oc) (214)
AEAA'
28

---

Thus in the remainder of the proof we turn our attention to showing Σ1z, E,[X,] = 0c. Applying
Eq. 205
and n//33 3 O, we need only show that
Σ (1(AA)(1- =x(A))) = 00.
(215)
Lemma 4.1 together with 0 o A + [K] implies that
Σ Ma E A
Σ 12T
Ma $ A-] = 00 a.s.
(216)
Since P(a; E F,) = (A') and P(a. & 111
the Extended Borel-Cantelli
Lemma (Lemma A.1 applied to Eq. (95) furnishes Σ129 (e(") - (1 (A')) xo a.s.
We now break into cases to show that Eq. (215) holds regardless of the behavior of TT (AA).
If n. (A*) 2 1/2 only finitely often then we can set u = max ft 2 0 (A(A') 2 1/2 for
Ne (Ar)
Σ (A')(1 T (AT))
=0.
(217)
2
t>a
Similarly, if (A*) < 1/2 only finitely often then u = max {t 2 0 : (T(AA) 1/2] gives us
Nx (A*)
Σ (m(4))1--m447)))
x.
(218)
2
We can narrow our focus to the case where He (AA") is both above and below 1/2 i.o. In particular, there must be infinitely many t 2 0 such that Te (AA) < 1/2 but To.4 (A*) 2 1/2, and for such è we have
Enes exp(O++1(a))
Tep (A*)
(Eq. 2 (219)
ECEA- exp(0x+1 + Dbe[K]VA- exp(Or+1(b))
The above equation is of the form 2/(x + y). where x == EneAr exp(Or+1(a)) and y EDEIKRA exp(O++1(b)) Since x/(x + y) is increasing in x and decreasing in y for x, y > 0, and ((t1(c) - (c(c)] I nR for all [K], can maximize the right hand side for the upper bound
ELEA exp(Or(a) + RR)
To (A') 5
(220)
E EaEA. exp(O:(a) + R) EbEIKRA exp(O.(b) R))
Also, (A*) < 1/2 yields EoEA. (x)().(a)) < ΣBELKTAA (b)) so
ENEA- (xp(Ox(a) + RR)
(221)
Eees- exp(Oc(a) + +R) EcE[KTAA- exp (b)) n2)
exp(1)) ECEA' exp(Or (a))
(222)
exp(nR) E exp(Or(a)) + exp(-nR) ESE:KTA exp(O((b))
exp(nR) EOEA. (x)()
(exp(nRt + (xxp(-nRt))
CEA (xp(O.(a))
EuEs. exp (a)) < E EDEIKRAA exp(O.(b)) (223)
exp(nR)
exp(2mR)
(224)
exp(y)t + exp(-1)R) exp(2n +
Connecting the above displays, there are infinitely many t 2 0 with n. (At) < 1/2 and Te. (A*) >
1/2, and for such we have - no (A*) > 1 ex) (2))2) (2x +1) = (exp(2n) + 11) 11
Therefore NT.4 (A1) Te._ (Ar)) > e2 + 2) i.o, establishing Eq. (215)
0
Proposition C.2 (Finite Suboptimal Parameters). For every suboptimal arm b E [K]
A",
lim (b) cx a.s.
Remark C.3. The proof remains virtually unchanged from the proof of Proposition and the necessary changes are identical to the ones made for the proof of Proposition C.I
Theorem C.4. In the non- non-stationary bandit setting described as above, Algorithm with any E (1) almost surely converges to playing optimal arms,
lim 8-000
Σ (a) a.s.
(225)
29

---

D Reinforcement Learning
Define the MDP M = (H, (ra (PP) p). Let Ne(s,a) == -iz 8, = a} be the total number of visitations of state-action pair (s,a) until episode t. We denote that p (sh+1 s' s'|sn = s) as the probability of visiting state s' in the horizon h + from the state in the horizon & during the episode t. First, we extend the bandit exploration lemma (Lemma 4.1 to obtain its counterpart in the RL setting.
Lemma D.1 (RL exploration (Lemma 5.1). Using the REINFORCE algorithm with any E (1) under the finite-horizon MDP M defined as above, for all h E H. for all reachable E Sh and for all a E As we have, almost surely, that every reachable state action pair will be visited i.o, i.e N (8, a) 00.
Proof. First, for all h E H. for a given reachable & E S₁ that is played infinite often, every action a A, will be played i.o. by the bandit exploration result (Lemma 4.T) In other words, for all h E H. for reachable state that is played i.o, we have, almost surely that,
(s) = 00
Σ (als) oo Va E A.
(226)
Next, for all h E H. we want to show that every reachable state E Sh will be visited i.o. by induction. Suppose for a given h E H. for some reachable E S₁, and there exists an action a E A, such that Ph+11 visited i.o. For the base case h = 0, for some reachable states 8 E So, i.e p(s) >> O we have,
s' sh. s, an a) > for some s' SK+1, if s is visited i.o, s is also
Σ p(s) 00
(227)
since p(s) is a constant for every episode. Therefore, every reachable state s E Sy is visited i.o. For the inductive case, if any reachable states S, is visited i.,, then any reachable states s' E S is also visited i.o. A state s' is reachable if there exists an action a E A, from a reachable state E SA such that P ( (s'ls, a) > O. Denote e == millses, minag Pa+i(s' (5'ls, a) be the minimum transition probability from the horizon h to h + among states and actions. For reachable s' from 8, we have.
Σ (s'ls) = Σ Σ 120
(228)
aEA.
Σ
Tt h
(als)
(229)
12
00
(by Eq. (226)
Therefore, i E S2 is reachable and visited i.o, then any reachable states s' E S from s will be visited i.o. Combined Eq. (26) and Eq. (228), for all E H. we have that any reachable state-action (s, a) E S₁ x An pairs will be visited i.o. we know that every state-action pair will be visited i.o. D
Next, we obtain the convergence of REINFORCE in the finite-horizon setting.
Theorem D.2 (RL convergence (Theorem 5.2 For the MDP defined as above, using the algorithm REINFORCE with constant learning rate 1j E (1), we have, almost surely. for all s E So. V (s) (i)(s) as co.
Proof. We denote 8 == min, ming [Q(s a) Qs, b) > 0 to be the minimum non-zero gap between Q-values. Denote Ai, {ala = arg max.cA, r(s, a)} is the set of optimal action at a given state s. We also denote C = max, max, mins(Q(s, a) - (s, b)). We want to prove by backward induction that for all reachable state 80 E So. Enc = (als)
as co. Suppose for all h' E (h..... H! 1}. for all reachable Sw. we have EueA; a. (als) 1 as l + co.
we want to prove that for all reachable E Sh-1, we have Ens Te (a|s) + 1 as + co. In
the base case h = H- 1, the REINFORCE update rule (Algorithm 2 is reduced to,
' (s. 0 a) + m[[[a=1 al m,
"| (als))r)
(230)
30

---

This is the bandit update rule (Algorithm{] 1 for given reachable state s E SH-1. By Theorem 4.2 for a given reachable state E Sh-1, using the stochastic gradient bandit algorithm with constant learning rate 7 E ( we will have, almost surely that Ea E.t, - (a + as -> oo By Lemma D.I. any reachable states & E St1-1 will be sampled i.o. Hence, using REINFORCE with 7 E ( that for all reachable s E Sh-1 that are played i.o, we have, almost surely, ( as t co.
EREAh Tr H- (a|s) + 1 ass xc, In other words, V =
For inductive case, suppose for all h' E (h...., H - 1}. for all reachable 8 E Sny, we have EMEA; Tt (als) + 1 as + oo, we want to prove that for all reachable s E Sn-1, we have EREAR ty (als) + last
By the induction hypothesis, for all h E H. for all reachable SE Sn (s) + (s) and 0% (s, + (s, a) for all a E Ag as - cc. First, we note that (8) - V/ (s) = Σ # (a' (d'ls)(max (s. a) (s,
(231)
Σ me (a'ls)(mmxx QN (s. a) (s, + (s, - (7
(232)
8
C2
We denote that The (t) = EA (d'ls). For the first term C₁, we have
C1 = Σ Te (a' (max (s, (%
(233)
aEA. Σ a (alls)(max (h, (')
(234)
aEA,
d'EAj
(t)(()
(235)
since the horizon H is fixed and I' S R for all h E H. then
max Qh (s, a) - (s, SC SC
(236)
aEA,
By the induction hypothesis, we have, for all h' E {h...., H 1}, we have that Th (t) + 0 as 1 1 0o.
For the second term C2, we have Q% (s, - (8, a') S Saw (t), where (e)(() - 0 as t + oc by induction hypothesis. Therefore,
(s) Vi (8) S Cm (1) + (x)
(237)
Denote (t) = Chw (t) + an (t) and en (t) + 0 as co. Hence, for sufficiently large timestep т, such that for all t 2 T. for all = h.... ....., H - 1, for all reachable s E Swy we have that
(*)
(238)
where 8 is the minimum possible gap Q-value defined as above. The existence of T is guaranteed since en (f) - 0 as é + oc. First, for a given reachable E Sn-1, such that for any actions a E A..
we have,
0 (s, = rh-1 a) Ep--Pa (s))
(239)
2 r a) + R (s)()') -
(240)
Qhh -E
(241)
Also, for any actions a E A,, we have
Qh (s, < (s, s (h, +e
(242)
By definition of 8, for a given reachable s E Sh-1, we know that Q7
(8, a) - Qi. 2 8 for
any a, b E A. such that a # b then we have
8
Qh a) (s,b) 2 5 2c 2 3
(243)
31

---

Note that 8 is a non-zero gap by definition. Note that the update rule of Algorithm 2
Ø-1
as) 0 (1{an-11 = -
+ -
m m (als))
Σ
TM
(244)
h'=h-1
is equivalent the update rule in the nonstationary bandit setting, by considering only the updates to the arms at state 8 and the full trajectory's 's rewards as the observed rewards.
Since by definition
E
rw 8, 8, - W
Σ
L The is an unbiased estimate of 1 (5h-11 up nonstationarity in म, which eventually diminishes below 8/3. Also, note that
H Σ
(5,
E
= 0, S R(H h) 1
(245)
h h'=h-1
since r(s,a) < E S. E A. Since the sample return Σm Th is a bounded, unbiased estimator of ( -1- and there is minimum gap of 6/3 between Q values among different actions within the same state, setting (Theorem C.4) to conclude that LeEA, (s) "e h-1 (als)
apply the convergence result from the nonstationary bandit 1 as t Do for all reachable s E Sn Therefore the induction hypothesis holds, and we conclude that, using REINFORCE with 7 ((1), EeEA; o/ (als) 1 as t for all S₁ (or ( Vo (s) as co for all E Sy).
E Convergence rate
To obtain the convergence rate of the REINFORCE algorithm (Algorithm 2 we first generalize the convergence rate result from the bandit setting with the uniqueness assumption to the one without Then, also obtain the convergence rate in the non-stationary bandit setting before showing the rate of the REINFORCE algorithm.
Theorem E.1. the bandit setting where multiple arms can have same reward, for a large enough T, for all T >> t, the average sub-optimality decreases at rate O logT) Formally, for constant c, we have
Σ (r(aa) (TO..)) 1 clog(T - T) T
(246)
(T T)
Proof. By Eq. 84). we have
E,10. (A*) -A ((()' nATO, ( To. (A*)) 20 0
(247)
By Theorem 4.2 we have lim; no, (A*)) a.s. Therefore, for large enough t, have
1 To, (A*) 2
(248)
By Lemma 4.1 we know that every action E [K] will be played i.o. In other words, for all E [K].
Σizo (1 xo. Therefore, we have
Σ (1 no. To, (A')) = ac 1=
(249)
Therefore, we have
80
E, ( 0+(A")] = 0a a.s
(250)
32

---

By Eq. 91. we have
Var, (4r,
- (A(Aa) S ( (1.
(251)
Since the conditional expecation and variance of the bound sequence (01+1 0. )24 are proportional, we can use the Lemma AA.5 to show that the expectation will dominate the variance eventually. Therefore, for all large enough t 2 т, for some constant C' > 0
(((A)
E (1 To, (A*))
(252)
A
6=T
is easy to see that sup, (.(a) < 00 for all a E [A] Therefore, for a large enough t 2 т, we have
0.(a) A (1(A)) -C Σ (1 To, (A*))
(253)
which implies that
Σ exp(O.(a) a
[A- [A- (1-0((A))) s -K--1-)) exp(pp Σ (1 no, (A*)))
1
(254)
Therefore, we have
1 - na, (A*) 5 - To. (At)
(255)
To, (At)
To, (a)
(256)
To. aE(K]iA
(A+)
exp(O:(a))
Σ
(257)
EOEAA. exp(O:(a'))
aE[k]] 1-
(a))
(Jensen's 's inequality) (258)
A+ exp( प (e(A+))
aE(K]i
$ -K-1At) exp( C Σ TO, (A")))
(Eq. 254
(259)
8=7
By Mei et al.
2024a
Lemma 15) with F. = Σ Tg. (A*)) > 0, xn+1 = E1=
To, (A))
0,0
C>> 0, (K |A 1) > 1, gives us for all T,
Σ ne, (4*)) - C log 7) exp (CM) +
1
π²²
(260)
12C
where M mB y log(C(K - -|A 1 ne, (A Finally, for all 2 and T T, we have
r(a") - (T),,))) = Σ
(a)(((((a)) r(a)) - 2R(1 No, (A*))
(261)
dEIKTIA'
Summing from T, we have
- Σ r((a)) (re)..)) <
1
2 log(C(T -T) + exp(CMM) + T2C
(262)
T
T--
Theorem E.2. In the non non-stationss seessttatonaryy bandit setting, for a large enough T, then for all T t, the average sub- sub-optimality decreases at rate O (oggT) Formally, for constant c, we have
T
(TO..)) x clog(T (T T)
r(a")
(263)
T B
T -
33

---

Proof. Repeating the same analysis with Eq. 205 Eq. (212). Theorem C.4
we have, for all f 2 T",
E0 - 10--0,(440 -0,
- C log(C(( 7) + exp(CM)) +
(264)
12C
==
where M max (B, è log(C(K 1Am))), No,,, (A*)}. Also, from the non-stationary bandit setting, there exists 7' such that for all & T',
(r(a) - (a)) S A
(265)
for all [K]. Therefore, for all 2 max (T 7") and T m have
r(a") ( r) s 2R(1 TT. (A*)
(266)
Summing from T = m-x to T, we have
1 T
2R( log(C(T - -T) + exp(CMM) 120
Σ
r(aa)= (TT) ((TE))(TT)))))
(267)
T
T-T
S=T
Theorem E.3. In the finite-horizon MDP setting, for large enough T, for all T > T, for all s E So- the average sub-optimality decreases at a rate O logTT Formally, for constant we have
T
T
Vo - (o))
clog T T
(268)
Proof. Repeating the same analysis, we have, for each h E {o,..., H - 13, for all s E S₁, for all t The
Σ (1 - mं (A)1s)) = T log(C(t - Tx) + exp(CM)) +
x²
(269)
12C
where Mj max [1Ax [ t log(C([AA,) - (A;1)), 1 no., (Agls)). Also, there exists T/ such
that for all / 2 T/e
A
(s, - Q7 (s,.)ll> -
(270)
3
for all a E A,. Therefore, for all horizon h E {o...., H 1}. for all t 2 max(Tn, and T > max(Th, 7/ we have
(h(s,a") Σ +1(cls) (s, S (Q(ssa") - Σ (Q73)))))))) aeA.
(271)
3
d.A.
Σ (fs - a)) +
(272)
rEA,
< 2( h) R(1 - (At]sss + A
(273)
3
which implies
1
Σ
T
(V
<
2R(H N) log(C(T Th) + exx((CM) + 120) 3
x² A (T Th)
T
T-
(274)
Since for all h E (O...., H - 1}, for all s E Sn, for all a E A,, lim, Q¹ (s, a) = (s, a), we can
take + O. Therefore.
2HR log(C(T To) exp(CMM) +
2²
T Σ (V) V0 (s)) <
T2C
(275)
T - To
(mmax(Foord)
34

---

10
Avolge Aroogge Subipimmsity (V5 V5100
30"4
10
10"4
Leaming rotes inl
Figure 5: Average last-iterate suboptimality gap of ChainMDP size 4
F
Additional experiments
Specifically, we measured the average suboptimality in the last episodes over 30 of the algorithm in longer ChainMDP, DeepSea environment and CartPole environment. For ChainMDP, we extended the lengths of the environment H {4, 5, 6) and measured the average suboptimality gap across 100 learning rates (from exp(-9) to exp(1)). For each length, we observed a clear bowl-shaped curve. As complexity (chain length) increased, the specific thresholds of the bowl shape varied slightly, but the optimal learning rate remained consistently around 17 = .95. Next, we gradually increase the complexity of our evaluation by testing the REINFORCE algorithm (Algorithm) 2 on the deep sea treasure environment. The agent operates in a square gridworld of a given depth d d= (5,6 6, 7)). starts the top left corner and its goal is reach the bottom right corner and receive reward of 1. The agent has two action 1 and 2. While taking action leads the agent downwards and receives no reward, taking the other leads the agent downwards and to the right and receives reward of 10.000000 00.001. Similar to the previous environment, for different depths, we measure the average suboptimality of the agent trained from 10 episodes over seeds using 100 different learning rates from exp(-9) to exp(7). We observed a similar "bowl" shape across the learning rates. However, the thresholds are different from the previous analysis. Specifically, the learning rate 7 10 has the lowest suboptimality. Finally, we evaluate the performance of the REINFORCE algorithm (Algorithm 2 in the Cartpole environment. Specifically, we measure the average return received by the agent from 10a episodes over 5 seeds using 1/ {10-3 10-0 11011110= 10-2 1}. Again, we observed similar "bowl" shape across learning rates. The learning rate r/ = 0.01 achieves the highest average return (approximately 150), while the average return of the others stay around 25. Overall, we consistently find a "bowl-shaped" relationship between the learning rate and performance, and the specific shape and optimal point of this bowl vary significantly with the environment' 's structure.
35

---

Avcroge autoptmnlty 04,
10"1
20T4
10
10
rates
Figure 6: Average last-iterate suboptimality gap of ChainMDP size 5
10
Aeongge mub.ttmayyyyyy WV 12691
Leaming rases lnt
Figure 7: Average last-iterate suboptimality gap of ChainMDP size 6
10
Merrag witopttaatt/oooo (916) VNON
10a2
19"2
28-1
107
10
107
Learning
Figure 8: Average last-iterate suboptimality gap of DeepSea depth
36

---

10"4
10
30-14
10
Learning
Figure 9: Average last-iterate suboptimality gap of DeepSea depth
Awooge www.pomaayyyyaiiooo... 1800
27
10
10
10
20
10
10'
10'
Figure 10: Average last-iterate suboptimality gap of DeepSea depth
IRe lwc5 IR-1e-04
200
UP-1e100
Aporage Splende tetum
ااا
Figure 11: Average suboptimality gap of Cart
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction are shown in Lemma Theorem 4.2, and Theorem 5.2
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In the conclusion (Section 6 we point out that REINFORCE exhibits high variance when using excessively large learning rates and highlight choosing an optimal learning rate schedule potential future work. The specific technical limitations of all results are apparent from the formal descriptions of the algorithms, settings, and results. In particular we state all assumptions explicitly in the settings, including that the state and action sets are finite and the rewards are bounded.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specificattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
38

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We numbered each theorem, formula, and proof in the paper: all results proved formally in the supplemental material. We have provided intuitive proof sketches where possible.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We described the experiments in detail in Section 5.3
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
39

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Our experiments are simple enough that they can be recreated easily using the information provided in Section 5.5 We studying classic algorithms and use only simulated data, which should be easily reproducible from the detailed descriptions.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips.cc/put wwtpcccccppccccceee casollcc/giieee /ttee/ggguddeeeeeeuSuuubbibeeee htt///ooeSubmiss... comommsssinn ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We do specify the list of values for each hyperparameter (learning rate, seed, horizon, training episodes).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All figure contain error bars except for figures that are explicitly stated to plot individual runs for demonstrative purposes.
Guidelines:
40

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: The environments (ChainMDP and TreeMDP) are simple and the experiments are small enough to run on any modern machine (e.g. an Intel Macbook 2019).
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We make sure to preserve anonymity, no new datasets are introduced, and we do not conduct research on human subjects.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
41

---

The focus on the paper is on theoretical guarantees of convergence for classic algorithms, and empirical validation of the proofs. There are no specific societal impact concerns beyond those of the field of RI. whole.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g.. pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: The work does not involve releasing high-risk artifacts such as pretrained models, large-scale datasets, generative tools that could be misused.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
We do use any existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
42

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperssi thoode com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not introduce new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our research does not require crowdsourcing or involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our research does require crowdsourcing involve human subjects.
Guidelines:
43

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The core method development in this research does involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
44


Reviews:
[{"review_id": "yV1F5glI35", "reviewer": "Reviewer_2sF6", "summary": "This paper presents a novel theoretical analysis of the stochastic policy gradient method with a constant learning rate. The authors offer improved convergence guarantees in the presence of reward ties by extending the existing bandit exploration lemma. Furthermore, they generalize their results to the RL setting. Preliminary experimental results are also provided.", "questions": "1. Is it possible to extend the analysis to the case of inexact gradient updates for the REINFORCE algorithm? This could provide practical guidance for choosing an appropriate batch size.\n\n2. The experimental results show that a large learning rate ( $\\eta=2$) leads to non-convergence, yet Theorem 4.2 does not specify a clear upper bound on $\\eta$. Could the authors provide an explanation for this apparent discrepancy?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. This paper extends the results of the previous work by Mai et al. (2024), removing the assumption that there is a unique optimal action. Technically, the authors strengthen the exploration property from \"at least two actions are selected infinitely often\" to \"all actions are selected infinitely often.\" This refinement leads to an improved convergence result, showing that the SPG method ultimately assigns all probability mass to the set of optimal actions. The technical contribution is solid.\n\n2. This paper also extends the results to the RL setting, which was not addressed in previous work. Although this extension may not be highly novel, it is important since the RL setting and the REINFORCE algorithm are more practical for real-world applications.\n\n3. The paper is clearly written and easy to follow. The proof sketches effectively convey the high-level ideas, and the detailed proofs are rigorous.\n\nWeaknesses:\n\n1. The absence of convergence rate analysis is, in my view, a key weakness of this work. The paper provides only a convergence guarantee for a classical RL algorithm, which is not that useful in practice, as it offers no guidance for practitioners on how to select critical hyperparameters such as the learning rate or batch size.\n\n2. The experiments are conducted only on a simple MDP. Including experiments on more diverse simulated environments and tasks would significantly strengthen the experimental section of the paper.\n\n\n.", "was_revised": true, "final_justification": "I appreciate the author's rebuttal. I will keep my score.", "rebuttal": "We thank the reviewer for appreciating our contribution, and for their careful reading and valuable feedback. The main concerns are addressed as follows.\n\n# Weaknesses\n\n> 1. The absence of convergence rate analysis is, in my view, a key weakness of this work. The paper provides only a convergence guarantee for a classical RL algorithm, which is not that useful in practice, as it offers no guidance for practitioners on how to select critical hyperparameters such as the learning rate or batch size.\n\nWe agree with the reviewer that a convergence rate is of great interest for improving the practicality of our analysis. To this end we have extended the $O(\\log(T)/T)$ convergence rate of Mei et al. 2024a [1] to our bandit setting (without any assumptions about ties in the mean rewards of arms). This is the only known rate in the literature that is in a setting comparable to ours. We then establish the *exact same* asymptotic convergence rate in the RL setting. Please find a high level description of the proofs in the \"Convergence Rate\" section of the rebuttal to Reviewer 2xdN below (since there is no enough space in this rebuttal section due to character limit). We will include these rates and proofs in updated versions of the manuscript.\n\nAs for the guidance our theory provides practitioners, there are takeaways regarding both the learning rate and the batch size. Existing theory provides guarantees for learning rates that are either impractically small or decreasing towards 0 on specific schedules; our work can be interpreted by practitioners as a license to tune a fixed learning rate without worrying about meeting scheduling conditions or being under a threshold. Similarly, our work (and other theoretical works in the stochastic gradient settings) do not rely on perfectly accurate estimates of the gradients. In other words, our results hold for a batch size of one or more&mdash;as opposed to the exact gradient setting, which is analogous to (but even stricter than) requiring a large batch for a highly accurate estimate of the gradient.\n\n> 2. The experiments are conducted only on a simple MDP. Including experiments on more diverse simulated environments and tasks would significantly strengthen the experimental section of the paper.\n\nWhile our contributions in this paper are primarily theoretical, following the reviewer's suggestions, we have extended our experiments as described in the \"New Experiments\" section below. Unfortunately it is not possible to attach figures, but we will add visualizations and detailed explanations of these experiments to subsequent versions.\n\n# Questions\n\n> 1. Is it possible to extend the analysis to the case of inexact gradient updates for the REINFORCE algorithm? This could provide practical guidance for choosing an appropriate batch size.\n\nWe are unclear as to the precise meaning of this question, and will try to answer it with three interpretations. **First**, if by inexact gradients the reviewer means that the learner only receives noisy data from the environment, and has to estimate the gradients from these data, then our analysis already accounts for this; we are effectively studying the setting where the batch size is 1, i.e. the learner must act from a single observation (reward in bandits or trajectory in RL). Thus our analysis will work for any batch size. \n\n**Second**, if the reviewer is referring to biased gradient observations, then we would argue that this issue is not present in our settings: since the computation of unbiased gradients is trivial from single observations of the rewards, analysis of biased gradient computations is unnecessary.\n\n**Third**, if inexact gradient updates are from other structures, such as function approximations, our speculation is that combining our results with recent work on function approximations, such as [2] would be able to extend to that case of inexact gradient updates for the REINFORCE algorithm. However, [2] is restricted to the bandit setting, and they rely on Assumption 2.1. This mean non-trivial efforts are needed to extend our analysis to function approximation settings.\n\n> 2. The experimental results show that a large learning rate $(\\eta=2)$ leads to non-convergence, yet Theorem 4.2 does not specify a clear upper bound on $\\eta$. Could the authors provide an explanation for this apparent discrepancy?\n\nThis seeming discrepancy highlights the important separation between finite time vs. asymptotic results. For excessively large learning rates there might be an arbitrarily large period before convergence (and even before the converge rate) kicks in. We think that the figure showing large learning rates failing to converge for an extended period is important to highlight the caveat of taking $\\lim\\_{t\\to\\infty}$. However, no finite-time experiment could actually conflict with our asymptotic convergence result.\n\n# New Experiments\nIn order to strengthen the experimental section of our paper, we ran new experiments to validate our findings in a more diverse set of environments. Specifically, we have conducted new experiments with two primary questions in mind:\n1. What is the relationship between the learner's convergence rate (as measured by finite-time performance, i.e. empirical suboptimality or return averaged across trials) and the magnitude of the constant learning rate? \n2. Does this relationship depend on the complexity of the environment (e.g., number of states, exploration requirement, chain length) or vary significantly across different types of environments?\n\nOur experiments across three distinct groups of environments give preliminary empirical answers to these questions. We consistently find a \"bowl-shaped\" relationship between the learning rate and performance, i.e. there is a unique minimum. The specific shape of this bowl and the minimum (the optimal value of $\\eta$ for the time ranges studied) vary significantly with the environment's structure, across many orders of magnitude. Since we cannot include the visualizations in the rebuttal, we provide a summary of our findings, which will be added in full (including plots) to the revised manuscript.\n### 1. Chain MDPs (Extended)\n- **Method:** We extended our analysis to Chain MDPs of lengths $H=\\{4, 5, 6\\}$, measuring the *average suboptimality* of an agent trained for $10^6$ episodes over $30$ seeds across $100$ learning rates (from $10^{-9}$ to $2$).\n- **Result:** For each length, we observed a clear bowl-shaped curve. As complexity (chain length) increased, the specific thresholds of the bowl shape varied slightly, but the optimal learning rate remained consistently around $\\eta ≈ 0.95$. We were surprised that the added length had such a muted effect, while switching the environment completely changed the optimal learning rate. We hypothesis that the size of the best learning rate (at a given budget of training timesteps) may be sensitive to the amount of exploration required to learn the environment's dymanics.\n### 2. Deep Sea Environment\n- **Method:** To evaluate a tabular MDP with sparse and deceptive rewards, we tested on the Deep Sea environment for depths $d=\\{5, 6, 7\\}$, measuring the average suboptimality of an agent trained for $10^6$ episodes over 5 seeds with $\\eta =\\{10^{-8}, 10^{-5}, 10^{-3}, 0.1 , 0.5, 1, 2, 5, 10, 50, 100\\}$.\n- **Result:** The bowl-shaped phenomenon was again present, but the scale of the bowl was dramatically different. The optimal learning rate shifted significantly to $\\eta = 10$, demonstrating that the pattern varies substantially across different environment types.\n### 3. CartPole Environment\n- **Method:** To evaluate a classic control task, we benchmarked on CartPole, which has a continuous observation space that we discretized. We highlight that this environment violates the assumption of previous work that optimal actions are unique: when the pole is nearly upright there are a variety of optimal policies which will prevent it from following down.\nWe measured the *average return* of an agent trained from $10^5$ episodes over 5 seeds with $\\eta = \\{10^{-5}, 10^{-4}, 10^{-2}, 1\\}$.\n- **Result:** The results again showed a clear bowl shape. The best average return was achieved at $\\eta = 0.01$, a value orders of magnitude different from the optimal rates in the other environments.\n### Conclusions\nIn summary, our experiments lead to two preliminary conclusions about setting the learning rate in different environments.\n- First, there is indeed a consistent *bowl-shaped pattern* relating the constant learning rate to final performance across all tested environments, meaning that most problems have best constant learning rate ranges (too large or too small learning rates wouldn't perform well as is already observed in the simple simulations in the paper).\n- Second, the specific characteristics of this bowl—including the location of the optimal learning rate—*change with the environment's complexity and vary significantly across different environments*.\n\nHowever, we have to re-emphasize that these finite-time experiments do not contradict our asymptotic theory: we know that if the time axis was extended far enough, in the limit all of these fixed learning rates would achieve optimal performance.\n\n[1] J. Mei, B. Dai, A. Agarwal, S. Vaswani, A. Raj, Cs. Szepesvári, and D. Schuurmans. Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates, 2024a.\n\n[2] M. Q. Lin, J. Mei, M. Aghaei, M. Lu, B. Dai, A. Agarwal, D. Schuurmans, Cs. Szepesvári, and S. Vaswani. Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation, 2025."}, {"review_id": "967lyTu7jS", "reviewer": "Reviewer_zR1q", "summary": "This paper studies REINFORCE stochastic policy gradient (SPG) method and proves that it converges to globally optimal policies in both bandit and finite-horizon MDP settings without the assumption of unique mean reward values.", "questions": "1. Given that this work involves a re-analysis of existing algorithms, what key technical novelties have led to the improvements on convergence guarantees and the extension to finite-horizon MDPs?\n2. Is it possible to establish similar results in infinite horizon MDPs or even with linear function approximation?", "limitations": "From the experiments, an extremely large learning rate leads to significant training variance, while a small learning rate causes slow training progress. Notably, this work lacks theoretical analysis on how learning rates influence the convergence rate of algorithms, which undermines the practical significance of the theoretical findings in this work.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\nThis work eliminates the assumption of unique mean reward values, which is common in bandit setting and provides convergence guarantees for REINFORCE stochastic policy gradient (SPG) method. The results in this work also demonstrate that the online SPG method samples all actions infinitely often during exploration-exploitation, which contradicts the conjecture in [1].\n\n**Weaknesses:**\n\nEstablishing a convergence rate theorem for different learning rates would significantly enhance the practical utility of this work. While the finding that REINFORCE SPG algorithms converge under any constant learning rate is theoretically valuable, its immediate practical significance remains limited without convergence rate guarantees. It would be valuable to explore whether novel learning rate designs could theoretically achieve improved convergence rates compared to [1].\n\nAdditionally, expanding experiments to larger-scale MDPs could further demonstrate how learning rates affect convergence speed, given that existing research is limited to a single MDP case.\n\n[1] J. Mei, Z. Zhong, B. Dai, A. Agarwal, C. Szepesvari, and D. Schuurmans. Stochastic gradient succeeds for bandits, 2024b. URL https://arxiv.org/abs/2402.17235.", "was_revised": true, "final_justification": "The rebuttal provides convergence rate guarantees and additional experimental results, which address my concerns and strengthen the original findings. I have therefore decided to raise my score.", "rebuttal": "We thank the reviewer for their careful reading and valuable feedback. The main concerns are addressed as follows, and hopefully the reviewer would reconsider the rating once the issue is clarified.\n\n# Weaknesses\n\n> 1. Establishing a convergence rate theorem for different learning rates would significantly enhance the practical utility of this work. While the finding that REINFORCE SPG algorithms converge under any constant learning rate is theoretically valuable, its immediate practical significance remains limited without convergence rate guarantees. It would be valuable to explore whether novel learning rate designs could theoretically achieve improved convergence rates compared to [1].\n\nA key contribution of our work, and a source of practical relevance is **simplicity**. While complicated learning rate designs can be powerful, they typically introduce additional hyperparameters, increasing the computational cost and human effort of implementation. Our analysis focuses on the fundamental constant step size setting and proves that this is sufficient for global convergence. One can begin experimenting without using a tapering learning rate or estimating a tiny problem-dependent constant, knowing that their algorithm is fundamentally sound. Specifically, in the chain MDP of length 4, our theory validates using a step size like $10^{−3}$—a choice that our experiments show accelerates convergence significantly compared to $10^{-5}$, which is suggested by prior theory [2, 3]. In summary, we show that practitioners can rely on a simpler, easier-to-tune optimizer and still be backed by a strong theoretical guarantee.\n\nThat being said, we agree with the reviewer that a convergence rate is of great interest for improving the practicality of our analysis. To this end we have extended the $O(\\log(T)/T)$ convergence rate of Mei et al. 2024a [1] to our bandit setting (without any assumptions about ties in the mean rewards of arms).  We then establish the *exact same* asymptotic convergence rate in the RL setting. Please find a high level description of the proofs in the \"Convergence Rate\" section of the rebuttal to Reviewer 2xdN below (due to the limit of characters in this rebuttal section). We will include these rates and proofs in subsequent versions of the manuscript. We hope that these rates significantly improve the impact of our work as the reviewer suggested.\n\nIt is worthing noting that Mei et al. 2024a [1] have the only rate in the literature that is in a setting comparable to ours. We highlight that the rate of Mei et al. 2024b [2] is only available for impractically small learning rates (and also requires no ties in the true mean reward, prohibiting extensions to RL). The technical details of the $O(1/T)$ rate of Mei et al. 2024b [2] depend heavily on the miniscule learning rate, and are thus completely inapplicable to the large $\\eta$ regime that we study. \n\nWe thank the reviewer for pointing that a fine grained understanding of learning rate designs and their interaction with convergence rates would be incredibly valuable. This is a very interesting research program. Our preliminary attempts show some evidences that results in this direction will be problem dependent. For instance, in a trivial bandit problem with two arms, one always returning positive rewards and the other negative rewards, increasing the learning rate can only speed up convergence (since the optimal action will always increase its parameter while the sub-optimal action always decrease its parameter). On the other hand, in a more difficult problem instance, there is empirical evidence that large learning rates cause excessive variance, such as Fig 3.b in the paper.\n\n> 2. Additionally, expanding experiments to larger-scale MDPs could further demonstrate how learning rates affect convergence speed, given that existing research is limited to a single MDP case.\n\nWhile our contributions in this paper are primarily theoretical, as several reviewers suggested, we extend our experiments as described in the \"New Experiments\" section of the rebuttal to Reviewer 2sF6 (due to character limit). We have also summarized the results and conclusions in that section. Unfortunately it is not possible to attach figures, but we will visualize and explain in detail these experiments in subsequent versions.\n\n# Questions\n\n> 1. Given that this work involves a re-analysis of existing algorithms, what key technical novelties have led to the improvements on convergence guarantees and the extension to finite-horizon MDPs?\n\nWhen there is no isolated stationary points (w/o Assumption 2.1), our analysis is still able to argue for convergence (without relying on convergence toward stationary points). To achieve this, the following novelties are needed.\n\n### Lemma 3.1 for exploration\nPrevious work in the bandit setting [1] relied on the result that at least two actions are sampled infinitely often, and showed that the optimal action was one of the infinitely sampled ones. From there, the assumption of unique mean rewards was necessary to show that \"progress\" dominated \"variance\" in the updates. We significantly strengthened the exploration guarantee with a novel proof by contradiction, showing that *every action* is sampled infinitely often. This on its own could be used to simplify the proofs for previous results, but we combine it with the other technical contributions to remove Assumption 2.1:\n\n### Removing Assumption 2.1\n\nA significant limitation in prior analyses is the reliance on Assumption 2.1. This is a strong condition, as in the RL setting it essentially requires the existence of a single, uniquely optimal trajectory. When this assumption is violated—for instance in any MDP where multiple actions at a state have the same $Q$-value—the analytical framework of previous work is no longer applicable (e.g. see Eq. 114, Theorem 2 of Mei et al. 2024a [1]). To overcome this, we have to show that $\\sum\\_{a\\in\\mathcal A^\\*} \\theta\\_t(a) \\to\\infty$ as $t\\to\\infty$. This causes a surprising amount of difficulty: while showing that the sum of optimal parameters diverges to $\\infty$ is relatively straightforward, showing that the sum of suboptimal parameters diverges to $-\\infty$ is not enough for convergence. The pathological case where at least one $a \\in \\mathcal{A}^\\*$ has $\\lim\\_t\\theta\\_t(a) = \\infty$ but also some $b \\notin \\mathcal{A}\\^*$ satisfies $\\lim\\_t\\theta\\_t(b) = \\infty$ must be ruled out by arguing per-action for suboptimal actions. This pathology could induce nonconvergence if $\\theta\\_t(b)$ grows at an asymptotically faster rate! Arguing per-action in the presence of ties faces a technical hurdle: at a given timestep, if there are two or more equally good (suboptimal) arms and one is very likely to be selected, the expected update of any of them approaches 0. Thus the noise dominates. Handling this issue requires repeated and subtle use of concentration inequalities, and is the most involved proof in our work.\n\n### Characterizing Convergence with the Set of Optimal Policies\n\nBy removing the uniqueness assumption, we can provide a more precise characterization of the algorithm's limiting behavior. Our results show that the learned policy $\\pi\\_t$​ converges to a \"generalized\" one-hot distribution that concentrates its probability mass on the **set** of optimal actions, $\\mathcal{A}^\\*$. Specifically, we prove that $\\lim\\_t\\sum\\_{a\\in\\mathcal{A}^\\*} \\pi\\_{\\theta\\_t}(a) = 1$, but in general $\\lim\\inf\\_t\\theta\\_t(a) \\ne \\infty$ for all $a\\in\\mathcal A^\\*$. This result provides a more nuanced understanding of how policy gradient methods behave when multiple optimal policies exist. We show that true one-hot convergence does not always hold when there are multiple optimal actions (in Proposition 2.2), contradicting a conjecture made in the literature [1]. This observation shows why prior proof techniques [1,2], which are only suitable for establishing one-hot convergence, cannot be easily extended to handle ties in the mean reward.\n\n> 2. Is it possible to establish similar results in infinite horizon MDPs or even with linear function approximation?\n\nThank you for asking this interesting question! Our speculation is that it will be possible to establish similar results in an infinite horizon setting. The work by Zhang et al. [4] provides a promising starting point; they designed an algorithm using a randomized horizon to achieve unbiased gradient estimation. However, their analysis only guarantees convergence to a stationary point, not necessarily an optimal policy. They also require a decreasing learning rate which approaches 0 at a controlled rate. An interesting avenue for future work would be to build upon these ideas to establish the stronger global convergence guarantees that our paper provides for the finite-horizon case.\n\nRecent progress [5] shows the convergence of stochastic policy gradient with linear function approximation. However, the analysis is restricted to the bandit setting, and they rely on Assumption 2.1. Generalizing the findings to MDPs represents a non-trivial challenge that we are excited to potentially explore in the future.\n\n[1] J. Mei, B. Dai, A. Agarwal, S. Vaswani, A. Raj, Cs. Szepesvári, and D. Schuurmans. Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates, 2024a.\n\n[2] J. Mei, Z. Zhong, B. Dai, A. Agarwal, Cs. Szepesvári, and D. Schuurmans. Stochastic gradient succeeds for bandits, 2024b.\n\n[3] S. Klein, S. Weissmann, and L. Döring. Beyond stationarity: Convergence analysis of stochastic softmax policy gradient methods, 2023.\n\n[4] K. Zhang, A. Koppel, H. Zhu, and T. Basar. Global convergence of policy gradient methods to (almost) locally optimal policies, 2020.\n\n[5] M. Q. Lin, J. Mei, M. Aghaei, M. Lu, B. Dai, A. Agarwal, D. Schuurmans, Cs. Szepesvári, and S. Vaswani. Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation, 2025."}, {"review_id": "lg1BDDRFpD", "reviewer": "Reviewer_2xdN", "summary": "The main contribution of this paper is to show that the REINFORCE algorithm converges without any assumptions. The novelty mostly lies in the case where the MDP has more than two optimal policies. They developed a new type of analysis method, basically by showing that each action must be taken infinite times, to show that the REINFORCE algorithm converges asymptotically.", "questions": "I have the following questions regarding this paper:\n\n1. This paper only proved convergence asymptotically, without providing the convergence rate. Is it possible to give a convergence rate guarantee for REINFORCE algorithm?\n2. The numerical experiments showed that the performance of the REINFORCE algorithm deteriorate whenever the learning rate is too large or too small. Is there some suggestions on how to choose the optimal learning rate, either from theoretical or practical perspective?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n1. This paper is well-written. The proofs are correct.\n2. The results are very clean. They proved the convergence of the REINFORCE algorithm without any assumption and with any learning rate.\n\nWeakness:\n1. This paper only proves the convergence of the REINFORCE algorithm, they did not provide any convergence rate guarantee.\n2. The numerical experiments are only based on examples constructed artificially by the authors. No experiment on real data or common RL tasks is conducted.", "was_revised": true, "final_justification": "This paper presents good results. However, due to absence of the convergence rate analysis, I think that this paper still has room for improvement. Hence I will maintain the score of this paper as weak acceptance.", "rebuttal": "We thank the reviewer for appreciating our contributions and their careful reading and valuable feedback. We address the main concerns as follows.\n\n# Weaknesses\n> 1. This paper only proves the convergence of the REINFORCE algorithm, they did not provide any convergence rate guarantee.\n\nWe agree with the reviewer that a convergence rate is of great interest for improving the practicality of our analysis. To this end we have extended the $O(\\log(T)/T)$ convergence rate of Mei et al. 2024a [1] to our bandit setting (without any assumptions about ties in the mean rewards of arms). This is the only known rate in the literature that is in a setting comparable to ours. We then establish the *exact same* asymptotic convergence rate in the RL setting.\n\nIt remains an open question to see if this rate can be improved or extended to a nonasymptotic convergence rate; while there is still interesting work to be done in this direction, we believe that the inclusion of this rate increases the utility of our results significantly. Please find a high level description of the proof of the rates below (in the \"Convergence Rate\" section). It is&mdash;perhaps surprisingly&mdash;a much simpler argument compared to the proof of convergence. We will include these rates and proofs in an updated version of the manuscript.\n\n> 2. The numerical experiments are only based on examples constructed artificially by the authors. No experiment on real data or common RL tasks is conducted.\n\nWhile we believe that the major contributions of the paper are theoretical, and there is a large literature of empirical work (e.g. Duan et al. 2016 [2]) studying the behavior of policy gradient methods like REINFORCE, following the reviewer's suggestion, we have extended the experiments to include standard MDPs beyond those in the initial submission, such as gridworld and classical control tasks. While we are unfortunately not able to attach figures, these new experiments and their results are summarised in the \"New Experiments\" section of the rebuttal to Reviewer 2sF6 above (due to character limit of each rebuttal section). We will add visualizations and detailed descriptions of the experiments to a future version of the manuscript. We hope these extended experimental results are satisfactory.\n\n# Questions\n\n> 1. This paper only proved convergence asymptotically, without providing the convergence rate. Is it possible to give a convergence rate guarantee for REINFORCE algorithm?\n\nYes, please see the \"Convergence Rate\" section below.\n\n> 2. The numerical experiments showed that the performance of the REINFORCE algorithm deteriorate whenever the learning rate is too large or too small. Is there some suggestions on how to choose the optimal learning rate, either from theoretical or practical perspective?\n\nAt a first approximation, we believe the takeaway from our experiments is that small learning rates tend to converge with relatively stable progress, but simply adjust the weights too slowly. On the other hand, large learning rates are severely effected by noise in the reward signal, which causes them to overcommit to suboptimal actions. The process of unlearning these overcommitments is then very slow, because the real optimal actions are seldom sampled. Thus the optimal learning rate for a given time horizon seems to be related to the (problem dependent) optimal balance between exploration and exploitation. For more discussion see the \"New Experiments\" section mentioned above.\n\nWe view the message of our convergence results as that practitioners are doing something valid when they tune a constant sized learning rate to get the best performance. Previous theoretical guarantees tell the story that the only constant learning rates which can be trusted to converge in the limit are impractically small. Furthermore, our results free practitioners from the concern that they might need complicated schedules or decaying learning rates to ensure the soundness of their algorithm.\n\n# Convergence Rate\nIn bandits, we show that the average suboptimality converges to $0$ at an asymptotic rate of $O(\\log(T)/T)$, matching Theorem 3 of Mei et al. 2024a [1], which is the only known convergence rate for the stochastic gradient setting with large learning rates. As with the rest of our results, we achieve this rate without assuming that there are no ties between the expected rewards of arms. We also extend the rate to the MDP setting, and show that REINFORCE achieves exactly the same guarantee. \n\nBelow we sketch out the proof modifications necessary to extend Theorem 3 of Mei et al. 2024a [1] to our settings, which are fairly straightforward given our convergence result. We will freely use notation and reference lines from the submitted manuscript, including the appendices from the supplementary material.\n\n### Bandit Convergence Rate\n\nWe prove that, when running Algorithm 1 in the bandit setting, there exists a constant $C > 0$ such that\n\n\\begin{align}\n\\exists\\tau>0\\ :\\ \\forall T>\\tau\\ :\\ \\frac{\\sum_{t=\\tau}^T r(\\mathcal{A}^*) - \\pi_{\\theta_t}^\\top r}{T-\\tau} \\le \\frac{C\\log(T-\\tau)}{T-\\tau}\\ .\n\\end{align}\n\nWe begin by controlling the \"progress\" of the sum of the optimal parameters, $\\mathbb{E}_t[\\sum\\_{a\\in \\mathcal{A}^\\*}\\theta\\_{t+1}(a) - \\theta_t(a)]$.\nAs shown in the proof of Proposition B.3, and in particular Eq. (56), this quantity is lower bounded by $\\eta\\Delta\\pi\\_{\\theta\\_t}(\\mathcal{A}^\\*) (1 - \\pi\\_{\\theta_t}(\\mathcal{A}^\\*))$. Also, by Theorem 3.2, we have $\\lim\\_t\\pi\\_{\\theta\\_t}(\\mathcal{A}^\\*) = 1$ a.s, so we can select $\\tau$ such that $\\forall t \\ge \\tau\\ :\\ \\pi\\_{\\theta\\_t}(\\mathcal{A}^\\*) \\ge 1/2$. Since $\\mathcal{A}^\\*\\ne[K]$, Lemma 3.1 implies that an arm (every arm) in $[K]\\setminus\\mathcal{A}^\\*$ is played i.o, and the extended Borel-Cantelli Lemma gives us that $\\sum\\_{t\\ge0}(1 - \\pi\\_{\\theta\\_t}(\\mathcal{A}^\\*)) = \\infty$. Therefore\n\\begin{align}\n\\sum\\_{t\\ge0}\\mathbb{E}\\_t\\big[\\sum\\_{a\\in \\mathcal{A}^\\*}\\theta\\_{t+1}(a) - \\theta\\_t(a)\\big] = \\infty \\text{ a.s.}\n\\end{align}\nWe can also control the variance using Eq. (63):  Var$\\_t[\\sum\\_{a\\in \\mathcal{A}^\\*}\\theta\\_{t+1}(a) - \\theta_t(a)] \\le \\eta^2R^2\\pi\\_{\\theta\\_t}(\\mathcal{A}^\\*) (1 - \\pi\\_{\\theta_t}(\\mathcal{A}^\\*))$. Therefore the conditional variances and expectations of the sequence of bounded random variables $(\\sum\\_{a\\in \\mathcal{A}^\\*}\\theta\\_{t+1}(a) - \\theta_t(a))\\_{t\\ge0}$ are proportional, and since the conditional expectations are not summable we can apply the Freedman Divergence Trick (Lemma A.4). In fact, to extract the convergence rate we will need to use Eq. (21) from the proof of Lemma A.4, which tells us that, for arbitrary $\\delta > 0$, $\\sum\\_{a\\in\\mathcal{A}^\\*}\\theta\\_t(a)$ eventually grows at a rate of $\\Omega(\\sum\\_{s=0}^t 1 - \\pi\\_s(\\mathcal{A}^\\*))$ with probability $1 - \\delta$. Taking $\\delta \\to 0$, as $\\delta$ does not appear in the event, makes this guarantee almost sure. \n\nSince we have shown in Proposition 3.4 that suboptimal arms have their parameters diverge to $-\\infty$, we have the same $\\Omega$ growth rate for $\\sum\\_{a\\in\\mathcal{A}^\\*}\\theta\\_t(a) - \\theta\\_t(b)$ for any arm $b \\in [K] \\setminus \\mathcal{A}^\\*$. At this point we can use Lemma 15 of Mei et al. [1], replacing $\\pi\\_{\\theta\\_t}(a^\\*)$ with $\\pi\\_{\\theta\\_t}(\\mathcal{A}^\\*)$, and then convert the result to a bound on the suboptimality gap. **Note** that this is where the difference between our result and the statement of Theorem 3 by Mei et al. [1] differ slightly: our result is mildly stronger by replacing $T$ with $T - \\tau$ in two places; this does not result from novel analysis, but is a natural consequence of the arguments (in particular, Lemma 15) of Mei et al. [1]. We believe they made a typo here, resulting in a correct but slightly (non asymptotically) looser bound.\n\n### MDP Convergence Rate\n\nExtending the above convergence rate from the bandit setting to MDPs, by way of the nonstationary bandit setting described in section 4.1, is straightforward. Intuitively, since the above rate kicks in after a $\\tau$ such that $\\forall t \\ge \\tau\\ :\\ \\pi\\_{\\theta\\_t}(\\mathcal{A}^\\*)\\ge1/2$ (among other requirements), we will be able to get a similar result in MDPs after waiting sufficiently long for the learner to be guaranteed to play optimal actions with probability at least $1/2$, uniformly across all states. The formal statement of the convergence rate is as follows.\n\nWe prove that, when running Algorithm 2 (REINFORCE) in the finite-horizon MDP setting, there exists a constant $C > 0$ such that\n\\begin{align}\n\\exists\\tau>0\\ :\\ \\forall T>\\tau\\ :\\ \\frac{\\sum\\_{t=\\tau}^TV\\_0^\\*(\\rho) - V\\_0^{\\pi_{\\theta\\_t}}(\\rho)}{T-\\tau} \\le \\frac{C\\log(T-\\tau)}{T-\\tau}\\ .\n\\end{align}\nTo prove this, first we repeat the bandit proof in the nonstationary bandit setting&mdash;making only minor notational changes suffices. Then we conclude from Theorem 4.2 that there exists a time $\\tau$ such that at all $t\\ge\\tau$: \n\n*(a)* $\\forall h \\in \\mathcal{H}\\ :\\ \\forall s \\in \\mathcal{S}\\_h\\ :\\ \\lVert Q^\\*\\_h(s,\\cdot) - Q^{\\theta\\_t}\\_h(s,\\cdot)\\rVert\\_\\infty < \\delta/3$ , and\n*(b)* $\\forall s \\in \\mathcal{S}\\ :\\ \\pi\\_{\\theta\\_t}(\\mathcal{A}^\\*(s)) \\ge 1/2$ .\n\nAfter $\\tau$ we can apply the convergence rate uniformly across the states, take the maximum of the finite set of constant factors (the $C$s), and multiply this constant by the horizon $H$ (which is constant in $t$) to procure a constant $C$ which satisfies the desired inequality.\n\n[1] J. Mei, B. Dai, A. Agarwal, S. Vaswani, A. Raj, Cs. Szepesvari, and D. Schuurmans. Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates, 2024a.\n\n[2] Y. Duan, X. Chen, R Houthouft, J. Schulman, P. Abbeel. Benchmarking Deep Reinforcement Learning for Continuous Control, 2016."}, {"review_id": "62bAoPsref", "reviewer": "Reviewer_abhc", "summary": "This paper studies the convergence of the stochastic policy gradient in the tabular MDP case with any $\\Theta(1)$ learning rates. The technical challenges arise from the ties of policy values. The paper provides a new exploration lemma that enables the analysis.", "questions": "In the traditional Borel-Cantelli Lemma, the condition $\\sum \\Pr(E_n) < +\\infty$ only implies that the probability of infinitely many events occurring is zero. Therefore, the first claim in Proof Sketch 2 cannot be justified using the classical version. However, upon checking the appendix, it becomes clear that an extended version of the Borel-Cantelli Lemma is actually employed. I suggest that the authors explicitly state this in Proof Sketch 2 and properly cite the relevant result.\n\nAdditionally, Lemma 3.1 is not proved in the appendix. Instead, it appears as Proposition B.2. For clarity and consistency, I recommend aligning the naming between the main text and the appendix.", "limitations": "The scope is restricted to tabular settings. I believe more general settings, including linear MDPs worth exploring. \n\n\n\n\nResults are specific to the softmax policy class; generalization to other parameterizations (e.g., Gaussian in continuous action spaces) is not addressed.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Honestly, I am not an expert on the theoretical side of the policy gradient. However, as far as I see, this paper contributes fundamentally in this field. \n\n### **Strengths**\n\n  * The main contribution is proving global convergence of REINFORCE with any constant learning rate in finite-horizon tabular MDPs. This closes a longstanding theoretical gap between practice and theory.\n\n\n\n*   The paper removes the assumption of unique optimal actions or rewards, which was previously required in the bandit setting (e.g., Mei et al. 2024ab). This is important for generalizing to MDPs.\n\n\n\n*   The simulation section supports the theory and highlights the trade-off between fast learning with large learning rates and increased variance.\n\n---\n\n### **Weaknesses**\n\n\n\n\n *  The scope is restricted to tabular settings. I believe more general settings, including linear MDPs worth exploring. \n\n\n\n\n\n   * Results are specific to the softmax policy class; generalization to other parameterizations (e.g., Gaussian in continuous action spaces) is not addressed.", "was_revised": true, "final_justification": "This paper is technically sound. The author's rebuttal answers my questions.", "rebuttal": "We thank the reviewer for their valuable suggestions, and we appreciate that the reviewer recognize the contribution of our work. We address the reviewer's questions as follows.\n\n# Weaknesses\n\n> 1. The scope is restricted to tabular settings. I believe more general settings, including linear MDPs worth exploring.\n\nWe completely agree! There are a variety of very interesting extensions to more general classes of MDPs for the future work (e.g. various notions of infinite horizon, function approximation). We believe our results in the tabular setting will be useful in this direction. Some non-trivial efforts and techniques are also be required for these extensions, which is beyond the scope of one paper.\n\nFor example, for linear function approximation, there has been recent progress in convergence results for policy gradient methods **in the bandit setting** [1]. The analysis uses results in [3] when using large learning rates, while being restricted to the assumption that there are no ties in the true mean reward (Assumption 2.1 in the paper). We take this as an evidence that our results can also be used in generalizing these findings to MDPs. Again this would require non-trivial efforts, which we are excited to potentially explore in the future.\n\n> 2. Results are specific to the softmax policy class; generalization to other parameterizations (e.g., Gaussian in continuous action spaces) is not addressed.\n\nOur proofs rely heavily on specific structures of the softmax parameterization (in short, it is the softmax derivative gives the specific update forms, which makes Lemma 3.1 hold). This strategy on its own should be considered as a strength of the study since (i) softmax is so widely used in modern machine learning models; (ii) otherwise using general analysis tools without considering special structures wouldn't obtain strong results in this paper.\n\nThat being said, we agree with the reviewer that it is both interesting and possible to abstract out a set of generic conditions on the parameterization that will guarantee convergence. Our initial attempts indicate that a key condition is the parameterization is able to make its corresponding update not too aggressive (such that there is a chance to explore sufficiently, like Lemma 3.1). A more comprehensive study would require more time and non-trivial effort, which we leave it for future work. \n\nRegarding Gaussian parameterizations in continuous action spaces, our intuition is that our analysis cannot just apply to Gaussian, and more assumptions are needed for REINFORCE to work guarantee global convergence for Gaussian policies. In particular, the softmax parameterization can represent all policies in the simplex over a finite action set (except those that assign 0 probability to any action, but these can be approximated by the softmax to arbitrary precision). On the other hand, the Gaussian parameterization imposes significant restrictions on the representable policies, and cannot approximate arbitrary distributions over a continuous action space well (such as multi-model policies, and skewed non-Gaussian shapes). iIf the optimal policies cannot be represented by Gaussian, then convergence would not be guaranteed for such setups without further assumptions. One possible direction for looking for those assumptions is that the closure conditions explored by Bhandari and Russo, 2022 [2] would need to be met.\n\n# Questions\n\n> 1. In the traditional Borel-Cantelli Lemma, the condition $\\sum\\textup{Pr}(E\\_n) < +\\infty$ only implies that the probability of infinitely many events occurring is zero. Therefore, the first claim in Proof Sketch 2 cannot be justified using the classical version. However, upon checking the appendix, it becomes clear that an extended version of the Borel-Cantelli Lemma is actually employed. I suggest that the authors explicitly state this in Proof Sketch 2 and properly cite the relevant result.\n\nGood catch! While we do cite the extended result where we give its statement (Lemma A.1), it is definitely confusing for readers familiar with the standard version when we refer to \"the Borel-Cantelli Lemma\" in the main paper. We will include the citation at the first mention in the main text and carry around the \"extended\" qualification throughout the paper.\n\n> 2. Additionally, Lemma 3.1 is not proved in the appendix. Instead, it appears as Proposition B.2. For clarity and consistency, I recommend aligning the naming between the main text and the appendix.\n\nAgreed, in a future version of the manuscript we will implement matching names for results that are stated in the appendix and the main text.\n\n[1] M. Q. Lin, J. Mei, M. Aghaei, M. Lu, B. Dai, A. Agarwal, D. Schuurmans, Cs. Szepesvári, and S. Vaswani. Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation, 2025.\n\n[2] J. Bhandari, and D. Russo. Global Optimality Guarantees For Policy Gradient Methods, 2022.\n\n[3] J. Mei, B. Dai, A. Agarwal, S. Vaswani, A. Raj, Cs. Szepesvari, and D. Schuurmans. Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates, 2024a."}]

Author rebuttal:

Meta-review: This paper presents a new theoretical analysis of the REINFORCE algorithm with constant learning rate. All the reviewers appreciated the work and commented that the analysis is novel and provides a natural extension of the previous work by Mei et al. (2024). During the discussion phase, the authors also provided definite convergence rates for the bandit setting and MDP setting and I request the authors to include the results in the final version of the paper.
Decision: Accept (poster)