# Invariant Lipschitz Bandits: A Side Observation Approach

Nam Phuong Tran  Department of Computer Science, University of Warwick  Long
Tran-Thanh  Department of Computer Science, University of Warwick

# Invariant Lipschitz Bandits: A Side Observation Approach

Nam Phuong Tran  Department of Computer Science, University of Warwick  Long
Tran-Thanh  Department of Computer Science, University of Warwick

###### Abstract

Symmetry arises in many optimization and decision-making problems, and has
attracted considerable attention from the optimization community: by utilizing
the existence of such symmetries, the process of searching for optimal
solutions can be improved significantly. Despite its success in offline
settings, the utilization of symmetries has not been well examined within
online optimization problems, especially in the bandit literature. As such, in
this paper, we study the invariant Lipschitz bandit setting, a subclass of the
Lipschitz bandits in which a group acts on the set of arms and preserves the
reward function. We introduce an algorithm named UniformMesh-N, which
naturally integrates side observations using group orbits into the uniform
discretization algorithm [17]. Using the side-observation approach, we prove
an improved regret upper bound, which depends on the cardinality of the group,
given that the group is finite. We also prove a matching regret’s lower bound
for the invariant Lipschitz bandit class (up to logarithmic factors). We hope
that our work will ignite further investigation of symmetry in bandit theory
and sequential decision-making theory in general.

Keywords— Bandit Theory Symmetry Group Theory.

##  1 Introduction

Stochastic Multi-Armed Bandit (MAB) is a typical model of a sequential
decision-making problem under uncertainty. The main challenge of these
decision-making problems is uncertainty. That is, the outcome of a decision is
only revealed after the decision is made with the possible presence of noise.
Therefore, to achieve a high total reward, the agent (or the decision maker)
must collect information along with trials and errors (i.e., exploring), while
using this information to choose a decision with a high expected reward (i.e.,
exploiting). The exploration-exploitation trade-off is the main problem that
one usually faces in such decision-making problems. The performance of a
bandit strategy is typically evaluated in terms of regret which is the
difference between the total expected reward of the used strategy and that of
the optimal strategy. Stochastic MAB has been extensively studied since, and
have achieved great success, both theoretically and practically [33, 14]. For
textbook treatment of the subject, see, e.g., [19, 32].

Classical stochastic MAB models assume a finite set of arms and unstructured
environment, that is, information of an arm gives no information of others.
This assumption is rather simple and might not capture the intrinsic relations
between the arms. An immediate consequence is that MAB problems with a large
or even infinite set of arms are difficult or intractable to address without
any further assumption. This leads to a significant body of literature
studying structured MAB, including linear bandits [1], convex optimizations
with bandit feedback [31], and Lipschitz bandits [18, 9]. With these
additional assumptions, algorithms can be designed to exploit the underlying
structures to achieve significantly smaller regret, compared to that of
algorithms that are oblivious to these structures.

In addition to the abovementioned structures on the set of arms, many
decision-making and optimization problems exhibit symmetry, that is, the
expected reward function and the set of arms are invariant under certain group
of transformations. For example, an important real-world application of
continuous bandits, which naturally inherit symmetry, can be found in the
context of online matrix factorization bandits [20]. The online matrix
factorization bandit problem, in turn, has important machine learning
applications, such as in interactive recommendation systems [16, 35, 36], or
the online dictionary learning problem [22, 23]. Briefly speaking, in
recommender systems the matrix factorization method aims to decompose the
user-item rating matrix $R$ into a product of small matrices, that is,
$R=HW^{\top}$, where $H$ is the user-feature matrix and $W$ is the item-
feature matrix. The goal is to find a pair $(H,W)$ such that the matrix $R$
can be recovered. Now, for any orthogonal matrix $\phi$ of the feature space,
it can be easily seen that if any pair $(H,W)$ can recover matrix $R$, the
pair $(H\phi,W\phi)$ can also recover matrix $R$. Therefore, this problem is
invariant with respect to the action of the group of orthogonal matrices. In
fact, as observed in [20], the appearance of symmetry in matrix factorization
gives rise to infinitely many saddle points in the optimization landscape,
causing a great challenge for an optimization algorithm that is oblivious to
the existence of symmetry. We discuss matrix-factorization bandit and the
implications of our result on this problem in Appendix F as it might be of
independent interest.

Another motivating example of symmetry in bandit settings is the online job-
machine allocation problem with identical machines. In this problem, if the
allocation is swapped among these identical machines, the total performance
remains unchanged, and hence the problem is permutation-invariant.
Intuitively, algorithms that are oblivious to this symmetry may waste time
exploring many symmetric solutions, resulting in slower convergence.

While symmetry has not been investigated in the bandit literature, it has been
studied extensively in the optimization domain, especially in Integer Linear
Programming (ILP) [25]. In these problems, where the majority of algorithms
are based on the branch-and-bound principle, the presence of symmetry causes
an extremely waste of time in branching symmetric solutions, if it is not
handled explicitly. The reason for this is that as symmetric solutions yield
the same objective function, they cannot be pruned by the bounding principle.
Therefore, the presence of symmetry causes great difficulty for existing
combinatorial optimization algorithms that are oblivious to symmetry. As such,
various approaches have been proposed to deal with existing symmetry in the
model, including adding symmetry-breaking constraints or pruning symmetric
nodes during the branch-and-bound process.

Despite its ubiquity in optimization problems, to date symmetry has not been
extensively studied in bandit problems, which can be considered as the online
counterpart of many optimization settings. Note that for unstructured
$K$-armed bandit problems, if we assume a group $\mathcal{G}$ acts freely on
the set of arms and the reward function is invariant under the action of
$\mathcal{G}$, then we can compute the fundamental domain (i.e., a subset of
arms whose orbit covers the original set) and restrict the bandit algorithm on
the subset. As there are exactly $K/|\mathcal{G}|$ disjoint orbits, the regret
of standard algorithms such as UCB1 [5] scales as
$\tilde{\mathcal{O}}\left(\sqrt{\frac{Kn}{|\mathcal{G}|}}\right)$ where $n$ is
the total number of rounds. Therefore, one could expect that the same
improvement can be easily achieved in the case of other bandit settings.
However, as we shall point out in detail in Subsection 2.3, the same reasoning
applied to the invariant $K$-armed bandits is not feasible in the case of
Lipschitz bandits. This is due to two main reasons: (i) As the set of arms we
consider is a dense subset of $\mathbb{R}^{d}$, simply counting disjoint
orbits to show the reduction in cardinality of the fundamental domain is not
feasible; (ii) The subgroup of Euclidean isometries we consider in this paper
may admit uncountably infinite fixed points. Therefore, it is not trivial that
the combination of symmetry with other structures such as Lipschitz continuity
might help algorithms achieve better regret.

Now, in theory, if a Lipschitz bandit problem has the expected reward function
to be invariant under the action of a finite group $\mathcal{G}$ of Euclidean
isometries, one naive approach to exploit symmetry is to construct the
fundamental domain and sample within the domain. However, sampling in the
fundamental domain is computationally impractical, as we shall point out in
detail in 2.3. Briefly, constructing a fundamental domain requires placing
global inequalities on the original set of arms, and the problem of finding
value for an arm that satisfies all global constraints is known as a NP-
complete problem [8].

Against this background, we ask the question whether we can design an
efficient bandit algorithm to tackle the Invariant Lipschitz Bandit (ILB)
problem without the need of constructing the fundamental domain (to avoid
facing the computationally expensive task of sampling from that domain). In
particular, we ask that whether utilizing invariance can result in tighter
regret bounds, if the only assumption of the model is that the set of arms is
equipped with a distance, and the expected reward is Lipschitz continuous
w.r.t. the set of arms.

###  1.1 Our Contributions

The contribution of this paper can be summarized as follows.

  1. 1.

We introduce a new model for ILB problems, where the reward and the set of
arms are invariant under a known finite group of transformations.

  2. 2.

We introduce an algorithm, named UniformMesh-N, which naturally integrates
side observations using group orbits into the uniform discretization
algorithm.

  3. 3.

We provide a regret analysis for the algorithm which shows an improvement in
regret by a factor depending on the cardinality of the group. In particular,
we show that if the number of rounds $n$ is large enough, the regret of
UniformMesh-N algorithm is at most
$\tilde{\mathcal{O}}\left(\left(\frac{1}{|\mathcal{G}|}\right)^{\frac{1}{d+2}}n^{\frac{d+1}{d+2}}\right)$,
where $\mathcal{G}$ is the transformation group and $\tilde{\mathcal{O}}$ only
hides logarithmic factor.

  4. 4.

We provide a new lower bound for this bandit class, that is
$\Omega\left(\left(\frac{1}{|\mathcal{G}|}\right)^{\frac{1}{d+2}}n^{\frac{d+1}{d+2}}\right)$,
given $n$ is large enough. This lower bound essentially matches the upper
bound of the algorithm up to a logarithimic factor.

Among these, our most important contribution is the regret analysis, which we
proved a strict improvement of leveraging symmetry in designing algorithm.
Note that, in supervised learning where symmetry is widely studied, while many
empirical work showed that empirical work shows that integrating symmetry into
learning can help reduce the generalization error, from a theoretical
perspective, proving strict improvement when using symmetry is known as a
challenging problem within the machine learning community [13, 7, 29]. To our
knowledge, our analysis is novel and this paper is the first to show a strict
improvement of using symmetry in the sequential decision-making context.

###  1.2 Related Works

Lipschitz MAB problem is referred to as continuum-armed bandit problems in
early works [2, 17, 6], where the set of arms is the interval $[0,1]$. Within
this context, [17] proposed a simple uniform discretization-based algorithm,
which is later referred to as UniformMesh algorithm. Despite its simplicity,
[17] showed that with the global Lipschitz continuous reward function, the
UniformMesh algorithm achieves $\tilde{\mathcal{O}}(n^{2/3})$ regret, which
essentially matches the minimax lower bound up to a logarithmic factor.
However, uniform discretization is potentially wasteful as it keeps the
approximation uniformly good over the whole space, while it is probably better
to adapt the approximation so that the approximation is more precise around
the maxima while being more loose in the rest of the space. With this in mind,
[18] and [9] proposed adaptive discretization algorithms, which are referred
to Zooming algorithm and HOO algorithm, respectively. These adaptive
discretization algorithms achieve better regret when dealing with benign
instances, while not being deteriorated in the worst case. In particular, [18,
9] showed that the regret of these algorithms is at most
$\tilde{\mathcal{O}}(n^{\frac{d^{\prime}+1}{d^{\prime}+2}})$, where
$d^{\prime}$ is near-optimal dimension and is upper-bounded by covering
dimension. Our algorithm is based on UniformMesh algorithm together with side
observation. The rationale behind this choice is that UniformMesh fixes the
set of played points and hence can easily combine with the group orbit to
create a fixed undirected graph, which cannot be done if the set of played
points (i.e., the set of vertices) varies every round. The combination of
group orbit with adaptively discretizing algorithms such as HOO or Zooming
algorithms may require a more complicated treatment and is left for future
work.

Side-observation feedback was first introduced in the adversarial MAB context
[24], and has been further studied by various authors [3, 4, 12]. Especially,
the minimax lower bound as in [24] is $\Omega\left(\sqrt{\alpha n}\right)$,
where $\alpha$ is the independent number of the graph. The first work that
examines side observations in a stochastic MAB setting is [11], in which the
observation graph is undirected and fixed over time. The authors introduced a
naive algorithm named UCB-N, which chooses an arm $x$ that maximizes the index
$\mathrm{UCB}$, then observes all the rewards in the neighborhood of $x$. [11]
proved the gap-dependent regret bound depends is at most
$\mathcal{O}\left(\log(n)\sum_{C\in\mathcal{C}}\frac{\max_{x\in
C}\Delta_{x}}{\min_{x\in C}\Delta_{x}^{2}}\right)$, where $\mathcal{C}$ is a
clique covering of the graph and $\Delta_{x}$ is the subopitimality gap of arm
$x$. More recently, [21] provided an alternative analysis to achieve a tighter
regret for UCB-N,
$\tilde{\mathcal{O}}\left(\log{n}\sum_{x\in\mathcal{I}}\frac{1}{\Delta_{x}}\right)$,
where $\mathcal{I}$ is an independent set of $G$. From this, they also derived
a minimax upper bound as $\tilde{\mathcal{O}}\left(\sqrt{\alpha n}\right)$.
Similarly, [12] an algorithm based on arm elimination that achieves gap-
dependent regret as
$\mathcal{O}\left(\log{n}\sum_{x\in\mathcal{I}}\frac{1}{\Delta_{x}}\right)$,
and minimax regret as $\tilde{\mathcal{O}}\left(\sqrt{\alpha n}\right)$. Our
algorithm UniformMesh-N is based on UCB-N algorithm, and our analysis
technique is similar to [11]. The reason for this choice is that the graph
induced by group action is highly ”regular”, namely, the covering number of
this graph is dependent on the covering number of the fundamental domain.
Therefore, the result of [11] is sufficient to introduce the cardinality of
the group into the regret.

Symmetry has been studied for decades in the literature of (Mixed) Integer
Linear Programming in the case of subgroups of the group of permutation
matrices [25]. There are two main approaches to dealing with symmetry; the
main idea is to eliminate symmetric solutions to reduce search space. The
first approach is to add symmetry-breaking constraints to the domain, making
symmetric solutions infeasible [34]. The second approach is to incorporate
symmetry information during the tree search procedure (e.g., branch and bound)
to prune symmetric branches, for example, isomorphism pruning [26], orbital
branching [27]. The concern of these works is to ensure that at least one of
the optimal solutions remains feasible. However, these works did not compare
the convergence rate of these algorithms, which uses symmetry information,
with algorithms that are oblivious to symmetry information. In contrast, we
analyze the convergence rate of the algorithm in terms of regret and are able
to show an improvement of the algorithm which incorporates the group
information. Although the simple mechanism of uniform discretization allows us
to provide the regret bound, integrating group information with tree-based
algorithms (e.g., isomorphism pruning [26] or orbital branching [27]) is an
interesting research direction and is left for future work.

###  1.3 Outline

The rest of this paper is organized as follows. Notations and some important
proporties of subgroup Euclidean isometries are provided in Section 2,
followed by the mathematical formulation of the ILB problem. In Section 3 we
formalize the construction of the graph induced by the group action; then the
UniformMesh-N algorithm is introduced, followed by its regret analysis. In
Section 4, a regret lower bound for the ILB problem is provided. The limit of
this paper and further work are discussed in Section 5. Due to the space
limit, we defer the most of the proofs to the appendix, as well as the more
detailed description of our algorithm (Appendix G), and the application of our
results to the matrix factorization bandit problem (Appendix F).

##  2 Preliminary and Problem Setup

###  2.1 Preliminary

Let $\mathcal{X}$ be a compact and convex subset of a $d$-dimensional
Euclidean space $E^{d}$; denote $\mathcal{D}$ as Euclidean distance. For any
$x\in\mathcal{X}$ and $\delta>0$, define a $\delta$-open ball as
$\mathcal{B}(x,\delta)=\\{x^{\prime}\in\mathcal{X}\mid\mathcal{D}(x,x^{\prime})<\delta\\}$.

#### Packing and Covering properties.

Consider $\delta>0$, $S\subseteq\mathcal{X}$, and a finite subset
$K\subset\mathcal{X}$. $K$ is called a $\delta$-packing of $S$ if and only if
$K\subset S$ and $\mathcal{D}(i,j)>\delta$ for any two distinct points $i,j\in
K$. $K$ is called a $\delta$-covering of $S$ if and only if for any $x\in S$,
there is $i\in K$ such that $\mathcal{D}(i,x)<\delta$. $K$ is called
$\delta$-net of $S$ if and only if $K$ is both a $\delta$-covering and
$\delta$-packing of $S$. $K$ is called a strictly $\delta$-packing of $S$ if
and only if $K$ is an $\delta$-packing of $S$ and $\mathcal{D}(i,\partial
S)>\delta,\forall i\in K$, where $\partial S$ is the topological boundary of
$S$ in $E^{d}$. The $\delta$-packing number
$N^{\mathrm{pack}}(S,\mathcal{D},\delta)$ of $S\subseteq\mathcal{X}$ with
respect to the metric $\mathcal{D}$ is the largest integer $k$ such that there
exists a $\delta$-packing of $S$ whose cardinality is $k$. The
$\delta$-covering number $N^{\mathrm{cov}}(S,\mathcal{D},\delta)$ of
$S\subseteq\mathcal{X}$ with respect to the metric $\mathcal{D}$ is the
smallest integer $k$ such that there exists a $\delta$-covering of $S$ whose
cardinality is $k$. By the definitions of packing and covering number, if $K$
is a $\delta$-net of $S$, then
$N^{\mathrm{cov}}(S,\mathcal{D},\delta)\leq|K|\leq
N^{\mathrm{pack}}(S,\mathcal{D},\delta)$. Moreover, we can bound the packing
and covering numbers of a compact set as follows.

######  Proposition 1 ([37]).

Let $\mathcal{B}$ be the unit ball and $S$ be a compact subset of $E^{d}$.
Then, for any $\delta>0$, we have

$\displaystyle\left(\frac{1}{\delta}\right)^{d}\frac{\mathrm{Vol}(S)}{\mathrm{Vol}(\mathcal{B})}$
$\displaystyle\leq N^{\mathrm{cov}}(S,\mathcal{D},\delta)\leq
N^{\mathrm{pack}}(S,\mathcal{D},\delta)\leq\left(\frac{3}{\delta}\right)^{d}\frac{\mathrm{Vol}(S)}{\mathrm{Vol}(\mathcal{B})}.$

#### Euclidean isometries.

A bijection mapping $\phi:E^{d}\rightarrow E^{d}$ is a Euclidean isometry if
and only if it preserves the Euclidean distance, that is,
$\mathcal{D}\left(\phi(x),\phi(x^{\prime})\right)=\mathcal{D}(x,x^{\prime})$.
The symmetry group of $\mathcal{X}$, denoted as
$\mathrm{Sym}\left(\mathcal{X}\right)$, is the set of all Euclidean isometries
that preserve $\mathcal{X}$, that is,

$\displaystyle\mathrm{Sym}\left(\mathcal{X}\right)$
$\displaystyle=\\{\phi:E^{d}\rightarrow E^{d}\mid\text{$\phi$ is a Euclidean
isometry and $\phi(\mathcal{X})=\mathcal{X}$}\\}.$

For any group element $\phi\in\mathrm{Sym}\left(\mathcal{X}\right)$, denote
$\phi(x)$ as $\phi\cdot x$. Let $\mathcal{G}$ be a finite subgroup of
$\mathrm{Sym}\left(\mathcal{X}\right)$, we write
$\mathcal{G}\leq\mathrm{Sym}\left(\mathcal{X}\right)$, where $\leq$ denotes
the subgroup relation. Denote the stabilizer of $x$ in $\mathcal{G}$ as
$\mathcal{G}_{x}=\\{g\in\mathcal{G}\mid g\cdot x=x\\}$. Denote the
$\mathcal{G}$-orbit of $x$ as $\mathcal{G}\cdot x=\\{g\cdot x\mid
g\in\mathcal{G}\\}$ and the $\mathcal{G}$-orbit of a subset $S$ as
$\mathcal{G}\cdot S=\\{g\cdot x\mid g\in\mathcal{G},x\in S\\}$. As stated in
[28], any finite group of isometries of Euclidean space must admit a point
$x\in E^{d}$ whose stabilizer $\mathcal{G}_{x}$ is trivial.

For a subset $S\subset E^{d}$, denote the closure of $S$ in $E^{d}$ as
$\overline{S}$. Note that since $\mathcal{X}$ is compact and then closed in
$E^{d}$, the closure of $S$ in $\mathcal{X}$ is equivalent to the closure of
$S$ in $E^{d}$. Next, we state the definition of the fundamental domain, an
important notion that we use throughout the paper, especially in the regret
analysis.

######  Definition 2 (Fundamental domain).

A subset $\mathbf{F}\subset E^{d}$ is a fundamental domain for a finite group
$\mathcal{G}$ of isometries of a Euclidean space $E^{d}$ if and only if (1)
the set $\mathbf{F}$ is open in $E^{d}$; (2) the members of the set
$\\{g\cdot\mathbf{F}\mid g\in\mathcal{G}\\}$ are mutually disjoint; (3)
$E^{d}=\bigcup_{g\in\mathcal{G}}g\cdot\overline{\mathbf{F}}$; (4) $\mathbf{F}$
is connected.

Consider a finite subgroup $\mathcal{G}$ of isometries of $E^{d}$, we can
explicitly construct a fundamental domain for $\mathcal{G}$. Recall that
$\mathcal{G}$ admits a point $x^{o}\in E^{d}$ whose stabilizer
$\mathcal{G}_{x^{o}}$ is trivial. As in [28], a fundamental domain can be
constructed as follows.

######  Definition 3 (Dirichlet domain).

Let $x^{o}$ be a point in $E^{d}$ such that $\mathcal{G}_{x^{o}}$ is trivial.
For each $g\in\mathcal{G}$, define an open half-space as

$H_{g}(x^{o})=\\{x\in E^{d}\mid\mathcal{D}(x,x^{o})<\mathcal{D}(x,g\cdot
x^{o})\\}.$ (1)

A Dirichlet domain is the intersection of those open half-spaces, particularly

$\mathbf{F}=\bigcap_{g\in\mathcal{G}}H_{g}(x^{o}).$ (2)

As shown in [28], a Dirichlet domain is indeed a fundamental domain. Note that
since the boundary of $\mathbf{F}$ is a subset of a finite union of some
$(d-1)$-dimensional hyperplanes, it has volume zero.

Given Dirichlet domain $\mathbf{F}$ of $\mathcal{G}$ in $E^{d}$. Define
$\mathbf{D}=\mathbf{F}\cap\mathcal{X}$. Now, we show that $\mathbf{D}$ is also
a fundamental domain for $\mathcal{G}$ acting in $\mathcal{X}$.

######  Proposition 4.

$\mathbf{D}$ is a fundamental domain for $\mathcal{G}$ acting in
$\mathcal{X}$. In particular, (i) $\mathbf{D}$ is open in $\mathcal{X}$; (ii)
the members of $\\{g\cdot\mathbf{D}\\}_{g\in\mathcal{G}}$ are mutually
disjoint; (iii) $\mathbf{D}$ is connected; (iv)
$\mathcal{X}=\bigcup_{g\in\mathcal{G}}g\cdot\overline{\mathbf{D}}$.

The Proof of Proposition 4 is deferred to Appendix D.

###  2.2 Problem formulation

For any $k\in\mathbb{N}^{+}\setminus\\{1\\}$, denote $[k]$ as $\\{1,...,k\\}$.
Denote the number of rounds as $n$, which is assumed to be known in advance.
Each round $t\in[n]$, the agent chooses an arm $X_{t}\in\mathcal{X}$, then the
nature returns a bounded stochastic reward that is sampled independently from
an unknown distribution $Y_{t}\sim\mathbb{P}_{X_{t}}$. Define the expected
reward function as $f(x):=\mathbb{E}\left[Y_{t}\mid X_{t}=x\right]$. Assume
that $\mathbb{P}_{x}$ has support in $[0,1]$ for all $x\in\mathcal{X}$. A
bandit strategy is a decision rule for choosing an arm $X_{t}$ in round
$t\in[n]$, given past observations up to round $t-1$. Formally, a bandit
strategy is a mapping
$\mathcal{A}:(\mathcal{X}\times[0,1])^{n}\rightarrow\mathcal{P}(\mathcal{X})$,
where $\mathcal{P}(\mathcal{X})$ is the set of probability measures over the
set of arms $\mathcal{X}$. A bandit strategy is deterministic if
$\mathcal{P}(\mathcal{X})$ is the set of Dirac probability measures.

Let $x^{*}$ be an optimal arm, associated with the optimal mean reward
$f^{*}=f(x^{*})$. In each round $t\in[n]$, the agent chooses an arm $X_{t}$
and incurs an immediate regret $f^{*}-f(X_{t})$. The agent’s goal is to
minimize the regret over $n$, defined as

$\mathbf{R}_{n}=\mathbb{E}\left[\sum_{t=1}^{n}f^{*}-f(X_{t})\right].$ (3)

Here, the expectation is taken over all random sources, including both the
randomness in the rewards and the bandit strategy used by the agent. Next, we
state the assumptions on the expected reward function that defines the ILB
problems.

######  Assumption 1 (Lipschitz continuity).

For all $x,x^{\prime}\in\mathcal{X}$,
$\mathcal{D}(x,x^{\prime})\geq|f(x)-f(x^{\prime})|$.

######  Assumption 2 (Invariant expected reward function).

Given a finite subgroup $\mathcal{G}\leq\mathrm{Sym}\left(\mathcal{X}\right)$,
the expected reward function $f$ is invariant under the group action of
$\mathcal{G}$, that is, for all $g\in\mathcal{G}$, $f(x)=f(g\cdot x)$. Assume
that $\mathcal{G}$ is revealed to the agent in advance.

Note that while Lipschitz continuity 1 is the standard assumption that defines
the class of Lipschitz bandits [18], the invariance assumption 2 is new in the
bandit’s literature. As the agent knows $\mathcal{G}$ in advance, he can
benefit from the information to learn the near-optimal arms more quickly.

###  2.3 A warm-up: invariant finite unstructured MAB

#### Invariant unstructured $K$-armed bandit.

As a warm-up, consider the case of an invariant $K$-armed bandit with
unstructured environment. The problem is almost the same as the problem
described in Subsection 2.2, however, there are only $K$ arms, and Lipschitz
continuity (assumption 1) is dropped. Now, assume that the group $\mathcal{G}$
acts freely on $[K]$, denote the quotient space as $[K]/\mathcal{G}$. As each
orbit contains exactly $|\mathcal{G}|$ arms and these orbits are disjoint, it
is obvious that the number of disjoint orbits $\left|[K]/\mathcal{G}\right|$
is $K/|\mathcal{G}|$.

For each element $q$ in the quotient space $[K]/\mathcal{G}$, denote the orbit
$[K]_{q}\subset[K]$ as the orbit corresponding to $q$, and denote $k_{q}$ as
the orbit representation of $[K]_{q}$. We have that the fundamental domain
$\bigcup_{q\in[K]/\mathcal{G}}k_{q}$ must contain the optimal arm, and its
cardinality is $K/\mathcal{G}$. Now, if we apply the standard MAB algorithm
such as UCB1 [5] to the fundamental domain and ignore other arms, we can
obtain the regret
$\tilde{\mathcal{O}}\left(\sqrt{\frac{Kn}{|\mathcal{G}|}}\right)$.

#### Difficulties of Invariant Lipschitz Bandit.

The simplicity of the above result for invariant unstructured MAB is based on
partitioning the set of arms into disjoint orbits, which in turn is based on
two important assumptions that are not feasible in the case of the invariant
and continuous Lipschitz bandit. First, as the set of arms $\mathcal{X}$ is a
uncountable set, simply counting the cardinality of the quotient set
$\mathcal{X}/\mathcal{G}$ to show the number of disjoint orbits as in the case
of $K$-armed bandit is not possible. Second, as groups of Euclidean isometries
might admit (uncountably infinite) fixed points (points which are fixed by all
group elements) and non-effective point (points which are fixed by some group
elements that are not indentity). Therefore, applying group action on some
points in $\mathcal{X}$ may result in the same points, or obtaining orbits
whose points stay arbitrarily close to each other. In this case, the orbit of
these nearly fixed points in the mesh might not produce useful information
(see, e.g., Example 23 in the appendix).

