# Anonymous Bandits for Multi-User Systems

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

## Key facts

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

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

- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Distributed Clustering of Linear Bandits in Peer to Peer Networks](https://mlsanity.com/paper/1604.07706/) (2016)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms](https://mlsanity.com/paper/1606.00911/) (2016)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [Algorithms for Differentially Private Multi-Armed Bandits](https://mlsanity.com/paper/1511.08681/) (2015)
- [On Context-Dependent Clustering of Bandits](https://mlsanity.com/paper/1608.03544/) (2016)
- [Collaborative Learning of Stochastic Bandits over a Social Network](https://mlsanity.com/paper/1602.08886/) (2016)
- [Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?](https://mlsanity.com/paper/1905.12298/) (2019)
- [Data Minimization for GDPR Compliance in Machine Learning Models](https://mlsanity.com/paper/2008.04113/) (2020)
- [Robust Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.03812/) (2020)
- [Parallelizing Thompson Sampling](https://mlsanity.com/paper/2106.01420/) (2021)
- [Batched Thompson Sampling](https://mlsanity.com/paper/2110.00202/) (2021)
- [Design of Experiments for Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2107.09912/) (2021)
- [k-Anonymity in Practice: How Generalisation and Suppression Affect Machine Learning Classifiers](https://mlsanity.com/paper/2102.04763/) (2021)
- [Bounded regret in stochastic multi-armed bandits](https://mlsanity.com/paper/1302.1611/) (2013)
- [Multi-User Multi-Armed Bandits for Uncoordinated Spectrum Access](https://mlsanity.com/paper/1807.00867/) (2018)
- [Dynamic Spectrum Access using Stochastic Multi-User Bandits](https://mlsanity.com/paper/2101.04388/) (2021)

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

- [PIIvot: A Lightweight NLP Anonymization Framework for Question-Anchored Tutoring Dialogues](https://mlsanity.com/paper/2505.16931/) (2025)

## Abstract (arXiv)

In this work, we present and study a new framework for online learning in systems with multiple users that provide user anonymity. Specifically, we extend the notion of bandits to obey the standard k-anonymity constraint by requiring each observation to be an aggregation of rewards for at least k users. This provides a simple yet effective framework where one can learn a clustering of users in an online fashion without observing any user's individual decision. We initiate the study of anonymous bandits and provide the first sublinear regret algorithms and lower bounds for this setting.