The Secretary Problem with a Stochastic Precursor Franziska Eberle∗
Alexander Lindermayr†
arXiv:2605.22653v1 [cs.DS] 21 May 2026
Abstract In learning-augmented online algorithms, predictions are usually valued for what they say: a value estimate, a solution, or an algorithmic recommendation. This paper shows that predictions can also be valuable solely due to their arrival time. We study the fundamental secretary problem augmented with a stochastic precursor: a content-free signal that is guaranteed to arrive no later than the best item, but is otherwise stochastically timed. The signal does not carry any additional information; nevertheless, its timing alone changes the structure of optimal stopping. We characterize optimal policies in the random-order and adversarial-order models. In random order, a single uniformly timed precursor already gives success probability at least 1/2, improving on the classic 1/e benchmark. With increasingly late precursors, the success probability approaches 1. In adversarial order, for which traditional models do not admit strong guarantees, sufficiently concentrated precursors recover constant success guarantees. Our results show that such novel forms of asynchronous temporal information are a distinct and powerful form of advice in online decision making and may also be effective for other problems.
1
Introduction
The classic secretary problem is one of the most fundamental models of online decision making under uncertainty [23, 27, 29, 41]. Its parsimonious formulation has made it a natural testbed for richer information models. Recent work on secretary and related problems studies algorithms with access to samples [16, 35], augmented by predictions of values, ranks, or thresholds [6, 9, 13, 28, 36, 46], or relying on more general forms of advice [22]. A common feature of these models is that the additionally provided information is synchronous and instructional : it is available before the process starts (or arrives with the respective item) and directly informs when to stop. In many applications, however, side information is generated by a separate process and arrives on its asynchronous timeline. In hiring, for instance, a delayed recommendation or inference-model score may become available only after interviews have already started, and may indicate only that a particularly strong candidate is still among the remaining applicants. Similar precursor events arise in popularity forecasting through early attention measurements [32, 52, 53], in recommendation systems through evolving user-behavior signals [34, 48, 56], and in scientific impact prediction or scouting through early indicators of future long-run success [1, 2, 24]. Such indicators may contain rich information in practice, but one basic aspect is purely temporal: they arrive at a time that only indicates whether the most important event has already occurred. This is much weaker than the predictions commonly used in learning-augmented algorithms since it does not inform a decision. This observation motivates a simple question at the boundary of optimal stopping theory and learning-augmented online algorithms: Can an online algorithm provably benefit from precursors whose only information is their timing? Our focus is on signals that are inherently asynchronous: ∗ Institut für Mathematik, Technische Universität Berlin, Germany. Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1, EXC-2046/2, project ID: 390685689). † Institut für Mathematik, Technische Universität Berlin, Germany.
1
they may be produced by machine-learning pipelines, external observations, or side processes that do not align with the arrival sequence. In this sense, our model is complementary to standard learning-augmented formulations. Rather than predicting values, ranks, or thresholds, the signal reveals only the temporal cue that something important is still ahead. In the standard secretary problem, n secretaries (or items) {1, . . . , n} =: [n] are presented online one by one, in adversarial or in uniformly random order, at times 1, . . . , n. The goal is to maximize the probability of stopping exactly when the unique best item arrives. Without side information, the classic random-order problem has optimal success probability 1e [23, 27, 41], while adversarial order is much harsher: deterministic algorithms cannot guarantee positive success probability, and randomized algorithms achieve at most n1 . We introduce an asynchronous and non-instructional precursor model for secretary problems. After the arrival order has been fixed, a time S is drawn from a distribution over [I], where I denotes the arrival time of the unique best item. When time S is reached, the algorithm receives a content-free signal. This isolates the algorithmic value of temporal side information from richer advice. The main message of the paper is that even this extremely weak signal model is surprisingly powerful; we give a high-level overview now and precise statements and definitions in Section 1.1: • Full characterization of deterministic and randomized optimal policies for αpower distributed signal times under both arrival orders for every α > 0; those policies always beat the respective benchmarks. To highlight two concrete results, we show that, even without knowing n in advance, in the • random-order setting a uniform signal suffices to succeed with probability 12 , and in the • adversarial-order setting a uniform signal guarantees that even a deterministic policy succeeds with probability n1 . Conceptually, our results show that timing alone can be algorithmically valuable. The signal itself cannot be used to assess the quality of the current item directly. Nevertheless, it helps to outperform the classic benchmark, eliminates the need for knowing n, and, when sufficiently concentrated near the optimum I, allows us to recover constant guarantees even under adversarial order. This makes asynchronous temporal information a distinct and tractable resource and a novel augmented information model in online decision making. We believe it will be useful beyond secretary problems.
1.1
A more detailed overview of our results
We focus on the α-power signal model for α > 0. Conditioned on I = i, the signal time is distributed as S = ⌈i · B⌉ for B ∼ Beta(α, 1); equivalently, each signal time s ∈ [i] appears with probability sα − (s − 1)α P[S = s | I = i] = . iα This Beta family gives a simple interpolation between signals that tend to occur early and signals that tend to occur late in the range [i]. Two prominent special cases are α = 1, where S is uniform on [i], and integer values α = m ≥ 1, where S has the same distribution as the maximum of m independent uniform signals in [i]. In general, for α ≪ 1, S underestimates i, i.e., small s are more likely, even for large i, and for α ≫ 1, S is likely close to i; cf. Figure 1 for representative densities. We call a time/item a record if the arriving item is the best item so far. The threshold policy A(k) with threshold k rejects all items before time k and then accepts the first record from that time onward. 2
asymptotic success prob.
signal density
α = 0.1 α = 0.5 α= 1 α= 2 α = 10
4
2
0 0
0.2
0.4
0.6
0.8
1
x
Figure 1: Left: PDFs of Beta(α, 1).
1
OPT(α), α < 1 OPT(α), α > 1
1/2 1/e 0
0.4
0.8 1
10
100
α
Right: Plot of OPT(α) from Theorem 2.
Random order: exact optimal policy (Section 2). We fully characterize the optimal online policy (cf. Theorem 2). If α ≥ 1, then the optimal rule is A(S) (which does not need to know n): wait for the signal and then accept the first record. Notably, already a uniform signal boosts the probability of the next record being the overall maximum above 12 . If 0 < α < 1, then the optimal policy is A(max{S, kn }) relying on n, where kn /n → (1 − α)1/α . Asymptotically (cf. Figure 1), the worst-case probability 1+1/α α + (1 − α) , if 0 < α < 1, n→∞ α+1 OPTn (α) −−−→ OPT(α) = α , if α ≥ 1. α+1 α→0
In particular, OPT(α) > 1e , beating the benchmark for all α > 0, and OPT(α) −−−→ 1e . Random order: robustness (Section 3). Knowing α ∈ / (0, 1) is sufficient to recover the optimal success probability achievable with precise knowledge of α. In general, the qualitative structure is robust: If the policy only knows a conservative estimate α̂ ≤ α of the true parameter α, a threshold policy tuned to α̂ still guarantees OPT(α̂) > 1e asymptotically (cf. Theorem 3); underestimating α is safe. We also give an explicit formula for the asymptotic success probability for arbitrary α, α̂ > 0: α 1−α (1 − α̂)(α+1)/α̂ + (1 − α̂)1/α̂ − , if 0 < α̂ ≤ 1, α+1 α α(α + 1) g(α, α̂) = α , if α̂ ≥ 1. α+1 Adversarial order: deterministic and randomized policies (Section 4). We also study an adversarial-order model with an α-power signal, where i⋆ is some (adversarially) fixed best item. For randomized policies, we give the exact worst-case success probability nα P OPTrand (α) = , n n α j=1 j achieved by A(max{S, R}), where R is a (non-trivial) random threshold that depends on n (cf. Theorem 4). This yields sharp asymptotic regimes: if α = o(n), then OPTrand (α) = o(1); if n rand α −c (α) → 1 − e (cf. Corollary 5). For deterministic policies, we show n → c ∈ (0, ∞), then OPTn that A(S) is optimal for every α > 0 (cf. Theorem 6), with exact worst-case success probability 1 α . OPTdet (α) = 1 − 1 − n n det α −c If α = o(n), then OPTdet n (α) = o(1), while n → c ∈ (0, ∞) implies OPTn (α) → 1 − e (cf. Corollary 7). Thus, qualitatively, deterministic and randomized policies exhibit the same asymptotic behaviors; randomization improves the finite-n guarantees in the small-α regime.
3
Adversarial order: full signal histories (Section 5). When α = m is an integer, the α-power signal can be interpreted as the last of m independent uniform signals in [i⋆ ]. We therefore also study the richer full-history model in which the algorithm observes all m signal times, rather than only their maximum. For randomized policies, we show that this gives no additional worst-case power (cf. Theorem 8). For deterministic policies, seeing the full history strictly improves the guarantee, already for n = 4 and m = 2. To capture this additional power, we characterize the deterministic full-history optimum by an integer linear program (Theorem 9). For m = 2 we simplify the characterization of optimal solutions (Theorem 14). Thus, unlike in the randomized case, the internal history of asynchronous signals can be algorithmically meaningful for deterministic adversarial-order stopping. Experimental results (Section 6). Our experimental results complement the theory with simulations of the actual online policies. In the random-order model, we show that the theorized gains over the classic secretary benchmark are visible already at moderate problem sizes, and that the threshold policies behave robustly when the signal-quality parameter is conservatively misspecified. We further test corrupted asynchronous signals and show that a simple fall-backto-classic rule provides a smooth interpolation between the learned and prediction-free regimes. In the adversarial-order model, we confirm the behavior in the α = cn regime predicted by the analysis, and demonstrate that full signal histories can strictly help deterministic algorithms. Conclusion. Taken together, our results isolate a new source of algorithmic power in online optimal stopping: not predictive content, but predictive timing. Asynchronous signals help even in the notoriously hard adversarial regime, and in random order they beat the classic optimum already with a single uniform signal. Most proofs are deferred to the appendix.
1.2
Further related work
A natural extension of the classic secretary problem is the full information setting, where item values are drawn i.i.d. from a known distribution [26, 29, 47]. More broadly, optimal stopping problems such as prophet inequalities [18, 31, 42], Pandora’s box problems [12, 55], and variants there-of typically assume full distributional knowledge. A recent line of work relaxes full distributional knowledge by providing the algorithm with samples from the underlying distribution(s), both in the prophet [7, 15, 17, 50] and secretary [16, 22, 35] settings. Another way to relax full distributional knowledge is by only assuming distributional advice such as partial or approximate knowledge of the input distribution [4, 19, 20, 21, 45]. While these models and our model of knowing the signal distribution may appear similar, the distinction is structural: All of these models provide information about the (distribution of the) item values, whereas the precursor signal only carries temporal information dependent on the arrival time of the optimum and cannot be used to evaluate any candidate directly. In the learning-augmented algorithms framework [40, 44], algorithms are equipped with a (potentially erroneous) machine-learned prediction, and their performance guarantee is typically analyzed as a function of some prediction error. This paradigm has been investigated for a variety of problems, e.g. caching [5, 10, 25, 43, 54], scheduling [8, 38, 39], matching and allocation [14, 33, 51], submodular maximization [3], and online learning [37, 49]. In the optimal stopping context, predictions typically take the form of the (final) rank or value of the current item and, if perfect, directly allow to stop at the maximum [6, 9, 13, 28, 36, 46]. In contrast, the precursor only signals that the optimum has not yet passed, and the question is how to optimally exploit a probabilistic but trustworthy temporal clue. Closest in spirit to our model is recent work on non-clairvoyant scheduling [11, 30], where a delayed external signal provides partial information about each job’s characteristics. Our
4
precursor signal shares the flavor of delayed and reliable side information, but differs in that it is tied to the optimality of an item rather than to intrinsic features such as processing times.
2
Random-order model: optimal policies
We start with the random-order model. Here, the arrival time I of the best item is uniformly distributed over all times [n], that is, P[I = i] = n1 for each i ∈ [n]. The baseline is the classic n threshold policy A e , which achieves the optimal success probability 1e ≈ 0.37 [23, 27, 41].
2.1
Warm-up: special cases
Single uniform signal. We show that we can improve substantially over 1e even with a single uniformly distributed signal S ∼ U([I]) (equivalent to the α-power model with parameter α = 1). We consider the policy A(S), that is, we reject all items before time S and accept the first record in {S, . . . , n}. For the analysis of the success probability of this policy, fix a realization I = i ∈ [n] and S = s ∈ [i]. If i = s, then A(S) picks i and succeeds. If s < i (and hence i ≥ 2), then A(S) wins if the best item among [i − 1] arrives before s. This makes s a non-record, lets A(S) stop at i and happens with probability s−1 i−1 . Averaging over s ∈ [i] yields success s−1 1 Pi 1 probability i s=1 i−1 = 2 . Finally, averaging over i ∈ [n] gives an overall success probability of 1 n−1 n+1 1 n + 2n = 2n > 2 . α-power signals. As a second warm-up, we extend the preceding argument to an α-power signal with an arbitrary fixed parameter α > 0. We again use the policy A(S): reject all items before the signal time S and accept the first record from time S onward. For the analysis, condition on I = i. The case i = 1 is trivial as then S = 1 and the policy succeeds. Hence, suppose i ≥ 2, and condition further on S = s ∈ [i]. If s = i, then the signal occurs at the best item and A(S) accepts it. If s < i, then A(S) succeeds exactly when the best item among the first i − 1 times appears before time s, which happens with probability s−1 i−1 . Therefore, i−1
iα − (i − 1)α X s − 1 sα − (s − 1)α P[success | I = i] = + · iα i−1 iα s=1
i−2
(i − 2)(i − 1)α X sα − iα (i − 1)iα (i − 1)iα s=1 i−1 X sα 1 (i − 1)α 1 α 1 =1− =1− +O = +O . (i − 1)iα α + 1 iα i α+1 i =1−
(i − 1)α
+
s=1
Averaging over all i ∈ [n] gives a total success probability of at least n 1X α log n n→∞ α P[success] = P[success | I = i] = +O −−−→ . n α+1 n α+1 i=1
The limiting success probability is increasing in α and tends to 1 as α → ∞, so increasingly late signals make A(S) nearly perfect. In the remainder, we show that, for all α ≥ 1, A(S) is indeed optimal. For α → 0, the signal concentrates at S = 1, and the asymptotic success probability of A(S) vanishes. In that regime, the signal alone should not be used as the threshold: the optimal policy combines S with an n-dependent deterministic threshold, achieving a success probability strictly larger than 1e for every 0 < α < 1 and approaching the classic 1e -guarantee as α → 0.
5
2.2
Bellman recursion and optimal policies
We first isolate the dynamic-programming structure of the problem in the following lemma. The history at time t describes the observed relative ranks as well as the signal time if S ≤ t. Lemma 1 (Bellman recursion). Fix α > 0. There is an optimal policy that never stops before the signal and only stops at record times. Let Πt be the optimal success probability conditioned on not having stopped before time t and having observed a history in which (i) the signal has already appeared, and (ii) time t is a record. P Then, Πt depends only on t. With the normalizing term Ψt := t1−α + ni=t+1 i−α and the (unnormalized) value Φt := Ψt Πt , we have Φn = n1−α and, for every t < n, ) ( n X t (1) Φt = max t1−α , Φu . u(u − 1) u=t+1
The recursion is a posterior comparison. Suppose the signal has already arrived and the current time t is a record. Conditioned on this, the exact signal time no longer matters: we obtain the same likelihood for every possible location of the maximum. In the unnormalized value Φt = Ψt Πt , stopping at t gives t1−α , the posterior weight that the current record is the overall maximum. If we continue, the only relevant future times are future records. The probability that the next t record occurs at u > t is the standard record factor u(u−1) , and the value from that point on is Φu . Thus, the Bellman recursion simply compares stopping now with waiting for the next record. A simplified view of the recursion asks if one should stop at t, assuming that any later P records1 will imply immediate stopping. In this case, the continuation value becomes Ct := t nu=t+1 (u−1)u α, 1−α 1−α whereas the stopping value is t . Hence, comparing Gt := t − Ct to 0 governs the local decision. Exactly here the parameter α comes into play: the larger α, the faster future weights u−α (and the future probabilities for records) decay and the more likely the current record is the maximum. For α ≥ 1, Bernoulli’s inequality ensures that the continuation value telescopes: Ct ≤ t
n X
(u − 1)−α − u−α < t1−α .
u=t+1
Thus, Gt > 0 for each t, and stopping at the first record after the signal is better; A(S) is optimal. We can evaluate the success probability and its asymptotic behavior as seen in the warm-up. For 0 < α < 1, Gt switches signs from negative to positive exactly once. On the scale t = ⌊cn⌋, n
α−1
Gt −→ c
1−α
Z 1 −c
y −(α+1) dy =
c
c − (1 − α)c1−α . α
This limit is negative for c < (1 − α)1/α and positive for c > (1 − α)1/α and we can show that the sign change induces a deterministic cutoff kn with knn → (1 − α)1/α : Records after the signal but before the cutoff point should still be skipped, while records after both the signal and the cutoff point should be accepted, making A(max{S, kn }) optimal. Again, we can compute the optimal success probability and derive the theorem below. Theorem 2. For α ≥ 1, the policy A(S) is optimal. For 0 < α < 1, there is a threshold kn ∈ [n] n→∞ such that the policy A(max{S, kn }) is optimal and knn −−−→ (1 − α)1/α . If OPTn (α) denotes the
6
0.6
0.4 1.0
opt. success prob.
0.5
1.5
g(α, α̂)
predicted parameter α̂
0.8
0.7
det., α = 0.1 det., α = 0.5 det., α = 1 det., α = 10
0.8 0.7
1/e
2.0
0.5 0.4 0.3 0.2 0.1
2.5
0.6
3.0
0.3 0.2
0.5
0.1
true parameter α
rand., α = 1 rand., α = 10 rand., α = 50
1.00 0.75 0.50 0.25 0.00
0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 5.5 6.0
det., α = 50 rand., α = 0.1 rand., α = 0.5
1
2
5
10
20
50
100
n
Figure 2: Left: Heatmap of the asymptotic guarantee g(α, α̂) from Theorem 3. Right: Optimal success probability in the adversarial-order model. Solid lines show the det. opt. 1 − (1 − 1/n)α ; P n dashed lines show the rand. opt. nα / j=1 j α . optimal success probability on instances of length n, then 1+1/α α + (1 − α) , n→∞ α+1 OPTn (α) −−−→ OPT(α) := α , α+1
3
0 < α < 1, α ≥ 1.
Random-order model: robustness
The threshold kn in Theorem 2 depends on the exact knowledge of α. In general, α might not be known. In order to ensure robustness to parameter misspecification, we also investigate the asymptotic behavior of A(max{S, ⌈βn⌉}) for β ∈ [0, 1] on instances with parameter α. We show that 1−α β α+1 α n→∞ + β− . P [success] −−−→ f (α, β) = α+1 α α(α + 1) Letting β ⋆ (α) denote the maximizer for α > 0, we recover f (α, β ⋆ (α)) = OPT(α). More importantly, for an estimate α̂ of α, we still obtain good bounds using β ⋆ (α̂) (instead of β ⋆ (α)). Theorem 3 (Smoothness and Robustness). Let α > 0 and α̂ > 0. The policy A(max{S, kn }) with kn = ⌈β ⋆ (α̂)n⌉ has an asymptotic success probability of at least α 1−α (1 − α̂)(α+1)/α̂ + (1 − α̂)1/α̂ − , α+1 α α(α + 1) g(α, α̂) = α , α+1
0 < α̂ ≤ 1, α̂ ≥ 1.
In particular, if α̂ ≤ α, then g(α, α̂) ≥ OPT(α̂) ≥ 1e . We highlight that for α ∈ / (0, 1), the optimal policy does not require a threshold besides S, and hence, the optimal success probability can be achieved only knowing α ≥ 1. Thus, the more demanding regime is α < 1, in which our guarantee g(α, α̂) degrades smoothly in |α − α̂|; cf. Figure 2.
4
Adversarial order
In this section, we present our tight results for adversarial arrival orders and policies enhanced by a single α-power signal. Here, the unique maximum arrives at an adversarially chosen time i⋆ ∈ [n] and the policy receives an α-power signal at time S ∈ [i⋆ ].
7
To describe instances, instead of talking about the relative ranks of items, we will think about the item at time i as having a value vi . This allows us to represent an instance I by its value vector v ∈ Nn0 . In fact, all of our upper bounds on the optimal success probabilities in this section use the family {Ii }ni=1 of hard instances where Ii := (1, 2, . . . , i, 0, . . . , 0) ∈ Nn0 for i ∈ [n].
4.1
Randomized policies
For randomized policies without information augmentation, the best possible policy has success probability n1 by stopping at a uniformly random time. With an additional α-power signal, the optimal randomized policy has significantly larger success probability. Theorem 4 (Randomized optimum). Let α > 0. For adversarial arrival orders with anPα-power signal, the optimal success probability for randomized policies is OPTrand (α) = nα /( nj=1 j α ). n The policy A(max{R, S}) is optimal where R ∈ [n] is independent of S and, for r ∈ [n], Pr α nα j=1 j · . P[R ≤ r] = Pn α rα j=1 j We can again analyze the asymptotic behavior of OPTrand (α) for n → ∞. n Corollary 5. For adversarial orders with an α-power signal, OPTrand (α) = o(1) if α = o(n) n rand −c and OPTn (α) → 1 − e for α/n → c ∈ (0, ∞).
4.2
Deterministic policies
Without any information augmentation, it is easy to see that no deterministic policy can achieve positive success probability, even for n = 2. In the α-power signal model this picture changes completely. We show that even for small values of α deterministic policies can achieve positive success probability and, asymptotically, they even match the performance of randomized policies for large enough values of α. Note that, in our model, no policy gains by stopping before the signal. In the α-power model, the deterministic optimum again admits a closed-form exact characterization. Theorem 6 (Deterministic optimum). Let α > 0. For adversarial orders with an α-power signal, 1 α policy A(S) is optimal with success probability OPTdet . n (α) = 1 − 1 − n rand Turning again to the limit n → ∞, we observe that OPTdet (α). n (α) behaves as OPTn
Corollary 7. For the adversarial orders with an α-power signal it holds that if α = o(n), then det −c OPTdet n (α) = o(1), and if α/n → c ∈ (0, ∞), then OPTn (α) → 1 − e .
5
Multiple uniform signals versus one α-power signal
In this section, we investigate whether a policy for adversarial arrival can exploit receiving m i.i.d. uniform signals in [i∗ ] instead of receiving a single m-power signal, which follows the law of the maximum of those independent signals. Let S1 , . . . , Sm be independently sampled from the m uniform distribution over [i⋆ ] and L := maxj∈[m] Sj . Thus, L satisfies P[L ≤ ℓ | i⋆ = i] = ℓi . Revealing only signal L is exactly the same as revealing a single α-power signal with parameter α = m.
8
5.1
Randomized policies: the last signal is enough
We first show that for randomized policies under adversarial arrival, it does not matter whether all m signals are known or only the latest signal is known. That is, the full signal history does not imply additional worst-case power beyond the single α-power signal with α = m. For m ∈ N, let OPTrand,full (m) denote the optimal success probability with access to all m signals. n Theorem 8. For all integers n, m ≥ 1, it holds that OPTrand (m) = OPTrand,full (m). n n
5.2
Deterministic policies: the full history can help
We move to deterministic policies. In contrast to randomized policies, we will see that using the full signal history can indeed improve over the optimal deterministic success probability. Before moving to our formal results, we consider a small example. Let n = 4 and m 2 = 2.7 With only the last signal, the optimal deterministic guarantee by Theorem 6 is 1 − 43 = 16 . We define a deterministic policy by mapping each signal pair (a, b) with a ≤ b to a stopping time t ≥ b: (1, 1) 7→ 1,
(1, 2) 7→ 2,
(1, 3), (2, 3), (3, 3) 7→ 3,
rest 7→ 4.
The resulting success probabilities on the worst-case instances I1 , I2 , I3 , I4 are 1, 12 , 59 , 12 , respec7 tively. Hence, the worst-case success probability of this deterministic policy is 12 > 16 . For general m, n ∈ N, we now characterize OPTdet,full (m), the optimal success probability n with access to all m signals, using an integer linear program (ILP). Clearly, OPTdet n (m) ≤ OPTdet,full (m). n In this richer setting, we define the history as a vector h = (c1 , . . . , cℓ(h) , 0, . . .) ∈ ({0} ∪ [m])n Pℓ(h) with cℓ(h) > 0 and t=1 ct = m, where ct ∈ [m] is the number of signals at time t and ℓ(h) ∈ [n] is the time of the last signal. Let Hm denote the set of all possible histories. Setting 0! := 1, we show that, on Ii , history h ∈ Hm is observed with probability ( m! · 1m if ℓ(h) ≤ i, λi (h) := c1 !·...·cℓ(h) ! i 0 if ℓ(h) > i. In the following ILP, observing variable xh,t = 1 means that the policy stops after history h at time t. (ILP)
max z n X
s.t.
xh,t = 1
∀h ∈ H
λi (h) xh,i ≥ z
∀i ∈ [n]
t=ℓ(h)
X h∈H:ℓ(h)≤i
xh,t ∈ {0, 1} ∀h ∈ H, ∀t ∈ {ℓ(h), . . . , n} Theorem 9 (ILP characterization). The optimal objective value of (ILP) is equal to OPTdet,full (m). n For the special case of m = 2 we give a full characterization of OPTdet,full (2) in Section D.2. In n 6(n−1) det,full 6n particular, we show (n+1)(2n+1) ≤ OPTn (2) ≤ (n+1)(2n+1) which implies OPTdet,full (2) = n det 3 1 2 1 n + O n2 . For small values of n, this notably improves over OPTn (2) = n + O( n2 ).
9
0.3
2.5
0.8 0.6 0.4
optimal policy (S) classical (n/e) OPT( )
0.2 0.0
(b) Misspecification, n=1000
10 1
100
101
true signal quality
0.2
2.0
0.1 0.0
1.5
0.1
1.0
0.2
0.5
102
0.6
empirical gain over classical empirical success probability
3.0
true quality
empirical success probability
(a) Clean model, n=1000 1.0
0.3 0.5
1.0
1.5
2.0
predicted quality
2.5
3.0
(c) Corrupted signals, n=1000
0.5 0.4 0.3 0.2 0.1 0.0 0.0
(S) fallback classical (n/e) 0.2
0.4
0.6
corruption rate
0.8
1.0
Figure 3: Empirical experiments for asynchronous predictions. Left: clean-model empirical success probabilities. Middle: empirical gain over the classic baseline under misspecified signal quality. Right: robustness to corrupted distributions.
6
Numerical experiments
We complement the theoretical results with synthetic experiments in the random-order model. In Appendix E we present more in-depth experiments, also in the adversarial-order model. Setup. For n = 1000 and signal parameter α, we first sample a uniformly random permutation of ranks [n] and let I be the arrival time of the highest rank. In the clean model, the signal α α S ∈ [I] is then sampled from Pr[S = s | I = i] = s −(s−1) . The empirical success probabilities of iα the actual policies are averaged over 1000 trials for each specific parameterization. Shaded regions are approximate 95% confidence intervals. The middle panel reports empirical paired gains over the classic 1e -baseline policy; standard errors for these gains are included in the supplementary files. Clean finite-sample behavior. In the left panel of Figure 3, we compare the optimal policy from Theorem 2, the signal-trusting policy A(S), and the classic A ne policy. The function OPT(α) is shown for reference. The simulation confirms that the asymptotic improvement over the classic threshold policy A ne is also visible at this finite scale; we present more results for smaller n in Appendix E. It also illustrates the transition at α = 1: for late signals, A(S) is optimal, while for early signals it is too aggressive and an additional waiting threshold is needed. Misspecified signal quality. The middle panel evaluates the learning-augmented policy A(max{S, kn }) obtained by tuning the threshold kn to a predicted parameter α̂ as in Theorem 3. For each true α, we generate 1000 trials and evaluate all α̂-tuned policies on those same instances. The heatmap plots the empirical success probability minus the empirical success probability of the classic A ne policy. The dashed diagonal is the correctly specified case, and the vertical line at α̂ = 1 marks the point after which all larger predictions induce the same policy A(S). The conservative region, where α̂ ≤ α, remains positive in accordance with Theorem 3; overconfident predictions can be harmful when the true signal is early, but we only observe a smooth degradation. Corrupted asynchronous signals. The right panel uses α = 1 and considers different levels of corruption. With probability 1 − ρ the clean signal is observed. With probability ρ, the signal is corrupted in one of three equally likely ways: it is missed entirely, replaced by a uniformly random false alarm in [n], or delayed to a uniformly random time after I when such a time exists. We compare the optimal policy A(S) for α = 1 that trusts the signal, the classic A ne policy, and a fallback policy, which uses the optimal policy A(S) that trusts the signal if the signal arrives before the classic threshold ne , but otherwise reverts to the classic A ne policy. The figure shows that blindly trusting corrupted signals can degrade rapidly, whereas the fallback policy gives a smoother interpolation between the learned and prediction-free regimes. 10
7
Discussion and limitations
We study a deliberately weak form of side information: the algorithm receives no a priori prediction, but only an asynchronously delayed signal that arrives before the best item. Our results show that even this timing-only information can be algorithmically useful. In the random order model, it breaks the classic 1e barrier via a simple threshold rule, and conservative underestimation of the signal quality remains fully robust. In adversarial order, timing information alone is weaker, but randomization and access to signal history still provide meaningful improvements. The main limitation is that our sharp theory assumes a clean signal: it always precedes the best item and follows the α-power model. Real predictions may be missing, delayed, or triggered by false positives. Our experiments indicate that a fallback policy can mitigate such corruptions, but a full theoretical treatment of noisy asynchronous signals is left for future work. Other natural extensions include richer secretary models with more general feasibility constraints.
References [1] G. Abramo, C. A. D’Angelo, and G. Felici. Predicting publication long-term impact through a combination of early citations and journal impact factor. In: J. Informetr. 13.1 (2019), pp. 32–49. [2] J. Adams. Early citation counts correlate with accumulated impact. In: Scientometrics 63 (2005), pp. 567–581. [3] A. Agarwal and E. Balkanski. Learning-Augmented Dynamic Submodular Maximization. In: NeurIPS. 2024. [4] S. Angelopoulos, M. Bienkowski, C. Dürr, and B. Simon. Contract Scheduling with Distributional and Multiple Advice. In: IJCAI. ijcai.org, 2024, pp. 3652–3660. [5] A. Antoniadis, C. Coester, M. Eliás, A. Polak, and B. Simon. Online Metric Algorithms with Untrusted Predictions. In: ACM Trans. Algorithms 19.2 (2023), 19:1–19:34. [6] A. Antoniadis, T. Gouleakis, P. Kleer, and P. Kolev. Secretary and online matching problems with machine learned advice. In: Discret. Optim. 48.Part 2 (2023), p. 100778. [7] P. D. Azar, R. Kleinberg, and S. M. Weinberg. Prior independent mechanisms via prophet inequalities with limited information. In: Games Econ. Behav. 118 (2019), pp. 511–532. [8] Y. Azar, S. Leonardi, and N. Touitou. Flow time scheduling with uncertain processing time. In: STOC. ACM, 2021, pp. 1070–1080. [9] E. Balkanski, W. Ma, and A. Maggiori. Fair Secretaries with Unfair Predictions. In: NeurIPS. 2024. [10] N. Bansal, C. Coester, R. Kumar, M. Purohit, and E. Vee. Learning-Augmented Weighted Paging. In: SODA. SIAM, 2022, pp. 67–89. [11] Z. Benomar, R. Cosson, A. Lindermayr, and J. Schlöter. Non-Clairvoyant Scheduling with Progress Bars. In: NeurIPS. 2025. [12] H. Beyhaghi and L. Cai. Recent Developments in Pandora’s Box Problem: Variants and Applications. In: SIGecom Exch. 21.1 (2023), pp. 20–34. [13] A. Braun and S. Sarkar. The Secretary Problem with Predicted Additive Gap. In: NeurIPS. 2024. [14] D. Choo, T. Gouleakis, C. K. Ling, and A. Bhattacharyya. Online bipartite matching with imperfect advice. In: ICML. 2024. [15] J. Correa, A. Cristi, B. Epstein, and J. A. Soto. The Two-Sided Game of Googol. In: J. Mach. Learn. Res. 23 (2022), 113:1–113:37. [16] J. Correa, A. Cristi, L. Feuilloley, T. Oosterwijk, and A. Tsigonias-Dimitriadis. The Secretary Problem with Independent Sampling. In: Manag. Sci. 71.4 (2025), pp. 2778–2801.
11
[17] J. Correa, P. Dütting, F. A. Fischer, and K. Schewior. Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution. In: Math. Oper. Res. 47.2 (2022), pp. 1287–1309. [18] J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, and T. Vredeveld. Recent developments in prophet inequalities. In: SIGecom Exch. 17.1 (2018), pp. 61–70. [19] Q. Cui and M. Dinitz. Ski Rental with Distributional Predictions of Unknown Quality. In: CoRR abs/2602.21104 (2026). [20] I. Diakonikolas, V. Kontonis, C. Tzamos, A. Vakilian, and N. Zarifis. Learning Online Algorithms with Distributional Advice. In: ICML. Vol. 139. PMLR, 2021, pp. 2687–2696. [21] M. Dinitz, S. Im, T. Lavastida, B. Moseley, A. Niaparast, and S. Vassilvitskii. Binary Search with Distributional Predictions. In: NeurIPS. 2024. [22] P. Dütting, S. Lattanzi, R. P. Leme, and S. Vassilvitskii. Secretaries with Advice. In: Math. Oper. Res. 49.2 (2024), pp. 856–879. [23] E. B. Dynkin. The optimum choice of the instant for stopping a Markov process. In: Soviet Mathematics 4 (1963), pp. 627–629. [24] M. Dziallas and K. Blind. Innovation indicators throughout the innovation process: An extensive literature analysis. In: Technovation 80-81 (2019), pp. 3–29. [25] M. Eliás, H. Kaplan, Y. Mansour, and S. Moran. Learning-Augmented Algorithms with Explicit Predictors. In: NeurIPS. 2024. [26] H. Esfandiari, M. Hajiaghayi, B. Lucier, and M. Mitzenmacher. Prophets, Secretaries, and Maximizing the Probability of Choosing the Best. In: AISTATS. PMLR, 2020, pp. 3717– 3727. [27] T. S. Ferguson. Who Solved the Secretary Problem. In: Stat. Sci. 4 (1989), pp. 282–289. [28] K. Fujii and Y. Yoshida. The Secretary Problem with Predictions. In: Math. Oper. Res. 49.2 (2024), pp. 1241–1262. [29] J. P. Gilbert and F. Mosteller. Recognizing the Maximum of a Sequence. In: J. Amer. Statistical Assoc. 61 (1966), pp. 35–73. [30] A. Gupta, H. Kaplan, A. Lindermayr, J. Schlöter, and S. Yingchareonthawornchai. A Little Clairvoyance Is All You Need. In: FOCS. IEEE, 2025, pp. 86–118. [31] T. P. Hill and R. P. Kertz. A Survey of Prophet Inequalities in Optimal Stopping Theory. In: Contemporary mathematics 125 (1992), pp. 191–207. [32] Y. Hu, C. Hu, S. Fu, M. Fang, and W. Xu. Predicting Key Events in the Popularity Evolution of Online Information. In: PLoS ONE 12 (2017). [33] B. Jin and W. Ma. Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model. In: NeurIPS. 2022. [34] P. Joulani, A. Gyorgy, and C. Szepesvari. Online Learning under Delayed Feedback. In: ICML. PMLR, 2013, pp. 1453–1461. [35] H. Kaplan, D. Naori, and D. Raz. Competitive Analysis with a Sample and the Secretary Problem. In: SIAM J. Comput. 54.6 (2025), pp. 1489–1513. [36] H. Karisani, M. Daneshvaramoli, H. Beyhaghi, M. Hajiesmaili, and C. Musco. The Secretary Problem with Predictions and a Chosen Order. In: ITCS. Schloss Dagstuhl– Leibniz-Zentrum für Informatik, 2026, pp. 86–1. [37] M. Khodak, M. Balcan, A. Talwalkar, and S. Vassilvitskii. Learning Predictions for Algorithms with Predictions. In: NeurIPS. 2022. [38] S. Lattanzi, T. Lavastida, B. Moseley, and S. Vassilvitskii. Online Scheduling via Learned Weights. In: SODA. SIAM, 2020, pp. 1859–1877. [39] A. Lindermayr and N. Megow. Permutation Predictions for Non-Clairvoyant Scheduling. In: ACM Trans. Parallel Comput. 12.2 (2025), 4:1–4:26. [40] A. Lindermayr and N. Megow. Repository of papers on algorithms with predictions. http: //algorithms-with-predictions.github.io/. 2026.
12
[41] D. V. Lindley. Dynamic Programming and Decision Theory. In: J. Roy. Stat. Soc. C-app. 10 (1961), pp. 39–51. [42] B. Lucier. An economic view of prophet inequalities. In: SIGecom Exch. 16.1 (2017), pp. 24–47. [43] T. Lykouris and S. Vassilvitskii. Competitive Caching with Machine Learned Advice. In: J. ACM 68.4 (2021), 24:1–24:25. [44] M. Mitzenmacher and S. Vassilvitskii. Algorithms with predictions. In: Commun. ACM 65.7 (2022), pp. 33–35. [45] B. Moseley, H. Newman, K. Pruhs, and R. Zhou. Robust Gittins for Stochastic Scheduling. In: SIGMETRICS (Abstracts). ACM, 2025, pp. 166–168. [46] H. Nourmohammadi, Y. Cao, B. Sun, and X. Tan. Ordinal Secretaries with Advice. In: AAAI. Vol. 40. 43. 2026, pp. 37108–37116. [47] P. Nuti. The Secretary Problem with Distributions. In: IPCO. Springer, 2022, pp. 429–439. [48] Y. Qian, Z. Zhang, P. Zhao, and Z.-H. Zhou. Learning with Asynchronous Labels. In: ACM Trans. Knowl. Discovery Data 18 (2024), pp. 1–27. [49] V. Raman and A. Tewari. Online Classification with Predictions. In: NeurIPS. 2024. [50] A. Rubinstein, J. Z. Wang, and S. M. Weinberg. Optimal Single-Choice Prophet Inequalities from Samples. In: ITCS. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, 60:1– 60:10. [51] F. Spaeh and A. Ene. Online Ad Allocation with Predictions. In: NeurIPS. 2023. [52] G. Szabo and B. A. Huberman. Predicting the popularity of online content. In: Commun. ACM 53.8 (2010), pp. 80–88. [53] A.-F. Tatar, M. D. de Amorim, S. Fdida, and P. Antoniadis. A survey on predicting the popularity of web content. In: Journal of Internet Services and Applications 5 (2014). [54] A. Wei. Better and Simpler Learning-Augmented Online Caching. In: APPROX-RANDOM. Vol. 176. LIPIcs. 2020, 60:1–60:17. Optimal search for the best alternative. In: Econometrica 47 (1978), [55] M. Weitzman. pp. 641–654. [56] J. Yang and D. Zhan. Generalized Delayed Feedback Model with Post-Click Information in Recommender Systems. In: NeurIPS. 2022.
A
Omitted proofs from Section 2
This section is dedicated to giving the formal proofs omitted from Section 2. We start by proving the Bellman recursion. Lemma 1 (Bellman recursion). Fix α > 0. There is an optimal policy that never stops before the signal and only stops at record times. Let Πt be the optimal success probability conditioned on not having stopped before time t and having observed a history in which (i) the signal has already appeared, and (ii) time t is a record. P Then, Πt depends only on t. With the normalizing term Ψt := t1−α + ni=t+1 i−α and the (unnormalized) value Φt := Ψt Πt , we have Φn = n1−α and, for every t < n, ( ) n X t 1−α Φt = max t , Φu . (1) u(u − 1) u=t+1
Proof. Stopping before the signal can never succeed because S ≤ I almost surely. Likewise, stopping at a non-record cannot be optimal. Hence we may restrict attention to policies that only stop at records in {S, . . . , n}.
13
Fix a time t and a history Ht satisfying the assumptions in the statement and let s be the realized signal time in Ht . We start by bounding the probability of observing Ht . The realized order σt of relative ranks up to time t with Rt = 1 and S = s determine Ht . Therefore, P[Ht , I = i] = P [S = s, σt , Rt = 1, I = i] = P [S = s | I = i] · P [σt | I = i] · P [I = i] , where we used that {S = s} only depends on {I = i} but not on σt . Let gs := sα − (s − 1)α . If i > t, the maximum has not yet appeared. Hence, the probability of observing a particular random order σt conditioned on {I = i} is t!1 . Thus, P[Ht , I = i] = P [S = s | I = i] · P [σt | I = i] · P [I = i] =
gs 1 1 · · iα t! n
If i = t, then the current item is the maximum. Hence, the probability of observing a particular random order σt conditioned on {I = t} is the same as observing the prefix σt−1 . Thus P[Ht , I = t] = P [S = s | I = t] · P [σt | I = t] · P [I = t] =
gs 1 1 · · α t (t − 1)! n
As the events {I = i} are disjoint, we can sum over i ∈ [n] and obtain ! n X 1 1 1 1 i−α = gs · · · Ψt . P[Ht ] = gs · · · t1−α + t! n t! n i=t+1
Therefore, P[I = t | Ht ] =
P [I = t, Ht ] t1−α = , P [Ht ] Ψt
(2)
i−α , Ψt
(3)
and P[I = i | Ht ] =
for all i > t, so the optimal success probability Πt indeed depends only on t. 1−α
If we stop at time t, we succeed exactly when I = t, so we win with probability Πstop = t Ψt . t Let U denote the next record after time t. If we continue at time t, then the only way to reach a future decision state is if U = u > t. Thus, our success probability if we continue at time t is given by n X cont Πt = P[U = u | Ht ] · Πu . u=t+1
We next compute P[U = u | Ht ]. Observe that for any r ̸= I, we have P[Rr ̸= 1 | r < I] = 1 − 1r . If I = u, then u is the next record after t if there is no record in {t + 1, . . . , u − 1}. Hence, we get P[U = u | I = u, Ht ] =
u−1 Y r=t+1
1 1− r
=
t u−1
If I > u, then u is the next record after t if there is no record in {t + 1, . . . , u − 1} and u is a record itself, which happens with probability u1 conditioned on I > u. Thus, u−1 1 Y 1 t P[U = u | I > u, Ht ] = 1− = u r u(u − 1) r=t+1
14
Combining both with (2) and (3) gives n X
P[U = u | Ht ] = P[U = u | I = u, Ht ] · P[I = u | Ht ] + P[U = u | I > u, Ht ]
P[I = i | Ht ]
i=u+1 n X i−α + P[U = u | I > u, Ht ] = P[U = u | I = u, Ht ] · Ψt Ψt i=u+1 n X t = u1−α + i−α u(u − 1)Ψt
u−α
i=u+1
t Ψu . = u(u − 1)Ψt Since we already established that Πu only depends on u for all u ≥ t, we have Πcont = t
n X
P[U = u | Ht ] · Πu =
u=t+1
n X u=t+1
n t 1 X t Ψu · Πu = Φu . u(u − 1)Ψt Ψt u(u − 1) u=t+1
In total, taking the maximum over both actions yields 1−α n t t 1 X Φu . , Ψt Ψt u(u − 1)
Πt = max{Πstop , Πcont } = max t t
u=t+1
Multiplying by Ψt gives (1) and completes the proof of the lemma. To solve the recursion just proved, we characterize the success probability of the previously defined threshold policies A(max{S, k}). Recall that A(max{S, k}) accepts the first record at or after the signal, but not before k. Lemma 10 (Threshold policy characterization). Let k ∈ {2, . . . , n}. The success probability of the threshold policy A(max{S, k}) is ! n i−1 X 1 1X 1− rα . pn,α (k) = n (i − 1)iα i=k
r=k
For k = 1, the success probability of A(max{S, 1}) is pn,α (1) = pn,α (2) + n1 . Proof. First, fix k ∈ [n]. We condition on I = i. If i < k, then A(max{S, k}) clearly cannot win, and these events do not contribute to pn,α (k). Hence, for i = 1, only A(max{S, 1}) has a positive probability of winning; it succeeds with probability 1 if I = 1. Now, assume i ≥ max{2, k} and additionally condition on S = s. The policy starts accepting at time max{s, k}. It succeeds if and only if the largest item among the first i − 1 arrivals appears before time max{s, k}. Since its location is uniform in {1, . . . , i − 1}, we obtain P[success | I = i, S = s] =
max{s, k} − 1 . i−1
With the law of total probability, i.e., by averaging over S, we obtain P[success | I = i] =
i X sα − (s − 1)α max{s, k} − 1 · iα i−1 s=1
15
k−1
i
s=1
s=k
X k−1 X α 1 α α α = s − (s − 1) + (s − 1) s − (s − 1) . (i − 1)iα (i − 1)iα The first sum telescopes to (k − 1)α . For the second sum, i X
α
α
(s − 1) s − (s − 1)
α
= (i − 1)i − (k − 1)
α+1
−
s=k
i−1 X
rα .
r=k
Hence, i−1
P[success | I = i] = 1 −
X 1 rα . α (i − 1)i r=k
for i ≥ 2. Averaging over the uniform choice of I proves the statement if k ≥ 2. For k = 1, recall that P [success | I = 1] = 1. Hence, averaging again over I concludes the proof. We can now finally characterize the optimal policies in both regimes, α ≥ 1 and 0 < α < 1. Theorem 2. For α ≥ 1, the policy A(S) is optimal. For 0 < α < 1, there is a threshold kn ∈ [n] n→∞ such that the policy A(max{S, kn }) is optimal and knn −−−→ (1 − α)1/α . If OPTn (α) denotes the optimal success probability on instances of length n, then 1+1/α α + (1 − α) , 0 < α < 1, n→∞ α+1 OPTn (α) −−−→ OPT(α) := α , α ≥ 1. α+1 Proof. We solve the Bellman recursion from Lemma 1. Case 1: α ≥ 1. We claim that Φt = t1−α for every t, i.e. it is optimal to stop at the first record after the signal. The proof is by backward induction on t. The claim is clear for t = n. Assume it holds for all u ≥ t + 1 ≥ 2. Then the term representing continuing (and not stopping) in (1) equals n n X X t 1 Φu = t . u(u − 1) (u − 1)uα u=t+1
u=t+1
1 By Bernoulli’s inequality, we have u−1 ≤
1 α 1 + u−1 ) − 1 for all u ≥ 2. Multiplying by u−α gives
1 1 1 ≤ − α. α α (u − 1)u (u − 1) u Inserting in the previous inequality yields t
n X u=t+1
n
X 1 ≤ t (u − 1)uα
u=t+1
1 1 − (u − 1)α uα
= t t−α − n−α < t1−α .
Hence, stopping is better than continuing at every time and, thus, optimal. Therefore, A(S) is optimal. It remains to evaluate the success probability of A(S) = A(max{S, 1}). With Lemma 10, we obtain ! n i−1 X 1 1X 1 OPTn (α) = pn,α (1) = + 1− rα . n n (i − 1)iα i=2
16
r=1
In order to determine the behavior of OPTn (α) for n → ∞, we observe that i−1 X
rα =
r=1
iα+1 + O(iα ), α+1
for i ≥ 2. Hence, i−1
X 1 rα = 1 − 1− (i − 1)iα r=1
Overall,
α+1 i α α + O(i ) = + O(i−1 ). α+1 α+1
α log n OPTn (α) = , +O α+1 n
which proves the limiting behavior for α ≥ 1. P 1 Case 2: 0 < α < 1. We start by defining kn . To this end, let Gt := t1−α − t nu=t+1 (u−1)u α for t ∈ [n] and set kn := min{t ∈ [n] : Gt ≥ 0}. We will show that kn satisfies the claims, i.e., that n→∞ A(max{S, kn }) is optimal and that knn −−−→ (1 − α)1/α . To this end, we first observe that Gn ≥ 0 as the sum is empty, and hence, kn is well-defined. We next show that the optimal policy is a threshold rule. Set n X
Cn := (kn − 1)
u=kn
1 . (u − 1)uα
Consider the solution to (1) given by ( t < kn , b t = Cn , Φ 1−α t , t ≥ kn . We verify that this satisfies the Bellman equation: Observe that Gt+1 Gt 1 (t + 1)1−α − t1−α − = (t + 1)−α − t−α + = > 0. t+1 t t(t + 1)α t Hence, Gtt is strictly increasing in t, and Gt ≥ 0 for t ≥ kn due to this monotonicity and the definition of kn . Thus, for t ≥ kn , 1−α
t
≥t
n X u=t+1
n X 1 t bu = Φ (u − 1)uα u(u − 1) u=t+1
implying that stopping is optimal. Therefore, for kn = 1, we have just shown that A(max{S, 1}) is optimal. Now suppose that kn > 1. If t < kn , then kX n n −1 X t t t bu = Cn + u1−α Φ u(u − 1) u(u − 1) u(u − 1) u=t+1 u=t+1 u=kn n X 1 1 1 =t − Cn + t t kn − 1 (u − 1)uα n X
u=kn
b t. = Cn = Φ
17
Moreover, Gkn −1 < 0 by definition of kn . Hence, n X
Cn = (kn − 1)
u=kn
1 > (kn − 1)1−α . (u − 1)uα
Since t1−α is increasing for 0 < α < 1, we get b t = Cn > t1−α Φ for all t < kn . Thus, continuing is optimal for t < kn . Combined with the restriction from Lemma 1 that one only stops at records at or after the signal, policy A(max{S, kn }) behaves as desired. It remains to determine the asymptotic behavior of kn . Fix c ∈ (0, 1] and let tn = ⌊cn⌋. Hence, 1−α 1−α n n tn nα tn X tn tn 1 X u −(α+1) u α−1 − = − n Gtn = · . n n (u − 1)uα n n n n u−1 u=tn +1
u=tn +1
Thus, in the limit, n
α−1
n→∞
1−α
Gtn −−−→ c
Z 1 −c
y −(α+1) dy = c1−α − c
c
c−α − 1 c − (1 − α)c1−α = . α α
The expression on the right-hand side is equal to 0 if and only if c = (1−α)1/α , while nα−1 Gtn = 0 if and only if Gtn = 0. Moreover, since Gtt is strictly increasing, it follows that kn n→∞ −−−→ (1 − α)1/α =: cα . n Finally, for n sufficiently large, kn ≥ 2, and we can apply Lemma 10 with k = kn to obtain n i−1 X X 1 1 1 − rα OPTn (α) = pn,α (kn ) = n (i − 1)iα i=kn
r=kn
Focus on the inner sum. Using y = ni gives i−1
i−1
Z y
r=kn
cα
X nα+1 X 1 r α n→∞ 1 1 α r = −−−→ α+1 α α (i − 1)i (i − 1)i n n y r=kn
z α dz .
Now we have for the outer sum Z 1 Z y n i−1 X X 1 1 1 α n→∞ α 1 − −−−→ 1 − α+1 z dz dy. r n (i − 1)iα y cα cα i=kn
r=kn
Ry α+1 −cα+1 α Evaluating the inner integral gives cα z α dz = y α+1 . Thus the whole integrand of the outer integral becomes 1 y α+1 − cα+1 α cα+1 α α 1 − α+1 · = + . y α+1 α + 1 (α + 1)y α+1 Hence the outer integral evaluates to α cα − cα+1 α2 + (1 − α2 )cα − cα+1 α α (1 − cα ) + = α+1 α(α + 1) α(α + 1) =
α2 + (1 + α)(1 − α)1+1/α − (1 − α)1+1/α α + (1 − α)1+1/α = . α(α + 1) α+1
This proves the claimed limit for 0 < α < 1. 18
B
Omitted proofs from Section 3
We start by investigating the behavior of A(max{S, ⌈βn⌉}) for an arbitrary parameter β ∈ [0, 1]. Lemma 11. Fix α > 0 and β ∈ [0, 1]. Let kn = ⌈βn⌉ and pn,α (k) denote the success probability of the threshold policy A(max{S, k}). Then, n→∞
pn,α (kn ) −−−→ f (α, β) :=
α 1−α β α+1 + β− . α+1 α α(α + 1)
Proof. If β = 0, then kn = 0 for all n, and the claim follows from the analysis of A(S) from the first case in the proof of Theorem 2. Assume now that β > 0 and consider n large enough such that kn ≥ 2. Hence, Lemma 10 yields n i−1 X X 1 1 1 − pn,α (kn ) = rα . n (i − 1)iα i=kn
r=kn
As before, we want to analyze pn,α (kn ) in the limit (for n → ∞). To this end, we approximate the sum using the Riemann integral of an appropriate function. Following the same steps as in the proof of Theorem 2 with ⌈βn⌉ as the lower limit and with y = ni Z y Z 1 1 n→∞ α z dz dy . pn,α (kn ) −−−→ 1 − α+1 y β β Evaluating the inner integral again, we obtain Z y 1 α β α+1 1 − α+1 z α dz = + , y α + 1 (α + 1)y α+1 β and can evaluate the whole term to obtain α β α+1 f (α, β) = (1 − β) + α+1 α+1
Z 1
y −α−1 dy
β
α β α+1 β −α − 1 = (1 − β) + · α+1 α+1 α α+1 α 1−α β = + β− . α+1 α α(α + 1) This completes the proof of the lemma. Next, we show how to maximize f (α, β) as a function of β ∈ [0, 1]. Lemma 12. For every fixed α > 0, the function f (α, ·) is maximized over [0, 1] by ( (1 − α)1/α , 0 < α < 1, β ⋆ (α) = 0, α ≥ 1. Further, f (α, β ⋆ (α)) = OPT(α). Proof. By Lemma 11,
α dfβ (α) d2 f (α) = 1−α−β and dββ 2 = −β α−1 . dβ α
If 0 < α < 1, the unique stationary point is given by β α = 1 − α, i.e., β ⋆ (α) = (1 − α)1/α . Observe that the second derivative is negative there, making β ⋆ (α) indeed the maximizer. If α ≥ 1, then 1 − α − β α < 0 for every β > 0, so f (α, β) is strictly decreasing on (0, 1] and the maximum is attained at β = 0. Substituting β ⋆ (α) into the formula from Lemma 11 yields exactly OPT(α). 19
We now have all ingredients together to calculate the success probability if we are only given an estimate α̂ for the parameter α. Theorem 3 (Smoothness and Robustness). Let α > 0 and α̂ > 0. The policy A(max{S, kn }) with kn = ⌈β ⋆ (α̂)n⌉ has an asymptotic success probability of at least α 1−α (1 − α̂)(α+1)/α̂ + (1 − α̂)1/α̂ − , α+1 α α(α + 1) g(α, α̂) = α , α+1
0 < α̂ ≤ 1, α̂ ≥ 1.
In particular, if α̂ ≤ α, then g(α, α̂) ≥ OPT(α̂) ≥ 1e . Proof. If 0 < α̂ < 1, then β ⋆ (α̂) = (1 − α̂)1/α̂ by Lemma 12, so the formula g(α, α̂) follows by substituting this value of β into Lemma 11. α If α̂ ≥ 1, then β ⋆ (α̂) = 0, so the asymptotic success probability is α+1 by Lemma 11.
For the second part, we distinguish 0 < α̂ < 1 and α̂ ≥ 1 and assume that α̂ ≤ α. If α̂ ≥ 1, then g(α, α̂) =
α α̂ ≥ = OPT(α̂) α+1 α̂ + 1
x since x 7→ x+1 is increasing.
Now suppose 0 < α̂ < 1. We want to show that α 7→ g(α, α̂) is increasing, which implies g(α, α̂) ≥ g(α̂, α̂). To this end, we set β = β ⋆ (α̂) = (1 − α̂)1/α̂ . Observe that α α β α+1 1 g(α, α̂) = + β− = 1−β− α+1 1−α α(α + 1) α
1 − β α+1 1−β− α+1
1 = 1−β− α
Z 1
(1−tα ) dt.
β
α
For each t ∈ (0, 1), the function 1−t α is decreasing in α since 1 − tα = α
Z 1
uα−1 du
t
and uα−1 is decreasing in α for 0 < u < 1. Hence, Z 1 1 α 7→ (1 − tα ) dt a β is decreasing, and overall, α 7→ g(α, α̂) is increasing. Therefore, with α ≥ α̂ by assumption, g(α, α̂) ≥ g(α̂, α̂) . Finally, β = β ⋆ (α̂) and Lemma 12 allow us to conclude g(α̂, α̂) = OPT(α̂). Thus, g(α, α̂) ≥ OPT(α̂) if α̂ ≤ α.
20
C
Omitted proofs from Section 4
C.1
Randomized optimal policy
Theorem 4 (Randomized optimum). Let α > 0. For adversarial arrival orders with anPα-power signal, the optimal success probability for randomized policies is OPTrand (α) = nα /( nj=1 j α ). n The policy A(max{R, S}) is optimal where R ∈ [n] is independent of S and, for r ∈ [n], Pr α nα j=1 j P[R ≤ r] = Pn · . α rα j=1 j Proof. Let
nα cn,α := Pn
j=1 j
α
.
We want to show that OPTrand (α) = cn,α . To this end, we first show that A(max{S, R}) n guarantees success probability cn,α on every instance of length n before proving that no policy can do better. We have
Pr F (r) := P[R ≤ r] = cn,α
j=1 j rα
α
.
Fix an instance whose maximum arrives at time i⋆ . Note that i⋆ is always a record. Since S follows the α-power distribution on [i⋆ ], it holds that ⋆ i −1 α ⋆ P[S = i ] = 1 − i⋆ and consequently P[S ≤ i⋆ − 1] =
⋆ i −1 α . i⋆
Policy A(max{S, R}) succeeds in at least the following two disjoint cases: If S = i⋆ and R ≤ i⋆ or if S ≤ i⋆ − 1 and R = i⋆ , A(max{S, R}) stops at i⋆ . Thus, ⋆ ⋆ i −1 α i −1 α ⋆ P[success] ≥ 1 − F (i ) + F (i⋆ ) − F (i⋆ − 1) ⋆ ⋆ i i ⋆ α i −1 = F (i⋆ ) − F (i⋆ − 1) i⋆ Pi⋆ α Pi⋆ −1 α ! j=1 j j=1 j = cn,α − = cn,α . α ⋆ i i⋆ α Hence, there is a policy with success probability at least cn,α which completes the proof of the lower bound on the optimal success probability. For the matching upper bound, let A be any randomized policy and let pi be its success probability on the hard instance Ii = (1, 2, . . . , i, 0, . . . , 0). With gs := sα − (s − 1)α for s ∈ [n], we have P [S = s] = igαs on Ii . For a signal time s ∈ [n] and a time t ∈ [n], let qs,t be the probability that A stops at time t on instance In conditioned on the signal occurring at time s. If s ≤ i, then Ii and In are identical up to time i. Hence, the decisions of A are identical up to i on Ii and In . Thus, we can rewrite pi as pi =
i X s=1
i
1 X P [success on Ii | S = s] P [S = s] = α gs qs,i . i s=1
21
Therefore, n X
α
i pi =
n X i X
gs qs,i =
i=1 s=1
i=1
n X
gs
s=1
n X
qs,i ≤
n X
gs = nα ,
s=1
i=s
where the inequality holds because, for each fixed signal time s, the policy A can stop at most once. This implies nα min pi ≤ Pn α = cn,α . i∈[n] i=1 i Since the worst-case guarantee of A is at most its minimum success probability on the family {Ii }ni=1 , no randomized policy can beat cn,α . This completes the proof of the upper bound and thus of the theorem. Corollary 5. For adversarial orders with an α-power signal, OPTrand (α) = o(1) if α = o(n) n rand −c and OPTn (α) → 1 − e for α/n → c ∈ (0, ∞). Proof. The exact formula from Theorem 4 and the bound n X
α
Z n
i ≥
xα dx =
0
i=1
give
nα+1 α+1
α+1 , n
OPTrand (α) ≤ n which proves the asymptotic behavior for α = o(n).
For αn → c, write α = cn + o(n) for some constant c > 0. Then n X iα i=1
nα
=
n α X i i=1
=
n
n−1 X j=0
j 1− n
α .
For each fixed j, it holds that 2 j α j j n→∞ 1− = exp α log 1 − = exp −(c + o(1))j + O −−−→ exp(−jc) . n n n Hence,
n X iα i=1
Thus,
C.2
n
n→∞
−−−→ α
∞ X
e−cj =
j=0
1 . 1 − e−c
nα nα n→∞ P P −−−→ 1 − e−c . OPTrand (α) = = n n n α α α /nα i n i i=1 i=1
Deterministic optimal policy
Theorem 6 (Deterministic optimum). Let α > 0. For adversarial orders with an α-power signal, 1 α policy A(S) is optimal with success probability OPTdet . n (α) = 1 − 1 − n Proof. For the lower bound, consider policy A(S). If the maximum is at position i⋆ , this policy succeeds if S = i⋆ , which happens with probability ⋆ i −1 α 1 α ⋆ P[S = i ] = 1 − ≥1− 1− . i⋆ n 22
Hence, OPTdet P[S = i⋆ ] = 1 − n (α) ≥ min i⋆ ∈[n]
1 1− n
α ,
which proves the lower bound on the success probability. For the upper bound, we have observed that it suffices to consider policies that do not stop before the signal. Fix such a policy A and let τ : [n] → [n] be its stopping rule on instance In = (1, 2, . . . , n − 1, n). That is, τ (s) ≥ s is the time at which A stops when the signal occurs at time s. As before, Ii and In are indistinguishable until time i + 1. On instance Ii = (1, 2, . . . , i, 0, . . . , 0), the success probability is pi = P [success on Ii ] =
i X
P [success on Ii | S = s] P [S = s] =
s=1
X s≤i: τ (s)=i
sα − (s − 1)α . iα
If the worst-case guarantee is positive, i.e., pi > 0 for every i ∈ [n], then for every i there must exist at least one signal time s ≤ i with τ (s) = i. Since there are exactly n signal times and exactly n target times, this implies that every i ∈ [n] has exactly one preimage under τ . Hence, τ is a bijection of [n]. Since τ (s) ≥ s for all s, n X
τ (s) ≥
s=1
n X
s.
s=1
Because τ is a bijection, equality must hold. Thus, τ (s) = s for every s ∈ [n]. Therefore, every deterministic policy with positive worst-case guarantee agrees with A(S) on the instance family {Ii }ni=1 . In particular, pi = P [A(S) succeeds on Ii ]. Since A(S) succeeds on Ii if and only if S = i, this implies iα − (i − 1)α i−1 α pi = =1− . iα i This quantity is decreasing in i. Thus, the worst-case guarantee is attained at i = n and equals 1 α 1− 1− n implying that A(S) is indeed optimal. Corollary 7. For the adversarial orders with an α-power signal it holds that if α = o(n), then det −c OPTdet n (α) = o(1), and if α/n → c ∈ (0, ∞), then OPTn (α) → 1 − e . Proof. The exact formula from Theorem 6 gives 1 α 1− . n If α = o(n), then αn → 0 as n → ∞. Using log 1 − n1 = − n1 + O n12 , we get α 1 α α log 1 − =− +O = o(1) , n n n2 OPTdet n (α) = 1 −
and therefore
OPTdet n (α) = 1 − exp
1 α log 1 − = o(1) . n
If instead αn → c ∈ (0, ∞), then 1 α 1 n→∞ = · n log 1 − −−−→ −c , α log 1 − n n n n→∞ since n log 1 − n1 −−−→ −1. Hence, 1 n→∞ det OPTn (α) = 1 − exp α log 1 − −−−→ 1 − e−c . n 23
D
Omitted proofs from Section 5
D.1
Randomized optimal policy
Theorem 8. For all integers n, m ≥ 1, it holds that OPTrand (m) = OPTrand,full (m). n n (m) ≤ OPTrand,full (m) is immediate, since the full signal history Proof. The inequality OPTrand n n contains at least as much information as the last signal L. For the reverse inequality, fix a randomized policy A for the full-history model, and consider the hard instances Ii = (1, 2, . . . , i, 0, . . . , 0) for all i ∈ [n]. Let pi denote the success probability of A on Ii . It is enough to show that nm = OPTrand (m). min pi ≤ Pn n m i∈[n] j=1 j Consider first a labeled signal tuple s = (s1 , . . . , sm ) ∈ [n]m and let L(s) := maxj∈[m] sj . As before, for t ∈ {L(s), . . . , n}, let qs,t denote the probability that APstops at time t on In , conditioned on the event (S1 , . . . , Sm ) = s. For every fixed s, we have nt=L(s) qs,t ≤ 1, because A stops with probability at most 1. Now fix i ∈ [n]. On Ii , the tuple (S1 , . . . , Sm ) is uniformly distributed on [i]m . Moreover, for s ∈ [i]m , the decisions of A on Ii and on In are identical up to time i when conditioned on (S1 , . . . , Sm ) = s since these two instances are indistinguishable and the same signals have appeared by time t ∈ [i]. Hence, 1 X pi = m qs,i . i m s∈[i]
Multiplying by im and summing over all i ∈ [n] gives n X i=1
Therefore,
m
i pi =
n X X
qs,i =
i=1 s∈[i]m
X
n X
X
qs,i ≤
s∈[n]m i=L(s)
1 = nm .
s∈[n]m
Pn m i pi nm P ≤ . min pi ≤ Pi=1 n n m m i∈[n] i=1 i i=1 i
Since the worst-case guarantee of A is at most mini∈[n] pi and A was chosen arbitrarily, we obtain nm P = OPTrand (m). OPTrand,full (m) ≤ n n n m i i=1 by Theorem 4, which completes the proof.
D.2
Deterministic optimal policy
Recall that for a history h ∈ Hm , we defined ( λi (h) =
m! 1 c1 !·...·cℓ(h) ! · im ,
if ℓ(h) ≤ i,
0,
if ℓ(h) > i.
Lemma 13. Each history h ∈ H is observed on Ii with probability λi (h).
24
Proof. Fix an instance Ii . In the full-history model, the m signals are drawn independently and uniformly from [i]. It is convenient to temporarily consider the signals as labeled, so a signal realization is a tuple s = (s1 , . . . , sm ) ∈ [i]m . Each such labeled tuple has probability i−m . Given a labeled tuple s, the observed history records only the number of signals at each time. That is, if ℓ(s) := maxj∈[m] sj , then the induced history is h(s) = (c1 (s), . . . , cℓ(s) (s)), where ct (s) = |{j ∈ [m] : sj = t}|. Thus the policy observes the counts of signals at each time, but not the labels of the signals. Now fix a history h = (c1 , . . . , cℓ(h) ) ∈ H. If ℓ(h) > i, then no signal can occur at time ℓ(h) on the instance Ii since all signals are supported on [i]. Therefore h is impossible, and P[h is observed on Ii ] = 0 = λi (h). Assume instead that ℓ(h) ≤ i. The history h is observed exactly when, for every t ∈ [ℓ(h)], Pℓ(h) precisely ct of the labeled signals are equal to t. Since t=1 ct = m, this also accounts for all m signals, so no signal occurs after time ℓ(h). It remains to count how many labeled tuples s ∈ [i]m induce this same unlabeled history. We first choose the c1 labeled signals that occur at time 1, then the c2 labeled signals among the remaining ones that occur at time 2, and so on. This gives m m − c1 m − c 1 − c2 c · · · ℓ(h) . c1 c2 c3 cℓ(h) The factorials telescope, so the number of labeled tuples producing h is m! . c1 ! · · · cℓ(h) ! Here the convention 0! = 1 handles times at which no signal occurs. Since each labeled tuple has probability i−m , we obtain P[h is observed on Ii ] =
m! 1 · m. c1 ! · · · cℓ(h) ! i
This is exactly λi (h) by definition. Hence every history h ∈ H is observed on Ii with probability λi (h). Recall our ILP (ILP)
max z s.t.
n X
∀h ∈ H
xh,t = 1
t=ℓ(h)
X
λi (h) xh,i ≥ z
∀i ∈ [n]
h∈H:ℓ(h)≤i
xh,t ∈ {0, 1}
∀h ∈ H, ∀t ∈ {ℓ(h), . . . , n}
Theorem 9 (ILP characterization). The optimal objective value of (ILP) is equal to OPTdet,full (m). n Proof. First consider any deterministic policy A. As observed before, we may assume that A stops only after all m signals have appeared. Consider its behavior on In . For every history h, let τ (h) ∈ {ℓ(h), . . . , n} be the stopping time of A after observing h, and set xh,t = 1[τ (h) = t]. Then the first set of constraints is satisfied. 25
Now fix i ∈ [n]. Up to time i, the two instances Ii and In are identical, so after any history h with ℓ(h) ≤ i, the policy makes the same decision on Ii as on In . Hence, by Lemma 13 the success probability of A on Ii is exactly X λi (h) xh,i . h:ℓ(h)≤i
Therefore every deterministic policy induces a feasible solution to (ILP) with z ≤ min P[A wins on Ii ]. i∈[n]
Since the worst-case guarantee of A is at most its minimum success probability on the hard family {Ii }ni=1 , we obtain that OPTdet n,m is at most the optimal objective value of (ILP). Conversely, let x be any feasible solution to (ILP) with value z. Define a deterministic policy that ignores the item values, waits until all m signals have appeared, reads the resulting history h, and then stops at the unique time t with xh,t = 1. For any adversarial instance whose maximum is at position i, the distribution of the signal history is the same as on Ii because the signals depend only on the maximum position. Thus, the success probability of this policy is exactly X λi (h) · xh,i h: ℓ(h)≤i
when the maximum is at position i, and this is at least z for every i ∈ [n] by the second set of constraints. Hence the policy has worst-case guarantee at least z. This shows that the ILP optimum is at most OPTdet n,m . Using the characterization just proved, we now turn to the special case of two signals. Theorem 14. For m = 2, we have ℓ n o X 2 2 OPTdet,full (2) = max z ∈ [0, 1] : ⌈zt ⌉ ≤ ℓ for all ℓ ∈ [n] . n t=1
Proof. For m = 2, write a history as a sorted pair (a, b), 1 ≤ a ≤ b ≤ n, and let ( 2, a < b, w(a, b) = 1, a = b. The weight w(a, b) is the number of labeled signal pairs inducing the sorted history (a, b). We may assume that a deterministic policy waits until both signals have appeared. In order to show ℓ n o X 2 2 OPTdet,full (2) ≤ max z ∈ [0, 1] : ⌈zt ⌉ ≤ ℓ for all ℓ ∈ [n] , n t=1
fix a deterministic policy and consider its behavior on the hard instance In . For every history (a, b), let τ (a, b) ≥ b be the stopping time chosen by the policy on In . Define X Ct := w(a, b). 1≤a≤b≤t τ (a,b)=t
On the hard instance It , the history (a, b) occurs with probability w(a, b)/t2 , and the policy wins exactly when τ (a, b) = t. Hence its success probability on It is Ct /t2 . 26
Suppose the policy has worst-case guarantee at least z. Then Ct ≥ zt2 , and since Ct is an integer, Ct ≥ ⌈zt2 ⌉. Moreover, for every ℓ, all histories relevant for Iℓ must have second signal at most ℓ. The total weight of such histories is ℓ X b X
ℓ X w(a, b) = (2b − 1) = ℓ2 .
b=1 a=1
Therefore
b=1
ℓ X
⌈zt2 ⌉ ≤
t=1
ℓ X
Ct ≤ ℓ2
t=1
for all ℓ ∈ [n]. This proves the upper bound. For the other direction ℓ n o X 2 2 z ∈ [0, 1] : ⌈zt ⌉ ≤ ℓ for all ℓ ∈ [n] ,
OPTdet,full (2) ≥ max n
t=1
suppose that z ∈ [0, 1] satisfies ℓ X ⌈zt2 ⌉ ≤ ℓ2 t=1
for all ℓ ∈ [n]. Set dt := ⌈zt2 ⌉ for all t < n and dn := n2 − implies dn ≥ ⌈zn2 ⌉.
Pn−1
t=1 dt . The constraint for ℓ = n
We now construct a deterministic policy by greedily assigning histories to stopping times so that the total weight of histories assigned to time t is dt . Suppose that the assignments for times 1, . . . , t − 1 have already been made, and let At := {(a, b) : 1 ≤ a ≤ b ≤ t and (a, b) is not yet assigned} be the set of currently available histories. Every history in At can be assigned to time t, since its second signal is at most t. Moreover, the total available weight is Wt :=
X
2
w(a, b) = t −
t−1 X
ds ≥ dt ,
s=1
(a,b)∈At
where the inequality follows from the prefix constraint. It remains to justify that one can select available histories of exactly weight dt . The available histories have weights only 1 and 2, and the diagonal history (t, t) is newly available at step t and was not available before, so it is still unassigned and has weight 1. Thus At contains at least one weight-1 history. Let p ≥ 1 be the number of weight-1 histories in At , and let q be the number of weight-2 histories. Then Wt = p + 2q. We claim that for every integer r ∈ {0, . . . , Wt } there is a subset B ⊆ At with X w(a, b) = r. (a,b)∈B
Indeed, if r ≤ 2q, write r = 2u + ε with ε ∈ {0, 1}. If ε = 0, choose u ≤ q weight-2 histories. If ε = 1, then r ≤ 2q implies u ≤ q − 1, so choose u weight-2 histories and one weight-1 history. If instead r > 2q, choose all q weight-2 histories and r − 2q weight-1 histories; this is possible because r ≤ p + 2q implies r − 2q ≤ p.
27
Applying the claim with r = dt gives a subset of available histories of total weight exactly dt , which we assign to stopping time t. We do this for every t < n. At time n, assign all remaining histories to time n. The total remaining weight is n2 −
n−1 X
dt = dn ,
t=1
so the weight assigned to time n is exactly dn . Let τ (a, b) denote the stopping time assigned to history (a, b). By construction, for every t ∈ [n], the total weight of histories assigned to stopping time t is exactly dt , that is, X w(a, b) = dt . 1≤a≤b≤t τ (a,b)=t
Now consider any instance whose maximum arrives at time t. The two signals are independent and uniform on [t]. Hence a sorted history (a, b) with a ≤ b ≤ t occurs with probability w(a, b)/t2 . The policy wins exactly on those histories that are assigned to stopping time t because then it stops exactly when the maximum arrives. Therefore the success probability on such an instance is X w(a, b) dt = 2 ≥z , t2 t 1≤a≤b≤t τ (a,b)=t
where the final inequality follows from dt = ⌈zt2 ⌉ ≥ zt2 for t < n, and dn = n2 −
n−1 X
⌈zt2 ⌉ ≥ ⌈zn2 ⌉ ≥ zn2 .
t=1
This defines a deterministic policy with worst-case success probability at least z. Hence z is achievable by a deterministic policy, so OPTdet,full (2) must be at least z. This concludes the n second part of the proof. 6(n−1) 6n Corollary 15. For every integer n ≥ 4, we have (n+1)(2n+1) ≤ OPTdet,full (2) ≤ (n+1)(2n+1) . In n det,full 3 1 particular, it holds that OPTn (2) = n + O n2 .
Proof. Let z ⋆ := OPTdet,full (2). Then, z ⋆ is feasible for the characterization given in Theorem 14. n Hence, using the constraint for ℓ = n, we get z
⋆
n X
2
t ≤
t=1
Since
Pn
t=1 t
n X
⌈z ⋆ t2 ⌉ ≤ n2 .
t=1
2 = n(n+1)(2n+1) , this gives 6
n2 ⋆ P OPTdet,full (2) = z ≤ n n
t=1
For the lower bound, set z :=
t2
=
6n . (n + 1)(2n + 1)
6(n − 1) . (n + 1)(2n + 1)
We show that z is feasible for the characterization given in Theorem 14. For this, set g(ℓ) :=
6(ℓ − 1) . (ℓ + 1)(2ℓ + 1) 28
A direct computation gives, for every ℓ ≥ 3, g(ℓ + 1) − g(ℓ) =
12(−ℓ2 + ℓ + 3) < 0. (ℓ + 1)(ℓ + 2)(2ℓ + 1)(2ℓ + 3)
Thus g is decreasing on {3, 4, . . .}. Moreover, g(2) = g(4) = 25 , so for every n ≥ 4 and every ℓ ∈ {2, . . . , n} we have z = g(n) ≤ g(ℓ). Now fix ℓ ∈ [n]. If ℓ = 1, then 0 < z ≤ 1, and hence 1 X
⌈zt2 ⌉ = ⌈z⌉ = 1.
t=1
If ℓ ≥ 2, then ⌈x⌉ ≤ x + 1 for every real x, and therefore ℓ X t=1
2
⌈zt ⌉ ≤ z
ℓ X
t2 + ℓ = z
t=1
ℓ(ℓ + 1)(2ℓ + 1) ℓ(ℓ + 1)(2ℓ + 1) + ℓ ≤ g(ℓ) + ℓ = ℓ2 . 6 6
Thus z satisfies all feasibility inequalities in Theorem 14, and so OPTdet n,2 ≥ z =
6(n − 1) . (n + 1)(2n + 1)
The two bounds differ by 6n 6(n − 1) − =O (n + 1)(2n + 1) (n + 1)(2n + 1) and the upper bound is n3 + O n12 . Hence, 3 1 det OPTn,2 = + O . n n2
E
1 n2
,
Additional numerical experiments
This section contains additional experiments supporting the numerical results in Section 6 and the adversarial-order theory in Section 4. We separate the experiments into random-order experiments, which extend the main empirical evaluation, and adversarial-order experiments, which illustrate the hard instances and scaling regimes.
E.1
Additional random-order experiments
The experiments in this subsection use the same setup as in Section 6. In each trial we sample a full random permutation of ranks [n], draw the signal S conditional on the realized arrival time I of the maximum, run the corresponding stopping rule on the realized order, and record whether the selected item is the maximum. The plotted curves are empirical success probabilities of the actual stopping rules over 1000 trials. Confidence bands are 95% confidence intervals. Model scaling with n. The first experiment repeats the model evaluation for several values of n. For each α, we use the finite-n optimal threshold from Theorem 2 and estimate its success probability. Figure 4 compares these empirical curves with the asymptotic optimum OPT(α) and the traditional 1e benchmark. The curves approach the asymptotic formula as n grows, while already showing the improvement over the classic A ne policy at moderate problem sizes. 29
Clean-model for different instance sizes
empirical success probability
1.0 0.9 0.8 0.7 0.6
n=5 n=20 n=100 OPT( ) 1/e
0.5 0.4 0.3
10 1
100
true signal quality
101
Figure 4: Random-order experiments for several problem sizes. Each curve shows the empirical success probability of the finite-n optimal asynchronous threshold policy from Theorem 2. The dashed curve is the asymptotic optimum OPT(α). Misspecification slices and induced thresholds. The middle panel of Figure 3 summarizes robustness to misspecification as a heatmap. Figure 5 gives a complementary one-dimensional view. We fix several true values of α and vary the estimated parameter α̂. We consider the policy A(max{S, kn }) from Theorem 3 that is tuned to the threshold kn (α̂) = max{1, ⌈β ⋆ (α̂)n⌉}. For each true α, the same sampled instances are used for all values of α̂, giving a paired comparison across thresholds. The lower panel plots the induced threshold fraction knn(α̂) . This makes explicit why the success curves become flat once α̂ ≥ 1: all such predictions induce the same signal-trusting policy A(S). The qualitative behavior is consistent with Theorem 3: conservative tuning is robust, while sufficiently overconfident tuning can be harmful when the true signal arrives early. Separating the noisy-signal failure modes. The right panel of Figure 3 combines three corruption types into one mixed corruption rate. Figure 6 separates these effects. In each panel, with probability 1 − ρ the clean signal is observed, while with probability ρ the signal is corrupted in one specified way: it is missed entirely, replaced by a uniformly random false alarm in [n], or delayed to a uniformly random time after I when such a time exists. We compare the optimal policy from Theorem 2, the classic threshold A ne policy, and the fallback policy from Section 6. Missed and late signals mostly harm the pure asynchronous policy by preventing it from acting in time, whereas false alarms can induce premature stopping. The fallback rule mitigates both effects by reverting to the classic threshold when the signal is absent or arrives too late.
E.2
Additional adversarial-order experiments
We now supplement the adversarial-order results from Section 4. These experiments use the hard family Ii = (1, 2, . . . , i, 0, . . . , 0) where the maximum is at position i and no item after time i is a record. Unlike the random-order experiments above, there is no permutation randomness: the adversary fixes the instance Ii . In the single-signal experiments, randomness comes only from the signal time S and, for randomized policies, from the internal random threshold of the algorithm. The full-history experiment for m = 2 is computed exactly from the characterization in Theorem 14.
30
Robustness slices, n=1000
empirical success probability
0.7
all
0.6
1 induce (1)
0.5 0.4 0.3
true = 1 true = 2
true = 0.25 true = 0.5
0.2
k( )/n
0.3 0.2 0.1 0.0
0.0
0.2
0.4
0.6
0.8
1.0
predicted signal quality
1.2
1.4
Figure 5: Misspecification slices in the random-order model. The top panel shows empirical success probabilities as a function of the predicted parameter α̂ for several true values of α. The bottom panel shows the induced threshold fraction kn (α̂)/n, explaining the plateau for α̂ ≥ 1.
Noisy-signal breakdown, n=1000
empirical success probability
Missed signals
False alarms
Late signals
0.5 0.4 0.3 0.2
optimal policy fallback classical
0.1 0.0 0.0
0.2
0.4
0.6
corruption rate
0.8
1.0 0.0
0.2
0.4
0.6
corruption rate
0.8
1.0 0.0
0.2
0.4
0.6
corruption rate
0.8
1.0
Figure 6: Noisy-signal breakdown in the random-order model. The three panels isolate missed signals, false alarms, and late signals. The fallback policy gives a smoother degradation than the pure asynchronous policy across the different corruption mechanisms.
31
empirical success probability
1.0
Adversarial hard family Ii, n = 1000, = 1000 opt. det. policy opt. rand. policy
0.9 0.8 0.7 0.6 0.0
0.2
0.4
0.6
adversarial maximum position i/n
0.8
1.0
Figure 7: Adversarial position profile on the hard family Ii . The deterministic signal-stopping rule is sensitive to the adversarial maximum position, while the randomized minimax policy from Theorem 4 approximately equalizes success across positions. Position profile of the hard family. The first adversarial experiment fixes n and α and varies the adversarial maximum position i. We compare the deterministic signal-stopping rule from Theorem 6 with the randomized policy from Theorem 4. The deterministic policy succeeds on Ii only when the signal reaches the maximum position, so its success probability depends strongly on i. The randomized policy approximately equalizes the hard-family instances, as shown in Theorem 4. Scaling regime α = cn. The second adversarial experiment studies the regime α = cn. For each constant c > 0, we estimate the empirical worst-case success probability over the sampled hard-family positions and compare it with the exact deterministic and randomized values from Theorems 4 and 6. The limiting behavior is governed by Corollaries 5 and 7: when α is proportional to n, both values approach the constant curve 1 − e−c . Figure 8 confirms that the empirical worst-case values track the exact finite-n curves and approach this limit. Full history versus the last signal for m = 2. The final adversarial experiment considers the multiple-signal model from Section 5. Revealing only the last signal L = maxj Sj is equivalent to a single α-power signal with α = m. Thus, for m = 2, the deterministic last-signal baseline is given by Theorem 6 with α = 2, while the randomized last-signal value is given by Theorem 4; Theorem 8 shows that randomized algorithms gain no additional worst-case power from observing the full history. For deterministic algorithms, however, full history can help. We compute the exact full-history value for m = 2 using Theorem 14 and compare it with the last-signal baselines. The shaded region in Figure 9 shows the finite-n bounds from Corollary 15. The figure illustrates the separation: the deterministic full-history value scales like n3 , whereas the deterministic last-signal value scales like n2 .
32
Adversarial scaling regime, n = 1000
worst-case success probability
1.0 0.8 0.6 0.4 0.2 0.0
0.5
1.0
opt. det. policy opt. rand. policy
limit 1 e c
1.5
2.5
2.0
signal concentration c = /n
3.0
Figure 8: Adversarial scaling regime α = cn. Empirical worst-case success probabilities match the exact finite-n deterministic and randomized values and approach the limit 1 − e−c .
empirical success probability scaled by n
Adversarial full-history separation for m = 2 3.0 2.8 2.6
last signal, deterministic full two-signal history, deterministic last signal, randomized theoretical bounds
2.4 2.2 2.0 1.8 1.6 101
problem size n
102
Figure 9: Full-history separation for m = 2 in the adversarial-order model. The full-history deterministic value from Theorem 14 lies between the bounds in Corollary 15 and is strictly larger than the deterministic last-signal value from Theorem 6.
33