Off-policy estimation with adaptively collected data: the power of online learning

Authors: jeonghwan  lee
cong  ma
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 09:41:33

Abstract: We consider estimation of a linear functional of the treatment effect from adaptively collected data. This problem finds a variety of applications including off-policy evaluation in contextual bandits, and estimation of the average treatment effect in causal inference. While a certain class of augmented inverse propensity weighting (AIPW) estimators enjoys desirable asymptotic properties including the semi-parametric efficiency, much less is known about their non-asymptotic theory with adaptively collected data. To fill in the gap, we first present generic upper bounds on the mean-squared error of the class of AIPW estimators that crucially depends on a sequentially weighted error between the treatment effect and its estimates. Motivated by this, we propose a general reduction scheme that allows one to produce a sequence of estimates for the treatment effect via online learning to minimize the sequentially weighted estimation error. To illustrate this, we provide three concrete instantiations in (1) the tabular case; (2) the case of linear function approximation; and (3) the case of general function approximation for the outcome model. We then provide a local minimax lower bound to show the instance-dependent optimality of the AIPW estimator using no-regret online learning algorithms.

Main paper: 
 introduction: 
 Estimating a linear functional of the treatment effect is of great importance in both causal inference and reinforcement learning (RL). For instance, in causal inference, one is interested in estimating the average treatment effect (ATE) [20] or their weighted variants, and in the literature of bandits and RL, one is interested in estimating the expected reward of a target policy [38, 64, 41, 37] . Two main challenges arise when tackling this problem:• Off-policy estimation: Oftentimes, one needs to estimate the linear functional based on observational data collected from a behavior policy. This behavior policy may not match the desired distribution specified by the linear functional [42] ; • Adaptive data collection mechanism: It is increasingly common for observational data to be adaptively collected due to the use of online algorithms (e.g., via contextual bandit algorithms [60, 33, 2, 52, 34] ) in experimental design [67] .In this paper, we deal with two challenges simultaneously by investigating the estimation of a linear functional of the treatment effect from observational data that are collected adaptively. When the observational data is collected non-adaptively, i.e., in an i.i.d. manner, there is an extensive line of work [51, 49, 10, 24, 1, 27, 43, 6, 3, 64, 41] investigating the asymptotic and non-asymptotic theory of various estimators. Most notably are the study [6] that establishes the asymptotic efficiency of a family of semi-parametric estimators, and a more recent study [42] that undertakes a finite-sample analysis which uncovers the importance of a certain weighted ℓ 2 -norm when estimating the treatment effect. On the other hand, when it comes to adaptively collected data, most prior works [16, 67] focus on the asymptotic normality of the estimators, and do not discuss the finite-sample analysis of the estimators. In this paper, we aim to fill in this gap.More specifically, we make the following three main contributions in this paper:• First, we present generic finite-sample upper bounds on the mean-squared error of the class of augmented inverse propensity weighting (AIPW) estimators that crucially depends on a sequentially weighted error between the treatment effect and its estimates. This sequentially weighted estimation error demonstrates a clear effect of history-dependent behavior policies;• Second, motivated by previous finding, we propose a general reduction scheme that allows one to form a sequence of estimates for the treatment effect via online learning to minimize the sequentially weighted estimation error. To demonstrate this, we provide three concrete instantiations in (1) the tabular case; (2) the case of linear function approximation; and (3) the case of general function approximation for the outcome model;• In the end, we provide a local minimax lower bound to showcase the instance-dependent optimality of the AIPW estimator using no-regret online learning algorithms in the large-sample regime.Off-policy estimation with observational data Off-policy estimation in observational settings has been a central topic in statistics, operations research, causal inference, and RL. Here, we group a few prominent off-policy estimators into the following three categories: (i) Model-based estimator: often dubbed as the direct method (DM), whose key idea is to utilize observational data to learn a regression model that predicts outcomes for each state-action pair, and then average these model predictions [29, 10, 9, 39] . Due to model mis-specification, DM typically has a low variance but might lead to highly biased estimation results. (ii) Inverse propensity weighting (IPW): for the OPE task, IPW uses importance weighting to account for the distribution mismatch between the behavioral policy and the target policy [21, 55] . If the behavioral policy differs significantly from the target policy, then IPW can have an overly large variance (known as the low overlap issue) [23] . Typical remedies for this issue include propensity clipping [25, 57] or self-normalization [19, 58] . (iii) Hybrid estimator: some off-policy estimators (e.g., the doubly-robust (DR) estimator [10] ) combine DM and IPW together to blend their complementary strengths [48, 10, 9, 59, 12, 56, 64] . A key asymptotic results in OPE is that the cross-fitted DR is √ n-consistent and asymptotically efficient (that is, it attains the lowest possible asymptotic variance), even for the case where nuisance parameters are estimated at rates slower than √ n-rates [6] . However, these methods still might be vulnerable to the low overlap issue especially for large or continuous action spaces. Thus, there has been a line of recent studies on OPE for large action spaces [13, 53, 44, 54] and OPE for continuous action space [28, 35, 63] .Off-policy estimation with adaptively collected data A recent strand of works studied asymptotic theory of adaptive variants of the IPW and DR estimators (e.g., asymptotic normality, semi-parametric efficiency, and confidence intervals) [31, 8, 7] for adaptively collected data. However, in adaptive experiments, overlap between the behavioral policies and the target policy can deteriorate since the experimenter shifts the behavioral policies in response to what he/she observes (known as the drifting overlap) [67] . It may engender unacceptably large variances of the IPW and DR estimators. To address this large variance problem, there has been a recent strand of works investigating variance reduction strategies for the DR estimator based on shrinking importance weights toward one [4, 64, 57, 56] , local stabilization [40, 69] , and adaptive weighting [17, 67] . Recent studies on policy learning with adaptively collected data [68, 26] explored the adaptive weighting DR estimator for policy learning. In contrast with the majority of prior works on off-policy estimation with adaptively collected data that focus on asymptotic results, this paper aims at establishing non-asymptotic theory of the problem. While several researchers have been recently explored non-asymptotic results of the problem with an emphasis on uncertainty quantification [30, 65] , we focus on analyses of estimation procedures of the off-policy value. As a majority of existing standard objects for uncertainty quantification, such as a confidence interval (CI), take a very static view of the world (e.g., it holds for a fixed sample size and is not designed for interactive/adaptive data collection procedures), the aforementioned two papers [30, 65] instead study a more suitable statistical tool for such cases called a confidence sequence. 
problem formulation: 
 We first formulate our problem using the language of contextual bandits: let X, A, and Y ⊆ R denote the context space, the action space, and the outcome space, respectively. Denote by O := X × A × Y the space of all possible context-action-outcome triples. In an adaptive experiment, one observes n samples {(X i , A i , Y i ) ∈ O : i ∈ [n]} produced by the following data generating procedure [26, 68] :At each stage i ∈ [n], (i) A context X i ∈ X is independently sampled from a fixed context distribution Ξ * (•) ∈ ∆(X);(ii) There exists a behavioral policyΠ * i (•, •) : X × O i-1 → ∆(A) that selects the i-th action as A i |X i , O i-1 ∼ Π * i (• |X i , O i-1 ), where O i := (X 1 , A 1 , Y 1 , • • • , X i , A i , Y i ) ∈ O i for i ∈ [n]. As Π * i (• |X i , O i-1 ) may depend on previous observations, {(X i , A i , Y i ) : i ∈ [n]} are no longer i.i.d.; (iii) Given a Markov kernel Γ * (•, •) : X × A → ∆(Y), we assume that the outcome is generated according to Y i ∼ Γ * (• |X i , A i ). Moreover, the conditional mean of the outcome Y i ∈ Y is specified as E [Y i |X i , A i ] = Y yΓ * (dy |X i , A i ) = µ * (X i , A i ) ,where the functionµ * (•, •) : X × A → R is called the treatment effect (in causal inference)or the reward function (in bandit and RL literature). We note that the treatment effect µ * is not revealed to the statistician. We also define the conditional variance function σ 2 (•, •) :X×A → [0, +∞] defined by σ 2 (x, a) := E {Y -µ * (X, A)} 2 (X, A) = (x, a) , whichis assumed to satisfy σ 2 (x, a) < +∞ for every state-action pair (x, a) ∈ X × A.At this moment, we assume the existence of σ-finite base measures λ X (•), λ A (•), and λ Y (•) over X, A, and Y, resp., such thatΞ * (•) ≪ λ X (•), Π * i (• |x, o i-1 ) ≪ λ A (•) for every (x, o i-1 ) ∈ X × O i-1 and i ∈ [n], and Γ * (• |x, a ) ≪ λ Y (•)for all state-action pairs (x, a) ∈ X × A. Here, the notation ≪ stands for the absolute continuity of measures. Our main goal is to estimate the off-policy value for any given target evaluation function g(•, •) : X × A → R defined asEQUATIONwhereI * := (Ξ * , Γ * ) ∈ I := ∆(X) × (X × A → ∆(Y))defines our problem instance. Throughout the paper, we assume that the propensity scores{π * i (X i , O i-1 ; A i ) : i ∈ [n]} are revealed, where π * i (x, o i-1 ; •) := dΠ * i (•|x,oi-1 ) dλ A : A → R.As we mentioned earlier in Section 1, the estimation problem of a linear functional of the treatment effect µ * turns out to be useful in both causal inference and RL in the following sense:• Estimation of average treatment effects: We consider the binary action space A = {0, 1} equipped with the counting measure. The average treatment effect (ATE) in our problem setting is defined as the linear functionalATE := E I * [Y i (1) -Y i (0)] = E X∼Ξ * [µ * (X, 1) -µ * (X, 0)] .Once we take the evaluation function as g(x, a) = 2a -1, the ATE boils down to a particular case of the equation (1);• Off-policy evaluation (OPE) for contextual bandits: Assume that a target policy Π target (•) :X → ∆(A) is given such that Π target (• |x ) ≪ λ A (•) for every context x ∈ X. For simplicity, let π target (x, •) := dΠ target (•|x ) dλ Adenote the density function of the target policy for each context x ∈ X. If we take g(x, a) = π target (x, a), then the linear functional (1) corresponds to the value of the target policy Π target . This problem has been widely studied in the literature of bandits and RL, known as the off-policy evaluation (OPE).We conclude this section by introducing notations that will be useful in later sections: let P i I ∈ ∆ O i denote the law of the sample trajectory O i under the sampling mechanism with a problem instance I = (Ξ, Γ) ∈ I. We denote the density function ofEQUATIONfor any function φ(•, •) : X × A → R, together with the k-th weighted ℓ 2 -space byL 2 (k) := φ(•, •) ∈ (X × A → R) : ∥φ∥ (k) < +∞ . 
