Michel Waldschmidt
email: miw@math.jussieu.fr

Algebraic values of analytic functions

Keywords: Arithmetic functions, algebraic values, transcendence criterion, diophantine analysis, transcendental functions, PACS:

Given an analytic function of one complex variable f , we investigate the arithmetic nature of the values of f at algebraic points. A typical question is whether f (α) is a transcendental number for each algebraic number α. Since there exist transcendental entire functions f such that f (t) (α) ∈ Q[α] for any t ≥ 0 and any algebraic number α, one needs to restrict the situation by adding hypotheses, either on the functions, or on the points, or else on the set of values.

Among the topics we discuss are recent results due to Andrea Surroca on the number of algebraic points where a transcendental analytic function takes algebraic values, new transcendence criteria by Daniel Delbos concerning entire functions of one or several complex variables, and Diophantine properties of special values of polylogarithms.

Introduction

At the end of XIXth century, after the proof by Hermite and Lindemann of the transcendence of e α for non zero algebraic α, the question arose:

( * ) Does a transcendental analytic function usually takes transcendental values at algebraic points?

In the example of the exponential function e z , the word "usually" stands for avoiding the exception α = 0. Recall also that a transcendental function is a function f (here a complex valued function in a single complex variable) such that, for any nonzero polynomial P ∈ C[X, Y ], the function P (z, f (z)) is not the zero function. If f is meromorphic in all of C, this just means that f is not a rational function. If f is an entire function, namely a function which is analytic in C, to say that f is a transcendental function amounts to say that it is not a polynomial.

However in 1886 Weierstrass found that a positive answer to the initial question ( * ) can hold only for restricted classes of functions: he gave an example of a transcendental entire function which takes rational values at all rational points. He also suggested that there exist transcendental entire functions which take algebraic values at any algebraic point. After the early works of Strauss and Stäckel at the end of XIXth century, one knows now that for each countable subset Σ ⊂ C and each dense subset T ⊂ C there is a transcendental entire function f such that f (Σ) ⊂ T . According to [START_REF] Gramain | Fonctions entières arithmétiques: un aperçu historique[END_REF], in case the countable set Σ is contained in R, then the same conclusion holds also for a dense subset T ⊂ R.

Denote by Q the field of complex algebraic number (Q is the algebraic closure of Q into C). Another construction due to Stäckel produces an entire function f whose derivatives f (t) , for t = 0, 1, . . ., all map Q into Q. Furthermore, Faber refined the result in f (t) (Q) ⊂ Q(i) for any t ≥ 0. Later (1968), A.J. van der Poorten constructed a transcendental entire function f such that f (t) (α) ∈ Q(α) for any t ≥ 0 and any α ∈ Q. A. Surroca [START_REF] Surroca | Sur le nombre de points algébriques où une fonction analytique transcendante prend des valeurs algébriques[END_REF] recently revisited this construction of van der Poorten by providing, for such a function f , a sharp lower bound for the number of α ∈ Q of bounded degree and height such that f (α) has also a bounded height (see section 2).

One may notice that all these constructions may be worked out so that the growth of the constructed function f is as small as possible: given any transcendental entire function ϕ, one may require

|f | R ≤ |ϕ| R
for all sufficiently large R, where

|f | R := sup |z|=R |f (z)|.
On the other hand N. Elkies and A. Surroca give, for a transcendental analytic function f , upper bounds for the number of α ∈ Q of bounded degree and height such that f (α) ∈ Q has also bounded degree and height. We discuss this topic in section 2.

In view of such results, one needs to restrict the initial question ( * ). Most often the restriction is on the class of analytic functions: for instance one requires that the considered function satisfies some differential equation. A fashionable topic nowadays is the study of the arithmetic nature of special values of polylogarithms. Despite the fact that very few information is available so far on the values of Riemann zeta function, one may expect that extending the investigations to multiple zeta values will prove to be a fruitful direction. We consider this topic in section 4 where we notice that the open problem of algebraic independence of logarithms of algebraic numbers reduces to a linear independence question on the values of multiple polylogarithms at algebraic points: the point is that for n ≥ 1, (log(1 -z)) n is a multiple polylogarithm.

2 Algebraic Values of Analytic Functions, Following A. Surroca

In the course of his Diophantine investigations, N. Elkies [START_REF] Elkies | Rational points near curves and small nonzero |x 3 -y 2 | via lattice reduction[END_REF] devoted attention to the number of rational points of bounded height lying on a transcendental curve C. Assume C is a planar curve, in C 2 , and denote by C(Q) the intersection C ∩ Q 2 . One expects indeed the number of (α, β) ∈ C(Q) with h(α) ≤ N and h(β) ≤ N to be quite small compared with the number of α ∈ Q with h(α) ≤ N . Here, h(p/q) = max{log |p|, log q} for p/q ∈ Q with gcd(p, q) = 1 and q > 0. In particular, given an interval I ⊂ R (the problem is local), the number of p/q ∈ Q ∩ I with h(p/q) ≤ N is not too far from e N .

A special case of Elkies result reads as follows:

Let f be a transcendental real analytic function on an open subset of R containing an interval I. For N > 0, consider the set

S N = {x ∈ Q ∩ I ; f (x) ∈ Q, h(x) ≤ N, h(f (x)) ≤ N }.
Then, for each > 0, there exists N 0 > 0 such that

|S N | ≤ e N for N ≥ N 0 .
Several questions then arise: is this estimate best possible? Is it possible to improve it for infinitely many N (in place of all sufficiently large N )? Do similar results hold for algebraic points on a transcendental curve, in place of rational points?

These questions, and much more, are addressed by A. Surroca [START_REF] Surroca | Sur le nombre de points algébriques où une fonction analytique transcendante prend des valeurs algébriques[END_REF]. Denote by h(α) the absolute logarithmic height of an algebraic number α:

h(α) = 1 [Q(α) : Q] log M(α), where M(α) = v max{1, |α| v } is Mahler's measure of α (and v ranges over the set of normalized absolute values of Q(α)). For α = p/q ∈ Q, one recovers the previous definition of h(p/q).
The number of algebraic numbers α with [Q(α) : Q] ≤ D and h(α) ≤ N has been investigated by many a mathematician, including Schanuel, Evertse, Schmidt, Loher and Masser (see for instance [START_REF] Loher | Counting points of bounded height[END_REF][START_REF] Loher | Uniformly counting points of bounded height[END_REF]). Loosely speaking, a rough estimate is e D(D+1)N .

In [START_REF] Surroca | Sur le nombre de points algébriques où une fonction analytique transcendante prend des valeurs algébriques[END_REF], A. Surroca shows that Elkies' result is not far from best possible, to a certain extent:

Theorem 1 Let φ be a positive valued real function such that φ(x)/x → 0 as x → ∞. There exist a transcendental entire function f satisfying

f (t) (α) ∈ Q(α) for all t ≥ 0 and α ∈ Q
and such that, for any positive integer D, there are infinitely many N ≥ 0, for which the set

S N = {α ∈ Q ; |α| ≤ 1, [Q(α) : Q] ≤ D, h(α) ≤ N, h(f (α)) ≤ N } has cardinality |S N | ≥ e D(D+1)φ(N ) .
In the other direction, using transcendence arguments, A. Surroca [START_REF] Surroca | Sur le nombre de points algébriques où une fonction analytique transcendante prend des valeurs algébriques[END_REF] proves the following result, which is exponentially sharper than Elkies' one, but is valid only for infinitely many N :

Theorem 2 Let U be a connected open set in C and K a compact in U. There exists a positive real number c > 0 such that, for any transcendental complex analytic function f in U and any positive integer D, there are infinitely many integers N for which the set

S N = {α ∈ Q∩K ; f (α) ∈ Q, [Q(α, f (α)) : Q] ≤ D, h(α) ≤ N, h(f (α)) ≤ N } has |S N | ≤ cD 3 N 2 .
An explicit value for c follows from [START_REF] Surroca | Sur le nombre de points algébriques où une fonction analytique transcendante prend des valeurs algébriques[END_REF]. Further results, involving multiplicities, as well as S-integers, are given in [START_REF] Surroca | Sur le nombre de points algébriques où une fonction analytique transcendante prend des valeurs algébriques[END_REF].

3 Transcendence Criteria for Entire Functions of One or Several Complex Variables

In this section we concentrate on entire functions in one or several complex variables: the local question of analytic functions in an open subset is only briefly discussed at the end of § 3. For an entire function f in C n , we denote

|f | R = sup |z 1 |=•••=|zn|=R |f (z 1 , . . . , z n )|
the maximum modulus of f on a polydisc of radius R (any other norm would do), and we say that f has order ≤ if lim sup

R→∞ 1 R log |f | R < ∞.
We start with the easier case n = 1. A simple case of Schneider-Lang Transcendence Criterion in one variable ( [10] Chap. III, Th. 1) is :

Theorem 3 Let f 1 , f 2 be two algebraically independent entire functions of finite order in C and let K be a number field. Assume

f j ∈ K[f 1 , f 2 ] for j = 1 and j = 2.
Then the set

S = {w ∈ C ; f j (w) ∈ K for j = 1 and j = 2}
is finite.

Upper bounds for the number of elements in S are known -but here we are just interested in the finiteness result.

One deduces Hermite-Lindemann's Theorem on the transcendence of e β for algebraic β = 0 by considering

f 1 (z) = z, f 2 (z) = e z , S = {mβ ; m ∈ Z}.
Notice that when f 1 (z) = z, the assumption that f 1 , f 2 are algebraically independent just means that f 2 is a transcendental function.

Another consequence of Theorem 3 is Gel'fond-Schneider's Theorem on the transcendence of α β for algebraic α and β with α = 0, β ∈ Q, log α = 0 and α β = exp{β log α}: just consider

f 1 (z) = e z , f 2 (z) = e βz , S = {m log α ; m ∈ Z}.
Theorem 3 is only a special case of Schneider-Lang's criterion in one variable in [10], Chap. IV: the full statement deals with meromorphic functions and more general differential equations; in particular it applies to elliptic and even to abelian functions.

An extension of Theorem 3 to several complex variables has also been considered by Schneider and Lang; it deals with Cartesian products ([10] Chap. IV, Th. 1 and [START_REF] Waldschmidt | Diophantine Approximation on Linear Algebraic Groups[END_REF], Chap. 4, § 4.1). Here is a simplified statement, which is sufficient for us.

Theorem 4 Let f 1 , . . . , f n+1 be algebraically independent entire functions of finite order in C n , K a number field, (e 1 , . . . , e n ) a basis of C n over C and S 1 , . . . , S n subsets of C. Assume

(∂/∂z ν )f j ∈ K[f 1 , . . . , f n+1 ] for 1 ≤ j ≤ n + 1 and 1 ≤ ν ≤ n.
Assume also In 1980, D. Bertrand and D.W. Masser pointed out that Baker's result on the linear independence of logarithms of algebraic numbers was in fact a corollary of Theorem 4 (see Chap. 4 of [START_REF] Waldschmidt | Diophantine Approximation on Linear Algebraic Groups[END_REF]).

f j (w 1 e 1 + • • • + w n e n ) ∈
According to [10] Chap. IV, Nagata suggested that under the assumptions of Theorem 4, the set

S = {w ∈ C n ; f j (w) ∈ K for 1 ≤ j ≤ n + 1}
is contained in an algebraic hypersurface: this is obviously a stronger statement than Theorem 4. This suggestion turns out to be right, as shown by E. Bombieri in 1970 [START_REF] Bombieri | Algebraic values of meromorphic maps[END_REF]:

Theorem 5 Let f 1 , . . . , f n+1 be algebraically independent entire functions of finite order in C n and K a number field. Assume

(∂/∂z ν )f j ∈ K[f 1 , . . . , f n+1 ] for 1 ≤ j ≤ n + 1 and 1 ≤ ν ≤ n.
Then the set

S = {w ∈ C n ; f j (w) ∈ K for 1 ≤ j ≤ n + 1}
is contained in an algebraic hypersurface.

Bombieri's conclusion deals with the source set S ⊂ C n . Another type of result has just been produced by D. Delbos: under the same hypotheses as Theorem 5, the conclusion deals with the range set f (S) ⊂ C n+1 , where

f = (f 1 , . . . , f n+1 ) : C n → C n+1 .
Theorem 6 Let f 1 , . . . , f be entire functions of finite order in C n and K a number field. Assume

(∂/∂z ν )f j ∈ K[f 1 , . . . , f n+1 ] for 1 ≤ j ≤ and 1 ≤ ν ≤ n.
Let S be a finite subset of C such that f j (w) ∈ K for all w ∈ S and 1 ≤ j ≤ .

Then there exists a positive constant c and a positive integer M such that, for each integer N ≥ M , there is a nonzero polynomial Q

N in C[X 1 , . . . , X ] of degree ≤ cN /n such that the function F N = Q N (f 1 , . . . , f ) has a zero of multiplicity ≥ N at each point of S.
Again this result contains Baker's Theorem on the linear independence of logarithms of algebraic numbers: starting with a nontrivial linear relation

β 0 + β 1 log α 1 + • • • + β n-1 log α n-1 = log α n
with algebraic α's and β's, one considers the functions z 0 , e z 1 , . . . , e z n-1 , e

β 0 +β 1 z 1 +•••+β n-1 z n-1 .
The proof of Baker's result along these lines is more natural than the approach by Bertrand-Masser using Theorem 4, but it requires a zero-estimate. On the other hand, in contrast with the proof by Bertrand and Masser, it is effective and yields quantitative results (measures of linear independence for logarithms of algebraic numbers.)

Other criteria are available from [START_REF] Delbos | Criteria involving real analytic functions follow from the "elementary" approach of Gel'fond and Linnik[END_REF]. One may point out that such criteria also apply to real analytic functions, by means of the "elementary approach" of Gel'fond and Linnik in [START_REF] Gel'fond | Elementary methods in the analytic theory of numbers[END_REF]. See [START_REF] Bundschuh | Schneider's transcendence method by elementary means[END_REF] and [START_REF] Bundschuh | Gel'fond's transcendence method by elementary means[END_REF] for the methods of Schneider and Gel'fond respectively. However, according to Delbos, the hypotheses which are necessary for the elementary method to work (involving Rolle Theorem for real functions as a substitute to Schwarz' Lemma for complex functions) usually imply that the functions are just restrictions to the real line of complex analytic functions of finite order.

Further, most results in this section extend easily to meromorphic functions of several variables (essentially, one only needs to avoid singularities). Furthermore, extensions are possible to functions which are defined only locally, say in a polydisc in C n , but then the results are usually weaker: this is the main reason for which p-adic results are sometimes weaker than their complex analogues. A witness of this difficulty is the open problem of proving a p-adic analogue of the Lindemann-Weierstrass Theorem on the algebraic independence of e α 1 , . . . , e αn for linearly independent algebraic α's.

Polylogarithms

The classical polylogarithms A folklore conjecture is that the numbers It is far easier to prove a statement of linear independence rather than a statement of algebraic independence. For instance, according to the Lindemann-Weierstrass' Theorem on the algebraic independence of values of the exponential function, the numbers e α 1 , e α 2 , e α 3 , . . . are algebraically independent if the algebraic numbers α 1 , α 2 , α 3 . . . are linearly independent over the rational number field. However most proofs establish the equivalent statement that the numbers e β 1 , e β 2 , e β 3 , . . . are linearly independent over the field of rational numbers if the algebraic numbers β 1 , β 2 , β 3 . . . are pairwise distinct. In the same way, the algebraic independence problem for the values of the Riemann zeta function boils down to a linear independence result for the values of multiple polylogarithms in one single variable, namely

ζ(2), ζ (3)
ζ(s) = Li s (1) = n 1 >n 2 >•••>n k ≥1 1 n s 1 1 • • • n s k k for s = (s 1 , . . . , s k ) with s 1 ≥ 2, where Li s (z) = n 1 >n 2 >•••>n k ≥1 z n 1 n s 1 1 • • • n s k k for z ∈ C, |z| ≤ 1 with (z, s 1 ) = (1, 1).
There are plenty of linear relations among these numbers, and a conjecture of Zagier [START_REF] Zagier | Values of zeta functions and their applications[END_REF][START_REF] Cartier | Functions polylogarithmes, nombres polyzêta et groupes prounipotents[END_REF][START_REF] Waldschmidt | Multiple Polylogarithms: An Introduction[END_REF] predicts a precise value for the dimension d n of the vector space over the rational number field spanned by these numbers ζ(s) restricted to The fact that the integers d n are bounded from above by the numbers defined by this inductive formula has just been proved by T. Terasoma in [START_REF] Terasoma | Mixed Tate motives and multiple zeta values[END_REF]. As pointed out in [START_REF] Terasoma | Mixed Tate motives and multiple zeta values[END_REF], the same result was announced by A.B. Goncharov in his preprints AG/0005069 and AG/0103059. See the related paper by P. Deligne and A.B. Goncharov NT/0302267.

s 1 + • • • + s k = n, namely d n = d n-2 + d n-3 with d 1 = 0, d 2 = 1. It is known that d 3 = 1 because ζ(3) = ζ(2,
Several related conjectures are explained by Cartier [START_REF] Cartier | Functions polylogarithmes, nombres polyzêta et groupes prounipotents[END_REF]. Also the values at roots of unity of the functions Li s (z) have been considered by a number of authors: in this case it is appropriate to consider polylogarithms in several variables

n 1 >n 2 >•••>n k ≥1 z n 1 1 • • • z n k k n s 1 1 • • • n s k k for z = (z 1 , . . . , z k ) ∈ C, |z i | ≤ 1 with (z 1 , s 1 ) = (1, 1)
. However here we shall consider only multiple polylogarithms in a single complex variable.

We describe now another example of linearization of an algebraic independence question. One of the main conjectures in transcendental number theory states that linearly independent numbers for which e are algebraic (one says usually that such is a logarithm of an algebraic number) are algebraically independent.

Let us show how this question reduces to a linear independence problem on special values, at algebraic points, of multiple polylogarithms.

For simplicity let α 1 , . . . , α m be positive real algebraic numbers such that the numbers 1 = log α 1 , . . . , m = log α m are linearly independent.

We introduce the notation {1} n for the sequence (1, 1, . . . , 1) with n occurrences of 1. It is easy to check that Li {1}n (z) = (-1) n n! (log(1 -z)) n

for n ≥ 1 and |z| ≤ 1 with z = 1 (this is formula (1.1) of [START_REF] Waldschmidt | Multiple Polylogarithms: An Introduction[END_REF]).

Let m and d be two positive integers and Z ij be variables, with 1 ≤ i ≤ m and 1 ≤ j ≤ d+1 m . The determinant

∆(Z) = ( Z i 1 1j • • • Z im mj ) , with i 1 + • • • + i m ≤ d and 1 ≤ j ≤ d+1
m , as a polynomial in the variables Z ij , does not vanish identically. Let a ij be rational numbers such that the determinant ∆ does not vanish at the corresponding point. Writing

(X 0 + a 1j X 1 + • • • + a mj X m ) d as a linear form in the monomials X i 0 0 • • • X im m with i 0 +• • •+i m = d,
we deduce that each of these monomials is a linear combination with rational coefficients of (X 0 + a

1j X 1 + • • • + a mj X m ) d for 1 ≤ j ≤ d+1 m . Since log u + log v = log(uv)
for u, v > 0, it follows that the question of algebraic independence of logarithms of positive algebraic numbers 1 , . . . , m can be reduced to a question of linear independence of values of the multiple polylogarithms Li {1}n , (n ≥ 1) (in a single variable), at algebraic points then there exists (p, q) ∈ Z 2 \ {(0, 0)} such that a p = c q and b q = d p as follows:

• then there exists (p, q) ∈ Z 2 \ {(0, 0)} such that a p = c q and b q = d p Polylogarithms in one variable are related by differential equation, namely they have a generating series which satisfies the Knizhnik-Zamolodchikov equation

y = x 0 z + x 1 1 -z y,
where x 0 and x 1 are two non-commuting variables (see [START_REF] Cartier | Functions polylogarithmes, nombres polyzêta et groupes prounipotents[END_REF]).

Hence in the previous discussion differential equations are always there. However in the hypotheses of Ramachandra's criterion [START_REF] Ramachandra | Contributions to the theory of transcendental numbers. I[END_REF], no differential equation is required, but functional equations (like f (u + v) = f (u)f (v) for the usual exponential function) are there. Also, q-analogues of some the above questions have been extensively studied by Tschakaloff, Lototskii, Bundschuh, Wallisser, Popov and others (see for instance [START_REF] Fel'dman | Number theory. IV. Transcendental Numbers[END_REF] Chap. 2, § 8). A typical example is the entire function f (z) = n≥1

(1 + zq -n ) for q ∈ C, |q| > 1, which is solution of the functional equation f (qz) = (1 + z)f (z).

K for any j = 1 ,

 1 . . . , n + 1 and any (w 1 , . . . , w n ) ∈ S 1 × • • • × S n . Then one at least of the sets S 1 , . . . , S n is finite. This topic was first investigated in 1941 by Th. Schneider when he proved the transcendence of the values of the beta function B(a, b) at rational numbers a and b with a, b and a + b not in Z. It was further studied by S. Lang around 1964 in connection with transcendence results on algebraic varieties.

Li s (z) = n≥1 z n n s for s = 1 , 2 , 1 n s for s = 2 , 3 ,

 12123 . . . and |z| ≤ 1 with (s, z) = (1, 1), are ubiquitous. The study of the arithmetic nature of their special values is a fascinating subject [18]: very few is known. Several recent investigations concern the values of these functions at z = 1: these are the values at the positive integers of Riemann zeta function ζ(s) = Li s (1) = n≥1 . . .. One knows that ζ(3) is irrational (Apéry, 1978), and that infinitely many values ζ(2n + 1) of the zeta function at odd integers are irrational (see the lectures by T. Rivoal and W. Zudilin at this conference).

  , ζ(5), . . . , ζ(2n + 1) do not satisfy any non trivial algebraic relation with rational coefficients: this amounts to say that the values at the odd integers of Riemann zeta function, namely ζ(3), ζ(5), . . ., are algebraically independent over the field Q(π).

d 5

 5 = 2 is equivalent to the open problem to prove that ζ(5)/ζ(2)ζ(3) is irrational.

1 -b 1 1 • • • bm m where b 1 •

 11 , . . . , b m are positive integers. For instance we translate the (real case of the) four exponentials conjecture, namely: If a, b, c, d are algebraic numbers in the range 0 < x < 1 such that (log a)(log b) = (log c)(log d),

  Define f (x) = Li 11 (1 -x) = (1/2)(log x) 2 for 0 < x < 1. If a, b, c, d are algebraic numbers in the range 0 < x < 1 such that f (ab) -f (a) -f (b) = f (cd) -f (c) -f (d),

  The case of entire functions satisfying a linear differential equation provides the strongest results, related with Siegel's E functions[START_REF] Fel'dman | Number theory. IV. Transcendental Numbers[END_REF], Chap. 5. Another class of functions, which are analytic only in a neighborhood of the origin, have also been introduced by C.L. Siegel under the name of G-functions[START_REF] Fel'dman | Number theory. IV. Transcendental Numbers[END_REF], Chap. 5, § 7. More recently, generalizations of transcendence and independence results related to modular functions to more general classes of functions have been introduced by P. Philippon with his new class of K-functions[START_REF] Philippon | Indépendance algébrique et K-fonctions[END_REF]: typical such functions are Ramanujan P , Q and R functions.

	Another type of differential equation is related with the solution, by A.O.
	Gel'fond, of Hilbert's seventh problem, and gives rise to the Schneider-Lang
	criterion. Once again this criterion started from a transcendence result, it
	provides a general statement on the values of analytic functions, and then it
	yields new transcendence results (here in connection with algebraic groups). A
	number of variations have been produced. In section 3 we quote a new result
	by D. Delbos which is a variant of a result by E. Bombieri [12] dealing with
	functions of several variables satisfying algebraic differential equations.

Journal of Computational and Applied Mathematics, to appear. http://www.institut.math.jussieu.fr/∼miw/articles/pdf/avaf.pdf


El Mehdi Saad

Nicolas Verzelen

Alexandra Carpentier

Active Ranking of Experts Based on their Performances in Many Tasks

We consider the problem of ranking n experts based on their performances on d tasks. We make a monotonicity assumption stating that for each pair of experts, one outperforms the other on all tasks. We consider the sequential setting where in each round, the learner has access to noisy evaluations of actively chosen pair of expert-task, given the information available up to the actual round. Given a confidence parameter δ ∈ (0, 1), we provide strategies allowing to recover the correct ranking of experts and develop a bound on the total number of queries made by our algorithm that hold with probability at least 1 -δ. We show that our strategy is adaptive to the complexity of the problem (our bounds are instance dependent), and develop matching lower bounds up to a poly-logarithmic factor. Finally, we adapt our strategy to the relaxed problem of best expert identification and provide numerical simulation consistent with our theoretical results.

Introduction

Consider the problem of ranking n experts based on noisy evaluations of their performances in d tasks. This problem arises in many modern applications such as recommender systems [START_REF] Zhou | The state-of-the-art in personalized recommender systems for social networking[END_REF] and crowdsourcing [START_REF] Snow | Cheap and fast-but is it good? evaluating non-expert annotations for natural language tasks[END_REF][START_REF] Vikas C Raykar | Learning from crowds[END_REF][START_REF] Karger | Iterative learning for reliable crowdsourcing systems[END_REF][START_REF] Lu | Recommender system application developments: a survey[END_REF], where the objective is to recommend, for instance, films, music, books, etc based on the product ratings. Sports is another field where ranking plays an important role via the task of player ranking based on their data-driven performances [START_REF] Morgulev | Sports analytics and the big-data era[END_REF][START_REF] Pappalardo | Playerank: data-driven performance evaluation and player ranking in soccer via a machine learning approach[END_REF]. In many situations, it is possible to rank experts in an active fashion by sequentially auditing the performance of a chosen expert on a specific task, based on the information collected previously.

In this paper, we consider such a sequential and active ranking setting. For a positive integer N we write N = {1, . . . , N }. We consider that the performance of each expert i ∈ n on task j ∈ d is modeled via random variable following an unknown 1-sub-Gaussain distribution ν ij with mean M ij -and the matrix M = (M i,j ) i,j encodes the mean performance of each expert on each task. Samples are collected sequentially in an active way: at each round t, the learner chooses a pair expert-task and receives a sample from the corresponding distribution -and we assume that the obtained samples are mutually independent conditional on the chosen distribution.

Our setting is related to the framework of comparison-based ranking considered in the active learning literature [START_REF] Kevin | Active ranking using pairwise comparisons[END_REF][START_REF] Heckel | Active ranking from pairwise comparisons and when parametric assumptions do not help[END_REF]. This literature stream is tightly connected to the dueling bandit setting [START_REF] Yue | The k-armed dueling bandits problem[END_REF][START_REF] Nir Ailon | Reducing dueling bandits to cardinal bandits[END_REF], where the learner receives binary and noisy feedback on the relative performance of any pair of experts -which is a specific case of our setting when n = d. An important decision for setting the ranking problem is then on defining a notion of order between the experts based on the mean performance M -which is ambiguous for a general M . In the active ranking literature, as well as in the dueling bandit literature, it is customary to define a notion of order among any two experts, for instance, through a score as e.g. the Borda score, or through another mechanism as e.g. Condorcet winners. E.g. the widely used Borda scores corresponds, for each expert i, to the average performance of expert i on all questions -so that this corresponds to ranking experts based on their average performance across all tasks. We discuss this literature in more detail in Section 3.

In this paper, we are inspired by recent advances in the batch literature on this settingwhere we receive one sample for each entry expert-task pair. Beyond the historical parametric Bradley-Luce-Terry (BLT) model [START_REF] Allan | Rank analysis of incomplete block designs: I. the method of paired comparisons[END_REF], recent papers have proposed batch ranking algorithms in more flexible settings, where no parametric assumption is made, but where a monotonicity assumption, up to some unknown permutation, is made on the matrix M . A minimal such assumption was made in [START_REF] Flammarion | Optimal rates of statistical seriation[END_REF] where it is assumed that the matrix M is monotone up to a permutation of its lines, namely of the experts. More precisely, they suppose that there is a complete ordering of the n experts, and that expert i is better than expert k if the first outperforms the latter in all tasks:

" i • ≥ k " : ∀j ∈ d , M ij ≥ M kj .
(

Such a shape constraint is arguably restrictive, yet realistic in many applications -e.g. when the tasks are of varying difficulty yet of same nature. There have been recently very interesting advances in the batch literature on this setting, through the construction and analysis of efficient algorithm that fully leverage such a shape constraint. And importantly, these approaches vastly overperform on most problems with a naive strategy that would just rank the experts according to their Borda scores. Beyond the Borda score, this remark is true for any fixed score, as the recent approaches mentioned ultimatively resort in adapting the computed scores to the problem in order to put more emphasis on informative questions.See Section 3 for an overview of this literature.

In this paper, we start from the above remark in the batch setting -namely that in the batch setting and under a monotonicity assumption, ranking according to fixed scores as e.g. Borda is vastly sub-optimal -and we aim at exploring whether this is also the case in the sequential and active setting. We therefore make the monotonicity assumption of Equation [START_REF] Nir Ailon | Reducing dueling bandits to cardinal bandits[END_REF], and aim at recovering the exact ranking in the active and online setting described above. More precisely, given a confidence parameter δ ∈ (0, 1), our objective is to rank all the experts using as few queries as possible and consequently adapt to the unknown distributions (ν ij ) ij .

In this paper, we make the following contributions: First, In Section 4, we consider the problem of comparing two expert (n = 2) based on their performances on d tasks under a monotonicity assumption. We provide a sampling strategy and develop distribution dependent upper bound on the total number of queries made by our algorithm to output the correct ranking with probability at least 1 -δ, δ ∈ (0, 1) being prescribed confidence. We then consider the problem of ranking estimation for a general n in Section 5, we use the previous algorithm for pairwise comparison as a building block and provide theoretical guarantees on the correctness of our output and a bound on the total number of queries made that holds with high probability. Next, we consider the relaxed objective of identifying the best expert out of n, we provide a sampling strategy for this problem and a bound on the query budget that holds with high probability. In Section 6 we give some instance-dependent lower bounds for the three problems above, showing that all our algorithms are optimal up to a poly-logarithmic factor. In Section 7 of the appendix, we make numerical simulations on synthetic data. The proofs of the theorems are in the appendix.

Problem formulation and notation

Consider a set of n experts evaluated on d tasks. As noted in the introduction, the performance of each expert i ∈ n on task j ∈ d , is modeled via a random variable following an unknown distribution ν ij with mean M ij -and write M = (M ij ) i≤n,j≤d . We refer to ν = (ν ij ) i≤n,j≤d as the (expert-task) performance distribution, and to M = (M ij ) i≤n,j≤d as the mean (experttask) performance. We have two aims in this work: (i) Ranking identification (R), namely identifying the permutation that ranks the expert, and (ii) Best-expert identification (B), namely identifying the best expert -we will define precisely these two objectives later.

On top of assuming as explained in the introduction the existence of a total ordering of experts following (1), we also make an identifiability assumption, so that we have a unique assumption for our problems of ranking (R) and best-expert identification (B); this is summarised in the following assumption.

Assumption 1. Suppose that the following assumption holds:

• Monotonicity: there exists a permutation π :

n → n , such that ∀i ∈ n -1 , ∀j ∈ d : M π(i)j ≥ M π(i+1)j .
• Bounded mean performance: we assume that the mean performance M takes value in [0, 1], namely M i,j ∈ [0, 1] for all i ∈ n and j ∈ d .

We will then assume one of these two identifiability assumptions, depending on whether we are considering the ranking identification problem (R), or the best expert identification problem (B).

• Identifiability for (R):

for i, k ∈ n , if i ̸ = k then ∃j ∈ d : M i,j ̸ = M k,j .
• Identifiability for (B):

for i ∈ {2, . . . , n}, ∃j ∈ d : M π(i),j ̸ = M π(1),j .
Note that under the identifiability assumption for (R), there exists a unique ranking, and that under the identifiability assumption for (B), there exists a unique best expert (and that the identifiability assumption for (R) implies the the identifiability assumption for (B)).

We write π : n → n for the corresponding permutation such that: π(1)

• ≥ π(2) • ≥ . . . • ≥ π(n).
In what follows, we write M n,d ⊂ R n×d for the set of matrices M satisfying Assumption 1. Moreover, we are also going to assume in what follows that the samples collected by the learner are sub-Gaussian.

Assumption 2. For each

i ∈ n , j ∈ d : ν ij is 1-sub-Gaussian.
It is satisfied for e.g. random variables taking values in [0, 1], or for Gaussian distributions of variance bounded by 1.

We consider the fixed confidence setting presented in the sequential and active identification literature [START_REF] Heckel | Active ranking from pairwise comparisons and when parametric assumptions do not help[END_REF][START_REF] Kaufmann | On the complexity of best-arm identification in multi-armed bandit models[END_REF][START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF]. At each time t, the learner tasks an expert on a task -we write (I t , J t ) for this pair of expert and task -based on previous observations, and receive an independent sample Z t following the distribution of ν ItJt . Based on this information, the learner also decides whether it terminates, or continues sampling -and we write N for the termination time, to which we also refer to as number of queries. Upon termination, the learner outputs an estimate, and we consider here the two problems of ranking (R), and best-expert identification (B):

• (i) Ranking identification (R): the learner aims at outputting a ranking π that estimates π. For a given confidence parameter δ ∈ (0, 1), we say that it is δ-accurate for ranking (R) if it satisfies: (R) :

P(π ̸ = π) ≤ δ
• (ii) Best-expert identification (B): the learner aims at outputting an expert k ∈ d that estimates the best performing expert, namely π [START_REF] Nir Ailon | Reducing dueling bandits to cardinal bandits[END_REF]. For a given confidence parameter δ ∈ (0, 1), we say that it is δ-accurate for best-expert identification (B) if it satisfies:

(B) : P( k ̸ = π(1)) ≤ δ.
The performance of any δ-accurate algorithm is then measured through the total number N of queries made when the procedure terminates. The emphasis is then put on developing high probability guarantees on N i.e., bounds on N on the event of probability at least 1 -δ where the δ-accurate algorithm is correct .

Notation: Let A ∈ R n×d be a rectangular matrix, for i ∈ n , we write A i for its i th line. Let ∥.∥ 2 denote the euclidean norm and ∥.∥ 1 denotes the l 1 norm on R d . For two numbers x, y, denote x ∨ y = max{x, y}.

Related work

Best-arm identification and Top-k bandit problems: Active ranking is related to many works in the vast literature of identification in the multi-armed bandit (MAB) model [START_REF] Mannor | The sample complexity of exploration in the multiarmed bandit problem[END_REF][START_REF] Kaufmann | On the complexity of best-arm identification in multi-armed bandit models[END_REF][START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF], where each arm is associated to a univariate random variable. The learner's objective is to build a sampling strategy from the arms' distributions to identify the one with the largest mean -which would resemble our objective of best expert identification.

Other related works consider the more general objective of identifying the top-k arms with the largest means -and in the case where the problem is solved for all k, it resembles the ranking problem. In this work, we consider a more general setting where instead of having a univariate distribution that characterizes the performance of an expert (akin to an arm in the aforementioned literature), we have a multivariate distribution, corresponding to the d questions.

Many of the previous works rely on a successive elimination approach by discarding arms that are seemingly sub-optimal. This idea is not directly applicable in our setting due to the multidimensional aspect of the rewards/performances of each candidate expert. Perhaps, the most natural way to cast our setting into the standard MAB framework is to associate each expert with the average of its performances in all tasks. For expert i ∈ n , let Y i := d j=1 X ij /d and m i := E[Y i ] and observe that due to the monotonicity assumption on the matrix M , the ranking experts with respect to the means m i leads to the correct ranking. Moreover, the learner has access to samples of Y i by sampling the performance of expert i in a task chosen uniformly at random from d. Using the last scheme, one can exploit MAB methods to recover the correct ranking. However, we argue that such methods are sub-optimal: consider the problem of comparing two experts associated with distributions Y 1 and Y 2 defined previously. The minimum number of queries necessary to decide the better expert is of order

O(1/(m 1 -m 2 ) 2 ) = O(d 2 /( d j=1 M 1j -M 2j ) 2
), in contrast, the procedure presented in Section 4, decides the optimal expert using at most O(d/ d j=1 (M 1j -M 2j ) 2 ) up to logarithmic factors. We can show using Jensen's inequality that our bound matches in the worst case the former. However, in general, the improvement can be up to a factor of d. This is due to the fact that our strategy uses a more refined choice of tasks to sample from.

On comparison-based ranking algorithms and duelling bandits: Many previous works consider the problem of ranking based on comparisons between experts in the online learning literature [START_REF] Nir Ailon | Reducing dueling bandits to cardinal bandits[END_REF][START_REF] Chen | Combinatorial pure exploration for dueling bandit[END_REF][START_REF] Heckel | Active ranking from pairwise comparisons and when parametric assumptions do not help[END_REF][START_REF] Kevin | Active ranking using pairwise comparisons[END_REF][START_REF] Jamieson | Sparse dueling bandits[END_REF][START_REF] Urvoy | Generic exploration and k-armed voting bandits[END_REF][START_REF] Yue | The k-armed dueling bandits problem[END_REF]. For instance, in [START_REF] Heckel | Active ranking from pairwise comparisons and when parametric assumptions do not help[END_REF], the authors consider a setting where data consist of noisy binary outcomes of comparisons between pairs of experts. More precisely, the outcome of a queried pair of expert (i, j) ∈ n × n is a Bernoulli variable with mean M ij . The experts are ranked with respect to their Borda scores defined for expert i by τ i := k∈ n \{i} M ik /(n -1). The authors provide a successive elimination-based procedure leading to optimal guarantees up to logarithmic factors. Their bound on the total number of queries to recover the correct ranking is of order Õ( n-1 i=1 /(τ π(i) -τ π(i+1) ) 2 ), where π is the permutation corresponding to the correct ranking. Their setting can be harnessed into ours by considering that d = n and that for each expert i, the task j consists of outperforming expert j. However, contrary to duelling bandit, our model underlies the additional assumption that experts' performances are monotone which is common in the batch ranking literature -see the next paragraph. In the duelling bandit framework, our monotonicity assumption is equivalent to the strong stochastic transitivity assumption [START_REF] Nihar | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF], in the sense that M π(i+1),k ≤ M π(i),k for all k. In this work, our main idea is to build upon the monotonoticity assumption to drastically reduce in some problem instances the number of queries. Existing approaches based on fixed scores cannot be optimal on all problem instances as they do not adapt to the problem -e.g. applying Borda-scores algorithms in our setting leads to a total number of queries of order d 2 /( d j=1 M 1,j -M 2,j ) 2 , which compared to our bound is sub-optimal, with a difference up to a factor d.

On batch ranking:

In Batch learning, the problem of ranking has attracted a lot of attention since the seminal work of 7. In this setting, the learner either observes noisy comparisons between experts or the performances of experts in given tasks. Observing that parametric models such as Bradley-Luce-Terry are sometimes too restrictive 32 have initiated a stream of literature on non-parametric models under shape constraints [START_REF] Flammarion | Optimal rates of statistical seriation[END_REF][START_REF] Nihar | A permutation-based model for crowd labeling: Optimal estimation and robustness[END_REF][START_REF] Mao | Breaking the 1/ √ n barrier: Faster rates for permutation-based models in polynomial time[END_REF][START_REF] Liu | Better algorithms for estimating non-parametric models in crowd-sourcing and rank aggregation[END_REF][START_REF] Nihar | Feeling the bern: Adaptive estimators for bernoulli probabilities of pairwise comparisons[END_REF][START_REF] Pananjady | Worst-case versus average-case design for estimation from partial pairwise comparisons[END_REF][START_REF] Pananjady | Isotonic regression with unknown permutations: Statistics, computation and adaptation[END_REF][START_REF] Pilliat | Optimal permutation estimation in crowd-sourcing problems[END_REF].

Our monotonicity assumption inspired from 11 is the weakest one in this literature. That being said, our results and methods differ importantly from this literature as we aim at recovering the true ranking with a sequential strategy while these works aim at estimating an approximate ranking according to some loss function in the batch setting.

Link to adaptive signal detection: Consider two expert (n = 2) and let M 1 , M 2 ∈ R d be their mean performance vectors on d tasks. A closely related problem to the objective of identifying the best expert out of the two (under monotonicity assumption) is signal detection performed on the differences vector ∆ = M 1 -M 2 , where the aim is to decide whether

{M 1 = M 2 } or {M 1 ̸ = M 2 }.
There is a vast literature in the batch setting for the last testing problem [START_REF] Baraud | Non-asymptotic minimax rates of testing in signal detection[END_REF][START_REF] Yuri I Ingster | Minimax signal detection in ill-posed inverse problems[END_REF][START_REF] Vincent | An introduction to signal detection and estimation[END_REF]. [START_REF] Rui | Adaptive sensing performance lower bounds for sparse signal detection and support estimation[END_REF] considered the signal detection problem in the active setting: given a budget T , the learner's objective is to decide between the two hypotheses {∆ = 0} and {∆ ̸ = 0}, under the assumption that ∆ is s-sparse. When the magnitude of non-zero coefficients is µ, they proved that reliable signal detection requires a budget of order d log(1/δ) sµ 2 , where δ is a prescribed bound on the risk of hypothesis testing. Our theoretical guarantees are consistent with the last bound and are valid for any difference vector ∆.

Link to bandits with infinitely many arms: As discussed earlier, a key feature of our setting, is the ability of the learner to pick the task to assess the performance of chosen experts. When comparing two experts, since the tasks underlying the greatest performance gaps are unknown, the learner should balance between exploring different tasks and committing to a small number of tasks to build a reliable estimate of the underlying differences. This type of breadth versus depth trade-off in pure exploration arises in the context of best-arm identification in the infinitely-many armed bandit problem. It was introduced by [START_REF] Berry | Bandit problems with infinitely many arms[END_REF] and analysed in many subsequent works [START_REF] Jamieson | The power of adaptivity in identifying statistical alternatives[END_REF][START_REF] Aziz | Pure exploration in infinitely-armed bandit models with fixed-confidence[END_REF][START_REF] Katz | The true sample complexity of identifying good arms[END_REF][START_REF] De | Bandits with many optimal arms[END_REF]. While comparing two experts in our setting includes dealing with similar challenges in the previous literature, note that we are particularly interested in detecting the existence (and the sign) of the gaps between experts' performances rather than identifying tasks with the largest performance difference.

Comparing two experts (n = 2)

We start by considering the case where n = 2, which we will then use as a building block for the general case. In this case, the ranking problem (R) is equivalent to the best-expert identification problem (B). Algorithm 1 takes as input two parameters: a confidence level δ ∈ (0, 1), and a precision parameter ϵ > 0, and outputs the best expert if the L 2 distance between the compared experts is greater than ϵ.

One wants ideally to focus on the task displaying the greater gap in performance in order to quickly identify the best expert, however, such knowledge is not available to the learner. This raises the challenge of balancing between sampling as many different tasks as possible to pick one that has a large gap and focusing on one task to be able to distinguish between the two experts based on this task. Such width versus depth trade-off arises in many works of best arm identification with infinitely many arms [START_REF] De | Bandits with many optimal arms[END_REF][START_REF] Jamieson | The power of adaptivity in identifying statistical alternatives[END_REF], where the proportion of optimal arms is p ∈ (0, 1) and the gap between optimal and sub-optimal arms is ∆ > 0. In contrast, the gaps between tasks (equivalent to arms in the previous problem) may be dense, in order to bypass this difficulty we make the following observation: For j ∈ d let x j denote the gap in task j: x j := |M 1,j -M 2,j |. Denote x (j) the corresponding decreasing sequence, we have:

max s∈ d sx 2 (s) ≤ d j=1 x 2 j ≤ log(2d) max s∈ d sx 2 (s) . ( 2
)
The last inequality was presented in [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF] in the context of fixed budget best arm identification (see Lemma F.3 in the appendix). It suggests that, up to a logarithmic factor in d, the L 2 distance is mainly concentrated in the top s * elements with the largest magnitude, where s * is an element in d satisfying the maximum in equation ( 2). We exploit this observation by focusing our exploration effort on tasks with the largest s * gaps.

In the first part of our strategy, presented in Algorithm 1, we discretize the set of possible values of s * and x (s * ) using a doubling trick. The last scheme was adapted from [START_REF] Jamieson | The power of adaptivity in identifying statistical alternatives[END_REF], and allows to be adaptive to the unknown quantities (s * , x (s * ) ). In the second part, given a prior guess (s, h), we run Algorithm 2 consisting of two main ingredients: (i) sampling strategy and (ii) stopping rule. We start by sampling a large number of tasks (with replacement) to ensure that with large probability, a proportion s/d of "good tasks" -i.e. relevant for ranking the two experts, namely the tasks where the experts differ the most -where chosen, then we proceed by median elimination by keeping only half of the tasks with the largest empirical mean in each iteration and doubling the number of queries made to have a more precise estimate of the population means. The aim of this process is to focus the sampling force on the "good tasks", by gradually eliminating tasks where the two experts perform similarly. Also, at each iteration, we run a test on the average of the kept tasks to potentially conclude on which one of the two experts is best and terminate the algorithm.

Algorithm 1 Compare(δ, ϵ)

Input: δ, ϵ.

Initialize: ρ = 1, output k = null. while { k = null} and ϵ 2 < 4 log(2d)d 2 -ρ do for r = 0, . . . , ρ do Set s r = 2 r d/2 ρ , h r = 1/ √ 2 r . Run: Try-compare(δ/(10ρ 3 log(d)), s k , h k ) and Set : k its output. If k ̸ = null, break. end for ρ ← ρ + 1 end while Output: k.
We now turn to the analysis of the performance of compare. We first show that with probability at least 1 -δ, Algorithm 1 does not make the wrong diagnostic. Based on the precision parameter ϵ, we prove that if the unknown squared L 2 distance between the experts' performance vectors is larger than ϵ, then the algorithm identifies the optimal expert out of the two, with a large probability. We also bound on the same event the total number of queries N made by the procedure. Theorem 4.1. Suppose Assumption 1 holds. For δ ∈ (0, 1), ϵ > 0, consider Algorithm 1 with Algorithm 2 Try-compare(δ, s, h)

Input: δ ∈ (0, 1), s ≤ d, h > 0. Initialize: ϕ = 2 ⌈log 2 [26 log(1/δ)d/s]⌉ , n 0 = 64/h 2 , k ← null.
Draw a set (denoted S 1 ) of ϕ elements from d uniformly at random with replacement. Initialize: S , sample the entries (1, j) and (2,

j) t ℓ = nϕ/ S (12) ℓ times, denote (X (u,ℓ) 1,j , X (u,ℓ) 2,j ) u≤t ℓ the obtained samples. Compute: the means μ(12) j,ℓ = 1 t ℓ t ℓ u=1 X (u,ℓ) 1,j -X (u,ℓ) 2,j μ(12) ℓ = 1 n 0 ϕ t ℓ u=1 j∈S ℓ X (u,ℓ) 1,j -X (u,ℓ) 2,j . Denote μ(21) ℓ = -μ (12) ℓ if μ(12) ℓ ≥ 2 log(2/δ) n 0 ϕ then k = 1, break else if μ(21) ℓ ≥ 2 log(2/δ) n 0 ϕ then k = 2, break else
Find the median of (μ

(
H := d ∥M 1 -M 2 ∥ 2 2 .
With probability at least 1 -δ, we have

• The output k satisfies: k ∈ {null, π(1)}. • If ϵ < ∥M 1 -M 2 ∥ 2 , the output satisfies: k = π(1).
Moreover, with probability at least 1 -δ, its total number of queries, denoted N , satisfies:

N ≤ c × log(1/δ)H ϵ , where c = log 2 (d) log(H ϵ ) log(log(H ϵ ∨ d))
, where H ϵ := min{H, d/ϵ 2 } and where c is a numerical constant.

We now discuss some properties of the algorithms and its corresponding guarantees. The sample complexity of Algorithm 1 is of order

H = d/∥M 1 -M 2 ∥ 2
2 , matching the lower bound presented in Theorem 6.1 in Section 6 up to a poly-logarithmic factor. The dependence on the L 2 distance between experts is mainly due to the sampling scheme introduced in Algorithm 2, relying on median elimination. We illustrate the gain of our algorithm with respect to a uniform allocation strategy across all tasks. Such sampling schemes rely on the average performances of each expert across all tasks as a criterion [START_REF] Heckel | Active ranking from pairwise comparisons and when parametric assumptions do not help[END_REF][START_REF] Jamieson | Sparse dueling bandits[END_REF][START_REF] Urvoy | Generic exploration and k-armed voting bandits[END_REF]. Suppose that the difference vector is s-sparse and the amplitude of the non-zero gaps is equal to ∆. Then, sampling a task uniformly at random leads to an expected gap of s∆/d, which leads to a sample complexity of O(d 2 /(s∆) 2 ) in order to identify the optimal expert. On the other hand, our bound suggests that the total number of queries scales as O(d/(s∆ 2 )). This gain is due to the median elimination strategy allowing the concentration of the sampling effort on tasks with large gaps. More precisely, we prove that the initially sampled set of tasks S 1 contains a proportion of s/d of non-zero gaps and that at each iteration in median elimination the last proportion increases by at least a constant factor r > 1. Consequently, after roughly log(d/s) iteration, "good tasks" constitute a constant proportion of the active tasks, which allows the algorithm to conclude by satisfying the stopping rule condition.

Ranking estimation (general n)

Ranking identification

In this section, we consider the task of ranking identification (R). Algorithm 3 takes as input δ ∈ (0, 1) and outputs a ranking π of all the experts. We use Algorithm 1 with precision ϵ = 0 to compare any pair experts. Given Algorithm 1 as a building block, we proceed using the binary insertion sort procedure: experts are inserted sequentially and the location of each expert is determined using a binary search. Algorithm 3 presents the procedure, where in each iteration (corresponding to the insertion of a new expert) a call to the procedure Binary-search is made. A detailed implementation of the last procedure (using Algorithm 1) is presented in Section C in the appendix.

Algorithm 3 Active-ranking(δ)

Input: δ. Initialize: Define π by π(1) = 1.

for i = 2, . . . , n do j ← Binary-search( δ n⌈log 2 (n)⌉ ), i, π, 1, i -1). Shift the rank of π[k] for k ≥ j by one. π[j] ← i end for Output: π.
The following theorem presents the theoretical guarantees on the output and sample complexity of Algorithm 3. Theorem 5.1. Suppose Assumption 1 holds. Let δ ∈ (0, 1), and define for i ∈ n -1 :

H i := d M π(i) -M π(i+1) 2 2
.

Let H * = max i≤n-1 H i . With probability at least 1 -δ, Algorithm 3 outputs the correct ranking, and its total number of queries (denoted N ) is upper bounded by:

N ≤ c × log(1/δ) n-1 i=1 H i , where c = c log(n) log 2 (d) log(H * ) log(n log(H * ∨ d))
and where c is a numerical constant.

The first result states that Algorithm 3 with input δ is δ-accurate. The second guarantee is a control on the total number of queries made by our procedure, with a large probability. As one would expect, the cost of full ranking of experts underlies the cost of distinguishing between two consecutive experts π(i) and π(i + 1) for i ∈ n -1 . The last cost is characterized by the sample complexity

H i = d/ M π(i) -M π(i+1) 2 2
. Consequently, the total number of queries made by Algorithm 3 is of order of O n-1 i=1 H i up to a poly-logarithmic factor.

Best expert identification:

Algorithm 4 takes as input the confidence parameter δ and outputs a candidate for the best expert. Note that while ranking the experts using Algorithm 3 would lead to identifying the top item, one would expect to use fewer queries for this relaxed objective. Algorithm 4 builds on a variant of the Max-search algorithm (a detailed implementation is presented in Section D). In the last algorithm, given a subset of expert S and a precision ϵ, we initially select an arbitrary element as a candidate for the best expert, then we perform comparisons with the remaining elements of S using compare(δ/n, ϵ) and update the candidate for the best expert accordingly. This method leads to eliminating sub-optimal experts that have an L 2 distance with respect to expert π(1) larger than O(ϵ). Therefore, performing sequentially Max-search and dividing the prescribed precision ϵ by 4 after each iteration allows identifying the optimal expert after roughly log

4 (1/ M π(1) -M π(2) 2 2 ) iterations. Algorithm 4 Best-expert(δ) Input: δ, S = n , ϵ = 1, δ ′ = δ/2 while |S| > 1 do S ← Max-search(δ ′ , S, ϵ). ϵ ← ϵ/4 δ ′ ← δ ′ /2 end while Output: S.
The theorem below analyses the performance of Algorithm 4. Theorem 5.2. Suppose Assumption 1 holds. Let δ ∈ (0, 1), and define for i ∈ 2, n :

G i := d M π(1) -M π(i) 2 2
.

Let G * = max i∈ 2,n G i . With probability at least 1 -δ, Algorithm 4 outputs π(1), and the total number of queries (denoted N ) satisfies

N ≤ c × log(1/δ) n i=2 G i , with c = c log 2 (d) log 2 (G * ) log(n log(d))
and c a numerical constant.

In the first result, we show that Algorithm 4 is δ-accurate for (B). The second result presents a bound on the total number of queries made by the algorithm. Observe that for each i ∈ {2, . . . , n} the quantity

G i = d/ M π(1) -M π(i) 2 2
characterizes the sample complexity to distinguish expert π(i) from the optimal expert. In order to identify the correct expert, a number of queries of order G i is required for each suboptimal expert π(i), which leads to a total number of queries of order n i=2 G i , up to a poly-logarithmic factor.

Discussion

Algorithms 3 and 4 are proven to be δ accurate for the ranking problem (R) and best expert (B). Moreover, Theorems 6.2 and 6.3 in Section 6 below show that their sample complexities are optimal up to a poly-logarithmic factor. While both procedures rely on comparing pairs of experts, their use of the compare procedure presented in Algorithm 1 is different. The ranking procedure builds on compare(δ, 0), i.e., we need the exact order between compared experts. In contrast, for best expert identification, we only need approximate comparisons output by compare(δ, ϵ) for an adequately chosen precision ϵ. This difference is due to the fact that a complete ranking underlies comparing the closest pair of experts (in L 2 distance) while best expert identification requires distinguishing only the optimal expert from the sub-optimal ones.

Lower bounds

In this section, we provide some lower bounds on the number of queries of any δ-accurate algorithm. As for the upper bound, we first consider the case of 2 experts (n = 2) in which ranking identification is the same as best expert identification. Then we consider the general case (any n ≥ 2).

Lower bound in the case of two experts (n = 2)

Problem-dependent lower bounds, i.e. lower bounds that depend on the problem instance at hand 1 , are generally obtained by considering slight changes of any fixed problem, and proving 1 which is what we need in order to match the upper bound in Theorem 4.1.

that it is not possible to have an algorithm that performs well enough simultaneously on all the resulting problems. In the ranking problem, our monotonicity assumption constraint heavily restricts the nature of problem changes that we are allowed to consider.

For a given matrix M 0 ∈ M 2,d representing the mean performance of a problem, a minimal and very natural class is the one containing M 0 = ((M 0 ) 1,. , (M 0 ) 2,. ) T , and also the matrix ((M 0 ) 2,. , (M 0 ) 1,. ) T where the two rows (experts) are permuted. In this class, however, we know the position of the question leading to maximal difference of performance between the two experts, as it is the question j such that |(M 0 ) 1,j -(M 0 ) 2,j | is maximised. So that an optimal strategy over this class would leverage this information by sampling only this question, and would be able to terminate using a number of query N smaller in order than log(1/δ)/ max j (M 0 ) 1,j -(M 0 ) 2,j 2 , with probability larger than 1 -δ. Note that this is significantly smaller than our upper bound in Theorem 4.1, but that the algorithm that we alluded to is dependent on the exact knowledge of the matrix M 0 -and in particular the positions of the informative questions -which is not available to the learner, and also very difficult to estimate. In order to include this absence of knowledge in the lower bound, we have to make the class of problems larger, by ensuring in particular that the position of informative questions are not available to the learner. A natural enlargement of the class of problem that takes this into account, but that is still very natural and tied to the matrix M 0 , is to consider the class of all matrices whose gaps between experts are equal to those in M 0 up to a permutation of rows and columns (experts and questions). This is precisely the class that we consider in our lower bound, and that we detail below.

Let M 0 ∈ M 2,d . Write ∆ = |(M 0 ) 1,. -(M 0 ) 2,.
| for the vector of gaps between experts, and π 0 for the permutation that makes M 0 monotone -and we remind that (M 0 ) π 0 (2),. is the least performant of the two experts. Write D M 0 for the set of performance distributions, namely of distributions of X = (X i,j ) i∈ 2 ,j∈ d corresponding to means M , such that: (i) Assumption 2 is satisfied for X, and (ii) The mean performance M π ∈ M 2,d , with associated permutation π that transforms it into a monotone matrix, is such that M π(2),. = (M 0 ) π 0 (2),. , and such that there exists a permutation σ of d such that M π(1),. = (M 0 ) π 0 (2),. + ∆ σ(.) .

The set D M 0 is therefore the set of all distributions of X that are 1-sub-Gaussian, and where while one expert in M is equal to the worst expert (M 0 ) π 0 (2),. of M 0 , the best expert is equal to (M 0 ) π 0 (2),. plus a permutation of the gap vector ∆. This ensures that the gap structure over the mean performance is the same for all problems in D M 0 .

The following theorem establishes a high probability lower bound on the termination time N over the class of problems D M 0 . Theorem 6.1. Fix n = 2. Let d ≥ 1 and δ ∈ (0, 1/4). Consider any matrix M 0 ∈ M 2,d . For any δ-accurate algorithm A for either the ranking identification, or best expert identification (which is the same for n = 2), we have:

max B∈D M 0 P B,A N ≥ d 2∥(M 0 ) 1,. -(M 0 ) 2,. ∥ 2 2 log 1 6δ ≥ δ,
where P B,A is the probability corresponding to samples collected by algorithm A on problem B.

This theorem lower bounds the budget of any δ-accurate algorithm by

d ∥M 1 -M 2 ∥ 2 2 log 1
6δ , which matches up to logarithmic terms the upper bound in Theorem 4.1. Interestingly, the query complexity depends therefore only on ∥(M 0 ) 1 -(M 0 ) 2 ∥ 2 2 , independently of the gap profile of (M 0 ) 1 -(M 0 ) 2 -i.e. of whether there are many small differences in performances across tasks, or a few large differences. Of course, a related optimal algorithm would solve differently the width versus depth trade-off on a sparse or dense problem, as discussed in Section 4, yet it does not show in the final bound on the query complexity thanks to the adaptivity of the sampling. A related phenomenon was already observed -albeit in a different regime and context -in [START_REF] Rui | Adaptive sensing performance lower bounds for sparse signal detection and support estimation[END_REF]. The bound on N in Theorem 6.1 is in high probability, on an event of high probability 1 -δwhere 1 -δ is also the minimal probability of being accurate for the algorithm. This matches our upper bound in Theorem 4.1, where we also provide high probability upper bounds for N .

Lower bound in the general case (any n)

We now consider the general problem of ranking and best expert identification when n > 2. As these two problems are not equivalent anymore, we provide two lower bounds.

In this part, we will consider classes of problems for constructing the lower bound which are wider than the one constructed for the case n = 2, see Theorem 6.1 and the class D M 0 . Driven by the fact that the quantity that appears there is the L 2 norm between experts, we will define the classes of problems by imposing constraints on the L 2 distance between pairs of experts.

Ranking identification

Fix any ∆ = (∆ 1 , . . . , ∆ n-1 ), such that ∆ i > 0 for each i ≤ n -1. Write D n,d ∆ for the set of performance distributions, namely of distributions of X = (X i,j ) i∈ n ,j∈ d corresponding to means M , such that: (i) Assumption 2 is satisfied for X, and (ii) The mean performance

M ∈ M n,d satisfies ∥M π(i) -M π(i+1) ∥ 2 2 = ∆ 2 i , for i = 1, . . . , n -1 .
The class D n,d ∆ is such that the L 2 distance between the i-th best expert π(i) and the i + 1-th best expert π(i + 1) is fixed to ∆ i . We however do not make further assumption on the gap structure within questions, as is done in Theorem 6.1 through the class D M 0 .

Next, we provide a minimax lower bound for general n. The following theorem lower bound the expected budget when we fix the sequence of L 2 distances between consecutive rows. Theorem 6.2. Let n, d ≥ 1, δ ∈ (0, 1). For any δ-accurate algorithm A for ranking identification (R), we have:

max B∈D n,d ∆ E B,A [N ] ≥ n-1 i=1 d ∆ 2 i log(1/(4δ)).
where E B,A is the probability corresponding to samples collected by algorithm A on problem B.

Best expert identification

Fix any positive and non-decreasing sequence ∆ = (∆ 1 , . . . , ∆ n-1 ), such that ∆ i > 0 for each i ≤ n -1. Write D n,d ∆ for the set of performance distributions, namely of distributions of X = (X i,j ) i∈ n ,j∈ d corresponding to means M , such that: the set of distributions of experts performances such that: (i) Assumption 2 is satisfied for X, and (ii) The mean performances matrix M ∈ M n,d satisfies

∥M π(1) -M π(i+1) ∥ 2 2 ≥ ∆ 2 i , for i = 1, . . . , n -1 .

The class D n,d

∆ is such that the L 2 distance between the best expert π( 1) and the i-th best expert π(i + 1) is fixed to ∆ i . It is related to the construction for Theorem 6.2 of the set D n,d

∆ , yet here we only consider the distance to the best expert. Theorem 6.3. Let n, d ≥ 1, δ ∈ (0, 1). For any δ-accurate algorithm A for best expert identification (B), we have:

min A∈A(δ) max B∈D n,d ∆ E B,A [N ] ≥ n-1 i=1 d ∆ 2 i log(1/(4δ)),
where E B,A is the probability corresponding to samples collected by algorithm A on bandit problem B.

Numerical simulations

In this section, we perform some numerical simulations on synthetic data to compare our Algorithm with a benchmark procedure from the literature. We chose AR algorithm from [START_REF] Heckel | Active ranking from pairwise comparisons and when parametric assumptions do not help[END_REF] since they considered the problem of ranking experts in an active setting. Their method is based on pairwise comparisons and uses Borda scores as a criterion to rank experts. In order to harness their model into ours, we proceed as follows: when querying a pair of experts (i, j), we sample a task uniformly at random from d , and sample the performances of experts on this task then output the result.

We focus on the specific problem of identifying the best out of two experts (n = 2) and d = 10 tasks. For each s ∈ d , we consider the following scenario: the performances of both experts in each task follow a normal distribution with unit variance. The means of performances of the sub-optimal expert M π(2) are drawn from [0, 1/2] following the uniform law. We build a gaps vector ∆ s that is s-sparse, the non-zero tasks are drawn uniformly at random from d , and the value of the k th non-zero gap is set to k 3s 2 . Then we consider M π(1) = M π(2) + ∆ s . Figure7 presents the sample complexity of Algorithm 1 with parameters (δ, 0) and AR from [START_REF] Heckel | Active ranking from pairwise comparisons and when parametric assumptions do not help[END_REF], as a function of the sparsity ratio s/d for s ∈ d . The results are averaged over 20 simulations for each scenario, in all simulations both algorithms made the correct output. Algorithm 1 with parameters (δ, 0) outperforms AR for small sparsity rates, mainly due to its ability to detect large gaps, as discussed previously. For large sparsity rates, the gaps vector is dense, and evaluating experts using their average performance across all tasks proves to be efficient. In the last regime, AR procedure outperforms Algorithm 1.

Conclusion

In this paper, we have addressed the challenge of ranking a set of n experts based on sequential queries of their performance variables in d tasks. By assuming the monotonicity of the mean performance matrix, we have introduced strategies that effectively determine the correct ranking of experts. These strategies optimize the allocation of queries to tasks with larger gaps between experts, resulting in a considerable improvement compared to traditional measures like Borda Scores.

Our research has unveiled several promising avenues for future exploration. One notable direction involves narrowing the poly-logarithmic gap in n between our upper and lower bounds for both full ranking and best expert identification. Achieving this goal will require the development of more refined ranking strategies, which we leave for future investigation. Additionally, relaxing the monotonicity assumption considered in this study and adopting a more inclusive framework that accommodates diverse practical applications would be an intriguing area to explore. It would be worthwhile to scrutinize the assumptions made in the study conducted by [START_REF] Bengs | Preference-based online learning with dueling bandits: A survey[END_REF] as a potential direction for further research.

Figure 2: Empirical sample complexity of AR by [START_REF] Heckel | Active ranking from pairwise comparisons and when parametric assumptions do not help[END_REF] and Algorithm 1 in this paper. We varied the number of tasks d ∈ [START_REF] Baraud | Non-asymptotic minimax rates of testing in signal detection[END_REF][START_REF] Rui | Adaptive sensing performance lower bounds for sparse signal detection and support estimation[END_REF][START_REF] Jamieson | The power of adaptivity in identifying statistical alternatives[END_REF][START_REF] Nihar | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF]64] while keeping the sparsity rate constant 1/3. The presented results are averaged over 20 simulations.

A Additional numerical simulations

We add a numerical simulation on synthetically generated data. We consider the task of comapring two experts and suppose that the performance gaps vector is sparse, with a fixed sparsity rate of 1/3. We conduct simulations for various dimension (number of tasks d) and plot the sample complexities of our algorithm and the benchmark algorithm AR ( [START_REF] Heckel | Active ranking from pairwise comparisons and when parametric assumptions do not help[END_REF]).

B Proof of Theorem 4.1

Suppose Assumption 1 holds and that (w.l.o.g) expert 1 is the optimal expert, that is π(1) = 1.

Additional notation: Define x j := M 1,j -M 2,j . Let (x (j) ) j∈ d denotes the (x j ) j∈ d ordered in a decreasing order. Next, we introduce the effective sparsity s * of the vector x. Lemma F.3 states that there exists s * ∈ d such that

∥x∥ 2 2 ≤ s * log(2d) x 2 (s * ) .
If x had been s-sparse and if all the non-zero components of x had been equal, then we would have s = s * and the above inequality would be valid (without the log(2d)). Here, the virtue of the effective sparsity s * is that it is defined for arbitrary vectors x. Then, we denote

x * := x (s * ) , ∆ 2 * := s * x 2 * ,
and

S * := {i ∈ d : x i ≥ x * } ,
where ∆ 2 * plays the role of the square norm x at the scale s * and S * is the corresponding set of size s * of coordinates larger or equal to x * .

In order to prove Theorem 4.1, we will follow three steps:

• Part 1: In Lemma B.3, we show that Algorithm 1 outputs k ∈ {null, 1} with probability at least 1 -δ.

• Part 2: In Lemma B.8 we consider Algorithm 2 with input (δ, s, h). If h < x * and s < s * , then, with probability at least 1 -log(d)δ, the output of the algorithm is k = 1.

• Part 3: As a conclusion, we will gather previous lemmas to derive a bound on the total number of queries until the termination of Algorithm 1.

.

Part 1:

Let us start by introducing the following concentration result for the empirical means computed in Algorithm 2. In the lemma below, the set S is considered as fixed. More generally, S can be any random set independent of the samples used to compute the means (μ j,T ) j,T Lemma B.1. Let T ≥ 1, fix j ∈ d and S ⊂ d . We have

P   1 |S| j∈S μ(21) j,T > 2 log(1/δ) |S|T   ≤ δ, where μ(21) j,T = 1 T T u=1 X (u) 2,j -X (u) 1,j .
Proof. The proof is a straightforward consequence of Chernoff's inequality. Recall that the variable X 2,j -X 1,j is √ 2-sub-Gaussian for any j ∈ S. Moreover, all samples used in the sum j∈S μ(21) j,T are independent. We have

P   1 |S| j∈S μ(21) j,T > 2 log(1/δ) |S|T   ≤ P   1 |S| j∈S μ(21) j,T + 1 |S| j∈S x j > 2 log(1/δ) |S|T   ≤ δ,
where the first inequality follows from the fact x j ≥ 0 (recall that the optimal expert is 1), and the second is a direct consequence of Chernoff's concentration inequality.

Lemma B.2. Consider Algorithm 2 with input (δ, s, h). We have

P k = 2 ≤ 1.75 log(d)δ.
Proof. We have

P k = 2 = P ∃ℓ ≤ log 4/3 (d/s) : μ(21) ℓ > 2 log(2/δ) n 0 ϕ ≤ log 4/3 (d/s) δ 2 ≤ 1.75 log(d)δ ,
where we used Lemma B.1.

Lemma B.3. Consider Algorithm 1 with input (δ, ϵ). The probability of outputting the wrong result satisfies

P k = 2 ≤ 0.6δ .
Proof. When Algorithm 1 with input δ halts, we denote k its returned ranking. For ρ ≥ 1 and r ≤ ρ, denote kρ,r the output of Algorithm 2 with input (δ ρ , s r , h r ). We have

P k = 2 = P ∃ρ ≥ 1, ∃r ≤ ρ : kρ,r = 2 ≤ ∞ ρ=1 ρ r=0 P kρ,r = 2 .
Using Lemma B.2, we have

P k = 2 ≤ ∞ ρ=1 ρ r=0 1.75 log(d) δ 10 log(d)ρ 3 ≤ 1.75δ 10 ∞ ρ=1 ρ + 1 ρ 3 ≤ 0.6δ .
Part 2: To ease notation, we write S ℓ instead of S [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] ℓ in the remainder of this proof. Introduce the following notation

T * := {j ∈ d : x (12) j ≥ 1 2 x * } ; M ℓ := {j ∈ S ℓ ∩ S * : μ(12) j,ℓ ≥ 3 4 x * } ; N ℓ := {j ∈ S ℓ \ T * : μ(12) j,ℓ ≥ 3 4 x * } ; q ℓ := exp(-2 ℓ ); ξ ℓ := |S ℓ ∩ S * | |S ℓ | ≥ s * 2d 4 3 ℓ-1 ; ξ ′ ℓ+1 := |S ℓ+1 ∩ S * | |S ℓ+1 | ≥ 4 3 |S ℓ ∩ S * | |S ℓ | ; Θ ℓ := |S ℓ ∩ (T * \ S * )| |S ℓ | < 1 4 ; Λ ℓ := |S ℓ ∩ S * | |S ℓ | < 1 4 .
While the set S * (introduced earlier) stands for the collection of coordinates that are larger or equal to x * , the set T * contains all moderate coordinates. The other new notation deal with the constant with the ℓ-th iteration in the algorithm. M ℓ corresponds to the set of 'significant' coordinates that lie in S ℓ and such that the empirical mean is large enough, while N ℓ is the set of 'small' coordinates that are in S ℓ and whose empirical mean is large. The events ξ ℓ , ξ ′ ℓ , Θ ℓ , and Λ ℓ are discussed later. The following lemma states the set S 1 at step ℓ = 1 contains a non-vanishing proportion of significant coordinates. Lemma B.4. Consider Algorithm 2 with input (δ, s, h). Suppose that s < s * . Recall that S 1 is the set of sampled questions. We have

P |S 1 ∩ S * | ≥ s * 2d |S 1 | ≥ 1 -δ . Proof. By definition, |S 1 ∩ S * | follows a binomial distribution with parameters (|S 1 |, s * /d).
Hence, Chernoff's inequality (Lemma F.4 with κ = 1/2) enforces that

P |S 1 ∩ S * | ≤ s * 2d |S 1 | ≤ exp - s * 8d |S 1 | ≤ exp - s * s log(1/δ) ≤ δ ,
where we used |S 1 | = ϕ ≥ 26 log(1/δ)d/s and s < s * .

The next lemma roughly states that, provided the event ξ ℓ holds, then, with high probability, S l+1 will contain a larger proportion of significant questions. More precisely, we prove that the number M ℓ of significant questions with a large empirical mean is high and the number S ℓ of non-significant questions with a large empirical mean is small. Lemma B.5. Consider Algorithm 2 with inputs (δ, s, h) such that s < s * and h < x * . For any ℓ ≥ 1, we have

P M ℓ ≤ 2 3 |S ℓ ∩ S * | ξ ℓ ≤ δ ; P N ℓ ≥ 1 4 |S ℓ | ξ ℓ ≤ δ . Proof. Define Mℓ := |S ℓ ∩ S * |. Using the definition of M ℓ , we have Mℓ = j∈S ℓ ∩S * 1 μ(12) j,ℓ < 3 4 x * . Let j ∈ S ℓ ∩ S * , recall that E[μ (12)
j,ℓ ] ≥ x * , and the samples (X

(u) 1,j -X (u) 2,j ) are √ 2-sub-Gaussian. Therefore, using Chernoff's bound P μ(12) j,ℓ < 3 4 x * ≤ exp -t ℓ x 2 * 32 = exp -2 ℓ-1 n 0 x 2 * 32 ≤ exp(-2 ℓ ) = q ℓ ,
since h ≤ x * and by definition of ℓ and of q ℓ . Thus, the variables

j,ℓ < 3 4 ∆ * ) for j ∈ S ℓ ∩S * are stochastically dominated by B(q ℓ ) and independent. Therefore Mℓ is stochastically dominated by B(|S ℓ ∩ S * |, q ℓ ), where B(a, b) denotes the binomial distribution with parameters (a, b). Let κ := 1/(3q ℓ ) -1 > 0, we have

P M ℓ ≤ 2 3 |S ℓ ∩ S * | ξ ℓ = P Mℓ > 1 3 |S ℓ ∩ S * | ξ ℓ = P Mℓ > (1 + κ)q ℓ |S ℓ ∩ S * | ξ ℓ
Using Lemma F.4 and the definition of the event ξ ℓ

P M ℓ ≤ 2 3 |S ℓ ∩ S * | ξ ℓ ≤ exp{κq ℓ |S ℓ ∩ S * | -(1 + κ)q ℓ |S ℓ ∩ S * | log(1 + κ)} ≤ exp 1 3 -q ℓ - 1 3 log 1 3q ℓ |S ℓ ∩ S * | .
Recall that q ℓ = exp(-2 ℓ ) so that κ > 1/5. Using the expression

|S ℓ | = |S 1 | 2 ℓ-1 ≥ 26d log(1/δ) 2 ℓ-1 s
, the definition of the event ξ ℓ , and s > s * , we deduce that

P M ℓ ≤ 2 3 |S ℓ ∩ S * | ξ ℓ ≤ exp 1 3 -exp(-2 ℓ ) - 2 l -log(3) 3 2 3 ℓ-1
13 log(1/δ) .

For ℓ ≥ 3, we have 2 ℓ-1 ≥ log(3) + 3, which leads to

P M ℓ ≤ 2 3 |S ℓ ∩ S * | ξ ℓ ≤ exp - 4 3 ℓ-1 13 log(1/δ) ≤ δ .
One easily check that this bound is still true for ℓ = 1, and ℓ = 2. We have proved the first part of the lemma.

For the second result, we start from

N ℓ = j∈S ℓ \T * 1 μ(12) j,ℓ ≥ 3 4 x * .
Arguing as in the first part, we easily check that the variables 1(μ

j,ℓ ≥ 3 4 x * ), for j ∈ S ℓ \ T * are independent and stochastically dominated by B(q ℓ ). Hence N ℓ is stochastically dominated by B(|S ℓ |, q ℓ ). Let κ ′ = 1 4q ℓ -1 ≥ 0. Using again Lemma F.4, we have

P N ℓ ≥ 1 4 |S ℓ | ξ ℓ = P N ℓ ≥ (1 + κ)q ℓ |S ℓ | ξ ℓ ≤ exp{κq ℓ |S ℓ | -(1 + κ)q ℓ |S ℓ | log(1 + κ)} ≤ exp 1 4 -q ℓ - 1 4 log 1 4q ℓ |S ℓ | .
Next, we use the expression of |S ℓ | and obtain

P N ℓ ≥ 1 4 |S ℓ | ξ ℓ ≤ exp 1 4 -exp(-2 ℓ ) - 1 4 log exp(2 ℓ ) 4 26d log(1/δ) s2 ℓ-1 .
Recall that d ≥ s. As in the first part of the proof, we easily check that ℓ = 1 and ℓ = 2 the above expression is smaller or equal to δ. For ℓ ≥ 3, we have 2 l-1 ≥ 1 + log(4), which implies also that

P N ℓ ≥ 1 4 |S ℓ | ξ ℓ ≤ exp - 2 ℓ-1 4 • 26 2 ℓ-1 log(1/δ) ≤ δ .
The event Λ ℓ and Θ ℓ respectively state that the proportion of significant (and moderately significant) questions in |S ℓ | is smaller or equal to 1/4. The following lemma roughly states that as long ξ ℓ , Θ ℓ+1 , and Λ ℓ+1 , then the proportion of significant questions in S ℓ+1 is significantly reduced.

Lemma

