Markov Decision Processes (MDPs) are a formal framework for modeling and solving sequential decision-making problems. In finite-time horizons such problems are relevant for instance for optimal stopping or specific supply chain problems, but also in the training of large language models. In contrast to infinite horizon MDPs optimal policies are not stationary, policies must be learned for every single epoch. In practice all parameters are often trained simultaneously, ignoring the inherent structure suggested by dynamic programming. This paper introduces a combination of dynamic programming and policy gradient called dynamic policy gradient, where the parameters are trained backwards in time. For the tabular softmax parametrisation we carry out the convergence analysis for simultaneous and dynamic policy gradient towards global optima, both in the exact and sampled gradient settings without regularisation. It turns out that the use of dynamic policy gradient training much better exploits the structure of finite- time problems which is reflected in improved convergence bounds.
Paper
Similar papers
Peer review
Summary
The paper presents a convergence (rate) analysis for a variant of policy-gradient learning of tabular-softmax policy models under finite-horizon MDP setting with discounting factor $\gamma=1$. In this variant, the policy parameters are updated in an epoch-by-epoch manner, from the last decision epoch at the horizon back to the first decision epoch. For each epoch, the learning is a vanilla (stochastic) gradient ascent process, with the objective function being the value obtained assuming fixed return in future epochs. It seems to me that most results in the paper are obtained following similar ideas with previous theoretical studies of policy gradient under discounted MDP settings (e.g. Agarwal et al., 2021, Mei et al., 2020).
Strengths
I appreciate the general motivation of this work which aims at analyzing RL algorithms under undiscounted setting. In my opinion (and as the authors also pointed out in the paper), many performance bounds of RL algorithms derived under the discounted MDP setting crucially depend on the factor $\frac{1}{1-\gamma}$, thus fail to accurately characterize the performance of RL algorithm under undiscounted setting. On the other hand, many real-world problems in practice are indeed undiscounted MDP problems. Therefore, directly analyzing RL algorithms under undiscounted MDP settings, or deriving results that do not degenerate when $\gamma$ approaches 1, is relevant and important research direction.
Weaknesses
However, several major concerns make me hard to appreciate this particular work. Specifically, 1. The so-called policy gradient algorithm as analyzed in this paper is not really the standard policy gradient algorithm as generally perceived and applied -- the latter updates the parameters of states for all decision epochs simultaneously in each gradient step while the algorithm variant targeted in this paper will update parameters only for one epochs each time. I think the standard co-updating strategy is much more practically relevant. For example, in RL training of language models, the problem is indeed an undiscounted MDP problem, and standard policy gradient methods (with PPO upgradation) are indeed widely used; see the InstructGPT paper (https://arxiv.org/abs/2203.02155) as an example. I thus have concern on the relevance and significance of the algorithm (not the problem setting) studied in this paper. 2. The epoch-wise updating strategy as assumed in this paper makes most of the analysis a straightforward adaptation of the standard analysis method used in the literature. Moreover, it seems to me that the epoch-wise learning problem analyzed in this paper is just a contextual bandit problem -- the paper assumes the policy $\tilde{\pi}$ for all future epochs is fixed, as well as assuming that the distribution $\mu_h$ for states encountered at the epoch is also fixed, but in this case we are essentially just maximizing an "augmented immediate reward (with future returns counted, which is fixed)" over actions conditioned on a context distribution. Since contextual bandit problem is a special case of discounted MDP (with arbitrary $\gamma$), I wonder if most results presented in this paper trivially hold given known results about discounted MDP. 3. I also have concerns on the authors' interpretation of their mathematical results. For example, the paper claims (as a main contribution) that Theorem 3.8 derives a linear performance bound to the horizon H. However, the bound contains the factor c_h, and it's not clear if c_h itself can be a function of H (or of H-h). c_h can be considered a "constant" only with respect to n, not to H. Moreover, Theorem 3.8 only gives a per-epoch performance while previous results gives the overall performance. My understanding is that when we consider the convergence of epoch 0 (which is what we eventually care), we would need to count the time spent on epoch 1 ~ H-1 too, which would bring in another factor of H to the bound? 4. Similarly, throughout the paper it's assumed that the state distribution $\mu_h$ is given for all epoch h, which is not a reasonable assumption in my opinion because except for $\mu_0$, the state distributions for all other epochs actually depend on the algorithm. This is in sharp contrast to the previous papers which only assume that the *initial* state distribution $\mu_0$ is given (which is indeed given). Again, this $\mu_h$ is considered a "constant" when interpreting the bound derived in Theorem 5.2, although $\mu_h$ (for h>0) may heavily depend on structures both in the problem and in the algorithm, in a highly non-trivial manner. 5. The majority of the paper assumes that the reward is nonnegative, which is a bit of a limitation, given that the sign of the rewards can greatly affects the performance of policy gradient.
Questions
(A) You argued that "*reducing the problem to stationary policies is inadequate for finite-time MDPs, and a new policy must be trained recursively at each time step*" (Line 50). I am not sure that this assertion is true. The so-called non-stationary policy $\pi$ (defined at Line 104) is exactly a stationary policy over the entire state space (note that you have defined the state space $S$ as the union of the disjoint epoch-wise state spaces; see Line 100). Since the policy $\pi$ at Line 104 is just an ordinary stationary policy over $S$, the standard policy gradient algorithm can be applied, and we don't have to train it recursively. Since this disagreement directly leads to my major concern 1 as stated above, I am open to hear your rebuttal if I am misunderstanding something here. (B) Line 154: It seems to me that $J_h$ depends not only on $\theta$ but also on $\mu_h$ and $\tilde{\pi}$. However, the notation here is hiding this fact. This in turn hide some subtle issues in the analysis later. For example, explicitly writing $J_h(\theta, \mu_h, \tilde{\pi})$ would make it clear that in Algorithm 1 the $\mu_h$ is left undetermined. (C) Line 263: What is $C_h$? I originally thought this is a typo for $c_h$, until I found that in Theorem 5.2 both $C_h$ and $c_h$ show up in the definition of $K_h$.
Rating
3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
3 good
Contribution
1 poor
Limitations
The paper well discussed the limitations of this work in Section 7.
Summary
This paper proves asymptotic convergence and convergence rate of (stochastic) policy gradient descent to global optimum for un-discounted finite time Markov decision process (MDP). For the deterministic version, at each decision time, they show the error bound depends linearly on the remaining time step. For the stochastic version, they derived probability bounds. They extend their analysis to REINFORCE on discounted MDP.
Strengths
The presented results are sound and complete. Both convergence and convergence rate of policy gradient methods with softmax policy are established for the finite-time MDPs.
Weaknesses
The main argument seems to be based on Mei et al (2020) with some modifications for un-discounted finite time MDPs case. I did not go over the details of proofs in appendix. It is hard to evaluate the significance and the novelty of the contributions.
Questions
See wekness
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
See weakness
Summary
This paper studies the convergence properties of stochastic policy gradient methods for finite-state MDPs for finite horizon problems with un-discounted optimality criteria. The convergence relies on the development of a weak PL condition. In the second part of the paper, the authors then extend their convergence analysis to the setting where the policy gradient is not available exactly and only a stochastic version of it can be used.
Strengths
The paper is well written and easy to follow. In particular, I find Section 4, where the convergence analysis is generalized to the stochastic setting strong and practical useful. Proofs are derived very clearly and detailed with I appreciate.
Weaknesses
1) Numerical example missing: In my opinion, it would be interesting to include a numerical example to the paper. In particular it would be interesting to see how tight the complexity bounds of Theorem 4.4 are on a concrete example. 2) Finite state/action spaces often are restrictive: What can you say about the results being generalised to continuous state and action spaces? Maybe for a linear system to start with. 3) How relevant are un-discounted problems? Could you add a detailed motivation, why these problems are practically relevant?
Questions
1) Could you clarify better which results are new and which are existing results. For example, I don’t understand if Theorem 2.2 is an existing result or if it is new. 2) In Equation (5), I don’t understand the dimension of $\theta$. I think there is something wrong here. 3) In Lemma 2.1, why is the superscript of the expectation operator $\pi_{(h)}$ and not $\pi$ ?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
4 excellent
Contribution
3 good
Limitations
Without Section 4, the work would have been limited as the gradients typically are not known exactly. But thanks to the results in Section 4, I think the paper is rather complete and I do not see major limitations.
Summary
The paper analyzes the convergence of non-stationary softmax policy gradient methods where the policy is parameterized by different parameters at each decision epoch. The convergence results on REINFORCE algorithm are provided under undiscounted finite-time and infinote-horizon cases.
Strengths
- The paper obtains new global convergence results for softmax policy under undiscounted finite-time and infinite-horizon MDPs. The assumptions used are standard in policy gradient literature. - The analyses in the paper also cover policy parameterized by deep neural network in deep reinforcement learning. - The paper is well-written and easy to follow.
Weaknesses
- My major concern is about the factor $c_h$ in Theorem 3.8. The authors use it as a constant but I argue it is not. Since $c_h$ is the infimum over all iteration of the minimum output of softmax policy, it is not known or can be computed before-hand. In fact, it depends on the choice of number of iteration $n$ and the current parameter $\theta_n$. More discussion is needed in this case. - The results in Theorem 3.8 and Theorem 4.4 are valid for the exact policy gradient which is rather restrictive and impractical. I believe having results in the stochastic case using stochastic policy gradient will strengthen the contribution of the paper.
Questions
1. The factor $c_h$ can be very small (if the policy is well-trained). Can we impose certain condition to overcome this? 2. I wonder if the results can be extended to other class of policy gradient method, such as ones with different policy gradient estimator.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
I do not find clear discussion on the limitation of the work but I find the use of exact gradient is the main limitation for the key results in the paper.
Response to Rebuttal
I would like to thank the authors for the detailed answers. I will keep my score.
Thanks for the rebuttal. > the approach of training all policies at once is used in practise (and works) there is limited theoretical understanding The "simultaneous" version of policy gradient is, in my opinion, really the algorithm that most people refer to when talking about "policy gradient", *not only in practice, but also in most theory works*. The algorithm is perhaps not analyzed in the undiscounted setting yet, but this is exactly why we *should* analyze it under this setting, right? I don't see why the fact that "the standard algorithm is not analyzed" motivates us to turn to analyze another algorithm. > our approach seems unnatural but allows a very clean analysis As I mentioned in Concern 2, I doubt if the epoch-by-epoch setting as you assumed has made the analysis a bit too easy. Given fixed future payoffs, the problem of finding optimal action *for a single epoch* is (just) a contextual bandit problem for which performance of policy gradient can be easily derived (because contextual bandit is a special case of discounted MDP). So, while I agree that your algorithm setting allows easier analysis, I think this makes your paper weak, actually. > There is indeed a miss-understanding here You are right that I shouldn't say "S_h are *disjoint* subsets", which I actually mean they are "*separate* subsets", but this correction doesn't touch the main point. My point here is that, the simultaneous-update version of policy gradient is also perfectly applicable in your problem setting because the so-called non-stationary policy that you are analyzing is only non-stationary with respect to the epoch-wise state spaces, but *is* a stationary policy with respect to the state space $\mathcal{S}$. > $c_h$ generally depends on $H$ I feel $c_h$ might also crucially depend on $\mu_h$. A positive $\mu_h$ can only guarantee convergence in the limit, but it feels unlikely that the speed of the convergence is agnostic to the specific form of $\mu_h$. > From our point of view it becomes quite clear how the simultaneous PG approach should be analyzed It is great to hear that you got inspired about analyzing the standard policy gradient. I agree that it would be quite interesting if a paper can show that the epoch-by-epoch variant is better than standard PG, either through systematic experiments or through mathematical analysis. It's interesting especially because I personally and intuitively don't feel it true :) In any case, I think the existing evidences you presented, including the rebuttal PDF, has not really established the above. I encourage you to keep working in this direction, though!
Thanks for the good discussion! Though it might go a bit far we carried out the proofs you asked for to assure you we did not try to take a theory shortcut by not studying the (simultaneous) PG algorithm. > ...interesting if a paper can show that the epoch-by-epoch variant is better than standard PG...especially because I ... don't feel it true :) Challenge accepted. We did the Maths. In short: the provable bounds for backwards PG are indeed more intriguing than simultaneous PG. It scales better in $H$ and even better, the disturbing (and possibly huge) model-based constants $c_h$ can be made to disapear for backwards PG if properly initiated (not for simultaneous PG). This confirms our simple simulation example. **Two algorithms for non-stationary finite-time MDP** a) First our algorithm. You are right, we now understood your thoughts. It can be interpreted as a concatenation of contextual bandits, this is our Sec 3. Sec 3 is similar to Mei2020 but still needs some extra analysis, e.g. the crucial dependence on the time horizon $H-h$ (obtained in the smoothness) would not be visible in Mei2020 by seeing a contextual bandit as MDP with $\gamma=0$. (But please keep in mind, our major contribution is the stochastic case of later sections!) b) Second, what you call the PG Algorithm: artificially use a stationary policy by adding the time coordinate to the state-space, then considering an undiscounted stationary MDP with finite time-horizon. This leads to a stationary softmax policy with $H |\mathcal{S}| |\mathcal{A}|$ many parameters. We guess this is what you meant, the state-space is artificially made disjoint. **The Maths** We did the analysis for simultaneous PG to finally convince you, that our viewpoint is indeed worth looking at and that your personal feelings might not be completely true :) The analysis of "standard PG" can be proved with methods similar to Mei2020 (or other recent articles). Calculating the smoothness constant for the artificial undiscounted MDP then adapting the PL-inequality and putting both together gives the number of gradient iterations $$N = \frac{2 H^5 R^\ast (2-\frac{1}{|\mathcal{A}|})||\mathcal{S}|}{c^2 \epsilon} \Big\lVert \frac{d_\mu^{\pi^\ast}}{\mu}\Big\rVert_\infty^2$$to achieve an error $V^\ast(\mu) - V^{\hat{\pi}^\ast}(\mu)\leq \epsilon$. The $H^5$ is not surprising, you can compare to known results for discounted MDPs and then keep in mind that $H$ should replace $1/(1-\gamma)$. In fact, a discounted MDP can be seen as an undiscounted one terminated at an $Geo(\gamma)$ time which has mean $1/(1-\gamma)$. Thus, stopping at $H$ should give $H$ instead of $1/(1-\gamma)$. In comparison, the total number of training steps from our Thm 5.1 to achieve the same error is$$N= \sum_{h=0}^{H-1} N_h = \sum_{h=0}^{H-1} \frac{4(H-h)H R^*|\mathcal{A}|}{ c_h^2 \epsilon } \Big\lVert \frac{1}{\mu_h}\Big\rVert_\infty.$$Note that we train $|\mathcal{S}||\mathcal{A}|$ many parameters in every $N_h$ such that $N |\mathcal{S}||\mathcal{A}|$ many partial derivatives are considered. The second viewpoint involves $H|\mathcal{S}||\mathcal{A}|$ many parameters in every training step and needs to evaluate $N H |\mathcal{S}||\mathcal{A}|$ many partial derivatives in total. **Comparison** a) the model dependent constants: Thinking about our backward inductive algorithm as a concatenation of contextual bandits, we now reaslised that the model-based constant $c_h$ simplifies to $\frac{1}{|\mathcal{A}|}$ **if we initialise softmax uniformly**. Mei2020 showed this already for bandits (in Prop 2) and this can also be transferred to contextual bandits. This is a bandit feature, i.e. using contextual bandits might not be that stupid after all. For the simultaneous training one looses this advantage and cannot get rid of the unknown $c$. b) The (non)dependence on $c$ is a clear advantage. A disadvantage is, as you already spotted, $\mu_h$. Our approach was motivated partially by optimal stopping approaches such as Becker et al. "Deep optimal stopping", JMLR 20 (2019) where backwards induction appear. In that case (see our simulation) one would start in $\mu_h$ uniform, i.e. yields $$N= \frac{4H^3 R^*|\mathcal{A}|^3 |\mathcal{S}|}{\epsilon }$$gradient steps, which is pretty nice and a much better guarantee than we have for simultaneous PG. Of course, if one cannot start at later times, then the constant matters just as the $c$ constant matters for simultaneous PG. Perhaps you believe that that there is just an important point about the backwards version. We think it is nice (hopefully important) to see clearly how to train different epochs differently. Analysing simultaneous PG was not the purpose of this article, we focused on extending PG to SPG in the spirit of the usual extension of GD to SGD. We feel a conference contribution with the analysis of new PG scheme, standard PG, REINFORCE might be a bit heavy, but we are happy to add the proofs for simultaneous PG into the appendix.
Thanks for the follow-up rebuttal. > It can be interpreted as a concatenation of contextual bandits, this is our Sec 3 ... But please keep in mind, our major contribution is the stochastic case of later sections To my understanding, the main results in Section 4 (i.e. all lemmas and theorems in this section) are talking only about per-epoch performance too. Within an epoch your algorithm is (just) solving a contextual bandit problem, which is a degenerate case of discounted MDP, for which the performance of PG, *for both exact and stochastic*, are well known. > what you call the PG Algorithm: artificially use a stationary policy by adding the time coordinate to the state-space This "artificially constructed" policy is exactly equivalent to the policy you are analyzing in the paper. In your policy formulation (at line 104), the subscript $h$ in the sub-policies $\pi_h$ is effectively serving as the time index. This policy has $\sum_h |S_h||A|$ parameters, no matter if you call it stationary or non-stationary. The standard PG is not only perfectly applicable to this policy, applying standard PG on this policy is an *extremely* widely adopted practice in the real world (when dealing with episodic RL problems). Note: the above is a revised comment, because I was wrong in my original post by saying that the time index is not needed -- what I want to stress is that, to apply standard PG, there is no need to add additional parameters to the policy model. > it might go a bit far we carried out the proofs you asked for ... Analysing simultaneous PG was not the purpose of this article I agree that it goes a bit far for you to prove for the standard PG, and actually, also for me and other reviewers to review such a proof,through the discussion period. In fact, I was not asking you to do this. I am giving review feedbacks to your original submission. I fully noticed that analyzing standard PG is not your purpose in the paper, and I guess I am challenging this purpose. In any case, I do hope you consider my (negative) feedbacks constructive, as I believe analyzing PG under undiscounted setting is an important research direction, as I've pointed out in the review comment.
Thanks again for the very constructive discussion we really appreciate a lot! > ... discounted MDP, for which the performance of PG, *for both exact and stochastic*, are well known. We are not aware of an analysis of tabular softmax PG for discounted MDPs (without regularisation) in the *stochastic* setting. And papers dealing with regularisation only prove convergence to the regularised optima. Most papers such as Mei2020 do not consider the stochastic case. There is a number of partial results in the stochastic setting (of which several are incorrect) but none applicable in our case. The point is, that there is no guarantee for the $c_h =\inf_n \min_s \pi^{\theta_n}(a^\ast(s)|s)$ to be a constant or more precise to be bounded away from zero, when $(\theta_n)$ is a stochastic trajectory. In the stochastic setting this is tricky. We are not aware of such an analysis in the discounted setting for PG without regularisation. This is why we do carry out our analysis also for the discounted case, see Sec 6. If we are wrong (RL literature moves really fast), we kindly ask for a reference for an analysis as ours. > to apply standard PG, there is no need to add additional parameters to the policy model. Correct! The numbers of parameters of both parametrisations is the same. But there are different ways of training the parameters: Either brute force train all of them at once (this is typically used, as you say, but ignores the structure of the problem). Or using the information that dynamic programming suggests to train them recursively with the right non-constant number of training steps that comes from the L-smoothness of contextual bandits from Sec 3 (keeping in mind that the episode to episode differ from contextual bandits as their rewards are rewards to go that get smaller for later epochs). The "artificial enlargement" is nothing but a mathematical trick to allow the analysis using stationary policies and, luckily, the analysis of discounted MDPs can be extended to that very very specific MDP without discounting (see last answer). It is not surprising that using structural information at least in theory leads to more efficient algorithms. This is what we tried to show in our previous answer, comparing both ways of training. > I fully noticed that analyzing standard PG is not your purpose in the paper, and I guess I am challenging this purpose. The analysis of standard PG in the followup rebuttal was just to convince you that our algorithm is (at least in theory) more efficient than brute force training of all parameters at once. One should be aware that training all parameters at once ignores all the advantage gained from the dynamic programming and throws away most of the structure of the problem. Although there might be good reasons to use a simple approach in practice, we believe that our duty as scientists is to develop theoretical improvements that might eventually be adopted in one way or another in practice.
Summary from our point of view
The discussion was intense but very constructive, thanks again. Here is the summary from our point of view. Practitioners use a brute force approach to train all parameters at once which is possible but ignores the very nature of the problem. The intrinsic nature of the problem is a contextual bandit problem (as you realised, we did not interpret it that way), with a non-trivial combination of bandits. This is nothing bad, this is actually very good! Using that intrinsic nature better algorithms can be designed (not surprising as it uses the true structure of the problem). In the paper we proposed and analysed the most natural one, for our discussion we compared it in the deterministic setting to the brute force simultaneous algorithm. The future will show how the theoretical understanding of the very nature of the problem problem might positively influence algorithms used in practice as well. It may or not, but that's typically the burden of theory papers.
I thank the authors for their clarification. I will keep my score.
Decision
Reject