Interval-based Offline Policy Evaluation without Sufficient Exploration or Realizability
Authors: Kohei Miyaguchi
Hiroshi Kajino
Venue: Submitted to ICLR 2023 (2023)
Keywords: Offline policy evaluation
marginal importance sampling
offline reinforcement learning

Abstract: We study the problem of offline policy evaluation (OPE),
where the goal is to estimate the value of given decision-making policy without interacting with the actual environment.
In particular, we consider the interval-based OPE, where the output is an interval rather than a point, indicating the uncertainty of the evaluation.
The interval-based estimation is especially important in OPE since, 
when the data coverage is insufficient relative to the complexity of the environmental model,
any OPE method can be biased even with infinite sample size.
In this paper, we characterize the worst case of such irreducible bias, called the *minimax bias*, in terms of the discrepancy between the target policy and the data-sampling distribution,
and show that the marginal-importance-sampling (MIS) estimator achieves the minimax bias with an appropriate importance-weight function.
Motivated with this result, we then propose a new interval-based MIS estimator that asymptotically achieves the minimax bias.

Under review as a conference paper at ICLR 2023
OFFLINE POLICY INTERVAL ESTIMATION WITHOUT SUFFICIENT EXPLORATION OR REALIZABILITY
Anonymous authors Paper under double-blind review
ABSTRACT
We study the problem of offline policy evaluation (OPE), where the goal is to estimate the value of given gecision-making policy without interacting with the actual environment. In particular, we consider the interval- OPE. where the output an interval rather than point, indicating the uncertainty of the evalu- ation. The interval-based estimation is especially important in OPE since, when the data coverage is insufficient relative to the complexity of the environmental model, any OPE method can be biased even with infinite sample size. In this pa- per, we characterize such irreducible biases in terms of the discrepancy between the target policy and the data-sampiln samplig distribution, and show that the marginal- ayportance-samplee (MIS) estimator achieves the minimax bias with an appro- priate importance-weigle function. Motivated with this result, we then propose a new interval- MIS estimator that asymptotically achieves the minimax bias.
INTRODUCTION
The offline policy evaluation (OPE) is the of estimating the value of given decision decision-making poli- cies based on offline datasets without interacting with the actual environment. Since the interaction with the environment is often infeasible or expensive in many real-world applications, it is better to evaluate the value offline rather than online.
In the literature, it is understood from theoretical perspectives that there are two fundamental condi- tions for OPE to be successful: sufficient exploration, the coverage of the data-sampling distribution over the state-action space relative to the target policy, and realizability, the knowledge of correct environmental model with bounded complexity. In particular, if neither of these two conditions met a certain manner, it is known that OPE is never sample efficient, i.c., it takes prohibitively large sample make the estimation reasonably accurate (Wang al., 2020 Zanette 2021). In prac- tice, given a problem instance of OPE, consisting of an environment and a dataset, it is difficult to confirm that these conditions hold or modify the problem instance so that these conditions hold, making the existing theoretical guarantees less practical. Towards practical OPE, we set our research objective develop a theoretically-sound value estimator without assuming these two conditions.
Towards our objective, we first analyze the statistical performance of OPE methods when the two assumptions do not hold (Section 4). The key quantity is the information-thhoredt -heoretic worst-case bias of the value estimator (Eq. (5) and its minimum termed the minimax bias (Eq. (6)) which is positive when there exist multiple indistinguishable environments, given only problem instance of OPE. In fact, we show that the minimax bias can be non-zero if we do not assume the two conditions (Corol- lary 4.2p. suggests that, without the two assumptions, there exists problem instance that any point-based value estimator is not reliable.
Given the existence of irreducible bias, we propose an alternative formulation of offline policy eval- uation called minimax-bias offline policy interval estimation (minimax-biac OPI), where the objec- tive is to estimate the shortest possible interval containing the true value, instead of a point esti- mate (Section 5) Since characterization of the minimax bias allows to define the optimal interval (Definition 5.1). the minimax-bias OPI is formulated as a problem to estimate the optimal interval (Problem 5.1)
We provide a thcoretical foundation to solve the minimax-bin bias OPI based on the marginal impor- tance sampling estimator (Section 6). The key result is that the optimal importance weight mini-

---

The non-asymptotic methods typically put their emphasis on the validity of the interval with any finite sample size, where intervals are valid if they contain the true value (Ix). For instance, Feng et al. (2000: 202T) compute intervals that contain the true policy value with high probability, under Under review as a conference paper at ICLR 2023
mizing the distributional Bellman residual (DBR) allows to construct approximately optimal interval (Theorem 6.3) This illustrates that our problem setting is well-posed and can be solved under realistic assumptions if we can solve the minimization of DBR. Accordingly, we develop novel algorithm in Section to find the best importance weight function, which results in an interval estimator applicable even if the two fundamental conditions do not hold (Theorem (77].
Before proceeding to these results, we introduce basic mathematical notation in the rest of this section, review the related work in Section and introduce the useful OPE-specific notation in Section 3
Mathematical notation. Let denote the identity operator and let avb max(a, b) and aAb = min by denote the maximum and minimum operators for a, b E R. respectively.
Let X' be metric space with Borel algebra E. Let 9 (X) and & (x) be the spaces of the rallev measurable bounded functions and the continuous functions on X, respectively, both of which is equipped with the uniform norm || = suprex f(x)]. Let (X)) denote the space of the finite signed measures on the same space X' equipped with the total variation (TV) norm || == xupp_+
P[E-)}. In particular, let 82 E (X)), x E X, denote Dirac's delta measure. For any f E (x) and any P E (X)), let (f.P) = f be shorthand for the (signed) expectation of f with respect to P. Let @ denote the importance-weigee weighhtng operation given by d(f & (z) = =(x)dd(x)), f E (X)), P E (xX. Let (P) be the space of the functions integrable with respect to P PE (2), i... IIʃ @ Pl[tV xc.
Let L(V) denote the set of the bounded linear operator normed vector space V. For any E L (x)),, let A" E (X)) denote the conjugate operator such that (A* P) = (J, AP) for f E (X) and P E (X)).
2 RELATED WORK
The problem of estimating the interval containing the true value has been known as offline policy interval estimation (OPI). This section reviews the existing studies on OPI by dividing the previous OPI methods into two categories: non-asymptotic and asymptotic methods (see Table for the summary of comparison). We also discuss our contribution the literature.
the realizability of the policy Q-functions 9-- [lingg and Huang (020)) also proposed an interval esti- mator with validity under more relaxed realizability condition that either the policy Q-function dx or the marginal density ratio function Wa is realizable. One limitation of this approach the theoretical understanding on the tightness of the interval is often unclear or partial. Another limitation of this approach is that they tend to require the realizability with known complexity. This requirement not desirable for practical use: if we used a too complex hypothesis class such as reproducing kernel Hilbert space with infinite radius, the resultant interval would be trivial and thus, non-informative.
The asymptotic methods focus on the asymptotically dominant term of the uncertainty in the large sample limit, which typically allows us to theoretically understand their behavior, especially the tightness, in depth. For instance, Kallus and Uehara (2020): (Shi et al. (202I) gave confidence interval estimators that achieve the efficiency lower bound. The bootstrap estimators (Hao et al. 2021) also enable us to compute the asymptotically exact confidence intervals in a more flexible manner. One major limitation is that they assume both the sufficient exploration and the realizability conditions of 9n and w, hold, which can be hardly validated in real- world applications. These assumptions are essential to their analyses because they focus on estimation of the asymptotic variance of order O(n -1/2), assuming that the bias is negligible. Therefore, these methods are not applicable to our setting where the asymptotic bias of order O(1) dominates the asymptotic variance.
In this study, we take the asymptotic approach, but with a focus on the estimation of the bias rather than the variance, because the bias is dominant in our setting where the sufficient exploration and the realizability do not hold at all. Our contributions are threefold. First, we characterize the theoretical lower bound of the asymptotic bias through the asymptotic analysis, which serves as theoretical
2

---

Under review as a conference paper at ICLR 2023
Comparison of OPI methods. 4x and fe denote the Q-function and the marginal density ratio function, respectively, w denotes generalization of wa for the insufficient exploration setting.
Table I:
Assumptions
Method
Guarantee
Asymptotic
Exploration
Realizability
Complexity
BONDIC Feng et al
2021
qF
Known
Valid
MVI [Jiang and Huang
2020)
q+ or Wn Known
Valid
DRL (Kallus and Uchara
2020
Yes
Yes
4n and Wx
Efficient
D2OPE (Sh el al.
2021
Valid
Ours
W
Optimal
foundation of OPE without sufficient exploration or realizability assumptions. Second, without the two assumptions, we develop an interval estimation method that outputs an asymptotically valid interval, that is, an interval that contains the true value in the large sample limit. Third, under the realizability condition of the generalized marginal density ratio function w we show that the estimated interval is optimal.
3 PRELIMINARIES
We first introduce our formulation of reinforcement learning and offline policy evaluation. Then, we introduce two fundamental concepts RI., a Q-function and an occupancy measure, along with shorthand notation for them.
Offline policy evaluation. Let e' = S x A be a compact Hausdorff space representing the state-
action space of the system with | xo [ Let M (1, R) be the Markov decision pro- cess (MDP) of environment on X, where 1 E 4 (S) is the initial state distribution, T X' -4 (S) is the transition dynamics and R X' -> (I 1]) is the conditional reward distribution. Let S - (AA) be the target policy. Then, the value (T) of a with respect to M is given by the y-discounted expected average reward
8 ((T) JM(T) = E.M (1- Σ+ r
E.M.
where > E (0, 1) is discounting factor and B.,ar denotes the expectation with respect to the Markov chain generated with a, ((:), Tt R(st, az), 8141 T(sr, ac) for all > 1 and
In offline policy evaluation, we are given dataset D = (Dr, PT,R) as input, where D, == { a of initial states and DT,R = {1x, s/ r ]
1 is set of transition records sampled from
m
dG II de du(s..)) II (T
where 3 E (x') is an arbitrary state-actions aate--actio--samllin distribution Then, an instance of the offline policy evaluation (OPE) is identified by the quadruple P. = (M, 3, ग, 7) and formalized as follows. Problem 3.1 (Offline policy evaluation, OPE). Given (D, 7) where D G estimate J(T).
Q-function and occupancy measure. Let E M(X) and T, (())( be the initial state- action distribution and the state-action transition operator associated with æ such that di, (s, a) = di( (u(s)dr(aas) and d(T,P) a) dT x ()
for S. A and P E M (x),
Thii includes cases where S and are finite or compact subsets finite-dimensional Faclidean spaces. For simplicity, assume the sample sizes of DD and DD,, are the same. The generalization with different sample sizes is possible with minor modification.

---

Under review as a conference paper at ICLR 2023
respectively. Also let p E ((²) be the expected reward function such that p(x) = rdR(rl=) for x E N. Then, the value ((x) is rewritten as
J(x) = (p, x()) (T (x) = (p. (9T.
(1)
where r = (1-7) - E (())( is the accumulation operator, Fx == r' E Al (2') is the normalized occupancy measure of (henceforth the occupancy measure), and 9t 1 E (() is the normalized Q-function of π (henceforth the Q-function). Note that we have o S 1 and || thanks the normalization.
Two Bellman equations. One of the essential difficulties of OPE lies in the fact the direct estima- tion of the accumulation operator I' (and hence μs and qn is intractable due to the infinite sum. The Bellman equation is useful to mitigate this problem. Here, introduce two variants of the Bellman equation, the functional and distributional Bellman equations, given by
P == Ar
4T Pn Mz.
where A : = (I (T,)/ - 7) the difference operator. Note that, in the Bellman equations, both fur and μlx are uniquely characterized via more directly estimatable quantities (p, Tx) and (1r, Tr), respectively.
The errors of the Bellman equations are referred to the Bellman residuals. In particular, the distributional Bellman residual (DBR) is given by
(w) = 4 E
which plays an important role in our analysis.
Empirical estimates. Finally, we introduce the empirical estimates of (lx, (1 P, based on the dataset as follows. For all P E. M. (x) and x
X.
1 n n 1=1
4x
T.P
P((x)), p(x) N(x,)
Σ T4
B
N(x) $1
72
where N(x) = V (i x4= = x is the data-counting function (with the zero-division safeguard) and Te,s == (St,is ac.i) and r (s/, a;) are the state-action pairs associated with additional samples agi ~ T (s,,s) and df ~ x(s)), respectively.
Throughout this paper, we employ the conventional marginal importance sampling (MIS) estima-
tor (Liu et al. 2018: Xie et al. (201)) to estimate the value in offline. The MIS estimator associated with weight function 36 (X) is given by
j(w) = (p. w 2 B).
(4)
The MIS estimator is justified if the weight function w equal to the marginal density wr := dkz
(assuming exists) since, in that case, the MIS estimator is unbiased, B[j(w=)] [TT) according to ①I.
Note, however, that w- does not exist when the exploration is insufficient, 3 * 1. and the unbi- asedness cannot be guaranteed in general. Two natural questions thus arise: Does the MIS estimator still enjoy any theoretical guarantee in such general setting? so, what the best weight function w? In short, the answer to the first question is affirmative and the answer to the second question is one of the main contributions this work.
4 IRREDUCIBLE BIAS IN OFFLINE POLICY EVALUATION
In this section, we theoretically analyze the statistical performance of OPE methods without suffi- cient exploration realizability assumptions. As result, will show that any OPE method must incur an irreducible bias that never disapears even when the sample size goes infinity. Given such a negative result, instead propose novel problem setting called the minimax-bias OPI, where the
4

---

Under review as a conference paper at ICLR 2023
goal is to estimate the interval that contains the true value and is short as possible. The proposed problem setting is expected to be solved without sufficient exploration or realizability assumptions, and thus, will be of practical use.
To study the statistical performance of OPE methods, we introduce the notion of the minimax bias of the point-based estimators. Let J be any random variable representing a point- based OPE estimator. Then, the information-theoreiic worst-case bias of J is given by
{M = c[]; =
sup (M..8))(M..)
(M) -E.
(5)
where the equivalence is defined by the equality with respect to the corresponding distributions of the dataset, ie., G = G.M.3. If there exist equivalent environments .M and .M' that result in
the different policy values J # JM (अt) yet indistinguishable from the dataset, the worst-case bias e[J] is inevitable without an additional source of information, i.c., domain knowledge. The minimax bias is then defined the minimum possible worst-case bias of OPE,
cx (T) = e (T; inf (J;
(6)
which be thought of as a characteristic of the problem P indicating its hardness in terms of the irreducible uncertainty even with infinitely large sample. In fact, there exists the unique J achieving the infimum and we refer to it as the optimal point estimator (T). Our main objective is to understand the minimax bias various settings.
To this end, we introduce novel concept, the projection of the occupancy measure H4r with respect to 3. Let H1 be the projection operator onto the support of 3 such that II P Xa x M (X) and (x) = 1 {x supp 3).
Definition 4.1 (Projected occupancy measure and its importance weight). We refer to
1 = (1 - T Σ
t=0
as the projected occupancy measure of n. Correspondingly, we also refer to
du4
d3
as the projected importance weight of with respect to 3.
Note that W can be thought of as extension of wx in the sense it is always well-defined and w = wn whenever wa exists. On the other hand, μ can be thought of as the known component of H4 since it is always identifiable given GM,s,, thanks to the projection ITg, and μ /e whenever 14, is also identifiable.
We now present main result, which discovers close relationships between the minimax bias (T), the MIS estimator (wn,, the DBR (w) and the projected importance weight wf.
Theorem 4.1. For all w E B(X), have
1+ 2 w w (I)) (T) < e [J(w]] < (1+ (T((T) + 1-7
(8)
Proof (sketch). The most nontrivial part the last inequality, which follows from the constructive proof of
( > (w
In particular, we construct two worst-case environments M₁ under the constraint (M+ 9) (M,3) Roughly speaking, the environments are constructed to have a special state 1 in the under- explored region of X' absorbing all the transition to that region, and have the extreme reward there, i.e., p(1) = +1. With this explicit construction of the environments, we can give an analytic lower bound of e, (TT), which coincides with R (wof I|TV. See Section B for the complete proof.
n
5

---

Under review as a conference paper at ICLR 2023
An immediate consequence of Theorem 4.1 that tells when and how the minimax bias is positive. To see this, let μ = fx - 11_ be the projection residual of pt- Corollary 4.2. We have e. (T) = || 2 ITV and thus
1
I S <.(())
ITV-
In other words, the minimax bias is zero if and only if the projection residual μ is zero, equiv- alently. if je is absolutely continuous with respect to the data distribution 33. Moreover, the size of the minimax bias is proportional the size of the projection residual nk It thus formally asserts the limitation of the point-based estimators in the insufficient exploration settings.
In summary, any OPE methods must be biased in the worst case whenever the exploration is insuf- ficient, fx * 3, motivating the interval-basee approach.
5 PROBLEM SETUP: MINIMAX-BIAL OPI
As discussed above, the point-based estimator suffers from irreducible bias, suggesting hardness in under
Problem under realistic assumptions. Given such a limitation, propose alternative problem setting called the minimax-bias OPI so that we can solve under realistic assumptions. Since there exists bias, idea is to estimate the value by interval that contains the true value, instead of point.
Let us first define the target of the estimation, which call the optimal interval. As discussed car- lier, since J. (x) and e, (T) are the best possible point estimator and its enror guarantee, respectively, the optimal interval can be naturally formulated as follows.
Definition 5.1 (Optimal interval). The following is referred to the optimal interval:
(T) = I. (T; P) [J.(T) - c. (T), (+T)) + (T)).
Then, the problem of offline policy interval estimation (OPI), an uncertainty-aware interval exten- sion of Problem 3.1 formalized follows.
Problem 5.1 (Minimax-bias OPI). Estimate [,) bused on (D, m, 7), where D G
Towards estimating the optimal interval, let us introduce two desirable properties of an interval. Definition 5.2 is stronger than Definition 5.3
Definition 5.2 (Approximate optimality). We refer to the interval I satisfying du (I, S 6, where du (-..) the Hausdorff distance, as e-approximately optimal. Moreover, a sequence of intervals { is said to be asymptotically (approximately) optimal if it converges to an (ap- proximately) optimal interval.
Definition 5.3 (Validity). An interval I R is said to be valid I (T). Moreover, a sequence of intervals [Inha21 said to be asymptotically valid if its lower limit lim3-+00 Onz In is valid.
THEORETICAL FOUNDATION OF MINIMAX-BIAS OPI
We provide a theoretical foundation to solve Problem mainly referring to Theorem 4.1
implies that the MIS estimator J(w) with the projected importance weight First, Theorem 4.1
W is optimal in the sense it achieves the minimax bias. More generally:
Corollary 6.1. There exists (B) such that e(J(w:) (..)
This motivates us to seek for the best weight function w within the MIS framework. The following corollary shows the next significant implications, that the optimal point-based and interval-based OPE is achieved with combining the MIS estimator and the minimization of DBR.
Corollary 6.2. Let w. be a minimizer of DBR in a compact hypothesis class W C B(X).
E argmin Rr (w) TV
(10)
wEW

---

Under review as a conference paper at ICLR 2023
Then, have
- J. (x -
ew, 7
1 1
(1I)
and
R (w.) (T) 1 1
1- cw:
(12)
where Ew == milwew ||w w (0) is the realizability error of W.
In other words, given W is expressive enough to approximate w well and thus ew is negligible, the optimal point estimator (²(x) and its uncertainty (.(T) can be estimated with a solution w, to (TO) and its objective value 2 (w, l|v,, respectively. These observations naturally lead us to the following proxy to the optimal interval
I(;; W) [w( (u.)(llllly [E.(w.) (u.)(Ty)
(13)
In fact, it satisfies two desirable properties: the validity and the approximate optimality. Theorem 6.3. The interval I(m;; W) is valid and 1+2
I 1- cw-aprrxxiaatll optimal.
ESTIMATION OF OPTIMAL INTERVAL
As discussed in the previous section, the estimation of the optimal interval I, (TT) is reduced to the minimization of the TV norm || (R)(()]|r However, even the estimation of the exact TV norm is notorious for its difficulty (e.g., see Section in (Sriperuumbuurr al. (2012)) let alone the minimiza- tion. This motivate us to develop new variational approximations for the TV norm. In particular, newly introduce two approximations of R2 (w)l[VV. each of which is suitable for the evaluation and the optimization of the objective, respectively.
7.1 EVALUATING THE OBJECTIVE
The first approximation reduces the evaluation of the TV norm to conventional regression problem. To see this, let us begin with the approximation formula for the TV norm of general measures.
Let F be universal function approximator on X, i.e., set of functions dense in (X)). such as the reproducing kernel Hilbert space (RKHS) with universal kernel (Sriperumbudur et al. 2010) or set of neural networks (Hornik et 1989).
Proposition 7.1. For all positive measures P E (2)), we have
PP sup ([.l. P)
(14)
fEF
where [t]] == max(-1, min(mmnnmm1 } denotes the clipping of E to [-1,1]
The proof is relegated to Section C Letting P = Rr (w), we immediately get the following special case useful for the evaluation of DBR.
Corollary 7.2. For all w E (XX), we have
[R)(()) = [u R2 (w)).
(15)
fEF
The supremum 15 is estimated via the regularized empirical risk minimization framework, mini- mizing the following objective
=(f)=-(11) Rw)w)) #(f).
(16)
3) is the natural empirical counterpart of the DBR, V : F + IR. is a penalty function that makes it easier to minimize and prevent the minimizer from overfitting, Once the regularized empirical risk minimizer f i= argmin L(F) is found, we then evaluate [[f], R=(w)) to approximate the RHS of (15) and get the desired estimate. The resultant procedure of the evaluation of the TV norm is summarized in Algorithm A.1
where
In fact, under a reasonable choice on F and V, shown that the output of Algorithm A.I is consistent. The details on the specific choice of F and v and the proof is provided in Section
7

---

Under review as a conference paper at ICLR 2023
Theorem 7.3. Let EvaluateDER w) be the ouppu of Algorithm A.1 where F and v are given as in Section D.1 Then, for all w E W, we have EvaluateDBR F,).w) - (w)]ll in probability.
7.2 MINIMIZING THE OBJECTIVE
We now turn to the minimization of (w=)lV with respect to w E W. The previous varia- tional formula (15 is not straightforwardly usable for this purpose since ends up with the saddle- point problem, which we found is too unstable in practice. To mitigate this issue, we introduce minimization-bant based approximation of the TV norm.
To this end, we first introduce the convolution of the TV norm with the maximum mean discrep- ancy (MMD) (Sriperumbudur et al., 2009). Here, the MMD of measure E M (x) is given by MMD, (P) = ((s, p82), where x: X² - is en-universal kernel in the sense of Sriperum- budur et al. (2010) and p82 denotes the product measure of P on X².
Definition 7.1 (Convolution norm). For all P E (X)) and 2 1, we refer to
|Pl inf QEP
[uMMD, Q) 1|Q[|Tv)
(17)
as the u-convolution norm of P.
The following proposition shows the u-convolution norm is reasonable approximation of the TV norm and admits sample-based estimation unlike the TV norm. Proposition 7.4. For all E (X),, we have
|| = lim ||lla 40000
(18)
Moreover, if P is probability measure, for all E (0, 1), we have
=01 u² + ln(1/))
Il -lluxx = -Plluxxx0
(19)
with probability 2 8, where Pr. = 1 En dr, is the empirical distribution of an n-sample
1=
(Ii,..., Fn) independently drawn from P, n
Proof. The key of the proof is Lemma E.2 which gives the dual representation of the convolution norm,
||la,, sup (f. P): (E(0(X)) ff
where H is the RKHS generated by Then, the density of the universal RKHS in ((X) implies that lim || = sup ولل= Si (f, P) = [P[[Tv. which proves the first statement. The second statement follows from the uniform law of large number, namely Theorem H.5 and Lemma H.6
Slightly extending it for the sample approximation the DBR (w (w), we obtain the following approximation formula useful for the weight optimization. The proof given in Section
Corollary 7.5. For all w E (X),, we have
[R) + (R
(20)
in probability
and n/v²
In the practical implementation, one may change the variable in the LHS of (20) from the measure Q E Al (X) to the function g ((X).
| (w)llu.
inf Q.
(uMMD, (w) Q) [1Q1
{ (R, 3 nxx (19), fx))
min (E(((2)
(21)
8

---

Under review as a conference paper at ICLR 2023
Algorithm 7.1:
Minimax Optimal Interval Estimation (MOI)
Input: Dataset D, universal approximator F, hypothesis class W, kernel k;; Output: Estimate of the optimal interval (x));
= Opt imi www.miieeeeeD..
W.R).
// Algorithm Algorithm
A.2
é EvaluateDBRR(CC F, .)
return [T - [w] + +
where fx = (ix + fx,3 + 93.3. Here, we have exploited the transitivity of the absolute continuity with Q < (w) < ft. Note that the minimization with respect to is tractable since is only
evaluated on the support of îi. which is a finite set. Moreover, the convolution basod formula (2T) is stable with the minimization with respect to E WW resulting in the joint minimization problem
of (wr.) g). unlike the regression-bant baaed formula 15 resulting in the saddle-point problem.
Since the objective of (1 is lower bounded and convex with respect to (w: 9), the minimizer
Da == argmin || (w) 1u,x
(22)
wEW
is computed with any convex optimization algorithms. The hyperparameter u is then chosen from predefined grid so that the TV norm DBR is minimized. Specifically, one may choose it as the logarihhmically-vee grid U == {2*) kmax
k==)) where the upper limit kmax == [log2 / /mmiffu (n, m is determined according to the order of empirical approximation error (19). The entire procedure of the weight estimation is summarized Algorithm A.2 By derivation, we can formally show the consistency of Algorithm A.2 The proof is relegated to Section G
Theorem 7.6. Let Apptiiiznn (eDBR W, k) be the output of Algorithm Opt ietimiieell imiizeDB((D)) D, F,W, K) w, in probability
A.2
Then,
00.
Finally, we present our OPI method in Algorithm 7.1 called the minimax optimal interval estima- tion (MOI), which is straightforwardly derived from Algorithm A.2 and the equation (13). We can also guarantee the validity and the approximate consistency of MOI in the asymptotic sense. The proof follows directly from Theorem 7.6
Theorem 7.7. Let MOI(D, F,W, k) be the output of Algorithmm 7.1 Then, MOI(D,,,W, is asymptotically valid and 1+7
1-7 ew-approximately optimal in probability.
CONCLUSION
In this paper, we have studied OPI without the sufficient exploration and the realizability conditions. In particular, we have pointed out the existence of the irreducible bias in such general setting, and correspondingly, introduced novel formulation of the interval-based OPE, We have then revealed the connection between the conventional MIS estimator and the irreducible bias, which is eventually utilized to construct the proposed method, the minimax optimal interval estimator (MOI), and to prove its optimality.
One of the major limitations of the proposed method is its model agnosticity, lying at the opposite end to the model-bar based approach, e.g., Yu al. (2020), that depends the full correctness of the model. It is left for future work to extend and combine these methods to be applicable to partially correct models.
REFERENCES
Boucheron, S., Lugosi, G., and Bousquet, O. (2003). Concentration inequalities. In Summer school on machine learning, pages 208-240. Springer.
Feng, Y., Ren, T., Tang, Z. and Liu, Q. (2020). Accountable off-policy evaluation with kernel bellman statistics. In International Conference on Machine Learning, pages 3102-3111, PMLR.
Feng, Y., Tang. Z., Zhang, N., and Liu, Q. (2021). Non-asymptotic confidence intervals of off- off-policy evaluation: Primal and dual bounds. arXiv preprint 113.v12103.05741

---

Under review as a conference paper at ICLR 2023
Hao, B., Ji, X., Duan, Y., Lu, H., Szepesvari, C., and Wang, M. (2021). Bootstrapping fitted qr evaluation for off-policy inference. In International Conference on Machine Learning, pages 4084- PMLR.
Hornik, K., Stinchcombe, M., and White, H. (1989). Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366
Jiang, N. and Huang. J. (2020). Minimax value interval for off- evaluation and policy opti-
mization. Advances Neural Information Processing Systems, 33:2747-2758
Kallus, N. and Uchara, M. (2020). Double reinforcement learning for efficient off-policy evaluation in markov decision processes. Journal of Machine Learning Research, (167)
Liu, Q.. Li, L., Tang, Z.,, and Zhou, D. (2018). Breaking the curse of horizon: Infinite-horizon oof-po estimation. Advances in Neural Information Processing Systems, 31.
Shi, C., Wan, R., Chemoohuuoo, V., and Song, R. (2021). Deeply-debiased off-policy interval estimation. International Conference on Machine Learning, pages 9580-9591. PMLR.
Sriperumbudur, B., Fukumizu, K., and Lanckriet, G. (2010), the relation between universality, characteristic kernels and rkhs embedding of measures. In Proceedings of the thirteenth interna- tional conference on artificial intelligence and statistics, pages 773-780. JMLR Workshop and Conference Proceedings.
Sriperumbudur, B. K., Fukumizu, K., Gretton, A., Schölkopf, B., and Lanckriet, G. R. (2009). On integral probability metrics, piiiiis.pppiddieeeeeeees and binary classification. arXiv preprint arXiv:0901.2698.
Sriperumbudur, B. K., Fukumizu, K., Gretton, A., Schölkopf, B., and Lanckriet, G. R. (2012). On the empirical estimation of integral probability metrics. Electronic Journal of Statistics, 6: 1550- 1599.
Wang, R., Foster, D. P., and Kakade, S. M. (2020). What are the statistical limits of offline rl with linear function approximation? arXiv preprint arXiv:2010.1189)
Xie, T., Ma. Y., and Wang, Y.-X. (2019). Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. Advances in Neural Information Processing Systems, 32.
Yu, T., Thomas, G., Yu, L., Ermon, S., Zou, Y., Levine, S., Finn, C., and Ma, (2020). Mopo: Model-based offline policy optimization. Advances in Neural Information Processing Systems, 14144222-1442..
Zanette, A. (2021). Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl. In International Conference on Machine Learning, pages 12287-12297. PMLR.
10

---

Under review as a conference paper at ICLR 2023
CONTENTS
Introduction
2
Related Work
Preliminaries
Irreducible Bias in Offline Policy Evaluation
Problem Setup: Minimax-Bias OPI
6
Theoretical Foundation of Minimax-Bin Bias OP1
7
Estimation of Optimal Interval
Evaluating the objective
7.2
Minimizing the objective
8
Conclusion
Algorithms
11
Proof of Theorem 4.1
11
Proof of Proposition 7.1
14
D Details and Proof of Theorem 7.3
15
D.I Choice of Function Approximator and Penalty Function
15
D.2 Consistency Analysis
15
Dual Representation of Convolution Norm (Proof of Proposition 7.4)
19
Proof of Corollary
21
Proof of Theorem 7.6
22
Basic Definitions and Results
22
H.1 Signed Measures
22
H.2 Rademacher Complexity and Uniform Law of Large Number
24
H.3
Reproducing Kernel Hilbert Space
26
A
ALGORITHMS
B PROOF THEOREM 4.1
We first show the first two inequality.
11

---

Under review as a conference paper at ICLR 2023
Algorithm A.1: Evaluation of DBR
Input: Dataset D, function upproximator F, density-ratio estimate w;; Output: Estimate of [
argmin Lff), where E(f) is given by (16
// See also Section
b ([/I, Rw));
return b;
Algorithm A.2: Optimization of DBR
Input: Dataset D, universal approximator F, hypothesis class W, kernel Output: Approximate minimizer of |[ (w))llVi
for E 21 do
th argmin RR, (w) Juxi
E._ = EvaluateDBR(2) F, tb.)
11 Algorithm A.1
= argmin, tvi
return Wp:
Lemma B.1. For all ((X),
(T))) S {ew)) s (w)]lTy
(23)
Proof.
The first inequality is trivial. To show the second one, observe
JM(()) 1 B.((w)
ke,, Tn w 2 B}]
Ka ls (w ())1
Mgx, R,((w))
& [
where the last inequality is owing we thus have
1lo s Since the RHS is independent of M given GM,3,
<[[w]]=
sup M..Gxe,==Gm.
JM B.(ww) s [R)
(24)
Now, to prove the last inequality, we prepare two extreme, yer indistinguishable environments
Mi = (r. 7, R
Let π be an arbitrary state-transition operator indistinguishable from T. which will be deter- mined later. Also let T. be the state-action transition operator associated with T and such that d a/æ) = (s)r))d((()))) for æ, (s, a) E X. Let й. == (1 -)( --,))_ be the com- occupancy measure of M+ induced with T, and Aa lalko be the singular component of j., with respect to 3. Let Xg be a set separating jb, &g from 3 and X3 = X \ Xo be its complement For convenience, let 11,,, 1ll (x)) + A (X') denote the projections of measure onto X₃ and Xo- respectively, given by IIg = X9 3 P. and II,
Xa) P where X8 being the indicator function of X's such that (x(x)= = if E X'g and Xo(x) = 0 otherwise. Note that A I = IojA by construction.
Finally, put (x) = 811 for I E Xo and (x) R(x) otherwise, which is necessary for the indistinguishabiiity of Ri, and denote the associated expected reward by (1) f (r(a))) x E X. Then, we have
-TT = (p+ p_, = 2 jillallly
(25)
That is, (No, X3 is partition of X such that 1 F.) for all measurable E. c X's and ((F) for all measurable No.
12

---

Under review as a conference paper at ICLR 2023
where (TT are the policy values with respect to M+
Now, the following lemma connects the RHS of (5 with DBR.
Lemma B.2. There exist I indistingutisable from such that
|1 l - [R (wt ||TV.
(26)
Proof. The proof constructive. Consider an expanded state space + Su(L), where denotes an absorbing state of T. Accordingly, let Xy + Xy U ({ x A). Now, put T == T + 7 * such that T5 is the restriction of T onto X3 and T a is the absorbing transition, respectively given by
π & P P(X)) 81:
P (x))
Here, T, is corresponding to the known component of T, which necessarily coincides with that of I' by definition, and T' * x is corresponding to the unknown component of T. Note that T is proper transition operator indistinguishable from
Let Txl sg and Ts s be the statc-action transition operator associated with Ta and To, respectively, such that dl' (s, alær) = | (s) and dř kals, a|z) = d (s(x))) for a, (s,a) E X. Then, have
- 71-r = (1 TT)
= (I 7T k 7T (4.3) P0
(I 3T < 7 (N )
(1 1 <<8))s - 7 p+ 1l
which implies, with P = :1= - x3)) (mm
Ln
jA = (1 (1-7)P-- 21 11 1 2 [Tv
7f -2010
= (1 7 1
( (:
Measuring the volumes on Xo. further get
|1 =(1 -1-7)P((X)) +
which yields
P(Xo) |1 lell
(27)
On the other hand, since : = (1 7) P) we have
R2 [R, IT
Lg (1 - -,
TV
(TD - (x.)
(: T.T:ll +t((E
1 1g IIITT l
(:Trles= - +IoTrl+0)
TV
Th
iT + + 1
TT P
(1 -==))r)))))pp11
P(X)).
Combining it with (77 we get the desired result.
Plugging 26 into
we have
1 R (T
(J+(E)
(28)
13

---

Under review as a conference paper at ICLR 2023
with specific configuration of T. Since M2 indistinguishable from another, any estima- tors must incur the bias of at least a half of the difference (+()) - J-((T) in the worst case, i.e, R2 (w I (T)). This proves the last inequality of (8) via the triangle inequality.
(w)(w)) Σ ((R=(wi) ITT + | - w o 1T
<. + + 7 I w (2)
and thus concludes the proof of Proposition 4.1
C PROOF OF PROPOSITION 7.1
First, we introduce saddle-point formulation of the TV norm. Let Fi = (fEF ll I be the intersection of with the unit ball of ( Lemma C.1 gives a general variational formula of the TV norm.
Lemma C.1. For all P E (x)), we have
|P
sup (f. P). fEFi
(29)
Proof. Let us denote the unit ball of (X) with U1 = {f E (X)
|| S 1J. As an instance
of the integral probability metrics (IPM), the TV norm known to be written as
| Iv sup (g. P)
(30)
gEl4,
Now fix g U1 such that 1||||v (g. P s for positive constant 0. Since Fi is dense in (2)) Uu, also dense (P) Un and therefore there exists f E Fi such that Then it follows that
Ilf (P)
||| - (f. P)| S P| - (g. p\ + Il gllm)p) S 2c.
(31)
Since e > 0 can be arbitrarily small, we finally have
|| < sup (J, Pt < sup (g, P] < |||TT
(32)
SEF
gEl41
which proves the desired result.
Since the supremum in 29 is taken over constrained domain F1, its computation is not necessarily tractable general. The following lemma useful make the domain unconstrained.
Lemma C.2. Let V ((x) R2 be penalty function such that (t) = Of e Fi. Then, for all P E M we have
sup (J, P) sup (L/ P) - v())
(33)
SEF
JEF
where [f](x) max min (x))} denotes the clipping of f(x) [-1,
Proof. Slightly extending
32 we have
||||v
sup (J, P)
feF
sup ((f, P) - (())
feFi
sup (I[S], Pt - v()) fer
(: domain expansion)
< sup (g, P) gEth
(: [1] eu, v() 2 0)
$ Pl|Tv.
This yields the desired claim.
Finally, Proposition 7.1 is proved taking the penalty function as the trivial one, (ff) = for all
F. We utilize nontrivial penalty function in Section D
14

---

Under review as a conference paper at ICLR 2023
D DETAILS AND PROOF OF THEOREM 7.3
We first present a preferred choice of the function approximator F and the penalty function V which is needed to construct the objective function (( in (16). Then, we prove Theorem 7.3 to show the consistency of the resultant algorithm (Algorithm A.1
D.1 CHOICE FUNCTION APPROXIMATOR AND PENALTY FUNCTION
As for the function approximator F, choose universal RKHS. Let K 2 R be the cor- responding symmetric positive-defintt kernel. We assume 6 is cn-universal in the sense of Sripe- rumbudur al. (2010). Also, without loss of generality, sup,,z'EX | S 1. For instance, the Gaussian kernel n( y) = exp(-1e - 0 2 E R d 1, > O, is one of such choices.
assume λ is normalized. || 0c
As for the penalty function V, we employ
()()) = ((If) - 1)+, (w)+ + (w)) + 2(1-7) 11
(34)
where > is hyperparameter, (0) = max (0, g} denotes the positive part of a function g (a)), RT,+(w) = i 1_ (w @ 3) and (w) == 1-7 (w @ 9) are the positive and the negative part of the empirical DBR, respectively, and || ||r is the RKHS norm. Then, letting C(P) =+ +
(w, P), P E Ml (X), the penalized objective (16) is simplified
Ł(f) = fff - 11, Rr (w)) + (If + 1/, (w)) + 2(1 7(-~) - -
(35)
which is convex with respect ʃ F. In other words, the minimizer
f= = argmin ((J)
(36)
fEr
can be found in tractable manner with convex optimization methods. As for choice of X, as will be seen in the next section, employ some fixed default À = /n or select the best hyperparameter within some fixed grid, egg., A, == 21,2.... 2 n!) }, that best attains the supremum (15), possibly using the training-validationn split technique.
achieve the consistency if Á - and n. - oc. Thus, may
D.2 CONSISTENCY ANALYSIS
We first introduce some notations useful for the analysis. Let us define probability measures P, Pr Ml 32 by
dP(ci, = de, d
a (1 24) = di (1n (23(22),
loss functions l,,oys 23 + R. F,
3 Cg(zi, F2, x3) = Σ (,,(
60 23) = Σ
j=1
j=1
for T2, T3 E X, where
(2,( = (1 (1-)))((x1) 1/,
(,11 = - [[
(2) = (222)]((22) + [l
(72 = (x22)
(,,(01)222 = 7/w(x2)((x)) - (x2)))
()a(z1)22 23) = (f
Let us also define the associated risk functions
Lx($:Q)= (y,, Q) 1
+(: = (p. Q),
15

---

Under review as a conference paper at ICLR 2023
for probability measures Q (2 By these definitions, have
P) 11--711 XIX],, Rx(w)), P();Pa) = =(1 - -XXI/,, Rx(w)),
and
C) - ((::)) ----)--000()))-00101100000-01010 C(B) Ex(F: = = DT P(f: + (1
(37)
(38)
for À > 0 and f E F, where 4 is given by
34 and
vx(f) = ((lf) - 1)+, Rx,+ (w) + Rx Rw)((w)) 2(1 - 7) f
(39)
= 4n Th + @ 3) and - (w) = 1 (w @ 3) are the positive and the negative
parts of the DBR, respectively.
Therefore, we obtain an alternative expression of the objective [6
Ł()) 1 1- P.) C(3),
1
which implies
fx argmin Lx(;; Pn). fEF
(40)
Moreover, by Lemma C.2
we also obtain alternative expressions of the quantity of interest
RR (w)]lv = I- FEF
inf P) FEr
(41)
1
C(3) y
inf Colf:P).
(42)
JEF
The goal of this section is to reveal the relationship of fa and (R)(wll via 40) 41 and 42
The following lemma gives key insight on the behavior of fx. G :=
w|lo be
the Lipschitz constant of f + Ey and H y. Let (0 1) = [ [l 1} be the unit closed ball of F. Let R. (H) is the Rademacher complexity of function class H. (XX) (see Definition H.4).
Lemma D.1. Suppose the predictor attaining minjer Cx(f:P) exists and denote it by ft E F. Also suppose |l I |Ifll for all f E F. Then. for all 8 E (0, 1), we have
SG2 Ex(sxP) < Lx(R2PP)
In(1/8)
R. (Bx(0,
2n
and
Ilfa 1ill> S 4G
In (118))
Hi (B,(0,
2n
with probability
Proof. Define
(((:)) - Lx(f3:Q)
25z - for j 1,2.3. Then, since e (J;P) > \ MB 2 fill3 by the strong convexity of
for f E F and Q E A(x). Let F. = (SEF e(f:P) < c} and let Ey.s = lfstos -
16

---

Under review as a conference paper at ICLR 2023
f L)( the uniform law of large number (Theorem H.5 gives
(e(f:P)-(JJ::) p((:P.)) fEF.
sup
sup Σ reF: j=1
(2)-133: P- Pn) Pm)
sup
(ogs P- Pn)
(: strong convexity)
llal = 20/2 j=1
3
2c
2c
ln(1/5)
22
Σ E9s 1loll> 1 $V A
+
+2G
Theorem H..
A
2n
8c X
1n(1/8)
$
Rn (Bx((11))
E(C,
( see below)
2n.
with probability 1 - 5 for all c > 0. Here, the last inequality follows from
(
2c
2c
Rn
|191|= S V
S Σ
Ri
faa=:llom 1191l1
(: subadditivity)
j=1
2c
$ Σ
G V
Rr, (0,,
(: Lemma
j=1
2c
$ /\ GRR (B=(0,)))
where Gj is the Lipschitz constants of f..z j 1,2,3. Now take Se E F such that fe S2 if cffx; P) S and, otherwise, c(fc Pw) $ and <fcc P) Then, when c > E(c, 6), we get with probability 1 8
<(fc: P) <(Foi +c)) Pn):
I sup falliiPse
- c(f: -(ff:)))((f:...). Pn):
(. P) sc)
<c,
which implies fc = fa and hence e(fx: P) < c with the same probability. Thus, since it holds with any such that e E(C, 8), we finally have
(fx:P)
with probability - 5, where et is the solution to c* = E(c",8), or more concretely
8G2
In(1/5)
=
Rr (B,((()))) +
2n
This concludes the proof.
Now, verifying the assumptions of Lemma D.I and evaluating the Rademacher complexity of the unit ball R, (0, 1)), we get the following proposition.
Proposition D.2 (Generalization error bound of RERM with RKHS). For all 5 E (0,1) and X > 0, we have
8G 8GPIn(e2/8)
Lo(fx < inf C)(f:P)+
JEH
An
'Such fc exists the intersection of the line segment ff and the level set (FEF elf: P) < since f + e(f Q) is convex.
17

---

Under review as a conference paper at ICLR 2023
and
4G
In(e2/0)
II - Rl S
(43)
2n
with probability 8.
Proof. It suffices to invoke Lemma D.I with Lemma H.6 To this end, we need to verify the exis- tence of min (x P) and the dominance of the norm || Ilae Il llxe- In fact, the minimum exists since - Lx P) is continuous with respect to L22 and the inifimum inf Lx(J; P) does not change if restrict the domain the ball {f E H || S (0; P)}. which is compact according to Lemma H.7 The dominance of the norm is shown by, for all f E H.
lIfl sup If(x)
=Ex
sup [<((,x), fiHl
=ex
< sup ||<[[; () [1x))+/[(11]
=ex
sup x(x,x)) flll
aEx $ llf
We need one more lemma to connect & (fx; Pa) with (ffx; P).
Lemma D.3. For all 8 E (0, 1), we have, in addition to the statements of Proposition D.2
8G
In(e218)
In(2/8)
(fA; P.) - ({2: S
+ 2G
An
2
2n
with probability 1 25.
Proof. It follows from the uniform law large number (Theorem H.5 with the high probability range of fa given by 43 Let G = {4r f FF llf fill= S d}, where d =
4G In(e2//0 /6)
V
2n
Now, applying Theorem H.5 with -8/2, F +G and 2G, we get
In(2/8)
sup 115 115
(pp. Pr p\| < 22R, (9)
2 +G
2n
with probability 1- 5. Since 11fa--f2l fills S with probability 1- 6, we further get by union bound
In(2/8)
(ppA Pn P) s (9 - + G
2n
with probability 1 - 28. Since ()fx:Q) = (9/4 @) for all Q A (xx3) the proof is concluded by
(g) = RM f SEF,IF 18 S <d))
Σ Rn(ters F fill= s <d))
s GanR (B)(0,1))
Gd
Vn
18

---

Under review as a conference paper at ICLR 2023
Finally, ready to prove Theorem 7.3
Observe
- (1 (1-1)
1 -
pffx
Rr (wo)lITV
1-7 (((1))))-
inf jEF
41
Due to Proposition D.2 and Lemma D.3 we have the following inequalities bounding both terms of RHS with probability 26: The first term bounded by
+ (fx:)) - inf feF
$(F: P)
< Co(fx:P) inf P) jef
37 with L o
0,
42
8G 1G9In(e200)
$ inf Cx(f:P)
inf Co
Proposition D.2)
feF
JEF
An
+ A dd +
8G In(e//0))
S s((d
2
An
for all d > where s(d) I Colf:)) inf Colf: by
The second is bounded
-()x SG2 An
In(e2/8)
ln(2/6)
+ 2G
Lemma D.3
2
2n
Combining these two inequalities, we get
(1 71-
1-7 (ffx: (Rx
S s(d) + Ad
SG²
In(e? In(e2/5)
ln(2/8)
+ 2 An
In(c"/8) V
+ 2G
2
2n
with probability 28. Now, since lima- (d) 0, taking d 11133 we have just shown the following proposition, which directly translates into Theorem 7.3 Proposition D.4. We have
--7 ((fx; P.) - (R)
probability as O and nW + 00.
E DUAL REPRESENTATION OF CONVOLUTION NORM (PROOF OF PROPOSITION 7.4)
We first show the following utility lemma.
Lemma E.1. Let llfIlA and I| be arbitrary norms of f E B(X). Also let [lf llfllA [ be the norm defined by the maximum of these. Then, for all P E M (X). we have
PPlKAvB)> S inf QEP
PII--Qlay + 1Q]1m.),
where we denote the dual norm of || I|x on ((x) by |||x = supjestww P) P Al (X). Moreover, if (supp(P)] is finite and
l| and || || dominate
||. -lloos then the equality is attained.
19

---

Under review as a conference paper at ICLR 2023
Proof. Observe
||Plaay
sup
(f, P)
(E))()) II IfllasI
sup
inf {ff, Pt + (g - Q} QEP
(:: Q as Lagrange multiplier)
(.E
|
sup
inf P Q)
(
QEP
[1 11
I inf
sup
(f. P Q) + sup (g. Q)
Q&P
(E
(E
inf
{II Qlla + 1
QEP
which proves the inequality.
Now suppose d == PP) is finite and II and || ||B dominate || Il.o- Label each element of supp(P) by {z,)ş=1- Then, following the same equality as above, we get
d Σ 1=1
- + Σ E00((s)) 5=1
PPlkvvB]
sup inf aEBa QEP bEBn
where
BA = (((+,)))- fe (()) 1 1 c Rd
B3 = {(((z))) ge (()), lllll 11)CR
The domination of A- and B-norms BA, Ba C cla where Ua == {2 E IR maxi |æyl < 1 denotes the unit hypercube of IRd. Since clda compact and Ba and Bn are closed subsets thereof, they are also compact. Thus, Sion's minimax theorem yields
the uniform norm implies there exists 0o such that
|| Plkvvay
sup inf aeB QEP bEB
( + Σ by Q(xj)
inf QEP
sup ((r;) - Q(x;)))++))))}}}}))))) + sup bEB j=1
b,(((z))
aEB
inf QEP
{II Ql1 [|Q|
This concludes the proof.
For P E A (XX), define
F.(P)= = sup (S, P)-
(
[1
Su
The following lemma shows that (P) is equal to the u-convolution norm. In other words, it gives the dual representation of the u-convolution norm in Proposition 7.4 Lemma E.2. For all P E M (X),, we have
||||, F.(P).
where PPll, w. is given with respect Definition 7.1
20

---

Under review as a conference paper at ICLR 2023
Proof. Without loss of generality, assume || 1. Let Pn be the empirical distribution of P given by Definition H.3
Let H. be the RKHS associated with the kernel Let lIfllA Ilffl and llf
llf
in
Lemma E.1 and observe that, for all P E (x)),
(.(P) = ||Pl(cvBB)' ||| u,, = inf {Ip Qlla + 1QQ1BB).
QEP
since |l (P) and || = P| Then, we have
|| Fu(P) S EF,
since
(P( S |||
Lemma E.1
S B|| Pallacs
( Jensen's ineq with Lemma H.3
= (Fx)
( Lemma E. with supp Px)) < oc)
S EF,,,, P).
triangle inequality of F.)())
The proof is concluded remembering that
S EF, - P) (1 E ((X) 1/ S uullollo S 11) 1 29 (15 E ((x)
Theorem H.5
: [lll st)
suprex x(x,
S 2
(:: Lemmal H.6
n
as n 0o, where Ri (F) is the maximal Rademacher complexity (Definition H.4
F PROOF OF COROLLARY 7.5
Let w w/|lwllo be the normalization of w. By Lemma E.2 we have
|| @ (8 ll
(wf, 3 B)
sup
FE
11
(w 3 B) (: (111fflll = 11511H, |w]l S l1
sup fE(
|| (l//llm.. Su [ffl 11
sup (x))
(g, 3-13)
(x)) c (())
Ne Su gll 51
|| Allu,N..
where Hip is the RKHS associated with := (()))(())) v). Similarly, we have
| 3 - @ (0008)13 3)
(f. [~ 2 T (w R))
sup FE))(X))
Su
S1
(w 60 J, 3(2) 8(2))
sup fESP(X)
(],8(2) - (3(2) 11
21

---

combined with the compactness of W and the continuity of Under review as a conference paper at ICLR 2023
where Br ,3 ((22) are given by d (I, = d8(x)d7x(x'(p) and d (2, (") (3(x)dT, (a/lz), and 2 ((x, (v, = (())(())c((' vf). Therefore, we have
(R) | ?
1 (R)(())luu))
(w 2 - (w o B)llmx + 1 1-7 Iw o (8 1)
$ 1 l balla, + 1-
< 7 l aalu,x + 71/2| x0 11
( + | 00 113 - Bllaak..
Since K, Ke and Ki are all bounded, now implies
100
u12 In(1/0)
|| (w)
R (1)))lm |unx =0
1-7
Combining this with (18 and take the limit with Do and n/u² _ oc, get the desired result.
G PROOF OF THEOREM 7.6
Note that Theorem 7.3 combined with the compactness of W and the continuity of w + (w))(l)l implies that Eval uar uat eDaatDDDBDDD w) converges to (w)](e uniformly on W. Thus, it suffice to show the following lemma.
Lemma G.1. We have
min (10)) > min wEll
wEW |i
Proof. Note also that Corollary + Rr (w) Il implies
7.5
(w) - (w)
uniformly for all E: W, under suitable asymptotics of and in Corollary 7.5 In other words, for all c and (0, there exists ug 2 1 and po > such that, for all u 2 do and n 2 pou2 such that supwew (w))lm. [| (w]]|vVl < e with probability 2 1 - 5. Therefore, taking such pair (u,n) n) satisfying u E U (which exists by the definition of (4), we have
min R (w)llTV S min Rr (wow) ll wEW
(:: restriction of domain)
w'Elf
S + | ( ((.))ll.x
S c + R (w,) Ilu.,
(:: definition of i..)
< 2c + R| (w,) ||TV
2c + min R (w)llTV
weW
with probability 2
5. Since 0 be arbitrary small, have just proved the desired
result.
H BASIC DEFINITIONS AND RESULTS
This section presents basic results used in the proof of our results for completeness. The main purpose of this section is to show Proposition D.2
H.1 SIGNED MEASURES
We first introduce the absolute value and the positive and negative parts of a signed measure. Recall that E is the Borel algebra of X.
22

---

Under review as a conference paper at ICLR 2023
Definition H.1 (Absolute value and positive and negative parts of signed measure). For all P M (2),, its absolute value is given by |P| E (X)) such that
P((E)=
sup E+
(P(E4)-P(B-))
Moreover, its positive and negative parts given by P1 = (IP) = P)/2 Ml
The following properties are then immediately seen. We omit the proof since it is trivial from the definitions.
Lemma H.1. The following statements are true.
1. Pt are nonnegative measures.
2. P P+ P_ and |P| P+ P_.
3. P,P+ IP|
4. ||||||Tv = |P+ || + +||--I/TV= |||||]
Next, the sign function of signed measure is defined with the absolute value.
Definition H.2 (Sign of signed measure). For all P E (X), its sign is given by sign P := dP ((X).
d|pl Lemma H.2. We have (sign (1)) S for [P] -almost every X.
We note that the essential range the sign function is bounded to [-1, 1].
Proof. It follows from
dP
dP-
dP_ P
dP
dP_
P
<
=1 1. P
(IP)-almost everywhere)
P
P
Finally, we define the empirical distribution for signed measures.
Definition H.3 (Empirical distribution of signed measure). For all E (A) such that || P|||Tv = define its n-th empirical distribution by
P
Σ (sign (x.)),.. 1=1
where {ri)E is n-i.i.d. sample drawn independently from [P], which is probability distribution.
Note that coincides with the empirical distribution of probability measures if P is nonnegative. One of its most basic properties is the unbiasedness.
Lemma H.3 (Unbiasedness). For all P A.l (Xx) such that ||]|
have P(E)=EAP) = (E)A(E)
for all E F.
Proof. It follows from that, for all E E,
(P) 1 Esign () E E]]
= (sign P o (E)
(::2, ~ [P))
P(E).
(: sign P P
23

---

Under review as a conference paper at ICLR 2023
H.2 RADEMACHER COMPLEXITY AND UNIFORM LAW OF LARGE NUMBER
The Rademacher complexity is measure of the complexity of function class. It is mainly utilized establish the concentration of the empirical processes corresponding the function classes, i.e. the uniform law of large number. Throughout the section, let o" = {= be a sequence of Rademacher random variables, each of which takes #1 with probability 1/2 independently.
Definition H.4 (Rademacher complexity). For a subset of n-dimensional vectors θ C R", the
Rademacher complexity ② is defined by
R(O) = Egg
sup 0,0
0E6
Moreover, for S E X and C B (X), the empirical Rademacher complexity of with respect to S is defined by
RF R(F(S)/n).
e RR = {ai) f F denotes the set of vectors ob- tained by applying f F on each element of S. Also, we define the n-th maximal Rademacher complexity of F by
where F(S) ==
RR, = sup Rs(F). SEx*
The following lemma is useful to bound the Rademacher complexity of the composition of functions. Lemma H.4 (Rademacher contraction lemma). For all θ E IR and family of 1-Lipschitz confin- uous functions (+p:)== sPs : - RR, we have
()) S R()),
where (p()) = {(p)) (01). ((.b)) E ER 0
Proof. Observe that
72
R({(O)) = FEgg sup (0,)
1=1
n-1
(0)) - =Pa((h) }1
Σ (0,) + (m(( + sup o'ee
sup
2
0Ee
Since the expression inside the expectation is bounded by
sup
(0,) + (On) + sup 0'
(1)) sn (0%)
(..)) + ((())) + (0p)(0n) pa (8a)3
sup 8.
a.(ip.(0.) + (;))))) + 10n -0'
sup
0,0' ee
sup
(.((p.(0))) + (()))} + On - 6%
(:: Symmetry of and 0')
n-1
sup dee
axpp; (0.) + On On
+ sup 0'ee
Σ (1))((0)) - -0n
have
R-1
(1)) 0, }
R(p(O))
< - E Egn-1
sup 8c0
(.p)((0,) + On
sup 6'
-())
where 0 = (PI,..., 1pnn.nnn111 I) and is the identity map. Iterating the same argument to swap P with for all 1,..., get the desired result.
24

---

Under review as a conference paper at ICLR 2023
The following theorem gives sufficient condition for the concentration of the empirical process f - (J, P. P). F, with respect the Rademacher complexity (F). Theorem H.5 (Uniform law of large number). For all probability measures P E Al (x) and all F C (X)). we have
sup(,, Pn P) S (F). FEF
Furthermore, we have
In(1/6)
su P) < (F) + DV fer
2n
with probability 1 1-66 where D SuP (()) f(v) Here, Pa is the empirical distri- bution of P given by Definition H.3
Proof. Let {ar] and {oi) are two n-ii.d. sample drawn independently from result follows from
The first
E sup Pa P) sup E fet
Σ ((x))
{
Lemma H.3
fet
1
Σ ((xz))
< E
sup SEF TI
1
sup SEF n
-(f(())
(:r symmetry of x; and z/)
n Σ (wx))
< 2E
sup feF
< 29R (F).
To show the second result, define
A(S) = sup feF n i=1
Σ (1x)
(S, P)
for S = (x.)== E X" and observe A(S) follows the same law as
sup
(f. Pr P\.
feF
Thus, suffices to establish
In(1/8)
A(S) - (E((S) S DV
2n
with probability 1 - 8, which follows from McDiarmid's 's inequality (Boucheron et al. 2003) applied on A(S). Here, the assumption of McDiarmid's inequality we need to verify that (())-(S)))) A(S))) S D/n for all S' = {x]]] n that only differs from S at the j-th element, 1 S j S m. This is verified by
A(S") sup
f(x)) (f, p)
JEF
n
f(x:) - (f, P) + - s(xi1)
sup feF
n
< A(S)
sup (f(a)) f(x,))
ni fEr
D
A n
This concludes the proof.
25

---

Under review as a conference paper at ICLR 2023
H.3 REPRODUCING KERNEL HILBERT SPACE
Throughout this section, we assume H. is the reproducing kernel Hilbert space generated with continuous, symmetric, positive-definite kernel K X R. Also let || and (s 1) be the associated norm and inner product, and let (x(0,1) = {f H. llfllx S 1 be the closed unit ball of H. The following lemma shows the Rademacher complexity of RKHS can be explicitly bounded. Note that un-unrrersal kernel is uniformly bounded and hence |||||> co.
Lemma H.6 (Rademacher complexity of RKHS). We have
Ri, (0 1)) -
n
Proof. It follows from that, for all S E x
Rg(BBH(0,1) = E...
sup (0.1) n
fff(
= E
sup
xz); f)u
(0.1( im1
Eg
0,K(;,D3)
n 1=1
7
2
n2
Paga
Jensen's ineq.)
71
i=1
#
xi),,
1
Σ
1=1
7=1
(n((, x((,I:))
x(Z,, 2.))
sup=ex ((x, x)
The following lemma shows the compactness of the closed RKHS balls the T.2-metrics.
Lemma H.7 (Compactness of RKHS). (x 1) is compact with respect to L?(() for all positive measures P A (X).
Proof. Mercer's theorem gives eigen decomposition of k such that
<(x, y) Σ AR (z)(x()))))
where the convergence is uniform on X², {oh X B] is a continuous orthonormal basis of LP(P) and == {Ax R is nonnegative decreasing sequence with lim A 0. It then follows from the standard function analysis that BH,1 under the (? is isomet- ric to U(A) = (a (ax) Exzoa # a A & 1} under the e via the mapping as(s) = (x) Here, evaluate 0/0 so. Therefore, the compactness of Bx,1 in (P) follows from the compactness of U(A in L To show the compactness of the latter,
26

---

Under review as a conference paper at ICLR 2023
suffices to show its completeness and total boundedness. The completeness is trivial, while the total boundedness follows from the fact that the elements of ((A) approximated with their projections onto the first K coordinates where the approximation error is bounded by AK+1, which tends to zero as + co.
27


Reviews:
[{"review_id": "pKX5rT4xVKx", "reviewer": "Reviewer_GGmU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes the problem of minimax bias estimation of the value of a policy using offline data. The algorithm is based on marginal-importance-sampling and minimizing the Bellman residual error.", "summary_of_the_review": "I think this is a good paper overall. But I am not very confident in my review since I did not check all the details.", "strength_and_weaknesses": "Strength:\n\n1) The problem of estimating the confidence interval of the value of a policy using offline data is very important. Since it is known that when the offline data is not exploratory enough, it is hard to get accurate point estimation, it's important to get good interval estimation.\n2) The theoretical analysis of this paper seems to be sound, although I did not check the details.\n\nWeakness:\n1) I think the notation in this paper is a bit heavy and I found it a bit hard to understand all the details. I also think it would be good to move the actual algorithms to the main sections of the paper instead of putting them in the appendix.\n2) It would be good to have some empirical evaluation.\n\nThere are a few places that I don't fully understand:\nPage 8 Proof of Proposition 7.4: why does the Rademacher complexity of the unit ball in H of the order O(n^{-1/2})? I assume it should also depend on certain intrinsic dimension of the space H.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "m_8P-alj8bK", "reviewer": "Reviewer_HEuP", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies offline policy interval evaluation for discounted MDPs where the goal is to generate an interval that contains the ground truth with high probability. Specifically, this paper shows that, without the coverage and realizability, there exists a lower bound of the asymptotic bias. Then the paper proposes an interval estimation method that can output an asymptotically valid interval without the coverage and realizability assumptions. When the realizability assumption holds, the proposed interval is shown to be optimal. ", "summary_of_the_review": "My current recommendation is reject. \nThe paper indeed considers an important problem and a meaningful setting. But my major concern is that the contribution and significance of the paper is unclear.\n\nThe details are as follows:\nThere is a lack of comparison with closely related work.\nNot enough explanation of the results. It makes this paper hard to understand for readers who are not very familiar with this exact topic.\nNo empirical evidence to show the validity of the proposed algorithm. \nOverall, I think a significant amount of modification is needed.\n", "strength_and_weaknesses": "Strength:\nThe problem itself is very meaningful and interesting. The setting where the commonly assumed coverage and realizability fail is very practical and worth investigation.\nThe theoretical results are well-structured. The role of each section looks clear.\n\n---\nWeakness: \n1. This paper fails to discuss a series of works that are very related to this one. OPE is an extensively considered problem studied by a variety of authors. Almost every part of this paper has some very related works. To be specific,\n(i) It is already a well-known result that OPE incurs bias without the coverage assumption (e.g. [1]). [2] has conducted a bias as well as variance analysis for OPE of tabular MDPs years ago. The relation between the lower bound in this paper and hardness results from these papers should be discussed as they seem closely related to me. \n(ii) IS/MIS is a common technique for OPE, studied by, [3-5], to list a few. In particular, [3] gives the sharpest bound for tabular MDP under the coverage assumption. How does the bound compare to this paper?\n(iii) Interval estimation is great. However, for some papers with point estimation, the results can be transformed into high-probability intervals (see for e.g. [7, 8] which considered the linear function case). [10] also consider OPE like this paper. Although this paper focus on the setting without coverage assumption, it is still necessary to investigate that, If under the assumption of coverage and realizability, how do these results compare to the interval in this paper?\n\n2. There is no numerical simulation to justify the theory. It seems necessary to show exactly how this paper compares to other IS-based OPE methods for tabular setting with coverage assumption (e.g. [3]). \nMathematics is heavy, but there is not enough explanation of the implication behind the theory. For example, why do we need two variants of Bellman equation; in the tabular setting, if the final bound does not depend on the cardinality of the state-action space, then which term characterizes the complexity.\n\n\n---\n\n[1] Wang, Ruosong, et al. \"Instabilities of offline rl with pre-trained neural representation.\" International Conference on Machine Learning. PMLR, 2021.\n\n[2] Mannor, Shie, et al. \"Bias and variance in value function estimation.\" Proceedings of the twenty-first international conference on Machine learning. 2004.\n\n[3] Yin, Ming, and Yu-Xiang Wang. \"Asymptotically efficient off-policy evaluation for tabular reinforcement learning.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2020.\n\n[4] Li, Lihong, et al. \"Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms.\" Proceedings of the fourth ACM international conference on Web search and data mining. 2011.\n\n[5] Li, Lihong, Rémi Munos, and Csaba Szepesvári. \"Toward minimax off-policy value estimation.\" Artificial Intelligence and Statistics. PMLR, 2015.\n\n[6] Thomas, Philip, and Emma Brunskill. \"Data-efficient off-policy policy evaluation for reinforcement learning.\" International Conference on Machine Learning. PMLR, 2016.\n\n[7] Duan, Yaqi, Zeyu Jia, and Mengdi Wang. \"Minimax-optimal off-policy evaluation with linear function approximation.\" International Conference on Machine Learning. PMLR, 2020. \n\n[8] Min, Yifei, et al. \"Variance-aware off-policy evaluation with linear function approximation.\" Advances in neural information processing systems 34 (2021): 7598-7610.\n\n[10] Hao, Botao, et al. \"Bootstrapping Fitted Q-Evaluation for Off-Policy Inference.\" International Conference on Machine Learning. PMLR, 2021.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "TG2Iuz_DO_b", "reviewer": "Reviewer_QpFW", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies the problem of offline policy evaluation (OPE) in the reinforcement learning setting without assumption that the offline data is well-explored. For such a problem, this paper characterizes the minimax estimation bias caused by the data distribution having a limited support. Moreover, the TV-norm of the Bellman error of the visitation measure gives an upper and lower bound of the bias. Based on that, this paper proposes an estimation method for estimating the bias, which is proved to be consistent. ", "summary_of_the_review": "This paper proposes a notion that characterizes the insufficient coverage of offline data in OPE. It also proposes a method to estimate such a quantity, which leads to a procedure to estimate a confidence region of the expected rewards. ", "strength_and_weaknesses": "Strength: This paper studies a theoretical problem that is more realistic in the sense that it does not impose a coverage assumption over the dataset. The notion of minimax bias seems interesting.\n\nWeaknesses: I feel that this paper can be improved in the following aspects.\n\n1. It would be great to have a more in-depth exposition of the minimax bias. First, it would be better to have a rigorous definition in the “definition” environment. Second, explain why it appears. Third, give a concrete example (maybe on a toy problem like bandit) to explain it. \n\n2. The authors seem to assume that $w^\\sharp$ lies in a certain class such that the last term in (8) vanishes. The authors should state this matter clearly. \n\n3. Although the results seem interesting, I am afraid that the bound might not be useful. In particular, the TV-norm of $R_{\\pi}$ seems a very conservative upper bound because $1/ (1- \\gamma)$ is a huge number. That means, if $ R_{\\pi}$ is not small, the confidence region can be vacuous. \n\n4. The theoretical analysis seems not so well developed. First, the TV-norm is not the exact thing used in estimation – an approximation via convolution norm is employed. We only know such an approximation is accurate when $u$ is sufficiently large. But how large should we need? What is the error when $u$ and $n$ are both finite? Second, the error analysis is merely asymptotic. From standard concentration results, one should be able to develop a non-asymptotic theory. \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "BuidgWL1DEO", "reviewer": "Reviewer_Zijs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studied policy value interval estimation problem given offline data without sufficient coverage and without realizability assumptions. The authors showed that without coverage assumption there would be an ``irreducible bias'' and therefore, proposed a new problem setup called minimax-bias OPI, which targets at estimating (near-)optimal (shortest) interval covering the true value $J(\\pi)$ with a shift at most at the level of the minimax bias. After that, in Sec. 6, they suggested an objective function to compute a near-optimal interval, which is also robust to the misspecification error of function class. Finally, in Sec. 7, they proposed how to computably approximate the solution of the objective function and established asymptotic guarantees.", "summary_of_the_review": "This paper has many interesting results. Although there is still some limitation, I would suggest the acceptance of this paper.", "strength_and_weaknesses": "### Strength\n\nThe method and analysis in this paper is interesting and inspiring. The new problem setup minimax-bias OPI is well-motivated, and it's nice to see their methods does not require the common assumptions in previous literatures to ensure the validity.\n\n\n### Weakness\n\nThe final results in Sec. 7 is just an asymptotic guarantee and it is unclear about the convergence speed. Especially, it's unclear how well $||P||\\_u$ approximates $||P||\\_{TV}$ when $u$ is large but not infinite.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject