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.

In this work, we study active covering, a variant of the active-learning problem that involves labeling (or identifying) all of the examples with a positive label. We propose a couple of algorithms, namely Density-Adjusted Non-Adaptive (DANA) learner and Density-Adjusted Adaptive (DAA) learner, that query the labels according to a distance function that is adjusted by the density function. Under mild assumptions, we prove that our algorithms discover all of the positive labels while querying only a sublinear number of examples from the support of negative labels for constant-dimensional spaces (see Theorems 5 and 6). Our experiments show that our champion algorithm DAA consistently improves over the prior work on some standard benchmark datasets, including those used by the previous work, as well as a couple of data sets on credit card fraud. For instance, when measuring performance using AUC, our algorithm is the best in 25 out of 27 experiments over 7 different datasets.