{'fraction_non_alphanumeric': 0.048001214259965466, 'fraction_numerical': 0.018764111028895594, 'mean_word_length': 4.109840038778478, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Doubly Robust Interval Estimation for Optimal Policy Evaluation in Online Learning

Evaluating the performance of an ongoing policy plays a vital role in many areas such as medicine and economics, to provide crucial instruction on the early-stop of the online experiment and timely feedback from the environment. Policy evaluation in online learning thus attracts increasing attention by inferring the mean outcome of the optimal policy (i.e., the value) in real-time. Yet, such a problem is particularly challenging due to the dependent data generated in the online environment, the unknown optimal policy, and the complex exploration and exploitation trade-off in the adaptive experiment. In this paper, we aim to overcome these difficulties in policy evaluation for online learning. We explicitly derive the probability of exploration that quantifies the probability of exploring the non-optimal actions under commonly used bandit algorithms. We use this probability to conduct valid inference on the online conditional mean estimator under each action and develop the doubly robust interval estimation (DREAM) method to infer the value under the estimated optimal policy in online learning. The proposed value estimator provides double protection on the consistency and is asymptotically normal with a Wald-type confidence interval provided. Extensive simulations and real data applications are conducted to demonstrate the empirical validity of the proposed DREAM method.


Introduction
Sequential decision-making is one of the essential components of modern artificial intelligence that considers the dynamics of the real world. By maintaining the trade-off between exploration and exploitation based on historical information, the bandit algorithms aim to maximize the cumulative outcome of interest and thus are popular in dynamic decision optimization with a wide variety of applications, such as precision medicine (Lu et al., 2021) and dynamic pricing (Turvey, 2017). There has been a vast literature on bandit optimization established over recent decades (see e.g., Sutton and Barto, 2018;Lattimore and Szepesvári, 2020, and the references therein). Most of these theoretical works focus on the regret analysis of bandit algorithms. When properly designed and implemented to address the exploration-and-exploitation trade-off, a powerful bandit policy could achieve a sub-linear regret, and thus eventually approximate the underlying optimal policy that maximizes the expected outcome. Yet, such a regret analysis only shows the convergence rate of the averaged cumulative regret (difference between the outcome under the optimal policy and that under the bandit policy) but provides limited information on the expected outcome under this bandit policy (referred to as the value in Dudík et al. (2011)).
Evaluating the performance of bandit policies plays a vital role in many areas, including medicine and economics (see e.g., Chakraborty and Moodie, 2013;Athey, 2019). By evaluation, we aim to unbiasedly estimate the value of the optimal policy that the bandit policy is approaching to and infer the corresponding estimate. Though there is an increasing trend in policy evaluation (see e.g., Li et al., 2011;Dudík et al., 2011;Swaminathan et al., 2017;Wang et al., 2017;Kallus and Zhou, 2018;Su et al., 2019), we note all these works focus on learning the value of a target policy offline using logged historical data. See the architecture of offline policy evaluation illustrated in the left panel of Figure 1. Instead of a post-experiment investigation, it attracts more attention recently to evaluate the ongoing policy in real-time. In precision medicine, the clinician aims to make the best treatment decision for each patient sequentially according to their baseline covariates. Estimating the mean outcome of the current treatment decision rule is crucial to answering several fundamental questions in health care, such as if the current strategy optimizes patients' outcomes significantly over some baseline strategies. When the value under the ongoing rule is much smaller than the desired average curative effect, the online trial must be terminated until more effective treatment options are available for the next round. Policy evaluation in online learning thus is a new desideratum to provide the early stop of the online experiment Figure 1: Left panel: the architecture of offline policy evaluation, with offline context-actionoutcome triples {(x t , a t , r t )} stored in the buffer to learn the value under a target policy π * with data generated by a behavior policy π b . Right panel: the architecture of doubly robust interval estimation (DREAM) method for policy evaluation in online learning, where the context-actionoutcome triple at time t, (x t , a t , r t ), is stored in the buffer to update the bandit policy π t and at the meantime to evaluate its performance. and timely feedback from the environment, as demonstrated in the right panel of Figure 1.

Related Works and Challenges
Despite the importance of policy evaluation in online learning, the current bandit literature suffers from three main challenges. First, the data such as the actions taken and rewards received sequentially collected from the online environment depend on the previous history and the running policy (see the right panel of Figure 1), and thus are not independent and identically distributed (i.i.d.). In contrast, the existing methods for the offline policy evaluation (see e.g., Li et al., 2011;Dudík et al., 2011) primarily assumed that the data are generated by the same behavior policy and i.i.d. across different individuals and time points. Such assumptions allow them to evaluate a new policy in offline data, by modeling the behavior policy or the conditional mean outcome. In addition, we note the target policy to be evaluated in offline policy evaluation is fixed and usually known, while for policy evaluation in online learning, the optimal policy of interest needs to be estimated and updated in real time.
The second challenge lies in estimating the mean outcome under the optimal policy online. Though there are numerous methods proposed recently to assess the online sample mean for a fixed action (see e.g., Nie et al., 2018;Neel and Roth, 2018;Deshpande et al., 2018;Shin et al., 2019a,b;Waisman et al., 2019;Hadad et al., 2019;Zhang et al., 2020), none of these methods are directly applicable to our problem since the sample mean only provides the impact of one particular arm, not the value of the optimal policy in bandits that considers the dynamics of the online environment. For instance, in the contextual bandits, we aim to select an action for each subject based on its context/feature to optimize the overall outcome of interest. Yet, there may not exist a unified best action for all subjects due to heterogeneity, and thus evaluating the value under one single optimal action cannot fully address the policy evaluation in such a setting. On the other hand, though commonly used in the regret analysis, the average of collected outcomes is not a good estimator for the value under the optimal policy in the sense that it does not possess statistical efficiency (see details in Section 3).
Third, given data generated by a bandit algorithm that maintains the exploration-andexploitation trade-off sequentially, inferring the value of the optimal policy online should consider such a trade-off and quantify the probability of exploration and exploitation. The probability of exploring non-optimal actions is essential for two folds. First, it determines the convergence rate of the online conditional mean estimator under each action. Second, it indicates the data points used for matching the value under the optimal policy. To the best of our knowledge, the regret analysis in the current bandit literature is built upon bounding the variance information (see e.g., Auer, 2002;Srinivas et al., 2009;Chu et al., 2011;Abbasi-Yadkori et al., 2011;Bubeck and Cesa-Bianchi, 2012;Zhou, 2015), yet little efforts have been made on formally quantifying the probability of exploration over time.
There are very few studies directly related to our topic. Chambaz et al. (2017) established the asymptotic normality for the conditional mean outcome under an optimal policy for sequential decision making. Later on, Chen et al. (2020) proposed an inverse probability weighted value estimator to infer the value of optimal policy using the -Greedy (EG) method. These two works did not discuss how to account for the exploration-andexploitation trade-off under commonly used bandit algorithms, such as Upper Confidence Bound (UCB) and Thompson Sampling (TS) as considered in this paper. Recently, to evaluate the value of a known policy based on the adaptive data, Bibaut et al. (2021) and Zhan et al. (2021) proposed to utilize the stabilized doubly robust estimator and the adaptive weighting doubly robust estimator, respectively. Yet, both methods focused on obtaining a valid inference of the value estimator under a fixed policy by conveniently assuming a desired exploration rate to ensure a sufficient sampling of different arms. Such an assumption can be violated in many commonly used bandits (see details shown in Theorem 4.1). Though there are other works focusing on statistical inference for adaptively collected data (Dimakopoulou et al., 2021;Zhang et al., 2021;Khamaru et al., 2021;Ramprasad et al., 2022) under the setting of bandits or reinforcement learning, our work handles policy evaluation from a completely unique angle on inferring the value of optimal policy by investigating the exploration rate in online learning.

Our Contributions
In this paper, we aim to overcome the aforementioned difficulties of policy evaluation in online decision-making. Our contributions lie in the following folds. The first contribution of this work is to explicitly characterize the trade-off between exploration and exploitation in the online policy optimization, we derive the probability of exploration in bandit algorithms. Such a probability is new to the literature by quantifying the chance of taking the non-greedy policy (i.e., a non-optimal action) given the current information over time, in contrast to the probability of exploitation for taking greedy action. Specifically, we consider three commonly used bandit algorithms for exposition, including UCB, TS, and EG methods. We note that the probability of exploration is pre-specified in EG by users while remaining implicit in UCB and TS. We use this probability to conduct valid inferences on the online conditional mean estimator under each action. The second contribution of this work is proposing the doubly robust interval estimation (DREAM) to infer the mean outcome of the optimal online policy. The DREAM provides double protection on the consistency of the proposed value estimator to the true value, given the product of the nuisance error rates of the probability of exploitation and the conditional mean outcome as o p (T −1/2 ) for T as the termination time. Under standard assumptions for inferring the online sample mean, we show the value estimator under DREAM is asymptotically normal with a Wald-type confidence interval provided. To the best of our knowledge, this is the first work to establish the inference for the value under the optimal policy by taking the exploration-and-exploitation trade-off into thorough account, and thus fills a crucial gap of the policy evaluation in online learning.
The rest of this paper is organized as follows. We introduce notation and formulate our problem, followed by preliminaries of standard contextual bandit algorithms and the formal definition of probability of exploration. In Section 3, we detail the DREAM method. Then in Section 4, we derive theoretical results of DREAM under contextual bandits by establishing the convergence rate of the probability of exploration and deriving the asymptotic normality of the online mean estimator. Extensive simulations are conducted to demonstrate the empirical performance of the proposed method in Section 5, followed by a real application using OpenML datasets in Section 6. We conclude our paper in Section 7 by discussing the performance of the proposed DREAM in terms of the regret bound and a direct extension of our method for policy evaluation with any known policy in online learning. All the additional results and technical proofs are given in the appendix.

Problem Formulation
In this section, we formulate the problem of policy evaluation in online learning. We first build the framework based on the contextual bandits in Section 2.1. We then introduce three commonly used bandit algorithms, including UCB, TS, and EG, to generate the data online, in Section 2.2. Lastly, we define the probability of exploration in Section 2.3. In this paper, we use bold symbols for vectors and matrices.

Framework
Let X ∈ X be d dimensional context/feature which includes 1 for the intercept, A ∈ A as the action, and R ∈ R as the reward/outcome. In contextual bandits, at each time step t ∈ T ≡ {1, 2, 3, · · · }, we observe a context x t drawn from a distribution P X . Suppose the reward given x and a follows R ≡ µ(x, a) + e, where µ(x, a) ≡ E(R|X = x, A = a) is the conditional mean outcome function (also known as the Q-function in the literature (Murphy, 2003;Sutton and Barto, 2018)), and is bounded by |µ(x, a)| ≤ U . The noise term e is independent σ-subguassian at time step t independent of H t−1 given a t for t ∈ T .
Let the conditional variance as E(e 2 |A = a) = σ 2 a . The value (Dudík et al., 2011) of a given policy π(·) is We define the optimal policy as π * (x) ≡ arg max a∈A µ(x, a), ∀x ∈ X , which finds the optimal action based on the conditional mean outcome function given a context x. Thus, the optimal value can be defined as V * ≡ V (π * ) = E X∼P X [µ{X, π * (X)}]. In the rest of this paper, to simplify the exposition, we focus on two actions, i.e., A = {0, 1}. Then the optimal policy is given by Our goal is to infer the value under the optimal policy π * from the online data generated sequentially by some bandit algorithms. Since the optimal policy is unknown, we estimate the optimal policy from the online data as π t by H t . As commonly assumed in the current online inference literature (see e.g., Deshpande et al., 2018;Zhang et al., 2020;Chen et al., 2020) and the bandit literature (see e.g., Chu et al., 2011;Abbasi-Yadkori et al., 2011;Bubeck and Cesa-Bianchi, 2012;Zhou, 2015), we consider the conditional mean outcome function taking a linear form, i.e., µ(x, a) = x β(a), where β(·) is a smooth function and can be estimated via a ridge regression based on H t−1 as where with ω = 1. Based on the ridge estimator in (1), the online conditional mean estimator for µ is defined as µ t−1 (x, a) = x β t−1 (a). With two actions, the estimated optimal policy at time step t is defined by We note the linear form of µ(x, a) can be relaxed to the non-linear case as µ(x, a) =

is a continuous function (see examples in our simulation studies in
Section 5). Then the corresponding online conditional mean estimator for µ is defined as

Bandit Algorithms
We briefly introduce three commonly used bandit algorithms in the framework of contextual bandits, to generate the online data sequentially.
Upper Confidence Bound (UCB) (Li et al., 2010): Let the estimated standard where c t is a non-increasing positive parameter that controls the level of exploration. With two actions, we have the action at time step t as Thompson Sampling (TS) (Agrawal and Goyal, 2013): Suppose a normal likelihood function for the reward given x and a such that R ∼ N {x θ(a), ρ 2 } with a known parameter ρ 2 . If the prior for θ(a) at time t is where N d is the d-dimensional multivariate normal distribution, we have the posterior distribution of θ(a) as for a ∈ {0, 1}. At each time step t, we draw a sample from the posterior distribution as θ t (a) for a ∈ {0, 1}, and select the next action within two arms by a t = I x t θ t (1) > x t θ t (0) .
-Greedy (EG) (Sutton and Barto, 2018): Recall the estimated conditional mean outcome for action a as µ t (x, a) given a context x. Under EG method, the action at time t is selected by where δ t ∼ Bernoulli(1 − t ) and the parameter t controls the level of exploration as pre-specified by users.

Probability of Exploration
We next quantify the probability of exploring non-optimal actions at each time step. To be specific, define the status of exploration as I{a t = π t (x t )}, indicating whether the action taken by the bandit algorithm is different from the estimated optimal action that exploits the historical information, given the context information. Here, π t can be viewed as the greedy policy at time step t. Thus the probability of exploration is defined by where the expectation in the last term is taken respect to a t ∈ A and history H t−1 . According to (3), κ t is determined by the given context information and the current time point. We clarify the connections and distinctions of the defined probability of exploration concerning the bandit literature here. First, the exploration rate used in the current bandit works mainly refers to the probability of exploring non-optimal actions given an optimal policy and contextual information x t at time step t, i.e., Pr{a t = π * (x t )}. This is different from our proposed probability of exploration κ t (x t ) ≡ Pr{a t = π t (x t )}. The main difference lies in the estimated optimal policy from the collected data at the current time step t, i.e., π t , in κ t (x t ). If properly designed and implemented, the estimated optimal policy under a bandit algorithm π t will eventually converge to the true optimal policy π * when t is large, which yields κ t (x) → lim t→∞ Pr{a t = π * (x)}. In practice, we can estimate κ t (x t ) sequentially by using {i, x i } 1≤i≤t as inputs and {I{a i = π i (x i )}} 1≤i≤t as outputs via parametric or non-parametric tools. We denote the corresponding estimator as κ t (x t ) for time step t. Such implementation conditions are explicitly described in Section 3.

Doubly Robust Interval Estimation
We present the proposed DREAM method in this section. We first detail why the average of outcomes received in bandits fails to process statistical efficiency. In view of the results established in regret analysis for the contextual bandits (see e.g., Abbasi-Yadkori et al., 2011;Chu et al., 2011;Zhou, 2015), we have the cumulative regret as , whereÕ is the asymptotic order up to some logarithm factor. Therefore, it is immediate that the average of rewards follows √ T (T −1 T t=1 r t − V * ) =Õ(1), since the dimension d is finite. These results indicate that a simple average of the total outcome under the bandit algorithm is not a good estimator for the optimal value, since it does not own the asymptotic normality for a valid confidence interval construction. Instead of the simple aggregation, intuitively, we should select the outcome when the action taken under a bandit policy accords with the optimal policy, i.e., a t = π t (x t ), defined as the status of exploitation. In contrast to the probability of exploration, we define the probability of exploitation as Following the doubly robust value estimator in Dudík et al. (2011), we propose the doubly robust mean outcome estimator as the value estimator under the optimal policy as where T is the current/termination time, and 1 − κ t (x t ) is the estimated matching probability between the chosen action a t and estimated optimal action given x t , which captures the probability of exploitation. Our value estimator provides double protection on the consistency to the true value, given the product of the nuisance error rates of the probability of exploitation and the conditional mean outcome as o p (T −1/2 ), as discussed in Theorem 3.
We further propose a variance estimator for V T as where σ 2 is an estimator for σ 2 a , for a = 0, 1. The proposed variance estimator is consistent to the true variance of the value shown in Theorem 3. We officially name our method as doubly robust interval estimation (DREAM), with the detailed pseudocode provided in Algorithm 1. To ensure sufficient exploration and a valid inference, we force to pull non-optimal actions given greedy samples with a pre-specified clipping rate p t in step (4) of Algorithm 1 of an order larger than O(t −1/2 ) as required by Theorem 3. The estimated probability of exploration is used in step (6) in Algorithm 1 to learn the value and variance. A potential limitation of DREAM rises when the agent resists taking extra non-greedy actions in online learning. Yet, we discuss in Appendix 7.1 that the regret from such an exploration is negligible compared to the regret from exploitation, thus we can still maintain the sub-linear regret under DREAM.
The theoretical validity of the proposed DREAM is detailed in Section 4, with its empirical out-performance over baseline methods demonstrated in Section 5.

Theoretical Results
We formally present our theoretical results. In Section 4.1, we first derive the bound of probability of exploration under three commonly used bandit algorithms introduced in Section 2.2. This allows us to further establish the asymptotic normality of the online conditional mean estimator under a specific action in Section 4.2. Next, we establish the theoretical properties of DREAM with a Wald-type confidence interval given in Section 4.3. All the proofs are provided in Appendix B. The following assumptions are required to establish our theories.  for all x ∈ X , and Σ = E XX has minimum eigenvalue λ min (Σ) > λ for some λ > 0.
Assumption 4.1 is well known as the margin condition, which is commonly assumed in the literature to derive a sharp convergence rate for the value under the estimated optimal policy (see e.g., Luedtke and Van Der Laan, 2016;Chambaz et al., 2017;Chen et al., 2020). Assumption 4.2 is a technical condition on bounded contexts such that the mean of the martingale differences will converge to zero (see e.g., Zhang et al., 2020;Chen et al., 2020). Assumption 4.3 is a technical requirement for the uniqueness and convergence of the least squares estimators, which requires the bandit algorithm to explore all actions sufficiently such that the asymptotic properties for the online conditional mean estimator under different actions hold (see e.g., Deshpande et al., 2018;Hadad et al., 2019;Zhang et al., 2020). The parameter {p i } t i=1 defined in Assumption 4.3 characterizes the boundary of the probability of taking one action and we name it as clipping rate. We ensure Assumption 4.3 is satisfied using step (4) in Algorithm 1. We establish the relationship between p t and κ t and discuss the requirement for p t to consistently estimate β t (a) next.

Bounding the Probability of Exploration
The probability of exploration not only shows the signal of success in finding the global optimization in online learning, but also connects to optimal policy evaluation by quantifying the rate of executing the greedy actions. Instead of directly specifying this probability (see e.g., Zhang et al., 2020;Chen et al., 2020;Bibaut et al., 2021;Zhan et al., 2021), we explicitly bound this rate based on the updating parameters in bandit algorithms, by which we conduct a valid follow-up inference. Since the probability of exploration involves the estimation of mean outcome function, we need to first derive a tail bound for the online ridge estimator and the estimated difference between the mean outcomes.
The results in Lemma 4.1 establish the tail bound of the online ridge estimator β t (a), which can be simplified as C 1 exp(−C 2 tp 2 t ), for some constants {C j } 1≤j≤2 , by noticing the constant h and λ, the dimension d, the subgaussian parameter σ, and the bound L x are positive and bounded, under bounded true coefficients β(a). Recall the clipping constraint that 0 < p t < 1 is non-increasing sequence. This tail bound is asymptotically equivalent to exp(−tp 2 t ). The established results in Lemma 4.1 work for general bandit algorithms including UCB, TS, and EG. These tail bounds are align with the bound exp(−t 2 t ) derived in Chen et al. (2020) for the EG method only. By Lemma 4.1, it is immediate to obtain the consistency of the online ridge estimator β t (a), if tp 2 t → ∞ as t → ∞.
In the following theorem, we derive the probability of exploration at each time step under the three discussed bandit algorithms for exposition.
Theorem 1 (Probability of exploration) In the online contextual bandit algorithms using UCB, TS, or EG, given a context x t at time step t, assuming Assumptions 4.1, 4.2, and 4.3 hold, let ∆ xt ≡ µ(x t , 1) − µ(x t , 0), for any ξ > 0 with c ξ specified in Corollary 4.1, The theoretical order of κ t (·) is new to the literature, which quantifies the probability of exploring the non-optimal actions under a bandit policy over time. We note that the probability of exploration under EG is pre-specified by users, which directly implies its exploring rate as t /2 (for the two-arm setting) as shown in results (iii). The results (i) and (ii) in Theorem 1 show that the probabilities of exploration under UCB and TS are non-increasing under certain conditions. For instance, if (t − 1)p 2 t−1 → ∞ for UCB and TS, as t → ∞, the upper bound for κ t (x t ) decays to zero with an asymptotically equivalent convergence rate as O{exp(−(t − 1)p 2 t−1 )} up to some constant. Under such a situation, the exploration for non-optimal arms might be insufficient, leading to a possibly invalid and biased inference for the online conditional mean. Therefore, additional exploration technique is required to collect informative online data for policy evaluation as discussed in Algorithm 1. Simulation studies are provided in Appendix 5.1 to compare the theoretical order of the probability of exploration under different bandit algorithms.

Asymptotic Normality of Online Ridge Estimator
We next use the established bounds for the probability of exploration in Theorem 1 to further obtain the asymptotic normality for the online conditional mean estimator under each action. Denote κ ∞ (x) ≡ lim t→∞ κ t (x) = lim t→∞ Pr{a t = π * (x)}. Assume the conditions in Theorem 1 hold and tp 2 t → ∞ as t → ∞, we have the upper bound of the probability of exploration decays to zero in Theorem 1 for UCB and TS. Since κ t (·) is lower bounded by a non-increasing sequence greater than 0 under the clipping assumption (A4.3) ensured by step (4) in Algorithm 1, it follows from Sandwich Theorem immediately that κ ∞ (·) exist for UCB and TS, and κ ∞ (·) = lim t→∞ t /2 for EG. We further obtain the following theorem for asymptotics and inference.
Theorem 2 (Asymptotics and inference) Suppose the conditions in Lemma 4.1 hold with x} for ∀x ∈ X and ∀a ∈ A, with the variance given by The results in Theorem 2 establish the asymptotic normality of the online ridge estimator and the online conditional mean estimator over time, with an explicit asymptotic variance derived. Here, κ ∞ (x) may differ under different bandit algorithms while the asymptotic normality holds as long as the adopted bandit algorithm explores the non-optimal actions sufficiently with a non-increasing rate, following the conditions in Theorem 2, i.e., a clipping rate p t of a order larger than O(t −1/2 ) as described in Algorithm 1. The proof of Theorem 2 generalizes Theorem 3.1 in Chen et al. (2020) by additionally considering the online ridge estimator and general bandit algorithms.