a class of aipw estimators and non-asymptotic guarantees: 
 The main objective of this section is to develop a meta-algorithm to tackle the estimation problem of the off-policy value (1), followed by some key rationale of the proposed procedure as a variancereduction scheme of the standard inverse propensity weighting (IPW) estimator.Akin to [42] , we consider a class of two-stage estimators obtained from simple perturbations of the IPW estimator. Given any collection f :=f i : X × O i-1 × A → R : i ∈ [n]of auxiliary functions, we consider the following perturbed IPW estimatorτ f n (•) : O n → R: τ f n (o n ) := 1 n n i=1 g (x i , a i ) y i π * i (x i , o i-1 ; a i ) -f i (x i , o i-1 , a i ) + ⟨f i (x i , o i-1 , •) , π * i (x i , o i-1 ; •)⟩ λ A . For each i ∈ [n], let ν i ∈ ∆ X × O i-1 × A denote the joint distribution of (X i , O i-1 , A i ) inducedby the adaptive data collection procedure described in Section 2. Then, we arrive at the following result whose proof is deferred to Appendix B.1: Proposition 3.1. For any collection f :=EQUATIONEQUATION+ 1 n n i=1 E I * g (X i , A i ) µ * (X i , A i ) π * i (X i , O i-1 ; A i ) -⟨g (X i , •) , µ * (X i , •)⟩ λ A -f i (X i , O i-1 , A i ) 2 .From the decomposition (4) of the variance of the perturbed IPW estimate τ f n (O n ), one observes that the only term that depends on the collection of auxiliary functions f is the third term. More importantly, the third term is equal to zero if and only ifEQUATIONThe collection of minimizing functionsEQUATIONwhose variance is given byEQUATIONAlgorithm 1 Meta-algorithm: augmented inverse propensity weighting (AIPW) estimator.Require:the dataset D = {(X i , A i , Y i ) ∈ O : i ∈ [n]} and an evaluation function g : X × A → R. 1: For each step i ∈ [n],we compute an estimate μi (O i-1 ) ∈ (X × A → R) of the treatment effect based on the sample trajectory O i-1 up to the (i -1)-th step. // Implement Algorithm 2 as a subroutine; 2: Consider the AIPW estimator (a.k.a., the doubly-robust (DR) estimator)EQUATIONwhere the objects being averaged are the AIPW scores Γi (•) :EQUATION) 3: return the AIPW estimate τ AIPW n (O n ).Since the treatment effect µ * is not revealed to the statistician in (6) , it is impossible to exactly compute the oracle estimate τ f * n (•) : O n → R using only the observational dataset O n . Therefore, a natural remedy would be the following two-stage procedure, which is referred to as the augmented inverse propensity weighting (AIPW) estimator or the doubly-robust (DR) estimator [10, 50, 61, 17, 67, 22] : (i) we first compute a sequence of estimates{μ i (O i-1 ) ∈ (X × A → R) : i ∈ [n]} of the treatment effect µ * ; and then (ii) we plug-in these estimates to the equation (6) to construct an approximation to the ideal estimate τ f * n (O n ). We summarize this two-stage procedure in Algorithm 1. We pause here to compare our problem setting and algorithms with the most relevant work [42] . We focus on off-policy estimation with adaptively collected data, which is technically more challenging compared to i.i.d. data considered in [42] . In the case with i.i.d. data, [42] proposed a natural approach to construct a class of two-stage estimators as follows: (a) compute an estimate μ of the treatment effect µ * utilizing part of the dataset; and (b) substitute this estimate in the equation (6) of the oracle estimator. Note that the authors use the cross-fitting approach [5, 6] , which allows to make full use of data to maintain efficiency and statistical power of machine learning algorithms for estimation of nuisance parameters while reducing overfitting bias. However, the cross-fitting strategy heavily relies on the i.i.d. nature of the data collection mechanism and therefore one cannot use it in the setting with adaptively collected data. Instead, we construct an estimate μi of the treatment effect µ * based on the sample trajectory O i-1 at each stage and then substitute these estimates in the equation ( 6). This is one of main contributions to address the adaptive nature of our data generating mechanism. We will make use of the framework of online learning to construct a sequence of estimates for the treatment effect µ * .In this section, we provide statistical guarantees for the class of AIPW estimators for dealing with the estimation problem of the off-policy value (1) . The main result of this section can be summarized as the following non-asymptotic upper bound on the mean-squared error (MSE) of Algorithm 1: Theorem 3.1 (Non-asymptotic upper bound on the MSE of the AIPW estimator). For any sequence of estimates {μ i (O i-1 ) ∈ (X × A → R) : i ∈ [n]} for the treatment effect µ * , the AIPW estimator (8) has the MSE bounded above byEQUATIONNote that the non-asymptotic upper bound (10) The learner selects a point μi (O i-1 ) ∈ (X × A → R) based on the sample trajectory O i-1 ;3:The environment then picks a loss function l i (•) : (X × A → R) → R defined asEQUATION4: end for 5: return the sequence of estimates{μ i (O i-1 ) ∈ (X × A → R) : i ∈ [n]} of the treatment effect.optimal variance (7) achievable by the oracle estimator, and the second termEQUATIONmeasures the average estimation error of the estimates{μ i (O i-1 ) ∈ (X × A → R) : i ∈ [n]} of µ * .Of primary interest to us is a subsequent upper bounding argument based on the MSE bound (10) in the finite sample regime: in particular, to minimize the RHS of (10) , one needs to choose a sequence of estimates{μ i (O i-1 ) ∈ (X × A → R) : i ∈ [n]} which minimizes the second term (11) .Let us now focus on constructing a sequence of estimates{μ i (O i-1 ) ∈ (X × A → R) : i ∈ [n]} of the treatment effect and upper bounding the estimation error (11) in the MSE bound (10) . To this end, we borrow ideas from the literature of online non-parametric regression [45] .To begin with, we consider an n-round turn-based game between the learner and the environment; see Algorithm 2 for the details. Then, one can readily observe for any µ(•, •) : X × A → R, we haveEQUATION)In the current turn-based game, our natural goal is to minimize the learner's static regret against the best fixed action in hindsight belonging to a pre-specified function class F ⊆ (X × A → R):EQUATIONwhere A denotes the learner's online non-parametric regression algorithm that returns a sequence of estimates {μ i (O i-1 ) : i ∈ [n]} for the treatment effect. Then, one can establish the following oracle inequality that demystifies a relationship between estimation problem of the off-policy value and the online non-parametric regression protocol. See Appendix B.3 for the proof. Theorem 3.2 (Oracle inequality for the class of AIPW estimators). The AIPW estimator (8) using the sequence of estimates{μ i (O i-1 ) ∈ (X × A → R) : i ∈ [n]} of the treatment effect µ * produced by the online non-parametric regression algorithm A enjoys the following upper bound on the MSE:EQUATIONA few remarks are in order. Apart from the optimal variance v 2 * , the RHS of the bound (15) contains two additional terms: (i) the expected regret relative to the number of rounds n, where the expected value is taken over O n ∼ P n I * (•); and (ii) the approximation error under the ∥•∥ (n) -norm. Given any fixed function class F ⊆ (X × A → R), if we consider the large sample size regime, i.e., the sample size n is sufficiently large, then one can see that the asymptotic variance of the AIPW estimator ( 8) is asymptotically the same as v 2 * +inf ∥µ -µ * ∥ 2 (n) : µ ∈ F , provided that the online non-parametric regression algorithm A exhibits a no-regret learning dynamics, i.e., E I * [Regret (n, F; A)] = o(n) as n → ∞. Consequently, the AIPW estimator (8) may suffer from an efficiency loss which depends on how well the unknown treatment effect µ * can be approximated by a member of the function class F ⊆ (X × A → R) under the ∥•∥ (n) -norm. Hence, any contribution to the MSE bound of the AIPW estimator (8) in addition to the efficient variance v 2 * primarily relies on the approximation error associated with approximating the treatment effect µ * utilizing a provided function class F.The main goal of this section is to illustrate the consequences of our general theory developed in Section 3 so far for several concrete classes of outcome models. Throughout this section, we consider the case for which Y = [-L, L] for some constant L ∈ (0, +∞), and impose the following condition: Assumption 1 (Strict overlap condition). The likelihood ratios are uniformly bounded by a universal constant B ∈ (0, +∞), i.e., for every i ∈EQUATION)We note that Assumption 1 is often referred to as the strict overlap condition in the literature of causal inference [20, 32, 66, 36, 11] . At this point, we emphasize that Assumption 1 is necessary to produce main consequences of the oracle inequality for the class of AIPW estimators (Theorem 3.2) that we discuss in the ensuing subsections: Theorems 3.3, 3.4, and the arguments throughout Appendix B.6.We embark on our discussion about the consequences of our theory established in Sections 3.3 and 3.4 for one of the simplest case of the outcome model satisfying the following assumption. Assumption 2 (Tabular setting of the outcome model). The state-action space X × A is a finite set.If we compute the gradient of the loss function (14) , we haveEQUATIONwhere δ (Xi,Ai) ∈ R X×A is the point-mass vector at the i-th state-action pair in the sample trajectory, i.e., δ (Xi,Ai) (x, a):= 1 if (x, a) = (X i , A i ); δ (Xi,Ai) (x, a) := 0 otherwise.Algorithm 3 Online gradient descent (OGD) algorithm for the finite state-action space.X×A , the total number of rounds n ∈ N, and a sequence of learning rates{η i ∈ (0, +∞) : i ∈ [n -1]}. 1: We first choose an initial point μ1 (∅) ∈ F arbitrarily; 2: for i = 1, 2, • • • , n -1, do 3: Observe a triple (X i , A i , Y i ) ∈ O; 4:Update μi+1 (O i ) ∈ F according to the following OGD update rule:EQUATIONwhere Π F [•] : R X×A → F denotes the projection map of R X×A onto the function space F. 5: end for 6: return the sequence of estimates {μ i (O i-1 ) ∈ F : i ∈ [n]} of the treatment effect µ * . Now, it is time to put forward an online contextual learning algorithm aimed at producing a sequence of estimates of µ * with a no-regret learning guarantee. For the tabular case, the online non-parametric regression problem can be resolved through standard online convex optimization (OCO) algorithms. In particular, we employ the online gradient descent (OGD) algorithm (see Algorithm 3) as a subroutine of Algorithm 1. By leveraging standard results on regret analysis of OCO algorithms, one can obtain the following regret bound, which guarantees a no-regret learning dynamics of Algorithm 3. Theorem 3.3 (Regret guarantee of Algorithm 3). Under Assumptions 1 and 2, the OGD algorithm (Algorithm 3) with learning ratesEQUATION)where diam(F):= sup {∥µ∥ 2 : µ ∈ F} denotes the diameter of F ⊆ [-L, L] X×A .See Appendix B.4 for the proof of Theorem 3.3. Combining the regret guarantee (19) of Algorithm 3 together with the MSE bound (15) in Theorem 3.2, one can establish a concrete upper bound on the MSE of the AIPW estimator ( 8) by utilizing Algorithm 3 to produce a sequence of estimates for the treatment effect µ * .We next move on to outcome models where the state-action space X × A can be infinite. We begin with the simplest case: the class of linear outcome functions. Let ϕ(•, •) : X × A → R d be a known feature map such that sup {∥ϕ(x, a)∥ 2 : (x, a) ∈ X × A} ≤ 1, and we consider the functions that are linear in this representation:f θ (•, •) : X × A → R, where f θ (x, a) := θ ⊤ ϕ(x, a)for some parameter vector θ ∈ R d . Given a radius R > 0, we define the function classEQUATIONwhereB (0 d ; R) := u ∈ R d : ∥u∥ 2 ≤ R .With this linear function approximation framework, let us consider the following OCO model: at the i-th stage, (i) the learner first chooses a point θi (O i-1 ) ∈ Θ;(ii) the environment then picks a loss function L i (•) : Θ → R defined asEQUATIONand our goal is to produce a sequence of estimates μi(O i-1 ) := θi (O i-1 ) ⊤ ϕ ∈ F lin : i ∈ [n]for the treatment effect µ * after n rounds of the above-mentioned OCO model which minimizes the learner's regret against the best fixed action in hindsight:Regret (n, F lin ; A) = n i=1 l i {μ i (O i-1 )} -inf n i=1 l i (µ) : µ ∈ F = n i=1 L i θi (O i-1 ) -inf n i=1 L i (θ) : θ ∈ Θ ,where A is the learner's OCO algorithm whose output is a sequence θi(O i-1 ) ∈ Θ : i ∈ [n] of parameters.If we compute the gradient of the loss function ( 21), one hasEQUATION)For the current linear function approximation setting, we implement the OGD algorithm (Algorithm 4) as a sub-routine of Algorithm 1. By using the same arguments as in Section 3.5.1, one can reproduce the following regret guarantee of Algorithm 4 whose proof is available at Appendix B.5. Theorem 3.4 (Regret guarantee of Algorithm 4). With Assumption 1, the OGD algorithm (Algorithm 4) with learning ratesEQUATION)Algorithm 4 Online gradient descent (OGD) algorithm for linear function approximation.Require: the radius R > 0 of the parameter space, the number of rounds n ∈ N, and a sequence of learning rates{η i ∈ (0, +∞) : i ∈ [n -1]}. 1: We first choose an arbitrary initial point θ1 (∅) ∈ Θ, where Θ := B (0 d ; R); 2: for i = 1, 2, • • • , n -1, do 3: Observe a triple (X i , A i , Y i ) ∈ O; 4:Update θi+1 (O i ) ∈ Θ according to the following OGD update rule:EQUATIONwhere Π Θ [•] : R d → Θ denotes the projection map of R d onto the parameter space Θ. 5: end for6: return the estimates μi (O i-1 ) := θi (O i-1 ) ⊤ ϕ ∈ F lin : i ∈ [n] of the treatment effect.General function approximation Lastly, we demonstrate the consequences of our general theory established in Sections 3.3 and 3.4 for the case of general function approximation: the function class F ⊆ (X × A → [-L, L]) can be arbitrarily chosen. Our further discussion this case heavily relies on the basic theory of online non-parametric regression from [45] whose technical details are rather long and complicated. So, we defer our detailed inspection on the case of general function approximation to Appendix B.6. 
