Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

The 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} )$.
strengths_and_weaknesses: Strenghts
- The paper is well written and easy to follow
- The authors give a thorough treatment of the problem with algorithms, numerical experiments, regret upper bounds and lower bounds
- 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.

Weaknesses
- **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
$$
X = \\{ x \in \\{0,1\\}^{N \times K} :  \sum_{i \in [N]} x_{i,j} \ge C \\;\\;\\; \forall j  \\} \subset \\{0,1\\}^{N \times K}
$$
the 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
$$
        \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}
$$
where $Z_{i,j}$ are $1$ sub-gaussian with mean $0$. The reward can be rewritten as
$$
      {1 \over \sqrt{N K}} \sum_{i \in [N]} \sum_{j \in [K]} x_{i,j} \mu_{i,j} + W
$$ 
where $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. 

- **Definition of regret** The authors define the regret as
$$
T \sum_{i \in [N]} \max_{j \in [K]} \mu_{i,j} - \sum_{t \in [T]} \sum_{i \in [N]} E(  r_{i,t} ) 
$$
This 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):
$$
T \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}) 
$$
where 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).




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 ?
- If one were to use a modified definition of regret, would the proposed results significantly change ? 


limitations: See above.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

strengths_and_weaknesses: Strengths
The 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. 

The 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.

Weakness
I 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.
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?

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

Q3: Could you please make sure there is a consistency in how you list the references and adding hyperlinks to the file.

Q4: Could you provide a simple example of a U-batched graph? I think this would help with the presentation 

Q5: You tried different anonymous decomposition algorithms. Is there one that would be more "better" than other? or is it irrelevant?

Minor suggestions

Line 67: Notation $\tilde{O}$ is used before it is defined. 

Line 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?
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

The 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.

This 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. 


strengths_and_weaknesses: Strengths:
1. The problem setup is well-motivated in the introduction with the example of displaying online advertisements to users.
2. This paper is well-written and easy to follow.
3. Related work is covered in detail.
4. 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). 

Weaknesses:
1. 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.
2. 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.
3. 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})$?
questions: Please address the concerns in the weaknesses of the paper in as much detail as possible.

Minor comments:
1. Inconsistent notation: please replace $n$ with $N$ for the number of users (for example, in pseudocode of Algorithm 1)
2. In line 215, shouldn't $j^*(i) = \arg \max_{j} \mu_{i, j}$?
3. 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).
4. 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
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

Their 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.
Also, 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$.   

They 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.

strengths_and_weaknesses: **Strengths**
- The problem setting with k-anonymity seems to be novel in bandit research

- They provide regret lower bounds for this problem and propose algorithms with regret analysis by achieving tight regret bounds.

**Weakness**
- 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.

[1] Shariff, Roshan, and Or Sheffet. "Differentially private contextual linear bandits." Advances in Neural Information Processing Systems 31 (2018).


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

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.

- I was wondering whether the suggested algorithm with the anonymity polytope method can achieve Theorem 1.
 
- Could you explain how the approximation ratio $\alpha(C,U)$ can be measured?

limitations: - It would be better to discuss the gap between the regret upper and lower bound such as where does this gap come from? 
- It would be better to explain the approximation ration $\alpha(C,U)$ in more detail such as how can we measure this?
review_title: null

Meta-review: metareview: The paper introduces a conceptually new variation of the standard multi armed bandit problem motivated by anonymity and ensuring privacy of user responses. This is likely to open up a new avenue for research into formulations of sequential decision making involving anonymity constraints. 

The reviewers' opinions were insightful, including a pertinent comment on the connection to casting the framework as a linear (combinatorial) bandit. The reviews were responded to in detail, and finally all the reviewers are unanimous in their positive view of the paper. Thus the paper deserves to be accepted. I request the author(s) to please use the additional page in the final version to discuss the subtleties of the comparison with linear bandits, in order to make this paper more complete in its statement.
confidence: Certain
Decision: Accept