Max K-armed bandit: On the ExtremeHunter algorithm and beyond
Mastane Achab Stephan Clémençon Aurélien Garivier Anne Sabourin Claire Vernade
stat.ML cs.LG



















LTCI, Télécom ParisTech, Université Paris-Saclay IMT, Université de Toulouse

Max K-armed bandit: 
 On the ExtremeHunter algorithm and beyond
    Mastane Achab1 Stephan Clémençon1 Aurélien Garivier2 Anne Sabourin1 Claire Vernade1
    December 30, 2023
=======================================================================================




This paper is devoted to the study of the max K-armed bandit problem, which consists in sequentially allocating resources in order to detect extreme values. Our contribution is twofold.
We first significantly refine the analysis of the ExtremeHunter algorithm carried out in
<cit.>, and next propose an alternative approach, showing that, remarkably, Extreme Bandits can be reduced to a classical version of the bandit problem to a certain extent. Beyond the formal analysis, these two approaches are compared through numerical experiments.







§ INTRODUCTION


In a classical multi-armed bandit (MAB in abbreviated form) problem, the objective is to find a  strategy/policy in order to
sequentially explore and exploit K sources of gain, referred to as arms, so as to
maximize the expected cumulative gain.
Each arm k∈{1, …,  K  } is characterized by an unknown probability distribution ν_k.
At each round t≥ 1, a strategy π picks an arm I_t=π((I_1,
X_I_1,1),  …,  (I_t-1, X_I_t-1, t-1)) and receives a random reward
X_I_t, t
sampled from distribution ν_I_t.
Whereas usual strategies aim at finding and exploiting the arm with highest expectation, the quantity of interest in many applications such as medicine, insurance or finance may not be the sum of the rewards, but rather the extreme observations (even if it might mean replacing loss minimization by gain maximization in the formulation of the practical problem).
In such situations, classical bandit algorithms can be significantly sub-optimal: the "best" arm should not be defined as that with highest expectation, but as that
producing the maximal values. This setting, referred to as extreme bandits in <cit.>,
was originally introduced by <cit.> by the name of
max K-armed bandit problem.
In this framework, the goal pursued is to obtain the highest possible
reward during the first n≥ 1 steps. For a given arm k, we denote by

    G_n^(k)=max_1≤ t≤ nX_k, t

the maximal value taken until round n≥ 1 and assume that, in expectation,  there is a unique optimal arm

    k^∗= _1≤ k≤ K𝔼[G_n^(k)] .

The expected regret of a strategy π is here defined as

    𝔼[R_n]= 𝔼[G_n^(k^∗)] - 𝔼[G_n^(π)],

where G_n^(π)=max_1≤ t≤ nX_I_t, t is the maximal value
observed when implementing strategy π.
When the supports of the reward distributions (i.e. the ν_k's) are bounded, no-regret is expected provided that every arm can be sufficiently explored, refer to <cit.> (see
also <cit.> for a PAC approach). If infinitely many
arms are possibly involved in the learning strategy, the challenge is then to explore and exploit optimally the unknown reservoir
of arms, see <cit.>.
When the rewards are unbounded in contrast, the situation is quite
different: the best arm is that for which the maximum G_n^(k) tends to
infinity faster than the others.
In <cit.>, it is shown that, for unbounded distributions, no policy can achieve no-regret without restrictive assumptions on the distributions.
In accordance with the literature, we focus on a classical framework in
extreme value
analysis. Namely, we assume that the reward distributions are  heavy-tailed.
Such Pareto-like laws are widely used to model extremes in many applications, where a conservative approach to risk assessment might be relevant (e.g. finance, environmental risks).
Like in <cit.>, rewards are assumed to be distributed as second order Pareto laws in the present article. For the sake of completeness, we recall that
a probability law with cdf F(x) belongs to the
(α, β, C, C')-second order Pareto family if, for every x≥
0,

    |1-Cx^-α-F(x)|≤ C'x^-α(1+β)  ,

where α, β, C  and  C' are strictly positive constants, see e.g. <cit.>.
In this context, <cit.> have proposed the
ExtremeHunter algorithm to solve the extreme bandit problem and provided a regret analysis.

The contribution of this paper is twofold. First, the regret analysis of the ExtremeHunter
algorithm is significantly improved, in a nearly optimal fashion.
This essentially relies on a new technical result of independent interest
(see Theorem <ref> below), which provides a bound for the difference between the expectation of the maximum among independent realizations X_1, …,  X_T of a  (α, β, C, C')-second order Pareto distribution,
𝔼[max_1≤ i≤ T X_i] namely, and its rough
approximation (TC)^1/αΓ(1-1/α).
As a by-product, we propose a more simple Explore-Then-Commit strategy
that offers the same theoretical guarantees as  ExtremeHunter.
Second, we explain how extreme bandit can be reduced to a classical bandit problem to a certain extent. We show that a regret-minimizing strategy such as
Robust-UCB (see <cit.>), applied on correctly
left-censored rewards, may also reach a very good performance. This claim is
supported by theoretical guarantees on the number of pulls of the best arm
k^∗ and by numerical experiments both at the same time. From a practical angle, the main drawback of this alternative approach
consists in the fact that its implementation requires some knowledge of the complexity of the problem (i.e. of the gap between the first-order Pareto coefficients of the first
and second arms). In regard to its theoretical analysis, efficiency is proved for large horizons only.


This paper is organized as follows.
Section <ref> presents the technical result mentioned above, which next permits to carry out a refined regret analysis of the ExtremeHunter algorithm in <ref>.
In <ref>, the regret bound thus obtained is proved to be nearly optimal: precisely, we establish a lower bound under the assumption that the distributions are close
enough to Pareto distributions showing the regret bound is sharp in this situation. In <ref>, reduction of the extreme bandit problem to
a classical bandit problem is explained at length, and an algorithm resulting from this original view is then described. Finally, we provide a preliminary
numerical study that permits to compare the two approaches from an experimental perspective. Due to space limitations, certain technical proofs are deferred to the Supplementary Material.






§ SECOND-ORDER PARETO DISTRIBUTIONS: APPROXIMATION OF THE EXPECTED MAXIMUM AMONG I.I.D. REALIZATIONS

		 


In the extreme bandit problem, the key to controlling the behavior of
explore-exploit strategies is to approximate the expected payoff of a
fixed arm k∈{1, …,  K  }. The main result of this section, stated in Theorem <ref>, provides such control: it significantly improves upon the result originaly obtained by
<cit.> (see Theorem 1 therein). As shall be next shown in Section <ref>, this refinement has substantial consequences on the regret bound.


In <cit.>, the distance between the
expected maximum of independent realizations of a (α,β,
C,C')-second order Pareto and the corresponding expectation of a Fréchet
distribution (TC)^1/αΓ(1-1/α) is controlled as follows:

    |𝔼[max_1≤ i≤
    	TX_i]-(TC)^1/αΓ(1-1/α)|
    ≤4D_2C^1/α/T^1-1/α+2C'D_β+1/C^β+1-1/αT^β-1/α
    +(2C'T)^1/(1+β)α .

Notice that the leading term of this bound is (2C'T)^1/((1+β)α) as T→ +∞. Below, we state a sharper result where, remarkably, this (exploding) term disappears, the contribution of the related component in the approximation error decomposition being proved as (asymptotically) negligible in contrast.
(Fréchet approximation bound)
	
	If  X_1, …,  X_T are i.i.d. r.v.'s drawn from
	a (α, β, C, C')-second order Pareto distribution with α>1 and T≥ Q_1, where Q_1 is the constant depending only on α, β, C and C' given in <ref> below, then,
	
    |𝔼[max_1≤ i≤
    		TX_i]-(TC)^1/αΓ(1-1/α)|
       ≤4D_2C^1/α/T^1-1/α+2C'D_β+1/C^β+1-1/αT^β-1/α
    	+2(2C'T)^1/(1+β)αe^-HT^β/β+1
       = T→∞o (T^1/α),

	where H=C(2C')^1/(α(1+β))/2.
	In particular, if β≥ 1, we have:
	
    |𝔼[max_1≤ i≤
    		TX_i]-(TC)^1/αΓ(1-1/α)| = o(1)  as  T→ +∞.


	We emphasize that the bound above shows that the distance of
	𝔼[max_1≤ i≤	TX_i] to the Fréchet mean (TC)^1/αΓ(1-1/α) actually vanishes as T→∞ as soon as β≥ 1, a property that shall be useful in Section <ref> to study the behavior
	of learning algorithms in the extreme bandit setting.

	Assume that T≥ Q_1, where
	
    Q_1 = 1/2C'max{(2C'/C)^(1+β)/β,   (8C)^1+β}.

	As in the proof of Theorem 1 in <cit.>, we consider the quantity B=(2C'T)^1/((1+β)α) that serves as a
	cut-off between tail and bulk behaviors. Observe that
	
    | 𝔼[max_1≤ i≤ TX_i] -
    	(TC)^1/αΓ(1-1/α) |
    	≤
    | ∫_0^∞{ 1-ℙ(max_1≤ i≤
    	TX_i≤ x)-1+e^-TCx^-α}dx
    	| 
    ≤|∫_0^B{ℙ(max_1≤ i≤ TX_i≤ x)
    	-e^-TCx^-α}dx |
    
    	+ |∫_B^∞{ℙ(max_1≤ i≤ TX_i≤
    	x)-e^-TCx^-α}dx| .

	
	For p∈{2, β+1}, we set D_p=Γ(p-1/α)/α. Equipped with this notation, we may write
	
    |∫_B^∞{ℙ(max_1≤ i≤ TX_i≤
    	x)-e^-TCx^-α}dx|
    	≤4D_2C^1/α/T^1-1/α+2C'D_β+1/C^β+1-1/αT^β-1/α.

	Instead of loosely bounding the bulk term by B, we write
	
    |∫_0^B{ℙ(max_1≤ i≤ TX_i≤
    	x)-e^-TCx^-α}dx|
    	≤ B ℙ(X_1≤ B)^T +
    	∫_0^Be^-TCx^-αdx .

	First, using (<ref>) and the inequality
	C'B^-(1+β)α≤ CB^-α/2 (a direct consequence of <ref>), we obtain
	
    ℙ(X_1≤ B)^T
    	≤(1-CB^-α+C'B^-(1+β)α)^T
       ≤(1-1/2CB^-α)^T
    	≤ e^-1/2TCB^-α= e^-HT^β/(β+1).


	Second, the integral in <ref> can be bounded as follows:
	
    ∫_0^B e^-TCx^-αdx	≤ Be^-TCB^-α
    	 = (2C'T)^1/((1+β)α)e^-2HT^β/(β+1).

This concludes the proof.












§ THE EXTREMEHUNTER AND EXTREMEETC ALGORITHMS



In this section, the tighter control provided by Theorem <ref> is used in
order to refine the  analysis of the ExtremeHunter
algorithm (Algorithm <ref>) carried out in  <cit.>.
This theoretical analysis is also shown to be valid for ExtemeETC, a novel algorithm we next propose, that greatly improves upon ExtremeHunter, regarding computational efficiency.



 §.§ Further Notations and Preliminaries


Throughout the paper, the indicator function of any event ℰ is denoted by 1{ℰ} and ℰ̅ means the complementary event of ℰ.
We assume that the reward related to each arm k∈{1, …,  K  } is drawn from a (α_k, β_k, C_k, C')-second
order Pareto distribution.
Sorting the tail indices by increasing order of magnitude, we use the classical notation for order statistics:
α_(1)≤…≤α_(K).
We assume that α_(1)> 1, so that the random rewards have finite expectations, and suppose that the strict inequality α_(1)<α_(2) holds true.
We also denote by T_k,t the number of times the arm k is pulled up to time t.
For 1≤ k≤ K and i≥ 1, the r.v. X_k, i is the reward obtained
at the i-th draw of arm k
if i≤ T_k, n or a new r.v. drawn from ν_k independent from the other r.v.'s otherwise.



We start with a preliminary lemma supporting the intuition that
the tail index α fully governs the extreme bandit problem. It will
allow to show next that the algorithm picks the right arm after the exploration phase, see Lemma <ref>.
(Optimal arm)
	
	For n larger than some constant Q_4 depending only on
        (α_k, β_k, C_k)_1≤ k≤ K and C', the optimal arm
        for the extreme bandit problem is given by:
				
    k^∗ = _1≤ k≤ Kα_k
                = _1≤ k≤ K V_k,

				where V_k = (nC_k)^1/α_kΓ(1-1/α_k).



	We first prove the first equality.
  It follows from <ref> that there exists a constant Q_2,
  depending only on {(α_k, β_k, C_k)}_1≤ k≤ K and
  C', such that for any arm k∈{1, …,  K },
  |𝔼[G_n^(k)]-V_k |≤ V_k/2.  Then for k≠ k^∗ we
  have, for all n>Q_2,
  V_k/2 ≤𝔼[G_n^(k)]≤𝔼[G_n^(k^∗)]≤
  3V_k^∗/2.
	Recalling that V_k is proportional to n^1/α_k, it follows that
  α_k^∗=min_1≤ k≤ Kα_k.
	Now consider the following quantity:

    Q_3 = max_k≠ k^∗[2C_k^1/α_kΓ(1-1/α_k)/C_k^∗^1/α_k^∗Γ(1-1/α_k^∗)]^1/(1/α_k^∗-1/α_k) .

For n>Q_4=max(Q_2, Q_3), we have V_k^∗>2V_k for any suboptimal  arm k≠ k^∗,
which proves the second equality.





From now on, we assume that n is large enough for  <ref> to apply.









 

 §.§ The ExtremeHunter algorithm <cit.>

  Before developing a novel analysis of the extreme bandit problem in Section <ref> (see Theorem <ref>), we recall  the main
 features of ExtremeHunter, and in particular the estimators and
 confidence intervals involved in the indices of this optimistic
  policy.




<ref> states that for any arm k∈{1, …,  K  }, 𝔼[G_n^(k)]≈ (C_k
n)^1/α_kΓ(1-1/α_k). Consequently, the
optimal strategy in hindsight always pulls the arm
k^∗=_1≤ k≤ K{(nC_k)^1/α_kΓ(1-1/α_k)}.
At each round and for each arm k∈{1, …,  K  }, ExtremeHunter algorithm
<cit.> estimates the coefficients α_k and C_k (but not β_k, see Remark 2 in <cit.>). The
corresponding confidence intervals are detailed below. Then, following the optimism-in-the-face-of-uncertainty principle (see <cit.> and references therein), the strategy  plays the arm
maximizing an optimistic plug-in estimate of
(C_kn)^1/α_kΓ(1-1/α_k). To that purpose,
Theorem 3.8 in
<cit.> and Theorem 2 in
<cit.> provide estimators α_k(T) and
C_k(T) for α_k and C_k respectively, after T draws of arm k. Precisely, the estimate α_k(T) is given by

    α_k(T)=log( ∑_t=1^T1{X_t>e^r}/∑_t=1^T1{X_t>e^r+1})  ,

where r is chosen in an adaptive fashion based on Lepski's method, see <cit.>, while
the estimator of C_k considered is

    C_k(T)=T^-2b/(2b+1)∑_i=1^T 1{X_k,i≥
    T^h_k(T)/(2b+1)},

where

    h_k(T)=min(1/α_k(T), 1) .

The authors also provide  finite sample error bounds for T≥
N, where

    N= A_0(log n)^2(2b+1)/b,

with b a known lower bound on the β_k's (b≤ min_1≤ k≤ Kβ_k), and
A_0 a constant depending only on (α_k, β_k, C_k)_1≤ k≤
K and C'.
These error bounds naturally define confidence intervals  of respective widths Λ_1 and Λ_2
at level δ_0 defined by

    δ_0 = n^-ρ,  where  ρ=2α_k^∗/α_k^∗-1.

More precisely, we have

    ℙ(|1/α_k-h_k(T)| ≤Λ_1(T), |C_k-C_k(T)|≤Λ_2(T) ) ≥ 1-2δ_0,

where

    Λ_1(T)=D√(log(1/δ_0))T^-b/(2b+1) and Λ_2(T)=E√(log(T/δ_0))log(T)T^-b/(2b+1),




denoting by D and E some constants depending only on (α_k, β_k,
C_k)_1≤ k≤ K and C'.
When T_k, t≥ N, denote by h_k, t=h_k(T_k, t) and
C_k, t=C_k(T_k, t) the estimators based on the
T_k, t observations for simplicity.
ExtremeHunter's index B_k, t for arm k at time t, the optimistic
proxy for 𝔼[G_n^(k)], can be then written as

    B_k, t=Γ(1-h_k, t-Λ_1(T_k, t))
    ((C_k, t+Λ_2(T_k, t))n)^h_k, t+Λ_1(T_k,
    t)  ,

where Γ(x)=Γ(x) if x>0 and +∞ otherwise.


On computational complexity.
Notice that after the initialization phase, at each time t>KN, ExtremeHunter computes estimators h_I_t, t
and C_I_t, t, each having a time complexity linear with the number of samples T_I_t, t pulled from arm I_t up to time t.
Summing on the rounds reveals that ExtremeHunter's time complexity is quadratic with the time horizon n.



 §.§ ExtremeETC: a computationally appealing alternative

In order to reduce the restrictive time complexity discussed previously, we now propose the ExtremeETC algorithm, an Explore-Then-Commit version of ExtremeHunter,
which offers similar theoretical guarantees.




After the initialization phase, the winner arm, which has maximal index B_k, KN, is fixed
and is pulled in all remaining rounds. Then ExtremeETC's time complexity, due to the computation of h_k, KN and
C_k, KN only, is 𝒪(KN)=𝒪((log n)^2(2b+1)/b), which is considerably
faster than quadratic time achieved by ExtremeHunter. For clarity, Table <ref> summarizes time and memory complexities of both algorithms.



Due to the significant gain of computational time, we used the ExtremeETC algorithm in our simulation study (Section <ref>) rather than ExtremeHunter.


Controlling the number of suboptimal rounds.
We introduce a high probability event that corresponds to the favorable
situation where, at each round, all coefficients (1/α_k, C_k)_1≤ k ≤
K simultaneously belong to the confidence intervals recalled in the previous subsection.


	
	The event ξ_1 is the event on which the bounds
	
    |1/α_k-h_k(T)|≤Λ_1(T)    |C_k-C_k(T)|≤Λ_2(T)

hold true for any 1≤ k≤ K and N≤ T≤ n.


The union bound combined with (<ref>) yields

    ℙ(ξ_1)≥ 1-2Knδ_0.



	
	For n>Q_5, where Q_5 is the constant defined in (<ref>), ExtremeETC and ExtremeHunter
	always pull the optimal arm after the initialization phase on the event ξ_1.
	Hence, for any suboptimal arm k≠ k^∗, we have on ξ_1:
	
    T_k, n = N   and thus   T_k^∗, n = n - (K-1)N.




	Here we place ourselves on the event ξ_1.
	For any arm 1≤ k≤ K, Lemma 1 in <cit.> provides lower
	and upper bounds for B_k, t when T_k, t≥ N
	
    V_k
    	≤ B_k, t≤ V_k 
    
     (1+Flog n √(log(n/δ_0))T_k, t^-b/(2b+1))  ,

	where F is a constant which depends only on (α_k, β_k,
	C_k)_1≤ k≤ K and C'.
 Introduce the horizon Q_5, which depends on (α_k, β_k,
 C_k)_1≤ k≤ K and C'

    Q_5 = max(e^(F√(1+ρ)A_0^-b/(2b+1))^2, Q_4).

Then the following <ref>, proved in <ref>, tells us that for n large enough, the exploration made during the initialization phase is enough to find the optimal arm, with high probability.

  
If n>Q_5, we have under the event ξ_1 that for any suboptimal arm k≠ k^∗ and any time t>KN
that B_k, t<B_k^∗, t .

	Hence the
	optimal arm is pulled at any time t> KN.


The following result immediately follows from <ref>.


	
	For n larger than some constant depending only on (α_k, β_k, C_k)_1≤ k≤ K and C' we have under ξ_1
	
    T_k^∗, n≥ n/2.



Upper bounding the expected extreme regret.
The upper bound on the expected
extreme regret stated in the theorem below improves upon that given in <cit.> for ExtremeHunter. It is also valid for ExtremeETC.


	
	For ExtremeETC and ExtremeHunter, the expected
	extreme regret is upper bounded as follows
	
    𝔼[R_n]
    	= 𝒪((log n)^2(2b+1)/bn^-(1-1/α_k^∗)+n^-(b-1/α_k^∗)),

as n→ +∞. If b≥ 1, we have in particular	𝔼[R_n]= o(1) as n→ +∞.


The proof  of <ref> is deferred to  <ref>.  It closely follows that of Theorem 2 in <cit.>, the main difference being that their concentration bound (Theorem 1 therein) can be replaced by our tighter bound (see Theorem <ref> in the present paper).
Recall that in Theorem 2 in <cit.>, the upper bound on the expected
extreme regret for ExtremeHunter goes to infinity when n→ +∞:

    𝔼[R_n]= 𝒪(n^1/(1+b)α_k^∗).


In contrast, in <ref> when b≥ 1, the upper bound obtained vanishes  when n→ +∞.
In the case b<1, the upper bound still improves upon <ref> by a factor
n^(α_k^∗ b(b+1)-b)/((b+1)α_k^∗)>n^b^2/(2α_k^∗).














§ LOWER BOUND ON THE EXPECTED EXTREME REGRET



In this section we prove a lower bound on the expected extreme regret for
ExtremeETC and ExtremeHunter in specific cases.
We assume now that α_(2)>2α_k^∗^2/(α_k^∗-1) and we start with a
 preliminary result on second order Pareto distributions, proved in <ref>.


	
	If X is a r.v. drawn from a (α, β, C, C')-second
	order Pareto distribution and r is a strictly positive constant,
	the distribution of the r.v. X^r is a (α/r, β, C, C')-second order Pareto.



In order to prove the lower bound on the expected extreme regret, we first establish that the event corresponding to the situation where the highest reward obtained by ExtremeETC and ExtremeHunter comes from
the optimal arm k^∗ occurs with overwhelming probability. Precisely,
we denote by ξ_2 the event such that the bound

    max_k≠ k^∗max_1≤ i≤ NX_k,i≤max_1≤ i≤
    n-(K-1)NX_k^∗,i.

holds true. The following lemma, proved in <ref>, provides a control of its probability of occurence.

	
	For n larger than some constant depending only on (α_k, β_k, C_k)_1≤ k≤ K and C', the following assertions hold true.
	
		
  * We have:
		
    ℙ(ξ_2)≥ 1-Kδ_0,

              where δ_0 is given in <ref>.
		
  * Under the event ξ_0=ξ_1∩ξ_2, the maximum reward obtained by
		ExtremeETC and ExtremeHunter comes from the optimal arm:
		
    max_1≤ t≤ nX_I_t, t = max_1≤ i≤
    		n-(K-1)NX_k^∗, i .

	







The following  lower bound shows that the upper bound  (<ref>)  is actually tight in
the case b≥ 1.

	
	If b≥ 1 and α_(2)>2α_k^∗^2/(α_k^∗-1),
	the expected extreme regret of ExtremeETC and ExtremeHunter are lower bounded as
	follows
	
    𝔼[R_n] = Ω((log
    	n)^2(2b+1)/bn^-(1-1/α_k^∗)) .




  Here, π refers to either ExtremeETC or else ExtremeHunter. In order to bound from  below
  𝔼[R_n]=𝔼[G_n^(k^∗)]-𝔼[G_n^(π)], we start with bounding 𝔼[G_n^(π)] as follows

	
    𝔼[G_n^(π)]
    	   = 𝔼[max_1≤ t≤ nX_I_t, t]
    	= 𝔼[max_1≤ t≤ nX_I_t,
    	t1{ξ_0}]+𝔼[max_1≤ t≤ nX_I_t,
    	t1{ξ̅_0 }]
       ≤ℙ(ξ_0)𝔼[max_1≤ t≤ nX_I_t, t |ξ_0]
    	+∑_k=1^K𝔼[max_1≤ i≤ T_k, nX_k,
    	i1{ξ̅_0 }]  ,

	where  X_k, i has been  defined in <ref>.
	From (ii) in <ref>, we have
	
    𝔼[max_1≤ t≤ nX_I_t, t | ξ_0]
    	= 𝔼[max_1≤ i≤ n-(K-1)NX_k^∗, i |ξ_0] .

	In addition, in the sum of expectations
        on the right-hand-side of <ref>, 
        
        T_k,n may be roughly bounded from above
        by n. A straightforward application of  Hölder inequality yields
	
    ∑_k=1^K𝔼[max_1≤ i≤ T_k, nX_k,
    	i1{ξ̅_0 }]
    	≤∑_k=1^K(𝔼[max_1≤ i≤ nX_k,
    	i^α_k^∗+1/2])^2/α_k^∗+1ℙ(ξ̅_0 )^α_k^∗-1/α_k^∗+1 .


	From (i) in <ref> and <ref>, we have
	ℙ(ξ̅_0 )≤ K(2n+1)δ_0.
	By virtue of <ref>, the r.v. X_k, i^(α_k^∗+1)/2 follows a
	(2α_k/(α_k^∗+1), β_k, C_k, C')-second order Pareto
	distribution.
	Then, applying <ref> to the right-hand side of (<ref>) and
	using the identity (<ref>), the upper bound (<ref>) becomes

	
    𝔼[G_n^(π)]
    	≤𝔼[max_1≤ i≤ n-(K-1)NX_k^∗, i1{ξ_0}]
       + ∑_k=1^K((n C_k)^α_k^∗+1/2α_kΓ(1-α_k^∗+1/2α_k)
    	+o(n^α_k^∗+1/2α_k))^2/α_k^∗+1(K(2n+1)δ_0)^α_k^∗-1/α_k^∗+1
       ≤𝔼[max_1≤ i≤ n-(K-1)NX_k^∗, i] +
    	𝒪(n^-(1-1/α_k^∗)),

	where the last inequality comes from the definition of δ_0.
	Combining <ref> and  (<ref>) we finally obtain the desired lower bound 
	
	
    𝔼[R_n]
    	= 𝔼[G_n^(k^∗)]-𝔼[G_n^(π)]
       ≥Γ(1-1/α_k^∗)C_k^∗^1/α_k^∗(n^1/α_k^∗-(n-(K-1)N)^1/α_k^∗)
    	+𝒪(n^-(1-1/α_k^∗))
       = Γ(1-1/α_k^∗)C_k^∗^1/α_k^∗/α_k^∗(K-1)Nn^-(1-1/α_k^∗)
    	+𝒪(n^-(1-1/α_k^∗)),

  where we used a Taylor expansion of x↦ (1+x)^1/α_k^∗ at zero for the last equality.










§ A REDUCTION TO CLASSICAL BANDITS



The goal of this section is to render explicit the connections between the max K-armed bandit considered in the present paper and a particular instance of the classical Multi-Armed Bandit (MAB) problem.



 §.§ MAB setting for extreme rewards



In a situation where only the large rewards matter, an alternative to
the max k-armed problem would be to consider the expected cumulative
sum of the most `extreme' rewards, that is, those which exceeds a
given high threshold
u. 
For k∈{1, …,  K  } and t∈{1, …,  n  }, we denote by Y_k, t these new rewards

    Y_k, t=X_k, t1{X_k, t>u} .

In this context, the classical MAB problem  consists in maximizing the expected cumulative gain

    𝔼[G^MAB] = 𝔼[ ∑_t=1^n Y_I_t,t].


It turns out that for a high enough threshold u,   the unique optimal arm
for this MAB problem, _1≤ k≤ K𝔼[Y_k, 1], is also the
optimal arm k^∗ for the max k-armed  problem.
We still assume second order Pareto distributions for the random variables
X_k, t and that all the hypothesis listed in Section <ref> hold true. 

The rewards {Y_k, t}_1≤ k≤ K, 1≤ t≤ T are also heavy-tailed so that it is legitimate to 

attack this MAB problem with the  Robust UCB algorithm
<cit.>,
which assumes that the rewards have finite moments of order 1+ϵ

    max_1≤ k≤ K𝔼[|Y_k, 1|^1+ϵ]≤ v  ,

where ϵ∈(0, 1] and v>0 are known constants. Given our second order
Pareto assumptions, it follows that <ref> holds with
1+ϵ<α_(1).
Even if the knowledge of  such constants ϵ and v is a strong assumption, it is
still fair to compare Robust UCB to ExtremeETC/Hunter, which also
has strong requirements.
Indeed, ExtremeETC/Hunter assumes that b and n
are known and verify conditions depending on unknown problem parameters (e.g. n≥ Q_1, see <ref>).

The following Lemma, whose the proof is postponed to <ref>, ensures that the two bandit problems are equivalent for high thresholds.


	
	
    If   u>max(1, (2C'/min_1≤ k≤ KC_k)^1/min_1≤ k≤ Kβ_k,
    	(3max_1≤ k≤ KC_k/min_1≤ k≤ KC_k)^1/α_(2)-α_(1)) 
    	 ,

	then the unique best arm for the MAB problem is _1≤ k≤
	Kα_k=k^∗.



	
	Tuning the threshold u based on the data is a difficult question, outside our scope.
	A standard practice is to monitor a relevant output (e.g. estimate of α) as a function of the threshold u and to pick the latter as low as possible in the stability region of the output.
	This is related to the Lepski's method, see e.g. <cit.>, <cit.>, <cit.>.








 §.§ Robust UCB algorithm <cit.>


For the sake of completeness, we recall below the main feature of Robust UCB  and make explicit its theoretical guarantees in our setting. The  bound stated  in the following proposition is a direct consequence of the regret analysis conducted by <cit.>.

	
	Applying the Robust UCB algorithm of <cit.>
	
	to our MAB problem, the expected number of
	times we pull any suboptimal arm k≠ k^∗ is upper bounded as follows
	
    𝔼[T_k, n] = 𝒪(log n) .

	
	
	
	
	



	See proof of Proposition 1 in <cit.>.



Hence, in expectation, Robust UCB pulls fewer times suboptimal arms than ExtremeETC/Hunter.
Indeed with ExtremeETC/Hunter, T_k, n≥
N=Θ((log n)^2(2b+1)/b).


	
<ref> may be an indication that the Robust UCB approach performs better than ExtremeETC/Hunter. Nevertheless, guarantees on its expected extreme regret
require sharp concentration bounds on T_k, n (k≠ k^∗), which is out of the scope of this paper and left for future work.












§ NUMERICAL EXPERIMENTS



In order to illustrate some aspects of the theoretical results presented previously,
	we consider a time horizon n=10^5 with K=3 arms and exact Pareto distributions with parameters given in <ref>.
	Here, the optimal arm is the second one (incidentally, the distribution with highest mean is the first one).





We have implemented Robust UCB with parameters ϵ=0.4, which satisfies 1+ϵ<α_2=1.5, v achieving the equality in <ref> (ideal case) and a threshold u equal to the lower bound in <ref> plus 1 to respect the strict inequality.
ExtremeETC is runned with b=1<+∞=min_1≤ k≤ Kβ_k.
In this setting, the most restrictive condition on the time horizon, n > KN ≈ 7000 (given by <ref>), is checked, which places us in the validity framework of ExtremeETC.
The resulting strategies are compared to each other and to the random strategy pulling each arm uniformly at random, but not to Threshold Ascent algorithm <cit.> which is designed only for bounded rewards.
Precisely, 1000 simulations have been run and Figure <ref> depicts the extreme regret (<ref>) in each setting averaged over these 1000 trajectories.
These experiments empirically support the theoretical bounds in <ref>: the expected extreme regret of ExtremeETC converges to zero for large horizons.




On the log-log scale (<ref>), ExtremeETC's extreme regret starts linearly decreasing after the initialization phase, at n > KN≈ 7000,
which is consistent with <ref>.
The corresponding linear regression reveals a slope ≈ -0.333 (with a coefficient of determination R^2≈ 0.97),
which confirms <ref> and <ref> yielding the theoretical slope -(1-1/α_k^∗)=-1/3.










§ CONCLUSION


This paper brings two main contributions. It first provides
a refined regret bound analysis of the performance of the ExtremeHunter algorithm in the context of the max K-armed
bandit problem that significantly improves upon the results obtained in the seminal
contribution <cit.>, also proved to be valid for ExtremeETC, a computationally appealing alternative we introduce.
In particular, the obtained upper
bound on the regret converges to zero for large horizons and is shown
to be tight when the tail of the rewards is sufficiently close to a
Pareto tail (second order parameter b≥ 1).  On the other hand, this paper
offers a novel view of this approach, interpreted here as a specific
version of a classical solution (Robust UCB) of the MAB
problem, in the situation when only very large rewards matter.

Based on these encouraging results, several lines of further research
can be sketched. In particular, future work will investigate to which
extent the lower bound established for ExtremeETC/Hunter
holds true for any strategy with exploration
stage of the same duration, and whether  improved  performance is
achievable with alternative stopping
criteria for the exploration stage.



§ ACKNOWLEDGMENTS

This work was supported by a public grant (Investissement d'avenir project, reference ANR-11-LABX-0056-LMH,
LabEx LMH) and by the industrial chair Machine Learning for Big Data from Télécom ParisTech.

apalike









§ APPENDIX





 §.§ Proof of <ref>



  For n>Q_3 (defined in <ref>),
  one has V_k^∗>2max_k≠ k^∗V_k, which implies that max_k≠ k^∗V_k/(V_k^∗-V_k) < 1.
  Hence
  
    max_k≠ k^∗e^(F√(1+ρ)A_0^-b/(2b+1)V_k/V_k^∗-V_k)^2<e^(F√(1+ρ)A_0^-b/(2b+1))^2≤ Q_5 .

  Then, as T_k, t≥ N and by definitions of N (<ref>) and δ_0 (<ref>), we have for n>Q_5
  that for any suboptimal arm k≠ k^∗
  
    (C_k n)^1/α_kΓ(1-1/α_k)
        (1+Flog n √(log(n/δ_0))T_k, t^-b/(2b+1))
       <(C_ k^∗ n)^1/α_k^∗Γ(1-1/α_k^∗)  ,

which implies, using <ref>, that under ξ_1: B_k, t<B_k^∗, t for t>KN.




 §.§ Proof of <ref>



	We want to upper bound
	𝔼[R_n]=𝔼[G_n^(k^∗)]-𝔼[G_n^(π)].
	To do so, we lower bound 𝔼[G_n^(π)] as follows
	
    𝔼[G_n^(π)]
    		=𝔼[max_t≤ nX_I_t, t]
    		≥𝔼[max_{t≤ n, I_t=k^∗}X_I_t, t]=𝔼[max_{i≤ T_k^∗, n}X_k^∗, i].

	Thus
	
    𝔼[G_n^(π)]
    		≥𝔼[max_i≤ n-(K-1)NX_k^∗, i1{ξ_1}]  ,

	where we used that under ξ_1, T_k^∗, n=n-(K-1)N.
	Now we call the following result (<ref>, proved in <ref>), giving a lower bound on the expected maximum of i.i.d. second order Pareto r.v. given some event.

	
	
	Let X_1, ..., X_T be i.i.d. samples from an (α, β, C, C')-second
	order Pareto distribution.
	Let ξ be an event of probability larger than 1-δ.
	If δ<1/2 and T≥max(4c, (4c)^1/βlog(2)C(2C')^1/β, 8log^2(2)) for a given constant c depending
	only on β, C and C', we have
	
    𝔼[max_1≤ i≤ TX_i1{ξ}]
    	≥ (TC)^1/αΓ(1-1/α)
    	-(4+8/α-1)(TC)^1/αδ'^1-1/α
       -2(4D_2C^1/α/T^1-1/α+2C'D_β+1/C^β+1-1/αT^β-1/α
    	+2(2C'T)^1/(α(1+β))e^-HT^β/(β+1)).

	

	Then, applying <ref> with ξ=ξ_1 and δ=δ_0 we obtain after simplification
	
    𝔼[R_n]
    		≤ H'n^1/α_k^∗{   1/n+1/n^b+K/n(log n)^2(2b+1)/b
    		+δ_0^1-1/α_k^∗
       +n^1/(α_k^∗(1+β_k^∗))e^-H_k^∗(n/2)^β/(β+1)}  ,

	where H_k^∗=1/2C_k^∗(2C')^1/(α_k^∗(1+β_k^∗)) and
	H' is a constant depending only on (α_k, β_k, C_k)_1≤ k≤
	K and C'.
	The definition of δ_0 concludes the proof.





 §.§ Proof of <ref>





We follow the proof of Lemma 2 in <cit.> except that we use
<ref> instead of their Theorem 1.
Let x_δ be such that ℙ(max_1≤ t≤ TX_t≤
x_δ)=1-δ.
Then we have

    𝔼[max_1≤ t≤ TX_t1{ξ}]
    = 𝔼[max_1≤ t≤ TX_t]-𝔼[max_1≤ t≤
    TX_t1{ξ̅}]
        = 𝔼[max_1≤ t≤ TX_t] -
    ∫_0^x_δℙ(max_1≤ t≤
    TX_t1{ξ̅}>x)   dx
                       - ∫_x_δ^∞ℙ(max_1≤ t≤
    TX_t1{ξ̅}>x)   dx
       ≥𝔼[max_1≤ t≤ TX_t] - δ x_δ
    - ∫_x_δ^∞ℙ(max_1≤ t≤
    TX_t1{ξ̅}>x)   dx  ,

where the inequality comes from ℙ(max_1≤ t≤ TX_t1{ξ̅}>x)≤ℙ(ξ̅)≤δ.
Since T≥log(2)max(C(2C')^1/β, 8log(2)) and δ<1/2, we have
from Lemma 3 in <cit.>

    |ℙ(max_1≤ i≤ TX_i ≤ (TC/log(1/(1-δ)))^1/α)-(1-δ)|
       ≤ (1-δ)(4/T(log1/1-δ)^2
    +2C'/C^1+β(log1/1-δ)^1+β)
       ≤4/T(2δ)^2+2C'/C^1+β(2δ)^1+β≤ cδmax(δ/T, δ^β/T^β)
    ≤ cδmax(1/T, 1/T^β)  ,

where c is a constant that depends only on C, C' and β.
As we have cmax(T^-1, T^-β)≤ 1/4, this implies

    x_-=(TC/log(1/(1-2δ)))^1/α≤ x_δ≤ (TC/log(1/(1-δ/2)))^1/α= x_+ .

It follows

    𝔼[max_1≤ t≤ TX_t1{ξ}]
    ≥𝔼[max_1≤ t≤ TX_t] - δ x_+ -
    ∫_x_-^∞ℙ(max_1≤ t≤ TX_t>x)   dx .

From <ref> we deduce

    𝔼[max_1≤ t≤ TX_t1{ξ}]
    ≥𝔼[max_1≤ t≤ TX_t] - δ x_+
    - ∫_x_-^∞ (1-e^-TCx^-α)   dx
       -(4D_2C^1/α/T^1-1/α+2C'D_β+1/C^β+1-1/αT^β-1/α
    +2(2C'T)^1/(α(1+β))e^-HT^β/(β+1)).

From the proof of Lemma 2 in <cit.> we have for δ small
enough

    ∫_x_-^∞ (1-e^-TCx^-α)   dx
    ≤8/α-1(TC)^1/αδ^1-1/α

and

    δ x_+≤ 4(TC)^1/αδ^1-1/α .

<ref> concludes the proof.







 §.§ Proof of <ref>




	Let F and F_r be respectively the cumulative distribution functions of
	X and X^r. For x≥ 0,
	
    F_r(x)=ℙ(X^r≤ x) = ℙ(X≤ x^1/r) = F(x^1/r) .

	As X follows an (α, β, C, C')-second order Pareto distribution
	we have
	
    |1-Cx^-α/r-F_r(x)|
    	=|1-Cx^-α/r-F(x^1/r)|
    	≤ C'x^-(α/r)(1+β)  ,

	which concludes the proof.





 §.§ Proof of <ref>



	We first state the following result (<ref>, proved in <ref>), yielding high probability lower and upper bounds for the maximum of i.i.d. second order Pareto r.v.

	
		
		For X_1, ..., X_T i.i.d samples drawn from an
		(α,β,C,C')-second-order Pareto distribution we define high
		probability lower and upper bound
		
    ℓ(T,δ)= (TC/2log1/δ)^1/α  and   L(T,δ)= (4TC/log1/1-δ)^1/α  ,

		where δ∈(0,1) can depend on T and is such that
		lim_T→∞ℓ(T,δ)=∞ and
		lim_T→∞L(T,δ)=∞.
		For T large enough such that Cℓ(T,δ)^-α≥
		2C'ℓ(T,δ)^-α(1+β), CL(T,δ)^-α≥
		C'L(T,δ)^-α(1+β) and L(T,δ)^-α≤1/4C
		we have
		
    ℙ(max_1≤ i≤ TX_i≤ℓ(T,δ))≤δ  and  ℙ(max_1≤ i≤ TX_i≥ L(T,δ))≤δ.

	

	With the notations of <ref>, we respectively denote by ℓ_k and L_k the high probability lower and upper bounds for any arm k.
	Using <ref> we have by a union bound that
	with probability higher than 1-Kδ_0
	
    max_1≤ i≤ n-(K-1)NX_k^∗,i≥ℓ_k^∗(n-(K-1)N,δ_0)  ,

	and for any suboptimal arm k≠ k^∗
	
    max_1≤ i≤ NX_k,i≤ L_k(N, δ_0) .

	Under this event, using the definition of the confidence level δ_0 we observe for n larger than some constant that
	for any suboptimal arm k≠ k^∗, L_k(N,δ_0)≤ℓ_k^∗(n-(K-1)N,δ_0), which concludes the proof.




 §.§ Proof of <ref>





For the high probability lower bound we write:

    ℙ(max_1≤ i≤ TX_i≤ℓ(T,δ))
    =ℙ(X_1≤ℓ(T,δ))^T
       ≤(1-Cℓ(T,δ)^-α+C'ℓ(T,δ)^-α(1+β))^T
       ≤(1-1/2TCℓ(T,δ)^-α)^T
    ≤ e^-1/2TCℓ(T,δ)^-α
    =δ.

And for the high probability upper bound:

    ℙ(max_1≤ i≤ TX_i≤ L(T,δ))
    =ℙ(X_1≤ L(T,δ))^T
       ≥(1-CL(T,δ)^-α-C'L(T,δ)^-α(1+β))^T
       ≥ (1-2CL(T,δ)^-α)^T
    ≥ e^-4TCL(T,δ)^-α
    =1-δ .




  

 §.§ Proof of <ref>


	From <ref>, we have for any arm k∈{1, …,  K  },
	
    𝔼[X_k, 11{X_k, 1>u}]
    	   ≤∫^∞_0 ℙ(X_k, 11{X_k, 1>u}≥ x)  dx
       = u(1-F_k(u)) + ∫^∞_u (1-F_k(x))  dx
    	≤ M_k + Δ_k  ,

	where M_k=(C_kα_k/(α_k-1))u^-α_k + 1 and
	Δ_k=(C'α_k(1+β_k)/(α_k(1+β_k)-1))u^-α_k(1+β_k)+1.
	Similarly, we have 𝔼[X_k, 11{X_k,
	1>u}] ≥ M_k-Δ_k.

	For u large enough, we want to prove that
	M_k^∗-Δ_k^∗>M_k+Δ_k for any arm k≠ k^∗, which would
	prove that _1≤ k≤ K𝔼[Y_k, 1]=k^∗.
	First, we observe for u>max(1, (2C'/min_1≤ k≤ KC_k)^1/min_1≤ k≤ Kβ_k)
	that Δ_k < 1/2M_k.
	Then, for
	u>(3max_1≤ k≤ KC_k/min_1≤ k≤ KC_k)^1/(α_(2)-α_(1)), we have that
	1/2M_k^∗>3/2M_k for any arm k≠ k^∗, which concludes the proof.




