On Private and Robust Bandits

Summary

In this paper, the authors study private and robust multi-armed bandits (MABs), where the heavy-tailed rewards are contaminated. They first present its minimax lower bound, characterizing the information-theoretic limit of regret with respect to privacy budget, contamination level, and heavy-tailedness. Then, they propose a meta-algorithm that builds on a private and robust mean estimation sub-routine PRM which could achieve nearly-optimal regrets. Finally, the authors run simulations to support their theoretical results.

Strengths

1. The problem of private and robust bandits is well-motivated. 2. The upper bounds nearly match the lower bound, the paper is solid. 3. The writing is very clear, I enjoy reading the paper. 4. Connecting privacy with robustness using truncation is quite interesting.

Weaknesses

My main question is about the last term in both Theorem 6.2 and Theorem 6.12. Intuitively, as the contamination converges to 0, the regret upper bound should be smaller, while the last term will converge to infinity. Could the authors discuss possible methods to get rid of the term or the difficulties?

Questions

Please refer to the weaknesses above.

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.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Yes.

Summary

The paper studies the MAB problem where the agent receives rewards that are both heavy tailed and contaminated according to Huber's process (provides true rewards w.p. $1-\alpha$ and provides samples from an arbitrary, unknown distribution w.p. $\alpha$). For the case of heavy-tailed rewards, both settings with finite $k$-th raw moment (the expected reward in a narrow range) and finite $k$-th central moment (expected deviation from the mean is in a relatively narrow range). The paper provides a regret lower bound for any algorithm in this setting, proposes a novel algorithms whose regret is analysed in both the finite $k$-th raw moment setting, as well as the finite central moment setting. Some experiments are provided in the Appendix though an existing algorithm, RUCB, appears to outperform the proposed algorithm.

Strengths

The paper provides both a regret lower bound as well as nearly matching upper bounds for the regret of their proposed algorithm. If contamination is removed from the setting, the regret upper bounds provided here match the lower bounds for the bounded central moment setting, filling a gap in the existing study of private bandits. The algorithms are accompanied by experiments showcasing their performance against other existing algorithms designed for similar (but not identical) settings.

Weaknesses

Presentation is lacking in my opinion and I found the paper hard to follow. I am missing a thorough description of the problem statement describing the interaction between the agent and the environment in a self-contained, concise section. I found the quite hard to read as the setting isn't made explicit in a single place. I suggest this be done instead of the Preliminaries section (the definitions can be made in place as the need appears rather than having to keep track of them until they appear). I would have liked to see a more explicit description of how privacy ties into this setting: whose privacy are we aiming to defend here and from whom? A more clear description of the setting should also clarify this, in my opinion. I find it hard to argue for the significance of the results here meeting the conference standards as the setting feels a bit too narrow. I would have liked to see the synergy between the two aspects studied here better articulated: is the combination of privacy and heavy tailed rewards in bandit settings more difficult than the sum of its parts? What does their interplay look like?

Questions

See Weaknesses. Also am I reading the experimental results correctly when assessing that the RUCB algorithm outperforms the one proposed here? Can you find a problem instance where your algorithm performs best among the baselines?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

I do not see any potential negative societal impact arising from this work.

Summary

This work studies the specific setting of heavy-tailed bandits with Huber contamination and differential privacy constraints. They first give a regret lower bound, tightly characterizing the minimax rate in terms of all the parameters involved in this setting. Then, they provide matching (up to log terms) upper bounds. The crucial technical novelty is to use new concentration bounds they developed for private and robust estimation via truncation methods in bandits.

Strengths

They derive the first minimax rates in this robust+private bandit setting and give matching upper bounds. The paper is also generally well-written and has many useful remarks comparing the results and techniques with previous works. The algorithmic ideas and intuition behind the new estimation scheme were easy to follow.

Weaknesses

* I think some discussion on problem-dependent rates in this setting would be interesting. The paper could at least comment on why their analyses don't extend easily to obtain problem-dependent rates or what the minimax problem-dependent rates might look like in terms of $\epsilon, k,\alpha$. * There are many recent works on "bandits with total corruption budget" (e.g., the cited paper Lykouris et al., 2018). It would be good to include some comparison with this setting, even if just in terms of experiments. For instance, the $T\cdot \alpha^{1-1/k}$ term in this paper's minimax regret rate seems to be similar to the additive corruption term sometimes seen in this other setting (Theorem 1; Gupta et al., COLT 2019). Can the analyses in this paper extend to this setting?

Questions

See above.

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

No forseeable negative societal impacts.

Summary

The paper studies the private and robust multi-armed bandits, where the rewards are heavy-tailed or contaminated. It proposes a meta-algorithm which is based on private and robust mean esitmation sub-routine incorporating reward truncation and Laplace mechanism.

Strengths

The paper establish the minimax regret lower bound for private and robust MABs. It proposes a meta-algorithm matching the lower bound. It takes into account both reward contamination and heavy-tailed cases. The analyses are relatively complete.

Weaknesses

The current setting seems to require the horizon, T, to be known in advance. If T is unknown or infinity, how does it change the differential privacy definition and the technical difficulty. The paper needs to include additional literature review about heavy-tailed cases, especially in the line of Catoni's estimator (with application in bandits). For example, 1. Olivier Catoni. Challenging the empirical mean and empirical variance: a deviation study 2. Gabor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distributions: A survey. 3. Sujay Bhatt, Guanhua Fang, Ping Li, Gennady Samorodnitsky. Nearly Optimal Catoni’s M-estimator for Infinite Variance Some detailed explanations of differences between proposed method and DPRSE should be given. In supplementary, it seems that Lemma B.2 is never used. According to the current algorithm, the pararell composition should be sufficient?

Questions

Overall, I think the paper is well organized and easy to follow. See questions in weakness part.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

No.

Further clarifications on the setting

Thank you for your response. I found your clarifications regarding the interplay between heavy-tailed rewards and the standard DP mechanisms and those surrounding the experimental results to be very informative. I believe the description provided in the sections you mention and the description in the response does not provide sufficient clarity about the setting to someone not intimately familiar with the privacy side of MABs (such as myself). Please allow me to formulate what I am finding unclear more explicitly: - What information does the adversary have access to (entire history of actions of the decision maker? The entire history of realised rewards as well? What does the adversary know about the users whose privacy we aim to protect?) and what is the information we are aiming to keep private (whether or not a user presented themselves to the system?)? Presenting this aspect of the setting together with the MAB protocol would make the paper a lot more accessible, in my opinion, as it crystallises the problem in one place and allows the reader to easier recognise the use of concepts introduced later in the paper. - "Practically speaking, our setting naturally covers many real-world scenarios." - Can you provide an example scenario where this setting applies: heavy-tail rewards and a setting where it is "easy" (possible) for an adversary to infer the information we aim to keep private (as described in the answer to the point above) when no privacy preserving mechanisms are employed? Such an example would make the significance of the problem a lot more obvious to me.

Thanks

Thank you for the detailed and clarifying response. My concerns were mostly writing/discussion suggestions, and I'm still in support of accepting the paper.