acceptodds
Under review as a conference paper at ICLR 2027

Best-of-Both-Worlds Bandits under Global Differential Privacy

14 views

Abstract

Best-of-both-worlds bandit algorithms exploit stochastic losses while retaining worst-case guarantees against adversarial losses, without knowing the environment in advance. Achieving this adaptivity under differential privacy requires balancing efficient learning and adversarial robustness within a fixed privacy budget. We introduce Private Detect-and-Switch (PrivDaS), which extends the detect-and-switch approach of Bubeck and Slivkins (COLT 2012) to private bandit learning. PrivDaS combines private successive elimination with tests for consistency with stochastic losses, continues to sample and monitor eliminated arms, and switches to a private adversarial algorithm when a test fails. Our construction controls the privacy cost across elimination, monitoring, and switching. For arms and a horizon of rounds, PrivDaS satisfies pure global -differential privacy and achieves expected regret against oblivious adversaries and in stochastic environments, where is the privacy parameter and is the suboptimality gap of arm . These bounds recover, up to additional logarithmic factors in the inverse gaps and the horizon, the gap-dependent stochastic guarantee of Azize and Basu (NeurIPS 2022) and the adversarial guarantee of Asi, Raman, and Talwar (ICML 2025), previously obtained by algorithms designed separately for the two environments. To our knowledge, PrivDaS is the first bandit algorithm to achieve best-of-both-worlds regret guarantees under global differential privacy.

Primary area:
learning theory
Keywords:
Bandits, Best-of-both-worlds, Privacy, Regret minimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_xiVmOpenReview ↗
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 ϵ\epsilon-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 ϵ=1/512\epsilon=1/512, 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 ϵ\epsilon). 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 log⁡(1/Δi)\log(1/\Delta_i) 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 ϵ\epsilon? Addressing this concern would strengthen my assessment of the paper and could positively influence my final score.

5 comments
AuthorsOpenReview ↗

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 ϵ\epsilon ranging from 1512\frac{1}{512} to 11. Kindly refer to "Varying values of ϵ\epsilon" 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

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 ε\varepsilon, even performing worse than PrivateConversion. Is there any intuition behind this behavior?

AuthorsOpenReview ↗

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 Θ(1ϵ)\Theta(\frac{1}{\epsilon}) 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 [0,1][0,1], with mean μi\mu_i, and a unique optimal arm i⋆i^\star. Write Δi=μi−μi⋆\Delta_i=\mu_i-\mu_{i^\star}. For 1/T≤ϵ≤11/T\le\epsilon\le1, PrivateConversion initialized with HTINF satisfies the stochastic pseudo-regret bound

RTsto=O(log⁡Tϵ∑i≠i⋆1Δi+1ϵ).R_T^{\mathrm{sto}}=O\left(\frac{\log T}{\epsilon}\sum_{i\ne i^\star}\frac{1}{\Delta_i}+\frac{1}{\epsilon}\right).

Proof. Set b=⌈1/ϵ⌉b=\lceil1/\epsilon\rceil and H=⌊T/b⌋H=\lfloor T/b\rfloor. For each complete batch BrB_r, define

Yr,i=ℓˉr,i+Zr,i,ℓˉr,i=1b∑t∈Brℓt,i,Zr,i∼Lap⁡(1/(bϵ)).Y_{r,i}=\bar\ell_{r,i}+Z_{r,i},\qquad \bar\ell_{r,i}=\frac1b\sum_{t\in B_r}\ell_{t,i},\qquad Z_{r,i}\sim\operatorname{Lap}(1/(b\epsilon)).

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:

E[Yr,i]=μi,E[Yr,i]−E[Yr,i⋆]=Δi.\mathbb E[Y_{r,i}]=\mu_i,\qquad \mathbb E[Y_{r,i}]-\mathbb E[Y_{r,i^\star}]=\Delta_i.

Let λ=1/(bϵ)≤1\lambda=1/(b\epsilon)\le1. The second moments satisfy

E[Yr,i2]=E[ℓˉr,i2]+2λ2≤3≤6.\mathbb E[Y_{r,i}^2]=\mathbb E[\bar\ell_{r,i}^2]+2\lambda^2\le3\le6.

Moreover, conditional on any batch mean ℓˉr,i=x∈[0,1]\bar\ell_{r,i}=x\in[0,1], Lemma 19 of [1] gives

E[(x+Zr,i)1∣x+Zr,i∣>M]≥0\mathbb E[(x+Z_{r,i})\mathbf{1}\\{|x+Z_{r,i}|>M\\}]\ge0

for every M≥0M\ge0. 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 α=2\alpha=2 and σ=6\sigma=\sqrt6. Consequently, their stochastic guarantee yields

R~Hsto:=E[∑r=1HΔJr]=O(log⁡(H+1)∑i≠i⋆1Δi),\widetilde R_H^{\mathrm{sto}}:=\mathbb E\left[\sum_{r=1}^H\Delta_{J_r}\right]=O\left(\log(H+1)\sum_{i\ne i^\star}\frac1{\Delta_i}\right),

where JrJ_r is the arm selected for batch rr.

Each batch-level selection of arm ii incurs bΔib\Delta_i original-round pseudo-regret. The incomplete final batch contributes less than bb. Therefore,

RTsto≤bR~Hsto+b=O(log⁡Tϵ∑i≠i⋆1Δi+1ϵ),R_T^{\mathrm{sto}}\le b\widetilde R_H^{\mathrm{sto}}+b=O\left(\frac{\log T}{\epsilon}\sum_{i\ne i^\star}\frac1{\Delta_i}+\frac1\epsilon\right),

using b≤2/ϵb\le2/\epsilon and H≤TH\le T. □\square

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 (1Δiϵ+1ϵ2)(\frac{1}{\Delta_{i}\epsilon}+\frac{1}{\epsilon^{2}}). In the case where ϵ\epsilon is large, such as ϵ=12\epsilon=\frac{1}{2} or 11, where we can treat it as a constant hidden by big-O notation, the stochastic bound derived for PrivateConversion reduces to O(∑i≠i⋆log⁡TΔi)O(\sum_{i\neq i^{\star}}\frac{\log T}{\Delta_{i}}), where for PrivDaS, it reduces to O(∑i≠i⋆log⁡Tlog⁡Δi−1Δi)O(\sum_{i\neq i^{\star}}\frac{\log T \log \Delta_{i}^{-1}}{\Delta_{i}}). The additional dependence on $ \log \Delta_{i}^{-1}$ still persists. Therefore, for larger values of ϵ\epsilon, PrivateConversion has a performance comparable to stochastic learners and PrivDaS appears less competitive. This argument is consistent because when ϵ\epsilon becomes small, the performance of PrivateConversion quickly deteriorates and PrivDaS takes advantage over it. This happens as the effect of factor 1ϵ2\frac{1}{\epsilon^{2}} outweighs the factor log⁡Δi−1\log \Delta_{i}^{-1} as ϵ\epsilon becomes small. Since our algorithm matches the best known stochastic guarantee up to a logarithmic factor instead of an inverse-square factor like 1ϵ2\frac{1}{\epsilon^{2}}, 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.

Reviewer_RAAcOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper focuses on multi-armed bandit algorithms in settings where the environment is known a priori. This is a highly challenging topic; while the assumption of a "known environment" is crucial in machine learning, it also limits the practical applicability of many theoretical results. In this research, achieving such adaptability while satisfying differential privacy constraints requires balancing efficient learning with adversarial robustness, all within a fixed privacy budget. The authors propose the "Private Detect-and-Switch" (PrivDaS) algorithm, which extends the "Detect-and-Switch" framework—originally introduced by Bubeck and Slivkins (COLT 2012)—to the context of private multi-armed bandit learning. PrivDaS combines a "private successive elimination" strategy with consistency checks designed for stochastic losses. It continues to sample and monitor arms that have already been eliminated; if a consistency check fails, the algorithm switches to a private adversarial learning strategy.

The algorithm proposed in this paper, PrivDaS, effectively controls privacy costs across three distinct phases: "elimination," "monitoring," and "switching." For a multi-armed bandit problem with KK arms and a total of TT rounds, PrivDaS satisfies pure global ϵ\epsilon-differential privacy. Under an "oblivious adversary" setting, the algorithm achieves an upper bound on expected regret of O((log⁡2T)KTϵ+1ϵ)O\left((\log^2 T)\sqrt{\dfrac{KT}{\epsilon}} + \dfrac{1}{\epsilon}\right), while in a stochastic environment, the upper bound on expected regret is O(∑i:Δi>0(log⁡T)(1+log⁡(1/Δi))min⁡{Δi,ϵ})O\left(\sum_{i:\Delta_i>0} \dfrac{(\log T)(1+\log(1/\Delta_i))}{\min\{\Delta_i,\epsilon\}}\right). Here, ϵ\epsilon is the privacy parameter, and Δi\Delta_i denotes the suboptimality gap of the ii-th arm. Up to logarithmic factors involving the reciprocals of the gaps and the total number of rounds TT, these bounds recover the gap-dependent regret bounds for stochastic environments established by Azize and Basu (NeurIPS 2022), as well as the regret bounds for adversarial environments established by Asi, Raman, and Talwar (ICML 2025)—results that were previously achieved by algorithms specifically designed for each respective environment. PrivDaS is the first multi-armed bandit algorithm under the global differential privacy framework to achieve optimal regret bounds in both stochastic and adversarial environments—a property known as ”best-of-both-worlds.”

