Anonymous Bandits for Multi-User Systems
Authors: Hossein Esfandiari
Vahab Mirrokni
Jon Schneider
Venue: NeurIPS 2022 Accept (2022)
Keywords: anonymity
multi-armed bandits
online learning

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.

Anonymous Bandits for Multi-User Systems
Hossein Esfandiari
Vahab Mirrokni Google Research mirrokni wwwpokiii@ooool...oooooooo com
Jon Schneider Google Research aschnei@google..o
Google Research
aefandiari@googlee.
Abstract
In this work, present and study 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 & users. This provides a simple yet effective framework where one 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.
Introduction
In many modern systems, the system learns the behavior of the users by adaptively interacting with the users and adjusting to their responses. For example, in online advertisement, a website may show certain type of ads to user, observe whether the user clicks on the ads not, and based on this feedback adjust the type of ads it serves the user. As part of this learning process, the system faces a dilemma between "exploring" new types of ads, which may or may not seem interesting to the user, and "exploiting" its knowledge of what types of ads historically seemed interesting to the user. This concept very well studied in the context of online learning.
In principle, users benefit from a system that automatically adapts to their preferences. However, users may naturally worry about system that observes all of their actions, and worry that the system may use this personal information against them or mistakenly reveal it to hackers or untrustworthy third parties. There therefore arises an additional dilemma between providing better personalized user experience and acquiring the users' trust.
We study the problem of online learning in multi-user systems under a version of anonymity inspired by k-anonymity [Sweeney] 2002). In its most general form, k-amonymity is a property of anonymous data guaranteeing that for every data point, there exist at least i: - 1 other indistinguishable data points in the dataset. Although there exist more recent notions of privacy and anonymity with stronger guarantees (e.g. various forms of differential privacy), k-anonymity is simple and practical notion of anonymity that remains commonly employed in practice and enforced various legal settings Gollstten al. 2021 Saf November 2019 Slijepčević et al. 2021].
To explain our notion of anonymity, consider the online advertisement application mentioned earlier. In online advertisement, when user visits website the website selects type of ad and shows that user an ad of that type. The user may then choose to click on that ad or not, and a reward is paid out based on whether the user clicks the ad or not (this reward may represent either the utility of the user or the revenue of the online advertisement system). Note that the here chosen by the website, and the fact that the website assigns user specific type of ad is not something to hide from the website. However, the decision to click on the ad is made by the user. We intend to protect these individual decisions, while allowing the website learn what general types of ads each user is interested in. In particular, we enforce a form group level C-anonymity on these decisions, by forcing the system group users into groups of at least C' users and to treat each group equally by
intend
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

assigning all users in the same group the same ad and only observing the total aggregate reward (e.g. the total number of clicks) of these users.
More formally, we study this version of anonymity in a simple model of online learning based on the popular multi-armed bandit setting. In the classic (stochastic) multi-armed bandits problem, there is a learner with some number K of potential actions ("arms"), where each arm is associated with an unknown distribution of rewards. each round (for I' rounds) the learner selects an arm and collects a reward drawn from distribution corresponding to that arm. The goal of the learner is to maximize their total expected reward (or equivalently, minimize some notion of regret).
In our mullti-user model, a centralized learner assigns N users to K arms, and each rewards for each user/arm pair are drawn from some fixed, unknown distribution. Each round the learner proposes an assignment of users to arms, upon which each user receives a reward from the appropriate user/arm distribution. However, the learner is only allowed to record feedback about these rewards (and use this feedback for learning) they perform this assignment in a manner compatible with C-anonymity, This entails partitioning the users into groups of size at least C, assigning all users in each group to the same arm, and only observing this group's 's aggregate rewards for this arm. For example, if C' in one round we may combine users 2 and into a group and assign them all to arm 3; we would then observe as feedback the aggregate reward V13 + F23 + T43. where Tsy represents the reward that user experienced from arm j this round. The goal of the learner to maximize the total reward by efficiently learning the optimal action for each user, while at the same time preserving the anonymity of individual rewards users experienced in specific rounds. See Section 2 for more detailed formalization of the model.
1.1
Our results
In this paper we provide low-regret algorithms for the anonymous bandit setting described above. We present two algorithms which operate in different regimes (based on how users cluster into their favorite arms):
If for each arm j there are at least 2 C+1 users for which arm j that user's optimal arm,
then Algorithm incurs regret at most O(NCVaKT), where a = max(11 K (C++))UUU)
If there no such guarantee (but N > C), then Algorithm incurs regret most
0(C2/9K1/372/3)
We additionally prove the following corresponding lower bounds:
We show (Theorem 3) that the regret bound of Algorithm i is tight for any algorithm to within factor of K VC (and to within factor of VC for U K(C 1)).
We show (Theorem 4 that the dependence on 72/3 in Algorithm is necessary in the absence of lower bound on U.
The main technical contribution of this work is the developmeen/anallyiis of Algorithm The core idea behind Algorithm[Tis is to use recent algorithms developed for the problem of batched bandits (where instead of I' rounds of adaptivity, users are only allowed B < T rounds of adaptivity) reduce this learning problem to a problem in combinatorial optimization related to decomposing a bipartite weighted graph into a collection of degree-constrained bipartite graphs. We then use techniques from combinatorial optimization and convex geometry to come up with efficient approximation algorithms for this combinatorial problem.
1.2 Related work
The bandits problem has been studied for almost century [Thompson] 1933]
and it has been extensively studied the standard single user version [Audibert et al. 2009a bl Audibert and Bubeck]
2010 et al. 2002 Auer and Ortner 2010 Bubeck et 2013 Garivier and Cappé [011] Lai and
Robbins [985] There exists recent work on bandits problem for systems with multiple users [Bande
and Veeravalli 2019a b Bande et al. 2021 Vial et al. 2021 Buccapatnam et al. [015 Chakraborty
et al., 2017 Kolla al. 2018 Landgren et al. [016]] Sannaaaraaann et al. 2019 These papers
study this problem from game theoretic and optimization perspectives (c.g. studying coordination! /

---

competition between users) and do not consider anonymity. To the best of our knowledge this paper the first attempt to formalize and study multi-arma bandits with multiple users from an anonymity perspective.
Learning how to assign many users (relatively) small set of arms can also be thought of
clustering problem. Clustering of users in multi-user multi-arm bandits has been previously studied. Maillard and Mannor [014] first studied sequentially clustering users, which was later followed up
by other researchers Nguyen and Lauw 2014 Gentile et al. 2017 Korda et al. 2016]. Although these works, similar to us, attempt to cluster the users, they are allowed to observe each individual's reward and optimize based on that, which contradicts our anonymity requirement.
One technically related line of work that we heavily rely is recent work on batched bandits. In the problem of batched bandits, the learner is prevented from iteratively and adaptively making decisions each round; instead the learning algorithm runs in small number of "batches", and in each batch the learner chooses a set of arms to pull, and observes the outcome at the end of the batch. Batched multi-armed bandits were initially studied by Perchet et al. (2016) for the particular case of two arms. Later Gao et al. [211 studied the problem for multiple arms. Esfandiari et al. [2019] improved the result of Gao et al. and extended it linear bandits and adversarial multi-armed bandits. Later this problem was studied for batched Thompson sampling (Kalkanli and Ozgur 2021 Karbasi et al.
2021 Gaussian process bandit optimization [i and Scarlett 2021 and contextual bandits (Zhang
et al. 2021 Zanette et al. [2021].
In another related line of work, there have been several successful attempts apply different notions of privacy such as differential privacy to multi-armed bandit settings TTosoou and Dimitrakakis) 2016 Shariff and Sheffer 2018 Dubey and Pentland 2020 Basu et al. 2019]. While these papers provide very promising guarantees of privacy measures, they focus on single-user settings. In this work we take advantage of the fact that there are several similar users in the system, and use this provide
guarantees of anonymity. Anonymity and privacy go hand in hand, and in a practical scenario, both lines of works can be combined provide higher level of privacy.
Finally, our setting has some similarities to the settings of stochastic linear bandits [Dani et al., 20088
Rusmevichientong and Tsitsiklss 2010 Abbasi- Yadkori et al. 201I] and stochastic combinatorial
bandits [Chen et al. [013] K Kveton et al. 2015]. For example, the superficially similar problem of assigning N users K arms each round that each arm has at least C users assigned to it (and where you get to observe the total reward per round) can be solved directly by algorithms for these frameworks. However, although such assignments are C-anonymous, there are important subtleties that prevent us from directly applying these techniques in our model. First of all, we do not actually constrain the assignment of users arms rather, our notion of anonymity constrains what feedback we can obtain from such an assignment (e.g.. it is completely fine for us to assign zero users to an arm, whereas in the above model no actions are possible when N < CK). Secondly, we obtain more nuanced feedback than is assumed in these frameworks (specifically, we get to learn the reward of each group of 2 C' users, instead of just the total aggregate reward). Nonetheless is an interesting open question if any of these techniques can be applied to improve our existing regret bounds (perhaps some form of linear bandits over the anonymity polytopes defined in Section 3.4.2
2 Model and preliminaries
Notation. We write [N] as shorthand for the set f1.2...., NY.. We write Ō(-) to suppress any poly-logarithmic factors (in N, K, C, or T) that arise. We say a random variable X is 0² subgausssin if the mean-normalized variable Y = X - E[xx satisfies Elexp(sY)) I exp(o² 5² /2) for all E R.
Proofs of most theorems have been postponed to Appendix of the Supplemental Material in interest of brevity.
2.1 Anonymous bandits
In the problem of anonymous bandits, there are N users. Each round (for T rounds), our algorithm must assign each user to one of K arms (multiple users can be assigned to the same arm). If user i plays arm j. they receive reward drawn independently from I-subgaussian distribution Di, with (unknown) mean Pt.j E [0, 1]. We would like to minimize their overall expected regret of our algorithm. That is, if user i receives reward rs in round f, we would like to minimize
3

---

N
Reg T _ 1=1
max Pij
E
Tit
Thus far, this simply describes independent parallel instances of the classic multi-armed bandit problem. We depart from this by imposing an anonymity constraint on how the learner is allowed to observe the users' feedback. This constraint is parameterized by positive integer C' (the minimum group size). In given round, the learner may partition a subset of the users into groups of size at least C. under the constraint that the users within single group must all be playing the same arm during this round. For each group G, the learner then receives feedback the total reward Eieg Ta, received by users in this group. Note that not all users must belong to group (the learner simply receives no feedback on such users), and the partition into groups is allowed to change from round to round.
Without any constraint on the problem instance, it may be impossible achieve sublinear regret (see Section 3.6). We therefore additionally impose the following user-cluster assumption on the users: each arm J the optimal arm for at least U users. Such assumption generally holds in practice (e.g., in the regime where there are many users but only a few classes of arms). This also prevents situations where, e.g., only a single user likes a given arm but it is hard to learn this without allocating at least C' users to this arm and sustaining significant regret. Typically we will take U >> C; when U C' the asymptotic regret bounds for our algorithms may be worse (see Section 3.5
2.2 Batched stochastic bandits
Our main tool will be algorithms for batched stochastic bandits, as described in Gao et al. 2019 For our purposes, a batched bandit algorithm is an algorithm for the classical multi-armed bandit problem that proceeds in B stages ("batches")) where the ith stage has predefined length of Do rounds (with D, T). At the beginning each stage the algorithm outputs a non-empty subset of arms A& (representing the set of arms the algorithm believes might still be optimal). At the end of each stage, the algorithm expects least D' |Aa independent instances of feedback from arm for each j e S; upon receiving such feedback, the algorithm outputs the subset of arms A to explore in the next batch.
In Gao et al. 2019). the authors design a batched bandit algorithm they call BaSE (batched successive- elimination policy); for completeness, we reproduce a description of their algorithm in Appendix [A] When B log log T, their algorithm incurs worst-case expected regret of most Ō (T)). ). In
our analysis, we will need the following slightly stronger bound on the behavior of BaSE:
Lemma 1. Ser = log log T. Let μ = maxje(K] Pj. and for each j E [K] let DS = 4² Hj.
Then for each 1 < < B, we have that:
D, E max 4, ÖVVKT).
JEA,
In other words, Lemma bounds the expected regret in each batch, even under the assumption that we receive the reward of the worst active arm each round (even if we ask for feedback on a different arm).
will also be essential in the analysis that follows that the total number of rounds D, in the 6th batch only depends on b and is independent of the feedback received thus far (in the language of Gao et al. [2019), the grid used by the batched bandit algorithm is static). This fact will let us run several instances of this batched bandit algorithm in parallel, and guarantees that batches for different instances will always have the same size.
Anonymous Bandits
3.1 Feedback-eliciting sub-algorithm
Our algorithms for anonymous bandits will depend crucially on the following sub-algorithm, which allows us to take matching from users to arms and recover (in OCC) rounds) an unbiased estimate

---

of each user's reward (as long as that user is matched to a popular enough arm). More formally, let [ + [K] be a matching from users to arms. We will show how to (in 2C + rounds) recover an unbiased estimate of (1, for each i such that o (-())) C + (i.e. is matched to an arm that at least C other users are matched to).
The main idea behind this sub-algorithm is simple; for each user, we will get sample of the total reward of group containing the user, and sample of the total reward of the same group but minus this user. The difference between these two samples is an unbiased estimate of the user's reward. More concretely, we follow these steps:
1. Each round (for 2C' + 2 rounds) the learner will assign user to arm r(1). However, the partition of users into groups will change over the course of these 2C + 2 rounds.
2. For each arm such that i [i) 2 C + 1. partition the users in π (() into groups of size at least C' + 1 and of size at most 2C Let G1, ....... Gs be the set of groups formed in this way (over all arms j). In each group, order the users arbitrarily.
3. In the first round, the learner reports the partition into groups [G1, G2,..., Gs}. For each group Gs, let r'so be the total aggregate reward for group G, this round.
4. In the kth of the next 2C + rounds, the learner reports the partition into groups {GI.k, G2.::.... Gs,s), where G..k is formed from G, by removing the kth element (if k > [G, then we set ,. G.). Let rs,k Ls, be the total aggregate reward from G, reported this round.
5. If user i is the kth user in G,, we return the estimate (i, -s.00 - -ssk of the average reward for user i and arm (i).
Lemma 2. In the above procedure, (l Mi,r(() and (i,(()) is an O(C)) random variable.
3.2 Anonymous decompositions of bipartite graphs
The second ingredient we will need in algorithm is the notion of an anonymous decomposition of a weighted bipartite graph. Intuitively, by running our batched stochastic bandits algorithm, at the beginning of each batch will obtain demand vector for each user (representing the number of times that user would like feedback on each of the m arms). Based on this, we want to generate a collection of assignments (from users arms) which guarantee that we obtain (while maintaining our anonymity guarantees) the requested amount of information for each user/arm pair.
Formally, represent weighted bipartite graph (representing the number of instances of feedback user i desires from arm j). We will assume that for each i, Σ3 Wi.j 0 (each user is interested in at least one arm). A C-anonymous decomposition of this graph is collection of R assignments M1, M2..... ...., MR from users to arms (i.c., functions from [JV] to [K] that satisfies the following properties:
matrix of non-negative entries Wajj
1. A user is never assigned to an arm for which they have zero demand. That is, if M, = j. then Wi, +0 0.
2. If Mi) = j. and |M,+ > C 1, we say that matching M, is informative for the user/arm pair (i. (Note that this is exactly the condition required for the feedback-eliciting sub-algorithm to output the unbiased estimate pو, when run on assignment M,-) For each user/arm pair (i, j), there must be at least way informative assignments.
The weighted bipartite graphs that concern come from the parallel output of N batched bandit algorithms (described in Section 2.2) and have additional structure. These graphs can be described by positive total demand D and a non-empty demand set A, C. [K] for each user i (describing the arms of interest to user i). If j E A,, then Waj = D/|A,,; otherwise, Wi,j = 0. To distinguish graphs with the above structure from generic weighted bipartite graphs, call such graphs batched graphs.
Moreover, for each user i, let (i) be the optimal arm for user (i)) arg max; pt). In the algorithm we describe in the next section, with high probability, j j"(i) will always belong to
A, Moreover, a user-cluster assumption of U implies that, for any arm j. 1)--1() 2 U. This means that in batched graphs that arise in our algorithm, there will exist an assignment where each
5

---

user is assigned to an arm in A, and each arm j has at least U assigned users. We therefore call graphs that satisfy this additional assumption U-batched graphs. Note that this assumption also allows us to lower bound the degrees of arms in this bipartite graph. Specifically, for each arm j. let
B3 = E [N] j E A.). Then a user-cluster assumption of U directly implies that [By] 2 U.
In general, our goal is to minimize the number of assignments At required in such decomposition (since each assignment corresponds some number of rounds required). We call an algorithm that takes in a U--btthed graph and outputs a C-anonymous decomposition of that graph an anonymous decomposition algorithm, and say that it has approximation ratio (CC.U) 2 if it generates an assignment with at most a U-- D+ (O(KKK) total assignments. This additive O is necessary for technical reasons, but our algorithm, D will always be much larger than K (we will have
D 2 vT), so this can be thought of as an additive o( D) term.
Later, in Section 3.4 we explicitly describe several anonymous decomposition algorithms and their approximation guarantees. In the interest of presenting the algorithm, will assume for now have access to a generic anonymous decomposition algorithm Decompose with approximation ratio U).
3.3 An algorithm for anonymous bandits
We are now ready to present our algorithm for anonymous bandits. The main idea behind this algorithm (detailed in Algorithm D is as follows. Each of the N users will run their own independent instance of BaSE with B = log log T' synchronized batches. During batch b, BaSE requires each user to get total of D, instances of feedback a set A., of arms which are alive for them. These sets Ar,o (with high probability) define a U-batched graph, so we can use an anonymous decomposition algorithm to construct C-anonymous decomposition of this graph into at most aCC, D, assignments. We then run the seddback-eliciting sub-al all-aggorithm on each assignment, getting one unbiased estimate of the reward for each user/arm pair for which the assignment is informative.
The guarantees of the C-anonymous decomposition mean that this process gives us D& total pieces of feedback for each user, evenly split amongst the arms in A.,. We can therefore pass this feedback along BaSE, which will eliminate some arms and return the set of alive arms for user in the next batch.
Algorithm 1: Low-regret algorithm for anonymous bandits.
Input: Anonymity parameter C, a lower bound on the user-cluster assumption U, time-horizon T. number of users N. and number of arms K. We additionally assume we have access an anonymous decomposition algorithm Decompose with approximation factor a = (CC For each user i E [N]. initialize an instance BaSE with a time horizon of T" -[2C+2] and
B= log log 7 batches. Let D1, D2...., D2 be the corresponding batch sizes (with Dg Dg T"). Let Ar, be the set of active arms for user i during batch
for b + 1 to B do
If D. and (A1, A2,,,,2,5.. A2......... An,,) do not define U'batched graph, abort the algorithm (this means we have eliminated the optimal arm for a user, which can only happen with negligible probability).
Run Decompose on D2 and (A1,s, A2..... An.o) to get a C-anonymous decomposition into at most R₂- = aD, assignments. Let M, be the rth such assignment. for r + 1--10 to Rs do
Over (2C + 2) rounds, run the feedback-solicitin sub- alg-orhtii (Section 3.1 on M, to get estimates (i) for all users for which M, is informative.
end
For each user i, we are guaranteed to receive (by the guarantees of Decompose) at least
Dy independent samples of feedback م for each arm j E As, Pass these samples Azal
user i's instance of BaSE and receive A&8-1 in response (unless this is the last batch).
end
Theorem 1. Algorithm i incurs an expected regret of at most O(NCVaKT) for the anonymous bandits problem.

---

One quick note computational complexity: note that we only rum Decompose once every batch; in particular, at most log log times. This allows us efficiently implement Algorithm [even for complex choices of Decompose that may require solving several línear programs.
3.4 Algorithms for constructing anonymous decompositions
3.4.1 A greedy method
We begin with perhaps the simplest method for constructing an anonymous decomposition, which achieves an approximation ratio (CC,U) K as long U 2 C' +.+ 1. To do this, for each arm j E [K], consider the assignment M, where all users i with j E A (i.c., users with any interest in arm j) are matched arm j. and other users are arbitrarily assigned to arms in their active arm set. Our final decomposition contains D copies of M, for each j E [K] (for total of K D assignments).
Note that since U 2 C + 1, there will be least C users matched to arm in M,, and therefore Mj will be informative for all users with j E A, Since we repeat each assignment times, we will have least D informative assignments for every valid user/arm pair, and therefore this is valid C-anonymous decomposition for the original batched graph.
Substituting this guarantee into Theorem gives us anonymous bandit algorithm with expected regret
3.4.2 The anonymity polytope
As U grows larger than C, is possible to attain even better approximation guarantees. In this section will give anonymous decomposition algorithm that applies techniques from combinatorial optimization to attain the following guarantees:
U 2 K(C + 1), then aCC,U) 1.
If If 1) S < K KCC 1), then a(C,U)= K(C+1) U
To gain some intuition for how this is possible, assume = K(C + 1). and consider the randomized algorithm which matches each user to random arm in A; each turn. expectation, after D rounds of this, user will be matched to each arm j E A, exactly D/|A, times (as user i desires). Moreover, since U K(C + 1), each arm j has at least K(C + 1) candidate users that can match to it. Each of these users matches to arm with probability at least 1/K, so in expectation at least C + 1 users match arm j. and therefore the feedback from arm j informative "in expectation".
The catch with this method is that is possible (and even reasonably likely) for fewer than C+ users to match to given arm j. and in this case receive feedback for user i. While it is possible to adapt this method to work with high probability, this requires additional logarithmic factors in either the user-cluster bound U, and even then has some probability of failure. Instead, we present deterministic algorithm which can exactly achieve the guarantees above by geometrically "rounding" the above randomized matching into a small weighted collection of deterministic matchings.
We define the C-anonymity polytope Pa C N to the convex hull of binary vectors E {0, 1] NN K that satisfy the following conditions:
For each i, E, viy E {0,1): 1}.
For each j. either E, Vij 2 C+1 2;=
We can interpret each such vertex
single assignment in C-anonymous decomposition, where Vy 1 iff we get feedback on the user/arm pair ( (so we must match user to j. and at least
C' + 1 users must be matched to arm j).
Now, for fixed bbatched graph G. w E [0, NxK be the weights of this G normalized by the demand D: so Waj 1/|A, if E A,, and wij = 0 otherwise. It turns out that we can reduce (via Caratheodory's 's theorem) the problem of finding C-anonymous decomposition of G into finding the maximal /3 for which 3w e Pc.
7

---

Lemma 3. for some 3 > O, fw E Pc. then there exists Canooyymous decomposition of G into at most 1D + NK + assignments. Similarly, if there exists a C. Cannonymous decomposition of G into aD assignments, then _ Pc.
In a sense, Lemma provides an "optimal" algorithm for the problem of finding C-anonymous decompositions. There two issues with using this algorithm in practice. The first interesting open question is that we do not understand the approximation guarantees of this decomposition algorithm (although they are guaranteed to be at least as good as every algorithm we present here).
Open Problem 1. For U- U-buicched graph G, let ((G) be the maximum value of B such that Bw E Pc (where w is the weight vector associated with C). What is max 3(G) over all U-batched graphs? Is it ??())?
The second that, computationally, it is not clear if there is an efficient way to check whether a point belongs to Pc (let alone write decompose Pc into the convex hull of a collection of more tractable polytopes; while it will still be hard to e.g. check membership Pc. this will help us efficiently compute decompositions that provide the guarantees at the beginning of this section.
convex combination of the vertices of Pc). We will now
For subset S [K] of arms, let Pc(S) N be the convex hull of the binary vectors that satisfy the following conditions:
For each i, E, 2iy E {0,
If SS, then E, Uij C C.
If j g SSS then Σ, Uij = 0.
By construction, each vertex of Pc appears as a vertex of some Pc(S) and each vertex of (S( belongs to 'Pc. Pe conv((Pc(()
S S [K]]). We now claim that we can write each polytope (S) as the intersection of small number of halfspaces (and therefore check membership efficiently). In particular, we claim that æ E N belongs to Po(S) iff it satisfies the following linear constraints:
0 < Fij 1
ViE [M E [K] [N]
Σ Zij 1
]E[K]
Fij 2 C+ VjES
(1)
Σ
Zij
O,
Vje [K] S.
EE[N]
Lemma 4. point x E N belongs to Pc(S) iff it satisfies the constraints in (I]
We can now prove the guarantees at the beginning of the section. We start with the case where U > K(C + 1). Here we show (via similar logic to the initial randomized argument) that w E Pc([K]).
Lemma 5. Uf 2 K(C + 1). then w (c([)]).
Applying Caratheodory's theorem, we immediately obtain a C-anonymous decomposition from L
Corollary 1. IfU 2 1))+ there exists C-anonymous decomposition into at most D KC+1 assignments. Moreover, it is possible to find this decomposition efficiently.
When C+150 U < K(C + 1), we first arbitrarily partition our arms into a = K(C + 1)/U" blocks S₁ S2,S2,.. Sa of at most U/(C + 1) vertices each. We then show how to write as linear combination of a points, one in each of the polytopes Pc
Lemma 6. There exist points waa) E Pc(S.) for 1 < < a such that w S E w(a)
Likewise, we can again apply Caratheodory's 's theorem to obtain C-anonymous decomposition from Lemmal6
8

---

(C K(C 1). there exists a C-anonymous decomposition into at most +N + assignments, where [K(C+ 1)/07 Moreover, is possible to find this decomposition efficiently.
Corollary 2.
3.5 Settings without user-clustering
The previous algorithms we have presented for anonymous bandits rely heavily on the existence of
a user-cluster assumption U. In this section we present an algorithm (Algorithm 2 for anonymous
bandits which works in the absence of any user-cluster assumption as long as N C. This comes
the cost of slightly higher regret bound which scales T2/3 shall see in Section 3.6 this dependence in some sense necessary.
Algorithm 2: Explore- algorithm for anonymous bandits without user-clustering assumption.
Input: Anonymity parameter C, time-horizon T, number of users N, and number of arms K.
Set I Tap 10C2/3 10C2///1///0 2/333///33 (log N KT)
For each user i E [N] and arm j E [K] initialize two variables nij = and Øij = 0. for r 4- 1 to /Tezp/ + +2] do
Divide [N] arbitrarily into groups GI...., Gs of size (adding all remaining users to
the last group Gs).
For each group Gs. set je = (r mod K).
Run the feedback-elicitnng sub-algorithm on the assignment induced by the groups G2 (where if i G, then क = ja).
for i <- 1 to N do
(i,)(() + (i)) +
(im(1) < (()( + (1) Here (t))()) is the unbiased estimate for (i,=(i) produced by the feedback-elieiting sub-algorithm.
end
end
for remaining roundy do
Match user to arg max, Øzj/ Fig/nig.
end
Algorithm 2 follows the standard pattern of Explore-Thes Then-Coomii algorithms (see e.g. Chapter of Lattimore and Szepesvári (2200). For approximately OTT2/3) rounds, we run the feedback- eliciting sub-algorithm on random assignments from users to arms (albeit ones which to guarantee each arm with any users matched to it has at least C' + I users matched to it), getting unbiased estimates of the means Mi.j- For the remaining arms, we match each user to their historically best-performing arm.
chosen
Theorem 2. Algorithm incurs an expected regret of at most O(NC213 for the anony- mous bandits problem.
3.6
Lower bounds
We finally turn our attention to lower bounds. In all of our lower bounds, we exhibit family of hard distributions over anonymous bandits problem instances, where any algorithm facing problem instance randomly sampled from this distribution incurs at least the regret lower bound in question.
We begin by showing an Q(N lower bound that holds even in the presence of user-cluster assumption (and in fact, even when 2 ((C++)) Since Algorithm incurs most Ô(NC' (TT)) regret for U > K KCC+ 1), this shows the regret bound of our algorithm is tight in this regime up to factor of /C (and additional polylogarithmic factors).
Theorem 3. Every learning algorithm for the anonymous bandits problem must incur expected regret at least D(N C(NCCK' /CKT), even when restricted to instances satisfying U 2 K(C + 1).
We now shift our attention to settings where there is guaranteed user-cluster assumption. We first show that the 2/3) dependency of the algorithm in Section 3.5 is necessary.

---

Theorem 4. There exists family of problem instances satisfying N = C + 1 where any learning algorithm must incur regret at least Q(T2(00).
Finally, we show the assumption in Section 3.5 that N > C' is in fact necessary; if N = C then it is
possible that no algorithm obtains sublinear regret.
Theorem 5. There exists a family of problem instances satisfying C where any learning algorithm must incur regret at least Q2T)).
4 Simulations
Finally, we perform simulations of our anonymous bandits algorithms the explore-then-comii algorithm (Algorithm ( and several variants of Algorithm [ with different decomposition algorithms on synthetic data. We observe that both the randomized decomposition and LP dccomposition based outperform the explore- tee--thenncee then-commit algorithm and the greedy variants of Algoritmm[[ggnificaaaln
decomposition variant, as predicted by our theoretical bounds. We discuss these in more detail in Section B of the Supplemental Material.
10

---

References
Safari privacy overview. Apple, November 2019.
http://////rrrrppppppoooo///ttaa Whtprii_ihateeaaee_____e Nov___ov___________ 2019.pdd
Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits.
Advances in neural information processing systems, 24, 2011.
J.-Y. Y. Audibert and Bubeck. Regret bounds and minimax policies under partial monitoring. The Journal of Machine Learning Research, 11:2785-2836, 2010.
J.-Y. Audibert, S. Bubeck, al. Minimax policies for adversarial and stochastic bandits. In COLT, volume 7, pages 1-122, 2009a.
J.-Y. Y. Audibert, R. Munos, and C. Szepesvári. Exploration-explootaainn tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):1876-1102,22 2009b. 2009b.
P. Auer and R. Ortner. Ucb revisited: Improved regret bounds for the stochastic multi-armed bandit problem. Periodica Mathematica Hungarica, (1(1-))55566 2010.
Auer, N. Desa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
M. Bande and V. V. Veeravalli. Adversarial multi-user bandits for uncoordinated spectrum access. In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4514-4518. IEEE, 2019a.
M. Bande and V. V. Veeravalli. Multi-user multi-armed bandits for uncoordinated spectrum access. In 2019 International Conference on Computing, Networking and Communications (ICNC), pages 653 657. IEEE, 2019b.
M. Bande, A. Magesh, and V. V. Veeravalli. Dynamic spectrum access using stochastic multi-user bandits. IEEE Wireless Communications Letters, 10(5):953-956, 2021.
D. Basu, C. Dimitrakakis, and A. Tossou. Differential privacy for multi-armed bandits: What and what is its cost? arXiv preprint arXiv:1905. 2019.
S. Bubeck, V. Perchet, and P. Rigollet. Bounded regret in stochastic multi-armed bandits. In Conference on Learning Theory, pages 122-134. PMLR, 2013.
Buccaaptnam, Tan, and L. Zhang. Information sharing in distributed stochastic bandits. In 2015 IEEE Conference Computer Communications (INFOCOM), pages 2605-2613. IEEE, 2015.
M. Chakraborty, K. Y. P. Chua, S. Das, and B. Juba. Coordinated versus decentralized exploration in multi-agent mumti-armed bandits. IJCAI, pages 164-170, 2017.
W. Chen, Y. Wang, and Yuan. Combinatorial multi-armed bandit: General framework and applications. In International conference machine learning, pages 151-159. PMLR, 2013.
V. Dani, T. P. Hayes, and S. M. Kakade. Stochastic linear optimization under bandit feedback. 2008.
A. Dubey and A. Pentland. Differentially-privtte federated linear bandits. arXiv preprint arXiv:2010. 11425, 2020.
H. Esfandiari, Karbasi, A. Mehrabian, and Mirrokni. Regret bounds for batched bandits. arXiv preprint arXiv: 1ex.vv::110.4400 04959, 2019.
Z. Gao, Y. Han, Z. Ren, and Z. Zhou. Batched multi-armed bandits problem. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 503-513, 2019.
A. Garivier and O. Cappé. The kl-ueb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pages 359-376. JMLR Workshop and Conference Proceedings, 2011.
C. Gentile, S. Li, P. Kar, Karatzoglou, Zappella, and Etrue. On context-dependent clustering of bandits. In International Conference on Machine Learning, pages 1253-1262, PMLR, 2017.

---

A. Goldsteen, G. Ezov, R. Shmelkin, M. Moffie, and A. Farkash. Data minimization for gdpr compliance machine learning models. Al and Ethics, pages 1-15, 2021.
R. Hoeksma, B. Manthey, and M. Uetz. Efficient implementation of carathéodory's theorem for the single machine scheduling polytope. Discrete applied mathematics, 215:136-145, 2016.
C. Kalkanli and A. Ozgur. Batched thompson sampling. Advances in Neural Information Processing Systems, 34, 2021.
A. Karbasi, V. Mirrokni, and M. Shadravan. Parallelizing thompson sampling. arXiv preprint arXiv:2106.00 06.00120, 2021.
R. K. Kolla, K. Jagannathan, and A. Gopalan. Collaborative learning of stochastic bandits over social network. IEEE/ACM Transactions on Networking, 26(4):1782-1795, 2018.
N. Korda, B. Szorenyi, and S. Li. Distributed clustering of linear bandits in peer to peer networks. In International conference on machine learning, pages 1301-1309. PMLR, 2016.
B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvari. Tight regret bounds for stochastic combinatorial semi-bandits. In Artificial Intelligence and Statistics, pages 535-543, PMLR, 2015.
T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
P. Landgren, V. Srivastava, and N. E. Leonard. Distributed cooperative decision-making in multiarmed bandits: Frequentist and bayesian algorithms. In 2016 IEEE 55th Conference Decision and Control (CDC), pages 167-172. IEEE, 2016.
T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Z. Li and J. Scarlett. Gaussian process bandit optimization with few batches. arXiv preprint arXiv:21 2021.
O.-A. Maillard and Mannor. Latent bandits. In International Conference on Machine Learning, pages 136-144. PMLR, 2014.
T. T. Nguyen and H. W. Lauw. Dynamic clustering of contextual multi-armed bandits. In Proceed- ings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, pages 1959-1962, 2014.
V. Perchet, P. Rigollet, S. Chassang, and Snowberg. Batched bandit problems. The Annals of Statistics, 44(2):660-681, 2016.
P. Rusmevichientong and J. N. Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395 411, 2010.
A. Sankararaman, A. Ganesh, and S. Shakkottai. Social learning in multi agent multi armed bandits. Proceedings of the ACM Measurement and Analysis of Computing Systems, 3(3):1-35, 2019.
R. Shariff and O. Sheffet. Differentially private contextual linear bandits. arXiv:1810.00063 2018.
arXiv preprint
D. Slijepčević, M. Henzl, L. D. Klausner, T. Dam, P. Kieseberg, and M. Zeppelzauer. k-anonymity in practice: How generalisation and suppression affect machine learning classifiers. Computers & Security, 111:102488, 2021. ISSN 0167-4048. doi: http:///doi.or//10011////// 102444 102488. URL http://ssw.....acaaca///////////
L. Sweeney. k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10(05):557-570, 2002.
W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285 294, 1933.
A. C. Tossou and C. Dimitrakakis. Algorithms for differentially private multi-armed bandits. In Thirtieth AAAI Conference Artificial Intelligence, 2016.
12

---

D. Vial, S. Shakkottai, and R. Srikant. Robust multi-agent aame bandits. In Proceedings of the Twenty-secome International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pages 161-170, 2021.
A. Zanette, K. Dong. J. Lee, and E. Brunskill. Design of experiments for stochastic contextual linear bandits. Advances in Neural Information Processing Systems, 34, 2021.
Z. Zhang. X. Ji, and Y. Zhou. Almost optimal batch-regret tradeoff for batch linear contextual bandits. arXiv preprint
2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is primarily a theory paper, and we not foresee any negative societal impacts of this work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] Code for the simulations is included in the Supplemental Material
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [No] The simulations performed in this work were not computationally intensive, so this is not of particular interest (combined, they took about an hour on laptop).
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "yho-9iMHQm_", "reviewer": "Reviewer_f33e", "summary": "The authors study a new multi-armed bandit problem, where there are $N$ users and $K$ arms. At each time $t$, a central entity allocates  each user $i$ to an arm $j$ (several users may be allocated the same arm), and a stochastic 1-subgaussian reward with mean $\\mu_{i,j}$ is obtained. Not all mappings between users and arms are allowed though: for all arms $j$ the number of users allocated to this arm must be greater than a fixed integer $C \\ge 1$.This constraint is used to model a privacy requirement, and represents a relaxed notion of privacy with the standard notion of differential privacy.\n\nThe authors then propose several algorithmic techniques to solve the problem, and provide theoretical regret upper bounds. Let $U$ be the minimal number of users that share the same optimal arm, When $U \\ge C+1$ their algorithm has a regret of $O( N C K \\sqrt{T} )$ and when $U \\ge K(C+1)$ their algorithm has a regret of $O( N C \\sqrt{K T} )$.", "questions": "- Is it possible to compare between the proposed algorithms and linear bandit algorithms applied to this problem, in terms of computational complexity and regret guarantees ?\n- If one were to use a modified definition of regret, would the proposed results significantly change ? \n\n", "limitations": "See above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts\n- The paper is well written and easy to follow\n- The authors give a thorough treatment of the problem with algorithms, numerical experiments, regret upper bounds and lower bounds\n- The idea of exploring relaxed notions of privacy (with respect to differential privacy) seems very important. While differential privacy is theoretically well understood, in many practical settings it is too stringent, and studying other measures of privacy seems critical for practical applications.\n\nWeaknesses\n- **Casting the problem as a linear bandit** Upon close inspection, the problem studied by the authors is a linear bandit (as well as a combinatorial bandit too). To cast the problem as a linear bandit denote by\n$$\nX = \\\\{ x \\in \\\\{0,1\\\\}^{N \\times K} :  \\sum_{i \\in [N]} x_{i,j} \\ge C \\\\;\\\\;\\\\; \\forall j  \\\\} \\subset \\\\{0,1\\\\}^{N \\times K}\n$$\nthe set of available decisions, where $x_{i,j} = 1$ if user $i$ is allocated to arm $j$ and $x_{i,j} = 0$ otherwise, and let the reward obtained by the learner when choosing decision $x$ be\n$$\n        \\sum_{i \\in [N]} \\sum_{j \\in [K]} x_{i,j} \\mu_{i,j} +  \\sum_{i \\in [N]} \\sum_{j \\in [K]} x_{i,j} Z_{i,j}\n$$\nwhere $Z_{i,j}$ are $1$ sub-gaussian with mean $0$. The reward can be rewritten as\n$$\n      {1 \\over \\sqrt{N K}} \\sum_{i \\in [N]} \\sum_{j \\in [K]} x_{i,j} \\mu_{i,j} + W\n$$ \nwhere $W$ is 1-subgaussian with mean $0$. So indeed this is a standard linear bandit (a combinatorial bandit as well) in dimension $N \\times K$, where the set of decisions is $X$, the unknown mean reward vector is ${1 \\over \\sqrt{NK}} \\mu$ and the reward distribution is $1$ subgaussian. Now this implies that any algorithm for linear bandits can be applied to the problem at hand, for instance this implies that one can always obtain regret scaling as $O( N K \\sqrt{T})$, and this should work irrespective of the value of $C$ and $U$, while those numbers play a critical role in the regret upper bounds at hand. \n\n- **Definition of regret** The authors define the regret as\n$$\nT \\sum_{i \\in [N]} \\max_{j \\in [K]} \\mu_{i,j} - \\sum_{t \\in [T]} \\sum_{i \\in [N]} E(  r_{i,t} ) \n$$\nThis is the difference between the reward obtained by an oracle that allocates the optimal arm to each user and the learner. Now I feel that this definition is problematic, in the sense that the oracle is allowed to take actions that cannot be taken by the learner. And indeed, in some regimes, the regret cannot be made sub-linear. It seems to me that it would make more sense to define the regret as (for $X$ see definition above):\n$$\nT \\max_{x \\in X} \\left( \\sum_{i \\in [N]} \\sum_{j \\in [K]} x_{i,j} \\mu_{i,j} \\right) - \\sum_{t \\in [T]} \\sum_{i \\in [N]} E( r_{i,t}) \n$$\nwhere the oracle is only allowed actions that are also  allowed to the learner.  With this definition the regret can always be made sublinear, and indeed, there exists algorithms with sublinear regrets (since the problem is a linear bandit).\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Kyj5fh1eEDx", "reviewer": "Reviewer_1FZP", "summary": "In this paper, the author(s) address a variant of the multi-arms bandit problem. In this setting, there is the need to keep the user's choices anonymous to the learner. In this regard, the author(s) design a feedback-eliciting sub-algorithm that will allow the learner to obtain the user's rewards without revealing the user's choice. Then the authors present an algorithm where each user will run BaSE (Gap et al 2019) independently. \n", "questions": "Q1: It would be useful for completeness if you spelled out that $K\\geq N$. I'm assuming that how big $C, N, K$ are in comparison to each other does not really play an important role in the analysis, does it?\n\nQ2: In your Feedback-eliciting sub-algorithm, one gets a sample of the total reward of a group containing the user, and a sample of the total reward of the same group without that on user. Is How does one know that this is a anonymous procedure; namely, is there no way to reverse-engineer the process and discover the user's choice? I think the steps 1 to 5 and Lemma 2 address this, but could you make it more explicit?\n\nQ3: Could you please make sure there is a consistency in how you list the references and adding hyperlinks to the file.\n\nQ4: Could you provide a simple example of a U-batched graph? I think this would help with the presentation \n\nQ5: You tried different anonymous decomposition algorithms. Is there one that would be more \"better\" than other? or is it irrelevant?\n\nMinor suggestions\n\nLine 67: Notation $\\tilde{O}$ is used before it is defined. \n\nLine 173: development/analysis --> development and analysis", "limitations": "I did not see any specific discussion of limitations or potential negative societal impacts. If I'm mistaken, could you tell me where these are being addressed?\n\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\nThe paper has an interesting setting that is readily applicable to industry. For example, in A/B testing, this set up would protect the anonymity of the choice of the user. In today's world, there is the desire to preserve a certain level of anonymity, which makes this paper's setup both interesting and relevant. \n\nThe authors accomplish several things in the paper: They talk about how to partition the set of users in a way that their choices would remain anonymous. I thought their schemes to produce anonymous decompositions was interesting in their own right as a combinatorial problem. The authors also provide theoretical guarantees backing up the efficiency of their low-regret algorithm for anonymous bandits.\n\nWeakness\nI think this is overall a good paper. I have one minor comment relating to the formatting. There seems to be an inconsistency about how references are cited. Sometimes the author(s) use the format \"[Author(s), year]\" and sometimes \"Author [Year].\" The author(s) might want to consider going through the draft to make sure the references are consistent. There also doe snot seem to be a hyperlink from the references in text pointing to said reference in the bibliography.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GbcPmeCZP0n", "reviewer": "Reviewer_ex8q", "summary": "Authors consider the problem of online learning in multi-user systems under a version of anonymity inspired by $k$-anonymity. In their model, a centralized learner assigns $N$ users to $K$ arms using groups of size at least $C$ (assigning all users in a group to the same arm) and can only observe this group’s aggregate rewards. The goal is to maximize total rewards while at the same time preserving the anonymity of individual rewards from users.\n\nTheir algorithms depend on a sub-algorithm for matching from users to arms and recovering an unbiased estimate of each user’s reward. The key idea is as follows: By getting aggregate rewards from a group (assigned to an arm) including a target user and by getting aggregate rewards from the group excluding the user, they can estimate the mean reward of the user to the arm.\nAlso, their algorithm needs the anonymous decompositions of bipartite graphs in which each entry represents the number of assignments from a user to an arm. The graph needs to be constructed to satisfy that the number of users assigned to an arm is larger than or equal to $C+1$.   \n\nThey propose an algorithm using BaSE algorithm and Decompose for constructing anonymous decomposition. This algorithm achieves $\\tilde{O}(NC\\sqrt{\\alpha KT})$ under the user-cluster assumption $U$. Also, they provide several algorithms for constructing anonymous decompositions. Lastly for the case of the absence of user-clustering assumption, using the explore-then-commit approach with the feedback-eliciting sub-algorithm, they achieve $\\tilde{O}(NC^{2/3}K^{1/3}T^{2/3})$ regret bound.  They provide a lower bound of $\\Omega(N\\sqrt{CKT})$ under the user cluster assumption, and $\\Omega(T^{2/3})$, otherwise.\n", "questions": "- I was wondering whether the $C$-anonymity could preserve the privacy of users. According to the suggested algorithms, they can estimate each mean reward which implies that the algorithms can estimate user preference.\n\n- I was wondering whether the suggested algorithm with the anonymity polytope method can achieve Theorem 1.\n \n- Could you explain how the approximation ratio $\\alpha(C,U)$ can be measured?\n", "limitations": "- It would be better to discuss the gap between the regret upper and lower bound such as where does this gap come from? \n- It would be better to explain the approximation ration $\\alpha(C,U)$ in more detail such as how can we measure this?\n", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- The problem setting with k-anonymity seems to be novel in bandit research\n\n- They provide regret lower bounds for this problem and propose algorithms with regret analysis by achieving tight regret bounds.\n\n**Weakness**\n- I have a concern about whether the problem setting is suitable or not for preserving the privacy of users which is the main motivation of this paper. According to their algorithms, they utilize feedback-eliciting sub-algorithms to estimate mean rewards for user-arm pairs. This implies that the algorithm can recover the mean reward (preference) of each user so that privacy may not be preserved. On the other hand, for example, in the differential private linear contextual bandits [1], bandit algorithms were proposed by adding noise to context and reward information such that the server cannot estimate the mean rewards.\n\n[1] Shariff, Roshan, and Or Sheffet. \"Differentially private contextual linear bandits.\" Advances in Neural Information Processing Systems 31 (2018).\n\n\n- Another concern is that it may not be clear that there exists a method of constructing groups for achieving Theorem1. Even though the authors discuss some methods such as a greedy method and the anonymity polytope, it would be better to discuss clearly whether the anonymity polytope can achieve the result of theorem 1.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2hWOsCDf7ao", "reviewer": "Reviewer_TxQ1", "summary": "This paper studies a new framework for multi-user multi-armed bandits that provides user anonymity. At each round, a centralized learner assigns $N$ users to $K$ arms and the reward for each user-arm pair is drawn from some fixed, unknown distribution. However, the learner can obtain information about the rewards and use it for learning only if the assignment conforms to the notion of $C$-anonymity. This notion requires partitioning the users into groups of size $C$, assigning all users in a particular group to the same arm and only observing the group's aggregate rewards for the assigned arm.\n\nThe goal of this work is to use the aggregated rewards received per arm in each round to minimize the group cumulative regret. In order to do so, the authors proposed regret minimization algorithms in two different regimes: one under the assumption for each arm $j \\in [K]$, there are at least $C+1$ users for which arm $j$ is optimal and the other without this assumption. They also evaluate the tightness of the regret guarantees of the proposed algorithms by providing lower bounds for both regimes.\n\nThis paper uses ideas from batched bandits in Gao et. al. [2019] to reduce the online learning problem at hand to a combinatorial optimization problem involving decomposition of a bipartite weighted graph into a set of degree-constrained bipartite graphs. \n\n", "questions": "Please address the concerns in the weaknesses of the paper in as much detail as possible.\n\nMinor comments:\n1. Inconsistent notation: please replace $n$ with $N$ for the number of users (for example, in pseudocode of Algorithm 1)\n2. In line 215, shouldn't $j^*(i) = \\arg \\max_{j} \\mu_{i, j}$?\n3. In line 222, it should read as follows: a user-cluster assumption of $U$ directly implies that $|B_j| \\geq U$ \"with high probability\" (missing in the current version).\n4. In the numerical results in the appendix, please run the algorithms for at least 30 independent runs for obtaining reasonably tight confidence bounds.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The problem setup is well-motivated in the introduction with the example of displaying online advertisements to users.\n2. This paper is well-written and easy to follow.\n3. Related work is covered in detail.\n4. In the process of obtaining the first non-trivial sub-linear regret guarantees for the anonymous MAB problem, the authors have creatively used the ideas from combinatorial optimization and convex geometry to come up with efficient approximation algorithms for solving the problem of decomposing a bipartite weighted graph into a set of degree-constrained bipartite graphs (which could be of independent interest in the optimization and algorithms community). \n\nWeaknesses:\n1. A potential downside of the applicability of this setting would be in cases where users are not active at all times, and as a result, the learner may not conform to the notion of $C$-anonymity for obtaining feedback about the arms.\n2. As claimed in the paper, the user would like feedback on each of the arms (for example, in lines 194-196). This doesn't seem correct, because the user seems to be a source of data (rather than an agent) in this setting, and it is the learner which requires the feedback about the arms.\n3. The result in Lemma $1$ seems incorrect: shouldn't $D_b . \\mathbb{E}[\\max_{j \\in A_b} \\Delta_j] = \\widetilde{O}(\\sqrt{K D_b})$ instead of $\\widetilde{O}(\\sqrt{K T})$?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept