Uniformly bounded regret in the multisecretary problem

DOI10.1287/STSY.2018.0028zbMATH Open1446.60033arXiv1710.07719OpenAlexW2766449057WikidataQ127302489 ScholiaQ127302489MaRDI QIDQ5113899FDOQ5113899

Authors: Alessandro Arlotto, Itai Gurvich 

Publication date: 18 June 2020

Published in: Stochastic Systems (Search for Journal in Brave)

Abstract: In the secretary problem of Cayley (1875) and Moser (1956), $n$ non-negative, independent, random variables with common distribution are sequentially presented to a decision maker who decides when to stop and collect the most recent realization. The goal is to maximize the expected value of the collected element. In the $k$-choice variant, the decision maker is allowed to make $kleqn$ selections to maximize the expected total value of the selected elements. Assuming that the values are drawn from a known distribution with finite support, we prove that the best regret---the expected gap between the optimal online policy and its offline counterpart in which all $n$ values are made visible at time $0$---is uniformly bounded in the the number of candidates $n$ and the budget $k$. Our proof is constructive: we develop an adaptive Budget-Ratio policy that achieves this performance. The policy selects or skips values depending on where the ratio of the residual budget to the remaining time stands relative to multiple thresholds that correspond to middle points of the distribution. We also prove that being adaptive is crucial: in general, the minimal regret among non-adaptive policies grows like the square root of $n$. The difference is the value of adaptiveness.

Full work available at URL: https://arxiv.org/abs/1710.07719

Recommendations

• scientific article; zbMATH DE number 3947461
• The secretary problem with distributions
• A new secretary problem with rank-based selection and cardinal payoffs
• Prophet secretary
• New results for the \(k\)-secretary problem

zbMATH Keywords

regretadaptive online policymultisecretary problem

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Stopping times; optimal stopping problems; gambling theory (60G40)

Cites Work

• Concentration inequalities. A nonasymptotic theory of independence
• Title not available (Why is that?)
• Stochastic optimal control. The discrete time case
• Fundamentals of Stein's method
• The dynamic and stochastic knapsack problem
• A Knapsack Secretary Problem with Applications
• A multiple-choice secretary algorithm with applications to online auctions
• The Secretary Problem and Its Extensions: A Review
• Who solved the secretary problem
• The theory and practice of revenue management
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• Dynamic Programming and Decision Theory
• Stability of queueing networks
• Title not available (Why is that?)
• Optimal selection based on relative rank (the 'Secretary Problem')
• Title not available (Why is that?)

Cited In (7)

• Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards
• Simple and fast algorithm for binary integer and online linear programming
• A unified approach for solving sequential selection problems
• Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds
• Online allocation and pricing: constant regret via Bellman inequalities
• Constant Regret Resolving Heuristics for Price-Based Revenue Management
• Learning in repeated auctions

This page was built for publication: Uniformly bounded regret in the multisecretary problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113899)