Faster Rates for Private Adversarial Bandits

We thank the reviewer for their comments. We address the reviewer's main concern below and hope that they will reevaluate their score accordingly.

Therefore, it is not entirely fair to directly compare the results with prior work, as the improvement may stem from this assumption.

While adaptive adversaries are well-studied in non-private bandit literature, oblivious adversaries have been the main focus in the private bandit literature. In particular, there are only two previous works that study private adversarial bandits, namely Tossou & Dimitrakakis (2017) and Agarwal & Singh (2017). In the last two paragraphs of Section 2.1, Tossou & Dimitrakakis (2017) make explicit that they first consider an oblivious adversary. They then note that their guarantees can be apply to an $m$-bounded adaptive adversary. As for Agarwal & Singh (2017), Theorem 4.1 makes it clear that they only consider an oblivious adversary as the sequence of loss vectors is fixed before the game begins. Nevertheless, if one considers an adaptive adversary, then the lower bound from Asi et al. (2023) shows that sublinear regret is not possible under pure differential privacy even for a constant $\epsilon$. Moreover, for approximate differential privacy, the lower bounds from Asi et al. (2023) show that sub linear regret is not possible if $\epsilon \leq \frac{1}{\sqrt{T}}.$ Thus, the adaptive adversary case is not as interesting because existing algorithms are already optimal (up to log factors).

The definition of differential privacy should be refined...

Our definitions of differential privacy (see Definitions 2.3 and 2.4) do include $\delta$, and this is the standard $\delta$ which people use to capture failure probability.

Additionally, in lines 236-237, there is a contradiction between the stated upper bound and the previously established lower bound.

Our algorithm obtaining the upper bound in Corollary 3.2 satisfies the notion of central differential privacy. Therefore, the lower bound from Basu et al. (2019) does not apply here as it hold for the more strict notion of local differential privacy. We will clarify this in the paper. We will also make sure to include an explicit definition of local differential privacy in the camera-ready version.

(Q1) While the Generic Conversion method is well-motivated, it is unclear which of the three different results for Bandits with Experts is the best, and what specific advantages the other algorithms provide.

None of the regret guarantees of our three algorithms strictly dominate the other. Below, we highlight three regimes and the corresponding algorithm that obtains the best regret bound in that regime. We will make sure to include this detailed comparison in the final version.

Low-dimension and High Privacy ($N \leq K$): In this regime, our upper bound $O(\frac{\sqrt{NT}}{\sqrt{\epsilon}})$ is superior.

High-dimension and Low Privacy ($N \geq K$ and $\epsilon \geq \frac{K}{N}$): In this regime, our second upper bound $O(\frac{\sqrt{KT \log N} \log(KT)}{\epsilon})$ is superior.

High-dimension and High Privacy ($N \geq K$ and $\epsilon \leq \frac{1}{\sqrt{T}}$): In this regime, our third upper bound $O(\frac{N^{1/6}K^{1/2}T^{2/3}\log(NT)}{\epsilon^{1/3}} + \frac{N^{1/2}\log(NT)}{\epsilon})$ is superior.

These are all regimes that are interesting in practice, so its important to get the best rates for each one of these regimes.

(Q2) However, it is unclear why this method fails to achieve a $1/\sqrt{\epsilon}$ dependency in the second and third regret guarantees.

The second guarantee (Theorem 4.4) actually does not use the batching method. Instead, it simply adds Laplace noise to each loss vector. Thus, one should not expect to get a $\frac{1}{\sqrt{\epsilon}}$ here, as this approach actually gives a stronger, local DP guarantee. We will make this more explicit in the camera ready version. As for the third guarantee, this is more subtle and occurs because more noise needs to be added to privatize the batched expert losses. We will include a more complete discussion in the camera-ready version.

(Q3) However, it remains unclear whether the batch learning framework with a batch size of can effectively remove the logarithmic dependency on compared to previous work...

Our technique allows us to improve upon existing regret bounds in terms of both $\epsilon$ and $T$. As the reviewer noted, our batching with noise technique allows to improve the dependence on $\epsilon$ from $1/\epsilon$ to $1/\sqrt{\epsilon}.$ However, our technique also allows us to expand the set of bandit algorithms that we can privatize beyond EXP3. In particular, we are now able to privatize heavy-tailed bandit algorithms which do not have $\log{T}$ terms in their regret bounds, one of which is the HTINF algorithm from Huang et al. (2022). Because our reduction carries over the regret bound from the base bandit algorithm, we are able to remove a log factor in $T.$

We thank the reviewers for their comments. We address their concerns below and hope they will reevaluate their score accordingly.

No experiments.

We acknowledge the concern regarding the lack of experiments. However, our work is intentionally theoretical, aimed at understanding fundamental rates and limits of private adversarial bandits. Theoretical contributions often provide key insights that guide future empirical research. While experimental validation is certainly valuable, we believe that our results are meaningful in their own right and align with the norms of theoretical research in this area.

(Q1) How do the proposed algorithm compare experimentally to the SOTA?

Our paper is mainly theoretical in nature. That said, we agree with the reviewer that this is an important direction of future work.

Could alternative privacy mechanisms improve regret rates?

This is a great question. We believe that one way to improve our regret bounds is through the use of the Binary Tree Mechanism, which has been used to obtain private regret guarantees in the full-information setting. However, our current attempts at doing have been unsuccessful. In particular, some subtleties arise in the bandit setting as one needs to deal with unbiased estimates of the true loss, whose sensitivity can be massive. We will make sure to discuss this in the camera-ready version.

How does the proposed approach generalize to contextual bandits?

The bandits with expert advice setting can be viewed as the contextual version of the traditional adversarial bandit setting [1]. Accordingly, our results in Section 4 show that our techniques do extend to the contextual setting. Table 1 summarizes the exact regret bounds we achieve for the bandits with expert advice setting.

[1] Auer, Peter, et al. "The nonstochastic multiarmed bandit problem." SIAM journal on computing 32.1 (2002): 48-77.

We thank the reviewer for their comments and noting that our work advances the frontier of privacy-preserving algorithms and could have a broader impact. We address the reviewer's main concern below and hope they reevaluate their score accordingly.

Does Lemma 5.1 rule it out?

The reviewer is correct in that Lemma 5.1 does not rule out the possibility that the algorithm from Tossou & Dimitrakakis (2017) obtains a regret of $O(\frac{T^{2/3} \sqrt{K \log K}}{\epsilon^{1/3}})$ as this upper bound is larger than our lower bound $O(\sqrt{T/\epsilon})$ in Lemma 5.1. Nevertheless, even if one considers the upper bound $O(\frac{T^{2/3} \sqrt{K \log K}}{\epsilon^{1/3}})$, our upper bound of $O(\sqrt{KT/\epsilon})$ in Corollary 3.2 is strictly better for all $\epsilon \leq 1$.

In Line 1850, Shouldn't...”?

Yes, this is a typo and the reviewer is correct. We will make sure to fix this in the camera-ready version.

We thank the reviewer for their comments. We address their concerns below and hope they will reevaluate their score accordingly.

in line 43-44, "Motivated by this gap", which gap?

By this phrase, we are referring to our comment in the previous sentence on lines 38-40: "it was not known how large $\epsilon$ needs to be to obtain sublinear expected worst-case regret." We will clarify this in the final version.

"it is well known that this is not the case for local differential privacy." then what is your contribution?

In this paper, we study the weaker notion of central differential privacy. Our results (Corollary 3.2) shows that under central differential privacy constraints, sub-linear regret is possible even when $\epsilon \leq \frac{1}{\sqrt{T}}.$ This is not the case under the strict notion of local differential privacy, where sublinear regret is not possible if $\epsilon \leq \frac{1}{\sqrt{T}}.$ Hence, our results establish a separation between central and local differential privacy in terms of when sublinear regret can be achieved.

No experiments

We acknowledge the reviewer's concern. However, our work is intentionally theoretical, aimed at understanding fundamental rates and limits of private adversarial bandits.

(Q1) The regret of $O(\sqrt{KT \log K}/\epsilon)$ is for the local differential privacy model...

Since local differential privacy is stronger than central differentially privacy, any $\epsilon$-locally differentially private algorithm is also an $\epsilon$-centrally differentially private algorithm. Accordingly, comparing our regret bounds against $O(\sqrt{KT \log K}/\epsilon)$ is still meaningful since this is the only known regret bound for adversarial bandits under central differential privacy. That is, we don't intend to compare our CDP results with LDP; it just happens to be the case that the previous best known regret bound for adversarial bandits under CDP is $O(\sqrt{KT \log K}/\epsilon)$.

(Q2) What are the same points and differences among the three algorithms?

For bandits with expert advice, we give three different algorithms/regret bounds to cover different combinations of small and large $K, N$ and $\epsilon.$ In particular, amongst the three algorithms we give, none of their regret bounds strictly dominate the other -- there are certain choices of $K, N$ and $\epsilon$, where the regret bound of one algorithm is better than the other. Below, we highlight three regimes and the corresponding algorithm that obtains the best regret bound in that regime. We will include this detailed comparison in the final version.

Low-dimension and High Privacy ($N \leq K$): Our upper bound $O(\frac{\sqrt{NT}}{\sqrt{\epsilon}})$ is superior.

High-dimension and Low Privacy ($N \geq K$ and $\epsilon \geq \frac{K}{N}$): Our second upper bound $O(\frac{\sqrt{KT \log N} \log(KT)}{\epsilon})$ is superior.

High-dimension and High Privacy ($N \geq K$ and $\epsilon \leq \frac{1}{\sqrt{T}}$): Our third upper bound $O(\frac{N^{1/6}K^{1/2}T^{2/3}\log(NT)}{\epsilon^{1/3}} + \frac{N^{1/2}\log(NT)}{\epsilon})$ is superior.

These regimes are all interesting in practice, so it's important to get the best rates for each one. With regards to the algorithms, two out of the three algorithms, namely those obtaining the guarantees in Corollary 4.3 and Theorem 4.5, use the batching plus noise technique. The last algorithm, the one obtaining the guarantee in Theorem 4.4, does not batch and adds noise to each loss vector.

(Q3) What is the exact information you want to protect?

We are taking only the sequence of loss functions as the sensitive information. This is made explicit in our definition of differential privacy in Definition 2.4 and is standard in the private bandit literature.

(Q4) Why did you choose pure differential privacy?

Pure differential privacy is a stronger privacy guarantee and often easier to derive minimax rates for. Surprisingly, and unlike under full-information online learning, we found that even under pure differential privacy, the minimax rates for adversarial bandits were not known. This motivated our study of pure differential privacy.

(Q5) Compare your results with related work.

We will make sure to include a comparison in the final version. For HTINF, the non-private version achieves a regret bound of $O(\sqrt{TK})$ whereas our private version achieves a regret bound of $O(\frac{\sqrt{TK}}{\sqrt{\epsilon}} + \frac{1}{\epsilon}).$ So, the blow is by a factor of $O(\frac{1}{\sqrt{\epsilon}}).$

(Q6) There is a gap of the factor of $\sqrt{K}$ between your upper bound and lower bound.

This gap comes from the fact that in our lower bound we only consider a setting with two arms. It should be possible to upgrade of lower bound with a factor of $K$ using the standard strategy for proving lower bounds for adversarial bandits, but we leave this for future work.