Asymptotically Exact Error Characterization of Offline Policy Evaluation with Misspecified Linear Models
Authors: Kohei Miyaguchi
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
offline policy evaluation
linear function approximation

Abstract: We consider the problem of offline policy evaluation~(OPE) with Markov decision processes~(MDPs), where the goal is to estimate the utility of given decision-making policies based on static datasets. Recently, theoretical understanding of OPE has been rapidly advanced under (approximate) realizability assumptions, i.e., where the environments of interest are well approximated with the given hypothetical models. On the other hand, the OPE under unrealizability has not been well understood as much as in the realizable setting despite its importance in real-world applications.
To address this issue, we study the behavior of a simple existing OPE method called the linear direct method~(DM) under the unrealizability. Consequently, we obtain an asymptotically exact characterization of the OPE error in a doubly robust form. Leveraging this result, we also establish the nonparametric consistency of the tile-coding estimators under quite mild assumptions.


Asymptotically Exact Error Characterization of Offline Policy Evaluation with Misspecified Linear Models
Kohei Miyaguchi IBM Research Tokyo miyaguchi 0ibm. com
Abstract
We consider the problem of offline policy evaluation (OPE) with Markov decision processes (MDPs), where the goal is to estimate the utility of given decision- making policies based on static datasets. Recently, theoretical understanding of OPE has been rapidly advanced under (approximate) realizability assumptions, i.e., where the environments of interest are well approximated with the given hypothetical models. On the other hand, the OPE under unrealizability has not been well understood as much as in the realizable setting despite its importance real-world applications. To address this issue, study the behavior of simple existing OPE method called the lincar direct method (DM) under the unrealizability. Consequently, we obtain asymptotically exact characterization of the OPE error in a doubly robust form. Leveraging this result, we also establish the nonparametric consistency of the tile-coding estimators under quite mild assumptions.
Introduction
We consider the problem of offline data-driven decision optimization, wherein static records of previous interactions between decision makers and the environmental system of interest are given. The possible application areas include autonomous driving vehicles, natural-language dialogue systems, recommender systems, financial portfolio optimization and healthcare treatment optimization.
The framework of offline reinforcement learning (RL) is of the promising approaches this task (Levine et al. 2020). In the standard RL, the environment and the decision-making policy are respectively modeled as Markov decision processes (MDPs) M and conditional distributions of actions (Sutton and Barto 2018), where each series of consecutive interactions between M and are abstracted stochastic sequence of state action a and reward called an episode. The objective of the offline RL is then formalized as the maximization of the policy value J/ (TT), the expected value of the total reward obtained from a single episode, given a static dataset of previous interactions.
The crucial part of the problem is that the dataset is static; No additional interaction with the environment is allowed. This constraint poses several unique challenges to the problem. First, the policies we are optimizing, i.e., the target policies, cannot be in the actual environment, Second, the policies used to generate the dataset, i.e., the behavior policies, are often unknown and may be totally different from the target policies. Consequently, it is even difficult accurately estimate the value of target policies. This is problematic especially in consideration of real-life applications involving financial costs and healthcare risks.
To address the issue of policy value estimation, the problem of offline policy evaluation (OPE) have been extensively studied in the literature. A class of OPE algorithms referred as the direct methods (DMs), in which some characteristics of M are assumed to be realizable under some
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table 1: Comparison of the consistency conditions of linear DM. 'Yes' in the Consistency column implies linear DM solves any OPE instances satisfying the corresponding conditions. The definitions of the terminologies (such as compatibility) and mathematical symbols are given in Section and
Realizability
Exploration
Additional cond.
Consistency
Duan et al. 2020)
Bellman operator
concentrability
yes
Uchara et al. 20200
Q and v/p
bounded v/μ
yes
Our result
Q" or v/u
concentrability
compatibility
yes
Amortila et al. 2020
Q
concentrability
no
hypothetical models and (x) is estimated via a direct estimation of such characteristics. For example, in the fitted Q-evaluation (FQE) algorithm (Le et al. 2019), the policy Q-function is assumed to be well-approximated with a parametric function class and the OPE is reduced the estimation of its parameters.
DMs are known to be empirically effective (Fu et al., 2021 if such realizability assumptions satisfied and, more importantly, the converse is also true (Voloshin et al., 2019). However, the theoretical understanding of DMs under unrealizability is still in its active development. For example, several authors have recently studied OPE or offline RL under relatively weak or approximate
realizability assumptions (Jin et al. 2020 Xie and Jiang 2020 Wang al. 2020) and consequently proposing new algorithms.
In this paper, we approach the problem of unrealizability in the opposite direction; we start with an existing OPE method, study its behavior under complete unrealizability and seek for the possibility of regaining its consistency (i.e., asymptotically achieving errors). More specifically, the properties of a simple DM with linear function approximation. which equivalent with a number of existing algorithms such as LSTDQ (Lagoudakis and Parr (003),, FQE (Le et al., 2019) with linear function regressors, the marginalized importance sampling estimator (Yin and Wang 2020)
investigate
and DualDICE (Nachum al. 2019) in tabular settings.
In particular, we first characterize the exact asymptotic error of linear DM under as weak assumptions as possible. It turns out the error is governed by an inner product of two approximation residuals R and Rx
J(T) &
+ +0(V/))
(informal)
where they are corresponding to the unrealizable components of the value function Q" and the marginal density ratio v/p, respectively. To the best of our knowledge, this is the first to show linear DM is doubly robust against model misspecification, i.c., consistent if either RB = 0 or R2 0 hold (Table D. Leveraging the above result, we also show that a linear DM with the tile-coding function approximation (Section ..3.2,Sutttn and Barto (2018) is consistent under surprisingly mild conditions with appropriate tile-size scheduling.
The rest of the paper is organized as follows. In Section we formalize the problem setting as well the definition of the linear direct estimators. In Section 3 we present the main results, i.e., the asymptotic error analysis of the linear direct estimators and a construction of consistent nonparametric estimators as its application. Finally, in Section we present concluding remarks, limitations and future directions. All the proofs of the propositions and the theorem are relegated the appendix. See Section | for the proofs of the propositions. For the theorem, we present proof sketch and the pointer to the full proof.
Section 4 we discuss related works with comparison our results.
2 Preliminary
In Section 2.1 some notational conventions are introduced. The problem of OPE is then formalized
in Section 2.2 Then, Section 2.3 2.4 and 2.5 respectively introduce assumptions and definitions on
the data-collecting processes, the environmental models and the class of estimators we will examine.

---

2.1 Basic Notation
We implicitly assume the spaces we encounter in this paper, such as the state space and the action space A, are equipped with respective metrics and base measures, each of which is compact subset of either a Euclidean space with the Lebesgue measure, a discrete space with the counting measure or a product of those. We denote by Jx (x) dæ the integration of function ʃ with respect to the base measure of X. The subseript X' may omitted it is obvious from the context. This way we can immediately generalize our results to both continuous and discrete spaces. Also, we denote the expectation of function f with respect probability density p by (f), = Ex-p[f(x)]-
Let [m] := {1. ............ m) denote the set of integers from m. Let Il-llp denote the ("-norm for vectors and ||A|| p-2q = sup, 250 |Ax) / ||= the operator norms for matrices, with the convention ||4||, == p- p-pp> for all $ p.q S 0c.
2.2
Problem Setup
The goal of OPE is to estimate the value of decision- strategy based static dataset of interactions with the environment of interest, without directly knowing its mechanism.
The environment is modeled as Markov decision process (MDP) M (S, A. po,pr, pr), where the state space, A the action space, Po(s) the initial state probability, pr(''|s, a) the transition probability and p- pr(sss, a) the [0, 1J-valued reward probability density function for s, E S, a A, r E [0. 1]. Here we assume pr and p. are unknown. On the other hand, the decision-making strategy modeled policy, state-conditional action distribution π (als)) for s S. a E A.
The value of is measured with the expected cumulative reward
J(T)
= Σ
(1)
Pd
h= 0
where 7 E 10. the discounting factor, P is the state transtrannition operator such that (P)) a) f(s', (s') (s, (d'ls'))) da', F(s,a) = I (r-(rlss fs.s a) dr is the expected reward function, and pā (s, a) == (a)) is the initial state-action distribution. In particular, (Phr)yg denotes the expected reward after h transitions starting from pō-
The policy value J(T) is estimated based on a collection of transition records 5" = (E1...., E DD called an offline dataset, where D = S x A x [0, 1] S the space of transition records and & (st, a; Tú, s{{) E D. i E [n]. is a transition record made of a preceding state-action pair (s;, a.), the associated reward r., and the state after transition s'c The dataset 5" assumed to be instantiation of the random variables =" = (Ei..... 3. E. = (S,, A,, Rs, S)), collected with interactions between the environment M and query distribution Pquery = (Pquery(i) (s. (" such that its distribution is given in conditional fashion.
P(E, 5 ) = Pquery(i) (si, a.lg"= p. (rals;, a;) (s(5/1s,, az), i E [n]]
Note that the notion of query distribution is so flexible that it admits {" to be a union of episodes generated with multiple nonstationary policies and even adversaries the choice of state-action pairs.
Definition 1 (OPE problem). An instance of the offline policy evaluation problem is specified with POPE. = (M,T,7; 7 Pquery), where the goal is estimate the policy value J(x) determined by (,, given the inpul data 8d generated with (M, Pquery), ) without knowing any of pT, Pr or Pquery-
2.3 Assumptions on Data-Collecting Process
To ensure the existence of reasonable estimators for POPE, we pose a condition on the mixing of data-collecting process, i.e., conditions Pquery- We assume the amounts of mutual dependencies induced by Pquery between time-distam transition records are bounded.
Assumption 1 (G*-mixing dataset). There exists constant G oo such that 3 is '8 ssr-strong mixing with the coefficient (h) satisfying 1 + 2 Ei Vg(h) < G
'The symbol "6" in the -trong mixing has its root in statistics and completely unrelated to the feature mapping. We denote the mixing coefficient by g(h) to avoid confusion with the feature mappings.
3

---

See Definition 17 (in the appendix) for the definition of the "6' "t'-sorong mixing coefficients. Typical examples satistying Assumption Iinclude datasets consisting of multiple short episodes and mixing Markov chains induced by stationary behavior policies.
Proposition 1. The following statements are true.
1. Assume E" consists of multiple independently collected episodes with length bounded by H, ordered in consecutive manner. Then have G S 2H 1.
2. Let Pquery(s) (s, ior policy Tb (b(aa)) and assume the resulting Markov chain has a finite mixing time mix <, 00. Then we have G S +1+77 7m
04-))-1,0-11mm (als), 1 S S n. for some stationary behav-
Note that the definition of G* G*-mixing is designed to be more general than these examples. In particular, it is more suitable for query-distribution framework, which admits adversaries behind the choice of (st; 0-)-s or dynamically changing behavior policies.
Under Assumption 1 most properties of Pquery is characterized with the marginal data density.
Definition 2 (Marginal data density). Let p(s, a) be the marginal data density, given by uls, a) = E (lpquery()) (s, f 8 E S and A.
The marginal data density lr quantifies the expected frequency visitation at each point (s, a) E SxA made by the querying process. Thus, roughly speaking, s((s,) a) indicates that how likely the point (s, a) will be sampled =
2.4 (Possibly Misspecified) Environmental Model: Linear MDPs
We introduce linear MDPs, a simple class of the environmental models denoted by Ha F We also define the projection of M onto Ho as we are concerned with the unrealizable case, M Ha-
linear MDP Ha formally defined via bounded vector-valued function on the state-action space called a feature mapping, denoted by o: S A RK K 2 1. We assume the boundedness and the concentrability of the mapping as follows.
Assumption (Boundedness). SupsES, (lo((, al) < 1.
Assumption 3 (Concentrabilityy. Let = (ØØT) nm be the feature covariance matrix and c, = XE) be its smallest eigenvalue. Then, > 0.
Note that the concentrability is standard assumption ensuring all the dimensions of the feature space will be explored in the data-collecting process. A typical example satisfying the above assumptions the tabular features.
Remark 1. & is said to be tabular there exits a K K-partition of S x A. {Pa]kE[K) such that
a = I((, E Pk}, & [K], s E S, a A
where II } denotes the indicator function. The tabular features always satisfy Assumption More- over, it satisfies Assumption 3 if every cell is covered with the data marginal, minke[K] Pp 0, where p denotes the probability measure induced by μ.
Now, the class of d-linear MDPs defined as follows.
Definition 3 (ø-linear MDPs), We say M d-linear with respect to π F FERK x such that
F if there exist b E RK and
F(s,a) = bT ((s,a),
(Po)(s,a) = F)(s.a)
for almost every E S and a e A. We refer to the set of all the o-linear MDPs as Ho.
We assume Hy contains the true environmental model. is rather used to facilitate the construction of OPE estimators Section 2.5
'The o- o-linearity is the property of the MDP M and the policy æ since the transition operator P' depends on However, omit the dependency on nt for brevity.

---

In other words, M is o-linear if both the reward distribution and the transition dynamics are linearly predictable in expectation with respect to @. This definition is motivated by the following proposition; if M is realizable member of Hp. the problem of OPE is reduced to the estimation of b and F.
Proposition 2. Under Assumplion
and 3
iM E Ha. we have
J(x) = 6"( (1 -FF -FF) Io.
(3)
where zo = f (b88 a) Pe (s, a) ds da.
However, it impractical assume know the mapping that attains the realizability with the environment of interest M. Thus we introduce the projection of M onto H..
Definition 4 (Projection of MDP), Let (b, F) be the parameter discrepancy of the --linearity, given by
(², F) = ((,,))y
BB [F(s,a) - bJ a() + ((P))(().)) - F))
(4)
We refer to its minimizer as the projections of M onto H&s denoted by FF).
Note that the projection coincides with the true parameter (b, F) if M is realizable. Throughout the paper, however, we consider the general case in which the true parameter may not exist, but (b², FF) always does.
2.5 Linear Direct Estimators
We finally introduce the linear direct estimator. The idea of the linear direct estimator is twofold. First, we approximately solve the minimization of 4 based on the sample {" to obtain the estimate of the projection, (b, F) z (bi, F²). Then, we plug the estimate into (3) to get a policy value estimate, which seems reasonable if . is (approximately) realizable.
More precisely, the first step is formalized via the least squares method.
Definition 5 (Empirical projection of MDP). The empirical projection (6, F.) is defined the minimizer of the following cost function
Fib.F:E =
- o(s + (n)(s)) - Fo(s;, (o(().a))) a.)
Here, ==( f ((s a) a)) (a]s) da is the state-marginal feature mapping.
This definition is justified follows. Proposition 3. For all E R and E RRKK V E|C(b, F: F:E)] D, (2, F).
In other words, the gradient of the cost function coincides with that of the parameter discrepancy function in expectation and thus one expect (6, F) (6F, FFF in the large sample limit.
We have closed form of the empirical projection. Proposition Let (4) n,, be given by
= [Ø(s1, a1), ((5n, Tn
V vz ==
A= [n]]
Then, the empirical projection is given by
i
F ΦË+
(5)
n
where E = 1 the empirical covariance matrix and + its pseudo-inverse
'If the sample size n is small, the minimizer may not be unique. In this case, we admit multiple empirical projections.
5

---

Algorithm Linear Direct OPE
Input: Initial distribution po. target policy data {", feature mapping ø
Output: Policy value estimate ((T
Compute the empirical projection (b, F) according to Proposition 4
2: Compute [TT = 6T6 (I - - z0, where Zg == ʃ 1 (s)po(s) ds.
Algorithm 2 Linear Fitted Q-Evaluation
Input: Initial distribution po. target policy и, data ç", feature mapping Φ, iteration number H
Output: Policy value estimate (
1: Let 0, = 0 I
2: for h 1, 1.., do
3:
Find 0,. the least-norm minimizer of 1 Ei=1 (ry +
- 0% (81 as)l
4: end for
5: Compute (T) Of where xo = (s ds.
The whole procedure is summarized in Algorithm 1 Note that (8) in Vr and xp is not nec- essarily tractable in closed form. One always resort Monte-Carlo estimates (s)() s 1 EE ((s, 0z), where a₂ T [T]]s). l [n.]] are i..d. samples. Proposition 3 still holds under Ry t==1
this approximation. Also note that (T)) is undefined if -I7-- 7f singular. To avoid the undefined behavior and the numerical instability due to near-singularity, we assume is compatible with PoPE in the following sense.
Assumption 4 (Compatibility). F = (1 >F- exists.
Note that the compatibility implies the well-definedness of J(z) with high probability for sufficiently large n since FF lim F. We also discuss the interpretation, sufficient conditions and statistical test of the compatibility in Section 3.1.1 and
Algorithm is equivalent to the LSTDQ (Lagoudakis and Parr 2003) algorithm and number of equivalence relationships to recent OPE estimators are drawn in Duan al. (2020). For the completeness, we show Algorithm| is equivalent to the limit of Fitted OvEaluattion (Le et al. 2019)
with linear function approximators, shown in Algorithm 2
Proposition 5. The output of Algorithm lim (T) if both exist.
((x) identical to the limit of that of Algorithm 2
3
Main Results
First, we give an asymptotic characterization of the error J(T) [r), which sheds light on the doubly robust nature of linear DM. Second, leveraging the first result, show novel consistency properties of a simple tile-coding estimator.
3.1 Asymptotic Error of Linear DM
As will be shown later, the dominant term of the OPE error is written inner product of two functions, namely the x-residual function and the Bellman residual function. To introduce these residual functions, begin with the definitions of the é-spanned function space, the d-semi norm and the marginal target density.
Definition 6 (o-spanned function space). Ø1, .... ØR. i..., F& ((0T σ) : S A + E RR}
denote by Fo the normed function space spanned by
Definition 7 (ø-semi norm). For any real-valued functions functionn over the state-action space f :SSA R. the s-semi norm of f is given by 1f1 == (of),, l|2.
Definition 8 (Marginal target density). Let v(s, a) be the marginal target density, given by v(s, = (L - 7) E n (Pth (s, a), where pt is the adjoint operator of P.

---

Note that (Pth (s, (s,a a) denotes the state-action density after h transitions starting from Pu- Thus, can be thought of the relative frequency of the state-action visitations the target episode with horizon-dependent multiplicative weights n/.
Then, two residual functions are defined follows.
Definition (x-residual function). The x-residual function is defined as
Rx v(s,a) (s,a,,
(}s,a)
where wa the minimizer of Lx(w) = ([ - --)))/ in Fs.
Definition 10 (Bellman residual function). The Bellman residual function is defined as a)) = (BQ*) (+, 0) - Q (s,
where B: +++F++++PP is the Bellman operator and QF is the minimizer of LB(Q) (BB(Q)===BQQ00 2 in Fg.
Note that these functions are 'residual" since they the remainders of the projection of some functions onto Fg. R2 is the residual the density ratio w/ and RB is the residual of the Bellman equation. Also note that the projection of the Bellman equation is coarse-grained as Ifl = 0 does not necessarily imply f 0 (therefore it is semi-norm). We will discuss further interpretation of these residual functions in Section 3.1.I
Now we are ready to state our first result.
Theorem 6. Suppose Assumption 7 2 and hold. Then, we have the almost-sure convergence
J(x) J(x)
1-7 RR
(6)
in a Cr, convergence also uniform with respect to the choice of if sup, || 0o.
rate, uniformly with respect to the choice of po- Moreover, the
Proof. (Sketch.) It is directly derived from the non-asymptotic bound (Thcorem 13 in the appendix), whose proof strategy is to decompose the error by j[T) - J(r) = (J²( ( - ((x))( (J(m) (x)))), where (F((T) == (Q))pz is the projected policy value, and evaluate these terms separately. The limit (6) is obtained by evaluating the first term and the second term vanishes in rate of (L/vvn). In particular, the key step in the evaluation of the first term is the following series of identities.
(T( J(T) ... (RD), ( R
- RB ( (M-1)),
E
where the last identity is what allows us to fit arbitrary function in Fs away from v/p, which is made possible with Rg being in the orthogonal complement of Fg. The full proof is deferred to Section
3.1.1 Implications and Interpretations
Consistency under Q-function realizability (and necessity of the compatibility). Theorem shows the necessary and sufficient condition for the consistency of compatible linear DM. Specifically, J(x) is consistent if either RB = or R₂ = The first condition R 0 can be interpreted as the so-called f-function realizability.
Proposition 7. Let Q²= Σnzo 7"t (P")) be the policy Q-function. Then, under Assumption and we have R if and only if Q" F
This is interesting since RB preserves the full information of Q=, the unique solution to the Bellman equation, even though it is the result of the coarse searse-grained projection (Definition TOp. Moreover, compared with the existing results on the hardness of OPE under realizability (Wang et al.) 2020) Amortila et al., 2020). Proposition] 7 |suggests the compatibility is the key for the consistency of linear aarriuullr,,mmotiilaaa DM. particular, Amortila et al. (2020) showed there exists class of hard instances where consistent
OPE is impossible if we just assume the Q-function realizability and the concentrability. On the other hand, Theorem and Proposition show we can eliminate such instances if we additionally assume the compatibility (Table
7

---

Consistency under density-ratio realizability. Theorem 6 immlies another route to achieve the consistency, namely R 0. By definition, is trivial that Rx = 0 equivalent to v/p E FØ. Proposition 8. Under Assumption
2 and we have Rx if and only if V/P/ Fe.
It suggests we have consistent estimate of ((T) when the density ratio v/p is realizable even if the true value function Q" is not at all realizable. This is interesting since linear DM is equivalent to linear FQE, which is designed to estimate value function Q" In another words, linear FQE is doubly robust in bias without estimating the density ratio. See Section 4 for further comparison with previous double robustness results. Moreover, the density-ratio realizability behaves better than the Q-function realizability. In particular, we have non-decreasing sequence of linear function
classes (Fam) (0)) C. F a(2)) C... }. the corresponding sequence of x-residuals {R\), Re
is also
non-increasing, i.e., ||(R(²] [|2=(w) is the non-increasing function of m 2 1. This does not hold in general with the Bellman residual R.B because the projection metric depends on Φb.
Convergence without concentrability. A convergence result similar to Theorem 6 can be estab- lished without the concentrability condition (Assumption B). i.e., even if the covariance matrix Σ is singular. this case, the projections 67, F², wt and Q* modified the least-norm minimizers and the rate of convergence depends on the minimum nonzero cigenvalue of E. See Definition 13 and Theorem 13 in the appendix for the detailed statement.
Linear DM is L (((()-mmnimmzztionn As illustrated in the sketch, the proof of Theorem 6 gives the large sample limit of ((x), namely ((z) - J²(x) (Q*) Therefore, since Q* is a mini- mizer of (Q) (Definition TO), linear DM is asymptotically equivalent solving mingeF, LQ(Q). This observation is closely related to the kernel-loss interpretation of the temporal difference meth- ods (Corollary 3.5 in Feng al. (2019)).
3.1.2 Sufficient Conditions for Compatibility and Uniform Boundedness of F?
In practical sense, the compatibility is necessary (not just sufficient) condition for the asymptotic convergence of linear DM: I y is singular, the smallest singular value of I -- approaches to zero and hence its inverse (T - -) the estimate (()). This is seen from the concentration lim F F (see Proposition 19 in the appendix) and the continuity of singular values.
P) 1 is divergent and unstable (if not nonexistent) as well as
However, difficult to completely characterize when F exists is uniformly bounded. Below, we show a sufficient condition for the uniform boundedness which depends only μ and Σ.
Proposition 9. Under Assumption
and 3 we have sup, |1 < oo if
1. There exists uy E RRK such that vo o(..)) 1, and
2. d0s (54,a)=-1d ((8, a') 2 0 for all (s, (8', E S A
Note that both assumptions hold with the tabular features ái i.e., tabular features always compati- ble. In general, the first condition can be satisfied by expanding 6 with an extra 'bias' dimension whose value is always one. On the other hand, the second condition is dependent 6 and Σ in nontrivial manner.
Even if it is difficult to analytically guarantee the compatibility and the uniform boundedness, is possible to statistically test/bound them by computing a high-probabillie upper bound on |[F 2a (cf. Proposition 19 and in the appendix). Moreover, combining it with the non-asymptotic bound (Theorem [3] in the appendix), one can obtain a data-dependent concentration bound. the resulting concentration rate is not acceptable, then may change or fall back on tabular features.
3.2 Consistency of Tile-Coding Estimators under Unrealizability
As is seen from Theorem 6 not surprisingly, linear estimator with fixed á is not consistent in general under unrealizabilitt. This motivates us investigate alternative methods that adaptively selects feature mappings. Such estimation method is formally defined as follows.

---

Definition 11 (Nonparametric estimator). We refer to (Φ, m) as a nonparametric estimator if Φ = ( m== is a sequence of feature mappings such that ol"²) ; S x A - RRK",, Km 2 L, and m N N a model-selecting function such that lim mh(n) = co. The output of the estimator given as (T: Φ m.) == [m: ( (f(()))), where [x:; 6) denotes the linear direct estimate given by Algorithm Twth feature mapping Φ
In principle, (m)) diverges slowly compared to the convergence (6). the error of (Φ,, vic) still characterized by Theorem Thus, if & is such that the asymptotic bias given by (6) goes to zero as m - 0o, there exists a consistent nonparametric estimator ( m) with sufficiently slowly diverging function mn)...
Below, we show a typical instance of such consistent nonparametric estimators, namely the refining tile-coding estimator. Henceforth, we assume for simplicity S x A = [0, d 2 1, i.e., both states and actions are continuous. D
Definition 12 (Refining tile-coding sequence). We call & as the refining tile-coding sequence if. for all m 2 1, <fm) is tabular with respect the m -partitionn (P(T)) ke[mm] such that pl(m) -[]= I for all k = =ki,..,,,k ki)) E [m]], where I(m)
= k- 11 h for all 1 S k < m and rIm) == 1 kg
m 1]
Leveraging Theorem 13 the non-asymptotic version of Theorem 6 it is shown the nonparametric estimation using the tile-coding scheme consistent under very mild assumptions.
Proposition 10. For the refining tile-coding sequence &, we have [T; m)) " ((T) a.s.
1. =" is G -m-mxxing for some G oo (Assumption 7.
2. 0 o₁ inf u(s, S C₁ == sup <c.
3. (n)) //n 0 as n cc.
Note that Proposition 10 assumes nothing on pr. PT. Po and π other than the implicit well-definedness of their density functions. Because of this, the rate of convergence may be arbitrarily slow. We have stronger guarantee if some regularities of the density ratio 2/μ given. typical example of such regularity is the Lipschitz continuity.
Proposition 11. Under the assumptions of Proposition 10 if fv/p is Lipschitz continuous on x A. then we have [J(;; Φb, m) J(x)] = O(n 2 with m()) ( 2044
Note that the stronger convergence result obtained still without any explicit conditions on the reward and the transition dynamics. This matches the implication of Theorem 6 the error can be controlled with the norm of Rxx which measures the regularity of v/p, without forcing explicit regularities on the Beliman operator.
4 Related Work
The offline policy evaluation is closely related the off-policy policy evaluation the bandit and RL literatures (Precup) 2000) DDudi et al. 2011) [Sutton and Barto 2018), where behavior policies are often assumed to be known. Recently, number researchers are focusing on more 'offline" settings (Levine al. 2020) featuring unknown data-collecting policies and relatively large distribution shifts.
The theory of OPE has been often studied under a number of different types of realizability conditions. common type of realizability is the cellman-operatee realizability (Y'n and Wang [2020] Duan et al.) 2020). Jin et al. 2020) also considered the same, but approximate realizability and presented an upper bound with respect to the violation of the realizability. Xie and Jiang (2020) studied offline RI. under the Q-function realizability, relaxation of the Bellman-operator realizability, also allowing small realizability- violation vitollatttt
their analysis. In comparison, we focus on exactly evaluating (dominating term of) the OPE error to understand more about the phenomenon under unrealizability, not just bounding it from above, which allows us to find the double robustness and show the consistency of the nonparametric estimator without realizability.
'It is possible extend it to allow states and actions being discrete partially entirely.

---

Doubly-robust properties similar to Theorem were previously studied in the literature (Kallus and [eharr 2020: Tang et al. 2019). In particular, Theorem quite similar to Theorem 3.1 in Tang et al.) (2019) as both establish the double robustness of the bias of some OPE methods, although they are orthogonal one another in the following senses. Theorem (hshows the DR property of linear DM, while Kallus and Uehara (2020): [Tang et al. (2019) establish those of generic meta algorithms based on given (nice) malue-function and density-ratio estimators. In particular, Theorem 6 is nontrivial from the context of meta algorithm because linear DM does not perform any density-ratio estimation explicitly. Theorem is also closely related to Example 2 and Example in [Uehara et al. (2020). These examples show that linear DM can be interpreted as both value function regression and density ratio regression, but their analysis requires both the Q-function and the density realizabilities to achieve the consistency (Table I
Theories of the kernel-based RL. naturally takes into account the function approximation error. The difference between kernel-based methods and linear methods is subtle; Although kernel methods tends to more expensive in computation, they can be approximated with a finite linear basis (Rahimi al. 2007). Ormoneit and Sen (2002) shows a kernel-smoothing approach yields nonparametric convergence rate of O(n 224+) under different regularity assumptions, including the continuity of f. (Feng et al., (2020) studied a kernel-based OPE with confidence error bound, but the error bound is algorithmicaly determined and not studied analytically.
Concluding Remarks
We have derived an asymptotically exact characterization of the error of the linear direct estimators, one of the most simple and basic OPE methods, under a completely unrealizable setting. As consequence, we have found that the error matches the inner product of two residual functions implying the double robustness of linear DM, each of which measures the unrealizability of the value function and the marginal density ratio, respectively. We have also found the compatibility of øi as a key condition that guarantees the above identity. Finally, we have investigated as its application the егтor of nonparametric estimators.
Limitation. One limitation of the present work is that we do not have any methods to control || other than Proposition 9 which affects the speed of the concentration (6). In particular, this makes difficult to construct consistent nonparametric estimators with general feature sequences & other than the tabular ones since the norm || may depend on n. in nontrivial manner. However, discussed in Section 3.1.1 controlling || [ is at least equivalent of keeping the hard instances away from the easy instances in the sense of Wang et al. (2020) and Amortila et al. (2020). Thus, we speculate it could be a key question for better understanding of the hardness of OPE problems, rather than just a technical difficulty.
Another limitation is that all the results in this paper are derived under the implicit assumption that the marginal target density v is well defined with respect to the base measure of S x A. In particular, generalized functions like Dirac's delta density function cannot be handled straightforwardly in our framework.
Feature Work. The generalization of the double robustness of linear DM to nonlinear estimators would be interesting future direction. Studies on the compatibility of the feature mappings 6 with higher-order smoothness such as Gaussian radial basis functions, spline functions and neural tangent kernels (Jacot et al. 2018) are promising for faster convergence rate of the nonparametric estimator. Another promising direction is to extend the current analysis towards adaptive state-abstraction methods, e.g., Whiteson (2007).
Acknowledgment
We deeply thank all the reviewers and the area chair for extensive discussions, which help us greatly improve the manuscript.
10

---

References
Amortila, P., Jiang, N., and Xie, T. (2020). A variant of the wang-foster-kakade lower bound for the discounted setting. arXiv preprint arXiv:2011.01075,
Bradley, R. C. (2005). Basic properties of strong mixing conditions. survey and some open questions. arXiv preprint math/051 1078.
Duan, Y. Jia, Z., and Wang, M. (2020). Minimax-optimal off-policy evaluation with linear function approximation. In International Conference on Machine Learning, pages 2701-2709, PMLR.
Dudík, M., Langford, J., and Li, L. (2011). Doubly robust policy evaluation and learning, arXiv preprint arXiv:1103.400 103, 4601.
Feng, Y., Li. L.., and Liu, Q. (2019). A kernel loss for solving the bellman equation. arXiv preprint arXiv: 1905. 10506.
Feng, Y., Ren, T., Tang, Z. and Liu, Q. (2020). Accountable pof-py evaluation with kernel bellman statistics. In International Conference on Machine Learning, pages 3102-3111. PMLR.
Freedman, D. A. (1975). On tail probabilities for martingales. the Annals of Probability, pages 100-118.
Fu, J., Norouzi, M., Nachum, O., Tucker, G., Wang, Z., Novikov, A., Yang, M., Zhang, M. R., Chen, Y., Kumar, A., et al. (2021). Benchmarks for deep off off-policy evaluation. arXiv preprint arXiv:2103. 16596.
Jacot, A., Gabriel, F., and Hongler, C. (2018). Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arX1v:1806.07572.
Jin, C., Yang, Z., Wang. Z., and Jordan, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR.
Kallus, N. and Uehara, (2020). Double reinforcement learning for efficient off-policy evaluation in markov decision processes. J. Mach. Learn. Res., 21:167-1.
Lagoudakis, M. G. and Parr, R. (2003). Least-squares policy iteration. The Journal of Machine Learning Research, 4:1 107-1149.
Le, H., Voloshin, C., and Yue, Y. (2019). Batch policy learning under constraints. In International Conference on Machine Learning, pages 3703-3712. PMLR.
Levin, D. A. and Peres, Y. (2017). Markov chains and mixing times, volume 107. American Mathematical Soc.
Levine, S., Kumar, A., Tucker, G., and Fu, J. (2020). Offline reinforcement learning: Tutorial, review, and perspectives open problems. arXiv preprint arXiv:2005.01643
Nachum, O., Chow, Y., Dai, B., and Li, L. (2019). Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. arXiv preprint arXiv: 1XXV:19966.07333
Ormoneit, D. and Sen, S. (2002). Kernel-based reinforcement learning. Machine learning, 1962):161- 178.
Precup, D. (2000). Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, page 80.
Rahimi, A., Recht, B., al. (2007). Random features for large-scale kernel machines. In NIPS,
volume 3, page 5. Citeseer.
Sutton, R. S. and Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.
Tang, 7., Feng, Y., Li, I.., Zhou, D., and Liu, Q. (2019). Doubly robust bias reduction in infinite horizon off-policy estimation. arXiv preprint 17Xiv:191.

---

Tropp, J. A. (2012). User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(():389-443) 4344.
Uehara, M., Huang, J., and Jiang, (2020). Minimax weight and q-function learning for off-policy
evaluation. In International Conference on Machine Learning, pages 9659-9668. PMLR.
Voloshin, C., Le, H. M., Jiang, N., and Yue, Y. (2019). Empirical study of off-policy policy evaluation for reinforcement learning. arXiv preprint arXiv:/911.0685:
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.11895
Whiteson, (2007). Adaptive tile coding for value function approximation. Technical report.
Xie, T. and Jiang, N. (2020), Batch value-function approximation with only realizability. arXiv preprint (xXix:2008.04990
Yin, M. and Wang, Y.-.. (2020). Asymptotically efficient off-policy evaluation for tabular rein- forcement learning. In International Conference on Artificial Intelligence and Statistics, pages 1948-3955 PMLR.
12


Reviews:
[{"review_id": "lBYVKxviPBl", "reviewer": "Reviewer_rVKG", "summary": "The paper consider off-policy evaluation using linear function approximation\nunder unrealizability setting.\nUnder such more relaxed assumption, they provide characterization of the linear direct method(DM)\nas an error governed by two approximation residual $\\mathcal{R}_B$ and $\\mathcal{R}_X$,\n$$\n    \\hat{J}(\\pi) - J(\\pi) = \\mathbb{E}[\\mathcal{R}_B(s,a)\\mathcal{R}_X(s,a)] + O(1/\\sqrt{n}),\n$$\nwith $\\mathcal{R}_B$ corresponding to Bellman residual and \n$\\mathcal{R}_X$ corresponding to residual of marginal density ratio.\nLeveraing this result, they establish a nonparametric tile-coding estimators \nto solve the unrealizability though with a slower convergence.", "questions": "", "limitations": "", "rating": 4, "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": "**Novelty:**\nI have the major concern about the novelty of this paper,\nwhere there is a large class of OPE literature about doubly robust estimator, e.g. [1-2], \nthe paper fails to discuss and compare with.\nEspecially in [2] Theorem 3.1, the bias term of double robustness estimator can be characterized\nas the inner product of two residual terms of Bellman residual and residual of marginal density ratio.\nAlthough the two estimators compared is not exactly the same (doubly robust vs DM), \nthe bias error decomposition looks quite similar.\n\nI encourage the author to investigate deeper into those papers and find out the relationship.\nIt is possible that the similar error decomposition can imply linear DM is \nalready a doubly robust estimator in some sense, which may be a very interesting finding.\n\n**Quality, Clarity and Significance:**\nI am satisfied with the quality and the clarity of the paper.\nThe theoretical significance is still lacking before comparison with doubly robust estimator.\n\nReference:\n\n[1] Kallus, Nathan, and Masatoshi Uehara. \"Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes.\" \n\n[2] Tang, Z., Feng, Y., Li, L., Zhou, D., Liu, Q. (2019). Doubly robust bias reduction in infinite horizon off-policy estimation.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "hKWX2pC7IJU", "reviewer": "Reviewer_xAW2", "summary": "This paper characterizes the offline policy evaluation (OPE) error with linear function approximation in the discounted reward setting. With certain assumptions, this paper proves that the error of Linear Direct OPE algorithm (which is equivalent to the limit of Fitted Q-Evaluation algorithm) converges to the expectation of the product of two residuals. As a corollary, when either the function class is closed or the density ratio is realizable, the asymptotic error is zero. In addition, in the same setting the paper upper bounds the OPE error for tile-coding estimator.\n\n", "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": "This paper proves a novel asymptotic characterization of the OPE error with non-realizable linear function approximation. Compared with previous results, this paper exactly computes the dominant term of the OPE error, instead of providing an upper bound.\n\nOn the plus side, this paper is well written. Proofs are technically sound and solid. The results imply that the direct OPE (as well as the Fitted Q-Evaluation) algorithm automatically satisfies doubly-robust-type error bound: when either the Bellman residual is small or the density ratio can be well approximated, the estimation error is small. So this paper could contribute to the understanding of linear OPE tasks.\n\nThe main weakness of this paper is that the results are asymptotic (i.e., only holds when the number of samples approaches infinite). It is unclear how realistic are the phenomena described in this paper. For example, the convergence rate in Theorem 6 depends polynomially on the term 1/c_\\mu, which is the minimum data density over all state-action pairs. For MDPs with large state/action space, the term could be much larger than the number of samples. In other words, it’s unclear whether the dominating term is still characterized by Eq. (6) in real-world OPE tasks.\n\nIn addition, this paper doesn’t directly tackle the difficulty of linear OPE tasks. On the one hand, the assumptions such as 1/c_\\mu-dependence or upper bound of \\|F^#_\\gamma\\|_2 exclude some natural hard instances. Are these assumptions an artifact of the analysis, or necessary for the result? On the other hand, the sample complexity of tile-coding estimators is exponential in the dimension d, which is not very realistic.\n\nMinor issues which may cause unnecessary confusion:\n-\tThe notation f* in Definition 8 and 9 is used to denote different functions.\n-\tDoes Definition 3 depend on the policy \\pi being evaluated (because the term (P\\phi)(s,a) depends on \\pi)? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed limitations and potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "DUVhg6TB6U3", "reviewer": "Reviewer_Fdr6", "summary": "They analyze the linear DM method in detail. They prove that the estimator has an error form, which is written as an inner product of two residual functions. One is associated with the misspecification of Q-functions. Another is related to the misspecification of W-functions. \n", "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": " I appreciate the author's detailed analysis. In this paper, if I understand correctly, the main new finding of this paper is if you have realizability of marginal ratios and the existence of  I-\\gamma F^{#}, you can show the PAC guarantee.  \n\n1; if I understand correctly, the non-singularity (existence) of I-\\gamma F^{#} is pretty much strong. If you use minimax-type estimators with linear models like modified RBM in CJ 2019 (this paper is for learning but for the modification of policy evaluation is easy), I guess that you can prove the closedness of Q-function class like TQ \\subset Q' as you can write like a^{\\top} (I-\\gamma F) \\phi  \\subset b^{\\top}\\phi (Q and Q' are linear models with different radius ) I think this kind of discussion is essential. The present discussion in Section 3.1.1 really does not discuss this point. ( non-singularity of I-gamma F^{#} versus the closedness of Q-function linear class. )\n\n2: Second, UIJKSX 2021 might already show one of the main findings of this paper. They showed that the realizability of marginal ratios and the closedness of the Bellman operator for marginal ratios are sufficient for PAC guarrantee. I think the non-singularity of I- gamma F^{#} essentially says the closedness of the bellman operator for marginal ratios. Pleasee refer to Lemma 4 in UIJKSX. I am sorry if I am wrong at this point.....( Note their estimators are DM methods when using linear models. The estimator is essentially the same as this paper. )\n\n3: Line 341 \" To the best of our knowledge, the present study is the first to report the density-ratio-estimation 342 interpretation of linear direct methods in unrealizable settings\"\nThat sounds not correct. For example, if you see UIJKSX 2021, they show the realizability of marginal ratios and Q-functions are sufficient for PAC guarantee by presenting unrealizable settings first (theorem 10). The error takes the product form like the errors for marginal ratios and the errors for Q-functions. (Though this form is different from (6) in the author's paper, you can get rid of the boundedness of F^{#} in their expansion. ) \n\n\n[CJ ]Information-Theoretic Considerations in Batch Reinforcement Learning\nhttps://arxiv.org/abs/1905.00360\n[UIJKSX] Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency https://arxiv.org/pdf/2102.02981.pdf\n\n-----------------------------------------------------\n\nAfter thinking more, what I wrote regarding the first point and second point are wrong. I apologize for that. Please ignore them. \nSomehow, the mysterious assumption, the existence of (I-gamma F^{#}) helps and produces a nice result. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No ", "review_text": "", "extra_scores": {"ethical_concerns": "No ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "3qesrNA9ZD", "reviewer": "Reviewer_S51y", "summary": "In this paper, the authors analyze the off-policy evaluation error of a direct estimator with linear function approximation under unrealizability. In Theorem 6, they derive the closed form of the asymptotic bias term as the number of samples approaching \\infty. Besides, in section 3.2, they study another method where the feature mappings can be selected adaptively and provide the convergence analysis for their estimation to ground-truth J(\\pi).", "questions": "", "limitations": "", "rating": 5, "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": "This paper is well-written, and the notation and definitions are clear. Their theoretical results are solid and interesting. But I’m concerned about the significance of the contribution of this paper.\n\n(1) I’m feeling the theoretical results in Theorem 6 may not be novel enough. The bias decomposition in Theorem 6 is similar to the Eq (12) in [1], in which the authors proposed a “doubly robust” estimator and decomposed the bias to the residual of density ratio estimation error and value estimation error.\n\nIt seems that if we use linear functions to approximate density ratio and value function (e.g. see Example 2 and Example 7 in [2]) with the same data and plug them into the “doubly-robust estimator” in [1], it directly recovers the \\hat J(\\pi) estimator in Algorithm 1 in this paper. As a result, a bias term similar to Theorem 6 can be obtained by directly adapting from results in [1] to the linear setting as a special case with a different definition of “residual” (R_\\chi & R_B in this paper v.s. \\epsilon_{\\hat w} & \\epsilon_{\\hat V} in [1]).\n\nI wonder if the authors can discuss some connections and essential differences comparing with the results in [1], which is missing in the paper.\n\n(2) Although the analysis in this paper fills some blanks in OPE research, I'm feeling the results in this paper is not substantial enough. It would be a more solid paper to me if there are more discussions about what we can do with the bias analysis, or say, how can we use that bias analysis (e.g. given two feature sets, can we identify the one with a smaller bias), or maybe more bias analysis beyond the linear setting with unrealizability.\n\nReference:\n\n[1] Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation, Ziyang Tang, Yihao Feng, Lihong Li, Dengyong Zhou, and Qiang Liu\n\n[2] Minimax Weight and Q-Function Learning for Off-Policy Evaluation, Masatoshi Uehara, Jiawei Huang, and Nan Jiang", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "-4BWWiWIdO8", "reviewer": "Reviewer_pMsS", "summary": "This is a theoretical paper which addresses the RL off-policy evaluation with linear function approximation. It proves convergence results of linear function approximations and shows that the direct method (model the dynamics) is asymptotically equivalent to FQE (modeling the value function) and analyzes its convergence properties. Additionally, it proves consistency results for such methods under tile-coding, allowing for consistency (using non-parametric estimation) even under unrealizability of the linear approximators.", "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": "The paper presents interesting results and is well written. I did not check all the proofs in the paper (it is more theoretically oriented than my expertise), and therefore my confidence in the review is limited. It has two major drawbacks - The first and most obvious one is its reliance on linearity. It is uncommon for linear models to properly model MDPs of interest, and therefore I am not sure how impactful the results will be. The authors do provide consistency results using feature tiling which allows for consistency using tile-coding, and therefore the results could in essence be applied to highly nonlinear MDPs, but I expect such case to be limited to low dimensional MDPs in the same way non-parametric always suffer in high dimensions. Second, the set of assumptions the authors use, while not very strong, is very uncommon compared to the majority of OPE work, further limiting the potential of these results to have a large impact on the field.\n\nThe central result (theorem 6) is very reminiscent of the properties of the (very commonly used in OPE) doubly robust estimator. The DR is unbiased if either the behavior policy is know (analogous to R_X being realizable), or the control variate is accurate (analogous to R_B being realizable). I am not sure how useful the analogy is in this case, but since it is a very obvious analogy and DR is such a common estimator in OPE it might be worth exploring.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "~4 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper characterizes the asymptotic bias of off-policy evaluation using linear function approximation when realizability assumptions do not hold, with convergence rate analysis. The major concerns of the reviewers focused on the paper's lack of discussions of closely related results in MIS (e.g., Uehara et al, Tang et al); in fact, some of the high-level claims in the paper (e.g., first to discover connection between direct methods and density-ratio learning, first to provide "doubly robust" guarantee to LSTDQ) are already known in the prior works. 

After extensive post-rebuttal discussions, the AC decides that this is borderline paper that can go either way, but their personal recommendation is acceptance: the paper's exact characterization of the bias in LSTDQ is a significant result. As mentioned above, prior works have noticed the curious nature of LSTDQ and how it connects to MIS methods, but an exact characterization of its bias is missing, and different approaches to bounding the bias (e.g., under either realizability of value function or density ratio) yield different results, lacking unification. 

This paper solves this problem by providing the *exact* characterization of the bias, which takes the form of the product of realizability errors of value function and density ratio, respectively. For reference, the most comparable results that is previously known takes the form of minimum over these errors; see post-rebuttal discussions (also Remark 2 in Appendix A of Uehara et al, which does not require realizability). While multiplicative errors are known for doubly robust estimators (e.g., Tang et al, Kallus and Uehara), these are meta-estimators and require approximate value function and density ratio as inputs, so the results are somewhat orthogonal to the current paper. Furthermore, the paper complements the bias analysis by a convergence rate analysis, which takes care of non i.i.d. data and finite-sample effects. With all these, the AC feels that the paper will be a valuable reference for anyone who wants to investigate the statistical behavior of linear OPE estimators, and therefore recommends acceptance. 

Despite the AC's recommendation, the authors are noted that missing significant related works is a major issue, and a rejection will also be reasonable given that the revision needed is quite substantial that may warrant another round of reviewing. Regardless of the final decision, the authors are urged to fix overclaiming and draw connections to related works. Just to give a few pointers: 

- Abstract: "OPE ... has been advanced under the (approximate) realizability assumptions. However, such assumptions undermine the applicability of the results since the given environmental models may be completely wrong." This sentence suggests a qualitative difference from existing works, whereas the actual difference is more quantitative.

- Line 60: " new interpretation of the linear DMs as marginal density ratio estimator" Already known in the literature.

- A comparison to previous upper bounds on the bias should be provided.

Finally, some additional detailed comments from the AC:

1. The authors might want to reconsider the title, which is not very informative in its current form given that the central result is the exact characterization of bias and the connection between DM (LSTDQ) and MIS is somewhat known. Also, linear function approximation is a crucial component of the setup, which is not reflected in the title.

2. The authors mentioned the lower bound of Wang et al several times during discussions, but may have some slight misunderstanding of their results. It was mentioned that they assumed bounded $1/C_{\mu}$, which is not true. Wang et al's data assumption is about the minimal eigenvalue of $\Sigma$, which is a much weaker one; the authors should be careful when discussing related issues in the paper. On a somewhat related note, the paper's derivation requires invertible $\Sigma$, but that may not be necessary. In the usual LSTD analyses, $\Sigma$ and $(I-\gamma F^{\\#})$ is often multiplied together as a single matrix (usually in the form of $E[\phi(s)\phi(s) - \gamma \phi(s) \phi(s')]$, and the requirement of invertibility of $\Sigma$ may be an artifact of extracting out $\Sigma$. 

3. Def 9 for "Bellman residual" is not as interpretable as Def 8. For Def 8, one can easily see that the residual is 0 if the linear class realizes the true density ratio function. For Def 9, it is unclear/unintuitive why the residual is 0 when the linear class realizes the true value function (though I think $Q^{\\#}=Q^\pi$ when $Q^\pi$ is realizable and therefore the residual is $0$ in this case); the reference to $Q^{\\#}$ in the definition is somewhat undesirable since the quantity is a complicated expression in the estimator which does not make direct sense in the MDP. Also, if $Q^{\\#}$ is allowed in the expression, bias can be trivially written as $E_{p_0^\pi}[Q^{\\#} - Q^\pi]$ which is vacuous. Is it possible to rewrite it as an expression that looks like more standard forms of Bellman errors, e.g., replacing $B Q^{\\#} - q$ with $B q - q$?

Uehara et al. Minimax Weight and Q-Function Learning for Off-Policy Evaluation.

Kallus and Uehara. Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes.

Tang et al. Doubly robust bias reduction in infinite horizon off-policy estimation.

Wang et al. What are the Statistical Limits of Offline RL with Linear Function Approximation?
Decision: Accept (Poster)