  The secretary problem is probably the purest model of decision making under
uncertainty. In this paper we ask which advice can we give the algorithm to
improve its success probability?
  We propose a general model that unifies a broad range of problems: from the
classic secretary problem with no advice, to the variant where the quality of a
secretary is drawn from a known distribution and the algorithm learns each
candidate's quality on arrival, to more modern versions of advice in the form
of samples, to an ML-inspired model where a classifier gives us noisy signal
about whether or not the current secretary is the best on the market.
  Our main technique is a factor revealing LP that captures all of the problems
above. We use this LP formulation to gain structural insight into the optimal
policy. Using tools from linear programming, we present a tight analysis of
optimal algorithms for secretaries with samples, optimal algorithms when
secretaries' qualities are drawn from a known distribution, and a new noisy
binary advice model.
