# accurate_inference_for_adaptive_linear_models__3bf7a1e4.pdf

Accurate Inference for Adaptive Linear Models

Yash Deshpande 1 Lester Mackey 2 Vasilis Syrgkanis 2 Matt Taddy 2 3

Estimators computed from adaptively collected data do not behave like their non-adaptive brethren. Rather, the sequential dependence of the collection policy can lead to severe distributional biases that persist even in the infinite data limit. We develop a general method W - decorrelation for transforming the bias of adaptive linear regression estimators into variance. The method uses only coarse-grained information about the data collection policy and does not need access to propensity scores or exact knowledge of the policy. We bound the finite-sample bias and variance of the W -estimator and develop asymptotically correct confidence intervals based on a novel martingale central limit theorem. We then demonstrate the empirical benefits of the generic W -decorrelation procedure in two different adaptive data settings: the multi-armed bandit and the autoregressive time series.

1. Introduction

Consider a dataset of n sample points (yi, xi)i n where yi represents an observed outcome and xi Rp an associated vector of covariates. In the standard linear model, the outcomes and covariates are related through a parameter β:

yi = xi, β + εi. (1)

In this model, the noise term εi represents inherent variation in the sample, or the variation that is not captured in the model. Parametric models of the type (1) are a fundamental building block in many machine learning problems. A common additional assumption is that the covariate vector xi for a given datapoint i is independent of the other sample point outcomes (yj)j =i and the inherent variation (εj)j [n]. This paper is motivated by experiments where

1Department of Mathematics, MIT 2Microsoft Research New England 3Booth School of Business, University of Chicago. Correspondence to: Yash Deshpande <yash@mit.edu>.

Proceedings of the 35 th International Conference on Machine Learning, Stockholm, Sweden, PMLR 80, 2018. Copyright 2018 by the author(s).

the sample (yi, xi)i n is not completely randomized but rather adaptively chosen. By adaptive, we mean that the choice of the data point (yi, xi) is guided from inferences on past data (yj, xj)j<i. Consider the following sequential paradigms:

1. Multi-armed bandits: This class of sequential decision making problems captures the classical exploration versus exploitation tradeoff. At each time i, the experimenter chooses an action xi from a set of available actions X and accrues a reward R(yi) where (yi, xi) follow the model (1). Here the experimenter must balance the conflicting goals of learning about the underlying model (i.e., β) for better future rewards, while still accruing reward in the current time step.

2. Active learning: Acquiring labels yi is potentially costly, and the experimenter aims to learn with as few outcomes as possible. At time i, based on prior data (yj, xj)j i 1 the experimenter chooses a new data point xi to label based on its value in learning.

3. Time series analysis: Here, the data points (yi, xi) are naturally ordered in time, with (yi)i n denoting a time series and the covariates xi include observations from the prior time points.

Here, time induces a natural sequential dependence across the samples. In the first two instances, the actions or policy of the experimenter are responsible for creating such dependence. In the case of time series data, this dependence is endogenous and a consequence of the modeling. A common feature, however, is that the choice of the design or sequence (xi)i n is typically not made for inference on the model after the data collection is completed. This does not, of course, imply that accurate estimates on the parameters β cannot be made from the data. Indeed, it is often the case that the sample is informative enough to extract consistent estimators of the underlying parameters. Indeed, this is often crucial to the success of the experimenter s policy. For instance, regret in sequential decision-making or risk in active learning are intimately connected with the accurate estimation of the underlying parameters (Castro & Nowak, 2008; Audibert & Bubeck, 2009; Bubeck et al., 2012; Rusmevichientong & Tsitsiklis, 2010) . Our motivation is the

Accurate Inference for Adaptive Linear Models

natural follow-up question of accurate ex post inference in the standard statistical sense:

Can adaptive data be used to compute accurate confidence regions and p-values?

As we will see, the key challenge is that even in the simple linear model of (1), the distribution of classical estimators can differ from the predicted central limit behavior of nonadaptive designs. In this context we make the following contributions:

Decorrelated estimators: We present a general method to decorrelate arbitrary estimators bβ(y, Xn) constructed from the data. This construction admits a simple decomposition into a bias and variance term. In comparison with competing methods, like propensity weighting, our proposal requires little explicit information about the data-collection policy.

Bias and variance control: Under a natural exploration condition on the data collection policy, we establish that the bias and variance can be controlled at nearly optimal levels. In the multi-armed bandit setting, we prove this under an especially weak averaged exploration condition.

Asymptotic normality and inference: We establish a martingale central limit theorem (CLT) under a moment stability assumption. Applied to our decorrelated estimators, this allows us to construct confidence intervals and conduct hypothesis tests in the usual fashion.

Validation: We demonstrate the usefulness of the decorrelating construction in two different scenarios: multi-armed bandits (MAB) and autoregressive (AR) time series. We observe that our decorrelated estimators retain expected central limit behavior in regimes where the standard estimators do not, thereby facilitating accurate inference.

The rest of the paper is organized with our main results in Section 2, discussion of related work in Section 3, and experiments in Section 4. Due to page constraints, all proofs are given in Appendix A in the supplementary information.

2. Main results: W -decorrelation

We focus on the linear model and assume that the data pairs (yi, xi) satisfy:

yi = xi, β + εi, (2)

where εi are independent and identically distributed random variables with E{εi} = 0, E{ε2 i } = σ2 and bounded third moment. We assume that the samples are ordered naturally in time and let {Fi}i 0 denote the filtration representing increasing information in the sample. Formally, we let data points (yi, xi) be adapted to this filtration, i.e. (yi, xi) are measurable with respect to Fj for all j i.

Our goal in this paper is to use the available data to construct ex post confidence intervals and p-values for individual parameters, i.e. entries of β. A natural starting point is to consider is the standard least squares estimate:

bβOLS = (XT n Xn) 1XT nyn,

where Xn = [x T 1 , . . . x T n] Rn p is the design matrix and yn = [y1, . . . yn] Rn. When data collection is non-adaptive, classical results imply that the standard least squares estimate bβOLS is distributed asymptotically as N(β, σ2(XT n Xn) 1), where N(µ, Σ) denotes the Gaussian distribution with mean µ and covariance Σ. Lai & Wei (1982) extend these results to the current scenario: Theorem 1 (Theorems 1, 3 (Lai & Wei, 1982)). Let λmin(n) (λmax(n)) denote the minimum (resp. maximum) eigenvalue of XT n Xn. Under the model (2), assume that (i) εi have finite third moment and (ii) almost surely, λmin(n) with λmin = Ω(log λmax) and (iii) log λmax = o(n). Then the following limits hold almost surely:

bβOLS β 2 2 C σ2p log λmax

λmin | 1 nσ2 yn Xn bβOLS 2 2 1| C(p) 1+log λmax

Further assume the following stability condition: there exists a deterministic sequence of matrices An such that (iii) A 1 n (Xn TXn)1/2 Ip and (iv) maxi A 1 n xi 2 0 in probability. Then,

(XT n Xn)1/2(bβOLS β) d N(0, σ2Ip).

At first blush, this allows to construct confidence regions in the usual way. More precisely, the result implies that bσ2 = yn Xn bβOLS 2 2/n is a consistent estimate of the noise variance. Therefore, the interval [bβOLS,1 1.96bσ(XT n Xn) 1 11 , bβOLS,1 + 1.96bσ(XT n Xn) 1 11 ] is a 95% two-sided confidence interval for the first coordinate β1. Indeed, this result is sufficient for a variety of scenarios with weak dependence across samples, such as when the (yi, xi) form a Markov chain that mixes rapidly. However, while the assumptions for consistency are minimal, the additional stability assumption required for asymptotic normality poses some challenges. In particular:

1. The stability condition can provably fail to hold for scenarios where the dependence across samples is

Accurate Inference for Adaptive Linear Models

non-negligible. This is not a weakness of Theorem 1: the CLT need not hold for the OLS estimator (Lai & Wei, 1982; Lai & Siegmund, 1983).

2. The rate of convergence to the asymptotic CLT depends on the quantitative rate of the stability condition. In other words, variability in the inverse covariance XT n Xn can cause deviations from normality of OLS estimator (Dvoretzky, 1972). In finite samples, this can manifest itself in the bias of the OLS estimator as well as in higher moments.

An example of this phenomenon is the standard multiarmed bandit problem (Lai & Robbins, 1985). At each time point i n, the experimenter (or data collecting policy) chooses an arm k {1, 2, . . . , p} and observes a reward yi with mean βk. With β Rp denoting the mean rewards, this falls within the scope of model (2), where the vector xi takes the value ek (the kth basis vector), if the kth

arm or option is chosen at time i.1 Other stochastic bandit problems with covariates such as contextual or linear bandits (Rusmevichientong & Tsitsiklis, 2010; Li et al., 2010; Deshpande & Montanari, 2012) can also be incorporated fairly naturally into our framework. For the purposes of this paper, however, we restrict ourselves to the simple case of multi-armed bandits without covariates. In this setting, ordinary least squares estimates correspond to computing sample means for each arm. The stability condition of Theorem 1 requires that Nk(n), the number of times a specific arm k [p] is sampled is asymptotically deterministic as n grows large. This is true for certain regret-optimal algorithms (Russo, 2016; Garivier & Capp e, 2011). Indeed, for such algorithms, as the sample size n grows large, the suboptimal arm is sampled Nk(n) Ck(β) log n for a constant Ck(β) that depends on β and the distribution of noise εi. However, in finite samples, the dependence on Ck(β) and the slow convergence rate of (log n) 1/2 lead to significant deviation from the expected central limit behavior.

