betaFeedback

WorksMathematics

Low-dimensional optimal stopping with rank-dependent loss

Abstract

Sequential selection problems with independent observable scores and rank-dependent objectives are not reducible, in general, to dynamic optimisation over a state space of fixed dimension. We consider optimal stopping problems with truncated loss structures through the lens of the planar Poisson process, where self-similarity removes the time variable and the state is reduced to the mm lowest scores observed so far, rescaled to the initial time. For m=1m=1 the optimal rule stops at the first record below a hyperbola, which is found by a sliding-window argument. For m=2m=2 we derive the equations for the boundaries of the stopping sets of 11-records and 22-records, solve them explicitly on a part of the state space, and express the optimal values by quadratures. The value function and the optimal strategy are characterised by a static integro-differential equation. The optimal strategies are compared with simple low-parameter rules, which are close to optimality.

Introduction

Let X1,…,XnX_1,\ldots,X_n be independent random scores sampled from some continuous distribution. The scores are observed sequentially, with the aim to select one of them using a nonanticipating stopping rule τ\tau with values in [n]:={1,…,n}[n]:=\{1,\ldots,n\}. With each score XkX_k we associate its final rank among all nn scores,

Rk,n:=#{i∈[n]:Xi≤Xk}.(1)R_{k,n}:=\#\{i\in[n]:X_i\le X_k\}. \tag*{(1)}

In ‘secretary problems’ the loss for selecting XkX_k depends on the scores (X1,…,Xn)(X_1,\ldots,X_n) through the ranking permutation (R1,n,…,Rn,n)(R_{1,n},\ldots,R_{n,n}) [24]. This includes in the first turn stopping problems with objectives of the form

E q(Rτ,n)→min⁡,(2)\mathbb{E}\,q(R_{\tau,n})\to\min, \tag*{(2)}

where q(r)q(r) is a nondecreasing function on the integers; the classical best-choice objective being q(r)=1(r>1)q(r)=1(r>1). The nature of a selection problem largely depends on the type of information allowed in stopping rules.

In rank-information problems one considers the family of stopping rules adapted to the sequence (Ik,k∈[n])(I_k,k\in[n]) of initial ranks

Ik:=#{i∈[k]:Xi≤Xk},(3)I_k:=\#\{i\in[k]:X_i\le X_k\}, \tag*{(3)}

where I1,…,IkI_1,\ldots,I_k encode the ranking permutation of the first kk scores. Adopting the terminology of extreme-value theory, we say that XkX_k is an ii-record if Ik=iI_k=i, and just a record if i=1i=1. By exchangeability, the sequence of final ranks is a uniformly random permutation of [n][n], the initial ranks are independent with IkI_k uniformly distributed on [k][k], and Rk,nR_{k,n} is independent of I1,…,Ik−1I_1,\ldots,I_{k-1}. For problems (2) this implies that the optimal decision at stage kk depends on the observed scores through IkI_k, which makes the stopping problems efficiently solvable by backward induction, as the continuation value only depends on kk and nn. The structural clarity underlies the large-sample theory developed for (2) and related problems in the framework of a continuous-time infinite-arrivals model [9], where the value function is determined from a piecewise differential equation [21]. Closed-form asymptotic solutions are available, in particular, for the problem of choosing one of the mm best with q(r)=1(r>m)q(r) = \mathbf{1}(r > m) [8, 10, 20, 21], and Lindley’s minimum rank problem with the linear loss q(r)=rq(r) = r [4, 16, 21].

In full-information problems the optimum is sought within the larger family of all stopping rules adapted to (Xk,k∈[n])(X_k, k \in[n]). The term ‘full-information’ was coined in [10] to stress that the observer knows exactly the source distribution (which may be assumed uniform), and can use the score values in the selection strategies. The informational advantage makes the optimisation problem much more complex, because the global ranking couples the observed and future scores, thus forcing history dependence of the continuation value and decisions. To date the sole completely understood instance is the best-choice problem, reducible to optimal stopping of the univariate Markovian sequence of records [12, 13, 18]. For problems (2) with general qq, in particular for the linear loss – known in this full-information setting as the Robbins problem – one should not expect a closed-form solution, since the continuation value at stage kk depends on all kk past scores [1, 6], and the full history dependence persists in the limit [14]. The present paper aims to illustrate how the complexity grows with the dimension, by focusing on truncated loss structures, where only a small number mm of the ii-record processes, i≤mi \le m, is relevant. Concretely, we consider two loss structures:

