On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learning
Authors: Anas Barakat
Souradip Chakraborty
Peihong Yu
Pratap Tokekar
Amrit Singh Bedi
Venue: NeurIPS 2025 poster ()
Keywords: policy gradient methods
reinforcement learning with general utilities
Primary area: reinforcement_learning

Abstract: Reinforcement learning with general utilities (RLGU) offers a unifying framework to capture several problems beyond standard expected returns, including imitation learning, pure exploration, and safe RL. Despite recent fundamental advances in the theoretical analysis of policy gradient (PG) methods for standard RL and recent efforts in RLGU, the understanding of these PG algorithms and their scope of application in RLGU still remain limited. In this work, we establish global optimality guarantees of PG methods for RLGU in which the objective is a general concave utility function of the state-action occupancy measure. In the tabular setting, we provide global optimality results using a new proof technique building on recent theoretical developments on the convergence of PG methods for standard RL using gradient domination. Our proof technique opens avenues for analyzing policy parameterizations beyond the direct policy parameterization for RLGU. In addition, we provide  global optimality results for large state-action space settings beyond prior work which has mostly focused on the tabular setting. In this large scale setting, we adapt PG methods by approximating occupancy measures within a function approximation class using maximum likelihood estimation. Our sample complexity only scales with the dimension induced by our approximation class instead of the size of the state-action space.

On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learning
Anas Barakat', Souradip Chakraborty", Peihong Yu², Pratap Tokekar", Amrit Singh Bedi
Singapore University of Technology and Design,
2 University Maryland-College Park, University of Central Florida
Abstract
Reinforcement learning with general utilities (RLGU) offers a unifying framework to capture several problems beyond standard expected returns, including imitation learning, pure exploration, and safe RL. Despite recent fundamental advances in the theoretical analysis of policy gradient (PG) methods for standard RL and recent efforts in RLGU, the understanding of these PG algorithms and their scope of application in RLGU still remain limited. In this work, establish global optimality guarantees of PG methods for RLGU in which the objective a general concave utility function of the state-action occupancy measure. In the tabular setting, we provide global optimality results using a new proof technique building recent theoretical developments RL using gradient domination. Our proof technique opens avenues for analyzing policy parameterizations beyond the direct policy parameterization for RLGU. In addition, we provide global optimality results for large state-action space settings beyond prior work which has mostly focused on the tabular setting. this large scale setting, we adapt PG methods by approximating occupancy measures within function approximation class using maximum likelihood estimation. Our sample complexity only scales with the dimension induced by our approximation class instead of the size of the state-action space.
the convergence of PG methods for standard
Introduction
Reinforcement learning with general utilities (RLGU) has emerged general framework unify range of RL applications where the objective of the RL agent cannot be simply cast as standard expected cumulative reward (Zhang et al., 2020). For instance, in imitation learning, the objective is to learn policy minimizing the divergence between the induced state-action occupancy measure and expert demonstrations (Ho and Ermon, 2016). In pure exploration, the goal is to learn policy to explore the state space in a reward-free setting by maximizing the entropy the state occupancy measure induced by the agent's policy (Hazan et al., 2019). Other examples include risk-averse and constrained RL (Garcıa and Fernández, 2015), diverse skills discovery (Eysenbach et al., 2019), and experiment design (Mutny al., 2023).
well known that the standard RL objective can written as a linear functional of the occupancy measure. To capture all the aforementioned applications, the RLGU objective is possibly nonlinear functional of the state action occupancy measure induced by the policy (Zhang et al., 2020). Due to non- non-lineen ooneeiicrr,ty, policy gradient algorithms for solving RLGU problems face the major bottleneck of occupancy measure estimation. Prior works (Hazan et al., 2019: Zhang et al., 2020) have mostly focused on the tabular setting where the state-action occupancy measure needs to be estimated for each state-action pair using Monte Carlo estimation via sampling trajectories. However, this setting is restrictive for larger state and action spaces where tabular methods become intractable due to
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

the curse of dimensionality, This scalability issue stands as an important challenge to overcome to establish RLGU as a general unified framework for which efficient algorithms exist to solve its larger state-action space instances.
The understanding of PG methods and their scope of application still remains limited despite recent fundamental advances in the theoretical understanding of PG methods for standard RL and recent efforts in RLGU. Specifically;
In the tabular setting, existing global optimality results rely on hidden convexity which consists in seeing the problem as a convex problem in the occupancy measure. This approach leaves unclear and open the question of the connection of existing analysis with the recent advances in the analysis of PG methods for standard expected return RL as highlighted as future work in Zhang et al. (2020).
Most existing results focus on the tabular setting. Beyond this restrictive setting, few recent results propose to approximate the occupancy measure using function approximation and either Mean Square Estimation (MSE) (Barakat et al., 2023) or Maximum Likelihood Estimation (MLE) (Huang and Jiang, 2024). However these works only establish first-order stationarity guarantees and hence fall short of providing global convergence guarantees for RLGU beyond standard RL. Moreover, they have several other limitations that render them either inefficient in addressing large state-action space settings due to a dependence on the state action space or suboptimal even for standard expected return objective function. We refer the reader to our related work section below and section 4.4 for a more detailed discussion.
Main contributions. In this work, we investigate the question of global optimality of PG methods for RLGU. Our contributions are summarized as follows:
In the tabular setting, we establish new structural property of the RLGU objective in the form of a gradient domination inequality (cf. Sec. 3). This result generalizes existing results for standard expected return objectives in RL and enables global optimality guarantees for PG methods in RLGU within the tabular setting.
We address the scalability challenge by proposing simple algorithm for the general and flexible RL.GU framework with global optimality guarantees. In this algorithm, an actor performs policy parameter updates whereas a critic approximates the state-action occupancy measure via maximum likelihood estimation (MLE) within a function approximation class (ef. Sec. 4). We analyze the sample complexity of our algorithm under suitable assumptions. Our analysis relies
total variation performance bound for occupancy measure approximation via MLE which scales with the dimension of the parameters of the function approximation class rather than the state-action space size. Using this result, we establish first-order stationarity and global optimality guarantees for our algorithm for nonconcave and concave utilities respectively (cf. Sec. 4.3).
Related Works. The general framework of RLGU, also known convex RL, has been recently introduced in the literature (Hazan et al., 2019; Cheung, 2019; Zhang et al., 2021; Zahavy et al., 202 :; Geist et al., 2022; Bai et al., 2022). Hazan et al. (2019) initially focused the particular instance of maximum entropy exploration problem and Zhang et al. (2020) proposed a variational policy gradient method to solve the RLGU problem. Zhang al. (2021) then introduced simpler (variance-reducee) policy gradient method to solve the (possibly nonconcave) RLGU problem using a simpler policy gradient theorem (see also Kumar et al. (2022)). Later, Barakat al. (2023) proposed an even simpler single-loop normalized policy gradient algorithm to solve RLGU. Zahavy et al. (2021) leveraged Fenchel duality cast the convex RL problem into a saddle-point problem that be solved using standard RI. algorithms. In a line of works, Mutti et al. (2022b,a, 2023) formulated the convex RL problem in finite trials instead of infinite realizations and considered an objective which is any convex function of the empirical state distribution computed from a finite number of realizations. Ying et al. (2023a) introduced policy-based primal-dual methods for solving convex constrained CMDPs and Ying et al. (2023b) further addressed a multi-agent RL problem with general utilities. All the aforementioned works focus on the tabular setting. In particular, most of these works use a count- count-based Monte Carlo estimate of the occupancy measure that cannot scale to large state-action spaces. More recently, Huang et al. (2023) provided sample-efficient online/offline RL algorithms with density features in low-rank MDPs for occupancy estimation. Only few recent works (Barakat et al., 2023; Huang and Jiang, 2024) propose to go beyond the tabular setting, we discuss them in more details in section 4.4. See also appendix B for more detailed related work discussion.

---

Notation. For given finite set A' we use the notation |2'] for its cardinality and A(X) for the space of probability distributions over X. We equip any Euclidean space with its standard inner product denoted by (:::) The notation || refers to both the standard 2-norm for vectors and the spectral norm for matrices. We interchangeably denote functions f X - over finite set as vectors
R X1 with components f()) with slight abuse of notations.
2 Problem Formulation
MDP with General Utility. Consider a discrete-time discounted Markov Decision Process (MDP) (S, F, p, where S and A are finite state and action spaces respectively, P x A - (S)) is the state transition probability kernel, F A - a general utility function defined over the space of probability measures on the product state-action space X S x A, p is the initial state distribution, and E (0, 10 is the discount factor. A stationary policy π S + A (AA maps each state S a distribution (-[ss) over the action space A. The of all stationary policies is denoted by IT. At each time step / E N in state E S, the RL agent chooses an action E .A with probabil- ity (a, st) and then environment transitions to a state st+1 S with probability P(s++1|$ at). We denote by Pp. the probability distribution of the Markov chain (st. IEN induced by the policy π with initial state distribution p. We use the notation Ep,- (or often simply E) for the associated expectation. We define for any policy π E II the (normalized) state and state-action occupancy measures d= E X E A(S x A) respectively!:
(=) = (1 - 7) Σ 7 (s:
The general utility function F assigns a real to each occupancy measure x induced by a policy π E II. We note that X will also be seen as a vector of the Euclidean space R SH-AAI, In the rest of this work, we will consider class of policies parametrized by vector 0 Idd for some fixed integer d E N. We shall denote by Te E Il such policy in this class.
Policy optimization. The goal of the RL agent is to find a policy my solving the problem:
max F(A*"),
BER4
where A is defined in (1), F is smooth function supposed to be upper bounded and F is used to denote the maximum in (2). The agent has access to trajectories of finite length generated from the In particular, provided time horizon H and
MDP under the initial distribution and the policy a policy To with 0 E Ted, the learning agent can simulate a trajectory т = (sg. ... 88 11) from the MDP when the state transition kernel P is unknown. This general utility problem was described, for instance, in Zhang et al. (2021) (see also Kumar et al. (2022)). Recall that the standard RL problem corresponds to the particular case where the general utility function is linear function, i.., F()**) = (r, XT)) for some vector r E RIS)-IA in which case we recover the expected return function as an objective:
T (r) = E. B.p.
Er'r(ss,
Remark We prefer the terminology of 'RL with general utilities' to 'convex RL' since the objective may even be nonconvex in the occupancy measure in full generality. Although our focus in this work on concave utilities, we provide first-order stationarity theoretical guarantees for the nonconcave case. While the convex RL literature exclusively focuses the case of concave utilities, lot of applications of interest do not fall under this umbrella and inherently involve nonconcave utilities. We provide several such examples in Appendix D.
3 Global Optimality in the Tabular Setting
In this section, our main goal is to establish a structural property of the RLGU objective as a function of its policy parameters depending the policy parameterization. Recall that even when
'We mostly drop the dependence on the initial distribution in the notation throughout the paper, except for the statement and proof of Theorem 1.
3

---

the functional F' is concave in the occupancy measure. the RLGU objective is in general nonconcave in the policy parameters. Recent works in the last few years (Agarwal al., 2021: Bhandari and Russo, 2024; Mei et al., 2020) have shown that the expected return in standard RI., which is also nonconcave in the policy parameters, satisfies a gradient domination inequality. This interesting property implies that any stationary point of the objective is actually a globally optimal point. In this section we extend this result to RLGU and show that the RLGU objective function also satisfies a similar, but different, gradient domination inequality when the functional F is concave. Our results open an avenue for going beyond expected return objectives by exploiting the underlying dynamic programming structure of occupancy measures which is key to our results.
In view of our analysis, we recall how to derive the policy gradient for the general utility objective. For convenience, we use the notation X(0) for A Since the cumulative reward can be rewritten more compactly V* (r) = (A*1,, r),, it follows from the policy gradient theorem that:
+oo Σ
log no (ax [s))
[v\(1)]T = VoV=e(r) (r) = E,,s
7'r(SE, as)
(4)
where VoA(0) is the Jacobian of the vector-valued mapping A(0) - Using the chain rule, we have VoF(A(0)) [V
VoV"*
(r))==AAP(10))
(5)
The classical policy gradient in the standard RL setting uses rewards which are obtained via interaction with the environment. In RLGU, there is no reward function but rather a pseudoreward V ((((O))) depending on the unknown occupancy measure induced by the policy. We assume that the gradient of F w.r.t. its variable is known function the agent. This is the case in most prior works, e.g. when F is the negative entropy function in pure exploration (Hazan et al., 2019), or a KL divergence in imitation learning (Ho and Ermon, 2016). penalized objective in constrained RL, or other objectives in experiment design (Mutny et al., 2023). The policy gradient identity (5) shows that the gradient of the RLGU objective with respect its policy parameters coincides with the standard expected return policy gradient evaluated at the reward function V V)((O))) This observation is essential for our development and we believe it could be of independent interest in settings involving varying rewards as a function of policy parameters. Using this key insight, the next result shows that the RLGU objective satisfies a gradient domination inequality when the policy parametrization tabular, extending the structural result for standard expected return (Agarwal et al., 2021; Bhandari and Russo, 2021; Xiao, 2022).
Assumption (Concavity). The utility function
+ R is concave.
Theorem 1. (RLGU objective gradient domination) policy parametrization (To(a)s) = for all (8,a) E S x A). Then for every O E Rd.
Let Assumption I hold. Consider a direct
dp (VxF(M()))
1
F(X(0)) F(((0))
max TT, VoF(X(0))),
(6)
1
1
REll
where d = -| [A], x² (r) E arg max (T for any r E RISHA 8r is an optimal policy parameter and is any state distribution s.t. uus) > 0 for all states E S.
A few comments are in order regarding this result:
The gradient domination inequality depends on a distribution mismatch coefficient which itself depends the pseudo-reward function V F(AOO). Theorem I recovers the standard gradient domination result linear RL, as in Lemma 4. Agarwal et al. (2021), when the pseudo-reward is constant and equal to the true reward.
The mismatch coefficient is finite for any 0, provided the reference distribution has full support.
one seeks a uniform upper bound over all 0, the coefficient can be large. However, this worst-case bound is still finite, and can be upper-bounded by the state space size if μ is uniform. It can also be upper bound by its maximum over the reward functions which are bounded by the range of pseudo-rewards (see e.g. Assumption 3).

