Addressing Bias in Online Selection with Limited Budget of Comparisons

Authors: ziyad  benomar
evgenii  chzhen
nicolas  schreuder
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-08 22:48:40

Abstract: Consider a hiring process with candidates coming from different universities. It is easy to order candidates with the same background, yet it can be challenging to compare them otherwise. The latter case requires additional costly assessments, leading to a potentially high total cost for the hiring organization. Given an assigned budget, what would be an optimal strategy to select the most qualified candidate?
We model the above problem as a multicolor secretary problem, allowing comparisons between candidates from distinct groups at a fixed cost. Our study explores how the allocated budget enhances the success probability of online selection algorithms.

Main paper: 
 introduction: 
 Online selection is among the most fundamental problems in decision-making under uncertainty, Multiple problems within this framework can be modeled as variants of the secretary problem [Dynkin, 1963 , Chow et al., 1971] , where the decision-maker has to identify the best candidate among a pool of totally ordered candidates, observed sequentially in a uniformly random order. When a new candidate is observed, the decision maker can either select them and halt the process or reject them irrevocably. The optimal strategy is well known and consists of skipping the first 1/e fraction of the candidates and then selecting the first candidate that is better than all previously observed ones. This strategy yields a probability 1/e of selecting the best candidate. A large body of literature is dedicated to the secretary problem and its variants, we refer the interested reader to [Chow et al., 1971 , Lindley, 1961] for a historical overview of this theoretical problem.In practice, as pointed out by several social studies, the selection processes often do not reflect the actual relative ranks of the candidates and might be biased with respect to some socioeconomic attributes [Salem et al., 2022 , Raghavan et al., 2020] . To tackle this issue, several works have explored variants of the secretary problem with noisy or biased observations [Salem and Gupta, 2019, Freij and Wästlund, 2010] . In particular, Correa et al. [2021a] studied the multi-color secretary problem, where each candidate belongs to one of K distinct groups, and only candidates of the same group can be compared. This corresponds for example to the case of graduate candidates from different universities, where the within-group orders are freely observable and can be trusted using a metric such as GPA, but inter-group order cannot be obtained by the same metric. This model, however, is too pessimistic, as it overlooks the possibility of obtaining inter-group orders at some cost, through testing and examination. Taking this into account, we study the multicolor secretary problem with a budget for comparisons, where comparing candidates from the same group is free, and comparing candidates from different groups has a fixed cost of 1. We assume that the decision-maker is allowed at most B comparisons. This budget B represents the amount of time/money that the hiring organization is willing to invest to understand the candidate's "true" performance. As in the classical secretary problem, an algorithm is said to have succeeded if the selected candidate is the best overall, otherwise, it has failed. The objective is to design algorithms that maximize the probability of success.The paper studies an extension of the multi-color secretary problem [Correa et al., 2021a] , where comparing candidates from different groups is possible at a cost. This makes the setting more realistic and paves the way for more practical applications, but also introduces new analytical challenges.In Section 2, we describe a general class of Dynamic-Threshold (DT) algorithms, defined by distinct acceptance thresholds for each group, that can change over time depending on the available budget. First, we examine a particular case where all thresholds are equal, which can be viewed as an extension of the classical 1/e-strategy. However, the analysis is intricate due to additional factors such as group memberships, comparison history, and the available budget. By carefully controlling these parameters, we compute the asymptotic success probability of the algorithm, demonstrating its extremely rapid convergence to the upper bound of 1/e when the budget increases, hence constituting a first efficient solution to the problem. Subsequently, our focus shifts to the case of two groups, where we explore another particular case of DT algorithms: static double threshold algorithms. These involve different acceptance thresholds for each group, that depend on the groups' proportions and the initial budget, but do not vary during the execution of the algorithm. We prove a recursive formula for computing the resulting success probability, and we exploit it to establish a closed-form lower bound and compute explicit thresholds.In the two-group scenario, we also derive the optimal algorithm among those that do not utilize the history of comparisons, which we refer to as memory-less. We present an efficient implementation of this algorithm and demonstrate, via numerical simulations, that it belongs to the class of DT algorithms when the number of candidates is large. Leveraging this insight, we numerically compute optimal thresholds for the two-group case.The secretary problem The secretary problem was introduced by Dynkin [1963] , who proposed the 1/e-threshold algorithm, having a success probability of 1/e, which is the best possible. Since then, the problem has undergone extensive study and found numerous applications, including in finance [Hlynka and Sheahan, 1988] , mechanism design [Kleinberg, 2005 , Hajiaghayi et al., 2007] , Nested Rollout Policy Adaptation (NRPA) [Dang et al., 2023] , active learning [Fujii and Kashima, 2016] , and the design of interactive algorithms [Sabato and Hess, 2016, 2018] . Moreover, the secretary problem has multiple variants [Karlin and Lei, 2015 , Bei and Zhang, 2022 , Assadi et al., 2019 , Keller and Geißer, 2015] , and has inspired other works, for instance, related to matching [Goyal, 2022 , Dickerson et al., 2019] or ranking [Jiang et al., 2021] . A closely related problem is the prophet inequality [Krengel and Sucheston, 1977, Samuel-Cahn, 1984] , where the decision-maker sequentially observes values sampled from known distributions, and its reward is the value of the selected item, in opposite the secretary problem where the reward is binary: 1 if the selected value is the maximum and 0 otherwise. Prophet inequalities also have many applications [Kleinberg and Weinberg, 2012 , Chawla et al., 2010 , Feldman et al., 2014] and have been explored in multiple variants [Kennedy, 1987 , Azar et al., 2018 , Bubna and Chiplunkar, 2023 , Benomar et al., 2024] .In some practical scenarios, the secretary problem may present a pessimistic model. Therefore, variants with additional information have been studied. For example, Gilbert and Mosteller [2006] explored a scenario where candidates' values are independently drawn from a known distribution. Other studies have examined potential improvements with other types of information, such as samples [Correa et al., 2021b] or machine-learned advice [Antoniadis et al., 2020 , Dütting et al., 2021 , Benomar and Perchet, 2023] . Conversely, some works more closely aligned with ours have investigated more constrained settings. Notably, Correa et al. [2021a] introduced the multi-color secretary problem, where totally ordered candidates belong to different groups, and only the partial order within each group, consistent with the total order, can be accessed. Under fairness constraints, they designed an asymptotically optimal strategy for selecting the best candidate. Other settings with only partial information have been studied as well. For example, Monahan [1980, 1982] addressed the optimal stopping of a target process when only a related process is observed, and they designed mechanisms for acquiring information from the target process. However, these works do not assume a fixed budget and instead consider a penalized version of the problem.Online algorithms with limited advice This paper also relates to other works on online algorithms, where the decision-maker is allowed to query a limited number of hints during execution. The objective of these analyses is to measure how the performance improves with the number of permitted hints. Such settings have been studied, for example, in online linear optimization [Bhaskara et al., 2021] , caching, [Im et al., 2022] , paging [Antoniadis et al., 2023] , scheduling [Benomar and Perchet] , metrical task systems [Sadek and Elias, 2024] , clustering [Silwal et al., 2023] , and sorting [Bai and Coester, 2024, Benomar and Coester, 2024] . Another related paper by Drygala et al. [2023] studies a penalized version of the Bahncard problem with costly hints. 
formal problem: 
 We consider a strictly totally ordered set of cardinal N , whose elements will be called candidates. We assume that these candidates are observed in a uniformly random arrival order (x 1 , . . . x N ), and that they are partitioned into K groups G 1 , . . . , G k . For all t ∈ [N ], we denote by g t ∈ [K] the group of x t , i.e. x t ∈ G gt , and we assume that {g t } t∈[N ] are mutually independent random variablesP(g t = k) = λ k , ∀t ∈ [N ], ∀k ∈ [K] ,where λ k > 0 for all k ∈ [K] andK k=1 λ k = 1.We assume that comparing candidates of the same group is free, while comparing two candidates of different groups is costly. To address the latter case, we consider that a budget B ≥ 0 is given for comparisons and we propose two models: the algorithm can pay a cost of 1 in order to:1. compare a two already observed candidates x t and x s belonging to different group, 2. determine if the current candidate is the best candidate seen so far among all the groups.For simplicity, we focus on the second model. However, we explain during the paper how our algorithms adapt to the first model and the cost they incur.When a new candidate arrives, the algorithm can choose to select them, halting the process, or it can choose to skip them, moving on to the next one-hoping to find a better candidate in the future. Once a candidate has been rejected, they cannot be recalled-the decisions are irreversible. Given the total number of candidates N , the probabilities (λ k ) k∈[K] characterizing the group membership, and a budget B, the goal is to derive an algorithm that maximizes the probability of selecting the best overall candidate. We refer to the problem as the (K, B)-secretary problemFor all t < s ∈ [N ], we denote by x t:s := {x t , . . . , x s }, and for all k ∈ [K] we denote by G k t:s the set of candidates of group G k observed between steps t and s,G k t:s := {x r : t ≤ r ≤ s and g r = k} = x s:t ∩ G k . If t = 1, then we lighten the notation G k s := G k 1:s .Let A be any algorithm for the (K, B)-secretary problem, we define its stopping time τ (A) as the step t when it decides to return the observed candidate. We will often drop the explicit dependency on A and write τ when no ambiguity is involved. We will say that A succeeded if the selected candidate x τ is the best among all the candidates {x 1 , . . . , x N }. Let us also define, for any step t ≥ 1, the random variablesr t = t t ′ =1 1(x t ≤ x t ′ , g t = g t ′ ) and R t = t t ′ =1 1(x t ≤ x t ′ ) .(1)Both random variables have natural interpretations: given a candidate at time t, r t is its in-group rank up to time t, while R t is its overall rank up to time t. Note that the actual values of x t do not play a role in the secretary problem and we can restrict ourselves to the observations r t , g t , R t . While the first two random variables are always available at the beginning of round t, the third one can be only acquired utilizing the available budget. At each step t ∈ [N ], the decision-maker observes r t , g t and can perform one of the following three actions:1. skip: reject x t and move to the next one; 2. stop: select x t ; 3. compare: if the comparison budget is not exhausted, use a comparison to determine if (R t = 1)-compare the candidate x t to the best already seen candidates in the other groups;Furthermore, if a comparison has been used at time t, the algorithm has to perform stop or skip afterward. We denote respectively by a t,1 and a t,2 the first and second action made by the algorithm at step t. Let us also define g * t the group to which the best candidate observed until step t belongs,g * t = argmax k∈[K] {max G k t } ∀t ∈ [N ] ,and B t as the budget available forA at step t B 1 = B and B t = B t-1 -1(a t,1 = compare) ∀t ∈ [N ] .In the presence of a non-zero budget, the first time when A decides to make a comparison will be a key parameter in our analysis of the success probability. We denote it by ρ 1 (A),ρ 1 (A) = min{t ∈ [N ] : a t,1 = compare} .As with the stopping time, when there is no ambiguity about A, we simply write ρ 1 . Remark 2.1. Although we formalized the problem using the variables r t and R t , the only information needed at any step t is 1(r t = 1) and 1(R t = 1), i.e we only need to know if the candidate is the best seen so far, in its own group and overall. In practice, 1(r t = 1) can be observed by comparing x t to the best candidate up to t -1 belonging to G gt , and if this is the case then 1(R t = 1) can be observed by comparing x t to the best candidate in the other group.3 Dynamic threshold algorithm for K groupsIn this section, we introduce a general family of Dynamic-threshold (DT) algorithms. A DT algorithm for the (K, B)-secretary problem is defined by a finite doubly-indexed sequence (α k,b ) k∈[K],b≤B of real numbers in [0, 1], which determines the acceptance thresholds based on the group of the observed candidate and the available budget. During a run of the algorithm, the thresholds used for each group dynamically change depending on the evolution of the available budget. We denote this algorithm byA B (α k,b ) k∈[K],b≤B .Upon the arrival of a new candidate x t , the algorithm observes its group g t = k ∈ [K] and its in-group rank r t , and has an available budget ofB t = b ≥ 0. If t/N < α k,b or r t = 0, the candidate is immediately rejected. Otherwise, if t/N ≥ α k,b and r t = 1, then the candidate is selected if b = 0;and if the budget is not yet exhausted (b > 0), then the algorithm pays a unit cost to observe the variable 1(R t = 1). If this variable is 1, indicating a favorable comparison, the candidate is selected; otherwise, it is rejected. A formal description is given in Algorithm 1, and a visual representation for the case of three groups is provided in Figure 1 . 
