1 Introduction↩︎

Off-policy evaluation is the problem of estimating the benefits of one treatment assignment policy using historical data that was collected using another. For example, in personalized healthcare we may wish to use historical data to evaluate how particular groups of patients will respond to a given treatment regime for the design of future clinical trials [1]; in targeted advertising one may want to understand how alternative advertisements perform for different consumer segments [2]. The estimation challenge arises since an individual’s outcome is observed only for the assigned treatments, so counterfactual outcomes for alternative treatments are not observed. There is a large literature on this problem in the cases where historical observations, which are collected by one or multiple policies, are independent from one another [3]–[6]. However, it has been increasingly common for data to be collected in adaptive experiments, for example using contextual bandit algorithms [7]–[9]. Contextual bandits trade off exploration and exploitation in an attempt to learn the policy that best targets the treatment assignment to an observation’s context (e.g., a patient’s characteristics). In these experiments, assignment probabilities depend on the context in a way that is updated over time as the algorithm learns from past data. In this paper, we focus on off-policy evaluation using data collected by contextual bandits.

One common approach to off-policy evaluation, often called the direct method (DM), is to use the historical data to estimate a regression model that predicts outcomes for each treatment/context pair, then averages this model’s predictions for treatments assigned by the target policy. However, regression models fit to adaptively collected data tend to be biased [10]–[13], and this bias is inherited by DM estimators. In particular, downward bias tends to arise when fitting data generated by a bandit, as treatments for which we observe random downward fluctuations early on tend to be sampled less afterward than those for which we observe upward ones. Therefore, downward fluctuations get corrected less than upward ones when more data arrives. Consider the following example.

Example . We run a contextual bandit experiment with a Thompson sampling agent [14], collecting \(1000\) observations for one simulation. At each time \(t\), a context \(X_t\) is sampled from the context space \(\{x_0, x_1, x_2, x_3, x_4\}\) with probability \([0.6, 0.1, 0.1, 0.1, 0.1]\). The agent chooses one \(W_t=w_j\) out of five treatments \(\{w_0, w_1, w_2, w_3, w_4\}\) based on assignment probabilities that are computed using previous observations, and observes the outcome \(\mathop{\mathrm{\mathbb{I}}}\{i=j\} + \varepsilon_t\), where \(\varepsilon_t\) is standard normal. The target policy always assigns treatment \(W_t=w_0\).

A natural implementation of the direct method estimates the target policy value by \(T^{-1}\sum_{t=1}^{T} \hat{\mu}_0(X_t)\), where \(\hat{\mu}_0(x)\) is the sample mean calculated from observed outcomes under treatment \(w_0\) on context \(x\). Figure 1 shows that it has substantial bias.

An unbiased alternative, inverse propensity weighting (IPW) [15], weights observations from the collected data to look like treatment were assigned using the target policy. However, when the assignments made during data collection differ substantially from those made by the target policy, called low overlap between policies, this requires the weights, and therefore the variance, to be large [16]. The doubly robust (DR) estimator [3], also unbiased, reduces variance by combining DM and IPW. It uses a weighted average of regression residuals to correct the bias of the DM estimator, reducing variance to a degree determined by the accuracy of the regression model’s predictions. This estimator is optimal in large samples when historical observations are independent and identically distributed [17]. With observations from adaptive experiments, while what is optimal is not well understood, there is strong evidence that DR estimator is outperformed by other estimators in terms of mean squared error [18].

This difference in behavior is caused by drifting overlap in adaptive experiments. As the experimenter shifts the data-collection policy in response to what they observe, overlap with the target policy can deteriorate. As a result, the variance of both the IPW and DR estimators can be unacceptably large. This is exacerbated in contextual settings, as importance weights can grow without bound even when there exists a relatively small set of contexts for which overlap is low. In Example [example], the set of contexts for which overlap worsens has total probability \(0.4\), but, as shown in Figure 1, this is enough to inflate the variance of the DR estimator.

Recently, shrinking importance weights toward one has been explored as a variance reduction strategy for the DR estimator [19]–[22]. This can substantially reduce variance by introducing a potentially small bias if the amount of shrinkage is chosen well, but choosing this is a challenging tuning problem. An alternative approach focuses on local stabilization. For example, when data is collected in batches, [23] proposes the use of a hypothesis test for the policy value based on the average of batch-specific studentized statistics. [23] shows that the variance is stabilized within each batch using this hypothesis test. [24] propose a locally studentized version of the DR estimator that does not require batched collection, using a rolling-window estimate of a term in the DR estimator’s standard deviation. [18] refine this approach, observing that the optimal way to aggregate observations with different variances is not an inverse standard deviation weighted (standardized/studentized) average but an inverse variance weighted one. Focusing on the case of multi-armed bandits, they show that locally inverse variance weighted averages can reduce asymptotic variance while retaining its desirable inferential properties if a particular approximate rolling-window variance estimate is used. We view our method as an extension of [18] to contextual bandits, where the story of local stabilization is more complex because the relevant notion of local variance depends on context as well as treatment.

2 Setting↩︎

We begin by formalizing the problem of off-policy evaluation in contextual bandits and introducing some notation. We use potential outcome notation [4], denoting by \(Y_t(w)\) a random variable representing the outcome that would be observed if at time \(t\) an individual were assigned to a treatment \(w\) from a finite set of options \(\{1 \ldots K\}\). In any given experiment, this individual can be assigned only one treatment \(W_t\), so we observe only one realized outcome \(Y_t = Y_t(W_t)\). Associated to each individual is a context \(X_t\); a policy \(\pi\) assigns individuals with context \(x\) to a treatment \(w\) with probability \(\pi(x,w)\).

We focus on the “stationary” environment where individuals, represented by a context \(X_t \in \mathcal{X}\) and a vector of potential outcomes \(\big(Y_t(1),\) \(\ldots, Y_t(K)\big)\), are independent and identically distributed. However, our observations \((X_t, W_t, Y_t)\) are neither independent nor identically distributed because the assignment \(W_t\) depends on the observations before it. We assume that an individual’s treatment assignment is randomized, with nonzero probability of receiving each treatment,⁴ as a function of their context and previous observations. We write \(H_t = \{(X_s,W_s,Y_s): s \le t\}\) for the history of observations up to time \(t\); \(e_t(x,w)=\mathop{\mathrm{\mathbb{P}}}(W_t=w \mid X_t=x, H_{t-1})\) for the conditional randomization probability, also known as the propensity score; and \(\mu_t(x,w)=\mathop{\mathrm{\mathbb{E}}}[Y_t(w) \mid X_t=x]\) for the regression of the outcome on context. We summarize these assumptions as follows.

Our goal is to estimate the quantity \[Q(\pi) := \sum_{w=1}^K \mathop{\mathrm{\mathbb{E}}}[\pi(X_t, w) Y_t(w)],\] which is the average outcome attained when individuals are assigned treatment in accordance with the policy \(\pi\), typically called the average policy value.

Because Assumption 1(a) implies \(\mu_t(x,w)\) is constant in \(t\), we will write \(\mu(x,w)\) in its place from here on. To simplify notation, we will also write for , write \(||f(z)||_{\infty}\) for the sup-norm \(\sup_{z \in \mathcal{Z}} |f(z)|\) of a function \(f: \mathcal{Z} \to \mathbb{R}\), and let \(Q(x, \pi) := \sum_{w} \mathbb{E}_{}\left[{\pi(X_t, w) Y_t(w)|X_t=x}\right]\).

3 Doubly robust estimator↩︎

The doubly robust (DR) estimator considered here takes the form \[\label{eq:qdr} \widehat{Q}_T^{DR}(\pi) := \frac{1}{T} \sum_{t=1}^{T} \widehat{\Gamma}_t(X_t, \pi),\tag{1}\] where the objects being averaged are doubly-robust scores, \[\label{eq:aipw} \widehat{\Gamma}_t(X_t, \pi) := \sum_{w} \pi(X_t,w) \Big( \widehat{\mu}_t(X_t, w) + \frac{\mathop{\mathrm{\mathbb{I}}}\{W_t=w\}}{e_t(X_t,w)}(Y_t-\widehat{\mu}_t(X_t, w))\Big).\tag{2}\] Above, \(\widehat{\mu}_t(x,w)\) is an estimate of the outcome regression \(\mu(x, w)\) based only on the history \(H_{t-1}\). Similar estimators are widely used, including in bandit settings [3], [18], [25], [26].

Recalling that the assignment probabilities \(e_t(X_t, w)\) and the estimated regression \(\widehat{\mu}_{t}(X_t, w)\) are functions of the history, it is straightforward to show that the DR scores are unbiased estimators of the policy value \(Q(\pi)\) conditional on past history and, by the tower property, their average \(\widehat Q_T^{DR}(\pi)\) is unbiased.

We refer readers to Appendix 8.1 for proof details. The variance of the DR estimator is largely governed by the similarity between the policy being evaluated and the assignment probabilities. This phenomenon is expected since we should be better able to evaluate policies that assign treatments in a similar manner as that used when collecting data. The next proposition, which quantifies this intuition, is convenient when considering variance-minimizing schemes in the next section.

The proof is deferred to Appendix 8.2. Averaging over the contexts in ?? , we derive a variant for the context-free conditional variance. \[\label{eq:gamma95condvar} L\leq \mathrm{Var}_{}\left({\widehat{\Gamma}_t(X_t, \pi)|H_{t-1}}\right) \Big/ \mathop{\mathrm{\mathbb{E}}}\Big[\sum_{w}\frac{\pi^2(X_t,w)}{e_t(X_t,w)}\Big|H_{t-1}\Big] \leq U.\tag{3}\]

4 Adaptive weighting↩︎

When overlap between the evaluation policy and the assignment mechanism deteriorates as \(t\) grows (in the sense that \(\sum_w \pi^2(X_t, w) / e_t(X_t, w)\) increases), the DR estimator 1 can have high variance and heavy tails with large samples. This phenomenon is demonstrated in Figure 1. In light of Proposition 2, the problem is that the DR estimator is a uniformly-weighted average of scores with variances that can differ dramatically. We can improve on the DR estimator by averaging those scores with non-uniform weights \(h_t\) that stabilize variance term-by-term. \[\label{eq:qnc} \widehat{Q}^{NC}_T(\pi) := \sum_{t=1}^T \frac{h_t}{\sum_{s=1}^T h_s} \widehat{\Gamma}_t(X_t, \pi),\tag{4}\]

As stabilizing weights, we consider both weights that approximately standardize the terms and approximate inverse variance weights. Both rely on the variance proxy from 3 : \[\label{eq:hnc95infeasible} h_t := \phi\Big( \mathop{\mathrm{\mathbb{E}}}\Big[ \sum_{w} \frac{\pi^2(X_t;w)}{e_t(X_t;w)}\Big|H_{t-1}\Big] \Big),\tag{5}\] where different functions \(\phi\) yields weights that have different properties:

(i) StableVar: \(\phi(v)=\sqrt{1/v}\) yields weights \(h_t\) that approximately standardize the terms of \(\widehat{Q}^{NC}_T\).

(ii) MinVar: \(\phi(v)=1/v\) yields weights \(h_t\) that approximately minimize the variance of \(\widehat{Q}^{NC}_T\).

We refer to both weights in 5 as non-contextual weights, since the realized context \(X_t\) is integrated out. In practice, one may not compute oracle weights 5 exactly. We thus use a feasible approximation in our simulation, \[\label{eq:hnc95feasible} \widetilde{h}_t := \phi\Big( \frac{1}{t-1} \sum_{s=1}^{t-1} \sum_{w} \frac{\pi^2(X_s;w)}{e_t(X_s;w)} \Big).\tag{6}\]

The idea of MinVar weighting scheme is similar to the weighted IPW estimator proposed in [5], where the authors use the (context-independent) inverse variance to weight samples from multiple logging policies. The essential difference is that, in the adaptive setting we consider, each observation is from a new logging policy, so we must estimate inverse variance weights for each observation instead of for a relatively small number of logging policies.

The StableVar weights are less effective at reducing variance than MinVar, but would allow us to construct asymptotically valid confidence intervals if we had access to an oracle that would allow us to compute the conditional expectation in 5 . To start, we introduce additional assumptions on the data generating process and the nuisance estimator \(\hat{\mu}_t\).

Assumption 2(a) is satisfied for various types of non-constant random variables including, for example, bounded rewards. Assumption 2(b) requires that exploration in the adaptive experiments should not be reduced faster than some polynomial decay rate, and is also enforced when analyzing the asymptotics of adaptive weighting for multi-armed bandits in [18]. Assumption 2(c) is standard in the literature on DR estimators [16], [27]. We state a limit theorem, proven in Appendix 10, for for \(\hat{Q}_T^{NC}\) using StableVar weighting.

Condition ?? says that the inverse of assignment probabilities, which essentially represents the variance of estimating the value of each arm, is asymptotically equivalent to its expectation. To understand it, consider the thought experiment of running multiple simulations of a bandit setting in which arms are identical. If the bandit algorithm is “too greedy”, spurious fluctuations in arm value estimates at the beginning can decide the algorithm’s long-run behavior. In some of these simulations, \(e_t(x, w)\) may increase to one while in others it may decay to zero. Condition ?? requires that the long-run behavior of the assignment algorithm is stable. For many bandit algorithms, it will hold if, for every point of the context space, the signal from the best arm is strong enough to have it discovered eventually. For some tractable contextual bandit algorithms, for example [28], it holds without qualification.

5 Adaptive contextual weighting↩︎

We can control variance better by using context-dependent weights \(h_t(x)\). Thinking of the DR estimator \(\widehat Q_T^{DR}(\pi)\) as a double sum , it is natural to stabilize terms in the inner sum rather than the outer, as proposed in Section 4.

Figure 2 demonstrates how, in Example [example], the contextual variance proxy from ?? varies with context. Recall that the target policy always assigns treatment \(w_0\): \(\pi(\cdot, w_0)=1\). For context \(x_0\), treatment \(w_0\) is optimal, so \(e_t(x_0, w_0)\) increases over time as the experimenter learns to assign it. Thus, the variance proxy \(\sum_{w}\pi^2(x_0,w)/e_t(x_0,w)\) decreases. For other contexts, \(w_0\) is suboptimal and the variance proxy increases, which drives the increase in the non-contextual variance proxy (dashed black line in Figure 2) used in 5 .

We thus propose contextual weighting to observe such variation of score variance in context: \[\label{eq:qc} \widehat{Q}_T^C(\pi) = \sum_{t=1}^T \frac{h_t(X_t)}{\sum_{s=1}^T h_s(X_t)}\widehat{\Gamma}_t(X_t, \pi).\tag{7}\] Here, adaptive weight \(h_t(\cdot)\) is a function of context \(x\in\mathop{\mathrm{\mathcal{X}}}\). The normalized term weights the score We define the contextual adaptive weight \(h_t(x)\) as a function of the context-specific variance proxy from ?? , \[\label{eq:hc} h_t(x) = \phi\Big(\sum_{w}\frac{\pi^2(x,w)}{e_t(x,w)}\Big), \quad x\in \mathop{\mathrm{\mathcal{X}}},\tag{8}\] where, as in Section 4, \(\phi(v)=\sqrt{1/v}\) for StableVar weights and \(\phi(v)=1/v\) for MinVar weights.

Like its counterpart with non-contextual weights, the estimator 7 admits a central limit theorem when contextual StableVar weights are used. However, our result requires more fragile assumptions on the data generating process and assignment mechanism. Again, we focus on evaluating a fixed-arm policy that always assigns a pre-specified treatment \(w\).

We defer the proof to Appendix 11. Condition ?? requires the similar stability from assignment probabilities as Condition ?? , while this time it in addition requires a more strict assumption—a pair of inverse of \(e_t\) needs to be asymptotically equivalent to its expectation.

6 Experimental results↩︎

This section provides an empirical investigation of different estimators for off-policy evaluation in contextual bandits.⁵ We consider four estimators: (i) the DM estimator \[\widehat{Q}^{DM}_T(\pi)=T^{-1}\sum_{t=1}^T\sum_{w}\widehat{\mu}_{T}(X_t,w)\pi(X_t, w),\] (ii) the DR estimator \(\smash{T^{-1} \sum_{t=1}^T \widehat{\Gamma}_t}(X_t, \pi)\), (iii) the adaptively-weighted estimator with non-contextual MinVar and StableVar weights as in Section 4, and (iv) the adaptively-weighted estimator with contextual MinVar and StableVar weights as in Section 5. In all estimators, \(\hat{\mu}_t(\cdot,w)\) is a linear model fit via least squares on the observations \(\{(X_s,Y_s) : W_s=w,\;s < t\}\).

