Bayesian Optimal Stopping with Maximum Value Knowledge

Abstract

We consider an optimal stopping problem with n correlated offers where the goal is to design a (randomised) stopping strategy that maximises the expected value of the offer at which we stop. Instead of assuming to know the complete correlation structure, which is unrealistic in practice, we only assume to have knowledge of the distribution of the maximum value Xmax  of the sequence, and want to analyse the worst-case correlation structure whose maximum follows this distribution. This can be seen as a trade-off between the setting in which no distributional information is known, and the Bayesian setting in which the (possibly correlated) distributions of all the individual offers are known. As our first main result we show that a deterministic threshold strategy using the monopoly price of the distribution of the maximum value is asymptotically optimal assuming that the expectation of the maximum value grows sublinearly in n. In our second main result, we further tighten this bound by deriving a tight quadratic convergence guarantee for sufficiently smooth distributions of the maximum value. Our results also give rise to a more fine-grained picture regarding prophet inequalities with correlated values, for which distribution-free bounds only yield a performance guarantee of the order 1/n.