PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithms for Robbins' Problem using Markov Decision Processes

Léonard Brice, F. Thomas Bruss, Anirban Majumdar, Jean-François Raskin

arXiv:2608.27419v1cs.GTmath.PR

TL;DR

Robbins’ problem seeks a no-recall sequential strategy minimizing the expected final rank of one selected candidate, but optimal decisions depend on the entire observed history. The paper models the problem as an infinite MDP and develops finite-state abstractions for computation. These abstractions produce improved approximations for n=5 through n=100 and practical strategies, while larger abstractions face state-space limitations.

  • Problem

    Robbins’ problem asks how to minimize the expected final rank when candidates are observed sequentially and optimal decisions require the complete history.

  • Method

    The paper models Robbins’ problem as an infinite MDP and develops finite-state abstractions solved by backward induction.

  • Results

    For every n from 5 through 100, the abstractions yield approximate values better than the best previously known upper bounds.

  • Takeaways & Limitations

    The abstractions provide implementable strategies whose performance surpasses previously known memoryless strategies.

  • Takeaways & Limitations

    The k-best-draw abstraction can become infeasible because its state space grows as O(n · d^k+1), while larger n requires reasonably large d for precision.

Abstract

from arXiv · show

In this paper, we consider Robbins' problem, which is a full information variant of the well-known secretary selection problem. In this version of the problem, the goal is to minimize the expected rank of the selected candidate among $n$ that are interviewed sequentially, and a decision to select or not the $m^{th}$ candidate needs to be taken right after the interview (so without seeing the last $n-m$ candidates and without recall). We first show how to model instances of Robbins' problem as infinite Markov Decision Processes (MDPs). Then we propose several finite-state abstractions of these MDPs that allow us to approximate the value of the problem for fixed $n$. While it is known that the full memory of past candidates' values is necessary for optimal expected rank minimization, making the analysis of the problem challenging, we highlight simple memory structures that are sufficient for obtaining near-optimal selection strategies. Additionally, we provide approximate values for Robbins' problem for numbers of candidates $n$ up to 100 for which no good approximations were previously known (the exact value is only known for instances where $n \leq 4$ and numerical approximations were for small values of $n$ not exceeding one digit), for all $n : 5 \leq n \leq 100$, we give better approximation than what was previously known.

1 Introduction

Robbins’ problem asks for a sequential, no-recall strategy that minimizes the selected candidate’s expected final rank. The paper addresses the problem’s full history dependence with finite MDP abstractions that yield improved approximations and practical strategies.

  • Robbins’ problem requires immediate accept-or-reject decisions and obliges selecting the final candidate if all earlier candidates are rejected.
  • The objective is to minimize the expected rank of the selected candidate among all n candidates, including the unresolved limiting value as n grows.
  • Memoryless threshold strategies use only the current value and round-dependent thresholds, but they cannot be optimal because optimal strategies require the full observed history.
  • The optimal strategy depends on the complete cloud of previously observed values, so no sufficient statistic smaller than the full history is known for optimal decisions.
  • The truncation method is computationally impractical because its storage requirements grow exponentially with both n and the truncation level.

2 Preliminaries

The preliminaries define Markov chains and Markov decision processes through states, actions, transition probabilities, and losses. Strategies resolve MDP choices and induce Markov chains whose expected loss is evaluated over paths to final states.

  • A Markov chain consists of states, an initial state, a transition mapping, and a partial loss mapping.
  • Final states have defined losses and are absorbing, so execution remains there after reaching a terminal outcome.
  • Paths are state sequences beginning at the initial state, following positive-probability transitions, and ending in a final state.
  • An MDP adds a finite action set and action-dependent transitions and losses to the state space and initial state.
  • An MDP strategy maps finite paths to actions and induces a Markov chain by unfolding the process under those choices.
  • The expected loss is the expectation of the loss over executions reaching final states, evaluated using the induced transition probabilities.

3 An MDP abstraction for full d-discrete history

The section discretizes Robbins’ infinite-history MDP by partitioning [0, 1) into d intervals and retaining interval counts, yielding a finite MDP whose value upper-bounds and converges to the exact value.

  • Exact Robbins’ problem MDP: The exact Robbins’ problem is modeled as an infinite MDP whose states are draw histories and whose actions are STOP and ¬STOP.Stopping or exhausting the draws returns the expected rank of the selected draw as loss.
  • Discrete abstraction: The finite abstraction discretizes draws into d intervals and represents each history by interval counts, the latest interval, and remaining draws.The discretized state includes a count vector and the interval containing the most recent draw.
  • Discrete abstraction: The loss for stopping combines draws in lower intervals, the average contribution of draws in the latest interval, and expected smaller future draws.This decomposition explains how the discrete state determines the stopping loss.
  • Approximation guarantees: Theorem 1 guarantees that the minimum expected loss in the discrete MDP is at least vn for every n and d.Thus, the abstraction provides an upper bound on the exact optimal value.
  • Approximation guarantees: For every fixed n, the discrete optimum converges to vn as d →∞ because conflict-free histories approach probability one.On conflict-free branches, the exact and discretized processes assign matching or arbitrarily close values.

4 Remembering the k best candidates only

The second abstraction remembers only the intervals of the k best previous draws, reducing the state space while preserving correctness and experimentally producing values close to the full-history abstraction.

  • State representation: The abstraction retains only interval counts for the k best previous draws instead of the complete discretized history.This produces an MDP whose state-space size is bounded by O(n · d^(k+1)).
  • State representation: When fewer than k draws have been observed, new interval counts are stored; afterward, the newest draw replaces the worst retained draw.The transition rules implement this bounded-memory update.
  • Correctness: The k-best abstraction is exact when k = n, since its optimal loss equals that of the full-history MDP.Lemma 2 establishes equality between Mn,d and Mn,d,n.
  • Loss function: The stopping loss adds terms accounting for forgotten histories that may share the latest interval or lie between retained intervals.These corrections compensate for information discarded by limiting memory.
  • Correctness: The stopping-loss function is correct: conditional expected rank equals Loss(s, STOP) for fixed n, d, and k.This connects the compressed state representation to the original Robbins’ loss.