A naive way to exploit symmetry in the ILB setting is to construct the
Dirichlet domain and sampling within this subset. To show the reduction in
terms of regret, proving that the covering number of the fundamental domain is
$\mathcal{O}\left(\frac{\delta^{-d}}{|\mathcal{G}|}\right)$ as a direct
consequence of our Lemma 5 is sufficient. However, as we mentioned in the
introduction, sampling within the fundamental domain is computationally
impractical. In particular, construction of the Dirichlet fundamental domain
in the Lipschitz bandit case is equivalent to placing global inequality
constraints on the set of arms as the construction in Definition 3. Given that
verifying that a value of $x$ satisfies all $|\mathcal{G}|$ linear inequality
constraints takes $|\mathcal{G}|d^{2}$ operation, [8] showed that the problem
of finding a point $x\in\mathcal{X}$ that satisfies the global constraints is
NP-complete, implying that sampling in the fundamental domain is
computationally intractable. Against this background, we seek another approach
that does not require sampling within the fundamental domain. Note that while
in the rest of the paper we are not interested in the method of sampling
within the fundamental domain, the geometric properties of the fundamental
domain still play a crucial role in our analysis.

##  3 UniformMesh-N algorithm and regret analysis

In this section, we first explain the construction of the graph induced by the
group action of $\mathcal{G}$. According to this, UniformMesh-N algorithm is
introduced, followed by its regret analysis.

###  3.1 Graph structure induced by the group action

We now explain how the group action can naturally induce a graph structure on
the set of discretization points of $\mathcal{X}$. Intuitively, in round $t$,
the agent chooses an arm $X_{t}$, and nature returns a reward $Y_{t}$, and the
agent can then use the returned reward $Y_{t}$ to update the node along the
orbit $(\mathcal{G}\cdot X_{t})$. This is similar to the side-observation
setting, where the nature returns not only a reward associating the chosen
arm, but also the rewards of its neighbors in graph feedback. As a result, the
orbit of $X_{t}$ can be treated as a neighborhood of $X_{t}$ in a graph formed
by the group action. Moreover, it turns out that the graph’s structure induced
by the group action is highly regular, particularly its clique covering
depends on the covering number of fundamental domain.

Given a number $\delta>0$, let us denote $V$ as a $\delta$-net of
$\mathcal{X}$. Given the Dirichlet domain $\mathbf{D}$ of $\mathcal{G}$ acting
on $\mathcal{X}$, let $V_{\overline{\mathbf{D}}}$ denote a smallest subset of
$V$ that covers $\overline{\mathbf{D}}$. By Proposition 1, it follows that
$|V|=\Theta(\delta^{-d})$. We now compare the size of $\overline{\mathbf{D}}$
with $\mathcal{X}$ in terms of covering number as the follows.

######  Lemma 5.

For some numbers $c_{1},c_{2}>0$, the cardinality of
$V_{\overline{\mathbf{D}}}$ is bounded as

$|V_{\overline{\mathbf{D}}}|\leq\frac{c_{1}\delta^{-d}}{|\mathcal{G}|}+c_{2}\delta^{-(d-1)}.$
(4)

Moreover, there are constants $c_{3},c_{4}>0$, such that for any
$\delta:0<\delta<c_{4}/|\mathcal{G}|$, one has

$|V_{\overline{\mathbf{D}}}|\leq\frac{c_{3}\delta^{-d}}{|\mathcal{G}|}.$ (5)

Lemma 5 is in a similar vein as Lemma $1$ in [29]. However, while [29] only
proved for the permutation group, our Lemma 5 can be applied to any finite
subgroup of $\mathrm{Sym}\left(\mathcal{X}\right)$, and therefore the
permutation group is treated as a special case. Thus, for our analysis is it
essential to use Lemma 5 instead of the result from [29] (as our setting is
more generic).

The generalization of Lemma 5 comes from a different technique that exploits
the fact that the boundary of the Drichlet domain has zero volume. The proof
is deferred to Appendix A, but we provide the underlying idea of the proof
here. First, we partition the set $V_{\overline{\mathbf{D}}}$ into two
disjoint subsets. The first subset is points in $V_{\overline{\mathbf{D}}}$
lying ”strictly” inside the fundamental domain (whose distance to the boundary
greater than $\delta$), and the second subset is all points in
$V_{\overline{\mathbf{D}}}$ lying near the boundary. Now, it is clear that the
cardinality of the former is lesser than $|V|/|\mathcal{G}|$, since there are
$|\mathcal{G}|$ disjoint images of $\mathbf{D}$ and we can always choose the
image that contains the smallest number of points. The cardinality of the
latter is derived from the fact that the volume of the area near the boundary
shrinks as $\delta$ gets smaller; consequently, the packing number of this
area is only bounded by $\mathcal{O}(\delta^{-(d-1)})$.

Lemma 5 implies that the covering number of the Dirichlet domain is
proportional to $1/|\mathcal{G}|$and can become significantly small when
$|\mathcal{G}|$ is large. This is the key ingredient to the improvement in
regret’s bound. We give examples of some symmetry groups to hightlight the
importance and difficulty of Lemma 5 in appendix E.

Before stating the definition of the graph, we first make an observation as
follows.

######  Proposition 6.

Let $\mathcal{G}$ be a finite subgroup of
$\mathrm{Sym}\left(\mathcal{X}\right)$. For any $x,x^{\prime}\in\mathcal{X}$
and a constant $\delta>0$, if there is an action $g\in\mathcal{G}$ such that
$\mathcal{D}(g\cdot x,x^{\prime})<\delta$, then $\mathcal{D}(x,g^{-1}\cdot
x^{\prime})<\delta$.

######  Definition 7.

Given a constant $\varepsilon>0$, define the graph
$G_{\varepsilon}=(V,E_{\varepsilon})$, where
$E_{\varepsilon}=\left\\{(x,x^{\prime})\mid x,x^{\prime}\in V\text{ and
}\exists g\in\mathcal{G}\text{ s.t. }\mathcal{D}(g\cdot
x,x^{\prime})<\varepsilon\right\\}$.

Note that as a result of Proposition 6, it follows that if $(x,x^{\prime})\in
E_{\varepsilon}$, then $(x^{\prime},x)\in E_{\varepsilon}$. Therefore,
$G_{\varepsilon}$ is an undirected graph.

######  Definition 8.

Given a constant $\varepsilon>0$, a Neighborhood of Orbit $(\mathcal{G}\cdot
x)$ in $V\subset\mathcal{X}$ with distance at most $\varepsilon$ is defined as

$\mathrm{N}(i,\varepsilon)=\left\\{x\in V\mid\exists g\in\mathcal{G}\text{
s.t. }\mathcal{D}(g\cdot i,x)\leq\varepsilon\right\\}.$

It is obvious that $\mathrm{N}(i,\varepsilon)$ is the neighborhood of $i$ in
$G_{\varepsilon}$. Besides, for a constant $\delta>0$, suppose
$x\in\mathrm{N}(i,2\delta)$, let $g\in\mathcal{G}$ such that
$\mathcal{D}(x,g\cdot i)<2\delta$, we obtain

$\displaystyle|f(x)-f(i)|=|f(x)-f(g\cdot i)|<\mathcal{D}(x,g\cdot i)<2\delta.$
(6)

Given a graph $G_{\varepsilon}$, a clique in $G_{\varepsilon}$ is a subset of
vertices $C\subseteq V$ such that all arms in $C$ are neighbors. Moreover, a
clique covering of $G_{\varepsilon}$ is a collection of cliques whose union is
$V$. The clique covering number of the graph $G_{\varepsilon}$, denoted as
$\chi(G_{\varepsilon})$, is the smallest integer $k$ such that there exists a
clique covering of $G_{\varepsilon}$ whose cardinality is $k$.

######  Proposition 9.

Given a constant $\delta>0$ and $i\in V$, the set $\mathrm{N}(i,\delta)$ forms
a clique of graph $G_{2\delta}$.

######  Remark 10.

In order to prove the regret bound using [11]’s analysis, we need to bound the
clique covering of the graph induced by group action, which can be done by
bounding the number of disjoint neighbors of orbits. However, due to the
possibility of the existence of mutual neighbors of orbits, partitioning the
graph into $|V|/|\mathcal{G}|$ disjoint neighbors of orbits is challenging. In
particular, for an arbitrary $\delta$-net $V$ for $\mathcal{X}$, applying $g$
on $x\in V$ does not necessarily result in another point $x^{\prime}\in V$.
This leads to the situation where applying the action on two points in the
mesh $V$ may end up in a same covering ball, implying that they might not have
disjoint neighbors of orbits in $V$. To see this, let $x,x^{\prime}\in V$ such
that $\mathcal{D}(x,x^{\prime})<2\delta$, there could be a case where $g\cdot
x,g^{\prime}\cdot x^{\prime}$ stay in the same covering ball
$\mathcal{B}(z,\delta)$ whose diameter is $2\delta$, for some $z\in V$. The
trivial reduction to $|V|/|\mathcal{G}|$ can only be achieved (as in the case
of $K$-armed bandits) when we have a special mesh where each point in the mesh
can map exactly to another point. If we only look at the combinatorial
properties of the graph induced by group action, it is difficult to prove the
number of disjoint dense neighbors of the graph (cliques). Instead, we need to
look at the geometry of the problem. As a result of Proposition 9 and Lemma 5,
the next lemma shows the upper bound of the clique covering number of the
induced graph by utilising the connection between the clique covering of the
graph and the covering of the fundamental domain.

######  Lemma 11.

There are constants $c_{1},c_{2}>0$, such that for any
$\delta:0<\delta<c_{2}/|\mathcal{G}|$, the clique covering number of graph
$G_{2\delta}$ is bounded as

$\chi(G_{2\delta})\leq\frac{c_{1}\delta^{-d}}{|\mathcal{G}|}.$ (7)

###  3.2 UniformMesh-N: Uniform Discretization with the Transformation Group

UniformMesh-N is a combination between UniformMesh [17] and UCB-N [11].
Roughly speaking, UniformMesh-N first uniformly discretizes the set of arms
$\mathcal{X}$ into a $\delta$-net $V$. The algorithm then exploits the graph
$G_{2\delta}$ induced by the group $\mathcal{G}$ as follows. In each round
$t\in[n]$, it chooses an arm $x\in V$, observes a reward $Y_{t}$ and uses it
to update the UCB index of all points within the neighborhood of $x$ in
$G_{2\delta}$, that is, $\mathrm{N}(x,2\delta)$. In this paper, we assume that
there is an oracle such that in each round $t$, for a chosen arm $x\in V$, the
oracle returns its neighbor of orbit $\mathrm{N}(x,2\delta)$.

To formulate the algorithm, we need some additional notations. For each
$x\in\mathcal{X}$, after round $t\in[n]$, let
$T(x,t):=\sum_{s=1}^{t}\mathbb{I}_{\\{X_{s}=x\\}}$ be the number of times the
arm $x$ is played, where $\mathbb{I}$ is the indicator random variable. After
round $t$, given that the chosen arm is $X_{t}$, arm $x\in\mathcal{X}$ is
observed if and only if $x\in\mathrm{N}(X_{t},2\delta)$. Denote the number of
times arm $x$ is observed after the round $t$ as $O(x,t)$, that is,

$O(x,t):=\sum_{s=1}^{t}\mathbb{I}_{\\{x\in\mathrm{N}(X_{s},2\delta)\\}}.$ (8)

Denote $\hat{f}(x,t)$ as empirical mean reward of $x$, that is,

$\hat{f}(x,t):=\sum_{s=1}^{t}Y_{t}\mathbb{I}_{\\{x\in\mathrm{N}(X_{s},2\delta)\\}}.$
(9)

Let $\mathrm{U}(x,t)$ be the UCB index of arm $x$ after round $t$ as follows:

$\mathrm{U}(x,t):=\hat{f}(x,t)+\sqrt{\frac{2\log(n)}{O(x,t)}}+3\delta.$ (10)

The suboptimal gap of a point $i$ is defined as $\Delta_{i}=f^{*}-f(i)$. Let
$\mathcal{C}$ be a clique covering of graph $G_{2\delta}$. For each clique
$C\in\mathcal{C}$, define its played time as $T(C,t)=\sum_{i\in C}T(i,t)$. It
is clear that $T(C,t)\leq O(i,t)$ for all $i\in C$. The pseudocode of
UniformMesh-N is given in Algorithm 1.

While Algorithm 1 provides a general principle, we argue that the algorithm
can be carried out efficiently with a carefully designed representation of
$V$. In particular, since most of the computation burden is to search
$\mathrm{N}(X_{t},2\delta)$, we can use a tree of coverings to represent $V$
as in [9], and implement tree search to find the neighbor of any point
$x\in\mathrm{N}(X_{t},2\delta)$ within the tree with at most $\mathcal{O}(d)$
operations. We give a detailed description of how to represent $V$ and
implement the search of $\mathrm{N}(X_{t},2\delta)$ in Appendix G. In each
round, it takes only $\mathcal{O}(|\mathcal{G}|d)$ to find an approximation of
$\mathrm{N}(X_{t},2\delta)$, and with a more refined design, we believe that
one can find the exact $\mathrm{N}(X_{t},2\delta)$ with a similar strategy.
Therefore, in contrast to sampling within the fundamental domain, which is
computationally intractable, our algorithm is computationally efficient by
carefully designing the data structure to facilitate searching for the
neighbor of orbits.

Algorithm 1 UniformMesh-N

Require $n,V,\delta,\mathcal{G}$

Init $\mathrm{U}(x,0)=\infty,O(x,0)=0,\hat{f}(x,0)=0$, for all $x\in V$.

for $t=1:n$ do

Play $X_{t}=\arg\max_{x\in V}\mathrm{U}(x,t-1)$ with ties broken arbitrarily.

Receive a reward $Y_{t}$.

Compute $\mathrm{N}(X_{t},2\delta)$.

for $i\in\mathrm{N}(X_{t},2\delta)$ do

Update $O(i,t)$ as (8).

Update $\hat{f}(i,t)$ as (9).

Update $\mathrm{U}(i,t)$ as (10).

end for

end for

######  Theorem 12.