We consider two setups. In Section 6.1, we have a synthetic data-generating process (DGP). In Section 6.2, the DGP is adapted from multi-class classification datasets on OpenML [29]. In both cases, we show that adaptive weighting reduces variance and MSE significantly and that contextual weighting outperforms non-contextual weighting.

6.0.0.1 Target policies.

We estimate the contrast \(\Delta = Q(\pi_1)-Q(\pi_2)\) between the best contextual policy \(\pi_1\) and the best non-contextual policy \(\pi_2\). The former assigns individuals with context \(x\) to the treatment \(w^*(x)=\arg\max_w \mathop{\mathrm{\mathbb{E}}}[Y_t(w) \mid X=x]\); the latter assigns all individuals to \(w^*=\arg\max_w \mathop{\mathrm{\mathbb{E}}}[Y_t(w)]\). To construct this estimator \(\widehat{\Delta}_T\) and corresponding estimated variance \(\widehat{V}_T\), we re-visit the discussion starting from Section 3, defining the doubly robust score for the contrast as the difference in doubly robust scores for the two policies. We use variants of the adaptive weights discussed in Sections 4 & 5 with the variance proxy \(\sum_w (\pi_1(x,w)-\pi_2(x,w))^2/e_t(x,w)\).

6.0.0.2 Metrics.

In Section 6.1, we evaluate the performance of each estimator in terms of its root mean squared error (RMSE), bias, and the radius and coverage of \(95\%\) confidence intervals based on the approximate normality of studentized estimates, as in Theorems 1 and 2. In Section 6.2, we focus on RMSE, bias, and standard errors.

6.1 Synthetic datasets↩︎

6.1.0.1 Data-generating process

We consider a four-arm contextual bandit setting. Each time step, the algorithm observes a vector of context \(X_t \sim \mathop{\mathrm{\mathcal{N}}}(0, I_3)\) drawn independently. We consider two outcome models. In the no-signal setting, \(\mu(x,w)=0\) for all contexts and treatments. In the signal setting, we divide the context space into four regions, depending on whether the first two coordinates \(X_{t, 1}\) and \(X_{t, 2}\) are above or below \(0.5\). In each region, one of the treatments has \(\mu(x,w)=0.7\), where all others have \(\mu(x,w)=0\), so each region is associated with a distinct treatment with positive mean outcome. In both settings, we observe \(Y_t = \mu(X_t,W_t) + \varepsilon_t\) where \(\varepsilon_t \sim \mathop{\mathrm{\mathcal{N}}}(0,1)\).

6.1.0.2 Assignment probabilities

A modified Thompson sampling algorithm interacts with the environment, collecting data in batches of size \(100\). During the first batch, the agent assigns arms uniformly at random. For each subsequent batch, the agent first discretizes context space using PolicyTree [30] based on previous observations. Next, for each subspace, the algorithm computes tentative Thompson sampling assignment probabilities. Finally, a lower bound is imposed on these probabilities, so that final assignment probabilities are guaranteed to satisfy \(e_t\geq t^{-0.8}/4\).

• RMSE. Figure 3 shows that in both scenarios, adaptive weighting reduces RMSE significantly as compared to DR, and contextual weighting has a larger improvement than non-contextual weighting. When there is signal, DM is outperformed by all other methods as a result of substantial bias. When there is no signal, it performs best, as the systematic biases in evaluating each of the two policies—which generate identical rewards in the case of no signal—cancel out.

• Inference. Figures 3 shows that in the signal scenario, adaptive weighting has nominal coverage with improved power relative to DR; in the no-signal scenario, only non-contextual weighting has nominal coverage. Such inferential properties are also verified by the t-statistics shown in Figure 4. This is in line with our theorems—Theorem  2 for contextual weighting requires higher-order stability of assignment probabilities as compared to Theorem 1. DM tends to be much more biased than variable, so confidence intervals based on the assumption of asymptotic normality with negligible bias and variance of approximately \(\widehat{V}^{DM}_T(\pi) = T^{-2}\sum_{t=1}^T\big(\widehat{Q}^{DM}_T(\pi)-\sum_{w}\widehat{\mu}_{T}(X_t,w)\pi(X_t,w)\big)^2\) do not yield much coverage in our simulations; thus, we omit it in our coverage plots.

6.2 Sequential classification with bandit feedback↩︎

6.2.0.1 Data generating process

In this section we follow prior work [3], [20], [22], [31] and use multi-class classification datasets to generate bandit problems. The idea is to transform a sequential classification problem into a bandit problem, by taking features as contexts and classes as arms. At each time step, the bandit algorithm is shown a vector of features sampled uniformly from the dataset and must choose a corresponding class. If it manages to label the observation correctly, the bandit algorithm receives reward \(Y_t = 1 + \varepsilon_t\) for \(\varepsilon_t \sim \mathop{\mathrm{\mathcal{N}}}(0,1)\); otherwise, \(Y_t = \varepsilon_t\). Here, we consider \(86\) public datasets from OpenML [29] (see Appendix 12 for the list of datasets), which vary in number of classes, number of features, and number of observations, as summarized in Table 1.

6.2.0.2 Data collection

A linear Thompson sampling agent [7] is used to collect data with assignment probability floor \(t^{-0.5}/K\), where \(K\) is number of arms/classes.

6.2.0.3 Performance

For each dataset, we calculate bias and standard error (S.E.) of all estimators based on \(100\) simulations.

• Adaptive weighting v.s. DR. Figure 5 uses DR as a baseline and shows its comparison with adaptive weighting and DM on various datasets. Each subplot corresponds to an estimation method, wherein each point denotes a dataset, and its \((x,y)\) coordinates are bias and standard error normalized by RMSE of DR estimate on the same dataset. It can be seen that all adaptive weighting schemes reduce RMSE as compared to DR in most datasets. In many, RMSE is reduced by half. We also note that across various datasets, standard error accounts for most of the RMSE with adaptive weighting and DR estimates, while bias is the main factor for DM.

• Non-contextual v.s. contextual. Figure 6 (a) proceeds to investigate within adaptive weighting, how contextual weighting performs as compared to its non-contextual counterpart. In the left panel, each point denotes a dataset, and its \((x,y)\) coordinates are bias and standard error of contextual MinVar normalized by RMSE of non-contextual MinVar on the same dataset. The same visualization approach is applied to contextual and non-contextual StableVar in the right panel. We see a clear improvement in RMSE of contextual weighting over the non-contextual.

• MinVar v.s. StableVar. We compare the two adaptive weighting choices MinVar and StableVar in Figure 6 (b). As before, each point corresponds to a dataset. The \((x,y)\) coordinates are bias and standard error of MinVar normalized by its StableVar counterpart in forms of both non-contextual weighting (left panel) and contextual weighting (right panel). We can see that MinVar typically reduces RMSE relative to StableVar.

7 Discussion↩︎

Off-policy evaluation on adaptive data can be challenging, as observations are dependent and overlap between the target policy and data-collection policy often deteriorates over the course of data collection. Many estimators suffer from bias or high variance. In this paper, we propose a set of heuristics that address the issue by modifying the DR estimator through averaging doubly robust scores using adaptive, non-uniform weights. When chosen appropriately, these weights are able to reduce variance, at the cost of a small finite-sample bias. We prove that our estimators have consistency and asymptotic normality under certain conditions. Empirically, our estimators outperform existing alternatives with lower RMSE and expected coverage.

A number of important research directions remain. For example, it would be of interest to know if some of our more stringent sufficient conditions for asymptotic normality can be weakened, allowing for inference based on approximate normality in more general settings. Another interesting avenue of research would be to consider whether adaptive weights as presented here could be beneficial for learning optimal policies using logged data from bandit algorithms.

Acknowledgements↩︎

The authors would like to thank Stefan Wager, Sanath Kumar Krishnamurthy, and Kristine Koutout for helpful discussions. The authors are also grateful for the generous support provided by Golub Capital Social Impact Lab. S.A. acknowledges support from the Office of Naval Research grant N00014-19-1-2468 and Schmidt Futures. R.Z. acknowledges support from the Total Graduate Fellowship and PayPal Graduate Fellowship. D.A.H. acknowledges support from the Stanford Institute for Human-Centered Artificial Intelligence.

8 Additional proofs↩︎

With some abuse of notation, starting from this section, we will write \[\label{eq:dr95single} \widehat{\Gamma}_t(X_t, w) := \widehat{\mu}_t(X_t, w) + \frac{\mathop{\mathrm{\mathbb{I}}}\{W_t=w\}}{e_t(X_t,w)}(Y_t-\widehat{\mu}_t(X_t, w)),\tag{9}\] so that \(\widehat{\Gamma}_t(X_t, \pi) \equiv \sum_{w} \pi(X_t, w)\widehat{\Gamma}_t(X_t, w)\).

8.1 Proof of Proposition 1↩︎

Recall that \(\widehat{\mu}(X_t, w)\) and \(e_t(X_t, w)\) are functions of past data \(H_{t-1}\) and the current context \(X_t\). Therefore, the rightmost term of 9 has conditional expectation \[\begin{align} & \mathop{\mathrm{\mathbb{E}}}\Big[ \frac{\mathop{\mathrm{\mathbb{I}}}\{W_t=w\}}{e_t(X_t,w)}(Y_t-\widehat{\mu}_t(X_t, w)) \Big|H_{t-1}, X_t\Big] \\ \stackrel{(i)}{=}~& \mathop{\mathrm{\mathbb{E}}}\Big[ \frac{(Y_t(w)-\widehat{\mu}_t(X_t, w))}{e_t(X_t,w)} \Big|H_{t-1}, X_t, W_{t}=w \Big]e_t(X_t,w) \\ =~ &\mathop{\mathrm{\mathbb{E}}}\big[Y_t(w)|H_{t-1}, X_t, W_{t}=w\big] -\widehat{\mu}_t(X_t, w) \\ \stackrel{(ii)}{=}~ &\mathbb{E}_{}\left[\left.{Y_t(w)}\right|{X_t}\right] -\widehat{\mu}_t(X_t, w) \\ =~&\mu(X_t, w) -\widehat{\mu}_t(X_t, w), \end{align}\]

where in (i) we used the definition of \(e_t(X_t, w)\) and in (ii) we used Assumption 1 to drop the conditioning on \(H_{t-1}\) and \(W_t\). This implies that \[\begin{align} \mathop{\mathrm{\mathbb{E}}}\big[\widehat{\Gamma}_t(X_t, \pi)\big|H_{t-1}, X_t\big] = \sum_{w} \pi(X_t, w) \mathop{\mathrm{\mathbb{E}}}\big[\widehat{\Gamma}_t(X_t, w) \big|H_{t-1}, X_t\big] = \sum_{w} \pi(X_t, w)\mu(X_t, w). \end{align}\] Take expectation with respect to context, we have \[\mathop{\mathrm{\mathbb{E}}}\big[\widehat{\Gamma}_t(X_t, \pi)\big|H_{t-1}\big] = \mathop{\mathrm{\mathbb{E}}}\big[\sum_{w} \pi(X_t, w)\mu(X_t, w)\big] = Q(\pi).\]

8.2 Proof of Proposition 2↩︎

We first prove the lower bound of the conditional variances in ?? . Expanding the definition of \(\widehat{\Gamma}_t\) from 2 and substituting 9 , we have that

\[\label{eq:cond95var95expand} \begin{align} \mathrm{Var}_{}\left({\widehat{\Gamma}_t(X_t, \pi)|H_{t-1}, X_t}\right)=& \sum_{w}\pi^2(X_t, w)\mathrm{Var}_{}\left({\widehat{\Gamma}_t(X_t, w) |H_{t-1}, X_t}\right)\\ & + \sum_{w_1\neq w_2} \pi(X_t, w_1)\pi(X_t, w_2)\mathrm{Cov}\left({\widehat{\Gamma}_t(w_1) }, {\widehat{\Gamma}_t(w_2) |H_{t-1}, X_t}\right) \end{align}\tag{10}\]

Let us analyze these sums. A routine calculation reveals that the conditional variances decompose as \[\label{eq:var95decomp} \begin{align} \mathrm{Var}_{}\left({\widehat{\Gamma}_t(X_t, w) |H_{t-1}, X_t}\right) = & \frac{\mathrm{Var}_{}\left({Y_t(w) | X_t}\right)}{e_t(X_t, w)} + \Big(\frac{1}{e_t(X_t, w)} - 1\Big) \left(\widehat{\mu}_t(X_t, w) - \mu(X_t, w) \right)^2, \end{align}\tag{11}\] while the conditional covariances reduce to \[\label{eq:covar95decomp} \begin{align} &\mathrm{Cov}\left({\widehat{\Gamma}_t(w_1) }, {\widehat{\Gamma}_t(w_2) |H_{t-1}, X_t}\right)=\widehat{\mu}_t(X_t, w_1){\mu}_t(X_t, w_2) + {\mu}_t(X_t, w_1)\widehat{\mu}_t(X_t, w_2) - {\mu}_t(X_t, w_1){\mu}_t(X_t, w_2). \end{align}\tag{12}\]

Substituting 11 and 12 in 10 , \[\label{eq:var95decomp95a} \begin{align} \mathrm{Var}_{}\left({\widehat{\Gamma}_t(X_t, \pi)|H_{t-1}, X_t}\right) = \sum_w\frac{\pi^2(X_t, w)\mathrm{Var}_{}\left({Y_t(w)|X_t}\right)}{e_t(X_t, w)} + A, \end{align}\tag{13}\]

where \(A\) collects all the terms involving \(\widehat{\mu}\) and \(\mu\), and after some algebra can be shown to be \[\begin{align} A := \sum_w\frac{\pi^2(X_t, w)(\hat{\mu}_t(X_t, w)-\mu(X_t, w))^2}{e_t(X_t, w)} - \Big(\sum_w \pi(X_t, w)\big(\hat{\mu}_t(X_t, w)-\mu(X_t, w)\big)\Big)^2. \end{align}\] Note that \(A \geq 0\), since by the Cauchy-Schwartz inequality and recalling that \(\sum_{w}e_t(X_t, w)=1\), \[\begin{align} & \Big(\sum_w\frac{\pi^2(X_t, w)(\hat{\mu}_t(X_t, w)-\mu(X_t, w))^2}{e_t(X_t, w)}\Big)\times \Big(\sum_{w}e_t(X_t, w)\Big) \geq \Big(\sum_w \pi(X_t, w)\left({\hat{\mu}_t(X_t, w)-\mu(X_t, w)}\right)\Big)^2. \end{align}\]

Thus from 13 and the fact that \(A \geq 0\), we have \[\begin{align} \mathrm{Var}_{}\left({\widehat{\Gamma}_t(X_t, \pi)|H_{t-1}, X_t}\right)&\geq \sum_w\frac{\pi^2(X_t, w)\mathrm{Var}_{}\left({Y_t(w)|X_t}\right)}{e_t(X_t, w)}\geq C_0\sum_w\frac{\pi^2(X_t, w)}{e_t(X_t, w)}, \end{align}\] wherein the last inequality is due to the assumption that \(\mathrm{Var}_{}\left({Y_t(w)|X_t}\right)\) is uniformly bounded below by \(C_0 > 0\).

To prove the upper bound on conditional variances in ?? , \[\begin{align} \mathrm{Var}_{}\left({\widehat{\Gamma}_t(X_t, \pi)|H_{t-1}, X_t}\right) \leq & \sum_w\frac{\pi^2(X_t, w)\mathrm{Var}_{}\left({Y_t(w)|X_t}\right)}{e_t(X_t, w)} + \sum_w\frac{\pi^2(X_t, w)(\hat{\mu}_t(X_t, w)-\mu(X_t, w))^2}{e_t(X_t, w)}\\ \leq & \sum_w\frac{C_1\pi^2(X_t, w)}{e_t(X_t, w)} + \sum_w\frac{4C_2^2\pi^2(X_t, w)}{e_t(X_t, w)}, \end{align}\] where for the last inequality, we use the assumption that \(\mathrm{Var}_{}\left({Y_t(w)|X_t}\right)\) is uniformly bounded above by some constant \(C_1\) and that \(\widehat{\mu}_t, \mu\) are uniformly bounded above by \(C_2\). This justifies the result ?? .

9 Auxiliary theorems↩︎