This paper establishes privacy guarantees and provides regret bounds for both stochastic and adversarial environments. Furthermore, it presents experimental results in synthetic settings to demonstrate the performance of the proposed algorithm under various environmental dynamics.

Critical strengths
  1. This paper explores the "best-of-both-worlds" multi-armed bandit problem under differential privacy---a theoretically significant topic. Achieving regret guarantees for both stochastic and adversarial environments simultaneously while adhering to privacy constraints is a major contribution, as it requires the algorithm to strike a balance between efficient learning in stochastic settings and robustness against environmental shifts.

  2. The "detect-and-switch" framework is conceptually elegant. Notably, the continuous monitoring of previously discarded arms is crucial, as these underperforming arms may regain competitiveness following a change in the environment. The proposed monitoring mechanism addresses this challenge without incurring the full cost typically associated with adversarial exploration.

  3. By integrating standard privacy-preserving tools---such as the Laplace mechanism, the AboveThreshold mechanism, and privacy composition---the paper establishes the privacy guarantees for the PrivDaS algorithm. Furthermore, it provides a unified theoretical framework for analyzing regret in both stochastic and adversarial environments.

Critical weaknesses
  1. The innovations of the proposed method require further clarification. The algorithmic framework appears to integrate mechanisms for "private stochastic Bayesian learning," "privacy-preserving monitoring," and "private adversarial backup." While this combination may seem logical, the paper should more clearly articulate the specific technical obstacles that prevent a straightforward integration of existing methods. Furthermore, what fundamental new algorithms or analytical approaches are introduced? In particular, it is necessary to distinguish the contributions---stemming from the monitoring process, switching criteria, and privacy analysis---from the existing contributions found in established "private stochastic Bayesian" and "private adversarial Bayesian" algorithms.

  2. The upper bound on regret includes an additional logarithmic factor. In the stochastic setting, the regret exhibits an extra logarithmic dependence on the reciprocal of the "suboptimal gap," which the authors attribute to the arms discarded during the monitoring process. In the adversarial setting, the performance guarantee also contains an additional logarithmic factor compared to corresponding private adversarial benchmarks; this arises from the inclusion of a "pre-switch cumulative loss certificate." While these costs might be inherent to simultaneously achieving privacy protection and optimal performance, the paper does not sufficiently justify their necessity. Could these factors be reduced further? Or does a lower bound exist that proves these costs are unavoidable for this problem?

  3. The experimental evaluation is somewhat limited. Experiments were conducted exclusively in synthetic environments; while this demonstrates the algorithm's performance under various switching patterns, it provides insufficient evidence regarding its robustness or practical advantages in broader, more diverse scenarios. For instance, the evaluation could be strengthened by examining the algorithm's sensitivity to the privacy parameter ϵ\epsilon, the number of arms KK, and the frequency or magnitude of environmental changes. Additionally, conducting ablation studies would help clarify the specific roles played by the monitoring and switching mechanisms.

  4. The switching mechanism warrants a more in-depth evaluation. The effectiveness of PrivDaS hinges on its ability to accurately detect violations of the "randomness assumption" without consuming excessive monitoring resources. A more systematic analysis of detection latency, false-positive rates, and the resulting "regret" costs would be highly valuable. In particular, current empirical evaluations leave it unclear how these factors evolve as the environment becomes more dynamic; furthermore, it remains uncertain whether the proposed certificates remain robust if environmental changes occur shortly after an arm has been removed.

Questions for authors
  1. Within the stochastic adversarial regret framework, is it possible to improve upon the additional logarithmic factor? Are there any provable lower bounds for these costs?
  2. Can the authors quantify the detection latency and false-positive rate of the proposed monitoring method, and explain how these metrics affect the regret value?
  3. How sensitive is PrivDaS to the privacy parameter ϵ and the frequency of environmental changes? Does the algorithm remain competitive under more diverse switching patterns?
4 comments
AuthorsOpenReview ↗

Response to Reviewer RAAc (Part I)

Dear Reviewer RAAc,

We thank you for your constructive and valuable feedback. We provide clarifications as follows:

Innovation of the algorithm. We agree that since we adapt detect-and-switch framework, our algorithm is an integration of techniques from private stochastic and adversarial learners. However, it is not a trivial combination of the abovementioned mechanisms due to the following two technical challenges:

(1) In "Batches and private feedback" in Section 4, we discussed that to prevent significant downgrade in utility due to addition of Laplace noise, we perform observations in batches and only privatize batch aggregates. However, to achieve logarithmic stochastic regret while preserving privacy, we have to be aggresive in commitment, in the sense of increasing batch length. See the section of "Adaptive episode with doubling" of Section 4 of [1]. On the other hand, batched observations are prone to adversarial attack if it keeps increasing its length, as an adversary can deteriorate an arm after the learner decides to commit a long batch to it. It is still feasible to consider batched observations for private adversarial bandits as shown by [2], but we must be more conservative to take short and constant batch lengths to be prompt to react to adversarial attack. A sufficient scale is Θ(1ϵ)\Theta(\frac{1}{\epsilon}), which is deployed by [2] as well as PrivDaS. Therefore, requirement of increasing batch length for stochastic environment and constant batch length for adversarial environment exhibit inconsistency to prevent a naive combination. Our algorithm resolves the inconsistency by introducing the stages in the stochastic mode: Each batch of observations is having size Θ(1ϵ)\Theta(\frac{1}{\epsilon}), while we complete stage mm to release stage aggregates only when all arms have at least qmq_{m} batches of observations, and the stage quota qmq_{m} roughly doubles when mm increases. Hence we are still able to strengthen our commitment in stochastic mode while having batch size not too long when we switch to adversarial mode. Furthermore, PrivDaS can prevent an adversary from exploiting long stage lengths, because PrivEAP and PrivBSC conduct checks every batch and can interrupt long stages when adversarial behavior is detected halfway. Therefore, despite adapting detect-and-switch framework, PrivDaS is not a straightforward integration of existing mechanisms.

(2)The privacy analysis is not trivial. Privacy analysis for many private adversarial and stochastic learners are relatively easier because they usually deploy techniques such as: (i)decompose executions into phases with forgetting/restart to remove complicated interdependency. (ii)let the learner only see privatized data and apply post-processing property. However, to design a private algorithm with detect-and-switch framework introduces complicated interdependency between various mechanisms, especially in stochastic mode, where the learner must monitor eliminated arms and update active arms concurrently. PrivDaS is designed to ensure that the total privacy budget of mechanisms that could access the perturbed data sums up to at most ϵ\epsilon (Theorem D.3), and our privacy analysis (Corollary C.8) extends a result from [3] to ensure that privacy is preserved when we interleave queries to private mechanisms instead of having a simple sequential composition.

Lower bounds or impossibility results. We have explained the source of the extra factors in our upper bounds. Since they are all arising from our algorithmic design, we cannot assert whether those factors are essential. Removing/improving on those factors remains as our future work to provide sharper theoretical guarantee. To the best of our knowledge, there is no known lower bound for either private stochastic bandits or private adversarial bandits that holds for all private learners over [0,1][0,1]-bounded loss. There are some existing lower bounds that holds in restricted cases. For example, [6] provides a lower bound for private Bernoulli bandits, and [2] provides a lower bound for private adversarial bandits for algorithms satisfying some given constraints. Nevertheless, we can still get some insights on the sharpness of our results by letting ϵ→∞\epsilon \rightarrow \infty to reduce to non-private bandit problems. For stochastic bandits, when ϵ→∞\epsilon \rightarrow \infty, our stochastic upper bound (Theorem F.1) reduces to O(∑Δi>0log⁡Tlog⁡(1Δi)Δi)O(\sum_{\Delta_{i}>0}\frac{\log T \log(\frac{1}{\Delta_{i}})}{\Delta_{i}}), this matches lower bound by Lai-Robbins [4] up to the factor O(log⁡(1Δi))O(\log(\frac{1}{\Delta_{i}})). For adversarial bandits, when our adversarial upper bound (Theorem F.6) reduces to O(log⁡2TKT)O(\log^{2}T\sqrt{KT}), this matches lower bound by Auer, et al. [5] up to the factor of O(log⁡2T)O(\log^{2}T). Hence, our private best-of-both-worlds upper bounds nearly match the non-private lower bounds for each individual environment when we reduce private problems to non-private ones.

AuthorsOpenReview ↗

Response to Reviewer RAAc (Part II)

Additional experiments. We have performed additional experiments where we run the same instance across multiple values of ϵ\epsilon (ranging from 1512\frac{1}{512} to 11) as well as different frequency of adversarial perturbations. Kindly refer to "Varying values of ϵ\epsilon" in our general response for a description of experiment settings and a discussion of experiment results. Thank you.

Ablation studies. We have reimplemented two ablation versions of PrivDaS: The first version has PrivEAP removed while preserving everything else. The second version has PrivBSC removed while preserving everything else. Kindly refer to "Ablation of PrivDaS" in our general response for a description of experiment settings and a discussion of experiment results. In essence, both components are necessary. We designed an adversarial instance where removal of either component will negatively impact the performance of PrivDaS. We have also provided an intuitive justification of the phenomenon displayed in our ablation study.

Latency and false positive rates. Thank you for your concerns. By "false positive rates" we interpret as you are interested in the probability of PrivDaS wrongly switching to adversarial mode when the environment is eventually stochastic. This probability can be explicitly controlled by the parameter β\beta, which is introduced in "Private elimination" of Section 4 and to be chosen by user. The significance of β\beta is that, Theorem E.15 proves that a good event Gsafesto\mathcal{G}_{\mathrm{safe}}^{\mathrm{sto}} occurs with probability at least 1−β1-\beta, and PrivDaS never wrongly switches conditioning on Gsafesto\mathcal{G}_{\mathrm{safe}}^{\mathrm{sto}}. Furthermore, β\beta appears in both of our regret bounds via a term LHL_{H} of order O(log⁡Tβ)O(\log\frac{T}{\beta}), so, we can make β\beta arbitrarily small by choosing β=1Tα\beta = \frac{1}{T^{\alpha}} with higher exponent α\alpha without worsening the order of our regret guarantees.

For latency analysis, please note that our goal is regret minimization, which does not necessarily depend on rapid detection of adversary. Intuitively, if an adversary is "mild" in the sense that learning it by a stochastic learner does not incur great regret(at least for some period of time), then it takes no serious harm for not identifying it immediately. This idea reflects in the design and the regret analysis of PrivDaS: PrivDaS does not provide any explicit judgement on the underlying nature of the environment, nor it establishes any upper bound of switching time in adversarial environment, but it focuses on estimating and controlling cumulative regret incurred regardless of the environment we are learning from. This regret guarantee is explained in "Adversarial regret" in Section 5.1, where we decompose total regret into pre-switch regret and post-switch regret. Pre-switch regret is the regret incurred by stochastic mode of PrivDaS in an adversarial environment. Despite PrivDaS assumes the adversarial environment as stochastic before the switch, which may sound "conceptually mismatched", its regret during this period can still be effectively controlled due to the fact that all PrivBSC and PrivEAP checks must pass before the switching batch, which provides sufficient certificates to bound the pre-switch regret and achieve our target of regret minimization. We invite you to read the paragraph for more intuition. In essence, it is acceptable to not immediately identify adversarial environments, as long as the cumulative regret of learning remains controlled.

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] Azize, A., & Basu, D. (2022). When privacy meets partial information: A refined analysis of differentially private bandits. Advances in Neural Information Processing Systems, 35, 32199-32210.

[2] 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.

[3] Vadhan, S., & Wang, T. (2021, November). Concurrent composition of differential privacy. In Theory of Cryptography Conference (pp. 582-604). Cham: Springer International Publishing.

[4] Lai, T. L., & Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1), 4-22.

[5] Auer, P., Cesa-Bianchi, N., Freund, Y., & Schapire, R. E. (2002). The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1), 48-77.

[6] Azize, A., Wu, Y., Honda, J., Orabona, F., Ito, S., & Basu, D. (2025). Optimal Regret of Bandits under Differential Privacy. Advances in Neural Information Processing Systems, 38, 115153-115202.

Thanks for the clarifications. Given the positive score, I will keep the score unchanged.

AuthorsOpenReview ↗

Response to Reviewer RAAc

Dear Reviewer RAAc,

Thank you for your positive feedback.

Best regards,

Authors

Reviewer_xg71OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces PrivDaS, the first MAB algorithm designed to achieve "best-of-both-worlds" regret guarantees under pure global differential privacy (DP). It runs private successive elimination in batches, adds Laplace noise to batch aggregates rather than individual observations, and monitors whether observations remain consistent with stochastic behavior through private certificates. It continuously audits both active and eliminated arms (via private "AboveThreshold" queries) to check for consistency with stochastic behavior. For the fallback, if any of these private stochasticity certificates fail, indicating an adversarial shift, the algorithm permanently switches to a specialized private adversarial learning subroutine. The authors give PrivDaS the bound, including a gap-dependent stochastic regret. Experiments against ADAP-UCB and PrivateConversion on stochastic and stochastically-constrained-adversarial instances illustrate that it adapts to the unknown environment and match purely adversarial algorithms.

Critical strengths
  1. This paper fills the gap that for stochastic and adversarial environments, private algorithms exist seperately but no one under global DP to achieve guarantee at once. The authors propose the method which allows aggregating a batch before adding noise, rather than privatizing each observation as in local DP. Also reveals under a weaker access restriction, the price of privacy is fundamentally lower, which makes sense for me.
  2. The authors use concurrent-composition theory and add a refinement, then says only mechanisms that actually read the changed record contribute to the privacy loss, so that only interleaving itself costs nothing extra. So I think the regret is not the main novelty, the idea of mechanisms that run interleaved is main point.
Critical weaknesses
  1. The author admits that PrivDaS design prevents an intermediate regret bound for stochastic environments with mild corruption. I have some concern that whether it is a step back compared to the existing BoBW work. This concern also lies in the experiment part. Also, no analysis of ϵ\epsilon value since I do not understand why it is fixed at 1/512. Need more analysis then.
Questions for authors
  1. The analysis moves between ϵ\epsilon and ϵ0=min⁡ϵ,1\epsilon_0 = \min {\epsilon, 1}. Is the guarantees hold for ε > 1, and is the privacy claim unaffected in that regime?
  2. PrivDaS requires all active arms to complete a synchronized stage quota qmq_m before any private empirical means are updated and eliminations occur. I am just curious whether asynchronous, arm-specific update schedules can work when not violating the concurrent composition privacy bounds?
  3. Need some discussion of whether controlled restarts or corruption-tolerant certificates could cover the intermediate regime without breaking the privacy analysis and need more experiments to analyze different privacy levels.
4 comments
AuthorsOpenReview ↗

Reponse to Reviewer xg71

Dear Reviewer xg71,

We thank you for your constructive and valuable feedback. We provide clarifications as follows:

Larger values of ϵ\epsilon. Note that the privacy constraint becomes weaker as ϵ\epsilon increases. With ϵ0=min⁡ϵ,1\epsilon_{0}=\min\\{\epsilon,1\\}, what we prove is that PrivDaS, run with privacy parameter ϵ0\epsilon_{0}, is ϵ0\epsilon_{0}-DP. Since ϵ0≤ϵ\epsilon_{0} \leq \epsilon, the definition of differential privacy gives, for every pair of neighboring inputs L,L′L,L' and every E⊆[K]TE \subseteq [K]^{T},

Mπ,L(E)≤eϵ0Mπ,L′(E)≤eϵMπ,L′(E).\mathbb{M}_{\pi,L}(E) \leq e^{\epsilon_{0}}\mathbb{M}_{\pi,L'}(E) \leq e^{\epsilon}\mathbb{M}_{\pi,L'}(E).

If ϵ<1\epsilon < 1, Theorem 4.1 directly asserts that PrivDaS is ϵ\epsilon-DP. If ϵ≥1\epsilon \geq 1, running PrivDaS with privacy parameter 1 gives 1-DP, which implies ϵ\epsilon-DP by the inequality above. Thus, using the clipped privacy parameter ϵ0\epsilon_{0} provides the requested privacy guarantee for every ϵ>0\epsilon > 0.

Additional experiments. We have performed additional experiments in which we run the same instance across multiple values of ϵ\epsilon (ranging from 1512\frac{1}{512} to 11), as well as different frequencies of adversarial perturbations. Kindly refer to “Varying values of ϵ\epsilon” in our general response for a description of the experimental settings and a discussion of the results. Thank you.

Asynchronous and arm-specific updates. We appreciate your interest in our algorithm design. We adopted synchronous updates to ensure that all arms complete their stages and release private empirical estimates at the same time. This design brings convenience to the theoretical analysis of the good event Gactsto\mathcal{G}_{\mathrm{act}}^{\mathrm{sto}} (defined in Appendix E.1 and shown to occur with high probability by Lemmas E.2 and E.6), which implies that all private empirical estimates concentrate around the true means within a specified radius when the environment is stochastic.

This does not provide evidence against a potential asynchronous design. However, in the asynchronous case, we expect the analysis of the same good event to become more involved. Establishing the same concentration guarantee would require considering more combinations of release times, since each arm could complete its stage and release its estimate while other arms are still completing their stages. Since a synchronous design is sufficient to derive our bounds, we retain this design and leave asynchronous updates as an interesting direction for future work.

Intermediate regime. Thank you for your interest. To the best of our knowledge, PrivDaS is the first globally differentially private algorithm to pursue a best-of-both-worlds performance guarantee. We believe this contributes to the study of best-of-both-worlds bandit problems and differential privacy.

We agree and acknowledge in Appendix G that PrivDaS has not yet been specifically adapted to the stochastic regime with corruption, although our adversarial guarantee still applies. Whether we can obtain a bound better than the adversarial bound O(KTϵ+1ϵ)O(\sqrt{\frac{KT}{\epsilon}}+\frac{1}{\epsilon}) in this regime remains a direction for future work. Thank you for your valuable insights.

We hope the above clarifies the questions you raised. Thank you for your dedication to reviewing our work!

Best regards,

Authors

Thank you for the detailed response and extra experiments. I will keep my point and have some more discussion: First, how much corruption is needed before the certificates fail and PrivDaS switches to the adversarial subroutine? Second, FTRL-based methods such as Tsallis-INF handle this regime gracefully without privacy. Is there a structural reason they are hard to make globally private.

