**Lemma 21.** Let $\delta \in (0, 1)$. Let $(\tilde{\mu}_n, \tilde{N}_n, k_n)$ are given by $GPE_\eta(\epsilon)$. Let $c$ as in Eq. (27). For all $a \in [K]$, let us define

$$ \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 c(k_{n,a}, \delta) \right\}, \quad (29) $$

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} = [N_i]$ 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}) = ([N_i], 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( [N_i] \tilde{d}_{\epsilon}^{+} ((Z_{\lceil N_i \rceil} + S_i)/[N_i], \mu_a, [N_i]/i) \ge c(i, \delta) \right), \end{aligned} $$

where $Z_{\lceil N_i \rceil}$ is the cumulative sum of $[N_i]$ 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 $[N_i] \tilde{d}_{\epsilon}^{+} (\mu_a - x, \mu_a, [N_i]/i) = c(i, \delta)$, which exists by Lemma 33. Then, we obtain

$$ \begin{aligned} \mathbb{P} \left( [N_i] \tilde{d}_{\epsilon}^{+} \left( \frac{(Z_{\lceil N_i \rceil} + S_i)}{[N_i]}, \mu_a, \frac{[N_i]}{i} \right) \ge c(i, \delta) \right) &= \mathbb{P} \left( \tilde{d}_{\epsilon}^{+} \left( \frac{(Z_{\lceil N_i \rceil} + S_i)}{[N_i]}, \mu_a, \frac{[N_i]}{i} \right) \ge \tilde{d}_{\epsilon}^{+} (\mu_a - x_i, \mu_a, \frac{[N_i]}{i}) \right) \\ &\le \mathbb{P} \left( Z_{\lceil N_i \rceil} + S_i \le [N_i] (\mu_a - x_i) \right) \le f \left( [N_i] \tilde{d}_{\epsilon}^{+} (\mu_a - x_i, \mu_a, \frac{[N_i]}{i}) \right) = f(c(i, \delta)) \le \frac{\delta}{\zeta(s)i^s} \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., $[N_i] \tilde{d}_{\epsilon}^{+} (\mu_a - x, \mu_a, [N_i]/i) = c(i, \delta)$. The first inequality is obtained by using Lemma 34, and the second inequality is obtained by using Lemma 19. The last inequality uses the same derivations based on Lemma 11 as in the proof of Lemma 20 by taking

$$ c(i, \delta) = \bar{W}_{-1} \left( \log \left( \frac{i^s \zeta(s)}{\delta} \right) + 3 - \log 2 \right) - 3 + \log 2. $$

This concludes the proof since $\mathbb{P}_{\nu\pi}(\mathcal{E}_{\delta,a,-}^{\mathcal{C}}) \le \sum_{i \in \mathbb{N}} \frac{\delta}{\zeta(s)i^s} \le \delta$. $\square$

# G Divergence, Transportation Cost and Characteristic Time

Appendix G is organized as follow. First, we derive regularity properties for the signed (modified) divergences $d_{\epsilon}^{\pm}$ (Appendix G.1) and $\tilde{d}_{\epsilon}^{\pm}$ (Appendix G.1.1). Second, we derive regularity properties the (modified) transportation costs $W_{\epsilon,a,b}$ (Appendix G.2) and $\bar{W}_{\epsilon,a,b}$ (Appendix G.2.1) for a pair of arms $(a, b)$. Third, we study the characteristic time for $\epsilon$-global DP BAI (Appendix G.3).

## G.1 Signed Divergence

Recall $[x]_0^1 := \max\{0, \min\{1, \lambda\}\}$ and

$$ \forall (\lambda, \mu) \in (0, 1)^2, \quad \text{kl}(\lambda, \mu) := \lambda \log \left( \frac{\lambda}{\mu} \right) + (1 - \lambda) \log \left( \frac{1 - \lambda}{1 - \mu} \right) $$

where kl is infinity when $\{\mu, \lambda\} \cap \{0, 1\} \neq \emptyset$. The signed divergences $d_{\epsilon}^{\pm}$ are defined in Eq. (3), i.e.,

$$ \begin{aligned} \forall (\lambda, \mu) \in \mathbb{R} \times [0, 1], \quad d_{\epsilon}^{-} (\lambda, \mu) &:= 1 (\mu < [\lambda]_0^1) \inf_{z \in [\mu, [\lambda]_0^1]} \{\text{kl}(z, \mu) + \epsilon([\lambda]_0^1 - z)\}, \\ d_{\epsilon}^{+} (\lambda, \mu) &:= 1 (\mu > [\lambda]_0^1) \inf_{z \in [[\lambda]_0^1, \mu]} \{\text{kl}(z, \mu) + \epsilon(z - [\lambda]_0^1)\}. \end{aligned} $$

Lemma 22 relates $d_{\epsilon}$ and $d_{\epsilon}^{\pm}$.
**Lemma 22.** Let $d_{\epsilon}^{\pm}$ and $d_{\epsilon}$ as in Eq. (3) and (1). Let $(\kappa, \nu) \in \mathcal{F}^2$ with means $(\lambda, \mu) \in (0, 1)^2$. Then,

$$d_{\epsilon}(\kappa, \nu) = \begin{cases} 0 & \text{if } \lambda = \mu \\ d_{\epsilon}^{-}(\lambda, \mu) & \text{if } \mu < \lambda \\ d_{\epsilon}^{+}(\lambda, \mu) & \text{if } \mu > \lambda \end{cases}.$$

*Proof.* When $\lambda = \mu$, we have $d_{\epsilon}(\kappa, \nu) = 0$ by taking $\varphi = \nu$ and using the non-negativity of $d_{\epsilon}$.

Let $\varphi \in \mathcal{F}$ with mean $z \in (0, 1)$. When $\mu < \lambda$, we have

$$d_{\epsilon}(\kappa, \nu) = \min\left\{ \begin{array}{l} \inf_{z \in (0, \mu)} \{\mathrm{kl}(z, \mu) + \epsilon(\lambda - z)\}, \quad \inf_{z \in [\lambda, \lambda]} \{\mathrm{kl}(z, \mu) + \epsilon(\lambda - z)\}, \\ \\ \inf_{z \in (\lambda, 1)} \{\mathrm{kl}(z, \mu) + \epsilon(z - \lambda)\} \\ \\ \inf_{z \in [\lambda, \lambda]} \{\mathrm{kl}(z, \mu) + \epsilon(\lambda - z)\} = d_{\epsilon}^{-}(\lambda, \mu), \end{array} \right.$$

where we partitioned $(0, 1)$ and used that $(1) z \mapsto \mathrm{kl}(z, \mu) + \epsilon(z - \lambda)$ is increasing on $(\lambda, 1)$, hence the infimum on this interval is achieved at $\lambda$, and $(2) z \mapsto \mathrm{kl}(z, \mu) + \epsilon(\lambda - z)$, is decreasing on $(0, \mu)$, hence the infimum on this interval is achieved at $\mu$.

When $\mu > \lambda$, we have

$$d_{\epsilon}(\kappa, \nu) = \min\left\{ \begin{array}{l} \inf_{z \in (0, \lambda)} \{\mathrm{kl}(z, \mu) + \epsilon(\lambda - z)\}, \quad \inf_{z \in [\lambda, \lambda]} \{\mathrm{kl}(z, \mu) + \epsilon(z - \lambda)\}, \\ \\ \inf_{z \in (\lambda, 1)} \{\mathrm{kl}(z, \mu) + \epsilon(z - \lambda)\} \\ \\ \inf_{z \in [\lambda, \lambda]} \{\mathrm{kl}(z, \mu) + \epsilon(z - \lambda)\} = d_{\epsilon}^{+}(\lambda, \mu), \end{array} \right.$$

where we partitioned $(0, 1)$ and used that $(1) z \mapsto \mathrm{kl}(z, \mu) + \epsilon(z - \lambda)$ is increasing on $(\mu, 1)$, hence the infimum on this interval is achieved at $\mu$, and $(2) z \mapsto \mathrm{kl}(z, \mu) + \epsilon(\lambda - z)$, is decreasing on $(0, \lambda)$, hence the infimum on this interval is achieved at $\lambda$. $\square$

Lemma 23 shows a strong link between $d_{\epsilon}^{\pm}$. This symmetry property can be used to carry regularity properties from $d_{\epsilon}^{+}$ to $d_{\epsilon}^{-}$, and vice versa.

**Lemma 23.** Let $d_{\epsilon}^{\pm}$ as in Eq. 3. For all $\mu \in [0, 1]$ and all $\lambda \in \mathbb{R}$,

$$d_{\epsilon}^{+}(1 - \lambda, 1 - \mu) = d_{\epsilon}^{-}(\lambda, \mu) \quad \text{and} \quad d_{\epsilon}^{-}(1 - \lambda, 1 - \mu) = d_{\epsilon}^{+}(\lambda, \mu).$$

*Proof.* By definitions and change of variable $\tilde{z} = 1 - z$ and $\mathrm{kl}(1 - \tilde{z}, 1 - \mu) = \mathrm{kl}(\tilde{z}, \mu)$, we obtain

$$\begin{align*} d_{\epsilon}^{+}(1 - \lambda, 1 - \mu) &= 1 (\mu < [\lambda]_{0}^{1}) \inf_{z \in [1 - [\lambda]_{0}^{1}, 1 - \mu]} \{\mathrm{kl}(z, 1 - \mu) + \epsilon(\max\{0, \min\{1, \lambda\} - (1 - z)\})\} \\ &= 1 (\mu < [\lambda]_{0}^{1}) \inf_{\tilde{z} \in [\mu, [\lambda]_{0}^{1}]} \{\mathrm{kl}(1 - \tilde{z}, 1 - \mu) + \epsilon(\max\{0, \min\{1, \lambda\} - \tilde{z}\})\} \\ &= 1 (\mu < [\lambda]_{0}^{1}) \inf_{\tilde{z} \in [\mu, [\lambda]_{0}^{1}]} \{\mathrm{kl}(\tilde{z}, \mu) + \epsilon(\max\{0, \min\{1, \lambda\} - \tilde{z}\})\} = d_{\epsilon}^{-}(\lambda, \mu). \end{align*}$$

The second equality is a consequence of the first. $\square$

Lemma 24 gathers regularity properties on the functions $g_{\epsilon}^{\pm}$ that appear in the explicit solutions of $d_{\epsilon}^{\pm}$, as shown below. Intuitively, those functionals govern locally the separation between the low privacy regime where $d_{\epsilon}^{\pm}$ is equals to the kl and the high privacy regime where the divergence has to be modified to account for the privacy budget $\epsilon$.

**Lemma 24.** Let $\epsilon > 0$. Let $g_{\epsilon}^{\pm}$ defined as

$$\forall x \in [0, 1], \quad g_{\epsilon}^{+}(x) := \frac{x}{x(1 - e^{\epsilon}) + e^{\epsilon}} \quad \text{and} \quad g_{\epsilon}^{-}(x) := \frac{xe^{\epsilon}}{x(e^{\epsilon} - 1) + 1}. \qquad (30)$$

On $[0, 1]$, the function $g_{\epsilon}^{+}$ is twice continuously differentiable, increasing and strictly convex. It satisfies $g_{\epsilon}^{+}(0) = 0$, $g_{\epsilon}^{+}(1) = 1$ and $g_{\epsilon}^{+}(x) < x$ on $(0, 1)$. On $[0, 1]$, the function $g_{\epsilon}^{-}$ is twice continuously differentiable, increasing and strictly concave. It satisfies $g_{\epsilon}^{-}(0) = 0$, $g_{\epsilon}^{-}(1) = 1$ and $g_{\epsilon}^{-}(x) > x$ on $(0, 1)$. For all $x \in [0, 1]$, we have $g_{\epsilon}^{+}(g_{\epsilon}^{-}(x)) = x$ and $g_{\epsilon}^{-}(1 - x) + g_{\epsilon}^{+}(x) = 1$. For all $x \in [0, 1]$, we have $\lim_{\epsilon \to 0} g_{\epsilon}^{+}(x) = \lim_{\epsilon \to 0} g_{\epsilon}^{-}(x) = x$; it satisfies $\lim_{\epsilon \to +\infty} g_{\epsilon}^{-}(x) = 1$ if $x \neq 0$ and $\lim_{\epsilon \to +\infty} g_{\epsilon}^{+}(x) = 0$ if $x \neq 1$.
**Proof.** Using that $e^{\epsilon} > 1$, direct computations yield that, for all $x \in [0, 1]$,

$$ (g_{\epsilon}^{+})'(x) = \frac{e^{\epsilon}}{(x(1 - e^{\epsilon}) + e^{\epsilon})^2} > 0 \quad \text{and} \quad (g_{\epsilon}^{+})''(x) = -2 \frac{e^{\epsilon}(1 - e^{\epsilon})}{(x(1 - e^{\epsilon}) + e^{\epsilon})^2} > 0, $$

$$ (g_{\epsilon}^{-})'(x) = \frac{e^{\epsilon}}{(x(e^{\epsilon} - 1) + 1)^2} > 0 \quad \text{and} \quad (g_{\epsilon}^{-})''(x) = -2 \frac{e^{\epsilon}(e^{\epsilon} - 1)}{(x(e^{\epsilon} - 1) + 1)^3} < 0. $$

Therefore, $g_{\epsilon}^{+}$ is twice continuously differentiable, increasing and strictly convex on $[0, 1]$ and $g_{\epsilon}^{-}$ is twice continuously differentiable, increasing and strictly concave on $[0, 1]$. It is direct to see that $g_{\epsilon}^{+}(0) = g_{\epsilon}^{-}(0) = 0$ and $g_{\epsilon}^{+}(1) = g_{\epsilon}^{-}(1) = 1$. Since they are strictly convex and strictly concave, we obtain $g_{\epsilon}^{+}(x) < x$ and $g_{\epsilon}^{-}(x) > x$ for all $x \in (0, 1)$. It is direct to see that, for all $x \in [0, 1]$, we have $g_{\epsilon}^{+}(g_{\epsilon}^{-}(x)) = x$ and $1 - g_{\epsilon}^{+}(x) = g_{\epsilon}^{-}(1 - x)$. It is direct to see that, $\lim_{\epsilon \to 0} g_{\epsilon}^{+}(x) = \lim_{\epsilon \to 0} g_{\epsilon}^{-}(x) = x$ for all $x \in [0, 1]$, and $\lim_{\epsilon \to +\infty} g_{\epsilon}^{+}(x) = \lim_{\epsilon \to +\infty} g_{\epsilon}^{-}(x) = 1$ if $x \neq 1$ and $\lim_{\epsilon \to +\infty} g_{\epsilon}^{-}(x) = 1$ if $x \neq 0$. $\square$

**Lemma 25.** Let $d_{\epsilon}^{+}$ as in Eq. (3), and $g_{\epsilon}^{\pm}$ as in Eq. (30). For all $\mu \in [0, 1]$ and $\lambda \in \mathbb{R}$, we have

$$ d_{\epsilon}^{+}(\lambda, \mu) = \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] \\ \text{kl}(\lambda, \mu) & \text{if } \lambda \in (0, 1) \wedge \mu \in ([\lambda]_{0}^{1}, g_{\epsilon}^{-}([\lambda]_{0}^{1})] \end{cases}. $$

The function $(\lambda, \mu) \mapsto d_{\epsilon}^{+}(\lambda, \mu)$ is jointly continuous on $\mathbb{R} \times [0, 1]$. For all $\mu \in [0, 1]$, the function $\lambda \mapsto d_{\epsilon}^{+}(\lambda, \mu)$ is constant on $(-\infty, 0]$ and on $[1, +\infty)$. Then,

$$ \forall \lambda \in (0, 1), \forall \mu \in [0, 1], \quad d_{\epsilon}^{+}(\lambda, \mu) = \begin{cases} 0 & \text{if } \mu \in [0, \lambda] \\ \text{kl}(\lambda, \mu) & \text{if } \mu \in (\lambda, g_{\epsilon}^{-}(\lambda)) \\ -\log(1 - \mu(1 - e^{-\epsilon})) - \epsilon\lambda & \text{if } \mu \in (g_{\epsilon}^{-}(\lambda), 1] \end{cases}. $$

For all $\mu \in [0, 1]$, the function $\lambda \mapsto d_{\epsilon}^{+}(\lambda, \mu)$ is continuously differentiable, positive, decreasing and convex on $(0, \mu)$; it is affine with negative slope $-\epsilon$ on $(0, g_{\epsilon}^{+}(\mu))$ and twice continuously differentiable and strictly convex on $(g_{\epsilon}^{+}(\mu), \mu)$.

For all $\lambda \in (0, 1)$, the function $\mu \mapsto d_{\epsilon}^{+}(\lambda, \mu)$ is positive, three times differentiable with continuous first derivative, increasing and strictly convex on $(\lambda, 1]$; its second derivative is discontinuous at $g_{\epsilon}^{-}(\lambda)$ with gap $\frac{\partial^2 d_{\epsilon}^{+}}{\partial \mu^2}(\lambda, g_{\epsilon}^{-}(\lambda)) - \lim_{\mu \to g_{\epsilon}^{-}(\lambda)+} \frac{\partial^2 d_{\epsilon}^{+}}{\partial \mu^2}(\lambda, \mu) > 0$. Moreover, we have

$$ \forall \mu \in (\lambda, 1], \quad \frac{\partial d_{\epsilon}^{+}}{\partial \mu}(\lambda, \mu) = \begin{cases} \frac{1 - e^{-\epsilon}}{1 - \mu(1 - e^{-\epsilon})} & \text{if } \mu \in (g_{\epsilon}^{-}(\lambda), 1] \\ \frac{\mu - \lambda}{\mu(1 - \mu)} & \text{if } \mu \in (\lambda, g_{\epsilon}^{-}(\lambda)] \end{cases}. $$

The function $d_{\epsilon}^{+}$ is jointly convex on $(0, 1) \times [0, 1]$.

**Proof.** Recall that $d_{\epsilon}^{+}(\lambda, \mu) = 1 (\mu > [\lambda]_{0}^{1}) \inf_{z \in [[\lambda]_{0}^{1}, \mu]} f_{\epsilon}^{+}([\lambda]_{0}^{1}, \mu, z)$ where $f_{\epsilon}^{+}(\lambda, \mu, z) = \text{kl}(z, \mu) + \epsilon(z - \lambda)$. Direct computations yield that, for all $z \in ([\lambda]_{0}^{1}, \mu)$,

$$ \frac{\partial f_{\epsilon}^{+}}{\partial z}(\lambda, \mu, z) = \log \left( \frac{z(1 - \mu)}{(1 - z)\mu} \right) + \epsilon \quad \text{and} \quad \frac{\partial f_{\epsilon}^{+}}{\partial z}(\lambda, \mu, z) = 0 \iff z = g_{\epsilon}^{+}(\mu), $$

$$ \frac{\partial^2 f_{\epsilon}^{+}}{\partial z^2}(\lambda, \mu, z) = \frac{1}{z(1 - z)} > 0. $$

Therefore, $z \to f_{\epsilon}^{+}(\lambda, \mu, z)$ is twice continuously differentiable, positive and strictly convex on $([\lambda]_{0}^{1}, \mu)$. Moreover, $z \to f_{\epsilon}^{+}(\lambda, \mu, z)$ is decreasing on $([\lambda]_{0}^{1}, \max\{g_{\epsilon}^{+}(\mu), \lambda\})$ and increasing on $(\max\{g_{\epsilon}^{+}(\mu), \lambda\}, \mu)$. Using Lemma 24, we obtain

$$ f_{\epsilon}^{+}(\lambda, \mu, \lambda) = \text{kl}(\lambda, \mu), \\ \text{kl}(g_{\epsilon}^{+}(\mu), \mu) = -(g_{\epsilon}^{+}(\mu) + g_{\epsilon}^{-}(1 - \mu)) \log(\mu(1 - e^{\epsilon}) + e^{\epsilon}) + \epsilon g_{\epsilon}^{-}(1 - \mu) $$
$$ = -\log(1 - \mu(1 - e^{-\epsilon})) - \epsilon g_{\epsilon}^{+}(\mu), \\ f_{\epsilon}^{+}(\lambda, \mu, g_{\epsilon}^{+}(\mu)) = -\log(1 - \mu(1 - e^{-\epsilon})) - \epsilon \lambda. $$

By definition of the indicator function, we have $d_{\epsilon}^{+}(\lambda, \mu) = 0$ if $\mu \in [0, [\lambda]_{0}^{1}]$. When $\lambda \le 0$, for all $\mu \in (0, 1)$, we have

$$ \forall \mu \in (0, 1), \quad d_{\epsilon}^{+}(\lambda, \mu) = f_{\epsilon}^{+}([\lambda]_{0}^{1}, \mu, g_{\epsilon}^{+}(\mu)) = -\log(1 - \mu(1 - e^{-\epsilon})) - \epsilon[\lambda]_{0}^{1}, $$

by using the properties of $z \to f_{\epsilon}^{+}(\lambda, \mu, z)$ on $(0, 1) = (g_{\epsilon}^{-}([\lambda]_{0}^{1}), 1)$ by Lemma 24. This function can be extended by continuity to $\mu = 0 = g_{\epsilon}^{-}([\lambda]_{0}^{1})$ with value $d_{\epsilon}^{+}(\lambda, 0) = 0$. When $\lambda \in (0, 1)$ and $\mu \in (g_{\epsilon}^{-}(\lambda), 1)$, we have

$$ \forall \mu \in (0, 1), \quad d_{\epsilon}^{+}(\lambda, \mu) = f_{\epsilon}^{+}([\lambda]_{0}^{1}, \mu, g_{\epsilon}^{+}(\mu)) = -\log(1 - \mu(1 - e^{-\epsilon})) - \epsilon[\lambda]_{0}^{1}, $$

by using the properties of $z \to f_{\epsilon}^{+}(\lambda, \mu, z)$ on $(g_{\epsilon}^{-}(\lambda), 1) = (g_{\epsilon}^{-}([\lambda]_{0}^{1}), 1)$ by Lemma 24. This function can be extended by continuity to $(\lambda, \mu) = (0, 0) = \lim_{\lambda \to 0^{+}}(\lambda, g_{\epsilon}^{-}([\lambda]_{0}^{1}))$ with value $d_{\epsilon}^{+}(0, 0) = 0$. In both cases, this function can be extended by continuity to $\mu = 1$ with value $d_{\epsilon}^{+}(\lambda, 1) = \epsilon(1 - [\lambda]_{0}^{1})$.

When $\lambda \in (0, 1)$, i.e., $[\lambda]_{0}^{1} = \lambda$, and $\mu \in (\lambda, g_{\epsilon}^{-}(\lambda)) \subseteq (0, 1)$ by Lemma 24, we have

$$ d_{\epsilon}^{+}(\lambda, \mu) = f_{\epsilon}^{+}(\lambda, \mu, \lambda) = \text{kl}(\lambda, \mu). $$

This function can be extended by continuity to $\mu = \lambda$ with value $d_{\epsilon}^{+}(\lambda, \lambda) = 0$ since $\text{kl}(\lambda, \lambda) = 0$. Using Lemma 24, this function can be extended by continuity to $\mu = g_{\epsilon}^{-}(\lambda)$ (i.e., $\lambda = g_{\epsilon}^{+}(\mu)$) with value

$$ d_{\epsilon}^{+}(\lambda, g_{\epsilon}^{-}(\lambda)) = \text{kl}(\lambda, g_{\epsilon}^{-}(\lambda)) = \text{kl}(g_{\epsilon}^{+}(\mu), \mu) = -\log(1 - \mu(1 - e^{-\epsilon})) - \epsilon g_{\epsilon}^{+}(\mu). $$

Therefore, we have

$$ \forall \lambda \in (0, 1), \forall \mu \in [\lambda, g_{\epsilon}^{-}(\lambda)], \quad d_{\epsilon}^{+}(\lambda, \mu) = \text{kl}(\lambda, \mu). $$

Using that $\lim_{\lambda \to 0^{+}}[\lambda, g_{\epsilon}^{-}(\lambda)] = \{0\}$, this function can be extended by continuity to $\lambda = 0$ with value 0. Using that $\lim_{\lambda \to 1^{-}}[\lambda, g_{\epsilon}^{-}(\lambda)] = \{1\}$, this function can be extended by continuity to $\lambda = 1$ with value $0 = \lim_{(\mu, \lambda) \to 1^{-}} -\log(1 - \mu(1 - e^{-\epsilon})) - \epsilon[\lambda]_{0}^{1}$.

Putting all the continuity arguments together, we have shown that $(\lambda, \mu) \to d_{\epsilon}^{+}(\lambda, \mu)$ is jointly continuous on $\mathbb{R} \times [0, 1]$. Moreover, it is direct to see that, for all $\mu \in [0, 1]$, the function $\lambda \to d_{\epsilon}^{+}(\lambda, \mu)$ is constant on $(-\infty, 0]$ and on $[1, +\infty)$. Then,

$$ \forall \lambda \in (0, 1), \forall \mu \in [0, 1], \quad d_{\epsilon}^{+}(\lambda, \mu) = \begin{cases} 0 & \text{if } \mu \in [0, \lambda] \\ \text{kl}(\lambda, \mu) & \mu \in (\lambda, g_{\epsilon}^{-}(\lambda)] \\ -\log(1 - \mu(1 - e^{-\epsilon})) - \epsilon\lambda & \text{if } \mu \in (g_{\epsilon}^{-}(\lambda), 1] \end{cases}. $$

Let $\mu \in [0, 1]$ and $\lambda \in (0, \mu)$. Using that $\mu \in (g_{\epsilon}^{-}(\lambda), 1]$ if and only if $\lambda \in (0, g_{\epsilon}^{+}(\mu))$. For all $\mu \in [0, 1]$, the function $\lambda \to d_{\epsilon}^{+}(\lambda, \mu)$ is positive and affine with negative slope $-\epsilon$ on $(0, g_{\epsilon}^{+}(\mu))$. Let $\lambda \in (g_{\epsilon}^{+}(\mu), \mu)$. Direct computation yields that

$$ \begin{aligned} \frac{\partial d_{\epsilon}^{+}}{\partial \lambda}(\lambda, \mu) &= \frac{\partial \text{kl}}{\partial \lambda}(\lambda, \mu) = \log\left(\frac{\lambda(1-\mu)}{(1-\lambda)\mu}\right) < 0, \\ \lim_{\lambda \to g_{\epsilon}^{+}(\mu)^{+}} \frac{\partial d_{\epsilon}^{+}}{\partial \lambda}(\lambda, \mu) &= -\epsilon = \lim_{\lambda \to g_{\epsilon}^{+}(\mu)^{-}} \frac{\partial d_{\epsilon}^{+}}{\partial \lambda}(\lambda, \mu), \\ \frac{\partial^2 d_{\epsilon}^{+}}{\partial \lambda^2}(\lambda, \mu) &= \frac{\partial^2 \text{kl}}{\partial \lambda^2}(\lambda, \mu) = \frac{1}{\lambda(1-\lambda)} > 0. \end{aligned} $$

For all $\mu \in [0, 1]$, the function $\lambda \to d_{\epsilon}^{+}(\lambda, \mu)$ is continuously differentiable, positive, decreasing and convex on $(0, \mu)$. For all $\mu \in [0, 1]$, the function $\lambda \to d_{\epsilon}^{+}(\lambda, \mu)$ is twice continuously differentiable, positive and strictly convex on $(g_{\epsilon}^{+}(\mu), \mu)$. Combining the above results concludes the part of $\lambda \mapsto d_{\epsilon}^{+}(\lambda, \mu)$ on $(0, \mu)$.

Let $\lambda \in (0, 1)$. Let $a > 0$ and $k \in \mathbb{N}$. The k-th derivative of $u(x) = a(1 - ax)^{-1}$ on $[0, 1]$ is $u^{(k)}(x) = (k - 1)!a^{k+1}(1 - ax)^{-(k+1)}$. Then,

$$ \forall \mu \in (g_{\epsilon}^{-}(\lambda), 1], \forall k \in \mathbb{N}, \quad \frac{\partial^k d_{\epsilon}^{+}}{\partial \mu^k}(\lambda, \mu) = \frac{(1 - e^{-\epsilon})^k (k - 1)!}{(1 - \mu(1 - e^{-\epsilon}))^k} > 0, $$
$$
\begin{align*}
\forall \mu \in (\lambda, g_{\epsilon}^{-}(\lambda)], \quad \frac{\partial d_{\epsilon}^{+}}{\partial \mu}(\lambda, \mu) &= \frac{\mu - \lambda}{\mu(1 - \mu)} > 0, \\
\frac{\partial^2 d_{\epsilon}^{+}}{\partial \mu^2}(\lambda, \mu) &= \frac{(\mu - \lambda)^2 + \lambda(1 - \lambda)}{\mu^2(1 - \mu)^2} > 0, \\
\frac{\partial^3 d_{\epsilon}^{+}}{\partial \mu^3}(\lambda, \mu) &= 0.
\end{align*}
$$

Direct computation yields

$$
\begin{align*}
\lim_{\mu \to g_{\epsilon}^{-}(\lambda)} \frac{\mu - \lambda}{\mu(1 - \mu)} &= (1 - e^{-\epsilon})(1 + \lambda(e^{\epsilon} - 1)), \\
\lim_{\mu \to g_{\epsilon}^{-}(\lambda)} \frac{1 - e^{-\epsilon}}{1 - \mu(1 - e^{-\epsilon})} &= (1 - e^{-\epsilon})(1 + \lambda(e^{\epsilon} - 1)), \\
\lim_{\mu \to g_{\epsilon}^{-}(\lambda)} \left\{ \frac{(\mu - \lambda)^2 + \lambda(1 - \lambda)}{\mu^2(1 - \mu)^2} - \frac{(1 - e^{-\epsilon})^2}{(1 - \mu(1 - e^{-\epsilon}))^2} \right\} &= \frac{\lambda(1 - \lambda)}{g_{\epsilon}^{-}(\lambda)^2(1 - g_{\epsilon}^{-}(\lambda))^2} > 0.
\end{align*}
$$

For all $\lambda \in (0, 1)$, the function $\mu \to d_{\epsilon}^{+}(\lambda, \mu)$ is positive, three times differentiable with continuous first derivative and increasing on $(\lambda, 1]$. For all $\lambda \in (0, 1)$, the function $\mu \to d_{\epsilon}^{+}(\lambda, \mu)$ is strictly convex on $(\lambda, g_{\epsilon}^{-}(\lambda)]$ and $(g_{\epsilon}^{-}(\lambda), 1]$. The second derivative is discontinuous at $g_{\epsilon}^{-}(\lambda)$ with gap $\frac{\partial^2 d_{\epsilon}^{+}}{\partial \mu^2}(\lambda, g_{\epsilon}^{-}(\lambda)) - \lim_{\mu \to g_{\epsilon}^{-}(\lambda)^+} \frac{\partial^2 d_{\epsilon}^{+}}{\partial \mu^2}(\lambda, \mu) > 0$. Thanks to the continuity of the first derivative and the sign of the second derivative, the function $\mu \to d_{\epsilon}^{+}(\lambda, \mu)$ is strict convexity on $(\lambda, 1]$.

Let $(\mu_1, \mu_2) \in [0, 1]^2$ and $(\lambda_1, \lambda_2) \in (0, 1)^2$. On the convex set $\mathcal{F}_0 = \{(\lambda, \mu) \in (0, 1) \times [0, 1] \mid \mu \in [0, \lambda]\}$, the function $d_{\epsilon}^{-}$ is null hence jointly convex. Let $((\mu_1, \lambda_1), (\mu_2, \lambda_2)) \in (((0, 1) \times [0, 1]) \setminus \mathcal{F}_0)^2$. Let $(z_1, z_2) \in [\lambda_1, \mu_1] \times [\lambda_2, \mu_2]$ be the minimizers realizing $d_{\epsilon}^{+}(\lambda_1, \mu_1)$ and $d_{\epsilon}^{+}(\lambda_2, \mu_2)$. Since it is a convex set, we have $(\alpha\lambda_1 + (1-\alpha)\lambda_2, \alpha\mu_1 + (1-\alpha)\mu_2) \in ((0, 1) \times [0, 1]) \setminus \mathcal{F}_0$ for all $\alpha \in [0, 1]$. Moreover, we have $\alpha z_1 + (1-\alpha)z_2 \in [\alpha\lambda_1 + (1-\alpha)\lambda_2, \alpha\mu_1 + (1-\alpha)\mu_2]$ for all $\alpha \in [0, 1]$. Using the definition of $d_{\epsilon}^{+}$ as an infimum, we obtain

$$
\begin{align*}
& d_{\epsilon}^{+}(\alpha\lambda_1 + (1-\alpha)\lambda_2, \alpha\mu_1 + (1-\alpha)\mu_2) \\
& \le \text{kl}(\alpha z_1 + (1-\alpha)z_2, \alpha\mu_1 + (1-\alpha)\mu_2) + \epsilon(\alpha z_1 + (1-\alpha)z_2 - (\alpha\lambda_1 + (1-\alpha)\lambda_2)) \\
& \le \alpha(\text{kl}(z_1, \mu_1) + \epsilon(z_1 - \lambda_1)) + (1-\alpha)(\text{kl}(z_2, \mu_2) + \epsilon(z_2 - \lambda_2)) \\
& = \alpha d_{\epsilon}^{+}(\lambda_1, \mu_1) + (1-\alpha)d_{\epsilon}^{+}(\lambda_2, \mu_2)
\end{align*}
$$

where the second inequality comes from the joint convexity of the Kullback-Leibler divergence.
Combining both results, we have shown that the function $d_{\epsilon}^{+}$ is jointly convex on $(0, 1) \times [0, 1]$. $\square$

Lemma 26 gather regularity properties of $d_{\epsilon}^{-}$. In particular, it gives a closed-form solution, which is a key property used in our implementation to reduce the computational cost.

**Lemma 26.** Let $d_{\epsilon}^{-}$ as in Eq. (3), and $g_{\epsilon}^{\pm}$ as in Eq. (30). For all $\mu \in [0, 1]$ and all $\lambda \in \mathbb{R}$, we have

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

The function $(\lambda, \mu) \mapsto d_{\epsilon}^{-}(\lambda, \mu)$ is jointly continuous on $\mathbb{R} \times [0, 1]$. For all $\mu \in [0, 1]$, the function $\lambda \mapsto d_{\epsilon}^{-}(\lambda, \mu)$ is constant on $(-\infty, 0]$ and on $[1, +\infty)$. Then,

$$
\forall \lambda \in (0, 1), \forall \mu \in [0, 1], \quad d_{\epsilon}^{-}(\lambda, \mu) = \begin{cases} 0 & \text{if } \mu \in [\lambda, 1] \\ \text{kl}(\lambda, \mu) & \text{if } \mu \in [g_{\epsilon}^{+}(\lambda), \lambda) \\ -\log(1 + \mu(e^{\epsilon} - 1)) + \epsilon\lambda & \text{if } \mu \in [0, g_{\epsilon}^{+}(\lambda)) \end{cases} .
$$

For all $\mu \in [0, 1]$, the function $\lambda \mapsto d_{\epsilon}^{-}(\lambda, \mu)$ is continuously differentiable, positive, increasing and convex on $(\mu, 1)$; it is affine with positive slope $\epsilon$ on $(g_{\epsilon}^{-}(\mu), 1)$ and twice continuously differentiable and strictly convex on $(\mu, g_{\epsilon}^{-}(\mu))$.
For all $\lambda \in (0, 1)$, the function $\mu \mapsto d_{\epsilon}^{-}(\lambda, \mu)$ is positive, three times differentiable with continuous first derivative, decreasing and strictly convex on $[0, \lambda)$; its second derivative is discontinuous at $g_{\epsilon}^{+}(\lambda)$ with gap $\lim_{\mu \to g_{\epsilon}^{+}(\lambda)} -\frac{\partial^2 d_{\epsilon}^{-}}{\partial \mu^2}(\lambda, \mu) - \frac{\partial^2 d_{\epsilon}^{-}}{\partial \mu^2}(\lambda, g_{\epsilon}^{+}(\lambda)) < 0$. Moreover, we have

$$ \forall \mu \in [0, \lambda), \quad \frac{\partial d_{\epsilon}^{-}}{\partial \mu}(\lambda, \mu) = \begin{cases} -\frac{e^{\epsilon}-1}{1+\mu(e^{\epsilon}-1)} & \text{if } \mu \in [0, g_{\epsilon}^{+}(\lambda)) \\ -\frac{\lambda-\mu}{\mu(1-\mu)} & \text{if } \mu \in [g_{\epsilon}^{+}(\lambda), \lambda) \end{cases}. $$

The function $d_{\epsilon}^{-}$ is jointly convex on $(0, 1) \times [0, 1]$.

*Proof.* Using Lemmas 23 and 24, we have

$$ \begin{gathered} d_{\epsilon}^{-}(\lambda, \mu) = d_{\epsilon}^{+}(1 - \lambda, 1 - \mu) \quad \text{and} \quad g_{\epsilon}^{+}(\lambda) = 1 - g_{\epsilon}^{-}(1 - \lambda), \\ \frac{\partial d_{\epsilon}^{-}}{\partial \mu}(\lambda, \mu) = -\frac{\partial d_{\epsilon}^{+}}{\partial \mu}(1 - \lambda, 1 - \mu) \quad \text{and} \quad \frac{\partial^2 d_{\epsilon}^{-}}{\partial \mu^2}(\lambda, \mu) = \frac{\partial^2 d_{\epsilon}^{+}}{\partial \mu^2}(1 - \lambda, 1 - \mu). \end{gathered} $$

Moreover, we have $kl(\lambda, \mu) = kl(1 - \lambda, 1 - \mu)$ and

$$ -\log(1 + \mu(e^{\epsilon} - 1)) + \epsilon[\lambda]_{0}^{1} = -\log(1 - (1 - \mu)(1 - e^{-\epsilon})) - \epsilon[1 - \lambda]_{0}^{1}. $$

Combining the above with properties of $d_{\epsilon}^{+}$ in Lemma 25 concludes the proof. $\square$

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

### G.1.1 Modified Divergence

Let us define

$$ \forall x > 0, \quad h(x) := \sqrt{1+x^2} - 1 + \log \left( \frac{2}{x^2} \left( \sqrt{1+x^2} - 1 \right) \right). \quad (31) $$

For all $(\lambda, \mu, r) \in \mathbb{R} \times (0, 1) \times \mathbb{R}_{+}^{*}$, we define

$$ \begin{aligned} \tilde{d}_{\epsilon}^{-}(\lambda, \mu, r) &:= \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) &:= \inf_{z \in ([\lambda]_{0}^{1}, \mu)} \left\{ \text{kl}(z, \mu) + \frac{1}{r}h(r\epsilon(z - \lambda)) \right\}. \end{aligned} \quad (32) $$

Lemma 27 shows a strong link between $\tilde{d}_{\epsilon}^{\pm}$. This symmetry property can be used to carry regularity properties from $\tilde{d}_{\epsilon}^{+}$ to $\tilde{d}_{\epsilon}^{-}$, and vice versa.

**Lemma 27.** Let $\tilde{d}_{\epsilon}^{\pm}$ as in Eq. (32). For all $(\lambda, \mu) \in \mathbb{R} \times [0, 1]$, we have

$$ \tilde{d}_{\epsilon}^{+}(1 - \lambda, 1 - \mu, r) = \tilde{d}_{\epsilon}^{-}(\lambda, \mu, r) \quad \text{and} \quad \tilde{d}_{\epsilon}^{-}(1 - \lambda, 1 - \mu, r) = \tilde{d}_{\epsilon}^{+}(\lambda, \mu, r). $$

*Proof.* Using the definitions, the change of variable $\tilde{z} = 1 - z$ and $kl(1 - \tilde{z}, 1 - \mu) = kl(\tilde{z}, \mu)$, we obtain

$$ \begin{aligned} \tilde{d}_{\epsilon}^{+}(1 - \lambda, 1 - \mu, r) &= \inf_{z \in [1 - [\lambda]_{0}^{1}, 1 - \mu]} \left\{ \text{kl}(z, 1 - \mu) + \frac{1}{r}h(r\epsilon(\lambda - (1 - z))) \right\} \\ &= \inf_{\tilde{z} \in [\mu, [\lambda]_{0}^{1}]} \left\{ \text{kl}(1 - \tilde{z}, 1 - \mu) + \frac{1}{r}h(r\epsilon(\lambda - \tilde{z})) \right\} \\ &= \inf_{\tilde{z} \in [\mu, [\lambda]_{0}^{1}]} \left\{ \text{kl}(\tilde{z}, \mu) + \frac{1}{r}h(r\epsilon(\lambda - \tilde{z})) \right\} = \tilde{d}_{\epsilon}^{-}(\lambda, \mu, r). \end{aligned} $$

The second equality is a consequence of the first. $\square$

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

Lemma 28 gathers regularity properties of the function $h$ defined in Eq. (31).
**Lemma 28.** Let $h$ as in Eq. (31). Then,

$$ \forall x > 0, \quad h'(x) = \frac{x}{\sqrt{x^2+1}+1} > 0 \quad \text{and} \quad h''(x) = \frac{1}{1+x^2+\sqrt{1+x^2}} > 0. $$

On $\mathbb{R}_+^*$, the function $h$ is twice continuously differentiable, increasing and strictly convex. Moreover, it satisfies

$$ h(x) =_{x \to 0} x^2/4 + \mathcal{O}(x^4) \quad \text{and} \quad h(x) =_{x \to +\infty} x - \mathcal{O}(\log(x)). $$

*Proof.* For all $x > 0$, $h_1(x) = x + \log(x)$, $h_2(x) = \sqrt{1+x^2}-1$ and $h_3(x) = \sqrt{1+x^2}-x$. Then

$$ h'_1(x) = 1 + \frac{1}{x}, \quad h'_2(x) = \frac{x}{\sqrt{1+x^2}} \quad \text{and} \quad h'_3(x) = \frac{x}{\sqrt{1+x^2}} - 1, $$

Then, we have

$$ \forall x > 0, \quad h(x) = h_1(h_2(x)) - 2\log(x) + \log 2. $$

Therefore, we have

$$ \begin{aligned} h'(x) = h'_2(x)h'_1(h_2(x)) - \frac{2}{x} &= \frac{x}{\sqrt{1+x^2}} \left( 1 + \frac{1}{\sqrt{1+x^2}-1} \right) - \frac{2}{x} \\ &= \frac{x}{\sqrt{1+x^2}-1} - \frac{2}{x} = \sqrt{1+\frac{1}{x^2}} - \frac{1}{x} = h_3(1/x). \end{aligned} $$

Note that

$$ \sqrt{1 + \frac{1}{x^2}} - \frac{1}{x} = \frac{x}{\sqrt{x^2+1}+1}. $$

Moreover, we have w

$$ h''(x) = -\frac{1}{x^2}h'_3(1/x) = -\frac{1}{x^2}\left(\frac{1/x}{\sqrt{1+(1/x)^2}} - 1\right) = \frac{1}{1+x^2+\sqrt{1+x^2}}. $$

By taking the limit, we have $\lim_{x \to 0^+} h(x) = 0$. Moreover, we see that $\lim_{x \to 0^+} h'(x) = 0$ and $\lim_{x \to 0^+} h''(x) = 1/2$. Therefore, one can conclude that $h(x) =_{x \to 0} x^2/4 + \mathcal{O}(x^4)$ by Taylor expansion. The second result is obtained directly by limit. $\square$

Lemma 29 provides upper and lower bound on the function $r \mapsto h(rx)/r$ involved in the definition of $\tilde{d}_\epsilon^\pm$.

**Lemma 29.** Let $h$ as in Eq. (31). Let $\kappa(r, x) = h(rx)/r - x$ for all $r > 0$ and all $x \in \mathbb{R}_+^*$. Then, we have

$$ \forall r > 0, \quad \frac{\partial \kappa}{\partial r}(r, x) = \frac{rxh'(rx) - h(rx)}{r^2} = \log\left(\frac{1}{2}(\sqrt{1+(rx)^2} + 1)\right) > 0. $$

On $\mathbb{R}_+^*$, the function $r \mapsto \kappa(r, x)$ is increasing. Moreover, we have

$$ \forall r > 0, \forall x \in \mathbb{R}_+, \quad 0 \le r\kappa(r, x) + \log(1 + 2xr) + 1 \le 1 + \log 4, $$

*Proof.* Using Lemma 28 and the definition in Eq. (31), we obtain that

$$ \forall x > 0, \quad xh'(x) - h(x) = -\log\left(\frac{2}{x^2}(\sqrt{1+x^2}-1)\right) = \log\left(\frac{1}{2}(\sqrt{1+x^2}+1)\right) > 0, $$

where we used that $\sqrt{1+x^2}+1 > 2$ for the last inequality. Let us define

$$ \forall x \in \mathbb{R}_+, \quad g_1(x) = \frac{2(1+2x)}{\sqrt{1+x^2}+1}. $$

Then, we obtain $g_1(0) = 1$, $\lim_{x \to +\infty} g_1(x) = 4$ and

$$ g'_1(x) = 2 \frac{2 + 2\sqrt{1+x^2} - x}{\sqrt{1+x^2}(\sqrt{1+x^2}+1)^2} > 2 \frac{2+x}{\sqrt{1+x^2}(\sqrt{1+x^2}+1)^2} > 0. $$
Since $g_1$ is strictly increasing on $\mathbb{R}_+^*$, we obtain $\log g_1(x) \ge \log g_1(0) = 0$ and $\log g_1(x) \le \log 4$ for all $x \in \mathbb{R}_+$.

By definition, we obtain

$$ 
\begin{aligned}
r\kappa(r, x) + \log(1 + 2xr) + 1 &= h(rx) - rx + 1 + \log(1 + 2xr) \\
&= \sqrt{1 + (rx)^2} - rx + \log\left(\frac{2(1 + 2xr)}{\sqrt{1 + r^2x^2} + 1}\right).
\end{aligned}
$$

Using that $0 \le \sqrt{1+x^2} - x \le 1$ on $\mathbb{R}_+$, we obtain

$$ 
\begin{aligned}
r\kappa(r, x) + \log(1 + 2xr) + 1 &\ge \log\left(\frac{2(1 + 2xr)}{\sqrt{1 + r^2x^2} + 1}\right) = \log(g_1(rx)) \ge 0, \\
r\kappa(r, x) + \log(1 + 2xr) + 1 &\le 1 + \log(g_1(rx)) \le 1 + \log 4.
\end{aligned}
$$

This concludes the proof.

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

Lemma 30 provides lower and upper bounds on the gap between $\tilde{d}_{\epsilon}^{\pm}$ and $d_{\epsilon}^{\pm}$.

**Lemma 30.** Let $d_{\epsilon}^{\pm}$ and $\tilde{d}_{\epsilon}^{\pm}$ as in Eq. (3) and (32). For all $(\lambda, \mu, r) \in \mathbb{R} \times (0, 1) \times \mathbb{R}_+^*$ such that $[\lambda]_0^1 < \mu$. Then,

$$ d_{\epsilon}^{+}(\lambda, \mu) \le \tilde{d}_{\epsilon}^{+}(\lambda, \mu, r) + \frac{\log(1 + 2\epsilon r) + 1}{r} . $$

For all $(\lambda, \mu, r) \in \mathbb{R} \times (0, 1) \times \mathbb{R}_+^*$ such that $[\lambda]_0^1 > \mu$. Then,

$$ d_{\epsilon}^{-}(\lambda, \mu) \le \tilde{d}_{\epsilon}^{-}(\lambda, \mu, r) + \frac{\log(1 + 2\epsilon r) + 1}{r} . $$

For all $(\lambda, \mu, r) \in [0, 1] \times (0, 1) \times \mathbb{R}_+^*$ such that $\lambda < \mu$. Then,

$$ d_{\epsilon}^{+}(\lambda, \mu) \ge \tilde{d}_{\epsilon}^{+}(\lambda, \mu, r) - \frac{\log 4}{r} . $$

For all $(\mu, \lambda, r) \in [0, 1] \times \mathbb{R}_+^*$ such that $\lambda > \mu$. Then,

$$ d_{\epsilon}^{-}(\lambda, \mu) \ge \tilde{d}_{\epsilon}^{-}(\lambda, \mu, r) - \frac{\log 4}{r} . $$

*Proof.* Since $\mu \in (0, 1)$, we have $[\lambda]_0^1 = \max\{0, \lambda\}$. Therefore, we have $z - \lambda \ge z - [\lambda]_0^1$ and $z - [\lambda]_0^1 \in (0, \mu - [\lambda]_0^1) \subset (0, 1)$ for all $z \in ([\lambda]_0^1, \mu)$. Using Lemmas 28 and 29 and $\epsilon > 0$, we obtain, for all $r > 0$ and all $z \in ([\lambda]_0^1, \mu)$,

$$ 
\begin{aligned}
\epsilon(z - [\lambda]_0^1) &\le \frac{1}{r}h(r\epsilon(z - [\lambda]_0^1)) + \frac{\log(1 + 2\epsilon(z - [\lambda]_0^1)r) + 1}{r} \\
&\le \frac{1}{r}h(r\epsilon(z - \lambda)) + \frac{\log(1 + 2\epsilon r) + 1}{r}.
\end{aligned}
$$

Therefore, for all $z \in ([\lambda]_0^1, \mu)$, we obtain that

$$ \mathrm{kl}(z, \mu) + \epsilon(z - [\lambda]_0^1) \le \mathrm{kl}(z, \mu) + \frac{1}{r}h(r\epsilon(z - \lambda)) + \frac{\log(1 + 2\epsilon r) + 1}{r} . $$

Taking the infimum over $z \in ([\lambda]_0^1, \mu)$ on both sides of both inequalities and using that

$$ 
\begin{aligned}
d_{\epsilon}^{+}(\lambda, \mu) &= \inf_{z \in [[\lambda]_0^1, \mu]} \{\mathrm{kl}(z, \mu) + \epsilon(z - [\lambda]_0^1)\} = \inf_{z \in ([\lambda]_0^1, \mu)} \{\mathrm{kl}(z, \mu) + \epsilon(z - [\lambda]_0^1)\}, \\
\tilde{d}_{\epsilon}^{+}(\lambda, \mu, r) &= \inf_{z \in ([\lambda]_0^1, \mu)} \left\{\mathrm{kl}(z, \mu) + \frac{1}{r}h(r\epsilon(z - \lambda))\right\},
\end{aligned}
$$

we obtain

$$ d_{\epsilon}^{+}(\lambda, \mu) \le \tilde{d}_{\epsilon}^{+}(\lambda, \mu, r) + \frac{\log(1 + 2\epsilon r) + 1}{r} . $$
This concludes the proof of the first result. Using Lemmas 23 and 27 yields the second result.

Suppose that $\lambda \in [0, 1]$, hence $\lambda = [\lambda]_0^1$. Using Lemmas 28 and 29 and $\epsilon > 0$, we obtain, for all $r > 0$ and all $z \in ([\lambda]_0^1, \mu)$,

$$ \frac{1}{r}h(r\epsilon(z - \lambda)) \le \epsilon(z - \lambda) + \frac{\log 4 - \log(1 + 2\epsilon(z - \lambda)r)}{r} \le \epsilon(z - [\lambda]_0^1) + \frac{\log 4}{r}. $$

Adding $kl(z, \mu)$ on both sides and taking the infimum over $z \in ([\lambda]_0^1, \mu)$ on both sides of both inequalities yields the proof of third result. Using Lemmas 23 and 27 yields the fourth result. $\square$

**Lemma 31.** Let $\tilde{d}_{\epsilon}^{+}$ as in Eq. (32), and $g_{\epsilon}^{\pm}$ as in Eq. (30). For all $\mu \in (0, 1)$, $\lambda \in \mathbb{R}$ and $r > 0$, we have

$$ \tilde{d}_{\epsilon}^{+}(\lambda, \mu, r) = \begin{cases} 0 & \text{if } \mu \in (0, [\lambda]_0^1] \\ \text{kl}(x_{\epsilon}^{+}(\lambda, \mu, r) + g_{\epsilon}^{+}(\mu), \mu) + \frac{1}{r}h(r\epsilon(x_{\epsilon}^{+}(\lambda, \mu, r) + g_{\epsilon}^{+}(\mu) - \lambda)) & \text{if } \mu \in ([\lambda]_0^1, 1) \end{cases}, $$

where $x_{\epsilon}^{+}(\lambda, \mu, r) \in (\max\{0, \lambda - g_{\epsilon}^{+}(\mu)\}, \mu - g_{\epsilon}^{+}(\mu))$ is the unique solution for $x \in (\max\{0, \lambda - g_{\epsilon}^{+}(\mu)\}, \mu - g_{\epsilon}^{+}(\mu))$ of the equation

$$ \log \left( 1 + \frac{x}{g_{\epsilon}^{+}(\mu)(1 - x - g_{\epsilon}^{+}(\mu))} \right) + \epsilon \left( \frac{r\epsilon(x + g_{\epsilon}^{+}(\mu) - \lambda)}{\sqrt{(r\epsilon(x + g_{\epsilon}^{+}(\mu) - \lambda))^2 + 1 + 1}} - 1 \right) = 0. $$

For all $(\mu, r) \in (0, 1) \times \mathbb{R}_+$, the function $\lambda \mapsto \tilde{d}_{\epsilon}^{+}(\lambda, \mu, r)$ is positive, twice continuously differentiable, decreasing and strictly convex on $(-\infty, \mu)$; it satisfies $\lim_{\lambda \to \mu^{-}} \tilde{d}_{\epsilon}^{+}(\lambda, \mu, r) = 0$ and $\lim_{\lambda \to -\infty} \tilde{d}_{\epsilon}^{+}(\lambda, \mu, r) = +\infty$.

For all $(\lambda, r) \in \mathbb{R} \times \mathbb{R}_+$, the function $\mu \mapsto \tilde{d}_{\epsilon}^{+}(\lambda, \mu, r)$ is positive, twice continuously differentiable, increasing and strictly convex on $([\lambda]_0^1, 1)$. Moreover, we have

$$ \forall \mu \in ([\lambda]_0^1, 1), \quad \frac{\partial \tilde{d}_{\epsilon}^{+}}{\partial \mu}(\lambda, \mu, r) = \frac{\mu - g_{\epsilon}^{+}(\mu) - x_{\epsilon}^{+}(\lambda, \mu, r)}{\mu(1 - \mu)}. $$

For all $(\lambda, \mu) \in \mathbb{R} \times (0, 1)$ such that $\mu \in (0, [\lambda]_0^1]$, the function $r \mapsto \tilde{d}_{\epsilon}^{+}(\lambda, \mu, r)$ is the zero function. For all $(\lambda, \mu) \in \mathbb{R} \times (0, 1)$ such that $\mu \in ([\lambda]_0^1, 1)$, the function $r \mapsto \tilde{d}_{\epsilon}^{+}(\lambda, \mu, r)$ is positive, continuously differentiable and increasing on $\mathbb{R}_+$.

*Proof.* By definition of the indicator function, we have $\tilde{d}_{\epsilon}^{+}(\lambda, \mu, r) = 0$ if $\mu \in (0, [\lambda]_0^1]$. Let $(\lambda, \mu)$ such that $\mu \notin (0, [\lambda]_0^1]$, i.e., $([\lambda]_0^1, \mu)$ is non-empty. Since $\mu \in (0, 1)$, this implies that $\lambda \in (-\infty, 1)$ necessarily, i.e., $[\lambda]_0^1 = \max\{0, \lambda\}$.

Recall that $\tilde{d}_{\epsilon}^{+}(\lambda, \mu, r) = 1$ ($\mu > [\lambda]_0^1$) $\inf_{z \in ([\lambda]_0^1, \mu)} \tilde{f}_{\epsilon}^{+}(\lambda, \mu, r, z)$ where $\tilde{f}_{\epsilon}^{+}(\lambda, \mu, r, z) = \text{kl}(z, \mu) + \frac{1}{r}h(r\epsilon(z - \lambda))$. Using Lemma 28, direct computations yield that, for all $z \in ([\lambda]_0^1, \mu)$,

$$ \begin{aligned} \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial z}(\lambda, \mu, r, z) &= \log \left( \frac{z(1 - \mu)}{(1 - z)\mu} \right) + \epsilon h'(r\epsilon(z - \lambda)) \\ &= \log \left( \frac{z(1 - \mu)}{(1 - z)\mu} \right) + \epsilon \frac{r\epsilon(z - \lambda)}{\sqrt{(r\epsilon(z - \lambda))^2 + 1 + 1}}, \\ \frac{\partial^2 \tilde{f}_{\epsilon}^{+}}{\partial z^2}(\lambda, \mu, r, z) &= \frac{1}{z(1 - z)} + r\epsilon^2 h''(r\epsilon(z - \lambda)) > 0. \end{aligned} $$
Therefore, $z \to \tilde{f}_{\epsilon}^{+}(\lambda, \mu, r, z)$ is twice continuously differentiable, positive and strictly convex on $([\lambda]_{0}^{1}, \mu)$. Moreover, we have

$$ \lim_{z \to \mu} \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial z}(\lambda, \mu, r, z) = \epsilon h'(r\epsilon(\mu - \lambda)) > 0, \\ \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial z}(\lambda, \mu, r, g_{\epsilon}^{+}(\mu)) = -\epsilon \left( 1 - \frac{r\epsilon(z - \lambda)}{\sqrt{(r\epsilon(z - \lambda))^{2} + 1 + 1}} \right) < 0, $$

$$ \text{When } [\lambda]_{0}^{1} > g_{\epsilon}^{+}(\mu), \quad \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial z}(\lambda, \mu, r, \lambda) = \log \left( \frac{\lambda(1 - \mu)}{(1 - \lambda)\mu} \right) < 0. $$

Note that $\max\{[\lambda]_{0}^{1}, g_{\epsilon}^{+}(\mu)\} = \max\{\lambda, g_{\epsilon}^{+}(\mu)\}$ since $\mu \in (0, 1)$. Using that $z \to \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial z}(\lambda, \mu, r, z)$ is continuously differentiable and increasing on $([\lambda]_{0}^{1}, \mu)$, with negative value at $\max\{\lambda, g_{\epsilon}^{+}(\mu)\}$ and finite positive limit at $\mu$, $z \mapsto \tilde{f}_{\epsilon}^{+}(\lambda, \mu, r, z)$ admit a unique minimizer on $(\max\{\lambda, g_{\epsilon}^{+}(\mu)\}, \mu)$. Let $\tilde{g}_{\epsilon}^{+}(\lambda, \mu, r) \in (\max\{\lambda, g_{\epsilon}^{+}(\mu)\}, \mu)$ be defined as this unique minimizer, defined implicitly as solution for $z \in (\max\{\lambda, g_{\epsilon}^{+}(\mu)\}, \mu)$ of the equation

$$ \log \left( \frac{z(1 - \mu)}{(1 - z)\mu} \right) + \epsilon \frac{r\epsilon(z - \lambda)}{\sqrt{(r\epsilon(z - \lambda))^{2} + 1 + 1}} = 0. $$

Then, we have $\frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial z}(\lambda, \mu, r, z) = 0$ if and only if $z = \tilde{g}_{\epsilon}^{+}(\lambda, \mu, r)$. Moreover, $z \mapsto \tilde{f}_{\epsilon}^{+}(\lambda, \mu, r, z)$ is decreasing on $([\lambda]_{0}^{1}, \tilde{g}_{\epsilon}^{+}(\lambda, \mu, r))$ and increasing on $(\tilde{g}_{\epsilon}^{+}(\lambda, \mu, r), \mu)$.

Let us define $z = g_{\epsilon}^{+}(\mu) + x$ where $x \in (\max\{0, \lambda - g_{\epsilon}^{+}(\mu)\}, \mu - g_{\epsilon}^{+}(\mu))$. Then, we have

$$ \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial z}(\lambda, \mu, r, g_{\epsilon}^{+}(\mu) + x) = \log \left( 1 + \frac{x}{g_{\epsilon}^{+}(\mu)(1 - x - g_{\epsilon}^{+}(\mu))} \right) + \epsilon \left( \frac{r\epsilon(x + g_{\epsilon}^{+}(\mu) - \lambda)}{\sqrt{(r\epsilon(x + g_{\epsilon}^{+}(\mu) - \lambda))^{2} + 1 + 1}} - 1 \right) $$

Therefore, we have $\tilde{g}_{\epsilon}^{+}(\lambda, \mu, r) = g_{\epsilon}^{+}(\mu) + x_{\epsilon}^{+}(\lambda, \mu, r)$ where $x_{\epsilon}^{+}(\lambda, \mu, r) \in (\max\{0, \lambda - g_{\epsilon}^{+}(\mu)\}, \mu - g_{\epsilon}^{+}(\mu))$ is the solution for $x \in (\max\{0, \lambda - g_{\epsilon}^{+}(\mu)\}, \mu - g_{\epsilon}^{+}(\mu))$ of the equation

$$ \log \left( 1 + \frac{x}{g_{\epsilon}^{+}(\mu)(1 - x - g_{\epsilon}^{+}(\mu))} \right) + \epsilon \left( \frac{r\epsilon(x + g_{\epsilon}^{+}(\mu) - \lambda)}{\sqrt{(r\epsilon(x + g_{\epsilon}^{+}(\mu) - \lambda))^{2} + 1 + 1}} - 1 \right) = 0. $$

When $\lambda \in (0, 1)$ and $\mu \to \lambda = [\lambda]_{0}^{1}$, it is direct to see that $\tilde{g}_{\epsilon}^{+}(\lambda, \mu, r) \to \lambda$. Then, we have

$$ \lim_{\mu \to \lambda^{+}} \tilde{d}_{\epsilon}^{+}(\lambda, \mu, r) = \lim_{\mu \to \lambda^{+}} \{\text{kl}(\tilde{g}_{\epsilon}^{+}(\lambda, \mu, r), \mu)\} + \frac{1}{r} \lim_{\tilde{g}_{\epsilon}^{+}(\lambda, \mu, r) \to \lambda^{+}} \{h(r\epsilon(\tilde{g}_{\epsilon}^{+}(\lambda, \mu, r) - \lambda))\} = 0. $$

Direct computation yields that, for $z \in ([\lambda]_{0}^{1}, \mu) \subset (0, 1)$,

$$ \begin{aligned} \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial \mu}(\lambda, \mu, r, z) &= \frac{\mu - z}{\mu(1 - \mu)} > 0, \\ \frac{\partial^2 \tilde{f}_{\epsilon}^{+}}{\partial \mu^2}(\lambda, \mu, r, z) &= \frac{(\mu - z)^2 + z(1 - z)}{\mu^2(1 - \mu)^2} > 0, \\ \frac{\partial^2 \tilde{f}_{\epsilon}^{+}}{\partial z^2}(\lambda, \mu, r, z) &= \frac{1}{z(1 - z)} + r\epsilon^2 h''(r\epsilon(z - \lambda)) > 0, \\ \frac{\partial^2 \tilde{f}_{\epsilon}^{+}}{\partial \mu \partial z}(\lambda, \mu, r, z) &= -\frac{1}{\mu(1 - \mu)} < 0. \end{aligned} $$

Since $\frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial z}(\lambda, \mu, r, g_{\epsilon}^{+}(\lambda, \mu, r)) = 0$, the implicit function theorem yields that

$$ \frac{\partial \tilde{g}_{\epsilon}^{+}}{\partial \mu}(\lambda, \mu, r) = - \frac{\frac{\partial^2 \tilde{f}_{\epsilon}^{+}}{\partial \mu \partial z}(\lambda, \mu, r, g_{\epsilon}^{+}(\lambda, \mu, r))}{\frac{\partial^2 \tilde{f}_{\epsilon}^{+}}{\partial z^2}(\lambda, \mu, r, g_{\epsilon}^{+}(\lambda, \mu, r))} > 0. $$
Moreover, for $\mu \in ([\lambda]_0^1, 1)$,

$$ 
\begin{aligned}
\frac{\partial \tilde{d}_{\epsilon}^{+}}{\partial \mu}(\lambda, \mu, r) &= \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial \mu}(\lambda, \mu, r, \tilde{g}_{\epsilon}^{+}(\lambda, \mu, r)) + \frac{\partial \tilde{g}_{\epsilon}^{+}}{\partial \mu}(\lambda, \mu, r) \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial z}(\lambda, \mu, r, \tilde{g}_{\epsilon}^{+}(\lambda, \mu, r)) \\
&= \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial \mu}(\lambda, \mu, r, \tilde{g}_{\epsilon}^{+}(\lambda, \mu, r)) = \frac{\mu - g_{\epsilon}^{+}(\mu) - x_{\epsilon}^{+}(\lambda, \mu, r)}{\mu(1 - \mu)} > 0,
\end{aligned}
$$

$$ \frac{\partial^2 \tilde{d}_{\epsilon}^{+}}{\partial \mu^2}(\lambda, \mu, r) = \frac{\partial^2 \tilde{f}_{\epsilon}^{+}}{\partial \mu^2}(\lambda, \mu, r, \tilde{g}_{\epsilon}^{+}(\lambda, \mu, r)) \frac{\partial \tilde{g}_{\epsilon}^{+}}{\partial \mu}(\lambda, \mu, r) > 0. $$

Therefore, for all $(\lambda, r) \in \mathbb{R} \times \mathbb{R}_+^*$, the function $\mu \mapsto \tilde{d}_{\epsilon}^+(\lambda, \mu, r)$ is positive, twice continuously differentiable, increasing and strictly convex on $([\lambda]_0^1, 1)$.

Let $(\mu, r) \in (0, 1) \times \mathbb{R}_+^*$. Direct computation yields that, for $z \in ([\lambda]_0^1, \mu) \subset (0, 1)$,

$$ \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial \lambda}(\lambda, \mu, r, z) = -\epsilon h'(r\epsilon(z - \lambda)) < 0, $$

$$ \frac{\partial^2 \tilde{f}_{\epsilon}^{+}}{\partial \lambda \partial z}(\lambda, \mu, r, z) = -r\epsilon^2 h''(r\epsilon(z - \lambda)) < 0. $$

Since $\frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial z}(\lambda, \mu, r, g_{\epsilon}^{+}(\lambda, \mu, r)) = 0$, the implicit function theorem yields that

$$ \frac{\partial \tilde{g}_{\epsilon}^{+}}{\partial \lambda}(\lambda, \mu, r) = - \frac{\frac{\partial^2 \tilde{f}_{\epsilon}^{+}}{\partial \lambda \partial z}(\lambda, \mu, r, g_{\epsilon}^{+}(\lambda, \mu, r))}{\frac{\partial^2 \tilde{f}_{\epsilon}^{+}}{\partial z^2}(\lambda, \mu, r, g_{\epsilon}^{+}(\lambda, \mu, r))} = \frac{r\epsilon^2 h''(r\epsilon(g_{\epsilon}^{+}(\lambda, \mu, r) - \lambda))}{\frac{1}{z(1-z)} + r\epsilon^2 h''(r\epsilon(g_{\epsilon}^{+}(\lambda, \mu, r) - \lambda))} < 1. $$

Direct computation yields that, for $\lambda \in (-\infty, \mu)$,

$$ 
\begin{aligned}
\frac{\partial \tilde{d}_{\epsilon}^{+}}{\partial \lambda}(\lambda, \mu, r) &= \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial \lambda}(\lambda, \mu, r, \tilde{g}_{\epsilon}^{+}(\lambda, \mu, r)) + \frac{\partial \tilde{g}_{\epsilon}^{+}}{\partial \lambda}(\lambda, \mu, r) \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial z}(\lambda, \mu, r, \tilde{g}_{\epsilon}^{+}(\lambda, \mu, r)) \\
&= \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial \lambda}(\lambda, \mu, r, \tilde{g}_{\epsilon}^{+}(\lambda, \mu, r)) = -\epsilon h'(r\epsilon(\tilde{g}_{\epsilon}^{+}(\lambda, \mu, r) - \lambda)) < 0,
\end{aligned}
$$

