Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methods
Authors: Sara Klein
Simon Weissmann
Leif Döring
Venue: ICLR 2024 poster (2024)
Keywords: reinforcement learning
policy gradient
stochastic approximation
finite-time MDP
Primary area: reinforcement learning

Abstract: Markov Decision Processes (MDPs) are a formal framework for modeling and solving sequential decision-making problems. In finite time horizons such problems are relevant for instance for optimal stopping or specific supply chain problems, but also in the training of large language models. In contrast to infinite horizon MDPs optimal policies are not stationary, policies must be learned for every single epoch. In practice all parameters are often trained simultaneously, ignoring the inherent structure suggested by dynamic programming. This paper introduces a combination of dynamic programming and policy gradient called dynamical policy gradient, where the parameters are trained backwards in time. 
   
   For the tabular softmax parametrisation we carry out the convergence analysis for simultaneous and dynamic policy gradient towards global optima, both in the exact and sampled gradient settings without regularisation. It turns out that the use of dynamic policy gradient training much better exploits the structure of finite-time problems which is reflected in improved convergence bounds.

Published as a conference paper at ICLR 2024
BEYOND STATIONARITY: CONVERGENCE ANALYSIS OF STOCHASTIC SOFTMAX POLICY GRADIENT METHODS
Sara Klein, Simon Weissmann & Leif Döring Institute of Mathematics, University of Mannheim {sara. lsara.kleile klein, s simon. weissmann, leif.doering maninnnheenn de
ABSTRACT
Markov Decision Processes (MDPs) are a formal framework for modeling and solving sequential decision-making problems. In finite-time horizons such prob- lems are relevant for instance for optimal stopping specific supply chain prob- lems, but also in the training of large language models. In contrast to infinite horizon MDPs optimal policies are not stationary, policies must be learned for every single epoch. In practice all parameters are often trained simultancously. ignoring the inherent structure suggested by dynamic programming. This paper introduces a combination of dynamic programming and policy gradient called dy- namic policy gradient, where the parameters are trained backwards in time.
For the tabular softmax parametrisation we carry out the convergence analysis for simultaneous and dynamic policy gradient towards global optima, both in the exact and sampled gradient settings without regularisation. It turns out that the use of dynamic policy gradient training much better exploits the structure of finite- time problems which is reflected in improved convergence bounds.
INTRODUCTION
Policy gradient (PG) methods continue to enjoy great popularity practice due their model-free nature and high flexibility. Despite their far-reaching history (Williams) 1992 Sutton et al., 1999. Konda & Tsitsiklis 1999 Kakade (000), there were no proofs for the global convergence these algorithms for a long time. Nevertheless, they have been very successful in many applications, which is why numerous variants have been developed in the last few decades, whose convergence analysis, if available, was mostly limited to convergence to stationary points (Pirotta et al. 2013
Schulman et al., 2013] Papini et al. 2018: Clavera et al. 2018 Shen et al.) 2019 Xu et al. 2020b
Huang al.] 2220 Xu et al. [2000a] Huang et al.] (2022). In recent years, notable advancements
have been achieved in the convergence analysis towards global optima (Fazel et al. 2018: Agarwal
al.
2021
Mei al. 2220 Bhandari & Russo 2021
2022 Cen et al. 2022 Xiao 2022] Yuan
et al.
2022 Alfano & Rebeschini, 2023) Johnson et al. 2023). These achievements are partially
attributed to the utilisation of (weak) gradient domination or Polyak-Lojasiewicz (PL) inequalities (lower bounds on the gradient) (Polyak 1963).
As examined in Karimi al. 2016) PL-inequality and 3-smoothness (i.e. 3-Lipschitz continuity of the gradient) implies a linear convergence rate for gradient descent methods. In certain cases, only a weaker form of the PL inequality can be derived, which states that is only possible to lower bound the norm of the gradient instead of the squared norm of the gradient by the distance to the optimum. Despite this limitation,
can still be achieved in some instances.
This article deals with PG algorithms for finite-time MDPs. Finite-time MDPs differ from dis- counted infinite-time MDPs in that the optimal policies are not stationary, i.e. depend on the epochs. While a lot of recent theoretical research focused on discounted MDPs with infinite-time horizon not much is known for finite-time MDPs. However, there are many relevant real world applications stationaat finite-tim solutions such as inventory management in hospital supply
which require chains (Abu Zwaida et al. 202T) or optimal stopping in finance (Becker et al., 2019). There is a pre- vailing thought that finite-time time MDPs do not require additional scrutiny as they can be transformed

---

Published as a conference paper at ICLR 2024
into infinite horizon MDPs by adding additional time-coordinate. Seeing finite-time MDPs this way leads to a training procedure in which parameters for all epochs are trained simultaneously. see for instance Guin & Bhatnagar 2023). While there are practical reasons to go that way, will see below that ignoring the structure of the problem yields worse convergence bounds. The aim of this article is two-fold. Firstly, analyse the simultaneous PG algorithm. The analysis for exact gradients goes along arguments of recent articles, the analysis of the stochastic PG case is novel. Secondly, we introduce new approach gramming structure and view the MDP as a nested sequence of contextual bandits. Essentially, our algorithm performs a sequence of PG algorithms backwards in time with carefully chosen epoch de- pendent training steps. We compare the exact and stochastic analysis to the simultaneous approach. Dynamic PG can bee seen as a concrete algorithm for Policy Search by Dynamic Programming. where policy gradient is used to solve the one-step MDP (Bagnell et al. 20033 [Schererr] [0114) There are some recent articles also studying PG of finite-time horizon MDPs from a different per- spective considering fictitious discount algorithms (Guo et al. 2022) or finite-time linear quadratic
PG for finite-time MDPs. We exploit the dynamic pro-
control problems (Hambly et al. 2021
2023
Zhang et al. 2021 2023b a Zhang & Başar 2023)
This article can be seen to extend series of recent articles from discounted MDPs to finite-time MDPs. In AAgarwal et al. (2021),
the global asymptotic convergence of PG is demonstrated under tabular softmax parametri- sation, and convergence rates are derived using log-barrier regularisation and natural policy gradient. Building upon this work. Mei et al. (2020) showed the first convergence rates for PG using non-uniform PL-inequalities (Mei jet al. (02T). specifically for tabular softmax parametrisation. The convergence rate relies heavily on the discount factor as (1-7)- and does not not readily convert non-discounted MDPs. Through careful analysis, we estab- lish upper bounds involving HS for simulta- neous PG, contrasting with H for dynamic PG. Essentially, dynamic PG offers clear ad- vantage. Examining the PG theorem for finite- time MDPs reveals that early epochs should be trained less policies for later epochs are suboptimal. A badly learned Q-function-to-p leads to badly directed gradients in early epochs. Thus, simul- taneous training yields ineffective early epoch training. addressed by our dynamic PG algorithm, optimizing policies backward in time with more training steps. To illustrate this phenomenon implemented a simple toy example where the advantage of dynamic PG becomes visible. In Figure one can see 5 simulations of the dynamic PG with different target accuracies (blue curves) plotted against one version of the simultaneous PG with target accuracy 0.1 (dashed magenta curve). The
5.0
4.6
4.2
3.8
optimal value function
Value funct in trained bacdd time trained simuitareousll
50000
300000
130000
200000
250000
number of gradient steps
Figure 1: Evolution of the value function during training.
time-horizon is chosen as H = 5. More details on the example can be found in Appendix E
A main further contribution of this article is a stochastic analysis, where we abandon the assumption that the exact gradient is known and focus the model free stochastic PG method. For this type of algorithm, very little is known about convergence to global optima even in the discounted case. Many recent articles consider variants such as natural PG or mirror descent analyse the stochastic scenario (Agarwal et al. 2021 Fatkhullin et al., 2023 Xiao 2022 Alfano et al., 2023). Ding et al. stochastic PG. They use a well-chosen stopping time which measures the distance to the set of optimal parameters, and simultaneously guarantees convergence to the regularised optimum prior to the occurrence of the stopping time by using a small enough step size and large enough batch size. As we are interested in convergence to the unregularised optimum, we consider stochastic softmax PG without regularisation. Similar to the previous idea, we construct different stopping time, which allows us to derive complexity bounds for an approximation arbitrarily close to the global optimum that does not require a set of optimal parameters and this is relevant when considering softmax parametrisation. To the best of our knowledge, the results presented in this paper provide the first convergence analysis for dynamic programming inspired PG under softmax parametrisation in the finite-time MDP setting. Both for exact and batch sampled policy gradients without regularisation.
(2022) derive complexity bounds for antropy-regulane
2

---

Published as a conference paper at ICLR 2024
2 FINITE-TIME HORIZON MDPs AND POLICY GRADIENT METHODS.
A finite-time MDP is defined by a tuple (H, (H,S,A, r. p) with H = {0. (O..................... H - 1 decision epochs, finite state space S = So U... U UH-1. finite action space A = USES As. reward function r S x A + R and transition function p- S x A A(S) with p(Sn+1ls, a) = for every < H 1, 8 E S₁ and a E A,. Here (D) denotes the set of all probability measures over a finite set D.
Throughout the article π = (mT) the policy in decision epoch h E H. with Th (A,]s) 1 for every Sn. It is well-known that in contrast to discounted infinite-time horizon MDPs non-stationary policies are needed to optimise fnite-time MDPs. An optimal policy in time point h depends the time horizon until the end of the problem (see for example| P (2005)). The epoch-dependent value functions under policy are defined by
H-1 denotes a time-dependent policy, where TA : S. - ((A) is
H-1 r(S. An)]. h E H.
VB Vi (ph) == E
Σ kmh
(1)
where ueg is initial distribution, (Th)- ( denotes the sub-policy of i from h H and Em is the expectation under the measure such that Sn ~ μh, Ag ~ T (-(ss) and Sk+1 ~ p(-|Sx: A&) for h S k < H 1. The target is find (time-dependent) policy that maximises
the state-value function Vo at time O. In the following we will discuss two approaches to solve finite-time MDPs with PG:
An algorithm that is often used in practice, where parametrised policies are trained simul- taneously, i.e. the parameters for To, - are trained at once using the objective Vo. A new algorithm that trains the parameters sequentially starting at the last epoch. We call this scheme dynamic PG because it combines dynamic programming (backwards induc- tion) and PG.
In fact, one can also consider PG algorithms that train stationary policies (i.e. independent of h) for finite-time MDPs. However, this violates the intrinsic nature of finite-time MDPs (optimal policies will only be stationary in trivial cases). In order to carry out complete theoretical analysis as- sumptions are required. In this article we will assume that all policies are softmax parametrised, an assumption that appeared frequently in the past years. It is a first step towards a full understanding and already indicates why PG methods should use the dynamic programming structure inherent in finite-time MDPs. This paper should not be seen as limited to the softmax case, but more like kick-off to analyse a new approach which is beneficial in many scenarios.
Simultaneous Policy Gradient. Let start by formulating the simultancous PG algorithm that is often used in practice. The action spaces may depend on the current state and the numbers of possible actions in epoch h is denoted by dn Eess, |Agg). To perform a PG algorithm all policies Th (or the entire policy т) must be parametrised. While the algorithm does not require particular policy we will analyse the tabular softmax parametrisation
exp(f(sh, a)) 0 (0(s), ES),,EE E RR du
(alsn) Ea. exp(((s),a
(2)
where the notation S!H| defines the enlarged state space, containing all possible states associated to their epoch (see Remark A.I for more details). The tabular softmax parametrisation uses a single parameter for each possible state-action pair at all epochs. Other parametrised policies, e.g. neural networks, take states from all epochs, i.e. from the enlarged state space SIN], as input variables. The simultaneous PG algorithm trains all parameters at once and solves the optimisation problem (to maximize the state value function at time 0) by gradient ascent over all parameters (all epochs) simultancously.
Most importantly, the algorithm does not treat epochs differently, the same training effort goes into all epochs. For later use the objective function will be denoted by
H-1
J(0,p) = -Vo-* (n) = E
r(Sh, An)
(3)
h=0
3

---

Published as a conference paper at ICLR 2024
Algorithm 1: Simultaneous Policy Gradient for finite-time MDPs
Result: Approximate policy n n²
initialise ((0) _R de. Choose fixed step sizes 17 > O, number of training steps N and start distribution for 72 .,....N 1 do
g(m+l) ((m) + 13 VoVo VoVora ((m)
(4)
end
Set #" 7: g(N)
Furthermore, let o (s) = En= P7 (Sp, = s) be the state-visitation measure on and di (s)
PP (s) be the normalised state-visitation distribution. We denote by (n) supa J J(0 (u) the
optimal value of the objective function and note that J'())) V (1) sup,: Policy Vi" (p) under the tabular softmax parametrisation, as an optimal policy can be approximated arbitrarily well.
Dynamic Policy Gradient. First of all, recall that the inherent structure of finite-time MDPs is backwards induction principle (dynamic programming), see for instance (Puterman] 2005). To see backwards induction used in learning algorithms we refer for instance to Bertsekas Tsitsiklis [1996] Sec 6.5). In way, finite-time MDPs can be viewed dynamic PG approach suggested this article builds upon this intrinsic structure and sets on top PG scheme. Consider H different parameters 0g.-.., 0- such that 0, E Rdh A parametric policy (n*a | is defined such that the policy in epoch h depends only the parameter 0g. An example is the tabular softmax parametrisation formulated slightly differently than above. For each decision epoch h H the tabular softmax parametrisation is given by
nested contextual bandits. The
exp((n(s,a))
9n (als) = EvEA E exp(On(s,a') 0₂ = (0)(5.0))EES,..EA E Rd
(4)
The total dimension of the parameter tensor (fo.... 0H-1) equals the one of f from the Equation because 0x(s,, a) = (s,, a) for s, E S,, C S(M. The difference is that the epoch dependence is made more explicit Equation
2
The main idea of this approach is as follows. The dynamic programming perspective suggests to learn policies backwards time. Thus, we start by training the last parameter vector 0 on the sub-problem VH-1, one-step MDP which can be viewed as contextual bandit. After convergence up to some termination condition, it is known how to act near optimality in the last epoch and one can proceed to train the parameter vector from previous epochs by exploiting the knowledge of acting near optimal in the future. This is what the proposed dynamic PG algorithm does. A policy trained up some termination condition and then used optimise an epoch earlier.
Algorithm 2: Dynamic Policy Gradient for finite-time MDPs
Result: Approximate policy カ* se n initialise (00) (0(0) [00 E
for h H
do
Choose fixed step size Th, number of training steps N₁, and start distribution 14 for n O,..., Nn- do
0 ((n+1) (0 + Th Von V
(5th (
mott)) (mm))og
end
Set म T. of (N))
end
A bit notation is needed to analyse this approach. Given any fixed policy म, the objective func- tion Jn in epoch h is defined to be the h-state value function in state under the extended policy
4

---

Published as a conference paper at ICLR 2024
(n (((+1))) (T , Thb1............................ "...,,,H-11 #H-1),
H Σ (s)
Ju 11+ [h) Via 1( (((++1))) (mu) Ejp.
(* ((4as)
(5)
km
While the notation is a bit heavy the intuition behind is easy to understand. the policy after epoch h is already trained (this is +1)+ then Jn function of 0,, is the parametrised dependence of the value function when only the policy for epoch h is changed. Gradient ascent is then used to find parameter 0% that maximises Jn( ((t++),, 0x), for all S,, where ó, the dirac measure Note that to train f₂ one chooses 1(h+1) A (b+1) in Algorithm
priori it not clear if simultaneous or dynamic programming inspired training is more efficient. Dynamic PG has additional loop but trains less parameters at once. We give detailed analysis for the tabular softmax paramctrisation but want to give heuristic argument why simultancous training favorable. The policy gradient theorem, see Theorem A.5 states that
J(O,
Σ P (SL)
(a|s)) (a)s))))) (s), aeA.,.
Σ
SLESDI
involving Q-values under the current policy[ It implies that training policies earlier epochs massively influenced by estimation errors Q7 Reasonable training of optimal decisions is only possible if all later epochs have been trained well, i.e. Q7 R Q% This may lead to inefficiency earlier epochs when training all epochs simultaneously. It important to note that the policy gradient formula is independent of the parametrisation. While our precise analysis only carried out for tabular softmax parametrisations this general heuristic remains valid for all classes policies. Assumption 2.1. Throughout the remaining manuscript we assume that the rewards are bounded in [0, Jt,, for some !t > 0. The positivity is no restriction of generality, bounded negative rewards can be shifted using the base-line trick.
In what follows we will always assume the tabular softmax parametrisation and analyse both PG schemes. First under the assumption of exact gradients, then with sampled gradients la REIN- FORCE.
CONVERGENCE OF SOFTMAX POLICY GRADIENT WITH EXACT GRADIENTS
In the following, we analyse the convergence behavior of the simultaneous as well as the dynamic approach under the assumption to have access to exact gradient computation. The presented conver- gence analysis in both settings inspired from the discounted setting considered recently Agarwal et al. (22TT; Mei et al.) (2020). The idea is to combine smoothness of the objective function and (weak) PL-inequality in order to derive global convergence result.
3.1 SIMULTANEOUS POLICY GRADIENT
To prove convergence in the simultaneous approach we will interpret the finite-time MDP as an undiscounted stationary problem with state-space 8(H) and deterministic absorption time H. This MDP is undiscounted but terminates in finite-time. Building upon Agarwal al. (202T) Mei al.
2020 ; Yuan et al. (022) we prove that the objective function defined in Equation 3 3-smooth with parameter
H² [Ai and satisfies a weak PL-inequality of the form
| min mis T² (a (sn")ssss))) dx
(J*(z) J(0, dF
V|S(H|]
Here x² denotes fixed but arbitrary deterministic optimal policy for the enlarged state space S(H] and a" (sh) = argmax AeA,, xt (a(ss) is the best action in state 8y- The term
max SES d=
(6)
'See Appendix A Equation 12 and Equation 13 for the definition of the state-action value function Q and the enlarged state visitation measure p.
5

---

Published as a conference paper at ICLR 2024
is the distribution mismatch coefficient introduced in Agarwal al. (2021) 3.f Both properties
are shown in Appendix [.I] To ensure that the distribution mismatch coefficient can be bounded from below uniformly in 0 (see also Remark(B.4) we make the following assumption.
Assumption 3.1. For the simultaneous PG algorithm we assume that the state space is constant over all epochs, i.e. S₁ = S for all epochs.
As already pointed out in Mei et al. 2020) one key challenge in providing global convergence is to bound the term minses 77 (a ; (s) 8) from below uniformly in 0 appearing in the gradient as- cent updates. Techniques introduced in Agarwal et al. (2021) can be extended to the finite-horizon setting to prove asymptotic convergence towards global optima. This can then be used to bound = c( = inf, minses π ((m)) (s)ls) > 0 (Lemma B.5). Combining smoothness and the gradient domination property results in the following global convergence result.
Theorem 3.2. Under Assumption 3.1 let μ be a probability measure such that jus) for all S, let n कह and consider the sequence (0(ml) generated by Algorithm initialisation ((0) For O choose the number of training steps as N 10H R" it holds that
with arbitrary
Then
o²t
V (1) Vo olN) OLN)
(p)
One can compare this result to Mei et al. (2020) Thm for discounted MDPs. A discounted MDP can be seen as an undiscounted MDP stopped at an independent geometric random variable with surprise that algorithms with deterministic absorption time H
mean (1 -1 Thus, it comes have analogous estimates with H instead of (1 - -)- See Remark B.6 B.6 for a detailed comparison. Furthermore, it is noteworthy that it cannot be proven that c independent of H. We omitted this dependency when we compare to the discounted case because the model dependent constant there
could also depend on y the same sense.
3.2 DYNAMIC POLICY GRADIENT
We now come to the first main contribution of this work, improved bound for the convergence of the dynamic PG algorithm. The optimisation objectives are Jn defined in Equation The structure of proving convergence is follows. For each fixed h E H we provide global convergence given that the policy after is fixed and denoted by न. After having established bounds for each decision epoch, we apply backwards induction to derive complexity bounds on the total error accumulated over all decision epochs. The B-smoothness for different Jj. is then reflected in different training steps for different epochs.
The backwards induction setting can be described as nested sequence of contextual bandits (one- step MDPs) and thus, can be analysed using results from the discounted setting by choosing y 0. Using PG estimates for dicounted MDPs MMei et al. 2020 Yuan et al., (2022) we prove in Appendix
B.2 that the objective Jn from Equation 5 ijs smooth function in H, with parameter B, = 2(H Rt)lt"
and satisfies also weak PL-inequality of the form
(1h, T(++1)+ Pb)lla
min 7 SESr
pn) Jn (n,, (((t1)
is crucial to keep in mind that classical theory from non-convex optimisation tells us that less smooth (large (3) functions must be trained with more gradient steps. It becomes clear that the dy- namic PG algorithm should spend less training effort on later epochs (carlier in the algorithm) and more training effort on earlier epochs (later in the algorithm). In fact, we make use of this observa- tion by applying backwards induction in order to improve the convergence behavior depending on H (see Theorem ) The main challenge is again to bound min.es "h (a (s)ls) from below uni- formly in On appearing in the gradient ascent updates from Algorithm 2 In this setting the required
asymptotic convergence follows directly from the one-step MDP viewpoint using 7 = obtained in
Agarwal et al. 2021 Thm 5) and it holds e₁ inf,2o min.es, π 000)) (aj (s)]s) 0 (Lemma B.
There is another subtle advantage in the backwards induction point of view. The contextual bandit interpretation allows using refinements of estimates for the special case of contextual bandits. A slight generalisation of work of Mei et al. (2020) for stochastic bandits shows that the umpleasant unknown constants e₁ simplify if the PG algorithm is uniformly initialised:

---

Published as a conference paper at ICLR 2024
Proposition 3.3. For fixed h E H. let ph, be probability measure such that pn(ss) O for all s E Sh and let 0 < Th S NH- Let / E Rd be an initialisation such that the initial policy a uniform distribution, then Ch = - O.
This property in sharp contrast to the simultancous approach. where the best of our knowledge is not known how to lower bound explicitly. Comparing the proof's of 0 and Ch > 0 one can see that this advantage comes from the backward inductive approach and is due fixed future policies which are not changing during training. For fixed decision epoch h combining B-smoothness and weak PL inequality yields the following global convergence result for the dynamic PG generated in Algorithm 2
Lemma 3.4. For fixed H, μh be a probability meusure such that μt (,( > for all 8 E Sh.
let = H(ーー and consider the sequence (o( generated by Algorithm
2 with arbitrary
initialisation %%) and ग. For choose the number of training steps as No.
4. 4 "HH Then
it holds that
( Vn V( (mm) - V ( (wn) (pn) S
Moreover, if 0 initialises the uniform distribution the constants Ch can be replaced by 1
The error bound depends on the time horizon up to the last time point, meaning intuitively that an optimal policy for earlier time points in the MDP (smaller h) is harder to achieve and requires longer learning period then later time points (h near to H). We remark that the assumption on μa is not a sharp restriction and can be achieved by using strictly positive start distribution on So fol- lowed by a uniformly distributed policy. Note that assuming a positive start distribution is common in the literature and Mei et al. (2020) showed the necessity of this assumption. Accumulating errors over time we can now derive the analogous estimates to the simultaneous PG approach. We obtain a linear accumulation such that an & -eroor in each time point h results in overall error of e which appears naturally from the dynamic programming structure of the algorithm.
Theorem 3.5. For all h E H. let Ph be probability measures such that pn(()) > 0 for all E Sp. let Th 2(H-MJR- For e. > O choose the number of training steps as N₁ H(H- of
phh lloo.
Then for the final policy from Algorithm * (77 (0000
(N-11) }, holds for all E So that
(z((s) V0tH Sc.
If (0) initialises the uniform distribution the constants ch can be replaced by [A]
3.3 COMPARISON OF THE ALGORITIIMS
3.2 we first Comparing Theorem to the convergence rate for simultaneous PG in Theorem highlight that the constant Ch in the dynamic approach can be explicitly computed under uniform initialisation. This has not yet been established in the simultancous PG (see Remark B.1l and especially it cannot be guaranteed that c is independent of the time horizon. Second, we compare the overall dependence of the training steps the time horizon. In the dynamic approach Σ, N₁ scales with H in comparison to H in the convergence rate for the simultaneous approach. In particular for large time horizons the theoretical analysis shows that reaching a given accuracy more costly for simultancous training of parameters. In the dynamic PG the powers due to the smoothness constant, the स7 error which we have to achieve in every epoch and finally the sum over all epochs. In comparison, in the simultaneous PG power of is due to the smoothness constant, another power of 2 is due to the distribution mismatch coefficient the PL-inequality which we need bound uniformly in 0 (see also Remark B.3) and the last power is due the enlarged state space |S!*|| SS| H. Note that we just compare upper bounds. However, refer to Appendix E for a toy example visualising that the rate convergence in both approaches is order O(H) and the constants in the dynamic approach indeed better then for the simultaneous approach.

---

Published as a conference paper at ICLR 2024
4 CONVERGENCE ANALYSIS OF STOCHASTIC SOFTMAX POLICY GRADIENT
In the previous section, we have derived global convergence guarantees for solving a finite-time MDP via simultaneous as well as dynamic PG with exact gradient computation. However, in prac- tical scenarios assuming access to exact gradients is not feasible, since the transition function p of the underlying MDP is unknown. In the following section, we want to relax this assumption by re- placing the exact gradient by a stochastic approximation. To be more precise, we view a model-free setting where are only able generate trajectories of the finite-time MDP. These trajectories are used to formulate the stochastic PG method for training the parameters in both the simultaneous and dynamic approach.
Although in both approaches we are able to guarantee almost sure asymptotic convergence similar to the exact PG scheme, we are no longer able to control the constants e and cr respectively along tra- jectories of the stochastic PG scheme due to the randomness in our iterations. Therefore, the derived lower bound in the weak PL-inequality may degenerate in general. In order to derive complexity bounds in the stochastic scenario, we make use of the crucial property that (and on respectively) remain strictly positive along the trajectory of the exact PG scheme. To do so, we introduce the stopping times and stopping the scheme when the stochastic PG trajectory is too far away from the exact PG trajectory (under same initialisation). Hence, conditioning on {T 2 n) (and (Th 2 n) respectively) forces the stochastic PG to remain close to the exact PG scheme and hence, guarantees non-degenerated weak PL-inequalities. The proof structure in the stochastic setting is then two-fold:
1. We derive a rate of convergence of the stochastic PG scheme under non-degenerated weak Pl.-inequality on the event {T n). Since we consider constant step size, the batch size needs to be increased sufficiently fast for controlling the variance occurring through the stochastic approximation scheme. See Lemma D.4 and Lemma D.8
2. We introduce a second rule for increasing the batch-size depending on a tolerance ó > 0 leading to P(T I n) < 5. This means, that one forces the stochastic PG to remain close to the exact PG with high probability. See Lemma D.5 and Lemma D.9
A similar proof strategy has been introduced in Ding al. (2022) for proving convergence for entropy-regularis stochastic PG in the discounted case. Their analysis heavily depends on the existence of optimal parameter which is due to regularisation. In the unregularised problem this is not the case since the softmax parameters usually diverge to +/ - oo in order to approximate a deterministic optimal solution. Consequently, their analysis does not carry over straightforwardly to the unregularised setting. One of the main challenges in our proof is to construct different stopping time, independent of optimal parameters, such that the stopping time still occurs with small probability given a large enough batch size. We again first discuss the simultaneous approach followed by the dynamic approach.
Simultaneous stochastic policy gradient estimator: Consider K trajectories (s), af (k.0 H-1 for i 1, 1,... K, generated by s6 pt at x (+(1s) and sf, p( . for 0 < h < H. The gradient estimator is defined by
1 K H-1
V VJ (0,P))
Σ
Vog(( (a (c),ss)))
K
where 12. = HH-1 r(s), at)) is an unbiased estimator of the /-state-action value function in (sh, ai under policy TO This gradient estimator is unbiased and has bounded variance (Lemma D.I. Then the stochastic PG updates for training the softmax parameter are given by
g g(m) + 17 JK (0(m), ,14..
Our main result for the simultaneous stochastic PG scheme given follows.
Theorem 4.1. Under Assumption 3.1 let μ be a probability measure such that jus)) > O for all E S. Consider the final policy using Algorithm 7 with stochastic updates from Equation dennotdd denoted by ** n B(8) Moreover, for any 8,e > O assume that the number of training steps satisfies
N > (21SSH" c862
let 5H VN and K
10 max R" xa
Then it holds true that
6262
((V)(1)) V (1) 6) >1
8

---

Published as a conference paper at ICLR 2024
Dynamic stochastic policy gradient estimator: For fixed h consider K₁ trajectories (#) "=)k=h k=hh
for i 1..... Kr generated by sy pb. oz Th and of th for h < k < H. The estimator is defined by
K logg(= (ahls)))
J (0, m(++1): PN) = KR
1
where Ri, Et=h r(s), ai) is an unbiased estimator of the h-state-action value function in (5), aa)) under policy i. Then the stochastic PG updates for training the parameter f are given by
- Th V. (0,") Aa+11)
(x)) Mx).
(10)
Our main result for the dynamic stochastic PG scheme is given follows.
Theorem 4.2. For all h H. let pm be probubility measures such that un (s)(5) 0 for all h H.
E Sh. Consider the final policy using Algorithm 2 with stochastic updates from Equation 70
denoted by At (17% goo)
g(Nu-1 1) H-1
Moreover, for any d.6 > O assume that the numbers of 12(H-b) R)R H²
5N H22
training steps satisfy No. 2
let 17h. 21H THH-AR-NN and Kn. 2
6
c
Then it holds true that
P P( So Vo(s)
(s) <c) > 1 1
Comparison In both scenarios the derived complexity bounds for the stochastic PG uses a very large batch size and small step size. It should be noted that the choice of step size and batch size are closely connected and both strongly depend on the number of training steps N. Specifically, as N increases, the batch size increases, while the step size tends to decrease to prevent exceeding the stopping time with high probability. However, it is possible to increase the batch size even further and simultancously benefit from choosing a larger step size, or vice versa.
An advantage of the dynamic approach is that O₁ can be explicitly known for uniform initialisation. Hence, the complexity bounds for the dynamic approach results in practicable algorithm, while c is unknown and possibly arbitrarily small for the simultaneous approach. Finally, we will also compare the complexity with respect the time horizon. For the simultaneous approach the number of training steps scales with H and the batch size with H while in the dynamic approach the overall number of training steps scale with H² and the batch size with 2 We are aware that these bounds are far from tight and irrelevant for practical implementations. Nevertheless, these bounds highlight once more the advantage of the dynamic approach in comparison to the simultaneous approach and show (the non-trivial fact) that the algorithms can be made to converge without knowledge of exact gradients and without regularisation.
CONCLUSION AND FUTURE WORK
In this paper, we have presented a convergence analysis of two PG methods for undiscounted MDPs with finite-time horizon in the tabular parametrisation. Assuming exact gradients we have obtained an (1lnn) -oooe--conveeeeecee rate for both approaches where the behavior regarding the time horizon and the dedel-dependent constant e better the dynamic approach than the simultancous approach. In the model-free setting we have derived complexity bounds to approximate the error to global optima with high probability using stochastic PG. would be desirable to derive tighter bounds using for example adaptive step sizes or variance reduction methods that lead to more realistic batch sizes.
Similar to many recent results, the presented analysis relies on the tabular parametrisation. However, the heuristic from the policy gradient theorem does not, and the dynamic programming perspective suggests that parameters should be trained backwards in time. It would be interesting future work to see how this theoretical insight can be implemented in lower dimensional parametrisations using for instance neural networks.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENT
Special thanks to the anonymous reviewers for their constructive feedback and insightful discus- sions, which greatly improved this paper. We also acknowledge the valuable input received from the anonymous reviewers of previous submissions. Sara Klein thankfully acknowledges the funding V. and is grateful to the DFG RT31953 "Statistical Modeling
support by the Hanns-Seidel-Stifie of Complex Systems and Processes" for funding this research.
REFERENCES
Tarck Abu Zwaida, Chuan Pham, and Yvan Beauregard. Optimization of inventory management to prevent drug shortages in the hospital supply chain. Applied Sciences, 11(6), 2021. URL
https: httpp:://www.pp....... com 200m/2076-m0 3417/11/6/2725
Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98)11-76, 2021. UtLhttp: http:/tteee/....rrrrrr//////e//s
html
Carlo Alfano and Patrick Rebeschini. Linear convergence for natural policy gradient with log-linear policy parametrization. arXiv Preprint, arXiv:2209. 2023. URL https://arxix:
org/aba/ 220..1291110
Carlo Alfano, Rui Yuan, and Patrick Rebeschini. A novel framework for policy mir- ror descent with general parameterization and linear convergence. In Advances in Neu- ral Information Processing Systems, volume 36, pp. 30681-30725. Curran Associates, Inc., 2023. URL https::/ppocceed// www.::/innnn......ssere........e neurips. ce cc/paper. files/paper/2023/ 11l10/25s82777fff555777555522283 oaner
J. Bagnell, Sham M Kakade, Jeff Schneider, and Andrew Ng. Policy search by dy- namic programming. In S. Thrun, L. Saul, and B. Schölkopf (eds.), Advances
in Neural Information Processing Systems, volume 16. MIT Press, 2003. URI.
https: httts://ppceeeinnssssuoooo.....o http:////ppppeeeeeeea///a/////// FlLes//ppper2200//LL 3B724411ccaaaceee0000066642222-2
Amir Beck. Order Methods in Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2017. URL
Sebastian Becker, Patrick Cheridito, and Jentzenn Deep optimal stopping. Journal of Machine Learning Research, 20(74))1-25, 2019. URL http://iw....orrpppppss/////////
html
Dimitri P. Bertsekas and John N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1st
edition, 1996. ISBN 1886529108.
Jalaj Bhandari and Daniel Russo. On the linear convergence of policy gradient methods for finite MDPs. In Proceedings of The 24th International Conference on Artificial Intelligence and Statis- fies, volume 130 of Proceedings of Machine Learning Research, pp. 2386 2394. PMLR, 13-15 Apr 2021.
URL wwtpthtt:////t httpps:/prroceedirintt
.ml...r..... http://..........ee/e////aaaaaaa
i2la html
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv Preprint, MeXXvv1906.017880 2022.
01786
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4):2563- 2578, 2022. URL/https: httpltttss:/doi.orgggg
1287/ wtt.:///....//...ee...... 20w.....022.... 2151
Ignasi Clavera, Jonas Rothfuss, John Schulman, Yasuhiro Fujita, Tamim Asfour, and Pieter Abbeel. Model-based reinforcement learning via meta-policy optimization. Proceedings of The 2nd Conference on Robot Learning, volume 87 of Proceedings of Machine Learning Research. pp. 617-629. PMLR, 29-31 Oct 2018. URL https: https::/pproeeedingg mir. press/v87/ wtt..//sss.......ss////////
llavera 8a httml
10

---

Published as a conference paper at ICLR 2024
Yuhao Ding, Junzi Zhang, and Javad Lavaci. Beyond exact gradients: Convergence of stochastic soft-max policy gradient methods with entropy regularization. arXiv Preprint, arXiv:2110.00117, 2022. URL //apiii..///a......//.//i/.v..v/ org/ 2ttp:///b/2111111111
lyas Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao He. Stochastic policy gradient meth- ods: Improved sample complexity for Fisher-non-degenerate policies. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learn- ing Research, pp. 9827-9869. PMLR, 23-29 Jul 2023. URL wwtps:ts////cc. /ptp:aas//poooeeiggg..o.t v2.2 1t2.0//aaathhl11122222
press/ /tlaa//2200
html
Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradi- ent methods for the linear quadratic regulator. In Proceedings the 35th International Conference on Machine Learning, volume 80 Proceedings of Machine Learning Research, pp. 1467-1476 ml preas. http:/v0//// faa.lfaazll88.
PMLR, 10-15 Jul 2018. URL
html
Soumyajit Guin and Shalabh Bhatnagar. A policy gradient approach for finite horizon constrained Markov decision processes. In 2023 62nd IEEE Conference on Decision and Control (CDC), pp. 3353-3359, 2023. URLhttps: /ttaa////eeeeepp/rr/eee leee . wttpr////aatttt//ccttoeeoo.aa
10383413
Xin Guo, Anran Hu, and Junzi Zhang. Theoretical guarantees of fictitious discount algorithms for episodic reinforcement learning and global convergence of policy gradient methods. Proceedings of the AAAI Conference on Artificial Intelligence, 36(6) Jun. 2022. URL https:
//ois. www..aiaa......... org/ ptrg/inee index. pttp:/AAt//rttcll///iie.///////
Ben Hambly, Renyuan Xu, and Huining Yang. Policy gradient methods for the noisy linear quadratic regulator over finite horizon. SIAM Journal on Control and Optimization, 59(5):339-3331,, 2021. URL https: /ww./ org/ 10.
Ben Hambly, Renyuan Xu, and Huining Yang. Policy gradient methods find the Nash equilibrium in n-player general-sum linear quadraaca games. Journal of Machine Learning Research, 24(139): 1-56, 2023. URL (RRt:tt::// http::///mmm..r.o/pp////ssss/ss/ http//////////2 0842 html
Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Momentum- policy gradient meth- ods. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4422 4433. PMLR, 13-18 Jul 2020. URL
https://proceeding mlr wttpssssmm..pprrr. press http//v1/v////// http////llggagaaa..e html
Feihu Huang, Shangqian Gao, and Heng Huang. Bregman gradient policy optimization. In Interna- net/
lional Conference on Learning Representations, 2022. URL
Forum?id-220 2F 2FTTulNN
Emmeran Johnson, Ciara BurkeB and Patrick Rebeschini. Optimal convergence rate for exact policy mirror descent in discounted Markov decision processes. In Advances in Neu- ral Information Processing Systems, volume 36, pp. 76496-76524. Curran Associates, Inc., filess/aper/20233 inw..uuurinnng....nn........... httpp/aaeeeeeeee//apeeeeeeeeeeee
2023. URL
F11e:/00rs22eclcccaa0000aaeeeee2 -apeer-ape----- Conference pdf
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pp. 267-274. Morgan Kaufmann Publishers Inc., 2002.
Sham M Kakade. A natural policy gradient. In Advances in Neural Information Processing Sys- tems, volume 14. MIT Press, 2001. URL httpp/pppe//ppppoeeeess...p.pp.p
Ei Leeeeppaa wwss/paprr/ae htapperr2000/555 20w0/f011iio 4b8 6abe (ac.cccceeeae33eeee11cce33e13633
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Solyak-Lojasiewiice condition. In Machine Learning and Knowledge Discovery in Databases, pp. 795 811, Cham, 2016. Springer International Publishing. URL
https://doi .org 007
1612-612-- 1_50]

---

Published as a conference paper at ICLR 2024
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. In Advances in Neu- ral Information Processing Systems, volume 12. MIT Press, 1999. URL
http:://proceeinggg.. cwtprippppccppppp..eeeeeee files/papens #tLes/paper//39//111e Pappelperra-aarrr.r---a Paper.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global conver- gence rates of softmax policy gradient methods. In Proceedings of the 37th International Con- ference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp- mlr www..p.sss/vvi.....m
2820-6829) PMLR, 13-18 Jul 2020. URL https: https::/proceedingg
deei20b.. html.
Jincheng Mei, Yue Gao, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. Leveraging non- uniformity first-order non-convex optimization. Proceedings of the 38th International Con- ference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pp. 7564. PMLR, 18-24 Jul 2021. URL https:: wttpee/e/rrrammrmm.rss/////////
ngs. prils.pres//11////
me www..aatmmmmmmm.mmmmmmm h
Yurii Nesterov. Introductory Lectures on Convex Optimization. Springer New York, NY, 2013, URL https: .org/10....... wtt..oo/...100/1-11111111
8853-9
Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance- reduced policy gradient. In Proceedings of the 35th International Conference on Machine Learning, volume 80 Proceedings of Machine Learning Reseurch, pp. 4026-4035. PMLR, 10-15 Jul 2018. URL htttttss://prcceeinngggeoeeeeeee wttpm/ppeee.////////pp/. http///00/p/////m/
html
Matteo Pirotta, Marcello Restelli, and Luca Bascetta. Adaptive step-size for policy gradi- ent methods. In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL https:: httpp::/pproceddigg..eeeiiiiiiii http://///....ea.......EEEEEEaa.
files/
B.T. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathe-
matics and Mathematical Physics, 3(4):864-878 1963.
(63) 90382-33330
M.I. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John
Wiley & Sons, 2005. ISBN 9780470316887.
Bruno Scherrer. Approximate policy iteration schemes: A comparison. In Eric P. Xing and Tony Jebara (eds.), Proceedings the 31 International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 1314-1322, Bejing, China, 22-24 Jun 2014. PMLR. URL
www.mmmr..rrrrse. /32///222//// scherrer14.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region
policy optimization. In Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1889-1897. Lille, France, 07- 09 Jul 2015. PMLR. URL httph: tttps::/proceed: ngs m press/v37. schu 1mnn html
Zebang Shen, Alejandro Ribeiro, Hamed Hassani, Hui Qian, and Chao Mi. Hessian aided policy Machine Learning, volume 97
gradient. In Proceedings of the 36th International Conference PMIR, 09-15 Jun 2019. URL. of Proceedings of Machine Learning Research, pp. -738.. httpps:/ppocceeeee
https: htppppppepiinnss/eee/eeepep..s.t
www.rrr....... wal.s.pres//vee /
wtt//////nn/neee/ shennshensls 9d. htteenldd...mlll...mmmmmm
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gra- Advances
dient methods for reinforcement learning with function approximation.
in Neural Information Processing Systems. volume 12. MIT Press. 1999. URL
45G52488500e33ee000e00322------3 fwles/paper/1199/
pdd
Ronald J. Williams. Simple statistical gradient-followngg algorithms for connectionist reinforce- ment learning. Machine Learning, 8(3))229-25)) 2566. 1992. URL/attps: htttttps:/ddi..rooo/ /ttp:////o..oo./111000000
BF RFC0992696
12

---

Published as a conference paper at ICLR 2024
Lin Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23(282):1-366 2022. http:p/p///all.ccoc/////////////
Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recur- sive variance reduction. In International Conference Learning Representations, 2020a. URL
htttps://ppeneeiee.. net forum?1d-HUJxIUSS oegp
Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance- reduced policy gradient. In Proceedings of The 35th Uncertainty in Artificial Intelliencce Con- ference, volume 115 of Proceedings of Machine Learning Research, pp. 541-551. PMLR, 22-25
Jul 2020b. URL http:: pttttp:://proceeinnng m.r. wwt.sprsssssvssueusse xu2 /tt.e/ainnnng.......ra////////// html
m
Rui Yuan, Robert M. Gower, and Alessandro Lazaric. general sample complexity analysis of
vanilla policy gradient. In Gustau Camps-Valls, Francisco R. Ruiz, and Isabel Valera (eds.), Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 3332-3380. PMLR, 28-30 Mar 2022. URL
mlr. wwwppprssssss. / http:s//wwiyyyyaa222aaaaa html
Kaiqing Zhang. Xiangyuan Zhang, Bin Hu, and Tamer Basar. Derivative-free policy optimization for linear risk-sensitive and robust control design: Implicit regularization and sample complex- ity. In Advances in Neural Information Processing Systems, volume 34, pp. 2949-2964. Cur- ran Associates, Inc., 2021. URL http f22e:7/20..44111177766622/077012
files/
Xiangyuan Zhang and Tamer Başar. Revisiting lqr control from the perspective of receding-horizon policy gradient. IEEE Control Systems Letters, 7:1664-1669, 2023, URL /tL/itttps:///o..rr//
19..1199/LCSS3 2023. 3271594
Xiangyuan Zhang, Bin Hu, and Tamer Başar. Learning the Kalman filter with fine-grained sample complexity. In 2023 American Control Conference (ACC), pp. 4549 2023a. URL https:
//doi.org/ 10. 23319/ACCC5772 2023. 10156641
Xiangyuan Zhang, Saviz Mowlavi, Mouhacine Benosman, and Tamer Başar. Global convergence of receding- horizon policy search in learning estimator designs. arXiv Preprint, arXiv:2309.0483) 2023b. URL https: /ttp///aavvv/.e//eeeeeeeeeaaeeea org/ 2309, 04831
13

---

Published as a conference paper at ICLR 2024
A PRELIMINARY RESULTS
Before we prove some preliminary results we will give more detailed description of the enlarged state space STA] and introduce more functions and notation used throughout the proofs.
Remark A.I. The enlarged state space introduced for the simultaneous approach encompasses all possible states across all epochs. Therefore initially, states associated with their respective epochs, resulting in disjoint state spaces between epochs, which are subsequently fused into a single
comprehensive state space S Formally, this means that for every state space Sn = {s),... ; 84
one constructs disjoint sets Dj- = Sn x {h} = . J. ,h") } for h = 0.... H - 1. Then, s!Hl : Do H ..... t - contains all possible states associated with their epoch.
The h-state-action value function for every tuple a) E Sh x A is defined by
h " (s,a) = r(),a) +
Σ a) 3'ESA-1
h --2
(11)
where (s) (o, the ft-state value function with start state E Sn. Note that Q₁ is indepen- - (8, a) == r(s, a) independently of any policy. Furthermore,
dent of policy Tr and for H - 1, QH-
define the h-state-action advantage function
A (()) (s,a) =- 0% T1)+)) (8, a) T(N) (s), 8 E Sn E A.-
(12)
In the following, we will suppress the dependence of T(N)) and write in the superscripts of Vn, Qh and An. when the policy is clear out of context.
Remark A.2. Note that we can drop the subscript h in the value function, state-action value function or advantage function, when we define them on the enlarged state-space SIM, Then, V is a vector of dimension [ and Q and are matrices of dimension [S(H] JA]. Hence, using the state
8& E S(K) assigned to the epoch h, we use the notation V** (Sn) = V (sx) to denote the assigned value function in epoch h. Similar also for Q and A.
Moreover we define the state visitation measure on the enlarged state space as
p (sh) == p (S₁ si), for every E S!H| and the state visitation distribution d Em.ssin P7 (sx)= Exes Pj (s) H.
(13)
1 x=" H
Pp
Note that it holds
The performance difference lemma (akkade & Langford 2002) is useful identity to compare policies. It turns out to be very useful to prove convergence of PG methods (Agarwal et al. 2021 For finite-time MDPs obtain the following version.
Lemma A.3 (Performance difference lemma). For any h E H. and any pair of policies g and x' the following holds true for every s Sn:
H-1
(T) VT (s)
Σ
E3,
[
(Sk, Ac)
k=h
Proof.
H
(8)
V/
(s) T()
r(Se, As) VTT (s)
#-1
H-1
E T(k)
r(Sk. A&) + Σ
(Sk)
Σ
V (Sx)
- V (s)
9
kmh
Jmh
H-1
H-1
E (()
r(S An) + Σ
VT (St)
Σ
Vs (Si)
k=h+1
k=h
H-1
H-2
H-1
E (1)
r(St. Ax) + Σ
V
Vel (Sx+1)
Σ
VT (5x)
9,
k=h
k=h
k=h
14

---

Published as a conference paper at ICLR 2024
H-1
E (()
(r(Sk, + (S+1(5k+1) - V (Sx))
Sn.
E (6)
A (Sk: An)
S.
k=h
S4 = AR (Sk, An)]
where we have used that r(Sk, Ax) + V (Sk+1) Q7 (Sk, At). In the fifth equation used the notation Vи= = 0 and note that QH-1 r independent of any policy.
This implies a corollary for the objectives (0, (i) and Jn (On, a(h-1) 1); Ph).
Corollary A.4. For the objective J(0, defined in Equation 3 and Jn (On, #( defined in Equation iit holds
H-1
(') J(0,N)= = 1
Σ
A (Sh: An)
Σ S4 #NES.N]
P (sn) (shs a" (sn))
and
Jh 17(1)))))) (On, 1(0+ pb) BE [A (s" (((+t))))))) (Sh. An)]
Proof. The first claim follows directly from Lemma A.3 and the definition of the state visitation measure in Equation 13 For the second claim, we proof a more general result: For any h E H. and two policies π and n²: If T(h+1) / 1)+ it holds that
(T) Vo (s)
Teny Sy
A (Sh An)
To see this, let k > h, then
A% (Sk, As)
Σ (alsss
Σ
Teh p(s' ls, a
Q (Sk. Au) Vi (Sw)
Sh. Sh
s'ES
Σ Ta(a)s)
p(8 18, Σ e'ES
m(n+1)
O (Sk, Ax) VT (Sa)
Su+1=o
aEA
Σ Ta(a)s)
Σ p(8'l8, (1/11sa)) a)
Es
[ IQT (Sx, Ant]] - B3 a
[V (Se)
aEA
e'ES
[Ta(als)
Σ
p(s'le |s, a)
E (
VT (Sk)
E ((--1)
(Ve((Sa) (Sw))
aEA
#'ES
O.
The claim follows with Lemma A.3
Next we derive the policy gradient theorems for finite-time horizon MDPs in both, the simultaneous and the dynamic approach.
Theorem A.5 (Policy Gradient Theorem for the simultaneous approach). Consider any parametri- sation T on the enlarged state space S(H), then the gradient the J(O., p)) defined in Equation is given by
J((. = E
V log(* #
" (AN1SW)) (Sh, An)
h=0
Σ
p (sk)
Σ
(sh.
=
SIES
aEArp
15

---

Published as a conference paper at ICLR 2024
Proof. The second equality follows directly from the definition of the state visitation measure in Equation| 13
For the first equality consider the probability of trajectory (so, dp. ................................ S. Qn-1) under the policy T² and initial state distribution i.e.
カ-1
(ao|s0) (o) P (T) = p(sn)= (aol
II
p(ss 9h akI=) (an
Then,
Vlog(p)) (T)) = V (log(u(s))) + (og(="(aol00))
H-1
log(p(s + log(s (og(="(an(sx)) (axls)))
V
log( (anlss))
which is known as the log-trick. Let W be the set of all trajectories from 0 to H - 1. Note that W finite due the assumption that state and action space is finite. Then,
VJ(0m))= V
Σ TEW
Pi
r(sks ax)
k=
H Log(g (T))
Σ
P (T)
Σ
r(8k ax)
7EW
k=0
Σ TEW
V Vlog(= (an (8h))
rsk, 0k)
H
V Vlo((T (an (8h))
r88:; 0k)
TEW
h=
h=h
#-1
E
log(( (An
Σ
rSnn An)
H
H-1
E
V log(( (At
Σ
r(Sk, Ab) Shr An
km
V log(m" (AalSa) Io QT (Sh, An)
h=0
In the forth equation we have used that for every < holds
ET V log(=" (AN())(AA)))))r A4)]
B
E
V log((T (A,lS))(An So. Au... Sh-1, An r( As)
and furthermore
E
V log(s= (An)Sh)) Swn) Su, Sh-, Si]
V llog(= (An (ANISa)) |Sh]
= E
Σ
n" (a)s)) log( (An|(A))
aeds
V
Σ
<a(assh)) = O.
dE.As,
16

---

Published as a conference paper at ICLR 2024
Theorem A.6 (Policy Gradient Theorem for the dynamic approach). For a fixed policy it and h H the gradient of (0% ((h+1), 5τ) defined in Equation is given by
(J,(n, ((++)); 6s) = Bs (-18) V log(n" (Ax))))) (An)(m((
As]].
Proof. The probability of trajectory T (T" ((h+1))= = (T ; and initial state distribution 6, is given by
(sh, ah...... -:-1:
5 ( under the policy
H-1
10 a(nt)) (T) = (sx) (an
II
Ps
Am
Then,
(x" (((tt)))))) = V (1o((5((5h)) + log(oo (an(s((an)))))
V Pog(ps
Σ
0x- log( nA (ax|ss)
R=++1
Volg(= (anls))),
which is known as the log-trick. Let W be the set of all trajectories from to H 1. Note that W finite due the assumption that state and action space is finite. Then for E S₁.
H-1
Ju (On, ((++1),
Σ TEW
Ps
(n FO
(T)
Σ
r(ks ax)
Am
Σ
Ps
( -((11)))
(T) log(ps aaain)
r rsk ax)
TEW
H-1
Σ TEW
Ps
(T 1((11)))
l (anlsn))
r(sks ax)
E
V log(TT (An|())) ((1))))
Σ
r(Sk: An)
S
k=h
Es S,=s
(m m(tt)))
V Vog((" "log(T((A (ArlSa))
Σ
r(Sk. As) Sn, An
k=h
Vlog(n (A₁ ( (S)) An)
Using these two theorems we can explicitly derive the derivatives of objective functions under the softmax parametrisation. First, we compute the derivative of the softmax policy for every 8 E S and As.
((sa))
# (a(s)
EveA clloaa)) cloaa)
with parameter E Id:;
i llg((m (als)) a0(a','') s²)
1 | - (a'ls")))
Hence,
V (og(s" (1 - - (a'ls'))
d'E,, E Rd4
17

---

Published as a conference paper at ICLR 2024
Lemma A.7. The partial derivative of the objective defined in Equation 3 is given by:
0J(0, p)) @0( a) PH (s)))"(((ss))) (sh, a),
for every sh E S(H) and E Asn.
Proof. Let 8/, 8TM and a E Asn. Using Theorem A.5 holds that
0J(0,
E
log(n log(n (A (Sn, An)
(8(sh,a) a)
(8 (p(s)aa)
H
Ex
1 [8) (1(A)=0) (1 > (Sh. And
h=0
PT (Sh, sn) Σ π (a'ls))) Qf (sn.
p (sn) TT (alsn) (sh. (a - Σ (d((d)s))=)((sss) (sn
PT (alsa) (s),a))
Lemma A.8. For fox E H. the partial derivative of the objective defined in Equation is given by:
OJ, 1(++1), (als)) (50 F((tt)) (s, 08(s,a)
for every E Sh, and a E A.
Proof. By the policy gradient Theorem A.6
(n,, (141)) = Viewp (0, 1(1+))) 54)
Σ
=
8ES
V log(n" (A As)]
SES
Next plug in the derivative of the softmax parametrisation and obtain
V Jn,0 ((+4):
(4 -d'(s(s))) S'ESna'EA Σ (s (
Q (Sh,
SES
(E)(()) (( (dd J'ES
SES
acA.
(mu(s') (d'ls) (d'sss (n(ss) Σ (alss)) d'SS,a'EA,
aed. a'ES,,
-mm((') (a'ls')
= (mans)) ne m (am (5','') "'SM,
where used that Eacs, - (d = (n,0,, #1(+1): dz)
18

---

Published as a conference paper at ICLR 2024
B PROOFS OF SECTION 3
B.1 PROOFS OF SECTION 3.1
Lemma B.1. The objective [(, 4 from Equation 3 is smooth in 0 with parameter / = 12 (A))
Comparing this result to Lemma E.1. in Yuan et al. (2022) where the smoothness constant discounted MDP under softmax parametrisation given by (I- (2 - F we can see that r- the expectation of a geometric r.v. and the expected length of a discounted MDP, is replaced by H, the expected length of the finite-time MDP.
Proof. We are going to bound the norm of the hessian. Therefore, we first calculate the first and second derivative if J for finite-time horizon stationary MDPs. So, let 7 (so, do, $1...., -H-1, aI- be a trajectory of the MDP under policy x² and denote by p the discrete probability density. Then,
H
V((0,))= = V Σ (T()T)
Σ
r(sh: r(sh:an)
h=0
H-1
H-1
Σ (T)
v Vlog( TT (ax (s,))
Σ
r(sn, an)
h=0
1=0
H-1
Ex
v llog(= (an
Σ
r(sh, r(sn)an))
For the second derivative we have
V²J(0,m) (I PL
log(("
r(sh, an))
h=
H-1
H-1
H-1
Vlg((n (anlsn))) (aallr"(alll
( (anlsn)))
v
Σ h=
r(sh: an)
h=
h=0
(1)
H
H-1
22 log( a (anlsw))
Σ
r(sh,
r(sh.an)
A=
h=0
(2)
Using the bounded reward assumption we get for the second term, that
[1(2]] <
2 log(T
(anls))( HR
h=
-HR Σ B || log( lag( (anls)))ll
By Lemma 4.8 in Yuan et al. (002), we have for the softmax parametrisation that
E || log( (ax < 1. Hence,
[2)1] < R*
19

---

Published as a conference paper at ICLR 2024
Next for the first term.
H
[I(1)]I - 1
V log((T (axls)))l H1
-HR
E
(an
h=0
H
A
where we first used the bounded reward assumption, then Lemma 3.6 and again Lemma 4.8 from Yuan et al. 20022. Finally, we obtain that
I J(0, 12
A
Lemma B.2. It holds that
d min SA ESDI T² (a(aass))ss,,
m)ll2
(J*(M) J(),
VISIMI
d
Proof. The idea of the proof follows the outline Mei et al. (2020 Lem. 8) from the discounted setting. It holds
Ov²² (m)
3/1/22
((,,
Σ
Σ
(0(s. a)
Su ESTS
ave" (1)
2/22/2
8y. EST (0(s,,
00 Sh; (8n))
ov (1)
Σ
(8) a (sn))
SESSINg
Σ
PH (m (sn)ssss)) a"n,a"(sz))
VISHT
min sy ESINI T (a*
|1-
Σ
Ph (st)
A (sh, a" (sh))
VISHT]
00
min sn ESII TO (a" (sn)))))))
d
Σ
Pj (Sn)
(sh, a" (sn)
VISHH]
dx
EStN)
=Bn ED Ag" (Sn.A.))
min sn EsP2y T (a*()))))))
(J J(0,
S|S
The third line is due to Cauchy-Schwand afterwards we used the derivative of the objective function by definition of the state visitation
from Lemma A.7 For the firths line, that oc
measures and distribution mismatch coefficient (see Equation 6.. Finally, the last equation is due to Corollary A.4 from the performance difference lemma.
O
Remark B.3. Note that in order to use this weak PL-inequality uniformly we also have to bound the distribution mismatch coefficient uniform in 0. Therefore, under Assumption 3.1 it holds dy (s) >
us(s by definition for any since
8-1
(s)
Σ
pa M (Sn = =s) 2 H ((s).
(14)
H
h=0
20

---

Published as a conference paper at ICLR 2024
Hence, we obtain that
min SESII T (Paaaa d |- (J(x)- J(0.N))
H H
Remark B.4. Without Assumption
3.1 the expression
H-1
E SES h=0
pa J
(S
= s)=
Σ S
P(S = sk)
(15)
cannot be bounded from below by μ., since the probability to visit states later epochs depends crucially on 0. This cannot be covered by μ the state 8n might not belong Sp.
Lemma B.5. Let μ be a probability measure such that p(s) 0 for all S and let 0 S 5 Consider the sequence (0lm) generated by Algorithm for arbitrary o(0) E RE,, du, Then,
= =000) = infa min sxEtt) π pl0)) (sn))sn) > O.
The proof is adapted to the finite-time horizon from Mei et al. [2020] Lem. 9).
Proof. We will drop the μ in [0, 14)
for the rest of the proof. Define for all Sp &SH))
(sx) = Q (sh, ai (8))
max
Q a) 0, and A min A A*(s)) > #xEStH|
aza" afta"(s))
where Q is the optimal Q-function from Lemma C.2
Now consider for any E S the following sets
(0) (sh 8: (0 as))) 00(sh. a) for all a + a" (sh))
(J)
(2() (0: Qn a'hh)((shh) 2 (sh, a" (sh)) A (*
s
R2(sh) (00m) ya Voolan (sn) 2 Q 6(m)
(sn))
(sh, a" (sn))
for all n 2 1 large enough
2
Furthermore, we define c(sn)=
LAIHR" (NN)))
and
No(sn) = {0: (a7(()))))) 2 c(SA)
c(8h)
We divide the proof into the following Claims:
Claim 1. R(sn) (sk))) n (sN) Ra(a)) is a nice region, i.e.
(i) 000) E R(sn) = ((++1) E R(sn).
(ii) gin+t) (a" (s))))))) 2 T 0(0))
(a (sn))sn)-
Claim 2. (e(sn) n (2h))) n Ra((w) S R(() n R2(8h) n Ra(sk).
Claim 3. For every sh s!H|, there exists a finite-time (s)) 2 1, such that
((mo(sw)) E (c( R2(3n) n Ra(H)) C R1 R2( n Ra(ah)
and thus inf n21
g(n) (a" (a"())))))))
min Igngna(3n)
x plm)
(a*(aa)))))
If all three claims hold true, can finally define no max EsTR no(ss)) such that
g(m) (a" (sn)]sh) min min pim) (a (a")))))s)) 0. Ssn on ESNN
inf min n21
21

---

Published as a conference paper at ICLR 2024
Due to the positiveness of the softmax parametrisation the assertion follows.
Claim 1. We first prove ii Let ((m) E (R(s)) and a o a" (8a). Then 0(++1) E R2((h) by definition of (s))s). To see that B ((++ E R2(s%) note that
Qneints) (sh: a" (8%))
Qh (
(sh: (sh a' (8h))
d(n)
ash, + Qh o(n+1)
as,, - Qh o(m)
0%a0 (sh, a" (sh))
= =hh
Qn
Qh o())
ash, d'
E
p(s' (iss) a" (S h+1 (5')
s'SDE
Σ p(s'|sn, a" a (sn)) oim)
ar(sh
(s')
SSS.N)
2h )()
(sh, a' +
Σ
p(sls8 a² (sw))
h+1 (8') Vh+t (8')
06m11)
s'Stn]
(l)) Ui (sh, Q ah,aa((s)))
A (88))
Q a
2
where the first inequality is due to monotonicity of V last inequality follows from ((m) R2(s)).
(s') in n for every of S(H) and the
Next show ((++1) Ri (sn). Therefore we first show that
Quoem) (sh, a' (8b)) - @na (sh; a) 2 (sn)))
(16)
2
for all a + a²" (sn). This holds true, because
@no(m)
a" Quaan ash,a)
-Qao(n) p(m)
(sh, a (sn)) - ( a" (sh)) + (sn)) - Qrown
(sh: a)
(sh)
+ Q ( (Bn.) (sh, + (sn, a) Qaolaa
(8h, a)
2
A (sh)
+ (sa)
+ Σ
p(s'lsh, (V pr0(n)) (s'))
2
s'ESIM]
A A*(sn) (SR)
IV
The first inequality follows from ((m) E R2(s), second by the definition A A* and the last from mononicity of y= (s') for every and V beeing the limit. Using Lemma A.7 we obtain for any # a" (8h) that
(J((())) 00 a" (8n)) a0(
aJ(O(N))
+ 0 (sn 3x)))) (Q p(m)
(sn,a" (sn)) - Vo a(n)
V7, (sn) 2 n 0(")
(c)s)(O a(m)
(sn, - V/ 17
(sn))
(17)
We divide into cases:
a) n g(m) (a" (sn) (sn) 2 0(0) (alsk),
b) gin) (a" (88)) 0(0) (alss).
22

---

Published as a conference paper at ICLR 2024
In a) the assumption x o (a" (8a))s)))) , (a(ss) (alsa) implies Oi0) (sh, a² (s()) 2 0l0 (sn, Thus,
aJ(((n))
(sx)) = 0(^) (s, a (s))) + ash, a
(0(()))))
2 g(n) a) " 00 (2) (sh, a)
= (s,
which implies n. p(m (a (sW))s)) 2 2 0(nt1) (als)). Moreover, we have
Qh 0l0011 (sh, a" (sh))
Qh olmt)) (sh, a)> (*(a
2 0,
2
Oh 0l441)
(8h a (sn)) - V/A (
o(m41)
(8) a) - 1//-0 1770()41)
(8)) 2 2h
-1,
(sh).
Thus, both together yields
mfni (a())))ss)) sa) (QT (sh, asn))) V/a oln+1)
g((tz)) (alsn) (Qh o(+11)
(s1)) Tt
(sk, a)
(sh)):
which is by Equation 17 equivalent to
aJ(A(++1)) (J(((n+1))
(0(xt1)(s
(8(nt))(sh.a)
Hence, ((++1)& E (1))).
In b) assume now that n. )6()) (a" (s)) < (a(sa)) in this case and rearranging of terms gives
(alsa). As As
E (sn) Equation 17 is also true
aJ(A(N))
aJ(((M))
(0(2) (5n, a (sn))
(0k)) a)
Q o(n) (sh, (1- T (dn()))))))
)(R s(m)
(sh, as())) - Vy oin)
Vi (sh))
+ th (8h, a" (8h))
n (alsn)
+ 2h p())
(sh, 2 (1- exp(0 (1-cxp((0 (sh, a" (sn) - a)) (2+ 0(m)
(s), (ss)) Vi (sn)).
(sh (s)))
(18)
Note next that by g(n) E (sx)) and definition of R1 (8a) we have
g(nt1) (sn, a" (sn)) - ( () (sn. a)
aJ(O(m))
aj(O(l)
= - a" (sh) + 1 a0 (xn, a*x))) - (0000)))0(000mm)m (sh,
2 gl a" (sn)) ((") (sh, a)
and is follows
(1 - exp(o(n+)) (sn, (sn)) ((n+1) a))) S (1 exp(0(m) (sn, a (sn))
g(a) (sh, a)))
1 by assumption b). We already know 0(++1) E R2(sn) and therefore
vxslntt)) h
(sn) 2 Q7 o(m-1) (sh, (sn)) (a)
2. This leads to
Qoalntt
al++1) Vysolnt) (sn) (* Q
Q axa(+)))
(sh,
(sx)) (sh))
(sh, a),
where the last inequality is due Equation 16
Combining everything leads
(1 exp((ln+t)) (s, (s, gln+t)(s,
(8, a))) QT
alnt1)
(sn, a" (sn)) V/
o(nt1)
(sx)
S S (s))a((s))) - Q TTa1111 12)
(sh, a),
which is by Equation 18 eqqivaalent to f(n+1) Rí (sk)-
23

---

Published as a conference paper at ICLR 2024
Now come to Claim
((42)
(a (sh)
exp exp(@(n+11) (s/, a (sh)))
aEA
exp(f(m) (sh: a" (86)) 11 igtn) " ((n))
0,100
Σ exp(((n)( (sh. a) 7) 20(")) (sn.aa) aEA
2J (
exp( (sh, a (8a))) exp poin (exl)
(J(((())
Σ exp(B(n) a)) exp(1) og( (es (eh)) aEA
(J((()))
g(m) (s)())))s)))
where the inequality follows by ((m) E R1 (sa)-
Claim Assume E (N(sh)) n (2(8h) (s())) and divide again in two cases. If a)
(a" max (alsn). then for all a + a" (sx) we have
0J(0)
(s
= Py (sh) (a" (sn)(sn)A ash:)"(sh)) (sh,
2 Py
AJ(0)
a0(sh:a) a)
Where the inequality follows from A as A (sh, Q=' (sh, a² (sn))
Qn" (sn, a) 2 A (an) > 0 by Equation 16 Hence, 0 E Rs(s)).
2
The case 6) where " (a" (sx) (s)) < max n (alsh) is not possible for 0 E Nc((s)). Assume there
aEA
exists + a" (sn) such that = 2a (8n))8)) T < sa)s)). Then
2AH
(sn))s)) + 7 (alsk) c(sr) +1
2c(sh)
(s)
(s)
2
2 A
2 1,
LAH (s())
AAHR
because (s) < HRR by definition and |A|] 2 2. This is contradiction as T" is probability distribution and Claim 2 proven.
Claim 3. By the asymptotic convergence of Theorem C.I
we have that n -000) (a"(s))(sM) +
for Dc. Thus, there exists No(ss)
such that o g(m) (a" (Sn)(sa) 2
d(an) for all
a
No(s)), i.c g(a) Ne(sn) for all n 2 No(ss).
Furthermore, Q Qm)) (sn, (sn))"(s)) (sn; (sn)) for n co there exists N₁ (1h) such that g(n) (st))) for all 2 Nı (sh). Moreover, as Q o(H)
(s,, + Q a" (sh)) V* and Vra(m) (sh) + V for - ao there exists N2(sn) such that g(m) E R2(sh) for all n 2 (sn). We choose (o(ss) = max(No(s)). (s),,
which proves Claim 3.
Theorem 3.2. Under Assumption 3.1 let μ be probability measure such that p(s) 0 for all
E S. let n oF and consider the sequence (0(m)) generated by Algorithm 1 with arbitrary
initialisation 8(0) For > O choose the number of training steps as N = 10H de 12
(S]
Then
it holds that
Vo (n) V.OCN (N) Sc
24

---

Published as a conference paper at ICLR 2024
Proof. We will show that
-'()- - -(0 p)) V/ (1)) - Vo p(n)
vo
101151111
dz
(4) S
cn
then the claim follows immediately from this.
For any B-smooth function f IRd + the descent lemma gives (see Beck 2017 Lemma 5.7)
f(y) S f(x) + Vf(x)² (v- - x) + 3
2 ly x112.
As -f is also 3-smooth we follow
-f(y) - ff(x) (y 2)) + 8
2 lly x=1??
which is equivalent to
f(y) 2 f(x) + Vi -x) ly x11
(19)
Now for gradient ascent updates
Tk+1 = m4 + f(Fx)
we have that
3
[(x-1)) 2 (xx) + V [ (xx+11 xxk)
|
xxx11
2
3a²
= [((x)) + arl (xx\|(
11
||/s(1)))1
2
= (ax) + (a- Ba²
2
follows for the maximum f of f that
f 5f f(xs) - (a-
3a²
2 [f())))
Now assume that there exists such that |V > b(ft f(xxx) for all k 2 0. then
f(*++1) S - f((x) (a-
Ba²
($ f(xx))?
2
We choose the step size a S
3. then
f -f -f( ac² f(xx))
When f" f(x1) S 22 then f³ - f(x()) S atin (see Lemma B.7
2
We apply this our objective p0) with a = = = 5H2R R and b
-1
Note for
VIsI HH
b, that dr'(s) (s) 2 m(s) by definition for any (see also Remark B.3 that
So, we only need to check
('( J(O(0), S 2H 5H
S
d
d
2
This is directly given by the bounded reward assumption and the fact that c < 1 and Then, we yield the claim
>
1.
(' - J(0(m),,)) ,4) < 10H
S
d
2n
25

---

nq. Published as a conference paper at ICLR 2024
Remark B.6. In the discounted setting Mei of 3 is due to their smoothness constant (1->)² a power of 2 is due to the distribution mismatch coefficient and the additional power is due to comparing value functions with a different start distri- bution p instead of μ.. Comparing to our results, directly using p leads also to factor (1 (1-7) 11-7)-3 For the simultaneous PG the smoothness of order H R. leads to H² in the convergence rate, then the distribution mismatch coefficient adds another H² and the additional H comes from the PL-inequality, as the cardinality of the enlarged state space under Assumption 3.1 | [S|H. H. As mentioned the article, it cannot proven that e independent of H. We omitted this depen- dency when compare to the discounted also depend on in the same sense.
Mei et al. (2200) obtain the factor (1-7) where a power
because the model dependent constant there could
Lemma B.7. Let (dn Inet be a positive sequence, such that d S dn qol, for some q > 0 and do < 4. then d, S I. gm
Proof. We use an argument similar to Nesterov
(2013 Thm. 2.1.14). It holds
1
1
qdn 1
+
dn+1
dn
da+1
dn
where the first inequality is due to dividing by d and the second inequality follows by mono- tonicity. Using a telescope-sum argument we obtain
1
1
1
dn
=
do
dx+1
2
do
k=0
Finally,
1
dn
S
S
+ do
q(n
+
1)
qm
B.2 PROOFS OF SECTION 3.2
Lemma B.8. Let h E H. then the objective Jr (1+1)); Ph) from Equation with parameter Br, 2(H R)
5 is smooth in Og
Proof. Note that we can interpret the objective function Jn (On, #(h+1); (4h)) as value function of one-step discounted MDP with y and bounded rewards between [0, IH" - -h). Hence, we
use Yuan al. 2022 Lem 4.4 and 4.8) obtain that the softmax policy thh fulfills the desired
properties with
An 9n
||V log Th (A|s)]
$ [4,1]
Vs E
E Am
1 log oh th (A|s)]12 <
which leads to smoothness constant Br = 2(H - R² for the objective function Jn.
Lemma B.9. It holds that
(On, mit Pn)ll2 2 min n (c])))) - Jn(0n, ((++ Mb)).
SES,
V (T (14)), because the tabular sofumax parametrisation can approximate any deterministic policy arbitrarily well. Using
Proof. First note that by the definition of nH, we have J [++ mn)
CChossin the learning rate (1 - 7)) //8 leads to the (1 11-7)-3 factor the convergence rate. Using recent results in (Yuan et al. 2022 Lem 4) one can improve the smoothness constant for discounted MDPs. Still, the global convergence result in Agarwal et al. 2022 Thm 5) holds only for learning rate (1 7)3 /8 and hence does lead direct improvement in the convergence
26

---

Published as a conference paper at ICLR 2024
the performance difference lemma in the dynamic setting from Corollary A.4 and the derivative of the objective given in Lemma A.8 we obtain
JJ (O,, #(++1), (4h
00,
OJ ((++1); 00)
Σ
(s)
sESA
JJh(On ((++)): 55) 2
Σ
Σ
Σ (s())
00n(s',a')
8'ESs d'EA,
RESh
(Jn(0n,a(u+1))) 6.)
(n(
00n(s, (f))
SES
Σ (s)
(s)(s))ss
2 (m++))) (s)))
SES,
Σ (s) (+))b) (T (T( 0.) - (On, a(1+1),8))) sES.
min
n Th (s)(s) (J (T(+(+1))))) - (Oh, (10+)) pn))
sES,
The first inequality is due the non-negativity of all other terms, and we just drop them.
Lemma B.10. Let μh be probability measure such that (n((s) for all Sn and let 0 Th I 2(H-h) Consider the sequence (e(")) generated by Algorithm for arbitrary 0 E Rdh
and i. Then, Cr. cx(" inf, min 2!!")) (at 0.
The idea of the proof is based on Mei et al. 2020 Lemma 5) for bandits and extended to the contextual bandit case.
Proof. Throughout the proof we abuse notation as follows:
As consider fixed time point h will only write 0, instead of g0
We denote the objective function by (0) instead of Ja (0, a(,+1)) ph) for fixed policy ă and start distribution (4n- Furthermore, we will just write Jř instead of JH (*(+1))) Mh).
We will write (0) for the objective function which starts almost surly in Sn, i.c. (0) Jn (0, ((44)) 6.).
First note that
(On) Σ Thh (3.s))
where Q7, (s, a) is independent of 0. We will drop the subscript # in Qy for the rest of the proof and define for all E Sn.
A (s) = (s,
max Qu(s, 0, and (s))((s
min A (s)s) >
sES,
Consider the following sets
(s) {0: (h),(0)
00(s, (s)) > (Jh,((0)
Va + (s))
00(s.
R3 (0 7 (s) > >aass) # af (s))
(s)
Na(s) (0: ( (s(s) +1
27

---

Published as a conference paper at ICLR 2024
for (s) Al(H-)) and (s) Qu(s,a"(s)) maXaşe Qn(s.a). Then consider the (x)
following Claims:
1. 0n E (+) = Out1 E (x),
2. If 8n E (s), then x²n 1 (s)ls) xd (a)((()))
3. (s)s) _ (s) _ (s).
Claim 1. Bn E (s) and a & 0% (s). Using the derivative of the value function we obtain
(0,) (0n)
00 (s)) al(s,a)
(20)
+ T"" (a (s) (Q) (s)) (On) 2 = (a(o)(( - (n.))
We divide into two cases:
a) x Rm (z)(s) 2 x (als),
b) x (a 2m (a|s).
In a) the assumption T (aj (s)[s} 2 - (als) implies (n (s)) 2 (n a). Thus, (O,)
0n+1(s, (s)) = Bn (s)) (s) 00 (s, (s))
(O,)
2 (, a) + mm (s)
(s,
(s,
which implies n u-+ (s)(s) 2 7 p (a|s). By the optimality of oj (s) we follow
1n (s))s Qn o (s))
8 (als) (als)(Q((ssa) (fn)(), Jh. (fn+()))))
at
which is by Equation 20 equivalent to
(Jh,((aa11)
00 00 (3)
00n+1 (8,
Hence, pnt1 E (s). In b) assume now that Th (aj (s)]s) < (als). As 0n (s) Equation 20 is also true this case and rearranging of terms gives
(Jm.)(Om (On)
00, (0,(5,07(3)) (8,
(a)(())))))) (()(), (o,)
(n(s, (s)) - Qn(s,a) 2 (1 101221111 (9-(s(s)
- an) 2 (1 - cxp(O (s)))) - (s(s (((ss,))(Qn(ss))()))) Jn. (6n)).
(21)
Note next that by ((n) E (s) and definition of (s) we have
0 (s, (s,
0 (s)) mn (s) (Jn,
(s, (s) 0Jh.c(On) 00,
00, (s))
2 20,( as)
and is follows (1 - exp(On+ (s)) 0 a))) S (1 - exp(O. (s)) On (s, <
by assumption 6). By the ascent lemma for smooth functions we get monotonicity in the objective function,
()(s,47(5) Jh. Qn(ss (O.))
28

---

Published as a conference paper at ICLR 2024
where the last inequality is due to the definition of (s)... Combining everything leads to
(1 (x n+ a))) Qu(s,a)(s) (nn.))))))n.(((tt)))
$ - exp(e(((((s)) 0n a)) (x((, - (0n)
$ (s) - Qu
which is by Equation 21 equivalent to 8 (s))).
Claim 2. If nn E (s), then
p (a)()))))
(1,00+)(,,0((5))
Σ exp(0nt1(s,0) aEd
exp(On (s)) + (s) (a,
(O...
Σ ( mm) (s,a) aeA.
DJo. (0.)
exp(On(s, 07 (x))) (2,07,7770
(....10..)
Σ exp a)) (xp())))exphh((())) 8. (0.)) AEA.
= = (a)((s)ss) s).
where the inequality follows by 0, E R2 (s).
Claim 3. 6n E (s), then by the optimality of a" (s),
en (G,) 2 a as)
(, (s)) Jn.. x (cbb)((((ss))) (n,)
(22)
(B,)
(23)
a)) (s)) Hence, On E (s). On the other hand, let On E Na)s), then assume there exists a # (s) such that T² (s))sss) (a)s). Then
<
- -
T (s)sss)s)++
2c(s)
(7(0))
2 || - h) A > 1, 2 2
(s)
c(s) +1
A[
87(0))
because (s) (H R)R by definition and [ 2 2.
This is contradiction as x is
probability distribution and Claim 3 is proven.
To follow the claim of the lemma from the claims 1 to 3, we need asymptotic convergence to the global optimum. This is given by Agarwal al. 22021 Theorem 5), since we can interpret the objective Jn as a one-step MDP with y = O. Then, assuring that the step size is smaller than one over the smoothness parameter is enough to use the same proof as provided in Agarwal al. (202I)
So, there exists time to such that 0 E (s) for all E S. Finally,
inf min x (s)ss)
min min "= (s)(s))s) > O. 05
Proposition 3.3. For fixed h E H. let sh be probability measure such that (n((s) > 0 for all 8 E Sy, and let 0 < Th S 2H-1 Let (%)) E Rdh be an initialisation such that the initial policy is uniform distribution, then Cy [ 0.
29

---

Published as a conference paper at ICLR 2024
Proof. If we initialise uniformly, then do R2 for all S, from the proof of the previous
Lemma B.10 Therefore, 8 E Rs) ) for all n 2 and from Claim 2 we have
Ch inf min Th (s)ss) min 7 (a" (s)[s) n
[A
Remark B.11. Let shortly discuss why the constant C₁ in the dynamic plicitly, but e in the simultaneous case can not. In the dynamic case, the future policy is fixed and the optimal action a" (s) is chosen with respect to the best policy , dependent on the fixed future policy (hh+1)- This leads to monotone improvements in epoch h (due to smoothness), and so the probability choose the best action increases over the training steps. In the simultaneous approach the future policy changes in ever training step, as changes after every update. Smoothness just guarantees improvement in the value function, i.e. improvement in expectation over the time hori- zon. As π is the final best policy, we have to bound s T (a" (sx))s)) for every in the enlarged state space. This the cannot be followed from improvement in expectation.
be bound ex-
Lemma 3.4. For fixed H. let μh be a probability measure such that (n((s) 0 for all E Sh. let nh = -リー and consider the sequence (o(.)) generated by Algorithm 2 with arbitrary
initialisation %% and ft. For choose the number of training steps Nn. 4 a()-") Then it holds that
(K ( (um) ( ma--)) (wn) Se
Moreover, if ( initialises the uniform distribution the constants Op can be replaced by J
Proof. First, note that V (mj 12) (pa) (T(4))) pa) and V/ alt)
(n(( (m) a(n-1), Hh) by definition of Jn. and choice of mÿ. We will proof
(f(+)))) ( #(b+1); mn) 4(H h)R
G.. n
Then the claim follows directly from this.
We use the same arguments as in the proof of Theorem Jn (O,, (4)) Thus, only need to assure, that
3.2 for our objective function
JR (1 Ph) Ja (0 (1tD),
1
ab? for q 2
with = 1/ and = Ch. It holds that
JA (T - Jn %0 10) #
S (H - hh)Rt
<
4(H R)
28p
ch
ch 9
2
and the claim follows as in the proof of Theorem
3.2
Theorem 3.5. For all h E H. let Us be probability measures such that (n((s) > for all s E Sp
let Th byR For e >> 0 choose the number of training steps N₁. 4[H 4(H-h)H
loo
d/e
1h.
Then for the final policy from Algorithm # (7
(N ), it holds for all E So that n
(z) vo SE) Se.
If ()) initialises the uniform distribution the constants ch can be replaced by TAT
Proof. First note that by our choice of the future policy ** we have
(0 (N.)
,,(441), = V (s).
(24)
30

---

Published as a conference paper at ICLR 2024
By Lemma 3.4 obtain
4(H -1)
JR (((+)))) - Jo #(b-1): S
N/
For every E Sh,
(N)) JR (T( 5.) Jn(Op .((h+)):6)) Σ pn(s') 5o(5")
Jh (a(x+1)): (0, IT( 86)
un (sn)
s'ESk
(Ji (J((((())))
[AA 1cc
4(H R)
1
c Nb.
(25)
where
1 Ph
max,6s.
1 > 0 by assumption. As No 4(H -A)HA pn(s)
of
1
it holds that
(T 8.) - Jn A(h+1),, 6.) S
E
(26)
H
for every E Sh. For 11 it follows directly by Equation 24 and the specialty of the last time point that for all s SH-1,
(s) - (6.) (0 .80) - H
Note that the last epoch is independent सt. Assume now that for all 8 E Sh.
Vi(() V/ (s) S (H - h) Then it holds for all s E Sh-1 that,
(27)
H
Jh (#ta)) 8,) max aeA.
a()
E p(5'1s, p(s()s,
Σ p(s'ls, v(((s))
S'ES
s'ES,
E(Hl
r(8,0)) + Σ p(8 p(d(s,,)
max aEA.
H
S'ES
e(H - h)
= VV
(s)
H
(28)
by the Bellman expectation equation for finite-time MDPs (Puterman (005)). We close the back- ward induction using Equation 24 such that for all E Sh
V V (s) = V (s) J (T 8,) + Jr (#()). 5,) V (s)
eHH h1)
+ H
(29)
H
H (h
1))
H
Finally, it holds for h 0 and all So that
(s) - (5) Sc.
Sc
C ASYMPTOTIC CONVERGENCE FOR SIMULTANROUS PG
In this section we will proof asymptotic convergence of simultaneous softmax PG towards the global optimum. Therefore, we use the extended notation of the state value, state-action value and advan- tage function introduced in Remark A.2 For the rest of the section we will write 9, = g(*) to save notation.
31

---

Published as a conference paper at ICLR 2024
Theorem C.1. Let μ be a probability measure such that p(s) 0 for all S and let 0 n -
SH Consider the sequence (0(T)) generated by Algorithm 1 for arbitrary g(0) E R2, dr, Then,
for all 8y E S(H) we have Va (sh) - (sn) as n - co. Especially we have Vo pln)
(s) as oo for all E Sg.
Before proof this result have proof row of lemmata. The outline follows the proof of
Agarwal et al. 2021, Theorem 5). For the rest of this section we will just write J(0) or J instead
of JU, p)) (()).
Lemma C.2 (Monotonicity). If the learning rate satisfies < < S HRS S
HRR 2 (2-
then va (sp) 2 V*" (sh) and Qa (sh, a) 2 QT"" (sh, a) for all 8h. S(H) and all a E A.
Furthermore, there exist limits (s) and (s) such that
lim V="" (s) = V (s) x0.
lim Q² (5, = (s, <0.
(s) for each state S (in the not enlarged state space) and each epoch h. Then by the bounded reward assumption there exists (s) such that vie" (s) ve for Q-functions from the relation
Proof. We will show that " (s) I V/ V
If this holds true the mononicity and convergence of the
O (s,a) = + ppss's
E'ES
with VH= O.
In order to show the claim we first see from the performance difference lemma, that
H-1
Vh
V nn+1
(s)
V/ Pn
(s)
A th
(St, An)]
t=h
Σ
Ps
(st)
Σ 20 7a= (st)
S
aEA
where P5,h 2 (st)
= HH-1 ppn n+4 Sn== (St = si) the state visitation measure from epoch to H
on the enlarged state space S(H1, Note that prrh (si) = for I < h, as we cannot visit states from previous epochs.
We will prove that EneA n Rn 1 (a(sa) (s), a) 2 EnEa (als)) AAT (sn. a), for any sn E S(H], Then the fact that ELEA Th= (als) TT (s leads to the desired result.
Therefore, we consider the function
Fs,, (0%%)
Σ
π 8hh (c)sn)c(sn,.) 8h E S(H)
aEA
for 8% (0(sh, a))A RIAI,
We will set c(s), a) A (sh, a). but for 8n, fix, i.e. the following derivatives with respect to 8% of F are independent of A=" From Agarwal Lemma C.2 we know that
oF,, (0th)
T p(m) (als))AA
(sh,
(30)
(0(s a) 10th
Furthermore, Fs, (9,..) is 5 smooth for every sn by Lemma D.1 in Agarwal and the bounded reward assumption. Considering our gradient ascent updates from simultaneous training get
0V*"" (n)
0nti(sh, (nh a) +
(31)
00 (s),a)
0n(sh, a) + npp (sn) On (alsh)A** (sh. a)
(32)
=n(shha) a) + npア (sn) 0F s, (0m,)
(33)
00, (Sh, a) 0%
32

---

Published as a conference paper at ICLR 2024
As np,. (sh) n. ". (sh) and di (sh) probability measure that np, (sh) 5HM by our choice of 7) S ~ Then the descent lemma for the 5H R -moooh function Fs,. gives the desired inequality
Σ acA
π Anta (a(s)) (sh, 2 Σ
(a((ss))) (sh,
aEA
Remark C.3. We want to point out that the proof of Lemma C.2 is crucial for the choice of the step size in the convergence analysis of the simultaneous PG algorithm. As we can only use the descent lemma for a step size < 7 S 5 we can only achieve asymptotic convergence towards global minima under this assumption. Hence, we also need this step size requirement in the convergence analysis.
We introduce the following definitions:
( (snga)
min
where (sh, u) Q (sh, a) (sa)...
We define the sets for each E S(H]:
T0th {a A Q (000 (sn = V (sn)),
1 {a E Q (sh. > V (sh)),
1 {a E A - (sh < V (s:))-
We aim to prove that 4 is empty set, then V (s:) V (st) the optimal value function (epoch wise true).
Lemma C.4. There exists a time N₂ > 0 such that for all n > N1, and 8n. E S(H), we have
A
A
(0n a) < Jorael A (sh. a) > for a 1t.
Proof. Fix Sy E SlR arbitrarily. As -T (sn) + (s)) for and S is finite, we have that there exists N1 > 0 such that for all Ni and E siM!
A
v (sk) > (s))
4
follows all n > N1. 8n E S(N) and a E 1 by the definition of A:
A
A
(Sh, a) = -Q== (8h, y="" (sn) S $ (sh, a) - V (8n)
+
<
4
4
Similarly, for all n N1. 8n SPA] and E 1 we obtain from monotonicity Lemma C.2 definition of A,
and the
1hr (8, a) = = a) - paaa (sA) 2 (8,
100 (8
A
A
4
4
4
[sn.aa 0 as + 00 for all 8h E SlH, A.- This implies that for E Thh U 1th nt (alsk) + O and that E Eaes. B (alsn) + 1 for + co.
Lemma C.5. It holds that aJ(0.).
Proof. From (Beck 2017 Theorem 10.15) we deduce for any 3-smooth function f Rdd + R. that |/ If [= 0 for k + oo, if k+1 x (a*() when 1j 3. By Lemma B. J(.) is
H2 Rd (2 A -mooth. It follows by choice of < TH that [J(0a) + 0 as
(8,(a)))
33

---

Published as a conference paper at ICLR 2024
for all Sn s(H), E Ag. Now remember the derivative of the softmax parametrisation in the stationary case
OJ(On)
(5h(sh.0 a) P/ (al"())
a),
TH (sh) 0 by and by Lemma C.4 11 a)l for all N1 and I U As PH assumption on jl and the positivity of the softmax parametrisation. It follows that T (als) 0 for
n + oo for all a E 1 U from (J((0.) ()). + 0 as n + 0o.
The last claim, Emery x (alan) + 1 for n + co, follows immediately from ExEA, - (alsn) = 1 by:
lim 10 720
Σ aE
π (alsn)
lim n0000
Σ a
π nn
(alsa) Σ
<a<((())))
OER
E
lim π Pn (alss)
uhrh" 22000
ot aE
Lemma C.6. For & 1+,, the sequence (0,, (8h, a))=zo is strictly increasing for n > N₁ and for E Thh the sequence (0x(sn,a) n2) is strictly decreasing for n >> N1.
Proof. With Lemma C.4 we know that for >> Ni
AlT (Sho a) > 0 for E 1 (sh, a) <0 a 1th
and by the derivative of the value function
(0()))
Pj (sn) (als)) (sh. a).
(0, a)
As Pi (sn) 0 by the assumption u(s)) 0 and the positivity of the softmax parametrisation, have for all n > Ni
(J((m)) 0 for E 1hh
aJ(On)
0 for 1
00,(sh, a)
00, a)
This implies for 1
0 ( a) (sh, a) aJ((n) 0,
50(sn. a)
Le. (0,(sn, m2) is strictly increasing for N, and similar for 1sh
aJ(O.))
0 (nti a) 0nh a) 17 30, (sh,
i.e. (0n( m)) is strictly decreasing for Ni. Lemma C.7. For all 8s E S(H) where 1 + 0, we have that
max 0n a) + o and min (Sn, a) + -00 for n + 0o. aei,
aEA
Proof. By assumption 1th + there exists a_ I and by Lemma C.5 we have T0 0, as n + co. Hence, by softmax parametrisation this is equivalent to
exp(e, (sh, a+)) + O, for n - oc.
Σ exp(On.ss, a)) REA
34

---

Published as a conference paper at ICLR 2024
Using Lemma C.6 i.e. (sh 0+) is strietly increasing for N1, we imply that (xp(66 a+))
strictly increasing for n > N1. This implies that
Σ
exp(On a)) - o0, for n - co.
aEA
Again by Lemma C.5
we know that
Σ (a/s)) + 1, for - oc, a
Le. by definition
Σ exp(6n(sh..0) a))
(sh, + 1, for + 00.
d'EA
As Σ d'EA
a')) + oo it follows that
Σ
exp(On(8h,a)) + 00, for +
"
implying
max 6 (1 a) o0, for - aEl
For the second claim it holds that
(f.))
Σ acA
"r (sh) E ThH (a(s) (sh - 1n (sh))
(0n()): a)
aeA
Pp (sn) 100 (sh, a)] - (/t"((sn) (sn)
pp"1 =Pp (sh)(V (sn) V/ (sn)
O.
By induction, we obtain EoEA On(on;a) a) = EnEA 0o(on, a) == c for every n > and hence
min on (mh a) aEA
<
Σ
nn a)) - max On (8h, a) = max
(n a) + c.
aed
aEA
aEA
Since max 0n1 (8h, a) min (sp, a) xc for + Do.
-
00,
because max On (n a)
7 oo, we conclude
L
Lemma C.8. Suppose a. E 1 If there exists a E 10" such that for some n > Ni, on (alas) S Th (a+1s)), then for all m >> it holds that T (a|sk) S 7
Proof. Suppose there exists a E I5 such that for an n > O, on (alsn) S Thn (a+1sn) We show that On+i (alsa) +n+i (s_1 then the claim follows by induction. We have
(O,)
PH (s
Pn (sh. a) - V/ (5h))
(0,,
P (sn)=""(ar (sn) (sh, a+) Vi-"0 (sn))
(0m)
(0, a+)
where the inequality follows with
A
Q (sh a4) 2 Q80
(sh, a+)
A
Q (8h, a) +A
Q4 (sh, a).
35

---

Published as a conference paper at ICLR 2024
The first inequaility is due to Lemma by assumption we have n (alsh) I n (a=1(14))) and thus 0n (s, a) S 0n (8h, It follows
C.4 and the second by the definition of A and Iga Now
(8n)
(J((o.) 0n+1 a+).
0n+1(sh, a) (sh 0) + (00((sh.0) S (sh a+) + 17 00, a+)
Now define for every at + the set
1i (a+) - {a E (a+1ss))))))) S
x* (alss) for all / 0}
and denote its complement in T as B (a+) = 10"h Bi (a+).
Lemma C.9. Suppose + + 0. For all a+ E I we have that B (a+) F 0 and
E
(a<(a(s)) +, as
aE (a+)
This implies:
On 0n(sh, a) - 20, for -
max aEBi (a+)
Proof. Let a++ E 1thh and consider E BBth (a+). Then by definition of BB (a+) there exists n' > N1 such that nh. (a+1s)) 2 The (als)). Hence, by Lemma C.8 for all 2 n' we have xd= (a+(ss)) 2 >= (al(s)))). As Th (a+ |sh
- for n - pc. We obtain n R (a|ss) - 0 for n - oo, co, have that 8n (a 1. as + co. The second claim follows from
for all E (a+). Since by Lemma C.5 Eeerç T (alsp)
for
BØ"h (a+) * 0 and that EoeB (a_) (a_)
this as in Lemma C.7
Lemma C.10. Consider sh E S x H such that 1 + 0. Then, for any at E 17, there exists Na. such that for all n > Na. we have
9 (a+ (n) > T (a(sk) for all a B (a+).
Proof. For every a E B (a+) exists time such that
-n (a+ (8n) > n en (alsa) for all a E B (a+)
for all n > na by definition. Set Na+ = a (a+) and the proof is completed.
Lemma C.11. Assume again 1 + Ó. For all actions a E Ih", we have that 6, (Sh, a) is bounded from below as cc. And for all a Ish, have that 0n(Sh, a) -00
co.
Proof. The first claim follows directly with Lemma C.6 as (sh; a) is strictly increasing for all a E 1hh n > Ni, and thus for all n > Nj we have On (sh, a) 2 ON, (Sh, a). Now suppose Tth then by Lemma C.6 we have that (s(s,, a) is strictly decreasing for for all n > N₁. By Lemma C.7
Ni. Assume
there exists b such that lim (sp, a) = b, then 0₂ (sh, a)
n-
there exists an action a' E A such that (8p. a') - -oo for n - co. Consider > 0 such that
ON (sh, d') 2 b 8. Define for all n N1
T(n) max (K= E (N1, (a(nnaaa) 2 b 8).
Define also
T(m) {T(M) n' <n: (J(ww)
00, (Sh, a') $0).
36

---

Published as a conference paper at ICLR 2024
as the set of all indices r' in (r(n), n), where (5k, d') is decreasing. Next define Z, a,(0,,)) En'TT 80 (s,.a"" then holds that
OJ(On')
7n
Σ
00,, (5h,
n' (M)()
(J()..)
20,t (sh.(sh.00) d')
nn=7())+1
OJ(nn))
0J aJ(0)(n))
+
00n a')
(0+(n) (8h,
n'=7(1)
By Lemma A.7 and the bounded reward assumption we have (J(()(n) (m) (sh: a') D7 ((1)
(SH) TTw (a'(s))|Ap Prow a'), S H²
Hence,
a5(wn)
Zn <
+ 1²
00nr (5h, a')
n' = (m))
17 (0 a') - (0r(n)(Sh, a')) H²R
5 (On(on, a') - -b+ -b+ H²
Then (m.(h,, -00 for + implies that Zn -0 for - co. As we chose a E 1
holds that (sn, a)l 2 for n > Ni with Lemma C.4 and so for all n' E (m))
(.T(2.))
n' (al 8n A a))
aJ(00.))
(a' sn A (sn,
(an.aa)
(alsh))
Tee (a'(sn) 4HR
A
exp(On (sh; a) On (sn d'))
AHR
A
2 exp(b (b 8)) AHR
= exp(0) 4HR
where we used in the last inequality that Ow a') S b- â for all n' > r()) and 0g (sh, a) > b for all n' > N1. By the definition of (n)) these inequalities holds especially for all E (()) Using this we can imply that for all n > N1 with ((m) #
aJ(e,.))
0N, (Sh, a) - (n(s =
77
N'=N++1 10n.(sh. a)
aJ(On.)
00,, (Sh, a)
(m)
OJ(0mc) 00 a²)
< cxp(6)
4HR n'ET(a)
exp(()
4HR* Zm,
37

---

Published as a conference paper at ICLR 2024
where the first inequality holds because 8, (st, a) is strictly decreasing for n' N1. ie. 0J(0.)) for all n' (Ni +N++L. 1........ 1}. . In the second inequality we used
00 (an.a)
8J(0,))
A
exp(0)
(J((),))
4HR
08,, (sh,a')
Note that ()
( (s).a) < and aJ(0.,,)
(0,r("),a") <O E T(x) that the sign of the inequality reverses.
Finally, we deduce from Zn - -00 that (,, a) + so for n - co, which is contradiction to
(n,(5, a) strictly decreasing for all n > Ni.
Lemma C.12. Consider s E S(iH such that I + D. Then for any a+ E I it holds that
Σ
On(sn, a) + 0o, for n + 00.
af REB (a+)
Proof. Let a+ E 1 and B (a+). Then by definition of B (a+) have n 8d (a(4+1))) S T (alsn)
for all > and hence by softmax parametrisation 0n (sh: a4) 3 (nh a) for all n By Lemma C.11 we have that On (sn, a4) and thus also On (5 a) is bounded from below for Together with
max (xh a) 00, for n faE (a+)}
by Lemma C.9 we deduce the claim.
Finally, we are ready to prove the asymptotic convergence of simultaneous PG with tabular softmax parametrisation.
Proof of Theorem C.1 We have show that 1 0 for all 8h S(M), So assume there exists 8/ E ((H) such that 1 + and let a+ E 1 Then by Lemma C.12 we have
Σ
(sh, a) + 0o, for n 00.
(34)
BE (a1)
For any a E 1 we have by Lemma C.Il that
- (alsh) no (a+11p))
(sp(0n(sp..)) a)
(sh ) 0, > oc.
boundedd from below
Hence, there exists N₂ > N1 such that for all > N2
0n (alsk)
A
0n (a+ 188)
H
which leads for n > N2 to
HR Σ (a(sk) aE
A
On (a+1sa).
(35)
16
Note that if Tth we can just ignore this sum later on.
Next consider D (a+) C 1 By the definition of 1 we have that 4 (sh,
A (sh, a) = for n - co. By Lemma C.10 we have for > No.
n on (144)))
On (alsk)
38

---

Published as a conference paper at ICLR 2024
Thus, there exists N₂ > max(N2, Na, } such that for all Ns
n A
14% a)]
79 (a(())))) 16|A
This implies
A
Σ
n =a (sn, a)] 70 (a+
16
aE Bg (a+)
and so
Sh
Σ
(a) (s,, < <T00(a+1s))
(36)
16
16
ae (a+)
for all n > N3. We can conclude again for n > N3.
Σ R (a) (sh.
acA
E
T ( (sh,
E (a (sh.
aE (a1)
aER (a1)
Σ
(alsh)A ( (sh) + Σ nh ( (sh,
AETT
Σ
(a((a)()) (sn, O0 (a+
A
+ pn
(a+1sh)
A
HR Σ
x (alss)
16
4
aEI %
Σ
T" (a((s)))))))) (sp, a) - ~-"0 T (a+1s))
+ π
pn
(a+1s)
π
pn (a+1sh)
16
4
16
B (a+)
Σ
T" (a)ss)A4 (sh. a)
B (a4)
where we used Equation Equation 36 and Lemma C.4 in the first inequality and Equation Equa-
tion 35 in the second inequality. Finally, by our assumption and Equation Equation 34 for Na.
+00
Σ
(0)(s,a)= (sn((nn))) a))
ag aEB (a+)
O)w(w)
Σ
2 (Sh,a)
n'= B (a+)
(sh)
Σ
n (a (sn,a),
n'=Na
BEB (a+)
which contradicts EeeB 2 (als) (s. < for all n N3.
D PROOFS OF SECTION
D.1 SIMULTANEOUS APPROACH
We first proof that the gradient estimator unbiased and has bounded variance.
Lemma D.1. Consider the estimator from Equation For any K holds that
E
v K (0, p)] V))
and
ET [1 (
(0, n1) VJ
1)11 3H max R
114
E
K
K
39

---

Published as a conference paper at ICLR 2024
Proof. By the definition of J we have
A
k
(0, [)]
js
K
V log x (A))))))
K
H
E
log((T (An
H B
H-1
Vlog(T (A,))))
Σ
r(Sk As)
R=h
where we used that we consider independent samples for = l,..., K. From the proof of the policy gradient Theorem, we obtain that
( (0.N))
For the second claim we first see that
|J(00 = Σ Σ(H (s))((
(als) (mls) (s))))))
BESiNI aEd
< R" Σ
Σ
(1 (s)m)
SESTH aEA
< (R)?
because (-ls) I 1, d (s) S 1 and both are probability distributions.
Next we have that
H log(T (T (An (A)
Ex 14 [|| (0,
w)]l
S H R E
log(T (Ar (A,|)))]]] [sa)i]
R²
where the last inequality follows with by Yuan et al. (0022
Lem 4.8) and Jensen's incquality.
Thus,
E7 & J (0, 1)
EE""
<
K
K Ex="" |112:/0000-220000/0/////01101110
<
H + (1*) +
< K
Define 3 max RR" 13 > HR + (R*)2 (R*) proves the claim.
Recall the stochastic PG updates for training the softmax parameter from Equation
( ffm) + 1) JK (0(n) 14).
In the following denote by (0(m)) n20 the deterministic sequence generated by Algorithm such that the initial parameter agree, ((0) = g(0), and the step size is the same for both processes. The natural filtration of (0(m) )n20 is denoted by (F(")) Recall that for the deterministic scheme could assure inf, min ESIN| ? (a* (sx) (8))) is bounded away from by Lemma B.5
40

---

Published as a conference paper at ICLR 2024
This cannot be guaranteed for the stochastic trajectory. The idea of the convergence analysis for stochastic softmax PG is now to define the following stopping time
T == min (n 2 0: |10(x) 0 2 7
This means, T is the first time when the stochastic process (0!")) is too far away from the PG trajectory (0(m))n2-- Hence, all challenges encountered in the deterministic case transfer to the stochastic context, indicating that the model dependent constant e naturally appears the error bounds of the stochastic case. We emphasise that is stopping time with respect the filtration (FF*) 220 by construction.
First, consider the event (n S r), i.e. |000) 06 S ch Then, it follows from the V2-Lipschitz continuity of + n (a" (s)ls) that minogagr min.es nt 8(m)) (a" (s)]8) 2 0.
Lemma D.2. The softmax policy x² (als) is 22-Lipschitz with respect to 0 E Rdd for every 8, a.
Proof.
The derivative of the softmax function is
(al() 18'=s 1a'=a exp(O(s, a)) (Eee exp(O(s, exp(0(s, exp(O(s,
00(s',a')
(EeEA, ex)(
=1, la T" ='(als)
Therefore,
(a|s)]l]
(al=a T (als))
aEA.
7 (nlls)2-2 (a
Σ [ddd aEA.
$ V2.
Lemma D.3. Let be a probability measure such that p(s) > 0 for all s E and con- sider the sequence (0(m) n20 generated by Equation Then, it holds almost surely that minosngr min T F(n) (a)(s))s) & is strictly positive.
Proof. For every n S T we obtain by the /2-Lipschitz continuity in Lemma D.2 that
n g(m)
2 π ((m) (a" (s)1s)
2 n g6m) (a (s))s) - -17 0(") (a" (s)(s) g(.) (s))ss
(s)ss) v2(10(m) g(n)112
holds almost surely. The claim follows directly.
This allows us to the weak PL-inequality of Lemma B.2 to derive convergence rate on the event (n I T in the following sense:
Lemma D.4. Under Assumption 3.1 let μ be a probability measure such that p(s) > 0frrr all S
and consider the sequence (0(m)) Izzo generated by Equation 8 Suppose that
the batch size ((n) è² max RR' .11 2v8
n is increasing for fix N 2 1,
N3/2|S
the step size 1) 5H Rt VN"
41

---

Published as a conference paper at ICLR 2024
Then,
20
([(J*(n) - J(Omm) (u)) (nsr))
c²
(1
2VN nn
Proof.
Throughout the proof we drop the μ in and J
First, we deduce from the 3-smoothness of J, as in the proof of Theorem 3.2 that almost surely
(0(a+1) (((())))))(()))))))))))))))))))) J(olatl)) 2 J((()) + (VJ(O())))
((m))
3 (0(nt)) - x(a) 12
2
We continue with
J(O(n+!)) 2 ((0()) + ( ((aaO) (V)J =
- ..g a JK (0(0))11
= =]((m)) + 1u (alglra ( + V (())) x ( (0(m) - vJ(((N))
(p())) -J]((()) + |J(
2
Thus,
J(gln+1)) 2 [(((m), (n) (n- B17 ) + +1 B (V Φn)
3n² 1l
2
where on = JKK (p(n)) V(((x))). Next we take the conditional expectation on Fr. Then by
Lemma D.I we obtain
31p [( 2 I(Oin)) + (1 -1 2 (J
33125
2K,
Subtracting this equation form J and taking the expectation under the event {n + 1 S r) results
in:
E (J+ 11
E (J - -((( Fr
1 1[ntis7)
s E (J+ E(J(((nt)))
( (nST)
(1- B18²
3175
< E (J* - (((0))) ))1 (mST)
13 [ (ns)))
+ 2K,
B172
SB (J -((()))))))))))))) ))1 (
17(1
E (
121 (mst)
+
2/N
2Kn
where we used that (n + S mh (m. S <nj is Fe-measurable and that 1 [[nt15t)) S ((ngt)
a.s. With the PL-type inequality Lemma B.2 and millognrr min,es nt ((m) (a (s)]s) 2 by
Lemma D.3 we have
E B( ((((n+)))) (
s B
(J' <B([J=
-(((m)) [n5=}]
-1/(1
1
E (J - ((O (mST)
12
+ 2k
3r12
2/N
|
d
SE([J- 1(01))))
11(1
1
c²
d
E
(J+ 1(
(n
2 311E
2/N
H
/
8
2K,
42

---

Published as a conference paper at ICLR 2024
where used in the last inequality that under Assumption 3.1 Remark B.3 For dn := E -J= - (( (n(s))
have di, (s)
2 म (ss) (see
we obtain the recursive inequality
BnZE
dn+1 S dn n(1 2/N H
dh,
2Kn
We define := nn1
and B By's
0 such that
2/X 5
B
d S d wdn)
K
Note that w > 0 by the assumption u(s) > O for all E S. Then by our choice of K₂ it holds that
W Bn 9 g B(1
2/7
)
d= 1
n²
|
9 e (1 2/ 15
d=
n
9 c
max f R 1)
2VN
1
-2
n
S Kn-
VNISHH 8
N3/2
Furthermore, we have for rj
that
5H
H
H R*
3w
3r/(1
1
2/N
VN
2VN
We obtain that
4
di S HR <
3w
3
1
because e < 1.
2 and J (1 2VN
for all N 2 1.
Suppose the induction assumption dn I
4 holds true. First, recall the recursive inequality Jwn
B
da+1 S dn wdh Kn
The function f(x) wxx is monotonically increasing in [0, 2. and by induction assumption dn I Aun I Thus,
B
dn+1 S dr wdd +
Kg
16
B
+
3wn
9wn
16
4B
+
3wn
9wn
9w Bn?
12
3mm
9wn
3w m
n
3wn
by the choice of K, 2 9 wwB. We deduce the claim
4
20|SH 11 R²
d, S
3wn
)
VN
2/N
43

---

Published as a conference paper at ICLR 2024
Secondly, consider the complementary event {r I n). We can bound the probability of this event by for a large enough batch size K. The proof is inspired by a similar result obtained by Ding et al. [2022] Lem. 6.3) for discounted MDPs.
Lemma D.5. Let μa be probability measure such that μuss 0 for all S and consider the sequence (n20) generated by Equation For any 5 O, suppose that
the batch size K 10 max [2" n)
the step size 17 VISHER
Then we have P(r S 5n) < 8.
Proof. By the definition of r we have
P(r S n) = ( max
Ch ostsn
|10(0)
|(0)|
>
4
so we first study ||00.)
|.
We emphasise that
Ding et al.
2022
Lemma 6.3) established
similar recursive inequality.
|1000 1=
A -
n (0W)) x))l
7 V k (g(k), (u) - VJ(O(() HIll
v k (g(k) 11) p V ا1 + (V(() ()) ()((()) .)]l.. ()))).
k=1
We define again of = ( ,1) (((()) (4) and continue using the 3-lipschitz continuity of (()) such that
11000- 11 S (l || + (110(k) 11
2-1
o 113 -100()) - -
17
Using this inequality sequentially leads to
t-1
||000 - g || < 1
K 11 + n/8
((k)) g(()
1-2
6 || n/8 Σ (((k)) g( + nB
10 + 173 2 10(k)) g(6)
$ 1
1-2
Σ
o || + 2
Σ
11 || + (1 1783)1133
(0(k) g(6)||
7
k-2
+ 17(1 + m33) Σ
Hot K || + (1 +
10(k) - 1001
1=1
(1 + 1 K ||-
44

---

Published as a conference paper at ICLR 2024
Applying Markov's inequality results in
10( (00))((())))) -0(0 2 -
P(T S n)
P max 0sesn
P
(71 1
Chay
7 [ + m |0 11
Am
4nn + 1
where in the last inequality B1ll 111 - v B K [2] v K Now we plug in the choice of ?) V*SH2R
by Jensen's 's inequality and Lemma D.1
4n V (1 + 1
3)m
Vnn
P(T 1)) S
4VT(11 + + VOh
4VOnVE
RH
5H2R-eVK
where the last step is due to f(z) (1 + 1 )-1
S x for all 1. We follow that P(r < n)
vz
16n
16n 1 max R 1) (5 22222
48 max 132n3
10 max 10max(1(,
K.
25H (R-)2
56282
2282
Theorem 4.1. Under Assumption 3.1 let j be a probability measure such that p(s)) > 0 for all E S. Consider the final policy using Algorithm Twith stochastic updates from Equation X denoted
by #* π 8(N) Moreover, for any 8,e > 0 assume that the number of training steps satisfies
N 2
(21SH
let 5H and K N 10max R Na
Then it holds true that
6282
P(Vo(u) Vo (1) () >11
Proof. First note again, that by definition ('()) (u) and J(O(N), = Vo -VJ0(N) (10). We separate the probability using the stopping time 7 and obtain
P((J'()) J(O(M),N) ,1) 2 S 2 J(O(N) 14)) 2 6))
+ +P((T + J(((N) w)) 2 et)
E
(J ((ON)) ())
+ +P(TSN)
20|S|H*R* R'
d 2
8
E 2 VN (1
2/N )
1
000
2
8
2
8,
45

---

Published as a conference paper at ICLR 2024
where the second inequality holds due to Lemma D.4 and Lemma D.5 by our choice of N:
The last inequality follows
20|S| R
d
S
c2 DRV((1
2/N
if and only if N 2 20 H" R'
+ }) 2
which is satisfied if N
ebc
oc
Note that we can use Lemma D.4 choice of 1)
in the equation above with a constant batch size, because by our
9 e max RR", 1) 8
2VN
2 n²
10 max [t", 13
10 [t", 1
max
|3/2|8|
/
e²6²
c²8²
for all n S N. The last equality holds, as c < 1,
<I
D.2 DYNAMIC APPROACH
We start again by showing that the gradient estimator is unbiased and has bounded variance.
Lemma D.6. For any H and Kn. > 0 it holds that
[(" (()()))) J K6 (0, #(N+1), [b)] = Jv, ( 1). pb)
and
(5) ( (0, (n) VJ (0, 9 (1++))) mm)) Ejp
5(H (R*)2
4/
=:
Kr.
K
Proof. By the definition of JK we have
(8)x+t)
J (0, a mn))
Kn
Eph
(T' (+)
V Vlog(T (Ag(TT(AAii (A)())) (()) Ri
Kh
Epp.
lnfa. (1)
V log(T (R)
H Σ r(Sk, Ar)
Epp. (()((+)))
Vog(( (Av))))
k=h
where we used that we consider independent samples for i I,..., Kn. From the proof of the policy gradient Theorem A.6 we obtain that
E Byn
(f)
J (0, a(++1):)1))) 1))
H-1
Eyp
(x" (a))))))))))))
V log((= (A1 Sa))
Σ
r(Se, Ac)
k=h
(0, ((.+1))M4)
For the second claim we have
(T7
(+)()))))))))
[| J (0, f10 Pb) J), R ())+))),1)1
Kh
1
E
Bph
(7 ((F)(at1))
(All))=(A An. (+)1
n-1 Σ
1 ((=((())+)))))
Σ Σ
(1amAn ~ ((ab)))
r r(Su, Ax)
Kr.
SESh aed
k=h
(s) (aass)
(x" (())
(s, (s.
46

---

Published as a conference paper at ICLR 2024
by the definition of J/ (8, ((++1), ph) and the derivative of V Jr, 11h pb) for the softmax parametrisation. Further,
1=", (#)(( 1)) Epp
J Kh (0, m(+t)) (0, (1)+1)))11)))
H-1
1 15 (F)(())(++)))
Epn
Σ
(Ia=An - ~x
Σ ((Sk:AA)
Kn
aEA,
k=hh
Σ 111
r(Sk, (l (f (Sh, a)
2
Ala=An - (a((s))
aEA,
(als) (=" (
aEA.
We consider all three terms separately. For the first term have
H
( (n (F)ca+1))
Σ
(la=An - - (a|ss))
Σ rSkk, Aa)) }
GEA.
H-1
#-1
-Epn
(f))(()(
r(Sk: As) As) 29-
2E,h,
( (F)cnt2)
72 (ANISW)
r(S An) '
kmh
Am h
111
+ Bas
(9 (()))+))))
Σ n" (alS))
Σ
r(Se, Ant) '
aEA.
k=
S ((H - 1) + ((H- h))²²²
- ([(H-h)RP
by bounded reward assumption and the fact that x² is a probability distribution. For the second term, we note that A, (x" (800++)) (Sh, a) can be negative, therefore we consider the absolute value and obtain
H-1
2
(5" (004))
Σ (La=An - (a(S,)
Σ
r(Sk, (s) (00++) (4000))))))
aed
k=h
< 2E
(T (80((1))))
Σ 1. (111-1)) 1- 1- (a) (HI -hh-h)
BEA.
= -2((H- - ?
For the last term we have
(F) E
[Σ> SES₁ aEA,
(n()) (als)² A (f". (()()))))))))) (s,a)) s
In total, it holds that
E (7" (())a+1))
| Kn (0, A(n1)): J., # (m)11
5((H - R2)
K
Recall (0)-) 1=2 be the stochastic process from Equation 10 let (o(")) ),20 be the deterministic
sequence generated by PG with exact gradients,
6h (n+1) (1) + Th ( .00t1)
such that the initial parameter agree, 0000 = g( and the step size mh is the same for both processes. The natural filtration of (0(m) )220 is denoted by (I(1)) m2o-
47

---

Published as a conference paper at ICLR 2024
For the deterministic scheme we could assure сд min,20 min n Thh from by Lemma 10 As for the simultaneous PG this cannot be guaranteed for the stochastic trajectory. Define for every epoch the following stopping time
(s)ss is bounded away
Th = min(n 2 0: 110
0% 2
Ch 4 }.
We emphasise that The is a stopping time with respect the filtration (F ( Inz0 by construction.
follows again by the V2-Lipschitz continuity + x (a(aa)))))) (Lemma D.2p that minogagra minses N (i)) (a" (s))s) 2 O.
Lemma D.7. Let pu be probability measures such that (1( 0 for all Sh. and
sider the sequence (0(m)) )n20 generated by Equation 10 Then, holds almost surely that
minogagn, min,es, π ") (a (8)(8) 2 Sg is strictly positive.
Proof.
For every n S T we obtain by the 22-Lipschitz continuity in Lemma D.2 that
x tht
2 n th (a'(s))s) - 1, (s))s) the (s)(s)
(a'(s))))
2 n th (s)()))) v2110% 000111
Ch 0.
2
holds almost surely. The claim follows directly.
We derive a convergence rate the event {n S Th in the following sense:
Lemma D.8. Let μh be probability measures such that pa(s)) > 0 for all E Sp and consider the
sequence (of")) )n20 generated by Equation 10 Suppose that
the batch size kc(") 2
45c (1 N/N, ) is increasing for some Nç.
61N
the step size Th 2(H-h)R- VN.
Then,
32/N - R" 3(1
-
2/ Jc
Proof. As in the proof of Theorem 4.1 we deduce from the -ssomohtsssss and Lemma D.6 that
E [(((utt))
#(+t))
>(((h)) (5(44))))))
(m
Bnn e'h (.(44)))m))))) 1n))11
2K (n) h.
48

---

Published as a conference paper at ICLR 2024
We take the expectation of this inequality on both sides under the event {n + 1 S Th). Note that
{n + 1 1 m = {Th I n2 is Fn F--mesuurable and that 1 (n+1sm) S 1 (nST,) a.s., thus
E (J (+(++))) ma) Jn (0/ I() Pb (m+timm)))))
E E (T 13. mb) Jh (1( #()+1)) (m)
1 [
< E (F mn) E [Jn(0h ((04)) 1m) (2))
Instal
(JA ( mb) - Jr (hk -(++1): mb) (mSTm))
E
(m Bith
E [ - 1bh ml1 )13 (mSTm))
2k (n)
E
(Ji (#((++)); mm)
Jr (h m(b+1); (b)) ( (nST))
5(H - h) 2k Nn. |n
E 1 A((+ Ma) 121 (mSmm)
mh 2 N
By Lemma B.9 we have that
[ ( #w)+) 2 min x x" (S) -Jn(0h") -((+))): unl))
almost surely, and by Lemma almost surly. Therefore,
D.7 we have that millognsn. minges "h (a (x)s))2 2 4 >
E (JA (T(h- 1). Mb) In (0, a(h+1), PN)
E (J((+((11)))))) - _ (h)+))+[))]am
m (1-
1
E
m (a (s|s)) (J) - 2 (mStm))
min SES
5(H - R)
N/
2k NT.
< E5 (J un) - -J)( A((+1), Mn) (n))
m (1- 2/
1
B
- (k( (w)))))
2 + 2K(1) (1) N₂
5(H - h)
where we used Jensen's incquality in the last step.
For dr = (]] mK)) - ( :*(111), (kh) (msmm) we imply the recursive inequality
dn+1 S dn - m1 (1 2/
1
ch da +
5(H - h)R
2K (m) Nv
Define w :- 171h (1 (1- 2/Nn
c 0 and B 5(H - 2Nr
0, then
B
dn+1 S d1 - -wd,)
+ (x)
and by our choice of mh.
(n)
45cB
)n²
9
w BBn.
64N h
4
Moreover, it holds that
1
4
4
di S (H h)R < 77
3w
3w
1
49

---

Published as a conference paper at ICLR 2024
because ch 1 and vr. (1 z/7, 1 for all N₁ 2 1. 4 holds true, then for dm+1;
Suppose the induction assumption
dn S 3um
B
dn+1 S dn wo +
The function f(x) a wx² is monotonically increasing in [0, 2nd and by induction assumption
dn S Twn 3 2w So dn wol <
4_ which implies
Swn
B
dnt1 S dn
wa
2
+
(x)
16
B
+
3wn
9wn
Kn
16
4B
+
3wn
9wn
9w Bn?
12
3wn
9wn
3w n
3w (n + 1)'
where we used that k,
2 2 Bn2. We follow the claim
4 2 (H - R
dn <
3wn
3(1
2/N, )0
Secondly, consider the complementary event {r S n). We can bound the probability of this event by for large enough batch size Kn. The proof is again inspired by similar results obtained in Ding et al. (2022] Lem. 6.3) for discounted MDPs.
Lemma D.9. Let 14h be probability measures such that (4(s) 0 for all Sn. and consider the sequence (of")))) generated by Equation 10 For any > suppose that
the batch size Kn 2
5m
82
the step size Th
Then, we have P(( S n) < 6.
Proof. The proof follows line by line the one of Lemma D.5
One obtains
P(Th S n) PP max |10(")) .6²011 >
Ch
Ost5n
4nm (1 + mm -1
Vn Kh.
50

---

Published as a conference paper at ICLR 2024
where 4% from Lemma D.6 Now plug in the choice of 17
//ph
2
v
4n
31
n-
vnon
Kh.
P(T S n) S
Ch
4/7((1 + V
V
3rCn Kn
2nvnven
nvōn
Brch VK
CA Cv
where the last step is due to f(x) = (1+
v + S x for all 2 1. We follow that (P(n < n) <
if
5m 3
Kn 2
c 82
We are now ready to proof the epoch wise statement. Lemma D.10. Let Ph be probability measures such that (x(()) > 0 for all 8 E Sp and consider the sequence (0("))2e generated by Equation 10 Moreover, for any 6, e > 0, assume that
(i) the number of training steps N₁.
(12(H-118R*) )
cōcß
5N3
(ii) the step size Th 2(H--)J vNr and the batch size Kū
27,62
Then, it holds true that P
Mn) - Jn, (6 A(++)): Ma) 2 2)) S 8.
(a)
Proof. We separate the probability using the stopping time Th and obtain
JA (f Pb) (o) Am++)::H) 2 2))
P (Th 2 Nx) (J](( Jn (0, (o. -()-1)) 26}) P (Th S No.
-n, A((+t), 2 2c))
(JR( - (h No)
+ +PP(T S No)
32, NH h)R²
+
6
3(1
2/N, 10
8 8
+
2 2
5,
where the second inequality it due to Lemma D.8 and Lemma D.9 our choice of N₁:
The last inequality follows by
32 ( h)R
11 - R) 6 2
3E( 1 2/N, John
c(1
2/N1
for N₁ 2
[1) <5o2
2 which is satisfied for N₂.
12(H 12(H-N)8 2 Note further that edo7
could use Lemma D.8 in the equation above with a constant batch size K₁, because
45c
1
)n²
5
5/3 C 8
max
64N
2/Nr
2
for all n 5 Nr. (1 2/N,
and Ch
1.
51

---

Published as a conference paper at ICLR 2024
Theorem 4.2. For all h E H. let (h be probability measures such that pu(s) 0 for all h H.
8 E Sh. Consider the final policy using Algorithm 2 with stochastic updates from Equation 70
denoted by i²* = (1r %0000
No)
). Moreover, for any ó, > 0 assume that the numbers of Ph
12(H NYR n²
training steps satisfy No. Z
let Tph.
2(H-N)R and KA. 2
6
%
Then it holds true that
P P( So Vi(() 10¹ (8) <c) 8.
Proof. As in the proof of the exact gradient case (Theorem 3.5 Equation 24 we have by our choice of the future policy म = 5* that
Jn (A(+1)),00) 0,) = V/x" (s).
(37)
By Lemma D.10 we have that
6
TP Jh (#(41)))) Jn (0,,,,, (((+1))sh)) 2
H
H
phh
by our choice of No. Mh and Kn.- For every E Sn, denote by 8₂ the dirac measure state s, then as in Equation 25
() 5,) - Jn(0h Ai+ 6,) S - ll (J) (J)( An) - (1 (a))
((+t)))N)) a.s.
Thus, for all h E H it holds that
P As E Sn [A(+)-1) - (1 (n) .((41)):0))
06) 2
6
H
(38)
S [J - Jn(( ( Pb) 2
S
H
H
Define the event A₁ := (J 82) (1 m(++)) 6.)
$ E S. Then Equation 38
equivalent to P(4 S म. For = H - 1 follows directly with Equation 37 and the special property of the last time point that
P 3s
Sn Vn i (5) - V# (s) 2 :)
H
S 8
IP 3s E Sn (6.) J 10 No) .,0)) 2 H
H
We close the proof by induction. Assume for some 0 < h < H that
P ss E Sn. (s) V (s) 2 <(H
H -
h1)
6 H h)
(39)
H
Define B₁ = (s)
h (8) <(H- vs E Sr.. Similar to Equation
28 on the event Bg it
H
holds that
J ( 8.) = max
(((s,)) - Σ (V)
Σ
- (s))
aeA.
s'ES,
S'ES,
E(H - h)
max aeA,
(((s,a) + Σ p(s')s, p)
H
S
= (s) c(H - h)
H
We obtain on the event An-1 O Bn that (compare to Equation 29
(s) V (s) V (s)
J (T 6,) + Jj (7(1). 6.) V (s)
{H h)
e
H +
H
elll (h- 1))
H
52

---

1)) Published as a conference paper at ICLR 2024
for every Sh-1- Hence, A4-1 0 By C Bh-1- Finally, close the induction by
P Is E Sh-1 1 V h- e(Hl (h -
H1
(( 1 ( B₂) P( S P(BB))
= -P(1e Sh-1 ( 6.) - Jn- 10 (N=-1) -(()): 6,)2 E
H
Is Sn : (b) V/ (8) 2 (H- h))
+ PP(3
H
8 8(H h)
Σ +
H
H
8(H
(h
H
Finally, for = we have shown the assertion
P(3 EesE So (s) V/5 20 5o.
E EXAMPLE
We enclose a numerical toy example of a very simple MDP problem of optimally stopping when throwing dice H times. This is non-trivial example for which exact policy gradients be computed. The simulations show that the theoretical results (in the exact gradient setup) are sharp up constants.
The MDP corresponding to this example is defined as follows:
a constant state space over the epochs = (1,...,6,AA) containing all sides of the dice
1, ...., 6 and terminal state A,
constant action space A = {0, 1}. where 1 indicates stopping and jumping into the terminal state and indicates continuing to the next epoch,
transition function p
p(s' 8, s.a) P(S++1 5' Sh = a, = a)
if 10. 6), a= 0.
6
1, if A, s s S, a= lors' - a=0,
0, otherwise.
Thus, we throw the dice iid until stopping for the first time, then we jump into the terminal state and stay there for the rest of the game.
a reward function r
s:
if E f0.1......... 6), 1,
(88, a)
= 0, otherwise.
We only observe a reward when we choose action to top the game and the reward equals the number on the dice.
Having this model with known transition probabilities allows us to implement the simultaneous and dynamic PG under the exact gradient assumption. In the simulation we always initialised the parameters uniformly and chose = 0. Furthermore chose the suggested learning rates from Theorem 3.2 in the simultaneous approach and from Theorem 3.5 in the dynamic approach.
First, note that Figure 2 (a) is the same Figure T from the introduction. The dotted red line in this plot shows the target: Vgg. On the æ-axis we count the number of gradient computations in the algorithms, way of measuring the computational complexity. The dashed magenta curve shows the
53

---

Published as a conference paper at ICLR 2024
52
50-
10a
Im
optrmal vn un fundtio
Interptatton of entpoints
value funetion traihed backward time value function trained aimutanneoust
value function netteed backword time
value function telined sinutanenusly
50000 300000
200000
number gradient stops
number of gradient steps
(a)
(b)
Figure 2: (a) shows the behavior of Vo (Dn
during the training steps over all epochs. (b) shows the log-log plot of the same simulation visualizing the convergence rate towards Vi+
evolution of the estimated value function trained with the simultaneous training of all parameters. As is unknown for the approach, we trained the parameters until an error of 0.1 was achieved. The blue curves show the evolution of the estimated value function trained with our algorithm backwards. Note that the number of gradient steps varies for different epochs, as suggested by Theorem 3.5 less training for later epochs. This can be the blue lines. One plateau shows the training of one parameter. Just when the last parameter 0g is trained, the value function V/"" finally converges towards the target. In this simulation we chose e 5, 1, 0.5, 0.25, 0.12 to define the length of the training steps according to Theorem 3.5 Note that the uniform initialisation lead to с₁ 0.5 such that N₂. could be explicitly calculated. From light to dark blue e decreases. can be seen that the final error is better than the chosen epsilon, indicating that the rate of convergence from the dynamic approach is tight up constants.
in the plot by the different lengths of the plateaus of
In Figure 2 (b) for comparison the red line constant times 1 The dashed magenta line is the optimal value minus the dashed magenta curve from (a) of the simultaneous approach. Also, the blue curves are the optimal value minus the blue curves from (a). The dotted blue line is the linear interpolation of the end points of the blue lines. As the dotted blue line, the magenta line and the red line have the same slop, this shows the 1 convergeence rate in the accuracy level The larger difference from the dashed magenta line the red line in comparison the dotted blue line the red line indicates the larger constant in the rate of convergence.
Both plots show that the dynamic PG algorithm converges faster than the simultaneous one. As suggested by the upper bounds the effect gets much stronger for larger H.
54


Reviews:
[{"review_id": "pSEn38MztK", "reviewer": "Reviewer_EGiX", "summary": "This paper proposed a policy gradient algorithm for finite-horizon MDPs that are trained backward, for the benefit of explicit constant dependence in convergence guarantees and faster convergence behavior comparing to policy gradient methods that are trained simultaneously.", "questions": "- For simultaneous PG analysis of unregularized softmax, you claimed that you are the first to analyze the global convergence rate. However, there are a number of works that study convergence rate and sample complexity for stochastic policy mirror descent, which is a more general algorithmic framework that encompass softmax as a special case [1].\n- Given the plethora of works on softmax policy gradient in the tabular case and discussions on its limitations [2], what would be practical benefits of using softmax aside from the fact that it gives rise an unconstrained optimization problem?\n- In the unregularized MDP problem the optimal policy can be deterministic, in which case softmax parametrization does not cover all the possible policies and therefore is incomplete. Can you elaborate on the benefit of using an incomplete policy class in the tabular case here?\n- Is it possible to compare with Guo et al. 2022 (appeared in original reference list of the paper) performance numerically?\n\n\n[1] Alfano, Carlo, Rui Yuan, and Patrick Rebeschini. \"A novel framework for policy mirror descent with general parametrization and linear convergence.\" arXiv preprint arXiv:2301.13139.\n[2] Li, Gen, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. \"Softmax policy gradient methods can take exponential time to converge.\" In Conference on Learning Theory, pp. 3107-3110. PMLR, 2021.\n\n-----------\n\nPost-rebuttal: I thank the authors for their clarification and agree that unregularized softmax would be of interest for theoretical analysis. I personally disagreed with the statement in the paper \"...very little is known about convergence to global optima even in the discounted case\" per the discussion before. I have increased my score.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The idea of using dynamic programming related idea to capture the structure of finite-horizon MDPs to improve efficiency of policy gradient algorithms is interesting, and the convergence guarantees with explicit constants are established with accompanying experiments.", "weaknesses": "More comparisons with state-of-the-art policy gradient methods for tabular finite-horizon MDPs could have been presented to increase the convincingness of the example. It should be clearly stated why unregularized softmax is interesting to analyze by itself given the volume of past works on softmax PG and mirror descent methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "czxl64K2uP", "reviewer": "Reviewer_iprP", "summary": "This manuscript delves into the convergence characteristics of policy gradient (PG) methodologies utilizing softmax policies within the context of MDPs that have a finite horizon, denoted as $H$. A prevalent approach to implementing PG methods in finite horizon scenarios involves augmenting the state space with a temporal coordinate, subsequently training across all epochs in a simultaneous fashion. The authors have extended the convergence analysis techniques from [Agarwal et al., 2021; Mei et al., 2020], originally applied to gradient ascent algorithms with exact gradients in infinite MDPs, to the domain of simultaneous PG with exact gradients for finite horizon MDPs. This adaptation has yielded a global convergence rate of $O(H^5)$. Building upon this, the paper introduces an innovative algorithm that synergizes PG with dynamic programming, termed as dynamic PG, which notably enhances the global convergence rate of simultaneous PG to $O(H^3)$. Finally, the authors extended their findings to encompass scenarios where a stochastic gradient is utilized instead of an exact gradient.", "questions": "Correct me if I'm wrong, my intuition is that since dynamic PG is fixing policy from $h+1$ onward, it can be viewed as a specific coordinate ascent algorithm. Do you see any way to use the backward update idea for infinite horizon non-stationary MDPs?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I believe this paper is comprehensively developed and presents a balanced view on the topic at hand. Despite the intricate nature of the subject, the paper is articulately written, ensuring clarity and ease of understanding for the readers. While I have not had the opportunity to delve into Appendix C, I feel reasonably assured about the soundness of the proofs presented in the rest of the document. To me, the concept of backward updating stands out as the most intriguing aspect of this paper, marking a novel application of this technique in proving global convergence, something I have not encountered in previous papers proving global convergence result for MDPs.", "weaknesses": "The only limitation I can think of is the limited experimental results; however, this is understandable given its theoretical nature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "imhtebVx65", "reviewer": "Reviewer_Y9J6", "summary": "This paper presents a thorough investigation of policy gradient (PG) methods applied to finite-horizon Markov Decision Processes (MDPs). The authors introduce two PG methods: the conventional simultaneous PG and a novel dynamic PG. The convergence of these methods is mathematically proven by leveraging two key factors: (1) the smoothness property inherent in finite-horizon MDPs, and (2) the gradient dominance condition. Furthermore, the authors extend their analysis to the model-free setting, proposing two stochastic PG methods with proven convergence analysis.", "questions": "The proofs make sense to me. I have the following minor questions:\n\n1. As mentioned above, it would be nice if the authors could further describe the technical challenges of establishing the convergence results.\n\n2. Why does the term '$\\exists s \\in\\mathcal{S}$' exist in the equation of Theorem 4.2? It seems the result of Theorem 4.2 is weaker.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper is easy to follow. The dynamic gradient method proposed is new to finite-horizon MDP, and it is complimented by strong theoretical guarantees, while the smoothness property and the gradient dominance condition existing in infinite-horizon MDPs' literature are adopted into the finite-horizon case. Meanwhile, the paper also considers the character of the coefficient $\\inf_{n}\\min_{s\\in\\mathcal{S}}\\pi^{\\theta}(a^{\\star}(s)|s)$ and further shows how to determine its lower bound, which is a new insight. \n\nTo address the model-free setting, the authors introduce two related stochastic PG methods with proven convergence results. In their comparison, both dynamic PG and stochastic dynamic PG take less steps than their counterparts.", "weaknesses": "One reason for not giving a higher score at this point is that the global convergence results and their analysis are actually not that surprising. As mentioned in the paper, all proofs of convergence behaviors follow the idea of the smoothness property and the gradient dominance condition, which are well used especially in [1]. While they are adopted in the finite-horizon MDP, it would surely help if the authors could discuss more about the technical challenges of the analysis.\n\nFurthermore, the discussion on motivation in the paper appears to be somewhat weak. It would be beneficial to include a more comprehensive review of relevant literature to emphasize the significance and importance of studying finite-horizon MDPs. \n\n[i] On the Global Convergence Rates of Softmax Policy Gradient Methods, ICML, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)