- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies best-of-both-worlds multi-armed bandits under pure central (global) differential privacy (DP). It proposes Private Detect-and-Switch (PrivDaS), a central DP bandit algorithm designed to achieve low regret in both stochastic and adversarial environments. The paper establishes pure -DP (Theorem 4.1) guarantees for PrivDaS and provides regret bounds for both adversarial (Theorem 5.1) and stochastic (Theorem 5.2) environments, matching existing specialized guarantees up to additional logarithmic factors. Finally, the experiments show that PrivDaS performs reasonably well in both stochastic and adversarial settings, although it does not outperform algorithms designed specifically for each setting.
Critical strengths
The paper makes a solid theoretical contribution by extending private best-of-both-worlds bandit learning from local to central DP. The theoretical analysis also provides regret guarantees for both stochastic and adversarial environments for the proposed algorithm.
The theoretical analysis is also technically involved, particularly in handling adaptive decisions, private monitoring, and the composition of privacy mechanisms.
Critical weaknesses
My main concern is the limited experimental evaluation. The experiments consider four synthetic settings with only a fixed privacy budget of , which corresponds to a strong privacy regime. Based on the results, it is unclear how PrivDaS performs under potentially more practical settings with weaker privacy guarantees (larger values of ). Evaluating different privacy budgets would provide a better understanding of the privacy–regret tradeoff and strengthen the experimental results.
Although the paper explains the source of the additional logarithmic factors, they are still a limitation compared to existing specialized algorithms. In particular, the stochastic regret bound has an extra factor, which can become large when the gaps are small (Theorem 5.2).
Questions for authors
Could the authors include experiments with larger values of ? Addressing this concern would strengthen my assessment of the paper and could positively influence my final score.
5 comments
Thank you for the additional experiments.
The results are encouraging. However, I have a follow-up question: It seems that PrivDaS becomes less competitive in the stochastic setting for larger values of , even performing worse than PrivateConversion. Is there any intuition behind this behavior?
Response to Reviewer xiVm
Dear Reviewer xiVm,
Thank you for your question. The source of the phenomenon lies in PrivateConversion from [1]. In fact, PrivateConversion is a meta-algorithm that converts a non-private bandit algorithm into a private one by passing privatized batch average from batches of size to the base learner. In our experiment and in Corollary 2 of [1], the base learner is HTINF from [2], which is a best-of-both-worlds algorithm in non-private case for heavy-tailed losses. Therefore, PrivateConversion inherits a stochastic guarantee from HTINF. We can give a simple proof here by invoking theoretical guarantee from [2]:
Claim. Suppose each arm has i.i.d. losses in , with mean , and a unique optimal arm . Write . For , PrivateConversion initialized with HTINF satisfies the stochastic pseudo-regret bound
Proof. Set and . For each complete batch , define
The noise is fresh and independent. Only the selected arm’s feedback is observed.
The batch-level environment remains stochastic. Since the noise has mean zero, its arm means and gaps are unchanged:
Let . The second moments satisfy
Moreover, conditional on any batch mean , Lemma 19 of [1] gives
for every . Averaging over the batch mean establishes truncated non-negativity.
Thus the noisy batch losses satisfy the assumptions of Theorem 4.1 of [2] with the parameters and . Consequently, their stochastic guarantee yields
where is the arm selected for batch .
Each batch-level selection of arm incurs original-round pseudo-regret. The incomplete final batch contributes less than . Therefore,
using and .
From the argument above, we could see that PrivateConversion in our experiment indeed has a stochastic regret also logarithmic in T. However, the dependency on the sub-optimality gaps and the privacy parameter takes the scale of . In the case where is large, such as or , where we can treat it as a constant hidden by big-O notation, the stochastic bound derived for PrivateConversion reduces to , where for PrivDaS, it reduces to . The additional dependence on $ \log \Delta_{i}^{-1}$ still persists. Therefore, for larger values of , PrivateConversion has a performance comparable to stochastic learners and PrivDaS appears less competitive. This argument is consistent because when becomes small, the performance of PrivateConversion quickly deteriorates and PrivDaS takes advantage over it. This happens as the effect of factor outweighs the factor as becomes small. Since our algorithm matches the best known stochastic guarantee up to a logarithmic factor instead of an inverse-square factor like , it will take advantage in more challenging senarios such as tasks with strong privacy constraint due to extremely sensitive data, we believe that PrivDaS is still theoretically and practically meaningful and not undermined by the stochastic guarantee of this version of PrivateConversion.
We hope the above provides sufficient clarifications to the questions you raised. Thank you for your dedication to review our work!
Best regards,
Authors
References:
[1] Asi, H., Raman, V., and Talwar, K. (2025). Faster rates for private adversarial bandits. Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 1796–1832. PMLR, 2025.
[2] Huang, J., Dai, Y., & Huang, L. (2022, June). Adaptive best-of-both-worlds algorithm for heavy-tailed multi-armed bandits. In international conference on machine learning (pp. 9173-9200). PMLR.
Response to Reviewer xiVm
Dear Reviewer xiVm,
We thank you for your constructive and valuable feedback. We provide clarifications as follows:
Additional experiments. We have performed some additional experiments where we run same problem instance with varying value of ϵ ranging from 5121 to 1. Kindly refer to "Varying values of ϵ" in our general response for a description of experiment settings and a discussion of experiment results. Thank you.
We hope the above provides sufficient clarifications to the questions you raised. Thank you for your dedication to review our work!
Best regards,
Authors