Our proof is established on martingale central limit theorems. Particularly, we invoke the following result multiple times throughout the proof.

The following proposition is also useful in our proof.

A similar proposition will also be used.

where \(\max_{1\leq t\leq T} |a_{T,t}|\) vanishes as \(T\rightarrow\infty\), and \(\sum_{t=1}^T a_{T,t}\) bounded, we thus have \(\bigg|\sum_{t=1}^T a_{T,t}x_t\bigg| = O(\epsilon)\) for large \(T\), concluding the proof.

10 Limit theorems of non-contextual weighting↩︎

In this section, we establish Theorem 1. At a high level, Theorem 1 is an extension of limiting theorems for adaptive weighting in multi-armed bandits from [18]. Note that the non-contextual adaptive weight \(h_t\) proposed in 5 is independent of the realized context \(X_t\); when proving its asymptotics, we can view context as exogenous randomness and follow a similar martingale analysis framework as that in [18].

Recall that our goal is to evaluate a policy \(\pi\), whose policy value is \(Q(\pi)=\mathop{\mathrm{\mathbb{E}}}[\sum_{w}\mu(x,w)]\). Our policy value estimate and the associated variance estimate are \[\begin{align} \widehat{Q}_T^{NC}(\pi) = \frac{\sum_{t=1}^T h_t \widehat{\Gamma}_t(X_t, \pi) }{\sum_{t=1}^T h_t}\quad and\quad \widehat{V}_T^{NC}(\pi) = \frac{\sum_{t=1}^T h_t^2 (\widehat{\Gamma}_t(X_t, \pi) - \widehat{Q}_T^{NC}(\pi) )^2 }{(\sum_{t=1}^T h_t)^2}, \end{align}\] with StableVar weights \(h_t = \sqrt{1 / \mathop{\mathrm{\mathbb{E}}}[\sum_{w}\pi^2(X_t, w)/e_t(X_t, w)|H_{t-1}]}\).

To start, we define an auxiliary martingale difference sequence (MDS) \(\{\xi_{T,t}\}_{t=1}^T\) for estimator \(\widehat{Q}^{NC}_T\), \[\label{eq:def95xi} \xi_{T, t} = \frac{h_t\big(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi)\big)}{\sqrt{\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\big[h_t^2\big(\widehat{\Gamma}_t(X_t, \pi) -Q(\pi)\big)^2 \big]} },\tag{14}\] which martingale difference property is justified since \(\mathop{\mathrm{\mathbb{E}}}[\xi_{T,t}|H_{t-1}]=0\) by Proposition 1, which immediately yields \(\mathop{\mathrm{\mathbb{E}}}[(\sum_{t=1}^T\xi_{T,t})^2] = 1\): \[\begin{align} \mathop{\mathrm{\mathbb{E}}}[(\sum_{t=1}^T\xi_{T,t})^2] = \mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T\xi^2_{T,t}] = \frac{\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\big[h_t^2\big(\widehat{\Gamma}_t(X_t, \pi) -Q(\pi)\big)^2 \big] }{ \sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\big[h_t^2\big(\widehat{\Gamma}_t(X_t, \pi) -Q(\pi)\big)^2 \big] } = 1. \end{align} \label{eq:xi952}\tag{15}\] We proceed to show the following steps in details.

• Step I: consistency of \(\widehat{Q}^{NC}_T(\pi)\), that is, \(\widehat{Q}^{NC}_T(\pi) \xrightarrow{p} Q(\pi)\).

• Step II: CLT of MDS \(\{\xi_{T,t}\}_{t=1}^T\), that is, \(\sum_{t=1}^T \xi_{T,t}\xrightarrow{d}\mathop{\mathrm{\mathcal{N}}}(0,1)\).

• Step III: CLT of \(\widehat{Q}^{NC}_T(\pi)\), that is, \(\big(\widehat{Q}^{NC}_T(\pi) - Q(\pi)\big) / \big(\widehat{V}_T^{NC}(\pi) \big)^{1/2}\xrightarrow{d}\mathop{\mathrm{\mathcal{N}}}(0, 1)\).

10.1 Consistency of \(\widehat{Q}^{NC}_T\)↩︎

We now show that \(\widehat{Q}^{NC}_T(\pi)\) converges to true policy value \(Q(\pi)\). We have \[\begin{align} \big|\widehat{Q}^{NC}_T(\pi) - Q(\pi)\big| & = \Big|\frac{\sum_{t=1}^T h_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))}{\sum_{t=1}^T h_t}\Big|\\ & = \Big|\frac{\sum_{t=1}^T h_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))}{\sqrt{\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\big[h_t^2\big(\widehat{\Gamma}_t(X_t, \pi) -Q(\pi)\big)^2}\big]}\Big|\cdot \frac{\sqrt{\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\big[h_t^2\big(\widehat{\Gamma}_t(X_t, \pi) -Q(\pi)\big)^2}\big]}{\sum_{t=1}^T h_t}\\ & = \Big|\sum_{t=1}^T \xi_{T,t}\Big|\cdot \frac{\sqrt{\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\big[h_t^2\big(\widehat{\Gamma}_t(X_t, \pi) -Q(\pi)\big)^2}\big]}{\sum_{t=1}^T h_t}\\ & = \Big|\sum_{t=1}^T \xi_{T,t}\Big|\cdot \frac{\sqrt{\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\big[h_t^2\mathop{\mathrm{\mathbb{E}}}\big[\big(\widehat{\Gamma}_t(X_t, \pi) -Q(\pi)\big)^2|H_{t-1}\big]\big]}}{\sum_{t=1}^T h_t}\\ &\stackrel{(i)}{\leq}\Big|\sum_{t=1}^T \xi_{T,t}\Big|\cdot \frac{\sqrt{\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\big[(\mathop{\mathrm{\mathbb{E}}}[\sum_w \pi(X_t, w)/e_t(X_t, w)|H_{t-1}])^{-1}\cdot U \mathop{\mathrm{\mathbb{E}}}[\sum_w \pi(X_t, w)/e_t(X_t, w)|H_{t-1}]\big]}}{\sum_{t=1}^T (\mathop{\mathrm{\mathbb{E}}}[\sum_w \pi(X_t, w)/e_t(X_t, w) |H_{t-1}])^{-1/2}}\\ &=\Big|\sum_{t=1}^T \xi_{T,t}\Big|\cdot \frac{\sqrt{\sum_{t=1}^T U}}{\sum_{t=1}^T (\mathop{\mathrm{\mathbb{E}}}[\sum_w \pi(X_t, w)/e_t(X_t, w)|H_{t-1}])^{-1/2}}\\ &\stackrel{(ii)}{\lesssim} \Big|\sum_{t=1}^T \xi_{T,t}\Big| \cdot \frac{\sqrt{T}}{\sum_{t=1}^T t^{-\alpha/2} } =\Big|\sum_{t=1}^T \xi_{T,t}\Big|\cdot O(T^{(\alpha-1)/2}), \end{align}\] where in (i), we use 3 and the definition of StableVar weights; in (ii), we use Assumption 2b that \(e_t\geq C t^{-\alpha}\). Therefore, for any \(\epsilon>0\), \[\begin{align} \mathop{\mathrm{\mathbb{P}}}\big(\big|\widehat{Q}^{NC}_T(\pi) - Q(\pi)\big| >\epsilon \big) &\leq \epsilon^{-2} \mathop{\mathrm{\mathbb{E}}}\big[ \big|\widehat{Q}^{NC}_T(\pi) - Q(\pi)\big|^2 \big] \\ & \leq \epsilon^{-2} \mathop{\mathrm{\mathbb{E}}}\big[ \big(\sum_{t=1}^T \xi_{T,t}\big)^2 \big]O(T^{\alpha-1}) = \epsilon^{-2}O(T^{\alpha-1})\rightarrow 0, \end{align}\] where we use the fact that \(\mathop{\mathrm{\mathbb{E}}}\big[ \big(\sum_{t=1}^T \xi_{T,t}\big)^2 \big]=\mathop{\mathrm{\mathbb{E}}}\big[\sum_{t=1}^T \xi_{T,t}^2 \big]=1\) by 15 .

10.2 CLT of martingale difference sequence \(\{\xi_{T,t}\}_{t=1}^T\)↩︎

We show the convergence of \(\sum_{t=1}^T\xi_{T,t}\) by verifying two martingale CLT conditions stated in Proposition 3.

10.2.1 Variance convergence.↩︎

We want to show that the following ratio converges in probability to 1. \[\begin{align} \label{eq:xi2} \sum_{t=1}^T\mathbb{E}_{}\left[\left.{\xi^2_{T,t}}\right|{H_{t-1}}\right] = \frac{\sum_{t=1}^T h_t^2 \mathop{\mathrm{\mathbb{E}}}\big[\big(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi)\big)^2| H_{t-1}\big] }{\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\big[h_t^2\big(\widehat{\Gamma}_t(X_t, \pi) -Q(\pi)\big)^2\big]}. \end{align}\tag{16}\]

We will later show that 16 can be rewritten as \(Z_T/\mathop{\mathrm{\mathbb{E}}}[Z_T]\), where \[\label{eq:zt95num} Z_T = \sum_{t=1}^{T} \mathbb{E}\Big[h_t^2 \sum_w \frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t, w)} | H_{t-1}\Big] + C_2\sum_{t=1}^{T} h_t^2 + o_p\left( \sum_{t=1}^{T} \mathbb{E}\Big[h_t^2\Big\{ \sum_w \frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t, w)} + C_2\Big\} | H_{t-1}\Big] \right),\tag{17}\] and \[\label{eq:zt95denom} \mathbb{E}[Z_T] = \sum_{t=1}^{T} \mathbb{E}\Big[h_t^2 \sum_w \frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t, w)} \Big] + C_2\sum_{t=1}^{T} \mathbb{E}[h_t^2] + o\left( \sum_{t=1}^{T} \mathbb{E}\Big[h_t^2 \Big\{\sum_w \frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t, w)}+ C_2\Big\}\Big] \right).\tag{18}\] Above, \(C_1\) is a function of \(X_t\) and \(w\) but not the history, bounded above and away from zero; \(C_2\) is a finite constant. This characterization implies that that 16 is asymptotically equivalent to the following ratio of dominant terms in 17 and 18 , which we denote as \[\label{eq:xi295target} \frac{A_T}{\mathbb{E}A_T} := \frac{ \sum_{t=1}^{T} \mathbb{E}\Big[h_t^2 \sum_w C_1(X_t, w)\frac{\pi^2(X_t, w)}{e_t(X_t, w)} | H_{t-1}\Big] + C_2\sum_{t=1}^{T} h_t^2 }{ \sum_{t=1}^{T} \mathbb{E}\Big[h_t^2 \sum_w C_1(X_t, w)\frac{\pi^2(X_t, w)}{e_t(X_t, w)} \Big] + C_2\sum_{t=1}^{T} \mathbb{E}[h_t^2]}.\tag{19}\]

For now, let’s assume that we have characterized 16 as \(Z_T/\mathbb{E}Z_T\) and show that 19 converges in probability to one. We will show that both the numerator and the denominator of 19 are equivalent to \(M_T\) asymptotically, where \[\label{eq:M} M_T := \sum_{t=1}^T \mathbb{E}\Big[\sum_w \frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t, w)}\Big]\Big/\mathop{\mathrm{\mathbb{E}}}\Big[\sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}\Big] + \sum_{t=1}^TC_2\Big/\mathop{\mathrm{\mathbb{E}}}\Big[\sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}\Big].\tag{20}\]

It will be useful to note that the sequence \(M_T\) is \(\Omega(T)\). This is shown later in 31 .

Let’s begin by showing that \(A_T/M_T \to 1\) almost surely as \(T \to \infty\) or, equivalently, that \(A_T/M_T - 1 \to 0\) almost surely. This ratio decomposes as follows, \[\begin{align} \label{eq:xi95hCe295p} \frac{A_T}{M_T} - 1 = & \frac{\sum_{t=1}^{T} \mathbb{E}\Big[h_t^2 \sum_w\frac{ C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t, w)} | H_{t-1}\Big] + C_2\sum_{t=1}^{T} h_t^2 }{M_T} - 1 = \frac{ \sum_{t=1}^{T}a_t m_t +C_2 b_t n_t }{M_T}\\ where\quad & a_t := \frac{ \mathbb{E}\Big[h_t^2 \sum_w\frac{ C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t, w)} | H_{t-1}\Big]}{\mathbb{E}[\sum_w \frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t, w)}]\big/\mathop{\mathrm{\mathbb{E}}}[\sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}]} - 1, \quad b_t := \frac{ h_t^2}{\mathop{\mathrm{\mathbb{E}}}[\sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}]^{-1}} -1\nonumber\\ & m_t := \mathbb{E}[\sum_w \frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t, w)}]\big/\mathop{\mathrm{\mathbb{E}}}[\sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}], \quad n_t :=\mathop{\mathrm{\mathbb{E}}}[\sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}]^{-1}.\nonumber \end{align}\tag{21}\] Below, we will show that \(a_t\xrightarrow{a.s.}0\) and \(b_t\xrightarrow{a.s.}0\). Consequently, for any \(\epsilon>0\), there exists \(T_0\) such that \(|a_t|<\epsilon\) and \(|b_t|<\epsilon\) for \(t \ge T_0\) on an event of probability one. We work on this event. Note that \(m_t\) is bounded because \(C_1\) is bounded; \(n_t \in (0,1]\) because \(e_t \le 1\) and \(\sum_w \pi(x,w)^2 \le \sum_w \pi(x,w) = 1\) for all \(x\); and below, in 31 , we show that \(M_T=\Omega(T)\). It follows that \(\sum_{t=T_0}^T a_tm_t+C_2 b_tn_t\le \epsilon \sum_{t=T_0}^T (m_t + C_2 n_t) \le \epsilon M_T\). Furthermore, because \(a_t\) and \(b_t\) are convergent, they are bounded, and it follows that \(\sum_{t=1}^{T_0} a_tm_t+C_2 b_tn_t\) is bounded and therefore less than \(\epsilon M_T = \Omega(T)\) for large \(T\). We have decomposed the numerator of the right side of 21 into two terms, and shown both are arbitrarily small relative to the denominator; it follows that \(A_T / M_T-1\) converges to \(0\) on the aforementioned event, i.e., almost surely.

Because the ratio \(A_T / M_T\) is bounded, \(\mathop{\mathrm{\mathbb{E}}}[A_T/M_T]\) also converges to one as consequence of the above and dominated convergence. To see that it is bounded, recall that \(M_T=\Omega(T)\) and observe that \(A_T=O(T)\), as each summand in \(A_T\) is \(O(1)\). In particular, the summands satisfy \[\begin{align} &h_t^2\{\mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{ C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t, w)} | H_{t-1}] + C_2\} \\ \leq& h_t^2 (\sup_{x,w}|C_1(x,w)|+|C_2|)\mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{ \pi^2(X_t, w)}{e_t(X_t, w)} | H_{t-1}]\\ =&(\sup_{x,w}|C_1(x,w)|+|C_2|) < \infty, \end{align}\] as \(h_t^2\) is the inverse of the conditional expectation in the second line above.

Note that \(M_T\) is not random, so this implies that \(\mathbb{E}[A_T] / M_T \to 1\). Thus, as \(A_T/M_T \xrightarrow{a.s.} 1\), it follows that \(A_T / E A_T = (A_T / M_T) / (\mathbb{E}[A_T] / M_T) \xrightarrow{a.s.} 1\).

Next, let’s show that \(b_t\) defined in 21 converges to \(0\) almost surely. We’ll show that the equivalent is true: \[\label{eq:eX95converged} \begin{align} &\bigg| \frac{\mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{\pi^2(X_t, w)}{e_t(X_t,w)} |H_{t-1}\big]}{\mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{\pi^2(X_t, w)}{e_t(X_t,w)}\big]} - 1 \bigg| \\ \stackrel{(i)}{=}& \bigg| \frac{\int_{x}\sum_w\frac{\pi^2(x, w)}{e_t(x,w)} d\mathop{\mathrm{\mathbb{P}}}_{x}}{\mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{\pi^2(X_t, w)}{e_t(X_t,w)}\big]} - 1 \bigg| \\ \stackrel{(ii)}{=}& \bigg| \frac{\int_{x}\sum_w\frac{\pi^2(x, w)}{e_t(x,w)} - \mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{\pi^2(x, w)}{e_t(x,w)} ] d\mathop{\mathrm{\mathbb{P}}}_{x}}{\mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{\pi^2(X_t, w)}{e_t(X_t,w)}\big]} \bigg| \\ \leq& \frac{\int_{x}|\sum_w\frac{\pi^2(x, w)}{e_t(x,w)} - \mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{\pi^2(x, w)}{e_t(x,w)} ]| d\mathop{\mathrm{\mathbb{P}}}_{x}}{\mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{\pi^2(X_t, w)}{e_t(X_t,w)}\big]} = \frac{ \int_{x} \Big|\frac{\sum_w\frac{\pi^2(x, w)}{e_t(x,w)}}{\mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{\pi^2(x, w)}{e_t(x,w)}]} -1 \Big|\mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{\pi^2(x, w)}{e_t(x,w)}]d\mathop{\mathrm{\mathbb{P}}}_{x} }{ \mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{\pi^2(X_t, w)}{e_t(X_t,w)}\big] }\\ \leq & \frac{\sup_{x}\Big|\frac{\sum_w\frac{\pi^2(x, w)}{e_t(x,w)}}{\mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{\pi^2(x, w)}{e_t(x,w)}]} -1 \Big| \int_{x} \mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{\pi^2(x, w)}{e_t(x,w)}]d\mathop{\mathrm{\mathbb{P}}}_{x} }{ \mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{\pi^2(X_t, w)}{e_t(X_t,w)}\big] } \\ = & \frac{\sup_{x}\Big|\frac{\sum_w\frac{\pi^2(x, w)}{e_t(x,w)}}{\mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{\pi^2(x, w)}{e_t(x,w)}]} -1 \Big| \cdot \mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{\pi^2(X_t, w)}{e_t(X_t,w)}\big] }{ \mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{\pi^2(X_t, w)}{e_t(X_t,w)}\big] } \\ = & \sup_{x}\Big|\frac{\sum_w\frac{\pi^2(x, w)}{e_t(x,w)}}{\mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{\pi^2(x, w)}{e_t(x,w)}]} -1\Big|\\ \stackrel{(iii)}{\leq} & \sup_x \bigg|\sum_w \frac{\frac{\pi^2(x, w)}{e_t(x,w)} }{\mathop{\mathrm{\mathbb{E}}}[\frac{\pi^2(x, w)}{e_t(x,w)}]}-1\bigg| \leq \sup_x \sum_w \bigg|\frac{\frac{\pi^2(x, w)}{e_t(x,w)} }{\mathop{\mathrm{\mathbb{E}}}[\frac{\pi^2(x, w)}{e_t(x,w)}]}-1\bigg|\\ \stackrel{(iv)}{=}& \sup_{x}\sum_w \bigg|\frac{e_t^{-1}(x,w) }{\mathop{\mathrm{\mathbb{E}}}[e_t^{-1}(x,w)]}-1\bigg|\leq K \sup_{x,w} \bigg|\frac{e_t^{-1}(x,w) }{\mathop{\mathrm{\mathbb{E}}}[e_t^{-1}(x,w)]}-1\bigg|\xrightarrow{a.s.}0 , \end{align}\tag{22}\] where in (i), we rewrite \(\mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{\pi^2(X_t, w)}{e_t(X_t,w)} |H_{t-1}]\) as \(\int_{x}\sum_w\frac{\pi^2(x, w)}{e_t(x,w)} d\mathop{\mathrm{\mathbb{P}}}_{x}\) since \(\mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{\pi^2(X_t, w)}{e_t(X_t,w)} |H_{t-1}]\) is an expectation over \(X_t=x\) conditioning on history \(H_{t-1}\); in (ii), we rewrite \(\mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{\pi^2(X_t, w)}{e_t(X_t,w)}]\) as \(\int_{x}\mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{\pi^2(x, w)}{e_t(x,w)} ] d\mathop{\mathrm{\mathbb{P}}}_{x}\), since \(\mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{\pi^2(X_t, w)}{e_t(X_t,w)}]\) is an expectation over \((X_t, H_{t-1})\), and here, we use law of iterated expectations to integrate out \(H_{t-1}\) first; in (iii), we substitute a smaller denominator for each term in the numerator then use the triangle inequality; (iv), the equation is true since we can pull the \(\pi^2(x,w)\) out of the expectation with fixed \((x,w)\). This concludes that \(b_t\xrightarrow{a.s.}0\).

Next we are proving \(a_t\xrightarrow{a.s.}0\). Note that \((a_t+1) = (b_t+1) \cdot \frac{\mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t,w)} |H_{t-1}\big]}{\mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t,w)}\big]}\). We already have \(b_t\xrightarrow{a.s.}0\), to show \(a_t\xrightarrow{a.s.}0\), we only need to show that the latter factor converges to one. We use an argument similar to the one above. \[\label{eq:xi95hCe2} \begin{align} &\bigg| \frac{\mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t,w)} |H_{t-1}\big]}{\mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t,w)}\big]} - 1 \bigg| \\ &= \bigg| \frac{\int_{x}\sum_w\frac{C_1(x, w)\pi^2(x, w)}{e_t(x,w)} d\mathop{\mathrm{\mathbb{P}}}_{x}}{\mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t,w)}\big]} - 1 \bigg|\\ &= \bigg| \frac{\int_{x}\sum_w\frac{C_1(x, w)\pi^2(x, w)}{e_t(x,w)} - \mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{C_1(x, w)\pi^2(x, w)}{e_t(x,w)}] d\mathop{\mathrm{\mathbb{P}}}_{x} }{\mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t,w)}\big]} \bigg|\\ &\leq \frac{\int_{x}\Big|\frac{\sum_w\frac{C_1(x, w)\pi^2(x, w)}{e_t(x,w)}}{ \mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{C_1(x, w)\pi^2(x, w)}{e_t(x,w)}]}-1\Big|\mathop{\mathrm{\mathbb{E}}}[\sum_w\frac{C_1(x, w)\pi^2(x, w)}{e_t(x,w)}] d\mathop{\mathrm{\mathbb{P}}}_{x} }{\mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t,w)}\big]} \\ &\leq \frac{\sup_{x}\Big|\frac{\sum_w\frac{C_1(x, w)\pi^2(x, w)}{e_t(x,w)}}{\mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{C_1(x, w)\pi^2(x, w)}{e_t(x,w)}\big]} -1 \Big| \int_{x}\mathop{\mathrm{\mathbb{E}}}[ \sum_w\frac{C_1(x, w)\pi^2(x, w)}{e_t(x,w)}]d\mathop{\mathrm{\mathbb{P}}}_{x} }{ \mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t,w)}\big] }\\ & = \sup_{x}\Big|\frac{\sum_w\frac{C_1(x, w)\pi^2(x, w)}{e_t(x,w)}}{\mathop{\mathrm{\mathbb{E}}}\big[\sum_w\frac{C_1(x, w)\pi^2(x, w)}{e_t(x,w)}\big]} -1 \Big|\\ &\leq \sup_x \bigg|\sum_w\frac{\frac{C_1(x,w)\pi^2(x, w)}{e_t(x,w)} }{\mathop{\mathrm{\mathbb{E}}}[\frac{C_1(x,w)\pi^2(x, w)}{e_t(x,w)}]}-1\bigg| \leq \sup_x \sum_w \bigg|\frac{\frac{C_1(x,w)\pi^2(x, w)}{e_t(x,w)} }{\mathop{\mathrm{\mathbb{E}}}[\frac{C_1(x,w)\pi^2(x, w)}{e_t(x,w)}]}-1\bigg|\\ & =\sup_{x}\sum_w \bigg|\frac{e_t^{-1}(x,w) }{\mathop{\mathrm{\mathbb{E}}}[e_t^{-1}(x,w)]}-1\bigg|\leq K \sup_{x,w} \bigg|\frac{e_t^{-1}(x,w) }{\mathop{\mathrm{\mathbb{E}}}[e_t^{-1}(x,w)]}-1\bigg|\xrightarrow{a.s.}0. \end{align}\tag{23}\]

This completes the proof that \(a_t\) converges to one almost surely.

Next we’ll show 16 can be rewritten as \(Z_T/\mathop{\mathrm{\mathbb{E}}}[Z_T]\). Let’s start by understanding the behavior the quantity in the numerator of 16 .

\[\label{eq:decompose95numerator95a} \begin{align} \mathop{\mathrm{\mathbb{E}}}[(\widehat{\Gamma}_t(X_t,\pi) - Q(\pi))^2|H_{t-1}, X_t] & = \mathop{\mathrm{\mathbb{E}}}[(\widehat{\Gamma}_t(X_t,\pi) - \sum_w \pi(X_t, w)\mu(X_t, w))^2|H_{t-1}, X_t] + (\sum_w \pi(X_t, w)\mu(X_t, w)-Q(\pi))^2. \end{align}\tag{24}\]

By derivation in Appendix 8.2 (see Equation 13 ) , we have \[\label{eq:decompose95numerator95b} \begin{align} &\mathop{\mathrm{\mathbb{E}}}[(\widehat{\Gamma}_t(X_t,\pi) - \sum_w \pi(X_t, w)\mu(X_t, w))^2|H_{t-1}, X_t] = \mathrm{Var}_{}\left({\widehat{\Gamma}_t(X_t, \pi)|H_{t-1}, X_t}\right) \\ &= \sum_w\frac{\pi^2(X_t, w)\mathrm{Var}_{}\left({Y_t(w)|X_t}\right)}{e_t(X_t, w)} + \sum_w\frac{\pi^2(X_t, w)(\hat{\mu}_t(X_t, w)-\mu(X_t, w))^2}{e_t(X_t, w)} - \Big(\sum_w \pi(X_t, w)\big(\hat{\mu}_t(X_t, w)-\mu(X_t, w)\big)\Big)^2. \end{align}\tag{25}\]

Combing 24 and 25 , we have \[\label{eq:decompose95numerator} \begin{align} &\mathop{\mathrm{\mathbb{E}}}[(\widehat{\Gamma}_t(X_t,\pi) - Q(\pi))^2|H_{t-1}] = \mathop{\mathrm{\mathbb{E}}}[\mathop{\mathrm{\mathbb{E}}}[(\widehat{\Gamma}_t(X_t,\pi) - Q(\pi))^2|X_t, H_{t-1}] |H_{t-1}]\\ = &\mathop{\mathrm{\mathbb{E}}}\Big[ \sum_w\frac{\pi^2(X_t, w)[\mathrm{Var}_{}\left({Y_t(w)|X_t}\right) + (\hat{\mu}_t(X_t, w)-\mu(X_t, w))^2 ]}{e_t(X_t, w)} |H_{t-1} \Big]\\ &\quad - \mathop{\mathrm{\mathbb{E}}}\Big[\Big(\sum_w \pi(X_t, w)\big(\hat{\mu}_t(X_t, w)-\mu(X_t, w)\big)\Big)^2 |H_{t-1}\Big] +\mathop{\mathrm{\mathbb{E}}}[(\sum_w \pi(X_t, w)\mu(X_t, w)-Q(\pi))^2] \\ = & \mathop{\mathrm{\mathbb{E}}}\Big[ \sum_w C_1(X_t, w)\frac{\pi^2(X_t, w)}{e_t(X_t, w)} |H_{t-1} \Big] + C_2 + \mathop{\mathrm{\mathbb{E}}}[m_t(X_t)|H_{t-1}] \end{align}\tag{26}\] where \(C_1(X_t, w) = \mathrm{Var}_{}\left({Y_t(w)|X_t}\right) + (\mu_\infty(X_t, w)-\mu(X_t, w))^2\), \(C_2 =\mathop{\mathrm{\mathbb{E}}}[(\sum_w \pi(X_t, w)\mu(X_t, w)-Q(\pi))^2]- \mathop{\mathrm{\mathbb{E}}}[(\sum_w \pi(X_t, w)(\mu_\infty(X_t, w)-\mu(X_t, w)))^2 ]\). Note neither \(C_1\) or \(C_2\) depend on the history \(H_{t-1}\). The variable \(m_t\) collects the following terms: \[\label{eq:mt95def} \begin{align} m_t(X_t) =& \sum_{w}\frac{\pi^2(X_t, w)}{e_t(X_t, w)} (\hat{\mu}_t(X_t, w)-\mu_\infty(X_t, w))^2 -(\sum_w \pi(X_t, w)(\hat{\mu}_t(X_t, w)-\mu_\infty(X_t, w)))^2\\ &+ 2\sum_{w}\frac{\pi^2(X_t, w)}{e_t(X_t, w)}(\hat{\mu}_t(X_t, w)-\mu_\infty(X_t, w))(\mu_\infty(X_t, w)-\mu(X_t, w)) \\&-2(\sum_w \pi(X_t, w)(\hat{\mu}_t(X_t, w)-\mu_\infty(X_t, w)))(\sum_w \pi(X_t, w)(\mu_\infty(X_t, w)-\mu(X_t, w))). \end{align}\tag{27}\] Below in 32 we will prove that \(m_t\) is upper bounded as \[\label{eq:mt95upper} \begin{align} | m_t(X_t) | \lesssim & \sup_{x, w}|\hat{\mu}_t(x, w)-\mu_\infty(x, w)|\sum_{w}\frac{\pi^2(X_t, w)}{e_t(X_t, w)}. \end{align}\tag{28}\] For now, let’s take this as fact and show that \(Z_T\) and \(\mathbb{E}Z_T\) decompose as claimed in 17 and 18 .

To show that the negligible terms in 17 are indeed negligible, we consider the ratio between these terms and the dominant term in \(Z_T\), \[\label{eq:negligible95x} \begin{align} & \frac{\sum_{t=1}^{T} \mathbb{E}[h_t^2 m_t(X_t)| H_{t-1}]}{ \sum_{t=1}^{T} \mathbb{E}\Big[h_t^2 \Big\{\sum_w\frac{ C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t, w)}+C_2\Big\} | H_{t-1}\Big] } \\ \lesssim & \frac{\sum_{t=1}^{T} \sup_{x, w}|\hat{\mu}_t(x, w)-\mu_\infty(x, w)| \mathbb{E}[h_t^2 \sum_{w}\frac{\pi^2(X_t, w)}{e_t(X_t, w)} |H_{t-1}]}{ \sum_{t=1}^{T} \inf_{x,w}\mathop{\mathrm{Var}}(Y_t(w)|x)\mathbb{E}[h_t^2 \sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)} | H_{t-1}] } \\ = &\frac{\sum_{t=1}^{T} \sup_{x, w}|\hat{\mu}_t(x, w)-\mu_\infty(x, w)| }{ \inf_{x,w}\mathop{\mathrm{Var}}(Y_t(w)|x)T }\xrightarrow{a.s}0, \end{align}\tag{29}\] where in the first inequality we substituted \(m_t\) by its upper bound 28 in the numerator, and in the denominator we used a lower bound shown below in 30 . In the equality we used the definition of \(h_t\). The limit is due to the fact that \(\sup_{x,w} |\hat{\mu}_t(x,w) - \mu_{\infty}(x,w)|\) converges to zero almost surely, and therefore so does \((1/T) \sum_{t} \sup_{x,w} |\hat{\mu}_t(x,w) - \mu_{\infty}(x,w)|\).

Similarly, to show that the negligible terms in 18 are indeed negligible, we consider the following ratio, \[\begin{align} \frac{\sum_{t=1}^{T} \mathbb{E}[h_t^2 m_t(X_t)]}{ \sum_{t=1}^{T} \mathbb{E}\Big[h_t^2 \Big\{\sum_w \frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t, w)}+C_2\Big\} \Big] } &\lesssim \frac{\sum_{t=1}^{T} \mathop{\mathrm{\mathbb{E}}}\big[\sup_{x, w}|\hat{\mu}_t(x, w)-\mu_\infty(x, w)| h_t^2\mathbb{E}[ \sum_{w}\frac{\pi^2(X_t, w)}{e_t(X_t, w)} |H_{t-1} ]\big]}{ \sum_{t=1}^{T} \inf_{x,w}\mathop{\mathrm{Var}}(Y_t(w)|x)\mathbb{E}[h_t^2 \sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}] }\\ &=\frac{\sum_{t=1}^{T} \mathop{\mathrm{\mathbb{E}}}\big[\sup_{x, w}|\hat{\mu}_t(x, w)-\mu_\infty(x, w)| \big]}{ \inf_{x,w}\mathop{\mathrm{Var}}(Y_t(w)|x) T } \end{align}\] Since \(\hat{\mu}_t, \mu_\infty\) is bounded and \(\sup_{x, w}|\hat{\mu}_t(x, w)-\mu_\infty(x, w)|\xrightarrow{a.s}0\) by Assumption 2, we have \(\sup_{x, w}|\hat{\mu}_t(x, w)-\mu_\infty(x, w)|\xrightarrow{L_1}0\) and thus \(\mathop{\mathrm{\mathbb{E}}}[\sup_{x, w}|\hat{\mu}_t(x, w)-\mu_\infty(x, w)|]\rightarrow 0\); this yields \[\frac{\sum_{t=1}^{T} \mathbb{E}[h_t^2 m_t(X_t)]}{ \sum_{t=1}^{T} \mathbb{E}\Big[h_t^2 \sum_w C_1(X_t, w)\frac{\pi^2(X_t, w)}{e_t(X_t, w)} \Big] } \rightarrow 0.\]

