Robust Sequential Search

Résumé

We study robust decision making in sequential search. The searcher is unaware of the distribution of values of unexplored alternatives. Her decision rule should be dynamically robust, in the sense that it should perform close to Bayesian-optimal under any prior, at each point of time, and after each history of observations. The standard rules used in the search literature are based on cutoff strategies and are not robust. We derive an optimal robust decision rule. It requires randomized behavior and can be approximated by a rule with a linear stopping probability. (joint work with Karl Schlag)