Adaptive Linear Estimating Equations
Authors: Mufang Ying
Koulik Khamaru
Cun-Hui Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: bandit algorithm
statistical inference
adaptively collected data
asymptotic normality
TL;DR: We study statistical inference for adaptively collected data.

Abstract: Sequential data collection has emerged as a widely adopted technique for enhancing the efficiency of data gathering processes. Despite its advantages, such data collection mechanism often introduces complexities to the statistical inference procedure. For instance, the ordinary least squares (OLS) estimator in an adaptive linear regression model can exhibit non-normal asymptotic behavior, posing challenges for accurate inference and interpretation. In this paper, we propose a general method for constructing debiased estimator which remedies this issue. It makes use of the idea of adaptive linear estimating equations, and we establish theoretical guarantees of asymptotic normality, supplemented by discussions on achieving near-optimal asymptotic variance. A salient feature of our estimator is that in the context of multi-armed bandits,  our estimator retains the non-asymptotic performance of the least squares estimator while obtaining asymptotic normality property. Consequently, this work helps connect two fruitful paradigms of adaptive inference: a) non-asymptotic inference using concentration inequalities  and b) asymptotic inference via asymptotic normality.

Adaptive Linear Estimating Equations
Mufang Ying Department of Statistics
Koulik Khamaru Department of Statistics
Rutgers University New Brunswick my4260scarletman rutgers..eu
Rutgers University New Brunswick k12410stat. rutgers edu
Cun-Hui Zhang
Department of Statistics
Rutgers University New Brunswick
rchang@stat.rutgee edu
Abstract
Sequential data collection has emerged widely adopted technique for enhane- ing the efficiency of data gathering processes. Despite its advantages, such data collection mechanism often introduces complexities the statistical inference procedure. For instance, the ordinary least squares (OLS) estimator in an adap- live linear regression model can exhibit non-normal asymptotic behavior, posing challenges for accurate inference and interpretation. In this paper, we propose a general method for constructing debiased estimator which remedies this issue. It makes use of the idea of adaptive linear estimating equations, and we establish theoretical guarantees of asymptotic normality, supplemented by discussions on achieving near-optimal asymptotic variance. A salient feature of our estimator is that in the context of multi-armed bandits, our estimator retains the non-asymptotic performance of the least squares estimator while obtaining asymptotic normality property. Consequently, this work helps connect two fruitful paradigms of adaptive inference: a) non-asymptotic inference using concentration inequalities and b) asymptotic inference via asymptotic normality.
Introduction
Adaptive data collection arises as common practice various scenarios, with notable example being the use of (contextual) bandit algorithms. Algorithms like these aid in striking balance between exploration and exploitation trade-offs within dccision-making processes, encompassing domains such personalized healthcare and web-based services [35, 24, 3, 22]. For instance, in personalized healtheare, the primary objective is to choose the most effective treatment for each patient based on their individual characteristics, such medical history, genetic profile, and living environment. Bandit algorithms can be used to allocate treatments based on observed response, and the algorithm updates its probability distribution to incorporate new information as patients receive treatment and their response is observed. Over time, the algorithm can learn which treatments are the most effective for different types of patients.
Although the adaptivity in data collection improves the quality data, the sequential nature (non-iid) of the data makes the inference procedure quite challenging [34, 26, 5, 28, 27, 10, 30, 29]. There is lengthy literature on the problem of parameter estimation in the adaptive design setting. a series of work [15, 19, 17], the authors studied the consistency of the least squares estimator for an adaptive
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

linear model. In a later work, Lai [14] studied the consistency of the least squares estimator in nonlinear regression model. The collective wisdom of these papers is that, for adaptive data collection methods, standard estimators are consistent under mild condition on the maximum and minimum eigenvalues of the covariance matrix [19, 14]. In a more recent line of work [1, 2], the authors provide high probability upper bound on the f2-error of the least squares estimator for linear model. We point out that, while the high probability bounds provide a quantitative understanding of OLS, these results assume stronger sub- aub-Gaussian assumption on the noise variables.
The problem of inference, i.e. constructing valid confidence intervals, with adaptively collected data is much more delicate. Lai and Wei [19] demonstrated that for a unit root autoregressive model, which is an example of adaptive linear regression models, the least squares estimator doesn't 't achieve asymptotic normality. Furthermore, the authors showed that for a linear regression model, the least squares estimator is asymptotically normal when the data collection procedure satisfies stability condition. Concretely, letting z; denote the covariate associated with i-th sample, the authors require
B S, I
(1)
where S, = -x- T,=; and (B,)n2) I is sequence of non-random positive definite matrices. Unfortunately, in many scenarios, the stability condition (1) is violated [38, 19]. Moreover, in practice, might be difficult verify whether the stability condition (1) holds not. In another line of research [10, 36, 37, 4, 9, 28, 31, 25, 38], the authors assume knowledge of the underlying data collection algorithm and provide asymptotically valid confidence intervals. While this approach offers intervals under much weaker assumption on the underlying model, full knowledge of the data collection algorithm is often unavailable in practice.
Online debiasing based methods: In order to produce valid statistical inference when the stability condition (1) does not hold, some authors [8. 7, 13] utilize the idea of online debiasing. At a high level, the online debiased estimator reduces bias from an initial estimate (usually the least squares estimate) by adding some correction terms, and the online debiasing procedure does not require the knowledge of the data generating process. Although this procedure guarantees asymptotic reduction of bias to zero, the bias term's convergence rate can be quite slow.
In this work, we consider estimating the unknown parameter in an adaptive linear model by using set of adaptive linear estimating equations (ALEE). We show that our proposed ALEE estimator achieves asymptotic normality without knowing the exact data collection algorithm while addressing the slowly decaying bias problem in online debiasing procedure.
2 Background and problem set-up
In this section, we provide the background for our problem and set up few notations. We begin by defining the adaptive data collection mechanism for linear models.
2.1 Adaptive linear model
Suppose a scalar response variable y is linked to a covariate vector æ, E RRd at time / via the linear model:
x 0r + for E [n],
(2)
where 0" E Rd is the unknown parameter of interest.
In adaptive linear model, the regressor æ, at time is assumed to be a (unknown) function of the prior data point {x1. ....... It-1, 1t-1} } as well as additional source of randomness that may be present in the data collection process. Formally, assume there is an increasing sequence of o-fields (Fih220 such that
a VI...., 11 ax) E F.-1 for t [n].
For the noise variables (erhe appearing in equation (2), we impose the following conditions
E|c|[F--]]00 = B[ = and sup 121
< xo,
(3)
for some 8 > 0. The above condition is relatively mild compared to sub-Gaussian condition.

---

Examples of adaptive linear model arise in various problems, including multi-armed and contextual bandit problems, dynamical input-oulput systems, adaptive approximation schemes and time series models. For instance, in the context of the multi-armed bandit problem, the design vector dt is one of the basis vectors (ex (dj)) representing an arm being pulled, while f*, Ut represent the true mean reward vector and reward at time i, respectively.
2.2 Adaptive linear estimating equations
As we mentioned earlier, the OLS estimator can fail achieve asymptotic normality due to the instability of the covariance matrix with adaptively collected data. To get around this issue, we consider different approach ALEE (adaptive linear estimating equations). Namely, we obtain an estimate by solving a system of linear estimating equations with adaptive weights,
ALEE:
E we(c x, ALLE)) 0.
Here the weight wp E Rd is chosen in way that wy E Fi-1 for t E [n]. Let try gain some intuition behind the construction of ALEE. Rewriting equation (4), we have
Ei=n w (OALEE - -0) = Σi= WrEr.
(5)
Notably, the choice of w, E Fi makes Ei=1 W the sum of martingale difference sequence. Our first theorem postulates conditions on the weight vectors {wi)r> such that the right-hand side of (5) converges to normal distribution asymptotically. Throughout the paper, we use the shorthand W. (w....., un;) Rtxd X, (x11 ..,,.....3. Tt) E R
Proposition 2.1. Suppose condition (3) holds and the predictable sequence {wilisss satisfies
max
1, 1|2 (1)
and
La W. lp o1).
(6)
ISt
Let A V. X, with W. Aw V being the SVD of W n- Then,
A e A 0 0-//0 d, (O.
where ā is any consistent estimator for a.
Proof. Invoking the second part of the condition (6), we have that A is invertible for large and IV VT Iallop op (1). Utilizing the expression (5), we have
A ALFE 8")/a = V A X
O ALEE 0-)/o- V.AA
w.sjo.
Invoking the stability condition the weights (w,)) and using the fact that Σ ==1 waet is martingale difference sequence, we conclude from martingale central limit theorem [11, Theorem 2. I] that
E wis/o - No Lz).
Combining the last equation with A VT -allop = (1) and using Slutsky's 's theorem yield
A OALEE 0")/o - (..
The claim Proposition 2.1 now follows from Slutsky's theorem.
few comments regarding the Proposition 2.1 are in order. Straightforward calculation shows
A.A.A P Sn. where
P = (,,WW, W.) -'W..
(8)
In words, the volume of the confidence region based (7) is always larger than the confidence region generated by the least squares estimate. Therefore, the ALEE-based inference, which is consistently valid, exhibits reduced efficiency in cases where both types of confidence regions valid. Compared with the confidence regions based on OLS, the advantage of the ALEE approach is provide flexibility in the choice of weights guarantee the validity of the CLT conditions (6).
Next, note that the matrix A is asymptotically equivalent to the matrix W X,, (see equation (5) under the stability condition (6). The benefit of this reformulation is that it helps better understand

---

efficiency of ALEE compared with the OLS. This has led us to define notion of affiniyy between the weights (w2 and covariates (ar) for better understanding the efficiency of ALEE and ways to design nearly optimal weights, as it will be clear in the next section.
Finally, it is straightforward to obtain consistent estimate for a. For instance, assuming log(Amaa (X, Xn))/n 9- 0 and the noise condition (3), we have
6²
Ut xi 0ls)² -.,
(9)
Here, Ots refers to the least squares estimate. See [19, Lemma 3] for detailed proof of equation (9).
3 Main results
In this section, we propose methods to construct weights (we)e21 which satisfy the stability prop- erty (6), and study the resulting ALEE. Section 3.1 is devoted to the multi-armed bandit case, Section 3.2 to an autoregressive model, and Section 3.3 to the contextual bandit case. Before delving into details, let us try to understand intuitively how construct weights that have desirable properties.
The expression (8) reveals that the efficiency of ALEE depends on the projection of the data matrix X, Wn. Thus, the efficiency of the ALEE approach can be measured by the principal angles between the random projections P., in (8) and Pa, = S,,,,, X
Accordingly, we define the affinity
A(W,, n. X,) of the weights (w, )221 the cosine of the largest principle angle, or equívalently
A(W x.,) P.)) (,,
(10)
as the d-th largest singular value of P, P...P. angle between the two subspaces spanned by the columns of X,, and W., respectively [12]. Good weights (we)r21 are those with relatively large affinity or
Formally, the above definition captures the cosine the
Um X,S
(approximately).
(1I)
3.1 Multi-armed bandits
In the context of the K-arm bandit problem, the Gram matrix has diagonal structure, which means that we can focus on constructing weights (wih2 for each coordinate independently. For an arm k E [K] and round t > 1, define
$tkk so Ei= L.
for some positive so E Fo.
(12)
Define the k-th coordinate of the weight we as
Wo.k
8t.k
Fr.k
with f(z) f(z)= x. log( (2xx)) (log log(e=x)))²
log 2
(13)
80
/50
The intuition behind the above construction is as follows. The discussion at near equation (11) 1/2,
indicates that the k-th coordinate of w, should be proportional to /E. 1/2, However, the weight w, required to be predictable, which can only depend on the data points up time t. Consequently, we approximate the sum Eisn x.f by the partial sum 8t,k in (12). Finally, note that
Wr.k 5(
Ft.k
(14)
80
BLRk
The logarithmic factors in (13) ensure that the stability conditions (6) hold. In the following theorem, generalize the above method general strategy for constructing weights {w,h21 satisfying the stability condition (6).
Note that 2t,s E Fi-1 can be used to construct we

---

Distribution of errors in AR(1)
Distribution of errors with E-greedy
.to,11 1)
. 1)
OLS
OLS ALEE
ALEE
-3
-2 -1
4
-3
-2
-1
0
2
4
Figure I: Empirical distribution of the standardized estimation errors from OLS and ALEE approach. Results obtained with a dataset of size n 1000 and 3000 independent replications. Left: (R(1) model Y/ = 1/-1 + with independent errors é, ~ (Q 1). Right: Two-armed bandit problem with equal arm mean 0 0 0.3 and independent noise E (O 1). Figure 4 in Section C.3 considers the same setting with centered Poisson noise, which is not sub-Gaussian
3.1.1 Stable weight construction strategy
Consider a positive decreasing function f(z) on the interval [1, oo) with an increasing derivative fx)).. Let satisfy the conditions: f'/ f/fix increasing,
J P(x)da=1 =1 and J [()ddo 00.
(15)
With 80 E Fo. we define weight Wi,k
Wi,k f
8t,k
Ft.k
with St,k = +
(16)
80
80
A key condition that ensures the weights fwi, satisfy the desirable stability property (6) is
max
St.k
x
max 18t5n
(1- H
f(5(-11//0))
00
(x)ddz= op()..
(17)
50
50
For multi-armed bandits, this condition is automatically satisfied when both quantities 1/s0 and so/sn.k converge to zero in probability. Putting together the pieces, we have the following result for bandits.
Theorem 3.1. Suppose condition (3) holds and 1/su + su/sn,k 0y(1) for some k [K]. Then, the k-th coordinate ALEE, obtained using weights from equation (16), satisfies
(ALLEE. - 0%) /9n.ee/ 8o 550 f(x)da 4 N(O,
(18)
where ā is consistent estimate of a.. Equivalently.
ALLBE, & - 0%)
Σ wLL
a N(0,))
(19)
Eisiso w2,x
The proof of Theorem can be found in Section A. of Appendix. few comments regarding Theorem 3.1 are in order.
First, the above theorem enables us construct valid CI in the estimation of the mean 0 for sub-optimal arm & when employing an asymptotically optimal allocation rule to achieve the optimal regret in [18] with sample size Eesn Tt,k log n,, or when using sub-optimal rule achieve polylog(n)). On the other hand, the classical martingale CLT is applicable to the optimal arm (if unique) under such asymptotically optimal or sub-optimal allocation rules. Consequently, one may obtain a valid CI for the optimal arm from the standard OLS estimate [19]. However, is important to note that such Cls are not guaranteed for sub-optimal arms.
5

---

Next, while Theorem 3.1 holds for any so diverging to infinity but of smaller order than 8n, (which may depend on k). the convergence rate of Lisign W to normality is enhanced by choosing large value for so. In practical terms, it is advisable to choose an so that is slightly smaller than the best-known lower bound for Sn
Finally, the choice of function f determines the efficiency of ALEE estimator. For instance, taking function (x) = 1/2, we obtain an estimator with asymptotic variance of order 1/ (/ log"(s, / //))))) so)). which is only better than what one would get using stopping time results by a logarithmic factor. In the next Corollary, improved choice of f yields near optimal variance up to logarithmic terms.
Corollary 3.2. Consider the same sei of assumptions as stated in Theorem 3. The ALEE estimator
T GALEE, ko obtained by using f() (3 log 2/ { e²x) (log log x2x) -1//2 for any 3 > 0 satisfies
4,(log 2)3
Sn,k ( OLLERR - 02) - N(.1))
V log(Sn, su) flog log Sn,k/ su)
The proof of this corollary follows directly from Theorem 3.1. For su log n/ log log in multi- armed bandits with asymptotically optimal allocations, (og(Sn,,//u) (1 + o(1)) log log 8n,k-
3.1.2 Finite sample bounds for ALEE estimators
One may also construct finite sample confidence intervals for each arm via applying concentration bounds, Indeed, for any arm K, we have
W...T...k) (DALER, 0%
(20)
Following the construction of Wr,k Fr-1, the term E We is amenable to concentration inequalities if we assume that the noise e, is sub-Gaussian conditioned on Fr-1,
Ble Fi-1l &
(21)
Corollary 3.3 (Theorem in [1]). Suppose the sub- Gaussian noise condition (21) in force. Then
for any 5 > 0 and Ao > O, the following bound holds with probability at least 1 -
(Ao Ei= 82N0
Σ
WL.KDikk
(ALLEE, f8 0 (Au +
Σ wx,x (ex)-logg t=1
(22)
Remark 3.4. In the context of multi-armed bandit, by considering the function f in Corollary 3.2 with 3 and Corollary 3.3 with Xn we derive that with probability at least 1
Õ -O%l S og V log(2/22) /2 2 + log(Sn.k/ 80) log (2 + log((s, k/8))
(23)
V8n,k
/80
provided so > 1. See Section A.2 of the Appendix for a proof of this argument. Recall that / (so + Eisn 2²2 the bound is in the same spirit as existing finite sample bounds for the OIS estimator for arm means [1, 21]. In simple terms, the ALEE estimator behaves similarly to the OLS estimator in non-asymptotic setting while still maintaining asymptotic normality.
3.2 Autoregressive time series
Next, we focus on an autoregressive time series model
V: = yt-1 + t for E [n]].
(24)
where Yo 0. Note that the above model is a special case of the adaptive linear model (2).
well-known that when 0* (-1,11 1), the time series model (24) satisfies stability assumption (1).
Consequently, one might use the OLS estimate based confidence intervals [19] for 0* However,
when 0" - also known as the unit root case stability condition (1) does not hold, and the

---

least squares estimator is not asymptotically normal [19]. In other words, when 0 = 1, the least squares based intervals do not provide correct coverage.
In this section, we apply ALHE-based approach to construct confidence intervals that are valid for 0r [-1,1]- Similar previous sections, let 8o E Fo and denote 8, 80 Eisige Vi-1- Following construction similar to the last section, we have the following corollary.
Corollary 3.5. Assume the noise variables {(+) are ii.d with mean zero, variance o² and sub- Gaussian parameter og. Then, for any 0' E [-1,1], the ALEE estimator, obtained using wi (81/880)t-11 /so with function J from Corollary 3.2 and 80 n// log log(n),, satisfies
4log 2)
O (ALRR 0*) d No.
(25)
log(sn/ 80) (log log(sn/////ooooo (sn/ (0)) (o)
The proof of Corollary 3.5 can be found in Section A.3 of the Appendix.
3.3 Contextual bandits
In contextual bandit problems, the task of defining adaptive weights that satisfy the stability con- dition (6) while maintaining a large affinity is challenging. Without loss of generality, we assume that || aalll 22 S 1. Following the discussion around (11) and using S, as approximation of Sn,
that good choice for the weight is wy S, x₁, However, it is not all clear the moment why the above choice produces d' di-iimesioonal weights w, satisfying the stability condition (6). turns out that the success of our construction is based on the variability of certain matrix V.. For Fo Fo-measurable x d symmetric matrix En 2 La and /. E [n]. we define
E, Eg +
a
and
21 E 24
(26)
as For 1. E [n], we define the variability matrix V,
Ve = La
(Variability).
(27)
The variability matrix V, comes up frequently in finite sample analysis of the least squares estima- tor [16, 19, 2], the generalized linear models with adaptive data [23], and in online optimization [6]; see comments after Theorem 3.6 for a more detailed discussion on the matrix V.. Now, we define weights (we)t2)
W. V1+ Vi-1 ViZi.
(28)
Theorem 3.6. Suppose condition (3) holds and 1| 1 + I|V = op()) Then, the ALEE estimator ALL obtained using the weights {we h from (28), satisfies
Σ WEE
OOALER 0¹) - N(0,0,
The proof of Theorem 3.6 can be found in Section A.4 of the Appendix. In Theorem B.4 in the appendix, we establish the asymptotic normality of a modified version of the ALEE estimator, which has the same asymptotic variance the one Theorem 3.6 under the assumption E llo = (1). In other words, the modified theorem B.4 does not assume any condition on the |V
To better convey the idea of our construction, we provide lemma that may be of independent interest. This lemma applies to weights we generated by (27) and (28) with general 2t- Lemma 3.7. Let w, be as in (28) with the variability matrix V, in (27). Then,
Σ w.W. 1 V n:
max IStsa
|wr]12 max 15t5n
|| - 1 / 2, V V.-12,)
(29)
For 2t Fr-1, the stability condition (6) holds when maxigisn 2, V22, + VV o1())
7

---

Proof. For any t 2 1, V2 = Vt-1 V V 11-1/(1+ 2, Vl11z). It follows that Vize Ve-1a1 + 2, (=+) and Et=1 :m = E V., V,, = La Vn.
Comments Theorem 3.6 conditions: It is instructive to compare the conditions of Theorem 3.1 and Theorem 3.6. The condition |oop o1( is analogue of the condition 1/50 o,()).
The condition |V = (p(1) is a bit more subtle. This condition an analogue of the condition
kn, (1). Indeed, applying elliptical potential lemma [2, Lemma 4] yields
log(det( (2 + S,)) log( (det (Eo))
log(det Eo + S..) log(det (oo))
trace( d Σ o. و Bi S 2.
(30)
where S, = E
i= T is the Gram matrix. We see that for |/ op(1), it is necessary that the eigenvalues of S., grow infinity at faster rate than the eigenvalues of Eg. Moreover, in the case of dimension d = 1, the condition | V Vlll = Op (1) is equivalent to fo/sn, = op(1).
Numerical experiments
In this section, consider three settings: two-armed bandit setting, first order rugo-regressive model setting and contextual bandit setting. In two-armed bandit setting, the rewards are generated with same arm mean (01, 05) (0.3, 0.3). and noise generated from a normal distribution with mean 0 and variance 1. To collect two-armed bandit data, we use e-Greedy algorithm with decaying exploration rate Vlog(t)/t. The rate is designed to make sure the number of times each armed is pulled has order greater than log(n) up to time n.. the second setting, we consider the time series model.
Yt = lt yt-1 + Ct:
(31)
where 0* = and noise is drawn from normal distribution with mean 0 and variance 1. In the contextual bandit setting, consider the true parameter O" be 0.3 times the all-one vector. In the initial iterations, random context 2; is generated from a uniform distribution in sd-1 Then, we apply e- e-Greedy algorithm to these pre-selected contexts with decaying exploration rate log (t)/t. For all of the above three settings, we run 1000 independent replications.
Bandit: lower tail coverage for 0
Bandit: upper tail coverage for 6
Average two-sided CI width for e
1.0
CLB
ALEE
Eingkical covernge probeslly
68
Concontraln ation
Wedeoome
Meae wigth Cr
Target Coverago
Tarpet Coverage
OLS
OLS
Conconitation W decomdaation
Conconttation W docorddation
5.6
0.6
511
0.80
0.85
6.0
6.75
0:00
655
0.75
0.00
0.85
0,00
Targatcovaaag coveraga probabilltt
Targat covaragi probabillty
Targatcovarage cowarage probabilltt
Figure 2: Two-armed bandit problem with equal arm mean 0j 05 0.3. Error bars plotted are +
standard errors.
To analyze the data we collect for these settings, we apply ALEE approach with weights specified in Corollary 3.2, 3.5 and Theorem B. B.4, respectively. More specifically, in the first two settings, we consider 8 = in Corollary 3.2. For two-armed bandit example, known to be lower bound for sn,1. For AR(I) model. we consider so = e2n/ log log(n). For the contextual bandit example, we consider Eg log(n) L,. In the simulations, we also compare ALEE approach to the normality based confidence interval for OLS estimator [19] (which may be incorrect), the concentration bounds for the OLS estimator based on self-normalized martingale sequence [1], and W-decorrelation [8]. Detailed implementations about these methods can be found in Appendix C.I.
set so e² log(n), which
In Figure 2, we display results two-armed bandit example, providing the empirical coverage plots for the first arm mean Of well average width for two-sided Cls. We observe that Cls based on
8

---

AR: lower tail coverage for 0*
AR: upper tail coverage for 8*
Average two-sided CI width for
10
10
OLS
ALEE
Engg aigeiiialll eovanigia probebblty
protesbility
Concantration
12
0002
W-dhesoraadio
0.01
Tarpet Coverago
EmplWai
Torget Coverage
6.4
OLS
0003
Concentation
Concentration
W-deecmmedaiinn
W-ddecomeetionn
0622
Target coverage probatbility
Target coverage probabilltt
Targetcoverag coverage probaibllity
Figure 3: AR(1) with model coefficient 6* = and Su = e2nz/ log log(n). Error bars plotted are + standard errors.
OLS undercover 0f while other methods provide satisfactory coverage. Notably, from the average CI width plot, we can see that W-decorrelation and concentration methods have relatively large CI widths. On the contrary, ALEE-based CIs achieve target coverage while keeping the width of CIs relatively small.
For AR(1) model, we display the results in Figure 3. For the context bandit example, consider 20 and summarize the empirical coverage probability and the logarithm of the volume of the confidence regions in Table I, along with corresponding standard deviations. See Appendix C.2 for experiments with dimension 10 and d = 50.
Table 1: Contextual bandit: d 20
Method
Level of confidence
0.8
0.85
0.9
Avg. Coverage
Avg. log(Volumn)
Avg. Coverage
Avg. log
Avg. Coverage
Avg. logi Volumn)
0.528)
0.861 0.346)
0.528)
0.910 0.286)
0.528)
OLS
0.776 (#: 0.417)
-2,079 (= 0.525)
0.830 ( 0.376)
-1.513 (#: 0.525)
0.881 (d: 0.524)
-0.315 (#: 0.525)
D-Dezomelation
0.416)
25.727
0,829 0.377)
26.294 0.518)
0,870 (:: 0.336)
(+: 0.518)
Concentaation
1.000 (:: 0.000)
17.374 (= 0.506)
1.000 0.000)
17:408/1 0.506)
1,000 (:: 0,000)
17.455 (:: 0.506)
5
Discussion
In this paper, we study the parameter estimation problem in adaptive linear model. We propose to use ALEE (adaptive linear estimation equations) obtain point and interval estimates. Our main contribution is to propose an estimator which is asymptotically normal without requiring any stability condition on the sample covariance matrix. Unlike the concentration based confidence regions, our proposed confidence regions allow for heavy tailed noise variables. We demonstrate the utilitity of our method by comparing our method with existing methods.
Our work leaves several questions open for future research. For example, it would be interesting to characterize the variance of the ALEE estimator compared the best possible variance[ 13, 20] for d > 1. It would also be interesting to know if such results can be extended to non- non-linear adaptive models, e.g., to an adaptive generalized linear model [23]. Furthermore, our paper assumes fixed dimension d for the problem while letting - co. It would be interesting to explore whether we can allow the dimension grow with the number of samples specific rate.

---

Acknowledgments
This work was partially supported by the National Science Foundation Grants DMS-2311304 CCF- 1934924, DMS-2052949 and DMS-2210850.
References
[1] Yasin Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Online least squares estimation with self- normalized processes: An application to bandit problems. arXiv preprint arXiv: arXiv:/ 2011.
[3] Deepak Agarwal, Bee- Che-Chung Chen, Pradheep Elango, Nitin Motgi Seung Taek Park, Raghu Ramakrishnan, Scott Roy, and Joe Zachariah. Online models for content optimization. Advances in Neural Information Processing Systems, 21, 2008.
[4] Aurélien Bibaut, Maria Dimakopoulou, Nathan Kallus, Antoine Chambaz, and Mark van Der Laan. fost-contextual-baae bandtt inference. Advances in neural information processing systems, 34:28548-288 285599, 2021.
[5] Jack Bowden Lorenzo Trippa. Unbiased estimation for response adaptive clinical trials. Statistical methods in medical research, 26()):2376-2388, 2017.
Varsha Dani, Thomas P Hayes, and Sham M Kakade, Stochastic linear optimization under bandit feedback. 2008.
[7] Yash Deshpande, Adel Javanmard, and Mohammad Mehrabi. Online debiasing for adaptively collected high-dimensional data with applications time series analysis. Journal of the American Statistical Association, pages 1-14, 2021.
[8] Yash Deshpande, Lester Mackey, Vasilis Syrgkanis, and Matt Taddy, Accurate inference for adaptive linear models. In International Conference on Machine Learning, pages 1194 1203. PMLR, 2018.
[9] Maria Dimakopoulou, Zhimei Ren, and Zhengyuan Zhou Online multi-armed bandits with adaptive inference. Advances in Neural Information Processing Systems, 34: 1939-9999,,, 2021.
[10] Vitor Hadad, David A Hirshberg, Ruohan Zhan, Stefan Wager, and Susan Athey. Confidence inter- vals for policy evaluation in adaptive experiments. Proceedings of the National Academy of Sciences, (18(15):c21460011 18, 2021.
[11] Inge S Helland. Central limit theorems for martingales with discrete continuous time. Scandinavian Journal of Statistics, pages 79-94, 1982.
[12] Ilse Ipsen and Carl D Meyer. The angle between complementary subspaces. The American mathematical monthly, 904 911, 1995.
[13] Koulik Khamaru, Yash Deshpande, Lester Mackey, and Martin Wainwright. Near-optimal inference adaptive linear regression. arXiv preprint arXiv:2107.02266 2021.
[14] Tze Leung Lai. Asymptotic properties of nonlinear least squares estimates in stochastic regression models. The Annals of Statistics, pages 1917-1930, 1994.
[15] Tze Leung Lai and Herbert Robbins. Adaptive design and stochastic approximation. The annals of Statistics, pages 1196 1221, 1979.
[16] Tze Leung Lai and Herbert Robbins. Adaptive design and stochastic approximation. The annals of Statistics, pages 1 1196-1221, 1979.
[17] Tze Leung Lai and Herbert Robbins. Consistency and asymptotic efficiency of slope estimates in stochastic approximation schemes. Zeitschrifi für Wahhrcheinicckkeissheenr und verwandte Gebiete, 56(3):329-360 1981.
[18] Tze Leung Lai, Herbert Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-2,, 1985.
[19] Tze Leung Lai and Ching Zong Wei. Least squares estimates in stochastic regression models with applications to identification and control of dynamic systems. The Annals of Statistics, 10(1):154-1) 166, 1982.
10

---

[20] Tor Lattimore. A lower bound for linear and kernel regression with adaptive covariates. In The Thirty Sixth Annual Conference on Learning Theory, pages 2095-2113. PMLR, 2023.
[21] Tor Lattimore and Csaba Szepesvari. The end of optimism? an asymptotic analysis of finite-armed linear bandits. In Artificial Intelligence and Statistics, pages 728-737. PMLR, 2017.
[22] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandee approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 100-670,2200 2010.
[23] Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithus for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-2080. PMLR, 2017.
[24] Peng Liao, Kristjan Greenewald, Predrag Klasnja, and Susan Murphy. Personalized heartsteps: A reinforcement learning algorithm for optimizing physical activity. Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies, 4(1):1-22, 22, 2020.
[25] Licong Lin, Koulik Khamaru, and Martin Wainwright. Semi Semi-parametric inference based on adaptively collected data. arXiv preprint arXiv:2303. 02534, 2023.
[26] Alexander R Luedtke and Mark Van Der Laan. Statistical inference for the mean outcome under a possibly non-unique optimal treatment strategy. Anmals of statistics, 44(2):713, 2016.
[27] Seth Neel and Aaron Roth. Mitigating bias adaptive data gathering via differential privacy. In International Conference on Machine Learning, pages 3720-3729. PMLR, 2018.
[28] Xinkun Nie, Xiaoying Tian, Jonathan Taylor, and James Zou. Why adaptively collected data have negative bias and how to correct for it. In International Conference on Artificial Intelligence and Statistics, pages 1261-1269. PMLR, 2018.
[29] Jachyeok Shin, Aaditya Ramdas, and Alessandro Rinaldo. Are sample means in multi-armed bandits positively or negatively biased? Advances in Neural Information Processing Systems. 32, 2019.
[30] Jachyeok Shin, Aaditya Ramdas, and Alessandro Rinaldo. On the bias, risk and consistency of sample means in multi-armed bandits. arXiv preprint 1rXiv:1902.000 2019.
[31] Krishma Kumar Singh, Dhruv Mahajan, Kristen Grauman, Yong Jac Lee, Matt Feiszli, and Deepti Ghadi- yaram. Don't judge object by its context: Learning to overcome contextual bias. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition, pages 11070-11078, 2020.
[32] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[33] Martin J Wainwright. High-dimensional statisties: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
[34] Min Xu, Tao Qin, and Tie- Yan Liu. Fstimation bias in multi- armed bandit algorithms for search advertising. Advances in Neural Information Processing Systems, 26, 2013.
[35] Elad Yom-Tov, Guy Feraru, Mark Kozdoba, Shie Mannor, Moshe Tennenholtz, and Irit Hochberg, En- couraging physical activity in patients with diabetes: intervention using reinforcement learning system. Journal of medical Internet research, 193)),3338 2017.
[36] Ruohan Zhan, Vitor Hadad, David A Hirshberg, and Susan Athey. Off-policy evaluation via adaptive weighting with data from contextual bandits. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 2125-2135, 2021.
[37] Ruohan Zhan, Zhimei Ren, Susan Athey, and Zhengyuan Zhou. Policy learning with adaptively collected data. Management Science, 2023.
[38] Kelly Zhang, Lucas Janson, and Susan Murphy. Inference for batched bandits. Advances neural information processing systems, 33:9818-988 2020.
11