Villar et al. (2015) studied a variety of multi-armed bandit algorithms in the context of clinical trials. They empirically demonstrate that sample mean estimates from data collected using many standard multi-armed bandit algorithms are biased. Recently, (Nie et al., 2017) proved that this bias is negative for Thompson sampling and UCB. The presence of bias in sample means demonstrates that standard methods for inference, as advocated by Theorem 1, can be misleading when the same data is now used for inference. As a pertinent example, testing the hypotheses the mean reward of arm 1 exceeds that of 2 based on classical theory can be significantly affected by adaptive data

1Strictly speaking, the model (2) assumes that the errors have the same variance, which need not be true for the multi-armed bandit as discussed. We focus on the homoscedastic case where the errors have the same variance in this paper.

collection.

The papers (Villar et al., 2015; Nie et al., 2017) focus on the finite sample effect of the data collection policy on the bias and suggest methods to reduce the bias. It is not hard to find examples where higher moments or tails of the distribution can be influenced by the data collecting policy. A simple, yet striking, example is the standard autoregressive model (AR) for time series data. In its simplest form, the AR model has one covariate, i.e. p = 1 with xi = yi 1. In this case:

yi = βyi 1 + εi.

Here the least squares estimate is given by bβOLS = P

i n 1 yi+1yi/ P

i n 1 y2 i 1. When |β| is bounded away from 1, the series is asymptotically stationary and the OLS estimate has Gaussian tails. On the other hand, when β 1 is on the order of 1/n the limiting distribution of the least squares estimate is non-Gaussian and dependent on the gap β 1 (cf. (Chan & Wei, 1987)). A histogram for the OLS errors in two cases: (i) stationary with β = 0.02 and (ii) (nearly) nonstationary with β = 0.9 is shown on the left in Figure 1 where the large β example case is clearly non-Gaussian.

On the other hand, using the same data our decorrelating procedure is able to obtain estimates admitting Gaussian limit distributions, as evidenced in the right panel of Figure 1. We show a similar phenomenon in the MAB setting where our decorrelating procedure corrects for the unstable behavior of the OLS estimator (see Section 4 for details on the empirics). Delegating discussion of further related work to 3, we now describe this procedure and its motivation.

2.1. Removing the effects of adaptivity

We propose to decorrelate the OLS estimator by constructing:

bβd = bβOLS + W n(y Xn bβOLS),

for a specific choice of a decorrelating or whitening matrix W n Rp n. This is inspired by the highdimensional linear regression debiasing constructions of (Zhang & Zhang, 2014; Javanmard & Montanari, 2014b;a; Van de Geer et al., 2014). As we will see, this construction is useful also in the present regime where we keep p fixed and n p. By rearranging:

bβd β = (Ip W n Xn)(bβOLS β) + W nεn b + v.

We interpret b as a bias and v as a variance . This is based on the following critical constraint on the construction of the whitening matrix W n:

Accurate Inference for Adaptive Linear Models

Figure 1. The distribution of errors for (left) the OLS estimator for stationary and (nearly) nonstationary AR(1) time series and (right) error distribution for both models after decorrelation. n = 50, εi N(0, 1).

Definition 1 (Well-adaptedness of W n). Without loss of generality, we assume that εi are adapted to Fi. Let Gi Fi be a filtration such that xi are adapted w.r.t. Gi and εi is independent of Gi. We say that Wn is well-adapted if the columns of W n are adapted to Gi, i.e. the ith column wi is measurable with respect to Gi.

With this in hand, we have the following simple lemma. Lemma 2. Assume W n is well-adapted. Then:

β E{bβd} 2 E{ b 2},

Var(v) = σ2E{W n W T n}.

A concrete proposal is to trade-off the bias, controlled by the size of Ip W n Xn, with the the variance which appears through W n W T n. This leads to the following optimization problem:

W n = arg min W Ip W Xn 2 F + λTr(W W T). (3)

Solving the above in closed form yields ridge estimators for β, and by continuity, also the standard least squares estimator. Departing from (Zhang & Zhang, 2014; Javanmard & Montanari, 2014a), we solve the above in an online fashion in order to obtain a well-adapted W n. We define, W 0 = 0, X0 = 0, and recursively W n = [W n 1wn] for

wn = arg min w Rp I W n 1Xn 1 wx T n 2 F + λ w 2 2 .

As in the case of the offline optimization, we may obtain closed form formulae for the columns wi (see Algorithm 1). The method as specified requires O(np2) additional computational overhead, which is typically minimal compared to computing bβOLS or a regularized version like the ridge or lasso estimate. We refer to bβd as a W -estimate or a W -decorrelated estimate.

2.2. Interpretation as reverse implicit SGD

While we motivated W -decorrelation decorrelation as an online procedure for optimizing the bias-variance trade-