5 Remembering the k best candidates in first l intervals

The third abstraction discretizes only an initial range [0, l) finely and groups larger candidates together, substantially reducing states while retaining the k-best memory structure.

  • Computational scope: The uniform k-best abstraction grows as O(n · d^(k+1)), making large d difficult, whereas the non-uniform scheme reduces the state count using l.The paper reports that relatively smaller l can suffice for a reasonable approximation as n grows.
  • Non-uniform partition: The (d, k, l)-abstraction uses intervals of size 1/d in [0, l) and one aggregate interval for candidates in [l, 1).The non-uniform partition is tailored to the likely quality of the k best remembered draws.
  • Non-uniform partition: The resulting MDP has state-space size O(n · l^(k+1)), smaller than the uniform k-best abstraction.Only the finely partitioned region contributes multiple retained interval categories.
  • MDP construction: The transition system stores the k best draws among the fine intervals and the aggregate interval, replacing the worst retained draw once memory is full.The state and transition definitions distinguish the pre-full-memory and full-memory cases.
  • Correctness: The stopping-loss function remains correct for the (d, k, l)-abstraction, with conditional expected rank equal to Loss(s, STOP).Lemma 5 extends the correctness result to the non-uniform partition.

6 Experimental results

The experiments evaluate finite-state abstractions against prior memoryless strategies, showing that retaining a few best draws yields strong approximations across larger n while computational size remains substantial.

  • 6.1 Experiments on d-abstractions of Section 3: 1.391635988 and 1.391593893 approximate the exact v3 = 1.3915··· using d = 500 and d = 1000.For n = 4, the corresponding values are v4,500 = 1.493418067584 and v4,1000 = 1.493356615167, close to v4 = 1.4932···.
  • 6.1 Experiments on d-abstractions of Section 3: The first d-abstraction becomes almost infeasible for n ≥6 because its MDP size grows roughly as O(n · d^n).The paper motivates the (d, k)-abstraction as more tractable for larger n.
  • 6.2 Experiments on (d, k)-abstractions of Section 4: Remembering k = 2 or 3 best draws produces values close to optimal expected ranks for larger n.The experiments compare these abstractions with the memoryless strategy using d = 100.
  • 6.2 Experiments on (d, k)-abstractions of Section 4: For every n ≤30 and k ∈{1, 2, 3}, d = 100 yields a better value than the memoryless strategy of.Figure 2 compares minimal expected ranks for the two strategy classes.
  • 6.2 Experiments on (d, k)-abstractions of Section 4: For all n ≤100, suitable d and relatively small k ∈{2, 3} achieve better values than.For n = 500, d = 1000 and k = 2 gives a value close to, while larger abstractions can require very large MDPs and long runtimes.
  • 6.3 Experiments on (d, k, l)-abstractions of Section 5: For n = 500 and k = 2, v500,2000,2,300 = 2.32791 takes about 2 × 10^3 seconds, versus 1.3 × 10^5 seconds for v500,1000,2 = 2.32697.The restricted abstraction is reported as a good over-approximation while requiring much less computation.

7 Conclusion

The paper models Robbins’ problem with MDP abstractions to compute approximate values and finds that retaining only a few best past draws can closely approximate full-history strategies.

  • 7 Conclusion: The abstractions compute approximate Robbins’ problem values for every n from 5 through 100, improving on the best previously known upper bounds.The paper presents these as instances for which no good approximations were previously known.
  • 7 Conclusion: Remembering the two or three best previous draws while forgetting less favourable ones produces almost-optimal strategies.This concentrates memory on the most competitive past observations rather than retaining the entire history.
  • 7 Conclusion: Future work includes numerically computing lower bounds with MDPs and investigating whether discretization can approximate a related differential equation.The paper primarily focuses on methods for obtaining upper bounds.

A.1 Proof of Lemma 3

Lemma 3 establishes that the MDP’s STOP loss equals the conditional expected final rank under d-discretized history and the current observation interval.

  • A.1 Proof of Lemma 3: For fixed n, d, and k, Loss(s, STOP) equals E(Ln−r | (#»y, m)) for the discretized state s = (r, m, #»y).Here #»y records the d-discretization of observations seen so far, while m identifies the interval containing the current observation.
  • A.1 Proof of Lemma 3: When the current interval index m is below the largest occupied history index, the discretized history is perfect and the proof follows Lemma 1.The same argument applies when fewer than k observations have been seen.
  • A.1 Proof of Lemma 3: When more than k observations have been seen, the cases m = maxi and m > maxi may forget some d-discretized histories.The proof handles these cases through conditional probabilities involving earlier observations and the current interval.
  • A.1 Proof of Lemma 3: The proof evaluates the additional expected-rank contributions using conditional probabilities for earlier draws relative to the current discretized interval.These calculations include the probabilities stated in equations (14) and the subsequent evaluation.

A.2 Experimental Results

The experiments report values across n = 1 to 100 using fixed d and k settings, with separate tables covering n ≤50 and 51 ≤n ≤100.

  • Experimental setup: Experimental values are reported for n = 1 to 100 with d = 500, 1000 and k = 2.The tables also include the memoryless strategy of with parameter c = 1.9469.
  • Results by candidate count: Table 2 covers experimental results for 1 ≤n ≤50.
  • Results by candidate count: Table 3 covers experimental results for 51 ≤n ≤100.
Loading 2608.27419v1…