---

Appendix
Table of Contents
A Proof
12
A.1 Proof of Theorem 3.1
12
A.2 Proof of Remark 3,4
13
A.3 Proof of Corollary 3.5
14
A.4 Proof of Theorem 3.6
17
B Generalized Theorem 3.6
18
C Simulation
21
C.I Simulation details
21
C.2 Tables for contextual bandits
22
C.3 Asymptotic normality with centered Poisson noise variables
22
A Proof
Theorem 3.1, Corollary 3.3 and Remark 3.4, we deal with an arm with index &s E [K]. To simplify notations, we drop the subscript 8t,ks Wr,ks &t, ALBEE and 0f throughout the proof, and use 8t, Wy, Wt, ALLEE and 0", respectively.
A.1 Proof of Theorem 3.1
Condition (17) serves an important role in proving (18). Therefore, we start our proof by verifying the
condition (17). Since function f positive decreasing function, we first have
81
2 S f2 (1)
1
max Isee
(32)
80
80
80
Furthermore, since function f' / is increasing, we have
(1
[81//00)
[ 100--1/800 1/80) (8s/
max ists
f(80-1/80)
istsn
max
8 80)
(33)
1 max
(s
(1(
80
1stt
(88-1/80)
f(1)
where inequality (i) follows from value theorem and the monotonicity of the function f'/f. Thus. by assuming 1/50 (1) and 60/*, = (1), condition (17) follows directly from equation (32) and equation (33).
By the construction of ALEE estimator, we have
Σ Writ
00))=
whlt.
(34)
Note that
Evso 2
Σ W.F.
80
fss (o)
f(x)dr-
(35)
p f(r)dr
By the mean value theorem, we have that for E [n], & E 81]
f(x)dr
x f(E+/s0)
s0
12

---

Therefore, we have
Eisn Sem/ (x)ddx
Eisol [la//s0]
-1)f(Es/90)rts
f(te/20)
1
Eisn [(t//o))=
2
Observe that
Eien [(t//5a)
11f((E//0)=z/ /
[7| v
F(Le/oa)
Eisn [(E1/ (0.//s0)2? so
Eisn 114--1190
1 /{(E=/00)zz /0) Eisn f1E// (1/:/8u)=7/ /2// 80
165e/00)
1 [8)/s00 f(8c-1/50) op(1).
<
max 1st5n
Equality (it) follows from condition (17). Consequently, applying Slutsky's theorem yiclds
E i= WeFE 2 1.
88 pa f(x)do
Similarly, derive
(st so) ot = =11+ (mn/ P(o)de=
(36)
Knowing SISN wi maxi misigien (st// )=) /00 = (1). which is consequence of equation (17). martingale central limit theorem together with application of Slutsky's 'ss theorem yields
(AALER- 8¹)
sm/
/50 σ
f(x)dr - N(0, 1).
Lastly. recall that
8 0ALER 0"
Wels
Wc6t-
Eesa ui
V mi
T Eesn
Therefore, equation (19) follows from martingale central limit theorem and Slutsky's theorem.
Remark A.1. Equation (18) sheds light the asymptotic variance of the ALEE estimator, thereby aiding in the selection of a suitable function f improve the efficiency of ALEE estimator. On other hand, equation (19) offers a practical approach to obtaining an asymptotically precise confidence interval.
Remark A.2. Condition (17) general requirement that governs equation (18), and not specific to bandit problems. However, the difficulty verifying (17) can vary depending on the problem hand.
A.2 Proof of Remark 3.4
Corollary 3.3 follows directly from Theorem 1 [1]. In this section, we provide proof Remark 3.4. By considering Ao = in Corollary 3.3, we have with probability at least 1
1+ >" wi
Σ
(ALEE 8¹1 ooN (1+ Σ wf) log
(37)
82
By the construction of the weights in Corollary 3.2, we have
2 L f())d==1.
(38)
13

---

Therefore, to complete the proof, it suffices to characterize lower bound for Σ 21gigo War. By definition, we
have
Weit
(st/50)
5
(
27
(st log 8 80) 1/2 log (t/
ui
(39)
(2 log( /8)) 12 12g lo (n//8)) (0))
v
1=1
2(y/on - /50)
Su
(2 log( 80 1/2 1og(2 + /00((/)/))))
1+ 80
(60)
v2(V -V v=0)-
2 + (os((s//ss)))) (2 + log(sn/ so))
In equation (i). we plug in the expression of function f and hence /sp cancels out. Since æt is either 0 or 1. inequality (ti) follows from the integration of the function h(x) 1/ /2. Incquality (iii) follows from so >> 1. Putting things together, we have
(2log(2/82)
ÕaLRR 0'15 0g
Σ 2igisn WilF
(40)
0g (oog(o22/ 2 log (0g((s//55 (0) log log (s., /80)
v 8/
880
This completes our proof Remark 3.4.
A.3 Proof of Corollary 3.5
Note that it suffices to verify the following condition (41)
St
(1
1/80)1/80) ( [(s
f(33/30)
f
(())do= oy()
(41)
89
5.//00
for 0" E 1] the proof of Theorem 3.1. To simplify notations, we let.
1] in order to complete the proof of Corollary 3.5. The other part of the proof can be adapted from
Ti
A maxX S
Di-1 80
T3
max IStSn
(1 (1- [(91/50) [+=-1//00))
and T3
2
f (c))de. 6n/50
Therefore, proving equation (41) is equivalent showing that Ti. T2, T3ss converge zero probability. We will now demonstrate the convergence of each these three terms to zero in probability.
Ti with 0" 1: To prove Ti (1),,, we make use of a result in [19, Equation 3.23], which is
P
lim lim (log log n)
Σ
y1 1 0² 1.
(42)
1=1
Observe that
(2( 8t
22-1
T max
1tt5
80
1stšn
max log( ( / 50)
(log (e 114
vi
istsn 9; log(e? Ylog 10g(
max
(43)
Vi
max 2(log2)1+3
Isesn
81
max
2(log 2)
1693)
2/3/ +1St5h $ $1,9/3, 80
In equation (43), we split the sequence into two parts and set different lower bounds for s.. The major benefit of this step to help derive better choice of so. Now bound max 22-1 and
14

---

(2288 41SIgH vi-1- Note that
P
max
2
2c)
15/5|02/3)
max
max
Ut-1; max -V--1} 15t5\n2/aj
2 Ve)
(44)
max 1 15/5 Vt-1 max max -VC-
VV 2n2 log(2n)/3)
where inequality is derived from [33, Exercise 2.12] and the fact that is sub-Gaussian with sub-Gaussian parameter n for $ [n2/ Therefore, we conclude that
max Vi Op(n 2/3 logn). 15/5
Consequently, we have
vē-1
2/3 log n
max 1
n/ log logn Op(1) ol,().
(45)
80
By applying the same trick max
2/3 + Di-11 1, we can derive
max +istge
Di Op log
In
Hence we have
Op(nlogn) ///3/ / log log n273
n2 /log loggng/n n²/3 (6)
max n2/3 +ISEn 11,2/8
(,(1))0((1) = =0p(1) (46)
$1,2/3
Equality (it) makes use of equation (42). Combining equation (44) with equations (45) and (46), we conclude that Ti = (1)..
Ti with 6" = -1: When 0" 1, the proof is essentially the the when 0 -1 The only difference lies in the order Eisisn vi-1- However, by pairing 6 with ezr for t N+ we can arrive the same result. Specifically, for t E N+ we let = E21 - E2. and define
where vu 2 and (4))21 are random variables with mean zero, variance 20 and sub-Gaussian parameter 2n Therefore, applying equation (44) yiclds
lim n (log log Σ 2
(47)
i 00
Setting no [(Ln=/a] 1)/2], we have
2/3
ng
ag+1
$,,2/3 =
Σ
(u/)² =
Σ
(16-1)²
(48)
According to equation (47) and equation (48), we have
max 1 vE-1
1.9/3341515+ 112218
Eisrsnot (1/-1)²
(no + 1)2/ log log(no 1)
(49)
(no + 1)2 log (ng + 1)
= =1) (1) (1),
which completes the proof of (1( for the when 0* -.
15

---

T with 0' E (-1,1); Given 0" é (-1,1), we observe that ye. is sub-Gaussian random variable with for any t E N Therefore, following equation (43), we have
of
Sub-Gaussian parameter 1-(0-yz
T z 2 2)1+
(50)
where in the above inequality we so lower bound for 8t. By applying [33, Exercise 2. 2.12], we have max vi-1 (logg))) istgn
(51)
leading the conclusion that Ti (1()).
T3 with 0 E [[=1,1];
Similar to equation (33), we have
(1- f(8t/50) 50)
((s-1/50) 30)- f(8e/80)
T2
max 1515
fl (811-1/80)
max 1sis
f(8=-1/S0)
-f' 1 /30) Vi-1
max
f 1 /80) 80
Define g(x) = (x)) and we can compute that
/ ((x))d== -
f'(x) do=
/ df log f C,
f(x)
where C is some constant. Doing some calculation yields
d
((x)
log f =
dr 12 (log(x)) + log log(e x)) + + 9) log log log(e x3)
dr
log (e2x) + 1+
1
2r 1 +
log(e?x) log log(e?x)
Therefore, we have
-f((8-1//8) yē-1
1--1
T3 max
max g(06-1 isr5n
15t50
[st--1/ su)
80
3
+ 8
VE-1
$
+
max
2 2 2log
1st5
8t-1
We note that demonstrating maxistsn vi 1/8--1 (1) follows the approach as the proof of
maxi 1/- (1). Hence, we omit it. To conclude, we show that T22 (1) for 0* E [-1,
Ta with 0* E (-11, 1]: To prove T3 op(1), it suffices verify that
Eisisn vł (1).
80
(52)
For convenience, in equation (52) ys instead of 9t-1- Note that when 0* = 1 or 0" -1 have provided almost sure lower bounds Eisegn yř the proof Ti (1). Therefore, equation (52) follows from these lower bounds. prove equation (52) when 0" E (-1,1), we begin by rewriting Eis's Mē in quadratic form. Without confusion and loss of generality, we replace 8" by 0, consider Var(er) 1, and e. (c1,62,.. c..) For L E [ra], we have
y1
Σ 1=1
0
cx a, En:
where E R² and atj 0--3 for S l and 0r,j
0 for > t. Therefore, Σ Eisesn di can be written as
Σ v Σ e, a.a en. e." Ae..
(53)
15t5n
15t5p
where A =
== Eisisn a.aT. Applying Hanson Hanson-Wright incquality (c.g. see (32]), we have
P (1s
AE Aen A > >) < 2 2exp
-emin
t
t
)
(54)
K IA
K2|A||
16

---

where e and K are some universal constants. Observe that
BE, Agn = trace( A) = trace(
a.a,') ) = -trace(
Σ a. at)
15
Σ 15450
(1+ 0²
21)
1 1- 02h
Σ
1- 82
15
0 )
1 - 8²
(1- (1-
Furthermore, we have
|| = trace(A (A T A) trace( Σ
a:ay"
)
15isn
1515n
E
Σ
(a, a;;)
(55)
1SiS IStS
Σ
||a:l12 +
Σ
| P(--)))
Isicisn
Subsequently, we have
Σ 1si5a
||a||
|| S
Σ
||a.112:
(56)
1 1- 1
15ish
where
28 (1 62n
8 gdn)
Σ |a: Isi5n
n2
02)
(1 02)3
(1 02 04)
Assuming ó S -c and =
K |AAli log(?)) we have with probability at least 1 8,
s., AeT 2 RE,T Ae.. - - lo 2
(57)
We note that the term on the right hand side of equation (57) has order n.. For any 0, consider the following probability
lim sup n-+00
80
><)
lim sup IP 10
>E, 2 BE, Ae. 1 1 111AA1 ()) e Aen Be, Aen ! 1 ())
80 E AE
E, Ae
+ lim sup
(58)
lim sup IP
EE AEn - A log( ( >0) +
80
By fixing 8 and comparing the order of so with the order of e, AE
k |A| log(()) ). have
lim sup P 10000
80
> O.
Ee_
K2d (l 2
Since ó can be arbitrarily small, conclude that
A = (1()),
(,,1,,
(59)
which completes the proof of T3 = (1).).
A.4 Proof of Theorem 3.6
Note that for any 2 1, we have
Vvllop < and V - -1- VV.1 VI-
21 V(-12().
(60)
The second part of equation (60) follows from the Sherman- Morrison formula. Let u Vezi and we adopt the notation V. = Ig. By multiplying z, the right hand side of V., we have
V,z,- V.-IZ, V1-1Z,2 V.-12,((1 2, V1-1222_V_-1z1111
V.-12,)
VI-1
VI-12t 1 2 V,-12,"
(61)
V
1
1 2, V
17

---

Therefore, following the definition of u. we have (1+ x, Vi-iziJu = V.-12 Consequentl,
Σ (1+2) Vi-12))u E V V, n..
(62)
By recognizing
v + 12 U4, come to -Vliv Vn.
Σ wi
What remains now is verify conditions in (6). Notably, assumption |V = op(1) implies
Σ w. _, la-
(63)
Since 'llop = (1). VVlllop S and |a=e|22 1, we can show
2e Viz x; E V. op(1).
(64)
Besides, equation (61) together with equation (64) implies
21 Vizi Op(
max max 2, VI-12
(65)
istsn
2, Vizt
Thus, follows
W
max 1515
V 1 xI 1- Vizi
$ max 18
1 Ve-12 IIV
llop IIV zr|12
(66)
VV(1+
(1
max 2. ( ISt5R
max 2 V.2; (1)
ist5R
Combining equations (66) and (63) yields (6). Hence we complete the proof by applying Proposition 2.1.
Remark A.3. The detailed proof of Lemma 3.7 can be found in the proof of Theorem 3.6.
B Generalized Theorem 3.6
In Theorem 3.6, we impose the following condition (67) so that the ALEE estimator with weights specified in equation (28) achieves asymptotic normality:
IV = (1)
(67)
However, it is typically difficult to directly verify the above condition in practice. To tackle this problem, in this
section, we provide modified version of ALEE estimator which achieves asymptotic normality without requiring condition (67). In this section, use the same notations E,, 21, Vi, and w: detined in equations (26), (27) and (28), respectively. Furthermore, let 2 ... A, be the eigenvalues of the matrix V-l and ai,-..; an be corresponding eigenvectors.
At high level, we construct additional m, vectors (2, 1=1)eesessmmm so that the minimum eigenvalue of resulting matrix V=1 n+mm, greater than a pre-specified constant K.,. which satisties lim, Ko, It is easy that by construction (see Algorithm 1), the matrix V Vn+ma satisfies
1 140 where m7
IV W llop
mk.
(69)
Kn
km1
Remark B.I. Parameter Kn, set ensure condition (69) holds. In practice,
K., dl log(n))
Remark B.2. It's worth mentioning that the number of extra {zs tese is a random variable. Therefore, in order to prove a similar asymptotic normality theorem to Theorem 3.6, we have to apply martingale central limit theorem with stopping times [11, Theorem 2.1].
Theorem B.3 (Theorem 2.1 in [1I]). Let (Eo,k)221,n21 be an array of random variables defined on probability space (R, P) and let (Fn,k)zz1e be array of a-fields such that En.k meeasuaaeeeb and Fo,k-1 C. Funk C F for each n and k 2 1. For each let kn be stopping time with respect to (Fn. 1200 Suppose that
18

---

Algorithm 1: Modified ALEE estimate
I2 and tuning parameter Kn.
2: Compute {(2,, V,, w))) {(A,, (x)) I==1= and obtain consistent estimate σ² of o²
3: Initiate t = n and set = 1/ 1/2 lopp
4: for k L...., do
5: Compute
[ma - Ab. 0} Tn
6: if my then
7: for i = ..... R2 do
8:
Set = + Simulate t, (0,
9:
Define 2: = ax/Tn Tn
11:
Compute
1112 Vi-1
V, V
and
wP V 2, VVV12 Viz
1 ze Vc-1
12:
end for
13: end if
14:
end for
15: Obtain PALEE from equation
wi (y/s
x. 2xLLL) +
Σ
wic: = 0
(68)
1=4+1
16: Output: AULE
km
En, | Fra P.
(70a)
km
Var (5n Fu.e-1) 24 1,
(70b)
km
Σ
Kkn 2+0
Fal -
for some > 0,
(70c)
1
then Ekn En,k d NN0, 1).
With this setup, we are now ready prove the asymptotic normality of PALEE from (68).
Theorem B.4 (Generalized Theorem 3.6). Suppose condition (3) holds. Then, for any tuning parameters
Eg and K., that satisfy ||_g ||opp = op(1) and ,im Ki oo, the ALFE estimator O ALEE obtained from equation (68) sotisfies
OALER 0 d (O.TT.))
Σ
w.Ft
where ō is a consistent estimator of
Remark B.5. We would like reiterate that the asymptotic variance of the modified ALEE estimator obtained from (68) is the same as the one mentioned in Theorem 3.6. Additionally, this modified version does not require the condition | olop = (1( hold and hence is more applicable in practice with theoretical guarantee.
Proof. Rewriting equation (68), we have
m
Σ w. (QALEE
0²)
Σ
(71)
[=1
[=1
19

---

Therefore, by Cramér-Wold theorem, it suffices to show that for any unit vector
Σ
WEEt - (O,
(72)
The proof now follows by verifying the conditions (70a)-(70c) of Theorem B.3 with En, " W.CC. We begin by verifying conditions (70a)-(70c). By Lemma 3.7, we have
WiW;
Ia
Vutma.
(73)
Note that
Warlw Ft-1]
o² wwwi + +
02 -1
Σ
w.w,
(74)
By equation (73) and fact that 0² is consistent, have
and Combining equations (69), (73), (74) and (75), we conclude
w, 3 I
g² - 0.
(75)
Varlwie Fe-1] _ L'L
(76)
On the other hand, we have
( S
(V1+2 V ||ze|la]
max AStSn+mn
max 1sten+ma
V
max IstSntmn
x v2 12
1/2 lop.
Inequality (i) follows from the definition of w., inequality (ii). the assumption that Eg Lg and
the fact that | and [[Vellop I 1. The last inequality (tit) follows from the definition z, and condition that || |25 llop (1)).. Henee, we can see that
max istnntma
[ lla P, O.
(77)
Therefore, have
n+
max SE
(p und
and
Var(v wyet [[-1] _ o²
(78)
Note that condition (70a) holds because {u WEEkhA21 is martingale difference sequence by construction. Condition (70b) follows from statement (78). It remains to verify condition (70c). Observe that
mmm
Elle wiet
2+6
[[-1]=
l0 w.
2+ Bl|e,
244
F(
wil")
sup +21
Blled 2+8 240
Fill)
maxt
n ntt
Variu wie: F(-1]
15iSntm,
o go
(tt) (1) (1))
Equation (io) follows from condition (3), equation (78) and the 2² is consistent estimator. Lastly, by applying Slutsky's 's theorem, we prove that
Σ E=1
w.xx (OALEE - 0²) - NV(0, Lt).
(79)
20

---

C
Simulation
In this section, provide additional comparisons among the ALEE method, the OLS, the W-decorrelation [8]. and the concentration inequality based bounds [I]. The code can be found https: http//ggtttt...t com/
muf mufangying/ ALEE.
C.1
Simulation details
Throughout experiments, utilize 8² from equation (9) as (consistent) estimate of of o² [19].
OLS: When data are ii.d, the least squares estimator satisfies the following condition
qt (os 0*) S.. 0*) - X2.
Therefore, we consider - a confidence region to be
CLs
Rd
OLs T (1ss -) xài-a-
(80)
We point out that the above confidence region is not guaranteed to he accurate when the data is collected in an adaptive manner, as will also be highlighted in our experiments.
W-decorrelation: The W-decorrelation method is borrowed from Algorithm in [8]. Specifically, the estimator takes the form
Ow ocS Σ weli x2 0is)
(81)
Given a parameter weights {w, isesn are set as follows
w: La Σ wox. 11/e)+11
(82)
Following the recommendations from the paper [8]. in order to set À appropriately, we first run the handit algorithm or time series with replications and record the corresponding minimum eigenvalues Amin (S (S. Finally,
[Amin (S )...., Amin ( {>))) We choose À to be the I-quantee of (Sm Ami.,
we obtain a confidence region for 6" as
Cw
0 R
30 (Ow " WWWWWw 5 0x21111000
(83)
where W (wi.,.... wr)
Concentration based on self-normalized martingales: We consider [1, Theorem 1] for single coordinate in two-armed bandit problem and AR(1) model. For contextual bandits, we apply [1, Theorem 2]. Applying concentration bounds requires a sub-Gaussian parameter, for which we use ē from equation (9) as an estimate. We point that this estimate of the sub- uub-Gaussian parameter is conservative, the sub-Gaussian parameter a sub- Gaussian random variable always lower bounded by variance [33, Chapter 2J. This variance estimate is accurate for Gaussian noise random variables.
For dimensional examples, have that for any À O. with probability at least
LLS 8 / at
(A+
Σ 2
log
(84)
Σ x?
Xa²
In two-armed bandit problem, 2, is simply 14,1 for 0f 24,2 for 03. Here consider
For the contextual bandit examples, apply Theorem from [1], and set S = vd: small value = 0.01 to mimic the performance an OLS estimators. Specifically, we utilize following a confidence region
Con
TALL 0 Rd (0, (ALa S.) 0) (0/001100 log
det(ALs + S.))
A 21 f
ddaa
(85)
where O, (X,,X,, ALa) -X,, Y. and Y. = =x1 (B1....,
21

---

C.2 Tables for contextual bandits
In all the contextual bandit simulations, we consider noises that are generated from centered Poisson distribution (i.e. (oisson()) 1). We would like highlight that the centered Poisson random variable is sub-Gauu Gaos-aassia.. Therefore, it important to note concentration inequality- based bounds [1] may not be guaranteed work. In the simulations of this section, we set the number of samples as n = 1000, and the tables below show results over 1000 replications. The tables below clearly show that the average log-volume of the confidence regions are smallest for ALEE among methods which yield valid confidence regions (empirical coverage is more than the target coverage). The volume of the confidence region obtained from the OL. estimate is the smallest, but they under-cover the true parameter. The confidence regions for ALEE are obtained from Theorem B.4 with En = (n) La and Ks, = d (n).
Table 2: Contextual bandit: d= 10
Method
Level of confidence
0.8
0.85
0.9
Avg. Coverage
Avg. log(Volum))
Avg. Coverage
Avg. log(Volumn)
Avg. Coverage
Avg. log( Volumn)
ALEB
0.385)
-2.761 (= 0.263)
0.872 0.334)
-2.370 0.263)
0.921 (#: 0.271)
-1.894 0.263)
OLS
0.807 (d: 0.395)
-7,306 (:: 0.262)
0.863 (3: 0.344)
-6.915 (d: 0.262)
0,905 (d: 0.293)
-6.439 (d: 0.262)
W-Decoorlltionn
0.378)
0.252)
9.249 0.252)
Concuntaaiion
1.000 (:t: 0.000)
2,517 (= 0.252)
1.000 (# 0.000)
2,548 (#: 0.252)
1,000 (#: 0.000)
2,591 (# 0.252)
Table 3: Contextual bandit: d= 50
Metbod
Level of confidence
0.8
0.85
0.9
Avg. Coverage 0.744 0.436)
Avg. logl Volumm))
Avg. Coverage
Avg. (Vllum))
Avg. Coverage
Avg. logí Volumn)
ALEE
72,759
1.403)
0.809 0.393)
73,680 1.403)
0,875 (d: 0,331)
74.822 (::: 1.40%)
OLS
0.730 (d:: 0.444)
44.640 (5: 1.370)
0.791 (3: 0.407)
45.560 (1: 1.370)
0.847 (1: 0.360)
46.703 (å 1.370)
W- Decorrelation
0.192 0.394)
97.559 (# 1.337)
0.225 0.488)
98.479 1.357)
0.276 (#: 0.447)
99.622 (#: 1.337)
Concentraiion
1.000 (#: 0.000)
90.964 (= 1.312)
1.000 0.000)
91.004 1,312)
1,000 (#: 0.000)
91.060 (#: 1.312)
C.3 Asymptotic normality with centered Poisson noise variables
Distribution of errors in AR(1)
Distribution of errors with E-greedy
AT,, 1)
^TO, 1
OLS
OLS ALEE
ALEE
-3
-3
-2
-1
Figure 4: Same setting as Figure but with noise variables {ee) distributed as centered Poisson(1) (). We set = 3000 and the number of replications is set to 1000. The simulations show that the asymptotic distribution of ALEE is good accordance with the asymptotic normality proved in Corollary 3.5 and Theorem 3.1.
22


Reviews:
[{"review_id": "MLGN7NI2y4", "reviewer": "Reviewer_Z7he", "summary": "This paper introduces a general method for constructing debiased estimator within the context of sequential data collection. The proposed methodology is applied explicitly to multi-arm bandits, autoregressive time series, and contextual bandits. Experiments are conducted in these three domains to verify the applicability and effectiveness.", "questions": "In Figures 2 and 3, what do “lower tail coverage” and “upper tail coverage” represent? ", "limitations": " Limitations are not mentioned, and the potential negative societal impact is not addressed.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe proposed method is able to achieve asymptotic normality without knowing the data collection algorithm and can obtain a faster convergence rate of the bias term.\n2.\tPointwise and interval estimates can therefore be generated.\n", "weaknesses": "The experiment section only contains synthetic results. Considering the broad application of sequential data collection, it would greatly enhance the study if the authors could validate their framework using real-world datasets. This could provide more practical insight into the effectiveness of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere appreciation to the reviewer for dedicating the time to reviewing our paper and offering us valuable feedbacks. We truly appreciate your comments and suggestions, and believe they can make our work better.\n\nIn the following, we are going to take this opportunity to address each of the points raised in your review, in the order in which they were presented.\n\n**Weaknesses:** Thank you for your suggestion, and we agree with the reviewer that incorporating additional numerical/real data simulations will enhance the appeal of the paper. In the current version of the paper, we have primarily focused on simulated experiments. The use of simulated experiments allows us to establish a known ground truth, making it easier to compare the utility of different methods.\nIn the revised version of the paper, we plan to supplement the existing simulations with new ones involving different noise variables, such as mean-centered Poisson and Gamma noise variables. These additional results will align with the findings presented in the paper (please refer to Figure 1). Furthermore, we intend to include a real data example and assess the performance of various methods on it. While real data examples lack a known ground truth, comparing the confidence interval widths of different methods will be beneficial in evaluating their effectiveness. We extend our gratitude to the reviewer once again for this excellent suggestion.\n\n**Questions:**  Thank you for your question. Lower tail coverage represents whether the lower one-sided confidence interval, which has the form$(-\\infty, a)$, can cover the true parameter. Upper tail coverage corresponds to the upper one-sided confidence interval, which has the form $(a, \\infty)$. \n\n**Limitations:**  We apologize for not including the limitation part and not addressing the potential negative societal impact.  We are going to add them in the final version. Thank you for your suggestion."}, {"review_id": "7XmKLhw9Xt", "reviewer": "Reviewer_ADJL", "summary": "This paper proposes an estimator (ALEE) for adaptively collected data generated from adaptive linear models, describes its construction such that asymptotic normality holds for practically relevant examples, and demonstrates its desirable properties in numerical experiments.", "questions": "- One novelty of the paper is that Eq (3) is weaker than sub-Gaussian, yet all experiments are for Gaussian noise. I would be more convinced if the numerical simulations shows the same desirable properties for non-Gaussian noise.\n\n- Perhaps refer to Fig 1 from the main text?\n\nSome minor typos I find:\n\n- Refs 14&15 are identical\n- l51 - _debaising_ → debiasing\n- l98 - _Slutsy's theorem_ → Slutsky's theorem", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I enjoy reading this paper. It reads well. \n\n- The problem of inference for adaptive data is practically relevant\n- Theoretical guarantees assume somewhat weaker assumptions than previous works\n- The proposed method provides an improvement over other approaches, at least in the numerical experiments shown", "weaknesses": "I don't think this submission lacks anything for a NeurIPS paper", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere appreciation to the reviewer for dedicating the time to reviewing our paper and offering us valuable feedbacks. We truly appreciate your comments and suggestions, and believe they can make our work better.\n\nIn the following, we are going to take this opportunity to address each of the points raised in your review, in the order in which they were presented. \n\n**Strengths and weaknesses:**  we are glad that you enjoy reading this paper and thank you so much for your kind words.\n\n**Questions:** \n\nThank you for your suggestion. We conducted simulations with mean-centered Poisson, Gamma, and Bernoulli noise variables. The results obtained using these noise variables align with what we have presented in the paper (please see Figure 1 from the paper). In the final version of the paper, we plan to include these simulations. We believe that these additional numerical validations will enhance the appeal of the paper, and we sincerely appreciate the reviewer for providing this valuable suggestion.\n\nLastly, thank you for catching the typos, we will correct them in the final version. \n\n\n\n"}, {"review_id": "U4sfhvsj8U", "reviewer": "Reviewer_M8Ec", "summary": "This paper considers the problem of least squares when the data is collected sequentially. It proposes a form of weighted least squares where the weights are designed to lead to estimates that are asymptotically normal and nearly optimal variance. The appropriate weights are derived for the multi-arm bandit, autoregressive, and context bandit settings. Experimental results on some toy datasets confirm the theory.", "questions": "Please see above.", "limitations": "The paper is largely theoretical, so I think it's fine that the authors don't include a broader impacts section. However, I think the authors should include something about the limitations of the current work (see previous sections).", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The proposed estimator is simple and nearly efficient.\n2. Therefore, I think it would be useful for practitioners.\n3. The problem is well-motivated.\nI am not familiar with the literature on this problem, so I cannot comment on originality.", "weaknesses": "1. The presentation is somewhat confusing at times. The matrix $A$ from Section 2 does not appear in Section 3. The general construction strategy in Section 3.1 does not seem to be applied in Section 3.3 and it's not clear why. \n2. The examples used in the experiments are all very simple. It would strengthen the work to, for example, vary the number of arms/dimension.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere appreciation to the reviewer for dedicating the time to reviewing our paper and offering us valuable feedbacks. We truly appreciate your comments and suggestions, and believe they can make our work better.\n\nIn the following, we are going to take this opportunity to address each of the points raised in your review, in the order in which they were presented.\n\n**Weakness:** \n\nWe apologize for any confusion caused by our presentation, and we would like to clarify certain aspects of the paper to make it clearer.\n\n1. A benefit of using $A_w$ is that it allows for a better evaluation of the efficiency of the ALEE estimator, and it also serves as motivation for constructing weights $w_t$ with desirable properties (see equations (10) and (11)). We would like to highlight that the matrices $A_w$ and $W^\\top X$ yield the same variance asymptotically, meaning that $A_w^\\top A_w =   X^\\top W W^\\top X + \\text{ lower order term}$, and consequently, they can be used interchangeably; see the discussion near equations (8) and (9) where we already discuss the utility of using the matrix $A_w$. In section 3 onwards, we use the matrix $W^\\top X$ because it is easier to understand. We sincerely appreciate the reviewer for bringing this to our attention, and we will add additional clarification to the paper to highlight the utility of the matrix $A_w$. \n\n 2. We thank the reviewer for this careful observation. In Section 3.1, we consider the multi-armed bandit problem, where the problem is ``effectively\" one dimensional due to the orthogonality of the columns of the data matrix $X$. In dimension $d = 1$, we can do nice manipulations to the variance term which allows us to simplify the asymptotic variance term, and the resulting corollaries are much more informative and interpretable.   In Section 3.3,  we tackle the general contextual bandit problem, where the columns of the columns of the data-matrix matrix $X$ are no longer orthogonal, and we had to develop ideas that apply to dimension $d > 1$. This is why the constructions in section 3.1 and section 3.3 --- although they have same goal --- are very different.   \n\n3. We conducted some additional simulations with different noise variables (mean-centered Poisson, Gamma, and Bernoulli noise variables) and for various dimensions and parameter values. The results obtained using these settings align with what we have presented in the paper. In the final version of the paper, we plan to include these simulations. We believe that these additional numerical validations will enhance the appeal of the paper, and we sincerely appreciate the reviewer for providing this valuable suggestion.\n\n**Limitations:** Thank you for your suggestions. We apologize for not including the limitation of the work and will add it in the final version of  the paper.\n\n"}, {"review_id": "S3zDYm712k", "reviewer": "Reviewer_G4km", "summary": "The authors propose a general method for constructing debiased estimator called Adaptive Linear Estimating Equations (ALEE) estimator, which achieves asymptotic normality even in sequential data collection.\n\nTo obtain valid statistical inference, the online debiasing concept is used. The online debiasing procedure guarantees asymptotic reduction of bias to zero, but the convergence speed is slow. However, the ALEE estimator solves the slowly decreasing bias problem.\n\nIn this paper, the stable weights of ALEE are proved through equations for three cases: multi-arm bandits, autoregressive time series, and contextual bandits. A comparison of the ALEE method confirms that it performs better than the previous method.", "questions": "Table 1: OLEE typo (ALEE), and Table 1 seems to lack explanation.\n", "limitations": "- ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- ALEE provides point and interval estimation based on the central limit theorem, which enables stable estimation. It also prove the stability condition of ALEE through formulas for stable weights in three cases (Multi-arm bandits, Autoregressive time series, and Contextual bandits), which increases the efficiency of ALEE. Based on this stability and efficiency, we expect that it can be applied to various models.\n\n- ALEE's training algorithm has fast convergence. The authors provide theoretical performance guarantees and demonstrate ALEE's effectiveness on distributed time series forecasting problems with several examples.\n", "weaknesses": "- In the numerical experiments, the results are only shown using parameter values of 0.3 and 1 for the two-armed bandit setting and the contextual bandit setting. It would be better if used the various values for the parameters.\n\n- Lack of explanation for Table 1.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere appreciation to the reviewer for dedicating the time to reviewing our paper and offering us valuable feedbacks. We truly appreciate your comments and suggestions, and believe they can make our work better.\n\nIn the following, we are going to take this opportunity to address each of the points raised in your review, in the order in which they were presented.\n\n**Weakness:**\n\n1. We performed additional simulations across multiple dimensions and parameter values, incorporating different distributions for noise variables such as mean-centered Poisson, Gamma, and Bernoulli. The outcomes obtained under these settings align with the findings already presented in the paper. We intend to incorporate these simulations into the final version of the paper, as we believe that these additional numerical validations will further strengthen the appeal of the paper. We are grateful to the reviewer for offering this valuable suggestion.\n\n2. Thank you for bringing this up. We are going to add more explanations of Table 1 in the final version.\n\n**Questions:**\n\nThank you for catching the typos. We will correct it in the final version."}]

Author rebuttal:
Due to the page limit, we only include part of the updated simulations. Please see attached pdf file for simulations regarding different distributions for the noise variables and varying dimension $d$ for the contextual bandit example.

We plan to add limitation in the discussion section.

**Limitations:** In our paper, we propose ALEE estimator that achieves asymptotic normality and discuss its optimality. Our result is based on large samples and it would be interesting to investigate how to improve the efficiency of ALEE framework under finite samples.

Meta-review: Statistical inference on data collected by sequential data collection algorithms such as bandit algorithms is a topic of much contemporary relevance and interest. This paper considers an adaptive linear model and proposes an adaptive-linear-estimation-equations based approach that corrects for the bias in the ordinary least squares (OLS) solution. It is a very nice case of merging asymptotic normality arguments with finite sample concentration inequalities. All reviewers are unanimous in recommending acceptance.
Decision: Accept (poster)