off objective (3), it holds a dual interpretation as implicit stochastic gradient descent (SGD) (see, e.g., Kulis & Bartlett, 2010), also known as incremental proximal minimization (Bertsekas, 2011) or the normalized least mean squares filter (Nagumo & Noda, 1967) in this context, with step-size λ applied to the least-squares objective, 1 n Pn i=1(yi β, xi )2. Importantly, to obtain the well-adapted form of our updates, one must apply implicit SGD in reverse, starting with the final observation (yn, xn) and ending with the initial observation (y1, x1); this recipe yields the parameter updates bβ0 = bβOLS and

bβi+1 = bβi + xn i(yn i xn i, bβi+1 )/λ

= (Ip + xn ix T n i/λ) 1(bβi + yn ixn i/λ)

= (Ip xn ix T n i/(λ + xn i 2 2))bβi

+ yn ixn i/(λ + xn i 2 2).

Unrolling the recursion, we obtain bβn = bβOLS + Pn i=1 yiwi with each wi precisely as in Algorithm 1:

wi = Qn j=1(Ip xjx T j /(λ + xj 2 2)).

2.3. Bias and variance

We now examine the bias and variance control for bβd. We first begin with a general bound for the variance:

Theorem 3 (Variance control). For any λ 1 set nonadaptively, we have that

Tr{Var(v)} σ2

λ (p E{ Ip W n Xn 2 F }).

In particular, Tr{Var(v)} σ2p/λ. Further, if xi 2 2 C for all i:

Tr{Var(v)} σ2

λ (p E{ Ip W n Xn 2 F }).

This theorem suggests that one must set λ as large as possible to minimize the variance. While this is accurate, one

Accurate Inference for Adaptive Linear Models

must take into account the bias of bβd and its dependence on the regularization λ. Indeed, for large λ, one would expect that Ip W n Xn Ip, which would not help control the bias. In general, one would hope to set λ, thereby determining bβd, at a level where its bias is negligible in comparison to the variance. The following theorem formalizes this:

Theorem 4 (Variance dominates MSE). Recall that the matrix W n is a function of λ. Suppose that there exists a deterministic sequence λ(n) such that:

E{ Ip W n Xn 2 op} = o(1/ log n), (4)

P{λmin(Xn XT n) λ(n) log n} 1/n, (5)

Then we have

E{ b 2 2} Tr{Var(v)} = o(1).

The conditions of Theorem 4, in particular the bias condition on Ip W n Xn are quite general. In the following proposition, we verify some sufficient conditions under which the premise of Theorem 4 hold.

Proposition 5. Either of the following conditions suffices for the requirements of Theorem 4.

1. The data collection policy satisfies for some sequence µn(i) and for all λ 1:

E{ xix T i λ+ xn 2 2 |Gi 1} µn(i)

λ Ip, (6) P

i µn(i) n µn K n, (7)

for a large enough constant K. Here we keep λ(n) n µn/ log n.

2. The matrices (xix T i )i n commute and λ(n) log n is (at most) the 1/nth percentile of λmin(XT n Xn).

It is useful to consider the intuition for the sufficient conditions given in Proposition 5. By Lemma 2, note that the bias is controlled by I W n Xn op, which increases with λ. Consider a case in which the samples xi lie in a strict subspace of Rp. In this case, controlling the bias uniformly over β Rp is now impossible regardless of the choice of W n. For example, in a multi-armed bandit problem, if the policy does not sample a specific arm, there is no information available about the reward distribution of that arm. Proposition 5 the intuition that the data collecting policy should explore the full parameter space. For multi-armed bandits, policies such as epsilon-greedy and Thompson sampling satisfy this assumption with appropriate µn(i).

Given sufficient exploration, Proposition 5 recommends a reasonable value to set for the regularization parameter. In

Algorithm 1 W -Decorrelation Method Input: sample (yi, xi)i n, regularization λ, unit vector v Rp, confidence level α (0, 1), noise estimate ˆσ2. Compute: bβOLS = (XT n Xn) 1Xnyn. Setting W 0 = 0, compute W i = [W i 1wi] with wi = (Ip W i 1XT i )xi/(λ + xi 2 2), for i = 1, 2, . . . , n. Compute bβd = bβOLS + W n(y Xn bβOLS) and ˆσ(v) = ˆσ v, W n W T nv 1/2

Output: decorrelated estimate bβd and CI interval I(v, α) = [ v, bβd ˆσ(v)Φ 1(1 α), v, bβd + ˆσ(v)Φ 1(1 α)].

particular setting λ to a value such that λ λmin occurs with high probability suffices to ensure that the W - decorrelated estimate is approximately unbiased. Correspondingly, the MSE (or equivalently variance) of the W - decorrelated estimate need not be smaller than that of the original OLS estimate. Indeed the variance scales as 1/λ, which exceeds with high probability the 1/λmin scaling for the MSE. This is the cost paid for debiasing OLS estimate.

Before we move to the inference results, note that the procedure requires only access to high probability lower bounds on λmin, which intuitively quantifies the exploration of the data collection policy. In comparison with methods such as propensity score weighting or conditional likelihood optimization, this represents rather coarse information about the data collection process. In particular, given access to propensity scores or conditional likelihoods one can simulate the process to extract appropriate values for the regularization λ(n). This is the approach we take in the experiments of Section 4. Moreover, propensity scores or conditional likelihoods are ineffective when data collection policies make adaptive decisions that are deterministic given the history. A important example is that of UCB algorithms for bandits, which make deterministic choices of arms.

2.4. A central limit theorem and confidence intervals

Our final result is a simple CLT that provides an alternative to the stability condition of Theorem 1 and standard martingale CLTs.2 We state it for martingales of the form of P

i wiεi, as required, but a form for general martingales also holds true. Define, for any vector t Rp, the conditional variance σi(t) P

j i wj, t 2. We make the following crucial moment stability assumption on the conditional covariance:

2Many standard martingale CLTs (see, e.g., Lai & Wei, 1982; Dvoretzky, 1972) demand the convergence of P

i wiw T i /n to a constant, but this convergence condition is violated in many examples of interest, including the AR examples in Section 4.

Accurate Inference for Adaptive Linear Models

Assumption 1. For a = 1, 2, and positive integer k

sup t 2 1 Pm(n) i=1 E{|E{εa i σm(t)k|Fi 1}

E{εa i |Fi 1}E{σm(t)k}|Fi 1}|} = on(1).

Theorem 6 (Martingale CLT). Let (wi(n), εi(n), Fi(n))i m(n) be a triangular martingale difference array. Here for each n 1, Fi(n) is a non-decreasing sequence of sub-sigma-algebras, εi(n) are i.i.d. (uniformly) bounded random variables with E{εi|Fi 1} = 0, E{ε2 i |Fi 1} = 1 and wi m Fi 1 is predictable and bounded by 1 almost surely. Suppose a Lyapunov condition holds, i.e. P

i E{w3 i } = on(1). Then

i wiw T i ) 1/2 P

i wiεi d N(0, σ2Ip). In particular, for any bounded, continuous ϕ : Rp R

lim n E n ϕ X

i wiεi ϕ σ h X

i wiw T i i1/2 ξ o = 0,

where ξ N(0, Ip) is independent of P

i wiw T i .

The assumptions on ε are made for simplicity of proof, which uses the usual Fourier-analytic approach to prove the central limit theorem (Billingsley, 2008). These can be relaxed significantly to standard third moment assumptions as in a Lyapunov CLT. Assumption 1 is an alternate form of stability. It controls the dependence of the conditional covariance of P

i wiεi on the first two conditional moments of the martingale increments εi. In words, it states that conditioning on the conditional covariance P

i wiw T i does not change the first two moments of the random variables εi by much. In particular, this holds given a quantitative version of the stability condition of (Lai & Wei, 1982; Dvoretzky, 1972). We have the following

Lemma 7. Consider a martingale sequence P

i wiεi as in Theorem 6. If a non-random sequence An satisfies A 1 n P

i wiw T i Ip = o(n 1/2), then Assumption 1 holds.

With a CLT in hand, one can now assign confidence intervals in the standard fashion, based on the assumption that the bias is negligible. For instance, we have the following result on two-sided confidence intervals.

Proposition 8. Fix any α > 0. Suppose that the data collection process satisfies the assumptions of Theorems 4 and 6. Set λ = λ(n) as in Theorem 4, and let bσ be a consistent estimate of σ as in Theorem 1. Define Q = bσ2W n W T n and the interval I(a, α) = [bβd a QaaΦ 1(1 α/2), bβd a+ QaaΦ 1(1 α/2). Then

lim supn P{βa I(a, α)} α.

3. Related work

There is extensive work in statistics and econometrics on stochastic regression models (Wei, 1985; Lai, 1994; Chen

et al., 1999; Heyde, 2008) and non-stationary time series (Shumway & Stoffer, 2006; Enders, 2008; Phillips & Perron, 1988). This line of work is analogous to Theorem 1 or restricted to specific time series models. We instead focus on literature from sequential decision-making, policy learning and causal inference that closely resembles our work in terms of goals, techniques and applicability.

The seminal work of Lai and Robbins (Robbins, 1985; Lai & Robbins, 1985) has spurred a vast literature on multi-armed bandit problems and sequential experiments that propose allocation algorithms based on confidence bounds (see (Bubeck et al., 2012) and references therein). A variety of confidence bounds and corresponding rules have been proposed (Auer, 2002; Dani et al., 2008; Rusmevichientong & Tsitsiklis, 2010; Abbasi-Yadkori et al., 2011; Jamieson et al., 2014) based on martingale concentration and the law of iterated logarithm. While these results can certainly be used to compute valid confidence intervals, they are conservative for a few reasons. First, they do not explicitly account for bias in OLS estimates and, correspondingly, must be wider to account for it. Second, obtaining optimal constants in the concentration inequalities can require sophisticated tools even for non-adaptive data (Ledoux, 1996; 2005). This is evidenced in all of our experiments which show that concentration inequalities yield valid, but conservative intervals.

A closely-related line of work is that of learning from logged data (Li et al., 2011; Dud ık et al., 2011; Swaminathan & Joachims, 2015) and policy learning (Athey & Wager, 2017; Kallus, 2017). The focus here is efficiently estimating the reward (or value) of a certain test policy using data collected from a different policy. For linear models, this reduces to accurate prediction which is directly related to the estimation error on the parameters β. While our work shares some features, we focus on unbiased estimation of the parameters and obtaining accurate confidence intervals for linear functions of the parameters. Some of the work on learning from logged data also builds on propensity scores and their estimation (Imbens, 2000; Lunceford & Davidian, 2004).

Villar et al. (2015) empirically demonstrate the presence of bias for a number of multi-armed bandit algorithms. Recent work by Dimakopoulou et al. (2017) also shows a similar effect in contextual bandits. Along with a result on the sign of the bias, (Nie et al., 2017) also propose conditional likelihood optimization methods to estimate parameters of the linear model. Through the lens of selective inference, they also propose methods to randomize the data collection process that simultaneously lower bias and reduce the MSE. Their techniques rely on considerable information about (and control over) the data generating process, in particular the probabilities of choosing a specific action at each

Accurate Inference for Adaptive Linear Models

Figure 2. Left: One-sided confidence region coverage for OLS and decorrelated W -decorrelated estimator trials. Right: Quantile-quantile (QQ) plots and empirical excess kurtosis (inset) for the OLS and W -decorrelated estimator errors

point in the data selection. This can be viewed as lying on the opposite end of the spectrum from our work, which attempts to use only the data at hand, along with coarse aggregate information on the exploration inherent in the data generating process. It is an interesting, and open, direction to consider approaches that can combine the strengths of our approach and that of (Nie et al., 2017).

4. Experiments

In this section we empirically validate the decorrelated estimators in two scenarios that involve sequential dependence in covariates. Our first scenario is a simple experiment of multi-armed bandits while the second scenario is autoregressive time series data. In these cases, we compare the empirical coverage and typical widths of confidence intervals for parameters obtained via three methods: (i) classical OLS theory, (ii) concentration inequalities and (iii) decorrelated estimates. Jupyter notebooks reproducing our experiments are available on the first author s Github (Deshpande et al., 2018).

4.1. Multi-armed bandits

In this section, we demonstrate the utility of the W - estimator for a stochastic multi-armed bandit setting. Vil-

lar et al. (2015) studied this problem in the context of patient allocation in clinical trials. Here the trial proceeds in a sequential fashion with the ith patient given one of p treatments, encoded as xi = ea with a [p], and yi denoting the outcome observed. We model the outcome as yi = xi, β + εi where εi Unif([ 1, 1]) with β being the mean outcome of the p treatments.

We sequentially assign one of p = 2 treatments to each of n = 444 patients using one of three policies (i) an εgreedy policy (called ECB or Epsilon Current Belief), (ii) a practical UCB strategy based on the law of iterated logarithm (UCB) (Jamieson et al., 2014) and (iii) Thompson sampling (Thompson, 1933). The ECB and TS sampling strategies are Bayesian. They place an independent Gaussian prior (with mean µ0 = 0.3 and variance σ2 0 = 0.33) on each unknown mean outcome parameter β = (0.3, 0.31) and form an updated posterior belief concerning β following each treatment administration xi and observation yi. For ECB, the treatment administered to patient i is, with probability 1 ε = .9, the treatment with the largest posterior mean; with probability 1 ε, a uniformly random treatment is administered instead, to ensure sufficient exploration of all treatments. Note that this strategy satisfies condition (6) with µn(i) = ε/p. For TS, at each patient i, a sample bβ of the mean treatment effect is drawn from the posterior belief. The treatment assigned to patient is the one maximizing the sampled mean treatment, i.e. a (i) = arg maxa [p] bβa. In UCB, the algorithm maintains a score for each arm a [p] that is a combination of the mean reward that the arm achieves and the empirical uncertainty of the reward. For each patient i, the UCB algorithm chooses the arm maximizing this score, and updates the score according to a fixed rule. For details on the specific implementation, see Jamieson et al. (2014). Our goal is to produce confidence intervals for the mean effect βa of each treatment based on the data adaptively collected from these standard bandit algorithms.

We repeat this simulation 4000 times. From each trial simulation, we estimate the parameters β using both OLS and the W -estimator with λ = ˆλ10%,π which is the 10th percentile of λmin(n) achieved by the policy π {ECB, UCB, TS}. This choice is guided by Corollary 4. We compare the quality of W -decorrelated estimator confidence regions, OLS Gaussian confidence regions (OLSgsn), and the OLS-based concentration inequality regions (OLSconc) (Abbasi-Yadkori et al., 2011, Sec. 4). Figure 2 (left column) shows that the OLS Gaussian have lower tail regions that typically overestimate coverage and upper tail regions that typically underestimate coverage. This is consistent with the observation that the sample means are biased negatively (Nie et al., 2017). The concentration OLS tail bounds are all conservative, producing nearly 100% coverage, irrespective of the nominal level. Meanwhile, the

Accurate Inference for Adaptive Linear Models

Figure 3. Mean 2-sided confidence interval widths (error bars show 1 standard deviation) for the 2 arms in the MAB experiment.

decorrelated intervals improves coverage uniformly over OLS intervals, often achieving the nominal coverage.

Figure 2 (right column) shows the QQ plots of OLS and W -estimator errors for each parameter βa. The distribution of OLS errors is distinctly non-Gaussian with considerable excess kurtosis for every policy. Conversely, for the W estimator the excess kurtosis is reduced for every policy by an order of magnitude (0 for ECB and UCB).

Figure 3 summarizes the distribution of 2-sided interval widths produced by each method for each arm. As expected, the W -decorrelation intervals are wider than those of OLSgsn but compare favorably with those provided by OLSconc. For UCB and for arm 0 for all policies, the mean OLSconc widths are always largest. For arm 1 in the ECB and TS policies, W -decorrelation yields smaller intervals than OLSconc for moderate confidence levels and larger for high confidence levels.

4.2. Autoregressive time series

In this section, we consider the classical AR(p) model where yi = P

ℓ p βℓyi ℓ+ εi.. We generate data for the model with parameters p = 2, n = 50, β = (0.95, 0.2), y0 = 0 and εi Unif([ 1, 1]); all estimates are computed over 4000 monte carlo iterations.

We plot the coverage confidences for various values of the nominal on the right panel of Figure 4. The QQ plot of the error distributions on the bottom right panel of Figure 4 shows that the OLS errors are skewed downwards, while the W -estimate errors are nearly Gaussian. We obtain the following improvements over the comparison methods of OLS standard errors OLSgsn and concentration inequality widths OLSconc (Abbasi-Yadkori et al., 2011)

The Gaussian OLS confidence regions systematically give incorrect empirical coverage. Meanwhile, the concentration inequalities provide very conservative intervals, with nearly 100% coverage, irrespective of the nominal level. In contrast, our decorrelated intervals achieve empirical coverage that closely approximates the nominal levels. These coverage improvements are enabled by an increase in width over that of OLSgsn, but the W -estimate widths are systematically smaller than those of the concentration inequalities.

Figure 4. Lower (Top left) and upper (Top right) coverage probabilities for OLS with Gaussian intervals, OLS with concentration inequality intervals and W -decorrelated estimate intervals. QQ plot with kurtosis inset (bottom right) errors in OLS estimate and W-decorrelated estimate. Mean confidence widths (bottom left) for OLS, concentration and W -decorrelated estimates. Error bars show one standard deviation.

Acknowledgements

Y.D would like to thank Adel Javanmard for feedback on an earlier draft of this paper.

Accurate Inference for Adaptive Linear Models

Abbasi-Yadkori, Y., P al, D., and Szepesv ari, C. Online least squares estimation with self-normalized processes: An application to bandit problems. ar Xiv preprint ar Xiv:1102.2670, 2011.

Athey, S. and Wager, S. Efficient policy learning. ar Xiv preprint ar Xiv:1702.02896, 2017.

Audibert, J.-Y. and Bubeck, S. Minimax policies for adversarial and stochastic bandits. In COLT, pp. 217 226, 2009.

Auer, P. Using confidence bounds for exploitationexploration trade-offs. Journal of Machine Learning Research, 3(Nov):397 422, 2002.

Bertsekas, D. P. Incremental proximal methods for large scale convex optimization. Mathematical programming, 129(2):163, 2011.

Billingsley, P. Probability and measure. John Wiley & Sons, 2008.

Bubeck, S., Cesa-Bianchi, N., et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends R in Machine Learning, 5(1):1 122, 2012.

Castro, R. M. and Nowak, R. D. Minimax bounds for active learning. IEEE Transactions on Information Theory, 54 (5):2339 2353, 2008.

Chan, N. H. and Wei, C.-Z. Asymptotic inference for nearly nonstationary ar (1) processes. The Annals of Statistics, pp. 1050 1063, 1987.

Chen, K., Hu, I., Ying, Z., et al. Strong consistency of maximum quasi-likelihood estimators in generalized linear models with fixed and adaptive designs. The Annals of Statistics, 27(4):1155 1163, 1999.

Dani, V., Hayes, T. P., and Kakade, S. M. Stochastic linear optimization under bandit feedback. In COLT, pp. 355 366, 2008.

Deshpande, Y. and Montanari, A. Linear bandits in high dimension and recommendation systems. In Communication, Control, and Computing (Allerton), 2012 50th Annual Allerton Conference on, pp. 1750 1754. IEEE, 2012.

Deshpande, Y., Mackey, L., Syrgkanis, V., and Taddy, M. Accurate inference for adaptive linear models, 2018. URL https://bit.ly/2m Jx ULg.

Dimakopoulou, M., Athey, S., and Imbens, G. Estimation considerations in contextual bandits. ar Xiv preprint ar Xiv:1711.07077, 2017.

Dud ık, M., Langford, J., and Li, L. Doubly robust policy evaluation and learning. ar Xiv preprint ar Xiv:1103.4601, 2011.

Dvoretzky, A. Asymptotic normality for sums of dependent random variables. In Proc. 6th Berkeley Symp. Math. Statist. Probab, volume 2, pp. 513 535, 1972.

Enders, W. Applied econometric time series. John Wiley & Sons, 2008.

Garivier, A. and Capp e, O. The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual Conference On Learning Theory, pp. 359 376, 2011.

Heyde, C. C. Quasi-likelihood and its application: a general approach to optimal parameter estimation. Springer Science & Business Media, 2008.

Imbens, G. W. The role of the propensity score in estimating dose-response functions. Biometrika, 87(3):706 710, 2000.

Jamieson, K., Malloy, M., Nowak, R., and Bubeck, S. lilucb: An optimal exploration algorithm for multiarmed bandits. In Conference on Learning Theory, pp. 423 439, 2014.

Javanmard, A. and Montanari, A. Confidence intervals and hypothesis testing for high-dimensional regression. Journal of Machine Learning Research, 15(1):2869 2909, 2014a.

Javanmard, A. and Montanari, A. Hypothesis testing in high-dimensional regression under the gaussian random design model: Asymptotic theory. IEEE Transactions on Information Theory, 60(10):6522 6554, 2014b.

Kallus, N. Balanced policy evaluation and learning. ar Xiv preprint ar Xiv:1705.07384, 2017.

Kulis, B. and Bartlett, P. L. Implicit online learning. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pp. 575 582, 2010.

Lai, T. and Siegmund, D. Fixed accuracy estimation of an autoregressive parameter. The Annals of Statistics, pp. 478 485, 1983.

Lai, T. L. Asymptotic properties of nonlinear least squares estimates in stochastic regression models. The Annals of Statistics, pp. 1917 1930, 1994.

Lai, T. L. and Robbins, H. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4 22, 1985.

Accurate Inference for Adaptive Linear Models

Lai, T. L. and Wei, C. Z. Least squares estimates in stochastic regression models with applications to identification and control of dynamic systems. The Annals of Statistics, pp. 154 166, 1982.

Ledoux, M. Isoperimetry and Gaussian analysis, volume 1648. Springer, Providence, 1996.

Ledoux, M. The concentration of measure phenomenon. Number 89. American Mathematical Soc., 2005.

Li, L., Chu, W., Langford, J., and Schapire, R. E. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661 670. ACM, 2010.

Li, L., Chu, W., Langford, J., and Wang, X. Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms. In Proceedings of the fourth ACM international conference on Web search and data mining, pp. 297 306. ACM, 2011.

Lunceford, J. K. and Davidian, M. Stratification and weighting via the propensity score in estimation of causal treatment effects: a comparative study. Statistics in medicine, 23(19):2937 2960, 2004.

Nagumo, J.-I. and Noda, A. A learning method for system identification. IEEE Transactions on Automatic Control, 12(3):282 287, 1967.

Nie, X., Xiaoying, T., Taylor, J., and Zou, J. Why adaptively collected data have negative bias and how to correct for it. 2017.

Phillips, P. C. and Perron, P. Testing for a unit root in time series regression. Biometrika, 75(2):335 346, 1988.

Robbins, H. Some aspects of the sequential design of experiments. In Herbert Robbins Selected Papers, pp. 169 177. Springer, 1985.

Rusmevichientong, P. and Tsitsiklis, J. N. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395 411, 2010.

Russo, D. Simple bayesian algorithms for best arm identification. In Conference on Learning Theory, pp. 1417 1418, 2016.

Shumway, R. H. and Stoffer, D. S. Time series analysis and its applications: with R examples. Springer Science & Business Media, 2006.

Swaminathan, A. and Joachims, T. Batch learning from logged bandit feedback through counterfactual risk minimization. Journal of Machine Learning Research, 16: 1731 1755, 2015.

Thompson, W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285 294, 1933.

Tropp, J. A. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12 (4):389 434, 2012.

Van de Geer, S., B uhlmann, P., Ritov, Y., Dezeure, R., et al. On asymptotically optimal confidence regions and tests for high-dimensional models. The Annals of Statistics, 42(3):1166 1202, 2014.

Villar, S., Bowden, J., and Wason, J. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: a review journal of the Institute of Mathematical Statistics, 30(2):199, 2015.

Wei, C.-Z. Asymptotic properties of least-squares estimates in stochastic regression models. The Annals of Statistics, pp. 1498 1508, 1985.

Zhang, C.-H. and Zhang, S. S. Confidence intervals for low dimensional parameters in high dimensional linear models. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 76(1):217 242, 2014.