lower bounds: local minimax risk: 
 We turn our attention to a local minimax lower bound for estimating the off-policy value τ * = τ (I * ).Here, we aim at establishing lower bounds that hold uniformly over all estimators that are permitted to know both the propensity scores{π * i (X i , O i-1 ; A i ) : i ∈ [n]} and the evaluation function g. We assume the existence of a constant K ≥ 1 and reference Markov policiesEQUATION1 K ≤ π i (x, a) π * i (x, o i-1 ; a) ≤ K (25) for all (x, o i-1 , a) ∈ X × O i-1 × A, where π i (x, •) := dΠi( •|x) dλ A : A → R + for each context x ∈ X.Proximity of behavioral policies to certain Markov policies is often assumed under adaptive data collection procedures. For instance, in Theorem 1 of [67] , the authors assumed that the sequence of behavior policies is eventually Markov; see the equation ( 8) therein.Given any problem instance I * = (Ξ * , Γ * ) ∈ I and an error function δ : X × A → R + , we consider the following local neighborhoods:N (Ξ * ) := Ξ ∈ ∆(X) : KL (Ξ ∥Ξ * ) ≤ 1 n ; N δ (Γ * ) := {Γ ∈ (X × A → ∆(Y)) : |µ(Γ)(x, a) -µ (Γ * ) (x, a)| ≤ δ(x, a), ∀(x, a) ∈ X × A} ,where for any given Γ :X × A → ∆(Y), let µ(Γ)(x, a) := Y yΓ ( dy| x, a) for each (x, a) ∈ X × A.Our goal is to lower bound the following local minimax risk:EQUATIONwhere C δ (I * ) := N (Ξ * ) × N δ (Γ * ) ⊆ I. We now specify some assumptions necessary for lower bounding the local minimax risk (26) . Prior to this, we introduce a new important notation: given any random variable Y ∈ L 4 (Ω, F, P) defined on a probability space (Ω, F, P), its (2, 4)-moment ratiois defined as ∥Y ∥ 2→4 := √ E[Y 4 ] E[Y 2 ] . Assumption 3. Let h(x) := ⟨g(x, •), µ * (x, •)⟩ λ A -E X∼Ξ * ⟨g(X, •), µ * (X, •)⟩ λ A .We assume thatH 2→4 := ∥h∥ 2→4 = √ E X∼Ξ * [h 4 (X)] E X∼Ξ * [h 2 (X)] < +∞.We next make an assumption on a lower bound on the local neighborhood size:EQUATIONfor all (x, a, i)∈ X × A × [n].We note that Assumptions 3 and 4 are analogues of Assumptions (MR) and (LN) considered in [42] , respectively, for the case of adaptively collected data. Under these assumptions, one can prove the following lower bound on the local minimax risk over C δ (I * ): Theorem 4.1. Under Assumptions 3 and 4, the local minimax risk over C δ (I * ) is lower bounded byEQUATIONwhere C(K) > 0 is a universal constant that only depends on the data coverage constant K ≥ 1 of the reference Markov policiesΠ i (•) : X → ∆(A) : i ∈ [n] defined in (25).The proof of Theorem 4.1 can be found in Appendix C.1. This result delivers a key message: the termv 2 *n including the sequentially weighted ℓ 2 -norm is indeed the fundamental limit for estimating the linear functional based on adaptively collected data. Our results can be viewed as a generalization of those developed in [42] for the case of i.i.d. data.The following lemma is useful for the truncation arguments used in the proofs of our local minimax lower bounds. In particular, it enables to make small modifications on a pair of probability measures by conditioning on good events of each probability measure, without inducing an overly large change in the total variation distance. Lemma A.1. Let (µ, ν) be a pair of probability measures defined on a common sample space (Ω, F), and consider any two events A, B ∈ F satisfying min {µ(A), ν(B)} ≥ 1 -ϵ for some ϵ ∈ 0, 1 4 . Then, the conditional distributions (µ|A) (•) ∈ ∆ (Ω, F) and (ν|B) (•) ∈ ∆ (Ω, F) defined by(µ|A) (E) := µ (A ∩ E) µ(A) and (ν|B) (E) := ν (B ∩ E) ν(B)for any event E ∈ F, satisfy the boundEQUATION)Proof of Lemma A.1. Due to the triangle inequality for the total variation (TV) distance, it follows thatEQUATIONandEQUATIONAt this point, one can easily observe thatEQUATIONPutting the observation (32) into the inequalities (30) and (31) , the assumptions 1 -µ(A) ≤ ϵ and 1 -ν(B) ≤ ϵ establish the desired result.B Proofs and omitted details for Section 3B.1 Proof of Proposition 3.1First, one can observe thatEQUATION+ ⟨f i (X i , O i-1 , •) , π * i (X i , O i-1 ; •)⟩ λ A (X i , H i-1 ) = 1 n n i=1 E I * A g (X i , a) µ * (X i , a) dλ A (a) -⟨f i (X i , O i-1 , •) , π * i (X i , O i-1 ; •)⟩ λ A + ⟨f i (X i , O i-1 , •) , π * i (X i , O i-1 ; •)⟩ λ A = τ (I * ) .We now assume (3) and note thatEQUATIONOne can reveal thatEQUATION-{τ(I * )} 2 (a) = E I * g 2 (X i , A i ) σ 2 (X i , A i ) (π * i ) 2 (X i , O i-1 ; A i ) + E I * g (X i , A i ) µ * (X i , A i ) π * i (X i , O i-1 ; A i ) -⟨g (X i , •) , µ * (X i , •)⟩ λ A -f i (X i , O i-1 , A i ) 2 + E I * ⟨g (X i , •) , µ * (X i , •)⟩ 2 λ -{τ (I * )} 2 = Var X∼Ξ * ⟨g(X,•),µ * (X,•)⟩ λ A = E I * g 2 (X i , A i ) σ 2 (X i , A i ) (π * i ) 2 (X i , O i-1 ; A i ) + E I * g (X i , A i ) µ * (X i , A i ) π * i (X i , O i-1 ; A i ) -⟨g (X i , •) , µ * (X i , •)⟩ λ A -f i (X i , O i-1 , A i ) 2 + Var X∼Ξ * ⟨g (X, •) , µ * (X, •)⟩ λ A ,where the step (a) can be verified as follows:E I * g (X i , A i ) µ * (X i , A i ) π * i (X i , O i-1 ; A i ) -f i (X i , O i-1 , A i ) 2 = E I * E I * g (X i , A i ) µ * (X i , A i ) π * i (X i , O i-1 ; A i ) -f i (X i , O i-1 , A i ) 2 (X i , H i-1 ) = E I * Var I * g (X i , A i ) µ * (X i , A i ) π * i (X i , O i-1 ; A i ) -f i (X i , O i-1 , A i ) (X i , H i-1 ) + E I *           E I * g (X i , A i ) µ * (X i , A i ) π * i (X i , O i-1 ; A i ) -f i (X i , O i-1 , A i ) (X i , H i-1 ) = ⟨g(Xi,•),µ * (Xi,•)⟩ λ      2      = E I * g (X i , A i ) µ * (X i , A i ) π * i (X i , O i-1 ; A i ) -⟨g (X i , •) , µ * (X i , •)⟩ λ A -f i (X i , O i-1 , A i ) 2 + E I * ⟨g (X i , •) , µ * (X i , •)⟩ 2 λ A .Next, we compute CovEQUATIONg (X j , A j ) µ * (X j , A j ) π * j (X j , O j-1 ; A j ) -f j (X j , O j-1 , A j ) (X j , H j-1 ) -{τ (I * )} 2 = E I * g (X i , A i ) Y i π * i (X i , O i-1 ; A i ) -f i (X i , O i-1 , A i ) ⟨g (X j , •) , µ * (X j , •)⟩ λ A -{τ (I * )} 2 = E I * E I * g (X i , A i ) Y i π * i (X i , O i-1 ; A i ) -f i (X i , O i-1 , A i ) ⟨g (X j , •) , µ * (X j , •)⟩ λ A H j-1 -{τ (I * )} 2 (b) = 0,where the step (b) holds due to the fact that X j is independent of the historical data H j-1 , which immediately yieldsX j | H j-1 d = X j ∼ Ξ * (•).Taking two pieces (35) and (36) collectively into the equation (34) , one hasn • Var I * τ f n (O n ) = Var X∼Ξ * ⟨g(X, •), µ * (X, •)⟩ λ A + 1 n n i=1 E I * g 2 (X i , A i ) σ 2 (X i , A i ) (π * i ) 2 (X i , O i-1 , A i ) +E I * g (X i , A i ) µ * (X i , A i ) π * i (X i , O i-1 ; A i ) -⟨g (X i , •) , µ * (X i , •)⟩ λ A -f i (X i , O i-1 , A i ) 2 ,as desired.We first single out a key technical lemma throughout this section that plays a crucial role in the proof of Theorem 3.1.Lemma B.1. The following results hold:(i) It holds that E I * Γi (O i ) (X i , H i-1 ) = ⟨g (X i , •) , µ * (X i , •)⟩ λ A for all i ∈ [n].Therefore, one hasEQUATION(ii) For every 1 ≤ i < j ≤ n, we haveCov I * Γi (O i ) , Γj (O j ) = 0; (iii) For every i ∈ [n],VarEQUATIONProof of Lemma B.1.(i) From the definition of Γi (•) : O i → R in (9), we haveEQUATIONThus, we obtainEQUATIONas desired.(ii) One can reveal thatCov I * Γi (O i ) , Γj (O j ) = E I * Γi (O i ) E Γj (O j ) (X j , A j , H j-1 ) -{τ (I * )} 2 = E I * Γi (O i ) g (X j , A j ) π * j (X j , O j-1 ; A j ) {µ * (X j , A j ) -μj (O j-1 ) (X j , A j )} + ⟨g (X j , •) , μj (O j-1 ) (X j , •)⟩ λ A -{τ (I * )} 2 (41) = E I * Γi (O i ) E I * g (X j , A j ) π * j (X j , O j-1 ; A j ) {µ * (X j , A j ) -μj (O j-1 ) (X j , A j )} + ⟨g (X j , •) , μj (O j-1 ) (X j , •)⟩ λ A (X j , H j-1 ) -{τ (I * )} 2 = E I * Γi (O i ; g) ⟨g (X j , •) , µ * (X j , •)⟩ λ A -{τ (I * ; g)} 2 (a) = 0,where the step (a) holds due to the facts that Γi (O i ) is H j-1 -measurable and X j ⊥ ⊥ H j-1 , together with the equation (37) .(iii) It follows thatVar I * Γi (O i ) = E I * Var I * Γi (O i ) (X i , H i-1 ) + Var I * E I * Γi (O i ) (X i , H i-1 ) (b) = E I * E I * Var I * Γi (O i ) (X i , A i , H i-1 ) (X i , H i-1)EQUATION+ Var X∼Ξ * ⟨g(X, •), µ * (X, •)⟩ λ A = E I * g 2 (X i , A i ) σ 2 (X i , A i ) (π * i ) 2 (X i , O i-1 ; A i ) + E I * Var I * g (X i , A i ) π * i (X i , O i-1 ; A i ) {µ * (X i , A i ) -μi (O i-1 ) (X i , A i )} (X i , H i-1 ) + Var X∼Ξ * ⟨g(X, •), µ * (X, •)⟩ λ A ,as desired, where the step (b) follows from the fact (40) . Now, it's time to finish the proof of Theorem 3.1. One can reveal thatE I * τ AIPW n (O n ; g) -τ (I * ; g) 2 (a) = 1 n 2 n i=1 Var I * Γi (O i ; g) (b) ≤ 1 n 2 n i=1 Var X∼Ξ * ⟨g (X, •) , µ * (X, •)⟩ λ A + E I * g 2 (X i , A i ) σ 2 (X i , A i ) (π * i ) 2 (X i , O i-1 ; A i ) +E I * g 2 (X i , A i ) {µ * (X i , A i ) -μi (O i-1 ) (X i , A i )} 2 (π * i ) 2 (X i , O i-1 ; A i ) (c) = 1 n v 2 * + 1 n n i=1 E I * g 2 (X i , A i ) {μ i (O i-1 ) (X i , A i ) -µ * (X i , A i )} 2 (π * i ) 2 (X i , O i-1 ; A i ) ,where the step (a) holds from the part (ii) of Lemma B.1, the step (b) makes use of the inequality (38) , and the step (c) follows from the definition of v 2 * in (7).It holds due to the observation ( 12) thatE I * n i=1 l i {μ i (O i-1 )} = n i=1 E I * [E I * [ l i {μ i (O i-1 )}| (H i-1 , X i , A i )]] = n i=1 E I * g 2 (X i , A i ) (π * i ) 2 (X i , O i-1 ; A i ) σ 2 (X i , A i ) + {μ i (O i-1 ) (X i , A i ) -µ * (X i , A i )} 2 = n ∥σ∥ 2 (n) + n i=1 E I * g 2 (X i , A i ) {μ i (O i-1 ) (X i , A i ) -µ * (X i , A i )} 2 (π * i ) 2 (X i , O i-1 ; A i ) ,which establishes the following expression of the estimation error term (11) :1 n n i=1 E I * g 2 (X i , A i ) {μ i (O i-1 ) (X i , A i ) -µ * (X i , A i )} 2 (π * i ) 2 (X i , O i-1 ; A i ) = 1 n E I * n i=1 l i {μ i (O i-1 )} -∥σ∥ 2 (n) (43) = 1 n E I * [Regret (n; A)] + 1 n E I * inf n i=1 l i (µ) : µ ∈ F -∥σ∥ 2 (n) .At this point, one can realize thatEQUATION) (a) = inf 1 n n i=1 E I * g 2 (X i , A i ) (π * i ) 2 (X i , O i-1 ; A i ) σ 2 (X i , A i ) + {µ (X i , A i ) -µ * (X i , A i )} 2 : µ ∈ F = ∥σ∥ 2 (n) + inf ∥µ -µ * ∥ 2 (n) : µ ∈ F ,where the step (a) holds by the fact (12) . Taking two pieces ( 43) and ( 44) collectively, it follows thatEQUATIONHence, the upper bound (15) on the MSE of the AIPW estimator ( 8) is an immediate consequence of the inequality (45) by putting it into the bound (10) in Theorem 3.1.One can easily observe from the equation ( 17) for every µ ∈ F thatEQUATIONwhich holds due to Assumption 1 together with the fact Y = [-L, L]. So it turns out that the loss function ( 14) is Lipschitz continuous with parameter G := 4LB 2 P n I * -almost surely. Hence, the desired conclusion immediately follows by Theorem 3.1 in [18] with parameter G = 4LB 2 .One can realize from the equation ( 22) that P n I * -almost surely,EQUATIONwhich holds by Assumption 1 together with the facts Y = [-L, L] and sup (x,a)∈X×A ∥ϕ(x, a)∥ 2 ≤ 1.So, the loss function ( 21) is Lipschitz continuous with parameter G := 2B 2 (L + R) P n I * -a.s. Hence, the desired result follows by Theorem 3.1 in [18] with parameter G = 2B 2 (L + R) and D = 2R.Lastly, we consider the most challenging setting where the estimation of the treatment effect µ * (•, •) : X × A → R is parameterized by general function classes. Under Assumption 1, one first observes from the MSE bound (10) of the AIPW estimator (8) in Theorem 3.1 thatEQUATIONFrom the last term in the MSE bound (48) , our aim becomes to control an upper bound of the termEQUATIONin the finite sample regime. Towards achieving this goal, we consider the online non-parametric regression problem described in Algorithm 2 whose sequence {l i (•) :(X × A → R) → R : i ∈ [n]}of loss functions defined as ( 14) is superseded byl i (•) : (X × A → R) → R : i ∈ [n] ,whereEQUATIONIt is straightforward to see for every i ∈ [n] thatEQUATION)With this modified online non-parametric regression problem, we now aim to minimize the learner's modified regret defined as follows:Regret n, F; A :=EQUATIONwhere A denotes the learner's online non-parametric regression algorithm that returns a sequence ofestimates {μ i (O i-1 ) ∈ (X × A → R) : i ∈ [n]} of the treatment effect based on interactions with the environment which selects modified loss functions l i (•) :(X × A → R) → R : i ∈ [n] . Theorem B.1. The AIPW estimator (8) based on a sequence {μ i (O i-1 ) ∈ (X × A → R) : i ∈ [n]}of estimates for the treatment effect µ * produced by making use of an online non-parametric regression algorithm A against the environment which chooses the sequence of modified loss functions (50) enjoys the following upper bound on the MSE:l i (•) : (X × A → R) → R : i ∈ [n] defined inEQUATION)Proof of Theorem B.1. It follows from the property ( 51) thatE I * n i=1 l i {μ i (O i-1 )} = n i=1 E I * E I * l i {μ i (O i-1 )} (F i-1 , X i , A i ) = n i=1 E I * σ 2 (X i , A i ) + {μ i (O i-1 ) (X i , A i ) -µ * (X i , A i )} 2 = n i=1 E I * σ 2 (X i , A i ) + n i=1 E I * {μ i (O i-1 ) (X i , A i ) -µ * (X i , A i )} 2 ,which leads to the following expression of the estimation error term (49):1 n n i=1 E I * {μ i (O i-1 ) (X i , A i ) -µ * (X i , A i )} 2 = 1 n E I * n i=1 l i {μ i (O i-1 )} - 1 n n i=1 E I * σ 2 (X i , A i ) (54) = 1 n E I * Regret n; A + 1 n E I * inf n i=1 l i (µ) : µ ∈ F (55) - 1 n n i=1 E I * σ 2 (X i , A i ) .Here, one may observe thatEQUATION) (a) = inf 1 n n i=1 E I * σ 2 (X i , A i ) + {µ (X i , A i ) -µ * (X i , A i )} 2 : µ ∈ F = 1 n n i=1 E I * σ 2 (X i , A i ) + inf 1 n n i=1 E I * {µ (X i , A i ) -µ * (X i , A i )} 2 : µ ∈ F ,where the step (a) holds by the fact (51) . Putting two pieces ( 54) and ( 56) together yieldsEQUATIONHence, the desired result (53) on the MSE of the AIPW estimator ( 8) is a straightforward consequence of the inequality ( 57) by plugging it into the bound (48) .Here, we remark that aside from the optimal variance v 2 * , the MSE bound (53) shows two additional terms: (i) the expected regret relative to the number of rounds n, where the expectation is taken over O n ∼ P n I * (•); and (ii) the approximation error term whose form is slightly different from the oneinf ∥µ -µ * ∥ 2 (n) : µ ∈ F appeared in the MSE bound (15) of Theorem 3.2.Non-asymptotic theory of online non-parametric regression Before delving into the investigation of the modified regret ( 52), we briefly recap the main results in [45] that establishes a theoretical framework of online non-parametric regression. In contrast to most existing works of online regression, the authors do NOT start from an algorithm, but instead directly work with the minimax regret in [45] . We will be able to extract a (not necessarily efficient) algorithm after taking a closer look at the minimax regret. Let us use ⟪• • • ⟫ n i=1 to denote an interleaved application of the operators inside repeated over n rounds. With this notation in hand, the minimax regret of the online non-parametric regression problem for estimation of the treatment effect can be written asEQUATIONwhereF ⊆ (X × A → [-L, L]) is a pre-specified function class. One of the key tools in the study of estimators based on i.i.d. data is the symmetrization technique [15, 62] . Under the i.i.d. scenario, one can investigate the supremum of an empirical process conditionally on the data by introducing Rademacher random variables, which is NOT directly applicable given the adaptive nature of our main problem. In the online prediction scenario, such a symmetrization technique becomes more subtle and it requires the notion of a binary tree, the smallest entity which captures the sequential nature of the problem in some sense. Towards achieving our goal in our problem, let us state some definitions. Definition B.1. Let S be a measurable state space. An S-valued tree of depth n is a rooted complete binary tree with nodes labeled by elements of the state space S: the sequence s = (s 1 , s 2 , • • • , s n ) of labeling functions s i (•) : {±1} i-1 → S which provides the labels of each node. Here, s 1 ∈ S is the label for the root of the tree, while s i for 2 ≤ i ≤ n is the label of the node obtained by following the path of length i-1 from the root, with +1 indicating right and -1 indicating left. A path of length n is given by the sequenceϵ 1:n = (ϵ 1 , • • • , ϵ n ) ∈ {±1} n . Given any measurable function ϕ(•) : S → R, ϕ(s) is an R-valued tree of depth n with labeling functions (ϕ • s i ) (•) : {±1} i-1 → R for level i ∈ [n](or, in words, the evaluation of ϕ(•) : S → R, ϕ(s) on s). Lastly, we let Tree (S, n) denote the set of all S-valued trees of depth n.Here, one may think of the sequence of functions {s i (•) : i ∈ [n]} defined on the underlying sample space as a predictable stochastic process with respect to the dyadic filtration {σ (ϵ 1:i ) : i ∈ [n]}. Next, let us define the notion of a sequential β-cover quantifies one of the key complexity measures of a function class G ⊆ (S → R) evaluated on the predictable process: the sequential covering number. Definition B.2 (Sequential covering numbers [46] ).(i) Define the following random pseudo-metric between two R-valued trees u = (u i :EQUATIONEQUATIONwhere G(s) := {g(s) : g ∈ G} ⊆ Tree (R, n);(iii) The sequential β-covering number with respect to l p -norm of a function class G ⊆ (S → R) on an S-valued tree s of depth n, where p ∈ [1, +∞], is defined byN p (β, G, s) := min {|V | : V ⊆ Tree (R, n) is a sequential β-cover w.r.t. l p -norm of G on s} .Let us further define N p (β, G, n) := sup {N p (β, G, s) : s ∈ Tree (S, n)} to be the maximal sequential β-covering number with respect to l p -norm of G over S-valued trees of depth n. Now, we will refer to log N p (β, G, n) as the sequential β-metric entropy of G with respect to l p -norm.In particular, we are going to study the behavior of the minimax regret V n (F) for the case where the sequential metric entropy of F ⊆ (X × A → [-L, L]) w.r.t. l 2 -norm grows polynomially as the scale β decreases:EQUATION)Let us also consider the parametric "p = 0" case when the sequential covering number of F with respect to l 2 -norm itself behaves as:EQUATION)For instance, the function class F := f θ (•) : R d → R : θ ∈ Θ for the linear regression problem in a bounded measurable subset Θ ⊆ R d , where the function f θ (•) : R d → R is given by f θ (x) := θ ⊤ x for θ ∈ R d , satisfies the condition (62) . By employing the main results (in particular, Theorem 2) in [45] , one can establish the following conclusion:Theorem B.2 (The rates of convergence of the minimax regret). Given any function class F ⊆ (X × A → [-L, L]) with sequential metric entropy growth log N 2 (β, F, n) ≤ β -p for p ∈ (0, +∞), it holds that (i) for p ∈ (2, +∞), the minimax regret (58) is bounded asEQUATION)(ii) for p ∈ (0, 2), the minimax regret (58) is bounded asEQUATION)(iii) for p = 2, the minimax regret (58) is bounded asEQUATION)(iv) for the parametric case (62), the minimax regret (58) is bounded asEQUATION) (v) if the function class F ⊆ (X × A → [-L, L]) is a finite set, the minimax regret (58) is bounded asEQUATION)It is shown in [45] that the upper bounds (i)-(iv) on the minimax regret (58) in Theorem B.2 are tight up to logarithmic factors. See Theorem 3 therein for further details.Although Theorem B.2 characterizes the rates of convergence of the minimax regret (58) in various scenarios statistically, its proof is non-constructive in the sense that the regret bounds therein are established without explicitly constructing an algorithm. In order to provide a general algorithmic framework for the problem of online non-parametric regression, we follow the abstract relaxation recipe proposed in [47] . It was shown in [47] that if one can find a sequence of mappings from the observed data to real numbers Rel n , often called a relaxation, satisfying some desirable conditions, then one can construct estimators based on such relaxations. To be specific, we search for a relaxation Rel n (•, •) :n k=0 (X × A) k × [-L, L]k → R that satisfies the following two conditions:EQUATIONwhere (x, a)EQUATIONfor any k ∈ [n] and any x k ∈ X. Regret (n, F; Alg. 5)A relaxation Rel n (•, •) : n k=0 (X × A) k × [-L, L] k → R satisfying AssumptionsEQUATIONWe further notice that if the functiony i ∈ [-L, L] → (ŷ -y i ) 2 + Rel n (((x, a) 1:i ) , (y 1:i-1 , y i ))is convex for every (ŷ, x 1:n , a 1:n , y1:i-1 ) ∈ [-L, L] × X n × A n × [-L, L] i-1 and i ∈ [n], then the prediction rules (71) and (72) becomes much simpler, since the supremum over y i ∈ [-L, L] is attained either L or -L. The prediction rules then can be written asEQUATIONand for i ∈ {2, 3,EQUATIONOne can easily observe that the prediction rules ( 73) and ( 74) can be further simplified asEQUATIONAlgorithm 5 A generic forecaster based on the relaxation recipe proposed in [47] Require: a relaxation Rel n (•, •) :EQUATION: for i = 2, 3, • • • , n, do 3: Observe a triple (X i , A i , Y i ) ∈ O; 4:We compute μi (O i-1 ) ∈ (X × A → R) according to the following rule:EQUATION5: end for 6: return the sequence of estimatesEQUATIONwhereχ [-L,L] (•) : R → [-L, L] defines a clip function onto the interval [-L, L], i.e., χ [-L,L] (x) :=    L if x > L; x if -L ≤ x ≤ L; -L otherwise.By directly using Lemma 16 in [45] , one can obtain the following significant result:EQUATIONwhere the pair (z, m) ranges over the set Tree (X × A, n) × Tree (R, n), is an admissible relaxation. As a direct consequence of the regret bound (70), Algorithm 5 using the admissible relaxation R n (•, •) as an input enjoys the regret bound of an offset Rademacher complexity: EQUATIONEQUATIONprovided that n ≥ 16H 2 2→4 . Lemma C.2. Under Assumption 4, the local minimax risk over the class C δ (I * ) is lower bounded byEQUATIONC.2 Proof of Lemma C.1The proof relies on Le Cam's two-point method by taking the outcome kernel Γ * : X × A → ∆(Y) to be fixed, and perturbing the context distribution Ξ * (•) ∈ ∆(X): we first construct a collection of context distributions {Ξ s (•) ∈ ∆(X) : s ∈ (0, +∞)}. Later, we will choose the parameter s > 0 small enough so that Ξ s ∈ N (Ξ * ) and two distributions P n (Ξs,Γ * ) ∈ ∆ (O n ) and P n (Ξ * ,Γ * ) ∈ ∆ (O n ) are indistinguishable, but large enough such that the functional values τ (Ξ s , Γ * ) and τ (Ξ * , Γ * ) are well-separated. Le Cam's two-point lemma (the equation (15.14) in [62] ) guarantees that the local minimax risk M n (C δ (I * )) is lower bounded asEQUATIONprovided that Ξ s ∈ N (Ξ * ).As the first step, we upper bound the total variation distance TV P n (Ξs,Γ * ) , P n (Ξ * ,Γ * ) . Thanks to the Pinsker-Csiszár-Kullback inequality, one hasEQUATIONWe can find that the density function of the lawP n I = P n (Ξ,Γ) ∈ ∆ (O n ) of the sample trajectory O n under the problem instance I = (Ξ, Γ) ∈ I with respect to the base measure (λ X ⊗ λ A ⊗ λ A )⊗n is given byEQUATIONUsing this fact, the KL-divergence KL P n (Ξs,Γ * ) P n (Ξ * ,Γ * ) can be computed asEQUATIONSo if one can show that Ξ s ∈ N (Ξ * ), then the equation (89) guarantees thatKL P n (Ξs,Γ * ) P n (Ξ * ,Γ * ) = n • KL ( Ξ s ∥ Ξ * ) ≤ 1,which can be taken collectively with the bound (87) to produce the following conclusion:EQUATION)With the arguments thus far in place, it remains to construct a family {Ξ s ∈ ∆(X) : s ∈ (0, +∞)} and then choose a parameter s > 0 such that Ξ s ∈ N (Ξ * ) and the functional values τ (Ξ s , Γ * ) and τ (Ξ * , Γ * ) are well-separated. To this end, we consider the function h(•) : X → R defined byh(x) := h(x) if |h(x)| ≤ 2H 2→4 E X∼Ξ * [h 2 (X)]; sign (h(x)) E X∼Ξ * [h 2 (X)] otherwise.Since H 2→4 ≥ 1, one can easily find that h(x) ≤ |h(x)| for all x ∈ X. Now for each s ∈ (0, +∞), we define the tilted probability measure Ξ s (•) ∈ ∆(X) byEQUATIONwhere Z(s) := X ξ * (x) exp s h(x) dλ X (x) = E X∼Ξ * exp s h(X) . At this point, we note for every x ∈ X thatEQUATIONwhich also immediately yieldsEQUATIONHere, we choose s =1 4∥h∥ L 2 (Ξ * ) √ n > 0.Then, it holds due to the fact h(x) ≤ 2H 2→4 ∥h∥ L 2 (Ξ * ) for all x ∈ X thatEQUATIONwhere the step (a) follows due to the assumption that n ≥ 16H 2 2→4 . Now, it's time to prove that Ξ s ∈ N (Ξ * ) for the current choice of the parameter s > 0. Due to Theorem 5 in [14] , it follows thatEQUATIONSo it suffices to upper bound the χ 2 -divergence χ 2 ( Ξ s ∥ Ξ * ). One can reveal that χ 2 ( Ξ s ∥ Ξ * ) = Var X∼Ξ * ξ s (X) ξ * (X) = 1 Z 2 (s) Var X∼Ξ * exp s h(X) ≤ 1 Z 2 (s) E X∼Ξ * exp s h(X) -1 2 (96) (b) ≤ exp 2s h ∞ E X∼Ξ * exp 2s h(X) • s 2 h2 (X) (c) ≤ exp 4s h ∞ • s 2 E X∼Ξ * h 2 (X) ,EQUATIONwhich implies Ξ s ∈ N (Ξ * ) for the choice of the parameter s =1 4∥h∥ L 2 (Ξ * ) √ n .Hence, the upper bound on the total variation distance (90) turns out to be valid.Next, we lower bound the gap between the functional values τ (Ξ s , Γ * ) and τ (Ξ * , Γ * ). It holds thatEQUATION)Since s h ∞ ≤ 1 8 , we have s h(X) ∈ -1 4 , 1 4 and therefore the simple inequalityEQUATION,EQUATION) (f) ≥ s 2 E X∼Ξ * h 2 (X) -s 2 H 2→4 E X∼Ξ * h 2 (X) 3 2 = ∥h∥ L 2 (Ξ * ) 8 1 √ n - H 2→4 2n (g) ≥ ∥h∥ L 2 (Ξ * ) 16 √ n ,where the step (d) holds due to the fact that sign (h(x)) = sign h(x) , ∀x ∈ X, the step (e) makes use of the property that h(x) ≤ |h(x)|, ∀x ∈ X, together with the Cauchy-Schwarz inequality, the step (f) follows due to Lemma 7 in [42] , and the step (g) utilizes the assumption that n ≥ 16H 2 2→4 . Putting the lower bound (99) into the equation (98) yieldsEQUATIONwhere the step (h) holds since E X∼Ξ * exp s h(X) ≤ 3 2 , which follows by the fact s h(X) ≤ 1 8 . Finally, by taking three pieces (86), (90), and (100) collectively, one completes the proof of Lemma C.1.The proof Lemma C.2 is also heavily relies Le Cam's two-point method. For each (i, s, z) ∈ Then, due to Le Cam's two-point lemma, the local minimax risk over the class C δ (I * ) can be lower bounded byEQUATIONprovided that Γ i (zs) ∈ N δ (Γ * ) for z ∈ {±1}.We first upper bound the total variation distance TV P n (Ξ * ,Γi(s)) , P n (Ξ * ,Γi(-s)) . By employing the Pinsker-Csiszár-Kullback inequality, one hasEQUATIONThe KL-divergence KL P n (Ξ * ,Γi(s)) P n (Ξ * ,Γi(-s)) can be computed asEQUATIONNote thatEQUATIONBy utilizing the fact (105), one can obtain from the equation (104) thatKL P n (Ξ * ,Γi(s)) P n (Ξ * ,Γi(-s)) = n i=1 E (Ξ * ,Γi(s)) E (Ξ * ,Γi(s)) sg (X i , A i ) π i (X i , A i ) {2Y i -µ i (s) (X i , A i ) -µ i (-s) (X i , A i )} (X i , A i , H i-1 ) = n i=1 E (Ξ * ,Γi(s)) sg (X i , A i ) π i (X i , A i ) {µ i (s) (X i , A i ) -µ i (-s) (X i , A i )} = 2s 2 n i=1 E (Ξ * ,Γi(s)) g 2 (X i , A i ) σ 2 (X i , A i ) π 2 i (X i , A i ) (106) = 2s 2 n i=1 E I * g 2 (X i A i ) σ 2 (X i , A i ) π 2 i (X i , A i ) (a) ≤ 2K 2 s 2 n i=1 E I * g 2 (X i , A i ) σ 2 (X i , A i ) (π * i ) 2 (X i , O i-1 ; A i ) = 2K 2 s 2 n ∥σ∥ 2 (n) ,where the step (a) follows by the assumption (25) . If we put s =1 2K √ n∥σ∥ (n)into the bound (106), it follows that KL P n (Ξ * ,Γi(s)) P n (Ξ * ,Γi(-s)) ≤ 1 2 . So, by combining this conclusion together with the basic inequality (103), we arrive atEQUATION)At this point, we should note for every (i, z, x, a)EQUATIONwhere the step (b) holds due to Assumption 4, and the step (c) utilizes the fact that K ≥ 1, which establishes that Γ i (zs) ∈ N δ (Γ * ) for z ∈ {±1} and thus the local minimax lower bound (102) turns out to be valid.Next, we aim at establishing a lower bound on the gap between the functional values τ (Ξ * , Γ i (s)) and τ (Ξ * , Γ i (-s)). One can observe thatτ (Ξ * , Γ i (s)) -τ (Ξ * , Γ i (-s)) = E X∼Ξ * ⟨g(X, •), µ i (s)(X, •) -µ i (-s)(X, •)⟩ λ A = 2s • E I * A g 2 (X i , a) σ 2 (X i , a) π i (X i , a) dλ A (a) (d) ≥ 2s K • E I * A g 2 (X i , a) σ 2 (X i , a) π * i (X i , O i-1 ; a) dλ A (a) (109) = 2s K • E I * g 2 (X i , A i ) σ 2 (X i , A i ) (π * i ) 2 (X i , O i-1 ; A i ) = 1 K 2 √ n ∥σ∥ (n) E I * g 2 (X i , A i ) σ 2 (X i , A i ) (π * i ) 2 (X i , O i-1 ; A i ) ,where the step (d) holds due to the assumption (25) . By taking three pieces (102), (107), and (109) collectively, we haveEQUATIONfor every i ∈ [n]. Hence, one can conclude by taking an average of the local minimax lower bound (110EQUATIONwhere the step (e) makes use of the Cauchy-Schwarz inequality.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA]Justification: We don't have experimental results in this paper.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA]Justification: We don't have experimental results in this paper.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: We don't have experimental results in this paper.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). Justification: This paper is mostly theoretical, and is not tied to a particular application. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix:  