Asymptotic Normality and Robustness for DREAM
In this section, we further derive the asymptotic normality of √ T ( V T − V * ). The following additional assumption is required to establish the doubly robustness of DREAM.

Assumption 4.4 (Rate Double Robustness)
Assumption 4.4 requires the estimated conditional mean function and the estimated probability of exploration to converge at certain rates in online learning. This assumption is frequently adopted in the causal inference literature (see e.g., Zhang et al., 2012;Luedtke and Van Der Laan, 2016) to derive the asymptotic distribution of the estimated average treatment effect with either parametric estimators or non-parametric estimators (see e.g., Wager and Athey, 2018;Farrell et al., 2021). We remark that under the conditions required We then have the asymptotic normality of √ T ( V T − V * ) as stated in the following theorem.
Theorem 3 (Asymptotic normality for DREAM) Suppose conditions in Lemma 4.1 hold.
Assuming Assumptions 4.1 and 4.4, with The above theorem shows that the value estimator under DREAM is doubly robust to the true value, given the product of the nuisance error rates of the probability of exploitation and the conditional mean outcome as o p (T −1/2 ). We use the Martingale Central Limit Theorem to overcome the non-iid sample problem for asymptotic normality. The asymptotic variance of the proposed estimator is caused by two sources. One is the variance due to the context information, and the other is a weighted average of the variance under the optimal arm and the variance under the non-optimal arms. The weight is determined by the probability of exploration when t → ∞ under the adopted bandit algorithm. To the best of our knowledge, this is the first work that studies the asymptotic distribution of the mean outcome of the estimated optimal policy under general online bandit algorithms, which takes the exploration-and-exploitation trade-off into thorough account. Our method thus fills a crucial gap of policy evaluation in online learning. By Theorem 3, a two-sided denotes the upper α/2−th quantile of a standard normal distribution.

Simulation Studies
We investigate the finite sample performance of DREAM in this section. The computing infrastructure used is a virtual machine in the AWS Platform with 72 processor cores and 144GB memory.

Demonstration for Probability of Exploration
Firstly, we demonstrate simulation results to show the probabilities of exploration of the three online bandits algorithms. Consider the 2-dimensional context X = [X 1 , X 2 ] , with . Suppose the outcome of interest given x and a is gener- . Then the optimal policy given by I{−1 + 5 cos(x 1 ) − 3 cos(x 2 ) > 0}, and the optimal value as 3.27 calculated by integration. We apply three bandit algorithms in Section 2.2 to show their probabilities of exploration with the following specifications: (i) for UCB, let c t ∈ {1, 2}; (ii) for TS, let priors

Coverage Probabilities under DREAM
Then, we demonstrate the coverage probabilities of the policy value under DREAM. Consider the same setting as in Section 5.1 with total decision time T = 2000 and the burning period T 0 = 50. We employ the three bandit algorithms described in Section 2.2 to generate the online data with ω = 1 (Li et al., 2010), where c t = 1 for UCB, θ(a) ∼ N d (0 d , I d ) with ρ = 2 for TS, and t = 0.1t −2/5 for EG. We next evaluate the doubly robustness property of the proposed value estimator under DREAM in comparison to the simple average of the total reward for contextual bandits. To be specific, we consider the following four methods: 1. the models of conditional mean function µ and probability of exploration κ t are both correctly specified in DREAM; 2. the model of µ is misspecified with linear regression; 3.
the model of κ t is misspecified by a constant 0.5; 4. using the averaged reward as the value estimator. These four value estimators are evaluated by the coverage probabilities of the 95% two-sided Wald-type CI on covering the optimal value, the bias, and the ratio between the standard error and the Monte Carlo standard deviation, as shown in Figure 3 for UCB, and Figures 4 and 5 for TS and EG, aggregated over 1,000 runs. We remark that the above simulation results are not sensitive to the choose of p t and additional simulation results to show the sensitivity analysis of probabilities of exploration under the three online bandits algorithms are provided in Section A in Appendix.

Real Data Applications
In this section, we evaluate the performance of the proposed DREAM method in real datasets from the OpenML database, which is a curated, comprehensive benchmark suites  for machine-learning tasks. Following the contextual bandit setting considered in this paper, we select two datasets in the public OpenML Curated Classification benchmarking suite 2018 (OpenML-CC18; BSD 3-Clause license) (Bischl et al., 2017), i.e., the SEA50 and SEA50000, to formulate the real application. Each dataset is a collection of pairs of 4-dimensional features x and their corresponding labels Y ∈ {0, 1}, with a total number of observations as n =1,000,000. To simulate an online environment for data generation, we turn two-class classification tasks into a two-armed contextual bandit problems (see Here, the mean of reward is 1 if the selected action matches the underlying true label, and 0 otherwise. Therefore, the optimal value is 1 while the optimal policy is unknown due to the complex relationship between the collected features and the label. Our goal is to infer the value under the optimal policy in the online settings produced by datasets SEA50 and SEA50000.
Using the similar procedure as described in Section 5, we apply DREAM in comparison to the simple average estimator, by employing three bandit algorithms with following spec-

Discussion
In this paper, we propose the doubly robust interval estimation (DREAM) to infer the mean outcome of the optimal policy using the online data generated from a bandit algorithm. We explicitly characterize the probability of exploring the non-optimal actions under a bandit policy, and show the consistency and asymptotic normality of the proposed value estimator.
In this section, we discuss the performance of the proposed DREAM in terms of the regret bound, and extend it to the evaluation of a known policy in online learning.

Regret Bound under DREAM
In this section, we discuss the regret bound of the proposed DREAM method. Specifically, we study the regret defined as the difference between the expected cumulative rewards under the oracle optimal policy and the bandit policy, which is We note that the indicator function is equivalent to |a t − π * (x t )| and is bounded by |a t − π(x t )| + | π(x t ) − π * (x t )|. Thus, we can divide the regret defined in Equation (6) into two parts as R T ≤ R (1) is the regret from the exploration and R (2) is the regret from the exploitation. It is well known that the regret from the exploitation R (2) T is sublinear (Chu et al., 2011;Agrawal and Goyal, 2013) and the regret for EG has been well studied by Chen et al. (2020). Therefore, we focus on the analysis of the regret R (1) T from the exploration for UCB and TS here. Since ∆ xt is bounded and the upper bound of has an asymptotically equivalent convergence rate as O{exp(−tp 2 t )} up to some constant by Theorem 1, there exists some constant C such that the regret from the exploration is bounded by

Evaluation of a Known Policy in Online Learning
We could extend our method to evaluate a known new policy π E that is different from the bandit policy, in the online environment. Typically, we focus on the statistical inference of policy evaluation in online learning under the contextual bandit framework. Recall the setting and notations in Section 2, given a target policy π E , we propose its doubly robust value estimator as where T is the current time step or the termination time and p t−1 (a t |x t ) is the estimated propensity score of the chosen action a t . The following theorem summarizes the asymptotic properties of V T (π E ), built upon Theorem 2.
Here, we impose the same conditions on the bandit algorithms as in Theorem 3 to guarantee a positive non-increasing exploration rate bounded away from zero. This ensures a sufficient exploration on different arms, and thus evaluating an arbitrary policy is valid. The use of rate doubly robustness assumption and the margin condition (Assumption 4.1) follows the similar logic as in Theorem 3. The estimator of σ(π E ) 2 denoted as σ(π E ) 2 can be obtained similarly as Equation (5). Thus a two-sided 1 − α CI for V (π E ) under the online There are some other extensions we may also consider in the future work. First, in the current paper, we focus on settings with binary actions. Thus, a more general method with multiple actions or even continuous action space is desirable. Second, we consider the contextual bandits in this paper and all the theoretical results are applicable to the multiarmed bandits. It would be practically interesting to extend our proposal to reinforcement learning problems. A Sensitivity Test for the Choice of p t We conduct a sensitivity test for the choice of p t in this section. We run all the simulations with p t = 0.01, 0.05, 0.1 and find that Algorithm 1 is not sensitive to the choice of p t .

B Technical Proofs for Main Results
This section provides all the technical proofs for the established theorems for policy evaluation in online learning under the contextual bandits.

B.1 Proof of Lemma 4.1
The proof of Lemma 4.1 consists of three main steps. To be specific, we first reconstruct the target difference β t (a) − β(a) and decompose it into two parts. Then, we establish the bound for each part and derive its lower bound Pr( β t (a) − β(a) 1 ≤ h).
Step 1: Recall Equation (1) with D t−1 (a) being a N t−1 (a) × d design matrix at time t − 1 with N t−1 (a) as the number of pulls for action a, we have We are interested in the quantity Our goal is to find a lower bound of Pr( β t (a) − β(a) 1 ≤ h) for any h > 0. Notice that by the triangle inequality we have β t (a) − β(a) 1 ≤ η 3 1 + η 4 1 , thus we can find the lower bound using the inequality as Step 2: We focus on bounding η 4 first.
By the relationship between eigenvalues and the L2 norm of symmetric matrix, we have M −1 2 = λ max (M −1 ) = {λ min (M )} −1 for any invertible matrix M . Thus we can obtain that By Cauchy-Schwartz inequality, we further have bound of the L1 norm of η 4 as Step 3: Lastly, using the results in (B.5), we have By the definition of η 3 and Lemma 2 in Chen et al. (2020), for any constant c > 0, we have

Therefore, from (B.3) and (B.6), taking
Based on the above results, it is immediate that the online ridge estimator β t (a) is consistent to β(a) if tp 2 t → ∞ as t → ∞. The proof is hence completed.

B.2 Proof of Corollary 4.1
Since µ t (x t , a) − µ(x t , a) = x t β t (a) − β(a) , by Holder's inequality, we have By Lemma 4.1, we further have Note that by the Triangle Inequality, consistent with time t.

B.3 Proof of Theorem 1
The proof of Theorem 1 consists of two main parts to show the probability of exploration under UCB and TS, respectively, by noting the probability of exploration under EG is given by its definition.

B.3.1 Proof for UCB
We first show the probability of exploration under UCB. This proof consists of three main steps stated as following: 1. We first rewrite the target probability by its definition and express it as 2. Then, we establish the bound for the variance estimation such that

Lastly, we bound Pr
using the result in Corollary 4.1.
Step 1: We rewrite the target probability by definition and decompose it into two parts.
Let ∆ xt ≡ µ(x t , 1) − µ(x t , 0). Based on the definition of the probability of exploration and the form of the estimated optimal policy π t (x t ), we have Next, we rewrite η 0 and η 1 using the estimated mean and variance components µ t−1 (x t , a) and σ t−1 (x t , a), where a = 0, 1. We focus on η 0 first.
Given π t (x t ) = 1, i.e., µ t−1 (x t , 1) − µ t−1 (x t , 0) > 0, based on the definition of the taken action in Lin-UCB that the probability of choosing action 0 rather than action 1 is where the second equality is to rearrange the estimated mean and variance components, and the last equality comes from the definition of the conditional probability. Combining this with (B.8), we have Similarly, we have Thus combined with Equation (B.8), we have The rest of the proof is aims to bound the probability Step 2: Secondly, we bound the variance σ t−1 (x t , 0) and σ t−1 (x t , 1) .
We consider the quantity Let v be any d × 1 vector, then the sample variance under action 0 is given by where the first inequality is to replace (x t / x t 2 ) with any normalized vector, and the second inequality is due to the definition. According to (B.10), combined with Assumption 4.2, we can further bound σ t−1 (x t , 0) by It is immediate from (B.10) and (B.11) that where the first inequality is owing to Assumption 4.3 , and the second inequality is owing to Assumption 4.2. This together with (B.12) gives the lower and upper bounds of σ t−1 (x t , 0) which follows that Combining (B.9) and the above equation, we get the conclusion that Step 3: Lastly, we aim to bound Pr | µ t−1 (x t , 1) − µ t−1 (x t , 0)| < 2ctLx √ (t−1)p t−1 λ using the result in Corollary 4.1.
For any ξ > 0, define E : Thus for the probability Pr Recall that by Assumption 4.1, there exist some constants γ and δ such that for large i.e., there exist some constant M such that Therefore , combined with the Equation (B.16), we have The proof is hence completed.

B.3.2 Proof for TS
We next show the probability of exploration under TS consisting of three main steps: 1. We firstly define an event E : 2. Next, We bound the probability of exploration on the event E.
3. Lastly, we combine the results in the previous two steps to get the unconditioned probability of exploration .
Using the law of iterated expectations, based on the definition of the probability of exploration and the form of the estimated optimal policy π t (x t ), on the event E, we have (B.18) Step 2: Next, we focus on deriving the bound of Recalling the bandit mechanism of TS, we have a t = I x t θ t (1) > x t θ t (0) , where θ t (a) is drawn from the posterior distribution of θ(a) given by From the posterior distributions and the definitions of µ t−1 (x t , a) and σ t−1 (x t , a), we have that is, Notice that x t θ t (1) and x t θ t (0) are drawn independently, thus, Therefore, on the Event E we have where Φ(·) is the cumulative distribution function of the standard normal distribution.
This yields that on the Event E, Using similar arguments in proving (B.13)that Therefore, combining the above two equations leads to Note that on the Event E, we have which follows that on the Event E, Step 3 The proof is hence completed.

B.4 Proof of Theorem 2
We detail the proof of Theorem 2 in this section. Using the similar arguments in (B.2) in the proof of Lemma 4.1, we can rewrite √ t{ β t (a) − β(a)} as Our goal is to prove that √ t{ β t (a) − β(a)} is asymptotically normal. The proof is to generalize Theorem 3.1 in Chen et al. (2020) by considering commonly used bandit algorithms, including UCB, TS, and EG here. We complete the proof in the following four steps: • Step 1: Prove that where G a is the variance matrix to be spesified shortly. • Step 2: Prove where σ 2 a = E(e 2 t |a t = a) for a = 0, 1. • Step 3: Prove that Step 4: Combine above results in steps 1-3 using Slutsky's theorem.
Step 1: We first focus on proving that Using Cramer-Wold device, it suffices to show that for any v ∈ R d , we have that I(a i = a)v x i e i is a Martingale difference sequence. We next show the asymptotic normality of η 1 (v) using Martingale central limit theorem, by the following two parts: i) check the conditional Lindeberg condition; ii) derivative the limit of the conditional variance.
Firstly, we check the conditional Lindeberg condition. For any δ > 0, denote Combining this with (B.22), we obtain that where the right hand side equals Then, we can further write (B.23) as where e i(a) = e i when a i = a and 0 otherwise. Since e i conditioned on a i are i.i.d., ∀i, we have the right hand side of the above inequality equals where e is the random variable given by e i |H i−1 . Note that e 2 I {e 2 > tδ 2 /( v 2 2 L 2 x d)} is dominated by e 2 with Ee 2 < ∞ and converges to 0, as t → ∞. Then, by Dominated Convergence Theorem, the results in (B.24) can be further bounded by Therefore, conditional Lindeberg condition holds.
Secondly, we derive the limit of the conditional variance. Notice that Since e t is independent of H i−1 and x i given a t , and E [e 2 i | a i = a] = σ 2 a , we have Here, the first equation comes from iteration expectation over x i and the fact that I(a i = a) = I(a i = a = π * (x i )) + I(a i = a = π * (x i )) = I(a i = π * (x i ))I(π * (x i ) = a) + I(a i = π * (x i ))I(π * (x i ) = a), and the second equation is owing to the fact that I(π * (x i ) = a)v x i x i v is a constant given x i and independent of H i−1 . Define then the conditional variance can be expressed as which can be expressed as Therefore for the expectation of It follows immediately that Therefore, by the triangle inequality, we have Since the above equation holds for any > 0 and 0 < t−t 0 t < 1, we have which goes to zero as t → ∞. Thus, which goes to zero as t → ∞. Combined with Equation (B.26), it follows immediately that as t goes to ∞, we have Therefore, as t goes to ∞, we have 1 Thus, following the similar arguments in S1.2 in Chen et al. (2020), we have Finally, by Martingale Central Limit Theorem, we have (B.28) The first part is thus completed.
Step 2: We next show a , which is sufficient to find the limit of (1/t) t i=1 I(a i = a)x i x i + 1 t I d . By Lemma 6 in Chen et al. (2020), it suffices to show the limit of 1 Recall the results in (B.26) and (B.28), we have E I(a i = a)v x i x i v | H i−1 = G a /σ 2 a . Combining this with (B.29), we have , as t → ∞.
By Lemma 6 in Chen et al. (2020) and Continuous Mapping Theorem, we further have Step 3: We focus on proving and by (B.4), we have Step 4: Finally, we combine the above results using Slutsky's theorem, and conclude that where G a is defined in (B.28). Denote the variance term as with σ 2 a = E(e 2 t |a t = a) denoting the conditional variance of e t given a t = a, for a = 0, 1, The proof is hence completed.

B.5 Proof of Theorem 3
Finally, we prove the asymptotic normality of the proposed value estimator under DREAM in Theorem 3 in this section. The proof consists of four steps. In step 1, we aim to show Next, in Step 2, we establish The above two steps yields that Then, in Step 3, based on (B.30) and Martingale Central Limit Theorem, we show where σ 2 a = E(e 2 t |a t = a) for a = 0, 1, and κ t → κ ∞ as t → ∞. Lastly, in Step 4, we show the variance estimator in Equation (5) is a consistent estimator of σ 2 DR . The proof for Theorem 3 is thus completed.
Step 1: We first show V T = V T + o p (T −1/2 ). To this end, define a middle term as Thus, it suffices to show V T = φ T + o p (T −1/2 ) and φ T = V T + o p (T −1/2 ).
Firstly, we have We can further decompose (B.31) by We first show that the first term in (B.32) is o p (T −1/2 ). Define a class of function where Π and Λ are two classes of functions that maps context x ∈ X to a probability.
Define the supremum of the empirical process indexed by F κ as where the last equation is due to the definition of the noise e t . Therefore, Equation B.33 can be further written as Next, we show the second moment is bounded by Notice that κ t (x t ) ≤ C 1 < 1 and κ t (x t ) ≤ C 1 < 1 for sure for some constant C 1 < 1 (by definition of a valid bandit algorithm and results of Theorem 1), we have where C 2 is a bounded constant. Thus we have Therefore, for the second moment of the inner term of the first term, we have Therefore, we have and It follows from the maximal inequality developed in Section 4.2 of Dedecker and Louhichi (2002) that there exist some constant K ≥ 1 such that The above right-hand-side is upper bounded by Therefore, for the first term in (B.32), we have Then we consider the second term in (B.32). Given the Assumption 4.4 that by Lemma 6 in Luedtke and Van Der Laan (2016), we have the second term in (B.32) is Then, we focus on proving by Theorem 2, and notice that which is bounded, we have the inner part of (B.35) satisfies for 0 < α < 1/2. Therefore, by Lemma 6 in Luedtke and Van Der Laan (2016), we have Hence, φ T = V T + o p (T −1/2 ) holds, and thus V T = V T + o p (T −1/2 ) holds. The first step is thus completed.
Step 2: We next focus on proving V T = V T + o p (T −1/2 ). By definition of V T and V T , we We first show η 5 = o p (1). Since κ t (x t ) ≤ C 2 < 1 for sure for some constant 0 < C 2 < 1 (by definition of a valid bandit algorithm an results for Theorem 1), it suffices to show which is the direct conclusion of Lemma B.3.
Then we focus on proving ψ 6 = o p (1) here. Define a class of function where Π and Λ are two classes of functions that maps context x ∈ X to a probability.
Define the supremum of the empirical process indexed by F κ as Firstly we notice that Secondly since κ t (x t ) ≤ C 2 < 1 for sure for some constant 0 < C 2 < 1 (by definition of a valid bandit algorithm an results for Theorem 1), by the Triangle inequality, we have Therefore, we have It follows from the maximal inequality developed in Section 4.2 of Dedecker and Louhichi (2002) that there exist some constant K ≥ 1 such that The above right-hand-side is upper bounded by where O(1) denotes some universal constant. Hence, we have and ψ 6 = o p (1). Next, for ψ 7 , by triangle inequality, we have Therefore, η 6 = ψ 6 + ψ 7 = o p (1). Hence, V T = V T + o p (T −1/2 ) hold.
Step 3: Then, to show the asymptotic normality of the proposed value estimator under DREAM, based on the above two steps, it is sufficient to show as T → ∞, using Martingale Central Limit Theorem. By r t = µ{x t , a t ) + e t , we define Since e t is independent of H i−1 and x i given a t , and E {e t | a t } = 0, we have Notice that E[µ{x t , π * (x t )}] = V * by the definition, we have Thus, we have E{ξ t | H t−1 } = 0, which implies that {Z t } T t=1 , {W t } T t=1 and {ξ t } T t=1 are Martingale difference sequences. To prove Equation (B.40), it suffices to prove that (1/ √ T ) T t=1 ξ t D −→ N (0, σ 2 DR ), as T → ∞, using Martingale Central Limit Theorem. Firstly we calculate the conditional variance of ξ t given H t−1 . Note that Since e t is independent of H i−1 and x i given a t , we have By the definition of Equation (B.25), Similar as before, since lim i→∞ P {a i = π * (x)} = κ ∞ (x), we have for any > 0, there exist We firstly consider the expectation of 1 Therefore by the triangle inequality we have Since the above equation holds for any > 0, we have Since κ ∞ (x) ≤ C 2 < 1 for sure for some constant 0 < C 2 < 1 (by definition of a valid bandit algorithm an results for Theorem 1), and by Equation (B.37), we have Pr{a t = π * (x t )} > C 1 for some constant C 1 > 0, therefore we have Then we consider the variance of 1 Therefore, we have Similarly as before, we could proof Therefore, as T goes to infinity, we have , Using the same technique of conditioning on a t and x t , we have Thus the conditional Lindeberg condition is checked.
Next, recall the derived conditional variance in (B.42). By Martingale Central Limit Theorem, we have as T → ∞. Hence, we complete the proof of Equation (B.40).
Step 4: Finally, to show the variance estimator in Equation (5) is a consistent estimator of σ 2 DR . Recall that the variance estimator is Firstly we proof the first line of the above Equation (B.43) is a consistent estimator for Recall that we denote ∆ xt = µ t−1 (x t , 1) − µ t−1 (x t , 0), thus we can rewrite σ 2 T as .
We decompose the proposed variance estimator by Our goal is to prove that the first three lines are all o p (1).
Firstly, recall that Since e i is i.i.d conditional on a i , and E(e 2 i |a i = a) = σ 2 a , note that lim t→∞ Therefore the first line is o p (1).
Lastly, under the assumption that κ t (x t ) is a consistent estimator for κ t (x t ), we have the third line is o p (1) by the continuous mapping theorem.
Next we proof the second line of Equation (B.43) is a consistent estimator for Var [µ{x, π * (x)}].
By Central Limit Theorem and Continuous Mapping Theorem, we have Since x t are i.i.d, µ T {x t , π T (x t )} are i.i.d as well. Thus by the Law of Large Numbers, we have 1 T Note that since for all x ∈ [0, 1], x 2 ≤ x. Therefore, Then we consider general interval [a, b]. Define Y = X−a b−a , which is restricted in [0, 1]. Equivalently, X = (b − a)Y + a, which follows immediate that where the inequality is based on the first result. Now, by substituting µ Y = µ X −a b−a , the bound equals which is the desired result.
Therefore we have Next, we consider the second part ζ 2 . Note that where the inequality holds since