Occupancy-based Policy Gradient: Estimation, Convergence, and Optimality
Authors: Audrey Huang
Nan Jiang
Venue: NeurIPS 2024 poster (2024)
Keywords: policy gradient
offline reinforcement learning
offline policy gradient
Primary area: learning_theory

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.

Occupancy-based Policy Gradient: Estimation, Convergence, and Optimality
Audrey Huang
Nan Jiang
Department of Computer Science University of Illinois Urbana-Chane Chammpagnn
Department of Computer Science University of Illinois Urbana-Chama Champaiin Champaign, IL 61820 nanjiang@illinois edu
Champaign, IL 61820 audreyh5@illinois edu
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 (only) occupancy functions 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 RI., without modeling value functions. Our algorithms reduce gradient es- timation to squared-loss regression and are computationally oracle-efficient, We characterize the sample complexities of both local and global convergence, ac- counting for both finite-sample estimation error and the roles of exploration (on- line) and data coverage (offline). Occupancy-basc -base PG naturally handles arbitrary offline data distributions, and, with one-line algorithmic changes, can be adapted to optimize any differentiable objective functional.
Introduction
Value-based methods have been the dominant paradigm in model-free reinforcement learning, with solid thcoretical foundation large state spaces under function approximation [CJ19; JYWJ20a: ZLKB20; JLM21; XJ21; XFBJK22). In contrast, model-free RL paradigm based on their natural counterparts- the occupancy functions- ceteiioon-eemains largely under-investigated. Occupancy functions are densities that describe a policy's state visitation, and play instrumental roles in guiding explo- ration [HKSVS19; AFK24], handling distribution shift [HM17: NCDL19; CJ22], and optimizing general objectives beyond the expected return [ZBWK20; MDSDBR22). Despite this, they are sel- dom modeled directly in learning algorithms and appear only the analyses, except in conjunction with value functions in marginalized importance sampling [LLTZZ18 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 computation- ally efficient policy optimization for occupancy- based methods remained 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-lit like recursion, we reduce occupancy-based gradient estimation to solving series of squared-loss minimization prob- lems, which can be done in 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-
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

clude general objectives of occupancy functions, such as entropy maximization for pure exploration and riskseesitivv functionals in safe RL [MDSDBR22]. These objectives generally cannot be opti- mized using value-based policy gradients because they do not admit value functions or Bellman-like equations with which to estimate them [ZBWK200 HDGP24).
In the offfine 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; NZJZW22J. 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 (See. 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- baased PG algorithm that reduces gra- dient 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 conver- gence, 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 offiin 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.
2 Preliminaries
Finite-horizon Markov decision process (MDP). Finite-horizon MDPs are defined by the tuple M AS P. R. H, do), where S is the state space, A is the action space, and H is the horizon. We use H = {O..... H} and when clear from the context, use { = {O, hee( For notational compactness we assume that S = S is the union of H disjoint sets {S*), }, 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 single timestep, we can now define the (non-stationary) transitions as P : S x A + ASS). and the initial state distribution as do E A(S"). We assume the reward function R S - [o, 1] is bounded on the unit interval and (for simplicity) state-wise deter- ministic. 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(A) interacting with M observes trajectories {(Sk, aje Sh+1, Th+1) ) h= and has expected return ((r) = 1 4-1
R(sn)] At any (h, 8, a), its expected return-to-go is encoded in the value function (7, a) R. En R(sh) 1sh 8, az = a).
For each la E [.f] a policy's occupancy function di E (S)) is p.d.f. describing its state visitation, (s)) = P. (s%, = s). 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 that dí p di for all h E [H]. Here, Pd is the Bellman flow operator with (P* f)s') ==
E.o P(s'((ss s, a) (a)s))(ss E IR_ for any function f SSSRR
Policy optimization. For an objective function ʃ : He - R. the general goal of this work is to find argmax ((TT) over a policy class He parameterized by a convex and closed parameter class θ with dimension p. One example of f is the expected return J J(T)). Projected gradient ascent (PGA) will be our base algorithm for policy optimization. For a fixed learning rate 77 and iterations t E [7]. it iteratively updates (f(m))) Jps[pl
{ 0 E 0,0 E RP, ||O|| < B}.
g(t+1) = Proje (0(*) + 1/ (Tote)) Here, (((=)) respect to 0, where superscript p indexes the p-th entry of vector. We will assume that the gradient of the policy's 's log- bog-robabbilty is bounded, as is ubiquitous in the PG literature [LSAB19; AKLM21J.
Jps(p) E IRP is the gradient with

---

Assumption 2.1. For all Ta E He, max,,a V loggo(alss)le S.
We will later analyze the convergence rate of our algorithms to stationary points with (approxi- mately) zero gradient, and refer to x(f) Tatt) for short. For PGA, stationarity will be measured using the standard gradient mapping [[ with (T( = 7, ( g(t+1)), the parame- ter change between iterations [Bec17]. Note that if θ = R and no projection is required, then ||G"(
IV (=)())] reduces to the gradient magnitude.
Computational oracles. As is common 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 terms of problem-relevant parameters. Given an i..d. dataset D (x.,)) and function class F, the maximum likelihood estimation oracle outputs [log fz)].. The squared- regression oracle finds argmin Ep((f()) - y) Both can be approximated efficiently whenever optimizing over F is feasible [MHKL20; FR20].
argmax fer Ep
3 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 gather new trajectories. Our gradient estimation routine is based on recursive Bellman flow-like equation that can be approxi- mately 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.
3.1 Oceupancy-basse Policy Gradient
The expected return of a policy π can be expressed as the expectation over its occupancy of the per-state rewards, [(x En E., ((s)). The gradient of ((x) then passes through d",
VJ(T)= = E. (s) = En Esn-dy v log dī
We use the grad-log trick above to write V (TT) as an expectation over d' which makes it amenable estimation from online samples as long as we can calculate log di S - RR. We make the key observation that V log dj, can be expressed as a function of V log - which involves time-reversed conditional expectation over the previous timestep's (sh-1. a1- given the current
Sh.
Lemma 3.1. For any a and h E [H]. V log dj, satisfies the recursion
V log di E 1 (V (Vlog* ग + V log d.
where E f((') = E, (s = 87 = E., P((llsa))((ca)dd_1()) f(s, a) , for any (''('')
function f f8 A + Rp. Further, under Asm. 2.1, max,, , V log di (s) S hG.
Eq. is derived by propagating the gradient through the Bellman flow equation, and we can solve it from to to compute V log dj, (with log dj by definition). While related observations have been made throughout the rich history of PG literature [CC97: MT01; KU20; XYW1211 the expression in Eq. (1) is adapted to our unique pursuit of modeling log dd with general function approximators. In particular, the conditional expectation (E*) immediately hints that V log d is amenable to estimation using squared-loss regression, a technique that is well-understood for value functions [SB 18] and, more recently, for occupancy functions [HCJ23].
Formally, solve the dynamic programming equation of Eq. (1) a computationally efficient manner, we reduce it to minimizing a squared- regression problem. Consider the standard (super- vised learning) regression setup. The solution to argmin, E(xxa)~o((f(( the conditional expectation given x of the target y under the joint Q. As result (see Lem. B.2),
maps + Eoly [x).
E. [|o((n) (V log 7 (an- + log di (
11. (2)
V log di argmin S
We use the convention 0/0 for ratios between two functions.
3

---

Algorithm OcCUPG: Online Occupancy-based Policy Gradient
Input: Samples nt; iterations T: policy class llg; gradient function class ) learning rate 7)
do 2: Collect n trajectories with x1). Set D {(s), an, 8h+1));=1 for all h. Repeat for (D
I: for = .,..., T- .
3: Initialize 9o
0.
4: for h I...., H do
5: Let _/20 (ghi (n-igg-1) = n E "e,,, [lgh(s)) (V (Vlog (als) + - Set
Th
argmin dn ED, c (ghi 11
(1)
6: end for
7: Estimate -
gh (5')-r'
8: Update ((++1) = Proje (B() + (((0))))))
9: end for
Here, 9 is a vector-valued function, and the norm || 1|2 is equivalent to the sum of scalar-valued squared-losses for each parameter dimension. The RHS only requires sampling (5h- ah-1, 8h) ~ from online rollouts. Then, given finite samples, we can robustly estimate V logg d by minimizing an empirical version of Eq. (2) using regression oracles.
3.2 Online policy gradient algorithm and analyses
Alg. 1 (OcCUPG) displays our full online occupancy-based PG procedure. For each iteration e [T], first collect two independent datasets: {Dr for V loggd" d=(()) estimation, and {Derad) for (+))()) estimation. The former occurs Line 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, tion procedure produces accurate estimates of VJ(T). Our guarantee holds under the requirement that the gradient function classes {G,} 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; HCJ23J.
establish that our regression- based estima-
Assumption 3.1 (Gradient function class completeness). For all / E [M], [uf].suPg5s0 guP (s) S IG. Further, for all π E IT. we have E (V log π + 9h-1) E Gh, for all -h-1 E -
Next, since allow G to be continuous function class, sample complexity bound for gradient estimation is expressed in terms of its pseudodimension := dg (Def. F.I). Examples of & param- eterizations and their dg are discussed in Rem. 3.1 below. Finally, Thm. 3.1 shows that OCCUPG produces accurate gradient estimates given the following polynomial sample size.
Theorem 3.1. Fix 8 10 and Ne. Under Asm. 2.1 and Asm. 3. I, we have that w.p. 2 1 6, [T) (=)]l < when Ö pdg G2 116)
2²
Remark 3.1. Lastly, we provide examples of G for Asm. 3.1 in representative MDP structures. Low- rank MDPs (Def. B. are a well-studied setting where the transition function admits a low-rank decomposition into two features of rank k. i.e.. there exists á S x A + R& and µ S + Ig such that a()
(Ø(s,a), p(s') [JYWJ20b]. Tabular MDPs are special case with one- hot features. Due to the bilinear transitions, both the occupancy and its gradient are linear func- tions of μ. i.e., d = is and Vdd
T u(s)" 1 for some V R &b R and all s E S. When f is known, we can set Gn. to be a linear-over-limear function class Gh. (x) = p(a) v (()) &
pEXp, t R* max, (s)] S hG). which has dg = kp (Prop. B.I).
Stationary convergence. Next, we analyze the convergence rate of OCCUPG to 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 standard in the literature, we will assume that the objective has smooth gradient [LSAB19; AKLM21J.

---

Assumption 3.2 (5-smooth objective). For function f II - R, there exists 3 >> 0 such that [ (T 2 I 8|00 2 for all 0, 8' e.
Cor. 3.1 shows that, in expectation, OccuPG with T = ((HH/=) iterations outputs e-stationary point, as measured by [] = 1 ||((()) 1(t The proof relies on Thm. 3.1, i.c., with enough samples the statistical noise of the gradient estimates are sufficiently small to enable conver- gence.
Corollary 3.1. Under Asm. 2.1, Asm. 3.1, and Asm. 3.2, the iterates of OCCUPG with T O(HHe-1) and Oppdg G log(T/5)e satisfty + E (1]) S..
Computational efficiency. OccuPG is not only statistically efficient but computationally oracle- efficient as well, since it reduces 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 e-stationary point, from Cor. 3.1 require total of ((3H² /e) 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 coverage coefficient C* with respect to the optimal policy.
Lemma 3.2. For any and n', define B² (x(') == - (s))
Suppose Vi Ie
1. (Policy completeness) There exists x E Th such that n+ argmax, Bd (TT). ((x)'=11)) - 13 (BT(T S m maxore (VB* - 0)
2. (Gradient domination) max elle (x))
Given v E (S),, define the coverage coefficient C = E| d% /oo sor x-' argmax, J(T). Then for any me Ill,
((T') - ( S C*
max (VJL(TO), O'Ello
(4)
where (T) E Ex En rhl is the expected return of MM with initial state distribution v.
The lemma preconditions are identical to those required for value-based analysis [BR24]. B" (TT')
one-step improvement objective with respect 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 opperebounded by the one-step policy gradient magnitude, for which the constant is determined wholly by the policy parameterization. For example, the tabular policy my (a|s) 2se has m [AKLM21].
The coverage coefficient C* is the finite-horizon counterpart the infinite-horizon "exploratory initial distribution" salient to the analysis of [AKLM21] and [BR24] (which lists developing it as future work). In RI., 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 initializa- tions 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 optimol
Corollary 3.2. Under the preconditions of Lem. 3.2 and Cor. 3.1, rumning OCCUPG with initial distribution satisfies E(min, J(x²) [[]] S when T = Ō ( (3B"(C= 3 H²²
and
G Ō B (c (((c=")ppm ? pdd GT CooGGoogg] log(T)
3.3
Optimization of general functionals
One standout feature of OCCUPG that can, with a one-line change, be adapted for pol- icy optimization of any (differentiable) objective function involving occupancies. We work with JF (T) Σn Fi (dī,) as representative formula, where FA A(S) + R is a general functional. Such objectives often evade value-based PG optimization because they do not admit value functions or Bellman-like recursions with which to compute them. Examples include entropy maximization
"This means that trajectories are generated by first sampling the initial state $1 ~ then rolling out the policy according to the true MDP's dynamics.
5

---

where (d) - (d, log d); imitation learning where (d) = -lId - dh 1 for an expert policy Tei and the expected return with (d) (d. R) IMDSDBR22].
The policy gradient is then (Jr(T) En Ba-ay
Implementation- wise, we need only change Line in OCCUPG to accommodate the new gradient formula, to DFr(d)
(F
8d(z) d= V log
logg di (s)
(Jr(T) = En ExED, (s)
ad(a) ب= The partial derivative of Fh, 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 9% ~ V log dī (Line 5) is reused verba- tim. Given their resemblance those in Sec. 3.2, the full algorithm and analyses are deferred to App. B.5.
4 Offline Occupancy-based PG
In this section, develop algorithm for occupancy-basee policy optimization in the offline setting, where only fixed datasets are available for learning. A direct modification of OccuPG, e.g., by converting occupancies 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 offiine RI algorithms,, our goal is to establish offline PG algorithm that adapts to and retains meaningful guarantees under arbitrary offline datasets, for which our key consideration establishing an offline gradient estimation method. We begin by defining these offline datasets.
Sh+1.Ph+1)) rh+1)) is gener- ated i.i.d. as 8 ~ dR for some d E (S)) and On ~ 2 (11s) in M, for a known behavior policy D. The marginal next-state distribution in Dj is denoted as d d. (88411) Th
Definition 4.1. The offline dataset is D = {Di,,, where Dr_ = {(s), ahe Sh+1,
Def. 4.1 is more general than the typical i.i.d. trajectory setting [KU20; NZJZW22), where de = d- Crucially, unlike previous works that require lower-bounded dD or all-policy coverage [KU20; X XYWL21; NZJZW22), we will make no assumptions about the quality of D with respect to lIg.
Additional notation. For short, we say Ep. [-] = E an Sh 1.5%, 1)-P, F. and use (s. as.a,'',e r²) D, when clear from the context. For any g : SSx A + Rp reweighting function p HxSxA-
R+, we define an offline reweighted analog to E (Lem. 3.1) for all h E [H] to be
(Pa-oiKee,,') EPP P. g]()) == ('s,,,,') Pa Lg(s, a)l = En,a E... (Pa g(sa).
(5)
The (time-reversed) conditional expectation is taken over [Dr prl(s,a,s) := P(s'ls Is, a)dR (s)TT pals) (s, a), the joint offline distribution re-weighted by Ph- While this may not be valid density, its induced conditional distribution on (s, (s,a always is, i.e. [Di (D. (D..Pa(ssa,sa))
En,o E.. [P..palls.a.t
= 1. As an example, for a given π we have E,""
Eg when
(n(s,a) a) = (a)))( is the policy's density ratio and is well-defined.
d. (+)m (als)
4.1 Offline density-based policy gradient
A policy's occupancy dh may not be covered by arbitrary offline data (Def. 4.1), so neither its expected return J(T)= = Σn (di, R) nor its gradient ( will be estimatable from D. As a result, there is hope of recovering argmax (TT). Our solution is to instead maximize return only on areas of the state space that are sufficiently covered by offfine data, which is captured exactly by the recursively clipped occupancy d= from [HCJ23]. It clamps the policy occupancy to preset multiples C₁ C7 of the offline data distribution, thereby representing only the "sufficiently covered" portion.
E,
Definition 4.2 (Recursively clipped occupancy). Let (O = min (. Given clipping con-
D) and recursively define stants {C*, C 2 1, define the clipped policy to be गn = (T C.
= (dh-1 Ch vh E [M]
(6)
Eq. (6) resembles the Bellman flow equation with clipped policy म. and acts on the previous-timestep d clipped to at most Ch Above this threshold the occupancy is considered to be insuf- ficiently covered for estimation, and C strikes bias-variance tradcoff between the amount of

---

clipped mass vs. distribution shift. The clipped oceupancy's 's density ratio is always bounded as /d-i Ch h- and we use it to define our (now learnable) offline objective,
and
( = C (s)) = En En EDS-:
de R(sh. (9%)
For any "fully covered policy with di S Ch-1 1h-1 P.tt for all h E [M]. we have d= = d and (T) = Jz). In this sense, argmax, J(T) will be at least as good as the best policy fully covered by offline data. Next, define the density ratio be T = di / The gradient of J(T) is
J((T)= = Σn Ep._, प (sA ((s)) V log (s))
To calculate this gradient we must compute both /" and V log d= for the former, [HCJ23] provides a method that we will later call as a subroutine. Our focus is on computing V log d% which is enabled by the following recursive equation, which is offline analog of Lem. 3.1.
Lemma 4.1. For any ι and all [H),, define (%,s,
(+))
(als)) Then " [a]a]
(a())
V log dz - (Vlog 1[m CF V Vog H O 1
CR (7)
where ER-A" is from Eq. (5), and [M el()) == v( v(-M(()) RP for M : p and v 0
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 V logg т and V log d where they are insufficiently covered, e.g., 1 > C7 Ch (s). Further, under full offline coverage we recover Lem. 3.1 and V Voog d= = V log d=
Because the rewards are nonnegative, V log d' induces a pessimistic policy gradient that shifts poli- cies away from -fitt--iiittibution actions, even if they generate high return. This is seen more clearly in Prop. 4.1, that rearranges the resulting expression for ( into a value-based form: Proposition 4.1. We can equivalently write
VJ(T)= = ED, [pR V) log Th (s,
where QT is a pessimistic value function that obeys the Bellman-like recursion (8, = ()(()))))))))))
1/x S CR Kalo) (()l(s.)) (R(5') + 1(7 S Ch+1 Q (6b,T(1)))))))) (h+1))
In Q-, future returns zeroed out states and actions that exceed the threshold of data coverage, due to indicators functions that are inherited from V log d= Prop. 4.1 can be seen as a pessimistic of- fline analog the classical PG theorem [= = Σn Ex [V log (als) (s,a)] (SMSM99), entirely induced by the definition of the clipped occupancy.
of V log d= estimation to plug-in densities. With finite samples, however, it turns out that consistent estimates of V log di, 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ī and {77))
. Compute log dū using Eq. (7) with plug-in indicator function estimate 1 S
The problem arises in step two, as 1[-] stepwise function and not smooth. Even if d= is van- ishingly close to d',, the gradient calculated from plug-in occupancy estimates can have constant error.
Proposition 4.2. There exists MDP and policy such that, for any > O, maxk,s V log (s)= & log di. (s) (1) when || d; S E and || dhllz S E for all h.
4.2 Smooth clipping
To resolve this issue, we will use a "smooth--lipping" function a (x, c) to approximate the "hard"- clipping (x A c) in Eq. (6), whose non-smooth gradient was the source of our estimation problems. Figure plots 1-D examples of (ar, c) against (x Ac) as reference (dashed), and Asm. 4.1 describes the properties of o that enable our later estimation and convergence guarantees.
7

---

0.5))
[x(, CM 0.5)
1.0
D₂
1/2
1/4
1/8
Figure 1: We plot o(z, c) from Prop. 4.3 for different b, that trade-off between clipping ap- proximation error and smooth- ness (D, x 1/L.).
0.5
1/16
16
0.0
0.5
1.0
0.5
1.0
Assumption 4.1. Assume that satisfies v'r c, e E dom(a),
1. (Approximate clipping) 3D, 2 such that 0 S (2 ( (x, c) s D, (x Ac).
2. (Monotonicity) a (z', c) s a (z, c) if S x; (z, 5 (z, if c' s c; and vice versa.
3. (Smooth gradient) Define the smoothed indicator i (r, c) == x 02 log (2, where O₂ is the partial derivative w.r.t. x. Then [ E [0, 1] and 3I 2 s.t. Vx, c,,' E dom(o))
cj (c. c) i cz), ba - 1'1. and x/ (x, c) - (xx, c)1 s Ladee d'l-
Note that (z, c) (x A is special case with i (x)c) c) = 1[x S c). thus D2 = 0 and Lo oo. The following choice of a, which is plotted in Fig. 1, fulfills Asm, 4.1.
Proposition 4.3. For any b 1, a (2,c) (a + b) 1/b has Lag b and D, = 1/b.
Next, we define the amooth-clipped occupancy function dh. which is no larger than dā. Definition 4.3 (Recursively smooth-clipped occupancy). For smooth-clipping function o satisfying Asm. 4.1 and clipping constants {C7, C.). define ān := a (T,, CT and inductively set
T = P
C (d (h-hh-)) wh [H].
(8)
Then letting W6 = d d D.t our new objective is J(TT) = En, Ep._. [on (sN H(s)) with gradient
(m))) = En ED,_, (ū sh) R(Sn) V d (s%)], where V log dī obeys the following recursion.
Lemma 4.2. For satisfying Asm. 4.1, recall i (z, c)
Og log a (I, Then for all h E [H].
V Voog dh. = E-
EE D.7
V log @ Ch- + V log 1 i (T.-,.7-
(9)
where (s, (3
ān (als) and E ED is defined in Eq. (5). Further,
(s)
(als)
under Asm. 2.1, max,.h |/ log di (8) < hG.
Eq. (9) replaces the (non-smooth) indicator function in V log d= (Lem. 4.1) with its smooth approxi- mation I, 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(m), ), also approximately maximize our target objective J(m),, with bias proportional to D.. Proposition 4.4. Under Asm. 4.1, 0 < maxxells ((T) max, J(x) S H2
4.3 Offline smooth-clipped gradient estimation
Alg. 2 describes the offline PG algorithm for optimizing J(m).. To reduce clutter, have used V log 7r := V log @ i (M,, C) First, OFF-OcCUPG estimates dh_, using MLE (details in App. D due to space constraints). Then, for each iteration t, it estimates the smooth-clipped occupancy J.. using FORC (adapted from [HCJ23], see App. E). This is plugged into squared- loss regression problem approximating Eq. (9) to learn V log dr (lines to 10), then estimate vJ ()) (line 12).
8

---

Algorithm 2 OFF-OCCUPG: Offline Occupancy-based Policy Gradient
Input: data D; iters T; learning rate yf function classes ll,, J, W, G; clipping constants {0 Cj
I: Split D equally into Diule DEORC "Dres, Derad, each with n samples.
2: Estimate {2h 2.11
} x- MLE (Dmlee
11 Alg. 4
3: for t = . T do
4: Estimate (w))) < FORC (r(1),DOOM W, (2p, 2)
1/ Alg.
5: Set occupancy estimate 2. = wh) 2 for all [H].
6: Initialize In
(() 0.
7: for h = 1. , H do
o , 1h 1)
20
=ff) 8: Set density ratio Ph-1 -
9: Set gradient regression target
1/th
-h- c hh 07-12h1)
Let (,41 19:09.))))))) [e., p(s, a))lg(s))) (Vlog (hgs (((s) Solve
(1) In
argmin
gs ED, (0t (ghi -h-11 ph-1)
(10)
11:
end for
12: Set (T((())) 1 Σ "(s.,'" (s' (s))
"
Update g(++1) Proja (0()) + ()((())))
14: end for
Before stating the estimation guarantee for (JT,,, 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; HCJ23J. We focus on discussing Asm. 4.2 for the offline gradient function class, which requires stronger level of expressiveness. Since the regression target in OFF-OCCUPG involves plug-in occupancy estimates, the completeness condition naturally requires G, to express the gradi- ent update in Lem. 4.2 for all possible targets composed of functions from FR-1, Wh-1, Gh-1. As a result, Asm. 4.2 is generally stronger than Asm. 3.1 for OCCUPG.
Assumption 4.2. For all h, supgeg, lo I hG; and for all (a. (5.9.t f.f., w) E Ill x Gh-1 X Fn x Fn-1 x Wh-1, we have - (V log Th-1 + y o (w]', C ( E Gn. where p = awo .TT) R
When the underlying MDP has favorable structure, however, we can expect that dg is not much larger than required for OccuPG. This is indeed the case in low-rank MDPs, where the defined in Rem. 3.1 also satisfies Asm. 4.2 (proof in Prop. C.I). Due to the bilinear transition structure, the offline gradient update (Lem. 4.2) applied any target remains linear-over-linear function.
The guarantees for the MLE (Alg. 4) and weight estimation (Alg. 5) subroutines require Asm. D.1 and Asm. 1. respectively, which are included in the preconditions of the main result below. Briefly, Asm. D.I requires F to realize the true data distributions dă and a which is standard in super- vised learning. Asm. E. requires W to be closed under the Bellman flow operator, and can be viewed as 1-dimensional version of Asm. 4.2 where p In this sense both assumptions 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 C, C.CC)) and the smooth- ness of a.

---

Theorem 4.1. Suppose J(.) satisfies Asm. 3.2 and fix π E Il.. Under Asm. 2.1, Asm. 4.1,
Asm. 4.2, Asm. D.I, and Asm. E.I, w-p. 2 1 have [V [J(T) S when
Ō pdg C7CR) 1og([W]()118)
Stationary convergence & computational efficiency. Similar to OCCuPG, OFF-OCCUPG with T = -(8H2 converges to an e-stationary point. The formal statement is given in Cor. C.I and is based on the estimation guarantee Thm. 4.1. As a result, OFF-OcCUPG also computationally oracle-efficient. Each invocation of MLE involves 2H calls to 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 (33H2 /s") 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. 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 } (instead of the online (*)) However, this is not guaranteed 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 stationary policy might be far off- support, 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.
5
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 conver- gence. 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-bart -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 launch empirical investigations of our methods, especially those for optimizing general functionals. Additionally, the conditions un- der which offline PG can converge to global optima not well-understood, and we hope that our preliminary results here encourage greater interest and investigation into this question.
Acknowledgements
Nan Jiang acknowledges funding support from NSF IIS-2112471, NSF CAREER IS-2114781. Google Scholar Award, and Sloan Fellowship.
References
[AFK24]
Philip Amortila, Dylan J Foster, and Akshay Krishnamurthy. "Scalable Online Ex- ploration via Coverability". In: arXiv preprint arXiv:2403..m 0657/ (2024). Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. "Flambe: Structural complexity and representation learning of low rank mdps"" " In: Advances in Neural Information Processing Systems (2020).
[AKKS20]
[AKLM21]
Alekh Agarwal, Sham M Kakade, Jason D) Lee, and Gaurav Mahajan. "On the the- ory of policy gradient methods: Optimality, approximation, and distribution shift". In: The Journal of Machine Learning Research 22.1 (2021), pp. 4431-4506.
[ASM07]
András Antos, Csaba Szepesvári, and Rémi Munos. "Fitted Q-iteration in contin- uous space MDPs". In: Advances in neural information processing systems 20 (2007).
[Bec17]
Amir Beck. First-order methods in optimization. SIAM, 2017.
10

---

[BFH23]
Anas Barakat, Ilyas Fatkhullin, and Niao He. "Reinforcement learning with general utilities: Simpler variance reduction and large state-action space". In: International Conference on Machine Learning. PMLR. 2023, pp. 1753-1800.
[BR24]
Jalaj Bhandari and Daniel Russo. "Global optimality guarantees for policy gradient methods". In: Operations Research (2024).
[CC97]
Xi-Ren Cao and Han-Fu Chen. "Perturbation realization, potentials, and sensitivity analysis of Markov processes". In: IEEE Transactions on Automatic Control 42.10 (1997), pp. 1382-1393.
[CJ19]
Jinglin Chen and Nan Jiang. Inffrrmtiion-Theorel Considerations in Batch Re- inforcement Learning". In: International Conference on Machine Learning. 2019. Jinglin Chen and Nan Jiang. "Offline reinforcement learning under value and density-ratio realizability: the power of gaps". In: Uncertainty in Artificial Intel- ligence. PMLR. 2022, pp. 378-388.
2019.
[CJ22]
[DWS12]
Thomas Degris, Martha White, and Richard S Sutton. "Off--plicy actor-critic". In: arXiv preprint arXiv: 220//2555..353 (2012).
[FR20]
Dylan Foster and Alexander Rakhlin. "Beyond ucb: Optimal and efficient contex- tual bandits with regression oracles". In: International Conference Machine Learning. PMLR. 2020, pp. 3199-3210.
[GL16]
Saeed Ghadimi and Guanghui Lan. "Accelerated gradient methods for nonconvex nonlinear and stochastic programming". In: Mathematical Programming 156.1-2
(2016), pp. 59-99.
[HCJ23]
Audrey Huang. Jinglin Chen, and Nan Jiang. "Reinforeement Learning in Low- Rank MDPs with Density Features". In: arXiv preprint arXiv:2302.0222: (2023). Jia Lin Hau, Erick Delage, Mohammad Ghavamzadeh, and Marek Petrik. "On Dy- namic Programming Decompositions of Static Risk Measures in Markov Decision Processes". In: Advances in Neural Information Processing Systems 36 (2024). Audrey Huang and Nan Jiang. "Beyond the Return: Off off-policy Function Estima- tion under User-specified Error-measuring Distributions". In: Advances in Neural Information Processing Systems. 2022.
[HDGP24]
[HJ22a]
[HJ22b)
Jiawei Huang and Nan Jiang. "On the convergence rate of off-policy policy opti- mization methods with density-ratio correction". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2022, pp. 2658-2705.
[HKSVS19]
Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. "Provably efficient maximum entropy exploration". In: International Conference Machine Learn- ing. PMLR. 2019, pp. 2681-2691
[HM17]
Assaf Hallak and Shie Mannor. "Consistent on-line off-policy evaluation". In: In- ternational Conference Machine Learning. PMLR. 2017, pp. 1372-1383.
[JKALS1]]
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. "Contextual decision processes with low Bellman rank are PAC- learnable". In: International Conference on Machine Learning. 2017.
[JLM21]
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. "Bellman Eluder dimension: New rich classes of RL problems, and sample-efficient algorithms". In: Advances in Neural Information Processing Systems. 2021.
[JYW320a]
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. "Provably efficient reinforcement learning with linear function approximation". In: Conference on Learning Theory. 2020.
[JWJ200b]
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. "Provably efficient reinforcement learning with linear function approximation". In: Conference on learning theory. PMLR. 2020, pp. 2137-2143.
[KJDC24]
Pulkit Katdare, Anant Joshi, and Katherine Driggs-Camphell "Towards Provable Log Density Policy Gradient". In: arXiv preprint voXiv:2403.0666 (2024). Nathan Kallus and Masatoshi Uchara. "Statistically efficient off-policy policy gradients". In: International Conference on Machine Learning. PMLR. 2020. pp. 5089-5100.
[KU20]

---

[LLTZI8]
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. "Breaking the curse of horizon: hhriioe-horizon off-policy estimation". In: Advances in neural informa- tion processing systems 31 (2018).
[LNSJ23]
Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin. "Optimistic mle: A generic model-based algorithm for partially observable sequential decision mak- ing". In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023, pp. 363-376.
[LSAB19]
Yao Liu, Adith Swaminathan, Alckh Agarwal, and Emma Brunskill. "Off- policy policy gradient with state distribution correction". In: arXiv preprint arXiv:1904.066 0004438873300 (2019).
[MBFR24]
Zak Mhammedi, Adam Block, Dylan Foster, and Alexander Rakhlin. "Efficient model-free exploration in low-rank mdps". In: Advances in Neural Information Processing Systems 36 (2024).
[MDSDBR22]
Mirco Mutti, Riccardo De Santi, Piersilvio De Bartolomeis, and Marcello Restelli. "Challenging common assumptions in convex reinforcement learning". In: Ad- vances in Neural Information Processing Systems 35 (2022), pp. 1489-4502
[MHKI.20] Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. "Kinematic state abstraction and provably efficient rich-observation reinforcement learning". In: International conference on machine learning. 2020.
[MTOI]
Peter Marbach and John N Tsitsiklis. "Simulation-based optimization of Markov reward processes". In: IEEE Transactions on Automatic Control 46.2 (2001), pp. 191-209.
[NCDL19]
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. "Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections". In: Advances in neu- ral information processing systems 32 (2019).
INDKCLS19]
Ofrr Nachum, Bo Dai, llya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schu- urmans. "Algaedice: Policy gradient from arbitrary experience". In: arXiv preprint arXiv:
(2019).
[NZJZW22]
Chengzhuo Ni, Ruiqi Zhang, Xiang Ji, Xuezhou Zhang, and Mengdi Wang. "Op- timal Estimation of Policy Gradient via Double Fitted Iteration". In: International Conference Machine Leurning. PMLR. 2022, pp. 16724-16783.
[SB18]
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[SMSM99]
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. "Pol- icy gradient methods for reinforcement learning with function approximation". In: Advances in neural information processing systems 12 (1999).
[UHJ20]
Masatoshi Uchara, Jiawei Huang, and Nan Jiang. "Minimax weight and q-function learning for off-policy evaluation". In: International Conference on Machine Learning. PMLR. 2020, pp. 9659-9668.
[UIJSXX1]]
Masatoshi Uchara, Masaaki Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, and Tengyang Xie. "Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency". In: arXiv preprint trXiv:2102.02966 (2021).
[XCJMA2I]
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. "Bellman-consistent pessimism for offline reinforcement learning". In: Advances in neural information processing systems 34 (2021).
[XFBJK22]
Tengyang Xie, Dylan Foster, Yu Bai, Nan Jiang, and Sham M Kakade. "The role of coverage in online reinforcement learning". . In: arXiv preprint arXiv:2210.04157 (2022).
[X121]
Tengyang Xie and Nan Jiang. "Batch malue-function upproximation with only real- izability". In: International Conference on Machine Learning. 2021.
[XYWL21]
Tengyu Xu, Zhuoran Yang. Zhaoran Wang, and Yingbin Liang. "Doubly robust off- policy actor-critie: Convergence and optimality"" In: International Conference on Machine Learning. PMLR. 2021, pp. 11581-11591.
[ZBWK20]
Junyu Zhang, Amrit Singh Bedi, Mengdi Wang, and Alec Koppel. "Cautious rein- forcement learning via distributional risk the dual domain".. In: arXiv preprint a:Xiv:2002.12475 (2020).
12

---

[ZHHJL22]
Wenhao Zhan, Baihe Huang, Audrey Huang. Nan Jiang, and Jason Lee. "Offline re- inforcement learning with realizability and single-policy concentrability", In: Con- ference on Learning Theory. PMLR. 2022, pp. 2730-2775.
[ZLKB20]
Andrea Zanette, Alessandro Lazaric, Mykel J Kochenderfer, and Emma Brunskill. "Provably efficient reward reward-agnostic navigation with linear value iteration". In: Ad- vances in Neural Information Processing Systems. 2020.
13

---

Appendix
Related work
14
B Additional results and proofs for Sec. 3
15
B.1 Proofs for Sec. 3.1
15
B.2 Proofs for Sec. 3.2 Estimation and local convergence
16
B.3 Proofs for Sec. 3.2: Global convergence
17
B.4 Examples of gradient function class
19
B.5 Policy optimization of general functionals
20
C Additional results and proofs for Sec. 4
21
C.I Proofs for Sec. 4.1
C.2 Proofs for Sec. 4.2
22
C,3 Proofs for Sec. 4.3
25
C.4 Local convergence of OFF-OCCUPG
30
C.5 Global convergence of OFF-OcCUPG
32
C.6 Proofs for App. C.5
33
D Maximum Likelihood Estimation
38
Offfine Density Estimation
39
F Probabilistic Tools
41
Optimization Tools
43
A Related work
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 ap- proximation. In particular, [KJDC24] requires on-policy sampling from the time-reversed transition (s, als'), which, as they note, is highly restrictive. To overcome this issue they propose min-mi max algorithm that converges under linear approximation, which is computationally far more difficult to solve (under a more stringent structural assumption) than regression objective in Alg. Simi- larly, [BFH23] consider only online policy gradient, and to handle large state spaces they use linear function approximation, which may incur large error through bias in many settings. [ZBWK20] approach the problem of optimizing risk functionals through 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 INDKCLS19; HJ22b; UDJKSX21; 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 classical convergence analysis that allow us to focus on the role of coverage coefficients in our final results.
14

---

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 [UIJKSX2]] exhibits a recursive decomposition that is related to ours. However, their formulation not compatible with our data assumptions and they require policy coverage to be well-defined. A follow-up paper in [XYWL.21] 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 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 (s) Pals) = O. This is done (in the infinite horizon setting) by resampling the dataset based on augmented MDP where such (s, a) transition to an absorbing state However, this does not control the (potentially extremely large) vari- ance of the estimator, e.g., on states where (s)s) & O. Their objective can be seen special case J (T) with finite but extremely large choices of C and C 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 aver- aged on 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 [XCJMA2I] is a policy optimization algorithm based on pessimistic value functions. Their setting somewhat orthogonal 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 standalone policy class but rather an implicit one induced by the value functions, which be extremely large. In the value function sphere, [NZJZW22] leverage the linear structure of linear- MDPS 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. 3
B.1
Proofs for Sec. 3.1
Proof of Lem. 3.1 First we expand Vdg, using the Bellman flow equation, d5(s') Ex,a (a)as)
(d)(s) = E.a P(s'ls, a) (V + log d (s)).
= =..a P(s'ls
In the last line above we use the grad-log trick. Note that V log d (s) is not well-defined when (x) O, but the two terms will cancel out the above expression for this case. From Bayes' theorem, p (sh-1 8, a=-1 = alsa = 8') = P(6'1s, a))))) (s)/ (d/( thus
V log di (s') (o))6')/
E" V log (als) + V log d. (8) =
[E V log V log d (s'). We use the convention that 0/0- = 0, thus V log dí is always well-defined.
Lastly, the second statement results from Lem. B.I. which shows that |/ log di (s')l is always bounded and well-defined under Asm. 2.1.
Lemma B.1. Under Asm. 2.1, have max V log ds)l S hG.
Proof. The lemma statement can be derived inductively starting from the observation that Eq. (1) an expectation over its target functions. As result, the maximum gradient magnitude should accrue
15

---

additively over horizons. More concretely, fix h and Then
V log dz (s')l
| log (als) + V lloo logd Sy
s'lll
- V log [) + V log -1))l
- G + V log (s)]l
using Asm. 2.1 in the last line. Since V log dj 0 by definition, unrolling the above recursion through timesteps gives the stated result.
Lemma B.2. For S + IP and f f x A + IR, define the squared loss
Ln(g: x) E, [llg(()+1) f(sn, )111
Then for any such
E ( argmin La (gi f.T)
and
V log d3 argmin La (g; V log π V log dl. R).
9:8-+3?
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 O in an element-wise manner. Fix s'. Taking the gradient of LA (g: x.) with respect g(s'), we have that
0 (>))((())))
Σ P(cls.aarralb0
Rearranging and using the definition of Ej gives the result. The second statement follows from Lem. 3.1.
B.2 Proofs for Sec. 3.2 Estimation and local convergence
Proof of Thm. 3.1 First we split up the emrors contributed by regression and the estimation. Fix
then Ere ( Σn Eg Oxx (s) Ra (s)) and
[+) ( (+)) Ep [T](]]] (+)
The first term is related the regression error कe approximating log di.
J Epie [T(]]]
= Eg V log d (s) RR (s)] - Eag (s)
Σ Egg log di 07% [s)]
Σn v
E 1= log
I 1o 11
For fixed h and p. we recursively decompose
|| log di
9h P 1,.g
&
V log di
E
V log ग + Th 1111))111100
E V log
_ + Th )r 1 1 11.55
v log di
99
||| 1,
ET V log + -) - 10
using the fact that V log dj recursion, we have
E ( log ग + V log d 1 in the second line. Then unrolling the
V log di
II Σ
+ 17-") 17,
Applying Lem. F.2 (more exactly, this is an offline version but we invoke it with = and no clipping for the online setting) with 8' 8/2Hp and a union bound over all h and p. we have
E log -6 ) 19. 1
EECo (R Ih-1)
S.pee (E (V log क + -.
1). DT )
16

---

S 2 1)
where 1h log
Then for any p have
"
V log df
11,,0; 2
Eg
S
/
2odgh G2 log (og(2Hp/0)
95h
Implying
2epdg G log log(2Hp/6) 19 1
(V) & log do
n
For the second term,
Σ (s) S H log (2g(2p//0) T2
De (PJ (P)]))pP((T)) {P]( & Σ
n
sED
where use Hoeffding's inequality with union bound. for all h E [H] and in the last line, given that the randomness of ğ is independent given D Thus
p log((pHH/)
B [(T]]] (((+)) & HPG
Combining the two terms, our final bound is
pdg H8G log(2H
[ - (((+)l
with the regression error dominating.
Proof of Cor. 3.1 For any fixed run of Alg. calling Thm. 3.1 for (1) a union bound over 7 gives with probability at least that
with 8' 6/T and taking
pdg H (2g(2H)T/0) Vt V [T].
[V - ()(())) S
n
Then setting 8 // we have
-
pdg pdgHiG H2 log(2HpTn)
n
where the expectation is over random samples in Drek, Dost Finally, plugging this into the PGD stationary convergence bound in Lem. G.I gives
1 - Σ E (T [J(((( -
43H
6pdg log
T
T
Setting the RHS to and setting T, n appropriately gives the result.
B.3 Proofs for Sec. 3.2: Global convergence
We will establish the conditions under which (x) satisfies a gradient domination property, meaning that for any 0 E O, the suboptimality of me is bounded by some function S that includes a measure of its stationarity, i.e., maxx'elly J(m²) ((ma) < ((VJ(m))) (m))) 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 (TT) induced by running starting from initial distribu- tion do it will be useful to consider performing Alg. using a different exploratory initial distribu- tion μ ASS). By exploratory, we In the (stationary) infinite horizon this is a common trick for obtaining well-defined gradient domi- nation 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]).
that allow u(s)) 0 for all S, unlike dy A(S").
We state and prove more general version of Lem. 3.2:
17

---

Lemma B.3. For any π and x', define B" (3') == En
a). Suppose VT E IIa,
1. (Policy completeness) There exists x E lT such that nt E argmax, (T))') B"
2. (Gradient domination)
B (x")) eale
(²(T) (T) S m maxere (VB*(T), - 0)
Given us E (S)), define the coverage coefficient C En di / 00 for nt argmax & [mr Then for any ne E 1le,
Σn dh En
J(x') - ((TO) S m
max O'Ella
(VJ 0' 0)
th u.h
S c"
max l'elle
(VJu(To), 0' 0
where (T) == E Exporr EE Thl is the expected return of M with initial state distribution v.
Proof of Lem. B.3 First we note two facts that hold regardless of M. We have Q7 (s a²))
Q7 a²)) for any g I h, and dy (s = 0 if g > h.
H-1
J(x)) - [ = ΣΣ1 dx (T) mo(als)) (% (s
h=0 8,0
Then we will write QT a) = Q7 (s) thus
((=')
Σ
d% (s) (als) -
h=U
Σ
Σ di (s)
Te(c))) (T((),)))
S max
dh (8)
(T (at(s))) - mo(als))
8,0
h
Σn h
di
Σ (i)(s) (als) Te(ass) (s,
max
u.h
Σn d
max x
The u.h
(s) (c(aa))==((ass)) =o(a|s)) a= (s,
8,0
For the RHS, observe that di (s = O for g > h. Then
ΣΣdh(s d (s) (T+ (als) (als)) (s,a)
h 8,0
M. (8) (als)) =a(als) Q7 (s,a)
h
(3) (als) Ta (als)) Q (5,a)
H.h
h
B (T
R (TO)
S max
F (m²), 8¹ B)
Peee
= max 6'Ee
(TO), V ( 8' 0)
Combining the two inequalities results in the final guarantee.
Proof of Cor. 3.2 Fix (m(()) heEry from Alg. 1. Then for any E [T], from Lem. 3.2 we have
J(T") (1) < mm" max l'elle
(VJ(T(())) - 8)
18

---

BmC [[
(Lem. G.4)
Then summing through 7 and taking expectation over the randomness in the algorithm, we have
E
1
-
< BmC
E
T Σ (T(
T
433H T
6pdg H log(2HpTn))
< Bmc
(Cor. 3.1)
n
B.4 Examples of gradient function class G
This section contains formal statements the claims Rem. 3.1, and their proofs. We begin by defining the low-rank MDP, noting that for notational compactness have dropped the features' h-dependence given our assumption that there is a one-to-one correspondence between states and the timestep at which they are visited.
Definition B.1 (Low-rand MDP). We say M a low-rank MDP with dimension & if vh E [H) there exists é S x A 7 g and μú S + IR such that (s, a, s'), we have P(s' s, (Ø(x, a), v(x')) Further, || S C and Σ, ((s))) C
Prop. B.1 shows that, in low-rank MDPs, a linear-over-linaal parameterization for the gradient func- tion class satisfies the completeness requirement in Asm. 3.1, with pseudo-dimension linear in the low-rank dimension and the parameter dimension, i.c., dg. = Okp)).
Proposition B.1. Suppose M is a low-rank MDP (Def. B.1), and suppose μ is known. For each layer h, define the function class
Gn -
T V J T
RE +b Rt 11nn loo S hG, vh E mm]
Then {9n} satisfies Asm. 3.1 and has pseudodimension (Def. F.) dg, = O(kp).
Proof of Prop. B.I. It suffices show that, for any function f S x A IRP and policy its gradient update from Lem. 3.1 is E ( log ग + f) E Gh+1-
Since E, V log + (s') = E, V log (s. a) - [s)]s'), from Bayes' rule and the definition of Bellman flow operator (see proof of Lem. 3.1), we have
E (V log + f))(s") = P (V log x + f)](s'
(s')')
First, we will show that (P))(**)) = u(s') T for some E R and all s' S. Below, we use (s) to denote the p-th parameter of (s) E RR. For fixed p E [p).
[PT)(())) Σ (Flls.. (*
= =(() Σ (V f(()))
8,a
= =s
where xi = Es.a (s, (als) (V log (als) + (s)) E R Stacking this result for each into the matrix Wi shows the desired statement that [P))((s)) Tv.
can apply similar reasoning as above in the Bellman flow equation to show that di (j(s'), b) for some 0 E R Combined with the above, this shows that
/ V
V log (s))
J
Combining the linear forms of the numerator and denominator reveal that V log d E Gh. Lastly, the pseudo-dimension of GR follows directly from applying Lemma 24 of (HCJ23), which bounds the pscudo-dimension of lvnear-over-lineat function classes with p 1, in all dimensions. D
19

---

Algorithm 3 Online Occupancy-based PG for General Functionals
Input: Functional }: Samples nı; iterations T;; policy class ll;; function class G; learning rate 77, function class FF;
for ..... T- do
2: For all h E [H] deploy (() for 3n trajectories. Set D = {(h,, ahe (++1))==1+ and simi-
larly for Di and Di
3: for / = 1,..., H - do
4: Define h/ hh (9h, 9h-1) = 1 n (( [lgh(s') (V log (o + 1s))
and set
(1)) argmin yn EGn, - -h 12
(11)
5: end for
6: Estimate dí + MLE(DEDm F).
11 Alg. 4
7: Estimate (JF(TT = N, En EoEDin (s) Bd(s) d=
(Fa(d)
8: Update ((++1) = Proje (BL)) + +()))()())
9:
end for
B.5 Policy optimization of general functionals
Alg. 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 Alg. 1, the only change is the objective gradient calculation in Line 7, which uses a plug-in in estimate of the occupancy (Line 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 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, F3 has smooth gradient, i... for any f. E A(S) that
(d) od(s) d=f ad(s) d=f' S Lr - I'1l,
(d)
Σ
and has bounded range [ (x) S CF.
Theorem B.1. Suppose that Asm. 2.1 and Asm. B.I hold. Fix a Th With probability at least 1 8,
VJr(m) ((oo))--Jr(m))] & HPGLEY plog( plog(2pH(F110b)
Hd 2o
Cry
When Asm. 3.2 holds, this result directly leads to a stationary convergence guarantee similar to Cor. 3.1, by union bounding Thm. B.1 over all T then plugging it into Lem. G.5 (see proof of Cor. 3)... We expect that the global convergence in Cor. 3.2 can also be extended with little overhead when ( (F.) are convex, but leave full investigation future work.
Proof of Thm. B.1 The analysis follows largely the same lines as the proof of Thm. 3.1. However, we must additional account for the error of approximating
0F ad(a)
with the plug-in occupancy
d=
estimate. This was unnecessary for the expected return in Sec. 3.2 since (F,(d) Rs(s) is indepen- dent of the occupancy.
ad(s]
First, for all E [A]. with probability at least 1 we have occupancy estimates from Alg. 4 such that
2 2 (H F1/8)
|d
mle, Vh [H].
n
20

---

This follows directly from Lem. D.I with a union bound over H.
Next, isolate the occupancy estimation-related term from the would like to bound. De-
fine (T) = Σn Bendj
(F.(d) ad(e) d= V log di (s)) and decompose
[[V - vJr((T] = (m) (T) - (
For the first term,
TaF (d)
(Fr(d)
||V - --]((T] Σ Bondh
dd((s
ddddy
log (s)
0d(s)
d=
v log di
(FF
0Fr
$ HG) Σ
Bend
0d(s)
d=dy
dd(s)
d=
(d)
HG Σ
Od(s)
d=d7
ad(s)
d=
b
S GL max ||df -d7 II.
S HLGLpemle
using Asm. B.1 in the second last inequality. This takes care of the aforementioned occupancy estimation error.
Jr(r)] || analogous the error bounded in Thm. 3.1, and the proof follows identically thereon, but with dependence on the range Cr of the functionals.
Conditioned such {d% J. the second pair of terms [[)
C Additional results and proofs for Sec.
C.1 Proofs for Sec. 4.1
Proof of Lem. 4.1 By passing the gradient through the clipped Bellman flow equation Def. 4.2,
we have
(s')
A 11
Σ
P(s'ls, (Vannv(as)(( (T]
8,0
Σ ((s)s.00m
Ch o (Vlo
Vog (8) A C oh
Next, dropping the h - subscript for a moment, observe that
V dst (s), 10
if < Cdd df > C (s).
V log
with a discontinuity at ds (s) For simplicity, set V log (d (s) (c
v log d' (8) 1 (s) Cs)D Similarly, have V (als) Vlog 2 (T(as)
C (a]s)]-
Finally, V log (s') dd) where d3's E., P(s'|s, a) (c))) The lemma statement follows from the definition of E.L. and the gradient magnitude bound results from invoking Lem. C.2 with a (x, c) = (a c).
This result follows from applying Lem. C.7, which more general version of the proposition statement that holds for any Samooth->clippinn function, to (z, c) (x A c).
Proof Prop. 4.1
21

---

Proof of Prop. 4.2 The MDP we will describe corresponds to mnulti-armer bandit with 2 actions. Consider an MDP with H 2, and 8 {sa). S' Sn, S In any state there are two actions, A = {T,, RJ. with deterministic transitions. For the first level, we have 8p 4 81, and 80 3 8R. For the second level, we have 85, - 8- and 822 + regardless of action taken. For the reward function, R(s-))
s which are terminal.
and is 0 otherwise.
The policy is parameterized by a single parameter & such that TL) = 1 0, and ( = 0. such that di (SR) = d2 (5+) = 0. Further, both the offline data and behavior policy are uniform in each level. Consequently, To
m (L) m (R) 2 and di unif(S+). We set Ci C. 2, and C 2 so that F. nh for all h.
Fix @ and estimated occupancies d=e and dP. For any s' S² we have
V log d2 (s') log dio (6)) = (s') (1 (1(4 s
& ||
Next, we instantiate dma _ for any :T. The preconditions of the proposition are satisfied by an estimated occupancy with dio (8L) 0 + e/2 and di (sn) 0 c/2. addition, we have an estimate d with (st. = 1/2 c/2 and d (SR) = 1/2 + c/2.
We will consider 0 = 1/2, so that di v Ctdp. However, d,00 (sL) > dp (sL). As a result,
log o (s') - V log dz (5') = V4 (s 0
C.2 Proofs for Sec. 4.2
First, we formally state and prove the claim that Lem. 4.2 can be reduced to minimizing squared- loss regression problem recursively over timesteps, i.e.,
V log di
(11)
[lo(s') Oi + V log oh oî (??
= argmin Ep. 9:8-+B0
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 S + Rp and f S x A + R and reweighting function S x A + R.,
define the offline reweighted squared loss regression objective
En(g: f.P) = E.,,p((s, an)llg(sh+1) - -(ss:an))13)
Then for any such
E E argmin Cx: f.p). 9:5-
( ;n(als) and smooth-clipped
Further, for the smooth--lipped density ratio 2%
df(c)
x (((ss)
target function yi = Vlog a ④ CR + V log d o (ār, cRdR) from Lem. 4.2, we have
CRup
V logg argmin En (g: vi. 3
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-wiss wise manner. For each s',
- P (lss
g(s')
9,8
8.0
Rearranging and using the definition of E. (Bq. (5)) gives the result. The second statement follows from Lem. 4.2.
22

---

Proof of Prop. 4.3 Part follows from the gradient formula
B-1 (x + 1010- = 11331
0g (z, - = x
It can be that 0,0 (2) [0, 1] and is non-increasing in its inputs, thus is monotonic.
Additionally, la (I, c) a (x', c]l I l x'|. Since a is symmetric in its arguments, we also have
|0 (ar,c) 08 (x,
dl.
Next, we prove Part 2. Let 2 = (I A c). and observe that 2 - a (I,c) = 2 - a (2,2) since o is monotonie. Further,
(2,z) 2)
(2z 12==0)-111 =1 11 1/8
1 8
2
Rearranging and plugging in the expression for gives the result.
Part 3 can be derived algebraically (but not easily), and is best intuited from the plot of the maximum z'| in Figure C.2, which corresponds to La/e e in
slope sup=,a' (,, [ (z, c) - 1x', (x', ,c) // the RHS of the bound. The left plot shows that the maximum slope increases linearly in 3, and the right plot shows increases inversely with c. The dashed red line is a "guess" for the exact constant La/e 0.33 /c. that upper-bounds the maximum slope. Clearly, L 0(3).
Varying A
Varying c: fixed A
30
12
10-
Moximumass ml
10
5
8
[[a,c) [(a,c)-i(2',))) Lo/c.
Figure 2: The y-axis plots the maximum slope sup, r, ,,,'
x-2'
Proof of Lem. 4.2
Using the chain rule,
vdh (s')
Σ P(slls,a) (V vo ((,
8,a
Σ P(s'ls, (c) (Vlog (
+ V Ch
(a (1lgm)
5,a
v log a (s), oh)
where in the last line use the definition of Ph-1 from Lem. 4.2 to make change-of-measure. Further,
V llo (s), dh Vdj (s) 0,0 (s), Ch_) dh))))
log (5) (T))(()) 0.0 (8)- C (R))
23

---

v log log @ (g))((s), Ch dh-
by definition. We can make the analogous statement for V log - Next, using the same change of measure in Def. 4.3, we have
(o') =
3,0
The lemma statement follows from V log di (s') Eq. (5). The gradient magnitude bound is proved in Lem. C.2. Lemma C.2 (Bounded gradient magnitude). Suppose differentiable almost everywhere. Under Part of Asm. 4.1 and Asm. 2.1,
and the definition of D.P in
max h
Vlog (s)
S GG.
Proof of Lem. C.2. As a consequence of Asm. 4.1, which states that the gradient of a is nonincreas- ing the first argument, for any z, c we have
a (I,C) = L'" Ono (z, 2 /0- 0200 (x, (), x 020 (2,c)
Then
substituting V log (s).
( and
(s), the above shows that Since Lem. 4.2 involves valid (con-
< v log dg pointwise.
ditional) expectation, for any E S we have
V log di (s')
0
- max
( ( Cn (4
Vlog
< G max
max
Vlogo
< hG
where 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:
Jh 5 ( (dh-1 - max | Tu (-1s)]l
For the second term and any 8,
| (-18) - - (10, -mh- ^ Ca -Z 1
< Dz (1) (1)ss)) - D.
For the first term,
j C C2 (2
(T ^ CH dh
< 0 di. d= Ch Ch
( ^ C 1 dh
)l1 + -h-))
1 - (dh A C - d
Dr (ā ^ Ch. 1 |||
where in the last line we use Asm. 4.1 to upper bound the first term, and the properties of the pointwise minimum A to upper bound the second term. Since ( Cj. di S d S dh-1 have
J5 - T 2DD + Jh Tht < <h(D Dz)
24

---

after rolling out the induction. Then for any x,
J(T) - J(T) -
dp
dj
22 Dr
h=1
Lastly, let 7 argmax, Felle J(T), and define H" similarly. Then
J(#)) J(#*) S - 5 2
C.3 Proofs for Sec. 4.3
First, we give an example of G that satisfies Asm. 4.2 in low-rank MDPs. Proposition C.I. Suppose M is low-rank MDP (Def. B.1), and suppose p is known. For each layer h define the function class
1 TT M
E 3 E R², , 1eghlllle SG vh E |mI
Gn -
Then {9h) satisfies Asm. 4.2 and has pseudodimension (Def. F.1) dg. = O(kp).
Proof of Prop. C.I. suffices show that, for any S A + IR,, reweighting function p A R4, and [H], the gradient update Lem. 4.2 has [E fl 9ht1-
Fix J, and h. From the definition of EyG, we have
[X]((+)- En,o ((d))s,a))((a)))) (s, a)p(s, (s. E.a a) (als)d (s, a)p(s,a)
Then since a() (o(s, a), p(s')),
apply the same steps as the proof of Prop. B.1 to show that there exists V E Rxx and vp E R* such that
[E(((s)) = mus') Vs' E.
(xs')
Specifically, &5 = Eeo () (als)) ()) and the p-th column of v is Wp E.o M(s a) (als)a
Proof of Thm. 4.1 For the remainder of this section, we define the constants Ex and mlle to be the estimation errors of S and dD, respectively, such that for a given a and any h [M] we have
w/
1.
=
d
mle and
af mll
We can obtain such estimates using Alg. 4 and Alg. 5, and direct application of Lem. D.1
with union bound gives giule = 0
log [ and similarly Thm. E.1 states that wreg
logí (1/)
Next, recall that
V.((T)
Rs (s').
D
h=0
(s.a,)))
The expected value over draws of Dgrad is
B Darad
Σ
E
(0 (S)
s
25

---

First we bound the statistical error from using samples to approximate vJ(()), given the gradient estimate. Fix the other datasets, then
[J(T))
- V max
(d
pE(p)
S vP
Σ CRCA
max pE()),EE[H]
E -
P.
[s')] - E. p.1 gh (s')l
S vD
Σ
staa
(12)
h
where gxtat HGV
log(SpH1/5)
obtained by using Hoeffding's with 8' = 6/4, since the random-
2n
ness in @ and 1 are fixed. Then for any p E [p].
aad {](TT] - -vJ(m
Σ P.t (s') (0) (T((') - wx(( v Vlog loggd((s))
h
Σ
P.t (s') (s's))R (5') (s') (MT - V Vlog o (f()))
Σ (5' (s('))(())) (107(5)) w (s(()
+
S VP Σ
hG [00g - wlll , + max
[oN""
v log oī
(13)
pE[p]
1,g
The first term is bounded by Thm. E.I. For the second term, use the following decomposition, which is proved at the end of this section.
Lemma C.3 (Gradient estimation error decomposition). Let mll and E" be such that for all h E [h] and x E lle, we have
a - d0 11, 112h
&D.t 11 S mll and | W 1ill,app SEN
Then under Asm. 2.1 and Asm. 1.1. for any p E [p), T7. from Alg. 2 satisfies
1o 7 log
Jx
S
(data distribution estimation error)
1,55
33hh.GG 6%
(occupancy estimation error)
To. -B (V log アー -r 1)) 1.5g
(statistical regression error)
+ 11 V log cr 1,
(recursive term)
From Lem. C.4, we have
112
9h 1,
S 2 01++0
Cg. mlle )= + 2hG (20%-1Emll mll + =
dg Cn NAG (6p11/11
where of in Lem. C.3, we have
O(V
Then plugging the above into the decomposition
P
log dm
< 110
$ + 5hG e
1.27
+ 2
2 (1
Cx
_ reg + +1gh_1
5/
V log J 1
26

---

Unrolling through timesteps, we have
4" log d%
GOh' Egggg
+ +5h
Σ Σ
2(1 Cg=n
) )
1,
gsh
gsh
95h
s G10H'
Σoger)
emle + 5HH +
Σ
res (v2 07.- c...
b
Since # S CR En C.) + V2 C,C,) e mreg
0 V log oh
1,
& GLo
C9C mll + +5V211GLo
Σ
E ewreR +
Σ
reg
(V2 + c.
hh
Finally, combining with Eq. (12) and upper bounding gntg further, we have
S vp Σ CRRR ( (SRM)+25/1* GL, + 55/21& wrek) + vp 1122 + mle
Σ ch
(max TeR e
h
Combining inequalities and plugging in the expression for each e, we have
-J(m)~m((()) $ cv depH Ex CB L3 log( (11188))
Additional results
Lastly, we state and prove the helper lemmas used above.
Proof of Lem. C.3. First from Lem. C.I, the population minimizer of Eq. (10) given p", Dhh1 is
gh = 5 where
S == E (V log ã + 0%-1
f = E 1 (1)
Below, superscript p to select the p-th parameter of gradient object. We first separate the statistical regression error by decomposing
V log d
9h
TP
<
119
T-P
0I 11 + V log di
9h T.Pl 1
1.5g
1.1g
The first term appears as the regression error Lem. C.3. Since V Flog dे. = Vdl/df, for any p E [p] we have
V
V log di
gh
J.
di
Sh
1,77
di
<
dh - 1%
Sh
+
TTP Aop
1
11
|1 1l0
||d;
f ||
< 20
11 o0
d
11
|
+ 115
(14)
The error || f/ bounded by Lem. C.5, and || 11
|9 is bounded by Lem. C.2.
27

---

We will bound the second term above. Letting 9h-1 == V log Oh be the (true) regression target and using the gradient Bellman equation for V log dj in Lem. 4.2, we have
11 1-p--Pa v 1
h- (V log ग + 1
TP E
V log + (T=
( - -
4-1 h-1
p
log log
06-1) ( Ch-10h-1) in (V" T -
0
hh 1: 1h-10h-1
4 log - + -
d 11 Cr -h-1 1og +2
+ Ch-1
(G
| -1-10000 1idp11 - 1
$ 0 (h- 1h-10p
70
2. - 0 11 1 , h- J.P
+G||o
Ch- 1h- - (dh-1, Ch- ||, + - (G+ || - 2b-1lla
$ 1 Ch-1 1
70
0 (Jh -h _ 9
+ GGlld_11 - - + -h (2G + 19 1l(0) |1hh11 - -dR--l1
(15)
Now consider the first term above, where
- o (T. and wパ- = V log df o (d%-1,, (h
Then plugging this into the first line from the previous block, we have
0 0--10-111--111 -.- Th-1 - c
Ch yh-11
1
lo ( 1: 1h-1 -h- ) i (d--1: Ch -h
T.PP 9h-1
Ch
Ci VP 1og
-
7p log dj 11
+ 1| 11o (h Th-1 i (di Cr -2- - -h-1) (f (1
(16)
where we add and subtract a (T Ch- i (d ity. The first error is the recursive term, so it remains to bound the second, for which we will use the smoothness properties of (z. e) from Asm. 4.1.
Ih-1 to obtain the inequal-
0 ch 1. Ch_ 2h-1) i ( 0 1h 2h-1) - O- xh-1) i ( -h-1 1I
11 C _ (i (JT Og
1 O
-i (1-11-11
Ch Th-1) ) [ (1 Ch Th i
1h-1 -
0
+ 1h Th Rh-1) -
1t 11 C5 20 ))
i
c Ch 1h-1))
< Log
a c 1r
h-1 - [
+ T
c 11
dp 1)
db--))
d7
+ +1[(0
(Ji
02-1chh)
ID
σ 12 C
)|
$ (To +1) T
t ||| + (Trr + Ch-1)
1ap ah ||
(17)
Lastly,
s 0
DD
+ 1000
(18)
28

---

Finally, after combining Eq. (14), Eq. (15), Eq. (16), Eq. (17), and Eq. (18), we have
p log Ji
In -.
T. 9-1 - VP log d 111.
1.g
+ 115 - -9h" 1
+ (G+ + (Lo + 1) + [19 1000= - 0% 10%-1l22.p2
+ C -h-1 (G + (Lo + 1) - (1Gill50)
[20.]
n-
+ (2C + (L. C -11b> 119
| d--
Plugging in |1 I hG and consolidating terms, gives the result.
Lemma C.4.
With probability 2 1 - for all h E [H) and fixed we have
Ih E 1 (V log -- + Th Fh-1)
D
$ 22 C 1 2 2hG (2Ch_16R1) mlle + = 1) mll geg
1,4%
(19)
Proof. Let (5' Eeo P(s'|s, a) (s, ( (als) be the data distribution reweighted
by pa. For short, we use V/
p (V log Th- + Th .)p.. For any p E [p].
P. F.Pl
T.P
T.P
19hh
Un T-P 11
1.
1.f2
10
2.
+ 2hG
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 bound
|
8,0,8'
Ch 1d66...0 Ch-11 6,a,8'
or a get tighter result with
M
σ (s), C5)
Σ P()))s,))
Th (als) (s) (s) -
dp (8) (8)
8,0,5'
+ Σ
P(s (,,0)/nnnin 1 (s), C5 (h)
s,0,s'
< C
Ch-1
DD h-
+1
Next bound |
T.P Vn
Define
Ch p) ( p(s. a) (g"(s') (V (Vlog (als) + (s))))
be the p-th parameter version of Eq. (10). Recall the regression target - then we have
1/ J.P
E EE ( T7 1) - E C (DA: Th 1)
12.5%
< 2 (4
(T): 1 1h-1) 2% (0%: TT. 1 13) + 28
(Lem. F.2)
29

---

< 2
(2% E Gh. Asm. 4.2)
Then
10
11 S 2 | |oh_ ah- E + 2hG
fh di 1
Plugging in the bound from Lem. C.5 for I5% df gives the result.
L
Lemma C.5. For any g and estimates {4h). (PP)). let pa be defined as in Alg. 2, and for any h [H] and s' 8 define
f7((') = (.
to be the next-state marginal distribution induced by reweighling dD with jA. We have
1 < 20
Jh 1Ph1--h-- -ah-dhhl dR-1/1, + 0 1110, -
Proof.
Using
the
definition of p", we first
rewrite
(s
Es,a P(s ((s')s,a)iaa an (als) (0) 1 db 1 (s).
Then
86 (0)
di
i 1.
C9 Ch.11 h-11
- - ( (h
4-1
d
h-1 C
h-1 1h
(Tp (2h-1- dh-2)
+ +110
Ch-1 (0h--1 -o (Z C
h-1
S 20 --
db_
11,
Th-
2
where in the last inequality we use Asm. 4.1 bound the second term.
C.4 Local convergence of OFF-OcCUPG
We demonstrate that OcC-OCC can converge to E-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., [[]](T) VJ(T)]] e for all algorithm, which introduces additional correlations between iterations. In the online setting it was sufficient simply union bound over iterations, and functions our function classes, because we drew fresh trajectories for each policy iterate.
Th. This is because the fixed offline data is reused throughout the
Since and He continuous function classes, will start result in terms of their covering numbers, defined below. We handle this in the simplest manner by using &oo coverings, and leave more refined amalysis to future work. Def. C.1 is covering For example, the direct policy parameterization with To = 0 has N (7, Ilee < (max, / (Lem. C. 10). In the below definition, overload the definition of (the clipped policy in Lem. 4.1) temporarily.
the clipped policy ratio over n D
Definition C.1 (Policy ratio y-cover). Let ITe be an for covering of Ih such that for any E He there exists Th with (n.CO==)) Wh. Cp cardinality.
l S Let Let.ee Ie)) denote its minimum
=
*
Definition C.2 (Gradient function class coveer)) Denote Noc (7,9) to the fox covering number of } with resolution
30

---

Next, we state the stationary convergence guarantee in terms of these function class complexities, the offline coverage coefficient determined by input clipping constants {C%, C. and L, that represents the second-order smoothness of a.
Corollary C.1. Suppose Asm. 3.2 holds. Then under the preconditions of Thm. 4.1,
T Σ B (TTT0)
when
T T= Ō
E
pH (En C.C.) (ogg
Proof of Cor. C.I First, we invoke a union- version of the offline regression estimation guarantee in Lem. F.2. For any n. g S - RP, reweighting function p S A R,, and target function y : S + IRP, define the p-th parameter squared loss for a fixed policy to be
2 - (gr " y- p) = (.... (10((0) - (V log Ta (als) + (((+)))²
Then from Lem. F.3, With probability at least 8', for all [H].P E [p]. g E 9h+1, and p. y.y induced by F, W (see preconditions of Lem. F.3 for more exact statement), we have
( - (1 ( v. p) F%. (gh+1:3. p) (g:
s Blch 1L (g:v. - 5% (oh"(9hh+i.000 + (E
(V log म. +yn and s O ( OR, No 100p811..1131//88
where 9h E, P.P
To complete the regression part of the analysis we need to take a union bound over the result in Lem. F3 for all क E ll.. For any π E lle, let E Ill of Def. C.1 be its fo cover. We need to bound the covering approximation error C (g: c (g: y, p). Consider a fixed (h, 8, a, s') and fix the inputs L. y. x), for which
CT.P
"T U: p) 2% LT (1:,,))(ss,,,1)
(x (g"(s') - (((s))-2(V"'o)) log ((()) + (s') (g"(s')- - (s))
= p(s)
* (als)
Then
" p) (g:"( p)] - (C (g.. - (T:
00 (I..GRo)) (FF073.))
+ 8C hG max | Vlog log (als))
s.a
< & + ChCLL))))
where we get smoothness of the gradient portion using Asm. 4.1 and Asm. 3.2. Then by setting = (8(C*C")2G2 + C*C*hGLo8)) and combining the above errors with Lem. F.3, we have that with probability least for all π II that
TE [C,, (Ph, th 0h, x) Cb,, (ph, gh+1, Uh. T)] Cb, (Ph, 9h+1, T) CD,, (ph, F Uh, T)
$ E[C
Uh. x) Cb, (ph. gh Uh, T)]
2
+ DF
reg
:= E
for some absolute constant c. The remainder of the proof identical to the proof of Thm. 4.1 using the above Ex which is then combined with Lem. G.I to give the result.
31

---

C,5
Global convergence of OFF-OCCUPG
We now turn our attention to analyzing gradient domination of the offline objective J(x). 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 Vd For each (h, 8, a), define
(s) == 2.0 (RA Σ P(s))s..)(((()))
+ 0g0 (T (d)+)(6'), (h+ (hildha(()) (d,
Lem. C.6 shows that the optimality gap of a policy for the smooth-clipped objective J(x) 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 isn't applicable,
it is not covered by the data in Do supported on S 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 μ dg, the original initial state distribution.
Lemma C.6. For any π and n', define Bdr (π') = En, (%) a). Suppose that VI E lTg.
1. (Policy completeness) There exists xt + E Ie such that x E argmax, (T)
2. (Gradient domination) el B (=())) B (T) S maxoree (T)* - 0).
Then for any comparator policy Th and Toe E Ie. we have
o7dR))
J( -(0o) S m max h
max (VJ(TT)) 0).
To C7 d
B'EB
Compared to Lem. 3.2, the first precondition of Lem. C.6 may be stronger because x can be stochastic policy, whereas deterministic policies suffice in the online setting. The second precondi- tion is of similar strength. More importantly cients of the form in Lem. C.6 are not ideal because they involve T. in the denominator, which are variable over the learning process.
have previously discussed coverage coeffi-
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 exploratory initial distribution to use with OFF-OCCUPG (in some sense, this, or some reweighted in the offline setting). Prop. C.2 shows that this is indeed
version of it, is the only thing available 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 En Cā
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 {dh), }. define a new data distribution where d
H- de vh E [M]. F Σ
Then for any n,, use {dp }, = A, and clipping constants {C% Oy') } to define [dī. according to Def. 4.3. Let (T) Σn (QTV,R)
For any n and n'. recall 8TT (T') := En (d)' (Q))) Suppose that V Ile.
1. (Policy completeness) There exists - E Il such that + E argmax, (TT').
2. (Gradient domination) m ello (=('') nTT (T) < max (V 8).
Then if (Cg. CR.) are such that ( < C ap', wh, for any mo Ne have
max J((T) J(mo) s mH
Σ
Cj
max V ('))) 8).
8'E0
32

---

In practice, we can easily generate a new dataset D satisfying Prop. C.2 by first splitting each Dr into H equal parts {Di then setting Dj g The sample complexity of running Alg. 2 on D' will then scale with Σn C. which are imput parameters, instead of the coefficient in Lem. C.6, which is d-dependent and cannot be controlled. In exchange, it requires all-policy coverage w.r. the new [d"]', which, while strong, was insufficient for optimality in Lem. C.6. One justification (formalized the hardness result of Prop. C.3) is that the exploratory initialization can cause policies exceed coverage thresholds (the original) dg- 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%, CR } set to be high enough, it's unclear whether doing this will require exponentially large coefficients in the worst case.
awward-generating states, despite being covered on
Lastly, we combine the above gradient domination claims with the stationary convergence guarantee in Cor. C.I state the following global convergence result. Cor. C.2 is stated for J(x). 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(x) satisfies Asm. 3.2. If Alg. 2 with DD' defined in Prop. C.2 satisfies the preconditions of Prop. C.2, then set CC = H Ch- Otherwise, define CC = max maxk oor (Thh" .C // (TR.CR CRaP) || and assume the preconditions of Lem. C.6. Then under Def. C.I and the preconditions Thm. 4.1, Alg. satisfies
max ((m) - S 2H Dr
- when T' = Ō B (B'm and
n ō 0( (B0mm"CC0)PP (CC))C))))" [Ex C.OR) 13 (2ee
Though we optimize J(r. the guarantee in Cor. C.2 is with respect to our target offline objective J(x), which implies that the learned policy competes with the best policy fully covered by offline data. Generally Lg and D, trade-off between ease of convergence (smoothness) and approximation error, respectively. For example, instantiating the bound with a from Prop. 4.3 with x e results in a final 1- 1/4 rate.
C.6 Proofs for App. C.5
Proof of Lem. C.6 We will use superscript à to refer to sh E Sh, the set of states visitable at timestep h, and drop Cj below to reduce clutter. By the performance difference upper bound for the smooth-clipped objective in Lem. C.8, we have
H-1
J(m²) F(TO) s
Σ
Σ
chh (s),dR (al(s To(als)) QT (s,a)
h=0
8,a
H --
Σ
Σ σ (Th (s*), (s())) (5 (a"1s") - Ro(a"ll"") 2h
A=U aa
since (s) > 0 only if 8 E Sh. Now define -+ such that for any 8, *+(11s) =
urgmaxFEA/A H, 2h (s, )). Then
) [((T)
H-1
Σ
T (5*) (s ( - - (s" (s")
h=0 shaat
#-1
Σ
0
(6))
(( (
(a"(a)) - ))(a"(s-)) (s".a")
(20)
4=0
33

---

0 hh "
#-1
< max h
Σ (st),,
(rttaa))") -z0(aa))
h C2
4=0 s ,n
(pp")""))))))) (5" aa
0 4 cR
H
Σ
Σ
(s"), (B()) - :7 (8") (s",
max
af .at
ck oRdR
max
max x²
B (TTO 1 (TTO)
Jne C7dR)
ch CR
(TT) 1 (TTE)
max
max Tyr
0 C2
Proof of Prop. C.2 Under all all-policy coverage, we can apply the result in Lem. 3.2, noting that do # Rh and d, I c
S
+0
Figure 3: Example in Prop. C.3
Proposition C.3 (Vanishing gradient from clipping with exploratory data). Consider the MDP in App. C.6, and the data distribution where d (X) 1/2 and (Y) and (Z) (1-c)/2 for some E 10, 1). For any C, we have all all-policy coverage, i.e., dī S Cndy for all h and all policies n. Let v be the stationary (and in this case, optimal) policy of running Alg. 2 with D' described in Prop. C.2. Then
J(TT) -(m")-((m) (1- (1 (1yeC))))....
Ife is exponentially small, J(x*) ((T] 0(1) unless Cy is exponentially large.
Proof. The example boils down simple bandit problem of choosing either or R in state X. C)) = 2Cyc, and T (R) = - =[[[X. In comparison, x* (L|X) = 1. Then
xL] = 2d(x)
j(x) = J(T) Cyd (X) + +c(1 n (L) In comparison, J(T²) = 1, so
- = c) -1-
For reasonable choices of Cz (say, or 3), Cy must be proportional to for the suboptimality gap to shrink, and particular if exponentially small then Cy must exponentially large, which blows up the RHS of the bound.
D
34

---

Proof of Cor. C.2 The first step follows the proof of Cor. 3.2. Combining Thm. 4.1 with Lem. G.5 and plugging in above, we have
Σ J(TT) - J(x((1)
BH
pH (En C,C,)² L2 (g
x BmCC
71
Then we also have
E
T J(T - )(
<
E
T Σ J(TT) - -J(r(10)
22H2D. Dr
(Prop. 4.4)
(V
3H T
G2 (En C,OR)) LA
22 + BmCC
Additional results
Helper lemmas are stated and proved below.
Lemma C.7. Suppose satisfies Parts and of Asm, 4.1. Then J(T) = (s
H-1
VJ(TT) ΣΣ (d)(s)
(
h=0 8.
where
(T(;,a)= = Σ Phoolss)) (Ram166)+ (dnti 0,0 (Ji+zld'), Ci+z2h)))))))))) (11
Proof of Lem, C.7. For notational elarity we omit Cj below. Expanding Vdd we have
Σ
P(sh18h-17 14 (at ( (8h-2), (8h-1))
#h-1 -d-1
# 1a--(aa-n1shh- 1h-11) 020
(h Voh (5h-1)
h-1
Σ Σ
II
P( a ano (s))
g<h
Ll=9+1
P(sg+1l8g a d3)) (an(a)))))
For short, define
h-1
(*(ss19g: ag) =
Σ
II L==+11
P(s al d.o (d (st), ((:)))
P(8g+118p. ag)
(eh 1h--1ih--nm1-ppp Spt.1ptt1.0
observing if 7.. = Th and 0.a Tāh ap
for all h, we have Pa (8n ag) = PM (Sa ag): the
standard transition kernel from (8g: ag) - Sh- This occurs, for example, when σ is hard clipping
and is fully covered by data. Then using the above definition, have
(dh.(s))
ΣΣ 9 g&h S9
(()(s))) dg(s)) Vāg(aylsg)) (T
(21)
35

---

Plugging this expression into (T( we obtain
VJ(T)= = Σ Σ
V. (5h
(s))
8h
(e Vig(ayls ( (s)lsg.ag)) R(SN)
h
8h
9=0 0g
#-1 Σ
H
d (sg), dg()))))))))))))))))))))) (
Σ Σ
pd (oulogr ag) R((n))
g
8g:4g
h=g+1 on
H
Σ
(d (
=
9=0 fg
where we have defined
(g)) = Σ
Σ P ay)
hmg+1 8b.
Σ 1(5g-115g.ag)
R(18+22) + Σ
(attllgg)))) 0.0 a (T)H((041)) (pH1()11)))) (0
as+1
Lemma C.8. a is concave in its first argument, for any nO and π we have
H-1
- J(T)) -
ΣE THh (s).
(F)(ass) (alas) (7,,,)).
h=0 8.a
where Q7, 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. a concave in its their first arguments, then for any h and n, T'
(s')
(s')
Σ Σ
TH (s) (o (2 (Ta(als), 2 (als)) PT = =s'18, = =8,00 =a),
geh 8.a
where
h-1
p (g)]
Σ
II L(=++1
91 2.a (f)))) p(tgtalsg)
18 1ot1
Proof Lem. C.9. Define 7 ( m -p.-.-,T---1. 1. i.e., policy that starts playing timestep g. and plays nt for the timesteps before that.
T. (s') (s') Jे. (s') J. (s') + di (s') (s') (s')
For the first pair of terms, n and nh" only differ the policy used to take the action an-1 (and both play x' before that), thus d d= and
T (6) - "
(5')
Σ a)) (a (r/s), (alss) - a ( m (als)) (5),
3,0
36

---

For the second pair of terms, x²ー1 and æ both play at time h - 1, but the former uses I' for timesteps I....,h. 2:
(5') (s')
Σ (0 (F) (o (s). a (Th. (s), (s), d
= (
(5) 15),
8,
$
Σ
0,0 (s) ( (s) (
where the last inequality above uses the concavity of 0² in the first argument (recall concave func- tions f satisfy f(y) - f(x) + (z) - z)). Combining the above two inequalities, we have the recursive relationship
dh (8)) - (5')
(() (
(R ( (s)-1()) (T)
8,0
(T)- Ogo (h (Th-1(s) Jh 1
Unrolling through timesteps gives the lemma statement.
Lemma C.10. Lel C maxa Cº. Suppose He is the direct policy parameterization, i.e. To(als) 02.a: and a such that Do S C for all Then for any 7 E (0, 1]. in Def. C.I we have No (7, ITe)= S (Ca /7)
Proof of Lem. C.10. Typical gridding-styy style arguments discretize the range of ((ass) for each (s, a). Since we are concerned with creating a cover for the policy ratio, however, a naive argument will incur 1/ min.,a x (als) in the grid's cardinality. Our solution is to grid IT adaptively according the magnitude of x (a s). Intuitively, only need to grid up to the threshold
For each (h, s, a). define the adaptive gridding scale be Thea yT (als). For any и Igg set its cover स as follows.
s(els) Then CR T (als), otherwise.
ial(a)s) < P
T (als)
Let II. : lo}. Then [Tol (max,, Ch/r)) MSA, Further,
(T<(a)s) Cg (als)) - (Fn(a)s) A C (als)) S yαk ( (als),
thus ( 10x0 S 7, and applying Lem. C.11 gives the result.
Lemma C.11. Suppose Hh satisfies Def. C.I with owc (x C). Then for any a E Il. let E Th be its cover. Under Asm. 4.1, we have
CC(++DD +
Proof of Lem. C.I.. If (((a)) Cn using the 1-Lipschitzness of have
lo (=(a))), C Cx (als)) (#(als), C+ C+P(())))
= lo ((T(a)s) A C (( Cr (al(s) - a S A
Cx (#(als),C**P(l)))
#(a|s)]
37

---

Algorithm 4 Maximum Likelihood Estimation
Input:
datasets }. function class JF 1: for h = .,..., H do
2: Estimate marginal data distributions 2h-1 and 2 by MLE on dataset DA-1
Th- arginax 1h-1EFn-1
log (dn (s))
(22)
DD
(KT))ER
7. argmax drEFn
Σ
log (d, (s'))
[D
3: end for Output:
estimated data distributions {4h he[H] and (7 (
S Cyr (als)
If (((a)) C+ (alxx) lo (=(als), Cn (als)
Cx (x S (al()))) (F(als), On (als))
CC - (1 - -D) (
^ ((P(aas
s < + 77)x
using Asm. 4.1 in the second inequality. As a result.
a (a (x (a|s)
< CC(+ Dz)
(a(s))
D Maximum Likelihood Estimation
Algorithm displays the data distribution estimation procedure used in offline gradient estimation (Algorithm 2), which is direct application of MLE. The general formulation of the MLE problem utilized this paper to estimate a probability distribution over the instance space S. Given an iid. sampled dataset D {s(0)m and function class F, we optimize the MLE objective of the form
= argmin JEF
Σ SED
log (f(s)).
(23)
D
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 well-established result (for example, proof can be found in Appendix E of [AKKS20]).
Lemma D.1 (MLE guarantee). Let D (1(0pp pi be dataset, where (( are drawn i.i.d. from some fixed probability distribution f over S. Consider a function class that satisfies: (i) f F, and (ii) each function F is valid probability distribution over S (i.e., f E A(S)) Then with probability least
8. from Eq. (23) has & error guarantee
log F1/8)
18-
The formal guarantee of Algorithm 4 is stated below, which is straightforward application of Lemma D.I with union bound (over all functions in F, and over all timesteps).
Assumption D.1 (MLE Realizability). Suppose that Yh E [b]. we have dh. d. E Fn for D defined in Def. 4.1. Additionally, f e A(S) is valid distribution for all Fr.
38

---

Algorithm 5 Fitted Oceupancy Iteration with Smooth Clipping
Input: policy n, datasets {Da). function class W, clipping thresholds {Cx, C... data estimates
[dh) and (dh
1: Initialize di dg
2: for 1,... H do
3: Define DD.-1 (w/, wh T--1) 11 = P
Σ
[(sa, (wn(d)) w/-1(s)
5y ((ll))
and estimate
argmin LDa-1
Wh:
o1ch-1,
50 (Th-1, 02-1
(24)
02
w.EWh.
4: Set the estimate oz 17 -
5: end for Output: estimated state occupancies {ūn hNE(H)-
Lemma D.2. Suppose (Fr} satisfies Asm. D.I. Then with probability at least 1 - for all h E [H]
the outputs of Algorithm satisfy [2p db) S emll and 2hh
a. S mle where
2log (
mlee
E Offline Density Estimation
The algorithm for offline density estimation is displayed in Alg. 5, and is directly copied from Algo- rithm of [HCJ23], but with two minor modifications. The first is that the densities are clipped using function σ, that can take clipping a special case. The second is that outputs the learned weights instead of the learned densities. The weight function class completeness assump- tion shown Asm. 1, and is satisfied low-rank MDPs using linear-over-ling 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 p and in that sense strictly weaker.
Assumption E. (Weight function completeness). For any E Iī and h [H], we have
(w. -
5
Wh, Yu Wh-1, Vf. E Fn-11
Theorem E.1. Suppose satisfies Asm, 4.1 and W satisfies Asm. E.I. Let (d and (2P.tt be such that Vh [H].
d
S mle and
(p. -a mle
Then with probability at least 1 - 8, the outputs {ūū,} of Algorithm 5 satisfy for all h e [H]
[0
क al. <
Σ
Cg +2 +
Cz 9<h
mle + v2
gwreg (25)
g<h-1
g&h
where gweeg_..
log (1
for some absolute constant c.
Proof of Theorem E.1 We begin by stating the following decomposition the error of of which is proved at the end of this section.
Lemma E.1. Suppose a satisfies Assumption 4.1. Then for any h E [H], the error between प6, and D.t the target WT = - /...t can be recursively decomposed as
| T6 11,444 < [ 1. 111..01111
39

---

20 aR d
||
CR
d
+ w
- (dh-1 wh-1) 2,
where w == -R d
Applying Lem. E.2 with union bound over all h, we have
W - (dh-1 w/: wh-11 1 2
E CDNy, (wh, w x) E LDYE, (E (dh- wh-1), 1)
< 2 Cores (wh, 7) Lopee (Bi (dh- wh-1) wh R)) + 1Ch-1 (h1 (6
Then unrolling Lemma E.I, for any h, we have for ewrey
clog( H WW/388))
Preg
|000 1Il &
Σ gch-1
C +2
+ gth
mlee + V2
Cg Σ
Eggcn
Ewrez
94h
Lastly, we state and prove the intermediate results below.
Lemma E.2 (Deviation bound for regression with squared loss from [HCJ23]). If [Wa} satisfies Asm. E. then with probability 2 1 - 5, for any h E [H], there exists universal constant such that
Laps (wh+1, Wh, n Ly E wh: T))
(Crgr (Wh+1, Wh. T) - LDy EE* Wh. Wh, m))
c()7 2 log (H (1/0))
E (Dxx (Wa+1, Wh TT) CD EE whi Whi m)
Tlrgg.
Proof of Lemma E.I. Decompose
10 1
(T--1:0--1
<
Wh 1
dh
+
wh _
dh-
dR-1
dp-1
2.4
P.I
The first term is the statistical error of regression. The second term reflects the bias between the popu- lation regression solution (involving plug-in estimates for the regression target) and our target weight function. Since dī = Pn-1(( (o ch
then पū En-1 (o ((
for the second term we have
dh
W
E h-1
d
ap
1 Pit
dh-111
C
Ex-1
(0
E
dh-
h-1
1.
(dh C
1
Ph-1
( (TT - P カー
DD
dh-1
d
Ch-1dh-1
ch-
2D
C -h -d
dh
40

---

0 22
dh
o
( -h- 1h-1
-0 0h
1
2 Jh- dh
||
+
1h-1 8h
(Assumption 4.1)
1
Finally, since 0//=1 = w/h 11-22
| - Th =
Dit
1 1-2
pDi
-h
h-2
S | Jh
+ 10
0x-1 11..1
Combining the inequalities completes the proof.
F Probabilistic Tools
Definition F.1 (Pseudodimension)) Suppose a function class FF C R*, and øj = {2,)²= X
We say 21 is pseudo-shatteree by JF if there exists E R" such that for all {-1,+11", there exists f E F such that sign(f(ff - c)) = y- The pseudo-dimension of F defined as
dz max(n N 3rd E X s.t. 24 is pseudo-shattered by F},
i.., the cardinality of the largest set of points in X' that F aseudo-shatters.
Lemma F.1 (Lemma 26 from [HCJ23]). For b 2 1, let H S (Z + [-b,b]) be a hypothesis class and z (Z1,-.., Zn) 2", where 2; are iid samples drawn from distribution supported on Z. Then for any E H. we have
[[h(2)]
1 Σ (Ei) (E)))E TE
20
36N1
H,
40nb²
exp
ne²
6405
g2
128V[h(2)] + 512eb
Lemma F.2. Fix π. For any E [H] consider functions yh S A ThGG,GG and Ph.
Sxx A [0, CR. that depend only on the datasets Dighe and DFORC and Derad Let G {
be function classes and with pseudo-dimension dG (Def. F.I). For any gh+1 -94+1 and p E [p]. define the loss function
(gh+1i yh. Ph. n.
Σ
(h a) (5) (Vlog (als) + as)
(s,a,"))ED
Then with probability at least 1 8, for all gh+1 E Gh+1 and p E [p] and [H], we have
B (gh-1: 1: Ph)) ( Uh Ph)l f% (gh+1i yh. Ph) S% (9h+49941:00 2h Ph)
< B(C ( (gh+ti yh.
10. Ph) CT (fh+1ig Who Pn)l + (=
2
where Th41 = P.P log मe + yn) and for some absolute constant
do0 Ca C2_, log(npH/5)
reg h
ov
(26)
Proof. Fix Dmlle and FORC and Dered We first prove the stated bound conditioned on these datasets, which means 9f and P% fixed, and the randomness below comes from random draws of Derad Consider the following hypothesis class induced by Gh+1:
Z(hh. 9h+1,9h) (ps a) (gn+)(5')
(s, a))² (9h+)18') - (s)))))) (((l)())))( gh+1 Gnti..
and for any Z E Z, we have |Z| < 20 (Ion+tllss + l1unl(z)) < ACRORA262 We also have E|Z"(p, (p, +1 yn)] = |1
9h+1 1 Further,
+.
V [2 11 2nde E[ZP(pp 9h+1, 3
41

---

p)(s,a) (n) - yn 3n(s.a))))
pa((s a)? (s') (yh(s, +iii(('') (oh+2(5') gh (
160 (n(s, a) (oh+z(6') - 9h 1 (d'))
16C G (Ph. Ih+1,
Next, we show that the uniform covering number of Z can be bounded by the uniform covering number of G, since for any 1 Fh+1 E Gh+1 have
(ph, 9h+1. Mh) Z (Ph, 9 Wh)] pa(s, a) (9h (n(s, (gh+2(s') yn (s, a
< 1607, + (9 - gh+1(s')l
In other words, any 7/ 7/166 - Ch above with Lem. F.1, we have
h covering of Gn covering of Zn. Then combining the
G²
P
B B[Z"
11h-11100 (P Ih. Uh 1)1 Σ 27 (ph-1: 9h 3h-1) =E
(40m(Ch-117-11) 1/
2 36N1
102400,,C81200 29 Ph- Uh 1h-1),
8²
n
exp
2048C 1048CR-192 Ch_ 12 2P (ph-1: -h. 2h-1, TT
2048:07_1
Ch C2
640m(Cr, 0
< 36NN
Ih. (18840(C;CB)2118))
E²
no²
exp
204801 12 G (ph-1, Ih. 9h 9h-1)) + 2048 C Ch h22
640n|Ch 18, 6
Define
W1 ( 9n:
Then setting the RHS equal to
8', this implies that
2048C h-1 Ca_ 1 G2 (T (ph- Ih, yn 1)] + e) log (36N/8')
g2
and
2048C7,-, , h²2 log(36N/8') 20480s R- C 122 (PPPE(ZPPPP-1 Ih, log (36N/8")
8 S
n
n
Since n 2 2048C CD G²
there exists an absolute constant e such that log(36N/8') s edg log(n/ 8¹). Then with probability at least 8',
E E[ZP(pn-1 (Ph-1, 9h, Uh 1)1
Σ Z (ph-1, 9h. 11-1)
2048cdg, Ch Ca 112 E (P 1. 9h- log(n/88)
2048edgCT,_10 Cj. 12² log(n/8")
n
B[ZP(ph-1. Th. Wh- 1)] 3072edg 12 2
Since the above bound holds for a fixed datasets, also holds for the expectation over the datasets. Applying the above bound for all E [p] and h E [H] with 8' = 6 6/HHp Hp and taking the union bound, then plugging in the definition of Z", gives the result.
Lemma F.3. Fix h and denote the product class composed from G, W, F to be
3h x Ph. = (v.p) y= -
(ww5',33)) 9h E Gn, w E Wh. F E EFo
42

---

Fix π. and E [p], and define the loss function
(g:
Σ
pls) (x (als)) (((sss)
(g"(8') - (VP (V + (8)))
(s
Then with probability at least 1 - 6, for all h E H.) E ipl and g E Gh+1, (v.P) E Vn x Ph. we have
(5:1,P) "
-hh (fh+ p)] L% C () CT 1hh+1:
Σ 2
Blch Pl: - C, (h p)] + (=h+11)²
E, ( Tn + yh. and rog h 0 o (o (00
where Fh+11 ED
Proof of Lem. F3. Use the same notation for 2 as in the proof of Lem. F.2. Using Bernstein's inequality with union bound over all W₁, and Fn and the too covers of Gr. Ga+1, with probability at least 1 - we have
EE[Z" (ph. 91+11 Uhhl
2 (Ph: 91.
2V [2P (ph. Mh+ 1, 9n log (WIFF (GGC)FGG
3n (ogCCI/(Foog//NNsee31W1111 3n
G2 Uh 9n)) log( (e +
By accounting for the lo covering error, we then have
E E (ph. 9h+1 mnh] (ph, gh+1,gh)
( + 166
3n
Using the AM-GM inequality with = = 0(1/C,0 gives the result.
G
Optimization Tools
Definition G.1 (Gradient mapping).
1 - - Projx -r-rroxx (x + ngg)) 1)
(x =
(27)
Lemma G.1 (Stationary convergence of PGD). Suppose f X - I. is B-smooth over X, nonempty closed and convex set, and that we have access to a gradient oracle such that [xg = fz(x) and [[]lg(z)= fz())) < 2 Then if n 1/8, have
48(Jo - 1*)
ΣΣ E G (I((t)
(f <
+ +
T
T
Proof. For any I, define + = Projx (a - (z(x))) Since x = prox 1x (xr - 1g(x)), where Ix is
the indicator function for the set X. from Lem. G.2 we have
(x ng(z) x x s O.
43

---

Rearranging, this implies
(o(x)) xt ----)) -x) + "
+1- x+12 s 0.
Next, since f is 3-smooth, for any x and x we have
f(xt) - f(x) + (Vf(z), 2)
2 || x+12
= =f(x) + (o(x)) - 2) (V/(+) g(2)),x -x) B -
2
<((c) (o(a)) V/(s), (1/ 11 [["'),,(()))
= =f(x) + (9(x) Vf(x), Vf(x))) (g(x))) 1
( V((x))
1) -n)
|,
2
where we substitute the definition of G* (x. (xx in the the second to last line. Notice that
(9(x) (= Vlx, - [l)(()) - - Gz,
< [lg())) /(()]
from the non-expansion of the projection operator. Then we have
(22 -n) ||=T(z.(()))1
(1²8
f ((())+((((())) G" (f(x))))) nlgg(=) -
S
Next, we take the expectation of both sides conditioned on x.
[[[(x+))xx) s [(x) + ( ( G) V)(x)))
728 - 7 (z.
+ nB]lg(() - vf(x)|] + 2
{ - G [1x)
S f(x) n +
Then unrolling the recursion through iterations and substituting " = 11/3. we have
T Σ Gl (2 (((())))) 23(S(x(0)) - ((x(1))
+ 2 2,3 22(((xx(0)) - S(x)))
+ +02
T
T
f is nonnegative. Lastly,
1
(z'"") Σ (x((" VS(a = - Σ (x )((00) -Ca
+ Go (C* v (G)
T
< T Blllo"(>! 0112 2
2
Σ
T Σ (xl))"((!t) 0(x(0))))))))))))))))) - (z) (f(=(0)))1
48(f(z(0)) - f(x")) + + Σ Blllg(a(()) ()(
T
- 48(f(z(0))
T +
Lemma G.2 (Theorem 6.39 from [Bec17]). Let : E - (0o, cx] be a proper closed and convex function. Then for any I, y E E, the following three claims are equivalent:
1. y prox (z)
44

---

2. x Ōg(u)
v) S g((u) g(v) for any E E Lemma G.3. Suppose f is M -ggradient dominated and B-smooth, and
3. (x y, u y)
T
where (x, 9) is the gradient mapping defined in Def. G.I. Also, suppose || - 2'112 S r for all 3' E X. Then
min TE[T]
- S F (n + 1)e.
(28)
Proof of Lemma G.3. If f is gradient dominated, for any t E [7'] we have
f(x") fxx(1) S M max x'ER (V 2(0)
Applying Lemma G.4 with -f, we have
ff(x()) E Nx(x + B (in3 + 1)|lG (x((((-1))))
From the definition of the normal cone, have (u, - =(1))> s 0 for any (x( and x' E X. Then for any x' E EX
Vf(a")), - 2 s (n3 1) (z(t))) "f (f( ||- 21) s (n3 + 1)r (x v (z
Combining the above inequalities.
min (a(h)
< (n18 + M) min (G*(((t-11) ([(x(t-1))) S (1 + 1)Mrs.
rE(T]
Lemma G.4 (Lemmaa 3 from [GL16]). Let f Rdd + (-o0, oo) be be B-smooth over a convex set X For any E [T], consider (t-+1) = Projx (x - V/ f(x(t))). Then
(V((t((t E (1 B (n13 + 1)]| (zx (V))
where Nx is the normal cone of X and B(r) = {u E Rd ||>||| S r)
Proof of Lemma G.4. Projected gradient descent can be equivalently written as [Bec17]
Projx (z00) (600-1VV6 vV((((())) argmin zERd
[raa + (VI(a")), x- 1er-xxh x(())
1
| =01 1x(3
2n
where [x) = 0 if x E X, and toc otherwise, is the indicator function for X. Then by the subgradient optimality condition, we have
0 E v)(x()) (x((1)) - x1)) + (x((1((-1))
With some rearrangement, this implies that
((x((())))) E (x + (zx(()) -(((((+)) + (1(((+1)- -x(0) x(0)
which implies the lemma statement since
- (((ttt)) s -1(1(()=z((11)))
1 (12(00 (0+2))
S <n3 + (z(() v(((())))
using the 8-smoothness of f in the first inequality, and Definition G.I in the second.
45

---

Lemma G.5. Suppose f is 3-smooth and that at each iteration t. we have g() from gradient oracle such that E [gg(t) |x(")] vf(a()) and E [Ilff((!)) g [| I for all [T].
Then gradient ascent using } satisfies
|
(0)
23(Ju - 5*) 8².
T R
(29)
T
Proof of Lem. G.5. From the 3-smoothness of f.
f(zlt+1)) S f(x())) (v((((()) )2 (1+11) x11)
B
-1((t1))22(1111
-2(1))1
= =(((0)) ( (vf(z(()) /1(11) + Bn
111
2
=(([(0) (V)(=(()) V)((((()) vf(((0)) + )001) + Bn?
2 - + g
v)(x(00)
=(((0)) [Sn] f2 + (Bn² n) (ff(z(()) ( g(t vf(x())) 318² [V)()(1)) 11
Taking the expectations of both sides conditioned on (1)) (prior histories), we have
)1( = fxxl0) + [ -n -) [ + Bnp²=²
2
Substituting - 1/8, unrolling through iterations, and using the law of total expectation gives the result.
46

---

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

---

Answer: [Yes]
Justification: We fully disclose all assumptions and discuss their strengths and weaknesses. While theorems/lemmas in the main text are not cross-referenced with pointers to their proofs in the appendix. the appendix is organized with table of contents according to section, and proofs are clearly labeled with the theorem or lemma they pertain to. We did not have space provide proof sketches in the main text, but, where possible, we attempted to provide a brief intuition.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We do not have experimental results other than the graph in Figure 1, which is plot of 1-D functions that are fully disclosed in the caption and referenced proposition.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
48

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome 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 possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: We do not believe that Figure constitutes as an experiment that requires code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
Policcy)l for more details.
While we encourage the release of code and data, understand that this might not be possible, so No an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips. cccpublcc/geeecccccccccccccepcee httggguddd//coeee www.ssuummiisiiiiims ssi iesionPorr onnolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Per 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 level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined other appropri- ate 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 emror.
Guidelines:
49

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, 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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors 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 out of range (e.g. negative eтror 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http:///eeriss.eeee htwpai///ehhcchiiiellllliielee
Answer: [Yes]
Justification:
We do believe we deviate from the Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
50

---

Our paper is purely theoretical, and we do not believe there is societal impact to be discussed. We do not see direct path negative applications.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g.. deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (c.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not use data or train models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not have code, data, or models.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
51

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license. copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswi neewwhhoode com/ datasets has curated licenses for some datascts. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
There are no new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We do not use human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do not use human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
52

---

Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do include any information that would break anonymity (if applicable), such as the institution conducting the review.
53


Reviews:
[{"review_id": "lfeaamgjBk", "reviewer": "Reviewer_2KwR", "summary": "This paper investigates the convergence of model-free policy gradient (PG) methods that compute the gradient through occupancy.", "questions": "See the 'Weakness' part.", "limitations": "See the 'Weakness' part.", "rating": 3, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The convergence analysis and the theorem appear to be sound.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your comments. However, we respectfully disagree that our paper over-claims its results. The reviewer’s comment that “the coverage coefficient… removes the need of exploration” likely results from confusion over the term “exploration”, whose meaning in the PG literature is different from that in PAC-RL. Our use of the term is aligned with the literature, and our results’ dependence on the coverage coefficient is also standard. Results of a similar nature are commonly found in the literature, and we elaborate on the details below.\n\n\n---\n\n\n**re: \"The convergence depends on a coverage coefficient, which removes the need for exploration\"**\n\nIn (online) policy gradient analysis, the coverage coefficient $\\mathcal{C}^{\\pi^*}$ (Lemma 5) expresses the difficulty of the exploration problem in policy optimization. L184-188 discusses this in-depth. \n\nThere may be some confusion over terminology because our algorithm, along with routine PG methods such as REINFORCE and PPO, do not actively explore in the sense of PAC exploration (e.g., UCB and other optimism-in-face-of-uncertainty algorithms). Rather, exploration here refers to the difficulty of finding a good policy within the policy class from online interactions with the environment. \n\nThis usage of the phrase “exploration” matches foundational works in the PG literature, for which $\\mathcal{C}^{\\pi^*}$ is also the standard notion of online PG complexity. They are identical to Definition 3.1 from the seminal work of [AKLM21], and the paragraph above it (modulo differences in infinite and finite horizon MDPs). Definition 3 of [BR24] is another point of comparison. All of these coefficients depend on how well an initial state distribution covers the optimal policy’s occupancy. \n\nThat said, we should have defined “exploration” more explicitly in the abstract/introduction to reduce confusion, and will revise accordingly. This is a simple fix that can be lifted from L184-188, and that is aligned with standards and terminology from existing work.\n\n---\n\n**re: \"the obtained bound does not indicate the number of samples needed for exploration when the initial policy is not good\"**\n\nFirst of all, the coverage coefficient is defined with respect to a _distribution over initial/starting states_. This is _not an initial policy, or even a policy_.  \n\nMoreover, a good coverage coefficient does not necessarily imply a good initial policy; the initial policy can still have poor performance, and we rely on gradient ascent to find a better policy through online interactions. This is what the PG literature means by “exploration”. \n\n---\n\n**re: \"Additionally, the proposed algorithm does not address the problem of exploration\"**\n\nAs argued above, the coverage coefficient in our online bounds characterizes the difficulty of exploration faced by policy gradient optimization algorithms, on par with the existing literature.  \n\nHowever, developing algorithms that actively explore to improve policy optimization is a valuable direction of future work, given that in practice the initial state distribution may not be very exploratory (aka have poor coverage over $d^{\\pi^*}$ per Lemma 5). \n\n---\n\n**Coverage coefficient in offline setting**\n\nLastly, our results cover both online and offline PG, and the latter makes up half of the paper (pages 6-9). In the offline learning setting, the learner cannot interact with the environment and must learn from the given data, hence _the problem of exploration simply does not exist there_. As with all offline results, a coverage coefficient is expected in the guarantee, reflecting the quality of the offline data (since, if the data is poor, there is nothing one can do). In fact, the kind of coverage coefficient we use is already improved over previous _offline_ PG results; previous results require all-policy coverage even just for estimating the gradient [LSAB19, NZJZW22], whereas our estimation guarantee only depends on single-policy coverage (Theorem 16).\n\n---\n**References** \n\n[AKLM21] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. “On the theory of policy gradient methods: Optimality, approximation, and distribution shift”. In: The Journal of Machine Learning Research 22.1 (2021), pp. 4431–4506.\n\n[BR24] Jalaj Bhandari and Daniel Russo. “Global optimality guarantees for policy gradient methods”. In: Operations Research (2024)\n\n[LSAB19] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. “Off-policy policy gradient with state distribution correction”. In: arXiv preprint arXiv:1904.08473 (2019).\n\n[NZJZW22] Chengzhuo Ni, Ruiqi Zhang, Xiang Ji, Xuezhou Zhang, and Mengdi Wang. “Optimal Estimation of Policy Gradient via Double Fitted Iteration”. In: International Conference on Machine Learning. PMLR. 2022, pp. 16724–16783.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qFOdVjAKLH", "reviewer": "Reviewer_K5ET", "summary": "This paper introduces policy gradient algorithms that focus on\nestimating the gradient of the *occupancy measure* with respect to the\npolicy parameters. In this framework, one can easily extend convergence\nanalysis beyond the standard RL objective (e.g., maximization of\nexpected return) to a much broader class of occupancy objectives, such\nas imitation learning or pure exploration. In addition to an online\nalgorithm, the authors design an algorithm for the offline setting based\non pessimistic corrections to density ratios, and provide bounds on the\npolicy gradient error for both under function approximation. In the case\nof the offline algorithm, this paper demonstrates convergence bounds\nunder weaker assumptions than existing methods. In the case of the\nonline algorithm, the paper further provides conditions under which\ntheir policy gradient algorithm achieves global optimality.", "questions": "In Corollary 6, what does it mean to run OccuPG with initial\ndistribution $\\nu$?\n\nOn line 238, you defined $\\bar{\\pi}_h = (\\pi\\land\nC^\\mathbf{a}_h\\pi^D_h)$. I am having some trouble interpreting this.\nFirstly, should it not be $(\\pi_h\\land C^\\mathbf{a}_h\\pi^D_h)$? Then, if\nthat's the case, is this equivalent to\n\n$$\\begin{align*}\n\\bar{\\pi}_h(a\\mid s) = \\min\\{\\pi_h(a\\mid s), C^a_h\\pi^D_h(a\\mid s)\\}?\n\\end{align*}$$\n\nGiven that the text focuses almost entirely on the problem of maximizing\nexpected return, how do the bounds given in this paper compare to those\nof existing results? Is there any benefit to running OccuPG if you only\ncare about expected return (especially in the online setting)?\n\nHow tight are your convergence bounds, particularly in the case of\noptimizing general functionals?\n\nIn Lemma 5, when should one expect to have $\\mathcal{C}^{\\pi^*}<\\infty$?", "limitations": "No major issues in this regard. Two limitations come to mind that were not\nthoroughly addressed:\n1. For optimization of general functionals, convergence results depend on a\n   Lipschitz assumption on the functional that is only discussed on the\n   appendix. How generally is this assumption satisfied?\n2. For the global convergence result (Lemma 5), there is a very strict\n   assumption on the initial state distribution, which would not often be\n   satisfied in practice (to my understanding). That said, other theoretical\n   works have made similar assumptions.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This paper is very interesting and extemely thorough. I really like the idea of\nestimating the occupancy gradient in order to generalize over objectives for\nsequential decision-making; these seems quite powerful, and has the potential of\nbeing very impactful. Effectively, here the authors have provided a\nmeta-algorithm (with convergence bounds) for a much broader class of algorithms\nthan standard policy gradient methods, which can unify several fields of research.\nThe Offline OccuPG method was really neat, and makes great\nuse of the existing FORC method for estimating clipped density ratios.", "weaknesses": "The biggest weakness for the paper, in my opinion, is that it could\nbenefit from extra clarification at many points. Realistically, this was\nprobably omitted in favor of making room for more content (the paper is\nvery dense), but I suggest the authors add some guiding discussions.\n\nParticularly, I think the following should be clarified:\n\n- **Motivation**: My first instinct after having read the draft was\n  \"this was very interesting to read, but how is the field of RL better\n  off in light of these results?\". The conclusion and introductory\n  sections place a lot of emphasis on the fact that this paper presents\n  the first algorithms/convergence results based on estimating the\n  occupancy measure, but it's not immediately clear why this is so\n  impactful. Ultimately, my impression is that the following two points\n  (especially the first) are the real winners:\n  1.  The ability to optimize a general class of functionals;\n  2.  Weaker assumptions for convergence with the offline algorithm.\n\n  I believe emphasizing these points more, and motivating them, can\n  really help the reader appreciate the results, but I found these\n  points to get a little lost in the sea of math.\n- **Comparison to existing work**: While I understand that this paper is\n  the first to analyze convergence of PG methods based on occupancy\n  measures, the paper focuses largely on the application of optimizing\n  expected return. As such, as someone that is not intimately familiar\n  with convergence results for PG methods, it would have been helpful to\n  have a more concrete comparison between the bounds presented in this\n  work and existing ones.\n- **Misc. writing/clarity issues**: Some math and/or algorithmic details\n  were ambiguous and/or unclear, listed below. This made the logic a\n  little difficult to follow at times.\n\n## Minor issues\n\nOn line 28, \"In answer\" -\\> \"In response\".\n\nIn Algorithm 1, $\\mathcal{D}^{\\mathrm{grad}}$ is not properly defined. On\nline 2 of the algorithm, it is implied that it is seeded the same way as\n$\\mathcal{D}^{\\rm reg}$, but on line 7 it appears that\n$\\mathcal{D}^{\\rm grad}$ is supposed to contain reward data (unlike\n$\\mathcal{D}^{\\rm reg}$).\n\nIn Algorithm 1, I think the definition of $\\mathcal{D}^{\\mathrm{reg}}$ has a\ntypo. It says $\\mathcal{D}_h^{\\mathrm{reg}} = \\{(s\\_h, a\\_h,\ns\\_{h+1})\\}\\_{i=1}^n$, but the index $i$ does not appear anywhere. My\nguess is that it should really be something like\n$\\mathcal{D}\\_h^{\\mathrm{reg}} = \\{(s\\_h^{(i)}, a\\_h^{(i)},\ns\\_{h+1}^{(i)})\\}\\_{i=1}^n$, where e.g. $\\{s^{(i)}\\_h\\}$ is the sequence of\nstates encounted over the course of rollout $i$.\n\nIn Theorem 2, $\\mathsf{pd}\\_{\\mathcal{G}}$ looks confusing (not clear\nthat it is $\\mathsf{p}$ times $\\mathsf{d}\\_{\\mathcal{G}}$ as opposed to a\nvariable called $\\mathsf{pd}\\_{\\mathcal{G}}$). Is it necessary to use\nsans serif font for $\\mathsf{p}$?\n\nIn definition 46, I believe there is a notational issue. It says\n$\\mathcal{F}\\subset\\mathbb{R}^{\\mathcal{X}}$, but then you have a term\n$\\mathrm{sign}(f(x_1^n - c))$ for $f\\in\\mathcal{F}$. But $x_1^n -\nc\\not\\in\\mathcal{X}$. Are you actually mapping $f$ over the dimensions\nof $x_1^n - c$? Also, there is a typo here, $c$ should be $v$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and insightful feedback, and for your appreciation of our work. We will refine our presentation per your comments, and include additional discussions according to the points below. \n\n---\n\n**Motivation**\n\nYes, these are the main contributions of the online and offline algorithms. We will make them more prominent in our revision. \n\n---\n\n**Comparison to previous work**\n\nFor both the online and offline settings, our results can be divided into two parts, estimation and optimization. Once the estimation and gradient domination conditions (e.g., Eq.(4) for online) are established, the optimization analyses largely follow from existing techniques in the literature.  \n\n\nOverall, the dependencies on sample size $n$, Lipschitz constant $\\beta$, and iterations $T$ match what we expect to see based on previous work and the optimization literature [Bec17, KU20, AKLM21, NZJZW22, BR24]. For coverage coefficients, the online version (Definition 3) is analogous to those in existing work (ours is finite-horizon while [AKLM21] is infinite-horizon). For offline gradient estimation, the results in [NZJZW22] pay for coverage of all policies (Assumption 6.1) while ours is single-policy (Theorem 16). \n\nBeyond that, our setting of occupancy-based gradient estimation is novel, so a direct comparison for the gradient estimation bounds is not readily available. In addition, few previous works provide end-to-end analysis incorporating both estimation/statistical error and optimization error (e.g., [AKLM21] establish global convergence with true gradients, while [NZJZW22] estimate off-policy gradients but do not use them for policy gradient). \n\n---\n\n**Questions**\n\n> In Corollary 6, what does it mean to run OccuPG with initial distribution $\\nu$? \n\nThis means that the initial state is drawn from $\\nu$, i.e., $s_1 \\sim \\nu$. The rest of the trajectory is generated by rolling out the policy in the true MDP.  We will revise our paper to make this more explicit. \n\n> Definition of $\\bar\\pi_h$ in L238 \n\nWe believe our use of the $h$ subscript might have caused some confusion (discussed below), but overall yes. By $\\bar\\pi_h  = \\left(\\pi \\wedge C_h^{\\mathsf{a}}\\pi^D_h \\right)$ we do mean $\\bar\\pi_h(a_h|s_h) = \\min \\left\\lbrace \\pi(a_h|s_h), C_h^{\\mathsf{a}} \\pi^D_h(a_h|s_h) \\right\\rbrace$, and we will make this more explicit in L238. \n\nWith regards to $\\pi(a_h|s_h)$ vs. $\\pi_h(a_h|s_h)$, for notational compactness we assumed that the same state cannot appear in multiple timesteps (L60-62). So $\\pi(a_h|s_h)$ only refers to the policy’s action at timestep $h$, and is de facto equivalent to $\\pi_h(a_h|s_h)$. \n\nIn the general offline dataset from Def. 7, where each $h$ has a different dataset, $\\pi^D_h$ was intended to indicate the data collection policy for timestep $h$. This might have caused some confusion, and we will clarify our notation accordingly. \n\n> Benefit to running OccuPG for expected return (esp. online)?\n\nIn the online setting with expected return, we view OccuPG as complementary to value-based PG, in the sense that the former can be beneficial when occupancy modeling is more feasible or aligned with existing inductive biases (e.g., on occupancy representations). However, it is possible that calculating $\\nabla\\log d^\\pi$ is more challenging than auto-differentiating through the value-based policy gradient. This is something that we are interested in exploring experimentally. \n\nMore importantly, OccuPG serves as the conceptual framework for our offline PG algorithm Off-OccuPG, and here we do see improvements in sample complexity because, unlike previous works [LSAB19, NZJZW22], we get away with single-policy coverage in gradient estimation. \n\n> Tightness of convergence bounds, particularly in the case of optimizing general functionals\n\nThis is an interesting question, and currently we are not sure. For occupancy gradient estimation, we do not expect that the rate of $n^{-½}$ can be improved, and our dependence in $\\mathsf{p}$ matches similar works on (off-policy) gradient estimation [NZJZW22]. It’s possible that $H$ factors can be reduced by more sophisticated handling of error compounding. \n \nFor general functionals, the generality of our bound (obtained through the Lipschitz factor, which doesn’t take into account properties of the objective such as curvature) means that it is likely not tight.  \n\n> In Lemma 5, when should one expect to have $\\mathcal{C}^{\\pi^*} < \\infty$? \n\n$\\mathcal{C}^{\\pi^*} < \\infty$ if we have access to some distribution over states $\\nu \\in \\Delta(\\mathcal{S})$, such that $\\nu(s) \\gg \\sum_h d^{\\pi^*}(s)$ for all $s$. In other words, it places nonzero mass on all states visited by the optimal policy. \n\nAt the worst, one can always guarantee $\\mathcal{C}^{\\pi^*}$ is finite (though potentially very large) by setting $\\nu = \\mathrm{uniform}(\\mathcal{S})$ to be uniform over all states. In practice, one may be able to craft a more refined $\\nu$ that results in smaller $\\mathcal{C}^{\\pi^*}$ given some expert or domain knowledge.\n\n---\n\n**References**\n\n[AKLM21] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. “On the theory of policy gradient methods: Optimality, approximation, and distribution shift”. In: The Journal of Machine Learning Research 22.1 (2021)\n\n[Bec17] Amir Beck. First-order methods in optimization. SIAM, 2017.\n\n[BR24] Jalaj Bhandari and Daniel Russo. “Global optimality guarantees for policy gradient methods”. In: Operations Research (2024)\n\n[LSAB19] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. “Off-policy policy gradient with state distribution correction”\n\n[KU20] Nathan Kallus and Masatoshi Uehara. “Statistically efficient off-policy policy gradients”. In: International Conference on Machine Learning. PMLR. 2020\n\n[NZJZW22] Chengzhuo Ni, Ruiqi Zhang, Xiang Ji, Xuezhou Zhang, and Mengdi Wang. “Optimal Estimation of Policy Gradient via Double Fitted Iteration”. In: International Conference on Machine Learning. PMLR. 2022", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8pZ3DI7nLk", "reviewer": "Reviewer_n45j", "summary": "With a focus on \"occupancy-based\" methods for RL, the authors propose a \nmodel-free, policy gradient method for policy optimization in finite-horizon \nMDPs via occupancy estimation. Guided by the representation of return in terms \nof the state-visitation probability and reward, they express the gradient of \nthe return in terms of gradient of the log of the state-visitation probability. \nThey propose to estimate the latter term via squared loss regression (see \neq 2). This estimate is then used to approximate the gradient of the return \nwhich is then plugged in to the usual policy gradient objective. In the online \nRL setting, they provide gradient estimation guarantees and convergence to a \nnear-optimal policy. For offline RL, due to insufficient coverage of the \noffline dataset, they provide guarantees on the estimate of the gradient of the \nclipped return.\n\n**Update**: I have revised my score based on the following considerations:\n1. The authors satisfactory response to the rebuttal,\n2. The unique approach to policy gradients, which may be insightful in advancing research on policy gradient methods,\n3. While rigidity of their assumption in the offline setting may limit its broader applicability, it also leaves room for further improvement.\n4. The authors willingness to address the other reviewers suggestions on notation and presentation.", "questions": "Just some additional comments:\n\n1. Line 70: should be $h'\\geq h$.\n2. In Line 151, do you mean $\\psi^{\\pi}$ instead of $\\psi$? Also, the first expression $d^{\\pi}=\\mu(s)^{T}\\psi$ seems inconsistent.", "limitations": "None. This is a purely theory paper.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. To the best of my knowledge, the authors propose a novel perspective to policy gradients in online and offline RL based on computing the return gradient by first estimating the gradient of occupancy measures.\n\n2. Their method for the online setting is technically sound with local and global convergence claims supported by theoretical analysis and relevant assumptions.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your feedback. \n\n---\n\n**re: \"Introduce new assumptions in the appendix which appear to influence their main results\"**\n\nThe omission of Asm. 7 and 8 from the preconditions of Theorem 16 was an oversight, rather than a deliberate choice to obscure dependencies. We will include Asm. 7 and 8 in the preconditions of Theorem 16 for the next revision, and space allowing, will move the definitions of Asm. 7 and 8 (and surrounding discussions) into the main text.  \n\nWe made the difficult decision of not including Asm. 7 and 8 (or Algs. 4 and 5) in the main text due to space constraints, given the breadth of our results in both offline and online policy gradient. Our reasoning was that\n- Alg. 4 (requiring Asm. 7) and Alg. 5 (requiring Asm. 8) are algorithms from established papers and have been analyzed therein.\n- They are orthogonal to the novelty of our paper, which uses algorithms from the aforementioned works as subroutines.\n- Most importantly, we wanted to highlight the distinguishing parts of our analysis given limited space. \n\nIn addition, they are weaker in some sense than Asm. 5 (expanded on below), which we mentioned briefly in L310, “We focus on discussing Asm. 5 for the offline gradient function class, which requires a stronger level of expressiveness.” Given extra space, we will expand this discussion based on the following points sourced from the Appendix:  \n\n> Assumption 8\n\nFrom L1002-1005: “The weight function class completeness assumption is shown Asm. 8, 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. 5 where $\\rho = 1$, and in that sense strictly weaker.”\n\n>Assumption 7\n\nThis is the standard realizability guarantee for maximum likelihood estimation or supervised learning (it is analogous to [Theorem 21, AKKS20] and also required by [HCJ23]), and only requires that the function class includes the ground-truth function. In comparison, Asm. 5 and 8 involve multiple functions. \n\n---\n\n**re: \"Paper is not self-contained and the results are rather difficult to verify\"**\n\nAside from the above issue (for which our previous response proposes a self-contained fix), we believe that the paper is self-contained and verifiable. For all algorithms and results in the appendix we have included rigorous proofs, and assumptions with justification. However, we empathize with the sentiment of your comment in the sense that our results rely on algorithms from established papers as subroutines, which results in layers of analysis. With more space, we hope to provide more details and results on this in the main body, per the existing descriptions, guarantees, and proofs in Appendices D and E.\n\n---\n\n**Questions** \n\nYes, it should be $d^\\pi = \\mu(s)^\\top \\psi^\\pi$. Thank you for catching these typos. We will correct them in our paper.\n\n---\n\n**References**\n\n[AKKS20] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. “Flambe: Structural complexity and representation learning of low rank mdps”. In: Advances in Neural Information Processing Systems (2020).\n\n[HCJ23] Audrey Huang, Jinglin Chen, and Nan Jiang. \"Reinforcement learning in low-rank mdps with density features.\" International Conference on Machine Learning. PMLR, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)