Experimental Designs for Heteroskedastic Variance
Authors: Justin David Naggar Weltz
Tanner Fiez
Alexander Volfovsky
Eric Laber
Blake Mason
Houssam Nassif
Lalit K Jain
Venue: NeurIPS 2023 poster (2023)
Keywords: Heteroskedastic Variance
Linear Bandits
Experimental design
TL;DR: We make novel contributions to heteroskedastic variance estimation and experimental design in flexible settings.

Abstract: Most linear experimental design problems assume homogeneous variance, while the presence of heteroskedastic noise is present in many realistic settings. 
Let a learner have access to a finite set of measurement vectors $\mathcal{X}\subset \mathbb{R}^d$ that can be probed to receive noisy linear responses of the form $y=x^{\top}\theta^{\ast}+\eta$. 
Here $\theta^{\ast}\in \mathbb{R}^d$ is an unknown parameter vector, and $\eta$ is independent mean-zero $\sigma_x^2$-sub-Gaussian noise defined by a flexible heteroskedastic variance model, $\sigma_x^2 = x^{\top}\Sigma^{\ast}x$. Assuming that $\Sigma^{\ast}\in \mathbb{R}^{d\times d}$ is an unknown matrix, we propose, analyze and empirically evaluate a novel design for uniformly bounding estimation error of the variance parameters, $\sigma_x^2$. 
We demonstrate this method on two adaptive experimental design problems under heteroskedastic noise, fixed confidence transductive best-arm identification and level-set identification and prove the first instance-dependent lower bounds in these settings.
Lastly, we construct near-optimal algorithms and demonstrate the large improvements in sample complexity gained from accounting for heteroskedastic variance in these designs empirically.

Experimental Designs for Heteroskedastic Variance
Justin Weltz" Tanner Fiez! Eric Laber Alexander Volfovsky
Blake Mason 1 Houssam Nassif Lalit Jain
Abstract
Most linear experimental design problems assume homogeneous variance, even though heteroskedastic noise is present in many realistic settings. Let a learner have access to a finite set of measurement vectors X C R that can be probed to receive noisy linear responses of the form y x TO parameter vector, and is independent mean-zero o2-strictly-sub-aausii
0r + 1). Here 0" E IR is unknown
noise T Σ æ. Assuming that E' E Rdxd is an unknown matrix, we propose, analyze and empirically evaluate a novel design for uniformly bounding estimation error of the variance parameters, o. We demonstrate the benefits of this method with two adaptive experimental design problems under heteroskedastic noise, fixed confidence transductive best- arm identification, and level-set identification; proving the first instance deeendeen lower bounds in these settings. Lastly, construct near-optimal algorithms and empirically demonstrate the large improvements in sample complexity gained from accounting for heteroskedastic variance in these designs.
defined by a flexible heteroskedastic variance model, o² = x
Introduction
Accurate data analysis pipelines require decomposing observed data into signal and noise components. To facilitate this, the noise is commonly assumed to be additive and homogeneous. However, in applicd fields this assumption is often untenable, necessitating the development novel design and analysis tools. Specific examples of deviations from homogeneity include the variability in sales figures of different products e-commerce 31]. the volatility of stocks across sectors (5), spatial data (58) 4 and genomics
48 10]. This heteroskedasticity is frequently structured as function of observable features. In this work, we develop two near-optimal adaptive experimental designs that take advantage of such structure.
There are many approaches, primarily developed the statistics and econometrics literature, for efficient mean estimation in the presence of heteroskedastic noise (see [56] [6] for survey). These methods concentrate on settings where data have already been collected and do not consider sampling to better understand the underlying heteroskedasticity. Some carly work exists experimental design in the presence of heteroskedastic noise, however these methods are non-adaptive (see Section 2 for details). Importantly, using naive data collection procedures designed for homoskedastic environments may lead to sub-optimal inference downstream (see Section 1.2 for examples). A scientist may fail take samples that allow them observe the effect of interest with fixed sampling budget, thus wasting time and money. This work demonstrates how to efficiently and adaptively collect data
Department Statistical Science, Duke University, justin. weltz @dukeduuukeuuue work conducted Amazon Amazonncom, USA, fieztann @amazon.comm
I Department Statistical Science, Duke University, cric.laherddukee
$ Department of Statistical Science, Duke University, dlexander. wow.eroooooooooooooeee....... Amazmm..com com, USA, bjmason amazon.com
|l Meta, USA, houssamn @ meta.com
Miichael G. Foster School Business, University Washington, lalitj uw.edu, work conducted at Amazon
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

