Optimal Selection from a Random Sequence with Learning of the Underlying Distribution

Abstract

Consideration is given to an extension of the so-called secretary problem in which each alternative has an observable value drawn from a distribution unknown a priori. A uniform distribution is considered here, because this gives analytical solutions which are easily compared with previous work. It is shown that when maximizing the probability of selecting the best candidate, learning does not contribute to the solution. When maximizing expected value, learning does play a role, giving a solution intermediate between that based on ranks and that based on known distributions.

Key Words:

• Secretary problem
• Bayesian inference
• Uniform distribution