Finally, to conclude the proof, let’s establish some auxiliary results used above. First, a lower bound on the dominant terms in \(Z_T\). By expanding the definition of \(C_1\) and \(C_2\) from the discussion following 26 , \[\label{eq:C1C2} \begin{align} \mathop{\mathrm{\mathbb{E}}}\Big[\sum_w \frac{C_1(X_t,w)\pi^2(X_t, w)}{e_t(X_t, w)}\Big] + C_2 &=\mathop{\mathrm{\mathbb{E}}}\Big[\sum_w \frac{[\mathrm{Var}_{}\left({Y_t(w)|X_t}\right)\pi^2(X_t, w)}{e_t(X_t, w)} \Big] \\ &+ \mathbb{E}\Big[(\mu_\infty(X_t, w)-\mu(X_t, w))^2 \frac{\pi^2(X_t, w)}{e_t(X_t, w)}\Big]\\ &+ \mathop{\mathrm{\mathbb{E}}}[(\sum_w \pi(X_t, w)\mu(X_t, w)-Q(\pi))^2] \\ &- \mathop{\mathrm{\mathbb{E}}}[(\sum_w \pi(X_t, w)(\mu_\infty(X_t, w)-\mu(X_t, w)))^2 ] \end{align}\tag{30}\]

The third term of this decomposition is non-negative. The second term is larger than the fourth in magnitude, since by Cauchy-Schwartz inequality, \[\begin{align} \mathbb{E}[(\sum_w \pi(X_t, w)(\mu_\infty(X_t, w)-\mu(X_t, w)))^2 ] &= \mathbb{E}[(\sum_w \frac{\sqrt{e_t(X_t, w)} \pi(X_t, w)}{\sqrt{e_t(X_t, w)}}(\mu_\infty(X_t, w)-\mu(X_t, w)))^2 ] \\ &\leq \mathbb{E}\left[\sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}(\mu_\infty(X_t, w) - \mu(X_t, w))^2 \left( \sum_w e_t(X_t, w) \right) \right] \\ &= \mathbb{E}\left[\sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}(\mu_\infty(X_t, w) - \mu(X_t, w))^2 \right]. \end{align}\]

This implies the last three terms sum to a non-negative number, and hence we have the following lower bound: \[\mathop{\mathrm{\mathbb{E}}}\Big[\sum_w \frac{C_1(X_t,w)\pi^2(X_t, w)}{e_t(X_t, w)}\Big] + C_2 \geq \mathop{\mathrm{\mathbb{E}}}\Big[\sum_w \frac{[\mathrm{Var}_{}\left({Y_t(w)|X_t}\right)\pi^2(X_t, w)}{e_t(X_t, w)} \Big] \gtrsim \inf_{x,w} \mathrm{Var}_{}\left({Y_t(w)|x}\right).\]

The result above implies that that the sequence \(M_T=\Omega(T)\) since \[\begin{align} \label{eq:M95lower} M_T &=\sum_{t=1}^T \mathbb{E}\Big[\sum_w \frac{C_1(X_t, w)\pi^2(X_t, w)}{e_t(X_t, w)} + C_2\Big]\Big/\mathop{\mathrm{\mathbb{E}}}\Big[\sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}\Big] \\ &\geq \sum_{t=1}^T \mathbb{E}\Big[\sum_w \frac{\mathop{\mathrm{Var}}(Y_t(w)|X_t)\pi^2(X_t, w)}{e_t(X_t, w)}\Big]\Big/\mathop{\mathrm{\mathbb{E}}}\Big[\sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}\Big]\\ &\geq \inf_{x,w}\mathop{\mathrm{Var}}(Y_t(w)|x) T. \end{align}\tag{31}\]

The upper bound on \(m_t\) referred to in 28 can be derived as follows, \[\label{eq:mt95upper95deriv} \begin{align} | m_t(X_t) | =& \bigg| \sum_{w}\frac{\pi^2(X_t, w)}{e_t(X_t, w)} (\hat{\mu}_t(X_t, w)-\mu_\infty(X_t, w))^2 -(\sum_w \pi(X_t, w)(\hat{\mu}_t(X_t, w)-\mu_\infty(X_t, w)))^2\\ &+ 2\sum_{w}\frac{\pi^2(X_t, w)}{e_t(X_t, w)}(\hat{\mu}_t(X_t, w)-\mu_\infty(X_t, w))(\mu_\infty(X_t, w)-\mu(X_t, w)) \\&-2(\sum_w \pi(X_t, w)(\hat{\mu}_t(X_t, w)-\mu_\infty(X_t, w)))(\sum_w \pi(X_t, w)(\mu_\infty(X_t, w)-\mu(X_t, w))) \bigg|\\ \leq & \bigg| \sum_{w}\frac{\pi^2(X_t, w)}{e_t(X_t, w)} (\hat{\mu}_t(X_t, w)-\mu_\infty(X_t, w))^2\bigg| + \bigg|(\sum_w \pi(X_t, w)(\hat{\mu}_t(X_t, w)-\mu_\infty(X_t, w)))^2\bigg|\\ &+2\bigg|\sum_{w}\frac{\pi^2(X_t, w)}{e_t(X_t, w)}(\hat{\mu}_t(X_t, w)-\mu_\infty(X_t, w))(\mu_\infty(X_t, w)-\mu(X_t, w)) \bigg| \\&+ 2\bigg|(\sum_w \pi(X_t, w)(\hat{\mu}_t(X_t, w)-\mu_\infty(X_t, w)))(\sum_w \pi(X_t, w)(\mu_\infty(X_t, w)-\mu(X_t, w))) \bigg|\\ \leq & 2\bigg| \sum_{w}\frac{\pi^2(X_t, w)}{e_t(X_t, w)} (\hat{\mu}_t(X_t, w)-\mu_\infty(X_t, w))^2\bigg|\\ &+2\sup_{x,w}|\mu_\infty(x,w)-\mu(x,w)|\cdot \sup_{x, w}|\hat{\mu}_t(x, w)-\mu_\infty(x, w)| \sum_{w}\frac{\pi^2(X_t, w)}{e_t(X_t, w)} \\&+ 2\sup_{x,w}|\mu_\infty(x,w)-\mu(x,w)|\cdot \sup_{x, w}|\hat{\mu}_t(x, w)-\mu_\infty(x, w)|\\ \leq &\sup_{x, w}|\hat{\mu}_t(x, w)-\mu_\infty(x, w)| \cdot \sum_{w}\frac{\pi^2(X_t, w)}{e_t(X_t, w)} \cdot \Big\{2+ 4 \sup_{x,w}|\mu_\infty(x,w)-\mu(x,w)|\Big\} \\ \lesssim & \sup_{x, w}|\hat{\mu}_t(x, w)-\mu_\infty(x, w)|\sum_{w}\frac{\pi^2(X_t, w)}{e_t(X_t, w)}. \end{align}\tag{32}\]

Remark . By Proposition 2, \(\sum_{t=1}^T \mathbb{E}_{}\left[\left.{\xi_{T,t}^2}\right|{H_{t-1}}\right]\leq \frac{U}{L}\), we thus have \(\sum_{t=1}^T \mathbb{E}_{}\left[\left.{\xi_{T,t}^2}\right|{H_{t-1}}\right]\xrightarrow{L^p}1\) for any \(p\geq 1\).

10.2.2 Moment decay.↩︎

Now consider the conditional fourth moment of \(\xi_{T,t}\), we have \[\begin{align} &\mathop{\mathrm{\mathbb{E}}}\big[\big(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi)\big)^4| H_{t-1}, X_t\big]\nonumber\\ = & \mathop{\mathrm{\mathbb{E}}}\big[\big(\widehat{\Gamma}_t(X_t, \pi) -\sum_w \pi(X_t, w)\mu(X_t, w)+ \sum_w \pi(X_t, w)\mu(X_t, w)- Q(\pi)\Big)^4|H_{t-1}, X_t\Big]\nonumber\\ = & \mathop{\mathrm{\mathbb{E}}}\big[\big(\widehat{\Gamma}_t(X_t, \pi) - \sum_w \pi(X_t, w)\mu(X_t, w)\big)^4|H_{t-1}, X_t\big]\tag{33} \\ & + 4\big(\sum_w \pi(X_t, w)\mu(X_t, w)- Q(\pi)\big)\mathop{\mathrm{\mathbb{E}}}\big[\big(\widehat{\Gamma}_t(X_t, \pi) - \sum_w \pi(X_t, w)\mu(X_t, w)\big)^3|H_{t-1}, X_t\big]\tag{34}\\ &+ 6\big(\sum_w \pi(X_t, w)\mu(X_t, w)- Q(\pi)\big)^2\mathop{\mathrm{\mathbb{E}}}\big[\big(\widehat{\Gamma}_t(X_t, \pi) - \sum_w \pi(X_t, w)\mu(X_t, w)\big)^2|H_{t-1}, X_t\big]\tag{35}\\ &+ 4\big(\sum_w \pi(X_t, w)\mu(X_t, w)- Q(\pi)\big)^3\mathop{\mathrm{\mathbb{E}}}\big[\big(\widehat{\Gamma}_t(X_t, \pi) - \sum_w \pi(X_t, w)\mu(X_t, w)\big)|H_{t-1}, X_t\big]\tag{36}\\ & + \big(\sum_w \pi(X_t, w)\mu(X_t, w)- Q(\pi)\big)^4\tag{37} \end{align}\] We analyze each term respectively.

(i) For term 33 , we have \[\begin{align} \eqref{eq:xi95fourth95i} =~ & \sum_w e_t(X_t, w)\Big(\frac{\pi(X_t, w)}{e_t(X_t, w)}(Y_t(w)-\hat{\mu}_t(X_t, w)) + \sum_{w'}\pi(X_t, w')(\hat{\mu}_t(X_t, w')-\mu(X_t, w')) \Big)^4 \\ \leq~ & c_1\Big(1 + \sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)} + \sum_w \frac{\pi^3(X_t, w)}{e_t^2(X_t, w)} + \sum_w \frac{\pi^4(X_t, w)}{e_t^3(X_t, w)}\Big), \end{align}\] for some constant \(c_1\).

(ii) Similarly, for term 34 , there exists a constant \(c_2\) such that \[\eqref{eq:xi95fourth95ii} \leq~ c_2\Big(1 +1 + \sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)} + \sum_w \frac{\pi^3(X_t, w)}{e_t^2(X_t, w)} \Big).\]

(iii) For term 35 , by Proposition 2, there exists \(U>0\) such that \[\mathop{\mathrm{\mathbb{E}}}\big[\big(\widehat{\Gamma}_t(X_t, \pi) - \sum_w \pi(X_t, w)\mu(X_t, w)\big)^2|H_{t-1}, X_t\big] = Var(\widehat{\Gamma}_t|H_{t-1}, X_t) \leq U \sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)} .\]

(iv) By Proposition 1, term \(\eqref{eq:xi95fourth95iv}=0\).

(v) Term 37 is bounded by a constant by Assumption 2.

Thus we have \[\begin{align} \sum_{t=1}^T \mathbb{E}_{}\left[\left.{\xi_{T,t}^4}\right|{H_{t-1}}\right] &= \frac{\sum_{t=1}^T h_t^4 \mathop{\mathrm{\mathbb{E}}}\big[\big(\widehat{\Gamma}_t(X_t, \pi) - Q( \pi)\big)^4| H_{t-1}\big]}{\mathop{\mathrm{\mathbb{E}}}\big[h_t^2 \big(\widehat{\Gamma}_t(X_t, \pi) - Q( \pi)\big)^2\big]^2}\\ &\lesssim \frac{\sum_{t=1}^T h_t^4 \mathop{\mathrm{\mathbb{E}}}\big[ 1 + \sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)} + \sum_w \frac{\pi^3(X_t, w)}{e_t^2(X_t, w)} + \sum_w \frac{\pi^4(X_t, w)}{e_t^3(X_t, w)} \big] }{ \big(\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\big[h_t^2\sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}\big]\big)^2 }\\ &\stackrel{(i)}{\leq} \frac{\sum_{t=1}^T h_t^4 \mathop{\mathrm{\mathbb{E}}}\big[ \sum_w \frac{\pi^4(X_t, w)}{e_t^3(X_t, w)} |H_{t-1}\big] }{ \big(\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\big[ h_t^2\sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}\big]\big)^2}\\ &\stackrel{(ii)}{=} \frac{\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\big[ \sum_w \frac{\pi^4(X_t, w)}{e_t^3(X_t, w)} |H_{t-1}\big] \big/ \mathop{\mathrm{\mathbb{E}}}\big[\sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}|H_{t-1}\big]^2 }{T^2}\\ &\stackrel{(iii)}{ \lesssim} \frac{\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\big[ \sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)} t^{2\alpha} |H_{t-1}\big] \big/ \mathop{\mathrm{\mathbb{E}}}\big[\sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}|H_{t-1}\big] }{T^2}=\frac{\sum_{t=1}^T t^{2\alpha} }{T^2}=O(T^{2\alpha-1})\xrightarrow 0 , \end{align}\] where in (i), we use Lemma 1 ; in (ii), we use the definition of non-contextual StableVar weights that \(h_t=\big(\mathop{\mathrm{\mathbb{E}}}\big[ \sum_w \frac{\pi^2(X_t, w)}{e_t(X_t, w)}|H_{t-1} \big]\big)^{-1/2}\); in (iii), we use the condition that \(1\geq e_t\geq C t^{-\alpha}\).

Collectively, \(\xi_{T,t}\) satisfies the two conditions for martingale central limit theorem in Proposition 3, and thus we have \(\sum_{t=1}^T \xi_{T,t}\xrightarrow{d}\mathop{\mathrm{\mathcal{N}}}(0,1)\).

10.3 CLT of \(\widehat{Q}^{NC}_T\)↩︎

We now establish Theorem 1. We have \[\label{eq:t-stat-nc} \begin{align} \frac{\widehat{Q}^{NC}_T(\pi) - Q(\pi)}{\sqrt{\widehat{V}_T^{NC}(\pi) }} = \frac{ \sum_{t=1}^T h_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi)) }{\sqrt{ \sum_{t=1}^T h_t^2(\widehat{\Gamma}_t(X_t, \pi) - \widehat{Q}_T^{NC}(\pi) )^2}} = \sum_{t=1}^T \xi_{T,t} \cdot \frac{\sqrt{\mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T h_t^2(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi) )^2] } }{\sqrt{ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - \widehat{Q}_T^{NC}(\pi) )^2} }. \end{align}\tag{38}\] We have shown that \(\sum_{t=1}^T \xi_{T,t}\) is asymptotically standard normal, so by Slutsky’s theorem it suffices to show that the rightmost factor in 38 converges to \(1\) in probability. We have \[\begin{align} \frac{ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - \widehat{Q}_T^{NC}(\pi) )^2 }{ \mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2] } = \underbracket[0.4pt]{\frac{ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2 }{ \mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2] }}_{(a)} + \underbracket[0.4pt]{ \frac{ \sum_{t=1}^T h^2_t(Q(\pi)- \widehat{Q}_T^{NC}(\pi) )^2 }{ \mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2] } }_{(b)} \\+ \underbracket[0.4pt]{2~\frac{ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))(Q(\pi)- \widehat{Q}_T^{NC}(\pi) ) }{ \mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2] } }_{(c)}. \end{align}\] We shall show that term(a)\(\xrightarrow{p}1\), term(b)\(\xrightarrow{p}0\), and term(c)\(\xrightarrow{p}0\), which concludes the proof.

• Term (a). We have \[\begin{align} \frac{ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2 }{ \mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2] } = \frac{ \sum_{t=1}^T h^2_t\big((\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2 - \mathop{\mathrm{\mathbb{E}}}[h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2|H_{t-1}] \big) }{ \mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2] } \\+ \frac{ \sum_{t=1}^T h^2_t\mathop{\mathrm{\mathbb{E}}}[h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2|H_{t-1} ]}{ \mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2] } \end{align}\] The first term converges to \(0\) (to be shown shortly), and the second term is \(\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[\xi_{T,t}^2|H_{t-1}]\xrightarrow{p}1\). The first term is the sum of a martingale difference sequence, and we have \[\begin{align} & \mathop{\mathrm{\mathbb{E}}}\Big[ \Big| \frac{ \sum_{t=1}^T h^2_t\big((\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2 - \mathop{\mathrm{\mathbb{E}}}[h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2|H_{t-1}] \big) }{ \mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2] } \Big|^2\Big]\\ =~ &\mathop{\mathrm{\mathbb{E}}}\Big[\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\Big[ \frac{ h^4_t\big((\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^4 - \mathop{\mathrm{\mathbb{E}}}[h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2|H_{t-1}] \big)^2 }{ \mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2]^2} \Big|H_{t-1}\Big]\Big]\\ \leq~ &\mathop{\mathrm{\mathbb{E}}}\Big[\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\Big[ \frac{ h^4_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^4 }{ \mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2]^2} \Big|H_{t-1}\Big]\Big] = \mathop{\mathrm{\mathbb{E}}}\Big[\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\big[\xi_{T,t}^4 |H_{t-1}\big]\Big] = O(T^{2\alpha-1})\rightarrow 0.\\ \end{align}\] In the last step, we’ve used a fourth moment bound from Section 10.2.2.

• Term (b). This term vanishes because \(\widehat{Q}_T^{NC}\xrightarrow{p}Q\). The ratio \[\begin{align} \frac{ (Q(\pi)- \widehat{Q}_T^{NC}(\pi) )^2 \sum_{t=1}^T h^2_t }{ \mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2] } \end{align}\] goes to zero because (i) the squared StableVar weights \(h_t^2 = 1/\mathop{\mathrm{\mathbb{E}}}[{\sum_{w}\frac{\pi^2(X_t, w)}{e_t(X_t, w)}}|H_{t-1}]\) are each less than one and their sum, therefore, is less than \(T\) and (ii) each term in the denominator is bounded away from zero, as 3 implies that the inverse of \(h_t^2\) is on the order of \(\mathop{\mathrm{\mathbb{E}}}[(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2|H_{t-1}]\), so the denominator itself is \(\Omega(T)\).

• Term (c). This term also vanishes by Cauchy-Schwartz inequality. We have \[\begin{align} & \Big(\frac{ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))(Q(\pi)- \widehat{Q}_T^{NC}(\pi) ) }{ \mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2] }\Big)^2 \\\leq &\frac{ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2 }{ \mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2] } \times \frac{ \sum_{t=1}^T h^2_t(Q(\pi)- \widehat{Q}_T^{NC}(\pi) )^2 }{ \mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T h^2_t(\widehat{\Gamma}_t(X_t, \pi) - Q(\pi))^2] }\xrightarrow{p}0. \end{align}\]

11 Limit theorems of contextual weighting↩︎

In this section, we establish Theorem 2. For a target policy \(\pi\), the policy value is \(Q(\pi)=\mathop{\mathrm{\mathbb{E}}}[\sum_w\pi(x,w)\mu(x,w)]\). Our goal is to show that, with contextual StableVar weights \(h_t(x)=1/\sqrt{\sum_w\frac{\pi^2(x,w)}{e_t(x,w)}}\), the estimate \(\widehat{Q}_T^C\) is consistent and asymptotically normal. In what follows, we shall use \(P_x=\mathop{\mathrm{\mathbb{P}}}(X=x)\) and \(Q_x=Q(x,\pi)=\sum_w\pi(x,w)\mu(x,w)\) for notational convenience.

The following lemma characterizes the convergence of StableVar weights for each context and each pair of contexts, which be will invoked multiple times throughout the proof.

11.1 Consistency of \(\widehat{Q}_T^C\)↩︎

Estimate \(\widehat{Q}_T^C\) is in fact a summation of policy value estimates conditional on covariates, that is, \[\begin{align} \widehat{Q}_T^C (\pi) = \sum_x (\widehat{P_x Q_x})_T, \quadwhere\quad (\widehat{P_x Q_x})_T := \frac{\sum_{t=1}^T h_t(x)\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) }{\sum_{t=1}^T h_t(x)}. \end{align}\] We have \[\begin{align} \widehat{Q}_T^C(\pi) - Q(\pi)=\sum_x \sum_{t=1}^T \frac{ h_t(x) (\mathop{\mathrm{\mathbb{I}}}\{ X_t = x\}\widehat{\Gamma}_t(x, \pi) - P_x Q_x)}{\sum_t h_t(x) } = \sum_x (\widehat{P_x Q_x})_T - P_xQ_x. \end{align}\] It thus suffices to show that each \((\widehat{P_x Q_x})_T\) is consistent for \(P_xQ_x\). To do so, we introduce a context-specific MDS \(\eta_{T,t}(x)\) for each covariate \(x\), \[\label{eq:eta95x} \eta_{T,t}(x) = \frac{h_t(x)(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x)}{\sqrt{\mathop{\mathrm{\mathbb{E}}}[\sum_{s=1}^T h_t^2(x)(\mathop{\mathrm{\mathbb{I}}}\{X_s=x\}\widehat{\Gamma}_s(w) - P_xQ_x)^2 ]}}.\tag{47}\] which martingale difference property is justified by observing \(\mathop{\mathrm{\mathbb{E}}}[ \eta_{T,t} | H_{t-1} ]=0\) by routine calculation. We immediately have \(\mathop{\mathrm{\mathbb{E}}}[ (\sum_{t=1}^T\eta_{T,t})^2 ]= \mathop{\mathrm{\mathbb{E}}}[ \sum_{t=1}^T\eta_{T,t}^2 ]=1\).

The conditional variance of the numerator in 47 can be calculated explicitly and dominated by \(\sum_w \frac{\pi^2(x,w)}{e_t(x,w)}\), that is, \[\label{eq:eta95second95moment} \begin{align} &\mathbb{E}_{}\left[\left.{(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x)^2}\right|{H_{t-1}}\right] \\ = & P_x \mathbb{E}_{}\left[\left.{(\widehat{\Gamma}_t(x, w) - P_xQ_x)^2}\right|{H_{t-1}, X_t=x}\right] + (1-P_x)P^2_xQ^2_x\\ = & P_x \mathbb{E}_{}\left[\left.{(\widehat{\Gamma}_t(x,w) - Q_x)^2}\right|{H_{t-1}, X_t=x}\right] + P_x (1-P_x)^2 Q^2_x + (1-P_x)P_x^2Q^2_x\\ = & P_x \mathbb{E}_{}\left[\left.{(\widehat{\Gamma}_t(x,w) - Q_x)^2}\right|{H_{t-1}, X_t=x}\right] + P_x(1-P_x)Q^2_x\\ = & P_x \mathop{\mathrm{Var}}(\widehat{\Gamma}_t(x,w)|H_{t-1}, X_t=x) + P_x(1-P_x)Q^2_x, \end{align}\tag{48}\] which is lower bounded by \(c_1 \cdot \sum_w \frac{\pi^2(x,w)}{e_t(x,w)}\) and upper bounded by \(c_2 \cdot \sum_w \frac{\pi^2(x,w)}{e_t(x,w)}\) for some constant \(c_1, c_2\) by Proposition 2. Moving on, we have, \[\begin{align} |(\widehat{P_xQ_x})_T - P_xQ_x|^2 = &\Big|\frac{\sum_{t=1}^T h_t(x)(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x) }{\sum_{t=1}^T h_t(x)}\Big|^2 \\ = &\Big|\sum_{t=1}^T \eta_{T,t}(x) \Big|^2 \frac{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T\big(h_t(x)\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x\big)^2]] }{(\sum_{t=1}^T h_t(x))^2} \\ \stackrel{(i)}{\lesssim} & \Big|\sum_{t=1}^T \eta_{T,t}(x) \Big|^2 \frac{T}{(\sum_{t=1}^T t^{-\alpha/2})^2 } =\Big| \sum_{t=1}^T \eta_{T,t}(x)\Big|^2 O(T^{\alpha-1}), \end{align}\] where in (i), we use 48 , \(h_t(x)=1/\sqrt{\sum_w \frac{\pi^2(x,w)}{e_t(x,w)}}\), and that \(e_t\geq Ct^{-\alpha}\) for some \(\alpha\in[0,1/2)\) by Assumption 2. Thus for any \(\epsilon>0\), \[\begin{align} \mathop{\mathrm{\mathbb{P}}}(|(\widehat{P_xQ_x})_T - P_xQ_x|>\epsilon)\leq& \epsilon^{-2} \mathop{\mathrm{\mathbb{E}}}[|(\widehat{P_xQ_x})_T - P_xQ_x|^2]\\ \leq &\epsilon^2 \mathop{\mathrm{\mathbb{E}}}\Big[\Big|\sum_{t=1}^T \eta_{T,t}(x)\Big|^2\Big]O(T^{\alpha-1})\\ = & \epsilon^2 O(T^{\alpha-1})\rightarrow 0, \end{align}\] which concludes the consistency of \((\widehat{P_xQ_x})_T\) and in turn \(\widehat{Q}_T^C\).

11.2 Asymptotic normality of \(\widehat{Q}_T^C\)↩︎

Expanding the definitions, we have \[\label{eq:studentized} \frac{\widehat{Q}_T^C(\pi) - Q(\pi)}{\sqrt{\widehat{V}^C_T(\pi) }} = \frac{1}{\sqrt{\widehat{V}^C_T(\pi) }} \sum_{t=1}^T \sum_x \frac{ h_t(x) (\mathop{\mathrm{\mathbb{I}}}\{ X_t = x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x)}{\sum_t h_t(x) },\tag{49}\] where the variance estimate given in 49 can be rewritten as \[\label{eq:vhatc} \widehat{V}_T^C(\pi) := \sum_{t=1}^T \Big( \sum_{x}\frac{ h_t(x)(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - (\widehat{P_x Q_x})_T) }{ \sum_{t=1}^T h_t(x) } \Big)^2.\tag{50}\]

One challenge in proving 49 is asymptotically normal is that the weight normalization term \(\sum_t h_t(x)\) in 49 is context-specific, and hence we cannot leverage a single martingale difference sequence (MDS) to establish the central limit theorem as we did in Appendix 10 for non-contextual weighting. However, we notice that 49 is related to the sum of context-specific MDSs \(\eta_{T,t}(x)\). Therefore, instead of working with 49 directly, we will show that the following “auxiliary” statistic (which is also a MDS) is asymptotically normal: \[\label{eq:sum95zeta} \begin{align} \sum_{t=1}^T \zeta_{T,t} &:= \frac{1}{\sqrt{V_T^C}} \sum_{t=1}^T \sum_{x}\alpha_T(x)\eta_{T,t}(x), \end{align}\tag{51}\] where the aggregation weight is given by \[\label{eq:alpha95T} \alpha_T(x) = \frac{\sqrt{\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[h^2_t(x)(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x)^2]}}{ \sum_{t=1}^T\mathbb{E}_{}\left[{h_t(x)}\right] } .\tag{52}\] and the variance \(V_T^C\) is given by \[\label{eq:vc} \begin{align} & \quad V_T^C = \sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\Big[ \Big( \sum_{x}\frac{ h_t(x)(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x) }{ \sum_{t=1}^T\mathbb{E}_{}\left[{h_t(x)}\right] } \Big)^2\Big]. \end{align}\tag{53}\]

Once this is established, we then show that we can replace the population quantities by their sample counterparts (e.g., \(\widehat{V}_T^C\) by \(V_T^C\)) without perturbing the asymptotic behavior of the statistic. This is done in the following steps.

• Step I: CLT of context-specific MDS \(\eta_{T,t}(x)\). For a fixed covariate \(x\), this essentially reduces to a non-contextual problem, so we can prove asymptotic normality of \(\sum_{t=1}^T \eta_{T, t}(x)\) by repeating a similar proof to Theorem 1.

• Step II: CLT of the aggregation MDS \(\zeta_{T,t}\). We shall show that this \(\zeta_{T,t}\) satisfies two martingale CLT conditions stated in Proposition 3 leveraging that each \(\eta_{T,t}(x)\) satisfies the same conditions; hence \(\sum_{t=1}^T \zeta_{T,t}\) is asymptotically standard normal.

• Step III: CLT of 49 . The final step in the proof is to show that we can replace the population quantities \(V_T^{C}\) and \(\sum_{t=1}^{T} \mathop{\mathrm{\mathbb{E}}}[h_t(X_t)]\) by their sample counterparts.

11.2.1 Step I: CLT of context-specific MDS \(\eta_{T,t}(x)\)↩︎

Fixing a covariate \(x\), the context-specific MDS \(\eta_{T,t}(x)\) reduces to that constructed in multi-armed bandits, which has been studied in [18]. The subtlety here is the indicator function \(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\), but the entire argument from [18] directly applies. For completeness, we lay out the details and verify two CLT conditions of \(\eta_{T,t}(x)\) required in Proposition 3.

11.2.1.1 Variance convergence.

We want to show that \[\label{eq:eta2} \begin{align} \sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[\eta^2_{T,t}(x)|H_{t-1}] = \frac{ \sum_{t=1}^T h_t(x)^2 \mathop{\mathrm{\mathbb{E}}}[(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x)^2|H_{t-1}] }{ \sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[h_t(x)^2 (\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x)^2] }\xrightarrow{p}1. \end{align}\tag{54}\]

Each summand in the numerator has been computed analytically in Appendix 8.2, that is, \[\begin{align} &\mathbb{E}_{}\left[\left.{(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x)^2}\right|{H_{t-1}}\right] \\ = & P_x \mathop{\mathrm{Var}}(\widehat{\Gamma}_t(X_t,\pi)\mid H_{t-1}, X_t=x) + P_x(1-P_x)Q_x^2\\ = & P_x \sum_w\frac{\pi^2(x, w)\mathrm{Var}_{}\left({Y_t(w)\mid x}\right)}{e_t(x, w)} + P_x \sum_w\frac{\pi^2(x, w)(\hat{\mu}_t(x, w)-\mu(x, w))^2}{e_t(x, w)} \\ &\quad - P_x \Big(\sum_w \pi(x, w)\big(\hat{\mu}_t(x, w)-\mu(x, w)\big)\Big)^2 + P_x(1-P_x)Q_x^2 \end{align}\] The numerator in 54 can be decomposed as \[\begin{align} Z_T =& \sum_{t=1}^T h_t^2(x) \Big\{P_x \sum_w\frac{\pi^2(x, w)\mathrm{Var}_{}\left({Y_t(w)\mid x}\right)}{e_t(x, w)} + P_x \sum_w\frac{\pi^2(x, w)(\hat{\mu}_t(x, w)-\mu(x, w))^2}{e_t(x, w)} \\ & - P_x \Big(\sum_w \pi(x, w)\big(\hat{\mu}_t(x, w)-\mu(x, w)\big)\Big)^2 + P_x(1-P_x)Q_x^2\Big\}\\ = & \sum_{t=1}^T h_t^2(x) \Big\{P_x \sum_w\frac{\pi^2(x, w)[\mathrm{Var}_{}\left({Y_t(w)\mid x}\right) + (\mu_\infty(x,w)-\mu(x,w))^2 ]}{e_t(x, w)} \\ & - P_x \Big(\sum_w \pi(x, w)\big(\mu_\infty(x, w)-\mu(x, w)\big)\Big)^2 + P_x(1-P_x)Q_x^2\Big\}\\ & + \sum_{t=1}^T h_t^2(x)P_x\Big\{\sum_w\frac{\pi^2(x,w)}{e_t(x,w)}[(\hat{\mu}_t(x,w)-\mu_\infty(x,w))^2+2(\hat{\mu}_t(x,w)-\mu_\infty(x,w))(\mu_\infty(x,w)- \mu(x,w))]\\ & -\big(\sum_w \pi(x,w)(\hat{\mu}_t(x, w) -\mu_\infty(x,w))\big)^2 - 2(\sum_w \pi(x,w)(\hat{\mu}_t(x, w) -\mu_\infty(x,w))(\sum_w \pi(x,w)(\mu_\infty(x, w) -\mu(x,w)) \Big\}, \end{align}\] which can be characterized as (to be shown shortly) \[\label{eq:eta95ZT} \begin{align} Z_T =& \sum_{t=1}^T h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)} +C_2(x) \sum_{t=1}^T h_t^2(x) + o_p\Big(\sum_{t=1}^T h_t^2(x) \Big\{\sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)} +C_2(x)\Big\} \Big), \end{align}\tag{55}\] where \(C_1(x,w) = P_x(\mathrm{Var}_{}\left({Y_t(w)\mid x}\right) + (\mu_\infty(x,w)-\mu(x,w))^2)\) and \(C_2(x) = - P_x \Big(\sum_w \pi(x, w)\big(\hat{\mu}_t(x, w)-\mu(x, w)\big)\Big)^2 + P_x(1-P_x)Q_x^2\) do not depend on the history \(H_{t-1}\). Note that \(\sum_w \frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)}+C_2(x)\geq \sum_w \frac{\mathop{\mathrm{Var}}(Y_t(w)|x)\pi^2(x,w)}{e_t(x,w)}\) by a calculation that is similar to the one done in 30 . Similarly, we have its expectation as \[\label{eq:eta95EZT} \begin{align} \mathop{\mathrm{\mathbb{E}}}[Z_T] =& \sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)}] +C_2(x) \sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[ h_t^2(x)] + o\Big(\sum_{t=1}^T\mathop{\mathrm{\mathbb{E}}}\Big[ h_t^2(x)\Big\{ \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)}+C_2(x)\Big\}\Big] \Big). \end{align}\tag{56}\] If we have 55 and 56 , to show 54 , we only need to show \[\label{eq:eta295target} \frac{\sum_{t=1}^T h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)} +C_2(x) \sum_{t=1}^T h_t^2(x) }{\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)}] +C_2(x) \sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[ h_t^2(x)] }\xrightarrow{p}1.\tag{57}\]