Decision: This is a significant piece of theory work that presents finite sample bound for AIPW estimators. While concerns have been raised regarding related work, clarity of writing and lack of experimental evaluations, all of them have been addressed during the rebuttal period. Therefore I would recommend acceptance.

Reviews: review: paper_summary: paper_summary: This paper study the off-policy problem in the sequential decision setting with adaptively collected data. The authors propose to use augmented Inverse propensity weighting estimator to estimate the policy value and conduct extensive theoretical analysis on the estimator, including variance and mean square error. Based on the analysis, the authors propose the methods to learn the function estimator in AIPW estimators.
strength_weakness: strength_weakness: I am confused about the claim of "adaptive" and "online learning" in the title. The two words seems that the decision-maker can adaptively select the action during the decision process. However, it seems that the record (context, actions, outcomes) are passively observed in the problem. So I concern that the paper may be mis-positioned.

Therefore, the technical distinction between the sequential decision setting and static setting is not clearly presented. It seem to be a trivial extention of the traditional policy evaluations problem in the static setting.
questions: questions: The formulation of  perturbed IPW estimator in section 3.1 seems different with the doubly robust estimator.  Can the authors provide the connection between the perturbed IPW estimator and the doubly robust estimator in other papers. For example, the doubly robust estimators in [1].

