{'fraction_non_alphanumeric': 0.05075084950126055, 'fraction_numerical': 0.01867075888779276, 'mean_word_length': 4.140871525169046, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Confidence Interval for Off-Policy Evaluation from Dependent Samples via Bandit Algorithm: Approach from Standardized Martingales

This study addresses the problem of off-policy evaluation (OPE) from dependent samples obtained via the bandit algorithm. The goal of OPE is to evaluate a new policy using historical data obtained from behavior policies generated by the bandit algorithm. Because the bandit algorithm updates the policy based on past observations, the samples are not independent and identically distributed (i.i.d.). However, several existing methods for OPE do not take this issue into account and are based on the assumption that samples are i.i.d. In this study, we address this problem by constructing an estimator from a standardized martingale difference sequence. To standardize the sequence, we consider using evaluation data or sample splitting with a two-step estimation. This technique produces an estimator with asymptotic normality without restricting a class of behavior policies. In an experiment, the proposed estimator performs better than existing methods, which assume that the behavior policy converges to a time-invariant policy.


Introduction
The multi-armed bandit (MAB) problem is one of the sequential decision-making problems, which is applied in various applications, such as ad-optimization, personalized medicine, search engines, and recommendation systems. In the MAB problem, we choose an action at a period and observe the outcome. To reduce the cost of searching for better policies, the evaluation of a new policy using historical data obtained from past trials has gathered great attention (Beygelzimer & Langford, 2009;Li et al., 2010;Athey & Wager, 2017). This framework is called off-policy evaluation (OPE) (Dudík et al., 2011;Wang et al., 2017;Narita et al., 2019;Bibaut et al., 2019;Kallus & Uehara, 2019a;Oberst & Sontag, 2019). Although several methods for OPE have been proposed, existing studies often presume that the samples are independent and identically distributed (i.i.d.). However, in the MAB problem algorithm, the policy is usually updated based on past observations, and the samples are not i.i.d. due to the policy updating process. In this case, the consistency and asymptotic normality of the existing methods are not guaranteed. In particular, the asymptotic normality is critical because it guarantees the √ n-consistency and is needed for the confidence interval in hypothesis testing to determine whether the new policy is better than the existing policy. Thus, the motivation for establishing a novel method for performing OPE from dependent samples is strong.
existing methods have several drawbacks. With the first approach, the assumption that the policy converges to a timeinvariant policy sometimes does not hold. For example, if the algorithms of the MAB problem change during past trials, it is difficult to justify this assumption. The second and third approaches cannot be applied in cases where the policy is sequentially updated, and the conditions of mixingales do not hold, respectively.
To overcome these drawbacks, in this study, we propose a novel estimator with the asymptotic normality, which does not assume policy convergence, the existence of batches, and the independence of time-separated samples. To accomplish this goal, we refocus on the first approach. In the first approach, we use a martingale difference sequence (MDS) for constructing an estimator. In this approach, the convergence of the policy used in past trials to the timeinvariant policy in probability is assumed for using central limit theorem (CLT) of an MDS, which requires that the variance of an MDS becomes asymptotically constant. In this paper, instead of assuming the convergence of the policy, we consider constructing an MDS with asymptotically constant variance by standardization using an estimator of the variance. To implement the standardization, we assume access to evaluation (test) data or conduct sample splitting. Through this technique, we can guarantee the asymptotic normality of the proposed estimator with fewer assumptions.
Contributions and Organization of this Paper: This paper has three main contributions. First, this paper provides a theoretical solution for causal inference from dependent samples obtained via bandit feedback, which is more realistic than the situation that has been often considered in the existing work. Second, the proposed estimator achieves the asymptotic normality with fewer assumptions compared with existing solutions. Third, the estimator also achieves a lower mean squared error (MSE) in experiments using benchmark datasets.
Additional Related Work: There are various studies for OPE under the assumption that samples are i.i.d. (Dudík et al., 2011;Wang et al., 2017;Narita et al., 2019;Bibaut et al., 2019;Kallus & Uehara, 2019a;Oberst & Sontag, 2019), but there are fewer studies focus on the case in which samples are not i.i.d. When the policy converges, der Laan & Mark (2008), Hadad et al. (2019), and Kato et al. (2020a) proposed using an estimator based on an MDS. When including the covariates for OPE, der Laan & Mark (2008) mainly suggested using targeted maximum likelihood estimation. On the other hand, Hadad et al. (2019) and Kato et al. (2020a) proposed using an estimator based on the doubly robust or augmented IPW estimator. Kallus & Uehara (2019b) dealt with the application of reinforcement learning and proposed an estimator constructed from dependent samples. In their study, they proposed time cross-fitting, which is a variant of cross-fitting of double/debiased machine learning (Chernozhukov et al., 2018). The theoretical guarantee is based on mixingale theory. For obtaining the asymptotic normality, conducting the standardization is also proposed by Luedtke & van der Laan (2016). Luedtke & van der Laan (2016) tries to solve a similar problem in the batch policy updating. In addition to this difference of policy updating, there are the following two points different from us. First, in their solution, they require estimators of f * and e * to satisfy some conditions like the Donsker condition. However, in our estimator, we do not impose such restrictions on estimators of f * and e * except for the boundedness. This difference is critical because, in practice, as Chernozhukov et al. (2018) pointed out, the estimators of f * and e * usually do not satisfy the Donsker condition when we use modern methods such as the Lasso and Random forest regression. Second, for obtaining an estimator with the asymptotic normality under sequential policy updating, we propose using evaluation data or sample splitting.

Problem Setting
In this section, we introduce our problem setting.

Date Generating Process
Let A t be the action taking variable in A = {1, 2, . . . , K}, X t be the covariate observed by the decision maker when choosing an action, and X be the domain of covariate. Let us denote a random variable of a reward at a period t as a function Y t : A → R. Let ½[·] be an indicator function. In this paper, we have access to a set of historical data, , with the following data generating process (DGP): , p(x) denote the density of the covariate X t , p t (a | x, Ω t−1 ) denote the probability of assigning an action A t conditioned on a covariate X t , p(y | a, x) denote the density of an outcome Y t conditioned on A t and X t , and Ω t−1 ∈ M t−1 denotes the history defined as Ω t−1 = {X t−1 , A t−1 , Y t−1 , . . . , X 1 , A 1 , Y 1 } with the domain M t−1 . We assume that p(x) and p(y | a, x) are invariant across periods, but p t (a | x, Ω t−1 ) can take different value across periods. Besides, we allow the decision maker to change p t (a | x, Ω t−1 ) based on past observations. In this case, samples (X t , A t , Y t ) behavior policies, which determine the probability p t (a | x, Ω t−1 ). Let a behavior policy π t : A×X ×M t−1 → (0, 1) in the t-th period be a function of a covariate X t , an action A t , and a history Ω t−1 . In this study, we assume that π t (a | x, Ω t−1 ) = p t (a | x, Ω t−1 ).
Remark 1 (Evaluation Data). In Section 4.3, we also assume that there is access to evaluation data, . In Remark 7, we relax this assumption by introducing the sample splitting.

Off-Policy Evaluation
Under the DGP defined in the previous subsection, we consider estimating the value of an evaluation policy using samples obtained under the behavior policies. Let an evaluation policy π e : A×X → (0, 1) be a function of a covariate X t and an action A t ; this evaluation policy can be considered as the probability of taking the action A t conditional on the covariate X t . We are interested in estimating the expected reward from a given pre-specified evaluation policy π e (a | x). Then, we define the expected reward under π e as R(π e ) := E K a=1 π e (a, X t )Y t (a) . We also denote R(π e ) as θ 0 . The goal of this study is to estimate R(π e ) using dependent samples under a sequentially-updated policy. To identify R(π e ), we make the following assumptions on the policies and the outcomes.
Assumption 1. The behavior policies π t (a | ·, Ω t−1 ) and the evaluation policy π e (a | ·) are known 1 . Additionally, the evaluation policy is deterministic.
The deterministic evaluation policy looks restrictive. However, the optimal policy that maximizes the expected reward is a deterministic policy when the policy is not restricted. Therefore, when we find the optimal policy from a set of policies, such as off-policy learning (Zhao et al., 2012;Kitagawa & Tetenov, 2018;Zhou et al., 2018;Chernozhukov et al., 2019), this assumption can be accommodated. Thus, restricting the policy class to the deterministic policy class would be reasonable in practice. In fact, most of the existing methods follow this way.
Remark 2 (Existing Methods for OPE). We review three types of standard estimators of R(π e ) under the case where p 1 (a | x) = p 2 (a | x) = · · · = p T (a | x) = p(a | x) in the DGP defined in (1). The first estimator is an inverse probability weighting (IPW) estimator given by 1  (Horvitz & Thompson, 1952;Rubin, 1987;Hirano et al., 2003). Although this estimator is unbiased when the behavior policy is known, it has a high variance. The second estimator is a direct method (DM) estimator is an estimator of f * (a, X t ) (Hahn, 1998). This estimator is known to be weak against model misspecification for f * (a, X t ). The third estimator is a doubly robust estimator defined as (Robins et al., 1994;Chernozhukov et al., 2018). Under certain conditions, it is known that this estimator achieves the lower bound (a.k.a semiparametric lower bound), which is the lower bound of the asymptotic MSE of OPE, among regular √ T -consistent estimators (van der Vaart, 1998, Theorem 25.20). Remark 3 (Unconfoundedness). Existing methods often make an assumption called unconfoundedness, that is, they assume that the outcomes (Y t (0), Y t (1), . . . , Y t (K)) and the action A t are conditionally independent on X t for identification. In the DGP, we can obtain a similar result from the assumption that an action A t is chosen according to probability p t (a | x, Ω t−1 ).
Remark 4 (Semiparametric Lower Bound). The lower bound of the variance can be defined for an estimator under some posited models of the DGP. If this posited model is a parametric model, then the lower bound is equal to the Cramér-Rao lower bound. When this posited model is a non-or semiparametric model, the corresponding lower bound can still be defined (Bickel et al., 1998). Narita et al. (2019) shows that the semiparametric lower bound of the DGP (1) under p 1 (a | x,

Notations: Let a be an action in
t (a) | x], and Var(Y t (a) | x) as f * (a, x), e * (a, x), and v * (a, x), respectively. Let F be the domain of f * (a, x). Letf t (a, x),ê t (a, x), andθ t be estimators of f * (a, x), e * (a, x), and θ 0 constructed from Ω t , respectively. Let N (µ, var) be the normal distribution with mean µ and variance var.

Policy Updating
In the DGP defined in Section 2.1, we allow the behavior policy π t (a | x, Ω t−1 ) to be updated based on past observations. For example, when applying some algorithms proposed in the MAB problem, we usually optimize the probability to maximize the cumulative reward using past observations. When the behavior policy π t (a | x, Ω t−1 ) depends on past observations, the samples are not i.i.d. In this case, we cannot apply the standard methods for OPE, which assume that the samples are i.i.d. To clarify this problem, we classify the patterns of policy updating into two scenarios: sequential policy updating and batch policy updating. In sequential policy updating, the policy can be updated each period. In batch policy updating, the policy is updated after observing some samples (Hahn et al., 2011;Narita et al., 2019). In this study, we consider a problem using sequential policy updating.

OPE under a Converging Policy
In this section, we review OPE when a policy converges to the time-invariant policy in probability. As der Laan & Mark (2008), Hadad et al. (2019) and Kato et al. (2020a) proposed, in such a situation, we can construct an estimator with the asymptotic normality by using an MDS (Hall et al., 2014). To conduct OPE when the behavior policy is known, we can use the following score function ψ : Chernozhukov et al., 2018): where Θ, Π t , and Π are spaces of a parameter θ, a behavior policies π t , and an evaluation policy π e . Then, for the true policy value θ 0 , the score function with π e ,f t−1 ] = 0. As we explain in Remark 2, there are several other candidate estimators, including the IPW estimator. However, the estimator based on the score function defined in (2) achieves the lowest asymptotic variance when π t is fixed among periods (Bickel et al., 1998;Scharfstein et al., 1999). Using ψ t θ 0 ; X t , A t , Y t , π t , π e ,f t−1 T t=1 , we consider constructing an MDS z t T t=1 that satisfies the conditions of the following CLT for an MDS.

Proposition 1.
[CLT for an MDS, Hamilton (1994), Proposition 7.9, p. 194 When Y t , π e /π t , and f t−1 are bounded, we can easily show that the condition (b) holds (Assumption 2). The remaining task is to show that conditions (a) and (c) hold.
Thus, by the assumption , the variance of h t converges to time-invariant value, and this property is the motivation of the assumption proposed by Kato et al. (2020a) can be proved to be consistent and has the asymptotic normality (Hadad et al., 2019;Kato et al., 2020a) 2 . We refer to this estimator as Adaptive AIPW (A2IPW). We can also define the corresponding IPW estimator and refer to it as adaptive IPW (AdaIPW) estimator.
Remark 5 (Efficiency of A2IPW). The asymptotic variance of the A2IPW estimator matches the semiparametric lower bound under a time-invariant policy α (Kato et al., 2020a).

OPE from Dependent Samples under Sequential Policy Updating
In this section, we discuss a strategy for constructing an estimator without assuming the convergence of the policy. Then, we show a method for constructing an estimator with the asymptotic normality.

Strategy for OPE from Dependent Samples under Sequential Policy Updating
However, there are various applications in which we cannot assume that π t (a | x, Ω t−1 ) p − → α(a | x). Therefore, we have a strong motivation for constructing an estimator with asymptotic normality without assuming that π t (a | x, we can show that the estimator has the asymptotic normality as follows.
Theorem 1. Suppose that there exists C 2 such that |f t | ≤ C 2 . Then, under Assumption 2, Besides, we can show thatz t is bounded from assumptions, and 1/T T t=1z 2 t p − → 1 from the weak law of large numbers of Proposition 5 in Appendix A. Then, we can apply CLT for an MDS.

OPE with a Weighted Average Estimator: Case with Unknown Variance
In general, the variance σ 2 t is unknown and needed to be replaced with an estimator. However, we cannot use the samples used for constructing π t andf t−1 to estimate σ 2 t due to the dependency. For this reason, we assume access to a dataset only with covariates, , we can approximate σ 2 t by applying the law of large numbers to the sample average g ′ t,N , defined as π e , f * is showed as follows.
In practice, we need to avoid having the estimator of σ * 2 t be less than or equal to 0. Thus, instead of (1−r)T , we use the estimator g t,N , defined as g t,(1−r)T = max g ′ t,N , ǫ , where ǫ > 0 is the lower bound of the variance σ * 2 t . The estimator g t,N is consistent, as is g ′ t,N . The value ǫ is assumed to be known, and we can use any sufficiently small value for ǫ because it is simply a technical term. The proof is shown in Appendix B. Then, using g t,N , we define the Feasible A3IPW (FA3IPW) estimatorθ FA3IPW Similarly, we can also define the corresponding IPW estimator and refer to it as Feasible weighted Average Adaptive IPW estimator (FA2daIPW).
In some applications, we can obtain the dataset as evaluation (test) data, which is the target of a new policy (Kato et al., 2020b). On the other hand, by introducing a sample splitting, we can relax the assumption as the following remark.
Remark 7 (Sample Splitting). To relax the access to E N , we consider splitting In the following discussion, for simplicity, we assume that rT is an integer (i.e., ⌊rT ⌋ = rT ).
The samples Thus, to approximate σ 2 t , we can apply the law of large numbers to the sample average g t, . More details on sample splitting are provided in Appendix D.

Asymptotic Properties of a FA3IPW Estimator
Based on this property, the following theorems gives us the consistency and asymptotic normality ofθ FA3IPW T . First, we show the consistency ofθ FA3IPW Theorem 3 (Consistency of the Proposed Estimator). Suppose that there exist C 2 and C 3 such that |f t | ≤ C 2 and Proof. From the boundedness, we can apply the law of large numbers for an MDS (Proposition 5 in Appendix A). Therefore, 1 The following theorem shows the asymptotic normality ofθ FA3IPW T . The proof is in Appendix C.
, an appropriate valueθ Remark 8 (Difference of Assumption between the Consistency and Asymptotic Normality). The asymptotic normality requires g t,N −σ 2 * t p − → 0. However, we can obtain the consistencyθ A3IPW From this property, we can obtain the consistent estimator of the variance, σ * 2 t , which requires the consistent estimator of the policy value, θ 0 .
Remark 9 (Heuristic Stabilization). The proposed estimator requires a sequence of f t T −1 t=0 . Because the early estimator of f t may be unstable due to the insufficient amount of training data, some heuristic stabilizations may improve its performance. Hadad et al. (2019) proposed a similar estimator and suggested using a weight sequence for stabilization. In the setting of Kato et al. (2020a), they can change p t (a | x, Ω t−1 ) and proposed adjusting the probability to stabilize their proposed estimator. In this study, we take a simple approach by suggesting discarding some samples at first and constructing the proposed estimator without them. We call this estimator the stabilized FA3IPW (SFA3IPW) estimator. In some experiments, this approach improves the estimator's performance.

Efficiency of A3IPW Estimator
In the problem setting, it is not easy to discuss an efficiency of an estimator. For simplicity, we consider the lower bound of the variance of an estimator within a class of estimators such thatθ T = T t=1 w tψt (X t , A t , Y t , π t ), wherẽ ψ is a score function and w t is a weight satisfying T t=1 w t = 1. Let us note that we usually use w t = 1/T in the case where samples are i.i.d. First, we consider the variance ofψ t . In OPE, the lowest variance is given as E K a=1 π e (a|Xt) 2 v * (a,Xt) πt(a|X,Ωt−1) + π e (a | X t )f * (a, X t ) − θ 0 2 . In the proposed estimator, each element of {ψ t } T t=1 achieves this variance. In addition, it is well known that for a sequence of positive values φi minimizes the variance ofθ T when the covariances among the score functions are 0. When {φ t } T t=1 is an MDS, the covariance is 0. Thus, the proposed estimator uses the weights and scores that minimize the variance for an estimator with a form that satisfies T t=1 w tψt (X t , A t , Y t , π t ).

Main Algorithm: Two-step FA3IPW Estimation
Under the assumption of g t,N − σ * 2 t p − → 0, the proposed estimatorθ A3IPW T has the asymptotic normality. However, to estimate σ * 2 t = Var z t | Ω t−1 , a consistent estimator of θ 0 is required, which is why we use g t,N . However, we can obtain a consistent estimator of θ 0 without imposing the assumption that g t,N − σ * 2 t p − → 0. Based on these properties, we propose two-step estimation. First, using arbitrary appropriate values for g t,N =g t for t = 1, 2, . . . , T − 1, such asg t = 1, we obtain the initial estimates, θ t T −1 t=1 . Then, usingθ t p − → θ 0 , we construct g t,N − σ * 2 t p − → 0. Finally, we can estimate the next estimator of θ 0 ,θ TSFA3IPW T , with asymptotic normality from Theorem 4. We summarize the process of two-step FA3IPW (TSFA3IPW) estimation in Algorithm 1.
Remark 10 (Estimation of Functions f * t and e * t ). Several nonparametric regression estimators can be proved to be consistent for dependent samples via certain bandit algorithms (Yang & Zhu, 2002).  0

Experiments
In this section, using benchmark datasets, we demonstrate the effectiveness of the proposed FA3IPW estimator and the FA3IPW estimator with discarding some early samples for stabilization (SFA3IPW estimator in Remark 9). Following Dudík et al. (2011) and Farajtabar et al. (2018), we evaluate the proposed estimators using classification datasets by transforming them into contextual bandit data. From the LIBSVM repository, we use the satImage, pendigits, mnist, dna, letter, sensorless, connect-4, and covtype datasets 3 . First, we create an adaptive policy π a t by following a random walk and perform upper confidence bound (UCB) algorithms in the MAB problem. Then, we construct a behavior policy as a mixture of π a t and the uniform random policy π u t , defined as π t = 0.7π a t +0.3π u t (Kallus & Uehara, 2019a). When we use the RW policy, the policy π a t does not converge. In contrast, when we use the UCB policy to generate π a t , the policy converges to a time-invariant policy. To construct an evaluation policy, we create a deterministic policy π d by training a logistic regression classifier on historical data. Then, we construct the evaluation policy π e as a mixture of π d and the uniform random policy π u , defined as π e = 0.7π d + 0.3π u . Through experiments, the behavior policy π t is assumed to be known. More details are in Appendix E.
We compare the MSEs of six estimators, the FA3IPW, SFA3IPW, DM, AdaIPW, A2IPW, and FA2daIPW estimators. For the FA3IPW, SFA3IPW, and FA2daIPW estimators, we applied the two-step estimation. In each experiment, we have access to historical data with T = 1000 and evaluation data with N = 1000. With the SFA3IPW estimator, we discard the first 1000 samples of the historical data. When estimating f * and e * , we use the Nadaraya-Watson regression (NW) estimator, which is used in Yang & Zhu (2002). The resulting MSEs and their standard deviations (SDs) over 20 replications of each experiment are shown in Tables 1 and 2. In the experimental results, when the RW policy is used, the FA3IPW and SFA3IPW estimators show preferable performances compared with the A2IPW estimator. This is because the performance of the A2IPW estimator is guaranteed only when the policy converges to a time-invariant policy. On the other hand, when the UCB policy is used, the A2IPW estimator also works well as we can expect. From the results, we recommend using the FA3IPW estimator when the policy does not converge. More importantly, in the case, we can construct confidence intervals from the FA3IPW estimator, but cannot construct it from the A2IPW estimator. In Appendix E, we show the experimental results with other settings.

Conclusion
This study presented solutions for causal inference from dependent samples obtained via bandit feedback. By utilizing evaluation data or sample splitting, we can standardize the variance of an MDS. Then, we can apply the CLT for an MDS to obtain the asymptotic normality of the proposed estimator. In experiments, the proposed estimators showed theoretically expected performances.

Broader Impact
In various applications, such as A/B testing and clinical trials, the problem of causal inference from dependent samples arises. Because this study promotes the use of OPE for those applications by presenting an effective solution to this problem, the ethical issues related to such applications will become more critical. For example, in clinical trials, the proposed method also should take the criteria proposed by the US Food and Drug Administration (FDA, 2019) into account.
Besides, although this study solved an essential problem with OPE, the limitations of methods for OPE should still be recognized. The existing methods for OPE try to find causality only from data without requiring domain-specific knowledge, but they sometimes lead to inappropriate decision making by producing incorrect results. When finding causality in the real world, it might be desirable to utilize domain-specific knowledge combined with the results obtained from machine learning methods.
Proposition 4 (L r Convergence Theorem, Loeve (1977)). Let 0 < r < ∞, suppose that E |a n | r < ∞ for all n and that a n p − → a as n → ∞. The following are equivalent: (i) a n → a in L r as n → ∞; (ii) E |a n | r → E |a| r < ∞ as n → ∞; (iii) |a n | r , n ≥ 1 is uniformly integrable.
Remark 11. The weak law of large numbers for martingale holds when the random variable is bounded by a constant.

B Proof of Theorem 2
Proof. The variance σ 2 * t can be calculated as follows: Confidence Interval for Off-Policy Evaluation from Dependent Samples via Bandit Algorithm: Approach from Standardized Martingales Therefore, what we want to show is From the assumptions, Here, from the weak law of large numbers, as N → ∞, Therefore, as t → ∞ and N → ∞,

C Proof of Theorem 4
Proof. We have where note that To show (3), we use the central limit theorem for an MDS (Proposition 1 in Appendix A). Because ẑ t T t=1 is an MDS, we check the following three conditions of Proposition 1: Step 1: Check of Condition (a) We have Because the last term is 1, We have First, we show that the first and second terms vanishes asymptotically. We have From the continuous mapping theorem and assumption that g t,N − σ * 2 is uniformly integrable, we can prove E[|1/ √ g t,N − 1/ σ * 2 t |] → 0 as t → ∞ using L r -convergence theorem (Proposition 4 in Appendix A).
Step 2: Check of Condition (b) We can prove this condition using the assumption of the boundedness of the random variables.     The proposed FA3IPW estimator performs well in many datasets. Especially when we use the RW policy, the performance of the estimator tends to be better than the other methods.     ) under a policy π t = 0.5π a t + 0.5π u t with T = 1, 000 and N = 1, 000, and the Nadaraya-Watson regression. The method with the lowest MSE is in bold.   ) under a policy π t = 0.5π a t + 0.5π u t with T = 1, 000 and N = 1, 000, and the K-nearest neighbor regression. The method with the lowest MSE is in bold.