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: This work investigates $\epsilon$-global differential privacy for multi-armed bandits. For both stochastic and linear bandits, it derives refined instance-dependent and global lower bounds on the regret for differentially private learning, in that they quantify the burden of privacy in two distinct regimes. Crucially, in the low-privacy regime, the privacy constraint doesn't make the bandits problem any harder. Next, the work formulates a general $\epsilon$-global strategy for stochastic bandits and shows that two algorithms based on it have regret upper bounds with privacy regime patterns like those in the lower bounds. This is confirmed empirically, where the two privacy regimes are evident.
strengths_and_weaknesses: Strengths:
- The paper touches contributes to a very important theme in the context of differential privacy for bandits - the cost of obtaining this privacy - and identifies two distinct regimes of privacy preservation. Empirical results confirm the theory.
- It materializes a simple $\epsilon$-global DP strategy applicable to existing index-based bandit algorithms. This strategy clearly incorporates features that are known/desirable in the context of DP algorithms (e.g. Laplacian noise, private empirical means using little data).

Weaknesses: Please see questions.
questions: 1. It would be useful to clarify either in the abstract or in "Our Contributions" that the regret lower bounds effectively generalize the claims of [1] in generalizing it beyond Bernoulli to general distributions. My point is that there was prior work hinting at distinct regimes of privacy and I think it's a good idea to acknowledge that at the outset.
2. It would be useful to discuss the gap between the lower bounds and the upper bounds for AdaP-UCB and AdaP-KLUCB. If feasible, instance-independent upper bounds would also be useful to have.
3. In Algorithm 1 (line 253), please clarify where $I_a^\epsilon$ comes from. You mention index-based algorithm but never actually define $I_a^\epsilon$.
4. Please fix some minor typos (e.g. "Algortihm") through the manuscript.
limitations: Not applicable.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the regret minimization problem for stochastic (Bernoulli and linear) bandits under the notion of global differentially privacy. This is a thorough study of the problem where the authors propose lower bounds quantifying fundamental problem hardness, an algorithmic framework and upper bound on the regret for the proposed algorithms under this framework. These results are supported by sound numerical findings. Some highlights: 

-- Two sets of lower bound results are provided: problem-dependent and minimax. The key lemma driving these results is a non-trivial extension of Karwa-Vadhan lemma which bounds the differential privacy when the data is generated from non-identical distributions. 

-- The algorithmic developments are novel from a bandit perspective more-so than from a privacy perspective, particularly, the idea of adaptive phases which is the key driver in ensuring the privacy of the algorithm. 

strengths_and_weaknesses: Strengths: 

-- Non-trivial novel theoretical contributions for both lower bound and upper regret bound. Some of the key results (for eg., Theorem 10) could be of independent interest and have wider application. The key implication of the lower bound is the phase transition behavior of bandits depending on the privacy budget. This has implications particularly because in the low-privacy regime, the problem is equivalent to the non-private setting.

-- The general purpose framework proposed for algorithmic design unifies existing bandit algorithms. This is a much deeper contribution than proposing and analyzing a single algorithm. I believe this makes the contribution very fundamental.

-- Numerical results are also done for a variety of privacy budget though it would interesting if they could demonstrate the lower bounds as well as study the dependence on $\alpha$. A

Weakness: 

-- More discussion regarding the parameter $alpha$ and how to tune it. A small discussion regarding this possibly in the main body of the paper. 

questions: -- A natural idea would be to use a tree-based aggregation technique for adaptively keeping track of the means. It is not completely clear to me how adaptively using doubling horizon ensures the same privacy level. Further, the privacy proofs do not require composition which is surprising. I would like to be convinced if this is due to the definition of Global DP or a consequence of the algorithmic template. 

limitations: A contextual bandit extension would be nice esp. since the authors get rid of tree-based aggregation. But there the adaptive-doubling idea might not work since the minimum eigenvalue of the covariance matrix would need to be updated regularly in order to have consistent parameter estimate.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper considers DP bandits under the central model. The authors present both minimax and problem-dependent lower bounds for both MAB and linear bandits. Then, they also establish a general method for designing private bandit algorithms based on non-private ones. Extensive numerical simulations are conducted to validate the theoretical results. 
strengths_and_weaknesses: **strengths**
- A comprehensive study of lower bounds under the central model

