Fixed-Budget Differentially Private Best Arm Identification

We are grateful for your positive feedback on our paper and that you find value in our work. We present our response to your comments below.

Q1: "Unless I misunderstood, two datasets are neighboring if the set of possible rewards differ in only one location. I'm curious what the motivation for this is. For example, if we use clinical trials as the motivating example then each arm may correspond to a different treatment. In this case, I would view two datasets as neighboring if the set of observations differ at one step which could mean that all $K$ arms at a single time step have different rewards. I am curious how this impacts the results of the paper."

A1: We thank the reviewer for this insightful question. In the revised version of our paper, we have created a new Appendix C to reply to this question. Briefly, our definition of DP is equivalent to that of table-DP appearing in [1] (by making a correspondence between the notations), and the latter precisely satisfies the reviewer's expectation of ``I would view two datasets as neighboring if the set of observations differ at one step which could mean that all $K$ arms at a single time step have different rewards.'' See Definition C.2 as well as the subsequent analyses for the details.

Reference

[1] Azize, A. and Basu, D. (2023). Interactive and concentrated differential privacy for bandits. In Sixteenth European Workshop on Reinforcement Learning.

We thank the reviewer for engaging with our manuscript and providing useful feedback. We summarise your comments/questions and respond to them below.

Q1: The empirical evaluation is limited on a particular synthetic data instance.

A1: We acknowledge the limitation pointed out by the reviewer, and this is indeed an aspect that we are mindful of. The focus of our paper is primarily theoretical, aiming to establish and explore conceptual frameworks within differentially private BAI. Although the key intent of our work is to provide a strong theoretical foundation for future research and discussion, keeping in mind the importance of empirical validation, we benchmark the performance of our algorithm against existing non-private algorithms or the private adaptations thereof. We sincerely hope that the reviewer perceives this stance of ours optimistically.

Q2: ``It would be great for the authors to provide motivation to consider DP in bandit problem, especially on the best arm identification task.''

A2: Our conceptualization of differential privacy within the context of bandit problems aligns closely with established literature [1,2,3,4,5,6], particularly drawing inspiration from the work of Nikolakakis et al. [3]. While the primary objective of our work is fixed-budget BAI, it is noteworthy that the objectives in other relevant studies center around either regret minimization or fixed-confidence BAI. Importantly, these alternative settings necessitate unique analytical methodologies, yielding results distinct in nature from our own.

The underlying principle of privacy in the aforementioned body of literature, including our work, may be articulated as follows: an alteration in one of the rewards received by the learning agent should not largely influence subsequent decisions regarding the pulling of arms. To illustrate this point further, certain works posit a scenario where each time step is associated with an independent "user"; pulling arm $i$ at time $t$ provides the agent with user $t$'s "score" of arm $i$. If the score from a preceding user significantly impacts subsequent arm selections by the agent, there exists a potential inference risk for later users regarding the (private) scores of their predecessors through observations of the arm selections. Such privacy leakage can be mitigated by the application of differential privacy mechanisms tailored for bandit scenarios. In the context of the BAI task, the "agent" can be perceived as a surveyor seeking to identify the optimal item from a set of $K$ items in a market survey, while the "users" can be likened to customers participating in the survey.

Dear Reviewer mZMs,

We hope this message finds you well. The rebuttal period is scheduled to conclude on November 22nd, which is ending. We are committed to engaging all reviewers with discussions. We hope that our responses are satisfactory; if you need further clarifications, please let us know. Thank you for your time and attention.

Best regards,

Authors of 3619

We thank the reviewer for recognizing the value of our work and for your insightful comments. Below are our responses to your questions.

Q1: ``I am skeptical about their definition of DP since it is defined over length $T$ sequences. I would expect that in the online setting this definition would only be defined over a sample of sequence starting from the time when the reward sequences differ as done in joint differential privacy.''

A1: We thank the reviewer for this question. Our definition of DP indeed aligns with your expectation of ``over a sample of sequence starting from the time when the reward sequences differ''. Intuitively, this is because the future rewards have no impact on the past sequence of arm pulls. Below are further details.

Our definition of DP does not explicitly entail time steps; note that $X_{i,j}$ in Section 2 represents the $j$-th reward from arm $i$ (rather than the classical representation of reward from arm $i$ at time step $j$). In spite of the minor difference in the representation of rewards, our definition of DP is, in fact, equivalent to the notion of DP arising from the classical representation of rewards (which we call $\varepsilon$-table-DP borrowing the terminology from Azize et al. [1]). We prove this formally in the newly created Appendix C of the revised manuscript by introducing a dual decision maker who observes reward $X_{A_t,t}$ at time $t$ instead of $X_{A_t, N_{A_t, t}}$ as in our work. We then show that for any $\varepsilon$-DP policy $\pi$ of the decision maker as defined in our work, its dual decision maker's policy (or simply the dual policy) $D(\pi)$ meets the $\varepsilon$-table-DP criterion, and vice-versa (see Propositions C.4 and C.5 in the revised paper).

