# Bandit Pareto Set Identification in a Multi-Output Linear Model

Cyrille Kone, Emilie Kaufmann, Laura Richert

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

To cite this version:

Cyrille Kone, Emilie Kaufmann, Laura Richert. Bandit Pareto Set Identification in a Multi-Output Linear Model. AISTATS 2025 - 28th International Conference on Artificial Intelligence and Statistics, May 2025, Phuket, Thailand. hal-05125311

HAL Id: hal-05125311

https://hal.science/hal-05125311v1

Submitted on 23 Jun 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Bandit Pareto Set Identification in a Multi-Output Linear Model

Cyrille Kone<fnref n="1" />

Emilie Kaufmann<fnref n="1" />

Laura Richert<fnref n="2" />

## Abstract

We study the Pareto Set Identification (PSI) problem in a structured multi-output linear bandit model. In this setting, each arm is associated a feature vector belonging to $\mathbb{R}^h$, and its mean vector in $\mathbb{R}^d$ linearly depends on this feature vector through a common unknown matrix $\Theta \in \mathbb{R}^{h \times d}$. The goal is to identify the set of non-dominated arms by adaptively collecting samples from the arms. We introduce and analyze the first optimal design-based algorithms for PSI, providing nearly optimal guarantees in both the fixed-budget and the fixed-confidence settings. Notably, we show that the difficulty of these tasks mainly depends on the sub-optimality gaps of $h$ arms only. Our theoretical results are supported by an extensive benchmark on synthetic and real-world datasets.

## 1 INTRODUCTION

A multi-armed bandit is a stochastic game where an agent faces $K$ distributions (or arms) whose means are unknown to her. When the distributions are scalar-valued, the agent faces two main tasks: regret minimization and pure exploration. In the former, the agent aims at maximizing the sum of observations collected along its trajectory (Lattimore and Szepesvári, 2020). In pure exploration, the agent has to solve a stochastic optimization problem after some steps of exploration, and it does not suffer any loss during exploration (Bubeck and Munos, 2008). Examples of pure exploration tasks include best arm identification in which the goal is to find the arm with the largest mean (Audibert and Bubeck, 2010), thresholding ban-

dit (Locatelli et al., 2016), or combinatorial bandits (Chen et al., 2014), to name a few.

In this paper, we are interested in the less common setting where the rewards are $\mathbb{R}^d$-valued, with $d > 1$. Different pure exploration tasks have been considered in this context, e.g., finding the set of feasible arms, i.e., arms whose mean satisfies some constraints (Katz-Samuels and Scott, 2018), or a feasible arm maximizing a linear combination of the different criteria (Katz-Samuels and Scott, 2019; Faizal and Nair, 2022). Finding appropriate constraints is not always possible in practical problems, and our focus is on the identification of the Pareto set, that is, the set of arms whose means are not uniformly dominated by that of any other arm, a setting first studied by (Zuluaga et al., 2013; Auer et al., 2016). We note that a regret minimization counterpart of this problem has been considered by (Drugan and Nowe, 2013).

Pareto set identification can be relevant in many real-world problems where there are multiple, possibly conflicting objectives to optimize simultaneously. Examples include monitoring the energy consumption and runtime of different algorithms (see our use case in Section 5) or identifying a set of interesting vaccines by observing different immunogenicity criteria (antibodies, cellular response, that are not always correlated, as exemplified by Kone et al. (2023)). In both cases, there could be many arms with a few descriptors of the different arms (e.g., vaccine technology, doses, injection times). By incorporating such arm features in the model, we expect to reduce substantially the number of samples needed to identify the Pareto set.

In this work, we incorporate some structure in the PSI identification problem through a multi-output linear model, formally described in Section 2. In this model, each of the $K$ arms whose means are in $\mathbb{R}^d$ is described by a feature vector in $\mathbb{R}^h$, $h > 1$. We propose the GEGE algorithm, which combines a G-optimal design exploration mechanism with an accept/reject mechanism based on the estimation of some notion of sub-optimality gap. GEGE can be instantiated in both the fixed-budget setting (given at most $T$ samples, output

<footnote n="1">¹ Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9198-CRIStAL, F-59000 Lille, France</footnote>

<footnote n="2">² Univ. Bordeaux, Inserm, Inria, BPH, U1219, Sistm, F-33000 Bordeaux, France</footnote>

<footnote>Proceedings of the 28th International Conference on Artificial Intelligence and Statistics (AISTATS) 2025, Mai Khao, Thailand. PMLR: Volume 258. Copyright 2025 by the author(s).</footnote>
a guess of the Pareto set minimizing the error probability) and the fixed-confidence setting (minimize the number of samples used to guarantee an error probability smaller than some prescribed $\delta$). Through a unified analysis, we show that in both cases, the sample complexity of GEGE, that is, the number of samples needed to guarantee a certain probability of error, scales only with the $h$ smallest sub-optimality gaps. This yields a reduction in sample complexity due to the structural assumption. Finally, we empirically evaluate our algorithms with extensive synthetic and real-world datasets and compare their performance with other state-of-the-art algorithms.

**Related work** When $d=1$ and the feature vectors are the canonical basis of $\mathbb{R}^K$, PSI coincides with the best arm identification problem, that has been extensively studied in the literature both in the fixed-budget (Audibert and Bubeck, 2010; Karnin et al., 2013; Carpentier and Locatelli, 2016) and the fixed-confidence settings Kalyanakrishnan et al. (2012); Jamieson et al. (2014). For sub-Gaussian distributions, the sample complexity is known to be essentially characterized (up to a $\log(K)$ factor in the fixed-budget setting) by a sum over the $K$ arms of the inverse squared value of their *sub-optimality gap*, which is their distance to the (unique) optimal arm. In the fixed-confidence setting and for Gaussian distributions, there are even algorithms matching the minimal sample complexity when $\delta$ goes to zero, which takes a more complex, non-explicit form (e.g., Garivier and Kaufmann (2016); You et al. (2023)).

Still, when $d=1$ but for general features in $\mathbb{R}^h$, our model coincides with the well-studied linear bandit model (with finitely many arms), in which the best arm identification task has also received some attention. It was first studied by Soare et al. (2014) in the fixed-confidence setting, who established the link with optimal designs of experiments (Pukelsheim, 2006), showing that the minimal sample complexity can be expressed as an optimal (XY) design. The authors proposed the first elimination algorithms where, in each round the surviving arms are pulled according to some optimal designs and obtained a sample complexity scaling in $(h/\Delta_{\min}^2) \log(1/\delta)$ where $\Delta_{\min}$ is the smallest gap in the model. Tao et al. (2018) further proposed an elimination algorithm using a novel estimator of the regression parameter based on a G-optimal design, with an improved sample complexity in $\sum_{i=1}^h \Delta_{(i)}^{-2} \log(1/\delta)$ where $\Delta_{(1)} \le \dots \le \Delta_{(h)}$ are the $h$ smallest gaps. This bound improves upon the complexity of the unstructured setting when $K \gg h$. Some algorithms even match the minimal sample complexity either in the asymptotic regime $\delta \to 0$ (Degenne et al., 2020; Jedra and Proutiere, 2020) or within mul-

tiplicative factors Fiez et al. (2019). Some adaptive algorithms, such as LinGapE Xu et al. (2018) are also very effective in practice but without provably improving over unstructured algorithms in all instances.

The fixed-budget setting has been studied by Azizi et al. (2022); Yang and Tan (2022), who propose algorithms based on Sequential Halving (Karnin et al., 2013) where in each round, the active arms are sampled according to a G-optimal design. The best guarantees are those obtained by Yang and Tan (2022) who show that a budget $T$ of order $\log_2(h) \sum_{i=1}^h \Delta_{(i)}^{-2} \log(1/\delta)$ is sufficient to get an error smaller than $\delta$. Katz-Samuels et al. (2020) propose an elimination algorithm that can be instantiated both in the fixed confidence and fixed budget settings and is close in spirit to our algorithm. However, unlike prior work, their optimal design aims at minimizing a new complexity measure called the Gaussian width that may better characterize the non asymptotic regime of the error. Extending this notion, or that of minimal (asymptotic) sample complexity to linear PSI is challenging due to the complex structure of the set of alternative models with a different Pareto set. In this work, our focus is on obtaining refined gap-based guarantees for the structured PSI problem.

When $d > 1$, the PSI identification problem has been mostly studied in the unstructured setting ($h = K$, canonical basis features). Auer et al. (2016) introduced some appropriate (non-trivial) notions of sub-optimality gaps for the PSI problem, which we recall in the next section. They proposed an elimination-based fixed-confidence algorithm whose sample complexity scales in $\sum_{i=1}^K \Delta_i^{-2} \log(1/\delta)$, which is proved to be near-optimal. A fully sequential algorithm with some slightly smaller bound was later given by Kone et al. (2023), who can further address different relaxations of the PSI problem. Kone et al. (2024) proposed the first fixed-budget PSI algorithm: a generic round-based elimination algorithm that estimates the sub-optimality gaps of Auer et al. (2016) and discard and classify some arms at the end of each round, with a sample complexity in $\sum_{i=1}^K \Delta_i^{-2} \log(K) \log(1/\delta)$.

The multi-output linear setting that we consider in this paper was first studied by Lu et al. (2019) from the Pareto regret minimization perspective. This model may also be viewed as a special case of the multi-output kernel regression model considered by Zuluaga et al. (2016) when a linear kernel is chosen. This work provides guarantees for approximate identification of the Pareto set, scaling with the information gain. Choosing appropriately the approximation parameter in $\varepsilon$-PAL as a function of the smallest gap $\Delta_{\min}$ yields a fixed-confidence PSI algorithm with sample complexity of order $(h^2/\Delta_{\min}^2) \log(1/\delta)$. More re-
cently, the preliminary work of Kim et al. (2023) proposed an extension of the fixed-confidence algorithm of Auer et al. (2016) with a robust estimator to simultaneously minimize the Pareto regret and identify the Pareto set. Their claimed sample complexity bound is in $(h/\Delta_{\min}^2) \log(1/\delta)$.

**Contributions** We propose GEGE, the first algorithm for PSI that relies on an optimal design to estimate the PSI gaps. In the fixed-confidence setting, GEGE only uses $O(\log(1/\Delta_{(1)}))$ adaptive rounds to identify the Pareto set, and we prove an improved sample complexity bounds in which $(h/\Delta_{\min}^2)$ is replaced by the sum $\sum_{i=1}^h \Delta_{(i)}^{-2}$. Moreover, to the best of our knowledge, the fixed-budget variant of GEGE is the first algorithm for fixed-budget PSI in a multi-output linear bandit model and enjoys near-optimal performance. Our experiments confirm these good theoretical properties and illustrate the impact of the structural assumption.

## 2 SETTING

We formalize the linear PSI problem. Let $d, h \in \mathbb{N}^*$ and $h \le K$. $\nu_1, \dots, \nu_K$ are distributions over $\mathbb{R}^d$ with means (resp.) $\mu_1, \dots, \mu_K \in \mathbb{R}^d$. We assume there are known feature vectors $x_1, \dots, x_K \in \mathbb{R}^h$ associated to each arm and an unknown matrix $\Theta \in \mathbb{R}^{h \times d}$ such that for any arm $k$, $\mu_k = \Theta^T x_k$. Let $\mathcal{X} := (x_1 \dots x_K)^T$ and $[K] = \{1, \dots, K\}$. The Pareto set is defined as $S^* = \{i \in [K] : \nexists j \in [K] \setminus \{i\} : \mu_i \le \mu_j\}$ in the sense of the following (Pareto) dominance relationship.

**Definition 1.** For any two arms $i, j \in [K]$, $i$ is weakly dominated by $j$ if for any $c \in \{1, \dots, d\}$, $\mu_i(c) \le \mu_j(c)$. An arm $i$ is dominated by $j$ ($\mu_i \le \mu_j$ or simply $i \le j$) if $i$ is weakly dominated by $j$ and there exists $c \in \{1, \dots, d\}$ such that $\mu_i(c) < \mu_j(c)$. An arm $i$ is strictly dominated by $j$ ($\mu_i < \mu_j$ or simply $i < j$) if for any $c \in \{1, \dots, d\}$, $\mu_i(c) < \mu_j(c)$.

In each round $t$, an agent chooses an action $a_t$ from $[K]$ and observes a response $y_t = \Theta^T x_{at} + \eta_t$ where $(\eta_s)_s \le t$ are i.i.d centered vectors in $\mathbb{R}^d$ whose marginal distributions are $\sigma$-subgaussian.<fnref n="1" /> In this stochastic game, the goal of the agent is to identify the Pareto set $S^*$. In the fixed-confidence setting, given $\delta \in (0, 1)$, the agent collects samples up to a (random) stopping time $\tau$ and outputs a guess $\hat{S}_\tau$ that should satisfy $\mathbb{P}(\hat{S}_\tau \neq S^*) \le \delta$ while minimizing $\tau$ (either with high-probability or in expectation). In the fixed-budget setting, the agent should output a set $\hat{S}_T$ after $T$ (fixed) rounds and minimize $e_T := \mathbb{P}(\hat{S}_T \neq S^*)$.

**Notation** The following notation is used throughout the paper. $\Delta_n$ is the probability simplex of $\mathbb{R}^n$ and if $A \in \mathbb{R}^{n \times n}$ is positive semidefinite, for $x \in \mathbb{R}^n$, $\|x\|_A^2 = x^T A x$ and $x(i)$ denotes the $i$-th component of $x$. For $a, b \in \mathbb{R}$, $a \wedge b := \min(a, b)$, and $(a)_+ := \max(a, 0)$.

### 2.1 Complexity Measures for Pareto Set Identification

Choosing the features vectors to be the canonical basis of $\mathbb{R}^K$ and $\Theta = (\mu_1, \dots, \mu_K)^T$, we recover the unstructured multi-dimensional bandit model, in which the complexity of Pareto set identification is known to depend on some notion of sub-optimality gaps, first introduced by Auer et al. (2016). These gaps can be expressed with the quantities

$$m(i, j) := \min_{c \in [d]} [\mu_j(c) - \mu_i(c)] \text{ and } M(i, j) := -m(i, j).$$

We can observe that $m(i, j) > 0$ iff $i \prec j$ and represents the amount by which $j$ dominates $i$ when positive. Similarly, $M(i, j) > 0$ iff $i \not\prec j$ and when positive represents the quantity that should be added component-wise to $j$ for it to dominate $i$. The sub-optimality gap $\Delta_i$ measures the difficulty of classifying arm $i$ as optimal or sub-optimal and can be written (Lemma 1 of Kone et al. (2024))

$$\Delta_i := \begin{cases} \Delta_i^* := \max_{j \in [K]} m(i, j) & \text{if } i \notin S^* \\ \delta_i^* & \text{else,} \end{cases} \quad (1)$$

where $\delta_i^* := \min_{j \neq i}[M(i, j) \wedge (M(j, i)_+ + (\Delta_j^*)_+)$. For a sub-optimal arm $i$, $\Delta_i$ is the smallest quantity by which $\mu_i$ should be increased to make $i$ non-dominated. For an optimal arm $i$, $\Delta_i$ is the minimum between some notion of "distance" to the other optimal arms, $\min_{j \in S^* \setminus \{i\}}[M(i, j) \wedge M(j, i)]$ and the smallest margin to the sub-optimal arms $\min_{j \notin S^*}[M(j, i)_+ + (\Delta_j^*)_+].$ These quantities are illustrated in Appendix G. We assume without loss of generality that $\Delta_1 \le \dots \le \Delta_K$ and we recall the quantities $H_1 = \sum_{i=1}^K \Delta_i^{-2}$ and $H_2 := \max_{i \in [K]} i \Delta_i^{-2}$ which have been used to measure the difficulty of Pareto set identification respectively in fixed-confidence (Auer et al., 2016) and fixed-budget (Kone et al., 2024) settings. In this work, we introduce two analog quantities for linear PSI, namely

$$H_{1,\text{lin}} = \sum_{i=1}^{h} \frac{1}{\Delta_i^2} \quad \text{and} \quad H_{2,\text{lin}} := \max_{i \in [h]} \frac{i}{\Delta_i^2} \quad (2)$$

and we will show that the hardness of linear PSI can be characterized by $H_{1,\text{lin}}$ and $H_{2,\text{lin}}$ respectively in the fixed-confidence and fixed-budget regimes. These complexity measures are smaller than $H_1$ and $H_2$, respectively, as they only feature the $h$ smallest gaps. To obtain this reduction in complexity, it is crucial to estimate the underlying parameter $\Theta \in \mathbb{R}^{h \times d}$ instead of the $K$ mean vectors.

<footnote n="1">¹A centered random variable $X$ is $\sigma$-subgaussian if for any $\lambda \in \mathbb{R}$, $\log \mathbb{E}[\exp(\lambda X)] \le \lambda^2 \sigma^2/2$.</footnote>
## 2.2 Least Square Estimation and Optimal Designs

Given $n$ arm choices in the model, $a_1, \dots, a_n$, we define $X_n := (x_{a_1} \dots x_{a_n})^\top \in \mathbb{R}^{n \times h}$ and we denote by $Y_n := (y_1 \dots y_n)^\top \in \mathbb{R}^{n \times d}$ the matrix gathering the vector of responses collected. We define the information matrix as $V_n := X_n^\top X_n = \sum_{i=1}^K T_n(i)x_i x_i^\top \in \mathbb{R}^{h \times h}$ where $T_n(i)$ denotes the number of observations from arm $i$ among the $n$ samples. More generally, given $w \in \mathbb{R}^K$, we define $V^w := \sum_{i=1}^K w(i)x_i x_i^\top$.

The multi-output regression model can be written in matrix form as $Y_n = X_n \Theta + H_n$ where $H_n = (\eta_1 \dots \eta_n)^\top$ is the noise matrix. The least-square estimate $\hat{\Theta}_n$ of the matrix $\Theta$ is defined as the matrix minimizing the least-square error $Err_n(A) := \|X_n A - Y_n\|_F^2$. Computing the gradient of the loss yields $V_n \hat{\Theta}_n = X_n^\top Y_n$. If the matrix $V_n$ is non-singular, the least-square estimator can be written

$$ \hat{\Theta}_n = V_n^{-1} X_n^\top Y_n. $$

In the course of our elimination algorithm, we will compute least-square estimates based on observation from a restricted number of arms, and we will face the case in which $V_n$ is singular. In this case, different choices have been made in prior work on linear bandits: Alieva et al. (2021) defines a custom “pseudo-inverse” while Yang and Tan (2022) define new contexts $\tilde{x}_i$ that are projections of the $x_i$ onto a sub-space of dimension rank($\mathcal{X}_S$) where $\mathcal{X}_S := (x_i : i \in S)^\top$ and $S$ is the set of arms that are active. We adopt an approach close to the latter, which is described below. Let the singular-value decomposition of $(\mathcal{X}_S)^\top$ be $USV^\top$ where $U, V$ are orthogonal matrices and $B := (u_1, \dots, u_m)$ is formed with the first $m$ columns of $U$ where $m = \text{rank}(\mathcal{X}_S)$. We then define

$$ V_n^\dagger := B(B^\top V_n B)^{-1} B^\top \quad \text{and} \quad \hat{\Theta}_n = V_n^\dagger X_n^\top Y_n. \quad (3) $$

The following result addresses the statistical uncertainty of this estimator.

**Lemma 1.** If the noise $\eta_t$ has covariance $\Sigma \in \mathbb{R}^{d \times d}$ and $a_1, \dots, a_n$ are deterministically chosen then for any $x_i \in \{x_{a_1}, \dots, x_{a_n}\}$, $\text{Cov}(\hat{\Theta}_n^\top x_i) = \|x_i\|_{V_n^\top}^2 \Sigma$.

Therefore, estimating all arms' mean uniformly efficiently amounts to pull $\{a_1, \dots, a_n\}$ to minimize $\max_{i \in S} \|x_i\|_{V_n^\top}^2$. The continuous relaxation of this problem is equivalent to computing an allocation

$$ w_S^* \in \underset{w \in \Delta_{|S|}}{\operatorname{argmin}} \max_{i \in S} \|\tilde{x}_i\|_{(\tilde{V}^w)^{-1}}^2 \quad (4) $$

where $\tilde{x}_i := B^\top x_i$, $\tilde{V}^w := \sum_{i \in S} w(s_i) \tilde{x}_i \tilde{x}_i^\top$ and $i \mapsto s_i$ maps $S$ to $\{1, \dots, |S|\}$. (4) is a G-optimal design over

the features $(B^\top x_i, i \in S)$ and it can be interpreted as a distribution over $S$ that yields a uniform estimation of the mean responses for (3). This is formalized in Appendix H.

# 3 OPTIMAL DESIGN ALGORITHMS FOR LINEAR PSI

Our elimination algorithms operate in rounds. They progressively eliminate a portion of arms and classify them as optimal or sub-optimal based on empirical estimation of their gaps. In each round, a sampling budget is allocated among the surviving arms based on a G-optimal design.

## 3.1 Optimal Designs and Gap Estimation

At round $r$, we denote by $A_r$ the set of arms that are still active. To estimate the means and, henceforth, the gaps, we first compute an estimate of the regression matrix denoted $\hat{\Theta}_r$. This estimate is obtained by carefully sampling the arms using the integral rounding of a G-optimal design.

**Algorithm 1: OptEstimator(S, N, $\kappa$)**

**Input:** Subset $S \subset [K]$, sample size $N$, precision $\kappa$
Compute the transformed features $\tilde{\chi}_S = (B^\top x_i, i \in S)$ with $B$ as defined in Section 2.2
Compute a G-optimal design $w_S^*$ over the set $\tilde{\chi}_S$
Pull $(a_1, \dots, a_N) \leftarrow \text{ROUND}(N, \tilde{\chi}_S, w_S^*, \kappa)$ and collect responses $y_1, \dots, y_N$
Compute $V_N^\dagger$ as in Eq. (3) and compute the OLS estimator on the samples collected

$$ \hat{\Theta} \leftarrow V_N^\dagger \sum_{t=1}^{N} x_{a_t}^\top y_t $$

**return:** $\hat{\Theta}$

Algorithm 1 takes as input a set of arms $S$, a budget $N$ and chooses some $N$ arms to pull (with repetitions) based on an integer rounding of $w_S^*$, a continuous G-optimal design over the set $\{\tilde{x}_i, i \in S\}$ of (transformed) features associated to that arms. Several rounding procedures have been proposed in the literature, and we use that of Allen-Zhu et al. (2017), henceforth referred to as **ROUND**. In Appendix H, we show that $\text{ROUND}(N, \tilde{\chi}_S, w_S^*, \kappa)$ outputs a sequence of arms $a_1, \dots, a_N \in S$ such that $\max_{i \in S} \|x_i\|_{V_N^\top}^2 \le (1 + 6\kappa) \frac{F_S(w_S^*)}{N}$, where $F_S(w_S^*)$ is the optimal value of
(4). Using the Kiefer-Wolfowitz theorem (Kiefer and Wolfowitz, 1960), we further prove that $F_S(w_S^*) = h_S$, the dimension of span($\{x_i, i \in S\}$). This observation is crucial to prove the following concentration result at the heart of our analysis.

**Lemma 2.** Let $S \subset [K]$, $\kappa \in (0, 1/3]$ and $N \ge 5h_S/\kappa^2$ where $h_S = \dim(\operatorname{span}(\{x_i : i \in S\}))$. The output $\hat{\Theta}$ of OptEstimator($S$, $N$, $\kappa$) satisfies for all $\varepsilon > 0$ and $i \in S$

$$ \mathbb{P}\left(\| (\Theta - \hat{\Theta})^{\top} x_i \|_{\infty} \ge \varepsilon\right) \le 2d \exp\left(-\frac{N\varepsilon^2}{2(1 + 6\kappa)\sigma^2 h_S}\right). $$

Once the parameter $\hat{\Theta}_r$ has been obtained as an output of Algorithm 1 with $S = A_r$ and an appropriate value of the budget $N$, we compute estimates of the mean vectors as $\hat{\mu}_{i,r} := \hat{\Theta}_r^\top x_i$ and the empirical Pareto set of active arms,

$$ S_r := \{i \in A_r : \mathfrak{D}j \in A_r : \hat{\mu}_{i,r} < \hat{\mu}_{j,r}\}. $$

In both the fixed-confidence and fixed-budget settings, at round $r$, after collecting new samples from the surviving arms, GEGE discards a fraction of the arms based on the empirical estimation of their gaps. We first introduce the empirical quantities used to compute the gaps:

$$ M(i, j; r) := \max_{c \in [d]} [\hat{\mu}_{i,r}(c) - \hat{\mu}_{j,r}(c)] \quad \text{and} $$

$$ m(i, j; r) := \min_{c \in [d]} [\hat{\mu}_{j,r}(c) - \hat{\mu}_{i,r}(c)]. $$

We define for any arm $i \in A_r$, the empirical estimates of the PSI gaps as:

$$ \hat{\Delta}_{i,r} := \begin{cases} \hat{\Delta}_{i,r}^* := \max_{j \in A_r} m(i, j; r) & \text{if } i \in A_r \setminus S_r \\ \hat{\delta}_{i,r}^* & \text{if } i \in S_r \end{cases} \quad (5) $$

with $\hat{\delta}_{i,r}^* := \min_{j \in A_r \setminus \{i\}} [M(i, j; r) \wedge (M(j, i; r)_+ + (\hat{\Delta}_{i,r}^*)_+)]$; the empirical estimates of the gaps introduced earlier in Section 2.1. Differently from BAI, as the size of the Pareto set is unknown, we need an accept/reject mechanism to classify any discarded arm. This mechanism is described in detail in the next sections for the fixed-budget and fixed-confidence versions.

**Final output** In both cases, letting $A_r$ be the set of active arms and $B_r$ be the set of arms already classified as optimal at the beginning of round $r$, GEGE outputs $B_{\tau+1} \cup A_{\tau+1}$ as the candidate Pareto optimal set, where $\tau$ denotes the final round. And $A_{\tau+1}$ contains at most one arm.

## 3.2 Fixed-budget algorithm

Algorithm 2, operates over $\lceil \log_2(h) \rceil$ rounds, with an equal budget of $T/\lceil \log_2(h) \rceil$ allocated per round. By construction $|A_{\lceil \log_2(h) \rceil+1}|= 1$. At the end of round $r$, the $\lceil h/2^r \rceil$ arms with the smallest empirical gaps are kept active while the remaining arms are discarded and classified as Pareto optimal (added to $B_{r+1}$) if they are empirically optimal (belonging to set $S_r$) and deemed sub-optimal otherwise. If a tie occurs, we break it to eliminate arms that are empirically sub-optimal. This is crucial to prove the guarantees on the algorithm, as sketched in Section 4.

<caption>**Algorithm 2:** GEGE: G-optimal Empirical Gap Elimination [fixed-budget]</caption>

**Input:** budget $T$
**Initialize:** let $A_1 \leftarrow [K]$, $B_1 \leftarrow \emptyset$, $D_1 \leftarrow \emptyset$
**for** $r = 1$ **to** $\lceil \log_2(h) \rceil$ **do**
    Compute $\hat{\Theta}_r \leftarrow \text{OptEstimator}(A_r, T/\log_2(h), 1/3)$
    Compute $S_r$ the empirical Pareto set and the empirical gaps $\hat{\Delta}_{i,r}$ with Eq. (5)
    Compute $A_{r+1}$ the set of $\lceil \frac{h}{2^r} \rceil$ arms in $A_r$ with the smallest empirical gaps
    // ties broken by keeping arms of $S_r$
    Update $B_{r+1} \leftarrow B_r \cup \{S_r \cap (A_r \setminus A_{r+1})\}$
    and $D_{r+1} \leftarrow D_r \cup \{(A_r \setminus A_{r+1}) \setminus S_r\}$
    **return:** $B_{\lceil \log_2(h) \rceil+1} \cup A_{\lceil \log_2(h) \rceil+1}$

**Theorem 1.** *The probability of error of Algorithm 2 run with budget $T \ge 45h \log_2 h$ is at most*

$$ \exp\left(-\frac{T}{1200\sigma^2 H_{2,\text{lin}} \lceil \log_2 h \rceil} + \log C(h, d, K)\right) $$

where $C(h, d, K) = 2d(K + h + \lceil \log_2 h \rceil)$.

To the best of our knowledge, GEGE is the first algorithm with theoretical guarantees for fixed-budget linear PSI. Our result shows that in this setting, the probability of error scales only with the first $h$ gaps. Kone et al. (2024) proposed EGE-SH, an algorithm for fixed-budget PSI in the unstructured setting whose probability of error is essentially upper-bounded by

$$ \exp\left(-\frac{T}{288\sigma^2 H_2 \log_2 K} + \log(2d(K-1)|S^*|\log_2 K)\right). $$

Therefore, GEGE largely improves upon EGE-SH when $K \gg h$. Moreover, when $K = h$ and $x_1, \dots, x_K$ is the canonical $\mathbb{R}^h$-basis, both algorithms coincide, thus, GEGE can be seen as a generalization of EGE-SH.

We state below a lower bound for linear PSI in the fixed-budget setting, showing that GEGE is optimal
in the worst case, up to constants and a $log_2(h)$ factor.

**Theorem 2.** Let $W_H$ be the set of instances with complexity $H_{2,lin}$ smaller than $H$. For any budget $T$, letting $\hat{S}_T^A$ be the output of an algorithm $\mathcal{A}$, it holds that

$$ \inf_{\mathcal{A}} \sup_{\nu \in W_H} \mathbb{P}_{\nu}(\hat{S}_T^A \neq S^*(\nu)) \geq \frac{1}{4} \exp\left(-\frac{2T}{H\sigma^2}\right). $$

### 3.3 Fixed-confidence algorithm

In round $r$, Algorithm 3, allocates a budget $t_r$ to compute an estimator $\hat{\Theta}_r$ of $\Theta^*$ by calling Algorithm 1. $t_r$ is computed so that through $\hat{\Theta}_r$, the mean of each arm is estimated with precision $\epsilon_r/4$ with probability larger than $1 - \delta_r$ (using Lemma 2). Then, the empirical Pareto set $S_r$ of the active arms is computed, and the empirical gaps are updated following (5).

At the end of round $r$, empirically optimal arms (those in $S_r$) whose empirical gap is larger than $\epsilon_r$ are discarded and classified as optimal (added to $B_{r+1}$). Empirically sub-optimal arms whose empirical gap is larger than $\epsilon_r/2$ are also discarded and classified as sub-optimal (added to $D_{r+1}$).

**Algorithm 3: GEGE: G-optimal Empirical Gap Elimination [fixed-confidence]**

Initialize: $A_1 \leftarrow [K]$, $B_1 \leftarrow \emptyset$, $D_1 \leftarrow \emptyset$, $r \leftarrow 1$ 
while $|A_r| > 1$ do
  Let $\epsilon_r \leftarrow 1/(2 \cdot 2^r)$ and $\delta_r \leftarrow 6\delta/\pi^2 r^2$ and
  $h_r \leftarrow \text{dim}(\text{span}(\{x_i : i \in A_r\}))$
  Update $t_r := \left\lfloor \frac{32(1+3\epsilon_r)\sigma^2 h_r}{\epsilon_r^2} \log\left(\frac{|A_r|d}{2\delta_r}\right) \right\rfloor$
  Compute $\hat{\Theta}_r \leftarrow \text{OptEstimator}(A_r, t_r, \epsilon_r)$
  Compute $S_r$ and the empirical gaps $\hat{\Delta}_{i,r}$ with Eq. (5)
  Update $B_{r+1} \leftarrow B_r \cup \{i \in S_r : \hat{\Delta}_{i,r} \ge \epsilon_r\}$ and
  $D_{r+1} \leftarrow D_r \cup \{i \in A_r \setminus S_r : \hat{\Delta}_{i,r} \ge \epsilon_r/2\}$
  Update $A_{r+1} \leftarrow A_r \setminus (D_{r+1} \cup B_{r+1})$
  $r \leftarrow r+1$
return: $B_r \cup A_r$

**Theorem 3.** The following statement holds with probability at least $1 - \delta$: Algorithm 3 identifies the Pareto set using at most

$$ \log_2(2/\Delta_1) + O\left(\sum_{i=2}^{h} \frac{\sigma^2}{\Delta_i^2} \log\left(\frac{Kd}{\delta} \log_2\left(\frac{2}{\Delta_i}\right)\right)\right) $$

samples and $\lceil \log_2(1/\Delta_1) \rceil$ rounds, where $O(\cdot)$ hides universal multiplicative constant (explicit in Appendix E.3).

This result shows that the complexity of Algorithm 3 scales only with the first $h$ gaps. In particular, when $K \gg h$ using our algorithm substantially reduces the sample complexity of PSI. In Table 1, we compare the sample complexity of GEGE to that of existing fixed-confidence PSI algorithms, showing that GEGE enjoys stronger guarantees than its competitors. We emphasize that both Kim et al. (2023) and Zuluaga et al. (2016) use uniform sampling and do not exploit an optimal design, which prevents them from reaching the guarantees given in Theorem 3.

<table><caption>**Table 1:** Sample complexity up to constant multiplicative terms of different algorithms for PSI in the fixed-confidence setting.</caption><thead><tr><th>Algorithm</th><th>Upper-bound on &tau;<sub>&delta;</sub></th><th>Linear PSI</th></tr></thead><tbody><tr><td>Zuluaga et al. (2016)</td><td>(h<sup>2</sup> / &Delta;<sub>min</sub><sup>2</sup>) log<sup>3</sup> (Kd / &delta;)</td><td>&#10003;</td></tr><tr><td>Kone et al. (2023)</td><td>&Sigma;<sup>K</sup><sub>i=1</sub> (1 / &Delta;<sub>i</sub><sup>2</sup>) log(Kd / &delta; log(1 / &Delta;<sub>i</sub><sup>1</sup>))</td><td>&#10003;</td></tr><tr><td>Kim et al. (2023)</td><td>(h / &Delta;<sub>min</sub><sup>2</sup>) log(d(h &or; K) / (&delta;&Delta;<sub>min</sub><sup>2</sup>))</td><td>&#10003;</td></tr><tr><td>GEGE (Ours)</td><td>&Sigma;<sup>h</sup><sub>i=1</sub> (1 / &Delta;<sub>i</sub><sup>2</sup>) log(Kd / &delta; log(1 / &Delta;<sub>i</sub><sup>1</sup>))</td><td>&#10003;</td></tr></tbody></table>

We state a lower bound, showing that our algorithm is essentially minimax optimal for linear PSI.

**Theorem 4.** For any $K, d, h \in \mathbb{N}$, there exists a set $\mathcal{B}(K, d, h)$ of linear PSI instances s.t for $\nu \in \mathcal{B}(K, d, h)$ and for any $\delta$-correct algorithm for PSI, with probability at least $1 - \delta$,

$$ \tau_{\delta}^{A} \ge \Omega(H_{1,lin}(\nu) \log(\delta^{-1})). $$

**Remark 1.** When $K = h$ and $x_1, \dots, x_K$ form the canonical $\mathbb{R}^h$ basis, we recover the classical PSI problem. We note that, unlike its fixed-budget version, GEGE does not coincide with an existing PSI identification algorithm. Instead, it matches the optimal guarantees of Kone et al. (2023) while needing only $\lceil \log(1/\Delta_1) \rceil$ rounds of adaptivity, which is the first fixed-confidence PSI algorithm having this property. Such a batched algorithm may be desirable in some applications, e.g., in clinical trials where measuring different biological indicators of efficacy can take time.

**GEGE for $\epsilon$-PSI** Algorithm 3 can be easily modified to identify an $\epsilon$-Pareto Set. As introduced in Auer et al. (2016), an $\epsilon$-Pareto Set $S_\epsilon$ is such that $S^* \subset S_\epsilon$ and for any arm $i \in S_\epsilon$, $\Delta_i^* \le \epsilon$: it contains the Pareto Set and possibly some sub-optimal arms that are $(\epsilon)$-close to be optimal. Such a relaxation is particularly useful in instances with small gaps or when identifying the exact Pareto Set may be unnecessarily restrictive. To identify an $\epsilon$-Pareto Set, we
relax the stopping condition: instead of stopping when it remains only one active arm (i.e., $|A_r| \le 1$), we stop when ($|A_r| \le 1$ or $\varepsilon_r \le \varepsilon/4$) holds. After stopping, the same set is recommended, namely $A_\tau \cup B_\tau$. The guarantees of GEGE under this modification are discussed in Section E.5.

# 4 UNFIED ANALYSIS OF GEGE

Before sketching our proof strategy, we highlight a key property of PSI that makes the analysis different from classical BAI settings. Let $a$ be a (Pareto) sub-optimal arm. From (1), there exits $a^* \in S^*$ such that $\Delta_a = m(a, a^*)$ and importantly, $a^*$ could be the unique arm dominating $a$. Therefore, discarding $a^*$ before $a$ may result in the latter appearing as optimal in the remaining rounds, thus leading to the misidentification of the Pareto set.

To avoid this, an elimination algorithm for PSI should guarantee that if a sub-optimal arm $a$ is active, then $a^*$ is also active. We introduce the following event

$$ \mathcal{P}_r := \{ \forall s \le r : \forall i \in (S^*)^c, i \in A_s \Rightarrow i^* \in A_r \}. $$

An important aspect of our proofs is to control the occurrence of $\mathcal{P}_\infty$ (by convention, if $\mathcal{P}_t$ holds and $A_s = \emptyset$ for any $s \ge t$, then $\mathcal{P}_\infty$ holds). The first step of the proof is to show that when $\mathcal{P}_r$ holds, we can control the deviations of the empirical gaps, which is essential to guarantee the correctness of GEGE and to control its sample complexity in fixed-confidence. We now define for $\eta > 0$, the good event

$$ \mathcal{E}^r(\eta) = \{ \forall i, j \in A_r : \|(\hat{\Theta}_r - \Theta)^\intercal(x_i - x_j)\|_{\infty} \le \eta \}. \quad (6) $$

Letting $n_r = |A_r|$ and $\lambda$ a constant to be specified, we introduce $\mathcal{E}_{\text{fb}}^\lambda := \cap_{r=1}^{\lfloor \log_2(h) \rfloor} \mathcal{E}^r(\lambda \Delta_{n_{r+1}+1})$ and $\mathcal{E}_{\text{fc}} := \cap_{r=1}^\infty \mathcal{E}^r(\varepsilon_r/2)$. We then prove by concentration and induction the following key result.

**Proposition 1.** Let $\lambda \in (0, 1/5)$ and assume $\mathcal{E}_{\text{fc}}$ (resp. $\mathcal{E}_{\text{fb}}^\lambda$ in fixed-budget) holds. Then at any round $r$, $\mathcal{P}_r$ holds and for all arm $i \in A_r$,

$$ \hat{\Delta}_{i,r} - \Delta_i \ge \begin{cases} -\eta_r & \text{if } i \in S^* \\ -\eta_r/2 & \text{else,} \end{cases} \quad \text{where} $$

$$ \eta_r := \begin{cases} 2\lambda\Delta_{n_{r+1}+1} & (\text{fixed-budget}) \\ \varepsilon_r & (\text{fixed-confidence}). \end{cases} $$

Building on this result, we show that the recommendation of Algorithm 2 is correct on $\mathcal{E}_{\text{fb}}^\lambda$, so its probability of error is upper-bounded by $\inf_{\lambda \in (0,1/5)} \mathbb{P}(\mathcal{E}_{\text{fb}}^\lambda)$. We conclude the proof of Theorem 1 by upper bounding this probability (see Appendix D).

Similarly, using Proposition 1 we prove the correctness of Algorithm 3 on $\mathcal{E}_{\text{fc}}$: at any round $r$, $B_r \subset S^*$ and $D_r \subset (S^*)^c$.

To further upper bound its sample complexity, we need an additional result to control the size of $A_r$.

**Lemma 3.** The following statement holds for Algorithm 3 on the event $\mathcal{E}_{\text{fc}}$: for all $p \in [K]$, after $\lfloor \log(1/\Delta_p) \rfloor$ rounds it remains less than $p$ active arms. In particular, GEGE stops after at most $\lfloor \log(1/\Delta_1) \rfloor$ rounds.

The proof of this lemma is given in Appendix E.2. To get the sample complexity bound of Theorem 3, some extra arguments are needed. We sketch some elements below (the full proof is given in Appendix E.3). Assume $\mathcal{E}_{\text{fc}}$ holds and let $\tau_\delta$ be the sample complexity of Algorithm 3. Lemma 3 yields $\tau_\delta \le \sum_{r=1}^{\lfloor \log(1/\Delta_1) \rfloor} \Omega(h_r/\varepsilon_r^2)$ with $h_r \le |A_r|$.

Using Lemma 3, we introduce "checkpoints rounds" between which we control $|A_r|$ and thus $h_r$. Let the sequence $(\alpha_s)_{s \ge 0}$ defined as $\alpha_0 = 0$ and $\alpha_s = \lfloor \log_2(1/\Delta_{\lfloor h/2^s \rfloor}) \rfloor$, for $s \ge 1$. Simple calculation yields $\alpha_{\lfloor \log_2(h) \rfloor} = \lfloor \log_2(1/\Delta_1) \rfloor$ and $\{1, \dots, \lfloor \log_2(1/\Delta_1) \rfloor\} = \cup_{s=1}^{\lfloor \log_2(h) \rfloor} [1 + \alpha_{s-1}, \alpha_s]$. Therefore

$$ \tau_\delta \le \sum_{s=1}^{\lfloor \log_2(h) \rfloor} \sum_{r=\alpha_{s-1}+1}^{\alpha_s} \Omega(|A_r|/\varepsilon_r^2). $$

Now by Lemma 3, for $r > \alpha_s$, $|A_r| \le \lfloor h/2^s \rfloor$, so essentially $\tau_\delta \le \sum_{s=1}^{\lfloor \log_2(h) \rfloor} \Omega(4^{\alpha_s} \lfloor h/2^s \rfloor)$.

Carefully re-indexing this sum and addressing a few more technicalities, we obtain the result in Theorem 3. Showing that $\mathbb{P}(\mathcal{E}_{\text{fc}}) \ge 1 - \delta$, from Lemma 2 completes the proof.

# 5 EXPERIMENTS

We evaluate GEGE in real-world and synthetic instances. In the fixed-budget setting, we compare against EGE-SH and EGE-SR (Kone et al., 2024), two algorithms for unstructured PSI in the fixed-budget setting, and a uniform sampling baseline.

In the fixed-confidence setting, we compare to APE (Kone et al., 2023), a fully adaptive algorithm for unstructured PSI, and PAL (Zuluaga et al., 2013), an algorithm that uses Gaussian process modeling for PSI, instantiated with a linear kernel.

## 5.1 Experimental protocol

We describe below the datasets in our experiments, and we detail our experimental setup.
**Synthetic instances** We fix features $x_1, \dots, x_h$ and $\Theta$ common to the instances described below. For any $K \ge h$ we define a linear PSI instance $\nu_K$ augmented with arms $x_{h+1}, \dots, x_K$ chosen so that arms $1, \dots, h$ have the same lowest gaps in $\nu_K$. This implies that the complexity terms $H_{1,\text{lin}}$ and $H_{2,\text{lin}}$ are constant for such instances, irrespective of the number of arms. We set $h = 8, d = 2$.

**Real-world dataset** NoC (Almer et al., 2011) is a bi-objective optimization dataset for hardware design. The goal is to optimize $d = 2$ performance criteria: energy consumption and runtime of the implementation of a Network on Chip (NoC). The dataset contains $K = 259$ implementations, each of them described by $h = 4$ features.

In each instance, we report, for different algorithms, the empirical error probability (fixed-budget) and the empirical distribution of the sample complexity (fixed-confidence) averaged over 500 seeded runs. We set $\delta = 0.01$ for the fixed-confidence experiments and $T = H_{2,\text{lin}}$ for fixed-budget.

<figure><img src="image_3.png" /><figcaption>**Figure 1:** Average misidentification rate w.r.t $K$ on the synthetic dataset</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Figure 2:** Average sample complexity w.r.t $K$ in the synthetic experiment</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Figure 3:** Average misidentification rate w.r.t $T$ on NoC experiment</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Figure 4:** Empirical sample complexity in the NoC experiment</figcaption></figure>

## 5.2 Summary of the results

By Theorem 1 and 3, on the synthetic instance with $K$ arms, the sample complexity of GEGE should be a constant plus a $\log(K)$ term. This is coherent with what we observe: Fig. 1 shows that the probability of error of GEGE merely increases with $K$, whereas for EGE-SH/SR, it grows much faster. Similarly, on Fig. 2,

the sample complexity of GEGE does not significantly increase with $K$, unlike that of APE. Therefore, GEGE only suffers a small cost for the number of arms.

For the real-world scenario, GEGE significantly outperforms its competitors in both settings. Fig. 4 shows that it uses significantly fewer samples to identify the Pareto set compared to both APE and PAL. Fig. 3 shows that the probability of misidentification of GEGE is reduced by up to 0.5 compared to EGE-SH. Moreover, it is worth noting that EGE-SH requires $T \ge K \log_2(K) \approx 2000$ (for NoC) to run on this instance while GEGE only needs $T \ge \log_2(h)$.

We reported runtimes around 10 seconds for single runs on instances with up to $K = 500, d = 8$ (cf Table 2 in Appendix I.1). The time and memory complexity is addressed in Appendix I.1, and additional details about the implementation are provided. Appendix I.2 contains additional experimental results on a real-world multi-criteria optimization problem with $K = 768$ arms.

# 6 CONCLUSION AND FINAL REMARKS

We have proposed the first algorithms for PSI in a multi-output linear bandit model that are guaranteed to outperform their unstructured counterparts. They leverage optimal design approaches to estimate the means vector and some sub-optimality gaps for PSI. In the fixed-budget setting, GEGE is the first algorithm with nearly optimal guarantees for linear PSI. In the fixed-confidence setting, GEGE provably outperforms its competitors both in theory and in our experiments. It is also the first fixed-confidence PSI algorithm using a limited number of batches.

While the sample complexity of GEGE features a complexity term depending only on $h$ gaps, we still have $\log(K)$ terms due to union bounds. Katz-Samuels et al. (2020) showed that such union bounds can be avoided in linear BAI by using results from supremum of empirical processes. Further work could investigate if these observations would apply in linear PSI. In the alternative situation where $h \gg K$, for example, in an RKHS, following the work of Camilleri et al. (2021), we could investigate how to extend this optimal design approach to PSI with high-dimensional features.

## Acknowledgements

Cyrille Kone is funded by an Inria/Inserm PhD grant. This work has been partially supported by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project (ANR-23-PEIA-0003).
References

A. Alieva, A. Cutkosky, and A. Das. Robust pure exploration in linear bandits with limited budget. In *Proceedings of the 38th International Conference on Machine Learning*, Proceedings of Machine Learning Research. PMLR, 2021.

Z. Allen-Zhu, Y. Li, A. Singh, and Y. Wang. Near-optimal design of experiments via regret minimization. In *Proceedings of the 34th International Conference on Machine Learning*. JMLR.org, 2017.

O. Almer, N. Topham, and B. Franke. A learning-based approach to the automated design of MPSOCs for artificial intelligence networks. 2011.

J.-Y. Audibert and S. Bubeck. Best arm identification in multi-armed bandits. In *COLT - 23rd Conference on Learning Theory*, 2010.

P. Auer, C.-K. Chiang, R. Ortner, and M.-M. Drugan. Pareto front identification from stochastic bandit feedback. In *Proceedings of the 19th International Conference on Artificial Intelligence and Statistics*. PMLR, 2016.

M. Azizi, B. Kveton, and M. Ghavamzadeh. Fixed-budget best-arm identification in structured bandits. In *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*. International Joint Conferences on Artificial Intelligence Organization, 2022.

S. Bubeck and G. Munos, R. and Stoltz. Pure exploration for multi-armed bandit problems, 2008.

R. Camilleri, K. Jamieson, and J. Katz-Samuels. High-dimensional experimental design and kernel bandits. In *Proceedings of the 38th International Conference on Machine Learning*, Proceedings of Machine Learning Research. PMLR, 2021.

A. Carpentier and A. Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In *29th Annual Conference on Learning Theory*, Proceedings of Machine Learning Research. PMLR, 2016.

S. Chen, T. Lin, I. King, M. R. Lyu, and W. Chen. Combinatorial pure exploration of multi-armed bandits. In *Advances in Neural Information Processing Systems*. Curran Associates, Inc., 2014.

R. Degenne, P. Ménard, X. Shang, and M. Valko. Gamification of pure exploration for linear bandits. In *International Conference on Machine Learning (ICML)*, 2020.

M.-M. Drugan and A. Nowe. Designing multi-objective multi-armed bandits algorithms: A study. In *The 2013 International Joint Conference on Neural Networks (IJCNN)*, 2013.

F. Z. Faizal and J. Nair. Constrained pure exploration multi-armed bandits with a fixed budget, 2022.

T. Fiez, L. Jain, K. G. Jamieson, and L. Ratliff. Sequential experimental design for transductive linear bandits. In *Advances in Neural Information Processing Systems*. Curran Associates, Inc., 2019.

A. Garivier and E. Kaufmann. Optimal best arm identification with fixed confidence. In *29th Annual Conference on Learning Theory*. PMLR, 2016.

K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. lil' ucb: An optimal exploration algorithm for multi-armed bandits. In *Proceedings of The 27th Conference on Learning Theory*. PMLR, 2014.

Y. Jedra and A. Proutiere. Optimal best-arm identification in linear bandits. In *Advances in Neural Information Processing Systems*. Curran Associates, Inc., 2020.

S. Kalyanakrishnan, A. Tewari, P. Auer, and P. Stone. PAC subset selection in stochastic multi-armed bandits. In *Proceedings of the 29th International Conference on International Conference on Machine Learning*. Omnipress, 2012.

Z. Karnin, T. Koren, and O. Somekh. Almost optimal exploration in multi-armed bandits. In *Proceedings of the 30th International Conference on International Conference on Machine Learning*. JMLR, 2013.

J. Katz-Samuels and C. Scott. Feasible arm identification. In *Proceedings of the 35th International Conference on Machine Learning*. PMLR, 2018.

J. Katz-Samuels and C. Scott. Top feasible arm identification. In *Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics*. PMLR, 2019.

J. Katz-Samuels, L. Jain, z. karnin, and K. G. Jamieson. An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits. In *Advances in Neural Information Processing Systems*. Curran Associates, Inc., 2020.

E. Kaufmann, O. Cappé, and A. Garivier. On the complexity of best-arm identification in multi-armed bandit models. *Journal of Machine Learning Research*, 2016.

J. Kiefer and J. Wolfowitz. The equivalence of two extremum problems. *Canadian Journal of Mathematics*, 1960.

W. Kim, G. Iyengar, and A. Zeevi. Pareto front identification with regret minimization, 2023.

C. Kone, E. Kaufmann, and L. Richert. Adaptive algorithms for relaxed pareto set identification. In
*Thirty-seventh Conference on Neural Information Processing Systems*, 2023.

C. Kone, E. Kaufmann, and L. Richert. Bandit Pareto set identification: the fixed budget setting. In *Proceedings of The 27th International Conference on Artificial Intelligence and Statistics*, Proceedings of Machine Learning Research. PMLR, 2024.

T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.

A. Locatelli, M. Gutzeit, and A. Carpentier. An optimal algorithm for the thresholding bandit problem. In *Proceedings of The 33rd International Conference on Machine Learning*, Proceedings of Machine Learning Research. PMLR, 2016.

S. Lu, G. Wang, Y. Hu, and L. Zhang. Multi-objective generalized linear bandits. In *Proceedings of the 28th International Joint Conference on Artificial Intelligence*. AAAI Press, 2019.

F. Pukelsheim. *Optimal Design of Experiments (Classics in Applied Mathematics) (Classics in Applied Mathematics, 50)*. Society for Industrial and Applied Mathematics, 2006.

M. Soare, A. Lazaric, and R. Munos. Best-arm identification in linear bandits. In *Advances in Neural Information Processing Systems*. Curran Associates, Inc., 2014.

C. Tao, S. Blanco, and Y. Zhou. Best arm identification in linear bandits with linear dimension dependency. In *Proceedings of the 35th International Conference on Machine Learning*, Proceedings of Machine Learning Research. PMLR, 2018.

A. Tsanas and A. Xifara. Energy efficiency. UCI Machine Learning Repository, 2012.

L. Xu, J. Honda, and M. Sugiyama. A fully adaptive algorithm for pure exploration in linear bandits. In *Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics*. PMLR, 2018.

J. Yang and V. Tan. Minimax optimal fixed-budget best arm identification in linear bandits. In *Advances in Neural Information Processing Systems*. Curran Associates, Inc., 2022.

W. You, C. Qin, Z. Wang, and S. Yang. Information-directed selection for top-two algorithms. In *Proceedings of Thirty Sixth Conference on Learning Theory*, Proceedings of Machine Learning Research. PMLR, 2023.

M. Zuluaga, G. Sergent, A. Krause, and M. Püschel. Active learning for multi-objective optimization. In *Proceedings of the 30th International Conference on Machine Learning*. PMLR, 2013.

M. Zuluaga, A. Krause, and M. Püschel. e-pal: An active learning approach to the multi-objective optimization problem. *Journal of Machine Learning Research*, 2016.

Checklist

1. For all models and algorithms presented, check if you include:

(a) A clear description of the mathematical setting, assumptions, algorithm, and/or model. **Yes, see section 2, section 4 and Appendix B to H**

(b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. **Yes, see section 4, section I.1**

(c) (Optional) Anonymized source code, with specification of all dependencies, including external libraries. **Yes, see additional material**

2. For any theoretical claim, check if you include:

(a) Statements of the full set of assumptions of all theoretical results. **Yes, see section 4, section 3 and section 2,**

(b) Complete proofs of all theoretical results. **Yes, see section 4 and the proofs in Appendix B to H**

(c) Clear explanations of any assumptions. **Yes, see section 4 and section 2**

3. For all figures and tables that present empirical results, check if you include:

(a) The code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL). **Yes, see section 5 and section I.2, I.1,**

(b) All the training details (e.g., data splits, hyperparameters, how they were chosen). **Yes, see section 5 and section I.2, I.1,**

(c) A clear definition of the specific measure or statistics and error bars (e.g., with respect to the random seed after running experiments multiple times). **Yes, see section 5**

(d) A description of the computing infrastructure used. (e.g., type of GPUs, internal cluster, or cloud provider). **Yes, see section I.1,**

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include:
(a) Citations of the creator If your work uses existing assets. **Yes, see section 5 and section I.1**

(b) The license information of the assets, if applicable. **Not Applicable**

(c) New assets either in the supplemental material or as a URL, if applicable. **Not Applicable**

(d) Information about consent from data providers/curators. **Not Applicable**

(e) Discussion of sensible content if applicable, e.g., personally identifiable information or offensive content. **Not Applicable**

5. If you used crowdsourcing or conducted research with human subjects, check if you include:

(a) The full text of instructions given to participants and screenshots. **Not Applicable**

(b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. **Not Applicable**

(c) The estimated hourly wage paid to participants and the total amount spent on participant compensation. **Not Applicable**
# A OUTLINE

In section C, we prove Proposition 1, which is a crucial result to prove the guarantees of GEGE in both fixed-confidence and fixed-budget settings. Section D proves the fixed-budget guarantees of GEGE, in particular Theorem 1. In section E we prove the fixed-confidence guarantees of GEGE by proving Theorem 3. Section F contains some ingredient concentration lemmas that are used in our proofs. In section G, we analyze the lower bounds in both fixed-confidence and fixed-budget settings. In section H, we analyze the properties of Algorithm 1 by using some results on G-optimal design. Finally, section I contains additional experimental results and the detailed experimental setup.

# B NOTATION

We introduce some additional notation used in the following sections.

In the subsequent sections, $r$ will always denote a round of GEGE, which should be clear from the context. We then denote by $A_r$ active arms at round $r$ and by $\hat{\Theta}_r$ the empirical estimate of $\Theta$ at round $r$, computed by a call to Algorithm 1. By convention we let $\max_{\emptyset} = -\infty$.

For any sub-optimal arm $i$, there exists a Pareto-optimal arm $i^*$ (not necessarily unique) such that $\Delta_i = m(i, i^*)$. More generally given a sub-optimal $i$ we denote by $i^*$ any arm of $\text{argmax}_{j \in S^*} m(i, j)$.

At a round $r$, we let

$$ \mathcal{P}_r := \{\forall s \in \{1, \dots, r\}, \forall i \in A_s, i \in (S^*)^c \cap A_s \Rightarrow i^* \in A_s\}, \quad (7) $$

with $\mathcal{P} = \mathcal{P}_\infty$. In particular, for a sub-optimal arm $i$, $i^* \in A_s$ should be understood as $A_s \cap (\text{argmax}_{j \in S^*} m(i, j)) \neq \emptyset$. If for some $\tau$, $\mathcal{P}_\tau$ is true and $A_{\tau+1} = \emptyset$ then we say that $\mathcal{P}$ holds.

# C PROOF OF PROPOSITION 1

We first recall the result.

**Proposition 1.** Let $\lambda \in (0, 1/5)$ and assume $\mathcal{E}_{\text{fc}}$ (resp. $\mathcal{E}_{\text{fb}}^\lambda$ in fixed-budget) holds. Then at any round $r$, $\mathcal{P}_r$ holds and for all arm $i \in A_r$,

$$ \hat{\Delta}_{i,r} - \Delta_i \ge \begin{cases} -\eta_r & \text{if } i \in S^* \\ -\eta_r/2 & \text{else,} \end{cases} \quad \text{where} $$

$$ \eta_r := \begin{cases} 2\lambda\Delta_{n_{r+1}+1} & (\text{fixed-budget}) \\ \varepsilon_r & (\text{fixed-confidence}). \end{cases} $$

In both the fixed-budget and fixed-confidence setting, the proof proceeds by induction on the round $r$. Before presenting the inductive argument separately in each case, we establish in Appendix C.1 an important result that is used in both cases (Lemma 7): if $\mathcal{P}_r$ holds at some round $r$ then, the empirical gaps computed at this round are good estimators of the true PSI gaps.

To establish this first result, we need the following intermediate lemmas, proved in Appendix F.

**Lemma 4.** At any round $r$ and for any arms $i, j \in A_r$ it holds that

$$ |M(i, j; r) - M(i, j)| \le \|(\hat{\Theta}_r - \Theta)^\top(x_i - x_j)\|_{\infty} \text{ and} $$

$$ |m(i, j; r) - m(i, j)| \le \|(\hat{\Theta}_r - \Theta)^\top(x_i - x_j)\|_{\infty}. $$

**Lemma 5.** At any round $r$, for any sub-optimal arm $i \in A_r$, if $i^* \in A_r$ and $i^*$ does not empirically dominate $i$ then $\Delta_i^* < \|(\hat{\Theta}_r - \Theta)^\top(x_i - x_{i^*})\|_{\infty}$.

## C.1 Deviations of the gaps when $\mathcal{P}_r$ holds

In this part, we control the deviations of the empirical gaps when proposition $\mathcal{P}_r$ holds.
**Lemma 6.** Assume that the proposition $\mathcal{P}_r$ holds at some round $r$. Then for any arm $i \in A_r$ it holds that

$$|(\hat{\Delta}_{i,r}^*)_+ - (\Delta_i^*)_+| \le |\hat{\Delta}_{i,r}^* - \Delta_i^*| \le \gamma_{i,r}$$

where $\gamma_{i,r} := \max_{j \in A_r} \|(\hat{\Theta}_r - \Theta)^T (x_i - x_j)\|_{\infty}$.

*Proof.* This inequality is a direct consequence of Lemma 4 and the relation $|x_+ - y_+| \le |x - y|$ which holds for any $x, y \in \mathbb{R}$. Note that for a Pareto-optimal arm $i$ we trivially have $(\Delta_i^*)^+ = 0 = (\max_{j \in A_r} m(i, j))_+$. And for a sub-optimal arm $i \in A_r$, as $i^* \in A_r$ (from proposition $\mathcal{P}_r$) we have $\Delta_i^* = m(i, i^*) = \max_{j \in A_r} m(i, j)$. Thus for any arm $i \in A_r$ we have

$$\begin{aligned} |(\hat{\Delta}_{i,r}^*)_+ - (\Delta_i^*)_+| &= |(\max_{j \in A_r} m(i, j; r))_+ - (\max_{j \in A_r} m(i, j))_+|, \\ &\le |(\max_{j \in A_r} m(i, j; r)) - (\max_{j \in A_r} m(i, j))|, \\ &\le \max_{j \in A_r} |m(i, j; r) - m(i, j)|, \\ &\le \max_{j \in A_r} \|(\hat{\Theta}_r - \Theta)^T (x_i - x_j)\|_{\infty} = \gamma_{i,r}, \end{aligned}$$

where the last inequality follows from Lemma 4. $\square$

**Lemma 7.** If the proposition $\mathcal{P}_r$ holds at some round $r$ then for any arm $i \in A_r$,

$$\hat{\Delta}_{i,r} - \Delta_i \ge \begin{cases} -2\gamma_r & \text{if } i \in S^*, \\ -\gamma_{i,r} & \text{else,} \end{cases}$$

where $\gamma_{i,r} := \max_{j \in A_r} \|(\hat{\Theta}_r - \Theta)^T (x_i - x_j)\|_{\infty}$ and $\gamma_r := \max_{i \in A_r} \gamma_{i,r}$.

*Proof.* We first prove the result a sub-optimal arm $i$. From the proposition $\mathcal{P}_r$, as $i \in A_r$ we have $i^* \in A_r$ so $\Delta_i = \max_{j \in A_r} m(i, j)$ and we recall that

$$\hat{\Delta}_{i,r} := \max(\hat{\Delta}_{i,r}^*, \hat{\delta}_{i,r}^*). \qquad (8)$$

Note that by reverse triangle we have for any arm $i \in A_r$ (sub-optimal or not)

$$\left| \left( \max_{j \in A_r} m(i, j; r) \right) - \left( \max_{j \in A_r} m(i, j) \right) \right| \le \max_{j \in A_r} |m(i, j; r) - m(i, j)|, \qquad (9)$$

$$\le \max_{j \in A_r} \|(\hat{\Theta}_r - \Theta)^T (x_i - x_j)\|_{\infty} = \gamma_{i,r}. \qquad (10)$$

where the last inequality follows from Lemma 4. If $i$ is a sub-optimal arm ($i \notin S^*$) then as $\Delta_i = \Delta_i^*$, it follows

$$\hat{\Delta}_{i,r} - \Delta_i \ge \hat{\Delta}_{i,r}^* - \Delta_i^*$$

therefore

$$\begin{aligned} \hat{\Delta}_{i,r} - \Delta_i &\ge -|\hat{\Delta}_{i,r}^* - \Delta_i^*| \\ &= -|(\max_{j \in A_r} m(i, j; r)) - (\max_{j \in A_r} m(i, j))| \\ &\ge -\gamma_{i,r} \quad (\text{see (10)}). \end{aligned}$$

Now we assume $i$ is a Pareto-optimal arm ($i \in S^*$) so that

$$\Delta_i = \delta_i^*.$$

Combining with Eq. (8) yields

$$\hat{\Delta}_{i,r} - \Delta_{i,r} \ge \hat{\delta}_{i,r}^* - \delta_{i,r}^*.$$
where we recall that

$$ \hat{\delta}_{i,r}^{*} = \min_{j \in A_r \setminus \{i\}} [M(i, j; r) \wedge (M(j, i; r)_+ + (\hat{\Delta}_{j,r})_+)] $$

and

$$ \delta_i^* := \min_{j \in [K] \setminus \{i\}} [M(i, j) \wedge (M(j, i)_+ + (\Delta_j^*)_+)]. $$

As for any $x, y \in \mathbb{R}$ we have $|x^+ - y^+| \le |x - y|$, the following holds for any $i, j \in A_r$

$$ |M(j, i; r)^+ - M(j, i)^+| \le |M(j, i; r) - M(j, i)| \quad (11) $$

$$ \le \gamma_{j,r}. \quad (12) $$

From Lemma 6 we have for any $j \in A_r$

$$ (\hat{\Delta}_{j,r}^*)_+ - (\Delta_j^*)_+ \ge -\gamma_{j,r}. \quad (13) $$

Combining (12) and (13) yields for any $j \in A_r$

$$ M(j, i; r)_+ + (\hat{\Delta}_{j,r}^*)_+ \ge M(j, i)_+ + (\Delta_j^*)_+ - 2\gamma_{j,r}, \quad (14) $$

which in addition to $M(j, i; r) \ge M(j, i) - \gamma_{j,r}$ yields

$$ [M(i, j; r) \wedge (M(j, i; r)_+ + (\hat{\Delta}_{j,r}^*)_+)] \ge [M(i, j) \wedge (M(j, i)_+ + (\Delta_j^*)_+)] - 2\gamma_{j,r} $$

for any arm $j \in A_r$. Thus taking the min over $i \in A_r$ yields

$$ \begin{aligned} \hat{\delta}_{i,r}^* &= \min_{j \in A_r \setminus \{i\}} [M(i, j; r) \wedge (M(j, i; r)_+ + (\hat{\Delta}_{j,r}^*)_+)] \\ &\ge \min_{j \in A_r \setminus \{i\}} [M(i, j) \wedge (M(j, i)_+ + (\Delta_j^*)_+)] - 2\gamma_r, \\ &\ge \min_{j \in [K] \setminus \{i\}} [M(i, j) \wedge (M(j, i)_+ + (\Delta_j^*)_+)] - 2\gamma_r, \\ &= \delta_i^* - 2\gamma_r \end{aligned} $$

which concludes the proof of this lemma.

Building on this result, we show that $\mathcal{P}_\infty$ holds in the fixed-confidence and fixed-budget settings.

## C.2 Fixed-budget setting

We recall the definition of the good event for any $\lambda > 0$.

$$ \mathcal{E}_{\text{fb}}^{r,\lambda} = \left\{ \forall i, j \in A_r : \| (\hat{\Theta}_r - \Theta)^{\top} (x_i - x_j) \|_{\infty} \le \lambda \Delta_{n_{r+1}+1} \right\} $$

and $\mathcal{E}_{\text{fb}}^{\lambda} := \cap_{r=1}^{\lfloor \log_2(h) \rfloor} \mathcal{E}_{\text{fb}}^{r,\lambda}$. We prove that proposition $\mathcal{P}_\infty$ holds on the event $\mathcal{E}_{\text{fb}}^{\lambda}$ for some any $\lambda \in (0, 1/5)$.

**Lemma 8.** The proposition holds $\mathcal{P}_\infty$ on the event $\mathcal{E}_{\text{fb}}^{\lambda}$ for any $\lambda \in (0, 1/5)$: at any round $r \in \{1, \dots, \lfloor \log_2 h \rfloor + 1\}$ and for any arm $i \in A_r \cap (S^*)^c$, $i^* \in A_r$.

*Proof.* We prove $\mathcal{P}_\infty$ by induction on the round $r$. In the sequel we assume $\mathcal{E}_{\text{fb}}^{\lambda}$ holds. We also assume $\mathcal{P}_r$ is true until some round $r$. As $\mathcal{E}_{\text{fb}}^{\lambda}$ holds, we have by application of Lemma 7: for any arm $i \in A_r$,

$$ \hat{\Delta}_{i,r} - \Delta_i \ge \begin{cases} -2\lambda\Delta_{n_{r+1}+1} & \text{if } i \in S^* \\ -\lambda\Delta_{n_{r+1}+1} & \text{else.} \end{cases} \quad (15) $$

We shall prove that if a Pareto-optimal arm $i$ is discarded at the end of round $r$ then there exists no arm sub-optimal $j \in A_{r+1}$ such that $j^* = i$. Since $i$ is removed and $|A_{r+1}| = n_{r+1}$ there exists $k_r \in A_{r+1} \cup \{i\}$ such that

$$ \Delta_{k_r} \ge \Delta_{n_{r+1}+1}. \quad (16) $$
If $i$ is empirically sub-optimal then as it is discarded we have

$$ \hat{\Delta}_{i,r} = \hat{\Delta}_{i,r}^{*} \geq \hat{\Delta}_{k,r} $$

for any arm $k \in A_{r+1}$. So $\hat{\Delta}_{i,r}^{*} \geq \hat{\Delta}_{k,r}$ thus using (15) and (16) it comes that

$$ \begin{aligned} \max_{q \in A_r \setminus \{i\}} m(i, q) &\geq \Delta_{n_{r+1}+1} - 3\lambda\Delta_{n_{r+1}+1} \\ &= (1 - 3\lambda)\Delta_{n_{r+1}+1} \end{aligned} $$

and the latter inequality is not possible for $\lambda < 1/3$ as the LHS of the inequality is negative as $i$ is a Pareto-optimal arm.

Next we assume that $i$ is empirically optimal. We claim that $j$ is not dominated by $i$. To see this, first note that as $j \in A_{r+1}$ we have

$$ \hat{\Delta}_{i,r} \geq \hat{\Delta}_{j,r} \qquad (17) $$

so that as $i$ is empirically optimal, if $j$ was empirically dominated by $i$ we would have

$$ \hat{\Delta}_{i,r} \leq M(j, i; r)_+ + (\hat{\Delta}_{j,r})_+ = \hat{\Delta}_{j,r}. \qquad (18) $$

Combining (17) and (18) yield $\hat{\Delta}_{i,r} = \hat{\Delta}_{j,r}$, $i$ is empirically optimal and $j$ is empirically sub-optimal. However our breaking rule ensures that this case cannot occur. Therefore $j$ is not dominated by $i$. But, by assumption, $j$ is such that $j^* = i$ and we have proved that $i$ does not empirically dominate $j$ so by Lemma 5

$$ \Delta_j \leq \|(\hat{\Theta}_r - \Theta)^{\top}(x_j - x_i)\|_{\infty} $$

which on the event $\mathcal{E}_{\text{fb}}$ yields

$$ \Delta_j \leq \lambda \Delta_{n_{r+1}+1}. \qquad (19) $$

On the other side, as $i$ is discarded as an empirically optimal arm we have

$$ \hat{\Delta}_{i,r} = \hat{\delta}_{i,r}^{*} \geq \hat{\Delta}_{k,r} $$

for any arm $k \in A_{r+1}$. Since $k_r \in A_{r+1} \cup \{i\}$ it comes $\hat{\delta}_{i,r}^{*} \geq \hat{\Delta}_{k,r}$ thus using (15) and (16) yields

$$ M(j, i)_+ + \Delta_j \geq \Delta_{n_{r+1}+1} - 4\lambda\Delta_{n_{r+1}+1} $$

which further combined with (19) yields

$$ M(j, i)_+ \geq (1 - 5\lambda)\Delta_{n_{r+1}+1}. $$

However, as $j^* = i$ we have $M(j, i)_+ = 0$ so the latter inequality is not possible as long as $\lambda < 1/5$. Put together, we have proved that if $\mathcal{P}_r$ holds then for any Pareto-optimal arm $i$ which is removed at the end of round $r$, there does not exist an arm $j \in A_{r+1}$ such that $j^* = i$. So $\mathcal{P}_{r+1}$ holds. Finally noting that $\mathcal{P}_r$ trivially holds for $r = 1$ we conclude that $\mathcal{P}_{\infty}$ holds on the event $\mathcal{E}_{\text{fb}}^{\lambda}$ for any $\lambda < 1/5$. $\square$

Combining this result with Lemma 7 and assuming $\mathcal{E}_{\text{fb}}^{\lambda}$ holds then yields at any round $r \in \{1, \dots, \lceil \log_2 h \rceil\}$ and for any arm $i \in A_r$:

$$ \hat{\Delta}_{i,r} - \Delta_i \geq \begin{cases} -2\lambda\Delta_{n_{r+1}+1} & \text{if } i \in S^* \\ -\lambda\Delta_{n_{r+1}+1} & \text{else,} \end{cases} \qquad (20) $$

which proves Proposition 1 in the fixed-budget setting.
### C.3 Fixed-confidence setting

We recall below the good events we study in the fixed-confidence setting:

$$ \mathcal{E}_{\text{fc}}^{r} = \left\{ \forall i, j \in A_r : \|(\hat{\Theta}_r - \Theta)^{\top}(x_i - x_j)\|_{\infty} \le \varepsilon_r/2 \right\} $$

and $\mathcal{E}_{\text{fc}} := \cap_{r=1}^{\infty} \mathcal{E}_{\text{fc}}^r$.

**Lemma 9.** The proposition $\mathcal{P}_{\infty}$ holds on the event $\mathcal{E}_{\text{fc}}$: at any round $r$ for any arm $i \in A_r \cap (S^*)^c$, $i^* \in A_r$.

*Proof of Lemma 9.* We prove the proposition by induction on the round $r$. Note that the proposition $\mathcal{P}_r$ trivially holds for $r=1$. Assume the property holds until the beginning of some round $r$. Let $i \in S^*$ be an optimal arm and assume $i$ is discarded at the end of round $r$. We will prove that there exists no sub-optimal arm $j \in A_{r+1}$ such that $j^* = i$. Recall that when $i$ is discarded, we have either $i \in S_r$ (empirically optimal) or $i \notin S_r$ (empirically sub-optimal). We analyze both cases below. If $i \notin S_r$ then it holds that

$$ \hat{\Delta}_{i,r} \ge \varepsilon_r/2, $$

then, as $i \notin S_r$ it follows that $\hat{\Delta}_{i,r} = \hat{\Delta}_i^* := \max_{j \in A_r \setminus \{i\}} m(i, j; r)$, so

$$ \max_{j \in A_r \setminus \{i\}} m(i, j; r) \ge \varepsilon_r/2 $$

which using Lemma 4 and assuming event $\mathcal{E}_{\text{fc}}^r$ holds would yield

$$ \max_{j \in A_r \setminus \{i\}} m(i, j) > 0. $$

The latter inequality is not possible as $i \in S^*$ is a Pareto-optimal arm. Therefore, on $\mathcal{E}_{\text{fc}}^r$, when $i \in S^*$ is discarded we have $i \in S_r$.

Next, we analyze the case $i \in S_r$: that is $i$ is discarded and classified as optimal. In this case it follows from the definition of $\hat{\Delta}_{i,r}$ that

$$ \min_{j \in A_r \setminus \{i\}} [M(j, i; r)_+ + (\hat{\Delta}_{j,r}^*)_+] \ge \varepsilon_r. \quad (21) $$

Let $j \in A_{r+1} \cap (S^*)^c$ be such that $j^* = i$. If $j$ is empirically optimal then $(\hat{\Delta}_{j,r}^*)_+ = 0$ thus $M(j, i; r)_+ \ge \varepsilon_r$. On the contrary, if $j$ is empirically sub-optimal then because it has not been removed at the end of round $r$ it holds that

$$ \hat{\Delta}_{j,r}^* < \varepsilon_r/2, $$

which combined with (21) yields $M(j, i; r)_+ > \varepsilon_r/2$. Thus, in both cases we have $M(j, i; r)_+ > \varepsilon_r/2$ which using Lemma 4 and assuming event $\mathcal{E}_{\text{fc}}^r$ would imply that

$$ M(j, i)_+ > 0, $$

which is impossible as, by assumption $j^* = i$, so $j$ is dominated by $i$.

Put together with what precedes, on $\mathcal{E}_{\text{fc}}$, if $\mathcal{P}_r$ holds then $\mathcal{P}_{r+1}$ holds. Since the property trivially holds for $r=1$ we have proved that the property $\mathcal{P}_r$ holds at any round when $\mathcal{E}_{\text{fc}}$ holds. $\square$

Combining this result with Lemma 7 proves that, on the event $\mathcal{E}_{\text{fc}}$, for any round $r$ and for any arm $i \in A_r$

$$ \hat{\Delta}_{i,r} - \Delta_i \ge \begin{cases} -\varepsilon_r & \text{if } i \in S^* \\ -\varepsilon_r/2 & \text{else,} \end{cases} \quad (22) $$

which proves Proposition 1 in the fixed-confidence setting.
D UPPER BOUND ON THE PROBABILITY OF ERROR

In this section, we prove the theoretical guarantees of GEGE in the fixed-budget setting. We prove Theorem 1 and some ingredient lemmas.

**Theorem 1.** The probability of error of Algorithm 2 run with budget $T \ge 45h \log_2 h$ is at most

$$ \exp\left(-\frac{T}{1200\sigma^2 H_{2,\text{lin}}[\log_2 h]} + \log C(h, d, K)\right) $$

where $C(h, d, K) = 2d(K + h + \lceil \log_2 h \rceil)$.

*Proof of Theorem 1.* We first prove the correctness of GEGE on the event $\mathcal{E}_{\text{fb}}^{\lambda}$ for some $\lambda$ small enough. Let us assume $\mathcal{E}_{\text{fb}}^{\lambda}$ holds which by Proposition 1 implies that $\mathcal{P}_{\infty}$ holds and at round $r$, we have for any arm $i \in A_r$

$$ \hat{\Delta}_{i,r} - \Delta_i \ge \begin{cases} -2\lambda\Delta_{n_{r+1}+1} & \text{if } i \in S^* \\ -\lambda\Delta_{n_{r+1}+1} & \text{else.} \end{cases} \qquad (23) $$

We recall the definition of the good event for any $\lambda > 0$,

$$ \mathcal{E}_{\text{fb}}^{r, \lambda} = \left\{ \forall i, j \in A_r : \|(\hat{\Theta}_r - \Theta)^{\top}(x_i - x_j)\|_{\infty} \le \lambda \Delta_{n_{r+1}+1} \right\} $$

and $\mathcal{E}_{\text{fb}} := \cap_{r=1}^{\lceil \log_2(h) \rceil} \mathcal{E}_{\text{fb}}^{r, \lambda}$. Applying Lemma 4 on this event then yields for all arms $i, j \in A_r$,

$$ |M(i, j; r) - M(i, j)| \le \lambda \Delta_{n_{r+1}+1} \quad \text{and} \qquad (24) $$

$$ |m(i, j; r) - m(i, j)| \le \lambda \Delta_{n_{r+1}+1}. \qquad (25) $$

Let $i$ be an arm discarded at the end of round $r$. Since $i$ is discarded and $|A_{r+1}| = n_{r+1}$ there exists $k_r \in A_{r+1} \cup \{i\}$ such that

$$ \Delta_{k_r} \ge \Delta_{n_{r+1}+1}. \qquad (26) $$

If $i \notin S_r$ that is $i$ is empirically sub-optimal then

$$ \hat{\Delta}_{i,r} = \hat{\Delta}_{i,r}^{*} \ge \hat{\Delta}_{k_r,r}, $$

then, recalling that

$$ \hat{\Delta}_{i,r}^{*} := \max_{j \in A_r \setminus \{i\}} m(i, j; r) $$

and further applying (23) to $k_r$ and using (25) yields

$$ \max_{j \in A_r \setminus \{i\}} m(i, j) \ge (1 - 3\lambda) \Delta_{n_{r+1}+1} $$

which for $\lambda < 1/3$ implies that $\max_{j \in A_r} m(i, j) > 0$, that is there exists $j \in A_r$ such that $\mu_i < \mu_j$ so $i$ is a sub-optimal arm.

Next, assume $i \in S_r$ (i.e, $i$ is empirically Pareto-optimal). In this case we have $\hat{\Delta}_{i,r} = \hat{\delta}_{i,r}^{*} \ge \hat{\Delta}_{k_r,r}$. We recall that

$$ \hat{\delta}_{i,r}^{*} = \min_{j \in A_r \setminus \{i\}} [M(i, j; r) \wedge (M(j, i; r)_{+} + (\hat{\Delta}_{i,r}^{*})_{+})]. $$

Applying (23) to $k_r$ and using (24), it follows that

$$ \min_{j \in A_r \setminus \{i\}} M(i, j) \ge (1 - 3\lambda) \Delta_{n_{r+1}+1}. $$

Thus, for $\lambda < 1/3$, we have $\min_{j \in A_r \setminus \{i\}} M(i, j) > 0$. Therefore, no active arm at round $r$ dominates $i$ (based on their true means), which, together with proposition $\mathcal{P}_{\infty}$, yields that $i$ is a Pareto-optimal arm (otherwise, we would have $i^* \in A_r$ that dominates $i$).
All put together, we have proved that for any $\lambda < 1/5$ (we need $\lambda < 1/5$ for $\mathcal{P}_\infty$ to hold), Algorithm 2 does not make any error on the event $\mathcal{E}_{\text{fb}}^\lambda$. It then follows that the probability of error of GEGE is at most

$$ \inf_{\lambda \in (0,1/5)} \mathbb{P}((\mathcal{E}_{\text{fb}}^{\lambda})^c) \qquad (27) $$

Now we upper-bound Eq. (27), which will conclude the proof. Let $\lambda \in (0, 1/5)$ be fixed. We have by union bound

$$ \begin{aligned} \mathbb{P}((\mathcal{E}_{\text{fb}}^{\lambda})^c) & \le \sum_{r=1}^{\lfloor \log_2 h \rfloor} \mathbb{E} \left[ \mathbb{P} \left( (\mathcal{E}_{\text{fb}}^{r, \lambda})^c | A_r \right) \right] \\ & \le \sum_{r=1}^{\lfloor \log_2 h \rfloor} \mathbb{E} \left[ \sum_{i \in A_r} \mathbb{P} \left( \| (\hat{\Theta}_r - \Theta)^T x_i \|_{\infty} > \frac{1}{2} \lambda \Delta_{n_{r+1}+1} | A_r \right) \right] \end{aligned} $$

Note that for $i$ fixed, we can use Lemma 2 with $\kappa = 1/3$ and the conditions of this theorem are satisfied as the budget per phase is $T/\log_2(h) \ge 45h$ (recall from the theorem that GEGE is run with $T \ge 45h \log_2(h)$). Thus, applying this theorem yields

$$ \begin{aligned} \mathbb{P}((\mathcal{E}_{\text{fb}}^{\lambda})^c) & \le 2d \sum_{r=1}^{\lfloor \log_2 h \rfloor} n_r \mathbb{E} \left[ \exp \left( -\frac{\lambda^2 \Delta_{n_{r+1}+1}^2 T}{24 \sigma^2 h_r \log_2 h} \right) \right] \\ & \le 2d \sum_{r=1}^{\lfloor \log_2 h \rfloor} n_r \exp \left( -\frac{\lambda^2 T \Delta_{n_{r+1}+1}^2}{24 \sigma^2 \min(h, n_r) \lfloor \log_2 h \rfloor} \right), \quad \text{as } h_r \le \min(n_r, h). \end{aligned} $$

Then, note that

$$ \begin{aligned} \frac{\Delta_{n_{r+1}+1}^2}{\min(h, n_r)} &= \frac{\Delta_{\lfloor h/2^r \rfloor+1}^2}{\lfloor h/2^{r-1} \rfloor} \\ &= \frac{\Delta_{\lfloor h/2^r \rfloor+1}^2}{\lfloor h/2^r \rfloor + 1} \frac{\lfloor h/2^r \rfloor + 1}{\lfloor h/2^{r-1} \rfloor} \\ &\ge \frac{\Delta_{\lfloor h/2^r \rfloor+1}^2}{\lfloor h/2^r \rfloor + 1} \frac{h/2^r + 1}{h/2^{r-1} + 1} \\ &\ge \frac{\Delta_{\lfloor h/2^r \rfloor+1}^2}{\lfloor h/2^r \rfloor + 1} \frac{1}{2}. \end{aligned} $$

which follows as $(x+1)/(2x+1) = (1/2) + (1/2)/(2x+1) \ge \frac{1}{2}$ for $x \ge 0$. Therefore,

$$ \begin{aligned} \frac{\Delta_{n_{r+1}+1}^2}{\min(h, n_r)} &\ge \frac{1}{2} \frac{\Delta_{\lfloor h/2^r \rfloor+1}^2}{\lfloor h/2^r \rfloor + 1} \\ &\ge \frac{1}{2H_{2,\text{lin}}}. \end{aligned} $$

Thus,

$$ \begin{aligned} \mathbb{P}((\mathcal{E}_{\text{fb}}^{\lambda})^c) & \le 2 \exp \left( -\frac{\lambda^2 T}{48 \sigma^2 H_{2,\text{lin}} \lfloor \log_2 h \rfloor} + \log(d) \right) \sum_{r=1}^{\lfloor \log_2 h \rfloor} n_r \\ & \le 2 (K + h + \lfloor \log_2 h \rfloor) \exp \left( -\frac{\lambda^2 T}{48 \sigma^2 H_{2,\text{lin}} \lfloor \log_2 h \rfloor} + \log(d) \right) \end{aligned} $$

Finally, it follows that

$$ \inf_{\lambda \in (0,1/5)} \mathbb{P}((\mathcal{E}_{\text{fb}}^{\lambda})^c) \le 2 (K + h + \lfloor \log_2 h \rfloor) \exp \left( -\frac{T}{1200 \sigma^2 H_{2,\text{lin}} \lfloor \log_2 h \rfloor} + \log(d) \right), $$

which concludes the proof.

□
# E UPPER BOUND ON THE SAMPLE COMPLEXITY

We prove the theoretical guarantees in the fixed-confidence setting. We prove the correctness of Algorithm 3 and we prove the sample complexity bound of Theorem 3 and some key lemmas. We first prove the correctness of the fixed-confidence variant of GEGE.

## E.1 Proof of the correctness

We need to prove that the final recommendation of Algorithm 3 is correct: that is we should show that : at any round $r$, $B_r \subset S^*$ and $D_r \subset (S^*)^c$.

**Lemma 10.** On the event $\mathcal{E}_{fc}$, Algorithm 3 identifies the correct Pareto set.

*Proof of Lemma 10.* In this part let $\tau$ denotes the stopping time of Algorithm 3. We assume $\mathcal{E}_{fc}$ holds.

Using Proposition 1: for any round $r \le \tau$ for any (Pareto) sub-optimal $i \in A_r$ we have $i^* \in A_r$. We then prove the correctness of the algorithm as follows. Let $i$ be an arm that is removed at the end of some round $r$. Assume $i \in S_r$ then, as $i$ is discarded and empirically optimal we have $\hat{\Delta}_{i,r} = \hat{\delta}_i^* \ge \varepsilon_r$. In particular, it holds that

$$ \min_{j \in A_r \setminus \{i\}} \mathrm{M}(i, j; r) \ge \varepsilon_r $$

which using Lemma 4 on the event $\mathcal{E}_{fc}$ yields

$$ \min_{j \in A_r \setminus \{i\}} \mathrm{M}(i, j) > \varepsilon_r/2 > 0, $$

that is no active arm dominates $i$. Put together with proposition $P_\infty$ (cf Lemma 9) the latter inequality yields $i \in S^*$. Now assume we have $i \notin S_r$: $i$ is discarded and it is empirically sub-optimal. Then

$$ \hat{\Delta}_{i,r} = \max_{j \in A_r} m(i, j; r) \ge \varepsilon_r/2, $$

so using Lemma 4 again on event $\mathcal{E}_{fc}$ it follows that there exists $j \in A_r$ such that $m(i, j) > 0$: that is $i \notin S^*$. Put together, we have proved that if $\mathcal{E}_{fc}$ holds then for any arm $i$ discarded at some round $r$,

$$ i \in B_{r+1} \iff i \in S^*. $$

Note that if $A_\tau$ is non-empty, then it contains a single arm and because $P_\infty$ holds, this arm is also Pareto optimal. $\square$

Thus, Algorithm 3 is correct on $\mathcal{E}_{fc}$. Before proving Theorem 3 we need Lemma 3 to control the size of the active set $A_r$ in the fixed-confidence setting.

## E.2 Controlling the size of the active set

We prove the following result that controls the size of the active set.

**Lemma 3.** The following statement holds for Algorithm 3 on the event $\mathcal{E}_{fc}$: for all $p \in [K]$, after $\lceil \log(1/\Delta_p) \rceil$ rounds it remains less than $p$ active arms. In particular, GEGE stops after at most $\lceil \log(1/\Delta_1) \rceil$ rounds.

*Proof of Lemma 3.* By Lemma 9 we on the event $\mathcal{E}_{fc}$: for any round $r$ and for any arm $i \in A_r$,

$$ \hat{\Delta}_{i,r} - \Delta_i \ge \begin{cases} -\varepsilon_r & \text{if } i \in S^* \\ -\varepsilon_r/2 & \text{else.} \end{cases} $$

Then let $p \in [K]$ and let assume an arm $i \in \{p, \dots, K\}$ is still active at round $r = \lceil \log_2(1/\Delta_p) \rceil$. We have $\hat{\Delta}_{i,r} \ge \Delta_i - \varepsilon_r$ with $\varepsilon_r = 1/2^{r+1}$ and $\Delta_i \ge \Delta_p$ which combined with $\hat{\Delta}_{i,r} \ge \Delta_i - \varepsilon_r$ yields

$$ \hat{\Delta}_{i,r} \ge \Delta_p - \varepsilon_r. \qquad (28) $$

As $r = \lceil \log_2(1/\Delta_p) \rceil$, it holds that $2\varepsilon_r \le \Delta_p$ so Eq. (28) yields $\hat{\Delta}_{i,r} \ge \varepsilon_r$ thus $i$ will be discarded at the end of round $r$ that is any arm $i \in \{p, \dots, K\}$ will be discarded at the end of round $\lceil \log_2(1/\Delta_p) \rceil$. $\square$

We now prove the main lemma on the sample complexity of GEGE in the fixed-confidence setting.
### E.3 Proof of Theorem 3

We provide an upper bound on the sample complexity of the algorithm.

**Theorem 3.** The following statement holds with probability at least $1 - \delta$: Algorithm 3 identifies the Pareto set using at most

$$ \log_2(2/\Delta_1) + O\left(\sum_{i=2}^{h} \frac{\sigma^2}{\Delta_i^2} \log\left(\frac{Kd}{\delta} \log_2\left(\frac{2}{\Delta_i}\right)\right)\right) $$

samples and $\lceil \log_2(1/\Delta_1) \rceil$ rounds, where $O(\cdot)$ hides universal multiplicative constant (explicit in Appendix E.3).

*Proof.* We assume $\mathcal{E}_{fc}$ holds. The correctness of Algorithm 3 is then proven in Lemma 10 and Lemma 3 upper-bounds the number of rounds before termination. It remains to bound the sample complexity of the algorithm on $\mathcal{E}_{fc}$ and compute $\mathbb{P}(\mathcal{E}_{fc})$ to conclude.

By Lemma 3 an upper-bound on $|A_r|$ for some specific rounds. Interestingly we can bound the sample complexity between consecutive "checkpoints rounds". In what follows, we rewrite the complexity as a sum of number of pulls between these intermediate "checkpoints rounds". Let us introduce the sequence $\{\alpha_s : s \ge 0\}$ defined as $\alpha_0 = 0$ and for any $s \ge 1$, $\alpha_s = \lceil \log_2(1/\Delta_{\lceil h/2^s \rceil}) \rceil$. We assume w.l.o.g that the sequence is non-decreasing and that the gaps are bounded in $(0, 1)$ (otherwise, we could start the sequence $(\alpha)_s$ from arms with gap smaller than 1). Simple calculation shows that $\alpha_{\lceil \log_2(h) \rceil} = \lceil \log_2(1/\Delta_1) \rceil$ and

$$ \{1, \dots, \lceil \log_2(1/\Delta_1) \rceil\} = \bigcup_{s=1}^{\lceil \log_2(h) \rceil} \{1 + \alpha_{s-1}, \alpha_s\}. \quad (29) $$

Introducing

$$ T_r := \frac{32(1 + 3\varepsilon_r)\sigma^2 h_r}{\varepsilon_r^2} \log\left(\frac{dn_r}{\delta_r}\right), $$

where $n_r = |A_r|$, we have $t_r = \lceil T_r \rceil$, so $t_r \le T_r + 1$. Using (29) then leads to

$$ \sum_{r=1}^{\lceil \log_2(1/\Delta_1) \rceil} T_r = \sum_{s=0}^{\lceil \log_2(h) \rceil - 1} \sum_{r=\alpha_s+1}^{\alpha_{s+1}} T_r \\ =: \sum_{s=0}^{\lceil \log_2(h) \rceil - 1} N_s $$

where $N_s = \sum_{r=\alpha_s+1}^{\alpha_{s+1}} T_r$ is "the number of arms pulls" between round $(\alpha_s + 1)$ and $\alpha_{s+1}$.

Next we bound the term $N_s$ for $s \in \{0, \dots, \lceil \log_2(h) \rceil - 1\}$. We recall that $h_r \le \min(h, n_r)$ as, $n_r = |A_r|$ is the number of active arms at round $r$ and $h_r$ is the dimension of the space spanned by the features of the active arms. Using Lemma 3 on $\mathcal{E}_{fc}$, it holds that for $r \ge \alpha_s + 1$

$$ n_r \le \begin{cases} K & \text{if } s = 0 \\ \lfloor h/2^s \rfloor - 1 & \text{if } s \ge 1 \end{cases} \quad (30) $$

Therefore for $s \in \{0, \dots, \lceil \log_2(h) \rceil - 1\}$ and for any $r \ge \alpha_s + 1$, we simply have $\min(h, n_r) \le \lfloor h/2^s \rfloor$, so $h_r \le \lfloor h/2^s \rfloor$ and even $h_r \le \lfloor h/2^s \rfloor - 1$ if $s > 0$. In particular, it holds that

$$ h_r \le 2\lfloor h/2^{s+1} \rfloor \quad \text{for } r \ge \alpha_s + 1. $$
It then follows that

$$ \tilde{N}_s = N_s/(32(1+3\varepsilon_1)\sigma^2) = \sum_{r=\alpha_s+1}^{\alpha_{s+1}} T_r/(32(1+3\varepsilon_1)\sigma^2) \quad (31) $$

$$ \le 2\lfloor h/2^{s+1} \rfloor \log \left( \frac{Kd}{\delta_{\alpha_{s+1}}} \right) \sum_{r=\alpha_s+1}^{\alpha_{s+1}} \frac{1}{\varepsilon_r^2} \quad (32) $$

$$ = 8\lfloor h/2^{s+1} \rfloor \log \left( \frac{Kd}{\delta_{\alpha_{s+1}}} \right) \sum_{r=\alpha_s+1}^{\alpha_{s+1}} 4^r \quad (33) $$

$$ \le 8\lfloor h/2^{s+1} \rfloor \log \left( \frac{Kd}{\delta_{\alpha_{s+1}}} \right) \sum_{r=1}^{\alpha_{s+1}} 4^r \quad (34) $$

$$ = \frac{32\lfloor h/2^{s+1} \rfloor}{3} \log \left( \frac{Kd}{\delta_{\alpha_{s+1}}} \right) (4^{\alpha_{s+1}} - 1) \quad (35) $$

then further using that

$$ \alpha_s \ge \begin{cases} \log_2(1/\Delta_{\lfloor h/2^s \rfloor}) & \text{if } s \ge 1 \\ 0 & \text{if } s = 0 \end{cases} $$

yields

$$ 4^{\alpha_{s+1}} \le \frac{1}{\Delta_{\lfloor h/2^s \rfloor}^2} $$

which combined with (35) yields

$$ \tilde{N}_s \le \frac{32\sigma^2 \lfloor h/2^{s+1} \rfloor}{3\Delta_{\lfloor h/2^s \rfloor}^2} \log \left( \frac{Kd}{\delta_{\alpha_{s+1}}} \right). \quad (36) $$

We can now bound $N = \sum_s N_s$ in terms of the sub-optimality gaps:

$$ \tilde{N} = \sum_{s=0}^{\lfloor \log_2 h \rfloor - 1} \tilde{N}_s \quad (37) $$

$$ \le \frac{32\sigma^2}{3} \sum_{s=0}^{\lfloor \log_2 h \rfloor - 1} \frac{\lfloor h/2^{s+1} \rfloor}{\Delta_{\lfloor h/2^{s+1} \rfloor}^2} \log \left( \frac{\pi^2 K d \lfloor \log_2(1/\Delta_{\lfloor h/2^{s+1} \rfloor}) \rfloor^2}{6\delta} \right), \quad (38) $$

$$ = \frac{32\sigma^2}{3} \sum_{s=1}^{\lfloor \log_2 h \rfloor} \frac{\lfloor h/2^s \rfloor}{\Delta_{\lfloor h/2^s \rfloor}^2} \log \left( \frac{\pi^2 K d \lfloor \log_2(1/\Delta_{\lfloor h/2^s \rfloor}) \rfloor^2}{6\delta} \right) \quad (39) $$

Then, recalling that by assumption $\Delta_1 \le \dots \le \Delta_K$, one can observe that the mapping from $[K]$ to $(0, \infty)$,

$$ u \mapsto \frac{1}{\Delta_u^2} \log \left( \frac{\pi^2 K d \lfloor \log_2 (1/\Delta_u) \rfloor^2}{6\delta} \right) $$

is non-increasing and it is easy to check that

$$ \lfloor h/2^s \rfloor - \lfloor \lfloor h/2^s \rfloor / 2 \rfloor + 1 \ge \frac{1}{2} \lfloor h/2^s \rfloor $$

therefore

$$ \frac{\lfloor h/2^s \rfloor}{\Delta_{\lfloor h/2^s \rfloor}^2} \log \left( \frac{\pi^2 K d \lfloor \log_2 (1/\Delta_{\lfloor h/2^s \rfloor}) \rfloor^2}{6\delta} \right) \le 2 \sum_{u=\lfloor \lfloor h/2^s \rfloor / 2 \rfloor}^{\lfloor h/2^s \rfloor} \frac{1}{\Delta_u^2} \log \left( \frac{\pi^2 K d \lfloor \log_2 (1/\Delta_u) \rfloor^2}{6\delta} \right) \quad (40) $$

Combining (39) and (40) yields

$$ N \le \frac{64\sigma^2}{3} \sum_{s=1}^{\lfloor \log_2 h \rfloor} \sum_{u=\lfloor \lfloor h/2^s \rfloor / 2 \rfloor}^{\lfloor h/2^s \rfloor} \frac{1}{\Delta_u^2} \log \left( \frac{\pi^2 K d \lfloor \log_2 (1/\Delta_u) \rfloor^2}{6\delta} \right) \quad (41) $$
Now let us introduce for any $s$, the set of integers $\mathcal{I}_s = \llbracket \lfloor h/2^s \rfloor/2 \rfloor, \lfloor h/2^s \rfloor \rrbracket$. We have

$$ \bigcup_{s=1}^{\lfloor \log_2 h \rfloor} \mathcal{I}_s \subset \{2, \dots, h\}. $$

We show that for any $p, q \in \{1, \dots, \lfloor \log_2(h) \rfloor\}$ if $|p - q| \ge 2$ then $\mathcal{I}_p \cap \mathcal{I}_q = \emptyset$. Assuming $p \le q$ we claim that

$$ \lfloor h/2^{p+2} \rfloor < \lfloor \lfloor h/2^p \rfloor/2 \rfloor \quad (42) $$

Assume otherwise, then $\lfloor h/2^{p+2} \rfloor \ge \lfloor \lfloor h/2^p \rfloor/2 \rfloor \ge \lfloor h/2^p \rfloor/2$ so

$$ h/2^{p+1} \ge \lfloor h/2^p \rfloor $$

which is impossible since for any $p \in \{0, \dots, \lfloor \log_2(h) \rfloor - 1\}$, $h/2^p \ge 1$. Therefore we have proved (42) and for any $q \ge p + 2$ it holds that

$$ \lfloor h/2^q \rfloor \le \lfloor h/2^{p+2} \rfloor < \lfloor \lfloor h/2^p \rfloor/2 \rfloor $$

thus $\mathcal{I}_q \cap \mathcal{I}_p = \emptyset$ and for any $i \in \{2, \dots, h\}$, $i$ belongs to no more than 2 of the subsets $\mathcal{I}_1, \dots, \mathcal{I}_{\lfloor \log_2 h \rfloor}$, thus we have

$$ \tilde{N} \le \frac{64}{3} \sigma^2 \sum_{s=1}^{\lfloor \log_2 h \rfloor} \sum_{u=\lfloor \lfloor h/2^s \rfloor/2 \rfloor}^{\lfloor h/2^s \rfloor} \frac{1}{\Delta_u^2} \log \left( \frac{\pi^2 K d \lfloor \log_2 (1/\Delta_u) \rfloor^2}{6\delta} \right) \quad (43) $$

$$ \le \frac{128}{3} \sigma^2 \sum_{i=2}^{h} \frac{1}{\Delta_i^2} \log \left( \frac{\pi^2 K d \lfloor \log_2 (1/\Delta_i) \rfloor^2}{6\delta} \right) \quad (44) $$

$$ \le \frac{128}{3} \sigma^2 \sum_{i=2}^{h} \frac{1}{\Delta_i^2} \log \left( \frac{\pi^2 K d \log_2(2/\Delta_i)^2}{6\delta} \right) \quad (45) $$

$$ \le \frac{256}{3} \sigma^2 \sum_{i=2}^{h} \frac{1}{\Delta_i^2} \log \left( \frac{K d}{\delta} \log_2 \left( \frac{2}{\Delta_i} \right) \right) \quad (46) $$

Then, from Lemma 9 it holds that with probability at least $1 - \delta$ the sample complexity $N^\delta$ of GEGE is upper-bounded as

$$ \log_2(2/\Delta_1) + O\left(\sum_{i=2}^{h} \frac{\sigma^2}{\Delta_i^2} \log\left(\frac{Kd}{\delta} \log_2\left(\frac{1}{\Delta_i}\right)\right)\right), \quad \square $$

where $O(\cdot)$ hides universal multiplicative constant. Therefore, we have shown the sample complexity bound and the correctness on $\mathcal{E}_{\text{fc}}$. Thus, proving that $\mathbb{P}(\mathcal{E}_{\text{fc}}) \ge 1 - \delta$ will conclude the proof.

## E.4 Probability of the good event $\mathcal{E}_{\text{fc}}$.

At round $r$,

$$ \mathbb{P}((\mathcal{E}_{\text{fc}}^r)^c | A_r) \le \sum_{i \in A_r} \mathbb{P}\left(\| (\hat{\Theta}_r - \Theta)^\top x_i \|_\infty > \varepsilon_r/4 | A_r\right) $$

Then, note that at round $r$, Algorithm 3 calls OptEstimator with precision $\varepsilon_r/2$ and budget $t_r$ and by design we have $t_r \ge 20h_r/\varepsilon_r^2$, so using Lemma 2, it follows

$$ \begin{aligned} \mathbb{P}((\mathcal{E}_{\text{fc}}^r)^c | A_r) &\le 2d \exp\left(-\frac{t_r \varepsilon_r^2}{32(1 + 3\varepsilon_r)\sigma^2 h_r}\right) \\ &\le \delta_r / |A_r| \end{aligned} $$

which follows by plugging in the value of $t_r$. Therefore, by union bound over $A_r$ and $r$ it holds that $\mathbb{P}(\mathcal{E}_{\text{fc}}) \ge 1 - \sum_{r \ge \delta_r} \delta_r \ge 1 - \delta$. This concludes the proof of Theorem 3.
## E.5 GEGE for $\epsilon$-PSI

Note that sub-optimal arms with small gaps are close to the Pareto Set. Indeed, given $\epsilon > 0$ and a sub-optimal arm $i$ such that $\Delta_i < \epsilon$. From the definition of the gap (cf Equation 1, Section 2), it follows that for any arm $j \neq i$, $m(i, j) < \epsilon$, which by definition rewrites as $\min_{c \in \{1, \dots, d\}} [\mu_j(c) - \mu_i(c)] < \epsilon$. Thus, for any arm $j \neq i$, there exists an objective $c_j$ such that $\mu_i(c_j) + \epsilon > \mu_j(c_j)$, that is $\mu_i + (\epsilon, \dots, \epsilon)$ is not dominated by any of the arms $\{\mu_j : j \neq i\}$.

Auer et al. (2016) proposed the concept of $\epsilon$-PSI, which allows practitioners to specify a parameter $\epsilon \ge 0$ to define an indifference zone around the Pareto Set. Be given an instance $\mu := (\mu_1, \dots, \mu_K)$ and its Pareto Set $S^*$, a set $S_\epsilon \subset [K]$ is an $\epsilon$-Pareto Set if: $S^* \subset S_\epsilon$, and for any $i \in S_\epsilon$, $\mu_i + (\epsilon, \dots, \epsilon)$ is not dominated by any of $\{\mu_j : j \neq i\}$. Intuitively, such a set contains all the Pareto-optimal arms but may also include some arms that are close to be Pareto-optimal.

We prove below that with the modification suggested in the main, the recommended set will be an $\epsilon$-Pareto Set and, with tiny modifications, our proof extends to cover this case and we could prove that Theorem 3 holds with each gap $\Delta_i$ replaced with $\Delta_{i,\epsilon} := \max(\Delta_i, \epsilon/2)$; that is the sample complexity is now upper bounded by

$$ \log_2(2/\Delta_{1,\epsilon}) + O\left(\sum_{i=1}^h \frac{\sigma^2}{\Delta_{i,\epsilon}^2} \log\left(\frac{Kd}{\delta} \log\left(\frac{1}{\Delta_{i,\epsilon}}\right)\right)\right). $$

**Sketch of proof** At its core, Lemma 3 proves that (with high probability) any arm $i$ such that $\Delta_i \ge 2\epsilon_r$ will not be active after round $r$ (cf proof in Section E.2). Assume the algorithm stops at some round $\tau$ because $\epsilon_\tau \le \epsilon/4$. Then, from the previous observation, if an arm $i$ is still alive at round $\tau$ then $\Delta_i < 2\epsilon_{\tau-1}$ and since $\epsilon_\tau = \epsilon_{\tau-1}/2$ (cf $\epsilon_r = 1/(2 \cdot 2^r)$ in Algorithm 3), $\Delta_i < 4\epsilon_\tau$. By assumption on the stopping, $\epsilon_\tau \le \epsilon/4$, so any arm still alive at stopping satisfies $\Delta_i < 4\epsilon_\tau \le \epsilon$. Coupling this with the proof of Lemma 10 and the discussion above will prove that the recommended set is an $\epsilon$-Pareto Set. The case where the stopping occurs because $|A_\tau| \le 1$ is already covered by Lemma 10.

To prove the sample complexity bound, we note that because of this relaxed stopping condition, Lemma 3 simply holds by replacing every gap $\Delta_i$ with $\Delta_{i,\epsilon} := \max(\Delta_i, \epsilon/2)$, then propagating this change into the proof of Theorem 3 (Appendix E.3) yields the claimed result.

## F CONCENTRATION RESULTS

In this section we prove some concentration inequalities that are essential to the proofs of others results.

**Lemma 4.** At any round $r$ and for any arms $i, j \in A_r$ it holds that

$$ \begin{aligned} |M(i, j; r) - M(i, j)| &\le \|(\hat{\Theta}_r - \Theta)^{\top}(x_i - x_j)\|_{\infty} \quad \text{and} \\ |m(i, j; r) - m(i, j)| &\le \|(\hat{\Theta}_r - \Theta)^{\top}(x_i - x_j)\|_{\infty}. \end{aligned} $$

*Proof.* We have

$$ \begin{aligned} |M(i, j; r) - M(i, j)| &= \left| \max_c [\hat{\mu}_{i,r}(c) - \hat{\mu}_{j,r}(c)] - \max_c [\mu_i(c) - \mu_j(c)] \right|, \\ &\stackrel{(i)}{\le} \max_c \left| (\hat{\mu}_{i,r}(c) - \hat{\mu}_{j,r}(c)) - (\mu_i(c) - \mu_j(c)) \right|, \\ &= \|(\hat{\mu}_{i,r} - \hat{\mu}_{j,r}) - (\mu_i - \mu_j)\|_{\infty}, \\ &= \|(\hat{\Theta}_r - \Theta)^{\top}(x_i - x_j)\|_{\infty}. \end{aligned} $$

where $(i)$ follows from reverse triangle inequality. The second part of the lemma is a direct consequence of the relation $M(i, j) = -m(i, j)$ as well as $M(i, j; r) = -m(i, j; r)$ that holds for any pair of arms $i, j$. $\square$

**Lemma 5.** At any round $r$, for any sub-optimal arm $i \in A_r$, if $i^* \in A_r$ and $i^*$ does not empirically dominate $i$ then $\Delta_i^* < \|(\hat{\Theta}_r - \Theta)^{\top}(x_i - x_{i^*})\|_{\infty}$.
Proof. Since $i^*$ does not empirically dominate $i$ it holds that $M(i, i^*; r) > 0$ so $M(i, i^*; r) - M(i, i^*) > -M(i, i^*)$. Then noting that

$$-M(i, i^*) = m(i, i^*) = \Delta_i$$

yields $M(i, i^*; r) - M(i, i^*) > \Delta_i$. Therefore

$$\Delta_i = \Delta_i^* < M(i, i^*; r) - M(i, i^*) \\ \le \|(\hat{\Theta}_r - \Theta)^T(x_i - x_{i^*})\|_{\infty},$$

where the last inequality is a consequence of Lemma 4. □

We recall the following lemma from the main paper.

**Lemma 1.** If the noise $\eta_t$ has covariance $\Sigma \in \mathbb{R}^{d \times d}$ and $a_1, \dots, a_n$ are deterministically chosen then for any $x_i \in \{x_{a_1}, \dots, x_{a_n}\}$, $\mathrm{Cov}(\hat{\Theta}_N^T x_i) = \|x_i\|_{V_N^\dagger}^2 \Sigma$.

We actually prove a stronger statement that is stated below.

**Lemma 11.** If the noise $\eta_t$ has covariance $\Sigma \in \mathbb{R}^{d \times d}$ and $a_1, \dots, a_N$ are deterministically. Assuming the set of active arms is $x_1, \dots, x_K$ then for any $x \in \mathrm{span}(\{x_1, \dots, x_K\})$, $\mathrm{Cov}(\hat{\Theta}_N^T x) = \|x\|_{V_N^\dagger}^2 \Sigma$.

Proof. In what follows we let $E := \mathrm{span}(\{x_1, \dots, x_K\})$ be the space spanned the vectors $x_1, \dots, x_K$. As the columns of $B$ forms an orthogonal basis of $E$, $P = B(B^T B)^{-1}B^T = BB^T$ is a matrix that project onto $E$. Therefore, for any $x \in E$

$$\Theta^T x = \Theta^T B B^T x = (B^T \Theta)^T B^T x.$$

Thus recalling that $X_N = (x_{a_1}, \dots, x_{a_N})^T$ it holds that $X_N \Theta = (X_N B)(B^T \Theta)$. Rewriting the solution of the least squares leads to

$$\begin{aligned}
\hat{\Theta}_N &= B(B^T V_N B)^{-1} B^T X_N^T (X_N \Theta + H_N) \\
&= B(B^T V_N B)^{-1} B^T X_N^T (X_N \Theta) + V_N^\dagger X_N^T H_N \\
&= B(B^T V_N B)^{-1} B^T X_N^T (X_N B)(B^T \Theta) + V_N^\dagger X_N^T H_N \\
&= B(B^T V_N B)^{-1} (B^T V_N B)(B^T \Theta) + V_N^\dagger X_N^T H_N \\
&= BB^T \Theta + V_N^\dagger X_N^T H_N
\end{aligned}$$

then for any $x \in E$, as $BB^T x = x$ it follows that

$$\begin{aligned}
\hat{\Theta}_N^T x &= \Theta^T B B^T x + (V_N^\dagger X_N^T H_N)^T x \\
&= \Theta^T x + (V_N^\dagger X_N^T H_N)^T x
\end{aligned}$$

thus we have for $x \in E$,

$$(\hat{\Theta}_N - \Theta)^T x = (V_N^\dagger X_N^T H_N)^T x. \qquad (47)$$

Computing the covariance follows as

$$\mathrm{Cov}((\hat{\Theta}_N - \Theta)^T x) = \mathbb{E}[(V_N^\dagger X_N^T H_N)^T x x^T (V_N^\dagger X_N^T H_N)] \quad (48)$$

$$= \mathbb{E}[H_N^\dagger \tilde{x} \tilde{x}^T H_N] \qquad (49)$$

where $\tilde{x} := X_N V_N^\dagger x$. Letting $h_i^\dagger$ denotes the $i$-th row of $H_N^\dagger$, for each $i, j$

$$\mathbb{E}[h_i^\dagger \tilde{x} \tilde{x}^T h_j] = \tilde{x}^T \mathbb{E}[h_i h_j^\dagger] x \qquad (50)$$

$$= \tilde{x}^T \sigma_{i,j} \tilde{x} \qquad (51)$$

where $\Sigma := (\sigma_{r,s})_{r,s \le d}$ and the last line follows since for any $t, t' \le N$ by independence of successive observations we have $\mathbb{E}[h_i(t)h_j(t')] = \delta_{t,t'}^{\mathrm{kro}} \sigma_{i,j}$. Combining Eq. (51) with Eq. (49) yields

$$\mathrm{Cov}((\hat{\Theta}_N - \Theta)^T x) = \Sigma \tilde{x}^T \tilde{x}$$
then further noting that

$$ 
\begin{align*}
\tilde{x}^{\top} \tilde{x} &= x^{\top} V_{N}^{\dagger} X_{N}^{\top} X_{N} V_{N}^{\dagger} x \\
&= x^{\top} B (B^{\top} V_{N} B)^{-1} B^{\top} V_{N} B (B^{\top} V_{N} B)^{-1} B^{\top} x \\
&= x^{\top} V_{N}^{\dagger} x = \|x\|_{V_{N}^{\dagger}}^{2}
\end{align*}
$$

concludes the proof.

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

The following results is proven in Appendix H.

**Lemma 2.** Let $S \subset [K]$, $\kappa \in (0, 1/3]$ and $N \ge 5h_S/\kappa^2$ where $h_S = \dim(\operatorname{span}(\{x_i : i \in S\}))$. The output $\hat{\Theta}$ of OptEstimator($S$, $N$, $\kappa$) satisfies for all $\varepsilon > 0$ and $i \in S$

$$ \mathbb{P} \left( \| (\Theta - \hat{\Theta})^{\top} x_i \|_{\infty} \ge \varepsilon \right) \le 2d \exp \left( - \frac{N\varepsilon^2}{2(1 + 6\kappa)\sigma^2 h_S} \right). $$

## G LOWER BOUNDS

Before proving the lower bounds, we illustrate the PSI and the quantities M, m on Fig.5

<figure><img src="image_8.png" /><figcaption>Figure 5: PSI gaps and distances</figcaption></figure>

We note that, in this instance $\Delta_i = m(i, j)$ and by increasing $i$ by $\Delta_i$ on both $x$ and $y$ axes it will become non-dominated.

We also have $\Delta_{\ell} = m(\ell, j)$. As $\ell$ is only dominated by $j$, if it is translated by $m(\ell, j)$ on the $x$-axis it will become Pareto optimal.

For Pareto-optimal arms $k, j$, $\delta_k^+ = \delta_j^+ = M(j, k)$. As $k$ dominates both $i$ and $\ell$ its margin to sub-optimal arms is $\delta_k^- = \min(\Delta_i, \Delta_{\ell})$ and we have $\delta_j^- = \min(M(\ell, j) + \Delta_{\ell}, \Delta_i)$.

Observe that for both $j, k$, $\Delta_j = \Delta_k = M(j, k)$. If $k$ is translated by $M(j, k)$ on the $y$-axis it will dominate $j$. Similarly, if $j$ is translated by $-M(j, k)$ on the $y$-axis, it will be dominated by $k$.

We now prove minimax lower bounds in both fixed-confidence and fixed-budget settings. We recall the lower-bound below for un-structured PSI in the fixed confidence setting.

**Theorem 5 (Theorem 17 of Auer et al. (2016)).** For any set of operating points $\mu_i \in [1/4, 3/4]^d$, $i = 1, \dots, K$, there exist distributions $(D_i)_{1 \le i \le K}$ such that with probability at least $1 - \delta$, any $\delta$-correct algorithm for PSI requires at least

$$ \Omega \left( \sum_{i=1}^{K} \frac{1}{\tilde{\Delta}_i^2} \log(\delta^{-1}) \right) $$

samples to identify the Pareto set. Where for any sub-optimal arm $\tilde{\Delta}_i = \Delta_i$ and for an optimal arm $\tilde{\Delta}_i = \delta_i^+$.
In particular, there exist instances where $\Delta_i = \delta_i^+$ for any Pareto-optimal arm $i$. Thus, this result shows that $H_1$ is a good proxy to measure the complexity of PSI in the fixed-confidence setting.

The proof of such results often rely on the celebrated change of distribution technique (see e.g Kaufmann et al. (2016)) which given the instance $\nu := (\nu_1, \dots, \nu_K)$ shifts the mean of $\nu_i$ for an arm $i$ while keeping the others fixed constant. However, in linear PSI, the arms' means are correlated through $\Theta$. So, in general, Theorem 5 does not directly apply to linear PSI. We recall below our lower bound for linear PSI in the fixed-confidence setting.

**Theorem 4.** For any $K, d, h \in \mathbb{N}$, there exists a set $\mathcal{B}(K, d, h)$ of linear PSI instances s.t for $\nu \in \mathcal{B}(K, d, h)$ and for any $\delta$-correct algorithm for PSI, with probability at least $1 - \delta$,

$$ \tau_{\delta}^{A} \geq \Omega(H_{1,lin}(\nu) \log(\delta^{-1})). $$

*Proof of Theorem 4.* The idea of the proof is to transform an unstructured bandit instance into a linear PSI instance. Let $\nu$ be a bandit instance with $K \geq 2$ arms and dimension $d \geq 1$ and with means $\mu_1, \dots, \mu_K \in [0, 1]^d$. Let $e_1, \dots, e_h$ denote the canonical basis of $\mathbb{R}^h$. We define a linear PSI instance $\nu_{\text{lin}}$ with features

$$ x_i = \begin{cases} e_i & \text{if } i \leq h \\ \mathbf{0} & \text{else.} \end{cases} $$

We assume that the learner knows that $\mu_i \in [0, 1]^d$ for any arm $i$. We claim that with this information an "efficient" algorithm for PSI should not pull arms from $\{h+1, \dots, K\}$. To see this, first note that these arms will be sub-optimal so $S^* \subset [h]$. Moreover, even if an arm $i \in \{h+1, \dots, K\}$ dominates another arm $j \in \{1, \dots, h\}$, as $j$ is not Pareto-optimal there exits another arm $j^* \in S^* \subset \{1, \dots, h\}$ which dominates $j$ with a larger margin, so is "cheaper" to pull. Therefore the complexity of $\nu_{\text{lin}}$ reduces to the complexity of a linear bandit $\tilde{\nu}_{\text{lin}}$ with only $h$ arms. As the features in $x_1, \dots, x_h$ forms the canonical $\mathbb{R}^h$ basis, $\tilde{\nu}_{\text{lin}}$ reduces to an un-structured bandit instance with (un-correlated) means $\tilde{\mu}_i = \Theta^\top x_i$, $i = 1, \dots, h$. Therefore, by choosing $\mu_1, \dots, \mu_h \in [1/4, 3/4]^d$, we can apply Theorem 5 to $\tilde{\nu}_{\text{lin}}$. $\square$

The result proven above holds for a class of instances $\mathcal{B}(K, d, h)$ with the covariates defined as above and with matrix coefficients in $[1/4, 3/4]^d$.

For the fixed-budget setting, Kone et al. (2024) proved a lower bound for a class of instances. We recall their result below after introducing some notation.

Their lower bound applies to the class of instances $\mathcal{B}$ defined as follows. $\mathcal{B}$ contains the instances such that each sub-optimal arm $i$ is only dominated by a Pareto-optimal arm denoted by $i^*$ and that for each optimal arm $j$ there exists a unique sub-optimal arm which is dominated by $j$, denoted by $\tilde{j}$. Moreover, for any instance in $\mathcal{B}$ the authors require its Pareto-optimal arms not to be close to the sub-optimal arms they don't dominate: for any sub-optimal arm $i$ and Pareto-optimal arm $j$ such that $\mu_i \not\perp \mu_j$,

$$ M(i, j) \geq 3 \max(\Delta_i, \Delta_{\perp}). $$

Let $\nu := (\nu_1, \dots, \nu_K)$ be an unstructured instance whose means belongs to $\mathcal{B}$ and with isotropic multi-variate normal arms $\nu_i \sim \mathcal{N}(\mu_i, \sigma^2 I)$. For every $i \in [K]$, define the alternative instance $\nu^{(i)} := (\nu_1, \dots, \nu_i^{(i)}, \dots, \nu_K)$ in which only the mean of arm $i$ is shifted:

$$ \mu_i^{(i)} := \begin{cases} \mu_i - 2\Delta_i \tilde{e}_{d_i} & \text{if } i \in S^*(\nu), \\ \mu_i + 2\Delta_i \tilde{e}_{d_i} & \text{else,} \end{cases} \qquad (52) $$

where $\tilde{e}_1, \dots, \tilde{e}_d$ denotes the canonical basis of $\mathbb{R}^d$ and for any arm $i$, $d_i := \underset{c \in [d]}{\operatorname{argmin}} [\mu_i^*(c) - \mu_i(c)]$. Defining $\nu^{(0)} := \nu$, the theorem below holds.

**Theorem 6** (Theorem 5 of Kone et al. (2024)). Let $\nu = (\nu_1, \dots, \nu_K)$ be an instance in $\mathcal{B}$ with means $\mu := (\mu_1 \dots \mu_K)^\top$ and $\nu_i \sim \mathcal{N}(\mu_i, \sigma^2 I)$. For any algorithm $\mathcal{A}$, there exists $i \in \{0, \dots, K\}$ such that $H(\nu^{(i)}) \leq H(\nu)$ and the probability of error $\mathcal{A}$ on $\nu^{(i)}$ is at least

$$ \frac{1}{4} \exp \left( - \frac{2T}{\sigma^2 H(\nu^{(i)})} \right). $$
As explained above for the fixed-confidence setting. The proof of this lower bound also uses the change of distribution lemma. In the instances $\nu^{(i)}$ introduced above, it is crucial that only the mean of arm $i$ has changed w.r.t $\nu^{(0)}$. Therefore, Theorem 6 does not apply to general instances in linear PSI. We recall our lower-bound for linear PSI in the fixed-budget.

**Theorem 2.** Let $\mathbb{W}_H$ be the set of instances with complexity $H_{2,\text{lin}}$ smaller than $H$. For any budget $T$, letting $\hat{S}_T^A$ be the output of an algorithm $\mathcal{A}$, it holds that

$$ \inf_{\mathcal{A}} \sup_{\nu \in \mathbb{W}_H} \mathbb{P}_{\nu}(\hat{S}_T^A \neq S^*(\nu)) \geq \frac{1}{4} \exp\left(-\frac{2T}{H\sigma^2}\right). $$

*Proof of Theorem 2.* Let $H$ be fixed and recall that $\mathbb{W}_H : \{\nu_{\text{lin}} : H_{2,\text{lin}}(\nu) \leq H\}$ is the set of linear PSI instances with complexity less than $H$. The proof of Theorem 2 follows similar lines to Theorem 4. Let $\nu$ be an un-structured bandit instance with $K \geq 2$ arms, dimension $d \geq 1$, with means $\mu_1, \dots, \mu_K \in [0, 1]^d$ and such that $H_2(\nu) \leq H$. We construct a linear PSI instance $\nu_{\text{lin}}$ from an unstructured multi-dimensional instance $\nu$ by setting $x_i := e_i$ for any $i \leq h$ and for $i > h$, $x_i = 0$ where $e_1, \dots, e_h$ is the canonical $\mathbb{R}^h$-basis. We also assume that the agent knows that $\mu_i \in [0, 1]^d$ for any arm $i$. For $\nu_{\text{lin}}$ the arms $\{h+1, \dots, K\}$ are necessarily sub-optimal so $S^* \subset [h]$ thus to identify the Pareto set and efficient algorithm should reduce to pull arms in $\{1, \dots, h\}$. Indeed, as explained in the proof of Theorem 4 even if an arm $i \in \{h+1, \dots, K\}$ dominates another arm $j \in \{1, \dots, h\}$, as $j$ is not Pareto-optimal there exists another arm $j^* \in S^* \subset \{1, \dots, h\}$ which is "cheaper" to pull as it dominates $j$ with a larger margin. $\nu_{\text{lin}}$ reduces to a linear bandit $\tilde{\nu}_{\text{lin}}$ with only $h$ arms and since the features $x_1, \dots, x_h$ forms the canonical basis of $\mathbb{R}^h$, $\tilde{\nu}_{\text{lin}}$ is an un-structured bandit instance with (un-correlated) means $\tilde{\mu}_i = \Theta^\top x_i$, $i = 1, \dots, h$. Therefore, by choosing $\tilde{\nu} := (\nu_1, \dots, \nu_h)$ that belongs to $\mathcal{B}$, we can apply Theorem 6 which yields

$$ \max_{i \in \{0, \dots, K\}} \mathbb{P}_{\tilde{\nu}^{(i)}}(S_T^A \neq S^*(\tilde{\nu}^{(i)})) \geq \frac{1}{4} \exp\left(-\frac{2T}{H\sigma^2}\right) $$

where by construction $\tilde{\nu}^{(i)}$ (see construction above) is also a linear PSI instance. Then further noting that $H \geq H_2(\nu) \geq H_2(\tilde{\nu})$ and by Theorem 6 for any $i \leq h$ $H_{2,\text{lin}}(\tilde{\nu}) \geq H_2(\tilde{\nu}^{(i)})$. Then recalling that $\nu_{\text{lin}}$ is equivalent to $\tilde{\nu}$ it comes

$$ \inf_{\mathcal{A}} \sup_{\nu \in \mathbb{W}_H} \mathbb{P}_{\nu}(S_T^A \neq S^*(\nu)) \geq \frac{1}{4} \exp\left(-\frac{2T}{H\sigma^2}\right), $$

which is the claimed result.

□

## H COMPUTATION AND ROUNDING OF G-OPTIMAL DESIGN

In this section, we discuss the results related to the G-design and the rounding. In what follows, let $S \subset [K]$ be a set of arms. To ease notation we re-index the arms of $S$ by assuming $S := \{1, \dots, |S|\}$. Let $N$ be the allocation budget (the total number of pulls of arms in $S$) and $\kappa \in (0, 1/3]$ the parameter of the rounding algorithm to be fixed. $h_S = \dim(\text{span}(\{x_i : i \in S\}))$ is the dimension of the space spanned by the covariates of $S$. $\mathcal{X}_S := (x_i, i \in S)^\top$ and $B_S := (u_1, \dots, u_m)$ is the matrix formed with the first $m = h_S = \text{rank}(S)$ columns of $U$, the matrix of left singular vectors of $\mathcal{X}_S^\top$ obtained by singular value decomposition. We recall that for $N$ pulls of arms in $[S]$, letting $T_i(N)$ be number of samples collected from arm $i$,

$$ V_N^\dagger := B_S(B_S^\top V_N B_S)^{-1} B_S^\top \quad \text{and} \quad V_N := \sum_{i=1}^K T_i(N) x_i x_i^\top. \qquad (53) $$

As from Lemma 1 the statistical uncertainty from estimating the mean of arm $i$ scales with $\|x_i\|_{V_N^\dagger}$, a call to OptEstimator($S$, $N$, $\kappa$) is meant to estimate the hidden parameter $\Theta$ by collecting $N$ samples from arms in $S$ according to an approximation of the solution of the following problem (ordinal G-optimal design):

$$ \begin{array}{ll} \underset{s \in [0, \dots, N] | s|}{\operatorname{argmin}} & \max_{i \in S} \|x_i\|_{(V^s)^\dagger} \\ \text{s.t.} & \sum_{i \in S} s(i) = N. \end{array} \qquad (54) $$
Finding such an optimal design with integer values is an NP-hard problem (Allen-Zhu et al., 2017). Instead, its continuous relaxation (obtained by normalizing by $N$), amounts to finding an allocation $w$ that minimizes

$$ \max_{i \in S} (B_S^\top x_i)^\top \left( \sum_{i \in S} w(i) B_S^\top x_i x_i^\top B_S \right)^{-1} B_S^\top x_i, \quad (55) $$

which reduces to compute a G-optimal allocation on the covariates $B_S^\top x_i, i \in S$:

$$ w_S^* \in \operatorname*{argmin}_{w \in \Delta_{|S|}} \max_{i \in S} \|\tilde{x}_i\|_{(\tilde{V}^w)^{-1}}^2, \quad \text{and} \quad \tilde{V}^w := \sum_{i \in S} w(i) \tilde{x}_i \tilde{x}_i^\top. \quad (56) $$

This is a convex optimization problem on the probability simplex of $\mathbb{R}^{|S|}$. Efficient solvers have been used in the literature for linear BAI and experiment design optimization see (e.g Fiez et al. (2019); Soare et al. (2014)). In this work, we follow Allen-Zhu et al. (2017) and we recommend an entropic mirror descent algorithm to solve Eq. (56), which is recalled as Algorithm 4 for the sake of completeness.

Then, computing an integer allocation whose value is close to the optimal value of Eq. (56) can be done in different ways. Tao et al. (2018) and Camilleri et al. (2021) use a stochastic rounding: they sample $N$ arms from $S$ following the distribution $w_S^*$ and use a novel estimator different from the least-squares estimate. Yang and Tan (2022); Azizi et al. (2022) use floors and ceilings of $N w_S^*$. Although practical, it is known that the value of such rounded allocations can deviate a lot from the optimal value of Eq. (54) (Tao et al., 2018).

**Algorithm 4:** Entropic mirror descent algorithm for computing $w_S^*$ Tao et al. (2018)

**Input:** A set of arms $S$ and covariates $(\tilde{x}_i, i \in S)$, tolerance $\varepsilon$ and Lipschitz constant $L_f$

**Initialize:** $t \leftarrow 1$ and $w^{(1)} \leftarrow (1/|S|, \dots, 1/|S|)$

**while** $|\max_{i \in S} \tilde{x}_i^\top (\tilde{V}^w)^{-1} \tilde{x}_i - h_S| \ge \varepsilon$ **do**

set $\eta_t \leftarrow \frac{\sqrt{2 \ln N}}{L_f} \frac{1}{\sqrt{t}}$

Compute gradient $g_i^{(t)} \leftarrow \text{Tr} (\tilde{V} (w^{(t)})^{-1} (\tilde{x}_i \tilde{x}_i^T))$

Update $w_i^{(t+1)} \leftarrow \frac{w_i^{(t)} \exp(\eta_t g_i^{(t)})}{\sum_{i=1}^N w_i^{(t)} \exp(\eta_t g_i^{(t)})}$

$t \leftarrow t + 1$

**return:** $w^{(t)}$

Allen-Zhu et al. (2017) proposed an efficient rounding procedure that guarantees that the value of the returned integer allocation is within a small factor of the optimal value of Eq. (56). Before recalling their result, we introduce the notation $F_S(s) := \max_{i \in S} \|x_i\|_{(V^s)^\top}$.

We recall the celebrated Kiefer-Wolfowitz equivalence theorem below.

**Theorem 7** (Restatement of Kiefer and Wolfowitz (1960)). Let covariates $\{x_i : i \in S\} \subset \mathbb{R}^h$ and for any $w \in \Delta_{|S|}$ define $V^w = \sum_{i \in S} w(i) x_i x_i^\top$ and when $V^w$ is non-singular $f(x; w) := x^\top (V^w)^{-1} x$. The following two extremum problems:

a) $w$ maximizing $\det(V^w)$

b) $w$ minimizing $\max_{i \in S} f(x_i; w)$

are equivalent and a sufficient condition to satisfy Eq. (b) is $\max_{i \in S} f(x_i, w) = h$, which is satisfied when the covariates $\{x_i : i \in S\} \text{span } \mathbb{R}^h$.

**Theorem 8** (reformulated; rounding method of Allen-Zhu et al. (2017)). Suppose $\kappa \in (0, 1/3]$ and $N \ge 5h_S/\kappa^2$. Let $w_S^* = \argmin_{w \in \Delta_S} F_S(w)$. Then, there exists an algorithm that outputs an integer allocation $s^*$ satisfying

$$ s^* \in \mathcal{D}_{S,N} \quad \text{and} \quad F_S(s^*) \le (1 + 6\kappa) \frac{F_S(w_S^*)}{N} $$

where $\mathcal{D}_{S,N} := \{s \in \{0, \dots, N\}^{|S|} : \sum_{i \in S} s(i) = N\}$. This algorithm runs in time complexity $\tilde{O}(N|S|\tilde{h}^2)$.
We refer to a call to this algorithm as `ROUND(N, {x̃_i, i ∈ S}, w_S^*, κ)`. It returns an integer allocation $s^* = (s^*(1), ..., s^*(|S|))$ from which we can immediately deduce a list of arms to pull (the first arm in $S$ replicated $s^*(1)$ times, the second replicated $s^*(2)$ times, etc.).