[1] Miroslav Dudik, John Langford, and Lihong Li. 2011. Doubly robust policy evaluation and learning. In International Conference on International Conference on Machine Learning. 1097–1104.
limitations: limitations: I think the discussion of the limitation in the paper is not sufficient.
paper_summary: paper_summary: The paper investigates the challenge of estimating a linear functional of the treatment effect from adaptively collected data, commonly found in contextual bandits and causal inference studies. It introduces finite-sample upper bounds for the mean-squared error (MSE) of augmented inverse propensity weighting (AIPW) estimators and proposes a reduction scheme to minimize these bounds. The method is illustrated through three concrete examples. Additionally, the paper establishes a local minimax lower bound, demonstrating the instance-dependent optimality of the AIPW estimator.
strength_weakness: strength_weakness: -	Although the paper is primarily theoretical, it would be helpful if the authors could include some simulation experiments to verify the theoretical results. For example, it would be interesting to see how the regret converges in practice in the examples of Section 3.5.
-	It would be beneficial if the authors could provide more explanations regarding certain definitions. For example, the off-policy value is defined as the expectation of the inner product between $g$ and $\mu^*$, rather than, e.g., the expectation of $g$ itself. What is the rationale behind this definition? In addition, why is the perturbed IPW estimator considered over the traditional IPW estimator?
-	The paper has generalized the theory developed for i.i.d. data to adaptively collected data and discussed the technical difficulties in Section 3.2. Could the authors compare the results for i.i.d. data with those for adaptively collected data? Is there any efficiency loss when the data is collected adaptively?
questions: questions: See above.
limitations: limitations: Limitations have been discussed in the checklist.
paper_summary: paper_summary: This paper presents an approach to estimating linear functionals of the reward function in contextual bandit settings from adaptively collected data. They consider the class of augmented inverse propensity weighted (AIPW) estimators and prove guarantees about the quality of the estimator in terms of the quality of the plugin estimator of the mean reward. Specifically, they characterize the finite sample MSE of the AIPW estimator on adaptively collected data. They quality of the estimator (in terms of low MSE) depends on the quality of the plugin estimator of the mean. They relate online learning of the plugin estimator of the mean reward to online non-parametric regression; they then prove a regret bound, where regret relates to the quality of the plug-in estimator learned online.

***edited score based on rebuttal. See comment below***
strength_weakness: strength_weakness: - There is significant missing discussion of relevant related work on finite sample approaches for off policy evaluation in contextual bandits. For example "Anytime-valid off-policy inference for contextual bandits" by Waubly-Smith et al., "Off-Policy Confidence Sequences" by Karampatziakis et al. and "Optimal and Adaptive Off-policy Evaluation in Contextual Bandits" by Wang et al., as some examples. I would recommend the authors compare to these papers both theoretically and ideally experimentally as well.

- The main result the authors present that holds for general plug-in estimators of the mean is the derivation of the MSE upper bound for the AIPW estimator (Theorem 3.2) as a function of the "regret" of the plug-in estimator error. Beyond this the authors provide results for the plug-in estimators in tabular data settings (Theorem 3.3) and plug-in estimators that are linear models (Theorem 3.4). I feel this is a limited contribution in terms of the types of plug-in estimators the authors can provide guarantees for. 

- The main results presented in this work assume that the behavior has a constant exploration rate (Assumption 1). Other works on statistical inference after adaptive sampling generally can prove results when the exploration can decay.

- The writing is technically precise but extremely dense and often lacks sufficient context. I give explicit examples below:

(-) The final result in section 4 was extremely hard to parse. There is a mention of "mis-specification" in the section 4.1 title, but then there is no mention of mis-specification anywhere in the section itself. It is not easy to understand how the result presented in that section is related to mis-specification.

(-) There was little discussion as to why the pertubed IPW estimator was introduced in section 3.1, rather than just starting with the AIPW estimator in 3.2 (since there were no examples discussed of the perturbed IPW estimator that were not some version of an AIPW estimator). Furthermore, if the discussion in 3.1 is kept, the connection between these two estimators presented in 3.1 and 3.2 respectively needs to be made more explicitly. For example, explicitly relating AIPW if for a certain choice of $f$ these two estimators are the same.
questions: questions: - In line 97, I do not understand why $\mu$ is called a treatment effect. It is also called the "reward model" and appears to be the expected reward function (function of context and action). Why is this called a treatment effect? This is not what is "commonly referred to" as a treatment effect in the causal inference literature.
- In line 107 you state that its assumed the propensities are "revealed", does this mean known?
- Please define << notation used in 117
limitations: limitations: - A severe limitation of this work (especially compared to previous literature) is that they only provide guarantees about the mean squared error of the AIPW estimator and do not provide any approach to constructing confidence intervals for the quantities of interest. I would expect most people interested in using statistical inference methods on adaptively collected data (especially if data is small enough to warrant using a linear plug-in model or be in a tabular data setting) would care solely about estimation and not uncertainty quantification. As a result, the practical utility of this work is very limited. 

- There are no simulations demonstrating their approach in practice or comparing to other methods.