≤ P M ℓ < 2 3 |S ℓ ∩ S * | ξ ℓ ≤ δ ,
where we used Lemma B.5 in the last line.

Upper bound for the second term in the rhs of [START_REF] Aziz | Pure exploration in infinitely-armed bandit models with fixed-confidence[END_REF]. The event Θ ℓ+1 implies in particular that

|S ℓ+1 ∩ S * | + |S ℓ+1 \ T * | ≥ 3 4 |S ℓ+1 |.
Moreover, we have that the event {m ℓ ≥

∩ S * | + N ℓ ≥ 3 4 |S ℓ+1 |} ξ ℓ ≤ P N ℓ ≥ 1 2 |S ℓ+1 | ξ ℓ = P N ℓ ≥ 1 4 |S ℓ | ξ ℓ ≤ δ,
where we used the definition of Λ ℓ+1 and Lemma B.5 in the second line. We conclude that P Θ ℓ+1 and Λ ℓ+1 and ¬ξ ′ ℓ+1 ξ ℓ ≤ 2δ .

Consider Algorithm 2 with input (δ, s, h). Let l := ⌈log 4/3 (d/s * )⌉ + 1. Introduce the following event:

E ℓ := {Algorithm 2 made at least ℓ iterations} and

u=ℓ u=1 (Θ u ∩ Λ u ). ( 4
)
Lemma B.7. Consider Algorithm 2 with input (δ, s, h). Suppose that h < x * and s < s * . We have P(E l) ≤ 2 lδ.

Proof. First, let us prove by induction that, for any ℓ ≤ l, we have P(¬ξ ℓ and E ℓ ) ≤ 2ℓδ.

The assertion for ℓ = 1 is a direct consequence of Lemma B.4. Suppose that the result for some ℓ ≤ l. Observe that, by definition, the event ¬ξ ℓ+1 implies that either we have ¬ξ ′ ℓ+1 or we have ¬ξ ℓ . This leads us to P(¬ξ ℓ+1 and E ℓ+1 ) ≤ P ¬ξ ′ ℓ+1 and E ℓ+1 + P(¬ξ ℓ and E ℓ+1 ) ≤ P ¬ξ ′ ℓ+1 and Λ ℓ+1 and Θ ℓ+1 + P(¬ξ ℓ and E ℓ ) ≤ 2δ + 2ℓδ, where we used Lemma B.6 and induction hypothesis in the last line.

Observe that

¬ξ l = |S l ∩ S * | |S l| < s * 2d 4 3 l-1 ; Λ l = |S l ∩ S * | |S l| < 1 4 .
Recall that l = ⌈log 4/3 (d/s * )⌉ + 1, which implies that s * 2d 4 3 l ≥ 1 4 . Hence, we have ¬ξ l ⊂ Λ l and we conclude that P(E l) = P(¬ξ l and E l) ≤ 2ℓδ.

The following result is built upon the previous lemmas and states that Algorithm 2 returns null with a very small probability provided that h and s are small enough.

Lemma B.8. Consider Algorithm 2 with input (δ, s, h). Suppose that h < x * and s < s * . We have P { k = null} ≤ 3 lδ.

Proof. We have: (otherwise, the algorithm halts at iteration ℓ and outputs k ∈ {1, 2}). Then

P { k = null} = P { k = null}
P { k = null} and ¬E ≤ l ℓ=1 P μ(12) ℓ < 2 log(2/δ) n 0 ϕ and {¬Θ ℓ ∪ ¬Λ ℓ } = l ℓ=1 P      1 |S ℓ | j∈S ℓ x j - μ(12) ℓ > 1 |S ℓ | j∈S ℓ x j - 2 log(2/δ) n 0 ϕ    and {¬Θ ℓ ∪ ¬Λ ℓ }   ≤ l ℓ=1 P   1 |S ℓ | j∈S ℓ x j - μ(12) ℓ > 1 8 x * - 2 log(2/δ) n 0 ϕ   ≤ l ℓ=1 P   1 |S ℓ | j∈S ℓ x j - μ(12) ℓ > 2 log(2/δ) n 0 ϕ   ≤ lδ ,
where we used the definition of Θ ℓ and Λ ℓ in the third line, the assumption h < x * and s < s * in the fourth line and Chernoff's bound in the last line.

Part 3:

Here, we gather all the previous lemmas to establish the three claims of the theorem. (

Conclusion

) 5
By assumption, we have x Consider Algorithm 1 with input (δ, ϵ). Suppose that ϵ 2 ≥ d/H, therefore the maximum number of iterations is less than ρ ′ = ⌊log 2 (4 log(2d)d/ϵ 2 )⌋. Therefore the total number of queries satisfies:

N ≤ ρ ′ ρ=1 ρ r=0 N sr,hr ≤ 4096[log 4/3 (d) + 2] ρ ′ ρ=1 ρ r=0 log(1/δ r ) s r h 2 r ≤ 10 4 log(d) log 10 log(d)ρ ′ 3 δ ρ ′ ρ=1 (ρ + 1)2 ρ ≤ 8.10 4 log 2 (2d) log 2 log(8d log(d)) ϵ 2 log 10 log(d)ρ ′3 δ d ϵ 2 ≤ c ′ log 2 (2d) log log(2d) ϵ 2 log 2 log(2d/ϵ 2 ) δ d ϵ 2 ,
where c ′ is a numerical constant. Now suppose that ϵ 2 < d/H. We have shown previously that, with probability at least 1 -δ, the algorithm stops no later than at iteration ρ * and r * (defined in [START_REF] Bengs | Preference-based online learning with dueling bandits: A survey[END_REF]). Under such an event, the total number of iterations satisfies As a consequence, the total number N of queries from iteration 2 to r * satisfies

N ≤ ρ * -1 ρ=1 ρ r=0 N sr,hr + r * r=0 N sr,hr ≤ 4096[log 4/3 (d) + 2]   ρ * -1 ρ=1 ρ r=0 log(1/δ r ) s r h 2 r + r * r=0 log(1/δ r ) s r h 2 r   ≤ 10
N ≤ c ′ d log 2 (d) log n log(d) δ n + r * r=2 r log(d4 2r )4 2r |B 2•4 -r+2 | ≤ c ′ d log 2 (d) log n log(d) δ   n + i̸ =i * r * r=2 k log(d4 2r )4 2r 1{∥M i -M i * ∥ 2 ≤ 2 • 4 -r+2 }   ≤ c ′′ d log 2 (d) log n log(d) δ   n + i̸ =i * 1 ∥M i -M i * ∥ 2 2 log 2 d ∥M i -M i * ∥ 2 2 ∨ 1   .
The result follows.

E Proofs of the lower bounds

Proof of Theorem 6.1. Fix d ≥ 1, δ ∈ (0, 1/4), and ∆ ∈ (R + ) d such that ∥∆∥ 2 > 0, and let A be a δ-accurate algorithm. Define the 2 × d matrix M * by M * 1,j = ∆ j for j ∈ d and M * 2,j = 0. For any permutation π of 2 and any permutation σ of d , we write M * π,σ for the permuted matrix such that (M * π,σ ) i,j = (M * π,σ ) π -1 (i),σ -1 (j) . Obviously, we have M * π,σ belongs to M n,d and π is the permutation that order the rows of M * π,σ . For any permutations π and σ, we write P (π,σ) for the distribution of the data such that X i,j ∼ N [(M * π,σ ) i,j , 1]. We also introduce the 'null' distribution P 0 such that X i,j ∼ N [0, 1]. There exist only 2 permutations on 2 , that we respectively denote π 0 (for the identity permutation) and π 1 . Since the strategy A is δ-accurate, we have, for any permutation σ of d , that

P (π 0 ,σ) (π ̸ = π 0 ) ≤ δ and P (π 1 ,σ) (π ̸ = π 1 ) ≤ δ . ( 7
)
Denote N the total budget of the algorithm A. Let x be the smallest integer such that max σ max z=0,1

P (πz,σ) [N > x] ≤ δ
Next, we claim that P 0 (N > x) ≥ 1 -2δ. Indeed, for any κ > 0, consider the 2 × d matrix M ′ such that M ′ 1,1 = κ and M ′ i,j = 0 otherwise. Write M ′ π 0 and M ′ π 1 for the matrix M ′ where we have permuted the rows according to π 0 and π 1 . Write P ′ (π 0 ) and P ′ (π 1 ) for the corresponding distribution of the data. Since the strategy A is δ-accurate, we have

P ′ (π 0 ) (π ̸ = π 0 ) ≤ 1 -δ and P ′ (π 1 ) (π ̸ = π 0 ) ≤ 1 -δ As a consequence, P ′ (π 0 ) (π = π 1 and N ≤ x) + P ′ (π 1 ) (π = π 0 and N ≤ x) ≤ 2δ
On the event where N ≤ x, the distributions P ′ (π 0 ) and P ′ (π 1 ) converges in total variation distance towards P 0 when κ goes to zero. This implies that P 0 [N ≤ x] ≤ 2δ.

Consider the new algorithm A ′ defined as follows. If the total budget of A is smaller or equal to x, then it returns H = H 1 , if the total budget is higher than, then it returns H = H 0 ". With a slight abuse of notation, we still write N for the total budget of A ′ and P (π,σ) for the corresponding distributions. By definition of x, we have max σ max z=0,1

P (πz,σ) [ H = H 1 ] ≥ 1 -δ and P 0 [ H = H 1 ] ≥ 1 -2δ .
By definition of the total variance distance T V between distributions (see Theorem 2.2 of [START_REF] Alexandre | Introduction to nonparametric estimation[END_REF]), we derive that min z=0,1

1 d! σ
TV P (πz,σ) , P 0 ≥ 1 -3δ By Lemma F.2, we control the total variation distance in terms of Kullback-Leibler discrepancy.

TV P (π,σ) , P 0 ≤ 1 -

1 2 exp    - 2 i=1 d j=1 E 0 [N i,j ] KL P (0) i,j , P π,σ i,j    , (8)
Under P π,σ , the distribution the (i, j)-th entry is N (M * π -1 (i),σ -1 (j) , 1). Fixing π = π 0 and averaging over all permutation σ leads to Proof of Theorem 6.2. We introduce the n × d matrix M 0 by (M 0 ) 1,j = 1 and (M 0 ) i,j = 1 -i-1 l=1 ∆ l / √ d for i = 2, . . . , n -1. All the rows of M 0 are constant. Obviously, the true ranking π is the identity, while ∥M i -M i+1 ∥ 2 2 = ∆ 2 i . Given i ∈ n 0 -1 , let π i,i+1 denote the transposition that exchanges i and i + 1. Any δ-accurate algorithm A is able to decipher with probability higher than 1-δ between the matrix M 0 and the permuted matrix (M 0 ) π i,i+1 , which, since the rows of M 0 are constant, is equivalent to best arm identification in a two-arm problem with gap ∆ i / √ d. Assume that we observe the matrix M 0 with a standard Gaussian noise and denote B 0 for the corresponding distribution. By [START_REF] Kaufmann | On the complexity of best-arm identification in multi-armed bandit models[END_REF], we have E B 0 ,A [N i+1 ] ≥ d log[1/4δ)]/∆ 2 i . By linearity, we deduce that

E B [N ] ≥ n-1 i=1 d ∆ 2 i log[1/(4δ)] ,
which concludes the proof.

Proof of Theorem 6.3. This theorem is a straightforward consequence of existing lower bounds in multi-armed bandits for best arm identification. Indeed, the set D n,d ∆ contains in particular problem instances that are constant over questions. For these instances, our d-dimensional problem is akin to a one dimensional problem, i.e. to a standard multi-armed bandit problem. Existing lower bounds in this case imply the bounds, see e.g. [START_REF] Kaufmann | On the complexity of best-arm identification in multi-armed bandit models[END_REF].

F Technical results

The first lemma is a slight generalization of Lemma 3. Proof. Fix any such b and x. We simply exchange the summation order.

H d ≤ log(d) + γ + 1 2d -1 .
The following lemma is a direct consequence of Chernoff's inequality applied to a binomial random variable. Proof. We only show the first inequality, the other ones being classical. All of them are consequences of Chernoff inequality. For a variable Y , we denote M Y (t) its moment generating function. Recall that, for any X i ∼ Ber(p), we have M X i (t) ≤ e p(e t -1) . Moreover for X = n i=1 X i , we have

P(X ≥ k) ≤ min t>0 M X (t) e (k) = min t>0 n i=1 M X i (t) e tk
≤ min t>0 e p(e t -1) n e tk = min t>0 e µ(e t -1) e tk .

For k = (1 + κ)µ, we take t = log(1 + κ) and we obtain P(X ≥ (1 + κ)µ) ≤ e µ(e log(1+κ) -1) e (1+κ)µ log(1+κ) = e κµ (1 + κ) (1+κ)µ .

1 = S 1 .

 11 for ℓ = 1, . . . , ⌈log 4/3 (d/s)⌉ + 1 do Sample: For each element j ∈ S

Figure 7

 7 Figure 7 presents the empirical sample complexity of Algorithm 1 and AR as a function of the sparsity rate s/d. The results show, as suggested by theoretical guarantees, that

Figure 1 :

 1 Figure 1: Empirical sample complexity of AR by [13] and Algorithm 1 in this paper. We varied the sparsity rate of the gaps vector s/d ∈ [5%, 100%]. The presented results are averaged over 20 simulations.

  Figure A displays the results.

  for the first claim: Lemma B.3 leads to the first claim of Theorem 4.1. Conclusion for the second claim: Let us prove that if ϵ 2 < d/H then Algorithm 1 with input (δ, ϵ) outputs k = 1 with probability at least 1 -δ. By Lemma B.3, we have P( k = 2) ≤ 0.6δ. Hence, it suffices to prove that P( k = null) ≤ 0.4δ. Define ρ * := log 2 16d s * x 2 * and r * := log 2 1 x 2 * .

3 10r * 3

 33 log(d) (⌈log 4/3 (d/s * )⌉ + 1)δ ≤ 0.4δ. We conclude that P[ k = 1] ≥ 1 -δ. Conclusion for the third claim: The total number of queries made by Algorithm 2 with inputs (δ, s, h) is at most N s,h = 4096 log 4/3 (16d/(9s)) log(1/δ) sh 2 .

E 0 2 ,

 02 [N 1,j ]∆ 2 σ -1 (j) ≥ log(1/(6δ)) .Arguing similarly for the permutation π 1 , we arrive at1 d! σ d j=1 E 0 [N 1,j + N 2,j ]∆ 2 σ -1 (j) ≥ 2 log(1/(6δ)) .Then, by Lemma F.1, this left-hand-side term of this equation is larger or equal toE 0 [N ]∥∆∥ 2 2 /d. Since E 0 [N ] ≥ (1 -2δ)x, we conclude that x ≥ d log(1/6δ) 2∥∆∥2which conclude the proof.

1 in 8 Lemma F. 1 .

 81 Let Υ d denote the set of permutations on d . Consider any vectors x = (x 1 , . . . , x d ) ∈ R d + and any b = (b 1 , . . . , b d ) ∈ R d + .

2 (Lemma F. 3 . 9 )

 239 [START_REF] Kaufmann | On the complexity of best-arm identification in multi-armed bandit models[END_REF], with slight modification). Let ν and ν ′ be two collections of d probability distributions on R, such that for all a ∈ d , the distributions ν a and ν a ′ are mutually absolutely continuous. For any almost-surely finite stopping time τ with respect to the data collected before τ ,sup E∈Fτ |P ν (E) -P ν ′ (E)| ≤ 1 -1 2 expd a=1 E ν [N a (τ )]KL(ν a , ν ′ a ) . Let (x i ) i∈d denote a sequence of non-increasing numbers in [0, 1]. We have d i=1 x i ≤ log(2d) max 1≤s≤d {s x s }. (Proof. Suppose for the sake of contradiction that, for any s ∈ d , we have s log(2d) x s < d i=1 x i . Dividing the above inequality by s and summing it over s ∈ d , we deduce that log(2d) which contradict the upper bound on the partial sum of harmonic series H d = d s=1 1 s :

Lemma F. 4 . 2 µ 2 P

 422 Let X = n i=1 X i , where X i are independent and follow the Bernoulli distribution with parameter p, and let µ = E[X], we have for any κ ≥ 0P(X ≥ (1 + κ)µ) ≤ e κµ (1 + κ) (1+κ)µ .Besides, for any κ ∈ (0, 1), we haveP(X ≤ (1 -κ)µ) ≤ expκ (X ≥ (1 + κ)µ) ≤ expκ 2 µ 3

Upper bound for the first term in the rhs of

  B.6. Let any integer ℓ ≥ 1, we have P Θ ℓ+1 and Λ ℓ+1 and ¬ξ ′ ℓ+1 ξ ℓ ≤ 2δ . (3). The event m ℓ < (3/4)x * implies that {j ∈ S ℓ ∩ S

	:	μ(12) j,ℓ ≥ 3 4 x * } ⊂ S ℓ+1 . Hence,
		j ∈ S ℓ ∩ S * :	μ(12) j,ℓ ≥	3 4	x * ⊂ S ℓ+1 ∩ S * ,
	which gives M ℓ ≤ |S ℓ+1 ∩ S * |. This leads us to
	P Θ ℓ+1 and Λ ℓ+1 and ¬ξ ′ ℓ+1 and {m ℓ <	3 4	x * } ξ ℓ ≤ P ¬ξ ′ ℓ+1 and {m ℓ <	3 4	x * } ξ ℓ
						= P {|S ℓ+1 ∩ S * | ≤	2 3	|S ℓ ∩ S * |} and {m ℓ <	3 4	x * } ξ ℓ
						≤ P {M ℓ <	2 3	|S ℓ ∩ S * |} and {m ℓ <	3 4	x * } ξ ℓ
	Proof. Recall that m instead of m (12) ℓ in this proof for the sake of simplicity. We have (12) denotes the median computed in Algorithm 2, we will denote m ℓ ℓ
	P Θ ℓ+1 and Λ ℓ+1 and ¬ξ ′ ℓ+1 ξ ℓ = P Θ ℓ+1 and Λ ℓ+1 and ¬ξ ′ ℓ+1 and {m ℓ <	3 4	x * } ξ ℓ
		+ P Θ ℓ+1 and Λ ℓ+1 and ¬ξ ′ ℓ+1 and {m ℓ ≥	3 4	x * } ξ ℓ .
						(3)

*

  which gives |S ℓ+1 ∩ S * | + N ℓ ≥ |S ℓ+1 ∩ S * | + |S ℓ+1 \ T * | ≥ 3 4 |S ℓ+1 |.We conclude that P Θ ℓ+1 and Λ ℓ+1 and ¬ξ ′ ℓ+1 and {m ℓ ≥

		3 4 x * } implies that
	j ∈ S ℓ \ T * :	μ(12) j,ℓ ≥ x 3 3 4 4 x

* ⊃ S ℓ+1 \ T * , * } ξ ℓ ≤ P Λ ℓ+1 and {|S ℓ+1

  and ¬E l + P { k = null} and E l ≤ P { k = null} and ¬E l + 2 lδ, where we used Lemma B.7. Now Suppose E l is false. Hence, there exists an iteration ℓ ≤ l such that either Θ ℓ is false or Λ ℓ is false. Recall that { k = null} implies that μ[START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF]

	ℓ	< 2 log(2/δ) n 0 ϕ

  2 * ≤ 1, so that r * ≥ 1 and ρ * ≥ 1. Recall that ϵ 2 < d H ≤ log(2d)s * x 2 * ≤ 16 log(2d)d 2 -ρ * . If Algorithm 1 returns k = null, then it implies in particular that Algorithm 2 returns k = null at the iteration ρ * and r * ≤ ρ * . At this step, the inputs (δ r * , s r * , h r * ) of Algorithm 2 satisfy δ r * ≤ δ/(10r * 3 log(d)), h r * = 1/ √ 2 r * ≤ x * , and s r * = 2 r * d/2 ρ * ≤ s * . We then deduce from Lemma B.8 that k = null with probability less or equal to

  := min i̸ =i * ∥M i -M i * ∥ 2 2 for the minimum distance between i * and another expert. Denote r * = ⌈log 4 (8/∆ * )⌉. By (6), we have r ≤ r * . By Lemma D.2, the total number of queries made at iteration r is no larger than where c is a numerical constant and |S r-1 | ≤ |B 2•4 -r+2 | for r ≥ 2 and |S 0 | = n.

	Write ∆ c log 2 (d) log	d 4 -2r log	n2 k log( d 4 -2r ) δ	d|S r-1 | 4 -2r ,
	4 log(d) log	10 log(d)ρ * 3 δ	ρ * ρ=1 (ρ + 1)2 ρ
	≤ 10 4 log(d) log	10 log(d)ρ * 3 δ	(ρ * + 1)2 ρ * +1
	≤ 8 • 10 4 log(d) log	10 log(d) δ	log 3 2	4d s * x 2 *	log 2	8d s * x 2 *	d s * x 2 *
	≤ c ′ log 2 (d) log(H) log	log(H) log(d) δ	H ,
	where c else
	Output: start.
	end if
	end if
	if start > end then
	Output: start.
	end if
	Let mid ← ⌊(start + end)/2⌋
	if compare(δ, 0, i, r[mid]) = i then
	Output: Binary-search(δ, i, r, mid + 1, end).
	else if compare(δ, 0, i, r[mid]) = r[mid] then
	Output: Binary-search(δ, i, r, start, mid -1).
	else
	Output: mid.
	end if

′ is a numerical constant and where we used that ∥x∥ 2 2 ≤ s * log(2d)x 2 s * .

C Full Ranking

C.1 Binary search algorithm

Algorithm 5 Binary-search(δ, i, r, a, b) Input: δ, r, i expert to be inserted, start, end (start/end of array r). if start = end then if compare(δ, 0, i, r[start]) = i then Output: start + 1. *

Acknowledgments: The work of A. Carpentier is partially supported by the Deutsche Forschungsgemeinschaft (DFG) Emmy Noether grant MuSyAD (CA 1488/1-1), by the DFG -314838170, GRK 2297 MathCoRe, by the FG DFG, by the DFG CRC 1294 'Data Assimilation', Project A03, by the Forschungsgruppe FOR 5381 "Mathematical Statistics in the Information Age -Statistical Efficiency and Computational Tractability", Project TP 02, by the Agence Nationale de la Recherche (ANR) and the DFG on the French-German PRCI ANR ASCAI CA 1488/4-1 "Aktive und Batch-Segmentierung, Clustering und Seriation: Grundlagen der

KI" and by the UFA-DFH through the French-German Doktorandenkolleg CDFA 01-18 and by the SFI Sachsen-Anhalt for the project RE-BCI. The work of E.M. Saad and N. Verzelen is supported by ANR-21-CE23-0035 (ASCAI).

C.2 Proof of Theorem 5.1

For i ∈ n -1 , define:

.

By convention, we define H 0 = 0. Binary insertion sort procedure makes at most n⌈log 2 (n)⌉ comparisons, hence using an union bound, we conclude that all calls to compare algorithm output a correct result with probability at least 1 -δ. Moreover, inserting any expert i costs at most ⌈log 2 (n)⌉ calls to compare. For any k ∈ n \ {i}, we apply Theorem 4.1. Hence, the total number of queries made by Binary-search(δ/(n⌈log

with probability at least 1 -δ/n. Here, c stands for a numerical constant. Summing for i ∈ n -1 gives the desired result.

D Best expert identification D.1 Max search algorithm

The max-search routine with precision ϵ is described in Algorithm 6 below.

Algorithm 6 Max-search(δ, S, ϵ)

Input: δ confidence parameter, S a set of experts, ϵ a precision parameter.

Output: Set C of experts. Let ℓ = |S| and a 1 , . . . , a ℓ be the elements of S.

D.2 Proof of Theorem 5.2

Let i * ∈ d denote the optimal expert. For ϵ ∈ (0, 1), define B ϵ ⊂ d as follows: Proof. Fix δ ∈ (0, 1) and ϵ ∈ (0, 1). To ease notation, we denote R 1 (a, b) (resp. R 2 (a, b)), the output of compare(δ, ϵ, a, b) for a ∈ S and b ∈ S in the first (resp. second) loop of Algorithm 6. Also, we we write m the element with which items are compared in the second loop of Algorithm 6.

Using Theorem 4.1, we have that, on an event of probability 1 -δ, all the results of R 1 (m, i) and R 2 (m, i) in Algorithm 6 are such that, for

Let us show that, under this event, we have i * ∈ C and C ⊆ B 2ϵ . Indeed, if i * / ∈ C, this implies that in the second loop we had R 2 ( m, i * ) = m, which is not possible by definition.

Besides, we easily check that m satisfies ∥M m -M i ∥ 2 ≤ ϵ. Since C only contains the elements j such that we have found R s ( m, j) ∈ {j, m} for s = 1 or s = 2, this implies that either j is above m or that ∥M m -M i ∥ 2 ≤ ϵ. By triangular inequality, we have proved that C ⊆ B 2ϵ . Lemma D.2. Consider Algorithm 6 with input (δ, S, ϵ) such that ϵ ≤ 1 and i * ∈ S. Denote N ϵ the total number of queries made. We have

where c is a numerical constant.

Proof. Observe that in Algorithm 6, there are at most 2|S| calls to the procedure compare with precision parameter ϵ. Using Theorem 4.1, we get the result.

Conclusion:

Fix δ ∈ (0, 1) and denote N the total number number of queries made by Algorithm 4.

Write r = 1, . . . , r for the iterations of Algorithm Algorithm 4 and write S r for the corresponding result of Max-search algorithm. We write S 0 = [n]. Applying Lemma D.1, we know that on event of probability higher than 1 -δ, we have, i ∈ S r and S r ⊆ B 2•4 -r+1 .

(

simultaneously for all r = 1, . . . , r.

We work henceforth under this event. First, this implies that S r = {i * }. Hence, the procedure recovers the best expert.