Variance-Aware Off-Policy Evaluation with Linear Function Approximation
Authors: Yifei Min
Tianhao Wang
Dongruo Zhou
Quanquan Gu
Venue: NeurIPS 2021 Poster (2021)
Keywords: off-policy evaluation
offpolicy
reinforcement learning
linear function approximation

Abstract: We study the off-policy evaluation (OPE) problem in reinforcement learning with linear function approximation, which aims to estimate the value function of a target policy based on the offline data collected by a behavior policy. We propose to incorporate the variance information of the value function to improve the sample efficiency of OPE. More specifically, for time-inhomogeneous episodic linear Markov decision processes (MDPs), we propose an algorithm, \texttt{VA-OPE}, which uses the estimated variance of the value function to reweight the Bellman residual in Fitted Q-Iteration. We show that our algorithm achieves a tighter error bound than the best-known result. We also provide a fine-grained characterization of the distribution shift between the behavior policy and the target policy. Extensive numerical experiments corroborate our theory.

Variance-Aware Off-Policy Evaluation with Linear Function Approximation
Yifei Min"
Tianhao Wang"
Department of Statistics and Data Science Yale University CT 06511 yifei. aeteeii.mn@yall...m edu
Department of Statistics and Data Science Yale University CT 06511
tianhao. www.owwwwnaaaa..e.eemommoom
Dongruo Zhou
Quanquan Gu
Department of Computer Science University of California, Los Angeles
Department of Computer Science University of California, Los Angeles CA 90095
CA 90095 drzhou@cs, ucla. edu
gguêcs ucla.
Abstract
We study the off-policy evaluation (OPE) problem in reinforcement learning with linear function approximation, which aims estimate the value function of target policy based on the offline data collected by a behavior policy. We propose to incorporate the variance information of the value function to improve the sample efficiency of OPE. More specifically, for time-inhomogennous episodic linear Markov decision processes (MDPs), uses the estimated variance of the value function to reweight the Bellman residual in Fitted Q-Iteration. We show that our algorithm achieves tighter error bound than the best-known result. We also provide fine-grained characterization of the distribution shift between the behavior policy and the target policy. Extensive numerical experiments corroborate our theory.
propose algorithm, VA-OPE, which
Introduction
Reinforcement learning (RL) has been hot spot in both theory and practice in the past decade. Many efficient algorithms have been proposed and theoretically analyzed for finding the optimal policy adopted by an agent maximize the long-term cumulative rewards. In contrast online RL where the agent actively interacts with the environment, offline RL (a.k.a., batch RL) [25, 24] aims to extract information from past data and this information learn the optimal policy. There has been much empirical success of offline RL in various application domains [4, 6, 37, 40,30,,6) 36).
Among various tasks of offline RL, an important task is called off-policy evaluation (OPE), which evaluates the performance of a target policy π given offline data generated by a behavior policy म. Most existing theoretical works OPE are in the setting of tabular MDPs [34, 26, 11, 16, 45, 47-49), where the state space and the action space A are both finite. However, real-world applications often have high-dimensional approximation is required for computational tractability and generalization. While provably efficient online RL with linear function approximation has been widely studied recently [46, 17, 50, 15, 3, 54], little work has been done for analyzing OPE with linear function approximation, with one notable exception by Duan al. [10]. More specifically, Duan al. [10] analyzed regression-based
state and action spaces, where function
"Equal contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Fitted Q-Iteration method (FQI-OPE) that achieves an Õ(H² ((1 + d( x))/N) enror for linear MDPs [46, 17], where H is the planning horizon, N is the sample size, and d( म) represents the distribution shift between the behavior policy and the target policy. They also proved a sample complexity lower bound for a subclass of linear MDPs, for which their algorithm nearly minimax optimal. However, as we will show later, the H² dependence is not tight since they discard the useful variance information contained in the offline data. Consequently, their result is only optimal for a small class of MDPs of which the value functions have large variance. The H2 dependence in the sample complexity also makes their algorithm less sample-efficient for long-horizon problems, which is one of the major challenges in RL.
Extracting useful information from the data is particularly important for offline RL since the agent cannot sample additional data by interacting with the environment, as compared to online RL. In this paper, we propose a new algorithm that incorporates the variance information of the value functions to improve the sample efficiency of OPE. This allows us to achieve a deeper understanding and tighter error bounds of OPE with linear function approximation. In detail, we consider time-inhomogeneous linear MDPs [46, 17] where the transition probability and reward function are assumed to be linear functions of known feature mapping and may vary from stage to stage.
The main contributions of this paper are summarized as follows:
We develop VA-OPE (Variance-Awart Aware Off-Policy Evaluation), an algorithm for OPE that effectively utilizes the variance information from the offline data. The core idea behind the proposed algorithm is to calibrate the Bellman residual in the regression by an estimator of the conditional variance of the value functions, such that data points of higher quality can receive larger important weights.
We show that our algorithm achieves O (v, Vn is the expectation of the feature vectors under target policy and A, is the uncentered covariance matrix under behavior policy weighted by the conditional variance of the value function. Our algorithm achieves tighter error bound and milder dependence on H than FQI-OPE [10], and provides a tighter characterization of the distribution shift between the behavior policy and the target policy, which is also verified by extensive numerical experiments.
///)//KKK)) policy evaluation error, where
Our analysis is based induction to establish worst-case uniform convergence results for the estimators of the value functions. In the second step, the convergence of OPE estimator is proved by tightening the uniform convergence result based on an average-case analysis. Our proof strategy provides a generic way for analyzing (weighted) ridge regression methods that are carried out backward and iterated fashion. The analyses in both steps might be of independent interest.
novel two-step proof technique. In the first step, use backward
Notation We use lower case letters to denote scalars and use lower and upper case boldface letters to denote vectors and matrices respectively. For any vector x E Rdd and any positive semi deiiniefnitee matrix Σ Rdxd, we denote by |x||2 the Euclidean norm and || ΣΣ]
the operator norm, and define ||x||= = V Σx. For any positive integer n. we denote by [n]] the set (1.....n) n]. For any finite set A, denote by |A] the cardinality of A. For two sequences {an) and (b,.), we write a, Ob,,) there exists an absolute constant C. such that on I Cbn, and we write 0, = (2b,,)) if there exists an absolute constant C such that an, 2 Cbn, We use O() to further hide the logarithmic factors.
2 Preliminaries
2.1 Markoy Decision Processes
We consider the time-inhomoogeneous episodic Markov Decision Process (MDP), which is represented by tuple M (S, A, H, {rx { In specific, we denote the state space by S and the action space by A. and H 0 is the horizon length of each episode. At each stage h [H].
Th : S x A + [0. 1] is the reward function, and PA, (s'|s, ls a) is the transition probability function which represents the probability for state s to transit to state given action a. policy л consists of
H mappings (TT } from S to the simplex on A, such that for any (h,s) [H] x S, TT (-(s) is
probability distribution over A. Here a policy can be either deterministic (point mass) or stochastic.
By uniform convergence we mean the convergence of the estimated value functions in norm to their true values, which is different from the uniform convergence over all policies in Yin et al. [48].

---

For any policy и, we define the associated action-value function (7, a) and value function Vi each stage [H] as follows:
(s, a) Ex Σ (1( 8b - 5, 0n =a =a
(T) - 2% Qh a))
(2.1)
where ag ~ (-1:8; and 8141 ~ Pi(-|ss, a;). For any function V : S + R. we introduce the following shorthand notation for the conditional expectation and variance of V: [P a) = (e
[V)V](s,a) = [P a) - (Is)) (2.2)
Time-inhomogeneous linear MDPs. We consider special class of MDPs called linear MDPs [46, 17]. Note that most of the existing works on RL with linear function approximation rely on this assumption.
H ) is called a linear MDP with known feature mapping Φ : 8 x + Rd, if for any h [H], there exist Yh and us E Rd, such that for any state-action pair (s, a) E S x A, it holds that
Assumption 2.1. (,,,,, (T (Ph)-
(- 8, a) = (Φ(s, (*)),;
a) ()(s,.), 7k))
(2.3)
We assume that at any stage h. for any state-action pair (8,a) E S x A. the reward received by the agent is given by r = (x, a) + c (8, (8,a). a), where Tn (8,a) E [0, 1] is the expected reward and e (8, a) is the random noise. We assume that the noise is zero-mean and independent of anything else.
Without loss of generality, we assume that 1 We also assume that ry (s, a) + cx,ss, a) S 1, (s, a)l S 1 almost surely and thus Var(ca a)) < for all & E [H] and (s, a) E S x A. Moreover, we assume that maxлe(H] Il.s ((s)ddp()))l S vd for all bounded function S > IR such that sup.es [f(s) S 1.
and [| a) S for all (s, a) E 8 A.
The above assumption on linear MDPs implies the following proposition for the action-value func- tions.
Proposition 2.2 (Proposition 2.3, [17]). For linear MDP, for any policy x, there exist weights (w7, h E [H]] such that for any (s,a, h)) E x A x [H], we have Q% (s. = (Φ((, a), wi) Moreover, we have || la S 2// vd for all h E [M].
Following this proposition, we may further show that the value functions are also linear functions, but of different features. We define (s)(s) -A (ss, (aT)ss for all e [S] and E [H]. Then by 12.1) we have
(T) / Φ(s,a) wādw(als)
2.2 Off-polic Evaluation
The purpose of OPE is to evaluate a (known) target policy ar given an offline dataset generated by a different (unknown) behavior policy æ. In this paper, our goal is to estimate the expectation of the value function induced by и over fixed initial distribution Ç1, i.e.,
Eg [VT (s)]-
To faciliate the presentation, we further introduce some important notations. For all h E [H), let va be the occupancy measure over S x A at stage h induced by the transition P and the behavior policy म. that is, for any E C S x A,
pn = E [[s,, an) E E' 51 ~ E1, a; #(-1s),, 5:+1 Pr(--ss, at), 1 15 S h].
(2.4)
For simplicity, we write LE, (f, a)] = Ex, =f,
SSXA f(s, a))) a) for any function on x A. Similarly, we use Er,, n. [[(, (6, a)] to denote the expectation of / with respect to the occupancy measure at stage h induced by the transition P and the target policy и.
We define the following uncentered covariance matrix under behavior policy for all h e [H]:
Σ Σ+, [ a))(s, T]
(2.5)
Intuitively, these matrices measure the coverage of the offline data in the state-action space. It is known that the success OPE necessitates good coverage [10, 43). Therefore here we make the same coverage assumption on the offline data.
3

---

Assumption 2.3 (Coverage). For all h E [H] Kh = Amiu (En) > 0. Denote k minme(m]
key difference in our result is that, instead of depending on Σ, directly, the error bound depends on the following weighted version of the covariance matrices defined
A == Ex, [on (s, a) 2 *d(s, ())((s
(2.6)
for all h E [H]] where each σ% S x A + R is defined as
(s) = max(L, (s, +1.
(2.7)
Note that in the definition of (.((..)) taking the maximum and adding an extra is purely for technical reason and is related to its estimator ōx (-.)). which we will introduce and explain later in Section 3.2. In general, one can think of of a) R Vn Vr ( a). Therefore, compared with the raw covariance matrix En. As further incorporates the variance of the value functions under the target policy. This the key to obtaining a tighter dependent error bound.
Definition 2.4 (Variance-aware coverage). We define in. Amin (Aa) and 1 = minneeH]] 4h-
Since SUP(s.))SxA a)² is bounded from above, by (2.6) and Assumption 2.3, we immediately have in 2 / (s.
0% (s, a) > 0 for all h [H]] and thus 0. Even if Assump- tion 2.3 does not hold, we can always restrict to the subspace span (( sh, an)). J. For convenience of presentation, we make Assumption 2.3 this paper.
Next, we introduce the assumption on the sampling process of the offline data.
Assumption 2.5 (Stage-sampling Data). We have two offline datasets D and D where each dataset consists of data from H stages: D (Diheεи) and D {Da)nema For the dataset D. we assume Di, is independent of Dr, for h1 * h2. For each stage h, we have Dr. ((Sk,h: Ok, Fk sk,n) ke[]], where we assume for each k E [K], the data point (sk,h: Ok,h: hk,,; (,,)) is sampled identically and independently in the following way: (sK,,, ok.h) (.(:.)) where un (;,')) is the occupancy measure defined in (2.4), and s PA (-1sk,, ag,h). The same holds for D, and we write Dr, ( 0k.hs tu,,, &y, h, ]RE[K]- Note that here 5k,6 # 8k,+1-
Assumptions 2.5 is standard in the offline RL literature [48, 10J. Note that in the assumption, there a data splitting, i.e., one can view it as the whole dataset D U D being split into two halves. The datasets and D will then be used for two different purposes in Algorithm I as will be made clear in the next section. We would like to remark that the only purpose of the splitting is to avoid lengthy analysis. There is no need to perform the data splitting in practice. Also, our implementation and experiments, do not split the data.
3 Algorithm
To case the notation, we denote Φx, = ((S2,A) (g.A), Φu. Φ(š an.n), ōx.b = ā (sw.n h ag,h) and тkR (5k.h, (g.A) + ER,A for all (h, [H] x [K]. Recall that we use the check mark to denote the other half of the splitted dataset. How the splitted data is utilized will be clear in Section 3.2 when we introduce the proposed algorithm.
3.1 Regression-Basse Value Function Estimation
By Proposition 2.2, it suffices to estimate the vectors {w h E [H]]. A popular approach is to apply the Least-Square Value Iteration (LSVI) [17] which relies on the Bellman equation, (s,(s,)) (x a) + (P, VA V. 17s, a), that holds for all h E [H] and (s, a) E S x A. By viewing V ( as an unbiased estimate of [Px V 1 (SE ak,k), the idea of the LSVI-type method is to solve the following ridge regression problem:
K
W = argmin A
12+++ +
Σ k=
[ w) -Kk. - (
(3.1)
wERd

---

for some regularization parameter À > 0. Since we do not know the exact values of h+1 in (3.1), we replace by an estimator V 1 and then recursively solve the lease-square problem a backward manner, which enjoys a closed-form solution follows
K Σ ΦLLDEE + AL
K Σ ΦKN Fk. + VH (441(5
This has been used in the LSVI-UCE algorithm proposed by Jin et al. [17] and the FQI-OPE algorithm studied by Duan et al. [10], for online learning and OPE of linear MDPs respectively. For this kind of algorithms, the key difficulty in the analysis lies in bounding the Bellman error:
K Σ
T SRACK + Ald
Σ Sann ([Pr (PP (ERI)
Jin et al. [17] applied a Hoeffding-type inequality to bound the Bellman error. Although Duan al. [10] applied Freedman's inequality their analysis, their algorithm design overlooks the variance information in the data and consequently they can only adopt a crude upper bound on the conditional variance of the value function, i.c., VvV441 S (H h)². which simply comes from supses V +++ (s) S H h. Therefore, prevents [10] from getting tight instance-dependent error bound for OPE. This is further verified by our numerical experiments in Appendix A which show that the performance of FQI-OP? degrades for large H. This motivates to utilize the variance
information in the data for OPE.
3.2 The Proposed Algorithm
In particular, present our main algorithm displayed in Algorithm 1. Due to the greedy nature of the value functions, we adopt a backward estimation scheme.
Weighted ridge regression. For any h [H]. let Wh+1 be the estimate of w computed at the previous step, and correspondingly ())+()) = (+)+ Wh11). Instead of the ordinary ridge regression (3.1), we consider the following weighted ridge regression:
argmin A/ w|| 1122
(DE w) Fk.h (irn( ok
(3.2)
h
weld
where Ōk.h (sk,k, (k.)) for all (h, k)) E [H] [K] with (:(,,)) being proper estimate of o)) defined in (2.7). We then have the following closed-for form solution (Line and 7 of Alg. I):
K
K
W = A- Σ
ΦR. (FK,A - VKtz(sh,n) okeh. with A = -o
+ Ala- (3.3)
k=1
In the above estimator, we use the dataset to estimate the value functions. Next, we apply an LSVI-type method estimate on using the dataset D.
Variance estimator.
By (2.2), we can write
VV (7 a) =BA -(...sl))a(((A,,llllll ((P.V),1(ssa))= For the first term in (3.4), by Assumption 2.1 we have
(PP.V
(3.4)
PA D (s. / V V =(ssa))
((s,a) / VTT ds)n
which suggests that IP also has linear representation. Thus adopt linear estimator (Φ(s,a), (,,,a),;;))) BT) where B (Line 4) is the solution to the following ridge regression problem:
K
K TR. D (3.5)
3 = arggii
Σ
(0x 1( tlellk = Σ Eh.
BERd
k=1
R=
5

---

Algorithm Variance-Aware Off-Policy Evaluation (VA-OPE)
1: Input: target policy π (TA he(H), datasets D ([(SE,) dg,s, Pk,,, s ) hE hE( bEELK] and
D - {[(8R,n, dR k h hejen))ek]] initial distribution Et, W
2: for h H, 1..... .....,..0 do
3: Σn Ex=1 PK AL
BB Σn "E SR VT (
4:
VT On ΣT E PK h+1 (k,h))
5:
(n(; + V mmxx(1 VA (+))):)) +1
6:
7:
An + Σk=1 D / ALa
8:
YuA + Tk, (07 ( WhI
WA A7 ""EE PR.h /
9:
10:
(7()))) - ( wh),
(.()) <- (6)(),
end for
12: Output: of Js V (s) (s)
Similarly, estimate the second term in (3.4) by (1b(s, a), 0%), where 0% (Line 5) given by
0n argmin BRRd
( 0) ( Al10 E 2u.n (
(3.6)
with Σn E TR Alg. Combining (3.5) and (3.6), estimate Vn V by
(o ( 10. (((())) 0
(3.7)
where the subscript [0, (H - h 1) denotes the clipping into the given range, and similar for the subscript (0, h + 1]. We do such clipping due to the fact that Vi E [0, H h). We add to deal with the approximation error in 7 1+1
Based on v D= 1+ the final variance estimator Ōn(---) (Line 6) is defined as
G.(..)) = max(1, VA Va Vitiii (..)) +
In order to deal with the situation where V V < 0 or very close to O, we take maximum h+1 and 1. Also, account for the noise in the observed rewards, add an extra 1 which is an upper bound of the noise variance by Assumption 2.1.
between Vn VT
Final estimator. Recursively repeat the above procedure for h H, H - 1,.... 1, and obtain Vg. Then the final estimator for of (Line 12) is defined as 0ह Ss VTT ds).
Intuition behind Ag. To illustrate the intuition behind the weighted covariance matrix Ag, here we provide some brief heuristics. Let {( 0g,ti 5 (1,n))ken [)jk(]]) be i.i.d. samples such that (sk,hs ak.h) for some distribution over S x A and Sk PA PA (- 0n.n). Define
e₁ = Φ(8k,,, 0x.n.) (TP,, Vi+1 an - Vh+ 1 (sk,)) / (VA 1 Ar,1)
for all & E [K]. Note that e₃ are i.i.d zero-mean random vectors and a simple calculation yields Cov(ex) = [ V (sk,h - ( ar.A) 8k.hs (t.)),
This coincides with (2.6). Suppose Cov(ek) > O, then by the central limit theorem, holds that
K
e d N0, Cov(ex))
Therefore, Cov(en) equivalently A- can be seen as the Fisher information matrix asso- ciated with the weighted product of the Bellman error and the feature vectors. This is a tighter characterization of the convergence rate than bounding V, V by its naive upper bound (H h)

---

Theoretical Results
In this section, we introduce our main theoretical results and give an overview the proof technique.
4.1
OPE Error Bound
Our main result is a refined average-case OPE analysis that yields tighter error bound in Theorem 4.1. The proof is in Appendix D. To simplify the notation, we define:
Ch.2
H
1
Ch,3 = (II - h 1)²
C (IAAll - ||,,,,;)) '1)²2.
2
2
1=h
Theorem 4.1. Set X = 1. Under Assumptions 2.1, 2.3 and 2.5, if K satisfies
dH² K
K C C3 d²
log
(4.1)
where C' is some problem-indepentee universal constant and
Ch.3
h2
Hd
H²
Ch.3
CR.3
C3 = max
max NE(H]
max hE[H]
max
8
R²
1 x²
2
he(H] 4n
then with probability at least 1 - 8, the output of Algorithm 1 satisfies
log(16H/0)
16H 8
1
Jo - 05 sC.
V A
+C-Cr log
+
K
K3/4
K
where vT. = Er,, ( an) and C2 = MI-IVCO, Cn.2 -0,22
(H-h+1)d 41
log
dH²K
||
|
Theorem 4.1 suggests that Algorithm provably achieves a tighter instance-dependent error bound for OPE than that in [10]. In detail, the dominant term in our bound is O IIvill, as compared to the Ö - h + 1) D I/V/K term in [10]. By (2.5) and (2.6), our bound is at least as good as the latter since Σn. < [[H + 1)² + 1]An. More importantly, it instance-dependent and tight for the general class of linear MDPs: for those where V, 1et1 is close to its crude upper bound (H h + 1)2, our bound recovers the prior result. When V, V is small, VA-OPE benefits from incorporating the variance information and our bound gets tightened accordingly.
Remark 4.2. Note that we do not require Vn V (s, a) to be uniformly small for s, a, and h. From the bound and (2.6), as long as the variances are smaller than (Hf - h + 1)² on average of (s, a) E S x A and in sum of h. the bound is improved. It is also worth noting that the lower bound proved in [10] only holds for subclass of linear MDPs with V, V = S((H - h + 1)²), and thus their minimax-optimall refer the reader to Appendix B.
does not hold for general linear MDPs. For more detailed comparison
Remark 4.3. Conceptually, the term I| serves as a more precise characterization of the distribution shift between the behavior policy т and the target policy π in a variance-aware manner. This enables algorithm utilize the data more effectively. Compared with online RL where one can sample new data, OPE is more 'data-hungry': one cannot decide the overall quality of the data. Thus is especially beneficial to put more focus on targeted values with less uncertainty. This also the intuitive reason why our algorithm can achieve a tighter error bound.
4.2 Overview of the Proof Technique
Here we provide an overview of the proof for Theorem 4.1. Due to the parallel estimation of the value functions and their variances, the analysis of VA-OPE is much more challenging compared with that of FQI-OPE, As a result, we need to develop a novel proof technique. First, we have the following error decomposition.
7

---

Lemma 4.4. For any h E [H], let V be the output of Algorithm 1. Then it holds that
(T)(s) - - (s)
[ h+1 V% ( (s) A w
(4.2)
K Σ
1-16 (Vitz(6)) (5)) (s')
NR k.h Au.
where 4x, = PA Vh+ ( (k.n) ( - Ck, In particular, recall that 37 = E 81 ~ {i] and the OPE error can be decomposed as
ElV
/ (ViTi(s) 1 pan 1a (s)ds
h=1
Ou A
(4.3)
A=1
1=1
h=1
The OPE error bound (Theorem 4.1) is proved by bounding the three terms separately in (4.3). This decomposition is different from [10] in that Σ, is replaced by An. This prevents from adopting matrix embedding-tye proof as used in the prior work.
The key is to show the convergence of Å, to its population counterpart. However, by definition of Ån. to establish such a result, it first requires the convergence of V to Vi41 in a uniform manner, i.e., a high probability bound for supses (75() (s) Vi, (s)). . To show this, we leverage the decomposition in (4.2) and a backward induction technique, and prove a uniform convergence result which states that with high probability, for all h E [H], Algorithm can guarantee
V (s) - V (s) S
sup
VK
SES
This result is formalized as Theorem C.2 and proved in Appendix C. To the best of our knowledge, Theorem C.2 is the first to establish the uniform convergence of the estimation error for the value functions offline RL with linear function approximation. We believe this result is of independent interest and may be broadly useful in OPE.
Numerical Experiments
In this section, provide numerical experiments to evaluate algorithm VA-OPE, and compare it with FQI-OPE.
We construct linear MDP instance as follows. The MDP has |S| = 2 states and | = 100 actions, with the feature dimension and a E {1, ... 99} with probability 1 - and uniformly over {1. always chooses a 0 no matter which state is, making state 0 and 1 absorbing. The parameter p can be used to control the distribution shift between the behavior and target policies. Here p - 0 leads to small distribution shift, and p - leads to large distribution shift. The initial distribution &1 is uniform over (S). For more details about the construction of the linear MDP and parameter configuration, please refer to Appendix A.
10. The behavior policy then chooses action a with probability
99). The target policy
We compare the performance of the two algorithms on the synthetic MDP described above under different choices of horizon length H. We plot the log-scaled OPE error versus VK in Figure 1. It is clear that VA-OPE la), their performance is very comparable, which is as expected. As И increases, we can see from Figure la, lb and Ic that VA-OPE starts to dominate FQI-OPE, and the advantage is more significant for larger H, as suggested by Theorem 4.1. Due to space limit, comprehensive comparison under different parameter settings deferred Appendix
least as good FQI-OPE all the cases. Specifically, for small (Figure
6 Related Work
Off-policy evaluation. There is a large body of literature on OPE for tabular MDPs. Since the seminal work by Precup [34], various importance sampling- based estimators have been studied in

---

10
FQI-OPE VA-OPE
FQI-OPE VA-OPE
104
FQI-OPE
OPE Eiror
100
10
OPE Error
109
10
OPE
10"1
2.0
10-2
10
10
10
0
25
50
75 100125 125 150 275
25
50
75
100 150 1752000
25
50
75 100 150 200
<K
<
(a) H 5.
(b) H 10.
(c) 30.
Figure 1: Comparison of VA-OPE and FQI-OPE under different settings of horizon length H. VA-OPE's advantage becomes more significant as H increases, matching the theoretical predic- tion. The results are averaged over 50 trials and the error bars denote an empirical [10%.00] ]0%] confidence interval. The y-axis is log-scaled OPE error and x-axis is v K. For more details please see Appendix A.
the literature [26, 27, 39]. By using marginalized importance sampling methods [28, 45, 21, 47], one is able to further break the "curse-of-horizon" Moreover, various doubly robust estimators [11, 16, 12, 38, 49] have been developed to achieve variance reduction. Most recently, it is shown by Yin et al. [48] that uniform convergence over all possible policy is also achievable. However, all the aforementioned works are limited to tabular MDPs. There is also a notable line of work on the estimation of the stationary distribution ratio between the target policy and the behavior policy using a primal-dual formulation [30, 51, 8]. However, a theoretical guarantee for the OPE error is not given in the work. More recently, Chen et al. [7] studied OPE in the infinite-horizz setting with linear function approximation.
There are many others topics related to OPE, for example, policy gradient [20, 31, 2], conservative policy iteration [19], off-policy lemporal-difference learning [35], off-policy Q-learning [23], safe policy iteration [33] and pessimism in RL [22, 18), to mention few. We refer the reader to the excellent survey by Levine et [25] for more detailed introduction.
Online RL with linear function approximation. RL with function approximation has been ac- tively studied as an extension of the tabular setting. Yang and Wang [46] studied discounted linear MDPs with a generative model, and Jin al. [17] proposed an efficient LSVI algorithm for linear MDPs without a generative model. It has been shown by Du et al. [9] that MDP with misspecified linear function approximation could be exponentially hard leam. Linear MDPs under various settings have also been studied by [50, 32. 14, 44].
A parallel line of work studies linear mixture MDPs [15, 3, 533, 29] (a.k..., linear kernel MDPs [54]) where the transition kernel is a linear function a ternary feature mapping v/s S x A x S + Rd. In particular, Zhou al. [53] achieved nearly minimax regret bound by carefully utilizing the variance information of the value functions. Zhang et al. [52] constructed a variance-awar confidence set for humeehomogeneuus linear mixture MDPs. However, both works are focused on online RL rather than offline RL. It requires novel algorithm designs to exploit the variance information for offline tasks like OPE. What's more, the analysis in the offline setting deviates lot from that for online RL where one can easily apply the law of total variance to obtain tighter bounds.
7 Conclusion and Future Work
In this paper, we incorporate the variance information into OPE and propose VA-OPE, an algorithm that provably achieves tighter eтror bound. Our (v, A, (/)1////// error bound has a sharper dependence the distribution shift between the behavior policy and the target policy.
Our work suggests several promising future directions. Theoretically, remains open to provide an instance-dependen lower bound for the OPE error. Also, beyond the linear function approximation, interesting to establish similar results under more general function approximation schemes. Empirically, can we exploit the algorithmic insight of our algorithm to develop practically more

---

data-effectice OPE algorithms for complex real-world RL tasks? We wish to explore these directions the future.
Acknowledgments and Disclosure of o Funding
We thank Mengdi Wang and Yaqi Duan for helpful discussions during the preparation of the paper. We also thank the anonymous reviewers for their helpful comments. DZ and QG are partially supported by the National Science Foundation CAREER Award 1906169, IIS- 15--1901883 and AWS Machine Learning Research Award. The views and conclusions contained in this paper are those of the authors and should not be interpreted representing any funding agencies.
References
[1] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 14:2312-23221 2011.
[2] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. arXiv preprint arXiv:1908 00261, 2019.
[3] A. Ayoub, Z. Jia, C. Szepesvari, Wang, and L. Yang. Model-based reinforcement learning with
regression. In International Conference Machine Learning, pages 463-474, PMLR, 2020.
[4] F. Bertoluzzo and M. Corazza. Testing different reinforcement learning configurations for financial trading: Introduction and applications. Procedia Economics and Finance, 3:68-77, 2012.
[5] Q Cai, Z. Yang, C. Jin, and Z. Wang. Provably efficient exploration in policy optimization, In International Conference on Machine Learning, pages 1283-1294. PMLR, 2020.
[6] D. Charles, M. Chickering, and P. Simard. Counterfactual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 14, 2013.
[7] L. Chen, B. Scherrer, and P. L. Bartlett. Infinite-horizon offline reinforcement learning with linear function approximation: Curse of dimensionality and algorithm. arXiv preprint 10X1v:2103.09847, 2021.
[8] B. Dai, O. Nachum, Y. Chow, L. Li, C. Szepesvári, and D. Schuurmans. Coindice: Off-policy confidence interval estimation. In Advances in Neural Information Processing Systems, 2020.
[9] S. Du, S. M. Kakade, R. Wang, and L.. F. Yang. Is good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations, 2020.
[10] Y. Duan, Jia, and M. Wang. Minimax-optimal off-policy evaluation with linear function approximation. In International Conference on Machine Leurning, pages 2701-2709. PMLR, 2020.
[11] M. Dudík, J. Langford, and L. Li. Doubly robust policy evaluation and learning. In International Conference Machine Learning. PMLR, 2011.
[12] M. Farajtabar, Y. Chow, and M. Ghavamzadeh. More robust doubly robust off-policy evaluation. In International Conference on Machine Learning, pages 1447-1456. PMLR, 2018.
[13] D. A. Freedman. On tail probabilities for martingales. the Annals Probability, pages 100-118, 1975.
[14] J. He, D. Zhou, and Q. Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning. PMLR, 2021.
[15] Z. Jia, Yang, C. Szepesvari, and M. Wang. Model-based reinforcement learning with talgettargeted regression. In Learning for Dynamics and Control, pages 666-686. PMLR, 2020.
10

---

[16] N. Jiang and L. Li. Doubly robust off off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning. pages 652-661. PMLR, 2016.
[17] C. Jin, Z. Yang, Z. Wang, and M. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020.
[18] Y. Jin, Z. Yang, and Z. Wang. Is pessimism provably efficient for offline rl? arXiv preprint arXiv:2012.15083 2020.
[19] S. Kakade and J. Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
[20] S. M. Kakade, A natural policy gradient. In Advances in neural information processing systems, volume 14, 2001.
[21] N. Kallus and M. Uehara. Efficiently breaking the curse of horizon in off-policy evaluation with double reinforcement learning. arXiv preprint arXiv:190..05850 2019.
[22] R. Kidambi, A. Rajeswaran, P. Netrapalli, and T. Joachims. Morel: Model-based offline
reinforcement learning, arXiv preprini arXiv:2005.05955 2020.
[23] A. Kumar, J. Fu, G. Tucker, and S. Levine. Stabilizing off-policy q-learning via bootstrapping error reduction. In Advances Neural Information Processing Systems, volume 32, 2019.
[24] S. Lange, T. Gabel, and M. Riedmiller. Batch reinforcement learning. In Reinforcement learning, pages 45-73. Springer, 2012.
[25] S. Levine, A. Kumar, G. Tucker, and J. Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.0166 01643, 2020.
[26] L. Li, W. Chu, J. Langford, and X. Wang. Unbiased offline evaluation of contextual-bandic based news article recommendation algorithms. In Proceedings of the fourth ACM international conference on Web search and data mining, pages 297-306, 2011.
[27] L. R. Munos, and C. Szepesvári. Toward minimax off- off-policy value estimation. In Artificial Intelligence and Statistics, pages 606-616. PMLR, 2015.
[28] Q. Liu, L. Li, Z. Tang, and D. Zhou. Breaking the curse of horizon: Infinite-horizon off-policy estimation. In Advances in Neural Information Processing Systems, volume 31, 2018.
[29] Y. Min, J. He, T. Wang, and Q Gu. Learning stochastic shortest path with linear function approximation. arXiv preprint arXiv:2/ 12727, 2021.
[30] O. Nachum, Y. Chow, Dai, and L. Li. Dualdice: Behavior aggossic estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems, volume 32, pages 2318-2328. Curran Associates, Inc., 2019.
[31] O. Nachum, B. Dai, Kostrikov, Y. Chow, L. Li, and D. Schuurmans. Algaedice: Policy gradient from arbitrary experience. arXiv preprint arXiv:1912.02074 2019.
[32] G. Neu and C. Pike-Burke. A unifying view of optimism in episodic reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
[33] M. Pirotta, M. Restelli, A. Pecorino, and D. Calandriello. Safe policy iteration. In International Conference on Machine Learning, pages 307-315. PMIRR, 2013.
[34] D. Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
[35] D. Precup. R. S. Sutton, and S. Dasgupta. Off-policy lemporal-differene learning with function approximation. International Conference on Machine Learning, pages 417-424, 2001.
[36] D. Quillen, E. Jang, O. Nachum, C. Finn, J. Ibarz, and S. Levine. Deep reinforcement learning for bbaedd robotic grasping: A simulated comparative evaluation of off-polic methods. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 6291. IEEE, 2018
11

---

[37] L. Tang, R. Rosales, A. Singh, and D. Agarwal. Automatic ad format selection via contextual bandits. Proceedings of the 22nd ACM international conference on Information & Knowledge Management, pages 1587-1594, 2013.
[38] Z. Tang, Y. Feng. L. Li, D. Zhou, and Q. Liu. Doubly robust bias reduction in infinite horizon off off-policy estimation. In International Conference Learning Representations, 2020.
[39] P. Thomas and E. Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference on Machine Learning, pages 21339-2148. PMLR, 2016.
[40] P. S. Thomas, G. Theocharous, M. Ghavamzadeh, I. Durugkar, and E. Brunskill. Predictive off-policy policy evaluation for nonstationary decision problems, with applications to digital marketing. In AAAI, pages 4740-4745, 2017.
[41] J. A. Tropp. Uriendry tail bounds for sums of random matrices. Foundations of computa- tional mathematics, 12(4):389-434 2012.
[42] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027 2010.
[43] R. Wang, Y. Wu, R. Salakhutdinov, and S. M. Kakade. Instabilities of offline rl with pre-trained neural representation. In International Conference on Machine Learning. PMLR, 2021.
[44] T. Wang, D. Zhou, and Q. Gu. Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. In Advances in Neural Information Processing Systems, 2021.
[45] T. Xie, Y. Ma, and Y.-X. Wang. Towards optimal off- policy evaluation for reinforcement learning with marginalized importance sampling. In Advances in Neural Information Processing Systems, volume 32, 2019.
[46] L. Yang and M. Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004, 2019.
[47] M. Yin and Y.-X. Wang. Asymptotically efficient off-policy evaluation for tabular reinforcement learning. In International Conference Artificial Intelligence and Statistics, pages 3948-3955 PMLR, 2020.
[48] M. Yin, Y. Bai, and Y.-X. Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 1567-1575. PMLR, 2021.
[49] M. Yin, Y. Bai, and Y.-X. Wang. Near-optimal offline reinforcement learning via double variance reduction. Advances in Neural Information Processing Systems, 2021.
[50] A. Zanette, A. Lazaric, M. Kochenderfer, and E. Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978-10989. PMLR, 2020.
[51] R. Zhang, B. Dai, L. Li, and D. Schuurmans. Gendice: Generalized offline estimation of stationary values. In International Conference on Learning Representations, 2020.
[52] Z. Zhang, J. Yang, X. Ji, and S. S. Du. Variance-awar confidence set: Muriance-dependee bound for linear bandits and horizon-free bound for linear mixture mdp. arXiv preprint arXiv:2101.1 12744 2021.
[53] D. Zhou, Q Gu, and C. Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference Learning Theory. PMLR, 2021.
[54] D. Zhou, J. He, and Q. Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning. PMLR, 2021.
12

---

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


Reviews:
[{"review_id": "wyYmoR_QmDS", "reviewer": "Reviewer_c9Y4", "summary": "The variance-aware OPE method uses the estimated variance of the value function to reweight the Bellman residual in Fitted Q-Iteration. It shows that the algorithm achieves a tighter error bound than the best-known result.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "It is a really good paper with high quality. Especially, such a variance-aware structure helps people to understand what is essential in the linear MDP model and improves over the existing Duan et al. in a non-trivial way (from the statistical sense). The use of two folds of data to estimate $\\widehat{\\sigma}$ is neat and the fisher information interpretation for $\\Lambda^{-1}$ is appropriate. I think it makes a very good contribution to the OPE community for the purpose of understanding instance-optimal / problem-dependent RL.\n\nOnly one small concern: it would be better if $s_{k, h}^{\\prime} \\neq s_{k, h+1}$ can be got rid of (especially Yin et al. does not really use this, their data is coming in a sequential way). But I can understand the authors since without this the analysis could be nasty due to the data dependence within the episodes. \n\nAn additional comment: since your bound include the variance structure, in the special case of tabular MDP, could your result match the dominate term in Yin & Wang 20 (square root of their MSE bound)? It would interesting if your result can achieve that since their bound is statistically optimal (matching the Cramer-Rao lower bound) for tabular RL.  \n\nThis is within one of the best in my batch therefore I will choose my score as acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15 Hours"}, "extra_text": {}}, {"review_id": "nppUzMhXosr", "reviewer": "Reviewer_7eNH", "summary": "This paper proposes a new off-policy evaluation (OPE) algorithm in the finite horizon MDP setting. The reviewer finds the new results are sightly incremental compared with the existing results and thus suggests not accepting the paper.", "questions": "", "limitations": "", "rating": 6, "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": "This paper proposes a new off-policy evaluation (OPE) algorithm in the finite horizon MDP setting. Compared with the regular LSVI-type algorithm, the proposed algorithm involves an extra estimation step on the variance of the next-step state value and uses it to reweight the sample in the least-square regression for estimating value functions. The theoretical analysis shows that the leading term of the OPE error bound now depends on the weighted coverage matrix rather than the original coverage matrix.\n\nMy main concern is that the new theoretical result is, most of the time, equal to the previous result, while it is hard to say that it can be better than the original results with regard to the order of H. This is because the variance $\\sigma(s, a)$ in average is just of order H. There might be certain state-action pairs having close-zero state-action values or having a deterministic transition distribution to the next state, but the difference showing up in the new error bound is not clearly an improvement since it does not change the order and the constants can not be directly compared.", "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": "TDER4geAJHE", "reviewer": "Reviewer_ASrb", "summary": "This paper studies the off-policy evaluation (OPE) problem in reinforcement learning with linear function approximation. They propose to incorporate the variance information of the value function to improve the sample efficiency of OPE. This has better theoretical properties.", "questions": "", "limitations": "", "rating": 6, "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": "1.As for the final variance estimator \\hat{\\sigma}_h, why use a mechanism similar to clip? And using it, we can get \\hat{\\sigma}_h>1, this is very different from variance. so what is the motivation to set such range?\n2. The paper said \"Theorem 4.1 suggests that Algorithm 1 provably achieves a tighter instance-dependent error bound for OPE than that in [10].\"  But from formula (B.1), the dominant term in error bound is not better than [10]. And What about the rest of error bound?\n3. in experiments, From Fig.1. ,  the variance of the proposed methods is very large. In general, the larger the variance, the more unstable the OPE error.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "32CjcSHzP6L", "reviewer": "Reviewer_PGyL", "summary": "The paper focuses on OPE for linear MDPS in an offline setup. The proposed algorithm accounts for the value-function variance in the dataset, and bounds the resulting value error as a function of that variance.", "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": "The paper is written fairly well, though there are several grammar errors or typos. As an example, line 85: \"there exists \\gamma_h and \\mu_h...\". Nonetheless, I appreciate the idea of using the variance to improve data efficiency. The results seem like they make sense. But, specifically, I have the following several questions to the authors:\n1. Why exactly do you split the data? In Sec. 2 you suggest this would be explained in Sec. 3, but I didn't find such an explanation.\n2. The expectation of the weighted covariance matrix in (2.6) is taken w.r.t. \\tilde{\\pi}. If I understand correctly, it means that directly using the data to estimate it is straightforward. However, the variance inside that equation is taken w.r.t. \\pi. How is that done? I can't find a place in the text or algorithm which show how you reweigh the variance to match the target distribution.\n3. I don't understand how the norm in Remark 4.3 characterizes the distribution shift. I guess this relates to my previous question. \n\nAfter I understand the answers to the above questions I can decide whether I think this paper should be published or not. In other words, I'm open to change my score either positively or negatively. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Irrelevant. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies off-policy evaluation in linear MDPs. The authors extend the FQI work of [10] by reweighing the Bellman residual by an estimate of the value function variance. This slightly improves the instance-dependent sample efficiency, by up to a factor of H.
The paper is fairly incremental compared to [10] and of somewhat limited scope, but executed well overall to warrant acceptance.

Decision: Accept (Poster)