Occupancy-based Policy Gradient: Estimation, Convergence, and Optimality

Authors: audrey  huang
nan  jiang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 17:08:37

Abstract: Occupancy functions play an instrumental role in reinforcement learning (RL) for guiding exploration, handling distribution shift, and optimizing general objectives beyond the expected return. Yet, computationally efficient policy optimization methods that use (only) occupancy functions are virtually non-existent. In this paper, we establish the theoretical foundations of model-free policy gradient (PG) methods that compute the gradient through the occupancy for both online and offline RL, without modeling value functions. Our algorithms reduce gradient estimation to squared-loss regression and are computationally oracle-efficient. We characterize the sample complexities of both local and global convergence, accounting for both finite-sample estimation error and the roles of exploration (online) and data coverage (offline). Occupancy-based PG naturally handles arbitrary offline data distributions, and, with one-line algorithmic changes, can be adapted to optimize any differentiable objective functional.

Main paper: 
 introduction: 
 Value-based methods have been the dominant paradigm in model-free reinforcement learning, with a solid theoretical foundation in large state spaces under function approximation [CJ19; JYWJ20a; ZLKB20; JLM21; XJ21; XFBJK22]. In contrast, a model-free RL paradigm based on their natural counterparts-the occupancy functions-remains largely under-investigated. Occupancy functions are densities that describe a policy's state visitation, and play instrumental roles in guiding exploration [HKSVS19; AFK24], handling distribution shift [HM17; NCDL19; CJ22], and optimizing general objectives beyond the expected return [ZBWK20; MDSDBR22] . Despite this, they are seldom modeled directly in learning algorithms and appear only in the analyses, except in conjunction with value functions in marginalized importance sampling [LLTZ18; NDKCLS19; UHJ20; ZH-HJL22; HJ22a]. Recently, [HCJ23] developed algorithms in online and offline RL that model only occupancies via density function classes, spotlighting their roles in handling non-exploratory offline data and in online exploration. However, their focus was on statistical guarantees, and computationally efficient policy optimization for occupancy-based methods remained an open problem.In answer, we develop model-free policy gradient (PG) algorithms that compute the gradient through occupancy functions, without estimating any values. By leveraging a Bellman-like recursion, we reduce occupancy-based gradient estimation to solving a series of squared-loss minimization problems, which can be done in a computationally oracle-efficient manner. Our analysis captures the effects of gradient estimation error, exploration (in online PG, which is characterized by the initial state distribution), and offline data quality (in offline PG) on the sample and iteration complexity required for local and global convergence. In the online setting, our results complement previous works on the optimality of value-based PG [AKLM21; BR24] and extend past their scope to in-clude general objectives of occupancy functions, such as entropy maximization for pure exploration and risk-sensitive functionals in safe RL [MDSDBR22] . These objectives generally cannot be optimized using value-based policy gradients because they do not admit value functions or Bellman-like equations with which to estimate them [ZBWK20; HDGP24].In the offline setting, we handle gradient estimation from fixed datasets of poor coverage, which departs from most existing (value-based) off-policy PG estimators that assume an exploratory dataset [KU20; XYWL21; NZJZW22]. Learning with non-exploratory data is a core consideration in recent offline RL [XCJMA21; ZHHJL22] , and gives rise to unique challenges in our setting: occupancies are converted into density ratios for learning purposes, but these ratios become unbounded when the data lacks coverage. [HCJ23] used clipping to handle occupancy estimation under poor coverage, which we show is insufficient for gradient estimation (Prop. 4.2). Instead, a novel smooth-clipping mechanism (Sec. 4.2) is developed to provide statistically robust gradient estimates.App. A includes a full discussion of related work, and our contributions are organized as follows:1. Online PG (Sec. 3) We propose OCCUPG, an occupancy-based PG algorithm that reduces gradient estimation to squared-loss minimization, based on a recursive Bellman flow-like update for the occupancy gradient. We analyze the sample complexities for both local and global convergence, and, notably, our algorithm and analyses extend straightforwardly to the optimization of general objective functionals. 2. Offline PG (Sec. 4) For offline RL we develop and analyze OFF-OCCUPG, which optimizes only the portions of a policy's return that are adequately covered by offline data. Conceptually, our algorithm is based on combining the methods in Sec. 3 with (a smoothed version of) the recursively clipped occupancies from [HCJ23] . As a result, our estimation and convergence guarantees do not require assumptions on data coverage, which relaxes the restrictions of previous works.+ ∈ Π Θ such that π + ∈ argmax π ′ B π (π ′ ).+ ∈ Π Θ such that π + ∈ argmax π ′ B π (π ′ ). 
preliminaries: 
 Finite-horizon Markov decision process (MDP). Finite-horizon MDPs are defined by the tuple M = (S, A, P, R, H, d 0 ), where S is the state space, A is the action space, and H is the horizon.We use [H] = {0, . . . , H} and when clear from the context, use {□ h } = {□ h } h∈ [H] . For notational compactness we assume that S = ∪h S h is the union of H disjoint sets {S h }, each of which is the set of states reachable at timestep h. This is WLOG as we can always augment the state space with[H] at the cost of only H factors [JKALS17; MBFR24].Since each state can only be visited at a single timestep, we can now define the (non-stationary) transitions as P : S × A → ∆(S), and the initial state distribution as d 0 ∈ ∆(S 0 ). We assume the reward function R : S → [0, 1] is bounded on the unit interval and (for simplicity) state-wise deterministic. This sufficiently captures the challenges of our setting since the occupancies are densities over states, and it will be easily seen later that our results generalize to per-state-action rewards. A policy π : S → ∆(A) interacting with M observes trajectories {(s h , a h , s h+1 , r h+1 )} H-1 h=0 , and has expected returnJ(π) = E π [ H h=1 R(s h )].At any (h, s, a), its expected return-to-go is encoded in the value functionQ π h (s, a) = E π [ h ′ >h R(s h ′ )|s h = s, a h = a].For each h ∈ [H], a policy's occupancy function d π h ∈ ∆(S) is a p.d.f. describing its state visitation, d π h (s) = P π (s h = s). In combination with the policy, the MDP dynamics dictate the evolution of the occupancy over timesteps. This is encoded in the recursive Bellman flow equation, which mandates thatd π h = P π d π h-1 for all h ∈ [H].Here, P π is the Bellman flow operator with (P π f )(s ′ ) := s,a P (s ′ |s, a)π(a|s)f (s) ∈ R □ , for any function f : S → R □ . Policy optimization. For an objective function f : Π Θ → R, the general goal of this work is to find argmax π θ ∈ΠΘ f (π θ ) over a policy class Π Θ = {π θ : θ ∈ Θ, θ ∈ R p , θ ≤ B}, parameterized by a convex and closed parameter class Θ with dimension p. One example of f is the expected return J(π θ ). Projected gradient ascent (PGA) will be our base algorithm for policy optimization. For a fixed learning rate η and iterations t ∈ [T ], it iteratively updates θ (t+1) = Proj Θ θ (t) + η∇f (π θ (t) ) . Here, ∇f (π θ ) = [ ∂f (π θ )∂θ p ] p∈[p] ∈ R p is the gradient with respect to θ, where superscript p indexes the p-th entry of a vector. We will assume that the gradient of the policy's log-probability is bounded, as is ubiquitous in the PG literature [LSAB19; AKLM21] . Assumption 2.1. For all π θ ∈ Π Θ , max s,a ∇ log π θ (a|s) ∞ ≤ G.We will later analyze the convergence rate of our algorithms to stationary points with (approximately) zero gradient, and refer to π (t) = π θ (t) for short. For PGA, stationarity will be measured using the standard gradient mapping G η (π (t) ) with G η (π (t) ) := 1 η (θ (t) -θ (t+1) ), the parameter change between iterations [Bec17] . Note that if Θ = R p and no projection is required, then G η (π (t) ) = ∇f (π (t) ) reduces to the gradient magnitude.Computational oracles. As is common in the literature, we analyze computational efficiency in terms of the number of calls to the following oracles, which serve as computational abstractions. We desire a polynomial number of such calls in terms of problem-relevant parameters. Given an i.i.d. dataset D = {(x, y)} and function class F, the maximum likelihood estimation oracle outputs argmax f ∈F E D [log f (x)]. The squared-loss regression oracle findsargmin f ∈F E D [(f (x) -y) 2 ].Both can be approximated efficiently whenever optimizing over F is feasible [MHKL20; FR20].max π ′ ∈ΠΘ B π (π ′ ) -B π (π) ≤ m max θ ′ ∈Θ ∇ B π (π), θ ′ -θ .Then for any comparator policy π E and π θ ∈ Π Θ , we haveJ(π E ) -J(π θ ) ≤ m   max h σ d π E h , C s h d D h σ d π θ h , C s h d D h ∞   max θ ′ ∈Θ ∇ J(π θ ), θ ′ -θ .Compared to Lem. 3.2, the first precondition of Lem. C.6 may be stronger because π + can be a stochastic policy, whereas deterministic policies suffice in the online setting. The second precondition is of similar strength. More importantly-as we have previously discussed-coverage coefficients of the form in Lem. C.6 are not ideal because they involve π θ in the denominator, which are variable over the learning process.Offline data as an exploratory initialization Since all occupancies are clipped to some constant of the offline data, however, we might wonder if the offline data distribution itself might serve as an exploratory initial distribution to use with OFF-OCCUPG (in some sense, this, or some reweighted version of it, is the only thing available to us in the offline setting). Prop. C.2 shows that this is indeed possible when the offline data is exploratory enough, and we use clipping for simplicity. Notably, the coverage coefficient present in the gradient domination bound is the input clipping constant h C s h . This can be seen as an offline analog of C π * in Lem. 3.2, since all occupancies are clipped to have this ratio over the offline data.Proposition C.2. Given {d D h }, define a new data distribution where d D ′ h = 1 H H-1 g=0 d D g , ∀h ∈ [H]. Then for any π, use {d D ′ h }, σ = ∧, and clipping constants {C s ′ h , C a ′ h } to define [ d π h ] ′ according to Def. 4.3. Let J ′ (π) = h [ d π h ] ′ , R . For any π and π ′ , recall B π (π ′ ) := h,s,a [ d π h ] ′ (s) π ′ (a|s)[ Q π ] ′ h (s, a). Suppose that ∀π ∈ Π Θ ,max π ′ ∈ΠΘ B π (π ′ ) -B π (π) ≤ m max θ ′ ∈Θ ∇ B π (π), θ ′ -θ . Then if {C s ′ h , C a ′ h } are such that [ d π θ h ] ′ ≤ C s ′ h d D ′ h , ∀h, for any π θ ∈ Π Θ , we have max π J(π) -J(π θ ) ≤ mH h C s h max θ ′ ∈Θ ∇ J ′ (π θ ), θ ′ -θ .In practice, we can easily generate a new dataset D ′ satisfying Prop. C.2 by first splitting eachD h into H equal parts {D i h } H i=1 , then setting D ′ h = ∪ H g=1 D h g .The sample complexity of running Alg. 2 on D ′ will then scale with h C s h , which are input parameters, instead of the coefficient in Lem. C.6, which is θ-dependent and cannot be controlled. In exchange, it requires all-policy coverage w.r.t the new [ d π ] ′ , which, while strong, was insufficient for optimality in Lem. C.6. One justification (formalized in the hardness result of Prop. C.3) is that the exploratory initialization can cause policies to exceed coverage thresholds on reward-generating states, despite being covered on (the original) d 0 . Clipping causes gradient signals to vanish, so a stationary policy might be far off-support, instead of optimal. While everything works out conceptually if {C s h , C a h } are set to be high enough, it's unclear whether doing this will require exponentially large coefficients in the worst case.Lastly, we combine the above gradient domination claims with the stationary convergence guarantee in Cor. C.1 to state the following global convergence result. Cor. C.2 is stated for J(π), our original offline optimization objective, and therefore takes into the account of approximating the clipping function with its smooth-clipped version.Corollary C.2. Suppose J(π) satisfies Asm. 3.2. If Alg. 2 with D ′ as defined in Prop. C.2 satisfies the preconditions of Prop. C.2, then set CC = H h C s h . Otherwise, define CC = max π∈ΠΘ max h σ d π * h , C s h d D h /σ d π h , C s h d D h ∞and assume the preconditions of Lem. C.6. Then under Def. C.1 and the preconditions of Thm. 4.1, Alg. 2 satisfiesE 1 T t max π J(π) -J(π (t) ) ≤ ε + 2H 2 D σ when T = O B 2 m 2 (CC) 2 βH ε 2 and n = O B 2 m 2 (CC) 2 pH 6 G 2 ( h C s h C a h ) 2 L 2 σ log(N∞(ε,G) N D ∞ (ε,ΠΘ)|F ||W|) ε 2 .Though we optimize J(π), the guarantee in Cor. C.2 is with respect to our target offline objective J(π), which implies that the learned policy competes with the best policy fully covered by offline data. Generally L σ and D σ trade-off between ease of convergence (smoothness) and approximation error, respectively. For example, instantiating the bound with σ from Prop. 4.3 with b ∝ ε results in a final ε -1/4 rate. 