Fix an invariant Lipschitz bandit instance with respect to a finite group
$\mathcal{G}$. There are some numbers $a_{1},a_{2}>0$ such that if
$n=\Omega\left(|\mathcal{G}|^{2d+2}\right)$, the regret of UniformMesh-N
algorithm satisfies

$\mathbf{R}_{n}\leq
a_{1}\left(\frac{\log(n)}{|\mathcal{G}|}\right)^{\frac{1}{d+2}}n^{\frac{d+1}{d+2}}+a_{2}\left(\frac{|\mathcal{G}|}{\log(n)}\right)^{\frac{d}{d+2}}n^{\frac{d}{d+2}}.$
(11)

Note that the second term on the right-hand side of (11) is insignificant, as
it grows at a slower rate in $n$ compared to that of the first term. The proof
of Theorem 12 is deferred to Appendix B, but we provide the intuition
underlying the analysis here. First, using the analysis of [11], the regret
bound increases at most
$\mathcal{O}\left(\sum_{C\in\mathcal{C}}\log(n)\frac{\max_{i\in
C}\Delta_{i}}{\min_{i\in C}\Delta_{i}^{2}}\right)$. In addition, we already
proved that the clique covering number of the graph $G_{2\delta}$ is at most
$|V|/|\mathcal{G}|$ when $n$ is sufficiently large. Moreover, for a strongly
suboptimal clique, the factor $\frac{\max_{i\in C}\Delta_{i}}{\min_{i\in
C}\Delta_{i}^{2}}$ can be reduced to $\mathcal{O}\left(\delta^{-1}\right)$
since the difference in the expected reward of nodes in any clique cannot be
greater than $\delta$. Putting things together and choosing the suitable value
for $\delta$, we obtain Theorem 12.

##  4 Regret Lower Bound

This section presents a minimax lower bound for the ILB class that matchs the
upper bound in Theorem 12 up to a logarithmic factor, hence show that
UniformMesh-N algorithm is near optimal in the minimax sense. The lower bound
for ILB class can be stated formally as follows.

######  Theorem 13.

Consider the invariant Lipschitz bandit problems in
$(\mathcal{X},\mathcal{D})$ with respect to action of group $\mathcal{G}$.
Suppose $n=\Omega(|\mathcal{G}|^{d+1})$, then any bandit strategy must suffer
a regret at least
$\Omega\left(\left(\frac{1}{|\mathcal{G}|}\right)^{\frac{1}{d+2}}n^{\frac{d+1}{d+2}}\right)$.

While the full proof of Theorem 13 is deferred to Appendix C, we brief the
main idea for the lower bound here. First, we prove that the (strictly)
packing number of the fundamental domain $\mathbf{D}$ is at least
$\Omega(\delta^{-d}/|\mathcal{G}|)$ when $\delta$ is small enough. Then, let
$W$ be a strictly packing points in $\mathbf{D}$ that has maximum cardinality,
we can construct a strictly packing points in $\mathcal{X}$ using the group
action on those points in $\mathbf{D}$. Second, we construct a class of
invariant problem instances that assigns the same expected reward for the
image of each point in $W$ under the action of $\mathcal{G}$, and we show that
this class has at least $\Omega(\delta^{-d}/|\mathcal{G}|)$ instances.
Applying standard information-theoretic analysis we obtain the lower bound.

##  5 Conclusion

In this paper, we consider the class of invariant Lipschitz bandit problems.
We first introduce the idea of the graph induced by the group action, and
prove that the clique covering number of this graph is only at most as
$|\mathcal{G}|^{-1}$ large as the number of vertices. Based on the concept of
the group-induced graph, we propose an algorithm called UniformMesh-N, which
uses group orbits as side observations. Furthermore, using side observation-
based analysis, we provide an upper regret for UniformMesh-N, which shows that
the improvement by a factor depends on the cardinality of the group
$\mathcal{G}$; therefore, we are the first to show a strict statistical
benefit of using group information to design algorithms. Finally, we also
provide the regret lower bound for the ILB class, which essentially matches
the upper bound up to a logarithmic factor. This implies that UniformMesh-N
algorithm is near-optimal in the worst case within the class of ILB problems.
Note that as ILB has many important real-world applications (e.g., matrix
factorization bandits, online dictionary learning) our results will open new
research directions in those areas as well, providing new ideas to further
improve the regret bounds of those respective domains.

As our current results use of uniform discretization instead of adaptive
discretization, we conjecture that there is still room for improvement. In
particular, as shown in [18] and [9], uniform discretization is less effective
compared to adaptive discretization. We believe that by applying group orbit
as side observation in adaptive discretization algorithms, one can achieve the
regret bound whose shape is similar to that of Theorem 12, except that the
covering dimension $d$ is replaced by the near-optimal dimension $d^{\prime}$
[9]. However, the combination of side observations with adaptive
discretization algorithms is significantly more challenging in terms of
analysis. The reason is twofold: (i) While the analysis technique of side-
observation setting requires the set of arms (i.e., feedback graph’s vertices)
to be fixed over time, the set of candidate arms in adaptive discretization
algorithms vary each round; (ii) The proof of Lemma 5 heavily depends on the
nice geometric properties of the Dirichlet domain, particularly, the set is
full dimension with zero volume boundary. In contrast, a near-optimal set
(e.g., the near-optimal set assumption in [9]) can have an arbitrary shape.
Therefore, without any further assumption, it is difficult to prove the upper
bound for the covering number of the part of near-optimal set lying in the
fundamental domain.

## References

  * Abbasi-Yadkori et al. [2011] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  2011\.
  * Agrawal [1995] Rajeev Agrawal.  The continuum-armed bandit problem.  _SIAM Journal on Control and Optimization_ , 33:1926–1951, 11 1995.
  * Alon et al. [2013] Noga Alon, Nicolò Cesa-Bianchi, Claudio Gentile, and Yishay Mansour.  From bandits to experts: A tale of domination and independence.  7 2013.
  * Alon et al. [2017] Noga Alon, Nicolo Cesa-Bianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir.  Nonstochastic multi-armed bandits with graph-structured feedback.  _SIAM Journal on Computing_ , 46, 2017.
  * Auer et al. [2002] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine Learning_ , 47, 2002.
  * Auer et al. [2007] Peter Auer, Ronald Ortner, and Csaba Szepesvári.  Improved rates for the stochastic continuum-armed bandit problem.  volume 4539 LNAI, 2007.
  * [7] Arash Behboodi, Gabriele Cesa, and Taco Cohen.  A PAC-bayesian generalization bound for equivariant networks.  In _Advances in Neural Information Processing Systems_.
  * Bessiere et al. [2007] Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, and Toby Walsh.  The complexity of reasoning with global constraints.  _Constraints_ , 12, 2007.  ISSN 13837133.  doi: 10.1007/s10601-006-9007-3.
  * Bubeck et al. [2011a] Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári.  X-armed bandits.  _Journal of Machine Learning Research_ , 12, 2011a.
  * Bubeck et al. [2011b] Sébastien Bubeck, Gilles Stoltz, and Jia Yuan Yu.  Lipschitz bandits without the lipschitz constant.  5 2011b.
  * Caron et al. [2012] Stephane Caron, Branislav Kveton, Marc Lelarge, and Smriti Bhagat.  Leveraging side observations in stochastic bandits.  10 2012.
  * Cohen et al. [2016] Alon Cohen, Tamir Hazan, and Tomer Koren.  Online learning with feedback graphs without the graphs.  5 2016.
  * Elesedy and Zaidi [2021] Bryn Elesedy and Sheheryar Zaidi.  Provably strict generalisation benefit for equivariant models.  2 2021.
  * Herbert [1952] Robbins Herbert.  Some aspects of the sequential design of experiments.  _Bulletin of the American Mathematical Society_ , 58, 1952.  ISSN 02730979.  doi: 10.1090/S0002-9904-1952-09620-8.
  * Jain and Pal [2022] Prateek Jain and Soumyabrata Pal.  Online low rank matrix completion.  9 2022.
  * Kawale et al. [2015] Jaya Kawale, Hung Bui, Branislav Kveton, Long Tran Thanh, and Sanjay Chawla.  Efficient thompson sampling for online matrix-factorization recommendation.  volume 2015-January, 2015.
  * Kleinberg [2005] Robert Kleinberg.  Nearly tight bounds for the continuum-armed bandit problem.  2005\.
  * Kleinberg et al. [2019] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal.  Bandits and experts in metric spaces.  _Journal of the ACM_ , 66, 2019.
  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit Algorithms_.  Cambridge University Press, 7 2020.
  * Li et al. [2019] Xingguo Li, Junwei Lu, Raman Arora, Jarvis Haupt, Han Liu, Zhaoran Wang, and Tuo Zhao.  Symmetry, saddle points, and global optimization landscape of nonconvex matrix factorization.  _IEEE Transactions on Information Theory_ , 65, 2019.  ISSN 15579654.  doi: 10.1109/TIT.2019.2898663.
  * Lykouris et al. [2019] Thodoris Lykouris, Eva Tardos, and Drishti Wali.  Feedback graph regret bounds for thompson sampling and ucb.  5 2019.
  * Lyu et al. [2020] Hanbaek Lyu, Deanna Needell, and Laura Balzano.  Online matrix factorization for markovian data and applications to network dictionary learning.  _J. Mach. Learn. Res._ , 2020.
  * Mairal et al. [2010] Julien Mairal, Francis Bach, Jean Ponce, and Guillermo Sapiro.  Online learning for matrix factorization and sparse coding.  _Journal of Machine Learning Research_ , 11, 2010.  ISSN 15324435.
  * Mannor and Shamir [2011] Shie Mannor and Ohad Shamir.  From bandits to experts: On the value of side-observations.  2011\.
  * Margot [2010] François Margot.  _Symmetry in Integer Linear Programming_ , pages 647–686.  Springer Berlin Heidelberg, 2010.
  * Margot [2002] François Margot.  Pruning by isomorphism in branch-and-cut.  _Mathematical Programming, Series B_ , 94, 2002.  ISSN 00255610.  doi: 10.1007/s10107-002-0358-2.
  * Ostrowski et al. [2011] James Ostrowski, Jeff Linderoth, Fabrizio Rossi, and Stefano Smriglio.  Orbital branching.  _Mathematical Programming_ , 126, 2011.  ISSN 00255610.  doi: 10.1007/s10107-009-0273-x.
  * Ratcliffe [2007] John G. Ratcliffe.  _Foundations of Hyperbolic Manifolds_.  2007\.  doi: 10.1007/978-0-387-47322-2.
  * Sannai et al. [2019] Akiyoshi Sannai, Masaaki Imaizumi, and Makoto Kawano.  Improved generalization bounds of group invariant / equivariant deep networks via quotient feature spaces.  10 2019.
  * Sen et al. [2016] Rajat Sen, Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G. Dimakis, and Sanjay Shakkottai.  Contextual bandits with latent confounders: An nmf approach.  6 2016.  Must.
  * Shamir [2013] Ohad Shamir.  On the complexity of bandit and derivative-free stochastic convex optimization.  volume 30, 2013.
  * Slivkins [2019] Aleksandrs Slivkins.  Introduction to multi-armed bandits.  _Foundations and Trends in Machine Learning_ , 12, 2019.
  * Thompson [1933] William R. Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25, 1933.
  * Walsh [2012] Toby Walsh.  Symmetry breaking constraints: Recent results.  volume 3, 2012.  doi: 10.1609/aaai.v26i1.8437.
  * Wang et al. [2017] Huazheng Wang, Qingyun Wu, and Hongning Wang.  Factorization bandits for interactive recommendation.  2017\.  doi: 10.1609/aaai.v31i1.10936.
  * Wang et al. [2019] Qing Wang, Chunqiu Zeng, Wubai Zhou, Tao Li, S. S. Iyengar, Larisa Shwartz, and Genady Ya Grabarnik.  Online interactive collaborative filtering using multi-armed bandit with dependent arms.  _IEEE Transactions on Knowledge and Data Engineering_ , 31, 2019.  ISSN 15582191.  doi: 10.1109/TKDE.2018.2866041.
  * Wu [2016] Yihong Wu.  Lecture 14: Packing, covering, and consequences on minimax risk.  http://www.stat.yale.edu/~yw562/teaching/598/lec14.pdf, 2016.  [Online].

Appendix

##  Appendix A Properties of The Graph Induced by the Group Action

###  A.1 Proof of Lemma 5

To prove Lemma 5, we first need the following proposition.

######  Proposition 14.

Let $H$ be a $(d-1)$-dimensional hyperplane in an Euclidean space $E^{d},d>1$,
and $S\subset H\subset E^{d}$ be a bounded subset. For $\delta>0$, define
$K=\\{x\in E^{d}\mid\mathcal{D}(x,S)<\delta\\}$. For a small positive number
$0<\delta<\frac{1}{4}$, there exists a finite positive constant $c>0$ such
that $\mathrm{Vol}(K)\leq c\delta$.

###### Proof.

By rotation and translation, we can suppose that $H$ is the vector subspace
whose last coordinate is $0$. Then $S$ is covered by a fixed cube in $H$, that
is,

$\left(\prod_{i=1}^{d-1}I_{i}\right)\times\\{0\\},$

where $I_{i}=[a_{i},b_{i}]$ for some finite numbers $a_{i},b_{i}$ such that
$a_{i}<b_{i}$. Then $K$ is a subset of the whole cube
$\left(\prod_{i=1}^{d-1}I_{i}\right)\times[-\delta,\delta]$. Define
$l_{i}=b_{i}-a_{i}$, we have

$\displaystyle\mathrm{Vol}(K)$ $\displaystyle\leq
2\delta\prod_{i=1}^{d-1}(l_{i}+2\delta)$ $\displaystyle\leq 2\delta
c_{\mathrm{max}}\sum_{i=0}^{d-1}(2\delta)^{i}$ $\displaystyle\leq 2\delta
c_{\mathrm{max}}\frac{1}{1-2\delta},$

for some constant $c_{\mathrm{max}}>0$. Now, for $0<\delta<1/4$, we have
$\mathrm{Vol}(K)\leq 4c_{\mathrm{max}}\delta<c\delta$ for some number $c>0$
that is independent of $\delta$. ∎

