Anonymous Bandits for Multi-User Systems
This addresses privacy concerns in multi-user systems like recommendation engines by enabling learning without individual user data, though it is incremental as it extends bandit algorithms with anonymity constraints.
The paper tackles the problem of online learning in multi-user systems while preserving user anonymity, introducing a framework where observations aggregate rewards from at least k users to ensure k-anonymity, and it provides the first sublinear regret algorithms and lower bounds for this setting.
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.