High-dimensional Contextual Bandit Problem without Sparsity
Authors: Junpei Komiyama
Masaaki Imaizumi
Venue: NeurIPS 2023 poster (2023)
Keywords: multi-armed bandits
linear bandits
contextual bandits
overparameterized models
high-dimensional models
online learning
TL;DR: Contextual linear bandits with high-dimensional linear covariates

Abstract: In this research, we investigate the high-dimensional linear contextual bandit problem where the number of features $p$ is greater than the budget $T$, or it may even be infinite. Differing from the majority of previous works in this field, we do not impose sparsity on the regression coefficients. Instead, we rely on recent findings on overparameterized models, which enables us to analyze the performance of the minimum-norm interpolating estimator when data distributions have small effective ranks. We propose an explore-then-commit (EtC) algorithm to address this problem and examine its performance. Through our analysis, we derive the optimal rate of the ETC algorithm in terms of $T$ and show that this rate can be achieved by balancing exploration and exploitation. Moreover, we introduce an adaptive explore-then-commit (AEtC) algorithm that adaptively finds the optimal balance. We assess the performance of the proposed algorithms through a series of simulations.

High-dimensional Contextual Bandit Problem without Sparsity
Junpei Komiyama New York University j Lunpei@komyyane info
Masaaki Imaizumi The University of Tokyo / RIKEN Center for AIP imaizumi@g ecc. u-tokyo.ac. ac.
Abstract
In this research, we investigate the high-ding lith-iimensional linear contextual bandit prob- lem where the number of features p is greater than the budget T, or may even be infinite. Differing from the majority of previous works in this field, we do not impose sparsity on the regression coefficients. Instead, we rely on recent find- ings overparameterized models, which enables to analyze the performance the nooim interpolating estimator when data distributions have small effective ranks. We propose this problem and examine its performance. Through our analysis, we derive the optimal rate of the ETC algorithm in terms of 7' and show that this rate be achieved by balancing exploration and exploitation. Moreover, we introduce an adaptive seplore-then-comeee
ssplore-then-comeee
(EtC) algorithm to address
(AEtC) algorithm that adaptively finds the optimal balance. We assess the performance of the proposed algorithms through a series of simulations.
Introduction
The multi-armed bandit problem [Robbins, 1952, Lai and Robbins, 1985] has been widely studied in the field of sequential decision-makin problems in uncertain environments, and it can be applied to variety of real-world scenarios. This problem involves an agent selecting one K arms each round and receiving corresponding reward. The agent aims maximize the cumulative reward over rounds by using a clever algorithm that balances exploration and exploitation. In particular, a version of this problem called the contextual bandit problem [Abe and Long, 1999, Li et al., 2010] has attracted significant attention in the machine learning community. By observing the contexts associated with the arms, the agent can choose the best arm function of the contexts. This extension enables us to model many personalized machine learning scenarios, such as recommendation systems [Li et al., 2010, Wang al., 2022] and online advertising [Tang et al., 2013], and personalized treatments [Chakraborty and Murphy, 2014].
Most of the papers about stochastic linear bandits assume that the number of features is moderate [Li al., 2010, Chu et al., 2011, AbbassiYadkond et al., 2011]. When p o( to the number of rounds T. the model is identifiable, and the agent can choose the best arm for most rounds. However, recent machine learning models desire to utilize even larger number of features, and the theory of bandit models under the identifiability assumption does not necessarily reflect the modern use of machine learning. Several recent papers have overcome this limitation by considering sparse linear bandit models [Wang et al., 2018, Kim and Paik, 2019, Bastani and Bayati. 2020, Hao et al., 2020, Oh al., 2021, Li al., 2022, Jang et al., 2022]. Sparse linear bandit models accept very large number of features' and suppress most of the coefficients by introducing the &l regularize.
Typicallyy the number of feature p can be exponential the number of datapoints T.
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

That said, the sparsity imposed by such models limits the applicability of these models. For example, in the case of recommendation models based on factorization, each user is associated with dense latent vector [Rendle, 2010, Agarwal et al., 2012, Wang et al., 2022], which implies the sparsity is not unlikely the case. Another possible drawback of sparse models that requires the condition number to be close to one (e.g., the restricted isometry property, see Van De Geer and Bühlmann [2009] for review). ) This implies that the quality of the estimator is compromised by the noise on the features that correspond to small eigenvalues. Furthermore, it is still non-trivial to select proper value the penalty coefficient as that small changes in the choice of coefficients significantly alter feature selection, and Miolane and Montanari [2021] show a limitation of the conventional theory on the choice of penalty coefficients.
For example, Hara and Maehara [2017] claims
In this paper, We consider an alternative high- nigh-dimensional linear bandit problem without sparsity. We allow p to be as large as desired, and in fact, we even allow p to be infinitely large. Such an overparameterized model has more parameters than the number of training data points. A natural estimator in such case is an interpolating estimator, which perfectly fits the training data. We adopt recent results that bound the error of the estimator in terms of the effective rank [Koltchinskii and Lounici, 2017, Bartlett et al., 2020] on the covariance of the features. When the eigenvalues of the covariance decay moderately fast, we can obtain concentration inequality on the squared error of the estimator.
The contributions of this paper are as follows: First, We consider explore- esplore-then-comee them- (EtC) strategy for the stochastic bandit problem based on the minimum mimimum-norm norm interpolating estimator. We derive the optimal rate of exploration that minimizes regret. However, ErC requires model-dependent parameters on the covariance, which limits the practical utility. To address this limitation, we propose an adaptive explore-then-comme (AEiC) strategy, which adaptively estimates these parameters and achieves the optimal rate. We conduct simulations to verify the efficiency of the proposed method.
2 Preliminary
2.1 Notation
For N, [x] := (1,2....... For x R. the notation [x] here denotes the largest integer that is less than or equal to a scalar x. For vectors X' E RP, (X, X') := X X' is an inner product, |III|] == (X, X) is (2-norm. For a positive-definite matrix A E X || (X, Ax) is weighted 62-norm. || denotes an operator norm of A. 0()) (-)) and @(.) denotes Landau's Big-O, little-o, Big-Omege little-omega, and Big-Thett notations, respectively. ((.), and ((-) the notations that ignore polylogarithmic factors.
2.2 Problem Setup
This paper considers a linear contextual bandit problem with arms. We consider the fully stochastic setting, where the contexts, as well the rewards, are drawn from fixed distributions. For each round / E [7] and arm i E [K], we define x (1) as aossa--daee p-dimensional zero-mean sub-Gaussian vector. We assume ( (1) is independent among rounds (i.e., vectors in two different rounds 1, are independent) but allow vectors (²)) (t), x(2) (I)...,, (x) be correlated with each other. The forecaster chooses arm [(t) [K] based on the (r) values of all the arms, and then observes
a reward that follows a linear model as shown in
y(uii))) (T) ((t))) + +(()).
The unknown true parameters g00) for each arm i [K] lie in a parameter space + c RP, and the independent noise term (() has zero mean and variance 2 > 0. We assume that E(t) is sub-Gaussian, and for the sake of simplicity, we assume that does not depend on the choice of the arm. However, our results can be extended to the case where E(t) varies among arms. We assume that each ((i) are bounded ||0 z 0 For each i E [K], we define a covariance matrix y (() (1) RPXP
We define i" (1) == argmax [K] (I) as the (ex ante) optimal arm at round 1. Our goal is to design an algorithm that maximizes the total reward, which is equivalent to minimizing the following

---

expected regret [Lai and Robbins, 1985, Auer et al., 2002];
R(T) B Σ (x(m))
(1) 0 (x)m
where the expectation is taken with respect to the randomness of the contexts and (possibly) on the choice of arm ((1).
2.3 Theory of Overparametrized Models
The primary focus of this paper is on scenarios where the number of arms K moderate, but the number of features is greater than the budget T, possibly to the point of being infinite. The efficiency of linear regression models in such scenarios depends significantly on the covariance matrix, Σ Unlike sparsity, the theory of benign overfitting tightly examines errors using the decay of the eigenvalues of the covariance matrix of the context. In particular, if the decay rate of the eigenvalues is certain level, the error in linear regression converges zero, in high-dimensional spaces. To provide a more rigorous analysis of eigenvalue decay, the concept of effective rank introduced in Section 2.4.
Remark 1. (Dependence on 7)) In accordance with Bartlett [2020], permit the covariance ma- trix I to depend on In other words, we consider the sequence of covariances Σ (1), E(" (2).... for each T = 1, ..... The linear regression is consistent if the effective rank of (T) grows sufficiently slow function of T.
2.4 Effective Ranks of Covariance Matrix
For covariance matrix (0 for E [K] and [p]. let ( be its k-th largest eigenvalue, such that y(0 Σi= u "k ("k, concept of effective rank as
(i) (T with order 11th 2 (1 2 ... 2 1 and eigenvectorss " We define the
rx (E == _e and (E ()
1
Ej>x(1
The first quantity F& (E(0) is related to the trace of E00, and the second quantity R& (E())) is related to the decay rate of the eigenvalues.
The effective rank is used as measure of the intrinsic complexity of high-dimensional data, by rigorously capturing a decay rate of cigenvalues. If the covariance matrix ( is an identity matrix of size p. then ro(E and ()) are both equal to p (the rank of ( However, we anticipate that these quantities will be less than p. which enables learning with fewer samples. In Figure 1, we plot of the effective rank in & with certain cases of eigenvalues {d of Σ. Even though Σ is full-rank, the effective rank (Σ) is sublinear in k, which reflects the intrinsic low-complexity of data.
Because of this property, the effective ranks are used in modern high giggh-iimnsiinall statistics. Koltchin- skii and Lounici [2017] evaluated concentration incqualities for high-dimensionall random matrices using the notion. Bartlett al. [2020], Tsigler and Bartlett [2020] evaluated the prediction error of a high-dimensional linear regression using the effective ranks and showed the consistency of the prediction.
3 Explore-then-Commit with Interpolation
The Explore-the Huplore-then--oe linear bandit problems, and it has been shown to be effective in previous studies such as Hao et al. [2020], Li et al. [2022]. The EtC algorithm operates by first conducting To NK T rounds of exploration, during which it uniformly explores all available arms construct estimator @0)) for each arm i e [K]. After the exploration phase, the algorithm proceeds with exploitation. Let N be the number of the draws of arm and (!) (x(") ..... x Nx and (() = (y(") ..... ((O)) ) e R
(EtC) algorithm is well-known approach for solving high dich-niiensional

---

Eigenvalue λk
Effective rank rk(2)
Effective rank Rx(2)
10
50
Case
0.5
0.0
10
50
Case 2
0.5
25
0.0
10
k
k
Figure 1: Eigenvalues 2g (left), the effective rank (2) (middle), and the effective rank R (E) (right) with k I,... 15 and T = 3; Case I: 22 = Ck-1+1/72.0 and Case 2: dx = C(exp(-R) (k) T exp(-T)/p). Case considers decay that slightly faster than k-1, whereas Case considers an exponentially fast decay. The slower increase of r2 and (E)) in Case 2 reflects the impact of the eigenvalues' faster decay.
be the observed contexts and rewards of arm i, where (x(), y,!') is the corresponding values on the n-th draw of arm í. Since choose 1(r) uniformly during the exploration phase, these independent and identically drawn samples from the corresponding distribution.
For estimating the parameter g(i), we consider the minimum- interpolating estimator that perfectly fits the data, which reveals its advantage in recent results on high-dimensioos [Bartlett al., 2020]. Rigorously, we assume p > N and and consider the following definition:
@ argmin ||012 0 R
Σ
(Y
(0, x(.x
(Y X JnsN
This estimator has a simple representation ØV)- presented in Algorithm 1, which utilizes the aforementioned interpolating estimator. the subsequent sections, we will first discuss the assumptions on the gata-generating process, followed by an analysis of the accuracy of the estimator. We then present an upper bounds on the regret of the ErC algorithm.
(x)))) The EtC algorithm
4 Theory of Exploretthen-Commit
This section analyzes the EIC algorithm. If we were to fix the number of samples, this theory would largely align with the existing literature [Bartlett et al., 2020, Tsigler and Bartlett, 2020]. However, the unique challenge in our case arises from the fact that the EIC selects the number of samples used to construct estimator to balance between exploration and exploitation.
4.1 Assumption and Notion
We consider a spectral decomposition 0 ((() A (0 (((O)) with the matrices (operators) v() and (i) for each arm [K]. then impose the following assumptions.
Assumption isub-Gaussianity). For all N and i e [K], the followings hold:

---

Algorithm Explore-then-Conee (EiC)
Require: Exploration duration T6-
for f = l,.., do
Observe (() (z) for all [K].
Choose ( = K.
Receive reward (I).)
end for
for E [K] do ((0) (X (xx)) (XO))
end for for
To I...., do
Observe X (t) for all i [K].
Choose 1(1) argmax (x) ())
Receive reward (r)
end for
There exists a random vector Z (t) such that (() più (A()))222 which is independent elements and sub-Gaussian with parameter 23 > 0, that is, for all a IR, we have B[exp( (A, (r)) exp(<211a11/2)
Moreover, g(t) is conditionally sub-Gaussian with a parameter K2 0, that is, for all A R, we have Blexp(Ag(n) x (r) s exp(x2
The first bullet point of Assumption requires that the features are multivariate sub-Gaussian and their tail is not too heavy, which is important for concentration inequalities on random variables [Vershynin, 2018]. The second bullet point of Assumption I, which states that rewards involve sub-Gaussian noise, is a common assumption in contextual bandit problems.
4.2 Benign Covariance
We impose a condition to be benign on the covariance matrix (() for all E [K]. The condition described using the notion of effective/coherent rank, which is commonly applied to the study of benign overfitting [Bartlett et al., 2020, Tsigler and Bartlett, 2020]. However, unlike those papers that estimate using all 7 samples, we only use a portion of the data for learning.
We first define the coherent rank of (() with number of samples N
k = k (i) NN == min(k NU (0) (x 2 N),
where we define mi] to0. By using the coherent rank, we decompose the error into two quantities called effective bias/variance denoted as N,T and number of samples N used for estimation.
(i) (i) N,7 based on budget of T and the
B N.T = (i) and
VO N.T
K N
N
(4)
R N
(EO)
Definition (Benign covariance). Under Assumption 1, a covariance matrix ( is benign, (()) N. o(1) and (f)
N.T o(1) hold as N,T while N = O(T).
To put it differently, Assumption and Definition state that, if we can achieve consistent estimation by using all the data for estimation, then the covariance matrix considered benign.
Technically, the benign property implics that eigenvalues decay fast enough compared with T. In particular, the following examples have been considered in the literature.
Proposition (Example of Benign Covariance, Theorem 31 in Bartlett et al. [2020] ). covariance matrix ( with eigenvalues 2() .2!) ... is benign if it satisfies one of the following.
PIt should be noted that Bartlett et al. [2020] only provided the variance term. Later on, Tsigler and Bartlett [2020] described both the variance and bias terms, which we follow.
5

---

Example 1: Let E (0, 1), p and { = k- -((+-//T" In this case, have B N.T O((T9N))HI)T) and vl0) required, and the variance dominates the bias.
N.T O(T*/N + T). For this model to be learnable, N * 7 is
Example 2: Let 2k
k-b and p = pr = O(T9) with E (0,1) and c 1-b) In this case, we have B NII O(ro(1-b)/ /N) and vli N.T
[aax O((N/TS)mx()s (1) For this model be learnable, N x Te(l-b) is required, and the bias
11. I-b 1-b
dominates the variance.
The first example is when the decay rate is near k-1, I but the trace is O(T9). The second example is when the decay rate is smaller than k-1, and the trace is O(Te(I-b)), Note that Bartlett et al. [2020] provided two other examples of the benign covariance matrices. 3 Our analysis mainly focuses on the two examples in Proposition 1, but another example is also empirically tested in Section 6.
4.3 Estimation Error by Exploration
We evaluate an error in the estimator g(0) by its prediction quality. That is, with a covariance matrix (i) and identical copy x!!) of ( study
(1 11 1 = =xy ((0(0)
((0(0,x!)) x!")) - (01) "... )
The following result bounds the error of the estimator T00) in terms of bias and variance, which is a slight extension of Tsigler and Bartlett [2020]. For [p], we define an empirical submatrix
x(I)
k:00 (x(pkk)) k) as the p k columns to the right of X and define a Gram sub-matrix E
as
K kwo
Theorem 2. Suppose Assumption 1. there exists cu such that ky N/cu and condition
number of A is positive with probability at least 1 - -cce-- -Nico, then we have
100h (00000000 1 S Cu (B v(0) N.T)
(5)
with some constant Cu > O and probability at least 1 2cve -Neeu,
Theorem 2 implies that the estimation error converges to zero if y(() has the benign property. The
assumption on the condition number of A has a sufficient condition, which is provided Lemma 3 in Tsigler and Bartlett [2020].
Moreover, the following lemma implies the tightness of the analysis in Theorem 2.
Lemma 3 (Lower bound of estimation error, Theorem 10 in Tsigler and Bartlett (2020]). Suppose
Assumption 1. These exist some constants CL, CL 0 such that, with probability at least - C1e Mc,, we have
1 I z Ct (D ).r).
(6)
In other words, the upper bound in Theorem 2 is optimal up a constant.
4.4 Regret Bound of Explore-then-Comee
This section analyzes the EiC algorithm. We introduce an error function E(N,T) T) that characterizes the rate of regret, which can be obtained by considering N,T v(i N.T) )/2 Assumption 2. (Error function*) There exists continuous function E R2 B that is decreasing in N such that ||@ ((0) g θ (E(N,T) T)) as N,T o0.
SOne of the omitted examples is the case where cigenvalues decay slightly slower than Example 1. The other example is the case where cigenvalues decay exponentially but has noise term.
*Note that the constant here depend model parameters.
'The coherent rank kyy as well (i) N. are discrete in N,T, and the error function E(N,T) introduced to circumvent the issues related to this discreteness.

---

Assumption 2 is satisfied in Examples and 2. In particular, for Example in Proposition 1, the error function is given as E(N,T) /T while for Example in Proposition 1, it is given as E(N, T) = <T<(I-b)/N)
Theorem Suppose Assumptions 1-2. Suppose that we run the EIC algorithm (Algorithm 1). Then, regrel (2) satisfies
R(T)= = Ō(L)))()
as T with O. where L(T, K) is such that
N min N TE(N/K,7)
Specifically, for Example in Proposition 1, we have L(T, K) = (2x ( whereas for Example 2 in Proposition 1, we have L(T, K) = (((cc((--))))) x2/3
Proof sketch of Theorem 4. We show that the regret-per- egrre-per-round is 0(1) during the exploration phase. Moreover, regret-per-round is O(E(To/K K,7) during the exploitation phase. The total regret is To + (BB(T//K K,)),, and optimizing To by using the decreasing property of E(N.T) in N yields the desired result.
4.5 Matching Lower Bound
We show that this choice of To function of I' is indeed optimal.
Theorem 5. Suppose Assumptions 1-2. Assume that any choice of To, the following event occurs with strictly positive probability as - oo:
the ErC algorithm (Algorithm 1). For
R(T) = 5 (L.T,)))
Proof sketch of Theorem 5. We explicitly construct a model with = 3. Let Ey = B(ToKK, In the model, the (1), (2), ( are identical, and the only difference is that the first coefficients ( =1,0 (er)), ( 0. All other coefficients are set to zero. Roughly speaking, the gap is
(x() 0 (x.)
@(1) (1=1.j=2,3) @(er) (i=2.j=3)
The regret-per-round during the exploration phase is @(1) due misidentification of the best arm between arm and arms {2. 3}. The regret-per-round during the exploitation phase is ((er) due to misidentification of the best arm between arm 2 and arm
Adaptive Explore-then-Comee
(AEtC) Algorithm
In the prior section, demonstrated that the optimal way to minimize EtC's regret is by selecting To, with To balancing the exploration and the exploitation. However, this requires knowledge of covariance matrix's spectrum, which can be difficull to obtain in advance in certain scenarios. This section explores the way to adaptively determines the extent of exploration required.
5.1 Estimator
We assume that g follows the data Sata-generatiin process of Example or 2 in Proposition 1. We use Br to denote that
1000 C.j
(8)
with some constant C2 We have Br = 1 1/7" for Example 1, and Br = b(< 1) for Example 2. Balancing exploration and exploitation in an overparameterizzed model challenging for the following reasons. First, the number of features p very large even infinite Second, the trace is heavy-tail
Namely, p for for Proposition (1) or 7 in for Proposition (2).
7

---

because the decay is not very fast. As a result, naive use of traditional method does not work. We address this issue by utilizing two estimators. The first estimator is on the trace tr(E that we extracted from overparameterization theory [Bartlett et al., 2020J, whereas the second estimator is on the estimated decay rate Br that derives from Bosq [2000], Koltchinskii and Lounici [2017].
For an arm E [K] with N To/K K draws, we define an estimated eigenvalues 7 ..... 2 > from an empirical covariance matrix ~ := N Σد x (1)x (r) We define the empirical trace to be (r( = وこ 2/ The following lemma states the consistency of the estimated trace under very mild conditions.
Lemma 6. (Error bound of empirical trace) Suppose Assumption Suppose the data generating process (DGP) of Example I or Example in Proposition 1. Then, for any Cpoly > O, with probability at least - poh, we have the following as T
00:
- tr(2())
=0(1)
Moreover, the following bounds the estimation error of each eigenvalue.
Lemma 7. Suppose Assumption 1. For any (0, 1), for any Cpoly O, with probability at least 1/T we have the following for any j 1,.... p T
p - 1/0 =0 (T(
(10)
N
Lemma 7 implies the estimator of each eigenvalue is o(1) ) if we choose N > tr( However, even if we choose large N, the error is still non-negligible for the tail of eigenvalues where 12," -1 is very small?. Consequently, X for large are not necessarily consistent, so to the effective rank and the coherent rank estimated from them. To address this, we estimate the decay rate Br, and then estimate the subsequent statistics.
Let the estimated decay rate be Br = (1/T) Ei/ log(A</ /log( (k 1) Theoretically, By is consistent for any constant 1. In practice, we can use a reasonable constant т, such 10, for robustness. To estimate the effective ranks, we use the following form
- = BB
Namely, we consider empirical analogues of the effective rank for k as
tr( and (I (tr (1)(2
Fs (
70
(2) (2)))2
We also define estimator for the coherent rank ky minfk NU (0) (F((Z 2 N). Further, we define estimators of B N of Eq. (4)
KN N
T( N.T En N.T
(()) and
R (ΣO)
Note that the estimators Fx and R3 use the trace tr (0)) which is sum of eigenvalues, instead of the partial sum of the eigenvalues that constitutes the effective rank of Eq. (3). Despite this change, this does not a asymptotic consistency of the coherent rank estimator kN.
The following lemma states that small r suffices to assure the quality of ( We study convergence
rate ( and the other estimators as follows.
"Remember that we consider ((i) g00 (7) that depends on T. Tail of eigenvalues are o(1) 7 as well. s *This because Σj jBr with ßr 1 Br 1 is tail- tail-heavy.
8

---

Algorithm Adaptive Explore-then-Commii (AEIC)
while 2, do
Observe ( (z) for all [K].
Choose ((t) =1 K.
Receive a reward (T).
if [Le*]]
N.N 2 log then
if Stop(r/K) then
To t. Break.
end if end if'
end while
for i E [K] do
g - (X(0))(XX (X "Y(
end for
for / To I.....T do
Observe (z) (1) for all [K].
Choose ((1) a (xl0) (1), )
Receive reward (1)
end for
Lemma 8. Suppose Assumption 1. Suppose DGP of Example I or Example 2 in Proposition 1. Assume that we choose N (T) such that ( o(1) for all i. Then, for any Cpoyy 0, with probability at least 1/ts, we have
(1)
(1) 1
= o()).
(1)
as T - 0o for all k E [T]. Moreover, it implies |Br - -Br-Br1= = o(1) and
B(O
F(0)
max
B
N.T
v(ū
N.T
(
(11)
N.T
N.T
Eq. (11) states that the estimated rate of error is accurate as T + co. To see this, for Example in Proposition 1, the estimated error rate is To(1) (V (TTT//++++*+ whose exponent approaches to /Ta/N- 7 as -
5.2 Adaptive Explore-then-Commii (AEtC)
The Adaptive Explore-thes Meen-C (AErC) algorithm described in Algorithm 2. Unlike EtC, the amount of exploration in AEIC is adaptively determined based on the stopping condition:
Stop (6) (N) N Cy (r) OKK T
50) N.T
(()) N.T
and Stop = Oie [K] Stop where Cr = Cr(T) is a function of T that slowly diverges to too. The first condition N Cr tr (()) ensures that N is large enough have consistency the estimators, whereas the second condition NK 2 T (1)) ((() following theorem bounds the regret of AECC.
N,T balances the exploration and exploitation. The
Theorem 9, Suppose Assumption 1. Suppose DGP of Example 1 or Example in Proposition 1. Then, for any e > O, the regret (2) when we run the AEIC algorithm (Algorithm 2) with a sufficiently slowly diverging Cr is bounded as follows T 00:
R(T) = (L((T KYT*)
where L(T, K) is the function defined in Theorem 4.
*Note that DGP of Example or implies the existence of the function of Assumption 2.

---

Theorem 9 states that, we can choose arbitrarily small > 0 and the exponent of the regret of AEiC approaches that of ErC. (Theorem 4). Note that the condition N 2 C)tr(E(i) should not dominate the balance between exploration and exploitation: For example, Cr = C log 7 for any suffices. In practice, constant Cr works.
Proof sketch of Theorem 9. We can derive that Eqs. (9), (10), and (11) for e [7] that hold with probability at least 1 - O(1/T) by setting Opoly = 2 and taking union bound over N, and thus
B N,T + D00)
log
N.T
log(To(U))
(12)
N,T + v()
[E[K] N2Crtr(E1n)
N,T
holds. Under this event, the stopping time of AEIC and ExC are at most ( times different. Given this, the proof of the theorem is easily modified from the proof of Theorem 4.
T-500 p-200 K-2 DGP:1
T-500 p-200 K-2 DGP-2
T-500 p-200 K-2
T-500 p-200 K-2 DGP:4
Assumtated Regret
proposal
ESTC
Regret
32
30
proposal
ESTC
Accumeattd Hagret
proposal
Acoumrated Hegret
proposal
ESTC
DRLasso
2.5
DRLasso
DRLasso
DRLasso
LinUCD
LinUCB
LinUIB
LinUCG
2
100
200
300
-00
300
130
300
30C
500
100
300
10
200
300
400
500
Round
Round C
Round t
Round
T=1000 p=200 K=10 DGP:1
1000 p-200
T-1000 p-200
T-1000 p-200 K-10 DGP:4
Accunratee Regret
preposal
ESTC
proposal ESTC
Acoumrettd Hegnet
ESTC
proposal
Accumrated Ragret
ESTC
proposal
DRLasso
DRLasso LinUCB
DRLasso
LinUIC
Aicsumsdee
LinUCB
LinUCC
200
400
300
800
1000
200
400
503
506
100
220
800
400
X00
1XC
200
400
600
800
100
Round
Round
Round
Round
Figure 2: Comparison of methods on four DGPs. Smaller regret indicates better performance. The solid lines are the mean of 10 repetitions and the bands represent the standard deviation.
Simulation
We consider two setups: (K, p,7) = (2, 200,500), and (K, p. (10, 200, 1000). For each setup, we consider a covariance matrix ( = c where (( ~ Uni([O.5, 1.5]) and a base covariance Σ for each
[K]. which represents a heterogeneous covariance among the arms. The base covariance Σ follows the following configurations: DGP 1:
= =k -0.5 DGP 2: Σ = diag(1) (p), = exp(-k)= + exeeppp exp(-7)/p. DGP 3: Σ = diag (... A.....p))..
--11/T and DGP 4: Σ, = 0.3 and Σ,, = 0.7 for j * E [p]. Note that the DGPs and 3 correspond to Examples 2 and in Proposition 1. DGP is benign well, while DGP 4 is not. We generate (1) from centered p-dimensional Gaussian with covariance _() g()) from a standard normal distribution which yields non-sparse parameter vectors, and ( (r) by the linear model (I) with the noise with variance 2 0.01. We compare proposal (AEIC, Cr 2) to ESTC [Hao et al., 2020), LinUCB [Li et al., 2010, Abbasi-Yadkori et al., 201 IJ. and DR Lasso Bandit [Kim and Paik, 2019].
Figure 2 illustrates the accumulated regret R(r) in relation to the round E [7]. In the first three benign DGPs, the AEiC consistently outperforms the other methods. DGP the advantage of AEiC is insignificant because the regret of any method is already small. This is because in DGP 2, a model with exponentially decaying behavior, only a small fraction of eigenvalues are important. However, AEIC performs significantly better than its competitors in DGP and DGP 3, where the eigenvalues have heavy-tail distribution. non-benign example of DGP 4, the proposed method is still comparable to LinUCB, which demonstrates the utility of interpolating estimator.
10

---

References
Yasin Abbasi-Yadkori Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011. 1, 10, 13
Naoki Abe and Philip M. Long. Associative reinforcement learning using linear probabilistic con- cepts. In Proceedings of the Sixteenth International Conference on Machine Learning, ICMI,, page 3-11. Morgan Kaufmann Publishers Inc., 1999.
Deepak K. Agarwal, Bee-Chung Chen, Pradheep Elango, and Xuanhui Wang. Personalized click shaping through lagrangian duality for online recommendation. In SIGIR '12, 2012. 2
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., 47(2-3):235-256, 2002. doi: 10.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117748):30063333077 2020. 2, 3,
4, 5, 6, 13, 19
Hamsa Bastani and Mohsen Bayati, Online decision making with high-dimensional covarittes. Oper. Rex., 68( (8(1))276-294 2020.
Denis Bosq. Linear processes in function spaces: theory and applications, volume 149. Springer Science & Business Media, 2000. 8, 19
Bibhas Chakraborty and Susan A. Murphy. Dynamic treatment regimes. Annual Review of Statistics and Its Application, 1(1):447-464 2014.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff' functions. In Geoffrey Gordon, David Dunson, and Miroslav Dudík, editors, Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 208-214. PMLR, 1 11-13 Apr 2011. 1
Dylan J. Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. In Advances Neural Information Processing Systems 32, pages 14714-1472 2019. 13
Botao Hao, Tor Lattimore, and Mengdi Wang. High- High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems,
2020. 1, 10
Satoshi Hara and Takanori Maehara. Enumerate lasso solutions for feature selection. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017. 2
Kyoungseok Jang, Chicheng Zhang, and Kwang-Sung Jun. Popart: Efficient sparse regression and experimental design for optimal sparse linear bandits. In NeurIPS, 2022. I
Gi-Soo Kim and Myunghee Cho Paik. Doubly-robust lasso bandit. Advances in Neural Information Processing Systems, 32, 2019. 1, 10
Vladimir Koltchinskii and Karim Lounici. Concentration inequalities and moment bounds for sample covariance operators. Bernoulli, 23(1): 133, 2017. 2, 3, 8, 19
Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22, 1985. ISSN 0196-8858. 1,
Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, WWW '10 page 661-670. Association for Computing Machinery, 2010. 1,
Wenjie Li, Adarsh Barik, and Jean Honorio. A simple unified framework for high dimensional bandit problems. In International Conference on Machine Learning, pages 12619 12655.. PMLR, 2022. 3,3
Léo Miolane and Andrea Montanari. The distribution of the lasso: Uniform control over sparse balls and adaptive parameter tuning. The Annals of Statistics, 49(4):2313-23) 2021.

---

Shogo Nakakita and Masaaki Imaizumi. Benign overfitting in time series linear model with over- parameterization. arXiv preprint arXiv:2204.08369, 2022.
Min-hwan Oh, Garud Iyengar, and Assaf Zeevi. Sparsity-agnostic lasso bandit. In International Conference on Machine Learning, pages 8271 8271-8280. PMLR, 2021.
Steffen Rendle. Factorization machines. In Geoffrey I. Webb, Bing Liu, Chengqi Zhang, Dimitrios Gunopulos, and Xindong Wu, editors, JCDM 2010, The 10th IEEE International Conference on Data Mining, Sydney, Australia, 14-17 December 2010, pages 995-1000. IEEE Computer Society, 2010. 2
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Sociery, 58(5):527 535, 1952.
Liang Tang, Rómer Rosales, Ajit Singh, and Deepak Agarwal. Automatic ad format selection via contextual bandits. In 22nd ACM International Conference on Information and Knowledge Management, CIKM' 13, pages 1587-1594. ACM, 2013. 1
Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. arXiv preprint arXiv:2009.14288 2020. 3, 4, 6, 13, 14
Sara A Van De Geer and Peter Bühlmann. On the conditions used to prove oracle results for the lasso. Electronic Journal of Statistics, 3:1360-1392, 2009. 2
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Xue Wang, Mingcheng Wei, and Tao Yao. Minimax concave penalized multi-armed bandit model with high-dimensional covariates. In International Conference on Machine Learning, pages 5200-5208. PMLR, 2018.
Yuyan Wang. Long Tao, and Xian Xing Zhang. Recommending for a multi-sided marketplace with heterogeneous contents. In Proceedings of the 16th ACM Conference on Recommender Systems, RecSys '22, page 456-459. 459. Association for Computing Machinery, 2022. 1,2
12


Reviews:
[{"review_id": "mfMKyVCfEc", "reviewer": "Reviewer_h4Ff", "summary": "This paper analyzes the Explore-then-commit algorithm for the linear contextual bandit problem in high dimensions, when the number of features is higher than the number of rounds T. The authors use recent studies on overparametrized models for linear regression to analyze the algorithm. Since this algorithm requires the knowledge of the underlying covariance matrices of the contexts, the authors provide an alternate algorithm where they adaptively determine the extent of exploration required. ", "questions": "1. Could the authors define the conditional number of a matrix? If they are referring to the standard condition number, how can this number be negative? \n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents a thorough analysis of the high-dimensional linear contextual bandit problem by providing upper and matching lower bounds on the estimation error. The Adaptive algorithm presented in the paper further adds to the paper's strengths and provides a practical way to solve the problem. The simulations provided demonstrate the the adaptive algorithm works practically in both the benign and non-benign cases.\n\n", "weaknesses": "The authors could improve the writing of the paper in the following ways:\n1. The introduction of the term benign covariance is a bit abrupt and very technical very quickly. The authors could provide more intuition about what it means before defining the bias and variance terms. \n\n2. The effective rank definitions used in this paper vary slightly from the standard definitions in literature. The authors could maybe visualize the spectra of a matrix and illustrate what these quantities correspond to. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful review. We would improve the introduction of benign overfitting theory as suggested. \n\n> The introduction of the term benign covariance is a bit abrupt and very technical very quickly. The authors could provide more intuition about what it means before defining the bias and variance terms. \n> The effective rank definitions used in this paper vary slightly from the standard definitions in literature.\n\nThis terminology derives from the theory of benign overfitting (Bartlett et al 2020, Tsigler and Bartlett, 2020). We will add a more detailed discussion of these terminologies. Please see the global reply for its outline. Effective rank characterizes the complexity of the problem where the spectrum is considered. Eigenvalues that are close to zero make little contribution to the effective rank. Coherent rank splits eigenvalues into major and minor ones. Bias corresponds to loss due to the minor eigenvalues that are unlearnable but acceptable. Variance corresponds to the loss from the major eigenvalues that are learnable.\n\n\n> The authors could maybe visualize the spectra of a matrix and illustrate what these quantities correspond to.\n\nExample 1 states that the spectrum decays slightly faster than $k^{-1}$. Example 2 states that spectrum decays slower than $k^{-1}$ but $p$ is finite. The simulation also involves exponential decay. We will add a visualized spectrum of these settings in the camera-ready version. Please see the pdf for figures in the global reply.\n\nNote also that, in the context of benign overfitting, our main innovations in view of the overparameterized theory are as follows: \nUnlike (Bartlett et al 2020, Tsigler and Bartlett, 2020), we consider the case the number of data points used in training ($N$ in our paper) is smaller than full data of size $T$. We introduce the method for estimating the optimal rate. The utility of this result is not limited to bandit setting but can benefit the overparameterization theory.\n\n\n> Could the authors define the conditional number of a matrix? If they are referring to the standard condition number, how can this number be negative?\n\nWe define the conditional number as the ratio between the largest and the smallest singular values, which is non-negative but can be zero. Theorem 2 excludes some corner cases where the conditional number is zero with non-negligible probability. \n\n[references]\n* Bartlett et al. (2020). Benign overfitting in linear regression. PNAS.\n* Tsigler and  Bartlett (2023). Benign overfitting in ridge regression. JMLR.\n"}, {"review_id": "Q3atze1jvz", "reviewer": "Reviewer_pLAf", "summary": "This paper addresses the linear contextual bandit problem in high dimensions where the number of features is greater than the budget.  While the recent works impose an assumption about sparsity on the regression coefficients, this paper uses the minimum-norm interpolating estimator which is inspired by recent results on overparameterized models when data distributions have small effective ranks. The authors propose an explore-then-commit algorithm and derive an optimal regret for the proposed algorithm under their setting. This algorithm requires model-dependent parameters on the covariance, which can limit the applications in practice. Therefore, they further propose\nan adaptive explore-then-commit algorithm by estimating these parameters and show that their adaptive version also achieves the optimal rate. Finally,  they provide some simulations to verify the efficiency of the proposed method.", "questions": "- In Theorem 4, they impose Assumptions 1 and 2. Thus, where is the assumption about the benign covariance?\n- Also see my questions in the Weaknesses section", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Unlike previous works, the paper solves the high-dimensional linear contextual bandit problem without sparsity. This seems to be the first work in the field of high-dimensional contextual bandits. This paper also proposes new algorithms in the form of the Explore-then-Commit strategy in their setting and derives the optimal regrets for proposed algorithms.\n\n- The organization and the presentation are almost clear to follow. \n\n", "weaknesses": "- Although the paper introduces a new direction for the high-dimensional linear contextual bandits, the authors seem not to analyze deeply the difference between their work and the recent works using sparsity (e.g., Kim and Paik, 2019, Bastani and Bayati, 2020, Hao et al., 2022). Without sparsity, their work needs to impose a condition to be benign on the covariance matrix as well as Assumption 2 in the paper. I am wondering if this assumption is weaker than the assumption on the sparsity of the recent works. Thus, I think that a section of the related works and a comparison of assumptions with recent works are needed. \n- The regret bounds in Theorem 4 and Theorem 9 are in terms of $\\alpha$. However, the definition of $\\alpha$ is not clear at all. For examples 1 and 2 in the paper, $\\alpha$ can be understood but in general, what is $\\alpha$?\n-  Although the regret bounds are provided for the proposed algorithms, I think that a comparison of regret bounds with the recent works (e.g., Hao et al., 2022) is also needed. \n-  The used techniques are adapted from the recent work of Bartlett et al., 2020. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful review. These questions are fundamental to the benign assumption, and we will revise the paper based on your comments. Below, we answer the questions raised.\n\n> Although the paper introduces a new direction for the high-dimensional linear contextual bandits, the authors seem not to analyze deeply the difference between their work and the recent works using sparsity (e.g., Kim and Paik, 2019, Bastani and Bayati, 2020, Hao et al., 2022). Without sparsity, their work needs to impose a condition to be benign on the covariance matrix as well as Assumption 2 in the paper. I am wondering if this assumption is weaker than the assumption on the sparsity of the recent works. Thus, I think that a section of the related works and a comparison of assumptions with recent works are needed.\n\nSparse and benign overfitting are orthogonal. Many examples are benign but non-sparse and vice versa. The main motivation behing benign overfitting theory is to explain the learnability of recent large-scale models. To put it differently, we consider different classes of problems where we can guarantee sublinear regret bound irrespective of sparseness assumption.\n\n> The regret bounds in Theorem 4 and Theorem 9 are in terms of $\\alpha$. However, the definition of $\\alpha$ is not clear at all. For examples 1 and 2 in the paper, can be understood but in general, what is $\\alpha$?\n\n$T^{\\alpha}$ is such that $N = T E(N, T)$ (Eq.(7) with $K=O(1)$), and its closed formula is derived in Examples 1 and 2. The $\\alpha$ in Theorem 4 and 9 is identical. We thank the reviewer for pointing out this and will revise the paper to clarify this.\n\n> Although the regret bounds are provided for the proposed algorithms, I think that a comparison of regret bounds with the recent works (e.g., Hao et al., 2022) is also needed.\nThe used techniques are adapted from the recent work of Bartlett et al., 2020.\n\nThe complexity of a sparse bandit algorithm is characterized by a number of non-zero features $s$. In our case, $s$ corresponds to $p$ (i.e., all dimensions are non-zero), and for any $p \\ge T$, all sparse bandit regret bounds are meaningless $\\Omega(T)$ bounds (c.f., Li et al. Table 1, Jang et al. Table 1) unlike our algorithms that have sublinear regret for $p \\ge T$. We will add this discussion in the revised version.\n\n> In Theorem 4, they impose Assumptions 1 and 2. Thus, where is the assumption about the benign covariance?\n\nThank you for the important clarification question. Definition 1 is the heart of the benign property. \nFollowing (Bartlett et al 2020, Tsigler and Bartlett, 2020), Assumption 1 is used to derive our bound, but this assumption is not necessary for the benign property (i.e., there are benign examples without Assumption 1).\n\nThank you for many other suggestions. We will update the paper accordingly.\n"}, {"review_id": "TjHMKkNf1t", "reviewer": "Reviewer_dtiS", "summary": "The authors studied the high-dimensional linear contextual bandit problem where the number of features 𝑝 is greater than the budget 𝑇, or it may even be infinite. \n\nProblem setting: They assumed each arm has an individual hidden parameter, and the contexts are drawn from nature for each round. \n\nThey argue that only by using the notion of effective dimension, in some cases when data distributions have a small effective rank, explore-then-commit algorithm can address this problem.", "questions": "0) In line 117, you mentioned that $\\hat{\\theta}$ can be achieved by simple OLS (ordinary least square) operation. However, you mentioned that $p>n$. How can you define $(XX^\\top)^{-1}$ in this case? The authors also mentioned that their analysis can be executable even when $p=\\infty$ (the first sentence of the abstract.) Please help me to understand this. \n\n\n1) The authors use the word 'optimal balance' when they describe AEtC. Here's the sentence:\n\n> Moreover, we introduce an adaptive explore-then-commit (AEtC) algorithm that adaptively finds the optimal balance. \n\nI want to ask what the word 'optimal' means. I cannot see any lower-bound proof of the exploration in this paper. Did you prove that none of the EtC algorithms can beat the AEtC algorithm? If not, I believe that one should be careful of using the word 'optimal.'\n\n\n2) According to my understanding, AEtC is an algorithm that relieves the assumption on the knowledge of $\\Sigma^{(i)}$ (and naturally Assumption 2) from EtC, not the algorithm that improves the order of regret, am I right?\n\n\n3) I want to know whether you 'assumed' the covariance matrix to be benign, or Assumption 1 (or 2) implies the covariance matrix to be benign. \n\n\n4) In your proposition 1, I want to check that your $\\lambda_k^{(i)}$ is exactly $k^{-1 + 1/T^a}$ or $k^b$, not the orderwise notation, am I right?\n\n\n5) Maybe a silly question, but suppose that we regard your problem as a K-armed bandit problem, without considering the context. Then, isn't this mean that we already have a regret bound of $O(\\sqrt{KT})$? Even for EtC, we have $O(T^{2/3})$ regret bound for K-armed bandit with EtC. What is the main factor that separates your problem from the naive K-armed bandit problem?", "limitations": "There's no negative societal impact of their work. \nI also think they didn't state their limitations or future works properly.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "They adopted the new techniques from [Bartlett et al., 2020] to design an explore-then-commit algorithm with this 'tough' environment - where the dimension $p$ is large compared to the number of samples. Seems like this observation is original.\n\nPlus, they proved that their regret bound is tight by proving several lower bounds. If their arguments are all correct, these results can be significant.", "weaknesses": "I am unsure whether this paper is clear enough.\n\n1) It's not straightforward whether they assumed 'benign covariance matrix' in proposition 1 or their assumption 1 implies benign covariance matrix.\n\n2) I cannot understand how one can take an inverse matrix in line 117 when $p>n$.\n\n3) Eventually, seems like they made only two major assumptions - Assumption 1 with sub-gaussianity, and Assumption 2 which is about the error rate of the OLS. Especially, for AEtC, they only used Assumption 1. I am strongly doubtful that they achieve a meaningful regret bound without any additional assumption on high-dimensional space - As in the first paragraph of Chapter 7, 'High-dimensional statistics' by Martin Wainwright, if the model lacks any additional structure, then there is no hope of getting a consistent estimator in the high-dimensional environment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank your careful reading and insightful comments. The score is a bit low compared with the tone of the review. The main questions raised by the reviewers are about the problem setting. To address this, we will revise the paper as outlined in the global reply. Below, we answer each of the questions.\n\n> It's not straightforward whether they assumed 'benign covariance matrix' in proposition 1 or their assumption 1 implies benign covariance matrix.\n\nAssumption 1 shows that the elements of this random matrix are independent sub-Gaussian (light tail probability). It is possible to have benign covariance (Definition 1) but not satisfy Assumption 1, and it is possible to satisfy Assumption 1 but not have benign covariance. I will add an explanation for this.\n\n> I cannot understand how one can take an inverse matrix in line 117 when $p > n$.\n> In line 117, you mentioned that can be achieved by simple OLS (ordinary least square) operation. However, you mentioned that. How can you define in this case? \n\nWe consider situations where $p>n$.\nOur estimator takes the inverse of the matrix $X X^T$, so we have $n \\times n$ matrices with rank $n$, and the estimator $X^T (X X^T)^{-1} Y$ (e.g., line 117) does not cause a problem.\nNote that this estimator can be rewritten as $ (X^T X)^{-1} X^T Y$, in which case it takes the inverse of $X^T X$. Since this matrix is $p \\times p$ and the rank is $n$, we cannot take the inverse matrix, but we can take the generalized inverse matrix.\n\n\n\n> Eventually, seems like they made only two major assumptions - Assumption 1 with sub-gaussianity, and Assumption 2 which is about the error rate of the OLS. Especially, for AEtC, they only used Assumption 1. I am strongly doubtful that they achieve a meaningful regret bound without any additional assumption on high-dimensional space.\n\nWe make specific assumptions on the eigenvalue structure of the covariance matrix $\\Sigma$. Namely, the assumption of benign covariance as given in Definition 1. Under this assumption, the benign overfitting theory proves that we can achieve a consistent estimator in high dimensions (Bartlett et al. (2020)). \n\n> Meaning of “optimal” here. “Moreover, we introduce an adaptive explore-then-commit (AEtC) algorithm that adaptively finds the optimal balance.”\n> According to my understanding, AEtC is an algorithm that relieves the assumption on the knowledge of  (and naturally Assumption 2) from EtC, not the algorithm that improves the order of regret, am I right?\n\nThe optimality here is on the choice of $T_0$. To optimize it, EtC needs to know the spectrum ${\\lambda_k}$, and AEtC adaptively estimates it. Thank you for the clarification. \n\n> I want to know whether you 'assumed' the covariance matrix to be benign, or Assumption 1 (or 2) implies the covariance matrix to be benign.\n\nAssumption 2 given in EtC's theorem (assumed to be of error order) is necessary for the covariance matrix to be benign (Definition 1). \n\nTheorem 9 for AEtC more directly assumes the eigenvalue structure of the covariance matrix (see the sentence “Suppose DGP of Example 1 or Example 2 in Proposition 1.” in the statement). This makes the covariance matrix benign, allowing the matching estimator to be constructed naturally.\n\n\n> In your proposition 1, I want to check that your $\\lambda_k^{(i)}$ is exactly $k^{-1+1/T^a}$ or $k^b$, not the orderwise notation, am I right?\n\nIt is exactly $k^{-1+1/T^a}$ or $k^b$, but multiplying a constant $C$ to all eigenvalues is easy.\n\n> Maybe a silly question, but suppose that we regard your problem as a K-armed bandit problem, without considering the context. Then, isn't this mean that we already have a regret bound of $O(\\sqrt{KT})$? Even for EtC, we have regret bound $O(T^{2/3})$ for K-armed bandit with EtC. \n\nAs you mentioned, our problem is contextual (that means, to have sublinear regret, we must choose the best arm $i^*(t)$ for each round $t$ (Eq. (2)). Therefore the regret here is much more challenging than the regret of context-free K-armed bandit problem (where the best arm is consistent) and results on context-free K-armed bandit problem do not apply. \n\n[references]\n* Bartlett et al. (2020). Benign overfitting in linear regression. PNAS.\n* Tsigler and  Bartlett (2023). Benign overfitting in ridge regression. JMLR.\n"}, {"review_id": "MnTETSTzV3", "reviewer": "Reviewer_C3HD", "summary": "This paper considers a high-dimensional contextual linear bandit setting and uses recent results on \nthe risk of minumum\nnorm linear interpolators to evaluate the regret of two variants of an explore-then-commit algorithm. \nThe first variant makes use of the risk results to balance regret in the \"explore\" vs \"commit\"\nphases, assuming oracle knowledge of the population covariance of the contexts (which \ndetermine the risk, hence regret, of the linear interpolator and derived arms). The second variant\nuses simple sample-covariance-based estimators that do not require such oracle knowledge to inform\nthe stopping of the explore phase, making the algorithm adaptive to the instance. ", "questions": "1. Can you relate/situate this work with e.g. the paper \"Model selection for Contextual Bandits\" by Foster et al. and the references therein? \nThe settings are similar, but different in crucial ways (e.g. in their work context covariances are assumed bounded below).\n2. Can you elaborate on the regret dependence in terms of $\\theta_\\max$? Presumably knowledge of this affects the optimal choice of $T_0$?\n3. Can the class of covariance structures considered \"benign\" be expanded if one does not use interpolating estimators?\n4. Can the example of Theorem 5 provide a \"hard\" example for more than explore-then-commit algorithms?", "limitations": "See above", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper's ideas are straightforward, and relatively easy to understand once one is familiar\nwith the work analyzing the risk of interpolating linear estimators. The paper also lays\nout the results and proof ideas well. The algorithms are\nalso easy to motivate from that context, and amenable to quick implementation. The setting\nof high-dimensional linear contextual bandits without sparsity is also interesting, pointing towards potentially\ninfinite-dimensional contexts.", "weaknesses": "In my view, the papers main limitations are related to its reliance on\nthe interpolating estimator work:\n1. It is unclear to me why the paper is focused on covariance structures of the type\nin Proposition 1. Presumably this is because these are the covariances for which the \nminimum norm interpolators have non-trivial risk guarantees, but that seems like\na weak reason to focus solely on them; e.g. one could consider ridge estimators, lasso\nestimators (notwithstanding the lack of sparsity, given it can still have good prediction error), etc.\n2. The authors provide a lower bound for explore then commit algorithms showing that \ntheir upper bound is tight, restricted to this class of algorithms. However, it is not obvious\nthat ucb or thompson sampling algorithms would face the same obstacle in performance. An information-theoretic\nlower bound would be convincing on this score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and many comments. \n\n> It is unclear to me why the paper is focused on covariance structures of the type in Proposition 1. Presumably this is because these are the covariances for which the minimum norm interpolators have non-trivial risk guarantees, but that seems like a weak reason to focus solely on them; e.g. one could consider ridge estimators, lasso estimators (notwithstanding the lack of sparsity, given it can still have good prediction error), etc.\n\nYour point is spot-on. We are interested in this covariance structure because we can show that the ridge-less least-square estimator can yield a consistent estimator under this covariance structure. Regarding the ridge and lasso estimators, under the same covariance, non-sparse high-dimension settings these estimators are inconsistent (e.g., Tsigler & Bartlett (2020), Dobrian & Wagner (2019)). Hence, the ridge/lasso estimator is not suitable in this setting.\n\n> The authors provide a lower bound for explore then commit algorithms showing that their upper bound is tight, restricted to this class of algorithms. However, it is not obvious that ucb or thompson sampling algorithms would face the same obstacle in performance. An information-theoretic lower bound would be convincing on this score.\n\nYou are right, our lower bound is for the class of explore-then-commit algorithms.\n\n> Can you relate/situate this work with e.g. the paper \"Model selection for Contextual Bandits\" by Foster et al. and the references therein? The settings are similar, but different in crucial ways (e.g. in their work context covariances are assumed bounded below).\n\nFoster et al. considered a linear bandit problem where the hypothesis space is nested with dimensions $d_1 < d_2 < d_3 < \\dots < d_M$. Our AEtC and Foster et al. are in common in the sense that they both find the best sample complexity in linear contextual bandit problem. However, their sample complexity is determined to deal with finite dimension problem with $d_m$ (after a known map $\\phi(x, a)$), whereas we consider $p$ non-zero dimensions with $p \\ge T$ or even infinite without any such a map.  We will revise the paper to add this.\n\n> Can you elaborate on the regret dependence in terms of $\\theta_{\\mathrm{max}}$? Presumably knowledge of this affects the optimal choice of  $T_0$?\n\nThank you for your question. Regret depends on linearly on $\\theta_{\\mathrm{max}}$, which we assumed to be a constant. If we consider this to be a variable, it matters to the choice of $T_0$.\n\n> Can the class of covariance structures considered \"benign\" be expanded if one does not use interpolating estimators?\n\nWe can consider Ridge and Lasso regressors, but these regressors do not have consistency in our setting (Tsigler & Bartlett (2020), Dobrian & Wagner (2019)). Therefore, the choice of OLS is indispensable.\n\n> Can the example of Theorem 5 provide a \"hard\" example for more than explore-then-commit algorithms?\n\nFor UCB or more adaptive algorithms where the sample depends on the history, existing results on benign overfitting do not apply because these theories are on a fixed number of samples (i.e., $N_i(t)$ cannot change adaptively). \n\n[references]\n*  Tsigler and  Bartlett (2023). Benign overfitting in ridge regression. JMLR.\n*  Dobriban, E., & Wager, S. (2018). High-dimensional asymptotics of prediction: Ridge regression and classification. AoS.\n"}, {"review_id": "aNGGXIDGDt", "reviewer": "Reviewer_57ot", "summary": "The paper addresses the problem of high-dimensional linear contextual bandits where the number of features is greater than the budget or even infinite. Unlike previous works, the paper does not impose sparsity on the regression coefficients but instead leverages over parameterized models. The authors propose an explore-then-commit (EtC) algorithm and an adaptive explore-then-commit (AEtC) algorithm to tackle this problem. The performance of the proposed algorithms is evaluated through simulations, and the optimal rate of the ETC algorithm is derived, showing that it can be achieved by balancing exploration and exploitation.", "questions": "Besides the questions in the above Weakness section, I have some questions here:\n\n1. For your experiments, in several cases (DGP 1, DGP 2) it seems that the cumulative regret of your algorithm and other existing algorithms is linearly increasing according to the plots. Could authors explain why sublinear pattern is not observed?\n\n2. Can your algorithm still work well when $p$ is greater than $T$ in practice? It might be more comprehensive if such case could be considered in your simulation studies.", "limitations": "No negative societal impact.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper studies a new problem in high-dimensional bandits when there is no sparsity in parameter vector. EtC is first proposed based on the minimum-norm interpolating estimator with the optimal exploration rate, and then AEtC is introduced to deal with the model-dependent parameters on the covariance.", "weaknesses": "1. Lower bound of the problem is not discussed in the paper. Since this is the first work on the high-dimensional bandit without sparsity, a lower bound can help people understand how good your algorithm is in theory. I acknowledge that authors mention this point as limitation in the appendix, but I believe this is an important issue.\n\n2. Assumptions are strong and more explanations will be better. Some assumptions are given in the paper, e.g. Assumption 1, which may not be realistic in practice. For example, I can hardly understand the first part of Assumption 1. What is the intuition behind it? Why you used spectral decomposition to construct $X^{(i)}(t)$? Some examples on which these assumptions hold should be given.\n\n3. More explanation on definitions should be presented. Authors use some definitions in this work that are not commonly used in the bandit community, e.g. effective bias, effective variance, coherent rank, effective rank, benign covariance. Some more explanations on these definitions and maybe correlation between them should be given in the paper.\n\n4. The regret bound in Theorem 4 depends on some $\\alpha > 0$, but this value is not clearly explained in Theorem 4. I think when authors write a formal Theorem in the paper, it is better to explain every term in detail (e.g. how to formulate $\\alpha$ in general).\n\n5. (minor): in the first page, the footnote 1 is under the sentence \"submitted to 37th Conference on .......\", which seems unusual. Maybe the authors change the margin of the template a little bit?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank your careful reading and insightful comments. The score is a bit low even though no critical issue was raised. If the main concerns are the unclarity of the problem setting, we would be happy to address any concerns. Regarding the clarification on the benign covariance, we will revise the paper in accordance with the global reply above. Below, we answer each of the questions.\n\n> Lower bound of the problem is not discussed in the paper. \n\nThank you for your clarification. We derived the lower bound on the class of EtC algorithms that matches our regret upper bound. You are right that this does not exclude the possibility of non-EtC algorithms that has a lower regret. We would also like to mention that the sparse linear bandit problem was introduced without a nontrivial lower bound (Abbasi-Yadkori et al. 2012). Given that we introduced a new problem, non-adaptive (EtC) and adaptive (AEtC) algorithms as well as experimental results, we consider the contributions of this paper are more than what is expected.\n\nYasin Abbasi-Yadkori, David Pal, Csaba Szepesvari. “Online-to-Confidence-Set Conversions and Application to Sparse Stochastic Bandits.” (Sparse linear bandits)\n\n> Assumptions are strong, and more explanations will be better. Some assumptions are given in the paper, e.g. Assumption 1, which may not be realistic in practice. For example, I can hardly understand the first part of Assumption 1. What is the intuition behind it? \n\nThe combination of Assumption 1 and Definition 1 is from the theory of benign overfitting (Bartlett et al 2020, Tsigler and Bartlett, 2020). We clarify that the first assumption implies that each feature is an independent sub-Gaussian after diagonalization. Covariance matrices in Examples 1 and 2 satisfy these assumptions. The second assumption implies that the rewards are noisy with subGaussian noise. Note that sub-Gaussian noises are standard in this assumption. Thank you for your clarification questions. We will revise the paper accordingly.\n\n> More explanation on definitions should be presented. Authors use some definitions in this work that are not commonly used in the bandit community, e.g. effective bias, effective variance, coherent rank, effective rank, benign covariance. Some more explanations on these definitions and maybe correlation between them should be given in the paper.\n\nThank you for your suggestions. Since we introduce the new problem into the bandit community, we will add a more detailed discussion on these terminologies as outline in the global reply above. Effective rank characterizes the complexity of the problem where the spectrum is taken into consideration. Eigenvalues that are close to zero do little contribution to the effective rank. Coherent rank splits eigenvalues into major and minor ones. Bias corresponds to loss due to the minor eigenvalues that are unlearnable but acceptable. Variance corresponds to the loss from the major eigenvalues that are learnable. \n\n> The regret bound in Theorem 4 depends on some, but this value is not clearly explained in Theorem 4\n\n$T^{\\alpha}$ is such that $N = T E(N, T)$ (Eq.(7) with $K=O(1)$), and its closed formula, which depends on the covariance spectrum, is derived in Examples 1 and 2. The value $\\alpha$ in Thm 4 and 9 is identical. We will revise the paper to clarify this.\n\n> For your experiments, in several cases (DGP 1, DGP 2) it seems that the cumulative regret of your algorithm and other existing algorithms is linearly increasing according to the plots. Could authors explain why sublinear pattern is not observed?\n\nEtC has two phases (exploration and commitment), and it has a linear growth of regret for each of the phases for a fixed $T$. Sublinear regret (Theorem 9) implies that, if we run the EtC for each of $T=1,2,4,8,\\dots$, $R(T)$ (regret at the final round) grows sublinear to $T$. \n\n> Can your algorithm still work well when is greater than in practice?\n\nWe can deal with $p > T$ or even infinite $p= \\infty$ as long as our assumptions hold. Example 1 is such a case.\n\nWe appreciate many other suggestions. "}]

Author rebuttal:
Thank you all for your thoughtful and important comments. 
We are making the following major changes based on your comments.

> Add more introduction to benign covariance and related notion

To enhance our readers' comprehension of overparameterized models, we propose to provide a more comprehensive introduction to this topic. In particular, we feel it would be beneficial to emphasize that many of our underpinning assumptions align seamlessly with the established norms in the field (Bartlett et al. (2020) and Tsigler and Bartlett (2020)).

When the eigenvalues decay at a certain rate, the error convergences to zero even in high or infinite dimensions. An effective rank is introduced to more rigorously capture the decay of eigenvalues. This notion has been used in a random analysis for matrices (e.g. Koltchinskii et al. (2017)). We will add new figures to describe how the eigenvalue decay affects the effective rank.

We append a plot of effective rank $r_k(\Sigma), R_k(\Sigma)$ up to dimension $k$, in order to give intuitions on the effective rank. Even though we consider full-rank covariance matrices, effective ranks can be sublinear to the number of dimensions. 

> Clarify our innovation in the theory of benign covariance

Based on the overparameterized theory, our main innovations in the context of the overparameterized theory are as follows:
* Unlike the standard overparameterized theory (Bartlett et al 2020, Tsigler and Bartlett, 2020), we consider the case the number of data points used in the training ($N$ in our paper) is smaller than full data of size $T$.
* We introduce the method for estimating the optimal rate. The utility of this result is not limited to bandit setting but can benefit the overparameterization theory.

> Add discussion on comparison with bandit with sparse context

The complexity of a sparse bandit algorithm is characterized by the number of non-zero features $s$. In our case, $s$ corresponds to $p$ (i.e., all dimensions are non-zero), and for any $p \ge T$ all sparse bandit regret bounds are meaningless $\Omega(T)$ bounds (c.f., Li et al. Table 1, Jang et al. Table 1) unlike our algorithms that have sublinear regret for $p \ge T$. We will add this discussion in the camera ready.

[references]
* Bartlett et al. (2020). Benign overfitting in linear regression. PNAS.
*  Tsigler and  Bartlett (2023). Benign overfitting in ridge regression. JMLR.
* Jang et al. (2022) PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits, NeurIPS.
* Li et al. (2022) A simple unified framework for high dimensional bandit problems, ICML.
* Koltchinskii & Lounici,  (2017). Concentration inequalities and moment bounds for sample covariance operators. Bernoulli.


Meta-review: The reviewers all agree that this paper studies overparameterized models for linear regression for bandits, introducing this new problem setup to the bandit community. 

The reviewers requested that the authors add more explanations in the final version, as the original submission is technically too fast for most readers and the use of tools are not commonly known to the bandit community.
Decision: Accept (poster)