Symmetric Linear Bandits with Hidden Symmetry
Authors: Nam Phuong Tran
The-Anh Ta
Debmalya Mandal
Long Tran-Thanh
Venue: NeurIPS 2024 poster (2024)
Keywords: Bandit theory
group theory
symmetry
sparsity.
Primary area: bandits
TL;DR: We study the symmetry structure in high-dimensional linear bandits. With certain assumptions, our algorithm achieves regret that depends logarithmically on the ambient dimension.

Abstract: High-dimensional linear bandits with low-dimensional structure have received considerable attention in recent studies due to their practical significance. The most common structure in the literature is sparsity. However, it may not be available in practice. Symmetry, where the reward is invariant under certain groups of transformations on the set of arms, is another important inductive bias in the high-dimensional case that covers many standard structures, including sparsity. In this work, we study high-dimensional symmetric linear bandits where the symmetry is hidden from the learner, and the correct symmetry needs to be learned in an online setting. We examine the structure of a collection of hidden symmetry and provide a method based on model selection within the collection of low-dimensional subspaces. Our algorithm achieves a regret bound of $ O(d_0^{2/3} T^{2/3} \log(d))$, where $d$ is the ambient dimension which is potentially very large, and $d_0$ is the dimension of the true low-dimensional subspace such that $d_0 \ll d$. With an extra assumption on well-separated models, we can further improve the regret to $ O(d_0 \sqrt{T\log(d)} )$.

Symmetric Linear Bandits with Hidden Symmetry
Nam Phuong Tran Department of Computer Science
The Anh Ta CSIRO's Data61 Marsfield, NSW, Australia theanh.. ta@csiro....... au
University of Warwick Coventry, United Kingdom
p. wwwwwwarwickk ac. uk
Debmalya Mandal
Long TranTThanh Department of Computer Science
Department of Computer Science
University of Warwick
University of Warwick Coventry, United Kingdom long brran-hhanh@warrickk ac uk
Coventry, United Kingdom
debmalya. mandalllaaallllmaam @warwick ck. ac. uk
Abstract
High-dimensional linear bandits with low-dimensional structure have received considerable attention in recent studies due to their practical significance. The most common structure in the literature is sparsity. However, it may not be available in practice. Symmetry, where the reward is invariant under certain groups of transformations the set of arms, is another important inductive bias in the high- dimensional case that covers many standard structures, including sparsity. In this work, we study high-dimensional symmetric linear bandits where the symmetry is hidden from the learner, and the correct symmetry needs to be learned in an online setting. We examine the structure of a collection of hidden symmetry and provide a method based on model selection within the collection of low-dimensional subspaces. Our algorithm achieves regret bound of (1 log(d)), where d is the ambient dimension which is potentially very large, and do is the dimension of the true low-dimensional subspace such that dg d. With an extra assumption well-separated models, we can further improve the regret O(do / log(d)).
Introduction
Stochastic bandit is a sequential decision decision-making problem in which a player, who aims to maximize her reward, selects action each step and receives stochastic reward, drawn from an initially unknown distribution of the selected arm, in response. Linear stochastic bandit (LSB) [1] is an important variant in which the expected value of the reward is a linear function of the action. It is one of the most studied bandit variants and has many practical applications [27].
Actions in LSB are specified as feature vectors Rd for very large feature dimension d, with performance i.e. the resulting regret scaling with d. Many works have addressed this curse of dimensionality by leveraging different low-dimensional structures as inductive biases for the learner. For example, sparsity, which assumes that the reward is sparse linear function, has been used extensively in LSB to design bandit algorithms with better performance [2, 36, 23]. However, when the reward function lacks the structure for sparsity (which may occur in many real-world situations), question arises: Are there different structures in the features of LSB that we can exploit to overcome the curse of dimensionality and design bandit algorithms with better performance?
In this paper, we study the inductive bias induced by symmetry structures in LSB, which is a more general model inductive bias than sparsity, and can facilitate efficient and effective learning [9]. Symmetry describes how, under certain transformations of the input of the problem, the outcome
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

should either remain unchanged (invariance) or shift predictably (equivariance). In supervised learning, it has been empirically observed [17. 12] and theoretically proven [16, 6] that explicitly integrating symmetry into models leads to improved generalization error. However, in the literature on sequential decision-making, unlike sparsity, symmetry is rarely considered to date. This leads us to the following research question: Can one leverage symmetry in sequential decision-making tasks to enable effective exploration, and eventually break the curse of dimensionality?
In the machine learning literature, especially in supervised learning, most studies symmetry assume prior knowledge of symmetry structures of the tasks under consideration [31, 16]. However, in numerous practical scenarios, the learner can only access partial knowledge of the symmetry, necessitating the incorporation of symmetry learning mechanisms into the algorithms to achieve better performance. Examples of hidden symmetry can be found in multi-agent learning with cooperative behavior. As motivating example, consider company undertaking large project that consists of several subtasks. The company must hire subcontractors with the goal of maximizing project quality while staying within budget constraints. Symmetry may arise in this situation when coalitions form among subcontractors, where members of coalition work together to complete their allocated tasks using shared resources. In particular, the allocation of tasks within a coalition can be swapped without affecting overall team performance, inducing symmetry (i.e., performance remains invariant under permutation) in the task assignments. Coalitions among subcontractors often arise since sharing labor and resources reduces operational costs, making their work more efficient and cost-effective. However, these coalitions are typically hidden from the hiring company. One reason is that if the hiring company were aware of these collaborations, they could use this information to negotiate lower prices, knowing that the subcontractors are benefiting from shared resources. Another reason is that coalitions may raise concerns about collusion. In particular, in a competitive market, such as when subcontractors are hired through bidding platform, coalition members collaborate to manipulate the bidding process, which is considered unfair and could undermine the integrity of the bidding. For more practical examples of hidden symmetry in multi-agent reinforcement learning [34] and robotics [3], we refer the reader to Appendix D.2. Motivated by these examples, we believe that hidden symmetry is much more relevant in the context of sequential decision-making because the environment and its symmetry structure may not be readily available to the learner, as opposed to supervised learning and offline settings where data are provided during the training phase. As the learner has the power to freely collect data, it is expected that they will learn the hidden symmetry structures as they explore the environment.
Against this background, we ask the question of whether learner can leverage symmetry to enable effective exploration, and break the curse of dimensionality without a prior knowledge of the symmetry structure? Moreover, in the presence of symmetry, when can design learning algorithms with optimal regret bounds? Towards answering this question, we investigate the setting of symmetric linear stochastic bandit in Rdd where d is potentially very large, and the expected reward function is invariant with respect to the actions of a hidden group G of coordinate permutations. Our contributions summarised as follows:
1.
We first give an impossibility result that no algorithm can get any benefit by solety knowing that G is a subgroup of permutation matrices. We achieve this by formally establishing a relation between the class of subgroup to the partition over the set {1..... d). A direct implication of this impossibility result is that it necessary to have further information about the structure of the hidden subgroup in order to achieve improved regret bounds.
2. Given this, we establish a cardinality condition on the class of symmetric linear bandits with hidden G, in which the learner can learn the true symmetry structure and overcome the curse of dimensionality. Notably, this class includes a sparsity as a special case, and therefore inherits all the computational and statistical complexities of sparsity. Apart from sparsity, this class includes many other practically relevant classes, such as partitions that respect underlying hierarchies, non-crossing partitions, and non-nesting partitions (see Subsection 4.2.1 and Appendix D.2).
3. We cast our problem of learning with hidden subgroup G into model selection with collection of low-dimensional subspaces [25, 35]. To address the polynomial scaling of regret bounds with respect to the number of models and arms in previous works, we depart from model aggregation, which is typically used in LSB model selection, and introduce new framework

---

inspired by Gaussian model selection [7] and compressed sensing [8]. Based on this framework, we introduce a new algorithm, called EMC (for Explore Models then Commit). Under the assumption that the set of arm is exploratory, we prove that the regret bound of the EMC algorithm is (d//312// log(d)), and O / (oggolllg()) (d)( with additional assumption on well-separated partitions, where do < d is the dimension of the low-dimensional subspace associated with group G.
To the best of our knowledge, our work is the first in the linear stochastic bandits literature that leverages symmetry in designing provably efficient algorithms. To save space, all proofs in this paper are deferred to the Appendix.
1.1 Related Work
We now briefly outline related work and compare them with our results. We refer the reader to Appendix F for a more in-depth literature review.
Sparse linear bandits. As we will explain in Section 4.2, sparsity is equivalent to a subset symmetry structures, and thus, can be seen as a special case of our setting. As such, we first review the literature of sparsity. Sparse linear bandits were first investigated in [2], where the authors achieve a regret of Ó( dss),, with Ô disregarding the logarithmic factor, and representing the sparsity level, and T is the time horizon. This matches the regret lower bound for sparse bandits, which is ds) [27]. More recently, the contextual version of linear bandits has gained popularity, where additional assumptions are made regarding the context distribution and set of arms [26, 36, 28, 11, 23] to avoid polynomial dependence on d. Notably, with the assumption on exploratory set of arms, [23] propose an Explore then Commit style strategy that achieves T ), nearly matching the regret lower bound ((s T [24] in the data-poor regime. As sparsity is equivalent to a subclass of hidden symmetry, all the lower bounds for sparse problems apply to our setting of learning with hidden symmetry.
Model selection. Our problem is also closely related to the problem of model selection in linear bandits, as the learner can collect potential candidates for the hidden symmetry model. Particularly, in model selection, there a collection of M features, and different linear bandits running with each of these features serve as base algorithms. By exploiting the fact that the data can be shared across all the base algorithms, the dependence of regret in terms of the number of features can be reduced to lM)( In particular, [25] propose method that concatenates all M features of dimension d into one feature of dimension Md, and uses the Lasso estimation as a aggregation of models. Their algorithm achieves a regret bound of O vlog(M) under the assumption that the Fuclidean norm of the concatenated feature is bounded by constant. However, in our case, the Euclidean norm of the concatenated feature vector can be as large as vM, which leads to VM multiplicative factor in the regret bound. Besides, [35] uses the online aggregation oracle approach, and is able to obtain regret of O( / dT log(M)) where K is the number of arms. In contrast, we use algorithmic mechanisms that are different from aggregation of models. In particular, we explicitly exploit the structure of the model class as a collection of subspaces and invoke results from Gaussian model selection [21, 7] and dimension reduction on the union of subspaces [8]. With this technique, we able achieve O (M), which is rate-optimal in the data-poor regime, has logarithmic dependence M without strong assumptions on the norm of concatenated features, and is independent of the number of arms K. We refer the reader Section 4.2 for a more detailed explanation.
Symmetry in online learning. The notion of symmetry in Markov decision process dates back to works such as [0]. Generally, the reward function and probability transition are preserved under an action of a group on the state-action space. Exploiting known symmetry has been shown to help achieve better performance empirically [43, 42] tighter regret bounds theoretically [41]. However, all these works requires knowledge of symmetry group, while our setting consider hidden symmetry group which may be considerably harder. Hidden symmetry on the context or state space has been studied by few authors, with the term context-lumpalte can be partitioned into classes of similar contexts. It is important note that the symmetry group acts differently on the context space and the action space. As we shall explain in detail in Section 3, while one can achieve a reduction in terms of regret the case of hidden symmetry acting on context
bandits [29], meaning that the set of contexts
'We note that "Gaussian model selection") is a technique in statistics, similar to model aggregation (see [21]'s chapter and 4), which should not be confused with "model selection" in the bandit literature.
3

---

spaces [29], this is not the case when the symmetry group acts on the action space. The work closest to ours is [39], where the authors consider the setting of K Kaareed bandit, where the set of arms can be partitioned into groups with similar mean rewards, such that each group has at least > 2 arms. With the constrained partition, the instance-dependent regret bounds are shown asymptotically to be of order O log ) Comparing [39], study the setting of stochastic linear bandits with similar arms, in which the (hidden) symmetry and linearity structure may intertwine, making the problem more sophisticated. We also impose different constraints the way one partitions the set of arms, which is more natural in the setting of linear bandits with infinite arms.
2 Problem Setting
k). For C R&, let (X denote the set of probability measures supported on X. Given a set IR for some 1, denote [I) as the Euclidean projection of IR on S, and conv(S) as the convex hull of S.
For any k E N+, denote [k] [l,...,kk)
We denote by T the number of rounds, which is assumed be known in advance. Each round E [T'. the agent chooses an arm I; E X C R2, and nature returns stochastic reward yt (xr, 0.) + Tk: where 7/ is an i.i.d. g-Gaussian random variable. Now, denote (xz) = Efye xe)_ A bandit strategy a decision rule for choosing an arm Ie in round [T]. given past observations up to round t 1.
Formally, bandit strategy is mapping A: (X' x R - (
Σ 1 (a.- Zt, 0.) denote the expected cumulative regret. In this paper. we investigate the question whether one can get any reduction in term of regret, if the reward function is invariant under the action a hidden group of transformations on the set of arms. We define the notion of group of symmetry as follows:
Let x, arg max f (z). and let Ry-
Group and group action. Given E N+, let S, denote the symmetry group of [d]. that is, Sa:= (h : d] d] h is bijective) the collection of all bijective mappings from [d] to itself. We
also define the group action è of Sa on the vector space I² as
: x TRd
Rd
(g, (x)))
+ (ro(())E(())
In other words, group element acts on an arm E Id by permuting the coordinates of x. In the setting of linear bandit, the permutation group action also acts on the set of parameters via coordinate permutation. For brevity, we simply denote g 9 and g as و(g, 0) and ő(g, z). respectively. Denote by Ag the permutation matrix corresponding to g. We write G S Sa denote that 9 is a subgroup of Sa. Given any point 0 e Fd we write A == {g 0 g E 9} to denote the orbit of & under G. It is well known that the orbit induced by the induced action of subgroup G I Sa corresponds to set partition of [d]. We denote this partition as Tg.
Let G be a subgroup of Sy that acts on Tee via the action A. In symmetric linear bandit, the expected reward invariant under the group action of 9 on X, that is, f(g 2) = f(x). Due to the linear structure of f. this is equivalent to g 0, = f, for all E G. We assume that, while the group action & is known to the learner, the specific subgroup G is hidden and must be learned in an online manner.
3 Impossibility Result of Learning with General Hidden Subgroups
We now show how frame the learning problem with hidden symmetry group as the problem of model selection. We further analyse the structure of the collection of models, and show that no algorithm can benefit by solely knowing that < Sa, which implies that further assumptions are required to achieve significant improvement in term of regret.
3.1 Fixed Point Subspace and Partition
The analysis of learning with hidden subgroup requires group-theoretic notion which is referred to as fixed-point subspaces [10]. As we shall explain promptly, there is a tight connection between the collection of fixed-point subspaces and set partitions.

---

Fixed-point subspaces. For a subset X' S R denote Fixx(A)) := {x X 9 g.. Ag } as the fixed-point subspace of G; and Fs,(X) (X) (Fix; (X) 9 S Sa) as the collection of all fixed- point subspaces of all subgroups of Sg. We simply write Fs,- Fsa (IRa) and Fixg F Fixg (R2)) for brevity.
Set partition. Given d E N+, we denote Pa as the set of all partitions of [d]. Let Pa,k as the set of all partitions of [d] with exactly k classes, and Pa,sk k be the set of all partitions of [d] with at most ls classes The number of set partitions with classes (Pa, is known as the Stirling number of the second kind, and [Pa] is known as Bell number.
3.2 Impossibility Result
Problem with known symmetry. Before discussing the problem of hidden symmetry, let us explain why the learner with an exact knowledge of & can trivially achieve smaller regret. The reason is that 0, E Fixg by the assumption that 0, is invariant w.rt the action of group G. If g is known in advance, the learner can restrict the support of 0, in Fixg, and immediately obtains that the regret scales with dim(Fixg) instead of d, which can be significantly smaller (e.g.. if Sa. then dim(Fixg) = 1).
For any subgroup, there exists fixed point subspace, and some subgroups may share the same fixed point subspace. Therefore, instead of constructing a collection of subgroups, one can create a smaller collection of models using the collection of fixed point subspaces. As is hidden, must learn Fixg within the set of candidates Fsy, leading to the formulation the model selection.
From the setting with hidden subgroup to the setting with hidden set partition. Now, discuss the structure of the collection of models Fs.. First, we show the equivalent structure between the collection of fixed point subspaces and the partitions follows.
Proposition 1. There a bijection H between Pa and FSa
As there is a bijection between Pa and Fs.,, we can count the number of subspaces of each dimension l explicitly using the following.
Proposition 2 ([10J's Theorem 14). Given subgroup I' Sa and its fixed-point subspace Fixr, suppose that गा partitions [d] into k classes, then dim(Fixr) = k.
By Proposition 2, we have that the number of subspaces of dimension le in Fs., is exactly the number of set partitions with k-classes. Suppose that the learner knows that the orbit under action of g partitions the index of 0, into 2 equivalent classes that is, clim = 2. The learner cannot get any reduction in terms of regret.
Proposition 3. Assume that the action set is the unit cube X = {ur E Rd || S. 1}, and f is invariant w.r.t. action of subgroup G < Sq, such that dim(Fixg) = 2. Then, the regret of any bandit algorithm is lower bounded by RT = (d
The implication of Proposition 3 is that even if the learner knows 0. lies in an extremely low- dimensional subspace within the finite pools of candidates, they still suffer regret that scales linearly with the ambient dimension d. This suggests that further information about the group & must assumed be known in order to break this polynomial dependence on d in the regret bound.
The Case of Hidden Subgroups with Subexponential Size
As indicated by Proposition 3, there is improvement in terms of regret, despite the learner having access to a collection of extremely low-dimensional fixed point subspaces. Therefore, we assume that the learner can access only a reasonably small subset of the collection of low-dimensional fixed point subspaces. Let dn be the upper bound for the dimension of fixed point subspaces; that is, we know that the orbit of & partitions [d] into at most de classes. Now, let us assume that the learner knows that G does not partition [d] freely, but must satisfy certain constraints, that is, Tg E Qd. C. Pa. Here, Qa.5á, a small collection of partitions with at most do classes, which encodes the constraints on the way 9 partitions [d]. We introduce an assumption regarding the cardinality of <d. which formally stated in Section 4.2. Using the Proposition 1, we can define the collection of fixed point subspaces associated with the collection of partition Qd.5d, via the bijection H as
M = H (Qa.sdo) and M == [M].
In addition, let us define the extension of the collection M as M {conv (m U Um)) I m, m' e M), where conv(s) is the convex hull of the set S C R
5

---

We have that M is collection of subspaces, that is, conv (m U m²) ) is indeed a subspace [8]. Denote M == M then we have M = (M² /2. Moreover, if dimension of subspace in M is at most du then the dimension of subspace in J is at most 2dg
4.1 The Explore- Moo-MMoolllssee -e----e--tth---oommee Algorithm
Given some [T'], we define
Y = X0, + 77
where Y E R", X = [_1,..... Fnl" E Raxd is the design matrix, 0. Rd is the true model; n- = mn, ..... mn We have the information that 0. must be contained in some (not necessarily unique) subspace m E M. Denote by dm the dimension of m, we have dm S dg for any m M.. Let Xm Im (xx)) and Sn be the column space of Xms one has dim(Sm) I dm- For any
m E M. and given Y, let Ils.. (-) be the projection onto Sm. Define
fm = Im (V); Om == arg min J|Y - x012
(3)
Now, given data points, we can choose the model mn E M that minimises the least square error
m E arg min || MEM
fm 12
(4)
Based on the framework of model selection, we now introduce our Algorithm 1. Mallore-Models -eelss--e----eeeee Jahen-Comitt (EMC). Our algorithm falls into the class bandit algorithms. The exploration phase consists of t rounds. During this phase, one samples data independently and identically distributed (i.i..)) from an exploratory distribution v. After the exploration phase, one computes the solution to the model selection problem and then commits the best arm corresponding to the chosen model.
Remark The key step of Algorithm that may incur significant costs is solving equation (4) (line 6). Without additional information about M, one might need to enumerate all models in M and optimize among them, which would induce a time complexity of O(nd However, if we have more information about the partitions, e.g., if they are non-crossing or non-nesting partitions, their lattice structures can be exploited to speed up the optimization process of solving equation (4). Due to space limitations, we refer readers to Appendix D.3 for detailed explanation of a subroutine that leverages these lattice structures for more efficient computation. Additionally, Section 6 demonstrates that Algorithm 1, when using the lattice search algorithm for non-crossing partitions and non- nesting partitions as a subroutine, achieves polynomial computational complexity of O(nd)) and guarantees low regret.
4.2 Regret Analysis
Algorithm Explore Models then Commit
The regret analysis of Algorithm uses results from the Gaussian model selection literature [7, 21] as a basis. As such, we first state the assumptions that are common in the Gaussian model selection literature on the collection of models M and the set of arms X' (Section 1.2.1). We then provide our main analysis in Section 4.2.2, highlighting the key technical novelties of our approach.
1: Input: T, v, 4
2: for / = 11,,....44 do
3: Independently pull arm x, according to v/ and receive a reward yt-
4: end for
5: X + [21,..., It,, IT,Y + [ulket
Compute mn as (4).
Compute 01, as (3) corresponding to m.
4.2.1 Assumptions
8: for t = f1 + 1 to T do
Take greedy actions:
Recall that due to our lower bound in Proposition 3, further assumptions are required on the collection of fixed-point subspaces
Z4 arg min (0,.2). xE
achieve reduction in terms of regret. As suggested by the model selection literature [25, 35), one can achieve regret in terms of log(M) MM) for a collection of M models. Adopting this idea, we make the following assumption regarding the number of potential fixed-point subspaces and the set of arms.
10: end for

---

Assumption 5 (Sub-exponential number of partitions). The partition corresponding to g belongs to a small subclass of partitions Qa C Pa particular. Tg Qa.d., for some d, S dg. for each E [do], there exists a constant e > 0, such that 12d, S ).
Assumption 6 (Bounded set of arms). There are positive numbers Kgs Reuas such that, for all X and m M. I| (z))l < Kz, and (2r, 0-) S Rmaxx
As consequence of Assumption 5, the cardinality of the collection of fixed point subspaces is not too large, particularly, M (dddo). First, we note that this class includes interval partitions, structure equivalent to sparsity as a strict subset, as explained below.
Remark 7 (Equivalence between sparsity and interval partition). A set partition of [d] is an interval partition partition of interval if its parts interval. We denote Ia the collection of all interval partition of d. Ia admits a Boolean lattice of order 2d-1, making equivalent to the sparsity structure in d - 1 dimensions. Specifically, consider the set of entries of parameters yp Rd with a linear order, that is, şi 2 822 2 2 (d.- Then define the variable 0 E IRd-1 such that 0. (ypr - 10i+1). Each interval partition on the entries of oo will determine unique sparse pattern of 0. Therefore, is clear that the cardinality of the set of interval partition with do classes is bounded as <d Oddo).. Moreover, as a result, symmetric linear bandit is strictly harder than sparse bandit and inherits all the computational complexity challenges of sparse linear bandit, including the NP-hardness of computational complexity.
Apart from sparsity, class of partitions with sub- exponential size also naturally appears when there a hierarchical structure on the set [d]. and the partitioning needs to respect this hierarchical structure. A partition that respects ordered tree groups the children of the same node into a single equivalence class, for example, see Fig- ure 1. It is shown in [15] and the cardinality of the set of partitions that respect ordered trees is sub-exponential. Furthermore, as shown in [15] there is bijection between partitions that respect ordered trees and the set of non- crossing partitions.
3
c
Figure Partition that respects the un- derlying ordered tree.
real-life example that meets these assumptions is the subcontractor example in the introduction: hierarchical structure may exist, where hired subcontractor can further subcontract parts of the work to others. A tree represents the hierarchical order among subcontractors, where subcontractors hired by another contractor can be grouped into one class. Further real-life examples of non-crossing partitions and other structured partitions that satisfy sub-exponential cardinality, such as non-nesting partitions and pattern- avoidance partitions [33], can be found in Appendix D.2.
Next, similar as [23], we define the exploratory distribution as follows.
Definition 8 (Exploratory distribution). The exploratory distribution P E A(X) is solution of the following optimisation problem
V = arg max Amin (Ezow I), V := Ex J, Cmin (X) = Amin Amin(V). (V).
(5)
wE)(Z)
Since our setting includes sparsity as a special case, the regret lower bound in [24] applies to our setting as well. In particular, we have:
Proposition 9 (Regret lower bound). There exist symmetric linear bandit instances in which Assumption 5, 6 hold with K2 8dg, such that, any bandit algorithm must suffer regret Ry Ω (min (X)) $ d T vaT))
We note that the lower bound can be relaxed if we have a stronger assumption on the group G, which allows algorithm to go beyond the lower bound in Proposition 9 of the sparsity class. For example, we consider collection of fixed-pont -oint subspaces with a nested structure, similar to those discussed in [20], the algorithm may achieve O(doVT) rate. The key takeaway is that symmetry exhibits significant flexibility in structure. Depending on the specific class of symmetry, one may achieve either no reduction at all or significant reduction in terms of regret bound.
7

---

4.2.2 Main Regret Upper Bound Result
We now state the main result of the regret upper bound for Algorithm 1.
Theorem 10 (Regret upper bound). Suppose the Assumptions 5, 6 hold. With the choice of t Rmaxo C min (2)) K3 di T (log(dT))3, then the regret of Algorithm 1 is upper bounded as
Rr 0 o C. (X)) de T (log(dT))
Remark 11. We note that when K₂ (do), as in the lower bound instances, our upper bound is ò (Cmia (x) ) which matches the lower bound in Proposition 9.
The main idea is to bound the risk error after exploration rounds, as stated in the following lemma which implies the regret bound after standard manipulations.
Lemma 12. Suppose the Assumptions 5, hold. For t1 22K3do log(d/0)) with probability at least 1 - 8, one has the estimate
0- 0 11:
= =0
/ log(d/5) )
Cmin (2()tz
Remark 13 (Non-triviality of Lemma 12). At the first glance, it seems that we can cast the problem of learning with a collection of M subspaces into a model selection problem in linear bandit with M features. This leads to a question: Can we apply the model selection framework based on model aggregation in [35, 25] to our case?
First, let us explain how to cast our problem into a model selection problem in linear bandit. For each subspace m, let 2m _2 do be the feature map that computes the image of the projection I1m with respect to the orthogonal basis of subspace m. Thus, we then have a collection of M features ( MEM. Consider the algorithm introduced in [25], which concatenates the feature maps into ((x) = (Tr) 2 as (xr] E R-Mdo, and the regret bound depends on (1)
only bound | (2))ll2 S VM, which leads to VM dependence on regret, if we use their algorithm. Regarding [35], their algorithm aggregates the predictions among models for each arm, and based on that, they compute the distribution for choosing each arm. This leads to the regret scaling with the number of arms K, which is not feasible in our case when K = 20.
However, in case where || @ (x)]l2 < 1,
We note that the similarity with the model selection technique in 35] is that they use model ag- gregation among M bound the prediction error ΣT (zz, 0 0.) but this does not necessarily
guarantee the risk error |00 0. 1|2. The reason is that, although model aggregation can guarantee small prediction error, it imposes no restriction on the estimator 0, which limits its ability to leverage the further benign property of designed matrix X. Instead of model aggregation, our algorithm explicitly picks the best model from the pool M, ensuring the following two properties: (1) The prediction error is small, similar to model aggregation; and (2) We can guarantee that lies in one of the subspaces of M. The second property gives us control over (0 - 0.) by ensuring it lies in at most 2 subspaces. Then, exploiting the restricted isometry property (see Definition 15) of designed matrix X, we can guarantee that with O(log M)) exploratory samples, we can bound the risk error This is crucial for eliminating polynomial dependence on M and the number of arms K.
||@ 12
Proof sketch of Lemma 12. We provide a proof sketch here and defer their full proof to Appendix B.I. Our proof borrows techniques from Gaussian model selection [21] and the compressed sensing literature [8]. There are two steps to bound the risk error as in Lemma 12:
Step 1 Bounding the prediction error.
We can bound the prediction error | X8,,
|1, using
the Gaussian model selection technique [21] as follows.
Proposition 14, Let f. = X0 For the choice of Fm as in Eqn. (3) & Eqn. (4), with probability at least 1 - 8, there exists a constant C > 1 such that
Fm f. S Co² log (M8-1).
(8)
8

---

Step 2 - Bounding the risk error from prediction error. To bound the risk error from the prediction error, we invoke the restricted isometry property on the union of subspaces of sub- Gaussian random matrix as in [8]. Note that and 0, can belong to two different subspaces of M, and 0 - 0. may not lie in any subspace of M, but in M. An important property of the design matrix X, which allows one recover 0, with the knowledge that 6, is in a subspace m MM, can be captured by the following notion of restricted isometry property (RIP):
Definition 15 (Restricted isometry property). For any matrix X, any collection of subspaces M and any 0 E m E .,, we define M-restricted isometry constant ( (X to be the smallest quantity such that
(1 - (1)0x(X))100) - |xx < (1 + x
We have the minimum number of samples required so that a random matrix satisfies RIP for given constant with high probability as Proposition 16 below. Then, Lemma 12 is followed by combining Proposition 16 and Proposition 14.
Proposition 16. Let X [mt], where xe 's are i.i.d. drawn from v, and let Ω (C (X) (log(2Mdno-11)) Then, with probability at least - ō, and for any 01, 02 in subspaces of M, has that
110 02112 s 2 (2) ( 02))1
(10)
5 Improved Regret Upper Bound with Well-Separated Partitions
We now show that by adding more structure (i.e., well-separatedness) to the setting, we can further improve the regret upper bound to O(vT). In particular, we will introduce the notion of well- separatedness in this section, and show that this notion can lead to improved (i.e., O(VT)) regret bounds.
For each partition E Pa. there is a unique equiva- lence relation on [d] corresponding p. Denote by E the equivalence relation corresponding to Next, we define well-separattenness
Algorithm 2 Exploring Model then Commit with well-separated partition
1: Input: T, v, l2
for = 1.... .t do
Assumption 17 (Well-separated partitioning). Given the true subgroup G, and the corresponding partition TG. For all (i,j) such that i "2 j. it holds
3: Independently pull arm I, according to and receive reward yt.
4: end for
that 10., -0.5) 2 for some Eo >
X + [21,.... [21,..., Nt,
IT, Y +- [W]]et])]
6: Compute in as (4).
The implication of Assumption 17 is that the projec-
for 1 l2 + to 7 do
tion of 0, to any subspace m E M not containing 0, will cause some bias in the estimation error. In particular, one can show that for any m E .M such that f, & m, holds that
Playing OFUL algorithm [1] on m.
9: end for
||0 II,,, (0.)11 2
(11)
We now show that under the Assumption 17, after the exploring phase, the algorithm returns a true fixed-point subspace m 0, with high probability.
Theorem 18. Suppose the Assumptions 5, 6. 17 hold. Let =Ω
(2"K2 log(dT) 2 (X0e
(2
Then, Algorithm
2 returns m 0, with probability at least 1/T, and its regrel is upper bounded as
Ry = (R
RRmax 2 K log(dT)) + odo odo / log (log(KoT))
(12)
min C (2)
That is. if the separating constant Eo is known in advance and Eq 2 T-1/4 1/4, then we can achieve (do VT log(K,T)) regret upper bound.

---

Remark 19. A weakness of Algorithm 2 is that without knowing that 2 T-114 is true a priori, there may be possible mis-specification error, which leads linear regret if one applies the algorithm naively. On the other hand, Algorithm can always achieve regret O(72/3) in the worst case. As such, the following question arises: Does there exist an algorithm that, without the knowledge of Eo. can achieve regret O(VT) whenever 2 T-1/4 but guarantees the worst-case regret of O( Toward answering this question, we propose simple method which has O(vT) regret whenever the separating constant is large, and enjoys worst-case regret guarantee of O(T8/4) (slightly worse than OTT2/3)). We refer the reader to Appendix C.2 for detailed description of the algorithm, its regret bound and further discussion.
Experiment
To illustrate the performance of our algorithm, we conduct simulations where the entries of O. satisfy three cases: sparsity, non-crossing partitions and non-nesting partitions. We refer readers to Appendix D.I for a more formal description of non-crossing partitions, non-nesting partitions, and why the interval partition (i.e., the partition structure equivalent to sparsity) is strict subset of both non-crossing and non-nesting partitions. Since sparsity is equivalent to strict subset of non-crossing and non-nesting partitions, we compare our Algorithm with the sparse- sparse-bandit ESTC algorithm proposed in [23] benchmark in all environments. The set of arms X' is Vdgd-1 d = 100, do = 15. The ground-truth sparse patterns, partitions and 02 are randomized before each simulation.
0.1, and
The regret of both algorithms is shown Figure 2, which indicates that our algorithm performs competitively in the sparsity case and significantly outperforms the sparse-bandit algorithm in cases of non-crossing and non-nesting partitions. Due to space limitations, we refer the reader to Appendix E for detailed description of the experiments, including how we applied the sparse-bandit algorithm in the cases of non-crossing and non-nesting partitions, and how we ran Algorithm the case of sparsity. Additionally, explain how exploited the particular structure of non-crossing and non-nesting partitions to enable efficient computation in Appendix E.
Speralty, d' 120. de 1.1
Nonecroaery Partitan, di 1C0, 11
Nun-noainng Pattitian d' 100, dy =1
RST Lanie
40300
PSTT: 9-00)
20000
200.0
70023
+200
38300
20000
5000
2000
19300
15000
20000
5005
10099
12000
23300
5000
10000
15000
20000
Figure 2: Regret of EMC (Algorithm 1) and of ESTC proposed in [23], in cases of sparsity, non- crossing partitions, and non non-nesting partitions.
7 Conclusion and Future Work
In this paper, we study symmetric linear stochastic bandits in high dimensions, where the linear reward function is invariant with respect to some hidden subgroup G & Sa- We first prove that no algorithm gain any advantage solely by knowing G < Sg. Given this, we introduce cardinality condition on the hidden subgroup G. allowing the learner to overcome the curse of dimensionality. Under this condition, we propose novel model selection algorithms that achieve regrets of ((d2 and Ö(do with an additional assumption on the well-separated partition. For future work, will explore convex relaxation techniques for efficient computation, leveraging specific structures of symmetries.
10

---

References
[1] Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, 2011.
[2] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Daline-to-confidencess conversions and application sparse stochastic bandits. In Journal of Machine Learning Research, 2012.
[3] Miguel Abreu, Luis Paulo Reis, and Nuno Lau. Addressing imperfect symmetry: novel symmetry-learinng actor-critic extension. arXiv preprint arXiv:2309.02711 2023.
[4] Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E. Schapire. Corralling a band of bandit algorithms. In Proceedings of the 2017 Conference on Learning Theory, 2016.
[5] Richard Baraniuk, Mark Davenport, Ronald Devere and Michael Wakin. A simple proof of the restricted isometry property for random matrices. Constructive Approximation, 2008.
[6] Arash Behboodi, Gabriele Cesa, and Taco Cohen. A pac-bayesian generalization bound for equivariant networks. In Advances in Neural Information Processing Systems, 2022.
[7] Lucien Birgé and Pascal Massart. Minimal penalties for gaussian model selection. Probability Theory and Related Fields, 2007.
[8] Thomas Blumensath and Mike E. Davies. Sampling theorems for signals from the union of finite-dimensional linear subspaces. IEEE Transactions on Information Theory, 55, 2009.
[9] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges, 2021.
[10] R. Bödi and K. Herr. Symmetries in linear and integer programs. arXiv preprint arXiv:0908.32. 3329, 2009.
[11] Alexandra Carpentier and Remi Munos. Bandit theory meets compressed sensing for high- dimensional stochastic linear bandit. In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, 2012.
[12] Gabriele Cesa, Leon Lang, and Maurice Weiler. A program to build e(n) equivvriaa steerable cnns. In International Conference on Learning Representations, 2022.
[13] Minshuo Chen, Yan Li, Ethan Wang, Zhuoran Yang. Zhaoran Wang, and Tuo Zhao. Pessimism meets invariance: Provably efficient offline mean-field multi-agent Advances in Neural Information Processing Systems, 2021.
[14] William Chen, Eva Deng, Rosena Du, Richard Stanley, and Catherine Yan. Crossings and nestings of matchings and partitions. Transactions of the American Mathematical Society, 2006.
[15] Nachum Dershowitz and Shmuel Zaks. Ordered trees and non-crossing partitions. Discrete Mathematics, 1986.
[16] Bryn Elesedy and Sheheryar Zaidi. Provably strict generalisation benefit for equivariant models. In International Conference on Machine Learning. 2021.
[17] Mare Finzi, Samuel Stanton, Pavel Izmailov, and Andrew Gordon Wilson. Generalizing convolutional neural networks for equivariance to lie groups on arbitrary continuous data. In International Conference on Machine Learning, 2020.
[18) Dylan Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. In Advances in Neural Information Processing Systems, 2019.
[19] Dylan Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to misspecifica- tion contextual bandits. In Advances in Neural Information Processing Systems, 2020.
[20] Avishek Ghosh, Abishek Sankararaman, and Kannan Ramchandran. Problem-commlexity adaptive model selection for stochastic linear bandits. arXiv preprint 2rXin:2000.000612220000
[21] Christophe Giraud. Introduction to High-Dimensionss Statistics. 2021.
11

---

[22] Robert Givan, Thomas Dean, and Matthew Greig. Equivalence notions and model minimization markov decision processes. Artificial Intelligence, 7 2003.
[23] Botao Hao, Tor Lattimore, and Mengdi Wang.
High-dimensional sparse linear bandits. In Advances in Neural Information Processing Systems, 2020.
[24] Kyoungseok Jang, Chicheng Zhang, and Kwang-Sung Jun. Popart: Efficient sparse regression and experimental design for optimal sparse linear bandits. In Advances in Neural Information Processing Systems, 2022.
[25] Parnian Kassraie, Aldo Pacchiano, Nicolas Emmenegger, and Andreas Krause. Anytime model selection in linear bandits. In Advances in Neural Information Processing Systems, 2023.
[26] Gi-Soo Kim and Myunghee Cho Paik. Doubly-robust lasso bandit. In Advances in Neural Information Processing Systems, 2019.
[27] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 7 2020.
[28] Tor Lattimore, Koby Crammer, and Csaba Szepesvári. Linear multi-resource allocation with semi-bandit feedback. In Advances in Neurul Information Processing Systems, 2015.
[29] Chung- Wei Lec, Qinghua Liu, Yasin Yadkor, Chi Jin, Tor Lattimore, and Csaba Szepesvári. Context-lumpable stochastic bandits. 6 2023.
[30] Chi Kwong Li and Roy Mathias. The fidski--mirsk--willdde theorem-additive and multiplica- tive versions. Numerische Mathematik, 1999.
[31] Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S. Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora. Enhanced convolutional neural tangent kernels. 11 2019.
[32] Anuj Mahajan and Theja Tulabandhula. Symmetry learning for function approximation in reinforcement learning. arXiv preprint 1rXiv: 02999, 2017.
[33] Toufik Mansour. Combinatorics of Set Partitions. 2012.
[34] Washim Uddin Mondal, Mridul Agarwal, Vaneet Aggarwal, and Satish V. Ukkusuri. On the approximation of cooperative heterogeneous multi-agent reinforcement learning (marl) using mean field control (mfc). Journal of Machine Leurning Research, 2022.
[35] Ahmadreza Moradipari, Berkay Turan, Yasin Abhasi- Yadkori, Mahnoosh Alizadeh, and Moham- mad Ghavamzadeh. Feature and parameter selection in stochastic linear bandits. In International Conference on Machine Learning, 2022.
[36] Min-hwan Oh, Garud Iyengar, and Assaf Zeevi. Sparsity-agnostie lasso bandit. In International Conference on Machine Learning, 2021.
[37] Aldo Pacchiano, Christoph Dann, Claudio Gentile, and Peter Bartlett Regret bound balancing and elimination for model selection in bandits and rl. arXiv preprint arXiv:2012.13044 2020.
[38] Aldo Pacchiano, Christoph Dann, and Claudio Gentile. Data-driven online model selection with regret guarantees. In International Conference on Artificial Intelligence and Statistics, 2024.
[39] Fabien Pesquerel, Hassan Saber, and Odalric Ambrym Maillard. Stochastic bandits with groups of similar arms. In Advances in Neural Information Processing Systems, 2021.
[40] B Ravindran and A G Barto. Approximate homomorphisms: A framework for non-exact minimization in markov decision processes. Proceedings of the Fifth International Conference on Knowledge Based Computer Systems (KBCS 04), 2004.
[41] Nam Phuong Tran and Long Tran-Thanke Invariant lipschitz bandits: A side observation approach. In Machine Learning and Knowledge Discovery in Databases: Research Track, 12 2022.
[42] Elise van der Pol, Thomas Kipf, Frans A. Oliehoek, and Max Welling. Plannable approximations to mdp homomorphisms: Equivariance under actions. In International Joint Conference on Autonomous Agents and Multiagent Systems, 2020.
12

---

[43] Elise van der Pol, Daniel E. Worrall, Herke van Hoof, Frans A. Oliehoek, and Max Welling. Mdp homomorphic networks: Group symmetries in reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
13

---

Contents of Appendix
A Impossibility Result of Learning with General Hidden Subgroups
14
The Case of Hidden Subgroups with Subexponential Size
15
B.1 Lower Bound for the Case of Hidden Subgroups with Subexponential Size
15
B.2 High Probability Prediction Error of Model Selection
17
B.3 Regret Upper bound
20
Improved Regret Bound
C.1 Improve Regret Bound with Well-Separated Partitions
C.2 Adapting Separating Constant EO
23
On Collections of Partitions with Subexponential-Size
24
D.1 Important Classes of Partitions with Suhexponentill-Size
24
D.2 Practical Examples of Partitions with Subexponential-Sizz
25
D.3 Efficient Greedy Algorithm for Specific Classes of Partitions
25
Experiment details
26
Extended Related Work
27
Additional notations
For any subset S C CRd, and matrix W e Rdxd, we write W(S) (W> x E S}.
A Impossibility Result of Learning with General Hidden Subgroups
To prove Proposition 1, we need to prove Proposition 20 and use Proposition 21.
Proposition 20. For each S Sa acting naturally on [d], the orbit of T on [d] forms unique purtition of [d]. Moreover, for each partition E Pa. there exists at least one I < Sq such that its orbit on [d] under natural action is exactly p.
Proof. The first claim is obvious by the property of orbit, that is, orbit consists of non-empty and disjoint subsets of [d], whose union is [d].
We prove the second claim. Let p nonempty and mutually disjoint. Define group follows
{p+ (per where I is the index of partition; note that P: is
r = ( p. - P: f is bijective):
(13)
clear that I; is group under function composition. Now, define the product group
r II r. RET
and the action sb P x [d] -> [d] such that
vb (U)))er, [z(x), for Pj D..
(14)
Therefore, it is clear that (f))ez is bijection from [d] onto itself, hence, I' is subgroup of Sa.
14

---

Let E = (es) be the standard basis. Given that group & partition [d] into disjoint orbits, G also partition E into & disjoint orbits corresponding to its action on Rd that is,
E
E
Let V, = Span( EE,), then, one has the following.
Proposition 21 ([10]'s Theorem 14).
Fixg (RR)
Fixg (Vi).
(15)
f=1
We now state the proof of Proposition I as corollary of Proposition 20 and Proposition 21. Proposition There a bijection H between Pa and Fsa
Proof. First, show that for each set partition of [d], there exists unique H Fs, (R*). This is straightforward due to the fact that, given a set partition P. the partition of basis (Ei)ier is unique by definition, as Vi span(E,), As result, let H Fixr(V.. by Proposition 21, H E Fs, (IR). As (Vi)ke is unique, Hf is unique.
Second, we show that for each H E Fs, ((RR), there is a unique set partitiinneequivllet relation P. Denote P as an equivalent relation under the set partition P. Suppose there are two different set partitions P, Q, there must be two set element p q such that p 2 under P, and p 2 under Q- Denote Hp, HQ as the subspaces defined by P and Q respectively. As q, there must exist point Hq such that Tp + 2q. However, Tp = Ig for all Hp. Hence, Hp cannot be the same as HQ.
Proposition 3. Assume that the action set is the unit cube {ar E Rd || S 1}, and f is invariant w.r.f. action of subgroup G S S4. such that dim(Fixg) = 2. Then, the regret of any bandit algorithm is lower bounded by Rr ((d/T).
Proof. Suppose there is a collection of model parameter θ (-8, s] for some 0. For each E θ, it is straightforward that since has two classes of indices, by Proposition and 2, there must be a subgroup G Sa such that 0 E Fixg and dim (Fixg) = 2.
Now, θ be used family of problem instances for minimax lower bound of linear bandit. By Theorem 24.1 in [27], we have that with the choice of = 1/2 one has that
exp -2 dVT.
R 2
(16)
V8
B The Case of Hidden Subgroups with Subexponential Size
B.1 Lower Bound for the Case of Hidden Subgroups with Subexponential Size
Proposition 9 (Regret lower bound). There exist symmetric linear bandit instances in which Assumption 5, 6 hold with K2 Sdo, such that, any bandit algorithm must suffer regret Ru a min (Cmin (x) dā T v dT
Proof sketch. First, we show change of variable between the sparsity and interval partition cases, including the parameter space and set of arms. Next, we demonstrate that mapping problem instances in the lower bound of sparse bandits in [23, 24] satisfies the constraints in Assumption 6. After that, the proof follows immediately by carrying out step-by-step calculations similar those in [23, 24].
15

---

First, let us define the sparse bandit instances. Let Z be the set of arm of sparse bandit problem, such that V2 2, || < Let o R be sparee parameters. Now, let define the mapping that corresponds to change of variable between and yp as follows: (1) For i E [d - 1]. 9:: 0, - 0;+1+ (2) 4p = Od- Therefore, one can write
0
0
-1 1
0
-1
0
0
6
0.
(17)
0
WER
is easy to verify that entries of 0 has equivalent classes and only if yp is sparse. Now, suppose expected reward for arm in interval-partition instance is equal expected reward for arm in sparsity instance, that is,
(or, 0) = ((WT)-*>, W = (z, (z
(18)
Therefore, to guarantee the bijection between sparsity and interval partition instance, we define the set of arm X = W (2)= ( =
We need to prove that X' satisfies Assumption Therefore, x WT 2, and X W WTZ Our job verify that, for all [-1, 1js, the projection || (V=)ll2 [V dim(m) & 2dg. Let Si...., (dim(m) be the classes according to the interval partition corresponding m, such that
/dg. for any such that
(im(m)
E
1Sal
[T (x)]1
Σ
|
S&
i= E=Eeee
(S,) )+1
(19)
Lveraage entries within class
dim(m)
Ejse 18a1
Sp
1= i=
151+1)
Since WTa 2, we have that x;
23, Vi E [d]. with 20 0 for convenience. Note that
E 1-,, E [d]. We have that
dim((m)
Essu 19,1
[mm (WT 2)11
-1
SA
18/++1)
(20)
Telescoping
dim(m)
4
8dg-
S2
Therefore, we have that, for all I E X' = W (Z), [1 (x)1l2 S 2
Moreover, we also have that Cmin (x) 2 Cmin (Z). Particularly, let us denote the exploratory distribution on Z as
p arg max Amin (Errw (22 T]) wEA(2)
p:= Ex~plzz J, Cmiu (2) == Amin (P). (21)
16

---

Define ux(z) : (((WT)=12) 2), and let U := Eewul> ( z). we have that U = W PW. Since all eigenvalue of W is 1, according to [30], we have that (PP) (U( for all E [d]. Therefore, have that Cmin (A) 2 Cmin 2
Then, using change of variable argument, the calculation of the lower bound is identical to that of [23, 24]. Therefore, can conclude that all policies must suffer regret
R mC (X) $ T VdT).
B.2 High Probability Prediction Error of Model Selection
The proof of Proposition 14 uses the following concentration.
Proposition 22 ([21)'s Theorem B.7), For some subspace S C R2 of dimension ds, with probability at least d, one has that
| o s sa 2 ())
(22)
Proposition 14. Let f. = X0.. For the choice of fm as in Equ. (3) & Eqn. (4), with probability at least 1 - 8, there exists constant C 1 such that
fm - f- 1 S Co log (M8-1)
(8)
Proof. Define E the event such that for all E M.
Us.. (n)lll S Lo dm top log 50
(23)
By Proposition 22 and union bound, & occurs with probability 1 M For the rest of the proof, we assume & occurs.
Let us denote f = fr.. By the model selection procedure (4), one has that
||Y f11 - fm.
(24)
Also, Y f. 17. has that, for some K
2 S f. fm. 1| + 2 n7, n. Sm.) + Kodd - 2(1.. - f) Koo (25)
f fz
1 Note that, Im.. (f+) f.. as f. Sm,- We have that,
First, consider the term
2
f.
fm.
=11 IIss.. (f. + +m112
2
||ʃ- -f-ll² - (IIs.. (m), f.) + I (n)
(26)
< 0 lo dm. + t 2
5o
< 20 do 40 log
5n

---

Second, consider the term (1, f. Pm.) ). We have that,
n fx Sm.) =(n - -Iss. (f+ + 11))
(n,
(27)
=(n. f. - -f.) - || (n) s
Third, we need to control the magnitude of the term 2 n (n.f-S.) term can be bounded
{z)
-Kodda. We show that this
2 2 - f.) do sa f-
f. (llg((1/))),
with probability at least 1 - Md for any constant a > 0. Denote (f.) ) be the line that is spanned
by f.. For each m E .M, let us define the subspace Sm = Sm + (f.). Define 5m C Sm as the subspace that is orthogonal to (f+), that is, one can write S. = S. ① (f+). By AM-GM inequality, for some O, we have that
2 2n1 f f.
(I (n). f.) = Va
Im (n).
_
1
(f- f.)
f f. ||:
S a |لاا (1) 1 + a -1
(28)
V + ao U + a | fz 1
where V = 0 [T (r.) (m)l and Un = 02 |1 (m) Note that, dim((f=)) 1, with
probability at least 1 og, one has that
V V 4log(6,))
(29)
Define the event & the event where the above inequality holds.
Therefore, our final task is control the quantity aU Kd Choose has that
(K + 1)/2 one
K +1
2K K
K +1
2K
al' Kdm
Unn
dm
Um
dm
+
mE.
K
Now, directly control the magnitude of Un 2K
K+1 da is difficult, m depends on 7,, and their distribution might be complicated. Instead, we will control the maximum of the above quantity Um 2K Rm dm over all m E M. Since the dimension of 5m is at most dm similar as the event &,, we define the event Eg as for all m E M, we have that
1 50
11 (m)ll2 S a dm + / 2 log
(30)
By Proposition 22 and the union bound, Eg occurs with probability least 1 M 6o. We assume that Eg occurs, then for all m E M,
Um 5
dm +
2
5n
(31)
2K
4K
1
<
dm +
log
K + 1
K -
8n
18

---

Therefore, one has that for all m E M,
K
2K
K +
2K
2 Una
dia
max
Um
dm
K +
2
mEM
K + 1
(32)
2K [K + 1)
log
K -
80
Putting things together, let 5 (2M + 16) we assure that event & E2g occurs with probability least 1 8. Combining (26), (27), (29), (32), with (25), one has that
K
f 1.112 S 20 + 2 log
2.M +
Ko²do
K
2M +1
( + 1)
2MM +
0² (K 1) + 20 (K log
log
K
(33)
Note that, the dominating term in the above equation log ( (ff , we have that, there some constant
C> O.
- f. 1 S Co log
M
(34)
Proposition 16. Let X = [xe]ee(m) where xy's are i.i.d. drawn from v, and let
Ω (C.m K2 (log(2Md,oo-11) Then, with probability at least - ō, and for any 02, O2 in subspaces of M, one has that
110 1211 s 20 20 (2)= | -82)11
(10)
Proof. Our proof strategy inspired by [8].
First, we compute the subgaussian norm for the normalised distribution along fews directions v. For any x E X, we have that
V V-1/2z,0)
V-1/222, v1/2w)
max || =1, WEM, MEM
|| ,-,, vVV M
max 11,///|1,=1, (r,w))
(35)
MEM
K2 Cuin (x)
< max meM
[+) C-1 Cmin (X) S
This means that, the distribution (V- 1/2x w) has bounded support [0, of v.
Kx Cain
for any above direction
Next, for any denote dy V1/20, note that the direction corresponding to By satisfies (35). Using Hoeffding's 's inequality for bounded random variable, there an absolute constant C₁ > such that
nej C miin (X))²²
1/2 1/222 Fis 0r) )- 16vl12 2 <l10v
Pr
< 2 2cxp
K2
(36)
1/28y 1- - -10v11 2 e e110v112
(- (-no; Ch (X)e²
Pr
XV
< 2eep
12
K2
Let 2 - LV 1/2 From Lemma 5.1 [5], we know that if the above incquality holds, then
(1 - ह, (Z) | l12) < |20v 112 < (1 + 8 (Z) 10vll2)
(37)
19

---

holds with probability more than
12
2dg
Ci (X))no (Z)
1 - 2
exp
M
5M (Z)
K²
for any Oy E (m) in subspace M. Take union bound for M subspaces, and let
2do
G
(X))6 (Z)
8 2M
exp
M
Ôπ (Z)
K
K
log(2M) do log
+ 1og((-1)
82 (2)
C (2)
85 (2)
M
Let 82 (2) 1/2. Then, Given n 0 0
K² C
(log(2M) + do - log(6-1))) for probability at
M7
(X)
least 1 8, have that
1
v
11/20
2
$
XV XV 1V-1/22
2
11
1
1
2 Cin (2²) 110112
|
n
Let = 01 02 for any 01 E m, Og E m', for any m, m' E M. We conclude the proof.
B.3 Regret Upper bound
Lemma 12. Suppose the Assumptions 5, hold. For 4 52(K2doCmi log(d/)), with
probability at least - 6, one has the estimute
00. 1.-Oaull ---0ll2-0
log log(d/8)
Cmin (X),
Proof. First, let consider Proposition 16, and recall that log( log(M) and log( are both O log (d). Therefore, for the choice of f = do (Xt log(d/8) (d/)), with probability least 8/2, one has that
Cinin (x) 00. 0,, 1,113==
2 t
X(0_ - 0.:)
(38)
Second, by Proposition 14, has that with probability at least - 8/2.
d x(O, - Bm))13 cco0ddo log (o)
(39)
for constant C1 > O.
Therefore, putting thing together, we have that with probability least 1 6, one has that
dd log (1)
0. 00-00u11, s e Cmin (X)t
(40)
for constant C2 >>
Theorem 10 (Regret upper bound). Suppose the Assumptions 5, 6 hold. With the choice of d T (log(dT)) then the regret of Algorithm I is upper bounded as f = R 3 min (X)
Rr = o 0 o c- (X)K d3 T (log(dT))+
Proof. Let define the pesudo regret as Ri ET1 (z. xr, 0.). Denote in E the subspace contains 0, - -O,, We start by simple regret decomposition follows.
20

---

31
R Σ (0,,20 F4 -21) = Σ
(0., I, rz)
(0., 2. - xz)
1=
T
< R Rmaxt1 +
Σ (0- 01, 2x - 21 +
0,, - 12
1mit+1
< Rmaxt +
E
(0. 0 -x1)
1=h+1
Bmaxt +
Σ (0. :2,, 11 - Iz))
As 0, - 0,, E m.
1=
Rmaxh
Σ
|0+ 0ng
[[ x2)1l2
+=
T
S Rmaxt1 +
Σ
2v
K
00. - 0eg 11:
Since [I]m( - x1)1l2 s 2v K2
1=
(41)
Now, we invoke Lemma 12. Let & the event in that the exploration error is bounded as in Lemma 12, then there is an absolute constant e₁ > such that,
T Σ
R & Pemax + E
2
Ox
0/1112
+ (TPr(ERRmaa
+
(42)
do log(d/o)
I Rmaxt + 01 //
(2)i T + R8
Let 1/T, and f = Rmax C #
min (x) dø T (log(dT)) $ one has that Ry = 0 R R c min (x) d3 T (log(dT)))
(43)
C Improved Regret Bound
C.1 Improve Regret Bound with Well-Separated Partitions
Theorem 18. Suppose the Assumptions 5, 6. 17 hold. Let =Ω -0(0 (22 log(dT)
Then, Algorithm
C (Xeg
2 returns mn 0. with probability at least 1 1/T, and its regrel is upper bounded as
R₁ =0
R do log(dT) odo TooooTllooKK
(12)
C2 min (x)=
Proof. Define the event E as
8= (IX - 1s (Y) 1|Y Is... (Y) 0, E m, 0, $ m
(44)
21

---

The event & is equivalent as
|| 1s (X)l < 1| IIs (V)
f. + - fm 2 v f. + 7 fm 2
(45)
f. fm + 2 17, f- Pm $ f. - fm
+ +2(n. 17, f= - Fm)
First, we upper the LHS of (45) with high probability.
[as 0. ml Il.. J. - (n)ll + (n, sls (n)) |m (n)ll 2 ||IT Sm (n)ll² 50
(46)
with probability at least - 8. The above inequality uses the union bound for all M.
Second, we lower bound the RHS of (45),
+2(1) ||,--mml12 +
Fmll2
f- -fm). with high probability.
Let 5. = S. + (f=), then 77: f- - Fm) [T (n), fx fml) Therefore, we have that, with
probability at least 1 - 8/3.
J. fm 1 11 (1), S. -Fm) 2
1 5. fm ! s. (m)
f sm
2
2
2
2
1
f+ f
4 (o2(d) (do + +
o² (log(3MM8 1))
2
1
2 f.
f
5 (o + o (lgg((300)))
(47)
as dm S dg.
Also, we have that, with probability at least 1 - -8/3
f+ fm = l1f- IT (f+) IT (n)
llf. ITs... (f.)l2
Where the inequalities holds because Is.... (f+) is the projection of f. Sm. Therefore, have that
f. fm + 2 n. f. Fm)) |f. IIs., (s+) - (o + o² (log(M (48)
Now, by choosing l2 = 12 (cm2 (2) (og(Mo-1)) by Proposition 16, we have that with probabil- ity at least - 6/3,
12
L25
|lf- ITs,, (f+) [| - Is,, (0+))
110 IT... (0-)12 2
(49)
20min (X)
4C (X)
Therefore, the RHS of (45) is lower bounded as follows
f. Fm 1| + +2 n. 2.2
fm
to
3
(log 1)))
(50)
80min (X)
Therefore, the sufficient condition for event & holds with probability least 1- 8 is that
tze (o² + o² (log( 0;
(51)
8Cmin (X))
Note that M Oddo log(d)), for holds with probability at least 6, it suffice choose
2 k22 log(dō-1)
1/ Ω
(52)
C2 min (X))3
22

---

The regret upper bound is an immediate consequence of the fact that Algorithm 2 return the true subspace m d., combined with the regret bound of OFUL the exploitation phase and 8 1/T.
C.2 Adapting to Separating Constant 8O
As stated in Theorem 18, if one knows in advance that the separating constant Eo 2 T-1/1, then using Algorithm 2 leads vT regret. The reason is that the learner can learn the true subspace m. after VT steps with no mis-specification errors. However, without knowing Eo > 7 priori, one cannot guarantee to recover the true subspace. Hence, naively using Algorithm which is not aware of potential mis-specification errors, leads to linear regret. On the other hand, using Algorithm can achieve regret 72/3 in the worst case (without the knowledge of &o 2 T-1/1). A question arises: does there exist an algorithm that, without the knowledge of Eo. can achieve regret vT whenever Eo T-141 but guarantee the worst-case regret as T
We note that the role of Eo is similar the minimum signal in sparsity, and it is somewhat surprising that the question of adapting to unknown minimum signal has not been resolved in the literature of sparse linear bandits. Towards answering the question, propose simple method using adaptation to misspecified error in linear bandit [19]. which has vT regret whenever the separating constant is large, and enjoys worst-case regret guarantee of slightly worse 73/1 regret.
The algorithm described in 4 is direct application of the algorithm proposed in [19], designed for adapting to misspecification errors in linear bandits. Particularly, the algorithm in [19] can adapt to unknown misspecification errors and achieve regret bound of Oddy + mmis 7), where émis the misspecification error. At high level, our algorithm exploring vT rounds using exploratory distribution, which ensures that the misspecification error Ciis of the chosen subspace m is at most T-1/4, Therefore, we can run multiple linear bandit algorithms using different levels of misspecification error. Particularly, base algorithm & E [K] is a linear bandit algorithm with misspecified level e = 2 Note that the base algorithm K has the same order of regret vT as well-specified model. Therefore, in exploitation phase, one can guarantee that in the case of well-separated partitions where Émis = 0, the algorithm can achieve a regret of dovT, while in the general case, the regret caused by misspecification error is most 73/4 Vdg-
collection of K = [Tog(T) base algorithms, where
Algorithm 3 Adaptive algorithm
Input T, 1/, tz.
2: for = 1,... t3 do
3: Independently pull arm xa according and receive reward yt-
4: end for
5: X + [ri,..., 2t, IT Y ()lre(()))
6: Compute m (4).
7: Let K = [log(T |, |/, = (Ex := :
2- k [K]].
8: for t 12 + T do
9: Corralling K base misspecified linear bandit algorithms SquareCB Lin+ (Ex) [19] on m.
end for
Corollary 23. Suppose the Assumptions 5, 6 hold. Then, there exists algorithm which achieves regret bound as follows:
(i) /Well-separated partitions) If 2 T-1/1, then Ry = ((doTT).
(ii) -Neparell-epparrted partitions] 1f < T14/ then Rr = Ô(do +T3
Proof sketch. Denote Emis 110, 11 (0.)ll the misspecification error. With
= Ω 100220020 log 2d ()
We can guarantee that, with probability at least - 8, if:
23

---

(i) Eo > T-4/4, then by Theorem 18, A, E m, that is, Cmis = 0;
ii E0 > T-4/ then by Lemma 12, we can bound Emis S T TT41/4
The regret of adaptive algorithm in [19] of the form Cmis /du). Let 1/T. Consider case (i) where mmis = 0, we have Ry (dovv) Consider case (ii), where 6mis = 7--7--1/ 1/4 we have R = O(do + T Vd))
The result in Corollary 23 is still sub-optimal in the worst case, as can only achieve O regret bound instead of OTT2/3). We conjecture that new techniques are required achieve order-optimal regret in both cases, and will continue to investigate this question in future works.
D On Collections of Partitions with Subexponential-Size
D.1 Important Classes of Partitions with Subexponential-Size
In this section, we discuss several important classes of partitions which satisfy Assumption 5,
Patter-avoidance partitions is arguable the most important class of studied partition [33], in which, non-crossing partition is one the most studied.
Definition 24 (Non-Crossing Partition). Let [d] admits cylic order as 1 < < ... < d, and d 1. non-crossing partition of [d] is partition such that for i, j in one block and p, in one block, then they are not arranged in the order i < < q-
Similarly, we denote NC,, NCa,,, NC as the set of all non-crossing partition of [d]. the set of all partition of [d] with & classes, and the set of all partition of [d] with at most & classes. We have the following fact ([33]' section 3.2).
1
2d
)
IWCa,.l - k
(x)
WCaal
= d d+1
(53)
which is the Catalan number and the Narayana number. Note that,
(
d d
ed
( ed
(K-1)
1 1 ed S d
2k
(54)
k
k
Therefore, non non-crossing partition satisfied the cardinality restriction as Assumption 5, that is, NCd, C Qd.
Another important class pattern-avoidence partitions is nonnesting partition [14].
Definition 25 (Non-Nesting Partition). Let [d] admits cylic order as 1 < < ... d, and 1. A non-crossing partition of [d] is partition such that for if i, j in one block and p, in one block, then they are not arranged in the order i < <p= < j.
Similarly, we denote NN a N. d,k, N. as the set of all non-crossing partition of [d], the set of all partition of [d] with & classes, and the set of all partition of [d] with at most k classes. There is bijections between class of N and NCa, non-nesting partitions also satisfy the sub-exponential constraint (Assumption 5).
One special case both non-crossing partitions and non-nesting partitions is interval partition, which has identical structure sparsity.
Definition 26 (Interval Partition). set partition of [d] an interval partition or partition of interval if its parts are interval.
We denote Ia as the collection of all interval partition of d, we have that Ia C. NCa. Pa. and Ia C NN. C Pa.
Remark 27. Ia admits a Boolean lattice of order 2d-1, making it equivalent the sparsity structure in d-1 dimensions. Specifically, consider the set of entries of parameters &p E Rd with linear order, that is, :i < 222 < < Pa. Then define the variable E Rd-1 such that 0, ((p:-1-9p3) Each interval partition on the entries of yp will determine unique sparse pattern of 0. In other words, symmetric linear bandit strictly harder than sparse bandit and inherits all the computational complexity challenges of sparse linear bandit, including the NP-hardness of computational complexity.
24

---

Inspired by the literature on sparse linear regression, where one can relax solving exact sparse linear regression by using norm-1 minimization, also known as LASSO methods, we ask whether there is a convex relaxation for the case of non-crossing partitions or anttern-vvoidance partitions in general.
D.2 Practical Examples of Partitions with Subexponential-Size
General hidden symmetries. Examples of hidden symmetry in reinforcement learning tasks can be found in robotic control [32, 31, where robot is initially designed symmetrical, but part of symmetry is destroyed by mechanical imperfection. Further examples of hidden symmetry can be also found in the literature on multi-agent reinforcement learning with a large number of agents. To avoid the curse of dimensionality, researchers often rely the assumption of the existence of homogeneous agents [13, 34j. In the extreme case where all agents are homogeneous, such as in mean-ficld games, sample complexity becomes independent of the number of agents [13]. However, in practice, agents can be clustered into different types [34], and this information may not be known in advance to the learner (here symmetry occurs between different agents from the same type).
Non-crossing partitions. Sub-exponential size naturally appears when there is a hierarchical structure on the set [d], and the partitioning needs to respect this hierarchical structure. Particularly, let T(d, do) be the set of ordered trees with (d + 1) nodes and dg internal nodes (i.e., nodes that are not the leaves). A partition that respects an ordered tree groups the children of the same node into a single equivalence class (for example, see Figure 1). It is shown in [15] that the cardinality of the set of partitions that respect ordered trees in Tcd, do) is sub-exponential. More precisely, it is O (ddddo) Furthermore, there is a natural bijection between partitions that respect ordered trees in T(d, do) and the set of non-crossing partitions.. NCa,,d [15].
Recall the subcontractor example in the introduction. Here, after the company hires subcontractors {1, 4, 6) to do the job, these subcontractors further break down the tasks into smaller subtasks and hire additional subcontractors (2,3), {5), and {7, 8,9). respectively, to execute the subtasks.
Non-nesting partitions. Besides non-crossing partitions, another sub-exponential-Sie partitions with practical relevance is non non-nesting partitions. Consider the resource allocation task where there are d upcoming tasks and do machines. The job of the designer is to allocate these tasks to each machine.
class of
Now, assume each task will appear in time t < t2 < ... < ta. but the exact time (the value of t.) is unknown to the designer. Moreover, the cost of machine l [do]. given subset of tasks Av. (ordered according to execution time), is Cs- = (mmx((A))
(Ax)
The goal of the designer minimize the maximum cost of all machines:
min max CR-
To achieve this, the designer should avoid nesting allocations (i.e., searching among non-nesting partitions). In particular, assuming that if tasks at times t, and t, are assigned to machine k. (where l < (2)), and tasks at times tp and l, are assigned to machine & (where Ip < (4), then it should not be the case that 4 < lp < bg < Lj- This is because the cost of machine would be significantly higher than that of machine k., and the cost could be reduced by swapping task l, for machine k with task I for machine k'.
D.3 Efficient Greedy Algorithm for Specific Classes of Partitions
The model selection procedure in the exploration phase of Algorithms and requires finding the best subspace in the pool m E .M with respect to least square errors. In the worst case, the algorithm needs to solve M linear regression approaches. While the exact computation of the best subspace m as in (4) an Na-hard problem in general (since contains interval partition as subclass), we argue that an greedy algorithm can find the ground- -tuthh subspace m, in ((dd)) time complexity, given sufficient large number of samples.
The pseudo code of the greedy algorithm is given in Figure 4. Given that the set of partitions Q. is equipped with a lattice structure, in which the finest partition is (1|2)... ... (d) and the coarsest partition is (1,
The algorithm starts with the finest partition a (1/2) ... (d). each iteration, the algorithm finds the finest coarsening of the current partition सt. In graph-theoretic terms, it finds all neighbors of स in
25

---

the lattice that are coarsenings of it The operator for finding the finest coarsening of î is denoted as Coarsen(f), and returns collection of the finest coarsened partitions. Next, the algorithm finds the partition that minimizes the prediction error ||Y - sT,,, (Y)ll among the current coarsening collection. At the end of each iteration, as the number of classes is reduced by one, the dimension variable is also reduced by 1. The while loop stops when the dimension equals do-
Since the algorithm only optimizes locally within the current coarsening collection, it exhibits behavior similar to a greedy algorithm. We note that for non-crossing and non-nesting partitions, the cardinality of the coarsening collection at any level of the lattice is at most d,, Therefore, assuming that creating a finest coarsening partition take ((d) operator, and solving least square takes ((nd)), the algorithms time complexity is )(
Algorithm 4 Greedily Search within Lattice
1: Input: Compact representation M, design matrix X, reward vector Y.
2: Initialise ã = (1/2|3|4...|d) dimension = d.
3: while dimension >> du do
4: Collection Coarsen(f).
5: i = arg
|| - IIsm (3)
6: A = H (m))
7: dimension dimension -
8: end while
9: 0 arg mingem || X
10: Return m, 0.
E Experiment details
We conduct simulations where the entries 0. satisfy non-crossing partition constraints. The set of arms X' Vds distribution be the uniform distribution the unit sphere. The ground-truth partition Tg and O, are randomized before each simulation.
0.1, and (d, do) {(40, 4), (80, 10), (100, 15)]. We let exploratory
To run ESTC-Lasso algorithm [23], we introduce an auxiliary sparse vector y corresponding to Oz, whose entries are defined as yp = 0.+1 0,, and Pa = 02. We apply Lasso regression for p., get the estimate c then convert back to 0 using the map that transforms sparse vector to interval-partition vector (inversion of the map we defined above).
Regarding implementing our algorithm, we use greedy Algorithm 4 as introduced in Appendix D.3, to solve the optimisation in equation (3), (4), and its complexity is (l,d)). It is shown in the simulation result (Figure 2, 3, 4), the greedy algorithm achieves small risk error and consequently leads to small regret. Code is available at: httpp:/// //g thub. com/ Coom/NamTrra WammTranKeLL/Syymeee ceteeric--iii L-in-nan---aaaee tetiiitwitttt with Hah--iddden Hidden-SSmmetryy Symmetry. git.
Partition,
30000
DMC 2ur
10300
EMC CSrO
160.2
EMC cero
10020
600
20003
11:50
4300
10050
2000
2350
10065
10rbea nourd2
7. nummerr of MAarEs
mumbbrr roundo
Figure 3: Regret of EMC (Algorithm 1) and of ESTC proposed in [23], cases of sparsity, non- crossing partitions, and non-nesting partitions, with d = 40, do = 4.
26

---

Sparsky,
37500
20000
29C-2u
Latie
30000
EMC- Cur
00003
16000
EMC-dete
23000
50000
32500
200.0
46022
10000
7500
10300
5000
5230
7-rander
T-remberath manns
T-maanaae of
Figure 4: Regret of EMC (Algorithm 1) and of ESTC proposed in [23], cases of sparsity, non- crossing partitions, and non-nesting partitions, with d = 80, dg = 10.
F Extended Related Work
Sparse linear bandits. As we will explain in Section 4.2, sparsity is equivalent to a subset symmetry structures, and thus, can be seen as special case of our setting. As such, we first review the literature of sparsity. Sparse linear bandits were first investigated in [2], where the authors achieve a regret of ((VdsT) with Ô disregarding the logarithmic factor, and s representing the sparsity level, and T is the time horizon. Without additional assumptions on the arm set and feature distribution, the lower bound for regret in the sparsity case is ((VdsT) [27]. Consequently, the contextual setting has recently gained popularity in the sparsity literature, where additional assumptions are made regarding the context distribution and set of arms. With this assumption, it can be shown that one can achieve regret of the form (TsyTT), where r is problem-dependent constant that may have a complex form and varies from paper to paper [26, 36]. Apart from the contextual assumption, to avoid polynomial dependence on T in the regret bound, assumptions are required for the set of arms [28, 11, 23]. Recently, [23] offers a unified perspective on the assumption regarding the set of arms by assuming the existence of an exploratory distribution the set of arms. With this assumption, the authors propose Explore then Commit style strategy that achieves T nearly matching the lower bound 52(s T)) in the poor data regime [24]. As the sparsity structure can be reduced to a subset of the symmetry structure, all the lower bounds for sparse problems apply to (unknown) symmetric problems.
Model selection. Our problem is also closely related model selection in linear bandits, as the learner can collect potential candidates for the unknown symmetry. Bandit model selection involves the problem where there a collection of M base algorithms (with unknown performance guarantees) and a master algorithm, aiming to perform as well as the best base algorithm. The majority of the literature assumes the black-box collection of models M base algorithms and employs a variant of online mirror descent to select the recommendations of the base agent [4, 37, 38). Due to the black-box nature, the regret guarantee bound depends on poly(M). There is a growing literature on model selection in stochastic linear bandits, where there is collection of M features, and linear bandits running with these features serve as base algorithms. By exploiting the fact that the data can be shared across all the base algorithms, the dependence of regret in terms of the number of models can be reduced to log( (M). In particular, [25] propose a method that concatenates all M features of dimension d into one feature of dimension d, and then runs a group-Lasso bandit algorithm on top of this concatenated feature space, using the Lasso estimation as a aggregation of models. Their algorithm achieves a regret bound of OTT / /Tog( M)) under the assumption that the Euclidean norm of the concatenated feature is bounded by constant. However, in our case, the Euclidean norm of concatenated feature can be large as VM, which leads VM multiplicative factor in regret. Besides, [35] uses the online aggregation oracle approach, and able to obtain regret as O( log())) where K is the number of arms. In contrast, we use different algorithmic mechanism than aggregation of models. In particular, we explicitly exploiting the structure of the model class as a collection of subspaces and invoking results from Gaussian model selection [21] and dimension reduction on the union of subspaces [8]. With this technique, we are able achieve OT (M), which is rate-optimal in the data-poor regime, has logarithmic dependence on M without strong assumptions on the norm of concatenated features, and is independent of the number of arms K. A special case of feature selection where one can achieve a very tight regret compared to the best model is the nested feature class [18, 20J. In particular, in the nested feature class where
27

---

dimensions range from {l..... .......d,, d), and dm. < d represents the realizable feature of the smallest dimension, the regret bound can be Ō( (dm. as shown in [20]. While the regret bound nearly matches the regret of the best model in the nested feature class, the assumption on nested features cannot be applied in our setting.
Symmetry in online learning. The notion of symmetry in Markov Decision Making dates back to works such as [22, 40]. Generally, the reward function and probability transition are preserved under an action of group on the state-action space. Exploiting known symmetry has been shown to help achieve better performance empirically [43, 42] or tighter regret bounds theoretically [41]. However, all these works requires knowledge of symmetry group, while setting consider unknown subgroup which may be considerably harder. Unknown symmetry on the context or state space has been studied by few authors, with the term context-lumpable bandit [29], meaning that the set of contexts can be partitioned into classes of similar contexts. It is important to note that the symmetry group acts differently on the context space and the action space, As we shall explain in detail in Section 3, while one can achieve reduction in terms of regret in the case of unknown symmetry acting on context spaces [29], this is not the case when the symmetry group acts on the action space. the partition structure of similar classes
Particularly, show that without any extra information of arms, no algorithm can achieve any reduction in terms of regret.
The work closest to ours is [39], where the authors consider the setting of K KCarmedd bandit, where the set of arms can be partitioned into groups with similar mean rewards, such that each group has at least 9 > 2 arms. With the constrained partition, the instance- deeendedd regret bounds are shown asymptotically to be of order O ((K/9) 9) log T). Comparing to [39], we study the setting of stochastic linear bandits with similar arms, in which the (unknown) symmetry and linearity structure may intertwine, making the problem more sophisticated. We also impose different constraints on the way one partitions the set of arms, which is more natural in the setting of linear bandits with infinite arms. As a result, we argue that the technique used in [39] cannot be applied in our setting. To clarify this, let us first review the algorithmic technique from [39]: The algorithm in [39] assumes there is an cquivalence among the parameters 0, and that the set of arms X' is a simplex. At each round t, given an estimation êr, the algorithm maintains a sorted list of indices in [d] that follows the ascending order of the magnitude of 0,. The algorithm then uses the sorted list (6, keEt to choose arm accordingly. The key assumption here is that, since the set of arms is a simplex, we can estimate each 0, independently. This implies that the list (0.) (0es should respect the true order of the list (0.)seja) [d] when there are sufficiently large number of samples. Unfortunately, this is typically not the case in linear bandits where X' has a more general shape. In linear bandits, there can be correlations between the estimates 0 and fg for any i.j E [d]. Hence, one should not expect that (0:))e(4) will maintain the same order as (0:)) In other words, the correlations among the estimates (0,,..., 0a) may destroy the original order in (01,--. 0a). In fact, we can only guarantee the risk error of estimation 8, i.e., ||@ 0.|| is small, but not necessarily the order of the indices in 8. Therefore, the technique used in [39] cannot be directly applied to linear bandits in its current form.
28

---

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: Our claims made in the abstract and introduction reflect the paper's 's contribu- tions 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.
is fine 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 discussed the limitations of the work in the main paper and the conclusion.
Guidelines:
The answer NA means that the paper has no 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 their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The 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 a 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-text system might not be used reliably 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 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.
29

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
We stated the assumptions in the main paper and provide the proof in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged 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 supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification:
We described our simulations and provided a link to the code available online.
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 either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
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 clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
30

---

(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 reproducibility may be tricky in some cases, in which case authors are welcome 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 possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We provided link to the code available online.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cr httiii//giidees/ddeSuubmiii sosoooooooss for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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: //npps.cc///cccc ppwpic/guudes..///.pppppppop /eeo/eeodSSbiic ssi criionPolicee for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments 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 much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
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 understand the results?
Question:
Answer: [Yes]
Justification:
We described our simulations and provided a link to the code available online.
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 provided either with the code, appendix, or as supplemental material.
31

---

7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We described our simulations and statistical significance of the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state 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 (c.g. negative етror 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: [Yes]
Justification:
We discussed the time complexity of algorithm.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://neurips.ccmm http://ppp.pppppppppcccccccceeee
Answer: [Yes]
Justification:
We have reviewed the NeurIPS Code of Ethics.
32

---

Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances 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 in 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: This paper is primarily theoretical and may have limited direct impact or implications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors impact or why the paper does not address societal impact.
NA No, they should explain why their work has no societal
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.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 cxample, 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 being used 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
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.
33

---

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 is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/dttasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to 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:
This paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember 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 as details about compensation (if any)?
Answer: [NA]
34

---

Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 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 an equivalent approval/teview based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
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.
35


Reviews:
[{"review_id": "TEKfttW1di", "reviewer": "Reviewer_qZUs", "summary": "This paper studies stochastic linear bandits with hidden symmetry, where the reward function is invariant with respect to a subgroup $\\mathcal{G}$ of coordinate permutations. The paper first presents an impossibility result, showing that solely knowing a low-dimensional symmetry structure exists does not help. However, when the collection of fixed-point subspaces of $\\mathcal{G}$ is not too large, one can use model selection algorithms to first learn the symmetry structure. The paper provides regret bounds of the algorithms, including an improved bound under an additional assumption that the equivalence classes of coordinates are well-separated.", "questions": "- In proposition 3, is the claim \"let $\\mathcal{G}$ be an unknown subgroup with $\\dim(\\mathrm{Fix}_{\\mathcal{G}}) = 2$. \n\nThen, for any algorithm, there exists $\\theta^* \\in \\mathrm{Fix}_{\\mathcal{G}}$ such that...\"?\n\n- What can be done if Assumption 5 does not hold? \n\n- Can you elaborate on the comparison with [1], especially given that the symmetry structure here is on the coordinates so there are more similarities to the \"groups of similar arms\" assumption in multi-armed bandits? Could you further compare the settings and the techniques?\n\n- In terms of presentation, I think a concrete running example in Section 2 can be very helpful.\n\n[1] F. Pesquerel, H. Saber, and O. A. Maillard. Stochastic bandits with groups of similar arms. In Advances in Neural Information Processing Systems, 2021.", "limitations": "Assumptions are properly discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The low-dimensional symmetry structure in linear bandits studied in this paper seems novel and interesting. It also generalizes the sparsity assumption that has often been considered in the literature.\n\n- The impossibility result is not surprising but still good to have.\n\n- The mathematical formulation is clean, and the connection between fixed-point subspaces and set partitions allows for a relatively simple notion of cardinality assumption for the algorithms to work.\n\n- The improved regret bound in Section 5 leads to some interesting questions about additional structure that a learner could exploit.\n\n- The technical results are clear, and the paper is well-written and easy to follow.", "weaknesses": "- The algorithms are not computationally-efficient.\n\n- The algorithms require a rather strong assumption on the size of the collection of fixed-point subspaces of $\\mathcal{G}$.\n\n- While hidden symmetry is observed in many learning tasks (e.g., control, multi-agent reinforcement learning), the paper does not provide specific real-world applications of symmetry structures within the context of linear bandits.\n\n- The paper can be much stronger with an empirical validation on at least synthetic data. In particular, it would be interesting to see how the algorithms behave on sparse linear bandits, in comparison with specialized algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Responses to  Reviewer qZUs \nWe thank the reviewer for the insightful comments. Below are our responses/clarifications to your questions:\n\n## Question 1: What can be done if Assumption 5 does not hold?\n### Response:\nIf the cardinality in Assumption 5 is not satisfied, one might need to find an alternative notion of *complexity* for a partition. \nHowever, as the literature of partitions with constraints is diverse with many different types of partitions, such as non-crossing partitions [1], non-nesting partitions [2], pattern avoidance partitions [3], partitions with distance restrictions [4], it is highly non-trivial to find unifying parameters to measure the complexity of partitions in learning tasks. \nAs the unifying measure of complexity for partitions is unclear, one may study specific types of partitions to exploit their special properties and structures, such as the literature on sparsity (i.e., interval partitions), but this approach may lead to a loss of generality.\n\n## Comment 1: Compare with [5], where symmetry appear in parameter space instead.\n\n### Response:\n\nLet us first review the algorithmic technique of [5]:  \nThe algorithm assumes there is an equivalence among the parameters $\\theta$, and that the set of arms $\\mathcal{X}$ is a simplex. At each round $t$, given an estimation $\\hat \\theta_t$, the algorithm maintains a sorted list of indices in $[d]$ that follows the ascending order of the magnitude of $\\hat \\theta_i$.\nThe algorithm then uses the sorted list of $ \\hat{\\theta}_i $ for all $i \\in d$,  to choose arm $x$ accordingly. \nThe key assumption here is that, since the set of arms $\\mathcal{X}$ is a simplex, we can estimate each $\\theta_i$ independently. This implies that the order of entries of $ \\hat{\\theta}$ , should respect the true order of the entries of $\\theta$ when there are a sufficiently large number of samples.\n\nUnfortunately, this is typically not the case in linear bandits where $\\mathcal{X}$ has a more general shape. \nIn linear bandits, there can be correlations between the estimates $\\hat \\theta_i$ and $\\hat \\theta_j$ for any $i, j \\in [d]$. Hence, one should not expect that the list of entries of  $\\hat \\theta $ will maintain the same order as that of $\\theta$. In other words, the correlations among the estimates $\\\\{\\hat \\theta_1, \\ldots, \\hat \\theta_d\\\\}$ may destroy the original order in $\\\\{\\theta_1, \\ldots, \\theta_d\\\\}$.\nIn fact, we can only guarantee the risk error of estimation $\\hat \\theta$, i.e., $\\\\| \\hat \\theta - \\theta_\\star \\\\|_2$ is small, but not necessarily the order of the indices in $\\theta$.\nTherefore, the technique used in [5] cannot be directly applied to our setting in its current form.\n\n## Comment 2: On the sub-exponential assumption, and practical examples\n### Response: \nSub-exponential size naturally appears when there is a hierarchical structure on the set $[d]$, and the partitioning needs to respect this hierarchical structure.\nParticularly, let $T(d,d_0)$ be the set of ordered trees with $(d+1)$ nodes and $d_0$ internal nodes (i.e., nodes that are not the leaves). \nA partition that respects an ordered tree groups the children of the same node into a single equivalence class.\nWe provide an example of such a partition in the PDF file (Figure 1).\nIt is shown in [6] that the cardinality of the set of partitions that respect ordered trees in $T(d,d_0)$ is sub-exponential. More precisely, it's $O(d^{d_0})$.\nFurthermore, there is a bijection between partitions that respect ordered trees in $T(d,d_0)$ and the set of non-crossing partitions $\\mathcal{NC}_{d,d_0}$ [6].\n\nDue to space limitations, we refer the Reviewer to the discussion with Reviewer Viv8 (in our response to their Comment 2 - examples for partitions) and to the attached PDF file (Figure 1) for a specific example of a linear bandit with a collection of sub-exponential partitions.\n\n## Comment 3: On the computational complexity.\n### Response:\nWe believe that to develop computationally efficient algorithms for a particular partition, we need to fully exploit its structure, similar to how existing literature has exploited the structure of sparsity.\nHowever, this sacrifices the generality of the result, especially if our aim is to establish a general condition on partitions under which one can achieve regret that scales with the dimension of the fixed-point subspace $d_0$.\nAs establishing this general condition is the primary concern of the paper, we did not focus on computational efficiency.\nWe are aware that developing efficient computational methods is important in practice, and we hope to investigate this question in the future for some important classes of partitions other than sparsity, such as non-crossing partitions.\n\nMoreover, as mentioned in Remark 4 of the paper, since the prediction error for each model $m \\in \\mathcal M$ can be computed independently, we can exploit parallel computing to reduce the algorithm's computation time.\n\n## Comment 4: Empirical validation.\n### Response:\n\nWe run the simulation, with $d = 16$, $d_0 = 2$, $\\mathcal X$ is the unit ball, with two scenarios: interval partition, and non-crossing partition. Due to the space limitations, we refer the reviewer to the discussion with Reviewer Viv8 (our response to their Comment 3) for simulation details, and the attached PDF file (Figure 2, 3) for simulation results. The simulation results show that, our algorithm achieves similar (or even smaller) regret in the case of interval partitions, and notably smaller regret in the case of non-crossing partitions compared to the sparse bandit algorithm.\n\n## References:\n\n[1] Baumeister et al. Non-crossing partitions. 2019.\n\n[2] Chen et al. Crossings and nestings of matchings and partitions. 2006.\n\n[3] B. E. Sagan. Pattern avoidance in set partitions. 2010.\n\n[4] Chu&Wei. Set partitions with restrictions. 2008.\n\n[5] Pesquerel et al. Stochastic bandits with groups of similar arms. 2021.\n\n[6] Dershowitz&Zaks. Ordered trees and non-crossing partitions. 1986.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jhbhxYqYSQ", "reviewer": "Reviewer_Viv8", "summary": "The paper explores the impact of unknown symmetry on the regret for stochastic linear bandits. Under some assumptions on the set partition induced by the unknown subgroup G, the paper develops an \"Explore-then-commit\" algorithm that attains optimal scaling of the regret in terms of the dimension d_0 of the low-dimensional space induced by the group action.", "questions": "Please see weaknesses above", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The paper describes the assumptions clearly and develops a regret bound that matches the lower bound for sparse linear bandits.\n* The paper makes a good case motivating the generality of the symmetric bandits structure by showing how it can recover sparse bandits.\n* A discussion comparing the results to those in the model aggregation literature is given.", "weaknesses": "- The writing could be made clearer in some sections. For eg, the implication $g \\cdot \\theta_* = \\theta_*$ in line 164 seems valid only under some conditions on the set $\\mathcal{X}$. Suppose $g$ only swaps the first and second components and all vectors in $\\mathcal{X}$ have the same first and second components. It would be helpful if an example is used to describe the orbit and associated partition, the fixed-point subspace, etc.\n- The implications of the assumption on $\\pi_{\\mathcal{G}}$ in line 218 and Assumption 5 could be described more clearly. Again, a short example might help.\n- Experimental evaluation of their proposed approach is missing, Even a small simulation experiment could assure reader of the applicability of the algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Responses to Reviewer Viv8\nWe thank the reviewer for the insightful comments. Below are our responses/clarifications to your questions:\n\n## Comment 1: On the condition of $\\mathcal X$ so that $\\theta_\\star = g\\cdot \\theta_\\star$.\n\n### Response:\n\nWe do not need to impose any condition on $\\mathcal{X}$ for $\\theta_\\star = g\\cdot \\theta_\\star$ to hold. \nIn particular, we only require $f(g\\cdot x) = f(x)$, but we do not require that the orbit under the action of $\\mathcal{G}$ stays in $\\mathcal X$, that is, we do not require, $g \\cdot x \\in \\mathcal{X}$, for all $g \\in \\mathcal{G}$. \nTherefore, the condition $\\theta_\\star = g \\cdot \\theta_\\star$ holds regardless of the shape of $\\mathcal{X}$.\n\n\n## Comment 2: On illustrative examples of partitions.\n### Response:\nSub-exponential size naturally appears when there is a hierarchical structure on the set $[d]$, and the partitioning needs to respect this hierarchical structure.\nParticularly, let $T(d,d_0)$ be the set of ordered trees with $(d+1)$ nodes and $d_0$ internal nodes (i.e., nodes that are not the leaves). \nA partition that respects an ordered tree groups the children of the same node into a single equivalence class.\nWe provide an example of such a partition in the PDF file (Figure 1).\nIt is shown in [1] that the cardinality of the set of partitions that respect ordered trees in $T(d,d_0)$ is sub-exponential. More precisely, it's $O(d^{d_0})$.\nFurthermore, there is a bijection between partitions that respect ordered trees in $T(d,d_0)$ and the set of non-crossing partitions $\\mathcal{NC}_{d,d_0}$ [1].\n\n**A linear bandit example**: To further illustrate the occurrence of such symmetry in a linear bandit problem, consider the following example:\nSuppose there are $d$ workers, and each worker $i$ can put $x_i \\in [0,1]$ level of effort into the task. \nHence, $x = [x_i]_{i\\in [d]} \\in \\mathbb{R}^d$ is a vector that represents the effort of all workers. \nThe performance of the whole team is measured by\n$$\nf(x) = \\left <x,\\theta\\right>,\n$$\n\nwhere $\\theta \\in \\mathbb{R}^d$, and each entry $\\theta_i > 0$ represents the significance of worker $i$ to the success of the whole project. \nIn other words, a higher $\\theta_i$ implies that $x_i$ has more impact on the success of the project.\n\nNow, a new manager, who does not know $\\theta$, employs a bandit algorithm to optimize the performance $f$.\nWhile she does not know $\\theta$, she has prior knowledge that the skill levels of each worker in $[d]$ are hierarchical, meaning the significance of workers to the task can be represented as an ordered tree.\nThis is expected in practice, as workers may come from different skill sets (e.g., developing, maintenance, testing) and varying skill levels (from senior to junior).\nWe refer the reviewer to the PDF file (Figure 1) for an illustration of such a partition with respect to the ordered tree.\nSuppose she knows that there are at most $d_0$ equivalence classes in the partition.\nIn that case, the number of partitions that respect the tree structures (i.e., can only group children of the same node into one equivalence class) must be at most $O(d^{d_0})$, due to the fact mentioned earlier.\n\n## Comment 3: Empirical Validation.\n### Response:\n\nWe run the simulation, with $d = 16$, $d_0 = 2$, $\\mathcal X$ is the unit ball, with two scenarios:\n\n**Interval partition (i.e., sparse linear bandits)**: \n\nWe first run our algorithm with the following $\\theta$ whose entries satisfy interval partition constraints (i.e., it represents a sparse linear bandit setting):\n$$\n\\theta_\\star = [1,1,2,2...,2]\n$$\nEquivalently, we can introduce a sparse vector $\\varphi$ corresponding to $\\theta_\\star$, defined as entries defined as $\\varphi_i = \\theta_{i+1} - \\theta_i$, and $\\varphi_d = \\theta_d$. We have that $\\varphi_\\star = [0,1,0,...,0,2]$, which is $2$-sparse vector. We apply Lasso regression for $\\varphi_\\star$, get the estimate $\\hat \\varphi$, then convert back to $\\hat \\theta$ using the map that transforms sparse vector to interval-partition vector (inversion of the map we defined above). Then, we compare the regret of our algorithm with that of state-of-the-art sparse linear bandit algorithm introduced in [2]. \nWe show the regret bound of both algorithms in the attached PDF (Figure 2).   \nIt can be seen that our algorithm achieves similar regret (or even smaller) compared to the sparse bandit algorithm. \n\n**Non-crossing partition**:\n \nNow we run our algorithm with an $\\theta$ whose entries satisfy non-crossing partition constraints but not interval partition constraints.\n$$\\theta_\\star = [1,1,2,2,2,1,1...,1].$$\nWe use the same map to convert $\\theta_\\star$ to sparse vector $\\varphi_\\star$, run Lasso to get estimation $\\hat \\varphi$ and then convert back to get estimation $\\hat \\theta$. Then, we compare the regret of our algorithm with that of [2].\nWe show the regret bound of both algorithms in the attached PDF (Figure 3). \nWe can see from the plot, the regret of our algorithm is notably smaller than that of [2]. \nIt indicates that our algorithm performs better than Lasso-based algorithms (which is designed only for interval partition) in the general case of non-crossing partition.\n\n## References: \n[1] Dershowitz&Zaks. Ordered trees and non-crossing partitions. 1986.\n\n[2] Hao et al. High-dimensional sparse linear bandits. 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hju2ZGqX2w", "reviewer": "Reviewer_WDJx", "summary": "The paper studies high-dimensional linear bandits that are invariant w.r.t. an *unknown* subgroup of coordinate permutations. The authors first show through a lower bound that further information about the structure of the hidden subgroup is required to achieve a dimension-independent regret bound. They then propose a subexponential cardinality constraint on the hidden subgroup, which is sufficient to avoid the dimension dependency. They specifically propose *Explore-Models-then-Commit*, which successfully avoids the worst-case dimension-dependency under certain conditions.", "questions": "- The paper states that as sparsity is equivalent to interval partitions, the lower bound of Hao et al. (2020) also trivially applies. Then, is this lower bound tight for other combinatorial structures with similar subexponential cardinality constraints, e.g., non-crossing partition?\n- In sparse linear bandits, there is always an assumption about the context distribution or the arm set (e.g., compatibility condition, restricted eigenvalue, etc.). Can these assumptions be interpreted as part of the paper's proposed group-theoretic framework as well?\n- (minor) Would the principles here be extendable to information-directed sampling [3]?\n\n\n[2] https://proceedings.neurips.cc/paper/2020/hash/7a006957be65e608e863301eb98e1808-Abstract.html\n\n[3] https://openreview.net/forum?id=syIj5ggwCYJ", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Well-written\n- Clear motivation and a novel problem-setting of importance\n- Solid motivation for subexponential cardinality assumption on the hidden subgroup, as well as interesting combinatorial concepts intertwined throughout the paper\n- First good regret bounds in the case of hidden symmetry", "weaknesses": "- The only symmetry somewhat intuitive to me is the sparsity, equivalent to interval partitions. Despite the Introduction stating the importance of symmetry, it is unclear whether there is practically meaningful coordinate symmetry beyond sparsity.\n(Of course, theoretically, I appreciate the results here.)\n\n- No experimental results. Especially as the authors have stated that Algorithm 1 can be \"parallelised using tools such as Ray\", I was expecting at least some toy experiments (one showing the efficacy of learning the hidden symmetry and scaling of the algorithm as the number of models $M$ increase)\n\n- The algorithm is explore-then-commit style, which requires the horizon length $T$ in advance and inherits its suboptimality [1].\n\n\n\n[1] https://papers.nips.cc/paper_files/paper/2016/hash/ef575e8837d065a1683c022d2077d342-Abstract.html", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer WDJx\nWe thank the reviewer for the insightful comments. Below are our responses/clarifications to your questions:\n## Comment 1: Practical motivations \n### Response: \nSub-exponential size naturally appears when there is a hierarchical structure on the set $[d]$, and the partitioning needs to respect this hierarchical structure.\nParticularly, let $T(d,d_0)$ be the set of ordered trees with $(d+1)$ nodes and $d_0$ internal nodes (i.e., nodes that are not the leaves). \nA partition that respects an ordered tree groups the children of the same node into a single equivalence class.\nWe provide an example of such a partition in the PDF file (Figure 1).\nIt is shown in [1] that the cardinality of the set of partitions that respect ordered trees in $T(d,d_0)$ is sub-exponential. More precisely, it's $O(d^{d_0})$.\nFurthermore, there is a bijection between partitions that respect ordered trees in $T(d,d_0)$ and the set of non-crossing partitions $\\mathcal{NC}_{d,d_0}$ [1].\n\n**A linear bandit example**: To further illustrate the occurrence of such symmetry in a linear bandit problem, consider the following example:\nSuppose there are $d$ workers, and each worker $i$ can put $x_i \\in [0,1]$ level of effort into the task. \nHence, $x = [x_i]_{i\\in [d]} \\in \\mathbb{R}^d$ is a vector that represents the effort of all workers. \nThe performance of the whole team is measured by\n$$\nf(x) = \\left <x,\\theta\\right>,\n$$\n\nwhere $\\theta \\in \\mathbb{R}^d$, and each entry $\\theta_i > 0$ represents the significance of worker $i$ to the success of the whole project. \nIn other words, a higher $\\theta_i$ implies that $x_i$ has more impact on the success of the project.\n\nNow, a new manager, who does not know $\\theta$, employs a bandit algorithm to optimize the performance $f$.\nWhile she does not know $\\theta$, she has prior knowledge that the skill levels of each worker in $[d]$ are hierarchical, meaning the significance of workers to the task can be represented as an ordered tree.\nThis is expected in practice, as workers may come from different skill sets (e.g., developing, maintenance, testing) and varying skill levels (from senior to junior).\nWe refer the reviewer to the PDF file (Figure 1) for an illustration of such a partition with respect to the ordered tree.\nSuppose she knows that there are at most $d_0$ equivalence classes in the partition.\nIn that case, the number of partitions that respect the tree structures (i.e., can only group children of the same node into one equivalence class) must be at most $O(d^{d_0})$, due to the fact mentioned earlier.\n\n\n## Question 1: Is this lower bound tight for other combinatorial structures with similar subexponential cardinality constraints, e.g., non-crossing partition?\n\n### Response:\nThe lower bound derived from the sparsity case [2] applies to any class of partitions that includes interval partitions, such as non-crossing partitions [3] and non-nesting partitions [4], and thus is tight in these settings. \nHowever, this lower bound does not hold for smaller classes that do not contain a structure equivalent to interval partitions. It is still unknown what a tight lower bound would be in this case, and thus, remains as future work.\n\n## Question 2: Can assumptions such as compatibility condition, restricted eigenvalue, be interpreted as part of the paper's proposed group-theoretic framework as well?\n\n### Response: \nWe note that many conditions, such as the compatibility condition and restricted eigenvalue condition, are carefully tailored to exploit specific structures of sparsity (e.g., interval partitions) [5]. \nTherefore, we believe that developing such conditions for symmetric bandits requires exploiting a specific combinatorial structure, such as non-crossing partitions. \nAlthough this is beyond the scope of our paper, as we study a wide class of partitions, it is indeed an interesting question that we hope to investigate in future work.\n\n## Question 3: Would the principles here be extendable to information-directed sampling?\n\n### Response:\nExtending our framework to information-directed sampling is indeed a very interesting and challenging problem.\nSince bounding the information ratio as in [6] requires strongly exploiting the particular structure of sparsity, we conjecture that studying specific partitions to fully exploit their combinatorial structures is necessary to derive the information ratio bound. \nThis remains an open question, which we leave for future work.\n\n## Comment 2: Empirical validation.\n### Response:\n\nWe run the simulation, with $d = 16$, $d_0 = 2$, $\\mathcal X$ is the unit ball, with two scenarios: interval partition, and non-crossing partition. Due to the space constraints, we refer the reviewer to the discussion with Reviewer Viv8 (our response to their Comment 3: Empirical validation) for simulation details, and the attached PDF file (Figure 2, 3) for simulation results. The simulation results show that, our algorithm achieves similar (or even smaller) regret in the case of interval partitions, and notably smaller regret in the case of non-crossing partitions compared to the sparse bandit algorithm.\n\n## References:\n[1] Dershowitz&Zaks. Ordered trees and non-crossing partitions. 1986.\n\n[2] Hao et al. High-dimensional sparse linear bandits. 2020.\n\n[3] Baumeister et al. Non-crossing partitions. 2019.\n\n[4] Chen et al. Crossings and nestings of matchings and partitions. 2006.\n\n[5] S. A. V. de Geer and P. Bühlmann. On the conditions used to prove oracle results for the lasso. 2009.\n\n[6] Hao et al. Information directed sampling for sparse linear bandits. 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "q8DImtQezq", "reviewer": "Reviewer_qJvB", "summary": "The authors study the problem of symmetric linear bandits with hidden symmetry (where the expected reward is a linear function of the selected arm, and is invariant under a hidden symmetry group). They show that, with no additional information, the minimax regret cannot be improved. When the partition corresponding to the hidden symmetry group is known to belong to a given set of a sub-exponential number of partitions, the authors provide an algorithm that that achieves a regret of $\\tilde{O}(d_0^{1/3} T^{2/3})$. Under the assumption that the models are well separated, this regret guarantee is improved to $\\tilde{O}(d_0 \\sqrt{T})$.", "questions": "See weaknesses. At a high level:\n1. Adaptivity: the algorithm requires as input the set $\\mathcal{Q}_{d,\\le d_0}$ , and it is not clear how to obtain this in practice.  Additionally, it appears that the key regret improvement is the scaling with the log of the cardinality of this set, instead of with $d$. Is there a way to make these assumptions less restrictive, adapt to the ``true'' complexity of the partition, or to estimate this set in practice?\n2. Implementability: the algorithm as written does not seem to be implementable. Can the authors either provide an implementation (comparing their results with existing algorithms for sparse linear bandits), or suggest how this could be done in practice?\n3. Practical motivation: is there a motivating example (not sparsity) where the arms are high dimensional, the symmetry is unknown, and the partition is known to belong to a set of sub-exponential size?", "limitations": "The key limitations of this method, that have not been sufficiently discussed, are its required knowledge of $\\mathcal{Q}_{d,\\le d_0}$, and its computational intractability, both of which appear to be severe practical limitations.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors generalize the study of sparse linear bandits to high-dimensional symmetric linear bandits, where the symmetry is unknown and must be learned. The authors show that 1) no algorithm can benefit solely from knowing that there exists some subgroup under which the expected reward is invariant, 2) that a regret of $\\tilde{O}(d_0^{1/3} T^{2/3})$ can be achieved when the partition is known to belong to a set of sub-exponential size, and 3) that a regret of $\\tilde{O}(d_0 \\sqrt{T})$ can be achieved when the models are well separated. For the well separated case, they note that the initialization phase length $t_2$ depends on the separation $\\epsilon_0$, and question how to adapt to this parameter that will be unknown in practice.", "weaknesses": "- Adaptivity: the algorithm requires as input the set $\\mathcal{Q}_{d,\\le d_0}$ (currently not shown as in input). Additionally, the algorithm / regret do not appear to adapt to the complexity of the problem instance, but rather depend on the size of this input set. The manuscript should be revised to clarify (in the algorithm) that this is needed as input.\n- The algorithm does not appear to be implementable. The minimization step in equation 5 is over $\\mathcal{M}$, which is of exponential size ($d^{d_0}$). In the high dimensional regime of interest, this is infeasible without additional structural assumptions. The authors touch on this at the very end of the paper (line 402: \"for future work, we will explore convex relaxation techniques for efficient computation\"), but do not provide any concrete suggestions for how this could be done.\n- Practical motivation: the authors do not provide any concrete examples of where this problem arises, and how the input set $\\mathcal{Q}_{d,\\le d_0}$ could be obtained in practice. The paper should be self contained and self-motivated (e.g. Line 20, referencing [24] alone is insufficient). The illustrative example of an ant robot does not seem very related to the problem at hand, as there are at most 4 symmetries. The authors briefly discuss possible hidden symmetries in Appendix D, but don't provide examples where we should expect to see these symmetries (anything besides sparsity, for which there already exist specialized methods).\n- Clarity: the paper is quite difficult to read, and should be revised for clarity. I've listed some typos below, but thorough proofreading is needed.\n\n\nWriting typos:\n- Line 9: hidden symmetry\n- Line 16: \"Stochastic bandit is\" incomplete sentence\n- Line 26: \"fo\"\n- Line 38: \"most of studies\"\n- Line 81: \"the set of arm is exploratory\". Also, exploratory is undefined (reused in line 98).\n- Line 100: data-poor regime is undefined\n- Line 112: \"And able to obtain regret\"\n- Line 114: \"That are different to aggregation\"\n- Line 120: \"Making\" shouldn't be capitalized\n- Line 124: missing \"the\"\n- Line 142: \"*In* each round\"\n- Line 148: in term*s* of regret\n- Line 179: grammar, missing \"to\" and \"as\"->\"be\"\n- Line 204: in term*s* of regret\n- Line 206: \"the\" missing before \"regret\"\n- Line 221: \"are\"->\"is\", unnecessary \"the\"\n- Line 222: partition*s*\n- Line 320: \"designed\"->\"the design\"\n- general comment: \"the assumptions\" -> \"assumptions\"\n\nMath typos / comments:\n- Line 144: Is $\\eta_t$ supposed to be a 0 mean $\\sigma$-sub-Gaussian random variable?\n- Line 144: Clearer to write $f(x_t) = \\langle x_t, \\theta_{\\star}\\rangle$\n  - Equations 1 and 2: $\\phi$ and $\\hat{\\phi}$ perform the same operation on $\\mathbb{R}^d$, so it is unclear why they are separately defined for operating on $x$ and on $\\theta$. Also, $\\hat{\\phi}$ is confusing notation to use, as this is not an estimator of $\\phi$.\n- Line 163: missing $\\forall g \\in \\mathcal{G}$\n- Line 188: should explicitly define dim before usage\n- Prop 3: some intuitive explanation / proof sketch would be helpful.\n- Line 234: \"data\"->\"actions\"\n- Algorithms 1 and 2 critically require as input $\\mathcal{Q}_{d,\\le d_0}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Responses to Reviewer qJvB\n\n## Question: Practical motivation on sub-exponential partitions\n### Response: \nSub-exponential size naturally appears when there is a hierarchical structure on the set $[d]$, and the partitioning needs to respect this hierarchical structure.\nParticularly, let $T(d,d_0)$ be the set of ordered trees with $(d+1)$ nodes and $d_0$ internal nodes (i.e., nodes that are not the leaves). \nA partition that respects an ordered tree groups the children of the same node into a single equivalence class.\nWe provide an example of such a partition in the PDF file (Figure 1).\nIt is shown in [1] that the cardinality of the set of partitions that respect ordered trees in $T(d,d_0)$ is sub-exponential. More precisely, it's $O(d^{d_0})$.\nFurthermore, there is a bijection between partitions that respect ordered trees in $T(d,d_0)$ and the set of non-crossing partitions $\\mathcal{NC}_{d,d_0}$ [1].\n\n**A linear bandit example**: To further illustrate the occurrence of such symmetry in a linear bandit problem, consider the following example:\nSuppose there are $d$ workers, and each worker $i$ can put $x_i \\in [0,1]$ level of effort into the task. \nHence, $x = [x_i]_{i\\in [d]} \\in \\mathbb{R}^d$ is a vector that represents the effort of all workers. \nThe performance of the whole team is measured by\n$$\nf(x) = \\left <x,\\theta\\right>,\n$$\n\nwhere $\\theta \\in \\mathbb{R}^d$, and each entry $\\theta_i > 0$ represents the significance of worker $i$ to the success of the whole project. \nIn other words, a higher $\\theta_i$ implies that $x_i$ has more impact on the success of the project.\n\nNow, a new manager, who does not know $\\theta$, employs a bandit algorithm to optimize the performance $f$.\nWhile she does not know $\\theta$, she has prior knowledge that the skill levels of each worker in $[d]$ are hierarchical, meaning the significance of workers to the task can be represented as an ordered tree.\nThis is expected in practice, as workers may come from different skill sets (e.g., developing, maintenance, testing) and varying skill levels (from senior to junior).\nWe refer the reviewer to the PDF file (Figure 1) for an illustration of such a partition with respect to the ordered tree.\nSuppose she knows that there are at most $d_0$ equivalence classes in the partition.\nIn that case, the number of partitions that respect the tree structures (i.e., can only group children of the same node into one equivalence class) must be at most $O(d^{d_0})$, due to the fact mentioned earlier.\n\n ## Question: adapt to the true complexity of the partition instead of using the cardinality, or to estimate this collection of partition in practice?\n\n### Response:\nWe thank the reviewer for the interesting suggestion.\nHowever, as the literature of partitions with constraints is diverse with many different types of partitions, such as noncrossing partitions [2], non-nesting partitions [3], pattern avoidance partitions [4], partitions with distance restrictions [5], it is highly non-trivial to find unifying parameters to measure the hardness of partitions in learning tasks. \nThe question of finding the right measure of complexity for partitions as well as adapting to this complexity hardness is challenging, hence we leave it to future work. \nFor the current paper, as the unifying measure of complexity hardness for partitions is still unclear, we have decided use the cardinality of the set as a natural measure of complexity, which is a reasonable choice.\n\nIn particular, the complexity of partitions with an extremely rich structures, can also be measured by cardinality: \nTake an interval partition, for example. \nAlthough its lattice structure is rich, its complexity relevant to the learning task is still $d_0 \\log(d)$, which is the same as $\\log(|\\mathcal{Q}_{d,\\leq d_0}|)$. \nTherefore, we argue that cardinality is useful for learning with partitions, including those with rich structure.\n\n## Comment: Computational limitation. \n### Response:\nWe believe that to develop computationally efficient algorithms for a particular partition, we need to fully exploit its structure, similar to how existing literature has exploited the structure of sparsity.\nHowever, this sacrifices the generality of the result, especially if our aim is to establish a general condition on partitions under which one can achieve regret that scales with the dimension of the fixed-point subspace $d_0$.\nAs establishing this general condition is the primary concern of the paper, we did not focus on computational efficiency.\nWe are aware that developing efficient computational methods is important in practice, and we hope to investigate this question in the future for some important classes of partitions other than sparsity, such as non-crossing partitions.\n\nMoreover, as mentioned in Remark 4 of the paper, since the prediction error for each model $m \\in \\mathcal M$ can be computed independently, we can exploit parallel computing to reduce the algorithm's computation time.\n\n## Comment: Empirical validation.\n### Response:\n\nWe run the simulation, with $d = 16$, $d_0 = 2$, $\\mathcal X$ is the unit ball, with two scenarios: interval partition, and non-crossing partition. Due to the space constraints, we refer the reviewer to the discussion with Reviewer Viv8 (our response to Comment 3) for simulation details, and the attached PDF file (Figures 2 & 3) for simulation results. The simulation results show that, our algorithm achieves similar (or even smaller) regret in the case of interval partitions, and notably smaller regret in the case of non-crossing partitions compared to the sparse bandit algorithm.\n\n## References:\n[1] Dershowitz&Zaks. Ordered trees and non-crossing partitions. 1986.\n\n[2] Baumeister et al. Non-crossing partitions. 2019.\n\n[3] Chen et al. Crossings and nestings of matchings and partitions. 2006.\n\n[4] B. E. Sagan. Pattern avoidance in set partitions. 2010.\n\n[5] Chu&Wei. Set partitions with restrictions. 2008.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DzbmfQKZy3", "reviewer": "Reviewer_ZVeC", "summary": "The paper introduces and analyzes the problem of symmetric linear bandits with hidden symmetry. The authors study high-dimensional linear bandits where the reward function is invariant under certain unknown group actions on the set of arms. The key contributions are:\n\n- An impossibility result showing that no algorithm can benefit solely from knowing that the symmetry group is a subgroup of permutation matrices, necessitating further structural assumptions.\n- Establishment of a cardinality condition on the class of symmetric linear bandits with hidden symmetry, under which the learner can overcome the curse of dimensionality.\n- Introduction of a new algorithm called EMC (Explore Models then Commit) that achieves a regret bound of O(d_0^(1/3) * T^(2/3) * log(d)), where d is the ambient dimension and d_0 is the dimension of the true low-dimensional subspace (d_0 << d).\n- An improved regret bound of O(d_0 * sqrt(T) * log(d)) under an additional assumption of well-separated models.\n- Discussion of an open problem regarding adaptive algorithms that can achieve optimal regret in both well-separated and general cases.\n\nThe paper provides theoretical analysis and proofs for the proposed algorithms and bounds. The authors position their work in the context of existing literature on sparse linear bandits and model selection, highlighting the novelty of their approach in leveraging symmetry for efficient exploration in high-dimensional linear bandits.\n\nThis paper is primarily theoretical, focusing on the mathematical formulation of the problem, algorithm design, and regret analysis. It does not include experimental results.", "questions": "Empirical Validation:\n   Could you provide any empirical results, even on synthetic data, to illustrate the performance of the EMC algorithm? How does it compare practically to existing methods for sparse linear bandits?\n\nPractical Implications of Assumptions:\n   Could you elaborate on real-world scenarios where Assumption 5 (sub-exponential number of partitions) and Assumption 16 (well-separated partitioning) are likely to hold or be violated?\n\nIntuitive Explanations for Key Concepts:\n  The connection between interval partitions and sparsity, as well as the concept of hidden symmetry, are intriguing but complex. Could you provide more intuitive explanations or concrete examples to illustrate these key ideas, particularly for readers less familiar with group theory or symmetry concepts in bandits?", "limitations": "The authors have adequately addressed the limitations of their work, particularly by acknowledging open problems and discussing constraints of their assumptions. While they could expand on practical implementation challenges and potential societal impacts, their upfront approach to discussing limitations is commendable. A brief section explicitly addressing broader implications would further strengthen the paper, but overall, the authors have done a good job in addressing limitations within the context of their theoretical work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. Originality:\n   - Introduces a novel problem formulation of symmetric linear bandits with hidden symmetry, extending and generalizing the well-studied sparse linear bandit setting.\n   - Creatively combines ideas from group theory, model selection, and bandit algorithms to address this new problem.\n   - The proposed EMC algorithm represents an innovative approach to leveraging hidden symmetry in high-dimensional bandits.\n\n2. Quality:\n   - The technical analysis is rigorous and thorough, with well-structured proofs for all major claims.\n   - Provides a comprehensive theoretical framework, including an impossibility result, regret bounds, and algorithm analysis.\n   - Builds upon and extends existing results in a mathematically sound manner.\n\n3. Clarity:\n   - The problem motivation and significance are clearly articulated.\n   - The paper is well-structured, with a logical flow from problem formulation to theoretical results.\n   - Technical concepts are generally well-explained, with appropriate use of mathematical notation.\n   - Some complex concepts, particularly around the equivalence between sparsity and interval partitions, could benefit from more intuitive explanations or concrete examples for broader accessibility.\n\n4. Significance:\n   - Addresses an important gap in the literature by considering hidden symmetry in high-dimensional linear bandits.\n   - Provides new insights into the role of symmetry in sequential decision-making, with potential broad implications for reinforcement learning and online optimization.\n   - Establishes connections between symmetry structures and sparsity, potentially opening new avenues for efficient exploration in high-dimensional spaces.\n   - The proposed algorithms and bounds represent significant progress in overcoming the curse of dimensionality in certain bandit settings.", "weaknesses": "1. Limited empirical validation:\n   - The paper appears to be primarily theoretical, with no mention of experimental results or simulations to validate the proposed algorithms.\n   - Including empirical studies, even on synthetic datasets, would strengthen the practical relevance of the theoretical results.\n   - Comparison with existing methods in terms of computational efficiency and performance could provide valuable insights.\n\n2. Complexity of concepts:\n   - Some key concepts, such as the equivalence between sparsity and interval partitions, are not explained intuitively enough for a broader audience.\n   - Additional examples or visual representations could make these complex ideas more accessible.\n\n3. Practical applicability:\n   - The paper lacks a detailed discussion on how the proposed algorithms could be implemented in real-world scenarios.\n\n4. Computational complexity:\n   - There's limited discussion on the computational complexity of the proposed algorithms, particularly for the EMC algorithm.\n   - Understanding the trade-offs between theoretical performance and computational requirements is crucial for practical implementation.\n\n5. Assumptions and limitations:\n   - While the paper acknowledges some limitations, a more comprehensive discussion of the assumptions' implications and potential violations in real-world scenarios would be beneficial.\n\n6. Comparison with related approaches:\n   - While the paper discusses how it differs from some existing methods, a more comprehensive comparison with other approaches to high-dimensional bandits or symmetry exploitation could provide better context.\n\nThese weaknesses are not meant to diminish the paper's overall contribution but rather to identify areas where the work could be further strengthened or extended in future research.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Responses to Reviewer ZVeC\nWe thank the reviewer for the insightful comments. Below are our responses/clarifications to your questions:\n\n## Question 1: Practical Implications of Assumptions 5 and 16:\n\n### Response:\n**Assumption 5: sub-exponential partitions.**\nSub-exponential size naturally appears when there is a hierarchical structure on the set $[d]$, and the partitioning needs to respect this hierarchical structure.\nParticularly, let $T(d,d_0)$ be the set of ordered trees with $(d+1)$ nodes and $d_0$ internal nodes (i.e., nodes that are not the leaves). \nA partition that respects an ordered tree groups the children of the same node into a single equivalence class.\nWe provide an example of such a partition in the PDF file (Figure 1).\nIt is shown in [1] that the cardinality of the set of partitions that respect ordered trees in $T(d,d_0)$ is sub-exponential. More precisely, it's $O(d^{d_0})$.\nFurthermore, there is a bijection between partitions that respect ordered trees in $T(d,d_0)$ and the set of non-crossing partitions $\\mathcal{NC}_{d,d_0}$ [1].\n\n**A linear bandit example**: To further illustrate the occurrence of such symmetry in a linear bandit problem, consider the following example:\nSuppose there are $d$ workers, and each worker $i$ can put $x_i \\in [0,1]$ level of effort into the task. \nHence, $x = [x_i]_{i\\in [d]} \\in \\mathbb{R}^d$ is a vector that represents the effort of all workers. \nThe performance of the whole team is measured by\n$$\nf(x) = \\left <x,\\theta\\right>,\n$$\n\nwhere $\\theta \\in \\mathbb{R}^d$, and each entry $\\theta_i > 0$ represents the significance of worker $i$ to the success of the whole project. \nIn other words, a higher $\\theta_i$ implies that $x_i$ has more impact on the success of the project.\n\nNow, a new manager, who does not know $\\theta$, employs a bandit algorithm to optimize the performance $f$.\nWhile she does not know $\\theta$, she has prior knowledge that the skill levels of each worker in $[d]$ are hierarchical, meaning the significance of workers to the task can be represented as an ordered tree.\nThis is expected in practice, as workers may come from different skill sets (e.g., developing, maintenance, testing) and varying skill levels (from senior to junior).\nWe refer the reviewer to the PDF file (Figure 1) for an illustration of such a partition with respect to the ordered tree.\nSuppose she knows that there are at most $d_0$ equivalence classes in the partition.\nIn that case, the number of partitions that respect the tree structures (i.e., can only group children of the same node into one equivalence class) must be at most $O(d^{d_0})$, due to the fact mentioned earlier.\n\n**Assumption 16: well-separated partitions.**\nFor Assumption 16 to hold, there must be a significant differences among the classes in the partition. Let consider our incentivising workers example. \nThe differences among classes occur among classes occur, for instance, when each group consists of specialists who excel in very specific skills, making the differences among the groups noticeable. As such, one can easily distinguish individuals in different groups, which is essentially the notion of a well-separated partition.\n\n## Question 2: Intuitive Explanation for Key Concepts\n\n### Response:\nTo illustrate the equivalence between interval partitions and sparsity, let us consider the following example. \nLet $\\theta \\in \\mathbb{R}^5$ where its entries satisfy a linear order, that is, $\\theta_1 < \\theta_2 < \\cdots < \\theta_5$. For example, let $\\theta = [1, 1, 2, 3, 3]$, which has $d_0 = 3$ equivalent classes.\nNow, to define the corresponding sparse pattern, let $\\varphi \\in \\mathbb{R}^4$ with entries defined as $\\varphi_i = \\theta_{i+1} - \\theta_i$, and $\\varphi_d$ = $\\theta_d$. Hence, if $\\theta = [1, 1, 2, 3, 3]$, then $\\varphi = [0, 1, 1, 0, 3]$, so $\\varphi$ is a $d_0 = 3$-sparse vector.\n\nThe concept of hidden symmetry, intuitively speaking, means that the set of arms $\\mathcal X$ contains several equivalence classes, each of which has the same expected reward. However, hidden symmetry implies that the learner does not know the equivalence classes in advance and must learn them through data sampling.\n\n\n## Comment 1: On the computational complexity.\n### Response:\nWe believe that to develop computationally efficient algorithms for a particular partition, we need to fully exploit its structure, similar to how existing literature has exploited the structure of sparsity.\nHowever, this sacrifices the generality of the result, especially if our aim is to establish a general condition on partitions under which one can achieve regret that scales with the dimension of the fixed-point subspace $d_0$.\nAs establishing this general condition is the primary concern of the paper, we did not focus on computational efficiency.\nWe are aware that developing efficient computational methods is important in practice, and we hope to investigate this question in the future for some important classes of partitions other than sparsity, such as non-crossing partitions.\n\nMoreover, as mentioned in Remark 4 of the paper, since the prediction error for each model $m \\in \\mathcal M$ can be computed independently, we can exploit parallel computing to reduce the algorithm's computation time.\n\n## Comment 2: Empirical validation.\n### Response:\n\nWe run the simulation, with $d = 16$, $d_0 = 2$, $\\mathcal X$ is the unit ball, with two scenarios: interval partition, and non-crossing partition. Due to the space constraints, we refer the reviewer to the discussion with Reviewer Viv8 (our response to their Comment 3) for simulation details, and the attached PDF file (Figure 2, 3) for simulation results. The simulation results show that, our algorithm achieves similar (or even smaller) regret in the case of interval partitions, and notably smaller regret in the case of non-crossing partitions compared to the sparse bandit algorithm.\n\n## References:\n[1] Dershowitz&Zaks. Ordered trees and non-crossing partitions. 1986.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you for your valuable and constructive feedback. We have performed the additional experiments as requested by the reviewers and have provided the results in this PDF file. We have also added a picture in this PDF file that illustrates a practical example of how sub-exponential partitioning occurs when there is a hierarchical structure on the set $[d]$.

Meta-review: The paper focuses on a novel low-dimensional structure, exploitable/non-exploitable, in high-dimensional stochastic linear bandits. The paper asserts that the knowledge of the symmetry group (symmetric structure) as a subgroup of permutation matrices structures is not sufficient to achieve sublinear regret (impossibility result). The authors further demonstrate sublinear/minimax optimal regret guarantees under certain symmetries (stronger than permutation but beyond sparsity, a previously known symmetric structure). The guarantees match the minimax lower bound shown in the literature of sparse linear bandit, which is a significant finding acknowledged by some reviewers. The main contribution is theoretical, with practical implementation posing challenges in the proposed settings/algorithms, as commented by reviewers.

There seems to be a concern raised by a reviewer about the necessity of the input $\mathcal{Q}_{d, \le d_0}$. The discussion revealed the requirement of a special structure beyond the partition in the absence of this input, which would be better explained in the paper. There were also comments from several reviewers about the lack of real-world examples where symmetry becomes important. The authors have provided motivating examples that have been acknowledged by the reviewers. These should be included in the revised version of the paper.
Decision: Accept (poster)