single-threshold algorithm for k groups: 
 In this section, we focus on the single-threshold algorithm, a specific case within the family of DT algorithms, where all thresholds are identical across groups and budgets. Initially, the algorithm rejects all candidates until step T -1, where T ∈ [N ] is a fixed threshold. Upon encountering a new candidate that is the best within its group, if no budget remains, the candidate is selected. Alternatively, if there is still a budget available, the algorithm utilizes it to determine if the current candidate is the best among all groups. If that is the case, the candidate is then selected. We denote by A B T the single-threshold algorithm with threshold T and budget B. We demonstrate that this algorithm has an asymptotic success probability converging very rapidly to the upper bound of 1/e.In this first lemma, we prove a recursion formula on the success probability of the single-threshold algorithm, with a threshold T = ⌊αN ⌋ for some α ∈ [0, 1].1,0 2,0 3,0 1,1 2,1 3,1 1,2 2,2 3,2 1,3 2,3 3,3 0.0 0.2 0.4 0.6 0.8 1.0 / 0 1 2 3 Remaining budget comp: = 1, = 1 skip: ∈ {2, 3} comp: = 1, ∈ {1, 2} skip: = 3 skip comp: = 1 Dynamic reshold algorithm: A ( , ) ∈[3], ≤3Figure 1 : Schematic description of a DT algorithm in the case of 3 groupsAlgorithm 1: Dynamic-Threshold algorithm A B (α k,b ) k∈[K],b≤B Input: Available budget B, thresholds (α k,b ) k∈[K],b≤B Initialization: b = B for t = 1, . . . , N do Receive new observation: (r t , g t ) if t ≥ ⌊α gt,b N ⌋ and r t = 1 then // compare in-group if b > 0 then // check budget 5 Update budget: b ← b -1 6 if R t = 1 then Return: t // compare inter-groupelse Return: t Lemma 3.1. The success probability of the single threshold algorithm A B T with threshold T = ⌊αN ⌋ and budget B ≥ 0 satisfies the recursion formulaP(A B T succeeds) = α -α K K -1 + 1(B ≥ 0) (K -1) N t=T T K t K+1 P(A B-1 t+1 succeeds) + O log N N .The proof hinges on analyzing the behavior of the algorithm following the first comparison. After that comparison, the algorithm halts if R t = 1, and the success probability can be computed in that case. Otherwise, if R t ̸ = 1, the candidate is rejected, and the algorithm transitions to a new state at step t + 1, where the available budget reduces to B -1. Its success probability becomes precisely that of algorithm A B-1 t+1 , with budget B -1 and threshold t + 1. The recursion outlined in Lemma 3.1 can be used to calculate the asymptotic success probability of the single-threshold algorithm A B ⌊αN ⌋ as the number of candidates N approaches infinity. Theorem 3.2. The asymptotic success probability of the single threshold algorithm A B T with threshold T = ⌊αN ⌋ and budget B ≥ 0 is limN →∞ P(A B ⌊αN ⌋ succeeds) = α K K -1 B b=0 1 α K-1 - b ℓ=0 log(1/α K-1 ) ℓ ℓ! .In particular, limB→∞ lim N →∞ P(A B ⌊αN ⌋ succeeds) = α log(1/α) .Note that, for B = ∞, the asymptotic success probability in the previous theorem corresponds to the success probability of the algorithm with a threshold ⌊αN ⌋ in the secretary problem. Indeed, with an unlimited budget, the decision-maker can assess at each step whether the current candidate is the best so far, and the problem becomes equivalent to the classical secretary problem.Alternative comparison model. In the alternative comparison model presented in Section 2, the single threshold algorithm A B T can be adapted to guarantee the same success probability at the cost of K -1 additional comparisons. After the first T candidates are rejected, K -1 comparisons are made between the maximums from each group to identify the best candidate so far. The algorithm then keeps track of the best candidate: whenever a new candidate is the best in their group, they are compared to the current best candidate using a single comparison, and the latter is updated accordingly. This approach enjoys the same guarantees as in Theorem 3.2, but with a budget ofK + B -1 instead of B.The next corollary measures how the success probability of the single threshold algorithm, in the setting with K groups, converges to 1/e as the budget increases. Corollary 3.2.1. The success probability of the single-threshold algorithm with threshold T = ⌊N/e⌋ and budget B ≥ 0 satisfies limN →∞ P(A B ⌊N/e⌋ succeeds) ≥ 1 e 1 - (K -1) B+1 (B + 1)! .In particular, for all ε > 0, if K ≤ 1 + B+1 e (eε)1 B+1 , then lim N P(A B ⌊N/e⌋ succeeds) ≥ (1 -ε)/e.This corollary proves that the success probability of A B ⌊N/e⌋ converges very rapidly to the upper bound 1/e as B increases. However, the convergence becomes slower when K is larger. Surprisingly, the asymptotic success probability of A B ⌊N/e⌋ is not influenced by the proportions (λ k ) k∈ [K] , but only by the number of groups K. This means that the algorithm does not benefit from the cases where there is a majority group G k with λ k very close to 1, which would make the problem easier. Indeed, it is always possible to achieve a success probability of max k∈[K] λ k /e by rejecting all the candidates not belonging to the majority group G k * , and using the classical 1/e-rule counting only elements of G k * . This algorithm can be combined with ours by always running the one with the highest success probability, depending on the available budget, the number of groups, and the group proportions. The resulting algorithm has a success probability that converges to the upper bound 1/e both when B increases and when max k λ k converges to 1. Nonetheless, due to the very fast convergence of the success probability of the single threshold algorithm to 1/e, the improvement brought by having a majority group is only marginal when the budget is sufficient.As a consequence, the single threshold algorithm surprisingly constitutes a very efficient solution to the problem even with moderate values of the budget. Computing the optimal thresholds remains however an intriguing question, which we explore in the following sections in the case of two groups. 
the case of two groups: 
 In this section, we delve into the particular case of two groups, and we demonstrate how leveraging different thresholds for each group can enhance the success probability. Let λ ∈ (0, 1) represent the probability of belonging to group G 1 , and 1 -λ the probability of belonging to group G 2 . We examine the success probability of Algorithm A B (α, β), with threshold ⌊αN ⌋ for group G 1 and ⌊βN ⌋ for group G 2 , having a budget of B comparisons. This algorithm is a specific instance of the DT family, wherein the thresholds depend only on the group, and not on the available budget. We call it a static double-threshold algorithm.We assume without loss of generality that α ≤ β, and we denote by C N the event(C N ) : ∀t ≥ 1 : max(||G 1 t | -λt| , ||G 2 t | -(1 -λ)t|) ≤ 4 t log N .This event provides control over the group sizes at each step. Lemma A.2 guarantees that C N holds true with a probability at least 1 -1 N 2 for N ≥ 4. Furthermore, for all t ∈ [N ], we denote by A B t (α, β) the algorithm with acceptance thresholds max{⌊αN ⌋, t} and max{⌊βN ⌋, t} respectively for groups G 1 and G 2 , and we denote by U B N,t,k the probabilityEQUATIONSimilar to the analysis of the single-threshold algorithm, we establish in Lemma C.1 a recursion formula satisfied by (U B N,t,k ) B,t,k , which we later utilize to derive lower bounds on the asymptotic success probability of A B (α, β). To prove this lemma, we study the probability distribution of the occurrence time ρ 1 of the first comparison made by A B t (α, β), and we examine the algorithm's success probability following it. Essentially, if ρ 1 = s, we can compute the probability of stopping and the corresponding success probability, and the distribution of the state of the algorithm at step s + 1, which yields the recursion. Using adequate concentration arguments and Lemma C.1, we show the two following results, giving explicit recursive formulas satisfied by the limit of U B N,t,k when N → ∞, respectively for k = 2 and k = 1. Lemma 4.1. For all B ≥ 0 and w ∈ [α, β], the limit φ B 2 (α, β; w) = lim N →∞ U B N,⌊wN ⌋,2 exists, and it satisfies the following recursionφ B 2 (α, β; w) = -λw log (1 -λ) w β + λ + (1 -λ)βw 2 (1 -λ)w + λβ B b=0 1 β - b ℓ=0 log(1/β) ℓ ℓ! + 1(B > 0) w 2 β w (1 -λ) 2 w + λ(2 -λ)u ((1 -λ)w + λu) 2 u 2 φ B-1 2 (α, β; u)du . Moreover, U B N,⌊wN ⌋,2 = φ B 2 (α, β; w) + O log N N .Lemma 4.2. For all B ≥ 0 and w ∈ [α, β], the limit φ B 1 (α, β; w) = lim N →∞ U B N,⌊wN ⌋,1 exists, and it satisfies the following recursionφ B 1 (α, β; w) = λw log 1 -λ + λ β w + λwβ 2 (1 -λ)w + λβ B b=0 1 β - b ℓ=0 log(1/β) ℓ ℓ! + 1(B > 0) λ 2 w β w (u -w)φ B-1 2 (α, β; u) ((1 -λ)w + λu) 2 u du . Moreover, U B N,⌊wN ⌋,1 = φ B 1 (α, β; w) + O log N N .We deduce that the asymptotic success probability of Algorithm A B ⌊wN ⌋ , conditioned on the event C N , exists and equals φ B 1 (α, β; w) + φ B 2 (α, β; w). Additionally, by applying Lemma A.3, we eliminate the conditioning on C N , thus proving the following theorem. Theorem 4.3. For all 0 < α ≤ β ≤ 1, The success probability of Algorithm A B (α, β) satisfiesP(A B (α,β) succeeds) -O log N N = λα log β α + αβ B b=0 1 β - b ℓ=0 log(1/β) ℓ ℓ! + 1(B > 0) α β α φ B-1 2 (α, β; u)du u 2 ,with φ B 2 (α, β; •) defined in Lemma 4.1. It is possible to use Theorem 4.3 and 4.1 to numerically compute the success probability of A B (α, β). However, this computation is heavy due the recursion defining φ B 2 (α, β; w). Moreover, it is difficult to prove a closed expression, and even more to compute the optimal thresholds. By disregarding the term containing φ 2 (α, β; •) in the theorem, we derive an analytical lower bound expressed as a function of the parameters λ, B, α, and β, allowing a more effective threshold selection. In the subsequent discussion, for all w ∈ (0, 1] and B ≥ 0, we denote by S B (w) the following sum:S B (w) = B b=0 1 w - b ℓ=0 log(1/w) ℓ ℓ! . Corollary 4.3.1. Assume that λ ≥ 1/2. Let h B : β → min β e exp βS B (β) λ, β , and αB , βB the thresholds defined as αB = h B ( βB ), and βB minimizing the mappingβ ∈ [0, 1] → λh(β) log β h B (β) + h B (β)βS B (β) , then the success probability of A B ( αB , βB ) satisfies lim N →∞ P(A B (α B , βB ) succeeds) ≥ 1 e -min 1 e(B + 1)! , ( 4 e -1)λ(1 -λ) .Therefore, in contrast to the single-threshold algorithm, the asymptotic success probability of A B (α B , βB ) approaches 1/e both when the budget increases and when λ approaches 0 or 1.In the following, an algorithm is called memory-less if its actions at any step t ∈ [N ] depend only on the current observations r t , g t , 1(R t = 1), the available budget B t , and the cardinals(|G k t-1 |) k∈[K] .We use in this section a dynamic programming approach to determine the optimal memory-less algorithm, which we denote by A * . Unlike previous sections, our analysis here is not asymptotic. By meticulously examining how various variables, including the precise number of candidates observed in each group, influence the success probability of A * , we rigorously analyze its state transitions and corresponding success probabilities to determine optimal actions at each step.A full description and analysis of the optimal memory-less algorithm can be found in Section D. Here, we illustrate its actions through Figure 2 . Alternative comparison model. In the particular case of two groups, both comparison models introduced in Section 2 are equivalent, as freely comparing a candidate with the best in their group and then making one costly comparison with the best candidate from the other group is sufficient to determine if they are the best so far. Therefore, all the results of the current section regarding the static double-threshold algorithm and optimal memory-less algorithm remain true in the alternative comparison model. 
numerical experiments: 
 In this section, we confirm our theoretical findings via numerical experiments, and we give further insight regarding the behavior of the algorithms we presented and how they compare to each other. In all the empirical experiments of this section, each point is computed over 10 6 independent trials. The code used for the experiments is available at github.com/Ziyad-Benomar/Addressing-bias-in-onlineselection-with-limited-budget-of-comparisons.Using Theorem 3.2, the optimal threshold, for the single-threshold algorithm, can be computed numerically for fixed K and B. Figure 3 illustrates the optimal threshold and the corresponding success probability for B ∈ {0, . . . , 30} and K ∈ {2, 10, 25, 50}. For any K ≥ 2, as the budget grows to infinity, the problem becomes akin to the standard secretary problem, leading the optimal threshold to converge to 1/e. However, as discussed in Corollary 3.2.1, the convergence is slower when the number of groups K is higher. Moreover, Theorem 3.2 reveals that the asymptotic success probability is independent of the probabilities of belonging to each group, and it is equal to a value smaller than 1/e. This indicates a discontinuity of the success probability at the extreme points of the polygon defining the possible values of (λ k ) k∈ [K] . Figure 4 illustrates this behavior for the case of two groups, with N = 500 candidates, and B ∈ {0, 1, 2}. On the other hand, while our theoretical results study asymptotic success probabilities, they do not comprehend how the performance of the algorithms varies with the number of candidates. Figure 5 shows that the success probability is better when the number of candidates is small, and it decreases to match the asymptotic expression when N → ∞, represented with dotted lines, for K ∈ {2, 3, 4}, with B = 3. In the case of two groups, Figure 3 shows that, even with a very limited budget, the single-threshold algorithm has a success probability almost indistinguishable from the upper bound 1/e. Consequently, in the remaining experiments in the two-group scenario, we restrict ourselves to small budgets B ≤ 3.Theorem D.4 shows a recursive formula for computing the success probability of the optimal memory-less algorithm A * for all N ≥ 1, B ≥ 0, and λ ∈ (0, 1). For λ = 0.5, both groups have symmetric roles, and the optimal thresholds αB and βB to choose in the static-threshold algorithm are identical. Hence, the success probability of A B (α B , βB ) for λ = 0.5 is exactly that of the single-threshold algorithm, which is independent of λ (Theorem 3.2). We deduce from this observation and Figure 6 that having different thresholds for each group yields a substantial improvement over the single-threshold algorithm when λ is close to 0 or 1.Finally, to emphasize that the dynamic programming algorithm A * is equivalent to an instance of DT algorithm for large N , Figure 7 For λ ∈ {0.5, 0.7, 0.95}, the figure confirms that, despite the intricate structure of the optimal memory-less algorithm, it does not surpass the performance of the DT algorithm with optimal thresholds when N is large. Nonetheless, the analysis of the optimal memory-less algorithm is what enables the numerical computation of the optimal thresholds, as explained previously. Figure 8 shows the optimal thresholds α ⋆ b , β ⋆ b for all λ ∈ [0.5, 1] and B ∈ {0, 1, 2}. These thresholds are continuous functions of λ, both converging to 1/e very rapidly as the budget increases. Indeed, for B ≥ 1, they both become very close to 1/e, as for B = 0, the optimal thresholds are exactly equal to α ⋆ 0 = λ exp( 1 λ -2) and β ⋆ 0 = λ, which correspond to the optimal thresholds described in Corollary 4.3.1 for B = 0 (See the proof of the corollary). 
