Sparse Optimistic Information Directed Sampling
Authors: Ludovic Schwartz
Hamish Flynn
Gergely Neu
Venue: NeurIPS 2025 poster ()
Keywords: regret minimization
sparse linear models
Information Directed Sampling
Bayesian methods
Primary area: theory

Abstract: Many high-dimensional online decision-making problems can be modeled as stochastic sparse linear bandits. Most existing algorithms are designed to achieve optimal worst-case regret in either the data-rich regime, where polynomial dependence on the ambient dimension is unavoidable, or the data-poor regime, where dimension-independence is possible at the cost of worse dependence on the number of rounds. In contrast, the Bayesian approach of Information Directed Sampling (IDS) achieves the best of both worlds: a Bayesian regret bound that has the optimal rate in both regimes simultaneously. In this work, we explore the use of Sparse Optimistic Information Directed Sampling (SOIDS) to achieve the best of both worlds in the worst-case setting, without Bayesian assumptions. Through a novel analysis that enables the use of a time-dependent learning rate, we show that OIDS can be tuned without prior knowledge to optimally balance information and regret. Our results extend the theoretical guarantees of IDS, providing the first algorithm that simultaneously achieves optimal worst-case regret in both the data-rich and data-poor regimes. We empirically demonstrate the good performance of SOIDS.

Sparse Optimistic Information Directed Sampling
Ludovic Schwartz
Hamish Flynn Gergely Neu
Universitat Pompeu Fabra, Barcelona, Spain
(ludovic. schwartz, famishedward.flype gergely. neu)) edu
Abstract
Many high-dimensional online decision-making problems can modeled as stochastic sparse linear bandits. Most existing algorithms are designed to achieve optimal worst-case regret in either the data-rich regime, where polynomial depen- dence on the ambient dimension is unavoidable, dimension-independenee is possible at the cost of worse dependence on the num- ber of rounds. In contrast, the sparse Information Directed Sampling (IDS) algo- rithm satisfies a Bayesian regret bound that has the optimal rate in both regimes simultaneously. In this work, explore the use of Sparse Optimistic Informa- tion Directed Sampling (SOIDS) to achieve the same adaptivity in the worst-case setting, without Bayesian assumptions. Through a novel analysis that enables the use a time-dependent learning rate, we show that SOIDS can optimally balance information and regret. Our results extend the theoretical guarantees of IDS, pro- viding the first algorithm that simultancously achieves optimal worst-case regret in both the data-rich and data-poor regimes. We empirically demonstrate the good performance of SOIDS.
the data-poor regime, where
Introduction
In stochastic linear bandits, one assumes that the mean reward associated with each action is linear in an unknown d-dimensional parameter vector [Abe and Long, 1999, Auer, 2002, Dani al., 2008, Abbasi-Yadkori et al., 2011], 1j. Under standard conditions, it is known that the minimax regret in this setting is of the order (dd/T) [Dani et al., 2008, Rusmevichientong and Tsitsiklis, 2010]. Nu- merous follow-up works have investigated the possibility of reduced regret under various structural assumptions on the unknown parameter vector, the noise, or the shape of the decision set [Valko al., 2014, Chu al., 2011, Kirschner and Krause, 2018], [Lattimore and Szepesvári, 2020, Chap- ter 22]. One such assumption is that the unknown parameter vector is sparse, which means that it has only s & d non-zero components. This setting is called sparse linear bandits and s is referred to as the sparsity level. In this setting, previous work has established the existence of algorithms with regret scaling as O sd) [Abbasi-Yadiee Yadkori et al., 2012]. This result is complemented by lower bound, which says that this rate cannot be improved as long as 2 d for some a > 0 [Lattimore and Szepesvári, 2020]. We refer to this scenario the data-rich regime. Since this bound scales polynomially with the dimension d, many researchers have considered this to be a negative result, interpreting it sign that sparsity cannot be effectively exploited in linear bandit problems. This interpretation has been challenged by a more recent observation that, when the action set admits an exploratory distribution, simple exxllorethhencomee ((ST))) [Hao al., 2020, Jang et al., 2022]. These bounds scale only logarithmically with the dimension, and constitute a major improvement over the previously mentioned rate in the data-poor
algorithms enjoy regret bounds of order
specialized either the data-poor data- rich regime, and perform poorly in the other one. A notable exception is the sparse Information Directed Sampling algorithm introduced in Hao et al. [2021], which performs almost optimally in both regimes. However, Hao et al. [2021] only provide Bayesian performance guarantees for sparse
regime, where T & (=)² Most known algorithms
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

IDS. These results hold on average, assuming that the problem instance is drawn at random from a known prior distribution.
In this work, we lift this assumption and develop an algorithm that can adapt to both regimes in a "frequentist" sense: we assume that the true parameter fixed and unknown to the learner, and provide guarantees that hold for any given instance. The algorithm is an adaptation of the recently proposed Optimistic Information Directed Sampling (OIDS) algorithm of Neu, Papini, and Schwartz [2024], which itself is an adaptation of the classic Bayesian IDS algorithm originally proposed by Russo and Van Roy [2017]. Within the Bayesian setting, has been shown that IDS can exploit var- ious types of problem structure, and adapt the hardness of the given instance [Hao and Lattimore, 2022, Hao et al., 2022]. These results have been complemented by the recent work of Neu, Papini, and Schwartz [2024], which showed that similar improvements can be achieved without Bayesian assumptions, via a simple adjustment of the standard IDS method. In this paper, we continue this line of work. We show that sparse version of OIDS enjoys worst-case regret bound that matches the optimal rate in both regimes simultaneously.
Our contribution is as follows:
We extend the analysis of the optimistic posterior to allow the use of time-dependent learn- ing rates and history-dependent learning rates. Time-dependent learning rates allow us to drop the requirement that the horizon is known in advance, and are essential for worst- case regret bounds that can adapt to both regimes. History-dependent learning rates allow to update the learning rate based on data observed by the agent instead of some loose theoretical constant, a necessity for efficient algorithms.
We demonstrate that the Sparse Optimistic Information Directed Sampling (SOIDS) algo- rithm recovers almost optimal rates in both the data-poor and data-rich regimes. This is the first algorithm to do so a frequentist setting.
2 Preliminaries
Sparse linear bandits. We consider the following decision-making game, in which a learning agent interacts with an environment over a sequence of T rounds. At the start of each round the leamner selects an action A, E Ac Rd according to randomized policy E ((A)). In response, the environment generates a stochastic reward Y; r(A:) Et, where : A IR is a fixed reward function and is zero-mean, conditionally J-sub-Gaussian noise. We assume that the action set A finite, and that the reward function can be written as
r(a) (0o: a),
where &g E Rd is an unknown parameter vector. We make the mild boundedness assumptions that max,eA |lallo < 1 and ||6011 i < 1. We study the special case of this problem in which the parameter vector Og is s-sparse in the sense that at most s & of its components are non-zero. In other words, we assume that 0g belongs to the following sparse parameter space:
{0 Rd 10=1-(0 S |00| 100]==1]
11]
θ =
We assume that the sparsity level is known to the agent. The performance of the agent is evaluated in terms of the regret, which is defined as
T
Rr = T max (0p. a) - E Σ r (Att 0o) aEA
(1)
where the expectation taken with respect to both the random choices of the agent and the random noise in the observed rewards. We note that the regret is implicitly function of the true parameter 8g Our focus is on proving regret bounds that hold for arbitrary choices of 0g E e.
The data-rich and data-poor regimes. As mentioned the introduction, it known there exist algorithms for sparse linear bandits with worst-case regret of the order ((vrdT) [Abbasi- Yadkori et al., 2012]. This regret bound is only meaningful when the dimension d is smaller than the number of rounds T, situation referred as the data-rich regime. Under the assumption that there exists an exploratory policy, Hao et al. [2020] showed that there is a simple algorithm that satisfies

---

regret bound, which can be meaningful in the so-called data poor regime, where is much larger than T. Formally, we say that there exists an exploratory policy if the action set A is such that
(Jaa" dodaa))a)) 0,
Cini
max min MEA(A)
which equivalent to the condition that A spans Rd_ The exploratory policy is the distribution on A that achieves the maximum (which guaranteed exist when A is finite). The Explore the Sparsity Then Commit (ESTC) algorithm was shown to satisfy a regret bound of the order (
min Cmi 2/3) [Hao al., 2020]. The transition between the T2/3 rate in the data-poor regime and the vT rate in the data-rich regime also appears an existing lower bound of the order ( ( VdT) [Hao et al., 2020].
Adapting to both regimes. Recently, Hao et al. [2021] showed that the sparse Infor- mation Directed Sampling (IDS) algorithm performs well in both regimes. Under the sparse optimal action condition (Definition 1), IDS satisfies a regret bound of the order O(min( (dTnV A, neously optimal in both the data-rich and data-poor regimes. However, this result is limited to the Bayesian setting. This is because IDS uses the Bayesian posterior to quantify uncertainty, which is only meaningful 0g really is a random draw from the prior.
min )) where A x miin(lo((AA)) (IAA), log(dT/s))- This is simulta-
The sparse optimal action condition. Part of our analysis requires that a certain technical condi- tion is satisfied. This condition comes from prior work [Hao et al., 2021], and is used to bound the regret in the data-poor regime (cf. Lemma 7).
Definition 1. For given prior Q an action set A has sparse optimal actions if with probability the random draw of 0 from Q+ there exists a' arg max r(a, 0) such that ||a'|lo S s.
We use prior that only assigns positive probability to s-sparse vectors, which means the sparse optimal action property is satisfied whenever the action set is an bp-ball. Note that the hard in- stances in both the sdd lower bound in Theorem 24.3 of Lattimore and Szepesvári [2020] and the 2//3T2/3 lower bound in Theorem 5 of Jang et al. [2022] satisfy the sparse optimal action property'. Therefore, imposing this additional condition does trivialize the problem.
Notation. We conclude this section by introducing some additional notation that will be used in the subsequent sections. For any candidate parameter vector (or model) 0 E IR4, we let r(,, 0) = (0, a) denote the corresponding linear reward function. In addition, we define a" (0) arg max,e r(a, 0) (with ties broken arbitrarily) and r" (0) = rraa((( (0). ()) to be the optimal action and maximum reward for the model 0. The gap of an action a for model 0 is A(a, 8) r' (0) r(a, 0). Similarly, the gap for a policy π E ((AA) and a model distribution Q E (()) is A(T, Q) = SAxe A(a, 0) dm X ((a, 0), and we let A. = (TT,, 0o) denote the gap of the policy played by the agent in round / under the true model 0g. Using this notation, the regret can be written Rí E A.]. We define the unnormalized Gaussian likelihood function p(y|0,a) a) = exp( -vp(-w-(eea ((.))) Finally, we let F, = a (A1, (A,,Y1, Yi,..., A,, Yt) denote the o-algebra generated by the interaction between the agent and the environment up to the end of round t.
3 Sparse Optimistic Information Directed Sampling
We develop extension of the Optimistic Information Directed Sampling (OIDS) algorithm pro- posed by Neu, Papini, and Schwartz [2024]. The main difference between OIDS and IDS is that the Bayesian posterior is replaced by an appropriately adjusted optimistic posterior. For an arbitrary prior Q E A(0), the optimistic posterior is defined by the following update rule:
dQt dQ
(0)
II (p(Ys A.A)) exp X Σ A(As, 0)).
'The optimal actions in the hard instance used to prove Theorem 5 in Jang et al. [2022] are 2s 2s-spas which still allows us to prove the same bound on the surrogate 3-information ratio, up to constant factors.
3

---

Here, is positive constant that should be thought of as "large", and (At)s is decreasing sequence of positive real numbers that decays to 0, and should be thought of as "small". We allow X, to be computed by the algorithm at the end of the round f. In other words, any Fi-measurable ) is ad- missible. Note that when 7) = and X = 0, the optimistic posterior coincides with the Bayesian posterior. While this construction is closely related to the optimistic posterior update described in Zhang [2022] and Neu, Papini, and Schwartz [2024], there are a few important differences. First, the A(A,,) 0) term appearing in the adjustment serves r' (0))) for the same purpose. Intuitively this serves to "overestimate" the true gaps with the op- timistic posterior, driving exploration towards parameters that promise rewards much higher than whatever would have been accrued by the agent. In contrast, the adjustment of Zhang [2022] drives exploration towards parameters 0 with high optimal reward regardless of how well the agent would have performed under the same 0-meaning that unduly assigns mass to uninteresting parameter choices, where any policy is guaranteed to work well anyway. Intuition aside, this adjustment greatly simplifies our analysis of the optimistic posterior as compared to the analysis of Zhang [2022] and Neu, Papini, and Schwartz [2024]. An important additional novelty is that our update features time-dependent exploration parameter Xe, which is crucial for the adaptive regret bounds that we seek in this work. To describe the OIDS algorithm, gain and the surrogate regret. For any round i and any policy π E ((A), the surrogate information gain is defined
alternative to their proposal of using
must first define the surrogate information
Σ
Σ x(a) l ((-))()))a)) aQ7 (0), DEA
(T)
((Q) E [0] is the mean parameter under distribution Q. The surrogate regret is defined as
where for any Q A()).
( = Σ x(a) / Ala,
I
aEA
For any policy ı and any 7 2, we define the surrogate generalized information ratio as
IR ( (T) (T)) (T)
= (( (0, (o.0000 ((T))
(3)
((a) (0- oQ) (0)
We can at last define the Sparse Optimistic Information Directed Sampling (SOIDS) algorithm. In each round the policy played by SOIDS is defined be the distribution A that minimizes the 2- 2-information ratio:
(SOID))
arg min IR, (TT).
(2)
(4)
TEA(A)
The choice of 7 2 is motivated by the fact that the minimizer of the 2-information ratio is an approximate minimizer of surrogate generalized information ratio for all 2 2.
Lemma 1. For all 2 2,
TR (SOIDS)
2-2 min IR (T).
REA(A)
This fact was discovered for the Bayesian IDS policy by Lattimore and György [2021] and remains true for the SOIDS policy. We provide a proof in Appendix F.2 for completeness. Finally, we remark that the "sparse" part of the name SOIDS refers the choice of the prior Q We use the subset selection prior from Section 3 of Alquier and Lounici [2011], which is described in Appendix B.2.
Main results
In this section, we state our main results. First, we relate the true regret any policy sequence to the surrogate regret of the same policy sequence. We then use the fact that the surrogate regret is controlled by both the and 3-information ratios. This, combined with Lemma 1, allows us to show that with properly tuned parameters, SOIDS has optimal worst-case regret in both the data-poor and data-rich regimes. Finally, we show that SOIDS can be tuned in a data-dependent manner, such that its regret bound scales with the cumulative observed information ratio instead of the time horizon.

---

4.1 General bound for the optimistic posterior
We start with generic worst-case regret bound relating the true regret of any algorithm to its sur- rogate regret. Since the surrogate regret is defined with respect to the optimistic posterior, which is known to the learner, can be controlled with standard Bayesian techniques. This result is an extension of the bounds stated in Neu al. [2024], Zhang [2022]. To our knowledge, it the first result of its kind which is compatible with time-dependent or data-dependent learning rates. The stated result is specialized the setting of sparse linear bandits, but the techniques used deal with iime-dependent and data- detendeenndent learning rates are applicable beyond this setting.
Theorem 1. Assume that the optimistic posterior is computed with = and a sequence of de- Set Ào 1 2" If the learning rates do not
creasing learning rates x satisfying Vt 2 1, depend on the history, then the regret of any sequence of policies Tt satisfies
Rr <
R 5 2s
TAT
T
3
(T.(
+ 22
(5)
AI-1
32
A
E=1
Otherwise, the learning rates depend on the history, let CA,T be deterministic upper bound - valid for all t S T, and C2,r be deterministic upper bound Xo-1 The regret of any sequence of policies me satisfies
4e C7,
2 2 log
3 (Te)
RT
+
> (T(
2
(6)
ÀT
32
d=1
4.2 Adapting to both regimes
We show that the SOIDS algorithm with properly tuned parameters achieves the optimal regret rate in both the data-rich and data-poor regimes.
Theorem 2. Assume that the sparse optimal action condition in Definition is satisfied. Let
x = V
128d(E+1) and x
3C11
CyLIv
miin
with C2 = + 2s 2slog edtt
If A =
(1+1)V8
min( 2: max(>!?) (2), ,,,(1))., then the regret of SOIDS satisfies
Ro 5 min l 5 15+2s 2s log
edl
edd')
Tv VCmin
+ 2s log df, 30
+
log
EdT (0 (o sdT
o (ST) log edT
)
)
= =mi
where O OVVilog (z) represents an absolute constant independent of
We observe that our algorithm enjoys both the (( and the ((sT)) regret rates. Unlike the Bayesian regret bound for the sparse IDS algorithm of Hao et al. [2021], our regret bound holds in "worst-case" sense for any value of 6 e. To our knowledge, this makes our method the first algorithm to achieve optimal worst-case regret in both the data-poor and data-rich regimes
4.3 Instance-dependent guarantees
The bounds presented in the previous sections are minimax in nature, meaning they hold uniformly over all problem instances. We present bound which the scaling with respect the horizon T is replaced with the cumulative surrogateinffommtion ratio, which could be much smaller than T in "easier" instances, leading better guarantees.
Theorem Assume that the sparse optimal action condition in Definition I is satisfied, and (
that < 2- Let x
V 2d (R? and X
+Σ:= VIR (IR(")(T)))
5

---

A max (3) ), then the regret of SOIDS satisfies
3
RT -
2 +
80
+ 5 log
edT
min
8
2d
+ Σ
--1
IR²
(Te))
,s,
3v6s 6s
IR;
(T))
3
Cmmi
1=1
(8)
edT
T-1 (TTE)
3 3
0
log
min
2d +
IR,
888
IR (Te)
VCmin
This type of result is only possible because novel analysis of the optimistic posterior (cf. The- orem I) can handle bistory-dependen learning rates. A full proof is provided in Appendix D. This result shows that (with appropritate choices of the learning rates) SOIDS is fully adaptive to which of the two regimes is best. Because our analysis requires decreasing learning rates, we are forced to leave the log(T) terms out of the learning rates, and our logarithmic term has worse power than in the bound Theorem 2. An interesting open question is whether it is possible to improve the dependency on this logarithmic term while still using data-dependent learning rates.
Analysis
We now provide an outline of the proofs of the main results.
5.1 Proof of Theorem
A key observation is that the optimistic posterior can be interpreted as learner playing an auxiliary online learning game over distributions (()). The loss of that game is a weighted sum of negative log-likelihood and estimation error losses. We define
(1) (0)
Σ log
1 p(Y, A,))
(10, A.) -Y.)²
be the cumulative negative likellkeioood loss of and
L ((
()
to be the cumulative estimation error loss of f. In addition, we define the regularizer + A()) - IR by the mapping ~ DxL (P](T). which is the KL-divergence with respect to the prior Q With those notations, the optimistic posterior corresponds to an instance of the Follow the Regularized Leader (FTRL) algorithm introduced by Hazan and Kale [2010] and Abemetty et al. [2008]. FTRL a standard method in online convex optimization that balances cumulative loss minimization with a regularization term to enforce stability and guarantee controlled regret. The update can be reframed as
Q
arg min (inmminnnn))) (P,nL, (1) + >e + ((P).
PEA(O)
This formulation enables the application of tools from convex analysis and online learning, such as Fenchel duality, to derive regret bounds for this auxiliary online learning game and to understand the interplay between the two losses under the learning rates 1 and X We now focus on the case in which the learning rates X don't depend on the history and relegate the analysis of distory-dependen learning rates to Appendix C. The following lemma provides a bound on the average regret when the model 0g is drawn from an arbitrary comparator distribution P.
Lemma 2. Let P E (()) be any comparator, then the following bound holds
*(P) x0 (n A)A,
(2) (0T) ()) XT (2))
" ((P, I.(1))
T (Or)).
Xx
(9)

---

Here 02 = arg g (0) denotes the maximum likelihood estimator at time t, and (L( log Ie exp(L()))dQ (0) is the Fenchel dual of the regularizer क. A complete proof of this result provided in appendix B.1.1. We aim to chose comparator P and the prior Q such that P is concentrated around 8, and the KL divergence KKL (t) is controlled. If the parameter space were finite, the natural choice would be to take P as a Dirac on dg and Q as a uniform distribution on the whole parameter space; more care is necessary here. Choosing Q as subset-selection prior and P uniform distribution sparse neighborhood of 0g satisfies both requirements.
Lemma 3. The subset-selection prior Qf E (()) verifies that for any e and 0 O, there is comparator Po E A()) satisfying both
2ed
Aa' E sPpp(Po), 10 -0-6l1 11 and DxL (Pol s log
The proof of this lemma, as well the exact choice of the prior Q and the comparator P(Ou), are provided in Appendix B.2. In Appendix I (ef. Lemma 21), we establish that both L (+) and are 2T-L-pschitt with respect to the & norm. Hence,
E LT (+)
E
(1) P.
TT LT
(1) (Bo)
2Te
and Σ [0.. Ad) - ((),A)) s 2T'..
ÀT
AT
Combining these with Lemma 2, we obtain the following bound on the cumulative regret:
log
2nd + 2T + tije
Φ (-(-n(L)))) - (0r)) (L2) > L (.)
Rr
<
AT
AT
(06) (4)) AT
E
The first term balances model complexity and approximation via In the usual FTRL analysis, (AL) is non decreasing for any L RR, and the term involving क' can be telescoped. Things are more complex here because only some part of the loss is weighted by the time varying learning rate XT. Through a careful analysis involving the maximum likelihood estimator, we can decompose the 4* term into telescoping sum and remainder term. Lemma 4.
4 (n(LF) (07) - XT
())
E
4* (n(Li (00)L)
(2) (.)) - A (-
& (n((( (0)(0) ( (.))
<
E
Xe-1
A-1
(10)
(6 + log TdT
(11)
AT
A detailed proof of this result is provided in Appendix B.1.2. Finally, the remaining sum can be handled by looking at the explicit formula for Φ* The terms related to the likelihood and the gap estimates can be separated using Hölder's 's inequality, as is done in Zhang [2022] and Neu, Papini, and Schwartz [2024]. More explicitly, by now choosing 17 4. we obtain the following lemma.
Lemma 5.
t (0) - 11 (-)) --- 12-11
---
E
Ac-1
dc-1
T
(mt)
T
< E
+2 32A,11
+ m
(12)
full proof of this result is provided in Appendix B. 1.4. Combining Lemmas 2, 3, 4, and setting Z. we obtain the desired regret bound stated in Theorem 1.
7

---

5.2 Proof of Theorem 2
We show how Theorem 1 can be combined with bounds on the surrogate regret to control the true regret. The first important fact is that the surrogate regret of any policy can always be controlled in terms of the or the 3-surrogate information ratio of that policy.
Lemma 6. Let X O, then we have that for any policy π E ((A)
(T)(T) mmiin A
(x(T)
XTR
(T),
c3
XIR (T)
where cg < 2 is an absolute constant defined in Lemma 27.
This is a consequence of a simple generalization of the AM-GM inequality and is proved in Ap- 64 3 A and Theorem 1, we can further upper
pendix F.1. Combining the previous lemma with À = bound the regret of sequence of policies (IT)) as
5
28 log edT
(Tt)
T
RT S E
+
Σ
((())
XT-
321
1=1
T
< E
CT
min
32
3 X IR
(2) (T),
16 C/
3A
IR (TT))
(13)
AT-1
3
where Cr 5+ 2s log edf', Usually, bounds on the 2- 2-information ratio can be converted to ((VT) bounds and bounds on the 3-information ratio can be converted to O(Tă) bounds. Hence we will use the 2-information ratio control the regret in the data-rich regime and the 3-information ratio to control the regret in the data-poot regime. Due to Lemma 1, the SOIDS policy minimizes the 2-information ratio and approximately minimizes the 3-information ratio. As a result, if there exists "forerunner" algorithm with bounded 2-information ratio or 3-information ratio, SOIDS inherits these bounds automatically. In particular, we can use a different forerunner for each regime and SOIDS will match the regret guarantees of the best forerunner in each regime.
This forerunner-based technique widely used to analyze IDS based algorithms and has been ap- plied to variety of Bayesian settings [Russo and Van Roy, 2017, Hao et al., 2021, Hao and Lat- timore, 2022] and some frequentist settings [Kirschner and Krause, 2018, Kirschner et al., 2020, 2021]. An advantage of the OIDS framework is that since the surrogate quantities defined with respect to the optimistic posterior, the analysis of the surrogate information ratio is virtually identical to the corresponding analysis of the information ratio in the Bayesian setting.
The forerunner we consider for the 2-information ratio is the Feel-Good Thompson Sampling (FGTS) algorithm of Zhang [2022]. For the 3-information ratio, we consider mixture of the FGTS policy and an exploratory policy. The following lemma provides bounds on the surrogate information ratios of the SOIDS algorithm.
Lemma 7. The 2- and desssoogatt-inoommmaiii ratio of the SOIDS algorithm satisfy for any 2
IR (2)
(T
(SOIDS))
<IR!") T
(2)
(FGTS)
S 2d
(14)
and
IR. 33) (SOIDS)
I 21R ( (mixx)
54s
T
<
Cuin
(15)
The explicit definition of both forerunner algorithms, as well as the proof of this lemma, are deferred to Appendix F.3. Finally, it remains to pick the learning rate X, The following lemma describes the appropriate learning rate for the data-poor and the data-rich regimes separately.
Lemma 8. The choice of learning rate X
128d guarantees
3C++1
32 T
CT
IR
(SODD))
2 s 16 CTaT.
X
(2)
3
7-1
[=l
The choice of learning rate
X
(3)
1
CULIV Camis (++1)/s
guarantees
4-63
CT
16
C
(x(3)
IR,
(x+
(3) (SOIDS)
I 12-63
(8 Cr Cmin
$ T
(3)
3
8

---

m 20, 2
10-40,,5-
100,
Rasdor
3002
2905
2002
100
1500
200
0
Figure 1: Cumulative regret for 20 (left) 40 (middle) and 100 (right), We plot the mean + standard deviation over 10 repetitions.
The proof is deferred to Appendix G.2. The expression for the constant cj S can be found in Appendix I.2 (cf. Lemma 27). It remains to analyze what happens when the learning rate X = min() max(A Ne )! is chosen. We defer this to Appendix G.4.
Experiments
We aim to verify that, in both the data-rich and data-poor regimes simultaneously, the regret of SOIDS is comparable with the regret of existing algorithms that achieve near optimal worst-case regret in either the data-rich the data-poor regime. Our baseline for the data-rich regime is the online-to-confidencee
Yadkori et al. [2012], which has worst (OTCS) method proposed by Abbasi-Yadkori
case regret of the order vsdT For a tougher comparison, we run this method with the confidence sets from Theorem 4.7 of Clerico et al. [2025], which have much smaller constant factors than those used by Abbasi-Yadkori Yadkori et al. [2012]. Our baseline for the data-poor regime is the Explore the Sparsity Then Commit (ESTC) algorithm proposed by Hao al. [2020]. which has worst-case regret of the order (sT)2/33 For reference, we also compare with LinUCB Abbasi-Yadkori et al. [2011], 11, which does not adapt to sparsity. It is generally difficult tio contains expectations w.r.t. the optimistic posterior. In our implementation of SOIDS, we use the empirical Bayesian sparse sampling procedure of Hao al. [2021] draw approximate sam- ples from the optimistic posterior, and then approximate the surrogate information ratio via sample averages. We provide further details regarding the implementations of each method in Appendix J.
the SOIDS algorithm exactly because the surrogate information
For each d E {20, 40, 100}, Og is the s-sparse vector in IRd, with s d/ /010. in which first s com- ponents are 10/s and the remaining components are zero. The action set consists of 200 random draws from the uniform distribution on 1]6. The noise variance is and we run each method 10 times. In Figure 1, we report the cumulative regret over T = 1000 steps. As d is varied from 20 100, appear to transition from the data-rich regime to the data-poor regime: for d 20, the OTCS method is the best performing baseline, whereas for d = 100, ETCS is the best performing baseline. As our theoretical results would suggest, SOIDS performs well in both regimes.
7 Conclusion
There remain several interesting questions that our work leaves open for future research, such as the possibility of improving the logarithmic terms in the instance-dependent regret bound (as mentioned earlier in Section 4). We highlight another question below.
In our experiments, we have made use of an approximate implementation of OIDS adapted from Hao al. [2021]. The initial success we have seen our experiments suggests that this approximation might be viable in more challenging settings, and worthy of an attempt at solid theoretical analysis. More broadly, the results indicate potential advantage of IDS-style methods over DEC-inspired methods [Foster et al., 2022b, Kirschner et al., 2023]. Indeed, we are not aware of any general methods for approximating the optimization problems that the E2D algorithm of Foster al. [2022b] requires to solve, in contrast to our results that indicate that IDS-inspired algorithms may very well be amenable to practical implementation. Whether the concrete approximation we used in experiments is the best possible one or not remains to be seen.

---

Acknowledgements. The authors wish to thank Johannes Kirschner for thought-prose provoking discus- sions about information directed sampling before the preparation of this manuscript. This project has received funding from the European Research Council (ERC), under the European Union's 's Horizon 2020 research and innovation programme (Grant agreement No. 950180).
10

---

References
Yasin Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Yasin Abbasi- Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Online-to-confidenee conversions and application to sparse stochastic bandits. 2012.
Naoki Abe and Philip M Long. Associative reinforcement learning using linear probabilistic cepts. In ICML, pages 3-11. Citeseer, 1999.
Jacob D. Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. pages 263-274, 2008. URL http:: cs. (aapprs/117-Aae helsinki. ftlffi/ppp http/papess/a/a 117 -beenbbrn pdf.
Pierre Alquier and Karim Lounici. Pac-bayesian theorems for sparse regression estimation with exponential weights. Electronic Journal of Stufistics, 5:127-145, 2011.
Peter Auer. Using confidence bounds for exploitation-exploraiio trade-offs. Journal of Machine Learning Research, 3(Nov):397-422 422, 2002.
Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensional covariates.
Operations Research, 68(1):276-294, 2020.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities A
Nonasymptoticc Theory of Independence. 2013. ISBN 978-0-19 19-55555--....
doi: 10.
ACPRROF-OSS//9330119553333 000.0000000.001.... 9780199635255. 001.052225550000000......
URL https://dois org/ 109./.0093///0 http//////oo../////////////oooo/ oso/
Sébastien Bubeck and Mark Sellke. First-Order Bayesian Regret Analysis of Thompson Sampling, 2022. URL httt::////xiiiv org//bs//a abs abwpaa//...////////////////aaa 191./99....00 00681.
Sunrit Chakraborty, Saptarshi Roy, and Ambuj Tewari. Thompson sampling for high-dimensional sparse linear contextual bandits. In International Conference Machine Learning, pages 3979- 4008. PMLR, 2023.
Wei Chu, Lihong Li, Lev Reyzin, and Robert E. Schapire Contextual bandits with linear payoff functions. volume 15 of JMLR Proceedings, pagess 208-214, 2011. URL http://pprocoeeinggs mlr. p.r.spressvv5//// chul 1a a/ chulla. pdf.
Eugenio Clerico, Hamish Flynn, Wojciech Kotlowski, and Gergely Neu, Confidence sequences for generalized linear models via regret analysis, 2025. URL https: /ettps///arxv... wrw. wwwrg/////////////o/ooo////eee// aa/aa/ba///000 2504. 16555.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In COLT, volume 2, page 3, 2008.
Dylan J. Foster and Alexander Rakhlin. Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles, 2020. URL http://arxiv org/ abg//bbs/0022 04926.
Dylan J. Foster, Noah Golowich, Jian Qian, Alexander Rakhlin, and Ayush Sekhari. A Note on Coefficient, 2022a. URL
Model-Free Reinforcement Learning with the
httg//bb//22111/ 2ttps///............11 14250.
Dylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin. The Statistical Complexity of Interactive Decision Making, 2022b. URL http:://rxiiy oow.ooog//ao...ooo..oo httggabs/2212.. 13487.
Dylan J. Foster, Alexander Rakhlin, Ayush Sekhari, and Karthik Sridharan. On the Complexity of Adversarial Decision Making, 2022c. URL /ttpt::///iii.t.ttt/ttttt
13063.
Sébastien Gerchinovitz. Sparsity regret bounds for individual sequences in online linear regression. The Journal of Machine Learning Research, ((11)729-7669 2013.
Botao Hao and Tor Lattimore. Regret bounds for information-directer reinforcement learning. 2022. URL http:://apper..eeee. wiw.. httpappprrrriipssscppppp..pep filelffilleeeeeeeeereeee / paapr//022/hash/
.tml..

---

Botao Hao, Tor Lattimore, and Mengdi Wang. High- sigh-dimensional sparse linear bandits. 2020.
Botao Hao, Tor Lattimore, and Wei Deng. Information directed sampling for sparse linear bandits. 2021.
Botao Hao, Tor Lattimore, and Chao Qin. Contextual Information- -irrected Sampling, 2022. URL
http:// /ttp///xxvvv///////////////.a../ www.eooggaooooo..... wtrg/abs/2205.. 10895.
Elad Hazan and Satyen Kale. Extracting certainty from uncertainty: Regret bounded by variation in costs. Machine Learning, 80(2-3):165-188, 2010. doi: 10.11001000 10.1007/5100944000-55777 URL
https://doi. org/10 1000000000/100044-0---5555
Kyoungseok Jang. Chicheng Zhang, and Kwang-Sung Jun. Popart: Efficient sparse regression and experimental design for optimal sparse linear bandits. Advances in Neural Information Processing Systems, 35:2 15:2102-2114, 2022.
Gi-Soo Kim and Myunghee Cho Paik. Doubly-robust lasso bandit. Advances in Neural Information Processing Systems, 32, 2019.
Johannes Kirschner and Andreas Krause. Information Directed Sampling and Bandits with Het- eroscedastic Noise, 2018. URL http: org/
wwwp/rgg//////eeeeeeeeeeeeeee/ee aaaaaaas.... 09667.
Johannes Kirschner, Tor Lattimore, and Andreas Krause. Information directed sampling for linear partial monitoring. volume 125 of Proceedings of Machine Learning Research, pages 1328-23699 2020. URL http://proceeedngs mlr. press/ press/vi22 111///irrcheere0aa html.
Johannes Kirschner, Tor Lattimore, Claire Vernade, and Csaba Szepesvári. Asymptotically optimal information-directer sampling. volume 134 Proceedings of Machine Learning Research, pages 2777-2821, 2021. URL http::/ppooceeding. mlr watsss//v3//kiissshh 21m.mmml..
Johannes Kirschner, Seyed Alireza Bakhtiari. Kushagra Chandak, Volodymyr Tkachuk, and Csaba Szepesvári. Regret minimization via saddle point optimiza- tion. 2023, URL http://papers mipperrr...pp........... cc/ 0tte67722aa44tabb111006eeeeeee.
/ Abstract- Cow.ettt-oooeeeeneeeeeee httl..
Tor Lattimore and András György. Mirror Descent and the Information Ratio. volume 134 of Pro- ceedings of Machine Learning Research, pages 2965-2992 2021. URL URRLttpp//prrceeedngs mlr.
html.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Gergely Neu, Julia Olkhovskaya, Matteo Papini, and Ludovic Schwartz. Lifting the Information Ratio: An Information-Theooee Analysis of Thompson Sampling for Contextual Bandits, 2022. URL http: org/ ab/aabbs22222 13924.
Gergely Neu, Matteo Papini, and Ludovic Schwartz. Optimistic information directed sampling. 2024.
Min-hwan Oh, Garud Iyengar, and Assaf Zeevi. Sparsity-agnostic lasso bandit. In International Conference on Machine Learning, pages 8271-8280. PMLR, 2021.
Francesco Orabona. modern introduction to online learning. CoRR, abs/1912.13213. 2019. URL
http:://axxiv.orr/bbbeee att////bb/11..../// 13213.
Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Operations Research, 35(2):395-411, 2010.
Mathematics of
Daniel Russo and Benjamin Van Roy. An citoommationtthooretti analysis of thompson sampling.
Journal of Machine Learning Research, 17:68:1-68:30, 2016. URL https: //jmrr//.///////// .rg/ html.
popers/vi7/44-0
Daniel Russo and Benjamin Van Roy. Learning to Optimize via Information- -iirected Sampling, 2017. URL http: //tp:///arxii org/abb abs///b//aae 1403. 5556.
12

---

Michal Valko, Rémi Munos. Branislav Kveton, and Tomás Kocák. Spectral bandits for smooth graph functions. volume of JMLR Workshop and Conference Proceedings, pages 46-54, 2014. URL http://procceedigg mlr wwt.ppees/v32//eee. http//////vaalaa valko14.
html.
M.J. Wainwright. Iliig-DDienssooal Statistics: Non-Asymplotic Viewpoint. Cambridge Series
in Statistical and Probabilistic Mathematics. 2019. ISBN 978-1-108-49802-99 URL https:
//books. google
Xue Wang, Mingcheng Wei, and Tao Yao. Minimax concave penalized multi-armed bandit model with high-dimensional covariates. In International Conference on Machine Learning, pages 5200-5208. PMLR, 2018.
Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement SIAM Journal on Mathematics of Data Science, 4(2):834 857, 2022. doi: 10.1 10.1137/21M140994X. URL https://doi. org/10. 10. 1137 0007/21m14400 m144924
13

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not move the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how answer these questions. For each question in the checklist:
You should answer [Yes]. [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
* Please provide short (1 (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evalu- ation. While "[Yes] " generally preferable to "[No] is perfectly acceptable answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true amswer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer:
[Yes]
Justification: We provide theoretical proof and experiments supporting the claims made in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations of the work and some remaining open questions. We comment on the computational efficiency of the proposed algorithm.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
-The authors encouraged to create separate "Limitations" section in their paper.
14

---

The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and faireess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The complete proof and assumptions of every single result is either in the main text or the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The code and data are provided and the experimental setting is described.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
15

---

If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), relcasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The code is available online.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nipss
mublic/guidess wwwpe///ooSSuumiiiiiiiiio onnooiccy for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//nips. cttpcc/ppllco http//ubllcccc c/ wttp///ggg/eeeeeeeeeeeeeeeeeeeee httgg/ude///dduubbeeeeeeeeeeeeee http//ooeeSSeeiieeeeee Sttteeeuummmmmiimmmimmmmmmm onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
16

---

Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
The full code available.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
See the figures included the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, one should state The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All of the experiments be run on the CPU of laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't tt make it into the paper).
17

---

9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: httpp:://neuris.... wwtppppccc/tateeeeeeeeeeeeeeecte ctt.cccciiiciiiieees
Answer: [Yes]
Justification: We respect NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: Due the theoretical nature of the work, societal impacts are hard to foresee.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions access the model or implementing safety filters.
18

---

Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: of the code has been written by the authors of the paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi thcodeeooeee.. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
19

---

Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects. and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttp///eeerrpp/eeeee cc/Conferencese / for what should or should not be described.
20

---

A Related work
The first algorithms and regret bounds for sparse linear bandits were designed for the data-rich regime. Abbasi-Yadkori et al. [2012] developed an ooline-to-coffidencesse conversion for linear models, which converts any algorithm for online linear regression into linear bandit algorithm whose regret depends on the regret of the online regression algorithm. When the SeqSEW algorithm [Gerchinovitz, 2013] is used in this conversion, the result is a sparse linear bandit algorithm with regret bound of the order sdV) (ignoring logarithmic factors). Lattimore and Szepesvári [2020] established a matching lower bound for the data-rich regime, showing that this rate cannot be improved.
More recently, several works have studied the data-poor regime, in which the dimension d is much larger than the number of rounds T. Hao et al. [2020] showed that an explore-then seree-thee--oommi algorithm satisfies a regret bound of the order ((ssT)*/*C min 22/3), and established a lower bound of order 1/33 V V Subsequently, Jang et al. [2022] proposed the PopArt estimator for
(mmin(s (3//312//3 min
algorithm that uses this estimator achieves regret bound of the order ((s2/3T2/3 H2/3), where H. is another problem-dependent quantity that satisfies H? I C- In addition, Jang et al. [2022] established lower bound of order 0(52/312/3 min showing that the optimal rate for the data-poor regime is 52/3722/3, Hao et al. [2021] showed that sparse IDS has a Bayesian regret bound that optimal for both regimes.
sparse linear regression, and showed that an explore-then-come
A number of works have considered sparse contextual linear bandits, in which the action set A changes in each round t. In the case where the actions sets are chosen by an adaptive adversary, the upper and lower bounds of the order sdd by Abbasi-Yadkori et al. [2012] and Lattimore and Szepesvári [2020] respectively still hold. Under the assumption that the action sets are generated randomly, and such that either uniform or greedy policy is (with high probability) exploratory, several methods have been shown to achieve nearly dimension-free regret bounds Bastani and Bayati [2020], Wang et al. [2018], Kim and Paik [2019], Oh et al. [2021], Chakraborty et al. [2023].
The concept of balancing instantaneous regret and information gain through the information ratio was first introduced by Russo and Roy [2016] in the context of analyzing Thompson Sampling. Building upon this, the Information-Direse Directed Sampling (IDS) algorithm was proposed by Russo and Van Roy [2017] to directly minimize the information ratio, thereby optimizing the trade-off between regret and information gain. These foundational ideas have since been extended and applied to a variety of settings including bandits [Bubeck and Sellke, 2022], contextual bandits [Neu et al., 2022, Hao et al., 2022], reinforcement learning [Hao and Lattimore, 2022], and sparse linear bandits [Hao al., 2021]. However, these works are primarily situated in the Bayesian framework and focus on Bayesian regret bounds that hold only in expectation with respect to the prior distribution.
A key challenge in extending these methods to the frequentist setting lies in estimating the instanta- neous regret and define meaningful notion of information gain. Both of those things are naturally possible in Bayesian analysis but difficult when the true model is unknown. Moreover, Bayesian posteriors may inadequately represent model uncertainty from frequentist perspective. We high- light three strands of research that have attempted to address this challenge:
Confidence-see based information ratio approaches: Works such as Kirschner and Krause [2018], Kirschner et al. [2020], and Kirschner et al. [2021] extend the notion of the information ratio to frequentist settings by constructing high-probability confidence sets for the instantaneous regret and information gain. These results are mostly limited to setting with some linear structure.
Distributionally robust and worst-case information-regree trade-offs: The cidision-to-Estmmation (D))f line of work of [Foster et al., 2022b, Foster and Rakhlin, 2020, Foster et al., 2022c,a, Kirschner et al., 2023] explores the frequentist setting by analyzing worst-case trade-offs between regret and information gain. One limitation is that the DEC is an inherently worst-case measure of comlexity. Moreover, algorithms based on the DEC usually require solving complex min-max optimization problems at each time step, making their practical implementation challeng- ing and unclear.
Optimistic posterior approaches for frequentist guarantees: The approach most closely related to our work modifies the Bayesian posterior to provide frequentist guarantees. Introduced by Zhang [2022], the optimistic posterior is modification of the Bayesian posterior which enables frequentist regret bounds for a variant of Thompson Sampling. Subsequently, Neu et al. [2024] studied the optimistic posterior framework in greater depth, defining a frequentist analog of the information
21

---

ratio to extend IDS to frequentist settings, A notable limitation of these works is their restriction to constant learning rates in the optimistic posterior, which limits adaptivity, an issue that we address in this paper.
B Analysis of the Optimistic posterior
This section provides further details about the prior underlying the optimistic posterior and guaran- tees on the posterior updates.
B.1 Follow the regularized leader analysis
The main step in our analysis of the optimistic posterior is to leverage the follow the regularized leader formulation our optimistic posterior update
Qit = arg min (i,n(PnL)) + AoL, + (P))
PEA(O)
B.1.1 Proof of Lemma 2
As is usual in the analysis of the follow the regularized leader algorithm, we introduce the Fenchel conjugate Φ* : g + R of the regularization function & PxL (-112)). which takes values
$* (LL SUPPEA(e) (P. L} ((P)). The Penchel-Yourg inequality guarantees that for any P E A ()) and LE R
(P. S xPP) (L).
We introduce the maximum likelihood estimator 0, = arg mingee Li-" (0)(()) and the function
I(-) ( - (0r) Xr T. (2) (.)
Since Ar is never used by the algorithm, we assume that Ar Ar-1- The role of the maximum
likelihood estimator is to ensure that the term (0) _ (0,) is always non-negative. The Fenchel-Young inequality tells us that
7 L (0r) - (P. Ar P. (. S (PP) + Φ*
())
Noticing that (2) ΣT= ((P.A) and rearranging the terms concludes the proof.
B.1.2 Proof Lemma 4
We start by rewriting the potential function in the form of the following telescopic sum:
4. (-n(L (-) 14 (Or) - (2)
AT
T ('(-n(L( (1) (44))) (-(-n(L_))))
(0--1) d A L.-1
A
A-1
In the usual follow-the-regulle www.rreuuuuad--eiieeeeee leader analysis, we use the fact that À (AL) is non- X
decreasing for any L. E R Here however, only one component of the linear loss is scaled by A and so the standard FTRL analysis fails. Crucially, because we introduced the maximum likeli- hood estimator ir, we have that (.) - L ()) (0.) 2 O. We can therefore use the following lemma that guarantees that a scaled and shifted dual is monotonic.
Lemma 9. Let + 2 0 and xp be convex function and its dual as defined previously. For L1, La g such that L1 2 0, the mapping À + (- is non-decreasing on IR+
Proof. By definition, we have
s0 (-L) + Nl2) SUPPES(O) (P, -1 + +bb)) ((P)
X
A
(P. + ((P)
sup PEA(O)
(P,
X
22

---

For any P E A()), we have that ((P) + (P.L1) 2 0 and the term inside the supremum is non-decreasing with respect lambda. Since the supremum of non-decreasing functions is also non-decreasing, this concludes the proof.
IT
Applying the previous lemma, we upper bound the previous sum by replacing each X factor by A--1 (using the convention Ao 1/22, and then we replace the maximum likelihood estimator O, by 8g inside gh to obtain
T Φ (-nnnn 1 (0.) x.I.2) (-(-n(1,10)
d
d=-1
6 (-(n((T(()) (.)
I (0.)) X 1. *'(n((1,1() L _ (0t-1)) - \ X--1
A-1
X-1
6' (-(nn(L4 (1) 11 (0o)) - 1., 4'(-n(L210 1 (0o)) -
A
A
" (0.) L, (.)(() (0o) (0)) (0--)))
A--1
It remains to bound the difference of the negative log likelihood of the true parameter and the max- imum likelihood estimator. This is done via the following result (whose proof we relegate to ap- pendix E.I.I).
Lemma 10. For any t 2 I, we have
0 < R (0)) (000-110000 (0,)) s inf {
{2pt.
2pt + 8 llog ed(1+
+ 2/pp)
edt
< 6 + s log
(16)
Using this lemma, we can further bound the previously considered expression as the following telescopic sum:
(L -." (00) (0--))) " (L)) LT (0r))
E
A
T
(I." (0.) 1 (B))) - -
" (I (0.) (6)))
E
A-1
xe
t=1
$ 1 Σ
(I) (1) (06) - 1 (00))
x -
xe-1 -
1=1
< 17(6 + s slog edT
AT
(1) Here, the first inequality comes from the non-negativity of (()())))))))))))) L (0,) by definition of 0g and the second one is from Lemma 10 just above and telescoping argument. Finally we obtain the claim of Lemma 4.
B.1.3 Controlling the losses separately
The focus of this section is to understand how to control (-(-)) where T. is either the negative- likelihood loss the estimation-error loss. We start by analyzing the negative-likelhhodd loss. As was done in Neu, Papini, and Schwartz [2024], we will relate the negative-likclihodd loss to the surrogate information gain.
For this analysis, we define the true information gain as
Σ x(a) /
IG
((0 Go a) (0),
(17)
AEA
and note that, by linearity reward function, the surrogate information gain always smaller than the true information gain. This is stated formally below.
23

---

Proposition 1. For any policy (AA) and any t 2 1 we have that
(T) S (T)
(18)
The proof provided in Appendix 1.1. This result can then be used to relate the surrogate and the true information gain to the negative- negative-lkeelhoodd loss. This result and its proof are identical to the proof of Lemma 17 in Neu, Papini, and Schwartz [2024].
Lemma 11. Assume that the noise Et is conditionnally I-sub- Gaussian, then any 2 1,77, 2 0 na (1 nja)
such that y 2
the following inequality holds
p p(Ya)0, ) (.)
na
log
dQt - -2 - 27,1-2y)E ((G(
(19)
S 2 1011-2111 [G.
(20)
In particular, the constant 2y(11 - 27) can be maximized the value 3 16 by the choice na
Proof.
By the tower rule of expectation and Jensen's 's inequality applied to the logarithm, we have p(Yi As) 00 Ar) dQi (0) Fi A1
p(Y, As) P(Y, At)
log /
log
aQt (0)
E
p(y, p(Y,
< E
log E
dQ2t (0)
Ar
p(Y,(on, A.)
(Y, A,))² (Yr - (0o, Aa))² )
F Fi-1, A, aet |
E
log
E
exp
2
2
Now, we fix some 0 E è and to simplify the notation, we let = (fo. Ad) and r (0, Ar). Using some elementary manipulations and the conditional Gau-Gansiinn tail behaviour of 6, and Yt = ro + E, which implies that for any (Fi-1, ( 4y)-measurable St. E [exp (x-, = exp(roGi) IF [exp (((5)) Ar] S exp(ro6t) exp
we have
2
(Y: r)² (Y--ro)) ro)2
))
E
exp
-nja
F F,-1, A1
2
1J0 (2Y, - - - -r)) ( Fr-1, As)
E
exp
2
r
72
E [exp (ra))))(((rr)))F)--1111 Ar]
exp
110
2
r0
2
2
11²02 (r (r-ro)?) ro)))
S exp
110
exp exponarolr roo) exp
2
exp
(r ro )
1J0
(1 m/xx)
2
Further, defining =
na 2
(1
nax), we have
7/0 (Y, r)²
(Y, -/)r ))
exp
F Fr-1, Ar
2
< exp((
(ppp--(r--) - 2)
2
< 7(r r0)² (r ro)*
2
< 1 7(r - -o)2
2 2n 2 (r ro)²
< 7( 27)(r r2)
Here, we used the elementary inequality exp(x) - 1 + x² for r S 0 and then used |r - rul S 2. Finally, using that log x < x - for any x > 0, and taking the integral over O we get that
E log / ( ())) na aQr (Q) --1(1- 2
A.)
Σ ((( [ ((0 6, a,,
LAEA
-- 2T [I,)
Rearranging and combining the result with Proposition 1 yields the claim of the lemma.
24

---

We now turn our focus to the estimation error loss and relate it to the surrogate regret through the following lemma, whose proof is straightforward application of Lemma 23.
Lemma 12. For any t 2 B, > 1, if 3 - 1, we have
3 log / exp((x exp(8At-1A(A, ()) (0) S R (23.(m))
E
(21)
B.1.4 Separation of the two losses: proof of Lemma
We make use of the fact that the Fenchel dual of + can be explicitly written as ('( = log Jo ex)( (Q) (0). As a result, we have
4 (-n(LL ()) Li (06)) x-)1 &
- X-11
E
2--1
T
So
p(Y))0.a.) plys (o.Ac)
0)) exp (-1112 (0) A (2)
- (0) aQt(o)
E
log
A1-1
10 exp (nn (0) A 1-
(2) (0)) dQT (0)
1=1
1
(1)) " ((Ycl(o, (M1Y100.A))
)
E
log
exp (AA(AA)A((A,,))) 0)) aQ? (0)
A
T
((V.
log / exp (BAc- (AA, aQt (8)
S
E
log
+
adi-
p(Yi)ou, A.)
-Ax-1
where the last equality is by definition of the optimistic posterior and the last inequality follows from using Hölder's inequality with the two real numbers a, > 1 that satisfy 1 + 3 Combining
a Lemma 11 and Lemma 12 with the choice a = 3 = 2. the fact that n and the last inequality yields the claim of the lemma.
B.2 Choice of the prior and comparator distribution: proof of Lemma 3
In order to construct the prior Qf and the comparator P for the regret analysis, we need to take into account two criteria: that DRi. (PI(QT) ) be controlled and that KP. L) I.(O)) be small. The comparator will be function of the unknown parameter fg. and thus we denote it by Pa.
As for the prior, it should take into account the sparsity level of the unknown 0g. but should have no access to its support. We first design a distribution over the set of all subsets of [d] = (I...., d). which have cardinality at most We choose the distribution such that: a) the probability assigned to each subset depends only on its cardinality; b) the probability assigned to the set of all subsets of size k is proportional to 2 where 1 < k s. In other words, we prefer smaller subsets and have no preference over which indices in [d] are included. The distribution that satisfies these requirements is
2 2-181
TTS)
(22)
Ei-12- 2-k (15)
d
For S = 0. we set II(S) = O. Doing so only complicates matters if the support of 0g is empty (i.e.. Oo = 0). However, in this case, the reward function is 0 everywhere, which means any algorithm would have O regret. We therefore continue under the assumption that fu * 0. The most impor- tant property of this distribution. which we will use later, is that for any subset S of cardinality s, log(1/II( ())) < s slog(eedss). For each subset S, we define Qs to be the uniform distribution on Og. The prior defined to be
Φ+= Σ N(S)Qs-
SCIISSSS
As for the comparator distribution Pa.. we would ideally like to take Dirac measure on Go. but this would make the KL divergence appearing in the bound blow up. Thus, we pick a comparator Ps. which dilutes its mass around 0,. For any 0 E O, with support S, and any E (0, 1). we define the set (1 -c)) = (1-c))++ed' 6' E es) C θg. We choose Po, to be the uniform distribution on (1 e +)0,, + <O where Sn the support of 9g. We now bound 4b (P,)))) = DxI. Pool1QQ for this choice of Po. in the following lemma, from which the claim of Lemma 3 then directly follows.
25

---

Lemma 13. For any 0 E O let S denote its support, and let |S| 8. If. for E (0,1). Pg = u((1 - [[6 + e and Q = Eschd
(s))Qss. ((S)) then DxL (Poll S slog 2nd
Proof. We notice that (1- g is s-dimensional f1-ball of radius 6, which is contained in gg Therefore, on the support of Pg. df' equal the ratio of the volumes of unit l-blll and aqı
an é ball of radius e, which is (1/c)². Thus,
dPp dPs S / log DKL (PollOT) = f log Es II(SddQs
dP dPg S s slog + log II(S) IT(S)dQs
Using the definition of II and the bound
(*) -
Ed on the binomial coefficient, we have
(
( 12g(2) + log Σ 2 S log
2ed
log
log
TT(S)
k=1
Combining everything, obtain
2ed
2ed
DKL (Po QT) S <slog
log
= s log
(23)
as advertised
C Proof of the history-dependent part of Theorem
Following the original analysis, we arrive again (9).
T
12) ((P) Φ (- ()) + nLT (07) AT ()) + XT
Σ A(A,,)) P) 1=1
((P,L LT (Or)).
AT
AT
where P A()) can be any comparator distribution. Lemma 3 is still valid and chose the same prior as before. We can still choose a comparator distribution supported on an e-ball around fn-
IP-L - (9w)
(e))
However, because D; depends on the history, we can no longer upper bound E
Ar
by E
2i's Ar
Using Lemma 21, we still have that L (-) is 2T Lipscciti and E ()) is 2T-
Lipschitz. Hence,
P
LT (1)
[ (Bu)
E
2TeC2,, and Σ |a a.) a(P.a:) $ 2Te,
ÀT-1
where we used C2.r, a deterministic upper bound on XT- Exactly the same telescoping of 6 can be done, however because the learning rate is history -eeeeddde,,n,ntt, the difference between the negative log likelihood of Gg and 6g must be treated with more care. We have the following lemma
Lemma 14. Let Cr,r be deterministic upper bound on (xita 2x)) that holds for all t. < T, then
E
n
(I. (16) II2, (0,1)) + Ax
17 (I. "I (fo) I
(0T))
de-
26 Ce
n115 + 3s log
(24)
2AT-1
complete proof of that result can be found in appendix E.2.1.
Finally, was the case in the history independent version the telescoping sum can be handled by looking the explicit formula for 4' and Lemma still holds. Applying Lemma 5 and setting TC2. yields the claim of the theorem.
26

---

D Proof of Theorem 3
We turn our attention to data-dependent bounds (that will scale with the cumulative information ratio rather than the time horizon). Combining the second part of Theorem I with Lemma and the choice À 64 A we have that for any non-increasing sequence of learning rates X₃ satisfying Ao S 2, the following holds
CT Ar-1
32 Σ
T
16 (Te),
RT < E
+ min
IR,
3 SaV 3A 3 IR, (TTe)
(25)
3
3
46 Ci and Ci,T, respectively C2,7 are deterministic upper bounds
where Cr 2 8 log on 1 No I respectively 17
f
We let x
2d+E.=1 IR (T.) and A (3)
and verify that d =
Jyde
+E,
(Tr))
VC
(2) X is decreasing and always smaller than We also verify that C1, = C2,r = /
max(A
valid upper bounds. As result, we have the following upper bound
4e C2,
< + log 3e (
edT - 2 + 58 log(
Cr = =2 log
(26)
g2
We focus bounding the containing the information ratios. Applying Lemma 7, obtain that for all t > 1, IR, (T,) < 2d and for any T 2
(2)
IR.
(Tp
T = V3
2d + Σ =
IR
(Tx))
IR, (TT)
Σ IR (2)
(Tx)
2
IR,
(2)
(mT))
t=1
T-1
2 2
2d
Σ
IR. (AT))
(2)
1=1
where we applied Lemma 19 with the function f(x) and a; IR. (T.) to get the second
(R(2)(m)))
v
inequality. This can be seen as generalization of the usual ΣT 1
vt < 2vT inequality. We
now define R / (2d ΣT= (R,") (Z.)). the data-dependent regret rate associated to the
2 2-surogaateiinformatioo ratio.
27

---

We now turn our attention to the 3-information ratio. Applying Lemma 7 we obtain that for all and for any 2
t 2
1,
IR (3)
(T+))
54
54
a²
Cmin
Crnn
T
(3) IR
(TT))
(Te) = 88
3y6s VCmin
IR_ (3)
(TT
T
V |R;
(TT2)
VA
88
IR
(Ts)
T
15
3
IR& (TT))
(3)
2
3
3vGs
IA
IR
(Te)
2
VCmin
where we applied Lemma 19 with the function f(x) ond inequality. This can be seen as a generalization of the usual Σ 1 S 3 3
J and a; V IR
(3)
(T)) to get the sec-
x3
2
We now
define R st
E V IR, (me) the data-dependent regret rate associated to Vinin
the 3-surrogate- informaaionoo ratio. We now consider the last time that the learning rates 1 and x(2) have been used. More specifically, we denote T/ maxft < T, x 2 x
1-11). }. and
>.2)). Coming back to the bound of Equation 25 and using the T3 max(t T, T (2) ( the following bound holds
(3) definition A = (1(
RT
E
Cr
min
32 (TT);
A
IR,
(2)
16
03
31, IR (TL)
XT-1
1=1
E
Or
min
(2)
(3)
min
(3
32
max
1 (10) IR (2)
16 (TT).
cj V
max( m
(1
IR, (3) (mee)
T-
--1
We can now separate the sum obtained at the last line based on which learning rate was used at time
t.
T
min
32
max
(2)
IR,
2)
(Te))
sv 3 max (2) (3) )IR (3) (#T) IR. (T))
(1
3
3
Σ
32
(2)
(Te)
Σ
16
3 0/
31
(3)
3
(8)
2
(
T2 32
Ts 16
IR (2)
(TT) +
03
31
IR
(T)).
3
3
t=1
1=1
We further bound - 32 (2)
1 IR (TT) <
04 (2)
R
T
and
D1'
48
/
3x
(3)
IR
(TT)
<
16 R2
(Using the explicit value oa = 2
The crucial observation is that which of X the term of leading order (up some constants). More specifically, Let T be such that x - > XT-1
(3)
or x is bigger will determine whether R or R is
(2) (3)
28

---

which means that
Rearranging, this implies
2d42 -1 IR. (m.)
Vmmm
+Σ
+21=1
IR. (T))
that s (2d +2d IR;
3y6a
T- 2==1
RR₁
(Tx)
which means that By S
VCmin
RG
Following the exact same steps, we also have that AT 2 XT implies that R _ R (2)
We apply this to the time T2 in which 21--1 2 1 by definition. we have that R - R and putting this together with the previous bound, have
RT E
CT
[3)
+
64
3
R
16
3
TT
((3)
T-1
$ E
CT
R
64
3
T2
(2)
16
3
T
(3
< R
CT 33)
64
T2
(3)
16
T1
(3)
E
CT (3)
64
(3)
16
R
(3)
3
T
3
1
CT
80
< E
3
where we use the fact that T + ( and + Ry are non-decreasing and T. S T,T3 5
Similarly by definition of T3, have that X7 TT-1 and conclude that R2 R
(2)
Putting this together, with the previous bound, we have
RT SS
E
CT
64
RT
(2)
16
RT,
(3)
(2)
3
T-
CT
R
64
((2)
16 (3)
8
3
S
CT (2)
64
R7
(2)
16
8
<
Cr
R
64
(2)
16
R
8
CT
80
S
11
3
where the fact that T - Putting both of those bounds together with Equation 26 yields the claim of the Theorem.
R(2 and T
R den-decrggi and T. T,Ts T.
E Maximum likelihood estimation
The focus this section is to bound the difference between the log-likelihoodd associated with the true parameter and the maximum likelihood estimator (MLE). We start by establishing upper bound that holds in expectation which suffices to handle bistory-independer learning rates. Then, to high-probability bounds that will allow us deal with data-dependent learning rates.
E.1 Bound in expectation
We start with the case in which the maximum likelihood estimator is computed on a finite subset of the parameter space θ.
Lemma 15. Let t > 1, and O' be finite subset of O define the MLE over O'
OMLE, (0')
arg min L (0).
6e
29

---

Then,
E [ (0o)
-. (OMLE:((()) - log |o'|
Proof. By the concavity of the logarithm and Jensen's inequality, have
P(Y,/0MLE, (0)..
E [. - -,," (PMLEE.)(())) - log E
II
p( |0, As)
===1
p p A.)
AY,,),,A.)
= log E
max Oee'
S log E
Σ II
p(Y, (o. A.)
P(Y, A.)
Loeer a=1
p(Y, 10, Ag) P(Y, As)
log
E
AE
By Lemma 25, we have that exp (0)) (0) II
P(Y.)0.A.)
(..AA a non-negative su- permartingale with respect the filtration Fi , At). That implies that each term in the sum is upper bounded by 1. Hence.
E ()) (0o) (00) I, (. (BALE,
S log Σ 1 = log (0%,
mEer
which proves the claim.
To extend the previous bound to the full parameter space, O' C θ is said to be a valid p-covering of θ with respect to the ε norm if for every E +, there exists A' O' such that | 8'1l1 p. We denote by M(e,, II1,P) the smallest possible cardinality a valid covering. We have the following bound on this quantity.
covering argument. A subset
Lemma 16. For every > 0,
d (1+ 2)a s slog ed(1 + 2/p) 8 (5)c
log.N(0, |l 111, p) s log
8
Proof. For each subset C [d] of cardinality [S] = 5, there is a surjective isometric embedding from (Os, || I11) to (1B ||- Il1). In particular, to embed E Og into (1), one simply
remove all the components of 0 corresponding to indices not in S. Therefore, for every p > 0, N(Os, - 1, p) (B) || [la, p). Moreover, via standard argument, we have N (I)
p) S (1 + ) (see, e.g., Lemma 5.7 in Wainwright, 2019). Now, let Os,p denote any minimal
p-covering of Og and notice that for an arbitrary E with support S, there exists a subset Š such that C S and JŠ| 8. Therefore, there exists 0 E 0 such that ||0 - 0|] S p. Hence, Usc(d] Ss.p forms valid p-covering of and its cardinality bounded by
( 11,p) s |Uscianst- S
Σ
(1+
(3) (1 1 )+
SC m=
and we conclude by the elementary inequality (9)
< de
E.1.1 Proof Lemma
We bound the difference between the log-likelihood of the true parameter and that of the maximum likelihood estimator on the full parameter space. To this end, let p >> and O' minimal valid p-cover of O is defined in Lemma 16, and 0' O' be such that ||0' - 0ell p. which exists by
30

---

definition of a p-covering, Then,
B L (06) (0.) =E [1 (06) - (O
E ((MO,,,, - I1 (8))
E 4 (0') LL. (0.)
+ 2pt.
where the first term is bounded by Lemma 15, the second term is non-positive by definition of the maximum likelihood estimator because 0' E O' and the third term is bounded because the mapping 0 + E L, (0) is 2t-Lipschitz with respect to the 1-norm by Lemma 21. Finally applying
Lemma 16 and setting p & yields the desired bound.
E.2 High-probabilityy bounds
We begin with the case where the maximum likelihood estimator is computed over a finite subset of the parameter space @ and provide a corresponding high-probability bound.
Lemma 17. Let O' be a finite subset of O we define OML,F,(O') = arg mingger L (0). Then
|o'
IP
32 1,
I. (OMLE, 2 log (0) 1,
S 6.
(28)
Proof. Fix 8 O'. By Lemma 25, we have that exp
1 (.) III' p(Y, (o
p(Y, O...))
non-negative supermartingale with respect to the filtration (F)),, where Fi o oF Al+1), allowing us to invoke Ville's inequality to get the following guarantee:
P 3t 2 1, exp((, L, (0) N 5 < 6.
(0)
Taking the logarithm and union bound O' yields the desired result.
We now provide a bound on the expected product a bounded random variable with the differenece in log-likelihood between the true parameter and the maximum likelihood estimator.
Lemma 18. Let B TR and X be random variable satisfying 0 S X S B almost surely. Then for any t 2 1,
2) ed(1+ 22 p
et
:d:d(1+ 2)
-.0 E X(L (1) (0o) (00)
inf 0,000
E
log
5 Bpt + Bös
s8t
so?
2
B
s log
E
X
(29)
T
Proof. Let p. 0 and O' be minimal valid p-cover of θ defined in Lemma 16, N = |'), let 0' = (fe) and let 0 e O' be such that ||0 0z]l S p. which exists by definition of valid p-cover. We have the following decomposition:
E ((IL!" - (0.))
X(L (0o) - _000))))) (0')) ( (00 #1
<
+ BE
(I (0o) (00) 111h (1)()))) (1) 1L. 71
+ BE (L, (0) (.0) + BE (1)
The first term is upper bounded by E [X log ]. the third term is upper bounded by 3 Btt because ||0 0'Il, | is uniformely bounded by / and by by Lemma 21. The fourth term is non-positive because 0' minimizes the negative log likelihood on e'. Finally, we turn our attention to the second term.
31

---

To simplify the computations, we let Y (06) (8). and compute E Y (r #3
Conditioning on whether e larger or smaller than log z/2 yields the following identity
[P 2 c
if log z/4 otherwise.
Y ) 2 2 IP Y log ]
We can now upper bound the expectation as follows
(Y210g }) =
Y1 (Y } 2 de
N
N
log
Y
log
P 2 c| de
8
log 3
N
N
N
log
Y Z log
8 P
2
log
d8'
8
N
S 6 log
+
where we used the change of variable E = log Nxx and used IP [[
2
log N < 8 by Lemma 17.
0
Finally, putting everything together and using N s &V(0,,1l1), [ed(1+ we get
2) by Lemma 16,
ed(1 + 2)
e d(1 + 2)
5
E X(LL LL)
E
Xs log s
B + Bōs B8glog
2
To balance the trade-off between the approximation error and the covering complexity, we choose p BT: and 5 which yields the desired form of the logarithmic factors. Substituting these into the bound completes the proof.
E.2.1 Proof of Lemma 14
As was noted in the analysis, since Ar is not used by the algorithm, we can replace ÀT by År- 1 in our computations. We have
T
(L (0.) (0)) (B0) + (00) (1) (0--1))
" (I (Bu) (0r))
E
E
"
(In (0x) (16)))
Σ
" (L) (1) ((,) L (Bb))
d=-
d
n E (L. ( (Bo) (8)
(1)
1
Let Oi, be a deterministic upper bound on 1. Ae+1
(x
Applying Lemma 18 to X
+) and telescoping, we get
xe)
(L. (1) (00) -(00))((((0))) (00)
()) (1- - --11
n
E
be
[=1
2ed
(). \ - 1 -11)) :]
1n 17
5 + log
E
s
2e Cf.
Ar + +1]
1
2n
5 + log
E
2e CP
(15 + 3s log
E
2AT-1
32

---

where in the last step, we used S 1
which implies 1. Xr
+ +15 S 2
3.
This finishes the proof.
2
F
Bounding the surrogate information ratio
E1 Proof of Lemma 6
The surrogate regret of policy is directly related to its and 3-information ratio by definition
(T) / (T) (.)) IG (TT)
By the AM-GM inequality, we have that for any X > 0, the surrogate regret is controlled as follows
(.(T) S (T) IR2 2
(T).
Similarly, by Lemma 27 which generalizes the AM-GM inequality, we can obtain the following regret bound
(T(T) S ( + V AIR (3)
(T))
À where cg < 2 is an absolute constant defined in Lemma 27. This concludes the proof.
F.2 Proof Lemma
The proof of Lemma is essentially the same the proof of Lemma 5.6 in Hao et al. [2021], but state it here for completeness. Throughout this proof, we use (p. f) = E.cA p(a) f() to denote the inner product between signed measure A and function f A R. Using this notation, we can, for example, write the generalized surrogate information ratio as IR, (T) = {म. IR(")
We define x. E arg min TEA(A) IR, ?)) (T) to be any minimizer of the generalized surrogate infor-
mation ratio with parameter 7 2 First, we observe that
2(T,, A. ((T,, PIG.
IR
TT. IGt)
(IT,IG,))*
Therefore, from the first-order optimality condition for convex constrained minimization (and the fact that IR, is convex on A(A)), we have
VIT E (AA), 0 OS (T
(SOIDS) V V.IR
(2) (T, (SODD))))
In particular,
0 2m²
(SOIDS A (7) (SOIDS) Σ,) ((m
(SOIDS)
A ) (m
(1) (SOIDS) IG.)
(OIDD)) IG+)
(SOIDS) I2
This inequality is equivalent to
Ad) 1+ (m. IG.)
2(
(n) Ao) 2 (m
(SOIDS)
(m.
(SOIDS) A.)
(m
(SOIDS)
IG.)
From this inequality, obtain
((m
(SOIDS)
Ao ((T
(SOIDS)
A (())(((T)))))) SOIDS)
T
A,)))=2
(T) IG,)
(SOIDS)
(TT (OODD)
IG.)
((T)) (7) A,)) (OODDS) A
(T .G.)
< 2- (1T (7) Ad)) 2
min IR. (T))
{TT (7) IG,)
=EA(A)
thus proving the claim.
33

---

F33
Proof of Lemma 7
This section is focused on bounding the information ratios of the sparse optimistic information directed sampling policy. As is widely done in the information directed sampling literature, will introduce a "forerunner" algorithm with controlled surrogate information ratio. By Lemma 1, the SOIDS policy will then automatically inherit the bound of the forerunner.
As one of our forerunners, we will make use of the Feel-Good Thompson Sampling (FGTS) algo- rithm introduced by Zhang [2022]. Letting Og ~ Q the FGTS policy is defined as
FFGTS) (a) Pr a" (6.) a)
(30)
Which can be seen the policy obtained by sampling parameter 02 Q and then picking the optimal action under this parameter. Compared to the usual Thompson Sampling policy, this boils down replacing the Bayesian posterior by the optimistic posterior. Whenever the optimal action for 0 is non-unique, we define a" (0) to be any optimal action with minimal O-norm. If there are multiple optimal actions with minimal O-norm, ties can be broken arbitrarily.
E3.1 Bounding the two information ratio
We will now prove the first part of Lemma 7, by showing that the information ratio of the FGTS policy is bounded by the dimension. The proof is exactly the same as in the Bayesian setting as is done in Proposition of Russo and Roy [2016], Lemma 7 of Neu et al. [2022] or in Lemma 5.7 of Hao et al. [2021], except the Bayesian posterior is replaced with the optimistic posterior. We provide the proof here for completeness.
Since defined the surrogate information gain in terms of the model 8, opposed to the optimal action a" (0), we follow the proof of Lemma in Neu et al. [2022]. For brevity, we let &a
(FGTS) (a) = Pt aa (0r) = a). We define the |A| x |A]] matrix by Tt
Ma.0' v Ca (Er (a),a,a, (ō.) = a'I - rr,, ((Q)))
Next, we relate the surrogate information gain and the surrogate regret to the Frobenius norm and the trace of M. First, we can lower bound the surrogate information gain of FGTS as
(m (FGTS)
Σ
(r(a,((Qt) - r(a, a))
2
aEA
Σ
Σ
2
aEA
a'EA
/ (1
= d')
2
AEAd'EA
Σ Σ
Qa (r(a,0(Qt) - E.rra, 0)) = a'))
2
AEAd'A
ΣΣ
M
M
0,
2
dEAd'Ed
Next, we can re-write the surrogate regret of FGTS
(m (FGTS) = ((d((0)))))07(00)
E aa / r(a,
(31)
aeA
Σ 1 1/
Σ
car((,, ((Q)))
e aeAA
aEA
a. E. = al - Σ carla,
aEA
aEA
tr(M).
34

---

Using Fact 10 from Russo and Roy [2016], we bound IR, (2)
(T ( as
(m (
2(tr(M))
2) (GTS)) IR T
M 2 22.raum rank(M))
(m (PCT))
All the remains is to show that M has rank at most d. Enumerate the actions as A = fa.,.... a and let μ4; L,, [0, (0.) azJ. By linearity of expectation (and of the reward fuucction, we can write
M = Varasyus o(Q7).a))
Therefore, M can be factorized as
(0i(m-0(Q1:))
M
[aaa
(OLAI(MAII (( ((QT))
Since M is the product of a K x d matrix and d x K matrix, it must have rank at most min(K, d).
F.3.2 Bounding the three information ratio
To bound the information ratio follow Hao et al. [2021] and we introduce the exploratory policy
1 arg max Omin
Σ aEA
(a)aaaa
(32)
TEA(A)
+N where y 2 0 will be determined later. First, we lower bound the surrogate information gain of the mixture policy the same way that we lower bounded the surrogate information gain of the FGTS policy previously. This time, obtain the lower bound
We define the mixture policy T, (mix)
(1-7) (FGTS)
IG, (T (mix)) (mixx)
T
(mix)
(a)
Σ
Pe(a" = d')(r(a, E, Daja" (0) a²))²
aEA
e'EA
Σ aEA
T
(mix)
(a)
Σ
Pa(a" = d') -(Q)),
a'EA
E, E, la (0:)) a'). From the inequality Tiz ((mbx) 2 mp(a), and the definition of Cmiu. we have
where Per
(T (mix)
2
7
Σ
Pi(a" (0.) = = Σ
- - aa (Mo ((Q)))
2
a'EAA
aeA
2
Σ
P.(a" (0:) =
2
a'EA
Using the expression for the surrogate regret of FGTS in (31), we obtain
å (m
(GGS))= = Σ
Pi(aa(()) = - (ō.) = = (0()))))))))
aEA
<
(((a((0)) = (), ()) = a] -
aEA
where in the last we used the Cathy-Schwarz inequality. Due to the sparse optimal action property, all actions for which (a (0.) a) have most non-zero elements. Therefore,
Σ Pa (0.) (),E, aj)a (0.) (0(2)))) a)) < Σ Pa(a" (0.) a)s 1ss|pa-- 1(.
35

---

This, combined with the lower bound on ( (mibx) means that
( (FGTS)
Pr(a a)s|lua 0
aEA
2s ?
Σ (0,) a) - 1
7Cin
2
aEA
28
(T (mi)
mmin
Choosing = 1, this tells us that
(T)
(GTTS))2
2B
(G(())
Cmin
We bound the information ratio in three cases. First, suppose that Âc(H) & ( this case,
IR 33 (w) (o(1)D
IG,(u) < ( (PCT))) )
(T
48
(n)
Cmin
Next, we consider the case where Ar(w) (T
( (PGTS)) For any 7 E (0, 1].
((1 (1--1) ( (Ti (FGT)) + ((1 (1-7) (m) (FFGT)) + A
(mix)
IR; (
(1 (1-7)1 IG, (PGT)) (m)
(1G)(1)
We define [(>) = ((1 - - ( (FGTS) + +>ār(1))3 (+T(4)))(((GG((1) to be the RHS of the previous equation. One can verify that the derivative f(7)
f(()) ((1 Am (FTTS) + (p)))
(2(De(k) (M(PGT))) Am (MFGTT)))
(I)
and that f(7) is minimised w.r.t. 7 > 0 at R, where 7 is the positive solution of (2 = 0, which is
B n (FGTS)
7 (() (T( (FGTS))
That & is always positive follows from the fact that ((( A { FGTS)) If take the forerunner to be the mixture policy with = 7. In this case,
1, then we can
(mix)) = (2)32(A.(w) - A ( (1] 2
33) ( IR,
(Ge(1)
388
278
Cmin
Cmin
Otherwise, ? > 1, then
3 (FGTS)
Âe(H)
(
2
In this case, we can take the forerunner to be The surrogate 3-information ratio can then be upper bounded
IR. (3) (14
((())())()))
( (FGT)))2
22
9s
(G)(p)
IG,(1)
Cuin
Cmin
Therefore, one can always find value of 7 E (0, 1] such that
IR. (T. (mix)
27s
<
Cuin
36

---

G
Choosing the learning rates
This section is focused on the choice of the learning rates required obtain the bound of Theorem 2.
G.1 Technical tools
We start by collection of technical results to help with choosing a time- deme-dependent learning rate. Lemma 19. Let a; 2 0 and f: [0, oc) + [0, oo) be a nonincreasing function. Then
Eiza at f(x) dz.
Σ t=1
a
(33)
1=0
The proof follows from elementary manipulations comparing sums and integrals. The result taken from Lemma 4.13 of Orabona [2019], where complete proof is also supplied. The following lemma ensures that the learning rates are non-increasing.
Lemma 20. Let C1 > C2 > O and define d
log(C,t) then x is a non-decreasing sequence. C2t
Proof. Let & >> O, we have
log(Ci(t + 1)) log (Ctt (ct( log(Cit) + log [++ ((t)
< 1+ tlog(Cit) S $1+3 t
log( log(Cit)
log(Ci) (Ctt
where the first inequality uses log(1 + +x) I for any x > -1 and the second inequality uses
log(Cit) 2 log(C1) 2 because we assumed C 2 e. Since C2(++1) 1 + we can conclude that the sequence A is non-increasing.
Cat
G.2 Data-rich regime: Proof of Lemma 8
We start by focusing on the data rich regime, and we bound the following part of the regret bound given in Equation (13):
Cr
32
A A IR, (me).
(2)
Ar-1
Here, CT 5 2s log edT To proceed, let dr a a(t+)). where is a constant that
will optimize later. Because & + C. is increasing, we get that A S av know that for all 2 1, IR.
Cr
By
Lemma 7, we
dt
(2) (TT) s 2d, hence
CT
32 T
IR
Te
<
v CrdT
64 + av
CT
Σ t=1
T
AT-1
3
3
1=1
1
128
$
V CrdT
+
av CrdT
3
< + 128
3 a VCrdT
/2
/ GrdT,
where the second line uses the standard inequality Σn V S 2VT,, optimizing the expression (1 3 a) with the optimal choice = /
and and the last line obtained by
3
which yields the value
128
1 3. This concludes the proof of the claim.
37

---

G.3
Data-poor regime: proof of Lemma 8
We now focus on the data-poor poor regime and specifically on bounding the following part the bound given in Equation (13):
Cr
16
3 C3
V
322-1IR (TT).
AT-1
1=1
3 where a > a constant that
Here, CT = 5 + 2s log
edT
Now, we let d =
(Cuti ((+1)/e
$
we will optimize later.
Because + C. is increasing, we get that A--1 S a
Cr
By
ts
Lemma 7, the 3-surrogate-informatin ratio is bounded for all 2 1 as IR, (Tx) S the following holds:
(3)
54 Hence,
Cmn
AT-
Cr
16
3
C3
T
1
IR
33)
(
1 S (Cr)
a
Tvs VCmin
+ 488c (2)
(VC
T
13
[=1
1
TV
T Tv
s
-
(Cr)
+ 72c' v 20 (rr)
Vmmin
VC
{ a
T
+ 72c3 /2xx
(CT)
VCnin
TV
12 12-66 (c
Vinin
Here, we have applied Lemma 19 with the function f(x) = x and a; = to bound E
1-1/3 <
3 in the second line, the last line comes from the choice 4.
which optimizes the constant
L1 72cg 22) (as per Lemma 27). This proves the statement.
G.4 Joint learning rates, end of the proof of Theorem 2
In the section below, we present the technical derivation related to choosing the choice of learning
3C rate X, min(3, max( (A , x))))) where x(2) 128d(1+11) and x =1
CuiiyCmia
4-63 ((+1)ys
with C, = 5 + log edt This choice interpolates between the data-rich and data-poor regimes. As
a first step, we start by confirming via Lemma 20 that both x(2) and x are non-increasing and the bound of Theorem 1 holds with our choice of Xς.
First, note that our choice of learning rates ensures that d S holds as long as T larger than an absolute constant, and thus we focus on this case here (and relegate the complete details of establishing this absolute constant to Appendix G.5), To proceed, we define the (constant-frea)
and note that they correspond to the regret regret rates R2 VC,il and R$ = (4V Emin
bounds obtained when using the respective learning rates X and X per Lemma
We now consider the last time that the learning rates (3) and X (2) have been used, More specifically,
denote T2 maxft S T, x., 2 ( and T3 max (t S T, (3) 2 x Combining the
bound of Equation 13 and using the definition X; min max(A A (())))
(2)
)). the following bound
38

---

holds
RT
E
CT
min
[3 x- IR,
32
()
(T²): o
16
31 IR; (3) (Te))
-T-1
OT
E
min( 2, max (2)
AT- x -11)
(3)
T
+
min
32
min( 2. max (A x IRR
(2)
(Te),
16
%
3 3 2. max ( (3) )RR (3)
(TT.)
3
3
[=1
T
< E
Cr min
1
Σ
min
32
max (1
(3) IRR
(2) (TT).
16
siv 3 max
max (2)
IIR (Te)
(3)
(2) 1 (3)
3
3
T-1
-1-1
1=1
We can now separate the sum obtained at the last line based on which learning rate used at time
t.
Σ min
32
3
max
(2)
1-1:
1 IR,
2)
(TT):
16
3
03
3 max (2 1-1 2
IR, (3) (m+)
32
(2) (2)
(TT)) +
Σ
16
31
(3)
IR 3)
(mT)
3
3
12
(3)
2
10
(2)
T2
Ts
32
IR₁
(2)
(T)) +
Σ
3
31
IR, (3)
(TT).
3
3
t=1
Following exactly the same step as in the proof of Lemma 8, we further bound EA 22 2 (m.) 8 n
()) and Ein 3 J 31
(T.)
S 63 R/
The crucial observation is that which of x or A is bigger will determine whether R or R the term of leading order (up to some constants). More specifically, Let T be such that 1 N
T-1 which means that
(3)
3CT
Crv/Cmin T/8
Rearranging, this implies that v VTTT S
1284T
4-63
G
(Tv
which means that 12(2)
R(
Following the exact same steps, we also We apply this to the time T2 in which
Cmin
4
(3)
T-1 implies that (3)
(2)
4 (22)
have that -T-1
G R(3) and putting this together with the
T -T by definition. we have that
R
<
4
previous bound, we have
RT
5
CT
+8
2
211
+8 6b R!! T2
3
4-1
2
6
1 4. 63 ((3)
+8V
(2)
+8 6 R
S <4. 63 64.6
+8 6 (3)
$ 4. 63 R +4. +8 (3)
$ 16 6 R
where we use the fact that T + (33 is increasing and T2 5 <T,T3 T. (2)
Using the same argument as before, we have that \ 2 7/-11 and we can conclude that R/ S
68 R,3
39

---

Putting this together, with the previous bound, we have
RT
CT
(2)
88
V3
2
R
2 T2
8
1-866RR
63
T-1
3
((2)
T
8V
2
3
+
63
6
4
RT
2
2
2
8
PT
16
22 R
2
8
R +
88
16
R
2 s 32
Rt
3
where we use the fact that T + Rg is increasing and T2 S T.T3 S T. Evaluating the constants
numerically yields 16 63 x 29.07 S 30 and 32 / 3 R 26.13 27.
G.5 Upper bound on the learning rates
We now consider the case where the learning rates exceed 2, and show that this only holds for small
values of T. First, we have that x S 1 if
2
3CT
S
128dT
2
Rearranging the inequality and recalling Cr = 5 + 2s log
edT
this is equivalent to
15
38
edT
T2
log
32d
16d
Using the loose inequality log edT <
dl
we get that this condition is satisfied for any T 2 1.
Similarly, we have that 1 S 2 if
1
(CTVCmin 1
4 63
Tv8
We note that
Tr [AAT]) d
Cmin max mmin miiu( (EAng [AAT]] < max PEA(A)
MEA(A)
where the first inequality uses that the trace of a matrix is always bigger than d-times its small- est eigenvalue and the second inequality uses the fact that for any vector a, we have Tr(aa") )) EL_ a² < d max, |a,| S d because we assumed that all the actions are bounded in infinity norm. Hence the previous inequality will be satisfied if
Cr
5
4 63
TVo
2
Rearranging the inequality, this is equivalent to
3
200
T2 4 C. = 8/33 log(eT)) + /3s
+ 8 log
Applying Lemma 24 with a = 8/3s and b = v3s 20 inequality is satisfied for all
+ +8log( ()), we find that the previous
3
Sev3d 3d
T 2 2a log ea + 2h = 10
+ 16v 35 log
Vs
40

---

Thus, letting min = 40 + 16 3s log Bey be the constant given above, both learning rates V=
stay upper bounded by for all T 2 min and the upper bound on the regret given the previous subsection holds. Otherwise, additional min ( log ( in the regret. Putting this together with the bound proved in the previous section, we thus have that the following regret bound is valid for any T T21 1:
upper bound the instantaneous regret by 2 and this leads to an
edT
df' 30 5 2s log )
( [TV (VCmi
) +
(V's
(Vslog log d
Rr S min 27
5 2s log
/
This concludes the proof of Theorem 2.
Technical Results
We state and prove the remaining technical results.
Lemma 21. Let π E (AA), the function 0 + (T 0) is 2- 2-pischiitz with respect to the I norm. Let 2-Lisschitz with respect to the norm. Moreover
t 2 1, the function + E log (Y.)8,8,AA)) 0, O' are random variables, then
)}
5 < sup 10
E log
log
0'
(.,)),,
(Y, At)
Proof. Let 0,0 0' E O, we have
|r( 0) r(T,
Σ ((a)0--0'0)) 8'aa)
oEA
T(a)]{0 f.aa)
AEA
T(a) 11 ||||
aEA
S 10 0'111
Similarly,
(r)( (())-)'(8')) = mmx maxxr(a 0) max max 8') S max aeA
|r(0, -r(a, s 110 8'11
aed
aEA
Finally
0) ATT, - (0) 0¹) r(,, 0) < 0'
(r) + r(T,
Let write ((9,A)). r' = (8'' AA) and ro (0a, At). We have that Y, ru < where c, is I-sub-Gaussian Gaussian. For the negative log- begllikelihood, we then have
1
)
1
E log
log 0(Y, A.)
E [(00, Ai) Yy)² (10', A.) YJ
p(Y,(0,A.))
2
[rr - Y,) - (r' - -Y;)
2
1
E[(r (')(r +r -YY))
2
1
1 E [rr r')a]
E [(r r')(r +r' -2ro)l +
2
1 1 [l|e 0'11, leel,
< 2E [|| 0' +
2
where we use the fact that Ir + r' 2rol < 4.
Now if 0, O' are fixed, since E [ee] 0. we get
log p(, A,)
log
p(Y. A.))
2 - 011
41

---

If 0, 6' are random variables, the subgaussianity of e, implies that E [c]] Schwarz we have
S 1 and by Cauchy-
B 1 8'11, lell & V 0'12 Bk2 I sup 10 8'11-
This yields the second claim of the Lemma.
Lemma 22. (Hoeffding's 's Lemma) Let a bounded real random variable such that X E [a, almost surely. Let 1) # O, then have
log E (exp (nX) S [ 7(b a)²
(34)
7
8
Proof. See for instance Chapter 2 in Boucheron et al. [2013].
We now provide data dependent version of Hoeffding's lemma that is used in the analysis of the gaps in the optimistic posterior.
Lemma 23. (A data dependent version of Hoeffding's 's Lemma) Let X be real random variable and 1) + 0 be such that nxX almost surely, then we have
log E (exp (n) < [ + m/
X S [X]
(35)
Proof. Using the elementary inequalities log(x) S x 1 for x > 0 and E S 11++t+ for x S 1, we get that
log E (exp (1)X) - E (exp(()X) - 1]
77
"1
[nXX + 17 x²²
"1
E [X] + nB [x
The following lemmas help us to analyze when the learning rates are smaller or bigger than 1 Lemma 24. Let 1, 2 then, the equation 2 a loog et+ is verified for any t 2 2a log ea + 2b
2'
Proof. We let f(t) = t - a log et - b, we have that f((t) f() has unique solution a on Ja, oo) such that f(t) bounding a. The equation f(a)) = 0 is equivalent to
>
on [a, +20) and f(a) < 0. Hence
0f 2 a. We now focus on upper
log a
1.
Now taking the exponential and reordering this is also equivalent to
a
exp
o+b
exp
a
Let
9: (-00, -1]
0)
T. DE
The previous equation can be rewritten g (=0) exp
We define W-1 : 1-2 0)
(-o0, 1] as theffunctional) inverse g. The function g the branch of the Lambert function. We have that for any < -1, W=1
and that for any 2 -W + < 2 log(y).
Since g is decreasing its domain, W_1 is well-defined and decreasing. Moreover, for any x S -1
42

---

expp -+
W-1(g(z)) In particular, we have that a -aW-1 formulation to find an upper bound on a.
We will use that
a
We fix some 2 e. We have -2 log(y) S -1 hence W (-2 log(y)e! log()))))))) (=2log(v))(-22oott))) = -olog(y). which means that 2lo((y) - 1-1(- where y² = e(llngiu))
"
2 log(yy)
logiv)
Because of the elementary inequality 2 log(az) S for x 0, we conclude that y S y" Since y + -W-1(- ) is an increasing function we finally have that for any y 2 e
-W-1 (- 1/ S -W
(-- 1/
- 2 log(y)).
Applying this to y = a exp (atb) 2 e, we get
-a
2a log(y) 2a log ea 2b.
Since any 2 a will satisfy f(t) 2 0, this concludes our proof.
Lemma 25. Let f E then M, = exp([ (06) I, (0) II
0.Y.) A.
supermartin-
gale with respect to the filtration (Fi).-
Proof.
We have
0 A.)
(00,, A1) - Y2) 1002-(10,,A))) A1) -V?))
E
Fi-1, Ag
EE exp
Al
P(Y:|0o,_A)
c ((0 00, Ad) - E,)3
exp
Fi-1,
(00
0o. A,))
cxp
E E(exp (c
-u,, A.) Ad
2
((0 8o: A,)2
((0 Gu, A,))
exp
exp
2
where the inequality comes from the conditional subgaussianity of et. Finally, by the tower rule of conditional expectations
p
(Y, Ad)
p(Y,10, Ad) 00. Ar)
E
F
=
E
Fr-1, A
Fi-1 $1.
p(Y. A.)
L1 Proof of Proposition
This is coming from the fact that the is the constant minimizing the mean squared error. We remind the reader of the definition of the surrogate information gain and the true information gain for policy æ E ((A)
Σ T(a) / (10- ((0--(Qt)aa))a00000
IG
(36)
aEA
where ō(Q+) = Ey-qz [0] is the mean parameter under the optimistic posterior Q
(G) 1 Σ T(a) (10. a) (0o, a))² dQt (0),
(0),
(37)
43

---

Let's fix A, we have that
(10 a)) (10- ((Q)) - -0. a,,
(
+ - ((Q,) o)) ()() - 8b a) ((((Q)) 8o a))²
[10 ((Q)), a))² + + ((Q2), .) (O(O)) 0o. a)
Now using that ((QT) fo 8 dQ, (0) and integrating, get
/ ((0 8, a))² aQ, (0) 2 / (10 (10 - ((Q dQt
Multiplying by (a)) and summing over actions, we get the claim of the lemma.
1.2 Generalization of the AM-GM inequality
Dealing with the generalized information ratio requires bounding the cubic root of products. While could Hölder's inequality to deal directly with products, we find it more flexible variational form of this inequality. In all that follows, we let p > 1 be real number and be such not hard to check that q -ー We start by stating a direct consequence of the Fenchel- Young Inequality which can be seen as an extension of the AM-GM inequality.
that 1 + 1
P
Lemma 26. Let z. y O, then
x2
y
xy
(38)
p
9
With equality if and only if pxp-1_ =
Proof. One can check that the Fenchel dual of the function
f FRIR
R
x
3
P
is exactly (1) y (for non-negative y). Then the Lemma direct consequence of the Fenchel Young inequality and of its equality case.
Refining a bit this Lemma, we get the following variational form of the previous inequality Lemma 27. Let x, y 0, 0, then
(1
(39)
x
where o = (pp 1 with equality if and only if y 0
p=
y
Proof. We apply the previous lemma to / X and v 2
In order to go from the variational form to the product form, we may use the following result.
Lemma 28. Let a. B > 0, then
inf a ASO X
BA5 3
(40)
where cp =p p-1
satisfies cp cf
1, and the minimum is reached X* (p- p-1
Proof. Applying the previous Lemma to and y cp 3
30-1 yiclds the result.
44

---

Remark An alternative is to pick to make both terms equal resulting in the same result but with 2 as a leading constant. Now
P
Cp = p
p-1
exp
logp
+
P
log
P p -
P
1
p-
+
p
P
2.
With equality if and only if p 2. So, the choice of Cp always yields a better leading constant. However, c3 2 1.88 so one could argue that the gain is small. Since we will usually use Lemma 27, & will naturally appear and ep will cancel it, ultimately making the leading constant as simple as possible.
Experimental details
Here, describe implementation of the SOIDS algorithm in more detail, well the hy- perparameters of all the methods used in our experiments. To run the SOIDS algorithm, one must minimise IR, (2) (x:) w.r.t. in each round This is not straightforward, because IR, (πr) contains expectations the optimistic posterior Q When use the Spike-and-Slab prior in Appendix
B.2, we are not aware of any efficient method that can be used to maximise IR, (T). Instead, we draw (approximate) samples ((1), ..... ((M) from Q produce the estimates A.(T) and IG:(T) for the surrogate regret and the surrogate information respectively, where
(x = Σ
(a
1
Σ
M
Aa
(T)
Σ aEA
T
1
Σ
M
(10()) - a))
M
M 1=1
oEA
Here, Om is the sample mean 37
E/ 000) We then maximimse the approximate surrogate infor-
(2) mation ratio IR, (IT). where
(2) IR. (T) IG,(T)
(T)
To draw the samples ((1) ...., ((M), we use the empirical Bayesian sparse sampling procedure pro- posed by Hao et al. [2021]] which is designed to draw samples from the Bayesian posterior. To sample from the optimistic posterior, incorporate the optimistic adjustment into the likelihood. This method replaces the theoretically sound spike-and aadke--nd-laabb prior with a relaxation in which the "spikes" are Laplace distributions with small variance, and the "slabs" are Gaussian distributions with large variance. In particular, the density of this prior is
41 (0)
Σ p(7) II (0,)(0,) + (1 (1-71) -1)) ()))) T J=1
Here, (0) is the density function of a univariate Gaussian distribution, with mean and vari- ance Pl. and to is the density function of univariate Laplace distribution, with mean and scale parameter Po- p(7) is product of Bernoulli distributions with mean B. In our experiments, we always use A1 10. Po 0.1 and / 0.1. Also, we set the learning rates to r) = 1/2 and
X = mim
max() V
[lgg(edt/s)
log[edt/s) )2/8))
71 TO
dt
Implementing the OTCS baseline exactly would require us to compute the means of the distributions played by an exponentially weighted average forecaster with a sparsity prior. These distributions are the same as the optimistic posterior, except X, 0 (i.e. there is optimistic adjustment). In our implementation of the OTCS baseline, we draw samples using the same empirical Bayesian sparse sampling procedure, and then replace the exact means with the sample means. We use the same
45

---

choices for the parameters 7/, Pt. Po and 3. We set the radii of the confidence sets to the values given Theorem 4.7 of Clerico et al. [2025]
For the LinUCB baseline, we set the radii of the confidence sets to the values given in Theorem 2 of Abbasi- Yadkori et [2011]. For the ESTC baseline, we the exploration length Ti to 50 when d = 20, 100 when d = 40 and d = 100. These values were chosen based on a small amount of trial and error. The theoretically motivated values Theorem 4.2 of Hao et al. [2020] are much larger than these values. Also for ESTC, we set the LASSO regularisation parameter to À Allog(d)/5 which is the value given in Theorem 4.2 of Hao et al. [2020].
46


Reviews:
[{"review_id": "7k9Sgr3DXH", "reviewer": "Reviewer_FDVS", "summary": "This paper presents Sparse Optimistic Information Directed Sampling (SOIDS), an extension of the Optimistic Information Directed Sampling (OIDS) algorithm for sparse linear bandits. The key contribution is achieving optimal worst-case regret bounds in both data-rich $O\\bigl(\\sqrt{sdT}\\bigr)$  and data-poor $O\\bigl(sT^{2/3}\\bigr)$ regimes simultaneously, without Bayesian assumptions. The authors adapt the optimistic posterior framework to allow time-dependent learning rates and provide theoretical guarantees showing SOIDS is the first frequentist algorithm to achieve best-of-both-worlds performance in sparse linear bandits. The paper includes experimental validation demonstrating competitive performance against specialized algorithms in both regimes.", "questions": "1. In Theorem 2, the learning rate λt = min(1/2, max(λt^(2), λt^(3))) switches between two regimes. Could you provide more intuition about why this specific switching mechanism is necessary? How sensitive is the algorithm's performance to the exact switching point?\n2. Theorem 3 provides an instance-dependent bound for the data-rich regime. Is it possible to obtain a unified instance-dependent bound that smoothly interpolates between both regimes, as mentioned in Section 4.3?", "limitations": "yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n- **Solid Theoretical contribution**: First frequentist algorithm achieving optimal regret in both data-rich and data-poor regimes for sparse linear bandits. Provides both worst-case bounds and instance-dependent guarantees.\n- **Novel technical approach**: Extends optimistic posterior framework to handle time-dependent learning rates, enabling adaptive algorithms.\n- **Clear presentation**: Paper is well-written with good intuition for the main ideas.\n\n### Weaknesses:\n- **Limited experimental validation**: Only basic synthetic experiments with small dimensions and specific parameter structures.\n- **Restrictive assumptions**: The assumption of known sparsity level s is restrictive in practice. The authors should discuss potential adaptations for unknown sparsity.", "was_revised": false, "final_justification": "", "rebuttal": "The authors thank the reviewer for their insightful comments and questions. \n\nRegarding known sparsity: this is a common assumption to make in this setting. The sparsity level could be replaced by a known upper bound on the sparsity, and the bounds would then scale with this upper bound. If there is no known upper bound on the sparsity, the best regret bound that we are aware of is of the order $s\\sqrt{dT}$ (Jin, Jang and Cesa-Bianchi, 2024). We can match this regret bound by making two modifications to SOIDS. First, the subset selection prior can be modified such that it has support for subsets of all sizes and does not require knowledge of $s$. One can simply replace the sum in the denominator by $\\sum_{k=1}^d2^{-k}$ and verify that Lemma 3 still holds. The only other place in which our $\\sqrt{sdT}$ regret bound requires knowledge of the sparsity is in the value of $\\lambda_t$. If one chooses $\\lambda_t = 1/\\sqrt{dT}$, then we no longer require knowledge of $s$, and get a regret bound of the order $s\\sqrt{dT}$. The situation for the $(sT)^{2/3}$ regret bound is more complicated. If the subset selection prior is extended to have support for subsets of all sizes, then samples from the prior are no longer $s$-sparse with probability 1, and so the sparse optimal action property might not be satisfied. Since samples from the \"full\" prior are still sparse with high probability, one can perhaps adapt our bounds on the 3-information ratio such that when $\\lambda_t$ is set independently of $s$, one has a regret bound of the order $sT^{2/3}$. The situation is the same for the Bayesian version of sparse IDS (Hao, Lattimore and Deng, 2021).\n\nRegarding the specific choice of the switching mechanism, the basic idea can be understood intuitively as follows. The optimal learning rate for the data-rich regime ($T >> \\mathrm{poly}(\\frac{d}{s})$) is $\\lambda_t^{(2)}$ and the optimal learning rate for the data-poor regime is $\\lambda_t^{(3)}$. Therefore, for rounds $t$ such that $t >> d/s$, we should use $\\lambda_t^{(2)}$ and for all other rounds we should use $\\lambda_t^{(3)}$. Using the expressions for $\\lambda_t^{(2)}$ and $\\lambda_t^{(3)}$ in Theorem 2, the inequality $\\lambda_t^{(2)} \\geq \\lambda_t^{(3)}$ can be rearranged to obtain (roughly) $t \\geq d^3/s$. This means that if we take $\\lambda_t = \\max(\\lambda_t^{(2)}, \\lambda_t^{(3)})$, we will be using the correct learning rate for each regime.\n\nFor a more technical explanation, the following might help. The idea is that we want our regret bound to adapt to each possible regime. In the data poor regime, we want to obtain the rate $R_T^{(3)} \\propto (sT)^ \\frac{2}{3}$, and in the data rich regime, we want to match the $R_T^{(2)} \\propto\\sqrt{sdT}$ rate. The bound obtained at the beginning of the analysis of Theorem 2 (Equation (12) line 258) scales with both the 3 information-ratio and the 2-information ratio. The tricky part is now to chose the learning rate. If we choose the learning rate $\\lambda^{(2)} \\propto \\frac{1}{\\sqrt{sdT}}$ to optimize the term with the 2-information ratio, we would obtain the data-rich rate of $R_T^{(2)} \\propto \\sqrt{sdT}$. If we choose the learning rate $\\lambda^{(3)} \\propto \\left(\\frac{1}{sT}\\right)^\\frac{2}{3}$ to optimize the term with the 3-information ratio, we would obtain the data-poor rate of $R_T^{(3)} \\propto (sT)^\\frac{2}{3}$ . The relevant question is now whether or not there is a way to chose the learning rate to get both rates at the same time. The essential observation now is that the bigger learning rate always matches the best regret rate. More specifically we have that $\\lambda^{(2)} \\lessapprox \\lambda^{(3)}$ if and only if $R_T^{(2)} \\gtrapprox R_T^{(3)}$. This can be seen by comparing the ratios of the learning rates and the regret rates. As a result, if we're trying to obtain the best regret rate, we should always pick the bigger learning rate out of $\\lambda^{(2)}$ and $\\lambda^{(3)}$ which is done by picking the maximum. When a time varying learning rate is used, the story is similar with a slightly more complicated analysis of the regret coming from having used the wrong learning rate in the past.\n\nThe question of a unified instance-dependent bound is extremely interesting. The analysis of Theorem 2 relied on using the fact that the learning rates only switch once, starting with the learning rate $\\lambda_t^{(3)}$ and then at some point switching to $\\lambda_t^{(2)}$. Such a behavior cannot be guaranteed when $\\lambda_t^{(2)}$ and $\\lambda_t^{(3)}$ are data-dependent, because the information ratios might behave differently than their respective upper bounds. It turns out that this switching argument is not\nnecessary and can be replaced by considering the last time that either of the two learning rates is used. Using this approach, one can simplify the proof of Theorem 2 and prove a unified instance-dependent bound that smoothly interpolates between the two regimes. We discovered this technique shortly after submission and will include it in the final version."}, {"review_id": "rbL3vYwWaC", "reviewer": "Reviewer_swR4", "summary": "This paper addresses the sparse linear bandit problem. The minimax regret in this setting depends on whether the problem instance falls within the data-rich regime or the data-poor regime. In the former, the time horizon $T$ is significantly larger than the dimension $d$ and the optimal regret is of order $\\sqrt{s d T}$ with $s$ being the sparsity level, while the latter concerns high-dimensional problems, where the optimal regret has a worse $T^{2/3}$ rate but can be dimension-independent in some cases. While achieving near-optimal regret in both regimes by one adaptive algorithm has only been shown in the Bayesian setting (via the information directed sampling approach), this paper presents the first algorithm that achieves this feat in the non-Bayesian (frequentist) regime. The adopted approach extends the optimistic information-directed sampling algorithm of Neu et al. (2024) to the sparse linear bandit setting. It features a modified choice of posterior distribution and employs a time-dependent (or history-dependent) learning rate.", "questions": "* Aside from the time-dependent learning rate, was the new adjustment in the definition of the optimistic posterior (compared to Neu et al. 2024) crucial for obtaining regime-adaptive bounds in the present setup? You mentioned that it simplifies the analysis, could you expand more on that? I also wonder if the 'optimistic' label is still accurate here as the posterior seems to lend importance to parameters under which the learner would have incurred large regret up to the present time.\n* How strict is the assumption that the sparsity level is known? Can it be dropped at the cost of a slightly worse bound as in Hao et al. (2020)?", "limitations": "Aside from the brief discussion on computational challenges in the last two sections, limitations of this work are scarcely discussed as I mentioned in the strengths/weaknesses section.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The primary contribution here is achieving non-Bayesian analogues of the regime-adaptive Bayesian bounds of Hao et al. (2021). In this manner, the paper addresses a more practically relevant setup and shows that regime adaptivity is also possible there. Additionally, the adopted time-dependent and history-dependent learning rates lend the algorithm more flexibility compared to similar approaches.\n\nOn the other hand, I feel that little has been highlighted in terms of the shortcomings of the results. For example, the data-poor bound scales with $s$ instead of $s^{2/3}$ like in the upper bound of Hao et al. (2020) or $s^{1/3}$ in the lower bound presented in the same paper. This is not a huge drawback as the focus here is on dimension-independence (indeed, this is also the case in Hao et al. 2021); however, this should still be mentioned to clarify what is meant by 'near-optimality'. Likewise, it is important to emphasize that $C_\\text{min}$ (featured in the data-poor bounds) can be dimension-dependent, depending on the geometry of the action set. Concerning the instance-dependent guarantee of Theorem 3, I find its significance a bit questionable; even if it improves upon the worst-case bound, which (interpretable/relevant) property of the instance can be exploited by this result? Overall, even if novelty is present in some parts of the algorithm and the analyses, the obtained results arguably constitute a modest leap from the current state-of-the-art.\n\nMinor correction: in line 94, I believe it should be $C_\\text{min}^{-1/3}$.", "was_revised": true, "final_justification": "After reading the other reviews and the rebuttal, my evaluation remains on the positive side. However, I think it is important that the authors highlight in the revised version the shortcomings that have been raised so far. Namely, the gap between your bound and the lower bound in terms of the dependence on $s$ (or how to improve it as claimed), the sparse optimal action assumption and its implications. Also, I think it is important to detail rigorously in the paper how Theorem 3 implies a first order regret bound as you claimed in the rebuttal, or some interpretable data-dependent improvement; otherwise, the significance of that result would remain unsupported. Finally, the paper can also benefit from including the discussion you provided in your rebuttal regarding the case when $s$ is unknown.", "rebuttal": "The authors thank the reviewer for their insightful comments and questions.\n\nThank you for pointing out the sub-optimal scaling in $s$ in the data-poor regime. We have inherited this scaling from the work of Hao, Lattimore and Deng (2021), and in particular, from their $ s^2 $ bound on the 3-information ratio. This leads to a data-poor regret bound scaling with $s$ rather than $ s^\\frac{2}{3} $. Note that the data-poor regret bound in Hao, Lattimore and Deng (2021) also scales with $s$ whenever the number of actions is large or infinite, which is arguably the most interesting situation. Though the lower bound in Hao, Lattimore and Wang (2020) indeed scales with $s^{1/3}$, the best achievable scaling is $s^{2/3}$. This follows from the lower bound in Jang, Zhang and Jun (2022). Since the initial submission of our work, we were able to obtain a tighter bound of order $s$ for the 3-information ratio. This directly translates to a $(sT)^\\frac{2}{3}$ regret bound by setting lambda accordingly (not only improving the results in the present paper but also the rates for the Bayesian algorithm of Hao, Lattimore and Deng). We will update the paper accordingly for the final version.\n\nWe will comment on the fact that the dependence of the data-poor regret bound on $C_{\\min}$ can introduce undesirable dimension-dependence.\n\nRegarding the instance-dependent bounds that we provide, it is well known that an algorithm tuned to optimize a worst-case\nregret bound might perform poorly in practice, since worst-case bounds are often very conservative. Conversely, a\nbound scaling with the actual information ratio might yield\na more practical algorithm. Thought it is not the subject of the present work, it can be shown that OIDS with data-dependent learning rates enjoys first-order bounds for contextual bandits without prior knowledge of the best cumulative loss. In the contextual bandit setting, it is known from the work of Neu, Papini and Schwartz (2024) that the information ratio scales with the surrogate loss of the selected action, and adapting to that\nscaling will give a first-order bound in which the time horizon is replaced by the cumulative loss of the best action.\nThis can lead to significant improvements in \"easy\" instances in which the cumulative best loss is small. Previous\nwork requires knowledge of this quantity to tune the learning rate. On the contrary, with our instance-dependent analysis\nwe can adapt to this quantity on the fly without prior knowledge.\n\nThere is indeed a typo on line 94, It should be $C_{\\min}^{-1/3}$. Thank you for spotting this.\n\nThe new adjustment to the optimistic posterior allows us to deal with the \"Bellman error/Underestimation error\" and the\n\"Feel-good term/ Best loss gap\" in a unified manner. For the data-independent bound (Theorem 2), it is possible to\ndirectly bound the underestimation error as in Neu, Papini and Schwartz (2024), which would lead to the same scaling as obtained here\n(and allow us to drop the requirement that the learning rate should be smaller than $ \\frac{1}{2} $). For the instance-dependent version, it might be possible to get a similar\nbound without this adjustment to the optimistic posterior, but we don't know for sure. In any case, we find it quite insightful to frame everything this way, so that Theorem\n1 directly relates the true regret to the surrogate regret.\n\nThe assumption of known sparsity can be relaxed somewhat. If there is a known upper bound on the sparsity, then the sparsity level can be replaced this upper bound, and the regret bounds would then scale with this upper bound. If there is no known upper bound on the sparsity, the best regret bound that we are aware of is of the order $s\\sqrt{dT}$ (Jin, Jang and Cesa-Bianchi, 2024).\nWe can match this regret bound by making two modifications to SOIDS. First, the subset selection prior can be modified such that it has support for subsets of all sizes and does not require knowledge of $s$. This can be achieved by replacing the sum in the denominator by $\\sum_{k=1}^d2^{-k}$ and verifying that Lemma 3 still holds. The only other place in which our $\\sqrt{sdT}$ regret bound requires knowledge of the sparsity is in the value of $\\lambda_t$. If one chooses $\\lambda_t = 1/\\sqrt{dT}$, then we no longer require knowledge of $s$, and get a regret bound of the order $s\\sqrt{dT}$. The situation for the $(sT)^{2/3}$ regret bound is more complicated. If the subset selection prior is extended to have support for subsets of all sizes, then samples from the prior are no longer $s$-sparse with probability 1, and so the sparse optimal action property might not be satisfied. Since samples from the \"full\" prior are still sparse with high probability, one can perhaps adapt our bounds on the 3-information ratio such that when $\\lambda_t$ is set independently of $s$, one has a regret bound of the order $sT^{2/3}$. The situation is the same for the Bayesian version of sparse IDS (Hao, Lattimore and Deng, 2021)."}, {"review_id": "GfGBO1o4jG", "reviewer": "Reviewer_3bN9", "summary": "This paper applies the OIDS algorithm by Neu et al. (2024) to the sparse linear bandit problem and establishes a cumulative regret bound of $\\tilde{\\mathcal{O}}(\\min\\lbrace \\sqrt{sdT}, sT^{2/3} \\rbrace)$.", "questions": "1. In Appendix C.1, why does the prior assign additional probability to $k = 1, \\ldots, s-1$-sparse vectors? If the sparsity level $s$ is known, wouldn't a uniform distribution over $\\Theta$ be more natural?\n\n2. In the proof outline of Theorem 1 in the main text, the equation after line 245 contains a term $\\mathbb{E} \\left[ \\frac{\\eta}{\\lambda_T}( L_T^{(1)}(\\theta_0) - L_T^{(1)}(\\theta_T)) \\right]$. While this term is not bounded in the outline, it seems that it should be included in the statement of Lemma 4. Could the authors clarify this point?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 1, "strengths_and_weaknesses": "Strengths\n\n1. The algorithm achieves both $\\tilde{\\mathcal{O}}(\\sqrt{T})$ and $\\tilde{\\mathcal{O}}(T^{2/3})$ regret bounds, making it the first algorithm to do so in the sparse linear bandit setting.\n\n2. The paper proposes adaptive learning rate schedules that do not require knowledge of the time horizon, which is not common in optimization-based sequential decision-making algorithms.\n\nWeaknesses\n\n1. In Appendix E.3, it appears that the bound for the 3-surrogate information ratio only holds under the sparse optimal action assumption. While the authors argue that the regret lower bound is invariant under this assumption, it is unclear why the upper bound on the information ratio should also remain the same. Without this assumption, it seems the $s$ factor must be replaced with a $d$ factor, resulting in a significantly worse regret bound of $\\tilde{\\mathcal{O}}(dT^{2/3})$ than the stated $\\tilde{\\mathcal{O}}(sT^{2/3})$ bound. Additionally, the $\\tilde{\\mathcal{O}}(sT^{2/3})$ bound is still looser than the previously known $\\tilde{\\mathcal{O}}((sT)^{2/3})$ bound [Hao et al. 2020] by a factor of $s^{1/3}$.\n\n2. The paper’s independent contribution is not sufficiently explained. The summary of contributions at the end of the introduction gives an impression that the main contribution is setting an appropriate prior and computing the information ratio for the sparse linear bandit problem, and the rest follows directly from Neu et al. (2024). The method of choosing history-dependent learning rates in Theorem 3, which is another emphasized contribution, is the same with the analysis of AdaGrad in Orabona (2019) and is somewhat hard to say it is novel - although I admit it was never explicitly mentioned in the sequential decision-making context.", "was_revised": true, "final_justification": "I had two concerns about the original submission, and they are mostly resolved by the authors' answers.\n\n1. The analysis requires an assumption (sparse optimal arm assumption) to achieve the $O(\\text{poly}(s)T^{2/3})$ regret bound, but was not introduced in the main paper and not properly discussed even in the appendix. The authors promised that they would make the assumption explicit and, instead of presenting their result as the best-of-both-worlds bound, they would present it as an extension of Hao et al. (2021), extending from the Bayesian regret to the frequentist regret. I am satisfied with this change and have no further concerns regarding this point. I only hope the other reviewers are aware of this change as one of the main contribution (or at least its presentation) has been retracted.\n\n2. The independent contribution of this paper was vague, which was a question asked by other reviewers as well. The authors have provided kind explanations and promised revision. To this end, due to the promised change of presentation mentioned above, I think the authors would have to be careful and explicit about describing what was achieved by Hao et al. (2021), Neu et al. (2024), and what is newly achieved in this paper. While the main contribution seems to follow from combining the analysis of the two papers, there are still additional contributions as the authors have clarified, which I think is sufficient for acceptance.\n\nIn conclusion, assuming that the contribution of the paper is explained well in the revision without any overstatements or understatements, I believe that the paper merits acceptance and have increased my score accordingly.  \nThat said, although the authors might disagree, my current impression is that the contribution consists of several minor (yet meaningful) improvements rather than having a major one, and therefore I have not raised my score further.", "rebuttal": "The authors thank the reviewer for their insightful comments and questions.\n\nIt is true that our bound on the 3-information ratio requires the sparse optimal action property. We will make this clear in the main text of the paper. It might be the case that the sparse optimal action condition is actually not necessary for obtaining dimension-independent bounds on the 3-information ratio. However, as far as we are aware, it is not known whether this is an artifact of the current analysis or a fundamental property of the 3-information ratio.\n\nThank you for pointing out the sub-optimal scaling in $s$ in the data-poor regime. We have inherited this scaling from the work of Hao, Lattimore and Deng (2021), and in particular, from their $ s^2 $ bound on the 3-information ratio. Note that this is also where the sparse optimal action property is required. This leads to a data-poor regret bound scaling with $s$ rather than $ s^\\frac{2}{3} $. Since the initial submission of our work, we were able to obtain a tighter bound of order $s$ for the 3-information ratio. This directly translates to a $(sT)^\\frac{2}{3}$ regret bound by setting lambda accordingly (not only improving the results in the present paper but also the rates for the Bayesian algorithm of Hao, Lattimore and Deng). We will update the paper accordingly for the final version.\n\nWe will try to highlight here the independent contribution of this work.\nOne of our main contributions is to allow the use of time-varying learning rates and data-dependent\nlearning rates for the optimistic posterior. This is not possible in Neu, Papini and Schwartz (2024) or Zhang (2022). All existing bounds derived from the analysis of the optimistic posterior\nrequire prior knowledge of the time horizon (or the best loss in hindsight). This result is not a direct application of the methods highlighted in the Adagrad paper and requires additional work. One could think that the regular analysis of FTRL could be applied to allow for time varying learning rates by using the monotonicity of the dual to\nperform the usual telescoping of the potential. Unfortunately this is not possible as only some part of the loss is\nscaled by the time varying learning rate (compared to the whole loss in the usual analysis). This seemingly simple fact\ncompletely breaks the analysis and makes it unclear how to proceed. Our solution is to replace the monotonicity of the\ndual (which doesn't hold here) by Lemma 9 which will still allow the telescoping of the potential. To apply Lemma 9, we\nneed one of the losses to be non-negative. To ensure that this is the case, we introduce the Maximum likelihood Estimator at every time step.\nNone of those results are standard and they required significant work to prove. We completely agree with the reviewer that going from Theorem 2 to Theorem 3 relies on setting up the learning rate to\nscale with the information ratio in a way that is similar to the analysis of AdaGrad. We note that this step is only\npossible because we are able to use time-dependent and data-dependent learning rates.\n\nThe analysis of Lemma 3 doesn't require previous knowledge of the sparsity and the result continues to hold\neven if we don't restrict the prior to a given sparsity level. As such, if we only had an upper bound on the sparsity\nlevel, we could use it to compute the prior and still adapt to the true sparsity.\nThe true sparsity is only needed\nin computing the 3-information ratio, which is why we restrict the prior to s-sparse parameters. If we only wished to\nuse the 2-information ratio, we could use the prior without any sparsity level restriction.\nWe agree with the reviewer that the bound of Lemma 3 would continue to hold with a uniform prior on the sparsity level\n$s$ but we would lose the nice properties pointed out before.\n\nThank you for the great catch\non line 245, this likelihood term is indeed controlled by Lemma 4 as can be seen in its proof in Appendix B but the term is\nmissing from the statement of Lemma 4, we'll update it for the final submission."}, {"review_id": "fmjYA1z9Q5", "reviewer": "Reviewer_KJfM", "summary": "The authors propose a new method (SO-IDS) that introduces sparsity to the IDS framework. It is an adaptation of the OIDS algorithm in Neu, Papini, and Schwartz [2024]. The key idea is to reduce the per-round computational burden by restricting sampling to a small, adaptively chosen subset of arms, rather than computing over the full action set. The authors propose two sparse variants: Uniform SO-IDS and Greedy SO-IDS. They prove that SO-IDS preserves the core theoretical performance guarantees of IDS in terms of regret bounds while significantly improving computational efficiency. The approach is validated empirically on synthetic and real-world bandit problems.", "questions": "1) Can the sparse sampling strategy extend to linear or contextual bandit settings, where the action space is large or continuous? If so, how would sparsity be enforced?\n\n2) Can the authors better explain how the framework developed in this paper depends on & differs from the prior work by Neu, Papini, and Schwartz 2024? \n\n3) How sensitive is the performance to the size of the subset of arms considered each round? Could the authors suggest a principled or adaptive way to select this size?", "limitations": "This paper is theoretical and there is no specific discussion on limitations or potential societal impacts.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: (1) Very solid technical paper. The authors provide solid theoretical regret guarantees and proof to justify the soundness of the sparse sampling design. (I do need to mention a caveat that I did not read the full proof, and I am not very familiar with the prior work by Neu, Papini, and Schwartz in terms of the technical details.) (2) A new perspective to improve IDS efficiency through sparsity. (3) The algorithm shows significantly better computational efficiency without sacrificing performance -- this highly relevant for large-scale online learning applications, where sparsity can allow more efficient design. \n\nWeaknesses: (1) The proof part can be further streamlined to improve readability. (2) The greedy SO-IDS algorithm is empirically strong, but a better (more sound) motivation could be provided. (3) It is unclear how the framework generalizes to structured or infinite action spaces (e.g., linear or contextual bandits).", "was_revised": true, "final_justification": "I’ll retain my positive rating.", "rebuttal": "The authors thank the reviewer for their insightful comments and questions.\n\nRegarding the comment about the motivation for the greedy SO-IDS algorithm, could the reviewer please provide us with more detail about what they mean by the greedy SO-IDS algorithm?\n\nRegarding the comments about how the framework generalizes to structured or infinite action spaces, such as linear or contextual bandits, the setup we consider directly extends to linear bandits without sparsity and contextual bandits (see Neu, Papini and Schwartz, 2024 for instance). The definition of the information\nratio naturally extends to contextual bandits by replacing all losses by their contextual counterparts. For linear\nbandits, the 2-information ratio can be shown to be bounded by $d$. The other difference is the choice of the prior and\nthe maximum likelihood estimator. In the absence of sparsity, a uniform prior is suitable, and for the MLE analysis, the same type of\ncovering number argument will apply.\n\nThe framework we develop in this work builds upon the analysis of the optimistic posterior and the\nOIDS algorithm from Neu, Papini and Schwartz (2024). The main differences are as follows:\n- We specialize their result to the sparse linear bandit settings. This requires the adaptation of some of the arguments (choice of the priors, covering of the sparse parameter space). In this setting we are able to match the performance of Bayesian SIDS and get the first frequentist algorithm that get the best worst-case regret in both the data-rich and data-poor regime.\n- We replace the Best-loss-gap by the difference between the regret and the surrogate regret. Conceptually, it reflects the fact that we are not interested in our posterior placing a lot of mass on parameters with high potential rewards but on making sure that the surrogate regret is an upper bound on the true regret. Moreover, this simplifies the analysis and allows us to more easily prove data-dependent bounds.\n- We provide an analysis of the optimistic posterior valid with time dependent(and data-dependent) learning rates. This is one of the main limitations of the work of Neu, Papini and Schwartz (2024) (and Zhang, 2022), which we remove. While the results presented here are specialized to sparse linear bandits, this analysis is very general and can easily be extended to contextual bandits or even to decision-making with side observations.\n\nWould the reviewer be able to provide us with more details regarding the last question about the size of the subset of arms considered at each round? The algorithm considers all possible arms at each round. \nOn the computational side, it is known that the IDS policy is supported on at most 2 actions so a\nsearch algorithm can identify the IDS policy with a computational complexity $ O(K^2) $. Moreover, one can approximately\noptimize the IDS policy by playing a mixture of an informative and a greedy action which only requires $O(K)$ complexity\nto compute."}]

Author rebuttal:

Meta-review: This work extends the OIDS algorithm to the sparse linear bandit setting that enjoys a dimension-dependent regret of $O(\sqrt{dsT})$ and a dimension independent regret of $O((sT)^{2/3})$ simultaneously. This is the first work to do so in a non-Bayesian setting.

All reviewers agree that achieving the regret bounds simultaneously for the data-rich and data-poor setting is a great contribution. Further, reviewers were happy with the extension of the optimistic posterior framework to handle time-dependent learning rates.

Multiple reviewers had expressed concerns about the scaling of $s$ in the dimension independent regret, the novelty of the technical contributions and the requirement that $s$ is known in advance by the algorithm. After a careful rebuttal these concerns have been addressed and I am happy to recommend the paper for acceptance. I would urge the authors to implement the updated regret bound sketched out in the rebuttal, together with a more careful discussion about the novelty of the technical contributions.
Decision: Accept (poster)