---

Remark 2. Recall that we assume throughout the paper that the state and action spaces are finite as mentioned in section 2. In particular. Theorem holds under this setting. While we mention the applicability of our algorithm to continuous state spaces in practice (in remark 3 below), the current analysis does not readily extend to that setting. Ensuring boundedness of the distribution mismatch coefffcient can be challenging beyond our finite setting, as mentioned in e.g. Koren et al. (2025) showing that policy gradient methods can then converge to locally (in contrast to globally) optimal policies (in classical linear RL).
Proof. We introduce few useful notations for the state action value functions induced by any fixed reward functions r E IR (RSS)AA and any 0 E Rdd for (8, a) E S x A:
t00 Σ
(r((s, 0, d V (r) = Σ Q7a (7)
Qua (r) == Ep,
REA
Proof. First, using the gradient domination result (Agarwal et al., 2021, Lemma 4) for standard expected return and any fixed reward function r, we obtain for every tabular policy n,
(r)
1
V (+) (r)
max REA(A)iS)
( V,VV
(8)
Plugging in m =g V and using (5), we get
1 dz (ro)
- -V S 1 1-7
max ( x, VoF(X(0)))
(9)
REALAJIS]
As (r) E arg n V (r), we have V Va (r) 2 (r) for every policy π. Using this inequality with π = TT arg max F(X²) gives
(=*(ro)(re) - (ro) V* (re) - (x0 = (ro, - xnd) F(X(0") F(X(0)), (10)
where the identity stems from the definition of a value function using occupancy measures and the last inequality follows from using concavity of F w.r.t. its occupancy measure argument (Assumption 1). Combining (9) and (10) concludes the proof.
Note that in the last step, we have only used concavity at given point A= which means that only weaker version of Assumption is needed. This means that we can potentially go beyond standard objectives in RLGU. We leave such investigations for future work.
Gradient domination incqualities can be readily used to show ((1kk) iteration complexity results for policy gradient methods using similar techniques to Xiao (2022) for instance (see also more recently Kumar et al. (2024) for actor-critic methods). Zhang et al. (2021) previously provided global optimality results for PG algorithm using hidden convexity. However their technique has several limitations: (a) it does not connect to structural properties of standard expected returns and standard policy gradients. In particular they do not show gradient domination for RLGU objectives as developed above and this is explicitly mentioned in their work; and (b) it requires a restrictive assumption (see (5) below) that is not easily verifiable beyond the tabular policy. We believe that our proof technique can be extended to the case of the softmax policy building on the results of Mei et al. (2020) (Lemma 8 specifically). We leave this question for future work.
4 Global Optimality Beyond the Tabular Setting
In this section, we propose policy gradient algorithm to solve the policy optimization problem (2) with general utilities for larger state-action spaces. We start by elaborating on the challenges faced to solve such large-scale problem. Section 4.1 mainly contains known material from the recent literature (Zhang et al., 2021), we report here separately from the problem formulation in section to motivate our algorithmic design. The rest of the section presents our algorithmic contributions.
5

---

4.1 Challenges for Large-scale RLGU
One of the main challenges in solving the general utility problem (2) via policy gradient algorithm based on (5) is to estimate the unknown state-action occupancy measure A(0) in large scale settings involving huge state and action spaces. This problem is arguably more delicate than that of estimating action-value functions in cumulative expected reward RI. problems. First, while action-value functions satisfy forward Bellman equation, occupancy measures satisfy a backward Bellman flow equation. This fundamental difference makes it hard to design stochastic algorithms minimizing mean-square Bellman errors as it is eustomary in algorithms using function approximation to solve standard RL. problems (see end of appendix B for further explanations). Second and foremost, while prior work has used Monte Carlo estimates for this quantity, such count-based estimates are not tractable beyond small tabular settings. Indeed, for very large state-action spaces, it is not tractable to compute and store a table of count-based estimates of the true occupancy measure containing all the values for all the aate-nctionn pairs. In the next section, we propose an approach to tackle this issue.
Stochastic Policy Gradient. In view of performing a stochastic policy gradient algorithm, we would like to estimate the policy gradient Vo F F()))) in (5). We can use the standard reinforce estimator suggested by Eq. (4). Define for every reward function (which is also seen as a vector in R (S x (AA),, every 8 E Rd and every H-length trajectory 7 simulated from the MDP with policy Ty and initial distribution p the (truncated) policy gradient estimate:
H-1
H Σ A=!
g(T,0,r) 0,r)
Σ
>rr(s,, an)
V log (a(a)))))-
(11)
t=
Given (5), we also need to estimate the state-action occupancy measure A(0) (when F is nonlinear)?. Prior work has exclusively focused on the tabular setting using Monte-Carlo estimate of this occu- pancy measure A = x()) (see (I)) truncated at the horizon H by A(r) = Σ - 7 Sss.. where for every (s, a) A 6,.a E R [| is a vector of the canonical basis of IR || i... the vector whose only non-zero entry is the (s, a)-th entry which is equal to 1, and T { an) JosAss--- is a trajectory of length H generated by the MDP controlled by the policy πg.
Remark 3. (Extension to continuous state-action spaces) Our algorithm can be used in the continuous (compact) state-action space setting since it only relies on using policy gradients and MLE which are both scalable. We stick to the discrete state action space notation for simplicity.
4.2 Occupancy Measure Estimation
In this section, we address the challenge of occupancy measure estimation in large state action spaces. Given policy Te, our goal is to estimate the unknown occupancy measure d induced by this policy using state samples obtained from executing the policy. Since the normalized occupancy measure is probability distribution, we propose to perform maximum likelihood estimation. Before presenting this procedure, we elaborate on the motivation behind approximating the occupancy measure by parametrized distribution in a given function class of neural networks for example.
Motivation. Besides the practical motivation of using distribution approximation to scale to larger state-action space settings, we provide some theoretical motivation. Recall that action-value functions are linear in the feature map for lincar (or low-rank) MDPs for solving standard cumulative sum RL problems (see Proposition 2.3 in Jin et al. (2020)). Similarly, it turns out that state-occupancy measures linear (or affine in the discounted setting) in density features in low-rank MDPs. We refer the reader to Appendix C for a proof of this statement (see also Lemma 16, 17 in Huang et al. (2023)). Therefore, in this case, it is natural approximate occupancy measures via linear function approximation using some density features. More generally, for an arbitrary MDP, we propose to approximate the (normalized) state occupancy measure d induced by policy me directly by probability distribution in a certain parametric class of probability distributions:
A := (p. E A(S) w Ω C E
(12)
where for instance m < [S]. An example of such parametrization for a given w E Rmm is the softmax aw defined over the state space by (s) == (s)))) where Z(w) :=
In the cumulative reward setting, the utility F' is linear w.r.t À and VxF(A(0) is independent of A(0)

---

Eves (s)) and where Uh : S - R is a given mapping which can be neural network practice. For continuous state spaces, practitioners can consider for instance Gaussian mixture models with means and covariance matrices encoded by trainable neural networks.
Maximum Likelihood Estimation (MLE). For simplicity, suppose have access to i.i.d. state samples following the distribution d= throughout our exposition. We refer the reader to Appendix E, for discussion about how to sample such states. Given the parametric distribution class A defined in (12) and a data set D := f=i.i=l..... E S" of n i.idd state samples following the distribution dt induced by the current policy Te. we construct the standard MLE
1 Σ (s:).
jTe = P
w² E arg max WEG C
(13)
An estimator of the state-action occupancy measure x is then given by (s, a) d (s) [a(a]s)
for any 8 A, a A (see (I)). Using MLE is important for our scalability goal. Barakat al. (2023) recently proposed a different procedure based on mean square error estimation. Please see appendix B for detailed comparison with this work highlighting the merits of our approach. In practice, a neural network learns the parameters of a chosen parametrized distribution class for approximating the true occupancy measure by maximizing the lig-liicl loss (13) over the samples generated (see appendix E. for sampling).
Proposed Algorithm. Based on sections 4.1 and 4.2, we propose stochastic policy gradient algorithm which consists of two main steps: (i) Compute an approximation of the unknown state- action occupancy measure A (R x AA] for a fixed parameter E Rd with MLE using collected state samples (see (13)); (ii) Perform stochastic policy gradient ascent using the stochastic policy gradient defined in (11) using the estimated occupancy measure computed in step (i). The resulting algorithm is Algorithm I which is model-free we do not estimate the transition kernel.
Algorithm 1 PG for RLGU with Occupancy Measure Approximation (PG-OMA)
1: Input: 0g E R T, 2 1, > 0, H.
2: for t = 0...., do
//Occupancy approximation for pseudo-reward learning
3: Compute the MLE estimator X₃ = d TT, using policy ne, (see (13)).
4:
fv=V,F(A.
//Policy parameter update
5: Sample batch of N independent trajectories )ssigN of length H using To
6: 0,41 = 0: + E g(7(") 0r, fr) (see (11))
7: end for
8: Return: 04
Remark 4. When running Algorithm 1, note that the vector S E RISIXIA (and hence the vec- tor re) is not computed for all state-action pairs. Indeed, at each iteration, one does only need to (t) compute (re(s) ai JogKsH- where Tt (s .0h )ogngH-1 to obtain the stochastic policy
(t) (t)
gradient g(T,, Be, r--1) as defined in (11).
Our occupancy measure estimation step can be seen critic for pseudo-reward learning. Notice though that this critic is not approximating value function like in standard RL but rather the occupancy measure which is a distribution.
4.3 Global Optimality for Policy Gradient with Occupancy Measure Approximation
Statistical Complexity of Occupancy Estimation. this section, we suppose we are given data set of i.i.d. state-action pair samples following the (normalized) occupancy measure x induced by
fixed given policy π. As previously explained, we approximate X by function (or parametrized density) in the function class A defined in (12). We make the following assumption to control the complexity of our function approximation class.

---

Assumption 2 (Function approximation class regularity). The following holds true:
(i) (parameter compactness) The set Qt is compact, we denote by Bw ea |wolooo (ii) (realizability) The (normalized) occupancy measure be estimated satisfies: X= A:
(ii) (Lipschitzness) Vu, @ E Q, Va X, (,(( E R.s. (po(z)-pa(x)) pa)( L(x) | w with B, == Jx ((r)dr= < to0.
Assumption 2 is satisfied for instance for the class of generalized linear models, i.e. A == {2) g(w" o(z)), Vr E X' : Pw E A(X), E Ω2} where g R + [0, is an increasing Lipschitz continuous function and Φ X' - R is given feature map s.t. f [lo())]l I B2 for some B2 > 0. Notice that features can be normalized appropriately to satisfy the assumption. A similar assumption has been made in the case of linear MDPs in Huang et al. (2023) (Assumption 1). The realizability assumption holds in the case of low-rank MDPs since state occupancy measures are linear in density features low-rank MDPs (see discussion in section 4.2 and Appendix C). This realizability assumption can be relaxed the price of incurring error due to function approximation that cannot vanish the true occupancy measures do not belong to our function approximation class.
We now state our sample complexity result for occupancy measure estimation via MLE in view of our PG sample complexity analysis. This result relies on arguments developed in the statisties literature Van de Geer (2000); Zhang (2006). These techniques were adapted to the RL setting for low-rank MDPs in e.g. Agarwal et al. (2020). Our proof builds on Huang et al. (2023) which we slightly adapt for our purpose (see Appendix E.2).
Proposition 1. Let Assumption 2 hold true. Then for any 5 > O. the MLE A defined using
12 log 21 8,
(13) satisfies with probability at least 1 - 5, _1 A= s <9
The above result translates into a sample complexity of )m) to guarantee an e-approximation of the true occupancy measure (in the / -nom distance) using samples. We highlight that sample complexity only depends on the dimension m of the parameter space and does not scale with the size of the state-action space. Hence the MLE procedure we use is the key ingredient scale our algorithm to large state-action spaces. To the best of our knowledge, existing algorithms for solving the RLGU problem (with nonlinear utility) are limited the restrictive tabular setting.
Global convergence guarantees. Now we establish sample complexity guarantees for Algorithm 1. We start by introducing the assumptions required for our results and discuss their relevance.
Assumption 3 (Policy parametrization). The following holds for every (s,a) E 8 A. For every 0 E Rd. (a(a)s) > 0. Moreover, the function 0 Te(als) is continuously differentiable and the score function 0 + V log (a s) is bounded by some positive constant B.
This standard assumption is satisfied for instance by the common softmax policy parametrization expls(s.a::))
defined for every 0 E Rd, (s) E Ay re(als) Ea'ea exp(v[s.a'.8]] where v AxAxR R is a smooth function such that the map (s,,, a; is twice continuously differentiable for every (s, a) 8 A and for which there exist L4, Lp > 0 s.t. (i) max.es, sup, [|Vu(s,, a; 0)]l L. and (ii) max sup, 2 f)ll < Ly.
We now make smoothness assumption on the utility function which is standard in the RLGU literature (Hazan et al., 2019; Zhang et al., 2020, 2021; Barakat et al., 2023; Ying et al., 2023a). 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 12 (quadratic) losses are also possible. For instance, the smoothed entropy defined as (x) -r log(æ + o)) (for > 0) is 1 smoothh w.r.t. the infinity norm and has been used RLGU, see e.g. Lemma 4.3 in Hazan al. (2019).
Assumption 4 (General utility smoothness). There exist constants Ix, LA > 0 s.t. for all >1, E A. [|)))())) la and [\vxF())) vxF()2)l22 < Lx|lAi A2ll2.
8

---

Under Assumptions 3 and 4, the function 0 + F(X*)) is Lg-smooth (see Lemma 3 for the expression). Using this property, the next result shows that our algorithm enjoys first-order stationary guarantee in terms of the non-convex general utility objective.
Theorem 2. (Nonconcave general utility) Let Assumptions 4 hold. Then the iterates generated by Algoritim with step sizes 0t S 1/(2)))) and T 2 1 iterations satisty:
B F(A*==()))))))) >1 16(F* [[ I]) C1
N + +CAEIII, x
(14)
aT
where I is a uniform random variable over {1, .) and expectation is w.r.t. all randomness (in (0t) and T).
The above upper bound shows decomposition of the first order stationarity error into three terms: the first two are the typical errors incurred by PG methods whereas the third one is due to occupancy measure approximation. In particular, choosing the number of iterations T, the batch size N (of sampled trajectories) appropriately and the number n of samples used in MLE for occupancy measure approximation, we obtain the following sample complexity result.
Let Assumptions 2, 3, hold. Setting the number of iterations to T' O ) the batch size for PG to N = Oe)-),, the horizon to H = O log())) and the number of samples for occupancy measure MLE holds that E F() )l1² I c. The total sample complexity is T(N + +n) Ö(me- a
Corollary
(me for some precision > in Theorem
"The notation (-)) hides polynomial and logarithmic dependence on problem parameters independent of the desired accuracy and the dimension m, (-)) hides in addition logarithmic dependence
In several applications in RLGU, the utility function F is concave w.r.t. its occupancy measure variable. We now turn to proving global performance bounds in this setting.
Notice that the general utility objective is in general nonconcave w.r.t the policy parameter A. exploit the so-called hidden convexity (concavity in our setting)
Despite this non-concavity, of the problem Zhang et al. (2021). We require an additional regularity assumption on the policy parametrization which has been previously made in Zhang et al. (2021); Ying et al. (2023a); Barakat et al. (2023). This is a local assumption relating parameterized policies and their corresponding occupancy measures, maintaining the hidden convexity structure. While this assumption holds for tabular policy parametrization, it is delicate to relax it further, see e.g. Appendix C in Barakat et al. (2023) for a discussion.
Assumption 5 (Policy overparamettiization) For the softmax policy defined above, the following three requirements hold: (i) For any 0 E Idd there exist relative neighborhoods Ue c Ra and Vx(0) C. A respectively containing 0 and X(8) s.t. the restriction Xlua forms a bijection between Mg and Vx(e; ; (ūi) There exists
0 s.l. for every E IRd, the inverse (Alu4,
L-Lipschitz continuous; (ūi) There exists vj > 0 s.1. for every positive real n S 7. (1-) + 1)* E Vx(e) where zg- is an optimal policy.
The following result makes use of the concavity of the utility function F to obtain global optimality guarantce for the iterates of our algorithm under the assumption that the occupancy measures induced by the policies encountered during the run of the algorithm are uniformly well-approximated.
Theorem 3. (Concave general utility) Let Assumptions to 5 hold. Assume furthrr that there exists EMLE > 0 s.t. E| x(00111 S CALE uniformly over T 2 1 iterations of Algorithm
with step sizes a4 < 1/LL).. Then the iterate output Or of Algorithm 1 satisfies for any v) < 7
E - F(X(O)) S < 7)= C3 + C4 a + EMLE
(15)
1 N
for some positive constants C3, C4 explicit in Appendix E.4, (53) and ón = EFF -F((()))
The above bound shows how the global optimality function value gap depends on the estimation error EMLE of occupancy measures. In the next result, use Proposition to reduce the estimation

---

error. Since occupancy measures are supposed to be realizable, we can approximate them arbitrarily well using enough samples (see Proposition 1). Indeed by picking the number of samples O(m/c"), the error <MLE is smaller than the desired function value gap accuracy
We obtain the following sample complexity by specifying the step size and number of iterations of our algorithm as well as large enough batch size and number of samples for MLE using Proposition 1.
0, set T ( ) O(e), O N 3)c H O _ log(?)) and O(me 3). then the total sample complexity to obtain E[F F()(0.)) - c is T(N + H) = Ó
Corollary 2. Let Assumptions 2 5 hold. For any given precision 7 log( du
4.4 Novelty and Comparison to Prior Work
In this section, discuss the two most relevant works (Barakat et al., 2023; Huang and Jiang, 2024).
Comparison to Huang and Jiang (2024). They focus primarily on the fnnieehorizon, expected return setting, with brief extension to general utilities leaving global optimality for future work. In contrast, our work directly targets fiinite-horizon discounted RLGU. Furthermore, we establish a last-iterate global convergence guarantee with rate for RLGU, improving upon their best-iterate rate for expected returns. Their analysis does not immediately extend to RLGU. Finally, although we both use MLE occupancy measure estimation, their method requires estimating both occupancy and log-gradient occupancy via recursive regression, introducing additional estimation error. Focusing on the online setting, method only requires MLE occupancy estimation.
Comparison to Barakat al. (2023, section 5). Before commenting on the limitations in the MSE approach of Barakat et al. (2023) for scaling to large spaces, we highlight first two preliminary points: (a) Global convergence. In contrast to our work which establishes global convergence guarantees (see Theorem 3, Corollary 2). Barakat et al. (2023) only provide a first-order stationarity guarantee; (b) Technical analysis. Our occupancy measure MLEE estimation combined with our PG algorithm requires different analysis even for our first-order stationarity guarantee. We exploit hidden convexity (similarly to Zhang et al. (2021)) to obtain global optimality and we isolate and propagate errors induced by occupancy measure approximation in the PG method. This leads to function value gap recursion with errors satisfied by the optimality function value gap. See appendix Furthermore, Barakat et al. (2023) propose to approximate the occupancy measure using a specific mean square error loss estimation procedure whereas we use an MLE procedure. This difference is important given the main goal and motivation of scaling to larger state action spaces. We argue that their MSE formulation has important limitations for occupancy measure approximation in terms of scalability and other fundamental aspects (see appendix B for detailed discussion).
Conclusion
In this paper, we have investigated the question of global optimality of PG algorithms for RLGU beyond the standard expected return RL setting in both the tabular and large state action space settings. Promising future directions include extensions to more general policy parameterizations. continuous state-action spaces, and average reward settings building on recent analysis of policy gradient methods (Kumar et al., 2025). We hope this work will stimulate further research in view of designing efficient and scalable algorithms for solving real-worle problems.
Acknowledgments and Disclosure of Funding
We thank anonymous reviewers for their useful comments.
References
Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. (2020). Flambe: Structural complexity and representation learning of low rank mdps. In Advances in Neural Information Processing Systems.
10

---

Agarwal, A., Kakade, S. M.. Lee, J. D., and Mahajan, G. (2021). On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1--7.
Bai, Q., Agarwal, M., and Aggarwal, V. (2022). Joint optimization of concave scalarized multi- objective reinforcement learning with policy gradient based algorithm. Journal of Artificial Intelligence Research.
Barakat, A., Fatkhullin, I,, and He, N. (2023). Reinforcement learning with general utilities: Simpler variance reduction and large state-action space. In International Conference on Machine Learning.
Bhandari, J. and Russo, D. (2021). On the linear convergence of policy gradient methods for finite mdps. In International Conference on Artificial Intelligence and Statisties.
Bhandari, J. and Russo, D. (2024). Global optimality guarantees for policy gradient methods. Operations Research, (2(5):1906-199)
Cheung. W. C. (2019). Regret minimization for reinforcement learning with vectorial feedback and complex objectives. Advances in Neural Information Processing Systems, 32.
De Santi, R., Prajapat, M., and Krause, A. (2024). Global reinforcement learning: Beyond linear and convex rewards via submodular semi-gradien methods. In International Conference on Machine Learning.
Eysenbach, B., Gupta, A., Ibarz, J., and Levine, S. (2019). Diversity is all you need: Learning skills without reward function. In International Conference on Learning Representationss
Fatkhullin, I., He, N., and Hu, Y. (2023). Stochastic optimization under hidden convexity. arXiv preprint arXiv:2401.00108
Garcia, J. and Fernández, F. (2015). A comprehensive survey on safe reinforcement learning, Journal of Machine Learning Research, 16(1):1437-148)
Geist, M., Pérolat, J., Laurière, M., Elie, R., Perrin, S., Bachem, O., Munos, R., and Pietquin, O. (2022). Concave utility reinforcement learning: The mean-field game viewpoint. In International Conference on Autonomous Agents and Multiagent Systems.
Hallak, A. and Mannor, S. (2017). Consistent on-line off-policy evaluation. In International Conference on Machine Learning.
Hazan, E., Kakade, S., Singh, K., and Van Soest, A. (2019). Provably efficient maximum entropy exploration. In International Conference on Machine Learning.
Ho, J. and Ermon, S. (2016). Generative adversarial imitation learning. In Advances in Neural Information Processing Systems.
Huang, A., Chen, J., and Jiang, N. (2023). Reinforcement learning in low-rank MDPs with density features. In International Conference on Machine Learning.
Huang, A. and Jiang, N. (2024). Occupancy-based policy gradient: Estimation, convergence, and optimality. In Advances Neural Information Prucessing Systems.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory.
Koren, U., Kumar, N., Gadot, U., Ramponi, G., Levy, K. Y., and Mannor, (2025). Policy gradient with tree search: Avoiding local optimas through lookahead. arXiv preprint arX1v:2506.07054.
Kumar, N., Agrawal, P., Ramponi, G., Levy, K. Y., and Mannor, S. (2024). On the convergence of single-timescale actor-critic. arXiv preprint arXiv:24
Kumar, N., Murthy, Y., Shufaro, I., Levy, K. Y., Srikant, R., and Mannor, S. (2025). Global convergence of policy gradient in average reward MDPs, In International Conference on Learning Representations.
11

---

Kumar, N., Wang, K., Levy, K., and Mannor, S. (2022). Policy gradient for reinforcement learning with general utilities. arXiv preprint arXiv:2210.0099.
Lin, K., Jie, C., and Marcus, S. (2018). Probabilistically distorted risk-sensitive infinite-horizon dynamic programming. Automatica, 97:1-6.
Lin. K. and Mareus, I. (2013). Dynamic programming with non-convex risk-sensitive measures. In 2013 American Control Conference, pages 6778-6783. IEEE.
Liu, J., Li, W., Lin, D., Wei, K., and Zhang. Z. (2025). On the convergence of projected policy gradient for any constant step sizes, Journal of Machine Learning Research, 26(193):1-35.
Liu, J., Li, W., and Wei, K. (2024). Elementary analysis of policy gradient methods. arXiv preprint arXiv:2404.0332 033772
Mei, J., Xiao, C., Szepesvari, C., and Schuurmans, D. (2020). On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning.
Mutny, M., Janik, T., and Krause, A. (2023). Active exploration via experiment design in markov chains. In International Conference on Artificial Intelligence and Statistics.
Mutti, M., De Santi, R., De Bartolomeis, P., and Restelli, M. (2023). Convex reinforcement learning in finite trials. Journal of Machine Learning Research, 24(250):1-42.
Mutti, M., De Santi, R., and Restelli, M. (2022a). The importance of non- non-markovianity in maximum state entropy exploration. In International Conference on Machine Learning.
Mutti, M., Santi, R. D., Bartolomeis, P. D., and Restelli, M. (2022b). Challenging common as- sumptions in convex reinforcement learning. In Advances in Neural Information Processing Systems.
Prajapat, M., Mutny, M., Zeilinger, M., and Krause, A. (2024). Submodular reinforcement learning. In International Conference on Learning Representations.
Prashanth, L., Jie, C., Fu, M., Marcus, S., and Szepesvári, C. (2016). Cumulative prospect theory meets reinforcement learning: Prediction and control. In International Conference on Machine Learning.
Van de Geer, S. A. (2000). Empirical Processes in M-estimation, volume 6. Cambridge university press.
Xiao, I.. (2022). On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23(282):1-36.
Ying, D., Guo, M. A., Ding, Y., Lavaei, J., and Shen, Z.-J. (2023a). Policy-based primal-dual methods for convex constrained markov decision processes. In AAAI Conference on Artificial Intelligence.
Ying, D., Zhang, Y., Ding, Y., Koppel, A., and Lavaei, J. (2023b). Scalable primal-dual actor- critic method for safe multi-agent RL with general utilities. In Advances in Neural Information Processing Systems.
Yuan, R., Du, S. S., Gower, R. M., Lazaric, A., and Xiao, (2023). Linear convergence of natural policy gradient methods with log-linear policies. In International Conference on Learning Representations.
Zahavy, T., O'Donoghue, B., Desjardins, G., and Singh, S. (2021). Reward is enough for convex mdps In Advances in Neural Information Processing Systems.
Zhang, J., Koppel, A., Bedi, A. S., Szepesvari, C., and Wang, M. (2020). Variational policy gradient method for reinforcement learning with general utilities. In Advances in Neural Information Processing Systems.
Zhang, J., Ni, C., Szepesvari, C., and Wang, M. (2021). On the convergence and sample efficiency of variance-reduced policy gradient method. In Advances in Neural Information Processing Systems.
Zhang, T. (2006). From e-ntrrpp to KI.-entropy: Analysis of minimum information complexity density estimation. The Annals of Statistics, 34(5):2180- 2210.
12

---

A
Appendix
Contents
1 Introduction
2 Problem Formulation
3
Global Optimality in the Tabular Setting
Global Optimality Beyond the Tabular Setting
4.1
Challenges for Large-scale RLGU
4.2
Occupancy Measure Estimation
6
4.3
Global Optimality for Policy Gradient with Occupancy Measure Approximation
4.4
Novelty and Comparison to Prior Work
10
5
Conclusion
10
Appendix
13
B Extended Related Work Discussion
14
Occupancy Measures in Low-Rank MDPs
19
D Examples of Nonconcave RLGU Problems
19
Proofs for Section 4.3
20
E.1 State Sampling for MLE
20
E.2 Proof of Proposition
20
E.3 Proof of Theorem
22
E,4 Proof of Theorem 3
24
E.5 Useful technical result
25
Future Work
25
13

---

B Extended Related Work Discussion
Table 1: Comparison to closest related works about RLGU.
Reference
First-order stationarity rate'
Global optimality rate?
Beyond tabular
No state space size dependence*
Hazan al. (2019)
Ō(e 3)
x
x
Zhang al. (2020)
y
0(c-1))
x
Zhang et al. (2021)
O 3)*
O(c
x
X
Zahavy et al. (2021)
x
((c-3)
X
X
Barakat al. (2023) (sec. 4)
0 3y
3(
X
X
Barakat al. (2023) (sec. 5)
(
X
X
Mutti al. (2023)*
x (me-7)
2
X
This paper
(me
Ô hides logarithmic factors in the accuracy c, mainly due to the horizon length in the infinite horizon discounted reward setting.
refers to the number of samples (or number of iterations in the deterministic case when specified) to achieve a
given first-order stationarity e, i.c. & F(X(0r)))l] S where Oy is sampled uniformly at random from the iterates of the algorithm (01,-... 0z) until timestep T'
refers to the number of samples (or number of iterations in the deterministic case when specified) to achieve global optimality under convexity of the general utility function F w.r.t. its occupancy mcasure variable, i.c. F )) I e where F is the maximum utility achieved for an optimal policy and 6r is the last iterate of the algorithm generated after T' steps.
means that the large scale state action space is discussed and addressed, i.e., the work is not restricted to the tabular setting in which occupancy measures are estimated using simple Monte Carlo scount-basedl estimator for each
S. For more extended discussion regarding this point and comparison to prior work. please see the rest this section below.
means that the performance bounds provided for first-order stationarity or global optimality do not depend on the state space size.
These results do not hold for the last iterate like for the other results but rather for mixture of policies in Hazan al. (2019) (Theorem 4.4), an averaged occupaney measure over the iterates in Zahavy al. (2021) (Lemma 2) and an average regret guarantee lcading to a statistical (rather than computational) complexity in Mutti et al. (2023) (Theorem 5).
This is for the deterministic setting only, i.e. only reporting the number of iterations required. The rate is
further improved to be linear under strong convexity of the general utility function. Other results provided
report sample complexities.
These results make use of variance reduction in the tabular setting to obtain improved sample complexities compared to vanilla PG algorithms.
This result considers different (single trial) problem formulation compared to ours (and other works in the literature), see detailed discussion helow for comparison.
m refers to the dimension of the function approximation class parameter for occupancy measure approximation, see eq. (12) and section 4.3. It should be noted here that we suppose access to a maximizer of the log- likelihood (13) (which requires some computational complexity that we do not discuss here), this is common in sample complexity analysis. Note also that all the other results suffer from dependence the size of the state space (explicit or hidden in the statements).
Comparison to Barakat et al. (2023). The work of Barakat et al. (2023) is mostly focused on the tabular setting (secs. 1 to 4). Section 5 therein is the only relevant section to work which focuses on the large state action space setting. We list here several fundamental differences with our work and crucial improvements in terms of scalability:
(a) MSE MLE. The aforementioned work we compare to here uses mean squared error estimator (MSE) whereas we use maximum likelihood estimator (MLE), this difference turns out to be crucial for scalability. This is because mean square error estimation for occupancy measure estimation fails to scale to large state action spaces. To see this, consider an even simpler setting: suppose we have an unknown distribution p* over space and i.i.d. samples X; p" i the accuracy e is some (X|--independent quantity that only depends on the sample size and complexity of the hypothesis class. In stark contrast, mean square regression would lead to
n. MLE provides a TVV bound ||p p || S where
14

---

Ez-p ((((x) -='(2)) S By the Cauchy-Schward inequality (which is tight if the enrrr p(z) p" (x) is relatively uniform over the space), we obtain Ex- [lp(2) -D*(=)]] - ve. While this bound is close to the TV error bound above, it has an extra p (a)) which implies an extra | dependence compared to the MIL approach if p² is close to uniform. This fundamentally not scalable. Note that MLE works even for densities over continuous spaces as it is already extensively used in the statistics literature. Please see also below (in the same section) for an extended discussion regarding MLE vs MSE;
(b) Dependence on the state space size. Their results do not make the dependence on the state space explicit and do not show an (exclusive) dependence on the dimension of the state action feature map. It is required in their Theorem 5.4 that p(s) 2 Pmmin- Notice that if covers the whole state space like in the uniform distribution case, then 1/Pauin scales as the state space size. The dependence on this quantity is not made explicit in Theorem 5.4. After a close investigation of their proof, one can spot the dependence on 1/ P/min (which scales with S) in their constants (see e.g. in the constant C2 in eq. (130) p. 41 in the detailed version of the theorem, see also eq. (139) p. 42 and eq. (143) p. 43 for more details).
(c) Global convergence. In contrast to our work (see our theorem 2 and corollary 2), they only provide a first-order stationarity guarantee and they do not provide global convergence guarantees;
(d) Technical analysis. From the technical viewpoint, our occupancy measure MLE estimation procedure combined with our PG algorithm requires different theoretical analysis even for our first order stationarity guarantee. Please see appendix E below;
(e) Experiments. They do not provide any simulations testing their algorithm in section 5 for large state action spaces, Fig. therein is only for the tabular setting.
More about MSE vs MLE. It is known that MSE is equivalent to MLE when the errors in a linear regression problem follow a normal distribution. However, as first preliminary comments regarding the comparison to the approach in Barakat et al. (2023), we additionally note that: (a) they only discuss the finite state action space setting for which this connection to MLE is not relevant and (b) there is no discussion nor any assumption about normality of the errors or any extension to the continuous state action space setting, we also observe that the occupancy measure values are bounded between 0 and 1/(1 - 7) (or 0 and 1 for the normalized occupancies) which is a finite support that cannot be the support of a Gaussian distribution.
Beyond these first comments, let us now elaborate in more details on their approach and its potential regarding scalability to provide further clarifications. Our goal is to learn the (normalized) state occupancy measure d induced by a given policy Tg which is a probability distribution. In the discrete setting, this boils down estimate d= for every 8 S. Note first that this quantity can be extremely small for very large state space settings which are the focus of our work, making the probabilities hard to model especially when using a regression approach.
The approach adopted in Barakat et al. (2023) consists in seeing this estimation problem as a regression problem. In more details, since the whole distribution needs to be estimated, they propose to consider an expected mean square error over the state space (rather than solving [S] regression problems one for each X ( (s) which is not affordable given the scalability objective). Hence the mean square loss they define is an expected error over a state distribution to obtain an aggregated objective. This is less usual and specific to occupancy measure estimation problem (this aggregation is not the mean over observations). This introduces a scalability issue as we recall that we would like to estimate d (s) for every E S, so the aggregated MSE objective considered there (see eq. (11) p. 7 therein) introduces a discrepancy w.r.t. the initial objective of estimating the whole distribution.
We do not exclude that mean square eиror approach under suitable statistical model assumptions might address the occupancy measure estimation problem in a scalable way for large state action spaces for the continuous setting. However, this is not addressed in Barakat et al. (2023), their regression approach needs to be amended to address issues we mentioned above to be applicable and relevant occupancy measure estimation and are not sure that can be even achieved to tackle the problem for both discrete and continuous settings as we do.
Illustrative example for the limitations of MSE vs MLE for probability distribution estimation. We provide a simple illustrative example. Consider a simple case where the distribution (x) to be estimated is uniform (p" (z) 1/|-8| where [x| is the size of the state space). The estimated
15

---

distribution p(z) = 2/| on one half of the space and O on the other-half i. this distribution is non-uniform, assigning a higher probability to events in one part of the space and zero probability to events in the other part. The expected loss thus incurred in this scenario using regression (namely Exex p² (xx) (p(ar) - -=(())) scales as ((1/|x113 after a simple computation. This means that with large cardinality of the space, it becomes impossible to detect the difference between the two models even with infinite data when doing regression, whereas MLE does not suffer from this issue.
The primary difference between regression and MLE is that MLE results in a useful TV error bound (see Zhang (2006) and Huang et al. (2023) (Lemma 12) which we make use of in our analysis) i.e Ipp-p" p=1l2 S c, where is independent of the cardinality of the space | and depends only on the sample size and complexity of the hypothesis class. In contrast, in the case of regression (MSE) where the expected loss is optimized, we get
E Egpp' 11p-p'1 6, B RaNDy' 1p- p'1l Ve,
p²1
(16)
where the second inequality stems from an application of the Cauchy-Schwartz inequality. Note that write the left-hand side of the above last inequality as Exex (p(x) p (=())] p" (x) S c,
which would eventually lead to the total variation norm upper-bounded by ve 1.8., assuming ("()) = 1/|21 to be uniform for illustration, thus incurring a large error while estimating the distribution.
Comments about limitations of their formulation.
The expected loss is over the initial state distribution (defining the MDP). Take the extreme case where we initialize at single state (note that this is also realistic, e.g. a robot starting at given deterministic state). Then this means that the expected loss boils down to estimating the occupancy measure only at that state. However we need estimate it as accurately as possible for all states and there is reason why the occupancy measure should be supported by the same set of states as the initial distribution (which we should have freedom about). Note also that the occupancy measure itself depends on the initial distribution. In principle, the distribution used for defining the expected loss (over state action pairs) should be different from the initial state distribution defining the MDP.
Coverage and scalability problem. Now you may argue that it is enough to take an initial distribution (or just p distribution for the expected loss if one assumes it is unrelated to the initial distribution) that just needs to cover the support of the occupancy measure we want to estimate. Note that the occupancy measure unknown and we want to estimate it so we have a priori no clue about its support. One might then think about just taking the uniform distribution as an initial distribution to be sure to cover the whole state space equally. This choice problematic for several reasons: (a) First, this introduces a bias: Why would we need to estimate the occupancy measure equally well in all the states if the occupancy measure is concentrated on a specific set of states which not necessarily the entire state space? (b) Second and most importantly, if we make such a choice, have now Pmin = 1/|S| (say in the discrete state space setting) and the first order stationarity bound in Barakat et al. (2023) scales with 1/pmin this makes the result not scalable to large state spaces. You might argue that we do not need the uniform distribution but just to take a distribution covering the entire state space (not necessarily equally well), i.e. which has support equal to the entire state space. Then again, this introduces a bias as the loss minimization might focus on states which are irrelevant to the occupancy measure want to estimate. Furthermore, note that MSE might not be the best metric for comparing distributions because it focuses on pointwise differences (in our case states state-action pairs). In our setting, how the weights of the MSE loss are chosen for fitting our probability distribution of interest is important.
Shortcomings of using MSE compared to MLE. There are number of shortcomings of using MSE compared to MLE for fitting a probability distribution in general, we summarize them here:
Consistency and efficiency. MLE maximizes the likelihood function, ensuring the estimator is consistent (i.e. converges to the true parameter value as the sample size increases) and asymptotically efficient (i.e. achieves the lowest possible variance among unbiased estimators for large samples). In contrast, as MSE minimizes mean squared errors, it does not guarantee properties like consistency or efficiency unless under specific assumptions on the data such as normality of the emrrs in which case both coincide. Note that the approach in Barakat et al. (2023) does not fit a Gaussian distribution to the normalized occupancy measure. We use favorable statistical properties of MLE (see Proposition 1).
16

---

Sensitivity to scaling. MLE operates on probabilities and likelihoods, these are normalized and scale-invariant. This makes MLE suitable for probability distribution fitting in general. MSE is rather better used for pointwise estimation in statistics (which is also indirectly used for distribution estimation via estimating parameters such as Gaussian means), MSE depends on the scale of the observations which might make it less robust in some settings.
Robustness to outliess. As MLE models probabilities directly, it might be more robust to outliers depending on the distribution. MSE can be more sensitive to outliers and extreme values as it relies on squared errors which amplify such outliers. In our setting. this is also relevant as we are interested in estimating occupancy measures on large state spaces, this induces small probability values (even extremely small for some of them) and squaring differences makes it worse, see discussion in appendix B.
Satisfying distribution constraints. MLE naturally adapts the distribution's 's shape and constraints to satisfy them. In contrast, MSE can lead to estimates that violate distribution constraints such as probability normalization or predicting negative variance for a normal distribution. Therefore, post-processing might be required to ensure these are satisfied.
Comparison to Theorem 5, section 3 in Mutti et al. (2023). We enumerate the differences between our results and settings in the following:
1. Problem formulation. As mentioned in the short related work section in the main part, Mutti et al. (2023) consider a finite trial version of the convex RL problem which has its own merits (for settings where the objective itself only cares about the performance on the finite number of realizations the agent can have access instead of expected objective which can be interpreted as an infinite realization access setting, see discussion therein) but this formulation is different from ours. Both coincide when the number of trials they consider goes to infinity. Although the problem formulations are different, let us comment further on some additional differences our results.
2. Assumptions. They assume linear realizability of the utility function F with known feature vectors (Assumption 4, p. 17 therein). Our setting differs for two reasons: (1) We do not approximate the utility function itself but rather the occupancy measure and (2) train a neural network to learn an occupancy measure approximation by maximizing a ligeliiel loss. In our case, our analog (similar but different in formulation and nature) assumption would be our function approximation class regularity assumption (Assump- tion 2). We do not suppose access to feature vectors which are given. Nevertheless. we do suppose that we can solve the log- log-likelihood optimization problem to optimality (which is approximated in practice and widely used among practitioners).
3. Algorithm. The algorithm they use is model-based, they repeatedly solve regression problem to approximate the utility function F using samples and use optimism for ensuring sufficient exploration. Our policy gradient algorithm is model-free and we rather rely on MLE for approximating occupancy measures rather than regression.
4. Analysis. Under concavity of the utility function, we provide a last iterate global optimality guarantee whereas Mutti et al. (2023) establish an average regret guarantee which is different in nature. Their proof relies on a reduction to an online learning per-epeeee framework. Our proof ideas are different: We combine gradient optimization analysis exploiting hidden convexity with a statistical complexity analysis for occupancy measure estimation. Overall, our results combine optimization and statistical guarantees whereas their results focus purely on the statistical complexity (as their problem is computationally hard).
Comparison to Mutti et al. (2023). Let us list first a few advantages/diifferrnees w.r.t. the aforemen- tioned work:
Advantages of our analysis/approach.
No planning oracle access. We do not suppose access to planning oracle able to solve any convex MDP efficiently. This precisely the point of our optimization guarantees for our PG algorithm which updates policies incrementally. Nevertheless, we point out here that Mutti et al. (2023) address a slightly different (finite-trial) convex RL problem which is computationally intractable. Our problem coincides with their infinite trial variant of the problem.
17

---

No access required to feature vectors for function approximation. We learn occupancy measure approximations rather than supposing access to a set of features approximate utilities (i.e. F()) in our notations), i.e. we do not suppose access to set of basis feature vectors for our approximation.
Model-free and no dependence on state action space size. We do not estimate the transition kernel, our algorithm is model-free as we only require access to sampled trajectories. In particular, we do not require go through the entire state action space to estimate each entry of the transition kernel. Therefore, our performance bounds do not have dependence on the state action space sizes as their regret bound.
Policy parameterization. We consider policy parameterization instead of tabular policies which results in practical algorithm. We do require strong assumption though (Assumption 5) to obtain our global optimality result.
Advantages of our model-free PG algorithm. We inherit the usual advantages of model-free vs model-based algorithms: (a) Model-free are often simpler to implement because they do not require learning using model of the environment. Our algorithm directly focuses on learning a policy (even if we do also approximate the occupancy measures but not the transitions themselves like in model-based approaches); (b) Robustness: Inaccuracies in environment modeling propagate to policy optimization and can significantly degrade performance. Model- -ree methods directly learn policies from interaction with the environment; (c) PG methods particularly suitable for complex and nigh-dimensional environments settings. Of course, model-based methods may also have advantages over model-free ones.
bout hardness of occupancy measure estimation. We comment here on one of the challenges discussed in the main part as for estimating the occupancy measure. An occupancy measure induced by a policy π satisfies the identity (= a) = (o(ss a) + +> P(s|s', a') ) (als')A (s', a') where Po is the initial state action distribution. Notice that the sum is not over the next action s in transition kernel P but rather the "backward' state actions (s',a'). In contrast, an action value function standard RL rather satisfies 'forward' Bellman equation. In contrast to the standard Bellman equation which can be written using an expectation and leads to sampled version of the Bellman fixed point equation, the equation satisfied by the occupancy measure cannot be written under expectation form and does not naturally lead to any stochastic algorithm. This issue is recognized in the literature in Huang et al. (2023) (see also Hallak and Mannor (2017)).
More about assumptions. Besides the points above, we provide few comments regarding assump- tions:
1. Some of our assumptions are quite similar. For instance, Mutti al. (2023) assume linear realizability of the utility function with known feature vectors (Assumption 4, 17 therein) and then assume access to regression problem solver with cross-entropy loss to approximate the utility function. We rather have a similar but different function approximation class regularity assumption (Assumption 1) and we suppose access to an optimizer which solves our log-likelihood loss maximization problem to approximate occupancy measures (see Eq. (8)). We both assume concavity of the utility function.
2.
We require smoothness assumptions on the utility function (Assumption 3) whereas Mutti et al. (2023) only require Lipschitzness of the same function (Assumption I therein). This is because smoothness is important for deriving optimization guarantees as we make use of gradient information whereas Lipschitzness is enough for developing their statistical analysis.
3. Mutti et al. (2023) assume access to an optimal planner (as mentioned above). we do not need such a requirement as we provide optimization guarantees using our PG algorithm.
4. We need policy parametrization assumptions as previously discussed, Mutti et al. (2023) do not consider policy parametrization.
Recently, Prajapat et al. (2024) and De Santi et al. (2024) proposed to go beyond linear and convex rewards by considering rewards which are defined globally over trajectories instead of locally over states.
For more recent work concerning the analysis of policy gradient methods in classical linear RL, we refer the reader to Liu et al. (2024, 2025).
18

---

C Occupancy Measures in Low-Rank MDPs
In this section, we show that occupancy measures have a linear structure in the so-called density features in low-rank MDPs. We provide proof for completeness. Similar results were established in Lemma 16, 17 in Huang et al. (2023) for the finite-horizon setting. Throughout this section, we use the same notations as in the main part of this paper.
Definition C.1 (Low-rank MDPs). An MDP is said to be low-rank with dimension Z if there exists feature map S A + RR and there exist d unknown measures (11,,.. -Pd) over the state space such that for every states (s, E S and every action a E A it holds that
P(s'[s,a) a)
(17)
with b0 & without loss of generality.
Before stating the result, recall that for any policy 11, state-occupancy measure is defined for every state s as follows:
d" (=) = t=
(18)
Lemma 1. Consider low-rank infinite horizon discounted MDP. Then, for any policy II, there exists vector wi E Rd such that the state-action occupancy measure d= induced by the policy x satisfies for any state 8 S.
de (s) p(s) (ws,
(19)
where we use the notation u(s) (s), ".)s)))),a())))²
Proof. Let π E II. It follows from the definition of the state-occupancy measure d" induced by the policy ı that satisfies the following (backward) Bellman flow equation for every state S:
dh (x) = p(5) +7
Σ
(20)
S'EEE'
Using the definition of a low-rank MDP and (17) in particular, we obtain:
dt (s) po(s) +y
Σ
(ø(s', a'), ((9)
(21)
''E,
= po(s) +
Σ
ø(s' (((d)')((d()))))())) u(s)
(22)
''Sa''A
=sl(s) + (Wi, ((s));
(23)
where we define W/ := E.' 06s' (o65.a/)(((aa) (a
D Examples of Nonconcave RLGU Problems
Nonconvexity is ubiquitous in real-world applications and we provide below few examples where it naturally arises beyond the standard convex RL examples in the literature. First of all, we would like mention risk-sensitive RL with non-convex risk measures inspired by Cumulative Prospect Theory (CPT) (with S-shaped utility curves). Nonconvex criteria are important for modeling human decisions. See e.g. (Lin and Marcus, 2013; Lin al., 2018) for discussion about their relevance and importance. See also Remark and figure p. in Prashanth et al. (2016).
Applications include for instance:
Robotics control: control tasks, is common to deal with nonconvex objectives such as minimizing energy consumption while achieving task maximizing the success rate of manipulation task.
Portfolio Management:
Utility functions finance may non-convex due risk measures transaction costs for example.
19

---

Traffic Control: RL can be used to optimize traffic flow and minimize congestion. The utility function may involve non-convex terms such as travel time, queue lengths, and safety constraints.
Supply Chain Management: RL can be applied inventory control, pricing, and logistics optimization. The utility function may include non-convex components such as demand forecasting, supply chain disruptions, and dynamic pricing.
We leave the experimental investigation of those applications for future work. hope our work will foster more research in this direction.
E
Proofs for Section 4.3
E.1 State Sampling for MLE
In this section, briefly discuss how sample states following the (normalized) state occupancy d for a given policy Ty In particular, these states are used for the MLE procedure described in section 4.2. The idea consists in sampling states following the transition kernel P and the policy me for random horizon following geometric distribution of parameter ? where 7 is the discount factor, starting from state drawn from the initial distribution. The detailed sampling procedure described in Algorithm 2, borrowed and adapted from Yuan et al. (2023) (Algorithm 3 22) which provides clear presentation of the idea as well as a simple supporting proof (see Lemma p. 23 therein). This procedure has been commonly used in the literature. see e.g. Algorithm p. 30 and Algorithm p. 34 in Agarwal et (2021).
Algorithm 2 Sampler for s ~ d
1: Input: Initial state distribution p. policy Te, discount factor y E [0. 1)
2: Initialize $o p. ag ~ TT(-1s)), time step h, O, variable X
3: while = do
4: With probability 7:
5: Sample S4+1 ~ P(. 8h, ap)
6: Sample 01+11 T-(-18441)
7: h - h++1
8: EndWith
9: Otherwise with probability 1 -
= (Accept 8n))
11: EndOtherwise
end while
13: Return: 8h.
E.2 Proof of Proposition
Proposition and its proof are largely based on the work of Huang et al. (2023): We follow and reproduce their proof strategy here. Since the latter paper deals with more complex setting that does not exactly fit our current focus, we provide proof for clarity and completeness.
We start by defining the concept of l optimistic cover. This cover will be immediately useful to quantify the complexity of our (possibly infinite) approximating function class I' defined in (12).
In the following, we denote by (X + IR} the set of functions defined on X' with values in IR.
Definition E.1 (Definition 3 in Huang et al. (2023)). For given function class A C A(X'), the function class A (X + is said to be an I optimistic cover of with scale & > 0f:
AAAA, RÄEA S.I. ||a - A1l1 S K, and Mxx) S Mx)
(24)
Remark 5. Notice that A does not need to be set containing only probability distributions if A is set of probability distributions, namely the set of (normalized) occupancy measures as we will be considering in the rest of this section.
20

---

We now provide general statistical guarantee for the maximum likelihood estimator (MLE) defined in (13) supposing we have access an optimistic cover of the space of distributions used for computing the MLE estimator.
Proposition 2 (Lemma 12 in Huang et al. (2023)). Let = Ji be dataset of state-action pairs drawn i..d from some fixed probability distribution X E A(X). Let _ ( be a function class such that:
(i) (realizabilitt) E.,
(ū) (probability distribution class) YA E E,,
(ii) (covering) A has a finite l1-optimistic cover m {X - Rzo) with scale k (see Definition E.I).
Then, for any > O, we have with probability at least 6,
[ 12 log
j - x
+ 61e
(25)
where X is the MLE estimator defined in (13) computed using the dataset and [A] is the cardinality of the finite cover A.
In view of using Proposition 2, the next lemma constructs an l optimistic cover for the function approximation class A used to computed the MLE. For the reader's convenience, we recall that
= (p- w E Q C TR E A(X))
(26)
Let Assumption 2 hold. Then there exists a finite I --optimistic cover A C {X' Rzo1 of the function class A with scale 0 and size most 2 B B. 7m where is the dimension of the parameter space Q C R
Lemma 2.
Proof. The proof follows the same lines as the proof of Lemma 22 p. 41 in Huang et al. (2023). Let
E A, i.e., À = p. for some w E Ω Let K¹ > O. Define the set B(w,, == x' L [0, k'm which is a cubic x' -nighboorhoo of the point w E Ω. Now define the function fw for every a E X as follows:
[ = max Pa (x)
(27)
@EB(w,x))
By construction, we immediately have f=(2) 2 (x) 2 0. Note that fw might not be a probability
distribution though. Then using Assumption 2 we also have
Ilf - Pw 111 /
(f) (x)
= max
=
Pa( Pe (x))dd GEB(W,x")
(po(*) - (=))ddd S @EB(U,N)
max
max wEB(unk))
[Lxx] || - w| S BIK'.
(28)
To conclude, we observe that there are most 2 B 1 unique functions in the -oppiiiisii cover À of A which is of scale By Setting x'' ___ Br. concludes the proof.
End of Proof of Proposition 1. We conclude the proof by using Proposition together with Lemma above, choosing a scale 1 where is the number of samples used for computing the MLE and plugging A < B n m_ We obtain after simple upper-boundis inequalities.
12 m log
[ Bw, B. Byn]
Id
d 1 S 61
(29)
7
21

---

E.3 Proof of Theorem 2
The proof follows similar lines to the proof of Theorem 5.4 in Barakat et al. (2023). However, our occupancy measure estimation procedure is different in the present case. We provide full proof here for completeness.
N We introduce the shorthand notation N Li=t g(T 0c, rt) for this proof. Using the smooth- ness of the objective function 0 + (() (see Lemma in Appendix E.5) and the update rule of the sequence (Dz), we have
Σ
Lg
F(((0+11) 2 (V 0,+1 Ot)
10
Oull
Loce
1|
=
2
1 Lock
G.) +
11ăe11
2
Loc
2 F(X(0)) VoF(A((.)) 3el1
11
12 +
1
2
2
= F(A(O)) A 2 VoF(A(0.)) 3e12 + a
(1
11Eel
2
2 F(((O)) 7 (VFO()(0)) 9.
@+
=(X(0)) (oF(((())) 3el2
1 2
=1
F(A(O)) + a 16 VgF(A(0)))
V F(A(O))
a 3el1
1
(30)
8
where (i) follows from the condition a - 1/2La and (ii) from a V+F(A(0))) - | - (V))()())) 3ell2.
We now control the last error term in the above inequality in expectation. Recalling that voF(>(0)) for any E RRd, we have
V
3.1 EII (T) - = 2E V 1 (T)) VOV (V / (v) - -9.
(31)
Now, upper bound each one of the terms above separately. For convenience, introduce the notations r V (A.()) and f. V}.().).
Upper bound of the term theorem (see (4)) yields
- "T in (31). Using the policy gradient
]]
(r E
|Vx VVF(())))))) - VXF(Ae)lanaa
V log ne (an, 8n)
(32)
22

---

Notice that the above expectation is only taken w.r.t. the state action pairs in the random trajectory of length H. Taking the norm, we obtain
VoV=o(r)
VoV* (f:)ll
E
- V.F(A))
Vo log n (n: sh.)
2l' + 10)1(++))''1 - -VB)))--FFFAAAA FXF(Ae)
HH-1
I E
22 + +1) (())))) - Sella
(d)
2 LA
(1 7)² (I)(0)) della.
(33)
where (a) follows from using the triangle inequality together with the definition of the sup norm, (b) uses Lemma 3 (i) in Appendix E.5, (c) is consequence of Assumption together with the fact that ||0]|so I ||>||2 for any x E Rd and (d) stems from the upper bound Er=o + 1)n" s
Dr + 1)7" [1ン7 Hence we have shown that
4 (1-~)² (O))
B V
Vo
Ar 12)
(34)
Upper bound of the term
E[| Vo V (f:)
Øel in (31). Recalling the definition of Gt. have
V (ft) 9-1l
V (f.)) g((t() 0s Px))
(llg(TT ft) (oV=o(f:)
(lll((Te 0,, 1
N
473
(35)
(1 ~
where (a) follows from the fact that the expectation of ((T,") (1) 0r. f.) w.r.t. the random trajectory T." conditioned O and ê. is precisely given by Vo (fx) by the policy gradient theorem (see (4)), notice also that all the N trajectories are drawn i.i.d. As for (b), use the fact that the variance of
random variable is upper bounded by its second moment. Finally (c) stems from using the expression
of g(T, (i) 0c. ft) in (11) together with Assumptions 3, 4 and Lemma 3 (i) in Appendix E.5. The proof of this last point follows similar lines to (33).
Combining both the previous upper bounds we have now established above, we obtain
Ō Ō2 E(IA)()) - A
E (oF((O) - 3: <
(36)
N
where č
1 (1-7)a and Č₂ = st 23 (1-7)4-
End of Proof of Theorem 2. We are now ready to conclude the proof of our result. Going back to (30), rearranging the terms and taking expectation, we obtain
16
ELF(((0--)) F(X(O.)) + 10 g..1
(37)
Plugging the bound (36) into the previous inequality, obtain
10č,
||| ((F((()))) E[F(A((
-F(()))))))((
+ 10Ō, E[)) -111),
(38)
a
N
23

---

Summing the previous inequality for t = to T, telescoping the right hand side and using the upper bound F* on the objective function leads
T
16(F E1IV&F((00)1111
E(F(((
10C1
10C² T
T ^r 11]] (39)
af
N
1=1
Setting C =
10C1 and C2 == C2 gives the desired result.
E.4 Proof of Theorem 3
The proof of this result borrows some ideas from Zhang et al. (2021) and Barakat et al. (2023).
However the algorithm we are analyzing is different and the proof deviates from the aforementioned results accordingly.
Remark 6. different technical analysis can be found in Fatkhullin et al. (2023) by considering particular case of their theorem 5 dealing with stochastic optimization under hidden convexity. How- ever, their general setting is not focused on our specific RLGU setting using policy parumetrization and specifying the assumptions needed as consequence. More importantly, we are considering context in which unknown occupancy measures are upproximated via function approximation using relevant collected state samples and our theorem accounts for the induced error. In contrast, Fatkhullin et al. (2023) assume access to an unbiased estimate of the gradient of the utility function which is not readily available in our RLGU setting since occupancy measures estimated via function approximation with a supporting sample complexity guarantee. Besides these differences, conduct different analysis which is rather inspired by the proofs in Zhang al. (2021) and Barakat et al. (2023) as previously mentioned.
unknown and
It follows from smoothness of the objective function 0 + F(X(O)) (see (30)) that for every iteration t,
F(A(O++1)) 2 F(X(O.) +
16 V+F(((0)))) 5 (oF((())) Gell 2 +
8 1
(40)
For any 17 17. the concavity reparametrizzttoon assumption implies that (1- (1-1)) (7,) + m)7(0)) Vx(e,) and therefore we have
Og = (A1x,,))~ - -))) + sT>(0") E Uo,
(41)
It also follows from the smoothness of the objective function 0 + F(X(0)) that
Ta
F(X(O.) Z F(X(O,)) (VoF(X(6.)), 0, - -0,) 2 110, 0al1
(42)
Combining (40) and (42), we obtain
F F(X(0++1) F(A(O,)) - (VoF()(0)), B, 02) La 10,, 1111
+
a VoF(X(B))
voF((()) - 9.112 a
11
(43)
16
8
Now, pick a S 18. using Young's inequality gives
1 _10, - -0,11.
(VoP()()))). O,, - 0.) S aa aol(V
(44)
aa
Plugging this inequality into (43) yields
F F(X(O.+1)) F(A(O,)) + a
axx) aax)l
a | 12
16
Lo
5 a (oF((()) - 3ell.. (45)
+
10,, 0.1 1|
2
ac
Therefore, since a S 16 we obtain
L-
1
5 [a -2.
1()(0.+1)) > F()(O.))
110, 0.11
(46)
2
ax
Using the definition of 9., and the concavity of F (Assumption 1), now control each one of the terms F(X(0,)) and ||o,, 0.112.
24

---

(i) By concavity of F (Assumption 1) and using the definition of 8yp we have
F()(O,)) = F((1 (),,) + m)(0)) 2 - ())))))(((()) + +)(((()))
(47)
(ii) Using the uniform Lipschitzness of the inverse mapping (Alews) ) (see Assumption 5), we have
100, 0.11 = =1(AAke,, ()) + ,;(((0)) - (Aluo,) +
- (1(0,) X(0")12
n2
(48)
(1 7)
Injecting (47) and (48) into (46) yields
Lo
41
F(M(0++1) 2 (1-m)))(((()))+)=((X)))
1 - VoF(X()))) -.ll
2
aa
(1
7)²
(49)
Rearranging the above inequality, adding F to both sides, taking expectation and using the nota- tion 5, == [F - F(X(O.))] we obtain
Lg
1
413
? + 5 o. aB(()))(((0.)) - 1.1
5,+1 S (1 - 1);; +
+
(50)
2
(1
7)2
Recall then from (36) that
0 N + Ö2 (()) - -112).
- 3. ve((
(51)
Since ([)))(0)) 111 S EMLE uniformly over the iterations, we get by combining (50) and (51) that
dc+1 $ (1- - n) +
Lo 2
1
472
"
+ 8
G
+ EZEMLE)
(52)
ac
(1 -
7)
N
Finally, unrolling this recursion gives
8T S (1 ( -7 +
Lo
1
41
17 +
a
ČZEMLE
(53)
00
(1
7)
8 1)
N
E.5 Useful technical result
Lemma (Lemma 5.3, Zhang et (2021)). Let Assumptions 3 and 4 hold. Then, the following statements hold:
(i) 40 Rd V(s,a) E 8 A, |/V log (a(as)) < 24p 11 lo 2(L + +()), and (oF() S 21//2
(1-
44x, shal2 (1-7)4 + (1-
(ii) The objective function + F(X*)) is Lm-shooth with Lg (Lu
21x [1
Future Work
We comment here on few future directions of improvement:
In our PG algorithm, the estimations of the state occupancy measure need to be relearned for each policy parameter 0,, We believe a regularized policy optimization approach could lead to a more efficient procedure. Indeed, by enforcing policy parameters to be not too far from each other, would allow reuse estimations of the occupancy measure from previous iterations to obtain better and more reliable estimations.
25

---

The oceupancy measure can be very complicated and hence difficult to estimate, espe- cially in complex -ihh-imenniinal state settings. The use of massively overparametrized neural networks for occupancy measure approximation might therefore be of much help in such complex settings as practice shows that overparametrized neural networks do perform well in general. Establishing theoretical guarantees in this regime is certainly an interesting question to extend our work.
It would definitely be interesting conduct experiments very large scale environments such as DMLab or Atari. Our work makes progress towards solving larger scale real-world RLGU problems and offers promising approach supported by theoretical guarantees.
26

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). ). In general, answering binary way, we
"[No] or "[NA] is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can found.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We provide clear statements in line with the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of some of our assumptions.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
27

---

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-specing well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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 low or images are taken in low lighting. Or speech-to-tes system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairess..
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best 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.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification:
We provide complete proofs 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 or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to 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 the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, 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.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
28

---

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 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 to 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either 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 reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g.. registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
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/
wwssssiinniiyiiii for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //n cesapps.cc/pubic//uuu /tte:/ggdddeeeooemmmmmiiiiiaaa /CodeSubmiieeeeeeeeee
onPolicy) 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, to 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?
29

---

Answer: [NA]
Justification:
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, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error 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 are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma eгrоr 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).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or 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 exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount 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 the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
30

---

Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips. http::///aarrpp.ccccoaaa////ttta
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws 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:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended 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.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as 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 (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
31

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
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 (e.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. cowccoo////oooo/o com/datasete has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsoureing 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 in the main paper.
32

---

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


Reviews:
[{"review_id": "CmE88a32aF", "reviewer": "Reviewer_px47", "summary": "Reinforcement learning with general utilities is an important topic in the RL community. This paper establishes global optimality guarantees of PG methods for RLGU in which the objective is a general concave utility function of the state-action occupancy measure. In the tabular setting, this paper provides global optimality results using a new proof technique building on recent theoretical developments on the convergence of PG methods for standard RL using gradient domination.", "questions": "Is the assumption of bounded gradients truly necessary, or could the results be generalized under gradient moment assumptions (e.g., bounded variance or sub-Gaussian tails?\n\nGiven that global optimality is approached as the inner-loop step size shrinks, how does this affect the sample efficiency and convergence speed in practice? Does the theory support any practical heuristics for tuning inner step sizes?", "limitations": "See weakness.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\nThis paper establishes tight bounds on the optimality gap using clear mathematical derivations and well-stated assumptions.\n\nWhile prior works have analyzed convergence or approximation properties of RLGU in practice or for specific architectures, this work is among the first to offer a general analysis of global optimality, which is an important supplement in the RLGU community.\n\nWeaknesses:\n\nThe analysis considers a single-step gradient update in the inner loop. While the authors briefly mention multi-step generalization, no formal analysis is provided. This limits applicability to practical implementations using multiple inner-loop steps.\n\nExperiments are very limited. While they serve to confirm the theory, they offer little practical insight into real-world performance or limitations.", "was_revised": true, "final_justification": "I have no further questions.", "rebuttal": "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’. \n\n\n> **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.\n\n**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.\n\n> **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)?\n\n**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. \n\n\n> **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?\n\n**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.\n\nWe 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."}, {"review_id": "KOgSNzK18f", "reviewer": "Reviewer_sc7M", "summary": "This paper studies reinforcement learning with general utilities (RLGU), where in a discounted Markov decision process (MDP), the objective is to maximize a utility function $F$ defined on the occupancy $\\lambda^\\pi$. Specifically, $\\lambda^\\pi (s, a)$ is the normalized discounted occupancy of $(s, a)$ under policy $\\pi$, and the utility is $F(\\lambda^\\pi)$. This work first establishes the gradient domination theorem for tabular MDPs and $F$ which is concave in $\\lambda$ (not $\\theta$, the parameter of $\\pi$). This theorem can further imply $\\epsilon^{-1}$ convergence for policy gradient (PG) methods. Then, when the occupancy falls inside a $m$-dimensional parametric class, the authors propose a two-stage PG algorithm, which iteratively does MLE for occupancy and policy update using the estimation. Under mild assumptions, the authors establish a $m \\epsilon^{-2}$ convergence to stationary points for general utility, and a $m \\epsilon^{-4}$ sub-optimality gap for concave utility.", "questions": "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?\n\n2. Can you provide real-world examples aside from standard RL that RLGU plays an important role? Is there any existing environments or benchmarks for this problem?", "limitations": "One limitation is the applicability of RLGU, which is from the problem side. This type of problem seems to mainly attract theoretical interests and lack practical significance, as I'm not aware of existing environments or benchmarks modeling RLGU. The other limitation is the assumption of known utility, which is from the algorithm side. There lacks a discussion on the necessity of this assumption.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "### Strengths\n- **Theories:** Establishes gradient domination properties for RLGU objectives, connecting them to recent advances in standard RL theory. First work to provide global optimality guarantees for RLGU beyond tabular settings. Results cover both concave and general utilities. Theorem 3 is a last-iterate global convergence guarantee which previous works fail to provide.\n- **Algorithm design:** PG-OMA is easily scalable to function classes beyond tabular.\n\n\n### Weaknesses\n- **Assumption on known utility:** This paper assumes that $F$ is known to calculate $\\nabla_\\lambda F(\\lambda)$, 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.\n- **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.", "was_revised": true, "final_justification": "The rebuttal addresses my concerns of the applications of general utility RL. However, the difficulty of unknown $F$ is still evasive, as the authors state that this is common in all previous works. Given this, I'll maintain my rating of 4.", "rebuttal": "We thank the reviewer for their time in evaluating our work and for their useful feedback. \n\n>**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.\n\n\n**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.\n\n> **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.\n\n**Response to Weakness 2:**\n\nWe 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.\n\n> **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?\n\n**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. \n\n> **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?\n\n**Response to Question 2:** \n\n- 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: \n\n    - (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; \n   - (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, \n   - (3) *Experiment design* (e.g. Mutny et al., AISTATS 2023) in science where an agent chooses experiments to maximize expected informativeness, \n   - (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. \n  - (5) *Pluralistic alignment* (e.g. of LLMs), see e.g. Chakraborty et al. ICML 2024, 'MaxMin-RLHF: Alignment with Diverse Human Preferences'.\n\n- 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.\n\nWe 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."}, {"review_id": "PnaiAJ27Nd", "reviewer": "Reviewer_hs2m", "summary": "This paper addresses reinforcement learning with general utilities, in which the objective is a (potentially non-linear) function of the state-action occupancy measure. The paper provides a global optimality result for policy gradient when the utility is concave and the MDP is tabular through gradient domination technique. Next, the paper addresses the same problem beyond the tabular setting, where the state-action occupancy measure is estimated via maximum likelihood within an approximating class. In this more challenging settings, first-order and global optimality guarantees, together with corresponding sample complexities, are derived under some more restrictive assumptions.", "questions": "**Tabular setting.**\n\n(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. have established that RLGU can be cast as a sequence of (linear) RL problems, for which gradient domination leads to global optimality of PG as know from previous works. However, the question here is how much the distribution shift constant is bigger here w.r.t. standard gradient domination. From what I know, the constant is usually thought with $\\mu$ as the state distribution of the initial policy parametrization, which needs to cover an optimal policy state distribution. Here, we need a distribution $\\mu$ that covers all of the policies that are optimal for some pseudoreward (?) In general, this looks like the set of all the deterministic policies, which would make the constant very large and the result somewhat vacuous. Am I missing something? I would recommend the authors to make an explicit comparison between the gradient domination analysis in RL (e.g., Lemma 4.1 in Agarwal et al., 2021) and RLGU in the manuscript.\n\n**Large-scale setting.**\n\n(2) Assumptions. Understanding the assumptions here is crucial to assess the generality of the results and when do the guarantees hold. However, the discussion of the assumptions is somewhat lacking in my opinion. Realizability (Assumption 2) is ubiquitous in RL theory for value function estimation. I am wondering how stronger it can be for occupancy estimation. Assumption 4 also could be explained beyond saying \"This assumption captures most of the problems of interest in RLGU and beyond\". Why is that the case? Assumption 5 is quite hard to process, I don't think I understood the implications of any of these. Finally, the $\\epsilon_{MLE}$ assumption introduced in the statement of Theorem 3 warrant some discussion. Isn't this implying that the algorithm doesn't really converge ($\\epsilon_{MLE}$ is just a constant error that is not scaled by N)? Moreover, why $\\epsilon_{MLE}$ doesn't appear in Corollary 2? Shall not that be something like \"for any precision $\\epsilon > \\epsilon_{MLE}$...\"?\n\n(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.\n\n(4) I am not very familiar with the analysis of Barakat et al. 2023. The paper here says that this previous work doesn't provide global optimality guarantees but just first-order. However, I am wondering whether their analysis would translate to global optimality when the same assumptions of this paper are considered. Aside from MSE and MLE step, what makes Barakat et al. analysis break for global optimality?\n\n**Other minor questions/comments.**\n\n(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?\n\n(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.\n\n(7) The discussion of the related work looks mostly complete. Perhaps \"Regret minimization for reinforcement learning with vectorial feedback and complex objectives\" Cheung 2019 and the pair \"Submodular reinforcement learning\" Prajapat et al. 2023, \"Global reinforcement learning: Beyond linear and convex rewards via submodular semi-gradient methods\" De Santi et al. 2024 could also be mentioned.", "limitations": "On the limitations, see questions above. Potential negative societal impact are not applicable at this level of abstraction.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths.**\n- RLGU is a framework that unifies a large body of settings of interest for RL, so any advancement on its understanding is potentially valuable;\n- The global optimality results for PG in tabular and larger scale RLGU settings are novel to the best of my knowledge;\n- The paper makes good use of recent advancements in the analysis policy gradient for RL to establish more general results beyond linear utilities;\n- The paper is well-written, with a mostly solid presentation.\n\n**Weaknesses.**\n- For both the tabular and larger scale settings, the significance of the results could be discussed in more details. It is not fully clear to which extent the reported results are a direct implication of previous results in RLGU and analysis of PG. While there might be important value in stating those results explicitly, still showing that the combination of what is previously known is non-trivial would be desirable;\n- The tabular setting could enjoy a more direct comparison with the analysis of the linear utility case;\n- The results with occupancy measure approximation is built upon a long string of assumptions. Some are more reasonable than others, but it would help to give more intuition/explanations on when they hold, why they are important, and how they might be overcome;\n- Some slippery details are briefly mentioned in the text and then buried in the appendix, most of all the need for i.i.d. state samples for MLE of the occupancy measure.\n\n**Evaluation.**\nOverall this looks like a solid and technically sound paper on a very interesting topic. While the readers who are familiar with previous results in RLGU may find some of the results not particularly surprising, seeing them stated explicitly and neatly in the theorem statements is great. However, as it is often the case in these kind of analysis, I think the assumptions are the core of the results, and I would like to see more discussion on them before judging the extent to which the paper is advancing the literature here. I am currently providing a borderline score, but I am open to increase if the authors can reassure me on the generality and strength of their results.", "was_revised": true, "final_justification": "I was missing some information on the novelty of the analysis and the needed assumptions, which have been covered by the authors' response. I am now more convinced on the value of the paper, thus increasing my score from borderline accept (4) to accept (5)", "rebuttal": "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.\n\n>**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. [...]\n\n**Response to Question 1 (also to weaknesses 1-2):** \n\nTo 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.\n\n- 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).\n- 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. \n- 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.\n- 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.\n\n> **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 ...\"?\n\n**Response to Question 2 (also to weakness 3):** \n\nWe 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.\n\n- **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. \n\n- **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. \n\n- **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.\n\n- **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. \n\n\n> **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.\n\n**Response to Question 3 (also to weakness 4):**\n\n 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. \n\n> **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?\n\n**Response to Question 4 (also to weakness 1):**\n\nApart from the use of smoothness, our global optimality analysis is completely different. \n- The first order stationarity analysis is based on exploiting smoothness of the objective alone as it is standard in smooth optimization. \n-  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. \n- 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. \n- 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). \n\n> **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?\n\n**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.\n\n> **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.\n\n**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. \n\n> **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.\n\n**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.\n\nWe 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."}, {"review_id": "YHOMiiZvi2", "reviewer": "Reviewer_Fepe", "summary": "The paper establishes the global convergence of policy gradient in RL with concave utility functions. Further it provides sample complexity for the same, approximating the occupany measures.", "questions": "**Q1). Global convergence requires the mis-matchcoefficient to be fininte  which is typically satisfied by taking assuming initial state distribution $\\min_{s}\\mu(s)>0$ (Xiao 2022). Otherwise, it has been shown that policy gradient can (in linear RL) converges to some local soution [1]. The paper claims their result to be applicable to the continuous/infinite state space, it is not clear how this mismatch coefficient can be finite in these cases.**  \n\n\n[1] @misc{koren2025policygradienttreesearch,\n      title={Policy Gradient with Tree Search: Avoiding Local Optimas through Lookahead}, \n      author={Uri Koren and Navdeep Kumar and Uri Gadot and Giorgia Ramponi and Kfir Yehuda Levy and Shie Mannor},\n      year={2025},\n      eprint={2506.07054},\n      archivePrefix={arXiv},\n      primaryClass={cs.LG},\n      url={https://arxiv.org/abs/2506.07054},}\n\n**Q2). Proposition 1 of the paper establishes sample complexity of $O(\\epsilon^{-2})$ for estimating occupation measure. I wonder, Lemma 1 of Kumar et al. 2022 that shows $\\gamma$-contracting operator for computing occupation measure (bootstraping just like Bellman operator), if this operator can help increase the sample complexity of the occupation measure?**\n\n**Q3 Could this work be extended to average reward case as studied in [4]? What could be possible challenges?**\n\n[4] @inproceedings{\nkumar2025global,\ntitle={Global Convergence of Policy Gradient in Average Reward {MDP}s},\nauthor={Navdeep Kumar and Yashaswini Murthy and Itai Shufaro and Kfir Yehuda Levy and R. Srikant and Shie Mannor},\nbooktitle={The Thirteenth International Conference on Learning Representations},\nyear={2025},\nurl={https://openreview.net/forum?id=2PRpcmJecX}\n}\n\n**Q4). (Bonus question) What do authors think about the sample complexity of single-time actor critic RELU as studied in [2,3]?**\n\n[2]@misc{chen2024finitetimeanalysissingletimescaleactorcritic,\n      title={Finite-time analysis of single-timescale actor-critic}, \n      author={Xuyang Chen and Lin Zhao},\n      year={2024},\n      eprint={2210.09921},\n      archivePrefix={arXiv},\n      primaryClass={cs.LG},\n      url={https://arxiv.org/abs/2210.09921}, \n}\n\n[3]@misc{kumar2025convergencesingletimescaleactorcritic,\n      title={On the Convergence of Single-Timescale Actor-Critic}, \n      author={Navdeep Kumar and Priyank Agrawal and Giorgia Ramponi and Kfir Yehuda Levy and Shie Mannor},\n      year={2025},\n      eprint={2410.08868},\n      archivePrefix={arXiv},\n      primaryClass={cs.LG},\n      url={https://arxiv.org/abs/2410.08868}, \n}", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: Theorem 1 is the most significant result of the paper. It establishes gradient domination for RLGU. Similar to linear RL, it upper bounds  the sub-optimality (a global quantity) with current  gradient (a local quantity).   Combined with sufficient increase lemma (smooth function), this result directly implies global convergece of policy gradient of RLGU with an iteration complexity of $O(\\frac{1}{\\epsilon})$ similar to linear RL. The proof for the theorem is also very short and sweet.  In my opinion, this result on its own is enough for the paper to be accepted.\n\n Weakness: (Minor) The paper misses to cite [1,2] that establishes convergence of policy gradient in finite steps (independent of state space).\n\n[1]@misc{liu2024elementaryanalysispolicygradient,\n      title={Elementary Analysis of Policy Gradient Methods}, \n      author={Jiacai Liu and Wenye Li and Ke Wei},\n      year={2024},\n      eprint={2404.03372},\n      archivePrefix={arXiv},\n      primaryClass={math.OC},\n      url={https://arxiv.org/abs/2404.03372}, \n}  \n\n[2] @misc{liu2024convergenceprojectedpolicygradient,\n      title={On the Convergence of Projected Policy Gradient for Any Constant Step Sizes}, \n      author={Jiacai Liu and Wenye Li and Dachao Lin and Ke Wei and Zhihua Zhang},\n      year={2024},\n      eprint={2311.01104},\n      archivePrefix={arXiv},\n      primaryClass={math.OC},\n      url={https://arxiv.org/abs/2311.01104}, \n}", "was_revised": true, "final_justification": "The paper has nice contribution to convex RL, hence worth accepting.", "rebuttal": "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. \n\n> **Weakness 1 (minor):** The paper misses to cite [1,2] that establishes convergence of policy gradient in finite steps (independent of state space).\n\n\n**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. \n\n> **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?\n\n**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. \n\n> **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?\n\n**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. \n\n> **Question 3:** Could your analysis extend to the average‑reward setting (e.g., Kumar et al. 2025)? What are the challenges?\n\n**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.\n\n> **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?\n\n**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.\n\n\nWe appreciate the reviewer’s detailed and supportive assessment. We will incorporate the suggested citations and clarifications in the final version."}]

Author rebuttal:

Meta-review: This paper analyzes the policy gradient method for reinforcement learning with general utilities and establishes global optimality guarantees. Specifically, it proves global optimality for policy gradient when the utility is concave and the MDP is tabular, using the gradient domination technique. The paper then extends the analysis beyond the tabular setting by estimating the state-action occupancy measure via maximum likelihood within an approximating class.

To the best of my knowledge, this is the first work to provide global optimality guarantees for reinforcement learning with general utilities (RLGU) beyond the tabular case, and it establishes a tight bound. Most reviewers agreed that the paper merits acceptance, and after carefully reviewing the rebuttal and discussion, I share this view. That said, I recommend that the authors incorporate the reviewers’ feedback into the final version of the paper, with particular attention to:

1- Including real-world examples that highlight the practical significance of the presented analysis.

2- Adding discussion on the limitations of the analysis, especially for the continuous case, and clarifying the assumptions made.
Decision: Accept (poster)