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

HAL
open science

# Pareto Set Identification With Posterior Sampling

Cyrille Kone, Marc Jourdan, Emilie Kaufmann

► To cite this version:

Cyrille Kone, Marc Jourdan, Emilie Kaufmann. Pareto Set Identification With Posterior Sampling. AISTATS 2025 - 28th International Conference on Artificial Intelligence and Statistic, May 2025, Phuket, Thailand. hal-05125257

HAL Id: hal-05125257

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

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
Pareto Set Identification With Posterior Sampling

Cyrille Kone

Univ. Lille, CNRS, Inria, Centrale Lille,
UMR 9189-CRISTAL, F-59000 Lille, France

Marc Jourdan

EPFL,
Lausanne, Switzerland

Emilie Kaufmann

Univ. Lille, CNRS, Inria, Centrale Lille,
UMR 9189-CRISTAL, F-59000 Lille, France

Abstract

The problem of identifying the best answer
among a collection of items having real-valued
distribution is well-understood. Despite its prac-
tical relevance for many applications, fewer
works have studied its extension when multiple
and potentially conflicting metrics are available
to assess an item’s quality. Pareto set identifi-
cation (PSI) aims to identify the set of answers
whose means are not uniformly worse than an-
other. This paper studies PSI in the transductive
linear setting with potentially correlated objec-
tives. Building on posterior sampling in both
the stopping and the sampling rules, we pro-
pose the PSIPS algorithm that deals simultane-
ously with structure and correlation without pay-
ing the computational cost of existing oracle-
based algorithms. Both from a frequentist and
Bayesian perspective, PSIPS is asymptotically
optimal. We demonstrate its good empirical per-
formance in real-world and synthetic instances.

# 1 INTRODUCTION

When facing a pure exploration problem, the decision
maker aims to answer a question about a set of unknown
distributions (e.g. modeling the treatment's effects) from
which she gathers observations (e.g., measure of its out-
comes) while providing theoretical guarantees on the can-
didate's answer. Practitioners might have multiple, poten-
tially conflicting, metrics to optimize simultaneously (Zu-
luaga et al., 2013). When there is no clear trade-off be-
tween those metrics, aggregation into a unique objective is
unrealistic despite being appealing. For instance, in clini-
cal trials, both the effectiveness and safety of a treatment
should be high (Jennison and Turnbull, 1993), but specify-

ing the safety cost of an increased efficacy would be uneth-
ical. Likewise, in chip design, the runtime of the hardware
and its energy consumption should be low (Almer et al.,
2011). Moreover, there may exist a statistical correlation
among the objectives (e.g., toxicity-efficacy in clinical tri-
als) or observable features that characterize each item (e.g.,
chip area) and design parameters in chip design (Zuluaga
et al., 2013)).

To further our investigations, we adopt the well-studied
stochastic bandit model (Audibert et al., 2010; Lattimore
and Szepesvári, 2020; Drugan and Nowe, 2013) in the
multi-dimensional setting with dimension $d \in \mathbb{N}$. In this
decision-making game, the learner interacts sequentially
with an environment of $K \in \mathbb{N}$ arms. Each arm $i \in
[K] := \{1, \dots, K\}$ is associated with an unknown prob-
ability distribution over $\mathbb{R}^d$ denoted by $\nu_i \in \mathcal{D}$, where $\mathcal{D}$
is the set of possible distributions $\mathcal{D} \subseteq \mathcal{P}(\mathbb{R}^d)$, and having
an unknown finite mean $\mu_i := (\mu_i(c))_{c \in [d]} \in \mathbb{R}^d$, where
$\mu_i(c) := \mathbb{E}_{X \sim \nu_i}[X](c)$ denotes the mean of the objective $c$
for the arm $i$. A bandit instance is uniquely characterized
by its vector of distributions $\boldsymbol{\nu} := (\nu_i)_{i \in [K]} \in \mathcal{D}^K$
admit-
ting $\boldsymbol{\mu} := (\mu_i)_{i \in [K]} \in \mathcal{M}$ as its matrix of means, where
$\mathcal{M} \subseteq \mathbb{R}^{K \times d}$ is the set of possible vectors of means.

We consider the set $\mathcal{D} = \{\mathcal{N}(\lambda, \Sigma) \mid \lambda \in \mathbb{R}^d\}$ of Gaussian distributions with known covariance matrix $\Sigma$. $\Sigma$ models the correlation between objectives (e.g., toxicity-efficacy in dose-finding trials). To model the dependency between the arms (e.g. treatments having similar active ingredients), we consider the linear setting (Soare et al., 2014; Degenne et al., 2020) in dimension $h \in \mathbb{N}$, where $\boldsymbol{\mu}$ is fully characterized by the set of arms vectors $\mathcal{A} := \{a_i\}_{i \in [K]} \subseteq \mathbb{R}^h$ and the regression matrix $\boldsymbol{\theta} \in \Theta$, where $\Theta \subseteq \mathbb{R}^{h \times d}$ is the set of possible regression matrices, namely $\mathcal{M} := \{\boldsymbol{\mu} \in \mathbb{R}^{K \times d} \mid \exists \boldsymbol{\theta} \in \Theta, \boldsymbol{\mu} = \mathcal{A}\boldsymbol{\theta}\}$ where $\mathcal{A} = (a_i)_{i \in [K]} \in \mathbb{R}^{K \times h}$. We will use $i \in [K]$ and $a \in \mathcal{A}$ to denote arms and $\boldsymbol{\mu}$ and $\boldsymbol{\theta}$ to denote means. The above setting encompasses two well-studied models: *unstructured multi-dimensional* ($h = K$ and $\mathcal{A} = I_K$) and *linear one-dimensional* ($d = 1$).

Proceedings of the 28th International Conference on Artificial In-
telligence and Statistics (AISTATS) 2025, Mai Khao, Thailand.
PMLR: Volume 258. Copyright 2025 by the author(s).

**Pareto Set Identification** We focus on Pareto set identifi-
cation (PSI) for *transductive* linear bandits, in which there
exists a finite set of answers $\mathcal{Z} \subseteq \mathbb{R}^h$ which can be dif-
ferent from the set of arms A (Fiez et al., 2019; Li et al., 2024). For example, the treatments of interests Z might be too numerous (e.g. A ⊆ Z ) or too costly (e.g. A ∩ Z =  ) compared to the treatments A that could be administered during clinical trials. Given an answer z ∈ Z , its vector of means is denoted by µ$_{z}$ := θ $^{⊤}$z ∈ R $^{d}$. In that task, the goal of the learner is to identify the set of answers whose means are not uniformly worse coordinate-wise than an- other, known as the Pareto set and denoted as S $^{∗}$( θ ) ⊆ Z (or S ∗ when θ is clear from the context). The Pareto set contains the answers that satisfy optimal trade-offs in the objectives. The linear setting is the case Z = A .

An answer z ∈ Z is said to be Pareto dominated by an answer x ∈ Z , which we denote by µ$_{z}$ ≺ µ$_{x}$ or z ≺ x , if

$$
\forall c \in [d], \mu_z(c) \le \mu_x(c) \text{ and } \exists c \in [d], \mu_z(c) < \mu_x(c).
$$

The Pareto set of a matrix of means λ ∈ R h × d is the set of answers that are not Pareto dominated, i.e.

$$
S^*(\lambda) := \{z \in \mathcal{Z} \mid \mathbb{1}[x \in \mathcal{Z} \setminus \{z\}], \lambda_z \prec \lambda_x\}.
$$

In the one-dimensional case ( d = 1), we recover best an- swer identification (BAI) since the Pareto set reduces to the set of best answers, i.e. S $^{∗}$( λ ) = argmax$_{z}$$_{∈}$$_{Z}$ λ$_{z}$ .

**Identification Strategy** At each time t , the learner chooses an arm a$_{t}$ ∈ A based on the observations previously collected and obtains a sample X$_{t}$ ∈ R $^{d}$, random variable with conditional distribution ν$_{a}$$_{t}$ given a$_{t}$ . It then proceeds to the next stage. An algorithm for the learner in this interaction should specify a sam- pling rule that determines a$_{t}$ based on previously ob- served samples and some exogenous randomness. For- mally, a$_{t}$ is F$_{t}$ -measurable with the σ -algebra F$_{t}$ := σ ( U$_{1}$, a$_{1}$, X$_{1}$, · · · , a$_{t}$$_{−}$$_{1}$, X$_{t}$$_{−}$$_{1}$, U$_{t}$ ) , called history before time t , where U$_{t}$ ∼ U ([0 , 1]) materializes the possible in- dependent randomness used by the algorithm at time t . The empirical allocation over arms is N$_{t}$ := ( N$_{t,a}$ )$_{a}$$_{∈}$$_{A}$ where N$_{t,a}$ := ∑ s ∈ [ t $_{−}$1] 1 ( a$_{s}$ = a ) and N$_{t}$ t − 1 ∈ △$_{K}$ := { w ∈ R K + | ∑ a ∈ A w$_{a}$ = 1 } where △$_{K}$ denotes the probability simplex of dimension K − 1 .

As the learner aims at identifying S $^{∗}$( θ ) , its algorithm should include a recommendation rule . At time t , the agent recommends a candidate answer ̂ S$_{t}$ ⊆ Z for the Pareto set before pulling arm a$_{t}$ , therefore ̂ S$_{t}$ is F$_{t}$ -measurable.

**Fixed-confidence PSI** There are several ways to evaluate the performance of a PSI algorithm. The two major theo- retical frameworks are the fixed-confidence setting (Even- Dar et al., 2006; Jamieson and Nowak, 2014; Garivier and Kaufmann, 2016), which will be the focus of this paper, and the fixed-budget setting (Audibert et al., 2010; Gabillon et al., 2012). In the fixed-confidence setting (Kone et al., 2023; Crepon et al., 2024), the agent aims at minimizing

the number of samples used to identify S $^{∗}$( θ ) with confi- dence 1 − δ ∈ (0 , 1) . In the fixed-budget setting (Kone et al., 2024), the objective is to minimize the probability of misidentifying S $^{∗}$( θ ) with a fixed number of samples.

In the fixed-confidence setting, the learner should define a stopping rule that is a stopping time for the filtration ( F$_{t}$ )$_{t}$. The sample complexity of an algorithm corresponds to its stopping time τ$_{δ}$ , which counts the number of rounds be- fore termination. An algorithm is said to be δ -correct on the problem class D K with a set of regression matrices Θ if its probability of stopping and not recommending a correct answer is upper bounded by δ , i.e. P$_{ν}$ ( τ$_{δ}$ < + ∞ , ̂ S$_{τ}$$_{δ}$ ̸ = S $^{∗}$( θ )) ≤ δ for all instances ν ∈ D K having regression matrix θ ∈ Θ . A fixed-confidence PSI algorithm is judged based on its expected sample complexity E$_{ν}$ [ τ$_{δ}$ ] , i.e., the expected number of samples collected before it stops and returns a correct answer with confidence 1 − δ . The learner should design a δ -correct algorithm minimizing E$_{ν}$ [ τ$_{δ}$ ] .

**Notation** For any w ∈ R K $_{+}$, let V$_{w}$ := ∑ a ∈ $_{A}$w$_{a}$ aa $^{⊤}$be the design matrix, which is symmetric and positive semi- definite, and definite if and only if Span( { a ∈ A | w$_{a}$ ̸ = 0 } ) = R $^{h}$. For any symmetric positive semi-definite matrix V , we define the semi-norm ‖ x ‖$_{V}$ := √ x $^{⊤}$V x . It is a norm if V is positive definite. ‖‖ A ‖‖ is the operator norm of A . Let A ⊗ B denote the Kronecker product of A , B and let vec ( A ) denote the concatenation of the columns of A .

**Lower Bound** A δ -correct algorithm should distinguish θ from all the instances λ ∈ Θ having a different Pareto set. To better disentangle the structure induced by PSI from the underlying structure Θ, we define the set of alternative instances as Alt( S $^{∗}$) := { λ ∈ R h × d | S $^{∗}$( λ ) ̸ = S $^{∗}$} (i.e. without Θ). The requirement to distinguish θ from Θ ∩ Alt( S $^{∗}$) leads to a lower bound on the expected sample complexity on any instance (Garivier and Kaufmann, 2016; Garivier et al., 2019; Crepon et al., 2024).

**Lemma 1.** An algorithm which is δ -correct on all problems in D K satisfies that, for all ν ∈ D K with regression matrix θ ∈ Θ, E$_{ν}$ [ τ$_{δ}$ ] ≥ T $^{∗}$( θ ) log(1 / (2 . 4 δ )) where T $^{∗}$( θ ) is a characteristic time whose inverse is defined as

$$
2T^*(\theta)^{-1} := \sup_{w \in \triangle_K} \inf_{\lambda \in \Theta \cap \text{Alt}(S^*(\theta))} \|\text{vec}(\theta - \lambda)\|_{\Sigma^{-1} \otimes V_w}^2,
$$

and its maximizer set of optimal allocations is w $^{∗}$( θ ) .

We say that an algorithm is asymptotically optimal if its sample complexity matches that lower bound, namely if lim sup$_{δ}$$_{→}$$_{0}$ E$_{ν}$ [ τ$_{δ}$ ] / log(1 /δ ) ≤ T $^{∗}$( θ ) .

1.1 Algorithms

We use the ξ -regularized least-square estimator for θ , i.e. ̂ θ$_{t}$ := ( V$_{N}$$_{t}$ + ξI$_{h}$ ) − 1 ∑ s ∈ [ t $_{−}$1] a$_{s}$X s T with ξ ≥ 0 . Given
the known covariance Σ for the objectives, we use the ξ-regularized empirical covariance Σ_t := Σ⊗(V_N_t+ξI_h)^-1. We recommend the empirical Pareto set ̂S_t := S^*(θ_t).

**Stopping Rules** Before designing a sampling rule matching the asymptotic lower bound, one should specify a good stopping rule. Elimination-based (Even-Dar et al., 2006; Karnin et al., 2013) and gap-based (Kalyanakrishnan et al., 2012) stopping rules are sub-optimal in their δ-dependency. Hence, they fail to reach asymptotic optimality even for known w^*(θ). The well-studied Chernoff stopping times (Garivier and Kaufmann, 2016) use the generalized loglikelihood ratio (GLR) statistic. The GLR stopping rule is defined as τ^GLR_δ := inf{t | GLR(t) > β(t-1, δ)} where β is a threshold. The ξ-regularized GLR statistic is

$$2\text{GLR}(t) := \inf_{\lambda \in \Theta \cap \text{Alt}(\hat{S}_t)} \|\text{vec}(\hat{\theta}_t - \lambda)\|_{\Sigma_t^{-1}}^2. \quad (1)$$

Provided β is well chosen, the GLR stopping rule ensures δ-correctness regardless of the sampling rule. Moreover, combining a well-chosen sampling rule with the GLR stopping rule yields an asymptotically optimal algorithm.

Due to its δ-correctness and simplicity, the GLR stopping rule has become the standard choice. However, in some specific pure exploration problems, the computational cost of the GLR statistic becomes a major bottleneck. PSI for transductive linear BAI (d = 1), the computational cost of (1) heavily depends on Θ, and there are no procedure for general Θ. While there is a closed form solution in $O(h^2|\mathcal{Z}|)$ when Θ = $\mathbb{R}^h$, a more involved one-dimensional optimization procedure should be solved $|\mathcal{Z}|$ times when Θ is a ball (Degenne et al., 2020). In the unstructured multi-dimensional setting, to the best of our knowledge, computing (1) is only tractable for the setting with independent objectives, i.e. Σ diagonal, $\mathcal{Z} = \mathcal{A}$, h = K, $\mathcal{A} = I_K$ and $\Theta = \mathbb{R}^{K \times d}$. Crepon et al. (2024) proposed the best-known procedure in that restrictive setting, which requires to solve $O(Kd^3|\hat{S}_t|^d)$ convex problems at each round. Their computationally costly procedure is difficult to extend to correlated objectives or structured settings.

We introduce the posterior sampling (PS) stopping rule. Based on at most $M(t-1, \delta)$ independent realizations from a posterior distribution inflated by $c(t-1, \delta)$, it stops when

$$\tau_{\delta}^{\text{PS}} := \inf\{t \mid \forall m \in [M(t-1, \delta)], \theta_t^m \notin \Theta \cap \text{Alt}(\hat{S}_t)\}, \quad (2)$$

with $\text{vec}(\theta_t^m - \hat{\theta}_t) | \mathcal{F}_t \sim \mathcal{N}(0_{hd}, c(t-1, \delta)\Sigma_t)$ for all $m \in [M(t-1, \delta)]$. For precise choice of $M(t, \delta)$ and $c(t, \delta)$ to ensure δ-correctness, we refer the reader to Section 2.1. The PS stopping rule allows tackling structured settings with correlated objectives and has a lower computational cost than the GLR stopping rule.

**Sampling Rules** Given a stopping rule, the sampling rule should make it stop as soon as possible. While gap-based sampling rules will be sub-optimal in their asymptotic allocation, the asymptotic optimality of Track-and-Stop (Garivier and Kaufmann, 2016) will come at the cost of a computational intractability since it computes $w_t \in w^*(\hat{\theta}_t)$ at time t. The game-based approach came from seeing the lower bound as the solution of a two-player game (Degenne et al., 2019). Using two no-regret learning algorithms against each other yields a saddle-point algorithm that sequentially approximates $T^*(\theta)^{-1}$. The popularized instance uses the best response as min learner, i.e.

$$\lambda^{\text{BR}} : \omega \mapsto \underset{\lambda \in \Theta \cap \text{Alt}(\hat{S}_t)}{\operatorname{argmin}} \|\text{vec}(\hat{\theta}_t - \lambda)\|_{\Sigma^{-1} \otimes (V_\omega + \xi I_h)}^2, \quad (3)$$

whose computational cost is the same as the GLR statistic (1). As for the PS stopping rule, we rely on an inflated posterior sampling (PS) learner for the min learner. Therefore, our algorithm can tackle structured settings with correlated objectives and has a low computational cost.

## 1.2 Contributions

As main contribution, we propose the PSIPS algorithm, which is the first computationally efficient algorithm for transductive linear PSI. PSIPS builds on posterior sampling in both the PS stopping rule and the min learner of the game-based sampling rule. By removing the Oracle calls to (1) or (3), PSIPS deals with the transductive linear PSI structure in a computationally efficient way.

For the PS stopping rule and regardless of the sampling rule, we exhibit choices of $M(t, \delta)$ and $c(t, \delta)$ ensuring δ-correctness in the unstructured setting with independent or correlated objectives and in transductive linear BAI ($d = 1$ and $\Theta = \mathbb{R}^h$). When $\lim_{\delta \to 0} \frac{c(t, \delta) \log M(t, \delta)}{\log(1/\delta)} \le 1$ (satisfied by our choices), PSIPS is shown to be asymptotically optimal for transductive linear PSI (Theorem 1). From a Bayesian perspective, the posterior probability that PSIPS misidentifies the Pareto set decays exponentially fast (as a function of t) with the optimal rate $T^*(\theta)$ (Theorem 2). Our experiments on both real-world and synthetic instances showcase the superior performance of our algorithm both in terms of sample complexity and computational cost.

## 1.3 Related Work

Pioneering the PSI problem for bandits, Auer et al. (2016) proposed a δ-correct algorithm based on uniform sampling with an accept/reject mechanism. They proved a high-probability lower bound on the sample complexity of any δ-correct algorithm for PSI, essentially scaling as $H(\mu) \log(1/\delta)$ with $H(\mu) := \sum_{i \in [K]} \Delta_i^{-2}$ where $\Delta_i$'s are PSI's “sub-optimality” gaps introduced therein. The sample complexity of the proposed algorithm is
$\mathcal{O}(H(\mu) \log(Kd \log(H(\mu))/\delta))$. Kone et al. (2023) generalized the LUCB algorithm (Kalyanakrishnan et al., 2012) to the PSI setting, proving guarantees similar to those of Auer et al. (2016). Still in the unstructured setting and for $\Sigma = \sigma^2 I_d$, Crepon et al. (2024) proposed a $\delta$-correct gradient-based algorithm. Their sampling rule requires computing a (super)-gradient of $N_t \mapsto \text{GLR}(t)$, whose per-round computational cost is $\mathcal{O}(Kd^3|\hat{S}_t|^d)$. The GLR stopping rule is obtained by solving $\mathcal{O}(Kd^3|\hat{S}_t|^d)$ convex problems per round. This gradient computation procedure does not apply to the non-isotropic case or the structured setting. For fixed-budget PSI, Kone et al. (2024) proposed an algorithm whose error probability is upper bounded by $\mathcal{O}(\exp(-T/(H(\mu) \log K)))$. The authors showed that up to the log K terms and some constants, this is tight on a set of non-trivial instances.

Gaussian processes were used to study PSI. Each arm has a feature whose mean is estimated by Gaussian process regression. Zuluaga et al. (2013, 2016) introduced a racing algorithm with correctness guarantees. The linear setting is also addressed by Kim et al. (2025); Kone et al. (2025), who introduced PSI algorithms leveraging G-optimal design approaches (Fiez et al., 2019). They proved gap-based guarantees comparable to those in Auer et al. (2016), which remain unaffected by off-diagonal correlation terms. Although efficient in practice, these approaches are known to be sub-optimal, in particular when $\delta$ is small.

Other multi-objective problems have been studied. Ararat and Tekin (2023) introduced the identification of the non-dominated set of any cone-induced partial order, of which PSI is a special case. The authors proposed an extension of the algorithm of Auer et al. (2016). In the fixed-budget setting, Katz-Samuels and Scott (2018) aims at identifying the arms belonging to a given polyhedron. For multi-objective regret minimization, we refer to Drugan and Nowe (2013); Xu and Klabjan (2023).

In the pure exploration literature, there is a surge of interest in algorithms based on posterior sampling. This literature aims at extending the success of Thompson Sampling (TS) for regret minimization (Thompson, 1933; Kaufmann et al., 2012; Agrawal and Goyal, 2013). Russo (2016) proposed the Top Two TS (TTTS) sampling rule for BAI and showed posterior contraction at the optimal rate. Having only Bayesian guarantees, TTTS is not paired with a stopping rule. Shang et al. (2020) considered a variant of the Top Two algorithm for BAI. They propose a Bayesian stopping rule that requires computing the posterior probability for an arm's optimality, which is computationally inefficient. In combinatorial pure exploration (a subcase of our setting), the TS-Explore algorithm (Wang and Zhu, 2022) is the first to leverage posterior samples in the sampling and the stopping rules. While their stopping rule is similar to the PS stopping rule defined in (2), the authors use a gap-based sampling rule that is asymptotically sub-optimal. In

**Algorithm 1: PSIPS**

**Input:** regularization $\xi \ge 0$, budget $M$ and inflation $c$ functions, exploration allocation $\omega_{\text{exp}}$ and rate $\alpha > 0$, inflation rate $\eta_{\lambda}$, AdaHedge learner denoted by $\mathcal{L}^A$; Get $(Z_1, V_1)$ and $\hat{\theta}_1 = V_1^{-1}Z_1$ and $\Sigma_1 = \Sigma \otimes V_1^{-1}$; for $t \ge 1$ **do**

Get $\hat{S}_t = S^*(\hat{\theta}_t)$;
Set $m = 0, m_t = +\infty$ and $m_{t,\delta} = +\infty$;
**while** $\max\{m_t, m_{t,\delta}\} = +\infty$ **do**
  Set $m \leftarrow m + 1$ and get $v_t^m \sim \mathcal{N}(0_{hd}, \Sigma_t)$;
  // Stopping Rule
  **if** $m_{t,\delta} = +\infty$ **then**
    $\text{vec}(\theta_t^m) = \text{vec}(\hat{\theta}_t) + \sqrt{c(t-1, \delta)}v_t^m$;
    **if** $\theta_t^m \in \Theta \cap \text{Alt}(\hat{S}_t)$ **then** $m_{t,\delta} \leftarrow m$;
    **else if** $m \ge M(t-1, \delta)$ **then break** and
    **return** $\hat{S}_t$;
  **end**
  // Min Learner
  **if** $m_t = +\infty$ **then**
    $\text{vec}(\lambda_t^m) = \text{vec}(\hat{\theta}_t) + \eta_{\lambda}^{-1/2}v_t^m$;
    **if** $\lambda_t^m \in \Theta_t \cap \text{Alt}(\hat{S}_t)$ **then** $m_t \leftarrow m$;
  **end**
  **end**
  Get $\omega_t$ from learner $\mathcal{L}^A$ and set $\lambda_t = \lambda_t^{m_t}$;
  Set $\tilde{\omega}_t = (1 - \gamma_t)\omega_t + \gamma_t\omega_{\text{exp}}$ with $\gamma_t = t^{-\alpha}$;
  Get arm $a_t \sim \tilde{\omega}_t$ and collect $X_t \sim \nu_{a_t}$;
  Feed gain $g_t(\omega) = \|\text{vec}(\hat{\theta}_t - \lambda_t)\|_{\Sigma^{-1} \otimes V_\omega}^2$ to $\mathcal{L}^A$;
  Update $\hat{\theta}_{t+1} = V_{t+1}^{-1}Z_{t+1}$ and $\Sigma_{t+1} = \Sigma \otimes V_{t+1}^{-1}$
  with $Z_{t+1} = Z_t + a_t X_t^\top$ and $V_{t+1} = V_t + a_t a_t^\top$;
**end**

transductive linear BAI (subcase of our setting), the PEPS algorithm (Li et al., 2024) is a game-based algorithm using posterior sampling for the min learner. PEPS relies on phases to tune the learning rates that depend on an upper bound on the stochastic losses. PEPS achieves the optimal convergence rate of the posterior, yet it lacks a stopping rule and fixed-confidence or fixed-budget guarantees.

## 2 PSIPS ALGORITHM

We propose the PSIPS (PSI with Posterior Sampling) algorithm for PSI in the transductive linear setting with correlated objectives. PSIPS combines the PS stopping rule and the game-based sampling rule using a PS min learner.

### 2.1 The Posterior Sampling (PS) Stopping Rule

We introduce the posterior sampling (PS) stopping rule. To specify the PS stopping rule, a budget function $M: \mathbb{N} \times (0, 1) \to \mathbb{R}_+$ and an inflation function $c: \mathbb{N} \times (0, 1) \to$
$\mathbb{R}_+$ are given. The PS stopping rule defined in (2) stops when $M(t-1, \delta)$ independent realizations from a posterior distribution inflated by $c(t-1, \delta)$ agrees with the evidence suggesting that $S^*(\theta) = \hat{S}_t$. Conditioned on $\mathcal{F}_t$, let $(v_t^m)_{m \in [M(t-1, \delta)]}$ be i.i.d. draws from the centered posterior distribution $\Pi_t := \mathcal{N}(0_{hd}, \Sigma_t)$. For all $m \in [M(t-1, \delta)]$, let $\mathrm{vec}(\theta_t^m) := \mathrm{vec}(\hat{\theta}_t) + \sqrt{c(t-1, \delta)}v_t^m$. Then,

$$ \tau_{\delta}^{\mathrm{PS}} := \inf\{t \mid \forall m \in [M(t-1, \delta)], \theta_t^m \notin \Theta \cap \mathrm{Alt}(\hat{S}_t)\}. $$

When $\tau_{\delta}^{\mathrm{PS}} < +\infty$, we recommend $\hat{S}_{\tau_{\delta}^{\mathrm{PS}}} := S^*(\hat{\theta}_{\delta}^{\mathrm{PS}})$. When $t < \tau_{\delta}^{\mathrm{PS}}$, let $m_{t,\delta} := \inf\{m \mid \theta_t^m \in \Theta \cap \mathrm{Alt}(\hat{S}_t)\}$. Intuitively, $\theta_t^{m,t,\delta}$ is a randomized approximation of the best-response Oracle $\lambda^{\mathrm{BR}}(N_t)$ as in (3).

**Computational Cost** To reduce the computational cost of PSIPS, we draw $(v_t^m)_m$ sequentially as the PS stopping condition is often infringed before $M(t, \delta)$ realizations are drawn (see Figure 6). We re-use the realizations $(v_t^m)_m$ in the PS min learner of our sampling rule with a different inflation parameter (see Section 2.2).

Compared to the Oracle call to (1), testing that $\theta_t^m \notin \Theta \cap \mathrm{Alt}(\hat{S}_t)$ has a lower computational cost. It scales as the sum of the costs of membership to $\Theta$ and to $\mathrm{Alt}(\hat{S}_t)^c$, which is at most $\mathcal{O}(dh|\hat{S}_t| \max\{|\hat{S}_t|, |\mathcal{Z}| - |\hat{S}_t|\})$ since

$$ \mathrm{Alt}(\hat{S}_t)^c = \bigcap_{(z,x) \in \hat{S}_t^2, x \neq z} \bigcup_{c \in [d]} \{\lambda \mid \langle E_{z,x}(c), \mathrm{vec}(\lambda) \rangle \ge 0\} \\ \cap \bigcap_{z \notin \hat{S}_t} \bigcup_{x \in \hat{S}_t} \{\lambda \mid \langle E_{x,z}(c), \mathrm{vec}(\lambda) \rangle \ge 0\}, \quad (4) $$

$$ \text{where } E_{z,x}(c) = e_c \otimes (z-x) \text{ and } e_c = (\mathbb{1}_{\{c' = c\}})_{c' \in [d]}. $$

To update the candidate answer, we check whether $\hat{\theta}_t \in \mathrm{Alt}(\hat{S}_{t-1})^c$, in which case $\hat{S}_t = \hat{S}_{t-1}$. Otherwise, we compute $\hat{S}_t = S^*(\hat{\theta}_t)$. While a naive implementation is at most in $\mathcal{O}(dh|\mathcal{Z}|^2)$, Kung et al. (1975) proposed an algorithm having a cost scaling as $\mathcal{O}(h|\mathcal{Z}|(\log|\mathcal{Z}|)^{\max\{1,d-2\}})$.

**Correctness** Lemma 2 exhibits choices of budget $M(t, \delta)$ and inflation $c(t, \delta)$ ensuring $\delta$-correctness in the unstructured setting with independent or correlated objectives and in transductive linear BAI ($d=1$ and $\Theta = \mathbb{R}^h$). Letting $X \sim \mathcal{N}(0, 1)$, we denote by $R(x) := \frac{\mathbb{P}(X>x)}{f_X(x)}$, the Mills ratio (Mills, 1926) of $X$, with $f_X$, the density of $X$.

**Lemma 2.** Let $\delta \in (0, 1)$, $s > 1$, $\zeta$ be the Riemann $\zeta$ function. Define $r(\delta, n) := \left(\frac{1}{\sqrt{2\pi}} R\left(\sqrt{\frac{2}{n}} \log(1/\delta)\right)\right)^n$. Let $\beta(t, \delta)$ be an anytime upper bound on $\frac{1}{2} \|\theta - \theta_t\|_{\Sigma_t^{-1}}^2$ with probability at least $1 - \delta$, as in Lemma 3. Regardless of the sampling rule, the PS stopping rule with $c(t, \delta) = \beta(t, \frac{\delta}{2}) / \log \frac{1}{\delta}$ and $M(t, \delta) = \left\lfloor \frac{\log(2t^2 \zeta(s)/\delta)}{\delta q(t, \delta)} \right\rfloor$ ensures that the algorithm is $\delta$-correct for any $\delta \in (0, 1)$,

1) when $\Theta = \mathbb{R}^{K \times d}$, $\mathcal{Z} = \mathcal{A}$, $h = K$, $\mathcal{A} = I_K$, by taking

$q(t, \delta) = \min\{r(\delta, d), r(\delta, d + |\hat{S}_{t+1}|)\}$ for $\Sigma$ diagonal, and otherwise $q(t, \delta) = \det(\Sigma\bar{\sigma})^{-1/2} \min\{r(\delta^{\frac{d\Sigma}{d}}, d)$, $r(\delta^{\frac{d\Sigma+|\hat{S}_{t+1}|}{d+|\hat{S}_{t+1}|}}, d + |\hat{S}_{t+1}|)\}$ with $\bar{\sigma} = \|\Sigma^{-1}\|$ and $d_{\Sigma} = \|1_d\|_{(\Sigma\bar{\sigma})^{-1}}^2$.

2) when $d=1$ and $\Theta = \mathbb{R}^h$, by taking $q(t, \delta) = r(\delta, 1)$. The above choices satisfy $\limsup_{\delta \to 0} \frac{c(t, \delta) \log M(t, \delta)}{\log(1/\delta)} \le 1$.

Lemma 2 does not propose choices of $(M, c)$ for transductive linear PSI with general $\Theta$. In Section 3.1.1, our proof sketch highlights the challenge arising due to the structure.

## 2.2 Game-based Sampling Rule

We introduce a game-based sampling rule (Degenne and Koolen, 2019) using a PS min learner. By combining a max learner playing $\omega_t$ and a min learner playing $\lambda_t$, it yields a saddle-point algorithm which approximates $T^*(\theta)^{-1}$.