$$ \frac{\partial^2 \tilde{d}_{\epsilon}^{+}}{\partial \lambda^2}(\lambda, \mu, r) = r\epsilon^2 \left( 1 - \frac{\partial \tilde{g}_{\epsilon}^{+}}{\partial \lambda}(\lambda, \mu, r) \right) h''(r\epsilon(\tilde{g}_{\epsilon}^{+}(\lambda, \mu, r) - \lambda)) > 0. $$

Therefore, for all $(\lambda, r) \in (0, 1) \times \mathbb{R}_+^*$, the function $\lambda \mapsto \tilde{d}_{\epsilon}^+(\lambda, \mu, r)$ is positive, twice continuously differentiable, decreasing and strictly convex on $(-\infty, \mu)$. Similarly as above, it is direct to see that $\lim_{\lambda \to \mu^-} \tilde{d}_{\epsilon}^+(\lambda, \mu, r) = 0$ and $\lim_{\lambda \to -\infty} \tilde{d}_{\epsilon}^+(\lambda, \mu, r) = +\infty$.

Let $(\lambda, \mu) \in \mathbb{R} \times (0, 1)$. When $\mu \in (0, [\lambda]_0^1]$, we have $\tilde{d}_{\epsilon}^+(\lambda, \mu, r) = 0$ for all $r \in [1, +\infty)$, hence $r \mapsto \tilde{d}_{\epsilon}^+(\lambda, \mu, r)$ is non-decreasing. Let $\kappa$ as in Lemma 29. Using Lemma 29, we have

$$ \forall z > \lambda, \quad \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial r}(\lambda, \mu, r, z) = \frac{\partial \kappa}{\partial r}(r, \epsilon(z - \lambda)) > 0. $$

When $\mu \in ([\lambda]_0^1, 1)$, we have $\tilde{g}_{\epsilon}^{+}(\lambda, \mu, r) \in (\max\{\lambda, g_{\epsilon}^{+}(\mu)\}, \mu)$ and, for all $r > 0$,

$$ 
\begin{aligned}
\frac{\partial \tilde{d}_{\epsilon}^{+}}{\partial r}(\lambda, \mu, r) &= \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial r}(\lambda, \mu, r, \tilde{g}_{\epsilon}^{+}(\lambda, \mu, r)) + \frac{\partial \tilde{g}_{\epsilon}^{+}}{\partial r}(\lambda, \mu, r) \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial z}(\lambda, \mu, r, \tilde{g}_{\epsilon}^{+}(\lambda, \mu, r)) \\
&= \frac{\partial \tilde{f}_{\epsilon}^{+}}{\partial r}(\lambda, \mu, r, \tilde{g}_{\epsilon}^{+}(\lambda, \mu, r)) > 0,
\end{aligned}
$$

where we used that $\tilde{g}_{\epsilon}^{+}(\lambda, \mu, r) > \lambda$. This concludes the last part of the proof. $\square$

Lemma 32 gathers regularity properties on the modified divergences $\tilde{d}_{\epsilon}^-$. In particular, it gives a closed-form solution based on an implicit solution of a fixed-point equation. This is a key property used in our implementation to reduce the computational cost.
**Lemma 32.** Let $\tilde{d}_{\epsilon}^{-}$ as in Eq. (32), and $g_{\epsilon}^{\pm}$ as in Eq. (30). For all $\mu \in (0, 1)$, $\lambda \in \mathbb{R}$ and $r > 0$, we have

$$ \tilde{d}_{\epsilon}^{-}(\lambda, \mu, r) = \begin{cases} 0 & \text{if } \mu \in [[\lambda]_0^1, 1) \\ \mathrm{kl}(g_{\epsilon}^{-}(\mu) - x_{\epsilon}^{-}(\lambda, \mu, r), \mu) + \frac{1}{r}h(r\epsilon(x_{\epsilon}^{-}(\lambda, \mu, r) + \lambda - g_{\epsilon}^{-}(\mu))) & \text{if } \mu \in (0, [\lambda]_0^1] \end{cases}, $$

where $x_{\epsilon}^{-}(\lambda, \mu, r) := x_{\epsilon}^{+}(1 - \lambda, 1 - \mu, r) \in (\max\{g_{\epsilon}^{-}(\mu) - \lambda, 0\}, g_{\epsilon}^{-}(\mu) - \mu)$ is the solution for $x \in (\max\{g_{\epsilon}^{-}(\mu) - \lambda, 0\}, g_{\epsilon}^{-}(\mu) - \mu)$ of the equation

$$ \log \left( 1 + \frac{x}{(1 - g_{\epsilon}^{-}(\mu))(g_{\epsilon}^{-}(\mu) - x)} \right) + \epsilon \left( \frac{r\epsilon(x - g_{\epsilon}^{-}(\mu) + \lambda)}{\sqrt{(r\epsilon(x - g_{\epsilon}^{-}(\mu) + \lambda))^2 + 1 + 1}} - 1 \right) = 0. $$

For all $(\mu, r) \in (0, 1) \times \mathbb{R}_+^*$, the function $\lambda \mapsto \tilde{d}_{\epsilon}^{-}(\lambda, \mu, r)$ is positive, twice continuously differentiable, increasing and strictly convex on $(\mu, +\infty)$; it satisfies $\lim_{\lambda \to \mu^+} \tilde{d}_{\epsilon}^{+}(\lambda, \mu, r) = 0$ and $\lim_{\lambda \to +\infty} \tilde{d}_{\epsilon}^{-}(\lambda, \mu, r) = +\infty$.

For all $(\lambda, r) \in \mathbb{R} \times \mathbb{R}_+^*$, the function $\mu \mapsto \tilde{d}_{\epsilon}^{-}(\lambda, \mu, r)$ is positive, twice continuously differentiable, decreasing and strictly convex on $(0, [\lambda]_0^1)$. Moreover, we have

$$ \forall \mu \in (0, [\lambda]_0^1), \quad \frac{\partial \tilde{d}_{\epsilon}^{-}}{\partial \mu}(\lambda, \mu, r) = \frac{\mu - g_{\epsilon}^{-}(\mu) + x_{\epsilon}^{-}(\lambda, \mu, r)}{\mu(1 - \mu)}. $$

For all $(\lambda, \mu) \in \mathbb{R} \times (0, 1)$ such that $\mu \in (0, [\lambda]_0^1]$, the function $r \mapsto \tilde{d}_{\epsilon}^{-}(\lambda, \mu, r)$ is the zero function. For all $(\lambda, \mu) \in \mathbb{R} \times (0, 1)$ such that $\mu \in ([\lambda]_0^1, 1)$, the function $r \mapsto \tilde{d}_{\epsilon}^{-}(\lambda, \mu, r)$ is positive, continuously differentiable and increasing on $\mathbb{R}_+$.

**Proof.** Using Lemmas 27 and 24, we have

$$ \begin{aligned} \tilde{d}_{\epsilon}^{-}(\lambda, \mu, r) &= \tilde{d}_{\epsilon}^{+}(1 - \lambda, 1 - \mu, r) \quad \text{and} \quad g_{\epsilon}^{+}(\lambda) = 1 - g_{\epsilon}^{-}(1 - \lambda), \\ \frac{\partial \tilde{d}_{\epsilon}^{-}}{\partial \mu}(\lambda, \mu, r) &= -\frac{\partial \tilde{d}_{\epsilon}^{+}}{\partial \mu}(1 - \lambda, 1 - \mu, r) \quad \text{and} \quad \frac{\partial^2 \tilde{d}_{\epsilon}^{-}}{\partial \mu^2}(\lambda, \mu, r) = \frac{\partial^2 \tilde{d}_{\epsilon}^{+}}{\partial \mu^2}(1 - \lambda, 1 - \mu, r). \end{aligned} $$

Let $x_{\epsilon}^{+}(1 - \lambda, 1 - \mu, r) \in (\max\{0, g_{\epsilon}^{-}(\mu) - \lambda\}, g_{\epsilon}^{-}(\mu) - \mu)$ be the unique solution for $x \in (\max\{0, g_{\epsilon}^{-}(\mu) - \lambda\}, g_{\epsilon}^{-}(\mu) - \mu)$ of the equation

$$ \log \left( 1 + \frac{x}{(1 - g_{\epsilon}^{-}(\mu))(g_{\epsilon}^{-}(\mu) - x)} \right) + \epsilon \left( \frac{r\epsilon(x - g_{\epsilon}^{-}(\mu) + \lambda)}{\sqrt{(r\epsilon(x - g_{\epsilon}^{-}(\mu) + \lambda))^2 + 1 + 1}} - 1 \right) = 0, $$

where we used $g_{\epsilon}^{+}(1 - \mu) = 1 - g_{\epsilon}^{-}(\mu)$ to simplify the formula given in Lemma 31. Therefore, we define $x_{\epsilon}^{-}(\lambda, \mu, r) = x_{\epsilon}^{+}(1 - \lambda, 1 - \mu, r)$. Then, we have

$$ \begin{aligned} \mathrm{kl}(g_{\epsilon}^{-}(\mu) - x_{\epsilon}^{-}(\lambda, \mu, r), \mu) + \frac{1}{r}h(r\epsilon(x_{\epsilon}^{-}(\lambda, \mu, r) + \lambda - g_{\epsilon}^{-}(\mu))) &= \\ \mathrm{kl}(x_{\epsilon}^{+}(1 - \lambda, 1 - \mu, r) + g_{\epsilon}^{+}(1 - \mu), 1 - \mu) + \frac{h(r\epsilon(x_{\epsilon}^{+}(1 - \lambda, 1 - \mu, r) + g_{\epsilon}^{+}(1 - \mu) - 1 + \lambda))}{r} &= \mathrm{kl}(1 - g_{\epsilon}^{-}(\mu) + x_{\epsilon}^{-}(\lambda, \mu, r), 1 - \mu). \end{aligned} $$

where we used that $\mathrm{kl}(g_{\epsilon}^{-}(\mu) - x_{\epsilon}^{-}(\lambda, \mu, r), \mu) = \mathrm{kl}(1 - g_{\epsilon}^{-}(\mu) + x_{\epsilon}^{-}(\lambda, \mu, r), 1 - \mu)$. Combining the above with the properties on $\tilde{d}_{\epsilon}^{+}$ in Lemma 31 concludes the proof. $\square$

Lemma 33 shows that we can invert $\tilde{d}_{\epsilon}^{\pm}$ with respect to their first argument, which is a key property used in Appendix F.

**Lemma 33.** Let $\tilde{d}_{\epsilon}^{\pm}$ as in Eq. (32). For all $(\mu, r, c) \in (0, 1) \times \mathbb{R}_+^* \times \mathbb{R}_+^*$, there exists $x > 0$ such that $\tilde{d}_{\epsilon}^{+}(\mu - x, \mu, r) = c$. For all $(\mu, r, c) \in (0, 1) \times \mathbb{R}_+^* \times \mathbb{R}_+^*$, there exists $x > 0$ such that $\tilde{d}_{\epsilon}^{-}(\mu + x, \mu, r) = c$.
*Proof.* Let us define $f(x) = \tilde{d}_{\epsilon}^{+}(\mu - x, \mu, r)$ for all $x > 0$. Using Lemma 31, we know that $f$ is continuous and increasing on $\mathbb{R}_{+}^{*}$ and it satisfies $\lim_{x \to 0^{+}} f(x) = 0$ and $\lim_{x \to +\infty} f(x) = +\infty$. Therefore, there exists a unique $x > 0$ such that $\tilde{d}_{\epsilon}^{+}(\mu - x, \mu, r) = c$. Using Lemma 32, we can conclude similarly for $\tilde{d}_{\epsilon}^{-}$. $\square$

Lemma 33 shows that $\tilde{d}_{\epsilon}^{\pm}$ is non-decreasing with respect to their first argument, which is a key property used in Appendix F.

**Lemma 34.** Let $\tilde{d}_{\epsilon}^{\pm}$ as in Eq. (32). For all $(\mu, r) \in (0, 1) \times \mathbb{R}_{+}^{*}$ and all $(\lambda_1, \lambda_2) \in \mathbb{R} \times (-\infty, \mu)$,

$$ \tilde{d}_{\epsilon}^{+}(\lambda_1, \mu, r) \geq \tilde{d}_{\epsilon}^{+}(\lambda_2, \mu, r) \quad \implies \quad \lambda_1 \leq \lambda_2 $$

For all $(\mu, r) \in (0, 1) \times \mathbb{R}_{+}^{*}$ and all $(\lambda_1, \lambda_2) \in \mathbb{R} \times (\mu, +\infty)$,

$$ \tilde{d}_{\epsilon}^{-}(\lambda_1, \mu, r) \geq \tilde{d}_{\epsilon}^{-}(\lambda_2, \mu, r) \quad \implies \quad \lambda_1 \geq \lambda_2 $$

*Proof.* Using Lemma 31, we known that $\lambda \mapsto \tilde{d}_{\epsilon}^{+}(\lambda, \mu, r)$ is decreasing on $(-\infty, \mu)$. Let $(\lambda_1, \lambda_2) \in \mathbb{R} \times (-\infty, \mu)$. Then, we have

$$ \lambda_1 > \lambda_2 \quad \implies \quad \tilde{d}_{\epsilon}^{+}(\lambda_1, \mu, r) < \tilde{d}_{\epsilon}^{+}(\lambda_2, \mu, r), $$

which is equivalent to the statement of the lemma by contraposition. Using Lemma 32, we can conclude similarly for $\tilde{d}_{\epsilon}^{-}$. $\square$

## G.2 Transportation Cost

Recall that $W_{\epsilon,a,b}$ is defined in Eq. (50), i.e., for all $(\mu, w) \in \mathbb{R}^{K} \times \mathbb{R}_{+}^{K}$,

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

where $d_{\epsilon}^{\pm}$ are defined in Eq. (3).

Lemma 35 gathers regularity properties on the transportation costs.

**Lemma 35.** Let $d_{\epsilon}^{\pm}$ as in Eq. (3). For all $(\lambda, \mu) \in (0, 1)^2$ such that $\lambda \geq \mu$ and $w \in \mathbb{R}_{+}^2$.

* The function $u \mapsto w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)$ is strictly convex on $[\mu, \lambda]$ when $\max\{w_1, w_2\} > 0$ and on $[0, 1]$ when $\min\{w_1, w_2\} > 0$. Then,

$$ \inf_{u \in [0,1]} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\} = \inf_{u \in [\mu, \lambda]} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\}. $$

* The function $(\lambda, \mu, w) \mapsto \inf_{u \in [0,1]} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\}$ is continuous on $(0, 1) \times (0, 1) \times \mathbb{R}_{+}^2$.

* If $\max\{w_1, w_2\} > 0$, $u_{\star}(\lambda, \mu, w) = \arg \min_{u \in [0,1]} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\}$ is unique and continuous on $(0, 1) \times (0, 1) \times \mathbb{R}_{+}^2$.

* If $\min\{w_1, w_2\} > 0$ and $\lambda > \mu$, $u_{\star}(\lambda, \mu, w) \in (\mu, \lambda)$ and $\min\{d_{\epsilon}^{-}(\lambda, u_{\star}(\lambda, \mu, w)), d_{\epsilon}^{+}(\mu, u_{\star}(\lambda, \mu, w))\} > 0$.

Moreover,

$$ \inf_{u \in [0,1]} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\} = \inf_{(u_1, u_2) \in [0,1]^2 : u_1 \leq u_2} \{w_1 d_{\epsilon}^{-}(\lambda, u_1) + w_2 d_{\epsilon}^{+}(\mu, u_2)\}. $$

*Proof.* These results are obtained by leveraging Lemmas 25 and 26 at each step.

For $u \leq \mu$, the function is equal to $w_1 d_{\epsilon}^{-}(\lambda, u)$, which is decreasing and strictly convex on $[0, \lambda)$ unless $w_1 = 0$ since $u \leq \mu \leq \lambda$. Therefore, the minimum over that interval is attained at $\mu$. For $u \geq \lambda$, the function is equal to $w_2 d_{\epsilon}^{+}(\mu, u)$, which is increasing and strictly convex on $(\mu, 1]$ unless $w_2 = 0$ since $u \geq \lambda \geq \mu$. Therefore, the minimum over that interval is attained at $\lambda$. On the interval $(\mu, \lambda)$, the function is equal to $w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)$, hence it is the sum of two convex functions,
one of which is strictly convex. Furthermore, the function is continuous at $\mu$ and $\lambda$. This concludes the first part of the proof.

As we have just shown, we can restrict the infimum to $[\mu, \lambda]$. We apply Berge's Maximum theorem [Berge, 1997, page 116]. Let

$$\phi(u, \lambda, \mu, w) = -w_1 d_{\epsilon}^{-}(\lambda, u) - w_2 d_{\epsilon}^{+}(\mu, u),$$

$$\Gamma(\lambda, \mu, w) = [\mu, \lambda],$$

$$M(\lambda, \mu, w) = \max\{\phi(u, \lambda, \mu, w) \mid u \in \Gamma(\lambda, \mu, w)\},$$

$$\Phi(\lambda, \mu, w) = \arg \max\{\phi(u, \lambda, \mu, w) \mid u \in \Gamma(\lambda, \mu, w)\}.$$

We verify the hypotheses of the theorem:

* $\phi$ is continuous on $[\mu, \lambda] \times (0, 1) \times (0, 1) \times \mathbb{R}_+^2$, by using the properties in Lemmas 25 and 26 since $(\lambda, \mu) \in (0, 1)^2$.

* $\Gamma$ is nonempty, compact-valued and continuous (since constant).

We obtain that $M$ is continuous on $(0, 1) \times (0, 1) \times \mathbb{R}_+^2$ and that $\Phi$ is upper hemicontinuous. This concludes the second part of the proof.

When $\max\{w_1, w_2\} > 0$, we have just shown that $\phi$ is a strictly concave function of $u$. Combining this with the fact that $\Gamma$ is convex, we can argue as in [Sundaram, 1996, Theorem 9.17] to prove that $\Phi$ is a single-valued upper hemicontinuous correspondence, hence a continuous function. This concludes the third part of the proof.

Suppose that $\min\{w_1, w_2\} > 0$ and $\lambda > \mu$. Using Lemmas 25 and 26, the function $u \mapsto w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)$ is continuously differentiable on $(\mu, \lambda)$ with derivative $w_1 \frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, u) + w_2 \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, u)$ where

$$\forall u \in (\mu, 1], \quad \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, u) = \begin{cases} \frac{1-e^{-\epsilon}}{1-u(1-e^{-\epsilon})} & \text{if } u \in (g_{\epsilon}^{-}(\mu), 1] \\ \frac{u-\mu}{u(1-u)} & \text{if } u \in (\mu, g_{\epsilon}^{-}(\mu)] \end{cases},$$

$$\forall u \in [0, \lambda), \quad \frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, u) = \begin{cases} -\frac{e^{\epsilon}-1}{1+u(e^{\epsilon}-1)} & \text{if } u \in [0, g_{\epsilon}^{+}(\lambda)) \\ -\frac{\lambda-u}{u(1-u)} & \text{if } u \in [g_{\epsilon}^{+}(\lambda), \lambda). \end{cases}$$

Since $\frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, u) \to_{u \to \lambda^{-}} 0$ and $\frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, u) \to_{u \to \mu^{+}} 0$, we obtain

$$\lim_{u \to \lambda^{-}} \left\{ w_1 \frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, u) + w_2 \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, u) \right\} = w_2 \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, \lambda) > 0,$$

$$\lim_{u \to \mu^{+}} \left\{ w_1 \frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, u) + w_2 \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, u) \right\} = w_1 \frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, \mu) < 0.$$

Therefore, the infimum is attained inside the open interval. Using Lemmas 25 and 26, we can conclude the proof of the first part of the fourth property.

Using the strict convexity of $u_1 \mapsto w_1 d_{\epsilon}^{-}(\lambda, u_1)$ and $u_2 \mapsto w_2 d_{\epsilon}^{+}(\mu, u_2)$ on $(\mu, \lambda)$, we obtain that

$$\inf_{u \in (\mu, \lambda)} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\} = \inf_{(u_1, u_2) : \mu < u_1 \le u_2 < \lambda} \{w_1 d_{\epsilon}^{-}(\lambda, u_1) + w_2 d_{\epsilon}^{+}(\mu, u_2)\}.$$

Re-using the same arguments as above, we obtain that

$$\inf_{(u_1, u_2) : \mu < u_1 \le u_2 < \lambda} \{w_1 d_{\epsilon}^{-}(\lambda, u_1) + w_2 d_{\epsilon}^{+}(\mu, u_2)\} \\ = \inf_{(u_1, u_2) \in [0, 1]^2 : u_1 \le u_2} \{w_1 d_{\epsilon}^{-}(\lambda, u_1) + w_2 d_{\epsilon}^{+}(\mu, u_2)\}.$$

This concludes the proof of the second part of the fourth property. $\square$

Lemma 36 relates the transportation costs $W_{\epsilon,a^*,a}$ with the transportation costs used in Eq. (2) to define the characteristic time. Crucially, this shows the equivalence with the definitions in Eq. (35).
**Lemma 36.** Let $W_{\epsilon,a^*,a}$ and $d_\epsilon$ as in Eq. (4) and (1). Let $\mu \in (0,1)^K$ such that $a^*(\mu) = \{a^*\}$. Let $\text{Alt}(\mu) = \{\lambda \in (0,1)^K | a^*(\lambda) \neq \{a^*\}\}$. Then,

$$ \forall w \in \Delta_K, \quad \inf_{\lambda \in \text{Alt}(\mu)} \sum_{a \in [K]} w_a d_\epsilon(\mu_a, \lambda_a) = \min_{a \neq a^*} W_{\epsilon,a^*,a}(\mu, w). $$

*Proof.* It is direct to see that $\text{Alt}(\mu) = \bigcup_{a \neq a^*} C_a$ where $C_a = \{\lambda \in (0,1)^K | \lambda_a \ge \lambda_{a^*}\}$. Then,

$$ \forall w \in \Delta_K, \quad \inf_{\lambda \in \text{Alt}(\mu)} \sum_{a \in [K]} w_a d_\epsilon(\mu_a, \lambda_a) = \min_{a \neq a^*} \inf_{\lambda \in C_a} \sum_{c \in [K]} w_c d_\epsilon(\mu_c, \lambda_c). $$

By non-negativity of $d_\epsilon(\mu_a, \lambda_a)$ for all $a \in [K]$, we obtain

$$ \begin{aligned} \inf_{\lambda \in C_a} \sum_{c \in [K]} w_c d_\epsilon(\mu_c, \lambda_c) &= \inf_{\lambda \in C_a} \sum_{c \in \{a, a^*\}} w_c d_\epsilon(\mu_c, \lambda_c) \\ &= \inf_{(\lambda_a, \lambda_{a^*}) \in (0,1)^2, \lambda_a \ge \lambda_{a^*}} \sum_{c \in \{a, a^*\}} w_c d_\epsilon(\mu_c, \lambda_c), \end{aligned} $$

where the two equalities are obtained by choosing $\lambda(a) \in (0,1)^K$ such that $\lambda(a)_b = \mu_b$ for all $b \notin \{a, a^*\}$ with the two other coordinates chosen freely such that $\lambda(a)_a \ge \lambda(a)_{a^*}$. Using that $\mu_{a^*} > \mu_a$, we can partition this set as follows

$$ \begin{aligned} C_{a,a^*} &= \{(\lambda_a, \lambda_{a^*}) \in (0,1)^2 | \lambda_a \ge \lambda_{a^*}\} = \{(\lambda_a, \lambda_{a^*}) \in (0, \mu_a)^2 | \lambda_a \ge \lambda_{a^*}\} \\ &\quad \cup \{(\lambda_a, \lambda_{a^*}) \in [\mu_a, \mu_{a^*}] \times (0, \mu_a)\} \\ &\quad \cup \{(\lambda_a, \lambda_{a^*}) \in (\mu_{a^*}, 1)^2 | \lambda_a \ge \lambda_{a^*}\} \\ &\quad \cup \{(\lambda_a, \lambda_{a^*}) \in (\mu_{a^*}, 1) \times [\mu_a, \mu_{a^*}]\} \\ &\quad \cup \{(\lambda_a, \lambda_{a^*}) \in [\mu_a, \mu_{a^*}]^2 | \lambda_a \ge \lambda_{a^*}\}. \end{aligned} $$

Using Lemma 22, $\mu_{a^*} > \mu_a$ and Lemmas 25 and 26, we obtain

$$ \begin{aligned} & \inf_{(\lambda_a, \lambda_{a^*}) \in (0, \mu_a)^2 | \lambda_a \ge \lambda_{a^*}} \{w_{a^*} d_\epsilon(\mu_{a^*}, \lambda_{a^*}) + w_a d_\epsilon(\mu_a, \lambda_a)\} \\ &= \inf_{(\lambda_a, \lambda_{a^*}) \in (0, \mu_a)^2 | \lambda_a \ge \lambda_{a^*}} \{w_{a^*} d_\epsilon^-(\mu_{a^*}, \lambda_{a^*}) + w_a d_\epsilon^-(\mu_a, \lambda_a)\} = w_{a^*} d_\epsilon^-(\mu_{a^*}, \mu_a), \\ & \inf_{(\lambda_a, \lambda_{a^*}) \in [\mu_a, \mu_{a^*}] \times (0, \mu_a)} \{w_{a^*} d_\epsilon(\mu_{a^*}, \lambda_{a^*}) + w_a d_\epsilon(\mu_a, \lambda_a)\} \\ &= \inf_{(\lambda_a, \lambda_{a^*}) \in [\mu_a, \mu_{a^*}] \times (0, \mu_a)} \{w_{a^*} d_\epsilon^-(\mu_{a^*}, \lambda_{a^*}) + w_a d_\epsilon^+(\mu_a, \lambda_a)\} = w_{a^*} d_\epsilon^-(\mu_{a^*}, \mu_a), \\ & \inf_{(\lambda_a, \lambda_{a^*}) \in (\mu_{a^*}, 1)^2 | \lambda_a \ge \lambda_{a^*}} \{w_{a^*} d_\epsilon(\mu_{a^*}, \lambda_{a^*}) + w_a d_\epsilon(\mu_a, \lambda_a)\} \\ &= \inf_{(\lambda_a, \lambda_{a^*}) \in (\mu_{a^*}, 1)^2 | \lambda_a \ge \lambda_{a^*}} \{w_{a^*} d_\epsilon^+(\mu_{a^*}, \lambda_{a^*}) + w_a d_\epsilon^+(\mu_a, \lambda_a)\} = w_a d_\epsilon^+(\mu_a, \mu_{a^*}), \\ & \inf_{(\lambda_a, \lambda_{a^*}) \in [\mu_a, \mu_{a^*}]^2 | \lambda_a \ge \lambda_{a^*}} \{w_{a^*} d_\epsilon(\mu_{a^*}, \lambda_{a^*}) + w_a d_\epsilon(\mu_a, \lambda_a)\} \\ &= \inf_{(\lambda_a, \lambda_{a^*}) \in [\mu_a, \mu_{a^*}]^2 | \lambda_a \ge \lambda_{a^*}} \{w_{a^*} d_\epsilon^-(\mu_{a^*}, \lambda_{a^*}) + w_a d_\epsilon^+(\mu_a, \lambda_a)\}. \end{aligned} $$

Therefore, we obtain

$$ \begin{aligned} & \inf_{(\lambda_a, \lambda_{a^*}) \in C_{a,a^*}} \{w_{a^*} d_\epsilon(\mu_{a^*}, \lambda_{a^*}) + w_a d_\epsilon(\mu_a, \lambda_a)\} \\ &= \inf_{(\lambda_a, \lambda_{a^*}) \in [\mu_a, \mu_{a^*}]^2 | \lambda_a \ge \lambda_{a^*}} \{w_{a^*} d_\epsilon^-(\mu_{a^*}, \lambda_{a^*}) + w_a d_\epsilon^+(\mu_a, \lambda_a)\} \\ &= \inf_{u \in [\mu_a, \mu_{a^*}]^2} \{w_{a^*} d_\epsilon^-(\mu_{a^*}, u) + w_a d_\epsilon^+(\mu_a, u)\} \\ &= \inf_{u \in [0,1]} \{w_{a^*} d_\epsilon^-(\mu_{a^*}, u) + w_a d_\epsilon^+(\mu_a, u)\} = W_{\epsilon,a^*,a}(\mu, w), \end{aligned} $$
where the second equality is obtained similarly as in Lemma 35 by leveraging the strict convexity of $d_{\epsilon}^{\pm}$ in their second argument (see Lemmas 25 and 26). We used Lemma 35 and the definition of $W_{\epsilon,a^*,a}(\mu, w)$ for the last two equalities. This concludes the proof. $\square$

Lemma 37 gathers additional properties on the transportation costs.

**Lemma 37.** Let $d_{\epsilon}^{\pm}$ as in Eq. (3).

* Let $(\lambda, \mu) \in (0, 1)^2$ such that $\lambda > \mu$. When $w_2 > 0$, the function $w_1 \mapsto \min_{u \in [0,1]} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\}$ is increasing on $\mathbb{R}_+$. When $w_1 > 0$, the function $w_2 \mapsto \min_{u \in [0,1]} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\}$ is increasing on $\mathbb{R}_+$.

* Let $(\lambda, \mu) \in (0, 1)^2$ and $\mu \in (0, 1)^K$. The function $w \mapsto \min_{u \in [0,1]} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\}$ is concave on $\mathbb{R}_+^2$. The function $w \mapsto \min_{a \in [K]\setminus\{1\}} \min_{u \in [0,1]} \{w_1 d_{\epsilon}^{-}(\mu_1, u) + w_a d_{\epsilon}^{+}(\mu_a, u)\}$ is concave on $\mathbb{R}_+^K$.

*Proof.* Let $w_2 > 0$ and $w_1' > w_1 \ge 0$. Using Lemma 35, since $w_1' > 0$, there exists $u' \in [0, 1]$ with $d_{\epsilon}^{-}(\lambda, u') > 0$ such that

$$ \begin{aligned} \min_{u \in [0,1]} \{w_1' d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\} &= w_1' d_{\epsilon}^{-}(\lambda, u') + w_2 d_{\epsilon}^{+}(\mu, u') \\ &> w_1 d_{\epsilon}^{-}(\lambda, u') + w_2 d_{\epsilon}^{+}(\mu, u') \\ &\ge \min_{u \in [0,1]} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\}. \end{aligned} $$

Let $w_1 > 0$ and $w_2' > w_2 \ge 0$. Then, we can show similarly by using Lemma 35 that

$$ \min_{u \in [0,1]} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\} > \min_{u \in [0,1]} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\}. $$

This concludes the first part of the proof. The proof of the second part is direct since those functions are minimum of linear functions, hence concave. $\square$

Lemma 38 gives a closed-form solution for the transportation costs. This is a key property used in our implementation to reduce the computational cost.

**Lemma 38.** Let $d_{\epsilon}^{\pm}$ and $g_{\epsilon}^{\pm}$ as in Eq. (3) and (30). For all $(a, c) \in \mathbb{R}_+^2$ and $b \in \mathbb{R}$, let $r_{1,+}(a, b, c) := \frac{\sqrt{b^2+4ac}-b}{2a}$. For all $(\lambda, \mu) \in (0, 1)^2$ and $w \in \mathbb{R}_+^2$ such that $\min\{w_1, w_2\} > 0$ and $\lambda > \mu$.

* When (1) $g_{\epsilon}^{-}(\mu) \ge \lambda$, or (2) $g_{\epsilon}^{-}(\mu) < \lambda$, $g_{\epsilon}^{+}(\lambda) \le g_{\epsilon}^{-}(\mu)$ and $\frac{w_2\mu+w_1\lambda}{w_2+w_1} \in [g_{\epsilon}^{+}(\lambda), g_{\epsilon}^{-}(\mu)]$, we have $u_{\star}(\lambda, \mu, w) = \frac{w_2\mu+w_1\lambda}{w_2+w_1}$ and

$$ \min_{u \in [0,1]} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\} = w_1 \mathrm{kl}(\lambda, u_{\star}(\lambda, \mu, w)) + w_2 \mathrm{kl}(\mu, u_{\star}(\lambda, \mu, w)). $$

* When (3) $g_{\epsilon}^{-}(\mu) < \lambda$, $g_{\epsilon}^{+}(\lambda) > g_{\epsilon}^{-}(\mu)$ and $u_{3,\star}(w) \in [g_{\epsilon}^{-}(\mu), g_{\epsilon}^{+}(\lambda)]$ where

$$ u_{3,\star}(w) := \frac{w_1(e^{\epsilon} - 1) - w_2(1 - e^{-\epsilon})}{(w_2 + w_1)(1 - e^{-\epsilon})(e^{\epsilon} - 1)}, $$

we have $u_{\star}(\lambda, \mu, w) = u_{3,\star}(w)$ and

$$ \begin{aligned} \min_{u \in [0,1]} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\} \\ = w_1 (-\log(1 + u_{3,\star}(w)(e^{\epsilon} - 1)) + \epsilon\lambda) + w_2 (-\log(1 - u_{3,\star}(w)(1 - e^{-\epsilon})) - \epsilon\mu). \end{aligned} $$

* When (4) $g_{\epsilon}^{-}(\mu) < \lambda$, $g_{\epsilon}^{+}(\lambda) \le g_{\epsilon}^{-}(\mu)$ and $\frac{w_2\mu+w_1\lambda}{w_2+w_1} \in (\mu, g_{\epsilon}^{+}(\lambda))$, or (5) $g_{\epsilon}^{-}(\mu) < \lambda$, $g_{\epsilon}^{+}(\lambda) > g_{\epsilon}^{-}(\mu)$ and $u_{3,\star}(w) < g_{\epsilon}^{-}(\mu)$, we have $u_{\star}(\lambda, \mu, w) = u_{1,\star}(\mu, w)$ and

