summaries: 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.   The paper consider off-policy evaluation using linear function approximation under unrealizability setting. Under such more relaxed assumption, they provide characterization of the linear direct method(DM) as an error governed by two approximation residual $\mathcal{R}_B$ and $\mathcal{R}_X$, $$     \hat{J}(\pi) - J(\pi) = \mathbb{E}[\mathcal{R}_B(s,a)\mathcal{R}_X(s,a)] + O(1/\sqrt{n}), $$ with $\mathcal{R}_B$ corresponding to Bellman residual and  $\mathcal{R}_X$ corresponding to residual of marginal density ratio. Leveraing this result, they establish a nonparametric tile-coding estimators  to solve the unrealizability though with a slower convergence. 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. 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.   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).
abstractText: We consider the problem of offline policy evaluation (OPE) with Markov decision processes (MDPs), where the goal is to estimate the utility of given decisionmaking 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.
authors.name: Kohei Miyaguchi
references.authors: P. Amortila N. Jiang T. Xie
references.title: A variant of the wang-foster-kakade lower bound for the discounted setting
references.venue: arXiv preprint arXiv:2011.01075
references.authors: R.C. Bradley
references.title: Basic properties of strong mixing conditions. a survey and some open questions
references.venue: arXiv preprint math/0511078
references.authors: Y. Duan Z. Jia M. Wang
references.title: Minimax-optimal off-policy evaluation with linear function approximation
references.venue: In International Conference on Machine Learning,
references.authors: M. Dudík J. Langford L. Li
references.title: Doubly robust policy evaluation and learning. arXiv preprint arXiv:1103.4601
references.authors: Y. Feng L. Li Q. Liu
references.title: A kernel loss for solving the bellman equation
references.venue: arXiv preprint arXiv:1905.10506
references.authors: Y. Feng T. Ren Z. Tang Q. Liu
references.title: Accountable off-policy evaluation with kernel bellman statistics
references.venue: In International Conference on Machine Learning,
references.authors: D.A. Freedman
references.title: On tail probabilities for martingales
references.venue: Annals of Probability,
references.authors: J. Fu M. Norouzi O. Nachum G. Tucker Z. Wang A. Novikov M. Yang M.R. Zhang Y. Chen A Kumar
references.title: Benchmarks for deep off-policy evaluation
references.venue: arXiv preprint arXiv:2103.16596
references.authors: A. Jacot F. Gabriel C. Hongler
references.title: Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arXiv:1806.07572
references.authors: C. Jin Z. Yang Z. Wang M.I. Jordan
references.title: Provably efficient reinforcement learning with linear function approximation
references.venue: In Conference on Learning Theory,
references.authors: N. Kallus M. Uehara
references.title: Double reinforcement learning for efficient off-policy evaluation in markov decision processes
references.venue: J. Mach. Learn. Res.,
references.authors: M.G. Lagoudakis R. Parr
references.title: Least-squares policy iteration
references.venue: The Journal of Machine Learning Research,
references.authors: H. Le C. Voloshin Y. Yue
references.title: Batch policy learning under constraints
references.venue: In International Conference on Machine Learning,
references.authors: D.A. Levin Y. Peres
references.title: Markov chains and mixing times, volume 107
references.authors: S. Levine A. Kumar G. Tucker J. Fu
references.title: Offline reinforcement learning: Tutorial, review, and perspectives on open problems
references.venue: arXiv preprint arXiv:2005.01643
references.authors: O. Nachum Y. Chow B. Dai L. Li
references.title: Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections
references.venue: arXiv preprint arXiv:1906.04733
references.authors: D. Ormoneit Ś. Sen
references.title: Kernel-based reinforcement learning
references.venue: Machine learning,
references.authors: D. Precup
references.title: Eligibility traces for off-policy policy evaluation
references.venue: Computer Science Department Faculty Publication Series,
references.authors: A. Rahimi B Recht
references.title: Random features for large-scale kernel machines
references.venue: In NIPS,
references.authors: R.S. Sutton A.G. Barto
references.title: Reinforcement learning: An introduction
references.authors: Z. Tang Y. Feng L. Li D. Zhou Q. Liu
references.title: Doubly robust bias reduction in infinite horizon off-policy estimation
references.venue: arXiv preprint arXiv:1910.07186
references.authors: M. Uehara J. Huang N. Jiang
references.title: Minimax weight and q-function learning for off-policy evaluation
references.venue: In International Conference on Machine Learning,
references.authors: C. Voloshin H.M. Le N. Jiang Y. Yue
references.title: Empirical study of off-policy policy evaluation for reinforcement learning
references.venue: arXiv preprint arXiv:1911.06854
references.authors: R. Wang D.P. Foster S.M. Kakade
references.title: What are the statistical limits of offline rl with linear function approximation? arXiv preprint arXiv:2010.11895
references.authors: S. Whiteson
references.title: Adaptive tile coding for value function approximation
references.venue: Technical report
references.authors: T. Xie N. Jiang
references.title: Batch value-function approximation with only realizability
references.venue: arXiv preprint arXiv:2008.04990
references.authors: M. Yin Wang Y.-X
references.title: Asymptotically efficient off-policy evaluation for tabular reinforcement learning
references.venue: In International Conference on Artificial Intelligence and Statistics,
sections.heading: 1 Introduction
sections.text: 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 one of the promising approaches to 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 betweenM and π are abstracted as a stochastic sequence of state s, action a and reward r, called an episode. The objective of the offline RL is then formalized as the maximization of the policy value J(π), 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 run 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 to 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 are referred as the direct methods (DMs), in which some characteristics ofM are assumed to be realizable under some
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  hypothetical models and J(π) 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 to the estimation of its parameters.
  DMs are known to be empirically effective (Fu et al., 2021) if such realizability assumptions are 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 et 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 zero errors). More specifically, we investigate the properties of a simple DM with linear function approximation, which is equivalent with a number of existing algorithms such as LSTDQ (Lagoudakis and Parr, 2003), FQE (Le et al., 2019) with linear function regressors, the marginalized importance sampling estimator (Yin and Wang, 2020) and DualDICE (Nachum et 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 residualsRB andRχ,
  Ĵ(π)− J(π) ∝ E [RB(s, a)Rχ(s, a)] +O ( 1/ √ n ) , (informal)
  where they are corresponding to the unrealizable components of the value function Qπ and the marginal density ratio ν/µ, respectively. To the best of our knowledge, this is the first to show linear DM is doubly robust against model misspecification, i.e., consistent if either RB = 0 or Rχ = 0 hold (Table 1). Leveraging the above result, we also show that a linear DM with the tile-coding function approximation (Section 8.3.2, Sutton 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 2, we formalize the problem setting as well as 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. In Section 4, we discuss related works with comparison to our results. Finally, in Section 5, we present concluding remarks, limitations and future directions. All the proofs of the propositions and the theorem are relegated to the appendix. See Section F for the proofs of the propositions. For the theorem, we present a proof sketch and the pointer to the full proof.
sections.heading: 2 Preliminary
sections.text: 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.
sections.heading: 2.1 Basic Notation
sections.text: We implicitly assume the spaces we encounter in this paper, such as the state space S and the action space A, are equipped with respective metrics and base measures, each of which is a 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 ∫ X f(x) dx the integration of function f with respect to the base measure of X . The subscript X may be omitted if 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 to probability density p by ⟨f⟩p := Ex∼p[f(x)].
  Let [m] := {1, 2, . . . ,m} denote the set of integers from 1 to m. Let ∥·∥p denote the ℓp-norm for vectors and ∥A∥p→q := supx ̸=0 ∥Ax∥q / ∥x∥p the operator norms for matrices, with the convention ∥A∥p := ∥A∥p→p, for all 1 ≤ p, q ≤ ∞.
sections.heading: 2.2 Problem Setup
sections.text: The goal of OPE is to estimate the value of decision-making strategy based on a static dataset of interactions with the environment of interest, without directly knowing its mechanism.
  The environment is modeled as a Markov decision process (MDP)M≡ (S,A, p0, pT , pr), where S is the state space, A the action space, p0(s) the initial state probability, pT (s′|s, a) the transition probability and pr(r|s, a) the [0, 1]-valued reward probability density function for s, s′ ∈ S, a ∈ A, r ∈ [0, 1]. Here we assume pT and pr are unknown. On the other hand, the decision-making strategy is modeled as a policy, a state-conditional action distribution π(a|s) for s ∈ S, a ∈ A. The value of π is measured with the expected cumulative reward
  J(π) := ∞∑ h=0 γh 〈 Phr̄ 〉 pπ0 , (1)
  where γ ∈ [0, 1) is the discounting factor, P is the state-transition operator such that (Pf)(s, a) =∫ f(s′, a′)pT (s ′|s, a)π(a′|s′) ds′ da′, r̄(s, a) := ∫ r pr(r|s, a) dr is the expected reward function, and pπ0 (s, a) := p0(s)π(a|s) is the initial state-action distribution. In particular, ⟨Phr̄⟩pπ0 denotes the expected reward after h transitions starting from pπ0 .
  The policy value J(π) is estimated based on a collection of transition records ξn ≡ (ξ1, ..., ξn) ∈ Dn called an offline dataset, where D := S ×A× [0, 1]× S is the space of transition records and ξi ≡ (si, ai, ri, s ′ i) ∈ D, i ∈ [n], is a transition record made of a preceding state-action pair (si, ai), the associated reward ri, and the state after transition s′i. The dataset ξ n is assumed to be an instantiation of the random variables Ξn ≡ (Ξ1, ...,Ξn), Ξi ≡ (Si, Ai, Ri, S′i), collected with interactions between the environmentM and a query distribution pquery ≡ {pquery(i)(s, a|ξi−1)}i∈[n] such that its distribution is given in a conditional fashion, p(ξi|ξi−1) = pquery(i)(si, ai|ξi−1) pr(ri|si, ai) pT (s′i|si, ai), i ∈ [n]. Note that the notion of query distribution is so flexible that it admits ξn to be a union of episodes generated with multiple nonstationary policies and even adversaries on the choice of state-action pairs. Definition 1 (OPE problem). An instance of the offline policy evaluation problem is specified with POPE ≡ (M, π, γ, pquery), where the goal is to estimate the policy value J(π) determined by (M, π, γ), given the input data ξn generated with (M, pquery), without knowing any of pT , pr or pquery.
sections.heading: 2.3 Assumptions on Data-Collecting Process
sections.text: To ensure the existence of reasonable estimators for POPE, we pose a condition on the mixing of data-collecting process, i.e., conditions on pquery. We assume the amounts of mutual dependencies induced by pquery between time-distant transition records are bounded. Assumption 1 (G∗-mixing dataset). There exists a constant G∗ < ∞ such that Ξn is ‘ϕ’-strong mixing with the coefficient g(h) satisfying 1 + 2 ∑n h=1 √ g(h) ≤ G∗.1
  1The symbol ‘ϕ’ in the ‘ϕ’-strong 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.
  See Definition 17 (in the appendix) for the definition of the ‘ϕ’-strong mixing coefficients. Typical examples satisfying Assumption 1 include datasets consisting of multiple short episodes and mixing Markov chains induced by stationary behavior policies.
  Proposition 1. The following statements are true.
  1. Assume Ξn consists of multiple independently collected episodes with length bounded by H , ordered in a consecutive manner. Then we have G∗ ≤ 2H − 1.
  2. Let pquery(i)(s, a|ξi−1) = pT (s|si−1, ai−1)πb(a|s), 1 ≤ i ≤ n, for some stationary behavior policy πb(a|s) and assume the resulting Markov chain has a finite mixing time tmix <∞. Then we have G∗ ≤ 1 + 7tmix.
  Note that the definition of G∗-mixing is designed to be more general than these examples. In particular, it is more suitable for our query-distribution framework, which admits adversaries behind the choice of (si, ai)-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 µ(s, a) be the marginal data density, given by µ(s, a) := 1 n ∑n i=1 E[pquery(i)(s, a |Ξi−1)] for s ∈ S and a ∈ A.
  The marginal data density µ quantifies the expected frequency of visitation at each point (s, a) ∈ S×A made by the querying process. Thus, roughly speaking, µ(s, a) indicates that how likely the point (s, a) will be sampled in Ξn.
sections.heading: 2.4 (Possibly Misspecified) Environmental Model: Linear MDPs
sections.text: We introduce linear MDPs, a simple class of the environmental models denoted by Hϕ.2 We also define the projection ofM ontoHϕ as we are concerned with the unrealizable case,M /∈ Hϕ. A linear MDPHϕ is formally defined via a bounded vector-valued function on the state-action space called a feature mapping, denoted by ϕ : S × A → RK , K ≥ 1. We assume the boundedness and the concentrability of the mapping as follows.
  Assumption 2 (Boundedness). sups∈S,a∈A ∥ϕ(s, a)∥2 ≤ 1.
  Assumption 3 (Concentrability). Let Σ := ⟨ϕϕ⊤⟩µ be the feature covariance matrix and c∗ := λK(Σ) be its smallest eigenvalue. Then, c∗ > 0.
  Note that the concentrability is a 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 is the tabular features.
  Remark 1. ϕ is said to be tabular if there exits a K-partition of S ×A, {Pk}k∈[K], such that
  ϕk(s, a) = I {(s, a) ∈ Pk} , k ∈ [K], s ∈ S, a ∈ A,
  where I {·} denotes the indicator function. The tabular features always satisfy Assumption 2. Moreover, it satisfies Assumption 3 if every cell is covered with the data marginal, mink∈[K] Pµ(Pk) > 0, where Pµ denotes the probability measure induced by µ.
  Now, the class of ϕ-linear MDPs is defined as follows.
  Definition 3 (ϕ-linear MDPs). We sayM is ϕ-linear with respect to π,3 if there exist b ∈ RK and F ∈ RK×K such that
  r̄(s, a) = b⊤ϕ(s, a), (Pϕ)(s, a) = Fϕ(s, a) (2)
  for almost every s ∈ S and a ∈ A. We refer to the set of all the ϕ-linear MDPs asHϕ.
  2We never assume Hϕ contains the true environmental model. It is rather used to facilitate the construction of OPE estimators in Section 2.5.
  3The ϕ-linearity is the property of the MDP M and the policy π since the transition operator P depends on π. However, we omit the dependency on π for brevity.
  In other words,M is ϕ-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; ifM is realizable as a member ofHϕ, the problem of OPE is reduced to the estimation of b and F . Proposition 2. Under Assumption 2 and 3, ifM∈ Hϕ, we have
  J(π) = b⊤(I − γF )−1x0, (3)
  where x0 := ∫ ϕ(s, a) pπ0 (s, a) dsda.
  However, it is impractical to assume we know the mapping ϕ that attains the realizability with the environment of interestM. Thus we introduce the projection ofM ontoHϕ. Definition 4 (Projection of MDP). Let D2(b, F ) be the parameter discrepancy of the ϕ-linearity, given by
  D2(b, F ) := E(s,a)∼µ [∣∣r̄(s, a)− b⊤ϕ(s, a)∣∣2 + |(Pϕ)(s, a)− Fϕ(s, a)|2] . (4)
  We refer to its minimizer as the projections ofM ontoHϕ, denoted by (b♯, F ♯).
  Note that the projection coincides with the true parameter (b, F ) ifM is realizable. Throughout the paper, however, we consider the general case in which the true parameter may not exist, but (b♯, F ♯) always does.
sections.heading: 2.5 Linear Direct Estimators
sections.text: 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 ξn to obtain the estimate of the projection, (b̂, F̂ ) ≈ (b♯, F ♯). Then, we plug the estimate into (3) to get a policy value estimate, which seems reasonable ifM is (approximately) realizable. More precisely, the first step is formalized via the least squares method.
  Definition 5 (Empirical projection of MDP). The empirical projection (b̂, F̂ ) is defined as the minimizer of the following cost function,4
  C(b, F ; ξn) := 1 n n∑ i=1 [∣∣ri − b⊤ϕ(si, ai)∣∣2 + |ψπ(s′i)− Fϕ(si, ai)|2] . Here, ψπ(s) := ∫ ϕ(s, a)π(a|s) da is the state-marginal feature mapping.
  This definition is justified as follows.
  Proposition 3. For all b ∈ RK and F ∈ RK×K ,∇b,FE[C(b, F ; Ξn)] = ∇b,FD2(b, F ).
  In other words, the gradient of the cost function coincides with that of the parameter discrepancy function in expectation and thus one can expect (b̂, F̂ )→ (b♯, F ♯) in the large sample limit. We have a closed form of the empirical projection.
  Proposition 4. Let (Φ,Ψπ, r̂) be given by
  Φ := [ϕ(s1, a1), ..., ϕ(sn, an)] ⊤, Ψπ := [ψπ(s ′ 1), ..., ψπ(s ′ n)] ⊤, r̂ := [r1, ..., rn] ⊤.
  Then, the empirical projection is given by
  b̂ = 1
  n Σ̂+Φ⊤r̂, F̂ =
  1 n Ψ⊤πΦΣ̂ +, (5)
  where Σ̂ := 1nΦ ⊤Φ is the empirical covariance matrix and Σ̂+ is its pseudo-inverse.
  4If the sample size n is small, the minimizer may not be unique. In this case, we admit multiple empirical projections.
  Algorithm 1 Linear Direct OPE Input: Initial distribution p0, target policy π, data ξn, feature mapping ϕ Output: Policy value estimate Ĵ(π)
  1: Compute the empirical projection (b̂, F̂ ) according to Proposition 4. 2: Compute Ĵ(π) = b̂⊤(I − γF̂ )−1x0, where x0 := ∫ ψπ(s)p0(s) ds.
  Algorithm 2 Linear Fitted Q-Evaluation Input: Initial distribution p0, target policy π, data ξn, feature mapping ϕ, iteration number H Output: Policy value estimate ĴH(π)
  1: Let θ0 := 0 ∈ RK . 2: for h = 1, 2, ...,H do 3: Find θh, the least-norm minimizer of 1n ∑n i=1 ∣∣ri + γθ⊤h−1ψπ(s′i)− θ⊤h ϕ(si, ai)∣∣2. 4: end for 5: Compute ĴH(π) = θ⊤Hx0, where x0 := ∫ ψπ(s)p0(s) ds.
  The whole procedure is summarized in Algorithm 1. Note that ψπ(s) in Ψπ and x0 is not necessarily tractable in a closed form. One can always resort to Monte-Carlo estimates ψπ(s) ≈ 1 nψ ∑nψ ℓ=1 ϕ(s, aℓ), where aℓ ∼ π(a|s), ℓ ∈ [nψ], are i.i.d. samples. Proposition 3 still holds under this approximation. Also note that Ĵ(π) is undefined if I − γF̂ is 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 ♯γ := (I − γF ♯)−1 exists.
  Note that the compatibility implies the well-definedness of Ĵ(π) with high probability for sufficiently large n since F ♯ = limn→∞ F̂ . We also discuss the interpretation, sufficient conditions and a statistical test of the compatibility in Section 3.1.1 and 3.1.2.
  Algorithm 1 is equivalent to the LSTDQ (Lagoudakis and Parr, 2003) algorithm and a number of equivalence relationships to recent OPE estimators are drawn in Duan et al. (2020). For the completeness, we show Algorithm 1 is equivalent to the limit of Fitted Q-Evaluation (Le et al., 2019) with linear function approximators, shown in Algorithm 2.
  Proposition 5. The output of Algorithm 1 Ĵ(π) is identical to the limit of that of Algorithm 2, limH→∞ ĴH(π), if both exist.
sections.heading: 3 Main Results
sections.text: First, we give an asymptotic characterization of the error Ĵ(π) − J(π), which sheds light on the doubly robust nature of linear DM. Second, leveraging the first result, we show novel consistency properties of a simple tile-coding estimator.
sections.heading: 3.1 Asymptotic Error of Linear DM
sections.text: As will be shown later, the dominant term of the OPE error is written as an inner product of two functions, namely the χ-residual function and the Bellman residual function. To introduce these residual functions, we begin with the definitions of the ϕ-spanned function space, the ϕ-semi norm and the marginal target density. Definition 6 (ϕ-spanned function space). We denote by Fϕ the normed function space spanned by ϕ1, ..., ϕK , i.e., Fϕ := { (θ⊤ϕ) : S ×A → R
  ∣∣ θ ∈ RK}. Definition 7 (ϕ-semi norm). For any real-valued functions over the state-action space f : S×A → R, the ϕ-semi norm of f is given by |f |ϕ := ∥ ⟨ϕf⟩µ ∥2. Definition 8 (Marginal target density). Let ν(s, a) be the marginal target density, given by ν(s, a) := (1− γ) ∑∞ h=0 γ h(P †hpπ0 )(s, a), where P † is the adjoint operator of P .
  Note that (P †hpπ0 )(s, a) denotes the state-action density after h transitions starting from p0. Thus, ν can be thought of as the relative frequency of the state-action visitations in the target episode with horizon-dependent multiplicative weights γh.
  Then, two residual functions are defined as follows. Definition 9 (χ-residual function). The χ-residual function is defined as
  Rχ(s, a) := ν(s, a)
  µ(s, a) − w♯(s, a),
  where w♯ is the minimizer of Lχ(w) := ⟨( νµ − w) 2⟩µ in Fϕ.
  Definition 10 (Bellman residual function). The Bellman residual function is defined as RB(s, a) := (BQ♯)(s, a)−Q♯(s, a),
  where B : Q 7→ r̄+ γPQ is the Bellman operator and Q♯ is the minimizer of LB(Q) := |BQ−Q|2ϕ in Fϕ.
  Note that these functions are ‘residual’ since they are the remainders of the projection of some functions onto Fϕ. Rχ is the residual of the density ratio ν/µ andRB is the residual of the Bellman equation. Also note that the projection of the Bellman equation is coarse-grained as |f |ϕ = 0 does not necessarily imply f = 0 (therefore it is a semi-norm). We will discuss further interpretation of these residual functions in Section 3.1.1.
  Now we are ready to state our first result. Theorem 6. Suppose Assumption 1, 2, 3 and 4 hold. Then, we have the almost-sure convergence
  Ĵ(π)− J(π) n→∞−→ − 1 1− γ ⟨RBRχ⟩µ (6)
  in a poly( 11−γ , 1 n , G ∗, 1c∗ , ∥F ♯ γ∥2) rate, uniformly with respect to the choice of p0. Moreover, the convergence is also uniform with respect to the choice of π, if supπ ∥F ♯γ∥2 <∞.
  Proof. (Sketch.) It is directly derived from the non-asymptotic bound (Theorem 13, in the appendix), whose proof strategy is to decompose the error by Ĵ(π)−J(π) = (J♯(π)−J(π))+(Ĵ(π)−J♯(π)), where J♯(π) := ⟨Q♯⟩pπ0 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 a rate of O(1/ √ n). In particular, the key step in the evaluation of the first term is the following series of identities,
  J♯(π)− J(π) = ... = −⟨RB⟩ν = − 〈 RB ν
  µ 〉 µ = − 〈 RB ( ν µ − f )〉 µ , ∀f ∈ Fϕ,
  where the last identity is what allows us to fit arbitrary function in Fϕ away from ν/µ, which is made possible with RB being in the orthogonal complement of Fϕ. The full proof is deferred to Section A.
sections.heading: 3.1.1 Implications and Interpretations
sections.text: Consistency under Q-function realizability (and necessity of the compatibility). Theorem 6 shows the necessary and sufficient condition for the consistency of compatible linear DM. Specifically, J(π) is consistent if eitherRB = 0 orRχ = 0. The first conditionRB = 0 can be interpreted as the so-called Q-function realizability. Proposition 7. Let Qπ := ∑ h≥0 γ
  h⟨Phr̄⟩pπ0 be the policy Q-function. Then, under Assumption 2, 3 and 4, we haveRB = 0 if and only if Qπ ∈ Fϕ.
  This is interesting sinceRB preserves the full information of Qπ , the unique solution to the Bellman equation, even though it is the result of the coarse-grained projection (Definition 10). 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 DM. In particular, Amortila et al. (2020) showed there exists a 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 6 and Proposition 7 show we can eliminate such instances if we additionally assume the compatibility (Table 1).
  Consistency under density-ratio realizability. Theorem 6 implies another route to achieve the consistency, namelyRχ = 0. By definition, it is trivial thatRχ = 0 is equivalent to ν/µ ∈ Fϕ. Proposition 8. Under Assumption 2 and 3, we haveRχ = 0 if and only if ν/µ ∈ Fϕ.
  It suggests we have a consistent estimate of J(π) when the density ratio ν/µ 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, if we have a non-decreasing sequence of linear function classes {Fϕ(1) ⊂ Fϕ(2) ⊂ · · · }, the corresponding sequence of χ-residuals {R (1) χ ,R(2)χ , · · · } is also non-increasing, i.e., ∥R(m)χ ∥L2(µ) is the non-increasing function of m ≥ 1. This does not hold in general with the Bellman residualRB because the projection metric depends on ϕ.
  Convergence without concentrability. A convergence result similar to Theorem 6 can be established without the concentrability condition (Assumption 3), i.e., even if the covariance matrix Σ is singular. In this case, the projections b♯, F ♯, w♯ and Q♯ is modified to the least-norm minimizers and the rate of convergence depends on the minimum nonzero eigenvalue of Σ. See Definition 13 and Theorem 13 in the appendix for the detailed statement.
  Linear DM is LB(Q)-minimization. As illustrated in the sketch, the proof of Theorem 6 gives the large sample limit of Ĵ(π), namely Ĵ(π) → J♯(π) = ⟨Q♯⟩pπ0 . Therefore, since Q
  ♯ is a minimizer of LB(Q) (Definition 10), linear DM is asymptotically equivalent to solving minQ∈Fϕ LB(Q). This observation is closely related to the kernel-loss interpretation of the temporal difference methods (Corollary 3.5 in Feng et al. (2019)).
sections.heading: 3.1.2 Sufficient Conditions for Compatibility and Uniform Boundedness of F ♯γ
sections.text: In a practical sense, the compatibility is a necessary (not just sufficient) condition for the asymptotic convergence of linear DM; if I − γF ♯ is singular, the smallest singular value of I − γF̂ approaches to zero and hence its inverse (I − γF̂ )−1 is divergent and unstable (if not nonexistent) as well as the estimate Ĵ(π). This is seen from the concentration limn→∞ F̂ = F ♯ (see Proposition 19 in the appendix) and the continuity of singular values.
  However, it is difficult to completely characterize when F ♯γ exists or is uniformly bounded. Below, we show a sufficient condition for the uniform boundedness which depends only on µ and Σ.
  Proposition 9. Under Assumption 2 and 3, we have supπ ∥F ♯γ∥2 <∞ if
  1. There exists v0 ∈ RK such that v⊤0 ϕ(·, ·) ≡ 1, and
  2. ϕ(s, a)Σ−1ϕ(s′, a′) ≥ 0 for all (s, a), (s′, a′) ∈ S ×A.
  Note that both assumptions hold with the tabular features ϕ, i.e., tabular features are always compatible. In general, the first condition can be satisfied by expanding ϕ with an extra ‘bias’ dimension whose value is always one. On the other hand, the second condition is dependent on ϕ and Σ in a nontrivial manner.
  Even if it is difficult to analytically guarantee the compatibility and the uniform boundedness, it is possible to statistically test/bound them by computing a high-probability upper bound on ∥F ♯γ∥2 (cf. Proposition 19 and 20 in the appendix). Moreover, combining it with the non-asymptotic bound (Theorem 13 in the appendix), one can obtain a data-dependent concentration bound. If the resulting concentration rate is not acceptable, then one may change ϕ or fall back on tabular features.
sections.heading: 3.2 Consistency of Tile-Coding Estimators under Unrealizability
sections.text: As is seen from Theorem 6, not surprisingly, a linear estimator with fixed ϕ is not consistent in general under unrealizability. This motivates us to investigate alternative methods that adaptively selects feature mappings. Such an estimation method is formally defined as follows.
  Definition 11 (Nonparametric estimator). We refer to (ϕ, m̂) as a nonparametric estimator if ϕ = {ϕ(m)}∞m=1 is a sequence of feature mappings such that ϕ(m) : S ×A → RKm , Km ≥ 1, and m̂ : N→ N is a model-selecting function such that limn→∞ m̂(n) =∞. The output of the estimator is given as Ĵ(π;ϕ, m̂) := Ĵ(π;ϕ(m̂(n))), where Ĵ(π;ϕ) denotes the linear direct estimate given by Algorithm 1 with a feature mapping ϕ.
  In principle, if m̂(n) diverges slowly compared to the convergence (6), the error of (ϕ, m̂) is still characterized by Theorem 6. Thus, if ϕ is such that the asymptotic bias given by (6) goes to zero as m→∞, there exists a consistent nonparametric estimator (ϕ, m̂) with sufficiently slowly diverging function m̂(n).
  Below, we show a typical instance of such consistent nonparametric estimators, namely the refining tile-coding estimator. Henceforth, we assume for simplicity S ×A = [0, 1]d, d ≥ 1, i.e., both states and actions are continuous. 5
  Definition 12 (Refining tile-coding sequence). We call ϕ as the refining tile-coding sequence if, for all m ≥ 1, ϕ(m) is tabular with respect to themd-partition {P(m)k }k∈[m]d such that P (m) k = ∏d j=1 I (m) kj for all k = (k1, ..., kd) ∈ [m]d, where I(m)k := [ k−1 m , k m ) for all 1 ≤ k < m and I (m) m := [1− 1m , 1].
  Leveraging Theorem 13, the non-asymptotic version of Theorem 6, it is shown the nonparametric estimation using the tile-coding scheme is consistent under very mild assumptions.
  Proposition 10. For the refining tile-coding sequence ϕ, we have Ĵ(π;ϕ, m̂) n→∞−→ J(π) a.s. if
  1. Ξn is G∗-mixing for some G∗ <∞ (Assumption 1).
  2. 0 < cµ := infs∈S,a∈A µ(s, a) ≤ Cµ := sups∈S,a∈A µ(s, a) <∞. 3. m̂(n)d/ √ n→ 0 as n→∞.
  Note that Proposition 10 assumes nothing on pr, pT , p0 and π other than the implicit well-definedness of their density functions. Because of this, the rate of convergence may be arbitrarily slow. We have a stronger guarantee if some regularities of the density ratio ν/µ is given. A typical example of such regularity is the Lipschitz continuity. Proposition 11. Under the assumptions of Proposition 10, if ν/µ is Lipschitz continuous on S ×A, then we have |Ĵ(π;ϕ, m̂)− J(π)| = O(n− 1 2d+2 ) with m̂(n) = Θ(n 1 2d+1 ).
  Note that the stronger convergence result is 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 Rχ, which measures the regularity of ν/µ, without forcing explicit regularities on the Bellman operator.
sections.heading: 4 Related Work
sections.text: The offline policy evaluation is closely related to the off-policy policy evaluation in the bandit and RL literatures (Precup, 2000; Dudík et al., 2011; Sutton and Barto, 2018), where behavior policies are often assumed to be known. Recently, a number of researchers are focusing on more ‘offline’ settings (Levine et 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. A common type of realizability is the Bellman-operator realizability (Yin 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 RL under the Q-function realizability, a relaxation of the Bellman-operator realizability, also allowing small realizability-violation in 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.
  5It is possible to extend it to allow states and actions being discrete partially or entirely.
  Doubly-robust properties similar to Theorem 6 were previously studied in the literature (Kallus and Uehara, 2020; Tang et al., 2019). In particular, Theorem 6 is 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 to one another in the following senses. Theorem 6 shows 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) value-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 6 is also closely related to Example 2 and Example 7 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-ratio realizabilities to achieve the consistency (Table 1).
  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 be more expensive in computation, they can be approximated with a finite linear basis (Rahimi et al., 2007). Ormoneit and Sen (2002) shows a kernel-smoothing approach yields a nonparametric convergence rate of O(n− 1 2d+4 ) under different regularity assumptions, including the continuity of r̄. (Feng et al., 2020) studied a kernel-based OPE with confidence error bound, but the error bound is algorithmically determined and not studied analytically.
sections.heading: 5 Concluding Remarks
sections.text: 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 a 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 ϕ as a key condition that guarantees the above identity. Finally, we have investigated as its application the error of nonparametric estimators.
  Limitation. One limitation of the present work is that we do not have any methods to control ∥F ♯γ∥ other than Proposition 9, which affects the speed of the concentration (6). In particular, this makes it difficult to construct consistent nonparametric estimators with general feature sequences ϕ other than the tabular ones since the norm ∥F ♯γ∥ may depend on n in a nontrivial manner. However, as discussed in Section 3.1.1, controlling ∥F ♯γ∥ 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 ν is well defined with respect to the base measure of S ×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 an interesting future direction. Studies on the compatibility of the feature mappings ϕ 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).
sections.heading: Acknowledgment
sections.text: We deeply thank all the reviewers and the area chair for extensive discussions, which help us greatly improve the manuscript.
title: Asymptotically Exact Error Characterization of Offline Policy Evaluation with Misspecified Linear Models