**Initialization** In the unstructured setting, we pull each arm once and observe $X_i \sim \nu_i$ for all $i \in [K]$. We take $\xi = 0$ and set $(Z_1, V_1) = (X_1, I_K)$ where $X_1 = (X_i^T)_{i \in [K]}$. In the structured setting, there is no initial pull of arms. We use $\xi > 0$ and set $(Z_1, V_1) = (0_{h \times d}, \xi I_h)$.

**Max Learner** As in Degenne and Koolen (2019), we opt for AdaHedge (De Rooij et al., 2014) as the max learner. We add forced exploration by mixing the played $\omega_t$ with an exploration allocation $\omega_{\mathrm{exp}} \in \Delta_K$. Formally, we pull $a_t \sim \tilde{\omega}_t$ with $\tilde{\omega}_t := (1 - \gamma_t)\omega_t + \gamma_t\omega_{\mathrm{exp}}$ where $\gamma_t = 1/t^\alpha$ with $\alpha \in (0, 1)$. The allocation $\omega_{\mathrm{exp}}$ should be chosen such that $\lambda_{\mathrm{min}}(V_{\omega_{\mathrm{exp}}}) > 0$. For example, we can use a uniform allocation on a set of arms spanning $\mathbb{R}^h$ or the G-optimal design (Li et al., 2024). Forced exploration ensures that $\hat{S}_t$ converges to $S^*(\theta)$ despite the initial fluctuation of the min learning space $\Theta \cap \mathrm{Alt}(\hat{S}_t)$.

**Min Learner** As in Li et al. (2024), we propose a PS min learner. The PS min learner draws independent realization from a posterior distribution inflated by $\eta_t > 0$ until one disagrees with $\hat{S}_t$. Let $(v_t^m)_m$ be i.i.d. draws from $\Pi_t$. For all $m \ge 1$, let $\mathrm{vec}(\lambda_t^m) := \mathrm{vec}(\hat{\theta}_t) + \eta_t^{-1/2}v_t^m$. Then,

$$ \lambda_t := \lambda_t^{m_t} \text{ with } m_t = \inf\{m \mid \lambda_t^m \in \Theta_t \cap \mathrm{Alt}(\hat{S}_t)\}, \quad (5) $$

where $\Theta_t := \Theta$ when $\Theta$ is bounded, and $\Theta_t$ is a bounded confidence region otherwise. Equivalently, we could draw $\mathrm{vec}(\lambda_t)$ from the distribution $\mathcal{N}(\mathrm{vec}(\hat{\theta}_t), \eta_t^{-1/2}\Sigma_t)$ truncated to $\Theta_t \cap \mathrm{Alt}(\hat{S}_t)$. The inflation $\eta_t$ is chosen as an upper bound on the magnitude of the stochastic loss. We refer the reader to Appendix D for more details on how $\eta_t$ and $\Theta_t$ are defined sequentially.

**Computational Cost** At time $t < \tau_{\delta}^{\mathrm{PS}}$, we re-use sequentially the realizations $(v_t^m)_{m \in [m_t, \delta]}$ drawn by the PS
stopping rule with a different inflation parameter. When $m_{t,\delta} < m_t$, we draw fresh realization sequentially. Despite the different inflations, $m_t$ is expected to be close to $m_{t,\delta}$, i.e. $\mathcal{O}(M(t, \delta))$ (see Figure 6). The computational cost of (5) is lower than a best-response Oracle to (1).

# 3 THEORETICAL GUARANTEES

We show that under a generic condition on $(c, M)$, which is satisfied in Lemma 2, the expected sample complexity of PSIPS is asymptotically optimal (Theorem 1). From a Bayesian perspective, the rate of decay for its posterior probability of misidentifying the Pareto set is shown to be asymptotically tight (Theorem 2). Theorems 1 and 2 hold for unstructured PSI ($\Theta = \mathbb{R}^{K \times d}$, $\mathcal{Z} = \mathcal{A}$, $h = K$, $\mathbf{A} = I_K$) and transductive linear PSI (bounded convex $\Theta$).

**Expected Sample Complexity** Theorem 1 shows that PSIPS is asymptotically optimal when using suitable choices of budget and inflation. In comparison, known upper bounds on $\mathbb{E}_{\nu}[\tau_{\delta}]$ were either sub-optimal (Auer et al., 2016), or restricted to the unstructured setting with independent objectives (Crepon et al., 2024) or transductive linear BAI ($d=1$). The proof is sketched in Section 3.1.2.

**Theorem 1.** Using budget $M$ and inflation $c$ such that $\limsup_{\delta \to 0} \frac{c(t, \delta) \log M(t, \delta)}{\log(1/\delta)} \le 1$, the PSIPS algorithm satisfies that $\limsup_{\delta \to 0} \mathbb{E}_{\nu}[\tau_{\delta}^{PS}]/\log(1/\delta) \le T^*(\theta)$ for all $\nu \in \mathcal{D}^K$ with regression matrix $\theta \in \Theta$, both for unstructured PSI ($\Theta = \mathbb{R}^{K \times d}$, $\mathcal{Z} = \mathcal{A}$, $h = K$, $\mathbf{A} = I_K$) and transductive linear PSI (bounded convex $\Theta$).

Lemma 2 gives choices of $(c, M)$ satisfying the above condition and ensuring $\delta$-correctness in unstructured PSI. Theorem 1 also holds on the set $\tilde{\mathcal{D}}$ of multi-variate $\Sigma$-sub-Gaussian, where $\kappa \in \tilde{\mathcal{D}}$ with mean $\lambda$ implies that $\mathbb{E}_{X \sim \kappa}[e^{u^T(X-\lambda)}] \le e^{\frac{1}{2}u^T\Sigma^{-1}u}$ for all $u \in \mathbb{R}^d$ (Denge and Perchet, 2016). This includes distributions with Bernoulli marginals or with bounded support. Optimality is only achieved for multi-variate Gaussian distributions.

**Posterior Probability of Misidentification** Theorem 2 shows that the posterior probability that PSIPS misidentifies the Pareto set decays exponentially fast (as a function of $t$) with a rate $T^*(\theta)$, which is shown to be asymptotically optimal by a lower bound. In comparison, known similar Bayesian guarantees were restricted to BAI ($d=1$) in the unstructured and structured settings (e.g. TTTS in Russo (2016) and PEPS in Li et al. (2024)).

**Theorem 2.** Let $\tilde{\Pi}_t := \mathcal{N}(\hat{\theta}_t, \Sigma \otimes V_{N_t}^{-1})$ be the posterior distribution under a flat Gaussian prior (without inflation). For all $\nu \in \mathcal{D}^K$ with regression matrix $\theta \in \Theta$, it almost surely holds that $\limsup_{t \to +\infty} -t^{-1} \log \mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(\Theta \cap \text{Alt}(S^*)) \le T^*(\theta)^{-1}$ for any algorithm, and PSIPS almost

surely satisfies that $\liminf_{t \to +\infty} -t^{-1} \log \mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(\Theta \cap \text{Alt}(S^*)) \ge T^*(\theta)^{-1}$, both for unstructured PSI ($\Theta = \mathbb{R}^{K \times d}$, $\mathcal{Z} = \mathcal{A}$, $h = K$, $\mathbf{A} = I_K$) and transductive linear PSI (bounded convex $\Theta$).

## 3.1 Proof Sketches

Before sketching the proofs of Lemma 2 and Theorem 1, we introduce the concentration event $\mathcal{E}_{\delta} := \bigcap_{t \in \mathbb{N}} \mathcal{E}_{t, \delta}$ with

$$ \mathcal{E}_{t, \delta} := \{ \|\text{vec}(\theta - \theta_t)\|_{\Sigma_t^{-1}}^2 \le 2\beta(t - 1, \delta) \}. \quad (6) $$

Lemma 3 in Appendix C gives choices of $\beta(t, \delta)$ such that $\mathbb{P}_{\nu}(\mathcal{E}_{\delta}^{\beta}) \le \delta$. They satisfy that $\lim_{\delta \to 0} \beta(\cdot, \delta)/\log(1/\delta) = 1$ and $\beta(t, \cdot) = +\infty \mathcal{O}(\log \log t)$. Using $\beta(t, \delta)$ in the GLR stopping rule yields $\delta$-correctness for any sampling rule.

### 3.1.1 Proof Sketch of Lemma 2

Under $\mathcal{E}_{\delta/2}$, the budget $M$ and the inflation $c$ are chosen to ensure $\delta$-correctness of the PS stopping rule, regardless of the sampling rule. Formally, we need to prove that

$$ \mathbb{P}_{\nu}(\mathcal{E}_{\delta/2} \cap \{\tau_{\delta}^{\text{PS}} < +\infty, \hat{S}_{\tau_{\delta}^{\text{PS}}} \neq S^*\}) \le \delta/2. $$

Let $\tilde{\Pi}_t := \mathcal{N}(\hat{\theta}_t, c(t-1, \delta)\Sigma_t)$. By union bound, the stopping in (2) and $1-x \le \exp(-x)$, it suffices to upper bound
$$ 1_{\mathcal{E}_{t, \delta/2} \cap \{\hat{S}_t \neq S^*\}} \exp \left( -M(t-1, \delta) \mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(\Theta \cap \text{Alt}(\hat{S}_t)) \right) $$
by $\frac{\delta}{2\zeta(s)(t-1)^s}$ since their sum is smaller than $\delta/2$. Therefore, we should lower bound $\mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(\Theta \cap \text{Alt}(\hat{S}_t))$ under the event $\mathcal{E}_{t, \delta/2} \cap \{\hat{S}_t \neq S^*\}$ to conclude the proof.

**Unstructured Setting** Having $\hat{S}_t \neq S^*$ implies that $\theta \in \text{Alt}(\hat{S}_t)$, see (4). Either (1) there exists $(i, j) \in \hat{S}_t$ with $i \neq j$ such that $\mu_i(c) < \mu_j(c)$ for all $c \in [d]$, and we define $\mathcal{J}_t = \{j\}$. Or (2) there exists $i \notin \hat{S}_t$ and $c \in [d] | \hat{S}_t|$ such that $\mu_j(c_j) < \mu_i(c_j)$ for all $j \in \hat{S}_t$, and $\mathcal{J}_t = \hat{S}_t$. Since $\Theta = \mathbb{R}^{K \times d}$, we can show that $1_{\hat{S}_t \neq S^*} \mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(\text{Alt}(\hat{S}_t)) \ge$

$$ \prod_{k \in \{i\} \cup \mathcal{J}_t} \mathbb{P}_{X \sim \mathcal{N}(0_d, \Sigma)} \left( X > \sqrt{\frac{N_{t,k}}{c(t-1, \delta)}} (\mu_k - \hat{\mu}_{t,k}) \right), $$

where $X > x$ denotes $X(c) > x(c)$ for all $c \in [d]$.

When $\Sigma$ is diagonal, we have $\mathbb{P}_{X \sim \mathcal{N}(0_d, \Sigma)}(X > x) = \prod_{c \in [d]} \mathbb{P}_{X \sim \mathcal{N}(0, \Sigma_{c,c})}(X > x(c))$. When $\Sigma$ is not diagonal, we derive a lower bound on $\mathbb{P}_{X \sim \mathcal{N}(0_d, \Sigma)}(X > x)$ for any vector $x \in \mathbb{R}^d$ (Lemma 7). To further lower bound those quantities, we introduce the ratio of the tail distribution to the density function for Gaussian, known as the Mills ratio (Mills, 1926). Under the event $\mathcal{E}_{t, \delta/2}$, we have
$N_{t,k} ||\mu_k - \hat{\mu}_{t,k}||_{\Sigma^{-1}} \le 2\beta(t-1, \delta/2)$. Using that the Mills ratio is non-increasing and log-convex, we obtain that

$$1_{\mathcal{E}_{t,\delta/2} \cap \{\hat{S}_t \neq S^*\}} \mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\mathrm{Alt}(\hat{S}_t)) \ge \delta q(t-1, \delta)$$

by taking $c(t, \delta) = \beta(t, \delta/2)/\log(1/\delta)$. This concludes the proof by considering $M(t, \delta) = \left[ \frac{\log(2t^* \zeta(s)/\delta)}{\delta q(t, \delta)} \right]$.

**Structured Setting** Both $\Theta$ and the arms $A \subseteq \mathbb{R}^h$ will introduce correlations between arms. Therefore, one cannot lower bound $\mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\Theta \cap \mathrm{Alt}(\hat{S}_t))$ by considering arms separately. Consequently, choosing $M$ and $c$ to ensure $\delta$-correctness for PSI in the transductive linear setting is a challenging open problem.

When $d=1$ (BAI) and $\Theta = \mathbb{R}^h$, we can show that $1_{\hat{S}_t \neq S^*} \mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\mathrm{Alt}(\hat{S}_t)) \ge \mathbb{P}_{X \sim \mathcal{N}(0,1)}(X > ||\mathrm{vec}(\hat{\theta}_t - \theta)||_{\Sigma^{-1}/\sqrt{c(t-1, \delta)}})$. Then, under $\mathcal{E}_{t,\delta/2}$, we conclude similarly using the Mills ratio properties.

**Technical Challenge** The $\delta$-correctness of the GLR stopping rule is obtained quite simply by concentration. We have GLR($t) \le \frac{1}{2} ||\mathrm{vec}(\hat{\theta}_t - \theta)||_{\Sigma^{-1}}^2 \le \beta(t-1, \delta)$ under $\mathcal{E}_{t,\delta} \cap \{\hat{S}_t \neq S^*\}$, hence $\mathbb{P}_{\nu}(\mathcal{E}_{\delta} \cap \{\tau_{\delta}^{\mathrm{GLR}} < +\infty, \hat{S}_{\tau_{\delta}^{\mathrm{GLR}}} \neq S^*\}) = 0$. In contrast, under a similar event, proving the $\delta$-correctness of the PS stopping rule requires to control the randomness of $\hat{\Pi}_t | \mathcal{F}_t$ by deriving anti-concentration results on $\mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\Theta \cap \mathrm{Alt}(\hat{S}_t))$.

### 3.1.2 Proof Sketch of Theorem 1

Studying the expected sample complexity of an algorithm using the PS stopping rule requires to control the randomness of $\hat{\Pi}_t | \mathcal{F}_t$ by deriving concentration results on $\mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\Theta \cap \mathrm{Alt}(\hat{S}_t))$ since a direct union bound yields that

$$\mathbb{P}_{\nu}(\tau_{\delta}^{\mathrm{PS}} > t) \le M(t-1, \delta) \mathbb{E}_{\nu}[\mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\Theta \cap \mathrm{Alt}(\hat{S}_t))]$$

Since $\mathrm{Alt}(\hat{S}_t)$ is a union of convex sets (Lemma 26), we use a Gaussian concentration result on convex sets (Lemma 27) for $\hat{\Pi}_t | \mathcal{F}_t$. This relates $\mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\Theta \cap \mathrm{Alt}(\hat{S}_t))$ to the GLR statistic defined in (1), namely we show that

$$\mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\Theta \cap \mathrm{Alt}(\hat{S}_t)) \le \alpha_0 \exp(-\mathrm{GLR}(t)/c(t-1, \delta)),$$

where $\alpha_0 \le |\mathcal{Z}|(|\mathcal{Z}| + d^{|\mathcal{Z}|})/2$ (Lemma 17). Once the event $\{\tau_{\delta}^{\mathrm{PS}} > t\}$ is linked to the GLR statistic, it suffices to lower bound GLR($t$) to conclude the proof. The rest of the proof would be conducted similarly when using the GLR stopping rule.

Studying the saddle-point convergence of our algorithm yields that, there exists $(\mathcal{E}_t)_{t \ge 1}$ and $T_0 \in \mathbb{N}$ such that for all $t > T_0$, when $\mathcal{E}_t$ holds, GLR($t$) $\ge (t-1)/T^*(\theta) - f(t)$

where $f(t) =_{+\infty} o(t)$ and $\sum_{t \in \mathbb{N}} \mathbb{P}(\mathcal{E}_t^c) = C_0 < +\infty$. Then, we have $\mathbb{E}_{\nu}[\tau_{\delta}^{\mathrm{PS}}] \le T_0 + C_0 +$

$$\sum_{t > T_0} \alpha_0 \exp \left( - \frac{t - 1 - T^*(\theta)f(t)}{T^*(\theta)c(t - 1, \delta)} + \log M(t - 1, \delta) \right).$$

Using that $\limsup_{\delta \to 0} \frac{c(t, \delta) \log M(t, \delta)}{\log(1/\delta)} \le 1$, a direct inversion of the above sum concludes the proof.

## 4 EXPERIMENTS

We evaluate the performance of PSIPS on real-world inspired and synthetic instances. As benchmarks, we consider the following PSI algorithms: APE (Kone et al., 2023), the gradient-based algorithm of Crepon et al. (2024) denoted as GAPSI, the oracle algorithm which samples arm following optimal weights, i.e $a_t \sim \omega^*(\theta)$, and round-robin uniform sampling (RR).

APE relies on confidence bounds to pull an arm at each round and to tailor its stopping rule. While APE can be extended to the structured setting, it does not exploit the correlation between objectives as its confidence intervals only consider the marginals' variance. GAPSI computes a supergradient of the GLR (1) and uses the GLR stopping rule. Similarly, GAPSI has no efficient implementation for correlated objectives or the structured setting. Since GAPSI is computationally expensive, we re-use the empirical results from Crepon et al. (2024).

In our experiments, we use the heuristics $c(t, \delta) = 1 + \frac{\log \log t}{\log(1/\delta)}$ and $M(t, \delta) = \frac{1}{\delta} \log \frac{t}{\delta}$. For a fair comparison, APE uses $\beta(t, \delta) = \log(1/\delta) + \log \log t$ in its bounds, hence improving its performance. We report the averaged results over 500 independent runs with boxplots or shaded areas for standard deviation. The observed empirical error is order of magnitude lower than $\delta$. Appendix J.3 contains supplementary experiments (e.g. higher $(K, d)$).

**Cov-Boost Trial** As prior work in PSI, we use the dataset from Munro et al. (2021) to simulate a bandit instance for PSI. The dataset consists of the average response of patients cohorts in a covid19 trial including 20 vaccine strategies. Among the indicators recorded to measure the efficacy of each strategy, following Kone et al. (2023); Crepon et al. (2024), we keep three of them: titres of neutralizing antibodies and immunoglobuline G), and the wild-type cellular response (cf Table 3). The ideal vaccine strategy would maximize all three indicators, but the average response for the considered metrics reveals a Pareto set of two vaccine strategies in the trial.

Figure 1 shows that PSIPS has a high variability of stopping time, which was expected due to the use of posterior sampling. While PSIPS outperforms uniform sampling, it performed on average slightly worse than APE and Oracle
<figure><img src="image_3.png" /><figcaption>**Figure 1:** Empirical stopping times on the covid19 experiment with $\delta = 0.01$ (left) and $\delta = 0.001$ (right).</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Figure 2:** Impact of the correlation $\rho$ on the stopping time.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Figure 4:** Empirical stopping time on random Gaussian (left) and Bernoulli (right) instances.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Figure 5:** Average runtime for the first *T* iterations in the covid19 experiment.</figcaption></figure>

<caption>**Figure 6:** Average number of per-round rejection samples $m_t, m_{t,\delta}$.</caption>

on the Cov-Boost instance. For $\delta = 0.1$, we reported an average sample complexity of 20456 for PSIPS compared to 17909 reported for GAPSI by Crepon et al. (2024). However, due to the high computational cost of their algorithm, we averaged its performance over 100 runs.

**Correlated Objectives** To assess the performance of PSIPS when the objectives are correlated (Σ not diagonal), we choose a Gaussian instance with five arms in dimension two (see Appendix J for the values). The covariance matrix Σ_ρ is chosen with unit variance and an off-diagonal correlation coefficient ρ ∈ (-1, 1): ρ close to 1 (resp. -1) means the two objectives are strongly positively (resp. negatively) correlated and ρ = 0 means independent objectives.

Figure 2 shows the sample complexity of PSIPS versus $\rho$, including GAPSI as heuristic. It reveals that PSIPS has a decreasing sample complexity for stronger (negative) correlation between objectives; reducing by up to factor 3 w.r.t the uncorrelated case ($\rho = 0$). Due to its asymptotic optimality, PSIPS inherits the properties of $T^*(\theta)$, which is most likely decreasing with negative $\rho$ on this specific instance. Both GAPSI and APE performance are independent of $\rho$.

**Robustness on Random Instances** To evaluate the robustness of PSIPS, we measure its performance on 250 randomly picked Bernoulli (marginals) and Gaussian instances with $K = 5$, $d = 2$ and $\Sigma = I_2/2$.

Figure 4 showcases the competitive performance of PSIPS, which remains good when used on sub-Gaussian instances.

**Structured Instance Network** on Chip (NoC, Almer et al. (2011); Zuluaga et al. (2013)) is a bi-objective optimization dataset designed for hardware development. The objective is to minimize two key performance criteria: energy consumption and runtime of NoC implementations. The dataset includes 259 designs, each characterized by four descriptive features, and its Pareto set comprises 4 arms (see Appendix J).

Figure 3 shows the superior performance of PSIPS on the structured instance as it can exploit the linear structure to reduce the sample complexity of PSI. We did not include RR as it was more than five times worse than PSIPS.

**Computational Cost** We evaluate the number of rejection samples used by PSIPS on a Gaussian instance with $\Sigma = I_2/2$ defined as $\mu_1 = (1, 1)^T$ and $\mu_i = R_{\pi/5}\mu_{i-1}$ for $i \in \{2, 3, 4, 5\}$ where $R_{\pi/5}$ is the $\pi/5$ rotation matrix. Without actually stopping, we record both $m_t$ and $m_{t,\delta}$ at each round, averaged over 1000 runs. We also report the cumulated runtime of PSIPS and APE on the covid19 experiment.

Figure 5 shows that the computational cost of PSIPS is comparable to APE, which is order of magnitudes smaller than GAPSI (see Figure 4 in Crepon et al. (2024)). Figure 6 reveals that, while finding an alternative is initially faster, more rejections are needed before finding an alternative when the posterior concentrates. It is precisely at this time that the PS stopping rule triggers.
# 5 PERSPECTIVES

We proposed the *PSIPS* algorithm for Pareto set identification in the transductive linear setting with correlated objectives. By leveraging posterior sampling in both the stopping and the sampling rules, *PSIPS* is a computationally efficient algorithm that deals with structure and correlation, without using costly oracle calls as existing algorithms. We show that *PSIPS* is asymptotically optimal both from a frequentist and Bayesian perspective. Moreover, *PSIPS* has competitive empirical performance.

While our choice of $c$ and $M$ ensures $\delta$-correctness of the PS stopping rule in the unstructured setting with independent or correlated objectives, we lack $\delta$-correctness guarantees in the structured setting. Even for transductive linear BAI ($d = 1$), we obtain $\delta$-correctness only when $\Theta = \mathbb{R}^h$. Therefore, it fails to account for the boundedness assumption, which is a key assumption to derive the upper bound on the expected sample complexity in the linear setting. To address this open problem, we need tight non-asymptotic lower bounds on the posterior probability of drawing a realization in $\Theta \cap \text{Alt}(\hat{S}_t)$.

Despite being a theoretically convenient distributional assumption, using Gaussian distributions with known covariance matrix is too restrictive for many applications. Therefore, generalizing our results to other classes of distributions is another interesting direction for future work. For example, when the covariance matrices are unknown and different for each arm, the estimation of the Pareto set is intertwined with estimating the correlation structure.

## Acknowledgements

Cyrille Kone is funded by an Inria/Inserm PhD grant. This work was conducted while Marc Jourdan was a PhD student in the Scool team of Inria Lille, partially supported by the THIA ANR program "AI.PhD@Lille". Emilie Kaufmann acknowledges the support of the French National Research Agency under the projects BOLD (ANR-19-CE23-0026-04) and FATE (ANR22-CE23-0016-01).

## References

S. Agrawal and N. Goyal. Thompson sampling for contextual bandits with linear payoffs. In *International conference on machine learning*. PMLR, 2013.

O. Almer, N. Topham, and B. Franke. A learning-based approach to the automated design of mpsoc networks. In *Proceedings of the 24th International Conference on Architecture of Computing Systems*. Springer-Verlag, 2011.

C. Ararat and C. Tekin. Vector optimization with stochastic bandit feedback. In *Proceedings of The 26th International Conference on Artificial Intelligence and Statistics*. PMLR, 2023.

J.-Y. Audibert, S. Bubeck, and R. Munos. Best arm identification in multi-armed bandits. In *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.

A. Baricz. Mills' ratio: Monotonicity patterns and functional inequalities. *Journal of Mathematical Analysis and Applications*, 2008.

Z. W. Birnbaum. An Inequality for Mill's Ratio. *The Annals of Mathematical Statistics*, 1942.

E. Crepon, A. Garivier, and W. M. Koolen. Sequential learning of the Pareto front for multi-objective bandits. In *Proceedings of The 27th International Conference on Artificial Intelligence and Statistics*, Proceedings of Machine Learning Research. PMLR, 2024.

S. De Rooij, T. Van Erven, P. D. Grünwald, and W. M. Koolen. Follow the leader if you can, hedge if you must. *J. Mach. Learn. Res.*, 2014.

R. Degenne. *Impact of structure on the design and analysis of bandit algorithms*. PhD thesis, 2019.

R. Degenne and W. Koolen. Pure exploration with multiple correct answers. In *Advances in Neural Information Processing Systems*. Curran Associates, Inc., 2019.

R. Degenne and V. Perchet. Combinatorial semi-bandit with known covariance. *Advances in Neural Information Processing Systems*, 2016.

R. Degenne, W. M. Koolen, and P. Ménard. Non-asymptotic pure exploration by solving games. *Advances in Neural Information Processing Systems*, 2019.

R. Degenne, P. Ménard, X. Shang, and M. Valko. Gamification of pure exploration for linear bandits. In *International Conference on Machine Learning*. PMLR, 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.

E. Even-Dar, S. Mannor, and Y. Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. *Journal of Machine Learning Research*, 2006.

T. Fiez, L. Jain, K. G. Jamieson, and L. Ratliff. Sequential experimental design for transductive linear bandits. *Advances in neural information processing systems*, 2019.

V. Gabillon, M. Ghavamzadeh, and A. Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. In *Advances in Neural Information Processing Systems*. Curran Associates, Inc., 2012.
A. Garivier and E. Kaufmann. Optimal best arm identification with fixed confidence. In *29th Annual Conference on Learning Theory*. PMLR, 2016.

A. Garivier, P. Ménard, and G. Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. *Mathematics of Operations Research*, 2019.

K. Jamieson and R. Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In *48th Annual Conference on Information Sciences and Systems (CISS)*, 2014.

C. Jennison and B. W. Turnbull. Group sequential tests for bivariate response: interim analyses of clinical trials with both efficacy and safety endpoints. *Biometrics*, 1993.

M. Jourdan, D. Rémy, and K. Emilie. Dealing with unknown variances in best-arm identification. In *Proceedings of The 34th International Conference on Algorithmic Learning Theory*. PMLR, 2023.

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*. Omni-press, 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.

E. Kaufmann, N. Korda, and R. Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In *International conference on algorithmic learning theory*. Springer, 2012.

W. Kim, G. Iyengar, and A. Zeevi. Learning the pareto front using bootstrapped observation samples. In *The 28th International Conference on Artificial Intelligence and Statistics*, 2025.

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*. PMLR, 2024.

C. Kone, E. Kaufmann, and L. Richert. Bandit pareto set identification in a multi-output linear model. In *The 28th International Conference on Artificial Intelligence and Statistics*, 2025.

J. Kuelbs, W. Li, and W. Linde. The gaussian measure of shifted balls. *Probability Theory and Related Fields*, 1994.

H. T. Kung, F. Luccio, and F. P. Preparata. On finding the maxima of a set of vectors. *J. ACM*, 1975.

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

Z. Li, K. Jamieson, and L. Jain. Optimal exploration is no harder than Thompson sampling. In *Proceedings of The 27th International Conference on Artificial Intelligence and Statistics*. PMLR, 2024.

D. Lu and W. V. Li. A note on multivariate gaussian estimates. *Journal of Mathematical Analysis and Applications*, 2009.

J. P. Mills. Table of the ratio: Area to bounding ordinate, for any portion of normal curve. *Biometrika*, 1926.

A.-P.-S. Munro, L. Janani, V. Cornelius, and et al. Safety and immunogenicity of seven COVID-19 vaccines as a third dose (booster) following two doses of ChAdOx1 nCov-19 or BNT162b2 in the UK (COV-BOOST): a blinded, multicentre, randomised, controlled, phase 2 trial. *The Lancet*, 2021.

D. Russo. Simple bayesian algorithms for best arm identification. In *29th Annual Conference on Learning Theory*. PMLR, 2016.

X. Shang, R. de Heide, P. Menard, E. Kaufmann, and M. Valko. Fixed-confidence guarantees for bayesian best-arm identification. In *Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics*. PMLR, 2020.

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

W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. *Biometrika*, 1933.

S. Wang and J. Zhu. Thompson sampling for ( combinatorial ) pure exploration. In *International Conference on Machine Learning*. PMLR, 2022.

M. Xu and D. Klabjan. Pareto regret analyses in multi-objective multi-armed bandit. In *Proceedings of the 40th International Conference on Machine Learning*. JMLR, 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 Sections 1, 2 and 3.**

