Algorithms for Robbins' Problem using Markov Decision Processes
2026-08-27 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study Robbins' problem, a version of the secretary problem where the goal is to pick a candidate with the lowest possible rank without looking back or seeing future candidates. They represent the problem using infinite Markov Decision Processes and create simpler models to approximate solutions. Although perfect memory of past candidates is usually needed, the authors find simpler memory methods that work nearly as well. They provide improved approximations for up to 100 candidates, filling a gap where only small cases were previously known.
Robbins' problemsecretary problemexpected rank minimizationMarkov Decision Process (MDP)optimal stoppingfinite-state abstractionapproximation algorithmssequential decision makingmemory structure
Authors
Léonard Brice, F. Thomas Bruss, Anirban Majumdar, Jean-François Raskin
Abstract
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.