in the presence of heteroskedastic noise. It bridges the gap between heteroskedasticity-noo robuust (but potentially inefficient) passive data collection techniques, and powerful (but at times brittle) active algorithms that largely ignore the presence of differing variances.
1.1 Problem Setting
To ground our discussion of heteroskedasticity in active data collection, we focus on adaptive experimentation with covariates; also known pure-exploration linear bandits 45) Let a learner be given finite set of measurement vectors X' C IR span(2') R which can be probed to receive linear responses with additive Gaussian noise of the form:
= 0 0 +1 with 1 ~~,
of = x L
Here, 0" E Rdd is an unknown parameter vector, 7) is independent mean-7ero Gaussian noise with variance 2h = x E"', and Σ* E IRddd is an unknown positive semi-definite matrix with the assumption that o I o S o max for all x X, where max: o2 > are known. We focus on Gaussian error for ease of exposition but extend to strictly sub-Gaussian noise in the Appendix. The linear model in Eq. ([) with unknown noise parameter Σ directly generalizes the standard multi-armed bandit to the case where the arms have different variances 4.. Additionallyy this heteroskedastic variance structure arises naturally in linear mixed effects models (20), which are used in variety of experimental settings to account for multi-leve! heterogeneity (patient, spatial and block design variation [41).. Throughout, Z C Rd will be a set (that need not be equal to X' over which our adaptive designs will be evaluated. While the theory holds true for o miy I 5. S o o in general, we consider the case where o = m x and oi = mingex dg so that K == d / /o summarizes the level of heteroskedasticity.
1.2 Heteroskedasticity Changes Optimal Adaptive Experimentation
To underscore the importance of adapting to heteroskedasticity, we consider the performance of RAGE [12] a best arm identification algorithm designed for homoskedastic settings. This algorithm does not account for differing variances, so it is necessary to upper bound o S o for each x to identify the best arm with probability 1 - for E (0, 1). In Fig. [ we compare this approach to the optimal sampling allocation accounting for heteroskedasticity in setting that is a twist on standard benchmark [66] for best-arm identification algorithms. Let X' = 2 C R and |X| = 3. We take (cos(0.5)) (0.5).
I1 61 and 22 C2 to be the first and second standard bases and set 23 Furthermore, we take 8* = e₁ such that Fj has the highest reward and F3 has the second highest. In the homoskedastic case, an optimal algorithm will focus sampling 22 because it is highly informative for distinguishing between 21 and I3 as shown in Fig [b However, if the errors are heteroskedastic, such a sampling strategy may not be optimal. If 02 01, T3, the optimal allocation for heteroskedastic noise focuses nearly all samples on 1 and æ3 (as shown in Fig. [a). which are more informative than I2 because they have less noise. Hence, ignoring heteroskedasticity and upper- bounding the variances leads to suboptimal sampling allocation and inefficient performance. This effect worsens as the amount of heteroskedasticity increases, leading to an additional multiplicative factor of π (cf., [2], Thm. 1) as demonstrated in Fig. [c] In this important example, we see that the sample complexity of an algorithm that ignores cetatiskedasticity suffers linear dependence on K. while a method that adapts to the heteroskedasticity in the data does not.
1.3 Paper Contributions
1. Finite Sample Noise Estimation Guarantees. We use an experimental design technique to construct estimates of the heteroskedastic noise variances with bounded maximum absolute error. This adaptive experimental design is a two-phase sample splitting procedure based on a pair of distinet G-optimal experimental designs 28 with bounds that scale favorably with the underlying problem dimension.
2. Near-Optimal Experimental Design Algorithms. We propose adaptive experimental design algorithms for transductive linear best-arm and level-set identification with heteroskedastic noise, that combine our variance estimation method with optimal experimental design techniques. We prove sample complexity upper bounds for unknown Σn that nearly match instance dependent lower bounds when V" is known. Importantly, we show that in contrast to naive methods which

---

0.6
Oradle Sample Complextty
2000
Hetorodkecartt
0.4
088
2000
Density
0.3
Density
0.5
64
0.2
1000
0.1
500
0.0
0.
(a) Hetcroskedastic design
Homoskedastic design
(c) Sample complexity increases
We compare the sampling strategies of algorithms that do and do not account for heteroskedastic variance in Figs. Ta and Tb respectively, when 20. Figure Ic shows that the gap in the optimal sample complexity between the two algorithms becomes linear as x: increases.
Figure 1:
have multiplicative dependence K, we only suffer an additive dependence. Lastly, we show that the theoretical improvements translate to stronger empirical performance.
Related Work
Experimental Design and Active Learning for Heteroskedastic Regression. Many experimental
design methods for heteroskedastic regression assume known weights (or efficiency functions) [55]
54
Procedures that estimate the heteroskedastic variance focus optimizing the design for the
weighted least squares estimator given burn-in period used to estimate the noise parameters [37 [3
52
These contributions assume that the variance is unstructured, which leads to sample complexities
that scale with the number of arms. Similarly, past active learning work on linear bandits with heteroskedastic noise either assume the variances are known (30 62], or that the variances are The works that assume structured heteroskedasticc noise in a linear bandit framework focus active maximum likelihood estimation and G-optimal design 77 45), but do not exploit the structure of the heteroskedastic noise to improve performance, leading to complexities scaling poorly in the problem dimension. Lastly, Mukherjee et al. (38) study policy value estimation under the reward model described in Eq. T However, their variance estimator is different from ours.
unstructured 14,
Best-Arm and Level Set Identification in Linear and Logistic Bandits. Best-arm identification is a fundamental problem in the bandit literature [3 46 [8] Soare [44] constructed the first passive and adaptive algorithms for pure-exploree exploratooot in linear bandits using G-optimal and X''-allocation experimental designs. Fiez et al. [1] built on these results, developing the first pure exploration algorithm (RAGE) for the transductive linear bandit setting with nearly matching upper and lower bounds. Recent work specializes these methods to different settings [47] 57 25] 26), improves time complexity [60 50, 33), and targets different (minimax, asymptotically optimal, etc.) lower
bound guarantees [59 22 9. In the level set literature, Mason et al. (35) provides the first instance optimal algorithm with matching upper and lower bounds. Critically, none of these contributions account for heteroskedastic variance. Finally, we note the connection between this work and the logistic bandits literature 23 1 36] In that setting, the observations Bernoulli random variables with probability given by P(y = 1|z) = exp(=x' {0))} for x E R4, 0 E Rd and y E {0, 1}. Because of the mean-variance relationship for Bernoulli random variables, points x for which (v 1|x:) is near 0 or 1 have lower variance than other z's. While the tools are different these two cases, we highlight two common ideas: First, Mason et (36) present method that explicitly handles the heteroskedasticity in logistic bandits. Second, a core focus of optimal logistic bandit papers is reducing the dependence on the worst case variance to only an additive penalty, similar to the guarantec of k herein, which has been shown to be unavoidable in general [23].
3 Heteroskedastic Variance Estimation
In this section, we describe an algorithm for heteroskedastic noise variance estimation with error bounds that scale favorably in the problem dimension. We then evaluate this method empirically.

---

Given a sampling budget I, our goal is to choose {ar C X to control the tail of the maximum absolute error (MAE): max,ex oo o by exploiting the heteroskedastic variance model. Alg. [ HEAD (Heteroskedasticity Estimation by Adaptive Designs), provides an experimental design for finite-time bounds on structured heteroskedastic variance estimation.
Notation. Let M := d(d + 1)/2. Define W = {Φz, V E 2} C RM where du vec(ar G and G' E x is the duplication matrix such that G vech xxx
vec(xx ), with vech(-) denoting Lven 1, A 2 0 V v) denote distributions over V/ and V(V) = fv' - v U. E V. v o e0) represent the differences between members set
the vellr-ecctoiization. For set V. let Pv == {} R M
General Approach. Given observations from = x 0 + + for 1 E (1,2,..., and the true value of 8* we can estimate o² for each a E X from the squared residuals n/ = (y -x, 8²)² (e.g.. using method of moments another estimating equation approach [15]). However, since 0 is not known, we cannot directly observe n/,- making estimation of o² more difficult. Consider a general procedure that first uses r' r/2 samples from the budget construct least-squares estimator for H*, 0r/2, and then uses the final 7/2 samples to collect enror estimates of the form of = (yt xy 0r/2)² Define Φr E RT/2XM as a matrix with rows (6a, Her.)22224 and î) E IR 1/2 as a vector with values (f: T/2411 With 77, we can estimate Σ" by least squares as
vech (Er) arg min |r 1?1 SERA
where we minimize over the space of symmetric matrices. Splitting samples ensures that the errors in estimating 0 and Σ' are independent. Note that (Er, 0r/2) is an M-estimator of (Σ", derived from unbiased estimating functions, common approach in heteroskedastic regression [21 51 34). Finally, by plugging in the estimate of l,, one can obtain an estimate of the variance, 6 = min[max(zz Eræ, m ) max) decomposition for any æ E X' with == o_ (0] -1
We show that this approach leads the following general error
lx T0= (E' (Eral) s for (Or/22 13} +
Σ t=T/2
Zt (Ti
I E Mxx;))
Σ 1=1/2
2 T (Ør/2 0" me
Experimental Design for Precise Estimation. The analysis above gives an eтror decomposition for any phased con-adaptive data collection method that splits samples between estimation 6" and Σ. Intuitively, we wish to sample (zi...., 2ry2) and { Fr} to control the maximum absolute error by minimizing the expression above. We achieve this via two phases of G-optimal experimental design 28 first over the X' space to estimate 0", and then over the W space to estimate E* Precisely, we control quantity A via stage of Alg. which draws from G-optimal design to minimize the maximum predictive variance
{ (0r/2 - -0))
max E X
Quantity is another sub-exponential quantity (Definition B.2 in Appendix [B, which we control by drawing from a G-optimal design Ao over W to minimize max Φ (0, (r) - Finally, C is controlled by combination of the guarantees associated with X" and At. This leads to the following error bound on 5 = min { max Er Ii 3,o
Theorem 3.1. Assume r = Ω Imax fo log( ()g(( d.). For any X and 5 (0. 1), Alg. guaranttess the following:
P ( - of S Cr,s) 2 5/2 where ( max P//T
The proof of Theorem 3.1 is in Appendix and follows from the decomposition in Eq. treating A,
B and C as sub-exponential random variables with bounds that leverage the experimental designs of Alg. П The details the constants involved in Theorem 3.1 are also included in Appendix D

---

Algorithm 1: HEAD (Heteroskedasticctt Estimation by Adaptive Designs)
Result: Find Er
IIput: Arms X' E Rd R E
2 //Stage 1: Take half the samples to estimate 0"
3 Determine X according to X = arg minxeey max T (Enrex ) -1
x
4 Pull arm 2 E X [X/T/2] times and collect observations {Iz, yt 1/2
5 Define === >
1//2 Za4t and 1y -I Tilh/ and estimate 0ry2 A A
6 //Stage 2: Take half the samples to estimate E" given 0
7 Determine Xt X1 arg argminxer. max of (Ea'ex 22 &z
8 Pull arm & E X [2] time and collect observations (Ix, Dt 1
9 Let At Ei-r/2+1 Por D2 - tae (v: J4 0r/2)
10 Output: vech(Ep) = At
Note that we design to directly control the MAE of T.. This in contrast to an inefficient alternative procedure that allocates samples to minimize the error of Eg in general, and then extends this bound to x E z for x E X.
Theoretical Comparison of Variance Estimation Methods. In contrast previous approaches that naively scale in the size of X' (14), the above result has a dimension dependence of d², which intuitively scales with the degrees of freedom of Σ² To highlight the tightness of this result, consider estimating the noise parameters for each arm, x E X. only using the samples of x (like the method in (14). We improve this approach by adapting it to our heteroskedastic variance structure and strategically pick d² points to avoid the dependence on |. We refer to this method as the Separate Arm Estimator, and in Appendix D we show that suffers dependence of dt This comparison
point, along with our empirical results below, suggest that the eтror bounds established in Theorem 3.] scale favorably with the problem dimension.
Empirical Comparison of Variance Estimation Methods. Define two sets of arms X1, A2 such that x E 2₁ is drawn uniformly from a unit sphere and X2 is drawn uniformly from sphere with radius 0.1; with | = 200 and [2²] = 1800. Let Σ* = diag(1, 0.1, 1,0.1., E dRadd and 0" = (1, II.., 1) E Rd This setting provides the heteroskedastic variation needed to illustrate the advantages of using HEAD (Alg. MT. An optimal algorithm will tend to target orthogonal vectors in X1 because these arms have higher magnitudes in informative directions. Defining X' = X1 U X2, perform 32 simulations in which randomly sample the arm set and construct estimators for each o² I E X' We compare HEAD, the Separate Arm Estimator, and the Uniform Estimator (see Alg. 3 in Appendix D). The Uniform Estimator is based on Alg. [ but samples arms uniformly from X' and does not split samples between estimation of 0 and Σ". HEAD should outperform its competitors in two ways: 1) optimally allocating samples, and 2) efficiently sharing information across arms in estimation. The Uniform Estimator exploits the problem structure for estimation but when sampling. In contrast, the Seperate Arm Estimator optimally samples, but does not use the relationships between arms for estimation. Fig. 2 depicts the average MAE and standard errors for each estimator. In Fig. 2a we see that HEAD outperforms its competitors over series of sample sizes for d = 15. Fig. 2b compares the estimators over a range of dimensions for a sample size of 95k. While HEAD continues accurately estimate the heteroskedastic noise parameters high dimensions, the Separate Arm Estimator error scales poorly with dimension as the analysis suggests.
4 Adaptive Experimentation with Covariates in Heteroskedastic Settings
As an application of the novel sampling procedure and resulting variance estimation bounds developed in section 3 we now study adaptive experimentation with covariates the presence of heteroskedastic
As 1/2 & N. it is not possible in reality to take X,1'/2 samples. This problem can easily be handled by rounding procedures detailed in Appendix A
5

---

HEAD Estimator
Separate Am Estimatcr
fnforrm Estimator
0.6
Nax Alcoluta Ergs
0.3
0.2
0.2
0.1
0.0
00000
5000E
60000
20000
Sample
(a)
(b)
Figure 2: The proposed experimental design estimator outperforms competitors terms of maximum absolute enror X o 0 over a range sample sizes (a) and dimensions (b).
noise through the lens of transductive linear identification problems [1]] Recalling the problem
setting from Section 1.1 we consider the following fixed confidence identification objectives:
1. Best-Arm Identification (BAI). Identify the singleton set {2*} where x" arg max 2 8".
2. Level-Set Identification (LS). Identify the G. {= 2 T a) given threshold E IR.
This set of objectives, together with a learning protocol, allow us to capture a number of practical problems of interest where heteroskedastic noise naturally arises in the assumed form. Consider The expected feed-
multivariate testing problems e-commerce advertisement applications 17 (3).
back is modeled through linear combination of primary effects from content variation dimensions (e.g., features or locations that partition the advertisement), and interaction effects between content variation in pairs of dimensions. The noise structure is naturally heteroskedastic and dependent on the combination of variation choices. Moreover, the transductive objectives allow for flexible experimentation such as identifying the optimal combination of variations or the primary effects that exceed some threshold. We return to this setting in Experiment 3 of Section [5] In the remainder of this section, we characterize the optimal sample complexities for the heteroskedastic transductive linear identification problems and design algorithms that nearly match these lower bounds.
4.1 Linear Estimation Methods with Heteroskedastic Noise
To draw inferences the experimentation problems of interest, is necessary consider estimation methods for the unknown parameter vector 0* E IRd. Given a matrix of covariates X E IR Igx'4 vector of observations Yr E IR and user-defined weighting matrix WT diag( (1,..., WT) xT the weighted least squares (WLS) estimator is defined as:
ÖWISS (X W, minger ||
X liv
Let Σx = diag(o² ..., xT
IR Txx denote the variance parameters of the noise observa- tions. The WLS estimator is unbiased regardless of the weight selections, with variance
v (BWLs) (XIWTXT) X.I.TErWJJ. Xr (XJ WTXT) Wr (XTT2T Xr)
The WLS estimator with WT = Enj' is the minimum variance linear unbiased estimator (2) In contrast, the ordinary least squares (OI.S) estimator, obtained by taking WT in the WL. estimator, is unbiased but with higher variance,
v (DOts) (XIxx)) x (xTxxT) 2 (T)
Consequently, WLS is natural choice with heteroskedastic noise for sample efficient estimation.
4.2 Optimal Sample Complexities
We now motivate the optimal sample complexity for any algorithm that returns the correct quantity with fixed probability greater than 1 ó, 8 (0, 1), in transductive identification problems with

---

heteroskedastic noise. We seek to identify a set of vectors HOBJ, where
MBAI {2*} farg max x 0*) and His = {z E 2 : 0 0}. #E2
Algorithms consist of sampling strategy and a rule return set H. time
Definition 4.1. An algorithm is Ó-PAC for OBJ E (BAI, LS) ir o, Po HOBJ) ) 2
Throughout, will only consider algorithms that are 6-PAC. For drawing parallels between best-arm and level set identification, will be useful to define set of values ΩOBJ, where
ΩBAI (= 2, =²) and QLs = (0),
and a constant bOBJ such that GBAI and PLs a. Both problems amount to verifying that for
all h E HORJ and QORJ, (h - 7) Owi.s bORJ, equivalently (h q) TT)To 0 boRs (h
q) (0+ @WLs) O. Using sub-Gaussian tail bound and union bound [2). this verification
requires the following to hold for all h E HOBI and q COBJ for the data collected:
1(h 4) (0* OwI.s))
V 211 (Bwrs) log log(2|21/6) (h g)T 0" bOBJ-
Let A denote the proportion T samples given to measurement vector a E X' so that when Wr 2n in Eq. 44.1.
V (DWLS) (x)
xx
/T
oEx
as in Eq. 2). Now, we reformulate the condition in Eq. 33) and minimize over designs À E Px to that 6-PAC verification requires
|| 9113 (I Ar 2
T 2/B l)g(2 where V'BB
min max EEOB
XePx Ho QoBT
((h ( T bOBJ}
(4)
This motivating analysis gives rise to the following sample complexity lower bound. Theorem 4.1. Consider an objective, OBJ, of best-arm identification (BAI) or level-set identification (L.S). For any (0, 1), 5-PAC algorithm must satisfy
E 2 2 llgglo//..//o
Remark 4.1. This lower bound assumes that the noise variance parameters are known. We compare to the existing lower bounds for the identification objectives with homoskedastic noise [12
35
in Appendix G These apply in this setting by taking the variance parameter o² a and are characterized by an instance-dependent parameter, POBJ such that x S V/ /POBJ (recall that K := / m. In general, λ can be quite large in many problems with heteroskedastic noise. Consequently, this implies that near-optimal algorithms for linear identification with homoskedastic noise can be highly suboptimal (by up to a multiplicative factor of k) in this setting.
4.3 Adaptive Designs with Unknown Heteroskedastic Variance
We now present Alg. H-RAGE (Heteroskedastic Randomized Adaptive Gap Elimination), solution for adaptive experimentation with covariates in heteroskedastic settings. The approach is composed of two components: 1) Obtain accurate estimates of the unknown variance pa- rameters [xe) using HEAD: 2) Use adaptive experimental design methods for minimizing the uncertainty in directions of interest given the estimated variance parameters. Denote by min ming Qoas (h - -q) T 0" boBJ the minimum gap for the objective and assume max,ez, (2 2", -- 2. We prove the following guarantees for Alg. 2
Theorem 4.2. Consider an objective, OBJ, of best-arm identification (BAI) or level-set identification (LS). The set returned from Alg. 2 at time is 6-PAC and
O (toBJ log(4 A 11) [log( Z /8) + log (A ")} log(A -AA--')d 'dd 1og(1x(100xx2d)
7

---

к relative Algorithm 2: (H-RAGE) Heteroskedastic Randomized Adaptive Gap Elimination
Result: Find x" == arg max 2 TT 8" for BAI or G = {= E : 0" > a} for LS
1 Input: E ER, E R confidence E 1). OBJ E {BAI.LS), threshold a E R Initialize: & <- 1, 21 Z. 91 + 0. B1 f 0
3 //Variance estimation
4 Call Alg. such that -- = min max Eræ, -in ) o max
02 S 502/2
5 while [| > 1 and OBJ=BAI) or (| > and OBJ=LS) do
//Determine the design
Let Te E Px be a minimizer of { (2,) if OBJ=BAI and g(>, 2x) if OBJ-LS where
7
(VV = infx {(>; V) = infx XeXx max || Erx
Set c2 = 2-2 T2 = 3r 2/(( 23) log log(8(1 /Determine stepsize
8
Pull arm x E X exactly [Te x times for ny samples and collect { Vt. nh
10
Define A = Ei= o
",,,x,,,, xe, be Din o, Ie, and construct 0g = A be
//El /'liminate arms
12
if OBJ is BAI then
Be+1 - ZAfz E Ze maxvez, - 2, > ac
13
else
G4+1 + L: 3 (2,01) 4 x>a} a}
15
16
B141 + B, (2 Z: (2, + <a)
17
2e41 f E/119 (4+1 (Bg B++1)
end
t +-1+1
20 end
Output: Z, for BAI Gr for LS
This result shows that Alg. ii nearly instance-optimal. Critically, the impact of not knowing the noise variances ahead of time only has an additive impact on the sample complexity relative to the lower bound. In contrast, existing near-optimal methods for identification problems with homoskedastic noise would be suboptimal by multiplicative factor depending to the lower bound. Given that the lower bound assumes the variances are known, an interesting question for future work is tighter lower bound assuming the variance parameters are unknown.
Remark 4.2.
Algorithm Overview. Observe that for V.B.I the optimal allocation depends on both the unknown gaps ((h - T) -aa--bbbaa bOBa) for h E HOBJ and E QOBJ, and the unknown noise variance parameters {or Lee To handle this, the algorithm begins with an initial burn-in phase using the procedure from Alg. to produce estimates ( Jaex of the unknown parameters {o]] trx,, achieving multiplicative error bound of the form 2 - o S / for all
X. From this point, the estimates (6)) >xx are used as plug-ins to the experimental designs and the weighted least squares estimates. In each round é E N of the procedure, we maintain a of uncertain items Z,, and obtain the sampling distribution de, by minimizing the maximum predictive variance the WLS estimator over all directions y h - q for h E HOBJ and g QOBJ- This is known in the best-arm and level set identification problems respectively. Critically, the number of samples taken in round & guarantees that the error in all estimates is bounded by e,, such that for any h E HOBJ and E QOBI. (h- q) 0 > 2e, is eliminated from the active set at the end of the round. By progressively honing in on the optimal item set HOBJ, the sampling allocation gets closer to approximating the oracle allocation.
X')'-allocation and
G-optimal-allocatiee
Experiments
We now present experiments focusing on the transductive linear bandit setting. We compare H-RAGE and its corresponding oracle to their homoskedastic counterparts, RAGE [2] and the oracle allocation

---

with noise equal to m RAGE is provably near-optimal in the homoskedastic setting and known to perform well empirically. The algorithm is similar in concept to Alg. 2 but lacks the initial exploratory phase to estimate the variance parameters. We include the pseudo-code of RAGE in Appendix H The homoskedastic and heteroskedastic oracles sample with respect to the optimal design with a sub-Gaussian interval stopping condition. All algorithms are run at a confidence level of 6 = 0.05, and we use the Franke-Wolfe method to compute the designs. We demonstrate that H-RAGE has superior empirical performance over a range of settings.
Linear bandits: Experiment (Signal-to-Noise). We begin by presenting an experiment that is variation of the standard benchmark problem for BAI in linear bandits [46] introduced in Sec. 1.2 Define e₁ E Rd as the standard basis vectors in d dimensions. In the standard example, X' = = == {er. e2, } where x' = {er cos(w) + 62 sin(w) for w + 0, and 0 = E1. Thus
e1 optimal, Z3 = x' is near-optimal, and x2 = 62 is informative to discriminate between I1 and zg-- We consider an extension of this benchmark in multiple dimensions that highlights the performance gains from accounting for heteroskedastic variance. First, define an arm set H that comprised of the standard example but with varied magnitudes. For E (0, 1),
H {(i) u {e2} U {q x e; e: U {er cos(w) + e sin(w)
Then define 9 to be series of vectors such that the rank of span (Øz E GUU)) R g allows for variance estimation. Finally, let the arm and item set be X' = GUU and 0 = E1.
We define Σ* as the d-dimensional identity matrix. Observe that æ1 en is optimal, the d - 1 arms given by {er cos(w) + e; sin(w)) are near-optimal with equal gaps A = 1 and the d 1 arms given by {e2] Uuq + { are informative to sample for discriminating between t1 = G1 and I2 = cos(w) + e, sin((W for each i E (2..... .d), respectively. To identify 21, we must estimate the A gap adequately in every dimension with arms (e2) U q {e:]==s Therefore, performing BAI without accounting for heteroskedastie variances will tend toward a design that prioritizes sampling informative arms {q X e, e since these have smaller magnitudes and seem less informative about the near-optimal arms in dimensions E {3, 4...d.. However, the signal to noise ratio is actually constant across arms (because the variance of q {ca (cr) is equal to q²) leading to oracle distribution that equally samples across {e2} } U q fe; )
account for heteroskedastic variances. This change in allocation is illustrated in Appendix H for d = 4, w = 0.01. q 0.4 and G (.5((e1 + e2) + 0.1eg, 0.5(c: + e2) + 0.1(es + e. In the same setting, Fig. Ba shows that the heteroskedastic variance experimental design and the tighter predictive confidence intervals of the weighted least squares estimator result in a large decrease in the sample size needed to identify the best arm.
when
Experiment 2: Benchmark. This experiment is also similar to the benchmark example introduced in Sec. 1.2 In this variation, the informative arms have the same magnitude but are bent at a 45 angle,
x== (e) U (ei cos(w) + e2 sin(w)) U (e) U ((e//2++ + e
Let the arm and item set be X Z and 0* e1- Experiment we have many near- near-optimal arms and H-RAGE reveals that each of these are equally difficult to distinguish from the best. In contrast, Experiment contains one near-optimal arm along with many potentially informative arms, and we are interested in identifying the one that is most helpful. Intuitively, Experiment 1 uses heteroskedastic variance estimates to assess the difficulty of many problems, while Experiment uses the same information to assess the benefits of many solutions. Let the unknown noise matrix be given by " = diag(o? of. .a......'' o²) where of = a², (o? o3) = 3 and (oī o ..., o²) = a². I1 E is again optimal and x2 {ei cos(w) + E2 sin(w)) ( is a near optimal arm. In this case, (ez/v2 + e U (e2/ /2 + e e / and the oracle allocation assuming homoskedastic noise (Homoskedastic Oracle) picks three of these vectors to sample. However, if a² >> 3², then it is optimal to sample {e2/v2 + e3/ 22/ e3) over other potential informative arm combinations. Appendix H shows this contrast in allocations for = 3, ~ = 0.01, a² = and 3² = 0.2. In the same setting, Fig. 3b shows that estimating and accounting for heteroskedastic noise contributes reduction in sample complexity.
informative for distinguishing between x1 and æz.
Experiment 3: Multivariate Testing. In this experiment, we return to the motivating example of Section 4 multivariate testing in e-commerce advertising [17 39 We divide an advertisement into natural locations or features called dimensions, each of which has different content options or variations. We induce heteroskedastic variance by allowing both the expected value and the variance

---

vaterossodasttoRAAA
RAGE
Hetoroskodastle Oracle
Horooskodastic Oracio
2.00
1.5
Sampe Complnitt
1.50
Sampli Complotty
122
1.00
840
Aigotitm
Algorthm
Algoritim
(a) Experiment
(b) Experiment 2
(c) Experiment
Figure 3: Experimental results show the mean sample complexity of each algorithm over 100 simulations with 95% Monte Carlo confidence intervals.
of an advertisement's reward to depend on the n variations in each of the m dimensions. Let X' Z denote the set of layouts corresponding to the combinations of variant choices in the dimensions so that | = n² The multivariate testing problem is often modeled in the linear bandit framework using the expected feedback for any layout X C (0,1) where = + given by
=2m(m + 1)/2,
x T = 03 (E Ej= 0f (isa)s)
ET Er EJ= Ej= (1
In this model, Fzij 10. }} is an indicator for variation j E (1,...,n) n) being placed in dimension i E (I...., m). and Σ5 Fi, = for E (I,...,77) n for any layout x E X. Observe that the expected feedback for layout is modeled as a linear combination of a common bias term, primary effects from the variation choices within each dimension, and secondary interaction effects from the combinations of variation choices between dimensions.
We consider an environment where the effect of variation changes in one dimension, call it di- mension j. has much higher variance than others; resulting the best variation for dimension being harder to identify. An algorithm that accounts for heteroskedastic variance will devote greater number of samples compare variations in dimension j. whereas an algorithm that up- per bounds the variance will split samples equally between dimensions, For simulation setting with 2 variations
dimensions, define E diag(0.3, 0.7, 10 1000.. ..... E 7 and 0" = (0, 0.005, 0.0075, 0.01. -0.1, 10.1..0.11.... variation each of the dimensions better than the first, but the positive effect in the first dimension hardest to identify. In Appendix H we can see that this causes the heteroskedastic oracle to devote more weight than the homoskedastic oracle vectors that include the second variation the first dimension. Fig-B3 depicts the improvement in sample complexity resulting from accounting for the heteroskedastic variances.
R This simulation setting implies that the second
Conclusion
This paper presents investigation of online linear experimental design problems with heteroskedas- tic noise. We propose two-phase sample splitting procedure for estimating the unknown noise variance parameters based on G-optimal experimental designs and show emror bounds that scale efficiently with the dimension of the problem. The proposed approach is then applied to fixed confidence transductive best-arm and level set identification with heteroskedastic noise, where present instance-dependent lower bounds with provably near-optimal algorithms.
This paper leads to a number of interesting future research directions. For example, there may be situations where the noise structure is not fully characterized by Σ*. Future work can explore the development of methods that handle more general noise structures (including correlated or heavy- tailed noise) while remaining nptrmo. Furthermore, it possible that an integrated approach to variance estimation and adaptive experimentation with covariates would be more sample efficient than our two-step method. Lastly, it would be interesting to extend our algorithm to nonlinear response models.
10

---

References
[1] Mare Abeille, Louis Faury, and Clément Calauzènes. Instance- wise minimax -optmmal- algorithms for logistic bandits. In International Conference Artificial Intelligence and Statistics, pages 3691-3699. PMLR, 2021.
[2] Alexander C Aitken. IV.-On least squares and linear combination of observations. Proceedings of the Royal Society of Edinburgh, 55:42 48, 1936.
[3] Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, and Yining Wang. Near-optimal discrete optimiza- tion for experimental design: A regret minimization approach. Mathematical Programming.
186:439-478, 2021.
[4] András Antos, Varun Grover, and Csaba Szepesvári. Active learning in heterosccdastic noise. Theoretical Computer Science, 41 (29-30):2212 12-222222222,, 2010.
[5] David Blitz and Pim Van Vliet. The volatility effect: Lower risk without lower return. Journal of portfolio management, pages 102-113 113, 2007.
[6] Romain Camilleri, Kevin Jamieson, and Julian Katz-Samuels. High-dimensional experimental design and kernel bandits. In International Conference on Machine Learning, pages 1227-1237. PMLR, 2021.
[7] Kamalika Chaudhuri, Prateek Jain, and Nagarajan Natarajan. Active heteroscedastic regression.
In International Conference on Machine Learning, pages 694-702. PMLR, 2017.
[8] Wesley Cowan, Junya Honda, and Michael Katehakis. Normal bandits of unknown means and variances. Journal of Machine Learning Research, 18(154):1-28 2018.
[9] Rémy Degenne, Pierre Ménard, Xuedong Shang, and Michal Valko. Gamification of pure exploration for linear bandits. In International Conference on Machine Learning, pages 2432- 2442. PMLR, 2020.
[10] Bianca Dumitrascu, Gregory Darnell, Julien Ayroles, and Barbara E Engelhardt. Statistical tests for detecting variance effects in quantitative trait studies. Bioinformatics, 35(2):200-25) 2019.
[11] Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. International Conference on Machine Learning, pages 3052-3060. PMLR, 2020.
[12] Tanner Fiez, Lalit Jain, Kevin G Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits, Advances in neural information processing systems, 32:10667-
-10677, 2019.
[13] Tanner Fiez, Sergio Gamez, Arick Chen, Houssam Nassif, and Lalit Jain. Adaptive experimental design and counterfactual inference. In Workshops of Conference Recommender Systems, 2022.
[14] Xavier Fontaine, Pierre Perrault, Michal Valko, and Vianney Perchet. Online a-optimal design and active linear regression. In International Conference on Machine Leurning, pages 3374- 3383. PMLR, 2021.
[15] VP Godambe and ME Thompson. Some aspects of the theory of estimating equations. Journal of Statistical Planning and Inference, 2(1):95-104, 1978.
[16] William H Greene. Econometric analysis. Pearson Education India, 2003.
[17] Daniel N Hill, Houssam Nassif, Yi Liu, Anand Iyer, and SVN Vishwanathan. An efficient bandit algorithm for realtime multivariate optimization. In International Conference Knowledge Discovery and Data Mining, pages 1813-1821, 2017.
[18] Matthew Hoffman, Bobak Shahriari, and Nando Freitas. On correlation and budget constraints in model-based bandit optimization with application to automatic machine learning. In Artificial Intelligence and Statistics, pages 365-374. PMLR, 2014.
[19] Jean Honorio and Tommi Jaakkola. Tight bounds for the expected risk of linear classifiers and BaC-Bayes maite-sample guarantees. Artificial Intelligence and Statistics, pages 384-392. PMLR, 2014.
[20] Francis L Huang, Wolfgang Wiedermann, and Bixi Zhang. Accounting for heteroskedastic- ity resulting from gerween-group differences in multilevel models. Multivariate Behavioral Research, pages 1-21, 2022.

---

[21] Peter Huber. The behavior of maximum likelihood estimates under nonstandard conditions.
In Berkeley Symposium on Mathematical Statistics and Probability, pages 221-233. University of California Press, 1967.
[22] Yassir Jedra and Alexandre Proutiere. Optimal best-arm identification in linear bandits. Ad- vances in Neural Information Processing Systems, 33:1 13:10007--0017 2020.
[23] Kwang-Sung Jun, Lalit Jain, Blake Mason, and Houssam Nassif. Improved confidence bounds for the linear logistic model and applications to bandits. In International Conference on Machine Learning, pages
PMLR, 2021.
[24] Maurits Kaptein and Petri Parvinen. Advancing e-commerce personalization: Process frame-
work and case study. International Journal of Electronic Commerce, 19(3):7-33, 2015.
[25] Zohar S Karnin. Verification based solution for structured mab problems. Advances in Neural Information Processing Systems, 29, 2016.
[26] Julian Katz-Samuels, Lalit Jain, Kevin G Jamieson, et al. An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits. Advances in Neural Information Processing Systems, 33: 13371-10882, 2020.
[27] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armee bandit models. The Journal of Machine Learning Research, 17(1):
1-42, 2016.
[28] Jack Kiefer. Optimum experimental designs. Journal of the Royal Statistical Society: Series B (Methodological), 21 21(2):272-304 1959.
[29] Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
[30] Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with heteroscedastic noise. In Conference On Learning Theory, pages 358-384. PMLR, 2018.
[31] Fanjie Kong. Yuan Li, Houssam Nassif, Tanner Fiez, Shreya Chakrabarti, and Ricardo Henao. Neural insights for digital marketing content design. In International Conference on Knowledge Discovery and Data Mining, pages 4320-4332 2023.
[32] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[33] Zhaoqi Li, Lillian Ratliff, Houssam Nassif, Kevin Jamieson, and Lalit Jain. Instance-optimal pac algorithms for contextual bandits. In Conference on Neural Information Processing Systems, pages 37590-37603, 2022.
[34] James G MacKinnon and Halbert White. Some secterosedaastiiiyyccoiisse covariance matrix estimators with improved finite sample properties. Journal of econometrics, 29(3):305-325, 1985.
[35] Blake Mason, Lalit Jain, Subhojyoti Mukherjee, Romain Camilleri, Kevin Jamieson, and Robert Nowak. Nearly optimal algorithms for level set estimation. In International Conference on Artificial Intelligence and Statistics, pages 7625-7658. PMLR, 2022.
[36] Blake Mason, Kwang- Sung Jun, and Lalit Jain. An experimental design approach for regret minimization in logistic bandits. In AAAI Conference on Artificial Intelligence, volume 36, pages 7736-7743, 2022.
[37] Darcy P Mays and Raymond H Myers. Design and analysis for a two-level factorial experiment in the presence of variance heterogeneity. Computational statistics & data analysis, 26(2): 219-233, 1997.
[38] Subhojyoti Mukherjee, Qiaomin Xie, Josiah Hanna, and Robert Nowak. SPEED: Experimental design for policy evaluation in linear heteroscedastic bandits. arXiv preprint arXiv:2301.12357 2023.
[39] Sareh Nabi, Houssam Nassif, Joseph Hong, Hamed Mamani, and Guido Imbens. Bayesian meta-prior learning using Empirical Bayes. Management Science, 1777)11777 2022.
[40] H Neudecker. Symmetry, 0-1 matrices and jacobians. Econometric Theory, 2:157-190, 1986.
[41] Ann I. Oberg and Douglas W Mahoney. Linear mixed effects models. Topics in biostatistics, pages 213-234, 2007.
[42] Friedrich Pukelsheim. Optimal design of experiments. SIAM, 2006.
12

---

[43]
Takaki Sato and Yasumasa Matsuda. Spatial extension of generalized autoregressive conditional heteroskedasticity models. Spatial Economic Analysis, 16(2):18--60, 2021.
[44]
Marta Soare. Sequential resource allocation in linear stochastic bundits. PhD thesis, Université Lille 1-Sciences et Technologies, 2015.
[45] Marta Soare, Alessandro Lazaric, and Rémi Munos. Active learning in linear stochastic bandits. Bayesian Optimization in Theory and Practice, 2013.
[46] Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification in linear bandits. In Advances in Neural Information Processing Systems, 2014.
[47] Chao Tao, Saúl Blanco, and Yuan Zhou. Best arm identification in linear bandits with linear dimension dependency. In International Conference on Machine Learning, pages 4877-4886. PMLR, 2018.
[48] Bryan W Ting, Fred A Wright, and Yi-Hui Zhou. Simultancous modeling of multivariate het- erogeneous responses and heteroskedasticity via a two-stage composite likelihood. Biometrical Journal, page 2200029, 2023.
[49] Martin J Wainwright. High-dimenssonal stafistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
[50] Po-An Wang, Ruo-Chun Tzeng, and Alexandre Proutiere. Fast pure exploration via Frank-Wolfe. Advances in Neural Information Processing Systems, 34:58 10-5821, 2021.
[51] Halbert White. A saaakeddstiiittyycoistttee covariance matrix estimator and a direct test for heteroskedastieity. Econometrica: journal of the Econometric Society, pages 817-838, 1980.
[52) Douglas P Wiens. Designs for weighted least squares regression, with estimated weights. Statistics and Computing, 23:391 1-01, 2013.
[53] Douglas P Wiens and Pengfei Li. V-optimal designs for heteroscedastic regression. Journal of Statistical Planning and Inference, 145:125-138, 2014.
[54] Weng Kee Wong and R Dennis Cook. Heteroscedastic g-optimal designs. Journal of the Royal Statistical Society: Series B (Methodological), 55(4))871-88) 1993.
[55] Weng Kee Wong and Wei Zhu. Optimum treatment allocation rules under variance hetero- geneity model. Statistics Medicine, 27(22):4581 -4555, 2008
[56] Jeffrey M Wooldridge. Econometric analysis of cross section and panel data. MIT press, 2010.
[57] Liyuan Xu, Junya Honda, and Masashi Sugiyama. A fully adaptive algorithm for pure explo- ration in linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 843-851. PMLR, 2018.
[58] Dan Yan, Xiaohang Ren, Wanli Zhang, Yiying Li, and Yang Miao. Exploring the real con- tribution of socioeconomic variation to urban PM2.5 pollution: New evidence from spatial heteroscedasticity. Science of the Total Environment, 806:150929, 2022.
[59] Junwen Yang and Vincent Tan. Minimax optimal fixgebbudget best arm identification in linear bandits. Advances in Neural Information Processing Systems, 35: 35: 12-12233-1222 12266, 2022.
[60] Mohammadi Zaki, Avinash Mohan, and Aditya Gopalan. Towards optimal and efficient best arm identification in linear bandits. arXiv preprint arXiv: 1.01695, 2019.
[61] Huiming Zhang and Song Xi Chen. Concentration inequalities for statistical inference. Commu- nications in Mathematical Research, 37(1):1-83 2021.
[62] Heyang Zhao, Dongruo Zhou, Jiafan He, and Quanquan Gu. Bandit learning with general function classes: Heteroscedastic noise and variance-deeendentt regret bounds. arXiv preprint a202 /3603, 2022.
13

---

Contents
Appendices
14
Background on Experimental Designs and Rounding
14
Technical Preliminaries
15
Baseline Variance Estimation Procedures
16
D Prools of Variance Estimation
17
Analysis of the Separate Arm Estimator
17
D.2 Analysis of the HEAD Estimator
21
Proofs of Best-Arm Identification
25
Lower Bound
25
F,2 Upper Bound
26
Proof of Correctness
26
E.2.2
Proof of Sample Complexity
28
F
Proofs of Level Set Identification
33
Lower Bound
33
F2
Upper Bound
34
F2.1
Proof of Correctness
34
F2.2
Proof of Upper Bound on Sample Complexity
35
Comparing Identification Lower Bounds
37
H Experiment Details
38
H.I Oracle Designs
38
H.2 Assuming Homosekedastic Noise
38
A Background on Experimental Designs and Rounding
We use optimal experiment design
29 to minimize uncertainty the estimator of interest. Con- sider the WLS estimator with the weight matrix W7. = =TT so that V(WwLs) = (XT
(T -z -=²2x=])-1 Let Å₂ denote the proportion of the total samples T given to the measurement vector x E X' so that v(@wLs) = x ) We wish to take T samples so as however TA₃ is often not an integer. As has been discussed depth 46 12 B2 efficient rounding schemes can solve this problem. Given some constant tolerance threshold e, design X E Px, and minimum sample size r(c), efficient rounding procedures return fixed allocation {ux, ) that yields a (1 + e) approximation to the intended design. A simple, well known procedure with r(e) < {d(d 1) 1)+ 2} /e comes from Pukelsheim 442. while the scheme of Allen-Zhu al. yields r(e) S (d/e2). In our experimental design algorithms, we leverage the aforementioned rounding schemes.
to construct the design E
Th "xx'
14

---

We adapt the guarantees of [3 for Alg. D as example in the following proposition. For sample size N, define X as a composed of the elements of X R duplicated N times and SN
{SE {0, ....,,.......................... ..l....,NNIIR N2Mzl Σ
M22 t=1 8, N as the set of discrete sample allocations.
Proposition A.I. Suppose (0, 1/3] and N 2 5d/e. Let À Px. then in polynomial-time (in and d), we can round AN to an integral solution X E SN satisfying
max J wEX
Σ X'EX
xS (1 6c) min max AEPx sE
Σ W'E
N x.
N NN
Proof. This follows
directly
from Theorem 2.1 in
letting CN
{s [0,N] Σ
E 8; S N be continuous relaxation of SN and setting A N
Na
and n = N|
Alternatvell, one could the robust inverse propensity score (RIPS) estimator 66. which avoids the need for rounding schemes via robust mean estimation.
B Technical Preliminaries
For our analysis, we do not assume that the error, in Eq. Tis Gaussian. We generalize by extending to strictly Lub-Gaussian noise, in which the variance of is equal to the optimal variance proxy for Me: Vt N. This paradigm allows for noise distributions such as the symmetrized Beta, symmetrized Gamma, and Uniform.
The following definitions and propositions will be used in the proofs of Appendices D Definition B.1. A real-valued random variable X sub-Gaussian if there exists positive constant x² such that
E E (xxx)= S 22212
for all X 0.
Proposition B.1 (Equation 2.9, [49)). Let X sub-Gaussian random variable with Sab-Gassiinn parameter o² and mean (E())= 1u. Then, for all > O, we have
P(X - M 2 t) < 2e 2.
Definition B.2. A real-valued random variable X with mean B(X) μ is sub-exponential if there are non-negative parameters (u, ar) such that
{ Se
MIIA 1
a
Proposition B.2 (Proposition 2.9, 49 and mean B(X) μ. Then, for > 0,
Suppose that X is sub-exponential with parameters (v, o)
P(X - 12
C
if 0
if
3
This implies that for 5 E (0,
P [[x - u| < max 2log(2/0) log log(2/0)a 1
Proposition B.3 (Equation 37 in Appendix B, 19).. Let X be a sub- Gaussian random variable with sub-Gaussian parameter o², Then X" is sub-exponential with parameters (v = /2, a = 4o Proposition B.4 (Equation 1818 [49).. Suppose that X; for E (1, n. are sub-exponential with parameters (2,, 0s)) such that E(X,) = (4s. Then, E (X, - (4,) is sub-exponential with parameters (v., a.) such that
0. = max O5 and U. =
Σ
2
1=1.2....
1=1
15

---

Definition B.3, A G-optimal design 28 X
Px, for a set of arms A' C IR is such that
x arg min max T XEPx
Σ
x.
ZE
Proposition B.5 (Lemma 4.6, For any finite X' TRd with span(22) = R2
Σ Xux
= min max x XePx TEA
a.
LEE
This implies that if we sample each arm
E
[ times, then
-1
-1
max O
ΣiTAyTo
x S m
Σ Aa
d
TEA
ZER
Definition B.4. The Forbenius norm of E TRaxm is
|||| (T(ATT).
Definition B.S. The Spectral norm of E 1R is
Axll2 |
|| = sup a/0
Proposition B.6 (Matrix Norm Properties). For A E |axxm, we have sub-multiplicativity for the Frobenius norm:
||A All $ ||A
and bound the Spectral norm:
||ll S ||||
Proposition B.7 (Corollary 4.7, 61 Let E . En be zero-mean
and A Raxx
For any t > 0,
P AC 2
0² tr A + 2tr(A + 2/ set,
which implies that with probability for (0,
TES o² (r(() 2tr 2 log (1 (1/5)} 1/2 2// log(1/6))
Proposition B.8 (Equation 20.3, 32 ). Assume the setup of Eq, | and that data set of size F, D {ax, ye )r has been collected through fixed design. Define Vi Et= sant and construct the least squares estimator for D. 0r Vi Einraa1)) Then, with probability for 5 E (0,1),
0 0'Ilvr 5 <2 (dlog(6) log(1/8))
C Baseline Variance Estimation Procedures
These are the algorithms we reference in the theoretical and empirical comparisons of Section 3
The Uniform Estimator. The Uniform Estimator draws arms uniformly random and uses all samples to construct estimators Ør of 0* and Σr of >**
The Separate Arm Estimator. Define as the set of subsets of W of size M d(d + 1)/2, and for U l4 construct ty such that its rows are composed of & E U. Let Smin be the minimum singular value of matrix A E Rddd The Seperate Arm Estimator picks set of M arms such that
U = arg max Smin (47
Uell
It then splits I' samples evenly between these arms, estimates the sample variance for each and finds the least squares estimator S.SAA
16

---

Algorithm 3: Uniform Estimator of Heteroskedastic Variance
Result: Find ŠUE
Input: Arms X' C IRd and I E
2 Sample arms uniformly at random from X'
3 Define A Σ Ze and b* Σi= Teft and estimate Or A
Define Al Σt= Pn, oz and bi Et=1 Oz. (y:- 22 0r)
5 Output: SUE A bt,
Algorithm 4: Seperate Arm Estimator of Heteroskedastic Variance
Result: Find ΣSA
1 Input: Arms X' C IRd and I' E
2 Define U* = arg maxu'u Smin ( (
3 Equally distribute T samples among arms Xy-- {m : 2m E U*} and observe rewards
(Um,t) / for Ay-
Define the sample average for each arm U.. = (M/TT
Eter Dm,t
L/M
s Output: ESA < arg mingeRM Emexy.
ΣI/M (
@mm
T (Tm ymn,) )2 {
D Proofs of Variance Estimation
In this appendix, we analyze the maximum absolute error of estimates associated with the Seperate Arm Estimator and the HEAD Estimator. Recall that M 1(d+1)/2. Define W {dh,, V X C R where d. = vec(xx JG and 12d xM the duplication matrix such that Gvech(xz = vec(xx)) )) with voch(-) denoting the half-vectorization.
D.1 Analysis of the Separate Arm Estimator
We begin by proving a general result bounding the absolute error of the sample variance for any sub-Gaussian random variable with parameter 7
Proposition D.1. Let X be " random variable with mean Assume that we have collected n independent copies of X, {X1, X2.... and label the sample mean as D" X1/n. Xs/nn Defining the sample variance 8 Ei=1(X X)2 /n, the true variance as o² E(X?) n and E (0,1), we find that with probability greater than 1- --6 6,
5 0-2 021 <
4v2, log(4/8)
32 log(4/6)
max 2
n
n
17

---

o2 Proof. We begin by upper bounding the absolute error using the triangle inequality,
0² Σi= (X; - -X²²
o² 021
B(X²) 11² Σ X?
X2 -2X,X +
n [=]
X?
B(X3) n.
+ +2X² X2
n1
Li=1 X?
2
B(X?)
X2
1
n1
n
Σ i=
X?
0
B(X?)
X2
n
n2
12
We first bound quantity A. Leveraging Proposition B.3 we establish that X? E(X?) is sub-
exponential with parameters (4,2 We can then use Proposition B.4 to analyze the sum
of independent sub-exponential random variables, finding that E (X? [x?)) /n is sub-
exponential with parameters (47² /2/ /n, /n2/ Finally, we invoke Proposition B.2 to bound
quantity A with probability 8/2.
Σ a
X?
472 log(4/0)
32>4 (og(4/8)
E(X?)
max
Now we bound quantity B. Appealing to Proposition B.3 we find that X² a² n is sub-
exponential with parameters (4v2n2/n,, We then use Proposition B.2 bound B with probability 1 1-8 8/2,
0²
422 log(4/8)
32-4 log (46)
X2
1
max
n²
4x2 log(4/8)
4x2 log (4g(4/))
V2
max
Mlg 1og(4/5)
(2) 2/2 log(4/5)
where (a) follows because v2/ / 1og(4/8) < V2. Finally, we combine quantities A, B and C, apply a union bound, and conclude that with probability for (0, 1).
X
X?
0² 021 $ [E(?)
+
X
Y
n
m
472 log 4/8)
32-4 log (4/8)
2 2 log (4/8)
22
max
n
4v/222 log(4/6)
32-4 (4/8)
max
n
n
We can now use Proposition [.T control the sample variance estimates of the arms chosen by the Separate Arm Estimator. Theorem D.I derives a concentration bound of the maximum absolute error of 82 = min max - x: A v with dimension highlighted in the theoretical and empirical comparisons conducted in Section 3
max This bound, which Odd)), scales unfavorably
18

---

Theorem D.1. Set SSSA as the output of Alg. 4 and define B such that for all E X, || - B. 2T
Defining oh min max { fo
ESA x
}
I max J. o² = x D and E [0, 11. for any x E X,
4v20 d 1og(8M/6) 320 dt (0 }
5B2 /2
P
o2 Smin (2v.)
max
21 - 6/2.
Note that we set the probability bound 8/2 instead of 8 because we want be able to leverage these variance estimation bounds with the identification algorithms of Section 4 (and so are anticipating another union bound).
Proof. Label M = d(d + 1)/2 and Nv. {m pm E U"}, where U is defined in Alg. Additionally, in Alg. 4 we observe {ym, I for each arm m E Xu.. Define the sample average for m E Ay as
21=1 Um.tt
Um
T/M
We obtain an estimate of Σ" via
T/M
vech (ES))
arg min SERM
Σ
Σ
{ (6mm 8) (Tm )22
(5)
mEX t=1
Label Zm, (Im ym,e)² E R. V vech(E") E R T vech(Ep.)) R and
I//M 2m,t
Zm
T/M
We reformulate Eq. 5 as follows
T/M Σ
T = arg min
Σ
(10m, s) - -2m.t)
BERM AM
m t=1
T/M
arg min
Σ mEXy* t=1
Σ
(0m,s)²
-2ūm,, (Wm, 8) + -2
r/Ms Σ
T/M
arg min SERM mENyy
Σ
(T/M) (dmm s)² 2/ s)
Zm,t
2
1=1
T/M
arg min
Σ m
(0m, 5)² -2(0m; s)zm +
1=1 2
T'/
(0)
arg min SERM
Σ
(pm, s)² - -2(0m, + =
mEXU
arg min MERM
Σ mEX
((0ms)) s) zm)²
where (a) follows because I//M 22 a (T../(T/////
(T/M) and =2 do not depend on s. Defining E
[mmlmeRoo E R Eq. 5 becomes
T arg min SERM
Σ
(10m, 8) =mm) arg min SER
| 2|12
mEXp.
We find that
1 (Vr v²'112
| Vr Φ 1/r - 2||2
| Vp E = - Φ.- v ||2
| Tr Σ||2 + = Φ V
p V -Øl12 + || Φ 11
2| By- T - El12--
19

---

Consequently, we can focus on bounding P 40- - Ø|12 in order to control | ( - )2)12
Note that the m entry of (+r- 1p" 2) is (m mm 3m) and that 2m is the sample variance of observations (tm,,)t=11 IT/M we show that with probability - 6/MM,
Using Proposition D. and the fact that the you, o max
Sub-Gaussian
2o max M log(8M/6)
32o M 1og(8M/0)
1m V
3m|
S -
max
(6)
We apply Eq. to quantity 1 v
- 2 and union bound to find that with probability 1 8/2,
5 M
4v 20 2 mux
M (8M(8)
320 a max
M log (8M//6)
- V - EEll2 S
max
2
T
r
4v 20 max
V M (8g(8)/0)
32a 1 max
M log 8M/6)
max
2
r
r
Consequently,
20
32o max M MVM log(8M/8)
M log(SM/0)
T (ur - -V'Il2 S max
max
r
r
We now analyze the absolute error of the estimate o. for arbitrary action X. Since Pu- is non-singular by construction, we know that for q: := (Øu. - &2 E R.M
W T oz
o
( 1/") T "Tddll2 122
(VVT w²) T -v- T '/122
([Vr TT ||| ||12
| (ūr - =V")] f -T)TTO &x l2
| (vr T )1) [1 -1) - 122|@z1|2
2 (Ur - " >2) 10
Smin (Qu-)
where (a) follows from the definition of the matrix norm. We now leverage the nature of the duplication matrix, G. and the fact that ||æ:||2 S B to bound 11
|| 2 vec(ax ) GG voc(wxx)
vec(ax (eoxx=)TTco ()
veo(ar
() G) G) G veo(sx) )
(a) 2vec(xx))
G(G vee((xx>)
2vec(xx)) I [vvo(xxx))
2x xx." T
S 2
where (a) follows from the fact that G = 2I as shown in Equation (61) of 40), and (b) uses the fact that G(G G vec(ax = vec(xx) ) as shown Equations (54) and (52) [40] Consequently, with probability greater than 1 8/2, we have that for any E &.
5B2
4v202 max M M (og(8
V
320 max
M2 log (8M(88/8)
152 - - Smin (Du-)
max
r
r
5B2 /2
4 20202 may
d log((8M)) (M/6)
13204 man d log(8M/8)
< Smin 22.))
max
20

---

D.2 Analysis of the HEAD Estimator
We now present the maximum absolute error guarantees of the HEAD procedure, Alg.
Proof of Theorem 3.1 In this proof, we bound the estimation error [ - o2h, Ve E X. Define
o Fiax m
or V vech(>>"), Ni {L...., 1/1.)., N2 (1/2 1,..,I11 and
{ SM. (ye x. 0r
arg min SERM
NEN2
where r = vech(Er) Furthermore, define vector e with entries e, = (yh I2 0r)2)² and such that the rows of are composed of {dz, JeN We find that
(Φ TT)
0x r /³)
For any &u W, are interested in bounding
10 (Ur - v/-) = c 1b T ②)
-1 Φ e - v.
= ( x T Φv)*))
Define 2 = 2x ( and X such that the rows of X are composed of fatheNs We can
bound this expression with the triangle inequality as
1 (vr (Vr-v*) [²)] = Σ
2t x (01/2-220 -0-)
2 +
21
(nh
(/' + Σ
2 (0r/2 - 0-),
N
BEN2
BEN2
ab (0r/2 - 03/)²
Σ
+
Σ IEN
(nk of 117)
oTTTT))
+
Σ
2211 (0r/2 - 0 8")
NE
IEN;
We can simplify the first term as,
Σ 28 { 2 (0r/2 )²)
Σ 200 vech (0) - Ty)
IEN
KEN2
$1 (oTTTo Φ) -l l $ x vech (Ør/2 - 0-)
(00)2-00))0pp - -
TTrr122 8¹) 0¹)(0r/2 - 8-) Tx
{o (0r/2 87)
Additionally, the third term is equivalent to 21 2) X X(0r/2 8*),. multiplication. Consequently, the absolute error is equal to
where "o" is element-
@ v\' = x (Ør,2 84)
+
Σ NEN;
24 (né
o. vt)
+2 (no T 0r)
Note that to bound I0_ (Tr V²") with probability - 5/2, it is necessary to bound quantities A, B and C with probability 5/6 in anticipation of union bound.
Quantity A. We sample {æ,, N₁) } according to the rounded G-optimal design over X' constructed in Stage 1 of Alg. We use the concentration bounds of Proposition B.I to state that with probability 1 8/6,
A < Tx
Σ mxae MEN
max
log (1)
21

---

We use Proposition B.5 in combination with the rounding procedure guarantees of Proposition A.J to bound quantity G. For E (0, 1/3], with probability 1 1-8/6.
4d(1 + be Ge)omax (og(12(x110)
A
Quantity B. According Proposition
B.3
o is sub-exponential with parameters
(4v20 max: 40 max)) Consequently. by Proposition B.4 we know that B is sub-exponential with parameters
23204
max /2 40 max NE
max
N
We now invoke the G-optimal design over W space conducted in Stage 2 of Alg. B.5 and to find that for (0, 1/3],
and Propositions
Σ o Σ teN2
o ( 2)
6.0 (Ø ②) o. -
tEN2
= 2 ( ①) 1 ④ ①) -1 02
2d (1 6c)
- 2 ( ②) 0x 5
r
Consequently,
2d (1
(d + 6c)
Σ 2f
r
NE
and
|ze| = 10 ( T )) 100
V 01 ( 4) -1 / 0. ( (TT))
2d + 6c)
Therefore, B has sub-exponential parameters (v max d2 ( 802 80 de + (1++666) GT) Using
Proposition B.2
with probability 8/6,
128 log (o8loog12//0 (21 t d2 + 6E)
16log(12/0)0
" (1 6c)
S max
r
16 16log d² 6e)
16 1og((12 max d² [1 + 6E)
m8
max
Quantity C. Construct V E IR//2xd such that the rows of V correspond to {z, t E N1). We can upper bound quantity C using the Cauchy-Schwartz Schwartz inequality in the following manner,
1(n o 2) x (0r 0 = (nn o 2) " XV
0*)
< 11 2)
0-)
By Proposition B.8 with probability 1 1 5/12.
II (VVTV) (0 0²) < 2 20 2220
{d 1og(12/8)).
Now construct D. diag((z): :NNN)) and express,
(l))2))TT X(V -リ 1/21/2 VNDD,X(VTV--XTTT
22

---

We first establish that by the G-optimal designs in both X' and W space along with Propositions B.5
and A.1
E (V
NE
2d(1 + 6E
Σ
21
T
NEN₂
(2) 4d (1 6E)²
r
where e E (0, 1/3] and (a) follows from Eq. 7 Consequently, we find that
4d + 6e)²
Ir (V D.)
(8)
r2
This inequality will be useful in the following derivation. Labeling A = D) Dz, we use Proposition B.7 to bound v/ Ar with probability 1 - 8/12 and explain below.
11 An < max
(r(A) + 2| log log(12/)) + 2 log(12/0))
(9)
4d + 6c)
2
+ 2/ +2211411120001210)""==11
+ 2
(10)
1
4d (1 + 6e)²
o max
1/ 1011 log log
(11)
1
4d (1 + 6z)²
|1244 log
(12)
max
1
4d (1 + 6E)2
2
2tr(A) log (12 ( 2
(13)
max
12
4d (1 62)²
4d (1 111+000 6e)²
log(12/6)1 4d
6e)
S max
log 12/8)
r2
(14)
4r + 62)
< 502 max
log (2/8).
(15)
I
where line (9) follows from Eq. g Proposition and Proposition B.7 In lines (10) and (11), we use Proposition B.6 again and then the definition of the Frobenius norm in line (12). Consequently, with probability 8/6.
C 1 X(0r/2200 -
-8)) < =))) 2) - (2 - 0²)112
2)) X(V
4d 6c)
< <2 100 max
log (12/5) (dlog(6) + log( 12/6)).
1
23

---

Combining quantities A, B and C together and applying union bound, we have with probability 1 8/2,
16 16log(12/0)ommnnd 6e) 16 16lg((2 dl + 6E)
_0_ (wr - 2^) s max
Vo max
+ Ado max
log(
(11(12221//)111- 66)
r
4d + 6E)²
+
100 max 2
log(12/6) (dlog(6) + log(1)/)))
r
V80mmx
(llog(1200jan) max de + 6e) 16 log loglo1/0)0 12/0)o max + 6e)
(3/10) max
r
r
W
4do max log( (1) 6c)
We exploit the dependencies of V and W simplify this bound in two ways under different conditions. Note that we only have dependency on | through term V. df > log([X))) log(1/6) and r >> 16 (og(12/6))o o d2 (1 Gε), then with probability 1 8/2,
256 log (12/(10)))
10120)0ooon max d2
6E)
10
(Vr V
r
Alternatively, if just r 16log(12)/)1/8)0
max de 6c), then
256 log (2 max de + 6E)
10 (Tr v/*)
(16)
r
Since oaax 2 02 2 oi for all x E EX
|0 (Ur - = |x T Erz x V min { max { T Erzz omin/ }. ) _maxx - -z
In summary, ifT > 16log (12 a d 6c).
C' log((<>') 10 max
P
: oal s
2 1-65 8,
where C" = 256(1 + 6e).
We now prove simple lemma relating the additive bound 10? of2 to multiplicative bound 1 Cr.s < 0 < + Cr,s-
Lemma D.I. Define a2 min max fo EEro, o miin } }.0 x }. Letting 2 min o
/ 2 2 and
2 < 1 Cr, 2 - 1-82, where Cr,5 =
O' log ('1))((2(/8))x²
P Va E X <
r
24

---

Proof. holds.
Using Lemma
D.1
we know that with probability greater than 1 - 8/2 the following event
C" log(((X1)/0)) max
10 0 1
r
C' C'log(IX| m6) d2
C² log 21/00) m d2
62
522 +
C" (o)o
max d²
C' Colog(12') J max d?
0 1
0
2 < 0/ + 1
T.
('log(221/0)0 max df
C' 111 max d2
1
min I
min T
C' log( x1/8)1222
C" log [og( /6)
1++1
r
1'
E Proofs of Best-Arm Identification
We divide the proof of Theorem 4.1 and 4.2 between Appendices B and for ease of exposition. In
Appendix EE] we consider the transductive linear best-arm identification problem (BATI) in which
are interested in identifying x² = max 2 0* with probability 1- 8 for å E (0, 1). In Appendix
we consider the level set (ISS) counterpart. Recall that for a set V. let Py == {} E TR V Evev A
Av 2 0 V f) denote distributions over V and V(V) == {v' - v. u. E V. v 전 r') be an operator giving differences. We begin with the lower bound.
E.1 Lower Bound
Proof of Theorem 4.1 for transductive best-arm identification. This proof is similar to the lower
bound proofs of 35 and [12] Let {0 Rd 3i s.t. ØT (2 - 2,) S 0}, i... Ø E and only if 2* is not the best arm in the linear bandit instance (X, 2,0). Additionally. label K |
We first invoke Lemma 1 of (27). Under a 5-PAC strategy for finding the best arm for the bandit instance (X, 3, 8*). let T; denote the random variable that is the number of times arm is pulled. Defining of x S*r for all æ E X, we let vø, denote the reward distribution of the i-th of X,
ie., Up, = [x] 0, o2.). For any E C we know from 27 that
K
K(To) 2 log(1/2.46).
Following the steps of we find that
((:)) 2 log(1/2)48) min max
(17)
XEXx dec ER X ,llvg,)
Label Z (21, 22...., 2n. where 21 without loss of generality. For # X e Px and 0, define A(A) Σ
oo
Wi Zj and
[w) 8" + c))(A) w A(A)
O)(,,A)= = 0²
25

---

Note that (, A) = -c < O, implying that B, E C. We find that the KL divergence between 18.3 and (o)( is given by:
1o 10t ( (),
(c.a)))))
2x
=w3 A(A) -1 (w) 0r + 2))=200 2,
20
A(A) wj.
[w] A(2) -2u;,
Returning Eq. 17
B(T)) 2 log(1/2.4b) min max k Xe L allug,)
XEPx dEC
(1g(1/2.48)
min max
XEPx j=2, m E X , (1l10,(e,.))) ((.A).)
{w] A(2)-11;)
2 log(1/2.48)
min max
XEPx j= m [w] 0+ + we] A(A) 11A; L.
A(A) ww
20
[w]AAA)) 111)
(a) log(L12))4
min max
xE j=2,- m (w, 0r + t A(A) |E/// X -
A(A)
{ [w] -
(10((1/)
min
AEPx j=2,.., m
(w) 0r + c)2
where (a) uses the fact that Σ
K
X
A()). Letting - 0 establishes the result.
E,2
Upper Bound
We now prove Theorem by first establishing that Alg. is 5-PAC for the transductive linear bandits best-arm identification problem.
E.2.1 Proof of Correctness
Overview of Correctness Proof. Lemma D.1 along with Lemmas E.1 through E.3 combined to prove that Algorithm 5-PAC for the best-arm identification problem. Lemma E. lveraages Lemma D.I and begins by establishing that in any round é E N. the estimation enror for the difference in mean rewards between = E Z and x" = arg maxzez z T 7" is bounded by ez = 2- with probability 1 5 for å (0, 1). Lemma E.2 uses this result to prove that starting at round =" Ze+11 with probability 1 - 6. This establishes that =" is not eliminated from the set of items we are considering at any step with high probability. Lastly, Lemma E.3 uses Lemma E. to show that Algorithm will eventually identify z². This is done by proving that Alg. Deliminates items with mean rewards that are outside a shrinking radius (halves at every step of the algorithm) of the highest reward, 2" 0" In other words, with probability - 5 for 8 E
(0, 1). we prove that items in Z, with expected rewards that are 2 away from 2" 8* will not be in 2 Since 6 + as oo, we know that lim PP P(Z,. = {=*}) }) =1 -18. 5.
Lemma E.1. With probability at least 1 - 8 for 8 E (0, 1).
[/2 0e - 8*)l S ce
for all é and 2 Z.
Proof. Define 03 = T E" x. Oe the weighted least squares estimator constructed in Algorithm at stage E, and events
E,,t (2 2-,0, 0¹) s et
26

---

and
J= 5 (1+
2 oo Vr E X3.
Label ny as the number of data points collected during stage f, Y = diag({o)) 1==1) f diag((")) X as matrix whose rows are composed of the arms die drawn during round L, Ye as the vector of rewards drawn during round E, A = 1 22, and f
A x7 "x as the weighted least squares estimator's covariance. We first estab- lish that for 2 E ER..
00) = = { x, "B()) - 00) -
x 1x,00 0000-001 -0-) 0,
(1,1x,
and
v f=T(00 -0)} =
Furthermore, defining un = A, x 7 1/2 E R and conditioning event J.
T ATA,' X --
= =x=T -
X 9 - 111 (f- -1
= 1
11 2
m
(0)
4
2 1=1
3
3
A 2,
2
where (a) is the result of event J. Using this result and Proposition B.1 with probability at least
1 2|
Ez, = 1(2 - 00
071 S ||2 z"Iliv / (8g
S - 2log 88 (
Conditioned on event J, we have with probability
127121
1(2 - (a===000, 00 - 0)1 s 3
||= - =*11
-1 /2 221g((8)111))
ExeviTede.
T
2 0|2 211
(0og(82212/00
Emex
1|1
11
ExEN dew TxT 83
2 21/6)
VTi
/ 1|1 2²11
zrT (ESC de,
2 ( 26 (2999((22 ()(2,)) 1og(8(2)21/0) V2 log(882 (218)
27

---

Applying a union bound, we find that
P {(ng= Ozez, & P (( Uzez,
E2,1 UzEZ,
U JJ
8
P(E + +P(J9)
2E
8
8
Σ
+
482
1
2
E= zE
5 51-6, 6,
which proves the result.
Now establish that, with probability - 5 for 5 (0, 1), the best arm 2" will not be eliminated from Zg for any round l E N.
Lemma E.2. With probability at least - 8 for 8 E (0, 1). for any & E N and a' E Ze.
(s' =0, s et-
Proof. We know that with probability 1 5 for all E N and s' Zt.
2", 2-))0)) (2' 2-,0= 0r) + (2' - - -0
< (z' =², 0-)
S CE.
where the last inequality follows from Lemma E.1
Then, we establish that in round l, items in Ze that have mean rewards farther than 2e, from the highest reward will be eliminated.
Lemma E.3. With probability at least 1 - 5 for d E (0, for any l E N and E Z₁ such that 2, 0*) > 22,
max (e' - 2, 02) Et. E'2,
Proof. We know that with probability 1 - for all & E N,
max (2' - 2, B2) 2 (z - z, 2,
2e
12" z, 0 8r) + (2" 2, 0-)
(a)
-et + 2EE
Et.
where (a) follows from Lemma E.1
E.2.2 Proof Sample Complexity
Overview of Sample Complexity Proof. In this section, we prove an upper bound on the sample complexity of Algorithm 2 for transductive best-arm identification with linear bandits. We begin by establishing some basic facts about the partial ordering of Hermetian positive definite matrices in Lemmas E.4 and E.5 Let A and B be Hermitian positive definite matrices in ddd and define A z if A B) is positive definite.
Lemma E.4. Let A and B Hermetian Positive Definite matrices in Rdxd
A
12
A 1/2 BA-BAA- 1/2
28

---

Proof. For any Rd we define y = A/22x and
x Ar x² A-A"2A-1-AAA-11 x
-v"ly
y A 11/2
z TT Br
=y A A 1/2
Lemma E.5. Let A and B be Hermitian positive definite matrices in Rdxd
A B -
Proof. We use Lemma E.4 twice in the following proof.
A + T A-
+ I A-1 B2/2
- I >> /2 /!/22
- B ビ A-!
where line 2 follows because A 1A- 1/2 is similar to /3/22-1/2A-11222 and both are Hemmetian positive definite.
We now use Lemmas
E.4 and E.5
in our problem context. For V C Rd define g (V. - such
that g(v, A) || (E, Aazx (02) (V, Px) R such that f(v || Aeæz" /0 and
q (²()) min max f(u, A), ((V) min max g(v, A). xEPx
xEPx vEV
Note that the function, q, also defined and leveraged in Algorithm multiplicative bound of the form
Lemma E.6 establishes
Cr,s) S ((;, (1 Cr.a) ((
using Lemmas D. and E.5
Lemma E.6. Define o min { max {ar T
oain maxx }. For a given X, define
Y = diag( ( xxxx) x
8-1 diag( (0 xxxx) x
Assume Cr.5 < and E Rd, then with probability 1 - 5/2 for (0, 1) the following holds true:
(1 Cr.6)) -x s < < x
51+ v (xT--1x)-1
or equivalently
Cr,s) A) S f(., & (1+ g(+)),))((.))))
Proof. Using Lemma D.I
we establish that
T Xu = -
-
$11+ 1
and
" T x
--
2 (1 c x
29

---

Leveraging the partial ordering of Hermitian positive definite matrices and Lemma E.5 represent these inequalities as
we can then
Cr,s) x ( =
(x r x) - (xT Crs (XT--X)-
xx)
1 Cr.6
This implies that
(XTT-IX) -1 = (1-Ch (1-Cr,)) (x -1
and
(xTr-Ix)- -1 3 (1 +++Cr Cr.a) (xT--1x)
By combining these inequalities arrive the result.
We now want to use the multiplicative bound of Lemma E.6 to define the relationship between ((V) and (V))) and eventually relate the sample complexity upper bound of Alg. 2 to the lower bound established in Theorem 4.1 order to accomplish this goal, we prove some general results concerning minimax problems in Lemmas E.7 and E.8
Lemma E.7. For c > 0, v E Id and E ,
(1 c)g(U, A) A) (v, S (1+ ()
then
(1 c) max g(v, A) S max f(v, NEV
3EV
S (1 + c)
max g A).
DEV
Proof. For a given À E Px, define vi (A) = arg max g(v A) and 1-' (A)) = arg max.ev f(u, A), then
(1 - c)g fo (A), {A)
{)))
< (l (1+ c)g ()g
Lemma E.8. For e > 0, E Rd and A E Px, if
()-c)g(v X) - [(v, & (1 + c)g(v,,
then
(1 c) min max g(u,))
S min max f(u, A) xEPx vEV
xEPx vEV
I (1 + c) min max A(v xEPx VEV
Proof. For given E Px, define of (X) arg max g(c f A), 0 v*(A)= arg max f(u, A),
X arg minxees maxvev fle A) and Al arg minxePs max g(e A), then
(1 cl c)g ( (2)). = (1 - c)g (u)
(a) x (()'
{f(1(N)),at)
s (1+t)o(0()))
2 (0
where lines (a) and (b) follows from Lemma E.7
Leveraging Lemma E.8 bound g (V) in terms of q(V) in Lemma
E.9
30

---

Lemma E.9. With probability 1 - 6/2 2 for ā (0,1),
(1 - Cr,6) ((v) s (0) 2 (1 (1+ Cr,)
Proof. From Lemma
E.6
know that
Cr,s) g(v, A) fl, A) & (l.,
According to Lemma
E.8
this implies
(1 (1- Cr,s) min max ((v, XEPx "EV
min max f(e A) $ (1 Cr,8) min max g(v, XePx wEV
xEPx NEV
In round of Algorithm 2 we sample arms in X' according to given design, λe Although other rounding procedures are possible (see Proposition A. Theorem 4.2 assumes that we take Te samples of arm E X' to accomplish this goal. This results more than Tę samples being taken in round f. We define the sparsity of any de design using Caratheodory's Theorem to motivate the number of extra samples needed by sampling in this manner.
Lemma E.10. [Appendix 8. 44
In Algorithm the support of de for all E N is +(d + 1)/2
Proof. Any design matrix in gddd is symmetric and can consequently be expressed as point in RM M d(d++ + 1)/2. The design matrices leveraged in this paper belong to a convex hull of subset of points since they are a convex combination of æx. for x E X. According to Caratheodory's 's theorem, any point in the convex hull of any subset of points in R. can be defined of + points. The optimal experimental designs this paper can therefore be represented using only M + 1 points (44). This sparsity holds regardless of the design's 's form and so applies to both the homoskedastic and heteroskedastic variance settings.
convex combination
Finally, we connect the sample complexity upper bound of Algorithm to the lower bound for 6-PAC algorithms established in Theorem 4.2 for transductive best-arm identification.
Proof of Theorem for transductive best-arm identification. Assume that max,ez, 1(z 2", ) 2. Define S, = {a Z, (z* z, 8*) S 4c.). Note that by assumption 2 Z1 S Lemma E.3 implies that with probability at least 1 ö for d E (0, 1), we know 2, C S₁ for all E E N. This means that
(()(Z)))
inf max ||> 2'1 XEPx 2,=
(EEE d xz )-
< inf max ||| - 2/1 xeXx ES,
(E.
xr )-1
=(()).
For f 2 (ogg(44-1)) we know that S = { Thus, the sample size needed to identify 2" is upper bounded as follows.
[log((4-") 11
(11 1)
d(d +1
TTedez
+
2
NEX
flog (42 111
d(d+ 1)
3
Σ
+2
2 (0x002)))
[lgga (41 111
d(d + 1)
Doga (4A 1)]
3x 3e-2 ( log())))22() 21/0)
2
d(d + 1)
[logo (4A ')1
2
[log, (4A-1)1
18[0gg
(4A-)1(1
+
3ogg
Σ
2 q(2)),
8
where (a) follows from Lemma E.10
31

---

We relate this quantity to the lower bound in Theorem 4.1 below. With probability 1 - 6,
112- =212
ExEx As o5
inf XEPx
max 2EZ((2)}
((2 2) [ 2
1| - =112
1
Euxx
inf
max
max sES,
AEPx ES [00 +)]
1(0t 2) 00-
1|2 - x|1?
ExxEx de o3
XETx E5 (10 1)
inf
max
max SES
(4 2 2-292
2112 112" -21?
[10 111
IV9
ErEn
22
logg (4A -
inf XEPx
Σ
max SES,
(4x2-1)
of
[ORA(44 291
IV
2 inf max xEPx ZES;
-
16 1oggog (1A
Eiex 2z
[1og 111
Σ
22 inf max
|| ||= -1a=-11" =2|2
64 loga (4A (4A
')1
XEPx 2,2 EEE
EEeex 2e 03
[ogg (48 11
1
Σ
2 inf max
1 511=' - =|1?
-
64 logg (4A
xEPx E.;
E
zz
og
(15 211
1
2 inf max || - =2|2 xEPx 2,5
128 (00g2(447))
EEEEx de axT
)
113
Mog (42-1))))) '1
Σ
(({e)
128 loga (AA
here (a) follows from the fact that the maximum of set of numbers is always greater than the average and (b) by the fact that the minimum of a sum is greater than the sum of the minimums. We used the fact that
max 2 ES
1| x113 -
(ZiTEN
zz og
max SES
||2"
=|12
-ieex Ag
-1 o5
by the triangle inequality in (c). Finally, (d) follows from Lemma E.9
Consequently, putting the previous pieces together we find that the sample complexity can be upper bounded as
(42 237
d(d + 1)
Σ Teed
[oga (4A [1]
2
1=1
xEX
[8 [8]log (44 (4A -A-11)11 1oog(44-1) -1
+
3 log
2 2())()))
8
d(d + 1)
[loge (4A 11
2
Blog (4A -1)7
+
384 384 log (4A - 1)] log
UBAT
8
where the dependency on d(d + 1)/2 can reduced to d by Proposition A.I This proves the result.
32

---

Proofs of Level Set Identification
This appendix contains the proofs for the results on transductive linear bandit level set identification. In this problem, we are interested in identifying the set (0*) {= E Z =T 0" aa. i.e., the items with mean rewards that exceed threshold a. We prove the lower bound on the sample complexity from Theorem 4.1 in App. F.I The proof of correctness and the sample complexity upper bound for Alg. 2 are presented in App. F.2 These proof' resemble the transductive linear bandit identification proofs with slight modifications accounting for the the problem structure. Recalling Ba (0*) = {a E Z : 0 < a). we assume that Z = (a U (,")),,, which is equivalent to the condition {a E Z z 0" = a} = 0. Let A mingez 2z 0 al denote the minimum absolute gap for the threshold
E. Lower Bound
Proof of Theorem 4.7 transductive level set identification. Label Rd as the measurement vectors such that K X and Z as the decision item set. This proof is similar to the lower bound
proof's of 335 and
Let C be the of alternatives such that for 0 C. (o + (0). This
set of alternatives is decomposed by
35 as,
C (UzEG.. (0 2 <= -00<a)) at) u
We now recall Lemma 1 of [27] Under 6-PAC strategy for bandit instance (X, 0*), let T; denote
the random variable that is the number of times amm i is pulled. Defining of = x Z'v for all x E X. we denote Ve as the reward distribution of the i-th arm of X, i.e., VØ, = N (x. 0, oz For any
i e C, know from 27 that
K
2 log(1/2.48).
Following the steps of [12 we find that
K
Σ
E(T)
log( (1/2.88)8) min max
(18)
xEXx dEC E L
For À E Px, define A(A) E/
I _
For and E Go (0*), define
0g (1 ()c, = 0 T0 = a ()+))A(A-12
where z (e, = a implying that Og (E, E C. For E G (0*), define
(z(c, = 0" 10= = a -E)A(A)-1
((A)
where =T,=(c,A) = a implying that 0z(c, C.
Defining e, e if z E (0*) and 6= = if E (0*),, we find that the KL divergence between Vo,i and (o.(e.)), given by:
[2] (0" (c, 2)))
20
(z 0 - a + e2) 22
==TA(A)-
20
A(2)
{2T (c))
33

---

Returning to Eq. 18
1 k
BT)) 2 (1g(2/) min max xEPx dEC AcKT(vo AKTTvo-,sillp. allvo,)
1
log(1/2.48) min max XEXx ZEZ
Ei=l A (11100.cc..))..)
{2TA(A) 112]
log(1/2.40)
min max XEPx =E2
Ei=(( (: - - A(2) 20
A(A)-12
{=T A
(a) llg((/22 min max
XEPx #E2
(=
(=))2T((A)) A(A)-1 (2/ X 23
A(A)-²z
oi
x' A(A) -1z
= 2 llg((12))4)
min max
xEPx 2E2
(z 4r + c2)
where (a) uses the fact that Σ X
K
A(A). Letting 6, establishes the result.
F22
Upper Bound
We now prove the upper bound on the sample complexity Alg. 2 for level set estimation. This proof follows similarly to the upper bound on the sample complexity of Alg. 2 for best-arm identification shown in App. E.2 Note that each round E N. Alg. 2 maintains a set Z₃ of undecided items, a set Ge of items estimated to have value exceeding the threshold a, and set Bg of items estimated to have value falling below the threshold a.
F.2.1 Proof of Correctness
To begin, we show that that for all rounds E of Alg. 2 the error in the estimates of 2T 8 for all E Z are bounded by eę with probability at least á for å (0, 1).
Lemma F.1. For all l E N and E Z, with probability at least 1 - 8 for 8 (0, 1).
(z, 0g 0) S cg.
Proof. This proof follows identically to Lemma E.I by replacing 2n with the zero vector.
We now apply the preceding result to show that with probability 1 - 8 for d E (0, Alg. 2 does not place items in the wrong category.
Lemma F.2. With probability least for (0, 1), for any z Ze, & N, such that -0 a,
(z, + > a,
and for any = Z, such that = T a.
(z, 0i) Eo a.
Proof. Consider Ga so that T a. Using Lemma with probability least 8 for 8 E 10 we have
(2,0c) + = (2, 0g - 8*) + ce + (2,0*) (2, 0r - 8r) + c t
2 a.
By the procedure of Alg.
2 this guarantees Ge+1 C G..
34

---

Now, consider E Ba so that T0 8r < a. Using Lemma F.1 with probability at least 1 - 8 for å E (0, 1) we have
(z,0z) -e = (z, 0z - 0-) - + 0*)
< (2, 02 0*)
S a.
By the procedure of Alg. 2 this guarantees B C Ba.
We now show that any Z such that T al > 2e is removed from the active set, Zz, in round E N of Alg. 2 with probability at least for (0, 1). Since et - 0, this proves that we will eventually identily G. correctly.
Lemma F.3. With probability at least - for 8 E (0, for any E N and E Zz such that 1=,00) al > 2ee.
Oz) - -al >
Proof. Set 8 (0,1), 1). Let begin by considering any Ze such that (2,0r) > 2cg. Using Lemma F1 with probability at least 5,
(2, 01) - El (2, --00-00) + (2,0") Ee
ce + (2, 0*)
> a.
Now, consider any E Zz such that (2, < -2ct. Using Lemma F.1 1 8,
with probability at least
(2,08) + c {2, 02 8r) + (2,00) 0*)
$ E + (2, 0*) +
Hence, for Zz such that (22,8)) al 2e,, have that (2, 0.) - cel with probability at least 1 - 8.
By the elimination conditions of Alg. this guarantees that the E Zz such that (2,,0) aal > 20g are not included in Zz+1-
F.2.2 Proof of Upper Bound on Sample Complexity
Now we prove the upper bound on the sample complexity of Alg. for the transductive level set identification problem.
Proof of Theorem 4.2 transductive level set identification. Set E 1). Assume that max (zz 0*) al < 2. Define S; {2 Zz (2, 0*) al < 4ez} for l N. Note that
by assumption 2 S = Z1. Lemma F3
implies that with probability at least - 8, we know
Ze C S for all f E N. This means
g(Zi) inf max || xE 2E2,
Exex do 87 )
< inf max || xEXx zES;
Excx 55.
= -S())
35

---

For 2 (4A "), we know that St = 0, thus the sample complexity to identify the set G. is upper bounded as follows.
[oga(1A 11
1og,(15
11
Σ
(a)
d(d+1)
+ +
2
FEX
E
Mogg (4
Σ
d(d 1)
+2
3
E " ((z)) 1og(88))222 (21/0]
2
2
F=1
[10g(444 11
d(d + 1) 2
[log2 (4A (4A
+
3e, 3 ((e) 1og((82 31/0)
d(d + 1)
[log (4A
(4A-1))+
2
(4A (4A-1)) Doga 1oga
8[log (4A -))19|
8
3 log
2d g(t),
8
where (a) follows from Lemma below. With probability
E.10
We now relate this quantity to the lower bound and explain
||
ExEx As T
Vis inf max XEPx ZE2
(z -a)2
||
Excx do ux o3
max XEPx E5 (S(oog(111 -1] =EB:
inf
max
(2 (= Hr - =x)
||
xx og Loer de
inf
max
max #E5
XEPx F5 [10 11)
2- 2)1
1o (4A Σ
1
inf
2
max SES;
||I||
16 logg (4A-1)
AEPx
Evex de
1=1
of
[4gg(44 211 Σ
3
22r inf max
||
16 [olllog244 (4A-1)
xEPx #ESt
Emex du ret
[ogg(4A-1 111
Σ
22r inf max ||=|| xEPx ZES;
32 logg (42 1
Em 201
[log((14
'91
1
Σ
22 (($).
32 [og, ( (4A 11)
where (a) follows from the fact that the maximum of set of numbers is always greater than the average, (b) by the fact that the minimum of sum greater than the sum of the minimums, and
(c) from Lemma E.9 Consequently, putting the previous pieces together we find that the sample
36

---

complexity can be upper bounded as
Togg (4A
d(d+1) 1)
Σ
Te S
flog2( (4A 1)1
TEA
[1gg(11 11
8 (1og2(4A-1))
3 log
Σ
2 g()))
8
d(d + 1)
[log2 (44-1)
(0logg(4A-)))))
966log (4A log
LL
where the dependency d(d 1)/2 can reduced to d by Proposition A.1
This proves the result.
G Comparing Identification Lower Bounds
In this section, we use the general notation for the level set and best-arm identification problems developed in Section 4 Define
|| 10-99 911 (l( (Exex Asster
POBJ == o min
max
XE AE PEBII
max
{(h q) fr bOBJ} }
which is the lower bound for both BAI and LS by [12] and 35 in the homoskedastic case when upper bounding the variance.
Lemma G.I. In the same setting Theorem 4.1
min POBJ S VOBJ I o2 max POBJ=
and both the upper and lower bounds are tight.
Proof. Consider semidefinite matrices A, and C in Raxdd such that A B 3 B-1 3 A- Hence, for E Rd, || || (ullB-1 < || Defining
Then C-1 1
A(A) =
X;
i=
we note that
K
K
A 3 A(A) 3
A
0²
max
min
Hence,
2 |
)-1 < || A(A)= S on
|121
Applying this to the result of Theorem 4.1 and invoking Lemma E.8
that
|| allo A--
2 min max XEPx WeHOoB.
{(h TO=
O0= - bOBI)" 1 ||/ - 9 all2(1)-1
max XEPx he dEBBI ((h 9) T 0r bORl) 1
min
|| 9 [ E.Ex A. T)
22 min
max max Px hEHoBII
{(h - 9) T Hr DOBJ
Recalling that
|| - 9l { [E-ex d, T)-
POBI == 2 min
max XEPx KE Qoma
{(h q) 0r - bOB.)
37

---

is the lower bound in both the best amm and level set problems for the homoskedastic variance algorithm in heteroskedastic noise setting (when upper bounding the variance), we see that
S #OBJ/POBI S
Moreover, both the upper and lower bounds are tight by taking o² = minn Vor X (to match the lower bound) and o o max: Var
(to match the upper bound).
H
Experiment Details
This Appendix gives more details on the experiments presented in Section S
H.1 Oracle Designs
We demonstrate the difference in oracle allocations referenced by Experiments 1-3 in Section 5
We begin with Experiment in Fig. 4 where the oracle distribution that assumes homoskedastic variance devotes more attention
informative directions with smaller magnitude. contrast, heteroskedastie oracle balances evenly because each informative arm has equivalent signal-noise ratio when accounting for variance.
Next, we analyze Experiment 2 in Fig. S In this setting the oracle distribution that assumes homoskedastic variance allocates evenly between three informative arms, while the heteroskedastic oracle prioritizes the informative directions with less variance.
0.6
Homoskodasic
Homosleddetiic
Helenoskedladic
0.4
Density
0.3
Density
0.3
0.2
0.2
0.1
0.1
0.0
0.0
2
Informative Arms
Informative Arms
Figure 4: Experiment I, the Heteroskedastic Ora- cle balances evenly between the informative arms.
Figure In Experiment 2, the Heteroskedastic Ora- cle prioritizes informative arms with less variance.
Lastly, we examine the oracle distributions for the multivariate testing experiment in Fig. Note that the first four arm have higher variance than the last four arms. We can see in Fig. that the Heteroskedastic Oracle prioritizes the second group of arms because these will require more samples to identify their effect sizes.
H.2 Assuming Homosekedastic Noise
If assume that there is homoskedastic noise heteroskedastic setting, then need upper- bound the noise with 2 in the sample size calculation of Alg Alg order to maintain correctness. In Section 5. compare H RAGE RAGE; the latter the maxx upper-bound and is described in
Alg.
38

---

Homoskedastic
Heteroske dastic
0.4
0.3
Density
0.2
0.1
0.0
2
3
6
7
Arms
Figure 6: In the multivariate testing experiment, the Heteroskedastic Oracle prioritizes the that have higher variance, i.c., the arms that include the second variation the first dimension.
Algorithm 5: (RAGE) Randomized Adaptive Gap Elimination
Result: Find x* arg m 2 =T lr for BAI G. E 2 8r a} for LS
Input: X' E IRd Z E Rd, confidence 8 E (0. OBJ E (BAI,LS), threshold a E R 2 Initialize: + 1, 2 + Z. 91 + B + (
while (1Zg] > 1 and OBJ=BAI) or (|
and OBJ=LS) do Let de Px be minimizer of q (Zz)) OBJ-BAA and g(A, Ze) if OBJ=LS where
q(V) infxePx {(>: V) = infxePx max,ev ||
zex Aa
Set = 2- 20 20 a( Ze) (8g(8((12)/0)
Pull arm x E X exactly [Te times for ny samples and collect { Ne, 18
Define At Em I be = Eie Le,iee, and construct 0e A bt
if OBJ is BAI then
2441 < ZA12 Ze max 0.) ec)
else
G.t1 (z Z: (2,0,) t, > a
12
Bz + B, U1= E Z, (z, 0z) + < at
Ze41 Ze1119 (4+1 Be+1}}
end
15
E+ {+1
end
Output: Z, for BAI Gr for LS
39


Reviews:
[{"review_id": "IgwVz9OhLf", "reviewer": "Reviewer_mrcD", "summary": "This paper considers the online linear experimental design problem that is affected by heteroskedastic noise. The authors propose a two-phase sample splitting method aimed at estimating the unknown parameters of noise variance, utilizing the principle of G-optimal experimental designs. \n\nFurthermore, the study extends the application of the proposed methodology to handle fixed confidence transductive best-arm and level set identification problems under conditions of heteroskedastic noise. The paper also deals with the instance-dependent lower bounds.", "questions": "1. How is the current approach compared to the previous works? Both in a theoretical sense and numerical experiments. \n\n2. What motivates the problem setting, that is, the sensing noise variance is $x^T \\Sigma x$. ", "limitations": "See above. ", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This paper does solid work and is in relatively good shape. ", "weaknesses": "1. The problem is not well motivated. It is unclear what are the practical applications of this problem. \n\n2. The numerical experiments only contain some toy examples. It is unclear how it performed in a large-scale set. \n\n3. Comparision between the previous works are not present. \n\n4. The problem setting looks weird. The sensing noise variance is $x^T \\Sigma x$, why it depends on the sensing vector $x$? What are the motivations for this problem setting? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments. It is encouraging to hear that the paper does solid work and is in relatively good shape. \n\n- Motivation for the Problem- The problem is motivated by: (i) the presence of heteroskedastic errors in numerous applications; and (ii) the significant impact of heteroskedastic error on the performance of methods which do not adequately account for it. First, we illustrate the ubiquity of heteroskedasticity with examples such as e-commerce [Kaptein and Parvinen, 2015] and the volatility of stocks across sectors [Dai et al., 2022]. Heteroskedasticity is also commonly encountered in clinical data [Grissom, 2000, Zhou et al., 2023], spatial data [Yan et al., 2022, Sato and Matsuda, 2021], and genomics [Ting et al., 2023, Dumitrascu et al., 2019] among other areas. We then show that algorithms in the best-arm and level set identification setting improve dramatically when they account for heteroskedastic variances. This is demonstrated theoretically and empirically in Sections 1, 4 and 5.\n- Numerical Experiments- In our simulations (Section 5), the first two settings are standard benchmark examples that illustrate important features of the algorithm [Soare et al., 2014]. The third setting considers Multivariate Testing, which is a relevant and realistic paradigm in advertising [Hill et al., 2017].\n- Comparison- We place our work in the literature in Section 2 (Related Works). We also make comparisons in terms of theory (Sections 3 and 4) and numerical experiments (Sections 1, 3 and 5). The theoretical comparisons of Sections 1 and 4 involve $\\kappa$, which quantifies the level of heteroskedasticity. We show that the state of the art suffers from a multiplicative dependency on $\\kappa$, while our method only has an additive dependency. In Sections 1 and 5, we compare H-RAGE to RAGE empirically.\n- Motivation for the Noise Structure- In the Related Works Section, we cite several papers in the active learning setting that have used this noise model [Chaudhuri et al., 2017, Soare et al., 2013]. Additionally, our heteroskedastic variance structure arises in linear mixed effects models [Huang et al., 2022], which are used in a variety of experimental settings to account for multi-level heterogeneity (patient, spatial and block design variation [Oberg and Mahoney, 2007]). In Section 1.1, we will note the connection to the linear mixed effects model covariance structure. Lastly, the paper mentions that our heteroskedastic variance model generalizes the standard multi-armed bandit to a setting where each arm has its own variance (in this case, the measurement vectors, $\\mathcal{X}$, are the standard bases and $\\Sigma^*$ is diagonal)."}, {"review_id": "3HAl6C9JfT", "reviewer": "Reviewer_VoEg", "summary": "The paper considers the problem of Experimental Designs for Heteroskedastic Variance. Here, a learner has access to finite set of measurement vectors $\\mathcal{X}$ and may query observations of the following form for chosen $x \\in \\mathcal{X}$: $y = x^\\top \\theta^* + \\eta$ where $\\eta$ is mean-zero and sub-Gaussian with variance $\\sigma^2_x = x^\\top \\Sigma x$. The paper first designs a procedure to estimate $\\Sigma$ and then utilizes this estimate for two related problems featuring linear objectives: Best-arm Identification and Level-set Identification. The paper then shows that when heteroskedastic variance is present, this procedure leads to improved results for these tasks. The paper then conducts empirical experiments to validate their claims.\n\nThe main technical contribution of the paper is the procedure to estimate $\\Sigma$. If $\\theta$ were known, $(y - \\theta^\\top x)^2$ provides an unbiased estimate of $\\sigma_x^2$. However, since $\\theta^*$ is not known, the paper first estimates it via a weighted least-squares estimator where the weights are chosen to ensure that each $x \\in \\mathcal{X}$ is well-represented in the spectrum of the weighted second-moment matrix. This ensures that $\\theta$ is accurate (at least along the $x$ in $\\mathcal{X}$). Then, a similar sampling procedure is used with the vectors $\\phi_x = \\mathrm{vec} (xx^\\top)$ and noting that $(y - x^\\top \\theta^*)^2$ is an unbiased estimate of $\\sigma_x^2 = \\mathrm{vec} (xx^\\top)^\\top \\mathrm{vec} (\\Sigma)$ which is a linear equation in $\\Sigma$. A similar weighting procedure is used to obtain an estimate of $\\Sigma$ such that $\\sigma_x^2$ is well-approximated for any $x \\in \\mathcal{X}$. These estimates are then used to design improved strategies for the aforementioned estimation tasks with linear objects.\n\nOverall this is a nice paper with strong technical results. The setting seems novel and interesting and the technical analysis is non-trivial. The main question I have for the authors is that the sampling procedure incurs large sample complexities in some extreme cases. Say, $\\mathcal{X}$ corresponded to the standard basis vectors. In this setting, the error bound on estimating $\\sigma_{e_1}$ depends on $\\max_j \\sigma_{e_j}$ while intuitively this dependence seems extreme. Furthermore, the fact that $d^2$ samples are needed to estimate $\\Sigma$ only along the directions in $\\mathcal{X}$ also seems too large if $\\mathcal{X}$ is not too large. It would be great if the authors can comment on these dependencies.\n", "questions": "See main review", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "See main review", "weaknesses": "See main review", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and positive comments.\n\n- This is a good point. We focus on a uniform bound over variance estimates because this is necessary for the best-arm and level set identification algorithms. In these procedures, the uniform bound quantifies the error in both the experimental design and the weighted least squares estimator. We then determine the number of samples needed to control this bound to identify the correct arm (or arm set) with $1-\\delta$ probability. \n- In paradigms where $|\\mathcal{X}| < d^2$, there is not enough information to accurately estimate $\\Sigma^*$. Consequently, it may be advantageous to ignore the structure and estimate the variances of the arms separately as Fontaine et al. [2021]  does. We could then use these estimates in the best-arm and level set identification algorithms with their corresponding bounds and maintain the correct identification rate. However, we focus on the case where $|\\mathcal{X}| >> d^2$, which aligns with a majority of the literature."}, {"review_id": "q1fnz5AtDH", "reviewer": "Reviewer_jG9W", "summary": "This paper investigates the problem of linear regression under heteroskedastic noise with adaptive data collection.\nThe proposed algorithm begins with estimating the covariance structure via Alg 1 and then using this in Alg 2 to construct an optimal design for estimating $\\theta$. The algorithm is instance-optimal up to an additive term depending on the conditioning $\\kappa$. They conclude with experiments demonstrating their algorithm's performance.", "questions": "* Regarding the optimality of Alg. 2, what is the appropriate regime to be thinking of for the quantities in Theorems 1 and 2? For example, how should the $\\log(\\Delta^{-1})\\log(|Z|/\\delta)$ multiplicative factor differing between the upper and lower bounds compare against $\\psi^\\star$. Also, how large will $d$ be, given that the additive suboptimality terms has a $d^2$ factor in it?\n\n\n\nMinor:\n* In Alg. 1, should it say $\\lambda^\\star_x$ in line 4 and $\\lambda^\\dag_x$ in line 8? Otherwise, I don't see how the quantities computed in lines 3 and 7 are used.", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* This work analyzes a useful problem and proposes a nice adaptation of RAGE to their setup.", "weaknesses": "* I'm not sure how common or realistic this assumption is, but the heteroskedasticity model (i.e., that $\\sigma_x^2 = x^T\\Sigma^\\star x$) seems very restrictive to me. It would be nice to have some further discussion about this and possibly about extending the algorithm to more general noise settings.\n* As they remark in the paper, the lower bound is weakened by the fact that the noise variances are considered to be known, and so the lower bound essentially becomes the same as Fiez et al. The lower bound would be much more compelling to me if it could incorporate the difficulty associated with estimating $\\Sigma^\\star$ (which could also address the current $\\kappa$-dependent gap between the upper and lower bounds).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and positive comments.\n\n- In the Related Works Section, we cite several papers in the active learning setting that have used this noise model [Chaudhuri et al., 2017, Soare et al., 2013]. Additionally, our heteroskedastic variance structure arises in linear mixed effects models [Huang et al., 2022], which are used in a variety of experimental settings to account for multi-level heterogeneity (patient, spatial and block design variation [Oberg and Mahoney, 2007]). In Section 1.1, we will note the connection to the linear mixed effects model covariance structure. Lastly, the paper mentions that our heteroskedastic variance model generalizes the standard multi-armed bandit to a setting where each arm has its own variance (in this case, the measurement vectors, $\\mathcal{X}$, are the standard bases and $\\Sigma^*$ is diagonal).\n- To address your question, the $\\log(\\Delta^{-1})\\log(|Z|/\\delta)$ multiplicative factor results from running the algorithm in rounds and is present in the homoskedastic setting as well. It should be small compared to $\\psi^*$ as long as the problem is sufficiently hard because $\\psi^*$ depends polynomially on the gap that is most difficult to learn (as opposed to logarithmically on the smallest gap and arm set size).  The dimension $d$ is an instance-dependent parameter. As we argue in the paper, it is natural for the suboptimality term to depend on $d^2$ since this is an instance dependent parameter that scales with the degrees of freedom in $\\Sigma^*$ and the lower bound assumes that $\\Sigma^{\\ast}$ is known. "}, {"review_id": "B18LvhbxmS", "reviewer": "Reviewer_Jphn", "summary": "This paper studies linear experimental design in the presence of heteroskedastic noise. The model can observe noise linear measurements generated by unknown model parameters, with sub-Gaussian covariance depends on the measurement vector. The goal is to estimate the unknown covariance matrix and corresponding covariance wrt measurement $x$. The algorithm works as follows: it uses the first half of the samples to construct a least-squares estimator for the model parameter, then use the second half to estimate the noises and consequently, the covariance. This algorithm leads to a sample complexity depends quadratically on $d$. As applications, the proposed approach can be used for best arm identification and level set identification. Finally, experiments are conducted to empirically validate the algorithm.", "questions": "What is the runtime complexity of the proposed algorithm?", "limitations": "Yes.", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper studied an interesting problem, in practical setting, heteroskedastic noises usually present, so it is important to study the sample complexity and efficient algorithm for this setting.\n\nThe presentation of the paper is good, it is a good mixture of motivation, intuition and technicality. I enjoyed reading the paper.\n\nThe results obtained in this paper are strong.", "weaknesses": "It will be better to also include the runtime complexity of the proposed algorithm. Linear bandits now admit highly efficient algorithms with curated data structures [Yang et al., ICML'22] and so does efficient experimental design [Allen-Zhu et al., ICML'17]. It will be interesting to study the runtime complexity of the proposed algorithm.\n\n[Yang el al., ICML'22]: S. Yang, T. Ren, S. Shakkottai, E. Price, I. Dhillion, S. Sanghavi. Linear Bandit Algorithms with Sublinear Time Complexity.\n\n[Allen-Zhu et al., ICML'17]: Z. Allen-Zhu, Y. Li, A. Singh, Y. Wang. Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and positive comments. We will cite the papers you listed.\n\nThe time complexity depends on the Frank-Wolfe method. Defining $k\\in \\mathbb{N}$ as the number of steps taken by the procedure, the algorithm has a worst case convergence rate of $O(1/k)$ [Jaggi, 2013]. Consequently, the time complexity to achieve a distribution within $\\epsilon$ of the optimal value is $O\\left [ \\left (|\\mathcal{Z}|d^2 + |\\mathcal{Z}|^2d + |\\mathcal{X}|d^2 \\right ) /\\epsilon \\right ]$. This is not a major concern in practice since the optimal distribution is computed in rounds and can be done offline, while online we can simply sample from the distribution."}]

Author rebuttal:

Meta-review: Most reviewers felt this was a technically solid paper. It considered experimental design for regression problems for the noise for covariate x is of the form x^TSigmax for some unknown Sigma. It uses half of its allocated samples to learn Sigma and the rest to learn the parameter vector. The paper draws on techniques from the linear bandits literature (specifically for the “pure exploration problem”). Most reviewers felt the paper was well-written and provided interesting theoretical results, although it could have done a better job motivating the problem.
Decision: Accept (poster)