Differentially Private Best-Arm Identification

1. Problem Statement

The paper addresses the Best Arm Identification (BAI) problem within the Fixed-Confidence (FC) setting, augmented with Differential Privacy (DP) constraints.

• Context: In FC-BAI, an agent interacts with $K$ unknown reward distributions (arms) to identify the arm with the highest mean ($a^*$) with probability at least $1-\delta$. The goal is to minimize the sample complexity (number of pulls $\tau_\delta$) required to achieve this confidence.
• Privacy Models: The authors study two distinct trust models:
  1. $\epsilon$-Local DP (LDP): Users do not trust the central curator. Each user perturbs their own reward before sending it to the algorithm.
  2. $\epsilon$-Global DP (GDP): Users trust the central curator, who has access to raw rewards but must ensure the final output (and potentially the interaction history) satisfies DP.
• Motivation: Applications like adaptive clinical trials, hyperparameter tuning, and user studies involve sensitive data where revealing the sequence of actions or rewards could leak private information.

2. Methodology and Theoretical Framework

2.1 Lower Bounds (Sample Complexity)

The authors derive fundamental lower bounds on the expected sample complexity for any $\delta$-correct algorithm satisfying DP. A key finding is the existence of two privacy regimes:

• Low-Privacy Regime: When the privacy budget $\epsilon$ is large, the sample complexity matches the non-private lower bound (governed by the Kullback-Leibler (KL) divergence). Privacy can be achieved "for free."
• High-Privacy Regime: When $\epsilon$ is small, the sample complexity is dominated by privacy constraints.
  • For $\epsilon$-LDP: The hardness depends on the Total Variation (TV) distance squared. The lower bound involves a characteristic time $T^*_{TV2}$, scaling as $\mathcal{O}(\epsilon^{-2} T^*_{TV2})$. The distinguishability measure becomes $\min\{KL, c(\epsilon)TV^2\}$.
  • For $\epsilon$-GDP: The hardness depends on the Total Variation (TV) distance (not squared). The lower bound involves a characteristic time $T^*_{TV}$, scaling as $\mathcal{O}(\epsilon^{-1} T^*_{TV})$. The distinguishability measure is $\min\{KL, \epsilon \cdot TV\}$.

The authors prove these bounds using novel sequential coupling arguments and a generalized "change-of-measure" lemma adapted for DP, relating the KL divergence of noisy outputs to the TV distance of the underlying distributions.

2.2 Algorithm Design

The paper proposes variants of Top Two (TT) algorithms, specifically building on the TTUCB meta-algorithm (Jourdan & Degenne, 2024), which selects a "leader" and a "challenger" arm at each step.

A. For $\epsilon$-Local DP: CTB-TT

• Mechanism: Uses the Convert-To-Bernoulli (CTB) estimator based on Randomized Response.
• Strategy: It effectively transforms the original bandit instance into a modified Bernoulli instance where the means are scaled by the privacy noise.
• Performance: The algorithm is asymptotically optimal. It recovers the non-private lower bound up to a constant factor (2 in the non-private limit, 4 in the high-privacy limit).

B. For $\epsilon$-Global DP: AdaP-TT and AdaP-TT$^\star$
To handle global DP efficiently, the authors introduce the DAF ($\epsilon$) (Doubling-And-Forgetting) estimator.

• DAF Mechanism:

  1. Doubling: Updates mean estimates only when the count of pulls for a specific arm doubles.
  2. Forgetting: Discards past observations from previous "phases" (episodes) of an arm.
  3. Noise: Adds calibrated Laplace noise to the empirical mean of the current phase.
  • Significance: This structure allows the algorithm to satisfy $\epsilon$-GDP without sequential composition of privacy loss, as each phase is independent.

• AdaP-TT (Plug-in Approach):

  • Uses the DAF estimator but retains the non-private transportation costs (based on KL divergence) for the challenger selection and stopping rule.
  • Limitation: While $\delta$-correct, it is sub-optimal in the high-privacy regime for instances with heterogeneous mean gaps. It fails to match the lower bound because it does not account for the specific structure of the privacy noise in the transport cost.

• AdaP-TT$^\star$ (Adapted Approach):

  • Innovation: Modifies the transportation costs and the stopping threshold to explicitly incorporate the privacy budget $\epsilon$.
  • Mechanism: The transportation cost $W^{G,\epsilon}_{a,b}$ uses a clipped mean gap $\min\{\epsilon/2, \Delta\}$, reflecting the lower bound derived for the global setting. The stopping threshold is also adapted to be "mean-aware."
  • Performance: This algorithm achieves asymptotic optimality in the high-privacy regime (up to a small multiplicative constant, e.g., 48), matching the derived lower bound. It outperforms AdaP-TT when $\epsilon \to 0$.

3. Key Contributions

1. Fundamental Limits: First derivation of tight lower bounds for sample complexity in FC-BAI under both $\epsilon$-LDP and $\epsilon$-GDP. The work identifies that TV distance (and its square) is the natural metric for privacy-induced hardness, replacing KL divergence in the high-privacy regime.
2. Two Regimes: Rigorous characterization of the transition between low-privacy (KL-dominated) and high-privacy (TV-dominated) regimes.
3. Algorithmic Solutions:
   • CTB-TT: An optimal LDP algorithm using Randomized Response.
   • DAF Estimator: A novel private mean estimator for GDP using doubling and forgetting to avoid composition costs.
   • AdaP-TT$^\star$: The first algorithm to achieve asymptotic optimality for $\epsilon$-GDP BAI in the high-privacy regime by adapting the transportation costs to the privacy budget.
4. Empirical Validation: Extensive experiments on Bernoulli instances confirm the theoretical existence of the two regimes and the superiority of AdaP-TT$^\star$ over existing baselines (like DP-SE) and the plug-in approach (AdaP-TT) in high-privacy settings.

4. Results

• Lower Bounds:
  • LDP: $E[\tau_\delta] \gtrsim \max(T^*_{KL}, \epsilon^{-2} T^*_{TV2})$.
  • GDP: $E[\tau_\delta] \gtrsim \max(T^*_{KL}, \epsilon^{-1} T^*_{TV})$.
• Upper Bounds:
  • CTB-TT: Matches the LDP lower bound up to a constant factor (limit is 4 as $\epsilon \to 0$).
  • AdaP-TT: Matches the non-private bound up to a factor of 16 in the low-privacy regime but is sub-optimal in the high-privacy regime.
  • AdaP-TT$^\star$: Matches the GDP lower bound up to a constant factor (limit is 48 as $\epsilon \to 0$) in the high-privacy regime.
• Adaptivity: The proposed algorithms require only $O(K \log^2(T^*_{KL} \log(1/\delta)))$ rounds of adaptivity (batches), making them practical for settings where frequent communication is costly.

5. Significance

This paper bridges a critical gap in the literature by moving beyond regret minimization to Best Arm Identification under differential privacy.

• Theoretical Impact: It establishes that the "cost of privacy" in BAI is fundamentally different from regret minimization, relying on Total Variation distances rather than just KL divergence. It provides the first matching upper and lower bounds for the high-privacy regime in global DP.
• Practical Impact: The proposed algorithms (especially AdaP-TT$^\star$) offer a practical framework for conducting privacy-preserving adaptive experiments (e.g., clinical trials, A/B testing) where identifying the optimal treatment or parameter is the goal, rather than just minimizing cumulative loss. The "Doubling-And-Forgetting" technique provides a robust method for managing privacy budgets in sequential learning without excessive noise accumulation.