Simple arguments from linear algebra show that the $h_S$ columns of $B_S$ form a basis of $\operatorname{span}(\{x_i : i \in S\})$, hence $\{B_S^T x_i : i \in S\}$ spans $\mathbb{R}^{h_S}$. Using Theorem 7 applied to the covariates $\{B_S^T x_i : i \in S\}$ yields

$$F_S(w_S^*) = h_S$$

and thus the integer allocation $s^*$ output by `ROUND(N, {x̃_i, i ∈ S}, w_S^*, κ)` satisfies for $N \ge 5h_S/\kappa^2$,

$$F(s^*) \le (1 + 6\kappa) \frac{h_S}{N},$$

which is stated below.

**Lemma 12.** Let $S \subset [K]$, $\kappa \in (0, 1/3]$ and $N \ge 5h_S/\kappa^2$ where $h_S = \dim(\operatorname{span}(\{x_i : i \in S\}))$. The allocation $\{T_i(N) : i \in S\}$ computed by OptEstimator($S$, $N$, $\kappa$) to estimate $\Theta$ satisfies

$$\max_{i \in S} \|x_i\|_{V_N^\dagger}^2 \le (1 + 6\kappa) \frac{h_S}{N}.$$

Building on this result, we derive the following concentration result.

**Lemma 2.** Let $S \subset [K]$, $\kappa \in (0, 1/3]$ and $N \ge 5h_S/\kappa^2$ where $h_S = \dim(\operatorname{span}(\{x_i : i \in S\}))$. The output $\hat{\Theta}$ of OptEstimator($S$, $N$, $\kappa$) satisfies for all $\varepsilon > 0$ and $i \in S$

$$\mathbb{P} \left( \| (\Theta - \hat{\Theta})^{\top} x_i \|_{\infty} \ge \varepsilon \right) \le 2d \exp \left( - \frac{N \varepsilon^2}{2(1 + 6\kappa) \sigma^2 h_S} \right).$$

*Proof of Lemma 2.* We recall that, by assumption, the vector noise has $\sigma$-sub-gaussian marginals. From the proof of Lemma 11 it is easy to see that for any $i \in S$, the marginals of $(\Theta - \hat{\Theta})x_i$ are $\sigma\|X_N^T V_N^\dagger x_i\|_{2}$-sub-gaussian. Then, direct calculation shows that

$$\begin{align*}
\| X_N^T V_N^\dagger x_i \|_2^2 &= x_i^T V_N^\dagger V_N V_N^\dagger x_i \\
&= x_i^T (B_S (B_S^T V_N B_S)^{-1} B_S^T) V_N (B_S (B_S^T V_N B_S)^{-1} B_S^T) x_i \\
&= x_i^T B_S (B_S^T V_N B_S)^{-1} B_S^T x_i \\
&= x_i^T V_N^\dagger x_i = \|x_i\|_{V_N^\dagger}^2.
\end{align*}$$

Therefore, by concentration of sub-gaussian variables (see e.g Lattimore and Szepesvári (2020)) we have for $i$ fixed,

$$\begin{align*}
\mathbb{P}(\| (\Theta - \hat{\Theta})^{\top} x_i \|_{\infty} \ge \varepsilon) &\le 2d \exp \left( - \frac{\varepsilon^2}{2\sigma^2 \|x_i\|_{V_N^\dagger}^2} \right) \\
&\le 2d \exp \left( - \frac{\varepsilon^2}{2\sigma^2 \max_{k \in S} \|x_k\|_{V_N^\dagger}^2} \right)
\end{align*}$$

then the G-optimal design and the rounding (Lemma 12) ensure that

$$\max_{k \in S} \|x_k\|_{V_N^\dagger}^2 \le (1 + 6\kappa)h_S/N.$$

Thus

$$\mathbb{P} \left( \| (\Theta - \hat{\Theta})^{\top} x_i \|_{\infty} \ge \varepsilon \right) \le 2d \exp \left( - \frac{N \varepsilon^2}{2(1 + 6\kappa) \sigma^2 h_S} \right).$$

□
# I IMPLEMENTATION DETAILS AND ADDITIONAL EXPERIMENTS

In this section, we detail our experimental setup and provide additional experimental results.

## I.1 Complexity and setup

**Time and memory complexity** The main computational cost of GEGE (excepting calls to OptEstimator) is the computation of the empirical gaps. This requires computing $M(i, j; r)$ for any tuple $(i, j)$ of active arms and to temporarily store them. Computing the gaps results in a total $O(K^2d)$ time complexity and $O(K^2)$ memory complexity. Note that for the memory allocation, we can maintain the same arrays for the whole execution of the algorithm; thus, only cheap memory allocations are made after initialization. The overall computational complexity is reasonable as GEGE is an elimination algorithm the computational cost reduces after rounds and we have proven that no more than $\lfloor \log_2(1/\Delta_1) \rfloor$ rounds are required in the fixed-confidence regime and only $\lfloor \log_2(h) \rfloor$ rounds in the fixed-budget setting. For this reason, the computational complexity of a call to OptEstimator has a limited impact in practice. We report below the average runtime on a personal computer with an ARM CPU 8GB RAM and 256GB SSD storage. The values are averaged over 50 runs.

<table><caption>Table 2: Runtime of GEGE recorded different instances.</caption><thead><tr><th>[K, h, d]</th><th>GEGE[δ = 0.1]</th><th>GEGE[T = 500]</th></tr></thead><tbody><tr><td>[10, 2, 2]</td><td>6ms</td><td>217ms</td></tr><tr><td>[50, 8, 2]</td><td>7ms</td><td>464ms</td></tr><tr><td>[100, 8, 4]</td><td>545ms</td><td>791ms</td></tr><tr><td>[200, 8, 8]</td><td>768ms</td><td>1139ms</td></tr><tr><td>[500, 8, 8]</td><td>1013ms</td><td>2425ms</td></tr></tbody></table>

**Setup** We have implemented the algorithms mainly in python3 and C++. For each experiment, the value reported (sample complexity or probability of error) is averaged over 500 runs. For the experiments on synthetic instances we generate an instance satisfying the conditions reported in the main by first picking the $h$ vectors (and thus $\Theta$) then the remaining arms are generated by sampling and normalizing some features from $U([0, 1]^h)$ to satisfy the contraints. For the real-world datasets, we normalize the features and (when mentioned) we use a least square to estimate a regression parameter $\hat{\Theta}$ or we use the dataset as such (mis-specified setting i.e., without linearization). PAL is run with the same confidence bonus used in Zuluaga et al. (2016) (which are tuned empirically) and for APE, we follow Kone et al. (2023) and we use their confidence bonuses on a pair of arms, which was already suggested by Auer et al. (2016).

