Beyond the Return: Off-policy Function Estimation under User-specified Error-measuring Distributions
Authors: Audrey Huang
Nan Jiang
Venue: NeurIPS 2022 Accept (2022)
Keywords: off-policy evaluation
marginalized importance sampling
finite-sample analyses

Abstract: Off-policy evaluation often refers to two related tasks: estimating the expected return of a policy and estimating its value function (or other functions of interest, such as density ratios). While recent works on marginalized importance sampling (MIS) show that the former can enjoy provable guarantees under realizable function approximation, the latter is only known to be feasible under much stronger assumptions such as prohibitively expressive discriminators. In this work, we provide guarantees for off-policy function estimation under only realizability, by imposing proper regularization on the MIS objectives. Compared to commonly used regularization in MIS, our regularizer is much more flexible and can account for an arbitrary user-specified distribution, under which the learned function will be close to the groundtruth. We provide exact characterization of the optimal dual solution that needs to be realized by the discriminator class, which determines the data-coverage assumption in the case of value-function learning. As another surprising observation, the regularizer can be altered to relax the data-coverage requirement, and completely eliminate it in the ideal case with strong side information.

Beyond the Return: Off-policy Function Estimation under User-specified Error-measuring Distributions
Audrey Huang
Nan Jiang
Computer Science
Computer Science
University of Illinois at crhama-Champaign audreyh5@i 11 www.iniiiiiiii....mmmm .eduiiueduuuu
University of Illinois Champaiggn
edu
Abstract
Off-policy evaluation often refers to two related tasks: estimating the expected return of a policy and estimating value function (or other functions of interest, such as density ratios). While recent works on marginalized importance sampling (MIS) show that the former can enjoy provable guarantees under realizable function approximation, the latter is only known to be feasible under much stronger assump- tions such as prohibitively expressive discriminators. guarantees for off aff-policy function estimation under only realizability, by imposing proper regularization on the MIS objectives. Compared to commonly used regu- larization in MIS, our regularizer is much more flexible and account for arbitrary user-specified distribution, under which the learned function will be close the groundtruth. We provide exact characterization of the optimal dual solution that needs to be realized by the discriminator class, which determines the data- coverage assumption in the of observation, the regularizer can be altered to relax the data-coverage requirement, and completely eliminate it in the ideal case with strong side information.
this work, we provide
learning. As another surprising
Introduction
Off-policy evaluation (OPE) often refers to two related tasks in reinforcement learning (RL): estimat- ing the expected return of target policy using dataset collected from a different behavior policy, versus estimating the policy's 's value function (or other functions of interest, such as density ratios). The former is crucial to hyperparameter tuning and verifying the performance of policy before real-world deployment in offline RL [VLJYT9, 2ai+20) [J21]. The latter, on the other hand, plays an important role in (both online and offline) training, often as the subroutine of actor-critic-styi algorithms [LP03 LSAB19, but is also generally more difficult than the former: if an accurate value function is available, one could easily estimate the return by plugging in the initial distribution.
Between the two tasks, the theoretical nature of off-policy return estimation is relatively well understood, especially in terms of the function pepetionaaproximatioo assumptions needed for sample- complexity guarantees, Among the available algorithms, importance sampling (IS) and its variants [PSS00) TTG15 J do not require any function approximation, but incur aoponentialin--hriii variance; Fitted- Q Evaluation [EGWOS] LVY19 can enjoy polynomial sample complexity under appropriate coverage assumptions, but the guarantee relies on the strong Bellman-comm callmaan-comlltennsss assumption the function class; marginalized importance sampling (MIS) methods, which have gained significant attention recently (LLIZI8] XMW19 UHD20 NCDL19). use two function classes simultaneously approximate the value and the density-ratie (or weight) function and optimize minimax objectives. Notably, it is the only family of methods known to produce accurate return estimates with polynomial sample complexity, when the function classes only satisfy the relatively weak realizability assumptions (i.e., they contain the true value and weight functions).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In comparison, little is known about off policy function estimation, and the guarantees are generally less desirable. Not only do the limitations of IS and FQE on return estimation carry over this more challenging task, but MIS also loses its major advantage over FQE: despite the somewhat misleading impression left by many prior works, that MIS can handle function estimation the same way as return estimation MIS for function estimation often requires unrealistic assumptions such as prohibitively expressive discriminators. For concreteness, a typical guarantee for function estimation from MIS looks like the following (see e.g., Theorem 4 of [LLTZI8] and Lemmas I and 3 of (UHJ20):
Proposition 1 (Function estimation guarantee for MIS, informal), Suppose the offline data distribu- tion d satisfies d a) > 0, Vs,a. a. Given WW 5xA q" = arg min gE Q max L(w, q) for some appropriate population loss function L
class Q with q" E Q and weight class
W =
To enable the identification of the value function q", the result requires the discriminator class W to be the space of all possible functions over the state-action space (W = (x)) In the simite-sample regime, using such class incurs sample complexity that depends the size of the state-action space, which completely defeats the purpose of function approximation.
In addition, these results only hold asymptotically. where the function of interest can be exactly identified in a point-wise manner. Such an overly strong guarantee is unrealistic in the finite-sample regime, where one can only hope approximate the function well in average sense under some distribution, i.e., finite-sample performance guarantees should ideally bound l|ğ - q" 2 for the learned 7. where || l12,, is v-weighted 2-norm. Such fine-grained analyses are non-existent in MIS. Even in the broader literature, such results not only require gellmann-completenes-yyyy (UNKSXX1), they also come with some fixed y (which is not necessarily d8; see Section 2 and the user has no freedom in choosing v. This creates a gap in the literature, as downstream learning algorithms that use off- off-colicy function estimation as subroutine often assume the estimation to be (see details in Appendix
assumptions
accurate under specific distributions KL02 AYBBLSWI9
To summarize, below are two important open problems on off-policy function estimation:
1. Is it possible to obtain polynomia 5 sample complexity for off-policy function estimation, using function classes that only satisfy realizability--n -ript assumptions?
2. Can we specify a distribution v to the estimation algoritim, such that the learned function will be close to the groundtruth under v?
In this work, we answer both open questions in the positive. By imposing proper regularization on the MIS objectives, we provide off off-policy function estimation guarantees under only realizability assumptions on the function classes. Compared to commonly used regularization in MIS (NCDL19, ND20 YNDLS20), our regularizer much more flexible and can account for an arbitrary user- specified distribution v, under which the learned function will be close to the groundtruth. We provide exact characterization of the optimal dual solution that needs to be realized by the discriminator, which determines the data-coverage assumption in value-function learning. As another surprising observation, the regularizer can be altered to relax the data-coverage requirement, and in the ideal case completely eliminate it when strong side information is available. Proof-of-concept experiments are also conducted to validate our theoretical predictions.
2 Related Works
Regularization in MIS The use of regularization is very common in the MIS literature. especially in DICE algorithms [NCDL19 NDKCLS19) YNDLS20). However, most prior works that consider regularization use tabular derivations and seldom provide finite-sample funetion-approximaaie guarantees on even return estimation, let alone function estimation. (An exception is the work of [UNKSX2T, who analyze related estimators under Bellman-comme wotp--eeeess--yyyppe.... assumptions; see the next paragraph.) More importantly, prior works provide very limited understanding in how choice of regularization affects learning guarantees, and have considered only naïve forms of regularization iiiee-actioninnepeeedee and typically under d)), under which different forms of regularization are essentially treated equally under coarse-grained theory (YNDLS20). In contrast, we provide much
For example, LSAB19 assumed a weight estimation oracle and cited LLTZI8 as possible instance. "Concretely, one can choose L as Eq. without the regularization term, which recovers MQL in [HH220] 'By "polynomial", we mean polynomial in the horizon, the statistical capacities and the boundedness of the function classes, and the parameter that measures the degree of data coverage.

---

more fine fine-graine grained characterization of the effects of regularization, which leads to novel insights about how to design better regularizers, and existing DICE estimators are subsumed as special cases of our method when we choose very simple regularizers (see Remark g in Section
Fitted-Q Evaluation (FQE) Outside the MIS literature, one can obtain return and
estimation guarantees via FQE [DJW20] CJT9 LVY19 (UKSX2I] However, it is well understood that FQE and related approaches require Bellman-compleeenss--yye assumptions, such as the function class being closed under the Bellman operator. Even putting aside the difference between completeness vs. realizability, we allow for a user-specified error-measuring distribution, which is not available in FQE or any other existing method. The only distribution these methods aware of is the data distribution d'. and even so, FQE and variants rarely provide guarantees on l|ğ q" 112.d0, but often the Bellman error (e.g.. I T T" instead (UUJKSX2I] J. and obtaining guarantees on a distribution of interest often requires multiple indirect translations and loose relaxations.
LSTDQ Our analyses focus on general function approximation. When restricted to linear classes, function estimation guarantees for q" under dº can be obtained by LSTDQ methods (LPP33 B Y09
DNP14] when the function class only satisfies realizability of q" (PKBK22). However, this requires an additional matrix invertibility condition (see Assumption 3 of (PKBK22), and it is still unclear what this condition corresponds to in general function approximation Moreover, many general woethods-including MIS [UH120] and other minimax methods [ASM08] XCIMA21 -oinccdee with LSTDQ in the linear case, so the aforementioned results can be viewed as a specialized analysis leveraging the properties of linear classes.
PRO-RL [ZHHJL222 Our key proof techniques are adapted from [HH)L22 whose goal is offline policy learning. They learn the importance weight function w" for a near-optimal and provide | == 122.00 guarantees as an intermediate result. Despite using similar technical tools, our most interesting and surprising results are in the malue-function estimation setting, which is not considered by [ZH.)).22] J Our novel algorithmic insights, such as incorporating error-measuring distributions and approximate models in the regularizers, are also potentially useful in [HHHJL22 's policy learning setting. Our analyses also reveal a number of important differences between OPE and offline policy learning, which will be discussed in Appendix A
3 Preliminaries
We consider off-policy evaluation (OPE) in Markov Decision Processes (MDPs). An MDP is specified by its state space S, action space A, transition dynamics P S A - ASS) (A(-) is the probability simplex), reward function R S x A + A (0, 1l). discount factor y E [0. 1), and an initial state distribution μu A(S). We assume S and A are finite and discrete, but their cardinalities can be ar- bitrarily large. Given target policy π S + A (AA), a random trajectory so, 0o ro, 81, (1) ,T,... can be generated so n0: at TT(-ss,,,rt rt R(-1st, at), 8c+1 ~ P(-[st; ae). Vi 2 0; we use E,, and Pa to refer to expectation and probability under such a distribution. The expected discounted return (or simply return) of æ is J(T) := E.g EE, <rr.). The Q-value function of a is the unique solution of the Bellman equations q" = = with the Bellman operator T S + RSXA defined as by E R (T=q) a)= := (,.ss)( [r] + (PP(t)) (P)4)(s,)) a). Here Pm R S AIx (Sx.A) is the state- action transition operator of æ. defined as (P (P, a) := Egg - (=)) (-)))(((((())))))))))) [9(5',
a')] Functions over S x A (such as 9) are also treated as |S x Al-dimensional vectors interchangeably.
In OPE, we want to estimate qd and other functions of interest based on a historical dataset collected by possibly different policy. As standard simplification, we assume that the offline dataset consisting of n i.i.d. tuples {(ss; Oz ri, s sampled as (8t, a;) ~ dD, r ~ R(-[s;, and af P(-1s;, a;). We call d the (offline) data distribution. As another function of interest, the (marginalized importance) weight function w" is defined as w (s, a) == dt (s, a) /dd (s, a). where d' (8) = (1 7) E >PP>>> = 8, <g = a] is the discounted state-action occupancy of π. For technical convenience we assume d a) > 0 Vs, a, so that quantities like w" are always well defined and finite Similarly to
q², nt also satisfies a recursive equation, inherited from the Bellman
'It is hinted by (UHJ20) that the invertibility is related to loss minimization condition in MIS. but the connection only holds for return estimation.
'It will be trivial to remove this assumption at the cost of cumbersome derivations. Also. these density ratios can still take prohibitively large values even if they are finite, and we will need to make additional boundedness assumptions to enable unite-sample guarantees anyway, so their finiteness does not trivialize the analyses
3

---

flow equation for d= d" = -) + +xP=d d=, where (s.a) Hō + Po, ~ TT-ss) is the initial state-action distribution, and p == (P*)T is the transpose of the transition matrix.
Function Approximation We will use function classes Q and W to approximate q" and w", respec- tively. We assume finite Q and W, and extension to infinite classes under appropriate complexity measures (e.g., covering number) is provided Appendix G
Additional Notation 12,2 := / [-)] is the weighted 2-norm of function under distribution v. We also use a standard shorthand f(s, π) == Ba-r(1s)] (1,,, a)]. Elementwise multiplication between two vectors u and v of the same dimension is o E and elementwise division is u/v.
4 Value-function Estimation
In this section we show how to estimate q R q" with guarantees on |/ -50--1ll 12,1 for a user-specified v, and identify the assumptions under which provable cample-complexity guarantees can be obtained. We begin with the familiar Bellman equations, that q" is the unique solution to:
E Ml-s,a)) [r] + PP s,a)l((s', m)] q(s, a) = O, Vs
(1)
While the above set of equations uniquely determines g = q²", this only true if we can enforce all the IS x A| constraints, which is intractable in large state-space problems. In fact, even estimating (a candidate q's violation of) a single constraint is infeasible as that requires sampling from the same state multiple times, which is related to the infamous double-samplle problem (Bar95].
To overcome this challenge, prior MIS works often relax Eq. 1 by taking weighted combination of these equations, e.g..
(((ssa))) a)) = 0, Vw E W. Enp [w[s, a) (r(s, + 79(6', g(.
Instead of enforcing 1S Al equations, we only enforce their linear combinations; the linear coefficients are d8(s,a) a) - w((s,), a). and w belongs to a class W with limited statistical capacity to enable sample-efficient estimation. While each constraint in Eq 2 can now be efficiently checked on data, this comes with a big cost that solution to Eq 2 is not necessarily q" Prior works handle this dilemma by aiming lower: instead of learning q ss q" they only learn ğ that can approximate the policy's 's return, i.e. E Eg [ā[s, rT] R (T) Es-pe po [g" (s, T]]. While [UH220) show that the latter possible when u W, they also show explicit counterexamples where & * q" even with infinite data. As result, how to estimate @ = qº under comparable realizability assumptions (instead of the prohibitive W SxA as in Proposition is still an open problem.
4.1 Estimator
We now describe our approach to solving this problem. Recall that the goal is obtain error bounds for - g"' for some distribution & E A(S x A) specified by the user. Note that we do not require information about and s' that are generated after (s,a) P and only care about the (s, a) marginal itself, so the user can pick v in an arbitrary manner without knowing the transition and the reward functions of the MDP. We assume that is given way that we can take its expectation (r..))=[(--), and extension to the case where // is given via samples is straightforward.
To achieve this goal, first turn [ into equivalent constrained convex program: given collection of strongly convex and differentiable functions (fv,a : IR - R]s,a- we will refer to the collection and discuss its choice consider
min Str.))-lleeaa00 s.t. EE, [r] + 7E3'' (q(s,, (1)],)]]== - -00 = Vs A.
(3)
The constraints here the same as Eq. D.. Since Eq. uniquely determines 9 q", the feasible
space of Eq.(3 is a singleton, so we can impose any objective function on top of these constraints (here we use E(s,a)re (g(s, a))]) and will not change the optimal solution (which is always q=, the only feasible point). As we will see, however, f {.f..a R + R)s,a will serve as important regularizer in the crattionnappoximmatiion setting and is crucial to our estimation guarantees.
Remark 1 ((s, dedeenddeeeeee of f). Regularizers in prior works are (s, inddeeepennn (CCLL19 YNDI.S20 ZHHJI.22). As we will see in Section allowing for (s, ad-deeenneeeee very important for designing regularizers with improved guarantees and performances.

---

We now rewrite B in its Lagrangian form, with d' w serving the role of dual variables:
min max L w) == E. [f.. (q(s. + Eg [w(ss, a) (r(s, a) + rg(sss T) g(s, a))l
(4)
Finally, our actual estimator approximates Eq. via finite-sample approximation of the population loss Lj, and searches over restricted function classes Q and W for q and w. respectively:
q arg min max (g w),
(5)
JEQ
wEW
where (g, w) E. (a
E.= w(ss; 0s) (ri + 79(6 ( at))
Intuition for identification Before giving the detailed sinite-sample analysis, we provide some high-level intuitions for why we can obtain the desired guarantee on llğ q" ||2. Note that Eq 4 is structurally similar to Eq. 2 and we still cannot verify the Bellman equation for q" in a per-state- action manner, the caveat of Eq. seems to remain; why we identify 9" under 1/?
The key here to show that suffices to check the loss function I.3 only under special choice of w (as opposed to all of R SxAA). Importantly, this special w is not w=" w rrather, it is the saddle point of our regularized objective LÝ; let (4" w7) be saddle point of L (we will give the closed form of w later). As long as w E W-even W extremely "simple" and contains nothing but ww-we can identify q²
To see that, it is instructive to consider the special case of W = {w and the limit of infinite data. In this case, our estimator becomes arg min Lg, wf). By the definition of saddle point:
L3 wf) S L3 (q. wz), vq..
While this shows that 9ºt is a minimizer of the loss, it does not imply that it is a unique minimizer. However, identification immediately follows from the convexity brought by regularization: since f + is strongly convex, - [s. [affs.a(qi (g(s. a))] as a mapping from IRS to is strongly convex under || lla, (see Lemma 7 in Appendix for formal statement and proof), and 1. wf) inherits such convexity since the other terms are affine in g. It is then obvious that 9º is the unique minimizer of L (a" wf)) up to || l|,,,, that is, any minimizer of L must agree with q" on (s, a) pairs supported on v. Our finite-sample analysis below shows that the above reasoning is robust to finite-sample errors and the inclusion of functions other than w in W.
4.2 Finite-sample Guarantees
In this subsection we state the formal guarantee of our estimator for q" and the assumptions under which the guarantee holds. We start with the condition on the regularization function f:
Assumption 1 (Strong convexity of f). Assume fa.a + R is nonnegative, differentiable, and M -t-strongly convex for each s E S, a E A. In addition, assume both fa.a and its derivative f'. take finite values for any finite input.
This assumption can be concretely satisfied by a simple choice of fa,a(x) = fa², which is indepen- dent of (s, a) and yields M 1. Alternative choices of f will be discussed in Section 4.3 Next the realizability and boundedness of W and Q:
Assumption 2 (Realizabilitty) Suppose w/ W. E Q.
Assumption 3 (Boundedness of W and Q). Suppose W and Q are bounded, that is,
C% m |gll 30, Că = wax || < co.
As a remark, Assumption 2 iipplcitty assumes the existence of wÿ. As we will see in Section 4.3 the
existence and finiteness of up is automatically guaranteed given the finiteness of f'.. (Assumption
and dD (s, a) O'vs a. More importantly, Assumptions 2 and 3 together imply that ||0" C% and [wj I Ciy, which puts constraints on how small C2 and Cy can be. For example, is common to assume that C% = T ie., the maximum possible return when rewards are bounded
"In fact, n" should not appear in analysis at all: w" is defined w.r.t. the initial distribution of the MDP, no. which has nothing to do with our goal of bounding ||ğ q 11....
5

---

in [0, 1], and this way ll I Cg will hold automatically. The magnitude of | ol and Cwy. however, is more nuanced and interesting, and we defer the discussion to Section
Now ready to state the main guarantee for identifying q" All proofs of this section can be found in Appendix
Theorem 2. Suppose Assumptions hold. Then, with probability at least 1 - 5,
9
|10 g=112,"" S 2
M
where sstat +C++ V
2 log 2IWTE!
73
Theorem 2 shows the desired bound on | 11,. which depends on the magnitude of functions in W and as well as their logarithmic cardinalities, which are standard measures of statistical complexity for finite classes. One notable weakness is the (nn slow rate; this is due to translating the Stat = (n 1/2 deviation between I. and into || - o- l|2, via a convexity argument, which takes square root of the error. The possibility of and obstacles to obtaining an O( rate will be discussed in Section 7
4.3 On the Closed Form of wi and the Data Coverage Assumptions
One unusual aspect of our guarantees Section 4.2 that we do not make any explicit data coverage assumptions, yet such assumptions are known to be necessary even for return estimation (typically the boundedness w" = d ()". Indeed, our data-coverage assumption is implicit in Assumptions
and 3 which require ||w] l|xx I W <
oc. If data fails to provide sufficient coverage, ||w will
be large and our bound in Theorem will suffer due large value of CW:
To make the data coverage assumption explicit, we provide the closed-fore expression of wy:
Lemma 3. The saddle point of (4",; (.}] = arg min, arg max L2 w), where
v0z = (T
- - PP (
(6)
Here ( is the shorthand for (4 a,, TRSAA
The closed-fome expression in Eq. 6 looks very much like density ratio: if we replace v f'(4") with u we have (7 77 > n. d (1 7)), and the expression would be the ratio between d" and dD (up to a horizon factor). Therefore, vy can be viewed as the density ratio of π against dD when π starts from the "fake" initial distribution v (²(x".. However, v f'(4") is in general not valid distribution, as is not necessarily normalized or even non negative, making [|w) ll so difficult intuit. Below we give relaxations of ||w |oo which are more interpretable and give novel insights into how relax the data-coverage assumption via tweaking f.
Proposition 4. l1w S -dd, occupancy of nt under v as the initial state-action distribution.
[l. where dz is the discounted state-action
The proposition states that ||w can be bounded if data provides sufficient coverage over dy, and fa bounded. The former shows that dd needs cover not only v/ but also state-action pairs reachable by starting from v. The latter is easily satisfied, and can be bounded again for concrete choices of f. e.g. (I"" & ||a I - for (x, 1
Designing / to relax the coverage assumption Lemma 3 shows that the coverage assumption (bounded (>>) depends
(or rather its derivative I"), which opens up the possibility of properly designing f to relax it. In fact, could completely eliminate the coverage assumption if we could set f'( ) = O, but that would require unrealistically strong side information.
As concrete example, consider (x) {(x (s, a))², and it is easy to verify that fr (s", a))
q- (s. (s.a))==qrss. tially adds Ist-order term 9" (s) to change wý. while leaving the convexity required by Assumption intact, which only depends on the 2nd-order term 1 Of course, this not a viable choice of f in practice it requires knowledge of q", which is precisely our learning target.
0. Compared (z) 1=², the new essen-

---

While the reason (z) = (a2 (= a can eliminate the coverage requirement is obvious retrospectively (q" already minimizes [g)] even without any data), our analyses apply much more generally and characterize the effects of arbitrary ʃ on the coverage assumption. Inspired by this example, we can consider practically feasible choices such as [s.a (2) (x - g(s, a))² where is an approximation of q" obtained by other means, e.g. guess based on domain knowledge. If R q", our estimator enjoys significantly relaxed coverage requirements. But even if q is a poor approximation of q", it does not affect our estimation guarantees as long as the condition implied by Proposition is satisfied. (In fact, (z) = 1²" is a special case of q 0.) Such a use of approximate models is similar to how doubly robust estimators (DLLIT 1 TB16] enjoy reduced
variance given an accurate model, and remain unbiased even if the approximate model is arbitrarily
poor. We will show in Section 6 that this idea is empirically effective.
Weight-function Estimation
Similar to falue-function estimation, our methodology can also be applied estimate the weight function w". Due to the similarity with Section 4 in the high-level spirit, we will be concise in this section and only explain in detail when there a conceptual difference from Section + Some notations (such as the function classes W and Q) will be abused, but we emphasize that this section considers a different learning task than Section f so they should be viewed as different objects (c.g.. the realizability assumptions for W and Q below will be different from those in Section 4
As before, we assume that the user provides distribution ?) E A(S A) and our goal is develop an estimator with guarantees on || w" 12.... Analogous to Section consider
min (( (w, a))]
(s, (s (s.p((ss'))ssssss ,d')((ss a), Vs s.t. (s) (1 (1-7))ā(ss,0 o
Here/ / = (e.at..a will need to satisfy similar assumptions as in Section + The constraints are the Bellman flow equations with a change of variable d(ss, a) dD (s. a) w(s a). Their unique solution is d(s,a) d'(ssa)) (and hence w(s, a) = dd (s, a) /d (s, a)), thus the feasible space is again a singleton, and the objective does not alter the optimal solution. We then use dual variables to rewrite in its Lagrangian form:
min,, max, L (g. w)
E,, (w,, a))] + EE [a(s, m]] + Eg (((s(s) x) ((sss a))l
(8)
We approximate the saddle-pon point solutions by optimizing the empirical loss Tyy over restricted func- tion classes W, Q: @ arg min max,e T.y (q, w), where Tyy w) == E., [ (w(s, +
(1 7) 1-2 To ((8), T) - 1t Σi= w(8;, aa) (79(*'33 T) - ((*,, a.)), and { is a separate ng j= dataset sampled i..dd from (t0 to provide information about the initial distribution.
We provide the closed-form expression for the saddle point of Ly below, which resembles the Q-function for a proxy reward function f'(w") o n/dD.
Lemma 5. The closed form solutions of 8 are (w=, ,4.) arg min arg max, (7 w), where
qj = 2f n/dd).
Remark 2 (Data Coverage Assumption). As we will see, the only data coverage assumption we need is the boundedness of w" d /d" Since n" is the function of interest and practical algorithms can only output functions of well-bounded ranges, such an assumption is an essential part of the learning task itself and hardly an additional requirement. Moreover, unlike Section 4 changing, f here will not affect the data-coverage assumption, though it still alters 9j. and a properly chosen I (e.g.. with f'(w") ) Ri 0) can still result in a 97 with small magnitude and thus make learning easier.
Remark 3 (Connection to DualDICE), We can recover DuaIDICE [NCDL19] by choosing (z) 2 and // = dP. Despite producing the same estimator, the derivations and assumptions under which the two works analyze the estimator are different. Their Theorem only provides return
'Reaall we assume d² (s, a) > 0 V's a for technical convenience. When this is not the case, 7 should be supported on dD, the target function w" is only defined on the support of dD
7

---

estimation guarantees, and depends on an implicit assumption of highly expressive function classe similar to Proposition [ Moreover, they do not characterize how the choice of can affect the learning guarantees (their f is (s, a)-indepennentt. This is one of the main insights of our paper and leads to the discovery of more practical regularizers, e.g. [s.a(1) = 2 (x - ((88 a))² with model w.
Below we present the assumptions, then learning guarantee for w.
Assumption 4 (Strongly Convex Objective). Suppose for all s, a, faaa is differentiable, non-negative, and -ttstoyngly convex. Further, suppose Ss,a and its derivative take finite values on any finite inputs, and let Cy maxwew (lf(w))o..
Assumption 5 (Realizability). Suppose w" E EWW 97 EQ
Assumption 6 (Bounded W and Q) Let CWv == max //wll and C5 == max llallo. Suppose W and Q are bounded function classes, that is, CW and C < oc.
Theorem Suppose Assumptions 4 hold. Then wap. 2 - 5, |
w"
Ila. S 2
Seia Maw
where
sstat (CT + (1++(1++)C)))0)
2og Mmu
+ +1- 20
2
n0
6 Experiments
We now provide experimental results to verify our theoretical predictions and insights. As (NDLS20
have performed extensive experiments on return estimation with simple regularization Ua (x)
_ we focus on the task of g" estimation, and the following two questions unique to our work:
Q1. When the goal is to minimize Ilğ - q- ll,. how much benefit does regularizing with v bring in practice, compared to regularizing with other distributions (or no regularization all)?
Q2. Can incorporating (even relatively poor) models in regularization (e.g., fe.a f..gg.f.aaa (2) = { ((s, a))²
from Section 4.3) improve estimation?
Setup We study these questions in large tabular Gridwalk environment [NCDL19 YNDLS20 with
a deterministic target policy that is optimal, and behavior policy that provides limited coverage over the target policy; see Appendix D for further details. To mimic the identification challenges associated with restricted function classes, we use linear function class Q { a [Rd) and discriminator class W {Φ β B E R*), where l < |S x AJ. The features & E RR|XAA|xd @ E x||x are chosen to satisfy the realizability assumptions of all estimators. Under linear classes, our estimator (Eq. ( becomes convex optimization problem with d variables and & linear constraints, and can be solved by standard packages. This allows us to avoid difficult minimax optimization which is still an open problem in the MIS literature- and focus the statistical behaviors of our estimators, which is what our theoretical predictions are about.
Remark 4. When no regularization is used, our linear estimator coincides with MQL UHJ20
If we further had T- T the estimator would coincide with LSTDQ. While Section mentioned that LSTDQ enjoys cumetion-estimation guarantees [KKBK22] (and folklore suggests they extend to ② * Φ). the guarantee only holds in the regime of k 2 d, i.e., the k linear constraints are over- determined. In our case, however, we have under-determinet constraints (k d), creating a more challenging learning task (which our theory can handle) where LSTDQ's guarantees do not apply.
Choice of Distributions We consider set of diverse distributions V {dD,, "ep d= U.P), where U is uniform over S x A and x (d" a I[w= > 50)). The distribution p isolates the least-covered states reached by म, which makes learning an accurate Q-function on v harder task.
Results for Q1 We use a default regularizer f = 1=²² with different regularizing distributions v E V, and measure و/q q for different v'. The results are shown in Figure []] which exhibit the expected trend: for example, regularizing with / = P performs poorly when the error is measured under / d= and U due to the large mismatch between / and v'. However, when v = p (rightmost panel), regularizing with v p significantly outperforms others. Similar behaviors can also be observed on U, though they are certainly not absolute (e.g.. V = dd does not do very well on
"In our notation, they measure the approximation error of W as m = min.ew [/w essentilll requiring W (and similarly Q) to closely approximate every function over S x A. However, we suspect that they could have measured realizability errors instead without changing much of their proofs.
8

---

log (i(m) -/tnl]
18 2.0
log 14 47
18- 10441.
0.0
04
12
42
1.0
10
.05
0.
0.5
0.0
-.0
.08
4.
05-
0.3
-1
4.4
0.
0.2
0.8
200
400
500
000
1000
Samples
Figure 1: Error of off- ofo-po return and function estimation function of sample size. Legend shows regularizing distribution y and header shows error meaoo-meauuiing distribution // (see text). Error bars show 95% confidence intervals calculated from 1000 runs.
Uniform Model
Model
Uniform Model
p Model
92
log lā d'
log
-2-
-2-
model
Model Quality
Quality
Figure 2: Estimation eπror when the regularizer incorporates a model 7. where x-axes represent the parameter m that controls the quality of q. The "model" line shows performance of g. Sample size 500 and the results are from 500 runs.
dP),), which suggests potential directions for more refined and accurate theory. Moreover, using no regularization ("none"" generally does not perform well for any v', but still manages to achieve high accuracy for return estimation J(x,,, which consistent with prior theory [e.g.. UHJ20) that return estimation does not require regularization.
We now use (x) = [z - ((s,s))) with different q to verify how the quality of q affect estimation accuracy. We first consider "uniform model" q = mqq (1 m /7, where q is constant and m j0, 1] controls the quality q. As shown from Panels & 3 in Figure our estimator's 's accuracy generally improves with better q (i.e., as m increases). Moreover, equipping with an appropriate regularizing distribution v (e.g.,
Results for Q2
U for both panels) can significantly outperform no regularization, even with very poor g (e.g., m 0.1). It also outperforms the model prediction itself (i.e., ạ 7) showing that the improvement is not due to our estimator simply taking predictions from q. but using the regularization to better assist the identification of g from data.
The previous model's quality is uniform across A. We then consider scenario where q is zeroed out outside p's support, making it only a good approximation of q" on p. In this case, we see that regularization cannot benefit much from the model when the error is measured on = U (Panel 2), but when 2/ = p (Panel 4), regularization can still bring benefits, as expected from theory.
7 Discussion and Conclusion
In this paper we showed that proper regularization can yield function eetiiittiittntiioonnnooo guarantees for MIS methods under only realizable function approximation. Compared to prior works, our regularizer is more flexible and can accommodate a user-specified error-measuring distribution. Further theoretical investigation provides fine-grained characterization of how the choice of regularization affects learning guarantces, which leads to the discovery of regularizers that incorporate approximate models (such as Z). While the superiority of such regularizers is perhaps obvious retrospectively, it is not allowed in the prior works' derivation that assumes (s, a) ---ideependent regularization, and our theoretical results provide deep understanding for even more general regularization schemes. In Appendix A provide further discussions on two topics: (1) the barriers to obtaining a faster O(n-t/2) rate, and (2) comparison to [2HHITT222] reveals interesting differences between off off-policy function estimation and policy learning, and insights in this paper may also be useful for the policy learning task.

---

Acknowledgments and Disclosure of Funding
The authors thank Jinglin Chen, Wenhao Zhan, and Jason Lee for valuable discussions during the early phase of the project, and Anonymous Reviewer e62P for insightful feedback that helped improve this paper during the review process. NJ acknowledges funding support from ARL Cooperative Agreement W91 1991IN-11---0111 Science Research Award.
NSF (IS-2112471) NSF CAREER IIS-2141781, and Adobe Data
References
[ASM08]
"Learning near-optimal poli- cies with Cellman-residuse minimization based fitted policy itcration and a single sample path". In: Machine Learning (2008).
András Antos, Csaba Szepesvári, and Rémi Munos.
[AVDB18]
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. "A rewriting system for convex optimization problems". In: Journal of Control and Decision 5.1 (2018), pp. 42-60.
[AYBBLSW19]
Yasin Abbasi- Yadaki,, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepes- vari, and Gellért Weisz. "Politex: Regret bounds for policy iteration using expert prediction" In: International Conference on Machine Learning. PMLR. 2019, pp.
[Bai95]
Leemon Baird. "Residual algorithms: Reinforcement learning with function ap- proximation". In: Machine Learning Proceedings 1995. Elsevier, 1995, pp. 30- 37.
[BY09]
Dimitri P Bertsekas and Huizhen Yu. "Projected equation methods for approximate solution of large linear systems". In: Journal of Computational and Applied Mathematics 227.1 (2009), pp. 27-50. Jinglin Chen and Nan Jiang. Tinformation-thhoreee considerations in batch rein- forcement learning". In: International Conference on Machine Learning. PMLR. 2019, pp. 1042-1051.
[CJ19]
[DB16]
Steven Diamond and Stephen Boyd. "CVXPY: A Python-embedded modeling language for convex optimization". In: Journal of Machine Learning Research 17.83 (2016), pp. 1-5.
[DJW20]
Yaqi Duan, Zeyu Jia, and Mengdi Wang. "Minimax-optimal off-policy evaluation with linear function approximation". In: International Conference Machine Learning. PMIR. 2020, pp. 2701-2709.
[DLLI]]
Miroslav Dudík, John Langford, and Lihong Li. "Doubly Robust Policy Evaluation and Learning". In: Proceedings of the 28th International Conference Machine Learning 2011, pp. 1097-1104.
[DNP14]
Christoph Dann, Gerhard Neumann, and Jan Peters. "Policy evaluation with tem- poral differences: A survey and comparison". In: The Journal of Machine Learning Research 15 (2014), pp. 809-883.
[EGW05]
Damien Ernst, Pierre Geurts, and Louis Wehenkel. "Tree- based batch mode rein- forcement learning". In: Journal of Machine Learning Research (2005), pp. 503- 556.
[JL16]
Nan Jiang and Lihong Li. "Doubly robust off-police value evaluation for reinforce- ment learning". In: International Conference on Machine Learning. PMLR. 2016,
pp. 652-661.
[KL02]
Sham Kakade and John Langford. "Approximately Optimal Approximate Rein- forcement Learning". In: Proceedings of the 19th International Conference on Machine Learning- Vol. 2. 2002, pp. 267-274.
[KU20]
Nathan Kallus and Masatoshi Uehara. "Double Reinforcement Learning for Effi- cient Off-Policy Evaluation in Markov Decision Processes." In: J. Mach. Learn.
Res. 21.167 (2020), pp. 1-63.
[LLTZ18]
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. "Breaking the curse of horizon: Infinite-horizon off off-policy estimation", In: Advances in Neural Informa- tion Processing Systems 31 (2018), pp- 5356-5366.
[LPO33]
Michail Lagoudakis and Ronald Parr. "Leasst-quares policy iteration". In: The Journal of Machine Learning Research 4 (2003), pp. 1107-1149.
10

---

[LSABI9]
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. "Off- policy policy gradient with state distribution correction". In: arXiv preprint arXiv: 1904 08473 (2019).
[LVY19]
Hoang Le, Cameron Voloshin, and Yisong Yue. "Batch Policy Learning under Constraints". In: International Conference on Machine Learning. 2019, pp. 3703- 3712.
[NCDL19]
Ofrr Nachum, Yinlam Chow, Bo Dai, and Lihong Li. "Dualdice: Behavior-agmostic cstimation of discounted stationary distribution corrections". In: arXiv preprint (2019).
[ND20]
Ofir Nachum and Bo Dai. "Reinforcement Learning via Fenchel-Rockafellar Duality". In: arXiv preprint arXiv:2001.011 0.0060008666 (2020).
[NDKCLS19]
Ofir Nachum, Bo Dai, llya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schu- urmans. "AlgaeDICE: Policy Gradient from Arbitrary Experience". In: arXiv preprint /9/2v/99/2.0222
(2019).
[Pai+20]
Tom Le Paine, Cosmin Paduraru, Andrea Michi, Caglar Gulcehre, Konrad Zolna, Alexander Novikov, Ziyu Wang, and Nando de Freitas. "Hyperparameter Selection for Offline Reinforcement Learning". - In: ar preprint arXiv:2007.09055 (2020). Juan C Perdomo, Akshay Krishnamurthy, Peter Bartlett, and Sham Kakade. "A Sharp Characterization of Linear Estimators for Offline Policy Evaluation". In: arXiv preprint arXiv:2203. 220.042300 (2022).
[PKBK22]
[PSS00]
Doina Precup. Richard S Sutton, and Satinder P Singh. "Eligibility Traces for Off Off-Policy Policy Evaluation". In: Proceedings the Seventeenth International Conference on Machine Learning. 2000, pp. 759-766.
[TB16]
Philip Thomas and Emma Brunskill. "Data--Dficii Efficient Off-Policy Policy Evaluation for Reinforcement Learning... In: Proceedings of the 33rd International Conference on Machine Learning. 2016. Philip Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. "High Confidence Off-Policy Evaluation". In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. 2015.
[TTG15]
[UHJ20]
Masatoshi Uehara, Jiawei Huang, and Nan Jiang. "Minimax Weight and Q- Function Learning for Off-Policy Evaluation". In: Proceedings of the 37th In- ternational Conference on Machine Learning- 2020, pp. 1023-1032.
[UI]SXX2]]
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 arXiv:2102 0298/ (2021).
[VLJY19]
Cameron Voloshin, Hoang M Le, Nan Jiang, and Yisong Yue. "Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning.. In: arXiv preprint arXiv: 191 1.66544 (2019).
[XCJMA21]
Tengyang Xie, Ching-An Cheng, Nan Jiang. Paul Mineiro, and Alekh Agarwal. "Bellman--consistett Pessimism for Offline Reinforcement Learning". In: arXiv preprint (eo::2200606222 (2021).
[XMW19]
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. "Towards optimal off-policy eval- uation for reinforcement learning with marginalized importance sampling". In: arXiv preprint arXiv: 1906.03393 (2019).
[YNDLS20]
Mengjiao Yang, Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans. "Off- policy evaluation via the regularized lagrangian" In: Advances in Neural Informa- tion Processing Systems 33 (2020), pp. 6551-6561.
[ZHHJL22]
Wenhao Zhan, Baihe Huang, Audrey Huang. Nan Jiang, and Jason D Lee. "Offline reinforcement learning with realizability and single-polcyy concentrability.. In: arXiv preprint arXiv:2202.044 04634 (2022).
[ZHW221]
Junyu Zhang, Mingyi Hong. Mengdi Wang, and Shuzhong Zhang. "Generalization bounds for stochastic saddle point problems". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2021, pp. 568-576
[ZJ21]
Siyuan Zhang and Nan Jiang. "Towards Hyperparameter-ffree Policy Selection for Offline Reinforcement Learning". In: Advances in Neural Information Processing Systems 34 (2021).

---

Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We discuss the slow rate of our guarantee in Appendix A
(C) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URI.)? [Yes]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] Our experiments are on relatively simple synthetic environments, and did not particularly track the use of computation.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'ne using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "zWa-FChRXfe", "reviewer": "Reviewer_e62P", "summary": "The paper studies the problem of learning the Q-function and density ratio for a given policy in offline reinforcement learning settings, where we have IID state, action, reward, next state tuples collected from the stationary distribution of some behavioral policy. They argue that in past work the focus has been on guarantees on the accuracy of policy value evaluation using estimates of these functions, rather than guarantees on the accuracy of the estimates of these functions themselves. The authors propose a new more general framework for regularized estimators of these functions, and provide guarantees on the L_2 error of the resulting estimates under any given distribution of state/action values. In this analysis, they provide some theoretical results which suggest that, using novel forms of regularization targeted towards some given distribution, they can likely achieve lower L_2 error w.r.t. that distribution. Finally, they test their theory with some simple synthetic experiments.", "questions": "Questions/Comments below:\n1. Saying that estimating the Q-function / state density ratio is “Off-Policy Evaluation” is confusing and contrary, I believe, to most of the literature. Usually, OPE refers specifically to what you call “return estimation” in section 1. I think it is worthwhile making the language use more clear in title/abstract/intro, and making it more clear that the focus of the paper is NOT on performing OPE, but rather on the related task of estimating value / weight functions, which can be used as a sub-routine for OPE (or other RL tasks).\n2. $d^D$ on line 57 of the introduction is not defined yet at that point.\n3. Lines 149-150: you say that “even estimating a single constraint is infeasible as that requires sampling from the same state multiple times”, but it seems like for any given (s,a) the constraints should be identifiable, since the distributions of r and s’ given (s,a) under the observational distribution should be identifiable. Therefore I’m not clear what you mean by this. This requires more detail / explanation.\n4. On line 205 (and later), I assume that $f’_{s,a}$ refers to the derivative of $f_{s,a}$? This notation is currently undefined and should be made explicit.\n5. In figure 2, it is not very clearly explained what is going on with the “model” data. I think based on the parantheses in the text these are showing results where we use $\\tilde q$ as the estimate rather than using your regularized estimator? This should be more clear.", "limitations": "Issues with limitations already addressed in the strengths/weaknesses section. No negative societal impact issues that I think need to be addressed.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Edit: see follow up discussion below for updates on these points\n\nStrengths:\n- The theory is very clean and easy to read / understand\n- They provide a nice, more novel framework for Q-function and state density ratio estimation, with very strong theoretical guarantees for these tasks\n- Their experiments are clean and well presented, and make a reasonably strong case that their novel regularization is good at reducing L_2 error under the target distribution of interest\n- Despite the weaknesses described below on the impact of this work, one positive impact is that it allows a strong relaxation of the identification conditions needed by existing minimax methods for Q-function and state density ratio estimation used in the OPE literature, which is significant.\n\nWeaknesses\n- The problem of needing to obtain strong guarantees on the accuracy of Q-function and state density ratio estimates is not very well motivated. As the authors point out, the main way in which these functions are used in practice is for policy value estimation, which is already very well studied in past work with guarantees for the actual task of interest. The authors mention for example that learning these functions can be used as sub-routines for other RL tasks such as actor-critic methods, but they do not provide much/any detail about this.\n- Related to and expanding on the previous point, since learning the Q-function or state density ratio is not particularly useful in and of itself, it is disappointing that they do not show show that improved performance in learning these functions can actually translate to improved performance in downstream tasks where they might be used. For example, they could provide either: (1) theoretical results that show that realizable versions of their proposed estimators can give improved guarantees for downstream tasks; or (2) empirical results that show that their proposed estimators can improve the performance of downstream tasks in practice. Without either (1) or (2), or something similar, it is not clear that the work is actually high impact.\n- Similar to the above two points, it is also not very clear how useful it is to be able to guarantee low L_2 error under particular target state/action distributions. For example, in the introduction they note that “downstream learning algorithms that use off-policy function estimation as a subroutine often assume the estimation to be accurate under certain specific distributions”, but unless these are fixed, known distributions it is not clear how their theory can be utilized, since they can only provide error guarantees w.r.t. fixed, known distributions. Again, without more analysis about how their theory can actually improve downstream tasks the impact is hard to assess. A concrete and detailed example case study of the use of the theory would be very helpful with these issues.\n- The results about how novel (s,a)-specific forms of regularization can improve performance is fairly heuristic. For example, they suggest using $f_{s,a}(x) = \\frac{1}{2}(x - \\hat q^\\pi(s,a))^2$ for Q-function estimation, where $\\hat q^\\pi$ is some first-stage estimate of the q function, which they argue results in zero error when the first-stage estimate is perfectly accurate, but they do not provide any actual concrete bounds on the resulting L_2 error given provable bounds on the accuracy of $\\hat q^\\pi$. Similarly, in their experiments they do not test these novel regularization methods with actual first-stage estimation of $\\hat q^\\pi$, but only with artificial error added to $q^\\pi$, which makes the empirical usefulness of this novel regularization difficult to assess.\n- There are several trivializing assumptions made, including: (1) finite state space; and (2) finite function classes. While it is true that often extending results using finite function classes to infinite ones using e.g. VC-dimension or Rademacher complexity is straightforward, this is not necessarily always the case (or at least making this exertion is sometimes less straightforward or requires additional assumptions), so not including more general results is definitely a weakness. Similarly, is there any reason why the state space was assumed to be finite? This is an unrealistic assumption in many settings, and none of the results depend on the size of the state space, so if there are any theoretical reasons why the theory doesn’t naturally extend to infinite state spaces this should be made clear. Similarly, the iid data assumption is generally unrealistic, although I am more sympathetic there since it is usually trivial to replace e.g. concentration inequalities, CLT, etc. with corresponding Markovian versions given mixing assumptions; however, there should at least be some discussion in the paper about this.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "rdjm0IlQuAi", "reviewer": "Reviewer_LV55", "summary": "The paper studies estimating Q function in the offline setup. The state-action space is assumed to be discrete and the performance of the estimation is measured under a user-specified measure that can be different from the data distribution. The major caveat stems from the distribution shift and existing results requires completeness and realizability assumptions. This work proposes a Lagrangian method and provides statistical guarantees in the absent of completeness assumption. The analytical framework is further extended to weight function estimation.", "questions": "The Lagrangian form in Equation (4) is obtained from the convex optimization problem in (3). Do we gain any intuition from writing out this convex program? In fact, we can directly use $f_{s, a}$ as a regularizer and obtain Equation (4). On the other hand, there seems to be multiple ways to formulate a Lagrangian function, e.g., we can use a weighted quadratic penalty term $w(s, a) (r(s, a) +\\gamma q(s', \\pi) - q(s, a))^2$. Does the linear penalty in the Lagrangian form work better? Intuitively speaking, quadratic term is naturally related to penalized least square estimation.\n\nHow does Assumption 3 compare to concentrability conditions commonly used in RL literature, which assumes the ratio of visitation measure is bounded? In addition, [DJW20] uses a restricted chi-square divergence term to measure the distributional shift. They showed that the restricted chi-square divergence is tighter compared to density ratios. Can authors also comment on the connection between restricted chi-square divergence to $w_f^*$?\n\nI am also curious about any connection to \"Bellman-consistent Pessimism for Offline Reinforcement Learning\", where an information theoretic confidence set of Q functions is constructed using offline data. The primary goal is different -- policy learning in the Bellman-consistent paper, however, they still obtain an estimation of Q function.\n", "limitations": "I don't see very obvious limitations in the paper, comparing to concurrent theoretical studies of RL. As mentioned, the assumption on weight function $w_f^*$ may be a bit strong.\n\nThe authors discussed the barriers of obtaining faster rate $n^{-1/2}$ in Appendix, which mainly owes to the regularity of the Lagrangian function. I am interested in whether the $n^{-1/2}$ rate is ever possible with novel techniques.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Offline off-policy evaluation is a very important problem in RL and has many applications across various domains. The paper focuses on addressing the change of measure issue between evaluating and sampling distributions. Moreover, the paper only needs realizability assumption. Both of these advances are important in off-policy evaluation. There are many existing works studying off-policy evaluation and to my knowledge, the proposed method here is new.\n\nThe paper is relatively easy to follow, with some minor issues on notations. The result seems correct and sound, although I have not checked the detailed proofs.\n\nI will discuss some weaknesses in the questions and limitations section.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "P_o2h70kvqO", "reviewer": "Reviewer_NNnr", "summary": "The authors provide finite sample Lp rate guarantees for q function estimation via minimax objectives. Unlike prior work they manage to prove guarantees with only realizability assumptions. Prior works obtained such results only for policy evaluation but not q function estimation. Or required function spaces for the adversarial weights that are too expressive to leverage statistical power.\n", "questions": "it seems that many techniques are already existent in the prior work of JHHJL22. If one ignores the extension to measuring dists and just looks at RMSE, then can you elaborate on what new you are bringing on the technical side", "limitations": "Given that this is mainly a theoretical contribution, the above points would need to be addressed before publication.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I found the theory interesting and well presented. The results could be of interest to the community of offline RL.\n\nMy main concerns are:\n\nwhy would one estimate a q function other than in order to estimate an offline policy value. Please provide more motivation as otherwise the results are covered by prior work.\n\nwhy are you restricting to finite action and state spaces. Given all your realizability assumptions it would seem that this is an overkill and defeats the purpose. These function approximation would be primarily most powerful with continuous states/actions.\n\nit is very unfortunate that only slow rates are obtained. Hence even for finite hypothesis spaces one gets n^(1/4) rates. Such realizability guarantees and also the absence of ill-posedness in this inverse problem should be leading to fast rates. See for instance the un-cited work of Chen and Qi: https://arxiv.org/abs/2201.06169 Please relate to this work in your response as it is highly relevant.\nwhy are you only giving bounds for finite hypothesis spaces. This is very restrictive.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept