A Novel General Framework for Sharp Lower Bounds in Succinct Stochastic Bandits
Authors: Guo Zeng
Jean Honorio
Venue: NeurIPS 2025 poster ()
Keywords: Bandits; Lower bounds; Sparsity; Low rankness
Primary area: reinforcement_learning

Abstract: Many online learning applications adopt the stochastic bandit problem with a linear reward model, where the unknown parameter exhibits a succinct structure. We study minimax regret lower bounds which allow to know whether more efficient algorithms can be proposed. We introduce a general definition of succinctness and propose a novel framework for constructing minimax regret lower bounds based on an information-regret trade-off. When applied to entry-sparse vectors, our framework sharpens a recent lower bound by (Hao et al, NeurIPS 2020). We further apply our framework to derive novel results. To the best of our knowledge, we provide the first lower bounds for the group-sparse and low-rank matrix settings.

A Novel General Framework for Sharp Lower Bounds in Succinet Stochastic Bandits
Guo Zeng
School of Computing and Information Systems, The University of Melbourne guo zengōstudent. unimelb. edu. au
Jean Honorio
School of Computing and Information Systems, The University of Melbourne, and ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications jean. www.rooounimemelle...looooooe edu.
Abstract
Many online learning applications adopt the stochastic bandit problem with a linear reward model, where the unknown parameter exhibits succinct structure. We study minimax regret lower bounds which allow us to know whether more efficient algorithms be proposed. We introduce general definition of suceinetness and propose a novel framework for constructing minimax regret lower bounds based on information-regret trade-off. When applied to entry-sparse vector, our framework sharpens a recent lower bound by [7]. We further apply our framework derive novel results. To the best of our knowledge, we provide the first lower bounds for the group-sparse and low-rank matrix settings.
1 Introduction
Stochastic bandits model online learning problems, where an agent is evaluated over its interactions with an initially unknown and memory-less bandit machine. At each round f, the agent (stochastically) plays an action A, to the machine and (stochastically) receives real-valued reward y/+ The memory- less nature allows defining optimal action that maximizes E[yr]. independent of the past interactions. Against those optimal actions, the agent's 's regret up rounds on specific bandit instance can be calculated. Assuming bounded single-round regret, it is desirable for algorithms achieve sub-linear regret rate onn) across a class of bandit instances, called the assumption class.
In real-world applications like advertising recommendation 6 and personalized healthcare systems 3. automated decision- -akiin often involves high high-dimensional data. To enable effective algorithm design, one common modeling approach assumes linear reward: E[yd] (A,, f), where the action represented by an associated data vector or matrix A,, and the bandit instance by a parameter of the same shape but with a succinet structure. For example, entry-sparse bandits also known as Lasso bandits or sparse linear bandits-assume that 0 E IRd has its number of non-zero entries limited to & d [5). Alternatively, if 0 is organized into matrix in Rdi xds it may be constrained to have a low rank s & min(d, dz), to group-sparse with no more than & dj non-zero rows, or to exhibit other structured forms [12]. We consider these bandits to be succinct linear bandits, differing in how they impose succinct constraints on
While upper bounds guarantee the regret growth of a specific algorithm across an assumption class, minimax lower bounds apply to all possible algorithms on that assumption class, and are usually established by identifying hard bandit instances tailored to any given algorithm. To illustrate, suppose that A, d is be chosen from the standard basis {el 62, ..., ex) and E Rd has only one non-zero entry. When d > given any algorithm, there obviously exists tailored 0 to cause that
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Some results obtained with our novel framework, compared to existing upper bounds from algorithms and prior lower bounds. The number of rounds is denoted by n. For entry-sparse vectors, d is the dimension and s is the number of non-zero entries. For low-rank matrices and group-sparse matrices, d1 is the number of rows and d2 is the number of columns. For low-rank matrices, s the matrix rank, while for group -papp--prsseeeeee matrices, s is the number of non-zero rows. Cmin is quantity measuring to what extent the action set admits a well-condition exploration, properly introduced in Definition 4.1
Upper Bound from Algurithms
Prior Lower Bound
Our Lower Bound
Entry-
((vsdn) in
0(min (Cmii //3///3 vdn)) Mmmin mia
(03 2/3 vdsn))
min
sparse
( (o)( in 10
du))
in 7
in Curollary 4.1
vector
0 sn log( in
12( sdn) in
O OCC
2/3) in 0(s ////3 /og(dn) in
2/3 8 2/8 2/3)
Low-
((dh + d2) 12)3 in
None
M(min (C
1/3
a 2////233 vdid2sn))
rank
((dd + dg) 3/22 sn
in Corollary 4.3
matrix
0 log(d: d1 d2)) in
Group-
((Sddd),n) in g
None
Q(min (C ( 2/3 vdldgn))
sparse
0 1//// (vd2+ + d))
in Corollary 4.2
matrix
in 12
algorithm linear regret. Since the entry-sparse 0 with 1 can also be interpreted as low-rank or group-sparse, the (2(n) regret is unavoidable in the data-poor regime (n < d) for succinct linear bandits without extra constraints.
Related Work. For eptry-sparse vector bandits, 1 gives lower bound O sdn) in the data- rich regime by emulating in parallel canonical multi-armed bandits, each with d/s arms and a lower bound Q2 ( ((d/s)m) established by (2). A matching upper bound O sdd) achieved by an onlinc-to-confidenec--
conversion algorithm in []] which works arbitrary action set and thus confirm the optimal rate 0(vsdn) in the data-rich regime. To ease the polynomial dependence on d, various constraints are introduced to study refined assumption classes [1 [3] [4], most of them focusing upper bound analysis for their proposed algorithms. One closely related previous study by (7] considers eptry-sparse bandits with a fixed action set A that allows for a well-explored sampling distribution, where the minimum eigenvalue of the population covariance matrix can be lower bounded despite growing d. By creating an information-regret trade-off, they construct a lower bound of Q( MainnCT/// (A)s" (A)s)/nn //n, vdn)), where Cmia is the lower-bounding quantity,
This lower bound nearly matches the upper bound O(C (()ss" (A4)"//">??
//²) for their explore-sparsing then-commit algorithm in the data-poor regime. It is also popular to study the contextual setting [10 13 [4] where action A, is chosen from a set of stochastically generated contexts, making it easy to impose complicated assumptions on the more passively available action data (At)
Other succinct linear bandits are less investigated. For low-rank matrix bandits, an upper bound of ((d) + / /sn) is established for different approaches: [9] developed an ppplloe-susspace-eeeee refine algorithm for bi-linear bandit setting, where the reward is computed the bi-linear product of the matrix parameter with the left and right arms. [8] extended the algorithm to the generalized linear setting under mild assumption on action data and the singular values of the low-rank parameter. For group-sparse matrix bandits, O(vsd, sds d2n) is given by [8] in an attempt to unify bandits with structured parameter in the contextual setting by constructing high-probability confidence ellipsoids. Under the restricted eigenvalue condition in the contextual setting, [12 offers a general framework of explore-sparsiee wwwpssspaattttt----oeeee commmm algorithms to achieve a common upper bound of (ss 2/a) on entry-sparse, low-rank, group-sparse bandits, and their novel formulation of multi-agent bandits.
Overall, lower bound analysis for succinct linear bandits has been relatively under-developed, espe- cially beyond the entry-sparse setting, where existing work often relies informal arguments or naive reductions to the entry-sparse case to invoke known lower bounds. Meanwhile, upper bounds with dominating dependency on d are proven attainable primarily in the data-rich regime [1 [0].

---

while dimension- free rates are typically achieved by constraining the assumption class to bandit instances that permit well-explored action data (Ar)==1 in order bypass the linear lower bound in the data-poor regime 7 12
Contributions. Our contributions in this work are threefold. First, in Section 3.1 we propose succinctness model in general vector space, along with lemmas that may be of independent interest. Second, in Section 3.2 develop general framework for deriving minimax lower bounds of succinct linear bandits in both data-rich and data-poor regimes, offering customizable constructions that revolve around two concepts. i.e. information-regret trade-off and suceinctness support. Third, in Section
4 we apply this framework to three stochastic linear bandit problems that exhibit succinct structure and permit well-conditioned exploration. With minimal customization, we are able to improve the previous bound of (7] for entry-sparse vector bandits. To the best of our knowledge, we obtain the first lower bounds for group-sparse matrix bandits as well for low-rank matrix bandits. showcase the generality of our framework and shed light to directions for extending existing upper and lower bounds.
These results, summarized in Table [
2 Preliminaries
In this section, we start with concise description of vector spaces, stochastic linear bandits and the notation used throughout this paper. We then briefly review the standard machinery commonly used in the literature for lower bound construction-ttccniiie that we also draw upon later in proving our main theorem.
2.1 Problem setting
Vector Space. We consider vector space V over I. which set equipped with the vector addition and the scalar multiplication operations satisfying the standard axioms, such as the existence of and additive inverse - -X of any vector X E V. We also define an inner product (. as function V x V IR that satisfies the properties of symmetry, linearity, and positive definiteness. Later, we will use the general definition of a norm, e.g. : + R, which satisfies the triangle inequality P(X + Y) S P(X) + P(Y), absolute scalability P(aX) = [a]P(X), and positive definiteness X # = P(X)= > 0, for all vectors X,Y E V and scalars a, b b R.
Stochastic Linear Bandit. At each round f, the agent perceives a fixed action set A S V and executes an action A, A. Then, the bandit machine generates a reward 3/t (A,, 8) + ne- where T7 ~ NO, 1) and some parameter 9 E V characterizes a bandit instance. The agent is conceptualized follow a policy which yields A, stochastically conditioned on the ongoing interaction A1g1 A2322 11-18--1-
Now that stochastic process can be fully determined from the interactions between the policy æ and the bandit instance (A, f), or briefly 0, up to a horizon of rounds, we can calculate the regret of n compared an omniscient policy that always plays an optimal action:
(A,0)) : Er,0
max Σ
max (X, 0) XEA
Σ U1
where max XEA
[(,00| <
(I)
Notation. We denote the sub-optimal gap of an action X E A under the instance as A maxx 10'00 f) - (X, f). Given an inner product, we define the induced norm or length ||X| X) for all X E V, which can be shown to be norm. We shorthand the set of integers 21,2,3... .... .d] as [d]. and 32.3..... d} as [2 d). Let [ be the cardinality of set G. The indicator 1(D) equals if the event D occurs and 0 otherwise. We will omit ı in P 7,0 and E,, when the context is clear. For vectors in Rd, we use ||- and ||-1/1 to denote the 1.g and the I norms. For matrices X E Rd xd2, ||,,, 2 == max; (E, 1/2 and || == EE x3,)) )/2 denote the 2,0 and the 4,2 norms, while I|-llop and Il denote the operator and the nuclear norms.
3

---

2.2 Techniques for lower bound construction
Le Cam's Lemma. The construction of minimax lower bounds can be viewed as mirroring Le Cam's s method in statistics for lower- boundigg the worst-case enror for any estimator. Let F be set of distributions, where each distribution PP E F is associated with parameter 0 E e. Consider ((S) as an estimator for ! using empirical data ~ P. Let metric d : x θ + [0, oo) satisfy symmetry and triangle inequality, For any PI,P2 E F with 01, 02 E ① and densities pl (2), (-),, we have d(01, 02)
/ min(pi P2))
inf sup Es (ss 0 PEF
The Ss term can be further lower bounded by 1/ exp(-KL P2)) or other options We can relate the regret of some policy л on a bandit instance 9 to the estimation error of some estimator (()) on the trajectory distribution P., The key establishing this bound is identify two instances (IP1, 01) and (I22, 02). along with some common event, e.g. = (d(O(S), 01) 2 d(O(S), 02)}, such that the sum of the two estimation errors can be lower bounded independent of 0(:):
/ Pi(() d(O(S).02) + Pe(S) ((((S)))2) / [pi(5) + |.(1S))11
d(0,, 02)
2
Kl-ddieegeence Decomposition. Let I9,, and Po, be the two trajectory distributions induced by the policy æ playing in the bandit instances 01 and fz. respectively. Consider trajectory A1y/ ...- A, yn. the log- loglliiel ratio log[po, This allows us to decompose KL(IPe, Pe,) n KL-divergences between reward distributions conditioned on Ar under Pe. If reward distributions are (VAr,, 01), and (((A,, 02), 1), we have
9nn)/pp (A1... equals Σx=1 log[po, (3ee A po (v/ A+)]
(L(PP,; Eg
(A,, 01 02)²
Main results
In this section, we present our general succinctness model which encompasses cases such as entry- sparse vectors, group-sparse matrices and low-rank matrices. We then present general minimax lower bound based on the proposed succinetness model.
3.1 Succinctness model
Here, we give the formal definition of vectors being "s-succinet" and related lemmas, in preparation for the lower bound construction in the next subsection.
We assume that all the 1-succinet vectors given in advance and that the scalar multiple a.X of some succinet X E V should be equally succinct at least when a o O. We first impose the existence of the set of "succinct units", i.e. the 1-succinct vectors of unit length.
Axiom 3.1 (existence of the succinct unit set). There exists a non-empty set l such that VE E E U <> E is an 1-succinct vector in V with || 1, and that VE: E E Eu -E e.
We aim to compose from some succinct units a new vector that can be regarded as "s-succinct" without any part or the whole reducing to "I-succinct". Then, those units the "s-succinet" vector decompose to must uphold some relation against all the succinct units in i to prove that they are indeed irreducible.
Definition 3.1 (succinct support). We say that an indexed set of d E N+ succinct units {E,]dm. C 2 forms support if and only if
sup
(E, =
BEU
Remark. It is easy to see that any non-empty subset of {E,).- forms a support. We can flip the sign of any support member and still get valid support, e.g. = The equality (2) implies mutual orthogonality. On the other hand, if 24 contains only mutually orthogonal elements, then 2/
itself forms support.

---

Now, we introduce the two quantities Q().. R(-) V [0, oo) for later imposing boundedness condition, and then state the, by now, fairly evident definition of "s-succinct".
Definition 3.2 (two semi-norms). For all X V, we define Q(X) supEeu (X, E), as well as R(X) := s (X, Y) where Y E V with Q(Y) I 1.
Remark. Since U is non-empty, both Q(- and R(-) validly defined and satisfy the triangle inequality. Moreover, because U is closed under additive inverse, it follows that Q(X) and R(X) also satisfy the property of absolute scalability. Hence, they qualify as semi-norms, as they satisfy all the norm properties except positive definiteness.
Remark. Given X * Ö, Q(X) = 0 suggests VE E Eu: (X, F) = Thus, Q(-) will be a norm if spans V, as U will have no other orthogonal complement in V than Ô. In addition, R(X) will also be |X|| (Q(()QQ(X))))))))))) > 0 as long as X * 0.
norm because R(X) (X,X/Q(X)
Definition 3.3 (s-succinct). Consider E N We call a vector X E V s-succinct if and only if it can can decompose to some support {E:)i=1 with some scalar coefficients (ai)i=,, i.e. X Σ Ei, and strictly s-succinct if and only if # 0 for all i E [s].
Based on the definitions above, we have the following lemmas. See their proofs at Appendix A
Lemma 3.1. !f X = Σi=1 03 Es for some support {Ei and some scalar coefficients {ai)i=r then Q(X) maX [as].
Lemma 3.2. If Ei= Fg for some support {Eiji=i and some scalar coefficients {a:)i=r. then R(X)= Σ |a:).
Lemma 3.3. If X is simultaneously s-succinct and strictly z-succinct, then 2
Lemma 3.4. X is simultaneously strictly s-succinct and strictly z-succinct, then s
holds for any Lemma 3.5. If X is s-succinct, then (X, & min ((X))(())
YEV. V.
Lemma 3.6. X is s-succinct, then suPR(Y) (X, Y) QXX,, where Y and R(Y) S 1.
Remark. If X is s-succinct, Lemma 3.1 and Lemma 3.2 ensure positive definiteness, i.c. X o 0 Q(X), [[XX= > O. Meanwhile, Lemma 3.5 and Lemma (.6)maa336shr show that Q(-) and I((-) resemble a norm and its dual norm at least for s-succinct vectors. On the other hand, If U spans V, then Q(-) becomes norm and R(-) its dual norm. In this case, have (X, I Q(X)R(() and sup su (X,Y) Q(X) hold for all X,Y E V. However, U spanning does not imply that every vector in V is s-succinet for some respective s E N+
3.2 General minimax lower bound
In what follows, we present our general lower bound for stochastic bandits under the suceinetness model previously described. We start with a set of assumptions, which are fulfilled by our applications in Section 4
Assumption 3.7. Suppose the following objects exist.
1. action set H C V satisfying maxxex (X, 0o) S -Co, where Co > 0 is some global con- stant and Og E V is some parameter that can decompose to some support (F) E Eg...., FE}3 of cardinality k +21 1.
2. 1 non-empty groups of succinct units, denoted as G1, C2,..,, where for any tu- ple (Ei, Ez,..., E.-x) the Cartesian set X - GG the set (Ei,..., E. Ei...., E.3 forms a support of cardinality 2 3k + 3.
3. q.P E R. satisfying EH gg (X) S and maxxee, Tg. (X) < for each i E [s- ke), where &G. (X) = Exeg. (X, /
Next, introduce main theoretical result. We provide formal proof based on sequence of steps and some claims that are proved in the Appendix B
Theorem 3.8. Consider the bandit problem
( where all actions X E and parameters E V are bounded with Q(X) < 1 and R(0)= < 1. Suppose Assumption 3.7 hold with some s E NT, Co 0
5

---

and p.q 2 1. Then, we can construct an action set A such that given any policy π. there exists an s-succinct parameter incur regret
(A, min(Co,e_*/5 min(s3n 8 s
Proof. Since Assumption 3.7 holds, we assume access to 0o. the action set H. and the k groups G1 Fi.92...., .....,9.... 9--k. Let [( k) It follows that b 2 k and 36 > 2b + k + 2 2b.
Note that 0 < Co I due to R(0o) S and Lemma 3.5 We choose a specific (Fi ....... E2)
Gb+s and extend each of the first groups with corresponding star star-marked unit as follows:
91 U (ET), G2 (E5) .... Go U [}E))
Step Construction action A. We construct
S Es ViE [b] E (EGUEE A HUS
Each action X S is s-succinct and satisfies Q(X) by Lemma 3.1 Since each action
corresponds with unique selection unit E, from each extended-grous G. {E }. later when
discussing the action A, at round and if A, S, we will use the notation Ar, == E, to represent its unit selection in the cheeddddggoup
Step 2: Parameters in consideration. Let >> 0 be constant to be decided later, subject the constraint < Ca We construct
h
0
E 2F, 1(E, + E;1) vi e
E, (
We can verify that V0 E
R()) < + 3bc < 1. Similar to the construction of S, there is a one-to-one correspondence between θ and X²_ (G, U {E,)). For any and i [6], we use (0) E 9, U ( to indicate the unit that 0 selects in the extended group i.
By construction, playing any H--baed action in any parameter setting 0 incurs at least a constant regret per round, compared to an optimal S-based action that shares the same unit selection as 0. By constraining se to be sufficiently small relative Co. we can show that vO E O, VX H: (X 2 Co/3. 1. See the formal argument at Appendix B.1
Step 3: Intricacies of avoiding sub-optimality. Choosing the correct optimal S-based action across different parameter settings of can be seen as solving sub-problems parallel, where the challenge is to minimize the regret of failing to select the correct unit (0) for each sheended-group i E [b]. Define T's (t E [n] A, 8), For each complement event D,):
[b], we introduce event D; (and its
D. = 1( ET
n
2
LET'
Claim 3.9. V0 E O, we can lower bound the regret in terms of those group-wise events:
where R = nE (P) if E, E, 2 (D.))) E + E
(A,0))
R
where Po is the distribution over empirical trajectories induced by æ playing in up to a rounds. See the proof at Appendix B.1

---

Step 4: Bound through KL-divergence. Intuitively, the sparse geometry in S and @ within each extended-gree groupp puts an anformation-theoretii limit on T ability distinguish between the situations (0) Ex and (0) + E" over all versions of O.
We consider different settings of 0 with varying (O) for the extended-group i, while keeping their unit selection fixed for the other extended-groups Given (Éi, Ez,.... E.....,,,))))) E X (G, U (EE)) and extended-grous index we reversely denote ((E,, E_,) == 200 + >i ( + 2E, 1(E, + E; where E_ (Fi..... 1 Fe+1...., P.). Fix i and E-;. Then, using Le Cam's 's Lemma, Kl.-divergence decomposition, and Jensen's Inequality, we can lower bound the following quantity:
R R B..) RR
ne Gel
(A,, E)²
exp
25 ( E.
Gil
REG:
[=1
REG
This intermediate bound is established to support the following claim. See the details at Appendix B.2
Claim 3.10. Define Tı == {t [n] Ae Hl.
We have
max R (A. 2
1188
exp(- -22
n +
max Eo [ ME0
(4)
AE
24
Step 5: Information-regret tradeoff. Overall, the lower bound 4 is optimistic regarding æ playing more H-based actions, as S-based actions are sparse and provide limited information for distinguishing between different across O. However, since H-based actions are also sub- optimal, there is another lower bound on the maximal regret that discourages the same quantity maxéce Eg [T]]]:
Co
max R (A,0) max Eg 0E
Σ (Ai) LITX
max Es [TT]] BEB
(5)
BE
The challenge of determining how often play regrettable yet potentially informative H-based actions leads us to the final lower bound. Combining the lower bounds (4) and (5) in a minimum expression, min(
replace maxaee [[[]] with free variable h, and obtain the lower bound + 1) Co h) that holds for any h R.
q
When p < n 39g, we let 9s2p < 2 2n). n). Then, we have lower bound min(e-1/28 Co/3) 8 syp.. When nås 393. we let 8 = n 3 à and h qe 2(8 < Co/3 requires q < Cin). Then, we have another lower bound min(e-1 /24, Co/3) sănăqs. Together, we have the final lower bound 3
vp/n and h -2 (the constraint SE S Co/3 requires
Applications
In this section, we show that our framework sharpens recent lower bound by 7 when applied to entry-sparse vectors. We then apply our framework to provide the first lower bounds (to the best of our knowledge) for the group-sparse and low-rank matrix settings.
First, we derive corollaries for bandit problems with three types of succinet representations: entry- sparse vector, group-sparse matrix, and low-rank matrix. Accordingly, we consider V == gd or Xd2, treating vectors in IRd as one-column matrices.
Naturally, the inner product is defined as (X,Y) the induced norm ||-||| := V(x,X X) follows. In addition, we define the following quantity to characterize the shape of an action set A C V.
trace(X"Y) for all matrices X, Y. V and
Definition 4.1. Let Pr(A) be the space of probability distributions over A and define
Cmin == max min ExnEEx((XX B}3] where 3 E V with |||||| = μEPe(A)
7

---

Remark. By flattening matrices X ~ I into vectors (min can be computed by finding distribution j that maximizes the minimum eigenvalue of the covariance matrix E [xx"], Intuitively speaking, Cmin measures how well the set A can support an exploration distribution that samples well-conditioned action data for probing the unknown bandit parameter.
Remark. Cuin (A) > if and only if A spans V. Cmin (A) is upper bounded by actions in A are bounded with Il- xe I 1, by 1/d2 if olo, S and by 1/ min(d1, d2) if ll-llop I 1.
4.1 Eptry- vector bandits
First, we use our general framework obtain lower bound order Q2min 1/3 2// Vdnn) miu (1/ 1/3
for entry-sparse vectors. Our result is tighter than the prior rate of Mmmin(( (Cii g n/ ddn)) shown in 77.
Corollary 4.1. Consider the bandit problem (T where actions x R and parameters 0 Rd are bounded with || I and [|0]| I 1. Given any policy there exist an action set A with (A) and parameter 9 with no more than non-zero entries, such that
(A.0) exp(-4) -iin (c min (A)s n vdnn
(6)
Proof. We define the succinct unit set set == {e)))=1 where each ej == (0,0, 1, 1,....0) E RR has a single at the j-th entry. Then, the two semi-norms Q(-) |1-1l and R(--) ||-111. Meanwhile, 0 having more than non-zero entries equivalent being s-succinet. Let < K S 1 be constant and construct the action set
{1 tx
ifj=1 otherwise
== Σ ag Ej
bj E
[d]
aj
We consider 0g == -1 which is 1-succinct and satisfies max (z. Bu) S -1. It also can be shown
that Cruin (H) 2 x², Assume (mod s) 0 and construct
id
id
Vi E [s 1]: 9j = Bg
jE
We can verify that max (x) I s/d and maxzew &g. (x) S k² for each E [s - 1]. Invoking Theorem 3.8 with the constructed H and {-]] we can construct an action set A with Cmin(A)
Ciiu (H) and s-succinct that make the lower bound (6) hold.
4.2 Group-sparse matrix bandits
Next, we use our general framework to obtain the first lower bound for group-sparse matrices. The following corollary provides lower bound of order (mmin 1/3 n/ /didzsn)).
min
Corollary 4.2. Consider the bandit problem (1) where actions X Rdixd2 and parameters f
Rd xd2 are bounded with ||X|] I 1 and || ll.2 S 1. Given any policy n, there exist an action set A with constant (m) and a parameter with no more than s non-zero rows, such that
exp(-4) min (C (A))333 ddid2n))
R (A,0)
24
Proof. We define the succinct unit set U = {eu- E {e E Rd,, = 1}. where { is the standard basis of Rd. Then, the two semi-norms Q(-) = ll and R(-) 1111,,2- Meanwhile, 0 having be an orthonormal basis d2 and < x < 1 be constant. We construct the action set
than non-zero rows is equivalent to it being s-succinet. Let {2, )
0
if - - + otherwise
H
T + clui
aj eyyy T
Vj [di]:
gE gE|da]
8

---

We consider 9b ;= -1e9f which is 1-succinct and satisfies maxxeн (X, - shown that Cmiu (H) 2 n²/dz Assume d1 (mod 8) 0 and construct
It also can be 2'
1
id1
id1
d1
Vi (s 1] 9:
egum
m [d2) 8
We can verify that max &g, (x) & (/1d22) and maxzeu & (2) S k2/d22 for each i E [s - 1]. Invoking Theorem 3.8 with the constructed Ht and {9i we can construct an action set A with Cmin (A) Cmin (H.) and s-succinct that make the lower bound (7) hold.
4.3 Low-rank matrix bandits
In what follows, we use our general framework to obtain the first lower bound for slightly more challenging problem: low-rank matrices. The corollary below provides a lower bound of order Q(min Cmin
1/3 ///332/3, vdidzn)).
Corollary 4.3. Consider the bandit problem (TP where actions X E Rddxx2 and parameters 0 R are bounded with |XX llop S. 1 and [10] nue S I. Given any policy π, there exist an action set A with constant Cmia (A) and a parameter 9 with its rank no larger than s, such that
(A,())
exp( -4)
min (C (A)s+ / /d1d2))
(8)
24
min
|||| = =1- Then, the two semi-norms Q(-) ll-llop and R(-) II-IInue- Mcanwhile, 0 having rank no larger than is equivalent to it being s-succinet. Let { and {1g]g== be orthonormal bases of Rd and Rd respectively. Let 0 < < be constant and assume d1 S d2 (the case d1 > d2 can be handled by swapping the subscripts of and below). We construct the action set
Proof. We define the succinct unit set 4 = (ue² u E Rdi, E Rd,, ||]]||
(o { + otherwise
if m(g.j) = }
::= U gE|dal
T u
Σ aj U)um(a)) 3=1
Vj E [d
where m(g,j) (g + j) (mod d2) + 1 is used to cyclically iterate over [d2] for each j E [d1],
with a different starting point for each g E [dg]. We consider Og := -a of which is 1-succinet and satisfies maxx EH (X, 0o) < - It also can be shown that (min(H) 2 x2//2.. Assume
dj (mod s) = dz dz(mod s) = 0 and construct
id
idi
di
id2
id2
id2
Vie [s 1]: G. = u
j jE
+
E
+
We can verify that max,eg, &g. (x) s² d2) and max $ g. (x) S k²s/do d2 for each i [s 1]. Invoking Theorem 3.8 with the constructed H and |= we can construct action set A with Ciiu (A) 2 Cuin (7)) and s-succinct that make the lower bound (8) hold.
Future Work
In this paper we give a first step towards unifying the study of lower bounds for succinct stochastic bandits. Although we provide three applications including two novel lower bounds, we believe our framework will motivate future work for finding lower bounds on other bandit problems. The study of other stochastic bandits over mathematical objects beyond vectors and matrices, such as a multi-linear regimes (e.g., tensors) and kernels of combinatorial objects (e.g., sentences, trees) would be interesting. In addition, the study of nonparametric settings, in which the bases are functions would also be an interesting extension.
References
[1] Y. Abbasi-Yadkonn D. Pal, and C. Szepesvari. application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pages 1-9. PMLR, 2012.
conversions and

---

[2] P. Auer, N. Cesa- Assa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
[3] H. Bastani and M. Bayati. Online decision making with high-dimensional covariates, Operations Research, 68(1):27-224, 2020.
[4] G. Burtini, J. Loeppky, and R. Lawrence. A survey of online experiment design with the stochastic multi-armed bandit. arXiv preprint arXiv: 2015.
[5] A. Carpentier and R. Munos. Bandit theory meets compressed sensing for high dimensional stochastic linear bandit. In Artificial Intelligence and Statistics, pages 190-198. PMLR, 2012.
[6] W. Chu, L. Li, L. Reyzin, and R. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208 214. JMIR Workshop and Conference Proceedings, 2011.
[7] B. Hao, T. Lattimore,
M. Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 11110773-117665 2020.
[8] N. Johnson, V. Sivakumar, and A. Banerjee. Structured stochastic linear bandits. arXiv preprint 16Xiv:1606.05692 2016.
[9] K.-S. Jun, R. Willett, S. Wright, and R. Nowak. Bilinear bandits with low-rank structure. In International Conference on Machine Learning, pages 3163-3172. PMLR, 2019.
[10] G.-S. Kim and M. C. Paik. Doubly-robust lasso bandit. Advances in Neural Information Processing Systems, 32, 2019.
[11] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[12] W. Li, A. Barik, and J. Honorio. A simple unified framework for high dimensional bandit problems. International Conference on Machine Learning, pages 12619-12655. PMLR, 2022.
[13] M.-h. Oh, G. Iyengar, and A. Zeevi. aggnosty- lasso bandit. In International Conference on Machine Learning, pages 8271-8280. PMLR, 2021.
[14] X. Wang. M. Wei, and T. Yao. Minimax concave penalized multi-armed bandit model with high- dimensional covariates. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5200-5200 5208. PMLR, 10-15 Jul 2018.
10

---

Supplementary Material: A Novel General Framework for Sharp Lower Bounds in Succinet Stochastic Bandits
A
Proofs of succinctness--elatte lemmas
Here, we provide detailed proofs for the succinetness--rllated lemmas in the main text.
A.1
Proof of Lemma 3.1
We rewrite
Ei= a,E, as x =i |as] sign(a;) Then,
sup (X,
sup EEU
a (sign(a; (a;) E, E)
BEll
sup max |a,1 BEul iE[s]
(s)gn(a;) EY
max
ag
sup BEUl
(E,, E)
<<[e]
max |g
(9)
<E(s]
Notably, step (9) applies the succinet support requirement on {Ea]i=1- This upper bound is reachable by letting E' = sign Em where arg maxie[s] la:]. Since sign(am Em U, have Q(X) == sup (X, E) max:e[s] la,|-
A.2 Proof of Lemma 3.2
We rewrite X = -Ee 0j Fg as X = Di= ladl sign(a:) E.. Then,
sup Q(Y)S)
(X,Y)
sup
lad (sign(a;) Y)
Q(Y)S i=1
sup
Σ i=1
lad |(E,, Y)1
Q(Y)
sup Q(Y)
lad
sup EEM
KE Y)
[=1
sup
lad Q(Y)
(10)
Q(YS
lail
(11)
Equality 11) requires the fact that 2/ is closed under flipping the sign of any E E U. The upper bound E,, in (TT is reachable by letting Y = Σim sign (a,) E,, in which case Q(Y) = due to Lemma 3.1
Therefore, have R(X)= supo (X.Y) Σi= las].
(iin(() 1(x 0} 1(x 0)

---

A.3 Proof of Lemma 3.3
From the definition of s-succinct and z-cuccinet, we know that Ei=1as a,E; Ein for some {= and some {E that constitute succinct support respectively, and where the coefficients can fulfill b; + for E [z].
Yet = B sign(a;) Fg. Due to the mutual orthogonality of support members, we have (X, Y (Ei=1 0; E, Y = Ei=1 lasl and (Y, = s. Importantly, Q(Y) = according to Lemma 3.1
Meanwhile, Lemma 3.2 suggests R(X)= Σi= las| Ei=1 |0:|- Once again, from X's decompo-
sition E:=1 |6,| sign bb: E, we calculate
(x, Y) = Σ bul Esign())))
bii
(12)
For each i e [z], we have upper bound
(sign(b:) Y) S (EE, Y) S sup (E,, Y)
sup FEUl
Q()) =1
(13)
Fell
12 to hold, the inequalities in must hold with equality, meaning (E) Y = 1, for all [=].
Since |6:|
0 for all i [=]. for equality
Let P = = construction, (P,Y)= = (P,P) = EE, = 2. Combining them with the
E be the projection of Y onto the set of bases {E Then, by
conclude |Y|| (Y,Y) vs 2/V2 V2, and thus inequality |P]| ||||| 2 (P,Y),
2 2.
A.4 Proof of Lemma 3.4
By definition, X is also s-suceinct and 2-succinet at the same time. From Lemma 3.3 and x 2 s at the same time. Naturally, $ = 2.
we have
A.5 Proof of Lemma 3.5
Recall that Q(-) is semi-norm, meaning Q(kA)) [k(Q(A)) and Q(A) 2 0 for all & E R and A E V. Therefore, for any A, B E V with Q(A) +
(A, Q(A)
((', Q(A')
< sup Q(A0)0
sup Q(A9)51
1(A', = sup (A', B) R(B) Q(A951
By substituting B,B B with X, Y. we have (X. < Q())R(Y) as long as Q(X) + 0. In the case of Q(X)= = 0, given that X = D E,E, for some support {E and some coefficients
{ai) have (X)) max;e[s] |a.| 0 from Lemma 3.1 which leads to X Ö and thus
(X = 0- Q(X)R(Y. Together, (X,Y) < Q(X)R(Y
By substituting A, B with Y.X, we have (X, S Q(Y) as long as Q(Y) # In the case of Q(Y) sup rey (Y, EE = 0. is easy to see that (E,, Y) = 0 for all the members in the support
(E.) and thus (X, Y) Together, (X, Y) & R(X).
A.6 Proof of Lemma 3.6
Applying Lemma
3.5 within the maximization, we obtain the upper bound
sup (X,Y) sup R(Y)Q(X) < Q(X)
R(Y)S)
R(Y)S)
Given that X = Ei= a, E, for some support { {E,}:-) and some coefficients {ai) let Y =
sign am) Em where m arg max4e[s] la,) We can verify that (X,Y) max la. = Q(X) due to Lemma 3.1 and that R(Y) 1 due to Lemma 3.2 Therefore, supR(Y):i (X,Y) Y)= Q(X).
12

---

B Proof details for Theorem 3.8
Here, we provide detailed proofs for the claims inside the proof of Theorem 3.8 in the main text.
B.1 Proof of Claim 3.9
With be I 2 K
Co. we can prove that AA E 0, VA E H:
(x
max [X,0) 0)
max (X, 0) XEN
max (X, 1
1
m max (X, 0)
80)
+ max (X,
2 200
XES
XEH 2
Q(XIs1
b
Co
E
11 + (() * Ei})
+ Σ
(1 + ((), * ET)
(14)
2
1=1
1=1
Co
Σ (B.(0)) + E
1=1
Co
2 8 > (E)(0)) F
(15)
Recall that by construction, 0 - 400 = =E +
+ (E, 1( * Ei}. In step (4)
maxxes (X, 0) is obtained by the action X = Σi= (0). while (X,
0 - (o) can be E E (0) (() + E Further, we have that A0 O
achieved by an action
(0) = Eg
Σ
max (x,) - (A..0) 03
XEA
max
X,,) 0) (Ac, if if EST
XES
2 Ea
(16)
1 ((,(0) ET} if EH
1(A,, = E
if E S, E,)) =
5
Eg
2 - 1(A,, = ET} - 2 1(Ar, 2 = =((()))
Af E S, 5,())) + E
(17)
1 ((,,(0) Fi)
if H
1 1- 1(A,, = E
if E SS, E,(0) -100)=b) EN
1 1( ET}
if E S, E,(0) + E
Eg
if H. E,(0) E
if A E H. Ex(0) # E 1+ Σ [1 11- 1(A. ET] if F,(()) E
LETN
TET'
E.
1(A,, ET}
if E,)) + E
1ETs
Eg
11 Σ 1| Ei}
if E. E
IET's
Eg
Σ 1(Ar,=
if E(())) + E
LieTs
13

---

ne (P())) if E. E;
2 (F((D)) if ( + E
H}. In step (16). for the case A, E H. we invoke the inequality in (15). Meanwhile, the case A, E S can be further analyised per extended-group as shown in step (7]: when At E S, the optimal move for A, in each extended- group is to select the unit that selects, i.e. A,, = (0); doing so yields an optimal gain of g (i( = E or an optimal gain of 2E if (() + ET.
Recall that Ts := ft E [n]
S) and Tx := f [m] A
B.2 Proof of Claim 3.10
Given and E is we have
Σ ne
I F E .) (D.)) + Po (D:)]
DEG:
nE
Σ exp ( - (L B(E; B. B.) Pe ((EEEEE .))
4
EEG:
T18
exp ( (- 2 E_.))
Σ (Ass FJ)2 )
4
Beg:
ne
n exp ( (- 2E?EOLE; E_.)
n
(A,, E}²
4
19il
FEG
ne
ne| exp ( (-22 1-2e"B -ee"BerE B.
max &g (X) + Σ
max D (x)
XES
XEM LETN
LIE's
ne [il exp ( 2 BB1)
max TG. (x0))
n max &g. (X) + |7xdl XE9;
XEM
ns [9,]
[T
exp
FF, E
1)
+
P
ne | exp ( 262
1
+ q BEB
max Eo [|
We consider
5
T : ((E,, E1), (E2, E2), ...,, (Es, E3))
X (g, (E1))
i=1
Given T, we denote
b E EE,, E.) (E, Ei}
iml
14

---

Thus, we have
max (0) 2 A56
R. (0(E))
X i-
h
(9, x {bi})
X i= E;}
PO(E) (Di) E, = Ex
nE
1
|9
2b
PMEE) (D,)
if E;
T
2m
Σ
Σ
nE
[POCE E..) (Di) + P F (D.)
2
2
1=1T
E- FES
Σ
2
exp (-2c²
22²2
n max Eo 11Tll )
0
2b
p q AEO
nbbe
exp
- 222
T1
max
Eo
[T
8
Then apply 3b 2 get the claimed lower bound
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract is short version of the introduction, and the introduction accurately reflects the paper's contribution and scope.
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 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.
It is fine to include aspirational goals as motivation long 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 clearly describe the different assumptions and models being used. We also describe the limitations of our results as ideas for future work.
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 are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with 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 approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails 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 address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
16

---

Answer: [Yes]
Justification: We provide several theorems and lemmas, together with their proofs, as well assumptions for our theoretical result.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and proof-based. No experiments were performed.
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.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors 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 have some path reproducing or verifying the results.
5. Open access to data and code
17

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and proof-hased. No experiments were performed.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc
aublic/guudees/Coeeetbii..s cosssiinnooyyy for more details.
While 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 run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wttps/cccppplccggua.aeaeaeccuuep Sttelee//ooSSSSSesSSioeaa www.ssssiicggooooo 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 proposed method and baselines. 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 in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: 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?
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and proof-based. No experiments were performed.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and proof-based. No experiments were performed.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
18

---

The factors of variability that the error bars are 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 the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 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 are out range (e.g. negative error rates).
If error bars 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 to reproduce the experiments?
Question:
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and proof-based. No experiments were performed.
Guidelines:
The answer NA means that the paper does 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 rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't fidn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The authors have read the NeurIPS Code of Ethics, and our papers conforms with the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make 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 societal impacts of the work performed?
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and mathematical proof- based. There no societal impact of the work performed.
Guidelines:
19

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to 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 to point out that 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
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: The contribution of this paper is entirely theoretical and mathematical proof- based.
Guidelines:
The answer NA means that the paper poses no 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 requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
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 we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and mathematical proof- based.
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 dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
20

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thcode cowc datasetss has curated licenses for some datasets. Their licensing guide can help determine the license 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 is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The contribution of this paper is entirely theoretical and mathematical proof-
based.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as 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 used.
At submission time, remember to anonymize your assets (if applicable). You can 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 paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and mathematical proof- based.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in 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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The contribution of this paper is entirely theoretical and mathematical proof- based.
Guidelines:
21

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
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 expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not 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 important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The core method development in this research does involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
22


Reviews:
[{"review_id": "UPDicZlqes", "reviewer": "Reviewer_hinF", "summary": "This paper proposes a general framework for deriving regret lower bounds in linear bandit problems where the loss vectors exhibit some form of structural simplicity. Concrete examples of such structure include sparse vectors, low-rank matrices, and group-sparse matrices. The framework aims to encompass these cases in a unified manner. In particular, for the sparse linear bandit setting, the paper derives an improved lower bound compared to existing results.", "questions": "Regarding Theorem 3.8, can the authors provide concrete examples where the bound becomes tight (or provably loose)? Would it be possible to state sufficient conditions under which the lower bound is tight?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe problem is formulated with technical precision, and the theoretical results are well structured.\n\nThe presentation emphasizes generality and extensibility, suggesting that the framework could potentially be applied to other problem settings.\n\nWeaknesses:\n\nThe intuitive explanation of the model definitions and technical results is somewhat limited. For example, in Section 3.1, while several notations and definitions are introduced, they are mostly listed without accompanying interpretations or illustrative examples. Providing such context would improve readability.\n\nIt would be helpful to include a more detailed discussion of how tight the proposed lower bounds are in general. For instance, regarding Theorem 3.8, can the authors provide concrete examples where the bound becomes tight (or provably loose)? Would it be possible to state sufficient conditions under which the lower bound is tight?", "was_revised": true, "final_justification": "All of my questions have been addressed, and I have no remaining concerns. I have also confirmed that the concerns raised by other reviewers have been addressed. While I would not consider the paper to have particularly high impact, it does not have any major weaknesses either. I would therefore like to maintain my current borderline accept rating.", "rebuttal": "> The problem is formulated with technical precision, and the theoretical results are well structured.\n\n> The presentation emphasizes generality and extensibility, suggesting that the framework could potentially be applied to other problem settings.\n\nWe sincerely thank the reviewer for the appreciation of our work.\n\n> The intuitive explanation of the model definitions and technical results is somewhat limited. For example, in Section 3.1, while several notations and definitions are introduced, they are mostly listed without accompanying interpretations or illustrative examples...\n\nWe have realized, from your comment and similar feedback from other reviewers, that Section 3 may be hard to follow without concrete examples. In response, we plan to add a short discussion between Sections 3.1 and 3.2 to illustrate how the three motivating cases --- entry-sparse, low-rank, and group-sparse --- fit into our succinctness model. Specifically, we will highlight the forms a succinct support takes in those three examples, and the instantiations of $Q(\\cdot)$ and $R(\\cdot)$. Right now, this discussion is compressed and deferred until the corollaries in Section 4. By moving it earlier, we hope to help readers anchor the abstract definitions in familiar examples --- particularly before Section 3.2 introduces Assumption 3.7 and Theorem 3.8, which work with general entities. \n\nFor instance, Assumption 3.7(ii) requires selecting one element from each group to form a support. In the entry-sparse case, this corresponds to dividing the standard basis into groups, since any non-empty subset of the basis forms a support. Similarly, for the entry-sparse case, Assumption 3.7(i) essentially means that the specific instance $\\theta_0$ is supported on the k standard basis vectors that are disjoint from those used by the groups. We hope the earlier inclusion of examples improves accessibility of the definitions and results, and would appreciate your thoughts on that.\n\n> It would be helpful to include a more detailed discussion of how tight the proposed lower bounds are in general.\n\n> Regarding Theorem 3.8, can the authors provide concrete examples where the bound becomes tight (or provably loose)? Would it be possible to state sufficient conditions under which the lower bound is tight?\n\nThank you for the thoughtful question. Intuitively, the lower bound in Theorem 3.8 is established by constructing an instance where $\\mathcal H$-based actions incur high regret under certain $\\theta_0$ but could \"potentially\" be informative when playing under those s-succinct parameters formed from the succinct groups, unlike those $\\mathcal S$-based actions. We can image that the bound becomes loose when this optimistic assumption is violated in some instances in the assumption class. When $\\mathcal H$-based actions are as uninformative as sepearately pulling d arms in n rounds, the regret can be as large as $\\Omega(n)$ in the data-poor regime, which is tighter than our bound of $\\Omega(n^{2/3})$.\n\nConcretely, if the assumption class of interest includes instances with only those s-succinct actions in $\\mathcal S$, that is to assume $\\mathcal H = \\emptyset$, Our construction will result in a lower bound of $s\\sqrt{pn}$. For the entry-sparse case where $\\mathcal S$ is constructed from the groups that divide the standard basis of cardinality $d$, it can eventually leads to $\\Omega(\\sqrt{sdn})$ in the data-rich regime which is tight due to an existing algorithm with matching upper bound that works on arbitrary action set, and to $\\Omega(n)$ in the data-poor regime. We tend to believe that the resulting general lower bound of $s\\sqrt{pn}$ in the data-rich regime is somewhat tight for such an assumption class, given the entry-sparse case. \n\nOn the other hand, in Section 4, when the construction is applied to a general $C_{\\min}$ assumption class in the three cases, we can successfully construct an $\\mathcal H$ such that it both (i) has a constant regret gap and (ii) satisfies $C_{\\min}(\\mathcal H) > 0$. The latter condition means that sampling $\\mathcal H$-based actions can give us well-conditioned exploration, i.e. they are indeed \"informative\". Again, for the entry-sparse case, the lower bound in Theorem 3.8 yields a lower bound $\\Omega(C_{\\min}^{-1/3}s^{2/3}n)$ in the data-poor regime, which is tight up to a $C_{\\min}^{1/3}$ factor since an existing algorithm guarantees a matching upper bound. This gives us some confidence that the resulting lower bounds for the other two cases, or even for such a general $C_{min}$ assumption class beyond the three cases, is somewhat tight in the data-poor regime. \n\nWe currently can only offer informal arguments for tightness, as formally proving tight lower bounds typically requires designing matching upper-bound algorithms, which lies beyond the scope of this work. Nonetheless, we believe the open questions raised by our work provide promising directions and motivation for extending existing lower-bound analysis and developing new algorithms."}, {"review_id": "qlreHsVcGH", "reviewer": "Reviewer_aWds", "summary": "A new model of \"succinct\" bandits is introduced that generalizes some previously studied models. Their model of succinctness relaxes the notion of orthonormal sets in a normed vector space. This allows the lower bound to apply to a variety of settings. For instance, when the 1-succinct points are 1-sparse vectors, s-succinct vectors correspond to k-sparse vectors, and so on. The authors apply their technique to a few settings establishing the first lower bounds for low rank and \"group sparse\" matrix bandits, and improving the lower bound on entry-sparse bandits.\n\nI think of this as similar in spirit to the theory of matroids for greedy algorithms, where a specific structure in the instance guarantees approximation guarantees.", "questions": "1. A direct comparison between succinctness and sparsity would be useful in Section 3.1. It seems like succinctness itself doesnt imply much structure and is just a set that could be specified in a problem, while the notion of a support is similar to that of orthonormality/independence, and s-succinct vectors _do_ have implied some structure. I think this is confusing, but there must be some reason for not just writing s-succinct vectors as decomposing into 1-succinct vectors, but rather as decomposing into a support of 1-succinct vectors.\n2. What is the purpose of the first part of Assumption 3.7 (i)? The lower bound just needs the existence of an action space, so I dont see why you need to impose a restriction on it as an assumption (that is, why do you need to say that $C_0 < 0$? If $C_0>0$ for some action set, then maybe the lower bound is just not valid).\n3. What do these assumptions mean for the entry sparse bandit? Specifically, does Assumption 3.7 say that the ground truth $\\theta$ is $k$-succinct? If so, what is the significance of the parameter $s$? How does Theorem 3.8 improve on the entry sparse lower bound? Is it just a better lower bound instance (so there is now a proof for the improved lower bound purely in terms of sparsity)? While this is not a necessary component of the narrative, it would be helpful in appreciating the technical merit of the paper.", "limitations": "Yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe authors provide a novel generalization that yields to lower bounds for bandit problems that have additional \"sparsity\" structure. This seems like a fruitful generalization, and beside the possibility of resulting in further lower bounds in other settings, it seems to extract the notion of sparsity relevant for bandit algorithms.\n\nWeakness:\nThe paper is very dense.\n1. Proving that the instances in Section 4 actually satisfy Assumption 3.7. For instance, line 273, 288 just say \"We can verify that ...\".\n2. Explaining in terms of sparsity what Assumptions 3.7 (ii) and (iii) mean. It seems like (ii) imposes a restriction on what is allowed to be denoted \"succinct\" vectors. Is $\\max \\Phi$ related to $C_min$ used later? If we just take $p=q=1$, then we already get a lower bound that differs mostly in $s$ terms, so is this specific useful in distinguishing this work from prior work?\n3. Where does the construction in line 203 of $\\Theta$ come from? Again I think that a concrete example with sparsity would make this easier to read.\n\nOverall, I think this paper could be a little longer, with some proofs explained in more detail. The key to using this framework elsewhere is understanding Assumption 3.7, and I dont think it is clear how to even verify these assumptions.", "was_revised": true, "final_justification": "Thank you for your response. I will keep my score.", "rebuttal": "> ... similar in spirit to the theory of matroids for greedy algorithms, where a specific structure in the instance guarantees approximation guarantees.\n\n> ... provide a novel generalization that yields to lower bounds for bandit problems that have additional \"sparsity\" structure... fruitful generalization, and beside the possibility of resulting in further lower bounds in other settings, it seems to extract the notion of sparsity relevant for bandit algorithms.\n\nWe sincerely thank the reviewer for the appreciation of our work.\n\n> The paper is very dense.\n\nWe believe we did the best one can do given the complexity and challenge of our topic. We sincerely hope we are not penalized due to this.\n\n> 1. Proving that the instances in Section 4 actually satisfy Assumption 3.7...\n\n> 2. ... It seems like (ii) imposes a restriction on what is allowed to be denoted \"succinct\" vectors. Is $\\max \\Phi$ related to $C_{\\min}$ used later? If we just take $p=q=1$, then we already get a lower bound that differs mostly in s terms, so is this specific useful in distinguishing this work from prior work?\n\n> 3. Where does the construction in line 203 of $\\Theta$ come from?...\n\nThank you for the comment. Understanding Assumption 3.7 is key to applying our framework to other problem classes. We acknowledge that, as currently stated in terms of general entities, the assumptions can be difficult to interpret on a first read. To provide an intuitive interpretation: Assumption 3.7 essentially says that if the assumption class permits some bandit instance with an action set $\\mathcal H$, that performs universally poorly under a specific $\\theta_0$ whose support lies in a certain \"succinct region\", then we can construct an additional set of s-succint actions $\\mathcal S$ from \"complementary\" succinct groups, and include them in the final action set $\\mathcal A:= \\mathcal H \\cup \\mathcal S$ (provided this is allowed by the assumption class). More Informally, Assumption 3.7 and Theorem 3.8 together tell the story that if we can have a bandit instance with a specific $\\mathcal H$ action set, that is in some sense geometrically flawed, then we can inject succinct/sparse actions to make the instance harder. \n\n$\\max \\Phi$ is not directly related to the generalized $C_{\\min}$ assumption class introduced in Section 4. Instead, it arises naturally from the geometric interplay between the $\\mathcal{H}$ action set and the succinct groups $\\mathcal{G}\\_i$, influencing the tightness of the resulting lower bound. That said, we believe there may be deeper connections between $\\max \\Phi$ and $C_{\\min}$ that help explain why our construction yields nearly tight bounds under the generalized $C_{\\min}$ assumption class.\n\nYou are right that $p = q = 1$ always holds, since $\\Phi_{\\mathcal{G}\\_i}$ can be interpreted as an \"averaged squared projection\" onto $\\mathcal{G}$. However, these parameters still influence the tightness of the final lower bound. As shown in Section 4, under the generalized $C_{\\min}$ assumption class, the difference primarily appears as a missing factor of $C_{\\min}^{-1/3}$ in the data-poor regime and a $d_2 / d_1$ factor in the data-rich regime. We note that for the low-rank and group-sparse cases, the magnitudes of $C_{\\min}^{-1/3}$ and $d_2 / d_1$ are comparable.\n\nThe construction of $\\Theta$ in line 203 is inspired by the one in Section 15.2 of Lattimore & Szepesvári (2020), where you can see how the sole $(\\Delta, 0,0,...,0)$ and variants of $(\\Delta, 0,...,2\\Delta,..., 0)$ correspond to the different succinct unit selection $\\tilde {E}_i \\in \\mathcal{G_i} \\cup \\{ E^*_i\\}$.\n\nWe now provide more detailed instructions for verifying Assumption 3.7 in the entry-sparse case. We define $\\mathcal U := \\{e_j \\}^d_{j=1}$ as the standard basis of $\\mathbb{R}^d$, so any non-empty subset of $\\mathcal{U}$ forms a succinct support. Meanwhile, we can define \n\n$\\mathcal H := \\{(1, \\pm\\kappa, \\pm\\kappa,..., \\pm\\kappa, \\pm\\kappa)^T\\} \\subset \\mathbb R^d$\n\nwhere each $\\mathcal{H}$-based action has its first entry fixed at 1 and the remaining entries equal to $\\kappa$ or $-\\kappa$. We can see that $C_{\\min}(\\mathcal H) \\ge \\kappa^2$ as the minimum eigenvalue of the population covariance matrix from uniformly sampling actions from $\\mathcal H$ will be $\\kappa^2$. Playing any $\\mathcal H$-based action under a specific $\\theta_0:= -e_1 =(-1, 0,0,...,0,0)^T$ will incur a constant regret of $1$ compared to some action whose first entry is 0.\n\nNow, we define $s-1$ groups where we can form a support of cardinality $s-1$ by selecting one element from each group. Importantly, the support should be \"succinct complementary\" with a support of $\\theta_0$ , e.g. $\\{e_1\\}$. Take $d= 12$ and $s=3$ for example. We can define\n\n$\\mathcal G_1 =\\\\{e_5, e_6, e_7, e_8\\\\}, \\quad \\mathcal G_2 =\\\\{e_9, e_{10}, e_{11}, e_{12}\\\\}$\n\nIt is easy to see that since elements in $\\mathcal G_i$ are mutually orthogonal, for any $x\\in \\mathcal G_i$\n\n$\\Phi_{\\mathcal G_i}(x) := \\sum_{e\\in \\mathcal G_i} \\langle x, e\\rangle^2/|\\mathcal G_i| = 1/|\\mathcal G_i| = 1/ (d/s)$\n\nIt is also easy to see that for any $x\\in \\mathcal H$, the above quantity will be upper bounded by $\\kappa^2$, since for each $e \\in \\mathcal G_i$ we have $\\langle e, x\\rangle^2 = \\kappa^2$.\n\n> 1. A direct comparison between succinctness and sparsity would be useful in Section 3.1. It seems like succinctness itself doesnt imply much structure and is just a set that could be specified in a problem, while the notion of a support is similar to that of orthonormality/independence, and s-succinct vectors do have implied some structure...\n\nYou are right that succinctness itself doesn't imply much structure, in the sense that we can just define a different succinct unit set $\\mathcal U$. These succinct units are just pre-defined to be \"1-succinct\". \n\nAn s-succinct vector is eventually defined via its decomposition to a support of s cardinality. A support is a set of succinct units that collectively uphold the relationship given in Eq (2), with respect to themselves and all the succinct units in $\\mathcal U$. That ensures that the whole or any part won't collapse into just \"1-succinct\". For example, adding $s$ 1-sparse vectors does not necessarily yield an $s$-sparse vector, and similarly, the sum of $s$ rank-1 matrices may not have rank $s$. \n\nOur succinctness model subsume the definition of sparsity in entry-sparse case, where an s-sparse vector could alternatively be defined as decomposable to a disjointed subset of the standard basis or just the $\\mathcal U$. The is a special case of succinctness, where the $\\mathcal U$ only contains mutually orthogonal units. When $\\mathcal{U}$ is the set of all rank-1 matrices of unit length, for instance, the units are no longer mutually orthogonal, and so a more general way is needed to define decomposition and support.\n\n> 2. What is the purpose of the first part of Assumption 3.7 (i)? The lower bound just needs the existence of an action space...\n\nOur framework establishes lower bounds by constructing hard bandit instances within a given assumption class. A bandit instance determines a stochastic process where a concrete regret can be computed, meaning it specifies how action options and rewards are generated. In our final constructed bandit instance, the action set $\\mathcal A := \\mathcal S \\cup \\mathcal H$. \n\nAssumption 3.7 (ii) enables the construction of $\\mathcal S$-based actions, which are s-succinct and thus uninformative when playing under s-succinct parameters coming from the same succinct groups. Meanwhile in Assumption 3.7 (i) ensures that $\\mathcal H$-based actions incur a constant regret under a specific instance $\\theta_0$ coming from a \"complementary succinct region\", discouraging the playing of $\\mathcal H$-based actions.\n\nWe encapsulate these essential construction requirements in Assumption 3.7, so that one can assess whether our framework is compatible with the assumption class relevant to their setting. As an extreme counterexample, one can consider the assumption class where an wildcard action $(1,1,1,...,1) \\in \\mathbb R^d$ is always available in the action set and where the s-sparse $\\theta$ only has positive entries. Our construction would be not valid in such an assumption class. A better phrasing in Assumption 3.7 (i) might be \"the assumption class permits the inclusion of such an action set $\\mathcal H$\", rather than \"there exists an action set $\\mathcal H$\"\n\n> 3. ... does Assumption 3.7 say that the ground truth $\\theta$ is k-succinct? If so, what is the significance of the parameter s? How does Theorem 3.8 improve on the entry sparse lower bound?... While this is not a necessary component of the narrative, it would be helpful in appreciating the technical merit of the paper.\n\nNo, Assumption 3.7 (i) does not say that the ground truth $\\theta$ is k-succinct. All it says is that $\\mathcal H$-based actions will get a reward with a negative mean that's small than $-C_0$ when playing under a specific instance $\\theta_0$ that has a support of cardinality $k$. In Corollary 4.1, we eventually pick $\\theta_0 := (-1, 0,0,...,0)$ with a support of cardinality $k=1$.\n\nFor the entry-sparse case. When the assumption class only considers those action sets that can admit a well-conditioned exploration distribution, i.e. $C_{\\min}(\\mathcal A) > 0$, (7) gives a lower bound of $\\min(C_{\\min}^{-1/3}s^{1/3}n^{2/3},\\sqrt{dn})$, which is improved to $\\min(C_{\\min}^{-1/3}s^{2/3}n^{2/3},\\sqrt{sdn})$ in our Corollary 4.1.\n\nWhile it is a modest improvement when one constrains the scope to that specific assumption class, i.e. $C_{\\min}(\\mathcal A) > 0$ and entry-sparse $\\theta$, we highlight that our framework elevates the discussion by offering a unified view and enables extension of existing lower and upper bounds analysis in specific cases."}, {"review_id": "bDORwovbbN", "reviewer": "Reviewer_23qS", "summary": "This paper proposes a novel “template” or framework to prove lower bounds on bandit problems with a so-called “succinct” structure (e.g. sparsity, defined in section 3). Following instantiations of their methods, the authors prove sharper or new lower bounds on Sparse bandits, Group-Sparse bandits and Low-Rank bandits.", "questions": "* I guess your framework applies to K-armed bandits as well since it’s a sub-case of the linear bandits. What are known lower bounds for the S-sparse K-armed bandits? Is your technique also improving that? \n* Your results seems to highlight gaps between lower and upper bounds, either in the C_min dependency or in the other problem quantities. All sections 4.1, 4.2, 4.3 are purely technical and do not discuss the implications of your results. Can you comment on the gaps you opened and whether you believe the lower bounds could be attainable? or perhaps what may cause sub-optimality in the upper-bounds?", "limitations": "Overall, this is a strong theory paper that has many contributions and few limitations. Given that there is a bit more space on page 9, I would like the authors to discuss a bit the implications of their results (see questions).", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n\n* The technical contribution is strong: the paper provides a clear and relatively novel method to prove lower bounds\n* Results are significant and may have major impact on succinct bandits research because the lower bounds that are proved are mainly not matched by existing upper bounds\n\n### Weaknesses: \n\n* Perhaps some additional citations could be provided, in particular in section 2.2 (KL lower bound on l.112 “or other options”). For now this section gives the feeling that this general framework wasn’t known before in the bandit literature, though similar ideas are discussed in many papers and gathered nicely in Lattimore &Szepesvari (2020). In general, I would have liked to understand better what was done wrong before and that you fixed. Perhaps this is written somewhere, or understandable in between the line and I missed it but I felt like I kept asking myself “What is different from known frameworks”? \n* Comments and discussions are lacking\n* Some vocabulary in Section 3 is a bit confusing and not always easy to connect with the bandit problems. Generally Section 3 is the hardest section to follow because it tries to be as general as possible in order to instantiate results into applications afterwards. It makes sense as a presentation choice, but I find that I often prefer to anchor my thoughts into a concrete example so I found myself reading sections 4 and 3 back and forth and trying to connect the dots. I think it’s a minor comment and I will adjust my judgement according to other reviewers’ opinions. Perhaps a way to help the reader would be to use sparse linear bandits as a running example?", "was_revised": true, "final_justification": "I have carefully read the responses as well as the other reviews. I maintain my opinion that this is a strong paper. My main suggestions for improvements are:\n* Try to use a running example to showcase the method and give an intuition of how the construction actually works (especially in the smallest example where the method improves over standard arguments)\n* Clarify some technical steps as discussed with reviewer fbhz (I did not explicitly mention these myself but I agree with the reviewer).", "rebuttal": "> The technical contribution is strong: the paper provides a clear and relatively novel method to prove lower bounds\n\n> Results are significant and may have major impact on succinct bandits research because the lower bounds that are proved are mainly not matched by existing upper bounds\n\n> Overall, this is a strong theory paper that has many contributions and few limitations...\n\nWe sincerely thank the reviewer for the appreciation of our work.\n\n> Perhaps some additional citations could be provided, in particular in section 2.2 (KL lower bound on l.112 \"or other options\"). For now this section gives the feeling that this general framework wasn't known before in the bandit literature, though similar ideas are discussed in many papers and gathered nicely in Lattimore &Szepesvari (2020)...\n\nThank you for the comment. Section 2.2 (inside the \"Preliminaries\" section) is not part of our proposed framework, but rather serves as a brief overview of standard techniques and machinery used in the literature for lower bound construction --- tools that we also draw upon later in proving our main theorem. In hindsight, we agree that the lack of citation may have unintentionally given the impression that we were proposing new techniques in Section 2.2. We will revise the text to clarify its preparatory purpose and add appropriate references to acknowledge the origins and prior applications of these techniques. In particular, a citation to Lattimore & Szepesvári (2020) should have been included after \"or other options\" in line 112.\n\n> Comments and discussions are lacking\n\n> Some vocabulary in Section 3 is a bit confusing and not always easy to connect with the bandit problems. Generally Section 3 is the hardest section to follow because it tries to be as general as possible in order to instantiate results into applications afterwards. It makes sense as a presentation choice, but I find that I often prefer to anchor my thoughts into a concrete example so I found myself reading sections 4 and 3 back and forth and trying to connect the dots. I think it's a **minor comment and I will adjust my judgement according to other reviewers' opinions**. Perhaps a way to help the reader would be to use sparse linear bandits as a running example?\n\nWe agree that Section 3 can be challenging to follow without concrete examples. Given the extra page for the final version, it is worthwhile to discuss between Section 3.1 and Section 3.2 how the three concrete cases, i.e. entry-sparse, group-sparse, and low-rank, fit into the general succinctness model. In particular, we will highlight what constitutes a succinct support in each case. For example, in the low-rank case, once we define the succinct unit set $\\mathcal U$ to contain all the 1-rank matrices of unit length, then any non-empty subset of $\\mathcal U$, e.g. $\\\\{u_iv_i^T\\\\}_{i=1}^{s}$ that fulfills $\\langle{u_i},{u_j}\\rangle=0$ and $\\langle{v_i},{v_j}\\rangle=0$ for distinct $i,j \\in [s]$ constitutes a support. That way, when following the proof of the main theorem in Section 3.2, hopefully, the reader would have an intuitive interpretation of how a set of succinct units are selected from each group $\\mathcal G_i$ to form a support. Originally, we had prepared three minor corollaries at the end of Section 3.1 to illustrate the three examples of the succinctness model, but we eventually compressed this material into the instantiations of general entities $\\mathcal{U}$,$Q(\\cdot)$ and $R(\\cdot)$ at the beginning of the proof of the corollaries in Section 4.\n\n> I guess your framework applies to K-armed bandits as well since it's a sub-case of the linear bandits. What are known lower bounds for the S-sparse K-armed bandits? Is your technique also improving that?\n\nYes, \"s-sparse K-armed bandits\" are essentially the entry-sparse case discussed in our paper, where $\\theta \\in \\mathbb R^d$ has the number of non-zero entries limited to $s$. For canonical K-armed bandits where the agent aims to identify the arm with the highest expected reward, we can consider a sole non-zero-mean reward arm, that is to set $s=1$ and $d=K$.\n\nFor the entry-sparse case. When the assumption class permits any arbitrary action set, [11] shows that $\\Omega(\\sqrt{sdn})$ can be constructed in the data-rich regime, i.e. assuming $d \\ll n$, while $\\Omega(n)$ can be trivially constructed in the data-poor regime. When the assumption class only considers those action sets that can admit a well-conditioned exploration distribution, i.e. $C_{\\min}(\\mathcal A) > 0$, [7] gives a lower bound of$\\min(C_{\\min}^{-1/3}s^{1/3}n^{2/3},\\sqrt{dn})$, which is improved to $\\min(C_{\\min}^{-1/3}s^{2/3}n^{2/3},\\sqrt{sdn})$in our Corollary 4.1.\n\nWhile it is a modest improvement when one constrains the scope to that specific assumption class, i.e. $C_{\\min}(\\mathcal A) > 0$ and entry-sparse $\\theta$, we emphasize that our framework elevates the discussion by offering a unified view and enables extension of existing lower and upper bounds analysis in specific cases.\n\n> Your results seems to highlight gaps between lower and upper bounds, either in the C_min dependency or in the other problem quantities. All sections 4.1, 4.2, 4.3 are purely technical and do not discuss the implications of your results. Can you comment on the gaps you opened and whether you believe the lower bounds could be attainable? or perhaps what may cause sub-optimality in the upper-bounds?\n\nEssentially, our framework operates by manipulating succinct groups where some support can be constructed by selecting one element from each group. In the constructional proof, to obtain the final action set $\\mathcal A := \\mathcal S \\cup \\mathcal H$, we constructed $\\mathcal S$-based actions that are s-succinct and thus uninformative when playing under the s-succinct parameters coming from the same succinct groups. Meanwhile, we impose that $\\mathcal H$-based actions incur high regret under a specific instance $\\theta_0$ coming from a \"complementary succinct region\". The trade-off yields our lower bound in the Theorem 3.8. In Section 4, we demonstrate that this general construction is valid when instantiated to the three specific assumption classes, i.e.$C_{\\min}(\\mathcal A) > 0$ in the three cases. \n\nFor the entry-sparse case, the resulting lower bound is optimal in the data-rich regime and nearly optimal by a gap of $C_{\\min}^{-1/3}$ in the data-poor regime, since there are algorithms offering matching upper bounds. From corollaries in Section 4, we believe that the construction framework can yield rather tight lower bounds in a generalized $C_{\\min} > 0$ assumption class. Proving so would likely require generalization of those algorithms, which is beyond the scope of our current study. However, from an intuitive standpoint, our framework lower-bounds the regret by imposing that $\\mathcal H$-based actions incur constant regret, and by optimistically assuming that $\\mathcal H$-based actions could be informative with respect to those s-succinct parameters, unlike s-succinct $\\mathcal S$-based actions. That optimistic assumption is materialized in the corollaries by imposing $C_{\\min}(\\mathcal H) > 0$. \n\nWe also recognize that there may be alternative ways to construct this information-regret trade-off. In its current form, the framework simply uses Assumption 3.7 (1), i.e. the constant sub-optimal gap under certain $\\theta_0$, to discourage playing the potentially informative $\\mathcal H$-based actions. This prevents degenerate cases such as a wildcard action $(1,1,1,...,1)$ that could always be played with zero regret under any s-sparse $\\theta\\in \\mathbb R^d$ with positive entries. It would be interesting to investigate possible replacements of the Assumption 3.7 (1) in our framework."}, {"review_id": "oWLKyJM1XH", "reviewer": "Reviewer_fbhz", "summary": "This paper presents an algebraic approach to defining *succinctness* and constructs a framework for the linear bandit problem with a succinct parameter, which encompasses entry-sparse vectors, low-rank matrices, and group-sparse matrices. The paper provides a regret lower bound under this framework, and the resulting lower bounds for each application are either new or improved.", "questions": "1. In Corollary 4.2, it seems like it should be $Q(\\cdot) = || \\cdot ||_ {2, \\infty}$ and $R(\\cdot) = || \\cdot ||_ {2, 1}$, which correspond to the maximum and the sum of $\\ell_ 2$ norms of the rows, respectively. Could the authors confirm this, or clarify the exact definitions of the matrix norms in the paper?\n\n2. I am curious about where the term *succinct* comes from. Is it a concept newly introduced in this paper, or is it an existing one? If it is the former, I suggest noting this in the abstract, as facing the word *succinct* before its description adds slight confusion.\n\n\n**Minor comments (Typos)**\n\nI could not find the definition of $\\Delta_{\\mathcal{X}}$, which appears for the first time in line 210. I could easily guess its definition, but I believe the authors would prefer to have it explicitly defined.  \nIn line 224, should it not be $1/2$ instead of $1/4$?  \nIn line 258, should it not be $C_{\\min}(\\mathcal{A}) > 0$ instead of $\\ge 0$, as the latter is always true?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The paper identifies core and common properties of three distinct problems (entry-sparsity, low-rank, and group-sparsity) and conducts the analysis under minimal assumptions. This approach is indeed novel and general. I believe it sets a strong example of how theoretical approach can unify multiple problem classes.\n\n2. The derived lower bounds improve upon previous ones, demonstrating the strength of the analysis.\n\n3. The introduction of the $Q$ and $R$ norms in the framework provides insight into which norm should be used in the boundedness assumptions for individual problem settings.\n\n\nWeaknesses\n\n1. The final step of the proof of the main theorem, as well as the proofs of the corollaries, is somewhat difficult to follow. For instance, it took me some time to understand that the phrase “we obtain the lower bound $\\min( \\frac{ns\\varepsilon}{24}\\exp(-2\\varepsilon [ \\frac{n}{p}+ \\frac{h}{q}]), \\frac{C_0}{3}h )$” in line 237 means that the worst-case regret is lower bounded by this expression for *any* $h$, as the intermediate steps are largely omitted. In the proofs of the corollaries, I would appreciate a bit more elaboration on how the bounds for $C_{\\min}(\\mathcal{H})$, $p$, and $q$ are obtained. While I understand it is mostly tedious calculation, I believe it would be helpful for readers if the authors briefly indicated what exactly needs to be computed.\n\n2. The final step of the proof of Theorem 3.8 introduces certain conditions on $n$, for example, $9s^2p \\le C_0^2 n$ in line 240, which are not mentioned in the theorem statement. Including these assumptions explicitly would improve clarity.\n\n3. The lower bound of $\\Omega(\\sqrt{sdn})$ from [11] is mentioned in the related work section but is omitted from Table 1, which could be slightly misleading.", "was_revised": true, "final_justification": "The paper provides a new and unified perspective on constructing lower bounds for three distinct problems, and the bounds improve upon the previous ones.\nThis paper has significant theoretical contributions and is technically sound.  \nThe main concern that was raised by all the reviewers was lack of details and explantions in Sections 3 and 4, and the authors agreed that those sections are hard to follow and promised improvements.\nBased on the premise that Sections 3 and 4 will contain more details in the final version as promised, I support the acceptance of the paper.", "rebuttal": "> 1. ... identifies core and common properties of three distinct problems... and conducts the analysis under minimal assumptions. This approach is indeed novel and general... sets a strong example of how theoretical approach can unify multiple problem classes.\n\nWe sincerely thank the reviewer for the appreciation of our work.\n\n> 1. The final step of the proof of the main theorem, as well as the proofs of the corollaries, is somewhat difficult to follow. For instance, it took me some time to understand that the phrase \"we obtain the lower bound $\\min(...)$\" in line 237 means that the worst-case regret is lower bounded by this expression for any h, as the intermediate steps are largely omitted. In the proofs of the corollaries, I would appreciate a bit more elaboration on how the bounds for $C_{\\min}(\\mathcal H)$, p, and q are obtained. While I understand it is mostly tedious calculation, I believe it would be helpful for readers if the authors briefly indicated what exactly needs to be computed.\n\nYes. In line 237, we meant to say that by combining the lower bounds (4) and (5) in a minimum expression, we can replace the quantity $\\max\\_{\\theta\\in\\Theta} \\mathbb E \\_\\theta [|T_{\\mathcal{H}}|]$ with a free variable $h$ (since one bound tightens by the growth of the constrained quantity and the other loosens) and then obtain the lower bound. We will rephrase it to stress that the bound $\\min(...)$ holds for any $h$. We agree that the proofs of the corollaries would benefit from more elaboration. While the derivations involve mostly routine calculations --- especially so when one realizes that we are simply manipulating groups of basis vectors that can span the whole space and can form some succinct support --- we will revise both the main text and the appendix to provide clearer guidance.\n\n> 2. The final step of the proof of Theorem 3.8 introduces certain conditions on n, for example, $9s^2p \\leq C_0^2n$ in line 240, which are not mentioned in the theorem statement. Including these assumptions explicitly would improve clarity.\n\nThank you for the suggestion. As is common in the literature, lower bounds are typically stated in a \"there exists an instance\" manner to avoid overloading the theorem statement with all the construction details. Some minor construction conditions are often omitted, unless they are directly relevant to the compatibility with the assumption class of interest, such as data-poor and data-rich regimes, e.g., $d \\ll n$. To fully verify compatibility, one must examine the specific instance constructed in the proof. For example, if there's some signal magnitude assumption imposed on $\\theta$, one should also check whether the constructed $\\theta$ satisfies it. That said, we agree that clarity is important, and we will consider discussing such conditions more explicitly or summarizing them in a remark.\n\n> 3. The lower bound of $\\Omega(\\sqrt{sdn})$ from [11] is mentioned in the related work section but is omitted from Table 1, which could be slightly misleading.\n\nYou are right. This was an unintentional omission. We will update Table 1 to include it.\n\n> 1. In Corollary 4.2, it seems like it should be $Q(.) = \\\\| \\cdot \\\\|\\_{2,\\infty}$ and $R(.) = \\\\| \\cdot \\\\|\\_{2,1}$, which correspond to the maximum and the sum of $\\ell_2$ norms of the rows, respectively. Could the authors confirm this, or clarify the exact definitions of the matrix norms in the paper?\n\nThanks for bringing it to our attention. We acknowledge that the notation for matrix norms in the paper may be unconventional and potentially ambiguous. To clarify, for a matrix $X\\in \\mathbb{R} ^{d_1\\times d_2}$, we intended the following definitions:\n\n$\\\\| X \\\\|\\_{1, 2} := \\sum_{i=1} ^{d_1} \\left(\\sum_{j=1} ^{d_2} |x_{ij}|^2\\right)^{1/2}$\n\n$\\\\| X \\\\|\\_{\\infty, 2} := \\max_{1\\leq i \\leq d_1} \\left(\\sum_{j=1} ^{d_2} |x_{ij}|^2\\right)^{1/2}$\n\nWe will revise the notation to follow standard conventions, changing the subscript order, e.g. from $\\\\|.\\\\|\\_{\\infty, 2}$ to $\\\\|.\\\\|\\_{2,\\infty}$.\n\n> 2. I am curious about where the term succinct comes from. Is it a concept newly introduced in this paper, or is it an existing one? If it is the former, I suggest noting this in the abstract, as facing the word succinct before its description adds slight confusion.\n\nWe developed the concept of succinctness in the context of identifying the common algebraic structure underlying these bandit problems. We chose the term \"succinct\" to distinguish it from \"sparse\", commonly seen in literature on the entry-sparse bandits. While the concept arose independently during our work and we did not find prior references specific to this setting, it is not hard at all to imagine that similar concepts have been explored, or even extensively studied in other domains or settings, as it represents a natural extension of general vector space theory. We appreciate the suggestion and will consider some further clarification in the abstract.\n\n> Minor comments (Typos)\n\n> I could not find the definition of $\\Delta_\\theta(X)$, which appears for the first time in line 210. I could easily guess its definition, but I believe the authors would prefer to have it explicitly defined.\n\n> In line 224, should it not be 1/2 instead of 1/4?\n\n> In line 258, should it not be $C_\\min(\\mathcal A)>0$ instead of $C_\\min(\\mathcal A) \\geq 0$, as the latter is always true?\n\nThank you for your careful review. Your comments are all valid. We clarify that $\\Delta_\\theta(X)$ represents the sub-optimal gap of any $X\\in\\mathcal{H}$ and is formally defined as\n\n$\\Delta_\\theta(X) := \\max_{X^* \\in \\mathcal A} \\langle X^*, \\theta \\rangle - \\langle X, \\theta\\rangle$\n\nThis will be explicitly introduced at its first appearance in the revised version. We also agree with the corrections in lines 224 and 258 and will update them accordingly."}]

Author rebuttal:

Meta-review: This paper studies lower bounds for linear bandits under structural assumptions like sparsity of low-rankedness. The reviewers agree the results are correct and constitute a significant contribution to the mature area of linear bandits. While some reviewers brought up concerns about tightness and required clarifications, these issues were resolved during the review process.
Decision: Accept (poster)