Comments: comment: We would like to thank the reviewer for engaging in the discussion. The classical empirical risk minimization (ERM) is not an appropriate strategy for estimation of the treatment effect $\mu^*$ in our setting for the following two reasons.

First, we would argue that online learning is a more natural strategy for estimation of the treatment effect $\mu^*$ in our setting, compared to the classical ERM. In view of Theorem 3.1 in our paper, we need to aim at building a sequence of estimates of the treatment effect $\mu^*$ that minimizes the weighted average estimation error in the equation (11). This objective naturally falls into the realm of online learning, where a sequence of decisions are made to minimize a sequence of certain loss functions. On the contrary, for the i.i.d. data collection model, one only needs to construct a single estimate $\hat{\mu}$ of the treatment effect $\mu^*$ that minimizes a certain weighted mean-squared error; see the equation (11) in [1] for the construction of the estimate. In this case, the classical ERM (the non-parametric weighted least-squares estimate for this case) is more natural.

Second, one could consider using the ERM in each step of the framework of online learning, i.e., an “adaptive” ERM. However, it is known that this algorithm may incur a linear regret in the worst case, which motivates us to employ no-regret learning algorithms such as the Follow-The-Regularized-Leader (FTRL; basically using the regularized ERM in each step) or its optimistic variants.

[1] Wenlong Mou, Martin J. Wainwright, and Peter L. Bartlett, “Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiency”, arXiv preprint arXiv:2209.13075, 2022.
Thanks for your response. I have get the meaning of "adaptive" and "online learning". However, I am still confused that why this problem needs the technology of online learning. Why ERM fails in this setting? Can you give me an example in practice to verify the practical significance？
Hello, I will raise my score a bit. I appreciate the addition of empirical evaluation and the addition of discussion to related work. This addresses bullet 1 of weaknesses I stated. Through rewriting it seems like bullets 2 and 4 can be addressed. My concerns are still bullet 3 and that the amount of edits needed (adding simulations results, and changing writing for bullets 2 and 4) are quite a lot of changes/addition that are not being reviewed.
Thank you for your thoughtful and detailed response to my comments. I have no further questions at this time. As noted by other reviewers, the paper introduces some concepts that are less commonly seen in the literature, making it essential to provide sufficient context and explanation. It appears that the current work is an extension of [1], which indeed provides more background. I recommend including more intuition and context in future revisions to enhance clarity.

[1] Mou, W., Wainwright, M.J. and Bartlett, P.L., 2022. Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiency. arXiv preprint arXiv:2209.13075.