AuthorsOpenReview ↗

Response to Reviewer xg71

Dear Reviewer xg71,

Thank you for these follow-up questions. We provide further clarifications as follows:

Corruption and switching. PrivDaS is designed for stochastic and adversarial environments. Switching is triggered by certificate violations, rather than a prescribed total corruption budget. Let us call the switching time tswitcht_{\mathrm{switch}}. Consequently, tswitcht_{\mathrm{switch}} depends on when and which arms are corrupted, their sampling frequencies, and the confidence thresholds incorporating privacy noise, which are all random. We have not quantitatively analyzed how tswitcht_{\mathrm{switch}} depends on the amount of corruption, nor have we established an upper bound of it. The key result of our analysis is that, regardless of what is the actual environment and what value tswitcht_{\mathrm{switch}} takes in an actual run, the cumulative regret prior to tswitcht_{\mathrm{switch}} is bounded by O(log⁡2TKTϵ)O(\log^{2}T\sqrt{\frac{KT}{\epsilon}}), which fits into our target of regret minimization. We invite you to read paragraph "Adversarial regret" in Section 5.1 for details. The regret analysis relies on the fact that PrivBSC and PrivEAP certificates must all check pass before tswitcht_{\mathrm{switch}}, instead of requiring tswitcht_{\mathrm{switch}} to have an explicit upper bound. Hence, we establish regret guarantee while bypassing the need to analyze how fast PrivDaS will react to corruptions.

Nevertheless, we can still bring some empirical intuition: On all stochastic experiments conducted, with regret curves plotted in Figure 2, PrivDaS remained in stochastic mode and never switched to adversarial mode until the horizon is reached. On all adversarial experiments conducted, including both the experiments in Figure 2 and the ablation studies in Figure 3, PrivDaS always switched to adversarial mode. This shows that PrivDaS is empirically able to identify the adversary.

Extending Tsallis-INF under privacy. The key challenge is not creating a private Tsallis-INF algorithm, as it can be easily done by adding Laplace noise to each bandit feedback. The difficulty lies in preserving sharp best-of-both-worlds guarantees after privatization. The self-bounding analysis controls the FTRL penalty and stability terms through the probabilities of selecting suboptimal arms, in a sketch,

\lesssim \sum_{t=1}^{T}\frac{1}{\sqrt{t}} \sum_{a\ne a^\star} \mathbb{E}\left[\sqrt{p_{t,a}}\right] +\text{lower-order terms}.$$ The self-bounding condition provides the complementary relation $$\mathrm{Reg}_T \geq \sum_{t=1}^{T}\sum_{a\ne a^\star} \Delta_a\\,\mathbb{E}[p_{t,a}]-C,$$ where $\Delta_a > 0$ is the gap of suboptimal arm $a$, and $C$ denotes the corruption-induced slack, with $C=0$ in the stochastic setting. By Cauchy–Schwarz, the first expression can then be related back to regret, yielding an inequality that can be solved for $\mathrm{Reg}_T$. The stability-penalty analysis for non-private Tsallis-INF in Section 7 of [3] crucially requires eliminating the optimal-arm contribution: its gap is zero, so its selection probability cannot be controlled through the self-bounding condition. When $p_{t,a^\star}$ approaches one, retaining a term such as $\sum_t t^{-1/2}\mathbb{E}[\sqrt{p_{t,a^\star}}]$ would leave an order-$\sqrt{T}$ contribution even in a stochastic environment. For FTRL, removing this contribution is typically more straightforward for the penalty term than for the stability term, which controls the effect of updating the estimated losses. Under privacy, even mean-zero perturbations can enlarge the second-moment terms appearing in the stability analysis, while clipping or truncating noisy estimates can introduce bias. The challenge is to control these additional terms through suboptimal-arm probabilities while retaining sharp dependence on privacy and the gaps. We believe there are some viable approaches, such as the loss shifting technique as in Lemma A.5 of [1], and the action selection probability-dependent clipping technique as in Lemma 1 of [2]. However, extending these arguments to obtain sharp joint dependence on privacy, gaps, and corruption requires a separate analysis, which we leave for future work. Best regards, Authors References: [1] 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. [2] Zhao, C., Ito, S., & Li, S. (2025). Heavy-tailed linear bandits: Adversarial robustness, best-of-both-worlds, and beyond. arXiv preprint arXiv:2508.13679. [3] Zimmert, J., & Seldin, Y. (2021). Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28), 1-49.

Thank you for your further justification, that makes clear for me. Thank you!

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response: Additional experiments

Dear Reviewers,

We post a general response to summarize our additional experiments. Edits in PDF have been marked in blue.

Varing values of ϵ\epsilon

