# highdimensional_contextual_bandit_problem_without_sparsity__560510c8.pdf

High-dimensional Contextual Bandit Problem without Sparsity

Junpei Komiyama New York University junpei@komiyama.info

Masaaki Imaizumi The University of Tokyo / RIKEN Center for AIP imaizumi@g.ecc.u-tokyo.ac.jp

In this research, we investigate the high-dimensional linear contextual bandit problem where the number of features 𝑝is greater than the budget 𝑇, 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 (Et C) algorithm to address this problem and examine its performance. Through our analysis, we derive the optimal rate of the ETC algorithm in terms of 𝑇and show that this rate can be achieved by balancing exploration and exploitation. Moreover, we introduce an adaptive explore-then-commit (AEt C) algorithm that adaptively finds the optimal balance. We assess the performance of the proposed algorithms through a series of simulations.

1 Introduction

The multi-armed bandit problem [Robbins, 1952, Lai and Robbins, 1985] has been widely studied in the field of sequential decision-making problems in uncertain environments, and it can be applied to a variety of real-world scenarios. This problem involves an agent selecting one of 𝐾arms in each round and receiving a corresponding reward. The agent aims to 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 as a function of the contexts. This extension enables us to model many personalized machine learning scenarios, such as recommendation systems [Li et al., 2010, Wang et 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 et al., 2010, Chu et al., 2011, Abbasi-Yadkori et al., 2011]. When 𝑝= 𝑜(

𝑇) to the number of rounds 𝑇, the model is identifiable, and the agent can choose the best arm for most rounds. However, recent machine learning models desire to utilize an 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 et al., 2021, Li et al., 2022, Jang et al., 2022]. Sparse linear bandit models accept a very large number of features1 and suppress most of the coefficients by introducing the ℓ1 regularize.

1Typically, the number of feature 𝑝can be exponential to the number of datapoints 𝑇.

