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:
- 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 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