We run the following set of experiments with ϵ∈1512,1256,1128,116,12,1\epsilon\in\\{\frac{1}{512}, \frac{1}{256}, \frac{1}{128}, \frac{1}{16}, \frac{1}{2}, 1\\}:

Stochastic instance: We set K=2K=2. Two arms follows Ber(0.99825)\mathrm{Ber}(0.99825) and Ber(0.999)\mathrm{Ber}(0.999) respectively.

Adversarial instance: We set K=8K=8. We alternate between the following two stochastic environments with period pp:

Environment A: The first arm follows Ber(12)\mathrm{Ber}(\frac{1}{2}) and the others follow Ber(34)\mathrm{Ber}(\frac{3}{4}).

Environment B: The second arm follows Ber(13)\mathrm{Ber}(\frac{1}{3}) and the others follow Ber(23)\mathrm{Ber}(\frac{2}{3}).

We run two different experiments for each ϵ\epsilon by changing how pp is set:

  1. Exponential period: pp is growing exponentially after each switch, with a power of 1.61.6.
  2. Constant period: p=6,250,019p=6,250,019.

We plot the regret curves of PrivDaS, AdaP-UCB and PrivateConversion for each value of ϵ\epsilon. All regrets are the average of 200200 independent trials with ±1\pm1 standard error. Link to plots. The additional numerical evaluations still empirically justify our results: For all values of ϵ\epsilon, the average cumulative regret of PrivDaS is no more than 55 times of the cumulative regret of AdaP-UCB in the stochastic experiments. The average cumulative regret of PrivDaS remains comparable to, and in some cases takes empirical advantage over, the regret of PrivateConversion in the adversarial experiments. These experiments demonstrate that our best-of-both-worlds guarantees are consistent through theoretical and empirical lens.

Ablation of PrivDaS

We compare PrivDaS with two ablation variants of it.

  1. Ablation I: We remove PrivEAP and preserve everything else.
  2. Albation II: We remove PrivBSC and preserve everything else.

We set T=230,K=2,ϵ=1512T=2^{30}, K=2, \epsilon=\frac{1}{512} and consider the following randomized adversary: For the first 2232^{23} rounds, it sets the loss by sampling from the stochastic environment (Ber(14),Ber(34))(\mathrm{Ber}(\frac{1}{4}),\mathrm{Ber}(\frac{3}{4})). After that, it selects either of the two branches with equal probability and samples the remaining loss values from it:

Branch A: the environment becomes (Ber(1),Ber(34))(\mathrm{Ber}(1),\mathrm{Ber}(\frac{3}{4})). Branch B: the environment becomes (Ber(14),Ber(0))(\mathrm{Ber}(\frac{1}{4}),\mathrm{Ber}(0)).

Note that the adversary selects branch by a fair coin toss prior to the start of the experiment, therefore it satisfies our assumption of being oblivious. Link to plot. All regrets are the average values of 200200 independent trials plotted with ±1\pm1 standard error. From the plot of average regret over all experiments, we could see that removal of either component hurts PrivDaS significantly. In the actual trials, 97 trials go to Branch A, and 103 trials go to Branch B. We also plot the regret curves in both cases separately.

For trials in Branch A, Ablation II incurs significantly more regret, indicating the cost of removing PrivBSC. For trials in Branch B, Ablation I incurs significantly more regret, indicating the cost of removing PrivEAP. This phenomenon is justified by the design of the adversary: It initially behaves as a stationary environment to provide sufficient stochastic evidence to mislead the stochastic mode of PrivDaS by making it suppress Arm 2. Subsequently, the adversary perturbs the environment into either branch. Going into Branch A makes the active arm (Arm 1) deteriorate by raising its mean loss from 14\frac{1}{4} to 11. Going into Branch B makes the eliminated arm (Arm 2) improve by dropping its mean loss from 34\frac{3}{4} to 00. In the paragraph "Basic stochasticity certificates" of Section 4, we discussed that the intuition of PrivBSC is to detect any adversarial behavior of active arms by comparing their cumulative regret against a certificate of their stochastic regret. If they differ by too much, it indicates that the active arms are incurring too much regret as compared to how much they are expected to incur in a stochastic environment. Therefore, removal of PrivBSC has made Ablation II unable to capture deterioration of an active arm and perform badly in Branch A. In the paragraph "Monitoring eliminated arms" of Section 4, we discuss that the intuition of PrivEAP is to detect any revival of an eliminated arm by comparing its post-elimination loss to a certificate of its pre-elimination loss. If it improves by too much, it indicates that an eliminated arm has become too good as compared to its pre-elimination performance. Therefore, removal of PrivEAP has made Ablation I unable to capture revival of an eliminated arm and perform badly in Branch B. Hence, this ablation study justifies the necessity of both components.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.