# Optimal Best Arm Identification under Differential Privacy

Marc Jourdan, Achraf Azize

► To cite this version:

Marc Jourdan, Achraf Azize. Optimal Best Arm Identification under Differential Privacy. NeurIPS 2025 - 39th Annual Conference on Neural Information Processing Systems, Dec 2025, San Diego, United States. hal-05393608

HAL Id: hal-05393608

https://inria.hal.science/hal-05393608v1

Submitted on 2 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Optimal Best Arm Identification under Differential Privacy

Marc Jourdan*

EPFL, Lausanne, Switzerland
marc.jourdan@epfl.ch

Achraf Azize*

FairPlay Joint Team, CREST, ENSAE Paris
achraf.azize@ensae.fr

## Abstract

Best Arm Identification (BAI) algorithms are deployed in data-sensitive applications, such as adaptive clinical trials or user studies. Driven by the privacy concerns of these applications, we study the problem of fixed-confidence BAI under global Differential Privacy (DP) for Bernoulli distributions. While numerous asymptotically optimal BAI algorithms exist in the non-private setting, a significant gap remains between the best lower and upper bounds in the global DP setting. This work reduces this gap to a small multiplicative constant, for any privacy budget $\epsilon$. First, we provide a tighter lower bound on the expected sample complexity of any $\delta$-correct and $\epsilon$-global DP strategy. Our lower bound replaces the Kullback-Leibler (KL) divergence in the transportation cost used by the non-private characteristic time with a new information-theoretic quantity that optimally trades off between the KL divergence and the Total Variation distance scaled by $\epsilon$. Second, we introduce a stopping rule based on these transportation costs and a private estimator of the means computed using an arm-dependent geometric batching. En route to proving the correctness of our stopping rule, we derive concentration results of independent interest for the Laplace distribution and for the sum of Bernoulli and Laplace distributions. Third, we propose a Top Two sampling rule based on these transportation costs. For any budget $\epsilon$, we show an asymptotic upper bound on its expected sample complexity that matches our lower bound to a multiplicative constant smaller than 8. Our algorithm outperforms existing $\delta$-correct and $\epsilon$-global DP BAI algorithms for different values of $\epsilon$.

## 1 Introduction

The stochastic Multi-Armed Bandit (MAB) is an interactive sequential decision-making model [Bubeck et al., 2012; Lattimore and Szepesvári, 2020], introduced by William R. Thompson [Thompson, 1933]. Thompson's motivation for studying MABs is to design clinical trials that adapt treatment allocations on the fly as the medicines appear more or less effective. Specifically, in MABs, a learner interacts with $K \in \mathbb{N}$ unknown probability distributions, referred to as *arms*. In clinical trials, the arms are the candidate medicines, while the observations are patient reactions, 1 if the patient is cured and 0 otherwise. The learner aims to identify the arm with the highest average efficiency, i.e., the medicine that cures most patients in expectation. Given a fixed error $\delta \in (0, 1)$, Best Arm Identification (BAI) [Audibert and Bubeck, 2010b; Jamieson and Nowak, 2014] algorithms in the fixed confidence setting [Even-Dar et al., 2006; Gabillon et al., 2012; Garivier and Kaufmann, 2016] suggest a candidate answer that coincides with the optimal arm with probability more than $1 - \delta$, while using as few samples as possible.

BAI algorithms have been increasingly deployed in data-sensitive applications, such as adaptive clinical trials [Thompson, 1933; Robbins, 1952; Aziz et al., 2021], pandemic mitigation [Libin et al., 2019],

<footnote>*Equal Contribution</footnote>
user studies [Losada et al., 2022], crowdsourcing [Zhou et al., 2014], online advertisement [Chen et al., 2014], hyperparameter tuning [Li et al., 2017], and communication networks [Lindståhl et al., 2022], to name a few. Due to the adaptive nature of these procedures, critical data privacy concerns are raised [Tucker et al., 2016], as exemplified by the adaptive dose finding trial. For each new patient $n$, a physician chooses a dose level $a_n \in [K] := \{1, \dots, K\}$ based on previous observations, and collects a binary observation measuring the effect of the selected dose on the patient. Crucially, the patients’ reactions might reveal information regarding their health. Subsequently, these outcomes will guide the physician’s decision for future patients. Eventually, the physician adaptively decides to stop the trial and recommends a dose $\hat{a}_{\tau_{\delta}}$ after collecting $\tau_{\delta}$ samples, referred to as *sample complexity*. Even if those outcomes are kept secret, the experimental findings and protocol are detailed thoroughly to the health authorities. This report contains the sequence of chosen dose levels $(a_n)_{n \le \tau_{\delta}}$ and the recommended dose level $\hat{a}_{\tau_{\delta}}$, both indirectly leaking information regarding the patients involved in the trial. This example underscores the need for privacy-preserving fixed-confidence BAI algorithms.

We adopt the Differential Privacy (DP) framework [Dwork and Roth, 2014], which bounds the influence of any single data point. Given a privacy budget $\epsilon$, we consider the $\epsilon$-global DP constraint that assumes the existence of a trusted curator (e.g., the physician running the clinical trial), who observes the outcomes and ensures privacy when publishing these findings. While $\epsilon$-global DP is well-studied in regret minimization [Mishra and Thakurta, 2015; Azize and Basu, 2022; Azize et al., 2025], its impact on fixed-confidence BAI is less understood [Sajed and Sheffet, 2019; Kalogerias et al., 2021]. A significant gap remains between the existing lower and upper bounds [Azize et al., 2023, 2024]. This paper reduces this gap to a small constant for any privacy budget $\epsilon$. Appendix C.1 contains a detailed literature review.

**Contributions.** Our contributions for fixed-confidence BAI under $\epsilon$-global DP are threefold.

**1. Lower bound under global DP.** We derive a novel information-theoretic lower bound on the expected sample complexity of any $\delta$-correct and $\epsilon$-global DP BAI algorithms (Theorem 2). Our lower bound replaces the Kullback-Leibler (KL) divergence in the transportation cost of the non-private characteristic time with an information-theoretic quantity $d_{\epsilon}$ (Eq. (1)) that smoothly interpolates between the KL divergence and the Total Variation (TV) distance scaled by $\epsilon$.

**2. Private estimator and Generalized Likelihood Ratio (GLR) stopping rule.** We introduce a private estimator using arm-dependent geometric batching without forgetting and a GLR stopping rule based on the $d_{\epsilon}$ refined transportation costs. Its correctness (Theorem 6) required novel tails concentration results for Laplace distributions and the sum of Bernoulli and Laplace distributions, which could be of independent interest.

**3. Asymptotically optimal algorithm.** We propose a new Top Two sampling rule (DP-TT, Algorithm 1) based on the $d_{\epsilon}$-transportation costs suggested by our lower bound. We show that the asymptotic expected sample complexity of DP-TT matches our lower bound for any privacy budget $\epsilon$ up to a constant smaller than 8 (Theorem 7). DP-TT outperforms all the other $\delta$-correct $\epsilon$-global DP BAI algorithms on all tested instances and all $\epsilon$.

## 2 Background: Best Arm Identification under Differential Privacy

In this section, we present the Best Arm Identification (BAI) under fixed confidence problem [Garivier and Kaufmann, 2016], introduce the Differential Privacy (DP) [Dwork et al., 2006] constraint, and finally extend DP to BAI algorithms.

**BAI under Fixed Confidence.** Let $\mathcal{F} := \{\text{Ber}(p) \mid p \in (0, 1)\}$ be the set of Bernoulli distributions. A bandit instance $\nu := (\nu_a)_{a \in [K]} \in \mathcal{F}^K$ is characterized by its means $\mu := (\mu_a)_{a \in [K]} \in (0, 1)^K$. The best (optimal) arm $a^*$ is assumed to be unique, i.e., $a^*(\nu) = a^*(\mu) := \arg\max_{a \in [K]} \mu_a = \{a^*\}$. Let $\delta \in (0, 1)$ be the risk parameter. A fixed confidence BAI algorithm $\pi$ specifies three rules that rely on previously observed samples and some exogenous randomness. The sampling rule determines the next arm to pull $a_n \in [K]$ for which $X_{n,a_n} \sim \nu_{a_n}$ is observed. The recommendation rule recommends a candidate arm $\tilde{a} \in [K]$. The stopping rule decides when to stop collecting additional samples and output the current candidate arm. The stopping time $\tau_{\epsilon,\delta}$ is the sample complexity. Let $\mathbb{P}_{\nu_{\pi}}$ and $\mathbb{E}_{\nu_{\pi}}$ denote the probability and expectation taken over the randomness of the observations from $\nu$ and the algorithm $\pi$ (e.g., due to its privacy mechanism). A fixed-confidence BAI algorithm $\pi$ is $\delta$-correct when $\mathbb{P}_{\nu_{\pi}}(\tau_{\epsilon,\delta} < +\infty, \tilde{a} \notin a^*(\nu)) \le \delta$ for all $\nu \in \mathcal{F}^K$.
**Differential Privacy (DP).** An algorithm satisfies the Differential Privacy constraint if the algorithm's outputs are “essentially” equally likely to occur, for any two input datasets that only differ in one individual's data. An adversary only observing the mechanism's output cannot distinguish whether any individual's data was included. A privacy budget $\epsilon$ captures the closeness of the output distributions. Smaller $\epsilon$ means stronger privacy.

**Definition 1 (ε-DP [Dwork et al., 2006]).** A mechanism $\mathcal{M}$ satisfies $\epsilon$-DP for a given $\epsilon \ge 0$, if, for all neighboring datasets $D \sim D'$, where $D \sim D'$ if and only if $d_{Ham}(D, D') := \sum_{t=1}^T 1\{D_t \neq D'_t\} \le 1$, i.e., $D$ and $D'$ differ by at most one record, and for all sets of output $\mathcal{O} \subseteq \text{Range}(\mathcal{M})$, $\text{Pr}[\mathcal{M}(\mathcal{D}) \in \mathcal{O}] \le e^\epsilon \text{Pr}[\mathcal{M}(\mathcal{D}') \in \mathcal{O}]$ where the probability space is over the coin flips of the mechanism $\mathcal{M}$.

To ensure $\epsilon$-DP, the Laplace mechanism [Dwork et al., 2010; Dwork and Roth, 2014] adds calibrated Laplacian noise to the algorithm's output. Let $\text{Lap}(b)$ be the Laplace distribution with mean/variance $(0, 2b^2)$.

**Theorem 1 (Laplace mechanism, Theorem 3.6 [Dwork and Roth, 2014]).** Let $f: \mathcal{X} \to \mathbb{R}^d$ be an algorithm with sensitivity $s(f) \triangleq \max_{D, D' \text{ s.t. } d_{Ham}(D, D')=1} \|f(D) - f(D')\|_1$, where $\|\cdot\|_1$ is the $\ell_1$ norm. Let $(Z_i)_{i \in [d]}$ be i.i.d. from $\text{Lap}(s(f)/\epsilon)$, then the noisy output $f(D) + (Z_i)_{i \in [d]}$ satisfies $\epsilon$-DP.

To be consistent with the literature on private bandits, we use global DP to denote the central DP model with a trusted central decision maker. While the notation $\delta$ is standard in the $(\epsilon, \delta)$-DP relaxation of the $(\epsilon, 0)$-DP constraint considered in this paper, we use $\delta$ for the confidence parameter to be consistent with the literature on pure exploration problems.

**DP for BAI.** In BAI algorithms, the private input is the observation dataset and the output is the recommended candidate arm $\tilde{a}$ and the sequence of sampled actions $(a_n)_{n<\tau_{\epsilon,\delta}}$ until stopping at $\tau_{\epsilon,\delta}$. Let $R = \{r_1, \dots\}$ be a sequence of private observations. Given a fixed sequence of observations $R$, we denote by $\text{Pr}[\pi(R) = (T+1, \tilde{a}, (a_1, \dots, a_T))]$ the probability that the BAI algorithm $\pi$ stops at step $T+1$, recommending action $\tilde{a}$ and sampling actions $(a_1, \dots, a_T)$ when interacting with $R$. The randomisation in this probability comes only from the BAI algorithm's sampling, recommendation and stopping rules, whereas the observations are fixed. Then, a BAI algorithm $\pi$ is said to be $\epsilon$-global DP if, for every two neighboring sequences of observations $R$ and $R'$, and for every possible stopping time, recommendation and sampled actions $(T+1, \tilde{a}, (a_1, \dots, a_T))$, we have that

$$ \text{Pr}[\pi(R) = (T+1, \tilde{a}, (a_1, \dots, a_T))] \le e^\epsilon \text{Pr}[\pi(R') = (T+1, \tilde{a}, (a_1, \dots, a_T))] . $$

**Main Goal:** Design $\epsilon$-global DP $\delta$-correct BAI algorithms, with the smallest sample complexity $\tau_{\epsilon,\delta}$.

**Notation.** Let $[x]_0^1 := \max\{0, \min\{1, x\}\}$ be the clipping operator to $[0, 1]$. Let $1(\cdot)$ be the indicator function. For two probability distributions $\mathbb{P}$ and $\mathbb{Q}$ on the measurable space $(\Omega, \mathcal{G})$, the Total Variation (TV) distance is $\text{TV}(\mathbb{P} \| \mathbb{Q}) := \sup_{A \in \mathcal{G}} \{\mathbb{P}(A) - \mathbb{Q}(A)\}$ and the Kullback-Leibler (KL) divergence is $\text{KL}(\mathbb{P} \| \mathbb{Q}) := \int \log \left( \frac{d\mathbb{P}}{d\mathbb{Q}}(\omega) \right) d\mathbb{P}(\omega)$, when $\mathbb{P} \ll \mathbb{Q}$, and $+\infty$ otherwise. The KL divergence and TV distance between two Bernoulli distributions with means $(p, q) \in (0, 1)^2$ are the relative entropy denoted by kl, i.e., $\text{KL}(\text{Ber}(p) \| \text{Ber}(q)) = \text{kl}(p, q) := p \log(p/q) + (1-p) \log((1-p)/(1-q))$, and the absolute mean difference, i.e., $\text{TV}(\text{Ber}(p) \| \text{Ber}(q)) = |p - q|$. Let $\Delta_K := \{w \in \mathbb{R}^K \mid w \ge 0, \sum_{a \in [K]} w_a = 1\}$ be the probability simplex of dimension $K-1$. For all $a \in [K]$, let $N_{n,a} := \sum_{t \in [n-1]} 1(a_t = a)$ be the global pulling count of arm $a$ before time $n$.

## 3 Lower Bound on the Expected Sample Complexity

In order to be $\delta$-correct, an algorithm has to be able to distinguish $\nu$ from alternative instances with different best arms, i.e., an instance $\kappa \in \text{Alt}(\nu) := \{\kappa \in \mathcal{F}^K \mid a^*(\kappa) \neq a^*(\nu)\}$. On the other hand, being $\epsilon$-global DP forces an algorithm to have similar behaviour on similar instances. The interplay between the stochasticity of the bandit instance, controlled with the KL divergence, and the stochasticity of the privacy mechanism, controlled with the TV distance, is smoothly captured by

$$ d_{\epsilon}(\nu, \kappa) := \inf_{\varphi \in \mathcal{F}} \{\epsilon \cdot \text{TV}(\nu \| \varphi) + \text{KL}(\varphi \| \kappa)\}, \quad (1) $$

recently introduced by Azize et al. [2025] for $\epsilon$-global DP regret minimization. The $d_{\epsilon}$ divergence measures the shortest two-parts path between the two distributions $\nu$ and $\kappa$, by finding the best
intermediate distribution $\varphi \in \mathcal{F}$. The cost of moving from $\nu$ to $\varphi$ is measured with the TV distance rescaled by $\epsilon$, while it is measured with the KL divergence when moving from $\varphi$ to $\kappa$.

The tension between the $\delta$-correct and $\epsilon$-global DP constraints yields the following problem-dependent non-asymptotic lower bound on the expected sample complexity $\mathbb{E}_{\nu\pi}[\tau_{\epsilon,\delta}]$ for any algorithm $\pi$ on any instance $\nu$, holding for any values of $\epsilon$ and $\delta$.

**Theorem 2.** Let $(\epsilon, \delta) \in \mathbb{R}_+^* \times (0, 1)$. For any algorithm $\pi$ that is $\delta$-correct and $\epsilon$-global DP on $\mathcal{F}^K$, $\mathbb{E}_{\nu\pi}[\tau_{\epsilon,\delta}] \ge T_{\epsilon}^*(\nu) \log(1/(3\delta))$

for all $\nu \in \mathcal{F}^K$ with unique best arm. The inverse of the characteristic time $T_{\epsilon}^*(\nu)$ is defined as

$$T_{\epsilon}^{*}(\nu)^{-1} := \sup_{w \in \Delta_K} \inf_{\kappa \in \text{Alt}(\nu)} \sum_{a=1}^{K} w_a d_{\epsilon}(\nu_a, \kappa_a). \quad (2)$$

**Comments.** (a) The characteristic time in the lower bound is the value of a two-player zero-sum game between a MIN player, who plays instances $\kappa$ close of $\nu$ is order to confuse the MAX player, who in order plays an arm allocation $w \in \Delta_K$ to distinguish between $\nu$ and $\kappa$.

(b) The crucial part in characteristic times similar to Eq. (2) is finding the “right” measure capturing the “distinguishability” between instances. In the non-private lower bounds, this is captured by the KL divergence for parametric distributions [Garivier and Kaufmann, 2016] and by the Kinf (i.e., inf KL under mean constraint) for non-parametric distributions [Agrawal et al., 2020]. In the DP lower bounds of Azize et al. [2023], it is captured by $\min\{\text{KL}, \epsilon\text{TV}\}$. In Theorem 2, it is captured by $d_{\epsilon}$ (as in Eq. (1)) that smoothly interpolates between KL and TV. Azize et al. [2025] recently introduced $d_{\epsilon}$ for $\epsilon$-global DP regret minimization. Our results show that $d_{\epsilon}$ also tightly captures the hardness of fixed-confidence BAI under $\epsilon$-global DP. Namely, our DP-TT algorithm achieves a matching upper bound when $\delta \to 0$ (up to a constant smaller than 8), for all instances with distinct means and all values of $\epsilon$.

(c) Azize et al. [2023, Theorem 2] provides a lower bound on the sample complexity of any $\epsilon$-global $\delta$-correct algorithm, where the inverse characteristic time is $\sup_{w \in \Delta_K} \inf_{\kappa \in \text{Alt}(\nu)} \min\{\sum_{a=1}^K w_a \text{KL}(\nu_a \| \kappa_a), 6\epsilon \sum_{a=1}^K w_a \text{TV}(\nu_a \| \kappa_a)\}$. The lower bound of Theorem 2 is strictly tighter than that of Theorem 2 in [Azize et al., 2023], for all instances $\nu$ and values of $\epsilon$. The reason is that $d_{\epsilon}(\mathbb{P}, \mathbb{Q}) \le \min\{\text{KL}(\mathbb{P}, \mathbb{Q}), \epsilon\text{TV}(\mathbb{P}, \mathbb{Q})\}$ for any two distributions.

(d) The lower bound of Theorem 2 suggests the existence of two privacy regimes, depending on the value of $\epsilon$ and the instance $\nu$. Specifically, when $\epsilon$ is big, $d_{\epsilon}$ reduces to the KL, and we retrieve the classic non-private lower bound. On the other hand, as $\epsilon \to 0$, $d_{\epsilon}$ reduces to $\epsilon$ TV, and the characteristic time reduces to $\frac{1}{\epsilon}T_{\text{TV}}^*(\nu) := \frac{1}{\epsilon} \left( \sup_{w \in \Delta_K} \inf_{\kappa \in \text{Alt}(\nu)} \sum_{a=1}^K w_a \text{TV}(\nu_a \| \kappa_a) \right)^{-1} = \frac{1}{\epsilon} \sum_{a=1}^k \frac{1}{\Delta_a}$, where $\Delta_a = \mu^* - \mu_a$ for $a \ne a^*$ and $\Delta_{a^*} = \min_{a \ne a^*} \Delta_a$. This improves the high privacy regime lower bound of prior work by a factor 6. Also, the value of $\epsilon$ at which the privacy regimes change can be tightly specified, which we quantify for Bernoulli instances in the following.

**Proof Sketch and Techniques.** The proof uses the standard reduction to hypothesis testing [Garivier and Kaufmann, 2016], using the data-processing inequality. The asymptotic techniques used by Azize et al. [2025] for regret cannot be adapted for our non-asymptotic lower bound. Thus, new techniques are needed. The main technical novelty of the proof is a tighter quantification of the “similar” behaviour of a DP mechanism when applied to stochastic datasets. Specifically, let $\mathcal{M}$ be an $\epsilon$-DP mechanism. Given two data-generating distributions $\mathbb{P}$ and $\mathbb{Q}$, letting $\mathbb{M}_{\mathbb{P},\mathcal{M}}$ (resp. $\mathbb{M}_{\mathbb{Q},\mathcal{M}}$) be the marginal over outputs of the mechanism when the input dataset is generated through $\mathbb{P}$ (resp. $\mathbb{Q}$), then we show that

$$\mathrm{KL}(\mathbb{M}_{\mathbb{P},\mathcal{M}} \| \mathbb{M}_{\mathbb{Q},\mathcal{M}}) \le \inf_{\mathbb{L}} \left\{ \epsilon \inf_{\mathbb{C}_{\mathbb{P},\mathbb{L}}} \left\{ \mathbb{E}_{D,D' \sim \mathbb{C}_{\mathbb{P},\mathbb{L}}} [d_{\mathrm{Ham}}(D, D')] \right\} + \mathrm{KL}(\mathbb{L} \| \mathbb{Q}) \right\},$$

where the first infimum is over all distributions $\mathbb{L}$ on the input space, and the second infimum is an optimal transport problem over all couplings between $\mathbb{P}$ and $\mathbb{L}$, where the cost is the Hamming distance (introduced in Definition 1). This bound of general interest could be applied to get tighter lower bounds in any DP application using stochastic inputs. For product and bandit distributions, we solve the optimal transport using maximal couplings, where the Total Variation naturally appears,
while keeping the first infimum unchanged, giving rise to the $d_\epsilon$ quantity. Finally, plugging the new upper bound on the KL in the hypothesis reduction concludes the sample complexity lower bound proof. A detailed proof and discussion of all these claims is given in Appendix D.

**Transportation Costs Based on Signed Divergences.** In non-parametric BAI, the ordering between the mean parameters is captured by a signed Kinf [Jourdan et al., 2022]. We adopt this convention by introducing a signed divergences: $d_\epsilon^+$ and $d_\epsilon^-$ defined in Lemma 3 on means rather than probability distributions, where $d_\epsilon^+$ refers to both of them. Given $(\kappa, \nu) \in \mathcal{F}^2$ with means $(\lambda, \mu) \in (0, 1)^2$, they satisfy $d_\epsilon(\kappa, \nu) = d_\epsilon^+(\lambda, \mu)$ when $\mu > \lambda$, and $d_\epsilon(\kappa, \nu) = d_\epsilon^-(\lambda, \mu)$ otherwise (Lemma 22).

**Lemma 3.** For all $x \in [0, 1]$, let us define $g_\epsilon^-(x) := \frac{xe^\epsilon}{x(e^\epsilon - 1) + 1}$ and $g_\epsilon^+(x) := 1 - g_\epsilon^-(1 - x) = (g_\epsilon^-)^{-1}(x)$. For all $(\lambda, \mu) \in \mathbb{R} \times [0, 1]$, the signed divergences are defined as

$$d_\epsilon^+(\lambda, \mu) := 1 (\mu > [\lambda]_0^1) \inf_{z \in [[\lambda]_0^1, \mu]} \{\mathrm{kl}(z, \mu) + \epsilon(z - [\lambda]_0^1)\} \\ = \begin{cases} 0 & \text{if } \mu \in [0, [\lambda]_0^1] \\ -\log(1 - \mu(1 - e^{-\epsilon})) - \epsilon[\lambda]_0^1 & \text{if } \mu \in (g_\epsilon^-([\lambda]_0^1), 1] \\ \mathrm{kl}(\lambda, \mu) & \text{if } \lambda \in (0, 1) \text{ and } \mu \in ([\lambda]_0^1, g_\epsilon^-([\lambda]_0^1)] \end{cases}, \\ d_\epsilon^-(\lambda, \mu) := 1 (\mu < [\lambda]_0^1) \inf_{z \in [\mu, [\lambda]_0^1]} \{\mathrm{kl}(z, \mu) + \epsilon([\lambda]_0^1 - z)\} = d_\epsilon^+(1 - \lambda, 1 - \mu). \quad (3)$$

When two distributions are close enough compared to the privacy $\epsilon$, the signed divergences reduce to the KL divergence: the indistinguishability due to the stochasticity of the instance is stronger than the indistinguishability due to DP. The function $g_\epsilon^-$ (resp. $g_\epsilon^+$) represents the maximal (resp. minimal) mean for which this property hold for $d_\epsilon^+$ (resp. $d_\epsilon^-$).

For $(\mu, w) \in \mathbb{R}^K \times \mathbb{R}_+^K$, the transportation cost of the pair of arms $(a, b) \in [K]^2$ is defined as

$$W_{\epsilon,a,b}(\mu, w) := 1 ([\mu_a]_0^1 > [\mu_b]_0^1) \inf_{u \in [0,1]} \{w_a d_\epsilon^-(\mu_a, u) + w_b d_\epsilon^+(\mu_b, u)\}. \quad (4)$$

The signed divergences $d_\epsilon^+$ and the transportation costs $(W_{\epsilon,a,b})_{(a,b) \in [K]^2}$ satisfy all the desired properties required to study BAI algorithms based on the empirical version of $W_{\epsilon,a,b}$ (see Lemmas 23, 24, 25 and 26, as well as Lemmas 35, 36, 37 and 38), e.g., symmetry, explicit formula, monotonicity, strict convexity, etc.

**Properties of the Characteristic Time and Optimal Allocation.** The set $w_\epsilon^*(\nu)$ of optimal allocations is the maximizer of the outer supremum on $\Delta_K$ that defines $T_\epsilon^*(\nu)^{-1}$ in Eq. (2). Theorem 4 gathers key properties satisfied by $T_\epsilon^*(\nu)$ and $w_\epsilon^*(\nu)$, for Bernoulli distributions. See lemmas proven in Appendix G, i.e., Lemmas 36, 43 and 47.

**Theorem 4.** Let $\nu \in \mathcal{F}^K$ having means $\mu \in (0, 1)^K$ with unique best arm $a^*$. Then, we have

$$T_{\epsilon}^{*}(\boldsymbol{\nu})^{-1} = \max_{w \in \Delta_K} \min_{a \neq a^{*}} W_{\epsilon, a^{*}, a}(\mu, w) \quad \text{and} \quad T_{\epsilon}^{*}(\boldsymbol{\nu}) \geq \sum_{a \in [K]} \Delta_{\epsilon, a}^{-1}. \quad (5)$$

where $\Delta_{\epsilon,a^*} := \min_{a \neq a^*} d_\epsilon^-(\mu_{a^*}, \mu_a)$ and $\Delta_{\epsilon,a} := d_\epsilon^+(\mu_a, \mu_{a^*})$ for all $a \neq a^*$. The optimal allocation is unique, has dense support and ensures the equality of the transportation costs with $T_\epsilon^*(\nu)^{-1}$ (i.e., information balance equation), namely $w_\epsilon^*(\nu) = \{w_\epsilon^*\}$, $\min_{a \in [K]} w_{\epsilon,a}^* > 0$ and $W_{\epsilon,a^*,a}(\mu, w_\epsilon^*) = T_\epsilon^*(\nu)^{-1}$ for all $a \neq a^*$.

In Garivier and Kaufmann [2016], the characteristic time and its optimal allocation can be computed with a simpler optimisation problem. A simpler optimization problem can also be solved to compute $T_\epsilon^*(\nu)$ and $w_\epsilon^*(\nu)$ explicitly (Lemma 47).

**Allocation Dependent Low Privacy Regime.** Let $(\mu, w, a, b) \in (0, 1)^K \times \mathbb{R}_+^K \times [K]^2$ such that $\mu_a > \mu_b$ and $\min\{w_a, w_b\} > 0$. The non-private Bernoulli transportation costs [Garivier and Kaufmann, 2016] are defined as

$$W_{a,b}(\mu, w) := w_a \mathrm{kl}(\mu_a, \mu_{a,b}^w) + w_b \mathrm{kl}(\mu_b, \mu_{a,b}^w) \quad \text{with} \quad \mu_{a,b}^w := \frac{w_a \mu_a + w_b \mu_b}{w_a + w_b}.$$

We provide an allocation-dependent low-privacy condition that depends on $(\epsilon, \mu, w)$ (Lemma 45), i.e., $W_{\epsilon,a,b}(\mu, w) = W_{a,b}(\mu, w)$ is implied by

$$\mu_a - \mu_b \le (1 - e^{-\epsilon}) \min \{(1 + w_a/w_b) \mu_a g_\epsilon^-(1 - \mu_a), (1 + w_b/w_a) (1 - \mu_b) g_\epsilon^-(\mu_b)\}. \quad (6)$$
Plugging $w_e^*$ from Theorem 4 in Eq. (6) would give an implicit condition on $(\epsilon, \mu)$ under which the non-private characteristic time $T^*(\nu)$ for Bernoulli distributions is recovered, i.e., $T_e^*(\nu) = T^*(\nu)$. From a privacy-utility tradeoff perspective, the choice of $\epsilon$ that provides the highest privacy protection while maintaining a low sample complexity is exactly this change-of-regime $\epsilon$, depending on the unknown $\mu$. A weaker (yet explicit) allocation-independent sufficient condition for $T_e^*(\nu) = T^*(\nu)$ is $\epsilon \ge \max_{a \ne a^*} \epsilon_{a^*,a}$ where $\epsilon_{a,b} := \log \left( \frac{\mu_a(1-\mu_b)}{\mu_b(1-\mu_a)} \right)$.

# 4 Generalized Likelihood Ratio Stopping Rule

Designing appropriate recommendation and stopping rules for the BAI problem can be framed as a sequential hypothesis testing task with multiple hypotheses $\{\mu_a = \max_{b \in [K]} \mu_b\}$. One of the earliest approaches to active hypothesis testing—where data collection is also optimized—was introduced by Chernoff [1959], who advocated for the use of Generalized Likelihood Ratio (GLR) tests for stopping decisions. This methodology is also popular in the context of BAI [Garivier and Kaufmann, 2016]. Despite its relevance, fewer works attempted to extend it for private sequential hypothesis testing, see, e.g., Zhang et al. [2022] under Rényi DP and Azize et al. [2024] under $\epsilon$-local and $\epsilon$-global DP.

**Mean Estimator.** Three rules need to be specified to define a BAI algorithm: recommendation, sampling, and stopping rules. An important remark in designing BAI algorithms is that the dependence of these rules on the private input observation dataset comes solely through the sequence of mean estimators. Thus, designing a sequence of mean estimators that satisfy DP is crucial when defining a $\epsilon$-global DP BAI algorithm. To estimate the sequence of means, defined in Lines 5-8 of Algorithm 1, we rely on two ingredients: adaptive arm-dependent episodes with a geometric update grid and the Laplace mechanism. We call this mechanism estimating the sequence of means the Geometric Private Estimator, i.e., $GPE_\eta(\epsilon)$. Most notably, we eliminate “observation forgetting” from $GPE_\eta(\epsilon)$, an important design choice made in all past BAI algorithms Sajed and Sheffet [2019]; Azize et al. [2023, 2024]. Specifically, for some $\eta > 0$ called the geometric grid parameter, $GPE_\eta(\epsilon)$ estimates the noisy means in arm-dependent phases: a phase changes when the counts of an arm has increased multiplicatively by $1 + \eta$ (Line 5). Then, $GPE_\eta(\epsilon)$ only updates the mean of the arm that changed phases, by accumulating the observations collected from its last phase and adding Laplace noise (Line 7). Due to this accumulation step, we *do not forget* the observations from past phases. Thus, each estimated noisy mean $\tilde{\mu}_{n,a}$ in Line 7 contains $\tilde{N}_{n,a}$ i.i.d. observations from $\nu_a$ and $k_{n,a} \approx \log_{1+\eta} \tilde{N}_{n,a}$ i.i.d. observations from Lap$(1/\epsilon)$. In contrast, using forgetting produces a noisy mean that contains fewer i.i.d. observations from $\nu_a$ (e.g. $\tilde{N}_{n,a}/2$ samples for forgetting with $\eta = 1$), but only *one* Laplace noise. While removing forgetting allows us to keep more signal, i.e., more i.i.d samples from $\nu_a$, we need more noise, i.e., the cumulative sum of Lap$(1/\epsilon)$, which is logarithmic in the number of samples from $\nu_a$. Tighter concentration inequalities allow controlling the cumulative sum of Laplace noise. See below for a detailed discussion about our novel concentration results. As long as the number of samples from the Lap$(1/\epsilon)$ is logarithmic in the number of samples from $\nu_a$, the effect of noise on the sample complexity is similar to having only *one* additional Laplace noise.

**Privacy Analysis.** By adaptive post-processing, the following lemma is proved naturally for any $\epsilon$.

**Lemma 5.** Any BAI algorithm using only $GPE_\eta(\epsilon)$ to access observations is $\epsilon$-global DP on $[0, 1]$.

**Proof Sketch.** The proof combines two steps. First, we show that the sequence of mean estimators produced by $GPE_\eta(\epsilon)$ is $\epsilon$-DP. The crucial observation is that a change in one observation *only* affects the partial sum collected in just *one* arm-phase. By the Laplace mechanism, adding one Lap$(1/\epsilon)$ to the partial sum is enough to make it $\epsilon$-DP. Then, by post-processing, the sequence of accumulated partial sums $(\hat{S}_{k_{n,a},a})$ and noisy means $(\mu_{n,a})$ (Line 7) are also $\epsilon$-DP. The second step shows how to use the sequential nature of the process and adaptive post-processing to conclude that BAI algorithms using only $GPE_\eta(\epsilon)$ are $\epsilon$-global DP. The detailed proof is in Appendix E.

**Recommendation Rule.** The recommendation rule $\tilde{a}_n$ is defined as the arm with the highest clipped noisy empirical mean, i.e., $\tilde{a}_n \in \arg\max_{a \in [K]} [\tilde{\mu}_{n,a}]_0^1$ where ties are broken uniformly at random.

**GLR Stopping Rule.** The GLR stopping rule runs *K* sequential GLR tests in parallel, and stops as soon as one of these tests can reject the null hypothesis. When comparing the recommendation $\tilde{a}_n$ with an alternative arm *a*, the GLR statistic is defined as the transportation cost $W_{\epsilon, \tilde{a}_n, a}$ evaluated
empirically at $(\tilde{\mu}_n, \tilde{N}_n)$ (see Eq. (4)). Intuitively, $W_{\epsilon, \tilde{a}_n, a}(\tilde{\mu}_n, \tilde{N}_n)$ represents the amount of empirical evidence to reject the hypothesis that arm a has a higher mean than $\tilde{a}_n$. One can stop and recommend $\tilde{a}_n$ when all these statistics exceed a given stopping threshold. Given a privacy budget and risk $(\epsilon, \delta) \in \mathbb{R}_+^* \times (0, 1)$ and a stopping threshold $c: \mathbb{N} \times \mathbb{R}_+^* \times (0, 1) \to \mathbb{R}_+$, we define

$$ \tau_{\epsilon, \delta} = \inf\{ n \mid \forall a \neq \tilde{a}_n, W_{\epsilon, \tilde{a}_n, a}(\tilde{\mu}_n, \tilde{N}_n) > c(\tilde{N}_{n, \tilde{a}_n}, \epsilon, \delta) + c(\tilde{N}_{n, a}, \epsilon, \delta) \}. \quad (7) $$

Given its proximity to the characteristic time $T_{\epsilon}^{*}(\nu)$, see Eq. (5) (Theorem 4), the GLR stopping rule is a good candidate to match the lower bound, i.e., if one could sample arms according to $w_{\epsilon}^{*}(\nu)$ and use the stopping threshold $\log(1/\delta)$. Unfortunately, this threshold is too good to be $\delta$-correct and $w_{\epsilon}^{*}(\nu)$ should be estimated as it is unknown (Section 5).

**Calibration of the Stopping Threshold.** Regardless of the sampling rule, the stopping threshold should ensure $\delta$-correctness of the GLR stopping rule for any pair $(\epsilon, \delta)$, see Theorem 6.

**Theorem 6.** Let $(\epsilon, \delta, \eta) \in \mathbb{R}_+^* \times (0, 1) \times \mathbb{R}_+^*$. Let $s > 1$, $\zeta$ be the Riemann $\zeta$ function and $\bar{W}_{-1}(x) = -W_{-1}(-e^{-x})$ for all $x \ge 1$, where $W_{-1}$ is the negative branch of the Lambert W function, satisfying $\bar{W}_{-1}(x) \approx x + \log x$ (Lemma 52). Given any sampling rule using the $GPE_{\eta}(\epsilon)$, using the GLR stopping rule as in Eq. (7) with the $GPE_{\eta}(\epsilon)$ and the stopping threshold $c(n, \epsilon, \delta) := c_1(n, \delta) + c_2(n, \epsilon)$ where

$$ c_1(n, \delta) = \bar{W}_{-1} \left( \log \left( K \zeta(s) / \delta \right) + s \log(k_{\eta}(n)) + 3 - \log 2 \right) - 3 + \log 2, \quad (8) $$

$$ c_2(n, \epsilon) = k_{\eta}(n) \left( \log \left( 1 + 2\epsilon n / k_{\eta}(n) \right) + 1 \right) \quad \text{with} \quad k_{\eta}(x) := 1 + \log_{1+\eta} x, $$

yields a $\delta$-correct and $\epsilon$-global DP algorithm for all Bernoulli instances with a unique best arm.

The proof of Theorem 6 builds on novel concentration results of independent interest (Appendix F.2). Our explicit instance-independent upper bounds are pivotal to derive the stopping threshold in Eq. (8), which avoids the large instance-dependent constants used in the regret minimisation literature [Azize et al., 2025].

**Concentration Results.** First, we give tail bounds for the cumulative sum of i.i.d. Laplace observations (Lemma 16). We use Chernoff’s method with the convex conjugate of the moment generating function of Lap$(1/\epsilon)$, hence improving on Azize et al. [2025, Lemma 18] that approximates it. Second, we derive tail bounds for the sum between independent cumulative sums of $t$ i.i.d. Bernoulli and $n_t$ i.i.d. Laplace observations (Lemmas 18 and 19). They involve the *modified* signed divergences $\tilde{d}_{\epsilon}^{\pm}$ that better capture the non-asymptotic tails behaviour, and are equivalent to $d_{\epsilon}^{\pm}$ to an additive term $\Theta(\log(1 + 2\epsilon r_t)/r_t)$ where $r_t := t/n_t$ (Lemma 30). Whenever $r_t \to +\infty$, we recover the same noise effect as adding only one Lap$(1/\epsilon)$ observation. For $x > 0$, the exponential decrease of the probability of exceeding $\mu + x$ (resp. being lower than $\mu - x$) scales as $t\tilde{d}_{\epsilon}^{-}(\mu + x, \mu, r_t)$ (resp. $t\tilde{d}_{\epsilon}^{+}(\mu - x, \mu, r_t)$). The proof builds on fine-grained tail bounds of the sum of two independent random variables, i.e., we bound those probabilities by the maximal product between their respective survival functions (Lemma 10). While Azize et al. [2025, Lemma 19] directly integrates their tail bounds, Lemma 12 can be used with any tail bounds. Third, we obtain time-uniform upper tail bounds for $\tilde{N}_{n,a}\tilde{d}_{\epsilon}^{\pm}(\tilde{\mu}_{n,a}, \mu_a, \tilde{N}_{n,a}/k_{n,a})$ by exploiting the geometric-grid update of $(\tilde{\mu}_n, \tilde{N}_n, k_n)$.

**Threshold Scaling.** The threshold $c_1$ in Eq. (8) ensures $\delta$-correctness of the *modified* GLR stopping rule, defined in Appendix F.1 with the *modified* transportation costs $\bar{W}_{\epsilon, a, b}$ and divergences $\tilde{d}_{\epsilon}^{\pm}$ (Appendix F.1). Independent of $\epsilon$, it scales as $\log(1/\delta) + \Theta(\log \log(1/\delta))$ when $\delta \to 0$ and $\Theta(\log \log(n))$ when $n \to +\infty$. The threshold $c_2$ in Eq. (8) is an upper bound on $\tilde{N}_{n,a}(d_{\epsilon}^{\pm}(\tilde{\mu}_{n,a}, \mu_a) - \tilde{d}_{\epsilon}^{\pm}(\tilde{\mu}_{n,a}, \mu_a, \tilde{N}_{n,a}/k_{n,a}))$ (Lemma 30) that scales as $\Theta(\epsilon n)$ when $\epsilon \to 0$ and as $\Theta((\log n)^2)$ when $n \to +\infty$. Both $c_1$ and $c_2$ scales as $\Theta(1/\log(1+\eta))$ when $\eta \to 0$.

**Limitation.** As the threshold in Eq. (7) is the sum of per-arm thresholds, it scales as $2\log(1/\delta)$ when $\delta \to 0$, hence incurs a suboptimal factor 2 asymptotically. Obtaining a threshold in $\log(1/\delta)$ is left for future work. It requires controlling the re-weighted sum of modified divergences $\tilde{d}_{\epsilon}^{\pm}$. Azize et al. [2023, Theorem 4] has a suboptimal factor 2 for the same reason and incurs an additive factor $\frac{1}{n\epsilon^2}\log(1/\delta)^2$ due to the separate control of the Laplace and the Bernoulli observations (based on sub-Gaussian concentration results). Azize et al. [2024, Lemma 18] alleviates this factor 2 in their low privacy regime, yet it also pays $\frac{1}{n\epsilon^2}\log(1/\delta)^2$.
**Algorithm 1** Differentially Private Top Two (DP-TT) Algorithm.

1: **Input:** setting parameters $(\epsilon, \delta) \in \mathbb{R}_+^* \times (0, 1)$, algorithmic hyperparameters $(\eta, \beta) \in \mathbb{R}_+^* \times (0, 1)$ and threshold $c$, e.g., $(\eta, \beta) = (1, 1/2)$ and $c$ as in Eq. (8). $(W_{\epsilon,a,b})_{(a,b)\in[K]}$ as in Eq. (4).

2: **Output:** Stopping time $\tau_{\epsilon,\delta}$, recommendation $\tilde{a}_{\tau_{\epsilon,\delta}}$, and pulling history $(a_n)_{n<\tau_{\epsilon,\delta}}$.

3: **Initialization:** For all $a \in [K]$, pull arm $a$, observe $X_{a,a} \sim \nu_a$ and draw $Y_{1,a} \sim \text{Lap}(1/\epsilon)$. Set $n = K + 1$. For all $a \in [K]$, set $\tilde{S}_{n,a} = X_{a,a} + Y_{1,a}$, $k_{n,a} = 1$, $T_1(a) = n$, $N_{n,a} = \tilde{N}_{n,a} = 1$, $\tilde{\mu}_{n,a} = \tilde{S}_{n,a}/\tilde{N}_{n,a}$, $L_{n,a} = 0$ and $N_{n,a}^a = 0$.

4: **for** $n \ge K + 1$ **do**

5: &nbsp;&nbsp;&nbsp;&nbsp;**if** there exists $a \in [K]$ such that $N_{n,a} \ge (1+\eta)^{k_{n,a}}$ **then** ▷ Per-arm geometric update grid

6: &nbsp;&nbsp;&nbsp;&nbsp;For this arm $a$, change phase $k_{n,a} \leftarrow k_{n,a} + 1$, and $(T_{k_{n,a}}(a), \tilde{N}_{n,a}) = (n, N_{T_{k_{n,a}}(a),a})$;

7: &nbsp;&nbsp;&nbsp;&nbsp;Set $\tilde{S}_{k_{n,a},a} = \sum_{t=T_{k_{n,a}-1}(a)}^{T_{k_{n,a}}(a)-1} X_{t,a} \mathbf{1}(a_t = a) + Y_{k_{n,a},a} + \tilde{S}_{k_{n,a}-1,a}$ with $Y_{k_{n,a},a} \sim \text{Lap}(1/\epsilon)$, and update the mean $\tilde{\mu}_{n,a} = \tilde{S}_{k_{n,a},a}/\tilde{N}_{n,a}$;

8: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

9: &nbsp;&nbsp;&nbsp;&nbsp;Set $\tilde{a}_n \in \arg\max_{a \in [K]} [\tilde{\mu}_{n,a}]_0^1$; ▷ Recommendation rule

10: &nbsp;&nbsp;&nbsp;&nbsp;**if** $W_{\epsilon, \tilde{a}_n, a}(\tilde{\mu}_n, \tilde{N}_n) > \sum_{b \in \{\tilde{a}_n, a\}} c(\tilde{N}_{n,b}, \epsilon, \delta)$ for all $a \ne \hat{a}_n$ **then** ▷ GLR stopping rule

11: &nbsp;&nbsp;&nbsp;&nbsp;**return** $(n, \tilde{a}_n, (a_t)_{t<n})$.

12: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

13: &nbsp;&nbsp;&nbsp;&nbsp;Set $B_n = \tilde{a}_n$ and $C_n \in \arg\min_{a \ne B_n} \{W_{\epsilon, B_n, a}(\tilde{\mu}_n, N_n) + \log N_{n,a}\}$; ▷ EB-TCI

14: &nbsp;&nbsp;&nbsp;&nbsp;Set $a_n = B_n$ if $N_{n,B_n}^{B_n} \le \beta L_{n+1,B_n}$, and $a_n = C_n$ otherwise; ▷ $\beta$-tracking

15: &nbsp;&nbsp;&nbsp;&nbsp;Pull $a_n$, observe and store $X_{n,a_n} \sim \nu_{a_n}$;

16: &nbsp;&nbsp;&nbsp;&nbsp;Update $(N_{n+1,a_n}, L_{n+1,B_n}, N_{n+1,B_n}^{B_n}) = (N_{n,a_n}, L_{n,B_n}, N_{n,B_n}^{B_n}) + (1, 1, \mathbf{1}(B_n = a_n))$;

17: **end for**

**5 Top Two Sampling Rule**

Equipped with a recommendation and stopping rules, we define a sampling rule using the GPE$_\eta(\epsilon)$. Within the fixed-confidence BAI literature, we adopt the Top Two approach [Russo, 2016; Qin et al., 2017; Shang et al., 2020; Jourdan et al., 2022] that recently received increased scrutiny due to its good theoretical guarantees [Jourdan and Degenne, 2024; You et al., 2023; Jourdan et al., 2024; Bandyopadhyay et al., 2024], competitive empirical performance, and low computational cost. The Differentially Private Top Two (DP-TT) algorithm (Algorithm 1) uses the EB-TCI-$\beta$ sampling rule [Jourdan et al., 2022]. In Appendix I, we introduce the Track-and-Stop [Garivier and Kaufmann, 2016] and LUCB [Kalyanakrishnan et al., 2012] sampling rules for fixed-confidence BAI under $\epsilon$-global DP.

After initialization, a Top Two sampling rule specifies four choices [Jourdan, 2024]: a leader arm $B_n \in [K]$, a challenger arm $C_n \in [K] \setminus \{B_n\}$, a target allocation $\beta_n(B_n, C_n) \in [0, 1]$ and a mechanism to choose the next arm to sample from, i.e., $a_n \in \{B_n, C_n\}$ by using $\beta_n(B_n, C_n)$. The leader should select a good estimator of the best arm $a^*$. We use the empirical best (EB) leader that coincides with our recommendation rule, i.e., $B_n := \tilde{a}_n$. The challenger should be a confusing alternative arm, for which the empirical evidence that the leader has a better mean is low. We use the TCI challenger [Jourdan et al., 2022] that penalizes oversampled challenger to foster implicit exploration, i.e., $C_n \in \arg\min_{a \ne B_n} \{W_{\epsilon, B_n, a}(\tilde{\mu}_n, N_n) + \log N_{n,a}\}$ where ties are broken uniformly at random. Crucially, we leverage our novel transportation costs $(W_{\epsilon, B_n, a})_{a \ne B_n}$ featuring the signed divergences $d_a^\pm$ that are evaluated empirically at $(\tilde{\mu}_n, N_n)$, see Eq. (3) and (4). The target should be chosen to balance the allocation between the leader and the challenger arms. Let $\beta \in (0, 1)$, e.g., $\beta = 1/2$. We use a fixed $\beta$-design $\beta_n(B_n, C_n) := \beta$. The mechanism to choose the next arm to sample should enforce that this target is reached on average. We use $K$ independent $\beta$-tracking procedures (one per leader), i.e., $a_n = B_n$ if $N_{n,B_n}^{B_n} \le \beta L_{n+1,B_n}$ and $a_n = C_n$ otherwise, where $N_{n,a}^a = \sum_{t \in [n-1]} \mathbf{1}((B_t, a_t) = (a, a))$ and $L_{n,a} = \sum_{t \in [n-1]} \mathbf{1}(B_t = a)$. Using Degenne et al. [2020b, Theorem 6] for each tracking procedure yields $-1/2 \le N_{n,a}^a - \beta L_{n,a} \le 1$ for all $a \in [K]$.
**Computational and Memory Cost.** The GPE$_{η}(\epsilon)$ sums the observations, and the recommendation and GLR stopping rules are updated when an arm is updated. Using the closed-form formula for $W_{\epsilon,a,b}$ (Lemma 38), the per-iteration computational and global memory costs of DP-TT are $O(K)$.

**Asymptotic Upper Bound on the Expected Sample Complexity.** Given a fixed target $\beta$, the empirical allocation of $a^*$ converges towards $\beta$, that differs from $w_{\epsilon,a^*}^*$. At best, we can estimate the $\beta$-optimal allocation $w_{\epsilon,\beta}^*(\nu)$, i.e., maximizer of the inverse $\beta$-characteristic time $T_{\epsilon,\beta}^*(\nu)^{-1}$ defined as in Eq. (5) with the constraint $w_{a^*} = \beta$. While being only nearly asymptotic optimal, i.e., $T_{\epsilon}^*(\nu) = \min_{\beta \in (0,1)} T_{\epsilon,\beta}^*(\nu)$, it satisfies $T_{\epsilon,1/2}^*(\nu) \le 2T_{\epsilon}^*(\nu)$ (Lemma 44).

DP-TT is $\epsilon$-global DP, $\delta$-correct and matches $T_{\epsilon}^*(\nu)$ to a small constant, for any privacy budget $\epsilon$. While Theorem 7 is an asymptotic upper bound for $\delta \to 0$, it holds for any $\epsilon$.

**Theorem 7.** Let $(\epsilon, \delta, \eta, \beta) \in \mathbb{R}_+^* \times (0, 1) \times \mathbb{R}_+^* \times (0, 1)$ and $c$ as in Eq. (8). The DP-TT algorithm is $\epsilon$-global DP, $\delta$-correct and satisfies that, for any Bernoulli instance $\nu$ with distinct means $\mu \in (0, 1)^K$,

$$ \limsup_{\delta \to 0} \frac{\mathbb{E}_{\nu\pi}[\tau_{\epsilon,\delta}]}{\log(1/\delta)} \le 2(1+\eta)T_{\epsilon,\beta}^*(\nu). $$

*Proof.* The proof (Appendix H) builds on the unified analysis of Jourdan et al. [2022] and relies heavily on the derived regularity properties for $d_{\epsilon}^{\pm}$, $(W_{\epsilon,a,b})_{(a,b)}$, $T_{\epsilon,\beta}^*(\nu)$ and $w_{\epsilon,\beta}^*(\nu)$ (Appendix G). $\square$

For $(\eta, \beta) = (1, 1/2)$, the asymptotic upper bound is $4T_{\epsilon,1/2}^*(\nu) \le 8T_{\epsilon}^*(\nu)$. For any privacy budget $\epsilon$, we reduced the gap between known lower and upper bounds for fixed-confidence BAI under $\epsilon$-global DP to a constant lower than 8, hence closing the open problem in Azize et al. [2024]. A discussion on how to improve this constant is deferred to Appendix C.2. Since DP-TT enjoys good empirical performance for moderate value of $\delta$ (Figure 1), adapting the non-asymptotic upper bound in Jourdan et al. [2024] to the private setting is an interesting direction for future work.

**Comparison with Azize et al. [2023, 2024].** AdaP-TT and AdaP-TT\* use the DAF($\epsilon$) estimator, GLR-inspired recommendation/stopping rules and the TTUCB [Jourdan and Degenne, 2024] sampling rule (i.e., UCB-TC-$\beta$ [Jourdan, 2024]), all based on arm-dependent doubling, forgetting and unclipped estimators. While AdaP-TT relies on the non-private Gaussian transportation costs, AdaP-TT\* accounts for a high privacy regime by clipping the mean gap, i.e., $(\mu_a - \mu_b)_+ \min\{3\epsilon, (\mu_a - \mu_b)_+\}$ instead of $(\mu_a - \mu_b)^2$. The AdaP-TT and AdaP-TT\* algorithms are $\epsilon$-global DP and $\delta$-correct. The sample complexity of AdaP-TT only matches the high privacy lower bound for instances where the means are of similar order. AdaP-TT\* improves on AdaP-TT by matching the high privacy lower bound for all instances with distinct means. However, both AdaP-TT and AdaP-TT\* fail to match the lower bound beyond the high-privacy regime, due to the use of non-adapted transportation costs. In contrast, DP-TT uses the $d_{\epsilon}$-inspired transportation costs, matching the lower bound up to a small constant for all values of $\epsilon$.

**Comparison with Sajed and Sheffet [2019].** DP-SE [Sajed and Sheffet, 2019] is an $\epsilon$-global DP version of the Successive Elimination algorithm introduced for the regret minimisation setting, modified by Azize et al. [2023] into a $\epsilon$-global and $\delta$-correct BAI algorithm. Compared to DP-TT, DP-SE is less adaptive and not anytime, since it relies on uniform sampling within each phase and the phase length depends explicitly on the risk $\delta$. The high probability upper bound on the sample complexity scales as $O(\sum_{a \ne a^*} (\Delta_a \min\{\epsilon, \Delta_a\})^{-1})$ with $\Delta_a = \mu_{a^*} - \mu_a$. This matches the lower bound when $\epsilon \to 0$ (to a constant), but fails to recover the sample-complexity lower bound beyond this regime.

# 6 Experiments

The empirical performance of DP-TT with $(\eta, \beta) = (1, 1/2)$ is compared to AdaP-TT [Azize et al., 2023], AdaP-TT\* [Azize et al., 2024], and DP-SE [Sajed and Sheffet, 2019] on different Bernoulli instances for varying privacy budget, ranging from 0.001 to 125 (see Appendix J.1). The first instance has means $\mu_1 = (0.95, 0.9, 0.9, 0.9, 0.5)$ and the second instance has means $\mu_2 = (0.75, 0.7, 0.7, 0.7, 0.7)$. As a benchmark, we also compare to the non-private EB-TCI-$\beta$
<figure><img src="image_2.png" /><figcaption>Figure 1: Empirical stopping time $\tau_{\epsilon,\delta}$ (mean $\pm 2$ std) for $\delta = 10^{-2}$ with respect to the privacy budget $\epsilon$ on Bernoulli instances (a) $\mu_1$ and (b) $\mu_2$. The vertical line separates the two privacy regimes.</figcaption></figure>

algorithm with $\beta = 1/2$. For $\delta = 10^{-2}$, we run each algorithm 1000 times, and plot the averaged empirical stopping times in Figure 1. Additional experiments are in Appendix J.

Figure 1 shows that DP-TT outperforms all the other $\delta$-correct and $\epsilon$-global DP BAI algorithms, for different values of $\epsilon$ and in all the instances tested. The empirical performance of DP-TT demonstrates two regimes. A high-privacy regime, where the stopping time depends on the privacy budget $\epsilon$, and a low privacy regime, where the performance of DP-TT is independent of $\epsilon$, and requires twice the number of samples used by the non-private EB-TCI-$\beta$. In Figure 1, the vertical lines are both at $\epsilon = 0.45$. We compare with our allocation-independent condition, i.e., $\max_{a \neq a^*} \epsilon_{a^*,a}$ where $\epsilon_{a,b} = \log \left( \frac{\mu_{a^*} (1-\mu_a)}{\mu_a (1-\mu_{a^*})} \right)$. For $\mu_2$, we have $\epsilon_{1,a} = 0.25$ for all $a \neq 1$ that is close to the empirical separation. For $\mu_1$, we have $\epsilon_{1,5} = 2.94$ and $\epsilon_{1,a} = 0.75$ for all $a \in \{2, 3, 4\}$. When an arm has a significantly lower mean, an allocation-dependent condition, such as Eq. (6), is required to reflect the empirical separation. Intuitively, an arm with a significantly lower mean will also be sampled significantly less, hence there is a compounding effect.

# 7 Conclusion

Motivated by the privacy requirements of sensitive applications of BAI, we address the problem of fixed-confidence BAI under $\epsilon$-global DP. We narrow the gap between the lower and upper bounds on the expected sample complexity to a multiplicative constant smaller than 8, for all $\epsilon$ values. Our novel lower bound incorporates $d_{\epsilon}$ an information-theoretic quantity smoothly balancing KL divergence and TV distance, scaled by $\epsilon$. We design a private, arm-dependent geometric grid estimator *without forgetting* and a GLR stopping rule based on the $d_{\epsilon}$-transportation costs, whose correctness requires novel concentration results for Laplace and mixed distributions. Finally, we proposed a Top Two sampling rule that achieves an asymptotic upper bound matching our lower bound to a small constant.

We detailed research directions to further reduce the constant gap between the lower and upper bounds, by improving both the calibration of the stopping threshold and the analysis of the sampling rule. The most exciting direction for future work is to extend our results to other classes of distributions (e.g., Gaussian or bounded distributions), structured settings (e.g., linear or unimodal), or other identification problems (e.g., approximate BAI or Good Arm Identification). Another interesting research direction is to extend the proposed technique to other variants of pure DP (e.g., $(\epsilon, \delta)$-DP or Rényi DP [Mironov, 2017]) or other trust models (e.g., shuffle DP [Cheu, 2021; Girgis et al., 2021]).

# Acknowledgments and Disclosure of Funding

We thank Junya Honda for the interesting discussions. Marc Jourdan was supported by the Swiss National Science Foundation (grant number 212111) and by an unrestricted gift from Google. Achraf Azize thanks the support of the FairPlay Joint Team.
References

Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In *International Conference on Machine Learning*, pages 32–40. PMLR, 2017.

Shubhada Agrawal, Sandeep Juneja, and Peter W. Glynn. Optimal $\delta$-correct best-arm selection for heavy-tailed distributions. In *Algorithmic Learning Theory (ALT)*, 2020.

J-Y. Audibert and S. Bubeck. Regret Bounds and Minimax Policies under Partial Monitoring. *Journal of Machine Learning Research*, 2010a.

J-Y. Audibert, S. Bubeck, and R. Munos. Best Arm Identification in Multi-armed Bandits. In *Conference on Learning Theory*, 2010.

Jean-Yves Audibert and Sébastien Bubeck. Regret bounds and minimax policies under partial monitoring. *The Journal of Machine Learning Research*, 11:2785–2836, 2010b.

Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. *Machine learning*, 47(2-3):235–256, 2002.

Peter Auer, Chao-Kai Chiang, Ronald Ortner, and Madalina Drugan. Pareto front identification from stochastic bandit feedback. In *Artificial intelligence and statistics*, pages 939–947. PMLR, 2016.

Maryam Aziz, Emilie Kaufmann, and Marie-Karelle Riviere. On multi-armed bandit designs for dose-finding clinical trials. *The Journal of Machine Learning Research*, 22(1):686–723, 2021.

Achraf Azize and Debabrota Basu. When privacy meets partial information: A refined analysis of differentially private bandits. *Advances in Neural Information Processing Systems*, 35:32199–32210, 2022.

Achraf Azize and Debabrota Basu. Concentrated differential privacy for bandits. In *2nd IEEE Conference on Secure and Trustworthy Machine Learning*, 2024.

Achraf Azize, Marc Jourdan, Aymen Al Marjani, and Debabrota Basu. On the complexity of differentially private best-arm identification with fixed confidence. *Thirty-Seventh Conference on Neural Information Processing Systems*, 2023.

Achraf Azize, Marc Jourdan, Aymen Al Marjani, and Debabrota Basu. Differentially private best-arm identification. *arXiv preprint arXiv:2406.06408*, 2024.

Achraf Azize, Yulian Wu, Junya Honda, Francesco Orabona, Shinji Ito, and Debabrota Basu. Optimal regret of bernoulli bandits under global differential privacy. *arXiv preprint arXiv:2505.05613*, 2025.

Agniv Bandyopadhyay, Sandeep Juneja, and Shubhada Agrawal. Optimal top-two method for best arm identification and fluid analysis. *Thirty-Eighth Conference on Neural Information Processing Systems*, 2024.

Debabrota Basu, Christos Dimitrakakis, and Aristide Tossou. Differential privacy for multi-armed bandits: What is it and what is its cost? *arXiv preprint arXiv:1905.12298*, 2019.

Claude Berge. *Topological Spaces: including a treatment of multi-valued functions, vector spaces, and convexity*. Courier Corporation, 1997.

Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. *Concentration Inequalities: A Nonasymptotic Theory of Independence*. Oxford University Press, 2013.

Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. *Foundations and Trends® in Machine Learning*, 5(1):1–122, 2012.

Alexandra Carpentier and Andrea Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In *Conference on Learning Theory*, pages 590–604. PMLR, 2016.

T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. *ACM Trans. Inf. Syst. Secur.*, 14(3), nov 2011. ISSN 1094-9224. doi: 10.1145/2043621.2043626.
Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao, and Ruosong Wang. Nearly optimal sampling algorithms for combinatorial pure exploration. In *Proceedings of the 30th Conference on Learning Theory (COLT)*, 2017.

Shouyuan Chen, Tian Lin, Irwin King, Michael R Lyu, and Wei Chen. Combinatorial pure exploration of multi-armed bandits. *Advances in neural information processing systems*, 27, 2014.

Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In *International Conference on Machine Learning*, 2013.

Zhirui Chen, P. N. Karthik, Yeow Meng Chee, and Vincent Tan. Fixed-budget differentially private best arm identification. In *The Twelfth International Conference on Learning Representations*, 2024.

Herman Chernoff. Sequential Design of Experiments. *The Annals of Mathematical Statistics*, 30: 755-770, 1959.

Albert Cheu. Differential privacy in the shuffle model: A survey of separations. *arXiv preprint arXiv:2107.11839*, 2021.

Sayak Ray Chowdhury and Xingyu Zhou. Shuffle private linear contextual bandits. In *International Conference on Machine Learning*, pages 3984–4009. PMLR, 2022.

R. Combes and A. Proutière. Unimodal bandits: Regret lower bounds and optimal algorithms. In *International Conference on Machine Learning (ICML)*, 2014.

Rémy Degenne and Wouter M Koolen. Pure exploration with multiple correct answers. *Advances in Neural Information Processing Systems*, 32, 2019.

Rémy Degenne, Pierre Ménard, Xuedong Shang, and Michal Valko. Gamification of pure exploration for linear bandits. In *International Conference on Machine Learning*, pages 2432–2442. PMLR, 2020a.

Rémy Degenne, Han Shao, and Wouter Koolen. Structure adaptive algorithms for stochastic bandits. In *International Conference on Machine Learning*, pages 2443–2452. PMLR, 2020b.

Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. *Foundations and Trends® in Theoretical Computer Science*, 9(3–4):211–407, 2014.

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In *Proceedings of the Third Conference on Theory of Cryptography*, TCC’06, pages 265–284, Berlin, Heidelberg, 2006. Springer-Verlag.

Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In *ACM symposium on Theory of computing*, pages 715–724. ACM, 2010.

Eyal Even-Dar, Shie Mannor, and Yishay Mansour. PAC bounds for multi-armed bandit and Markov decision processes. In *Conference on Computational Learning Theory, COLT ’02*, page 255–270, Berlin, Heidelberg, 2002. Springer-Verlag. ISBN 354043836X.

Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. *Journal of machine learning research*, 7(6), 2006.

S. Filippi, O. Cappé, A. Garivier, and C. Szepesvári. Parametric Bandits: The Generalized Linear case. In *Advances in Neural Information Processing Systems*, 2010.

Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. *Advances in Neural Information Processing Systems*, 25, 2012.

Evrard Garcelon, Kamalika Chaudhuri, Vianney Perchet, and Matteo Pirotta. Privacy amplification via shuffling for linear contextual bandits. In *International Conference on Algorithmic Learning Theory*, pages 381–407. PMLR, 2022.
Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In *Conference on Learning Theory*, pages 998–1027. PMLR, 2016.

Antonious M Girgis, Deepesh Data, Suhas Diggavi, Ananda Theertha Suresh, and Peter Kairouz. On the renyi differential privacy of the shuffle model. In *ACM SIGSAC Conference on Computer and Communications Security*, pages 2321–2341, 2021.

Yuxuan Han, Zhipeng Liang, Yang Wang, and Jiheng Zhang. Generalized linear bandits with local differential privacy. *Advances in Neural Information Processing Systems*, 34:26511–26522, 2021.

Osama Hanna, Antonious M Girgis, Christina Fragouli, and Suhas Diggavi. Differentially private stochastic linear bandits:(almost) for free. *IEEE Journal on Selected Areas in Information Theory*, 2024.

Junya Honda and Akimichi Takemura. Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. *Journal of Machine Learning Research (JMLR)*, 16:3721–3756, 2015.

Bingshan Hu and Nidhi Hegde. Near-optimal thompson sampling-based algorithms for differentially private stochastic bandits. In *Uncertainty in Artificial Intelligence*, pages 844–852. PMLR, 2022.

Bingshan Hu, Zhiming Huang, and Nishant A Mehta. Near-optimal algorithms for private online learning in a stochastic environment. *arXiv e-prints*, pages arXiv-2102, 2021.

Bingshan Hu, Zhiming Huang, Tianyue H Zhang, Mathias Lécuyer, and Nidhi Hegde. Connecting thompson sampling and ucb: Towards more efficient trade-offs between privacy and regret. *arXiv preprint arXiv:2505.02383*, 2025.

K. Jamieson, S. Katariya, A. Deshpande, and R. Nowak. Sparse Dueling Bandits. In *Proceedings of the 18th Conference on Artificial Intelligence and Statistics*, 2015.

Kevin Jamieson and Robert Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In *Conference on Information Sciences and Systems (CISS)*, pages 1–6. IEEE, 2014.

Marc Jourdan. *Solving Pure Exploration Problems with the Top Two Approach*. PhD thesis, Université de Lille, 2024.

Marc Jourdan and Rémy Degenne. Non-asymptotic analysis of a ucb-based top two algorithm. *Advances in Neural Information Processing Systems*, 36, 2024.

Marc Jourdan, Rémy Degenne, Dorian Baudry, Rianne de Heide, and Emilie Kaufmann. Top two algorithms revisited. *Advances in Neural Information Processing Systems*, 35:26791–26803, 2022.

Marc Jourdan, Rémy Degenne, and Emilie Kaufmann. Dealing with unknown variances in best-arm identification. *International Conference on Algorithmic Learning Theory*, 2023.

Marc Jourdan, Rémy Degenne, and Emilie Kaufmann. An $\epsilon$-best-arm identification algorithm for fixed-confidence and beyond. *Advances in Neural Information Processing Systems*, 36, 2024.

Kwang-Sung Jun, Lalit Jain, Houssam Nassif, and Blake Mason. Improved Confidence Bounds for the Linear Logistic Model and Applications to Bandits. In *International Conference on Machine Learning*, 2021.

Dionysios S Kalogerias, Kontantinos E Nikolakakis, Anand D Sarwate, and Or Sheffet. Quantile multi-armed bandits: Optimal best-arm identification and a differentially private scheme. *IEEE Journal on Selected Areas in Information Theory*, 2(2):534–548, 2021.

Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection in stochastic multi-armed bandits. In *International Conference on Machine Learning*, volume 12, pages 655–662, 2012.

Julian Katz-Samuels and Clayton Scott. Top Feasible Arm Identification. In *International Conference on Artificial Intelligence and Statistics (AISTATS)*, 2019.
Tomás Kocák and Aurélien Garivier. Epsilon best arm identification in spectral bandits. In *International Joint Conference on Artificial Intelligence (IJCAI)*, pages 2636–2642, 2021.

Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. *Advances in applied mathematics*, 6(1):4–22, 1985.

Tor Lattimore and Csaba Szepesvári. *Bandit algorithms*. Cambridge University Press, 2020.

Fengjiao Li, Xingyu Zhou, and Bo Ji. Differentially private linear bandits with partial distributed feedback. In *2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt)*, pages 41–48. IEEE, 2022.

Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. *The Journal of Machine Learning Research*, 18(1):6765–6816, 2017.

Pieter JK Libin, Timothy Verstraeten, Diederik M Roijers, Jelena Grujic, Kristof Theys, Philippe Lemey, and Ann Nowé. Bayesian best-arm identification for selecting influenza mitigation strategies. In *Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2018*, 2019.

Simon Lindståhl, Alexandre Proutiere, and Andreas Johnsson. Measurement-based admission control in sliced networks: A best arm identification approach. In *GLOBECOM 2022-2022 IEEE Global Communications Conference*, pages 1484–1490. IEEE, 2022.

David E Losada, David Elsweiler, Morgan Harvey, and Christoph Trattner. A day at the races: using best arm identification algorithms to reduce the cost of information retrieval user studies. *Applied Intelligence*, 52(5):5617–5632, 2022.

S. Magureanu, R. Combes, and A. Proutière. Lipschitz Bandits: Regret lower bounds and optimal algorithms. In *Proceedings on the 27th Conference On Learning Theory*, 2014.

Shie Mannor and John N Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. *Journal of Machine Learning Research*, 5(Jun):623–648, 2004.

Ilya Mironov. Rényi differential privacy. In *2017 IEEE 30th computer security foundations symposium (CSF)*, pages 263–275. IEEE, 2017.

Nikita Mishra and Abhradeep Thakurta. (Nearly) optimal differentially private stochastic multi-arm bandits. In *Conference on Uncertainty in Artificial Intelligence*, 2015.

Seth Neel and Aaron Roth. Mitigating bias in adaptive data gathering via differential privacy. In *International Conference on Machine Learning*, pages 3720–3729. PMLR, 2018.

Nikola Pavlovic, Sudeep Salgia, and Qing Zhao. Differentially private kernelized contextual bandits. In *The 28th International Conference on Artificial Intelligence and Statistics*, 2025.

Chao Qin, Diego Klabjan, and Daniel Russo. Improving the expected improvement algorithm. *Advances in Neural Information Processing Systems*, 30, 2017.

H. Robbins. Some aspects of the sequential design of experiments. *Bulletin of the American Mathematical Society*, 58(5):527–535, 1952.

Daniel Russo. Simple bayesian algorithms for best arm identification. In *Conference on Learning Theory*, pages 1417–1418. PMLR, 2016.

Touqir Sajed and Or Sheffet. An optimal private stochastic-mab algorithm based on optimal private stopping rule. In *International Conference on Machine Learning*, pages 5579–5588. PMLR, 2019.

Xuedong Shang, Rianne Heide, Pierre Menard, Emilie Kaufmann, and Michal Valko. Fixed-confidence guarantees for bayesian best-arm identification. In *International Conference on Artificial Intelligence and Statistics*, pages 1823–1832. PMLR, 2020.

Roshan Shariff and Or Sheffet. Differentially private contextual linear bandits. In *Advances in Neural Information Processing Systems*, pages 4296–4306, 2018.
Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification in linear bandits. *Advances in Neural Information Processing Systems*, 27, 2014.

Rangarajan K Sundaram. *A first course in optimization theory*. Cambridge university press, 1996.

Jay Tenenbaum, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Differentially private multi-armed bandits in the shuffle model. *Advances in Neural Information Processing Systems*, 34: 24956–24967, 2021.

Abhradeep Guha Thakurta and Adam Smith. (Nearly) optimal algorithms for private online learning in full-information and bandit settings. *Advances in Neural Information Processing Systems*, 26, 2013.

William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. *Biometrika*, 25(3-4):285–294, 1933.

Aristide CY Tossou and Christos Dimitrakakis. Achieving privacy in the adversarial multi-armed bandit. In *Thirty-First AAAI Conference on Artificial Intelligence*, 2017.

Katherine Tucker, Janice Branson, Maria Dilleen, Sally Hollis, Paul Loughlin, Mark J Nixon, and Zoë Williams. Protecting patient privacy when sharing patient-level data from clinical trials. *BMC medical research methodology*, 16(1):5–14, 2016.

J. Ville. *Étude Critique de la Notion de Collectif*. Collection des monographies des probabilités. Gauthier-Villars, 1939.

Siwei Wang and Jun Zhu. Optimal learning policies for differential privacy in multi-armed bandits. *Journal of Machine Learning Research*, 25(314):1–52, 2024.

Wei You, Chao Qin, Zihao Wang, and Shuoguang Yang. Information-directed selection for top-two algorithms. In *Conference on Learning Theory*, pages 2850–2851. PMLR, 2023.

Wanrong Zhang, Yajun Mei, and Rachel Cummings. Private sequential hypothesis testing for statisticians: Privacy, error rates, and sample size. In *International Conference on Artificial Intelligence and Statistics*, pages 11356–11373. PMLR, 2022.

Yao Zhao, Connor James Stephens, Csaba Szepesvári, and Kwang-Sung Jun. Revisiting simple regret: Fast rates for returning a good arm. In *40th International Conference on Machine Learning (ICML)*, 2023.

Kai Zheng, Tianle Cai, Weiran Huang, Zhengguo Li, and Liwei Wang. Locally differentially private (contextual) bandits learning. In *Advances in Neural Information Processing Systems*, volume 33, pages 12300–12310, 2020.

Yuan Zhou, Xi Chen, and Jian Li. Optimal pac multiple arm identification with applications to crowdsourcing. In *International Conference on Machine Learning*, pages 217–225. PMLR, 2014.
# NeurIPS Paper Checklist

## 1. Claims

**Question:** Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?

**Answer:** [Yes]

**Justification:** The claims made in the abstract and introduction reflect the paper's contributions and scope. Those claims are substantiated with details in the Sections 3, 4, 5 and 6 of the main paper. They are proven theoretically in Appendices D, F, G, H, I and J.

**Guidelines:**

* The answer NA means that the abstract and introduction do not include the claims made in the paper.

* The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.

* The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.

* It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.

## 2. Limitations

**Question:** Does the paper discuss the limitations of the work performed by the authors?

**Answer:** [Yes]

**Justification:** The limitations of Theorems 6 and 7 are detailed in Sections 4 and Appendix C.2. The low computational and memory costs of the DP-TT algorithm is discussed in Sections 4 and 5. Our work addresses the ε-global Differential Privacy constraint for fixed-confidence Best Arm Identification. Our algorithm can be deployed in data-sensitive applications, such as adaptive clinical trials or user studies.

**Guidelines:**

* The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.

* The authors are encouraged to create a separate "Limitations" section in their paper.

* The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.

* The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.

* The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.

* The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.

* If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.

* While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
### 3. Theory assumptions and proofs

**Question:** For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?

**Answer:** [Yes]

**Justification:** Theorem 2 is proven in Appendix D. Theorem 4 is based on numerous results proven in Appendix G. Lemma 5 is proven in Appendix E. Theorem 6 is proven in Appendix F. Theorem 7 is proven in Appendix H. All the other results mentioned in the main paper are proven theoretically in Appendices D, F, G, H and I.

**Guidelines:**

* The answer NA means that the paper does not include theoretical results.

* All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.

* All assumptions should be clearly stated or referenced in the statement of any theorems.

* The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.

* Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.

* Theorems and Lemmas that the proof relies upon should be properly referenced.

### 4. Experimental result reproducibility

**Question:** Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?

**Answer:** [Yes]

**Justification:** Implementation details on our experiments are given in Section 6 and Appendix J. The DP-TT algorithm is summarized in Algorithm 1, and includes default choices of hyper-parameters. Our experiments are reproducible and the code is provided as supplementary material.

**Guidelines:**

* The answer NA means that the paper does not include experiments.

* If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.

* If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.

* Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general, releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.

* While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example

(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.

(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.

(c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.

## 5. Open access to data and code

Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?

Answer: [Yes]

Justification: The code for our experiments is provided as supplementary material, and we provide sufficient instructions to faithfully reproduce our experimental results. As we rely on synthetic experiments on Bernoulli distributions, there is no dataset per se.

Guidelines:

* The answer NA means that paper does not include experiments requiring code.

* Please see the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.

* While we encourage the release of code and data, we understand that this might not be possible, so “No” is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).

* The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.

* The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.

* The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.

* At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).

* Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.

## 6. Experimental setting/details

Question: Does the paper specify all the training and test details (e.g., data splits, hyper-parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?

Answer: [Yes]

Justification: The code for our experiments is provided as supplementary material. We provide sufficient implementation details in Section 6 and Appendix J. The DP-TT algorithm is summarized in Algorithm 1, and includes default choices of hyper-parameters.

Guidelines:

* The answer NA means that the paper does not include experiments.

* The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.

* The full details can be provided either with the code, in appendix, or as supplemental material.

## 7. Experiment statistical significance

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?

Answer: [Yes]
Justification: The figures in Section 6 and Appendix J report the empirical means over 1000 runs for each algorithm. The 2-sigma error bars are based on the standard deviation of the means over those runs.

Guidelines:

* The answer NA means that the paper does not include experiments.

* The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.

* The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).

* The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

* The assumptions made should be given (e.g., Normally distributed errors).

* It should be clear whether the error bar is the standard deviation or the standard error of the mean.

* It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.

* For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).

* If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.

## 8. Experiments compute resources

Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?

Answer: [Yes]

Justification: Appendix J contains detailed information as regards the computational resources used for our experiments. The specific institutional cluster is omitted for the sake of anonymity. Overall, our experiments are relatively computationally inexpensive, and they could be run on a professional laptop.

Guidelines:

* The answer NA means that the paper does not include experiments.

* The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.

* The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.

* The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).

## 9. Code of ethics

Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?

Answer: [Yes]

Justification: After reading it, we confirm that the research conducted in our paper complies with the NeurIPS Code of Ethics.

Guidelines:

* The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.

* If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
* The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).

## 10. Broader impacts

**Question:** Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?

**Answer:** [Yes]

**Justification:** Our work addresses the ε-global Differential Privacy constraint for fixed-confidence Best Arm Identification. Our algorithm can be deployed in data-sensitive applications, such as adaptive clinical trials or user studies. Therefore, our paper can have a significant positive societal impact.

**Guidelines:**

* The answer NA means that there is no societal impact of the work performed.

* If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.

* Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.

* The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.

* The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.

* If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).

## 11. Safeguards

**Question:** Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?

**Answer:** [NA]

**Justification:** To the best of our understanding, our paper doesn't necessitate safeguards. Our experiments use synthetic Bernoulli data and our algorithm satisfy the ε-global Differential Privacy constraint.

**Guidelines:**

* The answer NA means that the paper poses no such risks.

* Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.

* Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.

* We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.

## 12. Licenses for existing assets
**Question:** Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?

**Answer:** [NA]

**Justification:** Our paper does not rely on existing assets. Our experiments use synthetic Bernoulli data and our algorithm was implemented from scratch.

**Guidelines:**

* The answer NA means that the paper does not use existing assets.

* The authors should cite the original paper that produced the code package or dataset.

* The authors should state which version of the asset is used and, if possible, include a URL.

* The name of the license (e.g., CC-BY 4.0) should be included for each asset.

* For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.

* If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.

* For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.

* If this information is not available online, the authors are encouraged to reach out to the asset's creators.

## 13. New assets

**Question:** Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?

**Answer:** [NA]

**Justification:** Our paper does not introduce new assets. The code for our experiments is provided as supplementary material, yet it does not constitute an asset per se.

**Guidelines:**

* The answer NA means that the paper does not release new assets.

* Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.

* The paper should discuss whether and how consent was obtained from people whose asset is used.

* At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.

## 14. Crowdsourcing and research with human subjects

**Question:** For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?

**Answer:** [NA]

**Justification:** Our paper does not involve crowdsourcing nor research with human subjects.

**Guidelines:**

* The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.

* Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.

* According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. **Institutional review board (IRB) approvals or equivalent for research with human subjects**

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?

Answer: [NA]

Justification: Our paper does not involve crowdsourcing nor research with human subjects.

Guidelines:

* The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.

* Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.

* We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.

* For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.

16. **Declaration of LLM usage**

Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.

Answer: [NA]

Justification: Our theoretical and empirical contributions do not involve LLMs.

Guidelines:

* The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.

* Please refer to our LLM policy (https://neurips.cc/Conferences/2025/LLM) for what should or should not be described.
## A Outline

The appendices are organized as follows:

* Notation are summarized in Appendix B.

* A detailed related work and an extended discussion is given in Appendix C.

* The lower bound on the expected sample complexity under $\epsilon$-global DP (Theorem 2) is proven in Appendix D.

* The proof of Lemma 5 is given in Appendix E.

* The proof of our concentration results are detailed in Appendix F. In particular, this includes the proof of Theorem 6.

* Appendix G gathers key properties on the (resp. modified) divergence $d_{\epsilon}^{\pm}$ (resp. $\tilde{d}_{\epsilon}^{\pm}$), the (resp. modified) transportation costs $W_{\epsilon,a,b}$ (resp. $\tilde{W}_{\epsilon,a,b}$) and (resp. $\beta$-)characteristic times $T_{\epsilon}^{*}(\nu)$ (resp. $T_{\epsilon,\beta}^{*}(\nu)$) and their (resp. $\beta$-)optimal allocation $w_{\epsilon}^{*}(\nu)$ (resp. $w_{\epsilon,\beta}^{*}(\nu)$). In particular, this includes the proof of Theorem 4 based on Lemmas 43 and 47.

* The proof of the upper bound on the asymptotic expected sample complexity of DP-TT (Theorem 7) is given in Appendix H.

* In Appendix I, we propose variants of algorithms to tackle $\epsilon$-global DP BAI. We aim at providing several choices for the interested practitioners.

* Implementation details and additional experiments are presented in Appendix J.

<table><caption>Table 1: Notation for the setting.</caption><thead><tr><th>Notation</th><th>Type</th><th>Description</th></tr></thead><tbody><tr><td>K</td><td>N</td><td>Number of arms</td></tr><tr><td>F</td><td>&le; P([0, 1])</td><td>Class of Bernoulli distributions</td></tr><tr><td>&nu;<sub>a</sub></td><td>F</td><td>Bernoulli distribution of arm a &isin; [K]</td></tr><tr><td>&nu;</td><td>F<sup>K</sup></td><td>Vector of Bernoulli distributions, &nu; := (&nu;<sub>a</sub>)<sub>a&isin;[K]</sub></td></tr><tr><td>&mu;<sub>a</sub></td><td>(0, 1)</td><td>Mean of arm a &isin; [K]</td></tr><tr><td>&mu;</td><td>(0, 1)<sup>K</sup></td><td>Vector of means, &mu; := (&mu;<sub>a</sub>)<sub>a&isin;[K]</sub></td></tr><tr><td>a<sup>*</sup>(&mu;), a<sup>*</sup>(&nu;)</td><td>&le; [K]</td><td>Set of best arms, a<sup>*</sup>(&nu;) = a<sup>*</sup>(&mu;) := arg max<sub>a&isin;[K]</sub> &mu;<sub>a</sub></td></tr><tr><td>a<sup>*</sup></td><td>[K]</td><td>Unique best arm, i.e., a<sup>*</sup>(&mu;) = {a<sup>*</sup>}</td></tr><tr><td>&epsilon;</td><td>R<sup>*</sup></td><td>Privacy budget for &epsilon;-global DP</td></tr><tr><td>&delta;</td><td>(0, 1)</td><td>Risk for &delta;-correctness</td></tr><tr><td>Alt(&nu;)</td><td>&le; F<sup>K</sup></td><td>Alternative instances with different best arms</td></tr></tbody></table>

## B Notation

We recall some commonly used notation: the set of integers $[n] := \{1, \dots, n\}$, the complement $X^c$ and interior $\tilde{X}$ of a set $X$, the indicator function $1(X)$ of an event, the probability $P_{\nu\pi}$ and the expectation $E_{\nu\pi}$ taken over the randomness of the observations from $\nu$ and the algorithm $\pi$, Landau's notation $o$, $O$, $\Omega$ and $\Theta$, the $(K-1)$-dimensional probability simplex $\Delta_K := \{w \in \mathbb{R}_+^K | w \ge 0, \sum_{i \in [K]} w_i = 1\}$. The functions $[x]_0^1 := \max\{0, \min\{1, x\}\}$, $k_{\eta}(x) := 1 + \log_{1+\eta} x$, $\overline{W}_{-1}$ in Lemma 52, $h$ in Eq. (31), $r$ in Eq. (33), $\zeta$ is the Riemann $\zeta$ function. Moreover, we recall the definitions: $d_{\epsilon}^{\pm}$ in Eq. (3), $d_{\epsilon}$ in Eq. (1), $\tilde{d}_{\epsilon}^{\pm}$ in Eq. (32), $W_{\epsilon,a,b}^{\pm}$ in Eq. (4), $\tilde{W}_{\epsilon,a,b}^{\pm}$ in Eq. (34), $(T_{\epsilon}^{*}(\nu), T_{\epsilon,\beta}^{*}(\nu), w_{\epsilon}^{*}(\nu), w_{\epsilon,\beta}^{*}(\nu))$ in Eq. 35. While Table 1 gathers problem-specific notation, Table 2 groups notation for the algorithms.
<table><caption>Table 2: Notation for the algorithm.</caption><thead><tr><th>Notation</th><th>Type</th><th>Description</th></tr></thead><tbody><tr><td>B<sub>n</sub></td><td>[K]</td><td>(EB) Leader at time n</td></tr><tr><td>C<sub>n</sub></td><td>[K]</td><td>(TC) Challenger at time n</td></tr><tr><td>a<sub>n</sub></td><td>[K]</td><td>Arm sampled at time n</td></tr><tr><td>X<sub>n,a<sub>n</sub></sub></td><td>{0, 1}</td><td>Sample observed at the end of time n, i.e. X<sub>n,a<sub>n</sub></sub> ~ v<sub>a<sub>n</sub></sub></td></tr><tr><td>Y<sub>k<sub>n,a</sub>,a</sub></td><td>R</td><td>Noisy perturbation drawn at the beginning of phase k<sub>n,a</sub> for arm a, i.e. Y<sub>k<sub>n,a</sub>,a</sub> ~ Lap(1/ε)</td></tr><tr><td>F<sub>n</sub></td><td>[K]</td><td>History before time n</td></tr><tr><td>ā<sub>n</sub></td><td>N</td><td>Arm recommended before time n</td></tr><tr><td>τ<sub>ε,δ</sub></td><td></td><td>Sample complexity (stopping time)</td></tr><tr><td>c(n, ε, δ)</td><td>N × R<sup>*</sup> × (0, 1) → R<sup>*</sup></td><td>Stopping threshold function</td></tr><tr><td>c<sub>1</sub>(n, δ)</td><td>N × (0, 1) → R<sup>*</sup></td><td>Stopping threshold function</td></tr><tr><td>c<sub>2</sub>(n, ε)</td><td>N × R<sup>*</sup> → R<sup>*</sup></td><td>Approximation threshold function</td></tr><tr><td>N<sub>n,a</sub></td><td>N</td><td>Number of pulls of arm a before time n</td></tr><tr><td>k<sub>n,a</sub></td><td>N</td><td>Current phase of arm a at time n</td></tr><tr><td>T<sub>k</sub>(a)</td><td>N</td><td>Time n where the arm a changes to phase k</td></tr><tr><td>S̃<sub>k,a</sub></td><td>R</td><td>Private sum of observations for arm a at phase k</td></tr><tr><td>Ñ<sub>n,a</sub></td><td>N</td><td>Number of pulls of arm a at the beginning of phase k<sub>n,a</sub></td></tr><tr><td>μ̃<sub>n,a</sub></td><td>R</td><td>Private estimator of the empirical mean of arm a at the beginning of phase k<sub>n,a</sub></td></tr><tr><td>L<sub>n,a</sub></td><td>N</td><td>Counts of B<sub>t</sub> = a before time n</td></tr><tr><td>N<sup>a</sup><sub>n,a</sub></td><td>N</td><td>Counts of (B<sub>t</sub>, a<sub>t</sub>) = (a, a) before time n</td></tr><tr><td>β</td><td>(0, 1)</td><td>Fixed proportion</td></tr></tbody></table>

# C Related Work and Extended Discussion

We provide a more detailed literature review in Appendix C.1, and an extended discussion in Appendix C.2.

## C.1 Related Work

**Structured Bandits.** While we consider unstructured bandits [Auer et al., 2002], numerous structural assumptions have been studied: linear bandits [Soare et al., 2014], generalized linear bandits [Filippi et al., 2010] such as logistic bandits [Jun et al., 2021], combinatorial bandits [Chen et al., 2013], sparse bandits [Jamieson et al., 2015], spectral bandits [Kocák and Garivier, 2021], unimodal bandits [Combes and Proutière, 2014], Lipschitz [Magureanu et al., 2014], partial monitoring [Audibert and Bubeck, 2010a], etc. Coping for the structural assumption while preserving ε-global DP is an interesting direction for future works.

**Pure Exploration Problems.** While we consider only BAI [Even-Dar et al., 2002], other pure exploration problems have been studied in the literature: ε-BAI [Mannor and Tsitsiklis, 2004], thresholding bandits [Carpentier and Locatelli, 2016], Top-k identification [Katz-Samuels and Scott, 2019], Pareto set identification [Auer et al., 2016], best partition identification [Chen et al., 2017], etc. Extending our ε-global DP results to answer these identification problems is an interesting research direction.

**Performance Metrics.** In pure exploration problems, the two major theoretical frameworks are the fixed-confidence setting [Even-Dar et al., 2006; Jamieson and Nowak, 2014; Garivier and Kaufmann, 2016], which is the focus of this paper, and the fixed-budget setting [Audibert et al., 2010; Gabillon et al., 2012]. In the fixed-budget setting, the objective is to minimize the probability of misidentifying a correct answer with a fixed number of samples T. Recent works have also considered the anytime setting, in which the agent aims at achieving a low probability of error at any deterministic time [Zhao et al., 2023; Jourdan et al., 2024]. Extending our findings to support ε-global DP in the fixed-budget or the anytime setting is an interesting direction for future works, see e.g., Chen et al. [2024].
**DP in Bandits.** DP has been studied for multi-armed bandits under different bandit settings: finite-armed stochastic [Mishra and Thakurta, 2015; Sajed and Sheffet, 2019; Zheng et al., 2020; Hu et al., 2021; Azize and Basu, 2022; Hu and Hegde, 2022; Azize and Basu, 2024; Wang and Zhu, 2024; Hu et al., 2025], adversarial [Thakurta and Smith, 2013; Agarwal and Singh, 2017; Tossou and Dimitrakakis, 2017], linear [Hanna et al., 2024; Li et al., 2022; Azize and Basu, 2024], contextual linear [Shariff and Sheffet, 2018; Neel and Roth, 2018; Zheng et al., 2020; Azize and Basu, 2024], and kernel bandits [Pavlovic et al., 2025], among others. Most of these works were for regret minimisation, but the problem has also been explored for best-arm identification, with fixed confidence [Azize et al., 2023, 2024] and fixed budget [Chen et al., 2024]. The problem has also been studied under three different DP trust models: (a) global DP where the users trust the centralised decision maker [Mishra and Thakurta, 2015; Shariff and Sheffet, 2018; Sajed and Sheffet, 2019; Azize and Basu, 2022; Hu and Hegde, 2022], (b) local DP where each user deploys a local perturbation mechanism to send a "noisy" version of the rewards to the policy [Basu et al., 2019; Zheng et al., 2020; Han et al., 2021], and (c) shuffle DP where users still feed their data to a local perturbation, but now they trust an intermediary to apply a uniformly random permutation on all users' data before sending to the central servers [Tenenbaum et al., 2021; Garcelon et al., 2022; Chowdhury and Zhou, 2022].

In the first papers on DP for bandits, the tree-based mechanism [Dwork et al., 2010; Chan et al., 2011] was used to compute the sum of rewards privately. However, this mechanism was proven to be sub-optimal, matching the lower bounds up to logarithmic factors. Then, forgetting was first proposed by Sajed and Sheffet [2019] to get rid of the tree-based mechanism, then adapted to UCB in [Hu et al., 2021; Azize and Basu, 2022]. Finally, if the KL is the divergence that controls the complexity of bandits without privacy [Lai and Robbins, 1985; Garivier and Kaufmann, 2016], then Azize and Basu [2022] were the first to show that the TV controls the complexity of private bandits, in the high privacy regime.

In this paper, we focus on $\epsilon$-pure DP, under a global trust model, in stochastic finite-armed bandits, for best arm identification under fixed confidence.

**Gap in the Literature.** This problem setting is first studied by Azize et al. [2023], who proposed the first problem-dependent sample complexity lower bound, and introduced AdaP-TT, an $\epsilon$-global DP version of the Top Algorithm. However, the sample complexity upper bound of AdaP-TT only matches the lower bound in the high privacy regime $\epsilon \to 0$, and for instances where the means have similar order (see Condition 1 in [Azize et al., 2023] in the discussion after Theorem 5 in [Azize et al., 2023]).

Azize et al. [2024] proposes AdaP-TT\*, an improved version of AdaP-TT. The improvement is achieved by using a transport inspired by the sample complexity lower bound from [Azize et al., 2023]. Using the new transport, AdaP-TT\* gets rid of Condition 1 needed by AdaP-TT, and achieves the high privacy lower bound for all instances up to a multiplicative factor 48.

However, both AdaP-TT and AdaP-TT\* do not match the lower bound, beyond the high privacy regime, i.e. for both the low privacy regime and transitional regimes.

## C.2 Extended Discussions

**Limitations of Theorem 7** Using adaptive targets $\beta_n(B_n, C_n)$ in DP-TT could replace $T_{\epsilon,\beta}^*(\nu)$ by $T_{\epsilon}^*(\nu)$, which is the optimal scaling asymptotically (Theorem 2). While we propose two adaptive choices of target based on IDS [You et al., 2023] or BOLD [Bandyopadhyay et al., 2024] (Appendix I), we leave their analysis for future work. Based on finer concentration results, the stopping threshold could scale asymptotically as $\log(1/\delta)$ instead of $2\log(1/\delta)$, hence improving by a factor 2. The assumption that the means are distinct is used to prove sufficient exploration; it can be removed by using forced exploration or a fine-grained analysis [Jourdan and Degenne, 2024; Jourdan et al., 2024]. Provided these improvements are proven, the multiplicative factor would be reduced to $1 + \eta$, where $\eta$ is the parameter that controls the geometrically increasing phases. While it improves the asymptotic upper bound, choosing $\eta$ too close to 0 negatively impacts the performance of DP-TT, due to the dependency in $O(1/\log(1+\eta))$ of the stopping threshold.

**Beyond Bernoulli Distributions** The non-asymptotic lower bound on the expected sample complexity (Theorem 2) holds for any class of distributions $\mathcal{F}$, and thus is already true beyond Bernoulli (e.g. exponential families, sub-Gaussians, etc). However, by going beyond Bernoulli, $d_\epsilon$ might not
admit a closed-form solution, e.g., the TV between Gaussian distributions has no simple formula. We conjecture that most regularity properties used to derive Theorem 4, and needed for the upper bound proofs, also hold for other classes of distributions. From a theoretical perspective, this might render the proof of the sufficient regularity properties more challenging. From a practical perspective, this increases the computational cost of the stopping rule and the challenger arm, as they require computing an empirical transportation cost based on the $d_e$ divergence. Finally, since the objective function inside the $d_e$ is continuous and convex over a compact interval, using off-the-shelf convex optimisation solvers to compute $d_e$ is still straightforward.

Our privacy analysis (Lemma 8) holds for any distribution with support in $[0, 1]$, and thus is already true beyond Bernoullis. It is straightforward to extend this to any distribution with a support in $[a, b]$, by multiplying the noise terms by the range $b-a$. Also, all prior works in bandits with DP are either for Bernoulli or bounded distributions, for the simple reason that this assumption makes estimating the empirical mean privately using the Laplace mechanism straightforward, as the sensitivity is controlled. This helps focus on the more interesting tradeoffs between DP, exploration and exploitation, without any additional technical overheads that may be introduced by estimating privately the mean of unbounded distributions.

The concentration results (Theorem 6) used to derive a stopping threshold ensuring $\delta$-correctness are highly specific to Bernoulli distributions. However, the proof builds on fine-grained tail bounds of the sum of two independent random variables, i.e., we bound those probabilities by the maximal product between their respective survival functions (Lemma 10). Therefore, the technical tools used for this intermediate result can be also used to study other one-parameter exponential families, e.g., Gaussian observation, with other noise mechanisms, e.g., Gaussian noise.

The proof of Theorem 7 (Appendix H) builds on the unified analysis of the Top Two algorithm Jourdan et al. [2022], coping with many classes of distributions, e.g., one-parameter exponential families and non-parametric bounded distributions. It relies heavily on the derived regularity properties (Appendix G) for the signed divergences, transportation costs, characteristic times, and optimal allocations. Based on the non-private BAI literature, we conjecture that most regularity properties used to derive Theorem 7 also hold for other classes of distributions. Due to the lack of explicit formulae, the proofs are challenging. The DP-TT algorithm becomes computationally costly due to the intertwined optimisation procedure when computing the transportation costs numerically.

**Beyond BAI** The technical arguments used in the proof of Theorem 2 allow obtaining a similar lower bound for (i) one-parameter exponential families, e.g., Gaussian, (ii) pure exploration problems with a unique correct answer, e.g., top-$m$ best arm identification, and (iii) structured instances without arm correlation, e.g., unimodal bandits. This is straightforwardly done by adapting the definition of $\text{Alt}(\nu)$, $a^*(\nu)$, and $\mathcal{F}$ in Eq. (2). For settings that do not fall into the above three categories, the characteristic time requires more subtle modifications; yet our intermediate technical results can still be used. Based on the non-private fixed-confidence literature, we conjecture the changes of characteristic times described below.

* For bounded distribution (non-parametric) or Gaussian with unknown variance (two-parameters exponential family), the KL should be replaced by an infimum over KL Agrawal et al. [2020]; Jourdan et al. [2023]. The plurality of distributions having the same mean implies the existence of a distribution that is the most confusing given a specific constraint on the mean, captured by the Kinf.

* For $\gamma$-Best Arm Identification (multiple correct answers), an outer maximization over all the correct answers should be added Degenne and Koolen [2019]. The plurality of correct answers implies the existence of a correct answer that is the easiest to verify.

* For linear bandits (correlated means), the inf in the definition of $d_e$ per-arm should be replaced by a joint infimum over all the arms and moved outside the sum over arms Degenne et al. [2020a].

**Beyond $\epsilon$-DP** Our lower bound technique (Theorem 2) can be seen as a generalisation of the packing argument, and thus depends on the group privacy property. Specifically, in Appendix D, just before Eq. (11), we used the group privacy of $\epsilon$-DP to bound $\text{KL}(M_D, M_{D'}) \le \epsilon \text{dham}(D, D')$.
* For $\rho$-zCDP, there is a similar group privacy property that can directly be plugged here, stating that $KL(M_D, M_{D'}) \le \rho d\text{ham}(D, D')^2$. This means that for $\rho$-zCDP, $\epsilon \times \text{dham}$ is replaced by $\rho \times \text{dham}^2$ in the fundamental optimal transport inequality of Eq. (11). We leave solving tightly this new optimal transport for future work.

* For $(\epsilon, \delta)$-DP, the group privacy property is not tight. This is a classic issue in $(\epsilon, \delta)$-DP lower bounds, where other techniques are used (e.g., fingerprinting). Adapting these techniques for bandits is an interesting open problem (even for bandits with regret minimisation).

It is straightforward to make DP-TT achieve either $\rho$-zCDP or $(\epsilon, \delta)$-DP, by replacing the Laplace mechanism with the Gaussian mechanism. To design a correct stopping rule with the Gaussian mechanism, it is possible to use the same fine-grained tail bounds of the sum of two independent random variables (Lemma 10) by only replacing the concentration of Laplace random variables with the concentration of Gaussian random variables. In the Top Two family of algorithms, an important design choice is the transportation cost, used for stopping and sampling the challenger. DP-TT uses a $d_\epsilon$ based transport, inspired by the lower bound of Theorem 2. Thus, to go beyond $\epsilon$-DP for algorithm design, it is important to derive a tight lower bound that suggests the use of a new transportation cost.

**Behavior with Near-optimal Arms** The unique best arm assumption is standard in the fixed-confidence BAI setting. Even in the non-private setting, this assumption is necessary to obtain a $\delta$-correct algorithm with finite expected stopping time, as the characteristic time becomes infinite otherwise. In the private setting, this phenomenon persists as can be seen by the lower bound in Eq. (5), i.e., $T_\epsilon^*(\nu) \to +\infty$ when $\Delta_{\epsilon,a^*} \to 0$. In near-tie scenarios, DP-TT will perform as badly as any other $\delta$-correct and $\epsilon$-global DP algorithms due to the fundamental lower bound. Empirically, this will be reflected by empirical transportation costs that are too small for the stopping condition to be met. In applications where the near-tie scenario is common, practitioners consider $\gamma$-Best Arm Identification, i.e., identify an arm that is $\gamma$-close to the best arm. For the non-private fixed-confidence $\gamma$-BAI setting, we refer to Jourdan et al. [2024] for references and guarantees satisfied by Top Two algorithms. To tackle $\gamma$-BAI, DP-TT should be modified by using the appropriate transportation costs in both the stopping rule and the definition of the challenger, i.e., $W_{\epsilon,\gamma,a,b}$ instead of $W_{\epsilon,a,b}$.

**Implications of Not Forgetting** DP-TT has the same memory complexity as the forgetting algorithms. The reason is that DP-TT only needs to store one accumulated noisy sum of rewards across phases, while the forgetting ones store the noisy sum of rewards of only the last phase. For privacy considerations, under our threat model where the adversary only observes the output of the algorithm (sequence of actions, final recommendation and stopping time), both forgetting and non-forgetting algorithms provide the same DP guarantees thanks to post-processing.

One can imagine other threat models where forgetting the rewards provides better privacy guarantees. One possible example of this is the pan-private threat model Dwork et al. [2010], where the adversary can also intrude into the internal states of the algorithm during its execution. In this threat model, if an adversary observes the internal states of the execution of DP-TT at some phase $\ell > 1$, they can see the full sum of rewards and maybe infer the membership of, say, the first user (up to tradeoffs guaranteed by the $\epsilon$-DP constraint, since the sum is noisy). However, for the forgetting algorithms, if the adversary observes the internal states of the execution of forgetting algorithms at some phase $\ell > 1$, the adversary can infer nothing about the reward of the first patient, since its reward has been deleted completely.

## D Lower Bound

Let $\mathcal{M}: \mathcal{X}^n \to \mathcal{O}$ be an $\epsilon$-DP mechanism. For $D \in \mathcal{X}^n$ an input dataset, we denote by $M_D$ the distribution over outputs, when the input is $D$, and $M_D(E)$ the probability of observing output $E$ when the input is $D$.

Let $\mathbb{P}$ and $\mathbb{Q}$ be two data-generating distributions over $\mathcal{X}^n$. We denote by $M_{\mathbb{P},\mathcal{M}}$ the marginal over outputs of the mechanism $\mathcal{M}$ when the input dataset is generated through $\mathbb{P}$, i.e.

$$ M_{\mathbb{P},\mathcal{M}}(A) := \int_{D \in \mathcal{X}^n} M_D(A) \, d\mathbb{P}(D), \qquad (9) $$

for any event $A$ in the output space. We define similarly $M_{\mathbb{Q},\mathcal{M}}$ the marginal over outputs of the mechanism $\mathcal{M}$ when the input dataset is generated through $\mathbb{Q}$.
The main question is to control the divergence KL ($\mathbb{M}_{\mathbb{P},\mathcal{M}} \parallel \mathbb{M}_{\mathbb{Q},\mathcal{M}}$) when the mechanism $\mathcal{M}$ satisfies DP. In general, for any mechanism $\mathcal{M}$, the data-processing inequality provides the following bound

$$ \mathrm{KL}(\mathbb{M}_{\mathbb{P},\mathcal{M}} \parallel \mathbb{M}_{\mathbb{Q},\mathcal{M}}) \leq \mathrm{KL}(\mathbb{P} \parallel \mathbb{Q}). \quad (10) $$

Now, for $\epsilon$-DP mechanisms, we want to translate the DP constraint to a tight bound on the divergence KL ($\mathbb{M}_{\mathbb{P},\mathcal{M}} \parallel \mathbb{M}_{\mathbb{Q},\mathcal{M}}$). To do so, let $\mathbb{L}$ be any other distribution on $\mathcal{X}^n$. Let $\mathbb{C}_{\mathbb{P},\mathbb{L}}$ be a coupling of $(\mathbb{P}, \mathbb{L})$, i.e., the marginals of $\mathbb{C}_{\mathbb{P},\mathbb{L}}$ are $\mathbb{P}$ and $\mathbb{L}$. We can now rewrite our the marginals using the definition of couplings. For $\mathbb{M}_{\mathbb{P},\mathcal{M}}$, we have

$$ \mathbb{M}_{\mathbb{P},\mathcal{M}}(A) := \int_{D \in \mathcal{X}^n} \mathcal{M}_D(A) \, d\mathbb{P}(D) = \int_{D, D' \in \mathcal{X}^n} \mathcal{M}_D(A) \, d\mathbb{C}_{\mathbb{P},\mathbb{L}}(D, D'), $$

and for $\mathbb{Q}$ we get

$$ \begin{aligned} \mathbb{M}_{\mathbb{Q},\mathcal{M}}(A) &:= \int_{D' \in \mathcal{X}^n} \mathcal{M}_{D'}(A) \, d\mathbb{Q}(D') = \int_{D' \in \mathcal{X}^n} \mathcal{M}_{D'}(A) \frac{d\mathbb{Q}(D')}{d\mathbb{L}(D')} \, d\mathbb{L}(D') \\ &= \int_{D, D' \in \mathcal{X}^n} \mathcal{M}_{D'}(A) \frac{d\mathbb{Q}(D')}{d\mathbb{L}(D')} \, d\mathbb{C}_{\mathbb{P},\mathbb{L}}(D, D'). \end{aligned} $$

Using the data-processing inequality, we get

$$ \begin{aligned} \mathrm{KL}(\mathbb{M}_{\mathbb{P},\mathcal{M}} \parallel \mathbb{M}_{\mathbb{Q},\mathcal{M}}) &\leq \int_{D, D' \in \mathcal{X}^n} \int_{o \in \mathcal{O}} \log \left( \frac{\mathcal{M}_D(o)}{\mathcal{M}_{D'}(o) \frac{d\mathbb{Q}(D')}{d\mathbb{L}(D')}} \right) \mathcal{M}_D(o) \, do \, d\mathbb{C}_{\mathbb{P},\mathbb{L}}(D, D') \\ &= \int_{D, D' \in \mathcal{X}^n} \left( \mathrm{KL}(\mathcal{M}_D \parallel \mathcal{M}_{D'}) + \log \left( \frac{d\mathbb{L}(D')}{d\mathbb{Q}(D')} \right) \right) \, d\mathbb{C}_{\mathbb{P},\mathbb{L}}(D, D') \\ &= \mathbb{E}_{D, D' \sim \mathbb{C}_{\mathbb{P},\mathbb{L}}} [\mathrm{KL}(\mathcal{M}_D \parallel \mathcal{M}_{D'})] + \mathrm{KL}(\mathbb{L} \parallel \mathbb{Q}). \end{aligned} $$

Since this is true for any coupling $\mathbb{C}_{\mathbb{P},\mathbb{L}}$ and any distribution $\mathbb{L}$, we get the final bound

$$ \mathrm{KL}(\mathbb{M}_{\mathbb{P},\mathcal{M}} \parallel \mathbb{M}_{\mathbb{Q},\mathcal{M}}) \leq \inf_{\mathbb{L} \in \mathcal{P}(\mathcal{X}^n)} \left\{ \inf_{\mathbb{C}_{\mathbb{P},\mathbb{L}} \in \mathcal{C}(\mathbb{P},\mathbb{L})} \left\{ \mathbb{E}_{D, D' \sim \mathbb{C}_{\mathbb{P},\mathbb{L}}} [\mathrm{KL}(\mathcal{M}_D \parallel \mathcal{M}_{D'})] \right\} + \mathrm{KL}(\mathbb{L} \parallel \mathbb{Q}) \right\} $$

where $\mathcal{P}(\mathcal{X}^n)$ is the set of all distributions over $\mathcal{X}^n$ and $\mathcal{C}(\mathbb{P}, \mathbb{L})$ is the set of all couplings between $\mathbb{P}$ and $\mathbb{L}$. Using that the $\mathcal{M}$ is $\epsilon$-DP, we can use the simple bound $\mathrm{KL}(\mathcal{M}_D \parallel \mathcal{M}_{D'}) \leq \epsilon d_{\mathrm{Ham}}(D, D')$ which gives

$$ \mathrm{KL}(\mathbb{M}_{\mathbb{P},\mathcal{M}} \parallel \mathbb{M}_{\mathbb{Q},\mathcal{M}}) \leq \inf_{\mathbb{L} \in \mathcal{P}(\mathcal{X}^n)} \left\{ \epsilon \inf_{\mathbb{C}_{\mathbb{P},\mathbb{L}} \in \mathcal{C}(\mathbb{P},\mathbb{L})} \left\{ \mathbb{E}_{D, D' \sim \mathbb{C}_{\mathbb{P},\mathbb{L}}} [d_{\mathrm{Ham}}(D, D')] \right\} + \mathrm{KL}(\mathbb{L} \parallel \mathbb{Q}) \right\}. \quad (11) $$

## D.1 Product Distributions

Suppose that $\mathbb{P} := \bigotimes_{i=1}^n \mathbb{P}_i$ and $\mathbb{Q} := \bigotimes_{i=1}^n \mathbb{Q}_i$ are product distributions. Consider the subset of product distributions $\mathbb{L} := \bigotimes_{i=1}^n \mathbb{L}_i$, and the maximal coupling $\mathbb{C}_{\infty}(\mathbb{P}, \mathbb{L}) := \prod_{i=1}^n \mathbb{C}_{\infty}(\mathbb{P}_i, \mathbb{L}_i)$. Plugging these in Equation (11), we get

$$ \begin{aligned} \mathrm{KL}(\mathbb{M}_{\mathbb{P},\mathcal{M}} \parallel \mathbb{M}_{\mathbb{Q},\mathcal{M}}) &\leq \inf_{\mathbb{L}_1, \dots, \mathbb{L}_n} \left\{ \epsilon \sum_{i=1}^n \mathbb{E}_{D_i, D_i' \sim \mathbb{C}_{\infty}(\mathbb{P}_i, \mathbb{L}_i)} [\mathbb{1}\{D_i \neq D_i'\}] + \sum_{i=1}^n \mathrm{KL}(\mathbb{L}_i \parallel \mathbb{Q}_i) \right\} \\ &= \inf_{\mathbb{L}_1, \dots, \mathbb{L}_n} \left\{ \sum_{i=1}^n (\epsilon \mathrm{TV}(\mathbb{P}_i \parallel \mathbb{L}_i) + \mathrm{KL}(\mathbb{L}_i \parallel \mathbb{Q}_i)) \right\} \\ &= \sum_{i=1}^n \inf_{\mathbb{L}_i \in \mathcal{P}(\mathcal{X})} \{\epsilon \mathrm{TV}(\mathbb{P}_i \parallel \mathbb{L}_i) + \mathrm{KL}(\mathbb{L}_i \parallel \mathbb{Q}_i)\} = \sum_{i=1}^n d_{\epsilon}(\mathbb{P}_i, \mathbb{Q}_i), \end{aligned} $$

where

$$ d_{\epsilon}(\mathbb{P}, \mathbb{Q}) := \inf_{\mathbb{L} \in \mathcal{P}(\mathcal{X})} \{\epsilon \mathrm{TV}(\mathbb{P} \parallel \mathbb{L}) + \mathrm{KL}(\mathbb{L} \parallel \mathbb{Q})\}. \quad (12) $$
**Algorithm 2** Bandit interaction between a policy and an environment

1: **Input:** A policy $\pi$ and an environment $\nu \triangleq (P_a : a \in [K])$

2: **for** $t = 1, \dots, \text{do}$

3: The policy samples an action $a_t \sim \pi_t(\cdot | a_1, r_1, \dots, a_{t-1}, r_{t-1})$

4: The policy observes a reward $r_t \sim P_{a_t}$

5: **end for**

6: **if** Regret minimisation **then**

7: The interaction ends after $T$ steps

8: **else** FC-BAI

9: The policy decides to stop the interaction at step $\tau_{\epsilon, \delta}$ and recommends the final guess $\hat{a}$

10: **end if**

## D.2 Sequential KL decomposition for bandits under DP

In this section, we adapt the techniques from product distributions to bandit marginals.

First, we introduce the bandit canonical model.

**The bandit canonical model.** A stochastic bandit (or environment) is a collection of distributions $\nu \triangleq (P_a : a \in [K])$, where $[K]$ is the set of available $K$ actions. The learner and the environment interact sequentially over $T$ rounds. In each round $t \in 1, \dots, T$, the learner chooses an action $a_t \in [K]$, which is fed to the environment. The environment then samples a reward $r_t \in \mathbb{R}$ from distribution $P_{a_t}$ and reveals $r_t$ to the learner. The interaction between the learner (or policy) and environment induces a probability measure on the sequence of outcomes $H_T \triangleq (a_1, r_1, a_2, r_2, \dots, a_T, r_T)$. In the following, we construct the probability space that carries these random variables.

Let $T \in \mathbb{N}^*$ be the horizon. Let $\nu = (P_a : a \in [K])$ a bandit instance with $K \in \mathbb{N}^*$ finite arms, and each $P_a$ is a probability measure on $(\mathbb{R}, \mathcal{B}(\mathbb{R}))$ with $\mathcal{B}$ being the Borel set. For each $t \in [T]$, let $\Omega_t = ([K] \times \mathbb{R})^t \subset \mathbb{R}^{2t}$ and $\mathcal{F}_t = \mathcal{B}(\Omega_t)$. We first formalise the definition of a policy.

**Definition 2 (The policy).** A policy $\pi$ is a sequence $(\pi_t)_{t=1}^T$, where $\pi_t$ is a probability kernel from $(\Omega_t, \mathcal{F}_t)$ to $([K], 2^{[K]})$. Since $[K]$ is discrete, we adopt the convention that for $a \in [K]$,

$$ \pi_t(a | a_1, r_1, \dots, a_{t-1}, r_{t-1}) = \pi_t(\{a\} | a_1, r_1, \dots, a_{t-1}, r_{t-1}) $$

We want to define a probability measure on $(\Omega_T, \mathcal{F}_T)$ that respects our understanding of the sequential nature of the interaction between the learner and a stationary stochastic bandit. Specifically, the sequence of outcomes should satisfy the following two assumptions:

(a) The conditional distribution of action $a_t$ given $a_1, r_1, \dots, a_{t-1}, r_{t-1}$ is $\pi(a_t | H_{t-1})$ almost surely.

(b) The conditional distribution of reward $r_t$ given $a_1, r_1, \dots, a_{t-1}, r_{t-1}, a_t$ is $P_{a_t}$ almost surely.

The probability measure on $(\Omega_T, \mathcal{F}_T)$ depends on both the environment $\nu$ and the policy $\pi$. To construct this probability, let $\lambda$ be a $\sigma$-finite measure on $(\mathbb{R}, \mathcal{B}(\mathbb{R}))$ for which $P_a$ is absolutely continuous with respect to $\lambda$ for all $a \in [K]$. Let $p_a = dP_a/d\lambda$ be the Radon-Nikodym derivative of $P_a$ with respect to $\lambda$. Letting $\rho$ be the counting measure with $\rho(B) = |B|$, the density $p_{\nu\pi} : \Omega_T \to \mathbb{R}$ can now be defined with respect to the product measure $(\rho \times \lambda)^T$ by

$$ p_{\nu\pi}(a_1, r_1, \dots, a_T, r_T) \triangleq \prod_{t=1}^{T} \pi_t(a_t | a_1, r_1, \dots, a_{t-1}, r_{t-1}) p_{a_t}(r_t) $$

and $\mathcal{P}_{\nu\pi}$ is defined as

$$ \mathbb{P}_{\nu\pi}(B) \triangleq \int_{B} p_{\nu\pi}(\omega)(\rho \times \lambda)^T(\mathrm{d}\omega) \quad \text{forall } B \in \mathcal{F}_T $$

Hence $(\Omega_T, \mathcal{F}_T, \mathbb{P}_{\nu\pi})$ is a probability space over histories induced by the interaction between $\pi$ and $\nu$. We define also a marginal distribution over the sequence of actions by

$$ m_{\nu\pi}(a_1, \dots, a_T) \triangleq \int_{r_1, \dots, r_T} p_{\nu\pi}(a_1, r_1, \dots, a_T, r_T) \mathrm{d}r_1 \dots \mathrm{d}r_T, $$
and for all $C \in \mathcal{P}([K]^T)$,

$$ \mathbb{M}_{\nu\pi}(C) \triangleq \sum_{(a_1, \dots, a_T) \in C} m_{\nu\pi}(a_1, a_2, \dots, a_T). $$

Finally, $([K]^T, \mathcal{P}([K]^T), \mathbb{M}_{\nu\pi})$ is a probability space over sequence of actions produced when $\pi$ interacts with $\nu$ for $T$ time-steps.