$$ \begin{aligned} u_{1,\star}(\mu, w) &:= r_{1,+}((w_2+w_1)(e^{\epsilon}-1), (w_2-(w_2\mu+w_1)(e^{\epsilon}-1)), w_2\mu), \\ \min_{u \in [0,1]} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\} \end{aligned} $$
$$= w_1(-\log(1 + u_{1,\star}(\mu, w)(e^{\epsilon} - 1)) + \epsilon\lambda) + w_2 \mathrm{kl}(\mu, u_{1,\star}(\mu, w)).$$

• When (6) $g_{\epsilon}^{-}(\mu) < \lambda$, $g_{\epsilon}^{+}(\lambda) \le g_{\epsilon}^{-}(\mu)$ and $\frac{w_2\mu+w_1\lambda}{w_2+w_1} \in (g_{\epsilon}^{-}(\mu), \lambda)$, or (7) $g_{\epsilon}^{-}(\mu) < \lambda$, $g_{\epsilon}^{+}(\lambda) > g_{\epsilon}^{-}(\mu)$ and $u_{3,\star}(w) > g_{\epsilon}^{+}(\lambda)$, we have $u_{\star}(\lambda, \mu, w) = u_{2,\star}(\lambda, w)$ and

$$ \begin{aligned} u_{2,\star}(\lambda, w) &:= 1 - r_{1,+}((w_2 + w_1)(e^{\epsilon} - 1), (w_1 - (w_1(1 - \lambda) + w_2)(e^{\epsilon} - 1)), w_1(1 - \lambda)) , \\ \min_{u \in [0,1]} & \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\} \\ &= w_1 \mathrm{kl}(\lambda, u_{2,\star}(\lambda, w)) + w_2 (-\log(1 - u_{2,\star}(\lambda, w)(1 - e^{-\epsilon})) - \epsilon\mu) . \end{aligned} $$

**Proof.** Suppose that $g_{\epsilon}^{-}(\mu) \ge \lambda$. Using Lemma 24, we know that $g_{\epsilon}^{-}(\mu) \ge \lambda$ if and only if $\mu \ge g_{\epsilon}^{+}(\lambda)$. Therefore, for all $u \in (\mu, \lambda)$, we have

$$w_1 \frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, u) + w_2 \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, u) = -w_1 \frac{\lambda - u}{u(1-u)} + w_2 \frac{u - \mu}{u(1-u)} = \frac{(w_2 + w_1)u - (w_2\mu + w_1\lambda)}{u(1-u)}.$$

Therefore, we have

$$u_{\star}(\lambda, \mu, w) = \frac{w_2\mu + w_1\lambda}{w_2 + w_1} \in (\mu, \lambda).$$

Suppose that $g_{\epsilon}^{-}(\mu) < \lambda$. Using Lemma 24, we know that $g_{\epsilon}^{-}(\mu) < \lambda$ if and only if $\mu < g_{\epsilon}^{+}(\lambda)$. Using strict convexity of the function on $(\mu, \lambda)$, it is enough to exhibit one local minimum to obtain a global minimum on $(\mu, \lambda)$.

Suppose that $g_{\epsilon}^{+}(\lambda) \le g_{\epsilon}^{-}(\mu)$. Similarly as above, we obtain, for all $u \in [g_{\epsilon}^{+}(\lambda), g_{\epsilon}^{-}(\mu)]$,

$$w_1 \frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, u) + w_2 \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, u) = \frac{(w_2 + w_1)u - (w_2\mu + w_1\lambda)}{u(1-u)}.$$

Suppose that $\frac{w_2\mu+w_1\lambda}{w_2+w_1} \in [g_{\epsilon}^{+}(\lambda), g_{\epsilon}^{-}(\mu)]$. Then, we can conclude as above that

$$u_{\star}(\lambda, \mu, w) = \frac{w_2\mu + w_1\lambda}{w_2 + w_1} \in [g_{\epsilon}^{+}(\lambda), g_{\epsilon}^{-}(\mu)],$$

since it is a local minimum of a strictly convex function.

Suppose that $\frac{w_2\mu+w_1\lambda}{w_2+w_1} < g_{\epsilon}^{+}(\lambda)$. Since the gradient is positive on $[g_{\epsilon}^{+}(\lambda), g_{\epsilon}^{-}(\mu)]$, we know that the minimum on $(\mu, \lambda)$ is achieved on $(\mu, g_{\epsilon}^{+}(\lambda))$, i.e., $u_{\star}(\lambda, \mu, w) \in (\mu, g_{\epsilon}^{+}(\lambda))$. Then, for all $u \in (\mu, g_{\epsilon}^{+}(\lambda))$,

$$w_1 \frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, u) + w_2 \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, u) = -w_1 \frac{e^{\epsilon} - 1}{1 + u(e^{\epsilon} - 1)} + w_2 \frac{u - \mu}{u(1 - u)}.$$

Using Lemma 24, direct computation yields

$$ \begin{aligned} w_1 \frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, u) + w_2 \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, u) > 0 &\iff \mu < u \left(1 + \frac{w_1}{w_2} \left(1 - \frac{g_{\epsilon}^{-}(u)}{u}\right)\right), \\ \lim_{u \to \mu^{+}} u \left(1 + \frac{w_1}{w_2} \left(1 - \frac{g_{\epsilon}^{-}(u)}{u}\right)\right) &= \mu \left(1 + \frac{w_1}{w_2} \left(1 - \frac{g_{\epsilon}^{-}(\mu)}{\mu}\right)\right) < \mu, \\ \lim_{u \to g_{\epsilon}^{+}(\lambda)^{-}} u \left(1 + \frac{w_1}{w_2} \left(1 - \frac{g_{\epsilon}^{-}(u)}{u}\right)\right) &= g_{\epsilon}^{+}(\lambda) \left(1 + \frac{w_1}{w_2} \left(1 - \frac{\lambda}{g_{\epsilon}^{+}(\lambda)}\right)\right) > \mu, \end{aligned} $$

where the second result uses that $u < g_{\epsilon}^{-}(u)$ and the last result is obtained by continuity of the differentials (Lemmas 25 and 26) and the positivity on $[g_{\epsilon}^{+}(\lambda), g_{\epsilon}^{-}(\mu)]$. For all $(a, c) \in \mathbb{R}_{+}^2$ and $b \in \mathbb{R}$, we define $r_{1,+}(a, b, c) = \frac{\sqrt{b^2+4ac-b}}{2a}$. Therefore, we have

$$ \begin{aligned} & w_1 \frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, u) + w_2 \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, u) = 0 \\ \iff & (w_2 + w_1)(e^{\epsilon} - 1)u^2 + (w_2 - (w_2\mu + w_1)(e^{\epsilon} - 1))u - w_2\mu = 0 \\ \iff & u_{\star}(\lambda, \mu, w) = r_{1,+}((w_2 + w_1)(e^{\epsilon} - 1), (w_2 - (w_2\mu + w_1)(e^{\epsilon} - 1)), w_2\mu) \in (\mu, g_{\epsilon}^{+}(\lambda)) \end{aligned} $$
where we used that $u_*(\lambda, \mu, w) \in (\mu, g_\epsilon^+(\lambda))$ is unique for the last equivalence, and that the second root of the second order polynomial equation is negative. Notice that $u_*(\lambda, \mu, w)$ is independent of $\lambda$.

Suppose that $\frac{w_2\mu+w_1\lambda}{w_2+w_1} > g_\epsilon^-(\mu)$. Since the gradient is negative on $[g_\epsilon^+(\lambda), g_\epsilon^-(\mu)]$, we know that the minimum on $(\mu, \lambda)$ is achieved on $(g_\epsilon^-(\mu), \lambda)$, i.e., $u_*(\lambda, \mu, w) \in (g_\epsilon^-(\mu), \lambda)$. Then, for all $u \in (g_\epsilon^-(\mu), \lambda)$,

$$w_1 \frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, u) + w_2 \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, u) = -w_1 \frac{\lambda - u}{u(1-u)} + w_2 \frac{1 - e^{-\epsilon}}{1 - u(1 - e^{-\epsilon})}.$$

Using Lemma 24, direct computation yields

$$\begin{align*}
w_1 \frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, u) + w_2 \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, u) < 0 &\iff \lambda > u \left(1 + \frac{w_2}{w_1} \left(1 - \frac{g_{\epsilon}^{+}(u)}{u}\right)\right), \\
\lim_{u \to \lambda^{-}} u \left(1 + \frac{w_2}{w_1} \left(1 - \frac{g_{\epsilon}^{+}(u)}{u}\right)\right) &= \lambda \left(1 + \frac{w_2}{w_1} \left(1 - \frac{g_{\epsilon}^{+}(\lambda)}{\lambda}\right)\right) > \lambda, \\
\lim_{u \to g_{\epsilon}^{-}(\mu)^{+}} u \left(1 + \frac{w_2}{w_1} \left(1 - \frac{g_{\epsilon}^{+}(u)}{u}\right)\right) &= g_{\epsilon}^{-}(\mu) \left(1 + \frac{w_2}{w_1} \left(1 - \frac{\mu}{g_{\epsilon}^{-}(\mu)}\right)\right) < \lambda,
\end{align*}$$

where the second result uses that $u > g_\epsilon^+(u)$ and the last result is obtained by continuity of the differentials (Lemmas 25 and 26) and the negativity on $[g_\epsilon^+(\lambda), g_\epsilon^-(\mu)]$.

Using Lemma 23, we obtain

$$\arg\min_{u \in [0,1]} \{w_1 d_{\epsilon}^{-}(\lambda, u) + w_2 d_{\epsilon}^{+}(\mu, u)\} = 1 - \arg\min_{u \in [0,1]} \{w_1 d_{\epsilon}^{+}(1-\lambda, u) + w_2 d_{\epsilon}^{-}(1-\mu, u)\}.$$

Using Lemma 24, we obtain

$$\begin{align*}
g_{\epsilon}^{-}(\mu) < \lambda &\iff g_{\epsilon}^{-}(1-\lambda) < 1-\mu, \\
\frac{w_2\mu + w_1\lambda}{w_2 + w_1} \in (g_{\epsilon}^{-}(\mu), \lambda) &\iff \frac{w_2(1-\mu) + w_1(1-\lambda)}{w_2 + w_1} \in (1-\lambda, g_{\epsilon}^{+}(1-\mu)).
\end{align*}$$

Therefore, we can leverage the above case to obtain $u_*(\lambda, \mu, w) = u_{2,*}(\lambda, w)$ where

$$u_{2,*}(\lambda, w) = 1 - r_{1,+}((w_2 + w_1)(e^{\epsilon} - 1), (w_1 - (w_1(1-\lambda) + w_2)(e^{\epsilon} - 1)), w_1(1-\lambda))$$

Notice that $u_*(\lambda, \mu, w)$ is independent of $\mu$.

Suppose that $g_\epsilon^-(\mu) < \lambda$ and $g_\epsilon^+(\lambda) > g_\epsilon^-(\mu)$. Similarly as above, we obtain, for all $u \in [g_\epsilon^-(\mu), g_\epsilon^+(\lambda)]$,

$$w_1 \frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, u) + w_2 \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, u) = -w_1 \frac{e^{\epsilon} - 1}{1 + u(e^{\epsilon} - 1)} + w_2 \frac{1 - e^{-\epsilon}}{1 - u(1 - e^{-\epsilon})}.$$

Therefore, we obtain

$$\begin{align*}
& w_1 \frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, u) + w_2 \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, u) > 0 \\
\iff & w_2(1 - e^{-\epsilon})(1 + u(e^{\epsilon} - 1)) - w_1(e^{\epsilon} - 1)(1 - u(1 - e^{-\epsilon})) > 0 \\
\iff & u > u_{3,*}(w) := \frac{w_1(e^{\epsilon} - 1) - w_2(1 - e^{-\epsilon})}{(w_2 + w_1)(1 - e^{-\epsilon})(e^{\epsilon} - 1)}.
\end{align*}$$

Suppose that $u_{3,*}(w) \in [g_\epsilon^-(\mu), g_\epsilon^+(\lambda)]$. Then, we can conclude as above that

$$u_*(\lambda, \mu, w) = u_{3,*}(w) \in [g_\epsilon^-(\mu), g_\epsilon^+(\lambda)],$$

since it is a local minimum of a strictly convex function. Notice that $u_{3,*}(w)$ is independent of $(\lambda, \mu)$.

Suppose that $u_{3,*}(w) > g_\epsilon^+(\lambda)$. Since the gradient is negative on $[g_\epsilon^-(\mu), g_\epsilon^+(\lambda)]$, we know that the minimum on $(\mu, \lambda)$ is achieved on $(g_\epsilon^+(\lambda), \lambda)$, i.e., $u_*(\lambda, \mu, w) \in (g_\epsilon^+(\lambda), \lambda)$. Then, for all $u \in (g_\epsilon^+(\lambda), \lambda)$,

$$w_1 \frac{\partial d_{\epsilon}^{-}}{\partial u}(\lambda, u) + w_2 \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu, u) = -w_1 \frac{\lambda - u}{u(1-u)} + w_2 \frac{1 - e^{-\epsilon}}{1 - u(1 - e^{-\epsilon})}.$$
This recovers the condition solved above. As we know that $u_*(\lambda, \mu, w) \in (g_\epsilon^+(\lambda), \lambda)$, we obtain $u_*(\lambda, \mu, w) = u_{2,*}(\lambda, w)$ where

$$u_{2,*}(\lambda, w) = 1 - r_{1,+}((w_2 + w_1)(e^{\epsilon} - 1), (w_1 - (w_1(1 - \lambda) + w_2)(e^{\epsilon} - 1)), w_1(1 - \lambda))$$

Suppose that $u_{3,*}(w) < g_\epsilon^-(\mu)$. Since the gradient is positive on $[g_\epsilon^-(\mu), g_\epsilon^+(\lambda)]$, we know that the minimum on $(\mu, \lambda)$ is achieved on $(\mu, g_\epsilon^-(\mu))$, i.e., $u_*(\lambda, \mu, w) \in (\mu, g_\epsilon^-(\mu))$. Then, for all $u \in (\mu, g_\epsilon^-(\mu))$,

$$w_1 \frac{\partial d_\epsilon^-}{\partial u}(\lambda, u) + w_2 \frac{\partial d_\epsilon^+}{\partial u}(\mu, u) = -w_1 \frac{e^\epsilon - 1}{1 + u(e^\epsilon - 1)} + w_2 \frac{u - \mu}{u(1 - u)}.$$

This recovers the condition solved above. As we know that $u_*(\lambda, \mu, w) \in (\mu, g_\epsilon^-(\mu))$, we obtain $u_*(\lambda, \mu, w) = u_{1,*}(\mu, w)$ where

$$u_{1,*}(\mu, w) = r_{1,+}((w_2 + w_1)(e^{\epsilon} - 1), (w_2 - (w_2\mu + w_1)(e^{\epsilon} - 1)), w_2\mu).$$

This concludes the proof.

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

### G.2.1 Modified Transportation Cost

Let $\eta > 0$ be the geometric parameter used for the geometric grid update of our private empirical mean estimator. Let us define

$$\forall x \ge 1, \quad r(x) := \frac{x}{1 + \log_{1+\eta} x}, \qquad (33)$$

which is increasing if and only if $x > \frac{e}{1+\eta}$. For all $(\mu, w) \in \mathbb{R}^K \times \mathbb{R}_+^K$ and all $(a, b) \in [K]^2$ such that $a \neq b$, we define

$$\tilde{W}_{\epsilon,a,b}(\mu, w) := 1 \left( [\mu_a]_0^1 > [\mu_b]_0^1 \right) \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\}, \quad (34)$$

where $\tilde{d}_\epsilon^\pm$ are defined in Eq. (32).

Lemma 39 gathers regularity properties of the function $r$ defined in Eq. (33).

**Lemma 39.** Let $r$ as in Eq. (33). Then,

$$\forall x \ge 1, \quad r'(x) = \frac{\log(x(1+\eta)/e)}{\log(1+\eta)(1+\log_{1+\eta} x)^2},$$

$$r''(x) = -\frac{1}{x(\log(1+\eta))^2} \frac{\log((1+\eta)xe^{-2})}{(1+\log_{1+\eta} x)^3}.$$

On $[1, +\infty)$, the function $r$ is twice continuously differentiable. It is decreasing on $[1, e/(1+\eta))$ and increasing on $(e/(1+\eta), +\infty)$; its minium is $r(e/(1+\eta)) \in (0, 1)$. It is strictly convex on $[1, e^2/(1+\eta))$ and strictly concave on $(e^2/(1+\eta), +\infty)$.

**Proof.** The proof is obtained by direct differentiation and manipulation. We have

$$\forall \eta > 0, \quad r(e/(1+\eta)) = \frac{e \log(1+\eta)}{1+\eta} \in (0, 1). \qquad \square$$

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

Lemma 40 shows that the modified transportation costs can be rewritten differently, which is a key property used in Appendix F.

**Lemma 40.** Let $\tilde{d}_\epsilon^\pm$ as in Eq. (32), and $r$ as in Eq. (33). For all $(\lambda, \mu) \in \mathbb{R}^2$ such that $[\lambda]_0^1 > [\mu]_0^1$ and $(w_1, w_2) \in [1, +\infty)^2$. Then,

$$\inf_{u \in (0,1)} \{w_1 \tilde{d}_\epsilon^-(\lambda, u, r(w_1)) + w_2 \tilde{d}_\epsilon^+(\mu, u, r(w_2))\}$$

$$= \inf_{u \in ([\mu]_0^1, [\lambda]_0^1)} \{w_1 \tilde{d}_\epsilon^-(\lambda, u, r(w_1)) + w_2 \tilde{d}_\epsilon^+(\mu, u, r(w_2))\}$$

$$= \inf_{(u_1, u_2) \in (0,1)^2: u_1 \le u_2} \{w_1 \tilde{d}_\epsilon^-(\lambda, u_1, r(w_1)) + w_2 \tilde{d}_\epsilon^+(\mu, u_2, r(w_2))\}.$$
Proof. These results are obtained by leveraging Lemmas 31 and 32.

Note that the condition $[\lambda]_0^1 > [\mu]_0^1$ implies that $\mu \in (-\infty, 1)$ and $\lambda \in (0, +\infty)$, i.e., $[\mu]_0^1 = \max\{0, \mu\}$ and $[\lambda]_0^1 = \min\{1, \lambda\}$.

Suppose that $\mu \le 0$ and $\lambda \ge 1$. Then, we have $[\mu]_0^1 = 0$ and $[\lambda]_0^1 = 1$. Therefore, the first part of the result holds by definition.

Suppose that $\mu \le 0$ and $\lambda \in (0, 1)$. Then, we have $[\mu]_0^1 = 0$ and $[\lambda]_0^1 = \lambda$. For $u \in [\lambda, 1)$, the function is equal to $w_2\tilde{d}_e^+(\mu, u, r(w_2))$, which is increasing and strictly convex on $(0, 1)$. Therefore, the minimum over that interval is attained at $\lambda$. For $u \in (0, \lambda)$, the function is equal to $w_1\tilde{d}_e^-(\lambda, u, r(w_1)) + w_2\tilde{d}_e^+(\mu, u, r(w_2))$. Since it is the sum of two strictly convex function, the minimum over that interval is achieved in $(0, \lambda)$. This concludes the proof of the first part of the result for this case.

Suppose that $\mu \in (0, 1)$ and $\lambda \ge 1$. Then, we have $[\mu]_0^1 = \mu$ and $[\lambda]_0^1 = 1$. For $u \in (0, \mu]$, the function is equal to $w_1\tilde{d}_e^-(\lambda, u, r(w_2))$, which is decreasing and strictly convex on $(0, 1)$. Therefore, the minimum over that interval is attained at $\mu$. For $u \in (\mu, 1)$, the function is equal to $w_1\tilde{d}_e^-(\lambda, u, r(w_1)) + w_2\tilde{d}_e^+(\mu, u, r(w_2))$. Since it is the sum of two strictly convex function, the minimum over that interval is achieved in $(\mu, 1)$. This concludes the proof of the first part of the result for this case.

Suppose that $(\mu, \lambda) \in (0, 1)^2$. Then, we have $[\mu]_0^1 = \mu$ and $[\lambda]_0^1 = \lambda$. For $u \in [\lambda, 1)$, the function is equal to $w_2\tilde{d}_e^+(\mu, u, r(w_2))$, which is increasing and strictly convex on $(0, 1)$. Therefore, the minimum over that interval is attained at $\lambda$. For $u \in (0, \mu]$, the function is equal to $w_1\tilde{d}_e^-(\lambda, u, r(w_1))$, which is decreasing and strictly convex on $(0, 1)$. Therefore, the minimum over that interval is attained at $\mu$. For $u \in (\mu, \lambda)$, the function is equal to $w_1\tilde{d}_e^-(\lambda, u, r(w_1)) + w_2\tilde{d}_e^+(\mu, u, r(w_2))$. Since it is the sum of two strictly convex function, the minimum over that interval is achieved in $(\mu, \lambda)$. This concludes the proof of the first part of the result for this case.

In summary, we have shown that

$$ \begin{aligned} & \inf_{u \in (0,1)} \{w_1 \tilde{d}_e^-(\lambda, u, r(w_1)) + w_2 \tilde{d}_e^+(\mu, u, r(w_2))\} \\ &= \inf_{u \in ([\mu]_0^1, [\lambda]_0^1)} \{w_1 \tilde{d}_e^-(\lambda, u, r(w_1)) + w_2 \tilde{d}_e^+(\mu, u, r(w_2))\}. \end{aligned} $$

Using the strict convexity of $u_1 \mapsto w_1\tilde{d}_e^-(\lambda, u_1, r(w_1))$ and $u_2 \mapsto w_2\tilde{d}_e^+(\mu, u_2, r(w_2))$ on $([\mu]_0^1, [\lambda]_0^1)$, we obtain that

$$ \begin{aligned} & \inf_{u \in ([\mu]_0^1, [\lambda]_0^1)} \{w_1 \tilde{d}_e^-(\lambda, u, r(w_1)) + w_2 \tilde{d}_e^+(\mu, u, r(w_2))\} \\ &= \inf_{(u_1, u_2) : [\mu]_0^1 < u_1 \le u_2 < [\lambda]_0^1} \{w_1 \tilde{d}_e^-(\lambda, u_1, r(w_1)) + w_2 \tilde{d}_e^+(\mu, u_2, r(w_2))\}. \end{aligned} $$

Re-using the same arguments as above, we obtain that

$$ \begin{aligned} & \inf_{(u_1, u_2) : [\mu]_0^1 < u_1 \le u_2 < [\lambda]_0^1} \{w_1 \tilde{d}_e^-(\lambda, u_1, r(w_1)) + w_2 \tilde{d}_e^+(\mu, u_2, r(w_2))\} = \\ &= \inf_{(u_1, u_2) \in (0,1)^2 : u_1 \le u_2} \{w_1 \tilde{d}_e^-(\lambda, u_1, r(w_1)) + w_2 \tilde{d}_e^+(\mu, u_2, r(w_2))\}. \end{aligned} $$

This concludes the proof. $\square$

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

Lemma 41 gives a closed-form solution for the modified transportation costs based on an implicit solution of a fixed-point equation. This is a key property used in our implementation to reduce the computational cost.

**Lemma 41.** Let $\tilde{d}_e^\pm$ as in Eq. (32), $x_e^\pm$ as in Lemmas 31 and 32, and $r$ as in Eq. (33). For all $(\lambda, \mu) \in \mathbb{R}^2$ such that $[\lambda]_0^1 > [\mu]_0^1$ and $w \in [1, +\infty)^2$. Then,

$$ \begin{aligned} & \inf_{u \in (0,1)} \{w_1 \tilde{d}_e^-(\lambda, u, r(w_1)) + w_2 \tilde{d}_e^+(\mu, u, r(w_2))\} \\ &= w_1 \tilde{d}_e^-(\lambda, u^*(\lambda, \mu, w), r(w_1)) + w_2 \tilde{d}_e^+(\mu, u^*(\lambda, \mu, w), r(w_2)), \end{aligned} $$
where $u^*(\lambda, \mu, w) \in ([\mu]_0^1, [\lambda]_0^1)$ is the unique solution for $u \in ([\mu]_0^1, [\lambda]_0^1)$ of the equation
$$u(w_1 + w_2) - w_1g_{\epsilon}^{-}(u) - w_2g_{\epsilon}^{+}(u) + w_1x_{\epsilon}^{-}(\lambda, u, r(w_1)) - w_2x_{\epsilon}^{+}(\lambda, u, r(w_2)) = 0.$$

*Proof.* Using Lemma 40, we have

$$
\begin{aligned}
& \inf_{u \in (0,1)} \{w_1 \tilde{d}_{\epsilon}^{-}(\lambda, u, r(w_1)) + w_2 \tilde{d}_{\epsilon}^{+}(\mu, u, r(w_2))\} \\
& = \inf_{u \in ([\mu]_0^1, [\lambda]_0^1)} \{w_1 \tilde{d}_{\epsilon}^{-}(\lambda, u, r(w_1)) + w_2 \tilde{d}_{\epsilon}^{+}(\mu, u, r(w_2))\}.
\end{aligned}
$$

Using Lemmas 32 and 31, we obtain

$$\forall u \in (0, [\lambda]_0^1), \quad \frac{\partial \tilde{d}_{\epsilon}^{-}}{\partial u}(\lambda, u, r(w_1)) = \frac{u - g_{\epsilon}^{-}(u) + x_{\epsilon}^{-}(\lambda, u, r(w_1))}{u(1-u)},$$

$$\forall u \in ([\mu]_0^1, 1), \quad \frac{\partial \tilde{d}_{\epsilon}^{+}}{\partial u}(\mu, u, r(w_2)) = \frac{u - g_{\epsilon}^{+}(u) - x_{\epsilon}^{+}(\mu, u, r(w_2))}{u(1-u)}.$$

Therefore, for all $u \in ([\mu]_0^1, [\lambda]_0^1)$,

$$
\begin{aligned}
& w_1 \frac{\partial \tilde{d}_{\epsilon}^{-}}{\partial u}(\lambda, u, r(w_1)) + w_2 \frac{\partial \tilde{d}_{\epsilon}^{+}}{\partial u}(\mu, u, r(w_2)) \\
& = \frac{w_1(u - g_{\epsilon}^{-}(u) + x_{\epsilon}^{-}(\lambda, u, r(w_1))) + w_2(u - g_{\epsilon}^{+}(u) - x_{\epsilon}^{+}(\mu, u, r(w_2)))}{u(1-u)} \\
& = \frac{u(w_1 + w_2) - (w_1g_{\epsilon}^{-}(u) + w_2g_{\epsilon}^{+}(u)) + w_1x_{\epsilon}^{-}(\lambda, u, r(w_1)) - w_2x_{\epsilon}^{+}(\mu, u, r(w_2))}{u(1-u)}.
\end{aligned}
$$

For $u \in ([\mu]_0^1, [\lambda]_0^1)$, let us define

$$g_1(u) := u(w_1 + w_2) - w_1 g_{\epsilon}^{-}(u) - w_2 g_{\epsilon}^{+}(u) + w_1 x_{\epsilon}^{-}(\lambda, u, r(w_1)) - w_2 x_{\epsilon}^{+}(\mu, u, r(w_2)).$$

Using the proof of Lemmas 32 and 31, we know that

$$
\begin{aligned}
\lim_{u \to [\mu]_0^1} \frac{\partial \tilde{d}_{\epsilon}^{+}}{\partial u}(\mu, u, r(w_1)) = 0 \quad \text{and} \quad \lim_{u \to [\lambda]_0^1} \frac{\partial \tilde{d}_{\epsilon}^{-}}{\partial u}(\lambda, u, r(w_1)) = 0, \\
\forall u \in (0, [\lambda]_0^1), \quad \frac{\partial \tilde{d}_{\epsilon}^{-}}{\partial u}(\lambda, u, r(w_1)) < 0 \quad \text{and} \quad \forall u \in ([\mu]_0^1, 1), \quad \frac{\partial \tilde{d}_{\epsilon}^{+}}{\partial u}(\mu, u, r(w_1)) > 0.
\end{aligned}
$$

Combined with the strict convexity of $\tilde{d}_{\epsilon}^{\pm}$ in their second argument, the equation $g_1(u) = 0$ admits a unique solution on $([\mu]_0^1, [\lambda]_0^1)$. Since $u(1-u) > 0$, we obtain the implicit equation defining $u^*(\lambda, \mu, w)$ as above. $\square$

### G.3 Characteristic Time

Let $\nu$ be a Bernoulli instance with means $\mu \in (0, 1)^2$ and unique best arm $a^* \in [K]$, i.e., $\arg\max_{a \in [K]} \mu_a = \{a^*\}$. For all $\beta \in (0, 1)$, we define

$$T_{\epsilon}^{*}(\boldsymbol{\nu})^{-1} = \sup_{w \in \triangle_K} \min_{a \neq a^{*}} W_{\epsilon, a^{*}, b}(\mu, w) \quad \text{and} \quad w_{\epsilon}^{*}(\boldsymbol{\nu}) = \arg \max_{w \in \triangle_K} \min_{a \neq a^{*}} W_{\epsilon, a^{*}, b}(\mu, w), \quad (35)$$

$$T_{\epsilon, \beta}^{*}(\boldsymbol{\nu})^{-1} = \sup_{w \in \triangle_K, w_{a^*} = \beta} \min_{a \neq a^*} W_{\epsilon, a^*, b}(\mu, w) \quad \text{and} \quad w_{\epsilon, \beta}^{*}(\boldsymbol{\nu}) = \arg \max_{w \in \triangle_K, w_{a^*} = \beta} \min_{a \neq a^*} W_{\epsilon, a^*, b}(\mu, w)$$

where $W_{\epsilon, a, b}$ are defined in Eq. (4).

Lemma 42 gathers regularity properties on the characteristic times and their optimal allocations.

**Lemma 42.** Let $W_{\epsilon, a, b}$ as in Eq. (4). Let $(T_{\epsilon}^{*}, T_{\epsilon, \beta}^{*})$ and $(w_{\epsilon}^{*}, w_{\epsilon, \beta}^{*})$ as in Eq. (35). The function $(\mu, w) \mapsto \min_{a \neq a^{*}} W_{\epsilon, a^{*}}(\mu, w)$ is continuous on $(0, 1)^K \times \triangle_K$. The functions $\nu \mapsto T_{\epsilon}^{*}(\nu)^{-1}$ and $\nu \mapsto T_{\epsilon, \beta}^{*}(\nu)^{-1}$ are continuous on $\mathcal{F}^K$. The correspondences $\nu \mapsto w_{\epsilon}^{*}(\nu)$ and $\nu \mapsto w_{\epsilon, \beta}^{*}(\nu)$ are upper hemicontinuous on $\mathcal{F}^K$ with compact convex values.
*Proof.* Let $\mathcal{F}_a^K = \{\boldsymbol{\nu} \in \mathcal{F}^K | a \in a^*(\boldsymbol{\nu})\}$. Since $\cup_{a \in [K]} \mathcal{F}_a^K = \mathcal{F}^K$, it is enough to show the property for all $\mathcal{F}_a^K$ for $a \in [K]$. Let $a^* \in [K]$.

First, the function $(w, \boldsymbol{\nu}) \mapsto \min_{a \neq a^*} \inf_{u \in [0,1]} \{w_{a^*} d_{\epsilon}^{-}(\mu_{a^*}, u) + w_a d_{\epsilon}^{+}(\mu_{a^*}, u)\}$ is continuous on $\Delta_K \times \mathcal{F}^K$ by Lemma 35 and the fact that a minimum of continuous functions is continuous. It is concave in $w$ by Lemma 37.

The correspondence $(w, \boldsymbol{\nu}) \mapsto \Delta_K$ is nonempty compact-valued and continuous (since constant). By Berge's maximum theorem, we get that $\boldsymbol{\nu} \mapsto T_{\epsilon}^{*}(\boldsymbol{\nu})^{-1}$ is continuous on $\mathcal{F}_{a^*}^K$ and that $\boldsymbol{\nu} \mapsto w_{\epsilon}^{*}(\boldsymbol{\nu})$ is upper hemicontinuous with compact values. By [Sundaram, 1996, Theorem 9.17], the concavity of the function being maximized implies that $\boldsymbol{\nu} \mapsto w_{\epsilon}^{*}(\boldsymbol{\nu})$ is convex-valued.

The correspondence $(w, \boldsymbol{\nu}) \mapsto \Delta_K \cap \{w_{a^*} = \beta\}$ is nonempty compact-valued and continuous (since constant). By Berge's maximum theorem, we get that $\boldsymbol{\nu} \mapsto T_{\epsilon, \beta}^{*}(\boldsymbol{\nu})^{-1}$ is continuous on $\mathcal{F}_{a^*}^K$ and that $w_{\beta}^{*}(\boldsymbol{\nu})$ is upper hemicontinuous with compact values. By [Sundaram, 1996, Theorem 9.17], the concavity of the function being maximized implies that $\boldsymbol{\nu} \mapsto w_{\epsilon, \beta}^{*}(\boldsymbol{\nu})$ is convex-valued. $\square$

Lemma 43 provides additional properties on the characteristic times and their optimal allocations. In particular, this results show that the $(\beta)$-optimal allocations is unique, has positive allocation for each arm and that the transportation costs are equal at equilibrium. Those properties are key in the analysis of a sampling rule.

**Lemma 43.** Let $W_{\epsilon,a,b}$ as in Eq. (4). Let $(T_{\epsilon}^{*}, T_{\epsilon,\beta}^{*})$ and $(w_{\epsilon}^{*}, w_{\epsilon,\beta}^{*})$ as in Eq. (35). Let $\beta \in (0,1)$ and $\boldsymbol{\nu} \in \mathcal{F}^K$ such that $a^*(\boldsymbol{\nu}) = \{a^*\}$ is a singleton.

* $T_{\epsilon}^{*}(\boldsymbol{\nu})^{-1} > 0$ and $T_{\epsilon,\beta}^{*}(\boldsymbol{\nu})^{-1} > 0$.

* $\min_{a \in [K]} w_a^* > 0$ and $\min_{a \in [K]} w_{\beta,a}^* > 0$ for all $w^* \in w_{\epsilon}^*(\boldsymbol{\nu})$ and $w_{\beta}^* \in w_{\epsilon,\beta}^*(\boldsymbol{\nu})$.

* the $(\beta)$-optimal allocations are unique and the transportation costs are all equals at equilibrium

$$w_{\epsilon}^{*}(\boldsymbol{\nu}) = \{w_{\epsilon}^{*}\} \quad \text{and} \quad \inf_{u \in [0,1]} \{w_{\epsilon,a^*} d_{\epsilon}^{-}(\mu_{a^*}, u) + w_{\epsilon,a} d_{\epsilon}^{+}(\mu_{a}, u)\} = T_{\epsilon}^{*}(\boldsymbol{\nu})^{-1},$$

$$w_{\epsilon,\beta}^{*}(\boldsymbol{\nu}) = \{w_{\epsilon,\beta}^{*}\} \quad \text{and} \quad \inf_{u \in [0,1]} \{w_{\epsilon,\beta,a^*} d_{\epsilon}^{-}(\mu_{a^*}, u) + w_{\epsilon,\beta,a} d_{\epsilon}^{+}(\mu_{a}, u)\} = T_{\epsilon,\beta}^{*}(\boldsymbol{\nu})^{-1}$$

*Proof.* Using the definition of the supremum with $1_K/K \in \Delta_K$ and Lemma 35, we obtain

$$T_{\epsilon}^{*}(\boldsymbol{\nu})^{-1} = \sup_{w \in \Delta_K} \min_{a \neq a^{*}} \inf_{u \in [0,1]} \{w_{a^{*}} d_{\epsilon}^{-}(\mu_{a^{*}}, u) + w_a d_{\epsilon}^{+}(\mu_a, u)\} \\ \geq \frac{1}{K} \min_{a \neq a^{*}} \inf_{u \in [0,1]} \{d_{\epsilon}^{-}(\mu_{a^{*}}, u) + d_{\epsilon}^{+}(\mu_a, u)\} > 0,$$

where the last inequality strict uses Lemma 35 and $\mu_a < \mu_{a^*}$ for all $a \neq a^*$. Similarly, we can prove that $T_{\epsilon,\beta}^*(\boldsymbol{\nu})^{-1} > 0$. This concludes the first part of the proof.

We proceed towards contradiction. Suppose that there exists $w^* \in w_{\epsilon}^*(\boldsymbol{\nu})$ and $b$ with $w_b^* = 0$. Then, we will show $T_{\epsilon}^*(\boldsymbol{\nu})^{-1} = 0$, which is a contradiction with the above result. If $b = a^*$ we have

$$T_{\epsilon}^{*}(\boldsymbol{\nu})^{-1} = \min_{a \neq a^{*}} \inf_{u \in [0,1]} w_{a}^{*} d_{\epsilon}^{+}(\mu_{a}, u) \leq \min_{a \neq a^{*}} w_{a}^{*} d_{\epsilon}^{+}(\mu_{a}, \mu_{a}) = 0.$$

If $b \neq a^*$, we have

$$T_{\epsilon}^{*}(\boldsymbol{\nu})^{-1} = \min_{a \neq a^{*}} \inf_{u \in [0,1]} \{w_{a}^{*} d_{\epsilon}^{-}(\mu_{a^{*}}, u) + w_{a}^{*} d_{\epsilon}^{+}(\mu_{a}, u)\} \\ \leq \inf_{u \in [0,1]} \{w_{a}^{*} d_{\epsilon}^{-}(\mu_{a^{*}}, u) + w_{b}^{*} d_{\epsilon}^{+}(\mu_{b}, u)\} = \inf_{u \in [0,1]} w_{a}^{*} d_{\epsilon}^{-}(\mu_{a^{*}}, u) = 0.$$

A similar proof allows to show the result for $w_{\epsilon,\beta}^*(\boldsymbol{\nu})$ by reasoning on $T_{\epsilon,\beta}^*(\boldsymbol{\nu})^{-1}$. This concludes the second part of the proof.

For notational simplicity, we assume without loss of generality that $a^* = 1$ is the best arm. At the optimal allocations, all $w_a$ are positive. Let us define $G_b(x) = \inf_{u \in [0,1]} \{d_{\epsilon}^{-}(\mu_1, u) + x d_{\epsilon}^{+}(\mu_b, u)\}$ for all $b \neq 1$. Let $w^* \in w_{\epsilon}^*(\boldsymbol{\nu})$. Then, we have

$$T_{\epsilon}^{*}(\boldsymbol{\nu})^{-1} = \max_{w \in \Delta_K, w_1 > 0} w_1 \min_{b \neq 1} G_b \left( \frac{w_b}{w_1} \right) \quad \text{and} \quad w^* \in \arg \max_{w \in \Delta_K} w_1 \min_{b \neq 1} G_b \left( \frac{w_b}{w_1} \right).$$
Introducing $x_b^* = \frac{w_b^*}{w_1^*}$ for all $b \neq 1$, using that $\sum_{b \in [K]} w_b^* = 1$, one has

$$w_1^* = \frac{1}{1 + \sum_{c \neq 1} x_c^*} \quad \text{and} \quad \forall b \neq 1, w_b^* = \frac{x_b^*}{1 + \sum_{c \neq 1} x_c^*}.$$

If $x^*$ is unique, then so is $w^*$. Since it is optimal, $\{x_b^*\}_{b=2}^K \in \mathbb{R}^{K-1}$ belongs to

$$\arg\max_{\{x_b\}_{b=2}^K \in \mathbb{R}^{K-1}} \frac{\min_{b \neq 1} G_b(x_b)}{1 + \sum_{c=2}^K x_c}. \quad (36)$$

Let's show that all the $G_b(x_b^*)$ have to be equal. Let $\mathcal{O} = \{a \in [K] \setminus \{1\} | G_a(x_a^*) = \min_{b \neq 1} G_b(x_b^*)\}$ and $\mathcal{A} = [K] \setminus (\{1\} \cup \mathcal{O})$. Assume that $\mathcal{A} \neq \emptyset$. For all $a \in \mathcal{A}$ and $b \in \mathcal{O}$, one has $G_b(x_b^*) > G_a(x_a^*)$. Using the continuity of the $G_b$ functions and the fact that they are increasing (Lemma 37), there exists $\epsilon > 0$ such that

$$\forall b \in \mathcal{A}, a \in \mathcal{O}, \quad G_b(x_b^* - \epsilon/|\mathcal{A}|) > G_a(x_a^* + \epsilon/|\mathcal{O}|) > G_a(x_a^*).$$

We introduce $\bar{x}_b = x_b^* - \epsilon/|\mathcal{A}|$ for all $b \in \mathcal{A}$ and $\bar{x}_a = x_a^* + \epsilon/|\mathcal{O}|$ for all $a \in \mathcal{O}$, hence $\sum_{b=2}^K \bar{x}_b = \sum_{b=2}^K x_b^*$. There exists $a \in \mathcal{O}$ such that $\min_{b \neq 1} G_b(\bar{x}_b) = G_a(x_a^* + \epsilon/|\mathcal{O}|)$, hence

$$\frac{\min_{b \neq 1} G_b(\bar{x}_b)}{1 + \bar{x}_2 + \dots + \bar{x}_K} = \frac{G_a(x_a^* + \epsilon/|\mathcal{O}|)}{1 + x_2^* + \dots + x_K^*} > \frac{G_a(x_a^*)}{1 + x_2^* + \dots + x_K^*} = \frac{\min_{b \neq 1} G_b(x_b^*)}{1 + x_2^* + \dots + x_K^*}.$$

This is a contradiction with the fact that $x^*$ belongs to (36). Therefore, we have $\mathcal{A} = \emptyset$.

We have proved that there is a unique value by $y^* \in \mathbb{R}_+$, such that for all $b \neq 1$, $G_b(x_b^*) = y^*$. Now since $G_b$ is increasing, this defines a unique value for $x_b^*$, equal to $G_b^{-1}(y^*)$.

For $y$ in the intersection of the ranges of all $G_b$, let $x_b(y) = G_b^{-1}(y)$. Then, $y^*$ belongs to

$$\arg\max_{y \in [0, \min_{b \neq 1} \lim_{+\infty} G_b(x))}} \frac{y}{1 + \sum_{b \neq 1} x_b(y)}. \quad (37)$$

For $\beta \in (0, 1)$, the same results (and proof) hold for $w_{\epsilon, \beta}^*(\boldsymbol{\nu})$ by noting that

$$T_{\epsilon, \beta}^*(\boldsymbol{\nu})^{-1} = \max_{w \in \Delta_K : w_1 = \beta} \beta \min_{b \neq 1} G_b(w_b / \beta).$$

Let $w_{\epsilon, \beta}^* \in w_{\epsilon, \beta}^*(\boldsymbol{\nu})$, since we have equality at the equilibrium, we obtain $\beta G_b(w_{\epsilon, \beta, b}^*/\beta) = T_{\epsilon, \beta}^*(\boldsymbol{\nu})^{-1}$ for all $b \neq 1$. Using the inverse mapping $x_b$, we obtain $w_{\epsilon, \beta, b}^* = \beta x_b (T_{\epsilon, \beta}^*(\boldsymbol{\nu})^{-1}/\beta)$ for all $b \neq 1$. This concludes the third part of the proof. $\square$

Lemma 44 shows that an asymptotically 1/2-optimal algorithm has an asymptotic expected sample complexity which is at worse twice the asymptotic expected sample complexity of an asymptotically optimal algorithm. This result motivates the recommendation to the practitioner of using $\beta = 1/2$ when no prior information is available on the true instance $\boldsymbol{\nu}$.

**Lemma 44.** Let $(T_{\epsilon}^*, T_{\epsilon, \beta}^*, w_{\epsilon}^*)$ as in Eq. (35). Let $\beta \in (0, 1)$ and $\boldsymbol{\nu} \in \mathcal{F}^K$ such that $a^*(\boldsymbol{\nu}) = \{a^*\}$ is a singleton. Then,

$$T_{\epsilon, 1/2}^*(\boldsymbol{\nu}) \le 2T_{\epsilon}^*(\boldsymbol{\nu}) \quad \text{and} \quad \frac{T_{\epsilon}^*(\boldsymbol{\nu})^{-1}}{T_{\epsilon, \beta}^*(\boldsymbol{\nu})^{-1}} \le \max \left\{ \frac{\beta^*}{\beta}, \frac{1-\beta^*}{1-\beta} \right\} \quad \text{with} \quad \beta^* = w_{\epsilon, a^*}^*.$$

*Proof.* Define for each non-negative vector $\psi \in \mathbb{R}_+^K$,

$$f(\psi) := \min_{a \neq a^*} \inf_{u \in [0,1]} \left\{ \psi_{a^*} d_{\epsilon}^{-}(\mu_{a^*}, u) + \psi_a d_{\epsilon}^{+}(\mu_a, u) \right\}.$$

$T_{\epsilon}^*(\boldsymbol{\nu})^{-1}$ is the maximum of $f(\psi)$ over probability vectors $\psi \in \Delta_K$. Here, we instead define $f$ for all non-negative vectors, and proceed by varying the total budget of measurement effort available
$\sum_{a \in [K]} \psi_a$. Using Lemma 37, $f$ is non-decreasing in $\psi_a$ for all $a$. $f$ is homogeneous of degree 1. That is $f(c\psi) = cf(\psi)$ for all $c \ge 1$. For each $c_1, c_2 > 0$ define

$$g(c_1, c_2) = \max \left\{ f(\psi) \mid \psi \in \mathbb{R}_+^K, \psi_{a^*}(\nu) = c_1, \sum_{a \neq a^*} \psi_a \le c_2, \right\}.$$

The function $g$ inherits key properties of $f$; it is also non-decreasing and homogeneous of degree 1. We have

$$T_{\epsilon, \beta}^{*}(\boldsymbol{\nu})^{-1} = \max \left\{ f(\psi) \mid \psi \in \mathbb{R}_{+}^{K}, \psi_{a^{*}} = \beta, \sum_{a \in [K]} \psi_{a} = 1 \right\} \\ = \max \left\{ f(\psi) \mid \psi \in \mathbb{R}_{+}^{K}, \psi_{a^{*}} = \beta, \sum_{a \neq a^{*}} \psi_{a} \le 1 - \beta \right\} = g(\beta, 1 - \beta),$$

where the second equality uses that $f$ is non-decreasing. Similarly, $T_{\epsilon}^{*}(\boldsymbol{\nu})^{-1} = g(\beta^{*}, 1 - \beta^{*})$ where $\beta^{*} = w_{\epsilon, a^{*}}^{*}$. Setting $r := \max \left\{ \frac{\beta^{*}}{\beta}, \frac{1-\beta^{*}}{1-\beta} \right\}$ implies $r\beta \ge \beta^{*}$ and $r(1-\beta) \ge 1 - \beta^{*}$. Therefore

$$r T_{\epsilon, \beta}^{*}(\boldsymbol{\nu})^{-1} = rg(\beta, 1-\beta) = g(r\beta, r(1-\beta)) \ge g(\beta^{*}, 1-\beta^{*}) = T_{\epsilon}^{*}(\boldsymbol{\nu})^{-1}.$$

Taking $\beta = \frac{1}{2}$, yields that $T_{\epsilon}^{*}(\boldsymbol{\nu})^{-1} \le 2 \max\{\beta^{*}, 1-\beta^{*}\} T_{1/2}^{*}(\boldsymbol{\nu})^{-1} \le 2T_{1/2}^{*}(\boldsymbol{\nu})^{-1}$. $\square$

Lemma 45 gives sufficient conditions on the means and allocations in order for the transportation costs to be equals to the non-private transportation costs. Moreover, it gives sufficient conditions on the means in order for this equality to hold irrespective of the considered allocation. Taken together, this result allows to have fine and coarse understanding of the separation between the high privacy regime and the low privacy regime for $\epsilon$-global DP BAI.

**Lemma 45.** Let $W_{\epsilon,a,b}$ as in Eq. (4). Let $\mu \in (0,1)^K$ such that $a^* = \arg\max_{a \in [K]} \mu_a$ is unique. Let $w \in (\mathbb{R}_+^*)^K$. Let $\epsilon > 0$. For all $x \in (0,1)$, we define $f_{\epsilon}(x) := (1-x) \left(1 - \frac{1}{1+x(e^{\epsilon}-1)}\right) = (1-x)g_{\epsilon}^{-}(x)(1-e^{-\epsilon})$. Let us define $\mu_{a^*,a}^w := \frac{w_{a^*,\mu_{a^*}^w} + w_a \mu_a}{w_{a^*} + w_a}$ for all $a \neq a^*$. For all $a \neq a^*$, we have

$$\mu_{a^*} - \mu_a \le \min \left\{ \left(1 + \frac{w_{a^*}}{w_a}\right) f_{\epsilon}(1 - \mu_{a^*}), \left(1 + \frac{w_a}{w_{a^*}}\right) f_{\epsilon}(\mu_a) \right\} \\ \implies W_{\epsilon, a^*, a}(\mu, w) = w_{a^*} \mathrm{kl}(\mu_{a^*}, \mu_{a^*, a}^w) + w_a \mathrm{kl}(\mu_a, \mu_{a^*, a}^w).$$

Moreover, we have

$$\max_{a^* \in [K], \mu \in (0,1)^K, a^*(\mu) = \{a^*\}, w \in (\mathbb{R}_+^*)^K} \min \left\{ \left(1 + \frac{w_{a^*}}{w_a}\right) f_{\epsilon}(1 - \mu_{a^*}), \left(1 + \frac{w_a}{w_{a^*}}\right) f_{\epsilon}(\mu_a) \right\} \le \epsilon/2$$

and, for all $a \neq a^*$, we have

$$\epsilon \ge \log \left( \frac{\mu_{a^*}(1 - \mu_a)}{\mu_a(1 - \mu_{a^*})} \right) = \frac{\partial \mathrm{kl}}{\partial x_1}(\mu_{a^*}, \mu_a) = \frac{\partial \mathrm{kl}}{\partial x_1}(\mu_a, \mu_{a^*}) \\ \implies \forall w \in (\mathbb{R}_+^*)^K, \quad W_{\epsilon, a^*, a}(\mu, w) = w_{a^*} \mathrm{kl}(\mu_{a^*}, \mu_{a^*, a}^w) + w_a \mathrm{kl}(\mu_a, \mu_{a^*, a}^w).$$

*Proof.* Let us define $f_{\epsilon}(x) = (1-x) \left(1 - \frac{1}{1+x(e^{\epsilon}-1)}\right)$ for all $x \in (0,1)$. Then, we have

$$\frac{\mu_a(1 - \mu_a)(e^{\epsilon} - 1)}{1 + \mu_a(e^{\epsilon} - 1)} = (1 - \mu_a) \left(1 - \frac{1}{1 + \mu_a(e^{\epsilon} - 1)}\right) = f_{\epsilon}(\mu_a), \\ \frac{\mu_{a^*}(1 - \mu_{a^*})(e^{\epsilon} - 1)}{e^{\epsilon} - \mu_{a^*}(e^{\epsilon} - 1)} = \mu_{a^*} \left(1 - \frac{1}{1 + (1 - \mu_{a^*})(e^{\epsilon} - 1)}\right) = f_{\epsilon}(1 - \mu_{a^*}).$$

Using Lemma 24, direct manipulation yields that

$$f_{\epsilon}(1 - \mu_{a^*}) < \mu_{a^*} - \mu_a \iff g_{\epsilon}^{+}(\mu_{a^*}) > \mu_a \iff f_{\epsilon}(\mu_a) < \mu_{a^*} - \mu_a$$
$$g_{\epsilon}^{-}(\mu_{a}) < \mu_{a^{*},a}^{w} \iff f_{\epsilon}(\mu_{a}) < \frac{w_{a^{*}}}{w_{a^{*}} + w_{a}}(\mu_{a^{*}} - \mu_{a}),$$

$$g_{\epsilon}^{+}(\mu_{a^{*}}) > \mu_{a^{*},a}^{w} \iff f_{\epsilon}(1 - \mu_{a^{*}}) < \frac{w_{a}}{w_{a^{*}} + w_{a}}(\mu_{a^{*}} - \mu_{a}).$$

Using that $\max\left\{\frac{w_a}{w_{a^*}+w_a}, \frac{w_{a^*}}{w_{a^*}+w_a}\right\} \le 1$, we obtain that

$$(g_{\epsilon}^{-}(\mu_{a}) < \mu_{a^{*}} \wedge g_{\epsilon}^{-}(\mu_{a}) < \mu_{a^{*},a}^{w}) \iff (1 + \frac{w_{a}}{w_{a^{*}}}) f_{\epsilon}(\mu_{a}) < \mu_{a^{*}} - \mu_{a},$$

$$(g_{\epsilon}^{-}(\mu_{a}) < \mu_{a^{*}} \wedge g_{\epsilon}^{+}(\mu_{a^{*}}) > \mu_{a^{*},a}^{w}) \iff (1 + \frac{w_{a^{*}}}{w_{a}}) f_{\epsilon}(1 - \mu_{a^{*}}) < \mu_{a^{*}} - \mu_{a},$$

$$(g_{\epsilon}^{-}(\mu_{a}) \geq \mu_{a^{*}} \lor (g_{\epsilon}^{-}(\mu_{a}) < \mu_{a^{*}} \wedge \mu_{a^{*},a}^{w} \in [g_{\epsilon}^{+}(\mu_{a^{*}}), g_{\epsilon}^{-}(\mu_{a})]))$$

$$\iff (g_{\epsilon}^{-}(\mu_{a}) \geq \mu_{a^{*}} \lor \mu_{a^{*},a}^{w} \in [g_{\epsilon}^{+}(\mu_{a^{*}}), g_{\epsilon}^{-}(\mu_{a})])$$

$$\iff (\min\{f_{\epsilon}(\mu_{a}), f_{\epsilon}(1 - \mu_{a^{*}})\} \geq \mu_{a^{*}} - \mu_{a})$$

$$\lor \mu_{a^{*}} - \mu_{a} \leq \min \left\{ \left(1 + \frac{w_{a^{*}}}{w_{a}}\right) f_{\epsilon}(1 - \mu_{a^{*}}), \left(1 + \frac{w_{a}}{w_{a^{*}}}\right) f_{\epsilon}(\mu_{a}) \right\}$$

$$\iff \mu_{a^{*}} - \mu_{a} \leq \max\{\min\{f_{\epsilon}(\mu_{a}), f_{\epsilon}(1 - \mu_{a^{*}})\},$$

$$\min \left\{ \left(1 + \frac{w_{a^{*}}}{w_{a}}\right) f_{\epsilon}(1 - \mu_{a^{*}}), \left(1 + \frac{w_{a}}{w_{a^{*}}}\right) f_{\epsilon}(\mu_{a}) \right\}$$

$$\iff \mu_{a^{*}} - \mu_{a} \leq \min \left\{ \left(1 + \frac{w_{a^{*}}}{w_{a}}\right) f_{\epsilon}(1 - \mu_{a^{*}}), \left(1 + \frac{w_{a}}{w_{a^{*}}}\right) f_{\epsilon}(\mu_{a}) \right\}.$$

Combining those conditions with Lemma 38 concludes the first part of the proof.

For all $x \in (0, 1)$, we have

$$f'_{\epsilon}(x) = \frac{(1-x)(e^{\epsilon} - 1) - x(e^{\epsilon} - 1)(1+x(e^{\epsilon} - 1))}{(1+x(e^{\epsilon} - 1))^2} = -(e^{\epsilon} - 1) \frac{x^2(e^{\epsilon} - 1) + 2x - 1}{(1+x(e^{\epsilon} - 1))^2},$$

$$f'_{\epsilon}(x) = 0 \iff x = \frac{e^{\epsilon/2} - 1}{e^{\epsilon} - 1},$$

$$\begin{aligned} f_{\epsilon}''(x) &= -2(e^{\epsilon} - 1) \frac{(1 + x(e^{\epsilon} - 1))^2 - (e^{\epsilon} - 1)(x^2(e^{\epsilon} - 1) + 2x - 1)}{(1 + x(e^{\epsilon} - 1))^3} \\ &= -\frac{2e^{\epsilon}(e^{\epsilon} - 1)}{(1 + x(e^{\epsilon} - 1))^3} \leq 0. \end{aligned}$$

As $f_{\epsilon}$ is strictly concave, the maximum is achieved at $\frac{e^{\epsilon/2}-1}{e^{\epsilon}-1}$ with value

$$\max_{x \in (0,1)} f_{\epsilon}(x) = f_{\epsilon}\left(\frac{e^{\epsilon/2}-1}{e^{\epsilon}-1}\right) = \frac{e^{\epsilon} - e^{\epsilon/2}}{e^{\epsilon}-1} \left(1 - e^{-\epsilon/2}\right) = \frac{(e^{\epsilon/2}-1)^2}{e^{\epsilon}-1}.$$

Let $\kappa_1(x) = x(e^x - 1) - 4(e^{x/2} - 1)^2$ for all $x > 0$. Then, we have

$$\frac{(e^{\epsilon/2} - 1)^2}{e^{\epsilon} - 1} \le \epsilon/4 \iff \kappa_1(\epsilon) \ge 0.$$

Then, we have $\kappa_1(0) = 0$ and

$$\kappa_1'(x) = 4e^{x/2} - 3e^x - 1 + xe^x \quad \text{and} \quad \kappa_1''(x) = e^x (2(e^{-x/2} - 1) + x).$$

Using that $e^{-x/2} - 1 \ge -x/2$, we obtain $\kappa_1''(x) \ge 0$. Using that $\kappa_1'(0) = 0$, we obtain $\kappa_1'(x) \ge 0$. Using that $\kappa_1(0) = 0$, we obtain $\kappa_1(x) \ge 0$. Therefore, we have shown that

$$\forall \epsilon > 0, \max_{x \in (0,1)} f_{\epsilon}(x) \le \epsilon/4.$$

Direct manipulation yields that

$$\min \left\{ \left(1 + \frac{w_{a^{*}}}{w_{a}}\right) f_{\epsilon}(1 - \mu_{a^{*}}), \left(1 + \frac{w_{a}}{w_{a^{*}}}\right) f_{\epsilon}(\mu_{a}) \right\}$$
$$ \leq \left( 1 + \min \left\{ \frac{w_{a^*}}{w_a}, \frac{w_a}{w_{a^*}} \right\} \right) \max_{x \in (0,1)} f_{\epsilon}(x) \leq \epsilon/2. $$

Taking the supremum over $w \in (\mathbb{R}_+^*)^K$, $\mu \in (0,1)^K$ such that $a^* = a^*(\mu)$ and over $a^* \in [K]$ concludes the second part of the proof.

Let $a \neq a^*$. Direct manipulations yield that

$$ \begin{align*} \mu_{a^*} - \mu_a &\le \min\{f_{\epsilon}(1 - \mu_{a^*}), f_{\epsilon}(\mu_a)\} \\ \implies \forall w \in (\mathbb{R}_+^*)^K, \quad \mu_{a^*} - \mu_a &\le \min\left\{\left(1 + \frac{w_{a^*}}{w_a}\right) f_{\epsilon}(1 - \mu_{a^*}), \left(1 + \frac{w_a}{w_{a^*}}\right) f_{\epsilon}(\mu_a)\right\} \\ \implies \forall w \in (\mathbb{R}_+^*)^K, \quad W_{\epsilon,a^*,a}(\mu, w) &= w_{a^*} \mathrm{kl}(\mu_{a^*}, \mu_{a^*,a}^w) + w_a \mathrm{kl}(\mu_a, \mu_{a^*,a}^w). \end{align*} $$

Recall that $f_{\epsilon}(x) = (1-x)\left(1-\frac{1}{1+x(e^{\epsilon}-1)}\right)$. Then, we have directly that

$$ f_{\epsilon}(x) \ge y \iff \frac{1-x-y}{1-x} \ge \frac{1}{1+x(e^{\epsilon}-1)} \iff \frac{(y+x)(1-x)}{x(1-x-y)} \le e^{\epsilon}. $$

Plugging this result, we obtain

$$ \begin{align*} \mu_{a^*} - \mu_a &\le \min\{f_{\epsilon}(1 - \mu_{a^*}), f_{\epsilon}(\mu_a)\} &\iff e^{\epsilon} &\ge \frac{\mu_{a^*}(1 - \mu_a)}{\mu_a(1 - \mu_{a^*})} \\ &\iff \epsilon &\ge \log\left(\frac{\mu_{a^*}(1 - \mu_a)}{\mu_a(1 - \mu_{a^*})}\right). \end{align*} $$

Recall that

$$ \frac{\partial \mathrm{kl}}{\partial x_1}(\mu_{a^*}, \mu_a) = \frac{\partial \mathrm{kl}}{\partial x_1}(\mu_a, \mu_{a^*}) = \log \left( \frac{\mu_{a^*}(1 - \mu_a)}{\mu_a(1 - \mu_{a^*})} \right). $$

This concludes the proof of the last part of the result.

□

Lemma 46 shows that our lower bound is larger (hence better) than the one derived in Azize et al. [2024].

**Lemma 46.** Let $T_g^*(\nu, \epsilon)$ as in Theorem 13 in Azize et al. [2024], and $T_\epsilon^*(\nu)$ as in Eq. (35). Then, we have $T_g^*(\nu, \epsilon) \le T_\epsilon^*(\nu)$.

*Proof.* Let $T_g^*(\nu, \epsilon)$ as in Theorem 13 in Azize et al. [2024]. A sufficient condition to obtain $T_g^*(\nu, \epsilon) \le T_\epsilon^*(\nu)$ is to show that, for all $\lambda \in \mathrm{Alt}(\mu)$, we have

$$ \sum_{a \in [K]} w_a d_{\epsilon}(\mu_a, \lambda_a) \le \min \left\{ \sum_{a \in [K]} w_a \mathrm{kl}(\mu_a, \lambda_a), 6\epsilon \sum_{a \in [K]} w_a |\mu_a - \lambda_a| \right\}, $$

since we can conclude by taking the infimum over $\lambda \in \mathrm{Alt}(\mu)$ and the supremum over $w \in \triangle_K$ on both sides of the inequalities. By definition of $d_\epsilon$ and evaluation the function at $z = \mu$ and $z = \lambda$ respectively, we obtain

$$ d_{\epsilon}(\lambda, \mu) = \inf_{z \in (0,1)} \{\mathrm{kl}(z, \mu) + \epsilon|\lambda - z|\} \le \min \{\mathrm{kl}(\lambda, \mu), \epsilon|\lambda - \mu|\}. $$

By summing those inequalities over arms $a \in [K]$, we obtain

$$ \begin{align*} \sum_{a \in [K]} w_a d_{\epsilon}(\mu_a, \lambda_a) &\le \sum_{a \in [K]} w_a \min\{\mathrm{kl}(\mu_a, \lambda_a), \epsilon|\mu_a - \lambda_a|\} \\ &\le \min \left\{ \sum_{a \in [K]} w_a \mathrm{kl}(\mu_a, \lambda_a), \epsilon \sum_{a \in [K]} w_a |\mu_a - \lambda_a| \right\}. \end{align*} $$

Using that $\sum_{a \in [K]} w_a |\mu_a - \lambda_a| \ge 0$ and $6\epsilon \ge \epsilon$, this concludes the proof.

□
In Garivier and Kaufmann [2016], the authors show how to rewrite the optimization problem underlying the characteristic time and its optimal allocation as a simpler optimization problem. Lemma 47 shows that similar properties holds for $\epsilon$-global DP BAI. In particular, it shows that computing the characteristic time $T_{\epsilon}^{*}(\nu)$ and their optimal allocation $w_{\epsilon}^{*}(\nu)$ can be done explicitly based on solving nested fixed-point equations. This result is key to implement computationally tractable Track-and-Stop algorithms. Additionally, Lemma 47 gives an explicit lower bound on the characteristic time $T_{\epsilon}^{*}(\nu)$.

**Lemma 47.** Let $d_{\epsilon}^{\pm}$ as in Eq. (3), and $(T_{\epsilon}^{*}, w_{\epsilon}^{*})$ as in Eq. (35). Let $a \neq a^{*}$. For $x \in [0, +\infty)$, let
$$G_a(x) := \inf_{u \in [0,1]} \{d_{\epsilon}^{-}(\mu_{a^{*}}, u) + x d_{\epsilon}^{+}(\mu_a, u)\} \quad \text{and} \quad u_a(x) := \arg \min_{u \in [\mu_a, \mu_{a^{*}}]} \{d_{\epsilon}^{-}(\mu_{a^{*}}, u) + x d_{\epsilon}^{+}(\mu_a, u)\}.$$

* The function $G_a$ is an increasing and strictly concave one-to-one mapping from $[0, +\infty)$ to $[0, d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_a))$; it satisfies that $G_a(0) = 0$ and $\lim_{x \to +\infty} G_a(x) = d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_a)$.

* The function $u_a$ is a decreasing one-to-one mapping from $[0, +\infty)$ to $(\mu_a, \mu_{a^{*}}]$; it satisfies that $u_a(0) = \mu_{a^{*}}$ and $\lim_{x \to +\infty} u_a(x) = \mu_a$.

* Let $x_a(y)$ be defined as the unique solution of $G_a(x) = y$ for all $y \in [0, d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_a))$. The function $x_a$ is an increasing and strictly convex one-to-one mapping from $[0, d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_a))$ to $[0, +\infty)$; it satisfies that $x_a(0) = 0$ and $\lim_{y \to d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_a)} x_a(y) = +\infty$.

For all $y \in [0, \min_{a \neq a^{*}} d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_a))$, let us define

$$G(y) := \frac{y}{1 + \sum_{a \neq a^*} x_a(y)} \quad \text{and} \quad F(y) := \sum_{a \neq a^*} \frac{d_{\epsilon}^{-}(\mu_{a^*}, u_a(x_a(y)))}{d_{\epsilon}^{+}(\mu_a, u_a(x_a(y)))}.$$

* The function $F$ is an increasing one-to-one mapping from $[0, \min_{a \neq a^{*}} d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_a))$ to $[0, +\infty)$; it satisfies that $F(0) = 0$ and $\lim_{y \to \min_{a \neq a^{*}} d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_a)} F(y) = +\infty$.

* On $[0, \min_{a \neq a^{*}} d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_a))$, the function $G$ is maximized at the unique $y^{*}$ solution in $[0, \min_{a \neq a^{*}} d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_a))$ of the fixed-point equation $F(y) = 1$. Moreover, we have $w_{\epsilon}^{*}(\nu)_{a} = w_{\epsilon}^{*}(\nu)_{a^{*}} x_a(y^{*})$ for all $a \neq a^{*}$,

$$w_{\epsilon}^{*}(\nu)_{a^{*}} = \frac{1}{1 + \sum_{a \neq a^{*}} x_a(y^{*})} \quad \text{and} \quad T_{\epsilon}^{*}(\nu)^{-1} = \frac{y^{*}}{1 + \sum_{a \neq a^{*}} x_a(y^{*})}.$$

* Moreover, we have

$$T_{\epsilon}^{*}(\nu) \geq \frac{1}{\min_{a \neq a^{*}} d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_{a})} + \sum_{a \neq a^{*}} \frac{1}{d_{\epsilon}^{+}(\mu_{a}, \mu_{a^{*}})}.$$

If $\epsilon < \log(\frac{\mu_a(1-\mu_b)}{\mu_b(1-\mu_a)})$, we have $d_{\epsilon}^{+}(\mu_a, \mu_{a^{*}}) = -\log(1 - \mu_{a^{*}}(1 - e^{-\epsilon})) - \epsilon\mu_a$ and $d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_a) = -\log(1 + \mu_a(e^{\epsilon} - 1)) + \epsilon\mu_{a^{*}}$.

