Anonymous Bandits for Multi-User Systems

Hossein Esfandiari, Vahab Mirrokni, Jon Schneider

Abstract

In multi-user online learning, personalizing experiences often requires tracking individual user actions, posing significant privacy risks. This paper introduces "Anonymous Bandits," a framework that enforces $k$-anonymity by requiring that reward observations be aggregated from groups of at least $k$ users. We present the first algorithms to achieve sublinear regret in this setting, proving that effective personalization is possible even when individual feedback is obscured.

Introduction

Modern recommendation and advertising systems rely on multi-armed bandit (MAB) algorithms to learn user preferences by observing reactions to specific items. However, this creates a privacy dilemma: to provide a personalized experience, the system must track individual actions, which users may find intrusive or risky.

This work addresses this challenge by extending the bandit framework to satisfy $k$-anonymity. In this model, the system cannot see if a specific user clicked an ad. Instead, it must group at least $k$ users together, show them the same type of ad, and only observe the total number of clicks from that group. The challenge is to learn which arms are best for which users while constrained by this "blurred" feedback.

Methodology

The paper introduces two primary algorithms designed to handle different assumptions about user behavior:

  1. Algorithm 1 (The Clustered Case): Designed for settings where users naturally fall into groups that prefer the same "arms" (items). It uses a Batched Successive Elimination (BaSE) strategy. Instead of updating after every round, it runs in a few large batches. At each stage, it uses a novel Decompose sub-algorithm to partition users into anonymous groups based on their current "active" set of potentially optimal arms.
Algorithm 1: The core low-regret algorithm for anonymous bandits, utilizing batched successive elimination and a decomposition strategy.
  1. Algorithm 2 (The General Case): An Explore-then-commit algorithm for scenarios where no assumptions are made about user clustering. It spends an initial period collecting anonymous feedback through random assignments before committing to the best-performing arms for the remaining time.

A key technical innovation is the feedback-eliciting sub-algorithm. It allows the learner to recover an unbiased estimate of a single user's reward by comparing the total reward of a group of $C+1$ users with the total reward of the same group when that specific user is removed over multiple rounds.

Theoretical Framework and Key Insights

The authors demonstrate that anonymity has a quantifiable cost: the regret (the difference between the algorithm's performance and the theoretical optimum) scales with the anonymity parameter $C$. Higher privacy requirements lead to slower learning.

  • The User-Cluster Assumption: Learning is significantly more efficient if we assume that for every arm, there is a minimum number of users ($U$) for whom that arm is optimal. This allows the system to form anonymous groups more easily.
  • Geometric Rounding for Privacy: The authors use the concept of an "Anonymity Polytope" and Caratheodory’s theorem to transform a desired (but non-anonymous) user-to-arm assignment into a collection of deterministic, $C$-anonymous assignments.

Key Results

  • Near-Optimal Regret: For the clustered case, Algorithm 1 achieves a regret of $\tilde{O}(NC\sqrt{\alpha KT})$. The authors prove a lower bound of $\Omega(N\sqrt{CKT})$, showing their algorithm is tight within a factor of $\sqrt{C}$ in this regime.
  • Sublinear Regret without Clusters: Even without the clustering assumption, Algorithm 2 achieves $\tilde{O}(T^{2/3})$ regret. They also prove that a $T^{2/3}$ dependence is fundamentally necessary in this general setting.
  • Simulation Performance: In experiments with 50 users and an anonymity requirement of $C=4$, Algorithm 1 variants (especially those using LP-based decomposition) significantly outperformed the simpler explore-then-commit approach on synthetic datasets (Uniform IID and Linear Models).

Limitations and Future Work

The most efficient algorithm (Algorithm 1) requires a lower bound on the number of users per cluster ($U$). If this assumption is violated, performance degrades. Furthermore, the current model assumes static user preferences. Extending this to "restless" or non-stationary bandits would be a valuable next step. Finally, while $k$-anonymity is practical, combining these grouping techniques with Differential Privacy (DP) noise-addition could provide even stronger privacy guarantees.

Summary updated

Abstract

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.
BibTeX
@inproceedings{esfandiari2022anonymous,
  author = {Hossein Esfandiari and Vahab Mirrokni and Jon Schneider},
  title = {{Anonymous Bandits for Multi-User Systems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=00jwOr7UA4P},
}
Figure