Now we proceed to the proof of Lemma 5.

###### Proof of Lemma 5.

Denote $V_{\overline{\mathbf{D}},1}=\\{x\in
V_{\overline{\mathbf{D}}}\mid\mathcal{D}(x,\partial\mathbf{D})\leq\delta\\}$
and $V_{\overline{\mathbf{D}},2}=\\{x\in
V_{\overline{\mathbf{D}}}\mid\mathcal{D}(x,\partial\mathbf{D})>\delta\\}$.
Thus, $V_{\overline{\mathbf{D}},1}$ and $V_{\overline{\mathbf{D}},2}$ are
disjoint subsets of $V_{\overline{\mathbf{D}}}$ whose union is
$V_{\overline{\mathbf{D}}}$. Now, we prove the upper bounds for the
cardinality of $V_{\overline{\mathbf{D}},1}$ and
$V_{\overline{\mathbf{D}},2}$.

#### First Step.

By the construction of the Dirichlet domain $\mathbf{D}$, its boundary is a
finite union of bounded subsets in some $(d-1)$-dimensional hyperplanes. In
particular,

$\partial\mathbf{D}\subseteq\bigcup_{i=1}^{m}S_{i},$ (12)

where $S_{i}$ is a bounded subset in some $(d-1)$-dimensional hyperplane, and
$m\leq|\mathcal{G}|$.

Now, we bound the number of elements in $V_{\overline{\mathbf{D}}}$ whose
distance to $\partial\mathbf{D}$ is smaller than $\delta$. Denote the set of
points whose distance near the boundary is $B$, that is,
$B=\\{x\in\mathcal{X}\mid\mathcal{D}(x,S_{i})\leq\delta,\forall i\in[m]\\}$.
Denote $K_{i}=\\{x\in\mathcal{X}\mid\mathcal{D}(x,S_{i})\leq\delta\\}$, we
have

$B=\bigcup_{i=1}^{m}K_{i}.$

This implies $\mathrm{Vol}(B)\leq\sum_{i=1}^{m}\mathrm{Vol}(K_{i})$. By
Proposition 14, it follows that

$\mathrm{Vol}(B)\leq\mathcal{O}(\delta).$

#### Second step.

By Proposition 1, it follows that

$N^{\mathrm{pack}}(B,\mathcal{D},\delta)\leq\left(\frac{3}{\delta}\right)^{d}\frac{\mathrm{Vol}(K)}{\mathrm{Vol}(\mathcal{B})}\leq
c_{2}\delta^{-(d-1)},$ (13)

where $c_{2}$ is some positive number and $\mathcal{B}$ is the unit ball of
$E^{d}$. Since $V_{\overline{\mathbf{D}},1}$ is a $\delta$-packing of $B$, it
follows that

$|V_{\overline{\mathbf{D}},1}|\leq N^{\mathrm{pack}}(B,\mathcal{D},\delta)\leq
c_{2}\delta^{-(d-1)}$ (14)

#### Third step.

Since there are $|\mathcal{G}|$ disjoint images of $\mathbf{D}$, if we
allocate $|V_{\overline{\mathbf{D}}}|$ points to such images, there must be
one image containing at most $|V|/|\mathcal{G}|$ points. Without loss of
generality, let $\mathbf{D}$ be such image, we obtain

$\displaystyle|V_{\overline{\mathbf{D}},2}|$
$\displaystyle\leq|V|/|\mathcal{G}|$
$\displaystyle\leq\frac{c_{1}\delta^{-d}}{|\mathcal{G}|},$ (15)

for some constant $c_{1}>0$, where the last inequality holds by Proposition 1.
From (14) and (15), it follows that

$\displaystyle|V_{\overline{\mathbf{D}}}|$
$\displaystyle\leq\frac{c_{1}\delta^{-d}}{|\mathcal{G}|}+c_{2}\delta^{-(d-1)}$
$\displaystyle=\frac{\delta^{-d}(c_{1}+c_{2}|\mathcal{G}|\delta)}{\mathcal{G}}\leq\frac{c_{4}\delta^{-d}}{|\mathcal{G}|},$

where the last inequality holds for some numbers $c_{3},c_{4}>0$ and
$\delta<\frac{c_{3}}{|\mathcal{G}|}$. ∎

###  A.2 Proof of Lemma 11

###### Proof of Proposition 6.

Let $\mathcal{G}\leq\mathrm{Sym}\left(\mathcal{X}\right)$ be a finite
subgroup. For any $x,x^{\prime}\in\mathcal{X}$ and a constant $\delta>0$, if
there is an action $g\in\mathcal{G}$ such that $\mathcal{D}(g\cdot
x,x^{\prime})<\delta$, then $\mathcal{D}(x,g^{-1}\cdot x^{\prime})<\delta$. ∎

###### Proof of Proposition 9.

If $\mathrm{N}(i,\delta)=\\{i\\}$ then it is a clique. Now, assume that
$\mathrm{N}(i,\delta)$ consists of at least 2 points of $V$. Let
$j,j^{\prime}\in\mathrm{N}(i,\delta)$, that is, there exists
$g_{1},g_{2}\in\mathcal{G}$ such that

$\begin{cases}\mathcal{D}(j,g_{1}\cdot i)<\delta,\\\
\mathcal{D}(j^{\prime},g_{2}\cdot i)<\delta.\end{cases}$ (16)

Applying the inverse action $g_{1}^{-1},g_{2}^{-1}$ to the left-hand side of
the above equations, given the fact that $g_{1}^{-1},g_{2}^{-1}$ are
isometries, we have

$\begin{cases}\mathcal{D}(g_{1}^{-1}\cdot j,i)<\delta\\\
\mathcal{D}(g_{2}^{-1}\cdot j^{\prime},i)<\delta.\end{cases}$ (17)

Therefore, we obtain the following:

$\displaystyle\mathcal{D}(j,(g_{1}\cdot g_{2}^{-1}\cdot j^{\prime}))$
$\displaystyle=\mathcal{D}(g_{1}^{-1}\cdot j,g_{2}^{-1}\cdot j)$
$\displaystyle\leq\mathcal{D}(g_{1}^{-1}\cdot j,i)+\mathcal{D}(g_{2}^{-1}\cdot
j,i)<2\delta.$

Therefore, $(j,j^{\prime})\in E_{2\delta}$. As this holds for any arbitrary
pair in $\mathrm{N}(i,\delta)$, it follows that $\mathrm{N}(i,\delta)$ is a
clique of $G_{2\delta}$. ∎

###### Proof of Lemma 11.

As $\mathbf{D}$ is a fundamental domain for the group $\mathcal{G}$ in
$\mathcal{X}$, for any $x\in\mathcal{X}$, there is a group element
$g\in\mathcal{G}$ such that $g\cdot x\in\overline{\mathbf{D}}$. Besides, since
$V_{\overline{\mathbf{D}}}$ is $\delta$-net of $\overline{\mathbf{D}}$, there
must exist $i\in V_{\overline{\mathbf{D}}}$ such that $\mathcal{D}(i,g\cdot
x)<\delta$, that is, $x\in\mathrm{N}(i,\delta)$. Therefore, we have

$V=\bigcup_{i\in V_{\overline{\mathbf{D}}}}\mathrm{N}(i,\delta).$

Now, for each $i\in V$, by Lemma 9, $\mathrm{N}(i,\delta)$ forms a clique in
$G_{2\delta}$. Therefore, by Lemma 5, there are some constants
$c_{1}>0,c_{2}>0$ such that for $0<\delta<c_{2}/|\mathcal{G}|$, we have

$\chi(G_{2\delta})\leq|V_{\overline{\mathbf{D}}}|\leq\frac{c_{1}\delta^{-d}}{|\mathcal{G}|}.$

∎

##  Appendix B Regret Upper Bound of UniformMesh-N algorithm

To prove Theorem 12, we first begin with the following lemmas.

######  Lemma 15.

Consider the optimal node $x$ in $V$. For all $t\in[n]$, we have

$\mathbb{P}\left\\{\mathrm{U}(x,t)\leq f^{*}\right\\}\leq t^{-3}.$ (18)

###### Proof.

Let $i^{*}=\arg\max_{i\in V}f(i)$ be an optimal node. Since $V$ is a covering,
under the Lipschitz assumption, we have $f^{*}\leq f(i^{*})+\delta$. As the
lemma holds trivially true when $O(i^{*},t)=0$, we only consider the case
where $O(i^{*},t)\geq 1$. We have

$\displaystyle\mathbb{P}$ $\displaystyle\left\\{\mathrm{U}(i^{*},t)\leq
f^{*}\text{ and }O(i^{*},t)\geq 1\right\\}$ (19)
$\displaystyle\leq\mathbb{P}\left\\{\mathrm{U}(i^{*},t)\leq
f(i^{*})+\delta\right\\}$
$\displaystyle=\mathbb{P}\left\\{\hat{f}(i^{*},t)+\sqrt{\frac{2\log(n)}{O(i^{*},t)}}+3\delta\leq
f(i^{*})+\delta\right\\}$
$\displaystyle=\mathbb{P}\left\\{O(i^{*},t)\hat{f}(i^{*},t)+O(i^{*},t)(2\delta-f(i^{*}))\leq-\sqrt{2O(i^{*},t)\log
n}\right\\}$
$\displaystyle=\mathbb{P}\Bigg{\\{}\sum_{s=1}^{t}(Y_{s}-f(X_{s}))\mathbb{I}_{\\{i^{*}\in\mathrm{N}(X_{s},2\delta)\\}}+\sum_{s=1}^{t}(f(X_{s})+2\delta-f(i^{*}))\mathbb{I}_{\\{i^{*}\in\mathrm{N}(X_{s},2\delta)\\}}$
$\displaystyle\quad\quad\leq-\sqrt{2O(i^{*},t)\log n}\Bigg{\\}}$
$\displaystyle\leq\mathbb{P}\left\\{\sum_{s=1}^{t}(Y_{s}-f(X_{s}))\mathbb{I}_{\\{i^{*}\in\mathrm{N}(X_{s},2\delta)\\}}\leq-\sqrt{2O(i^{*},t)\log
n}\text{ and }O(i^{*}t)\leq 1\right\\},$

where the last inequality is due to $f(X_{s})+2\delta-f(i^{*})>0$ if
$i^{*}\in\mathrm{N}(X_{s},2\delta)$, as (6). Now, let
$O_{j}=\min\\{t:O(i,t)=j\\}$ for $j=1,2,\cdots$, and denote
$\tilde{X}_{j}=X_{O_{j}}$ and $\tilde{Y}_{j}=Y_{O_{j}}$. Now, applying
Hoeffding’s inequality and the union bound for $1<O(i^{*},t)\leq t$, we obtain
the following:

$\displaystyle\mathbb{P}$
$\displaystyle\left\\{\sum_{s=1}^{t}(Y_{s}-f(X_{s}))\mathbb{I}_{\\{i^{*}\in\mathrm{N}(X_{s},2\delta)\\}}\leq-\sqrt{2O(i^{*},t)\log(n)}\right\\}$
(20)
$\displaystyle=\mathbb{P}\left\\{\sum_{j=1}^{O(i^{*},t)}\left(\tilde{Y}_{j}-f(\tilde{X}_{j})\right)\leq-\sqrt{2O(i^{*},t)\log(n)}\right\\}.$

Applying the Hoeffding-Azuma inequality for
$\left\\{\sum_{j=1}^{O(i^{*},t)}(\tilde{Y}_{j}-f(\tilde{X}_{j}))>-\sqrt{2O(i^{*},t)\log(n)}\right\\}$
and taking the union bound for $1\leq O(i^{*},t)\leq t$, we obtain the
following.

$\displaystyle\mathbb{P}$
$\displaystyle\left\\{\sum_{j=1}^{O(i^{*},t)}\left(\tilde{Y}_{j}-f(\tilde{X}_{j})\right)\leq-\sqrt{2O(i^{*},t)\log(n)}\right\\}$
(21)
$\displaystyle\leq\sum_{\tau=1}^{t}\mathbb{P}\left\\{\sum_{j=1}^{\tau}\left(\tilde{Y}_{j}-f(\tilde{X}_{j})\right)\leq-\sqrt{2\tau\log(n)}\right\\}$
$\displaystyle\leq\sum_{\tau=1}^{t}\exp{\left(-2\frac{2\tau\log(n)}{\tau}\right)}$
$\displaystyle\leq\sum_{\tau=1}^{t}n^{-4}\leq n^{-3}\leq t^{-3}.$

∎

######  Lemma 16.

Consider the clique $C\in\mathcal{C}$ such that $\min_{i\in
C}\Delta_{i}>5\delta$. For all $t\in[n]$, and for an integer $l_{c}\geq 1$
such that

$l_{c}\geq\frac{8\log(n)}{\left(\min_{i\in C}\Delta_{i}-5\delta\right)^{2}},$
(22)

for all $i\in C$, we have

$\mathbb{P}\left\\{\mathrm{U}(i,t)>f^{*}\text{ and }T(C,t)>l_{c}\right\\}\leq
tn^{-4}.$

###### Proof.

From (22), we obtain the following.

$\begin{cases}l_{c}\geq\frac{8\log(n)}{(\Delta_{i}-5\delta)^{2}}&\text{$\forall
i\in C$}\\\ O(i,t)\geq T(C,t)\geq l_{c}.\end{cases}$ (23)

Therefore, we have

$\displaystyle\sqrt{\frac{2\log(n)}{O(i,t)}}$
$\displaystyle\leq\sqrt{\frac{2\log(n)}{l_{c}}}\leq\frac{\Delta_{i}-5\delta}{2}.$
(24)

Now, consider