**Proof.** Using Lemma 37, we know that $G_a$ is concave. Let $u_a(x) \in \arg \min_{x \in [0, +\infty)} \{d_{\epsilon}^{-}(\mu_{a^{*}}, u) + x d_{\epsilon}^{+}(\mu_a, u)\}$ for all $x \in [0, +\infty)$, whose explicit formula is given in Lemma 45. It is direct to see that $G_a(0) = 0$ and $u_a(0) = \mu_{a^{*}}$. Using the optimality condition of $u_a(x)$, we obtain, for all $x \in [0, +\infty)$,

$$G'_{a}(x) = u'_{a}(x) \left( \frac{\partial d_{\epsilon}^{-}}{\partial u}(\mu_{a^{*}}, u_{a}(x)) + x \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu_{a}, u_{a}(x)) \right) + d_{\epsilon}^{+}(\mu_{a}, u_{a}(x)) \\ = d_{\epsilon}^{+}(\mu_{a}, u_{a}(x)) > 0,$$

where the last inequality is obtained by Lemma 35 and using that $d_{\epsilon}^{+}(\mu_a, u_a(0)) = d_{\epsilon}^{+}(\mu_a, \mu_{a^{*}}) > 0$. Therefore, $G_a$ is an increasing one-to-one mapping from $[0, +\infty)$ to $[0, \lim_{x \to +\infty} G_a(x))$.

Let $\mu_{a^{*},a}^{x} = \frac{\mu_{a^{*}} + x\mu_{a}}{1+x}$ for all $x \in [0, +\infty)$. It is easy to see that $G_a(0) = 0$, $u_a(0) = \mu_{a^{*}}$ and $\lim_{x \to +\infty} \mu_{a^{*},a}^{x} = \mu_a$. Using Lemma 45, we obtain that

$$\lim_{x \to +\infty} \min \{(1 + 1/x) f_{\epsilon}(1 - \mu_{a^{*}}), (1 + x) f_{\epsilon}(\mu_{a})\} = f_{\epsilon}(1 - \mu_{a^{*}}).$$
When $\mu_{a^*} - \mu_a \le f_e(1 - \mu_{a^*})$, we obtain

$$
\begin{align*}
\lim_{x \to +\infty} G_a(x) &= \lim_{x \to +\infty} \left\{ \mathrm{kl}(\mu_{a^*}, \mu_{a^*,a}^x) + x \mathrm{kl}(\mu_a, \mu_{a^*,a}^x) \right\} \\
&= \mathrm{kl}(\mu_{a^*}, \mu_a) + \lim_{x \to +\infty} \left\{ x \mathrm{kl}(\mu_a, \mu_{a^*,a}^x) \right\} = \mathrm{kl}(\mu_{a^*}, \mu_a),
\end{align*}
$$

where we used that

$$
\begin{align*}
x \mathrm{kl}(\mu_a, \mu_{a^*,a}^x) &= x \left( \mu_a \log \left( 1 - \frac{\mu_{a^*} - \mu_a}{\mu_a(1-\mu_a)} \frac{1}{\frac{\mu_{a^*}}{\mu_a} + x} \right) + \log \left( 1 + \frac{\mu_{a^*} - \mu_a}{1-\mu_a} \frac{1}{\frac{1-\mu_{a^*}}{1-\mu_a} + x} \right) \right), \\
\lim_{x \to +\infty} \{x \mathrm{kl}(\mu_a, \mu_{a^*,a}^x)\} &= \frac{(\mu_{a^*} - \mu_a)^2}{\mu_a(1-\mu_a)^2} \lim_{x \to +\infty} \left\{ \frac{x}{\left( \frac{\mu_{a^*}}{\mu_a} + x \right) \left( \frac{1-\mu_{a^*}}{1-\mu_a} + x \right)} \right\} = 0,
\end{align*}
$$

where we used that $\log(1+x) = \lim_{x \to 0} x + O(x^2)$. Using Lemma 26 and the proof of Lemma 45, we
know that $\mu_{a^*} - \mu_a \le f_e(1 - \mu_{a^*})$ if and only if $\mu_a \in [g_e^+(\mu_{a^*}), \mu_{a^*})$, hence we have $\mathrm{kl}(\mu_{a^*}, \mu_a) =
d_e^-(\mu_{a^*}, \mu_a)$. This concludes the proof in the first case.

When $\mu_{a^*} - \mu_a > f_e(1 - \mu_{a^*})$, we obtain

$$
\lim_{x \to +\infty} G_a(x) = \lim_{x \to +\infty} \{-\log(1 + u_{1,\star}(\mu_a, x)(e^\epsilon - 1)) + \epsilon\mu_{a^*} + x\mathrm{kl}(\mu_a, u_{1,\star}(\mu_a, x))\},
$$

where

$$
u_{1,\star}(\mu_a, x) = \frac{\sqrt{(x(1 - \mu_a(e^\epsilon - 1)) - (e^\epsilon - 1))^2 + 4(1 + x)(e^\epsilon - 1)x\mu_a - (x(1 - \mu_a(e^\epsilon - 1)) - (e^\epsilon - 1))}}{2(1 + x)(e^\epsilon - 1)}.
$$

Direct manipulation yields that $\lim_{x \to +\infty} u_{1,\star}(\mu_a, x) = \mu_a$, hence

$$
\lim_{x \to +\infty} G_a(x) = -\log(1 + \mu_a(e^\epsilon - 1)) + \epsilon\mu_{a^*} + \lim_{x \to +\infty} \{x\mathrm{kl}(\mu_a, u_{1,\star}(\mu_a, x))\}.
$$

Let us denote $v_{1,\star}(\mu_a, x) = u_{1,\star}(\mu_a, x) - \mu_a \ge 0$, i.e., $\lim_{x \to +\infty} v_{1,\star}(\mu_a, x) = 0$. Direct manipula-
tion yields that

$$
\begin{align*}
v_{1,\star}(\mu_a, x) &= \frac{1 + \mu_a(e^\epsilon - 1)}{2(e^\epsilon - 1)} \left(1 - \frac{1}{x+1}\right) \\
&\quad \left( \sqrt{1 - \frac{2x(1 - \mu_a(e^\epsilon + 1))(e^\epsilon - 1) - (e^\epsilon - 1)^2}{x^2(1 + \mu_a(e^\epsilon - 1))^2}} - 1 + \frac{(e^\epsilon - 1)(1 - 2\mu_a)}{x(1 + \mu_a(e^\epsilon - 1))} \right) \\
&= \sqrt{1 - \frac{2x(1 - \mu_a(e^\epsilon + 1))(e^\epsilon - 1) - (e^\epsilon - 1)^2}{x^2(1 + \mu_a(e^\epsilon - 1))^2}} - 1 + \frac{(e^\epsilon - 1)(1 - 2\mu_a)}{x(1 + \mu_a(e^\epsilon - 1))} \\
&= \lim_{x \to +\infty} \frac{(e^\epsilon - 1)(1 - 2\mu_a)}{x(1 + \mu_a(e^\epsilon - 1))} - \frac{2x(1 - \mu_a(e^\epsilon + 1))(e^\epsilon - 1) - (e^\epsilon - 1)^2}{2x^2(1 + \mu_a(e^\epsilon - 1))^2} + \mathcal{O}(1/x^2) \\
&= \lim_{x \to +\infty} \frac{2x(e^\epsilon - 1)2(1 - \mu_a)\mu_a(e^\epsilon - 1) + (e^\epsilon - 1)^2}{2x^2(1 + \mu_a(e^\epsilon - 1))^2} + \mathcal{O}(1/x^2),
\end{align*}
$$

$$
\text{hence } v_{1,\star}(\mu_a, x) = \lim_{x \to +\infty} \frac{2(1 - \mu_a)\mu_a(e^\epsilon - 1)^2}{x(1 + \mu_a(e^\epsilon - 1))^2} + \mathcal{O}(1/x^2).
$$

where we used that $\sqrt{1-x}-1 = \lim_{x \to 0} -x/2 + O(x^2)$ to obtain the last result. Similarly as before,
we derive

$$
\mathrm{kl}(\mu_a, u_{1,\star}(\mu_a, x)) = x \left( \mu_a \log \left( 1 - \frac{1}{\mu_a(1-\mu_a)} \frac{v_{1,\star}(\mu_a, x)}{1 + v_{1,\star}(\mu_a, x)/\mu_a} \right) \right. \\
\left. + \log \left( 1 + \frac{1}{1-\mu_a} \frac{v_{1,\star}(\mu_a, x)}{1 - v_{1,\star}(\mu_a, x)/(1-\mu_a)} \right) \right)
$$
$$
\lim_{x \to +\infty} \{xkl(\mu_a, \mu_{a^*,a}^x)\} = \frac{1}{\mu_a(1-\mu_a)^2} \lim_{x \to +\infty} \left\{ \frac{xv_{1,*}(\mu_a, x)^2}{\left(1 - \frac{v_{1,*}(\mu_a, x)}{1-\mu_a}\right) \left(1 + \frac{v_{1,*}(\mu_a, x)}{\mu_a}\right)} \right\} \\
= \frac{\lim_{x \to +\infty} xv_{1,*}(\mu_a, x)^2}{\mu_a(1-\mu_a)^2} = 0,
$$

where we used that $v_{1,*}(\mu_a, x) = x \to +\infty \mathcal{O}(1/x)$ to conclude. Therefore, we have shown that $\lim_{x \to +\infty} G_a(x) = -\log(1+\mu_a(e^\epsilon-1)) + \epsilon\mu_a^*$. Using Lemma 26 and the proof of Lemma 45, we know that $\mu_a^* - \mu_a > f_e(1-\mu_a^*)$ if and only if $\mu_a \in [0, g_e^+(\mu_a^*))$, hence we have $-\log(1+\mu_a(e^\epsilon-1)) + \epsilon\mu_a^* = d_e^-(\mu_a^*, \mu_a)$. This concludes the proof in the second case.

Therefore, $G_a$ is a strictly increasing one-to-one mapping from $[0, +\infty)$ to $[0, d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_{a})]$. Using the implicit function theorem, we obtain

$$
\forall x \in [0, +\infty), \quad u'_{a}(x) = - \frac{\frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu_{a}, u_{a}(x))}{\frac{\partial^{2} d_{\epsilon}^{-}}{\partial u^{2}}(\mu_{a^{*}}, u_{a}(x)) + x \frac{\partial^{2} d_{\epsilon}^{+}}{\partial u^{2}}(\mu_{a}, u_{a}(x))} < 0,
$$

where the strict inequality is obtained by using properties in Lemmas 25 and 26, since $u_a(x) \in (\mu_a, \mu_{a^*})$ by Lemmas 35 and 25. Similarly, we obtain

$$
\forall x \in [0, +\infty), \quad G_a''(x) = u_a'(x) \frac{\partial d_e^+}{\partial u}(\mu_a, u_a(x)) > 0,
$$

Therefore, we have shown that $G_a$ is strictly concave and that $u_a$ is decreasing.

Let us define $x_a(y)$ as the unique solution of $G_a(x) = y$, which is well-defined based on our above computations. Therefore, we have

$$
y = d_{\epsilon}^{-}(\mu_{a^{*}}, u_{a}(x_{a}(y))) + x_{a}(y)d_{\epsilon}^{+}(\mu_{a}, u_{a}(x_{a}(y))).
$$

Using the derivative of the inverse function, we obtain

$$
\forall y \in [0, d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_{a})), \quad x'_{a}(y) = \frac{1}{G'_{a}(x_{a}(y))} = \frac{1}{d_{\epsilon}^{+}(\mu_{a}, u_{a}(x_{a}(y)))} > 0,
$$

hence $x_a$ is increasing on $[0, d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_{a}))$. Moreover, we have

$$
\forall y \in [0, d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_{a})), \quad x_{a}''(y) = - \frac{u'_{a}(x_{a}(y))}{d_{\epsilon}^{+}(\mu_{a}, u_{a}(x_{a}(y)))^{3}} \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu_{a}, u_{a}(x_{a}(y))) > 0,
$$

hence $x_a$ is strictly convex on $[0, d_{\epsilon}^{-}(\mu_{a^{*}}, \mu_{a}))$.

For all $y \in [0, \min_{a \neq a^*} d_{\epsilon}^{-}(\mu_{a^*}, \mu_a))$, let us define $G(y) = \frac{y}{1 + \sum_{a \neq a^*} x_a(y)}$ and $F(y) = \sum_{a \neq a^*} \frac{d_{\epsilon}^{-}(\mu_{a^*}, u_a(x_a(y)))}{d_{\epsilon}^{+}(\mu_a, u_a(x_a(y)))}$. Using the above results, direct manipulations yield that, for all $y \in [0, \min_{a \neq a^*} d_{\epsilon}^{-}(\mu_{a^*}, \mu_a))$,

$$
\begin{align*}
G'(y) &= \frac{1 + \sum_{a \neq a^*} x_a(y) - y \sum_{a \neq a^*} x_a'(y)}{(1 + \sum_{a \neq a^*} x_a(y))^2} \\
&= \frac{1 + \sum_{a \neq a^*} x_a(y) - \sum_{a \neq a^*} \frac{y}{d_{\epsilon}^{+}(\mu_a, u_a(x_a(y)))}}{(1 + \sum_{a \neq a^*} x_a(y))^2} \\
&= \frac{1 - F(y)}{(1 + \sum_{a \neq a^*} x_a(y))^2},
\end{align*}
$$

hence we obtain that $G'(y) = 0$ if and only if $F(y) = 1$. Using that $x_a(0) = 0$, $u_a(0) = \mu_a^*$ and $d_{\epsilon}^{-}(\mu_a^*, \mu_a^*) = 0$, we obtain that $F(0) = 0$.

Using that $\lim_{y \to d_{\epsilon}^{-}(\mu_{a^*}, \mu_a)} x_a(y) = +\infty$, $\lim_{x \to +\infty} u_a(x) = \mu_a$, $d_{\epsilon}^{-}(\mu_a^*, \mu_a) > 0$ and $d_{\epsilon}^{+}(\mu_a, \mu_a) = 0$, we obtain that $\lim_{y \to \min_{a \neq a^*} d_{\epsilon}^{-}(\mu_a^*, \mu_a)} F(y) = +\infty$.

Let $H(y) = \sum_{a \neq a^*} \frac{1}{d_{\epsilon}^{+}(\mu_a, u_a(x_a(y)))}$ for all $y \in [0, \min_{a \neq a^*} d_{\epsilon}^{-}(\mu_a^*, \mu_a))$. Then, we have

$$
\sum_{a \neq a^*} x_a(y) = yH(y) - F(y) \quad , \quad \sum_{a \neq a^*} x_a'(y) = H(y),
$$
$$ \frac{\partial d_{\epsilon}^{-}}{\partial u}(\mu_{a^{*}}, u_{a}(x)) + x \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu_{a}, u_{a}(x)) = 0, \\ d_{\epsilon}^{-}(\mu_{a^{*}}, u_{a}(x_{a}(y))) + x_{a}(y)d_{\epsilon}^{+}(\mu_{a}, u_{a}(x_{a}(y))) = y. $$

Then, for all $y \in [0, \min_{a \neq a^*} d_{\epsilon}^{-}(\mu_{a^*}, \mu_a))$, we have

$$ H'(y) = - \sum_{a \neq a^*} \frac{u'_{a}(x_{a}(y))x'_{a}(y)}{(d_{\epsilon}^{+}(\mu_{a}, u_{a}(x_{a}(y))))^{2}} \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu_{a}, u_{a}(x_{a}(y))) \\ = - \sum_{a \neq a^*} \frac{u'_{a}(x_{a}(y))}{(d_{\epsilon}^{+}(\mu_{a}, u_{a}(x_{a}(y))))^{3}} \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu_{a}, u_{a}(x_{a}(y))), \\ F'(y) = \sum_{a \neq a^*} \frac{u'_{a}(x_{a}(y))x'_{a}(y)}{(d_{\epsilon}^{+}(\mu_{a}, u_{a}(x_{a}(y))))^{2}} \\ \left( d_{\epsilon}^{+}(\mu_{a}, u_{a}(x_{a}(y))) \frac{\partial d_{\epsilon}^{-}}{\partial u}(\mu_{a^*}, u_{a}(x_{a}(y))) - d_{\epsilon}^{-}(\mu_{a^*}, u_{a}(x_{a}(y))) \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu_{a}, u_{a}(x_{a}(y))) \right) \\ = - \sum_{a \neq a^*} \frac{u'_{a}(x_{a}(y))x'_{a}(y)}{(d_{\epsilon}^{+}(\mu_{a}, u_{a}(x_{a}(y))))^{2}} \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu_{a}, u_{a}(x_{a}(y))) \\ (x_{a}(y)d_{\epsilon}^{+}(\mu_{a}, u_{a}(x_{a}(y))) + d_{\epsilon}^{-}(\mu_{a^*}, u_{a}(x_{a}(y)))) \\ = -y \sum_{a \neq a^*} \frac{u'_{a}(x_{a}(y))x'_{a}(y)}{(d_{\epsilon}^{+}(\mu_{a}, u_{a}(x_{a}(y))))^{2}} \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu_{a}, u_{a}(x_{a}(y))) = yH'(y), $$

Therefore, showing that $H$ is increasing is a sufficient condition to show that $F$ is increasing. Using the above results, we have, for all $a \neq a^*$ and all $y \in [0, \min_{a \neq a^*} d_{\epsilon}^{-}(\mu_{a^*}, \mu_a))$, we have

$$ \frac{1}{(d_{\epsilon}^{+}(\mu_{a}, u_{a}(x_{a}(y))))^{3}} \frac{\partial d_{\epsilon}^{+}}{\partial u}(\mu_{a}, u_{a}(x_{a}(y))) > 0 \quad \text{and} \quad u'_{a}(x_{a}(y)) < 0. $$

Therefore, $H$ is increasing as a summation of increasing function, hence $F$ is increasing.

Let $y^*$ such that $F(y^*) = 1$. Reusing the above manipulation, we obtain