We note here that table-DP is based on ``a sample of sequence starting from the time when the reward sequences differ'' highlighted by the reviewer; see Corollary C.3 of the newly created Appendix C for further details.

Q2: ``I would like an intuitive explanation of why their algorithm works on a small example somewhere in the paper (maybe, in an appendix).What makes the apparent dimension go down for the first few rounds? How does decreasing the span basis vectors of the arm space lead to convergence to the optimal arm.''

A2: We thank the reviewer for the suggestion. We have now provided additional explanations in the newly created Appendix B of our revised paper (highlighted in blue). Firstly, we would like to clarify that in the first few rounds (precisely $M_1$ rounds), the dimension may not go down as the number of arms is at least $\Theta(d^2)$. Secondly, as pointed out by the reviewer, "decreasing the span" is indeed critical in identifying the best arm. This is because "decreasing the span" increases the probability that the private empirical mean of the best arm surpasses that of others, as is shown in Lemma E.2 of the original manuscript ( or Lemma G.2 of the revised version).

We remain open to elucidating any particular facet of our algorithm should the reviewer express a desire for further explanations.

Q3: Finally, the central idea of the paper is to use D-optimal design rather than G-optimal design. These ideas are theoretically equivalent (see Proposition~3 in Soare et al. NeurIPS 2014) but this paper demonstrates a dramatic performance improvement in their numerical experiments. What is the intuitive explanation for this?

A3: As pointed out by the reviewer, D-optimal design and G-optimal design are indeed theoretically equivalent. However, our Max-Det principle is rather different from D-optimal design. Note that $\gamma^*: \mathcal{A} \rightarrow [0,1]$ is a D-optimal design of vector set $\mathcal{A}$ if

There are two primary differences between D-optimal design and the Max-Det collection (defined in Definition 3.1). Firstly, the matrices of which the determinants are calculated are different. In D-optimal design, this matrix is formed by the weighted sum of some rank-one matrices of the form $aa^\top$ for $a \in \mathcal{A}$, whereas in Definition 3.1, this matrix is formed by stacking up a subset of vectors from $\mathcal{A}$ as its columns. Secondly, in D-optimal design, the weight of each vector (i.e., $\gamma^*(a)$ for $a\in \mathcal{A}$) may be any value in $[0,1]$. In contrast, in Definition 3.1, this ``weight'' of each vector in $\mathcal{A}$ can be regarded as being $0$ or $1$, depending on whether or not it belongs to the Max-Det collection.

We appreciate the reviewer's question for providing us with the opportunity to clarify the differences between D-optimal design and our Max-Det principle.

Reference

[1] Azize, A. and Basu, D. (2023). Interactive and concentrated differential privacy for bandits. In Sixteenth European Workshop on Reinforcement Learning.

We extend our sincere gratitude for your careful review of our paper. We present our response to your comments below.

Q1: ``How does DP-BAI compare to OD-LinBAI, especially when $\varepsilon \rightarrow \infty$.''

A1: When $\varepsilon \rightarrow \infty$, the upper bound on the error probability of our DP-BAI algorithm is given by

In contrast, the upper bound of OD-LinBAI is given by

Note that $H\_{\\rm BAI}$ is at least as large as $H\_{2,{\\rm lin}}$ because $H\_{\\rm BAI}=\\max\_{2\le i \le (d^2 \land K) }\frac{i}{\Delta_i^2} \ge H_{2,{\rm lin}}=\max_{2\le i \le (d \land K) }\frac{i}{\Delta_i^2}$. Hence, OD-LinBAI outperforms DP-BAI in the non-private setting (i.e., when $\varepsilon \rightarrow \infty$). However, DP-BAI outperforms DP-OD (a private adaptation of OD-LinBAI) as demonstrated in Appendix C of our original manuscript (or Appendix E of the revised version). These results are not surprising as OD-LinBAI is specifically designed for non-private settings, whereas DP-BAI is specifically designed for private settings. However, we would like to emphasize that $H_{\\rm BAI}$ shares the same form as $H_{2, {\\rm lin}}$ in that, for small $d$, it only depends on the first $d^2$ gaps ($d$ for OD-LinBAI).