An,m ⁣:the loss for selecting an i-record Xk is min⁡(i,m+1)+#{k<j≤n:Xj<Xk},(4)A_{n,m}\colon\text{the loss for selecting an }i\text{-record }X_k\text{ is }\min(i,m+1)+\#\{k<j\le n:X_j<X_k\}, \tag*{(4)}
Bn,m ⁣:q(r)=1(r>m) for the final rank r.(5)B_{n,m}\colon\qquad q(r)=\mathbf{1}(r>m)\text{ for the final rank }r. \tag*{(5)}

In problem An,mA_{n,m} the loss is the capped initial rank plus the number of later smaller scores. This objective was employed in [2] to compute numerical lower bounds for the value in Robbins’ problem. We will show that problem An,1A_{n,1} has a simple asymptotic solution, very much in line with the best-choice problem Bn,1B_{n,1}, both are treated here by a novel sliding window approach. We further consider An,2A_{n,2} and Bn,2B_{n,2}, which require keeping track of the 1- and 2-record processes. For Bn,mB_{n,m} the best of the explored single-curve rules has the failure probability within 7.5% (m=2m=2) and about 20% (m=3m=3) of the optimum computed in [19], and two- or three-parameter rules reduce the excess to below 1%. This suggests that for problems with rank-dependent loss the complexity of the exactly optimal strategies is not matched by the gain over simple low-parameter rules, in accord with our findings on the best-choice problem [17].

In [12, 13, 18] the full-information best-choice problem and some of its versions were embedded in a planar Poisson process (PPP) – an infinite-arrivals model providing a natural framework for the asymptotic analysis. In [14] this connection was extended to problems with objective (2) where the stopping value remains bounded as n→∞n \to\infty. In [17] we applied the PPP as a tool to compare the optimal best-choice strategy against a memoryless rule, which stops at the first arrival below a precommitted time-dependent threshold. Here we continue this line by using the self-similarity of the PPP to eliminate the time variable from the integro-differential optimality equation, to reveal the structural patterns of the optimal adaptive threshold, and to evaluate the limits in (4) and (5).

The rest of the paper is organised as follows. In § 2 we connect the discrete-time problems (4), (5) with their PPP counterparts AmA_m, BmB_m, show the convergence of the optimal stopping values, and analyse the optimality equation for the value function. The central optimality result, Theorem 2.4, is proved for more general loss structures; we need a special argument using self-similarity and an embedded Markov chain with a finite number of steps, since the PPP setting, with infinitely many arrivals and a rank-dependent loss, is not covered verbatim by the standard theorem. Proposition 2.7 describes the pathwise behaviour of the adaptive acceptance threshold: we show that this is a nondecreasing process drifting continuously between arrivals, jumping up at some arrival times, and staying flat once it reaches a past score. § 3 presents explicit solutions for m=1m=1. § 4 describes the geometric boundaries of the two-dimensional stopping sets, and § 5 and § 6 give the solutions of $A_2 and B2_2. Section 7 explores the performance of simple strategies, especially for BmB_m. Section 8 presents numerical evaluation of optimal and suboptimal stopping strategies.

The planar Poisson process framework

Scores, ranks and losses

Let Π\Pi be a unit rate PPP on [0,1]×[0,∞)[0,1]\times[0,\infty). We view Π\Pi as a random scatter of points, where an atom (t,x)∈Π(t,x)\in\Pi is interpreted as a score xx observed at time tt, smaller scores being preferred. The natural filtration is generated by the restrictions of Π\Pi to [0,t]×[0,∞)[0,t]\times[0,\infty), t∈[0,1]t\in[0,1]. An admissible selection strategy (sometimes referred to as rule) is a stopping time τ\tau with respect to this filtration, which is either the arrival time of an atom or τ=1\tau=1 (no selection); the latter happens with positive probability for the optimal strategies. See [23] for measure-theoretic aspects of optimal stopping for planar point processes, with objectives depending on (t,x)(t,x) alone.

