Addressing Bias in Online Selection with Limited Budget of Comparisons
Authors: Ziyad Benomar
Evgenii Chzhen
Nicolas Schreuder
Vianney Perchet
Venue: NeurIPS 2024 poster (2024)
Keywords: the secretary problem
online selection
online algorithms
decision-making under uncertainty
Primary area: algorithmic_game_theory

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.

Addressing Bias in Online Selection with Limited Budget of Comparisons
Ziyad Benomar ENSAE, Ecole Polytechnique, FairPlay joint team ziyad. benomar@enaae fr
Evgenii Chzhen CNRS, LMO, Université Paris-Saclay
fr
Nicolas Schreuder
Vianney Perchet CREST, ENSAE, Criteo AI LAB Fairplay joint team
CNRS, Laboratoire d'informatique
Gaspard Monge (LIGM/UMR 8049) nicolas wwwhreddereerr... fr
vianney saanmeyy.perchettoormllllaaasss org
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 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 multicolor secretary problem, allowing compar- isons between candidates from distinct groups at fixed cost. Our study explores how the allocated budget enhances the success probability in such settings.
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 a uniformly random order. When new candidate is observed, the decision maker can either select them and halt the process or reject them irrevocably. The optimal strategy 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 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 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 some socioeconomic attributes (Salem al.) 2022 Raghavan et al. 22020). To tackle this issue, several works have explored variants the secretary problem with noisy or biased observations [Salem and Gupta 2019 Freij and Wästlund 2010]. In particular, (Corea et al. (202 102la| studied the multi-color secretary problem, where each candidate belongs to one of 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 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 examination. Taking this into account, we study the multicolor secretary problem with budget for comparisons, where comparing candidates from the same group is free, and comparing candidates
obtaining inter-group orders at some cost, through testing and
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

from different groups has fixed cost of 1. We assume that the decision maker is allowed at most B comparisons. This budget 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 the selected candidate the best overall, otherwise, it has failed. The objective is to design algorithms that maximize the probability of success.
1.1 Contributions
The paper studies an extension of the multi-color secretary problem [Correa 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- 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/ /eesstratey.. However, the analysis is intricate due 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 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.
1.2 Related work
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 HHajiahhayi et al. 2007) Nested Rollout Policy Adaptation (NRPA) [Dang et al. [0023]. active learning [Fujii and Kashima 2016], and the design of interactive algorithms [Sabato and Hess 2016 2018). Moreover, the secretary problem has multiple variants [Krlin and Lei 2015 Bei and Zhang, 2022 Assadi et al., 2019 Keller and GeiBer| 2015), and has inspired other works, for instance, related to matching
The secretary problem The secretary problem was introduced by Dynkin 1963)
Goyal| 2022 [ Dickerson et al. [2019] or ranking (Jiang et al. [00T]] A closely related problem the prophet inequality [Krengel and Sucheston, 1977, Samuell Cahn 1984), where the decision-makke 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 al. 2010 Feldman et al.) [014] and have been explored in multiple variants Kennedy 1987 Azar et al. 2018 Bubna and Chiplunkar 2023 Benomar et al.) 2024].
Different information settings 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. [021b] or -eadrnee-eerred advice [Attoniadis 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 [9800] 1982] addressed the optimal stopping of target process when only related process is observed, and they designed mechanisms for acquiring information from the target process. However, these works do not assume fixed budget and instead consider penalized version of the problem.
Online algorithms with limited advice This paper also relates other works online algorithms, where the decision-make maker is allowed to query limited number of hints during execution. The 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. 202T]. caching. [Im et al. 2022], paging (Antoniadis et al., 2023), scheduling [Benomar Perchet]. metrical task systems (Sadek and Elias 20044] clustering [Silwal et al., 2023 and sorting [Bai and
objective of these analyses
Coester, 2024 [enommrr and Coester 2024j. Another related paper by Drygala al. [2023) studies
penalized version of the Bahncard problem with costly hints.
2 Formal problem
We consider strictly totally ordered set of cardinal N, whose elements will be called candidates. We assume that these candidates are observed in uniformly random arrival order (æ1,.. ZN), and that they are partitioned into K groups G ,...,. G For all t E [N], we denote by gt. E [K] the group of Tr, i.e. Ty. E G and we assume that [9:) are mutually independent random variables
P(ge = k)) Ak: E [N), vk E [K],
where A for all [K] and
Σ ^ 1.
We assume that comparing candidates of the same group is free, while comparing two candidates of different groups costly. To address the latter case, we consider that budget 2 0 given for comparisons and we propose two models: the algorithm can pay a cost of in order to:
1. compare two already observed candidates 2; and F, 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 the second model. However, explain during the paper how 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 better candidate the future. Once candidate has been rejected, they cannot be recalled-the decisions are irreversible. Given the total number of candidates N, the probabilities (Au )<e[K] characterizing the group membership, and 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, --secretrryy problem
2.1 Additional notation
For all < s E [N], we denote by Tt:a ;= f......,........................ }. and for all k E [K] we denote by Gk the set of candidates of group h observed between steps t and s,
G (x, tt and g. k} Zest O n*
Ift= 1, then we lighten the notation G ;= G Let be any algorithm for the (K, -eeerttryy problem, we define its stopping time T(4) the step t when it decides to return the observed candidate. We will often drop the explicit dependency on and write 7 when no ambiguity is involved. We will say that A succeeded if the selected candidate I, is the best among all the candidates (II...., NN Let us also define, for any step 2 1, the random variables
Σ 1( S1r. gr) and R 1(x, R
P=1
d=1
Both random variables have natural interpretations: given candidate at time 1,, v' its in-group rank up to time t, while R2 is its overall rank up to time Note that the actual values of æ; do not play

---

role in the secretary problem and we can restrict ourselves to the observations rt. 9t, R4. While the first two random variables are always available at the beginning of round t, the third one can only acquired utilizing the available budget. At each step E [N], the decision-make observes rt. and can perform one of the following three actions:
1. skip: reject 2t and move to the next one;
2. stop: select xy;
3. compare: if the comparison budget is not exhausted, use comparison to determine if (R; (>)-coppre the candidate I; to the best already seen candidates in the other groups;
Furthermore, a comparison has been used at time t, the algorithm has to perform stop or skip afterward. We denote respectively by dt,1 and 0,22 the first and second action made by the algorithm at step f. Let us also define ge the group to which the best candidate observed until step belongs,
gi argmax(max G
Vt [M]
kE(K]
and B3 as the budget available for A at step /
B1 = and B, B 1(a,11 = compare) VI E [M]]
In the presence of a non-zero budget, the first time when decides to make a comparison will key parameter in our analysis of the success probability. We denote it by P1 (A))
Pi (A min(t E [N] at,1 = compare].
As with the stopping time, when there is no ambiguity about A, we simply write p1- Remark 2.1. Although we formalized the problem using the variables rt and RG, the only information needed at any step is [(r = 1) and 1 1(, = 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;
can be observed by comparing Ie to the best candidate up to I belonging to G and if this is the case then I (Re = 1) can be observed by comparing It the best candidate in the other group.
3 Dynamic threshold algorithm for K groups
In this section, we introduce a general family of Dynamic-thresholl (DT) algorithms. A DT algorithm for the (K, B) --secretyyyy problem is defined by finite -oubly-indexed sequence (e bss 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 by A (((I,,)))(K)),5.)))
Upon the arrival of in-group rank rı, and has an available budget of B, = 2 0. If I/N < Og.b or r. = O, the candidate immediately rejected. Otherwise, if t/N OgRbb and = then the candidate is selected if b O; and if the budget is not yet exhausted (6 > 0), then the algorithm pays a unit cost to observe the variable IRR, 1). If this variable is indicating favorable comparison, the candidate selected; otherwise, it is rejected. A formal description is given in Algorithm I and a visual representation for the case of three groups is provided in Figure
candidate Tt, the algorithm observes its group g: k E [K] and its
3.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 - where T E [N] is a fixed threshold. Upon encountering new candidate that is the best within its group, if no budget remains, the candidate is selected. Alternatively, if there is still budget available, the algorithm utilizes to determine the current candidate is the best among all groups. If that is the case, the candidate is then selected. We denote by A the single-threshold algorithm with threshold and budget B. We demonstrate that this algorithm has 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 threshold T |aN] for some [0, 1].

---

Dynamic Threshold algarithm: M ((
01.3
625
Remaining budget
622
43322
skip
comp: Fy 1. =1
comp: 1. (1.
comp: 7:
ski 9, (2.3)
sk1p: m
0.2
0.6
1/N
Figure 1: Schematic description of a DT algorithm in the case of groups
Algorithm 1: Dynamic-Threshol algorithm A ((ax, ((()))))(())))5))
Input: Available budget B, thresholds (OE,,b)EE (E),b) KK)bBB Initialization: h = B for f ,......N .N do
Receive new observation: (rz, i [ and r; = then if b > O then Update budget: + b if RG I then Return:
// compare in in-group // check budget
// compare inter-group
else Return:
Lemma 3.1. The success probability of the single threshold algorithm A.. with threshold T |oN] and budget B 2 satisfies the recursion formula
a + K-1
T k++ t=T
P(T succeeds)
+1 2 0)
B-1 P(A
succeeds) + +0(v log N
The proof hinges analyzing the behavior of the algorithm following the first comparison. After that comparison, the algorithm halts if R. 1, and the success probability can be computed in that Otherwise, if R2 * the candidate is rejected, and the algorithm transitions new state step f. + 1, where the available budget reduces to B Its success probability becomes precisely that algorithm BB-1 with budget B 1 and threshold 1.
The recursion outlined in Lemma 3.1 can be used to calculate the asympiotic success probability of single-threshold algorithm A [[N]] as number of candidates N approaches infinity.
Theorem 3.2. The asymptotic success probability of the single threshold algorithm AB with threshold T = |aN] and budget B 0 is
K B
log(1 /1
lim P(A [aNj succeeds) N+000
K
ak-
El
b=0
t=
In particular,
lim lim P(4 [[A[Nn] succeeds) = a log(1/a).
B-530 N
Note that, for = oo, the asymptotic success probability the previous theorem corresponds the success probability of the algorithm with threshold |aN] in the secretary problem. Indeed, with an unlimited budget, the decision-male can assess at each step whether the current candidate the best so far, and the problem becomes equivalent to the classical secretary problem.
5

---

Alternative comparison model. In the alternative comparison model presented in Section 2 the single threshold algorithm Af can be adapted to guarantee the same success probability 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 of K + B instead of B.
The next corollary measures how the success probability of the single threshold algorithm, in the setting with K groups, converges 1/c as the budget increases. Corollary 3.2.1. The success probability of the single-threshold algorithm with threshold T LN/e]
and budget B 2 0 satisfies
1
(K (K-1)
Jim 40000
[N/e] succeeds)
e (B + 1)!
In particular, for all e > O, if < B+1 (EE) Bir, then limy P(A [N/e] succeeds) 2 (1 s)/e.
This corollary proves that the success probability of Afvee converges very rapidly to the upper bound 1/c as B increases. However, the convergence becomes slower when K is larger.
Surprisingly, the asymptotic success probability of [[N/c] is not influenced by the proportions (λе))E(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 with d very close to which would make the problem easier. Indeed, it is always possible to achieve success probability of max [K] Az/e by rejecting all the candidates not belonging to the majority group Gk', and using the classical 1/e-rule counting only elements of G* 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 1/e both when B increases and when max; A converges to 1. Nonetheless, due to the very fast convergence of the success probability of the single threshold algorithm to 1/c, the improvement brought by having majority group is only marginal when the budget is sufficient.
As consequence, the single threshold algorithm surprisingly constitutes very efficient solution to the problem even with moderate values of the budget. Computing the optimal thresholds remains however intriguing question, which we explore in the following sections in the case of two groups.
4 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 X E (0,1) represent the probability of belonging to group G', and 1 A the probability of belonging to group G2. We examine the success probability of Algorithm A (a. 3). with threshold [aN] for group G and [ for group G2, having a budget of B comparisons. This algorithm is 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
algorithm.
We assume without loss of generality that a S B, and we denote by Cn the event
(Cx):
VI 1: max(I G. XM ||G (1 A)E) < 4V1log N
This event provides control over the group sizes at each step. Lemma A.2 guarantees that CN holds true with probability at least 1 1
N₂ for N > 4. Furthermore, for all E [N], we denote by AB (a,33) the algorithm with acceptance thresholds Laxx( and max nax[[8N],4) respectively for groups GD and G², and we denote by UR the probability
u Uk P(A (a, B) succeeds, gh k CN)
(
Similar to the analysis of the single-threshold algorithm, we establish in Lemma CT recursion formula satisfied by ( k B,,,k,
B,K, which we later utilize to derive lower bounds on the asymptotic

---

success probability of A (a, B). To prove this lemma, we study the probability distribution of the occurrence time Pi of the first comparison made by A [a. 5), and we examine the algorithm's 's success probability following it. Essentially, if P1 8, we can compute the probability of stopping and the corresponding success probability, and the distribution of the state of the algorithm at step + 1, which yields the recursion. Using adequate concentration arguments and Lemma C. we show the two following results, giving explicit recursive formulas satisfied by the limit of N. when
N + oo, respectively for k 2 and k 1.
Lemma 4.1. For all B 2 0 and w E [a, B), the limit 22 (a, B; w) = limm- U and it satisfies the following recursion
N.
exists,
(1 - A)3W²
13
b
log(1/3))
22 (;, = -xw log ((1 =) + +1 +
(1 \)w + XB
3
e!
6=0
E=U
+ 1(B> > 0) w² / 1)= 1(2 A)U
P2 (a, B: u)du.
((1- Apw + Au)auz
Moreover, U NN 1.2 = 2 (a, B) + +0(v log N
N
Lemma 4.2. For all B 2 0 and w E la, B), the limit 4p (a, 3: w) = lim -o U [N,N exists, and it satisfies the following recursion
(a, B: = Aw log (1 x+ + Awi32
B
b
13)
(1 A)w + X3
3
e!
6
1 (u - w)pp B-1 (a, B: u)
+1 > 0) X2W
du.
((1 A)w + )u)
"
Moreover. Uh [N,NJJ = of (a, 3: w) + 0
Nog
We deduce that the asymptotic success probability of Algorithm A [ conditioned on the event CN.
exists and equals pp (a, 9; w) + op (a, 3: w). Additionally, by applying Lemma A.3 we eliminate the conditioning on CN, thus proving the following theorem.
A((a, 3) satisfies Theorem 4.3. For all 0 S 3 < 1, The success probability of Algorithm A (a,
P(A succeeds) 0 (VV
log N
B
b log(1
(1))) E!
3 (a, 33 u)
B-
= log 2
+ a3
+ L( 0)a
92
u
b=0
t=
with of (a, Bi-) defined in Lemma 4.1
It is possible use Theorem 4.3 and 4.1 to numerically compute the success probability of A ( 3). However, this computation is heavy due the recursion defining v (a, 33 w). Moreover, it is difficult to prove closed expression, and even more to compute the optimal thresholds.
By disregarding the term containing 2 (a,, B:-) ) in the theorem, we derive an analytical lower bound expressed as function of the parameters X, B, a, and 8, allowing more effective threshold selection. In the subsequent discussion, for all w E (0, 1] and B 2 0, we denote by S (w) the following sum:
B
b log(1/w)) Σ
SB((w)
Σ h=0
L
e!
Corollary 4.3.1. Assume that X 2 1/2. Let hB : min { exp es (8)
88 and āB,
the thresholds defined as ãg 1t (39)) and BB minimizing the mapping
(3) e E [0, 1] H Xh(3) log (n)()) + h
then the success probability of A (ā 3r) satisfies
lim ((AB((B,)) BB) succeeds) > min LeeB + f}!" ( -1-1)A(1 -N1} 12(1-1))
1
N-000
7

---

Therefore, in contrast to the single-threshol algorithm, the asymptotic success probability of ( (B) approaches 1/e both when the budget increases and when À approaches O or 1.
4.1 Optimal memory-less algorithm for two groups
In the following, an algorithm is called memory-less its actions at any step [N] depend only on the current observations Tt, 9t, 1 (R, 1), the available budget Bt, and the cardinals ((G ([G]-I)eE[K]]
We use in this section a dynamic programming approach to determine the optimal memory-less algorithm, which we denote by A..
KQJ
Unlike previous sections, analysis here is not asymptotic. By meticulously examining how var- ious 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 prob- abilities determine optimal actions at each step. A full description and analysis of the optimal memory-less algorithm can found in Section D Here, we illustrate its actions through Figure
63 A2 13
Figure 2: Acceptance region of A.
Computing optimal thresholds for the DT algorithm. Upon observing (r). A, makes a decision accept reject, where acceptance means stop if B 0 and compare otherwise. depending on f, G. B, 9t- Figure shows its acceptance region (dark green), with N = 500, and g. 2). The and y-axes display respectively the step f and possible group cardinal |G which implies |G?] up to time t. The latter follows binomial distribution with parameters (), which tightly concentrates around its mean G = At (and G ~ (1 A)t) even for moderate values of Consequently, when N large, |G Rs Al, and the acceptance region solely defined by a threshold the intersection of the acceptance region and the line [ x At. This observation implies that A. behaves as an instance DT algorithms when the number of candidates large. The corresponding thresholds, which we denote by (at, 8 los B. are necessarily optimal, and can be estimated the intersection of the acceptance region for 6 and the line (1, X6) for k: E {1, 21.
= 0.7, for {0, 1, 2} and for all possible values of E [N]. |G
Alternative comparison model. In the particular case of two groups, both comparison models introduced in Dection@aare equivalent, freely comparing 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- double-threshold algorithm and optimal memory-less algorithm remain true in the alternative comparison model.
5 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 106 independent trials. The code used for the experiments is available at selection- witheli selection-wih--iiiieedde wfth--limited-uuuge-----ffff codleettof-ccmppaiioonss
5.1
Single-threshold algorithm
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 E (O..... .0) and K (2, 10, 25, 50). For any K 2 2, as the budget grows to infinity, the problem becomes akin to the standard secretary problem, leading the optimal

---

threshold to converge to 1/c. However, as discussed in Corollary 3.2.1 the convergence is slower when the number of groups K is higher.
Optimall single threshol
Suceeepiiiliity
08
23
04
02
14
of of
Budget comprrriioo
Figure 3: Single threshold algorithm: optimal threshold and corresponding success probability
Moreover, Theorem 3.2 reveals that the asymptotic success probability is independent of the prob- abilities 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 (A Figure 4 illlustaates this behavior for the case of two groups, with N 500 candidates, and B E {0, 1, 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. Tiguree]ssoov that the success probability is better when the number of candidates is small, and it decreases match the asymptotic expression when N oc, represented with dotted lines, for E {2, 3, 4). with = 3.
6.0
6.4
2 A [6.]] bekoggia
condidates
Figure 4: Single threshold: success probability for 2 groups, with N 500 and [0, 1]
Figure 5: Convergence to the asymptotic success probability, with 2ς- = 1/K for all l E [K]
5.2 The case of two groups
In the case two groups, Figure 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, the remaining experiments in the two-group scenario, we restrict ourselves small budgets B
Theorem D.4 shows recursive formula for com- puting the success probability of the optimal memory-less algorithm A, for all N > 1, 2 0. and X E (0, 1). Figure 6 displays this success probability, in solid lines, for N = 500 and B E 1, 2). along with the success proba- bility of the static double-threshold algorithm (ā 3B) in dotted lines, where āB, .g are defined in Corollary 4.3. The figure demon- strates that for B = U. or close to 0.5, Algo- rithm A A 3B) matches the performance of A., despite having much simpler structure.
1/x
Probubility a [0 bf to
Figure 6: Success probability of A., and the lower bound of Corollary 4.3.1

---

For À = 0.5, both groups have symmetric roles, and the optimal thresholds âB and 3B to choose in the static-threshold algorithm are identical. Hence, the success probability of AA ( 9B for 0.5 exactly that of the single-threshor algorithm, which independent of (Theorem 3.2) We deduce from this observation and Figure 6 that having different thresholds for each group yields substantial improvement over the single-threshold algorithm when 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 compares the empirical success probabilities of A, (dotted lines) and the DT algorithm (solid lines) with thresholds (a Si B20. computed as explained in Section 4.1
0-07
0.15
0.35
0.565
B =0
0.36
0.36
0.500
11 ml
0.34
0.34
0.32
6:10
0.12
0.566
0.30
1.0
0.20
100 Number condidatos
300
939
Number candidates
Number candidittes
Figure 7: Empirical success probabilities of A. and the DT algorithm with optimal thresholds
For A E {0.5, 0.7, 0.95), the figure confirms that, despite the intricate structure of the optimal memory-less algorithm, 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 X shows the optimal thresholds ofg; f8 for all X [0.5, 1] and B E {0, 1,
4050
Todak B34 tu
Prekababy Uudbiaappp to
Figure 8: (at, (8) as functions of X.
These thresholds are continuous functions of X, both converging to 1/e very rapidly the budget increases. Indeed, for 2 1. they both become very close to 1/e, as for B = O, the optimal thresholds are exactly equal to a X exp( 2) and S X, which correspond to the optimal thresholds described in Corollary 4.3. for = (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 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 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.
10

---

Acknowledgements
This research was supported in part by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project (ANR-23-PELA-000) 23-CE23-0002. It was also funded by the European Union (ERC, Ocean, 101071601). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority be held responsible for them.
and through the grant DOOM ANR-
References
Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. Advances in Neural Information Processing Systems, 33: 7933-7944, 2020.
Antonios Antoniadis, Joan Boyar, Marek Fliás, Lene Monrad Favrholdt, Ruben Hoeksma, Kim S Larsen, Adam Polak, and Bertrand Simon. Paging with succinet predictions. In International Conference on Machine Learning, pages 952-968. PMLR, 2023.
Sepehr Assadi, Eric Balkanski, and Renato Leme. Secretary ranking with minimal inversions. Advances in Neural Information Processing Systems, 32, 2019.
Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Prophet secretary: Surpassing the 1-1/e barrier. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 303-318, 2018.
Xingjian Bai and Christian Coester. Sorting with predictions. Advances in Neural Information Processing Systems, 36, 2024.
Xiaohui Bei and Shengyu Zhang. The secretary problem with competing employers on random edge arrivals. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 4818 4825, 2022.
Ziyad Benomar and Christian Coester. Leaming-augmmetedd priority queues. arXiv preprint arXiv:2406.04793, 2024.
Ziyad Benomar and Vianney Perchet. Non-clairvoyant scheduling with partial predictions. In Forty-first International Conference on Machine Learning.
Ziyad Benomar and Vianney Perchet. Advice querying under budget constraint for online algorithms. In seirthy Conference on Neural Information Processing Systems, 2023.
Ziyad Benomar, Dorian Baudry, and Vianney Perchet. Lookback prophet inequalities. arXiv preprint arXiv:2406.06805. 2024.
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Logarithmic regret from sublinear hints. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021. NeurIPS 2021, December 6-14. 2021, virtual, pages 28222 28232. 2021. URL https: httptps:/pprcceeiinng
www.ainwng........o.oo.m cc/ http:///...sseceeee2e222222222f3 Abstraac.. .tml
Archit Bubna and Ashish Chiplunkar. Prophet inequality: Order selection beats random order. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 302-336, 2023,
Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. Multi-pant harti-parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM sympo- sium on Theory of computing, pages 31 1-300, 2010.
Y.S. Chow, H.E. Robbins, H. Robbins, and D. Siegmund. Great Expectations: The Theory of Optimal Stopping. Houghton Mifflin, 1971. ISBN 9780395053144 bookssid--A6LLhyceV44
URL, httphhttpt//bbott google. fr/

---

Jose Correa, Andres Cristi, Paul Duetting, and Ashkan Norouzi-Fart Fairness and bias in online selection. In International conference on machine learning, pages 21 2112-2121. PMLR, 2021a.
José Correa, Andrés Cristi, Laurent Feuilloley, Tim Oosterwijk, and Alexandros Tsigonias- Dimitriadis. The secretary problem with independent sampling. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2047-2058. SIAM, 2021b.
Chen Dang, Cristina Bazgan, Tristan Cazenave, Morgan Chopin, and HiereeHeent Wuillemin. Warm- starting nested rollout policy adaptation with optimal stopping. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 12381-12388 2023.
John P Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. Balancing relevance and diversity in online bipartite matching via submodularity. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1877-1884, 2019.
Marina Drygala, Sai Ganesh Nagarajan, and Ola Svensson. Online algorithms with costly predictions. In International Conference on Artificial Intelligence and Statistics, pages 8078 8101. PMLR, 2023.
Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. In Proceedings of the 22nd ACM Conference on Economics and Computation, EC '21, page 409-429, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781 450385541. doi: 10.1 11445/3465455634666623
org/ 10.
3467623
Evgenii Borisovich Dynkin. The optimum choice of the instant for stopping markov process. Soviet Mathematics, 4:627-629, 1963.
Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Proceedings of the twenfy-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 123-135. SIAM, 2014.
Ragnar Freij and Johan Wästlund. Partially ordered secretaries. Electronic Communications in Probability, 15:504-507, 2010.
Kaito Fujii and Hisashi Kashima. Budgeted stream-based active learning via adaptive submodular maximization. Advances in Neural Information Processing Systems, 29, 2016.
John P. Gilbert and Frederick Mosteller. Recognizing the Maximum of Sequence, pages 355- 398. Springer New York, New York, NY, 2006. ISBN 978-0-387-44956-2. doi: 10. 1007/ 978-0-387-44956-2222
URLp:tts:://dot org/ 10. 1007 900.1007797-00--88-4495-------
Mohak Goyal. Secretary matching with vertex arrivals and no rejections. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 5051-5058, 2022.
Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mecha- nism design and prophet inequalities. In AAAI, volume 7, pages 58-65, 2007.
M Hlynka and JN Sheahan. The secretary problem for random walk. Stochastic Processes and their applications, 28(2):317-325, 1988.
Sungjin Im, Ravi Kumar, Aditya Petety, and Manish Purohit. Parsimonious leamnig--agmentedd caching. In International Conference on Machine Learning, pages
PMLR, 2022.
Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil'uch: An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, pages 423-439. PMLR, 2014.
Zhihao Jiang, Pinyan Lu, Zhihao Gavin Tang, and Yuhao Zhang. Online selection problems against constrained adversary. In International Conference on Machine Learning, pages 5002-5012. PMLR, 2021.
Anna Karlin and Eric Lei. On a competitive secretary problem. In Proceedings of the AAAI Conference Artificial Intelligence, volume 29, 2015.
12

---

Thomas Keller and Florian GeiBer. Better be lucky than good: Exceeding expectations in mdp evaluation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Douglas Kennedy. Prophet-type inequalities for multi-choice optimal stopping. Stochastic Processes and their applications, 24(1):77-88 1987.
Robert Kleinberg and Seth Matthew Weinberg. Matroid prophet inequalities. In Proceedings of the forty-fourth anmual ACM symposium on Theory of computing, pages 123-136, 2012.
Robert D) Kleinberg. A multiple-choice secretary algorithm with applications to online auctions, In SODA, volume 5, pages 630-631. Citeseer, 2005.
Ulrich Krengel and Louis Sucheston. Semiamarts and finite values. 1977.
D. V. Lindley. Dynamic programming and decision theory. Journal of the Royal Statistical Society,
Series C (Applied Statistics), 10(1):39-51, 1961. ISSN 00359254, 14679876. 7/ www.. jww..stor... otg/stablee/985440
URL http:
George Monahan. Optimal stopping in partially observable markov process with costly informa- tion. Operations Research, 28(6):1319--333 1334, 1980.
George E. Monahan. State of the art-a survey of partially observable markov decision processes: theory, models, and algorithms. Management science, 28(1):1-16, 1982.
Manish Raghavan, Solon Barocas, Jon Kleinberg, and Karen Levy. Mitigating bias in algorithmic hiring: Evaluating claims and practices. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, FAT '20, page 469-481, New York, NY, USA, 2020. Associa- tion for Computing Machinery. ISBN 97814 7781450369367. doi: 10.1 10.1144/33519955337222 3337228. URL
https://doi.ont org/ 10. 1145/33511000 8332733333199333328888888
Sivan Sabato and Tom Hess. Interactive algorithms: from pool to stream. In Conference Learning Theory, pages 1419-1439 1439. PMLR, 2016.
Sivan Sabato and Tom Hess. Interactive algorithms: Pool, stream and precognitive stream. Journal of Machine Learning Research, 18(229):1-39) 2018
Karim Ahmed Abdel Sadek and Marek Elias. Algorithms for caching and MTS with reduced number of predictions. In The Twelfth International Conference on Learning Representations, 2024. URL / www.:eneeeooteiieeee net/EooruuitouuuuiiSsst
Jad Salem and Swati Gupta. Closing the gap: Group-aware parallelization for the secretary problem with biased evaluations. Available at SSRN 3444283, 2019.
Jad Salem, Deven R Desai, and Swati Gupta. Don't 't let ricci destefano hold you back: A bias-aware legal solution to the hiring paradox. arXiv preprint arXiv:2201.13367, 2022.
Ester Samuel-Cahn. Comparison of threshold stop rules and maximum for independent nonnegative random variables. the Annals of Probability, pages 1213-1216, 1984.
Sandeep Silwal, Sara Ahmadian, Andrew Nystrom, Andrew McCallum, Deepak Ramachandran, and Mehran Kazemi. Kwikbucks: Correlation clustering with cheap- weak and expensive-stree stronng signals. In Proceedings of The Fourth Workshop on Simple and Efficient Natural Language Processing (SustaiNLP), pages 1-31, 2023.
13

---

A Preliminaries
With the assumption that the group membership of each candidate is a random variable, 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 Lemma from Jamieson et al. (2014) to prove the following.
Lemma A.1 Jamieson et al. (0144). Let (X1) be i.i.d. Bernoulli random variables, N a positive integer, and m > satisfying n 8, then it holds with a probabiliiyy of at least N that
1A (x. - ((X.) 2 (m 1)t N
Proof. Bernoulli random variables sub-Gaussian with scale parameter 1/2, hence Lemma from 8
Jamieson al. 2014 with guarantees that, with probability of least 3( log )2 the
lollowing holds
Vt Z 1: (X. E(X,)) s 2 blog log(
8=1
Consider positive integers T < N, 2 1 such that N 8, and 8 2/N Then for all t [T.....,
log 2t)
2t
N Nm+1
5
and we deduce that
P 1 1: Σ (X, - E(X,)) S 2v (m + 1)tlog N
==1
V1 > 1: Σ(x, E[X,]) s 2 Vollog log(21) 2/N"
P
8=1
3(2/ log 2)
2m
25
N2m
In the context of the K'group secretary problem, adequately using the previous Lemma and using union bounds yields concentration inequality on number of candidates belonging to each group. Lemma A.2. Let N 2 max(4, K), and consider the following event
Yk E [K] 2 1: || Aut| s 4 log
which we denote by Cn. Then it holds that P(Cx) 2 1 NT.
Proof. The previous Lemma with N 2 4. m 3 and respectively with the Bernoulli random
variables X1, [[g: = k) and Xe, (gg = k), gives for all i {0, 1} and & E [K] that
25
P
Act) 4 tvglog.N .V) 2
No
and we obtain by a union bound that P(Cx)
>
50K No
Given that N > max(4 (4, K), it follows that
K
50
1
P(CN)
N
N
N2
N2
Lemma A.3. Let E be any event, not necessarily independent of CN (defined in Lemma A.2 then
P( CN) +(E)
14

---

Proof. We have by Lemma
A.2 that
P(E P(CN)
P
2 N²
2 .22
P(E Cx)
S 1+
P(E) P(()) +
N22
Using the same inequality with the complementary event Ee of & gives
P( Cx) =1 P(E (OE=ICNN)
(Cx) 2 1 (P()))
2 N2
P(()
N2
which concludes the proof.
Lemma A.4. For any and any B
we have
B
B-2
xC
Σ
S
E
B
+ 1j!
b=0
t=
Proof. Let x
> 0 and 2 1. First, observe that
b
8-1
20
e
xe x
e!
(1 1)!
b=0
t=
b=0
b=
b=0
8=0
therefore
S xe"
!
b=0
t=0
and we have
x
8
xe
c
Σ
(8-
B 1) e!
!!
!!
b=0
t=0
b= B-B
(=b+1
-B--b=BB4
BBB+
x BB2
6
!
(B+1)!'
t= B=
{=B+1
where we used for the last step the classical inequality
B
x B+1
5
(B 1)!
B+1
E=0
B Single-Threshold algorithms for K groups
B.1 Proof of Lemma 3.1
Proof. We consider that B 2 1. The case 0 treated separately the end of the proof. Let Cn
the event (Vk E [K], At 2 1: ||GH| - Abt| S 4 N). It holds that
P(A succeeds CN)) Σ
P(A succeeds, P 1, = - 1
N K K
P succeeds, R² = 1, = t, = L, l, = |
K
ΣΣΣ
P succeeds, R, + 1, = t.g, 1- = k CNN
(3)
15

---

In the following, we will estimate the terms in both sums. We recall that we consider K and (E to be constants, and T' = aN + o(1), with a also a constant. All the O terms appearing in the proof are independent of t. as T S t S N. they only depend on N, T/N parameters.
o(1), and the constant
For t E (T, only if 2t = mmax The event Hy = Tmax is independent of the group membership of the candidates, thus independent of Cv. and its probability is 1/N. The event 9t E, however, not independent of Cv. but Lemma A.3 gives that P(ge = é Cx) = P(ge f) + O(1/N²) = Xe + O(1/N3).
if
and R, 1, then the Algorithms stops 2t, hence its succeeds if and
Therefore, it holds for all k & E [K] and (T ..... N] that
P(A7 succeeds, RS = L, = gt = 9 = k CN)
= =P( = Tmax: PI 2 gt = L, -T (NN)
Paat = Tmax) P( 1 Cx) 2 -1 = k |NN)
de (N + 0(1/N9)) P( 2 -1 kb [1Cx))
Note that, for the single-threshold algorithm, we have the equivalence P1 = x P 2 and r. =
1. The event P1 2 happens if and only if no candidate F, for s E (T....,t 1} in any group m E [K] exceeds the best candidate seen up to time T 1 in the same group:
Vt 2 T: (p1 2 t)
(vm E [K] max GTa-1 < max GTT-1)
with the convention max 0 = - co. Consequently, if p1 2 1, then -- = k means that the best candidate in all groups until time belongs to group G1-1- Using that T = ((N), this yields
P(Ap succeeds, R. P1 9. - = k CN)
de
P(p 2 and max Gy-1 CN) 0(1/N3)) N
Ae
N 0(1/N9)
P(max Gh-1 CN) 2t maxxxa-111-11 Gh-1, CN)
d
( (Aa(T- - +0(1/N))
- P(p 2t /ttmaatt/miitt G Cn)
0(1/N9)
N
t-1
TedRT
+ +O(1/N9)
P(vm [K] \ {k) max GTa-11 max G Cn)
Nt
T
+ +0(1/N*)
G II mylk
E
CN]
Nt
IG
Am T + O(VN log N)
+ +011N23)
II E
Cn
Nt
Amt O(VN log N)
matk
(DEART
+ O(1/N3))
II mork
Nog N o(
7
NL
TEART
Nt + O(L/N3))
TK-
-K-1 0 (v
log (VooR(())
dede (T/E)* + +o(v
log N
(4)
On the other hand, regarding the terms of the second sum in 33, if p1 1 but Rg / 1, the Algorithm uses comparison to observe R, but then skips to the next step L 1. The budget at step L+ 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 + is fully determined by B - 1, o and the
16

---

number of candidates seen in each group so far, which is controlled by Cy. We deduce that
P(A succeeds, Rs # 11 = =t = 1,- = =k(CN)
= P(A succeeds + 1, = 1, = - = ki Cn)
(5)
x P(R + 1, P1 = gt -T =k(Cr)
P(4 succeeds
g = k. CN ((Re + 1, = 1, = 11 = &<Cx,,
(6)
where 1 succeeds) = 0. For& l = k, the probability P(Re o 1, = 1,9t = 1
Cv) is zero, because if 04-1 = k, pr 2 and 9t = f, then the best candidate up to step T - belongs to group G*, and no candidate v, for s E (T.....
1 is better than the maximum in its group seen before step T - 1, thus if xe belongs to G* and r2 = then necessarily R2 = 1.
For l + k, it holds that
P(R, + 1, = t, 1,-7-1 =k CN)
P(p1 = g, l, max I1:t E GG CN)
= P(maxXx1 11:1 E G Cx)Pp(p1 = t, = { mmx Z1a E -1 Cn)
(A -1) +0(1/N3))
1-1 (
P(p = 1, = l maxxti E Gk Cx)
ART +0(1/33) P(g+ = el CNx) PP Gf.--1 < max G < Zt
and Vm E [K] \ (k, f max GY:-11 < max Gm (NN)
AxT + +0(1/N2)) ) (Ar + O(1NN3))
G
Cn
E
Cn
1
|G- I+1
m (R,
DodeT + +0(1/29)
1o 1 G
E
CN
E
Cn
GI,,II 1+1
GT_
mg (A:E)
Xehur + +(1/19)
T
log N +0(V
II
T
0
log_N
Tppt
NJ
mE(k,e) TK- сくー2
DeAUT
+ +01NN33
T 1pp2
+
+0
log N Nº
log
t
IK+I + oO(
Jog No
where used in the last equations the event CN and the assumption T O(N). Therefore, substituting into (6) gives for all e, k E [K] and t E (T,...,NV that
PAA succeeds, Ru # 1, 1, = - = k: CN)
T
+0
log N3
+
1(k: + E) P(A succeeds gt = CN)
tK+T
A
1(k + 2) P(A 1-1 succeeds, 9² = 1 Cr)
tK+1 +0(1
log N No
P = k CN))
AKT
P(A succeeds, gt = k. Cn)
IK+I +0
log No
1(k +
d + 0(1/22)
TK
+ 0 (V
log N3
1(k + P(A
B-1 succeeds, gi = k Cv) (7)
tK+T
17

---

Finally, substituting (4) and into of t, gives that
3
and recalling that all the previous O terms are independent
P(Af succeeds
| [CN)
N
ded
(T/t)* + +0(v
log No.
k=
N
K
T
0
No No
P( 1-1 succeeds, 9i = k (NN)
pK+1
k= EGEk
(1 1 10g
N K
K
dede
(T/1)*
N
k=1
T
P(A B-1 succeeds, oi = k: Cx)
tKI
Eykk
= =1++ (v Jog
K
N
+ (K
-1 Σ
N T
kK P(4 B-1
succeeds Cx))
tk
Using Riemann sum properties, we obtain
T
(/NN
N Σ E
(1/N)K = aK [: du
uk + O(1NN) a a
--1 + +(1NN)
N
N
and by Lemma
A.3
we have for all t E (T...., and b 2 0 that
P(A succeeds CN) P(A, succeeds) + O(1/N2), Tk with the O(1/23) independent of t. Observing that ΣiST pK-T that
1-0 x K + =11
= 0(1,, it follows
(a-a- K
N
T
P(4f succeeds) = (1+0 log N
(K -
Σ
k+ P(A B-1 succeeds) + +
K-1
a - K
N
Tk
K- + (K-1)
- 1)
Σ
P(A B-1 succeeds) + ( N))
log N
kK
t=T
This concludes the proof for B 2 1.
For B 0, P(4 succeeds (Cx) can be decomposed as in 33) However, the terms of the second sum are all zero, because if P1 = t then the algorithm stops at t, but since R * 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 obtain
a a K
P(A succeeds)
K 1 + (
log N N
B.2 Proof of Theorem 3.2
Proof. Let E (0. constant. For all [a, and B 2 O, denote by (B the limit lim ((A succeeds) for t = [.N We will prove by induction over B that this limit exists for all {|a, 1], is equal to the expression stated in the theorem, with instead of a, and satisfies
P(4 succeeds) = ( + OVV log ), with the O term only depending on a and the other N constants of the problem. In particular, the O term is independent of t. For B = 0, Lemma immediately for any E (a, 1] and = [w:]] that
gives
P(4 succeeds) = w K
W.KK K
1 - -1) + +0 N
K - + ((V
lox
-1
18

---

The O term depends on f, but using the inequalities + o(1) - t/N I 1, it can be made only dependent on a. Let B and assume the result true for B Lemma 3.1 and the induction hypothesis give for all w E [ax 1] and i = [w.N that
P(4 succeeds)
w K
(K - 1)
P
B-1 P(A
succeeds) + +0V
log,N N
K
sk+1
w
t
K + (K-1) Σ
6
BB
1+1 +0
log N N
+ +0
log N N
sk+1
N
w
(t/N)) N
K - (K -
0(1
log N
N
(s/N)
where we used that the O term in the induction hypothesis is independent of 8 and that
NK N
N
1 N [s/N)K+1 0(1).
Σ sk+
Σ
K+1
Finally, I/N- = w + O(1/N, and BpB-1 is, by the induction hypothesis, a continuously differentiable function (a, 1], therefore, it holds by convergence properties of Riemann sums that
P(4 succeeds) = w w
+ (K - 1)(wx + +0(%))
( ukt
du + +0(k)) + +0(v log
K -
w w K
K 1 + (K 11w Sr -0- du 0(1 loR
(VLogN)
where the O term depends on t and the constant parameters. Using that T = LaN] the can be made dependent only on a and the other constant parameters. The limit 4p (w)) lim (AA [wnj succeeds) therefore exists, and is equal to
W w K
S'' (u- uk+1 du
(w)
+ (K- -1)
The induction hypothesis gives for all E [a, 1] that
u
B-1
1
log(1 (//u1/uu -1
B-1
K
uk
Cl
b=0
8=
hence
(K 1) S
(u)
B
log( /uu K -1ze
du
du
uk+1
uk
Elu
b=0
e=
So du
B-
log(1/u k/
Bw
uk
w
du
0=0
t=
-1
B-1
1og(1/uk<11)
KK
K
(K - 1)u
(K - 1) + 1)
10
Bun
B
b
log(1/ [0g(1/wK-11 -Iye4
WK-II 1)
w
K -1
(K- - 1) + I1!!
b=0
Bwn
1
log(1 0g(1//= -ipe
wk-1 -1 1)
K
K-1
(K 1)
bm
k
B
b
log(1/w
Wk-1
!!
b=1
t=1
K
B
log(1 /w
w
K
WK
!!
1=1
8=
19

---

and it follows that
w k
1
1
b
log / 1// j0
B
(w)
K
-
wk-1
+
wK-1
1
b=1
F=
w
log(1
/ 1// 12ee
K
w
1
b=0
E=
In particular, this identity is true for w which gives the wanted result.
Infinite budget
Taking the limit for B + oc, obtain that
lim lim P(A[aN] succeeds) = lim (w)
B-000 N0000
B-000
00
log(1 log(L/a"~11²
a
K
a
E!
b=0
1=
a
K
8
log(1/ log(1/aK<1je
b+1
a
e-1
log( 1/111aa 12
K
e!
t=1
b=0
K
log (1/(1/"" 11
a
K
1)!
K log(1 (g/(1//k/ K-1)
log(1/aK-1))
K-1
E!
2m0
a log(1/o)
aK-1
a log(1/a).
B.3 Proof of Corollary 3.2.1
Proof. Let a E (0, 1) and T =
[o:N]. Lemma A.4 gives for all x >> 0 that
B
b
(1- (B + 1)1
B+1 x
Σ
2 xe"
e!
b=0
in particular, we obtain for x log(1, (og(1/ctt
(11) that
a
log(1 log(1/a
lim P(A succeeds) = N-000
aK-1 Σ
K - 0=0
f!
t=
K
log( log(l/a
bog(1/a* (Bg11/a--1881 -1)
1
K -
ak-1
(B +11
(1- (K-1)) 1)441 log(1 1/a)
a log(1/a)
(B+ + 1)!
Taking a threshold T = [N/e] gives
1 (K - 1) P(A succeeds) > 1
lim
N
(B + 1)!
To achieve an asymptotic success probability of at least
1-g for some : > 0, using the inequality
m! 2 m)m)" "h it suffices that K and satisfy el 1+ 1811
(K-1) 941
< e, which equivalent to
B
K k1
(EE) गो.
20

---

C
Static Double-threshold algorithm for two groups
C.1
Recursion lemma
We first prove recursion satisfied by UR N. 2p. which use to prove the subsequent results in this
section.
Lemma C.1. For all B 2 0, EE (LaN] ..... L.N] - 1}, and & E (1,2), UR satisfies
[[..........
A L8Nj-1
U
UN
Σ
P(p 2, |NCN)
18N
1(B > 0)
Σ P = k. =, R, # CN NN
1-X
P ((A (a, B) succeeds, -i = k1 BN Cx) O
Assuming that P1 = (t..... |8N] 1}, the first sum corresponds to the success probability R. and the algorithm selects the candidate x.. The terms of the second sum represent the success probability after using comparison at step s but observing R. F 1, resulting in the rejection of the candidate. Therefore, the available budget step + 1 is B 1, and necessarily D 2, because comparison at step can only occur if gs = 1 by definition of the algorithm. Hence, only the term UN appears in the recursion, not UR 8-1 1, Finally, the last term represents the probability of success if no comparison has been made before step [
Proof. Let B 2 O. For all E [LaNJ, [aN] - 1) and k E [1,2), it holds that P(Af(c (a, 3) succeeds, 9i-1 k CN)
UR.
L@N -1
Σ P(A (a. 3) succeeds, -i-1 = k p1 = IsCC))
==
+ P(A B (a, B) succeeds, -i k. P1 3N [CN)
[AN -1
Σ P(A 3) succeeds, - = k. 8, R. = =1 CN)
(8)
19N
P(A (a, B) succeeds, gi k. P1 s, R. # CNC
(9)
+ P(A (a, 3) succeeds, gi ki 2 3N Cx)
(10)
For all 8 E (t...., [BN] 1]. by definition of Algorithm A 3), if p1 and R. = 1 then the candidate v. selected, and the algorithm succeeds if only x, -max Moreover, the event {pr = $} is equivalent to {p1 2 s.9, = 1,r, = 1}. hence the terms in ( can be written as
P(4 (a, succeeds, -. k.p s, R. CNn)
=P(x, Tmax: -i-1 k, s, R, = 1 CN)
P(æ, = xmax: - = k, 2 s,g, = 1 Cx)
P(g= = CN)
P(p 2 2 = k CN)
N
+ +O(
P(pi 2 2 k ((xx).
N
21

---

where used for that the event {z, Imax] | is independent of the group memberships, thus indepen- dent of Cv. and that it is also independent of {pi 2 s, -i = k), because realization of the latter event is determined only by the groups and relative ranks of the candidates {z1,--.. 1x-1). For the last equality, we used Lemma A.3
Secondly, in the case where P1 = s and R& * 1, if 0 then the algorithm selects candidate which is not the best overall, hence its probability of succeeding zero. If B 2 the algorithm makes a comparison but then rejects the candidate. Moreover, for E [t, 8N. if p1 8 then necessarily I= = and having Rg * 1 implies that 9 2. The success probability of ( given that f1 s, R. o is the same as the success probability of A (a, B) given that g; 2. Therefore, the terms of (9) satisfy
P(4 (a,,9) succeeds, 9 -i-1 =
= k: 8, R& # CN)
= 1(B > 0) P = k1 = 8, R. # 1 P(A, (a, (3 succeeds 9 = K1 = 8, R. # 11,CN)
= -(BB > 0) P = P, R, # |Cx) a+1 (a, B) succeeds 9. = 2, CN)
P P (a, B) succeeds, S 2 CN)
= -1 > 0) P = = =k * (xx))
P = 2 CNC
N, = 1BB > 0) P = k; R. # --
where we used again Lemma
A.3 Given that the O terms are independent of 8, We deduce that
|AN
(x+ (
4 N.,K
Σ
P(
2 8,00-1 = k CN)
[AN]-1
+ +1(B > 0)
1 [i- + 0
Σ
P =
C1 N1
8=1
P(A (), succeeds, 96-1 = p, 2 BN CNN
[8N1-1
Σ 2(128,9 = (NC)
N
8=1
18N]-1
1(B > 0)
Σ P K, 8, R2 # 1N CN
P(A (cx, B) succeeds, -4-1 = k, 2 BN CN) + +
C.2 Additional lemmas
In the following two lemmas, we compute the probabilities appearing in Lemma C.I for all (I...., [aN] 1 and & E (1,2)
Lemma C.2. Let [aNJ < < [3N], and consider run of Algorithm A& A((,, B), then it holds that
P(p 2 28 = =1 1|CN) = (1 X)t As
+ +0(V
log N
(1 - 2)
= P(M 2 = CxC = ((1 X)t As)s + +0(V
Jog N
N
Proof. Since there are only 2 groups, the event gi is equivalent max G? < max G For 8 E (I...., [GN]], Algorithm A (ax, (3) only makes comparison (or stops the case of B = 0) at step only if g, and r, 1. Therefore, P1 if and only if no candidate belonging
22

---

to Glas-1 surpasses the maximum value observed in G
P(p 2 s. -7 = 1 (x) = P(max G i:s-1 < Gi-1 max max Gh-1 < max (x)
P(maxx (C) 1: U CP-1) < G Cx)
G7-1l
E
CN
| + | + Gh-11
G4-1l
E
CN
1 + |G Lis-1
Xt + O Vlg N)
1 + A(s - 1) + OO log N)
(1 A + +0
M
log N
For the case 9," = 2, we obtain
P(p 2 s, 9 = 2| Cx) Pmmax Gha-1 < Gl-1 max Gi-1 < max G2-1 Cxx
max Gh < G < max G7 (Nn)
1G--1l
E
CN
G 1-1
+ |0 10
+ |
G G +
G7-1l
|G
E
CN
- + |G
(1- A)t + O / log N)
At + OVVN log N)
+ X(s -) + OOV VVV.log
log N)
As + 0 / / log N)
((1 - -jE + Asjs + +O(V
(1 1)t?
1og N
Lemma C.3. Let [aN] 515 [ and consider a run of Algorithm Af 3), then
P(P R, # 1, -/ = 1| |Cx) = 2² () - t)t
log N N3
((1 - A)t + \5) +
V
(1- A) ((1- A) + A(2 - A)s) t2
P(p = R. + 1, 24 21 2(Cx)
+
log N +0(V
((1 - A)8 + 2s)22²
No
Proof. For Algorithm A," (a. B) and (t..... element in G since step for which r, = 1, thus
[NN] - 1), P1 = s if and only if x. is the first
Is and max G/as11 < mmax G/-1 < <3.
PI A.3 gives that P(g. CN) = P(g. + =1)+ O(LNN) X O(INN)
Furthermore, Lemma Therefore, it holds that
P(p 8, R, f 1, -1 CN)
P(g. 1, max G < max GL-1 < Fs I, < max 02 G max G max G.-, CN)
P(g. CN (C))P((n P(max G1.s-1 < max G|_1 < K. < max G2 Gt.--1 max Gh-1 < max G CN)
= P(g. = |CC)
P P(max G/
1:--1 U UG? < max G < x, < max G2 CN)
[G|
(A+ ((
CN
1|
|+ 1++
G +0+
[G2 G
(A+00 (++)
G
CN
++ |G/,_1
8:
Volg (A+ ((+))))) (1 ()(s - 1) + 0(v / log N)
At + O(vNlog N)
s(t + A(s +) + 0 / log N))
+ X(s -t)
X²(1 - () - t)t + +0(1
log N3
(11 - AJt As)2
23

---

On the other hand, in the case where 97-1 2, we obtain
P(pi s, R, 1,97-1 = CN)
P(g. =1, max Gr.a-1 < max G/-1 < 2, 2s < max -a max G max G2-1 CN)
(max G G1.3-1 < max - < v, < max G maxx < max G.- Cx) P(g, = CN (
P(g. CN P < max(c, b < cn)
where a max G 1, b- max C -, max G and d = max G2 Let us denote by E the event (a b < Fg max c). It holds that
Enfo< d (o [(<b<cc<acc@/lo<caccccd
Entd<ck {a (ucbb<aa<mmcccc))ucchhcc
which yields
& = (Ent
= boooeccc.cclllbbbaa.ahcccccce/ee
= <a<b<<<<, fo
The two events above are disjoint, and we have
P(a <b<csbces < <d CN)
P P(max Gha-1 max GL_1 max G2-1 Ig G Cx)
10P
|C
G 1 G
CN
G G|, +1+ Gha-11
1+
[G
HGL
G2 1
1
GG 1G-_1
G
CN
=
1-
G
(1- A)(s t) + O(VN lo
(1- A)t + 0 log
Xt + OOVN log N)
s(t + A(s -0) +)+
O0 log.N))
++ X(s - t) + +ONN Nog.logg. N)
As + O(vN log N)
(1 1)-))s(s - -1)2
0
Log Na
((1 - A)t + 25)
The probability the second event is
P(a <bc <c| CN) = Pmmax G < max G < I, < max max (x))
10
co
= E
CN
+1+ G
C [
[ 1ot-11+00 |+
GG
G|-11
E
CN
t+ Gl Glasnl
GG G +1
G
(1 - X)1 + O(VN log N)
At + OOVN log N)
+ X(s - t) O /Voog
is + OVVNlogN)
As + log N)
(1 (1
+0(
log N8
A((1 A)t As)s²
24

---

Finally, Lemma A.3 shows that P(g. = 1 = =x))=+++11NN3) and we deduce
P(p:- = 8, R. + 1, - 22| = XP(E| | (x)+)
XP < <b<c<,, < d CN) + XP <b< + 0
1(1 - 1)7 t)t²
X((1 A)t Asss² + +0(V
X(1 - -AjE
log N=
((1 Ait 2s)
(1 - -))2
(A(1 ->((s -t) + (1 -)tt As) o(V
log N Na
((1 Ait >2)
(1 2)12
(11 2) + X(2 -))s) =o(v lor N
((1 A)t >s)?s²
Lemma C.4. Let LaNJ S <<< [BN and consider run of Algorithm Ad (ax, B), then
P(A (L, (0, succeeds, pr 2 BN, fi = CCC
u
1.NN...1 + ((1- - A)t + A8N) (N.LaNJ.2 + O(V ((V1022 log.N)
A(3N- - -ttt
uB
3N
P(A (a, 3) succeeds, p1 2 BN, gi 2 CN)
1 (11 - Xjt + 83
12
11N112 + (V
log N
Proof. Since Algorithm A (a, B) is memoryless, if it does not stop before step [3N], then its success probability is the same as that of ALAN (a, B) Al (3, B), which has the same threshold 33 for both groups if it is in the same state [[[a))- G (aNy))) (). In all the proof, P1 is relative to Algorithm A (a, (),, not A (B, B). It holds that
P(A (a, succeeds, 01 2 3N, - =1| 1(C))
Σ P(A (a, 3) succeeds, p1 2 BN, 1, 1.9 CxC (E(1,2)
=E P(p 2 BN -i = =1, 1 = =((Cx) =1((()))-=(((x))
=
(E(1.2
x x (ax, B) succeeds | -N, - = 1,9 = -
= Σ
P( 2 BN -i = L, L = el ((C)) succeds
succeeds 1i = C,CN)
(E(1.)
P(p 2 3N, -N = L, 1,NN = el ((Cr) P succeeds, 9 1- = e (CCN
= Σ
P(g P(NiAN]-1 = 8 CN)
(E(1.2)
UB N.INNJ.
Σ (E(1.2)
P(m 2 -N = -NN -1,
e(CN)
P P = -) 0
25

---

where we used Lemma A.3 and the definition 2 of U. Let us now compute the probability of the event (0r 2 AN, -:-1 1. Ef conditional to Cx. For l = 1, we have
P(p: 2 -N, = -1 = 1
= P(max G GEIBN--1 -1 < max Gi-1 max Gp-1 < max G/-1, max G [3N] < max G
[BN] -1 CN)
P(max #1: E G/-11 (Nn)
GGL-1 [BN]] CN
At + O / Nog N)
At
Nog (V
= AN + (1)
3N
+
N
For f 2= 2, we first compute the following
P(p 2 BN, 1 11CN)
Pmmax C 11 < G max C.-1 < max (xx
([Imax(G/aan]- U U.--1) < ma (xx
GL-_1l
E
CN
G (G + |G |
At O log N)
t XBN + O(VN log N)
N
+ -0
No N
(1 Alt + A8N
and it follows that
P(p 2N, = 1 2 -
P( 2 3N 1 Cxx - -P(pi 2 28N. -. = -1 1lc))
At
At
+0(1
Log
-1- - (1-x)t+ A)t+ ABN 3N
NV
X(1 AL1-ADy A)(3N t)t
+ 0
(V/1021)
1og.N)
-(1- - ((1-A) ABN)SN
N
All in all, we deduce that
P(A (a,, 3) succeeds, P1 2 BN, 1
Al
+0(1 Nog
UN
((1-A)t ( A3N)88 + (V(DOR)))
A(1 X)GNN - 1)L
1og N
U N.NNN.122
=
BN
+
1+0
+
I- x 0 MZ)
t.
O0(
log,N) N
-)tt + ABNNSN +0(V (ORR
A(8N -)t
1oR )) UR.
BBN BN
+
t.
A(8N- t)t
U UN +0
log
+
BN
((1
Ajt ABN)
26

---

On the other hand, if 97-1 = 2 and P1 2 ,NN, then necessarily gjeN = 2, because no candidate
in G' up to step [ surpasses max G!_ which is less than max G?? - Therefore
P(A (a, (3) succeeds, p1 2 3N, gi 2 (N)
= P(p1 2
= 2 CN PP4 (a, p1 2 -T = =2
= P(max G 1-NNN-11 < max G2-1 < max G CN)P(AR (B, 1 = =2, CN)
G
GG--l
P(AB (3, 9INN-1 = 12(CN)
E
CN
C 11LNN--1
[ANj-1
PL = (NN)
(1- A) + OV Voog N)
XL + OOVN log N)
2 19N12
1+ A(BN - 1) + O(V N)
ABN +
N)
1- + O
= -(1- ((1- ABN) LN.LON + +O(v
U
N
In the following lemma, we compute the exact limit of 2 J. when the number of candidates goes to infinity.
Lemma C.5. For all B 2 0 and h: E (1,2).
u UN.LSNIA 2n,32
Σ b=0
1
log(1 log(1
log N + +0(V
N
Proof. By definition 2 of Uf K, we have
_ P P(A (an)((a,))) succeeds, 9 = k |
threshold algorithm with threshold BN and budget B. Let T = [8N]. As in the proof of Lemma 3.1 we decompose the success probability of A [BN] as
and AA ] (a. B3 is simply the single-threshold
follows
UR UN,T. P(Af(c,
(cx, B3 succeeds, 97 ks Cx)
N
Σ
((A 3) succeeds, PI = 1t = 1 1 = k.
t=T' (1(12)
N
Σ
Σ
P(A 3) succeeds, P1 = -t, R. = 1,9t = l, 1, =k Cx)
(E(12))
PPA 3) succeeds, P1 = t, Rd * 1, gt e, - = Cx)
The terms appearing in the sums above were computed in the proof of Lemma respectively from 44) and 7 with K 2, that
3.1
foolows
P(Affa,))) succeeds, en 1, Rr gt - = Cx)
dede
log (T/1)2 +o(v
N
No
(( 3) succeeds, P1 = t, RR * 1, = l, E, = k Cn)
T
+ 0
log N N
1(B> 0,k # 4) B-1
13
N1+11
where the O terms are independent of t, they only depend on B. Therefore,
U [ (1+0(V
No
Σ
N
ded N
(T/1)2 + 1 1(B > 0, + t)
7
T=T
(E,1))
log.N = -(1+0(v
Σ
N
d
(T/t)+
+ T2 t
1(B > 0) 0) 1N
N
N
27

---

The first sum can easily be computed
R N
\T(T/N) N N
(T/t)²
Σ 1=T
(t/N)²
= + +0())) / du
3)) + O
Therefore,
UR. = -(1+0(/2x) 1orN ) (Ma3(1 -)) 0)
N
T
Σ
U - -0(+))
1
:=T
= -) 1B > 0)
Σ
N
T
+0(1
Ing
N.++k
1=1
Dividing by A yields
( B(1 1)
1(B 0)
Σ
( M.++in + +0(v log -
T
( N
T=T
thus the double-indexed sequence (A,- 1 N. )b.t satisfies the same recursion and initial condition as (P(4)(00, 0) succeeds])o. (see proof of Lemma 3.1 with | instead of w and K = 2. Therefore, we deduce immediately that:
log(1/33))
) +0(v //ogNN) )
B²
N.T.R
8
E!
b=0
t=
C.3
Proof of Lemma
Proof. Using Lemmas C.I
C.2
C,3 and C.4 for ts = 2, we obtain for all & E
1}
[-N]-1
(1 - A)
UB N.2
+ +0 NV
(11 A)t + As)s
e=t
+ 1(B > 0)
[NN-1
X) ((1 A) + X(2 1(2- A)s) t²
+0(1
log +0(V2x
u
1-X X
((1 A)t + 232
No
s
+ (11 - A)t + ABN)8N N,N + (0(
UB
log N N
The O terms inside the sums depend on the ratios I/N and s/N, but using that a S L/N < 1 it can be made only dependent on and the other constants of the problem. Moreover, Thus we can
28

---

write
LAN -1
U8,02
X(1 - A)t²
Σ
1
N
((1 21( + 28)8
s=t
[AN]-1
((1 ((1- + X(2 A)s)
+ > +1)
Σ
11-11 1,2
((1- + \s)
s=1
B N. + OV
log N N
+ ((1 - \ + A3N)
I-N
= X(1 () N
Σ
((1-A) + +
LØN (1- 1 + +1(2 A)
+ +I > (
2 1
Σ
u 1-1 N,
N
(1
+ 3
(1/N)²
N. + 0
Loy N
+ ((1 1) A3)S
Taking t = -L = N + 0() and using Riemann sum convergence properties yields
1-
[SN]-1
2 N
Σ
2
Σ
1 ((1
+ +++))
N
(
N
(1= + N
s=t
[
8
du
w
+0(#)
((1
A)w Xu)u
w
du
du
+0(+)
1 X
w (1/2 -1) + 1
w
(- (-log(w/ w/3) - logg1 - A + 13/w)) +
1- x
w log ((1 A) o/ + + +0
(11)
1
On the other hand,
(t/N)²
2² + +
((1 - x + A3)3 ((1 Ajw + XB)
and Lemma C.5 gives for 1: = that up8 (a, 3:5) exists, its expression is
l))(1/3)
2 ( 3:3) = (1 1)
(12)
e!
E=D
and it satisfies 4 N.,,8N,2 = p."(a, B: + 001
lop N N
Consequently,
u UNIwNNj22 = -A log ((1 2) +
1(B > 0) w² LØN
(1 - X) 2 w + X(2 A) & ((1 A)w + { N.
Σ
2
22 (a, (; + 0
log N N
(13)
(11 X)w + AB)
Using this equality, we will prove by induction over B 2 that, for all w E [a, the limit (a, Bü w) == lim u W.I.W]].2 exists, is continuous, and satisfies
2 N.NNN. = (a w) + @ Jog N
29

---

Initialization. For B = 0 and w E [a, 8]. 13)
gives immediately
U [.NN2, lo ((1-)) + +1)+ + ((1 A)8 + AB) 02 + (V) (14)
w²
Induction. Let B [a, B], and assume that 24
[NN (o, + OOV log N
N
for all [a, where the O does not depend on u. Using this hypothesis for with 8 E (t........0. 1}. along with te continuity of 422 (a, 3:-) and Riemann sums convergence properties, yields
2
[8N 1
(1 u + A(2 x)
Σ
((1 A)w + +)$)² U R-1
1,
[N
w² LAN 1-1
(1 2) + X(2 X) 2/4
Σ
B-1-
(a, 3; x + +0(v
log
((1 A) w + x x { P2
N
s= Lw:N
(1 2)2 + X(2 - X)u B-
2
((1 A)w + Au)
222
2 B; u)du + +0(1
(a,
log.N
N
Therefore, we deduce by 13 that
N,NN2,222 -xw log ((1 1 + +A)
2 (1 \)2w X(2 A)u
4/2 (a, 3 u)du
((1 N)w Au)zu2
w²
((1 A)w + 28) 22 (a, 3:3) + +0(v
log N
N
This proves that 4
[, = 4p 3:w) + +0(1
log N
where
22 (a, w) - log ((1 2) + 2)
1
(1
2) + A(2 A)u B-1
+ u
42 (a- udd
((1 x)w + 22
w²
+ (11 A)w + >B) 2 (ax, 33:3)
where the expression of o (a,, B3 B) is given in 12
30

---

C.4 Proof of Lemma 4.2
Proof. Using Lemmas C.1
C.2 and C.4 for l
2, we obtain for all & [laNJ..... L3N -1}
[AN -1
UN
Σ
Ait As + +0(v
AL
log N
N
s=t
[8NJ-1
1(B > 0)
Σ
A22 - ()(s= - -ttt
log.N +V(v
UN.++1.2
1-X
((1 - A)t + \t)3
No
BN N.8NI.1
((1 A)t + A3N)8N J. +
A(3N- - -1)
U
+vV log
(2(NN)
ON
Σ
N
(1- + N
18NI-1
+ 1(B> 0) X²(NN)
-
Σ
N N
U
N
((1- A) N
+ 2
N.
N
t/N
B N.N.NN.1 +
UR
A(3
N. N.N.NN.2 + o log
((1- 1) + +BBB8
Consider in the following t LwN] = wN + O()) Using Riemann sums convergence properties, we have
(t/N))
L8Nj-1
Σ
1
22w 6 (1 A)w + Au + +
du
N
(1 (1- + N
Aw [log((1 A)w + Xu)] + +
Au log (1 - X + x +
Since ur. $ 1 for all b, s, k; and t. wN + O(1), as in the proof of Lemma
we obtain
U [NN[=N]1 Aw log (1 - X 2 (
X2w L8N
+1 0)
Σ
UB-1
N. + +
((1 A)w + ) N
[=[
A(3 w)w
+ ((1 N)w + 1,333 N.L.N ,2 +
u
log N
Ao (1 -
X2w [ØNJ-1
+ 1(B 0)
Σ
N
u 1
N
((1 X) w
X 12
2
N.+112
[=[=N]
+ w B
8 11 (a, 3) +
X(3 - w w
22
B (a,, 3:33 + +0(v
log N
((1 A)w AB)
where we used Lemma C.5 in the last inequality, which guarantees that U
2x8 (a, 3:33)
va,
0
log for & E (1,2), with
+ (:9) 82
Σ
1
log(1/8)*
3
6=0
31

---

Denoting by (:, = (a, + (3,,,; ie. B²(a,
1 A P (a, B), we
have
3 3 (, 3:3) + ((1 - Ajw + \3) 92
w
B
1(3 w)w
B (a, (: =
Aw
1(1 - 1)(3 w/w
4 (a, 3;
B
((1 A)w + X3)3
Aw
(1 - A)(3 - w)
1 +
40 (a,
3
(1 --J-w + AB
Aw
B
B (a 3:
B
(1
X)u + X3
Aw
8 R. (:33.
(1
A)w
+ A
Thus
Aw
u [N.[uN],1 = Ao (1 X x+
w +
10 (a, 33
(1 - A)w + AB
[9N
IB > 0)
X²w
Σ
N w
u B
+ OV
Jog
(15)
N
((1 2) 1)w
N, 1
==
N
Now, we will prove by induction over that [N.L.NJ. xf (a, 3: w) + 0 (V
xx for
all
w E [a, 3). with ppf((, (a, -)- continuous function satisfying the recursion stated in the Lemma. Initialization For B = 0, [55) yields immediately for all w E [a
UN, [wnj,, Aw log (1 A x+ x + (1 A)w + X
Aw
4 B (a. 3:33 o( log N
Induction Let B 2 1, and assume that 14 B-1 [,LuN = कp (a, 3; u) + 0 and that o (a. (;-) is continuous. Consequently, using Riemann sums convergence properties, holds for all w E [a: 3] that
log N
N
for all u E [ax 3).
|.N 1-1
Σ
UB-1 UN
N
((1
a)w
2
==
N
N
[NN -1
2 w
N w
B B-1 la, B: ++ + 0(1 lor N
P2
N
A)W +
[o
|NN--
X
w
(a, B + 1
B-1
+ o(v Ing N
822
N
((1 A)w + X )2 N
[WN]
(u - w)42 B-1 (a. B; u)
= X2w
du + O (vV
log
((1 Ajw + 2u
N
thus, we have by substituting into 15
Aw
N.LNN = Aw (1 x+ m1)
+ (1 Ajw + 23 x0 "(a 3:13)
+ x2w 1"
8 (u (w=w)pg B-1 (a, 3: u)
du + (V//R
1ORN x
((1 - (1- + 22)
= (a, B:w) + 0
log N N
32

---

C.5 Proof of Corollary 4.3.1
Proof. Assume that À 2 1/2. For any thresholds 0 < S < Theorem 4.3 yields
lim (aA succeeds) 2 λι log (+) aB3* N-000
We will now determine thresholds maximizing this lower bound. For fixed B, we have
i
da (Aa log (2) aa35 2
A log
[ X + 38 (3)
Alog
(g) S 3S (B) -
8 exp
3 SB
This proves that, for fixed B the lower bound λa log (:) + a:35 (B) is maximized on [0, 3] for min(3, _ exp( (3 = (B). With this choice of a, the optimal choice of / is the one maximizing the mapping + Ah (B) log (पक())) h (B)
In particular, for B 0, obtain âg A exp( { 2) and Bo A. They guarantee asymptotic
success probability of least 2 exp(+ 2). Given that the sequence (5 (w)) ø is non-decreasing for all w E (0, 1], it holds for all B 2 0 that
lim P(A" 3B) succeeds) 2 Aā log ( + aB ((B)) 00000
{ Aa ( + a.5 (3)
max asd
{ Aaalog ( + a (3)
max o53
Aāo log
de ) + u0 (36) (
X2 eeep(( - 2)
2 - ( - 1)A(1 A)
On the other hand, taking equal thresholds 3 then using Corollary 3.2.1 with K = 2 gives
lim (a succeeds) > max { Ao fa log (2)+ a33 N
a
S (1/c)
6
2
e(B (B+1))
Thus, deduce that
(e(B+ + f}!" ( - 1)a(1 -1-1) -11
1
lim (aB BB) succeeds) > min
N
33

---

C.6 Proof of Theorem
4.3
Proof. By Lemmas A.3
4. and 4.2
The success probability of Algorithm A(a, 3) can be written
as
P(A (a, 3) succeeds)
P(A (a, 9) succeeds Cxr + +
P(A [aN] (a, () succeeds, succeedss. = CN)
+ PP(Afan) [aNj
(T (a, (3) succeeds, MoN!-1 = CN) + (()))
UN,1aNI,1 + U N. |aN].. (
(a, 8; 42 (a, 3; + 0
Los
2ag²
1
log( (1/
Aa - -1
(1 - A)a + XB
3
E!
[1 (u- (u-a)pp 1-1111 (a,, 3:u) du
+ ((B>0)
((1 A)a + uu
(1 x)
1
log(1 (/)}
Aa ((1 2) + + (1 - 2)a AB 6=
B
+ 1(B>0)a² /
(1- 11- + 2(2 - A)u
B
(a, B; u))u + o(1
log
((1 A)a + Au)
P22
N
then, regrouping the terms yields
P(A (a, B) succeeds)
= -a log (1 - A + 22) - -a ((1 - 2) B + 1)
a8
B
1
b
log log(1133) (1/3)²
(AB + +1 (1-)
(1 - 1Ja AB
E!
b=0
8=
1B 0) S' (x²(1 ()) + [
2) A(2 2)))
82 B-- (a, 3; (a,3:
u)du
+ +0(v 1og
((1 A)a + xu)a
Finally, observing that
(1 (1- X(2 1)) -1- 21) + 2X(1 A) +
= -11 A)a + Au)
deduce the result
P(A (ax, 3) succeeds)
= log (2)
+ 0;
B
Σ
b
log(1/3)
+ 1(B > 0)a
3 BB-1 B-1 " B; u)du
(a,
+ 0 (V/ogny
E!
u²
b=0
t=
D Optimal memory-less algorithm for two groups
In this section, we derive an optimal memoryless algorithm employing dynamic programming approach. We analyze the state transitions depending on the algorithm's 's actions and the associated success probabilities for each state. Unlike previous sections, our study here is not asymptotic. Therefore, we do not rely estimating the number of candidates in each group using concentration inequalities. Instead, we consider the exact number of candidates each group as a parameter for decision-man miisinn at each step.
34

---

D.1 Memoryless algorithms
One distinctive feature of Dynamic Threshold algorithms their decision-makiin process, which solely depends on the observations at each step and the available budget, without recourse to past comparison history. We designate algorithms exhibiting this characteristic memory- algorithms.
Definition D.1. An algorithm for the (K, ---serteyyyy problem is memory-lest if its actions at any step t E [N] depend only on the current observations rt: 9t. 1 = 1), the available budget Bt. the cardinals (IG+
We assume that memory-less algorithm is aware of the current step / at any time, and knows the proportions of each group (λк) However, our analysis, the knowledge of group proportions is dispensable since we investigate the asymptotic success probabilities of DT algorithms. Indeed, for setting thresholds that depend on group proportions, if the smallest threshold at least e > O, regardless of group proportions, it suffices to observe the first [eN] candidates, then estimate
A -LNNJ--E ii=1 LcN] 1(g. = k) for all & E [K]. The algorithm can choose the thresholds using (AK) instead of (Λs) As the number candidates tends to infinity, Ås. becomes arbitrarily close to d with high probability, and so do the thresholds, assuming they are continuous functions of the group proportions. Though this introduces additional intricacies to the proof', the fundamental proof arguments and the results remain the same. While Definition D.I only includes deterministic algorithms, it can be easily extended to randomized algorithms, by considering the distributions of the actions instead of the actions themselves.
only
In the following lemma, we establish that the success probability of memory-less algorithm, given the history up to step t - 1, is contingent upon only a few parameters, which are the available budget B,, the group which the best-observed candidate belongs g and the sizes of the groups (IGF)) l) E [K] Collectively, these parameters define the state of a memory-less algorithm at step t, which entirely determines the success probability of the algorithm starting from that state.
Lemma D.I. For any memory-less algorithm A and t [N), denoting by the stopping time of A and by Fi-1 1 is the history of the algorithm up to step t - 1, i.e. the set of all the observations and actions taken by the algorithm until step 1, then
PA succeeds 2 1, D4 Fi-1) P(A succeeds r 2 9 Br, ((G/D)<(K))
Proof. Let A be a memory-less algorithm, and let us denote by r its stopping time. Conditionally to the history of the algorithm until step / 1 and the event {7 2 (). the success probability of A depends on the future observations and the future actions of the algorithm.
Given that the algorithm is memory-less, at any step 2 t, its actions ag.1, as,2 depend the observations Tz, St. RG, the budget B, and ((G*-
Conditionally to the cardinals of the groups at step ( 1, the cardinals (G are independent of the history F because
1-1
G G + Σ 1g. Yk E [K],
Moreover, since the candidates are observed in uniformly random order, and the group memberships are also i.i.d random variables, then for all 8 distributions of r., R2 depend only on the cardinals of each group at step 1, on ys and -- Also y is function of 9- 1: Is and 1RR, 1):
g = 1 1 * 1) g. + 1(Rg + g)
and the budget B, satisfies
B, = B, 1(a, 1,2 = compare)
Therefore, Conditionally to the B,, (IG)- ())e)l)s((]])))) -7 the distributions of the observations and of the algorithm's 's actions at any step s 2 are independent of the history before step f.
At any given step I, memory-less algorithm has access to the available budget B, and the number of previous candidates belonging each group. In the case of two groups, this information reduces to
35

---

(t, L,B,, L. since |G-- G The state of the algorithm, which fully determines its success probability, is given by the tuple (t, Br, |G --199-1)- However, Di-1 is not known to the algorithm, hence it must make decisions relying on the limited information has, maximize the expected success probability, where the expectation is taken over 9i-1.
D.2 State transitions
For any memory-less algorithm A, we denote by S(AA) its state step t, which is tuple (t, b, m, E). Here, - 1 represents the count of previously rejected candidates, 2 denotes the available budget, < indicates the number of prior candidates from group G¹, and l {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 depending on (A)) While the group membership gi of candidate V, is independent of (A)), both r2 and RG are contingent on it.
Lemma D.2. For any memory-less algorithm A and state (1, m, b, f), denoting by k 3 8 the group index different from E, it holds that
P(r. = 1 Sx(A) (t, = = =)==
G + 1[G 1)
P(r, (A(A) (t, f) k)
P(R, (s((A) mt, b).. Lr = 1) =
G +1
P(R. = (a(A) = (4, b, 0). = kn = 1) = G G
where
if k = ( 11-1-11 if 2
G
Proof.
If S(A) = (t,, m. b, E), then in particular -ī- = l, i.e. max G > max G thus
P(r: 1 (,A) = (t, b. f). f) P(x max G. S((A) (t, m, E). g:
P(x max 01+-1 ((()) (1, (,.,,,), E), E)
1
because the rank of among previous candidates is independent of their relative ranks and groups. thus independent of the state of the algorithm. Moreover, if r. = 1, gt = and -;- = E, then x, is the better than the maximum of G which is the maximum of ø1 thus necessarily R₂ = 1,
P(R = 11| (e4) = (t, m, b, E), = r, = 1) = 1.
On the other hand, if gt = k + = - assume that |G/ > 0. holds that
P(r, (()())))((A)) (t, mt, b, k) P(r - L, -,1G m)
P(r, 1, gf = f gt = k. G. m)
P = { G = =m)
We have immediately that
P = E m) P(max Gf_, max Gk ||/ =m) G
36

---

and the numerator can be computed as
P(r:- 1, = 9: = --
(16)
P( max G = e = m)
P(re > max G G(11, max G > max G |G-11= m))
-((x max Gi-1 max G | m)
P(max G. > 2t max C
G|-11 m)
1
G
G G
+
t
t-1
[G/-1++1
G/-il
1
(17)
t --1
G
++1
which yields
1-1
GP--l ( 1
P(r: = ((A(( (t. b)
G t
t-1 +
G
1+
t-1
1+
G +1
G +
[[G]_|+11
+1)
Finally,
b).9 P(R, = 1 = m,,,, = k, = =) = P(R. 1,7 1, é 9: |G
P(r: 1,9i-1 = Ll 9: = k. k,
computed the denominator term and the numerator satisfies
P(Re 1, = 1, --1 = é = G, P(R. 1, el 1 hi G
P(r. max G G > max G |G-_l
G
t t-1
hence
P(R. = ((() = (t,m,b,0). () = k, = 1) =
10
GG 1+111
1
[-1
|+1
G
G +t
This concludes the proof when |G > [f = 0, then the same identities remain trivially true.
Using the previous Lemma, we can fully characterize the possible state transitions memory-less algorithm. First, the values of the parameters |G| and B,+1 trivially determined based on the state S, at the beginning of step f, the observations T and gr, and the actions of the algorithm:
GG!| = |G|_1| + [g =) Br+1 B, 1 compare)
where a,, the action taken by the algorithm, which only depends on the state S, since the algorithm memory-less.
37

---

Regarding 97, if 9: -i-11 then gi' = gi- remains unchanged with probability 1. However, if 9t + gi-1 and r. and if the algorithm skips the candidate without making comparison. then gi is not deterministic based on the history alone. The probability that D;- in this case is precisely the probability that R2 1, computed Lemma D.2
G 1111+1 +1
P = 9t (S((A) = (t, m, b, b. - -, 1)
+
D.3 Expected action rewards
In the following, we denote by A. the optimal memory-less algorithm for two groups, and for all B 2 e [N], < t and é E {1, we denote by
V Lm, P (AA.. succeeds 2 (,,,,(A.) = (,m,B,m, B,m,
which is its success probability starting from state (t, m,
We analyze the expected rewards and state transitions algorithm A. given its limited information access. When the algorithm receives a new observation (re, 9t):
If r. * 1, the optimal action is skip the candidate (skip).
If r2 and B, 0, the algorithm either stops skips the candidate. However, if there is a positive budget Br, stopping is suboptimal: it is always better to make a comparison first.
If the algorithm chooses to make a comparison and observes RG:
If Rg * the optimal action to skip the candidate.
If R2 the algorithm must decide whether to skip or stop. However, skipping after observing R. = is suboptimal compared to skipping immediately after observing
rz = 1, as the latter conserves the budget.
In summary, any rational algorithm follows these decision rules:
If (r+ + 1) or (r: = and Rg j 1), then skip the candidate.
If (r+ and R. 1), select the candidate.
Therefore, the main non-trivial decision to make is whether to reject or accept a candidate after observing 7i 1. Consider an algorithm AA following these rules. At time with budget B, and | m, if 9: k and r. 1, choosing an action E {skip, stop, compare] based on these rules leads to new state S (A) Ftt, b, m, k a). which is a random variable depending on gi-1 and R, If f E {stop, compare) } and R, = 1, then S,+ (AA) is final state; success or failure.
With this notation, define R. (a) as the reward that A. expects to gain by playing action a after observing F. and gr in state (A.)) (t, m. -), where it ignores -;-
& = E[P(A, succeeds (A+1 = Ftt, B, m, k a)) S.(A)) = (t, B, m, -), r2 = 1, = k)
where the expectation is taken over -i-1 and Re. The optimal memory-less action at any state (t, B, m, f), knowing that r, g: hi is the one maximizing RB R. (a).
Lemma D.3. Consider state S. = (t, B, m, )) and let (k, f = [1,2}, Ma = m + 1(k = 1), then
G
RB B t.m. (stop)
N
Gtl
+ G yB
RB B km (skip)
n 14.1,
t
Gh
Gill
+ t-1 BB
R (compare)
N
+
(G
N
G + (41,Med
Observe that, conditionally to ge and IG| 1. the cardinals of G G Gh G1, G are all known:
GG |G|_a| 1(g. = =1) | = - G = t 1 - |G|||
38

---

D.4 Optimal actions and success probability
Using Lemma D.3 and considering the potential state transitions based on the actions, we establish recursion satisheed by (t..,),.B.m B,,.. We present the result without distinction between the cases
t= 1 and & 2. For simplicity, let d Pgr k) for i = 1, 2, and define Mr- 1(k = 1)
for all m 2 0. Additionally, for all (B,t, m, k), define
o 1 (R., km, (accept) 2 R
where the action accept corresponds to compare for B > 0 and stop for 0
Theorem D.4. For all t E [N], m < t and fli, E) = {1, 2}. the success probability A, with zero budget satisfies the recursion
Vo t.m. de
(1-
54
VitI.Me.e)
1o
+ A
82 N
1-6%
Do
Me + (1- (2 (2-0) 0% G 11+1
vo Vet2,Ma.t)
for B 2 it satisfies
V. = de
6
+ (1
) (+
8 R
N
+ AR
6
GG I+I (1 - (1-4) 1 M, + 1-88 M,
+ -
6 1G 111 Veti.Me.))
DB
where V 1,m,k
0 for all B 2 0 S N and l E {1,2].
Proof. Using the results from Section D.2 and D.3 the actions of A. and the resulting state transitions as follows. If the state of A. at step is S, (A.) = (t, B, m, E) for some B 2 m < t and
l E (1,2): If g. = f, denoting by M, = m + ll 1), we have
1/t: r, 0, and the algorithm rejects the candidate, transitioning to the state (t + 1, B. E).
with probability
with probability 1/t: Tt 1, and necessarily R₂ = 1, because = - E.
If R. (compare) > R. (skip), then the algorithm uses a comparison and observes R. 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 (1 + 1, Mr, E)
On the other hand, if gt = k + gi-1, then denoting by Mş = m + 1(k = 1), we have
|c , [(+2),
with probability पाद !44)"* r, 0, and the algorithm rejects the candidate, transitioning to the state (t + 1, B, E).
|G |
with probability
((GG 1++)" Tt =
If R. Rm, (compare) >
then the algorithm uses comparison
|Gt 1111 [0 1ltt'
* with probability
Rg = 1 and the algorithm stops, its success probability
is t/N
* with probability |G |++* R2 = 0, the candidate rejected, and the algorithm
f-1
goes to state (t + 1, B B - 1, Mr. !) Otherwise, the candidate is rejected and
| G + the algorithm goes to state (t + B, Mr, k)
* with probability
* with probability [6 |++* the algorithm goes to state (t + 1, B, Mg, e)
39

---

In the case of zero budget, the algorithm compares R,,, (skip) to R x. (compare) instead of R. (compare). If the algorithm decides to reject the candidate then the same state transition occurs. However, if the candidate is selected and if 9r -i-1 É then the success probability is I/N. If On the other hand, if it is selected and St = k. + Fi-1 = l then the probability that the
1G 1
current candidate is the best overall is
G 11+ X N.
All in all, for B = 0, then
(V Emmee 90 = 00
1
t
+
V 1 (1- D M1,.
N
+)
Do
62 N
Me,
(Vem,e 9t = k)) M|G
10t
8 N(G + (1 - (1))
(1(+)11+1)
(10 v
(1o l+t Med + 10 vo
|G ,l+
Vo
o< G .I+1)
M2,
+
1 1-8% 0 0
M + (1- (2(- (2-6% -
Do [ ,1+1
VetI,M
N
and we deduce that
V VL.me de
(11-
VetIMM x3)
+ A1
62 1-60
VD
Nt.k + (1 (2 (2- 0% -,=,, Do
VetI,Ma.))
N
For B 2 1, we obtain
(V Vemeel 9t = =)=
80 (07
1
+ + (1-82) (1-88)V + (1- v Me,e
N
(1 -1-
4
y
M4,, + N
(VB (e,mee e gt =k))
1[05 1)1
10
(1 M
[0__,++2 y
10t_itte vetI,Me.))
1-1 V
(1
G 1|+1
, (+ 1,Ma
CC (-1 Do
ilte Mi.))
)
+
"[lGs 11+1]
1at 11+1
vB M,
6
(1
V
1-00 D
+(1-
8 ,,, I
BB
G.
+I
hence
V.B t,m,
de (xx + (11 5 / (ot1,
+ AR
6 N
+
I+I (1
6
1
1tI,,,,, + - M + (1
1- p
5 G
(41.Me.)
which concludes the proof.
Implementing the optimal memory-less algorithm A. with budget B requires knowing the for a E {skip, stop, compare), which depend themselves on the table (Vg,m.)) t.b.m,k Using Lemma D.3 and Theorem D.4 these tables can be computed in a O(BN2)
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 [D3] and when encountering r. = 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
40

---

Algorithm 2:
(V,,,,)) k.m.m, and ( for (skip, stop, compare)
Input: Number of candidates N, available budget B, probability distribution of gr: A1 22
Initialization: V mm +- 0 for all b - B.m m I N E {1,2}
for b 1...., B do
for t N, N 1, do
for 0, ..... do
Compute R. (., for E {1,2} and E {skip, stop, compare) using Lemma
D.3
Compute V t.mkk for k {1,2] using Theorem D.4
Return: (V dr (R), (a)),,
Algorithm 3: Optimal memory-less algorithm A.
Input: Number of candidates N, available budget B. probability distribution of gr: À A2 Initialization: b + B, m +-
Compute (Vr,m,))t.b.mm and (R),,,,(a))),,,mm.a using Algorithm 2
2 for I....,N do Receive new observation (rt,9t)
r. then
if b 0 and R2 Ri (stop) > RR. Rt.m.g (skip) then
Return:
if b > O and R/. a. (compare) > R (skip) then
b - -
if Rg then
10
Return:
11
772
m + L(g = 1)
41

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the introduction, we first formally present the problem considered, and state the main results the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed during the paper and in the conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
42

---

Justification:
All the proof' are in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
We explain the experimental settings.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
43

---

Answer:
[Yes]
Justification:
A link to the code is provided in the experiments section.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https Cooeeeoodeesssseeeeee //nips.com / wwwssnnnnccccyyc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
The full experiments setting is explained in the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Most plots show deterministic values (optimal thresholds, visualization of theoretic results....)
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
44

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 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 range (e.g. negative еπхо 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 the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer:[No
Justification:
The runtime is not important factor in our simulations, we do not feel that precising computer resources relevant.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://neurips. httppp......pbccttttt.cssdddeaa.
Answer: [Yes]
Justification:
We have reviewed the Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations 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 no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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.
45

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The contribution of the paper is mainly theoretical.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses 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 any assets.
Guidelines:
The answer NA means that the paper does 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
46

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not provide any new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No such experiments are included in the paper.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No such studies are included the paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
47


Reviews:
[{"review_id": "60QXYTxWqG", "reviewer": "Reviewer_U5mj", "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.", "questions": "See above weakness.", "limitations": "See above weakness.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well motivated, and the proposed method is technical sound.\n2. Related work is extensively discussed and surveyed.\n3. Extensive and rigorous theoretical analysis is provided.", "weaknesses": "1. Although the problem is well motivated, it lacks of empirical analysis on real datasets and applications.\n2. No baseline methods are compared in the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback on our submission. We generally agree with the positive evaluations made in terms of strengths (solid theoretical study and introduction of a novel and realistic variant of the multi-color secretary problem). We provide a detailed reply to the weaknesses and questions raised below.\n* **Real datasets.** In the secretary problem, the actual values of the items observed by the algorithm are irrelevant; only their relative order matters. Consequently, conducting experiments on real datasets is equivalent to using synthetic data. The key factors to consider are the budget, group proportions, and the number of candidates. We conducted experiments with various values of these parameters for two groups and additional experiments involving multiple groups are presented in Appendix A. We plan to include these experiments in the main body of the paper upon acceptance, as an additional page is allowed. \n* **Baseline methods.** Since the multi-color secretary problem has not been previously studied with budget constraints, the only available baselines are the algorithms proposed by Correa et al. (ICML 2021), which are optimal for the case of zero budget, and the classical $1/e$ strategy for an infinite budget. In our experiments, we compare our algorithms to the success probability of $1/e$ and the optimal algorithms for a zero-budget scenario.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NaWj36mTx1", "reviewer": "Reviewer_5bhX", "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.", "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": "The authors adequately discussed the limitations of the paper.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. This paper investigates a novel variant of the multi-color secretary problem that allows comparisons between candidates from different groups at a certain cost. This problem setting is appropriate for some real-world recruitment scenarios.\n\n2. The algorithms proposed in this article are supported by solid theoretical results and are simple to implement yet effective.\n\n3. This paper is well-organized and presented in a concise, clear and fluent manner.", "weaknesses": "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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback on our submission. We fully agree with the positive evaluations made, both in terms of strengths (solid theoretical study and introduction of a novel and realistic variant of the multi-color secretary problem) and in terms of future work (rigorous theoretical study of the multiple group case). We provide a detailed reply to the weaknesses and questions raised below.\n* **Weakness 1.** The title of the paper is meant to reference the paper \"Fairness and Bias in Online Selection\" in ICML 2021. The bias here refers to the difficulty of accurately comparing candidates from different groups and our paper suggests that these comparisons can be made at a cost. \n* **Weakness 2.** We thank the reviewer for this observation. We went carefully through the paper and corrected all the typos and presentation mistakes.\n* **Question.** The analysis presented in Section 4 can be generalized to multiple groups, but this would significantly increase the overall complexity as the computations are already cumbersome and technically challenging for the case of two groups. Additionally, the results would become much more difficult to interpret and/or visualize (e.g., Figure 2 would be way heavier). For the aforementioned reasons we decided to postpone this study for a journal version of the paper, yet we agree that this constitutes a logical direction for future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hHUTikMSp8", "reviewer": "Reviewer_io3s", "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.\nThe 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.", "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": "No concerns.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The idea of costly comparisons is interesting and the authors provide an interesting initial model to study this problem.\n\nI think this is a thorough and very well written paper.  Although the results pertain to special case, they seem difficult to obtain.\nThe numerical experiments are helpful and give insights into the problem, that may be hard to prove theoretically, such as Figure 4.", "weaknesses": "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.\n\nThe discussion on the alternate model is missing from the main body and appendix, despite available space in the main body.\n\nThe figures would benefit from an explanation of what the dashed lines and what the continuous lines each represent. \nDetailed/minor comments:\n\nThe sentence on line 36 is incomplete.\n\nLine 93: cardinal -> cardinality\n\nLine 148-151: Make the notation consistent with the pseudocode (whichever way around).\n\nLine 110: full stop missing\n\nFigure 2 and line? Why does the second row in Figure 2 not have (1-\\lambad)t displayed instead?\n\n256: cardinal-> cardinality\nWhat is |G_t^{1/2}|\n\nLine 259-260: The phrasing is unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback on our submission. We fully agree with the positive evaluation made, both in terms of strengths (solid theoretical study and introduction of a novel and realistic variant of the multi-color secretary problem) and in terms of future work (rigorous theoretical study of the multiple group case). We provide a detailed reply to the weaknesses and questions raised below.\n* **Focus on two groups.** The single threshold algorithm is studied for multiple groups, and the analysis shows how the dependence between $K$ and $B$ impacts the success probability. For algorithms with group-dependent thresholds, the analysis with two groups is already technically challenging and necessitates heavy computations. The analysis for an arbitrary number of groups $K$ should be technically possible. We believe that this study constitutes a logical future work for a journal version of this paper.\n* **Minor comments.** We thank the reviewers for pointing out the typos. We went carefully through the paper and corrected all of them.\n    * Regarding Figure 2, we preferred to display both acceptance regions depending on $\\lambda t$ because the dynamic programming algorithm uses as a parameter the number of observed elements in $|G^1_t|$; $|G^2_t|$ is implicitly given by $t - |G^1_t|$. We believe that the current figure gives a good intuitive understanding of the inner logic of the algorithm.\n    * $|G_t^{1/2}|$ should be $|G_t^{1}|$ instead. We corrected it.\n* **Alternative model.** The single threshold algorithm with $K$ groups can be adapted for the first comparison model at a cost of $K-1$ additional costly comparisons. After the first $\\alpha N$  candidates are rejected, $K-1$ comparisons are made between the maximum candidates from each group to identify the best candidate so far. The algorithm then keeps track of this best candidate. Whenever a new candidate becomes the best in their group, they can be 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 of $K + B - 1$ instead of $B$.\n\n    In the case of two groups, both models are equivalent, as freely comparing a candidate with the best in their group and then making a costly comparison with the best candidate from the other group is sufficient to determine if they are the best so far. Thus, the guarantees on algorithms for the case of two groups remain the same.\n\n    This discussion was removed from the paper due to page limits and it was not included in the appendix by mistake.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)