# Symmetric Linear Bandits with Hidden Symmetry

Nam Phuong Tran
Department of Computer Science
University of Warwick
Coventry, United Kingdom
<EMAIL_ADDRESS>
&The Anh Ta
CSIRO’s Data61
Australia
&Debmalya Mandal
Department of Computer Science
University of Warwick
Coventry, United Kingdom
<EMAIL_ADDRESS>
&Long Tran-Thanh
Department of Computer Science
University of Warwick
Coventry, United Kingdom
<EMAIL_ADDRESS>
###### 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}^{1/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)})$.

##  1 Introduction

Stochastic bandit is a sequential decision-making problem in which a player,
who aims to maximize his reward, selects an action at each step and receives a
stochastic reward, drawn from an initially unknown distribution of the
selected arm, in response. Linear stochastic bandit (LSB) [2] 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 [24].

Actions in LSB are specified as feature vectors in $\mathbb{R}^{d}$ 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 a sparse
linear function, has been used extensively in LSB to design bandit algorithms
with better performance [3, 32, 21]. However, when the reward function lacks
the structure fo sparsity (which may occur in many real-world situations), a
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 should either
remain unchanged (_invariance_) or shift predictably (_equivariance_). In
supervised learning, it has been empirically observed [15, 12] and
theoretically proven [14, 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 machine learning literature, especially supervised learning, most of
studies on symmetry assume prior knowledge of symmetry structures of the tasks
under consideration [27, 14]. However, in numerous practical scenarios, the
learner can only access to partial knowledge of the symmetry, necessitating
the incorporation of symmetry learning mechanisms into the algorithms to
achieve better performance. Examples of hidden symmetry in reinforcement
learning tasks can be found in robotic control [28, 4]. As an illustrative
example, consider a task of controlling a four-legged ant robot. In the ideal
scenario where all legs are identical, the robot’s movements in space should
exhibit four rotational symmetries:
$(0^{\circ},\;90^{\circ},\;180^{\circ},\;270^{\circ})$. However, due to
potentially different capacities of the legs on the right and left sides,
which is unknown to the designer, the rotational symmetry is reduced to
$(0^{\circ},\;180^{\circ})$. 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
on the assumption of the existence of homogeneous agents [13, 30]. In the
extreme case where all agents are homogeneous, such as in mean-field games,
sample complexity becomes independent of the number of agents [13]. However,
in practice, agents can be clustered into different types [30], and this
information may not be known in advance to the learner (here symmetry occurs
between different agents from the same type). 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 knowledge of the symmetry structure? Moreover, in the
presence of symmetry, when can we design learning algorithms with optimal
regret bounds? Towards answering this question, we investigate the setting of
symmetric linear stochastic bandit in $\mathbb{R}^{d}$, where $d$ is
potentially very large, and the expected reward function is invariant with
respect to the actions of a hidden group $\mathcal{G}$ of coordinate
permutations. Our contributions are summarised as follows:

  1. 1.

We first give an impossibility result that _no algorithm can get any benefit
by solely knowing that $\mathcal{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 is necessary to have further
information about the structure of the hidden subgroup in order to achieve
improved regret bounds.

  2. 2.

Given this, we establish a cardinality condition on the class of symmetric
linear bandits with hidden $\mathcal{G}$, in which the learner can learn the
true symmetry structure and overcome the curse of dimensionality. Notably,
this class includes sparsity as a special case, and therefore inherits all the
computational and statistical complexities of sparsity.

  3. 3.

We cast our problem of learning with hidden subgroup $\mathcal{G}$ into model
selection with collection of low-dimensional subspaces [22, 31]. 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 a new framework inspired
by Gaussian model selection [7] 111We note that “Gaussian model selection” is
a technique in statistics, similar to model aggregation (see [19]’s chapter 2
and 4), which should not be confused with “model selection” in the bandit
literature. 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 $O(d_{0}^{1/3}T^{2/3}\log(d))$, and
$O(d_{0}\sqrt{T}\log(d))$ with an additional assumption on well-separated
partitions, where $d_{0}\ll d$ is the dimension of the low-dimensional
subspace associated with group $\mathcal{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 D.2 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 [3], where the authors
achieve a regret of $\tilde{O}(\sqrt{dsT})$, with $\tilde{O}$ disregarding the
logarithmic factor, and $s$ representing the sparsity level, and $T$ is the
time horizon. This matches the regret lower bound for sparse bandits, which is
$\Omega(\sqrt{dsT})$ [24]. More recently, the contextual version of linear
bandits has gained popularity, where additional assumptions are made regarding
the context distribution and set of arms [23, 32, 25, 11, 21] to avoid
polynomial dependence on $d$. Notably, with the assumption on exploratory set
of arms, [21] propose an Explore then Commit style strategy that achieves
$\tilde{O}(s^{\frac{2}{3}}T^{\frac{2}{3}})$, nearly matching the regret lower
bound $\Omega(s^{\frac{1}{3}}T^{\frac{2}{3}})$ 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 is 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 $\log(M)$. In particular,
[22] propose a 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(T^{\frac{3}{4}}\sqrt{\log(M)})$ under the assumption that the Euclidean
norm of the concatenated feature is bounded by a constant. However, in our
case, the Euclidean norm of the concatenated feature vector can be as large as
$\sqrt{M}$, which leads to a $\sqrt{M}$ multiplicative factor in the regret
bound. Besides, [31] uses the online aggregation oracle approach, and able to
obtain regret of $O(\sqrt{KdT\log(M)})$, where $K$ is the number of arms. In
contrast, _we use algorithmic mechanisms that are different to 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
[19, 7] and dimension reduction on the union of subspaces [8]. With this
technique, we are able to achieve $O(T^{\frac{2}{3}}\log(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$. We refer the reader to Section 4.2 for a more detailed
explanation.

Symmetry in online learning. The notion of symmetry in Markov Decision Making
dates back to works such as [20, 36]. 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 [39, 38] or tighter regret bounds theoretically [37].
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-lumpable bandits [26], 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 a
reduction in terms of regret in the case of hidden symmetry acting on context
spaces [26], this is not the case when the symmetry group acts on the action
space. The work closest to ours is [35], where the authors consider the
setting of a $K$-armed bandit, where the set of arms can be partitioned into
groups with similar mean rewards, such that each group has at least $q>2$
arms. With the constrained partition, the instance-dependent regret bounds are
shown asymptotically to be of order $O\left(\tfrac{K}{q}\log T\right)$.
Comparing to [35], we 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 on the way one partitions the set of arms, which is more natural
in the setting of linear bandits with infinite arms.

##  2 Problem Setting

For any $k\in\mathbb{N}^{+}$, denote $[k]=\\{1,\dots,k\\}$. For
$\mathcal{X}\subseteq\mathbb{R}^{d}$, let $\Delta(\mathcal{X})$ denote the set
of all probability measures supported on $\mathcal{X}$. Given a set
$S\subset\mathbb{R}^{k}$, for some $k>1$, denote $\Pi_{S}(x)$ as the Euclidean
projection of $x\in\mathbb{R}^{k}$ on $S$, and $\mathrm{conv}(S)$ as the
convex hull of $S$.

We denote by $T$ the number of rounds, which is assumed to be known in
advance. Each round $t\in[T]$, the agent chooses an arm
$x_{t}\in\mathcal{X}\subset\mathbb{R}^{d}$, and nature returns a stochastic
reward $y_{t}=\left<x_{t},\theta_{\star}\right>+\eta_{t},\,$ where $\eta_{t}$
is an i.i.d. $\sigma$-Gaussian random variable. Now, denote
$f(x_{t})=\operatorname*{\mathbb{E}}[y_{t}\mid x_{t}]$. A bandit strategy is a
decision rule for choosing an arm $x_{t}$ in round $t\in[T]$, given past
observations up to round $t-1$. Formally, a bandit strategy is a mapping
$\mathcal{A}:(\mathcal{X}\times\mathbb{R})^{T}\rightarrow\Delta(\mathcal{X})$.

Let $x_{\star}=\operatorname*{arg\,max}_{x\in\mathcal{X}}f(x)$, and let
$\mathbf{R}_{T}=\mathbb{E}\left[\sum_{t=1}^{T}\left<x_{\star}-x_{t},\theta_{\star}\right>\right]$
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 of a hidden group of transformations on
the set of arms. We define the notion of group of symmetry as follows:

##### Group and group action.

Given $d\in\mathbb{N}^{+}$, let $\mathcal{S}_{d}$ denote the symmetry group of
$[d]$, that is, $\mathcal{S}_{d}:=\\{h:[d]\rightarrow[d]\mid\text{$h$ is
bijective}\\}$ the collection of all bijective mappings from $[d]$ to itself.
We also define the group action $\hat{\phi}$ of $\mathcal{S}_{d}$ on the
vector space $\mathbb{R}^{d}$ as

$\displaystyle\hat{\phi}:$ $\displaystyle\mathcal{S}_{d}\times\mathbb{R}^{d}$
$\displaystyle\rightarrow\mathbb{R}^{d}$ (1)
$\displaystyle\left(g,(x_{i})_{i\in[d]}\right)$
$\displaystyle\mapsto(x_{g(i)})_{i\in[d]}$

In other words, a group element $g$ acts on an arm $x\in\mathbb{R}^{d}$ 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 as

$\displaystyle\phi:$ $\displaystyle\mathcal{S}_{d}\times\mathbb{R}^{d}$
$\displaystyle\rightarrow\mathbb{R}^{d}$ (2)
$\displaystyle\left(g,(\theta_{i})_{i\in[d]}\right)$
$\displaystyle\mapsto(\theta_{g(i)})_{i\in[d]}$

For brevity, we simply denote $g\cdot\theta$ and $g\cdot x$ as
$\phi(g,\theta)$ and $\hat{\phi}(g,x)$, respectively. Denote by $A_{g}$ the
permutation matrix corresponding to $g$. We write
$\mathcal{G}\leq\mathcal{S}_{d}$ to denote that $\mathcal{G}$ is a subgroup of
$\mathcal{S}_{d}$. Given any point $\theta\in\mathbb{R}^{d}$, we write
$\mathcal{G}\cdot\theta=\left\\{g\cdot\theta\mid g\in\mathcal{G}\right\\}$ to
denote the orbit of $\theta$ under $\mathcal{G}$. It is well known that the
orbit induced by the induced action of a subgroup
$\mathcal{G}\leq\mathcal{S}_{d}$ corresponds to a set partition of $[d]$. We
denote this partition as $\pi_{\mathcal{G}}$.

Let $\mathcal{G}$ be a subgroup of $\mathcal{S}_{d}$ that acts on
$\mathbb{R}^{d}$ via the action $\phi$. In a symmetric linear bandit, the
expected reward is invariant under the group action of $\mathcal{G}$ on
$\mathcal{X}$, that is, $f(g\cdot x)=f(x)$. Due to the linear structure of
$f$, this is equivalent to $g\cdot\theta_{\star}=\theta_{\star}$ for all
$g\in\mathcal{G}$. We assume that, _while the group action $\phi$ is known to
the learner, the specific subgroup $\mathcal{G}$ is hidden and must be learned
in an online manner_.

##  3 Impossibility Result of Learning with General Hidden Subgroups

We now show how to 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 $\mathcal{G}\leq\mathcal{S}_{d}$, 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 a 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 $\mathcal{X}\subseteq\mathbb{R}^{d}$, denote
$\mathrm{Fix}_{\mathcal{G}}(\mathcal{X}):=\left\\{x\in\mathcal{X}\mid g\cdot
x=x,\;\forall g\in\mathcal{G}\right\\}$ as the fixed-point subspace of
$\mathcal{G}$; and
$\mathcal{F}_{\mathcal{S}_{d}}(\mathcal{X}):=\left\\{\mathrm{Fix}_{\mathcal{G}}(\mathcal{X})\mid\mathcal{G}\leq\mathcal{S}_{d}\right\\}$
as the collection of all fixed-point subspaces of all subgroups of
$\mathcal{S}_{d}$. We simply write
$\mathcal{F}_{\mathcal{S}_{d}}=\mathcal{F}_{\mathcal{S}_{d}}(\mathbb{R}^{d})$
and $\mathrm{Fix}_{\mathcal{G}}=\mathrm{Fix}_{\mathcal{G}}(\mathbb{R}^{d})$
for brevity.

##### Set partition.

Given $d\in\mathbb{N}^{+}$, we denote $\mathcal{P}_{d}$ be the set of all
partitions of $[d]$. Let $\mathcal{P}_{d,k}$ as the set of all partitions of
$[d]$ with exactly $k$ classes, and $\mathcal{P}_{d,\leq k}$ be the set of all
partitions of $[d]$ with at most $k$ classes. The number of set partitions
with $k$ classes $|\mathcal{P}_{d,k}|$ is known as the Stirling number of the
second kind, and $|\mathcal{P}_{d}|$ 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 $\mathcal{G}$ can trivially achieve smaller
regret. The reason is that $\theta_{\star}\in\mathrm{Fix}_{\mathcal{G}}$ by
the assumption that $\theta_{\star}$ is invariant w.r.t the action of group
$\mathcal{G}$. If $\mathcal{G}$ is known in advance, the learner can restrict
the support of $\theta_{\star}$ in $\mathrm{Fix}_{\mathcal{G}}$, and
immediately obtains that the regret scales with
$\mathrm{dim}(\mathrm{Fix}_{\mathcal{G}})$ instead of $d$, which can be
significantly smaller (e.g., if $\mathcal{G}=\mathcal{S}_{d}$, then
$\mathrm{dim}(\mathrm{Fix}_{\mathcal{G}})=1$).

For any subgroup, there exists a 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 $\mathcal{G}$ is hidden, one must
learn $\mathrm{Fix}_{\mathcal{G}}$ within the set of candidates
$\mathcal{F}_{\mathcal{S}_{d}}$, leading to the formulation of the model
selection.

##### From the setting with hidden subgroup to the setting with hidden set
partition.

Now, we discuss the structure of the collection of models
$\mathcal{F}_{\mathcal{S}_{d}}$. First, we show the equivalent structure
between the collection of fixed point subspaces and the set partitions as
follows.

######  Proposition 1.

There is a bijection $\mathbf{H}$ between $\mathcal{P}_{d}$ and
$\mathcal{F}_{\mathcal{S}_{d}}$.

As there is a bijection between $\mathcal{P}_{d}$ and
$\mathcal{F}_{\mathcal{S}_{d}}$, we can count the number of subspaces of each
dimension $k$ explicitly using the following.

######  Proposition 2 ([10]’s Theorem 14).

Given a subgroup $\Gamma\leq\mathcal{S}_{d}$ and its fixed-point subspace
$\mathrm{Fix}_{\Gamma}$, suppose that $\pi_{\Gamma}$ partitions $[d]$ into $k$
classes, then $\mathrm{dim}(\mathrm{Fix}_{\Gamma})=k$.

By Proposition 2, we have that the number of subspaces of dimension $k$ in
$\mathcal{F}_{\mathcal{S}_{d}}$ is exactly the number of set partitions with
$k$-classes. Suppose that the learner knows that the orbit under action of
$\mathcal{G}$ partitions the index of $\theta_{\star}$ into 2 equivalent
classes that is, $\mathrm{dim}(\mathrm{Fix}_{\mathcal{G}})=2$. The learner
cannot get any reduction in term of regret.

######  Proposition 3.

Assume that the action set is the unit ball
$\mathcal{X}=\\{x\in\mathbb{R}^{d}\mid\left\|x\right\|_{2}\leq 1\\}$, and $f$
is invariant w.r.t. action of subgroup $\mathcal{G}\leq\mathcal{S}_{d}$, such
that $\mathrm{dim}(\mathrm{Fix}_{\mathcal{G}})=2$. Then, for any $T\geq d/2$,
regret of any bandit algorithm is lower bounded by
$\mathbf{R}_{T}=\Omega(d\sqrt{T})$.

The implication of Proposition 3 is that even if the learner knows
$\theta_{\star}$ lies in an extremely low-dimensional subspace within the
finite pools of candidates, they _still suffer a regret that scales linearly
with the ambient dimension $d$_. This suggests that _further information about
the group $\mathcal{G}$_ must assumed to be known in order to break this
polynomial dependence on $d$ in the regret bound.

##  4 The Case of Hidden Subgroups with Subexponential Size

As indicated by Proposition 3, there is no 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 $d_{0}$ be the upper bound for the dimension of fixed point
subspaces; that is, we know that the orbit of $\mathcal{G}$ partitions $[d]$
into at most $d_{0}$ classes. Now, let us assume that the learner knows that
$\mathcal{G}$ does not partition $[d]$ freely, but must satisfy certain
constraints, that is, $\pi_{\mathcal{G}}\in\mathcal{Q}_{d,\leq
d_{0}}\subset\mathcal{P}_{d,\leq d_{0}}$. Here, $\mathcal{Q}_{d,\leq d_{0}}$
is a small collection of partitions with at most $d_{0}$ classes, which
encodes the constraints on the way $\mathcal{G}$ partitions $[d]$. We
introduce an assumption regarding the cardinality of $\mathcal{Q}_{d,\leq
d_{0}}$, which are 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 $\mathcal{Q}_{d,\leq d_{0}}$ via the bijection
$\mathbf{H}$ as

$\mathcal{M}:=\mathbf{H}\left(\mathcal{Q}_{d,\leq
d_{0}}\right)\quad\text{and}\quad M:=|\mathcal{M}|.$

###  4.1 The Explore-Models-then-Commit Algorithm

Given some $n\in[T]$, we define

$Y=X\theta_{\star}+\bm{\eta},$ (3)

where $Y\in\mathbb{R}^{n}$,
$X=\left[x_{1},\dots,x_{n}\right]^{\top}\in\mathbb{R}^{n\times d}$ is the
design matrix, $\theta_{\star}\in\mathbb{R}^{d}$ is the true model;
$\bm{\eta}=[\eta_{1},...,\eta_{n}]$. We have the information that
$\theta_{\star}$ must be contained in some (not necessarily unique) subspace
$m\in\mathcal{M}$. Denote by $d_{m}$ the dimension of $m$, we have $d_{m}\leq
d_{0}$ for any $m\in\mathcal{M}$. Let
$X_{m}=[\Pi_{m}(x_{t})]_{t\in[n]}^{\top},$ and $S_{m}$ be the column space of
$X_{m}$, one has $\mathrm{dim}(S_{m})\leq d_{m}$. For any $m\in\mathcal{M}$,
and given $Y$, let $\Pi_{S_{m}}(\cdot)$ be the projection onto $S_{m}$. Define

$\widehat{\bm{f}}_{m}:=\Pi_{S_{m}}(Y);\quad\widehat{\theta}_{m}:=\operatorname*{arg\,min}_{\theta\in
m}\left\|Y-X\theta\right\|_{2}^{2}.$ (4)

Now, given $n$ data points, we can choose the model
$\widehat{m}\in\mathcal{M}$ that minimises the least square error

$\widehat{m}\in\operatorname*{arg\,min}_{m\in\mathcal{M}}\|Y-\widehat{\bm{f}}_{m}\|_{2}^{2}.$
(5)

Based on the framework of model selection, we now introduce our Algorithm 1,
Explore-Models-then-Commit (EMC). Our algorithm falls into the class explore-
then-commit bandit algorithms. The exploration phase consists of $t_{1}$
rounds. During this phase, one samples data independently and identically
distributed (i.i.d.) from an exploratory distribution $\nu$. After the
exploration phase, one computes the solution to the model selection problem
and then commits to the best arm corresponding to the chosen model.

######  Remark 4.

Algorithm 1 may incur significant computational costs, as it concurrently
updates all $M$ models. Nevertheless, this process can be entirely
parallelised using tools such as Ray [1]. As a result, the algorithm’s runtime
will remain constant even as the size $M$ of $\mathcal{M}$ increases.

Algorithm 1 Explore Models then Commit

1: Input: $T,\;\nu,\;t_{1}$

2: for $t=1,\dots,t_{1}$ do

3: Independently pull arm $x_{t}$ according to $\nu$ and receive a reward
$y_{t}$.

4: end for

5: $X\leftarrow[x_{1},...,x_{t_{1}}]^{\top}$,
$Y\leftarrow[y_{t}]_{t\in[t_{1}]}$.

6: Compute $\widehat{m}$ as (5).

7: Compute $\widehat{\theta}_{t_{1}}$ as (4) corresponding to $\widehat{m}$.

8: for $t=t_{1}+1$ to $T$ do

9: Take greedy actions:
$x_{t}=\operatorname*{arg\,min}_{x\in\mathcal{X}}\left<\widehat{\theta}_{t_{1}},x\right>.$

10: end for

###  4.2 Regret Analysis

The regret analysis of Algorithm 1 uses results from the Gaussian model
selection literature [7, 19] as a basis. As such, we first state the
assumptions that are common in the Gaussian model selection literature on the
collection of models $\mathcal{M}$ and the set of arms $\mathcal{X}$ (Section
4.2.1). We then provide our main analysis in Section 4.2.2, highlighting the
key technical novelties of our approach.

####  4.2.1 Assumptions

Recall that due to our lower bound in Proposition 3, further assumptions are
required on the collection of fixed-point subspaces to achieve a reduction in
terms of regret. As suggested by the model selection literature [22, 31], one
can achieve regret in terms of $\log(M)$ 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.

######  Assumption 5 (Sub-exponential number of partitions).

The partition corresponding to $\mathcal{G}$ belongs to a small subclass of
partitions $\mathcal{Q}_{d,\leq d_{0}}\subset\mathcal{P}_{d,\leq d_{0}}$. In
particular, $\pi_{\mathcal{G}}\in\mathcal{Q}_{d,d_{\star}},\;\text{for some
$d_{\star}\leq d_{0}$}$, and for each $k\in[d_{0}]$, $|\mathcal{Q}_{d,k}|\leq
O(d^{k})$.

######  Assumption 6 (Exploratory distribution).

There exists a sub-Gaussian exploratory distribution
$\nu\in\Delta(\mathcal{X})$. Specifically, suppose there is a random vector
$Z$ whose distribution is $\nu$, then for any $a\in\mathbb{S}^{d-1}$,
$\left<Z,a\right>$ is a sub-Gaussian random variable.

######  Assumption 7 (Boundedness).

For all $x\in\mathcal{X}$, $\left\|x\right\|_{2}\leq 1$ and
$\left|\left<x,\theta_{\star}\right>\right|\leq R_{\mathrm{\max}}$, for some
$R_{\mathrm{\max}}>0$.

As a consequence of Assumption 5, the cardinality of the collection of fixed
point subspaces is not too large, particularly, $M=O(d^{d_{0}})$. This
assumption holds for broad classes of pattern-avoiding partitions [29], such
as interval partitions and non-crossing partitions. We refer the readers to
Appendix D for a detailed discussion.

######  Remark 8 (Equivalence between sparsity and interval partition).

A set partition of $[d]$ is an interval partition or partition of interval if
its parts are interval. We denote $\mathcal{I}_{d}$ as the collection of all
interval partition of $d$. $\mathcal{I}_{d}$ admits a Boolean lattice of order
$2^{d-1}$, making it equivalent to the sparsity structure in $d-1$ dimensions.
Specifically, consider the set of entries of parameters
$\varphi\in\mathbb{R}^{d}$ with a linear order, that is,
$\varphi_{1}<\varphi_{2}<\dots<\varphi_{d}$. Then define the variable
$\theta\in\mathbb{R}^{d-1}$ such that
$\theta_{i}=(\varphi_{i+1}-\varphi_{i})$. Each interval partition on the
entries of $\varphi$ will determine a unique sparse pattern of $\theta$.
Therefore, it is clear that the cardinality of the set of interval partition
with $d_{0}$ classes is bounded as $|\mathcal{I}_{d,\leq
d_{0}}|=O(d^{d_{0}})$. 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.

Since our setting includes sparsity as a special case, the regret lower bound
in [21] applies to our setting as well. In particular, we have:

######  Proposition 9 (Regret lower bound [21]).

Consider symmetric linear bandits in which Assumption 5, 6, 7 hold. Then any
bandit algorithm must suffer regret
$\mathbf{R}_{T}=\Omega\left(\min\left(d_{0}^{\frac{1}{3}}T^{\frac{2}{3}},\sqrt{d_{0}dT}\right)\right)$.

We note that the lower bound can be relaxed if we have a stronger assumption
on the group $\mathcal{G}$, which allows algorithm to go beyond the lower
bound in Proposition 9 of the sparsity class. For example, if we consider a
collection of fixed-point subspaces with a nested structure, similar to those
discussed in [18], the algorithm may achieve a $O(d_{0}\sqrt{T})$ 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.

####  4.2.2 Main Regret Upper Bound Result

We now state the main result of the regret upper bound for Algorithm 1.

######  Theorem 10.

Suppose the Assumptions 5, 6, 7 hold. With the choice of
$t_{1}=\Omega(d_{0}\log(dT))$, then the regret of Algorithm 1 is upper bounded
as

$\mathbf{R}_{T}=O\left(R_{\mathrm{\max}}^{\frac{1}{3}}T^{\frac{2}{3}}\sigma^{\frac{2}{3}}(d_{0}\log(dT))^{\frac{1}{3}}\right).$
(6)

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

Suppose the Assumptions 5, 6, 7 hold. For $t_{1}=\Omega(d_{0}\log(d/\delta))$,
with probability at least $1-\delta$, one has the estimate

$\left\|\theta_{\star}-\widehat{\theta}_{t_{1}}\right\|_{2}=O\left(\sqrt{\frac{\sigma^{2}d_{0}\log(d/\delta)}{t_{1}}}\right).$
(7)

The constants hidden in asymptotic notations are independent of
$d,\;d_{0},\;T$.

######  Remark 12 (Non-triviality of Lemma 11).

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[31, 22] 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
$\Phi_{m}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d_{0}}$ be the feature map that
computes the image of the projection $\Pi_{m}$ with respect to the orthogonal
basis of subspace $m$. Thus, we then have a collection of $M$ features
$\\{\Phi_{m}\\}_{m\in\mathcal{M}}$. Consider the algorithm introduced in [22],
which concatenates the feature maps into
$\bm{\Phi}(x)=[\Phi_{1}(x),\ldots,\Phi_{M}(x)]\in\mathbb{R}^{Md_{0}}$, and the
regret bound depends on $\|\bm{\Phi}(x)\|_{2}$.

However, in our case where $\|\Phi_{m}(x)\|_{2}<1$, we can only bound
$\|\bm{\Phi}(x)\|_{2}\leq\sqrt{M}$, which leads to a $\sqrt{M}$ dependence on
regret, if we use their algorithm. Regarding [31], 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=\infty$.

We note that the similarity with the model selection technique in [22, 31] is
that they use model aggregation among $\mathcal{M}$ to bound the prediction
error $\sum_{t=1}^{T}\left<x_{t},\widehat{\theta}-\theta_{\star}\right>^{2}$,
but this does not necessarily guarantee the risk error
$\|\widehat{\theta}-\theta_{\star}\|_{2}$. The reason is that, although model
aggregation can guarantee a small prediction error, it imposes no restriction
on the estimator $\widehat{\theta}$, 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 $\mathcal{M}$,
ensuring the following two properties: (1) The prediction error is small,
similar to model aggregation; and (2) We can guarantee that $\widehat{\theta}$
lies in one of the subspaces of $\mathcal{M}$. The second property gives us
control over $(\widehat{\theta}-\theta_{\star})$ by ensuring it lies in at
most $M^{2}$ subspaces. Then, exploiting the restricted isometry property (see
Definition 14) of designed matrix $X$, we can guarantee that with $O(\log(M))$
exploratory samples, we can bound the risk error
$\|\widehat{\theta}-\theta_{\star}\|_{2}$. This is crucial for eliminating
polynomial dependence on $M$ and the number of arms $K$.

##### Proof sketch of Lemma 11.

We provide a proof sketch here and defer their full proof to Appendix B. Our
proof borrows techniques from Gaussian model selection [19] and the compressed
sensing literature [8]. There are two steps to bound the risk error as in
Lemma 11:

##### Step 1 - Bounding the prediction error.

We can bound the prediction error
$\left\|X\theta_{\star}-X\widehat{\theta}_{t_{1}}\right\|_{2}$ using the
Gaussian model selection technique [19] as follows.

######  Proposition 13.

Let $\bm{f}_{\star}=X\theta_{\star}$. For the choice of
$\widehat{\bm{f}}_{\widehat{m}}$ as in Eqn. (4) & Eqn. (5), with probability
at least $1-\delta$, there exists a constant $C>1$ such that

$\left\|\widehat{\bm{f}}_{\widehat{m}}-\bm{f}_{\star}\right\|_{2}^{2}\leq
C\sigma^{2}\log\left(\frac{M}{\delta}\right).$ (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 a sub-Gaussian random matrix as
in [8]. For more detail, let us define the extension of the collection
$\mathcal{M}$ as

$\,\overline{\\!{\mathcal{M}}}:=\left\\{\mathrm{conv}\left(m\cup
m^{\prime}\right)\mid\;m,\;m^{\prime}\in\mathcal{M}\right\\},$ (9)

where $\mathrm{conv}(S)$ is the convex hull of the set
$S\subset\mathbb{R}^{n}$. We have that $\,\overline{\\!{\mathcal{M}}}$ is a
collection of subspaces, that is, $\mathrm{conv}\left(m\cup m^{\prime}\right)$
is indeed a subspace [8]. Denote
$\,\overline{\\!{M}}:=|\,\overline{\\!{\mathcal{M}}}|$, then we have
$\,\overline{\\!{M}}=(M^{2}-M)/2$. Moreover, if dimension of subspace in
$\mathcal{M}$ is at most $d_{0}$, then the dimension of subspace in
$\,\overline{\\!{\mathcal{M}}}$ is at most $2d_{0}$. The reason of introducing
the extension $\,\overline{\\!{\mathcal{M}}}$ is that $\widehat{\theta}$ and
$\theta_{\star}$ can belong to two different subspaces of $\mathcal{M}$, and
$\widehat{\theta}-\theta_{\star}$ may not lie in any subspace of
$\mathcal{M}$, but in $\,\overline{\\!{\mathcal{M}}}$.

An important property of the design matrix $X$, which allows one to recover
$\theta_{\star}$ with the knowledge that $\theta_{\star}$ is in a subspace
$m\in\mathcal{M}$, can be captured by the following notion of restricted
isometry property (RIP):

######  Definition 14 (Restricted isometry property).

For any matrix $X$ and any collection of subspaces
$\,\overline{\\!{\mathcal{M}}}$, we define
$\,\overline{\\!{\mathcal{M}}}$-restricted isometry constant
$\delta_{\,\overline{\\!{\mathcal{M}}}}(X)$ to be the smallest quantity such
that

$(1-\delta_{\,\overline{\\!{\mathcal{M}}}}(X))\leq\frac{\left\|X\theta\right\|_{2}^{2}}{\left\|\theta\right\|_{2}^{2}}\leq(1+\delta_{\,\overline{\\!{\mathcal{M}}}}(X)).$
(10)

We have the minimum number of samples required so that a random matrix $X$
satisfies RIP for a given constant $\delta_{\,\overline{\\!{\mathcal{M}}}}(X)$
with high probability as follows.

######  Proposition 15 ([8]’s Corollary 3.4).

Suppose $X=[x_{t}]_{t\in[n]}$, where $x_{t}$’s are is i.i.d. sub-gaussian
random vectors, and let

$n\geq\frac{2}{c\delta_{\,\overline{\\!{\mathcal{M}}}}(X)}\left(\log(2\,\overline{\\!{M}})+d_{0}\log\left(\frac{12}{\delta_{\,\overline{\\!{\mathcal{M}}}}(X)}\right)+\log(\delta^{-1})\right),$
(11)

for some constant $c>0$ only depends on the distribution of $x_{t}$. Then,
with probability at least $1-\delta$, and for any $\theta_{1},\theta_{2}$ in
subspaces of $\mathcal{M}$, one has that

$(1-\delta_{\,\overline{\\!{\mathcal{M}}}}(X))\left\|\theta_{1}-\theta_{2}\right\|_{2}^{2}\leq\frac{1}{n}\left\|X(\theta_{1}-\theta_{2})\right\|_{2}^{2}\leq(1+\delta_{\,\overline{\\!{\mathcal{M}}}}(X))\left\|\theta_{1}-\theta_{2}\right\|_{2}^{2}$
(12)

Moreover, if $(x_{t})_{t\in[n]}$ are i.i.d. normal random vectors, then
$c=7/18$, see [8]. Lemma 11 is followed by combining Proposition 15 and
Proposition 13.

##  5 Improved Regret Upper Bound

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(\sqrt{T})$
(Section 5.1). We then discuss an interesting open problem in Section 5.2.

###  5.1 Symmetric Linear Bandits with Well-Separated Partitions

Note that for each partition $p\in\mathcal{P}_{d}$, there is a unique
equivalence relation on $[d]$ corresponding to $p$. Denote by
$\overset{p}{\sim}$ the equivalence relation corresponding to $p$. We define
well-separatedness as follows.

Algorithm 2 Exploring Model then Commit with well-separated partition

1: Input: $T,\;\nu,\;t_{2}$

2: for $t=1,\cdots,t_{2}$ do

3: Independently pull arm $x_{t}$ according to $\nu$ and receive a reward
$y_{t}$.

4: end for

5: $X\leftarrow[x_{1},...,x_{t_{1}}]^{\top}$,
$Y\leftarrow[y_{t}]_{t\in[t_{1}]}$.

6: Compute $\widehat{m}$ as (5).

7: for $t=t_{2}+1$ to $T$ do

8: Playing OFUL algorithm [2] on $\widehat{m}$.

9: end for

######  Assumption 16 (Well-separated partitioning).

Given the true subgroup $\mathcal{G}$, and the corresponding partition
$\pi_{\mathcal{G}}$. For all $(i,j)$ such that
$i\overset{\pi_{\mathcal{G}}}{\nsim}j$, it holds that
$|\theta_{\star,i}-\theta_{\star,j}|\geq\varepsilon_{0}$, for some
$\varepsilon_{0}>0$.

The implication of Assumption 16 is that the projection of $\theta_{\star}$ to
any subspace $m\in\mathcal{M}$ not containing $\theta_{\star}$ will cause some
bias in the estimation error. In particular, one can show that for any
$m\in\mathcal{M}$ such that $\theta_{\star}\notin m$, it holds that

$\left\|\theta_{\star}-\Pi_{m}(\theta_{\star})\right\|_{2}^{2}\geq\frac{\varepsilon_{0}^{2}}{2}.$
(13)

We now show that under the Assumption 16, after the exploring phase, the
algorithm returns a true fixed-point subspace $\widehat{m}\ni\theta_{\star}$
with high probability.

######  Lemma 17.

Suppose the Assumptions 5, 6, 7, 16 hold. After
$t_{2}=\Omega\left(\frac{\sigma^{2}d_{0}\log(d\delta^{-1})}{\varepsilon_{0}^{2}}\right)$
exploring rounds, the Algorithm 2 returns $\widehat{m}\ni\theta_{\star}$, with
probability at least $1-\delta$.

Combining Lemma 17 with the standard regret bound $\tilde{O}(d_{0}\sqrt{T})$
for linear bandit algorithms [2] on the chosen subspace $\hat{m}$, we obtain
the following regret bound:

######  Theorem 18.

Suppose the Assumptions 5, 6, 7, 16 hold. Let
$t_{2}=\Omega\left(\frac{\sigma^{2}d_{0}\log(dT)}{\varepsilon_{0}^{2}}\right)$.
Then the regret of Algorithm 2 is upper bounded as

$\mathbf{R}_{T}=O\left(\frac{R_{\mathrm{\max}}\sigma^{2}d_{0}\log(dT)}{\varepsilon_{0}^{2}}+\sigma
d_{0}\sqrt{T\log(d_{0}T)}\right).$ (14)

That is, if the separating constant $\varepsilon_{0}$ is known in advance and
$\varepsilon_{0}\geq T^{-1/4}$, then we can achieve $O(d_{0}\sqrt{T}\log(dT))$
regret upper bound.

###  5.2 Adapting to the Separating Constant $\varepsilon_{0}$

A weakness of Algorithm 2 is that without knowing that $\varepsilon_{0}\geq
T^{-1/4}$ is true a priori, there may be possible mis-specification error,
which leads to linear regret if one applies the algorithm naively. On the
other hand, Algorithm 1 can always achieve regret $O(T^{2/3})$ in the worst
case. As such, the following question arises: Does there exist an algorithm
that, without the knowledge of $\varepsilon_{0}$, can achieve regret
$O(\sqrt{T})$ whenever $\varepsilon_{0}\geq T^{-1/4}$, but guarantees the
worst-case regret of $O(T^{2/3})$?

We now propose a simple method which has $O(\sqrt{T})$ regret whenever the
separating constant is large, and enjoys a worst-case regret guarantee of
$O(T^{3/4})$ (slightly worse than $O(T^{2/3})$). We refer the reader to
Appendix C.2 for a detailed description of the algorithm and further
discussion.

######  Corollary 19.

Suppose the Assumptions 5, 6, 7 hold. Then, there exists an algorithm which
achieves regret bound as follows:

  * (i)

[Well-separated partitions] If $\varepsilon_{0}\geq T^{-1/4}$, then
$\mathbf{R}_{T}=\tilde{O}(d_{0}\sqrt{T})$.

  * (ii)

[None well-separated partitions] If $\varepsilon_{0}<T^{-1/4}$, then
$\mathbf{R}_{T}=\tilde{O}(d_{0}\sqrt{T}+T^{\frac{3}{4}}\sqrt{d_{0}})$.

The result in Corollary 19 is still sub-optimal in the worst case, as it can
only achieve $O(T^{3/4})$ regret bound instead of $O(T^{2/3})$. We conjecture
that new techniques are required to achieve order-optimal regret in both
cases, and will continue to investigate this question in future works.

##  6 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 $\mathcal{G}\leq\mathcal{S}_{d}$. We first prove that no
algorithm can gain any advantage solely by knowing $\mathcal{G}\leq S_{d}$.
Given this, we introduce a cardinality condition on the hidden subgroup
$\mathcal{G}$, allowing the learner to overcome the curse of dimensionality.
Under this condition, we propose novel model selection algorithms that achieve
regrets of $\tilde{O}(d_{0}^{1/3}T^{2/3})$ and $\tilde{O}(d_{0}\sqrt{T})$ with
an additional assumption on the well-separated partition. For future work, we
will explore convex relaxation techniques for efficient computation,
leveraging specific structures of symmetries. In addition, we will investigate
whether there exists an adaptive algorithm that achieves $O(d_{0}\sqrt{T})$ in
the case of a well-separatedness, while also achieving $O(d_{0}^{1/3}T^{2/3})$
in the worst case.

## References

  * [1] Scaling ai and python workloads effortlessly with ray.  https://assets.ctfassets.net/bguokct8bxgd/26Vuu2NJLVnWkX4TkalSmB/fbc74da45885ca8e5048583f8a7e9d25/Ray_OSS_Datasheet_-_Final.pdf.
  * Abbasi-yadkori et al. [2011] 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.
  * Abbasi-Yadkori et al. [2012] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Online-to-confidence-set conversions and application to sparse stochastic bandits.  In _Journal of Machine Learning Research_ , 2012.
  * Abreu et al. [2023] Miguel Abreu, Luis Paulo Reis, and Nuno Lau.  Addressing imperfect symmetry: a novel symmetry-learning actor-critic extension.  _arXiv preprint arXiv:2309.02711_ , 2023.
  * Agarwal et al. [2016] 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.
  * Behboodi et al. [2022] Arash Behboodi, Gabriele Cesa, and Taco Cohen.  A pac-bayesian generalization bound for equivariant networks.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Birgé and Massart [2007] Lucien Birgé and Pascal Massart.  Minimal penalties for gaussian model selection.  _Probability Theory and Related Fields_ , 2007.
  * Blumensath and Davies [2009] 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.
  * Bronstein et al. [2021] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković.  Geometric deep learning: Grids, groups, graphs, geodesics, and gauges, 2021.
  * Bödi and Herr [2009] R. Bödi and K. Herr.  Symmetries in linear and integer programs.  _arXiv preprint arXiv:0908.3329_ , 2009.
  * Carpentier and Munos [2012] 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.
  * Cesa et al. [2022] Gabriele Cesa, Leon Lang, and Maurice Weiler.  A program to build e(n)-equivariant steerable cnns.  In _International Conference on Learning Representations_ , 2022.
  * Chen et al. [2021] Minshuo Chen, Yan Li, Ethan Wang, Zhuoran Yang, Zhaoran Wang, and Tuo Zhao.  Pessimism meets invariance: Provably efficient offline mean-field multi-agent rl.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Elesedy and Zaidi [2021] Bryn Elesedy and Sheheryar Zaidi.  Provably strict generalisation benefit for equivariant models.  In _International Conference on Machine Learning_ , 2021.
  * Finzi et al. [2020] Marc 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.
  * Foster et al. [2019] Dylan J. Foster, Akshay Krishnamurthy, and Haipeng Luo.  Model selection for contextual bandits.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Foster et al. [2020] Dylan J Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert.  Adapting to misspecification in contextual bandits.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Ghosh et al. [2020] Avishek Ghosh, Abishek Sankararaman, and Kannan Ramchandran.  Problem-complexity adaptive model selection for stochastic linear bandits.  _arXiv preprint arXiv:2006.02612_ , 2020.
  * Giraud [2021] Christophe Giraud.  _Introduction to High-Dimensional Statistics_.  2021\.
  * Givan et al. [2003] Robert Givan, Thomas Dean, and Matthew Greig.  Equivalence notions and model minimization in markov decision processes.  _Artificial Intelligence_ , 7 2003.
  * Hao et al. [2020] Botao Hao, Tor Lattimore, and Mengdi Wang.  High-dimensional sparse linear bandits.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Kassraie et al. [2023] Parnian Kassraie, Aldo Pacchiano, Nicolas Emmenegger, and Andreas Krause.  Anytime model selection in linear bandits.  In _Advances in Neural Information Processing Systems_ , 2023.
  * Kim and Paik [2019] Gi-Soo Kim and Myunghee Cho Paik.  Doubly-robust lasso bandit.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit Algorithms_.  Cambridge University Press, 7 2020.
  * Lattimore et al. [2015] Tor Lattimore, Koby Crammer, and Csaba Szepesvári.  Linear multi-resource allocation with semi-bandit feedback.  In _Advances in Neural Information Processing Systems_ , 2015.
  * Lee et al. [2023] Chung-Wei Lee, Qinghua Liu, Yasin Abbasi-Yadkori, Chi Jin, Tor Lattimore, and Csaba Szepesvári.  Context-lumpable stochastic bandits.  6 2023.
  * Li et al. [2019] Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S. Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora.  Enhanced convolutional neural tangent kernels.  11 2019.
  * Mahajan and Tulabandhula [2017] Anuj Mahajan and Theja Tulabandhula.  Symmetry learning for function approximation in reinforcement learning.  _arXiv preprint arXiv:1706.02999_ , 2017.
  * Mansour [2012] Toufik Mansour.  _Combinatorics of Set Partitions_.  2012\.
  * Mondal et al. [2022] 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 Learning Research_ , 2022.
  * Moradipari et al. [2022] Ahmadreza Moradipari, Berkay Turan, Yasin Abbasi-Yadkori, Mahnoosh Alizadeh, and Mohammad Ghavamzadeh.  Feature and parameter selection in stochastic linear bandits.  In _International Conference on Machine Learning_ , 2022.
  * Oh et al. [2021] Min-hwan Oh, Garud Iyengar, and Assaf Zeevi.  Sparsity-agnostic lasso bandit.  In _International Conference on Machine Learning_ , 2021.
  * Pacchiano et al. [2020] 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.13045_ , 2020.
  * Pacchiano et al. [2024] Aldo Pacchiano, Christoph Dann, and Claudio Gentile.  Data-driven online model selection with regret guarantees.  In _International Conference on Artificial Intelligence and Statistics_ , 2024.
  * Pesquerel et al. [2021] Fabien Pesquerel, Hassan Saber, and Odalric Ambrym Maillard.  Stochastic bandits with groups of similar arms.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Ravindran and Barto [2004] 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.
  * Tran and Tran-Thanh [2022] Nam Phuong Tran and Long Tran-Thanh.  Invariant lipschitz bandits: A side observation approach.  In _Machine Learning and Knowledge Discovery in Databases: Research Track_ , 12 2022.
  * van der Pol et al. [2020a] 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_ , 2020a.
  * van der Pol et al. [2020b] 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_ , 2020b.

###### Contents of Appendix

  1. 1 Introduction
    1. 1.1 Related Work
  2. 2 Problem Setting
  3. 3 Impossibility Result of Learning with General Hidden Subgroups
    1. 3.1 Fixed Point Subspace and Partition
    2. 3.2 Impossibility Result
  4. 4 The Case of Hidden Subgroups with Subexponential Size
    1. 4.1 The Explore-Models-then-Commit Algorithm
    2. 4.2 Regret Analysis
      1. 4.2.1 Assumptions
      2. 4.2.2 Main Regret Upper Bound Result
  5. 5 Improved Regret Upper Bound
    1. 5.1 Symmetric Linear Bandits with Well-Separated Partitions
    2. 5.2 Adapting to the Separating Constant $\varepsilon_{0}$
  6. 6 Conclusion and Future Work
  7. A Impossibility Result of Learning with General Hidden Subgroups
  8. B The Case of Hidden Subgroups with Subexponential Size
    1. B.1 High Probability Prediction Error of Model Selection
    2. B.2 Regret Upper bound
  9. C Improved Regret Bound
    1. C.1 Improve Regret Bound with Well-Separated Partitions
    2. C.2 Adapting to Separating Constant $\varepsilon_{0}$
  10. D Further Discussions
    1. D.1 Examples on Hidden Subgroups with Subexponential-Size
    2. D.2 Extended Related Work

##  Appendix 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 $\Gamma\leq\mathcal{S}_{d}$ acting naturally on $[d]$, the orbit of
$\Gamma$ on $[d]$ forms a unique partition of $[d]$. Moreover, for each
partition $\rho\in\mathcal{\mathcal{P}}_{d}$, there exists at least one
$\Gamma\leq\mathcal{S}_{d}$ such that its orbit on $[d]$ under natural action
is exactly $\rho$.

###### 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 $\rho=\\{\rho_{i}\\}_{i\in I}$, where $I$ is
the index of partition; note that $\rho_{i}$ is nonempty and mutually
disjoint. Define a group as follows

$\Gamma_{i}=\left\\{f:\rho_{i}\rightarrow\rho_{i}\mid\text{$f$ is
bijective}\right\\};$ (15)

It is clear that $\Gamma_{i}$ is a group under function composition. Now,
define the product group

$\Gamma:=\prod_{i\in I}\Gamma_{i},$

and the action $\psi:\;\Gamma\times[d]\rightarrow[d]$ such that

$\psi\left((f_{i})_{i\in I},x\right):=f_{j}(x),\quad\text{for $\rho_{j}\ni
x$}.$ (16)

Therefore, it is clear that $(f_{i})_{i\in I}$ is a bijection from $[d]$ onto
itself, hence, $\Gamma$ is a subgroup of $\mathcal{S}_{d}$. ∎

Let $E=(e_{i})_{i\in[d]}$ be the standard basis. Given that group
$\mathcal{G}$ partition $[d]$ into $k$ disjoint orbits, $\mathcal{G}$ also
partition $E$ into $k$ disjoint orbits corresponding to its action $\phi$ on
$\mathbb{R}^{d}$, that is,

$E=\bigcup_{i=1}^{k}E_{i}.$

Let $V_{i}=\mathrm{Span}(E_{i})$, then, one has the following.

######  Proposition 21 ([10]’s Theorem 14).

$\mathrm{Fix}_{\mathcal{G}}(\mathbb{R}^{d})=\bigoplus_{i=1}^{k}\mathrm{Fix}_{\mathcal{G}}(V_{i}).$
(17)

We now state the proof of Proposition 1 as a corollary of Proposition 20 and
Proposition 21. See 1

###### Proof.

First, we show that for each set partition of $[d]$, there exists a unique
$H\in\mathcal{F}_{\mathcal{S}_{d}}(\mathbb{R}^{d})$. This is straightforward
due to the fact that, given a set partition $P$, the partition of basis
$(E_{i})_{i\in I}$ is unique by definition, so as
$V_{i}=\mathrm{span}(E_{i})$. As a result, let
$H=\bigoplus_{i=1}^{k}\mathrm{Fix}_{\Gamma}(V_{i})$, by Proposition 21,
$H\in\mathcal{F}_{\mathcal{S}_{d}}(\mathbb{R}^{d})$. As $(V_{i})_{i\in I}$ is
unique, $H$ is unique.

Second, we show that for each
$H\in\mathcal{F}_{\mathcal{S}_{d}}(\mathbb{R}^{d})$, there is a unique set
partition/equivalent relation $P$. Denote $\overset{\mathrm{P}}{\sim}$ 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\overset{\mathrm{P}}{\sim}q$ under $P$, and
$p\overset{\mathrm{Q}}{\nsim}q$ under $Q$. Denote $H_{P},\;H_{Q}$ as the
subspaces defined by $P$ and $Q$ respectively. As
$p\overset{\mathrm{Q}}{\nsim}q$, there must exist a point $x\in H_{Q}$ such
that $x_{p}\neq x_{q}$. However, $x_{p}=x_{q}$ for all $x\in H_{P}$. Hence,
$H_{P}$ cannot be the same as $H_{Q}$. ∎

See 3

###### Proof.

Suppose there is a collection of model parameter
$\Theta=\\{-\varepsilon,\;\varepsilon\\}^{d}$, for some $\varepsilon>0$. For
each $\theta\in\Theta$, it is straightforward that since $\theta$ has two
classes of indices, by Proposition 1 and 2, there must be a subgroup
$\mathcal{G}\leq\mathcal{S}_{d}$ such that
$\theta\in\mathrm{Fix}_{\mathcal{G}}$ and
$\dim\left(\mathrm{Fix}_{\mathcal{G}}\right)=2$.

Now, $\Theta$ can be used as a family of problem instances for minimax lower
bound of linear bandit. By Theorem 24.2 in [24], if $T\geq d/2$, we have that
with the choice of $\varepsilon=\frac{1}{4\sqrt{3}}\sqrt{d/T}$, one has that

$\mathbf{R}_{T}\geq\frac{16}{\sqrt{3}}d\sqrt{T}.$ (18)

∎

##  Appendix B The Case of Hidden Subgroups with Subexponential Size

###  B.1 High Probability Prediction Error of Model Selection

The proof of Proposition 13 uses the following concentration.

######  Proposition 22 ([19]’s Theorem B.7).

For some subspace $S\subset\mathbb{R}^{n}$ of dimension $d_{S}$, with
probability at least $1-\delta$, one has that

$\left|\left\|\Pi_{S}(\bm{\eta})\right\|_{2}-\sigma\sqrt{d_{S}}\right|\leq\sigma\sqrt{2\log\left(\frac{1}{\delta}\right)}.$
(19)

See 13

###### Proof.

Define $\mathcal{E}_{1}$ as the event such that for all $m\in\mathcal{M}$,

$\left\|\Pi_{S_{m}}(\bm{\eta})\right\|_{2}\leq\sigma\sqrt{d_{m}}+\sigma\sqrt{2\log\left(\frac{1}{\delta_{0}}\right)}.$
(20)

By Proposition 22 and union bound, $\mathcal{E}_{1}$ occurs with probability
$1-M\delta_{0}$. For the rest of the proof, we assume $\mathcal{E}_{1}$ occurs
.

Let us denote $\bm{\widehat{f}}:=\bm{\widehat{f}}_{\widehat{m}}$. By the model
selection procedure (5), one has that

$\|Y-\bm{\widehat{f}}\|^{2}\leq\|Y-\bm{\widehat{f}}_{m_{\star}}\|^{2}.$ (21)

Also, as $Y=\bm{f}_{\star}+\bm{\eta}$, one has that, for some $K>1$

$\displaystyle\left\|\bm{\widehat{f}}-\bm{f}_{\star}\right\|_{2}^{2}\leq\left\|\bm{f}_{\star}-\bm{\widehat{f}}_{m_{\star}}\right\|_{2}^{2}+2\left<\bm{\eta},\bm{f}_{\star}-\bm{\widehat{f}}_{m_{\star}}\right>+K\sigma^{2}d_{\widehat{m}}-2\left<\bm{\eta},\bm{f}_{\star}-\bm{\widehat{f}}\right>-K\sigma^{2}d_{\widehat{m}}.$
(22)

First, consider the term
$\left\|\bm{f}_{\star}-\bm{\widehat{f}}_{m_{\star}}\right\|_{2}^{2}$. Note
that, $\Pi_{S_{m_{\star}}}(\bm{f}_{\star})=\bm{f}_{\star}$, as
$\bm{f}_{\star}\in S_{m_{\star}}$. We have that,

$\displaystyle\left\|\bm{f}_{\star}-\bm{\widehat{f}}_{m_{\star}}\right\|_{2}^{2}$
$\displaystyle=\left\|\bm{f}_{\star}-\Pi_{S_{m_{\star}}}(\bm{f}_{\star}+\bm{\eta})\right\|_{2}^{2}$
(23)
$\displaystyle=\left\|\bm{f}_{\star}-\bm{f}_{\star}\right\|_{2}^{2}-2\left<\Pi_{S_{m_{\star}}}(\bm{\eta}),\bm{f}_{\star}-\bm{f}_{\star}\right>+\left\|\Pi_{S_{m_{\star}}}(\bm{\eta})\right\|_{2}^{2}$
$\displaystyle\leq\left(\sigma\sqrt{d_{m_{\star}}}+\sigma\sqrt{2\log\left(\frac{1}{\delta_{0}}\right)}\right)^{2}$
$\displaystyle\leq
2\sigma^{2}d_{0}+4\sigma^{2}\log\left(\frac{1}{\delta_{0}}\right).$

Second, consider the term
$\left<\bm{\eta},\bm{f}_{\star}-\bm{\widehat{f}}_{m_{\star}}\right>$. We have
that,

$\displaystyle\left<\bm{\eta},\bm{f}_{\star}-\bm{\widehat{f}}_{m_{\star}}\right>$
$\displaystyle=\left<\bm{\eta},\bm{f}_{\star}-\Pi_{S_{m_{\star}}}(\bm{f}_{\star}+\bm{\eta})\right>$
(24)
$\displaystyle=\left<\bm{\eta},\bm{f}_{\star}-\bm{f}_{\star}\right>-\left\|\Pi_{S_{m_{\star}}}(\bm{\eta})\right\|_{2}^{2}\leq
0.$

Third, we need to control the magnitude of the term
$2\left<\bm{\eta},\bm{\widehat{f}}-\bm{f}_{\star}\right>-K\sigma^{2}d_{\widehat{m}}$.
We show that this term can be bounded as

$2\left<\bm{\eta},\bm{\widehat{f}}-\bm{f}_{\star}\right>-K\sigma^{2}d_{\widehat{m}}\leq
a^{-1}\left\|\bm{\widehat{f}}-\bm{f}_{\star}\right\|_{2}^{2}+O(\log(1/\delta_{0})),$

with probability at least $1-M\delta_{0}$, for any constant $a>0$. Denote
$\left<\bm{f}_{\star}\right>$ be the line that is spanned by $\bm{f}_{\star}$.
For each $m\in\mathcal{M}$, let us define the subspace
$\bar{S}_{m}=S_{m}+\left<\bm{f}_{\star}\right>$. Define
$\tilde{S}_{m}\subset\bar{S}_{m}$ as the subspace that is orthogonal to
$\left<\bm{f}_{\star}\right>$, that is, one can write
$\bar{S}_{m}=\tilde{S}_{m}\bigoplus\left<\bm{f}_{\star}\right>$. By AM-GM
inequality, for some $a>0$, we have that

$\displaystyle
2\left<\bm{\eta},\bm{\widehat{f}}-\bm{f}_{\star}\right>=2\left<\Pi_{\bar{S}_{\widehat{m}}}(\bm{\eta}),\bm{\widehat{f}}-\bm{f}_{\star}\right>$
$\displaystyle=2\left<\sqrt{a}\cdot\Pi_{\bar{S}_{\widehat{m}}}(\bm{\eta}),\frac{1}{\sqrt{a}}\left(\bm{\widehat{f}}-\bm{f}_{\star}\right)\right>$
(25) $\displaystyle\leq
a\left\|\Pi_{\bar{S}_{\widehat{m}}}(\bm{\eta})\right\|_{2}^{2}+a^{-1}\left\|\bm{\widehat{f}}-\bm{f}_{\star}\right\|_{2}^{2}$
$\displaystyle=a\sigma^{2}V+a\sigma^{2}U_{\hat{m}}+a^{-1}\left\|\bm{\widehat{f}}-\bm{f}_{\star}\right\|_{2}^{2},$

where
$V=\sigma^{-2}\left\|\Pi_{\left<\bm{f}_{\star}\right>}(\bm{\eta})\right\|_{2}^{2}$
and
$U_{\hat{m}}=\sigma^{-2}\left\|\Pi_{\tilde{S}_{\hat{m}}}(\bm{\eta})\right\|_{2}^{2}$.
Note that, as $\mathrm{dim}(\left<\bm{f}_{\star}\right>)=1$, with probability
at least $1-\delta_{0}$, one has that

$V\leq 2+4\log(\delta^{-1}_{0}).$ (26)

Define the event $\mathcal{E}_{2}$ as the event where the above inequality
holds.

Therefore, our final task is to control the quantity
$aU_{\hat{m}}-Kd_{\widehat{m}}$. Choose $a=(K+1)/2>1$, one has that

$aU_{\hat{m}}-Kd_{\widehat{m}}=\frac{K+1}{2}\left(U_{\hat{m}}-\frac{2K}{K+1}d_{\widehat{m}}\right)\leq\frac{K+1}{2}\max_{m\in\mathcal{M}}\left(U_{m}-\frac{2K}{K+1}d_{m}\right).$

Now, directly control the magnitude of
$U_{\hat{m}}-\frac{2K}{K+1}d_{\widehat{m}}$ is difficult, as $\widehat{m}$
depends on $\bm{\eta}$, and their distribution might be complicated. Instead,
we will control the maximum of the above quantity $U_{m}-\frac{2K}{K+1}d_{m}$
over all $m\in\mathcal{M}$. Since the dimension of $\tilde{S}_{m}$ is at most
$d_{m}$, similar as the event $\mathcal{E}_{1}$, we define the event
$\mathcal{E}_{3}$ as for all $m\in\mathcal{M}$, we have that

$\left\|\Pi_{\tilde{S}_{m}}(\bm{\eta})\right\|_{2}\leq\sigma\sqrt{d_{m}}+\sigma\sqrt{2\log\left(\frac{1}{\delta_{0}}\right)}.$
(27)

By Proposition 22 and the union bound, $\mathcal{E}_{3}$ occurs with
probability at least $1-M\delta_{0}$. We assume that $\mathcal{E}_{3}$ occurs,
then for all $m\in\mathcal{M}$,

$\displaystyle U_{m}$
$\displaystyle\leq\left(\sqrt{d_{m}}+\sqrt{2\log\left(\frac{1}{\delta_{0}}\right)}\right)^{2}$
(28)
$\displaystyle\leq\frac{2K}{K+1}d_{m}+\frac{4K}{K-1}\log\left(\frac{1}{\delta_{0}}\right).$

Therefore, one has that for all $m\in\mathcal{M}$,

$\displaystyle\frac{K+1}{2}\left(U_{\hat{m}}-\frac{2K}{K+1}d_{\widehat{m}}\right)$
$\displaystyle\leq\frac{K+1}{2}\max_{m\in\mathcal{M}}\left(U_{m}-\frac{2K}{K+1}d_{m}\right)$
(29)
$\displaystyle\leq\frac{2K(K+1)}{K-1}\log\left(\frac{1}{\delta_{0}}\right).$

Putting things together, let $\delta=(2M+1)\delta_{0}$, we assure that event
$\mathcal{E}_{1}\cap\mathcal{E}_{2}\cap\mathcal{E}_{3}$ occurs with
probability at least $1-\delta$. Combining (23), (24), (26), (29), with (22),
one has that

$\displaystyle\frac{K-1}{K+1}\left\|\bm{\widehat{f}}-\bm{f}_{\star}\right\|_{2}^{2}$
$\displaystyle\leq
2\sigma^{2}d_{0}+4\sigma^{2}\log\left(\frac{2M+1}{\delta}\right)+K\sigma^{2}d_{0}$
(30)
$\displaystyle+\sigma^{2}(K+1)+2\sigma^{2}(K+1)\log\left(\frac{2M+1}{\delta}\right)+\sigma^{2}\frac{2K(K+1)}{K-1}\log\left(\frac{2M+1}{\delta}\right).$

Note that, the dominating term in the above equation is
$\log\left(\frac{M}{\delta}\right)$, we have that, there is some constant
$C>0$.

$\left\|\bm{\widehat{f}}-\bm{f}_{\star}\right\|_{2}^{2}\leq
C\sigma^{2}\log\left(\frac{M}{\delta}\right).$ (31)

∎

###  B.2 Regret Upper bound

See 11

###### Proof.

First, let consider Proposition 15, with fixed constant
$\delta_{\,\overline{\\!{\mathcal{M}}}}(X)=1/2$, and recall that $\log(M)$ and
$\log(\,\overline{\\!{M}})$ are both $O(d_{0}\log(d))$. Therefore, for the
choice of $t_{1}=\Omega(d_{0}\log(d/\delta))$, with probability at least
$1-\delta/2$, one has that

$\left\|\theta_{\star}-\widehat{\theta}_{t_{1}}\right\|_{2}^{2}\leq\frac{2}{t_{1}}\left\|X(\theta_{\star}-\widehat{\theta}_{t_{1}})\right\|_{2}^{2}$
(32)

Second, by Proposition 13, one has that with probability at least
$1-\delta/2$.

$\left\|X(\theta_{\star}-\widehat{\theta}_{t_{1}})\right\|_{2}^{2}\leq
c_{1}\sigma^{2}d_{0}\log\left(\frac{d}{\delta}\right),$ (33)

for some constant $c_{1}>0$.

Therefore, putting thing together, we have that with probability at least
$1-\delta$, one has that

$\left\|\theta_{\star}-\widehat{\theta}_{t_{1}}\right\|_{2}\leq
c_{2}\sqrt{\frac{\sigma^{2}d_{0}\log\left(\frac{d}{\delta}\right)}{t_{1}}},$
(34)

for some constant $c_{2}>0$. ∎

See 10

###### Proof.

Let define the pesudo regret as
$\widehat{\mathbf{R}}_{T}=\sum_{t=1}^{T}\left<x_{\star}-x_{t},\theta_{\star}\right>$.
We start by simple regret decomposition as follows.

$\displaystyle\widehat{\mathbf{R}}_{T}$
$\displaystyle=\sum_{t=1}^{T}\left<\theta_{\star},x_{\star}-x_{t}\right>=\sum_{t=1}^{t_{1}}\left<\theta_{\star},x_{\star}-x_{t}\right>+\sum_{t=t_{1}+1}^{T}\left<\theta_{\star},x_{\star}-x_{t}\right>$
(35) $\displaystyle\leq
2R_{\mathrm{\max}}t_{1}+\sum_{t=t_{1}+1}^{T}\left<\theta_{\star}-\widehat{\theta}_{t_{1}},x_{\star}-x_{t}\right>+\sum_{t=t_{1}+1}^{T}\underbrace{\left<\widehat{\theta}_{t_{1}},x_{\star}-x_{t}\right>}_{\leq
0}$ $\displaystyle\leq
2R_{\mathrm{\max}}t_{1}+\sum_{t=t_{1}+1}^{T}\left\|\theta_{\star}-\widehat{\theta}_{t_{1}}\right\|_{2}\left\|x_{t}-x_{\star}\right\|_{2}$
$\displaystyle\leq
2R_{\mathrm{\max}}t_{1}+\sum_{t=t_{1}+1}^{T}2\left\|\theta_{\star}-\widehat{\theta}_{t_{1}}\right\|_{2}.$

Now, we invoke Lemma 11. Let $\mathcal{E}$ is the event in that the
exploration error is bounded as in Lemma Lemma 11, one has that

$\displaystyle\widehat{\mathbf{R}}_{T}$ $\displaystyle\leq
2R_{\mathrm{\max}}t_{1}+\mathbb{E}\left[\sum_{t=t_{1}+1}^{T}2\left\|\theta_{\star}-\widehat{\theta}_{t_{1}}\right\|_{2}\bigg{|}\mathcal{E}\right]+T\mathrm{Pr}(\mathcal{E})R_{\mathrm{\max}}$
(36) $\displaystyle\leq
2R_{\mathrm{\max}}t_{1}+c_{1}\sqrt{\frac{\sigma^{2}d_{0}\log(d/\delta)}{t_{1}}}T+T\delta
R_{\mathrm{\max}}.$

Let $\delta=1/T$, and
$t_{1}=R_{\mathrm{\max}}^{-\frac{2}{3}}T^{\frac{2}{3}}\sigma^{\frac{2}{3}}(d_{0}\log(dT))^{\frac{1}{3}}$,
one has that

$\mathbf{R}_{T}=O\left(R_{\mathrm{\max}}^{\frac{1}{3}}T^{\frac{2}{3}}\sigma^{\frac{2}{3}}(d_{0}\log(dT))^{\frac{1}{3}}\right)$
(37)

∎

##  Appendix C Improved Regret Bound

###  C.1 Improve Regret Bound with Well-Separated Partitions

See 17

###### Proof.

Define the event $\mathcal{E}$ as

$\mathcal{E}=\left\\{\left\|Y-\Pi_{S_{\widehat{m}}}(Y)\right\|_{2}^{2}\leq\left\|Y-\Pi_{S_{m}}(Y)\right\|_{2}^{2}\mid\theta_{\star}\in\widehat{m},\;\theta_{\star}\notin
m\right\\},$ (38)

The event $\mathcal{E}$ is equivalent as

$\displaystyle\left\|Y-\Pi_{S_{\widehat{m}}}(Y)\right\|_{2}^{2}$
$\displaystyle\leq\left\|Y-\Pi_{S_{m}}(Y)\right\|_{2}^{2}$ (39)
$\displaystyle\iff$
$\displaystyle\left\|\bm{f}_{\star}+\bm{\eta}-\bm{\widehat{f}}_{\widehat{m}}\right\|_{2}^{2}$
$\displaystyle\leq\left\|\bm{f}_{\star}+\bm{\eta}-\bm{\widehat{f}}_{m}\right\|_{2}^{2}$
$\displaystyle\iff$
$\displaystyle\left\|\bm{f}_{\star}-\bm{\widehat{f}}_{\widehat{m}}\right\|_{2}^{2}+2\left<\bm{\eta},\bm{f}_{\star}-\bm{\widehat{f}}_{\widehat{m}}\right>$
$\displaystyle\leq\left\|\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right\|_{2}^{2}+2\left<\bm{\eta},\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right>.$

First, we upper the LHS of (39) with high probability.

$\displaystyle\left\|\bm{f}_{\star}-\bm{f}_{\star}-\Pi_{S_{\widehat{m}}}(\bm{\eta})\right\|_{2}^{2}+2\left<\bm{\eta},-\Pi_{S_{\widehat{m}}}(\bm{\eta})\right>$
$\displaystyle=\left\|\Pi_{S_{\widehat{m}}}(\bm{\eta})\right\|_{2}^{2}-2\left\|\Pi_{S_{\widehat{m}}}(\bm{\eta})\right\|_{2}^{2}\leq
0\quad\text{[as $\theta_{\star}\in\widehat{m}$]}$ (40)

with probability at least $1-\delta$. The above inequality uses the union
bound for all $m\in\mathcal{M}$.

Second, we lower bound the RHS of (39),
$\left\|\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right\|_{2}^{2}+2\left<\bm{\eta},\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right>$,
with high probability. Let
$\,\overline{\\!{S}}_{m}=S_{m}\bigoplus\left<\bm{f}_{\star}\right>$, then
$\left<\bm{\eta},\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right>=\left<\Pi_{\,\overline{\\!{S}}_{m}}(\bm{\eta}),\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right>$.
Therefore, we have that, with probability at least $1-\delta/3$.

$\displaystyle\left\|\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right\|_{2}^{2}+2\left<\Pi_{\,\overline{\\!{S}}_{m}}(\bm{\eta}),\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right>$
$\displaystyle\geq\left\|\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right\|_{2}^{2}-2\left\|\Pi_{\,\overline{\\!{S}}_{m}}(\bm{\eta})\right\|_{2}^{2}-\frac{1}{2}\left\|\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right\|_{2}^{2}$
(41)
$\displaystyle\geq\frac{1}{2}\left\|\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right\|_{2}^{2}-4\left(\sigma^{2}(d_{0}+1)+\sigma^{2}(\log(3M\delta^{-1}))\right)$
$\displaystyle\geq\frac{1}{2}\left\|\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right\|_{2}^{2}-5\left(\sigma^{2}d_{0}+\sigma^{2}(\log(3M\delta^{-1}))\right),$

as $d_{m}\leq d_{0}$.

Also, we have that, with probability at least $1-\delta/3$

$\displaystyle\left\|\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right\|_{2}^{2}$
$\displaystyle=\left\|\bm{f}_{\star}-\Pi_{S_{m}}(\bm{f}_{\star})-\Pi_{S_{m}}(\bm{\eta})\right\|_{2}^{2}$
$\displaystyle\geq\left\|\bm{f}_{\star}-\Pi_{S_{m}}(\bm{f}_{\star})\right\|_{2}^{2}$

Where the inequalities holds because $\Pi_{S_{m}}(\bm{f}_{\star})$ is the
projection of $\bm{f}_{\star}$ to $S_{m}$. Therefore, we have that

$\left\|\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right\|_{2}^{2}+2\left<\bm{\eta},\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right>\geq\frac{1}{2}\left\|\bm{f}_{\star}-\Pi_{S_{m}}(\bm{f}_{\star})\right\|_{2}^{2}-5\left(\sigma^{2}d_{0}+\sigma^{2}(\log(M\delta^{-1}))\right).$
(42)

Now, by choosing $t_{2}=\Omega\left(\log(M\delta^{-1})\right)$, by Proposition
15, we have that with probability at least $1-\delta/3$,

$\displaystyle\left\|\bm{f}_{\star}-\Pi_{S_{m}}(\bm{f}_{\star})\right\|_{2}^{2}=\left\|X(\theta_{\star}-\Pi_{S_{m}}(\theta_{\star}))\right\|_{2}^{2}\geq\frac{t_{2}}{2}\left\|\theta_{\star}-\Pi_{S_{m}}(\theta_{\star})\right\|_{2}^{2}\geq\frac{t_{2}\varepsilon_{0}^{2}}{4}$
(43)

Therefore, the RHS of (39) is lower bounded as follows

$\left\|\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right\|_{2}^{2}+2\left<\bm{\eta},\bm{f}_{\star}-\bm{\widehat{f}}_{m}\right>\geq\frac{t_{2}\varepsilon_{0}^{2}}{8}-5\left(\sigma^{2}d_{0}+\sigma^{2}(\log(3M\delta^{-1}))\right).$
(44)

Therefore, the sufficient condition for event $\mathcal{E}$ holds with
probability at least $1-\delta$ is that

$\displaystyle\frac{t_{2}\varepsilon_{0}^{2}}{8}-5\left(\sigma^{2}d_{0}+\sigma^{2}(\log(M\delta^{-1}))\right)\geq
0;$ (45)

Note that as $M=O(d_{0}\log(d))$, for $\mathcal{E}$ holds with probability at
least $1-\delta$, it suffice to choose

$t_{2}=\Omega\left(\frac{\sigma^{2}d_{0}\log(d\delta^{-1})}{\varepsilon_{0}^{2}}\right).$
(46)

∎

See 18

###### Proof.

The analysis is an immediate consequence of Lemma 17 with the regret bound of
OFUL in the exploitation phase and $\delta=1/T$. ∎

###  C.2 Adapting to Separating Constant $\varepsilon_{0}$

As stated in Theorem 18, if one knows in advance that the separating constant
$\varepsilon_{0}\geq T^{-1/4}$, then using Algorithm 2 leads to $\sqrt{T}$
regret. The reason is that the learner can learn the true subspace $m_{\star}$
after $\sqrt{T}$ steps with no mis-specification errors. However, without
knowing $\varepsilon_{0}\geq T^{-1/4}$ a priori, one cannot guarantee to
recover the true subspace. Hence, naively using Algorithm 2, which is not
aware of potential mis-specification errors, leads to linear regret. On the
other hand, using Algorithm 1 can achieve regret $T^{2/3}$ in the worst case
(without the knowledge of $\varepsilon_{0}\geq T^{-1/4}$). A question arises:
does there exist an algorithm that, without the knowledge of
$\varepsilon_{0}$, can achieve regret $\sqrt{T}$ whenever $\varepsilon_{0}\geq
T^{-1/4}$, but guarantee the worst-case regret as $T^{2/3}$?

We note that the role of $\varepsilon_{0}$ is similar to 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, we propose a simple method
using adaptation to misspecified error in linear bandit [17], which has a
$\sqrt{T}$ regret whenever the separating constant is large, and enjoys a
worst-case regret guarantee of slightly worse $T^{3/4}$ regret.

The algorithm described in 3 is a direct application of the algorithm proposed
in [17], designed for adapting to misspecification errors in linear bandits.
Particularly, the algorithm in [17] can adapt to unknown misspecification
errors and achieve a regret bound of
$\tilde{O}(d_{0}\sqrt{T}+\epsilon_{\mathrm{mis}}T)$, where
$\epsilon_{\mathrm{mis}}$ is the misspecification error. At a high level, our
algorithm exploring $\sqrt{T}$ rounds using exploratory distribution, which
ensures that the misspecification error $\epsilon_{\mathrm{mis}}$ of the
chosen subspace $\hat{m}$ is at most $T^{-1/4}$. Therefore, we can run
multiple linear bandit algorithms using different levels of misspecification
error. Particularly, we use a collection of $K=\lfloor\log(T)\rfloor$ base
algorithms, where a base algorithm $k\in[K]$ is a linear bandit algorithm with
misspecified level $\varepsilon_{k}=2^{-k}$. Note that the base algorithm $K$
has the same order of regret $\sqrt{T}$ as a well-specified model. Therefore,
in exploitation phase, one can guarantee that in the case of well-separated
partitions where $\epsilon_{\text{mis}}=0$, the algorithm can achieve a regret
of $d_{0}\sqrt{T}$, while in the general case, the regret caused by
misspecification error is at most $T^{3/4}\sqrt{d_{0}}$.

Algorithm 3 Adaptive algorithm

1: Input $T,\;\nu,\;t_{3}$.

2: for $t=1,\cdots,t_{3}$ do

3: Independently pull arm $x_{t}$ according to $\nu$ and receive a reward
$y_{t}$.

4: end for

5: $X\leftarrow[x_{1},...,x_{t_{1}}]^{\top}$,
$Y\leftarrow[y_{t}]_{t\in[t_{1}]}$.

6: Compute $\widehat{m}$ as (5).

7: Let $K=\lfloor\log(T^{1/4})\rfloor$,
$\mathcal{E}=\left\\{\varepsilon_{k}:=2^{-k},\;k\in[K]\right\\}$.

8: for $t=t_{2}+1$ to $T$ do

9: Corralling $K$ base misspecified linear bandit algorithms
SquareCB.Lin+($\varepsilon_{k}$) [17] on $\widehat{m}$.

10: end for

See 19

###### Proof sketch.

Denote
$\epsilon_{\mathrm{mis}}=\|\theta_{\star}-\Pi_{\widehat{m}}(\theta_{\star})\|_{2}$
as the misspecification error. With

$t_{3}=\Omega\left(\sigma^{2}d_{0}\log(d\delta^{-1})\sqrt{T}\right),$

We can guarantee that, with probability at least $1-\delta$, if:

  * (i)

If $\varepsilon_{0}>T^{-1/4}$, then by Lemma 17,
$\theta_{\star}\in\widehat{m}$, that is, $\epsilon_{\mathrm{mis}}=0$;

  * (ii)

If $\varepsilon_{0}>T^{-1/4}$, then by Lemma 11, we can bound
$\epsilon_{\mathrm{mis}}\leq T^{-1/4}$.

The regret of adaptive algorithm in [17] is of the form
$\tilde{O}(d_{0}\sqrt{T}+\epsilon_{\mathrm{mis}}T\sqrt{d_{0}})$. Let
$\delta=1/T$. Consider case (i) where $\epsilon_{\mathrm{mis}}=0$, we have
$\mathbf{R}_{T}=\tilde{O}(d_{0}\sqrt{T})$. Consider case (ii), where
$\epsilon_{\mathrm{mis}}=T^{-1/4}$, we have
$\mathbf{R}_{T}=\tilde{O}(d_{0}\sqrt{T}+T^{3/4}\sqrt{d_{0}})$. ∎

##  Appendix D Further Discussions

###  D.1 Examples on Hidden Subgroups with Subexponential-Size

The model selection procedure in the exploration phase of Algorithms 1 and 2
requires finding the best subspace in the pool $m\in\mathcal{M}$ with respect
to least square errors. In the worst case, the algorithm needs to solve $M$
linear regression approaches. Although this step could be sped up using
parallel computing, it is still important to exploit certain possible
structures in the collection of subspaces $\mathcal{M}$, or equivalently,
structures in the collection of partitions $\mathcal{Q}_{d,\leq d_{0}}$, to
enable efficient computation. However, we argue that the exact computation of
the best subspace $\hat{m}$ as in (5) is an NP-hard problem for many important
cases of unknown partitions (or unknown symmetry).

Pattern-avoidance partitions is arguable the most important class of studied
partition [29], in which, non-crossing partition is one the most studied.

######  Definition 23 (Non-Crossing Partition).

Let $[d]$ admits a cylic order as $1<2<...<d$, and $d<1$. A non-crossing
partition of $[d]$ is a partition such that for if $i,\;j$ in one block and
$p,\;q$ in one block, then they are not arranged in the order $i<p<j<q$.

Similarly, we denote $\mathcal{NC}_{d}$, $\mathcal{NC}_{d,k}$,
$\mathcal{NC}_{d,\leq k}$ as the set of all non-crossing partition of $[d]$,
the set of all partition of $[d]$ with $k$ classes, and the set of all
partition of $[d]$ with at most $k$ classes. We have the following fact ([29]’
section 3.2).

$|\mathcal{NC}_{d}|=\frac{1}{d+1}{2d\choose
d},\quad|\mathcal{NC}_{d,k}|=\frac{1}{d}{d\choose k}{d\choose k-1},$ (47)

which is the Catalan number and the Narayana number. Note that,

$\frac{1}{d}{d\choose k}{d\choose
k-1}\leq\frac{1}{d}\left(\frac{ed}{k}\right)^{k}\left(\frac{ed}{k-1}\right)^{k-1}\leq\frac{1}{d}\left(\frac{ed}{k}\right)^{2k}.$
(48)

Therefore, non-crossing partition satisfied the cardinality restriction as
Assumption 5, that is,
$\mathcal{NC}_{d,\leq d_{0}}\subset\mathcal{Q}_{d,\leq d_{0}}$. One special
case of non-crossing partition is interval partition, which has identical
structure as sparsity.

######  Definition 24 (Interval Partition).

A set partition of $[d]$ is an interval partition or partition of interval if
its parts are interval.

We denote $\mathcal{I}_{d}$ as the collection of all interval partition of
$d$, we have that
$\mathcal{I}_{d}\subset\mathcal{NC}_{d}\subset\mathcal{P}_{d}$.

######  Remark 25.

$\mathcal{I}_{d}$ admits a Boolean lattice of order $2^{d-1}$, making it
equivalent to the sparsity structure in $d-1$ dimensions. Specifically,
consider the set of entries of parameters $\varphi\in\mathbb{R}^{d}$ with a
linear order, that is, $\varphi_{1}<\varphi_{2}<\dots<\varphi_{d}$. Then
define the variable $\theta\in\mathbb{R}^{d-1}$ such that
$\theta_{i}=(\varphi_{i+1}-\varphi_{i})$. Each interval partition on the
entries of $\varphi$ will determine a unique sparse pattern of $\theta$. In
other words, 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.

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 pattern-avoidance partitions in general.

###  D.2 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 a special
case of our setting. As such, we first review the literature of sparsity.
Sparse linear bandits were first investigated in [3], where the authors
achieve a regret of $\tilde{O}(\sqrt{dsT})$, with $\tilde{O}$ 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
$\Omega(\sqrt{dsT})$ [24]. 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 $\tilde{O}(\tau
s\sqrt{T})$, where $\tau$ is a problem-dependent constant that may have a
complex form and varies from paper to paper [23, 32]. Apart from the
contextual assumption, to avoid polynomial dependence on $T$ in the regret
bound, assumptions are required for the set of arms [25, 11, 21]. Recently,
[21] offers a unified perspective on the assumption regarding the set of arms
by assuming the existence of an exploratory distribution on the set of arms.
With this assumption, the authors propose an Explore then Commit style
strategy that achieves $\tilde{O}(s^{\frac{2}{3}}T^{\frac{2}{3}})$, nearly
matching the lower bound $\Omega(s^{\frac{1}{3}}T^{\frac{2}{3}})$ in the poor
data regime [21]. 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 to model selection in
linear bandits, as the learner can collect potential candidates for the
unknown symmetry. Bandit model selection involves the problem where there is 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 [5, 33, 34]. Due to the black-box nature,
the regret guarantee bound depends on $\text{poly}(M)$. There is a growing
literature on model selection in stochastic linear bandits, where there is a
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, [22] propose a
method that concatenates all $M$ features of dimension $d$ into one feature of
dimension $Md$, 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
$O(T^{\frac{3}{4}}\sqrt{\log(M)})$ under the assumption that the Euclidean
norm of the concatenated feature is bounded by a constant. However, in our
case, the Euclidean norm of concatenated feature can be as large as
$\sqrt{M}$, which leads to $\sqrt{M}$ multiplicative factor in regret.
Besides, [31] uses the online aggregation oracle approach, and able to obtain
regret as $O(\sqrt{KdT\log(M)})$, 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
[19] and dimension reduction on the union of subspaces [8]. With this
technique, we are able to achieve $O(T^{\frac{2}{3}}\log(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 [16, 18]. In particular, in the nested feature class where dimensions
range from $\\{1,\dots,d\\}$, and $d_{m_{\star}}<d$ represents the realizable
feature of the smallest dimension, the regret bound can be
$\tilde{O}(\sqrt{Td_{m_{\star}}})$ as shown in [18]. 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 [20, 36]. 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 [39, 38] or tighter regret bounds theoretically [37].
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 [26], 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 a reduction in
terms of regret in the case of unknown symmetry acting on context spaces [26],
this is not the case when the symmetry group acts on the action space.
Particularly, we show that without any extra information on the partition
structure of similar classes of arms, no algorithm can achieve any reduction
in terms of regret. The work closest to ours is [35], where the authors
consider the setting of a $K$-armed bandit, where the set of arms can be
partitioned into groups with similar mean rewards, such that each group has at
least $q>2$ arms. With the constrained partition, the instance-dependent
regret bounds are shown asymptotically to be of order
$O\left((\nicefrac{{K}}{{q}})\log T\right)$. Comparing to [35], 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.