Structure Matters: Dynamic Policy Gradient
Authors: Sara Klein
Xiangyuan Zhang
Tamer Basar
Simon Weissmann
Leif Döring
Venue: NeurIPS 2025 poster ()
Keywords: reinforcement learning
policy gradient
dynamic programming
Primary area: reinforcement_learning

Abstract: In this work, we study $\gamma$-discounted infinite-horizon tabular Markov decision processes (MDPs) and introduce a framework called dynamic policy gradient (DynPG). The framework directly integrates dynamic programming with (any) policy gradient method, explicitly leveraging the Markovian property of the environment. DynPG dynamically adjusts the problem horizon during training, decomposing the original infinite-horizon MDP into a sequence of contextual bandit problems. By iteratively solving these contextual bandits, DynPG converges to the stationary optimal policy of the infinite-horizon MDP. To demonstrate the power of DynPG, we establish its non-asymptotic global convergence rate under the tabular softmax  parametrization, focusing on the dependencies on salient but essential parameters of the MDP. By combining classical arguments from dynamic programming with more recent convergence arguments of policy gradient schemes, we prove that softmax DynPG scales polynomially in the effective horizon $(1-\gamma)^{-1}$. Our findings contrast recent exponential lower bound examples for vanilla policy gradient.

Structure Matters:
Dynamic Policy Gradient
Sara Klein
Xiangyuan Zhang² Tamer Başar* Simon Weissmann' Leif Döring'
IIstiittt for Mathematics, University of Mannheim, 68138 Mannheim simon. weissmann, leif.docring) Bantiingg@uamamaaiaaiiaaaa Luni-mannheim.de
2 Department of Electrical and Computer Engincering, and Coordinated Science Laboratory, University of Illinois Urbana- -aaaunaaChaaaign.... Urbana, IL 61801
[x27, basarl @ @ellinois.edu
3 AugusttWilleln Scheer Institute for Digital Products and Processes gGmbH, 66123 Saarbrüccen kara.klein @ aws-institut.de
Abstract
In this work, we study 7-discounted aalinite-horizon tabular Markov decision pro- cesses (MDPs) and introduce a framework called dynamic policy gradient (DynPG). The framework directly integrates dynamic programming with (any) policy gra- dient method, explicitly leveraging the Markovian property of the environment. DynPG dynamically adjusts the problem horizon during training, decomposing the original infinite-horizon MDP into sequence of contextual bandit problems. By iteratively solving these contextual bandits, DynPG converges to the stationary optimal policy of the infinite-horizon MDP. To demonstrate the power of DynPG, we establish its non-asymptotic global convergence rate under the tabular softmax parametrization, focusing the dependencies the MDP. By combining classical arguments from dynamic programming with more recent convergence arguments of policy gradient schemes, prove that soft- max DynPG scales polynomially in the effective horizon (1 7) Our findings contrast recent exponential lower bound examples for vanilla policy gradient.
salient but essential parameters
Introduction
The overarching goal reinforcement learning (RL) is to train an agent that interacts with an unknown environment. This is mathematically modeled through Markov decision process (MDP), where the agent actively learns a policy that, given a state, executes actions and receives rewards in return. The objective is to find policy that maximizes the expected discounted reward. We categorize RL algorithms into two groups. Rather than the conventional separation between value-based and policy-based algorithms,
distinguish between algorithms that leverage the model's structure and those that do not. The first class utilizes the dynamic programming (DP) principle, such as value iteration, policy iteration, Q-learning. Those algorithms optimize essentially single-period problems, where a single reward feedback used the update procedure and the future payoff is estimated by evaluation. The second class considers the entire multi-period problem solves it using classical optimization, as in policy gradient (PG) methods 29 [3] 10] Over time, hybrid approaches integrating both methods, such as actor-critic (AC) methods, have consistently demonstrated superior performance in practical applications even though dynamic programming is used rather indirectly. In AC, the critic suggests a baseline, estimating either the value action-value function. Dynamic programming becomes essential during the critic update process, effectively diminishing variance in gradient estimation. The essence of employing dynamic programming lies in the fact that parameter updates are not solely reliant on new trajectories, information is bootstrapped. Efforts of a broad research community have led to tremendous success of AC type algorithms (such as natural policy gradient (NPG), trust region policy optimization (TRPO), proximal policy optimization
and
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(PPO)) but these have not yet been backed by sufficient theoretical understanding. This paper
contributes to the basic theory of PG methods by studying the following questions:
To what extent can the Markov property of an MDP be exploited directly to improve convergence of PG methods? How much improvement is gained compared vanilla PG?
This paper addresses both points by merging dynamic programming and policy gradient into dynamic policy gradient (DynPG) and analyzing its convergence behavior. DynPG can be seen as a hybrid RL algorithm that utilizes policy gradient to optimize a sequence of contextual bandits. In each iteration, the algorithm extends the horizon of the MDP by adding additional epoch in the beginning and shifting trained policies to the future, as in applying the Bellman operator. A policy for the newly added epoch is trained by policy gradient where previous policies used to determine future actions (cf., Figure D. DynPG is not an AC method. It reduces the variance as far as possible by applying the previously trained, and therefore fixed, policies to generate trajectory. This leads stable estimates of the rewards-to-ge and improves convergence behavior. In this work, we first present a general error analysis which compatible with any optimization scheme address each contextual bandit problem such as PG, NPG or policy mirror descent [30]. We then employ vanilla PG to present an explicit complexity bound under softmax parametrization.
1.1
Related work
The idea of using dynamic programming in searching the optimal policy is not new and dates back to the early 2000s, having been revisited several times in recent decades. Policy search by dynamic programming (PSDP) 21 is most closely related to DynPG and searches for optimal policies in a restricted policy class without explicitly using gradient ascent to find the optimal policy. Next to this CBMPI in (2 is also related to DynPG. Here the greedy policy is based on a previous value-iteration step. However in DynPG, no value iteration is necessary. There is a line of similar algorithms like approximate policy iteration (APD, gradient temporal difference, policy dynamic programming and
numerous other variations [3] 25 26 9.. In these works, however, PG was not used as policy optimization step. In [2]. a similar concept, also called dynamic policy gradient, was employed to tackle finite-time MDPs without discounting. Their motivation to utilize dynamic programming stemmed from seeking non-stationary optimal policies in Emite-time MDPs. In contrast to their findings, our objective is to identify a stationary optimal policy and incorporate discounting into the framework. The present paper can be seen as a continuation of that line of research towards infinite- time horizon MDPs. Lastly, in their study of linear- quaara-qu continuous control and estimation proposed a seceding-horizer policy gradient algorithm, which also integrates dynamic programming- baaed receding-horie -ooiinnn control with policy gradient methods.
problems, 13 34 35
The discount factor y E (0, 1) plays an essential role in the convergence behavior of RL algorithms, as they explicitly depend on the contraction property of the Bellman operator. The closer y to one, the slower the Bellman operator contracts. Similarly, the convergence of PG methods also heavily depends on y but establishing a clear dependence is generally challenging due to the non-convex optimization landscape. Early works only concern convergence stationary points 18 23 17].
More recently, specific to tabular settings and the softmax parametrization, 16) have derived upper bounds on the convergence rate a global optimum by utilizing gradient domination property (19). As shown in [6]. vanilla softmax PG has a sublinear convergence rate of O(e-1) with respect to the error tolerance e. Dependencies on other salient but essential parameters of the MDP crucially affect the overall convergence behavior of PG methods, c.g., the effective horizon (1 --)- --- Notably, [55] constructed a counterexample such that vanilla PG could take an exponential time (with respect to (1 ")) to converge. Although the optimal solution can be reached in just |S] steps of exact value iteration in the counter example, vanilla softmax PG is very inefficient by not leveraging the inherent structure of the MDP. In contrast, for softmax DynPG, we establish an explicit dependency on the discount factor. The convergence rate under exact gradients scales with (1 (1-30 7) up to logarithmic factors; thus, we delineate the unknown model-ddependent constant C(>) in the rate of vanilla softmax PG [16]. As a result, DynPG can efficiently address the counterexample of [15); see Section 5 Table I summarizes the complexity bounds for softmax PG and softmax DynPG.

---

algorithm
complexity bounds
reference
softmax PG upper bound
O(C())(1- -
16 Thm. 4]
|8| (8p20()->)>)> gradient steps for e 0.15
softmax PG lower bound
15 Thm. 1]
softmax DynPG upper bound
(((1- ((11-))-(- -)) -
[our Thm. 4.8
Table 1: Comparison of convergence rate under exact gradients
1.2 Main contributions and outline
The main contribution of this article is to introduce and analyze a way to directly combine policy gradient and dynamic programming ideas. The algorithm we introduce Section 3 is called DynPG (dynamic policy gradient method). The algorithm (provably) circumvents recent worst case lower bound problems for standard PG that prove impracticability of plain vanilla PG in delicate environments. In Section 4 we provide detailed error decomposition to show the convergence behavior DynPG in general frameworks. For the tabular softmax parametrization we prove rigorous upper bounds on the convergence rate in Section 4.2 for the theoretical setting of exact gradients. Most importantly, the y-dependence is harmless, DynPG does not suffer from exponential dependencies in y! A simple example is presented in Section B show in sample based setting how DynPG can beat PG in environments that trick PG into so-called committal behavior.
Preliminaries
Let the tuple = -
denote an MDP, where S represents the state space, A represents
the action space, p S A (S) is the transition kernel mapping each state-action pair to the probability simplex of all possible next states A(S), S x A + R is the reward function mapping each state-action pair to a reward, l E (SS) denotes the initial state distribution, and y (0, 1) is the discount factor. We assume that the reward is bounded such that r(s, a) E [-It", R'] for all (s, a) x A and the state and action spaces are finite. Hereafter, we use capital and lowercase letters to distinguish random state and actions from deterministic ones. For x IR we denote its supremum norm by | = max; I we refer to Appendix A for complete notation conventions.
policy π : - A(A) is a mapping from a state & E S to a distribution over the action space, i.e., (-[s) E (AA). The set of all policies is denoted by I1. We refer N as the deterministic time- horizon, where the case h = oo corresponds to the standard infinite-horizon MDP. Non-stationary policies with time-horizon l are denoted by T (Th--,..... mo} 11th Let Vo and, for all h 0, define the h-step value function of policies T II
WTTh (w) tl mot (m)
E So Coma.ALTT ((S.)) S1t1 A..A.)
Σ 2'r(S,, A.)
(I)
When is Dirac measure at we let V (s) (s)= = V. (8.). Subsequently, we interpret a function V S + R as a vector in RIS Additionally, we use V/x" (w) == V ( (μ) to denote the value function the resulting infinite-horizon
of the stationary policy being applied h times in row. For h
discounted MDP admits a stationary optimal policy (0)). We define V (4) == supren V (и) and
use n² to denote a stationary policy that achieves V (1)) V (14). In contrast, when h is finite, the finite-horizon MDP optimization problem needs non-stationary optimal policies; thus, we define V,A (14) sup,, E W (I.) and use TÇ == (. mi) E 1 to denote sequence of policies that achieves V (n) VV)
For any function V E R! and stationary policy æ, the Bellman expectation operator T RR + RIS is defined for every E SSby by
T (V) = Σ π (als) (r(s,))+ +y Σ
p(s' (ds'|s,a\Vio [p(s)ss.aVV(')))
a
s'ES
3

---

The Bellman's optimality operator T : :R - R
S1 is then for every E S given by
(+)) = max aEd
(((, + Σ s'ES
The operators 7 and 7 are 7-contracting with unique fixed points denoted by VX and V respectively. In addition, the optimal htstep value functions V can be obtained by iteratively applying 7 and, as h + co, Vi converges to V (c.f. Lemma C.1
Vanilla Policy Gradient. Policy gradient is policy search method for which a family of differential parameterized policies (To (oR)) is fixed, say ne(-|s) == (-|ss, (r,ss)) 0), and the optimal policy is searched using gradient ascent:
0 -, On + Va, Vo (u).
Here, 1) > 0 is the step size. Analyzing the convergence of vanilla PG is generally non-trivial due the non-convexity of V and the approximation error of the policy approximation family. Specialized to tabular MDPs, [ has shown global convergence of vanilla PG under the softmax parametrization, and [16] established non-asymptotic convergence rate. It should be emphasized that convergence is slow and constants can easily dominate convergence rates.
Tabular Softmax Policy. Policy gradient can be applied in the tabular setting (i.e. considering separately each state-action pair). Although the tabular setting is not used in practical applications, is the most tractable setting for complete mathematical analysis and sheds light general principles.
We introduce the logit function 0 S A R and the softmax policy parametrized by 0 E IR (|AA|
exp(0(8, a))
To(a =
SES,
(3)
Ea'ed Ex exp(O(s.a'))
The tabular softmax policy can approximate any stationary and therefore also any optimal policy, whereas other parameterizations such as neural networks may induce an approximation error. This error needs to be considered in the convergence analysis.
Policy Search Framework. Inspired by dynamic programming, the authors in 3 proposed Policy Search by Dynamic Programming to search policies { {TH-1,-** mo) Iī" where H the problem horizon given as an input to the algorithm and IT C II the set of all deterministic policies. Formally, given H and fi, PSDP computes
(TTT.+5) (p) = argmax, w,elf म argmax ny eñ M+1
V. ( #6 (H).
(4)
V4+1
for h =, O,..., - 1. PSDP solves an (h + 1)-step MDP initialized at an So ~ ju in the iteration indexed by h. Specifically, it finds the optimal deterministic policy for selecting the first action Ay, denoted by R. but then all the remaining actions in the episode {A1,... AA-11 are selected according to the sequence of deterministic policies #े [. , #t). TH have been computed in previous iterations and are kept fixed. Compared to vanilla PG, PDSP exploits the Markovian property of the environment, rendering each iteration into solving contextual bandit problem. While considering deterministic policies may suffice in tabular MDPs, no explicit computational procedures have been provided in [1] solve the optimization problem in ( Further, determining the policy to be applied post-training is not immediately evident. The author in 21 proposse apply the non-stationary policy म in loop. Still, to solve the discussed infinite horizon MDP, a stationary policy is sufficient. We provide answers to these issues using DynPG.
Note that for all h.
3 Dynamic Policy Gradient
The DynPG Algorithm. DynPG starts by solving one-step contextual bandit problem and then incrementally extends the problem horizon by one in each iteration, which is done by appending
the new decision epoch in front of the current problem horizon (see the illustration Figure []] In each iteration, the parametrized (stochastic) policy responsible for sampling action Ao from the newly-added epoch is optimized using gradient ascent. subsequent time steps, DynPG applies the previous convergent policies to sample actions. Upon convergence of the current iteration, the

---

Algorithm 1: DynPG
Input: Initial state distribution y and class of
policies (To)DER*.
Output:
Result: Approximation of '²" denoted #*.
Set h 0 and initialize A + []:
H
Ag
H-1
H-2
2 while Convergence criterion not mer do Initialize 0 (c.g., 0g + O);
4 Design 17,, and N₁. (cf., Remark 4.4)
2
Ag
for n ....., NA- do
optimization variable
Sample G ~ Ven V h+1
( | (1) (cf.,
Fig %1
stored previous policies
DyaPG output
Theorem C:3
0
Fg
Update 0n+1 1 On G:
H+1
end
Figure 1: DynPG solves sequence of contex- tual bandit problems, iteratively storing the con- vergent policies to memory and applying them accordingly as fixed policies in later iterations.
Set A < RON;
10
Attach # at the beginning of A; Set h 1;
end
13
Return At <- #7 (the first element of A);
policy is stored in designated memory location, which will be utilized in future iterations. We define H := { 1: #o) E II with convention #ं 0 to denote the learned policies. DynPG returns the first policy in A when certain user-defined convergence criteria have been met. For example, this the case if the relative value improvements between two consecutive DynPG iterations are small
i... || V Il S
Hereafter, we let Vi = the construction DynPG implies th+s 1+1
(s) (V,"
(V,"")()) -... (T o o T (Vo) 8 S S,
(5)
which will be employed in the analyses of the convergence rate.
Compared vanilla PG in (2). DynPG dynamically adjusts the episode horizon during the execution of the algorithm. This results in two notable advantages. Firstly. we observe that DynPG effectively reduces the variance in gradient estimation through the utilization non-changing future policies. In contrast, the estimation of the gradient in vanilla PG involves assessing rewards-to-ge based on the stationary policy To. which changes during training. Secondly, DynPG requires significantly fewer samples, topic we discuss in detail later in this section. Moreover, each DynPG iteration has more benign optimization landscapes, as they are essentially contextual bandit problems. Specif- ically, DynPG has a simpler PG theorem (cf. Theorem C.3 and under softmax parametrization smaller smoothness constant, enabling the selection a more aggressive step size, Thh to enhance convergence.
In contrast to PSDP, we specify the set of policies to be a parameterized class of differentiable policies and computational procedure, namely PG, for the inner loop. straight forward to incorporate function approximation (e.g. using neural networks) to the DynPG algorithm. This preserves the model-free optimization characteristic of gradient methods, while still exploiting the underlying structure of MDPs by Dynamic Programming. DynPG can be further modified with additional enhancements such as regularization, natural policy gradient or policy mirror descent in ever optimization epoch. In addition, we show that applying the policy of the last training epoch as stationary policy is sufficient. This is non-trivial result and our analysis in Section 4 reveals that in general it requires additional training to obtain good stationary policy compared to using the non-stationary policy क in a loop as proposed in [21]. the tabular softmax case we specify these additional computational cost explicitly.
On the total sample complexity. For each gradient step in standard policy gradient, one must run the MDP until termination or up to stochastic horizon H Geom(1 - 7) to obtain an unbiased sample of the gradient (32]. DynPG, on the other hand, only requires à interactions with the environment to sample an unbiased estimator of the gradient in epoch h. Thus, comparing other policy
5

---

gradient methods to DynPG solely based on the number of gradient steps is inadequate. Instead, for fairness, the number of samples (interactions with the environment) should be compared in practical implementations. For DynPG the total sample complexity is given by Σn= (h + 1). This results in trade-off between increasing samples required for estimation and more accurate training obtain convergence (cf. Section 4.1
Numerical Example. To demonstrate DynPGis effectiveness we present a numerical study of a canonical example where vanilla PG suffers from committal behavior. A detailed description of the MDP and the experimental setup can be found Appendix B We note that the theoretical analysis for softmax DynPG in Section demonstrates its practical usefulness fine-tuning the learning rates.
In the figure to the right we plotted the success probability to achieve an overall error in the value function of less than
gamma 0.99
1.0
0.01 from the
optimal, i.. V VX x < 0.01. The success
0.8
probability is calculated by executing each algo- rithm 2000 times with randomly sampled initial states and the x-axis is the number of interac- tions with the environment used by both sample- based vanilla PG and sample-based DynPG. We observe that vanilla PG struggles solving this MDP, suffering from the high reward variance in certain states. Vanilla PG tends to concen- trate on large rewards samples while DynPG circumvents this committal behavior by more accurate estimation of the future Q-values. It can be observed that the performance of DynPG and vanilla PG are similar for the first 400 inter- actions with the environment. However, vanilla PG fails to converge to the optimal policy and can only reach the success probability around 0.8 under the given training budget. As usually for variants of vanilla PG, we expect that DynPG will not always more efficient than vanilla PG. While vanilla PG is stuck committal behavior the environment chosen for the simulation, there other (simpler) environments in which vanilla PG performs well. In that case our more complex algorithm will not beat vanilla PG or other equally well-perfooe well-performing variants, but expect comparable performance instead.
Success Probability
0.6
0.4
0.2
PG
DynPG
0.0
0
200 400 600 800 10001200
Interactions with environment
Figure Success probability of achieving the sub- optimality gap of c = 0.01 in the overall error.
DynAC. The DynPG algorithm requires to store sequence of policies which for large problems might result in memory issues. To mitigate the problem there is a natural actor-critic type extension, that call DynAC. Since analysis is out of the scope of this article DynAC is described in the appendix, compare Section
4 Convergence Analysis
Our numerical example suggests improved convergence properties for DynPG. In this section provide complexity bounds for exact gradients to keep notation simple. The reader with interest in bounds for estimated gradients is referred to Appendix F for the corresponding analysis.
In Section 4.1 four different layers of approximations were introduced that appear in the analysis of DynPG. Based this we present the asymptotic global convergence of DynPG under the assumption of small enough optimization errors and rich enough parametrization class. In Section 4.2) we establish non-asymptotic global convergence rates of DynPG for the softmax parametrization under the assumption that exact gradients are available. We provide suitable choices of H, N₁, and 7n such that DynPG achieves an error in the value functions of at most e, Proofs of all results are deferred to Appendix D

---

4.1 Error Decomposition and General Convergence
The analysis of DynPG employs four different layers of approximations, including 1) adopting parametrizations incapable of modeling the optimal policy perfectly (approximation error), 2) trun- cating the infinite time horizon to a finite horizon (truncation error), 3) utilizing a finite number of gradient updates to approximately solve each optimization problem (accumulated optimization error), and 4) applying the first policy of # as stationary policy in solving önite-horizon MDP (stationary policy error). We formally quantify these errors in the following proposition where the terms on the right-hand side of (6) correspond to the aforementioned errors, respectively.
Proposition 4.1. The overall error of DynPG after H iterations can be decomposed as follows
V V 1000 S V=
-sup
V
+
sup
V
sup 0o
H
+
sup
VH
1...tut
VA
+
|| R v 11:00
H
00....O 1
7 H +
V
sup
V
00
0
100
1 -
H-1
1 +
+
sup T (V - V h+1
H+1
V#
h=0
0
The error decomposition gives clear insights into algorithm design, for which is necessary to discuss the practical implications of the four summands.
1. To control the approximation error a rich enough policy parametrization required.
2. To keep the truncation error small, DynPG should run at least H
log(1-7) rounds.
log(?)
3. The third summand shows that approximation errors in earlier iterations are discounted more than approximation errors in later iterations. To achieve optimal training efficiency, we will thus require a geometrically decreasing optimization eтror across the iterations of DynPG. Recall the sample complexity discussion at the end of Section 3 to note that trade-off between more accurate training and increasing samples required for estimating the gradient must be made to obtain the best performance of DynPG.
4. DynPG approximates the value function by truncation at fixed time H and then replaces the optimal time-dependent policy by a stationary policy. As mentioned for PSDP, one could also apply the non-stationary policy H to approximate the value function. This would cause the fourth error term to vanish. Thus, in what follows, we distinguish between the overall error in 6 and the value function error:
H Rd
I V#* 1000 I
Vo-
sup BER4
Vo
+
1-7
H -- sup
T (V
V # h+1
lloo
DERd
It is important to note that the factor (1 - >) in the stationary policy error causes an additional dependence on the effective horizon the complexity bounds for softmax DynPG.
For the remainder of this section, we will proceed under the assumption of zero approximation error stemming from the parametrization. This condition generally holds true when the class of policies (Ta) can effectively approximate all deterministic policies, such as achieved through tabular softmax. Under this circumstance, it follows that T = sup, T and IV sup, V x0 = O. Subsequently, we demonstrate that certain reduction in the optimization error is adequate for achieving global convergence within the parametrized policy space.
Assumption 4.2. The class (ro) has zero approximation error and there exists a positive sequence en such that
7

---

Eizo 7 TH-h-leh cn - for H + 00, 00,
the policies obtained by DynPG satisfy 11 (V
thts V+1 1lo0 I for all h 220 0.
As an example for such a sequence one might think of es = 07 for some c > 0. Under this assumption prove convergence directly from the enror decomposition in Proposition 4.1
Corollary 4.3. Let Assumption 4.2 hold. Then, Algorithm generates a sequence of non-stationary policies Ti E 11 that satisfy
V 1100 +0
for H + 00.
Furthermore, the overall error vanishes the limit:
II
for H + oc. v 100 +
for H oo implies that the optimization error must decrease with increasing h to guarantee convergence. Hence, training must become more precise over time. It is advisable increase the number of gradient steps Nr. and decrease the step size Th.
Remark 4.4. The condition En=o -
4.2 Convergence Rates under Tabular Softmax Parametrization Exact Gradients
In this section, assume that all gradients known explicitly, strong assumption for practical use but standard for a rigorous analysis. The analysis extended in Appendix F to estimated gradients.
One might ask whether Assumption 4.2 is reasonable and whether there are situations in which the condition on algorithm holds. Indeed, we will show that this is the case for the softmax class of policies. More preciscly, for any çn O.
specify step size 7h, and number of gradient steps Nù, such that Assumption 44.2 is satisfied. In a second step, we optimize and the error sequence (ex) to obtain the optimal sample complexity for DynPG under softmax parametrization, where distinguish again between the value function error and the overall error.
Assumption 4.5. Suppose that p(s) > for all S such that | c0. Furthermore, the parametrization in DynPG (To)øERISIAA) is chosen to be the tabular softmax parametrization introduced in Equation (3). We further assume uniform distribution over the action space as the inilialization of 0g in Algorithm 7
Theorem 4.6. Let Assumption 4.5 hold true and the gradient accessed exactly. Let h 2 ch 00
and A A I be collection of h arbitrary policies. Then, using step size Th 21- (1-11)
and gradient steps N₁, 4n" (10-~~1)111 h achieves
11
in DynPG guarantees that the policy #G of iteration
(1-7)en
[T (V V
- 'lo0 S En.
we obtain from Theorem 4.6 convergence for softmax DynPG by choosing a sufficient decreasing eπror sequence (ex).
By Corollary 4.3
Remark 4.7. The proof is adapted from 112 Lem. 3.4] to the discounted setting and is provided in Appendix D.2 Note that we will not directly apply (16] Thm. 4] with 7 0 to prove this theorem for contextual handits because the authors assumed rewards in 10, 1}. Even when we make the same assumption, the problem horizon increases with h such that the contextual bandits we consider, h++
V(ne.A) will have maximal reward greater then after the first iteration. Therefore we provide more general framework with bounded rewards in [- R", R*). Furthermore, the smoothness constant used in [16] can be improved, which results in tighter bounds.
In order to obtain complexity bounds from Theorem 4.6 for a given accuracy e we optimize the total number of gradient steps Σ (Ck) with respect to H and (er) under the constraint that the overall error (6) or the value function error 7 bounded by e. provide detailed solution to the described constrained optimization problem Appendix Parts of the proof are motivated by a similar optimization problem solved (88, Sec. 3.2). We summarize the complexity bounds for both error types in the following.
8

---

Theorem 4.8. [cf. Theorem an Theorem D.8 detailed versions] Let Assumption 4.3 hold true and the gradient be accessed exactly. Choose
1. Overall enror: We can specify H. (Na))zo and (mm)== such that,
H
48R" || 1og(6R - -
Σ
N
S
7)
log(7-1)
7=0
accumulated gradient steps required achieve IIV VXi" 1o S.
2. Value function error: We can specify H, (NW) H-1 and (m H-1 such that,
H-1
2 log(2R (1 7)) NA - 7)
log(?" log(>-1)
KmO
accumulated gradient steps are required to achieve IIV - V 11 S...
Remark 4.9. We address each case individually and offer comprehensive versions of Theorem 4.8 in Theorem D.6 and Theorem D.8 delineating explicit selections for H, (Nr) and (m) h=))
To obtain the convergence behavior of DynPG in terms of y close to 1, in Lemma D.9 we derive that log(>-1) is asymptotically equivalent the term (1 (1-7). Combined with Theorem 4.8 find that the required gradient steps for close to 1 behave like
0((1-7) -0g(==1 -2)--21)))
(8)
for the overall error and
((1-7))3 log((11 100-))))-)
for the value function error. Compared to softmax PG, we observe an additional log(c-1) factor in the convergence rate and future research could explore the possibility of eliminating the log-factor. In terms of 7, however, DynPG offers a resilient upper bound, which, in comparison to vanilla PG, remains polynomial in the effective horizon.
5
Breaking the lower bound example with DynPG
In
15 a lower bound example was given for which softmax PG takes exponentially many steps in
the expected horizon (1 -1) to converge. More precisely, it is shown that at least | -0"1 gradient steps required to approximate the optimal value function with 0.15 accuracy. The constructed MDP is designed such that the unknown constant C(r) in the upper bound on softmax PG (see Table !
exponential in the effective time horizon (1 71))) -71 To understand this behavior, we take a closer look at the definition of C(7) == ( (min,es inf On (s))s)) in [66, where a" (s) denotes the optimal action state 8. To ensure small C(r) the probability of choosing the best action should not get close to 0 during training. But by construction in (15), finding the best action in state 8 decreases as long as the probability of choosing the best action a previous state is close enough 1. This results the phenomenon that the gradient steps required converge towards a" (s) grows at least geometrically as increases. However, using DP one can solve the MDP within [S] steps of exact value iteration 15 Lemma 1]. This already implies that DynPG easily circumvents this exponential convergence time by employing DP. As future actions are determined by the previously trained policies, DynPG can evaluate the MDP under a non nta-stationaay policy during training and thereby avoid the above described phenomenon. The upper bound on the complexity of softmax DynPG provides theoretical proof that the needed gradient steps scale at most polynomial in (1 -1-77) -1
6 Conclusion and Future Work
This theory paper contributes to the understanding of PG methods by directly including dynamic programming to gradient based policy search. To this end, we have introduced DynPG, an algorithm

---

that directly combines DP and gradient ascent to solve y-ddicounted infinite horizon MDPs. We provide mathematically rigorous performance estimates (for exact gradients in the main text, estimated gradients in Appendix F) in simplified situations which are typical for theory papers on PG methods. The main strength the algorithm, in contrast to vanilla PG, is to provably avoid exponential y-dependence. We have provided theoretical evidence that dynamic programming, combined with PG methods, can address well-known issues inherent to vanilla PG. This opens up a range of further avenues for future research, such as:
Investigate whether the complexity bounds the exact gradient setting are tight (numerically theoretically) and explore the possibility of eliminating the log- rag-factor.
Analyze the variant DynAC from Section 14] present sample complexity analysis of AC methods. Combining their results to control the critic error with the SGD analysis could result in convergence rates to achieve small value function error in DynAC.
Perform a simulation study of DynPG and DynAC on standard tabular environments and explore how numerical instability issues in standard PG can be overcome.
Combine DynPG and DynAC with deep RL implementations for PG algorithms such as PPO, TRPO.
Acknowledgements
The first author SK thankfully acknowledges the funding support by the Shuns--Sedel-Stiftung e. and is grateful to the DFG RTG1953 "Statistical Modeling of Complex Systems and Processes" for funding this research. The research of SK was also supported by the research project "SURF Smart, user-centered regional flexibility platform for grid and market" funded by the Federal Ministry for Economic Affairs and Energy [03I14092D]. The research of the second and third authors (XZ and TB) was sponsored in part by the US Army Research Office and was accomplished under Grant Number W911NF-24-1-00855.
References
[1] Alekh Agarwal, Sham M. Kakade, Jason D. Lec, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
[2] Mohammad Gheshlaghi Azar, Vicenç Gómez, and Hilbert Kappen. Dynamic policy programming. The Journal of Machine Learning Research, 13(1):320733245, 2012.
[3] Bagnell, Sham M Kakade, Jeff Schneider, and Andrew Ng. Policy search by dynamic programming In S. Thrun, L. Saul, and B. Schölkopf, editors, Advances in Neural Information Processing Systems, volume 16. MIT Press, 2003.
[4] Amir Beck. First-Order Methods in Optimization. Society for Industrial and Applicd Mathematics, Philadelphia, PA, 2017.
[5] Dimitri Bertsekas and John N Tsitsiklis. Neuro- Mauro-Dynamic Programming. Athena Scientific, 1996.
[6] Dimitri Bertsekas. Dynamic Programming and Optimal Control. 2. Athena Scientific, Belmont, Mass, cd. edition, 2001.
[7] Yuhao Ding, Junzi Zhang, and Javad Lavaei. Beyond exact gradients: Convergence stochastic soft-man -fx- policy gradient methods with entropy regularization. arXiv Preprint, 1xXiv:2110.10111 2022.
[8] Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 1587-1596, PMLR, 7 2018.
[9] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pages 267-274, 2002.
[10] Sham M Kakade. A natural policy gradient. In Advances in Neural Information Processing Systems. volume 14. MIT Press, 2001.
10

---

[11] Sham M. Kakade. On the sample complexity of reinforcement learning. PhD thesis, University College London, 2003.
[12] Sara Klein, Simon Weissmann, and Leif Döring. Beyond stationarity: Convergence analysis of stochastic softmax policy gradient methods. In The Twelfth International Conference on Learning Representations. 2024.
[13] Vijay Konda and John Tsitsiklis. Actor-critic algorithms. In Advances in Neural Information Processing Systems, volume 12. MIT Press, 1999.
[14] Harshat Kumar, Alec Koppel, and Alejandro Ribeiro. On the sample complexity of actor-critic method for reinforcement learning with function approximation. Machine Learning, 1 11(7):2433-2467, 2023.
[15] Gen Li, Yuting Wei, Yuejie Chi, and Yuxin Chen. Softmax policy gradient methods can take exponential time to converge. Mathematical Programming, 201 802, 2023.
[16] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6820 6829, PMLR, 18 Jul 2020.
[17] Mattco Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic radiaece-reduced policy gradicnt. Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4026-4035. PMLR, 10-15 Jul 2018.
Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. [18] Matteo Pirotta, Marcello Restelli, and Luca Bascetta. Adaptive step-size for policy gradient methods. In
[19] B.T. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics, 3(4):864 878, 1963.
[20] M.L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley Sons, 2005.
[21] Bruno Scherrer. Approximate policy iteration schemes: comparison. In Eric P. Xing and Tony Jehara, editors, Proceedings of the 31 International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 13 1314-1322, Bejing, China, 22-24 Jun 2014. PMLR.
[22] Bruno Scherrer, Mohammad Ghavamzadeh, Victor Gabillon, Boris Lesner, and Matthieu Geist. Ap- proximate modified policy iteration and its application to the game of tetris. J. Mach. Learn. Res.. (6(49):1629-1677 2015.
[23] John Schulman, Sergey Levine, Pieter Abbecl, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Proceedings of the 32nd International Conference Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1889 1889-1897,7 Lille, France, 09 Jul 2015. PMLR.
[24] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018
[25] Richard S Sutton, Hamid Maci, and Csaba Szepesvári. A convergent o(n) temporal-diiffrence algorithm for off-policy learning with linear function approximation. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates. Inc., 2008
[26] Richard S Sutton, Hamid Reza Maci, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods temporal-difee differeeee learning with linear function approximation. In Proceedings of the 26th annual international conference on machine learning, pages 993-1000, 2009.
[27] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, volume 12. MIT Press, 1999.
[28] Simon Weissmann, Ashia Wilson, and Jakob Zech. Multilevel optimization for inverse problems. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory. volume 178 of Proceedings of Machine Learning Research, pages 5489-5524, PMLR, 02-05 Jul 2022.
[29] Ronald J. Williams. Simple statistical maddient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3):229 256, 1992.

---

[30] Lin Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23(282):1-36, 2022.
[31] Rui Yuan, Robert M. Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera, editors. Proceedings of The 25th International Conference on Artificial Intelligence and Statistics. volume 151 of Proceedings of Machine Learning Research, pages 3332-3380. PMLR, 28-30 Mar 2022.
[32] Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Başar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58(6):5586 3612, 2020.
[33] Xiangyuan Zhang and Tamer Başar. Revisiting LQR control from the perspective of receding- horizon policy gradient. IEEE Control Systems Letters, 7:1664-1661 2023.
[34] Xiangyuan Zhang, Hu, and Tamer Başar. Learning Kalman filter with fine- ine-grained sample complexity. In 2023 American Control Conference (ACC), pages 4549-4554, IEEE, 2023.
[35] Xiangyuan Zhang, Saviz Mowlavi, Mouhacine Benosman, Tamer Başar. Global convergence of receding-horizonn policy search in learning estimator designs. arXiv Preprint, arXiv:2309.04831, 2023.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction summarizes the theoretical findings in this paper; all claims are proven.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

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

---

Answer: [Yes]
Justification: Code to reproduce the experiments is available in an anonymous repository, see Section[B]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
ssicnlolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experimental setup and all parameter details are explained in Section Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The experimental results are numerically stable and you achieve the same results in multiple runs. Behavior for different parameter settings is discussed Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
15

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Toy example which can be run without specific computer resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We agree with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
19

---

A
Notations
state space
A
action space
p()s,,))
transition kernel in (s,4); in (S)
r(s.0)
expected reward in (s,a)
y E (0)
discount factor
R" >
maximal absolute value of rewards
| max [xy
supremum norm for E Rd
n: S A(A) e
stationary policy (and stationary policy set)
Th {Th 1....... ma e II
h ttep con-stationary policy (and the set of all such policies)
initial state distribution
VyTh (p)
h-step discounted value function; policy Th, start distribution μ optimal discounted value function
(2)
optimal policy s.t. V (p) V (n) optimal discounted h-step reward function optimal h-step policy s.t. (r) v (w)
(4)
V = and To 0
conventions used in the manuscript
Q (s,
h-step Q-function
one-step Bellman operator under policy
T;
one-step Bellman optimality operator
V
stationary greedy policy after V e Iils
Q a)
Q-matrix obtained from V RiS)
Th. Nv.
learning rate, number of training steps in epoch of trained policies in the algorithm
trained policy by DynPG in epoch set of trained policy by DynPG from h to stationary parametrized policy
#
me
(Tx)00
apply na in loop for the infinite horizon problem
B Details of the Numerical Example
The example is an extension of 24 Example 6.7], which has been used to compare different variants of Q-learning algorithms, as it suffers from overestimation of the Q-values. Since the overestimation problem in Q-learning and the committal behavior problem in policy gradient are closely related (8), we decided to use this example. The example is certainly artificial, as the number actions and the rewards in the MDP are chosen to trap policy gradient from convergence. If we vary the MDP parameters from the current setting. DynPG consistently performs better, but the advantage over vanilla PG will become less significant. The code is available at httpss //githu.. thub. com/Sara- Kleinn/ttruccuureattttesss DynPG
20