By Lemma 2, we have \[\sum_{t=1}^T h_t^2(x) \Big/ \mathop{\mathrm{\mathbb{E}}}\Big[\sum_{t=1}^T h_t^2(x)\Big] \xrightarrow{p}1.\]

In addition, by condition that \(\mathop{\mathrm{\mathbb{E}}}[e_t^{-1}(x,w)]/e_t^{-1}(x,w) \xrightarrow{a.s.}1\), we have \[\label{eq:eta95h2c95as} h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)} \bigg/ \Big\{\mathop{\mathrm{\mathbb{E}}}\Big[\sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)} \Big]\Big/\mathop{\mathrm{\mathbb{E}}}\Big[ \sum_{w}\frac{\pi^2(x,w)}{e_t(x,w)}\Big]\Big\} \xrightarrow{a.s.}1,\tag{58}\] by a caculation similar to 41 . Recall the definition of StableVar weights is \(h_t(x) = 1/\sqrt{\sum_w\frac{\pi^2(x,w)}{e_t(x,w)}}\), we thus have \(h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)}\) is bounded above and away from zero, thus

\[\label{eq:eta95h2c95L1} h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)} \bigg/ \Big\{\mathop{\mathrm{\mathbb{E}}}\Big[\sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)} \Big]\Big/\mathop{\mathrm{\mathbb{E}}}\Big[ \sum_{w}\frac{\pi^2(x,w)}{e_t(x,w)}\Big]\Big\} \xrightarrow{L_1}1.\tag{59}\]

Combining 58 , 59 , and Lemma 2, we have \[\begin{align} &\frac{\sum_{t=1}^T h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)} +C_2(x) \sum_{t=1}^T h_t^2(x) }{\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)}] +C_2(x) \sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[ h_t^2(x)] } \\ =& \frac{(\{\sum_{t=1}^T h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)} +C_2(x)h_t^2(x)\} /M_T-1)M_T + M_T}{(\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)}] +C_2(x) h_t^2(x)]/M_T-1)M_T+M_T }\\ = & \frac{o_p(1)M_T+M_T}{o(1)M_T+M_T}\xrightarrow{p}1, \end{align}\] where \(M_T := \sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}\Big[\sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)} + C_2(x) \Big]\big/\mathop{\mathrm{\mathbb{E}}}[ \sum_{w}\frac{\pi^2(x,w)}{e_t(x,w)}]\), proving 57 .

To complete the proof, let’s show 55 and 56 . Define the next quantity, which collects the terms we’ll prove to be asymptotically negligible relative to the dominant terms in these expressions: \[\begin{align} & m(x) := \sum_{t=1}^T h_t^2(x)P_x\Big\{\sum_w\frac{\pi^2(x,w)}{e_t(x,w)}[(\hat{\mu}_t(x,w)-\mu_\infty(x,w))^2+2(\hat{\mu}_t(x,w)-\mu_\infty(x,w))(\mu_\infty(x,w)- \mu(x,w))]\\ & -\big(\sum_w \pi(x,w)(\hat{\mu}_t(x, w) -\mu_\infty(x,w))\big)^2 - 2(\sum_w \pi(x,w)(\hat{\mu}_t(x, w) -\mu_\infty(x,w))(\sum_w \pi(x,w)(\mu_\infty(x, w) -\mu(x,w)) \Big\}. \end{align}\]

For 55 , we need to show \(m(x) = o_p(\sum_{t=1}^T h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)})\), which is true since each summand in \(m_t\) is \(o_p(h_t^2(x)\sum_w\frac{\pi^2(x,w)}{e_t(x,w)})\) since \(\sup_{x,w}|\hat{\mu}_{t}(x,w)-\mu_\infty(x,w)|\xrightarrow{a.s.}0\); also notice that \(\sum_{t=1}^T h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)} = \Theta(T)\). Then invoking Proposition 4, we have \(m(x) / \big\{ \sum_{t=1}^T h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)}\big\} = o_p(1)\) and thus 55 .

For 56 , we need to show \(\mathop{\mathrm{\mathbb{E}}}[m(x)] = o(\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)}])\), which is true since each summand in \(\mathop{\mathrm{\mathbb{E}}}[m_t]\) is \(o(\mathop{\mathrm{\mathbb{E}}}[h_t^2(x)\sum_w\frac{\pi^2(x,w)}{e_t(x,w)}])\) since \(\sup_{x,w}|\hat{\mu}_{t}(x,w)-\mu_\infty(x,w)|\xrightarrow{L_1}0\); also notice that \(\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)}] = \Theta(T)\). Then invoking Proposition 5, we have
\(\mathop{\mathrm{\mathbb{E}}}[m(x)] / \big\{ \mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t^2(x) \sum_{w}\frac{C_1(x,w)\pi^2(x,w)}{e_t(x,w)}]\big\} = o(1)\) and thus 56 .

Remark . \(\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[\eta_t^2(x)|H_{t-1}]\) is bounded by derivation in 48 , we thus have \(\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[\eta_t^2(x)|H_{t-1}]\xrightarrow{L_p}1\) for any \(p>0\).

11.2.1.2 Moment decay.

A routine calculation (similar to what we have done in Appendix 10.2) leads to \[\begin{align} \mathbb{E}_{}\left[\left.{(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x)^4}\right|{H_{t-1}}\right] &\leq c\cdot \Big( 1+\sum_w \frac{\pi^2(x,w)}{e_t(x,w)} +\sum_w \frac{\pi^3(x,w)}{e_t^2(x,w)}+\sum_w \frac{\pi^4(x,w)}{e_t^3(x,w)} \Big)\leq c'\cdot\sum_w \frac{\pi^4(x,w)}{e_t^3(x,w)}, \end{align}\] for some constants \(c', c\). We thus have \[\begin{align} \sum_{t=1}^T \mathbb{E}_{}\left[\left.{\eta^4_{T,t}(x)}\right|{H_{t-1}}\right] &= \frac{\sum_{t=1}^T h_t^4(x) \mathbb{E}_{}\left[\left.{(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x)^4}\right|{H_{t-1}}\right]}{ \big( \sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[h_t(x)^2 (\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x)^2]\big)^2 }\\ &\lesssim \frac{\sum_{t=1}^T \sum_w \frac{\pi^4(x,w)}{e_t^3(x,w)}\big/(\sum_w \frac{\pi^2(x,w)}{e_t(x,w)})^2 }{T^2}\\ &\leq \frac{\sum_{t=1}^T \sum_w \frac{\pi^4(x,w)}{e_t^3(x,w)}\big/\sum_w \frac{\pi^4(x,w)}{e_t^2(x,w)} }{T^2} \lesssim \frac{\sum_{t=1}^T t^{\alpha}}{T^2} = O(T^{\alpha-1})\xrightarrow{a.s.} 0. \end{align}\] Invoking Proposition 3, we have \(\sum_{t=1}^T \eta_{T,t}(x)\xrightarrow{d}\mathop{\mathrm{\mathcal{N}}}(0,1).\)

11.2.2 Step II: CLT of aggregated MDS \(\zeta_{T,t}\)↩︎

We set out to show that we can aggregate our auxiliary MDS \(\eta_{T,t}(x)\) for each content \(x\) into an asymptotically normal studentized statistic \(\zeta_{T,t}\) for the value of the policy across \(x\). To do so, we will again prove that \(\zeta_{T,t}\) satisfies the conditions in Proposition 3. Recall that \(\zeta_{T, t} = \sum_x \eta_{T, t}(x) \alpha_T(x)/ (V_T^C)^{-1/2}\), where \(\alpha_T(x)\) and \(V_T^C\) are defined in 52 and 53 respectively. We in addition introduce the lemma below that will become handy in the subsequent proof.

11.2.2.1 Variance convergence.

We will invoke Lemma 3 to prove the result \(\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[\zeta_{T,t}^2|H_{t-1}]\xrightarrow{p}1\). In fact, the numerator of \(\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[\zeta_{T,t}^2|H_{t-1}]\) can be written as \(A_T-B_T\), and its denominator is \(\mathop{\mathrm{\mathbb{E}}}[A_T - B_T]\), where \[\label{eq:at95bt} \begin{align} & A_T = \sum_x \frac{\sum_{t=1}^T h_t^2(x) \mathop{\mathrm{\mathbb{E}}}[(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) -P_xQ_x )^2|H_{t-1}]}{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]^2}, \\ &B_T = \sum_{x\neq y} \frac{ \sum_{t=1}^T h_t(x)h_t(y)P_xP_yQ_xQ_y }{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(y)]. }. \end{align}\tag{60}\] It suffices to verify that \(A_T, B_T\) satisfy conditions in Lemma 3.

• Convergence \(A_T/\mathop{\mathrm{\mathbb{E}}}[A_T]\xrightarrow{p}1\). By variance convergence of \(\eta_{T,t}(x)\), we have for each \(x\in\mathop{\mathrm{\mathcal{X}}}\), \[\begin{align} \frac{\sum_{t=1}^T h_t^2(x) \mathop{\mathrm{\mathbb{E}}}[(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) -P_xQ_x )^2|H_{t-1}]}{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]^2} \Big/ \frac{ \sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[h_t^2(x)(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) -P_xQ_x )^2] }{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]^2 } \xrightarrow{p}1. \end{align}\]

• Convergence \(B_T/\mathop{\mathrm{\mathbb{E}}}[B_T]\xrightarrow{p}1\). By Lemma 2, for each \(x\neq y\) we have \[\begin{align} & \frac{\sum_{t=1}^T h_t(x)h_t(y) }{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)h_t(y)]}\xrightarrow{p}1\\ \Rightarrow \quad & \frac{ \sum_{t=1}^T h_t(x)h_t(y)P_xP_yQ_xQ_y }{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(y)] }\Big/ \frac{ \sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[h_t(x)h_t(y)]P_xP_yQ_xQ_y }{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(y)]} \xrightarrow{p}1. \end{align}\]

• Show that \(|A_T-B_T|\geq M_a A_T\) for some constant \(M_a\). \[\begin{align} & A_T- B_T \\ =& \sum_x \frac{\sum_{t=1}^T h_t^2(x) \mathop{\mathrm{\mathbb{E}}}[(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) -P_xQ_x )^2|H_{t-1}, X_t=x]}{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]^2} - \sum_{x\neq y} \frac{ \sum_{t=1}^T h_t(x)h_t(y)P_xP_yQ_xQ_y }{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(y)] }\\ = &\sum_x \frac{\sum_{t=1}^T h_t^2(x)P_x \mathop{\mathrm{\mathbb{E}}}[(\widehat{\Gamma}_t(x, \pi) -Q_x )^2|H_{t-1}, X_t=x]}{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]^2} +\sum_x \frac{\sum_{t=1}^T h_t^2(x)P_x(1-P_x) Q_x^2}{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]^2} \\ &\quad \qquad- \sum_{x\neq y} \frac{ \sum_{t=1}^T h_t(x)h_t(y)P_xP_yQ_xQ_y }{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(y)] }\\ =& \sum_x \frac{\sum_{t=1}^T h_t^2(x)P_x \mathop{\mathrm{\mathbb{E}}}[(\widehat{\Gamma}_t(x,\pi ) -Q_x )^2|H_{t-1}, X_t=x]}{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]^2} + \sum_{t=1}^T \sum_{x\neq y}P_xP_y\Big( \frac{ h_t(x)Q_x }{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]} - \frac{ h_t(y)Q_y }{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(y)]} \Big)^2\\ & \geq \sum_{t=1}^T \sum_x\frac{h^2_t(x)P_x\mathop{\mathrm{\mathbb{E}}}[(\widehat{\Gamma}_t(x, \pi) -Q_x )^2|H_{t-1}, X_t=x]}{ \mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]^2 } \gtrsim \sum_{t=1}^T \sum_x\frac{h^2_t(x)P_x}{ \mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]^2 } \end{align}\] Thus, we have \[\begin{align} A_T- B_T & \geq \sum_{t=1}^T \sum_x\frac{h^2_t(x)P_x\mathop{\mathrm{\mathbb{E}}}[(\widehat{\Gamma}_t(x, \pi) -Q_x )^2|H_{t-1}, X_t=x]}{ \mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]^2 } \\ &\gtrsim \sum_x \frac{\sum_{t=1}^T h_t^2(x) \mathop{\mathrm{\mathbb{E}}}[(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) -P_xQ_x )^2|H_{t-1}]}{\mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]^2}= A_T. \end{align}\]

• Show that \(|A_T-B_T|\geq M_b B_T\) for some constant \(M_b\). Similarly, \[\begin{align} A_T-B_T\gtrsim \sum_{t=1}^T \sum_x\frac{h^2_t(x)P_x}{ \mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]^2 }\gtrsim \sum_{t=1}^T \sum_x\frac{h^2_t(x)P_x(1-P_x) Q_x^2}{ \mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)]^2 }\\ \stackrel{(i)}{\geq} \sum_{t=1}^T \sum_{x\neq y}\frac{h_t(x)h_t(y)P_xP_yQ_xQ_y }{ \mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(x)] \mathop{\mathrm{\mathbb{E}}}[\sum_{t=1}^T h_t(y)] } = B_T, \end{align}\] where (i) is by Cauchy-Schwartz inequality.

11.2.2.2 Moment decay.

We proceed to show that the fourth moment of \(\sum_{t=1}^T\zeta_{T,t}=\sum_x\frac{\alpha_T(x)}{\sqrt{V_T^C}} \sum_{t=1}^T\eta_{T,t}(x)\) decays. To start, note that the aggregation weight \(\frac{\alpha_T(x)}{\sqrt{V_T^C}} = \sqrt{\frac{\mathop{\mathrm{\mathbb{E}}}[A_T]}{\mathop{\mathrm{\mathbb{E}}}[A_T]-\mathop{\mathrm{\mathbb{E}}}[B_T]}}\) is bounded, where \(A_T, B_T\) are defined in 60 . The conditional 4th moment of \(\zeta_{T,t}\) can be bounded as follows. \[\label{eq:zeta95lyap} \begin{align} \sum_{t=1}^T\mathop{\mathrm{\mathbb{E}}}\Big[\zeta_{T,t}^4|H_{t-1}\Big]^{1/4} &= \sum_{t=1}^T\mathop{\mathrm{\mathbb{E}}}\Big[\Big(\sum_x \eta_{T,t}(x) \frac{\alpha_T(x)}{\sqrt{V_T^C}}\Big)^4 |H_{t-1}\Big]^{1/4} \\ &\leq \sum_{t=1}^T\sum_x \frac{\alpha_T(x)}{\sqrt{V_T^C}}\left(\mathbb{E}_{}\left[\left.{\eta_{T,t}^4 (x)}\right|{H_{t-1}}\right] \right)^{1/4} \\ &\lesssim \sum_x \sum_{t=1}^T \mathbb{E}_{}\left[\left.{\eta_{T,t}^4 (x)}\right|{H_{t-1}}\right]^{1/4} \\ &\leq |\mathop{\mathrm{\mathcal{X}}}| \max_{x'} \Big(\sum_{t=1}^T\mathbb{E}_{}\left[\left.{\eta_{T,t}^4 (x')}\right|{H_{t-1}}\right]\Big)^{1/4} \xrightarrow{a.s.}0, \end{align}\tag{61}\] where the first inequality is due to Minkowski inequality, the second uses the fact that \(\alpha_T(x)/\sqrt{V_T^C}\) is bounded by above; the limit follows from the previous subsection.