**The KL upper bound.** Now, we adapt the techniques for the bandit marginals. Let $\nu = \{P_a, a \in [K]\}$ and $\nu' = \{P'_a, a \in [K]\}$ be two bandit instances in $\mathcal{F}^K$. We recall that, when the policy $\pi$ interacts with the bandit instance $\nu$, it induces a marginal distribution $\mathbb{M}_{\nu\pi}$ over the sequence of actions. We define $\mathbb{M}_{\nu'\pi}$ similarly.

The goal is to upper bound the quantity KL $(\mathbb{M}_{\nu\pi} \| \mathbb{M}_{\nu'\pi})$. The marginals $\mathbb{M}_{\nu\pi}$ and $\mathbb{M}_{\nu'\pi}$ in the sequential setting "look like" marginals generated by "product distributions". However, the hardness of the sequential setting lies in the fact that the data-generating distributions depend on the stochastic sequential actions chosen. Thus, the results of the previous section cannot be directly applied. To adapt the proof ideas of the previous section to the bandit case, we introduce the idea of a coupled bandit instance.

Let $\nu'' = \{P''_a : a \in [K]\}$ be any "intermediary" bandit instance from $\mathcal{F}^K$. Define $c_a$ as the maximal coupling between $P_a$ and $P''_a$, i.e., $c_a := \mathbb{C}_\infty(P_a, P''_a)$. Fix a policy $\pi = \{\pi_t\}_{t=1}^T$.

Here, we build a coupled environment $\gamma$ of $\nu$ and $\nu''$. The policy $\pi$ interacts with the coupled environment $\gamma$ up to a given time horizon $T$ to produce an augmented history $\{(a_t, r_t, r''_t)\}_{t=1}^T$. The iterative steps of this interaction process are:

1. The probability of choosing an action $a_t = a$ at time $t$ is dictated only by the policy $\pi_t$ and $a_1, r_1, a_2, r_2, \dots, a_{t-1}, r_{t-1}$, i.e. the policy ignores $\{r''_s\}_{s=1}^{t-1}$.

2. The distribution of rewards $(r_t, r''_t)$ is $c_{a_t}$ and is conditionally independent of the previous observed history $\{(a_s, r_s, r''_s)\}_{t=1}^{t-1}$.

This interaction is similar to the interaction process of policy $\pi$ with the first bandit instance $\nu$, with the addition of sampling an extra $r''_t$ from the coupling of $P_{a_t}$ and $P''_{a_t}$.

The distribution of the augmented history induced by the interaction of $\pi$ and the coupled environment can be defined as

$$ p_{\gamma\pi}(a_1, r_1, r_1'' \dots, a_T, r_T, r_T'') := \prod_{t=1}^{T} \pi_t(a_t \mid a_1, r_1, \dots, a_{t-1}, r_{t-1}) c_{a_t}(r_t, r_t'') . $$

To simplify the notation, let $\mathbf{a} := (a_1, \dots, a_T)$, $\mathbf{r} := (r_1, \dots, r_T)$, $\mathbf{r}' := (r'_1, \dots, r'_T)$ and $\mathbf{r}'' := (r''_1, \dots, r''_T)$. Also, let $c_{\mathbf{a}}(\mathbf{r}, \mathbf{r}'') := \prod_{t=1}^T c_{a_t}(r_t, r''_t)$ and $\pi(\mathbf{a} \mid \mathbf{r}) := \prod_{t=1}^T \pi_t(a_t \mid a_1, r_1, \dots, a_{t-1}, r_{t-1})$. We put $\mathbf{h} := (\mathbf{a}, \mathbf{r}, \mathbf{r}'')$. With the new notation

$$ p_{\gamma\pi}(\mathbf{a}, \mathbf{r}, \mathbf{r}'') := \pi(\mathbf{a} \mid \mathbf{r}) c_{\mathbf{a}}(\mathbf{r}, \mathbf{r}'') . $$

By the definition of the couplings, we have that $m_{\nu\pi}$ is the marginal of $p_{\gamma\pi}$ when integrated over $(\mathbf{r}, \mathbf{r}'')$, i.e.,

$$ m_{\nu\pi}(\mathbf{a}) = \int_{\mathbf{r}, \mathbf{r}''} p_{\gamma\pi}(\mathbf{a}, \mathbf{r}, \mathbf{r}'') \mathrm{d}\mathbf{r} \mathrm{d}\mathbf{r}'' . $$

Now, we define a new joint distribution $q_{\gamma\pi}$, inspired by the techniques used for product distributions:

$$ q_{\gamma\pi}(\mathbf{a}, \mathbf{r}, \mathbf{r}'') := \pi(\mathbf{a} \mid \mathbf{r}'') \frac{p'_{\mathbf{a}}(\mathbf{r}'')}{p''_{\mathbf{a}}(\mathbf{r}'')} c_{\mathbf{a}}(\mathbf{r}, \mathbf{r}'') , $$

where $p'_{\mathbf{a}}(\mathbf{r}'') := \prod_{t=1}^T p'_{a_t}(r''_t)$, and similarly, $p''_{\mathbf{a}}(\mathbf{r}'') := \prod_{t=1}^T p''_{a_t}(r''_t)$.

First, observe that it is indeed a valid joint distribution, i.e.

$$ \sum_{\mathbf{a}} \int_{\mathbf{r}, \mathbf{r}''} q_{\gamma\pi}(\mathbf{a}, \mathbf{r}, \mathbf{r}'') \mathrm{d}\mathbf{r} \mathrm{d}\mathbf{r}'' = \sum_{\mathbf{a}} \int_{\mathbf{r}, \mathbf{r}''} \pi(\mathbf{a} \mid \mathbf{r}'') \frac{p'_{\mathbf{a}}(\mathbf{r}'')}{p''_{\mathbf{a}}(\mathbf{r}'')} c_{\mathbf{a}}(\mathbf{r}, \mathbf{r}'') \mathrm{d}\mathbf{r} \mathrm{d}\mathbf{r}'' $$
$$ = \sum_{\mathbf{a}} \int_{\mathbf{r}''} \pi(\mathbf{a} | \mathbf{r''}) p'_{\mathbf{a}}(\mathbf{r''}) \mathrm{d}\mathbf{r}'' = \int_{\mathbf{r}''} p'_{\mathbf{a}}(\mathbf{r''}) \mathrm{d}\mathbf{r}'' = 1, $$

and that $m_{\nu'\pi}$ is the marginal of $q_{\gamma\pi}$ when integrated over $(\mathbf{r}, \mathbf{r''})$, i.e.,

$$ \begin{aligned} \int_{\mathbf{r},\mathbf{r}''} q_{\gamma\pi}(\mathbf{a}, \mathbf{r}, \mathbf{r''}) \mathrm{d}\mathbf{r} \mathrm{d}\mathbf{r}'' &= \int_{\mathbf{r},\mathbf{r}''} \pi(\mathbf{a} | \mathbf{r''}) \frac{p'_{\mathbf{a}}(\mathbf{r''})}{p''_{\mathbf{a}}(\mathbf{r''})} c_{\mathbf{a}}(\mathbf{r}, \mathbf{r''}) \mathrm{d}\mathbf{r} \mathrm{d}\mathbf{r}'' \\ &= \int_{\mathbf{r}''} \pi(\mathbf{a} | \mathbf{r''}) p'_{\mathbf{a}}(\mathbf{r''}) \mathrm{d}\mathbf{r}'' = m_{\nu'\pi}(\mathbf{a}). \end{aligned} $$

Using the data-processing inequality, we get

$$ \mathrm{KL}(\mathbb{M}_{\nu\pi} \| \mathbb{M}_{\nu'\pi}) \le \mathrm{KL}(p_{\gamma\pi} \| q_{\gamma\pi}). \quad (13) $$

Now, we compute

$$ \begin{aligned} \mathrm{KL}(p_{\gamma\pi} \| q_{\gamma\pi}) &\stackrel{(a)}{=} \mathbb{E}_{\mathbf{h}:=\mathbf{(a,r,r'')} \sim p_{\gamma\pi}} \left[ \log \left( \frac{\pi(\mathbf{a} | \mathbf{r}) c_{\mathbf{a}}(\mathbf{r}, \mathbf{r''})}{\pi(\mathbf{a} | \mathbf{r''}) \frac{p'_{\mathbf{a}}(\mathbf{r''})}{p''_{\mathbf{a}}(\mathbf{r''})} c_{\mathbf{a}}(\mathbf{r}, \mathbf{r''})} \right) \right] \\ &\stackrel{(b)}{\le} \mathbb{E}_{\mathbf{h}:=\mathbf{(a,r,r'')} \sim p_{\gamma\pi}} \left[ \epsilon d_{\mathrm{Ham}}(\mathbf{r}, \mathbf{r''}) + \log \left( \frac{p''_{\mathbf{a}}(\mathbf{r''})}{p'_{\mathbf{a}}(\mathbf{r''})} \right) \right] \\ &\stackrel{(c)}{=} \sum_{t=1}^{T} \mathbb{E}_{\mathbf{h} \sim p_{\gamma\pi}} \left[ \epsilon \mathbf{1} \{r_t \ne r_t''\} + \log \left( \frac{p''_{a_t}(r_t'')}{p'_{a_t}(r_t'')} \right) \right] \\ &\stackrel{(d)}{=} \sum_{t=1}^{T} \mathbb{E}_{\mathbf{h} \sim p_{\gamma\pi}} \left[ \mathbb{E}_{\mathbf{h} \sim p_{\gamma\pi}} [\epsilon \mathbf{1} \{r_t \ne r_t''\} + \log \left( \frac{p''_{a_t}(r_t'')}{p'_{a_t}(r_t'')} \right) | a_t] \right] \\ &\stackrel{(e)}{=} \sum_{t=1}^{T} \mathbb{E}_{\mathbf{h} \sim p_{\gamma\pi}} \left[ \epsilon \mathrm{TV}(p_{a_t} \| p''_{a_t}) + \mathrm{KL}(p''_{a_t} \| p'_{a_t}) \right] \\ &\stackrel{(f)}{=} \mathbb{E}_{\nu\pi} \left[ \sum_{t=1}^{T} \epsilon \mathrm{TV}(p_{a_t} \| p''_{a_t}) + \mathrm{KL}(p''_{a_t} \| p'_{a_t}) \right]. \end{aligned} $$

where:

(a) by the definition of the KL

(b) the group privacy property, applied to the $\epsilon$-global DP policy, we have

$$ \pi(\mathbf{a} | \mathbf{r}) \le e^{\epsilon d_{\mathrm{Ham}}(\mathbf{r}, \mathbf{r''})} \pi(\mathbf{a} | \mathbf{r''}) $$

(c) by the definition of dham

(d) by the towering property of conditional expectations

(e) given $a_t$, we have $r_t \sim p_{a_t}$, $r'_t \sim p'_{a_t}$ and $r'' \sim p''_{a_t}$

(f) by linearity of the expectation, and the fact that the expression inside the expectation only depends on the actions $a_t$

Since this is true for any "intermediary" bandit instance $\nu'' \in \mathcal{F}^K$, we take $\nu''_\star$ to be the environment where the infinimum of the $d_\epsilon(P_a, P'_a)$ is attained for each arm $a \in [K]$. Specifically, let $\nu''_\star = (p^*_a, a \in [K])$ where

$$ p^*_a = \arg \min_{\mathcal{L} \in \mathcal{F}} \{ \epsilon \mathrm{TV}(p_a \| \mathcal{L}) + \mathrm{KL}(\mathcal{L} \| p'_a) \} $$

Plugging $\nu''_\star$ gives

$$ \mathrm{KL}(\mathbb{M}_{\nu\pi} \| \mathbb{M}_{\nu'\pi}) \le \mathrm{KL}_{\nu\pi} \left[ \sum_{t=1}^{T} d_{\epsilon}(p_{a_t}, p'_{a_t}) \right] \quad (14) $$
Let $N_{t,a} = \sum_{s<t} 1 \{a_s = a\}$ be the counts of arm $a$ before step $t$. Then, we can rewrite the bound as

$$ KL(M_{\nu\pi} \| M_{\nu'\pi}) \le \sum_{a=1}^{K} \mathbb{E}_{\nu\pi}[N_{T+1,a}]d_{\epsilon}(p_a, p'_a), \quad (15) $$

**Stopping time version of the KL decomposition for BAI under DP.** Let $\pi$ be an $\epsilon$-DP BAI strategy. Let $\nu$ and $\lambda$ be two bandit instances. Denote by $M_{\nu\pi}$ the marginal distribution of the output of the BAI strategy when $\pi$ interacts with $\nu$. By using Wald's lemma in the proof technique seen before for the canonical bandit setting under FC-BAI, we get that

$$ KL(M_{\nu\pi} \| M_{\lambda\pi}) \le \mathbb{E}_{\nu\pi} \left( \sum_{t=1}^{\tau_{\epsilon,\delta}} d_{\epsilon}(\nu_{a_t}, \lambda_{a_t}) \right) = \sum_{a=1}^{K} \mathbb{E}_{\nu\pi}[N_{\tau_{\epsilon,\delta}+1,a}]d_{\epsilon}(\nu_a, \lambda_a), \quad (16) $$

where $\tau$ is the stopping time.

### D.3 Sample Complexity Lower Bound Proof

**Theorem 2 (Sample complexity lower bound for BAI under $\epsilon$-DP).** Let $(\epsilon, \delta) \in \mathbb{R}_+^* \times (0, 1)$. For any algorithm $\pi$ that is $\delta$-correct and $\epsilon$-global DP on $\mathcal{F}^K$,

$$ \mathbb{E}_{\nu\pi}[\tau_{\epsilon,\delta}] \ge T_{\epsilon}^{*}(\nu) \log(1/(3\delta)) $$

for all $\nu \in \mathcal{F}^K$ with unique best arm. The inverse of the characteristic time $T_{\epsilon}^*(\nu)$ is defined as

$$ T_{\epsilon}^{*}(\nu)^{-1} := \sup_{w \in \Delta_K} \inf_{\kappa \in \text{Alt}(\nu)} \sum_{a=1}^{K} w_a d_{\epsilon}(\nu_a, \kappa_a), \quad (17) $$

$$ d_{\epsilon}(\nu_a, \kappa_a) := \inf_{\varphi_a \in \mathcal{F}} \{ \text{KL}(\varphi_a \| \kappa_a) + \epsilon \cdot \text{TV}(\nu_a \| \varphi_a) \}. \quad (18) $$

*Proof.* Let $\pi$ be an $\epsilon$-global DP $\delta$-correct BAI strategy. Let $\nu$ be a bandit instance and $\lambda \in \text{Alt}(\nu)$.

Let $M_{\nu\pi}$ denote the probability distribution of the output when the BAI strategy $\pi$ interacts with $\nu$. For any alternative instance $\lambda \in \text{Alt}(\nu)$, the data-processing inequality gives that

$$ KL(M_{\nu\pi} \| M_{\lambda,\pi}) \ge \text{kl}(M_{\nu\pi}(\tilde{a} = a^*(\nu)), M_{\lambda,\pi}(\tilde{a} = a^*(\nu))) \ge \text{kl}(1 - \delta, \delta), \quad (19) $$

where the second inequality is because $\pi$ is $\delta$-correct, i.e., $M_{\nu\pi}(\tilde{a} = a^*(\nu)) \ge 1 - \delta$ and $M_{\lambda,\pi}(\tilde{a} = a^*(\nu)) \le \delta$, and the monotonicity of the kl. Now, using the stopping time version of the KL decomposition for FC-BAI, we get that

$$ \text{kl}(1 - \delta, \delta) \le \text{KL}(M_{\nu,\pi} \| M_{\lambda,\pi}) \le \sum_{a=1}^{K} \mathbb{E}_{\nu\pi}[N_{\tau_{\epsilon,\delta}+1,a}]d_{\epsilon}(\nu_a, \lambda_a). $$

Since this is true for all $\lambda \in \text{Alt}(\nu)$, we get

$$ \begin{align*} \text{kl}(1 - \delta, \delta) &\le \inf_{\lambda \in \text{Alt}(\nu)} \sum_{a=1}^{K} \mathbb{E}_{\nu\pi}[N_{\tau_{\epsilon,\delta}+1,a}]d_{\epsilon}(\nu_a, \lambda_a) \\ &\stackrel{(a)}{=} \mathbb{E}[\tau_{\epsilon,\delta}] \inf_{\lambda \in \text{Alt}(\nu)} \sum_{a=1}^{K} \frac{\mathbb{E}[N_{\tau_{\epsilon,\delta}+1,a}]}{\mathbb{E}[\tau_{\epsilon,\delta}]} d_{\epsilon}(\nu_a, \lambda_a) \\ &\stackrel{(b)}{\le} \mathbb{E}[\tau_{\epsilon,\delta}] \left( \sup_{\omega \in \Delta_K} \inf_{\lambda \in \text{Alt}(\nu)} \sum_{a=1}^{K} \omega_a d_{\epsilon}(\nu_a, \lambda_a) \right). \end{align*} $$

(a) is due to the fact that $\mathbb{E}[\tau_{\epsilon,\delta}]$ does not depend on $\lambda$. (b) is obtained by noting that the vector $(\omega_a)_{a \in [K]} \triangleq \left( \frac{\mathbb{E}_{\nu,\pi}[N_{\tau_{\epsilon,\delta}+1,a}]}{\mathbb{E}_{\nu,\pi}[\tau_{\epsilon,\delta}]} \right)_{a \in [K]}$ belongs to the simplex $\Delta_K$. The theorem follows by noting that for $\delta \in (0, 1)$, $\text{kl}(1 - \delta, \delta) \ge \log(1/3\delta)$. $\square$
# E Privacy Analysis

In this section, we prove Lemma 5. First, we justify using a geometric grid for updating the means (Lemma 8). Second, we obtain Lemma 5 as a combination of Lemma 8 and the post-processing property of DP (Proposition 1).

## E.1 Releasing partial sums privately

First, the following lemma justifies the use of geometric grids, and provides that the price of getting rid of forgetting is summing the Laplace noise from previous phases.

**Lemma 8 (Privacy of our grid-based mean estimator).** Let $T \in \{1, \dots, \ell\}$, $\ell < T$ and $t_1, \dots, t_\ell, t_{\ell+1}$ be in $[1, T]$ such that $1 = t_1 < \dots < t_\ell < t_{\ell+1} - 1 = T$.

Let $\mathcal{M}$ be the following mechanism:

$$ \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_T \end{pmatrix} \xrightarrow{\mathcal{M}} \begin{pmatrix} (x_1 + \dots + x_{t_2-1}) + (Y_1) \\ (x_1 + \dots + x_{t_3-1}) + (Y_1 + Y_2) \\ \vdots \\ (x_1 + \dots + x_T) + (Y_1 + Y_2 + \dots + Y_{\ell-1}) \end{pmatrix} $$

where $(Y_1, \dots, Y_\ell) \sim \text{iid Lap}(1/\epsilon)$.

Then, for any $\{x_1, \dots, x_T\} \in [0, 1]^T$, $\mathcal{M}$ is $\epsilon$-DP.

*Proof.* First, consider the following mechanism, that only computes the partial sums:

$$ \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_T \end{pmatrix} \rightarrow \begin{pmatrix} x_1 + \cdots + x_{t_2-1} \\ x_{t_2} + \cdots + x_{t_3-1} \\ \vdots \\ x_{t_{\ell-1}} + \cdots + x_T \end{pmatrix}. $$

Because $x_t \in [0, 1]$, the sensitivity of each partial sum is 1. Since each partial sum is computed over non-overlapping sequences, combining the Laplace mechanism (Theorem 1) with the parallel composition property of DP (Lemma 3) gives that the following mechanism:

$$ \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_T \end{pmatrix} \xrightarrow{\mathcal{P}} \begin{pmatrix} x_1 + \cdots + x_{t_2-1} + Y_1 \\ x_{t_2} + \cdots + x_{t_3-1} + Y_2 \\ \vdots \\ x_{t_{\ell-1}} + \cdots + x_T + Y_{\ell-1} \end{pmatrix} $$

is $\epsilon$-DP, where $(Y_1, \dots, Y_{\ell-1}) \sim \text{iid Lap}(1/\epsilon)$.

Consider the post-processing function $f: (x_1, \dots, x_{\ell-1}) \rightarrow (x_1, x_1 + x_2, \dots, x_1 + x_2 + \dots + x_{\ell-1})$. Then, we have that $\mathcal{M} = f \circ \mathcal{P}$. So, by the post-processing property of DP, $\mathcal{M}$ is $\epsilon$-DP. $\square$

**Remark 1.** Mechanism $\mathcal{P}$, defined in the proof of Lemma 8, is the fundamental mechanism used by all previous bandit algorithms [Sajed and Sheffet, 2019; Azize and Basu, 2022; Hu and Hegde, 2022; Azize et al., 2024] to justify the use of forgetting. Our mechanism $\mathcal{M}$ is just summing over the partial sums computed on each phase, and thus the price of having sums of $x_i$ that start from the beginning (i.e. do not forget) is that we have to sum now the noise from all previous phases too.

## E.2 Proof of Lemma 5

We are now ready to prove Lemma 5, i.e. that any BAI algorithm based solely on using $GPE_\eta(\epsilon)$ to access observations is $\epsilon$-global DP on $[0, 1]$.

*Proof.* Let $\pi$ be a BAI algorithm using only $GPE_\eta(\epsilon)$ to access observations. Let $R = \{x_1, \dots\}$ and $R' = \{x'_1, \dots\}$ be two neighbouring sequences of private observations, i.e. there exists a $t^* \in \{1, \dots\}$ such that $x_t = x'_t$ for all $t \neq t^*$, i.e. that $R$ and $R'$ only differ at $t^*$.
Fix a stopping time, recommendation and sampled actions $(T+1, \tilde{a}, (a_1, \dots, a_T))$, we want to show that

$$ \mathrm{Pr}[\pi(R) = (T+1, \tilde{a}, (a_1, \dots, a_T))] \le e^{\epsilon} \mathrm{Pr}[\pi(R') = (T+1, \tilde{a}, (a_1, \dots, a_T))] . $$

**Step 1: Probability decompositions:** First, let us denote by $\tau$, $\tilde{A}$ and $A_1, \dots, A_\tau$ the random variables of stopping, recommendation and sampled actions, when $\pi$ interacts with $R$. Similarly, let $\tau'$, $\tilde{A}'$ and $A'_1, \dots, A'_\tau$ the random variables of stopping, recommendation and sampled actions, when $\pi$ interacts with $R'$.

We have

$$ \mathrm{Pr}[\pi(R) = (T+1, \tilde{a}, (a_1, \dots, a_T))] = \mathrm{Pr}[\tau = T+1, \tilde{A} = \tilde{a}, A_1 = a_1, \dots, A_T = a_T] $$

$$ \mathrm{Pr}[\pi(R') = (T+1, \tilde{a}, (a_1, \dots, a_T))] = \mathrm{Pr}[\tau' = T+1, \tilde{A}' = \tilde{a}, A'_1 = a_1, \dots, A'_T = a_T] $$

Since for all $t < t^*$, $x_t = x_t'$, the policy samples the same actions, up to step $t^*$, i.e.

$$ \mathrm{Pr}[A_1 = a_1, \dots, A_{t^*} = a_{t^*}] = \mathrm{Pr}[A'_1 = a_1, \dots, A'_{t^*} = a_{t^*}] $$

And thus

$$ \frac{\mathrm{Pr}[\pi(R) = (T+1, \tilde{a}, (a_1, \dots, a_T))]}{\mathrm{Pr}[\pi(R') = (T+1, \tilde{a}, (a_1, \dots, a_T))]} = \frac{\mathrm{Pr}[\tau = T+1, \tilde{A} = \tilde{a}, A_{t^*+1} = a_{t^*+1}, \dots, A_T = a_T \mid A_1 = a_1, \dots, A_{t^*} = a_{t^*}]}{\mathrm{Pr}[\tau' = T+1, \tilde{A}' = \tilde{a}, A'_{t^*+1} = a_{t^*+1}, \dots, A'_T = a_T \mid A'_1 = a_1, \dots, A'_{t^*} = a_{t^*}]} $$

Let us denote by $t_1, \dots, t_\ell$ the time step corresponding to the beginning of the phases when $\pi$ interacts with $R$, and $t'_1, \dots, t'_\ell$ the time step corresponding to the beginning of the phases $\pi$ interacts with $\mathbf{r}'$.

Also, let $t_{k_*}$ be the beginning of the phase for which $t^*$ belongs in $R$ phases. Similarly, let $t'_{k_*}$ be the beginning of the phase for which $t^*$ belongs in $R'$ phases.

Since the actions $a_1, \dots, a_T$ are fixed, and $r_t = r'_t$ for $t < t^*$, $t^*$ falls in the same phase under both $R$ and $R'$. Thus, $t_{k_*} = t'_{k_*}$ and $k_* = k'_*$.

**Step 2: Using the structure of GPE$_\eta(\epsilon)$**

Let $\tilde{S}_{k^*}^p = \sum_{s=t_{k^*}}^{t_{k^*+1}-1} x_s + Y_{k^*}$ be the noisy partial sum of observations collected at phase $k^*$ for $\mathbf{r}$, where $Y_{k^*} \sim \mathrm{Lap}(1/\epsilon)$. Similarly, let $\tilde{S}_{k^*}^{p'} = \sum_{s=t_{k^*}}^{t_{k^*+1}-1} x'_s + Y'_{k^*}$ be the noisy partial sum of observations collected at phase $k^*$ for $\mathbf{r}'$, where $Y'_{k^*} \sim \mathrm{Lap}(1/\epsilon)$. Using the structure of GPE$_\eta(\epsilon)$, we have that:

(a) If the value of the noisy partial sums at phase $k^*$ is exactly the same between the neighbouring $R$ and $R'$, then the BAI algorithm $\pi$ will sample the same sequence of actions from step $t^*$ onward, recommend the same final guess and stop at the same time, with the same probability under $R$ and $R'$. Thus, for any $s \in \mathbb{R}$:

$$ \mathrm{Pr}[\tau = T+1, \tilde{A} = \tilde{a}, A_{t^*+1} = a_{t^*+1}, \dots, A_T = a_T \mid A_1 = a_1, \dots, A_{t^*} = a_{t^*}, \tilde{S}_{k^*}^p = s] = \mathrm{Pr}[\tau' = T+1, \tilde{A}' = \tilde{a}, A'_{t^*+1} = a_{t^*+1}, \dots, A'_T = a_T \mid A'_1 = a_1, \dots, A'_{t^*} = a_{t^*}, \tilde{S}_{k^*}^{p'} = s] \quad (20) $$

This is due to the fact that, in $\mathrm{GPE}_\eta(\epsilon)$, the reward at step $t^*$ only affects the statistic $\tilde{S}_{k^*}^p$, and nothing else.

(b) Since rewards are $[0, 1]$, using the Laplace mechanism, we have that

$$ \mathrm{Pr}[\tilde{S}_{k^*}^p = s \mid A_1 = a_1, \dots, A_{t^*} = a_{t^*}] \le e^{\epsilon} \mathrm{Pr}(\tilde{S}_{k^*}^{p'} = s \mid A_1 = a_1, \dots, A'_{t^*} = a_{t^*}). \quad (21) $$

**Step 3: Combining Eq. 20 and Eq. 21, aka post-processing:**
We have

$$
\begin{align*}
& \Pr[\tau = T + 1, \tilde{A} = \tilde{a}, A_{t^*+1} = a_{t^*+1}, \dots, A_T = a_T \mid A_1 = a_1, \dots, A_{t^*} = a_{t^*}] \\
&= \int_{s \in \mathbb{R}} \Pr[\tau = T + 1, \tilde{A} = \tilde{a}, A_{t^*+1} = a_{t^*+1}, \dots, A_T = a_T \mid A_1 = a_1, \dots, A_{t^*} = a_{t^*}, \tilde{S}_{k^*}^p = s] \\
& \Pr[\tilde{S}_{k^*}^p = s \mid A_1 = a_1, \dots, A_{t^*} = a_{t^*}] \\
&\le \int_{s \in \mathbb{R}} e^\epsilon \Pr[\tau' = T + 1, \tilde{A}' = \tilde{a}, A'_{t^*+1} = a_{t^*+1}, \dots, A'_T = a_T \\
&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \mid A_1 = a_1, \dots, A'_{t^*} = a_{t^*}, \tilde{S}_{k^*}^{\tau'} = s] \\
& \Pr(\tilde{S}_{k^*}^{\tau'} = s \mid A_1 = a_1, \dots, A'_{t^*} = a_{t^*}) \\
&= e^\epsilon \Pr[\tau' = T + 1, \tilde{A}' = \tilde{a}, A'_{t^*+1} = a_{t^*+1}, \dots, A'_T = a_T \mid A'_1 = a_1, \dots, A'_{t^*} = a_{t^*}].
\end{align*}
$$

This concludes the proof:

$$
\frac{\Pr[\pi(R) = (T + 1, \tilde{a}, (a_1, \dots, a_T))]}{\Pr[\pi(R') = (T + 1, \tilde{a}, (a_1, \dots, a_T))]} \leq e^{\epsilon}.
$$

□

E.3 Recalling the post-processing and composition properties of DP

**Proposition 1 (Post-processing [Dwork and Roth, 2014]).** Let $\mathcal{M}$ be a mechanism and $f$ be an arbitrary randomised function defined on $\mathcal{M}$'s output. If $\mathcal{M}$ is $\epsilon$-DP, then $f \circ \mathcal{M}$ is $\epsilon$-DP.

The post-processing property ensures that any quantity constructed only from a private output is still private, with the same privacy budget. This is a consequence of the data processing inequality.

**Proposition 2 (Simple Composition).** Let $\mathcal{M}^1, \dots, \mathcal{M}^k$ be $k$ mechanisms. We define the mechanism

$$
\mathcal{G}: D \rightarrow \bigotimes_{i=1}^{k} \mathcal{M}_{D}^{i}
$$

as the k composition of the mechanisms $\mathcal{M}^1, \dots, \mathcal{M}^k$.

If each $\mathcal{M}^i$ is $\epsilon_i$-DP, then $\mathcal{G}$ is $\sum_{i=1}^k \epsilon_i$-DP.

**Proposition 3 (Parallel Composition).** Let $\mathcal{M}^1, \dots, \mathcal{M}^k$ be $k$ mechanisms, such that $k < n$, where $n$ is the size of the input dataset. Let $t_1, \dots, t_k, t_{k+1}$ be indexes in $[1, n]$ such that $1 = t_1 < \dots < t_k < t_{k+1} - 1 = n$.

Let's define the following mechanism

$$
\mathcal{G}: \{x_1, \dots, x_n\} \rightarrow \bigotimes_{i=1}^{k} \mathcal{M}_{\{x_{t_i}, \dots, x_{t_{i+1}-1}\}}^{i}
$$

$\mathcal{G}$ is the mechanism that we get by applying each $\mathcal{M}^i$ to the i-th partition of the input dataset $\{x_1, \dots, x_n\}$ according to the indexes $t_1 < \dots < t_k < t_{k+1}$.

If each $\mathcal{M}^i$ is $\epsilon$-DP, then $\mathcal{G}$ is $\epsilon$-DP.

In parallel composition, the $k$ mechanisms are applied to different “non-overlapping” parts of the input dataset. If each mechanism is DP, then the parallel composition of the $k$ mechanisms is DP, with the same privacy budget. This property will be the basis for designing private bandit algorithms.

F Concentration Results

In Appendix F, we detail the proof of all our concentration results. In Appendix F.1, we start by
introducing a variant of GLR-based stopping rule using the modified transportation costs $\tilde{W}_{\epsilon,a,b}$
(see Appendix G.2.1 for details) which are defined based on the modified divergences $\tilde{d}_{\epsilon}^{\pm}$ (see Appendix G.1.1 for details). The proof of Theorem 6 is given in Appendix F.2. In Appendix F.3, we show tail bounds for a sum between independent Bernoulli and Laplace observations that feature the product of the tail bounds of each process. We prove time-uniform and fixed-time tails concentration for Laplace distribution in Appendix F.4, and recall existing results for Bernoulli in Appendix F.5. In Appendix F.6, we provide tail bounds for a sum between independent Bernoulli and Laplace observations that feature the modified divergence $\tilde{d}_{\epsilon}$ defined in Eq. (32). In Appendix F.7, we give geometric grid time uniform tails concentration for the reweighted modified divergence.

## F.1 Modified GLR Stopping Rule

The modified GLR stopping rule is defined as

$$ \tau_{\epsilon, \delta}^{\text{MGLR}} = \inf \left\{ n \mid \forall a \neq \tilde{a}_n, \tilde{W}_{\epsilon, \tilde{a}_n, a}(\tilde{\mu}_n, \tilde{N}_n) > \sum_{b \in \{\tilde{a}_n, a\}} \tilde{c}(k_{n,b}, \delta) \right\} \quad \text{with } \tilde{a}_n \in \arg \max_{a \in [K]} [\tilde{\mu}_{n,a}]_0^1, \qquad (22) $$

where $(\tilde{\mu}_n, \tilde{N}_n)$ are the outputs of GPE$_{\eta}(\epsilon)$. The modified transportation costs $(\tilde{W}_{\epsilon,a,b})_{(a,b) \in [K]^2}$ are defined in Eq. (34), i.e., for all $(\mu, w) \in \mathbb{R}^K \times \mathbb{R}_+^K$ and all $(a, b) \in [K]^2$ such that $a \neq b$,

$$ \tilde{W}_{\epsilon,a,b}(\mu, w) := 1 ([\mu_a]_0^1 > [\mu_b]_0^1) \inf_{u \in (0,1)} \left\{ w_a \tilde{d}_{\epsilon}^{-}(\mu_a, u, r(w_a)) + w_b \tilde{d}_{\epsilon}^{+}(\mu_b, u, r(w_b)) \right\}, $$

where $r(x) := \frac{x}{1+\log_{1+\eta} x}$ is defined in Eq. (33) for all $x \ge 1$. The modified divergence $\tilde{d}_{\epsilon}^{\pm}$ are defined in Eq. (32), i.e., for all $(\lambda, \mu, r) \in \mathbb{R} \times (0, 1) \times \mathbb{R}_+^*$,

$$ \tilde{d}_{\epsilon}^{-}(\lambda, \mu, r) := 1 (\mu < [\lambda]_0^1) \inf_{z \in (\mu, [\lambda]_0^1)} \left\{ \text{kl}(z, \mu) + \frac{1}{r} h(r\epsilon(\lambda - z)) \right\}, $$

$$ \tilde{d}_{\epsilon}^{+}(\lambda, \mu, r) := 1 (\mu > [\lambda]_0^1) \inf_{z \in ([\lambda]_0^1, \mu)} \left\{ \text{kl}(z, \mu) + \frac{1}{r} h(r\epsilon(z - \lambda)) \right\}, $$

where $h(x) := \sqrt{1+x^2} - 1 + \log\left(\frac{2}{x^2}(\sqrt{1+x^2} - 1)\right)$ is defined in Eq. (31) for all $x > 0$.

Lemma 9 gives a stopping threshold under which the modified GLR stopping rule is $\delta$-correct.

**Lemma 9.** Let $\delta \in (0, 1)$ and $\epsilon > 0$. Let $\eta > 0$. Let $s > 1$ and $\zeta$ be the Riemann $\zeta$ function. Let $\overline{W}_{-1}(x) = -W_{-1}(-e^{-x})$ for all $x \ge 1$, where $W_{-1}$ is the negative branch of the Lambert W function. It satisfies $\overline{W}_{-1}(x) \approx x + \log x$, see Lemma 52. Given any sampling rule using the GPE$_{\eta}(\epsilon)$, combining GPE$_{\eta}(\epsilon)$ with the modified GLR stopping rule as in Eq. (22) with the stopping threshold

$$ \tilde{c}(k, \delta) = \overline{W}_{-1} \left( \log \left( \frac{K\zeta(s)}{\delta} \right) + s \log(k) + 3 - \log 2 \right) - 3 + \log 2. \qquad (23) $$

yields a $\delta$-correct and $\epsilon$-global DP algorithm for Bernoulli instances with unique best arm.

*Proof.* Lemma 5 yields the $\epsilon$-global DP. Let $\mathcal{E}_{\delta} = \mathcal{E}_{\delta, a^*, +} \cap \bigcap_{a \neq a^*} \mathcal{E}_{\delta, a, -}$ with

$$ \mathcal{E}_{\delta, a^*, +} = \left\{ \forall n \in \mathbb{N}, \tilde{N}_{n, a^*} \tilde{d}_{\epsilon}^{+} (\tilde{\mu}_{n, a^*}, \mu_{a^*}, \tilde{N}_{n, a^*} / k_{n, a^*}) \le \tilde{c}(k_{n, a^*}, \delta) \right\}, $$

$$ \forall a \neq a^*, \quad \mathcal{E}_{\delta, a, -} = \left\{ \forall n \in \mathbb{N}, \tilde{N}_{n, a} \tilde{d}_{\epsilon}^{-} (\tilde{\mu}_{n, a}, \mu_{a}, \tilde{N}_{n, a} / k_{n, a}) \le \tilde{c}(k_{n, a}, \delta) \right\}, $$

where $(\tilde{\mu}_n, \tilde{N}_n, k_n)$ are given by GPE$_{\eta}(\epsilon)$, $\tilde{c}$ as in Eq. (23) and $\tilde{d}_{\epsilon}^{\pm}$ as in Eq. (32).

Using Lemmas 20 and 21, we have $\mathbb{P}_{\nu\pi}(\mathcal{E}_{\delta, a, -}^{\mathcal{C}}) \le \delta/K$ for all $a \neq a^*$, and $\mathbb{P}_{\nu\pi}(\mathcal{E}_{\delta, a^*, +}^{\mathcal{C}}) \le \delta/K$. By union bound over $a \in [K]$, we obtain $\mathbb{P}_{\nu\pi}(\mathcal{E}_{\delta}^{\mathcal{C}}) \le \delta$.

Let $\tau_{\epsilon, \delta}^{\text{MGLR}}$ as in Eq. (22) and $\tilde{a}_n \in \arg \max_{a \in [K]} [\tilde{\mu}_{n,a}]_0^1$. Then, we directly have that

$$ \mathbb{P}_{\nu\pi} \left( \tau_{\epsilon, \delta}^{\text{MGLR}} < +\infty, \tilde{a}_{\tau_{\epsilon, \delta}^{\text{MGLR}}} \neq a^* \right) \le \mathbb{P}_{\nu\pi} \left( \mathcal{E}_{\delta}^{\mathcal{C}} \right) + \mathbb{P}_{\nu\pi} \left( \mathcal{E}_{\delta} \cap \left\{ \tau_{\epsilon, \delta}^{\text{MGLR}} < +\infty, \tilde{a}_{\tau_{\epsilon, \delta}^{\text{MGLR}}} \neq a^* \right\} \right) $$
$$ \leq \delta + \mathbb{P}_{\nu\pi} (\mathcal{E}_{\delta} \cap \{\tau_{\epsilon, \delta}^{\text{MGLR}} < +\infty, \tilde{a}_{\tau_{\epsilon, \delta}^{\text{MGLR}}} \neq a^*\}). $$

Under $\mathcal{E}_{\delta} \cap \{\tau_{\epsilon, \delta}^{\text{MGLR}} < +\infty, \tilde{a}_{\tau_{\epsilon, \delta}^{\text{MGLR}}} \neq a^*\}$, by definition of the stopping rule as in Eq. (7) and the stopping threshold in Eq. (8), we obtain that there exists $a \neq a^*$ and $n \in \mathbb{N}$ such that $[\tilde{\mu}_{n,a}]_0^1 > [\tilde{\mu}_{n,a^*}]_0^1$ and

$$
\begin{align*}
& \sum_{b \in \{a, a^*\}} \tilde{c}(k_{n,b}, \delta) < \tilde{W}_{\epsilon, a, a^*}(\tilde{\mu}_n, \tilde{N}_n) \\
&= \inf_{u \in (0,1)} \left\{ \tilde{N}_{n,a} \tilde{d}_{\epsilon}^{-}(\tilde{\mu}_{n,a}, u, r(\tilde{N}_{n,a})) + \tilde{N}_{n,a^*} \tilde{d}_{\epsilon}^{+}(\tilde{\mu}_{n,a^*}, u, r(\tilde{N}_{n,a^*})) \right\} \\
&= \inf_{(u_a, u_{a^*}) \in (0,1)^2, u_a \le u_{a^*}} \left\{ \tilde{N}_{n,a} \tilde{d}_{\epsilon}^{-}(\tilde{\mu}_{n,a}, u_a, r(\tilde{N}_{n,a})) + \tilde{N}_{n,a^*} \tilde{d}_{\epsilon}^{+}(\tilde{\mu}_{n,a^*}, u_{a^*}, r(\tilde{N}_{n,a^*})) \right\} \\
&\le \tilde{N}_{n,a} \tilde{d}_{\epsilon}^{-}(\tilde{\mu}_{n,a}, \mu_a, r(\tilde{N}_{n,a})) + \tilde{N}_{n,a^*} \tilde{d}_{\epsilon}^{+}(\tilde{\mu}_{n,a^*}, \mu_{a^*}, r(\tilde{N}_{n,a^*})) \\
&\le \tilde{N}_{n,a} \tilde{d}_{\epsilon}^{-}(\tilde{\mu}_{n,a}, \mu_a, \tilde{N}_{n,a}/k_{n,a}) + \tilde{N}_{n,a^*} \tilde{d}_{\epsilon}^{+}(\tilde{\mu}_{n,a^*}, \mu_{a^*}, \tilde{N}_{n,a^*}/k_{n,a^*}) \le \sum_{b \in \{a, a^*\}} \tilde{c}(k_{n,b}, \delta),
\end{align*}
$$

where we used the definition of $\tilde{W}_{\epsilon, a, a^*}$ in Eq. (34) and Lemma 40 in the two equalities and $\mu_{a^*} > \mu_a$ in the following inequality. The second to last inequality uses that $r(\tilde{N}_{n,a}) \le \tilde{N}_{n,a}/k_{n,a}$ for all $a \in [K]$ by definition of $(k_n, \tilde{N}_n)$, i.e., $k_{n,a} \le 1 + \log_{1+\eta} \tilde{N}_{n,a} \le k_{n,a} + 1$, and that $r \mapsto \tilde{d}_{\epsilon}^{\pm}(\lambda, u, r)$ is non-decreasing, see Lemmas 31 and 32. The last inequality is obtained by the concentration event $\mathcal{E}_{\delta}$. Since this yields a contradiction, we obtain $\mathcal{E}_{\delta} \cap \{\tau_{\epsilon, \delta}^{\text{MGLR}} < +\infty, \tilde{a}_{\tau_{\epsilon, \delta}^{\text{MGLR}}} \neq a^*\} = \emptyset$. This concludes the proof, i.e., $\mathbb{P}_{\nu\pi} (\tau_{\epsilon, \delta}^{\text{MGLR}} < +\infty, \tilde{a}_{\tau_{\epsilon, \delta}^{\text{MGLR}}} \neq a^*) \le \delta$. $\square$

## F.2 Proof of Theorem 6

Lemma 5 yields the $\epsilon$-global DP. The proof of $\delta$-correctness is the same as the one of Lemma 9 detailed above. In particular, we use the same concentration event $\mathcal{E}_{\delta} = \mathcal{E}_{\delta, a^*, +} \cap \bigcap_{a \neq a^*} \mathcal{E}_{\delta, a, -}$ that satisfies $\mathbb{P}_{\nu\pi}(\mathcal{E}_{\delta}^{\mathcal{C}}) \le \delta$.

Under $\mathcal{E}_{\delta} \cap \{\tau_{\epsilon, \delta}^{\text{MGLR}} < +\infty, \tilde{a}_{\tau_{\epsilon, \delta}^{\text{MGLR}}} \neq a^*\}$, by definition of the GLR stopping rule as in Eq. (7) and the stopping threshold in Eq. (8), we obtain that there exists $a \neq a^*$ and $n \in \mathbb{N}$ such that $[\tilde{\mu}_{n,a}]_0^1 > [\tilde{\mu}_{n,a^*}]_0^1$,

$$ \sum_{b \in \{a, a^*\}} \left( c_1(\tilde{N}_{n,b}, \delta) + c_2(\tilde{N}_{n,b}, \epsilon) \right) = \sum_{b \in \{a, a^*\}} c(k_{n,b}, \epsilon, \delta) < W_{\epsilon, a, a^*}(\tilde{\mu}_n, \tilde{N}_n). $$

Then, we obtain

$$
\begin{align*}
W_{\epsilon, a, a^*}(\tilde{\mu}_n, \tilde{N}_n) &= \inf_{u \in [0,1]} \left\{ \tilde{N}_{n,a} d_{\epsilon}^{-}(\tilde{\mu}_{n,a}, u) + \tilde{N}_{n,a^*} d_{\epsilon}^{+}(\tilde{\mu}_{n,a^*}, u) \right\} \\
&= \inf_{(u_a, u_{a^*}) \in [0,1]^2, u_a \le u_{a^*}} \left\{ \tilde{N}_{n,a} d_{\epsilon}^{-}(\tilde{\mu}_{n,a}, u_a) + \tilde{N}_{n,a^*} d_{\epsilon}^{+}(\tilde{\mu}_{n,a^*}, u_{a^*}) \right\} \\
&\le \tilde{N}_{n,a} d_{\epsilon}^{-}(\tilde{\mu}_{n,a}, \mu_a) + \tilde{N}_{n,a^*} d_{\epsilon}^{+}(\tilde{\mu}_{n,a^*}, \mu_{a^*}),
\end{align*}
$$

where we used the definition of $W_{\epsilon, a, a^*}$ in Eq. (4) and Lemma 35 in the two equalities, and $(u_{a^*}, u_a) = (\mu_{a^*}, \mu_a) \in [0, 1]^2$ that satisfies $u_{a^*} > u_a$ in the following inequality.

Using Lemma 39 and initialization yields $\min\{r(\tilde{N}_{n,a^*}), r(\tilde{N}_{n,a})\} > 0$ by. When $[\tilde{\mu}_{n,a}]_0^1 > \mu_a$ and $\mu_{a^*} > [\tilde{\mu}_{n,a^*}]_0^1$, Lemma 30 yields

$$
\begin{align*}
\tilde{N}_{n,a^*} (d_{\epsilon}^{+}(\tilde{\mu}_{n,a^*}, \mu_{a^*}) - d_{\epsilon}^{-}(\tilde{\mu}_{n,a^*}, \mu_{a^*}, r(\tilde{N}_{n,a^*}))) &\le k_{\eta}(\tilde{N}_{n,a^*}) (\log(1 + 2\epsilon \frac{\tilde{N}_{n,a^*}}{k_{\eta}(\tilde{N}_{n,a^*})}) + 1) \\
\tilde{N}_{n,a} (d_{\epsilon}^{-}(\tilde{\mu}_{n,a}, \mu_a) - d_{\epsilon}^{-}(\tilde{\mu}_{n,a}, \mu_a, r(\tilde{N}_{n,a}))) &\le k_{\eta}(\tilde{N}_{n,a}) \left( \log \left( 1 + 2\epsilon \frac{\tilde{N}_{n,a}}{k_{\eta}(\tilde{N}_{n,a})} \right) + 1 \right),
\end{align*}
$$
where we used that $(\mu_a, \mu_{a^*}) \in (0, 1)^2$ and $x/r(x) = 1+\log_{1+\eta} x = k_\eta(x)$. When $[\tilde{\mu}_{n,a}]_0^1 \le \mu_a$, we have $d_\epsilon^-(\tilde{\mu}_{n,a}, \mu_a) = 0 = \tilde{d}_\epsilon^-(\tilde{\mu}_{n,a}, \mu_a, r(\tilde{N}_{n,a}))$. When $\mu_{a^*} \le [\tilde{\mu}_{n,a^*}]_0^1$, we have $d_\epsilon^+(\tilde{\mu}_{n,a^*}, \mu_{a^*}) = 0 = \tilde{d}_\epsilon^+(\tilde{\mu}_{n,a^*}, \mu_{a^*}, r(\tilde{N}_{n,a^*}))$. In either case, the above inequalities are still valid since the left hand side is null and the right hand side is positive. Therefore, we have

$$ \begin{aligned} & \tilde{N}_{n,a} d_{\epsilon}^{-}(\tilde{\mu}_{n,a}, \mu_a) + \tilde{N}_{n,a^*} d_{\epsilon}^{+}(\tilde{\mu}_{n,a^*}, \mu_{a^*}) \\ & \le \tilde{N}_{n,a} d_{\epsilon}^{-}(\tilde{\mu}_{n,a}, \mu_a, r(\tilde{N}_{n,a})) + \tilde{N}_{n,a^*} d_{\epsilon}^{+}(\tilde{\mu}_{n,a^*}, \mu_{a^*}, r(\tilde{N}_{n,a^*})) + \sum_{b \in \{a, a^*\}} c_2(\tilde{N}_{n,b}, \epsilon) \\ & \le \sum_{b \in \{a, a^*\}} \tilde{c}(k_{n,b}, \delta) + \sum_{b \in \{a, a^*\}} c_2(\tilde{N}_{n,b}, \epsilon) \le \sum_{b \in \{a, a^*\}} \left( c_1(\tilde{N}_{n,b}, \delta) + c_2(\tilde{N}_{n,b}, \epsilon) \right), \end{aligned} $$

where the second inequality uses the proof of Lemma 9, and third leverages that

$$ \tilde{c}(k_{n,a}, \delta) \le \bar{W}_{-1} \left( \log \left( \frac{K\zeta(s)}{\delta} \right) + s \log(k_\eta(\tilde{N}_{n,a})) + 3 - \log 2 \right) - 3 + \log 2, $$

by using that $\bar{W}_{-1}$ is increasing (Lemma 52) and $k_{n,a} \le 1 + \log_{1+\eta} \tilde{N}_{n,a} = k_\eta(\tilde{N}_{n,a})$ for all $a \in [K]$, as well as $r(x) = x/k_\eta(x)$. Combining all the above inequalities, we have shown that

$$ \sum_{b \in \{a, a^*\}} (c_1(\tilde{N}_{n,b}, \delta) + c_2(\tilde{N}_{n,b}, \epsilon)) < W_{\epsilon, a, a^*}(\tilde{\mu}_n, \tilde{N}_n) \le \sum_{b \in \{a, a^*\}} (c_1(\tilde{N}_{n,b}, \delta) + c_2(\tilde{N}_{n,b}, \epsilon)). $$

This yields a contradiction, hence we have $\mathcal{E}_\delta \cap \{\tau_{\epsilon,\delta} < +\infty, \tilde{a}_{\tau_{\epsilon,\delta}} \neq a^*\} = \emptyset$. This concludes the proof, i.e., $\mathbb{P}_{\nu_\pi}(\tau_{\epsilon,\delta} < +\infty, \tilde{a}_{\tau_{\epsilon,\delta}} \neq a^*) \le \delta$.

### F.3 Fixed Time Tails Bounds for a Convolution of Probability Distributions

We derive general upper and lower bounds on the upper and lower tails of the convolution (i.e., sum) between two independent random variables (Lemma 10). We provide upper (Lemma 12) and lower (Lemma 12) tail bounds for a sum (i.e., convolution) between independent Bernoulli and Laplace i.i.d. observations for a fixed time. The bounds are expressed as a function of the infimum over a bounded interval of a $-\frac{1}{t} \log(\cdot)$ transform of the product between the (upper or lower) tail bounds of each process. Therefore, in Lemmas 12 and 12, we can plug any bounds on the (upper or lower) tail concentration of each process. While those bounds are standard for Bernoulli distribution (Lemma 17 in Appendix F.5), we propose new bounds for Laplace distribution (Lemma 16 in Appendix F.4).

**Sketch of Proof of Lemma 10** The main difficulty when studying the sum of two random variables lies in the fact that it involves the integral of the convolution of their probability measures. In all generality, it is difficult to upper bound such a quantity. The main idea behind our proof technique is to split the event of interest into a partition of carefully chosen events. Then, on each of those smaller events, we derive a "tight" upper bound on the integral of the convolution of their probability measures. It is reasonable to wonder how one could choose those events such that the upper bound is easier to obtain. When the event is defined as the intersection of two independent events, then we obtain a straightforward upper bound by the product of their respective probabilities. When the event truly mixes the distributions, we need to use a smarter approach to control the integrated function. First, we upper bound a sub-component of this function by a maximum of the product of their respective probabilities (on a small interval that is defined by the smaller event). Second, after this upper bound, the integrated function coincides with the hazard function, whose integral is the cumulative hazard function. To conclude the proof, it only remains to merge together the different upper bounds.

To the best of our knowledge, the proof technique closest to ours is the one used to prove Lemma 64 in Jourdan et al. [2022]. They control the probability that two random variables have an unexpected empirical ranking as a function of the boundary crossing probabilities of each random variable. While tackling a distinct problem, they adopt the same proof structure. They decompose the event into carefully chosen events on which they can upper bound the integral of the convolution of their probability distributions. The upper bounds are obtained similarly as ours, with fewer events to consider.

Lemma 10 gives upper and lower bounds on the upper and lower tails of the sum of two independent random variables. This result is of independent interest.
**Lemma 10.** Let $\theta$ and $\lambda$ be two independent real random variables such that (i) $\theta$ has bounded support included in $[\alpha, \beta]$ and mean $\mu \in (\alpha, \beta)$ and (ii) $\lambda$ has zero mean. Let

$$ \forall u \in [0, 1], \forall v \in (0, 1], \quad p(u, v) := u(1 - \log(u) + \log(v)). $$

Then, for all $x > 0$, we have

$$ \begin{aligned} \mathbb{P}(\theta + \lambda \ge \mu + x) &\le \mathbb{P}(\lambda \ge x)\mathbb{P}(\theta \in [\alpha, \mu]) + \mathbb{P}(\lambda \le 0)\mathbb{P}(\theta \in [\min\{\beta, \mu + x\}, \beta]) \\ &\quad + p\left( \sup_{z \in (\mu, \min\{\beta, \mu+x\})} \{\mathbb{P}(\theta \in [z, \beta])\mathbb{P}(\lambda \ge \mu + x - z)\}, \mathbb{P}(\theta \in [\mu, \beta])\mathbb{P}(\lambda \ge 0) \right), \\ \mathbb{P}(\theta + \lambda \ge \mu + x) &\ge \sup_{z \in (\mu, \min\{\beta, \mu+x\})} \{\mathbb{P}(\theta \in [z, \beta])\mathbb{P}(\lambda \ge \mu + x - z)\}, \\ \mathbb{P}(\theta + \lambda \le \mu - x) &\le \mathbb{P}(\lambda \le -x)\mathbb{P}(\theta \in [\mu, \beta]) + \mathbb{P}(\lambda \ge 0)\mathbb{P}(\theta \in [\alpha, \max\{\alpha, \mu - x\}]) \\ &\quad + p\left( \sup_{z \in (\max\{\alpha, \mu-x\}, \mu)} \{\mathbb{P}(\theta \in [\alpha, z])\mathbb{P}(\lambda \le \mu - x - z)\}, \mathbb{P}(\theta \in [\alpha, \mu])\mathbb{P}(\lambda \le 0) \right), \\ \mathbb{P}(\theta + \lambda \le \mu - x) &\ge \sup_{z \in (\max\{\alpha, \mu-x\}, \mu)} \{\mathbb{P}(\theta \in [\alpha, z])\mathbb{P}(\lambda \le \mu - x - z)\}. \end{aligned} $$

**Proof. I. Upper Bound on Upper Tail.** We start by studying $\mathbb{P}(\theta + \lambda \ge \mu + x)$ where $x > 0$. We can suppose that there exists $y_1 \in (\max\{x + \mu - \beta, 0\}, x)$ such that $\mathbb{P}(\theta \ge x + \mu - y_1)\mathbb{P}(\lambda \ge y_1) > 0$. Otherwise, the probability of $\{\theta + \lambda \ge \mu + x\}$ is 0, and both bounds are 0 as well. Let $y_1$ be such a value, and

$$ y_3 \in [x, x + \mu) \quad \text{and} \quad y_2 \in (\min\{x + \mu - \beta, 0\}, 0]. $$

First, we note that $-\log \mathbb{P}(\theta \ge x + \mu - y_1)$ and $-\log \mathbb{P}(\lambda \ge y_1)$ are finite, since $\mathbb{P}(\theta \ge x + \mu - y_1)\mathbb{P}(\lambda \ge y_1) > 0$ implies that $\min\{\mathbb{P}(\theta \ge x + \mu - y_1), \mathbb{P}(\lambda \ge y_1)\} > 0$. Second, we note that $y_2$ only exists when $x + \mu < \beta$, i.e., $(\min\{x + \mu - \beta, 0\}, 0] \neq \emptyset$. In order to study the cases $x + \mu < \beta$ and $x + \mu \ge \beta$ simultaneously, we adopt the convention that the maximum of a positive quantity on an empty set is defined as zero. Note that the situation $x + \mu < \beta$ has more subcases.

We partition of the event $\{\theta + \lambda \ge \mu + x\}$ into eight sets, namely

$$ \begin{aligned} \{\theta + \lambda \ge \mu + x, \theta \in [\alpha, \beta], \lambda \in \mathbb{R}\} &= \{\lambda \in (\max\{x + \mu - \beta, 0\}, y_1), \theta \in [x + \mu - \lambda, \beta]\} \\ &\quad \cup \{\theta \in [x + \mu - y_1, \beta], \lambda \ge y_1\} \\ &\quad \cup \{\theta \in (\mu, x + \mu - y_1), \lambda \ge x + \mu - \theta\} \\ &\quad \cup \{\theta \in [x + \mu - y_3, \mu], \lambda \ge x + \mu - \theta\} \\ &\quad \cup \{\theta \in [\alpha, x + \mu - y_3), \lambda \ge x + \mu\} \\ &\quad \cup \{\lambda \in [y_3, x + \mu), \theta \in [x + \mu - \lambda, x + \mu - y_3]\} \\ &\quad \cup \{\lambda \in [y_2, 0], \theta \in [x + \mu - \lambda, \beta]\} \\ &\quad \cup \{\lambda \in [x + \mu - \theta, y_2), \theta \in [x + \mu - y_2, \beta]\}. \end{aligned} $$

First, it is direct to see that

$$ \begin{aligned} &\{\lambda \in [y_2, 0], \theta \in [x + \mu - \lambda, \beta]\} \cup \{\lambda \in [x + \mu - \theta, y_2), \theta \in [x + \mu - y_2, \beta]\} \\ &\subseteq \{\lambda \le 0, \theta \in [\min\{\beta, \mu + x\}, \beta]\}, \\ &\{\theta \in [x + \mu - y_3, \mu], \lambda \ge x + \mu - \theta\} \cup \{\theta \in [\alpha, x + \mu - y_3), \lambda \ge x + \mu\} \\ &\quad \cup \{\lambda \in [y_3, x + \mu), \theta \in [x + \mu - \lambda, x + \mu - y_3]\} \subseteq \{\lambda \ge x, \theta \in [\alpha, \mu]\}. \end{aligned} $$

By union bound, the probability of the union of those five events is upper bounded by the sum of the probability of those two events, i.e., $\mathbb{P}(\lambda \ge x, \theta \in [\alpha, \mu]) + \mathbb{P}(\lambda \le 0, \theta \in [\min\{\beta, \mu + x\}, \beta])$.

**A. Separate Conditions.** Those two events and one of the three remaining do not require to control $(\theta, \lambda)$ simultaneously, as they separate the conditions on $(\theta, \lambda)$. Thanks to the independence of $(\theta, \lambda)$, the probability of those events can be simply upper bounded by the product of the respective probability of those conditions. Therefore, we obtain

$$ \begin{aligned} &\mathbb{P}(\lambda \ge x, \theta \in [\alpha, \mu]) + \mathbb{P}(\lambda \le 0, \theta \in [\min\{\beta, \mu + x\}, \beta]) + \mathbb{P}(\theta \in [x + \mu - y_1, \beta], \lambda \ge y_1) \\ &= \mathbb{P}(\lambda \ge x)\mathbb{P}(\theta \in [\alpha, \mu]) + \mathbb{P}(\lambda \le 0)\mathbb{P}(\theta \in [\min\{\beta, \mu + x\}, \beta]) \end{aligned} $$
$$+ \mathbb{P}(\theta \in [x + \mu - y_1, \beta]) \mathbb{P}(\lambda \geq y_1).$$

**B. Mixed Conditions.** The two remaining events truly require to control $(\theta, \lambda)$ simultaneously, i.e., consider their convolution. The proof idea is the following: (1) we integrate one integral to obtain one survival function, (2) we make appear the other survival function artificially, (3) we upper bound the product of their survival functions on the whole set and (4) we integrate the remaining hazard function, whose integral is the cumulative hazard function. Let $dG$ and $dF$ be the probability measures of $\theta$ and $\lambda$ on $\mathbb{R}$.

For all $s \in (\max\{x + \mu - \beta, 0\}, y_1)$, we have $\mathbb{P}(\lambda \geq s) \geq \mathbb{P}(\lambda \geq y_1) > 0$. Then, we obtain

$$ 
\begin{aligned}
& \mathbb{P}(\lambda \in (\max\{x + \mu - \beta, 0\}, y_1), \theta \in [x + \mu - \lambda, \beta]) \\
&= \int_{s \in (\max\{x+\mu-\beta,0\}, y_1)} \mathbb{P}(\theta \in [x + \mu - s, \beta]) dF(s) \\
&= \int_{s \in (\max\{x+\mu-\beta,0\}, y_1)} \mathbb{P}(\lambda \geq s) \mathbb{P}(\theta \in [x + \mu - s, \beta]) \frac{1}{\mathbb{P}(\lambda \geq s)} dF(s) \\
&\leq \sup_{s \in (\max\{x+\mu-\beta,0\}, y_1)} \{\mathbb{P}(\lambda \geq s) \mathbb{P}(\theta \in [x + \mu - s, \beta])\} \int_{s \in (\max\{x+\mu-\beta,0\}, y_1)} \frac{1}{\mathbb{P}(\lambda \geq s)} dF(s) \\
&\leq \sup_{s \in (\max\{x+\mu-\beta,0\}, y_1)} \{\mathbb{P}(\lambda \geq s) \mathbb{P}(\theta \in [x + \mu - s, \beta])\} (-\log(\mathbb{P}(\lambda \geq y_1)) + \log(\mathbb{P}(\lambda \geq 0))),
\end{aligned}
$$

where we used that $\mathbb{P}(\lambda \geq \max\{x + \mu - \beta, 0\}) \leq \mathbb{P}(\lambda \geq 0)$.

For all $z \in (\mu, x + \mu - y_1)$, we have $\mathbb{P}(\theta \in [z, \beta]) \geq \mathbb{P}(\theta \in [x + \mu - y_1, \beta]) > 0$. Then, we obtain

$$ 
\begin{aligned}
& \mathbb{P}(\theta \in (\mu, x + \mu - y_1), \lambda \geq x + \mu - \theta) \\
&= \int_{z \in (\mu, x + \mu - y_1)} \mathbb{P}(\lambda \geq x + \mu - z) dG(z) \\
&= \int_{z \in (\mu, x + \mu - y_1)} \mathbb{P}(\lambda \geq x + \mu - z) \mathbb{P}(\theta \in [z, \beta]) \frac{1}{\mathbb{P}(\theta \in [z, \beta])} dG(z) \\
&\leq \sup_{z \in (\mu, x + \mu - y_1)} \{\mathbb{P}(\lambda \geq x + \mu - z) \mathbb{P}(\theta \in [z, \beta])\} \int_{z \in (\mu, x + \mu - y_1)} \frac{1}{\mathbb{P}(\theta \in [z, \beta])} dG(z) \\
&\leq \sup_{s \in (y_1, x)} \{\mathbb{P}(\lambda \geq s) \mathbb{P}(\theta \in [x + \mu - s, \beta])\} \\
&\qquad \cdot (-\log(\mathbb{P}(\theta \in [x + \mu - y_1, \beta])) + \log(\mathbb{P}(\theta \in [\mu, \beta]))).
\end{aligned}
$$

**C. Combining Results.** Putting everything together, we have, for all $y_1 \in (\max\{x + \mu - \beta, 0\}, x)$,

$$ 
\begin{aligned}
& \mathbb{P}(\theta + \lambda \geq \mu + x) \leq \mathbb{P}(\lambda \geq x) \mathbb{P}(\theta \in [\alpha, \mu]) + \mathbb{P}(\lambda \leq 0) \mathbb{P}(\theta \in [\min\{\beta, \mu + x\}, \beta]) \\
& + \mathbb{P}(\theta \in [x + \mu - y_1, \beta]) \mathbb{P}(\lambda \geq y_1) \\
& + \sup_{s \in (\max\{x + \mu - \beta, 0\}, y_1)} \{\mathbb{P}(\lambda \geq s) \mathbb{P}(\theta \in [x + \mu - s, \beta])\} (-\log(\mathbb{P}(\lambda \geq y_1)) + \log(\mathbb{P}(\lambda \geq 0))) \\
& + \sup_{s \in (y_1, x)} \{\mathbb{P}(\lambda \geq s) \mathbb{P}(\theta \in [x + \mu - s, \beta])\} (-\log(\mathbb{P}(\theta \in [x + \mu - y_1, \beta])) + \log(\mathbb{P}(\theta \in [\mu, \beta])))) \\
& \leq \mathbb{P}(\lambda \geq x) \mathbb{P}(\theta \in [\alpha, \mu]) + \mathbb{P}(\lambda \leq 0) \mathbb{P}(\theta \in [\min\{\beta, \mu + x\}, \beta]) \\
& + \mathbb{P}(\theta \in [x + \mu - y_1, \beta]) \mathbb{P}(\lambda \geq y_1) \\
& + \sup_{s \in (\max\{x + \mu - \beta, 0\}, x)} \{\mathbb{P}(\lambda \geq s) \mathbb{P}(\theta \in [x + \mu - s, \beta])\} \\
&\qquad \cdot (-\log(\mathbb{P}(\lambda \geq y_1) \mathbb{P}(\theta \in [x + \mu - y_1, \beta])) + \log(\mathbb{P}(\theta \in [\mu, \beta]) \mathbb{P}(\lambda \geq 0))),
\end{aligned}
$$

where the second inequality is obtained by extending the two suprema to $(\max\{x + \mu - \beta, 0\}, x)$, which is possible since multiplied by a positive value, and factorizing them together. Taking

$$y_1^* \in \arg \max_{s \in (\max\{x+\mu-\beta,0\},x)} \{\mathbb{P}(\lambda \geq s) \mathbb{P}(\theta \in [x + \mu - s, \beta])\},$$

and the change of variable $z = x + \mu - s$, i.e.,

$$\sup_{s \in (\max\{x+\mu-\beta,0\},x)} \{\mathbb{P}(\lambda \geq s) \mathbb{P}(\theta \in [x + \mu - s, \beta])\}$$
$$= \sup_{z \in (\mu, \min\{\beta, x+\mu\})} \{\mathbb{P}(\theta \in [z, \beta])\mathbb{P}(\lambda \ge x + \mu - z)\},$$

concludes the proof of the upper bound on the upper tail.

**II. Lower Bound on Upper Tail.** Let $z \in (\mu, \min\{\beta, \mu + x\})$. Then, we have directly that

$$\{\theta \in [z, \beta], \lambda \ge \mu + x - z\} \subseteq \{\theta + \lambda \ge \mu + x\}.$$

Using independence, we obtain

$$\mathbb{P}(\theta \in [z, \beta])\mathbb{P}(\lambda \ge \mu + x - z) = \mathbb{P}(\theta \in [z, \beta], \lambda \ge \mu + x - z) \le \mathbb{P}(\theta + \lambda \ge \mu + x).$$

Taking the supremum over $z \in (\mu, \min\{\beta, \mu + x\})$ on the left hand side concludes the proof of the lower bound on the upper tail.

**III. Upper/Lower Bound on Lower Tail.** The third and fourth inequalities are a direct consequence of the first and second inequalities applied to the two independent real random variables $-\theta$ and $-\lambda$ since (1) $-\theta$ has bounded support included in $[-\beta, -\alpha]$ and mean $-\mu \in (-\beta, -\alpha)$, and (2) $-\lambda$ has zero mean. Namely,

$$\begin{aligned}
\mathbb{P}(\theta + \lambda \le \mu - x) &= \mathbb{P}(-\theta - \lambda \ge -\mu + x), \\
\mathbb{P}(\lambda \le -x)\mathbb{P}(\theta \in [\mu, \beta]) &= \mathbb{P}(-\lambda \ge x)\mathbb{P}(-\theta \in [-\beta, -\mu]), \\
\mathbb{P}(\lambda \ge 0)\mathbb{P}(\theta \in [\alpha, \max\{\alpha, \mu - x\}]) &= \mathbb{P}(-\lambda \le 0)\mathbb{P}(-\theta \in [\min\{-\alpha, x - \mu\}, -\alpha]), \\
\mathbb{P}(\theta \in [\alpha, \mu])\mathbb{P}(\lambda \le 0) &= \mathbb{P}(-\theta \in [-\mu, -\alpha])\mathbb{P}(-\lambda \ge 0), \\
\sup_{z \in (\max\{\alpha, \mu - x\}, \mu)} \{\mathbb{P}(\theta \in [\alpha, z])\mathbb{P}(\lambda \le \mu - x - z)\} \\
&= \sup_{\tilde{z} \in (-\mu, \min\{-\alpha, -\mu + x\})} \{\mathbb{P}(-\theta \in [\tilde{z}, -\alpha])\mathbb{P}(-\lambda \ge -\mu + x - \tilde{z})\},
\end{aligned}$$

where we used the change of variable $\tilde{z} = -z$. $\square$

**Properties on the Rate Function** Lemma 11 gathers properties on the rate function $f$ in Lemmas 12 and 12.

**Lemma 11.** Let us define

$$\forall x \ge 0, \quad f(x) := (x + 3 - \log 2) \exp(-x). \qquad (24)$$

On $\mathbb{R}_+$, the function $f$ is twice continuously differentiable, positive, decreasing and strictly convex. It satisfies $f(0) > 1$, $\lim_{x \to +\infty} f(x) = 0$ and

$$f(x) \le \delta \iff x \ge \bar{W}_{-1}(\log(1/\delta) + 3 - \log 2) - 3 + \log 2,$$

where $\bar{W}_{-1}$ is defined in Lemma 52.

*Proof.* Direct manipulation yields $f(0) = 3 - \log 2 > 1$, $\lim_{x \to +\infty} f(x) = 0$, $\forall x \ge 0$, $f'(x) = -(x + 2 - \log 2) \exp(-x) < 0$ and $f''(x) = (x + 1 - \log 2) \exp(-x) > 0$.

Using that $f(x) = e^{3-\log 2} \exp(-h(x + 3 - \log 2))$ where $h(x) = x - \log(x)$, Lemma 52 yields

$$\begin{aligned}
f(x) \le \delta &\iff h(x + 3 - \log 2) \ge \log (e^{3-\log 2}/\delta) \\
&\iff \bar{W}_{-1}(\log(1/\delta) + 3 - \log 2) - 3 + \log 2 \le x.
\end{aligned}$$

**Fixed Time Upper and Lower Tails Concentration** Lemma 12 gives an upper and lower tails bound for a sum between independent Bernoulli and Laplace i.i.d. observations for a fixed time.

**Lemma 12.** Let $\mu \in (0, 1)$ and $\epsilon > 0$. Let $Z_t = \sum_{s \in [t]} X_s$ where $X_s \sim \text{Ber}(\mu)$ are i.i.d. observations. Let $S_t = \sum_{s \in [n_t]} Y_s$ where $Y_s \sim \text{Lap}(1/\epsilon)$ are i.i.d. observations where $(n_t)_{t \in \mathbb{N}}$ be a piece-wise constant increasing function from $\mathbb{N}$ to $\mathbb{N}$. Let $f$ as in Eq. (24). Then, for all $t \in \mathbb{N}$ and all $x > 0$,

$$\begin{aligned}
\mathbb{P}(Z_t + S_t \ge t(x + \mu)) &\le f\left(t \inf_{z \in (\mu, \min\{1, x+\mu\})} \left\{-\frac{1}{t} \log \left(\mathbb{P}(Z_t \ge tz)\mathbb{P}(S_t \ge t(x + \mu - z))\right)\right\}\right) \\
\mathbb{P}(Z_t + S_t \le t(\mu - x)) &\le f\left(t \inf_{z \in (\max\{0, \mu - x\}, \mu)} \left\{-\frac{1}{t} \log \left(\mathbb{P}(Z_t \le tz)\mathbb{P}(S_t \le t(\mu - x - z))\right)\right\}\right)
\end{aligned}$$
**Proof.** Let $t \in \mathbb{N}$ and $x > 0$. Then, $Z_t$ and $S_t$ are two independent real random variables such that (1) $Z_t$ has bounded support included in $[0, t]$ and mean $t\mu \in (0, t)$ and (ii) $S_t$ has zero mean. By symmetry of Lap(1/ε) around 0, the cumulative sum of $n_t$ observations (i.e., $S_t$) is also symmetric around 0. However, $Z_t$ follows Bin($t, \mu$) which can be skewed. Therefore, we have

$$ \mathbb{P}(S_t \ge 0) = 1/2 = \mathbb{P}(S_t \le 0) \quad \text{and} \quad \max\{\mathbb{P}(Z_t \in [t\mu, t]), \mathbb{P}(Z_t \in [0, t\mu])\} \le 1, \\ \forall z \in [0, 1], \quad \mathbb{P}(Z_t \in [tz, t]) = \mathbb{P}(Z_t \ge tz) \quad \text{and} \quad \mathbb{P}(Z_t \in [0, tz]) = \mathbb{P}(Z_t \le tz). $$

Using that $z \mapsto \mathbb{P}(Z_t \ge tz)$ is decreasing on $(\mu, \min\{1, x + \mu\})$ and $z \mapsto \mathbb{P}(S_t \ge t(\mu - x - z))$ is increasing on $(\mu, \min\{1, x + \mu\})$, we obtain

$$ \max\{\mathbb{P}(Z_t \ge t \min\{1, x + \mu\})\} \mathbb{P}(S_t \le 0), \mathbb{P}(S_t \ge tx) \mathbb{P}(Z_t \le t\mu) \\ \le \sup_{z \in (\mu, \min\{1, x+\mu\})} \{\mathbb{P}(Z_t \ge tz) \mathbb{P}(S_t \ge t(x + \mu - z))\}. $$

Let us define $g(x) := x(3 - \log(2) - \log(x))$. Using Lemma 10 for $(Z_t, S_t)$ and considering $tx > 0$ and $z \in (\mu, \min\{\beta, \mu + x\})$ (i.e., $tz \in (t\mu, t \min\{\beta, \mu + x\})$), we obtain

$$ \mathbb{P}(Z_t + S_t \ge t(x + \mu)) \le g \left( \sup_{z \in (\mu, \min\{1, x+\mu\})} \{\mathbb{P}(Z_t \ge tz) \mathbb{P}(S_t \ge t(x + \mu - z))\} \right). $$

Let $f$ as in Eq. (24) of Lemma 11. Then, we have $f(x) = g(\exp(-x))$. This concludes the proof of the upper bound on the upper tail. The second result is obtained similarly based on Lemma 10 and the above results. □

## F.4 Tails Concentration of Cumulative Laplace Distributions

We derive time-uniform (Lemma 15) and fixed-time (Lemma 16) tails concentration for the cumulative sum of i.i.d. Laplace observations. Our proof technique is based on the Chernoff method and Ville's inequality as in Eq. (26). Therefore, we need to derive the convex conjugate of the moment generating function of a Laplace distribution (Lemma 13). While the time-uniform result requires using the peeling method, the proof of the fixed-time concentration is simpler. To use the peeling method, we need to control the deviation of the process on slices of time (Lemma 14).

**Convex Conjugate of the Moment Generating Function of Laplace Distribution** Let $\epsilon > 0$. The moment generating function of the Laplace distribution Lap(1/ε) is defined as

$$ \forall \lambda \in (0, \epsilon), \quad \psi_{\text{Lap},\epsilon}(\lambda) = \log \mathbb{E}_{X \sim \text{Lap}(1/\epsilon)} [\exp(\lambda X)] = -\log(1 - \lambda^2/\epsilon^2). \quad (25) $$

Lemma 13 explicits the convex conjugate of $\psi_{\text{Lap},\epsilon}$ and its associated maximizer.

**Lemma 13.** Let $\psi_{\text{Lap},\epsilon}$ as in Eq. (25). Let us define

$$ \forall x > 0, \quad \psi_{\text{Lap},\epsilon}^*(x) := \max_{\lambda \in (0,\epsilon)} \{\lambda x - \psi_{\text{Lap},\epsilon}(\lambda)\} \quad \text{and} \quad \lambda(x) := \arg\max_{\lambda \in (0,\epsilon)} \{\lambda x - \psi_{\text{Lap},\epsilon}(\lambda)\}. $$

Then, for all $x > 0$, we have

$$ \lambda(x) = \frac{1}{x} \left( \sqrt{1 + (x\epsilon)^2} - 1 \right) \in (0, \epsilon) \quad \text{and} \quad \psi_{\text{Lap},\epsilon}^*(x) = h(\epsilon x) > 0. $$

where $h$ is defined in Eq. (31).

**Proof.** Let $f(\lambda) = \lambda x - \psi_{\text{Lap},\epsilon}(\lambda)$ for all $\lambda \in (0, \epsilon)$. Direct manipulation yields that

$$ \forall \lambda \in (0, \epsilon), \quad f'(\lambda) = x - \frac{2\lambda}{\epsilon^2 - \lambda^2} \quad \text{and} \quad f''(\lambda) = -2 \frac{\epsilon^2 + \lambda^2}{(\epsilon^2 - \lambda^2)^2} < 0. $$

Moreover, for all $\lambda \in (0, \epsilon)$, we have

$$ f'(\lambda) = 0 \iff \lambda^2 + 2\lambda/x - \epsilon^2 = 0 \iff \lambda = \frac{1}{x} \left( \sqrt{1 + (x\epsilon)^2} - 1 \right). $$

We used that the second solution to the second order polynomial equation is negative, hence not in $(0, \epsilon)$. Moreover, it is direct to see that $\frac{1}{x}(\sqrt{1 + (x\epsilon)^2} - 1) \in (0, \epsilon)$ since $\sqrt{1 + x^2} - 1 \le x$, as it
is equivalent to $1+x^2 \le (x+1)^2$ which is true when $x > 0$. Since $f$ is strictly concave, the above computation gives its unique maximizer on $(0, \epsilon)$, namely we have $\lambda(x) = \frac{1}{x}(\sqrt{1+(x\epsilon)^2}-1)$. Moreover, the convex conjugate of $\psi_{\text{Lap},\epsilon}$ is

$$ \begin{aligned} \psi_{\text{Lap},\epsilon}^{*}(x) &= f(\lambda(x)) = \sqrt{1+(x\epsilon)^2}-1 + \log\left(1-\frac{1}{(x\epsilon)^2}\left(\sqrt{1+(x\epsilon)^2}-1\right)^2\right) \\ &= \sqrt{1+(x\epsilon)^2}-1 + \log\left(\frac{2}{(x\epsilon)^2}\left(\sqrt{1+(x\epsilon)^2}-1\right)\right). \end{aligned} $$

This concludes the proof. $\square$

**Test Martingale for Cumulative Laplace Observations** Let $\epsilon > 0$ and $S_t = \sum_{s \in [t]} Y_s$ where $Y_s \sim \text{Lap}(1/\epsilon)$ are i.i.d. observations. Let us define

$$ \forall \lambda \in (0, \epsilon), \quad M_t(\lambda) := \exp(\lambda S_t - t\psi_{\text{Lap},\epsilon}(\lambda)). $$

It is direct to see that $M_0(\lambda) = 0$ almost surely and

$$ \mathbb{E}[M_t(\lambda) | \mathcal{F}_{t-1}] = M_{t-1}(\lambda)\mathbb{E}_{X \sim \text{Lap}(1/\epsilon)}[\exp(\lambda X - \psi_{\text{Lap},\epsilon}(\lambda))] = M_{t-1}(\lambda). $$

Therefore, $M_t(\lambda)$ is a test martingale. Using Ville's inequality [Ville, 1939] yields that

$$ \forall \delta \in (0, 1), \forall \lambda \in (0, \epsilon), \quad \mathbb{P}(\exists t \in \mathbb{N}, \lambda S_t - t\psi_{\text{Lap},\epsilon}(\lambda) \ge \log(1/\delta)) \le \delta. \quad (26) $$

**Time Uniform Tails Concentration** Lemma 14 controls the deviation of the process on slices of time.

**Lemma 14.** Let $\epsilon > 0$ and $S_t = \sum_{s \in [t]} Y_s$ where $Y_s \sim \text{Lap}(1/\epsilon)$ are i.i.d. observations. Let $N > 0$. For all $x > 0$, there exists $\lambda(x)$ such that for all $t \ge N$,

$$ \{S_t \ge tx\} \subseteq \{\lambda(x)S_t - t\psi_{\text{Lap},\epsilon}(\lambda(x)) \ge Nh(\epsilon x)\}, $$

where $\lambda(x)$ as in Lemma 13 and $h$ as in Eq. (31).

**Proof.** Using Lemma 13, we obtain $\lambda(x) \in (0, \epsilon)$ and $\psi_{\text{Lap},\epsilon}^*(x) = h(\epsilon x) > 0$, hence $t\psi_{\text{Lap},\epsilon}^*(x) \ge N\psi_{\text{Lap},\epsilon}^*(x)$ for $t \ge N$. Then, direct computations yield

$$ \begin{aligned} S_t \ge tx &\implies \lambda(x)S_t - t\psi_{\text{Lap},\epsilon}(\lambda(x)) \ge t(x\lambda(x) - \psi_{\text{Lap},\epsilon}(\lambda(x))) = t\psi_{\text{Lap},\epsilon}^*(x) \\ &\implies \lambda S_t - t\psi_{\text{Lap},\epsilon}(\lambda) \ge N\psi_{\text{Lap},\epsilon}^*(x) = Nh(\epsilon x). \end{aligned} $$

This concludes the proof. $\square$

Lemma 15 gives time-uniform tails concentration for the cumulative sum of i.i.d. Laplace observations. It is obtained by applying Lemma 14 on slices of time with geometric growth rate.

**Lemma 15.** Let $\delta \in (0, 1)$. Let $\gamma > 0$, $s > 1$ and $\zeta$ be the Riemann $\zeta$ function. Let $h^{-1}$ be the inverse of $h$ defined as in Eq. (31), which is well-defined by Lemma 28. Let $\epsilon > 0$ and $S_t = \sum_{s \in [t]} Y_s$ where $Y_s \sim \text{Lap}(1/\epsilon)$ are i.i.d. observations. Then,

$$ \begin{aligned} \mathbb{P}\left(\exists t \in \mathbb{N}, S_t \ge \frac{t}{\epsilon}h^{-1}\left(\frac{1+\gamma}{t}\left(\log\left(\frac{\zeta(s)}{\delta}\right) + s\log(1+\log_{1+\gamma}t)\right)\right)\right) \le \delta, \\ \mathbb{P}\left(\exists t \in \mathbb{N}, S_t \le -\frac{t}{\epsilon}h^{-1}\left(\frac{1+\gamma}{t}\left(\log\left(\frac{\zeta(s)}{\delta}\right) + s\log(1+\log_{1+\gamma}t)\right)\right)\right) \le \delta. \end{aligned} $$

**Proof.** Let us define the geometric grid $N_i = (1+\gamma)^{i-1}$, hence we have $\mathbb{N} = \bigcup_{i \in \mathbb{N}}[N_i, N_{i+1})$. For all $i \in \mathbb{N}$, let $x_i(\delta) > 0$ to be defined later, and $\lambda(x_i(\delta))$ as in Lemma 14. For all $t \in \mathbb{N}$, let $g(t, \delta)$ to be defined later such that $g(t, \delta) \ge x_i(\delta)$ for $t \in [N_i, N_{i+1})$. Using Lemma 14 with $x_i(\delta) > 0$ and $g(t, \delta) \ge x_i(\delta)$ for $t \in [N_i, N_{i+1})$, a union bound yields that

$$ \mathbb{P}(\exists t \in \mathbb{N}, S_t \ge tg(t, \delta)) $$
$$
\begin{align*}
&\le \sum_{i \in \mathbb{N}} \mathbb{P}(\exists t \in [N_i, N_{i+1}) : S_t \ge t x_i(\delta)) \\
&\le \sum_{i \in \mathbb{N}} \mathbb{P}(\exists t \in [N_i, N_{i+1}) : \lambda(x_i(\delta)) S_t - t \psi_{\text{Lap},\epsilon}(\lambda(x_i(\delta))) \ge N_i h(\epsilon x_i(\delta))) \\
&\le \sum_{i \in \mathbb{N}} e^{-N_i h(\epsilon x_i(\delta))},
\end{align*}
$$

where the last inequality uses Ville's inequality as in Eq. (26) for all $i \in \mathbb{N}$. Let us define

$$
\begin{align*}
g(t, \delta) &= \frac{1}{\epsilon} h^{-1} \left( \frac{1 + \gamma}{t} \left( \log \left( \frac{\zeta(s)}{\delta} \right) + s \log (1 + \log_{1+\gamma}(t)) \right) \right), \\
x_i(\delta) &= \frac{1}{\epsilon} h^{-1} \left( \frac{1}{N_i} \log \left( \frac{i^s \zeta(s)}{\delta} \right) \right).
\end{align*}
$$

Using Lemma 28, we obtain that $x_i(\delta) > 0$ and that $h^{-1}$ is increasing on $\mathbb{R}_+^*$. Using $t \in [N_i, N_{i+1})$ and $i = 1 + \log_{1+\gamma} N_i$, we obtain

$$
\begin{align*}
g(t, \delta) &\ge \frac{1}{\epsilon} h^{-1} \left( \frac{1}{N_i} \left( \log \left( \frac{\zeta(s)}{\delta} \right) + s \log (1 + \log_{1+\gamma}(t)) \right) \right) \\
&\ge \frac{1}{\epsilon} h^{-1} \left( \frac{1}{N_i} \log \left( \frac{i^s \zeta(s)}{\delta} \right) \right) = x_i(\delta).
\end{align*}
$$

Therefore, we have

$$
\mathbb{P}(\exists t \in \mathbb{N}, S_t \geq tg(t, \delta)) \leq \sum_{i \in \mathbb{N}} e^{-N_i h(\epsilon x_i(\delta))} \leq \frac{\delta}{\zeta(s)} \sum_{i \in \mathbb{N}} \frac{1}{i^s} = \delta.
$$

This concludes the proof of the first result.

By symmetry of the Lap(1/ε) around zero, the cumulative sum of i.i.d. observations is symmetric around zero. Combining the first result with the symmetry around zero yields the second result. □

**Fixed Time Tails Concentration** When the time is fixed and not random, there is no need to consider slices of time and we can directly control the deviation of the process.

**Lemma 16.** Let $\epsilon > 0$ and $S_t = \sum_{s \in [t]} Y_s$ where $Y_s \sim \text{Lap}(1/\epsilon)$ are i.i.d. observations. Let $h$ as in Eq. (31). Then,

$$
\begin{array}{ll}
\forall t \in \mathbb{N}, \forall x > 0, & \mathbb{P}(S_t \geq tx) \leq \exp(-th(\epsilon x)), \\
\forall t \in \mathbb{N}, \forall x > 0, & \mathbb{P}(S_t \leq -tx) \leq \exp(-th(\epsilon x)).
\end{array}
$$

*Proof.* The first result can be obtained with the same manipulation as in the proof of Lemma 15, i.e., combining Ville's inequality in Eq. (26) with Lemma 14 at $N = t$.

By symmetry of the Lap(1/ϵ) around zero, the cumulative sum of i.i.d. observations is symmetric around zero. Combining the first result with the symmetry around zero yields the second result. □

F.5 Fixed Time Tails Concentration of Cumulative Bernoulli Distributions

The fixed time upper and lower tail concentration of cumulative Bernoulli distributions are well-studied. Using the Chernoff method yields Lemma 17, whose proof is omitted since it is a classic result.

**Lemma 17 (Chernoff Tail Bound for Bernoulli Distributions [Boucheron et al., 2013])**. Let $\mu \in (0, 1)$ and $Z_t = \sum_{s \in [t]} X_s$ where $X_s \sim \text{Ber}(\mu)$ are i.i.d. observations. Then,

$$
\begin{align*}
\forall t \in \mathbb{N}, \forall x \in (\mu, 1), \quad & \mathbb{P}(Z_t \geq tx) \leq \exp(-tkl(x, \mu)), \\
\forall t \in \mathbb{N}, \forall x \in (0, \mu), \quad & \mathbb{P}(Z_t \leq tx) \leq \exp(-tkl(x, \mu)).
\end{align*}
$$
## F.6 Fixed Time Tails Concentration for a Convolution between Bernoulli and Laplace Distributions

We provide upper (Lemma 18) and lower (Lemma 19) tail concentrations for a sum (i.e., convolution) between independent Bernoulli and Laplace i.i.d. observations for a fixed time.

**Fixed Time Upper Tail Concentration** Lemma 18 shows an upper tail concentration on the sum (i.e., convolution) between independent Bernoulli and Laplace i.i.d. observations.

**Lemma 18.** Let $\mu \in (0, 1)$ and $Z_t = \sum_{s \in [t]} X_s$ where $X_s \sim \text{Ber}(\mu)$ are i.i.d. observations. Let $(n_t)_{t \in \mathbb{N}}$ be a piece-wise constant increasing function from $\mathbb{N}$ to $\mathbb{N}$. Let $\epsilon > 0$ and $S_t = \sum_{s \in [n_t]} Y_s$ where $Y_s \sim \text{Lap}(1/\epsilon)$ are i.i.d. observations. Then,

$$ \forall t \in \mathbb{N}, \forall x > 0, \quad \mathbb{P}(Z_t + S_t \ge t(\mu + x)) \le f\left(t\tilde{d}_{\epsilon}^{-}(\mu + x, \mu, t/n_t)\right), $$

where $f$ is defined in Eq. (24) and $\tilde{d}_{\epsilon}^{-}$ is defined in Eq. (32).

*Proof.* Let $t \in \mathbb{N}$ and $x > 0$. Combining Lemmas 16 and 17, we obtain, for all $x > 0$ and all $z \in (\mu, \min\{1, x + \mu\})$,

$$ -\frac{1}{t} \log (\bar{G}_t(tz) \bar{F}_{n_t}(t(x + \mu - z))) \ge \text{kl}(z, \mu) + \frac{n_t}{t} h \left( \frac{t}{n_t} \epsilon(x + \mu - z) \right), $$

where we used that $x + \mu - z > 0$. Taking the infimum on $(\mu, \min\{1, x + \mu\})$ on both sides and using that $[x + \mu]_0^1 = \min\{1, x + \mu\} > \mu$, we obtain

$$ \inf_{z \in (\mu, \min\{1, x+\mu\})} \left\{ -\frac{1}{t} \log (\bar{G}_t(tz) \bar{F}_{n_t}(t(x + \mu - z))) \right\} \ge \tilde{d}_{\epsilon}^{-}(\mu + x, \mu, t/n_t), $$

where $\tilde{d}_{\epsilon}^{-}$ is defined in Eq. (32). Since $f$ is decreasing on $\mathbb{R}_+$ (Lemma 11), using Lemma 12 yields

$$ \mathbb{P}(Z_t + S_t \ge t(x + \mu)) \le f\left(t\tilde{d}_{\epsilon}^{-}(\mu + x, \mu, t/n_t)\right). $$

which concludes the proof. $\square$

**Fixed Time Lower Tail Concentration** Lemma 19 shows a lower tail concentration on the sum (i.e., convolution) between independent Bernoulli and Laplace i.i.d. observations.

**Lemma 19.** Let $\mu \in (0, 1)$ and $Z_t = \sum_{s \in [t]} X_s$ where $X_s \sim \text{Ber}(\mu)$ are i.i.d. observations. Let $(n_t)_{t \in \mathbb{N}}$ be a piece-wise constant increasing function from $\mathbb{N}$ to $\mathbb{N}$. Let $\epsilon > 0$ and $S_t = \sum_{s \in [n_t]} Y_s$ where $Y_s \sim \text{Lap}(1/\epsilon)$ are i.i.d. observations. Then,

$$ \forall t \in \mathbb{N}, \forall x > 0, \quad \mathbb{P}(Z_t + S_t \le t(\mu - x)) \le f\left(t\tilde{d}_{\epsilon}^{+}(\mu - x, \mu, t/n_t)\right), $$

where $f$ is defined in Eq. (24) and $\tilde{d}_{\epsilon}^{+}$ is defined in Eq. (32).

*Proof.* Let $t \in \mathbb{N}$ and $x > 0$. Combining Lemmas 16 and 17, we obtain, for all $x > 0$ and all $z \in (\max\{0, \mu - x\}, \mu)$,

$$ -\frac{1}{t} \log (G_t(tz) F_{n_t}(t(\mu - x - z))) \ge \text{kl}(z, \mu) + \frac{n_t}{t} h \left( \frac{t}{n_t} \epsilon(z + x - \mu) \right), $$

where we used that $\mu - x - z < 0$. Taking the infimum on $z \in (\max\{0, \mu - x\}, \mu)$ on both sides and using that $[\mu - x]_0^1 = \max\{0, \mu - x\} < \mu$, we obtain

$$ \inf_{z \in (\max\{0, \mu-x\}, \mu)} \left\{ -\frac{1}{t} \log (G_t(tz) F_{n_t}(t(\mu - x - z))) \right\} \ge \tilde{d}_{\epsilon}^{+}(\mu - x, \mu, t/n_t), $$

where $\tilde{d}_{\epsilon}^{+}$ is defined in Eq. (32). Since $f$ is decreasing on $\mathbb{R}_+$ (Lemma 11), using Lemma 12 yields

$$ \mathbb{P}(Z_t + S_t \ge t(\mu - x)) \le f\left(t\tilde{d}_{\epsilon}^{+}(\mu - x, \mu, t/n_t)\right), $$

which concludes the proof. $\square$
### F.7 Geometric Grid Time Uniform Tails Concentration for a Convolution between Bernoulli and Laplace Distributions

We provide upper (Lemma 20) and lower (Lemma 21) tail concentrations for a sum (i.e., convolution) between independent Bernoulli and Laplace i.i.d. observations that holds time uniformly on a geometric grid.

**Geometric Grid Time Uniform Upper Tail Concentration** Lemma 20 gives a threshold ensuring that a geometric grid time uniform upper tail concentration holds with probability at least $1 - \delta$.

**Lemma 20.** Let $\delta \in (0, 1)$. Let $(\tilde{\mu}_n, \tilde{N}_n, k_n)$ are given by $GPE_\eta(\epsilon)$. Let $s > 1$ and $\zeta$ be the Riemann $\zeta$ function. Let $\overline{W}_{-1}(x) = -W_{-1}(-e^{-x})$ for all $x \ge 1$, where $W_{-1}$ is the negative branch of the Lambert W function. It satisfies $\overline{W}_{-1}(x) \approx x + \log x$, see Lemma 52. Let us define

$$c(k, \delta) = \overline{W}_{-1}(\log(1/\delta) + s \log(k) + \log(\zeta(s)) + 3 - 2 \log 2) - 3 + 2 \log 2. \quad (27)$$

For all $a \in [K]$, let us define

$$\mathcal{E}_{\delta,a,-} = \{ \forall n \in \mathbb{N}, \tilde{N}_{n,a} \tilde{d}_{\epsilon}^{-} (\tilde{\mu}_{n,a}, \mu_a, \tilde{N}_{n,a}/k_{n,a}) \le c(k_{n,a}, \delta) \}, \quad (28)$$

where $\tilde{d}_{\epsilon}^{-}$ is defined in Eq. (32). Then, we have $\mathbb{P}_{\nu_{\pi}}(\mathcal{E}_{\delta,a,-}^{\mathcal{C}}) \le \delta$ for all $a \in [K]$.

*Proof.* Let us define the geometric grid $N_i = (1 + \eta)^{i-1}$, hence we have $\mathbb{N} = \bigcup_{i \in \mathbb{N}} [N_i, N_{i+1})$. Let $a \in [K]$. If $\tilde{N}_{n,a} \in [N_i, N_{i+1})$, then we have $\tilde{N}_{n,a} = \lceil N_i \rceil$ and $k_{n,a} = i$. By union bound, we obtain

$$\begin{aligned} \mathbb{P}_{\nu_{\pi}}(\mathcal{E}_{\delta,a,-}^{\mathcal{C}}) &= \mathbb{P}_{\nu_{\pi}}\left(\exists n \in \mathbb{N}, \tilde{N}_{n,a} \tilde{d}_{\epsilon}^{-}(\tilde{\mu}_{n,a}, \mu_a, \tilde{N}_{n,a}/k_{n,a}) \ge c(k_{n,a}, \delta)\right) \\ &\le \sum_{i \in \mathbb{N}} \mathbb{P}_{\nu_{\pi}}\left(\exists i \in \mathbb{N}, (\tilde{N}_{n,a}, k_{n,a}) = (\lceil N_i \rceil, i) \wedge \tilde{N}_{n,a} \tilde{d}_{\epsilon}^{-}(\tilde{\mu}_{n,a}, \mu_a, \tilde{N}_{n,a}/k_{n,a}) \ge c(k_{n,a}, \delta)\right) \\ &= \sum_{i \in \mathbb{N}} \mathbb{P}\left(\lceil N_i \rceil \tilde{d}_{\epsilon}^{-}((Z_{\lceil N_i \rceil} + S_i)/\lceil N_i \rceil, \mu_a, \lceil N_i \rceil/i) \ge c(i, \delta)\right), \end{aligned}$$

where $Z_{\lceil N_i \rceil}$ is the cumulative sum of $\lceil N_i \rceil$ i.i.d. observations from Ber($\mu_a$) and $S_i$ is the cumulative sum of $i$ i.i.d. observations from Lap($1/\epsilon$).

For all $i \in \mathbb{N}$, let $x_i > 0$ be the unique solution of $\lceil N_i \rceil \tilde{d}_{\epsilon}^{-}(x + \mu_a, \mu_a, \lceil N_i \rceil/i) = c(i, \delta)$, which exists by Lemma 33. Then, we obtain

$$\begin{aligned} & \mathbb{P}\left(\lceil N_i \rceil \tilde{d}_{\epsilon}^{-}((Z_{\lceil N_i \rceil} + S_i)/\lceil N_i \rceil, \mu_a, \lceil N_i \rceil/i) \ge c(i, \delta)\right) \\ &= \mathbb{P}\left(\tilde{d}_{\epsilon}^{-}((Z_{\lceil N_i \rceil} + S_i)/\lceil N_i \rceil, \mu_a, \lceil N_i \rceil/i) \ge \tilde{d}_{\epsilon}^{-}(x_i + \mu_a, \mu_a, \lceil N_i \rceil/i)\right) \\ & \le \mathbb{P}(Z_{\lceil N_i \rceil} + S_i \ge \lceil N_i \rceil(x_i + \mu_a)) \le f\left(\lceil N_i \rceil \tilde{d}_{\epsilon}^{-}(x_i + \mu_a, \mu_a, \lceil N_i \rceil/i)\right) = f(c(i, \delta)), \end{aligned}$$

where $f(x) := (x + 3 - \log 2) \exp(-x)$ for all $x \ge 0$. The first and the last equalities are obtained by definition of $x_i$, i.e., $\lceil N_i \rceil \tilde{d}_{\epsilon}^{-}(x + \mu_a, \mu_a, \lceil N_i \rceil/i) = c(i, \delta)$. The first inequality is obtained by using Lemma 34, and the second inequality is obtained by using Lemma 18. Using Lemma 11 yields

$$f(x) \le \delta \iff \overline{W}_{-1}(\log(1/\delta) + 3 - \log 2) - 3 + \log 2 \le x.$$

Taking

$$c(i, \delta) = \overline{W}_{-1}(\log(i^s \zeta(s)/\delta) + 3 - \log 2) - 3 + \log 2,$$

we can conclude the proof since $\mathbb{P}_{\nu_{\pi}}(\mathcal{E}_{\delta,a,-}^{\mathcal{C}}) \le \sum_{i \in \mathbb{N}} f(c(i, \delta)) \le \sum_{i \in \mathbb{N}} \frac{\delta}{\zeta(s)^{i^s}} \le \delta$. $\square$

**Geometric Grid Time Uniform Lower Tail Concentration** Lemma 21 gives a threshold ensuring that a geometric grid time uniform lower tail concentration holds with probability at least $1 - \delta$.