(b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. **Yes, see Sections 2, 3 and 4, as well as Appendix J.**

(c) (Optional) Anonymized source code, with specification of all dependencies, including external libraries. **Yes, see Appendix J and the code attached in the supplementary materials.**

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

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

(b) Complete proofs of all theoretical results. **Yes, see Section 3.1 and Appendices C, D, F, G, H and I.**

(c) Clear explanations of any assumptions. **Yes, see Sections 1 and 3.**

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 Appendix J and the code attached in the supplementary materials.**

(b) All the training details (e.g., data splits, hyperparameters, how they were chosen). **Yes, see Appendix J and the code attached in the supplementary materials.**

(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 4 and Appendix J.**

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

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 4 and Appendix J.**

(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

The appendices are organized as follows:

* Notation are summarized in Appendix B.

* The $\delta$-correctness of the stopping rule is proven in Appendix C.

* Appendix D shows that the game-based sampling rule yields a saddle-point algorithm.

* In Appendix E, we prove some results related to the generalized likelihood and the posterior probability of error.

* The asymptotic upper bound on the expected sample complexity is proven in Appendix F.

* The convergence of the posterior distribution is proven in Appendix G.

* Appendix H gathers concentration results.

* Appendix I gathers existing and new technical results which are used for our proofs.

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

<table><caption>**Table 1:** Notation for the setting.</caption><tr><td>$K := |\mathcal{A}|$</td><td>Number of arms</td></tr><tr><td>$\Theta \subset \mathbb{R}^{h \times d}$</td><td>set of parameters</td></tr><tr><td>$\mathcal{A} \subset \mathbb{R}^h$</td><td>set of measurements (arms)</td></tr><tr><td>$\mathcal{Z} \subset \mathbb{R}^h$</td><td>set of items</td></tr><tr><td>$\mathbf{A} \in \mathbb{R}^{K \times h}$</td><td>matrix of features</td></tr><tr><td>$\theta \in \Theta$</td><td>true parameter of the instance</td></tr><tr><td>$\mu := \mathbf{A}\theta := (\mu_1 \dots \mu_K)^\top$</td><td>vector mean of each arm</td></tr><tr><td>$S^*(\theta)$</td><td>Pareto set of $\mathcal{Z}$</td></tr><tr><td>$D_\Theta := \max_{a \in \mathcal{A}} \max_{\theta, \theta'} \|\mathrm{vec}(\theta - \theta')\|_{\Sigma^{-1} \otimes_{aa} \Sigma}$</td><td>diameter of the means space</td></tr></table>

# B NOTATION

We recall some commonly used notation: the set of integers $[K] := \{1, \dots, K\}$, the complement $X^c$ and interior $\bar{X}$ and the closure $\bar{X}$ of a set $X$, the indicator function $1(X)$ of an event, the probability $P_\nu$ and the expectation $E_\nu$ under distribution $\nu$, Landau's notation $o$, $O$, $\Omega$ and $\Theta$, the $(K-1)$-dimensional probability simplex $\Delta_K := \{w \in \mathbb{R}_+^K | w \ge 0, \sum_{i \in [K]} w_i = 1\}$. $\zeta$ is the Riemann $\zeta$ function. When $\lambda$ is a matrix and $\pi$ is a distribution supported on vectors, we write $\lambda \sim \pi$ to denote $\mathrm{vec}(\lambda) \sim \pi$. When $M$ is a set of matrices $\mathrm{vec}(M) := \{\mathrm{vec}(m) | m \in M\}$.

While Table 1 gathers problem-specific notation, Table 2 groups notation for the algorithms.
<table><caption>**Table 2:** Notation for algorithms.</caption><tr><td>Alt(S)</td><td>set of parameters whose Pareto set is not S</td></tr><tr><td>S<sub>t</sub></td><td>pareto set of the empirical mean at time t</td></tr><tr><td>θ&#770;<sub>t</sub></td><td>(regularized) least-squares estimator of θ</td></tr><tr><td>a<sub>t</sub> ∈ A</td><td>measurement (arm) pulled at time t</td></tr><tr><td>V<sub>t</sub> := ξI<sub>h</sub> + V<sub>N,t</sub></td><td>design matrix after t iterations</td></tr><tr><td>a<sub>t</sub> ⊂ A</td><td>feature pulled at time t</td></tr><tr><td>L<sub>A</sub> := max<sub>a∈A</sub> ||a||<sub>2</sub></td><td>maximum feature norm</td></tr><tr><td>L<sub>*</sub> := 2 max<sub>a∈A</sub> ||a||<sub>V(ω<sub>exp</sub>)<sup>-1</sup></sub><sup>2</sup></td><td>squared feature norm due to forced exploration</td></tr><tr><td>L<sub>Θ</sub> := L<sub>M</sub> := max<sub>λ∈Θ</sub> max<sub>c∈[d]</sub> ||λe<sub>c</sub>||<sub>2</sub></td><td>maximum regression norm</td></tr><tr><td>a&#770; := Σ<sup>-1/2</sup> ⊗ a</td><td>extended feature (matrix)</td></tr><tr><td>V&#770;<sub>t</sub> := Σ<sup>-1</sup> ⊗ V<sub>t</sub></td><td>extended desing matrix</td></tr><tr><td>Λ<sub>t</sub> := Θ<sub>t</sub> ∩ Alt(̂S<sub>t</sub>)</td><td>truncated alternative space</td></tr><tr><td>π<sub>t</sub> := N(vec(θ<sub>t</sub>), η<sub>t</sub><sup>-1/2</sup>Σ<sub>t</sub>; Λ<sub>t</sub>)</td><td>Gaussian truncated to Λ<sub>t</sub></td></tr><tr><td>λ<sub>t</sub> ∼ π<sub>t</sub></td><td>strategy of the min player at time t</td></tr><tr><td>ω<sub>t</sub></td><td>strategy of the max player at time t</td></tr><tr><td>Δ<sub>min</sub></td><td>the minimum Pareto gap (Section D.1)</td></tr><tr><td>F<sub>t</sub> := σ(a<sub>1</sub>, y<sub>1</sub>, . . . a<sub>t+1</sub>, y<sub>t</sub>)</td><td>information gathered by the algorithm after t rounds</td></tr><tr><td>X<sub>t</sub> ∼ ν<sub>a<sub>t</sub></sub></td><td>observation collected from ν<sub>a<sub>t</sub></sub></td></tr><tr><td>ε<sub>t</sub> := X<sub>t</sub> − (I<sub>d</sub> ⊗ a<sub>t</sub>)vec(μ)</td><td>centered (sub)Gaussian noise at time t</td></tr><tr><td>η<sub>t</sub></td><td>learning rate for the min learner (Section D.2)</td></tr></table>

## C CORRECTNESS OF THE STOPPING RULE

In this section, we prove the correctness of the PS (Posterior Sampling) stopping rule. We recall the definition of $\tau_{\delta}^{\text{PS}}$:

$$ \tau_{\delta}^{\text{PS}} := \inf \{ t \mid \forall m \in [M(t-1, \delta)], \theta_t^m \notin \Theta \cap \text{Alt}(\hat{S}_t) \}, $$

where, conditioned on $\mathcal{F}_t$, $\theta_t$, $\theta_t^1, \dots, \theta_t^m$ are i.i.d samples from $N(\text{vec}(\hat{\theta}_t), c(t-1, \delta)\Sigma_t)$. To prove the correctness of this stopping rule, we will have to control the randomness in the posterior, which we do by introducing the concentration event $\mathcal{E}_{\delta} := \bigcap_{t \in \mathbb{N}} \mathcal{E}_{t, \delta}$ with

$$ \mathcal{E}_{t, \delta} := \left\{ \left\| \text{vec}(\theta - \hat{\theta}_t) \right\|_{\Sigma_t^{-1}}^2 \le 2\beta(t-1, \delta) \right\}, $$

for which, correct values of the thresholds are given in the lemma below.

**Lemma 3.** Let $s > 1$, $\zeta$ be the Riemann $\zeta$ function and $\bar{W}_{-1}(x) := -W_{-1}(-e^{-x})$ for all $x \ge 1$, where $W_{-1}$ is the negative branch of the Lambert W function. Let $\mathcal{E}_{\delta}$ in (6). Then, we have $\mathbb{P}_{\nu}(\mathcal{E}_{\delta}^{c}) \le \delta$ by taking

$$ \beta(t, \delta) = \frac{dK}{2} \bar{W}_{-1} \left( \frac{2}{dK} \log \frac{e^{Ks}\zeta(s)^K}{\delta} + \frac{2s}{d} \log \left( 1 + \frac{d}{2s} \log \frac{t}{K} \right) + 1 \right) $$

in the unstructured setting, and taking

$$ \sqrt{\beta(t, \delta)} = \sqrt{\log \left( \frac{1}{\delta} \left( \frac{L_A^2}{h\xi} t + 1 \right)^{\frac{dh}{2}} \right)} + \sqrt{\frac{dL_M^2}{2\lambda_{\min}(\Sigma)\xi}} $$

in the transductive linear setting, where $L_A := \max_{a \in A} ||a||_2$ and $L_M := \max_{\lambda \in \Theta} \max_{c \in [d]} ||\lambda e_c||_2$.

The following result shows that to prove the $\delta$-correctness, it is sufficient to show some anti-concentration of the posterior under the event $\mathcal{E}$. $\mathbb{P}_{\nu}(\mathcal{E}_{\delta/2} \cap \{\tau_{\delta}^{\text{PS}} < +\infty, \hat{S}_{\tau_{\delta}^{\text{PS}}} \neq S^*\}) \le \delta/2$.

**Lemma 4.** For all $c, M$, the PS stopping rule satisfies

$$ \mathbb{P}_{\nu}(\tau_{\delta}^{\text{PS}} < +\infty, \hat{S}_{\tau_{\delta}^{\text{PS}}} \neq S^*) \le \delta/2 + \mathbb{E} \left[ \sum_{t \ge 1} \mathbb{1}_{\mathcal{E}_{t, \delta/2}} \mathbb{1}_{\hat{S}_t \neq S^*} \exp \left( -M(t-1, \delta) \mathbb{P}_{\nu} \left( \theta_t \in \Theta \cap \text{Alt}(\hat{S}_t) \mid \mathcal{F}_t \right) \right) \right]. \quad (7) $$
Proof. Using the definition of the PS stopping rule in (2), we obtain

$$
\begin{align*}
\mathbb{P}_{\nu} (\tau_{\delta}^{\text{PS}} < \infty, \hat{S}_{\tau_{\delta}^{\text{PS}}} \neq S^{\star}) &\leq \delta/2 + \mathbb{P}_{\nu} (\mathcal{E}_{\delta/2} \cap \{\tau_{\delta}^{\text{PS}} < \infty, \hat{S}_{\tau_{\delta}^{\text{PS}}} \neq S^{\star}\}) \\
&\leq \delta/2 + \sum_{t \geq 1} \mathbb{P}_{\nu} (\mathcal{E}_{t, \delta/2} \cap \{\tau_{\delta}^{\text{PS}} = t, \hat{S}_{\tau_{\delta}^{\text{PS}}} \neq S^{\star}\}) \\
&= \delta/2 + \mathbb{E} \left[ \sum_{t \geq 1} \mathbb{1}_{\mathcal{E}_{t, \delta/2}} \mathbb{1}_{\hat{S}_t \neq S^*} \mathbb{P}_{\nu} (\tau_{\delta}^{\text{PS}} = t \mid \mathcal{F}_t) \right] \\
&\leq \delta/2 + \mathbb{E} \left[ \sum_{t \geq 1} \mathbb{1}_{\mathcal{E}_{t, \delta/2}} \mathbb{1}_{\hat{S}_t \neq S^*} \mathbb{P}_{\nu} \left( \forall m \leq M(t-1, \delta), \theta_t^m \notin \Theta \cap \text{Alt}(\hat{S}_t) \mid \mathcal{F}_t \right) \right] \\
&= \delta/2 + \mathbb{E} \left[ \sum_{t \geq 1} \mathbb{1}_{\mathcal{E}_{t, \delta/2}} \mathbb{1}_{\hat{S}_t \neq S^*} \mathbb{P}_{\nu} \left( \theta_t \notin \Theta \cap \text{Alt}(\hat{S}_t) \mid \mathcal{F}_t \right)^{M(t-1, \delta)} \right] \\
&= \delta/2 + \mathbb{E} \left[ \sum_{t \geq 1} \mathbb{1}_{\mathcal{E}_{t, \delta/2}} \mathbb{1}_{\hat{S}_t \neq S^*} \left( 1 - \mathbb{P}_{\nu} \left( \theta_t \in \Theta \cap \text{Alt}(\hat{S}_t) \mid \mathcal{F}_t \right) \right)^{M(t-1, \delta)} \right]
\end{align*}
$$

which follows since the samples $\theta_t, \theta_t^1, \dots, \theta_t^m$ are i.i.d given $\mathcal{F}_t$. Further recalling that $1-x \le \exp(-x)$, it follows

$$
\mathbb{P}_{\nu} (\tau_{\delta}^{\text{PS}} < \infty, \hat{S}_{\tau_{\delta}^{\text{PS}}} \neq S^{\star}) \leq \delta/2 + \mathbb{E} \left[ \sum_{t \geq 1} \mathbb{1}_{\mathcal{E}_{t, \delta/2}} \mathbb{1}_{\hat{S}_t \neq S^*} \exp \left( -M(t-1, \delta) \mathbb{P}_{\nu} \left( \theta_t \in \Theta \cap \text{Alt}(\hat{S}_t) \mid \mathcal{F}_t \right) \right) \right]. \quad (8) \\
\hfill \square
$$

Lemma 4 shows that choosing $c, M$ such that

$$
\mathbb{E} \left[ \sum_{t \ge 1} \mathbb{1}_{\mathcal{E}_{t, \delta/2}} \mathbb{1}_{\hat{S}_t \neq S^*} \exp \left( -M(t-1, \delta) \mathbb{P}_{\nu} \left( \theta_t \in \Theta \cap \text{Alt}(\hat{S}_t) \mid \mathcal{F}_t \right) \right) \right]
$$

is not larger than $\delta/2$ will ensure the correctness of the PS stopping rule. However, it is not possible to pick $M(t-1, \delta) \propto \mathbb{P}_{\nu}(\theta_t \in \Theta \cap \text{Alt}(\hat{S}_t) | \mathcal{F}_t)$ as the latter quantity is intractable due to multidimensional integration over a non-trivial domain. Instead, we will derive in the following sections, tractable lower bounds on $\mathbb{1}_{\mathcal{E}_{t, \delta/2}} \mathbb{1}_{S_t \neq S^*} \mathbb{P}_{\nu}(\theta_t \in \Theta \cap \text{Alt}(\hat{S}_t) | \mathcal{F}_t)$ with

$$
\text{Alt}(\hat{S}_t) = \left( \bigcup_{x \neq z \in \hat{S}_t^2} \bigcap_{c \in [d]} \{ \boldsymbol{\lambda} \in \mathbb{R}^{h \times d} \mid \langle E_{z,x}(c), \text{vec}(\boldsymbol{\lambda}) \rangle \ge 0 \} \right) \\
\bigcup \left( \bigcup_{z \notin \hat{S}_t} \bigcap_{x \in \hat{S}_t} \bigcap_{c \in [d]} \{ \boldsymbol{\lambda} \in \mathbb{R}^{h \times d} \mid \langle E_{x,z}(c), \text{vec}(\boldsymbol{\lambda}) \rangle \ge 0 \} \right), \quad (9)
$$

where $E_{z,x}(c) = e_c \otimes (z-x)$ and $e_c = (\mathbb{1}(c' = c))_{c' \in [d]}$.

C.1 Unstructured Setting

In this section, we calibrate $c, M$ to ensure the correctness of the PS stopping rule in the unstructured setting. In this setting, we have $\Theta = \mathbb{R}^{K \times d}$, $\mathbf{A} = I_K$, so that the quantity to control is

$$
\mathbb{1}_{\mathcal{E}_{t, \delta/2}} \mathbb{1}_{\hat{S}_t \neq S^*} \mathbb{P}_{\nu}(\theta_t \in \text{Alt}(\hat{S}_t) | \mathcal{F}_{\infty}) \quad \text{with} \quad \text{vec}(\theta_t - \hat{\theta}_t) | \mathcal{F}_t \sim \mathcal{N}(\mathbf{0}_{Kd}, c(t-1, \delta)\boldsymbol{\Sigma}_t),
$$

and

$$
\text{Alt}(\hat{S}_t) = \left( \bigcup_{i \neq j \in \hat{S}_t^2} \{ \boldsymbol{\lambda} := (\lambda_1 \dots \lambda_K)^\top \in \Theta \mid \lambda_i < \lambda_j \} \right) \bigcup \left( \bigcup_{i \notin \hat{S}_t} \{ \boldsymbol{\lambda} := (\lambda_1 \dots \lambda_K)^\top \in \Theta \mid \forall j \in \hat{S}_t, \lambda_i \not< \lambda_j \} \right).
$$
Indeed, recalling that Alt($S$) is the set of parameters for which the Pareto set differs from $S$. To change the Pareto set, we either add an arm or remove one from it. For a parameter instance $\lambda := (\lambda_1 \dots \lambda_K)^\top$, if $i \in S$ and there exists $j \in S$ such that $\lambda_i < \lambda_j$, then as $i$ is a dominated arm in the instance $\lambda$, we will have $S^*(\lambda) \neq S$. Similarly, if for some $i \notin S$ it holds that for all $j \in S$, $\lambda_i \not< \lambda_j$, then we cannot have $S^*(\lambda) = S$, otherwise, as $i \notin S^*(\lambda)$, an arm from $S^*(\lambda) = S$ would have dominated $i$. This is formally shown in Lemma 26, where it is further proven that

$$ \mathrm{Alt}(S) = \left( \bigcup_{(i,j) \in S^2, i \neq j} \{\lambda \in \mathbb{R}^{d \times K} \mid \lambda_i < \lambda_j\} \right) \bigcup \left( \bigcup_{i \in S^c} \bigcup_{\bar{d}^i \in [d]^S} \{\lambda \mid \forall j \in S, \lambda_i(d^i(\sigma(j))) \ge \lambda_j(d^i(\sigma(j)))\} \right) $$

where $\sigma$ is any permutation that maps $S$ onto $\{1, \dots, |S|\}$. In the sequel, we let

$$ \mathrm{Alt}^{-}(S) := \bigcup_{(i,j) \in S^2, i \neq j} \{\lambda \mid \lambda_i < \lambda_j\} \quad \text{and} \quad \mathrm{Alt}^{+}(S) := \bigcup_{i \in S^c} \bigcup_{\bar{d}^i \in [d]^S} \{\lambda \mid \forall j \in S : \lambda_i(d^i(\sigma(j))) \ge \lambda_j(d^i(\sigma(j)))\} $$

so that $\mathrm{Alt}(S) = \mathrm{Alt}^{+}(S) \cup \mathrm{Alt}^{-}(S)$. We prove the following lemma.

**Lemma 5. It holds that**

$$ \begin{aligned} 1_{\hat{S}_t \neq S^*} \mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\mathrm{Alt}(\hat{S}_t)) &\ge \max \left\{ \begin{array}{@{}l@{}} \displaystyle \max_{i \notin \hat{S}_t, \bar{d}^i \in [d]^S} 1_{(\forall j \in \hat{S}_t, \mu_i(\bar{d}_j^\sigma) \ge \mu_j(\bar{d}_j^\sigma))} \mathbb{P}_{Y \sim \mathcal{N}(0_d, \Sigma)} \left( Y > \sqrt{\frac{N_{t,i}}{c(t-1, \delta)}} (\mu_i - \hat{\mu}_{t,i}) \right) \\ \displaystyle \qquad \cdot \prod_{j \in \hat{S}_t} \mathbb{P}_{X \sim \mathcal{N}(0,1)} \left( X > \sqrt{\frac{N_{t,j}}{c(t-1, \delta)}} \|\mu_j - \hat{\mu}_{t,j}\|_{\Sigma^{-1}} \right), \\ \displaystyle \max_{i \neq j \in \hat{S}_t} 1_{(\mu_i < \mu_j) \sim \mathbb{P}_{Y \sim \mathcal{N}(0_d, \Sigma)}} \left( Y \ge \sqrt{\left(\frac{1}{N_{t,i}} + \frac{1}{N_{t,j}}\right)^{-1} \frac{1}{c(t-1, \delta)}} ((\hat{\mu}_{t,i} - \hat{\mu}_{t,j}) - (\mu_i - \mu_j)) \right) \end{array} \right\}. \end{aligned} $$

*Proof.*

$$ \begin{aligned} 1_{\hat{S}_t \neq S^*} \mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\mathrm{Alt}^{-}(\hat{S}_t)) &\ge 1_{\hat{S}_t \neq S^*} \max_{(i,j) \in \hat{S}_t, i \neq j} \mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\{\lambda = (\lambda_1 \dots \lambda_K)^\top \in \mathbb{R}^{d \times K} : \lambda_i < \lambda_j\}) \\ &\ge \max_{(i,j) \in \hat{S}_t, i \neq j} 1_{(\mu_i < \mu_j) \sim \mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}}(\{\lambda = (\lambda_1 \dots \lambda_K)^\top \in \mathbb{R}^{d \times K} : \lambda_i < \lambda_j\}) \\ &= \max_{(i,j) \in \hat{S}_t, i \neq j} 1_{(\mu_i < \mu_j) \sim \mathbb{P}_{\nu}(\theta_{t,i} < \theta_{t,j} | \mathcal{F}_t)}, \end{aligned} $$

where $\theta_{t,i} = \theta^T \tilde{e}_i$ and $\tilde{e}_1, \dots, \tilde{e}_K$ is the cananical basis of $\mathbb{R}^K$. In the unstructured setting, it is simple to check that $\theta_t^\top = (\theta_{t,1} \dots \theta_{t,K})$ where $\theta_{t,i} \mid \mathcal{F}_t \sim \mathcal{N}(\hat{\mu}_{t,i}, c(t-1, \delta)\Sigma/N_{t,i})$. Therefore, we have

$$ \begin{aligned} 1_{\hat{S}_t \neq S^*} \mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\mathrm{Alt}^{-}(\hat{S}_t)) &\ge \max_{(i,j) \in \hat{S}_t, i \neq j} 1_{(\mu_i < \mu_j) \sim \mathbb{P}_{\nu}((\theta_{t,i} - \theta_{t,j}) - (\hat{\mu}_{t,i} - \hat{\mu}_{t,j}) < (\mu_i - \mu_j) | \mathcal{F}_t)} \\ &\ge \max_{(i,j) \in \hat{S}_t, i \neq j} 1_{(\mu_i < \mu_j) \sim \mathbb{P}_{\nu}((\theta_{t,i} - \theta_{t,j}) - (\hat{\mu}_{t,i} - \hat{\mu}_{t,j}) \le (\mu_i - \mu_j) - (\hat{\mu}_{t,i} - \hat{\mu}_{t,j}) | \mathcal{F}_t)} \end{aligned} $$

then, observe that $(\theta_{t,i} - \theta_{t,j}) \mid \mathcal{F}_t \sim \mathcal{N}(\hat{\mu}_{t,i} - \hat{\mu}_{t,j}, (N_{t,i}^{-1} + N_{t,j}^{-1})c(t, \delta)\Sigma)$, so that letting $Y \sim \mathcal{N}(0_d, \Sigma)$, we have

$$ \begin{aligned} 1_{\hat{S}_t \neq S^*} \mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\mathrm{Alt}^{-}(\hat{S}_t)) &\ge \max_{i \neq j \in \hat{S}_t} 1_{(\mu_i < \mu_j) \sim \mathbb{P}_{Y \sim \mathcal{N}(0_d, \Sigma)}} \left( Y < \sqrt{\left(\frac{1}{N_{t,i}} + \frac{1}{N_{t,j}}\right)^{-1} \frac{1}{c(t-1, \delta)}} ((\mu_i - \mu_j) - (\hat{\mu}_{t,i} - \hat{\mu}_{t,j})) \right) \\ &\ge \max_{i \neq j \in \hat{S}_t} 1_{(\mu_i < \mu_j) \sim \mathbb{P}_{Y \sim \mathcal{N}(0_d, \Sigma)}} \left( Y \ge \sqrt{\left(\frac{1}{N_{t,i}} + \frac{1}{N_{t,j}}\right)^{-1} \frac{1}{c(t-1, \delta)}} ((\hat{\mu}_{t,i} - \hat{\mu}_{t,j}) - (\mu_i - \mu_j)) \right). \end{aligned} $$
We now prove a similar result on $Alt^+(\hat{S}_t)$. We have

$$
\begin{align*}
& \mathbb{1}_{\hat{S}_t \neq S^*} \mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t} (\mathrm{Alt}^+(\hat{S}_t)) \\
& \geq \max_{i \notin \hat{S}_t, \bar{d} \in [d] | \hat{S}_t |} \mathbb{1}_{(\forall j \in \hat{S}_t, \mu_i(\bar{d}_j^\sigma) \geq \mu_j(\bar{d}_j^\sigma))} \mathbb{P}_\nu (\forall j \in \hat{S}_t, \theta_{t,i}(\bar{d}_j^\sigma) \geq \theta_{t,j}(\bar{d}_j^\sigma) | \mathcal{F}_t) \\
& \geq \max_{i \notin \hat{S}_t, \bar{d} \in [d] | \hat{S}_t |} \mathbb{1}_{(\forall j \in \hat{S}_t, \mu_i(\bar{d}_j^\sigma) \geq \mu_j(\bar{d}_j^\sigma))} \mathbb{P}_\nu (\forall j \in \hat{S}_t, (\theta_{t,i} - \mu_i)(\bar{d}_j^\sigma) \geq (\theta_{t,j} - \mu_j)(\bar{d}_j^\sigma) | \mathcal{F}_t) \\
& \geq \max_{i \notin \hat{S}_t, \bar{d} \in [d] | \hat{S}_t |} \mathbb{1}_{(\forall j \in \hat{S}_t, \mu_i(\bar{d}_j^\sigma) \geq \mu_j(\bar{d}_j^\sigma))} \mathbb{P}_\nu ((\theta_{t,i} - \mu_i) > 0_d | \mathcal{F}_t) \prod_{j \in \hat{S}_t} \mathbb{P}_\nu ((\theta_{t,j} - \mu_j)(\bar{d}_j^\sigma) > 0 | \mathcal{F}_t)
\end{align*}
$$

then, noting again that $(\theta_{t,i} - \hat{\mu}_{t,i}) | \mathcal{F}_t \sim \mathcal{N}(0, c(t-1, \delta)\Sigma/N_{t,i})$, it follows that

$$
\mathbb{1}_{\hat{S}_t \neq S^*} \mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t} (\mathrm{Alt}^+(\hat{S}_t)) \geq \max_{i \notin \hat{S}_t, \bar{d} \in [d] | \hat{S}_t |} \mathbb{1}_{(\forall j \in \hat{S}_t, \mu_i(\bar{d}_j^\sigma) \geq \mu_j(\bar{d}_j^\sigma))} \mathbb{P}_{Y \sim \mathcal{N}(0_d, \Sigma)} \left( Y > \sqrt{\frac{N_{t,i}}{c(t-1, \delta)}} (\mu_i - \hat{\mu}_{t,i}) \right) \\
\cdot \prod_{j \in \hat{S}_t} \mathbb{P}_\nu((\theta_{t,j} - \mu_j)(\bar{d}_j^\sigma) > 0 | \mathcal{F}_t). \quad (10)
$$

Further noting that by Cauchy-Schwartz inequality,

$$ (\hat{\mu}_{t,j} - \mu_j)(\bar{d}_j^\sigma) \leq \|\tilde{e}_{\bar{d}_j^\sigma}\|_{\Sigma} \|\mu_j - \hat{\mu}_{t,j}\|_{\Sigma^{-1}}, $$

it follows for any $j \in \hat{S}_t$ that

$$
\begin{align*}
\mathbb{P}_{\nu}((\theta_{t,j} - \mu_j)(\bar{d}_j^\sigma) > 0 | \mathcal{F}_t) &= \mathbb{P}_{\nu}((\theta_{t,j} - \hat{\mu}_{t,j})(\bar{d}_j^\sigma) > (\mu_j - \hat{\mu}_{t,j})(\bar{d}_j^\sigma) | \mathcal{F}_t) \\
&\geq \mathbb{P}_{\nu}((\theta_{t,j} - \hat{\mu}_{t,j})(\bar{d}_j^\sigma) > \|\tilde{e}_{\bar{d}_j^\sigma}\|_{\Sigma} \|\mu_j - \hat{\mu}_{t,j}\|_{\Sigma^{-1}} | \mathcal{F}_t) \\
&= \mathbb{P}_{X \sim \mathcal{N}(0,1)} \left( X > \sqrt{\frac{N_{t,j}}{c(t-1, \delta)}} \|\mu_j - \hat{\mu}_{t,j}\|_{\Sigma^{-1}} \right),
\end{align*}
$$

which follows from $(\theta_{t,j} - \hat{\mu}_{t,j})(\bar{d}_j^\sigma) | \mathcal{F}_t \sim \mathcal{N}(0, c(t-1, \delta)) \|\tilde{e}_{\bar{d}_j^\sigma}\|/N_{t,\delta}$. Therefore, combining the last display with (10) yields

$$
\mathbb{1}_{\hat{S}_t \neq S^*} \mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t} (\mathrm{Alt}^+(\hat{S}_t)) \geq \max_{i \notin \hat{S}_t, \bar{d} \in [d] | \hat{S}_t |} \mathbb{1}_{(\forall j \in \hat{S}_t, \mu_i(\bar{d}_j^\sigma) \geq \mu_j(\bar{d}_j^\sigma))} \mathbb{P}_{Y \sim \mathcal{N}(0_d, \Sigma)} \left( Y > \sqrt{\frac{N_{t,i}}{c(t-1, \delta)}} (\mu_i - \hat{\mu}_{t,i}) \right) \\
\cdot \prod_{j \in \hat{S}_t} \mathbb{P}_{X \sim \mathcal{N}(0,1)} \left( X > \sqrt{\frac{N_{t,j}}{c(t-1, \delta)}} \|\mu_j - \hat{\mu}_{t,j}\|_{\Sigma^{-1}} \right),
$$

which achieves the proof. $\square$

### C.1.1 Special Case: PSI with Independent Covariate

In this section, we specialize Lemma 5 to the case where $\Sigma$ is diagonal. In this case, $\Sigma = \mathrm{diag}(\{\sigma_c^2\}_{c \in [d]})$ and

$$
(*) = \mathbb{P}_{Y \sim \mathcal{N}(0_d, \Sigma)} \left( Y \ge \sqrt{\left(\frac{1}{N_{t,i}} + \frac{1}{N_{t,j}}\right)^{-1} \frac{1}{c(t-1, \delta)}} ((\hat{\mu}_{t,i} - \hat{\mu}_{t,j}) - (\mu_i - \mu_j)) \right) = \\
\prod_{c \in [d]} \mathbb{P}_{X \sim \mathcal{N}(0,1)} \left( X > \underbrace{\sqrt{\left(\frac{1}{N_{t,i}} + \frac{1}{N_{t,j}}\right)^{-1} \frac{1}{\sigma_c^2 c(t-1, \delta)}} ((\hat{\mu}_{t,i} - \hat{\mu}_{t,j}) - (\mu_i - \mu_j))}_{Z_{i,j}(c)} (c) \right),
$$

which we may rewrite with Mills ratio as $R(x) := \frac{\mathbb{P}(X > x)}{\mathbb{P}_X(x)}$ so

$$ \mathbb{P}(X > x) = R(x) \exp(-\frac{1}{2}x^2) \frac{1}{\sqrt{2\pi}} = \tilde{R}(x) \exp(-\frac{1}{2}x^2), $$
and

$$ (*) = \exp\left(-\frac{1}{2} \sum_{c \in [d]} Z_{i,j}(c)\right) \prod_{c \in [d]} \tilde{R}(Z_{i,j}(c)) \\ = \exp\left(-\left(\frac{1}{N_{t,i}} + \frac{1}{N_{t,j}}\right)^{-1} \frac{1}{c(t-1, \delta)} \sum_{c \in [d]} \frac{((\hat{\mu}_{t,i} - \hat{\mu}_{t,j}) - (\mu_i - \mu_j))(c)^2}{2\sigma_c^2}\right) \prod_{c \in [d]} \tilde{R}(Z_{i,j}(c)) $$

and by Cauchy-Swchartz inequality,

$$ |((\hat{\mu}_{t,i} - \hat{\mu}_{t,j}) - (\mu_i - \mu_j))(c)| \le \sqrt{\frac{1}{N_{t,i}} + \frac{1}{N_{t,j}}} \sqrt{N_{t,i}(\hat{\mu}_{t,i} - \mu_i)(c)^2 + N_{t,j}(\mu_j - \hat{\mu}_{t,j})(c)^2} $$

Therefore

$$ (*) \ge \exp\left(-\frac{1}{c(t-1, \delta)} \sum_{k \in \{i,j\}} \frac{N_{t,k}}{2} \|\hat{\mu}_{t,k} - \mu_k\|_{\Sigma^{-1}}^2\right) \prod_{c \in [d]} \tilde{R}(Z_{i,j}(c)), \quad (11) $$

and using the following lemma,

**Lemma 6.** The Mills ratio $R$ is decreasing, log-convex and satisfies for all $(x_1, \dots, x_p) \in \mathbb{R}^p$,

$$ R\left(\frac{1}{p}\sum_{i=1}^{p} x_i\right)^p \le \prod_{i=1}^{p} R(x_i). $$

we obtain

$$ \begin{aligned} \prod_{c \in [d]} \tilde{R}(Z_{i,j}(c)) &\ge \tilde{R} \left( \frac{1}{d} \sum_{c \in [d]} Z_{i,j}(c) \right)^d \\ &\stackrel{(a)}{\ge} \tilde{R} \left( \frac{1}{d} \sum_{c \in [d]} \sqrt{\frac{1}{\sigma_c^2 c(t-1, \delta)}} \sqrt{N_{t,i}(\hat{\mu}_{t,i} - \mu_i)(c)^2 + N_{t,j}(\mu_j - \hat{\mu}_{t,j})(c)^2} \right)^d \\ &\stackrel{(b)}{\ge} \tilde{R} \left( \frac{\sqrt{2}}{\sqrt{c(t-1, \delta)d}} \sqrt{\sum_{k \in \{i,j\}} \frac{N_{t,k}}{2} \|\hat{\mu}_{t,k} - \mu_k\|_{\Sigma^{-1}}^2} \right)^d, \end{aligned} $$

where (a) follows since $\tilde{R}$ is decreasing (Lemma 6) and (b) follows from this monotonicity and Cauchy-Schwartz. Combining the last display with (11), we prove that on the event $\mathcal{E}_{t,\delta/2}$, we have

$$ (*) \ge \exp\left(-\frac{\beta(t-1, \delta/2)}{c(t-1, \delta)}\right) \tilde{R}\left(\sqrt{\frac{2\beta(t-1, \delta/2)}{c(t-1, \delta)d}}\right)^d $$

Choosing

$$ c(t, \delta) := \frac{\beta(t, \delta/2)}{\log(1/\delta)} $$

yields,

$$ (*) \ge \delta \tilde{R} \left( \sqrt{\frac{2 \log(1/\delta)}{d}} \right)^d = r(\delta, d) \quad \text{with} \quad r(\delta, n) = \tilde{R} \left( \sqrt{\frac{2 \log(1/\delta)}{n}} \right)^n $$
and proceeding identically, we prove that under the event $\mathcal{E}_{t,\delta/2}$,

$$ \mathbb{P}_{Y \sim \mathcal{N}(0_d, \Sigma)} \left( Y > \sqrt{\frac{N_{t,i}}{c(t-1, \delta)}} (\mu_i - \hat{\mu}_{t,i}) \prod_{j \in \hat{S}_t} \mathbb{P}_{X \sim \mathcal{N}(0,1)} \left( X > \sqrt{\frac{N_{t,j}}{c(t-1, \delta)}} \|\mu_j - \hat{\mu}_{t,j}\|_{\Sigma^{-1}} \right) \right. \\ \left. \geq \delta \tilde{R} \left( \sqrt{\frac{2 \log(1/\delta)}{d + |\hat{S}_t|}} \right)^{d+|\hat{S}_t|} \right). $$

All put together, we proved that

$$ \mathbb{1}_{\mathcal{E}_{t,\delta/2}} \mathbb{1}_{\hat{S}_t \neq S^*} \mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\mathrm{Alt}(\hat{S}_t)) \geq \delta \max \left\{ \mathbb{1}_{\mu \in \mathrm{Alt}^{-}(\hat{S}_t)} r(\delta, d), \mathbb{1}_{(\mu \in \mathrm{Alt}^{+}(\hat{S}_t))} r(\delta, d + |\hat{S}_t|) \right\} \\ \geq \delta \min(r(\delta, d), r(\delta, d + |\hat{S}_t|)) $$

which follows since $\hat{S}_t \neq S^* \Rightarrow \mu \in \mathrm{Alt}(\hat{S}_t) = \mathrm{Alt}^{+}(\hat{S}_t) \cup \mathrm{Alt}^{-}(\hat{S}_t)$.

The conclusion is immediate by taking $M(t, \delta) = \left\lfloor \frac{\log(2t^*\zeta(s)/\delta)}{\delta q(t, \delta)} \right\rfloor$ where $q(t-1, \delta) = \min(r(\delta, d), r(\delta, d + |\hat{S}_t|))$. Moreover, it is known (Birnbaum, 1942) that for $x \geq 0$,

$$ R(x) \geq \frac{2}{x + \sqrt{x^2 + 4}} $$

and $R(x) \sim \frac{1}{x}, x \to +\infty$. The Mills ratio of the standard normal is implemented in common scientific libraries. To compute $M(t, \delta)$, we just need to compute at most the values $(r(\delta, d + k))_{k \in [K] \cup \{0\}}$ at the initialisation of the algorithm. Using the lower bound on the Mills ratio, one can easily check that

$$ \frac{\log(M(t, \delta))c(t, \delta)}{\log(1/\delta)} \stackrel{\delta \to 0}{\leq} 1. $$

*Proof of Lemma 6.* The monotonicity is well-known and simple to prove by noting that

$$ \begin{aligned} R(x) &:= \exp(x^2/2) \int_x^\infty \exp(-t^2/2) dt \\ &= \exp(x^2/2) \int_0^\infty \exp(-(t+x)^2/2) dt \\ &= \int_0^\infty \exp(-tx - t^2/2) dt, \end{aligned} $$

from which we have $R(x + \alpha^2) = \int_0^\infty \exp(-t\alpha^2) \exp(-tx - t^2/2) dt < R(x)$. The log-convexity is proven in Theorem 2.5 of Baricz (2008). From the log-convexity and using Jensen inequality, we have

$$ \begin{aligned} \log R \left( \frac{1}{p} \sum_{i=1}^{p} x_i \right) &\leq \frac{1}{p} \sum_{i=1}^{p} \log R(x_i) \\ &= \frac{1}{p} \log \left( \prod_{i=1}^{p} R(x_i) \right) \end{aligned} $$

which by monotonicity of the log proves the claimed statement. $\square$

### C.1.2 PSI with a Covariance Matrix

We specialise Lemma 5 to the case where the covariance $\Sigma$ is non-diagonal. To derive this result, we will use the following lemma.

**Lemma 7.** Let $\Sigma$ a covariance matrix, $V$ diagonal matrix such that $(V - \Sigma^{-1})$ is psd, and define $d_\Sigma := \|1_d\|_{(V^{-1/2}\Sigma^{-1}V^{-1/2})}^2$. Then, for all $x \in \mathbb{R}^d$, it holds that

$$ \mathbb{P}_{X \sim \mathcal{N}(0_d, \Sigma)} (X \geq x) \geq (2\pi)^{-d/2} \det(V\Sigma)^{-1/2} \exp \left( -\frac{1}{2} x^\top \Sigma^{-1} x \right) \prod_{c \in [d]} R(e_c^\top V^{-1/2} \Sigma^{-1} x), $$
and in particular, $\prod_{c \in [d]} R(e_c^\top V^{-1/2} \Sigma^{-1} x) \ge R (\|x\|_{\Sigma^{-1}} \sqrt{d_{\Sigma}}/d)^d$.

Applying this result with $V = \bar{\sigma} I_d$ where $\bar{\sigma} = \|\Sigma^{-1}\|$, we have

$$ \mathbb{P}_{Y \sim \mathcal{N}(0_d, \Sigma)} \left( Y > \sqrt{\frac{N_{t,i}}{c(t-1, \delta)}} (\mu_i - \hat{\mu}_{t,i}) \right) \ge \frac{1}{\sqrt{(2\pi)^d \det(\bar{\sigma}\Sigma)}} \exp \left( -\frac{1}{2} \|\mu_i - \hat{\mu}_{t,i}\|_{\Sigma^{-1}}^2 \right) \prod_{c \in [d]} R(e_c^\top V^{-1/2} \Sigma^{-1} u_t), $$

with $u_t := \sqrt{\frac{N_{t,i}}{c(t-1, \delta)}}(\mu_i - \hat{\mu}_{t,i})$, therefore, letting

$$ (**) := \mathbb{P}_{Y \sim \mathcal{N}(0_d, \Sigma)} \left( Y > \sqrt{\frac{N_{t,i}}{c(t-1, \delta)}} (\mu_i - \hat{\mu}_{t,i}) \right) \prod_{j \in \hat{S}_t} \mathbb{P}_{X \sim \mathcal{N}(0,1)} \left( X > \sqrt{\frac{N_{t,j}}{c(t-1, \delta)}} \|\mu_j - \hat{\mu}_{t,j}\|_{\Sigma^{-1}} \right) $$

we have

$$ (**) \ge \det(\bar{\sigma}\Sigma)^{-1/2} \exp \left( - \sum_{k \in \{i\} \cup \hat{S}_t} \frac{1}{2} \|\mu_k - \hat{\mu}_{t,k}\|_{\Sigma^{-1}}^2 \right) \prod_{j \in \hat{S}_t} \tilde{R} \left( \sqrt{\frac{N_{t,j} \|\mu_j - \hat{\mu}_{t,j}\|_{\Sigma^{-1}}^2}{c(t-1, \delta)}} \right) \prod_{c \in [d]} \tilde{R}(e_c^\top V^{-1/2} \Sigma^{-1} u_t), $$

then note that by Lemma 6, we have

$$ \prod_{j \in \hat{S}_t} \tilde{R} \left( \sqrt{\frac{N_{t,j}}{c(t-1, \delta)}} \|\mu_j - \hat{\mu}_{t,j}\|_{\Sigma^{-1}} \right) \prod_{c \in [d]} \tilde{R}(e_c^\top V^{-1/2} \Sigma^{-1} u_t/d) \ge \tilde{R} \left( \frac{1_d^\top V^{-1/2} \Sigma^{-1} u_t + 1_{|\hat{S}_t|}^\top h_t}{d + |\hat{S}_t|} \right)^{d+|\hat{S}_t|} $$

with $h_t := (\sqrt{\frac{N_{t,j}}{c(t-1, \delta)}} \|\mu_j - \hat{\mu}_{t,j}\|_{\Sigma^{-1}})_{j \in |\hat{S}_t|}$ and by Cauchy-Swartz inequality, replacing $V = \bar{\sigma} I_d$,

$$ \begin{aligned} 1_d^\top V^{-1/2} \Sigma^{-1} u_t + 1_{|\hat{S}_t|}^\top h_t &\le \sqrt{\|1_d\|_{(\bar{\sigma}\Sigma)^{-1}}^2 + \|1_{|\hat{S}_t|}\|_2^2} \sqrt{\|u_t\|_{\Sigma^{-1}}^2 + \|h_t\|^2} \\ &= \sqrt{d_{\Sigma} + |\hat{S}_t|} \left( \sqrt{\frac{1}{c(t-1, \delta)} \sum_{k \in \{i\} \cup \hat{S}_t} N_{k,t} \|\mu_k - \hat{\mu}_{t,k}\|_{\Sigma^{-1}}^2} \right) \\ &\le \sqrt{d_{\Sigma} + |\hat{S}_t|} \sqrt{\frac{2\beta(t-1, \delta/2)}{c(t-1, \delta)}} \end{aligned} $$

where the last inequality follows on the event $\mathcal{E}_{t,\delta/2}$. Combining these displays with $c(t, \delta) := \frac{\beta(t, \delta/2)}{\log(1/\delta)}$, we have on the event $\mathcal{E}_{t,\delta/2}$,

$$ \begin{aligned} (**) &\ge \det(\bar{\sigma}\Sigma)^{-1/2} \delta \tilde{R} \left( \frac{\sqrt{d_{\Sigma} + |\hat{S}_t|}}{d + |\hat{S}_t|} \sqrt{2 \log(1/\delta)} \right) \\ &= \det(\bar{\sigma}\Sigma)^{-1/2} \delta r(\delta^{\frac{d_{\Sigma} + |\hat{S}_t|}{d + |\hat{S}_t|}}, d + |\hat{S}_t|). \end{aligned} $$

Following the same reasoning, it is simple to show that under the event $\mathcal{E}_{t,\delta/2}$, we have

$$ \begin{aligned} \mathbb{P}_{Y \sim \mathcal{N}(0_d, \Sigma)} & \left( Y \ge \sqrt{\left( \frac{1}{N_{t,i}} + \frac{1}{N_{t,j}} \right)^{-1} \frac{1}{c(t-1, \delta)}} \left( (\hat{\mu}_{t,i} - \hat{\mu}_{t,j}) - (\mu_i - \mu_j) \right) \right) \\ & \ge \det(\bar{\sigma}\Sigma)^{-1/2} \delta \tilde{R} \left( \sqrt{2 \log(1/\delta)} \frac{d_{\Sigma}}{d} \right) = \det(\bar{\sigma}\Sigma)^{-1/2} \delta r(\delta^{\frac{d_{\Sigma}}{d}}, d). \end{aligned} $$

All put together, we have

$$ \begin{aligned} \mathbb{1}_{\mathcal{E}_{t,\delta/2}} \mathbb{1}_{\hat{S}_t \neq S} \mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\mathrm{Alt}(\hat{S}_t)) &\ge \delta \det(\bar{\sigma}\Sigma)^{-1/2} \max \left\{ \mathbb{1}_{\mu \in \mathrm{Alt}^-(\hat{S}_t)} r(\delta^{\frac{d_{\Sigma}}{d}}, d), \mathbb{1}_{(\mu \in \mathrm{Alt}^+(\hat{S}_t))} r(\delta^{\frac{d_{\Sigma} + |\hat{S}_t|}{d + |\hat{S}_t|}}, d + |\hat{S}_t|) \right\} \\ &\ge \delta \det(\bar{\sigma}\Sigma)^{-1/2} \min(r(\delta^{\frac{d_{\Sigma}}{d}}, d), r(\delta^{\frac{d_{\Sigma} + |\hat{S}_t|}{d + |\hat{S}_t|}}, d + |\hat{S}_t|)) \end{aligned} $$
which follows similarly to the Σ diagonal case, since $\hat{S}_t \neq S^* \Rightarrow \mu \in Alt(\hat{S}_t) = Alt^+(\hat{S}_t) \cup Alt^-(\hat{S}_t)$. Remark that when $\Sigma = \sigma I_d$, we recover the results of section C.1.1.

*Proof of Lemma 7.* Σ is a $d \times d$ covariance matrix and $f_Σ$ is the density function of $N(0_d, Σ)$. We let $R_Σ$ denote the Mills ratio of the distribution $N(0_d, Σ)$, which is defined for a vector $x \in \mathbb{R}^d$ as

$$R_Σ(x) := \frac{\mathbb{P}(N(0_d, \Sigma) \geq x)}{f_Σ(x)} \qquad (12)$$

where for two vectors $x, y$, the notation $x \leq y$ should be understood component-wise. Expanding (12) gives

$$R_Σ(x) = \exp(\|x\|_{\Sigma^{-1}}^2/2) \int_{(x, \infty)} \exp(-\|u\|_{\Sigma^{-1}}^2/2) du,$$

with $(x, \infty) = (x(1), \infty) \times \dots \times (x(d), \infty)$. By a simple translation, it follows that

$$R_Σ(x) = \int_{(0_d, \infty)} \exp(-x^\top \Sigma^{-1} u - \|u\|_{\Sigma^{-1}}^2/2) du.$$

Since $(V - \Sigma^{-1})$ is psd, we have

$$\begin{aligned}
R_Σ(x) &\geq \int_{(0_d, \infty)} \exp(-x^\top \Sigma^{-1} u - u^\top V u/2) du \\
&= \det(V)^{-1/2} \int_{(0_d, \infty)} \exp(-x^\top \Sigma^{-1} V^{-1/2} u - u^\top u/2) du
\end{aligned}$$

which follows by change of variable. Thus, letting $z = V^{-1/2} \Sigma^{-1} x$, we have

$$\begin{aligned}
R_Σ(x) &\geq \det(V)^{-1/2} \int_{(0_d, \infty)} \exp(-u^\top z - u^\top u/2) du \\
&= \det(V)^{-1/2} \prod_{c \in [d]} R(z(c))
\end{aligned}$$

then using Lemma 6, it follows that

$$\begin{aligned}
R_Σ(x) &\geq \det(V)^{-1/2} R \left(1_d V^{-1/2} \Sigma^{-1} x/d\right)^d \\
&\geq \det(V)^{-1/2} R \left(\|1_d\|_{V^{-1/2} \Sigma^{-1} V^{-1/2}} \|x\|_{\Sigma^{-1}}/d\right)^d.
\end{aligned}$$

□

## C.2 Structured Setting: Transductive Linear BAI ($d = 1$ and $\Theta = \mathbb{R}^h$)

When $d = 1$, we have $S^* = \{z^*\}$ with $z^* = z^*(\theta)$ and $\hat{S}_t = \{\hat{z}_t\}$ where $\hat{z}_t = z^*(\hat{\theta}_t)$ where $z^*(\lambda) := \argmax_{z \in \mathcal{Z}} \theta^\top z$. Let $\sigma^2 = \Sigma$ be the variance of the unique objective.

Let $\Pi_t = N(0_h, \Sigma_t)$ where $\Sigma_t = \sigma^2(V_{N_t} + \xi I_h)^{-1}$. For all $m \in [M(t-1, \delta)]$, let $v_t^m \sim \Pi_t$ and $\theta_t^m = \hat{\theta}_t + \sqrt{c(t-1, \delta)}v_t^m$. Therefore, using computation as above and $1-x \leq e^{-x}$, we obtain

$$\mathbb{P}_{\nu} \left( \tau_{\delta}^{\text{PS}} < +\infty, \hat{z}_{\tau_{\delta}^{\text{PS}}} \neq z^{*} \right) \leq \delta/2 + \\ \mathbb{E}_{\nu} \left[ \sum_{t \geq 1} \mathbb{1}_{(\mathcal{E}_{t, \delta/2} \cap \{\hat{z}_t \neq z^*\})} \exp \left( -M(t-1, \delta) \mathbb{P}_{v_t^m \sim \Pi_t} \left( \exists z \neq \hat{z}_t, (\hat{\theta}_t + \sqrt{c(t-1, \delta)}v_t^m)^{\top} (z - \hat{z}_t) > 0 \right) \right) \right]$$
For all $m \in [M(t-1, \delta)]$, let $X_t^m = \frac{(\hat{v}_t^m)^T(z^* - \hat{z}_t)}{\|\hat{z}_t - z^*\|_{\Sigma_t}}$. Then, we have $X_t^m \sim \mathcal{N}(0, 1)$ since $v_t^m \sim \Pi_t$. Under $\mathcal{E}_{t, \delta/2}$, we have $\|\hat{\theta}_t - \theta\|_{\Sigma_t^{-1}} \le \sqrt{2\beta(t-1, \delta/2)}$. Using that $z^* \ne \hat{z}_t$ and $\theta^T(z^* - \hat{z}_t) > 0$, we obtain

$$
\begin{align*}
& \exists z \neq \hat{z}_t, \quad (\hat{\theta}_t + \sqrt{c(t-1, \delta)}v_t^m)^T(z - \hat{z}_t) > 0 \\
\Leftarrow & \quad \sqrt{c(t-1, \delta)}(v_t^m)^T(z^* - \hat{z}_t) > -\theta^T(z^* - \hat{z}_t) + (\hat{\theta}_t - \theta)^T(\hat{z}_t - z^*) \\
\Leftarrow & \quad \sqrt{c(t-1, \delta)} \frac{(v_t^m)^T(z^* - \hat{z}_t)}{\|\hat{z}_t - z^*\|_{\Sigma_t}} \geq \|\hat{\theta}_t - \theta\|_{\Sigma_t^{-1}} \\
\Leftarrow & \quad X_t^m \geq \sqrt{\frac{2\beta(t-1, \delta/2)}{c(t-1, \delta)}}.
\end{align*}
$$

In the following, we consider $c(t, \delta) = \frac{\beta(t, \frac{\delta}{2})}{\log \frac{1}{2}}$ and $M(t, \delta) = \left\lceil \frac{\log(2t^s \zeta(s)/\delta)}{\delta q(\delta)} \right\rceil$ where $q(\delta) = R(\sqrt{2\log(1/\delta)})/\sqrt{2\pi} = \mathbb{P}_{X \sim \mathcal{N}(0,1)}(X > \sqrt{2\log(1/\delta)})/\delta$. Therefore, we have shown that

$$
\mathbb{P}_{\nu} \left( \tau_{\delta}^{\text{PS}} < +\infty, \hat{z}_{\tau_{\delta}^{\text{PS}}} \neq z^{*} \right) \leq \delta/2 + \sum_{t \geq 1} \exp \left( - \left[ \frac{\log(2(t-1)^s \zeta(s)/\delta)}{\mathbb{P}_{X \sim \mathcal{N}(0,1)}(X > \sqrt{2\log(1/\delta)})} \right] \mathbb{P}_{X \sim \mathcal{N}(0,1)}(X > \sqrt{2\log(1/\delta)}) \right).
$$

Using that $\lceil x \rceil \ge x$ and $\sum_{t \ge 1} 1/t^s = \zeta(s)$ concludes the proof of $\delta$-correctness, i.e. $\mathbb{P}_{\nu} (\tau_{\delta}^{\text{PS}} < +\infty, \hat{z}_{\tau_{\delta}^{\text{PS}}} \neq z^*) \le \delta$.

D SADDLE-POINT CONVERGENCE

In this section, we prove the following saddle-point convergence theorem.

**Theorem 3.** There exists events $(\Xi_t)_{t \ge 1}$ and $t_3 \in \mathbb{N}$ such that for all $t \ge t_3$,

$$2\text{GLR}(t) \geq t \max_{\omega \in \Delta_K} \inf_{\lambda \in \Theta \cap \text{Alt}(S^*)} \|\text{vec}(\theta - \lambda)\|_{\tilde{V}_{\omega}}^2 - 2f(t), \quad (13)$$

with $f(t) = \infty$ $o(t)$ and $\mathbb{P}_{\nu}(\Xi_t) \ge 1 - 5/t^2$. In particular for $t \ge t_3$, $\hat{S}_t = S^*(\theta)$.

To derive this result, we will first define some concentration events below :

$$ \bullet \Xi_{1,t} := \left\{ \forall s \le t, \left\| \mathrm{vec}(\hat{\theta}_s - \theta) \right\|_{\tilde{V}_s}^2 \le \beta(t, 1/t^2) :=: f_1(t) \right\} \text{ where } \beta(t, \delta) \text{ is defined as in Lemma 3} $$

We also define the following (high-probability) event:

• $\Xi_{2,t}$ as in Lemma 24.

D.1 Convergence of the Alternatives

We study the time after which the Pareto set is well estimated. The forced-exploration weight vector $\omega_{\text{exp}}$ allows to define a deterministic time after which the Pareto set is well estimated on a good event. We prove the following result.

**Lemma 8.** There exists $t_1 \in \mathbb{N}$ such that for all $t \ge t_1$, if the event $\Xi_{1,t} \cap \Xi_{2,t}$ holds then $\hat{S}_t = S^*(\theta)$.

*Proof.* Let $e_1, \dots, e_d$ denote the canonical $\mathbb{R}^d$ basis and let $a \in \mathcal{A}$. And assume in this section that $\Xi_{1,t} \cap \Xi_{2,t}$ holds with $t \ge t_0(\alpha)$ (as in Lemma 24). For any $c \in [d]$ we have by Cauchy-Schwartz inequality,

$$
\begin{align*}
|(e_i \otimes a)^T \mathrm{vec}(\hat{\theta}_t - \theta)| &\le \|\Sigma^{1/2} \otimes V_t^{-1/2} (e_c \otimes a)\|_2 \|\mathrm{vec}(\hat{\theta}_t - \theta)\|_{\Sigma^{-1} \otimes V_t} \\
&\le \|\Sigma^{1/2} \otimes V_t^{-1/2} (e_i \otimes a)\|_2 \sqrt{f_1(t)},
\end{align*}
$$
on the event $\Xi_{1,t}$. From the inequality above, we have for all $a \in \mathcal{A}$,

$$
\begin{align*}
\|(I_d \otimes a)^\mathrm{tr} \mathrm{vec}(\hat{\theta}_t - \boldsymbol{\theta})\|_2^2 f_1(t)^{-1} &\le \sum_{c \in [d]} (e_c \otimes a)^\mathrm{tr} (\Sigma \otimes V_t^{-1}) (e_c \otimes a) \\
&= \sum_{c \in [d]} \mathrm{Tr}((e_c \otimes a)^\mathrm{tr} (\Sigma \otimes V_t^{-1}) (e_c \otimes a)) \\
&= \mathrm{Tr}\left((\Sigma \otimes V_t^{-1}) \sum_{i \in [d]} (e_c \otimes a)(e_c \otimes a)^\mathrm{tr}\right) \\
&= \mathrm{Tr}\left((\Sigma \otimes V_t^{-1}) \sum_{i \in [d]} (e_c e_c^T) \otimes (aa^T)\right) \\
&= \mathrm{Tr}((\Sigma \otimes V_t^{-1})(I_d \otimes (aa^T))) = \mathrm{Tr}(\Sigma \otimes V_t^{-1} aa^T) \\
&= \mathrm{Tr}(\Sigma) a^\mathrm{tr} V_t^{-1} a
\end{align*}
$$

which follows from $\mathrm{Tr}(A \otimes B) = \mathrm{Tr}(A)\mathrm{Tr}(B)$. Then Lemma 24 on forced exploration ensures that for any $a$, $\|a\|_{V_t^{-1}}^2 \le 2t^{\alpha-1}\|a\|_{V(\omega_{\mathrm{exp}})^{-1}}^2$, thus

$$ \|(I_d \otimes a)^{\mathrm{tr}} \mathrm{vec}(\hat{\theta}_t - \boldsymbol{\theta})\|_2^2 f_1(t)^{-1} \le 2t^{\alpha-1} \mathrm{Tr}(\Sigma) \|a\|_{V(\omega_{\mathrm{exp}})^{-1}}^2 $$

Now, letting $\mu_a$ denote the mean vector of arm $a$, remark that by writing the linear model we have $\mu_a = (I_d \otimes a)^{\mathrm{tr}} \mathrm{vec}(\boldsymbol{\theta})$, so that letting $\hat{\mu}_{t,a} = (I_d \otimes a)^{\mathrm{tr}} \mathrm{vec}(\hat{\theta}_t)$ the estimated mean of arm $a$ at time $t$, we have proved that

$$ \|\mu_{t,a} - \mu_a\|_2 \le \|a\|_{V(\omega_{\mathrm{exp}})^{-1}} \sqrt{2t^{\alpha-1}\mathrm{Tr}(\Sigma)f_1(t)}. \quad (14) $$

For any two arms $a, a'$, let $M(a, a') := \|(\mu_a - \mu_{a'})_+\|_2$ and $M(a, a'; t) := \|(\hat{\mu}_{t,a} - \hat{\mu}_{t,a'})_+\|_2$ where $(w)_+ := \max(w, 0)$ for $w \in \mathbb{R}$ and it is applied component-wise for a vector. It is simple to prove that

$$
\begin{align*}
|M(a, a') - M(a, a'; t)| &\le \|\hat{\mu}_{t,a} - \mu_a\|_2 + \|\hat{\mu}_{t,a'} - \mu_{a'}\|_2 \\
&\le 2\sqrt{L_* t^{\alpha-1} \mathrm{Tr}(\Sigma) f_1(t)}
\end{align*}
$$

where we recall $L_* := 2 \max_{a \in \mathcal{A}} \|a\|_{V(\omega_{\mathrm{exp}})^{-1}}^2$. Therefore, if $t$ is such that

$$ 2\sqrt{L_* t^{\alpha-1} \mathrm{Tr}(\Sigma) f_1(t)} < \Delta_1 := \min_{a \in S^*(\boldsymbol{\theta})} \min_{a' \in \mathcal{Z} \setminus \{a\}} M(a, a') $$

then for all arms $x \in S^*(\boldsymbol{\theta})$ and $a' \ne a \in \mathcal{Z}$, we will have $M(a, a'; t) > 0$, i.e. $a$ is not dominated by $a'$: it is empirically optimal.

Similarly defining $m(a, a') := \min_{c \in [d]} (\mu_a(c) - \mu_{a'}(c))$ and $m(a, a'; t) := \min_{c \in [d]} (\hat{\mu}_{t,a}(c) - \hat{\mu}_{t,a'}(c))$, one can also prove that

$$
\begin{align*}
|m(a, a') - m(a, a'; t)| &\le \|\hat{\mu}_{t,a} - \mu_a\|_2 + \|\hat{\mu}_{t,a'} - \mu_{a'}\|_2 \\
&\le 2\sqrt{L_* t^{\alpha-1} \mathrm{Tr}(\Sigma) f_1(t)}
\end{align*}
$$

and observe that, if $m(a, a'; t) > 0$ then $a$ is dominated by $a'$, so that when

$$ 2\sqrt{L_* t^{\alpha-1} \mathrm{Tr}(\Sigma) f_1(t)} < \Delta_2 := \min_{a \in \mathcal{Z} \setminus S^*(\boldsymbol{\theta})} \max_{a' \in S^*(\boldsymbol{\theta})} m(a, a'), $$

any arm in $\mathcal{Z} \setminus S^*(\boldsymbol{\theta})$ will be empirically dominated. Therefore, we define a gap $\Delta_{\min}$ under which the Pareto set is well estimated as

$$ \Delta_{\min} := \min(\Delta_1, \Delta_2) $$

and we define

$$ t_1 := \inf \left\{ n \ge t_0(\alpha) : \forall t \ge n, \frac{\sqrt{L_* t^{\alpha-1} \mathrm{Tr}(\Sigma) f_1(t)}}{\Delta_{\min}} < \frac{1}{2} \right\}, \quad (15) $$

which is well-defined as $f_1(t)$ is at most logarithmic. Note that the gap $\Delta_{\min}$ is related to the gaps that appear in finite-time analysis of PSI algorithms (Auer et al., 2016; Kone et al., 2023). □
## D.2 Learning on Unbounded Sets

In this section, we properly define $\Theta_t$, $\eta_t$, and the results that allow this definition. Most game-based analyses will assume the parameter space is bounded Degenne et al. (2019, 2020); Li et al. (2024). In the (transductive) linear setting, this assumption is also used to control the self-normalized deviations of the least-square estimate.

In the unstructured setting, we show that this assumption can be relaxed by learning the norm of $\mu$ online. This relies on the following result, whose proof can be found in Appendix I.

**Lemma 9.** Let $\omega \in \mathbb{R}_+^K$. For any $\mu' := (\mu'_1 \dots \mu'_K)^\top \in \mathbb{R}^{K \times d}$, the following statement holds in the unstructured setting

$$ \inf_{\lambda \in \operatorname{Alt}(S^*(\mu'))} \|\operatorname{vec}(\lambda - \mu')\|_{\Sigma^{-1} \otimes \operatorname{diag}(\omega)}^2 = \inf_{\lambda \in \operatorname{Alt}(S^*(\mu')) \cap \{\lambda \mid \max_i \|\mu'_i - \lambda_i\|_{\Sigma^{-1}} < \epsilon\}} \|\operatorname{vec}(\lambda - \mu')\|_{\Sigma^{-1} \otimes \operatorname{diag}(\omega)}^2, \quad (16) $$

where $\epsilon := \max(2 \max_{i \notin S} \max_{j \in S} \|\mu'_i - \mu'_j\|_{\Sigma^{-1}}, \max_{i,j \in S^2} \|\mu'_i - \mu'_j\|_{\Sigma^{-1}})$, and $S = S^*(\mu')$.

Intuitively, it shows that for any parameter, the best response lies inside a compact region of the alternative space. We then use the procedure in Algorithm 2 to define $\Theta_t$ and $\eta_t$.

### Algorithm 2: Estimate and Halve

**Input:** $B_1 = \infty$, $C_1$, $p_1 = \infty$, confidence threshold $f_1$, covariance matrix $\Sigma$ 
**for** $t = 1, \dots, \mathit{do}$

// define ucb function

$$ h^t \leftarrow a \mapsto \sqrt{f_1(t)} \|a\|_{V_t^{-1}} + \|\operatorname{vec}(\hat{\mu}_t)\|_{\Sigma^{-1} \otimes aa^T}; $$

// compute upper confidence bound

$$ U_t \leftarrow \max \left\{ \max\{h^t(a_i - a_j) \mid (i, j) \in \hat{S}_t^2\}, 2 \max\{h^t(a_i - a_j) \mid (i, j) \in (\hat{S}_t^c, S_t)\} \right\}; $$

$$ u_t \leftarrow \max_{a \in \mathcal{A}} h^t(a) $$

if $U_t \le 2p_t$ then

$$ | p_{t+1} \leftarrow U_t $$

else

$$ | p_{t+1} \leftarrow p_t $$

end

if $u_t \le 2C_t$ then

$$ | C_{t+1} \leftarrow u_t; $$

else

$$ | C_{t+1} \leftarrow C_t; $$

end

$$ B_{t+1} \leftarrow C_{t+1} + p_{t+1} $$

$$ \eta_{t+1} \leftarrow \frac{1}{8B_{t+1}^2} $$

$$ \Theta_{t+1} = \{\lambda := (\lambda_1, \dots, \lambda_K) \mid \max_{a \in \mathcal{A}} \|\lambda_a\|_{\Sigma^{-1}} < B_{t+1}\} $$

end

The procedure initializes a bound $B_1$, which is updated whenever the confidence bound is halved. We then show that both $B_t$ and $\eta_t$ will stabilize on a good event. That is after a time $t_2 \in \mathbb{N}$, we will have $B_t = B_{t_2}$ for all $t \ge t_2$.

**Lemma 10.** In the unstructured setting, there exists $t_2 \in \mathbb{N}$ (as defined below) such that for all $t \ge t_2$, if the event $\Xi_{1,t} \cap \Xi_{2,t}$ holds then $\eta_t = \eta_{t_2}$ and $\Theta_t = \Theta_{t_2}$.

*Proof.* We will first show that when $\Xi_{1,t}$ holds, $U_t$ is an upper confidence bound on the quantity $\epsilon$ of Lemma 9. Let $t \ge t_1$ and assume $\Xi_{1,t}$ holds. By Lemma 8, we have $\hat{S}_t = S^*(\mu)$. Note that by keeping the notation of the linear setting, we have for all $i, j \in [K]$,

$$ \begin{aligned} \|\mu_i - \mu_j\|_{\Sigma^{-1}}^2 &= \|I_d \otimes (a_i - a_j)\operatorname{vec}(\mu)\|_{\Sigma^{-1}}^2 \\ &= \operatorname{vec}(\mu)^\top (I_d \otimes (a_i - a_j)^\top) \Sigma^{-1} (I_d \otimes (a_i - a_j))\operatorname{vec}(\mu) \\ &= \operatorname{vec}(\mu)^\top \Sigma^{-1} \otimes (a_i - a_j)(a_i - a_j)^\top \operatorname{vec}(\mu), \end{aligned} $$
which follows by properties of Kronecker product. Let $\tilde{a}_{i,j} = \Sigma^{-1/2} \otimes (a_i - a_j)$, so we have $\|\mu_i - \mu_j\|_{\Sigma^{-1}}^2 = \|\mathrm{vec}(\boldsymbol{\mu})\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top}^2$. Therefore, we should derive upper bound on $\|\mathrm{vec}(\boldsymbol{\mu})\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top}$. We have by triangle inequality

$$ \|\mathrm{vec}(\boldsymbol{\mu})\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top} \le \|\mathrm{vec}(\hat{\boldsymbol{\mu}}_t)\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top} + \|\mathrm{vec}(\boldsymbol{\mu} - \hat{\boldsymbol{\mu}}_t)\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top}, \quad (17) $$

then we rewrite the RHS. Note that

$$ \begin{aligned} \|\mathrm{vec}(\boldsymbol{\mu} - \hat{\boldsymbol{\mu}}_t)\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top}^2 &= \|\mathrm{vec}(\boldsymbol{\mu} - \hat{\boldsymbol{\mu}}_t)\|^\top \tilde{V}_t^{-1/2} \tilde{V}_t^{-1/2} (\tilde{a}_{i,j}\tilde{a}_{i,j}^\top) \mathrm{vec}(\boldsymbol{\mu} - \hat{\boldsymbol{\mu}}_t) \\ &\le \|\mathrm{vec}(\boldsymbol{\mu} - \hat{\boldsymbol{\mu}}_t)\|_{\tilde{V}_t} \|\mathrm{vec}(\boldsymbol{\mu} - \hat{\boldsymbol{\mu}}_t)\|_{(\tilde{a}_{i,j}\tilde{a}_{i,j}^\top)\tilde{V}_t^{-1}(\tilde{a}_{i,j}\tilde{a}_{i,j}^\top)}, \end{aligned} \quad (18) $$

which follows by Cauchy-Swartz inequality, and we have

$$ \begin{aligned} (\tilde{a}_{i,j}\tilde{a}_{i,j}^\top)\tilde{V}_t^{-1}(\tilde{a}_{i,j}\tilde{a}_{i,j}^\top) &= (\Sigma^{-1} \otimes (a_{i,j}\tilde{a}_{i,j}^\top))(\Sigma \otimes V_t^{-1})(\Sigma^{-1} \otimes (a_{i,j}\tilde{a}_{i,j}^\top)) \\ &= (a_{i,j}^\top V_t^{-1} a_{i,j}) \Sigma^{-1} \otimes (a_{i,j}\tilde{a}_{i,j}^\top) \\ &= \|a_{i,j}\|_{V_t^{-1}}^2 \tilde{a}_{i,j}\tilde{a}_{i,j}^\top \end{aligned} $$

and combining with (18) yields

$$ \|\mathrm{vec}(\boldsymbol{\mu} - \hat{\boldsymbol{\mu}}_t)\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top}^2 \le \|a_{i,j}\|_{V_t^{-1}} \|\mathrm{vec}(\boldsymbol{\mu} - \hat{\boldsymbol{\mu}}_t)\|_{\tilde{V}_t} \|\mathrm{vec}(\boldsymbol{\mu} - \hat{\boldsymbol{\mu}}_t)\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top}, $$

that is $\|\mathrm{vec}(\boldsymbol{\mu} - \hat{\boldsymbol{\mu}}_t)\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top} \le \|a_{i,j}\|_{V_t^{-1}} \|\mathrm{vec}(\boldsymbol{\mu} - \hat{\boldsymbol{\mu}}_t)\|_{\tilde{V}_t}$ and plugging back into (17), yields

$$ \|\mathrm{vec}(\boldsymbol{\mu})\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top} \le h^t(a_i, a_j) := \|\mathrm{vec}(\hat{\boldsymbol{\mu}}_t)\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top} + \|a_{i,j}\|_{V_t^{-1}} \sqrt{f_1(t)}, $$

on the event $\Xi_{1,t}$. Therefore, as $\hat{S}_t = S^*$, and by the line above, $U_t$ is an upper bound on $\epsilon := \max(2 \max_{i \notin S^*} \max_{j \in S^*} \|\mu_i - \mu_j\|_{\Sigma^{-1}}, \max_{i,j \in (S^*)^2} \|\mu_i - \mu_j\|_{\Sigma^{-1}})$ and we have (due to the terms $\|\mathrm{vec}(\hat{\boldsymbol{\mu}}_t)\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top}$ in its definition),

$$ U_t \ge \epsilon_t := \max \left( 2 \max_{i \notin \hat{S}_t} \max_{j \in \hat{S}_t} \|\hat{\mu}_{t,i} - \hat{\mu}_{t,j}\|_{\Sigma^{-1}}, \max_{i,j \in \hat{S}_t^2} \|\hat{\mu}_{t,i} - \hat{\mu}_{t,j}\|_{\Sigma^{-1}} \right) $$

We now justify that after some rounds, $B_t$ will not change anymore. For that, it suffices to show that both $p_t$ and $C_t$ will stabilize due to the estimate and halve procedure. To see this, note that

$$ \begin{aligned} \|\mathrm{vec}(\hat{\boldsymbol{\mu}}_t)\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top} &\le \|\mathrm{vec}(\boldsymbol{\mu})\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top} + \|\mathrm{vec}(\boldsymbol{\mu} - \hat{\boldsymbol{\mu}}_t)\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top} \\ &\le \|\mathrm{vec}(\boldsymbol{\mu})\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top} + \|a_{i,j}\|_{V_t^{-1}} \|\mathrm{vec}(\boldsymbol{\mu} - \hat{\boldsymbol{\mu}}_t)\|_{\tilde{V}_t} \quad \text{cf above} \\ &\le \|\mathrm{vec}(\boldsymbol{\mu})\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top} + \|a_{i,j}\|_{V_t^{-1}} \sqrt{f_1(t)}, \end{aligned} $$

on the event $\Xi_{1,t}$. Let $\mathcal{I} := \{(i,j) \in (S^*)^2, i \ne j\} \cup \{(i,j) \in ((S^*)^c, S)\}$ and define $t_2$ as

$$ t_2 := \inf \left\{ n : \forall t \ge n : \max_{(i,j) \in \mathcal{I}} \frac{\|a_{i,j}\|_{V_t^{-1}} \sqrt{f_1(t)}}{\|\mathrm{vec}(\boldsymbol{\mu})\|_{\tilde{a}_{i,j}\tilde{a}_{i,j}^\top}} < \frac{1}{2} \right\}, \quad (19) $$

which is well defined as the numerator is of order $\log(t)/t^{1-\alpha}$ due to forced exploration and the denominator is positive for $(i,j) \in \mathcal{I}$. From $t_2$ we have $U_t \le 2\epsilon$. Since on $\Xi_{1,t}$ $p_{t-1}$ is an upper bound on $\epsilon$ we have $\epsilon < p_{t-1}$, so $p_t$ is updated at time $t_2$ as $U_{t_2}/2 \le \epsilon$. For $t \ge t_2$ when $\Xi_{1,t}$ holds, since $p_{t_2} \le 2\epsilon$, it cannot be halved again, so on $\Xi_{1,t} \cap X_{i_2,t}$,

$$ \forall t \ge t_2, p_t = p_{t_2}, $$

and proceeding similarly for $C_t$ we prove that for $t \ge t_2$,

$$ B_t = B_{t_2} \quad \eta_t = \eta_{t_2}, \quad \Theta_t = \Theta_{t_2}. $$

We recall that in the transductive linear setting $\Theta_t = \Theta$ and

$$ \eta_t := \eta = \frac{1}{8L_A^2 L_\Theta^2}. \quad (20) $$

□
The following result derives from Lemma 29 and the definition of $\Lambda_t$.

**Corollary 1.** On the event $\Xi_{1,t} \cap \Xi_{2,t}$, for $t \ge t_2$, it holds that: in the unstructured setting or the transductive linear setting, for all $a \in A$, $\lambda \in \Lambda_t \mapsto \exp(-\eta_t ||vec(\theta - \lambda)||_{\Sigma^{-1}}^2 \otimes aa^T)$ is concave.

*Proof.* In the (transductive) linear setting, we have $\eta_t := \eta = \frac{1}{8L_A^2 L_\Theta^2}$ then from the definition of $L_A, L_\Theta$, the statement follows by Lemma 29. In the unstructured setting, we have by definition $\Lambda_t := \text{Alt}(\hat{S}_t) \cap \Theta_t$ with $\Theta_t := \{\lambda := (\lambda_1, \dots, \lambda_K) \mid \max_a ||\lambda_a||_{\Sigma^{-1}} < B_t\}$ and $\eta_t := \frac{1}{8B_t^2}$. Note that in the unstructured setting we have

$$ ||vec(\theta - \lambda)||_{\Sigma^{-1}}^2 \otimes aa^T = ||\mu_a - \lambda_a||_{\Sigma^{-1}}^2, $$

and, as $2B_t$ is an upper confidence bound on $\max_{a \in A} ||\mu_a - \lambda_a||_{\Sigma^{-1}}$, the conclusion follows again using Lemma 29.

□

## D.3 Analysis of the Sampling Rule

Letting $t_1, t_2$ as defined in (15), (19) we let $t_3 = \max(t_1, t_2)$. When $t \ge t_3$ and $\Xi_{1,t} \cap \Xi_{2,t}$ holds, $\hat{S}_t = S^*$ (Lemma 8) and $\Lambda_t := \Theta_t \cap \text{Alt}(S_t) = \Theta_t \cap \text{Alt}(S^*)$. As $\Theta_t \subset \Theta$ we have $\Lambda_t \subset \Theta \cap \text{Alt}(S^*)$. In the sequel, assume $t > t_3$ and $\Xi_{1,t} \cap \Xi_{2,t}$ holds. As $t \ge t_3$, both $\eta_t$ and $\Lambda_t$ remains constant (Lemma 10) thus, in this section we may simply refer to them as $\eta$ and $\Lambda$ respectively. In particular, $\Lambda$ is bounded and we have

$$ \Lambda := \Lambda_{t_3}, \eta := \eta_{t_3} \quad \text{and} \quad \max_{a \in A, \lambda \in \Lambda} ||vec(\theta - \lambda)||_{\tilde{a}\tilde{a}^T}^2 \le B, \quad \text{with} \\ B := \begin{cases} 4\tilde{L}_A^2 L_\Theta^2 & (\text{transductive linear setting}) \\ (B_{t_3} + \max_{a \in A} ||\mu_a||_{\Sigma^{-1}})^2 & (\text{unstructured setting}). \end{cases} \quad (21) $$

**Iterative saddle point convergence** This section analyzes the regrets of the min and max learners. The proof of Theorem 3 will follow. In this regard, we relate the regret of each learner to the saddle-point value by:

$$ \inf_{\lambda \in \Lambda_{t-1}} \|\text{vec}(\lambda - \hat{\theta}_{t-1})\|_{\tilde{V}_{t-1}}^2 \ge \sum_{s=t_3}^{t-1} \mathbb{E}_{\lambda \sim \pi_{s-1}} \left[ \|\text{vec}(\hat{\theta}_{s-1} - \lambda)\|_{\tilde{a}_s \tilde{a}_s^T}^2 \right] - r_1(t) \quad (22) $$

$$ \ge \sum_{s=t_3}^{t-1} \mathbb{E}_{\lambda \sim \pi_{s-1}, a \sim \tilde{\omega}_s} \left[ \|\text{vec}(\hat{\theta}_{s-1} - \lambda)\|_{\tilde{a}\tilde{a}^T}^2 \right] - r_1(t) - m(t) \quad (23) $$

$$ \ge \max_{\omega \in \Delta_K} \sum_{s=t_3}^{t-1} \mathbb{E}_{\lambda \sim \pi_{s-1}, a \sim \omega} \left[ \|\text{vec}(\hat{\theta}_{s-1} - \lambda)\|_{\tilde{a}\tilde{a}^T}^2 \right] - r_1(t) - r_2(t) - m(t) \quad (24) $$

$$ \ge \max_{\omega \in \Delta_K} \sum_{s=t_3}^{t-1} \mathbb{E}_{\lambda \sim \pi_{s-1}, a \sim \omega} \left[ \|\text{vec}(\theta - \lambda)\|_{\tilde{a}\tilde{a}^T}^2 \right] - r_1(t) - r_2(t) - m(t) - z(t) \quad (25) $$

$$ \ge \max_{\omega \in \Delta_K} \sum_{s=t_3}^{t-1} \inf_{p \in \mathcal{P}(\Lambda_s)} \mathbb{E}_{\lambda \sim p, a \sim \omega} \left[ \|\text{vec}(\theta - \lambda)\|_{\tilde{a}\tilde{a}^T}^2 \right] - r_1(t) - r_2(t) - m(t) - z(t) \\ = (t - t_3) \max_{\omega \in \Delta_K} \inf_{\lambda \in \Theta \cap \text{Alt}(S^*)} \|\text{vec}(\theta - \lambda)\|_{\tilde{V}_\omega}^2 - r_1(t) - r_2(t) - m(t) - z(t), $$

where the last inequality follows since $\Lambda_s \subset \Theta \cap \text{Alt}(S^*)$ for $s \ge t_3$ when $\Xi_{1,t} \cap \Xi_{2,t}$ holds. In the decomposition above, $r_1(t)$ (resp. $r_2(t)$) is the regret of the min (resp. max) learner, $m(t)$ is a martingale concentration term and $z(t)$ is an approximation error. Each of these terms will be controlled in the following subsections. In particular, we justify in the next paragraphs that they are sub-linear terms (i.e. $o_{t \to \infty}(t)$).

### D.3.1 Bounding the approximation error : step (24) to (25)

We note that by convexity of the squared norm we have

$$ \sum_{s=t_3}^{t-1} ||vec(\hat{\theta}_{s-1} - \lambda_s)||_{\tilde{a}\tilde{a}^T}^2 \ge \sum_{s=t_3}^{t-1} ||vec(\theta - \lambda_s)||_{\tilde{a}\tilde{a}^T}^2 + 2 \sum_{s=t_3}^{t-1} vec(\hat{\theta}_{s-1} - \theta)^T (\tilde{a}\tilde{a}^T) vec(\theta - \lambda_s) $$
then, let us define $y_s := (\tilde{a}\tilde{a}^\top)\mathrm{vec}(\theta - \lambda_s)$ and observe that by Cauchy-Schwartz inequality, we have for $\lambda_s \in \Lambda$,

$$
\begin{align*}
\mathrm{vec}(\theta - \hat{\theta}_{s-1})^\top y_s &\le \|\mathrm{vec}(\theta - \hat{\theta}_{s-1})\|_{\tilde{V}_{s-1}} \|y_s\|_{\tilde{V}_{s-1}^{-1}} \\
&= \|\mathrm{vec}(\theta - \hat{\theta}_{s-1})\|_{\tilde{V}_{s-1}} \sqrt{\|\mathrm{vec}(\theta - \lambda_s)^\top (\tilde{a}\tilde{a}^\top) \tilde{V}_{s-1}^{-1} (\tilde{a}\tilde{a}^\top) \mathrm{vec}(\theta - \lambda_s)\|} \\
&= \|\mathrm{vec}(\theta - \hat{\theta}_{s-1})\|_{\tilde{V}_{s-1}} \|a\|_{V_{s-1}^{-1}} \|\mathrm{vec}(\theta - \lambda_s)\|_{\tilde{a}\tilde{a}^\top} \quad (\text{Kronecker product}) \\
&\le \|\mathrm{vec}(\theta - \hat{\theta}_{s-1})\|_{\tilde{V}_{s-1}} \|a\|_{V_{s-1}^{-1}} \sqrt{B}
\end{align*}
$$

where we recall that $\tilde{a} := \Sigma^{-1/2} \otimes a$ and $\tilde{V}_s := \Sigma^{-1} \otimes V_s$. From the previous inequality, it follows that for any $\omega \in \Delta_K$ fixed, we have

$$
\sum_{s=t_3}^{t-1} \mathbb{E}_{\lambda \sim \pi_{s-1}, a \sim \omega} \left[ \| \mathrm{vec}(\hat{\theta}_{s-1} - \lambda) \|_{\tilde{a}\tilde{a}^\top}^2 \right] \\
\geq \sum_{s=t_3}^{t-1} \mathbb{E}_{\lambda \sim \pi_{s-1}, a \sim \omega} \left[ \| \mathrm{vec}(\theta - \lambda) \|_{\tilde{a}\tilde{a}^\top}^2 \right] - 2\sqrt{B} \mathbb{E}_{a \sim \omega} \left[ \sum_{s=t_3}^{t-1} \| \mathrm{vec}(\theta - \hat{\theta}_{s-1}) \|_{\tilde{V}_{s-1}} \| a \|_{V_{s-1}^{-1}} \right].
$$

We will bound the RHS of the equation and prove that it is sub-linear due to the tiny forced exploration. We define

$$
z(t) := 2\sqrt{B} \max_{\omega \in \Delta_K} \mathbb{E}_{a \sim \omega} \left[ \sum_{s=t_3}^{t-1} \| \mathrm{vec}(\theta - \hat{\theta}_{s-1}) \|_{\tilde{V}_{s-1}} \| a \|_{V_{s-1}^{-1}} \right] \quad (26)
$$

which we claim to be sub-linear as from Lemma 24,

$$
\sum_{s=t_3}^{t-1} \|\mathrm{vec}(\theta - \hat{\theta}_{s-1})\|_{\tilde{V}_{s-1}} \|a\|_{V_{s-1}^{-1}}
\le \sqrt{t f_1(t)} \left( L * \sum_{s=1}^{t} s^{\alpha-1} \right)^{1/2}
\le \sqrt{L * t^{1+\alpha} f_1(t)/\alpha,
$$

which is sub-linear for $\alpha \in (0, 1)$ so

$$
z(t) \le 2\sqrt{BL_*t^{1+\alpha}} f_1(t)/\alpha \quad (27)
$$

is sub-linear. The next paragraph shows that $m(t)$ is a sub-linear term.

D.3.2 Martingale Concentration: step (22) to (23)

Let us define the s-indexed stochastic process $(U_s)$ as

$$
U_s := \mathbb{E}_{\lambda \sim \pi_{s-1}} \left[ \| \mathrm{vec}(\hat{\theta}_{s-1} - \lambda) \|_{\tilde{a}_s \tilde{a}_s^\top}^2 \right] - \mathbb{E}_{\lambda \sim \pi_{s-1}, a \sim \tilde{\omega}_s} \left[ \| \mathrm{vec}(\hat{\theta}_{s-1} - \lambda) \|_{\tilde{a}\tilde{a}^\top}^2 \right].
$$

We recall that both $\omega_s$ and $\mathbb{E}_{\lambda \sim \pi_{s-1}} [\|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda)\|_{\tilde{a}\tilde{a}^\top}^2]$ (for fixed $\tilde{a}$) are $\mathcal{F}_{s-1}$-measurable, and $U_s$ is adapted to the filtration $(\mathcal{F}_s)_{s \ge 1}$. Moroever, simple calculation yields

$$
\mathbb{E}[U_s | \mathcal{F}_{s-1}] = 0,
$$

i.e $(U_s)_s$ is $\mathcal{F}$-martingale difference sequence and $|U_s| \le f_2(s, t)$ on the event $\Xi_{1,t} \cap \Xi_{2,t}$ (bounded below). Let us define the event

$$
\Xi_{3,t} := \left( \sum_{s=1}^{t} U_s \le m(t) := \sqrt{2 \log(t^2) \sum_{s=1}^{t} f_2(s,t)^2} \right) \quad (28)
$$

and observe that by Azuma's inequality it holds that $\mathbb{P}(\Xi_{3,t}) \ge 1 - 1/t^2$. It remains to show that on $\Xi_{3,t} \cap \Xi_{1,t}$, $m(t)$ can be bounded by a sub-linear term. Indeed, we have

$$
\begin{align*}
\|\mathrm{vec}(\hat{\theta}_s - \boldsymbol{\lambda})\|_{\tilde{a}\tilde{a}^\top} &\le \|\mathrm{vec}(\hat{\theta}_s - \boldsymbol{\theta})\|_{\tilde{a}\tilde{a}^\top} + \|\mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})\|_{\tilde{a}\tilde{a}^\top} \\
&\le \|\mathrm{vec}(\hat{\theta}_s - \boldsymbol{\theta})\|_{\tilde{V}_s} \|a\|_{V_s^{-1}} + \sqrt{B}
\end{align*}
$$
so that on $\Xi_{1,t} \cap \Xi_{2,t}$, $f_2(s,t) \le f_1(t)\|a\|_{V_s^{-1}}^2 + B + 2\sqrt{B}\|\mathrm{vec}(\hat{\theta}_s - \theta)\|_{\tilde{V}_s}\|a\|_{V_s^{-1}}$ then

$$f_2(s,t)^2 \le (2L_*f_1(t)s^{\alpha-1} + B + 2\sqrt{L_*Bf_1(t)s^{\alpha-1}})^2$$

so that

$$\sum_{s=1}^{t} f_2(s,t)^2 \le \mathcal{O}(f_1(t)^2 t^{2\alpha-1} + f_1(t)t^{\alpha} + \sqrt{f_1(t)}t^{(\alpha+1)/2} + f_1(t)\sqrt{f_1(t)}t^{(3\alpha-1)/2})$$

which is sub-linear, so that

$$m(t) = \mathcal{O}(\sqrt{f_1(t)^2 t \log(t^2)}). \qquad (29)$$

### D.3.3 Regret of the min learner

We analyze the regret of the min player which akin to continuous exponential weights. The goal is to show that we can have a sub-linear regret with a constant learning rate for the min learner. In this section we show the following guarantees for the min learner.

**Lemma 11.** For any $t \ge t_3$, the following holds on $\Xi_t$:

$$\sum_{s=t_3+1}^{t} \mathbb{E}_{\lambda \sim \pi_{s-1}} \left[ \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda)\|_{\tilde{a}_s \tilde{a}_s^\intercal}^2 \right] - \inf_{\lambda \in \Lambda} \|\mathrm{vec}(\lambda - \hat{\theta}_t)\|_{\tilde{V}_s}^2 \le \mathcal{O}\left(\sqrt{t \log^2(t)}\right).$$

*Proof.* At round $s$, the strategy $\lambda_s$ of the min player is drawn from the distribution $\pi_{s-1} := \mathcal{N}(\mathrm{vec}(\theta_s), \eta_s^{-1/2}\Sigma_s; \mathrm{vec}(\Lambda_s))$ for which the density at $\lambda$ is proportional to $\exp(-\frac{1}{2}\eta\|\mathrm{vec}(\hat{\theta}_s) - \lambda\|_{\tilde{V}_s}^2)$, with a normalizing constant

$$W_s := \int_{\mathrm{vec}(\Lambda_s)} \exp \left( -\frac{1}{2} \eta \|\mathrm{vec}(\hat{\theta}_s) - \lambda\|_{\tilde{V}_s}^2 \right) d\lambda.$$

We have for $s \ge t_3$,

$$\begin{align*}
\log \frac{W_s}{W_{s-1}} &= \log \frac{\int_{\mathrm{vec}(\Lambda)} \exp \left( -\frac{\eta \|\mathrm{vec}(\hat{\theta}_s) - \lambda\|_{\tilde{V}_s}^2}{2} \right) d\lambda}{W_{s-1}} \\
&= \log \frac{\int_{\mathrm{vec}(\Lambda)} \exp \left( -\frac{\eta \|\mathrm{vec}(\hat{\theta}_s) - \lambda\|_{\tilde{V}_s}^2}{2} + \frac{\eta \|\mathrm{vec}(\hat{\theta}_{s-1}) - \lambda\|_{\tilde{V}_{s-1}}^2}{2} - \frac{\eta \|\mathrm{vec}(\hat{\theta}_{s-1}) - \lambda\|_{\tilde{V}_{s-1}}^2}{2} \right) d\lambda}{W_{s-1}} \\
&= \log \mathbb{E}_{\lambda \sim \pi_{s-1}} \left[ \exp \left( -\frac{\eta \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda)\|_{\tilde{a}_s \tilde{a}_s^\intercal}^2}{2} + \underbrace{\frac{\eta \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda)\|_{\tilde{V}_s}^2}{2} - \frac{\eta \|\mathrm{vec}(\hat{\theta}_s - \lambda)\|_{\tilde{V}_s}^2}{2}}_{\Gamma_s(\lambda)/2} \right) \right] \\
&\le \frac{1}{2} \left( \log \mathbb{E}_{\lambda \sim \pi_{s-1}} \left[ \exp \left( -\eta \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda)\|_{\tilde{a}_s \tilde{a}_s^\intercal}^2 \right) \right] + \log \mathbb{E}_{\lambda \sim \pi_{s-1}} \left[ \exp(\eta \Gamma_s(\lambda)) \right] \right) \quad \text{(Cauchy-Schwartz)}
\end{align*}$$

At this step, the goal is to use the exp-concavity of the squared norm on bounded domains. However we will not use it directly with $\lambda \mapsto \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda)\|_{\tilde{a}_s \tilde{a}_s^\intercal}^2$, but using concentration, we relate the latter to $\lambda \mapsto \|\mathrm{vec}(\theta - \lambda)\|_{\tilde{a}_s \tilde{a}_s^\intercal}^2$. For this purpose, observe that by convex inequality on the squared norm,

$$\begin{align*}
-\|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda)\|_{\tilde{a}_s \tilde{a}_s^\intercal}^2 &\le -\|\mathrm{vec}(\theta - \lambda)\|_{\tilde{a}_s \tilde{a}_s^\intercal}^2 + 2\mathrm{vec}(\theta - \hat{\theta}_{s-1})^\intercal (\tilde{a}_s \tilde{a}_s^\intercal) \mathrm{vec}(\theta - \lambda) \\
&\stackrel{(i)}{\le} -\|\mathrm{vec}(\theta - \lambda)\|_{\tilde{a}_s \tilde{a}_s^\intercal}^2 + 2\|\mathrm{vec}(\theta - \hat{\theta}_{s-1})\|_{\tilde{V}_{s-1}} \|a_s\|_{V_{s-1}^{-1}} \|\mathrm{vec}(\theta - \lambda)\|_{\tilde{a}_s \tilde{a}_s^\intercal} \\
&\stackrel{(ii)}{\le} -\|\mathrm{vec}(\theta - \lambda)\|_{\tilde{a}_s \tilde{a}_s^\intercal}^2 + 2\|\mathrm{vec}(\theta - \hat{\theta}_{s-1})\|_{\tilde{V}_{s-1}} \|a_s\|_{V_{s-1}^{-1}} \sqrt{B} \\
&= -\|\mathrm{vec}(\theta - \lambda)\|_{\tilde{a}_s \tilde{a}_s^\intercal}^2 + \alpha_s
\end{align*}$$
where (i) follows from Cauchy-Schwartz, and (ii) follows from the definition of B and, we define

$$ \alpha_s := 2 \|\mathrm{vec}(\boldsymbol{\theta} - \hat{\boldsymbol{\theta}}_{s-1})\|_{\tilde{V}_{s-1}} \|a_s\|_{V_{s-1}^{-1}} \sqrt{B}. \quad (30) $$

Thus by taking the expectation on both sides, we have

$$ \begin{aligned} \mathbb{E}_{\boldsymbol{\lambda} \sim \pi_{s-1}} \left[ \exp \left( -\eta \|\mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 \right) \right] &\le \mathbb{E}_{\boldsymbol{\lambda} \sim \pi_{s-1}} \left[ \exp \left( -\eta \|\mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 \right) \right] \exp(\eta \alpha_s) \\ &\le \exp \left( \mathbb{E}_{\boldsymbol{\lambda} \sim \pi_{s-1}} \left[ -\eta \|\mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 \right] \right) \exp(\eta \alpha_s) \end{aligned} $$

where $\eta$ ensures that the square loss $(\boldsymbol{\lambda} \mapsto \|\mathrm{vec}(\boldsymbol{\lambda} - \boldsymbol{\theta})\|_{\tilde{a}_t \tilde{a}_t^\top}^2)$ is $\eta$-exp-concave on $\Lambda$ (Corollary 1). Therefore,

$$ \log \mathbb{E}_{\boldsymbol{\lambda} \sim \pi_{s-1}} \left[ \exp \left( -\eta \|\mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 \right) \right] \leq -\eta \mathbb{E}_{\boldsymbol{\lambda} \sim \pi_{s-1}} \left[ \|\mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 \right] + \eta \alpha_s. \quad (31) $$

Now we will return to the loss with $\hat{\boldsymbol{\theta}}_{s-1}$ on the RHS of the above inequality. Similarly to the previous derivation, we have by convexity

$$ \begin{aligned} -\|\mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 &\le -\|\mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 - 2\mathrm{vec}(\boldsymbol{\theta} - \hat{\boldsymbol{\theta}}_{t-1})^\top (\tilde{a}_s \tilde{a}_s^\top) \mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda}) \\ &\le -\|\mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 + 2\|\mathrm{vec}(\boldsymbol{\theta} - \hat{\boldsymbol{\theta}}_{s-1})\|_{\tilde{V}_{s-1}} \|a_s\|_{V_{s-1}^{-1}} \|\mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}, \end{aligned} $$

then observe that

$$ \begin{aligned} \|\mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 &\le \|\mathrm{vec}(\boldsymbol{\theta} - \hat{\boldsymbol{\theta}}_{s-1})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 + \|\mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 \\ &\le \|\mathrm{vec}(\boldsymbol{\theta} - \hat{\boldsymbol{\theta}}_{s-1})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 + \sqrt{B} \\ &\le \|\mathrm{vec}(\boldsymbol{\theta} - \hat{\boldsymbol{\theta}}_{s-1})\|_{\tilde{V}_{s-1}} \|a_s\|_{V_{s-1}^{-1}} + \sqrt{B}. \end{aligned} $$

Putting these displays together yields

$$ -\eta \mathbb{E}_{\boldsymbol{\lambda} \sim \pi_{s-1}} \left[ \|\mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 \right] \le -\eta \mathbb{E}_{\boldsymbol{\lambda} \sim \pi_{s-1}} \left[ \|\mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 \right] + \eta(2\alpha_s + \alpha_s^2/(2B)) $$

which combined with (31) yields

$$ \log \frac{W_{s+1}}{W_s} \le -\frac{\eta}{2} \mathbb{E}_{\boldsymbol{\lambda} \sim \pi_{s-1}} \left[ \|\mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 \right] + \eta(2\alpha_s + \alpha_s^2/(2B)) + \frac{1}{2} \log \mathbb{E}_{\boldsymbol{\lambda} \sim \pi_{s-1}} \left[ \exp(\eta \Gamma_s(\boldsymbol{\lambda})) \right]. \quad (32) $$

By telescoping, we have

$$ \log \frac{W_t}{W_{t_3}} = \sum_{s=t_3+1}^{t} \log \frac{W_s}{W_{s-1}} \quad (33) $$

$$ \le \sum_{s=t_3+1}^{t} \left( -\frac{\eta}{2} \mathbb{E}_{\boldsymbol{\lambda} \sim \pi_{s-1}} \left[ \|\mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 \right] + \frac{1}{2} \log \mathbb{E}_{\boldsymbol{\lambda} \sim \pi_{s-1}} \left[ \exp(\eta \Gamma_s(\boldsymbol{\lambda})) \right] \right) + \eta d_t \quad (34) $$

$$ = -\frac{\eta}{2} \sum_{s=t_3+1}^{t} \mathbb{E}_{\boldsymbol{\lambda} \sim \pi_{s-1}} \left[ \|\mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda})\|_{\tilde{a}_s \tilde{a}_s^\top}^2 \right] + \frac{1}{2} \sum_{s=t_3+1}^{t} \log \mathbb{E}_{\boldsymbol{\lambda} \sim \pi_{s-1}} \left[ \exp(\eta \Gamma_s(\boldsymbol{\lambda})) + \eta d_t \right] \quad (35) $$

where $d_t := \sum_{s=t_3+1}^{t} \eta(2\alpha_s + \alpha_s^2/(2B))$. We also define

$$ \vartheta_t := \sum_{s=t_3+1}^{t} \log \mathbb{E}_{\boldsymbol{\lambda} \sim \pi_{s-1}} \left[ \exp(\eta \Gamma_s(\boldsymbol{\lambda})) \right]. \quad (36) $$

On the other side, let $\gamma > 0$, $\tilde{\lambda}_t \in \mathrm{argmin}_{\boldsymbol{\lambda} \in \bar{\Lambda}} \|\mathrm{vec}(\boldsymbol{\lambda} - \hat{\boldsymbol{\theta}}_t)\|_{\tilde{V}_t}^2$. Since $\Lambda$ is a union of convex sets, there exists a convex
set $\mathcal{C} \subset \bar{\Lambda}$ such that $\tilde{\lambda}_t \in \mathcal{C}$. Then letting $\mathcal{N}_\gamma := \{(1-\gamma)\tilde{\lambda}_t + \gamma\lambda, \lambda \in \mathcal{C}\} = (1-\gamma)\tilde{\lambda}_t + \gamma\mathcal{C}$, it follows

$$
\begin{align*}
\log \frac{W_t}{W_{t_3}} &\ge \log \frac{\int_{\mathrm{vec}(\mathcal{C})} \exp\left(-\frac{\eta \|\mathrm{vec}(\hat{\theta}_t) - \lambda\|^2_{\tilde{V}_t}}{2}\right) d\lambda}{W_{t_3}} \\
&\ge \log \frac{\int_{\mathrm{vec}(\mathcal{N}_\gamma)} \exp\left(-\frac{\eta \|\mathrm{vec}(\hat{\theta}_t) - \lambda\|^2_{\tilde{V}_t}}{2}\right) d\lambda}{W_{t_3}} \quad \text{(convexity of } \mathcal{C}\text{)} \\
&= \log \frac{\int_{\mathrm{vec}(\mathcal{C})} \exp\left(-\frac{\eta \|\mathrm{vec}(\hat{\theta}_t - (1-\gamma)\tilde{\lambda}_t) - \lambda\|^2_{\tilde{V}_t}}{2}\right) d\lambda}{W_{t_3}} \\
&= \log \frac{\int_{\mathrm{vec}(\mathcal{C})} \gamma^{dh} \exp\left(-\frac{\eta \|(1-\gamma)\mathrm{vec}(\hat{\theta}_t - \tilde{\lambda}_t) + \gamma\mathrm{vec}(\hat{\theta}_t) - \lambda\|^2_{\tilde{V}_t}}{2}\right) d\lambda}{W_{t_3}} \\
&\ge \log \frac{\int_{\mathrm{vec}(\mathcal{C})} \gamma^{dh} \exp\left(-\frac{\eta \left(\|(1-\gamma)\mathrm{vec}(\hat{\theta}_t - \tilde{\lambda}_t)\|^2_{\tilde{V}_t} + \gamma\|\lambda - \mathrm{vec}(\hat{\theta}_t)\|^2_{\tilde{V}_t}\right)}{2}\right) d\lambda}{W_{t_3}} \quad \text{(convexity of squared norm)} \\
&= dh \log(\gamma) - \frac{\eta(1-\gamma)}{2} \|\mathrm{vec}(\hat{\theta}_t - \tilde{\lambda}_t)\|^2_{\tilde{V}_t} + \log \frac{\int_{\mathrm{vec}(\mathcal{C})} \exp\left(-\frac{\eta\gamma\|\lambda - \mathrm{vec}(\hat{\theta}_t)\|^2_{\tilde{V}_t}}{2}\right) d\lambda}{W_{t_3}} \\
&\ge dh \log(\gamma) - \frac{\eta(1-\gamma)}{2} \|\mathrm{vec}(\hat{\theta}_t - \tilde{\lambda}_t)\|^2_{\tilde{V}_t} - \frac{\eta\gamma \mathbb{E}_{\lambda \sim \mathcal{U}(\mathcal{C})} \left[ \|\mathrm{vec}(\lambda - \hat{\theta}_t)\|^2_{\tilde{V}_t} \right]}{2} + \log \frac{\mathrm{vol}(\mathcal{C}_*)}{W_{t_3}}
\end{align*}
$$

with $\Lambda = \bigcup_{i \in \mathcal{I}} \mathcal{C}_i$ where $(\mathcal{C}_i)_{i \in \mathcal{I}}$ are convex sets with non-empty interior and $\mathcal{C}_*$ is the set with minimum general volume. Combining the last inequality with (35) and letting $\gamma = 1/t$ yields

$$
\sum_{s=t_3}^{t} \mathbb{E}_{\lambda \sim \pi_{s-1}} \left[ \| \mathrm{vec}(\hat{\theta}_{s-1} - \lambda) \|_{\tilde{a}_s \tilde{a}_s^T}^2 \right] - \inf_{\lambda \in \Lambda} \| \mathrm{vec}(\lambda - \hat{\theta}_t) \|_{\tilde{V}_t}^2 \le \varrho_t,
$$

where

$$
\varrho_t = \frac{2}{\eta} \log(W_{t_3}) + 2d_t + \frac{\vartheta_t}{\eta} + \frac{2dh \log(t)}{\eta} - \frac{2}{\eta} \log \mathrm{vol}(C_*) + \frac{\mathbb{E}_{\lambda \sim \mathcal{U}(\mathcal{C})} [\|\mathrm{vec}(\lambda - \hat{\theta}_t)\|_{\tilde{V}_t}^2]}{t} \quad (37)
$$

Then, note that $\mathrm{vol}(C_*) > 0$, since $C_*$ has non-empty interior (Alt($S^*$) is a union of convex sets with non-empty interior and $\Theta_t$ is a ball). Further remark that $W_{t_3} \le \mathrm{vol}(\Lambda)$, which is finite by definition of $\Lambda$ (cf (21)). Moreover, for $\lambda \in \mathcal{C} \subset \Lambda$,

$$
\begin{aligned}
\|\mathrm{vec}(\boldsymbol{\lambda} - \hat{\boldsymbol{\theta}}_t)\|_{\tilde{V}_t} &\le \|\mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})\|_{\tilde{V}_t} + \|\mathrm{vec}(\hat{\boldsymbol{\theta}}_t - \boldsymbol{\theta})\|_{\tilde{V}_t} \\
&\le \sqrt{tB} + \sqrt{f_1(t)},
\end{aligned}
$$

which holds on the event $\Xi_{1,t}$. Summerizing the displays above, we have

$$
\varrho_t \le \frac{2}{\eta} \log \frac{\mathrm{vol}(\Lambda)}{\mathrm{vol}(C_*)} + 2d_t + \frac{\vartheta_t}{\eta} + \frac{2dh \log(t)}{\eta} + \left(\sqrt{tB} + \sqrt{f_1(t)}\right)^2/t \quad (38)
$$

$$
= \frac{\vartheta_t}{\eta} + 2d_t + \left( B + f_1(t)/t + \sqrt{Bf_1(t)/t} + \frac{2}{\eta} \log \frac{\mathrm{vol}(\Lambda)}{\mathrm{vol}(C_*)} + \frac{2dh \log(t)}{\eta} \right), \quad (39)
$$

and the leftmost term is $\mathcal{O}(1)$ (recall that $f_1(t)$ is logarithmic). Bounding $d_t$ and $\vartheta_t$ in Lemma 12 will conclude the proof by showing that $\varrho_t + d_t = \mathcal{O}(\sqrt{t \log^2 t})$. $\square$

**Lemma 12.** On the event $\Xi_{1,t} \cap \Xi_{4,t}$ (cf (43)), it holds that

$$
d_t \le 4h f_1(t) \log \left( \frac{\mathrm{Tr}(V_0) + t L_{\mathcal{A}}^2}{d \det(V_0)^{1/d}} \right) + 2 \sqrt{2h B t f_1(t) \log \left( \frac{\mathrm{Tr}(V_0) + t L_{\mathcal{A}}^2}{d \det(V_0)^{1/d}} \right)} = \mathcal{O} \left( \sqrt{t \log^2(t)} \right), \text{ and}
$$
$$ \vartheta_t = \mathcal{O}\left(\sqrt{t \log^2(t)}\right). $$

*Proof.* The first statement follows by elliptic potential (Lemma 23). We have $d_t := \sum_{s=t_3+1}^{t} (\alpha_s + \alpha_s^2/(2B))$ with $\alpha_s := 2\|\mathrm{vec}(\boldsymbol{\theta} - \hat{\boldsymbol{\theta}}_{s-1})\|_{\tilde{V}_{s-1}} \|a_s\|_{V_{s-1}^{-1}} \sqrt{B}$. We have on the event $\Xi_{1,t}$

$$ \begin{aligned} d_t &\le 2f_1(t) \sum_{s=t_3+1}^{t} \|a_s\|_{V_{s-1}^{-1}}^2 + 2\sqrt{Btf_1(t)} \left( \sum_{s=t_3+1}^{t} \|a_s\|_{V_{s-1}^{-1}}^2 \right)^{1/2} \\ &\le 4hf_1(t) \log \left( \frac{\mathrm{Tr}(V_0) + tL_A^2}{d \det(V_0)^{1/d}} \right) + 2\sqrt{2hBtf_1(t) \log \left( \frac{\mathrm{Tr}(V_0) + tL_A^2}{d \det(V_0)^{1/d}} \right)} \\ &= \mathcal{O}\left(\sqrt{t \log^2(t)}\right). \end{aligned} $$

We now prove the second part of the statement. We recall that

$$ \vartheta_t := \sum_{s=t_3+1}^{t} \log \mathbb{E}_{\boldsymbol{\lambda} \sim \pi_{s-1}} [\exp(\eta \Gamma_s(\boldsymbol{\lambda}))]. $$

Letting $\boldsymbol{\lambda}_s \sim \pi_s$, and using Fubini's lemma, $\vartheta_t$ rewrites as

$$ \vartheta_t = \log \left( \mathbb{E}_{\boldsymbol{\lambda}_{t_3+1}, \dots, \boldsymbol{\lambda}_t} \left[ \exp \left( \sum_{s=t_3+1}^{t} \Gamma_s(\boldsymbol{\lambda}_{s-1}) \right) \right] \right) $$

We will first bound $\sum_{s=t_3+1}^{t} \Gamma_s(\boldsymbol{\lambda}_{s-1})$ and derive a bound on $\vartheta_t$. We recall that for any $\boldsymbol{\lambda}$,

$$ \begin{aligned} \Gamma_s(\boldsymbol{\lambda}) &= \|\mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda})\|_{\tilde{V}_s}^2 - \|\mathrm{vec}(\hat{\boldsymbol{\theta}}_s - \boldsymbol{\lambda})\|_{\tilde{V}_s}^2 \\ &\stackrel{(i)}{\le} 2\mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda})^\mathrm{T} \tilde{V}_s \mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \hat{\boldsymbol{\theta}}_s) \\ &\stackrel{(ii)}{=} -2(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda})^\mathrm{T} [\Sigma^{-1} \otimes a_s] (\varepsilon_s + (I_d \otimes a_s^\mathrm{T}) \mathrm{vec}(\boldsymbol{\theta} - \hat{\boldsymbol{\theta}}_{s-1})) \\ &= 2\mathrm{vec}(\boldsymbol{\lambda} - \hat{\boldsymbol{\theta}}_{s-1})^\mathrm{T} (\tilde{a}_s \tilde{a}_s^\mathrm{T}) \mathrm{vec}(\boldsymbol{\theta} - \hat{\boldsymbol{\theta}}_{s-1}) + 2\mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda})^\mathrm{T} [\Sigma^{-1} \otimes a_s] \varepsilon_s \end{aligned} $$

where (i) follows by convexity of the squared norm and (ii) is due to Lemma 30. We recall that $\varepsilon_s$ is the centered (sub)Gaussian noise in the observations at time $s$, $\tilde{a}_s = \Sigma^{-1/2} \otimes a_s$ with $a_s$ the covariate of the arm pulled at time $s$. In the sequel, for any $\boldsymbol{\lambda}$, and at any time $s$, we define

$$ \psi_s(\boldsymbol{\lambda}) := \mathrm{vec}(\hat{\boldsymbol{\theta}}_{s-1} - \boldsymbol{\lambda})^\mathrm{T} [\Sigma^{-1} \otimes a_s] \varepsilon_s \quad \text{and} \quad \phi_s(\boldsymbol{\lambda}) := \mathrm{vec}(\boldsymbol{\lambda} - \hat{\boldsymbol{\theta}}_{s-1})^\mathrm{T} (\tilde{a}_s \tilde{a}_s^\mathrm{T}) \mathrm{vec}(\boldsymbol{\theta} - \hat{\boldsymbol{\theta}}_{s-1}), \quad (40) $$

then, it follows that

$$ \frac{1}{2} \sum_{s=t_3+1}^{t} \Gamma_s(\boldsymbol{\lambda}_{s-1}) \le \sum_{s=t_3+1}^{t} \phi_s(\boldsymbol{\lambda}_{s-1}) + \sum_{s=t_3+1}^{t} \psi_s(\boldsymbol{\lambda}_{s-1}). $$

We further define

$$ \Psi_t := \sum_{s=t_3+1}^{t} \psi_s(\boldsymbol{\lambda}_{s-1}) \quad \text{and} \quad \Phi_t := \sum_{s=t_3+1}^{t} \phi_s(\boldsymbol{\lambda}_{s-1}). \quad (41) $$

In the next step, we will bound each of these terms separately. In Lemma 13, we bound $\Phi_t$ and Lemma 14 uses martingale concentration to bound $\Psi_t$. $\square$

**Lemma 13.** The following statement holds on $\Xi_{1,t}$

$$ \Phi_t \le \sqrt{2hBtf_1(t) \log \left( \frac{\mathrm{Tr}(V_0) + tL_A^2}{d \det(V_0)^{1/d}} \right) + 2hf_1(t) \log \left( \frac{\mathrm{Tr}(V_0) + tL_A^2}{d \det(V_0)^{1/d}} \right)} = \mathcal{O}\left(\sqrt{t \log^2(t)}\right). $$
*Proof.* First observe that for any $\lambda$ and any time $s$

$$ \phi_s(\lambda) \le \|\mathrm{vec}(\theta - \lambda)\|_{\tilde{a}_s \tilde{a}_s^\intercal} \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{V}_{s-1}} \|a_s\|_{V_{s-1}^{-1}} + \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{V}_{s-1}}^2 \|a_s\|_{V_{s-1}^{-1}}^2, \quad (42) $$

which follows from

$$ \begin{aligned} \phi_s(\lambda) &= \mathrm{vec}(\lambda - \hat{\theta}_{s-1})^\intercal (\tilde{a}_s \tilde{a}_s^\intercal) \mathrm{vec}(\theta - \hat{\theta}_{s-1}) \\ &= \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda)\|_{\tilde{a}_s \tilde{a}_s^\intercal} \|\mathrm{vec}(\theta - \theta)\|_{\tilde{a}_s \tilde{a}_s^\intercal} \\ &\le \|\mathrm{vec}(\theta - \lambda)\|_{\tilde{a}_s \tilde{a}_s^\intercal} \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{a}_s \tilde{a}_s^\intercal} + \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{a}_s \tilde{a}_s^\intercal}^2, \end{aligned} $$

and note that

$$ \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{a}_s \tilde{a}_s^\intercal} \le \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{V}_{s-1}} \|a_s\|_{V_{s-1}^{-1}}. $$

Further, we have

$$ \begin{aligned} \Phi_t &:= \sum_{s=t_3+1}^{t} \phi_s(\lambda_{s-1}) \\ &\le \sum_{s=t_3+1}^{t} \left( \|\mathrm{vec}(\theta - \lambda_{s-1})\|_{\tilde{a}_s \tilde{a}_s^\intercal} \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{V}_{s-1}} \|a_s\|_{V_{s-1}^{-1}} + \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{V}_{s-1}}^2 \|a_s\|_{V_{s-1}^{-1}}^2 \right) \\ &\le \sqrt{B \sum_{s=t_3+1}^{t} \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{V}_{s-1}}^2} \sqrt{\sum_{s=t_3+1}^{t} \|a_s\|_{V_{s-1}^{-1}}^2} + f_1(t) \sum_{s=t_3+1}^{t} \|a_s\|_{V_{s-1}^{-1}}^2 \end{aligned} $$

where the first term is due to Cauchy-Schwartz inequality, and the second term uses concentration on the event $\Xi_{1,t}$. Further applying elliptic potential (Lemma 23), we have

$$ \Phi_t \le \sqrt{2hBtf_1(t) \log \left( \frac{\mathrm{Tr}(V_0) + tL_A^2}{d \det(V_0)^{1/d}} \right)} + 2hf_1(t) \log \left( \frac{\mathrm{Tr}(V_0) + tL_A^2}{d \det(V_0)^{1/d}} \right). \quad \square $$

Introducing the event

$$ \Xi_{4,t} := \left( \sum_{s=t_3+1}^{t} \psi_s \le f_4(t) := \sqrt{2 \sum_{s=t_3+1}^{t} v_s \log(t^2)} \right), \quad (43) $$

we prove the following result.

**Lemma 14.** The following statement holds on the event $\Xi_{1,t} \cap \Xi_{4,t}$

$$ \Phi_t \le \sqrt{2 \log(t^2) \sum_{s=t_3+1}^{t} v_s}, $$

with

$$ \sum_{s=t_3+1}^{t} v_s \le tB + 2hf_1(t) \log \left( \frac{\mathrm{Tr}(V_0) + tL_A^2}{d \det(V_0)^{1/d}} \right) + 2\sqrt{2hBtf_1(t) \log \left( \frac{\mathrm{Tr}(V_0) + tL_A^2}{d \det(V_0)^{1/d}} \right)}, $$

$$ \text{so that } \Phi_t \le \mathcal{O}\left(\sqrt{t \log(t)}\right). $$

*Proof.* To bound $\Psi_t$, we use martingale arguments by defining a slightly richer filtration. In the sequel, we denote by $\tilde{\mathcal{F}}_s := \sigma(\mathcal{F}_s, \lambda_s)$ the information accumulated up to time $s$ including $\lambda_s$, i.e $\lambda_s$ is $\tilde{\mathcal{F}}_s$-measurable. We simplify notation and let $\psi_s := \psi_s(\lambda_{s-1}) = \mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})^\intercal [\Sigma^{-1} \otimes a_s] \varepsilon_s$, where we recall that $\lambda_s$ is the strategy of the min player at time $s$. Then observe that $\psi_s$ is $\tilde{\mathcal{F}}_s$-measurable and we have

$$ \begin{aligned} \mathbb{E}[\psi_s | \tilde{\mathcal{F}}_{s-1}] &= \mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})^\intercal \mathbb{E}[[\Sigma^{-1} \otimes a_s] \varepsilon_s | \tilde{\mathcal{F}}_{s-1}] \\ &= 0 \end{aligned} $$
that is $(\psi_s)_s$ is a $\tilde{\mathcal{F}}$-martingale difference sequence with conditionally (sub)Gaussian increment of variance (proxy)

$$v_s := \|[\Sigma^{-1} \otimes a_s^T] \mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})\|_{\Sigma}^2.$$

Using Azuma's inequality, we have that $\mathbb{P}(\Xi_{4,t}) \ge 1 - 1/t^2$. We argue that $f_4(t)$ is a sub-linear term on $\Xi_{1,t}$. Indeed, observe that

$$ \begin{aligned} v_s &= \mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})^{\top}[\Sigma^{-1} \otimes a_s][\Sigma^{-1} \otimes a_s^{\top}]\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1}) \\ &= (1/\|a_s\|^2)\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})^{\top}[\Sigma^{-1} \otimes a_s][\Sigma \otimes a_s^{\top}][I_d \otimes a_s][\Sigma^{-1} \otimes a_s^{\top}]\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1}) \\ &= (1/\|a_s\|^2)\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})^{\top}[I_d \otimes a_s a_s^{\top}][\Sigma^{-1} \otimes a_s a_s^{\top}]\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1}) \\ &= \mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})^{\top}[\Sigma^{-1} \otimes a_s a_s^{\top}]\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1}) \\ &= \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})\|_{\tilde{a}_s \tilde{a}_s^{\top}}^2. \end{aligned} $$

We will now bound the right-hand side as :

$$ \begin{aligned} \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})\|_{\tilde{a}_s \tilde{a}_s^{\top}} &\le \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{a}_s \tilde{a}_s^{\top}} + \|\mathrm{vec}(\theta - \lambda_{s-1})\|_{\tilde{a}_s \tilde{a}_s^{\top}} \\ &\le \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{V}_{s-1}} \|a_s\|_{V_{s-1}^{-1}} + \sqrt{B}, \end{aligned} $$

thus

$$v_s \le B + \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{V}_{s-1}}^2 \|a_s\|_{V_{s-1}^{-1}}^2 + 2\sqrt{B} \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{V}_{s-1}} \|a_s\|_{V_{s-1}^{-1}},$$

then, using Cauchy-Schwartz and the elliptic potential lemma, it follows that on the event $\Xi_{1,t}$,

$$ \begin{aligned} \sum_{s=t_3+1}^{t} v_s &\le tB + f_1(t) \sum_{s=t_3+1}^{t} \|a_s\|_{V_{s-1}^{-1}}^2 + 2\sqrt{B} \left( \sum_{s=t_3+1}^{t} \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{V}_{s-1}}^2 \right)^{1/2} \left( \sum_{s=t_3+1}^{t} \|a_s\|_{V_{s-1}^{-1}}^2 \right)^{1/2}, \\ &\le tB + 2hf_1(t) \log \left( \frac{\mathrm{Tr}(V_0) + tL_A^2}{d \det(V_0)^{1/d}} \right) + 2\sqrt{2hBtf_1(t) \log \left( \frac{\mathrm{Tr}(V_0) + tL_A^2}{d \det(V_0)^{1/d}} \right)}, \end{aligned} $$

where the last inequality follows from elliptic potential lemma, which achieves the proof. □

Combining Lemma 12 and Equation (39), we have proved that on $\Xi_{1,t} \cap \Xi_{4,t}$ for $t > t_3$, we have $r_1(t) = O(\sqrt{t \log^2(t)})$. and this achieves the proof of the *min* player's regret, as we have bounded $r_1(t)$.

### D.3.4 Regret of the max-learner

We study the max-learner's regret, aiming to prove that $r_2(t)$ is a sub-linear term. Formally, introducing the event (with $Z_s(w)$ as in (45) and $w_s^t$ defined in (46))

$$ \Xi_{5,t} := \left( \sup_{\omega \in \mathcal{V}(\varepsilon)} \sum_{s=t_3+1}^{t} Z_s(\omega) \le f_5(t) \right) \quad \text{with} \quad f_5(t) := \sqrt{2 \left( \sum_{s=t_3+1}^{t} (w_s^t(a))^2 \right) \log(|\mathcal{V}(\varepsilon)|t^2)}, \quad (44) $$

in this section, we prove that

**Lemma 15.** On the event $\Xi_{1,t} \cap \Xi_{5,t}$, it holds that

$$ \sup_{\omega \in \Delta_K} \sum_{s=t_3+1}^{t-1} (\tilde{g}_s(\omega) - \tilde{g}_s(\omega_s)) \le O\left(\sqrt{t \log^2(t)} + \log(t)t^{1-\alpha}\right), $$

$$ \text{with } \tilde{g}_s(\omega) := \mathbb{E}_{\lambda \sim \pi_{s-1}, a \sim \omega} \left[ \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda)\|_{\tilde{a}\tilde{a}^{\top}}^2 \right]. $$
Proof. We recall that $\omega \in \Delta_K$ is considered a distribution over $\mathcal{A}$ and for any $a \in \mathcal{A}$, $\tilde{a} := \Sigma^{-1/2} \otimes a$. Let us define for any $\omega \in \Delta_K$,

$$ Z_s(\omega) := \mathbb{E}_{\lambda \sim \pi_{s-1}, a \sim \omega} \left[ \left\| \mathrm{vec}(\hat{\theta}_{s-1} - \lambda) \right\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] - \mathbb{E}_{a \sim \omega} \left[ \left\| \mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1}) \right\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] - \mathbb{E}_{\lambda \sim \pi_{s-1}, a \sim \tilde{\omega}_s} \left[ \left\| \mathrm{vec}(\hat{\theta}_{s-1} - \lambda) \right\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] + \mathbb{E}_{a \sim \tilde{\omega}_s} \left[ \left\| \mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1}) \right\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right]. \quad (45) $$

Then observe that $(Z_s(\omega))_s$ is a $\tilde{\mathcal{F}}$-adapted process and and it is a $\tilde{\mathcal{F}}$-martingale difference sequence for any fixed $\omega$ since by direct algebra, $\mathbb{E}[Z_s(\omega) | \tilde{\mathcal{F}}_{s-1}] = 0$. Further note that, for $\lambda \in \Lambda_s$,

$$ \begin{aligned} \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda)\|_{\tilde{a}\tilde{a}\tilde{\tau}} &\le \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{a}\tilde{a}\tilde{\tau}} + \|\mathrm{vec}(\theta - \lambda)\|_{\tilde{a}\tilde{a}\tilde{\tau}}, \\ &\le \|\mathrm{vec}(\hat{\theta}_{s-1} - \theta)\|_{\tilde{V}_{s-1}} \|a\|_{V_{s-1}^{-1}} + \sqrt{B_s}. \end{aligned} $$

Therefore, on the event $\Xi_{1,t}$, we have $|Z_s(\omega)| \le 2 \max_{a \in \mathcal{A}} (w_t^s(a))^2$, where

$$ w_t^s(a) := 2\sqrt{f_1(t)} \|a\|_{V_{s-1}^{-1}} + \sqrt{B_2} \quad (46) $$

and remark that $B_2 < \infty$. Let $\varepsilon > 0$ and $\mathcal{V}(\varepsilon)$ be an $\varepsilon$-cover of $\Delta_K$, $\mathcal{N}(\varepsilon) = |\mathcal{V}(\varepsilon)|$. Note that by Azuma-Hoeffding's inequality, it is simple to see that $\mathbb{P}(\Xi_{5,t} \ge 1 - 1/t^2)$. Direct development yields

$$ \begin{aligned} (*) &:= \sum_{s=t_3+1}^{t-1} (\tilde{g}_s(\omega) - \tilde{g}_s(\omega_s)) \\ &= \sum_{s=t_3+1}^{t-1} Z_s(\omega) + \sum_{s=t_3+1}^{t-1} \mathbb{E}_{a \sim \omega} \left[ \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] - \mathbb{E}_{a \sim \tilde{\omega}_s} \left[ \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] \\ &= \sum_{s=t_3+1}^{t-1} \mathbb{E}_{a \sim \omega} \left[ \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] - \mathbb{E}_{a \sim \omega_s} \left[ \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] + \sum_{s=t_3+1}^{t-1} Z_s(\omega) + \sum_{s=t_3+1}^{t-1} \varphi_s, \end{aligned} $$

where

$$ \begin{aligned} \varphi_s &= \mathbb{E}_{a \sim \omega_s} \left[ \left\| \mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1}) \right\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] - \mathbb{E}_{a \sim \tilde{\omega}_s} \left[ \left\| \mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1}) \right\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] \\ &= \gamma_s \left( \mathbb{E}_{a \sim \omega_s} \left[ \left\| \mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1}) \right\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] - \mathbb{E}_{a \sim \omega_{\mathrm{exp}}} \left[ \left\| \mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1}) \right\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] \right), \\ &\le \gamma_s \max_{a \in \mathcal{A}} (w_t^s(a))^2 \end{aligned} $$

where the last inequality holds on the event $\Xi_{1,t}$. Therefore, on the event $\Xi_{5,t} \cap \Xi_{1,t}$, for all $\omega \in \mathcal{V}(\varepsilon)$, it holds that

$$ (*) \le h(t) + f_5(t) + \sum_{s=2}^{t-1} \gamma_s \max_{a \in \mathcal{A}} (w_t^s(a))^2 + \sum_{s=2}^{t-1} \mathbb{E}_{a \sim \omega} \left[ \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] - \mathbb{E}_{a \sim \omega_s} \left[ \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right], \quad (47) $$

where the rightmost term of Equation (47) is related to the regret of AdaHedge and

$$ \begin{aligned} h(t) &:= \sum_{s=2}^{t_3} \mathbb{E}_{a \sim \omega_s} \left[ \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] - \mathbb{E}_{a \sim \omega} \left[ \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right], \\ &\le \sum_{s=2}^{t_3} \max_{a \in \mathcal{A}} (w_t^s(a))^2, \\ &\le \mathcal{O}(f_1(t)), \end{aligned} \quad (48) $$

which follows by expanding the sum, and since $t_3$ fixed.
**Lemma 16 (De Rooij et al. (2014)).** AdaHedge run with gains $g_s(\omega) := \mathbb{E}_{a \sim \omega} [\|\mathrm{vec}(\hat{\theta}_s - \lambda_s)\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2]$ satisfies the following regret bound

$$ \max_{\omega \in \Delta_K} \sum_{s=2}^{t-1} \mathbb{E}_{x \sim \omega} \left[ \left\| \mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1}) \right\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] - \mathbb{E}_{a \sim \omega_s} \left[ \left\| \mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1}) \right\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] \le 2\sigma_t \sqrt{\log(|\mathcal{A}|t)} + 16\sigma_t \left( 2 + \frac{\log|\mathcal{A}|}{3} \right) $$
where $\sigma_t := \max_{s \le t, a \in \mathcal{A}} \|\mathrm{vec}(\hat{\theta}_{s-1} - \lambda_{s-1})\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2$.

We can bound $\sigma_t$ as

$$ \begin{aligned} \sigma_t &\le \max_{a \in \mathcal{A}, s \le t} (w_t^s(a))^2 \\ &\le \max_{a \in \mathcal{A}, s \le t} (2\sqrt{f_1(t)}\|a\|_{V_0^{-1}} + \sqrt{B_2})^2 \\ &= (2\sqrt{f_1(t)}\max_{a \in \mathcal{A}} \|a\|_{V_0^{-1}} + \sqrt{B_2})^2. \end{aligned} \quad (49) $$

Thus, we obtain for all $\omega \in \mathcal{V}(\varepsilon)$,

$$ (*) \le f_5(t) + h(t) + \sum_{s=1}^{t-1} \gamma_s(w_t^s(a))^2 + 2\sigma_t \sqrt{\log(|\mathcal{A}|t)} + 16\sigma_t(2 + \log(|\mathcal{A}|)/3). \quad (50) $$

In the next step, we relate the supremum over $\mathcal{V}(\varepsilon)$ to the supremum over $\Delta_K$ by using the covering argument and a Lipschitz condition. Letting $\omega, \omega' \in \Delta_K$, observe that

$$ \begin{aligned} \tilde{g}_s(\omega) - \tilde{g}_s(\omega') &= \sum_{a \in \mathcal{A}} (\omega_a - \omega'_a) \mathbb{E}_{\lambda \sim \pi_{s-1}} \left[ \left\| \mathrm{vec}(\hat{\theta}_{s-1} - \lambda) \right\|_{\tilde{a}\tilde{a}\tilde{\tau}}^2 \right] \\ &\le \|\omega - \omega'\|_1 (w_t^s(a))^2 \end{aligned} $$