Therefore, by Proposition 3, we have that \(\sum_{t=1}^T \zeta_{T,t}\xrightarrow{d} \mathop{\mathrm{\mathcal{N}}}(0,1)\).

11.2.3 Step III: CLT of \(\widehat{Q}_T^{C}\)↩︎

We now connect the convergence from \(\zeta_{T,t}\) to \(\widehat{Q}_T^C\). This procedure decomposes into two parts.

(a) From \(\sum_{t=1}^T \zeta_{T,t}\xrightarrow{d}\mathop{\mathrm{\mathcal{N}}}(0,1)\) to \((\widehat{Q}^C_T(\pi) - Q(\pi))\big/{\sqrt{V^C_T(\pi) }}\xrightarrow{d}\mathop{\mathrm{\mathcal{N}}}(0,1)\).

(b) From \((\widehat{Q}^C_T(\pi) - Q(\pi))\big/{\sqrt{V^C_T(\pi) }}\xrightarrow{d}\mathop{\mathrm{\mathcal{N}}}(0,1)\) to \((\widehat{Q}^C_T(\pi) - Q(\pi))\big/{\sqrt{\widehat{V}^C_T(\pi) }}\xrightarrow{d}\mathop{\mathrm{\mathcal{N}}}(0,1)\).

11.2.3.1 Part (a).

It suffices to show the difference is vanishing, \[\begin{align} &\sum_{t=1}^T \zeta_{T,t} - \frac{\widehat{Q}^C_T(\pi) - Q(\pi)}{\sqrt{V^C_T(\pi) }} \stackrel{\Delta}{=} \sum_x \delta(x),\quad where\\ & \delta(x) = \frac{\sum_{t=1}^T h_t(x)(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x) }{ \sqrt{V^C_T(\pi) }\sum_{t=1}^T \mathbb{E}_{}\left[{h_t(x)}\right] } \left({1-\frac{\sum_{t=1}^T \mathbb{E}_{}\left[{h_t(x)}\right] }{\sum_{t=1}^T h_t(x) } }\right). \end{align}\] We have \[\begin{align} |\delta(x)| &\stackrel{(i)}{\lesssim} \left| \frac{\sum_{t=1}^T h_t(x)(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x) }{ \sqrt{\sum_y \alpha^2_T(y)} \sum_{t=1}^T \mathbb{E}_{}\left[{h_t(x)}\right] }\right| \cdot\left|1-\frac{\sum_{t=1}^T \mathbb{E}_{}\left[{h_t(x)}\right] }{\sum_{t=1}^T h_t(x)} \right|\\ &\leq \left|\frac{\sum_{t=1}^T h_t(x)(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\widehat{\Gamma}_t(x, \pi) - P_xQ_x) }{ \sqrt{ \alpha^2_T(x)} \sum_{t=1}^T \mathbb{E}_{}\left[{h_t(x)}\right] }\right|\cdot \left|1-\frac{\sum_{t=1}^T \mathbb{E}_{}\left[{h_t(x)}\right] }{\sum_{t=1}^T h_t(x) } \right|\\ & = \left| \sum_{t=1}^T \eta_{T,t}(x)\right|\cdot \left|1-\frac{\sum_{t=1}^T \mathbb{E}_{}\left[{h_t(x)}\right] }{\sum_{t=1}^T h_t(x) } \right|\xrightarrow{p}0, \end{align}\] where in (i), we use that \(V_T^C=\mathop{\mathrm{\mathbb{E}}}[A_T-B_T]]\gtrsim \mathop{\mathrm{\mathbb{E}}}[A_T]=\sum_{y}\alpha_T^2(y)\) (where \(A_T, B_T\) defined in 60 ); and in the last convergence statement, we use the fact that \(\sum_{t=1}^T \eta_{T,t}(x)\) is asymptotically normal and thus \(O_p(1)\), and that with StableVar weights \(\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[h_t(x)] / \sum_{t=1}^T h_t(x) \xrightarrow{p}1\) by Lemma 2. Together we have \(\delta(x)\) is vanishing.

11.2.3.2 Part (b).

It suffices to show that the variance estimator converges to its expectation: \(\widehat{V}_T^C/{V}_T^C \xrightarrow{p}1\). Expanding the definitions of \(\widehat{V}_T^C\) and \({V}_T^C\), we have \[\begin{align} \widehat{V}_T^C(\pi) =& \sum_x \underbracket[0.4pt]{ \frac{\sum_{t=1}^T h_t^2(x)\big(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\hat{\Gamma}_t(x, \pi) - (\widehat{P_x Q_x})_T\big)^2 }{\big(\sum_{t=1}^Th_t(x)\big)^2}}_{\widehat{I}(x)} +\sum_{x\neq y} \underbracket[0.4pt]{\frac{\sum_{t=1}^T h_t(x)h_t(y) (\widehat{P_x Q_x})_T(\widehat{P_y Q_y})_T }{ \big(\sum_{t=1}^T h_t(x))\big(\sum_{t=1}^Th_t(y) ) }}_{\widehat{II_a}(x,y)} \\ &\quad -\sum_{x\neq y} \underbracket[0.4pt]{\frac{ \sum_{t=1}^T h_t(x)h_t(y) \mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\hat{\Gamma}_t(x, \pi) (\widehat{P_y Q_y})_T }{ \big(\sum_{t=1}^T h_t(x)\big)\big( \sum_{t=1}^Th_t(y)\big) } }_{\widehat{II_b}(x,y)} -\sum_{x\neq y}\underbracket[0.4pt]{ \frac{ \sum_{t=1}^T h_t(x)h_t(y) \mathop{\mathrm{\mathbb{I}}}\{X_t=y\}\hat{\Gamma}_t(x, \pi) (\widehat{P_x Q_x})_T }{ \big(\sum_{t=1}^T h_t(x)\big)\big( \sum_{t=1}^Th_t(y)\big) } }_{\widehat{II_c}(x,y)}.\\ V_T^C(x, \pi) =&\sum_x \underbracket[0.4pt]{ \frac{\sum_{t=1}^T\mathbb{E}_{}\left[{ h_t^2(x)\big(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\hat{\Gamma}_t(x, \pi) - P_xQ_x\big)^2 }\right]}{\mathbb{E}_{}\left[{\sum_{t=1}^Th_t(x)}\right]^2}}_{I(x)} - \sum_{x\neq y}\underbracket[0.4pt]{\frac{\sum_{t=1}^T \mathbb{E}_{}\left[{h_t(x)h_t(y)}\right]P_xQ_xP_y Q_y }{\big(\sum_{t=1}^T \mathbb{E}_{}\left[{h_t(x)}\right]\big)\left({ \sum_{t=1}^T\mathbb{E}_{}\left[{h_t(y)}\right] }\right)}}_{II(x,y)} \end{align}\] In fact, for any \(x,y\in \mathop{\mathrm{\mathcal{X}}}\), we have \(\frac{\widehat{I}(x)}{I(x)}, \frac{\widehat{II_a}(x,y)}{ II(x,y)}, \frac{\widehat{II_b}(x,y)}{II(x,y)}, \frac{\widehat{II_c}(x,y)}{II(x,y)}\) all converge to \(1\) in probability (to be shown shortly). Also, recall that \(\sum_x I(x) = \mathop{\mathrm{\mathbb{E}}}[A_T]\) and \(\sum_{x\neq y}II(x,y) = \mathop{\mathrm{\mathbb{E}}}[B_T]\) (where \(A_T, B_T\) are defined in 60 ); invoking Lemma 3 yields \(\widehat{V}_T^C/{V}_T^C \xrightarrow{p}1\).

We now show that \(\widehat{I}(x), \widehat{II_a}(x,y), \widehat{II_b}(x,y), \widehat{II_c}(x,y)\) converge to \(I(x), II(x,y), II(x,y), II(x,y)\) respectively.

• Show \(\widehat{I}(x) / I(x) \xrightarrow{p}1\). \[\begin{align} \frac{\widehat{I}(x)}{I(x)} = \frac{\sum_{t=1}^T h_t^2(x)\big(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\hat{\Gamma}_t(x,\pi) - (\widehat{P_x Q_x})_T\big)^2 }{\sum_{t=1}^T\mathbb{E}_{}\left[{ h_t^2(x)\big(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\hat{\Gamma}_t(x,\pi) - P_xQ_x\big)^2 }\right]} \frac{\mathbb{E}_{}\left[{\sum_{t=1}^Th_t(x)}\right]^2}{\big(\sum_{t=1}^Th_t(x)\big)^2} . \end{align}\] For StableVar weights, by Lemma 2, \(\frac{\mathbb{E}_{}\left[{\sum_{t=1}^Th_t(x)}\right]^2}{\big(\sum_{t=1}^Th_t(x)\big)^2} \xrightarrow{p}1\). On the other hand, following the same steps as in Appendix 10.3, one can show that \[\begin{align} \label{eq:x95var95consistent} \frac{\sum_{t=1}^T h_t^2(x)\big(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\hat{\Gamma}_t(x, \pi) - (\widehat{P_x Q_x})_T\big)^2 }{\sum_{t=1}^T\mathbb{E}_{}\left[{ h_t^2(x)\big(\mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\hat{\Gamma}_t(x, \pi) - P_xQ_x\big)^2 }\right]}\xrightarrow{p}1, \end{align}\tag{62}\] by observing that \((\widehat{P_x Q_x})_T\) is consistent to \(P_xQ_x\) (shown in Appendix 11.1), and that \(\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[\eta_{T,t}^2|H_{t-1}]\xrightarrow{L_1}1\), \(\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[\eta_{T,t}^4|H_{t-1}]\xrightarrow{a.s.}0\); we defer the proof to later text.

• Show \(\widehat{II_a}(x,y) / II(x,y)\xrightarrow{p}1\). By Lemma 2, with StableVar weights, we have \[\begin{align} \frac{ \sum_{t=1}^{T}h_t(x)}{ \sum_{t=1}^{T}\mathop{\mathrm{\mathbb{E}}}[h_t(x) ] } \xrightarrow{p}1,\quad \frac{ \sum_{t=1}^{T}h_t(x)h_t(y) }{ \sum_{t=1}^{T}\mathop{\mathrm{\mathbb{E}}}[h_t(x)h_t(y) ] } \xrightarrow{p}1. \end{align}\] Meanwhile, \((\widehat{P_x Q_x})_T, (\widehat{P_y Q_y})_T\) are consistent for \(P_xQ_x, P_y Q_y\) respectively, yielding the desired result.

• Show \(\widehat{II_b}(x,y) / II(x,y)\xrightarrow{p}1\). We have \[\begin{align} \frac{\widehat{II_b}(x,y) }{II(x,y)} &= \frac{ \sum_{t=1}^T h_t(x)h_t(y) \mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\hat{\Gamma}_t(x, \pi) (\widehat{P_y Q_y})_T }{ \big(\sum_{t=1}^T h_t(x)\big)\big( \sum_{t=1}^Th_t(y)\big) } \Big / \frac{\sum_{t=1}^T \mathbb{E}_{}\left[{h_t(x)h_t(y)}\right]P_xQ_xP_y Q_y }{\big(\sum_{t=1}^T \mathbb{E}_{}\left[{h_t(x)}\right]\big)\left({ \sum_{t=1}^T\mathbb{E}_{}\left[{h_t(y)}\right] }\right)} \\ & = \frac{\sum_{t=1}^T\mathbb{E}_{}\left[{h_t(x)}\right]}{\sum_{t=1}^Th_t(y)} \cdot \frac{\sum_{t=1}^T\mathbb{E}_{}\left[{h_t(y)}\right]}{\sum_{t=1}^Th_t(y)} \cdot \frac{ (\widehat{P_y Q_y})_T }{P_y Q_y} \cdot \frac{\sum_{t=1}^Th_t(x)h_t(y)}{\sum_{t=1}^T \mathop{\mathrm{\mathbb{E}}}[h_t(x)h_t(y)]}\\ &\quad \quad \times \frac{ \sum_{t=1}^T h_t(x)h_t(y) \mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\hat{\Gamma}_t(x, \pi) }{\sum_{t=1}^T h_t(x)h_t(y)} \Big/ \Big(P_xQ_x \Big). \end{align}\] We claim that \[\label{eq:cross95weights95consistency} \frac{ \sum_{t=1}^T h_t(x)h_t(y) \mathop{\mathrm{\mathbb{I}}}\{X_t=x\}\hat{\Gamma}_t(x, \pi) }{\sum_{t=1}^T h_t(x)h_t(y)}\xrightarrow{p} P_xQ_x,\tag{63}\] which concludes \(\widehat{II_b}(x,y) / II(x,y)\xrightarrow{p}1\). We defer the proof of 63 to later text.

• Show \(\widehat{II_c}(x,y) / II(x,y) \xrightarrow{p}1\), which holds by the same argument applied to showing \(\widehat{II_b}(x,y) / II(x,y) \xrightarrow{p}1\) above.

12 Classification dataset↩︎

The full list of the \(86\) datasets from OpenML [29] is:

 CreditCardSubset, 
 GAMETES_Epistasis_2-Way_20atts_0_4H_EDM-1_1,
 GAMETES_Heterogeneity_20atts_1600_Het_0_4_0_2_75_EDM-2_001, 
 LEV, Long, MagicTelescope, PhishingWebsites, PizzaCutter3, 
 SPECT, Satellite, abalone, allrep, artificial-characters, 
 autoUniv-au1-1000, balance-scale, banknote-authentication,
 blood-transfusion-service-center, boston, 
 boston_corrected, car, cardiotocography, chatfield_4, 
 chscase_census2, chscase_census6,
 cmc, coil2000, collins, credit-g, delta_ailerons, diabetes, dis,
 disclosure_x_noise, eeg-eye-state, eye_movements, fri_c0_1000_5,
 fri_c1_1000_25, fri_c1_1000_5, fri_c1_250_10, fri_c1_500_10,
 fri_c1_500_25, fri_c2_1000_25, fri_c2_1000_50, fri_c3_1000_25,
 fri_c3_250_10, fri_c3_250_5, fri_c3_500_5, fri_c4_1000_50, 
 haberman, heart-statlog, houses, ionosphere, 
 jEdit_4_2_4_3, jungle_chess_2pcs_endgame_elephant_elephant,
 jungle_chess_2pcs_endgame_panther_lion, kc3, kr-vs-kp, 
 mammography, mfeat-morphological, monks-problems-1, 
 monks-problems-2, monks-problems-3, nursery, oil_spill, 
 ozone_level, page-blocks, plasma_retinol, prnn_fglass, 
 qualitative-bankruptcy, ringnorm, rmftsa_sleepdata, 
 segment, solar-flare, spambase, splice, threeOf9,
 tic-tac-toe, vertebra-column, volcanoes-a1, 
 volcanoes-a2, volcanoes-b3, volcanoes-d4, volcanoes-e5, 
 wdbc, wilt, xd6, yeast

References↩︎

---

1. Institute for Computational and Mathematical Engineering, Stanford University.↩︎

2. Graduate School of Business, Stanford University.↩︎

3. This paper has been accepted in the Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD ’21) on May 17, 2021. The published version includes a short appendix with sketches of the proofs, while the appendix in this version includes complete proofs.↩︎

4. We do, however, permit the assignment probability \(e_t(x,w)\) to decay to zero as \(t\) grows. This is typically what happens in bandit experiments when treatment \(w\) is, on average, suboptimal for individuals with context \(x\).↩︎

5. Reproduction code can be found at https://github.com/gsbDBI/contextual_bandits_evaluation.↩︎