Doubly Robust Interval Estimation for Optimal Policy Evaluation in Online Learning

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 and rewards sequentially collected from the online environment, are not independent and identically distributed (i.i.d.) since they depend on the previous history and the running policy (see the right panel of Figure 1). 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 using offline data by modeling the behavior policy or the conditional mean outcome. In addition, we note that the target policy to be evaluated in offline policy evaluation is fixed and generally known, whereas 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. Although numerous methods have recently been proposed to evaluate 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 is directly applicable to our problem, as 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. However, there may not exist a unified best action for all subjects due to heterogeneity, and thus evaluating the value of one single optimal action cannot fully address the policy evaluation in such a setting. However, although commonly used in the regret analysis, the average of collected outcomes is not a good estimator of 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-and-exploitation 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 in two ways. First, it determines the convergence rate of the online conditional mean estimator under each action. Second, it indicates the data points used to match the value under the optimal policy. To our knowledge, the regret analysis in the current bandit literature is based on the binding of 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 effort has been made in 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, Chen et al. (2020) proposed an inverse probability weighted value estimator to infer the value of optimal policy using the $\epsilon$-Greedy (EG) method. These two works did not discuss how to account for the exploration-and-exploitation 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. However, 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 sufficient sampling of different arms. Such an assumption can be violated in many commonly used bandits (see details shown in Theorem 4.1). Although there are other works that focus on statistical inference for adaptively collected data (Dimakopoulou et al., 2021; Zhang et al., 2021; Khamaru et al., 2021; Ramprasad et al., 2022) in bandit or reinforcement learning setting, our work handles policy evaluation from a completely unique angle to infer the value of optimal policy by investigating the exploration rate in online learning.

In this paper, we aim to overcome the aforementioned difficulties of policy evaluation in online decision-making. Our contributions are expressed 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 nongreedy policy (i.e., a nonoptimal action) given the current information over time, in contrast to the probability of exploitation for taking greedy actions. Specifically, we consider three commonly used bandit algorithms for exposition, including the UCB, TS, and EG methods. We note that the probability of exploration is prespecified by users in EG 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 to propose 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 that 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 in the policy evaluation of online learning.

The remainder 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 introduce the DREAM method and its implementation details. 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 simulation studies 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 of any known policy in online learning. All the additional results and technical proofs are given in the appendix.

