  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)
optimization, the utilization of symmetries has not been well examined within
the online optimization settings, especially in the bandit literature. As such,
in this paper we study the invariant Lipschitz bandit setting, a subclass of
the Lipschitz bandits where the reward function and the set of arms are
preserved under a group of transformations. We introduce an algorithm named
\texttt{UniformMesh-N}, which naturally integrates side observations using
group orbits into the \texttt{UniformMesh} algorithm
(\cite{Kleinberg2005_UniformMesh}), which uniformly discretizes the set of
arms. 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.