37th Conference on Neural Information Processing Systems (Neur IPS 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 a 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 is that it requires the condition number to be close to one (e.g., the restricted isometry property, see Van De Geer and B uhlmann [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 a proper value of the penalty coefficient as a hyper-parameter. For example, Hara and Maehara [2017] claims 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.

In this paper, We consider an alternative high-dimensional linear bandit problem without sparsity. We allow 𝑝to be as large as desired, and in fact, we even allow 𝑝to be infinitely large. Such an overparameterized model has more parameters than the number of training data points. A natural estimator in such a 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 a concentration inequality on the squared error of the estimator.

The contributions of this paper are as follows: First, We consider explore-then-commit (Et C) strategy for the stochastic bandit problem based on the minimum-norm interpolating estimator. We derive the optimal rate of exploration that minimizes regret. However, Et C requires model-dependent parameters on the covariance, which limits the practical utility. To address this limitation, we propose an adaptive explore-then-commit (AEt C) 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, [𝑧] := {1, 2, . . . , 𝑧}. For 𝑥 R, the notation 𝑥 here denotes the largest integer that is less than or equal to a scalar 𝑥. For vectors 𝑋, 𝑋 R𝑝, 𝑋, 𝑋 := 𝑋 𝑋 is an inner product, 𝑋 2 2 := 𝑋, 𝑋 is an ℓ2-norm. For a positive-definite matrix 𝐴 R𝑝 R𝑝, 𝑋 2 A := 𝑋, A𝑋 is a weighted ℓ2-norm. A op denotes an operator norm of A. 𝑂( ), 𝑜( ), Ω( ), 𝜔( ) and Θ( ) denotes Landau s Big-O, little-o, Big-Omega, little-omega, and Big-Theta notations, respectively. e 𝑂( ), eΩ( ), and eΘ( ) are 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 as the rewards, are drawn from fixed distributions. For each round 𝑡 [𝑇] and arm 𝑖 [𝐾], we define 𝑋(𝑖) (𝑡) as a 𝑝-dimensional zero-mean sub-Gaussian vector. We assume 𝑋(𝑖) (𝑡) is independent among rounds (i.e., vectors in two different rounds 𝑡, 𝑡 are independent) but allow vectors 𝑋(1) (𝑡), 𝑋(2) (𝑡), . . . , 𝑋(𝐾) (𝑡) to be correlated with each other. The forecaster chooses an arm 𝐼(𝑡) [𝐾] based on the 𝑋(𝑖) (𝑡) values of all the arms, and then observes a reward that follows a linear model as shown in

𝑌(𝐼(𝑡)) (𝑡) = 𝑋(𝐼(𝑡)) (𝑡), 𝜃(𝐼(𝑡)) + 𝜉(𝑡). (1)

The unknown true parameters 𝜃(𝑖) for each arm 𝑖 [𝐾] lie in a parameter space Θ R𝑝, and the independent noise term 𝜉(𝑡) has zero mean and variance 𝜎2 > 0. We assume that 𝜉(𝑡) is sub-Gaussian, and for the sake of simplicity, we assume that it does not depend on the choice of the arm. However, our results can be extended to the case where 𝜉(𝑡) varies among arms. We assume that each 𝜃(𝑖) are bounded 𝜃(𝑖) 2 𝜃max. For each 𝑖 [𝐾], we define a covariance matrix Σ(𝑖) = E[𝑋(𝑖) (𝑡)𝑋(𝑖) (𝑡) ] R𝑝 𝑝.

We define 𝑖 (𝑡) := argmax𝑖 [𝐾] 𝑋(𝑖) (𝑡), 𝜃(𝑖) as the (ex ante) optimal arm at round 𝑡. 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];

𝑋(𝑖 (𝑡)) (𝑡), 𝜃(𝑖 (𝑡)) 𝑋(𝐼(𝑡)) (𝑡), 𝜃(𝐼(𝑡)) #

where the expectation is taken with respect to the randomness of the contexts and (possibly) on the choice of arm 𝐼(𝑡).

2.3 Theory of Overparametrized Models

The primary focus of this paper is on scenarios where the number of arms 𝐾is moderate, but the number of features 𝑝is greater than the budget 𝑇, 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 at a certain level, the error in linear regression converges to zero, even in high-dimensional spaces. To provide a more rigorous analysis of eigenvalue decay, the concept of effective rank is introduced in Section 2.4.

Remark 1. (Dependence on𝑇) In accordance with Bartlett et al. [2020], we permit the covariance matrix Σ(𝑖) to depend on𝑇. In other words, we consider the sequence of covariances Σ(𝑖) (1), Σ(𝑖) (2), . . . for each 𝑇= 1, 2, . . . . The linear regression is consistent if the effective rank of Σ(𝑖) (𝑇) grows sufficiently slow as a function of 𝑇.

2.4 Effective Ranks of Covariance Matrix

For a covariance matrix Σ(𝑖) for 𝑖 [𝐾] and 𝑘 [𝑝], let 𝜆(𝑖) 𝑘 be its 𝑘-th largest eigenvalue, such that Σ(𝑖) = Í𝑝 𝑘=1 𝜆(𝑖) 𝑘𝑢(𝑖) 𝑘(𝑢(𝑖) 𝑘) with order 𝜆(𝑖) 1 𝜆(𝑖) 2 𝜆(𝑖) 𝑝and eigenvectors 𝑢(𝑖) 𝑘. We define the concept of effective rank as

𝑟𝑘(Σ(𝑖)) :=

Í 𝑗>𝑘𝜆(𝑖) 𝑗

𝜆(𝑖) 𝑘+1 , and 𝑅𝑘(Σ(𝑖)) := (Σ 𝑗>𝑘𝜆(𝑖) 𝑗)2

Σ 𝑗>𝑘(𝜆(𝑖) 𝑗)2 . (3)

The first quantity 𝑟𝑘(Σ(𝑖)) is related to the trace of Σ(𝑖), and the second quantity 𝑅𝑘(Σ(𝑖)) is related to the decay rate of the eigenvalues.

The effective rank is used as a measure of the intrinsic complexity of high-dimensional data, by rigorously capturing a decay rate of eigenvalues. If the covariance matrix Σ(𝑖) is an identity matrix of size 𝑝, then 𝑟0(Σ(𝑖)) and 𝑅0(Σ(𝑖)) are both equal to 𝑝(the rank of Σ(𝑖)). However, we anticipate that these quantities will be less than 𝑝, which enables learning with fewer samples. In Figure 1, we plot of the effective rank in 𝑘with certain cases of eigenvalues {𝜆𝑘}𝑘of Σ. Even though Σ is full-rank, the effective rank 𝑅𝑘(Σ) is sublinear in 𝑘, which reflects the intrinsic low-complexity of data.

Because of this property, the effective ranks are used in modern high-dimensional statistics. Koltchinskii and Lounici [2017] evaluated concentration inequalities for high-dimensional random matrices using the notion. Bartlett et 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-then-Commit (Et C) algorithm is a well-known approach for solving high-dimensional 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 Et C algorithm operates by first conducting 𝑇0 = 𝑁𝐾< 𝑇rounds of exploration, during which it uniformly explores all available arms to construct an estimator b𝜃(𝑖) for each arm 𝑖 [𝐾]. After the exploration phase, the algorithm proceeds with exploitation. Let 𝑁be the number of the draws of arm 𝑖, and X(𝑖) = (𝑋(𝑖) 1 , ..., 𝑋(𝑖) 𝑁) R𝑁 𝑝and Y(𝑖) = (𝑌(𝑖) 1 , ...,𝑌(𝑖) 𝑁) R𝑁

Figure 1: Eigenvalues 𝜆𝑘(left), the effective rank 𝑟𝑘(Σ) (middle), and the effective rank 𝑅𝑘(Σ) (right) with 𝑘= 1, ..., 15 and 𝑇= 3; Case 1: 𝜆𝑘= 𝐶𝑘 1+1/𝑇0.99, and Case 2: 𝜆𝑘= 𝐶(exp( 𝑘) + 𝑇exp( 𝑇)/𝑝). Case 1 considers a decay that is slightly faster than 𝑘 1, whereas Case 2 considers an exponentially fast decay. The slower increase of 𝑟𝑘(Σ) and 𝑅𝑘(Σ) in Case 2 reflects the impact of the eigenvalues faster decay.

be the observed contexts and rewards of arm 𝑖, where (𝑋(𝑖) 𝑛,𝑌(𝑖) 𝑛) is the corresponding values on the 𝑛-th draw of arm 𝑖. Since we choose 𝐼(𝑡) uniformly during the exploration phase, these are independent and identically drawn samples from the corresponding distribution.

For estimating the parameter 𝜃(𝑖), we consider the minimum-norm interpolating estimator that perfectly fits the data, which reveals its advantage in recent results on high-dimensions [Bartlett et al., 2020]. Rigorously, we assume 𝑝> 𝑁and and consider the following definition:

b𝜃(𝑖) := argmin

(𝑌(𝑖) 𝑛,𝑋(𝑖) 𝑛):𝑛 𝑁 (𝑌(𝑖) 𝑛 𝜃, 𝑋(𝑖) 𝑛 )2

This estimator has a simple representation b𝜃(𝑖) = (X(𝑖)) (X(𝑖) (X(𝑖)) ) 1Y(𝑖). The Et C algorithm is presented in Algorithm 1, which utilizes the aforementioned interpolating estimator. In the subsequent sections, we will first discuss the assumptions on the data-generating process, followed by an analysis of the accuracy of the estimator. We then present an upper bounds on the regret of the Et C algorithm.

4 Theory of Explore-then-Commit

This section analyzes the Et C 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 Et C selects the number of samples used to construct an estimator to balance between exploration and exploitation.

4.1 Assumption and Notion

We consider a spectral decomposition Σ(𝑖) = 𝑉(𝑖)Λ(𝑖) (𝑉(𝑖)) with the matrices (operators) 𝑉(𝑖) and Λ(𝑖) for each arm 𝑖 [𝐾], then impose the following assumptions. Assumption 1 (sub-Gaussianity). For all 𝑡 N and 𝑖 [𝐾], the followings hold:

Algorithm 1 Explore-then-Commit (Et C) Require: Exploration duration 𝑇0.

for 𝑡= 1, ..,𝑇0 do

Observe 𝑋(𝑖) (𝑡) for all 𝑖 [𝐾]. Choose 𝐼(𝑡) = 𝑡 𝐾 𝑡/𝐾 . Receive a reward 𝑌(𝐼(𝑡)) (𝑡). end for for 𝑖 [𝐾] do

b𝜃(𝑖) (X(𝑖)) (X(𝑖) (X(𝑖)) ) 1Y(𝑖). end for for 𝑡= 𝑇0 + 1, ...,𝑇do

Observe 𝑋(𝑖) (𝑡) for all 𝑖 [𝐾]. Choose 𝐼(𝑡) = argmax𝑖 [𝐾] 𝑋(𝑖) (𝑡), b𝜃(𝑖) . Receive a reward 𝑌(𝐼(𝑡)) (𝑡). end for

There exists a random vector 𝑍(𝑖) (𝑡) such that 𝑋(𝑖) (𝑡) = 𝑉(𝑖) (Λ(𝑖))1/2𝑍(𝑖) (𝑡) which is independent elements and sub-Gaussian with a parameter 𝜅2 𝑥> 0, that is, for all 𝜆 R𝑝, we have E[exp( 𝜆, 𝑍(𝑖) (𝑡) )] exp(𝜅2 𝑥 𝜆 2 2/2).

Moreover, 𝜉(𝑡) is conditionally sub-Gaussian with a parameter 𝜅2 𝜉> 0, that is, for all 𝜆 R, we have E[exp(𝜆𝜉(𝑡)) | 𝑋(𝑖) (𝑡)] exp(𝜅2 𝜉𝜆2/2).

The first bullet point of Assumption 1 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 1, 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 𝑖 [𝐾]. The condition is 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 𝑇samples, we only use a portion of the data for learning.

We first define the coherent rank of Σ(𝑖) with a number of samples 𝑁as

𝑘 𝑁= 𝑘 𝑁(Σ(𝑖), 𝑁) := min{𝑘 N {0} | 𝑟𝑘(Σ(𝑖)) 𝑁},

where we define min{ } = + . By using the coherent rank, we decompose the error into two quantities called effective bias/variance denoted as 𝐵(𝑖) 𝑁,𝑇and 𝑉(𝑖) 𝑁,𝑇, based on a budget of 𝑇and the number of samples 𝑁used for estimation.

𝐵(𝑖) 𝑁,𝑇:= 𝜆(𝑖) 𝑘 𝑁, and 𝑉(𝑖) 𝑁,𝑇:=

𝑘 𝑁 𝑁+ 𝑁 𝑅𝑘 𝑁(Σ(𝑖))

Definition 1 (Benign covariance). Under Assumption 1, a covariance matrix Σ(𝑖) is benign, if 𝐵(𝑖) 𝑁,𝑇= 𝑜(1) and 𝑉(𝑖) 𝑁,𝑇= 𝑜(1) hold as 𝑁,𝑇 while 𝑁= Θ(𝑇).

To put it differently, Assumption 1 and Definition 1 state that, if we can achieve consistent estimation by using all the data for estimation, then the covariance matrix is considered benign.

Technically, the benign property implies that eigenvalues decay fast enough compared with 𝑇. In particular, the following examples have been considered in the literature. Proposition 1 (Example of Benign Covariance, Theorem 31 in Bartlett et al. [2020]2 ). A covariance matrix Σ(𝑖) with eigenvalues 𝜆(𝑖) 1 , 𝜆(𝑖) 2 , ... is benign if it satisfies one of the following.

2It 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.

Example 1: Let 𝑎 (0, 1), 𝑝= and 𝜆(𝑖) 𝑘 = 𝑘 (1+1/𝑇𝑎). In this case, we have 𝐵(𝑖) 𝑁,𝑇=

𝑂((𝑇𝑎/𝑁)1+1/𝑇𝑎) and 𝑉(𝑖) 𝑁,𝑇= 𝑂(𝑇𝑎/𝑁+ 𝑇 𝑎). For this model to be learnable, 𝑁 𝑇𝑎is required, and the variance dominates the bias.

Example 2: Let 𝜆(𝑖) 𝑘 = 𝑘 𝑏and 𝑝 = 𝑝𝑇 = 𝑂(𝑇𝑐) with 𝑏 (0, 1) and 𝑐 max 1, 2 2 𝑏, 1 1 𝑏2 , 1 1 𝑏 . In this case, we have 𝐵(𝑖) 𝑁,𝑇 = 𝑂(𝑇𝑐(1 𝑏)/𝑁) and 𝑉(𝑖) 𝑁,𝑇 =

𝑂((𝑁/𝑇𝑐)max(1, 1 𝑏

𝑏)). For this model to be learnable, 𝑁 𝑇𝑐(1 𝑏) is required, and the bias dominates the variance.

The first example is when the decay rate is near 𝑘 1, but the trace is 𝑂(𝑇𝑎). The second example is when the decay rate is smaller than 𝑘 1, and the trace is 𝑂(𝑇𝑐(1 𝑏)). 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 b𝜃(𝑖) by its prediction quality. That is, with a covariance matrix Σ(𝑖) and an identical copy 𝑋(𝑖) of 𝑋(𝑖) 1 , we study

𝜃(𝑖) b𝜃(𝑖) 2 Σ(𝑖) = E𝑋(𝑖)

h ( 𝜃(𝑖), 𝑋(𝑖) b𝜃(𝑖), 𝑋(𝑖) )2i ,

The following result bounds the error of the estimator b𝜃(𝑖) in terms of bias and variance, which is a slight extension of Tsigler and Bartlett [2020]. For 𝑘 [𝑝], we define an empirical submatrix as X(𝑖) 𝑘: R𝑁 ( 𝑝 𝑘) as the 𝑝 𝑘columns to the right of X(𝑖), and define a Gram sub-matrix 𝐴(𝑖) 𝑘 = X(𝑖) 𝑘: (X(𝑖) 𝑘: ) R𝑁 𝑁. Theorem 2. Suppose Assumption 1. If there exists 𝑐𝑈> 1 such that 𝑘 𝑁< 𝑁/𝑐𝑈and a condition number of 𝐴(𝑖) 𝑘 is positive with probability at least 1 𝑐𝑈𝑒 𝑁/𝑐𝑈, then we have

b𝜃(𝑖) 𝜃(𝑖) 2 Σ(𝑖) 𝐶𝑈 𝐵(𝑖) 𝑁,𝑇+ 𝑉(𝑖) 𝑁,𝑇 , (5)

with some constant 𝐶𝑈> 0 and probability at least 1 2𝑐𝑈𝑒 𝑁/𝑐𝑈.

Theorem 2 implies that the estimation error converges to zero if Σ(𝑖) has the benign property. The assumption on the condition number of 𝐴(𝑖) 𝑘 has a sufficient condition, which is provided in 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 𝑐𝐿, 𝐶𝐿> 0 such that, with probability at least 1 𝑐𝐿𝑒 𝑁/𝑐𝐿, we have b𝜃(𝑖) 𝜃(𝑖) 2 Σ(𝑖) 𝐶𝐿 𝐵(𝑖) 𝑁,𝑇+ 𝑉(𝑖) 𝑁,𝑇 . (6)

In other words, the upper bound in Theorem 2 is optimal up to a constant.4

4.4 Regret Bound of Explore-then-Commit

This section analyzes the Et C algorithm. We introduce an error function E(𝑁,𝑇) that characterizes the rate of regret, which can be obtained by considering (𝐵(𝑖) 𝑁,𝑇+ 𝑉(𝑖) 𝑁,𝑇)1/2.

Assumption 2. (Error function5) There exists a continuous function E : R2 R+ that is decreasing in 𝑁such that b𝜃(𝑖) 𝜃(𝑖) Σ(𝑖) = eΘ (E(𝑁,𝑇)) as 𝑁,𝑇 .

3One of the omitted examples is the case where eigenvalues decay slightly slower than Example 1. The other example is the case where eigenvalues decay exponentially but has a noise term. 4Note that the constant here can depend on model parameters. 5The coherent rank 𝑘 𝑁as well as 𝐵(𝑖) 𝑁,𝑇,𝑉(𝑖) 𝑁,𝑇are discrete in 𝑁,𝑇, and the error function E(𝑁,𝑇) is introduced to circumvent the issues related to this discreteness.

Assumption 2 is satisfied in Examples 1 and 2. In particular, for Example 1 in Proposition 1, the error function is given as E(𝑁,𝑇) =

𝑇𝑎/𝑁+ 𝑇 𝑎, while for Example 2 in Proposition 1, it is given as E(𝑁,𝑇) =

Theorem 4. Suppose Assumptions 1 2. Suppose that we run the Et C algorithm (Algorithm 1). Then, regret (2) satisfies

𝑅(𝑇) = e 𝑂(𝐿(𝑇, 𝐾)),

as 𝑇 with some 𝛼> 0. where 𝐿(𝑇, 𝐾) is such that

𝑁 = min 𝑁{𝑁: 𝑁 𝑇E(𝑁/𝐾,𝑇)}. (7)

Specifically, for Example 1 in Proposition 1, we have 𝐿(𝑇, 𝐾) = max(𝑇(2+𝑎)/3𝐾2/3,𝑇1 𝑎/2), whereas for Example 2 in Proposition 1, we have 𝐿(𝑇, 𝐾) = 𝑇(2+𝑐(1 𝑏))/3𝐾2/3.

Proof sketch of Theorem 4. We show that the regret-per-round is 𝑂(1) during the exploration phase. Moreover, regret-per-round is e 𝑂(E(𝑇0/𝐾,𝑇)) during the exploitation phase. The total regret is 𝑇0 + e 𝑂(E(𝑇0/𝐾,𝑇))𝑇, and optimizing 𝑇0 by using the decreasing property of E(𝑁,𝑇) in 𝑁yields the desired result.

4.5 Matching Lower Bound

We show that this choice of 𝑇0 as a function of 𝑇is indeed optimal.

Theorem 5. Suppose Assumptions 1 2. Assume that we run the Et C algorithm (Algorithm 1). For any choice of 𝑇0, the following event occurs with strictly positive probability as 𝑇 :

𝑅(𝑇) = eΩ (𝐿(𝑇, 3)) .

Proof sketch of Theorem 5. We explicitly construct a model with 𝐾= 3. Let 𝜖𝑇= E(𝑇0/𝐾,𝑇). In the model, the Σ(1), Σ(2), Σ(3) are identical, and the only difference is that the first coefficients 𝜃(1) 1 = 1, 𝜃(2) 1 = Θ(𝜖𝑇), 𝜃(3) 1 = 0. All other coefficients are set to zero. Roughly speaking, the gap is 𝑋(𝑖) (𝑡), b𝜃(𝑖) 𝑋( 𝑗) (𝑡), b𝜃( 𝑗) = Θ(1) (𝑖= 1, 𝑗= 2, 3) Θ(𝜖𝑇) (𝑖= 2, 𝑗= 3) .

The regret-per-round during the exploration phase is Θ(1) due to a misidentification of the best arm between arm 1 and arms {2, 3}. The regret-per-round during the exploitation phase is Θ(𝜖𝑇) due to a misidentification of the best arm between arm 2 and arm 3.

5 Adaptive Explore-then-Commit (AEt C) Algorithm

In the prior section, we demonstrated that the optimal way to minimize Et C s regret is by selecting 𝑇0, with 𝑇0 balancing the exploration and the exploitation. However, this requires knowledge of the covariance matrix s spectrum, which can be difficult 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 Σ(𝑖) follows the data-generating process of Example 1 or 2 in Proposition 1. We use 𝛽𝑇to denote that 𝜆(𝑖) 𝑗 = 𝐶𝜆𝑗 𝛽𝑇, (8)

with some constant 𝐶𝜆> 0. We have 𝛽𝑇= 1+1/𝑇𝑎for Example 1, and 𝛽𝑇= 𝑏(< 1) for Example 2.

Balancing exploration and exploitation in an overparameterized model is challenging for the following reasons. First, the number of features 𝑝is very large or even infinite6. Second, the trace is heavy-tail

6Namely, 𝑝= for for Proposition 1 (1) or 𝑝= 𝑇𝑐in for Proposition 1 (2).

because the decay is not very fast. As a result, a naive use of a traditional method does not work. We address this issue by utilizing two estimators. The first estimator is on the trace tr(bΣ(𝑖)) that we extracted from overparameterization theory [Bartlett et al., 2020], whereas the second estimator is on the estimated decay rate b𝛽𝑇that derives from Bosq [2000], Koltchinskii and Lounici [2017].

For an arm 𝑖 [𝐾] with 𝑁= 𝑇0/𝐾draws, we define an estimated eigenvalues b𝜆(𝑖) 1 , ..., b𝜆(𝑖) 𝑁> 0 from an empirical covariance matrix bΣ(𝑖) := 𝑁 1 Í𝑁 𝑗=1 𝑋(𝑖) 𝑗(𝑡)𝑋(𝑖) 𝑗(𝑡) . We define the empirical trace to

be tr(bΣ(𝑖)) = Í 𝑗b𝜆(𝑖) 𝑗. The following lemma states the consistency of the estimated trace under very mild conditions. Lemma 6. (Error bound of empirical trace) Suppose Assumption 1. Suppose the data generating process (DGP) of Example 1 or Example 2 in Proposition 1. Then, for any 𝐶poly > 0, with probability at least 1 1/𝑇𝐶poly, we have the following as 𝑇 :

|tr(Σ(𝑖)) tr(bΣ(𝑖))|

tr(Σ(𝑖)) = e 𝑂

Í 𝑗(𝜆(𝑖) 𝑗)2

= 𝑜(1). (9)

Moreover, the following bounds the estimation error of each eigenvalue. Lemma 7. Suppose Assumption 1. For any 𝛿 (0, 1), for any 𝐶poly > 0, with probability at least 1 1/𝑇𝐶poly, we have the following for any 𝑗= 1, ..., 𝑝as 𝑇 :

b𝜆(𝑖) 𝑗 𝜆(𝑖) 𝑗 = 𝑂

Lemma 7 implies the estimator of each eigenvalue is 𝑜(1) if we choose 𝑁 tr(Σ(𝑖)). However, even if we choose a large 𝑁, the error is still non-negligible for the tail of eigenvalues where |b𝜆(𝑖) 𝑗 𝜆(𝑖) 𝑗| is

very small7. Consequently, b𝜆(𝑖) 𝑗 for large 𝑗are not necessarily consistent, so as to the effective rank and the coherent rank estimated from them. To address this, we estimate the decay rate 𝛽𝑇, and then estimate the subsequent statistics.

Let the estimated decay rate be b𝛽𝑇= (1/𝜏) Í𝜏 𝑘=1 log(b𝜆𝑘/b𝜆𝑘+1)/log((𝑘+ 1)/𝑘). Theoretically, b𝛽𝑇is consistent for any constant 𝜏> 1. In practice, we can use a reasonable constant 𝜏, such as 𝜏= 10, for robustness. To estimate the effective ranks, we use the following form

e𝜆(𝑖) 𝑘 = b𝜆(𝑖) 1 𝑘 b𝛽𝑇.

Namely, we consider empirical analogues of the effective rank for 𝑘as

b𝑟𝑘(Σ(𝑖)) := tr(bΣ(𝑖))

e𝜆(𝑖) 𝑘+1 , and b𝑅𝑘(Σ(𝑖)) := (tr(bΣ(𝑖)))2

Í 𝑗>𝑘(e𝜆(𝑖) 𝑗)2 .

We also define an estimator for the coherent rank as b𝑘𝑁:= min{𝑘 N {0} | b𝑟𝑘(Σ(𝑖)) 𝑁}. Further, we define estimators of 𝐵(𝑖) 𝑁,𝑇, 𝑉(𝑖) 𝑁,𝑇of Eq. (4) as

b𝐵(𝑖) 𝑁,𝑇:= e𝜆(𝑖) b𝑘𝑁, and b𝑉(𝑖) 𝑁,𝑇:=

𝑁+ 𝑁 b𝑅b𝑘𝑁(Σ(𝑖))

Note that the estimators b𝑟𝑘and b𝑅𝑘use the trace tr(bΣ(𝑖)), which is a 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 affect8 asymptotic consistency of the coherent rank estimator b𝑘𝑁.

The following lemma states that small 𝜏suffices to assure the quality of b𝛽(𝑖). We study a convergence rate of b𝛽(𝑖) and the other estimators as follows.

7Remember that we consider Σ(𝑖) = Σ(𝑖) (𝑇) that depends on 𝑇. Tail of eigenvalues are 𝑜(1) to 𝑇as well. 8This is because Í 𝑗𝑗 𝛽𝑇with 𝛽𝑇< 1 or 𝛽𝑇 1 is tail-heavy.

Algorithm 2 Adaptive Explore-then-Commit (AEt C)

while 𝑡= 1, 2, 3, ... do

Observe 𝑋(𝑖) (𝑡) for all 𝑖 [𝐾]. Choose 𝐼(𝑡) = 𝑡 𝐾 𝑡/𝐾 . Receive a reward 𝑌(𝐼(𝑡)) (𝑡). if 𝑡 { 𝑒𝑁 | 𝑁 N, 𝑁 log𝑇} then

if Stop(𝑡/𝐾) then

𝑇0 𝑡. Break. end if end if end while for 𝑖 [𝐾] do

b𝜃(𝑖) (X(𝑖)) (X(𝑖) (X(𝑖)) ) 1Y(𝑖). end for for 𝑡= 𝑇0 + 1, ...,𝑇do

Observe 𝑋(𝑖) (𝑡) for all 𝑖 [𝐾]. Choose 𝐼(𝑡) = argmax𝑖 [𝐾] 𝑋(𝑖) (𝑡), b𝜃(𝑖) . Receive a reward 𝑌(𝐼(𝑡)) (𝑡). end for

Lemma 8. Suppose Assumption 1. Suppose DGP of Example 1 or Example 2 in Proposition 1.9 Assume that we choose 𝑁= 𝑁(𝑇) such that tr(Σ(𝑖))/𝑁= 𝑜(1) for all 𝑖. Then, for any 𝐶poly > 0, with probability at least 1 1/𝑇𝐶poly, we have

|e𝜆(𝑖) 𝑘 𝜆(𝑖) 𝑘|

𝜆(𝑖) 𝑘 = 𝑜(1),

as 𝑇 for all 𝑘 [𝜏]. Moreover, it implies |𝛽𝑇 b𝛽𝑇| = 𝑜(1) and

( b𝐵(𝑖) 𝑁,𝑇

𝐵(𝑖) 𝑁,𝑇 , b𝑉(𝑖) 𝑁,𝑇

= 𝑇𝑜(1). (11)

Eq. (11) states that the estimated rate of error is accurate as 𝑇 . To see this, for Example 1 in Proposition 1, the estimated error rate is 𝑇𝑜(1) (

𝑇𝑎/𝑁+ 𝑇 𝑎), whose exponent approaches to

𝑇𝑎/𝑁+ 𝑇 𝑎as 𝑇 .

5.2 Adaptive Explore-then-Commit (AEt C)

The Adaptive Explore-then-Commit (AEt C) algorithm is described in Algorithm 2. Unlike Et C, the amount of exploration in AEt C is adaptively determined based on the stopping condition:

Stop(𝑖) (𝑁) = 𝑁> 𝐶𝑇tr(bΣ(𝑖)) 𝑁𝐾 𝑇

b𝐵(𝑖) 𝑁,𝑇+ b𝑉(𝑖) 𝑁,𝑇

and Stop = 𝑖 [𝐾]Stop(𝑖), where 𝐶𝑇= 𝐶𝑇(𝑇) is a function of 𝑇that slowly diverges to + . The first condition 𝑁> 𝐶𝑇tr(bΣ(𝑖)) ensures that 𝑁is large enough to have consistency on the estimators,

whereas the second condition 𝑁𝐾 𝑇

b𝐵(𝑖) 𝑁,𝑇+ b𝑉(𝑖) 𝑁,𝑇balances the exploration and exploitation. The following theorem bounds the regret of AEt C. Theorem 9. Suppose Assumption 1. Suppose DGP of Example 1 or Example 2 in Proposition 1. Then, for any 𝑐> 0, the regret (2) when we run the AEt C algorithm (Algorithm 2) with a sufficiently slowly diverging 𝐶𝑇is bounded as follows as 𝑇 :

𝑅(𝑇) = e 𝑂(𝐿(𝑇, 𝐾)𝑇𝑐),

where 𝐿(𝑇, 𝐾) is the function defined in Theorem 4.

9Note that DGP of Example 1 or 2 implies the existence of the error function of Assumption 2.

Theorem 9 states that, we can choose arbitrarily small 𝑐> 0 and the exponent of the regret of AEt C approaches that of Et C (Theorem 4). Note that the condition 𝑁 𝐶𝑇tr(bΣ(𝑖)) should not dominate the balance between exploration and exploitation: For example, 𝐶𝑇= 𝐶log𝑇for any 𝐶> 0 suffices. In practice, a constant 𝐶𝑇works.

Proof sketch of Theorem 9. We can derive that Eqs. (9), (10), and (11) for all 𝑁 [𝑇] that hold with probability at least 1 𝑂(1/𝑇) by setting 𝐶poly = 2 and taking a union bound over 𝑁, and thus

𝑁 𝐶𝑇tr(bΣ(𝑖) )

b𝐵(𝑖) 𝑁,𝑇+ b𝑉(𝑖) 𝑁,𝑇

𝐵(𝑖) 𝑁,𝑇+ 𝑉(𝑖) 𝑁,𝑇

= log(𝑇𝑜(1))

holds. Under this event, the stopping time of AEt C and Et C are at most 𝑇𝑜(1) times different. Given this, the proof of the theorem is easily modified from the proof of Theorem 4.

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.

6 Simulation

We consider two setups: (𝐾, 𝑝,𝑇) = (2, 200, 500) and (𝐾, 𝑝,𝑇) = (10, 200, 1000). For each setup, we consider a covariance matrix Σ(𝑖) = 𝑐(𝑖) Σ where 𝑐(𝑖) Uni([0.5, 1.5]) and a base covariance Σ for each 𝑖 [𝐾], which represents a heterogeneous covariance among the arms. The base covariance Σ follows the following configurations: DGP 1: Σ = diag(𝜆1, ..., 𝜆𝑝), 𝜆𝑘= 𝑘 0.5, DGP 2: Σ = diag(𝜆1, ..., 𝜆𝑝), 𝜆𝑘= exp( 𝑘) + 𝑇exp( 𝑇)/𝑝, DGP 3: Σ = diag(𝜆1, ..., 𝜆𝑝), 𝜆𝑘= 𝑘 1+1/𝑇, and DGP 4: Σ𝑖, 𝑗= 0.3 and Σ𝑖,𝑖= 0.7 for 𝑗 𝑖 [𝑝]. Note that the DGPs 1 and 3 correspond to Examples 2 and 1 in Proposition 1. DGP 3 is benign as well, while DGP 4 is not. We generate 𝑋(𝑖) (𝑡) from a centered 𝑝-dimensional Gaussian with covariance Σ(𝑖), 𝜃(𝑖) from a standard normal distribution which yields non-sparse parameter vectors, and 𝑌(𝑖) (𝑡) by the linear model (1) with the noise with variance 𝜎2 = 0.01. We compare proposal (AEt C, 𝐶𝑇= 2) to ESTC [Hao et al., 2020], Lin UCB [Li et al., 2010, Abbasi-Yadkori et al., 2011], and DR Lasso Bandit [Kim and Paik, 2019].

Figure 2 illustrates the accumulated regret 𝑅(𝑡) in relation to the round 𝑡 [𝑇]. In the first three benign DGPs, the AEt C consistently outperforms the other methods. In DGP 2, the advantage of AEt C 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, AEt C performs significantly better than its competitors in DGP 1 and DGP 3, where the eigenvalues have a heavy-tail distribution. In a non-benign example of DGP 4, the proposed method is still comparable to Lin UCB, which demonstrates the utility of an interpolating estimator.

Yasin Abbasi-Yadkori, D avid P al, and Csaba Szepesv ari. 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 concepts. In Proceedings of the Sixteenth International Conference on Machine Learning, ICML, page 3 11. Morgan Kaufmann Publishers Inc., 1999. 1

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 o Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., 47(2-3):235 256, 2002. doi: 10.1023/A:1013689704352. 3

Peter L Bartlett, Philip M Long, G abor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30063 30070, 2020. 2, 3, 4, 5, 6, 8, 13, 19

Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensional covariates. Oper. Res., 68(1):276 294, 2020. 1

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. 1

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 on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 208 214. PMLR, 11 13 Apr 2011. 1

Dylan J. Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. In Advances in Neural Information Processing Systems 32, pages 14714 14725, 2019. 13

Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 33:10753 10763, 2020. 1, 3, 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 Neur IPS, 2022. 1

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):110 133, 2017. 2, 3, 8, 19

T.L Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4 22, 1985. ISSN 0196-8858. 1, 3

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, 10

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. 1, 3

L eo 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 2335, 2021. 2

Shogo Nakakita and Masaaki Imaizumi. Benign overfitting in time series linear model with overparameterization. ar Xiv preprint ar Xiv:2204.08369, 2022. 13

Min-hwan Oh, Garud Iyengar, and Assaf Zeevi. Sparsity-agnostic lasso bandit. In International Conference on Machine Learning, pages 8271 8280. PMLR, 2021. 1

Steffen Rendle. Factorization machines. In Geoffrey I. Webb, Bing Liu, Chengqi Zhang, Dimitrios Gunopulos, and Xindong Wu, editors, ICDM 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 Society, 58(5):527 535, 1952. 1

Liang Tang, R omer 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. ar Xiv preprint ar Xiv:2009.14286, 2020. 3, 4, 5, 6, 13, 14

Sara A Van De Geer and Peter B uhlmann. 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. 5

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. 1

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, Rec Sys 22, page 456 459. Association for Computing Machinery, 2022. 1, 2