Anonymous Linear Bandits for Multi-User Systems

摘要

We provide the first anonymity-preserving algorithm for a centralized decision maker in linear bandit-based multi-user systems. Our algorithm employs successive elimination techniques for linear bandits to build an assignment multi-graph (from users to arms) along with a greedy matching algorithm that efficiently allocates the arms to users. We provide lower and upper bounds for this problem, showing that our algorithm is regret optimal up to a √(CK) factor.