conclusion and future work: 
 This paper explores more realistic online selection processes, wherein nuanced factors such as imperfect comparisons and optimal budget utilization are considered. We studied a partially ordered secretary problem, wherein a constrained budget of comparisons is allowed. Our findings encompass both asymptotic and non-asymptotic analyses. Specifically, we explore the asymptotic behavior of the single threshold algorithm with K groups, demonstrating its high efficiency with a non-zero budget. Furthermore, in the context of two groups, we study the success probability of static double-threshold algorithms, and we present a non-asymptotic optimal memoryless algorithm. Through numerical experimentation, we demonstrate that this algorithm behaves as a DT algorithm, and, leveraging this insight, we show how to numerically compute the optimal DT thresholds. However, a limitation of the paper is that optimal thresholds are only computed in the case of two groups. Future investigation could explore methods for numerically or analytically characterizing optimal DT thresholds with an arbitrary number of groups K. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [No] Justification: The runtime is not an important factor in our simulations, we do not feel that precising computer resources is relevant. Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 9. Code Of Ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: We have reviewed the Code of Ethics. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: The paper studies a fundamental theoretic problem. It seems to us that no particular societal impact should be discussed. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The contribution of the paper is mainly theoretical.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: We do not use any assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: With the assumption that the group membership of each candidate is a random variable, to compute the asymptotic success probabilities of the algorithms presented in the paper, it is necessary to use concentration inequalities to estimate the number of candidates in each group. We use Lemma 3 from Jamieson et al. [2014] to prove the following. Lemma A.1 (Jamieson et al. [2014] ). Let (X t ) t≥1 be i.i.d. Bernoulli random variables, N a positive integer, and m > 0 satisfying N m > 8, then it holds with a probability of at least 1 -25N 2m that ∀t ≥ 1 : t s=1 (X s -E[X s ]) ≤ 2 (m + 1)t log N Proof.Bernoulli random variables are sub-Gaussian with scale parameter 1/2, hence Lemma 3 from Jamieson et al. [2014] with ε = 1 guarantees that, with a probability of at least 1 -3( δ log 2 ) 2 , the following holds∀t ≥ 1 : t s=1 (X s -E[X s ]) ≤ 2 t log log(2t) δ . Consider positive integers T ≤ N , m ≥ 1 such that N m > 8, and δ = 2/N m . Then for all t ∈ {T, . . . , N } log(2t) δ ≤ 2t δ = N m t ≤ N m+1and we deduce thatP ∀t ≥ 1 : t s=1 (X s -E[X s ]) ≤ 2 (m + 1)t log N ≥ P ∀t ≥ 1 : t s=1 (X s -E[X s ]) ≤ 2 t log log(2t) 2/N m ≥ 1 - 3(2/ log 2) 2 N 2m ≥ 1 - 25 N 2m .In the context of the K-group secretary problem, adequately using the previous Lemma and using union bounds yields a concentration inequality on the number of candidates belonging to each group. Lemma A.2. Let N ≥ max(4, K), and consider the following event∀k ∈ [K], ∀t ≥ 1 : ||G k t | -λ k t| ≤ 4 t log N , which we denote by C N . Then it holds that P(C N ) ≥ 1 -1 N 2 .Proof. The previous Lemma with N ≥ 4, m = 3 and respectively with the Bernoulli random variablesX t,k,0 = 1(g t = k) and X t,k,1 = 1 -1(g t = k), gives for all i ∈ {0, 1} and k ∈ [K] that P ∀t ≥ 1 : (-1) i (|G k t | -λ k t) ≤ 4 t log N ≥ 1 - 25 N 6 ,and we obtain by a union bound that P(C N ) ≥ 1 -50K N 6 . Given that N ≥ max(4, K), it follows thatP(C N ) ≥ 1 - K N • 50 N 3 • 1 N 2 ≥ 1 - 1 N 2 .Lemma A.3. Let E be any event, not necessarily independent of C N (defined in Lemma A.2), thenP(E | C N ) = P(E) + O(1/N 2 ) .Proof. We have by Lemma A.2 thatP(E | C N ) = P(E ∩ C N ) P(C N ) ≤ P(E) 1 -1 N 2 ≤ 1 + 2 N 2 P(E) ≤ P(E) + 2 N 2 .Using the same inequality with the complementary event E c of E givesP(E | C N ) = 1 -P(E c | C N ) ≥ 1 -P(E c ) + 2 N 2 = P(E) - 2 N 2 ,which concludes the proof.Lemma A.4. For any x > 0 and for any B ≥ 1 we have0 ≤ xe x - B b=0 e x - b ℓ=0 x ℓ ℓ! ≤ e x x B+2 (B + 1)! . Proof. Let x > 0 and B ≥ 1. First, observe that ∞ b=0 e x - b ℓ=0 x ℓ ℓ! = ∞ b=0 ∞ ℓ=b+1 x ℓ ℓ! = ∞ ℓ=1 ℓ-1 b=0 x ℓ ℓ! = ∞ ℓ=1 x ℓ (ℓ -1)! = x ∞ ℓ=0 x ℓ ℓ! = xe x , therefore B b=0 e x - b ℓ=0 x ℓ ℓ! ≤ xe x ,and we havexe x - B b=0 e x - b ℓ=0 x ℓ ℓ! = ∞ b=B+1 ∞ ℓ=b+1 x ℓ ℓ! = ∞ ℓ=B+2 ℓ-1 b=B+1 x ℓ ℓ! = ∞ ℓ=B+2 (ℓ -B -1) x ℓ ℓ! ≤ ∞ ℓ=B+2 x ℓ (ℓ -1)! ≤ x ∞ ℓ=B+1 x ℓ ℓ! ≤ e x x B+2 (B + 1)! ,where we used for the last step the classical inequality∞ ℓ=B+1 x ℓ ℓ! = e x - B ℓ=0 x ℓ ℓ! ≤ e x x B+1 (B + 1)! .B Single-Threshold algorithms for K groups B.1 Proof of Lemma 3.1Proof. We consider that B ≥ 1. The case B = 0 is treated separately at the end of the proof. Let C N the event (∀k∈ [K], ∀t ≥ 1 : ||G k t | -λ k t| ≤ 4 √ t log N ). It holds that P(A B T succeeds | C N ) = N t=T K k=1 K ℓ=1 P(A B T succeeds, ρ 1 = t, g t = ℓ, g * T -1 = k | C N ) = N t=T K k=1 K ℓ=1 P(A B T succeeds, R t = 1, ρ 1 = t, g t = ℓ, g * T -1 = k | C N ) + N t=T K k=1 K ℓ=1 P(A B T succeeds, R t ̸ = 1, ρ 1 = t, g t = ℓ, g * T -1 = k | C N ) .(3)In the following, we will estimate the terms in both sums. We recall that we consider K and (λ k ) k∈[K] to be constants, and T = αN + o(1), with α also a constant. All the O terms appearing in the proof are independent of t, as T ≤ t ≤ N , they only depend on N , T /N = α + o(1), and the constant parameters.For t ∈ {T, . . . , N }, if ρ 1 = t and R t = 1, then the Algorithms stops on x t , hence its succeeds if and only if x t = x max . The event x t = x max is independent of the group membership of the candidates, thus independent of C N , and its probability is 1/N . The event g t = ℓ, however, is not independent of C N , but Lemma A.3 gives that P(g t = ℓ | C N ) = P(g t = ℓ) + O(1/N 2 ) = λ ℓ + O(1/N 2 ).Therefore, it holds for all k, ℓ ∈ [K] and t ∈ {T, . . . , N } thatP(A B T succeeds, R t = 1,ρ 1 = t, g t = ℓ, g * T -1 = k | C N ) = P(x t = x max , ρ 1 ≥ t, g t = ℓ, g * T -1 = k | C N ) = P(x t = x max )P(g t = ℓ | C N )P(ρ 1 ≥ t, g * T -1 = k | C N ) = λ ℓ N + O(1/N 3 ) P(ρ 1 ≥ t, g * T -1 = k | C N ) .Note that, for the single-threshold algorithm, we have the equivalence ρ 1 = t ⇐⇒ ρ 1 ≥ t and r t = 1. EQUATION)On the other hand, regarding the terms of the second sum in (3), if ρ 1 = t but R t ̸ = 1, the Algorithm uses a comparison to observe R t but then skips to the next step t + 1. The budget at step t + 1 is thus B -1 and the group of the best candidate seen so far remains unchanged. Given that the single threshold algorithm is memory-less, its state at time t + 1 is fully determined by B -1, g * t and the number of candidates seen in each group so far, which is controlled by C N . We deduce thatEQUATIONwhereP(A B-1 N +1 succeeds) = 0. For ℓ = k, the probability P(R t ̸ = 1, ρ 1 = t, g t = ℓ, g * T -1 = k | C N ) is zero, because if g *T -1 = k, ρ 1 ≥ t and g t = ℓ, then the best candidate up to step T -1 belongs to group G k , and no candidate x s for s ∈ {T, . . . , t -1} is better than the maximum in its group seen before step T -1, thus if x t belongs to G k and r t = 1 then necessarily R t = 1.For ℓ ̸ = k, it holds thatP(R t ̸ = 1,ρ 1 = t, g t = ℓ, g * T -1 = k | C N ) = P(ρ 1 = t, g t = ℓ, max x 1:t ∈ G k T -1 | C N ) = P(max x 1:t ∈ G k T -1 | C N )P(ρ 1 = t, g t = ℓ | max x 1:t ∈ G k T -1 , C N ) = λ k (T -1) t -1 + O(1/N 2 ) P(ρ 1 = t, g t = ℓ | max x 1:t ∈ G k T -1 , C N ) = λ k T t + O(1/N 2 ) P(g t = ℓ | C N )P(max G ℓ T :t-1 < max G ℓ T -1 < x t and ∀m ∈ [K] \ {k, ℓ} : max G m T :t-1 < max G m T -1 | C N ) = λ k T t + O(1/N 2 ) (λ ℓ + O(1/N 2 ))E 1 |G ℓ t-1 |+1 • |G ℓ T -1 | |G ℓ t-1 | C N m / ∈{k,ℓ} E |G m t-1 | |G m T -1 | C N = λ ℓ λ k T t + O(1/N 2 ) E 1 |G ℓ t-1 |+1 • |G ℓ T -1 | |G ℓ t-1 | C N m / ∈{k,ℓ} E |G m t-1 | |G m T -1 | C N = λ ℓ λ k T t + O(1/N 2 ) T λ ℓ t 2 + O log N N 3 m / ∈{k,ℓ} T t + O log N N = λ ℓ λ k T t + O(1/N 2 ) T λ ℓ t 2 + O log N N 3 T K-2 t K-2 + O log N N = λ k T K t K+1 + O log N N 3, where we used in the last equations the event C N and the assumption T = Θ(N ). Therefore, substituting into (6) gives for all ℓ, k ∈ [K] and t ∈ {T, . . . , N } thatP(A B T succeeds,R t ̸ = 1, ρ 1 = t, g t = ℓ, g * T -1 = k | C N ) = λ k T K t K+1 + O log N N 3 1(k ̸ = ℓ) P(A B-1 t+1 succeeds | g * t = k, C N ) = λ k T K t K+1 + O log N N 3 1(k ̸ = ℓ) P(A B-1 t+1 succeeds, g * t = k | C N ) P(g * t = k | C N ) = λ k T K t K+1 + O log N N 3 1(k ̸ = ℓ) P(A B-1 t+1 succeeds, g * t = k | C N ) λ k + O(1/N 2 ) = T K t K+1 + O log N N 3 1(k ̸ = ℓ) P(A B-1 t+1 succeeds, g * t = k | C N ) . (7)Finally, substituting (4) and ( 7) into (3), and recalling that all the previous O terms are independent of t, gives thatP(A B T succeeds | C N ) = N t=T K k=1 K ℓ=1 λ ℓ λ k N (T /t) K + O log N N 3 + N t=T K k=1 ℓ̸ =k T K t K+1 + O log N N 3 P(A B-1 t+1 succeeds, g * t = k | C N ) = 1 + O log N N N t=T K k=1 K ℓ=1 λ ℓ λ k N (T /t) K + N t=T K k=1 ℓ̸ =k T K t K+1 P(A B-1 t+1 succeeds, g * t = k | C N ) = 1 + O log N N T K N N t=T 1 t K + (K -1) N t=T T K t K+1 P(A B-1 t+1 succeeds | C N ) .Using Riemann sum properties, we obtainT K N N t=T 1 t K = (T /N ) K N N t=T 1 (t/N ) K = α K 1 α du u K + O(1/N ) = α -α K K -1 + O(1/N ) ,and by Lemma A.3 we have for all t ∈ {T, . . . , N } and b ≥ 0 thatP(A b t succeeds | C N ) = P(A b t succeeds) + O(1/N 2 ) , with the O(1/N 2 ) independent of t. Observing that N t=T T K t K+1 = 1-α K K + o(1) = O(1), it follows that P(A B T succeeds) = 1 + O log N N α -α K K -1 + (K -1) N t=T T K t K+1 P(A B-1 t+1 succeeds) + O( 1 N ) = α -α K K -1 + (K -1) N t=T T K t K+1 P(A B-1 t+1 succeeds) + O log N N .This concludes the proof for B ≥ 1.For B = 0, P(A 0 t+1 succeeds | C N ) can be decomposed as in (3). However, the terms of the second sum are all zero, because if ρ 1 = t then the algorithm stops at t, but since R t ̸ = 1, the selected candidate is not the best one, and thus the succeeding probability is 0. All the computations regarding the first sum stay the same, and we obtainP(A 0 T succeeds) = α -α K K -1 + O log N N . B.2 Proof of Theorem 3.2Proof. Let α ∈ (0, 1] a constant. For all w ∈ [α, 1] and B ≥ 0, we denote by φ B (w) the limit lim N →∞ P(A B t succeeds) for t = ⌊wN ⌋. We will prove by induction over B that this limit exists for all w ∈ [α, 1], is equal to the expression stated in the theorem, with u instead of α, and satisfiesP(A B t succeeds) = φ B (w) + O log N N, with the O term only depending on α and the other constants of the problem. In particular, the O term is independent of t. For B = 0, Lemma 3.1 gives immediately for any w ∈ [α, 1] and t = ⌊wN ⌋ thatP(A 0 t succeeds) = w -w K K -1 + O log N N = w K K -1 1 w K-1 -1 + O log N N .The O term depends on t, but using the inequalities α + o(1) ≤ t/N ≤ 1, it can be made only dependent on α. Let B ≥ 1 and assume the result is true for B -1. Lemma 3.1 and the induction hypothesis give for all w ∈ [α, 1] and t = ⌊wN ⌋, thatP(A B t succeeds) = w -w K K -1 + (K -1) N s=t t K s K+1 P(A B-1 s+1 succeeds) + O log N N = w -w K K -1 + (K -1) N s=t t K s K+1 φ B-1 s+1 N + O log N N + O log N N = w -w K K -1 + (K -1) (t/N ) K N N s=t φ B-1 s+1 N (s/N ) K+1 + O log N N, where we used that the O term in the induction hypothesis is independent of s and thatN s=t t K s K+1 φ B-1 s+1 N ≤ N s=T N K s K+1 ≤ 1 N N s=T 1 (s/N ) K+1 = O(1) .Finally, t/N = w + O(1/N ), and φ B-1 is, by the induction hypothesis, a continuously differentiable function on [α, 1], therefore, it holds by convergence properties of Riemann sums thatP(A B t succeeds) = w -w K K -1 + (K -1)(w K + O( 1 N )) 1 w φ B-1 (u) u K+1 du + O( 1 N ) + O log N N = w -w K K -1 + (K -1)w K 1 w φ B-1 (u) u K+1 du + O log N N ,where the O term depends on t and the constant parameters. Using that T = ⌊αN ⌋ ≤ t ≤ N , the O can be made dependent only on α and the other constant parameters. The limit φ B (w) = lim N →∞ P(A B ⌊wN ⌋ succeeds) therefore exists, and is equal toφ B (w) = w -w K K -1 + (K -1)w K 1 w φ B-1 (u) u K+1 du .u ∈ [α, 1] that φ B-1 (u) = u K K -1 B-1 b=0 1 u K-1 - b ℓ=0 log(1/u K-1 ) ℓ ℓ! , hence (K -1)w K 1 w φ B-1 (u) u K+1 du = 1 w B-1 b=0 1 u K - b ℓ=0 log(1/u K-1 ) ℓ ℓ!u du = Bw K 1 w du u K -w K B-1 b=0 b ℓ=0 1 ℓ! 1 w log(1/u K-1 ) ℓ u du = Bw K -1 (K -1)u K-1 1 w -w K B-1 b=0 b ℓ=0 1 ℓ! - log(1/u K-1 ) ℓ+1 (K -1)(ℓ + 1) 1 w = Bw K K -1 1 w K-1 -1 -w K B-1 b=0 b ℓ=0 log(1/w K-1 ) ℓ+1 (K -1)(ℓ + 1)! = Bw K K -1 1 w K-1 -1 -w K B b=1 b ℓ=1 log(1/w K-1 ) ℓ (K -1)ℓ! = w K K -1 B b=1 1 w K-1 -1 - b ℓ=1 log(1/w K-1 ) ℓ ℓ! = w K K -1 B b=1 1 w K-1 - b ℓ=0 log(1/w K-1 ) ℓ ℓ! ,and it follows thatφ B (w) = w K K -1 1 w K-1 -1 + B b=1 1 w K-1 - b ℓ=0 log(1/w K-1 ) ℓ ℓ! = w K K -1 B b=0 1 w K-1 - b ℓ=0 log(1/w K-1 ) ℓ ℓ! .In particular, this identity is true for w = α, which gives the wanted result.Infinite budget Taking the limit for B → ∞, we obtain that limB→∞ lim N →∞ P(A B ⌊αN ⌋ succeeds) = lim B→∞ φ B (w) = α K K -1 ∞ b=0 1 α K-1 - b ℓ=0 log(1/α K-1 ) ℓ ℓ! = α K K -1 ∞ b=0 ∞ ℓ=b+1 log(1/α K-1 ) ℓ ℓ! = α K K -1 ∞ ℓ=1 ℓ-1 b=0 log(1/α K-1 ) ℓ ℓ! = α K K -1 ∞ ℓ=1 log(1/α K-1 ) ℓ (ℓ -1)! = α K log(1/α K-1 ) K -1 ∞ ℓ=0 log(1/α K-1 ) ℓ ℓ! = α K log(1/α) • 1 α K-1 = α log(1/α) .Proof. Let α ∈ (0, 1) and T = ⌊αN ⌋. Lemma A.4 gives for all x > 0 thatB b=0 e x - b ℓ=0 x ℓ ℓ! ≥ xe x 1 - x B+1 (B + 1)! ,in particular, we obtain for x = log(1/α K-1 ) that limN →∞ P(A B T succeeds) = α K K -1 ∞ b=0 1 α K-1 - b ℓ=0 log(1/α K-1 ) ℓ ℓ! ≥ α K K -1 • log(1/α K-1 ) α K-1 1 - log(1/α K-1 ) B+1 (B + 1)! = α log(1/α) 1 - (K -1) B+1 log(1/α) B+1 (B + 1)! .Taking a threshold T = ⌊N/e⌋ gives limN →∞ P(A B ⌊N/e⌋ succeeds) ≥ 1 e 1 - (K -1) B+1 (B + 1)! .To achieve an asymptotic success probability of at least 1-ε e for some ε > 0, using the inequality m! ≥ e m e m , it suffices that K and B satisfy (K-1) B+1 e( B+1 e ) B+1 ≤ ε, which is equivalent toK ≤ 1 + B + 1 e (eε) 1 B+1 .C Static Double-threshold algorithm for two groupsWe first prove a recursion satisfied by U B N,t,k (2), which we use to prove the subsequent results in this section. Lemma C.1. For all B ≥ 0, t ∈ {⌊αN ⌋, . . . , ⌊βN ⌋ -1}, and k ∈ {1, 2}, U B N,t,k satisfiesU B N,t,k = λ N ⌊βN ⌋-1 s=t P(ρ 1 ≥ s, g * t-1 = k | C N ) + 1(B > 0) 1 -λ ⌊βN ⌋-1 s=t P(g * t-1 = k, ρ 1 = s, R s ̸ = 1 | C N )U B-1 N,s+1,2 + P(A B t (α, β) succeeds, g * t-1 = k, ρ 1 ≥ βN | C N ) + O 1 N .Assuming that ρ 1 = s ∈ {t, . . . , ⌊βN ⌋ -1}, the first sum corresponds to the success probability if R s = 1 and the algorithm selects the candidate x s . The terms of the second sum represent the success probability after using a comparison at step s but observing R t ̸ = 1, resulting in the rejection of the candidate. Therefore, the available budget at step s + 1 is B -1, and necessarily g * s = 2, because a comparison at step s can only occur if g s = 1 by definition of the algorithm. Hence, only the term U B-1 N,s+1,2 appears in the recursion, not U B-1 N,s+1,1 . Finally, the last term represents the probability of success if no comparison has been made before step ⌊βN ⌋ Proof. Let B ≥ 0. For all t ∈ {⌊αN ⌋, . . . , ⌊βN ⌋ -1) and k ∈ {1, 2}, it holds thatEQUATIONEQUATIONEQUATION)For all s ∈ {t, . . . , ⌊βN ⌋ -1}, by definition of Algorithm A B t (α, β), if ρ 1 = s and R s = 1 then the candidate x s is selected, and the algorithm succeeds if only if x s = x max . Moreover, the event {ρ 1 = s} is equivalent to {ρ 1 ≥ s, g s = 1, r s = 1}, hence the terms in (8) can be written asP(A B t (α, β) succeeds, g * t-1 = k,ρ 1 = s, R s = 1 | C N ) = P(x s = x max , g * t-1 = k, ρ 1 = s, R s = 1 | C N ) = P(x s = x max , g * t-1 = k, ρ 1 ≥ s, g s = 1 | C N ) = P(g s = 1 | C N ) N P(ρ 1 ≥ s, g * t-1 = k | C N ) = λ N + O 1 N 3 P(ρ 1 ≥ s, g * t-1 = k | C N ) ,where used for that the event {x s = x max } is independent of the group memberships, thus independent of C N , and that it is also independent of {ρ 1 ≥ s, g * t-1 = k}, because a realization of the latter event is determined only by the groups and relative ranks of the candidates {x 1 , . . . , x s-1 }. For the last equality, we used Lemma A.3.Secondly, in the case where ρ 1 = s and R s ̸ = 1, if B = 0 then the algorithm selects candidate x s which is not the best overall, hence its probability of succeeding is zero. If B ≥ 1, the algorithm makes a comparison but then rejects the candidate. Moreover, for s ∈ [t, βN ], if ρ 1 = s then necessarily g s = 1, and having R s ̸ = 1 implies that g * s = 2. The success probability of A B t (α, β) given that ρ 1 = s, R s ̸ = 1 is the same as the success probability of A B-1 s+1 (α, β) given that g * s = 2. Therefore, the terms of (9) satisfyP(A B t (α, β) succeeds, g * t-1 = k, ρ 1 = s, R s ̸ = 1 | C N ) = 1(B > 0) P(g * t-1 = k, ρ 1 = s, R s ̸ = 1 | C N )P(A B t (α, β) succeeds | g * t-1 = k, ρ 1 = s, R s ̸ = 1, C N ) = 1(B > 0) P(g * t-1 = k, ρ 1 = s, R s ̸ = 1 | C N )P(A B-1 s+1 (α, β) succeeds | g * s = 2, C N ) = 1(B > 0) P(g * t-1 = k, ρ 1 = s, R s ̸ = 1 | C N ) P(A B-1 s+1 (α, β) succeeds, g * s = 2 | C N ) P(g * s = 2 | C N ) = 1(B > 0) P(g * t-1 = k, ρ 1 = s, R s ̸ = 1 | C N ) U B-1 N,s+1,2 1 -λ + O( 1 N 2 ), where we used again Lemma A.3. Given that the O terms are independent of s, We deduce thatU B N,t,k = λ N + O 1 N 3 ⌊βN ⌋-1 s=t P(ρ 1 ≥ s, g * t-1 = k | C N ) + 1(B > 0) 1 1 -λ + O 1 N 2 ⌊βN ⌋-1 s=t P(g * t-1 = k, ρ 1 = s, R s ̸ = 1 | C N )U B-1 N,s+1,2 + P(A B t (α, β) succeeds, g * t-1 = k, ρ 1 ≥ βN | C N ) = λ N ⌊βN ⌋-1 s=t P(ρ 1 ≥ s, g * t-1 = k | C N ) + 1(B > 0) 1 -λ ⌊βN ⌋-1 s=t P(g * t-1 = k, ρ 1 = s, R s ̸ = 1 | C N )U B-1 N,s+1,2 + P(A B t (α, β) succeeds, g * t-1 = k, ρ 1 ≥ βN | C N ) + O 1 N .In the following two lemmas, we compute the probabilities appearing in Lemma C.1 for all s ∈ {t, . . . , ⌊βN ⌋ -1 and k ∈ {1, 2}Lemma C.2. Let ⌊αN ⌋ ≤ t ≤ s < ⌊βN ⌋, and consider a run of Algorithm A B t (α, β), then it holds thatP(ρ 1 ≥ s, g * t-1 = 1 | C N ) = λt (1 -λ)t + λs + O log N N P(ρ 1 ≥ s, g * t-1 = 2 | C N ) = (1 -λ)t 2 ((1 -λ)t + λs)s + O log N N .Proof. Since there are only 2 groups, the event g * t-1 = 1 is equivalent to max G 2 t-1 < max G 1 t-1 . For s ∈ {t, . . . , ⌊βN ⌋}, Algorithm A B t (α, β) only makes a comparison (or stops in the case of B = 0) at step s only if g s = 1 and r s = 1. Therefore, ρ 1 ≥ s if and only if no candidate belonging to G 1 t:s-1 surpasses the maximum value observed in G 1 t-1P(ρ 1 ≥ s, g * t-1 = 1 | C N ) = P(max G 1 t:s-1 < G 1 t-1 , max G 2 t-1 < max G 1 t-1 | C N ) = P(max(G 1 t:s-1 ∪ G 2 t-1 ) < G 1 t-1 | C N ) = E |G 1 t-1 | |G 1 t-1 | + |G 1 t:s-1 | + |G 2 t-1 | C N = E |G 1 t-1 | t -1 + |G 1 t:s-1 | C N = λt + O( √ N log N ) t + λ(s -t) + O( √ N log N ) = λt (1 -λ)t + λs + O log N N .For the case g * t = 2, we obtainP(ρ 1 ≥ s, g * t-1 = 2 | C N ) = P(max G 1 t:s-1 < G 1 t-1 , max G 1 t-1 < max G 2 t-1 | C N ) = max G 1 t:s-1 < G 1 t-1 < max G 2 t-1 | C N ) = E |G 2 t-1 | |G 1 t-1 | + |G 1 t:s-1 | + |G 2 t-1 | • |G 1 t-1 | |G 1 t:s-1 | + |G 1 t-1 | C N = E |G 2 t-1 | t -1 + |G 1 t:s-1 | • |G 1 t-1 | |G 1 s-1 | C N = (1 -λ)t + O( √ N log N ) t + λ(s -t) + O( √ N log N ) • λt + O( √ N log N ) λs + O( √ N log N ) = (1 -λ)t 2 ((1 -λ)t + λs)s + O log N N .Lemma C.3. Let ⌊αN ⌋ ≤ t ≤ s < ⌊βN ⌋, and consider a run of Algorithm A B t (α, β), thenP(ρ 1 = s, R s ̸ = 1, g * t-1 = 1 | C N ) = λ 2 (1 -λ)(s -t)t ((1 -λ)t + λs) 2 s + O log N N 3 P(ρ 1 = s, R s ̸ = 1, g * t-1 = 2 | C N ) = (1 -λ) (1 -λ) 2 t + λ(2 -λ)s t 2 ((1 -λ)t + λs) 2 s 2 + O log N N 3 .Proof. For Algorithm A B t (α, β) and s ∈ {t, . . . , ⌊βN ⌋ -1}, ρ 1 = s if and only if x s is the first element in G 1 since step t for which r s = 1, thusρ 1 = s ⇐⇒ g s = 1 and max G 1 t:s-1 < max G 1 t-1 < x s . Furthermore, Lemma A.3 gives that P(g s = 1 | C N ) = P(g s = 1) + O(1/N ) = λ + O(1/N ). Therefore, it holds that P(ρ 1 = s, R s ̸ = 1, g * t-1 = 1 | C N ) = P(g s = 1 , max G 1 t:s-1 < max G 1 t-1 < x s , x s < max G 2 s-1 , max G 2 t-1 < max G 1 t-1 | C N ) = P(g s = 1 | C N )P(max G 1 t:s-1 < max G 1 t-1 < x s < max G 2 t:s-1 , max G 2 t-1 < max G 1 t-1 | C N ) = P(g s = 1 | C N )P(max(G 1 t:s-1 ∪ G 2 t-1 ) < max G 1 t-1 < x s < max G 2 t:s-1 | C N ) = (λ + O( 1 N ))E |G 2 t:s-1 | |G 1 t:s-1 |+|G 2 t-1 |+|G 1 t-1 |+1+|G 2 t:s-1 | • 1 |G 1 t:s-1 |+|G 2 t-1 |+|G 1 t-1 |+1 • |G 1 t-1 | |G 1 t:s-1 |+|G 2 t-1 |+|G 1 t-1 | C N = (λ + O( 1 N ))E |G 2 t:s-1 | s • 1 t + |G 1 t:s-1 | • |G 1 t-1 | t -1 + |G 1 t:s-1 | C N = (λ + O( 1 N )) (1 -λ)(s -t) + O( √ N log N ) s(t + λ(s -t) + O( √ N log N )) • λt + O( √ N log N ) t + λ(s -t) + O( √ N log N ) = λ 2 (1 -λ)(s -t)t ((1 -λ)t + λs) 2 s + O log N N 3.On the other hand, in the case where g * t-1 = 2, we obtainP(ρ 1 = s, R s ̸ = 1, g * t-1 = 2 | C N ) = P(g s = 1 , max G 1 t:s-1 < max G 1 t-1 < x s , x s < max G 2 s-1 , max G 1 t-1 < max G 2 t-1 | C N ) = P(g s = 1 | C N )P(max G 1 t:s-1 < max G 1 t-1 < x s < max G 2 s-1 , max G 1 t-1 < max G 2 t-1 | C N ) = P(g s = 1 | C N )P(a < b < x s < max(c, d) , b < c | C N ) , where a = max G 1 t:s-1 , b = max G 1 t-1 , c = max G 2 t-1 and d = max G 2 t:s-1 . Let us denote by E the event {a < b < x s < max(c, d)} ∩ {b < c}. It holds that E ∩ {c < d} = {a < b < x s < max(c, d)} ∩ {b < c} ∩ {c < d} = {a < b < c < x s < d} ∪ {a < b < x s < c < d} = {a < b < c < x s < d} ∪ {a < b < x s < c} ∩ {c < d} , E ∩ {d < c} = {a < b < x s < max(c, d)} ∩ {b < c} ∩ {d < c} = {a < b < x s < c} ∩ {d < c} ,which yieldsE = E ∩ {c < d} E ∩ {d < c} = {a < b < c < x s < d} ∪ {a < b < x s < c} ∩ {c < d} ∪ {a < b < x s < c} ∩ {d < c} = {a < b < c < x s < d} ∪ {a < b < x s < c} .The two events above are disjoint, and we haveP(a < b < c < x s < d | C N ) = P(max G 1 t:s-1 < max G 1 t-1 < max G 2 t-1 < x s < G 2 t:s-1 | C N ) = E |G 2 t:s-1 | |G 1 t:s-1 |+|G 1 t-1 |+|G 2 t-1 |+1+|G 2 t:s-1 | • 1 |G 1 t:s-1 |+|G 1 t-1 |+|G 2 t-1 |+1 • |G 2 t-1 | |G 1 t:s-1 |+|G 1 t-1 |+|G 2 t-1 | • |G 1 t-1 | |G 1 t:s-1 |+|G 1 t-1 | • | C N = E |G 2 t:s-1 | s • 1 t + |G 1 t:s-1 | • |G 2 t-1 | t -1 + |G 1 t:s-1 | • |G 1 t-1 | |G 1 s-1 | C N = (1 -λ)(s -t) + O( √ N log N ) s(t + λ(s -t) + O( √ N log N )) • (1 -λ)t + O( √ N log N ) t + λ(s -t) + O( √ N log N ) • λt + O( √ N log N ) λs + O( √ N log N ) = (1 -λ) 2 (s -t)t 2 ((1 -λ)t + λs) 2 s 2 + O log N N 3.The probability of the second event isP(a < b < x s < c | C N ) = P(max G 1 t:s-1 < max G 1 t-1 < x s < max G 2 t-1 | C N ) = E |G 2 t-1 | |G 1 t:s-1 |+|G 1 t-1 |+1+|G 2 t-1 | • 1 |G 1 t:s-1 |+|G 1 t-1 |+1 • |G 1 t-1 | |G 1 t:s-1 |+|G 1 t-1 | C N = E |G 2 t-1 | t + |G 1 t:s-1 | • 1 |G 1 s-1 | + 1 • |G 1 t-1 | |G 1 s-1 | C N = (1 -λ)t + O( √ N log N ) t + λ(s -t) + O( √ N log N ) • 1 λs + O( √ N log N ) • λt + O( √ N log N ) λs + O( √ N log N ) = (1 -λ)t 2 λ((1 -λ)t + λs)s 2 + O log N N 3 . Finally, Lemma A.3 shows that P(g s = 1 | C N ) = λ + O(1/N 2 ), and we deduceP(ρ 1 = s, R s ̸ = 1, g * t-1 = 2 | C N ) = λP(E | C N ) + O( 1 N 2 ) = λP(a < b < c < x s < d | C N ) + λP(a < b < x s < c | C N ) + O( 1 N 2 ) = λ(1 -λ) 2 (s -t)t 2 ((1 -λ)t + λs) 2 s 2 + λ(1 -λ)t 2 λ((1 -λ)t + λs)s 2 + O log N N 3 = (1 -λ)t 2 ((1 -λ)t + λs) 2 s 2 (λ(1 -λ)(s -t) + (1 -λ)t + λs) + O log N N 3 = (1 -λ)t 2 ((1 -λ)t + λs) 2 s 2 (1 -λ) 2 t + λ(2 -λ)s + O log N N 3 . Lemma C.4. Let ⌊αN ⌋ ≤ t < ⌊βN ⌋,and consider a run of Algorithm A B t (α, β), thenP(A B t (α, β) succeeds, ρ 1 ≥ βN, g * t-1 = 1 | C N ) = t βN U B N,⌊βN ⌋,1 + λ(βN -t)t ((1 -λ)t + λβN )βN U B N,⌊βN ⌋,2 + O log N N , P(A B t (α, β) succeeds, ρ 1 ≥ βN, g * t-1 = 2 | C N ) = t 2 ((1 -λ)t + λβN )βN U B N,⌊βN ⌋,2 + O log N N .Proof. Since Algorithm A B t (α, β) is memoryless, if it does not stop before step ⌊βN ⌋, then its success probability is the same as that of A B ⌊βN ⌋ (α, β) = A B 0 (β, β), which has the same threshold β for both groups, if it is in the same state (g * ⌊βN ⌋-1 , |G 1 ⌊βN ⌋ |). In all the proof, ρ 1 is relative to Algorithm A B t (α, β), not A B 0 (β, β). It holds thatP(A B t (α, β) succeeds, ρ 1 ≥ βN, g * t-1 = 1 | C N ) = ℓ∈{1,2} P(A B t (α, β) succeeds, ρ 1 ≥ βN, g * t-1 = 1, g * ⌊βN ⌋-1 = ℓ | C N ) = ℓ∈{1,2} P(ρ 1 ≥ βN, g * t-1 = 1, g * ⌊βN ⌋-1 = ℓ | C N )) × P(A B t (α, β) succeeds | ρ 1 ≥ βN, g * t-1 = 1, g * ⌊βN ⌋-1 = ℓ, C N ) = ℓ∈{1,2} P(ρ 1 ≥ βN, g * t-1 = 1, g * ⌊βN ⌋-1 = ℓ | C N )P(A B 0 (β, β) succeeds | g * ⌊βN ⌋-1 = ℓ, C N ) = ℓ∈{1,2} P(ρ 1 ≥ βN, g * t-1 = 1, g * ⌊βN ⌋-1 = ℓ | C N ) P(A B 0 (β, β) succeeds, g * ⌊βN ⌋-1 = ℓ | C N ) P(g * ⌊βN ⌋-1 = ℓ | C N ) = ℓ∈{1,2} P(ρ 1 ≥ βN, g * t-1 = 1, g * ⌊βN ⌋-1 = ℓ | C N ) U B N,⌊βN ⌋,ℓ P(g * ⌊βN ⌋-1 = ℓ) + O( 1 N 2 ), where we used Lemma A.3 and the definition (2) of U B N,s,ℓ . Let us now compute the probability of the event {ρ 1 ≥ βN, g * t-1 = 1, g * ⌊βN ⌋-1 = ℓ} conditional to C N . For ℓ = 1, we haveP(ρ 1 ≥ βN, g * t-1 = 1, g * ⌊βN ⌋-1 = 1 | C N ) = P(max G 1 t:⌊βN ⌋-1 < max G 1 t-1 , max G 2 t-1 < max G 1 t-1 , max G 2 ⌊βN ⌋-1 < max G 1 ⌊βN ⌋-1 | C N ) = P(max x 1:⌊βN ⌋-1 ∈ G 1 t-1 | C N ) = E |G 1 t-1 | ⌊βN ⌋ -1 C N = λt + O( √ N log N ) βN + O(1) = λt βN + O log N N.For ℓ = 2, we first compute the followingP(ρ 1 ≥ βN, g * t-1 = 1 | C N ) = P(max G 1 t:⌊βN ⌋-1 < max G 1 t-1 , max G 2 t-1 < max G 1 t-1 | C N ) = P(max(G 1 t:⌊βN ⌋-1 ∪ G 2 t-1 ) < max G 1 t-1 | C N ) = E |G 1 t-1 | |G 1 t:⌊βN ⌋-1 | + |G 2 t-1 | + |G 1 t-1 | C N = λt + O( √ N log N ) t + λ(βN -t) + O( √ N log N ) = λt (1 -λ)t + λβN + O log N N ,and it follows thatP(ρ 1 ≥ βN, g * t-1 = 1, g * ⌊βN ⌋-1 = 2 | C N ) = P(ρ 1 ≥ βN, g * t-1 = 1 | C N ) -P(ρ 1 ≥ βN, g * t-1 = 1, g * ⌊βN ⌋-1 = 1 | C N ) = λt (1 -λ)t + λβN - λt βN + O log N N = λ(1 -λ)(βN -t)t ((1 -λ)t + λβN )βN + O log N N .All in all, we deduce thatP(A B t (α, β) succeeds, ρ 1 ≥ βN, g * t-1 = 1 | C N ) = λt βN + O log N N U B N,⌊βN ⌋,1 λ + O( 1 N 2 ) + λ(1 -λ)(βN -t)t ((1 -λ)t + λβN )βN + O log N N U B N,⌊βN ⌋,2 1 -λ + O( 1 N 2 ) = t βN + O log N N U B N,⌊βN ⌋,1 + λ(βN -t)t ((1 -λ)t + λβN )βN + O log N N U B N,⌊βN ⌋,2 = t βN U B N,⌊βN ⌋,1 + λ(βN -t)t ((1 -λ)t + λβN )βN U B N,⌊βN ⌋,2 + O log N N .On the other hand, if g * t-1 = 2 and ρ 1 ≥ βN , then necessarily g* ⌊βN ⌋-1 = 2, because no candidate in G 1 up to step ⌊βN ⌋ -1 surpasses max G 1 t-1 , which is less than max G 2 t-1 . Therefore P(A B t (α, β) succeeds, ρ 1 ≥ βN, g * t-1 = 2 | C N ) = P(ρ 1 ≥ βN, g * t-1 = 2 | C N )P(A B t (α, β) | ρ 1 ≥ βN, g * t-1 = 2, C N ) = P(max G 1 t:⌊βN ⌋-1 < max G 1 t-1 < max G 2 t-1 | C N )P(A B 0 (β, β) | g * ⌊βN ⌋-1 = 2, C N ) = E |G 2 t-1 | t -1 + |G 1 t:⌊βN ⌋-1 | • |G 1 t-1 | |G 1 ⌊βN ⌋-1 | C N P(A B 0 (β, β), g * ⌊βN ⌋-1 = 2 | C N ) P(g * ⌊βN ⌋-1 = 2 | C N ) = (1 -λ)t + O( √ N log N ) t + λ(βN -t) + O( √ N log N ) • λt + O( √ N log N ) λβN + O( √ N log N ) • U B N,⌊βN ⌋,2 1 -λ + O( 1 N 2 ) = t 2 ((1 -λ)t + λβN )βN U B N,⌊βN ⌋,2 + O log N N .In the following lemma, we compute the exact limit of U B N,⌊βN ⌋,k when the number of candidates goes to infinity. Lemma C.5. For all B ≥ 0 and k ∈ {1, 2},U B N,⌊βN ⌋,k = λ k β 2 B b=0 1 β - b ℓ=0 log(1/β) ℓ ℓ! + O log N N . Proof. By definition (2) of U B N,t,k , we have U B N,t,k = P(A B ⌊βN ⌋ (α, β) succeeds, g * t-1 = k | C N ) , and A B ⌊βN ⌋ (α, β) is simply the single-threshold algorithm with threshold βN and budget B. Let T = ⌊βN ⌋. As in the proof of Lemma 3.1, we decompose the success probability of A B ⌊βN ⌋ as followsU B N,T,k = P(A B T (α, β) succeeds, g * T -1 = k | C N ) = N t=T ℓ∈{1,2} P(A B T (α, β) succeeds, ρ 1 = t, g t = ℓ, g * T -1 = k | C N ) = N t=T ℓ∈{1,2} P(A B T (α, β) succeeds, ρ 1 = t, R t = 1, g t = ℓ, g * T -1 = k | C N ) + P(A B T (α, β) succeeds, ρ 1 = t, R t ̸ = 1, g t = ℓ, g * T -1 = k | C N ) .The terms appearing in the sums above were computed in the proof of Lemma 3.1. It follows respectively from ( 4) and ( 7), with K = 2, thatP(A B T (α, β) succeeds, ρ 1 = t, R t = 1, g t = ℓ, g * T -1 = k | C N ) = λ ℓ λ k N (T /t) 2 + O log N N 3 , P(A B T (α, β) succeeds, ρ 1 = t, R t ̸ = 1, g t = ℓ, g * T -1 = k | C N ) = T 2 t 3 + O log N N 3 1(B > 0, k ̸ = ℓ) U B-1 N,t+1,k ,where the O terms are independent of t, they only depend on β. Therefore,U B N,T,k = 1 + O log N N N t=T ℓ∈{1,2} λ ℓ λ k N (T /t) 2 + T 2 t 3 1(B > 0, k ̸ = ℓ) U B-1 N,t+1,k = 1 + O log N N N t=T λ k N (T /t) 2 + T 2 t 3 1(B > 0) U B-1 N,t+1,k.The first sum can easily be computedN t=T λ k N (T /t) 2 = λ k (T /N ) 2 N N t=T 1 (t/N ) 2 = λ k (β 2 + O( 1 N )) 1 β du u 2 + O( 1 N ) = λ k β(1 -β) + O( 1 N ) .Therefore,U B N,T,k = 1 + O log N N λ k β(1 -β) + 1(B > 0) N t=T T 2 t 3 U B-1 N,t+1,k + O( 1 N ) = λ k β(1 -β) + 1(B > 0) N t=T T 2 t 3 U B-1 N,t+1,k + O log N N .Dividing by λ k yieldsλ -1 k U B N,T,k = β(1 -β) + 1(B > 0) N t=T T 2 t 3 λ -1 k U B-1 N,t+1,k + O log N N .thus the double-indexed sequence (λ -1 k U b N,t,k ) b,t satisfies the same recursion and initial condition as (P(A b t (0, 0) succeeds)) b,t (see proof of Lemma 3.1) with β instead of w and K = 2. Therefore, we deduce immediately that:λ -1 k U B N,T,k = β 2 B b=0 1 β - b ℓ=0 log(1/β) ℓ ℓ! + O log N N . C.3 Proof of Lemma 4.1 Proof. Using Lemmas C.1, C.2, C.3 and C.4 for k = 2, we obtain for all t ∈ {⌊αN ⌋, . . . , ⌊βN ⌋ -1} U B N,t,2 = λ N ⌊βN ⌋-1 s=t (1 -λ)t 2 ((1 -λ)t + λs)s + O log N N + 1(B > 0) 1 -λ ⌊βN ⌋-1 s=t (1 -λ) (1 -λ) 2 t + λ(2 -λ)s t 2 ((1 -λ)t + λs) 2 s 2 + O log N N 3 U B-1 N,s+1,2 + t 2 ((1 -λ)t + λβN )βN U B N,⌊βN ⌋,2 + O log N N .The O terms inside the sums depend on the ratios t/N and s/N , but using that α ≤ t/N ≤ s/N ≤ 1, it can be made only dependent on α and the other constants of the problem. Moreover, Thus we can writeU B N,t,2 = λ(1 -λ)t 2 N ⌊βN ⌋-1 s=t 1 ((1 -λ)t + λs)s + 1(B > 0) t 2 ⌊βN ⌋-1 s=t (1 -λ) 2 t + λ(2 -λ)s ((1 -λ)t + λs) 2 s 2 U B-1 N,s+1,2 + t 2 ((1 -λ)t + λβN )βN U B N,⌊βN ⌋,2 + O log N N = λ(1 -λ)( t N ) 2 1 N ⌊βN ⌋-1 s=t 1 ((1 -λ) t N + λ s N ) s N + 1(B > 0) ( t N ) 2 1 N ⌊βN ⌋-1 s=t (1 -λ) 2 t N + λ(2 -λ) s N ((1 -λ) t N + λ s N ) 2 ( s N ) 2 U B-1 N,s+1,2 + (t/N ) 2 ((1 -λ) t N + λβ)β U B N,⌊βN ⌋,2 + O log N N .Taking t = ⌊wN ⌋ = wN + O(1) and using Riemann sum convergence properties yieldsEQUATIONOn the other hand,(t/N ) 2 ((1 -λ) t N + λβ)β = w 2 ((1 -λ)w + λβ)β + O( 1 N ) ,and Lemma C.5 gives for k = 2 that φ B 2 (α, β; β) exists, its expression isEQUATIONand it satisfiesEQUATIONUsing this equality, we will prove by induction over B ≥ 0 that, for all w ∈ [α, β], the limit φ B (α, β; w) := lim N →∞ U B N,⌊wN ⌋,2 exists, is continuous, and satisfiesU B N,⌊wN ⌋,2 = φ B 2 (α, β; w) + O log N N .Initialization. For B = 0 and w ∈ [α, β], (13) gives immediatelyU B N,⌊wN ⌋,2 = -λw log (1 -λ) w β + λ + w 2 ((1 -λ)w + λβ)β φ B 2 (α, β; β) + O log N N . (14) Induction. Let B ≥ 1, w ∈ [α, β], and assume that U B-1 N,⌊uN ⌋,2 = φ B 2 (α, β; u) + O log N N for all u ∈ [α, β],where the O does not depend on u. Using this hypothesis for u = s+1 N , with s ∈ {t, . . . , ⌊βN ⌋ -1}, along with te continuity of φ B-1 2 (α, β; •) and Riemann sums convergence properties, yieldsw 2 N ⌊βN ⌋-1 s=⌊wN ⌋ (1 -λ) 2 w + λ(2 -λ) s N ((1 -λ)w + λ s N ) 2 ( s N ) 2 U B-1 N,s+1,2 = w 2 N ⌊βN ⌋-1 s=⌊wN ⌋ (1 -λ) 2 w + λ(2 -λ) s N ((1 -λ)w + λ s N ) 2 ( s N ) 2 φ B-1 2 (α, β; s+1 N ) + O log N N = w 2 β w (1 -λ) 2 w + λ(2 -λ)u ((1 -λ)w + λu) 2 u 2 φ B-1 2 (α, β; u)du + O log N N.Therefore, we deduce by (13) thatU B N,⌊wN ⌋,2 = -λw log (1 -λ) w β + λ + w 2 β w (1 -λ) 2 w + λ(2 -λ)u ((1 -λ)w + λu) 2 u 2 φ B-1 2 (α, β; u)du + w 2 ((1 -λ)w + λβ)β φ B 2 (α, β; β) + O log N N . This proves that U B N,⌊wN ⌋,2 = φ B 2 (α, β; w) + O log N N, whereφ B 2 (α, β; w) = -λw log (1 -λ) w β + λ + w 2 β w (1 -λ) 2 w + λ(2 -λ)u ((1 -λ)w + λu) 2 u 2 φ B-1 2 (α, β; u)du + w 2 ((1 -λ)w + λβ)β φ B 2 (α, β; β) ,where the expression of φ B 2 (α, β; β) is given in (12).Proof. Using Lemmas C.1, C.3, C.2 and C.4 for k = 2, we obtain for all t ∈ {⌊αN ⌋, . . . , ⌊βN ⌋ -1}U B N,t,1 = λ N ⌊βN ⌋-1 s=t λt (1 -λ)t + λs + O log N N + 1(B > 0) 1 -λ ⌊βN ⌋-1 s=t λ 2 (1 -λ)(s -t)t ((1 -λ)t + λs) 2 s + O log N N 3 U B-1 N,s+1,2 + t βN U B N,⌊βN ⌋,1 + λ(βN -t)t ((1 -λ)t + λβN )βN U B N,⌊βN ⌋,2 + O log N N = λ 2 (t/N ) N ⌊βN ⌋-1 s=t 1 (1 -λ) t N + λ s N + 1(B > 0) λ 2 (t/N ) N ⌊βN ⌋-1 s=t s N -t N ((1 -λ) t N + λ s N ) 2 s N U B-1 N,s+1,2 + t/N β U B N,⌊βN ⌋,1 + λ(β -t N ) t N ((1 -λ) t N + λβ)β U B N,⌊βN ⌋,2 + O log N N .Consider in the following t = ⌊wN ⌋ = wN + O(1). Using Riemann sums convergence properties, we haveλ 2 (t/N ) N ⌊βN ⌋-1 s=t 1 (1 -λ) t N + λ s N = λ 2 w β w du (1 -λ)w + λu + O( 1 N ) = λw [log((1 -λ)w + λu)] β w + O( 1 N ) = λw log 1 -λ + λ β w + O( 1 N ) .Since U b N,s,k ≤ 1 for all b, s, k, and t = wN + O(1), as in the proof of Lemma 4.1, we obtainU B N,⌊wN ⌋,1 = λw log 1 -λ + λ β w + O( 1 N ) + 1(B > 0) λ 2 w N ⌊βN ⌋-1 s=⌊wN ⌋ s N -w ((1 -λ)w + λ s N ) 2 s N U B-1 N,s+1,2 + O( 1 N ) + w β U B N,⌊βN ⌋,1 + λ(β -w)w ((1 -λ)w + λβ)β U B N,⌊βN ⌋,2 + O log N N = λw log 1 -λ + λ β w + 1(B > 0) λ 2 w N ⌊βN ⌋-1 s=⌊wN ⌋ s N -w ((1 -λ)w + λ s N ) 2 s N U B-1 N,s+1,2 + w β φ B 1 (α, β; β) + λ(β -w)w ((1 -λ)w + λβ)β φ B 2 (α, β; β) + O log N N, where we used Lemma C.5 in the last inequality, which guarantees thatEQUATIONNow, we will prove by induction overB that U B N,⌊wN ⌋,1 = φ B 1 (α, β; w) + O log N Nfor allw ∈ [α, β], with φ B 1 (α, β; •) a continuous function satisfying the recursion stated in the Lemma. Initialization For B = 0, (15) yields immediately for all w ∈ [α, β]U B N,⌊wN ⌋,1 = λw log 1 -λ + λ β w + λw (1 -λ)w + λβ φ B (α, β; β) + O log N N.Induction Let B ≥ 1, and assume that U B-1 N,⌊uN ⌋,1 = φ B-11 (α, β; u) + O log N N for all u ∈ [α, β],and that φ B 1 (α, β; •) is continuous. Consequently, using Riemann sums convergence properties, it holds for all w ∈ [α, β] thatλ 2 w N ⌊βN ⌋-1 s=⌊wN ⌋ s N -w ((1 -λ)w + λ s N ) 2 s N U B-1 N,s+1,2 = λ 2 w N ⌊βN ⌋-1 s=⌊wN ⌋ s N -w ((1 -λ)w + λ s N ) 2 s N φ B-1 2 (α, β; s+1 N ) + O log N N = λ 2 w N ⌊βN ⌋-1 s=⌊wN ⌋ s N -w ((1 -λ)w + λ s N ) 2 s N φ B-1 2 (α, β; s+1 N ) + O log N N = λ 2 w β w (u -w)φ B-1 2 (α, β; u) ((1 -λ)w + λu) 2 u du + O log N N, thus, we have by substituting into (15)U B N,⌊wN ⌋,1 = λw log 1 -λ + λ β w + λw (1 -λ)w + λβ φ B (α, β; β) + λ 2 w β w (u -w)φ B-1 2 (α, β; u) ((1 -λ)w + λu) 2 u du + O log N N = φ B 1 (α, β; w) + O log N N .C.5 Proof of Corollary 4.3.1Proof. Assume that λ ≥ 1/2. For any thresholds 0 < α ≤ β ≤ 1 Theorem 4.3 yields lim N →∞ P(A B (α, β) succeeds) ≥ λα log β α + αβS B (β) .We will now determine thresholds maximizing this lower bound. For a fixed β, we have∂ ∂α λα log β α + αβS B (β) ≥ 0 ⇐⇒ λ log β α -λ + βS B (β) ≥ 0 ⇐⇒ λ log α β ≤ βS B (β) -λ ⇐⇒ α ≤ β e exp β λ S B (β) .This proves that, for fixed β the lower bound λα logβ α + αβS B (β) is maximized on [0, β] for α = min(β, β e exp( β λ S B (β))) = h B (β).With this choice of α, the optimal choice of β is the one maximizing the mapping β → λh B (β) logβ h B (β) + h B (β)βS B (β).In particular, for B = 0, we obtain α0 = λ exp( 1 λ -2) and β0 = λ. They guarantee an asymptotic success probability of at least λ 2 exp( 1 λ -2). Given that the sequence (S B (w)) B is non-decreasing for all w ∈ (0, 1], it holds for all B ≥ 0 that limN →∞ P(A B (α B , βB ) succeeds) ≥ λα B log βB αB + αB βB S B ( βB ) = max α≤β λα log β α + αβS B (β) ≥ max α≤β λα log β α + αβS 0 (β) = λα 0 log β0 α0 + α0 β0 S 0 ( β0 ) = λ 2 exp( 1 λ -2) ≥ 1 e -( 4 e -1)λ(1 -λ) .On the other hand, taking equal thresholds α = β = 1 e then using Corollary 3.2.1 with K = 2 gives limN →∞ P(A B (α B , βB ) succeeds) ≥ max α≤β λα log β α + αβS B (β) ≥ S B (1/e) e 2≥ 1 e -1 e(B + 1)! .Thus, we deduce that limN →∞ P(A B (α B , βB ) succeeds) ≥ 1 e -min 1 e(B + 1)! , ( 1 e -1)λ(1 -λ) .C.6 Proof of Theorem 4.3Proof. By Lemmas A.3, 4.1 and 4.2, The success probability of Algorithm A(α, β) B can be written asP(A B (α, β) succeeds) = P(A B ⌊αN ⌋ (α, β) succeeds | C N ) + O( 1 N 2 ) = P(A B ⌊αN ⌋ (α, β) succeeds, g * ⌊αN ⌋-1 = 1 | C N ) + P(A B ⌊αN ⌋ (α, β) succeeds, g * ⌊αN ⌋-1 = 2 | C N ) + O( 1 N 2 ) = U B N,⌊αN ⌋,1 + U B N,⌊αN ⌋,2 + O( 1 N 2 ) = φ B 1 (α, β; α) + φ B 2 (α, β; α) + O log N N = λα log 1 -λ + λ β α + λαβ 2 (1 -λ)α + λβ B b=0 1 β - b ℓ=0 log(1/β) ℓ ℓ! + 1(B > 0) λ 2 α β α (u -α)φ B-1 2 (α, β; u) ((1 -λ)α + λu) 2 u du -λα log (1 -λ) α β + λ + (1 -λ)βα 2 (1 -λ)α + λβ B b=0 1 β - b ℓ=0 log(1/β) ℓ ℓ! + 1(B > 0) α 2 β α (1 -λ) 2 α + λ(2 -λ)u ((1 -λ)α + λu) 2 u 2 φ B-1 2 (α, β; u)du + O log N N, then, regrouping the terms yieldsP(A B (α, β) succeeds) = λα log 1 -λ + λ β α -λα log (1 -λ) α β + λ + αβ (1 -λ)α + λβ (λβ + (1 -λ)α) B b=0 1 β - b ℓ=0 log(1/β) ℓ ℓ! + 1(B > 0) α β α λ 2 (1 -α u ) + α u (1 -λ) 2 α u + λ(2 -λ) φ B-1 2 (α, β; u)du ((1 -λ)α + λu) 2 + O log N N .Finally, observing that(1 -λ) 2 α u + λ(2 -λ) = (1 -λ) 2 α 2 u 2 + 2λ(1 -λ) α u + λ 2 = 1 u 2 (1 -λ)α + λu 2 ,we deduce the resultP(A B (α, β) succeeds) = λα log β α + αβ B b=0 1 β - b ℓ=0 log(1/β) ℓ ℓ! + 1(B > 0) α β α φ B-1 2 (α, β; u)du u 2 + O log N N ,In this section, we derive an optimal memoryless algorithm employing a dynamic programming approach. We analyze the state transitions depending on the algorithm's actions and the associated success probabilities for each state. Unlike previous sections, our study here is not asymptotic. Therefore, we do not rely on estimating the number of candidates in each group using concentration inequalities. Instead, we consider the exact number of candidates in each group as a parameter for decision-making at each step.(t, B t , |G 1 t-1 |), since |G 2 t-1 | = t -1 -|G 1 t-1 |.The state of the algorithm, which fully determines its success probability, is given by the tuple (t, B t , |G 1 t-1 |, g * t-1 ). However, g * t-1 is not known to the algorithm, hence it must make decisions relying on the limited information it has, to maximize the expected success probability, where the expectation is taken over g * t-1 .For any memory-less algorithm A, we denote by S t (A) its state at step t, which is a tuple (t, b, m, ℓ).Here, t -1 represents the count of previously rejected candidates, b ≥ 0 denotes the available budget, m < t indicates the number of prior candidates from group G 1 , and ℓ ∈ {1, 2} is the group containing the best-seen candidate so far.To examine the state transitions of the algorithm, it is imperative to first understand the distribution of the new observations at any given step t, depending on S t (A). While the group membership g t of candidate x t is independent of S t (A), both r t and R t are contingent on it.Lemma D.2. For any memory-less algorithm A and state (t, m, b, ℓ), denoting by k = 3 -ℓ the group index different from ℓ, it holds thatP(r t = 1 | S t (A) = (t, m, b, ℓ), g t = ℓ) = 1 t P(r t = 1 | S t (A) = (t, m, b, ℓ), g t = k) = |G k t-1 | + t t(|G k t-1 | + 1) P(R t = 1 | S t (A) = (t, m, b, ℓ), g t = ℓ, r t = 1) = 1 P(R t = 1 | S t (A) = (t, m, b, ℓ), g t = k, r t = 1) = |G k t-1 | + 1 |G k t-1 | + t ,where|G k t-1 | = m if k = 1 t -1 -m if k = 2 . Proof. If S t (A) = (t, m, b, ℓ), then in particular g * t-1 = ℓ, i.e. max G ℓ t-1 > max G k t-1 , thus P(r t = 1 | S t (A) = (t, m, b, ℓ), g t = ℓ) = P(x t > max G ℓ t-1 | S t (A) = (t, m, b, ℓ), g t = ℓ) = P(x t > max x 1:t-1 | S t (A) = (t, m, b, ℓ), g t = ℓ) = 1 t ,because the rank of x t among previous candidates is independent of their relative ranks and groups, thus independent of the state of the algorithm. Moreover, if r t = 1, g t = 1 and g * t-1 = ℓ, then x t is the better than the maximum of G ℓ t-1 , which is the maximum of x 1:t-1 , thus necessarily R t = 1,P(R t = 1 | S t (A) = (t, m, b, ℓ), g t = ℓ, r t = 1) = 1 .On the other hand, ifg t = k ̸ = ℓ = g * t-1 , assume that |G ℓ t-1 | > 0. It holds that P(r t = 1 | S t (A) = (t, m, b, ℓ), g t = k) = P(r t = 1 | g * t-1 = ℓ, g t = k, |G 1 t-1 | = m) = P(r t = 1, g * t-1 = ℓ | g t = k, |G 1 t-1 | = m) P(g * t-1 = ℓ | |G 1 t-1 | = m).We have immediately thatP(g * t-1 = ℓ | |G 1 t-1 | = m) = P(max G ℓ t-1 > max G k t-1 | |G 1 t-1 | = m) = |G ℓ t-1 | t -1 ,and the numerator can be computed asEQUATIONwhich yieldsP(r t = 1 | S t (A) = (t, m, b, ℓ), g t = k) = t -1 |G ℓ t-1 | • |G ℓ t-1 | t 1 t -1 + 1 |G k t-1 | + 1 = 1 t 1 + t -1 |G k t-1 | + 1 = |G k t-1 | + t t(|G k t-1 | + 1).Finally,P(R t = 1 | S t (A) = (t, m, b, ℓ), g t = k, r t = 1) = P(R t = 1, r t = 1, g * t-1 = ℓ | g t = k, |G 1 t-1 |) P(r t = 1, g * t-1 = ℓ | g t = k, |G 1 t-1 |).We computed the denominator term in (17), and the numerator satisfiesP(R t = 1, r t = 1, g * t-1 = ℓ | g t = k, |G 1 t-1 |) = P(R t = 1, g * t-1 = ℓ | g t = k, |G 1 t-1 |) = P(x t > max G ℓ G ℓ t-1 > max G k t-1 | |G 1 t-1 |) = 1 t • |G ℓ t-1 | t -1 , hence P(R t = 1 | S t (A) = (t, m, b, ℓ), g t = k, r t = 1) = |G ℓ t-1 | t(t-1) |G ℓ t-1 | t 1 t-1 + 1 |G k t-1 |+1 = 1 1 + t-1 |G k t-1 |+1 = |G k t-1 | + 1 |G k t-1 | + t .This concludes the proof when |G ℓ t-1 | > 0. If |G ℓ t-1 | = 0, then the same identities remain trivially true.Using the previous Lemma, we can fully characterize the possible state transitions of a memory-less algorithm. First, the values of the parameters |G 1 t | and B t+1 are trivially determined based on the state S t at the beginning of step t, the observations r t and g t , and the actions of the algorithm:|G 1 t | = |G 1 t-1 | + 1(g t = 1) , B t+1 = B t -1(a t,1 = compare), where a t,1 is the action taken by the algorithm, which only depends on the state S t since the algorithm is memory-less.Using Lemma D.3 and considering the potential state transitions based on the actions, we establish a recursion satisfied by (V B t,m,ℓ ) t,B,m,ℓ . We present the result without distinction between the cases ℓ = 1 and ℓ = 2. For simplicity, let λ k = P(g t = k) for k = 1, 2, and define M k = m + 1(k = 1) for all m ≥ 0. Additionally, for all (B, t, m, k), defineδ B k = 1 R B t,m,k (accept) ≥ R B t,m,k (skip), where the action accept corresponds to compare for B > 0 and stop for B = 0. Theorem D.4. For all t ∈ [N ], m < t and {k, ℓ} = {1, 2}, the success probability of A * with zero budget satisfies the recursionV 0 t,m,ℓ = λ ℓ δ 0 ℓ N + 1 - δ 0 ℓ t V 0 t+1,M ℓ ,ℓ + λ k δ 0 k N + 1-δ 0 k t V 0 t+1,M k ,k + 1 -1 t 2 -δ 0 k - 1 |G k t-1 |+1 V 0 t+1,M k ,ℓ, and for B ≥ 1 it satisfiesV B t,m,ℓ = λ ℓ δ B ℓ N + 1 - δ B ℓ t V B t+1,M ℓ ,ℓ + λ k δ B k N + δ B k |G k t-1 |+1 1 -1 t V B-1 t+1,M k ,ℓ + 1-δ B k t V B t+1,M k ,k + 1 -1 t 1 - δ B k |G k t-1 |+1 V B t+1,M k ,ℓ, where V B N +1,m,k = 0 for all B ≥ 0 m ≤ N and k ∈ {1, 2}.Proof. Using the results from Section D.2 and D.3, the actions of A * and the resulting state transitions are as follows. If the state of A * at step t is S t (A * ) = (t, B, m, ℓ) for some B ≥ 1, m < t and ℓ ∈ {1, 2}: If g t = ℓ, denoting by M ℓ = m + 1(ℓ = 1), we have• with probability 1 -1/t: r t = 0, and the algorithm rejects the candidate, transitioning to the state (t + 1, B, M ℓ , ℓ).• with probability 1/t: r t = 1, and necessarily R t = 1, because g t = g * t-1 = ℓ.-If R B t,m,k (compare) > R B t,m,k (skip), then the algorithm uses a comparison and observes R t = 1, hence accepts the candidate. The success probability in that case is t/N . -Otherwise, the candidate is rejected and the algorithm goes to state (t + 1, B, M ℓ , ℓ)On the other hand, if g t = k ̸ = g * t-1 , then denoting by M k = m + 1(k = 1), we have• with probability|G k t-1 |(t+1) t(|G k t-1 |+1) : r t = 0,and the algorithm rejects the candidate, transitioning to the state (t + 1, B, M k , ℓ). In the case of a zero budget, the algorithm compares R B t,m,k (skip) to R B t,m,k (compare) instead of R B t,m,k (compare). If the algorithm decides to reject the candidate then the same state transition occurs. However, if the candidate is selected and if g t = g * t-1 = ℓ then the success probability is t/N . If On the other hand, if it is selected and g t = k ̸ = g * t-1 = ℓ then the probability that the current candidate is the best overall isEQUATION|G k t-1 |+1 |G k t-1 |+t × t N .All in all, for B = 0, then(V 0 t,m,ℓ | g t = ℓ) = 1 t δ 0 ℓ t N + (1 -δ 0 ℓ )V 0 t+1,M ℓ ,ℓ + 1 - 1 t V 0 t+1,M ℓ ,ℓ = 1 - δ 0 ℓ t V 0 t+1,M ℓ ,ℓ + δ 0 ℓ N (V 0 t,m,ℓ | g t = k) = |G k t-1 |+t t(|G k t-1 |+1) δ 0 k t(|G k t-1 |+1) N (|G k t-1 |+t) + (1 -δ 0 k ) |G k t-1 |+1 |G k t-1 |+t V 0 t+1,M ℓ ,l + t-1 |G k t-1 |+t V 0 t+1,M ℓ ,ℓ + |G k t-1 |+t t(|G k t-1 |+1) V 0 t+1,M k ,ℓ = δ 0 k N + 1-δ 0 k t V 0 t+1,M k ,k + 1 -1 t 2 -δ 0 k - 1 |G k t-1 |+1 V 0 t+1,M k ,ℓ ,and we deduce thatV 0 t,m,ℓ = λ ℓ 1 - δ 0 ℓ t V 0 t+1,M ℓ ,ℓ + δ 0 ℓ N + λ k δ 0 k N + 1-δ 0 k t V 0 t+1,M k ,k + 1 -1 t 2 -δ 0 k - 1 |G k t-1 |+1 V 0 t+1,M k ,ℓ . For B ≥ 1, we obtain (V B t,m,ℓ | g t = ℓ) = 1 t δ B ℓ t N + (1 -δ B ℓ )V B t+1,M ℓ ,ℓ + 1 - 1 t V B t+1,M ℓ ,ℓ = 1 - δ B ℓ t V B t+1,M ℓ ,ℓ + δ B ℓ N (V B t,m,ℓ | g t = k) = |G k t-1 |+t t(|G k t-1 |+1) δ B k |G k t-1 |+1 |G k t-1 |+t V B t+1,M k ,k + t-1 |G k t-1 |+t V B t+1,M k ,ℓ + (1 -δ B k ) |G k t-1 |+1 |G k t-1 |+t V 0 t+1,M k ,l + t-1 |G k t-1 |+t V 0 t+1,M k ,ℓ + |G k t-1 |+t t(|G k t-1 |+1) V B t+1,M k ,ℓ = δ B k N + δ B k |G k t-1 |+1 1 -1 t V B-1 t+1,M k ,ℓ + 1-δ B k t V B t+1,M k ,k + 1 -1 t 1 - δ B k |G k t-1 |+1 V B t+1,M k ,ℓ , hence V B t,m,ℓ = λ ℓ δ B ℓ N + 1 - δ B ℓ t V B t+1,M ℓ ,ℓ + λ k δ B k N + δ B k |G k t-1 |+1 1 -1 t V B-1 t+1,M k ,ℓ + 1-δ B k t V B t+1,M k ,k + 1 -1 t 1 - δ B k |G k t-1 |+1 V B t+1,M k ,ℓ, which concludes the proof.Implementing the optimal memory-less algorithm A * with budget B requires knowing the (R b t,m,k (a)) t,b,m,k for a ∈ {skip, stop, compare}, which depend themselves on the table V b t,m,k t,b,m,k . Using Lemma D.3 and Theorem D.4, these tables can be computed in a O(BN 2 ) time as described in Algorithm 2.After computing these tables, the optimal memory-less algorithm A * can be implemented by following the rational decision rules outlined in Section D.3, and when encountering r t = 1 and needing to choose between accepting or rejecting the candidate, A * selects the action that maximizes its expected reward given the information it has about the current state. A detailed description is provided in Algorithm 3. • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: This paper was interesting. Two of the reviewers gave positive but short reviews and then did not respond to the authors' rebuttal. The responsive reviewer updated their score to a 7 after rebuttal. I stepped in and read the paper myself and asked clarifying questions to authors. My initial review (just seen by me) is below: 

	I am reasonably impressed by this paper. I list strengths and weaknesses below, but I feel the theoretical strengths outweigh the empirical limitations of the work, even given the simple two-group framework they study. I'd push for weak acceptance.

	Strengths:
	(+) Clear motivation, simple theoretical framework, well-written
	(+) Nontrivial theoretical results even for relatively simple cases (i.e., two groups with potentially different thresholds or a single threshold for multiple groups)
	(+) I appreciated the authors' clarification that the two models are essentially the same K-1 comparisons to initially establish a "best over all groups" candidate that then gets updated as the process progresses
	(+) I agree with the authors' rebuttal that reviewers' concerns about real-world data are overblown

	Weaknesses:
	(-) I appreciated the authors' suggestion in their rebuttal that their machinery would extend to more than two groups; however, I am somewhat suspicious that it would be more complicated than they made it seem
	(-) The figures in the empirical section are poorly labeled and explained
	(-) Would it be possible to obtain any meaningful empirical results (even the performance of reasonable heuristics?) for more than two groups to give a taste of what extending results past two groups may look like? In a similar vein, is it possible to add any "natural" baselines in the case of two groups? Maybe something as simple as using the single-threshold algorithm would be a useful comparison point
	(-) In the vein of picking on experiments, would it be possible to examine what happens for higher values of B? B = 2 seems like a very small maximum budget
	(-) Minor typos throughout; largely did not influence my understanding of the paper