In contextual bandits, at each time step $t\in\mathcal{T}\equiv\{1,2,3,\cdots\}$, we observe a $d$-dimensional context $\bm{x}_{t}$ drawn from a distribution $P_{\mathcal{X}}$ which includes 1 for the intercept, choose an action $a_{t}\in\mathcal{A}$, and then observe a reward $r_{t}\in\mathcal{R}$. Denote the history observations prior to time step $t$ as $\mathcal{H}_{t-1}=\{\bm{x}_{i},a_{i},r_{i}\}_{1\leq i\leq t-1}$. Suppose that the reward given $\bm{x}$ and $a$ follows $r\equiv\mu(\bm{x},a)+e$, where $\mu(\bm{x},a)\equiv\mathbb{E}(r|\bm{x},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 $|\mu(\bm{x},a)|\leq U$. The noise term $e$ is independent $\sigma$-subgaussian at the time step $t$ independently of $\mathcal{H}_{t-1}$ given $a_{t}$ for $t\in\mathcal{T}$. Let the conditional variance be ${\mathbb{E}}(e^{2}|a)=\sigma^{2}_{a}$. The value (Dudík et al., 2011) of a given policy $\pi(\cdot)$ is defined as

We define the optimal policy as $\pi^{*}(\bm{x})\equiv\operatorname*{arg\,max}_{a\in\mathcal{A}}\mu(\bm{x},a),\forall\bm{x}\in\mathcal{X}$, which finds the optimal action based on the conditional mean outcome function given a context $\bm{x}$. Thus, the optimal value can be defined as $V^{*}\equiv V(\pi^{*})=\mathbb{E}_{\bm{x}\sim P_{\mathcal{X}}}\left[\mu\{\bm{x},\pi^{*}(\bm{x})\}\right]$. In the rest of this paper, to simplify the exposition, we focus on two actions, that is, $\mathcal{A}=\{0,1\}$. Then the optimal policy is given by

Our goal is to infer the value under the optimal policy $\pi^{*}$ using the online data sequentially generated by a bandit algorithm. Since the optimal policy is unknown, we estimate the optimal policy from the online data as $\widehat{\pi}_{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., $\mu(\bm{x},a)=\bm{x}^{\top}\bm{\beta}(a),$ where $\bm{\beta}(\cdot)$ is a smooth function and can be estimated via a ridge regression based on $\mathcal{H}_{t-1}$ as

where $\bm{I}_{d}$ is a $d\times d$ identity matrix, $\bm{D}_{t-1}(a)$ is a $\bm{N}_{t-1}(a)\times d$ design matrix at time $t-1$ with $\bm{N}_{t-1}(a)$ as the number of pulls for action $a$, $\bm{R}_{t-1}(a)$ is the $\bm{N}_{t-1}(a)\times 1$ vector of the outcomes received under action $a$ at time $t-1$, and $\omega$ is a positive and bounded constant as the regularization term. There are two main reasons to choose the ridge estimator instead of the ordinary least squares estimator that is considered in Deshpande et al. (2018); Zhang et al. (2020); Chen et al. (2020). First, the ridge estimator is well defined when $\bm{D}_{t-1}(a)^{\top}\bm{D}_{t-1}(a)$ is singular and its bias is negligible when the time step is large. Second, the parameter estimations in the ridge method are in accordance with the linear UCB (Li et al., 2010) and the linear TS (Agrawal and Goyal, 2013) methods (detailed in the next section) with $\omega=1$. Based on the ridge estimator in (1), the online conditional mean estimator for $\mu$ is defined as $\widehat{\mu}_{t-1}(\bm{x},a)=\bm{x}^{\top}\widehat{\bm{\beta}}_{t-1}(a)$. With two actions, the estimated optimal policy at time step $t$ is defined by

We note that the linear form of $\mu(\bm{x},a)$ can be relaxed to the non-linear case as $\mu(\bm{x},a)=f(\bm{x})^{\top}\bm{\beta}(a)$, where $f(\cdot)$ is a continuous function (see examples in our simulation studies in Section 5). Then the corresponding online conditional mean estimator for $\mu$ is defined as $\widehat{\mu}_{t-1}(\bm{x},a)=f(\bm{x})^{\top}\widehat{\bm{\beta}}_{t-1}(a)$ based on $\mathcal{H}_{t-1}$.

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 deviation based on $\mathcal{H}_{t-1}$ be $\widehat{\sigma}_{t-1}(\bm{x},a)=\sqrt{\bm{x}^{\top}\{\bm{D}_{t-1}(a)^{\top}\bm{D}_{t-1}(a)+\omega\bm{I}_{d}\}^{-1}\bm{x}}.$ The action at time $t$ is selected by

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 $\bm{x}$ and $a$ such that $R\sim\mathcal{N}\{\bm{x}^{\top}\bm{\beta}(a),\rho^{2}\}$ with a known parameter $\rho^{2}$. If the prior for $\bm{\beta}(a)$ at time $t$ is

where $\mathcal{N}_{d}$ is the $d$-dimensional multivariate normal distribution, we have the posterior distribution of $\bm{\beta}(a)$ as

for $a\in\{0,1\}$. At each time step $t$, we draw a sample from the posterior distribution as $\bm{\beta}_{t}(a)$ for $a\in\{0,1\}$, and select the next action within two arms by $a_{t}=\mathbb{I}\left\{\bm{x}_{t}^{\top}\bm{\beta}_{t}(1)>\bm{x}_{t}^{\top}\bm{\beta}_{t}(0)\right\}.$
$\epsilon$-Greedy (EG) (Sutton and Barto, 2018): Recall the estimated conditional mean outcome for action $a$ as $\widehat{\mu}_{t}(\bm{x},a)$ given a context $\bm{x}$. Under EG method, the action at time $t$ is selected by

where $\delta_{t}\sim\text{Bernoulli}(1-\epsilon_{t})$ and the parameter $\epsilon_{t}$ controls the level of exploration as pre-specified by users.

We next quantify the probability of exploring non-optimal actions at each time step. To be specific, define the status of exploration as $\mathbb{I}\{a_{t}\not=\widehat{\pi}_{t}(\bm{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, $\widehat{\pi}_{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}\in\mathcal{A}$ and history $\mathcal{H}_{t-1}$. According to (3), $\kappa_{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 $\bm{x}_{t}$ at time step $t$, i.e., ${\mbox{Pr}}\{a_{t}\not=\pi^{*}(\bm{x}_{t})\}$. This is different from our proposed probability of exploration $\kappa_{t}(\bm{x}_{t})\equiv{\mbox{Pr}}\{a_{t}\not=\widehat{\pi}_{t}(\bm{x}_{t})\}$. The main difference lies in the estimated optimal policy from the collected data at the current time step $t$, i.e., $\widehat{\pi}_{t}$, in $\kappa_{t}(\bm{x}_{t})$. If properly designed and implemented, the estimated optimal policy under a bandit algorithm $\widehat{\pi}_{t}$ will eventually converge to the true optimal policy $\pi^{*}$ when $t$ is large, which yields $\kappa_{t}(\bm{x})\to\lim_{t\rightarrow\infty}{\mbox{Pr}}\{a_{t}\not=\pi^{*}(\bm{x})\}$. In practice, we can estimate $\kappa_{t}(\bm{x}_{t})$ sequentially by using $\{i,\bm{x}_{i}\}_{1\leq i\leq t}$ as inputs and $\{\mathbb{I}\{a_{i}=\widehat{\pi}_{i}(\bm{x}_{i})\}\}_{1\leq i\leq t}$ as outputs via parametric or non-parametric tools. We denote the corresponding estimator as $\widehat{\kappa}_{t}(\bm{x}_{t})$ for time step $t$. Such implementation conditions are explicitly described in Section 3.

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 the 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 $\widehat{\bm{\beta}}_{t}(a)$, which can be simplified as $C_{1}\exp(-C_{2}tp_{t}^{2})$, for some constants $\{C_{j}\}_{1\leq j\leq 2}$, by noticing the constant $h$ and $\lambda$, the dimension $d$, the subgaussian parameter $\sigma$, and the bound $L_{\bm{x}}$ are positive and bounded, under bounded true coefficients $\bm{\beta}(a)$. Recall the clipping constraint that $0<p_{t}<1$ is non-increasing sequence. This tail bound is asymptotically equivalent to $\exp(-tp_{t}^{2})$. The established results in Lemma 4.1 work for general bandit algorithms including UCB, TS, and EG. These tail bounds are aligned with the bound $\exp(-t\epsilon_{t}^{2})$ 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 $\widehat{\bm{\beta}}_{t}(a)$, if $tp_{t}^{2}\rightarrow\infty$ as $t\rightarrow\infty$. We can further obtain the tail bound for the estimated difference between the conditional mean outcomes under two actions by Lemma 4.1 as detailed in the following corollary.

The above corollary quantifies the uncertainty of the online estimation of the conditional mean outcomes, and thus provides a crucial middle result to further access the probability of exploration by noting $\widehat{\pi}_{t}(\bm{x})=\mathbb{I}\left\{\widehat{\mu}_{t-1}(\bm{x},1)>\widehat{\mu}_{t-1}(\bm{x},0)\right\}$ in (2). More specifically, we derive the probability of exploration at each time step under the three discussed bandit algorithms for exposition in the following theorem.

The theoretical order of $\kappa_{t}(\cdot)$ 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 $\epsilon_{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_{t-1}^{2}\rightarrow\infty$ for TS, as $t\rightarrow\infty$, the upper bound for $\kappa_{t}(\bm{x}_{t})$ decays to zero with an asymptotically equivalent convergence rate as $\mathcal{O}\{\exp(-(t-1)p_{t-1}^{2})\}$ up to some constant. Similarly, for UCB, with an arbitrarily small $\xi$ at an order of $\mathcal{O}(1/\sqrt{tp_{t}})$, as $t\rightarrow\infty$, the upper bound for $\kappa_{t}(\bm{x}_{t})$ decays to zero as long as $(t-1)p_{t-1}^{2}\rightarrow\infty$. Theorem 1 also indicates that without the clipping required in Assumption 4.2 and implemented in step (4) of Algorithm 1, the exploration for non-optimal arms might be insufficient, leading to a possibly invalid and biased inference for the online conditional mean.

We 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. Specifically, denote $\kappa_{\infty}(\bm{x})\equiv\lim_{t\to\infty}\kappa_{t}(\bm{x})=\lim_{t\rightarrow\infty}{\mbox{Pr}}\{a_{t}\not=\pi^{*}(\bm{x})\}$ given a context $\bm{x}$. Assume the conditions in Theorem 1 hold and $tp_{t}^{2}\rightarrow\infty$ as $t\rightarrow\infty$, we have the upper bound of the probability of exploration decays to zero in Theorem 1 for UCB and TS. Since $\kappa_{t}(\cdot)$ is nonnegative by its definition, it follows from Sandwich Theorem immediately that $\kappa_{\infty}(\cdot)$ exist for UCB and TS, and $\kappa_{\infty}(\cdot)=\lim_{t\to\infty}\epsilon_{t}/2$ for EG. By using this limit, we can further characterize the following theorem for asymptotics and inference.

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, $\kappa_{\infty}(\bm{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 conclusion in Theorem 1, i.e., a clipping rate $p_{t}$ of an order larger than $\mathcal{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.

In this section, we further derive the asymptotic normality of $\sqrt{T}(\widehat{V}_{T}-V^{*})$. The following additional assumption is required to establish the double robustness of DREAM.

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 studied in the causal inference literature (see e.g., Farrell, 2015; Luedtke and Van Der Laan, 2016; Smucler et al., 2019; Hou et al., 2021; Kennedy, 2022) 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 in Theorem 2, we have $||\mu(\bm{x},a)-\widehat{\mu}_{t}(\bm{x},a)||_{2,T}=\mathcal{O}_{p}(T^{-1/2})$ for all $a\in\mathcal{A}$, thus Assumption 4.4 holds as along as $||\kappa_{t}(\bm{x})-\widehat{\kappa}_{t}(\bm{x})||_{2,T}=o_{p}(1)$. We then have the asymptotic normality of $\sqrt{T}(\widehat{V}_{T}-V^{*})$ as stated in the following theorem.

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-i.i.d. 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\rightarrow\infty$ 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 a thorough account. Our method thus fills a crucial gap in policy evaluation of online learning. By Theorem 3, a two-sided $1-\alpha$ confidence interval (CI) for $V^{*}$ is $[\widehat{V}_{T}-z_{\alpha/2}\widehat{\sigma}_{T}/\sqrt{T},\quad\widehat{V}_{T}+z_{\alpha/2}\widehat{\sigma}_{T}/\sqrt{T}]$, where $z_{\alpha/2}$ denotes the upper $\alpha/2-$th quantile of a standard normal distribution.

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

By noticing that $\mu(\bm{x}_{t},\pi^{*}(\bm{x}_{t}))-\mu(\bm{x}_{t},a_{t})=\Delta_{\bm{x}_{t}}$ if $a_{t}\neq\pi^{*}(\bm{x}_{t})$ and 0 otherwise, we have

We note that the indicator function is equivalent to $|a_{t}-\pi^{*}(\bm{x}_{t})|$ and is bounded by $|a_{t}-\widehat{\pi}(\bm{x}_{t})|+|\widehat{\pi}(\bm{x}_{t})-\pi^{*}(\bm{x}_{t})|$. Thus, we can divide the regret defined in Equation (6) into two parts as $R_{T}\leq R_{T}^{(1)}+R_{T}^{(2)}$ where

is the regret from the exploration and $R_{T}^{(2)}=\sum_{t=1}^{T}{\mathbb{E}}\left[\Delta_{\bm{x}_{t}}|\widehat{\pi}(\bm{x}_{t})-\pi^{*}(\bm{x}_{t})|\right]$ is the regret from the exploitation. It is well known that the regret from the exploitation $R_{T}^{(2)}$ 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_{T}^{(1)}$ from the exploration for UCB and TS here.

Since $\Delta_{\bm{x}_{t}}$ is bounded and the upper bound of ${\mathbb{E}}|a_{t}-\widehat{\pi}(\bm{x}_{t})|={\mathbb{E}}[\mathbb{I}\{a_{t}\not=\widehat{\pi}_{t}(\bm{x}_{t})\}]=\kappa_{t}(\bm{x}_{t})$ has an asymptotically equivalent convergence rate as $\mathcal{O}\{\exp(-tp_{t}^{2})\}$ up to some constant by Theorem 1, there exists some constant $C$ such that the regret from the exploration is bounded by

If we choose $p_{t}=\sqrt{{\alpha\log t}/{t}}$ for some $\alpha\in(0,1)$, the regret $R_{T}^{(1)}$ is bounded by $\sum_{t=1}^{T}\mathcal{O}\{t^{-\alpha}\}=\mathcal{O}\{T^{1-\alpha}\}$, where the equation is calculated using Lemma 6 in Luedtke and Van Der Laan (2016). Thus, we still have sublinear regret under DREAM.

We could extend our method to evaluate a new known policy $\pi^{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 $\pi^{E}$, we propose its doubly robust value estimator as

where $T$ is the current time step or the termination time and $\widehat{p}_{t-1}(a_{t}|\bm{x}_{t})$ is the estimator for the propensity score of the chosen action $a_{t}$ denoted as $p_{t-1}(a_{t}|\bm{x}_{t})$. The following theorem summarizes the asymptotic properties of $\widehat{V}_{T}({\pi}^{E})$, built on Theorem 2.