On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learning

We thank the reviewer for their time and for their thoughtful comments. We appreciate their positive feedback. We also agree with the reviewer that the gradient domination result is probably our most important contribution. We answer their questions below.

Weakness 1 (minor): The paper misses to cite [1,2] that establishes convergence of policy gradient in finite steps (independent of state space).

Response to Weakness 1 (minor): We thank the reviewer for mentioning these interesting references, we will definitely add them to our related work discussion about the convergence of PG methods for classical RL.

Question 1: Global convergence requires the mismatch coefficient to be finite, which is typically satisfied by choosing the initial state distribution to cover the optimal policy’s support (as in Xiao 2022). For continuous/infinite state spaces, how can this coefficient remain finite?

Response to Question 1 (continuous setting): We assume throughout the paper that the state and action spaces are finite as we mention in l.100. In particular Theorem 1 in section 3 holds under this setting and we also make the assumption that $\mu$ has full support in theorem 1 as mentioned by the reviewer (see the theorem statement). While we mention the applicability of our algorithm to continuous state spaces in practice (in remark 2, p.6, section 4), the current analysis does not extend to that setting as noticed by the reviewer. We will make this clearer and we thank the reviewer for the recent reference which we will add.

Question 2: Proposition 1 gives sample complexity for estimating the occupancy measure. Could sample complexity be improved using a contracting operator, as in Kumar et al. 2022?

Response to Question 2: This is an interesting question and idea. We have briefly thought about this. However, the Bellman consistency equation satisfied by the occupancy measure is unfortunately backward and not forward like in standard Bellman operators which allow for forward sampling. We briefly discuss this issue in l. 193-197 in the main part and expand on it in l. 659-668 in the appendix p. 17 (see there for the exact recursion satisfied by the occupancy measure which makes it clear than one cannot use forward sampling). Therefore even if it is a contraction, forward sampling using that Bellman consistency equation is not possible. As a consequence, we believe that Algorithm 1 (as proposed in the reference provided by the reviewer for the occupancy measure estimation step) cannot be implemented with standard bootstrapping. The reason is that we believe there is a missing transposition of the transition matrix $P^{\pi}$ which should be $P^{\pi,T}$ in Lemma 1. There might be some other way to exploit the recursion, we have mentioned the work of Hallak, A. and Mannor, S. (2017). 'Consistent on-line off-policy evaluation' which might be relevant in this regard. This requires further investigation.

Question 3: Could your analysis extend to the average‑reward setting (e.g., Kumar et al. 2025)? What are the challenges?

Response to Question 3: This is definitely an interesting question that is worth investigating in future work, especially that the analysis of PG algorithms is quite recent for the average reward setting as mentioned by the reviewer. We will add this reference to our related work discussion. We foresee that this extension is possible, one needs to be careful with the new policy gradient for that setting using differential value functions, use the appropriate smoothness result recently developed and derive adequate gradient domination results.

Question 4 (bonus): What do you think about the sample complexity of single‑timescale actor–critic methods, as studied by Chen & Zhao 2024 and Kumar et al. 2025?

Response to Question 4: We have restricted our literature review discussion to works either addressing RLGU or PG methods (without critics, i.e. excluding AC methods). We will definitely add these two references for completeness. In our RLGU setting, we do not deal with AC methods even if occupancy measure estimation can be seemingly seen as a critic step. Recall that a Bellman like update for occupancy measure estimation is not available to us as we discussed above and therefore ideas from the interesting single time scale analysis you mentioned cannot be immediately used. On a side note, the question of the sample complexity for global optimality for single time scale AC is interesting and the paper you mentioned seems to leave open an interesting gap with the $O(\epsilon^{-2})$ sample complexity.

We appreciate the reviewer’s detailed and supportive assessment. We will incorporate the suggested citations and clarifications in the final version.

We thank the reviewer for their time, their thorough and detailed review, and their thoughtful comments. We are glad the reviewer found our paper 'well-written, with a mostly solid presentation' and 'a solid and technically sound paper on a very interesting topic'. We respond to each one of the reviewer's concerns and questions in the following.

Question 1: I have some confusion about the strength of gradient domination result. From my understanding, Theorem 1 is saying that gradient domination for every pseudoreward gives a global optimality result. This makes a lot of sense, as Hazan et al. [...]

Response to Question 1 (also to weaknesses 1-2):

To clarify: Theorem 1 recovers the standard gradient domination result in linear RL, as in Lemma 4.1 of Agarwal et al. (2021), when the pseudo-reward is constant and equals the true reward.

• Importantly, our gradient domination inequality holds for each policy parameter $\theta$ with a distribution mismatch coefficient that depends on $\theta$, unlike in linear RL, where it is typically constant. This behavior also appears in prior work (e.g., Mei et al., ICML 2020 for softmax policies).
• Crucially, the mismatch coefficient is finite for any $\theta$, provided the reference distribution $\mu$ has full support. So the result is not vacuous, for each $\theta$, the mismatch is of comparable order to the one in standard linear RL.
• If one seeks a uniform upper bound over all $\theta$, the coefficient can be large, as you noted. However, this worst-case bound is still finite, and can be upper-bounded by the state space size if $\mu$ is uniform. It can also be upper bound by its maximum over the reward functions which are bounded by the range of pseudo-rewards using Assumption 4.
• We also emphasize that this inequality is not used in the non-tabular setting (Sec. 4), where we instead rely on a different proof technique based on hidden convexity. Still, we believe this result is valuable to clarify the relationship between gradient dominance and RLGU more generally.

Question 2: Assumptions. Understanding the assumptions here is crucial to assess the generality ..... appear in Corollary 2? Shall not that be something like "for any precision ..."?

Response to Question 2 (also to weakness 3):

We appreciate the reviewer’s careful examination of our assumptions. While we build on several assumptions standard in RLGU and RL theory (e.g., smoothness, realizability, bounded pseudo-rewards), our contributions lie in how we leverage these to obtain new global guarantees, particularly in the large-scale setting. We will revise the paper to better explain the role of each assumption and when they are satisfied as suggested by the reviewer. We respond to the questions of the reviewer below.

• Realizability (Assumption 2 (ii)) is natural even for occupancy measures as we briefly argue in l. 227-231 (see appendix C for a proof), see response to Q6 below for more details. Regarding this assumption, we also refer the reviewer to Definition 1 and Lemma 16 of Huang et al. ICML 2023, Remark 3., Assumption D.1 in Huang and Jiang Neurips 2024 making the assumption. We can also replace our Assumption 2. (ii) with a low-rank MDP assumption.

• Assumption 4 is standard in the RLGU literature: see e.g. Hazan et al. 2019, Zhang et al. 2020-22, Barakat et al. 2023, Ying et al. 2023. This assumption captures most of the problems of interest in RLGU including pure exploration (using the smoothed entropy), learning from demonstrations (using the smoothed KL) as well as standard linear RL and CMDPs. Other entropic measures or $l^2$ (quadratic) losses are also possible. For instance the smoothed entropy defined as $H_{\sigma}(x) = - x log(x + \sigma)$ is $1/(2\sigma)$-smooth w.r.t. the infinity norm and has been used in RLGU, see e.g. Hazan et al. 2019, Lemma 4.3. We will add a discussion to the paper to mention these.

• Assumption 5: As we mention it in l. 310-312, it was also used in Zhang et al. (2021); Ying et al. (2023a); Barakat et al. (2023) and others. While this assumption holds for a tabular policy parametrization, it is delicate to relax it as we acknowledge and as it was mentioned in prior work. We note though that it is only a local assumption and this overparametrization assumption is natural when one looks at hidden convexity and the need to relate policies and occupancy measures. Trying to relax such an assumption is an interesting question.

• Regarding $\epsilon_{MLE}$, note that this assumption is only made in theorem 3 to show how the bound depends on the estimation error of occupancy measures. In corollary 2, it is actually not required as this estimation error is driven to zero using Proposition 1. Indeed by picking the number of samples $n = \mathcal{O}(m/\epsilon^2)$ in corollary 2, the error $\epsilon_{MLE}$ is smaller than the desired function value gap accuracy $\epsilon$. Therefore there is no error floor that cannot be reduced in corollary 2. This is consistent with the fact that occupancy measures are realizable and we can approximate them arbitrarily well using enough samples (see Proposition 1). We will make this clearer in the paper.

Question 3: Occupancy measure estimation. Assuming i.i.d. sampling is somewhat problematic. It means n is actually the number of trajectory, not state-action pairs. The authors may consider making this more explicit in the paper, adding proper factors to the sample complexity results (at least an H factor shall be needed). Perhaps the results could look be refined by using more refined analysis for sampling and estimation from Markov chains. For the undiscounted case "Hoeffding's inequality for general Markov chains and its applications to statistical learning" Fan et al. 2021. For the discounted case "A tale of sampling and estimation in discounted reinforcement learning" Metelli et al. 2023.

Response to Question 3 (also to weakness 4):

We do not require this iid assumption in the analysis, it is just to simplify the exposition in the main part and gain some space in the main part by deferring the sampling mechanism for states to appendix E.1. As for the horizon, we need to set it to $H = \mathcal{O}(1/(1-\gamma) \log(1/\epsilon))$. We thanl the reviewer for the comment, we will make this clearer.

Question 4: I am not very familiar with the analysis of Barakat et al. 2023. [...] Aside from MSE and MLE step, what makes Barakat et al. analysis break for global optimality?

Response to Question 4 (also to weakness 1):

Apart from the use of smoothness, our global optimality analysis is completely different.

• The first order stationarity analysis is based on exploiting smoothness of the objective alone as it is standard in smooth optimization.
• We need to exploit hidden convexity to obtain global optimality and we isolate and propagate errors induced by occupancy measure approximation in the PG method.
• This leads to a function value gap recursion with errors satisfied by the optimality function value gap. See lines 814 to 831 for details compared to p. 41-44 in Barakat et al. 2023. In contrast, first-order stationarity immediately follows from telescoping the smoothness inequality.
• In particular, our occupancy measure estimation and error control are different, our technical analysis is different and our guarantee is itself much stronger (our last-iterate global optimality vs best iterate first order stationarity).

Question 5: The results in the paper are provided for the discounted setting. In principle, can we use the same technical tools to study undiscounted settings, with finite or infinite horizon?

Response to Question 5. For the undiscounted setting with finite horizon, the answer is yes. One would need to be careful about modifying the occupancy measure estimators and the description becomes cumbersome if one decides to introduce non-homogeneous time-dependent state transitions as is customary in the finite horizon RL setting. For the undiscounted infinite horizon, if you think about the average reward setting, then extra care is needed as this case introduces some additional difficulties, note that PG convergence rates in this setting are very recent (see e.g. Kumar, Murthy et al. Global convergence of PG in average reward MDPs, ICLR 2025). This is an interesting direction for future work given the importance of the average reward.

Question 6: "Assumption 2 is satisfied for instance for the class of generalized linear models". Well, this is not supported when realizability is included in the assumption. Better to clarify in the text.

Response to Question 6 (Assumption 2 (ii)): The realizability assumption holds in the case of low-rank MDPs. As we discuss in l. 230, state occupancy measures are linear in density features in low-rank MDPs as we prove it in appendix C. Beyond this low-rank case, we can also safely relax this realizability assumption in our analysis at the price of an error floor due to function approximation that cannot vanish if the true occupancy measures do not belong to our function approximation class. We will clarify this further in the text.

Question 7: The discussion of the related work looks mostly complete. Perhaps Cheung 2019 and the pair Prajapat et al. 2023, De Santi et al. 2024 could also be mentioned.

Response to Question 7: Additional related work. Thank you for mentioning these references. For the last two, submodular RL differs from convex RL in nature. Nevertheless we will add them in our related work for completeness as they also propose an interesting approach to go beyond standard linear RL.

We appreciate the reviewer’s careful and constructive feedback. We believe the revisions and clarifications above highlight the novelty and value of our contributions more clearly. We respectfully hope the reviewer will reconsider their evaluation in light of these updates.

We thank the reviewer for their time in evaluating our work and for their useful feedback.

Weakness 1: Assumption on known utility: This paper assumes that is known to calculate , which is used in the "policy gradient" in Equations (4) and (5). While this assumption is without loss of generality for standard RL (known reward does not make problem easier), it might significantly reduce problem difficulty for more general (or even concave) utilities.

Response to Weakness 1: As with most works in RLGU, our setting assumes access to the gradient of the known utility function $F$, which reflects the problem’s objective and is typically task-defined (e.g., entropy, divergence or quadratic, see also Mutny et al., 2023 for other examples). This assumption is standard in the literature (see e.g. Hazan et al. 2019, Zhang et al. 2020-2021, Bai et al. 2022, Barakat et al. 2023, Ying et al. 2023a,b), and allows us to isolate the optimization challenges inherent to non-linear, global objectives in RL. We will expand this discussion in the revised version.

Weakness 2: Lacking empirical verification: Did not provide empirical validations of the proposed algorithms, on either synthetic or practical environments. This weakens the importance of RLGU to real-world problems.

Response to Weakness 2:

We agree that practical validation of our algorithm in function-approximation settings is an important direction, and we are actively exploring this. Our current focus is to first establish a theoretical foundation — particularly global optimality guarantees — which had not previously been achieved for RLGU.

Question 1: Can you discuss about the cases of unknown F? For example, if the MDP is tabular and we only know that F is concave, how much difficulty will removing the knowledge of F impose on deriving a similar guarantee?

Response to Question 1: We need some form of feedback on the function $F$ to be optimized. If it is fully unknown and we do not have access to any form of feedback, then there is not much we can do. In our case, we only have access to a gradient oracle (gradient can be computed) as it is standard in the literature. If the reviewer is thinking about weaker forms of feedback such as zeroth order access to $F$ or some bandit feedback, then we believe this offers some interesting opportunities for future work using zeroth order optimization techniques or regret analysis for bandit feedback. We leave such investigations for future work.

Question 2: Can you provide real-world examples aside from standard RL that RLGU plays an important role? Is there any existing habitats or benchmarks for this problem?

Response to Question 2:

• As we briefly discuss in the introduction, there are plenty of applications for RLGU beyond standard RL. We provide more concrete applications in what follows building on the examples in the introduction:

  • (1) Pure exploration of state spaces (e.g. Hazan et al. ICML 2019), concrete applications include autonomous exploration of robots such as drones or Mars rovers where agents are tasked with mapping unknown environments without specific downstream tasks, in this reward-free setting, agents seek to maximize information gain, coverage, or novelty; another compelling application in this setting is scientific discovery: Robots or agents exploring chemical or material design spaces to uncover new compounds, protein discovery as well;
  • (2) Imitation learning (e.g. Ho and Ermon, NeurIPS 2016), applications in this setting include learning from diverse human demonstrations and social navigation where robots learn to imitate various crowd navigation strategies,
  • (3) Experiment design (e.g. Mutny et al., AISTATS 2023) in science where an agent chooses experiments to maximize expected informativeness,
  • (4) Diverse skills discovery (e.g. Eysenbach et al. ICLR 2019) in robotic tasks with the unsupervised emergence of diverse skills, such as walking and jumping.
  • (5) Pluralistic alignment (e.g. of LLMs), see e.g. Chakraborty et al. ICML 2024, 'MaxMin-RLHF: Alignment with Diverse Human Preferences'.

• Regarding benchmarks, for instance in (Ho and Ermon, 2016) and (Eysenbach et al. 2019), they adapt the standard continuous control task benchmark of Brockman et al., 2016 in standard RL. Existing works test their approach on specific applications. We are not aware of an established benchmark for RLGU with diverse objectives. We believe that such a benchmark would be clearly valuable for advancing the impact of RLGU in practice. Our contributions are primarily theoretical though.

We appreciate the reviewer’s careful and constructive feedback. We believe the revisions and clarifications above highlight the novelty and value of our contributions more clearly. We respectfully hope the reviewer will reconsider their evaluation in light of these updates.

We thank the reviewer for their time and feedback. We are glad the reviewer appreciates our contributions and finds them an ‘important supplement in the RLGU community’.

Weakness 1: The analysis considers only a single‑step gradient update in the inner loop. Although multi‑step updates are briefly mentioned, no formal analysis is provided, limiting applicability to implementations that use multiple inner‑loop steps.

Response to Weakness 1: We do not mention multi-step generalization, but if you are alluding to the occupancy measure step or the PG step as inner-loop, Our analysis can easily be adapted to handle multiple gradient steps, this can only improve our results. Once can also use multiple gradient ascent steps in MLE in practice.

Question 1: Is the assumption of bounded gradients truly necessary, or could the results be generalized under weaker moment assumptions (e.g., bounded variance or sub‑Gaussian tails)?

Response to Question 1: We do not make a boundedness assumption on the gradients of the objective function with respect to its policy parameters. The only boundedness assumption we make is that of the pseudo-reward functions in Assumption 4, as $\nabla_{\lambda} F(\lambda)$ plays the role of a pseudo-reward in our RLGU setting and it is a natural reward boundedness assumption that is standard in both RL as well as in RLGU, see e.g. Hazan et al., 2019; Zhang et al., 2020, 2021; Barakat et al., 2023; Ying et al., 2023a. We actually control the variance of our PG estimator precisely in p. 21-22 eqs. 31-35 using a minibatch of trajectories and a number of samples for occupancy estimation.

Question 2: Since global optimality is approached as the inner‑loop step size shrinks, how does this affect sample efficiency and convergence speed in practice? Does the theory support any practical heuristics for tuning the inner step size?

Response to Question 2: In practice, we can choose constant steps to ensure a good neural network function approximation of occupancy measures in MLE by running multiple steps of SGD with tuned constant stepsizes and then using the estimates to perform PG ascent with a constant step and appropriate minibatch size. We provide an analysis of the total sample complexity in corollaries 1 and 2 with the appropriate step sizes needed to obtain in-expectation first order stationarity for non-concave utilities and in expectation global optimality for concave utilities. Decreasing the step size as prescribed in theory is needed even in practice to reduce the training error.

We appreciate the reviewer’s feedback. We hope our clarifications address the concerns raised, and respectfully ask the reviewer to reconsider their evaluation in light of these updates.