## I.2 Additional experiments

We provide additional experiments on synthetic and real-world datasets. GEGE is evaluated both in the fixed-confidence and fixed-budget regimes.

**Multi-objective optimization of energy efficiency** We use the energy efficiency dataset of Tsanas and Xifara (2012). This dataset is made for buildings' energy performance optimization. The efficiency of each building is characterized by $d = 2$ quantities: the cooling load and the heating load. The heating load is the amount of energy that should be brought to maintain a building at an acceptable temperature, and the cooling load is the amount of energy that should be extracted from a building to sustain a temperature in an acceptable range. Ideally, both heating and cooling loads should be low for energy efficiency, and they are characterized by different factors like glazing area and the orientation of the building, amongst other parameters. Tsanas and Xifara (2012) reported the simulated heating and cooling loads of $K = 768$ buildings together with $h = 8$ features characterizing each building, including surface, roof and wall areas, the relative compactness, overall height, etc. The dataset was primarily made for multivariate regression, but we use it for linear PSI as the goal is to optimize simultaneously heating and cooling loads, which in general (and in this case), results in a Pareto front of 3 arms. We evaluate Algorithm 2 with a budget $T = 10000$ and in the fixed-confidence we set $\delta = 0.1$ for Algorithm 3. We report the results average over 500 runs on Fig.6 and
Fig.7. In the fixed-confidence experiment, "Racing" is the algorithm of Auer et al. (2016) for unstructured PSI.

<figure><img src="image_9.png" /><figcaption>**Figure 6:** Average probability of error on the energy efficiency dataset.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>**Figure 7:** Sample complexity distribution on the energy efficiency dataset.</figcaption></figure>

We observe that in both fixed-confidence and fixed-budget, GEGE largely outperforms its competitors. It is worth noting that in the fixed-budget setting, as $K = 768$, Uniform Allocation requires $T \ge 768$ to be run correctly, while EGE-SH requires $T \ge 7360$ to be able to initialize each arm, as they both ignore the linear structure. On the contrary GEGE just requires $T \ge [\log(h)]$ which is negligible w.r.t $K = 768$. Moreover, we observed that its probability of error is reasonable even for a budget $T < K$.