**Weaknesses**
- The proof for the privacy guarantees in the upper bound part seems to need more care
questions: - My first concern is about the proof of the privacy guarantee in Section 4. The tricky part is that the adaptive batch schedule also depends on private data (rewards). Thus, an adversary can observe the batch schedule to infer the private data. More specifically, changing one reward in the sequence will also change the follow-up batch schedule. The standard proof cannot be directly applied here. I believe this can be handled by a careful but non-trivial argument, but I will first leave it to the authors in the rebuttal period. 

- My second concern is more general. This relates to the commonly-used notion of DP in bandits. In particular, the neighboring relation is about two neighboring reward sequences, i.e., differ in the reward value at only one particular time slot. This is inspired by the standard continual model of DP. However, this is not the right notion for DP in MAB. To see it, this notion requires that if one changes a reward at time $t$, the reward obtained at $t+1, t+2,...$ are still the same by the requirement of the neighboring definition. This is obviously not the case in MAB, since the policy would be different at   $t+1, t+2,...$ due to the change of reward at time $t$, and hence the agent will pull different arms and hence different rewards will be observed. Note that this is in sharp contrast to the classic continual observation DP model where the typical task is simply to count the current counts in the online stream data, where there is no correlation between the data across time slots, and hence the standard neighboring relation makes sense in terms of privacy protection. I think one can also propose a more meaningful notion of DP in bandits (with only a minor change of the current proof), but again I will leave it to the authors in the rebuttal period.

- In fact, the intuition for the above two questions are quite related.
limitations: Yes,  limitations and potential negative societal impacts have been 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 proves the minimax regret lower bound and problem-dependent regret lower bound for stochastic and linear bandits that quantify the hardness of bandits with $\epsilon$-global DP. The results reveal interesting phase transition phenomenon in that in the high-privacy regime, the hardness depends on a coupled effect of privacy and partial information about the reward distributions; while in the low-privacy regime, the regret of bandits with $\epsilon$-global DP reduces to that of bandits without privacy. In the algorithm, the authors then propose AdaP-UCB and AdaP-KLUCB methods which are $\epsilon$-global DP extensions of UCB and KL-UCB algorithms, respectively. AdaP-KLUCB is shown to be the first algorithm that both satisfies $\epsilon$-global DP and yields a regret upper bound that matches the problem-dependent lower bound. 

strengths_and_weaknesses: Strengths 

1. In spite of a very theoretical paper, this paper is very well written and is easy to follow. 

2. DP in bandit algorithms has received recent attentions. The hardness of local DP in bandits in terms of regret lower bound has been well studied in the literature. However, fundamental hardness of differentially private bandits with global DP is less studied, except for Shariff and Sheffet (2018). 

3. The proposed algorithm is able to achieve a regret upper bound that matches the problem-dependent lower bound.  


Weaknesses

1. Technical novelty beyond Shariff and Sheffet (2018). Shariff and Sheffet (2018) studied the problem-dependent lower bound on regret for stochastic bandits of Bernoulli reward with $\epsilon$-globally DP. This paper extends the results to general reward case. It is important to explicitly highlight the technical contributions beyond Shariff and Sheffet (2018) . 

2. In the experiments, the proposed algorithms were compared to the benchmark methods DP-SE and DP-UCB. However, there are some recent developments, e.g., DP-TS by Hu and Hegde (2022), on differentially private stochastic bandits. DP-TS and its lazy version are shown to be superior over DP-SE. It is important to compare with the state-of-the-art methods. 

Hu and Hegde (2022), Near-Optimal Thompson Sampling-based Algorithms for Differentially Private Stochastic Bandits, UAI.

3. Can authors provide some discussion on the requirement $\alpha > 3$ in algorithms and theorems? I noticed that $\alpha =1$ actually works the best as shown in the additional simulation results in the supplementary materials.

4. The authors claim that Figure 3 show that in the low privacy regime ($\epsilon > 0.3$), the regret of AdaP-KLUCB does not depend on $\epsilon$. However, what I observe is that when $\epsilon > 0.3$, the regret first decreases when $\epsilon$ increases and then stabilizes. This step-shape decreasing pattern is consistent even when $\epsilon < 0.3$. Therefore, more convincing numerical evidence would be helpful to justify this claim. 


questions: See above weakness part.
limitations: N/A
review_title: null

Meta-review: metareview: This paper studies the problem of multi-armed bandits under differential privacy. The reviewers are all positive about the results and presentation of the paper. 
confidence: Certain
Decision: Accept