online occupancy-based pg: 
 We now develop our occupancy-based policy optimization algorithm for the online RL setting, where the policy can continuously interact with the environment to gather new trajectories. Our gradient estimation routine is based on a recursive Bellman flow-like equation that can be approximately solved using squared-loss regression, not unlike those used to estimate occupancy functions in FORC [HCJ23] or value functions in FQI [ASM07] . The intuitions established for our online algorithm form the foundation for our later offline methods.The expected return of a policy π can be expressed as the expectation over its occupancy of the per-state rewards, J(π) = h s h d π h (s h )R(s h ). The gradient of J(π) then passes through d π , ∇J(π) = h s h ∇d π h (s h )R(s h ) = h E s h ∼d π h [∇ log d π h (s h )R(s h )] . We use the grad-log trick above to write ∇J(π) as an expectation over d π , which makes it amenable to estimation from online samples as long as we can calculate ∇ log d π h : S → R p . We make the key observation that ∇ log d π h can be expressed as a function of ∇ log d π h-1 , which involves a time-reversed conditional expectation over the previous timestep's (s h-1 , a h-1 ) given the current s h . Lemma 3.1. For any π and h ∈ [H], ∇ log d π h satisfies the recursionEQUATIONwhere[E π h-1 f ](s ′ ) := E π [f (s h-1 , a h-1 )|s h = s ′ ] = s,a P (s ′ |s,a)π(a|s)d π h-1 (s) d π h (s ′ )f (s, a) 1 , for any function f : S × A → R p . Further, under Asm. 2.1, max s,h ∇ log d π h (s) ∞ ≤ hG.Eq. ( 1) is derived by propagating the gradient through the Bellman flow equation, and we can solve it from h = 1 to H to compute ∇ log d π h (with ∇ log d π 0 = 0 by definition). While related observations have been made throughout the rich history of PG literature [CC97; MT01; KU20; XYWL21], the expression in Eq. ( 1) is adapted to our unique pursuit of modeling ∇ log d π with general function approximators. In particular, the conditional expectation (E π ) immediately hints that ∇ log d π is amenable to estimation using squared-loss regression, a technique that is well-understood for value functions [SB18] and, more recently, for occupancy functions [HCJ23] .Formally, to solve the dynamic programming equation of Eq. (1) in a computationally efficient manner, we reduce it to minimizing a squared-loss regression problem. Consider the standard (supervised learning) regression setup. The solution to argmin f E (x,y)∼Q [(f (x)-y) 2 ] maps x → E Q [y|x], the conditional expectation given x of the target y under the joint Q. As a result (see Lem. B.2),∇ log d π h = argmin g:S→R p E π g(s h ) -∇ log π(a h-1 |s h-1 ) + ∇ log d π h-1 (s h-1 ) 2 .(2) 1 We use the convention 0/0 = 0 for ratios between two functions. Collect n trajectories with π (t) . Set D reg h = {(s h , a h , s h+1 )} n i=1 for all h. Repeat for {D grad h }.Initialize g 0 = 0.for h = 1, . . . , H do 5: Let L (t) h-1 (g h ; g h-1 ) := 1 n (s,a,s ′ )∈D reg h-1 g h (s ′ ) -∇ log π (t) (a|s) + g h-1 (s) 2 . Set g (t) h = argmin g h ∈G h L (t) h-1 (g h ; g (t)h-1 ).(3) 6:end for 7:Estimate ∇J(π(t) ) = 1 n H h=1 (s,a,s ′ ,r ′ )∈D grad h-1 g (t) h (s ′ ) • r ′ 8: Update θ (t+1) = Proj Θ θ (t) + η ∇J(π (t)) .Here, g is a vector-valued function, and the norm • 2 is equivalent to the sum of p scalar-valued squared-losses for each parameter dimension. The RHS only requires sampling (s h-1 , a h-1 , s h ) ∼ π from online rollouts. Then, given finite samples, we can robustly estimate ∇ log d π by minimizing an empirical version of Eq. (2) using regression oracles.Alg. 1 (OCCUPG) displays our full online occupancy-based PG procedure. For each iteration t ∈[T ], we first collect two independent datasets:{D reg h } for ∇ log d π (t)estimation, and {D grad h } for ∇J(π (t) ) estimation. The former occurs in Line 5, where we recursively solve an empirical version of Eq. (2); the latter is computed in Line 7, then used to update the policy (Line 8).Gradient estimation guarantee. In the following, we establish that our regression-based estimation procedure produces accurate estimates of ∇J(π). Our guarantee holds under the requirement that the gradient function classes {G h } can express the population gradient update (Lem. 3.1) for any target function. It is analogous to the Bellman completeness assumption that is required for regression-based value or occupancy function estimation [CJ19; HCJ23].h ,s∈S g h (s) ∞ ≤ hG. Further, for all π ∈ Π Θ , we have E π h-1 (∇ log π + g h-1 ) ∈ G h , for all g h-1 ∈ G h-1 .Next, since we allow G to be a continuous function class, our sample complexity bound for gradient estimation is expressed in terms of its pseudodimension := d G (Def. : S × A → R k and µ : S → R k such that P (s ′ |s, a) = ϕ(s, a), µ(s ′ ) [JYWJ20b]. Tabular MDPs are a special case with onehot features. Due to the bilinear transitions, both the occupancy and its gradient are linear functions of µ, i.e., d π = µ(s) ⊤ ψ and ∇d π (s) = µ(s) ⊤ Ψ for some Ψ ∈ R k×p , ψ ∈ R k , and all s ∈ S. When µ is known, we can set G h to be a linear-over-linear function classG h = g h (s) = µ(s) ⊤ Ψ µ(s) ⊤ ψ : Ψ ∈ R k×p , ψ ∈ R k , max s g h (s) ∞ ≤ hG , which has d G = kp (Prop. B.1).Stationary convergence. Next, we analyze the convergence rate of OCCUPG to a stationary policy, i.e., one that has near-zero gradient. Note that, in general, stationary policies are not necessarily optimal as the objective function is non-convex. As is standard in the literature, we will assume that the objective has a smooth gradient [LSAB19; AKLM21].Assumption 3.2 (β-smooth objective). For a function f : Π Θ → R , there exists β > 0 such that ∇f (π θ ) -∇f (π θ ′ ) 2 ≤ β θ -θ ′ 2 for all θ, θ ′ ∈ Θ.Cor. 3.1 shows that, in expectation, OCCUPG with T = O(βH/ε) iterations outputs a ε-stationary point, as measured by G η (π (t) ) = 1 η θ (t) -θ (t-1) . The proof relies on Thm. 3.1, i.e., with enough samples the statistical noise of the gradient estimates are sufficiently small to enable convergence. Corollary 3.1. Under Asm. 2.1, Asm. 3.1, and Asm. 3.2, the iterates ofOCCUPG with T = O(βHε -1 ) and n = O(pd G H 6 G 2 log(T /δ)ε -1 ) satisfiy 1 T T t=1 E[ G η (π (t) ) 2 ] ≤ ε.Computational efficiency. OCCUPG is not only statistically efficient but computationally oracleefficient as well, since it reduces to a series of squared-loss minimization problems. In each iteration, it makes H calls to a regression oracle to compute the occupancy gradient (Line 5). Then to converge to a ε-stationary point, from Cor. 3.1 we require a total of O(βH2 /ε) such calls.Optimality. Lastly, we analyze when the policies recovered by OCCUPG are also approximately optimal. The key inequality is an upper bound on the suboptimality of any policy in terms of its gradient magnitude (or stationarity), and a coverage coefficient C π * with respect to the optimal policy. Lemma 3.2. For any π and π ′ , defineEQUATION)whereJ ν (π) := E s0∼ν,π [ h r h ] is the expected return of π in M with initial state distribution ν.The lemma preconditions are identical to those required for value-based analysis [BR24] . B π (π ′ ) is a one-step improvement objective with respect to the occupancies and value functions of π, and we require (1) the policy class to be expressive enough that it contains any maximizer; and (2) the one-step objective to itself have optimality gap upper-bounded by the one-step policy gradient magnitude, for which the constant m is determined wholly by the policy parameterization. For example, the tabular policy π θ (a|s) = θ sa has m = 1 [AKLM21] .The coverage coefficient C π * is the finite-horizon counterpart to the infinite-horizon "exploratory initial distribution" salient to the analysis of [AKLM21] and [BR24] (which lists developing it as future work). In RL, a small gradient magnitude alone does not guarantee optimality, as it can also occur when the policy rarely visits rewarding states. The coverage coefficient quantifies both how policy performance can suffer from insufficient exploration, as well as how exploratory initializations mitigates this problem. Finally, combining Lem. 3.2 with the stationary convergence result in Cor. 3.1 shows that, on average, the best-iterate of OCCUPG is near-optimal. Corollary 3.2. Under the preconditions of Lem. 3.2 and Cor. 3.1, running OCCUPG 2 with initialdistribution ν satisfies E[min t J(π * ) -J(π (t) )] ≤ ε when T = O βB 2 (C π * ) 2 m 2 H 2 ε 2 and n = O B 2 (C π * ) 2 m 2 pd G H 6 G 2 log(T ) ε 2 .One standout feature of OCCUPG is that it can, with a one-line change, be adapted for policy optimization of any (differentiable) objective function involving occupancies. We work with J F (π) = h F h (d π h )F (π) = h E s∼d π h ∂F h (d) ∂d(s) | d=d π h ∇ log d π h (s). Implementationwise, we need only change Line 7 in OCCUPG to accommodate the new gradient formula, to∇J F (π) = 1 n h s∈D h g π h (s) ∂F h (d) ∂d(s) | d= d π h. The partial derivative of F h is evaluated with a plug-in occupancy estimate d π that can be obtained using maximum likelihood estimation (App. D). Notably, the occupancy gradient estimation module for g π h ≈ ∇ log d π h (Line 5) is reused verbatim. Given their resemblance to those in Sec. 3.2, the full algorithm and analyses are deferred to App. B.5. 
offline occupancy-based pg: 
 In this section, we develop an algorithm for occupancy-based policy optimization in the offline setting, where only fixed datasets are available for learning. A direct modification of OCCUPG, e.g., by converting occupancies to density ratios over the offline data distribution, will fail unless the data covers all possible policies, otherwise the density ratio may be unbounded. In-line with recent state-of-the-art offline RL algorithms, our goal is to establish an offline PG algorithm that adapts to and retains meaningful guarantees under arbitrary offline datasets, for which our key consideration is establishing an offline gradient estimation method. We begin by defining these offline datasets. Definition 4.1. The offline dataset is D = {D h }, where D h = {(s h , a h , s h+1 , r h+1 ))} n i=1 is gener- ated i.i.d. as s h ∼ d D h for some d D h ∈ ∆(S) and a h ∼ π D h (•|s h ) in M,) := E (s,a,s ′ )∼D h •ρ h [g(s, a)|s ′ ] = s,a [D h •ρ h ](s,a,s ′ ) s,a [D h •ρ h ](s,a,s ′ ) g(s, a).(5)The (time-reversed) conditional expectation is taken over[D h • ρ h ](s, a, s ′ ) := P (s ′ |s, a)d D h (s)π D h (a|s)ρ h (s, a), the joint offline distribution re-weighted by ρ h . While this may not be a valid density, its induced conditional distribution on (s, a|s ′ ) always is, i.e., s,a[D h •ρ h ](s,a,s ′ ) s,a [D h •ρ h ](s,a,s ′ ) = 1. As an example, for a given π we have E D,ρ h = E π h when ρ h (s, a) = d π h (s)π(a|s) d D h (s)π D h (a|s)is the policy's density ratio and is well-defined.A policy's occupancy d π may not be covered by arbitrary offline data (Def. 4.1), so neither its expected return J(π) = h d π h , R nor its gradient ∇J(π) will be estimatable from D. As a result, there is no hope of recovering argmax π∈ΠΘ J(π). Our solution is to instead maximize return only on areas of the state space that are sufficiently covered by offline data, which is captured exactly by the recursively clipped occupancy dπ from [HCJ23] . It clamps the policy occupancy to preset multiples C s h , C a h of the offline data distribution, thereby representing only the "sufficiently covered" portion. Definition 4.2 (Recursively clipped occupancy). Let (□ ∧ □) := min{□, □}. Given clipping constants {C s h , C a h } ≥ 1, define the clipped policy to be πh = π ∧ C a h π D h , and recursively defineEQUATIONEq. ( 6) resembles the Bellman flow equation with clipped policy π, and acts on the previous-timestepdπ h-1 clipped to at most C s h-1 d D h-1 .Above this threshold the occupancy is considered to be insufficiently covered for estimation, and C s strikes a bias-variance tradeoff between the amount of clipped mass vs. distribution shift. The clipped occupancy's density ratio is always well-defined and bounded as dπh /d D, † h-1 ≤ C s h-1 C a h-1, and we use it to define our (now learnable) offline objective,J(π) = h s h dπ h (s h )R(s h ) = h E D h-1 dπ h (s h ) d D, † h-1 (s h ) R(s h ) .For any "fully covered" policy withd π h ≤ C s h-1 C a h-1 d D, † h-1 for all h ∈ [H],we have dπ = d π and J(π) = J(π). In this sense, argmax π J(π) will be at least as good as the best policy fully covered by offline data. Next, define the density ratio be wπh := dπ h /d D, † h-1 . The gradient of J(π) is ∇ J(π) = h E D h-1 wπ h (s h )R(s h ) ∇ log dπ h (s h ) .To calculate this gradient we must compute both wπ and ∇ log dπ ; for the former, [HCJ23] provides a method that we will later call as a subroutine. Our focus is on computing ∇ log dπ h , which is enabled by the following recursive equation, which is an offline analog of Lem. 3.1.Lemma 4.1. For any π and all h ∈ [H], define ρπ h (s, a) :=EQUATION)where E D, ρπ h-1 is from Eq. (5), and[M v](•) := v(•)M (•) ∈ R p for M : □ → p and v : □ → R. Lem. 4.1 is derived from applying the chain rule to Def. 4.2, and the clipped occupancies play an instrumental role in handling insufficient offline coverage. Notably, the indicator function zeroes-out both the gradients ∇ log π and ∇ log dπ h-1 where they are insufficiently covered, e.g., dπh-1 (s) > C s h-1 d D h-1 (s).Further, under full offline coverage we recover Lem. 3.1 and ∇ log dπ = ∇ log d π . Because the rewards are nonnegative, ∇ log dπ induces a pessimistic policy gradient that shifts policies away from out-of-distribution actions, even if they generate high return. This is seen more clearly in Prop. 4.1, that rearranges the resulting expression for ∇ J(π) into a value-based form: Proposition 4.1. We can equivalently write∇ J(π) = h E D h [ρ π h (s, a)∇ log π h (a|s) Qπ h (s, a)],where Qπ is a pessimistic value function that obeys the Bellman-like recursion Qπh (s, a) = 1[π ≤ C a h π D h ](a|s) s ′ P (s ′ |s, a) R(s ′ ) + 1[ dπ h+1 ≤ C s h+1 d D h+1 ](s ′ ) Qπ h+1 (s ′ , πh+1 ) .In Qπ , future returns are zeroed out at states and actions that exceed the threshold of data coverage, due to indicators functions that are inherited from ∇ log dπ . Prop. 4.1 can be seen as a pessimistic offline analog to the classical PG theorem∇J(π) = h E s,a∼d π h [∇ log π(a|s)Q π h (s, a)] [SMSM99], entirely induced by the definition of the clipped occupancy.Non-robustness of ∇ log dπ estimation to plug-in densities. With finite samples, however, it turns out that consistent estimates of ∇ log dπ h in Eq. ( 6) cannot be computed. To make this argument, we first outline the high-level gradient estimation procedure for a fixed policy:• Estimate occupancies{ d π h } and { d D h } • Compute ∇ log dπ h using Eq. (7) with plug-in indicator function estimate 1[ d π h-1 ≤ C s h d D h-1 ]The problem arises in step two, as 1[•] is a stepwise function and not smooth. Even if d π is vanishingly close to d π , the gradient calculated from plug-in occupancy estimates can have constant error. Proposition 4.2. There exists an MDP and policy π such that, for any ε > 0, max h,s ∇ logd π h (s)- ∇ log dπ h (s) = O(1) when dπ h -d π h 1 ≤ ε and d D h -d D h 1 ≤ ε for all h.To resolve this issue, we will use a "smooth-clipping" function σ (x, c) to approximate the "hard"clipping (x ∧ c) in Eq. ( 6), whose non-smooth gradient was the source of our estimation problems. Figure 1 plots 1-D examples of σ (x, c) against (x ∧ c) as reference (dashed), and Asm. 4.1 describes the properties of σ that enable our later estimation and convergence guarantees. Assumption 4.1. Assume that σ satisfies ∀x, x ′ , c, c ′ ∈ dom(σ), 1. (Approximate clipping) ∃D σ ≥ 0 such that 0 ≤ (x ∧ c) -σ (x, c) ≤ D σ (x ∧ c). 2. (Monotonicity) σ (x ′ , c) ≤ σ (x, c) if x ′ ≤ x; σ (x, c ′ ) ≤ σ (x, c) if c ′ ≤ c;∃L σ ≥ 0 s.t. ∀x, x ′ , c, c ′ ∈ dom(σ), c| 1 (x, c) -1 (x ′ , c) | ≤ L σ |x -x ′ |, and x| 1 (x, c) -1 (x, c ′ ) | ≤ L σ |c -c ′ |. Note that σ (x, c) = (x ∧ c) is a special case with 1 (x, c) = 1[x ≤ c], thus D σ = 0 and L σ = ∞.The following choice of σ, which is plotted in Fig. 1 , fulfills Asm. 4.1. Proposition 4.3. For any b > 1, σ (x, c) = x -b + c -b -1/b has L σ = b and D σ = 1/b.EQUATIONThen lettingw π h := d π h /d D, † h-1 , our new objective is J(π) = h E D h-1 [ w π h (s h )R(s h )] with gradient ∇ J(π) = h E D h-1 [ w π h (s h )R(s h ) ∇ log d π h (s h )],where ∇ log d π h obeys the following recursion. Lemma 4.2. For σ satisfying Asm. 4.1, recall 1 (x, c) := x ∂ x log σ (x, c) . Then for all h ∈ [H],EQUATION)whereρ π h-1 (s, a) := σ( d π h-1 (s),C s h-1 d D h-1 (s)) d D h-1 (s) π h-1 (a|s) π D h-1 (a|s) and E D, ρ π h-1 is defined in Eq. (5). Further, under Asm. 2.1, max s,h ∇ log d π h (s) ∞ ≤ hG.Eq. (9) replaces the (non-smooth) indicator function in ∇ log dπ (Lem. 4.1) with its smooth approximation 1, which, as we will show shortly, enables robust gradient estimation with plug-in occupancy estimates. As before, we can reduce it to squared-loss regression (Eq. ( 11)). Further, by optimizing J(π), we also approximately maximize our target objective J(π), with bias proportional to D σ .Proposition 4.4. Under Asm. 4.1, 0 ≤ max π∈ΠΘ J(π) -max π∈ΠΘ J(π) ≲ H 2 D σ .Alg. 2 describes the offline PG algorithm for optimizing J(π). To reduce clutter, we have used Set density ratio ρ∇ log π h := ∇ log π 1 π, C a h π D h . First(t) h-1 = π (t) h-1 π D h-1 σ d (t) h-1 ,C s h-1 d D h-1 d D h-1. 9:Set gradient regression target yEQUATIONend for12: Set ∇ J(π (t) ) = 1 n H h=1 (s,a,s ′ ,r ′ )∈D grad h w (t) h (s ′ ) • g (t) h (s ′ ) • r ′ 13:Update θ (t+1) = Proj θ (θ (t) + η ∇ J(π (t) )). 14: end for Before stating the estimation guarantee for ∇ J(π), we first introduce the required assumptions. For simplicity, we assume that the function classes used in MLE and FORC are finite, and defer their guarantees to the respective appendices, as they have been well-established in previous papers [AKKS20 ; HCJ23] . We focus on discussing Asm. 4.2 for the offline gradient function class, which requires a stronger level of expressiveness. Since the regression target in OFF-OCCUPG involves plug-in occupancy estimates, the completeness condition naturally requires G h to express the gradient update in Lem. 4.2 for all possible targets composed of functions fromF h-1 , W h-1 , G h-1 .As a result, Asm. 4.2 is generally stronger than Asm. 3.1 for OCCUPG.h g h ∞ ≤ hG; and for all (π, g, f, f ′ , w) ∈ Π Θ × G h-1 × F h × F h-1 × W h-1 , we have E D,ρ h-1 (∇ log π h-1 + g 1 wf ′ , C s h-1 f ) ∈ G h , where ρ = σ(wf ′ ,C s h f ) f π h-1 π D h-1.When the underlying MDP has favorable structure, however, we can expect that d G is not much larger than was required for OCCUPG. This is indeed the case in low-rank MDPs, where the G defined in Rem. 3.1 also satisfies Asm. 4.2 (proof in Prop. C.1). Due to the bilinear transition structure, the offline gradient update (Lem. 4.2) applied to any target remains a linear-over-linear function.The guarantees for the MLE (Alg. 4) and weight estimation (Alg. 5) subroutines require Asm. D.1 and Asm. E.1, respectively, which are included in the preconditions of the main result below. Briefly, Asm. D.1 requires F to realize the true data distributions d D h and d D, † h , which is standard in supervised learning. Asm. E.1 requires W to be closed under the Bellman flow operator, and can be viewed as a 1-dimensional version of Asm. 4.2 where ρ = 1. In this sense both assumptions are weaker requirements on expressivity than that of the gradient class in Asm. 4.2, and more detailed discussions are left to App. D and App. E.Having established its preconditions, we now present our main estimation guarantee for OFF-OCCUPG, which pays additional factors for the coverage of offline data ( h C s h C a h ) and the smoothness of σ. p. ≥ 1 -δ we have ∇ J(π) -∇ J(π) ≤ ε when n = O pd G H 6 G 2 ( h C s h C a h ) 2 L 2 σ log(|W||F |/δ) ε 2 .Stationary convergence & computational efficiency. Similar to OCCUPG, OFF-OCCUPG with T = O(βH 2 /ε 2 ) converges to an ε-stationary point. The formal statement is given in Cor. C.1 and is based on the estimation guarantee in Thm. 4.1. As a result, OFF-OCCUPG is also computationally oracle-efficient. Each invocation of MLE involves 2H calls to a likelihood maximization oracle (see Alg. 4), and each invocation of FORC requires H calls to a squared-loss regression oracle (see Alg. 5). Then local convergence is still achieved with O(βH 2 /ε 2 ) such calls, as increasing T further cannot reduce error from statistical noise (that depends only on the fixed n).Optimality. Analyzing the conditions under which offline PG recovers global optima is more challenging, as we can no longer utilize exploratory initialization (from Cor. 3.2). However, since all occupancies have been clipped to the data distribution, we show in App. C.5 that the offline data itself can sometimes suffice as an exploratory initial distribution, and the corresponding bound is in terms of {C s h } (instead of the online C π * ). However, this is not guaranteed in general and our current result only holds under strong all-policy offline data coverage. Briefly, some hardness comes from the fact that clipping causes gradient signals to vanish, so a stationary policy might be far offsupport, rather than optimal. Investigating the possibility of more relaxed conditions for offline PG convergence (or, conversely, refining hardness results) are especially interesting directions for future work. 
conclusion: 
 For the first time, we demonstrate how policy optimization can be conducted with (only) occupancy functions for both online and offline RL, and comprehensively analyze both local and global convergence. In the online setting our method directly extends to optimizing general objective functionals that cannot be optimized using value-based methods, and in the offline setting the occupancy-based gradient naturally handles incomplete offline data coverage. As our work is the first in this line of research and theoretical in nature, for future work we plan to launch empirical investigations of our methods, especially those for optimizing general functionals. Additionally, the conditions under which offline PG can converge to global optima is not well-understood, and we hope that our preliminary results here encourage greater interest and investigation into this question. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [NA] Justification: We do not believe that Figure 1 constitutes as an experiment that requires code.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA] Justification: Per our answer to the previous question, we do not have experiments.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 a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
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: Per the answer to the previous question, we do not have experiments with statistical error.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, confidence 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, or 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 or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: Per the previous answer, we do not have experiments requiring computational resources.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 in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We do not believe we deviate from the Code of Ethics.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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA]  
 
 Appendix: In this section, we discuss related works in greater detail that concern the convergence and estimation of policy gradient in RL.While a handful of recent papers have similarly observed that the gradient of the log density can be utilized to compute the policy gradient, especially in the context of using it to optimize general functionals, none of them have analyzed methods that are sample-efficient under general function approximation. In particular, [KJDC24] requires on-policy sampling from the time-reversed transition (s, a|s ′ ), which, as they note, is highly restrictive. To overcome this issue they propose a min-max algorithm that converges under linear approximation, which is computationally a far more difficult to solve (under a more stringent structural assumption) than the regression objective in Alg. 1. Similarly, [BFH23] consider only online policy gradient, and to handle large state spaces they use linear function approximation, which may incur a large error through bias in many settings. [ZBWK20] approach the problem of optimizing risk functionals through a primal-dual approach that involves occupancies as dual variables, but they only analyze convergence in tabular settings.A number of works on off-policy gradient optimization utilize all three of the density ratio, value, and policy class functions to compute the gradient [NDKCLS19; HJ22b; UIJKSX21; XYWL21]. This is because the density ratios are required to handle distribution mismatches with offline data. The downside, however, is that even max-min optimization is difficult, so performing optimization over all three functions requires complex optimization loops. By using simply projected gradient ascent on a policy class, our algorithms avoid such complexities and are amenable to classical convergence analysis that allow us to focus on the role of coverage coefficients in our final results.Because the density ratio is generally not well-defined with arbitrary offline data, all of these works require some form of all-policy coverage for both estimation and convergence guarantees. The weight gradient calculation in [UIJKSX21] exhibits a recursive decomposition that is related to ours. However, their formulation is not compatible with our data assumptions and they require policy coverage to be well-defined. A follow-up paper in [XYWL21] uses squared-loss regression on the same updates, which is similar in flavor to our gradient estimation objectives. However, they use linear function approximation for weight functions, which is not realizable in general, and also require all-policy coverage for their convergence results.One close work of comparison is [LSAB19] , whose PG algorithm uses learned density ratios to reweight the data distribution and approximate the expression of the policy gradient theorem [SMSM99] . To handle coverage issues in offline PG, they "zero out" portions of the trajectory that exceed data coverage, but only do this for (s, a) such that d D (s)π D (a|s) = 0. This is done (in the infinite horizon setting) by resampling the dataset based on an augmented MDP where such (s, a) transition to an absorbing state However, this does not control the (potentially extremely large) variance of the estimator, e.g., on states where d D (s) ≈ 0. Their objective can be seen as a special case of J(π) with finite but extremely large choices of C s and C a . They show convergence to a stationary point in terms of weight and value estimation errors that are left implicit, and leave the high variance and coverage issues with offline data implicit.Another is [DWS12] , that takes the complementary approach and simply calculates the gradient averaged on d D . However, this is a biased gradient object and does not express the policy gradient of any specific function, which means its stationary point may not even exist, thus precluding convergence analysis.The PSPI algorithm in [XCJMA21] is a policy optimization algorithm based on pessimistic value functions. Their setting is somewhat orthogonal to ours in the sense that they study values and we study occupancies, and we note that they do not perform policy optimization with respect to a standalone policy class but rather an implicit one induced by the value functions, which an be extremely large. In the value function sphere, [NZJZW22] leverage the linear structure of linear-MDPS to develop closed-form gradient estimators through the value functions. They largely only analyze estimation errors and additionally require a form of all-policy coverage for their results.Lastly, our optimality analysis builds off the results in [BR24] and [AKLM21] that analyze global optimality in the (infinite horizon) online setting.B Additional results and proofs for Sec. 3B.1 Proofs for Sec. 3.1 Proof of Lem. 3.1 First we expand ∇d π h using the Bellman flow equation,d π h (s ′ ) = s,a P (s ′ |s, a)π(a|s)d π h-1 (s): ∇d π h (s ′ ) = s,a P (s ′ |s, a)(∇π(a|s)d π h-1 (s) + π(a|s)∇d π h-1 (s)) = s,a P (s ′ |s, a)π(a|s)d π h-1 (s)(∇ log π(a|s) + ∇ log d π h-1 (s)). In the last line above we use the grad-log trick. Note that ∇ log d π (s) is not well-defined when d π (s) = 0, but the two terms will cancel out in the above expression for this case. From Bayes' theorem,P π (s h-1 = s, a h-1 = a|s h = s ′ ) = P (s ′ |s, a)π(a|s)d π h-1 (s)/d π h (s ′ ), thus ∇ log d π h (s ′ ) = ∇d π h (s ′ )/d π h (s ′ ) = E π [∇ log π(a|s) + ∇ log d π h-1 (s)|s h = s ′ ] = [E π h-1 (∇ log π + ∇ log d π h-1 )](s ′ ).We use the convention that 0/0 = 0, thus ∇ log d π h is always well-defined. Lastly, the second statement results from Lem. B.1, which shows that ∇ log d π h (s ′ ) is always bounded and well-defined under Asm. 2.1. Lemma B.1. Under Asm. 2.1, we have max s,h ∇ log d π h (s) ≤ hG.Proof. The lemma statement can be derived inductively starting from the observation that Eq. ( 1) is an expectation over its target functions. As a result, the maximum gradient magnitude should accrue additively over horizons. More concretely, fix h and s. Then∇ log d π h (s ′ ) = E π [∇ log π(a|s) + ∇ log d π h-1 (s)|s h = s ′ ] ≤ ∇ log π(a|s) + ∇ log d π h-1 (s) ≤ G + ∇ log d πh-1 (s) , using Asm. 2.1 in the last line. Since ∇ log d π 0 = 0 by definition, unrolling the above recursion through timesteps gives the stated result.Lemma B.2. For g : S → R p and f : S × A → R p , define the squared lossL h (g; f, π) = E π [ g(s h+1 ) -f (s h , a h ) 2 ].Then for any such f ,E π h (f ) = argmin g:S→R p L h (g; f, π) and ∇ log d π h+1 = argmin g:S→R p L h (g; ∇ log π + ∇ log d π h , π) .Proof of Lem. B.2. Since the objective is convex, can solve for the minimizer in closed form by taking the derivative and setting it to 0 in an element-wise manner. Fix s ′ . Taking the gradient of L h (g; f, π) with respect to g(s ′ ), we have that0 = d π h (s ′ )g(s ′ ) - s,a P (s ′ |s, a)π(a|s)d π h-1 (s)f (s, a).Rearranging and using the definition of E π h gives the result. The second statement follows from Lem. 3.1.Proof of Thm. 3.1 First we split up the errors contributed by regression and the estimation. Fix π, thenE D reg [ ∇J(π)] = h E s∼d π h [ g π h (s)R h (s)]and∇J(π) -∇J(π) ≤ ∇J(π) -E D reg [ ∇J(π)] + E D reg [ ∇J(π)] -∇J(π)The first term is related to the regression error ing π h approximating ∇ log d π h , ∇J(π) -E D reg [ ∇J(π)] = h E d π h [∇ log d π h (s)R h (s)] -E d π h [ g π h (s)R h (s)] ≤ h E d π h [∇ log d π h (s) -g π h (s)] = h p p=1 ∇ p log d π h -[ g π h ] p 2 1,d π h .For a fixed h and p, we recursively decompose∇ p log d π h -[ g π h ] p 1,d π h ≤ ∇ p log d π h -[E π h-1 (∇ log π + g π h-1 )] p 1,d π h + [E π h-1 (∇ log π + g π h-1 )] p -[ g π h ] p 1,d π h ≤ ∇ p log d π h-1 -[ g π h-1 ] p 1,d π h-1 + [E π h-1 (∇ log π + g π h-1 )] p -[ g π h ] p 2,d π h , using the fact that ∇ log d π h = E π h-1 (∇ log π + ∇ log d π h-1) in the second line. Then unrolling the recursion, we have∇ p log d π h -[ g π h ] p 1,d π h ≤ h [E π h-1 (∇ log π + g π h-1 )] p -[ g π h ] p 2,d π hApplying Lem. F.2 (more exactly, this is an offline version but we invoke it with ρ = 1 and no clipping for the online setting) with δ ′ = δ/2Hp and a union bound over all h and p, we have[E π h-1 (∇ log π + g π h-1 )] p -[ g π h ] p 2 2,d π h = E[L p D reg h-1 ( g π h , g π h-1 ) -L p D reg h-1 (E π h-1 (∇ log π + g π h-1 ), g π h-1 )] ≤ 2(ε reg h-1 ) 2 ,whereε reg h-1 = cd G h 2 G 2 log(2Hp/δ) n. Then for any h, p we have∇ p log d π h -[ g π h ] p 1,d π h ≤ √ 2 g≤h ε reg g ≤ √ 2hε reg h = 2cd G h 4 G 2 log(2Hp/δ) n Implying ∇J(π) -E D reg [ ∇J(π)] ≤ √ pH ∇ p log d π H -[ g π H ] p 1,d π H = 2cpd G H 6 G 2 log(2Hp/δ) nFor the second term,|E D reg [ ∇ p J(π)] -∇ p J(π)| ≤ h |E s∼d π h [ g π h (s)R h (s)] - 1 n s∈D h g π h (s)R h (s)| ≤ H 2 G log(2pH/δ) n ,where we use Hoeffding's inequality with union bound, for all h ∈ [H] and p ∈ p in the last line, given that the randomness of g is independent given D reg h . ThusE D reg [ ∇J(π)] -∇J(π) ≤ H 2 G p log(2pH/δ) n Combining the two terms, our final bound is ∇J(π) -∇J(π) ≲ pd G H 6 G 2 log(2Hp/δ) n ,with the regression error dominating.Proof of Cor. 3.1 For any fixed run of Alg. 1, calling Thm. 3.1 for π (t) with δ ′ = δ/T and taking a union bound over T gives with probability at least 1 -δ that∇J(π (t) ) -∇J(π (t) ) ≲ pd G H 6 G 2 log(2HpT /δ) n , ∀t ∈ [T ].Then setting δ = 1/ √ n, we haveE ∇J(π (t) ) -∇J(π (t) ) ≲ pd G H 6 G 2 log(2HpT n) n ,where the expectation is over random samples in D reg , D est . Finally, plugging this into the PGD stationary convergence bound in Lem. G.1 gives1 T t E G η (π (t) , ∇J(π (t) )) 2 ≤ 4βH T + 6pd G H 6 G 2 log(2HpT n) nSetting the RHS to ε and setting T, n appropriately gives the result.We will establish the conditions under which J(π) satisfies a gradient domination property, meaning that for any θ ∈ Θ, the suboptimality of π θ is bounded by some function S that includes a measure of its stationarity, i.e., max π ′ ∈ΠΘ J(π ′ ) -J(π θ ) ≤ S(∇ J(π θ )). This combined with the sample complexity bounds for stationary convergence established in Cor. 3.1 enables our global optimality result in Cor. 3.2.Though we are concerned with optimizing J(π) induced by running π starting from initial distribution d 0 , it will be useful to consider performing Alg. 1 using a different exploratory initial distribution µ ∈ ∆(S). By exploratory, we mean that we allow µ(s) > 0 for all s ∈ S, unlike d 0 ∈ ∆(S 0 ).In the (stationary) infinite horizon this is a common trick for obtaining well-defined gradient domination bounds [AKLM21] , but its finite-horizon (nonstationary) counterpart is nontrivial and to our knowledge has not previously been formalized (it is listed as future work in [BR24] ).We state and prove a more general version of Lem. 3.2:Lemma B.3. For any π and π ′ , define B π (π ′ ) := h,s,a d π h (s)π ′ (a|s)Q π h (s, a). Suppose ∀π ∈ Π Θ , 1. (Policy completeness) There exists π + ∈ Π Θ such that π + ∈ argmax π ′ B π (π ′ ). 2. (Gradient domination) max π ′ ∈ΠΘ B π (π ′ ) -B π (π) ≤ m max θ ′ ∈Θ ∇B π (π), θ ′ -θ Given ν ∈ ∆(S), define the coverage coefficient C π * := h d π * h /ν ∞ for π * = argmax π J(π). Then for any π θ ∈ Π Θ , J(π * ) -J(π θ ) ≤ m h d π * h h d π θ µ,h ∞ max θ ′ ∈ΠΘ ∇J µ (π θ ), θ ′ -θ ≤ C π * max θ ′ ∈ΠΘ ∇J ν (π θ ), θ ′ -θ , where J ν (π) := E s0∼ν,π [ h r h ] is the expected return of π in M with initial state distribution ν.Proof of Lem. B.3 First we note two facts that hold regardless of M. We haveQ π g (s h , a h ) = Q π h (s h , a h ) for any g ≤ h, and d π g (s h ) = 0 if g > h. J(π * ) -J(π θ ) = H-1 h=0 s,a d π * h (s) (π * (a|s) -π θ (a|s)) Q π θ h (s, a)Then we will writeQ π (s, a) ≡ Q π h (s, a), thus J(π * ) -J(π θ ) = H-1 h=0 d π * h (s) (π * (a|s) -π θ (a|s)) Q π θ (s, a) = s,a h d π * h (s) (π * (a|s) -π θ (a|s)) Q π θ (s, a) ≤ max π + s,a h d π * h (s) π + (a|s) -π θ (a|s) Q π θ (s, a) ≤ max π + s,a h d π * h (s) h d π θ µ,h (s) h d π θ µ,h (s) π + (a|s) -π θ (a|s) Q π θ (s, a) ≤ h d π * h µ ∞ max π + s,a h d π θ µ,h (s) π + (a|s) -π θ (a|s) Q π θ (s, a)For the RHS, observe thatd π θ µ,g (s h ) = 0 for g > h. Then h s,a d π θ µ,h (s) π + (a|s) -π θ (a|s) Q π θ (s, a) = h s,a d π θ µ,h (s) π + (a|s) -π θ (a|s) Q π θ h (s, a) = h s,a d π θ µ,h (s) π + (a|s) -π θ (a|s) Q π θ µ,h (s, a) = B π θ (π + ) -B π θ (π θ ) ≤ m max θ ′ ∈Θ ∇B π θ (π θ ), θ ′ -θ = m max θ ′ ∈Θ ∇J µ (π θ ), θ ′ -θCombining the two inequalities results in the final guarantee. J(π * ) -J(π (t) ) ≤ mC π * max θ ′ ∈ΠΘ ∇J(π (t) ), θ ′ -θ ≤ BmC π * G η (π (t) ) (Lem. G.4)Then summing through T and taking an expectation over the randomness in the algorithm, we have E 1 T t J(π * ) -J(π (t) ) ≤ BmC π * E 1 T t G η (π (t) ) ≤ BmC π * 4βH T + 6pd G H 6 G 2 log(2HpT n) n . (Cor.G h = g h = µ ⊤ Ψ µ ⊤ ψ : Ψ ∈ R k×p , ψ ∈ R k , g h ∞ ≤ hG, ∀h ∈ [H] .Then {G h } satisfies Asm. 3.1 and has pseudodimension (Def. F.1)d G h = O(kp).Proof of Prop. B.1. It suffices to show that, for any function f : S × A → R p and policy π, its gradient update from Lem. 3.1 is E π h (∇ log π + f ) ∈ G h+1 . Since [E π h (∇ log π + f )](s ′ ) = E π [∇ log π(s, a) + f (s)|s ′ ],from Bayes' rule and the definition of the Bellman flow operator (see proof of Lem. 3.1), we have[E π h (∇ log π + f )](s ′ ) = [P π h-1 (∇ log π + f )](s ′ ) d π h (s ′ ).First, we will show that [P π h f ](s ′ ) = µ(s ′ ) ⊤ Ψ for some Ψ ∈ R k×p and all s ′ ∈ S. Below, we use f p (s) to denote the p-th parameter of f (s) ∈ R p . For fixed p ∈ [p],[P π h f ] p (s ′ ) = s,a P (s ′ |s, a)π(a|s) (∇ p log π(a|s) + f p (s)) = µ(s ′ ) ⊤ s,a ϕ(s, a)π(a|s) (∇ p log π(a|s) + f p (s)) = µ(s ′ ) ⊤ ψ,where ψ = s,a ϕ(s, a)π(a|s) (∇ log π(a|s) + f p (s)) ∈ R k . Stacking this result for each p into the matrix Ψ shows the desired statement that [P π h f ](s ′ ) = µ(s ′ ) ⊤ Ψ. We can apply similar reasoning as above in the Bellman flow equation to show that d π h (s ′ ) = µ(s ′ ), ψ for some θ ∈ R k . Combined with the above, this shows that∇ log d π h (s ′ ) = µ ⊤ Ψ µ ⊤ ψ ,Combining the linear forms of the numerator and denominator reveal that ∇ log d π h ∈ G h . Lastly, the pseudo-dimension of G h follows directly from applying Lemma 24 of [HCJ23] , which bounds the pseudo-dimension of linear-over-linear function classes with p = 1, in all p dimensions. for h = 1, . . . , H -1 do 4: Define L (t) h-1 (g h , g h-1 ) := 1 n (s,a,s ′ )∈D reg h-1 g h (s ′ ) -∇ log π (t) (a|s) + g h-1 (s) 2 ,and set g(t) h = argmin g h ∈G h L (t) h-1 (g h , g (t)h-1 ).end for6: Estimate d π h ← MLE(D mle , F). // Alg. 4 7: Estimate ∇J F (π) = 1 n h s∈D est h g π h (s) ∂F h (d) ∂d(s) d= d π h 8: Update θ (t+1) = Proj Θ θ (t) + η ∇J(π (t)) . 9: end forAlg. 3 displays the full algorithm for optimization of general functions (described in Sec. 3.3). It shares its occupancy gradient estimation module with OCCUPG. Compared to Alg. 1, the only change is the objective gradient calculation in Line 7, which uses a plug-in estimate of the occupancy (Line 6) to evaluate the partial derivative.Since the algorithmic change is small, the analysis for Alg. 3 requires only a few adaptations from the analysis of OCCUPG. For smooth and differentiable functionals, we provide the gradient estimation guarantee below. The smoothness ensures that using plug-in occupancy estimates to evaluate the partial derivative leads to consistent gradient estimates, and is in line with the spirit of standard objective smoothness requirements (Asm. 3.2). Assumption B.1. Suppose that for all h, F h has a smooth gradient, i.e., for any f, f ′ ∈ ∆(S) that First, for all h ∈ [H], with probability at least 1 -δ we have occupancy estimates from Alg. 4 such thats ∂F h (d) ∂d(s) d=f - ∂F h (d) ∂d(s) d=f ′ ≤ L F f -f ′ 1 ,d π h -d π h 1 ≤ 2 log(H|F|/δ) n := ε mle , ∀h ∈ [H].This follows directly from Lem. D.1 with a union bound over H.Next, we isolate the occupancy estimation-related term from the error we would like to bound. Define∇ J F (π) := h E s∼d π h ∂F h (d) ∂d(s) | d= d π h ∇ log d π h (s), and decompose∇J F (π) -∇J F (π) ≤ ∇J F (π) -∇ J F (π) + ∇ J F (π) -∇J F (π)For the first term,∇J F (π) -∇ J F (π) ≤ h E s∼d π h ∂F h (d) ∂d(s) | d=d π h ∇ log d π h (s) - ∂F h (d) ∂d(s) | d= d π h ∇ log d π h (s) ≤ HG h E s∼d π h ∂F h (d) ∂d(s) | d=d π h - ∂F h (d) ∂d(s) | d= d π h ≤ HG h,s ∂F h (d) ∂d(s) | d=d π h - ∂F h (d) ∂d(s) | d= d π h ≤ H 2 GL F max h d π h -d π h 1 , ≤ H 2 GL F ε mle .using Asm. B.1 in the second to last inequality. This takes care of the aforementioned occupancy estimation error.Conditioned on such { d π h }, the second pair of terms ∇ J F (π) -∇J F (π) is analogous to the error bounded in Thm. 3.1, and the proof follows identically thereon, but with dependence on the range C F of the functionals. ∇ dπ h (s ′ ) = s,a P (s ′ |s, a) ∇π h-1 (a|s) dπ h-1 (s) + π(a|s)∇ dπ h-1 (s) ∧ C s h-1 d D h-1 (s) = s,a P (s ′ |s, a)π h-1 (a|s) dπ h-1 (s) ∧ C s h-1 d D h-1 (s) ∇ log πh-1 (a|s) + ∇ log dπ h-1 (s) ∧ C s h-1 d D h-1 (s)Next, dropping the h -1 subscript for a moment, observe that∇ log dπ (s) ∧ C s d D (s) = ∇ log dπ (s), if dπ (s) < C s d D (s), 0, if dπ (s) > C s d D (s),with a discontinuity at dπ (s) = C s d D (s). For simplicity, we set ∇ log dπ (s) ∧ C s d D (s) = ∇ log dπ (s) 1[ dπ (s) ≤ C s d D (s)]. Similarly, we have ∇ log π(a|s) = ∇ log π(a|s) 1[π(a|s) ≤ C a π D (a|s)]. Finally, ∇ log dπ h (s ′ ) = ∇ dπ h (s ′ )/ dπ h (s ′ ), where dπ h (s ′ ) = s,a P (s ′ |s, a)π D h-1 (a|s)d D h-1 (s)ρ π h-1 .The MDP we will describe corresponds to a multi-armed bandit with 2 actions. Consider an MDP with H = 2, and S 0 = {s 0 }, S 1 = {s L , s R }, S 2 = {s -, s + } which are terminal. In any state there are two actions, A = {L, R}, with deterministic transitions. For the first level, we have s 0 L → s L and s 0 R → s R . For the second level, we have s L → s -and s R → s + , regardless of action taken. For the reward function, R(s + ) = 1 and is 0 otherwise. The policy is parameterized by a single parameter θ such that π(L) = 1 -θ, andπ(R) = θ, such that d π θ 1 (s R ) = d π θ 2 (s + ) = θ.Further, both the offline data and behavior policy are uniform in each level. Consequently, π D 0 (L) = π D 0 (R) = 1 2 and d D 1 = unif(S 1 ). We set C s 1 = C s 2 = 2, and C a 2 = 2 so that πh = π h for all h.Fix θ and estimated occupancies dπ θ and dD . For any s ′ ∈ S 2 we have∇ log d π θ 2 (s ′ ) -∇ log dπ θ 2 (s ′ ) = ∇ dπ θ 1 (s ′ ) 1[ dπ θ 1 (s ′ ) ≤ dD 1 (s ′ )] -1[d π θ 1 (s ′ ) ≤ d D 1 (s ′ )]Next, we instantiate dπ θ , dD for any π θ . The preconditions of the proposition are satisfied by an estimated occupancy with dπ θ 1 (s L ) = θ + ϵ/2 and dπ θ 1 (s R ) = θ -ϵ/2. In addition, we have an estimate dD with dD1 (s L ) = 1/2 -ϵ/2 and dD 1 (s R ) = 1/2 + ϵ/2. We will consider θ = 1/2, so that d π θ 1 ≤ C s 1 d D 1 . However, dπ θ 1 (s L ) > dD 1 (s L ). As a result, ∇ log d π θ 2 (s ′ ) -∇ log dπ θ 2 (s ′ ) = ∇ dπ θ 1 (s ′ ) = O(1)C.2 Proofs for Sec. 4.2First, we formally state and prove the claim that Lem. 4.2 can be reduced to minimizing a squaredloss regression problem recursively over timesteps, i.e.,∇ log d π h+1 (11) = argmin g:S→R p E D h g(s ′ ) -∇ log π 1 π, C a h d D h + ∇ log d π h-1 1 d π h , C s h d D h 2 .This is a reweighted offline analog of Eq. (2) from the online setting, and a more general version is presented below with proof.Lemma C.1. For g : S → R p and f : S × A → R p and reweighting function ρ : S × A → R + , define the offline reweighted squared loss regression objectiveL h (g; f, ρ) = E D h [ρ(s h , a h ) g(s h+1 ) -f (s h , a h ) 2 ].Then for any such f ,E D,ρ h (f ) = argmin g:S→R p L h (g; f, ρ).Further, for the smooth-clipped density ratioρ π h = σ( d π h (s),C s h d D h (s)) d D h (s) π h (a|s) π D h (a|s) and smooth-clipped target function y π h := ∇ log π 1 π, C a h d D h + ∇ log d π h 1 d π h , C s h d D h from Lem. 4.2, we have ∇ log d π h+1 = argmin g:S→R p L h (g; y π h , ρ π h ) .Proof of Lem. B.2. Since the objective is convex, can solve for the minimizer in closed form by taking the derivative and setting it to 0 in an element-wise manner. For each s ′ ,0 = g(s ′ ) s,a P (s ′ |s, a)π D h (a|s)d D h (s)ρ(s, a) - s,a P (s ′ |s, a)π D h (a|s)d D h (s)ρ(s, a)f (s, a).Rearranging and using the definition of E D,ρ h (Eq. ( 5)) gives the result. The second statement follows from Lem. 4.2.Proof of Prop. 4.3 Part 1 follows from the gradient formula∂ x σ (x, c) = x -β-1 x -β + c -β -1/β-1 = 1 + x β c -β -1/β-1 .It can be seen that ∂ x σ (x, c) ∈ [0, 1] and is non-increasing in its inputs, thus σ is monotonic.Additionally, |σ (x, c) -σ (x ′ , c)| ≤ |x -x ′ |.Since σ is symmetric in its arguments, we also have|σ s (x, c) -σ s (x, c ′ )| ≤ |c -c ′ |.Next, we prove Part 2. Let z = (x ∧ c), and observe that z -σ (x, c) ≤ z -σ (z, z) since σ is monotonic. Further,z -σ (z, z) z = z -(2z -β ) -1/β z = 1 -2 -1/β ≤ 1 -e -1/β ≤ 1 β .Rearranging and plugging in the expression for z gives the result.Part 3 can be derived algebraically (but not easily), and is best intuited from the plot of the maximum slope sup x,x ′ ,c,c ′ ∈[0,1] | 1 (x, c) -1 (x ′ , c) |/|x -x ′ | in Figure C.∇ d π h (s ′ ) = s,a P (s ′ |s, a) ∇ π h-1 (a|s) d π h-1 (s) + π(a|s)∇σ d π h-1 (s), C s h-1 d D h-1 (s) = s,a P (s ′ |s, a) π h-1 (a|s)σ d π h-1 (s), C s h-1 d D h-1 (s) ∇ log π h-1 (a|s) + ∇ log σ d π h-1 (s), C s h-1 d D h-1 (s) = s,a P (s ′ |s, a)π D h-1 (a|s)d D h-1 (s) ρ π h-1 (s, a) ∇ log π h-1 (a|s) + ∇ log σ d π h-1 (s), C s h-1 d D h-1 (s) ,where in the last line we use the definition of ρ π h-1 from Lem. 4.2 to make a change-of-measure. Further,∇ log σ d π h-1 (s), C s h-1 d D h-1 (s) = ∇ d π h-1 (s) ∂ x σ d π h-1 (s), C s h-1 d D h-1 (s) = ∇ log d π h-1 (s) d π h-1 (s) • ∂ x σ d π h-1 (s), C s h-1 d D h-1 (s) = ∇ log d π h-1 (s) 1 d π h-1 (s), C s h-1 d D h-1 (s) ,by definition. We can make the analogous statement for ∇ log π h-1 . Next, using the same change of measure in Def. 4.3, we haved π h (s ′ ) = s,a P (s ′ |s, a)π D h-1 (a|s)d D h-1 (s) ρ π h-1 (s, a).The lemma statement follows from ∇ log d π h (s ′ ) = ∇ d π h (s ′ )/ d π h (s ′ ),∇ log d π h (s) ∞ ≤ hG.Proof of Lem. C.2. As a consequence of Asm. 4.1, which states that the gradient of σ is nonincreasing in the first argument, for any x, c ≥ 0 we haveσ (x, c) = x 0 ∂ x σ s (z, c) dz ≥ x 0 ∂ x σ s (x, c) dz = x ∂ x σ (x, c) Then substituting x ← d π h-1 (s) and c ← d D h-1 (s), the above shows that ∇ log σ d π h-1 (s), d D h-1 (s) ≤ ∇ log d π h-1 pointwise. Since Lem. 4.2 involves a valid (conditional) expectation, for any s ∈ S we have∇ log d π h (s ′ ) ∞ ≤ max s,a ∇ log σ π(a|s), C a h-1 π D h-1 (a|s) ∞ + ∇ log σ d π h-1 (s), C s h-1 d D h-1 (s) ∞ ≤ G + max s ∇ log σ d π h-1 (s), C s h-1 d D h-1 (s) ∞ ≤ hGwhere we use Asm. 2.1 in the second line, and unroll the same inequalities through levels in the last line.Proof of Prop. 4.4 First, we bound the difference between the soft-clipped and clipped density functions:d π h -dπ h 1 ≤ σ d π h-1 , C s h-1 d D h-1 -dπ h-1 ∧ C s h-1 d D h-1 1 + max s π h-1 (•|s) -πh-1 (•|s) 1For the second term and any s,π h-1 (•|s) -πh-1 (•|s) 1 = σ π h-1 (•|s), C a h-1 π D h-1 (•|s) -π h-1 (•|s) ∧ C a h-1 π D h-1 (•|s) 1 ≤ D σ π h-1 (•|s) ∧ C a h-1 π D h-1 (•|s) 1 ≤ D σ For the first term, σ d π h-1 , C s h-1 d D h-1 -dπ h-1 ∧ C s h-1 d D h-1 1 ≤ σ d π h-1 , C s h-1 d D h-1 -d π h-1 ∧ C s h-1 d D h-1 1 + d π h-1 ∧ C s h-1 d D h-1 -dπ h-1 ∧ C s h-1 d D h-1 1 ≤ D σ d π h-1 ∧ C s h-1 d D h-1 1 + d π h-1 -d π h-1 1where in the last line we use Asm. 4.1 to upper bound the first term, and the properties of the pointwise minimum ∧ to upper bound the second term. Sinced π h-1 ∧ C s h-1 d D h-1 ≤ d π h-1 ≤ d π h-1 , we have d π h -dπ h 1 ≤ 2D σ + d π h-1 -d π h-1 1 ≤ h(D σ + D σ )after rolling out the induction. Then for any π,J(π) -J(π) ≤ H h=1 d π h -dπ h 1 ≤ 2H 2 D σLastly, let π * = argmax π∈ΠΘ J(π), and define π * similarly. Then J(π * ) -J( π * ) ≤ J(π * ) -J(π * ) ≤ 2H 2 D σ . C.3G h = g h = µ ⊤ Ψ µ ⊤ ψ : Ψ ∈ R k×p , ψ ∈ R k , g h ∞ ≤ hG, ∀h ∈ [H] .Then [E ρ h f ](s ′ ) = s,a P (s ′ |s, a)π D h (a|s)d D h (s, a)ρ(s, a)f (s, a) s,a P (s ′ |s, a)π D h (a|s)d D h (s, a)ρ(s, a)Then since P (s ′ |s, a) = ϕ(s, a), µ(s ′ ) , we can apply the same steps as the proof of Prop. B.1 to show that there exists Ψ ∈ R k×p and ψ ∈ R k such that Proof of Thm. 4.1 For the remainder of this section, we define the constants ε w and ε mle to be the estimation errors of w π and d D , respectively, such that for a given π and any h ∈ [H] we have[E ρ h f ](s ′ ) = µ(s ′ ) ⊤ Ψ µ(s ′ ) ⊤ ψ , ∀s ′ ∈ S.w π h -w π h 1,d D, † h-1 ≤ ε w d D h -d D h 1 ≤ ε mle and d D, † h -d D, † h 1 ≤ ε mle .We can obtain such estimates using Alg. .Next, recall that∇ J(π) = 1 |D grad h | H-1 h=0 (s,a,s ′ )∈D grad h w π h (s ′ )R h (s ′ ) g π h (s ′ ).The expected value over draws of D grad isE D grad h ∇ J(π) = h E s ′ ∼d D, † h-1 [ w π h (s ′ )R h (s ′ ) g π h (s ′ )] .First we bound the statistical error from using samples to approximate ∇ J(π), given the gradient estimate. Fix the other datasets, thenEQUATIONwhere ε stat = HG log(8pH/δ) 2n is obtained by using Hoeffding's with δ ′ = δ/4, since the randomness in w and g are fixed. Then for any p ∈ [p],E D grad h ∇ J(π) -∇ J(π) ≤ h s ′ d D, † h-1 (s ′ )R h (s ′ ) w π h (s ′ ) • g π h (s ′ ) -w π h (s ′ ) • ∇ log d π h (s ′ ) ≤ h s ′ d D, † h-1 (s ′ )R h (s ′ )w π h (s ′ ) g π h (s ′ ) -∇ log d π h (s ′ ) + s ′ d D, † h-1 (s ′ )R h (s ′ ) y π h (s ′ ) ( ŵπ h (s ′ ) -w π h (s ′ )) ≤ √ p h hG w π h -w π h 1,d D, † h-1 + max p∈[p] [ g π h ] p -∇ log d π h 1, d π h (13)The first term is bounded by Thm. E.1. For the second term, we use the following decomposition, which is proved at the end of this section.Lemma C.3 (Gradient estimation error decomposition). Let ε mle and ε w be such that for all h ∈ [h] and π ∈ Π Θ , we haved D h -d D h 1 , d D, † h -d D, † h 1 ≤ ε mle h and w π h -w π h 1,d D, † h-1 ≤ ε w h .Then under Asm. 2.1 and Asm. 4.1, for any p ∈ [p], g π h from Alg. 2 satisfiesg π,p h -∇ p log d π h 1, d π h ≤ 6hC s h-1 C a h-1 L σ G ε mle h-1(data distribution estimation error)+ 3hL σ G ε w h-1(occupancy estimation error)+ g π,p h -[E D, ρ h-1 (∇ log π h-1 + g h-1 )] p 1, d π h (statistical regression error) + g π,p h-1 -∇ p log d π h-1 1, d π h-1 (recursive term)From Lem. C.4, we have[E D, ρ h-1 g h-1 ] p -g π,p h 1, d π h ≤ 2 1 + C s h-1 ε mle h-1 ε reg h + 2hG 2C s h-1 ε mle h-1 + ε w h-1whereε reg h = O( d G C s h-1 C a h-1 h 2 G 2 log(npH/δ) n). Then plugging the above into the decomposition in Lem. C.3, we haveg p h -∇ p log d π h 1, d π h ≤ 10C s h-1 C a h-1 hGL σ ε mle h-1 + 5hGL σ ε w h-1 + 2 1 + C s h-1 ε mle h-1 ε reg h + g p h-1 -∇ p log d π h-1 1, d π h-1Unrolling through timesteps, we haveg p h -∇ p log d π h 1, d π h ≤ 10h 2 GL σ g<h C s g C a g ε mle g + 5h 2 GL σ g<h ε w g + g≤h 2(1 + C s g ε mle g )ε reg g ≤ 10H 2 GL σ h C s h C a h ε mle + 5H 3 GL σ ε w H + h ε reg h √ 2 + C s h ε mle Since ε w H ≤ ( h C s h C a h + 2 h C s h ) ε mle + √ 2 ( h C s h C a h ) ε wreg , g p h -∇ p log d π h 1, d π h ≤ 25H 3 GL σ h C s h C a h ε mle + 5 √ 2H 3 GL σ h C s h C a h ε wreg + h ε reg h √ 2 + C s h ε mleFinally, combining with Eq. ( 12) and upper bounding ε reg further, we have∇ J(π) -∇ J(π) ≤ √ p h C s h C a h ε stat + 25H 3 GL σ ε mle + 5 √ 2H 3 GL σ ε wreg + √ p H √ 2 + ε mle h C s h max h ε reg h ,Combining inequalities and plugging in the expression for each ε, we have∇ J(π) -∇ J(π) ≲ c d G pH 6 G 2 ( h C s h C a h ) 2 L 2 σ log(|W||F|/δ) n .Additional results Lastly, we state and prove the helper lemmas used above.Proof of Lem. C.3. First from Lem. C.1, the population minimizer of Eq. (10) given ρ π , y π h-1 is g π h = ζ π h /f π h , where ζ π h := E ρ h-1 ∇ log π + y π h-1 f π h := E ρ h-1(1) Below, we use superscript p to select the p-th parameter of a gradient object. We first separate out the statistical regression error by decomposing∇ p log d π h -g π,p h 1, d π h ≤ g π,p h -g π,p h 1, d π h + ∇ p log d π h -g π,p h 1, d π hThe first term appears as the regression error in Lem. C.3. Since ∇ logEQUATIONThe error d π h -f π h 1 bounded by Lem. C.5, andg π,p h ∞ ≤ G h ∞ is bounded by Lem. C.2.We will bound the second term above. Lettingy π h-1 := ∇ log σ d π h-1 , C s h-1 d D h-1be the (true) regression target and using the gradient Bellman equation for ∇ log d π h in Lem. 4.2, we haveζ π,p h -∇ p d π h 1 = E ρ h-1 ∇ p log π + y π,p h-1 -E ρ π h-1 ∇ p log π + y π,p h-1 1 ≤ σ( d π h-1 ,C s h-1 d D h-1 ) d D h-1 π h-1 π D h-1 d D h-1 π D h-1 ∇ p log π + y π,p h-1 -σ d π h-1 , C s h-1 d D h-1 π h-1 ∇ p log π + y π,p h-1 1 ≤ σ d π h-1 , C s h-1 d D h-1 ∇ p log π + y π,p h-1 -σ d π h-1 , C s h-1 d D h-1 ∇ p log π + y π,p h-1 1 + C s h-1 G + y π,p h-1 ∞ d D h-1 -d D h-1 1 ≤ σ d π h-1 , C s h-1 d D h-1 y π,p h-1 -σ d π h-1 , C s h-1 d D h-1 y π,p h-1 1 + G σ d π h-1 , C s h-1 d D h-1 -σ d π h-1 , C s h-1 d D h-1 1 + C s h-1 (G + G h-1 ∞ ) d D h-1 -d D h-1 1 ≤ σ d π h-1 , C s h-1 d D h-1 y π,p h-1 -σ d π h-1 , C s h-1 d D h-1 y π,p h-1 1 + G d π h-1 -d π h-1 1 + C s h-1 (2G + G h-1 ∞ ) d D h-1 -d D h-1 1 (15)Now consider the first term above, wherey π h-1 = g π h-1 1 d π h-1 , C s h-1 d D h-1 and y π h-1 = ∇ log d π h-1 1 d π h-1 , C s h-1 d D h-1 .Then plugging this into the first line from the previous block, we haveEQUATION)where we add and subtractσ d π h-1 , C s h-1 d D h-1 1 d π h-1 , C s h-1 d D h-1 g π,ph-1 to obtain the inequality. The first error is the recursive term, so it remains to bound the second, for which we will use the smoothness properties of 1 (x, c) from Asm. 4.1.σ d π h-1 , C s h-1 d D h-1 1 d π h-1 , C s h-1 d D h-1 -σ d π h-1 , C s h-1 d D h-1 1 d π h-1 , C s h-1 d D h-1 1 ≤ σ d π h-1 , C s h-1 d D h-1 1 d π h-1 , C s h-1 d D h-1 -1 d π h-1 , C s h-1 d D h-1 1 + σ d π h-1 , C s h-1 d D h-1 1 d π h-1 , C s h-1 d D h-1 -1 d π h-1 , C s h-1 d D h-1 1 + σ d π h-1 , C s h-1 d D h-1 -σ d π h-1 , C s h-1 d D h-1 1 d π h-1 , C s h-1 d D h-1 1 ≤ L σ σ( d π h-1 ,C s h-1 d D h-1 ) C s h-1 d D h-1 d π h-1 -d π h-1 1 + L σ σ( d π h-1 ,C s h-1 d D h-1 ) d π h-1 d D h-1 -d D h-1 1 + σ d π h-1 , C s h-1 d D h-1 -σ d π h-1 , C s h-1 d D h-1 1 ≤ (L σ + 1) d π h-1 -d π h-1 1 + L σ + C s h-1 d D h-1 -d D h-1 1 (17)Lastly,d π h -d π h 1 ≤ C s C a d D, † h-1 -d D, † h-1 1 + w π h -w π h 1,d D, † h-1 (18)Finally, after combining Eq. ( 14), Eq. ( 15), Eq. ( 16), Eq. ( 17), and Eq. ( 18), we have∇ p log d π h -g π,p h 1, d π h ≤ g π,p h-1 -∇ p log d π h-1 1, d π h-1 + ζ π,p h -g π,p h 1, d π h + (G + (L σ + 1) G h-1 ∞ + G h ∞ ) w π h-1 -w π h-1 1,d D, † h-1 + C s h-1 C a h-1 (G + (L σ + 1) G h-1 ∞ + G h ∞ ) d D, † h-1 -d D, † h-1 1 + 2C s h-1 G + (L σ + C s h-1 ) G h-1 ∞ + G h ∞ d D h-1 -d D h-1 1Plugging in G h ∞ ≤ hG and consolidating terms, gives the result.Lemma C.4. With probability ≥ 1 -δ, for all h ∈ [H] and a fixed π we haveg π h -E D, ρ π h-1 (∇ log π h-1 + g π h-1 ) 1, d π h ≤ 2 1 + C s h-1 ε mle h-1 ε reg h + 2hG 2C s h-1 ε mle h-1 + ε w h-1 (19) Proof. Let f π h (s ′ ) = s,a P (s ′ |s, a) ρ π (s, a)d D h-1 (s)π D (a|s)be the data distribution reweighted by ρ π . For short, we usey π,p h = [E D, ρ π h-1 (∇ log π h-1 + g π h-1 )] p . For any p ∈ [p], g π,p h -y π,p h 1, d π h ≤ g π,p h -y π,p h 1,f π h + g π,p h -y π,p h ∞ • f π h -d π h 1 ≤ f π h 2 • g π,p h -y π,p h 2,f π h + 2hG f π h -d π h 1, where in the second line we use Cauchy-Schwarz on the first term and Lem. C.2 on the second term. Consider the first term. One can loosely boundf π h 2 2 = s,a,s ′ P (s ′ |s, a) ρ π h-1 a)π D h-1 (a|s)d D h-1 (s) ≤ C s h-1 s,a,s ′ P (s ′ |s, a) π h-1 (a|s)d D h-1 (s) ≤ C s h-1 ,or a get a tighter result withf π h 2 2 = s,a,s ′ P (s ′ |s, a) ρ π h-1 (s, a)π D h-1 (a|s)d D h-1 (s) = s,a,s ′ P (s ′ |s, a) σ d π h-1 (s), C s h-1 d D h-1 (s) dD h-1 (s) π h-1 (a|s) d D h-1 (s) -d D h-1 (s) + s,a,s ′ P (s ′ |s, a) π h-1 (a|s)σ d π h-1 (s), C s h-1 d D h-1 (s) ≤ C s h-1 d D h-1 -d D h-1 1 + 1 Next we bound g π,p h -y π,p h 2,f π h . Define L p h-1 (g; y, ρ) = E (s,a,s ′ )∼D h-1 ρ(s, a) (g p (s ′ ) -(∇ log π h-1 (a|s) + y p (s)))2 to be the p-th parameter version of Eq. ( 10). Recall the regression target y π h-1 , then we haveg π,p h -y π,p h 2 2,f π h = E L p h-1 ( g π h ; y π h-1 , ρ π h-1 ) -E L p h-1 (y π h ; y π h-1 , ρ π h-1 ) ≤ 2 L p h-1 ( g π h ; y π h-1 , ρ π h-1 ) -L p h-1 (y π h ; y π h-1 , ρ π h-1 ) + 2ε reg h (Lem. F.2) ≤ 2ε reg h (y π h ∈ G h , Asm. 4.2) Then ŷp h -y p h 1, d π h ≤ 2 1 + C s h-1 d D h-1 -dD h-1 1 ε reg h + 2hG f π h -d π h 1Plugging in the bound from Lem. C.5 for f π h -d π h 1 gives the result.Lemma C.5. For any π and estimates { d π h }, { d D h }, let ρ π be defined as in Alg. 2, and for any h ∈ [H] and s ′ ∈ S definef π h (s ′ ) := s,a P (s ′ |s, a) ρ π (s, a)π D h-1 (a|s)d D h-1 (s),to be the next-state marginal distribution induced by reweighting d D with ρ. We havef π h -d π 1 ≤ 2C s h-1 dD h-1 -d D h-1 1 + dπ h-1 -d π h-1 1 Proof. Using the definition of ρ π , we first rewrite f π h (s ′ ) = s,a P (s ′ |s, a) π h-1 (a|s) σ( d π h-1 (s),C s h-1 d D h-1 (s)) d D h-1 (s) d D h-1 (s). Then f π h -d π h 1 ≤ σ dπ h-1 , C s h-1 d D h-1 d D h-1 d D h-1 -σ d π h-1 , C s h-1 d D h-1 1 ≤ σ d π h-1 , C s h-1 d D h-1 d D h-1 d D h-1 -d D h-1 1 + σ d π h-1 , C s h-1 d D h-1 -σ d π h-1 , C s h-1 d D h-1 1 ≤ 2C s h-1 d D h-1 -d D h-1 1 + d π h-1 -d π h-1 1where in the last inequality we use Asm. 4.1 to bound the second term.We demonstrate that OFF-OCCUPG can converge to a ε-stationary point. In order to establish this result, we will need the guarantee in Thm. 4.1 to hold for all possible policies, i.e., ∇ J(π) -∇ J(π) ≤ ε for all π ∈ Π Θ . This is because the fixed offline data is reused throughout the algorithm, which introduces additional correlations between iterations. In the online setting it was sufficient to simply union bound over iterations, and not functions in our function classes, because we drew fresh trajectories for each policy iterate.Since G and Π Θ are continuous function classes, we will start our result in terms of their covering numbers, defined below. We handle this in the simplest manner by using ℓ ∞ coverings, and leave a more refined analysis to future work. Def. C.1 is a covering on the clipped policy ratio over π D . For example, the direct policy parameterization withπ θ = θ has N D ∞ (γ, Π Θ ) ≤ (max h C a h /γ) HSA (Lem. C.10).In the below definition, we overload the definition of π (the clipped policy in Lem. 4.1) temporarily.Π Θ be an ℓ ∞ covering of Π Θ such that for any π ∈ Π Θ there exists π ∈ Π Θ with σ(π,C a h π D h ) π D h - σ(π h ,C a h π D h ) π D h ∞ ≤ γ. Let N D ∞ (γ, Π Θ ) denote its minimum cardinality. Definition C.2 (Gradient function class γ-cover). Denote N ∞ (γ, G) to be the ℓ ∞ covering number of {G h } with resolution γ.Next, we state the stationary convergence guarantee in terms of these function class complexities, the offline coverage coefficient determined by input clipping constants {C s h , C a h }, and L σ that represents the second-order smoothness of σ. Corollary C.1. Suppose Asm. 3.2 holds. Then under the preconditions of Thm. 4.1, 1 T t E G η (π (t) , ∇ J(π (t) )) 2 ≤ ε when T = O βH ε n = O pH 6 G 2 ( h C s h C a h ) 2 L 2 σ log(N ∞ (ε, G)N D ∞ (ε, Π Θ )|W||F|) ε .E[L π,p h (g; y, ρ) -L π,p h (g * h+1 ; y, ρ)] -L π,p h (g; y, ρ) -L π,p h (g * h+1 ; y, ρ) ≤ 1 2 E[L π,p h (g; y, ρ) -L π,p h (g * h+1 ; y, ρ)] + (ε reg h+1 ) 2 ,whereg * h+1 = E D,ρ h [∇ log π h +y h ] and ε reg h = O C s h-1 C a h-1 h 2 G 2 log(N∞(n -1 ,G)pH|W h ||F h |/δ ′ ) n .To complete the regression part of the analysis we need to take a union bound over the result in Lem. F.3 for all π ∈ Π Θ . For any π ∈ Π Θ , let π ∈ Π Θ of Def. C.1 be its ℓ ∞ cover. We need to bound the covering approximation error L π,p h (g; y, ρ) -L π,p h (g; y, ρ). Consider a fixed (h, s, a, s ′ ) and fix the inputs (g, ρ, y, π), for whichL π,p h (g; y, ρ)[s, a, s ′ ] -L π,p h (g; y, ρ)[s, a, s ′ ] = ρ(s) σ(π(a|s),C a h π D h (a|s)) π D h (a|s) g p (s ′ ) -2(∇ p log π(a|s) + y p (s)) + g * ,p h+1 (s ′ ) g p (s ′ ) -g * ,p h+1 (s ′ ) Then E[L π,p h (g; y, ρ) -L π,p h (g; y, ρ)] -(L π,p h (g; y, ρ) -L π,p h (g; y, ρ)) ≤ 8C s h 2 G 2 σ(π,C a h π D h ) π D h - σ(π,C a h π D h ) π D h ∞ + 8C s C a hG max s,a ∇ log π(a|s) -∇ log [π](a|s) ∞ ≤ 8(C s C a h 2 G 2 + C s C a hGL σ β)εwhere we get smoothness of the gradient portion using Asm. 4.1 and Asm. 3.2. Then by setting ε = (8(C s C a h 2 G 2 + C s C a hGL σ β))n -1 and combining the above errors with Lem. F.3, we have that with probability at least 1 -δ for all π ∈ Π Θ thatE[L p D h (ρ h , g h+1 , y h , π) -L p D h (ρ h , g * h+1 , y h , π)] -L p D h (ρ h , g h+1 , y h , π) -L p D h (ρ h , g * h+1 , y h , π) ≤ 1 2 E[L p D h (ρ h , g h+1 , y h , π) -L p D h (ρ h , g * h+1 , y h , π)] + c C s h-1 C a h-1 h 2 G 2 log(N D ∞ (n -1 , Π Θ )N ∞ (n -1 , G)pH|W h ||F h |/δ) n := ε reg h ,for some absolute constant c. The remainder of the proof is identical to the proof of Thm. 4.1 using the above ε reg h , which is then combined with Lem. G.1 to give the result.We now turn our attention to analyzing gradient domination of the offline objective J(π). The preconditions of our result are written in terms of the smooth-clipped analog of the pessimistic value function Qπ (Prop. 4.1), induced by the smooth-clipped occupancy gradient ∇ d π . For each (h, s, a), defineQ π h (s, a) := ∂ x σ π(a|s), C a h π D h (a|s) s ′ P (s ′ |s, a) R(s ′ ) + ∂ x σ d π h+1 (s ′ ), C s h+1 d D h+1 (s ′ ) Q π h+1 (s ′ , π h+1 ) .Lem. C.6 shows that the optimality gap of a policy for the smooth-clipped objective J(π) is bounded by a measure of its gradient magnitude, as well as a coverage coefficient. This is because our trick with exploratory µ in Lem. 3.2 applicable, as it is not covered by the data in D 0 supported on S 0 . Without this, our offline gradient domination guarantee in Lem. C.6 has a coverage coefficient that resembles the first inequality of Lem. B.3 when µ = d 0 , the original initial state distribution.Lemma C.6. For any π and π ′ , defineB π (π ′ ) := h,s,a d π h (s) π ′ (a|s) Q π h (s, a). Suppose that ∀π ∈ Π Θ ,Proof of Lem. C.6 We will use superscript h to refer to s h ∈ S h , the set of states visitable at timestep h, and drop C s h below to reduce clutter. By the performance difference upper bound for the smooth-clipped objective in Lem. C.8, we haveJ(π * ) -J(π θ ) ≤ H-1 h=0 s,a σ d π * h (s), d D h (s) ( π * (a|s) -π θ (a|s)) Q π θ h (s, a) = H-1 h=0 s h ,a h σ d π * h (s h ), d D h (s h ) π * (a h |s h ) -π θ (a h |s h ) Q π θ h (s h , a h ) since d D h (s) > 0 only if s ∈ S h . Now define π + such that for any s, π + (•|s) = argmax π∈∆(A) π, Q π θ h (s, •) . Then J(π E ) -J(π θ ) ≤ H-1 h=0 s h ,a h σ d π E h (s h ), d D h (s h ) π E (a h |s h ) -π θ (a h |s h ) Q π θ h (s h , a h ) ≤ H-1 h=0 s h ,a h σ d π E h (s h ), d D h (s h ) π + (a h |s h ) -π θ (a h |s h ) Q π θ h (s h , a h ) (20) ≤ max h σ d π E h , C s h d D h σ d π θ h , C s h d D h ∞ H-1 h=0 s h ,a h σ d π θ h (s h ), d D h (s h ) π + (a h |s h ) -π θ (a h |s h ) • 1 π θ (a h |s h ), C a h π D (a h |s h ) Q π θ h (s h , a h ) ≤ max h σ d π E h , C s h d D h σ d π θ h , C s h d D h ∞ H-1 h=0 s h ,a h σ d π θ h (s h ), d D h (s h ) π + (a h |s h ) -π θ (a h |s h ) Q π θ h (s h , a h ) = max h σ d π E h , C s h d D h σ d π θ h , C s h d D h ∞ max π + B π + (π θ ) -B π θ (π θ ) = max h σ d π E h , C s h d D h σ d π θ h , C s h d D h ∞ max π θ ′ ∈ΠΘ B π θ ′ (π θ ) -B π θ (π θ )Proof of Prop. C.2 Under all-policy coverage, we can apply the result in Lem. 3.2, noting that For any C, we have all-policy coverage, i.e., d π h ≤ C h d D h for all h and all policies π. Let π be the stationary (and in this case, optimal) policy of running Alg. 2 withd ′ 0 = 1 H d D h , and d π * h ≤ C s h d D h . S X Y Z P(X | S, a) = ϵ +1/ϵ +1 +0D ′ described in Prop. C.2. Then J(π * ) -J(π) = (1 -ϵ) (1 -2C Y ϵ) . If ϵ is exponentially small, J(π * ) -J(π) = O(1) unless C Y is exponentially large.Proof. The example boils down to a simple bandit problem of choosing either L or R in state X.π(L|X) = C Y d D (Y ) d D (X) = 2C Y ϵ, and π(R|X) = 1 -π(L|X). In comparison, π * (L|X) = 1. Then J(π) = J(π) = C Y d D (Y ) d D (X) + ϵ(1 -π(L|X)). In comparison, J(π * ) = 1, so J(π * ) -J(π) = (1 -ϵ) (1 -2C Y ϵ)For reasonable choices of C Z (say, 2 or 3), C Y must be proportional to ϵ -1 for the suboptimality gap to shrink, and in particular if ϵ is exponentially small then C Y must be exponentially large, which blows up the RHS of the bound.The first step follows the proof of Cor. 3.2. Combining Thm. 4.1 with Lem. G.5 and plugging in above, we haveE 1 T t J(π * ) -J(π (t) ) ≲ BmCC   βH T + pH 6 G 2 ( h C s h C a h ) 2 L 2 σ log(N ∞ (ε, G) N D ∞ (ε, Π Θ )|F||W|) n  Then we also haveE 1 T t J(π * ) -J(π (t) ) ≤ E 1 T t J(π * ) -J(π (t) ) + 2H 2 D σ (Prop. 4.4) ≲ 2H 2 D σ + BmCC   βH T + pH 6 G 2 ( h C s h C a h ) 2 L 2 σ log(N ∞ (ε, G) N D ∞ (ε, Π Θ )|F||W|) n  Additional results Helper lemmas are stated and proved below.Lemma C.7. Suppose σ satisfies Parts 1 and 2 of Asm. 4.1. Then forJ(π) = h s d π h (s)R h (s), ∇ J(π) = H-1 h=0 s,a σ d π h (s), C s h d D h (s) ∇ π h (a|s) Q π h (s, a),whereQ π h (s, a) = s ′ P h (s ′ |s, a) R h+1 (s ′ ) + a ′ π h+1 (a ′ |s ′ ) ∂ x σ d π h+1 (s ′ ), C s h+1 d D h+1 (s ′ ) Q π h+1 (s ′ , a ′ ) .Proof of Lem. C.7. For notational clarity we omit C s h below. Expanding ∇ d π , we have∇ d π h (s h ) = s h-1 ,a h-1 P (s h |s h-1 , a h-1 ) ∇ π h-1 (a h-1 |s h-1 )σ d π h-1 (s h-1 ), d D h-1 (s h-1 ) + π h-1 (a h-1 |s h-1 ) ∂ x σ d π h-1 (s h-1 ), d D h-1 (s h-1 ) ∇ d π h-1 (s h-1 ) = g<h (s h-1 ,a h-1 ,...,sg,ag) h-1 t=g+1 P (s t+1 |s t , a t ) π t (a t |s t ) ∂ x σ d π t (s t ), d D t (s t ) • P (s g+1 |s g , a g )σ d π g (s g ), d D g (s g ) ∇ π g (a g |s g )For short, defineP π (s h |s g , a g ) := (s h-1 ,a h-1 ,...,sg+1,ag+1) h-1 t=g+1 P (s t+1 |s t , a t ) π t (a t |s t ) ∂ x σ d π t (s t ), d D t (s t ) P (s g+1 |s g , a g ) observing if π h = π h and ∂ x σ d π h , d D h= 1 for all h, we have P π (s h |s g , a g ) = P π (s h |s g , a g ), the standard transition kernel from (s g , a g ) → s h . This occurs, for example, when σ s is hard clipping and π is fully covered by data. Then using the above definition, we haveEQUATIONPlugging this expression into ∇J(π), we obtain∇J(π) = h s h ∇ d π h (s h )R(s h ) = h s h   h-1 g=0 sg,ag σ d π g (s g ), d D g (s g ) ∇ π g (a g |s g ) P π (s h |s g , a g )   R(s h ) = H-1 g=0 sg,ag σ d π g (s g ), d D g (s g ) ∇ π g (a g |s g )   H h=g+1 s h P π (s h |s g , a g )R(s h )   = H-1 g=0 sg,ag σ d π g (s g ), d D g (s g ) ∇ π g (a g |s g ) Q π (s g , a g )where we have defined Q π g (J(π ′ ) -J(π) ≤ H-1 h=0 s,a σ d π ′ h (s), d D h (s) ( π ′ h (a|s) -π h (a|s)) Q π h (s, a),where Q π h is defined in Lem. C.7.Proof. This statement follows straightforwardly from plugging in Lem. C.9 and rearranging, similar to the proof of Lem. C.7.Lemma C.9. If σ is concave in its their first arguments, then for any h and π, π′ d π ′ h (s ′ ) -d π h (s ′ ) ≤ g<h s,a σ d π ′ g (s), d D g (s) σ π ′ g (a|s), π D g (a|s) -σ π g (a|s), π D g (a|s) P π (s h = s ′ |s g = s, a g = a),whereP π (s h |s g , a g ) := s h-1:g+1 ,a h-1:g+1 h-1 t=g+1 P (s t+1 |s t , a t ) π t (a t |s t ) ∂ x σ d π t (s t ), d D t (s t ) P (s g+1 |s g , a g ).Proof of Lem. C.9. Define π g = {π ′ 1 , . . . , π ′ g-1 , π g , . . . , π H-1 }, i.e., a policy that starts playing π at timestep g, and plays π ′ for the timesteps before that.d π ′ h (s ′ ) -d π h (s ′ ) = d π ′ h (s ′ ) -d π h-1 h (s ′ ) + d π h-1 h (s ′ ) -d π h (s ′ )For the first pair of terms, π ′ and π h-1 only differ the policy used to take the action a h-1 (and both play π ′ before that), thusd π ′ h-1 = d π h-1 h-1 and d π ′ h (s ′ ) -d π h-1 h (s ′ ) = s,a P (s ′ |s, a) σ π ′ h-1 (a|s), π D h-1 (a|s) -σ π h-1 (a|s), π D h-1 (a|s) σ d π ′ h-1 (s), d D h-1 (s)For the second pair of terms, π h-1 and π both play π at time h -1, but the former uses π ′ for timesteps 1, . . . , h -2:d π h-1 h (s ′ ) -d π h (s ′ ) = s,a P (s ′ |s, a)σ π h-1 (a|s), π D h-1 (a|s) σ d π h-1 h-1 (s), d D h-1 (s) -σ d π h-1 (s), d D h-1 (s) = s,a P (s ′ |s, a)σ π h-1 (a|s), π D h-1 (a|s) σ d π ′ h-1 (s), d D h-1 (s) -σ d π h-1 (s), d D h-1 (s) ≤ s,a P (s ′ |s, a)σ π h-1 (a|s), π D h-1 (a|s) ∂ x σ d π h-1 (s), d D h-1 (s) d π ′ h-1 (s) -d π h-1 (s)where the last inequality above uses the concavity of σ s in the first argument (recall concave functions f satisfy f (y) ≤ f (x) + f ′ (x)(y -x)). Combining the above two inequalities, we have the recursive relationshipd π ′ h (s ′ ) -d π h (s ′ ) ≤ s,a P (s ′ |s, a) σ π ′ h-1 (a|s), π D h-1 (a|s) -σ π h-1 (a|s), π D h-1 (a|s) σ d π ′ h-1 (s), d D h-1 (s) + σ π h-1 (a|s), π D h-1 (a|s) ∂ x σ d π h-1 (s), d D h-1 (s) d π ′ h-1 (s) -d π h-1 (s)Unrolling through timesteps gives the lemma statement.Lemma C.10. Let C a = max h C a h . Suppose Π Θ is the direct policy parameterization, i.e., π θ (a|s) = θ s,a , and σ is such that D σ ≤ C a for all h. Then for any γ ∈ (0, 1], in Def. C.1 we haveN D ∞ (γ, Π Θ ) ≤ (C a /γ) SAH .Proof of Lem. C.10. Typical gridding-style arguments discretize the range of π(a|s) for each (s, a). Since we are concerned with creating a cover for the policy ratio, however, a naive argument will incur 1/ min s,a π D (a|s) in the grid's cardinality. Our solution is to grid Π Θ adaptively according to the magnitude of π D (a|s). Intuitively, we only need to grid up to the threshold For each (h, s, a), define the adaptive gridding scale to be γ ′ hsa = γπ D h (a|s). For any π ∈ Π Θ , set its cover π as follows. π h (a|s) = π(a|s) γ ′ hsa , if π(a|s) ≤ C a h π D h (a|s), C a h π D h (a|s), otherwise. Let Π Θ = {π : π ∈ Π Θ }. Then |Π Θ | ≤ (max h C a h /γ) HSA . Further, π(a|s) ∧ C a h π D h (a|s) -π h (a|s) ∧ C a h π D h (a|s) ≤ γπ D h (a|s), thus (π∧C a h π D h )-(πh∧C a h π D h ) π D h ∞ ≤ γ,d D h-1 = argmax d h-1 ∈F h-1 1 |D h-1 | (s,•,•)∈D h-1 log (d h-1 (s)) (22) d D, † h-1 = argmax d h ∈F h 1 |D h-1 | (•,•,s ′ )∈D h-1 log (d h (s ′ )) . 3: end for Output: estimated data distributions { d D h } h∈[H] and { d D, † h } h∈[H]≤ Cγπ D (a|s). Algorithm 4 displays the data distribution estimation procedure used in offline gradient estimation (Algorithm 2), which is a direct application of The general formulation of the MLE problem utilized in this paper is to estimate a probability distribution over the instance space S. Given an i.i.d. sampled dataset D = {s (i) } n i=1 and a function class F, we optimize the MLE objective of the formEQUATION)We assume F is finite, and refer readers to [LNSJ23; HCJ23] for techniques for handling infinite function classes. The general MLE guarantee is stated below, and is a well-established result (for example, a proof can be found in Appendix E of [AKKS20] ).Lemma D.1 (MLE guarantee). Let D = {s (i) } n i=1 be a dataset, where s (i) are drawn i.i.d. from some fixed probability distribution f * over S. Consider a function class F that satisfies: (i) f * ∈ F , and (ii) each function f ∈ F is a valid probability distribution over S (i.e., f ∈ ∆(S)) Then with probability at least 1 -δ, f from Eq. (23) has ℓ 1 error guaranteef -f * 1 ≤ 2 log(|F|/δ) n .The formal guarantee of Algorithm 4 is stated below, which is a straightforward application of Lemma D.1 with union bound (over all functions in F, and over all timesteps). Define L D h-1 (w h , w h-1 , π h-1 ) := 1 |D h-1 | (s,a,s ′ )∈D h-1 w h (s ′ ) -w h-1 (s) π h-1 (a|s) π D h-1 (a|s) 2, and estimateEQUATIONSet the estimate d π h = w π h d D, † h-The algorithm for offline density estimation is displayed in Alg. 5, and is directly copied from Algorithm 1 of [HCJ23] , but with two minor modifications. The first is that the densities are clipped using a function σ, that can take clipping as a special case. The second is that it outputs the learned weights instead of the learned densities. The weight function class completeness assumption is shown Asm. E.1, and is satisfied in low-rank MDPs using linear-over-linear function classes that have pseudo-dimension bounded by MDP rank. It can be seen as a 1-dimensional version of Asm. 4.2 where ρ = 1 and in that sense strictly weaker. Assumption E.1 (Weight function completeness). For any π ∈ Π Θ and h ∈ [H], we have E D,1 h-1 σ(w•f ′ ,C s h-1 f ) f π h-1 π D h-1 ∈ W h , ∀w ∈ W h-1 , ∀f, f ′ ∈ F h-1 , Theorem E.d D h -d D h 1 ≤ ε mle and d D, † h -d D, † h 1 ≤ ε mle .Then with probability at least 1 -δ, the outputs { w π h } of Algorithm 5 satisfy for all h ∈ [H]EQUATION)where ε wreg := c log(H|W|/δ) nreg for some absolute constant c.Proof of Theorem E.1 We begin by stating the following decomposition on the error of w π h , which is proved at the end of this section. Lemma E.1. Suppose σ satisfies Assumption 4.1. Then for any h ∈ [H], the error between w π h and the target w π h = d π h /d D, † h-1 can be recursively decomposed asw π h -w π h 1,d D, † h-1 ≤ w π h-1 -w π h-1 1,d D, † h-2 + 2C s h-1 d D h-1 -d D h-1 1 + C s h-2 C a h-2 d D, † h-2 -d D, † h-2 1 + w π h -E π h-1 d D h-1 ω π h-1 2,d D, † h-1,where ω π := σ( d π h-1 ,C s h-1 d D h-1 ) d D h-1 .Applying Lem. E.2 with union bound over all h, we havew π h -E π h-1 d D h-1 ω π h-1 2 2,d D, † h-1 = E L D reg h-1 w π h , ω π h-1 , π -E L D reg h-1 E π h-1 d D h-1 ω π h-1 , ω π h-1 , π ≤ 2 L D reg h-1 w π h , ω π h-1 , π -L D reg h-1 E π h-1 d D h-1 ω π h-1 , ω π h-1 , π + 2 C s h-1 C a h-1 2 (ε wreg ) 2 ,Then unrolling Lemma E.1, for any h, we have for ε wreg = c log(H|W|n/δ) nreg , w π h -w π h 1,d D, † h-1 ≤   g<h-1 C s g C a g + 2 g<h C s g   ε mle + √ 2   g<h C s g C a g   εE L D reg h (w h+1 , w h , π) -L D reg h (E π w h , w h , π) -L D reg h (w h+1 , w h , π) -L D reg h (E π w h , w h , π) ≤ 1 2 E L D reg h (w h+1 , w h , π) -L D reg h (E π h w h , w h , π) + c(C s h C a h ) 2 log (H|W|/δ) n reg . Proof of Lemma E.1. Decompose w π h -w π h 1,d D, † h-1 ≤ w π h -E π h-1   d D h-1 σ d π h-1 , C s h-1 d D h-1 d D h-1   2,d D, † h-1 + w π h -E π h-1   d D h-1 σ d π h-1 , C s h-1 d D h-1 d D h-1   1,d D, † h-1The first term is the statistical error of regression. The second term reflects the bias between the population regression solution (involving plug-in estimates for the regression target) and our target weight function. Sinced π h = P h-1 σ d π h-1 , C s h-1 d D h-1 , then w π h = E h-1 σ d π h-1 , C s h-1 d D h-1, for the second term we havew π h -E π h-1   d D h-1 σ d π h-1 , C s h-1 d D h-1 d D h-1   1,d D, † h-1 = E h-1 σ d π h-1 , C s h-1 d D h-1 -E π h-1   d D h-1 σ d π h-1 , C s h-1 d D h-1 d D h-1   1,d D, † h-1 = P h-1 σ d π h-1 , C s h-1 d D h-1 -P π h-1   d D h-1 σ d π h-1 , C s h-1 d D h-1 d D h-1   1 ≤ σ d π h-1 , C s h-1 d D h-1 -d D h-1 σ d π h-1 , C s h-1 d D h-1 d D h-1 1 ≤ C s h-1 d D h-1 -d D h-1 1 + σ d π h-1 , C s h-1 d D h-1 -σ d π h-1 , C s h-1 d D h-1 1 ≤ 2C s h-1 d D h-1 -d D h-1 1 + d π h-1 -d π h-1 1 (Assumption 4.1) Finally, since d π h-1 = w π h-1 d D, † h-2 , d π h-1 -d π h-1 1 = w π h-1 d D, † h-2 -w π h-1 d D, † h-2 1 ≤ C s h-2 C a h-2 d D, † h-2 -d D, † h-2 1 + w π h-1 -w π h-1 1,d D, † h-2Combining the inequalities completes the proof.Definition F.1 (Pseudodimension). Suppose a function class F ⊆ R X , andx n 1 = {x i } n i=1 ∈ X n . We say x n 1 is pseudo-shattered by F if there exists v ∈ R n such that for all y ∈ {-1, +1} n , there exists f ∈ F such that sign(f (x n 1 -c)) = y. The pseudo-dimension of F is defined as d F = max{n ∈ N : ∃x n 1 ∈ X n s.t.x n 1 is pseudo-shattered by F}, i.e., the cardinality of the largest set of points in X that F pseudo-shatters. Lemma F.1 (Lemma 26 from [HCJ23] ). For b ≥ 1, let H ⊆ (Z → [-b, b]) be a hypothesis class and Z n = (z 1 , . . . , z n ) ∈ Z n , where z i are iid samples drawn from a distribution supported on Z. Then for any h ∈ H, we have Then with probability at least 1 -δ, for all g h+1 ∈ G h+1 and p ∈ [p] and h ∈ [H], we haveP E[h(z)] - 1 n i h(z i ) > ε ≤ 36N 1 ε 3 640b , H, 40nb 2 ε 2 exp - nε 2 128V[h(z)] + 512εb Lemma F.2. Fix π. For any h ∈ [H], consider functions y h : S × A → [-hG, hG] p and ρ h : S × A → [0, C s h C a h ]E[L π,p h (g h+1 ; y h , ρ h ) -L π,p h (g * h+1 ; y h , ρ h )] -L π,p h (g h+1 ; y h , ρ h ) -L π,p h (g * h+1 ; y h , ρ h ) ≤ 1 2 E[L π,p h (g h+1 ; y h , ρ h ) -L π,p h (g * h+1 ; y h , ρ h )] + (ε reg h+1 ) 2 ,where g * h+1 = E D,ρ h (∇ log π h + y h ) and for some absolute constant c,EQUATION)Proof. Fix D mle <h and D FORC <h and D grad <h . We first prove the stated bound conditioned on these datasets, which means g π h and ρ π h are fixed, and the randomness below comes from random draws of D grad h . Consider the following hypothesis class induced by G h+1 :Z(ρ h , g h+1 , y h ) = ρ h (s, a) (g h+1 (s ′ ) -y h (s, a)) 2 -g * h+1 (s ′ ) -y h (s, a) 2 : g h+1 ∈ G h+1 .and for any Z ∈ Z, we have|Z| ≤ 2C s h C a h g h+1 2 ∞ + y h 2 ∞ ≤ 4C s h C a h h 2 G 2 . We also have E[Z p (ρ, g h+1 , y h )] = y p h+1 -g * ,p h+1 2 2,f π h . Further, V [Z p (ρ h , g h+1 , y h )] ≤ E[Z p (ρ h , g h+1 , y h ) 2 ] = E ρ h (s, a) 2 g p h+1 (s ′ ) -y h (s, a) 2 -g * ,p h+1 (s ′ ) -y h (s, a) 2 2 = E ρ h (s, a) 2 g p h+1 (s ′ ) -2y h (s, a) + g * ,p h+1 (s ′ ) 2 g p h+1 (s ′ ) -g * ,p h+1 (s ′ ) 2 ≤ 16C s h C a h h 2 G 2 E ρ h (s, a) g p h+1 (s ′ ) -g * ,p h+1 (s ′ ) 2 = 16C s h C a h h 2 G 2 E[Z p (ρ h , g h+1 , y h )]Next, we show that the uniform covering number of Z can be bounded by the uniform covering number of G, since for any g h+1 , g ′ h+1 ∈ G h+1 we haveZ p (ρ h , g h+1 , y h ) -Z p (ρ h , g ′ h+1 , y h ) = ρ h (s, a) (g h+1 (s ′ ) -y h (s, a)) 2 -(g ′ h+1 (s ′ ) -y h (s, a)) 2 ≤ 16C s h C a h (h + 1) 2 G 2 |g h+1 (s ′ ) -g ′ h+1 (s ′ )| In other words, any γ/16C s h-1 C a h-1 h 2 G 2 covering of G h is a covering of Z h .Then combining the above with Lem. F.1, we haveP E[Z p (ρ h-1 , g h , y h-1 )] - 1 n i Z p i (ρ h-1 , g h , y h-1 ) > ε ≤ 36N 1 ε 3 10240C s h C a h h 2 G 2 , Z(G h , ρ h-1 , y h-1 ), 640n(C s h-1 C a h-1 ) 2 h 4 G 4 ε 2 • exp - nε 2 2048C s h-1 C a h-1 h 2 G 2 E[Z p (ρ h-1 , g h , y h-1 , π)] + 2048εC s h-1 C a h-1 h 2 G 2 ≤ 36N 1 ε 3 163840(C s h C a h ) 2 h 4 G 4 , G h , 640n(C s h-1 C a h-1 ) 2 h 4 G 4 ε 2 • exp - nε 2 2048C s h-1 C a h-1 h 2 G 2 E[Z p (ρ h-1 , g h , y h-1 )] + 2048εC s h-1 C a h-1 h 2 G 2 Define N := N 1 ε 3 163840(C s h C a h ) 2 h 4 G 4 , G h , 640n(C s h-1 C a h-1 ) 2 h 4 G 4 ε 2. Then setting the RHS equal to δ ′ , this implies thatn = 2048C s h-1 C a h-1 h 2 G 2 (E[Z p (ρ h-1 , g h , y h-1 )] + ε) log (36N/δ ′ ) ε 2 and ε ≤ 2048C s h-1 C a h-1 h 2 G 2 E[Z p (ρ h-1 , g h , y h-1 )] log(36N/δ ′ ) n + 2048C s h-1 C a h-1 h 2 G 2 log(36N/δ ′ ) n . Since n ≥ 2048C s h-1 C a h-1 h 2 G 2 ε , there exists an absolute constant c such that log(36N/δ ′ ) ≤ cd G log(n/δ ′ ). Then with probability at least 1 -δ ′ , E[Z p (ρ h-1 , g h , y h-1 )] - 1 n i Z p i (ρ h-1 , g h , y h-1 ) ≤ 2048cd G h C s h-1 C a h-1 h 2 G 2 E[Z p (ρ h-1 , g h , y h-1 )] log(n/δ ′ ) n + 2048cd G C s h-1 C a h-1 h 2 G 2 log(n/δ ′ ) n ≤ 1 2 E[Z p (ρ h-1 , g h , y h-1 )] + 3072cd G C s h-1 C a h-1 h 2 G 2 log(n/δ ′ ) nSince the above bound holds for a fixed datasets, it also holds for the expectation over the datasets. Applying the above bound for all p ∈ [p] and h ∈ [H] with δ ′ = δ/Hp and taking the union bound, then plugging in the definition of Z p , gives the result.Y h × P h = (y, ρ) : y = g 1 (wf ′ , C s h f ) , ρ = σ(wf ′ ,C s h f ) f , g h ∈ G h , w ∈ W h , f ∈ F h+1 , f ′ ∈ F h .Fix π and p ∈ [p], and define the loss functionL π,p h (g; y, ρ) = 1 n (s,a,s ′ )∈D h ρ(s) σ(π(a|s),C a h π D h (a|s)) π D h (a|s) (g p (s ′ ) -(∇ p log π(a|s) + y p (s))) 2 .Then with probability at least 1 -δ, for all h ∈ [H], p ∈ [p] and g ∈ G h+1 , (y, ρ) ∈ Y h × P h , we haveE[L π,p h (g; y, ρ) -L π,p h (g * h+1 ; y, ρ)] -L π,p h (g; y, ρ) -L π,p h (g * h+1 ; y, ρ) ≤ 1 2 E[L π,p h (g; y, ρ) -L π,p h (g * h+1 ; y, ρ)] + (ε reg h+1 ) 2 , where g * h+1 = E D,ρ h (∇ log π h + y h ) and ε reg h = O C s h-1 C a h-1 h 2 G 2 log(N∞(n -1 ,G)pH|W||F |/δ) n .Proof of Lem. F.3. Use the same notation for Z p as in the proof of Lem. F.2. Using Bernstein's inequality with a union bound over all W h and F h and the ℓ ∞ covers of G h , G h+1 , with probability at least 1 -δ we haveE[Z p (ρ h , g h+1 , y h )] - 1 n n i=1 Z p i (ρ h , g h+1 , y h ) ≤ 2V [Z p (ρ h , y h+1 , g h )] log(|W||F|N ∞ (ε, G)/δ) n + 4C s h C a h h 2 G 2 log(|W||F|N ∞ (ε, G)/δ) 3n ≤ 32C s h C a h h 2 G 2 E[Z p (ρ h , y h+1 , g h )] log(|W||F|N ∞ (ε, G)/δ) n + 4C s h C a h h 2 G 2 log(N ∞ (ε, G)|W||F|/δ) 3nBy accounting for the ℓ ∞ covering error, we then haveE[Z p (ρ h , g h+1 , y h )] - 1 n n i=1 Z p i (ρ h , g h+1 , y h ) ≤ 32C s h C a h h 2 G 2 E[Z p (ρ h , g h+1 , y h )] log(|W||F|N ∞ (ε, G)/δ) n + 4C s h C a h h 2 G 2 log(N ∞ (ε, G)|W||F|/δ) 3n + 16C s h C a h h 2 G 2 ε Using the AM-GM inequality with ε = O(1/C s h C a h h 2 G 2 n) gives the result.Definition G.1 (Gradient mapping).EQUATION)Lemma G.1 (Stationary convergence of PGD). Suppose f : X → R is β-smooth over X , a nonempty closed and convex set, and that we have access to a gradient oracle such that E[g(x)|x] = ∇f (x) and E[ g(x) -∇f (x) 2 |x] ≤ ε 2 . Then if η = 1/β, we have 1 T t E G η (x (t) , ∇f (x (t) )) 2 ≤ 4β(f 0 -f * ) T + 6ε 2Proof. For any x, define x + = Proj X (x -ηg(x)). Since x + = prox •,I X (x -ηg(x)), where I X is the indicator function for the set X , from Lem. G.2 we havex -ηg(x) -x + , x -x + ≤ 0.Rearranging, this impliesg(x), x + -x + 1 η x -x + 2 ≤ 0.Next, since f is β-smooth, for any x and x + we havef (x + ) ≤ f (x) + ∇f (x), x + -x + β 2 x -x + 2 = f (x) + g(x), x + -x + ∇f (x) -g(x), x + -x + β 2 x -x + 2 ≤ f (x) + η g(x) -∇f (x), G η (x, g(x)) + η 2 β 2 -η G η (x, g(x)) 2 = f (x) + η g(x) -∇f (x), G η (x, ∇f (x)) + η g(x) -∇f (x), G η (x, g(x)) -G η (x, ∇f (x)) + η 2 β 2 -η G η (x, g(x)) 2where we substitute the definition of G η (x, g(x)) = 1 η (x -x + ) in the the second to last line. Notice thatg(x) -∇f (x), G η (x, g(x)) -G η (x, ∇f (x)) ≤ g(x) -∇f (x) G η (x, g(x)) -G η (x, ∇f (x)) ≤ g(x) -∇f (x) 2from the non-expansion of the projection operator. Then we havef (x + ) ≤ f (x) + η g(x) -∇f (x), G η (x, ∇f (x)) + η g(x) -∇f (x) 2 + η 2 β 2 -η G η (x, g(x)) 2Next, we take the expectation of both sides conditioned on x.E[f (x + )|x] ≤ f (x) + η E[g(x)|x] -∇f (x), G η (x, ∇f (x)) + ηE[ g(x) -∇f (x) 2 |x] + η 2 β 2 -η E[ G η (x, g(x)) 2 |x] ≤ f (x) + ηε 2 + η 2 β 2 -η E[ G η (x, g(x)) 2 |x]Then unrolling the recursion through iterations and substituting η = 1/β, we have1 T t E[ G η (x (t) , g(x (t) )) 2 ] ≤ 2β(f (x (0) ) -f (x (T ) )) T + 2ε 2 ≤ 2β(f (x (0) ) -f (x * )) T + 2ε 2 if f is nonnegative. Lastly, 1 T t E[ G η (x (t) , ∇f (x (t) )) 2 ] = 1 T t E[ G η (x (t) , g(x (t) ) -G η (x (t) , g(x (t) ) + G η (x (t) , ∇f (x (t) )) 2 ] ≤ 2 T t E[ G η (x (t) , g(x (t) ) 2 + 2 T t E[ G η (x (t) , g(x (t) ) -G η (x (t) , ∇f (x (t) )) 2 ] ≤ 4β(f (x (0) ) -f (x * )) T + 4ε 2 + 2 T t E[ g(x (t) ) -∇f (x (t) ) 2 ] ≤ 4β(f (x (0) ) -f (x * )) T + 6ε 2Lemma G.2 (Theorem 6.39 from [Bec17] ). Let g : E → (∞, ∞] be a proper closed and convex function. Then for any x, y ∈ E, the following three claims are equivalent:1. y = prox g (x)2. x -y ∈ ∂g(u)3. x -y, u -y ≤ g(u) -g(y) for any u ∈ E Lemma G.3. Suppose f is M -gradient dominated and β-smooth, and1 T t G η (x (t) , ∇f (x (t) )) 2 ≤ ε 2 ,where G η (x, g) is the gradient mapping defined in Def. G.1. Also, suppose x -x ′ 2 ≤ r for all x, x ′ ∈ X . Then mint∈[T ]f (x * ) -f (x (t) ) ≤ rM (ηβ + 1)ε.(28)Proof of Lemma G.3. If f is gradient dominated, for any t ∈ [T ] we havef (x * ) -f (x (t) ) ≤ M max x ′ ∈X ∇f (x (t) ), x ′ -x (t) .Applying Lemma G.4 with -f , we have ∇f (x (t) ) ∈ N X (x (t) ) + B (ηβ + 1) G η (x (t-1) , ∇f (x (t-1) ))From the definition of the normal cone, we have v, x ′ -x (t) ≤ 0 for any v ∈ N X (x (t) ) and x ′ ∈ X . Then for any x ′ ∈ X , ∇f (x (t) ), x ′ -x (t) ≤ (ηβ + 1) G η (x (t-1) , ∇f (x (t-1) )) x -x (t) ≤ (ηβ + 1)r G η (x (t-1) , ∇f (x (t-1) ))Combining the above inequalities, G η (x (t-1) , ∇f (x (t-1) )) ≤ (ηβ + 1)M rε.Lemma G.4 (Lemma 3 from [GL16] ). Let f : R d → (-∞, ∞) be be β-smooth over a convex set X For any t ∈ [T ], consider x (t+1) = Proj X x (t) -η∇f (x (t) ) . Then -∇f (x (t+1) ) ∈ N X (x (t+1) ) + B (ηβ + 1) G η (x (t) , -∇f (x (t) ) ,where N X is the normal cone of X and B(r) = {x ∈ R d : x 2 ≤ r}.Proof of Lemma G.4. Projected gradient descent can be equivalently written as [Bec17] Proj X x (t) -η∇f (x (t) ) = argminx∈R d f (x (t) ) + ∇f (x (t) ), x -x (t) + 1 2η x -x (t) 2 2 + I X (x) ,where I X (x) = 0 if x ∈ X , and +∞ otherwise, is the indicator function for X . Then by the subgradient optimality condition, we have 0 ∈ ∇f (x (t) ) + 1 η (x (t+1) -x (t) ) + N X (x (t+1) ) With some rearrangement, this implies that -∇f (x (t+1) ) ∈ N X (x (t+1) ) + ∇f (x (t) ) -∇f (x (t+1) ) + 1 η (x (t+1) -x (t) ) which implies the lemma statement since ∇f (x (t) ) -∇f (x (t+1) ) + 1 η (x (t+1) -x (t) ) ≤ β x (t) -x (t+1) + 1 η x (t) -x (t+1) ≤ (ηβ + 1) G η (x (t) , ∇f (x (t) )) using the β-smoothness of f in the first inequality, and Definition G.1 in the second.Lemma G.5. Suppose f is β-smooth and that at each iteration t, we have g (t) from a gradient oracle such that E g (t) |x (t) = ∇f (x (t) ) and E ∇f (x (t) ) -g (t) 2 |x (t) ≤ ε 2 for all t ∈ [T ]. Then gradient ascent using {g (t) } satisfiesEQUATION)Proof of Lem. G.5. From the β-smoothness of f , f (x (t+1) ) ≤ f (x (t) ) + ∇f (x (t) ), x (t+1) -x (t) + β 2 x (t+1) -x (t) 2= f (x (t) ) -η ∇f (x (t) ), g (t) + βη 2 2 g (t) 2= f (x (t) ) -η ∇f (x (t) ), ∇f (x (t) ) -∇f (x (t) ) + g (t) + βη 2 2 ∇f (x (t) ) -∇f (x (t) ) + g (t) 2= f (x (t) ) + βη 2 2 -η ∇f (x (t) ) 2 + βη 2 -η ∇f (x (t) ), g (t) -∇f (x (t) ) + βη 2 2 ∇f (x (t) ) -g (t) 2Taking the expectations of both sides conditioned on x (t) (prior histories), we haveE[f (x (t+1) )|x (t) ] ≤ f (x (t) ) + βη 2 2 -η ∇f (x (t) ) 2 + βη 2 ε 2 2Substituting η = 1/β, unrolling through iterations, and using the law of total expectation gives the result.(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.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.This means that trajectories are generated by first sampling the initial state s1 ∼ ν, then rolling out the policy according to the true MDP's dynamics. 


Decision: In this paper on policy gradient for finite-horizon MDPs with general function approximation, the authors propose a novel approach based on the estimation of the gradients of occupancy measures.
Under (variants of) standard assumptions, they establish iteration and sample complexity upper bounds for finding stationary points and optimal policies. They also consider nonlinear performance functionals and the offline learning setting.

The reviewers agree on the originality and the soundness of the proposed approach. Indeed, although occupancy measures have been employed before in the PG literature (as discussed in appendix A of the paper), the perspective presented here is new and leads to a satisfying compromise between sample and computational complexity.

The reviewers also raised some important issues, especially regarding presentation, that were mostly solved in the discussion phase. 
Indeed, the paper is very dense and some parts need polishing.
I stress the importance of incorporating the fixes and clarifications in the revised manuscript. I will summarize the most important ones below, but solving the several minor issues pointed out by the reviewers is also important to improve overall clarity:

- Add a comparison with existing results from the PG literature, as suggested by Reviewer K5ET. Regarding this, I suggest to include the following simple but important observation: Alg. 1 needs a total of O(\epsilon^{-4}) samples to find an approximate stationary point with (not squared!) gradient norm smaller than epsilon, the same as REINFORCE (Yuan et al. 2022, "A general sample complexity analysis of vanilla policy gradient").

- Expand on the motivation of using an occupancy-based approach compared to more standard PG methods, as suggested by Reviewer K5ET

- Use the extra space to make the theory more self-contained, as suggested by Reviewer n45j

Additionally, as pointed out by Reviewer n45j in the discussion phase, the low-rank MDP example is a bit misleading. In low-rank MDPs, one typically assumes to know state-action features, while $\mu(s')$ is unknown. The alternative setting proposed here should be motivated better, or the authors should acknowledge that the completeness assumption may be a strong one.

I also suggest to add a few words on possible infinite-horizon extensions.

Regarding the concern of Reviewer 2KwR on concentrability coefficients, I agree with the authors that it is misdirected, as it applies to a significant part of the PG theory literature. However, I suggest to add a paragraph on the meaning of "exploration" to avoid further misunderstandings, as proposed in the authors' response.

Overall, I think that this paper would be interesting for the community and will be ready for publication after implementing the fixes suggested by the reviewers and summarized here, which I think can be reasonably done for the camera ready version.

Reviews: review: paper_summary: paper_summary: This paper investigates the convergence of model-free policy gradient (PG) methods that compute the gradient through occupancy.
strength_weakness: strength_weakness: In my opinion, the paper makes overclaims. The convergence depends on a coverage coefficient, which removes the need for exploration. Therefore, the obtained bound does not indicate the number of samples needed for exploration when the initial policy is not good. Additionally, the proposed algorithm does not address the problem of exploration.
questions: questions: See the 'Weakness' part.
limitations: limitations: See the 'Weakness' part.
paper_summary: paper_summary: This paper introduces policy gradient algorithms that focus on
estimating the gradient of the *occupancy measure* with respect to the
policy parameters. In this framework, one can easily extend convergence
analysis beyond the standard RL objective (e.g., maximization of
expected return) to a much broader class of occupancy objectives, such
as imitation learning or pure exploration. In addition to an online
algorithm, the authors design an algorithm for the offline setting based
on pessimistic corrections to density ratios, and provide bounds on the
policy gradient error for both under function approximation. In the case
of the offline algorithm, this paper demonstrates convergence bounds
under weaker assumptions than existing methods. In the case of the
online algorithm, the paper further provides conditions under which
their policy gradient algorithm achieves global optimality.
strength_weakness: strength_weakness: The biggest weakness for the paper, in my opinion, is that it could
benefit from extra clarification at many points. Realistically, this was
probably omitted in favor of making room for more content (the paper is
very dense), but I suggest the authors add some guiding discussions.

Particularly, I think the following should be clarified:

- **Motivation**: My first instinct after having read the draft was
  "this was very interesting to read, but how is the field of RL better
  off in light of these results?". The conclusion and introductory
  sections place a lot of emphasis on the fact that this paper presents
  the first algorithms/convergence results based on estimating the
  occupancy measure, but it's not immediately clear why this is so
  impactful. Ultimately, my impression is that the following two points
  (especially the first) are the real winners:
  1.  The ability to optimize a general class of functionals;
  2.  Weaker assumptions for convergence with the offline algorithm.

  I believe emphasizing these points more, and motivating them, can
  really help the reader appreciate the results, but I found these
  points to get a little lost in the sea of math.
- **Comparison to existing work**: While I understand that this paper is
  the first to analyze convergence of PG methods based on occupancy
  measures, the paper focuses largely on the application of optimizing
  expected return. As such, as someone that is not intimately familiar
  with convergence results for PG methods, it would have been helpful to
  have a more concrete comparison between the bounds presented in this
  work and existing ones.
- **Misc. writing/clarity issues**: Some math and/or algorithmic details
  were ambiguous and/or unclear, listed below. This made the logic a
  little difficult to follow at times.

## Minor issues

On line 28, "In answer" -\> "In response".

In Algorithm 1, $\mathcal{D}^{\mathrm{grad}}$ is not properly defined. On
line 2 of the algorithm, it is implied that it is seeded the same way as
$\mathcal{D}^{\rm reg}$, but on line 7 it appears that
$\mathcal{D}^{\rm grad}$ is supposed to contain reward data (unlike
$\mathcal{D}^{\rm reg}$).

In Algorithm 1, I think the definition of $\mathcal{D}^{\mathrm{reg}}$ has a
typo. It says $\mathcal{D}_h^{\mathrm{reg}} = \{(s\_h, a\_h,
s\_{h+1})\}\_{i=1}^n$, but the index $i$ does not appear anywhere. My
guess is that it should really be something like
$\mathcal{D}\_h^{\mathrm{reg}} = \{(s\_h^{(i)}, a\_h^{(i)},
s\_{h+1}^{(i)})\}\_{i=1}^n$, where e.g. $\{s^{(i)}\_h\}$ is the sequence of
states encounted over the course of rollout $i$.

In Theorem 2, $\mathsf{pd}\_{\mathcal{G}}$ looks confusing (not clear
that it is $\mathsf{p}$ times $\mathsf{d}\_{\mathcal{G}}$ as opposed to a
variable called $\mathsf{pd}\_{\mathcal{G}}$). Is it necessary to use
sans serif font for $\mathsf{p}$?

In definition 46, I believe there is a notational issue. It says
$\mathcal{F}\subset\mathbb{R}^{\mathcal{X}}$, but then you have a term
$\mathrm{sign}(f(x_1^n - c))$ for $f\in\mathcal{F}$. But $x_1^n -
c\not\in\mathcal{X}$. Are you actually mapping $f$ over the dimensions
of $x_1^n - c$? Also, there is a typo here, $c$ should be $v$.
questions: questions: In Corollary 6, what does it mean to run OccuPG with initial
distribution $\nu$?

On line 238, you defined $\bar{\pi}_h = (\pi\land
C^\mathbf{a}_h\pi^D_h)$. I am having some trouble interpreting this.
Firstly, should it not be $(\pi_h\land C^\mathbf{a}_h\pi^D_h)$? Then, if
that's the case, is this equivalent to

$$\begin{align*}
\bar{\pi}_h(a\mid s) = \min\{\pi_h(a\mid s), C^a_h\pi^D_h(a\mid s)\}?
\end{align*}$$

Given that the text focuses almost entirely on the problem of maximizing
expected return, how do the bounds given in this paper compare to those
of existing results? Is there any benefit to running OccuPG if you only
care about expected return (especially in the online setting)?

How tight are your convergence bounds, particularly in the case of
optimizing general functionals?

In Lemma 5, when should one expect to have $\mathcal{C}^{\pi^*}<\infty$?
limitations: limitations: No major issues in this regard. Two limitations come to mind that were not
thoroughly addressed:
1. For optimization of general functionals, convergence results depend on a
   Lipschitz assumption on the functional that is only discussed on the
   appendix. How generally is this assumption satisfied?
2. For the global convergence result (Lemma 5), there is a very strict
   assumption on the initial state distribution, which would not often be
   satisfied in practice (to my understanding). That said, other theoretical
   works have made similar assumptions.
paper_summary: paper_summary: With a focus on "occupancy-based" methods for RL, the authors propose a 
model-free, policy gradient method for policy optimization in finite-horizon 
MDPs via occupancy estimation. Guided by the representation of return in terms 
of the state-visitation probability and reward, they express the gradient of 
the return in terms of gradient of the log of the state-visitation probability. 
They propose to estimate the latter term via squared loss regression (see 
eq 2). This estimate is then used to approximate the gradient of the return 
which is then plugged in to the usual policy gradient objective. In the online 
RL setting, they provide gradient estimation guarantees and convergence to a 
near-optimal policy. For offline RL, due to insufficient coverage of the 
offline dataset, they provide guarantees on the estimate of the gradient of the 
clipped return.

**Update**: I have revised my score based on the following considerations:
1. The authors satisfactory response to the rebuttal,
2. The unique approach to policy gradients, which may be insightful in advancing research on policy gradient methods,
3. While rigidity of their assumption in the offline setting may limit its broader applicability, it also leaves room for further improvement.
4. The authors willingness to address the other reviewers suggestions on notation and presentation.
strength_weakness: strength_weakness: For the offline setting, the authors introduce new assumptions in the appendix which appear to influence their main result in Theorem 16. Precisely, in the proof of Theorem 16, the authors make use of Lemmas which refer to assumption 7 on page 37 and assumption 8 on page 38 to respectively control the MLE estimation error and density ratio estimation error. As such the paper is not self-contained and the results are rather difficult to verify.
questions: questions: Just some additional comments:

1. Line 70: should be $h'\geq h$.
2. In Line 151, do you mean $\psi^{\pi}$ instead of $\psi$? Also, the first expression $d^{\pi}=\mu(s)^{T}\psi$ seems inconsistent.
limitations: limitations: None. This is a purely theory paper.

Comments: comment: I thank the authors for their response. I am satisfied with their clarification of the Assumptions and willingness to move them (including Assumption 6) to the main text.

I have also read other review responses.
Thanks for the authors for the great and detailed response.

Upon reading the rebuttal and the other reviews, I maintain my view that this is a really nice paper that should be accepted for publication.