Technical flaw in Tao et al. 2022. Sure, we have provided a detailed discussion on it, which points out the incorrect step in their upper bound proof (see the above general response).

Novelty of Algorithm 1. We remark on the novelty (or insight) of Algorithm 1 from the perspectives of algorithmic design and analysis, respectively.

1. Algorithmic design: We use random response for privacy rather than the Laplace mechanism. This is due to the key observation that under corruption and LDP, the Laplace mechanism no longer gives the optimal rate, highlighting the interesting interplay of corruption and LDP.

2. Analysis: One key novelty in our analysis is that Algorithm 1 can adaptively give optimal rates for all three different scenarios (LTC, CTL, and C-LDP-C) for bounded data.

Hyper-parameter tuning. Yes, our MAB algorithms need to determine the optimistic or pessimistic radius, which requires us to know $\epsilon$, $\alpha$, $k$, and some constant $c$. We first note that even in non-private, non-corrupted cases, the radius also requires tuning with respect to $c$ in practical implementations. Regarding other parameters (in particular $\alpha$), we tend to believe that it is necessary to be known in advance to guarantee optimal rates. Finally, to achieve the optimal rate in CTL, one has to carefully choose the right radius, while C-LDP-C (corruption-LDP-corruption) can be the same as LTC.

Other exploration strategies. In this paper, we use UCB as an example. Since the key step in other variants (like Thompson sampling) also relies on a tight mean estimation, we believe one can generalize our results to other exploration strategies.

We thank the reviewer for your time and review. Below is our response to the comments.

Presentation. Thanks for the suggestion on the presentation. We will try to incoprate them in the final version, e.g., a summary table.

Practical scenarios of LTC and CTL Yes, we have already briefly discussed them in Appendix C.1.

Important contributions compared to previous works. Our result cannot be obtained by directly following previous works.

1. Even without corruption, the state-of-the-art result is ungrounded. We discuss it further above (see the general response), which highlights the incorrect step in the upper bound proof of Tao et al. 2022. This complements the points we have made from the lower bound perspective.

2. In contrast to Wu et al. 2023's setting of corruption plus central DP, where the standard Laplace mechanism will work, we have shown that the Laplace mechanism will only give a sub-optimal rate in the setting of local DP plus corruption. See Remark 4.

We thank the reviewer for your time and review. We will provide our response below.

Online MAB. In this paper, as in previous work (e.g., Wu et al 2023), we treat $\alpha$ as a constant (i.e., it does not scale with $T$). Thus, the third term in big-O of Proposition 4 is a lower order term as $T \to \infty$, which gives us Theorem 2.

Offline MAB. There is a typo in Proposition 5, i.e., the exponent term of $1-1/k$ is missing. Our proof in Appendix J indeed has the right one, which matches the upper bound in Proposition 6. The updated lower bounds in Proposition 5 are shown below:

(i) LTC: $\mathrm{SubOpt}^{\ast}_{\mathrm{LTC}}(\beta^{\ast}, k, \epsilon, \alpha, N) \geq \Omega\left(\left(\frac{\alpha}{\epsilon}\right)^{1-1/k} + \left(\frac{1}{\epsilon} \sqrt{\frac{\beta^{\ast}}{N}}\right)^{1-1/k}\right)$

(ii) CTL: $\mathrm{SubOpt}^{\ast}_{\mathrm{CTL}}(\beta^{\ast}, k, \epsilon, \alpha, N) \geq \Omega\left(\alpha^{1-1/k} + \left(\frac{1}{\epsilon} \sqrt{\frac{\beta^{\ast}}{N}}\right)^{1-1/k}\right)$

Technical flaw in Tao et al. 2022. Please see our general response above.