The authors presented a nice response to W3 (baseline) and W4 (B = 2 budget). They did acknowledge that the extension to more than two groups could be challenging, but they said that they were still confident that they could derive expressions in more complicated settings.

Reviews: review: paper_summary: paper_summary: This paper tackles an online hiring selection with budget problem. The authors propose a dynamic threshold method and provides theoretical analysis on the algorithm performance. The numerical experiments confirm the findings of the algorithm.
strength_weakness: strength_weakness: 1. Although the problem is well motivated, it lacks of empirical analysis on real datasets and applications.
2. No baseline methods are compared in the experiments.
questions: questions: See above weakness.
limitations: limitations: See above weakness.
paper_summary: paper_summary: This paper studies a novel extension of multi-color secretary problem, where comparing candidates from different groups is possible at a cost. With a limited budget total, a Dynamic-Threshold algorithms family is introduced, and the success probability of a special case, i.e. single-threshold algorithm for K groups, is comprehensively analyzed. Moreover, in-depth theories have been studied in the scenario of two groups, including double threshold algorithms and the optimal memory-less algorithm.
strength_weakness: strength_weakness: 1. The title of this paper is not quite appropriate, since bias defined in the field of statistics does not seem to exist in the multi-color secretary problem. I understand that there are different definitions of bias in real-life scenarios, but this could mislead readers in various areas.
2. There are some mistakes in the presentation of this article. For example, line 36 is not complete. Besides, the citation form in line 73 is not correct.
questions: questions: I would like to know whether the theories in Section 4 can be generalized to the case of more than 2 groups. If so, is the generalization straightforward?
limitations: limitations: The authors adequately discussed the limitations of the paper.
paper_summary: paper_summary: The paper studies an extension of the online secretary problems in which candidates from multiple groups arrive. The goal is to find the best candidate, but while within-group comparisons are free, inter-group comparisons are not available a priori and we have a limit of B queries to a comparison oracle for such comparisons.
The authors study the single threshold algorithm in which we wait up until some time t and then either selects the first candidate if its the best among all groups so far (by doing a comparison) or if comparisons have been used up selects a candidate if it is the best candidate in its group seen so far.  The authors derive a lower bound on the probability of success that converges rapidly to 1/e as the budget B tends to infinity. This algorithm is independent of the group proportions. For the case of two groups, they analyse a double threshold algorithm and show a more fine-grained analysis that does depend on the group proportions. They further provide the optimal memoryless algorithm for the case of two groups, facilitating the computation of the optimal bounds. They show that the double threshold algorithm fares well in comparison and that the optimal memoryless algorithm behaves like a double threshold algorithm in the large candidate limit.
strength_weakness: strength_weakness: The focus on the case of two groups is rather restrictive. Furthermore, it is unclear whether the techniques would generalise to further groups, or very much rely on this special case. In any case, the case for more groups seems non-trivial.

The discussion on the alternate model is missing from the main body and appendix, despite available space in the main body.

The figures would benefit from an explanation of what the dashed lines and what the continuous lines each represent. 
Detailed/minor comments:

The sentence on line 36 is incomplete.

Line 93: cardinal -> cardinality

Line 148-151: Make the notation consistent with the pseudocode (whichever way around).

Line 110: full stop missing

Figure 2 and line? Why does the second row in Figure 2 not have (1-\lambad)t displayed instead?

256: cardinal-> cardinality
What is |G_t^{1/2}|

Line 259-260: The phrasing is unclear.
questions: questions: 2. 103-104: While I appreciate listing two possible models (indeed, I think he first one seems more natural), you claim here that throughout the paper you discuss how to extend the results to model 1 (which to me appears more natural). However, reading the main body I didn’t see this. Can you please explain what the results are and specify where in the paper you discuss the first model?
limitations: limitations: No concerns.

Comments: comment: We thank the reviewer again for their feedback and appreciate the positive reevaluation of the score.  

In Figure 3, the continuous and dotted lines represent respectively the success probabilities of the optimal memory-less algorithm $\mathcal{A}_*$ and the algorithm of Corollary 4.3.1. In Figure 4, they represent respectively the success probabilities of the DT algorithm with optimal thresholds and the optimal memory-less algorithm. 

We will include this clarification, along with a discussion on the alternate model, in the revised version of the paper.
Thank you for your response. Regarding the alternate model: You seem to have some space available still in your main body, so it would be worth including this as a brief discussion. Please also clarify in an update version of the paper what the lines in your figures mean, i.e. what do dashed and continuous lines each represent. I am updating my score.
Thanks for the rebuttal from the authors. I have no further questions. After reading the paper again and all the reviews, I think my previous rating is adequate.