$$ G''(y) = - \frac{F'(y)(1 + \sum_{a \neq a^*} x_a(y)) + 2(1 - F(y)) \sum_{a \neq a^*} x'_a(y)}{(1 + \sum_{a \neq a^*} x_a(y))^3} \\ = - \frac{yH'(y)(1 + yH(y) - F(y)) + 2(1 - F(y))H(y)}{(1 + yH(y) - F(y))^3}, $$

$$ G''(y^*) = - \frac{H'(y^*)}{y^* H(y^*)^2} < 0, $$

Therefore, $y^*$ is the unique maximum of $G$. We conclude this part of the proof by using the intermediate results in the proof of Lemma 43.

By strict convexity of $x_a$ and using its properties proven above, we obtain

$$ x_a(y) \geq x_a(0) + yx'_a(0) = \frac{y}{d_{\epsilon}^{+}(\mu_a, \mu_{a^*})}. $$

Summing those inequalities, we obtain

$$ \forall y \in [0, \min_{a \neq a^*} d_{\epsilon}^{-}(\mu_{a^*}, \mu_a)), \quad G(y) = \frac{y}{1 + \sum_{a \neq a^*} x_a(y)} \leq \frac{1}{\frac{1}{y} + \sum_{a \neq a^*} \frac{1}{d_{\epsilon}^{+}(\mu_a, \mu_{a^*})}}. $$

Using that $y \mapsto 1/(1/y + \alpha)$ is increasing for $\alpha > 0$, we obtain that

$$ T_{\epsilon}^{*}(\nu)^{-1} = \max_{y \in [0, \min_{a \neq a^*} d_{\epsilon}^{-}(\mu_{a^*}, \mu_a))} G(y) \leq \frac{1}{\frac{1}{\min_{a \neq a^*} d_{\epsilon}^{-}(\mu_{a^*}, \mu_a))} + \sum_{a \neq a^*} \frac{1}{d_{\epsilon}^{+}(\mu_a, \mu_{a^*})}}. $$

This concludes the proof of the second to last result. The last result is obtained by combining Lemmas 26 and 25 and the derivation in the proof of Lemma 45. $\square$
Lemma 48 is a technical result used in the proof of sufficient exploration of our sampling rule.

**Lemma 48.** Let $d_{\epsilon}^{\pm}$ as in Eq. (3). Let $\mu \in (0, 1)^K$. There exists $\alpha > 0$ such that

$$ C_{\mu} := \min_{(a,b): \mu_a > \mu_b} \inf_{\lambda_a, \lambda_b: \max_{c \in \{a,b\}} |\mu_c - \lambda_c| \le \alpha} \inf_{u \in [0,1]} \{d_{\epsilon}^{-}(\lambda_a, u) + d_{\epsilon}^{+}(\lambda_b, u)\} > 0. \quad (38) $$

*Proof.* Using Lemma 35 for $w_1 = w_2 = 1$, the function $\mu \mapsto \inf_{u \in [0,1]} \{d_{\epsilon}^{-}(\mu_a, u) + d_{\epsilon}^{+}(\mu_b, u)\}$ is continuous on $\mathcal{F}^K$. Since it has strictly positive values when $\mu_a > \mu_b$ (Lemma 35), there exists $\alpha$ such that

$$ \inf_{\lambda_a, \lambda_b: \max_{c \in \{a,b\}} |\mu_c - \lambda_c| \le \alpha} \inf_{u \in [0,1]} \{d_{\epsilon}^{-}(\lambda_a, u) + d_{\epsilon}^{+}(\lambda_b, u)\} > 0. $$

Further lower bounding by a finite number of strictly positive constants yields the result. $\square$

Lemma 48 is a technical result used in the proof of convergence towards the optimal allocation of our sampling rule.

**Lemma 49.** Let $d_{\epsilon}^{\pm}$ as in Eq. (3). Let $(\phi_1, \phi_2) \in (0, 1)^2$. Let $\mathcal{I}_a := \{\mu \in (0, 1)^K | a \in a^*(\mu)\}$ for all $a \in [K]$. For all $a^* \in [K]$, all $\mu \in \mathcal{I}_{a^*}$, all $(a, b) \in ([K] \setminus \{a^*\})^2$ such that $a \neq b$, and all $\beta \in [0, 1]$, define

$$ G_{a,b}(\mu, \beta) := \inf_{u \in [0,1]} \{\beta d_{\epsilon}^{-}(\mu_{a^*}, u) + \phi_1 d_{\epsilon}^{+}(\mu_a, u)\} - \inf_{u \in (0,1)} \{\beta d_{\epsilon}^{-}(\mu_{a^*}, u) + \phi_2 d_{\epsilon}^{+}(\mu_b, u)\}. $$

The function $(\mu, \beta) \mapsto G_{a,b}(\mu, \beta)$ is continuous on $(0, 1)^K \times [0, 1]$. For all $\xi > 0$, the function $(\mu, \beta) \mapsto \inf_{\tilde{\beta}: |\beta - \tilde{\beta}| \le \xi} G_{a,b}(\mu, \beta)$ is continuous on $(0, 1)^K$.

*Proof.* Since $\cup_{a \in [K]} \mathcal{I}_a^K = (0, 1)^K$, it is enough to show the property for all $a \in [K]$. Let $a^* \in [K]$, $\mu \in \mathcal{I}_{a^*}$, $(a, b) \in ([K] \setminus \{a^*\})^2$ such that $a \neq b$. As done in Lemma 42 by using Lemma 35, we obtain that the function $(\mu, \beta) \mapsto G_{a,b}(\mu, \beta)$ is continuous on $\mathcal{I}_{a^*} \times [0, 1]$ for all $a^* \in [K]$, hence on $(0, 1)^K \times [0, 1]$. Let $\Phi: \mu \mapsto \{\tilde{\beta}: |\beta - \tilde{\beta}| \le \xi\}$, it is a continuous (constant), compact valued and non-empty correspondence. Using the above continuity, Berge's theorem yields that $\mu \mapsto \inf_{\tilde{\beta}: |\beta - \tilde{\beta}| \le \xi} G_{a,b}(\mu, \tilde{\beta})$ is continuous on $(0, 1)^K$. $\square$

## H Asymptotic Upper Bound on the Expected Sample complexity

Let $\nu$ be a Bernoulli instance with means $\mu \in (0, 1)^2$ and unique best arm $a^* \in [K]$, i.e., $\arg\max_{a \in [K]} \mu_a = \{a^*\}$. Let $\beta \in (0, 1)$. Let $w_{\epsilon, \beta}^*(\nu) = \{w_{\epsilon, \beta}^*\}$ be the unique $\beta$-optimal allocation defined in Eq. (35), which satisfies $\min_{a \in [K]} w_{\epsilon, \beta, a} > 0$ by Lemma 43. At equilibrium, we have equality of the transportation costs by Lemma 43, namely

$$ \forall a \neq a^*, \quad W_{\epsilon,a^*,a}(\mu, w_{\epsilon,\beta}^*) = T_{\epsilon,\beta}^*(\nu)^{-1}, \quad (39) $$

where $W_{\epsilon,a,b}$ is defined in Eq. (4) and $T_{\epsilon,\beta}^*$ is defined in Eq. (35).

Let $\gamma > 0$. Let $\omega \in \Delta_K$ be any allocation over arms such that $\min_a \omega_a > 0$. We denote by $T_{\gamma}(\omega)$ the convergence time towards $\omega$, which is a random variable quantifying the number of samples required for the global empirical allocations $N_n/(n-1)$ to be $\gamma$-close to $\omega$ for any subsequent time, namely

$$ T_{\gamma}(\omega) := \inf \left\{ T \ge 1 \mid \forall n \ge T, \left\| \frac{N_n}{n-1} - \omega \right\|_{\infty} \le \gamma \right\}. \quad (40) $$

The proof of Theorem 7 follows the same analysis as the unified analysis of Top Two algorithms, see, e.g., Jourdan et al. [2022]. Appendix H is organised as follows. After recalling some technical results (Appendix H.1), we prove sufficient exploration of our sampling rule (Appendix H.2). Second, we prove that convergence time towards the $\beta$-optimal allocation of our sampling rule (Appendix H.3) has finite expectation. Finally, we conclude the proof of Theorems 7 (Appendix H.4).
## H.1 Technical Results from the Literature

Lemma 50 relates the global counts $(N_{n,a})_{a \in [K]}$ and the local counts $(\tilde{N}_{n,a})_{a \in [K]}$.

**Lemma 50.** Let $\eta > 0$ be the geometric parameter used for the geometric grid update of our private empirical mean estimator. For all $(a, k) \in [K] \times \mathbb{N}$ s.t. $\mathbb{E}_{\nu\pi}[T_k(a)] < +\infty$, $N_{T_k(a),a} = \tilde{N}_{k,a} = [(1+\eta)^{k-1}]$. For all $a \in [K]$ and all $n \in \mathbb{N}$, $N_{n,a} \ge \tilde{N}_{n,a} \ge N_{n,a}/(1+\eta)$.

*Proof.* Let $a \in [K]$. After initialisation, we have $k = 1$, $T_1(a) = K + 1$ and $N_{T_1(a),a} = 1$. Using the definition of the phase switch, it is direct to see that $N_{T_2(a),a} = \tilde{N}_{2,a} = [1+\eta]$ when $\mathbb{E}_{\nu\pi}[T_2(a)] < +\infty$. Similarly, we obtain $N_{T_k(a),a} = \tilde{N}_{k,a} = [(1+\eta)^{k-1}]$ when $\mathbb{E}_{\nu\pi}[T_k(a)] < +\infty$. The last result is a direct consequence of the definition of the per-arm geometric update grid. □

Lemma 51 controls the deviation $N_{n,a}^a - \beta L_{n,a}$ enforced by the tracking procedure.

**Lemma 51** (Lemma 2.2 in Jourdan and Degenne [2024]). For all $n > K$ and all $a \in [K]$, $-1/2 \le N_{n,a}^a - \beta L_{n,a} \le 1$.

Lemma 52 gathers properties on the $\overline{W}_{-1}$ function used in the stopping threshold.

**Lemma 52** (Jourdan et al. [2023]). 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. The function $\overline{W}_{-1}$ is increasing on $(1, +\infty)$ and strictly concave on $(1, +\infty)$. In particular, $\overline{W}'_{-1}(x) = (1 - \frac{1}{\overline{W}_{-1}(x)})^{-1}$ for all $x > 1$. Then, for all $y \ge 1$ and $x \ge 1$,

$$ \overline{W}_{-1}(y) \le x \iff y \le x - \log(x). $$

Moreover, for all $x > 1$,

$$ x + \log(x) \le \overline{W}_{-1}(x) \le x + \log(x) + \min \left\{ \frac{1}{2}, \frac{1}{\sqrt{x}} \right\}. $$

Lemma 53 gives an upper bound on a time define implicit as a function of $\overline{W}_{-1}$, namely it is an inversion result.

**Lemma 53** (Lemma 32 in Azize et al. [2024]). Let $\overline{W}_{-1}$ defined in Lemma 52. Let $A > 0$, $B > 0$ such that $B/A + \log A > 1$ and $C(A, B) = \sup \{x \mid x < A \log x + B\}$. Then, $C(A, B) < h_1(A, B)$ with $h_1(z, y) = z \overline{W}_{-1}(y/z + \log z)$.

Lemma 54 shows that upon correction the supremum of sub-exponential random variables is also a sub-exponential random variable.

**Lemma 54** (Lemma 72 in Jourdan et al. [2022]). Suppose that $(X_n)_{n \ge 1}$ are sub-exponential random variables with constants $(C_n)$, such that $c := \inf_n C_n > 0$. Then $\sup_n(X_n/\log(e+n))$ is sub-exponential.

Lemma 55 gives a coarse convergence rate of the private empirical estimators of the means towards their true means.

**Lemma 55.** There exist sub-exponential random variable $W_\mu$ such that almost surely, for all $a \in [K]$ and all $n$ such that $\tilde{N}_{n,a} \ge 1$,

$$ \tilde{N}_{n,a} | \tilde{\mu}_{n,a} - \mu_a| \le W_\mu \log(e + \tilde{N}_{n,a}). $$

In particular, any random variable which is polynomial in $W_\mu$ has a finite expectation.

*Proof.* Let us define

$$ W_\mu = \max_{a \in [K]} \sup_{n \in \mathbb{N}} \frac{\tilde{N}_{n,a} |\tilde{\mu}_{n,a} - \mu_a|}{\log(e + \tilde{N}_{n,a})}. $$

Let $a \in [K]$. Let us define the geometric grid $N_k = [(1+\eta)^{k-1}]$ for all $k \in \mathbb{N}$, on which we effectively need to control the concentration. The maximum of a finite number of sub-exponential
random variables is sub-exponential. Therefore, using the geometric update grid, it suffices to show that

$$ \sup_{k \in \mathbb{N}} \frac{N_k |(Z_{N_k} + S_k)/N_k - \mu_a|}{\log(e + N_k)} $$

is sub-exponential, where $Z_{N_k}$ is the cumulative sum of $N_k$ i.i.d. observations from Ber($\mu_a$) and $S_k$ is the cumulative sum of $k$ i.i.d. observations from Lap($1/e$).

Using that $Z_{N_k} - N_k\mu_a$ is sub-Gaussian and $S_k$ is sub-exponential, for a fixed $k$, $|Z_{N_k} - N_k\mu_a + S_k|$ is sub-exponential. Applying Lemma 54, we obtain that

$$ \sup_{k \in \mathbb{N}} \frac{N_k |(Z_{N_k} + S_k)/N_k - \mu_a|}{\log(e + N_k)} $$

is sub-exponential. We finally obtain that the maximum over the finitely many arms has the same property. □

## H.2 Sufficient Exploration

The first step of in the generic analysis of Top Two algorithms [Jourdan et al., 2022] consists in showing sufficient exploration. The main idea is that, if there are still undersampled arms, either the leader or the challenger will be among them. Therefore, after a long enough time, no arm can still be undersampled. We emphasise that there are multiple ways to select the leader/challenger pair in order to ensure sufficient exploration. Therefore, other choices of leader/challenger pair would yield similar results.

Given an arbitrary phase $p \in \mathbb{N}$, we define the sampled enough set, i.e., the arms having reached phase $p$, and the arm with highest mean in this set (when not empty) as

$$ S_n^p = \{a \in [K] \mid N_{n,a} \ge (1+\eta)^{p-1}\} \quad \text{and} \quad a_n^* = \arg \max_{a \in S_n^p} \mu_a. \quad (41) $$

Since $\min_{a \neq b} |\mu_a - \mu_b| > 0$, $a_n^*$ is unique. Let $p \in \mathbb{N}$ such that $(p-1)/4 \in \mathbb{N}$. We define the highly and the mildly under-sampled sets as

$$ U_n^p := \{a \in [K] \mid N_{n,a} < (1+\eta)^{(p-1)/2}\} \quad \text{and} \quad V_n^p := \{a \in [K] \mid N_{n,a} < (1+\eta)^{3(p-1)/4}\}. \quad (42) $$

Those arms have not reached phase $(p-1)/2$ and phase $3(p-1)/4$, respectively.

Lemma 56 shows that, when the leader is sampled enough, it is the arm with highest true mean among the sampled enough arms.

**Lemma 56.** Let $S_n^p$ and $a_n^*$ as in (41). There exists $p_0$ with $\mathbb{E}_{\nu\pi}[\exp(\alpha p_0)] < +\infty$ for all $\alpha > 0$ such that if $p \ge p_0$, for all $n$ such that $S_n^p \neq \emptyset$, we have

* For all $a \in S_n^p$, we have $\tilde{\mu}_{n,a} \in (0, 1)$ and $a_n^* = \arg \max_{a \in S_n^p} \tilde{\mu}_{n,a}$.

* If $B_n \in S_n^p$, then $B_n = a_n^*$.

*Proof.* Let $p_0$ to be specified later. Let $p \ge p_0$. Let $n \in \mathbb{N}$ such that $S_n^p \neq \emptyset$, where $S_n^p$ and $a_n^*$ as in Equation (41). Since $N_{n,a} \ge (1+\eta)^{p-1}$ for all $a \in S_n^p$, we have $\tilde{N}_{n,a} \ge (1+\eta)^{p-1}$. Using Lemma 55 and $x \to \log(e+x)/x$ is decreasing, we obtain that

$$ \tilde{\mu}_{n,a_n^*} \ge \mu_{a_n^*} - W_\mu \frac{\log(e + (1 + \eta)^{p-1})}{(1 + \eta)^{p-1}}, \\ \forall a \in S_n^p \setminus \{a_n^*\}, \quad \tilde{\mu}_{n,a} \le \mu_a + W_\mu \frac{\log(e + (1 + \eta)^{p-1})}{(1 + \eta)^{p-1}}. $$

Let $\bar{\Delta}_{\min} = \min_{a \neq b} |\mu_a - \mu_b|$ and $\Delta_0 = \min_{a \in [K]} \min\{\mu_a, 1 - \mu_a\} > 0$. By assumption on the considered instances, we know that $\bar{\Delta}_{\min} > 0$. Let $p_1 = \lceil \log_{1+\eta}(X_1 - e) \rceil + 1$ with

$$ X_1 = \sup \{x > 1 \mid x \le 4(\min\{\bar{\Delta}_{\min}, \Delta_0\})^{-1} W_{\mu} \log x + e\} \\ \le h_1(4(\min\{\bar{\Delta}_{\min}, \Delta_0\})^{-1} W_{\mu}, e), $$
where we used Lemma 53, and $h_1$ defined therein. Then, for all $p \in \mathbb{N}$ such that $p \ge p_1 + 1$ and all $n \in \mathbb{N}$ such that $S_n^p \ne \emptyset$, we have

$$ \forall a \in S_n^p, \quad \mu_a - \min\{\bar{\Delta}_{\min}, \Delta_0\}/4 \le \tilde{\mu}_{n,a} \le \mu_a + \min\{\bar{\Delta}_{\min}, \Delta_0\}/4. $$

Therefore, we have $\tilde{\mu}_{n,a} \in (0, 1)$ for all $a \in S_n^p$. Since $\tilde{\mu}_{n,a_n^*} \ge \mu_{a_n^*} - \min\{\bar{\Delta}_{\min}, \Delta_0\}/4$ and $\tilde{\mu}_{n,a} \le \mu_a + \min\{\bar{\Delta}_{\min}, \Delta_0\}/4$ for all $a \in S_n^p \setminus \{a_n^*\}$, we obtain $a_n^* = \arg\max_{a \in S_n^p} \tilde{\mu}_{n,a}$ since $\arg\max_{a \in S_n^p} \tilde{\mu}_{n,a}$ is unique. The leader is defined as $B_n = \arg\max_{a \in [K]}[\tilde{\mu}_{n,a}]_0^1$. If $B_n \in S_n^p$, we obtain

$$ B_n = \arg\max_{a \in S_n^p} [\tilde{\mu}_{n,a}]_0^1 = \arg\max_{a \in S_n^p} \tilde{\mu}_{n,a} = a_n^*. $$

For all $\alpha \in \mathbb{R}_+$, we have $\exp(\alpha p_1) \le e^{3\alpha}(X_1 - e)^{\alpha/\log 2}$, hence $\mathbb{E}_{\nu_\pi}[\exp(\alpha p_1)] < +\infty$ by using Lemma 55 and $h_1(x, e) \sim_{x \to +\infty} x \log x$ to obtain that $\exp(\alpha p_1)$ is at most polynomial in $W_\mu$. Taking $p_0 = p_1$ concludes the proof. $\square$

Lemma 57 shows that the transportation costs between the sampled enough arms with largest true means and the other sampled enough arms are increasing fast enough.

**Lemma 57.** Let $S_n^p$ as in Eq. (41). There exists $p_1$ with $\mathbb{E}_{\nu_\pi}[\exp(\alpha p_1)] < +\infty$ for all $\alpha > 0$ such that if $p \ge p_1$, for all $n$ such that $S_n^p \ne \emptyset$, for all $(a, b) \in (S_n^p)^2$ such that $\mu_a > \mu_b$, we have

$$ W_{\epsilon,a,b}(\tilde{\mu}_n, N_n) \ge (1 + \eta)^{p-1} C_\mu, $$

where $C_\mu > 0$ is a problem dependent constant.

*Proof.* Let $p_0$ as in Lemma 56. Let $p \ge p_0$. Let $n \in \mathbb{N}$ such that $S_n^p \ne \emptyset$, where $S_n^p$ as in Eq. (41). Since $N_{n,a} \ge (1 + \eta)^{p-1}$ for all $a \in S_n^p$, we have $\tilde{N}_{n,a} \ge (1 + \eta)^{p-1}$ by using Lemma 50. Let $(a, b) \in (S_n^p)^2$ such that $\mu_a > \mu_b$. Using Lemma 48, there exists $\alpha_\mu > 0$ such that

$$ C_\mu = \min_{(a,b): \mu_a > \mu_b} \inf_{\max_{c \in \{a,b\}} |\mu_c - \lambda_c| \le \alpha_\mu} \inf_{u \in [0,1]} \{d_\epsilon^-(\lambda_a, u) + d_\epsilon^+(\lambda_b, u)\} > 0. $$

Let $\eta > 0$ s.t. $\eta < \frac{1}{4}\min\{\bar{\Delta}_{\min}, \Delta_0, \alpha_\mu\}$ where $\bar{\Delta}_{\min} = \min_{a \ne b} |\mu_a - \mu_b|$ and $\Delta_0 = \min_{a \in [K]} \min\{\mu_a, 1 - \mu_a\}$. Similarly as in the proof of Lemma 56, we can construct $p_2$ with $\mathbb{E}_{\nu_\pi}[\exp(\alpha p_2)] < +\infty$ for all $\alpha > 0$ such that if $p \ge p_2$, for all $n$ such that $S_n^p \ne \emptyset$, we have $|\tilde{\mu}_{n,a} - \mu_a| \le \eta$ for all $a \in S_n^p$. Therefore, we have $\tilde{\mu}_{n,a} = [\tilde{\mu}_{n,a}]_0^1$ and $[\tilde{\mu}_{n,b}]_0^1 = \tilde{\mu}_{n,b}$. Moreover, we have $\tilde{\mu}_{n,a} \ge \mu_a - \eta > \mu_b + \eta \ge \tilde{\mu}_{n,b}$. Then, we obtain

$$ \begin{aligned} W_{\epsilon,a,b}(\tilde{\mu}_n, N_n) &= \inf_{u \in [0,1]} \{N_{n,a} d_\epsilon^-(\tilde{\mu}_{n,a}, u) + N_{n,b} d_\epsilon^+(\tilde{\mu}_{n,b}, u)\} \\ &\ge (1+\eta)^{p-1} \inf_{u \in [0,1]} \{d_\epsilon^-(\tilde{\mu}_{n,a}, u) + d_\epsilon^+(\tilde{\mu}_{n,b}, u)\} \\ &\ge (1+\eta)^{p-1} \inf_{\max_{c \in \{a,b\}} |\mu_c - \lambda_c| \le \alpha_\mu} \inf_{u \in [0,1]} \{d_\epsilon^-(\lambda_a, u) + d_\epsilon^+(\lambda_b, u)\} \ge (1+\eta)^{p-1} C_\mu. \end{aligned} $$

This concludes the proof. $\square$

Lemma 58 shows that the transportation costs between sampled enough arms and undersampled arms are not increasing too fast.

**Lemma 58.** Let $S_n^p$ be as in Eq. (41). There exists $p_2$ with $\mathbb{E}_{\nu_\pi}[\exp(\alpha p_2)] < +\infty$ for all $\alpha > 0$ such that if $p \ge p_2$, for all $n$ such that $S_n^p \ne \emptyset$, For all $p \ge p_2$ and all $n$ such that $S_n^p \ne \emptyset$, for all $a \in S_n^p$ and $b \notin S_n^p$,

$$ W_{\epsilon,a,b}(\tilde{\mu}_n, N_n) \le (1 + \eta)^{p-1} D_\mu, $$

where $D_\mu \in (0, +\infty)$ is a problem dependent constant.

*Proof.* Let $n \in \mathbb{N}$ such that $S_n^p \ne \emptyset$, where $S_n^p$ as in Eq. (41). Since $N_{n,a} \ge (1 + \eta)^{p-1}$ for all $a \in S_n^p$, we have $\tilde{N}_{n,a} \ge (1 + \eta)^{p-1}$ by using Lemma 50. Likewise, $N_{n,b} < (1 + \eta)^{p-1}$ for all
$b \notin S_n^p$, we have $\tilde{N}_{n,b} < (1 + \eta)^{p-1}$. Let $a \in S_n^p$ and $b \notin S_n^p$. Since the result is direct when $[\tilde{\mu}_{n,a}]_0^1 \le [\tilde{\mu}_{n,b}]_0^1$, we assume $[\tilde{\mu}_{n,a}]_0^1 > [\tilde{\mu}_{n,b}]_0^1$ in the following.

Let $\eta > 0$ s.t. $\eta < \frac{1}{4} \min\{\bar{\Delta}_{\min}, \Delta_0\}$ where $\bar{\Delta}_{\min} = \min_{a \neq b} |\mu_a - \mu_b|$ and $\Delta_0 = \min_{a \in [K]} \min\{\mu_a, 1 - \mu_a\} > 0$. Similarly as in the proof of Lemma 56, we can construct $p_2$ with $\mathbb{E}_{\nu_{\pi}}[\exp(\alpha p_2)] < +\infty$ for all $\alpha > 0$ such that if $p \ge p_2$, for all $n$ such that $S_n^p \neq \emptyset$, we have $|\tilde{\mu}_{n,a} - \mu_a| \le \eta$ for all $a \in S_n^p$. Let $g_{\epsilon}^{+}(x) = \frac{x}{x(1-e^{\epsilon})+e^{\epsilon}}$ as in Lemma 24. Using Lemma 24, for all $a \in S_n^p$, we have

$$1 > \mu_a + \min\{\bar{\Delta}_{\min}, \Delta_0\}/4 \ge \tilde{\mu}_{n,a} > g_{\epsilon}^{+}(\tilde{\mu}_{n,a}) \ge g_{\epsilon}^{+}(\mu_a - \min\{\bar{\Delta}_{\min}, \Delta_0\}/4) > 0.$$

Taking $u = \tilde{\mu}_{n,a} \in [0, 1]$ and using that $d_{\epsilon}^{-}(\tilde{\mu}_{n,a}, \tilde{\mu}_{n,a}) = 0$, we obtain

$$W_{\epsilon,a,b}(\tilde{\mu}_n, N_n) = \inf_{u \in [0,1]} \left\{ \begin{aligned} & N_{n,a}d_{\epsilon}^{-}(\tilde{\mu}_{n,a}, u) + N_{n,b}d_{\epsilon}^{+}(\tilde{\mu}_{n,b}, u) \\ & \le N_{n,b}d_{\epsilon}^{+}(\tilde{\mu}_{n,b}, \tilde{\mu}_{n,a}) \le (1+\eta)^{p-1}d_{\epsilon}^{+}(\tilde{\mu}_{n,b}, \tilde{\mu}_{n,a}) \end{aligned} \right\},$$

where the last term is positive since $\tilde{\mu}_{n,a} > [\tilde{\mu}_{n,b}]_0^1$ and $\tilde{\mu}_{n,a} \in (0, 1)$ by Lemma 25.

When $\tilde{\mu}_{n,b} \le 0$, Lemma 25 yields that

$$d_{\epsilon}^{+}(\tilde{\mu}_{n,b}, \tilde{\mu}_{n,a}) = -\log(1 - \tilde{\mu}_{n,a}(1 - e^{-\epsilon})) \le \epsilon,$$

where we used that $x \to -\log(1 - x(1 - e^{-\epsilon}))$ is increasing on $(0, 1)$. When $\tilde{\mu}_{n,b} \in (0, g_{\epsilon}^{+}(\tilde{\mu}_{n,a}))$, Lemma 25 yields that

$$d_{\epsilon}^{+}(\tilde{\mu}_{n,b}, \tilde{\mu}_{n,a}) = -\log(1 - \tilde{\mu}_{n,a}(1 - e^{-\epsilon})) - \epsilon\tilde{\mu}_{n,b} \le \epsilon.$$

When $\tilde{\mu}_{n,b} \in [g_{\epsilon}^{+}(\tilde{\mu}_{n,a}), \tilde{\mu}_{n,a})$, Lemma 25 yields that

$$d_{\epsilon}^{+}(\tilde{\mu}_{n,b}, \tilde{\mu}_{n,a}) = \mathrm{kl}(\tilde{\mu}_{n,b}, \tilde{\mu}_{n,a}) \le -\log \min\{\tilde{\mu}_{n,a}, 1 - \tilde{\mu}_{n,a}\} \\ \le -\log \min\{\mu_a - \min\{\bar{\Delta}_{\min}, \Delta_0\}/4, 1 - \mu_a - \min\{\bar{\Delta}_{\min}, \Delta_0\}/4\},$$

where we used the classical result that $\mathrm{kl}(q, p) \le -\log \min\{p, 1 - p\}$. Let us define

$$D_{\mu} = \epsilon + \max_{a \in [K]} \left\{ -\log \min\{\mu_a - \min\{\bar{\Delta}_{\min}, \Delta_0\}/4, 1 - \mu_a - \min\{\bar{\Delta}_{\min}, \Delta_0\}/4\} \right\}.$$

Then, we have shown that $d_{\epsilon}^{+}(\tilde{\mu}_{n,b}, \tilde{\mu}_{n,a}) \le D_{\mu}$ where $D_{\mu} \in (0, +\infty)$. This yields the result. $\square$

Lemma 59 shows that the challenger is mildly undersampled if the leader is not mildly undersampled.

**Lemma 59.** Let $V_n^p$ be as in Equation (42). There exists $p_3$ with $\mathbb{E}_{\nu_{\pi}}[\exp(\alpha p_3)] < +\infty$ for all $\alpha > 0$ such that if $p \ge p_3$, for all $n$ such that $U_n^p \neq \emptyset$, $B_n \notin V_n^p$ implies $C_n \in V_n^p$.

*Proof.* Let $p_3$ to be specified later. Let $p \ge p_3$. Let $n \in \mathbb{N}$ such that $U_n^p \neq \emptyset$ and $V_n^p \neq [K]$, where $U_n^p \subseteq V_n^p$ are defined in Eq. (42). Since the statement holds when $B_n \in V_n^p$, we suppose that $B_n \notin V_n^p$ in the following.

Let $p_0$ as in Lemma 56, $p_1$ and $C_{\mu}$ as in Lemma 57, and $p_2$ and $D_{\mu}$ as in Lemma 58. Let $p_4 = \max\{2p_2 - 1, \frac{4}{3} \max\{p_0, p_1\} - 1/3\}$, which satisfied that $\mathbb{E}_{\nu_{\pi}}[\exp(\alpha p_4)] < +\infty$ for all $\alpha > 0$ by using Lemmas 56, 57 and 58. Then, for all $p \ge p_4 = \max\{2p_2 - 1, \frac{4}{3} \max\{p_0, p_1\} - 1/3\}$ and all $n$ such that $B_n \notin V_n^p$, we have $\tilde{\mu}_{n,a} \in (0, 1)$ for all $a \notin V_n^p$, $B_n = b_n^* := \arg \max_{a \notin V_n^p} \mu_a$, $B_n \notin U_n^p$ and

$$\forall b \notin \{b_n^*\} \cup V_n^p, \quad W_{\epsilon,b_n^*,b}(\tilde{\mu}_n, N_n) + \log N_{n,b} \ge (1+\eta)^{3(p-1)/4} C_{\mu} + \frac{3(p-1)}{4} \log(1+\eta),$$

$$\forall b \in U_n^p, \quad W_{\epsilon,b_n^*,b}(\tilde{\mu}_n, N_n) + \log N_{n,b} \le (1+\eta)^{(p-1)/2} D_{\mu} + \frac{p-1}{2} \log(1+\eta),$$

where we used Lemmas 56, 57 and 58. Direct manipulations yield that

$$(1+\eta)^{3(p-1)/4} C_{\mu} + \frac{3(p-1)}{4} \log(1+\eta) \ge (1+\eta)^{(p-1)/2} D_{\mu} + \frac{p-1}{2} \log(1+\eta)$$
$$\iff p \ge p_5 = 4[\log_{1+\eta}(D_\mu/C_\mu)] + 1,$$

where $\mathbb{E}_{\nu\pi}[\exp(\alpha p_5)] < +\infty$ for all $\alpha > 0$ since it is a deterministic constant. Let $p_3 = \max\{p_4, p_5\}$ which satisfies $\mathbb{E}_{\nu\pi}[\exp(\alpha p_3)] < +\infty$ for all $\alpha > 0$. Then, we have shown that for all $p \ge p_3$, for all $n$ such that $B_n \notin V_n^p$, we have $B_n = b_n^*$ and

$$\min_{b \notin \{b_n^*\} \cup V_n^p} \{W_{\epsilon, b_n^*, b}(\tilde{\mu}_n, N_n) + \log N_{n,b}\} > \max_{b \in U_n^p} \{W_{\epsilon, b_n^*, b}(\tilde{\mu}_n, N_n) + \log N_{n,b}\}.$$

By definition of the TC challenger, i.e., $C_n \in \arg\min_{b \neq B_n} \{W_{\epsilon, B_n, b}(\tilde{\mu}_n, N_n) + \log N_{n,b}\}$, we obtain that $C_n \in V_n^p$. Otherwise, there would be a contradiction since we assumed $U_n^p \neq \emptyset$. This concludes the proof. $\square$

Lemma 60 shows that all the arms are sufficient explored for large enough $n$.

**Lemma 60.** There exists $N_0$ with $\mathbb{E}_{\nu\pi}[N_0] < +\infty$ such that, for all $n \ge N_0$ and all $a \in [K]$, $N_{n,a} \ge \sqrt{n/K}$.

*Proof.* Let $p_0$ and $p_3$ as in Lemmas 56 and 59. Combining Lemmas 56 and 59 yields that, for all $p \ge p_4 = \max\{p_3, 4p_0/3 - 1/3\}$ and all $n$ such that $U_n^p \neq \emptyset$, we have $B_n \in V_n^p$ or $C_n \in V_n^p$. We have $\mathbb{E}_{\nu\pi}[(1+\eta)^{p_2}] < +\infty$. We have $(1+\eta)^{p_1-1} \ge K(1+\eta)^{3(p_1-1)/4}$ for all $p \ge p_5 = 4[\log_{1+\eta}K] + 1$. Let $p \ge \max\{p_5, p_4\}$. For notational simplicity, we conduct the proof as if that $k(1+\eta)^{p_1-1} \in \mathbb{N}$ for all $k \in [K]$. It is direct to adapt the proof by using the operator $[\cdot]$.

Suppose towards contradiction that $U_{K(1+\eta)^{p_1-1}}^p$ is not empty. Then, for any $1 \le t \le K(1+\eta)^{p_1-1}$, $U_t^p$ and $V_t^p$ are non empty as well. Using the pigeonhole principle, there exists some $a \in [K]$ such that $N_{(1+\eta)^{p_1-1}, a} \ge (1+\eta)^{3(p_1-1)/4}$. Thus, we have $|V_{(1+\eta)^{p_1-1}}^p| \le K - 1$. Our goal is to show that $|V_{2(1+\eta)^{p_1-1}}^p| \le K - 2$. A sufficient condition is that one arm in $V_{(1+\eta)^{p_1-1}}^p$ is pulled at least $(1+\eta)^{3(p_1-1)/4}$ times between $(1+\eta)^{p_1-1}$ and $2(1+\eta)^{p_1-1} - 1$.

**Case 1.** Suppose there exists $a \in V_{(1+\eta)^{p_1-1}}^p$ such that $L_{2(1+\eta)^{p_1-1}, a} - L_{(1+\eta)^{p_1-1}, a} \ge \beta^{-1}((1+\eta)^{3(p_1-1)/4} + 3/2)$. Using Lemma 51, we obtain

$$N_{2(1+\eta)^{p_1-1}, a}^a - N_{(1+\eta)^{p_1-1}, a}^a \ge \beta(L_{2(1+\eta)^{p_1-1}, a} - L_{(1+\eta)^{p_1-1}, a}) - 3/2 \ge (1+\eta)^{3(p_1-1)/4},$$

hence $a$ is sampled $(1+\eta)^{3(p_1-1)/4}$ times between $(1+\eta)^{p_1-1}$ and $2(1+\eta)^{p_1-1} - 1$.

**Case 2.** Suppose that for all $a \in V_{(1+\eta)^{p_1-1}}^p$, we have $L_{2(1+\eta)^{p_1-1}, a} - L_{(1+\eta)^{p_1-1}, a} < \beta^{-1}((1+\eta)^{3(p_1-1)/4} + 3/2)$. Then,

$$\sum_{a \notin V_{(1+\eta)^{p_1-1}}^p} (L_{2(1+\eta)^{p_1-1}, a} - L_{(1+\eta)^{p_1-1}, a}) \ge (1+\eta)^{p_1-1} - K\beta^{-1}((1+\eta)^{3(p_1-1)/4} + 3/2).$$

Using Lemma 51, we obtain

$$\left| \sum_{a \notin V_{(1+\eta)^{p_1-1}}^p} (N_{2(1+\eta)^{p_1-1}, a}^a - N_{(1+\eta)^{p_1-1}, a}^a) - \beta \sum_{a \notin V_{(1+\eta)^{p_1-1}}^p} (L_{2(1+\eta)^{p_1-1}, a} - L_{(1+\eta)^{p_1-1}, a}) \right| \le 3(K-1)/2.$$

Combining all the above, we obtain

$$\begin{align*}
& \sum_{a \notin V_{(1+\eta)^{p_1-1}}^p} (L_{2(1+\eta)^{p_1-1}, a} - L_{(1+\eta)^{p_1-1}, a}) - \sum_{a \notin V_{(1+\eta)^{p_1-1}}^p} (N_{2(1+\eta)^{p_1-1}, a}^a - N_{(1+\eta)^{p_1-1}, a}^a) \\
& \ge (1-\beta) \sum_{a \notin V_{(1+\eta)^{p_1-1}}^p} (L_{2(1+\eta)^{p_1-1}, a} - L_{(1+\eta)^{p_1-1}, a}) - 3(K-1)/2 \\
& \ge (1-\beta) \left( (1+\eta)^{p_1-1} - K\beta^{-1} \left( (1+\eta)^{3(p_1-1)/4} + 3/2 \right) \right) - 3(K-1)/2 \ge K(1+\eta)^{3(p_1-1)/4}
\end{align*}$$
where the last inequality is obtained for $p \ge p_6 + 1$ with

$$p_6 = \sup \left\{ p \in \mathbb{N} \mid (1 - \beta) \left( (1 + \eta)^{p-1} - K\beta^{-1} \left( (1 + \eta)^{3(p-1)/4} + 3/2 \right) \right) - \frac{3}{2}(K-1) < K(1 + \eta)^{3(p-1)/4} \right\}.$$

The left hand side summation is exactly the number of times where an arm $a \notin V_{(1+\eta)^{p-1}}^p$ was leader but wasn't sampled, hence we have shown that

$$\sum_{t=(1+\eta)^{p-1}}^{2(1+\eta)^{p-1}-1} 1 \left( B_t \notin V_{(1+\eta)^{p-1}}^p, a_t = C_t \right) \ge K(1+\eta)^{3(p-1)/4}.$$

For any $(1+\eta)^{p-1} \le t \le 2(1+\eta)^{p-1} - 1$, $U_t^p$ is non-empty, hence we have $B_t \notin V_{(1+\eta)^{p-1}}^p$ (hence $B_t \notin V_t^p$) implies $C_t \in V_t^p \subseteq V_{(1+\eta)^{p-1}}^p$. Therefore, we have shown that

$$\sum_{t=(1+\eta)^{p-1}}^{2(1+\eta)^{p-1}-1} 1 \left( a_t \in V_{(1+\eta)^{p-1}}^p \right) \ge \sum_{t=(1+\eta)^{p-1}}^{2(1+\eta)^{p-1}-1} 1 \left( B_t \notin V_{(1+\eta)^{p-1}}^p, a_t = C_t \right) \ge K(1+\eta)^{3(p-1)/4}$$

Therefore, there is at least one arm in $V_{(1+\eta)^{p-1}}^p$ that is sampled $(1+\eta)^{3(p-1)/4}$ times between $(1+\eta)^{p-1}$ and $2(1+\eta)^{p-1} - 1$.

In summary, we have shown $|V_{2(1+\eta)^{p-1}}^p| \le K - 2$ for all $p \ge p_7 = \max\{p_6, p_4, p_5\}$. By induction, for any $1 \le k \le K$, we have $|V_{k(1+\eta)^{p-1}}^p| \le K - k$, and finally $U_{K(1+\eta)^{p-1}}^p = \emptyset$ for all $p \ge p_7$. Defining $N_0 = K(1+\eta)^{p_7-1}$, we have $\mathbb{E}_{\nu_\pi}[N_0] < +\infty$ by using Lemmas 56 and 59 for $p_4 = \max\{p_3, 4p_0/3 - 1/3\}$ and $p_6$ and $p_5$ are deterministic. For all $n \ge N_0$, we let $(1+\eta)^{p-1} = \frac{n}{K}$. Then, by applying the above, we have $U_{K(1+\eta)^{p-1}}^p = U_n^{\log_{1+\eta}(n/K)+1}$ is empty, which shows that $N_{n,a} \ge \sqrt{n/K}$ for all $a \in [K]$. $\square$

### H.3 Convergence Towards β-Optimal Allocation

The second step of in the generic analysis of Top Two algorithms Jourdan et al. [2022] is to show the convergence of the empirical proportions towards the β-optimal allocation. First, we show that the leader coincides with the best arm. Hence, the tracking procedure will ensure that the empirical proportion of time we sample it is exactly $\beta$. Second, we show that a sub-optimal arm whose empirical proportion overshoots its β-optimal allocation will not be sampled next as challenger. Therefore, this “overshoots implies not sampled” mechanism will ensure the convergence towards the β-optimal allocation. We emphasise that there are multiple ways to select the leader/challenger pair in order to ensure convergence towards the β-optimal allocation. Therefore, other choices of leader/challenger pair would yield similar results. Note that our results heavily rely on having obtained sufficient exploration first.

Lemma 61 shows the leader and the candidate answer are equal to the best arm for large enough $n$.

**Lemma 61.** Let $N_0$ be as in Lemma 60. There exists $N_1 \ge N_0$ with $\mathbb{E}_{\nu_\pi}[N_1] < +\infty$ such that, for all $n \ge N_1$, we have $\tilde{\mu}_n \in (0, 1)^K$ and $\tilde{a}_n = B_n = a^*$.

*Proof.* Let $\Delta_{\min} = \min_{a \neq a^*} (\mu_{a^*} - \mu_a)$ and $\Delta_0 = \min_{a \in [K]} \min\{\mu_a, 1 - \mu_a\} > 0$. Using Lemma 55, we obtain, for all $n \ge N_0$,

$$\tilde{\mu}_{n,a^*} \ge \mu_{a^*} - W_\mu \frac{\log(e + \sqrt{n/K}/(1+\eta))}{\sqrt{n/K}/(1+\eta)} \\ \forall a \neq a^*, \quad \tilde{\mu}_{n,a} \le \mu_a + W_\mu \frac{\log(e + \sqrt{n/K}/(1+\eta))}{\sqrt{n/K}/(1+\eta)},$$
where we used that $x \to \log(e+x)/x$ is decreasing and $\tilde{N}_{n,a} \ge N_{n,a}/(1+\eta) \ge \sqrt{n/K}/(1+\eta)$. Let $N_1 = \max\{N_0, \lceil K(1+\eta)^2 X_1^2 \rceil\}$ where

$$X_1 = \sup \{x > 1 \mid x \le 4(\Delta_{\min}, \Delta_0)^{-1} W_{\mu} \log x + e\} \le h_1(4(\Delta_{\min}, \Delta_0)^{-1} W_{\mu}, e),$$

where we used Lemma 53, and $h_1$ defined therein. Using Lemmas 55 and 60, we obtain $\mathbb{E}_{\nu_{\pi}}[N_1] < +\infty$. Then, we have $0 < \mu_a - \Delta_0/4 \le \tilde{\mu}_{n,a} \le \mu_a + \Delta_0/4 < 1$ for all $a \in [K]$. Moreover, for all $n \ge N_1$, we have $\tilde{\mu}_{n,a^*} \ge \mu_{a^*} - \Delta_{\min}/4$ and $\tilde{\mu}_{n,a} \le \mu_a + \Delta_{\min}/4$ for all $a \ne a^*$, hence

$$a^* = \arg\max_{a \in [K]} \tilde{\mu}_{n,a} = \arg\max_{a \in [K]} [\tilde{\mu}_{n,a}]_0^1 = \tilde{a}_n = B_n.$$

This concludes the proof. $\square$

Lemma 62 shows that the pulling proportion of the best arm converges towards $\beta$. It is a direct consequence of Lemma 61 by using the same proof as Lemma 39 in Azize et al. [2024], hence we omit the proof.

**Lemma 62** (Lemma 39 in Azize et al. [2024]). Let $\gamma > 0$, and $N_1$ be as in Lemma 61. There exists a deterministic constant $C_0 \ge 1$ such that, for all $n \ge C_0 N_1$, we have $|\frac{N_{n,a^*}}{n-1} - \beta| \le \gamma$.

Lemma 63 shows that if a sub-optimal arm overshoots its $\beta$-optimal allocation then it cannot be selected as challenger for large enough $n$.

**Lemma 63.** Let $\gamma \in (0, \gamma_{\mu})$ where $\gamma_{\mu}$ is a problem dependent constant. Let $N_1$ and $C_0$ be as in Lemma 61 and 62. There exists $N_2 \ge C_0 N_1$ with $\mathbb{E}_{\nu_{\pi}}[N_2] < +\infty$ such that, for all $n \ge N_2$,

$$\exists a \neq a^*, \quad \frac{N_{n,a}}{n-1} \geq \gamma + \omega_{\epsilon, \beta, a}^* \quad \implies \quad C_n \neq a.$$

*Proof.* Let $\eta > 0$ and $\gamma > 0$ be small enough, which we will specify below. Let $\tilde{\gamma} \in (0, \gamma)$. Let $N_1$ as in Lemma 61 and $C_0$ as in Lemma 62 for $\tilde{\gamma}$. Let $n \ge C_0 N_1$. Therefore, we have $\tilde{\mu}_n \in (0, 1)^K$ and $\tilde{a}_n = B_n = a^*$ and $|\frac{N_{n,a^*}}{n-1} - \beta| \le \tilde{\gamma}$. Using the same proof as in Lemma 61, there exists $N_3$ with $\mathbb{E}_{\nu_{\pi}}[N_3] < +\infty$ such that, for all $n \ge N_3$, we have $\|\tilde{\mu}_n - \mu\|_{\infty} \le \eta$. Let $n \ge \max\{C_0 N_1, N_3\}$.

Let $a \neq a^*$ such that $\frac{N_{n,a}}{n-1} \ge \omega_{\epsilon, \beta, a}^* + \gamma$. Suppose towards contradiction that $\frac{N_{n,b}}{n-1} > \omega_{\epsilon, \beta, b}^*$ for all $b \notin \{a^*, a\}$. Then, for all $n \ge C_0 N_1$, we have

$$1 - \beta + \tilde{\gamma} \ge 1 - \frac{N_{n,a^*}}{n-1} = \sum_{b \neq a^*} \frac{N_{n,b}}{n-1} > \gamma + \sum_{b \neq a^*} \omega_{\epsilon, \beta, b}^* = 1 - \beta + \gamma,$$

which yields a contradiction since $\tilde{\gamma} < \gamma$. Therefore, for all $n \ge C_0 N_1$, we have

$$\exists a \neq a^*, \quad \frac{N_{n,a}}{n-1} \geq \omega_{\epsilon, \beta, a}^* + \gamma \quad \implies \quad \exists b \notin \{a^*, a\}, \quad \frac{N_{n,b}}{n-1} \leq \omega_{\epsilon, \beta, b}^*.$$

Let $b \notin \{a^*, a\}$ such that $\frac{N_{n,b}}{n-1} \le \omega_{\epsilon, \beta, b}^*$. By definition of the TC challenger, we obtain

$$\begin{align*}
C_n \neq a &\iff W_{\epsilon,a^*,a}(\tilde{\mu}_n, N_n) + \log N_{n,a} > W_{\epsilon,a^*,b}(\tilde{\mu}_n, N_n) + \log N_{n,b} \\
&\iff \frac{1}{n-1} (W_{\epsilon,a^*,a}(\tilde{\mu}_n, N_n) - W_{\epsilon,a^*,b}(\tilde{\mu}_n, N_n)) > \frac{1}{n-1} \log \frac{\omega_{\epsilon,\beta,b}^*}{\omega_{\epsilon,\beta,a}^* + \gamma} \\
&\iff \frac{1}{n-1} (W_{\epsilon,a^*,a}(\tilde{\mu}_n, N_n) - W_{\epsilon,a^*,b}(\tilde{\mu}_n, N_n)) > \frac{1}{n-1} \max_{a \neq b} \left| \log \frac{\omega_{\epsilon,\beta,b}^*}{\omega_{\epsilon,\beta,a}^*} \right|,
\end{align*}$$

where we used the positivity of the $\beta$-optimal allocation (Lemma 43) to ensure that $\max_{a \neq b} \log \frac{\omega_{\epsilon, \beta, b}^*}{\omega_{\epsilon, \beta, a}^*} \in (0, +\infty)$. Using that $\tilde{\mu}_{n,a^*} > \max\{\tilde{\mu}_{n,a}, \tilde{\mu}_{n,b}\}$, we obtain

$$\frac{1}{n-1} (W_{\epsilon,a^*,a}(\tilde{\mu}_n, N_n) - W_{\epsilon,a^*,b}(\tilde{\mu}_n, N_n)) \\
\geq \inf_{u \in [0,1]} \left\{ \frac{N_{n,a^*}}{n-1} d_{\epsilon}^{-}(\tilde{\mu}_{n,a^*}, u) + (\omega_{\epsilon, \beta, a}^* + \gamma) d_{\epsilon}^{+}(\tilde{\mu}_{n,a}, u) \right\}$$
$$ - \inf_{u \in [0,1]} \left\{ \frac{N_{n,a^*}}{n-1} d_{\epsilon}^{-}(\tilde{\mu}_{n,a^*}, u) + \omega_{\epsilon, \beta, b}^{*} d_{\epsilon}^{+}(\tilde{\mu}_{n,b}, u) \right\} \\ \geq \inf_{\tilde{\beta}: |\tilde{\beta} - \beta| \leq \tilde{\gamma}} G_{a,b}(\tilde{\mu}_n, \tilde{\beta}) \geq \inf_{\lambda: \|\lambda - \mu\|_{\infty} \leq \eta} \inf_{\tilde{\beta}: |\tilde{\beta} - \beta| \leq \tilde{\gamma}} G_{a,b}(\lambda, \tilde{\beta}), $$

where, for all $(a, b) \in ([K] \setminus \{a^*\})^2$ such that $a \neq b$,

$$ G_{a,b}(\lambda, \tilde{\beta}) = \inf_{u \in [0,1]} \left\{ \tilde{\beta} d_{\epsilon}^{-}(\lambda_{a^*}, u) + (\omega_{\epsilon, \beta, a}^{*} + \gamma) d_{\epsilon}^{+}(\lambda_{a}, u) \right\} \\ - \inf_{u \in [0,1]} \left\{ \tilde{\beta} d_{\epsilon}^{-}(\lambda_{a^*}, u) + \omega_{\epsilon, \beta, b}^{*} d_{\epsilon}^{+}(\lambda_{b}, u) \right\}. $$

Using the equality at equilibrium from (39) (see Lemma 43) and the fact that the transportation costs are increasing in their allocation argument (see Lemma 37), we obtain $G_{a,b}(\mu, \beta) > 0$ for all $(a, b) \in ([K] \setminus \{a^*\})^2$ such that $a \neq b$, since

$$ \inf_{u \in [0,1]} \left\{ \beta d_{\epsilon}^{-}(\mu_{a^*}, u) + (\omega_{\epsilon, \beta, a}^{*} + \gamma) d_{\epsilon}^{+}(\mu_{a}, u) \right\} > W_{\epsilon, a^*, a}(\mu, w_{\epsilon, \beta}^{*}) = W_{\epsilon, a^*, b}(\mu, w_{\epsilon, \beta}^{*}). $$

By Lemma 49, the functions $(\lambda, \tilde{\beta}) \to G_{a,b}(\lambda, \tilde{\beta})$ and $\lambda \to \inf_{\tilde{\beta}: |\tilde{\beta} - \beta| \leq \tilde{\gamma}} G_{a,b}(\lambda, \tilde{\beta})$ are continuous. Therefore, there exists $\eta_{\mu}$ and $\gamma_{\mu}$ small enough such that

$$ \inf_{\lambda: \|\lambda - \mu\|_{\infty} \leq \eta} \inf_{\tilde{\beta}: |\tilde{\beta} - \beta| \leq \tilde{\gamma}} G_{a,b}(\lambda, \tilde{\beta}) \geq G_{a,b}(\mu, \beta)/2 \geq \frac{1}{2} \min_{\substack{a \neq b, a \neq a^*, b \neq a^*}} G_{a,b}(\mu, \beta) > 0, $$

where the last strict inequality uses that the minimum of a finite number of positive constants is also positive. Considering such $(\eta_{\mu}, \gamma_{\mu})$ at the beginning of the proof and taking $N_2 = \max\{C_0 N_1, N_3, \kappa_{\mu}\}$ where

$$ \kappa_{\mu} = 2 + \frac{2 \max_{a \neq b} \left| \log \frac{\omega_{\epsilon, \beta, b}^{*}}{\omega_{\epsilon, \beta, a}^{*}} \right|}{\min_{\substack{a \neq b, a \neq a^*, b \neq a^*}} G_{a,b}(\mu, \beta)} < +\infty, $$

As it satisfies $\mathbb{E}_{\nu_{\pi}}[N_2] < +\infty$, this concludes the proof. $\square$

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

Lemma 64 shows that the convergence time towards the $\beta$-optimal allocation has finite expectation. It is a direct consequence of Lemmas 61, 62 and 63 by using the same proof as Lemma 41 in Azize et al. [2024], hence we omit the proof.

**Lemma 64** (Lemma 41 in Azize et al. [2024]). Let $\gamma \in (0, \gamma_{\mu})$ where $\gamma_{\mu}$ is a problem dependent constant, and $T_{\gamma}(w)$ as in Eq. (40). Then, we have $\mathbb{E}_{\nu_{\pi}}[T_{\gamma}(\omega_{\epsilon, \beta}^{*})] < +\infty$.

## H.4 Asymptotic Upper Bound

The final step of the generic analysis of Top Two algorithms [Jourdan et al., 2022] is to invert the GLR stopping rule in Eq. (7) by leveraging the convergence of the empirical proportions towards the $\beta$-optimal allocation. Provided this convergence is shown, the asymptotic upper bound on the expected sample complexity only depends on the dependence in $\log(1/\delta)$ of the threshold that ensures $\delta$-correctness. Compared to the non-private GLR stopping rule, the GLR stopping rule in Eq. (7) pay an extra cost to ensure privacy.

**Lemma 65.** Let $\epsilon > 0$, $\eta > 0$ and $(\delta, \beta) \in (0, 1)^2$. Let $T_{\epsilon, \beta}^{*}(\nu)$ as in Eq. (35) and $\omega_{\epsilon, \beta}^{*}$ be its associated $\beta$-optimal allocation. Assume that there exists $\gamma_{\mu} > 0$ such that $\mathbb{E}_{\nu_{\pi}}[T_{\gamma}(\omega_{\epsilon, \beta}^{*})] < +\infty$ for all $\gamma \in (0, \gamma_{\mu})$, where $T_{\gamma}(w)$ is defined in Eq. (40). Combining such a sampling rule, using the GPE$_{\eta}(\epsilon)$ update, with the GLR stopping rule as in Eq. (7) and the stopping threshold $c$ as in Eq. (8) yields an $\epsilon$-global DP and $\delta$-correct algorithm which satisfies that, for all $\nu$ with mean $\mu$ such that $|a^*(\mu)| = 1$,

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

*Proof.* Lemma 5 yields the $\epsilon$-global DP. Theorem 6 yields the $\delta$-correctness.
Let $\zeta > 0$ and $a^*$ be the unique best arm. Using the equality at equilibrium from (39) (see Lemma 43) and the continuity of $(\mu, w) \mapsto \min_{a \neq a^*}(\mu) W_{\epsilon,a^*(\mu),a}(\mu, w)$ (see Lemma 42), there exists $\gamma_\zeta > 0$ such that $\|\frac{N_n}{n-1} - \omega_{\epsilon,\beta}^*\|_\infty \le \gamma_\zeta$ and $\|\tilde{\mu}_n - \mu\|_\infty \le \gamma_\zeta$ implies that

$$ \forall a \neq a^*, \quad W_{\epsilon,a^*,a}(\tilde{\mu}_n, N_n/(n-1)) \geq \frac{(1-\zeta)}{T_{\epsilon,\beta}^*(\boldsymbol{\nu})}. $$

We choose such a $\gamma_\zeta$. Let $\gamma_\mu > 0$ be such that for $\mathbb{E}_{\nu_\pi}[T_\gamma(\omega_{\epsilon,\beta}^*)] < +\infty$ for all $\gamma \in (0, \gamma_\mu)$, where $T_\gamma(\omega)$ is defined in Eq. (40). Let $\gamma \in (0, \min\{\gamma_\mu, \gamma_\zeta, \min_{a \in [K]} \omega_{\epsilon,\beta,a}^*/4, \Delta_{\min}/4, \Delta_0/4\})$ where $\Delta_{\min} = \min_{a \neq a^*}(\mu_{a^*} - \mu_a)$ and $\Delta_0 = \min_{a \in [K]} \min\{\mu_a, 1 - \mu_a\}$. For all $n \ge T_\gamma(\omega_{\epsilon,\beta}^*)$, we have

$$ \tilde{N}_{n,a} \ge N_{n,a}/(1+\eta) \ge (n-1)(\omega_{\epsilon,\beta,a}^* - \gamma)/(1+\eta) \ge (n-1) \frac{3}{4(1+\eta)} \min_{a \in [K]} \omega_{\epsilon,\beta,a}^* > 0, $$

where the last inequality used the positivity of the $\beta$-optimal allocation (Lemma 43). Since arms are sampled linearly, it is direct to construct $N_3 \ge T_\gamma(\omega_{\epsilon,\beta}^*)$ with $\mathbb{E}_{\nu_\pi}[N_3] < +\infty$ such that $\|\tilde{\mu}_n - \mu\|_\infty \le \gamma$ and $\|\frac{N_n}{n-1} - \omega_{\epsilon,\beta}^*\|_\infty \le \gamma$ (as well as $\min_{a \in [K]} N_{n,a} > e$ trivially).

Recall that $c(n, \epsilon, \delta) = c_1(n, \delta) + c_2(n, \epsilon)$ where $n \mapsto c_1(n, \delta)$ and $n \mapsto c_1(n, \delta)$ are increasing (see Lemmas 52 and 39). Since $\tilde{N}_{n,a} \le N_{n,a} \le n$, we obtain

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

Using Lemma 37 and $\tilde{N}_{n,a} \ge N_{n,a}/(1+\eta)$ for all $a \in [K]$ (Lemma 50), we obtain

$$ W_{\epsilon,a^*,a}(\tilde{\mu}_n, \tilde{N}_n) \ge \frac{n-1}{1+\eta} W_{\epsilon,a^*,a} \left( \tilde{\mu}_n, \frac{N_n}{n-1} \right). $$

Let $\kappa \in (0, 1)$ and $T > N_3/\kappa$. For all $n \in [\kappa T, T]$, we have $\tilde{a}_n = a^*$ and, for all $a \neq a^*$,

$$ \begin{align*} \tau_{\epsilon, \delta} &> n \\ \Rightarrow \quad & \exists a \neq a^*, \quad W_{\epsilon, a^*, a}(\tilde{\mu}_n, \tilde{N}_n) \le \sum_{b \in \{a^*, a\}} c(\tilde{N}_n, \epsilon, \delta) \\ \Rightarrow \quad & \exists a \neq a^*, \quad \frac{n-1}{1+\eta} W_{\epsilon, a^*, a} \left( \tilde{\mu}_n, \frac{N_n}{n-1} \right) \le 2(c_1(n, \delta) + c_2(n, \epsilon)) \\ \Rightarrow \quad & \exists a \neq a^*, \quad \frac{n-1}{1+\eta} \frac{(1-\zeta)}{T_{\epsilon, \beta}^*(\boldsymbol{\nu})} \le 2c_1(T, \delta) + 2c_2(T, \epsilon), \end{align*} $$

where we used that $n \mapsto c_1(n, \delta)$ and $n \mapsto c_2(n, \epsilon)$ are increasing and $n \le T$. Therefore, we obtain

$$ \begin{align*} \min \{\tau_{\epsilon, \delta}, T\} &\le \kappa T + \sum_{n=\kappa T}^{T} 1 (\tau_{\delta} > n) \\ &\le \kappa T + \sum_{n=\kappa T}^{T} 1 \left( \frac{n-1}{1+\eta} \frac{(1-\zeta)}{T_{\epsilon, \beta}^*(\boldsymbol{\nu})} \right) \le 2c_1(T, \delta) + 2c_2(T, \epsilon) \\ &\le \kappa T + 1 + \frac{2(1+\eta)T_{\epsilon, \beta}^*(\boldsymbol{\nu})}{1-\zeta} (c_1(T, \delta) + c_2(T, \epsilon)). \end{align*} $$

Let $T_\zeta(\delta)$ defined as

$$ T_{\zeta}(\delta) := \inf \left\{ T \ge 1 \mid \frac{1}{1-\kappa} \left( 1 + \frac{2(1+\eta)T_{\epsilon,\beta}^*(\boldsymbol{\nu})}{1-\zeta} (c_1(T, \delta) + c_2(T, \epsilon)) \right) \le T \right\}. $$

Using Lemma 52, we know that $\bar{W}_{-1}(x) =_{x \to \infty} x + \log x$, hence we have $\limsup_{\delta \to 0} c_1(T, \delta)/\log(1/\delta) \le 1$. Since $\lim_{\delta \to 0} c_2(T, \epsilon)/\log(1/\delta) = 0$, we obtain
$\limsup_{\delta \to 0} \frac{T_\zeta(\delta)}{\log(1/\delta)} \le \frac{2(1+\eta)T_{\epsilon,\beta}^*(\nu)}{(1-\zeta)(1-\kappa)}$. For every $T \ge \max\{T_\zeta(\delta), N_3/\kappa\}$, we have $\tau_{\epsilon,\delta} \le T$, hence $\mathbb{E}_{\nu\pi}[\tau_{\epsilon,\delta}] \le T_\zeta(\delta) + \mathbb{E}_{\nu\pi}[N_3]/\kappa < +\infty$. Therefore, for all $\zeta, \kappa > 0$, we obtain

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

Letting $\zeta$ and $\kappa$ go to zero concludes the proof. $\square$

**Proof of Theorem 7** The proof is obtained by combining Theorem 6 and Lemmas 5, 60, 64 and 65.

# I Variants of Algorithms

In Appendix I, we propose several variants of the algorithmic components used in our algorithm. The objective is to give freedom of choice for the practitioners interested in solving $\epsilon$-global DP BAI. Given the rich literature on BAI, it is unreasonable to provide details for the $\epsilon$-global DP version of all the existing BAI algorithms. Therefore, we settle for a few instances that has received increased scrutiny in the BAI literature.

First, we adapt the Track-and-Stop sampling rule [Garivier and Kaufmann, 2016] to solve $\epsilon$-global DP BAI (Appendix I.1). This leverages the computational tractable procedure to compute the optimal allocation $w_\epsilon^*$ derived in Lemma 47. Second, we explore some alternative choices of components of the Top Two sampling rule for $\epsilon$-global DP BAI (Appendix I.2). This includes adaptive choice of target for the leader, hence aiming at achieving $T_\epsilon^*(\nu)$ instead of $T_{\epsilon,\beta}^*(\nu)$. Third, we adapt the LUCB sampling rule [Kalyanakrishnan et al., 2012] for $\epsilon$-global DP BAI (Appendix I.3).

## I.1 Track-and-Stop Sampling Rule

The Track-and-Stop (TaS) sampling rule was introduced in the seminal paper [Garivier and Kaufmann, 2016]. At each time $n$, it solves the optimization problem defining the characteristic time for the current empirical estimator $\tilde{\mu}_n$. When $\tilde{\mu}_n \in (0, 1)^K$, we define $\tilde{w}_n = w_\epsilon^*(\tilde{\nu}_n)$ where $\tilde{\nu}_n$ is the Bernoulli instance with means $\tilde{\mu}_n$. When $\tilde{\mu}_n \notin (0, 1)^K$, $[\tilde{\mu}_n]_0^1$ corresponds to a degenerate Bernoulli instance, hence we define $\tilde{w}_n = 1_K/K$. Since $\tilde{\mu}_n$ is updated on a per-arm geometric grid governed by $\eta$, the optimal allocation $\tilde{w}_n$ is updated on the same per-arm geometric grid. Therefore, choosing a larger $\eta$ yields lower computational cost of TaS at the cost of larger expected sampled complexity, i.e., asymptotic multiplicative factor $1 + \eta$ due to the update grid.

Given the vector $\tilde{w}_n \in \Delta_K$, the next arm $a_n$ to sample is obtained by using C-Tracking [Garivier and Kaufmann, 2016] with forced exploration in order to ensure that sufficient exploration holds. This is done here by projecting on $\Delta_K^\epsilon = \{w \in [\epsilon, 1]^K | \sum_{a \in [K]} w_a = 1\}$ for a well chosen $\epsilon \in (0, 1/K]$. Let $\tilde{w}_n^\epsilon$ be the $\ell_\infty$ projection of $\tilde{w}_n$ on $\Delta_K^\epsilon$ with $\epsilon_n = (K^2 + n)^{-1/2}/2$. While we consider a projection that changes at each time $n$ (due to $\epsilon_n$), $\tilde{w}_n^\epsilon$ could also be updated on a per-arm geometric grid, i.e., when $\tilde{w}_n$ is updated itself. For all $n \ge K+1$, the TaS sampling rule defines

$$ a_n \in \arg \max_{a \in [K]} \left\{ \sum_{t \in [n]} \tilde{w}_{t,a}^{\epsilon_t} - N_{n,a} \right\}. \quad (43) $$

In summary, our proposed Track-and-Stop algorithm is defined as in DP-TT with the sole modification that Lines 13-14 are replaced by the sampling rule defined in Eq. (43).

**Optimal Allocation Oracle** In Lemma 47, we show that $w_\epsilon^*(\nu)$ can be computed explicitly based on the unique fixed-point solution $F_\mu(y) = 1$ for $y \in [0, \min_{a \ne a^*(\mu)} d_\epsilon^-(\mu_{a^*(\mu)}, \mu_a))$, where $F_\mu$ is an increasing one-to-one mapping from $[0, \min_{a \ne a^*(\mu)} d_\epsilon^-(\mu_{a^*(\mu)}, \mu_a))$ to $[0, +\infty)$ defined as

$$ F_{\mu}(y) = \sum_{a \neq a^{*}(\mu)} \frac{d_{\epsilon}^{-}(\mu_{a^{*}(\mu)}, u_{a}(x_{a}(y)))}{d_{\epsilon}^{+}(\mu_{a}, u_{a}(x_{a}(y)))}. \quad (44) $$

The definitions of $u_a$ and $x_a$ is deferred to Lemma 47, $u_a$ is decreasing and $x_a$ is increasing and strictly convex.
**Asymptotic Expected Sample Complexity** Combining the TaS sampling rule $a_n$ as in Eq. (43) with the GPE$_{η}(\epsilon)$ update and the GLR stopping rule as in Eq. (7) for the stopping threshold as in Eq. (8) yields a $\delta$-correct and $\epsilon$-global DP algorithm (see Lemma 5 and Theorem 6). Moreover, we conjecture that its satisfies that, for all $\nu \in \mathcal{F}^K$ with unique best arm,

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

The multiplicative factor $1+\eta$ comes from the per-arm geometric update grid, and the factor 2 comes from the asymptotic scaling in $2\log(1/\delta)$ of the stopping threshold. Using Theorem 7 for $\beta = 1/2$ and $T_{\epsilon,1/2}^*(\nu) \le 2T_{\epsilon}^*(\nu)$ (Lemma 44), proving this conjecture would only yield an asymptotic improvement by a factor of at most 2. However, this would come at the price of a significantly higher computational cost.

**Proof Sketch of Conjecture** While the detailed proof of this conjecture is beyond the scope of this work, an astute reader could notice that all the necessary steps were proven to derive Theorem 7 for DP-TT. At a high level, it is intuitive that the asymptotic analysis of Track-and-Stop is simpler than the one of DP-TT.

First, the forced exploration is enforced algorithmically, hence an equivalent of Lemma 60 can be shown for the Track-and-Stop sampling rule. In contrast, the proof of sufficient exploration for DP-TT is more challenging and involves a subtle reasoning towards contradiction, see Appendix H.2 for more details.

Second, the convergence towards the optimal allocation is also enforced algorithmically. Thanks to the forced exploration and due to the continuity of $\nu \mapsto w_{\epsilon}^*(\nu)$ (Lemma 42) and the convergence $\tilde{\mu}_n \to_{n \to +\infty} \mu$, the empirical optimal allocation $\tilde{w}_n$ converges towards the true optimal allocation $w_{\epsilon}^*(\nu)$. Therefore, an equivalent of Lemma 64 can be shown for the Track-and-Stop sampling rule. In contrast, the proof of convergence towards $\beta$-optimal allocation for DP-TT is more challenging and leverage subtle regularity properties of the $\beta$ characteristic time and its optimal allocation, e.g., the equality at equilibrium of all the transportations costs in Eq. (39), see Appendix H.3 for more details.

Third, the inversion of the GLR stopping rule can be done similarly as for DP-TT. The sole modification lies in using our derived regularity properties for $w_{\epsilon}^*(\nu)$ instead of $w_{\epsilon,\beta}^*(\nu)$, e.g., the equality at equilibrium of all the transportations costs in Lemma 43. Therefore, an equivalent of Lemma 65 can be shown for the Track-and-Stop sampling rule with $2(1+\eta)T_{\epsilon}^*(\nu)$ instead of $2(1+\eta)T_{\epsilon,\beta}^*(\nu)$, see Appendix H.4 for more details.

## I.2 Top Two Sampling Rule

As detailed in Chapter 2.2 in Jourdan [2024], a Top Two sampling rule is defined by four choices: a leader arm $B_n \in [K]$, a challenger arm $C_n \in [K] \setminus \{B_n\}$, a target $\beta_n(B_n, C_n) \in [0, 1]$ and a mechanism to reach the target, i.e., $a_n \in \{B_n, C_n\}$ by using $\beta_n(B_n, C_n)$. For instance, the sampling rule in DP-TT uses the EB leader, the TCI challenger, a fixed target $\beta \in (0, 1)$ and $K$ independent $\beta$-tracking procedures (one per leader). We propose adaptive choice of target (Appendix I.2.1), as well as leader fostering implicit exploration (Appendix I.2.2).

### I.2.1 Adaptive Target

When the target is fixed to $\beta$ beforehand, the Top Two sampling rule can achieve $T_{\epsilon,\beta}^*(\nu)$ at best. We propose adaptive choices of the target inspired by the recent literature on asymptotically optimal Top Two algorithms [You et al., 2023; Bandyopadhyay et al., 2024].

**BOLD Target** Given the EB-TCI leader/challenger pair $(B_n, C_n)$ defined in DP-TT, we adapt the BOLD target from Bandyopadhyay et al. [2024]. Let us define

$$ u_{\epsilon, B_n, a}(\tilde{\mu}_n, N_n) = \arg \min_{u \in [0,1]} \left\{ N_{n, B_n} d_{\epsilon}^{-}(\tilde{\mu}_{n, B_n}, u) + N_{n, a} d_{\epsilon}^{+}(\tilde{\mu}_{n, a}, u) \right\}, \quad (45) $$
whose closed-form solution is given in Lemma 45. Then, the deterministic BOLD target defines the next arm to pull as

$$a_n = B_n \quad \text{if} \quad \sum_{a \neq B_n} \frac{d_{\epsilon}^{-}(\tilde{\mu}_{n, B_n}, u_{\epsilon, B_n, a}(\tilde{\mu}_n, N_n))}{d_{\epsilon}^{+}(\tilde{\mu}_{n, a}, u_{\epsilon, B_n, a}(\tilde{\mu}_n, N_n))} > 1 \quad \text{and} \quad a_n = C_n \quad \text{otherwise.} \quad (46)$$

In summary, the sole modification in DP-TT is Line 14 that is replaced by the sampling rule defined in Eq. (46).

For any single-parameter exponential family of distributions, Bandyopadhyay et al. [2024] shows that the BOLD target allows to reach asymptotic optimality. Forced exploration is added by Bandyopadhyay et al. [2024] to ensure that sufficient exploration holds. Showing that the BOLD target can achieve asymptotic optimality without forced exploration, i.e., meaning that it ensures sufficient exploration on its own, is an open problem.

**IDS Target** Given the EB-TCI leader/challenger pair $(B_n, C_n)$ defined in DP-TT, we adapt the IDS target from You et al. [2023]. Namely, the randomized IDS target defines the next arm to pull from as

$$a_n = \begin{cases} B_n & \text{with proba } \beta_n(B_n, C_n) \\ C_n & \text{otherwise} \end{cases} \quad \text{where } \beta_n(B_n, C_n) = \frac{N_{n, B_n} d_{\epsilon}^{-}(\tilde{\mu}_{n, B_n}, u_{\epsilon, B_n, C_n}(\tilde{\mu}_n, N_n))}{W_{\epsilon, B_n, C_n}(\tilde{\mu}_n, N_n)}, \quad (47)$$

where $u_{\epsilon, B_n, C_n}(\tilde{\mu}_n, N_n)$ is defined in Eq. (45). In summary, the sole modification in DP-TT is Line 14 that is replaced by the sampling rule defined in Eq. (47).

While we could use $K(K-1)$ tracking procedures to select $a_n \in \{B_n, C_n\}$, we use randomization above for the sake of simplicity. For Gaussian distributions with known variance, You et al. [2023] shows that the IDS target allows to reach asymptotic optimality. Showing that the IDS target can achieve optimality for other classes of distributions is an open problem.

**Asymptotic Expected Sample Complexity** Sampling $a_n$ as in Eq. (46) or (47) for the EB-TCI leader/challenger pair $(B_n, C_n)$ defined in DP-TT based on the GPE$_{\eta}(\epsilon)$ update and the GLR stopping rule as in Eq. (7) for the stopping threshold as in Eq. (8) yields a $\delta$-correct and $\epsilon$-global DP algorithm (see Lemma 5 and Theorem 6).

While we conjecture that their asymptotic expected sample complexities $\limsup_{\delta \to 0} \frac{\mathbb{E}_{\nu\pi[\tau_{\epsilon, \delta}]}$ are both upper bounded by $2(1+\eta)T_{\epsilon}^{*}(\nu)$, we emphasize that our analysis doesn't provide the necessary steps for this result to hold. This is an interesting research direction left for future work.

### I.2.2 Implicit Exploring Leaders and TC Challenger

The empirical best (EB) leader is a greedy choice of leader that doesn't foster implicit exploration. Without additional exploration mechanism, it can suffer from large empirical stopping time despite being enough for an asymptotic analysis, see [Jourdan et al., 2022]. This motivated the choice of the TCI challenger for DP-TT, since it fosters additional implicit exploration by penalizing over sampled challengers with the $\log N_{n,a}$ term. We propose other choices of leaders that foster implicit exploration, and define the TC challenger that removes this penalization.

The UCB leader is defined as

$$B_n^{\text{UCB}} \in \arg \max_{a \in [K]} U_{n,a} \quad \text{where} \quad U_{n,a} = \max \{u \in [0, 1] \mid N_{n,a} d_{\epsilon}^{+}([\tilde{\mu}_{n,a}]_0^1, u) \le \log(n)\}. \quad (48)$$

By adding a bonus to the empirical mean, we are optimistic since we consider that the means are better than suggested by our observations.

The IMED leader builds on the IMED algorithm [Honda and Takemura, 2015] is defined as

$$B_n^{\text{IMED}} \in \arg \min_{a \in [K]} \{N_{n,a} d_{\epsilon}^{+}([\tilde{\mu}_{n,a}]_0^1, \tilde{\mu}_n^*) + \log N_{n,a}\} \quad \text{where} \quad \tilde{\mu}_n^* = \max_{a \in [K]} [\tilde{\mu}_{n,a}]_0^1. \quad (49)$$

The TC challenger is defined as

$$C_n^{\text{TC}} \in \arg \min_{a \neq B_n} W_{\epsilon, B_n, b}(\tilde{\mu}_n, N_n), \quad (50)$$
where $W_{\epsilon,a,b}$ is defined as in Eq. (4).

In summary, the sole modification in DP-TT is Line 13 which can be replaced by choosing the leader as in Eq. (48) or Eq. (49), or choosing the challenger as in Eq. (50).

**Asymptotic Expected Sample Complexity** Choosing the leader as in Eq. (48) or Eq. (49) or the challenger as in Eq. (50) based on the $\beta$-tracking as in DP-TT, the $GPE_{\eta}(\epsilon)$ update and the GLR stopping rule as in Eq. (7) for the stopping threshold as in Eq. (8) yields a $\delta$-correct and $\epsilon$-global DP algorithm (see Lemma 5 and Theorem 6). Moreover, we conjecture that its satisfies that, for all $\nu \in \mathcal{F}^K$ with distinct means,

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

While the detailed proof of this conjecture is beyond the scope of this work, an astute reader could notice that all the necessary steps were proven to derive Theorem 7 for DP-TT. When using the TC challenger as in Eq. (50), the proofs of Lemmas 59 and 63 can be readily adapted. When using the UCB leader as in Eq. (48) or the IMED leader as in Eq. (49), the proofs of Lemmas 56 and 61 could also be adapted.

## I.3 LUCB Sampling Rule

While the Top Two terminology was introduced in Russo [2016], the first sampling rule having a Top Two structure is the greedy sampling strategy in LUCB1 introduced by Kalyanakrishnan et al. [2012]. At each time $n$, it selects the EB leader $B_n^{EB} = \tilde{a}_n$ and the UCB challenger defined as

$$ C_n^{\text{UCB}} \in \underset{a \neq B_n^{\text{EB}}}{\arg\max} U_{n,a} \quad \text{where} \quad U_{n,a} \quad \text{as in Eq. (48)}. \qquad (51) $$

Then, it samples both $B_n^{EB}$ and $C_n^{UCB}$. Instead of using the GLR stopping rule as in Eq.(7), LUCB1 stops when the LCB (lower confidence bound) of the leader exceeds the UCB of the challenger, i.e.,

$$ \tau_{\epsilon, \delta}^{\text{LUCB1}} = \inf \left\{ n \mid \tilde{L}_{n, B_n^{\text{EB}}} > U_{n, C_n^{\text{UCB}}} \right\}, \qquad (52) $$

where

$$ \tilde{L}_{n,a} = \max \left\{ u \in [0, 1] \mid N_{n,a} d_{\epsilon}^{-} ([\tilde{\mu}_{n,a}]_0^1, u) \le \log(n) \right\}. \qquad (53) $$

In summary, the modifications in DP-TT are: (1) the sampling rule in Lines 13-15 is replaced by sampling both $B_n^{EB}$ and $C_n^{UCB}$, and (2) the stopping rule in Line 10 is replaced by Eq. (52). While studying this algorithm is beyond the scope of this work, we emphasize that LUCB is known to not reach asymptotic ($\beta$-)optimality.

# J Implementation Details and Supplementary Experiments

Appendix J is organized as follows. First, we provide additional detail on the implementation details for our algorithm (Appendix J.1). Second, we provide supplementary experiments to illustrate the good performance of our algorithm (Appendix J.2).

## J.1 Implementation Details

We present additional experiments comparing the algorithms in different bandit instances with Bernoulli distributions, as defined by Sajed and Sheffet [2019], namely

$$ \begin{align*} \mu_1 &= (0.95, 0.9, 0.9, 0.9, 0.5), & \mu_2 &= (0.75, 0.7, 0.7, 0.7, 0.7), \\ \mu_3 &= (0.1, 0.3, 0.5, 0.7, 0.9), & \mu_4 &= (0.75, 0.625, 0.5, 0.375, 0.25), \\ \mu_5 &= (0.75, 0.53125, 0.375, 0.28125, 0.25), & \mu_6 &= (0.75, 0.71875, 0.625, 0.46875, 0.25). \end{align*} $$

For each Bernoulli instance, we implement the algorithms with $\epsilon \in \{0.001, 0.005, 0.01, 0.05, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1, 10, 100, 125\}$.

The risk level is set at $\delta = 0.01$. We verify empirically that the algorithms are $\delta$-correct by running each algorithm 1000 times.

We implement all the algorithms in Python (version 3.8) and on an 8 core 64-bits Intel i5@1.6 GHz CPU.
**Choice of Hyperparameters** The default choice $\beta = 1/2$ is motivated by the worst-case inequality $T_{\epsilon, 1/2}^*(\nu) \le 2T_{\epsilon}^*(\nu)$ proven in Lemma 44. It implies that an asymptotically 1/2-optimal algorithm has an expected sample complexity that is at worst twice as high as an asymptotically optimal algorithm. Moreover, this choice ensures that we sample the leader arm (i.e., the empirical estimate for $a^*$) half of the time, and spend the remaining samples to explore all the other suboptimal arms (i.e., the challengers) until we are confident enough about $\tilde{a}_n$ being $a^*$.

The default choice $\eta = 1$ is motivated by the trade-off existing between theoretical guarantees and empirical performance. Based on Theorem 7, smaller $\eta$ yields “better” theoretical asymptotic guarantees, i.e., smaller upper bound on the expected sample complexity of DP-TT. However, the asymptotic regime of $\delta \to 0$ fails to capture the empirical trade-off for moderate values of $\delta$. Choosing $\delta$ arbitrarily close to 0 will result in a large stopping threshold as $k_\eta$ scales as $1/\log(1+\eta)$, see Eq. (8) in Theorem 6. Smaller $\eta$ also implies that a larger cumulative Laplacian noise is added to the cumulative Bernoulli signal. The limit $\eta = 0$ coincides with adding one Laplace noise per Bernoulli observation. The concentration results in Appendix F.6 (Lemmas 18 and 19) show that the rate is governed by $\tilde{d}_\epsilon^\pm(\mu \pm x, \mu, 1)$, which is not equivalent to $d_\epsilon^\pm(\mu \pm x, \mu)$ asymptotically.

**Remark 2.** To implement the thresholds of AdaP-TT, AdaP-TT\* and DP-TT, we use empirical thresholds that we get by approximating the theoretical thresholds. The expressions of the empirical thresholds used can be found in the code in the supplementary material.

## J.2 Supplementary Experiments

Figure 2 confirms our experimental findings from Section 6. 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$.
<figure><img src="image_10.png" /><figcaption>Figure 2: Empirical stopping time $\tau_{\epsilon,\delta}$ (mean $\pm 2$ std. over 1000 runs) for $\delta = 10^{-2}$ with respect to the privacy budget $\epsilon$ for $\epsilon$-global DP on Bernoulli instances $\mu_3, \mu_4, \mu_5$ and $\mu_6$ (top left to bottom right). The shaded vertical line separates the two privacy regimes.</figcaption></figure>