thus, as $\mathcal{V}(\varepsilon)$ is an $\varepsilon$-cover of $\Delta_K$, for any $\omega \in \Delta_K$, there exists $\omega' \in \mathcal{V}(\varepsilon)$ such that $\|\omega - \omega'\|_1 \le \varepsilon$ and $\tilde{g}_s(\omega) \le \tilde{g}_s(\omega') + \varepsilon(w_t^s(a))^2$. All put together, we have

$$ \begin{aligned} \sup_{\omega \in \Delta_K} \sum_{s=1}^{t-1} (\tilde{g}_s(\omega) - \tilde{g}_s(\omega_s)) &= \sup_{\omega \in \Delta_K} \min_{\omega' \in \mathcal{V}(\varepsilon)} \sum_{s=1}^{t-1} (\tilde{g}_s(\omega) - \tilde{g}_s(\omega') + \tilde{g}_s(\omega') - \tilde{g}_s(\omega_s)) \\ &\le \sup_{\omega' \in \mathcal{V}(\varepsilon)} \sum_{s=1}^{t-1} (\tilde{g}_s(\omega') - \tilde{g}_s(\omega_s)) + \varepsilon \sum_{s=1}^{t-1} (w_t^s(a))^2 \\ &\le f_5(t) + h(t) + \sum_{s=1}^{t-1} \gamma_s(w_t^s(a))^2 + \sqrt{1/t} \sum_{s=1}^{t-1} (w_t^s(a))^2 \\ &\quad + 2\sigma_t \sqrt{\log(|\mathcal{A}|t)} + 16\sigma_t(2 + \log(|\mathcal{A}|)/3), \end{aligned} $$

where we take $\varepsilon = 1/\sqrt{t}$ and recall that $\mathcal{N}(\varepsilon) \le (3/\varepsilon)^K$. Replacing with the expression of each term we have

$$ \begin{aligned} f_5(t) &\le \sqrt{4 \left( \sum_{s=t_3+1}^{t} \max_{a \in \mathcal{A}} (w_t^s(a))^2 \right) \log(|\mathcal{V}(\varepsilon)|t^2)} \\ &\le \sqrt{4K \left( \sum_{s=t_3+1}^{t} \max_{a \in \mathcal{A}} (w_t^s(a))^2 \right) \log(3t^2\sqrt{t})} \\ &\le \sqrt{10Kt(2\sqrt{f_1(t)}\max_{a \in \mathcal{A}} \|a\|_{V_0^{-1}} + \sqrt{B_2})^2 \log(3t)} = \mathcal{O}(\sqrt{t \log^2(t)}) \end{aligned} \quad (51) $$

similarly, we have

$$ \begin{aligned} \sum_{s=1}^{t-1} \gamma_s(w_t^s(a))^2 &\le (2\sqrt{f_1(t)}\max_{a \in \mathcal{A}} \|a\|_{V_0^{-1}} + \sqrt{B_2})^2 \sum_{s=1}^{t-1} s^{-\alpha} \\ &\le (2\sqrt{f_1(t)}\max_{a \in \mathcal{A}} \|a\|_{V_0^{-1}} + \sqrt{B_2})^2 \frac{t^{1-\alpha}}{1-\alpha} = \mathcal{O}(\log(t) t^{1-\alpha}). \end{aligned} \quad (52) $$
Combining Equations (48), (49), (51) and (52) yields the claimed statement.

This achieves the proof of the sublinear regret for the max player.

### D.4 Proof of Theorem 3

Introducing the event

$$ \Xi_t = \bigcap_{i=1}^{5} \Xi_{i,t}, \qquad (53) $$

we have proven in the sections above that there exists a time $t_3 \in \mathbb{N}$ such that when $\Xi_t$ holds,

$$ \begin{aligned} \inf_{\lambda \in \Lambda_{t-1}} \|\mathrm{vec}(\lambda - \hat{\theta}_{t-1})\|_{\tilde{V}_{t-1}}^2 &\ge (t-t_3) \max_{\omega \in \Delta_K} \inf_{\lambda \in \Theta \cap \mathrm{Alt}(S^*)} \|\mathrm{vec}(\theta - \lambda)\|_{\tilde{V}_{\omega}}^2 - r_1(t) - r_2(t) - m(t) - z(t), \\ &= (t-1)T^*(\theta)^{-1} - 2 \underbrace{((1+t_3)T^*(\theta)^{-1} + r_1(t) + r_2(t) + m(t) + z(t))}_{f(t-1)}/2, \quad (54) \end{aligned} $$

and we further proved that $f(t)$ is sub-linear (Equation (27), Equation (29), Lemma 11, Lemma 15). To conclude the proof of Theorem 3, it remains to prove that the LHS of Equation (54) is the GLR at time $t-1$. Indeed, in the transductive setting, as $\Lambda_{t-1} = \Theta \cap \mathrm{Alt}(\hat{S}_{t-1})$, the result is immediate. In the unstructured setting, the result follows by Lemma 10 applied to $\hat{\mu}_t$, for $t \ge t_3$ on the event $\Xi_{1,t} \cap \Xi_{2,t} \subset \Xi_t$. Further observe that by their definition we have for each $i \in [5]$, $\mathbb{P}_{\nu}(\Xi_{i,t}) \le 1/t^2$. Therefore,

$$ \mathbb{P}_{\nu}(\Xi_t) \ge 1 - 5/t^2 $$

and the conclusion follows.

## E LIKELIHOOD RATIO AND POSTERIOR PROBABILITY OF ERROR

In this section, we prove some results related to the generalized likelihood ratio, the lower bound and the posterior probability of error.

### E.1 Lower Bound

We discuss the proof of the lower bound of PSI in this section.

**Lemma 1.** An algorithm which is $\delta$-correct on all problems in $\mathcal{D}^K$ satisfies that, for all $\nu \in \mathcal{D}^K$ with regression matrix $\theta \in \Theta$, $\mathbb{E}_{\nu}[\tau_{\delta}] \ge T^*(\theta) \log(1/(2.4\delta))$ where $T^*(\theta)$ is a characteristic time whose inverse is defined as

$$ 2T^*(\theta)^{-1} := \sup_{w \in \Delta_K} \inf_{\lambda \in \Theta \cap \mathrm{Alt}(S^*(\theta))} \|\mathrm{vec}(\theta - \lambda)\|_{\Sigma^{-1} \otimes V_w}^2, $$

and its maximizer set of optimal allocations is $w^*(\theta)$.

*Proof.* The proof of this lemma follows the same lines as Theorem 1 of Garivier and Kaufmann (2016) from which it is simple to prove that the stopping time $\tau_{\delta}$ of any $\delta$-correct algorithm for PSI satisfies

$$ \mathbb{E}_{\nu}[\tau_{\delta}] \ge T^*(\theta) \log(1/(2.4\delta)), $$

where, for the problems in $\mathcal{D}^K$,

$$ T^*(\theta)^{-1} := \sup_{\omega \in \Delta_K} \inf_{\lambda \in \Theta \cap \mathrm{Alt}(S^*(\theta))} \sum_{a \in \mathcal{A}} \frac{1}{2} \omega_a \|(\theta - \lambda)^{\mathrm{T}} a\|_{\Sigma^{-1}}^2. $$

Then, observe that by the properties of vectorization and Kronecker product,

$$ \begin{aligned} \mathrm{vec}(\theta^{\mathrm{T}} a) &= \mathrm{vec}(a^{\mathrm{T}} \theta), \\ &= (I_d \otimes a^{\mathrm{T}}) \mathrm{vec}(\theta), \end{aligned} $$
which follows from $\mathrm{vec}(AB) = (I_d \otimes A)\mathrm{vec}(B)$ for $A \in \mathbb{R}^{p,q}, B \in \mathbb{R}^{q,d}$. Therefore,

$$ \begin{aligned} \| (\boldsymbol{\theta} - \boldsymbol{\lambda})^{\mathrm{T}} a \|_{\Sigma^{-1}}^{2} &= \mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})^{\mathrm{T}} (I_d \otimes a^{\mathrm{T}})^{\mathrm{T}} \Sigma^{-1} (I_d \otimes a^{\mathrm{T}}) \mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda}) \\ &= \mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})^{\mathrm{T}} ((I_d \otimes a) \Sigma^{-1} (I_d \otimes a^{\mathrm{T}})) \mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda}), \end{aligned} $$

further note that

$$ \begin{aligned} (I_d \otimes a) \Sigma^{-1} (I_d \otimes a^{\mathrm{T}}) &= \frac{1}{a^{\mathrm{T}} a} (I_d \otimes a) (\Sigma^{-1} \otimes a^{\mathrm{T}} a) (I_d \otimes a_i^{\mathrm{T}}) \\ &\stackrel{(i)}{=} \frac{1}{a^{\mathrm{T}} a} \Sigma^{-1} \otimes (a a^{\mathrm{T}} a a_i^{\mathrm{T}}) \\ &= \Sigma^{-1} \otimes (a a^{\mathrm{T}}), \end{aligned} $$

where (i) follows from $(A \otimes B)(C \otimes D) = (AC) \otimes (BD)$. All put together, we have

$$ \begin{aligned} T^*(\boldsymbol{\theta})^{-1} &:= \sup_{\boldsymbol{\omega} \in \Delta_K} \inf_{\boldsymbol{\lambda} \in \Theta \cap \mathrm{Alt}(S^*(\boldsymbol{\theta}))} \sum_{a \in \mathcal{A}} \frac{1}{2} \omega_a \|\mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})\|_{\Sigma^{-1} \otimes aa^{\mathrm{T}}}^2 \\ &= \frac{1}{2} \sup_{\boldsymbol{\omega} \in \Delta_K} \inf_{\boldsymbol{\lambda} \in \Theta \cap \mathrm{Alt}(S^*(\boldsymbol{\theta}))} \|\mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})\|_{\Sigma^{-1} \otimes V_{\omega}}^2, \end{aligned} $$

with $V_{\omega} := \sum_{a \in \mathcal{A}} \omega_a a a^{\mathrm{T}}$.

□

## E.2 Posterior Error Probability

**Lemma 17.** Under the unstructured assumption or the linear transductive setting, and for any convex set $\Theta$, it holds at each round that

$$ \mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\Theta \cap \mathrm{Alt}(\hat{S}_t)) \le \alpha_t \exp \left( - \frac{\mathrm{GLR}(t)}{c(t-1, \delta)} \right), $$

with $2\alpha_t = p_t(p_t - 1) + (|\mathcal{Z}| - p_t)d^{p_t}$, with $p_t := |\hat{S}_t|$, the size of the empirical Pareto set at time t.

*Proof.* The proof of this lemma relies on the properties of $\Theta \cap \mathrm{Alt}(\hat{S}_t)$ and Gaussian concentration. Lemma 26 proves that $\mathrm{Alt}(\hat{S}_t) = \cup_{i \in [n_t]} C_i$ where $C_1, \dots, C_n$ are convex sets and $n_t := p_t(p_t - 1) + (|\mathcal{Z}| - p_t)d^{p_t}$. Since, $\hat{\Pi}_t | \mathcal{F}_t = \mathcal{N}(\mathrm{vec}(\boldsymbol{\theta}_t), c(t-1, \delta)\Sigma \otimes V_t^{-1})$, letting $\mathrm{vec}(\boldsymbol{\lambda}_t) | \mathcal{F}_t \sim \mathcal{N}(\mathrm{vec}(\boldsymbol{\theta}_t), c(t-1, \delta)\Sigma \otimes V_t^{-1})$, we have

$$ \mathbb{P}(\boldsymbol{\lambda}_t \in C_i | \mathcal{F}_t) = \mathbb{P}(\mathrm{vec}(\boldsymbol{\lambda}_t) \in \mathrm{vec}(C_i) | \mathcal{F}_t) $$

and by Lemma 27, and convexity of $\mathrm{vec}(C_i)$, it follows that

$$ \mathbb{P}(\boldsymbol{\lambda}_t \in C_i | \mathcal{F}_t) \le \frac{1}{2} \exp \left( - \inf_{\boldsymbol{\lambda} \in C_i} \frac{\|\mathrm{vec}(\hat{\boldsymbol{\theta}}_t - \boldsymbol{\lambda})\|_{\Sigma \otimes V_t^{-1}}^2}{2c(t-1, \delta)} \right), $$

therefore, by union bound and convexity of $\Theta \cap C_i$ (since $\Theta$ is convex), it follows that

$$ \begin{aligned} \mathbb{P}_{\hat{\Pi}_t | \mathcal{F}_t}(\Theta \cap \mathrm{Alt}(\hat{S}_t)) &:= \mathbb{P}(\boldsymbol{\lambda}_t \in \cup_{i \in [n_t]} (\Theta \cap C_i) | \mathcal{F}_t) \\ &\le \frac{1}{2} \sum_{i \in [n_t]} \exp \left( - \inf_{\boldsymbol{\lambda} \in \Theta \cap C_i} \frac{\|\mathrm{vec}(\hat{\boldsymbol{\theta}}_t - \boldsymbol{\lambda})\|_{\Sigma \otimes V_t^{-1}}^2}{2c(t-1, \delta)} \right) \\ &\le \frac{n_t}{2} \exp \left( - \inf_{\boldsymbol{\lambda} \in \Theta \cap \mathrm{Alt}(\hat{S}_t)} \frac{\|\mathrm{vec}(\hat{\boldsymbol{\theta}}_t - \boldsymbol{\lambda})\|_{\Sigma \otimes V_t^{-1}}^2}{2c(t-1, \delta)} \right) \\ &= \frac{n_t}{2} \exp \left( - \frac{\mathrm{GLR}(t)}{c(t-1, \delta)} \right) \end{aligned} $$

and from Lemma 26, $n_t = p_t(p_t - 1) + (|\mathcal{Z}| - p_t)d^{p_t}$, with $p_t := |\hat{S}_t|$, □

□
F ASYMPTOTIC EXPECTED SAMPLE COMPLEXITY

We prove the asymptotic optimality of our algorithm.

**Theorem 1.** Using budget M and inflation c such that $\limsup_{\delta \to 0} \frac{c(t, \delta) \log M(t, \delta)}{\log(1/\delta)} \le 1$, the PSIPS algorithm satisfies that $\limsup_{\delta \to 0} \mathbb{E}_{\nu}[\tau_{\delta}^{\text{PS}}]/\log(1/\delta) \le T^*(\theta)$ for all $\nu \in \mathcal{D}^K$ with regression matrix $\theta \in \Theta$, both for unstructured PSI $(\Theta = \mathbb{R}^{K \times d}, \mathcal{Z} = A, h = K, A = I_K)$ and transductive linear PSI (bounded convex $\Theta$).

*Proof.* In this section, $(\Xi_t)_{t \ge 1}$ denotes the sequence of events introduced in Equation (53) and $t_3 \in \mathbb{N}$. We have $\tau_{\delta}^{\text{PS}} = 1 + \sum_{t \ge 1} \mathbb{1}_{(\tau_{\delta}^{\text{PS}} > t)}$ then

$$ 
\begin{aligned}
\mathbb{E}[\tau_{\delta}^{\text{PS}}] &= 1 + \mathbb{E}\left[\sum_{t \ge 1} \mathbb{P}(\tau_{\delta}^{\text{PS}} > t \mid \mathcal{F}_t)\right] \\
&= 1 + \mathbb{E}\left[\sum_{t \ge 1} \mathbb{P}\left(\exists m \in [M(t, \delta)] : \theta_t^m \in \Theta \cap \text{Alt}(\hat{S}_t) \mid \mathcal{F}_t\right)\right] \\
&\le \mathbb{E}\left[\sum_{t \ge t_3} \mathbb{1}_{\Xi_t} M(t, \delta) \mathbb{P}(\theta_t \in \Theta \cap \text{Alt}(\hat{S}_t) \mid \mathcal{F}_t)\right] + \left[\sum_{t \ge 1} \mathbb{P}(\Xi_t^c)\right] + (t_3 + 1),
\end{aligned}
$$

where $\theta_t, \theta_t^1, \dots, \theta_t^m$ are i.i.d given $\mathcal{F}_t$. Moreover, by Lemma 17, we have

$$ \mathbb{P}(\theta_t \in \Theta \cap \text{Alt}(\hat{S}_t) \mid \mathcal{F}_t) \le \alpha_t \exp\left(-\frac{\text{GLR}(t)}{c(t-1, \delta)}\right) $$

with $2\alpha_t = p_t(p_t - 1) + (|\mathcal{Z}| - p_t)d^{p_t} \le |\mathcal{Z}|(|\mathcal{Z}| + d^{|\mathcal{Z}|}) := \alpha_0$, therefore,

$$ \mathbb{E}[\tau_{\delta}^{\text{PS}}] \le \underbrace{\mathbb{E}\left[\sum_{t \ge t_3} \mathbb{1}_{\Xi_t} \alpha_0 M(t, \delta) \exp\left(-\frac{\text{GLR}(t)}{c(t-1, \delta)}\right)\right]}_{L_1(\delta)} + \underbrace{\left[\sum_{t \ge 1} \mathbb{P}(\Xi_t^c)\right]}_{L_2} + (t_3 + 1), $$

then, since $\mathbb{P}(\Xi_t^c) \le 5/t^2$ we immediately have

$$ L_2 \le 5\pi^2/6. \qquad (55) $$

It remains to bound $L_1(\delta)$. Using the saddle-point convergence property on the event $\Xi_t$ ensures that (Theorem 3) for $t \ge t_3$,

$$ 2\text{GLR}(t) := \inf_{\lambda \in \Theta \cap \text{Alt}(\hat{S}_t)} \left\| \text{vec}(\lambda - \hat{\theta}_t) \right\|_{\Sigma^{-1} \otimes V_t}^2 \ge t \max_{\omega \in \Delta} \inf_{\lambda \in \Theta \cap \text{Alt}(S^*(\theta))} \left\| \text{vec}(\theta - \lambda) \right\|_{\Sigma^{-1} \otimes V_\omega}^2 - 2f(t), \quad (56) $$

which further results in

$$ 
\begin{aligned}
L_1(\delta) &\le \sum_{t \ge t_3} \alpha_0 M(t, \delta) \exp \left( - \frac{t}{T^*(\theta)c(t, \delta)} + f(t)/c(t, \delta) \right) \\
&= \sum_{t \ge t_3} \exp \left( - \frac{t}{T^*(\theta)c(t, \delta)} + f(t)/c(t, \delta) + \log(\alpha_0 M(t, \delta)) \right).
\end{aligned}
$$

To bound the above quantity, let us introduce

$$ T(\delta) := \sup \left\{ t \mid \frac{t}{T^*(\theta)c(t, \delta)} - \log(M(t, \delta)) - f(t)/c(t, \delta) - \log(\alpha_0) \le \log(t \log(t)) \right\}, \quad (57) $$

then it follows that

$$ L_1(\delta) \le T(\delta) + \sum_{t \ge t_3} (t \log(t))^{-1}. \qquad (58) $$

Further observe that $T(\delta)$ can be rewritten as

$$ T(\delta) := \sup \{t \mid t \le T^*(\theta)c(t, \delta) (\log(M(t, \delta)) + f(t)/c(t, \delta) + \log(\alpha_0) + \log(t \log(t)))\}. $$
**Bounding $T(\delta)$** Since $f$ is sub-linear in $t$, there exists $\varepsilon \in (0, 1)$ such that $f(t) = o_{t \to \infty}(t^\varepsilon)$ then $f(\log(1/\delta)^{1/\varepsilon}) = o(\log(1/\delta))$. Further observe that for $t_\delta = \log(1/\delta)^{1/\alpha}$,

$$ \underbrace{c(t_\delta, \delta) \log(M(t_\delta, \delta)) + f(\log(1/\delta)^{1/\varepsilon}) + c(t_\delta, \delta) (\log(t_\delta \log(t_\delta)) + \alpha_0)}_{b(t_\delta)} \underset{\delta \to 0}{\sim} \log(1/\delta). $$

Let $\delta_{\min} \in (0, 1)$ be defined as

$$ \delta_{\min} := \inf \left\{ \delta \in (0, 1) \mid b(t_\delta) > \log(1/\delta)^{1/\varepsilon} T^*(\theta)^{-1} \right\} $$

which is well defined as $b(t_\delta) \underset{\delta \to 0}{\sim} \log(1/\delta)$ and $\varepsilon \in (0, 1)$. Letting $T_{\max} = \log(1/\delta_{\min})^{1/\varepsilon}$, remark that for all $t \ge T_{\max}$, there is $(0, 1) \ni \delta' \le \delta_{\min} t'_\delta = t$ and $b(t_\delta') < t_\delta'$. Therefore, for all $\delta \le \delta_{\min}$

$$ T(\delta) \le \log(1/\delta)^{1/\varepsilon} \qquad (59) $$

and further noting that by definition $T(\delta) \le T^*(\theta)b(T(\delta))$ and $b$ is increasing, it follows that

$$ T(\delta) \le T^*(\theta)b(\log(1/\delta)^{1/\varepsilon}). \qquad (60) $$

Combining (55), (58) and (60), it follows that for $\delta \le \delta_{\min}$,

$$ \mathbb{E}[\tau_{\delta}^{\text{PS}}] \le T^*(\theta)b(\log(1/\delta)^{1/\varepsilon}) + 5\pi^2/6 + (t_0 + 1) + \sum_{t \ge t_3} (t \log(t))^{-1}. \qquad (61) $$

Finally, noting that $b(\log(1/\delta)^{1/\varepsilon}) \underset{\delta \to 0}{\sim} \log(1/\delta)$, we have proved that

$$ \limsup_{\delta \to 0} \frac{\mathbb{E}[\tau_{\delta}^{\text{PS}}]}{\log(1/\delta)} \le T^*(\theta). \qquad (62) $$

□

## G POSTERIOR CONVERGENCE

In this section, we prove the following result.

**Theorem 2.** Let $\tilde{\Pi}_t := \mathcal{N}(\hat{\theta}_t, \Sigma \otimes V_N^{-1})$ be the posterior distribution under a flat Gaussian prior (without inflation). For all $\nu \in \mathcal{D}^K$ with regression matrix $\theta \in \Theta$, it almost surely holds that $\limsup_{t \to +\infty} -t^{-1} \log \mathbb{P}_{\tilde{\Pi}_t|\mathcal{F}_t}(\Theta \cap \text{Alt}(S^*)) \le T^*(\theta)^{-1}$ for any algorithm, and PSIPS almost surely satisfies that $\liminf_{t \to +\infty} -t^{-1} \log \mathbb{P}_{\tilde{\Pi}_t|\mathcal{F}_t}(\Theta \cap \text{Alt}(S^*)) \ge T^*(\theta)^{-1}$, both for unstructured PSI ($\Theta = \mathbb{R}^{K \times d}$, $\mathcal{Z} = \mathcal{A}$, $h = K$, $\mathbf{A} = I_K$) and transductive linear PSI (bounded convex $\Theta$).

We prove that the posterior contraction rate of our algorithm is un-improvable for any adaptive algorithm. In BAI, Russo (2016) and Li et al. (2024) proved a similar result for truncated Gaussian (restricted to a bounded domain). We prove it more generally in the unbounded setting for Gaussian distribution.

We recall that when $\lambda$ is a matrix and $\pi$ is a distribution supported on vectors, $\lambda \sim \pi$ denotes $\text{vec}(\lambda) \sim \pi$.

*Proof of Theorem 2.* We first prove the upper bound. Similarly to Lemma 17, we can derive (using Lemma 26 and Lemma 27),

$$ \mathbb{P}_{\tilde{\Pi}_t|\mathcal{F}_t}(\Theta \cap \text{Alt}(S^*)) \le \alpha_0 \exp \left( - \frac{\inf_{\lambda \in \Theta \cap \text{Alt}(S^*)} \|\text{vec}(\hat{\theta}_t - \lambda)\|_{\Sigma_t}^2}{2} \right) $$

with $\alpha_0 := |\mathcal{Z}|(|\mathcal{Z}| + d^{|\mathcal{Z}|})$,

From Theorem 3, there exists events $(\Xi_t)_{t \ge 0}$ and $t_3 \in \mathbb{N}$ such that for $t \ge t_3$, $\hat{S}_t = S^*$, and

$$ 2\text{GLR}(t) := \inf_{\lambda \in \Theta \cap \text{Alt}(\hat{S}_t)} \|\text{vec}(\lambda - \hat{\theta}_t)\|_{\Sigma^{-1} \otimes V_t}^2 \ge t \max_{\omega \in \Delta} \inf_{\lambda \in \Theta \cap \text{Alt}(S^*(\theta))} \|\text{vec}(\theta - \lambda)\|_{\Sigma^{-1} \otimes V_\omega}^2 - 2f(t), \quad (63) $$
with $f(t) =_\infty o(t)$ and $\mathbb{P}_\nu(\Xi_t) \ge 1 - 5/t^2$. Since $\sum_{t \ge 1} \mathbb{P}(\Xi_t^c) < \infty$, by Borel-Cantelli's lemma, with probability 1, there exists a finite time $\tilde{t}_3$ (possibly) random such that for $t \ge \tilde{t}_3$, $\Xi_t$ holds. So for $t \ge \max(t_3, \tilde{t}_3)$, we have $\hat{S}_t = S^*$ and

$$ \frac{1}{2} \inf_{\lambda \in \Theta \cap \text{Alt}(S^*)} \left\| \text{vec}(\lambda - \hat{\theta}_t) \right\|_{\Sigma^{-1} \otimes V_t}^2 = \text{GLR}(t) \ge t T^*(\theta)^{-1} - f(t), $$

then

$$ \mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(\Theta \cap \text{Alt}(S^*)) \le \alpha_0 \exp(-t T^*(\theta)^{-1} + f(t)), $$

so that

$$ -\frac{1}{t} \log(\mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(\Theta \cap \text{Alt}(S^*)) \ge T^*(\theta)^{-1} - (1/t) \log(\alpha_0) - f(t)/t, $$

then, since $f(t) =_\infty o(t)$, put together, the above displays show that with probability 1,

$$ \liminf_{t \to \infty} -\frac{1}{t} \log(\mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(\Theta \cap \text{Alt}(S^*)) \ge T^*(\theta)^{-1}). $$

The proof of the lower bound uses Lemma 18. In the transductive linear setting, when $\Theta$ is convex $\text{Alt}(S^*) \cap \Theta$ is countably convex (by Lemma 26) and bounded. Then taking $O = \text{Alt}(S^*) \cap \Theta$ and applying Lemma 18 yields that with probability 1,

$$ \limsup_{t \to \infty} -\frac{1}{t} \log \mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(\text{Alt}(S^*) \cap \Theta) \le \frac{1}{2} \sup_{\omega \in \Delta_K} \inf_{\lambda \in \text{Alt}(S^*) \cap \Theta} \|\text{vec}(\theta - \lambda)\|_{\Sigma^{-1} \otimes V_\omega}^2 \\ = T^*(\theta)^{-1}. $$

In the unstrucutured setting, let $\mathbb{B}_\epsilon$ be the ball centered on $\mu$ and with radius $\epsilon$ as in Lemma 9. We have $-\mathbb{P}(\text{Alt}(S^*)) \le -\mathbb{P}(\text{Alt}(S^*) \cap \mathbb{B}_\epsilon)$, then $O = \text{Alt}(S^*) \cap \mathbb{B}_\epsilon$ is countably convex (Lemma 26 and $\mathbb{B}_\epsilon$ is convex) and bounded. Applying Lemma 18, we obtain

$$ \begin{aligned} \limsup_{t \to \infty} -\frac{1}{t} \log \mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(\text{Alt}(S^*)) &\le \limsup_{t \to \infty} -\frac{1}{t} \log \mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(\text{Alt}(S^*) \cap \mathbb{B}_\epsilon) \\ &\le \frac{1}{2} \sup_{\omega \in \Delta_K} \inf_{\lambda \in \text{Alt}(S^*) \cap \mathbb{B}_\epsilon} \|\text{vec}(\theta - \lambda)\|_{\Sigma^{-1} \otimes V_\omega}^2 \\ &= \frac{1}{2} \sup_{\omega \in \Delta_K} \inf_{\lambda \in \text{Alt}(S^*)} \|\text{vec}(\theta - \lambda)\|_{\Sigma^{-1} \otimes V_\omega}^2 \quad (\text{Lemma 9}) \\ &= T^*(\theta)^{-1}, \end{aligned} $$

which concludes the proof.

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

**Lemma 18.** Let $O \subset \mathbb{R}^{h \times d}$ be countably convex bounded set, with non-empty interior. With probability 1, it holds that

$$ \limsup_{t \to \infty} -\frac{1}{t} \log \mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(O) \le \frac{1}{2} \sup_{\omega \in \Delta_K} \inf_{\lambda \in O} \|\text{vec}(\theta - \lambda)\|_{\Sigma^{-1} \otimes V_\omega}^2. $$

*Proof.* Since $O$ is countably there exists convex sets $C_1, \dots, C_n$ such that $O = \cup_{i \in [n]} C_i$.

We have

$$ \mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(O) = (2\pi)^{-dh/2} \det(\Sigma_t)^{-1/2} \int_{\text{vec}(O)} \exp \left( -\frac{\|\text{vec}(\hat{\theta}_t) - \lambda\|^2_{\tilde{V}_t}}{2} \right) d\lambda. $$

Similarly to the proof of the regret of the min learner, let $\gamma > 0$ (to be defined) and $\tilde{\lambda}_t \in \text{argmin}_{\lambda \in \bar{O}} \|\text{vec}(\lambda - \hat{\theta}_t)\|_{\tilde{V}_t}^2$. Since $O$ is a union of convex sets, there exists a convex set $C \subset O$ such that $\tilde{\lambda}_t \in C$. Then letting $\mathcal{N}_\gamma := \{(1 - \gamma)\tilde{\lambda}_t + \gamma\lambda, \lambda \in$
$C} = (1 - \gamma)\tilde{\lambda}_t + \gamma C$, it follows

$$
\begin{align*}
w_t &:= \int_{\text{vec}(O)} \exp\left(-\frac{\|\text{vec}(\hat{\theta}_t) - \lambda\|_{\tilde{V}_t}^2}{2}\right) d\lambda \\
&\geq \int_{\text{vec}(C)} \exp\left(-\frac{\|\text{vec}(\hat{\theta}_t) - \lambda\|_{\tilde{V}_t}^2}{2}\right) d\lambda \\
&\geq \int_{\text{vec}(\mathcal{N}_\gamma)} \exp\left(-\frac{\eta\|\text{vec}(\hat{\theta}_t) - \lambda\|_{\tilde{V}_t}^2}{2}\right) d\lambda \quad (\text{convexity of } C) \\
&= \int_{\gamma\text{vec}(C)} \exp\left(-\frac{\|\text{vec}(\hat{\theta}_t - (1-\gamma)\tilde{\lambda}_t) - \lambda\|_{\tilde{V}_t}^2}{2}\right) d\lambda \\
&= \int_{\text{vec}(C)} \gamma^{dh} \exp\left(-\frac{\|(1-\gamma)\text{vec}(\hat{\theta}_t - \tilde{\lambda}_t) + \gamma\text{vec}(\hat{\theta}_t) - \gamma\lambda\|_{\tilde{V}_t}^2}{2}\right) d\lambda \\
&\geq \int_{\text{vec}(C)} \gamma^{dh} \exp\left(-\frac{\left((1-\gamma)\|\text{vec}(\hat{\theta}_t - \tilde{\lambda}_t)\|_{\tilde{V}_t}^2 + \gamma\|\lambda - \text{vec}(\hat{\theta}_t)\|_{\tilde{V}_t}^2\right)}{2}\right) d\lambda
\end{align*}
$$

therefore,

$$
\log w_t \ge dh \log(\gamma) - \frac{(1-\gamma)}{2} \|\mathrm{vec}(\hat{\theta}_t - \tilde{\lambda}_t)\|_{\tilde{V}_t}^2 - \frac{\eta \gamma \mathbb{E}_{\lambda \sim \mathcal{U}(C)} \left[ \|\mathrm{vec}(\lambda - \hat{\theta}_t)\|_{\tilde{V}_t}^2 \right]}{2} + \mathrm{vol}(\mathrm{vec}(C_*)) \quad (64)
$$

where $C_*$ is the set of minimum volume among $C_1, \dots, C_n$. We recall

$$
\Xi_{1,t} := \left\{ \forall s \le t, \left\| \mathrm{vec}(\theta - \hat{\theta}_s) \right\|_{\tilde{V}_s}^2 \le \beta(t, 1/t^2) :=: f_1(t) \right\},
$$

where $\beta(t, \delta)$ is defined as in Lemma 3, and $\mathbb{P}_{\nu}(\Xi_{1,t}) \ge 1-1/t^2$. Moreover, $f_1(t)$ is logarithmic in $t$. Since $\sum_{t \ge 1} \mathbb{P}(\Xi_t^c) < \infty$, by Borel-Cantelli's lemma, with probability 1, there exists a finite time $\tilde{t}$ (possibly) random such that for $t \ge \tilde{t}$, $\Xi_{1,t}$ holds.

Taking $\gamma = 1/t$ in Equation (64), and for $t \ge \tilde{t}$, we get (after simplification)

$$
\log w_t \geq -dh \log(t) - \frac{(1-\gamma)}{2} \|\mathrm{vec}(\hat{\theta}_t - \tilde{\lambda}_t)\|_{\tilde{V}_t}^2 - (\sqrt{tL(O)} + \sqrt{f_1(t)})^2/t + \mathrm{vol}(\mathrm{vec}(C_*)),
$$

where $L(O) = \max_{a \in A, \lambda \in O} \|\mathrm{vec}(\lambda - \theta)\|_{\Sigma^{-1} \otimes_{aa^T}}^2$. Now by convex inequality, we have for any $\lambda \in O$,

$$
\begin{align*}
\|\mathrm{vec}(\hat{\theta}_t - \boldsymbol{\lambda})\|_{\tilde{V}_t}^2 &\le \|\mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})\|_{\tilde{V}_t}^2 + 2\mathrm{vec}(\boldsymbol{\lambda} - \hat{\boldsymbol{\theta}}_t)^T \tilde{V}_t \mathrm{vec}(\boldsymbol{\theta} - \hat{\boldsymbol{\theta}}_t) \\
&\le \|\mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})\|_{\tilde{V}_t}^2 + 2\|\mathrm{vec}(\hat{\boldsymbol{\theta}}_t - \boldsymbol{\lambda})\|_{\tilde{V}_t} \|\mathrm{vec}(\boldsymbol{\theta} - \hat{\boldsymbol{\theta}}_t)\|_{\tilde{V}_t} \\
&\le \|\mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})\|_{\tilde{V}_t}^2 + 2f_1(t) + 2\sqrt{f_1(t)} \|\mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})\|_{\tilde{V}_t} \\
&\le \|\mathrm{vec}(\boldsymbol{\theta} - \boldsymbol{\lambda})\|_{\tilde{V}_t}^2 + 2f_1(t) + 2\sqrt{f_1(t)} \sqrt{tL(O)},
\end{align*}
$$

thus we have

$$
\|\mathrm{vec}(\hat{\theta}_t - \tilde{\lambda}_t)\|_{\tilde{V}_t}^2 \le \inf_{\lambda \in O} \|\mathrm{vec}(\theta - \lambda)\|_{\tilde{V}_t}^2 + 2f_1(t) + 2\sqrt{f_1(t)}\sqrt{tL(O)}.
$$

Put together, we have proved that

$$
- \log \mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(O) \le \frac{1}{2} \inf_{\lambda \in O} \|\mathrm{vec}(\theta - \lambda)\|_{\tilde{V}_t}^2 + 2f_1(t) + 2\sqrt{f_1(t)}\sqrt{tL(O)} + (dh/2)\log(2\pi) + \frac{1}{2}\log \det(\Sigma_t) + dh\log(t) \\
+ (\sqrt{tL(O)} + \sqrt{f_1(t)})^2/t - \mathrm{vol}(\mathrm{vec}(C_*)).
$$
We recall that $\Sigma_t = \Sigma \otimes V_t^{-1}$ and $\tilde{V}_t = \Sigma_t^{-1}$ with $V_t = V_{N_t} + V_0$ so $\log \det(\Sigma_t) \le \log(\det(\Sigma \otimes V_0)) = cste$ (due to initialization or regularization). Combining the displays above yield,

$$ - \log \mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(O) \le \frac{1}{2} \inf_{\lambda \in O} \|\mathrm{vec}(\theta - \lambda)\|_{\tilde{V}_t}^2 + o(t), $$

which finally yields,

$$ \begin{aligned} -1/t \log \mathbb{P}_{\tilde{\Pi}_t | \mathcal{F}_t}(O) &\le \frac{1}{2} \inf_{\lambda \in O} \|\mathrm{vec}(\theta - \lambda)\|_{\tilde{V}_t/t}^2 + o(t)/t, \\ &= \frac{1}{2} \inf_{\lambda \in O} \|\mathrm{vec}(\theta - \lambda)\|_{\Sigma^{-1} \otimes V_{N_t/t}}^2 + o(t)/t, \\ &\le \frac{1}{2} \sup_{\omega \in \Delta_K} \inf_{\lambda \in O} \|\mathrm{vec}(\theta - \lambda)\|_{\Sigma^{-1} \otimes V_\omega}^2 + o(t)/t, \end{aligned} $$

and taking the limit yields the claimed statement. $\square$

# H CONCENTRATION RESULTS

## H.1 Concentration of Good Event

**Lemma 3.** Let $s > 1$, $\zeta$ be the Riemann $\zeta$ function and $\bar{W}_{-1}(x) := -W_{-1}(-e^{-x})$ for all $x \ge 1$, where $W_{-1}$ is the negative branch of the Lambert W function. Let $\mathcal{E}_\delta$ in (6). Then, we have $\mathbb{P}_\nu(\mathcal{E}_\delta^c) \le \delta$ by taking

$$ \beta(t, \delta) = \frac{dK}{2} \bar{W}_{-1} \left( \frac{2}{dK} \log \frac{e^{Ks} \zeta(s)^K}{\delta} + \frac{2s}{d} \log \left( 1 + \frac{d}{2s} \log \frac{t}{K} \right) + 1 \right) $$

in the unstructured setting, and taking

$$ \sqrt{\beta(t, \delta)} = \sqrt{\log \left( \frac{1}{\delta} \left( \frac{L_A^2}{h\xi} t + 1 \right)^{\frac{dh}{2}} \right)} + \sqrt{\frac{dL_M^2}{2\lambda_{\min}(\Sigma)\xi}} $$

in the transductive linear setting, where $L_A := \max_{a \in A} \|a\|_2$ and $L_M := \max_{\lambda \in \Theta} \max_{c \in [d]} \|\lambda e_c\|_2$.

### H.1.1 Unstructured Setting

In the unstructured setting, we take $\xi = 0$ and denote the empirical mean by $\hat{\mu}_t$ instead of $\hat{\theta}_t$ with $\hat{\mu}_{t,i} = \frac{1}{N_{t,i}} \sum_{s \in [t-1]} 1(I_s = i) X_s$ where $I_t$ denote the index associated to the arm $a_t$ pulled at time $t$.

The set of multi-variate Gaussian distributions with known covariance matrix $\Sigma$ is a $d$-dimensional canonical exponential family admitting $\mathbb{R}^d$ as set of possible natural parameters. Let us denote by $\theta_i := \Sigma^{-1}\mu_i$ the natural parameter associated to $\mu_i$. The associated log-partition function is defined as $\phi_i(\theta_i) := \frac{1}{2}\theta_i^\top\Sigma\theta_i$ and satisfies that $\nabla\phi_i(\theta_i) = \Sigma\mu_i$ and $\nabla^2\phi_i(\mu_i) = \Sigma$. We note that $\hat{\mu}_{t,i}$ is the mean parameter associated with the natural parameter $(\nabla\phi_i)^{-1}(\frac{1}{N_{t,i}} \sum_{s \in [t-1]} 1(I_s = i) X_s) = \Sigma^{-1}\hat{\mu}_{t,i}$. Therefore, we can use the concentration results derived in Chapter 4 of Degenne (2019). In particular, we will be using the generalization to $K$ arms derived in Jourdan et al. (2023).

**Lemma 19** (Lemma 39 in Jourdan et al. (2023) based on Degenne (2019)). Let $\{\rho_{0,i}\}_{i \in [K]} \subseteq \mathcal{P}(\mathbb{R}^d)$. With probability $1 - \delta$, for all $t \in \mathbb{N}$,

$$ \sum_{i \in [K]} \frac{N_{t,i}}{2} \|\hat{\mu}_{t,i} - \mu_i\|_{\Sigma^{-1}}^2 \le \log(1/\delta) - \sum_{i \in [K]} \ln \mathbb{E}_{y \sim \rho_{0,i}} \exp \left( -\frac{N_{t,i}}{2} \|\hat{\mu}_{t,i} - y\|_{\Sigma^{-1}}^2 \right). $$

Lemma 20 gives the concentration threshold for the unstructured setting. The proof is obtained by using the method from Degenne (2019): peeling argument with a sequence of Gaussian priors.

**Lemma 20.** Let $s > 1$, $\bar{W}_{-1}$ as in Lemma 25 and $\zeta$ be the Riemann $\zeta$ function. With probability $1 - \delta$, for all $t \in \mathbb{N}$

$$ \sum_{i \in [K]} \frac{N_{t,i}}{2} \|\hat{\mu}_{t,i} - \mu_i\|_{\Sigma^{-1}}^2 \le \frac{dK}{2} \bar{W}_{-1} \left( \frac{2}{dK} \log \frac{e^{Ks} \zeta(s)^K}{\delta} + \frac{2s}{d} \log \left( 1 + \frac{d}{2s} \log \frac{t-1}{K} \right) + 1 \right). $$
Proof. Let $\gamma > 1$, $\eta > 0$ to be defined later. Let $(k_i)_{i \in [K]} \in \mathbb{N}^K$ and $n_k := \gamma^k$ for $k \in \mathbb{N}$. Let $(M_{0,i})_{i \in [K]}$ be positive definite matrices to be defined later. Let us define the prior $\rho_{0,i} = \mathcal{N}(\mu_i, M_{0,i}^{-1})$ for all $i \in [K]$. Using the computations in the proof of Lemma 4.23 in Degenne (2019), we obtain, for all $i \in [K]$,

$$ \mathbb{E}_{y \sim \rho_{0,i}} \exp \left( -\frac{N_{t,i}}{2} \| \hat{\mu}_{t,i} - y \|_{\Sigma^{-1}}^2 \right) = \sqrt{\frac{\det(M_{0,i})}{\det(N_{t,i} \Sigma^{-1} + M_{0,i})}} \exp \left( -\frac{1}{2} \| \hat{\mu}_{t,i} - \mu_i \|^2_{(\Sigma/N_{t,i} + M_{0,i}^{-1})^{-1}} \right). $$

For all $t \in \mathbb{N}$, for all $i$, there exists $k_i$ such $N_{t,i} \in [n_{k_i}, n_{k_i+1})$. Let $(k_i)_{i \in [K]}$ be such vector of indices. In the following, we consider $M_{0,i}^{-1} := \frac{1}{n_{k_i} \eta} \Sigma$, hence we have

$$ \sqrt{\frac{\det(M_{0,i})}{\det(N_{t,i} \Sigma^{-1} + M_{0,i})}} = \left(1 + \frac{N_{t,i}}{n_{k_i} \eta}\right)^{-d/2} \geq \left(1 + \frac{1}{\eta}\right)^{-d/2} \gamma^{-d/2}, \\ (\Sigma/N_{t,i} + M_{0,i}^{-1})^{-1} = N_{t,i} \left(1 + \frac{N_{t,i}}{n_{k_i} \eta}\right)^{-1} \Sigma^{-1} \leq N_{t,i} \left(1 - \frac{1}{\eta + 1}\right) \Sigma^{-1}. $$

where we used that $N_{t,i} \geq n_{k_i}$, $N_{t,i} \leq n_{k_i} \gamma$ and $\gamma > 1$. Therefore, we obtain

$$ \mathbb{E}_{y \sim \rho_{0,i}} \exp \left( -\frac{N_{t,i}}{2} \| \hat{\mu}_{t,i} - y \|_{\Sigma^{-1}}^2 \right) \geq \left(1 + \frac{1}{\eta}\right)^{-d/2} \gamma^{-d/2} \exp \left( -\frac{N_{t,i}}{2} \left(1 - \frac{1}{\eta+1}\right) \| \hat{\mu}_{t,i} - \mu_i \|_{\Sigma^{-1}}^2 \right). $$

We use Lemma 19 with prior $\rho_{0,i} = \mathcal{N}(\mu_i, M_{0,i}^{-1})$. By taking the logarithm, summing over $i \in [K]$ and re-ordering terms, we obtain that, with probability $1 - \delta$, for all $t \in \mathbb{N}$, if $N_t \in \bigotimes_{i \in [K]} [n_{k_i}, n_{k_i+1})$, then

$$ \sum_{i \in [K]} \frac{N_{t,i}}{2} \| \hat{\mu}_{t,i} - \mu_i \|_{\Sigma^{-1}}^2 \leq (\eta + 1) \left( \log(1/\delta) + \frac{dK}{2} \log \gamma + \frac{dK}{2} \log \left(1 + \frac{1}{\eta}\right) \right) $$

To choose an optimal value for $\eta$, we rely on Lemma 21 taken from Degenne (2019).

**Lemma 21 (Lemma A.3 in Degenne (2019)).** For $a, b \geq 1$, the minimal value of $f(\eta) = (1+\eta)(a+\ln(b+\frac{1}{\eta}))$ is attained at $\eta^*$ such that $f(\eta^*) \leq 1-b+\bar{W}_{-1}(a+b)$. If $b=1$, then there is equality.

Then, we have that, with probability $1 - \delta$, for all $t \in \mathbb{N}$, if $N_t \in \bigotimes_{i \in [K]} [n_{k_i}, n_{k_i+1})$, then

$$ \sum_{i \in [K]} \frac{N_{t,i}}{2} \| \hat{\mu}_{t,i} - \mu_i \|_{\Sigma^{-1}}^2 \leq \frac{dK}{2} \bar{W}_{-1} \left( 1 + \frac{2}{dK} \log(1/\delta) + \log \gamma \right) $$

Let us define $w_k = \frac{1}{\zeta(s)(k+1)^s}$. Then, we have

$$ \sum_{(k_i)_{i \in [K]} \in \mathbb{N}^K} \prod_{i \in [K]} w_{k_i} = \left( \sum_{k \in \mathbb{N}} w_k \right)^K = \left( \frac{1}{\zeta(s)} \sum_{k \in \mathbb{N}} \frac{1}{(k+1)^s} \right)^K = 1. $$

Using that $\bigcup_{(k_i)_{i \in [K]} \in \mathbb{N}^K} \bigotimes_{i \in [K]} [n_{k_i}, n_{k_i+1}) = \mathbb{N}^K$, we can apply the above results for each $(k_i)_{i \in [K]} \in \mathbb{N}^K$ with probability $1 - \delta \prod_{i \in [K]} w_{k_i}$. When $N_{t,i} \in [n_{k_i}, n_{k_i+1})$, we have $k_i \leq \log(N_{t,i})/\log(\gamma)$. Therefore, a direct union bound yields that, with probability $1 - \delta$, for all $t \in \mathbb{N}$,

$$ \sum_{i \in [K]} \frac{N_{t,i}}{2} \| \hat{\mu}_{t,i} - \mu_i \|_{\Sigma^{-1}}^2 \\ \leq \frac{dK}{2} \bar{W}_{-1} \left( 1 + \frac{2}{dK} \log(1/\delta) + \frac{2}{d} \log \zeta(s) + \frac{2s}{dK} \sum_{i \in [K]} \log(\log(\gamma) + \log N_{t,i}) - \frac{2s}{d} \log \log(\gamma) + \log \gamma \right). $$

The function $f: \gamma \to \log \gamma - \frac{2s}{d} \log \log \gamma$ is minimized at $\gamma^* = e^{2s/d}$ with value $f(\gamma^*) = 2s(1 - \log(2s/d))/d$. Taking $\gamma^*$ and using the concavity of $x \to \log(\frac{2s}{d} + \log x)$ concludes the proof since we have

$$ \frac{2s}{dK} \sum_{i \in [K]} \log \left( \frac{2s}{d} + \log N_{t,i} \right) \leq \frac{2s}{d} \log \left( \frac{2s}{d} + \log \frac{t-1}{K} \right). $$

□
### H.1.2 Structured Setting

We prove the following result.

**Lemma 22.** Letting

$$ \sqrt{\beta(t, \delta)} = \sqrt{\log \left( \frac{1}{\delta} \left( \frac{L_A^2}{h\xi} t + 1 \right)^{\frac{dh}{2}} \right)} + \sqrt{\frac{dL_M^2}{2\lambda_{\min}(\Sigma)\xi}}, $$

where $L_A := \max_{a \in A} \|a\|_2$ and $L_M := \max_{\lambda \in \Theta} \max_{c \in [d]} \|\lambda e_c\|_2$, the event

$$ \mathcal{E}_{\delta} := \left\{ \forall t \ge 1, \frac{1}{2} \| \mathrm{vec}(\boldsymbol{\theta} - \hat{\boldsymbol{\theta}}_t) \|_{\Sigma^{-1} \otimes (V_{N_t} + \xi I_h)}^2 \le \beta(t-1, \delta) \right\} $$

holds with probability at least $1 - \delta$.

*Proof.* At time $t$, $a_t$ is chosen from $[K]$ (adaptively) and a random vector $X_t := (I_d \otimes a_t)\mathrm{vec}(\boldsymbol{\theta}) + \varepsilon_t$ is observed and $\varepsilon, \varepsilon_1, \dots, \varepsilon_t$ are centered i.i.d $\Sigma$ subgaussian random vectors, i.e. for all $u \in \mathbb{R}^d$,

$$ \mathbb{E}[\exp(u^\top \boldsymbol{\varepsilon})] \le \exp\left(\frac{1}{2} \|u\|_{\Sigma}^2\right). \qquad (65) $$

Let us define $S_t := \sum_{s=1}^t \mathrm{vec}(a_s \varepsilon_s^\top)$, $A_t := (a_1 \dots a_t)^\top$, $X_t := (X_1 \dots X_t)$ and $H_t := (\varepsilon_1 \dots \varepsilon_t)^\top$. The regularized least-squares estimator of $\boldsymbol{\theta}$ (for the Frobenius norm) is given by

$$ \hat{\boldsymbol{\theta}}_t = (V_{N_t} + \xi I_h)^{-1} A_t^\top X_t. $$

We introduce slightly modified filtration that make $a_t$ precitbible (as $\tilde{\omega}$ is and an agent can pull $a_{t+1}$ at the end of round $t$). We define $\mathcal{F}_t = \sigma(\mathcal{F}_t, a_{t+1})$. We define the following $t$-indexed stochastic process for any $\lambda \in \mathbb{R}^{d \cdot h}$

$$ M^{\lambda}(t) := \exp \left( \lambda^{\top} S_t - \frac{1}{2} \|\lambda\|_{\Sigma \otimes V_{N_t}}^2 \right). $$

We first justify that $M^{\lambda}(t)$ is a super-martingale. Indeed, $M^{\lambda}(t)$ is an $\{\tilde{\mathcal{F}}_t\}_{t \ge 1}$-adapted process and

$$ \mathbb{E} [M^{\lambda}(t+1) | \tilde{\mathcal{F}}_t] = M^{\lambda}(t) \mathbb{E} \left[ \exp \left( \lambda^{\top} \mathrm{vec}(a_{t+1} \varepsilon_{t+1}^{\top}) - \frac{1}{2} \|\lambda\|_{\Sigma \otimes a_{t+1} a_{t+1}^{\top}}^2 \right) | \tilde{\mathcal{F}}_t \right], \quad (66) $$

then, note that by properties of Kronecker product, $\mathrm{vec}(x \varepsilon^\top) = (I_d \otimes x)\varepsilon$, so

$$ \lambda^{\top} \mathrm{vec}(a_{t+1} \varepsilon_{t+1}^{\top}) = \lambda^{\top} (I_d \otimes a_{t+1}) \varepsilon_{t+1}, \qquad (67) $$

and

$$ \begin{align*} \lambda^{\top} (I_d \otimes a) \Sigma (\lambda^{\top} (I_d \otimes a))^{\top} &= \lambda^{\top} (I_d \otimes a) \Sigma (I_d \otimes a^{\top}) \lambda \\ &= \frac{1}{aa^{\top}} \lambda^{\top} (I_d \otimes a) (\Sigma \otimes a^{\top} a) (I_d \otimes a^{\top}) \lambda \\ &= \frac{1}{aa^{\top}} \lambda^{\top} (\Sigma \otimes (aa^{\top}xa^{\top})) \lambda = \lambda^{\top} (\Sigma \otimes aa^{\top}) \lambda \end{align*} $$

which follows from the property $(A \otimes B)(C \otimes D) = (AC) \otimes (BD)$, proving that

$$ \|(I_d \otimes a_{t+1}^{\top})\lambda\|_{\Sigma}^2 = \|\lambda\|_{\Sigma \otimes (a_{t+1} a_{t+1}^{\top})}^2. $$

Thus, combining the above display with (66) and the sub-gaussian property of $\varepsilon_{t+1}$ shows that

$$ \mathbb{E} [M^{\lambda}(t+1) | \tilde{\mathcal{F}}_t] \le M^{\lambda}(t), $$
so $(M^{\lambda}(t))_t$ is a super-martingale. For $\xi > 0$ and $\Lambda \sim \mathcal{N}(0_{dh}, \Sigma^{-1} \otimes (\xi I_h)^{-1})$, we define

$$M(t) := \mathbb{E} [M^{\Lambda}(t) | \tilde{\mathcal{F}}_{\infty}] .$$

Letting $U_t := \Sigma \otimes V_{N_t}$ and defining $c(P) := \sqrt{(2\pi)^{d \cdot h}}/\det(P) = \int_{\mathbb{R}^{d \cdot h}} \exp(-\frac{1}{2}\lambda^{\top}P\lambda)d\lambda$, we have

$$\begin{aligned}
M(t) &= \frac{1}{c(\Sigma \otimes \xi I_h)} \int \exp \left( \lambda^{\top} S_t - \frac{1}{2} \lambda^{\top} U_t \lambda - \frac{1}{2} \lambda^{\top} (\Sigma \otimes (\xi I_h)) \lambda \right) d\lambda \\
&= \frac{1}{c(\Sigma \otimes \xi I_h)} \exp \left( \frac{1}{2} S_t^{\top} W_t^{-1} S_t \right) \int \exp \left( -\frac{1}{2} (\lambda - W_t^{-1} S_t)^{\top} W_t (\lambda - W_t^{-1} S_t) \right) d\lambda
\end{aligned}$$

where $W_t := U_t + \Sigma \otimes (\xi I_h) = \Sigma \otimes (V_{N_t} + \xi I_h)$ then direct algebra yields

$$\begin{aligned}
M(t) &= \frac{c(\Sigma \otimes (V_{N_t} + \xi I_h))}{c(\Sigma \otimes \xi I_h)} \exp \left( \frac{1}{2} \|S_t\|_{W_t^{-1}}^2 \right) \\
&= \left( \frac{\det(\Sigma \otimes \xi I_h)}{\det(\Sigma \otimes (V_{N_t} + \xi I_h))} \right)^{1/2} \exp \left( \frac{1}{2} \|S_t\|_{W_t^{-1}}^2 \right),
\end{aligned}$$

then it is known that $M_t$ is also a super-martingale (by Fubini's theorem) with $\mathbb{E}_{\nu}[M_t] \le 1$ and using classical technique similar to section 20.1 of Lattimore and Szepesvári (2020) on super-martingale, it holds that with probability at least $1 - \delta$ we have for all $t \ge 1$,

$$\begin{aligned}
\|S_t\|_{W_t^{-1}}^2 &\le 2 \log \left( \frac{\det(\Sigma \otimes (V_{N_t} + \xi I_h))^{1/2}}{\delta \det(\Sigma \otimes \xi I_h)^{1/2}} \right) \\
&= 2 \log \left( \frac{\det(V_{N_t} + \xi I_h)^{d/2}}{\delta \xi^{d \cdot h/2}} \right),
\end{aligned} \quad (68)$$

which follows as for $A \in \mathbb{R}^{p \times p}$ and $B \in \mathbb{R}^{q \times q}$

$$\det(A \otimes B) = \det(A)^q \det(B)^p.$$

We further have $\hat{\theta}_t := (V_{N_t} + \xi I_h)^{-1} A_t^{\top} X_t$ then

$$\begin{aligned}
\hat{\theta}_t &= (V_{N_t} + \xi I_h)^{-1} A_t^{\top} (A_t \theta + H_t) \\
&= (V_{N_t} + \xi I_h)^{-1} V_{N_t} \theta + (V_{N_t} + \xi I_h)^{-1} A_t^{\top} H_t \\
&= \theta - \xi (V_{N_t} + \xi I_h)^{-1} \theta + (V_{N_t} + \xi I_h)^{-1} A_t^{\top} H_t.
\end{aligned}$$

We recall that for any $B, C$ well defined and $C \in \mathbb{R}^{p \times q}$

$$\mathrm{vec}(BC) = (I_q \otimes B)\mathrm{vec}(C).$$

Therefore we can derive

$$\mathrm{vec}(\hat{\theta}_t - \theta) = -\xi (I_d \otimes (V_{N_t} + \xi I_h)^{-1}) \mathrm{vec}(\theta) + (I_d \otimes (V_{N_t} + \xi I_h)^{-1}) S_t.$$

We recall that for any two invertible matrices $A, B$, $A \otimes B$ is invertible and

$$(A \otimes B)^{-1} = A^{-1} \otimes B^{-1}$$

and for any matrices $A, B, C, D$ when the product is possible

$$(A \otimes B)(C \otimes D) = (AC) \otimes (BD)$$

and $(A \otimes B)^{\top} = (A^{\top} \otimes B^{\top})$. Letting $Z_t := I_d \otimes (V_{N_t} + \xi I_h)$ and for any $x \in \mathbb{R}^{dh}$,

$$\begin{aligned}
x^{\top} \mathrm{vec}(\hat{\theta}_t - \theta) &= -\xi x^{\top} Z_t^{-1} \mathrm{vec}(\theta) + x^{\top} Z_t^{-1} S_t \\
&= \xi x^{\top} (\Sigma \otimes I_h) W_t^{-1} \mathrm{vec}(\theta) + x^{\top} (\Sigma \otimes I_h) W_t^{-1} S_t
\end{aligned}$$
where $W_t = \Sigma \otimes (V_{N_t} + \xi I_h)$, then thanks to Cauchy-Schwartz inequality

$$ 
\begin{aligned}
|x^\top \mathrm{vec}(\hat{\theta}_t - \theta)| &\le \|W_t^{-1/2}(\Sigma \otimes I_h)x\| (\xi \|\mathrm{vec}(\theta)\|_{W_t^{-1}} + \|S_t\|_{W_t^{-1}}) \\
&= \|\Sigma^{1/2} \otimes (V_{N_t} + \xi I_h)^{-1/2}x\| (\xi \|\theta\|_{W_t^{-1}} + \|S_t\|_{W_t^{-1}}).
\end{aligned}
$$

Letting

$$ x := (\Sigma^{-1} \otimes (V_{N_t} + \xi I_h))\mathrm{vec}(\hat{\theta}_t - \theta), $$

and plugging back into the last equation yields

$$ 
\begin{aligned}
\|\mathrm{vec}(\hat{\theta}_t - \theta)\|_{\Sigma^{-1} \otimes (V_{N_t} + \xi I_h)}^2 &\le \|\Sigma^{-1/2} \otimes (V_{N_t} + \xi I_h)^{1/2} \mathrm{vec}(\hat{\theta}_t - \theta)\| (\xi \|\mathrm{vec}(\theta)\|_{W_t^{-1}} + \|S_t\|_{W_t^{-1}}), \\
&= \|\mathrm{vec}(\hat{\theta}_t - \theta)\|_{\Sigma^{-1} \otimes (V_{N_t} + \xi I_h)} (\xi \|\mathrm{vec}(\theta)\|_{W_t^{-1}} + \|S_t\|_{W_t^{-1}}),
\end{aligned}
$$

therefore

$$ \|\mathrm{vec}(\hat{\theta}_t - \theta)\|_{\Sigma^{-1} \otimes (V_{N_t} + \xi I_h)} \le \xi \|\mathrm{vec}(\theta)\|_{W_t^{-1}} + \|S_t\|_{W_t^{-1}}, $$

with $W_t := \Sigma \otimes (V_{N_t} + \xi I_h)$ and finally using the bound on (68), we prove that with probability at least $1 - \delta$, for all $t \ge 1$,

$$ \|\mathrm{vec}(\hat{\theta}_t - \theta)\|_{\Sigma^{-1} \otimes (V_{N_t} + \xi I_h)} \le \xi \|\mathrm{vec}(\theta)\|_{\Sigma^{-1} \otimes (V_{N_t} + \xi I_h)^{-1}} + \sqrt{2 \log \left( \frac{\det(V_{N_t} + \xi I_h)^{d/2}}{\delta \xi^{d \cdot h/2}} \right)}. \quad (69) $$

that is

$$ \frac{1}{2} \|\mathrm{vec}(\hat{\theta}_t - \theta)\|_{\Sigma^{-1} \otimes (V_{N_t} + \xi I_h)}^2 \le \left( \frac{\xi}{\sqrt{2}} \|\mathrm{vec}(\theta)\|_{\Sigma^{-1} \otimes (V_{N_t} + \xi I_h)^{-1}} + \sqrt{\log \left( \frac{\det(V_{N_t} + \xi I_h)^{d/2}}{\delta \xi^{d \cdot h/2}} \right)} \right)^2. \quad (70) $$

The result then follows by simple algebra combined with the determinant-trace inequality (cf Lemma 19.4 of Lattimore and Szepesvári (2020)). □

## H.2 Guarantees on the Sampling

The following result is well-known, and its proof can be found in Lattimore and Szepesvári (2020); Degenne et al. (2019).

**Lemma 23 (Elliptic potential lemma).** For $V_0 = \xi I_h$, $\xi \ge 1$, it holds that

$$ \sum_{s=1}^{t} \|a_s\|_{V_{s-1}^{-1}}^2 \le 2h \log \left( \frac{\mathrm{Tr}(V_0) + t L_A^2}{d \det(V_0)^{1/d}} \right). $$

In the following lemma, for two matrices $A, B$, we write $A \ge B$ iff $A - B$ is positive semi-definite.

**Lemma 24.** Let $\omega_{\mathrm{exp}}$ be a distribution on $\mathcal{A}$ supported on some atoms (not necessarily full support) and define the forced-exploration weights as $\tilde{\omega}_t := (1-\gamma_t)\omega_t + \gamma_t\omega_{\mathrm{exp}}$. For all $\varepsilon \in (0, 1/2)$ there exists $t_0(\alpha) \in \mathbb{N}$ and events $\Xi_{2,t}$ (cf (71)) such that for $t \ge t_0(\alpha)$, if $\Xi_{2,t}$ holds then $V_{N_t} \ge \frac{t^{1-\alpha}}{2(1-\alpha)}V_{\omega_{\mathrm{exp}}}$. Moreover, if $V_{\omega_{\mathrm{exp}}}$ is non-singular then $V_{N_t}^{-1} \le 2(1-\alpha)t^{\alpha-1}V_{\omega_{\mathrm{exp}}}^{-1}$.

*Proof.* Let us introduce $D_{t-1}^a := N_{t,a} - \sum_{s=1}^{t-1} \tilde{\omega}_s(a) = \sum_{s=1}^{t-1} (1_{(a_s=a)} - \tilde{\omega}_s(a))$ and the following event

$$ \Xi_{2,t}^a := \left( |D_t| \le \sqrt{2t \log(2|\mathcal{A}|t^2)} \right). $$

By simple algebra we $D_t$ is $\mathcal{F}_t$ measurable and recalling that $\tilde{\omega}_t$ is $\mathcal{F}_{t-1}$ measurable we have

$$ 
\begin{aligned}
\mathbb{E}[D_t^a | \mathcal{F}_{t-1}] &= D_{t-1} + \mathbb{E}[1_{(a_t=a)} - \tilde{\omega}_t(a) | \mathcal{F}_{t-1}] \\
&= 0,
\end{aligned}
$$
so $(D_t)_{t \ge 1}$ is a $\mathcal{F}$ martingale which satisfies $|D_t - D_{t-1}| \le 1$ almost surely. By Azuma's inequality, $\mathbb{P}_\nu(\Xi_{2,t}^a) \ge 1 - \frac{1}{|\mathcal{A}|t^2}$ and defining

$$ \Xi_{2,t} := \bigcap_{a \in \mathcal{A}} \Xi_{2,t}^a, \qquad (71) $$

we have $\mathbb{P}_\nu(\Xi_{2,t}) \ge 1 - 1/t^2$. When $\Xi_{2,t}$ holds, we have for any arm $a \in \mathcal{A}$,

$$ \begin{aligned} N_{t,a} &\ge \sum_{s=1}^{t-1} \tilde{\omega}_s(a) - \sqrt{2t \log(2|\mathcal{A}|t^2)} \\ &\ge \sum_{s=1}^{t-1} \gamma_s \omega_{\exp}(a) - \sqrt{2t \log(2|\mathcal{A}|t^2)}, \\ &\ge \frac{(t-1)^{1-\alpha}}{1-\alpha} \omega_{\exp}(a) - \sqrt{2t \log(2|\mathcal{A}|t^2)} \end{aligned} $$

so that introducing

$$ t_0(\alpha) := \inf \left\{ n : \forall t \ge n, \forall a \in \mathcal{A} \mid \omega(a) > 0, \frac{(t-1)^{1-\alpha}}{(1-\alpha)} \omega_{\exp}(a) - \sqrt{2t \log(2|\mathcal{A}|t^2)} \ge \frac{t^{1-\alpha}}{2(1-\alpha)} \omega_{\exp}(a) \right\}, \quad (72) $$

which is well defined for $\alpha \in (0, 1/2)$, we have for $t \ge t_0(\alpha)$, $N_{t,a} \ge \frac{t^{1-\alpha}}{2(1-\alpha)} \omega_{\exp}(a)$, so that

$$ \begin{aligned} V_{N_t} &\ge \frac{t^{1-\alpha}}{2(1-\alpha)} \sum_{a \in \mathcal{A}} \omega_{\exp}(a) aa^\top \\ &= \frac{t^{1-\alpha}}{2(1-\alpha)} V_{\omega_{\exp}}, \end{aligned} $$

which is the claimed result and the second part of the statement follows from Lemma 28. $\square$

# I TECHNICALITIES

Appendix I gathers existing and new technical results used for our proofs.

Lemma 25 gathers properties on the function $\overline{W}_{-1}$, which is used in the literature to obtain concentration results.

**Lemma 25 (Jourdan et al. (2023).)** Let $\overline{W}_{-1}(x) := -W_{-1}(-e^{-x})$ for all $x \ge 1$, where $W_{-1}$ is the negative branch of the Lambert W function. The function $\overline{W}_{-1}$ is increasing on $(1, +\infty)$ and strictly concave on $(1, +\infty)$. In particular, $\overline{W}_{-1}'(x) = (1 - \frac{1}{\overline{W}_{-1}(x)})^{-1}$ for all $x > 1$. Then, for all $y \ge 1$ and $x \ge 1$, $\overline{W}_{-1}(y) \le x$ if and only if $y \le x - \ln(x)$. Moreover, for all $x > 1$, $x + \log(x) \le \overline{W}_{-1}(x) \le x + \log(x) + \min\{\frac{1}{2}, \frac{1}{\sqrt{x}}\}$.

In general, $\mathrm{Alt}(\theta)$ is not convex, but the result below shows that it is countably convex i.e. union of convex sets, and their number depends on the size of the Pareto set, the dimension, and the number of arms.

**Lemma 26.** For all parameter $\theta$ letting $p := |S^*(\theta)|$, $\mathrm{Alt}(\theta)$ can be written as the union $(p(p-1) + (|\mathcal{Z}| - p)d^p)$ convex subsets.

*Proof.* We let $E_{z,x}(c) = e_c \otimes (z-x)$ and $e_c = (1(c' = c))_{c' \in [d]}$ for $z, x \in \mathcal{Z}$. To further ease notation, we let $E_z = I_d \otimes z^\top$, and $E_{z,x} = E_z - E_x$, which corresponds to row-wise stacking of vectors $(E_{z,x}(c))_c$. It yields $\theta^\top z = E_z \mathrm{vec}(\theta)$ and $E_z \mathrm{vec}(\theta) \prec E_x \mathrm{vec}(\theta)$ iff $E_{z-x} \mathrm{vec}(\theta) \prec 0_d$.

To have a Pareto set different from $S$, either an arm of $S$ should be made sub-optimal or an arm from $\mathcal{Z} \setminus S$ should be Pareto-optimal. We have

$$ \lambda \in \mathrm{Alt}(\theta) \iff S^*(\lambda) \neq S^*(\theta) \qquad (73) $$

$$ \iff \exists z \in S^*(\theta) : z \notin S^*(\lambda) \quad \text{or} \quad \exists z \in \mathcal{Z} \setminus S^*(\theta) : z \in S^*(\lambda) \qquad (74) $$

$$ \iff (\exists z, x \in S^*(\theta) : E_{z-x} \mathrm{vec}(\lambda) \prec 0_d) \quad \text{or} \quad (\exists z \in \mathcal{Z} \setminus S^*(\theta) : E_{z-x} \mathrm{vec}(\lambda) \not\prec 0_d \quad \forall x \in S^*(\theta)) \qquad (75) $$