Faster Rates for Private Adversarial Bandits

We thank the reviewer for noting that the problem setting is interesting and that our results would improve upon previous rates. We address the reviewer's concerns below.

The most important mistake I found is perhaps the following: in Theorem 1...

We had a typo in the definition of $\tilde R_B(T, K, \lambda)$ on lines 251-252. The correct definition is:

$\tilde R_B(T, K, \lambda) := \sup_{\ell_{1:T}} \left( \mathbb{E}\left[\sum_{t=1}^T \tilde \ell_t(B(\tilde H_t))\right] - \min_{i \in [K]} \mathbb{E}\left[ \sum_{t=1}^T \tilde{\ell}_t(i) \right] \right)$

so that

$\tilde R_B(T, K, \lambda) = \sup_{\ell_{1:T}} \left( \mathbb{E}\left[\sum_{t=1}^T \ell_t(B(\tilde H_t))\right] - \min_{i \in [K]} \sum_{t=1}^T \ell_t(i) \right) = \sup_{\ell_{1:T}} \left( \mathbb{E}\left[\sum_{t=1}^T \ell_t(B(\tilde H_t)) - \min_{i \in [K]} \sum_{t=1}^T \ell_t(i) \right]\right)$

The first equality in the equation above is due to the fact that the noise added to $\ell_{1:T}$ is zero-mean and the last equality is due to the fact that the true losses $\ell_1, ..., \ell_T$ are not random. That is, $\tilde R_B(T, K, \lambda)$ is the expected regret of the bandit algorithm $B$ on the original losses when it only observes noisy losses, where the amount of noise is captured by $\lambda$. In Appendix D, we establish bounds on $\tilde R_B(T, K, \lambda)$ when $B$ is taken to be EXP3 and FTPL respectively (see Lines 895 and 1064 in the updated submission). Line 826 in the proof of Theorem 1 now follows by definition of $\tilde R_B(T, K, \lambda)$ since $I_1, I_2, ...$ represent the actions taken by Algorithm 1 when updated on the noisy losses (as guaranteed by Line 9 in Algorithm 1). We have made this change to the manuscript and have highlighted it in blue. While $\tilde R_B(T, K, \lambda)$ may be an unusual definition, it enables us to provide a generic conversion of a non-private bandit algorithm into a private bandit algorithm. We believe this generality is useful as it allows one to construct private bandit algorithms from off-the-shelf bandit algorithms in a black-box way.

For example, in the proof of Theorem 3, is ambiguously defined...

We thank the reviewer for noting that $j^*$ in the proof of Theorem 3 is ambiguously defined. We have fixed this in the manuscript and highlighted in blue.

Some notations are not defined...

We thank the reviewer for pointing out the fact that $\tilde R_{B}(T/\tau, 1/(\tau \epsilon))$ is not defined in the Proof of Theorem 1. This is a typo and should read $\tilde R_{B}(T/\tau, K, 1/(\tau \epsilon)).$ We have fixed this in the final version.

In general, the authors exchange "min" and "$\mathbb{E}$" with too little caution...

With regards to swapping infimums with expectations, we have checked all expectations in the paper and confirmed that every time an infimum is inside an expectation, the object that is being minimized is not random. Accordingly, there should be no problem swapping the infimum and expectation. Actually, we can even drop the expectation surrounding the infimum term since it is not random. We will make sure to do this in the final version.

I thanks the authors for clarifying some points in their proofs.

In particular, I thank them for correcting their definition of the regret $\tilde R_B(T, K, \lambda)$. It seems that Theorem 1 remains correct with this new definition, and that the proofs of the corollaries now hold.

I still find that the proofs overall lack rigor: for example, in the proof of Corollary 1, on Line 927, to apply Lemma 12 the expectations should be taken with regards to the randomness of $I(t)$, conditionally on the Laplace noise (Lemma 12 applies for deterministic losses) and on the event $E^c$, before taking expectations with regards to the noise itself. To make the proofs easier to read, I strongly suggest to introduce specific notations to highlight the randomness with regards to which the expectation is taken.

Overall, I think that the reduction scheme used to apply smaller noise on batched loses is natural in a central DP setting. I am not convinced that the proof technics are particularly new, however they improve on previous rates shed light on a interesting separation between central and local DP.

As a further remark, I find the presentation of the results as a collection of algorithms and bounds somewhat challenging to follow. In particular, it is unclear why the authors apply their reduction scheme to such a wide range of algorithms, some of which yield suboptimal rates. Perhaps algorithms and results that are either suboptimal or differ only by minor variations in absolute numerical constants or logarithmic factors could be moved to the Appendix for clarity?

We thank the reviewer for noting that our upper bounds are "achieved through neat tricks" and that our lower bounds are an "initial and important step towards characterizing the minimax regret in adv. MAB with central DP." Before we address the reviewer's concerns, we would like to point out that the main contribution/focus of our paper is the improved upper bounds and their implications. For example, our upper bounds in the adversarial bandit setting imply that:

• There exists a separation in the achievable regret bounds between oblivious and adaptive adversaries. In particular, while we show that sublinear regret bounds are possible for all choices of $\epsilon \in \omega(\frac{1}{T})$ under an oblivious adversary, this is not the case for an adaptive adversary, where one cannot achieve sublinear regret if $\epsilon \in o(\frac{1}{\sqrt{T}})$ [Asi et al. 2023].
• This is the first work to show that sublinear regret bounds are possible for all choices of $\epsilon \in \omega(\frac{1}{T})$. This establishes a separation between the achievable regret bounds under central and local differential privacy, since for the latter it is well known that sublinear regret is not possible if $\epsilon \in o(\frac{1}{\sqrt{T}}).$

Previous results on private adversarial bandits do not shed light on whether such separations existed. In addition, we give the first upper bounds for private adversarial bandits with expert advice. We now address the reviewer's concerns.

...in this paper, it is only shown for certain algorithms (which satisfy conditions (1) and (2) defined around Line 2108)...

We acknowledge the limitations of our lower bound in the sense that it is algorithm-specific. However, we want to highlight that this is the first attempt at a lower bounds for private adversarial bandits, and that existing techniques in private online learning do not give non-trivial lower bounds. As such, we believe our algorithm-specific lower bound is non-trivial progress.

It's hard to tell how broad algorithm classes...

We give some intuition about what the two conditions mean around lines 2110-2119, and will add more discussion on these in the final version. At a high level, our lower bounds apply to algorithms which, when run on $\ell_{1:T}$ where $\ell_t(1) = \frac 1 2$ and $\ell_t(2) = 1$, drops the probability of action $2$ to $\gamma$ reasonably quickly and maintains the probability of action $2$ at $\gamma$ afterward. Condition (1) is not really an assumption as one should set $\gamma = O\left(\frac{R_{A}(\ell_{1:T})}{T}\right)$, where $R_{A}(\ell_{1:T})$ denotes the expected regret of $A$ when run on $\ell_{1:T}$. Then, condition (1) is trivially satisfied by any $A$, while condition (2) roughly states that $A$ drops the probability of playing action $2$ to around $O\left(\frac{R_{A}(\ell_{1:T})}{T}\right)$ by round $\tau$, and keeps it there. In other words, after round $\tau$, $A$ plays action $2$ on average $p$ times in $\frac{p}{\gamma} \approx O(\frac{p T}{R_{A}(T)})$ rounds. The latter property is reasonable for bandit algorithms given that $\ell_t(2) - \ell_t(1) = \frac{1}{2}$ for all $t \in [T]$, and thus any low-regret bandit algorithm should not be playing action $2$ often. Indeed EXP3 drops probabilities of bad arms fast enough that this condition immediately holds. We give a proof sketch below that our lower bound of $\Omega(\sqrt{T/ \epsilon})$ holds for any batched EXP3 algorithm (i.e., with any parameters), and we will add this discussion to the final version.

Batched EXP3 on the loss sequence $\ell_{1:T}$, where $\ell_t(1) = 1/2$ and $\ell_t(2) = 1$, has regret at least $\gamma T + \kappa/\eta$, where $\kappa$ is the batch size. Assume, towards a contradiction that for some setting of parameters, this was $o(\sqrt{T/\epsilon})$. This implies that $\gamma$ is $o(1/\sqrt{\epsilon T})$, and that $\kappa/\eta$ is $o(\sqrt{T/\epsilon})$. EXP3 drops the probability of a bad arm to $O(\gamma)$ in $\log (1/\gamma)/\eta$ steps, and the batched version will do so in $\kappa\log (1/\gamma)/\eta$ steps. Thus condition (2) is satisfied with $\tau$ being $o(\sqrt{T/\epsilon})$ and $p=\frac 1 \epsilon$ (ignoring logarithmic factors). This then yields a lower bound of $\omega(\sqrt{T/\epsilon})$ using Lemma 13, which contradicts the assumption. Thus the regret has to be $\Omega(\sqrt{T/\epsilon})$ up to logarithmic factors.

Could the authors please comment on any potential inspirations from Lemma 13?

We do not believe that the same construction can lead to fully general lower bounds. The lower bound rules out a large class of algorithms, and this may help lead us to a better algorithm. If there isn't a better algorithm, we suspect that we will need to construct the hard loss sequences in an algorithm-specific way, e.g. by simulating the bandit algorithm and using its internal state. This sort of technique was recently used to establish lower bounds for private online counting [Lyu et al. 2024].

We thank the reviewer for their comments and address their concerns below.

Maybe the authors can highlight more on the technical challenge...

Batching is an old technique in the history of bandit, and more generally, online learning algorithms. [Tossou and Dimitrakakis 2017] considered the batched version of EXP3 and used the internal randomness of EXP3 alone to argue about its privacy. Unfortunately, their privacy analysis is flawed as privately releasing only the selected action is not enough to ensure the overall privacy of EXP3 due to its use of Inverse Propensity Weighted estimators. In fact, in Appendix G, we provide evidence that EXP3 is actually inherently non-private. To overcome this issue, we additionally add noise to the batched losses, and only use the randomness of the batched losses to argue about privacy. However, by using noisy batched losses, we require that our base bandit algorithms to be able to handle negative and heavy-tailed losses. This is non-trivial requirement and more care needs to be taken when deriving regret bounds for adversarial bandits with negative losses. In fact, the standard regret analysis for adversarial bandit algorithms do not work if the losses can be negative and potentially unbounded. This is why we make sure to derive the regret bounds of EXP3, FTPL, and FTRL under negative losses explicitly in the Appendix. In addition, by considering noisy batched losses, we are able to establish a connection between privacy and the vast literature on heavy-tailed bandits. In particular, our reduction shows that any heavy-tailed bandit algorithm, like the ones we presented, can be converted into a private bandit algorithm. This allowed us to eventually remove log factors in $K$ and $T$ that EXP3 would give with our reduction.

There are some places that the author claims "not too hard" to obtain...

We will remove our wording of "not too hard" and "easy" throughout the text and be more explicit in the final version.

Line 2077 and below: please provide...

With regards to Line 2077 and the claim about $P_t(2)$, we provide a sketch of the proof below and will elaborate more in the final version. Fix $t \geq 2$ and suppose that $I_t = 1$. Then, by definition, for the loss sequence $\ell_{1:T}$, we have that $w_{t+2}(1) = w_{t+1}(1) = w_t(1) \exp\{\frac{-\eta}{P_t(1)}\}$ and $w_{t+2}(2) = w_t(2) \exp\{\frac{-\eta}{1 - P_{t+1}(1)}\}.$ Since $I_t = 1$, we know that $P_{t+1}(1) < P_t(1)$ and therefore $w_{t+2}(2) > w_t(2) \exp\{\frac{-\eta}{1-P_t(1)}\}$. Now, if $P_t(1) < \frac{1}{2}$, then $w_{t+2}(1) / w_{t+2}(2) < w_t(1) / w_t(2) < 1$. Accordingly, $P_{t+2}(1) < 1/2$, and repeating the analysis would eventually show that $w_t(1)/w_t(2) \rightarrow 0$, implying that $P_t(2) \rightarrow 1 - \frac{\gamma}{2}.$ A symmetric argument shows that if $P_t(1) > 1/2$, then $w_t(2)/w_t(1) \rightarrow 0$, and therefore $P_t(2) \rightarrow \frac{\gamma}{2}.$ Since the two loss sequences $\ell_{1:T}$ and $\ell^\prime_{1:T}$ are identical after time point $t = 2$, an identical argument holds for $\ell^\prime_{1:T}$. To complete the proof sketch, note that for loss sequence $\ell_{1:T}$, $I_4 = 1$ and $P_4(1) < \frac{1}{2}$, thus $P_t(2) \rightarrow 1 - \frac{\gamma}{2}.$ On the other hand, for loss sequence $\ell^\prime_{1:T}$, $I_2 = 1$ and $P^\prime_2(1) > \frac{1}{2}$, giving that $P^\prime_t(2) \rightarrow \frac{\gamma}{2}.$

We have also verified this claim experimentally and included a Figure displaying the results of our simulation and the code used. These are highlighted in blue and exhibit the rapid divergence in the probabilities of selecting action 2 between the two loss sequences.

Line 2187: can the authors provide...

We thank the reviewer for catching this typo. It should be $t' \geq \tau + \frac{p}{\gamma}$ on line 2187.

I wonder whether the lower bound mentioned in the last section (or Appendix G.2) applies...

We give a proof sketch below that our lower bound $\Omega(\sqrt{T/ \epsilon})$ holds for any batched EXP3 algorithm (i.e., with any parameters). We will add this discussion to the final version.

Batched EXP3 on the loss sequence $\ell_{1:T}$, where $\ell_t(1) = 1/2$ and $\ell_t(2) = 1$, has regret at least $\gamma T + \kappa/\eta$, where $\kappa$ is the batch size. Assume, towards a contradiction that for some setting of parameters, this was $o(\sqrt{T/\epsilon})$. This implies that $\gamma$ is $o(1/\sqrt{\epsilon T})$, and that $\kappa/\eta$ is $o(\sqrt{T/\epsilon})$. EXP3 drops the probability of a bad arm to $O(\gamma)$ in $\log (1/\gamma)/\eta$ steps, and the batched version will do so in $\kappa\log (1/\gamma)/\eta$ steps. Thus condition (2) is satisfied with $\tau$ being $o(\sqrt{T/\epsilon})$ and $p=\frac 1 \epsilon$ (ignoring logarithmic factors). This then yields a lower bound of $\omega(\sqrt{T/\epsilon})$ using Lemma 13, which contradicts the assumption. Thus the regret has to be $\Omega(\sqrt{T/\epsilon})$ up to log factors.