---

The MDP is defined as follows:
The state space given by S = {0, ..... 6): States 0, 6 are the terminal states and states 1, 2, 4, 5 are the initial states. We sample sp uniformly from 5).
The action space is given by A = ( 299}.
The state transitions and staeedeepn actions visualized in Figure 3 Each node represents a state, with squared ones being terminal states and elliptical ones being initial states. Each arrow represents action that deterministically transits from state another. From state to state 0, there is total of 300 possible actions, succinctly visualized using the dots.
Taking any a E from state 1 reaches state and receives reward of r(1,a) N(-0.3,10) 10).
Taking any of the 5 possible actions from state reaches state 5 and receives the reward of r(4,a) ~ (1.25, 1.25).
Taking any of the 5 possible actions from state reaches state 6 and receives the reward of r(5,a) ~ (1.25, 1.25).
Taking any of the 3 possible actions from state receives the reward of r(2, = 0.
Figure 3: Visualization of the MDP state transitions.
Experimental setup:
We evaluated the performance of (stochastic) vanilla and (stochastic) DynPG under two different discount factors, 7 0.9 and y 0.99. We used the tabular softmax parametrization studied in the convergence analysis for both algorithms. In DynPG, we used the 1-batch Monte-Carke estimator to sample the gradient according to Theorem A.3. In vanilla PG, chose the classical REINFORCE 1-batch estimator with truncation horizon 3, such that the estimator is also unbiased due the episodic setting (the maximum episode length in example is 3).
In DynPG, we chose the step size 77, and number of training steps N₁, according to Theorem D.6 and Theorem D.8 and only fine-tuned the constants 2 and 45:
1-2 7hh = R
h+1
N
45
We want to emphasize that the choices of Th and N,, consistently perform well under different choices of y (see therefore second convergence picture with y 0.9 in Figure(4), which underscores that the algorithmic parameters developed in our theory also provide good guidance in practice. For fair comparison, we fine-tuned 7 = 2 for stochastic vanilla PG, which is much larger than the pessimistic (1 ~3) suggested in [16].
21

---

gamma 0.9
1.0
0.8
Succass Prabability
0.6
0.4
0.2
DynPG
0.0
0
200 400
600 800 10001200
Interactions with environment
Figure 4: Success probability of achieving the sub-optimality gap of c = 0.01 the overall error.
Auxiliary Results
C.1 O-function, Advantage Function and Greedy Policy
First, we define the state-action value of Th- E 11n-1 at any (s, S x Aas
Thh as, = (1 Aw 1(:18))
(r) So = s, A. =
ar(s,a) +7 Σ
p(s'ls,,,,s, ((
e'ES
For 2 and ny E II we define the advantage function
A (8, = Q (88 ViTh (s)
(9)
For V S| greedy policy Y chooses the action that maximizes the Q-matrix
Q"((saa)=((s.))) Σ p(sssss.aVV(ss SES,aEA
.'ES
By the definitions of the Bellman operators, holds that a policy x is greedy with respect V if and only if T = TVV 6
C.2 Dynamic Programming Finite Time Approximation
Lemma C.I. Let Vo = 0. For any h 2 1, it holds that
(0) (s) = T (V, all S,
(i) [VV V < - R.
When multiple actions equally optimal, V selects arbitrary among them.
22

---

Proof. C.f. 66 Prop. 1.2.1] The first claim, follows directly from the definition of the Bellman optimality operator
(8)
sup
E
no(als)
r(s,a) +2
Σ
p(s (s')
Tll
aEA
e'ES
r(s,a) +7 ((s('(8,
Vh V (6')
(6')
= aEA
sup R
e'ES E
-V-()-))(+)).
For the second part, fix h 2 O. Recall that x² E II denotes stationary optimal policy for the infinite-time problem and Tx E І an optimal non-stationary policy.
We divide the proof of the second claim into two cases.
Case 1: Assume that V (s)
(s) s for all E S. Note that (s) ((Ti>> (s), where (T7))= denotes that we apply the finite time policy nx in loop for the infinite time problem. We have
V (s) & Vi (s) - v- (s)
h
E
Σ 11
y'r(S
=
(1 (1mmd 6o) 18)18,)
S 1 (S
R
R
where R' bounds the absolute value of rewards.
Case 2: Assume that V*(s) - (s) > for all s S. Note that VT (s) 2 Vr (s) due to the
optimality of मं over the finite-time horizon. Further, by the definition of V (x( = V (8), we have
V (s) Vi (s) < V (8)
VTT (s)
8
Σ
(r((S.,
S S. (11..) 9141~p pl (S,)A))
km
7/ R
R
7
1=/
Hence, we arrive at
nh
lIVe
V
max sEB
(2)(s)
(s)l
R²
C.3 Error bound for stationary policy
The following Lemma is inspired by error bounds presented in 16 Sec. 1.3]. The purpose of this result to establish validation of applying the last policy trained DynPG as stationary policy.
Lemma C.2. For any V E TRIS) and policy æ E II it holds that
(V Vl
| V
1 1-?
Proof. Consider any state E S. Since V is the unique fixed point of the operator T", we have
(g(s) - T Σ x(a)s)r(s,a)++
Σ {als)
Σ
p(s' p(s'|s,
e'ES
23

---

This implies that
(s) - V(s)
Σ T(als)r(s,a)) + Σ t(als)
[((
Σ ((als))(ss Σ T(als)
- V(s)
E T(als)r(s, a) + Σ T(als) Σ [p(s'ss,a\V(())
+ Σ T(als) Σ p(
V(6)) V(s))
aed
(V) V(s) +7
Σ s(als) E [)( V(8)),
S'ES
for any s S. We define the mappings + 9=(s) (V) V(s) and Jz(s)
V (8) - V(s), E S. Then, the above equation simplifies
- (x) +7 Σ Σ
aEA'ESS
By definition J, satisfies
Js(s) Σ Tals)) go +7) +7 En(((s,a)dr())
s'ES
for all S, and therefore solution of the Bellman equation with auxiliary reward function (s, a) + F(8,a) = (8). Note that this reward function also bounded and by the uniqueness of the solution of the Bellman equation it has to hold that
(x)
* gz (xx)) = (x) +
E
1 (5x)
A k=0
So= A
Se4rmp(-1Se As.
A==1
Se1rmp([Se.A)
Define 3 = min In (s) and B = max,es (s). Then,
8
79
73
3
(x)
1- S Jx(s)= S (8) +
1-
1
It follows that for any S,
[+x(s]] max,es (s)
1 1-7
By definition of ga and JR this yields the claim.
C.4 Policy Gradient Theorem for DynPG
Theorem C.3. Suppose that Th II fixed for any h 2 with the convention no = Q. Then, for any differentiable parametrized family, say (To) (i.e. O >> To(s,a), a), 0 E Rdd is differentiable for all (8,0) a) S x A), it holds that
VoViNo mo (s) (s)=
E A=e(A)
(AIS)) (8. (8,
Proof. The proof can be found in 12 Thm A.6]. However, we will need an index shift and additionally consider the discount factor 7. An h-step trajectory Tr (so, ap,.... 8h- (h-1) under policy (To, Th) and initial state distribution d, occurs with probability
h-1
I [o) (Th) = 65(())TT((agl5))
II km
p( ----1------ -1, a2-1)))))))))) (00-11mT(a (sk).

---

Then, the log trick yields that
Ve log(p! (Tr))
Vo (1og(6s log( (T (o)) + log(p(s; 8k ax-1)) + log TT (axlss))
Vo log ( so)).
Let W/ be the set of all trajectories from 0 to / 1. Then, the set Wh is finite due to the assumption that state and action space are finite. For a E we have
V VoVilaamm ma) (s)
h-1 E (skskka))
= V E
p T
The T.W.
k=0
h-1
Σ
Po (T. (Th) Vog((p (T.
(T0. (Tn))
Σ
**h rskk ax)
Th EW,
Σ
(e. (Th) log((To
T as)
=
Ps
EWa
k=
h-1
Vo Volog(T
(Aoo(("(AAo(S)) (AolSo)
Σ
r Aa))
=
8o A0 (-18)
(e (-15.)
k=0
h
=
Vo log(== (Au So)) S
E
Σ
y (rr Ax] Ao)
Ap
=
E {=
Vo (o
C.5 Performance Difference Lemma
Lemma C.4. Let Th+1, Thh11,T411 11 Then, it holds that
VTh (s) 1. (8)
E
Σ 1 A.)]
So=s A (-18))
(...mp((1S..A))
(ii) If both policies only differ in the first policy, iee. Thh The then the above equation simplifies
* (8)
Vi h+1
(8)
(A Ao)
(10)
Su A0
Proof. A similar proof can be found in 12
Thm A.6]. However, we will need index shift and
additionally to consider the discount factor 7. First, Thh1, Th41 I1++1 be two arbitrary policies.
We have
1Th (8) 1+1
th
(s)
E S0=8,A,TT (-1S,)
Σ
rrSs,, A.]] vitl (8)
(111M)(((S1.A))
t=0
E
rrr A1) + Σ
7 Th+1 (
h+11=
(St)
Σ
7 VV (V (S.)) - -itTT (s)
A - (-1S.)
(S
t=0
t=
0=
E
Σ
rr Ar) + Σ
'V t h (St)
(ht1'((ss)
h+1-t
Σ
2 1+1-1 -
A (-)..) 14
1=0
t=1
t=
25

---

h
h-1
h
yr((S,. A1) +
Σ
(S(+1)
Σ
"
S (11))) (
1=0
1=U
1=
? (r() + Vi - (S(+1) - (S))
Ab= A (11))) 8p11 As)
1=0
7 ( Ad) - v=lli
Sa=a, (11))) St-rmpl Ae)
(S A0)
S0=a, (1)))) St-1mp(-1S,,d (.)
t=0
where in the fifth equation we used the convention Vo = 0, in the sixth equation the definition of the Q-function, and in the last equation the definition of the advantage function. Second. suppose that th+1 and T/41 agree on all policies besides The i.e. л = n Then, for any > 0, holds that
E
A Ar)
A (St,
S0=s,A - SUIIN((1B.AA)))
Σ (n(as)) Σ p(s)ss,a)
E
A Ant1-i A (St, Ai)]
So So=a A A (11)))
eEES
S1t1
= Σ (n(als) Σ p(s)|s,a)
( A1) - V (5.)
So=d' A (1S)) (ei
aEA
#'ES
= 0.
This proves the claim.
C.6 Convergence under Gradient Domination
Lemma C.5. Let Rd + RK be L-smooth (i.e. L-Lipschitz continuity of the gradient), f sup, f(x < cC. Denote the gradient ascent procedure by kn+1 2,, &oV [ for some I1 R
and a = 1 and assume that f satisfies the following gradient domination property for some b along the gradient trajectory.
(f(xx))l =b(("=((zx)) Vn 2 1.
Then the convergence rale
2
f - f(xm) 5 abin'
holds true if f* f(x1) S 25.
Proof. We apply the descent lemma of smooth functions
Lem 5.7] on -f and obtain
L
f(y) 2 f(x) V5(x)
_ Ily xx12.
Now for gradient ascent updates we have that
L
[(F+t1) 2 [( Vs(x)) (#n+1 xn)
- I1 x.
Laz
[((m)) aalV//(am)))
2
= =((x) + (a- ||Vf(=n))1
La²
26

---

It follows that
f - (=xxt))) - ((xn) - (a La²
| ff
2
Exploiting the gradient domination along the gradient trajectory results in
f - f(nn+1) S f((nn) - (a-
La²
18 - f(xx))²
2
As I. we have
8²
f -' f(nnt)))) - f(
(f* f(m=)))
2L
When /" - [(x) S
2 az., then 1 - [(nn) S abn by 12 Lem. B.7].
2
D Proofs of Section
D.1 Proof for Section
Proof for Proposition
4.
Recall the claim:
I|V - V
V2
sup v
+
sup v
sup
VH ST
m.. 500
80 -1
sup
VH
V 11
+
V
1oc
Bo.... -1
R
sup
V
10
1
1
H H-hh-11 sup T (V
#1 h+1
# #1 #+1
V
11
The first inequality follows directly from the triangle inequality of the supremum norm. Note here that we cannot simplify the first error further as will depend on the chosen parametrization. Before we prove the second inequality, note that
sup f() sup g(0 S sup [(0) g(0)
for any two functions f.g RRd + R. supo f(0) supo g(0) 2 0, then
sup sup [() sup supg(0) (0) = sup s(0 sup (0) S sup( ,(0)) S sup [5(0) 2(0)
0
0
0
0
sup, (00) - sups g0) < 0, then the role of ʃ and g are swapped. Thus, we have |usup T (V) sup T (G) dasul (T (V) T (G))ll I v1VV Glloc. (11)
8
e'
We treat the second, third and fourth terms separately. For the second term, prove that sup, V sup 04 V (
# R'
similar
1-7
20
[5
to Lemma C.I Let E S be arbitrary but fixed. If Ifsu ViTe (s) -usss _ 9z
V/
(s) 2
0, then
Top
supp W (s)
sup 2y
(s) S sup V (s) sup
V
0
0
s sup Vi (s) V (s))
8
rrr Ar)
sup
A ( (S S4+1<p(1 -p( Ac)
7 .
7 R = 1 R*
t= H
27

---

where we used 1I in the second inequality.
On the other hand, if sup, (s)
1 11 1 (8) < O, then
suP8 su........ 0H VB
foon Too
sup
VH
sup
V (8)
0 OH
Tuoe
(1 100 Now (s)
sup 0a....00i
H
sup
Vo0
on. 0H-1
Too
(F00
D)w (5)
sup
F1
(8) Voc
E''r(S Ao)
sup
8 .n Se=eAAeT an (-18))
L(=H
11 (1
Rt
R
Collecting these together, we obtain that since E S was chosen arbitrary. For the third term, we show that
supa Vx
supe
0p-1
H
100
S
I-7
R
H
sup
VH
ATo n- 1 Nogk
1l S
H H-h h
Issup T (V,
(12)
80....,911-
h=0
9
holds for all 2 by induction. For H we have by 55) that |sup Vi
Vi 1ox0
sup 7 (Vo #o
-
7
with the convention Vo = and t5 = 0. So assume that Equation 12 for H + we have
holds for some H 2 1; then
sup
V
VH+1
Toa
+
8s.
V moo - T (V x
sup TH
sup
0h
0u....0-1 0H
V --e mo0m
< sup Hh
7
sup
sup T (V
Po 9z
88
+
sup OH
(V
7
sup
H
sup TH (V
T (V (
Op.....H
0x
H-1
7
1| 1n---1
ssu
T (V #2) a (1, |loo +
T - 7 (V +
h=0
B
8
H
H sup
T (V/ -T Th (V lbb.
0=
where we used 5 as well as 11 and the induction assumption. This yields the desired claim 12 for all 2
For the fourth error term, we have to deal with the error of applying the final policy as stationary policy. We use Lemma C.2
arrive at
1
||V
#1
1l
S
(V#
- *H 11
- 7
1
|
|
V 1loos
where we used again 55) in the last line.
28

---

Proof of Corollary 4.3 obtain
Adjusting
to zero approximation error and exploiting Assumption 4.2 we
R H
H-1 Σ h=0
||V V#= 00
H- 1----11 en + for H +
7
For the second part of the theorem note that V converges in the supremum norm Vo by the first part. This implies that V is Cauchy sequence with respect to the supremum norm, i.e. " =0 for H co. The claim follows directly from Proposition 4.1 I1
D.2 Proof of Theorem 4.6
Before we prove Theorem 4.6 we will discuss the similarities and differences between DynPG and the finite-time Dynamic Policy Gradient (FT-DynPG) Algorithm proposed in [12].
1. FT-DynPG has a prefixed time horizon H and trains policy backwards in time. contrast, DynPG adds arbitrarily many policies in the beginning and can therefore be applied without prefixed H.
2. Given a fixed time horizon FT-DynPG returns non-stationary policy #ū for an 1/-step MDP, but without discounting = 1. When DynPG is run for the same fixed number of iterations H. then FT-DynPG and DynPG only differ by the discount factor: The value functions Vh,H defined in [12] for FT-DynPG are by the strong Markov property equivalent Vo,H -h via index shifting. The function Vo differs from our H h-step value function Vn defined in only by the discount factor 7
In order to prove Theorem 4.6 we have to adapt the proof for [22 Lem. 3.4] to an additional discount factor. Note, that we cannot use [66 Thm. 2] for bandits, as we consider contextual bandits. Further, we cannot use [16] Thm. 4] with = O as they just consider positive rewards in [0. 1] which is inconvenient for our contextual bandit setting where the maximal rewards grows when we add a new time-epoch in the beginning.
Therefore, we will adapt the proofs functions.
16
22 and start with deriving smoothness of our objective
Lemma D.1. Suppose Te softmax(0). Then, for arbitrary II and μ E A(S), the function
m (μ) is -smooohh with La- 28 (1-11 A41)
+ h+1
(1-7)
The proof is similar to 12 Lem. B.8]. Note that we can interpret V [ma. h++1 (14) as a contextual bandit problem, iee discounted (infinite-times MDP with discount factor 0. The reward of the contextual bandit problem is almost surely bounded in 1-
Proof.
1- h+1 R*). because
- h+1
R
R
t=
We apply 31 Lem. 4.4 and Lem. 4.8] with Rinxx
1-ght1 1-
R G2 G² 1 \ and F
to obtain the smoothness constant L,, 2 (1-ah
(1-7)
Second, we obtain the following gradient domination property.
Lemma D.2. Under Assumption 4.5 holds for any Th E 1I that
V m.) (H)ll < min me(a" (s)ls)
v. mm)
(w)).
Vh+
sES
where a" (s) denotes the (unique) action taken after the greedy policy a V/ Remark D.3. Without loss of generality, we assume that the action a" (s) is unique for any fixed future policy The otherwise can consider mina optimal action in e Te s)ss.
29

---

Proof. First note from Theorem C.3 that under the tabular softmax parametrization we have
VoV. h+1
VoV. (xo (1)
Σ ((s)
E
S=8,ANTO(15)
Hence, with the derivative of the softmax function
Log(To(als)) = 1 (o=od) (I(a=ar) No (a((a(s)) 00()',a')
holds that
20(s',a')
(0=0() 8=s Am30(1))
E
[11 (1(A=or) - =o(a'(s') Qhti A)]
1 (s=0)
Tola'ls') (8', To(a'ls')
E
12 (S, A)]
S=s'
1 1 (s' a')
h+1 vil7amm) (s'))
( (s') ( as',
(13)
We deduce from Lemma
C.4 Equation (10). that
T' Thh (V (())
E
A (So, An)]
So Ap (-15)
Finally, the rest of the proof is derived as in 12 Lem. B.9]
2v (ma.m
Vo VoV. (m)
(w)ll2
Σ
((s))
h+1
00
SES
oy (Ta.m (s)
Σ
Σ 1
M(s)
h+1
)1²
]
a0(s',al)
S'ES e'EA
Σ ((s))o(d'(ss)A
(T (s, ]²
a'EAA
WES
(s))) (mo.mN)) (s))a(s)))
ES
Σ ((s)To(a" (8)]8)
ATre (S,
Sms,A V (-18)
#ES
((s) (s) (T (s) - -T (V,
SES
min
To (s){s) (T" (V," (H) - T (V (H²),
SES
where a" (s) denotes the action taken after the greedy policy nt V/- (c.f. Remark D.3).
The next step is to show that the term min,es ae(a" (s){s) can be bounded (uniformly in E S) from below by [A] along the gradient ascent trajectory, when softmax is initialized uniformly.
Lemma D.4. Let Assumption 4.2 hold and denote by (0x) the gradient ascent sequence in epoch h 2 0 of DynPG under the fixed future policy क1, E II Suppose further that Th 2R
1-y 1-2 is
chosen in Theorem 4.6 Then, for any S. it holds that
min no, (a (s)ss) R20
A
where a" (s) denotes the (unique) action taken after the greedy policy n. Vi: (see Remark D.3
30

---

Proof. The proof is adapted from [6] Lem. 5] and 12 Lem. B.10, Prop. 3.3].
First, we define the sets
(1) {0: (s)ss(s)ss) 2 no(als)Va # (s))
gyltu.mil (8)
oyinuiii (x)
(2 {0:
h+1
h+l
ta # (8))
08(s, a (s))
08(s, (s)
Claim 1: It holds that On R2 bu+1 E R2. To prove this claim, we first deduce from (13 that
ov (s)
avim (s)
z 00(s, a' (s))
a0(s
(14)
ne, (a){s)))4 mm.
(s, a (s)) 2 To,, (a|s) h41
(Ta ()
Let # (s) be arbitrary. We consider two cases to proof claim 1:
Suppose that Te, (s){s) 2 (als) for any a * as(s). Then, is holds that (n (s)) 2 On(s,a) a) by the definition of softmax. Next, as On R2. we derive
on Ax #1) (s)
6 (n+1(s,"" ax (s)
h+1
00n(s, a" (s))
O (1 00 a²
(s)
2 a) + (s)
0s a)-
Thus, by the definition of the softmax function, n (s))s) a + a" (s). Further, because a (s) is the greedy action, we arrive at
To (als) for any
A+1 (T 11 #1) (s, (s)) 2 no, (als) 11 # (s,
To... (s)ss)
such that Ox+1 E R2(3) by (4
2. Suppose that Te, (a" (s)ss) < ne. (als) for any a # a" (s). Then, 0, a" (s)) - On (8. < by definition of the softmax function. As 0n E R2(s), it holds that
as (s))(8,a)
2 On(s, a" (x)) + mus(s avima (,( mm((s)) h+1
Iy (mo (s)
80(s, (x))
00(s,a)
2 On,sa (8)) (s,
Thus, we obtain
- 1i=eep(On=+16 (x)) - On+ (s, a))) S es,
0g a))) < 1.
By the ascent lemma for smooth functions [6 Lem. 18] it follows monotonicity in the objective function (due to small enough step size 17h
T% with L, the smoothness constant
in Lemma D.I such that (T "Te.+1.**. * (s) 2
V [T... #i. (s). So.
h+1
h+1
11 *tie (s) V
e--epp (0p (s, (s, (s)) 0 (,
2 (s, (s))
$ (1 exp(O, (s)) (s a))
2h (s, a" (s)) ((o, #1) (s)
We rearrange 14 and obtain that 0 R2(s) is equivalent to
th 1 (s, a (s)) U O (s, a) 2 (1 exp(O a (s)) - 0x A (50 (s, a (s)).
31

---

We deduce by On E R2(s) that
(1 - exp(ppxx1 (s)) - 0n+1 (Rhti 11 (s)
2 (1 - exp(On(ss,0 - On(s, (s v/ll (s)
I ( (s)) (s.o.
and thus 0 E R2(s).
This proves claim
Claim 2: If fn, E (s), then it holds that To.. (a (s){s) 2 Te., (a*(s)
Line by line as in Claim of [12 Lem. B.10J. Claim 3: It holds that On E R((s) = On E R2(0).
Let On E (s). As a" (s) is optimal we have for any of a" (s) that
(s)) 2 mm. # (s. (oon hid (s,a" A+t
Further by On E (s) it holds
Te. (a" (s) h-1
t5em aho 26 (8) (T0, ( M a" (x)) 2 no, (als) h+1
Hence, by (3).. we deduce that 6n E (s)s).
Conclusion of the proof by combining claim 1, claim and claim 3:
Since Op is initialized such that softmax is the uniform distribution, we have that Og E (s) for all
8 E S. By claim 3. we have that Og E R2(s) and by claim 1 follows that On E R2(s) for all n 2
and all s S. Finally, by claim 2, it follows that min Te., (s, a as)) Too (s, a (s)) 1t for
any S.
We finally we collect all preliminary results prove Theorem 4.6
Proof of Theorem 4.6 First, note that the tabular softmax parametrization can approximate any deterministic policy arbitrarily well. As optimal policies in finite horizon MDPs are deterministic, we have that suPSER $I1 V vy(To.**)) ())))))))))))))))))()) (s) = T (V, (s) for all E S (zero approximation error induced by the parametrization). Moreover, for any 8 E E
T (V, (s) T (s) = Σ m(s') 10'=
(V (s') T (
H(s')
s'ES
$ |
(T*(VV, (u) - (v
14
For any O E Rd it holds that
1 1- b+1
2)_4/2
(V T (V (s) T (V )s) <
1² Ln
Th 7/h.
Moreover, by Lemma D.I the function 0 + #1)
(1) is -moohhh and fulfills the gradient
domination property along the gradient ascent steps with b |Al (Lemma D.2 and Lemma D.4 Hence, we can apply Lemma C.5 with
J a Th 2F-
and No. such that
4|A R (1 )
T (V - TON (V (
(1-7)Nn
By the choice of N₂, we deduce for any s E
TT (t) (s) <
1
(T" (T*
TMNN (V (()) S En
11
00
which proves the claim.
32

---

D.3 Proof of Theorem 4.8
We will treat the two cases of value function error and overall error separately and start with the value function enror.
Value function error. Note that under the tabular softmax parametrization we have zero approxi- mation error and the upper bound in 7 simplifies to
R
H-1
IIV
VH a mo S
cb
k=0
where сд upper bounds step optimization errors
suPoERs T (V
h+11
1l
cording to Theorem
In order to minimize the accumulated number of gradient steps, we have to solve the optimization problem:
H-1
1R (1-?)
1 (1 x+1) (11
min
N₁
H.
h=0
4=0
(15)
R
H
subject
H -- c/ S
1-7
k=0
In 28 Sec. 3.2] similar optimization problem was considered and it was shown that asymptotically
(as e + 0) suffices to bound both error terms the constraint by 5. The first condition, i.e.
y K
1-y < 5. leads to the criterion 2 log, ()-z))) To minimize the number of gradient steps we
fix H = logg (
(1-7)e) 212
).
It remains to solve the following optimization problem
H-1
H
min
anch
subject to
Σ h=U
H H-h- en S 2'
(16)
(0h) .0.0
A=0
with = -| 1R 1l (h 1)(1 (+
We provide solution of the optimization problem (6 by solving the following more general one:
Lemma D.5. Fix H > O. Let (an) and (bo) be strictly positive sequences. For any d 0 the optimization problem
H Σ
H-1 bnck S d
min (cx)
anch
subject to
Σ
h=0
h=0
optimally solved for cı = Ca.H
with CH.d = d( E (an bis )
Hence, the minimum of the optimization problem is given by 1 - ( (anbn)
Proof. The result and the proof is inspired by 28 Lem. 3.8].
We solve the constrained optimization problem by employing the Lagrange method, i.c
H-1
H-1
Σ h=0
anch
Σ h=0
bnch d
X.(e
The first order conditions are given by
#-1
-0 -2 + Ab,. = =0 vh = O,..., H - 1,
and
by d = 0.
hmo
33

---

deduce from first equations, that there exists a constant Ch such that c4. CH.a for all h O..... H - 1. Using this in the second equation solve for the constant
H-1
Ch.d =
7=0
Using the minima Ch = CH.d minimum
bn. (an)
in the optimization function >
anoh we obtain the
H
H-1
bn
H-1 1
2
Σ ahCh = Σ
(anbn)
Σ
(anba)
Hid
= H
Oh
0=0
h=0
h 1=0
h=0
Finally, ready state the detailed version of Theorem 4.8 for the value function error.
Theorem D.6. [Detailed version Theorem 4.8 (2.))
Let Assumption
4.5 hold true and the gradient be accessed exactly. Choose > O and set
H log
(1--)))
(1 7)
2R"
H-1
((1 (1- (1 -)))))))
(1- (1
-1
- -
Eh
1-7
2R' (1 x1+1)
N 4R (1 - +
71-
for = O.... Then, the non-stationary policy # obtained by DynPG under exact gradients
achieves
|
bl The total number of gradient steps are given by
#
88" loo (2R" (E
Σ NA
(1 2E
log(y-1)
11 00
h=
Proof. First, note that the choice of in the theorem is the solution of the optimization problem
min A
(ea) (1 71 1
H
A+1)
H-1
subject to
Σ
7 H - ca
S 2
C₁
h=0
h=0
Therefore, choose aA = (1 g
bn
n 1 h-1 Cr En and d = in Lemma D.5
where we
excluded the constant 4 2 (1-7) 1t
Then,
1
H
bp
é
((1 (11 -- (
eh = CH.d
t=0
is the optimal solution to this problem. For H log log(7)
we have that
1-y
Rt'
< 5
Using these (en) (-1 in Theorem 4.6 results in value function error for DynPG bounded by
R 1-7
#
|IVo - ~ 10 <
+
Σ
7
H H-
5
c
=6. e.
(17)
2
h=0
34

---

For the optimal complexity bound we ignore the Gauss-bracker in N₁. and derive
H-1
Σ No
Σ
anch
(1-
h=0
H-1
Up
(1-7)
4e
H.d
ah
h=0
C
(anbr))
(1-?)
H.d
h=0
4R"
(anba) 2
(1 (1-7)
H-1
((1 - ) )1)))))
(1 7)
hm0
8R ||
(67 H6 - -
(1- 7)
h=0
8R" 1|12
1
H
--h-1 - ")
(1 7)
h=0
where we used Jensen's inequality in the last step. Further it holds that
|4 (1
Σ N
H
Σ
8
h-1
-
7)
11
4=0
8R |A
1
H
(1 7)
11 10
h=0
88"
11
(1- 7)
11
1
8R" H [1
1
2E
11
Finally, note that we can rewrite H to be
(1 -)7 (1-2)e)
log
(1~2)c 21
llog(11 - -1-12-1121 )
H log,
21"
=
(og(>)
1og(>-1)
Overall error. To deal with the overall error, first derive the following upper bound.
Lemma D.7. Assume zero approximation error, i.e. T sup, T Further, assume bounded
optimization errors (V - T (V )l S Cb for all h = O..... H. If CH S (1
7) EH 7 H then the overall error of DynPG is bounded by
V
V 1l:c I
3
R
+
H-1
Σ h=
1
1-
1
Proof.
First, we have by triangle inequality
V 1lo0 S || ||
Vo + V
V |l.o.
H+1
35

---

By Proposition 4.1 we obtain, under zero approximation error, that
H
H h +
H R
H-1
#+1 Vallo + 1V22 VH
20 S
+
7
h
ch.
1
h=0
h=
By the assumption eØ S (1 - 7) ~h==0 ?
11-1
Eb. it holds further that -1
H
H-1
H-1
M-h h ch
Σ
--
ch
cH S
1-
H-
Ch-
h=0
h=0
h=0
We obtain
27 R
--1
00
+2 2
Σ
H
h-11-11-
Eh.
h=0
We deduce for the overall error (by Proposition
4.1 and under zero approximation error) that
R²
H-1
1
27 H
R
H-1
II
V 1mx
+
H-
+ 1-7
+ 2
Σ 7
H
h
1 1-7
h=0
h=0
3
H R
+ Σ
H-1
H - cn.
$
1-7 1
1-7
h=0
R
important notice that the overall error is upper bounded by the same error terms,
T-7
EMI 7 HH-h-len Eh. as the value function error (under zero approximation error) up the constant T-y.
3. Thus, we can obtain the result for the overall error by substituting e with (1-T)s
3
Theorem D.8. [Detailed version of Theorem 4.8 (1.)
Let Assumption 4.5 hold true and the gradient be accessed exactly. Choose e > 0 and set
log,
6R 1
e(1 7)
11 1
((11 - (() ( -H- -2 vh= = - H
( (1-aht)))
Ch =
6
4=U
7)E
EH
6
1 7
Th 2R" (1 x++l²²
vh 0..., H
N₁ 4R" (1 - ) Al2
4h -h=00 O..,, H.
- 7)-7)eh
Then, the stationary policy #; obtained by DynPG under exact gradients achieves 1 Voli The total number of gradient steps are given by
1lo0
Σ N P=0
H
48R" 1 (1-
log (og(6R
(6 -
1
log(>-1)
Proof.
The optimization procedure is the same as for the value function error by substituting with Morcover, note that
(1-
3
#-1
(1 7)
H h E/
6
36

---

Thus, < علججا is sufficient for Lemma D.7 to hold, and we obtain that using these (Ex. )'s in
Theorem results in an overall error for DynPG given by
| Vio 1 I 3
(1-m
H
+
H-1
Σ h=0
? H
$ 1 1
c(1 - 7) =c.
Note that we can again rewrite H to be
log, (1 (1-2)²
log((1 -7)
6Pt
log (og(7-1)
Thus, the complexity bounds for the optimization epochs = O...., H are given by
H
H-1
N
No +
NH
h=0
h=0
24 |A
log((1 26-
24 (1
- 7)
log(>~1)
11 10
7)
#r 11
48R" 1
log((1 - 7) -26 - 1:R.
(1 - 7)
1og(>-1)
14
where used the calculations in the proof of Theorem D.6 in the first step and substituted by (1-7)e
Lemma D.9. The term log (7- = log(()) is asymptotically equivalent to (1 7) for tt 1.
Proof. By the definition of asymptotic equivalence for two functions f andd g we have to show that
lim f(z)
*tl g(x)
holds by L'Hospital rule that
lim log(n) 11 (1 7)
lim
711
E DynPG in Large or Complex Environments
In the following, aim discuss challenge that may arise when applying DynPG in practice. In very complex MDPs, where the policy parametrization needs to be rich, the DynPG approach in Algorithm can suffer from storage problem. The number of policy parameters that need to be stored for future decisions scale linearly with the number of training steps. In order to circumvent this problem for practical applications propose actor-critic based modification of DynPG, called Dynamic Actor-Critic (DynAC). The general idea behind actor-critic in vanilla PG is to introduce called critic, second parametrized class of functions (Q") wEeR' which approximates the
Q-function Q" in the policy gradient theorem. Using the critic as estimator of the Q-values no more roll-outs needed to estimate the rewards-to-go In the actor-critic variant of DynPG, we include an additional training procedure after optimizing policy 4े to update the critic based on the old critic,
Q t6. and the newly trained policy, $2 using the relation:
( (8. = r(s,a) a) + Σ p( Σ *
The critic used in the policy gradient theorem an estimator for Q such that the new gradient in DynAC is given by
Dyn-AC V log( (A]S)) (A (S,001++SS.A AS,
37

---

Algorithm 2: DynAC
Input: Initial state distribution class of policies (1 )eE),, class of critic parametrization
weE)
Result: Approximation of x², denoted as R*.
Set h 0;
Train Q to approximate the reward function r;
while Convergence criterion not met do Initialize 80 (e.g., 8g = 0):
Choose 01 and N₁ (ef., Remark 4.4
for n O...., No
do
Sample S ~ μr and A ~ (-15);
>+)(-)));
Set Dynn-A = V log(
Update 0n+1 pn Gn;
end
Set n = NN;;
12
Train Wh+2 s.t. for all a: 12 == (sa) 1h (S, AS)
Set h h 1;
14 end
Return R* 1
where S ~ and A ~ (-1s) and n" is the policy we are currently training for epoch h + 1. This way there is no need to store all trained policies only the currently trained policy and the current critic are needed. For applications where the performance of vanilla PG is poor and the parametrized policy needs to keep this variant of DynPG in mind. We call this approach DynAC for dynamic actor-critic and summarize the steps Algorithm| 2
very rich such that storing many policies might cause storage issues, we suggest
theoretical analysis of this approach would require an assumption on the approximation error train the Q-functions. As the gradients are no longer unbiased, convergence towards the global optimum cannot be guaranteed and the bias errors will appear in the overall error. We leave further investigations of DynAC future work, as an in-depth exploration would exceed the scope of this paper.
F Convergence Rates under Tabular Softmax Parametrization -Sampled Gradients
In this section we drop the exact gradient assumption and analyze DynPG for sample based gradient estimates (generated by MDP roll-outs). We emphasize that the main insight into DynPG (breaking the (possibly) exponential 7-dependence) is part of the exact gradient analysis. Even though the estimates provided here are not relevant for practical use, we add this discussion for completeness.
For fixed future policy म consider K₁, trajectories (sk, of kizo for i = 1...., Kr, generated by si ~ μ4, a ~ Ty and dj ~ - for 1 < k < h. In analogy to the gradient estimator for vanilla PG (motivated by the policy gradient theorem) the estimator of V VoV
vo.th (μ) is defined by
Gk2 (0)
loog(m (og(ma(
(18)
Kr.
where Qh+1= Eko rs of) is an unbiased estimator of Q (st, af). Then the stochastic PG update for training the parameter in epoch given by
0, 0, + Th G KK (0,).
(19)
Our main result for the optimization of the contextual bandits in DynPG is given as follows.
Theorem F.I. Lei Assumption 4.5 hold true and DynPG be used with stochastic updates 19 Suppose, are in epoch h with fixed future policy A 4τū, and for any dn. > O and en, > 0, choose
38

---

NA
12 [2 1R²"" (1-7)eh
nh 2 211-2h+)re-- vNn and Kn
1-7
NR 8a
Then, it holds
PP ((T - vil .A)
(1)) 2 ch S
on.
To prove Theorem F.1 we adapt the proof ideas in 12 Sec. D.2] for finite-time dynamic policy gradient to discounted setting. We restate all results and show how to adapt the proofs.
We first verify that the gradient estimator in Appendix Fis unbiased and has bounded variance. Lemma F22 Consider the estimator GK (0) from Appendix For any K > it holds that
[e. 1 k, (0) = Va VoViTI (1)
and under softmax parametrization
5( - h+ 122)2 12
I (TO.A)
[[] (0) - (
E3.
K₂
K₁
Proof. By the definition of GKi, (0) we have
M. (0) E (M / v (AolSo)) Σ r An)]
as in [12 Lem. D.6] and from the DynPG policy gradient theorem (Theorem C.3 unbiasedness directly.
we obtain the
For the second claim, first obtain that R
B
||G Kn (0)
Vo VoVila
|| (ow.ooo((ooooooo.oooooooooo
(o0oAA))S)))00 ( (So, - Vo VoVi (To.A) (w)]1)
Kn
h+1
((T..A
ΣΣ .ES acA
(19=% - -o((ss))
* A&) (())))(()m((s)))))) a)) ).
Kn
Note that we have nearly the same term as in the proof of 12 Lem. D.6]. We can follow line by line the arguments there and have to replace the bounds Σk=h rSk, Ax) (H h) R with upper bound 7 A&) I 1- R.
So replacing (H h) with 1+1 obtain that 1-y
5(- 111- 1-7 R
B( [|Gk, -oooltaa
VoV.
(WIPP] S
Kh
We continue follow the proof in 12 Sec. D.2] and introduce stopping time control the non-uniform gradient domination inequality along the exact gradient trajectories.
Recall that we consider the optimization of DynPG at epoch h. Let (0n)22 be the stochastic process from (19) and let (0m)n20 the deterministic sequence generated by DynPG with exact gradients. Assume in the following that the initial parameter agrees, i.e. O fo. and the step size 7)s the same for both processes.
We denote by (Fr)22 the natural filtration of (0m).200 As assume uniform initialization, the non- uniform gradient domination property holds along the deterministic gradient scheme with constant Cy min.2o min.es Sn (a" (s))s) [AT (Lemma D.4 D.4
Therefore define the stopping time
1
min(n 0: 110,, 0nll2
4|Al
39

---

Employing this stopping time, we can control the non-umi non-uniform gradient domination property along the stochastic gradient trajectory, before the stopping time is hit.
Lemma F.3. Let Assumption 4.5 hold true and DynPG be used with stochastic updates from (9). Suppose, we are in epoch h with fixed futuree policy A = Th Then, it holds almost surely that minosngr minges Th (a" (s)[s) 2 2[ is strictly positive.
Proof. The proof follows line by line as in [12 Lem. D.7] with Ch
[
We consider the two events {n S T and {n r} separately, On the event {n S The we obtain the following convergence rate.
Lemma F.4. Let Assumption 4.5 hold true and DynPG be used with stochastic updates from 19
Suppose, we are epoch h with fxxd future policy A tīh Suppose, that
the batch size (Ki)a
(1
2/Nz )n increasing for some N₁. 2
64lliii
the step size Th =
1-4 2(1-gh+1)8*
Then,
E [(
(supp h+1 (p)
(mo.)) ))
(Ta. -. (w))
S 3(1 - 7)(1 2/N. )
32/NN | R
Proof. Line by line in 12 Lem. D.8]. Note that have different smoothness constant and a different variance control. In both constants one has to replace (H h) in [12] Lem. D.8] with 1- and Ch with [A]
Next, we bound the probability of the event {n 2 J by ö for large enough batch size Ki.
Lemma F.S. Let Assumption 4.5 hold true and DynPG be used with stochastic updates from 19 Suppose, we are epoch h with fixe future policy A 4h For any > suppose that
the batch size Kn 2 2
the step size nh S VnLa"
Then, we have PP(n 2 T) < 6.
Proof. Line by line as in 12 Lem. D.9]. Replace again ey with 1 [A] and (H - h) with 1-g htz
Using the above Lemmas prove the convergence of each contextual bandit problem.
40

---

Proof of Theorem F.1 Proof works as in 12 Lem. D.10], we can separate the probability using the stopping time and under the zero approximation error of softmax we have that
P (V, (() v A) (p) 2 cn)
A .A) (1)) 2c)
=P(
Sup sup ( Vn+1'
< <P((N, 5 n dsup
Ai (1) -Vn-1
(TāNs :.)
(14) 2 2))
A+1
8
(noN, A) (w)) 2 6t)
+ (Nv 2 t} n
(sup V (TaN)) (1)
V/
h+l
t .A)
E (supa Vh+11 v (1)
Vn+
(1)) (T))
+ 27)
132 A1 (
R
5
+
3(1 - 7)(1 2/N.
N₂
8
$ + 2
6,
where the second inequality is due to Lemma F.4 and Lemma
F.5 The last inequality follows by our
and (H- h) with 1-14+1
choice of N₁, in 12 Lem. D.10] by replacing en with [
From the previous contextual bandit result, we can derive a sample complexity result under which we obtain convergence in stochastic DynPG with arbitrary high probability.
Theorem F.6. Let Assumption 4.5
hold true and DynPG be used with stochastic updates from (99
Choose > > and set
(1 - 7) (1-7)eg
H log,
)
6R*
c(1
?)
H-
(((1 - h+1 " )))
-1 (
((-
- =h= 0 o..., 1,
Eh
(1-
6
h=0
7)
EH
N₂ = [(
12 12 (H + 1)(1 - N DR'
2 2
=h= = 0... H,
(1 7)
12
1-7
1/h 2(1 - 1 VNn"
vh = 0 O..,,H,
KA = (H + 1)
=h= 0 O...H...H.. H.
82
Then, the stationary policy H obtained by stochastic DynPG achieves P( V 1oc <() 1 8. The total number of samples is bounded by
H
1 02 -le ) 00 (1 178108
Nr
log(>-1)
h=O
Note first, that the constant C2 in the sample complexity is indeed natural number, hence independent of any model parameters. The concrete values H, (Nr) (nn) and ( (Kw) are derived in the proof below.
Remark F7. We obtain again sample complexity that scales at most polynomial in (1 -7)-1 and guarantees convergence in high probability. [7] sample complexity for softmax PG with entropy regularization is derived, where even larger batch sizes are required, which leads an exponentially
41

---

bad sample complexity with respect to (1 (1-7)-' Still, we do not expect the rates in Theorem F.6 be tight, but they prove that convergence stochastic settings achievable. We also want to remind the reader of the sample based example presented in Line 13 where no batch is needed for the implementation.
Proof. By our choice of Nr. Th and Kn. and Theorem E.1 holds that
( .A1
(TENn" .A7
P (Issup (
h+1 A+1
1oo < ch) = P P(3s E S
sup h+1
(s) Vn+1
(8) 2 cN
(ToNA .1) (w) 2 en (
P
sup v+1 (IT)
Vn+1
5
H
where in the first inequality we have used we used that
sup V. A)
(8) V
sup v+1 (1) Vn+t (aaN 1 (s) s |
v= (T6N) .A)
(u).
( .1)
Next we introduce the event C =
Vh 0,... H
|supe v(xa.A)
Vn+t 1l00 < {n) By
h+1 Lemma D.7 we deduce that under the event holds almost surely that
|IV
V
11:00
3
H R"
Hzn-h-leh sc
1 ?
1 1-7 h=0
1lo0 E) and therefore, by choices of e, 's and H. So C C (
l - v 1lo <t)
(maN, .A
2 Vh = O...., H Issup (T.AA)
Vn+
1lo < cn)
h+1
A A/ 1l00 En
P (3h 0. H. Iuuu V (maA))
Vn+
H
ssup y (moAA) (noN, .A) h+1
2
Σ
ht1
1110 2 ch
h=0
8
21
H
h=D
=1-4 5.
42

---

To upper bound the total number of samples, we suppress the bruus-- for simplicity and compute
Kn
H 5 +
11
82
h=0
5 H + 1
82
h=0
|A (H 1) -12
(1- 7
G1/1/18 (H + (8*)8
H
7
4=0
(H (R*)
H-1
H-1
Σ (((1 7
h+
(1
(1 7) 16810
88 (H + (R*8 11
(1 - 78861
c8(1 7)
1
Aaal + (
11-8 +
H H-1
((11 - h+1
((1-
H-1
(1 (
11-716810
1=
02) A + (R')
H-1
(1- 11
(((1 ((1-1h+1)
H )
((1 - - -
16810
hm0
h-0
02) 8 (H (R*)
[1 1413 HJ
H-1
((1 7 1+1 ) 2 -ー "
(1 - 7) 16
h=0
A2| (H + (R*)
(1 (1- + 11
H
h- 7 [)
168
h=
where we used Jensen's 's inequality twice and defined the natural numbers C₁ == 5 * (144)* and
22 = cj * 6 which are independent of any model parameters. Next, since y E (0, 1), we have
H-1
H-1
4-1
Σ H-
H
138
A=
h=0
#-1
1
7
<
1 1-
M=0
and obtain
1 8 A2|A| (H (R*)s
#-1
Σ N₁ <
(1 (1-1 H41]8 + H
(
- -
H
(1 - 16
h=0
h=0
1
02l 211 + (1728
<
1 + 8
168108
11
Finally, for H = logg
(1-2)²2]
there holds
log(7
1 1
02 12
log((1 -
18
Σ No Kn <
4=0
11
00
(1 7) 17810
1og(>-1)
43


Reviews:
[{"review_id": "AAuEZ0ZCc1", "reviewer": "Reviewer_Q7Hh", "summary": "This work develops DynPG: Dynamic Policy Gradient, an algorithm that exploits the structure of the MDP, combining dynamic programming with vanilla policy gradient. The authors proceed to study the newly proposed method in the $\\gamma$-discounted, infinite horizon tabular MDPs, using softmax policies and establish finite sample convergence to the stationary optimal policy. Exploiting the MDP structure enables the algorithm to scale polynomially in the effective horizon and circumvents a fundamental limitation of vanilla policy gradient.", "questions": "Answering these questions and including the discussions will definitely make the paper stronger:\n\n- PG methods and AC variants, especially with the softmax policy are mostly used in non tabular MDP settings. What can we expect in these scenarios? Can we extend the analysis to this setting? and how does the DynPG method apply here?\n- The example in Figure 2 compares DynPG to vanilla PG (with REINFORCE, no baseline). What happens when the baseline exploits the MDP structure (say use a Q or an advantage function), does it still fail in the example? Do we still have the same exponential dependence on the effective horizon?\n- Scaling DynPG to larger problems require an AC variant. Its theoretical analysis is out of scope, but I would have liked comparing it to classical Actor Critic. What are the main algorithmic differences? What should we intuitively expect from DynAC?", "limitations": "Yes. The limitations of the analysis and the proposed algorithm were covered mostly.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I like the paper overall, and think that its strengths overweight its weaknesses. These are listed below:\n\n**Strengths:**\n\n- The paper is written in a clear and accessible way. \n- The theoretical contribution is relevant to the community and answers an important question.\n- The paper acknowledges a big part of the limitation of the proposed method and suggests improvements.\n\n\n**Weaknesses:**\n- The analysis require somewhat strong assumptions (access to exact gradients for example).\n- It is a theoretical paper, but I would have loved to see more experimental discussions.\n- There is a lack of discussion and some questions are left unanswered. This is developed more in the questions section.", "was_revised": true, "final_justification": "My questions were addressed satisfactorily. While the contribution is primarily theoretical, it is both important and relevant to the community. I would have appreciated a deeper discussion of the practical implementation details and implications of the method.\n\nOverall, I support the acceptance of this work.", "rebuttal": "Dear reviewer,\n\nWe sincerely thank you for the time spent evaluating our work and for the positive feedback. \n\n\nFirst, we would like to point out that we relax the assumption of exact gradients in Appendix F and instead conduct our analysis under stochastic, sampled gradients. Even in this setting, we observe an improved convergence rate of DynPG compared to regularized vanilla PG (cf. Remark F.7).\n\nIn the following, we address your questions regarding the practical applicability of DynPG and its performance. Additional experiments are planned for future research.\n\n**Question 1 – DynPG in Non-Tabular Settings:**\n\nOnly the convergence analysis is restricted to the tabular case. The method itself, however, can also be applied in non-tabular environments. Algorithm 1 in the paper is not depended on a specific MDP setting or policy parametrization. \nAt present, the analysis using softmax cannot be extended to infinite state spaces. In such settings, it is open to establish a convergence rate based on properties of the loss landscape such as dominated gradient property, which is crucial for proving convergence in our setting. Nevertheless, in scenarios where standard algorithms suffer from committal behavior, we still expect DynPG to exhibit superior performance.\n\n**Question 2 - DynPG vs. PG with baseline in our Example:**\n\nThe possible exponential dependence of the effective horizon has been proved in the setting of exact gradients. Using baselines does not change the exact gradients at all, so the counter examples stay untouched using a baseline. Nonetheless, for the stochastic setting your question is very good and to our knowledge there is no answer. We performed additional experiments on our toy example with baselines, in particular using the estimated value function of the current policy. The baseline did not improve a lot, on the example DynPG was still significantly better.\n\n**Question 3 - DynAC vs. AC:**\n\nThe difference of DynAC and AC is similar to DynPG and PG. We stated DynAC in Section E. In DynAC we use an actor critic approach to learn a new policy for each epoch (as it is done in DynPG using standard PG). Compared to that in AC we learn one stationary policy applied in every epoch. Intuitively, the situation should be similar to our toy examples, delicate environments with dead ends should be favorable to DynAC while (as always) the simpler algorithms will perform equally well on simple environments."}, {"review_id": "XRzSiU2AQ4", "reviewer": "Reviewer_qBFH", "summary": "The authors propose an algorithm that combines dynamic programming with policy gradient in reinforcement learning. Theoretical upper bounds for convergence rate of the proposed algorithm are derived and shown to avoid the potentially exponential dependency on the effective horizon $(1-\\gamma)^{-1}$ in a vanilla policy gradient approach. This is numerically demonstrated on a toy example.", "questions": "In Algorithm 1, perhaps steps 4 and 6 can be made more explicit.\n\nIn Algorithm 1, step 3 initializes each new policy from scratch. One would imagine that the optimal policies between consecutive $h$ are similar and therefore initializing $\\theta_0$ with the previous $\\theta$ might have some benefits.\n\nI would suggest another round of proof-reading to fix many of the missing words in the main text.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe main strength of the paper is the proposed algorithm together with the analysis of its convergence rate. It is convincing how the DP steps of the algorithm circumvent the limitation of a vanilla policy gradient approach, and this idea can perhaps be implemented and incorporated in existing, more practical RL algorithms. The presentation of the key results in the paper is generally clear. I did not check the proofs but results seem believable.\n\nWeaknesses:\n\nAs usual in this kind of works, there is a question of the practical relevance of the proposed approach. The authors do state clearly that in many MDPs the vanilla policy gradient approach will do better. The issue of exploration as well as the challenge in estimating the gradient are omitted in the analysis. These issues have more practical relevance and may overshadow the gain from the proposed approach in practice.", "was_revised": true, "final_justification": "I maintain my acceptance recommendation.", "rebuttal": "Dear reviewer,\n\nWe sincerely thank you for the time spent evaluating our work and for the positive feedback. \n  \nWe would like to emphasize that we do not expect PG to outperform DynPG in most scenarios. Rather, we anticipate that in cases where PG performs well, DynPG will exhibit comparable performance, not worse performance. We will reformulate our formulation in line 226 to make this more precise. Additionally, please keep in mind that computing gradients in DynPG is actually simpler than in vanilla PG. The derivative with respect to the time-dependent policy has a simpler form (cf. Theorem C.3 with the gradient estimator used in PG). We will make this more explicit in the text. \n\n**Question 1 - Explanation of line 4 and 6 in the algorithm:**\n\nLine 6 of the algorithm specifies that $G$ should be an approximation, i.e. an estimator, of the exact gradient. In Theorem C.3, we express the true gradient as the expectation of log-probabilities multiplied by the future Q-function in a policy gradient theorem. This formulation enables an unbiased estimation of the gradient via straightforward Monte Carlo sampling. The estimation is simpler than in vanilla PG.\n\nLine 4 of the algorithm states that the hyperparameters $\\eta_h$ and $N_h$ must be set. In Remark 4.4 we derive implications for how these parameters should be chosen based on the theoretical results.\nWe will add remarks to clarify this in the final version of the manuscript. \n\n**Question 2 - Initialization of parameters for new epochs:**\n\nCopying the parameters from previous trainings as initialization for the new training epoch can indeed be a very good idea! It might be able to speed up the convergence in future epochs. Unfortunately, this is not always the case. Consider the example presented in the paper. Copying the weights from previous epochs would in this case lead to the same committal behavior effect as visible in vanilla PG. In general, we can therefore not guarantee improved convergence behavior when initializing based on previous trainings. \n\n**Question 3 - proof-reading:**\n\nThank you for bringing this to our attention. We will thoroughly review the main text for any missing words before submitting the final version."}, {"review_id": "mwotT6yJjC", "reviewer": "Reviewer_4fU7", "summary": "This paper introduces a new reinforcement learning algorithm called Dynamic Policy Gradient (DynPG) for solving $\\gamma$-discounted infinite-horizon tabular MDPs. Unlike vanilla policy gradient (PG) methods that optimize a stationary policy over the full horizon, DynPG decomposes the problem into a sequence of contextual bandit problems. Each iteration optimizes only the first decision epoch while reusing previously trained policies for future steps, mimicking dynamic programming structure.\n\nThe authors prove that DynPG achieves global convergence under tabular softmax parametrization. Specifically, it avoids the exponential dependence on $(1 - \\gamma)^{-1}$ found in vanilla PG and achieves a sample complexity of $\\tilde{O}((1 - \\gamma)^{-4} \\varepsilon^{-1})$ to reach $\\varepsilon$-optimality. Theoretical analysis includes an explicit error decomposition and optimization schedule. A synthetic experiment further demonstrates that DynPG mitigates the high variance and committal behavior that vanilla PG can suffer from.", "questions": "I have several questions about the future use of this algorithm and some notations.\n\n1: If the MDP has infinite states such as linear MDP, does this setting lead to any additional challenges to your method and why?\n\n2: If $\\mu$ is a Dirac measure, what would the value of $||\\frac{1}{\\mu}||_{\\infty}$ be? I think it should be 1 since you only need to consider starting from one single state, but please correct me if I'm wrong. I think it would be much better is there could be a remark about it.", "limitations": "yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: This paper presents a conceptually elegant and practically meaningful idea: by incrementally training over increasing horizons, the global infinite-horizon reinforcement learning problem is decomposed into a sequence of simpler contextual bandit problems. This structural decomposition not only improves the tractability of policy optimization but also explicitly leverages the Markov property of the MDP. The proposed algorithm, DynPG, is concise and intuitive---each iteration requires only the specification of the sample size $N_h$ and gradient step schedule for the current horizon $h$, making it easy to implement.\n\nThe theoretical analysis is rigorous and well-organized.The authors also derive non-asymptotic convergence bounds under softmax parametrization with polynomial dependence on $(1-\\gamma)^{-1}$, which contrasts with known exponential lower bounds for vanilla PG. \nOverall, this work makes a solid theoretical contribution and opens up promising directions for designing structure-aware reinforcement learning algorithms.\n\nWeaknesses: I think a potential weakness is about the experiment. The experiment of this paper is based on a single, synthetic tabular MDP. While this example is carefully constructed to illustrate the benefits of DynPG over vanilla PG, additional empirical results on more diverse environments (even small-scale function approximation settings) would help validate the practical utility of the approach.", "was_revised": true, "final_justification": "The authors have answered my questions about the paper and I think this paper is well-motivated with solid theory. I will keep my score 5 about the paper.", "rebuttal": "Dear reviewer,\n\nWe sincerely thank you for the time spent evaluating our work and for the positive feedback. \n\n**Question 1 - infinite state space:**\n\nOnly the convergence analysis is restricted to the tabular case. The method itself, however, can also be applied in non-tabular environments. Algorithm 1 in the paper is not depended on a specific MDP setting or policy parametrization. More specific, the algorithm can easily deal with infinite state spaces. One could use a linear softmax policy parametrization in linear MDPs, but any other parametrization will work as well. One can also use DynPG in problems with continuous action spaces. \n\n**Question 2 - Choice of $\\mu$:**\n\nIf $\\mu$ is a Dirac measure, then $\\lVert \\frac{1}{\\mu} \\rVert_\\infty = \\infty$, as $\\mu(s)=0$ for all but one state $s$. For the algorithm to work, we cannot choose $\\mu$ to be a Dirac measure. The reason for this is straightforward. If $\\mu$ is a Dirac measure, the algorithm learns only the behavior corresponding to that single state in each epoch and gains no insight into how it should act in other states. Therefore, for training purposes, it is essential that $\\mu(s)>0$ for all $s\\in\\mathcal{S}$. Once training is complete, however, the initial state may be chosen deterministically. We will add a comment on this in the final version of the manuscript."}, {"review_id": "WHl5rHfuCv", "reviewer": "Reviewer_6ZgJ", "summary": "The authors consider policy gradient for $\\gamma$-discounted infinite-horizon tabular reinforcement learning. They introduce Dynamic Policy Gradient (DynPG), a variant of policy gradient that exploits the Markovian property of the environment and thus reduces the worst-case error dependency on the effective horizon $(1-\\gamma)^{-1}$ from exponential to polynomial (with exponent 4). Furthermore, they hint at better compatibility of their algorithm with actor-critic based methods due to independence of the value function from the current policy at future steps. Empirically, they show substantial improvements over vanilla policy gradient in a fabricated setting, though the additional memory cost of DynPG can quickly become prohibitively expensive in real-world implementations. The suggested actor-critic variant (DynAC) seems promising to alleviate the memory bottleneck, but lacks any theoretical or empirical analysis.", "questions": "> Firstly, we observe that DynPG effectively reduces the variance in gradient estimation through the utilization of non-changing future policies. In contrast, the estimation of the gradient in vanilla PG involves assessing Q-values based on the stationary policy $\\pi_\\theta$, which changes during training.\n\nI thought this work would not consider any Q-value estimation, which would cross the line into actor-critic territory. So how exactly is the gradient variance reduced?\n\nYou argue that the total sample complexity is lower for DynPG compared to standard policy gradient. But if DynPG is run for longer than H steps, it becomes more expensive than vanilla policy gradient. Why does this not become an issue?\n\nThe value function is always written as an explicit function of the initial state distribution\n$\\mu$. It seems, however, that the optimal policy never depends on this state distribution, so why\nis $\\mu$ always explicitly included in all formulas? \n\n> The tabular softmax policy can represent any deterministic and therefore optimal policy. \n\nCan it not, more generally, represent any stationary policy? \n\nTypos:\n> In this section we provide estimates for exact gradient to keep notation simple\n\nDo you mean “estimates”, or rather “bounds”?\n> We formally quantify these errors in the following lemma\n\nDid you rather mean “proposition”?\n\nIn Equation (5) there seems to be a typo where $V_0^{\\hat \\pi_0^*}$ should simply be $V_0$.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The paper is very well-written in all but section 4, where it is decently well-written. The contributions are effectively contextualized in prior literature. The proposed algorithm is elegant and shows substantial worst-case improvements on the effective horizon compared to standard approaches. It is also practical in the sense that linearizing the value $V$ as a function of the last step policy $\\pi_h$ allows aggressive optimization. \n\nHowever, DynPG is impractical in the sense that the memory cost becomes quickly prohibitively expensive. Also, the estimation of $\\nabla_{\\theta_n} V_{h+1}^{\\{\\pi_\\theta, \\Lambda\\}}(\\mu)$ is not sufficiently opened up. As a policy gradient algorithm one would assume complete rollouts + score trick, but at multiple points one hints at the use of Q-value functions, which rather indicates the use of DynAC.", "was_revised": true, "final_justification": "The authors were able to answer all my questions to a satisfactory degree. There do not remain any open points or points of disagreement, and my assessment that the work is a strong contribution has been reinforced.", "rebuttal": "Dear reviewer,\n\nWe sincerely thank you for the time spent evaluating our work and for the positive feedback. \n\n**Question 1 - variance reduction and Q-values:**\n\nYou are correct that this work does not consider any Q-value estimation. Instead we sample one rollout - using the already trained (and therefore deterministic) policies - to estimate the gradient. Thus the variance in the gradient estimation of DynPG has less variance compared to vanilla PG. We agree that the formulation in this sentence is not accurate as plain vanilla PG also does not use Q-value estimation but rather uses a rollout under the current stationary policy to estimate the gradient. As this policy changes during the stochastic training, the variance is higher.\nWe will reformulate this sentence accordingly to make this more precise.\n\n**Question 2 - runtime DynPG and complexity comparison DynPG vs vanilla PG:**\n\nPlease note that the horizon $H$ in DynPG can be specified explicitly when comparing the complexity of DynPG and vanilla PG. Thus we can specify $H$, such that convergence of DynPG is guaranteed (see Theorem 4.8 and the detailed versions in the appendix for the specification of $ H$). This allows us to determine the upper bounds of DynPG in Theorem 4.8 only with respect to the stationary MDP parameters and more precisely independent of $H$.\n\n**Question 3 - dependence on $\\mu$:**\nThe choice of the initial state distribution $\\mu$ is only crucial for training and the choice of $\\mu$ influences the number of gradient steps until convergence in one epoch (see Theorem 4.6). Once the policy is converged and close to optimal (i.e. optimal in every state $s\\in \\mathcal{S}$), we can use it in the future trainings. The policy itself is then independent of $\\mu$. Note that we need $\\mu(s) >0 $ for every $s\\in \\mathcal{S}$ for this to hold. \n\n\n**Question 4 - class of softmax policies:**\n\nYes you are right, softmax policies can approximate any stationary policy. With this sentence we just wanted to emphasize that softmax policies are suitable to approximate optimal policies. We will change this sentence to be: The tabular softmax policy can approximate any stationary and therefore also any optimal policy.\n\n**Typos:**\n\nThank you for bringing this to our attention. We changed the two sentences accordingly and corrected the typo in Equation (5) for the camera ready version."}]

Author rebuttal:

Meta-review: The authors consider RL problems formulated as discounted infinite-horizon tabular MDPs, and introduce a framework called dynamic policy gradient (DynPG) that decomposes the problem into a sequence of contextual bandit problems, and combines some of the advantages of both a dynamic programming perspective and a policy gradient perspective.  They provide theoretical bounds for the convergence rate that are much better than the worst-case (exponential in the effective horizon) bounds for vanilla policy gradient methods.

The rebuttal period discussion for this paper mostly focused on technical points; the paper was well written, and the reviewers seem to have mostly understood the authors without additional discussion.  Everyone came into the rebuttal period fairly positive and remained so afterward.

The paper is primarily theoretical, as the authors explicitly acknowledge in the initial draft and as the reviewers also observed.  However, the reviewers were positive about the theoretical contributions ("convincing", "relevant to the community and answers an important question", "conceptually elegant and practically meaningful").  Though the algorithm proposed may not always be the right algorithm on its own, the reviewers commented that it seems plausible that the ideas can be implemented in existing, perhaps more practical RL algorithms.  This seems like it would garner quite a bit of community interest and inspire further work.
Decision: Accept (poster)