Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the problem of multi-armed bandits under the shuffled model of DP. The authors provide two algorithms, one of which almost matches the regret of the best known algorithms for the centralized model. To do so, they give a variant of the arm elimination algorithm that leverages the private summation algorithm by Cheu et al. [9] and uses exponentially growing batches. 
main_review: The paper is well written. It is easy to follow and read through, and it addresses a timely and important topic in our community. It's interesting to see that one can immediately get an optimal (up to log(T) factor) algorithm under the shuffled model of DP. 

That said, the paper does not present any fundamentally new algorithms or analyses and does not provide any experimentation or analyses for things other than regret (e.g. communication efficiency: number and length of messages to be shuffled). The shuffled model of DP has been (almost fully) solved for several canonical problems: summation, histograms, convex optimization, etc. And it seems that one can simply just apply the shuffled algorithms in those canonical settings as a black-box to get a "good enough" algorithm for other problem domains (like the one studied in this paper). From that perspective, it is unclear how novel or deep these attempts are. 
limitations_and_societal_impact: 1. The main limitation of this work stems from the lack of algorithmic novelty and lack of depth in the provided proofs. The solution seems to be largely a mix and match of known results (applying the private summation protocol as a black-box to the arm elimination algorithm with very little changes). I think shaving the log(T) term would have been interesting since it does not seem as straightforward. 

2. Since the algorithms are not as novel, I would have expected/hoped that the authors give other types of analyses (e.g. analyzing communication costs or implementation issues related to shuffling and conducting extensive experiments).
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors give a differentially private algorithm for the Multi-Armed Bandit (MAB) problem in the shuffle model. The algorithm attains similar privacy guarantees to the local model, but has almost matched regret bounds compared to the best known centralized model. 
main_review: - The paper is well written, I can quickly get the contributions of this work. Although I didn't follow the state-of-the-art in private MAB well, based on what the authors summarize I think this is a good work to the community. This also makes me find the shuffle model interesting. In the private MAB setting, this model somehow achieves the best-of-both-world: having similar privacy as local models while having similar regret as centralized models. The model seems very promising and is worthy of further investigation in the future.  
- My main question/confusion is about the batches. Specifically, the regret definition above Line 130 is confusing. First, the definition of B is not very clear to me. It doesn't appear in the algorithm (but the authors say it is used by the algorithm during its run) or elsewhere, so it is a little bit hard for me to relate. A formal definition and more explanation to it would be helpful. Additionally, I assume $\mathbb{E}[\sum_{b\in B}\sum_{i\in b}r_i]$ corresponds to the accumulated reward of the learner but why is there no dependence on T? And why does the last equality hold? I think there are more explanations required there.   
- Related to the last comment, I think the role of batches should be better explained. It seems that in the standard online learning problems, we have m=1. But in this paper the authors set something specific in the first algorithm and even make it time-varying in the second algorithm. Is this a parameter that the algorithm can set arbitrarily? What does it mean in the real applications? I think these are something the authors may clarify. 
- In footnote 6, the authors claim that their method also works for UCB. Then how about the regret bounds? Why do authors end up choosing arm elimination based algorithms instead of UCB based?
- In the caption of Table 1, where is LB?

=========

I thank the reviewer for the detailed responses. Now I have a better understanding of the shuffle model. After reading all the review and the author responses, I share a similar concern with other reviewers regarding the algorithmic novelty. It seems like the main algorithmic contribution is basically introducing the exponentially growing batch size (non-trivial) to improve the regret. Although this idea and the analysis are non-trivial, the overall contributions are slightly weaker than I thought. I decrease my score accordingly, but I still tend to recommend  the acceptance. 


limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes multi-armed bandit algorithms that are differentially private in the shuffle model.
For the proposed algorithms,
a gap-dependent regret bound and a distribution independent regret bound,
which are better than known regret bounds achieved by exsiting algorithms that are differentially private in the local model.
main_review: Originality:

This is the first work that consider bandit problems under the shuffle model of differential privacy.
The proposed algorithms heavily rely on a well-known arm elimination approach and 
a private binary summation mechanism in the shuffle model.
Given these two existing framework,
the proposed algorithms appear to be natural ones to come up with.


Quality and clarity: 

The paper is clearly written and well organized.

Significance:

Given a private binary summation mechanism with $\tilde{\Theta}(1 / \varepsilon)$-error in the shuffle model,
the results of the proposed multi-armed bandit algorithms and theoretical analysis are not very surprising.
On the other hand,
the work steadily advances the research area of optimal trade-offs between privacy and decision-making efficiency.
It would be better if there was a detailed explanation of why the shuffle model is important in the context multi-armed bandit problems.

limitations_and_societal_impact: I think limitations and societal impact have been well discussed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a shuffle model of DP for multi-armed bandits. The paper proposes two algorithms, SDP-AE and VB-SDP-AE, for bandits with shuffle DP and Bernoulli rewards. Distribution-dependent and independent regret bounds are derived for both the algorithms. VB-SDP-AE achieves additive regret due to privacy which has same order of dependence on $\epsilon$ but logarithmically worse dependence on $T$ than centralised DP.
main_review: Originality:
This paper is the first to propose shuffled DP for multi-armed bandits with Bernoulli rewards. It incrementally proposes two algorithms for SDP model and also provides theoretical analysis to support their efficiencies and shortcomings. This allows us to find an alternative model of DP which can have future applications.

Quality:
+ The submission is technically sound. The definitions and the setup are clear. The bounds and proves are also understandable enough.
+ The intermediate nature of SDP wrt LDP and centralised DP is clear from Table 1 and following discussions.
- But lack of lower bound makes it questionable whether it is an artefact of the algorithm or fundamentally unavoidable. A discussion on that or a lower bound will really help.
- The paper lacks experimental evaluation of the SDP algorithm against LDP and centralised DP algorithms. DP is a practical problem and the SDP model proposed is an interesting alternative. Though this is a generic problem of this category of papers, an experimental analysis (even in a simple synthetic setup) does not only firms the claims but also increases its applicability.
+ The algorithms proposed in this paper are novel and add new techniques merging private bandits and SDP.
+ In general, the authors compare it well with existing problem-dependent bounds for private bandits. They also discuss the strength and weakness against them.
- Though the authors have problem-independent bounds, there's no discussion along this line. There are multiple existing upper and lower minimax bounds in literature for both local and centralised DP in bandits. A discussion is needed to clarify how much SDP gets in both worst-case and problem-dependent domains.
- Another issue is that often the problem-dependent lower bounds in private bandits assume $O(1/\Delta_a)$ as the optimal problem dependent factor. But in bandit literature, it is long known that this dependence is suboptimal and the problem dependent factor should be $O(1/KL(R_a||R^*))$. This does not lessen the algorithm design or contribution but stating it clearly and using such existing bounds in private bandit literature rigorously clarifies the gaps in literature.


Clarity:
+ The contributions of the papers and the problem setup are clear. 
+ In general the write-up is smooth and easy to follow.
- Line 189-190: It is not really trivial for a reader from bandit community or even no experience with shuffled DP. It should be explained a bit more explicitly and rigorously even if it requires stating existing results.
- It would be very helpful for a reader if a running example is used to explain SDP.  Authors can probably extend the accessible example in introduction (line 22-28).


Significance:
This introduces a new way of ensuing DP in bandits. Though it is presently limited to Bernoulli rewards,  extensions to practical settings with experimental evaluations can become useful.
limitations_and_societal_impact: 1. The paper in general talks about the weakness and strength of their bounds against that of centralised and local DP respectively. But it should also remind the reader that this is limited to Bernoulli reward only. In lines 63-64, it is loosely mentioned that it can be extended to continuous case but it should be discussed a bit more in details.
2. The paper does not have a lower bound for shuffled DP model. Thus, it is worth mentioning that suboptimality of SDP here is unknown though it is compared with global and local DPs.
review_title: null

Meta-review: The paper considers the problem of differentially private multi-armed bandits which has been well-studied both in the local as well as global DP model. The paper proposes to study the recently popular shuffled model of privacy. The paper analyses two settings keeping a fixed batch and an exponentially increasing batch size showing the precise regret dependence with privacy loss. The latter algorithm with the increasing batch size represents the primary algorithmic contribution of the paper - the reviewers (after some discussion and a mixed verdict) agreed that the idea/analysis is non-trivial and somewhat novel as well as the fact that the same results as global DP can be achieved is a strength of the approach. 

I would like to point out that the paper's technical contribution is primarily in the space of multi-armed bandits and the privacy aspect is merely the part that actually defines the entire setup. Overall the paper contains some novel ideas and the algorithm/results are useful in general again in the space of multi-armed bandits. The authors should discuss the shuffle model better though and discuss the practical privacy impacts of their algorithm - in particular the exponentially increasing batch size, if they wish to make this paper more useful to their targeted application which is privacy. 

Overall the reviewers agree on the paper's contributions being (close to) but above the borderline for acceptance and that forms the rationale behind my recommendation. 
Decision: Accept (Poster)