Anytime Model Selection in Linear Bandits
Authors: Parnian Kassraie
Nicolas Emmenegger
Andreas Krause
Aldo Pacchiano
Venue: NeurIPS 2023 poster (2023)
Keywords: bandits
model selection
online learning

Abstract: Model selection in the context of bandit optimization is a challenging problem, as it requires balancing exploration and exploitation not only for action selection, but also for model selection. One natural approach is to rely on online learning algorithms that treat different models as experts. Existing methods, however, scale poorly ($\mathrm{poly}M$) with the number of models $M$ in terms of their regret.
Our key insight is that, for model selection in linear bandits, we can emulate full-information feedback to the online learner with a favorable bias-variance trade-off. This allows us to develop ALEXP, which has an exponentially improved ($\log M$) dependence on $M$ for its regret.
ALEXP has anytime guarantees on its regret, and neither requires knowledge of the horizon $n$, nor relies on an initial purely exploratory stage.
Our approach utilizes a  novel time-uniform analysis of the Lasso, establishing a new connection between online learning and high-dimensional statistics.

Anytime Model Selection in Linear Bandits
Parnian Kassraie' 'ETH Zurich
Nicolas Emmenegger'
Andreas Krause' Aldo Pacchiano Boston University
Broad Institute of MIT and Harvard nicolaem, krausea] @ethz. ch
{pkassraie,
pacchian@bu.c edu
Abstract
Model selection in the context of bandit optimization challenging problem, it requires balancing exploration and exploitation not only for action selection, but also for model selection. One natural approach to rely on online learning algorithms that treat different models experts. Existing methods, however, scale poorly (poly.) with the number of models M in terms of their regret. Our key insight is that, for model selection in linear bandits, feedback to the online learner with a favorable biri-vari trade-off. This allows to develop ALExP, which has exponentially improved (log M) dependence on M for its regret. ALEXP has anytime guarantees on its regret, and neither relies initial purely exploratory stage.
emulate full-information
requires knowledge of the horizon Our approach utilizes a novel time-uniform analysis of the Lasso, establishing a connection between online learning and high-dimensional statistics.
Introduction
When solving bandit problems or performing Bayesian optimization, we need to commit to a reward model priori, based on which estimate the reward function and build a policy for selecting the next action. In practice, there are many ways to model the reward by considering different feature maps hypothesis spaces, e.g., for optimizing gene knockouts [Gonzalez et al., 2015, Pacchiano et al., 2022] or parameter estimation in biological dynamical systems [Ulmasov et al., 2016, Imani al., 2019].
known priori which model going to yield the most sample efficient bandit algorithm, and we can only select the right model as we gather empirical evidence. This leads us ask, can we perform adaptive model selection, while simultaneously optimizing for reward?
In an idealized setting with no sampling limits, given a model class of size M, we could initialize M bandit algorithms (a.k.a agents) in parallel, each using of the available reward models. Then, as the algorithms run, at every step we can select the most promising agent, according to the cumulative rewards that obtained far. Model selection on a M-dimensional probability simplex, where the probability of selecting an agent is dependent on its cumulative reward, and the optimizer seeks find the distribution with the best return in hindsight. This approach is impractical for large model classes, since at every step, it requires drawing M different samples parallel from the environment so that the reward for each agent is realized.
then be cast into online optimization problem
In realistic applications of bandit optimization, we can only draw one sample at a time, and so we need to design algorithm which allocates more samples to the agents that are deemed more promising. Prior work [e.g., Maillard and Munos, 2011, Agarwal et al., 2017] [] propose to run a single meta algorithm which interacts with the environment by first selecting an agent, and then selecting action according to the suggestion of that agent. The online model selection problem can still be emulated in this setup, however this time the optimizer receives partial feedback, coming from only one agent. Con- sequently, many agents need to be queried, and the overall regret scales with poly.,, again restricting this approach to small model classes. In fact, addressing the limited scope of such algorithms, Agarwal et al. [2]1] raise an open problem on the fcasibility of obtaining a log M dependency for the regret.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

We show that this rate is achievable, in the particular case of linearly parametrizable rewards. We de- velop a technique to "hallucinate" the reward for every agent that was not selected, and run the online optimizer with emulated full-information feedback. This allows the optimizer to assess the quality of the agents, without ever having queried them. As result, our algorithm ALExp, satisfies a regret of rate (max Vnlog' M, n2/4 Vlog M)), with high probability, simultaneously for all n 2 1 (The- orem 1). Our key idea, leading to log M dependency, is to employ the Lasso as a low-variance online regression oracle, and estimate the reward for the agents that were not chosen. This trick is made pos- sible through our novel time-uniforn analysis of online Lasso regression (Theorem 3). Consequently, and explores adaptively without requiring an initial exploration stage. Empirically we find that ALEXP consistently outperforms prior work across a range of environments.
ALEXP is corizzon-indepente
Table 1: Overview of literature online model selection for bandit optimization
MS
MS Guarantee
adaptive exploration
Regret
anytime
Technique
Sparse Linear
Lasso
log M
x
x
x
Bandits
MS for Black-
OMD with
poly M
/
x
Box Bandits
bandit feedback
MS for Linear
EXP4 with
log M
/
Bandits (Ours)
full-information
2 Related Work
Online Model selection (MS) for bandits considers combining a number of agents in a master algorithm, with the goal of performing as well as the best agent [Maillard and Munos, 2011, Agarwal et al., 2017, Pacchiano et al., 2020, Luo et al., 2022]. This literature operates on black-box model classes of size M and uses variants of Online Mirror Descent (OMD) to sequentially select the agents. The optimizer operates on importance-weightee estimates of the agents' rewards, which has high variance M) and is non-zero only for the selected agent. Effectively, the optimizer receives partial (a.k.a. bandit) feedback and agents are at risk of starvation, since at every step only the selected agent gets the new data point. These works assume knowledge of the horizon, however, we suspect that this may be lifted with a finer analysis of OMD.
Sparse linear bandits use pparsit--inducing methods, often Lasso [Tibshirani, 1996), for estimating the reward in presence of many features, as an alternative model selection. Early results are in the data-rich regime where the stopping time n is known and larger than the number of models, and some suffer from poly M regret dependency [e.g., Abbasi-Yadie Yadkori et al., 2012]. Recent efforts often consider the contextual case, where at every step only finite stochastic subset of the action domain presented to the agent, and that the distribution of these points is i.i.d. and sufficiently diverse [Li et al., 2022, Bastani and Bayati, 2020, Kim and Paik, 2019, Oh et al., 2021, Cella and Pontil, 2021]. We do not rely on such assumptions. Most sparse bandit algorithms either start with a purely exploratory phase [Kim and Paik, 2019, Li ct al., 2022, Hao et al., 2020, Jang et al., 2022]. on a priori scheduled exploration [Bastani and Bayati, 2020]. The exploration budget is set according to the horizon n. Therefore, such algorithms inherently require the knowledge of n and can be made anytime only via the doubling trick [Auer et al., 1995]. Table 2 presents an in-depth overview.
rely
ALEXP inherits the best of both worlds (Table I): its regret enjoys the log M dependency of sparse linear bandits even on compact domains, and has adaptive probabilistic exploration with anytime guarantees. In contrast to prior literature, we perform model selection with an online optimizer (EXP4), which hallucinates full-information feedback using a low-variance Lasso estimator instcad of importance tepirteance-eigghedd weighted estimates. Moreover, our anytime approach lifts the horizon dependence and the exploration requirement of sparse linear bandits.
Our work is inspired by and contributes to the field of Learning with Expert Advice, which analyzes incorporating the advice of M oblivious (non- adaptivee experts, with bandit or full-information feedback [Haussler et al., 1998, Auer et al., 2002b, McMahan and Streeter, 2009]. The idea of employing an online optimizer for learning stems from this literature, and has been used in various applications of online learning [Foster et al., 2017, Singla et al., 201 8, Muthukumar et al., 2019, Karimi et al., 2021, Liu et al., 2022]. particular, we are inspired by Foster and Rakhlin [2020) and Moradipari et al. [2022], who apply EXP4 to least squares estimates, for arm selection in K K-ammed
2

---

contextual bandits. However, their algorithms are not anytime, and due to the choice of estimator, the corresponding regret scales with O(min (onin(vM,,Maa log M)).
3 Problem Setting
We consider bandit problem where learner interacts with the environment in rounds. At step t the learner selects an action V2 E X, where X' C Rdo is a compact domain and observes a noisy reward 1/2 = rxx,) + such that E; is an i..d. zero-mean sub- Sab-Gaussinn variable with parameter o². We assume the reward function r X + R is linearly parametrizable by some unknown feature map, and that the model class {Ø) R - R jj = .,....;. M) contains the set of plausible feature maps. We consider the setting where M can be very large, and while the set {Φ²} may include misspecificed feature maps, it contains least one feature map that represents the reward function, i.e. there exists j* E [M] such that r(-) = 0 Φy. (-). We assume the image of Φj spans Rd, and two feature maps
linearly dependent, i.e. for any j. [M], there exists a E R such that
(5(() = y (-). This assumption, which is satisfied by design in practice, ensures that the features are not ill-posed and we can explore in all relevant directions. We assume that the concatenated feature map ((x)= == (x) ΦM (x)) is normalized [|ő(()) < 1 for all x E X' and that
|10, S B, which implies |r(x)] I B for all x X'
We will model this problem in the language of model selection where a meta algorithm aims to optimize the unknown reward function by relying on number of base learners. In order to interact with the environment the meta algorithm selects an agent that in turn selects an action. In our setting we thinking of each of these M feature maps controlled by base agent running its own algorithm. Base agent j uses the feature map Φj for modeling the reward. At step of the bandit problem, each agent j is given access to the full history H₃-1 { v1),-.., (# to locally estimate the reward as ,, where B E R is the estimated coefficients vector. The agent then uses this estimate to develop its action selection policy pt,j MM)).. Here, M denotes the space of probability measures defined on X. The condition on existence of j* will ensure that there least one agent which using a correct model for the reward, and thereby can solve the bandit problem if executed in isolation. We refer to agent j" as the oracle agent.
11-1)) }. and uses it
Our goal is to find sample-efficient strategy for iterating over the agents, such that their suggested actions maximize the cumulative reward, achieved over any horizon n. 2 1. This is equivalent to minimizing the cumulative regret R(n) E r(æ:)) r((:), where ax is global maximizer of the reward function. We neither fix n, nor assume knowledge of it.
4 Method
As warm-up, consider an example with deterministic agents, i.e., when Pt.j is a Dirac measure on a specific action Zt.j. Suppose it was practically feasible to draw the action suggested by every agent and observe the corresponding reward vector r; (rt.)) In this case, model selection becomes full-information online optimization problem, and we can design minimax optimal algorithm as follows. We assign a probability distribution q. = (4t.) to the models, and update such that the overall average return Em= q. r, competitive to the best agent's average return Σ "t.j*. At every step, we update (t-1, X exp(E. )e since such exponential weighting is known to lead to optimal solution for this classic online learning problem [Cesa- -iiachBi and Lugosi, 2006]. In our setting however, the agents are stochastic, and we do not have access to the full rt vector.
We propose the Anytime EXPonential weighting algorithm based on Lasso reward estimates (ALExP), summarized Algorithm 1. At step we first sample an agent jt. and then sample an action 2; according to the agent's 's policy Pt.j. Let AM denote the M M-dimensional probability simplex. We maintain a probability distribution q, E AM over the agents, and update sequentially as we accumulate evidence on the performance of each agent. Ideally, we would have adjusted gr,i according to the average return of model j, that is, Em--,,, rx)). However, since r is unknown, we estimate the average reward with some fi.. We then update qe for the next step via,
Φ+1, = exp(n Ei= Peg)
EM exp(n) Σi= P2.))
3

---

for all ,....,,,, M, where Te is the learning rate, and controls the sensitivity of the updates. This rule allows us to imitate the full-iffrrmation example that we mentioned above. By utilizing ft. and hallucinating feedback from all agents, we can reduce the probability of selecting badly performing agent, without ever having sampled them (c.f. Fig. 4). It remains to design the estimator Prj. We concatenate all feature maps, and, knowing that many features are redundant, use a sparsity inducing estimator over the resulting coefficients vector. Mainly, let 0 the concatenated coefficients vector. We then solve
0xr) E R Ridd be
M Σ 110112 j=1
1 7
0. = arg min C(0; At) - arg min GERMA
- -191-0,011 + 24,
BERMd
where D, [ob (x=))aeee E RixMd is the feature matrix, yt E IR' is the concatenated reward vector, and de is an adaptive regularization parameter. Problem (1) is the online variant of the group Lasso [Lounici et al., 2011]. The second term is the loss is the mixed (2, 1n-ormm of 0, which can be seen as the ---ormm of the vector (10g]l [|. |00xz] Il) E RM This norm induces sparsity at the group level, and therefore, the sub-vectors o., E Re that correspond to redundant feature maps are expected to be O, i.e. the null vector. We then estimate the average return of each model by simply taking an expectation Az. = Ep (0. ((x))). This quantity is the average return of the agent's policy Pt+1..j according to our Lasso estimator. In Section 5.2 we explain why the particular choice of Lasso is crucial for obtaining log M rate for the regret.
For action selection, with probability Yr we sample agent j with probability tt, and draw D, ~ Pt. as per suggestion of the agent. With probability 1 1- .tt we choose the action according to some exploratory distribution π E M(X)) which aims to sample informative actions. This can be any design where supp(")) = X. We mix Pt.j with x, to collect sufficiently diverse data for model selection. We are not restricting the agents' policy, and therefore can not rely on them to explore adequately. In Theorem 1, we choose decreasing sequence of (7))22 the probabilities of exploration at step 2 1, since less exploration will be required as data accumulates. To conclude, the action selection policy of ALExP is formally described the mixture
M
(e(x) = TT(x) + (1- - 71)
Σ (x)Pt,(()). j=1
5
Main Results
For the regret guarantee, we consider specific choices of base agents and exploratory distribution. Our analysis may be extended to include other policies, since ALEXP can be wrapped around any bandit agent that is described by some Pt.j. and allows for random exploration with any distribution æ.
Base Agents. We assume that the oracle agent has either a UCB |Abbasi-Yadkori Yadkori et al., 2011] or GREEDY [Auer et al., 2002a] policy, and all other agents are free to choose any arbitrary policy. Similar treatment can be applied to cases where the oracle uses other (sublinear) polices for solving linear or contextual bandits [e.g., Thompson, 1933, Kaufmann et al., 2012, Agarwal al., 201 4]. In either case, agent j* calculates a ridge estimate of the coefficients vector based on the history H,
Bus arg figminnly. .... -||lll (eTy.DD. + +X1)
TT Pt.--tt-
BERd
Here De..- Rtxd is the feature matrix, where each row is JJ. (xx)) and Á is the regularization constant. Then at step t, a GREEDY oracle suggests the action which maximizes the reward estimate 3. (x)), and UCB oracle queries arg max 1,- (ar)) where -4-1,- (-) is the upper confidence bound that this agent calculates for r(-). Proposition 21 shows that the sequence (ut.5 )121 is in fact anytime valid upper bound for over the entire domain.
Exploratory policy. Performance of ALEXP depends on the quality of the samples that ा suggests. The eigenvalues of the covariance matrix E(T, x) == Ex- ((x)) (6 (æx) reflect how diverse the data is, and thus are a good indicator for data quality. van de Geer and Bühlmann [2009] present survey on the notions of diversity defined based on these eigenvalues. Let Amin (A) denote the minimium eigenvalue of a matrix A. Similar to Hao et al. [2020]. we assume that π is the maximizer of the problem below and present our regret bounds in terms of
Omin = Cmin (X, Φ) = max Amin (V(TT, Φ)), SEM(X)
(2)

---

Algorithm ALEXP
Inputs: T, (M,, Te, A,) for t 2
Let @1 f- MM) and initialize base agents (f1,1:...,PI,
for /. 2 1 do
Draw a₁ ~ Bernoulli(r)).
Decide to explore or exploit
if at = 1 then
Choose action 2; randomly according to и.
Explore
else
Draw je ~ qt-
> Select an agent
Draw H; Pt.j+
Select the action suggested by the agent
end
Observe 3r r(xx)) Ex-
Receive reward
H, H U ((x)..)))
b. Append history
0. t arg min L(O; He)
Update the parameter estimate
Report H, to all agents, and get updated policies . P...I...
Update agents
Update estimated average return of every agent
fri + Exorar 00 Φ())), j I,..., M
Update agent probabilities
qt+15 f exp(1): Σ1 Ei=1 Po.))
Σ exp(1): Ei=r Po.5)
M
end for
which is greater than zero under the conditions specified in our problem setting. Prior works in the sparse bandit literature all require a similar or stronger assumption of this kind, and Table gives an overview, Alternatively, one can work with an arbitrary オ. e.g., Unif (2'), (X'), long as Amin A (M(,,, Φ)) is bounded away from zero. Appendix C.1 reviews some configurations of (Φ, X, л) that lead to a non- zero minimum eigenvalue, and Corollary 12 bounds the regret of ALEXP with uniform exploration.
For this choice of agents and exploratory distribution, Theorem presents an informal regret bound. Here, we have used the O notation, and only included the fastest growing terms. The inequality is made exact in Theorem 14, up to constant multiplicative factors.
Theorem 1 (Cumulative Regret ALExP, Informal). Let 8 E (0, 1] and set π to be the maximizer of (2). Choose learning rate Ti (C tointt1//2 1atptttt/////////// (CM, d)), exploration probability Tt O(t 1/4) and Lasso regularization parameter A (/Cminn-1/C(MMM d)), where
C(M,8, 8, o O -V (0 (V1+
(log log d)+ + vd (log(M/8)) + (log log d)+)
Then ALExp satisfies the cumulative regret
R(n) =(n23AB+ n2/AC(M, C- Co VRC(M, log M
1/2 -C-1/2 1///,/// 5/8 v doo (n) + 1og(1/8)
simultaneously for all 2 1, with probability greater than
In this bound, the first term is the regret incurred at exploratory steps (when term due to the estimation error Lasso (i.e., ||0 O.ll). and the third term the regret of the exponential weights sub-algorithm. The fourth term, is the regret bound for the oracle agent j*, when run within the ALExP framework. It does not depend on the agent's 's policy (greedy or optimistic), and is worse than the minimax optimal rate of /nd log This is because the oracle is suggesting actions based on the history He, which includes uninformative action-rewait pairs queried by other, potentially misspecified, agents. In Corollary 12, provide regret bound independent of Cuin. for orthogonal feature maps, and show that the same O / log M, n3// Vlog M)) rate may be achieved even with the simple choice π = Un'.
1), the second
5

---

5.1 Proof Sketch
The regret is caused by two sources: selecting a sub-optimal agent, and an agent selecting a sub- optimal action. Accordingly, for any j ,,...,,, M, we decompose the regret
R(n)= = -r(a)) r((;)) = Σ r(a*) res)) +
Tis - r(mz)).
(3)
t=1
The first term shows the cumulative regret of agent j. when within ALEXP. The second term evaluates the received reward against the cumulative average reward of model j. We bound each term separately.
Virtual Regret. The first term
= Ei= r(x*) - -t, compares the suggestion of agent against the optimal action. We call it the virtual regret since the sequence (ft.j)+21 of the actions suggested by model j are not necessarily selected by the meta algorithm, unless Jr j. This regret is merely a technical tool, and not actually realized when running ALEXP. The virtual regret of the oracle agent may still be analyzed using standard techniques for linear bandits, e.g., Abbasi- Yadkori et al. [2011], I]. however we need to adapt it to take into account a subtle difference: The confidence sequence of model j is constructed according to the true sequence of actions (æz))21, while its virtual regret is calculated based on the virtual sequence (Z1,5- )e21, which the model suggests. The two sequences only match at the steps when model j* is selected. Adapting the analysis of Yadkori et al. (201] 1J to this subtlety, we obtain in Lemma 15 that with probability greater than 6, simultaneously for all 1,
Ry- (n) O (n 1/// 1/2 V /loog (n) + log(1/6))
Model Selection Regret. The second term in (3) is the model selection regret, j) = Σi= "tji raz;), which evaluates the chosen action by ALExP against the suggestion of the j-th agent. Our analysis relies on a careful decomposition of R)n,j),
n
R(n.j) Σ
Te ris-
+ fus
Σ q
Σ
(hr Te,)) (.,))
Σ nart r(x:)
m
(m)
(IV)
We bound away each term in a modular manner, until we are left with the regret of the standard exponential weights algorithm. The terms (I) and (III) are controlled by the bias of the Lasso estimator, and are (n33/4 8, d)) (Lemma 19). The last term (IV) is zero in expectation, and reflects the deviation of r(x;) from its mean. We observe that the summands form bounded Martingale difference sequence, and their sum grows as ((v)) (Lemma 18). Term (II) the regret of our online optimizer. which depends on the variance of the Lasso estimator. We bound this term with O(VCC(M, 5, d) log M), by first conducting standard anytime analysis of exponential weights (Lemma 17), and then incorporating the anytime Lasso variance bound (I (Lemma 20). We highlight that neither of the above steps require assumptions about the base agents. Combining these steps, Lemma 16 establishes the formal bound the model selection regret.
Anytime Lasso. We develop novel confidence intervals for Lasso with history-dependent data, which are uniformly valid over an unbounded time horizon. This result may be of independent interest in applications of Lasso for online learning or sequential decision making. Here, we use these confidence intervals to bound the bias and variance terms that appear in our treatment of the model selection regret. The width of the Lasso confidence intervals depends on the quality of feature matrix T, often quantified by the restricted eigenvalue property [Bickel et al., 2009, van de Geer and Bühlmann, 2009, Javanmard and Montanari, 2014]:
Definition 2. For the feature matrix 4 E RexdM we define (()),)) for any 1 S s S M
b 2
x(Dr, = inf (J.b) Vt V jie
b,
s.t. b E gd {(0),
Σ
bbbll2 3 > b2ll2,, J (1....,,4M M}. |l| S.s.
j
JEJ

---

Our analysis is in terms of this quantity, and Lemma 8 explains the connection between k( s) and Cmin as defined in (2), particularly that x(,,. 2) is also positive with a high probability.
Theorem (Anytime Lasso Confidence Sequences). Consider the data model yt 0 ((x))) &t for all & 2 1, where e, is i..dd zero-mean sub-Gaussian noise, and (xx))21 is preeditllee where Fi = (11..... Lt E1...... Et-1). Then the solution of (1) guarantees
4v10Ae
IP 1I 1:
|0
0.1
2 21-8
n: n²(
if the regularization parameter satisfies for all
20
12
5
Ae 1
(log(2M/6) + (log log +)+)+ V2
V2 (lo((2// + (log log d)+).
Our confidence bound enjoys the same rate as Lasso with fixed (offline) data, up to log log d factors. We prove this theorem by constructing self-normalized martingale sequence based on the 2--nrr of the empirical process error (Φ, Ex). We then apply the "stitched" time-uniform boundary of Howard et al. [2021]. Appendix B elaborates on this technique. Previous work on sparse linear bandits also include analysis of Lasso in an online setting. when D, is Fr measurable. Cella and Pontil [2021] imitate offline analysis and then apply union bound over the time steps, which multiplies the width by log n and requires knowledge of the horizon. Bastani and Bayati [2020] also rely on knowledge of n and employ a scalar-valued Bernstein inequality on -orm of the empirical process error, which inflates the width of the confidence sets by a factor of vd. We work directly on the f--norm, and use curved boundary for Lub-Gamma martingale sequences, which according to Howard et al. [2021] is uniformly tighter than a Bernstein bound, especially for small t.
5.2 Discussion
In light of Theorem and Theorem 3, we discuss some properties of ALExP.
Sparse EXP4. Our approach presents a new connection between online learning and high- dimensional statistics. The rule for updating the probabilities in ALExP is inspired by the exponential weighting for Exploration and Exploitation with Experts (EXP4) algorithm, which was proposed by Auer et al. [2002b] and has been extensively studied in the adversarial bandit and learning with expert advice literature [e.g.. McMahan and Streeter, 2009, Beygelzimer et al., 2011]. EXP4 classically uses importance- weighted (IW) or ordinary least squares (LS) estimators to estimate the return rt.j. both of which are unbiased but high-variance choices [Bubeck et al., 2012]. In particular, in our linearly parametrized setting, the variance of IW and LS scales with Md, which will lead to a poly(M (M) regret. However, it is known that introducing bias can be useful if it reduces the variance [Zimmert and Lattimore, 2022]. For instance, EXP3-IX [Kocák al., 2014] and EXP4-IX [Neu, 2015] construct a biased IW estimator. Equivalently, others craft regularizers for the reward of the online optimizer, seeking to improve the bias-variance balance [e.g., Abernethy et al., 2008, Bartlett et al., 2008 Abernethy and Rakhlin, 2009, Bubeck et al., 2017, Lee et al., 2020, Zimmert and Lattimore, 2022]. key technical observation in this work is that our online Lasso estimator leads EXP4 to achieve sublinear regret which depends logarithmically on M. This is due to the fact that while the estimator itself is diddimension its bias squared and variance scale with Vl M. To the best of our knowledge, this work is first to instantiate the EXP4 algorithm with a sparse low-variance estimator.
Adaptive and Anytime To estimate the reward, prior work on sparse bandits commonly emulate the Lasso analysis on offline data or on martingale sequence with a known length [Hao et al., 2020, Bastani and Bayati, 2020]. These works require a long enough sequence of exploratory samples, and knowledge of the horizon to plan this sequence. ALEXP removes both of these constraints, and presents fully adaptive algorithm. Crucially, we employ the elegant martingale bounds of Howard et al. [2020] to present the first time-uniform analysis of the Lasso with deeendent data (Theorem 3). This way we can use all the data points and explore with a probability which vanishes (/44) rate. Our anytime confidence bound for Lasso, together with the horizon-indes indeenndenn analysis of the exponential weights algorithm, also allows ALExP to be stopped at any time with valid guarantees.
Rate Optimality. For M >> n, we obtain a O( n log' M) regret, which matches the rate conjec- tured by Agarwal et al. [2017]. However, if M is comparable smaller, our regret scales with
7

---

Lightly Correlated
Highly Correlated
Many Models
20
20
p
10
p=10
p=
5=2
15-
Regret
10-
25
50
75
100
25
50
75
100
0
25
50
75
100
Oracle UCB
ALEXP
Naive UCB
ETC
ETS
Corral
Figure 1: ALEXP can model-select in both
Figure 2: ALExP performs well on a large class (M 165)
orthogonal and correlated classes (M = 55)
Onn ((n3/4Vlogg Vlog M). and while it is still sublinear and scales logarithmically with M,, the dependency on n is sub-optimal. This may be due to the conservative nature of our model selection analysis, during which we do not make assumptions about the dynamies of the base agents. Therefore, ensure sufficiently diverse data for successful model selection, we need to occasionally choose exploratory actions with vanishing probability of Yt- We conjecture that this is avoidable, if we make more assumptions about the agents, e.g., that sufficient number of agents can achieve sublinear regret if executed in isolation. Banerjee al. [2023] show that the data collected by sublinear algorithms organically satisfies a minimum eigenvalue lowerbound, which may also be sufficient for model selection. We leave this as open question for future work.
Experiments
Experiment Setup. We create a synthetic dataset based on our data model (Section 3), and choose the domain to be 1-dimensional X' [-1, 1]. As natural choice of features, consider the set of degree-p Legendre polynomials, since they form an orthonormal basis for (2)) if p grows unbound- edly. We construct each feature map, by choosing different polynomials from this set, and therefore obtaining MM - (D+1) different models. More formally, we let (x) = (Pj, (z)).... Pj. (x)) E R. where fj1.....Ja.
... and Pj denotes a degree j' Legendre polynomial. To construct the reward function, we randomly sample j* from [M]. and draw 0,. from an i.i.d. standard gaussian distribution. We then normalize ||0,- 1. When sampling from the reward, we add Gaussian noise with standard deviation o = 0.01. Figure 5 in the appendix shows how the random reward functions may look. For all experiments we set n 100, and plot the cumulative regret R(n) averaged over 20 different random seeds, the shaded areas in all figures show the standard сттог across these runs.
with oracle knowledge of j*, and a naive one which takes into account all M feature maps. We run Explore-then then-Commit (ETC) by Hao al. [2020], which explores for horizon of ng steps, performs Lasso once, and then selects actions greedily for the remaining steps. As another baseline, we introduce Explore-then-Seleca (ETS) that explores for no steps, performs model selection using the sparsity pattern of the Lasso estimator. For the remaining steps, the policy switches to UCB, calculated based on the selected features. Performance of ETC and ETS depends highly on no. we tune this hyperparameter separately for each experiment. We also run CORRAL as proposed by Agarwal et al. [2017]. with UCB agents similar ALEXP. We tune the hyper-parameters of CORRAL as well. To initialize ALExP we set the rates of de, 7t and 77 according to Theorem 1, and perform a light hyper- arper-parammter tuning to choose the scaling constants. We have included the details and results of our
Algorithms. We perform experiments two UCB algorithms,
tuning Appendix F.I. To solve (1), we use CELER, fast solver for the group Lasso [Massias et al., 201 8]. Every time UCB policy used, we set the exploration coefficient 3, 2, and every time exploration required, we sample according to (X)) Appendix F includes the pseudo-code for all baseline algorithms.
Easy vs. Hard Cases. We construct easy problem instance, where 2, p 10, and thus M = 55. Models are lightly correlated since each two model can have at most one Legendre polynomial common. We also generate an instance with highly correlated feature maps where = 8 and p = 10, which will be a harder problem, since out of the total M = 55 models, there are 36 models which have least Legendre polynomials common with the oracle model j* Figure shows that not only ALEXP is not affected by the correlations between the models, but also it achieves
'The PYTHON code for reproducing the experiments is accessible on gittub..ommaasgrou//ALEEX

---

Oracle UCB
Naive UCB
ETC
ALEXP
Corral
60
15
25-
Regret
1.25
10-
2.2
40
1.5
0.75
1.2
20-
0.5
50
100
59
100
50
100
50
100
50
100
M 45
M 55
M 66
M = 78
M = 91
Figure 3: ALExP is hardly affected by increasing the number of models (y-axis have various scales)
MS Distribution
Ratio of Visited Agents
Prob. of Oracle Agent
0.10
9t-
0.150
M,
90.*
0.125
M
0.20
0.06
0.100
0.075
0.050
0.02
0.025
0.05
ALEXP
0.000
150
50
50
(a)
(b)
(c)
Figure 4: ALEXP can rule out models without ever having queried them (M 165)
a performance competitive to the oracle in both cases, implying that our exponential weights technique for model selection is robust to choice of features. ETC and ETS rely Lasso for model selection, which performs poorly in the case of correlated features. CORRAL uses log-barrier-Ol importance-weighee
with an
estimator, which has a significantly high variance. The curve for CORRAL in Figures and 2 is cropped since the regret values get very large. Figure 6 shows the complete results. We construct another hard instance (Fig. 2), where the model class is large (s 3,p 10, M 165). AL.ExP continues to outperform all baselines with a significant gap. It is clear in the regret curves how explore- thelore-teen-oommii style algorithms are inherently horizon-dependent, and may exhibit linear regret, if stopped at an arbitrary time. This is not an issue with the other algorithms.
Scaling with M. Figure 3 shows how well the algorithms scale as M grows. For this experiment we set = 2 and change p E {9..... 13]. While increasing M hardly affects ALExP and Oracle UCB, other baselines become less and less sample efficient.
Learning Dynamics of ALEXP. Figure gives some insight into the dynamics of ALEXP when M = 165. In particular, it shows how ALEXP can rule out sub-optimal agents without ever having queried them. Figure (a) shows the distribution qt, at = 20 which is roughly equal to the optimal no for ETC in this configuration. The oracle model jr is annotated with star, and has the highest prob- ability of selection. We observe that, already at this time step, more than 80% of the agents are practi- cally ruled out, due to small probability of selection. However, according Figure (b), which shows Me the total number of visited models, less than 10% of the models are queried at = 20. This is the key practical benefit of ALEXP compared to black-box algorithms such CORRAL. Lastly, Figure (c) shows how qt,5 the probability of selecting the oracle agent changes with time. While this probability is higher than that of the other agents, Figure (c) shows that qt,z is not exceeding 0.25, therefore there is always a probability of greater than 0.75 that we sample another agent, making ALExp robust hard problem instances where many agents perform efficiently. We conclude that ALExP seems to rapidly recognize the better performing agents, and select among them with high probability.
Conclusion
We proposed ALEXP, an algorithm for simultaneous online model selection and bandit optimization. As first, our approach leads to anytime valid guarantees for model selection and bandit regret, and does not rely on priori determined exploration schedule. Further, we showed how the Lasso can be used together with the exponential weights algorithm to construct a low-variance online learner. This new connection between high- sigh-dimensionl statistics and online learning opens up avenues for future research on high-dimensional online learning. We established empirically that ALEXP has favorable cnvration-eploitattton dynamics, and outperforms existing baselines. We tackled the open problem of Agarwal al. [2017], and showed that log M dependency for regret is achievable for linearly parametrizable rewards. This problem remains open for more general, non-pau non-paramttric reward classes.

---

Acknowledgments
We thank Jonas Rothfuss and Miles "ang--Henderson for their valuable suggestions regarding the writing. We thank Scott Sussex and Felix Schur for their thorough feedback. This research was supported by the European Research Council (ERC) under the European Union's 's Horizon 2020 research and Innovation Program Grant agreement no, 815943. Nicolas Emmenegger was supported by the Zeno Karl Schindler Foundation and the Swiss Study Foundation. Aldo Pacchiano would like to thank the support of the Eric and Wendy Schmidt Center at the Broad Institute of MIT and Harvard. This work was supported in part by funding from the Eric and Wendy Schmidt Center at the Broad Institute of MIT and Harvard.
References
Yasin Abbasi-Yadkon Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 2011.
Yasin Yadkor,, David Pal, and Csaba Szepesvari. mmhlin-to-confidence-see conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics. PMLR, 2012.
Jacob Abernethy and Alexander Rakhlin. Beating the adaptive bandit with high probability. In 2009 Information Theory and Applications Workshop. IEEE, 2009.
Jacob Abernethy, Elad Hazan, and Alexander Rakhlin. An efficient algorithm for bandit linear optimization. In Conference on Learning Theory, 2008
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference Machine Learning. PMLR, 2014.
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling a band of bandit algorithms. In Conference on Learning Theory. PMLR, 2017.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. Gambling in rigged casino: The adversarial multi-armes bandit problem. In Foundations of Computer Science. IEEE, 1995.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 2002a.
Peter Auer, Nicolo Cesa-Bianchi,
Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing. 2002b.
Debangshu Banerjee, Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Exploration in linear bandits with rich action sets and its implications for inference. In International Conference on Artificial Intelligence and Statistics. PMLR, 2023.
Peter L Bartlett, Varsha Dani, Thomas P Hayes, Sham M Kakade, Alexander Rakhlin, and Ambuj Tewari. High-probability regret bounds for bandit online linear optimization. In Conference on Learning Theory, 2008
Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensional covariates.
Operations Research, 2020.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In International Conference Artificial Intelligence and Statisties, 2011.
Peter J. Bickel, Ya' acov Ritov, and Alexandre B. Tsybakov. Simultaneous analysis of Lasso and Dantzig selector. The Annals of Staristics, 2009.
Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 2012.
Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. Kernel-based methods for bandit convex optimiza- tion. In ACM SIGACT Symposium Theory of Computing, pages 72-85, 2017.
10

---

Peter Bühlmann and Sara Van De Geer. Statistics for high-dimensional data: methods, theory and applications. Springer Science Business Media, 2011.
Alexandra Carpentier and Rémi Munos. Bandit theory meets compressed sensing for high dimensional stochastic linear bandit. In Artificial Intelligence and Statistics. PMLR, 2012.
Leonardo Cella and Massimiliano Pontil. Multi-task and meta-learning with sparse linear bandits. In Conference Uncertainty in Artificial Intelligence, 2021.
Nicolo Cesa-Bianche and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning. PMLR, 2020.
Dylan J Foster, Satyen Kale, Mehryar Mohri, and Karthik Sridharan. Parameter- free online learning via model selection. Advances in Neural Information Processing Systems, 2017.
Dylan Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
Sébastien Gerchinovitz. Sparsity regret bounds for individual sequences in online linear regression. In Conference on Learning Theory, 2011.
Apostolos Giannopoulos. Notes isotropic convex bodies, October 2003.
Javier Gonzalez, Joseph Longworth, David C James, and Neil Lawrence. Bayesian optimization for synthetic gene design. arXiv preprint, 2015.
Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 2020.
David Haussler, Jyrki Kivinen, and Manfred K Warmuth. Sequential prediction of individual sequences under general loss functions. IEEE Transactions on Information Theory, 1998.
Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform chernoff
bounds via nonnegative supermartingales. Probability Surveys, 2020.
Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparamet- ric, nonasymptotic confidence sequences. The Annals of Statistics, 2021.
Mahdi Imani, Seyede Fatemeh Ghoreishi, Douglas Allaire, and Ulisses M Braga-Neto. Mibo-ssm: Multi-fidelity bayesian optimization for fast inference in state-space models. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
Kyoungseok Jang, Chicheng Zhang, and Kwang-Sung Jun. Popart: Efficient sparse regression and experimental design for optimal sparse linear bandits. In Advances in Neural Information Processing Systems, 2022.
Adel Javanmard and Andrea Montanari. Confidence intervals and hypothesis testing for high- dimensional regression. The Journal of Machine Learning Research, 2014.
Mohammad Reza Karimi, Nezihe Merve Gürel, Bojan Karlaš, Johannes Rausch, Ce Zhang, and Andreas Krause. Online active model selection for pre-trained classifiers. In International Conference on Artificial Intelligence and Statistics. PMLR, 2021.
Parnian Kassraie, Jonas Rothfuss, and Andreas Krause. Meta-learning hypothesis spaces for sequen- tial decision-making. In International Conference on Machine Learning. PMLR, 2022.
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On bayesian upper confidence bounds for bandit problems. In Artificial intelligence and statistics. PMLR, 2012.
Gi-Soo Kim and Myunghee Cho Paik. Doubly-robust lasso bandit, Advances Neural Information Processing Systems, 32, 2019.

---

Tomáš Kocák, Gergely Neu, Michal Valko, and Rémi Munos. Efficient learning by implicit explo- ration bandit problems with side observations. Advances in Neural Information Processing Systems, 2014.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Chung-War Wei Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Bias no more: beshh-rbbbiility data-dependent regret bounds for adversarial bandits and mdps. Advances in Neural Information Processing Systems, 2020.
Wenjie Li, Adarsh Barik, and Jean Honorio. A simple unified framework for high dimensional bandit problems. In International Conference on Machine Learning. PMLR, 2022.
Xuefeng Liu, Fangfang Xia, Rick L Stevens, and Yuxin Chen. Cost-effective online contextual model selection. arXiv preprint, 2022.
Karim Lounici, Massimiliano Pontil, Sara Van De Geer, and Alexandre B Tsybakov. Oracle inequali- ties and optimal inference under group sparsity. The annals of statisties, 2011.
Haipeng Luo, Mengxiao Zhang, Peng Zhao, and Zhi-Hua Zhou. Corralling larger band of bandits: A case study on switching regret for linear bandits. In Conference on Learning Theory. PMLR, 2022.
Odalric-Ambrym Maillard and Rémi Munos. Adaptive bandits: Towards the best history-dependent strategy. In International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings, 2011.
Mathurin Massias, Alexandre Gramfort, and Joseph Salmon. Celer: a fast solver for the lasso with dual extrapolation. In International Conference on Machine Learning, 2018.
H. Brendan McMahan and Matthew Streeter. Tighter bounds for multi-armed bandits with expert advice. In Proceedings of the 22nd Annual Conference on Learning Theory, 2009.
Ahmadreza Moradipari, Berkay Turan, Yasin Yadkkr,,, Mahnoosh Alizadeh, and Mohammad Ghavamzadeh. Feature and parameter selection in stochastic linear bandits. In International Conference on Machine Learning. PMLR, 2022.
Vidya Muthukumar, Mitas Ray, Anant Sahai, and Peter Bartlett. Best of many worlds: Robust model selection for online supervised learning. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, 2019.
Gergely Neu. Explore more: Improved high-probability regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 2015.
Min-hwan Oh, Garud Iyengar, and Assaf Zeevi. Sparsity-annostic lasso bandit. In International Conference on Machine Learning. PMLR, 2021.
Aldo Pacchiano, My Phan, Yasin Abbasi Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvari. Model selection in contextual stochastic bandit problems. Advances Neural Information Processing Systems, 2020.
Aldo Pacchiano, Drausin Wulsin, Robert A Barton, and Luis Voloch. Neural design for genetic perturbation experiments. arXiv preprint, 2022.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary De Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Ali Rahimi, Benjamin Recht, et al. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, 2007.
Felix Schur, Parnian Kassraie, Jonas Rothfuss, and Andreas Krause. Lifelong bandit optimization: No prior and regret. In Conference on Uncertainty in Artificial Intelligence, 2023.
12

---

Adish Singla, Hamed Hassani, and Andreas Krause. Learning to interact with learning agents. In AAAI Conference on Artificial Intelligence, 2018.
William R Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 1933.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 1996.
Doniyor Ulmasov, Caroline Baroukh, Benoit Chachuat, Marc Peter Deisenroth, and Ruth Misener. Bayesian optimization with dimension scheduling: Application biological systems. In Computer Aided Chemical Engineering. Elsevier, 2016.
Sara A. van de Geer and Peter Bühhmann. On the conditions used to prove oracle results for the Lasso. Electronic Journal of Statistics, 2009.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press. 2018.
Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. Cambridge university press, 2019.
Julian Zimmert and Tor Lattimore. Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. In Conference on Learning Theory. PMLR, 2022.
13

---

Contents of Appendix
Extended Literature Review
14
Time Uniform Lasso Analysis
15
C Results Exploration
18
C.I ALEXP with Uniform Exploration
20
C.2 Proof of Results on Exploration
20
Proof of Regret Bound
23
D.1 Proof of Model Selection Regret
D.2 Proof of Virtual Regret
30
E Time-Uniform Concentration Inequalities
32
F Experiment Details
34
E1 Hyper-Parameter Tuning Results
34
A
Extended Literature Review
The sparse linear bandit literature considers linear reward functions of the form 0 x. where x E RP however a sub-vector of size is sufficient span the reward function. This be formulated as model selection among M = (?) different linear parametrizations, where each Φb is a d-dimensional feature map. We present the bounds in terms of d and M for coherence with the rest of the text, assuming that M = (p), which is the case when d <
number of important factors. In this Table 2 compares recent work sparse linear bandits based table, the ETC algorithms follow the general format of exploring, performing parameter estimation t ng. and then repeatedly suggesting the same action which maximizes Ô d(x)). Explore- then-(y)rreedy takes a similar approach, however it does not settle on @n.- rather it continues to update the parameter estimate and select æ; arg max 0g ((x). The UCB algorithms iteratively update upper confidence bound, and choose actions which maximize them. The regret bounds in Table 2 are simplified to the terms with largest rate of growth, the reader should check the corresponding papers for rigorous results. Some of the mentioned bounds depend on problem-dependeee CK), which may not be treated as absolute constants and have complicated forms. To indicate such parameters we use in Table 2, following the notation of Hao et al. [2020]. Note that varies across the rows of the table, and is just an indicator for existence of other terms.
parameters (c.g.
Abbasi- Yadkori et al. [2012] use the SEQSEW online regression oracle [Gerchinovitz, 2011] for estimating the parameter vector, together with UCB policy. The regression oracle is exponential weights algorithm, which runs on the squared error loss. This subroutine, and thereby the algorithm proposed by Abbasi- Yadkori et al. [2012] not computationally efficient, and this is believed to be unavoidable. This work considers the data-rich regime and shows R(n) O(VdMn) matching the lower bound Theorem 24.3 Lattimore and Szepesvári [2020].
Abbasi-Yadkori
Carpentier and Munos [2012] assume that the action set Euclidean ball, and that the noise is directly added to the parameter vector, i.c. 8/ x (0 + E,). Roughly put, linear bandits with parameter noise are "easier" to solve than stochastic linear bandits with reward noise, since the noise is scaled proportionally to the features 2; and does less "damage [Chapter 29.3 Lattimore and Szepesvári, 2020]. this setting, Carpentier and Munos [2012] present a (dd/n) regret bound.
Recent work considers contextual linear bandits, where at every step Ar. stochastic finite subset of size K from A. presented the agent. commonly assumed that members of A, are i.i.d., and the sampling distribution is diverse and time- indepeddddenndtt. The diversity assumption is often in the
14

---

form of a restricted eigenvalue condition (Definition 2) on the covariance of the context distribution le.g. in, Kim and Paik, 2019, Bastani and Bayati, 2020]. Li et al. [2022] require a stronger condition which directly assumes that Amin (+,) the minimum eigenvalue of the empirical covariance matrix lower bounded. This generally not true, but may hold with high probability. Hao al. [2020] assume that the action set spans TR We believe that this assumption is the weakest in the literature, and conjecture that it is necessary for model selection. If not met, the agent can not explore in all relevant directions, and may not identify the relevant features. Our diversity assumption is similar to Hao et al. [2020], adapted to our problem setting. Mainly, we consider reward functions which linearly parametrizable, i.e. 0 ((x), oppose to linear rewards, i.e. 0 x.
key distinguishing factor between ALExP and existing work on sparse linear bandit is that ALExP is horizon- -ndeepenenn and does not rely on a forced exploration schedule. As shown on Table 2, majority prior work relies either on an initial exploration stage, the length of which is determined according to [e.g., Carpentier and Munos, 2012, Kim and Paik, 2019, Li et al., 2022, Hao et al., 2020, Jang et al., 2022], or on hand crafted schedule, which is again designed for a specific horizon [Bastani and Bayati, 2020]. Oh et al. [2021], which analyzes K'armed contextual bandits, does not require explicit exploration, and instead imposes restrictive assumptions on the diversity of context distribution, e.g. relaxed symmetry and balanced covariance. Regardless, the regret bounds hold in expectation, and are not uniforr..
Table 2: Overview recent work on high-dimensional Bandits. Parameter 7 shows existence of other problem-deye dependent terms which are not constants, and varies across different rows. The regret bounds are simplified and are nol rigorous.
lAi
data- pour
adup-
selection
action
MS algo
context
action
Regret
exp.
pulicy
assumpt.
EXP4
00
x
Surd emorr
A compact
VdMn, w.h.p.
Poster et
K
/
UCB
Sqrd error
EXP4
Amaa 2 cs.
(May
whhp
VRaME
Carpentier and Munos
00
/
x
UCB
Thresh.
param. moise
d/n, whh.
Explore then Greedy
rKd MY) w.h.p.
Bastani and Bayati
K
x
Lasso
A(E)
Explore
Kim and Paik
K
x
Lasso
x{D) >> Ox
(dvmlog(AAr)) whh.p.
c-Greedy
Oh et al.
k<
v
x
Greedy
Lasso
x(]?) > G.
rdd//looggae expeciation Kiutdjira Vlog ala aZa in expectation
other
K
Aman( > ca
spans R
(ndC (log My whop
Hlo el al.
/
ETC
Lasso
+ is compact
Jang al.
00
/
ЕТC
Thresh.
Hard
AC 11, 1
spans R
(nd) (pd) (/ oin log Mrjus w.h.p.
Greedy or UCB
EXP4
Imi (,) spans R A is compact
log A (n C M)
ALEXP (Ours)
reward est.
w.h.p
B Time Uniform Lasso Analysis
We start by showing that the sum of squared sub-gaussian variables a sub-Gamma process (c.f.
Definition 22).
Lemma 4 (Empirical Process is sub- aub-Gamma). For 2 1, suppose & are a sequence conditionally standard sub- Gaussians adapted to the filtration F, o (E E.). Let E R. and Z, = E -. Define the processes S, == Ei= Z and V, = E1 Ei= of. Then (S.) is lub-Gamma with variance process ( and scale parameter c = max;2114 U4
Proof of Lemma 4. By definition [c.f. Definition 1, Howard et al., 2021], S₁ is sub-Gamma if for each À E [0, 1/c), there exists supermartingale (M)() w.r.t F, such that E Mo and for all t 2 1:
X2 2(1 - ct) V1 < Mc(A)
exp
AS
a.s.
15

---

We show the above holds in equality by proving that the left hand side itself, is supermartingale w.r.t. Fr. We define, (A) Exp(AS,
X2V,/2(1 cA)]. therefore,
A²
22202
E [M < E
exp A 2(1 cλ)
1/-1 + Alru - (1 ct)
1
22
E [M, Fr |R
eexp (eZr [Fa-1] eexp exp
1- cd
22 Dz
M (exp (AZ, [ exp
1- 1-1-ch cλ
Note that Ze is -meesuuulree conditionally centered and conditionally sub-exponential with parameters (v,a) (2, 4) (c.f. Vershynin [2018, Lemma 2.7.6] and Wainwright [2019, Example 2.8)). Therefore, for 1/c.
E [exp (Aux Za) Fi-1] S exp (2X²0)) S exp
cd
where the last inequality holds due to the fact that 0 < 1
cd < 1. Therefore,
(
22
22²x2
E [M]]Fi]] M-- exp
1- exp (- 1 -c- M
for À E [0, 1/ /c), concluding the proof.
We now construct eoff-nommalizing martingale sequence based on f2-norm of the empirical process етror term, and recognize that it is a sub-gamma process. We then employ our curved Bernstein bound Lemma 25 control the boundary. This step will allow to "ignore" the empirical process егrог term later in the lasso analysis.
Lemma (Empirical Process dominated by regularization.). Let
A₁ (v+ 2 1: [((TT
Ex), (tpp:lll////s \./2).
Then, for any 0 S 5 < 1, the event A n Aj happens with probability 5, ifr all 1,
20
5
12
A 2
V (log(2M/6)) + (log log d)) +
(log(2MM6) + (log log d)
V2
V2
Proof of Lemma 5. This proof includes a treatment of the empirical process similar to Lemma B.1 in Kassraie al. [2022], but adapts it to our time-uniform setting. Since &, are zero-mean sub- gaussiann variables, as driven in Lemma 3.1 [Lounici et al., 2011], it holds that
1 t2 E
12 1
E 12 - 1) 2 an,
A5 3t
3t
2 mell
where Sa are sub-gaussian variables with variance proxy 1, scalar es denotes the i-th eigenvalue of L1, /tt with the concatenated vector v, (U1. v2), and
ex2/(400) tr TT D1.i) 2 1., 4
ot.
We apply Lemma 25 to control the probability of event AG by tuning X. Mainly, for AI to happen with probability less than 0/M, Lemma 25 states that the following must hold for all t,
5 max 4 [1 11. 1) wa/M (112)) + 12ws/M /r (11 1l2) max v2
V2llvelzans
(4)
2
121
Recall that w.l.o.g. feature maps are bounded everywhere ( I and rank(0,) S d which allows for the following matrix inequalities,
tr( tr( 2.j)
tr(2., 21,)
o (z:) St
16

---

9 2/1 - tr tr D St
( 22, - Pr 2 ااار F S v
,i, [,ان stvd
Therefore,
| 1 2
T 4.j
1 S Vd,
max e = max
D 1.1l...
t2
121
For Eq. (4) to hold, is suffices that for all 2 1,
X x 2a
12 v2
V 4d (logg2M///)) + (log log d)+) + (log(2MM/)) + (log log d)+). 2v2
Therefore, if D are chosen to satisfy the above inequality, each AÚ happens with probability less than ö/M. Then by applying union bound, A
A5 happens with probability less than
The theorem statement requires that the regularization parameter Ae is chosen such that condition of Lemma 5 is met, and therefore event A happens with probability 1 8. Throughout this proof, which adapts the analysis of Theorem 3.1. Lounici et al. [2011] to the time-uniform setting, condition on A happening, and later incorporate the probability.
Proof of Theorem 3.
Step 1. Let Og be minimizer of L and f be the true coefficients vector, then L(O,; H,, Ax) s C(0; H4, Az). Writing out the loss and re-ordering the inequality we obtain,
M
2 E (., 0) + 2X, 1 ( - 1 s t -0)
Σ (10,1l= - 11000011 ==1
which is often referred to the Basic inequality [Bühlmann and Van De Geer, 2011]. By Cauchy- Schwarz and conditioned on event A,
M S
M Or. 03
e (0. 0)
|| ( ex), exbill2 0.. - -0011-
S
0//12
2
/=1
to both sides, applying the triangle inequality, and recalling from Section that 8 0 for j + j gives
then adding A Σ 0zj_ 0g
(0, - 0) de Σ Ö,. 0/
S 2A, Σ 0n. 0,112
2Ac Σ (100112 -100ma
I 4 0..-
0g.
Since each term on the left hand side positive, then each is also individually smaller than the right hand side, and we obtain,
( - 0) s 42, 22l1Ba.5
0,- -0,-
(5)
100s 0.11 s 531lmns -0,111
(6)
Step 2. Consider a sequence (cI...., .,....), ). where 2.. 2 Ch
then
Ck S k
(kck +
ΣG) GG) 5
Ci
(7)
k
13k
Define Jn (i*) and Jg J') where
= arg max
0 0
]E[M] M] j
17

---

For any J C [M] the complementing set is denoted as J = [M] \ J. For simplicity let Cj =
0.. 0/ and let =(k) denote the index of the k-th largest element of fer j E Jf}. By
definition of J2 we have,
Cier
C.)
Σ AE
025
0j 1 = Σ
Σ
k2
A m(KjEji
K
MR)EJJ
1
16
c
Σ
S
96g.
k>1
x(KjEJ}
s 5 + -9) = Σ
Ori 0, 1/12
JEJ2
which, in turn, gives
M
0
Σ
0.j 0 S
10
Or.
(8)
JEJ2
Step On the other hand, due to (6), and by definition of J2 it also holds that
Σ
0. 0
33
Σ
0.. 0,
JEJS
JEJ2
From the theorem assumptions and Definition 2, we know that there exists 1o(#,,, 2), therefore by Definition 2, the feature matrix 4, satisfies,
Σ 0 0 jEJ2
1 tk² (k;
( 8) 00.g. 0,.
2
2
4h
4),,
Σ JEJ
0.. 0
R² (2 2)
i 2)
From here, by applying (8) we get,
4 1010
@ 0
S
x² ( 2)
If Xe are chosen according to Lemma event A and, in turn, the inequality above hold with probability greater than - 6.
C Results on Exploration
In this section present lower-bounds on the eigenvalues of the covariance matrix 4 D, ; it later used in our regret analysis. In particular, we show that the feature matrix 4, satisfies the restricted eigenvalue condition (Definition 2) required for valid Lasso confidence set (Theorem 3), and calculate lower bound on R( ((, 2). The lower bound later used by Lemma 19 and Lemma 20 develop the model selection regret. We show this bound in three steps.
Equivalent to Definition 2, we write x( ((2,, 8) = infoes, 2/bb2/// /t where
E, {b E (R)()) Eeeu [1byll2 Eşe, [lby v ESes b6 1 st. J M) M Ml
(9)
For simplicity notation, we further define
R(A,s) == min D Ab.
(10)
bEz.
since Ri 110 (1b
Step I. Consider the exploratory steps at which a; = 1. Let tr.t be a sub-matrix of o where only from exploratory steps included. Note that d IR XdM is random matrix, where the number of rows t' are also random. We show that x²(2,,, s) is lower bounded by x² ( s).
18

---

Lemma 6. Suppose Tn has t' rows. Then,
(0 2 7 (.)
Proof of Lemma 6. Let w ) T (xt) RdMxdM for all t == I..... n. Note that (p(() is
positive semi-definite by construction. We have,
|
b
(1)
6
Σ TT
SET.
SET=
where the set T contains the indices of the exploratory steps at which the action is selected according π. Therefore,
16 (B), s)
min bEE,
min beE,
b (
1
Σ (
.ET
Σ b b
min- DEE,
SET;
where the last inequality holds due to (b()) being PSD. Then we have,
1 ( SET+
Tx b
22 s) 2 min TT
vils)
1 (2
DEE,
While the number of rows of क.. a random variable, we continue to condition on the event that & has t' rows, and investigate the distribution of its restricted eigenvalues.
Step II. The restricted eigenvalues the exploratory submatrix are well bounded away from zero
Lemma 7. Let be the solution (2), and E N. Suppose xx,t has t' rows. Then for all 5 > 0,
P
VV' Pve
x² (2 (..,,))) 2 8)
80s Vlog(2Md/0) + (log log 41')+ 2 1 - V
where Σ- E (T, Φ) Ex ((x))))))))))))() (x)
and i is defined in (10).
Step III. Remains to combine the two above lemmas and incorporate high probability bound on L',
showing that is close to E 7s- Lemma 8. There exist absolute constants Cz Cl2 which satisfy.
Vt 2211 1: 12 (2,,) 2 C,R(E,2)t C2t -5/6 5/8 Vlog(Md/8) + (loglog log t)+) 2 1 - -
i = O(t-11())) 1/4). Let π be the solution to (2), then it further holds that
P (1121: (2),, 2) C. CiCmint -5/
(log log ()+
-
The regret analysis of Hao et al. [2020] also relies on connecting k(Dr, to Ciiu- and for this, they use Theorem 2.4 of Javanmard and Montanari [2014]. This theorem states that there exists problem-dependent constant C₁ for which x>2 s) 2 C,Cmin with high probability, if 2 no and roughly 74 O n log M). We highlight that Lemma 8, presents a lower-bound which holds for all f 2 1, however this comes at the cost of getting a looser lower bound than the result of Javanmard and Montanari [2014] for the larger time steps t. In fact, due to the sub-optimal dependency of Lemma on f, we later obtain sub-optimal dependency on the horizon for the case when n > M. unclear to if this rate can be improved without assuming knowledge of n, that 2 ni-
For the last lemma in this section we show that the empirical sub-matrices tt,, are also bounded away from zero. This will be required later to prove Lemma 15.
19

---

Lemma (Base Model Amin Bound), Assume т is the maximizer of Eq. (2). Then, with probability greater than 1 6. simultaneously for all 1..... M and 1,
Imin($, 2t.)) 2 Ci C2t 3/8 /log//ll + (log log
i = O(t
C.1 ALEXP with Uniform Exploration
We presented our main regret bound (Theorem I) in terms of Cmiu- which only depends properties of the feature maps and the action domain. We give a lower-bound on Cuin for a toy scenario which corresponds to the problem of linear feature selection over convex action sets.
Proposition 10 (Invertible Features). Suppose ((x) = Ax : TR + Rd is an invertible linear map, and E Rdd a convex body. Then,
Amnia (A) >
Cmin
X (i)ax(T)
where T is the transformation which maps X' to an isotropic body.
The lower-bound of Proposition 10 is achieved by simply exploring via π = Uni Inspired by Schur et al. [2023, Lemma E.13], we show that even for non-convex action domains and orthogonal feature maps, the uniform exploration yields a constant sower-bound on restricted eigenvalues.
Proposition 11 (Orthonormal Features). Suppose Φj X - R are chosen from an orthogonal basis of (2), and satisfy (| /Vo(X)) 2 Then there exist absolute constants C1 and C2 for which the exploration distribution π = (A' satisfies
P 2 1: (2,,, 1/4 C2t -5/8
5/8 Vlog(Md/0)- + (log (loglogt) t)++ 2 1-6.
The d 1 condition is met without loss generality, by splitting the higher dimensional feature base features, which will increase M. Moreover, the orthonormality
maps and introducing condition is met by orthogonalizing and re-scaling the feature maps. Basis functions such as Legendre polynomials and Fourier features [Rahimi al., 2007] satisfy these conditions.
By invoking Proposition 1, instead of Lemma the proof Theorem 1, we obtain the regret of ALEXP with uniform exploration.
Corollary 12 (ALExP with Uniform Exploration). Ler å (0, 1]. Suppose Φj : X - R are chosen from an orthogonal basis of I (X), and satisfy (| /Vo(XX)) Z 1. Assume the oracle agent employs UCB a Greedy policy, laid out in Section 5. Choose n) O(1/ViC(M, 5, d)) and Tt Ott-1(()) 1/4) and X OC((M,6 8, d)/ Vt), then ALEXP with uniform exploration attains the regret
Un)
R(n) = 0 Bn2// + VRC log M + B² Vn B n (log log nB²) + log (1/8))
+ (n3/4 + logn) 5, + 5/8 dlog + log (1/5) B2)
with probability greater than 1 - 5, simultaneously for all n 2 1. Here,
C(M,8,d) = ( (V1+ 1+ Vd (log(M/6) - (log +) (log(M/5) + (log log d)++)
C.2 Proof of Results on Exploration
As an intermediate step, we consider the restricted eigenvalue property of the empirical covariance matrix. Given f' samples, the empirical estimate of Σ is
Σ = Σ s=1
(11)
where æ, are sampled according to m. We show that every entry of E.t is close to the corresponding entry in Σ, and later use it in the proofs of eigenvalue lemmas.
20

---

Lemma 13 (Anytime Bound for The Entries of Empirical Covariance Matrix), Let Ey be the empirical covariance matrix corresponding [[,, Φ) given t' samples. Then.
5
3t' doo (E, 2
V(log 4t' + log(2.Md/6)) 2 v
where do (A, (), = m [ Biss
Proof of Lemma 13. We show the element- convergence of Σ to E, for the (i.j) entry where 2.j 1,... dM. Consider the random sequence X, Σnj (I (xx)) We show that
XI,..., Xn satisfies conditions of Lemma 26. We first observe that
E[X, (XXx|XX:s-111 EX,- = J) ( =0
since by definition Egg Exwar (x:) Φ (a)). Moreover, we have normalized features |}(( S 1, therefore, each entry (-)))((()) is also bounded, yielding |X&|| S 2. Then Lemma 26 implies that for all 8 >
P
3t'
E
X,
V V (1og log 4t")+ + log(2/8)) -
F
Setting 8 = (ddM) and taking a union bound over indices concludes the proof.
We are now ready present the proof's to the lemmas in Appendix C.
Proof of Lemma 7. By (11) we have En Be and thereby
(2 8) min 8 Et = s))
bEE.
Inspired by Lemma 10.1 in van de Geer and Bühlmann [2009], we show that element-wiss closeness of matrices E and Σn (c.f. Lemma 13) implies closeness in R:
| (e,,)), K(E, s)
k R(Ee s) R(E,
k EE Σ
s min do (E, Eee ||61 beE,
where the last line holds due to Hölder's. Moreover, since b E E.. for any J c [dM] where |/| S additionally holds that |bll|2 S and
|bb|] s (1 3)|bb>l1 S <4/s|bbull S 4/8
which gives,
,T, 2 R(E,s) 16sdac E.))
Therefore by Lemma 13,
80s
(T. 2 R(
((log log 48') + (og(2M))))
(12)
/r
with probability greater than 1 8, simultancously for all t' 2 1.
Proof of Lemma 8. In Lemma 6 showed that
(2,, - (2
where L' indicates the number of rows in the exploratory sub-matrix of +, Recall that L' = Σi= where a, are i..d Bernoulli random variables with success probability of %. Due Lemma 24,
PP (vt 2 1: It' - r s A 2 6/2
(13)
21

---

where
5
(log log +)+ + log(8/6)
A,
r
2
t
Due to Lemma 7, with probability greater than - 6/2 the following holds for all 2 1
t'
160
K (2,, 2)
x(
(log log 46'+ log (og(4M)/0)
r A ((,,)) 160
To A. ta
V (loglog (4r, + A.)) + log(4Md/6)
where the second inequality holds with probability 1- 6, by incorporating (13) and taking union bound. For the rest of the proof and to keep the calculations simple, we ignore the values of the absolute constants. We use the notation g(() o({(t) show that f(t) grows much faster than g()). More formally, for every constant there exists 4o. where 7() I c(f(() for all / 2 lo- Since T ((s00(ss10))) there exists C' such that I; = C+3/4, then it is straightforward to observe that there exists absolute constants C, which satisfy,
x² ( (1--1/((E,2)) 5/ ((,3
Vlog () 18g(8/6)
2
- 52t log(Md/8)) + (log log t)+ 55-5/8 Vlog(Md/6) (log log f)+
((E Öst 5/8 Vog( (Md/8) + (log log t)+
The last inequality holds since 3/2 /log logt 5/8 /log log The above chain of inequali- ties imply that there exist absolute constants C₁ C2, for which
P v 2 1: ( 2 ()
C2t 5/8 Vlg(MMd/5) (log log log f)+
2 1 11-6. 8.
If is chosen according (2), then (EE, 2) Cmin yielding the lemma's 's second argument.
Proof of Lemma 9, Fix j E (l...., M. and construct the set
Br = Rdd {0} = (b,,.... b,),, s.t. b, R 1,,1,1112 s and Vj' fj: by = =0]
Note that Ei.j C a.. Therefore,
inf b inf bE
1,bbll2 Vtr(Dr,,). s).
DEE,
Moreover, by construction of E we have for all b E Ei, that T, = Di therefore,
| inf bE
inf
|| b Amin ( Dr.).
by E
From the above equations we conclude that Ami 2 Therefore, using Lemma 8 we obtain that there exists Cj C2 such that
M. 1, Pzy)) ) 2 tx² s). for all j = I,..,,M.
P 1 M: Amin ( ( (t.)) 2 CiCmin - 3/8 Mog( (log logt)+) 2 1
Proof of Proposition 10. Since X' is a convex body, then there exists an invertible map T, such that (X)) is an isotropic body [e.g. Proposition 1.1.1., Giannopoulos, 2003]. Then by definition, X ~ Uni((T(A)) is an isotropic distribution and Cov(X) = Ia [e.g., c.f. Chapter 3.3.5 Vershynin, 2018]. Since @ is linear and invertible, it may be written is as ((x) Ax, where an invertible matrix. Therefore,
E( Φ) = Cov (xx))) = A Cov(X)A= A Cov (T- A = AT (T 1TA
As for the minimum eigenvalue, suppose Rd and ||o||| then
Cmin 2 Amin (E(=, Φ)) > x A (T 1)2 Av AvllzAAmin (T (7-2) 2)= ||Au|/2
Amin (A)
2
22 (T)
X2 X2 (T)
22

---

Proof of Proposition 11. By the assumption of the proposition, for all i E M
0),, = Ex-n (x()) = Vol(X) / ((()))p(x) 2 1
and for all i i
[[ 6)lss Bexr ( = Vol(2) / )(())))())))(()= = 0
We = E(T, Φ). For any b IR Md where ||6|| - 1,
b b Eb
Σ bj b, = Σ b Σ E; +
bj Ei WE(M)]
E
[E([M]
iE[M]
Σ
b.
Di,,,
kE[M]
Σ
|6
112 2 1.
iE[M]
Which implies,
R( s) = min T Σか 2 1.
bc _
By Lemma 8, there exist absolute constants C1 and C2 for which,
P P (2,, ((2,))C1t-11 - C2t 5/8 Vlog(Ad/0)) (log loglo)t)+) t)+
2 - 8.
concluding the proof.
D Proof of Regret Bound
Theorem 14 (Anytime Regret, Formal). Ler å E [0, and π be the maximizer of (2). Assume the oracle agent employs UCB or Greedy policy, laid out Section 5. Suppose nt OC C/M 8, d)) and "t 1(4-1/4) and X = OCC(M, 5, 1/2), then exists absolute constants .i...., Co which ALExP attains the regret
R(n) & Bn + C2vnC
min C(M, log M
C2BºC VT C BB) log(1/8))
C3 (1 C Cmin -3/8
3/8 Mlg(Md/0) + (log log
log (C(M,
n//8
x Bn + (n3/4 +
/llogn + log(1/6) + B
Cmin
Vmmin
with probability greater than 6, simultaneouslyy for all n 2 Here,
C(M, 5, = Caay 1 V (log(M/8) (log log d)+) + (log(M/8) (log log d)
Our main regret bound is immediate corollary of Lemma 15 and Lemma 16, considering the regret decomposition (3).
Lemma 15 (Virtual Regret of the Oracle). Let 8 E (0 and > 0. Assume the oracle agent employs UCB Greedy policy, laid out in Section 5. If O(1//1) there exists an absolute constant C1 for which with probability greater than 5, simultaneously for all n
Ry- (n)
8/8 Vani (1 (1+n 3/8
min Vlog(Md/5) (aaMdd/))(llllooo)) (loglogn):
x v o2d n +1) + 20 log(1/8) + ÂB²
23

---

Lemma 16 (Any-Time Medel-Selection Regret, Formal), Ler ő E (0, 1] and π be the maximizer of (2). Suppose Tn ( (M, 6, d)) and " = (t-11/4) and X = O(C(M, 6, d)/ Vt), then exists absolute constants C. for which ALExP attains the model selection regret
J) S C/ + C2vnCC
min C(M, 8, d) log M
Cy v C4Byn (flgg log BB²)+ log(1/6))
+Cs (GnBB/ (n3/4
log
Cmin C()
(1 (1+ + Cinn 3/8
1 log(Md/0)) lloglog n)++
with probability greater than simultaneously for all n Here,
C(M, 6, = Cao C v Vd + (log log d)+) + (log(M/b) + (log log d)+
D.1 Proof of Model Selection Regret
Our technique for bounding the model selection regret relies on a classic horizon-independderr analysis of the exponential weights algorithm, presented Lemma 17.
Lemma 17 (Anytime Exponential Weights Guarantee). Assume netts S 1 for all S S M and t 2 1. If the sequence (N1)221 is non-increasing, then for all n. 2 1,
log M
Σ t=1
Σ t=1
1 Σ P
nn
1=1
for any arm E [M].
Proof of Lemma 17. Define R t steps. We rewrite for a fixed
E Ei=1 fs. to be the expected cumulative reward of agent after
M
Pik
Po =
Pe.k
Σ 1=1
E Exng [a
(14)
1=1
We focus single term in the second sum. For any t, have
-e [fa]]
log(exp(-BB) (-asgp
T fr.l)) Log(exp(-BB-)) (n
1)
1 log(exp(-EE-n, (tce. (r,)))
?/t
1
log (engg
(m)
(15)
The
The inner expectation is over j. while the outer one over and therefore has no effect. Moreover,
1
log Erng [aa] + mef))))
log (exp(-ne Byrg (e exp(neft,))
7
7)
log Erwg 7, B, (rr)))
7)
log Bingi exp(1
(16)
7h
where again, the expectation can be reintroduced get the last line. Combining (15) and (16),
- -Ej~g [ log Bing, exp( exp(-mpEj-pp E. [fr.g] | + m)Fts) log Bing, exp(1eft.)
(17)
7}
This transformation is at the core of many exponential weight proofs [Bubeck et al., 2012, Lattimore and Szepesvári, 2020]. We first bound the first term in (17):
log Ergg exp(-nEE,-w [Fra] + mefr.) log Bing exp(n)ft.. neEEna
24

---

Bingi exp(neft.))
m/ jmgq Pt.j
Bing (exp(1xft,,) - 1 7T
1 Es (1111
(18)
where in (I) we use the fact that log(2) $ - and in (II) we use the fact that for x S 1, we have exp(x) I +1+2 +xxx- x², and hence exp(x:) the potential argument in Bubeck et al. [2012], but with slightly different potential function. We expand the definition of gr:
x². For the second term in (17), we will mirror
Σ i= exp(n
log Eswg. exp(nefe.)
log
7)t
Σ 1i=1 exp(1) Ro-
1 M
1
1
1
log
exp(m: + log ex
Σ M
Rc-
1}
M
11.
1=1
+1(1)) J
(19)
where we define Je(n) = - log 1/4 Σ ex.()
We also define F((n) =
log M ΣM exp(-n)Br,)) We observe the relation J(n) = F(-n). From this, it follows that for F S 0, by the argument in Bubeck et al. [2012, Theorem 3.1] that shows F'(n) 2 0 for any 1).
any 1), we have (n) =
Putting together the pieces Now, we can bound (17) by inputing (18) and (19):
- -Ejagi [F.g] S Bing [nerdd] + J+(())) It-1(1))
With this, rewrite (14)
Σ PaR Σ Eg-al -
EPE FEN + Σ [not. + Σ Je(n)) (=+)
(20)
Potential manipulation We can do Abel transformation the of potentials in (20), namely obtaining
n-1
Je(ne) - 11 = Σ (J((n) (e( + Jn (m)))
where we used that (n) = 0. We know J'(n) S 0 and so J is decreasing and since Mh+1 S Tho we
have (11++1) 2 ((w) (Je()e) Je(ne+1)) < 0, that for any fixed
a
log(M)
1 Ta
log Σ Eoxp(in(nnn))
J(n))) J=-1(1)) s (m()))
nn
log(M)
1
log (eop(nRnnni))
Thn
T/o
log(M)
Pt.k
(21)
7n
where (x) follows because exp is positive and log is decreasing (notice that drop M terms from the sum). Plugging (21) into (20), we obtain
Σ fr.k
Σ E Ejagi t=1
fr.
Ringe
[need + Σ Je(me)
J
t=1
E. Kinge [nr + (og(M)
Pr. +
Pzk
nn
1=1
[ner?d] + log(M)
Eingg
25

---

M (M)
11t
I t.j +
1/2
We expressed in Section 5.2, that the model selection regret of ALEXP, is closely tied to the bias and variance of the reward estimates fz.j. The following lemma formalizes this claim.
Lemma 18. (Anytime Generic regret bound) If me is picked such that nott, I for all 1 S & M and 1 almost surely, then Algorithm satisfies with probability greater than 1 - 26/3, that simultaneously for all n 21
log
M
M
R(n, 1) 2B
Σ 1=1
1/t
n 6
+
Σ 3=1
g(swes))
7n
1=1
10B n ((log log n nB² )+ + log (12/5)
where Wt, = |r, Pe.al.
Proof of Lemma 18. Let denote the Bernoulli random variable that is equal to if at step t we select actions according to π and otherwise. At each step t with a; ALEXP accumulates a regret of at most 2B, since |10|| I B and |](())] < 1. We can decompose the regret as,
R(n, i) S Σ
2 + (r,, (1) - aa)
1=1
For the first term, by Lemma 24, we have
5 V (logllgg)) + log(4/61))
2 at S 2B
Σ
i +
simultancously for all n 2 1. with probability 1 - ò1. Let = EØ= M second term of the regret as follows,
G.g We may re-write the
n
a
Σ (1 as) res (rea- rz) s Σ (1 ar) (re. Pr,s) + (Pr.z - (t) + (fr - -ro]
rr)
Σ wi, (1 on) (Pp ft) (fr ri)
We bound the second term on the right hand side, using Lemma 17
(frs - -a) 5 log M
Σ (1-a)) A.) S
Σ
Σ 1h
1/n.
1=1
1=1
1=1
As for the third term,
(1- Σ u.f r1) ar)
Σ
(
-ras + +ris)= r't
j=1
M
M
Wir + (1- ac) Ti Σ j=1
remains to bound the deviation term. For all that satisfy o, = the action/model is selected according to Jt.j. therefore the conditional expectation of r2 can be written as
EE 1
Tx.
26

---

The sequence X, = 7t Bi-- is martingale difference sequence adapted to the history H,, since for every 2
R X [r: E H = 0.
Since r I B. then Xt S 2B almost surely, which allows for an application of anytime Azuma- Hoeffding (Lemma 26):
M
5B
P
Em
T1
ges
2
Vn (loglognB*)+ log(2/62)) s 62
2
1=1
which, in turn, leads us to
M
at)
r2
1=1
1=1
w.i.p.
5B
S
V ((log log nB²) + log(2/6)))
2
simultaneously for all n 2 1. We set 61 82 8/3, take a union bound and put the terms together obtaining,
Σ t=1
Vt +
log M
a
Σ
(we +
Σ
Tm
j=1
5B
+
Vn n (log log + log(6/5)) + 5B / n)+ + log(12/6)
2
upper bound the sum last two terms to conclude the proof.
The next two lemmas bound the bias and variance terms which appear in Lemma 18.
Lemma 19 (Anytime Bound on the Bias Term). If the regularization parameter of Lasso is chosen at every step
20
5 V (log(2M// (log log d)+)
12
A Vi
(log(2M/8) (log log d)+
V2
V2
and 71 O( ((t--// 1/4), then with probability greater than 8, simultaneously for all n 2
Σ Pr, r2,ll < n/ 3/ 1. min CM,,,) (1 + 1n+n3/ 3/8 C.b Vlo(Md/jo)) + (log log
where
Vd (log(M/6) (log log d)+) + (log(M/6) + (log log d)+)
and an absolute constant.
Proof of Lemma 19. By the definition of the expected reward and its estimate,
Σ / (r(x) - f.(x))
2 Pr. - neal
(r(x)) F. (z)
/ 0 0. 0.11 0 dppez.)1
1=
hdd
Σ 0, 11
dp(+1,(0)) = Σ 0
27

---

We highlight that the Cauchy-Schwarz step may be refined. By further assuming that g,. is bounded
away from zero (also called the beta-min condition [Bühlmann and Van De Geer, 2011]) one can
show that A 02 is 2-sparse vector. This will then allow one to only rely on boundedness of ||
rather than ||>||| derive the last inequality, and relax our assumption of [ S ( S for all [M] From Theorem 3, with probability greater than 8/2 simultaneously for all n 2 1,
Fr. rra S
4V10A
C(M, 8, d) Σ
1 (0, 2)
x
where,
12
Č(M, d, = So 1+
V (log(4M/6) + (log log +)
+)+ + (log(4M/6) + (log log d)+).
v2
v2
From Lemma 8, there exist absolute constants C₁ C2 for which,
P P(12 (2,,, 2) 2 Ci Cmiit 1/44 Cat C/8-6/8 / Vlog(Md/0) + (loglog()+ 2 1
Using Taylor approximation we observe that, I---T = 1 + + = O 0(1+x=1) Therefore, these exists absolute constant C3, C4. for which with probability greater than 1 - 5 for all 2 1
5(M,5,d) ((2,2))VE
6(M,6,d) VE
C.0mint-1/4 - C21 Vlogi Md/8) (log log 1)+
Ö(M,8.d) O's
C2t-5/8 5/8 log(Md/0) + (log log t)+
Vt
Cmint-1/4
CiCmint 11/4 1/4
C,
3/88
1 C4
-v log(Md/0)) (log log t)+
Cmin
Cinn
CM, 8, 8,))%/
n3/8
(+ C2 Cmin
Vlog(Md/8) + (log log n))+
Cuin
Lemma 20 (Anytime Bound on Variance Term). Suppose is chosen according to Lemma 19. N) (t-1//4 and n OCuuint 1-12 (M(,, d)). Then with probability greater than 5, the following holds simultaneously for all n 2 1 and t
4V10A,
PLj S
+ +B, x2
Vj [M]
1
C2Bn (1 (1+
n -3/8
Th
f 5
Cmin V B2
v log(MMd8)) + (log log n1)
Cmin
log
1+ n 3//8
+ C(M, 5, d)
Tog Mog(Md/8) + (log logn)+
Cmin
Cuin
where C₁ absolute constants, and C(M, 0,d) defined in Lemma 19, up constant factors.
Proof of Lemma 20. We start by upper bounding fr.jj For all and t it holds that:
frj = 1 (0.,
< [8. /
< 0. s B + (0. 00/1
x
since |00|, B. To bound the last term, we only need to invoke Theorem 3, which, in turn, will simultaneously bound ft.j for all j = 1....... .M:
4
1011
P vt
Vj
[M
+B
2215
2
Cx
28

---

Which implies for all t 2 1,
2
4VI0Ar
160A
8B 8BVI
+
Σ R. C,,t
+ B² +
For the last term, similar to the proof of Lemma 19 we have,
8BV10A
CnB (1+
n/88/8
T
(od/)) + (log log n)+
Cmin
for some absolute constant C₁.
We treat the squared term similarly,
160X
Cs
(1+C, 3/88
71t
S 6(M,6,d)
Vlog(Md/0) + (log log 1)+
1Cmin
Cinn
t=1
C3 log
1 C4 33/8
S CCM,, d)
Vlog(Md/6) (log log n)+
Cuin
Cmin
Note that the last inequality is not tight. This term will not be fastest growing term in the regret, so we have little motivation to bound it tightly. Therefore,
M
26g Ri S C vn + C2B 1/4 (1+ n -3/8
Vlog(M (oogMM//)) + (log log 1)+
Cmin
log n
-3/8
C(M,6,d)
Cuin (1+ Ca
Vlog(Md/o) - (log loggogg),
Cmin
where C₁ are absolute constants.
Proof of Lemma 16. We start by conditioning on the event E that is picked such that n S for all and j 1,..., M. Then by application of Lemma 18 we get with probability greater than 25/3.
log M
i(n,i) < 2B Σ i'
1/t
+
(ur
Σ groWe.)) J=1
T/n
10B ((log log BB2) log((2/5))
We invoke Lemma 19 and Lemma 20 with 8 + 8/3 take union bound, to bound the variance and Wi,i terms as well. These lemmas require one application of Theorem to hold simultancously and no additional union bound is required between them, since the randomness comes only from the confidence interval over 0..
log M Th
R(n, 1) Bn
n 3/88
+ CCin V C/B 1
Vlog(M/00) + (log log n)+
Cmin
log
n 3388
C(M,
Vlog(Md/8) (log log n)+
Cmin
Ciin
n -3/8 3/8
+ n 3/ C(M, 8, 1+
log(Md/8)) + (loglog n)+
Cmin
+ 10B /n (log nBgg log(2))))1
log(12/8))
with probability greater than 1 - 6, conditioned on event E. Assuming that event E happens with probability 1 1 25, let B = (6,,, M, d, n, B, Cui)) denote the right-hand-side of the regret inequality above.
29

---

By the chain rule we may write,
PP ((Ree(n, i) - B))
2 P [(n, i) < 1I E [x],] E [M] mhits S $ (A1 E [n], e [M] :png $
2 P [R(n,i) i) S vt [m],j E [M] nope s $ (1 (1-20)
2 (1-5) - 26) 2 36.
remains to verify that event E is met with probability (C (MM,, d)), and that from Lemma 8 with probability 1 ö,
28.
Recall that m
Cmin
CiCmint /4 - C2t 1/8 log(Md/8) + (log l)g (VI,
x² ( 2)
8,,
4vI0A,
Therefore, from Lemma 20, there exists C, such that 7/t - C d) satisfying.
P 1,j [M] nett, S 1) - 24
The proof is then finished by setting < 35 (and updating the absolute constants).
D.2 Proof of Virtual Regret Proposition 21, For any fixed > 0, there exists an absolute constant C₁ such that
Vt 1: B - 0j 0,111 S w(t, 6,(,, 2
where
wll, 8, CiV
odd d'd
Ad
(
+1 +20 log(1/0)+ü8²
(1 1 (ooii Vlogoooo//// + (log log ()+
A Ammn 13/4
Moreover, for ue.5-()) (.) = 05. 25 (-)
+ 5t,
P(# 1, x X' :(x) S us (x)) ) 2 1 8.
Proof of Proposition 21. Define for convenience Vi T.. Di λy We first observe that
A... ( TTy
We can apply results from Abbasi- Yadkori et al. [201] 1] to get an anytime-valid confidence set. Their Theorem asserts that with probability 6, for all > have?
| 05
| v.
< B
where
det(Vv)2/2
= 200
B, = 20
+ ÁB²
det ()t((/))
Clearly, V, 2 Amin (n)n(1)44, and therefore with high probability,
| - V Amin (Vi)
3
uniformly over time. Our assumption is that [zx)(x)) S 1, and hence, denoting by ia the eigenvalues of Ve, the geometric-aritee arithmetic mean inequality yields
det VV) < II v < (+1race(v))
Thhii theorem statement slightly different, but they prove the stronger version state below.
30

---

Given that
traco(Vi)
(0 (x)) + i s Äd
i= s=1
can conclude that
(1/d+ X)1/2
Be s 202
AB² do² log
Àd +1
-2222100 log(1/))) ÅB²
\d/28
We note that
Amin (Vi) Amin (,,,, pt.)) X.
Then due Lemma 9, there exist absolute constants C1 and C2 such that for all f 1,
Amin (V)) À + C1 - C2t Sases///oog(o /log(M/8)) + (log log t)+
therefore, there exists C3 and C4 such that
Auniu (V))
V A C1 C.Cminn3/4
C2t3/8 Vlog Md/5) (log log t)+
C3
+3/8 /ologMM/// (M//)) + (log log t)+
1+
Vx+ + C.Cmin 13/4
À + C C//nn
C1
C 3/8 Vlo((Md/5) + (log log l)+
Vx + C1Cmin t3/4
min
with high probability for all 2 1. Setting
8 8, = -C3 dloog( +20 log! 118))
(1 C--1--31+ (log(Md/)) + (log log t)
t-/mingt/4
where Cs an absolute constant concludes the parametric confidence bound. The upper confidence bound then simply follows: for any E X'
r(w) BT. Φz (x) = (0)- B..j ())(()) < 0,- -r... ||,)) dd)
where the last inequality holds with high probability simultaneously for all / 2 1.
Proof of Lemma 15. Using Proposition 21 and the Cauchy-Schwarz inequality we obtain,
Rz- (n) = Σ r(x*) r((()))
1=1
Σ r(x*) - -A,(x*) + +x((x)) - (i + f.( - r(
0, 0 (110 (2))2 [1b,
+ +f((x") f (wt.))
< Σ (lt, 8, d) (11b( )ll + ((.,))))))l + fx(()))
(r(ā..))
with probability 1 - 8. If the agent selects actions greedily, then f, (x*) f )), and
R (n) S Σ wit d) (11b, (x (x"))²z + (
2w(t, 8, d)
since the feature map is normalized to satisfy |()(()| < 1. If the agent selects actions optimistically according to the upper confidence bound of Proposition 21, then
(( w(t 6, ( 2 fx(x*) + w(t, 6, (x"))
31

---

which implies
fa(at") - (((())))))
(1,, 8, (2)()()()=)))
and therefore,
Rí. S _ 2, ( - Σ 2w(1, 6,
Then due to Proposition 21, with probability greater than - 6, simultancously for all n 2 1,
dddlog [aa +12 1og(1/6)-
(t, 6, d) S Σ CiV
1 8/8 log( (2 + (log log t)+
A+Cmin
S 1/8
oddlog(
Ad
22d (o)
=3 1 Cmin 8
loog( (d (log log vz)+
Gmin
concluding the proof.
E
Time-Uniform Concentration Inequalities
We will make use of the elegant concentration results in Howard et [2021], which analyzes the boundary of sub- nab-Gamma processes.
Definition 22 (Sub-Gamma process). Let (S.) and (V+) be real-valued processes adapted to (F with So Vo 0 and Vú non-negative. We say that S, is sub-Gamma if for À E [0, 1/c),
there exists supermartingale (A)) w.r.t. Fr, such that My = 1 and for all t 2 1:
X 2(1 cA)
exp(AS,
V1 s M(()
a.s.
The following is a special case of Theorem in Howard al. [2021]. We have simplified it by making a few straightforward choices for the parameters used originally by Howard et al. [2021]. which will yield an casier-to-use bound in our scenario.
Proposition 23 (Curved Boundary of Sub-Gamma Processes). Let (Si)ozo be sub- GammGamma with scale parameter and variance process (Vi) Define the boundary
(2)) + 3c (loglogee)) + log
(2) a )2))
(v) = 2/ maxfv, 13 (log log eu)+ ev) + log
for > 0, where (x)+ max(0, x). Then,
P(t:: : S. (V.)) S
Proof of Proposition 23, Suppose g(-) denotes the Riemann zeta function. Theorem in Howard al. [2021] states that if (St)20 is sub-Gamma process with variance process (Vi)22 then the boundary
)) ck22 sooglog (nw') + log a log"
((s)
{(s) a log" n ))
Sa()') kayo
log log (nv') + log
satisfies,
P(3:: S 2 S. (max 1))) a
where
A1 1/ + -1/4
1/4
and
k2 (vn 1)/2
2
and 8, 2 1. Choosing 2 and
obtain ((2) n²/6 2. Furthermore, we have
k < _/4 and Kig 5 Then if o' 2 1 (which we will enforce by the construction v' = max(1, (1, v)), we compute
((s)
< 2(log log ev') + + log (2)
s log log (17²) ) + log a log"
32

---

Therefore, we can upper bound (using our bounds on k1.
Sa(1') - 2\
5 or (log log ev')+ + log (2) (2)) + 3c (1og (loglogeo'), log
(1ogglogerr)
2
Now, since the boundary is given by (maax(( 1)) and o' max(v, 1) 2 1 deduce that
Ba (v) - 2 [a lf (1oggogg (loglogev)) ev)+ + log ( )) + 3e (loglogeo)+ + +og
_
2
is an any-time valid boundary.
Lemma 24 Cimee-nnformm Two-sided Bernoulli). Let XI....,
X.... X.. be a martingale sequence
of Bernoulli random variables with conditional mean "/s. Then for all > 0,
5 Ex. Te) 2 2 ((og logt)+ log(4/6)) 2
3t:
Proof of Lemma 24. By Proposition 23, know that if S₁ is Lub-Gamma with variance process Vi and scale parameter e, then
IP (3 S. 2 Ba(V,))
where
(b(u)= max 2) (log log ev)+ + 1og((/0)) 3c ((log ev)))+ 1og(2/6))
By Howard et al. [2020]. we know that if f is Bermoulli sequence, then S; = E.= (X, -e)) sub-Gamma with variance process V, and scale parameter e (hence, sub- Guu-Saasssin)..... This implies,
5 / ((log log +)+ + log(2/8)) 6 2
Et: Ex. -))-n))
The above arguments also holds for the sequence Z, -x,. Then taking a union bound and adjusting 5 +- 8/2 concludes the proof.
n
Lemma 25 (Time-Uniform Bernstein). Let (E:);²) be a sequence of conditionally standard sub- gaussian variables, where each &, is Fi-1 = off measurable. Then, for v, IR and
8 E 10
5 2\ max {1, 4114 ws (s((wee ((wa(()))ll))) max vi (21
31:
Σ ( - 1)0 2
S 8
where, Di = (Vi,..., vt) E RR' and ws( = (log log(4e22)) ?)) log(2/6).
Proof of Lemma 25. From Lemma 4, S, Ei= (5 1)u; is sub-Gamma with variance process 1 of and = 4 max By Proposition 23, we know that if S; is sub-Gamma with V; = 4 E
variance process V, and scale parameter c, then
IP (3:: S. 2 BB(V))) < 6,
where
BB(v)= = V //mx(111) 1} (llog eo) + log(2/6)) + 3c (lloglogev) + log(2/8))
Lemma 26 (Time-Uniform Azuma-Hoeficn Axuma-Hoeffding) Let X1, X..... X,, be martingale difference sequence such that [X4] < B for all >> almost surely. Then for all > 0,
5B
P
:
X. z 2
v (1lg B2) + log(2/0)) <
==1
33

---

Proof of Lemma 26. By Proposition 23, we know that if S is sub-Gamme with variance process Vi and scale parameter c, then
( St 2 B&(V.)) x
where
BB(u) = max (lggglogee) eu) + (2/6)) + (log ev)+ + log(2/6)).
By [Howard et al., 2020J, we know that if (xx is B-bounded martingale difference sequence, then S: = > X, is sub-Gamma with variance process V, = =LB² and scale parameter 0. This implies,
5B Vt ((log log ctB²)+ + 1og(2/8)) S 6,
P =t: S.2
concluding the proof.
F
Experiment Details
-0A
-0.6
-1.00
-0.50
20.25
0.00
0.25
0.50
0.75
1.00
Figure 5: Examples of possible reward functions r(-) in our experiments.
F1 Hlyper-Paramee Tuning Results
We implement 6 algorithms our experiments, ETC [Algorithm 4, Hao et al., 2020], ETS (Algo- rithm 5), CORRAL [Algorithm 6, Agarwal et al., 2017], ALEXP (Algorithm 1), and Lastly UCB (Algorithm 3) with the oracle feature map Φ,. (Oracle), and UCB with the concatenated feature map github. hoom//agroop/ALEE When algorithms require
& (Naive). The Python code is available exploration, c.g., in the case ETC or ALExP, we simply set æ = (n') Figure shows the results of our hyperparameter tuning experiment. To ensure that the curves valid, each
Lightly Correlated
Highly Correlated
Many Models
p = 10
10
p
10
== 2
30
$
8
$
30
30
Regret
20
20
20
10
10
0
0
25
50
75
100
25
50
75
100
25
50
75
100
Oracle UCB
ALEXP
Naive
ETC
Corral
Figure 6: Bench-marking ALExP and other baselines. Complete version of Fig. 1 and Fig. 2.
34

---

Algorithm 2 GetPosterior
Inputs: Ht Φ, X
Let K2 + 16 (x:))(zz)))ss and V (K++ X21). and k()) - (2:)))((())))
Calculate (e(-) - k²(()))))))))))) (.)V,-'s)
Calculate o.(-) V h (.)((.) - (T)V
Return: Pt.
Algorithm 3 UCB
Inputs: X, Br,
for / = -,...,,! do
Choose 22 arg max u 1 = (x-1(x)) + 1(0)-1(1)).
>> Choose actions optimistically > Receive reward
Observe J/ r(x;) + Et.
H, f- H1-1 U ((tr,
>> Append history
Update pr; f- GetPosterior(HH, (,, Φ, x)
end for
configuration for 20 different random seeds, i.e. on different random environments. The shaded areas in Figure 7 show the standard error.
UCB. For all the experiments, the regression regularizer from À (0.01, 0.1, 0.5). We PYTORCH [Paszke et al., 2017] for updating the upper confidence bounds, which requires more regularization for longer feature maps (e.g. when 8, p 2), be computationally stable.
the exploration coefficient of UCB 3, 2 and choose
Lasso. Every time we need to solve Eq. (I), we set 7 according to the rate suggested by Theorem To find suitable constant scaling coefficient, perform hyper-parameter tuning experiment sampling 20 values [10 10 We choose Ào 0.009, and scale A₃ with it across all experiments.
We set the rates for "Y and 77 prescribed by Theorem 1. For the scaling constants, we perform hyper-parameter tuning experiment log-uniformly sampling 20 different configurations from To E [10-4, 10-1] and Vo [10", 10a). For each problem instance (i.e. as s and p change) we repeat this process. However we observe that the optimal ppper-parrmeters work well across all problem instances.
ALEXP.
ETC/ETS. For these algorithms, we separately tune no for each problem instance. We set À x Vlog M/nn according to Theorem 4.2 of [Hao al., 2020] and scale with Ào 0.009, stated before. We uniformly sample 10 different values where no E [2, 80) since the horizon is n = 100. The optimal value often happens around no 20.
CORRAL. We set the rates of the parameters as 7 O(1/n) and n O(VM/n) according to Agarwal et al. [2017, Theorem 5,]. Then similar to ALExP, we tune the scaling constants. The procedure for tuning the constants is identical to ALEXP, in the same search interval, and try 10 different configurations for and 17.
TT achieve the ddl log' regret, has 3 O(vdlog)) shown in Proposition 21.
35

---

Algorithm 4 ETC [Hao et al.. 2020]
Inputs: no. n, A1. π Let Hu = 1
for 1= ,,...,,,,, do
Draw 2t ~ a.
P Explore.
Observe // = r(x;)) + Et-
Receive reward
H1 +- H1-1 U (ztr
> Append history
end for
Ong - [(0, Hn, A1)
P Perform Lasso once
for 1 - + .,...,. do
Choose arg max O (xx)
Choose actions greedily
end for
Algorithm 5 ETS
Inputs: no. n1, A1, A, 3r, π
Let Hg =0 0
for t = ,,..., 1og do
Draw 24 π.
Explore > Receive reward
Observe Yt = r(x:)) + Et. Hi t H ( y1)}
b Append history
end for On
< C(0, Hng )1)
b. Perform Lasso once
J {j (jlOno.j + 0, j E [M]
Get sparsity pattern
Φ)(() [
Model-select acc. to j
for f. = + +l..... do
Choose æ; arg max 14 ( 14-1(x)) + 1(00-11(x))
Choose actions optimistically
Observe y/r r(æ;) +
11, 4- H,-1 U { (x))
Update Mc: 0, f- GetPosttriorrHH, j X)
end for
Algorithm CORRAL [Agarwal al., 2017]
Inputs: n, 77
Initialize 8 = 11/Inn, Inn T11 = 1/: Pl,j 2M for all j I,...,M M Set q: = 91 37 and initialize base agents (PI,I....,PI,MM)
for t = 1,...,7 do
Choose j: qr.
Sample Agent
Draw 2, ~ Pt.js-
Play action according to agent je
Observe Jr = r(xx) + Et.
IÍj = ji} for all = 1,..,, M. Calculate IW estimates fr.j = ":1
Send ft,j 41.3
#: Ifj = }e} to agents and get updated policies Pt+1.--
4r+1 = LUG--BRRIER-OMER
>> Update agent probabilities
4r+1 = (1 - g:-+1 7
> Mix with exploratory distribution Update parameters
for j ... M do
if 1
4+11, > Pt,j then Pt-1.j + 2 and M+t1. + Bmu
4.,"
else Pt-1.j Pt. and Mt+1.j Tt.j
end if
end for end for
Algorithm 7 BOOG-BARRIE-ON.
Inputs: q:. Le. Th
Find & E [min, lejj, max, Ee,zl such that EM (9T) + m., -)
Return:
ge+1 where getti 2. + (e, for all j E [M]
36

---

ETC
ETS
Corral
ALEXP
60
30
50
40-
10
10
75
30
50
30
30-
30
p
10-
10
10-
50
73
100
25
50
75
100
50
75
100
25
50
75
100
p= 12
20
25
50
75
100
25
50
75
100
25
50
75
100
23
50
75
100
30
40
5-2
20
30-
p= 13
10
50
75
75
100
60-
=
10
20
0-
40
$= 8 20
Figure Results for different hyper-parameters different problem instances. ALEXP is robust to the choice of hyper-paramtees.
37


Reviews:
[{"review_id": "HfGDv3mEeP", "reviewer": "Reviewer_XgJC", "summary": "This paper considers linear bandit problem given $M$ models, or sets of feature mappings.\nIn this problem, it is necessary to select the appropriate action as well as the model based on the bandit feedback.\nThis paper provides an algorithm with an anytime regret bound of $O(n^{3/4} \\sqrt{\\log M} + \\sqrt{n \\log^3 M} + n^{5/8}\\sqrt{d \\log n})$,\nwhere $n$ and $d$ represent the time horizon and the dimensionality of each model.", "questions": "- Can you add a description of the known regret lower bound and how it compares to the main result?\n- Line 290: $\\{1, ..., p \\}$ <- $\\{ 0, 1, ..., p \\}$ ?\n- Line 274-275: \"the rate conjectured by Agarwal et al. [2017]\" Can you tell me where I can find the corresponding description in Agarwal et al. [2017]?\n- The condition of $\\eta_t = O(..)$ and $\\gamma_t = O(..)$ in Theorem 1: Do the authors mean $\\Theta(..)$? I guess that too small $\\eta_t$ and $\\gamma_t$ do not work well.\n- It is difficult to see what figures 1 and 2 refer to.", "limitations": "I have no concerns about the limitations and potential negative societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The motivation for the research is well explained.\n- Experimental results support the effectiveness of the proposed method.", "weaknesses": "- The obtained regret bound includes $O(n^{3/4})$-term, which means that the bound is suboptimal if the number of rounds is large.\n- The proposed algorithm requires $O(M)$-time computation in each round. This can be a major computational bottleneck. In fact, in the application of sparse linear bandits, $|M|=\\binom{p}{s}$, which is exponentially large w.r.t. $s$.\nFurther, we need $M = \\Omega(\\exp(n^{1/4}))$ to ensure the regret is of $O(n \\log^3 M)$ (i.e., to ensure $n^{3/4} \\sqrt{\\log M}< \\sqrt{n \\log^3 M}$).\nThis means that the proposed algorithm is effective only when $M$ is exponentially large w.r.t. $n$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and your feedback on the notation. We have updated the text, fixing it on the instances that you mentioned. Our response follows.\n\n**On the difficulty of model selection, lower bounds, and minimax optimality.**\nThank you for this comment. We have added a discussion on lower bounds to the Conclusion section. An overview follows.\n\nOnline model selection for bandits is generally perceived to be a hard task with many unresolved problems. There are environments in which model selection may not be possible and the regret is $\\Omega(n)$ (cf. Theorem 2 Agarwal et al. 2017). There also exist environments in which the model selection algorithm will perform strictly worse that the algorithm with oracle knowledge, in terms of dependence of the regret on $n$ (cf. Theorem 6.2, Pacchiano et al. 2020). Therefore, the focus of prior so far has been on feasibility, rather than recovering minimax optimal rates. To the best of our knowledge, minimax lower bounds for model selection in linear bandits are *an open problem*. Suppose $B(d,n)$ is the lower bound of the oracle bandit algorithm (for example  $B(d, n) = \\Theta(d\\sqrt{n})$ when the action domain equals the unit ball). It is *not known* if there exists an algorithm that achieves a $\\mathcal{O}(B(d,n)\\log M)$ model selection regret. Therefore, we do not know if without further assumptions, the $n^{3/4}$ dependency of our regret bound can be improved or not.\n\nOur work is the *first* to show the feasibility of a $\\log M$ upper-bound for model selection in linear bandits, on a general infinite action domain. We are not aware of any prior work which attains a $\\mathcal{O}(n^{\\alpha}\\log M)$ with $\\alpha<1$ dependency on general action domains, let alone $\\mathcal{O}(\\log M\\sqrt{n})$. \nTo put our contribution in perspective, we mention the results of Foster et al. (2019), which considers model selection for linear bandits over a *finite* action domain of size $K$ and requires knowledge of the horizon $n$. In this setting, they obtain a regret of $$\\mathcal{O}\\left( \\min \\Big\\[(Mn)^{2/3} (Kd)^{1/3}, K^{1/4}(Mn)^{3/4}+\\sqrt{KdMn} \\Big\\] \\right)$$\nwhich scales polynomially with $M$ and has a potentially suboptimal dependency on $n$.\n\n\n**On computational complexity of ALEXP.** \nThe computational complexity of the algorithm scales linearly with $M$, since all agents/models have to be updated. However, updating the models can be done fully in parallel (using tools such as Ray), in which case, increasing the number of models will not affect the runtime of the algorithm. Even without parallelization, the algorithm is light and one complete run of ALEXP with $n=100$, $d=2$, and $M=45$ takes $2.9\\pm0.2$ minutes on a single CPU core. Figure 1 in the rebuttal pdf supplement shows how the run-time of our algorithm and other baselines scale with $M$.\n\n\nIn general, we suspect that without further assumptions (e.g. relation between $\\boldsymbol \\phi_j$) linear computational dependency on M may not be avoidable. While algorithms such as CORRAL update only one of the models at every step $t$, their statistical complexity scales polynomially with $M$ (since they require more steps to converge), which results in an overall polynomial computational complexity with $M$.\n\nIn the revised paper, we have added Figure 1, and a discussion on computational complexity to Appendix F on “Experiment Details”.\n\n\n**”Algorithm is effective only when M is exponentially large’’**. \nIn our experiments, we establish that ALEXP achieves a performance competitive to the oracle, when $M>n$, and $M$ is of the same order of magnitude as $n$.\nOur regret bound demonstrates an upper bound on the worst-case performance of the algorithm. Indeed $n^{3/4}$ is a worse rate than $\\sqrt{n}$. However, there are many effective algorithms (e.g. kernelized bandits) who’s (minimax optimal) regret has a worse dependency on the horizon than $\\sqrt{n}$. For instance, the commonly used GP-UCB with the $\\nu$-Matern kernel satisfies a $\\mathcal{O}(n^{\\frac{\\nu+2d}{2\\nu+2d}})$ regret [Whitehouse et al. 2023] which is strictly worse than $\\sqrt{n}$.\n\n\n**”Where is the conjectured rate mentioned in Agarwal et al. 2017?”** This can be found in Section 6 of their paper, titled “Conclusion and Open Problems”.\n\n\nHaving addressed your concern about rate optimality of the bound, and given the contributions of this paper to the bandit literature, we kindly ask you to reconsider the assessment of our paper. We would be happy to answer any remaining questions or concerns.\n\n---\n### References\n\nAgarwal, Alekh, Haipeng Luo, Behnam Neyshabur, and Robert E. Schapire. \"Corralling a band of bandit algorithms.\" In Conference on Learning Theory, pp. 12-38. PMLR, 2017.\n\nFoster, Dylan J., Akshay Krishnamurthy, and Haipeng Luo. \"Model selection for contextual bandits.\" Advances in Neural Information Processing Systems 32 (2019).\n\nPacchiano, Aldo, My Phan, Yasin Abbasi Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvari. \"Model selection in contextual stochastic bandit problems.\" Advances in Neural Information Processing Systems 33 (2020): 10328-10337.\n\nWhitehouse, Justin, Zhiwei Steven Wu, and Aaditya Ramdas. \"Improved Self-Normalized Concentration in Hilbert Spaces: Sublinear Regret for GP-UCB.\" arXiv preprint arXiv:2307.07539 (2023).\n"}, {"review_id": "LMVIFODyL2", "reviewer": "Reviewer_1XGh", "summary": "The paper considers the problem of model selection in (lifted) linear bandits. There are M hypothesis models, each of which have a different feature map, and one of these is the true model; it is unknown to the optimizer which of the M models is the correct one. At each timestep, the optimizer chooses one model and obtains instantaneous regret in accordance with the chosen model's selection. The goal is to minimize overall regret across n timesteps.\n\nIf feedback were obtained for all model's chosen query at each timestep, then the multiplicative weights update could be used to update the probability of any model being the true oracle model. And the guarantees from the literature would apply. However, we have limited information and only observe the reward for the chosen model's query.\n\nTo get around this obstacle, the authors consider an aggregated model with all M model's features combined together. And they train this aggregated model on all the data using a sparse LASSO estimator. Then, they use this aggregated model to fill in the missing regrets for the unchosen models. And these imputed values are then used for the MW updates.\n\nThe analysis consists of proving the recovery result on the LASSO, and adjusting the original proof to use the imputed data instead of the original. The authors verify their findings on synthetic data.", "questions": "1. If the LASSO performs well already, then what is the need to use the LASSO to perform model selection. Why can we not just use the LASSO directly?\n\n2. While the rewards for the query point of the unchosen model are not available, the predictions on the chosen $x_t$ are available. So, why can we not use the prediction error on these points for all the models to choose the weights? Instead of using the imputed data.\n\n3. What is special about the LASSO that makes it suitable for the choice of the aggregate model?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Clarity: \nThe problem is well presented, and the key difficulties of the problem are clearly identified - namely the missing regret data for unchosen models. The exposition of the solution is geared towards addressing the difficulty by imputing the missing values. \n\nThe structure of the proof is well-outlined in the main text. I also appreciated the intuitive explanation around introducing bias to reduce overall error as the reasoning behind the success of the algorithm.\n\nQuality:\nThe arguments appear correct and the correct tools are used to obtain the desired results. \n\nSignificance and Originality:\n\nAs far as I know, this problem has not been considered before, and the improvement in the scaling with M is helpful.", "weaknesses": "My main concern is Q1 below.\n\nOther weaknesses are mostly minor\n\n1. It would be useful for the authors to highlight more real-world examples where bandits with multiple models would be most applicable.\n2. In line with the above, real-data experiments would be useful to verify the applicability of the algorithm. However, the theoretical contributions are already sufficient so I think this can be deferred to future work.\n3. Figure 3 is missing label on the vertical axis and is difficult to interpret.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We have updated the Introduction and Experiments section, incorporating your feedback. Regarding your questions, see below.\n\n**What is special about Lasso that makes it a suitable choice?** To obtain $\\log M$ rates in online model selection, we require a reward estimator/hallucinator, whose bias and variance *both* scale with $\\mathcal{O}(\\log M)$. Lasso happens to hit this balance, while OLS, Ridge, or Importance Weighted estimates have a variance which grows with $\\sqrt{M}$. \n\n**When updating the models, why not hallucinate the reward for the chosen actions?** We actually considered this, but did not look into it too far, as it seemed not to affect the rate of the regret bound. We expect this approach to also work, and would be interesting to see how it changes the overall dynamics.\n\n**Why not just use LASSO directly?** Our randomized algorithm is more robust, particularly when features are correlated. We maintain a probability distribution based on Lasso estimates that encourages exploration on model selection level. In contrast, Lasso will deterministically discard some of the models, and in cases (e.g. orthogonal feature maps) will *never* sample them again.\n\nIn practice, Lasso often does not perform well for variable selection.The variable selection property of lasso highly relies on orthogonality of the feature maps, and the choice of regularization parameter. In our experiments, we introduce the ETS algorithm (cf. Algorithm 5), which uses Lasso for variable selection to select the model, and we see how it fails when there are many models, or the models are correlated (cf. Figure 1 in the paper).\n\nOn the technical side, our analysis allows for bounding the model selection regret, i.e. directly comparing the reward obtained by ALEXP with the oracle agent. It is not clear to us if/how this type of guarantee would be possible when performing Lasso variable selection to select the model.\n"}, {"review_id": "cNXxfMa275", "reviewer": "Reviewer_Vj2P", "summary": "The paper uses tackles model selection for linear bandits with $M$ models. In particular, rewards are estimated from the $M$ models using Lasso and then EXP4 is ran on-top of these estimated rewards to update individual model probabilities. The use of Lasso over ridge regression reduces variance, leading to a $\\log M$ dependence rather than usual $\\text{rm}poly \\, M$. The paper extends the usual martingale mixture analysis from ridge to lasso; this is something I thought would be quite tricky. I look forward to reading it in more detail in the future.", "questions": "None", "limitations": "Limitations clearly discussed in text.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Model selection is a very important problem. Problem is explained and motivated very well. Paper is very well written and polished to the standard of a camera-ready.", "weaknesses": "I'm not an expert on model selection in linear bandits or full information learning. As such, I cannot identify any weaknesses in this work.\n\nIt took me a couple minutes to see why (1) is indeed (group) Lasso---I was expecting to see a 1-norm. I see that you have a sentence or two explaining this after, but somehow this didn't do the trick for me. Maybe some rewording or an extra comment here could be useful, relating it to the more usual notion of Lasso.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.  Our response follows.\n\n**Add more insight on the group Lasso loss.** Thank you for pointing this out. In the revised version, we have included an explanation of the loss, focusing on how the $(2-1)$-norm induces sparsity at the group level.\n\n**Extending online Ridge analysis to Lasso is a tricky problem.** This is indeed a precise observation! We present time-uniform confidence sets, which shrink at *the lasso fast rate*. This is the key technical contribution which allows us to solve the model selection problem.\n\n"}, {"review_id": "U9qJafNGVn", "reviewer": "Reviewer_XArQ", "summary": "based on the time-uniform analysis of the Lasso, the anytime exponential weighting algorithm based on Lasso reward estimates with the nature of anytime regret guarantees on model selection linear bandits is developed. The result neither requires knowledge of the horizon n, nor relies on an initial purely exploratory stage.", "questions": "1 What is the relationship between the number of models and their final performance? \n2 During the entire learning process, for two cases, i.e., the number of models is fixed, and the number of models is changed. Can you consider these situations and discuss them?", "limitations": "the authors adequately addressed the limitations.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "the anytime exponential weighting algorithm based on Lasso reward estimates are horizon-independent, explores adaptively without requiring an initial exploration stage.", "weaknesses": "1 The dimensionality of the proposed algorithm model will be ultra-high, and the complexity of the algorithm's runtime depends on the efficiency of the sparse regression model algorithm.\n2 The results of the algorithm still belong to the class of multiplicative weights Update algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. \n\n**Our Contributions.** We would like to highlight the contributions of this paper as it seems to have missed the attention of the reviewer. \nWe address the open problem of Agarwal et al. 2017, and are the *first* to show the feasibility of the conjectured $\\log M$ rate for model selection on infinite action domains, when the reward is linearly parameterizable. This is a theoretically challenging problem, and our work is the first to show that such rates are attainable. \nOur algorithm ALEXP demonstrates how one can perform adaptive model selection while simultaneously optimizing for an objective, at a $\\log M$ rate. Our experiments show that It performs on par with an oracle solver, which knowledge of the true model.\nCrucially, this work presents a *novel time-uniform analysis of the Lasso* and establishes an important connection between online learning and high-dimensional statistics, as pointed our by reviewer Vj2P.\n\n\n**Questions.** \n1. What is the relationship between the number of the models and their performance? \n\n There is no relationship. The only assumption is that there exists one model that is able to solve the problem. \n\n2. During the entire learning process, for two cases, i.e., the number of models is fixed, and the number of models is changed. Can you consider these situations and discuss them? \n\nFollowing prior work on model selection, we assume that the number of models is fixed during the learning process. A problem setting where new models are introduced during learning could be an interesting future avenue of research.\n\n**Weaknesses.**\n1. \"The dimensionality of the proposed algorithm model will be ultra-high.”\n\nCould you please clarify what you mean by dimensionality of the algorithm? ALEXP can be computationally expensive, as it simultaneously updates all $M$ agents. However, this step can be fully parallelized with tools such as Ray. This way, the runtime of the algorithm will remain constant as $M$ grows. \n\n2. “The algorithm belongs to the class of multiplicative weights algorithms.”\n\nIndeed exponential weights is a variant of the multiplicative weights algorithm. Could you please clarify why you find this to be a weakness?\n\nHaving addressed the points you raised in your review, we kindly ask you to reconsider your assessment of our paper. We would appreciate it if you further express your questions and concerns, particularly given that you found the contributions of this work to be limited. We would be happy to answer them.\n\n"}, {"review_id": "5E6fI9rJrY", "reviewer": "Reviewer_XdEK", "summary": "This paper introduces AlExp, a novel algorithm to address the problem of online model selection in the context of bandit optimization. The algorithm interacts with the environment by randomly choosing a learner (linear bandit regret minimizer) each round, then the chosen learner tries to propose the optimal action. The exploration-exploitation trade-off is dealt with both by randomizing the choice of the learner and by the learner's policy itself. The authors provide theoretical guarantees and empirical validation and compare this approach with the existing literature.\n", "questions": "+ Can you please provide an examination of the computational limitations of this approach? E.g., providing the solving complexity of the optimizations involved.\n\n+ Due to the strong dependence (on both algorithm and analysis) on quantity C, can you please provide a more intuitive grasp on the magnitude of this quantity w.r.t. other problem-dependent quantities? Is there an available lower/upper bound on it? I feel that the quality of your theoretical results strongly depends on this quantity, and a characterization (at least qualitative) of its magnitude should be discussed.\n", "limitations": "- I feel that the main limitation of this work relies on its application in practice. However, the authors performed a sufficient experimental campaign, validating their approach. Unfortunately, the code for the experimental campaign has not been released, so reproducibility is another limitation of this work (even if they provide details to reproduce the experiments).\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The paper presents an extensive literature review and a detailed comparison between the proposed approach and the existing ones.\n\n+ The algorithm's routine is easy to understand, and its logic is well-commented.\n\n+ The algorithm effectively improves in some dependencies (e.g., the number of learners) w.r.t. to the existing approaches, both theoretically and empirically.\n\n+ The analysis presents technical novelty.\n", "weaknesses": "- In some points, the presentation is not easy to follow, and it will be nice to have a more intuitive grasp of the theoretical quantities considered.\n\n- It will be nice to have more discussion on the computational aspects of the proposed approach: numerically computing some of the quantities seems to be very expensive and prohibitive when the number of learners scales. This contrasts with the main strength of the approach, i.e., the better regret dependency on the number of learners.\n\n- The algorithm requires the knowledge of theoretical quantities (e.g., expected values). In practice, this can be bypassed by a Monte Carlo sampling procedure. However, when performing finite sampling, there's the need to explain how quickly the estimator converges to the theoretical quantity and explain the computational consequences (see previous point) or eventual corrections to the algorithm to deal with the estimation error (e.g., adding an upper confidence bound on the quantities) if due to computational reasons only a small number of samples can be generated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. Our response to your questions and concerns follows.\n\n\n**\"The algorithm has a strong dependency on quantity $C$, can you provide intuition on it?\"** Could you please clarify which $C$ are you referring to? In the text we have $C_{\\mathrm{min}}$ and $C(M, d, \\delta)$. We give a response on both. We have also updated the paper to give intuition on how $C_{\\mathrm{min}}$ affects the algorithm.\n\n- **On $C_{\\mathrm{min}}$:** If the action domain is *explorable* then $C_{\\mathrm{min}}$ is large, and in this case our bounds improve.\nIn many scenarios, this quantity can be treated as an absolute constant, e.g. 1, since we normalize the actions and the feature maps. In the revised text, *we have added a new appendix section* which presents *lower bounds on this quantity* under two scenarios. We prove that if the action domain is a convex body, or if the feature maps are orthonormal, this quantity is an absolute constant. *We have also added a corollary* to the main theorem, which bounds the regret for orthogonal feature map, **independent** of $C_{\\mathrm{min}}$, and with the same rate as the main theorem.\n\n- **On $C(M, d, \\delta)$:** This quantity has no intrinsic meaning and is defined only for a compact presentation of the theorem. The performance of the algorithm is not tied to it, rather, it depends on the values of the parameters $M, n, d, \\delta$ and $C_{\\mathrm{min}}$. Regarding its value, as defined in the paper\n$$C(M, \\delta, d) =  C_1\\sigma\\sqrt{1 +  \\log(M/\\delta) + (\\log\\log d)_+  +\\sqrt{\\log (M/\\delta)+(\\log\\log d)}}$$\nwhere $C_1$ is an absolute constant larger than $160\\sqrt{10}$.\n\n**\"The Algorithm has to calculate theoretical quantities, e.g. expected values, which are costly.\"** Many BO agents (e.g. UCB or Greedy) take actions deterministically, therefore the probability distribution $p_{t,j}$ is a single dirac delta at some point $\\boldsymbol x_{t,j}$, which for instance maximizes the UCB. Taking the expectation w.r.t  $p_{t,j}$, boils down to simply evaluating the function $\\hat{\\boldsymbol\\theta}^\\top_t\\boldsymbol \\phi(\\cdot)$ at the point $\\boldsymbol x_{t,j}$, and will not need sampling techniques. As you mentioned, upon using complex randomized agents, the expectations need to be approximated.\n\n\n\n**On computational complexity of ALEXP.** \nThe computational complexity of the algorithm scales linearly with $M$, since all agents/models have to be updated. However, updating the models can be done fully in parallel (using tools such as Ray), in which case, increasing the number of models will not affect the runtime of the algorithm. Even without parallelization, the algorithm is light and one complete run of ALEXP with $n=100$, $d=2$, and $M=45$ takes $2.9\\pm0.2$ minutes on a single CPU core. Figure 1 in the rebuttal pdf supplement shows how the run-time of our algorithm and other baselines scale with $M$.\n\n\nIn general, we suspect that without further assumptions (e.g. relation between $\\boldsymbol \\phi_j$) linear computational dependency on M may not be avoidable. While algorithms such as CORRAL update only one of the models at every step $t$, their statistical complexity scales polynomially with $M$ (since they require more steps to converge), which results in an overall polynomial computational complexity with $M$.\n\nIn the revised paper, we have added Figure 1, and a discussion on computational complexity to Appendix F on “Experiment Details”.\nThis being said, We would like to highlight that the contributions of this paper are primarily theoretical. We provide experiments mainly to give additional insights.\n\n\n**\"Reproducibility is limited due to lack of code.\"** We will publicly release the code upon acceptance. In general, the implementations are fairly standard and straightforward (cf. pages 31-34 for details).\n"}]

Author rebuttal:
We have responded to our reviewers individually. Attached is the pdf supplement, which is referred to in our responses to some of the reviewers.

Meta-review: This paper studies the model selection problem for linear bandits. The main contribution of this paper is an algorithm with a provable regret bound which scales only logarithmically with the number of base models. This is the first such result as all prior works on model selection problems establish regret bounds that are polynomial in the number of models. After the rebuttal and a good discussion all participating reviewers agree that this is a strong paper. One major concern which has been addressed in the rebuttal and discussion is the sub-optimality of the regret bounds in the horizon. It is actually unclear what the min-max regret bound would be both in terms of the number of models and time horizon, under the assumptions made by the authors. This seems like an interesting problem to be addressed in future work. I am happy to recommend this paper for acceptance to the program.
Decision: Accept (poster)