# Invariant Lipschitz Bandits: A Side Observation Approach

arXiv: https://arxiv.org/abs/2212.07524 · HTML: https://mlsanity.com/paper/2212.07524/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 39 references that are in the map.
- First posted on arXiv 14 Dec 2022.

## Builds on (most cited first, 13 of 13)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Provably Strict Generalisation Benefit for Equivariant Models](https://mlsanity.com/paper/2102.10333/) (2021)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [Improved Generalization Bounds of Group Invariant / Equivariant Deep Networks via Quotient Feature Spaces](https://mlsanity.com/paper/1910.06552/) (2019)
- [From Bandits to Experts: A Tale of Domination and Independence](https://mlsanity.com/paper/1307.4564/) (2013)
- [Online Learning with Feedback Graphs Without the Graphs](https://mlsanity.com/paper/1605.07018/) (2016)
- [Contextual Bandits with Latent Confounders: An NMF Approach](https://mlsanity.com/paper/1606.00119/) (2016)
- [A PAC-Bayesian Generalization Bound for Equivariant Networks](https://mlsanity.com/paper/2210.13150/) (2022)
- [Feedback graph regret bounds for Thompson Sampling and UCB](https://mlsanity.com/paper/1905.09898/) (2019)
- [Online Interactive Collaborative Filtering Using Multi-Armed Bandit with Dependent Arms](https://mlsanity.com/paper/1708.03058/) (2017)
- [Online Low Rank Matrix Completion](https://mlsanity.com/paper/2209.03997/) (2022)
- [Online matrix factorization for Markovian data and applications to Network Dictionary Learning](https://mlsanity.com/paper/1911.01931/) (2019)

## Built on by (most cited first, 1 of 1)

- [Symmetric Linear Bandits with Hidden Symmetry](https://mlsanity.com/paper/2405.13899/) (2024)

## Abstract (arXiv)

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 textttUniformMesh-N, which naturally integrates side observations using group orbits into the textttUniformMesh algorithm (citeKleinberg2005UniformMesh), 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.