For an atom (t,x)(t,x) we define its final rank rr to be one plus the number of atoms of Π\Pi with scores smaller than xx, and its initial rank ii to be one plus the number of earlier atoms with scores smaller than xx. When the atom arrives, xx and ii are observed, and the conditional distribution of r−ir-i is Poisson(ξ\xi), with the mean equal to the area of the south-east window (t,1]×(0,x)(t,1]\times(0,x), where

ξ:=txˉ,tˉ:=1−t.\xi:= t\bar{x}, \qquad\bar{t} := 1-t.

We call ξ\xi the box coordinate of the atom.

For m=1,2,…m=1,2,\ldots we consider two types of the adapted loss from stopping at an atom with initial rank ii and box coordinate ξ\xi, given the observed information:

Am:Q(ξ,i)=min⁡(i,m+1)+ξ,(6)\begin{aligned} A_m:\qquad&Q(\xi,i)=\min(i,m+1)+\xi, \tag*{(6)} \end{aligned}
Bm:Q(ξ,i)=1−∑j=0m−ie−ξξjj!,(7)\begin{aligned} B_m:\qquad&Q(\xi,i)=1-\sum_{j=0}^{m-i}\frac{e^{-\xi}\xi^j}{j!}, \tag*{(7)} \end{aligned}

where the sum in (7) is empty for i>mi>m. The PPP problems with these loss structures are infinite-arrivals counterparts of the full-information problems (4), (5) from the Introduction. In both cases Q(ξ,i)Q(\xi,i) is nondecreasing in ξ\xi and in ii. For the event {τ=1}\{\tau=1\} we assume the loss

Q∞=m+1 in Am,Q∞=1 in Bm.Q_\infty=m+1\text{ in }A_m,\qquad Q_\infty=1\text{ in }B_m.

This convention is the limit form of the terminal loss in the finite-nn problems (4), (5), where the observer must stop at stage nn: by exchangeability, the last score has rank of order nn with high probability, and the loss for being forced to accept it tends to Q∞Q_\infty. Clearly, it can only be optimal to stop at observations with initial rank i≤mi\le m, since otherwise the loss is at least Q∞Q_\infty; this may lead to missing all opportunities and ending at t=1t=1. The minimal achievable expected losses are denoted ama_m and bmb_m for problems AmA_m and BmB_m, respectively. For BmB_m the loss is the conditional probability of failure, which is the choice of an atom of final rank above mm; the complementary probability 1−bm1-b_m is the probability of successful choice of one of the mm best scores.

Here is the link to the discrete-time fixed-nn problems. Split the time range [0,1][0,1] in nn equal slots ((k−1)/n,k/n]((k-1)/n,k/n], k∈[n]k\in[n], and suppose that the arrival times of the nn slot-wise minima M1,…,MnM_1,\ldots,M_n belong to the prior information of the observer. Then the selection is reduced to an nn-step problem for M1,…,MnM_1,\ldots,M_n, which are independent and share the same exponential distribution. With the further advantage that only unobserved minima contribute to the final rank of the selected observation, the problem becomes equivalent to An,mA_{n,m}, respectively Bn,mB_{n,m}. This shows that the Poisson values am,bma_m,b_m are upper bounds for the values of the discrete problems. In problem [5] the values increase with nn to bm\mathbf{b}_m [14]. For problem [4] the same holds, but requires a separate proof, since the loss is not a function of the final rank.

Proposition 2.1. Let an,ma_{n,m} be the value of problem [4]. For every m≥1m \ge1 the sequence an,ma_{n,m}, n≥mn \ge m, is nondecreasing and converges to am\mathbf{a}_m.

Proof. The loss for selecting a score is min⁡(i,m+1)+N\min(i,m+1)+N, where ii is its initial rank and NN is the number of later scores below it. It depends on the scores only through their order, hence the common continuous distribution of the scores does not matter for the stopping problem.

Monotonicity in nn follows by a familiar coupling argument. Take n+1n+1 independent uniform scores, n≥mn \ge m, and let the observer be told in advance the value uu of the largest one; the advantage can only lower the minimal expected loss. If uu is the kk-th score, selecting it costs min⁡(k,m+1)+(n+1−k)≥m+1\min(k,m+1)+(n+1-k) \ge m+1, while the last of the other scores costs at most m+1m+1, so uu may be declined. Discarding uu does not impact ranking of the other scores, and given uu the other scores are independent and uniform on [0,u][0,u]. Thus the problem is reduced to nn scores, and an,m≤an+1,ma_{n,m} \le a_{n+1,m}.