$\displaystyle\mathbb{P}$ $\displaystyle\left\\{\mathrm{U}(i,t)>f^{*}\text{
and }T(C,t)>l_{c}\right\\}$ (25)
$\displaystyle=\mathbb{P}\left\\{\hat{f}(i,t)+\sqrt{\frac{2\log(n)}{O(i,t)}}+3\delta>f(i)+\Delta_{i}\text{
and }T(C,t)>l_{c}\right\\}$
$\displaystyle\leq\mathbb{P}\left\\{\hat{f}(i,t)+\frac{\Delta_{i}-5\delta}{2}+3\delta>f(i)+\Delta_{i}\text{
and }T(C,t)>l_{c}\right\\}$
$\displaystyle=\mathbb{P}\Bigg{\\{}\sum_{s=1}^{t}\left(Y_{s}-f(X_{s})\right)\mathbb{I}_{\\{i\in\mathrm{N}(X_{s},2\delta)\\}}+O(i,t)(f(X_{s})-2\delta-f(i))$
$\displaystyle\quad\quad>O(i,t)\frac{\Delta_{i}-5\delta}{2}\text{ and
}T(C,t)>l_{c}\Bigg{\\}}$
$\displaystyle\leq\mathbb{P}\left\\{\sum_{s=1}^{t}\left(Y_{s}-f(X_{s})\right)\mathbb{I}_{\\{i\in\mathrm{N}(X_{s},2\delta)\\}}>O(i,t)\frac{\Delta_{i}-5\delta}{2}\text{
and }T(C,t)>l_{c}\right\\}.$

Where the last inequality holds since $f(X_{s})-2\delta-f(i)\leq 0$ if
$i\in\mathrm{N}(X_{s},2\delta)$, as (6). Now, let $O_{j}=\min\\{t:O(i,t)=j\\}$
for $j=1,2,\cdots$, and denote $\tilde{X}_{j}=X_{O_{j}}$ and
$\tilde{Y}_{j}=Y_{O_{j}}$. We have

$\displaystyle\mathbb{P}$
$\displaystyle\left\\{\sum_{s=1}^{t}\left(Y_{s}-f(X_{s})\right)\mathbb{I}_{\\{i\in\mathrm{N}(X_{s},2\delta)\\}}>O(i,t)\frac{\Delta_{i}-5\delta}{2}\text{
and }T(C,t)>l_{c}\right\\}$ (26)
$\displaystyle=\mathbb{P}\left\\{\sum_{j=1}^{O(i,t)}\left(\tilde{Y}_{j}-f(\tilde{X}_{j})\right)>O(i,t)\frac{\Delta_{i}-5\delta}{2}\text{
and }T(C,t)>l_{c}\right\\}.$

Applying the Hoeffding-Azuma inequality for
$\left\\{\sum_{j=1}^{O(i,t)}(\tilde{Y}_{j}-f(\tilde{X}_{j}))>O(i,t)\frac{\Delta_{i}-5\delta}{2}\right\\}$
and taking the union bound for $l_{c}<O(i,t)\leq t$, we obtain the following.

$\displaystyle\mathbb{P}$
$\displaystyle\left\\{\sum_{j=1}^{O(i,t)}\left(\tilde{Y}_{j}-f(\tilde{X}_{j})\right)>O(i,t)\frac{\Delta_{i}-5\delta}{2}\text{
and }T(C,t)>l_{c}\right\\}$ (27)
$\displaystyle\leq\sum_{\tau=l_{c}}^{t}\mathbb{P}\left\\{\sum_{j=1}^{\tau}\left(\tilde{Y}_{j}-f(\tilde{X}_{j})\right)>\tau\frac{\Delta_{i}-5\delta}{2}\right\\}$
$\displaystyle\leq\sum_{\tau=l_{c}}^{t}\exp{\left(-\frac{2}{\tau}\left(\tau\frac{\Delta_{i}-5\delta}{2}\right)^{2}\right)}=\sum_{\tau=l_{c}}^{t}\exp{\left(-\frac{1}{2}\tau(\Delta_{i}-5\delta)^{2}\right)}$
$\displaystyle\leq
t\exp{\left(-\frac{1}{2}l_{c}(\Delta_{i}-5\delta)^{2}\right)}$
$\displaystyle\leq tn^{-4}.$

∎

######  Lemma 17.

Suppose that there is a clique covering $\mathcal{C}$ for graph $G_{2\delta}$.
Let $\mathcal{C}_{1}=\left\\{C\in\mathcal{C}\mid\min_{i\in
C}\Delta_{i}>6\delta\right\\}$. Then, the regret of UniformMesh-N satisfies

$\mathbf{R}_{n}\leq\sum_{C\in\mathcal{C}_{1}}\left(8\log(n)\left(\frac{\max_{i\in
C}\Delta_{i}}{(\min_{i\in C}\Delta_{i}-5\delta)^{2}}\right)\right)+4\sum_{i\in
V}\Delta_{i}+8n\delta.$ (28)

###### Proof.

The proof consists of three steps.

#### First step.

We need to bound regret of playing a node in a clique $C\in\mathcal{C}_{1}$.
For a clique $C\in\mathcal{C}_{1}$, define
$\hat{\mathbf{R}}_{n,C}=\sum_{t=1}^{n}\sum_{i\in
C}\Delta_{i}\mathbb{I}_{\\{X_{t}=i\\}}$. We have

$\displaystyle\hat{\mathbf{R}}_{n,C}$ $\displaystyle=\sum_{t=1}^{n}\sum_{i\in
C}\Delta_{i}\mathbb{I}_{\\{X_{t}=i\\}}$ (29) $\displaystyle=\sum_{i\in
C}\Delta_{i}\sum_{t=1}^{n}\mathbb{I}_{\\{X_{t}=i\text{ and
}\left({T_{C}(t)\leq l_{c}}\text{ or }{T_{C}(t)>l_{c}}\right)\\}}$
$\displaystyle\leq l_{c}\max_{i\in C}\Delta_{i}+\sum_{i\in
C}\Delta_{i}\sum_{t=1}^{n}\mathbb{I}_{\\{X_{t}=i\text{ and
}{T_{C}(t)>l_{c}}\\}}$

for an integer $l_{c}>1$. Consider the event $\\{X_{t}=i\text{ and
}{T_{C}(t)>l_{c}}\\}$, it follows that

$\displaystyle\mathbb{P}$ $\displaystyle\left\\{X_{t}=i\text{ and
}{T(C,t)>l_{c}}\right\\}$ (30)
$\displaystyle\leq\mathbb{P}\left\\{\mathrm{U}_{i}(t)>\mathrm{U}_{i^{*}}(t)\text{
and }{T_{C}(t)>l_{c}}\right\\}$
$\displaystyle\leq\mathbb{P}\left\\{\left\\{\mathrm{U}_{i}(t)>f^{*}\text{ or
}\mathrm{U}_{i^{*}}(t)\leq f^{*}\right\\}\text{ and
}{T_{C}(t)>l_{c}}\right\\}$
$\displaystyle\leq\mathbb{P}\left\\{\mathrm{U}_{i}(t)>f^{*}\text{ and
}{T_{C}(t)>l_{c}}\right\\}+\mathbb{P}\left\\{\mathrm{U}_{i^{*}}(t)\leq
f^{*}\right\\}$

For the choice $l_{c}$

$l_{c}=\frac{8\log n}{(\min_{i\in C}\Delta_{i}-5\delta)^{2}}+1,$

according to lemmas 15 and 16, one obtains the upper bound as follows.

$\mathbb{P}\left\\{X_{t}=i\text{ and }{T_{C}(t)>l_{c}}\right\\}\leq
nt^{-4}+t^{-3}.$ (31)

Therefore, the regret of playing a clique $C\in\mathcal{C}_{1}$ satisfies

$\displaystyle\mathbf{R}_{n,C}$
$\displaystyle=\mathbb{E}\left[\hat{\mathbf{R}}_{n,C}\right]$ (32)
$\displaystyle\leq\left(\frac{8\log n}{(\min_{i\in
C}\Delta_{i}}-5\delta)^{2}+1\right)\max_{i\in C}\Delta_{i}+\sum_{i\in
C}\Delta_{i}\sum_{t=1}^{n}(nt^{-4}+t^{-3})$
$\displaystyle\leq\left(\frac{8\log n}{(\min_{i\in
C}\Delta_{i}-5\delta)^{2}}+1\right)\max_{i\in C}\Delta_{i}+3\sum_{i\in
C}\Delta_{i}$ $\displaystyle\leq\left(\frac{8\log n}{(\min_{i\in
C}\Delta_{i}-5\delta)^{2}}\right)\max_{i\in C}\Delta_{i}+4\sum_{i\in
C}\Delta_{i}.$

Since we have

$\displaystyle\sum_{t=1}^{n}(nt^{-4}+t^{-3})$
$\displaystyle\leq\sum_{t=1}^{n}n^{-3}+\sum_{t=1}^{n}t^{-2}$
$\displaystyle\leq n^{-2}+\sum_{t=1}^{\infty}t^{-2}\leq
1+\frac{\pi^{2}}{6}<3.$

#### Second step.

Next, we bound the regret when playing a node not in $\mathcal{C}_{1}$.
Consider a clique $C$ such that $\min_{i\in C}\Delta_{i}\leq 6\delta$. Since
(6) holds for any neighborhood of the graph $G_{2\delta}$, for all $i\in C$,
we have

$\Delta_{i}\leq\min_{i\in C}\Delta_{i}+2\delta\leq 8\delta.$

Therefore, the regret of playing a node in $C$ is simply upper-bounded by
$8\delta n$.

#### Third step.

Taking the sum of regret for playing all the cliques in $\mathcal{C}$, note
that the cliques in $\mathcal{C}$ are disjoint. We obtain the following:

$\begin{aligned}
\mathbf{R}_{n}&=\sum_{C\in\mathcal{C}_{1}}\left(\left(\frac{8\log(n)}{(\min_{i\in
C}\Delta_{i}-5\delta)^{2}}\right)\max_{i\in C}\Delta_{i}+4\sum_{i\in
C}\Delta_{i}\right)+8n\delta\\\
&=\sum_{C\in\mathcal{C}_{1}}\left(\left(\frac{8\log(n)}{(\min_{i\in
C}\Delta_{i}-5\delta)^{2}}\right)\max_{i\in C}\Delta_{i}\right)+4\sum_{i\in
V}\Delta_{i}+8n\delta\end{aligned}.$

∎

######  Lemma 18.

For any constant $\delta>0$, for a clique covering $\mathcal{C}$ of
$G_{2\delta}$, the regret of UniformMesh-N satisfies

$\mathbf{R}_{n}\leq|\mathcal{C}|\frac{64\log(n)}{\delta}+4\sum_{i\in
V}\Delta_{i}+8n\delta.$ (33)

###### Proof.

Let $\mathcal{C}_{1}=\left\\{C\in\mathcal{C}\mid\min_{i\in
C}\Delta_{i}>6\delta\right\\}$. For all $C\in\mathcal{C}_{1}$, we have
$\min_{i\in C}\Delta_{i}-5\delta>\delta$, and $\max_{i\in
C}\Delta_{i}<\min_{i\in C}\Delta_{i}+2\delta$. By Lemma 17, we obtain

$\begin{aligned}
\mathbf{R}_{n}&\leq\sum_{C\in\mathcal{C}_{1}}\left(\left(\frac{8\log(n)}{(\min_{i\in
C}\Delta_{i}-5\delta)^{2}}\right)\max_{i\in C}\Delta_{i}\right)+4\sum_{i\in
V}\Delta_{i}+8n\delta\\\ &\leq
8\log(n)\sum_{C\in\mathcal{C}_{1}}\left(\frac{\min_{i\in
C}\Delta_{i}-5\delta}{(\min_{i\in
C}\Delta_{i}-5\delta)^{2}}+\frac{7\delta}{(\min_{i\in
C}\Delta_{i}-5\delta)^{2}}\right)+4\sum_{i\in V}\Delta_{i}+8n\delta\\\
&=8\log(n)\sum_{C\in\mathcal{C}_{1}}\left(\frac{1}{\min_{i\in
C}\Delta_{i}-5\delta}+\frac{7\delta}{(\min_{i\in
C}\Delta_{i}-5\delta)^{2}}\right)+4\sum_{i\in V}\Delta_{i}+8n\delta\\\ &\leq
8\log(n)\sum_{C\in\mathcal{C}_{1}}\left(\frac{1}{\delta}+\frac{7\delta}{\delta^{2}}\right)+4\sum_{i\in
V}\Delta_{i}+8n\delta\\\
&\leq|\mathcal{C}|\frac{64\log(n)}{\delta}+4\sum_{i\in
V}\Delta_{i}+8n\delta.\\\ \end{aligned}.$

∎

Now, We we proceed to the proof of Theorem 12.

###### Proof of Theorem 12.

Since Lemma 18 holds for any clique covering of graph $G_{2\delta}$, choose a
clique $\mathcal{C}$ such that $|\mathcal{C}|=\chi(G_{2\delta})$. By Lemma 11,
we have that for some constants $c_{1},c_{2}>0$ and
$0<\delta<c_{2}/|\mathcal{G}|$,

$|\mathcal{C}|\leq\frac{c_{1}\delta^{-d}}{|\mathcal{G}|}.$

Plugging this into (33), we obtain

$\displaystyle\mathbf{R}_{n}$
$\displaystyle\leq|\mathcal{C}|\frac{64\log(n)}{\delta}+8n\delta+4\sum_{i\in
V}\Delta_{i}$ (34) $\displaystyle\leq
c_{3}\frac{\log(n)\delta^{-(d+1)}}{|\mathcal{G}|}+c_{4}n\delta+c_{5}\delta^{-d},$

for some constants $c_{3},c_{4},c_{5}>0$, where the third term in the RHS of
the second inequality is due to $|V|=\Theta(\delta^{-d})$.

Choosing

$\delta=\left(\frac{\log(n)}{n|\mathcal{G}|}\right)^{\frac{1}{d+2}}.$ (35)

Since $\delta<c_{2}/|\mathcal{G}|$, we have

$\frac{n}{\log(n)}>c_{6}|\mathcal{G}|^{d+1},$ (36)

for some number $c_{6}>0$. Moreover, as $\sqrt{n}>\log(n)$ for $n>1$, (36) is
satisfied if we choose

$n>c_{7}|\mathcal{G}|^{2d+2},$

for a number $c_{7}>0$. Now, plugging the choice of $\delta$ as (35) into
(34), we obtain

$\displaystyle\mathbf{R}_{n}\leq
a_{1}\left(\frac{\log(n)}{|\mathcal{G}|}\right)^{\frac{1}{d+2}}n^{\frac{d+1}{d+2}}+a_{2}\left(\frac{|\mathcal{G}|}{\log(n)}\right)^{\frac{d}{d+2}}n^{\frac{d}{d+2}},$

for some constants $a_{1},a_{2}>0$.

∎

##  Appendix C Regret Lower Bound for ILB

This section presents a lower bound for the invariant Lipschitz bandit class.
Let $U$ be a $\delta$-packing of the Dirichlet domain $\mathbf{D}$ whose size
is $N^{\mathrm{pack}}(\mathbf{D},\mathcal{D},\delta)$, and $W\subseteq U$ be a
strictly $\delta$-packing of $\mathbf{D}$. The following result is similar to
Lemma 5.

######  Lemma 19.

Given a Dirichlet domain $\mathbf{D}$ for a finite group $\mathcal{G}$, there
are constants $c_{1},c_{2}>0$ such that

$|W|\geq\frac{c_{1}\delta^{-d}}{|\mathcal{G}|}-c_{2}\delta^{-(d-1)}.$ (37)

Moreover, there are numbers $c_{3},c_{4}>0$ such that for $0<\delta\leq
c_{3}/|\mathcal{G}|$, we have

$|W|\geq\frac{c_{4}\delta^{-d}}{|\mathcal{G}|}.$ (38)

###### Proof.

The proof consists of 2 steps.

#### Step 1.

Suppose that $V$ is a $\delta$-packing of $\mathcal{X}$ whose cardinality is
$N^{\mathrm{pack}}(\mathcal{X},\mathcal{D},\delta)$. Now, if we allocate $V$
to $|\mathcal{G}|$ disjoint images of $\mathbf{D}$, denote
$V_{g\cdot\mathbf{D}}^{p}=\\{V\cap g\cdot\mathbf{D}\\}$, it follows that

$\max_{g\in\mathcal{G}}|V_{g\cdot\mathbf{D}}^{p}|\geq\frac{N^{\mathrm{pack}}(\mathcal{X},\mathcal{D},\delta)}{|\mathcal{G}|}.$

Without loss of generality, let the identity group element maximize
$|V_{g\cdot\mathbf{D}}^{p}|$. As $V_{\mathbf{D}}^{p}$ is a set of packing
points in $\mathbf{D}$, it follows that for some number $c_{1}>0$, we have

$|U|=N^{\mathrm{pack}}(\mathbf{D},\mathcal{D},\delta)\geq
V_{\mathbf{D}}^{p}\geq\frac{N^{\mathrm{pack}}(\mathcal{X},\mathcal{D},\delta)}{|\mathcal{G}|}\geq\frac{c_{1}\delta^{-d}}{|\mathcal{G}|}.$

#### Step 2.

By Lemma 5, the number of points in $U$ whose distance to the boundary of the
Dirichlet domain is smaller than $\delta$ is bounded by $O(\delta^{d-1})$.
Formally, $\left|\\{x\in
U\mid\mathcal{D}(x,\partial\mathbf{D})\leq\delta\\}\right|\leq
c_{2}\delta^{-(d-1)}$ for a number $c_{2}>0$. It follows that

$\displaystyle|W|$ $\displaystyle\geq|U|-c_{2}\delta^{-(d-1)}$ (39)
$\displaystyle\geq\frac{c_{1}\delta^{-d}}{|\mathcal{G}|}-c_{2}\delta^{-(d-1)}.$

Moreover, there are some numbers $c_{3},c_{4}>0$ such that for $0<\delta\leq
c_{3}/|\mathcal{G}|$, we obtain

$|W|\geq\frac{c_{4}\delta^{-d}}{|\mathcal{G}|},$

and this completes the proof. ∎

Now, given a strictly $\delta$-packing $W$ of Dirichlet domain $\mathbf{D}$,
for each $i\in W$, define a subset
$\mathbf{C}_{i}=\bigcup_{g\in\mathcal{G}}\mathcal{B}(g\cdot
i,\frac{\delta}{2})$. It is obvious that the members of the collection
$\\{\mathbf{C}_{i}\\}_{i\in W}$ are mutually disjoint.

Define a constant function $f_{0}$, that is, $f_{0}(x)=\frac{1}{3}$ for all
$x\in\mathcal{X}$. For any number $\delta\in(0,\frac{2}{3})$ and for each
$i\in W$, define a function $f_{i}$ as follows:

$f_{i}(x)=\begin{cases}\frac{1}{3}+\frac{\delta}{2}-\mathcal{D}(i,x),&\text{if
$x\in\mathcal{B}(g\cdot i,\frac{\delta}{2}),g\in\mathcal{G}$; }\\\
\frac{1}{3},&\text{otherwise.}\end{cases}$ (40)

We now show that a bandit problem instance with the expected reward function
$f_{i}$ is indeed an instance of ILB problems.

######  Lemma 20.

For each $i\in W$, the function $f_{i}$ satisfies the following:

  1. (i)

$\sup_{x\in\mathbf{C}_{i}}f_{i}(x)-\sup_{x\in\mathcal{X}}f_{0}(x)=\frac{\delta}{2}$,
and $f_{i}(x)-f_{0}(x)\leq\frac{\delta}{2}$ if $x\in\mathbf{C}_{i}$.

  2. (ii)

$f_{i}$ is invariant with respect to the action of the group $\mathcal{G}$.

  3. (iii)

$f_{i}$ is Lipschitz continuous.

###### Proof.

Part (i) is immediately followed by the construction of $f_{i}$ (39).

Next, we prove part (ii). Given a point $i\in W$, and arbitrary point
$x\in\mathcal{X}$, there are two scenarios. First, if $x\notin
g\cdot\mathcal{B}(i,\frac{\delta}{2})$ for all $g\in\mathcal{G}$, then the
expected reward function on the orbit of $x$ is equal to $\frac{1}{3}$.
Second, if $x\in g\cdot\mathcal{B}(i,\frac{\delta}{2})$ for $g\in\mathcal{G}$,
then for any $g^{\prime}\in\mathcal{G}$, we have $g^{\prime}\cdot
x\in\mathcal{B}(g^{\prime}\cdot g\cdot i,\frac{\delta}{2})$. Therefore,

$f_{i}(g^{\prime}\cdot
x)=\frac{1}{3}+\frac{\delta}{2}-\mathcal{D}(g^{\prime}\cdot g\cdot
i,g^{\prime}\cdot x)=\frac{1}{3}+\frac{\delta}{2}-\mathcal{D}(g\cdot
i,x)=f_{i}(x).$

To prove part (iii), we need to show that
$|f_{i}(x)-f_{i}(y)|\leq\mathcal{D}(x,y)$ for arbitrary $x,y\in\mathcal{X}$.
For any arbitrary two points $x,y\in\mathcal{X}$, we consider the following
scenarios.

(1) if both $x,y$ in some balls $\mathcal{B}(g\cdot
i,\frac{\delta}{2}),\mathcal{B}(g^{\prime}\cdot i,\frac{\delta}{2})$. Now, if
$g=g^{\prime}$, that is, $x,y$ is in the same ball $\mathcal{B}(g\cdot
i,\frac{\delta}{2})$, then it is obvious that

$|f_{i}(x)-f_{i}(y)|=|\mathcal{D}(g\cdot i,y)-\mathcal{D}(g\cdot
i,x)|\leq\mathcal{D}(x,y).$

Consider the case where $g\neq g^{\prime}$, given the fact that $\mathcal{X}$
is convex, from any two distinct points $x,y$, we can draw a line segment
$[x,y]$. Since $\mathcal{D}(x,g\cdot i)<\frac{\delta}{2}$,
$\mathcal{D}(y,g\cdot i)>\frac{\delta}{2}$, and given the fact that
$\mathcal{D}$ is Euclidean metric and hence continuous, there must exist a
point $x^{\prime}\in(x,y)$ such that $\mathcal{D}(x^{\prime},g\cdot
i)=\frac{\delta}{2}$ and therefore $f_{i}(x^{\prime})=\frac{1}{3}$. Similarly,
there must exist $y^{\prime}\in(x,y)$ such that
$\mathcal{D}(y^{\prime},g^{\prime}\cdot i)=\frac{\delta}{2}$ and
$f_{i}(y^{\prime})=\frac{1}{3}$. We have

$\displaystyle|f_{i}(x)-f_{i}(y)|$
$\displaystyle=|f_{i}(x)-\frac{1}{3}+\frac{1}{3}-f_{i}(y)|$
$\displaystyle=|f_{i}(x)-f_{i}(x^{\prime})+f_{i}(y^{\prime})-f_{i}(y)|$
$\displaystyle\leq|f_{i}(x)-f_{i}(x^{\prime})|+|f_{i}(y^{\prime})-f_{i}(y)|$
$\displaystyle\leq\mathcal{D}(x,x^{\prime})+\mathcal{D}(y,y^{\prime})$
$\displaystyle\leq\mathcal{D}(x,y).$

Where the last inequality holds as $x^{\prime},y^{\prime}\in[x,y]$.

(2) Consider the case where neither $x$ nor $y$ is in
$\mathcal{B}(g^{\prime}\cdot i,\frac{\delta}{2})$ for
$g^{\prime}\in\mathcal{G}$. Without loss of generality, let
$y\notin\mathcal{B}(g^{\prime}\cdot i,\frac{\delta}{2})$ for all
$g^{\prime}\in\mathcal{G}$ so that $f_{i}(y)=\frac{1}{3}$, and
$x\in\mathcal{B}(g\cdot i,\frac{\delta}{2})$. With the same argument as in
scenario (1), there must exist $x^{\prime}\in[x,y]$ such that
$\mathcal{D}(x^{\prime},g\cdot i)=\frac{\delta}{2}$ and
$f_{i}(x^{\prime})=\frac{1}{3}$. Therefore,

$\displaystyle|f_{i}(x)-f_{i}(y)|$
$\displaystyle=|f_{i}(x)-\frac{1}{3}+\frac{1}{3}-f_{i}(y)|$
$\displaystyle\leq|f_{i}(x)-f_{i}(x^{\prime})|$
$\displaystyle\leq\mathcal{D}(x,x^{\prime})$
$\displaystyle\leq\mathcal{D}(x,y).$

(3) If both $x,y$ do not belong to any $\mathcal{B}(g\cdot
i,\frac{\delta}{2})$ for $g\in\mathcal{G}$, it is trivially true that
$|f_{i}(x)-f_{i}(y)|=0\leq\mathcal{D}(x,y)$.

∎

We adopt the notation style of [18]. Denote the collection $\mathcal{F}$ of
all mean reward functions $\mathcal{X}\rightarrow[0,1]$ that is Lipschitz
continuous and invariant with respect to the action of the group
$\mathcal{G}$. We denote $\mathcal{F}$ as class of all feasible mean reward
functions. Consider the rewards $\\{0,1\\}$, that is, for each for each
$f\in\mathcal{F}$, the probability that the reward corresponding arm $x$ is
$1$ is $f(x)$.

######  Definition 21 ([18]).

Given the set of arms $\mathcal{X}$ and class of all mean reward function
$\mathcal{F}$. An $(k,\varepsilon)$-ensemble is a collection of subsets
$\mathcal{F}_{1},...,\mathcal{F}_{k}\subset\mathcal{F}$ such that there exist
mutually disjoint subsets $C_{1},...,C_{k}\subset\mathcal{X}$ and a function
$\mu_{0}:\mathcal{X}\rightarrow[\frac{1}{3},\frac{2}{3}]$ such that for each
$i=1,...,k$ and each function $f_{i}\in\mathcal{F}_{i}$ the following holds:

  1. (i)

$\mu_{i}\equiv\mu_{0}$ on each $C_{l}$, $l\neq i$;

  2. (ii)

$\sup_{x\in C_{i}}\mu_{i}(x)-\sup_{y\in\mathcal{X}}f_{0}(y)\geq\varepsilon$;

  3. (iii)

$f_{i}(x)-f_{0}(x)<2\varepsilon$ if $x\in C_{i}$.

Now, given a strictly $\delta$-packing of the Dirichlet domain $W$, by Lemma
20, it is clear that $\\{f_{i}\\}_{i\in W}$ is a
$(|W|,\frac{\delta}{2})$-ensemble.

######  Lemma 22 ([18]’s Theorem 5.7).

Consider invariant Lipschitz bandit problems with $\\{0,1\\}$ rewards. Let
$\mathcal{F}_{1},...,\mathcal{F}_{k}\subset\mathcal{F}$ be an
$(k,\varepsilon)$-ensemble, where $k>2$ and $\varepsilon\in(0,\frac{1}{12})$.
Then for any $n\leq\frac{1}{128}k\varepsilon^{-2}$ and any bandit algorithm
there exist at least $\frac{k}{2}$ distinct i’s such that the regret of this
algorithm on any mean reward function from $\mathcal{F}_{i}$ is at least
$\frac{1}{60}\varepsilon n$.

Now, Lemma 22 together with Lemma 19 is sufficient to prove the following
lower bound.

###### Proof of Theorem 13.

By Lemma 19, there exist some constants $c_{1}$ such that for

$\delta\leq\frac{c_{1}}{|\mathcal{G}|},$ (41)

we have

$|W|=\Omega\left(\frac{\delta^{-d}}{|\mathcal{G}|}\right).$ (42)

Consider an arbitrary bandit strategy $\mathcal{A}$. By Theorem 13, suppose
$|W|\geq 2$ and given the fact that $\\{f_{i}\\}_{i\in W}$ is
$(|W|,\frac{\delta}{2})$-ensembles, it follows that for any time horizon $n$
satisfying

$n=\Omega(|W|\delta^{-2}),$ (43)

there must exist an index $i\in W$ such that for expected reward function
$f_{i}$, the regret of this algorithm satisfies

$\mathbf{R}_{n}=\Omega\left(\delta n\right).$ (44)

Substitute (41), (42) into (43) we have

$n\geq\Omega\left(\frac{\delta^{-(d+2)}}{|\mathcal{G}|}\right)\geq\Omega\left(|\mathcal{G}|^{d+1}\right).$
(45)

Now, suppose that $n$ satisfies (45), choose $\delta$ as follows

$\delta=\left(|\mathcal{G}|n\right)^{-\frac{1}{d+2}}.$ (46)

Substitute (46) into (44), we obtain that for
$n\geq\Omega\left(|\mathcal{G}|^{d+1}\right)$, regret of the algorithm
satisfies

$\displaystyle\mathbf{R}_{n}$ $\displaystyle\geq\Omega\left(\delta n\right)$
(47)
$\displaystyle\geq\Omega\left(\left(\frac{1}{|\mathcal{G}|}\right)^{\frac{1}{d+2}}n^{\frac{d+1}{d+2}}\right).$

∎

##  Appendix D Proof of Proposition 4

###### Proof of Proposition 4.

(i) The proof of part (i) is as follows. Since $\mathbf{F}$ is open in
$E^{d}$, $\mathbf{F}\cap\mathcal{X}$ is open in $\mathcal{X}$ with respect to
the subspace topology if $\mathcal{X}$.

(ii) The proof of part (ii) is as follows. Because
$\\{g\cdot\mathbf{F}\\}_{g\in\mathcal{G}}$ are mutually disjoint, so is
$\\{(g\cdot\mathbf{F})\cap\mathcal{X}\\}_{g\in\mathcal{G}}$.

(iii) Part (iii) follows immediately from the fact that both $\mathbf{F}$ and
$\mathcal{X}$ are convex, so their intersection is convex and connected.

(iv) Now, we prove the final part. We have

$\displaystyle\bigcup_{g\in\mathcal{G}}g\cdot\overline{\mathbf{D}}=\bigcup_{g\in\mathcal{G}}g\cdot\overline{\mathbf{F}\cap\mathcal{X}}.$
(48)

Next, we prove that
$g\cdot\overline{\mathbf{F}\cap\mathcal{X}}=\overline{g\cdot(\mathbf{F}\cap\mathcal{X})}$.
Consider the following:

$\displaystyle g\cdot\overline{\mathbf{F}\cap\mathcal{X}}$
$\displaystyle=g\cdot\left\\{\bigcap S\mid
S\supseteq(\mathbf{F}\cap\mathcal{X}),\text{$S$ is closed in
$E^{d}$}\right\\}$ (49) $\displaystyle=\left\\{\bigcap g\cdot S\mid
S\supseteq(\mathbf{F}\cap\mathcal{X}),\text{$S$ is closed in
$E^{d}$}\right\\}.$

Since $g$ is an isometry, $\mathbf{F}\cap\mathcal{X}\subseteq S$ if and only
if $g\cdot(\mathbf{F}\cap\mathcal{X})\subseteq g\cdot S$. Thus, we have

$\displaystyle g\cdot\overline{\mathbf{F}\cap\mathcal{X}}$
$\displaystyle=\left\\{\bigcap g\cdot S\mid
S\supseteq(\mathbf{F}\cap\mathcal{X}),\text{$S$ is closed in
$E^{d}$}\right\\}$ (50) $\displaystyle=\left\\{\bigcap S^{\prime}\mid
S^{\prime}\supseteq g\cdot(\mathbf{F}\cap\mathcal{X}),\text{$S^{\prime}$ is
closed in $E^{d}$}\right\\}$
$\displaystyle=\overline{g\cdot(\mathbf{F}\cap\mathcal{X})}.$

Substitute (50) into (48), we have

$\displaystyle\bigcup_{g\in\mathcal{G}}g\cdot\overline{\mathbf{D}}$
$\displaystyle=\bigcup_{g\in\mathcal{G}}\overline{g\cdot(\mathbf{F}\cap\mathcal{X})}$
(51)
$\displaystyle=\overline{\bigcup_{g\in\mathcal{G}}(g\cdot(\mathbf{F}\cap\mathcal{X}))}$
$\displaystyle=\overline{\bigcup_{g\in\mathcal{G}}(g\cdot\mathbf{F})\cap\bigcup_{g\in\mathcal{G}}(g\cdot\mathcal{X})}$
$\displaystyle=\overline{E^{d}\cap\mathcal{X}}$
$\displaystyle=\overline{\mathcal{X}}=\mathcal{X}.$

Here, the second equality holds due to the interchangeability of a finite
union and closure operator.

∎

##  Appendix E Example of Symmetry Group

In this section, we give examples of symmetry groups to highlight the
importance and challenge of the lemma 5. The difficulty of proving Lemma 5 is
that the Euclidean isometries may admit (uncountably) many fixed points and
non-effective points. Fortunately, using the notion of Dirichlet domain, it
can be shown that all of those fixed and non-effective points lie on the
boundary of the fundamental domain.

######  Example 23.

As an application of Lemma 5, consider the case of when $\mathcal{X}$ is the
3D unit cube $[0,1]^{3}$, and $\mathcal{G}$ is the permutation group that
permuted the coordinates ($|\mathcal{G}|=3!\,=6$). Let us temporarily denote
the coordinate variables by $x,y,z$. Notice that $\mathcal{G}$ fixes the
diagonal of the cube $\\{(x,y,z)\in[0,1]^{3}\mid x=y=z\\}$, and acts non-
effectively at points $\\{(x,y,z)\in[0,1]^{3}\mid(x=y)\vee(x=z)\vee(y=z)\\}$.
Therefore, applying the Lemma 5, we obtain the number of points in the
$\delta$-net $V$ to cover the fundamental domain as
$|V_{\overline{\mathbf{D}}}|\propto\frac{\delta^{-d}}{6}$, when $\delta$ is
small enough.

######  Example 24.

Apart from the group of permutation matrices, we can apply Lemma 5 to any
finite subgroup of $\mathrm{Sym}\left(\mathcal{X}\right)$, for example, where
$\mathcal{X}$ is a regular polytope and $\mathcal{G}$ is symmetry group of a
regular polytope known as the Coxeter group. In particular, consider the case
where $\mathcal{X}$ is a 3D icosahedron whose full symmetry group
$\mathrm{Sym}\left(\mathcal{X}\right)$ is icosahedral symmetry
($|\mathrm{Sym}\left(\mathcal{X}\right)|=532$). Let
$\mathcal{G}=\mathrm{Sym}\left(\mathcal{X}\right)$, then from Lemma 5, we
obtain a reduction in terms of the covering number
$|V_{\overline{\mathbf{D}}}|\propto\frac{\delta^{-d}}{532}$.

##  Appendix F Real-world applications of ILB

An important real-world application of the Lipschitz continuous bandits, which
naturally inherit symmetry, can be found in the context of online matrix
factorization bandits. The online matrix factorization bandit problem, in
turn, has important machine learning applications, such as the interactive
recommendation system [16, 36, 35], and the online dictionary learning problem
[22, 23].

For instance, consider the following matrix factorization-based recommender
systems. Let $R\in\mathbb{R}^{I\times J}$ be user-item rating matrix, where
$I$ and $J$ are the number of users and items, respectively. Assume that there
are $K$ features such that there exits a user-feature matrix
$H\in[0,1]^{I\times K}$ and an item-feature matrix $W\in[0,1]^{J\times K}$
generating the user-item matrix $R$. In particular,

$R\sim\mathrm{Pr}\\{\cdot\mid HW^{\top}\\},$

such that $R=\mathbb{E}[HW^{\top}]$.

Let $n$ be the number of rounds. In each round, the recommender system chooses
a pair $(H^{(t)}$, $W^{(t)})$, then the environment returns a noisy estimation
error whose expectation is as follows

$f(H^{(t)},W^{(t)})=\left\|\mathrm{vec}\left(HW^{\top}\right)-\mathrm{vec}\left(H^{(t)}W^{(t)\top}\right)\right\|,$
(52)

where $\mathrm{vec}$ is the vectorization operator. This problem can be seen
as a simplified version of the recommender system; where in the full version
of the recommender system, the feedback is an entry of the matrix $R$
corresponding to a chosen item and a given user for each round.

For sufficiently large $L$, for any pair $(H,W),(H^{\prime},W^{\prime})$ we
have

$|f(H,W)-f(H^{\prime},W^{\prime})|\leq
L\left\|\mathrm{vec}([H,W])-\mathrm{vec}([H^{\prime},W^{\prime}])\right\|.$
(53)

A crucial observation is that for any pair of matrices $(H^{(t)},W^{(t)})$
chosen in round $t$, the pair $(H^{(t)}\phi,W^{(t)}\phi)$ gives the same
result, where $\phi\in\mathbb{R}^{K\times K}$ is an orthogonal matrix. In
particular,

$H^{(t)}\phi(W^{(t)}\phi)^{\top}=H^{(t)}W^{(t)\top}.$ (54)

Therefore, the reward is invariant with respect to the action of the
orthogonal group $O(K)$ on the pair $(H,W)$. This means that symmetry appears
naturally in the online matrix factorization problem without any assumptions.
In fact, as observed in [20], the appearance of symmetry in matrix
factorization gives rise to infinitely many saddle points in the optimization
landscape, causing a great challenge for an optimization algorithm that is
oblivious to the existence of symmetry.

Let $d=IK+JK$ be the dimension of the set of arms. Note that our regret upper
bound holds for $n>c_{1}|\mathcal{G}|^{2d+2}$, for some $c_{1}>0$. Thus, we
can choose a finite subgroup $\mathcal{G}\subset O(K)$, such that
$|\mathcal{G}|=c_{2}n^{\frac{1}{2d+2}}$ for some $c_{2}>0$. Plugging the
choice of $\mathcal{G}$ into our current regret’s upper bound leads to

$\mathbf{R}_{n}=\tilde{\mathcal{O}}\left(L^{\frac{d}{d+2}}n^{\left(\frac{d+1}{d+2}-\frac{1}{(d+2)(2d+2)}\right)}\right).$
(55)

Note that while the dependence on $L$ is similar to [10], our naive approach
(i.e., direct application of ILB to the problem) is already able to reduce the
growth rate of $n$ by a small factor of $d$ (from
$\tilde{\mathcal{O}}(n^{\frac{d+1}{d+2}})$). This may indicate that the growth
rate of the regret can be further reduced if we also exploit the specific
properties of the matrix factorization problem, not just only the Lipschitz
continuity property (as in the case of naively applying our generic ILB). For
example, by further exploiting the sparsity structure of the matrix
factorization problem, state-of-the-art algorithms can achieve regret bound
$\tilde{\mathcal{O}}(n^{\frac{2}{3}})$ [30, 15] while the known lower bound is
$\Omega({n^{\frac{1}{2}}})$ [15]. We argue that if we combine these techniques
with our ILB model (i.e., by utilising symmetry) can indeed provide further
improvement and thus, provide a matching regret upper bound the matrix
factorization problem.

##  Appendix G Design and Implementation of Algorithm 1

Our algorithm gives a general principle, and its computational complexity
depends heavily on how to represent the set of vertices $V$. With a carefully
designed representation of $V$, we believe that the algorithm can be carried
out efficiently. In particular, since most of the computation burden of
algorithm 1 is to search $N(x,2\delta)$ for each point $z\in\mathcal{G}\cdot
x$, we suggest a design of the data structure along with a search algorithm as
follows.

To design a covering of $\mathcal{X}$ and facilitate searching the location of
a point simultaneously, a tree of coverings structure can be used [9].
Briefly, constructing a tree of coverings is done recursively as follows.

  * $\circ$

Denote node $i$ of the tree at depth $h$ by $\mathcal{P}_{h,i}$.

  * $\circ$

At depth $h=0$, the node corresponds to the original set of arms, that is,
$\mathcal{P}_{0,1}=\mathcal{X}$.

  * $\circ$

At depth $h=1$, we divide $\mathcal{X}$ into two disjoint subsets
$\mathcal{P}_{1,1}$ and $\mathcal{P}_{1,2}$, and continue to split in the next
level $h=2,...$.

  * $\circ$

The partition process must guarantee that at depth $h$ the diameter of
$\mathcal{P}_{h,i}$ must be smaller than $c\rho^{h}$ for some numbers
$\rho\in(0,1)$ and $c>0$; that is, the diameter of the subsets shrinks
geometrically with the depth.

  * $\circ$

The splitting ends when $\rho^{h}<2\delta$, and let $H$ be the depth of the
tree, we store all the nodes at depth $H$ as a representation of $V$.

The details of implementing tree of coverings are referred to [9] as it
requires some extra notation.

Given a tree of coverings, for a point $z\in\mathcal{G}\cdot x$, to
approximately find its neighbor $Z=\\{i\in V\mid\mathcal{D}(i,z)<\epsilon\\}$,
we can search which node at depth $H^{\prime}$ to which $z$ belongs, where the
diameter of the nodes at depth $H^{\prime}$ is at most $2\epsilon$. Then we
can take its successors as $Z$. The search process takes at most
$\mathcal{O}\left(d\log\left(\delta^{-1}\right)\right)$.

Therefore, in each round, only
$\mathcal{O}\left(|\mathcal{G}|d\log\left(\delta^{-1}\right)\right)$ is
required to search $\mathrm{N}(x,\epsilon)$. Although it is not exact
$\mathrm{N}(i,\epsilon)$, it can be surpassed by adding an additional factor
of $\epsilon$ to the confidence bound to ensure that the estimate is
optimistic. This factor will appear in regret as a multiplicative term. We
believe that with a more carefully designed data structure, we can find the
exact $\mathrm{N}(x,\epsilon)$ efficiently. Note that this tree structure was
already used in the Lipschitz bandit literature [9]. Therefore, we conjecture
that the combination of tree-based algorithm with the side observation scheme
may solve both statistical and computational complexity problems
simultaneously.

In conclusion, in contrast to sampling within the fundamental domain, which is
computationally intractable, our algorithm is computationally efficient by
carefully designing the data structure to facilitate searching for the
neighbor of orbits.