Variance-Aware Off-Policy Evaluation with 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, 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.

heading: 1 Introduction
text: Reinforcement learning (RL) has been a 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 to maximize the long-term cumulative rewards. In contrast to 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 use this information to learn the optimal policy. There has been much empirical success of offline RL in various application domains [4, 6, 37, 40, 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 on OPE are in the setting of tabular MDPs [34, 26, 11, 16, 45, 47–49], where the state space S and the action space A are both finite. However, real-world applications often have high-dimensional or even infinite-dimensional state and action spaces, where function 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 et al. [10]. More specifically, Duan et al. [10] analyzed a regression-based ∗Equal contribution.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Fitted Q-Iteration method (FQI-OPE) that achieves an Õ(H2 √
(1 + d(π, π̄))/N) error 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 is nearly minimax optimal. However, as we will show later, the H2 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 a 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-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̃( ∑ h(v > h Λ −1 h vh) 1/2/ √ K) policy evaluation error, where
vh is the expectation of the feature vectors under target policy and Λh is the uncentered covariance matrix under behavior policy weighted by the conditional variance of the value function. Our algorithm achieves a 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.
• Our analysis is based on a novel two-step proof technique. In the first step, we use backward induction to establish worst-case uniform convergence2 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 in a backward and iterated fashion. The analyses in both steps might be of independent interest.
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 ∈ Rd and any positive semi-definite matrix Σ ∈ Rd×d, we denote by ‖x‖2 the Euclidean norm and ‖Σ‖ the operator norm, and define ‖x‖Σ = √ x>Σx. For any positive integer n, we denote by [n] the set {1, . . . , n}. For any finite set A, we denote by |A| the cardinality of A. For two sequences {an} and {bn}, we write an = O(bn) if there exists an absolute constant C such that an ≤ Cbn, and we write an = Ω(bn) if there exists an absolute constant C such that an ≥ Cbn. We use Õ(·) to further hide the logarithmic factors.

heading: 2 Preliminaries

heading: 2.1 Markov Decision Processes
text: We consider the time-inhomogeneous episodic Markov Decision Process (MDP), which is represented by a tuple M(S,A, H, {rh}Hh=1, {Ph}Hh=1). 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], rh : S × A → [0, 1] is the reward function, and Ph(s′|s, a) is the transition probability function which represents the probability for state s to transit to state s′ given action a. A policy π consists of H mappings {πh}Hh=1 from S to the simplex on A, such that for any (h, s) ∈ [H]× S, πh(·|s) is a probability distribution over A. Here a policy can be either deterministic (point mass) or stochastic.
2By 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 Qπh(s, a) and value function V π h (s) at each stage h ∈ [H] as follows:
Qπh(s, a) = Eπ [ H∑ i=h ri(si, ai) ∣∣∣∣sh = s, ah = a], V πh (s) = ∫ A Qπh(s, a)dπh(a|s), (2.1)
where ai ∼ πi(·|si) and si+1 ∼ Pi(·|si, ai). For any function V : S → R, we introduce the following shorthand notation for the conditional expectation and variance of V :
[PhV ](s, a) = Es′∼Ph(·|s,a)[V (s ′)], [VhV ](s, a) = [PhV 2](s, a)− ([PhV ](s, a))2. (2.2)
Time-inhomogeneous linear MDPs. We consider a 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. Assumption 2.1. M(S,A, H, {rh}Hh=1, {Ph}Hh=1) is called a linear MDP with a known feature mapping φ : S × A → Rd, if for any h ∈ [H], there exist γh and µh ∈ Rd, such that for any state-action pair (s, a) ∈ S ×A, it holds that
Ph(· | s, a) = 〈φ(s, a),µh(·)〉, rh(s, a) = 〈φ(s, a),γh〉. (2.3) We assume that at any stage h, for any state-action pair (s, a) ∈ S ×A, the reward received by the agent is given by r = rh(s, a) + h(s, a), where rh(s, a) ∈ [0, 1] is the expected reward and h(s, 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 ‖γh‖2 ≤ 1 and ‖φ(s, a)‖2 ≤ 1 for all (s, a) ∈ S × A. We also assume that rh(s, a) + h(s, a) ≤ 1, | h(s, a)| ≤ 1 almost surely and thus Var( h(s, a)) ≤ 1 for all h ∈ [H] and (s, a) ∈ S ×A. Moreover, we assume that maxh∈[H] ∥∥∫ S f(s)dµh(s) ∥∥ 2 ≤ √ d for all bounded function f : S → R such that sups∈S |f(s)| ≤ 1.
The above assumption on linear MDPs implies the following proposition for the action-value functions. Proposition 2.2 (Proposition 2.3, [17]). For a linear MDP, for any policy π, there exist weights {wπh , h ∈ [H]} such that for any (s, a, h) ∈ S × A × [H], we have Qπh(s, a) = 〈φ(s, a),wπh〉. Moreover, we have ‖wπh‖2 ≤ 2H √ d for all h ∈ [H].
Following this proposition, we may further show that the value functions are also linear functions, but of different features. We define φπh(s) = ∫ A φ(s, a)dπh(a|s) for all s ∈ [S] and h ∈ [H]. Then by (2.1) we have
V πh (s) = ∫ A φ(s, a)>wπhdπ(a|s) = 〈φπh(s),wπh〉.

heading: 2.2 Off-policy Evaluation
text: The purpose of OPE is to evaluate a (known) target policy π 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 a fixed initial distribution ξ1, i.e., vπ1 = Es∼ξ1 [V π1 (s)]. To faciliate the presentation, we further introduce some important notations. For all h ∈ [H], let νh be the occupancy measure over S ×A at stage h induced by the transition P and the behavior policy π̄, that is, for any E ⊆ S ×A,
νh(E) = E [(sh, ah) ∈ E | s1 ∼ ξ1, ai ∼ π̄(·|si), si+1 ∼ Pi(·|si, ai), 1 ≤ i ≤ h] . (2.4) For simplicity, we write Eh[f(s, a)] = Eπ̄,h[f(s, a)] = ∫ S×A f(s, a)dνh(s, a) for any function f on S ×A. Similarly, we use Eπ,h[f(s, a)] to denote the expectation of f 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 ∈ [H]:
Σh = Eπ̄,h [ φ(s, a)φ(s, a)> ] . (2.5)
Intuitively, these matrices measure the coverage of the offline data in the state-action space. It is known that the success of OPE necessitates a good coverage [10, 43]. Therefore here we make the same coverage assumption on the offline data.
Assumption 2.3 (Coverage). For all h ∈ [H], κh := λmin(Σh) > 0. Denote κ = minh∈[H] κh.
A key difference in our result is that, instead of depending on Σh directly, the error bound depends on the following weighted version of the covariance matrices defined as
Λh := Eπ̄,h [ σh(s, a) −2φ(s, a)φ(s, a)> ] , (2.6)
for all h ∈ [H], where each σh : S ×A → R is defined as σh(s, a) := √ max{1,VhV πh+1(s, a)}+ 1. (2.7)
Note that in the definition of σh(·, ·), taking the maximum and adding an extra 1 is purely for technical reason and is related to its estimator σ̂h(·, ·), which we will introduce and explain later in Section 3.2. In general, one can think of σ2h(s, a) ≈ VhV πh+1(s, a). Therefore, compared with the raw covariance matrix Σh, Λh further incorporates the variance of the value functions under the target policy. This is the key to obtaining a tighter instance-dependent error bound.
Definition 2.4 (Variance-aware coverage). We define ιh := λmin(Λh) and ι = minh∈[H] ιh.
Since sup(s,a)∈S×A σh(s, a) 2 is bounded from above, by (2.6) and Assumption 2.3, we immediately have ιh ≥ κh/[sup(s,a)∈S×A σh(s, a)2] > 0 for all h ∈ [H], and thus ι > 0. Even if Assumption 2.3 does not hold, we can always restrict to the subspace span{φ(sh, ah)}. For convenience of presentation, we make Assumption 2.3 in 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 = {Dh}h∈[H] and Ď = {Ďh}h∈[H]. For the dataset D, we assume Dh1 is independent of Dh2 for h1 6= h2. For each stage h, we have Dh = {(sk,h, ak,h, rk,h, s′k,h)}k∈[K], where we assume for each k ∈ [K], the data point (sk,h, ak,h, rk,h, s ′ k,h) is sampled identically and independently in the following way: (sk,h, ak,h) ∼ νh(·, ·) where νh(·, ·) is the occupancy measure defined in (2.4), and s′k,h ∼ Ph(·|sk,h, ak,h). The same holds for Ď, and we write Ďh = {(šk,h, ǎk,h, řk,h, š′k,h)}k∈[K]. Note that here s′k,h 6= sk,h+1.
Assumptions 2.5 is standard in the offline RL literature [48, 10]. Note that in the assumption, there is a data splitting, i.e., one can view it as the whole dataset D ∪ Ď being split into two halves. The datasets D and Ď will then be used for two different purposes in Algorithm 1 as will be made clear in the next section. We would like to remark that the only purpose of the splitting is to avoid a lengthy analysis. There is no need to perform the data splitting in practice. Also, in our implementation and experiments, we do not split the data.

heading: 3 Algorithm
text: To ease the notation, we denote φk,h = φ(sk,h, ak,h), φ̌k,h = φ(šk,h, ǎk,h), σ̂k,h = σ̂h(sk,h, ak,h) and rk,h = rh(sk,h, ak,h) + k,h for all (h, k) ∈ [H] × [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.

heading: 3.1 Regression-Based Value Function Estimation
text: By Proposition 2.2, it suffices to estimate the vectors {wπh , h ∈ [H]}. A popular approach is to apply the Least-Square Value Iteration (LSVI) [17] which relies on the Bellman equation, Qπh(s, a) = rh(s, a) + [PhV πh+1](s, a), that holds for all h ∈ [H] and (s, a) ∈ S × A. By viewing V πh+1(s′k,h) as an unbiased estimate of [PhV πh+1](sk,h, ak,h), the idea of the LSVI-type method is to solve the following ridge regression problem:
ŵπh := argmin w∈Rd λ‖w‖22 + K∑ k=1 [ 〈φk,h,w〉 − rk,h − V πh+1(s′k,h) ]2 , (3.1)
for some regularization parameter λ > 0. Since we do not know the exact values of V πh+1 in (3.1), we replace it by an estimator V̂ πh+1, and then recursively solve the lease-square problem in a backward manner, which enjoys a closed-form solution as follows
ŵπh = [ K∑ k=1 φk,hφ > k,h + λId ]−1 K∑ k=1 φk,h [ rk,h + V̂ π h+1(s ′ k,h) ] .
This has been used in the LSVI-UCB 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∑ k=1 φk,hφ > k,h + λId ]−1 K∑ k=1 φk,h ( [PhV̂ πh+1](sk,h, ak,h)− V̂ πh+1(s′k,h) ) .
Jin et al. [17] applied a Hoeffding-type inequality to bound the Bellman error. Although Duan et al. [10] applied Freedman’s inequality in 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.e., VhV πh+1 ≤ (H − h)2, which simply comes from sups∈S V π h+1(s) ≤ H − h. Therefore, it prevents [10] from getting a 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-OPE degrades for large H . This motivates us to utilize the variance information in the data for OPE.

heading: 3.2 The Proposed Algorithm
text: In particular, we present our main algorithm as 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 ŵπh+1 be the estimate of wπh+1 computed at the previous step, and correspondingly V̂ πh+1(·) = 〈φπh+1(·), ŵπh+1〉. Instead of the ordinary ridge regression (3.1), we consider the following weighted ridge regression:
ŵπh := argmin w∈Rd λ‖w‖22 + K∑ k=1 [ 〈φk,h,w〉 − rk,h − V̂ πh+1(s′k,h) ]2 / σ̂2k,h, (3.2)
where σ̂k,h = σ̂h(sk,h, ak,h) for all (h, k) ∈ [H] × [K] with σ̂h(·, ·) being a proper estimate of σh(·, ·) defined in (2.7). We then have the following closed-form solution (Line 9 and 7 of Alg. 1):
ŵπh = Λ̂ −1 h K∑ k=1 φk,h ( rk,h + V̂ π h+1(s ′ k,h) )/ σ̂2k,h, with Λ̂h = K∑ k=1 σ̂−2k,hφk,hφ > k,h + λId. (3.3)
In the above estimator, we use the dataset D to estimate the value functions. Next, we apply an LSVI-type method to estimate σh using the dataset Ď.
Variance estimator. By (2.2), we can write [VhV πh+1](s, a) =[Ph(V πh+1)2](s, a)− ( [PhV πh+1](s, a) )2 . (3.4)
For the first term in (3.4), by Assumption 2.1 we have [Ph(V πh+1)2](s, a) = ∫ S V πh+1(s ′)2dPh(s′|s, a) = φ(s, a)> ∫ S V πh+1(s ′)2 dµh(s′),
which suggests that Ph(V πh+1)2 also has a linear representation. Thus we adopt a linear estimator 〈φ(s, a), β̂πh〉 where β̂πh (Line 4) is the solution to the following ridge regression problem:
β̂πh = argmin β∈Rd K∑ k=1 [〈 φ̌k,h,β 〉 − [V̂ πh+1]2(š′k,h) ]2 + λ‖β‖22 = Σ̂−1h K∑ k=1 φ̌k,hV̂ π h+1(š ′ k,h) 2. (3.5)
Algorithm 1 Variance-Aware Off-Policy Evaluation (VA-OPE) 1: Input: target policy π = {πh}h∈[H], datasets D = {{(sk,h, ak,h, rk,h, s′k,h)}h∈[H]}k∈[K] and Ď = {{(šk,h, ǎk,h, řk,h, š′k,h)}h∈[H]}k∈[K], initial distribution ξ1, ŵπH+1 = 0
2: for h = H,H − 1, . . . , 1 do 3: Σ̂h ← ∑K k=1 φ̌k,hφ̌ > k,h + λId
4: β̂h ← Σ̂−1h ∑K k=1 φ̌k,hV̂ π h+1(š ′ k,h) 2
5: θ̂h ← Σ̂−1h ∑K k=1 φ̌k,hV̂ π h+1(š ′ k,h)
6: σ̂h(·, ·)← √
max{1, V̂hV̂ πh+1(·, ·)}+ 1 7: Λ̂h ← ∑K k=1 φk,hφ > k,h/σ̂ 2 k,h + λId 8: Yk,h ← rk,h + 〈φπh(s′k,h), ŵπh+1〉 9: ŵπh ← Λ̂ −1 h ∑K k=1 φk,hYk,h/σ̂ 2 k,h
10: Q̂πh(·, ·)← 〈φ(·, ·), ŵπh〉, V̂ πh (·)← 〈φπh(·), ŵπh〉 11: end for 12: Output: v̂π1 ← ∫ S V̂ π 1 (s) dξ1(s)
Similarly, we estimate the second term in (3.4) by 〈φ(s, a), θ̂πh〉, where θ̂πh (Line 5) is given by
θ̂h = argmin θ∈Rd K∑ k=1 [〈 φ̌k,h,θ 〉 − V̂ πh+1(š′k,h) ]2 + λ‖θ‖22 = Σ̂−1h K∑ k=1 φ̌k,hV̂ π h+1(š ′ k,h), (3.6)
with Σ̂h = ∑K k=1 φ̌k,hφ̌ > k,h + λId. Combining (3.5) and (3.6), we estimate VhV πh+1 by
[V̂hV̂ πh+1](·, ·) = 〈φ(·, ·), β̂πh〉[0,(H−h+1)2] − [ 〈φ(·, ·), θ̂πh〉[0,H−h+1] ]2 , (3.7)
where the subscript [0, (H − h+ 1)2] denotes the clipping into the given range, and similar for the subscript [0, H − h+ 1]. We do such clipping due to the fact that V πh+1 ∈ [0, H − h]. We add 1 to deal with the approximation error in V̂ πh+1.
Based on V̂hV̂ πh+1, the final variance estimator σ̂h(·, ·) (Line 6) is defined as σ̂h(·, ·) = √ max{1, V̂hV̂ πh+1(·, ·)}+ 1.
In order to deal with the situation where V̂hV̂ πh+1 < 0 or is very close to 0, we take maximum between V̂hV̂ πh+1 and 1. Also, to account for the noise in the observed rewards, we add an extra 1 which is an upper bound of the noise variance by Assumption 2.1.
Final estimator. Recursively repeat the above procedure for h = H,H − 1, . . . , 1, and we obtain V̂1. Then the final estimator for vπ1 (Line 12) is defined as v̂ π 1 = ∫ S V̂ π 1 (s) dξ1(s).
Intuition behind Λh. To illustrate the intuition behind the weighted covariance matrix Λh, here we provide some brief heuristics. Let {(sk,h, ak,h, s′k,h)}k∈[K] be i.i.d. samples such that (sk,h, ak,h) ∼ ν for some distribution ν over S ×A and s′k,h ∼ Ph(·|sk,h, ak,h). Define
ek = φ(sk,h, ak,h) ( [PhV πh+1](sk,h, ak,h)− V πh+1(s′k,h) ) / [VhV πh+1](sk,h, ak,h)2
for all k ∈ [K]. Note that ek’s are i.i.d zero-mean random vectors and a simple calculation yields Cov(ek) = E [ [VhV πh+1](sk,h, ak,h)−2φ(sk,h, ak,h)φ(sk,h, ak,h)> ] .
This coincides with (2.6). Suppose Cov(ek) 0, then by the central limit theorem, it holds that
1√ K K∑ k=1 ek d−→ N (0,Cov(ek)).
Therefore, Cov(ek)−1, or equivalently Λ−1h , can be seen as the Fisher information matrix associated with the weighted product of the Bellman error and the feature vectors. This is a tighter characterization of the convergence rate than bounding VhV πh+1 by its naive upper bound (H − h)2.

heading: 4 Theoretical Results
text: In this section, we introduce our main theoretical results and give an overview of the proof technique.

heading: 4.1 OPE Error Bound
text: Our main result is a refined average-case OPE analysis that yields a tighter error bound in Theorem 4.1. The proof is in Appendix D. To simplify the notation, we define:
Ch,2 = H∑ i=h H − h+ 1√ 2ιh , Ch,3 = (H − h+ 1)2 2 , Ch,4 = ( ‖Λh‖ · ‖Λ−1h ‖ )1/2 .
Theorem 4.1. Set λ = 1. Under Assumptions 2.1, 2.3 and 2.5, if K satisfies
K ≥ C · C3 · d2 [ log ( dH2K
κδ
)]2 , (4.1)
where C is some problem-independent universal constant and
C3 := max { max h∈[H] Ch,3 · C2h,2 8ι2h , H4 κ2 , H2 κ2 · max h∈[H] Ch,3 2 · max h∈[H] Ch,3 ιh } ,
then with probability at least 1− δ, the output of Algorithm 1 satisfies
|vπ1 − v̂π1 | ≤C · [ H∑ h=1 ‖vπh‖Λ−1h ] · √ log(16H/δ) K + C · C4 · log ( 16H δ ) · ( 1 K3/4 + 1 K ) ,
where vπh := Eπ,h[φ(sh, ah)] and C4 := ∑H h=1 √ Ch,4 · Ch,2 · (H−h+1)d4ιh · log ( dH2K κδ ) · ‖vπh‖Λ−1h .
Theorem 4.1 suggests that Algorithm 1 provably achieves a tighter instance-dependent error bound for OPE than that in [10]. In detail, the dominant term in our bound is Õ( ∑H h=1 ‖vπh‖Λ−1h / √ K),
as compared to the Õ( ∑H h=1(H − h + 1)‖vπh‖Σ−1h / √ K) term in [10]. By (2.5) and (2.6), our bound is at least as good as the latter since Σh [(H − h + 1)2 + 1]Λh. More importantly, it is instance-dependent and tight for the general class of linear MDPs: for those where VhV πh+1 is close to its crude upper bound (H − h+ 1)2, our bound recovers the prior result. When VhV πh+1 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 VhV πh+1(s, a) to be uniformly small for all s, a, and h. From the bound and (2.6), as long as the variances are smaller than (H − h + 1)2 on average of (s, a) ∈ S ×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 a subclass of linear MDPs with VhV πh+1 = Ω((H − h+ 1)2), and thus their minimax-optimality does not hold for general linear MDPs. For more detailed comparison we refer the reader to Appendix B.
Remark 4.3. Conceptually, the term ‖vπh‖Λ−1h 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 our algorithm to 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 it is especially beneficial to put more focus on targeted values with less uncertainty. This is also the intuitive reason why our algorithm can achieve a tighter error bound.

heading: 4.2 Overview of the Proof Technique
text: Here we provide an overview of the proof for Theorem 4.1. Due to the parallel estimation of the 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.
Lemma 4.4. For any h ∈ [H], let V̂ πh be the output of Algorithm 1. Then it holds that V πh (s)− V̂ πh (s) = ∫ A [Ph(V πh+1 − V̂ πh+1)](s, a)dπh(a|s) + λφπh(s)>Λ̂−1h w π h (4.2)
+ φπh(s) >Λ̂−1h [ −λ ∫ S ( V πh+1(s ′)− V̂ πh+1(s′) ) dµh(s′) + K∑ k=1 φk,hσ̂ −2 k,h∆k,h ] ,
where ∆k,h = [PhV̂ πh+1](sk,h, ak,h)− V̂ πh+1(s′k,h)− k,h. In particular, recall that v̂π1 = E[V̂ π1 (s1) | s1 ∼ ξ1] and the OPE error can be decomposed as
vπ1 − v̂π1 =− λ H∑ h=1 (vπh) >Λ̂−1h ∫ S ( V πh+1(s)− V̂ πh+1(s) ) µh(s)ds
+ H∑ h=1 (vπh) >Λ̂−1h K∑ k=1 φk,hσ̂ −2 k,h∆k,h + λ H∑ h=1 (vπh) >Λ̂−1h w π h . (4.3)
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 Σ̂h is replaced by Λ̂h. This prevents us from adopting a matrix embedding-type proof as used in the prior work.
The key is to show the convergence of Λ̂h to its population counterpart. However, by definition of Λ̂h, to establish such a result, it first requires the convergence of V̂ πh+1 to V π h+1 in a uniform manner, i.e., a high probability bound for sups∈S |V̂ πh (s)− V πh (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 ∈ [H], Algorithm 1 can guarantee
sup s∈S ∣∣∣V̂ πh (s)− V πh (s)∣∣∣ ≤ Õ( 1√ K ) .
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 in offline RL with linear function approximation. We believe this result is of independent interest and may be broadly useful in OPE.

heading: 5 Numerical Experiments
text: In this section, we provide numerical experiments to evaluate our algorithm VA-OPE, and compare it with FQI-OPE.
We construct a linear MDP instance as follows. The MDP has |S| = 2 states and |A| = 100 actions, with the feature dimension d = 10. The behavior policy then chooses action a = 0 with probability p and a ∈ {1, · · · , 99} with probability 1− p and uniformly over {1, · · · , 99}. The target policy π always chooses a = 0 no matter which state it 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→ 1 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.
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 √ K in Figure 1. It is clear that VA-OPE is at least as good as FQI-OPE in all the cases. Specifically, for small H (Figure 1a), their performance is very comparable, which is as expected. As H increases, we can see from Figure 1a, 1b and 1c 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, a comprehensive comparison under different parameter settings is deferred to Appendix A.

heading: 6 Related Work
text: 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
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-horizon 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 temporal-difference learning [35], off-policy Q-learning [23], safe policy iteration [33] and pessimism in RL [22, 18], to mention a few. We refer the reader to the excellent survey by Levine et al. [25] for a more detailed introduction.
Online RL with linear function approximation. RL with function approximation has been actively studied as an extension of the tabular setting. Yang and Wang [46] studied discounted linear MDPs with a generative model, and Jin et al. [17] proposed an efficient LSVI-UCB 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 to learn. 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, 5, 53, 29] (a.k.a., linear kernel MDPs [54]) where the transition kernel is a linear function of a ternary feature mapping ψ : S ×A×S → Rd. In particular, Zhou et al. [53] achieved a nearly minimax regret bound by carefully utilizing the variance information of the value functions. Zhang et al. [52] constructed a variance-aware confidence set for time-homogeneous 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 a lot from that for online RL where one can easily apply the law of total variance to obtain tighter bounds.

heading: 7 Conclusion and Future Work
text: In this paper, we incorporate the variance information into OPE and propose VA-OPE, an algorithm that provably achieves tighter error bound. Our Õ( ∑ h(v > h Λ −1 h vh) 1/2/ √ K) error bound has a sharper dependence on the distribution shift between the behavior policy and the target policy.
Our work suggests several promising future directions. Theoretically, it remains open to provide an instance-dependent lower bound for the OPE error. Also, beyond the linear function approximation, it is 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-effective OPE algorithms for complex real-world RL tasks? We wish to explore these directions in the future.
Acknowledgments and Disclosure of 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-1904183 and AWS Machine Learning Research Award. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.

Review summaries:
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.