arXiv:2604.24545v1 [stat.ML] 27 Apr 2026
Extreme bandits Alexandra Carpentier Statistical Laboratory, CMS University of Cambridge, UK
Michal Valko SequeL team INRIA Lille - Nord Europe, France
Abstract In many areas of medicine, security, and life sciences, we want to allocate limited resources to different sources in order to detect extreme values. In this paper, we study an efficient way to allocate these resources sequentially under limited feedback. While sequential design of experiments is well studied in bandit theory, the most commonly optimized property is the regret with respect to the maximum mean reward. However, in other problems such as network intrusion detection, we are interested in detecting the most extreme value output by the sources. Therefore, in our work we study extreme regret which measures the efficiency of an algorithm compared to the oracle policy selecting the source with the heaviest tail. We propose the E XTREME H UNTER algorithm, provide its analysis, and evaluate it empirically on synthetic and real-world experiments.
1
Introduction
We consider problems where the goal is to detect outstanding events or extreme values in domains such as outlier detection [1], security [18], or medicine [17]. The detection of extreme values is important in many life sciences, such as epidemiology, astronomy, or hydrology, where, for example, we may want to know the peak water flow. We are also motivated by network intrusion detection where the objective is to find the network node that was compromised, e.g., by seeking the one creating the most number of outgoing connections at once. The search for extreme events is typically studied in the field of anomaly detection, where one seeks to find examples that are far away from the majority, according to some problem-specific distance (cf. the surveys [8, 16]). In anomaly detection research, the concept of anomaly is ambiguous and several definitions exist [16]: point anomalies, structural anomalies, contextual anomalies, etc. These definitions are often followed by heuristic approaches that are seldom analyzed theoretically. Nonetheless, there exist some theoretical characterizations of anomaly detection. For instance, Steinwart et al. [19] consider the level sets of the distribution underlying the data, and rare events corresponding to rare level sets are then identified as anomalies. A very challenging characteristic of many problems in anomaly detection is that the data emitted by the sources tend to be heavy-tailed (e.g., network traffic [2]) and anomalies come from the sources with the heaviest distribution tails. In this case, rare level sets of [19] correspond to distributions’ tails and anomalies to extreme values. Therefore, we focus on the kind of anomalies that are characterized by their outburst of events or extreme values, as in the setting of [22] and [17]. Since in many cases, the collection of the data samples emitted by the sources is costly, it is important to design adaptive-learning strategies that spend more time sampling sources that have a higher risk of being abnormal. The main objective of our work is the active allocation of the sampling resources for anomaly detection, in the setting where anomalies are defined as extreme values. Specifically, we consider a variation of the common setting of minimal feedback also known as the bandit setting [14]: the learner searches for the most extreme value that the sources output by probing the sources sequentially. In this setting, it must carefully decide which sources to observe 1
because it only receives the observation from the source it chooses to observe. As a consequence, it needs to allocate the sampling time efficiently and should not waste it on sources that do not have an abnormal character. We call this specific setting extreme bandits, but it is also known as max-k problem [9, 21, 20]. We emphasize that extreme bandits are poles apart from classical bandits, where the objective is to maximize the sum of observations [3]. An effective algorithm for the classical bandit setting should focus on the source with the highest mean, while an effective algorithm for the extreme bandit problem should focus on the source with the heaviest tail. It is often the case that a heavy-tailed source has a small mean, which implies that the classical bandit algorithms perform poorly for the extreme bandit problem. The challenging part of our work dwells in the active sampling strategy to detect the heaviest tail under the limited bandit feedback. We proffer E XTREME H UNTER, a theoretically founded algorithm, that sequentially allocates the resources in an efficient way, for which we prove performance guarantees. Our algorithm is efficient under a mild semi-parametric assumption common in extreme value theory, while known results by [9, 21, 20] for the extreme bandit problem only hold in a parametric setting (see Section 4 for a detailed comparison).
2
Learning model for extreme bandits
In this section, we formalize the active (bandit) setting and characterize the measure of performance for any algorithm π. The learning setting is defined as follows. Every time step, each of the K arms (sources) emits a sample Xk,t ∼ Pk , unknown to the learner. The precise characteristics of Pk are defined in Section 3. The learner π then chooses some arm It and then receives only the sample XIt ,t . The performance of π is evaluated by the most extreme value found and compared to the most extreme value possible. We define the reward of a learner π as: Gπn = max XIt ,t t≤n
The optimal oracle strategy is the one that chooses at each time the arm with the highest potential revealing the highest value, i.e., the arm ∗ with the heaviest tail. Its expected reward is then: E [G∗n ] = max E max Xk,t k≤K
t≤n
The goal of learner π is to get as close as possible to the optimal oracle strategy. In other words, the aim of π is to minimize the expected extreme regret: Definition 1. The extreme regret in the bandit setting is defined as: E [Rnπ ] = E [G∗n ] − E [Gπn ] = max E max Xk,t − E max XIt ,t k≤K
3
t≤n
t≤n
Heavy-tailed distributions
In this section, we formally define our observation model. Let X1 , . . . , Xn be n i.i.d. observations from a distribution P . The behavior of the statistic maxi≤n Xi is studied by extreme value theory. One of the main results is the Fisher-Tippett-Gnedenko theorem [11, 12] that characterizes the limiting distribution of this maximum as n converges to infinity. Specifically, it proves that a rescaled version of this maximum converges to one of the three possible distributions: Gumbel, Fréchet, or Weibull. This rescaling factor depends on n. To be concise, we write “maxi≤n Xi converges to a distribution” to refer to the convergence of the rescaled version to a given distribution. The Gumbel distribution corresponds to the limiting distribution of the maximum of ‘not too heavy tailed’ distributions, such as sub-Gaussian or sub-exponential distributions. The Weibull distribution coincides with the behaviour of the maximum of some specific bounded random variables. Finally, the Fréchet distribution corresponds to the limiting distribution of the maximum of heavy-tailed random variables. As many interesting problems concern heavy-tailed distributions, we focus on Fréchet distributions in this work. The distribution function of a Fréchet random variable is defined for x ≥ m, and for two parameters α, s as: α x−m P (x) = exp − . s 2
In this work, we consider positive distributions P : [0, ∞) → [0, 1]. For α > 0, the FisherTippett-Gnedenko theorem also states that the statement ‘P converges to an α-Fréchet distribution’ is equivalent to the statement ‘1 − P is a −α regularly varying function in the tail’. These statements are slightly less restrictive than the definition of approximately α-Pareto distributions1 , i.e., that there exists C such that P verifies: |1 − P (x) − Cx−α | = 0, x→∞ x−α lim
(1)
or equivalently that P (x) = 1 − Cx−α + o(x−α ). If and only if 1 − P is −α regularly varying in the tail, then the limiting distribution of maxi Xi is an α-Fréchet distribution. The assumption of −α regularly varying in the tail is thus the weakest possible assumption that ensures that the (properly rescaled) maximum of samples emitted by a heavy tailed distributions has a limit. Therefore, the very related assumption of approximate Pareto is almost minimal, but it is (provably) still not restrictive enough to ensure a convergence rate. For this reason, it is natural to introduce an assumption that is slightly stronger than (1). In particular, we assume, as it is common in the extreme value literature, a second order Pareto condition also known as the Hall condition [13]. Definition 2. A distribution P is (α, β, C, C ′ )-second order Pareto (α, β, C, C ′ > 0) if for x ≥ 0: 1 − P (x) − Cx−α ≤ C ′ x−α(1+β) . By this definition, P (x) = 1 − Cx−α + O x−α(1+β) , which is stronger than the assumption P (x) = 1 − Cx−α + o(x−α ), but similar for small β. Remark 1. In the definition above, β defines the rate of the convergence (when x diverges to infinity) of the tail of P to the tail of a Pareto distribution 1 − Cx−α . The parameter α characterizes the heaviness of the tail: The smaller the α, the heavier the tail. In the remainder of the paper, we will be therefore concerned with learning the α and identifying the smallest one among the sources.
4
Related work
There is a vast body of research in offline anomaly detection which looks for examples that deviate from the rest of the data, or that are not expected from some underlying model. A comprehensive review of many anomaly detection approaches can be found in [16] or [8]. There has been also some work in active learning for anomaly detection [1], which uses a reduction to classification. In online anomaly detection, most of the research focuses on studying the setting where a set of variables is monitored. A typical example is the monitoring of cold relief medications, where we are interested in detecting an outbreak [17]. Similarly to our focus, these approaches do not look for outliers in a broad sense but rather for the unusual burst of events [22]. In the extreme values settings above, it is often assumed, that we have full information about each variable. This is in contrast to the limited feedback or a bandit setting that we study in our work. There has been recently some interest in bandit algorithms for heavy-tailed distributions [4]. However the goal of [4] is radically different from ours as they maximize the sum of rewards and not the maximal reward. Bandit algorithms have been already used for network intrusion detection [15], but they typically consider classical or restless setting. [9, 21, 20] were the first to consider the extreme bandits problem, where our setting is defined as the max-k problem. [21] and [9] consider a fully parametric setting. The reward distributions are assumed to be exactly generalized extreme value distributions. Specifically, [21] assumes that the distributions are exactly Gumbel, P (x) = exp(−(x − m)/s)), and [9], that the distributions are exactly of Gumbel or Fréchet P (x) = exp(−(x − m)α /(sα))). Provided that these assumptions hold, they propose an algorithm for which the regret is asymptotically negligible when compared to the optimal oracle reward. These results are interesting since they are the first for extreme bandits, but their parametric assumption is unlikely to hold in practice and the asymptotic nature of their bounds limits their impact. Interestingly, the objective of [20] is to remove the parametric assumptions of [21, 9] by offering the T HRESHOLDA SCENT algorithm. However, no analysis of this algorithm for extreme bandits is 1 We recall the definition of the standard Pareto distribution as a distribution P , where for some constants α and C, we have that for x ≥ C 1/α , P = 1 − Cx−α .
3
provided. Nonetheless, to the best of our knowledge, this is the closest competitor for E XTREME H UNTER and we empirically compare our algorithm to T HRESHOLDA SCENT in Section 7. In this paper we also target the extreme bandit setting, but contrary to [9, 21, 20], we only make a semi-parametric assumption on the distribution; the second order Pareto assumption (Definition 2), which is standard in extreme value theory (see e.g., [13, 10]). This is significantly weaker than the parametric assumptions made in the prior works for extreme bandits. Furthermore, we provide a finite-time regret bound for our more general semi-parametric setting (Theorem 2), while the prior works only offer asymptotic results. In particular, we provide an upper bound on the rate at which the regret becomes negligible when compared to the optimal oracle reward (Definition 1).
5
Extreme Hunter
In this section, we present our main results. In particular, we present the algorithm and the main theorem that bounds its extreme regret. Before that, we first provide an initial result on the expectation of the maximum of second order Pareto random variables which will set the benchmark for the oracle regret. We first characterize the expectation of the maximum of second order Pareto distributions. The following lemma states that the expectation of the maximum of i.i.d. second order Pareto samples is equal, up to a negligible term, to the expectation of the maximum of i.i.d. Pareto samples. This result is crucial for assessing the benchmark for the regret, in particular the expected value of the maximal oracle sample. Theorem 1 is based on Lemma 3, both provided in the appendix. Theorem 1. Let X1 , . . . , Xn be n i.i.d. samples drawn according to (α, β, C, C ′ )-second order Pareto distribution P (see Definition 2). If α > 1, then: 2C ′ Dβ+1 1/α 1/α 1/α 2 E(max Xi ) − (nC)1/α Γ 1− α1 ≤ 4D (nC) + (nC) + B = o (nC) , n C β+1 nβ i
where D2 , D1+β > 0 are some universal constants, and B is defined in the appendix (9). Theorem 1 implies that the optimal strategy in hindsight attains the following expected reward: h i 1/α E [G∗n ] ≈ max (Ck n) k Γ 1− α1 k
Our objective is therefore to find a learner π Algorithm 1 E XTREME H UNTER such that E [G∗n ] − E [Gπn ] is negligible when Input: compared to E[G∗n ], i.e., when compared to K: number of arms ∗ ∗ (nC ∗ )1/α Γ 1− α1∗ ≈ n1/α where ∗ is the n: time horizon optimal arm. b: where for all k ≤ K : b ≤ βk N : minimum number of pulls of each arm From the discussion above, we know that the Initialize: minimization of the extreme regret is linked Tk ← 0 for all k ≤ K with the identification of the arm with the heavδ ← exp(− log2 n)/(2nK) iest tail. Our E XTREME H UNTER algorithm is Run: based on a classical idea in bandit theory: opfor t = 1 to n do timism in the face of uncertainty. Our stratfor k = 1 to K do egy is to estimate E [maxt≤n Xk,t ] for any k if Tk ≤ N then and to pull the arm which maximizes its upBk,t ← ∞ per bound. From Definition 2, the estimation else of this quantity relies heavily on an efficient esestimate b hk,t that verifies (2) timation of αk and Ck , and on associated confibk,t using (3) estimate C dence widths. This topic is a classic problem in update Bk,t using (5) with (2) and (4) extreme value theory, and such estimators exist end if provided that one knows a lower bound b on βk end for [10, 6, 7]. From now on we assume that a conPlay arm kt ← arg maxk Bk,t stant b > 0 such that b ≤ mink βk is known Tkt ← Tkt + 1 to the learner. As we argue in Remark 2, this end for assumption is necessary. Since our main theoretical result is a finite-time upper bound, in the following exposition we carefully describe all the constants and stress what quantities they depend on. Let Tk,t be the number of 4
samples drawn from arm k at time t. Define δ = exp(− log2 n)/(2nK) and consider an estimator b hk,t of 1/αk at time t that verifies the following condition with probability 1 − δ, for Tk,t larger than some constant N2 that depends only on αk , Ck , C ′ and b: p −b/(2b+1) 1 b = B1 (Tk,t ), (2) αk − hk,t ≤ D log(1/δ)Tk,t where D is a constant that also depends only on αk , Ck , C ′ , and b. For instance, the estimator in [6] (Theorem 3.7) verifies this property and provides D and N2 but other estimators are possible. Consider the associated estimator for Ck : Tk,t n o X b 1 h /(2b+1) 1/(2b+1) k,t bk,t = T C 1 Xk,u ≥ Tk,t (3) k,t Tk,t u=1 For this estimator, we know [7] with probability 1 − δ that for Tk,t ≥ N2 : q bk,t ≤ E log(Tk,t /δ) log(Tk,t )T −b/(2b+1) = B2 (Tk,t ), Ck − C k,T
(4)
where E is derived in [7] in the proof of Theorem 2. Let N = max A log(n)2(2b+1)/b , N2 where A depends on (αk , Ck )k , b, D, E, and C ′ , and is such that: (2b+1)/b √ 2D log(n)2 2 (2b+1)/b max (2B1 (N ), 2B2 (N )/Ck ) ≤ 1, N ≥ (2D log n) , N > 1−maxk 1/αk This inspires Algorithm 1, which first pulls each arm N times and then, at each time t > KN , pulls the arm that maximizes Bk,t , which we define as: bhk,t +B1 (Tk,t ) bk,t + B2 (Tk,t ) n C Γ̄ b hk,t , B1 (Tk,t ) , (5) where Γ̄(x, y) = Γ̃(1 − x − y), where we set Γ̃ = Γ for any x > 0 and +∞ otherwise. Remark 2. A natural question is whether it is possible to learn βk as well. In fact, this is not possible for this model and a negative result was proved by [7]. The result states that in this setting it is not possible to test between two fixed values of β uniformly over the set of distributions. Thereupon, we define b as a lower bound for all βk . With regards to the Pareto distribution, β = ∞ corresponds to the exact Pareto distribution, while β = 0 for such distribution that is not (asymptotically) Pareto. We show that this algorithm meets the desired properties. The following theorem states our main result by upper-bounding the extreme regret of E XTREME H UNTER. Theorem 2. Assume that the distributions of the arms are respectively (αk , βk , Ck , C ′ ) second order Pareto (see Definition 2) with mink αk > 1. If n ≥ Q, the expected extreme regret of E X TREME H UNTER is bounded from above as: ∗ (2b+1)/b − log(n)(1−1/α∗ ) −b/((b+1)α∗ ) log(n) + n + n , E[G∗n ]o(1) = L(nC ∗ )1/α K n where L, Q > 0 are some constants depending only on (αk , Ck )k , C ′ , and b (Section 6). Theorem 2 states that the E XTREME H UNTER strategy performs almost as well as the best (oracle) strategy, up to a term that is negligible when compared to the performance of the oracle strategy. ∗ Indeed, the regret is negligible when compared to (nC ∗ )1/α , which is the order of magnitude of the ∗ performance of the best oracle strategy E [Gn ] = maxk≤K E [maxt≤n Xk,t ]. Our algorithm thus detects the arm that has the heaviest tail. For n large enough (as a function of (αk , βk , Ck )k , C ′ and K), the two first terms in the regret become negligible when compared to the third one, and the regret is then bounded as: ∗ E [Rn ] ≤ E [G∗n ] O n−b/((b+1)α ) We make two observations: First, the larger the b, the tighter this bound is, since the model is then closer to the parametric case. Second, smaller α∗ also tightens the bound, since the best arm is then very heavy tailed and much easier to recognize. 5
6
Analysis
In this section, we prove an upper bound on the extreme regret of Algorithm 1 stated in Theorem 2. Before providing the detailed proof, we give a high-level overview and the intuitions. In Step 1, we define the (favorable) high probability event ξ of interest, useful for analyzing the mechanism of the bandit algorithm. In Step 2, given ξ, we bound the estimates of αk and Ck , and use them to bound the main upper confidence bound. In Step 3, we upper-bound the number of pulls of each suboptimal arm: we prove that with high probability we do not pull them too often. This enables us to guarantee that the number of pulls of the optimal arms ∗ is on ξ equal to n up to a negligible term. The final Step 4 of the proof is concerned with using this lower bound on the number of pulls of the optimal arm in order to lower bound the expectation of the maximum of the collected samples. Such step is typically straightforward in the classical (mean-optimizing) bandits by the linearity of the expectation. It is not straightforward in our setting. We therefore prove Lemma 2, in which we show that the expected value of the maximum of the samples in the favorable event ξ will be not too far away from the one that we obtain without conditioning on ξ. Step 1: High probability event. In this step, we define the favorable event ξ. We set def δ = exp(− log2 n)/(2nK) and consider the event ξ such that for any k ≤ K, N ≤ T ≤ n: p −b/(2b+1) 1 , αk − h̃k (T ) ≤ D log(1/δ)T p Ck − C̃k (T ) ≤ E log(T /δ)T −b/(2b+1) , where h̃k (T ) and C̃k (T ) are the estimates of 1/αk and Ck respectively using the first T samples. bk,t which are the estimates of the same quantities at time Notice, they are not the same as b hk,t and C t for the algorithm, and thus with Tk,t samples. The probability of ξ is larger than 1 − 2nKδ by a union bound on (2) and (4). Step 2: Bound on Bk,t . The following lemma holds on ξ for upper- and lower-bounding Bk,t . Lemma 1. (proved in the appendix) On ξ, we have that for any k ≤ K, and for Tk,t ≥ N : p 1 1 −b/(2b+1) (Ck n) αk Γ 1− α1k ≤ Bk,t ≤ (Ck n) αk Γ 1− α1k 1 + F log(n) log(n/δ)Tk,t (6) Step 3: Upper bound on the number of pulls of a suboptimal arm. We proceed by using the bounds on Bk,t from the previous step to upper-bound the number of suboptimal pulls. Let ∗ be the best arm. Assume that at round t, some arm k ̸= ∗ is pulled. Then by definition of the algorithm B∗,t ≤ Bk,t , which implies by Lemma 1: p −b/(2b+1) 1/α∗ 1/α (C ∗ n) Γ 1− α1∗ ≤ (Ck n) k Γ 1− α1k 1 + F log(n) log(n/δ)Tk,t Rearranging the terms we get: 1/α∗
(C ∗ n)
(Ck n)
1/αk
Γ 1− α1∗
p −b/(2b+1) ≤ 1 + F log(n) log(n/δ)Tk,t 1
(7)
Γ 1− αk
We now define ∆k which is analogous to the gap in the classical bandits: 1/α∗ (C ∗ n) Γ 1− α1∗ ∆k = −1 1/α (Ck n) k Γ 1− α1k Since Tk,t ≤ n, (7) implies for some problem dependent constants G and G′ dependent only on (αk , Ck )k , C ′ and b, but independent of δ that: 2 (2b+1)/(2b) (2b+1)(2b) log(n/δ) Tk,t ≤ N + G′ log n ∆ ≤ N + G log2 n log(n/δ) 2 k
6
This implies that number T ∗ of pulls of arm ∗ is with probability 1 − δ ′ , at least X (2b+1)/(2b) − KN, n− G log2 n log(2nK/δ ′ ) k̸=∗
where δ ′ = 2nKδ. Since n is larger than Q ≥ 2KN + 2GK log2 n log (2nK/δ ′ )
(2b+1)/(2b)
,
we have that T ∗ ≥ n2 as a corollary. Step 4: Bound on the expectation. We start by lower-bounding the expected gain: E[Gn ] = E max XIt ,Tk,t ≥ E max XIt ,Tk,t 1{ξ} ≥ E max X∗,T∗,t 1{ξ} = E max∗ Xi 1{ξ} t≤n
t≤n
t≤n
i≤T
The next lemma links the expectation of maxt≤T ∗ X∗,t with the expectation of maxt≤T ∗ X∗,t 1{ξ}. Lemma 2. (proved in the appendix) Let X1 , . . . , XT be i.i.d. samples from an (α, β, C, C ′ )-second order Pareto distribution F . Let ξ ′ be an event of probability larger than 1 − δ. Then for δ < 1/2 and for T ≥ Q large enough so that c max 1/T, 1/T β ≤ 1/4 for a given constant c > 0, that 1/β depends only on C, C ′ and β, and also for T ≥ log(2) max C (2C ′ ) , 8 log (2) : 1/α 1−1/α 1/α 8 (T C) δ E max Xt 1{ξ} ≥ (T C) Γ 1− α1 − 4 + α−1 t≤T 2C ′ D 1/α 1/α 2 + C 1+β1+β (T C) +B . − 2 4D T (T C) Tβ Since n is large enough so that 2n2 Kδ ′ = 2n2 K exp − log2 n ≤ 1/2, where δ ′ = exp − log2 n , and the probability of ξ is larger than 1 − δ ′ , we can use Lemma 2 for the optimal arm: ′1− 1 8D2 1 ′ Dmax 8 2B , E max∗ X∗,t 1{ξ} ≥ (T ∗ C ∗ ) α∗ Γ 1− α1∗ − 4+ α−1 δ α∗ − T ∗ − (C4C − 1 ∗ )1+b (T ∗ )b ∗ ∗ ∗ t≤T
(T C ) α
def
where Dmax = maxi D1+βi . Using Step 3, we bound the above with a function of n. In particular, ∗ we lower-bound the last three terms in the brackets using T ∗ ≥ n2 and the (T ∗ C ∗ )1/α factor as: ∗
(T ∗ C ∗ )1/α ≥ (nC ∗ )1/α
∗
2b+1 2 ′ KN 2b log(2n K/δ ) − 1 − GK n n
We are now ready to relate the lower bound on the gain of E XTREME H UNTER with the upper bound of the gain of the optimal policy (Theorem 1), which brings us the upper bound for the regret: E [Rn ] = E [G∗n ] − E [Gn ] ≤ E [G∗n ] − E max∗ Xi ≤ E [G∗n ] − E max∗ X∗,t 1{ξ} ≤ i≤T t≤T 2b+1 ∗ 2 ′ ′1−1/α∗ KN B 2b ≤ H(nC ∗ )1/α n1 + (nC1∗ )b + GK log(2n K/δ ) + + δ + , ∗ n n (nC ∗ )1/α where H is a constant that depends on (αk , Ck )k , C ′ , and b. To bound the last term, we use the ∗ ∗ ∗ ∗ definition of B (9) to get the n−β /((β +1)α ) term, upper-bounded by n−b/((b+1)α ) as b ≤ β ∗ . Notice that this final term also eats up n−1 and n−b terms since b/((b + 1)α∗ ) ≤ min(1, b). We finish by using δ ′ = exp − log2 n and grouping the problem-dependent constants into L to get the final upper bound, which is on the order of E [G∗n ] o(1): ∗ ∗ ∗ (2b+1)/b E [Rn ] ≤ L(nC ∗ )1/α K + n− log(n)(1−1/α ) + n−b/((b+1)α ) n log(n)
7
Comparison of extreme bandit strategies (K=3)
Comparison of extreme bandit strategies on the network data K=5 250
ExtremeHunter UCB ThresholdAscent
ExtremeHunter UCB ThresholdAscent
9000
Comparison of extreme bandit strategies (K=3)
2500
10000
ExtremeHunter UCB ThresholdAscent
200
2000
8000
6000 5000 4000
extreme regret
extreme regret
extreme regret
7000 1500
1000
150
100
3000 2000
50
500
1000 0
0
1000
2000
3000
4000
5000
6000
time t
7000
8000
9000
10000
0
0
1000
2000
3000
4000
5000
time t
6000
7000
8000
9000
10000
0
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
time t
Figure 1: Extreme regret as a function of time for the exact Pareto distributions (left), approximate Pareto (middle) distributions, and the network traffic data (right).
7
Experiments
In this section, we empirically evaluate E XTREME H UNTER on synthetic and real-world data. The measure of our evaluation is the extreme regret from Definition 1. Notice that even though we evaluate the regret as a function of time T , the extreme regret is not cumulative and it is more in the spirit of simple regret [5]. We compare our E XTREME H UNTER with T HRESHOLDA SCENT [20]. Moreover, we also compare to classical U CB [3], as an example of the algorithm that aims for the arm with the highest mean as opposed to the heaviest tail. When the distribution of a single arm has both the highest mean and the heaviest-tail, both E XTREME H UNTER and U CB are expected to perform the same with respect to the extreme regret. In the light of Remark 2, we set b = 1 to consider a wide class of distributions. Exact Pareto Distributions In the first experiment, we consider K = 3 arms with the distributions Pk (x) = 1−x−αk , where α = [5, 1.1, 2]. Therefore, the most heavy-tailed distribution is associated with the arm k = 2. Figure 1 (left) displays the averaged result of 1000 simulations with the time horizon T = 104 . We observe that E XTREME H UNTER eventually keeps allocating most of the pulls to the arm of the interest. Since in this case, the arm with the heaviest tail is also the arm with the largest mean, U CB also performs well and it is even able to detect the best arm earlier. T HRESHOLDA SCENT, on the other hand, was not always able to allocate the pulls properly in 104 steps. This may be due to the discretization of the rewards that this algorithm is using. Approximate Pareto Distributions For the exact Pareto distributions, the smaller the tail index the higher the mean and even UCB obtains a good performance. However, this is no longer necessarily the case for the approximate Pareto distributions. For this purpose, we perform the second experiment where we mix an exact Pareto distribution with a Dirac distribution in 0. We consider K = 3 arms. Two of the arms follow the exact Pareto distributions with α1 = 1.5 and α3 = 3. On the other hand, the second arm has a mixture weight of 0.2 for the exact Pareto distribution with α2 = 1.1 and 0.8 mixture weight of the Dirac distribution in 0. For this setting, the second arm is the most heavy-tailed but the first arm has the largest mean. Figure 1 (middle) shows the result. We see that U CB performs worse since it eventually focuses on the arm with the largest mean. T HRESHOLDA SCENT performs better than U CB but not as good as E XTREME H UNTER. Computer Network Traffic Data In this experiment, we evaluate E XTREME H UNTER on heavytailed network traffic data which was collected from user laptops in the enterprise environment [2]. The objective is to allocate the sampling capacity among the computer nodes (arms), in order to find the largest outbursts of the network activity. This information then serves an IT department to further investigate the source of the extreme network traffic. For each arm, a sample at the time t corresponds to the number of network activity events for 4 consecutive seconds. Specifically, the network events are the starting times of packet flows. In this experiment, we selected K = 5 laptops (arms), where the recorded sequences were long enough. Figure 1 (right) shows that E XTREME H UNTER again outperforms both T HRESHOLDA SCENT and U CB. Acknowledgements We would like to thank John Mark Agosta and Jennifer Healey for the network traffic data. The research presented in this paper was supported by Intel Corporation, by French Ministry of Higher Education and Research, and by European Community’s Seventh Framework Programme (FP7/2007-2013) under grant agreement no 270327 (CompLACS). 8
References [1] Naoki Abe, Bianca Zadrozny, and John Langford. Outlier Detection by Active Learning. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 504–509, 2006. [2] John Mark Agosta, Jaideep Chandrashekar, Mark Crovella, Nina Taft, and Daniel Ting. Mixture models of endhost network traffic. In IEEE International Conference on Computer Communications (INFOCOM),, pages 225–229. [3] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47(2-3):235–256, 2002. [4] Sébastien Bubeck, Nicolò Cesa-Bianchi, and Gábor Lugosi. Bandits With Heavy Tail. IEEE Transactions on Information Theory, 59(11):7711–7717, 2013. [5] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure Exploration in Multi-armed Bandits Problems. Algorithmic Learning Theory, pages 23–37, 2009. [6] Alexandra Carpentier and Arlene K. H. Kim. Adaptive and minimax optimal estimation of the tail coefficient. Statistica Sinica, 2014. [7] Alexandra Carpentier and Arlene K. H. Kim. Honest and adaptive confidence interval for the tail coefficient in the Pareto model. Electronic Journal of Statistics, 2014. [8] Varun Chandola, Arindam Banerjee, and Vipin Kumar. Anomaly detection: A survey. ACM Computing Surveys, 41(3):15:1–15:58, July 2009. [9] Vincent A. Cicirello and Stephen F. Smith. The max k-armed bandit: A new model of exploration applied to search heuristic selection. AAAI Conference on Artificial Intelligence (AAAI), 2005. [10] Laurens de Haan and Ana Ferreira. Extreme Value Theory: An Introduction. Springer Series in Operations Research and Financial Engineering. Springer, 2006. [11] Ronald Aylmer Fisher and Leonard Henry Caleb Tippett. Limiting forms of the frequency distribution of the largest or smallest member of a sample. Mathematical Proceedings of the Cambridge Philosophical Society, 24:180, 1928. [12] Boris Gnedenko. Sur la distribution limite du terme maximum d’une série aléatoire. The Annals of Mathematics, 44(3):423–453, 1943. [13] Peter Hall and Alan H. Welsh. Best Attainable Rates of Convergence for Estimates of Parameters of Regular Variation. The Annals of Statistics, 12(3):1079–1084, 1984. [14] Tze L. Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4–22, 1985. [15] Keqin Liu and Qing Zhao. Dynamic Intrusion Detection in Resource-Constrained Cyber Networks. In IEEE International Symposium on Information Theory (ISIT), 2012. [16] Markos Markou and Sameer Singh. Novelty detection: a review, part 1: statistical approaches. Signal Processing, 83(12):2481–2497, 2003. [17] Daniel B. Neill and Gregory F. Cooper. A multivariate Bayesian scan statistic for early event detection and characterization. Machine Learning, 79:261–282, 2010. [18] Carey E. Priebe, John M. Conroy, David J. Marchette, and Youngser Park. Scan Statistics on Enron Graphs. In Computational and Mathematical Organization Theory, volume 11, pages 229–247, 2005. [19] Ingo Steinwart, Don Hush, and Clint Scovel. A Classification Framework for Anomaly Detection. Journal of Machine Learning Research, 6:211–232, 2005. [20] Matthew J. Streeter and Stephen F. Smith. A Simple Distribution-Free Approach to the Max kArmed Bandit Problem. In International Conference on Principles and Practice of Constraint Programming (CP), volume 4204, pages 560–574, 2006. [21] Matthew J. Streeter and Stephen F. Smith. An Asymptotically Optimal Algorithm for the Max k-Armed Bandit Problem. In AAAI Conference on Artificial Intelligence (AAAI), pages 135–142, 2006. [22] Ryan Turner, Zoubin Ghahramani, and Steven Bottone. Fast online anomaly detection using scan statistics. IEEE Workshop on Machine Learning for Signal Processing (MLSP), 2010. 9
A
Proof of Lemma 3
Lemma 3. Assume that X1 , . . . , XT are T i.i.d. samples drawn according to (α, β, C, C ′ )-second order Pareto distribution, then for any x ≥ B: P max Xi ≤ x −exp −T Cx−α ≤ M exp −T Cx−α i
where M =
2 β+1 4 2C ′ T Cx−α + β+1 β T Cx−α , T C T
(8)
where B is defined as: 1/(αβ) 1/α B = max (2C ′ /C) , (8C) , (2T C ′ )1/(α(1+β)) .
(9)
Alternatively, let u ∈ (0, 1). When T ≥ log(1/u)B α /C: 4 2C ′ 1/α 1+β 2 P max Xi ≤ (T C/ log (1/u)) −u ≤u log(1/u) + β+1 β (log(1/u)) i T C T 1 1 2 1+β log (1/u) + β log (1/u) . =u×O T T Proof. Consider x ≥ B. Since the samples are i.i.d., we are going to study the following quantity2 : P(max Xi ≤ x) = P (x)T .
(10)
i
Since P is a second order Pareto, we have for any x ≥ 0: 1 − Cx−α − C ′ x−α(1+β) ≤ P (x) ≤ 1 − Cx−α + C ′ x−α(1+β) .
(11)
Since x ≥ B, we deduce from the first two terms in (9) that: Cx−α ≥ 2C ′ x−α(1+β)
and
2Cx−α ≤ 1/4.
Let cx be the quantity that depends on x and that is such that P (x) = 1 − Ccx x definition we know by (11) and further by the second inequality in (12) that: |cx − 1| ≤
(12) −α
. With such
C ′ x−αβ ≤ 1/2. C
(13)
Let y = Ccx x−α . By (12) and (13) we get that y ∈ [0, 21 ]. For any y ∈ [0, 12 ], we have, −y − y 2 ≤ log(1 − y) ≤ −y. Taking the exponential, setting y = Ccx x−α , and raising to the T -th power, we obtain: 2 exp −T Ccx x−α ≤
T
(1 − Ccx x−α ) ≤ 1, exp (−T (Ccx x−α ))
which by (10), the definition of cx , and both inequalities in (11) yields: P(max X ≤ x) 2 i i ′ −α(1+β) exp −T 2Cx−α − T C ′ x−α(1+β) ≤ ≤ exp T C x . exp(−T Cx−α ) After multiplication and subtraction of exp(−T Cx−α ): exp −T Cx−α exp −4T (Cx−α )2 − T C ′ x−α(1+β) − 1 ≤ P max Xi ≤ x − exp −T Cx−α i ≤ exp −T Cx−α exp T C ′ x−α(1+β) − 1 . 2
Notice that uT means ‘u to the power of T ’ and not ‘u transposed’.
10
We will now simplify the exp(y) − 1 terms in the previous inequality. For any y such that y ∈ (0, 1/2), we have exp(y) − 1 ≤ 2y and for any y ∈ R we have that y ≤ exp(y) − 1. In particular, this implies whenever x ≥ B ≥ (2T C ′ )1/(α(1+β)) , which is the third term in (9): exp −T Cx−α − 4T (Cx−α )2 − T C ′ x−α(1+β) ≤ P max Xi ≤ x − exp −T Cx−α i ≤ exp −T Cx−α 2T C ′ x−α(1+β) . This implies that for any x ≥ B and M as defined in (8): P max Xi ≤ x − exp −T Cx−α ≤ M exp −T Cx−α i
We now simply reparametrize this upper bound by setting: u = exp(−T Cx−α ). 1/α
Then u ∈ (0, 1) and x = (T C/ log (1/u)) . Then x is larger than B as soon as T is larger than log(1/u)B α /C. It follows that for such T , by the reparametrization in u, the rate of convergence of the distribution to a Fréchet distribution: 4 2C ′ 1/α 2 β+1 P max Xi ≤ (T C/ log (1/u)) −u ≤u (log 1/u) + β+1 β log(1/u) . i T C T
B
Proof of Theorem 1
Theorem 1. Assume that X1 , . . . , XT are T i.i.d. samples drawn according to (α, β, C, C ′ )-second order Pareto distribution P. If α > 1, then: 2C ′ Dβ+1 (T C)1/α 4D2 (T C)1/α 1/α + + B = o (T C) , E(max Xi )−(T C)1/α Γ 1− α1 ≤ i T C β+1 T β where D2 > 0 and D1+β > 0 are some universal constants, and B is as defined in (9). Proof. Since α > 1, by definition of a Fréchet distribution: Z ∞ 1 − exp(−T Cx−α ) dx = (T C)1/α Γ 1− α1
(14)
0
Notice that in (8) we have two terms of the form exp(−T Cx−α )(T Cx−α )p , for p = 2 and p = β + 1. In order to proceed, we first upper-bound the integral of such expression. Through a change of variable (setting t = T Cx−α ) we get that for any p > 0: Z ∞ Z (T C)1/α ∞ exp(−T Cx−α )(T Cx−α )p dx = exp(−t)tp−1−1/α dt = Dp (T C)1/α , (15) α 0 0 where Dp = Γ(p − 1/α)/α is bounded as long as p > 1/α, e.g. if p > 1. From the definition of expectation we have that: Z ∞ E max Xi = P max Xi ≥ x dx i
i
0
We now bound the difference between this expectation and that of the Fréchet distribution. Z ∞ E max Xi − 1 − exp −T Cx−α dx ≤ i 0 Z ∞ Z ∞ 1 − P max Xi ≤ x dx + 1 − exp −T Cx−α dx ≤ i
0
Z B ≤
0
Z B 1 − P max Xi ≤ x dx + 1 − exp −T Cx−α dx
i
0
Z ∞ + B
0
Z ∞ 1 − P max Xi ≤ x dx + 1 − exp −T Cx−α dx ,
i
B
11
where in the last term we split the domain of integration at B. We simply bound the first part by B and for the second term, we use Lemma 3 to obtain: Z ∞ Z ∞ 1 − exp −T Cx−α dx 1 − P max Xi ≤ x dx + i B B Z ∞ P max Xi ≤ x − exp −T Cx−α dx ≤ i Z0 ∞ 4 2 β+1 2C ′ T Cx−α + β+1 β T Cx−α exp −T Cx−α ≤ T C T 0 Instantiating (15) for p = 2 and p = β + 1, we deduce that: E(max Xi ) − (T C)1/α Γ(1 − 1/α) ≤ B + i
4D2 2C ′ Dβ+1 (T C)1/α + β+1 β (T C)1/α T C T
Note that since α > 1, we know that Dβ+1 and D2 are finite. This concludes the proof.
C
Proof of Lemma 1
Lemma 1. On ξ, we have that for any k ≤ K, and for Tk,t ≥ N , p 1 1 1 1 −b/(2b+1) (16) (Ck n) αk Γ 1− ≤ Bk,t ≤ (Ck n) αk Γ 1− 1+F log(n) log(n/δ)Tk,t αk αk Proof. From Step 1, we know that on ξ, we can bound Bk,t as: bhk,t +B1 (Tk,t ) α1 1 bk,t + B2 (Tk,t ))n Ck n k Γ 1− Γ̄ b hk,t , B1 (Tk,t ) ≤ (C αk α1 +2B1 (Tk,t ) Γ̄ 1/αk , 2B1 (Tk,t ) , ≤ (Ck + 2B2 (Tk,t ))n k since Γ is decreasing on [0, 1]. Note that by Theorem 1 we know that (Ck n)1/αk Γ(1 − 1/αk ) is a proxy for the expected maximum of the arm distribution with tail index αk . Factoring out (Ck n)1/αk we get: 1/αk +2B1 (Tk,t )
((Ck + 2B2 (Tk,t )) n)
Γ̄ (1/αk , 2B1 (Tk,t )) 1/αk +2B1 (Tk,t ) 1 2B2 (Tk,t ) ≤ (Ck n)2B1 (Tk,t ) Γ̄ (1/αk , 2B1 (Tk,t )) (Ck n) αk 1 + Ck
(17)
As we pull each arm at least N times (by the assumptions) we have that Tk,t ≥ N which implies max(2B1 (N ), 2B2 (N )/Ck ) ≤ 1. Since αk > 1: 1/αk +2B1 (Tk,t ) q 2 2B2 (Tk,t ) 2E −b/(2b+1) 1+ ≤ 1+ log(Tk,t /δ) log(Tk,t )Tk,t Ck Ck 6E p −b/(2b+1) ≤1+ log(n/δ) log(n)Tk,t . (18) Ck p Using again Tk,t ≥ N and log(Ck n)D log(1/δ)N −b/(2b+1) ≤ 1/2 for all k, we have: p (Ck n)2B1 (Tk,t ) = exp(log(Ck n)2D log(1/δ)T −b/(2b+1) ) p ≤ 1+2 log(Ck n)D log(1/δ)T −b/(2b+1) . (19) Now, let c be the maximum of the absolute value of the derivative of Γ on the segment: p p 1 1 −b/(2b+1) −b/(2b+1) − D log(1/δ)N + D log(1/δ)N 1 − max , 1 − min k αk k αk 12
Since by the assumption on N : N>
!(2b+1)/b p 2D log(1/δ) , 1 − maxk 1/αk
weknow that c is smaller than the maximum of the absolute value of the derivative of Γ function in 12 (1 − maxk 1/αk ), 32 (1 − mink 1/αk ) , since Γ is a convex and decreasing function on [0, 1]. When ξ happens, this implies: Γ̄(1/αk , 2B1 (Tk,t ) ≤ Γ(1−1/αk ) + 2cB1 (Tk,t ) p −b/(2b+1) (20) ≤ Γ(1−1/αk ) + 2cD log(1/δ)Tk,t Finally, combining (17) and (20), we get: 1/αk +2B1 (Tk,t ) (Ck + 2B2 (Tk,t ))n Γ̄ 1/αk , 2B1 (Tk,t ) p −b/(2b+1) ≤ (Ck n)1/αk Γ(1 − 1/αk ) 1 + F log(n) log(n/δ)Tk,t , where F depends on (αk , Ck )k , C ′ , D, and E. This implies that for Tk,t ≥ N , we can bound Bk,t as: p −b/(2b+1) 1/α (Ck n) k Γ 1−αk−1 ≤ Bk,t ≤ (Ck n)1/αk Γ 1−αk−1 1+F log(n) log(n/δ)Tk,t
D
Proof of Lemma 2
Lemma 2. Let X1 , . . . , XT be i.i.d. samples from an (α, β, C, C ′ )-second order Pareto distribution F . Let ξ ′ be an event of probability larger than 1 − δ. Then for T large enough so that c max(1/T, 1/T β) ≤ 1/2 (for a givenconstant c > 0 that depends only on C, C ′ and β), for 1/β T ≥ log(2) max C (2C ′ ) , 8 log (2) , and for δ < 1/2: ′ E max Xt 1{ξ } ≥ (T C)1/α Γ(1−1/α) − 8(T C)1/α δ 1−1/α t≤T 1/α 2C ′ D1+β (T C)1/α + + B . − 2 4D2 (TTC) C 1+β T β Proof. Since the probability of ξ ′ is larger than 1 − δ: E max Xt 1{ξ ′ } = E max Xt − E max Xt 1{ξ ′C } t≤T t≤T t≤T Z ∞ = E max Xt − P max Xt 1{ξ ′C } > x dx t≤T t≤T Z0 ∞ ≥ E max Xt − P max Xt > x dx − δxδ , t≤T
xδ
t≤T
where xδ is such that P (maxt≤T Xt ≤ xδ ) = 1 − δ. 1/β Since we have T ≥ log(2) max C (2C ′ ) , 8 log (2) , and δ < 1/2, we get by Lemma 3: 1/α P max Xi ≤ (T C/ log (1/(1 − δ))) − (1 − δ) i 2 1+β 1 2C ′ 1 4 ≤ (1 − δ) T log 1−δ + C 1+β log 1−δ ′
1+β ≤ T4 (2δ)2 + C2C 1+β (2δ) β ≤ cδ max Tδ , Tδ β ≤ cδ max T1 , T1β ,
13
where c > 0 is a constant that depends only on C, C ′ and β. This implies that for T large enough so that c max(1/T, 1/T β ) ≤ 1/4: x̄ = (T C/ log (1/(1 − δ/2)))
1/α
1/α
≥ xδ ≥ (T C/ log (1/(1 − 2δ)))
= x.
By Theorem 1 we can now deduce that: Z ∞ E max Xt 1{ξ ′ } ≥ E max Xt − P max Xt > x dx − δ x̄ t≤T
t≤T
x
t≤T
Z ∞ ≥ E max Xt − 1 − exp −T Cx−α dx t≤T
−
x
2C ′ D 1/α 1/α 4D2 + C 1+β1+β (T C) +B T (T C) Tβ
− δ x̄.
By the method of substitution, the Taylor expansion and for δ small enough: Z ∞ 1/α Z log(1/(1−2δ)) (T C) 1 − exp −T Cx−α dt = 1 − exp(−t) t−1−1/α dt α 0 x 1/α Z log(1/(1−2δ)) 2 (T C) ≤ exp(−t)t−1/α dt α 0 1/α Z log(1/(1−2δ)) 2 (T C) ≤ t−1/α dt α 0 1/α
2 (T C) 1−1/α log (1/(1 − 2δ)) α 8 1/α 1−1/α (T C) δ . ≤ α−1 ≤
1/α
We conclude the proof by combining all the above with the fact that δ x̄ ≤ 4 (T C) δ 1−1/α and ′ with Theorem 1 to get the final lower-bound on E [maxt≤T Xt 1{ξ }]: 2C ′ D1+β 1/α 1/α 1−1/α 1/α 1/α 8 2 (T C) Γ(1−1/α) − 4+ α−1 (T C) δ −2 4D (T C) + (T C) +B . 1+β β T C T
14