Q2: ``Does this implicitly assume that $\mathcal{A}$ spans $R^{d'}$?''

Q3: ``The phrasing in these lines is confusing and seems inconsistent with earlier descriptions.''

Response to Q2 and Q3: The reviewer is verily right in these two questions. We apologize for the typos, and have revised the above highlighted sentences in Section 3 (please see the parts in blue) accordingly. Briefly: (1) Yes, we only consider the case in which $\mathcal{A}$ spans $\mathbb{R}^{d'}$. (2) Yes, your understanding of Line 8 is correct, and "randomly" was a typo appearing in the earlier description of Line 14; we have now rectified this in the revised version. We express our sincere gratitude to the reviewer for their careful reading of our manuscript.

Q4: ``Can the authors provide some high-level intuition behind the choice of $g_i$ and $h_i$ as described in equations (5) and (6)?''

A4: The rationale behind the choices of $g_i$ and $h_i$ is rooted in their role as auxiliary parameters governing the number of active arms in each phase, as outlined in (7). Adhering to the principle of successive elimination (SE) [1,2], our algorithm aims to eliminate a specific proportion of active arms in each of the $\Theta(\log d)$ phases. The determination of this proportion in each phase is crucial for achieving the overall performance guarantee. In essence, when the number of active arms in any given phase significantly exceeds $\Theta(d^2)$, the agent eliminates approximately $1-\frac{1}{\lambda}$ proportion of active arms; otherwise, it eliminates roughly half of the active arms. The threshold $\Theta(d^2)$ is pivotal in the Max-Det principle analysis. The parameter $\lambda$ in (4) is chosen to ensure that $\Theta(\log d)$ phases transpire before the number of active arms reduces to $\Theta(d^2)$ in cases where $K \gg d^2$. This leads to $g_i \approx g_{i-1}/2$ and $h_i \approx h_{i-1}/\lambda$ in equations (5) and (6), respectively. These specifications are numerically illustrated in the newly created Appendix B for clarity.

References

[1] Karnin, Z., Koren, T., and Somekh, O. (2013, May). Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pp. 1238-1246. PMLR.

[2] Yang, J., and Tan, V. (2022). Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits. Advances in Neural Information Processing Systems, pp. 12253-12266.

We are grateful for your valuable feedback. We are truly honored and encouraged by the positive evaluation and constructive feedback you provided. Below is our response.

Q: ``I still suggest the paper provide more discussion on the connections between this problem to 1) BAI in the fixed-confidence regime, 2) and generally, MAB under DP. I understand superficially speaking they are different problems, but it is not very clear (to me) whether or not there exist some connections deeper. For example, there might be a simple adaptation of previous algorithms to suit this setting.''

A: Thank you for the suggestion. Below are some comparisons between the different bandit settings.

(1) Fixed-budget BAI and regret minimization: While regret minimization inherently entails an exploration vs. exploitation dilemma, BAI (encompassing fixed-budget and fixed-confidence regimes) on the other hand is centered around pure exploration. As astutely demonstrated in the work of Zhong et al. [1], no algorithm can perform optimally for both of the above objectives simultaneously. Thus, for instance, an algorithm achieving the minimum probability of error in identifying the best arm with a fixed budget is inevitably accompanied by a larger regret value, and vice versa; for more details, see [1, Theorem 5.1]. Consequently, in the nuanced context of our work, which involves additional considerations such as differential privacy, a mere transposition of ideas from regret minimization proves insufficient to devise algorithms with near-optimal performance for the rather distinct objective of BAI.

(2) Fixed-budget BAI and fixed-confidence BAI: In the domain of pure exploration problems, two pivotal considerations, namely (a) the probability of error and (b) the stopping time required to ascertain the best arm, compete with one another. In the fixed-budget regime, a deterministic time (a.k.a. budget) $T$ is fixed, and the goal is to minimise the probability of error in determining the best arm after $T$ time steps. On the other hand, in the fixed-confidence regime, given a threshold $\delta \in (0,1)$ (a.k.a. confidence level), the goal is to minimise the expected stopping time subject to the error probability not exceeding $\delta$. A notable challenge in fixed-confidence scenarios lies in the determination of the expected stopping time, which is typically unknown to the agent. This is because the upper bound of the expected stopping time is, in general, a function of an unknown problem-specific ``hardness'' parameter, as evidenced in various works such as [2,3,4,5]. Consequently, establishing a straightforward relationship between $\delta$ in the fixed-confidence regime and the budget $T$ in the fixed-budget regime is substantially intricate.

Furthermore, it is noteworthy that while the asymptotic complexity of fixed-confidence BAI has been comprehensively characterised in the asymptotic limit as $\delta \downarrow 0$ by Garivier and Kaufmann [2], a corresponding characterisation for fixed-budget BAI (where the asymptotics is as $T \to \infty$) remains an open problem, as articulated by Qin [6]. Hence, the transposition of ideas from fixed-confidence BAI into the realm of fixed-budget BAI appears nontrivial due to the above fundamental disparities.