Upper bound follows by the slot argument above: an,m≤ama_{n,m} \le\mathbf{a}_m. The rest of the proof deals with a lower bound.

References

  1. [1]F. T. Bruss, What is known about Robbins’ problem? J. Appl. Probab. 42 (2005), 108–120.DOI
  2. [2]F. T. Bruss and T. S. Ferguson, Minimizing the expected rank with full information, J. Appl. Probab. 30 (1993), 616–626.DOI
  3. [3]F. T. Bruss and T. S. Ferguson, Half-prophets and Robbins’ problem of minimizing the expected rank, in: Athens Conference on Applied Probability and Time Series, Lecture Notes in Statistics 114, Springer, 1996, 1–17.DOI
  4. [4]Y. S. Chow, S. Moriguti, H. Robbins and S. M. Samuels, Optimal selection based on relative rank (the “secretary problem”), Israel J. Math. 2 (1964), 81–90.DOI
  5. [5]Y. S. Chow, H. Robbins and D. Siegmund, Great Expectations: The Theory of Optimal Stopping, Houghton Mifflin, 1971.
  6. [6]R. Dendievel and Y. Swan, One step further: an explicit solution to Robbins’ problem when n = 4, Mathematica Applicanda 44 (2016), 135–148.DOI
  7. [8]A. Q. Frank and S. M. Samuels, On an optimal stopping problem of Gusein-Zade, Stoch. Process. Appl. 10 (1980), 299–311.
  8. [9]J. Gianini and S. M. Samuels, The infinite secretary problem, Ann. Probab. 4 (1976), 418–432.DOI
  9. [10]J. Gilbert and F. Mosteller, Recognizing the maximum of a sequence, J. Amer. Statist. Assoc. 61 (1966), 35–73.
  10. [11]A. Gnedin, Multicriteria extensions of the best choice problem: sequential selection without linear order, in: Strategies for Sequential Search and Selection in Real Time, Contemporary Mathematics 125 (1992), 152–172.DOI
  11. [12]A. Gnedin, On the full-information best-choice problem, J. Appl. Probab. 33 (1996), 678–687.DOI
  12. [13]A. Gnedin, Best choice from the planar Poisson process, Stoch. Process. Appl. 111 (2004), 317–354.DOI
  13. [14]A. Gnedin, Optimal stopping with rank-dependent loss, J. Appl. Probab. 44 (2007), 996–1011.arxiv.org/abs/0705.2976
  14. [15]A. Gnedin, Corners and records of the Poisson process in quadrant, Electron. Commun. Probab. 13 (2008), 187–193.arxiv.org/abs/0709.1285
  15. [16]A. Gnedin, Optimal stopping for the uniform distribution, arXiv:2601.04371 (2026).arxiv.org/abs/2601.04371
  16. [17]A. Gnedin and M. C. S. Carreira, The memoryless best-choice problem, arXiv:2607.16145 (2026).arxiv.org/abs/2607.16145
  17. [18]A. Gnedin, P. Koziel and M. Sulkowska, Running minimum in the best-choice problem, Extremes 26 (2023), 157–182.arxiv.org/abs/2110.05338
  18. [19]A. Goldenshluger and Y. Malinovsky, On optimal stopping problems with full information and rank-dependent reward, preprint (2026).arxiv.org/abs/2610.33701
  19. [20]S. M. Gusein-Zade, The problem of choice and the optimal stopping rule for a sequence of independent trials, Theory Probab. Appl. 11 (1966), 472–476.
  20. [21]A. G. Mucci, Differential equations and optimal choice problems, Ann. Statist. 1 (1973), 104–113.DOI
  21. [23]L. Rüschendorf, Approximative solutions of optimal stopping and selection problems, Mathematica Applicanda 44 (2016), 17–44.DOI
  22. [24]S. M. Samuels, Secretary problems, in Handbook of Sequential Analysis, Dekker, 1991, 381–405.

Paper details

vlnc:W_b29x4ccz
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents