Evaluating Distributional Predictions of Search Time: Put Up or Shut Up Games (Extended Abstract)


  • Sean Mariasin Ben-Gurion University of the Negev
  • Andrew Coles King's College London
  • Erez Karpas Technion
  • Wheeler Ruml University of New Hampshire
  • Solomon Eyal Shimony Ben-Gurion University of the Negev
  • Shahaf Shperberg Ben-Gurion University of the Negev




Metareasoning can be a helpful technique for controlling search in situations where computation time is an important resource, such as real-time planning and search, algorithm portfolios, and concurrent planning and execution. Metareasoning often involves an estimate of the remaining search time of a running algorithm, and several ways to compute such estimates have been presented in the literature. In this paper, we argue that many applications actually require a full estimated probability distribution over the remaining time, rather than just a point estimate of expected search time. We study several methods for estimating such distributions, including some novel adaptations of existing schemes. To properly evaluate the estimates, we introduce `put-up or shut-up games', which probe the distributional estimates without requiring infeasible computation. Our experimental evaluation reveals that estimates that are more accurate in expected value do not necessarily deliver better distributions, yielding worse scores in the game.