U-Calibration: Forecasting for an Unknown Agent
Robert Kleinberg Renato Paes Leme Jon Schneider Yifeng Teng
We consider the problem of evaluating forecasts of binary events whose
predictions are consumed by rational agents who take an action in response to a
prediction, but whose utility is unknown to the forecaster. We show that
optimizing forecasts for a single scoring rule (e.g., the Brier score) cannot
guarantee low regret for all possible agents. In contrast, forecasts that are
well-calibrated guarantee that all agents incur sublinear regret. However,
calibration is not a necessary criterion here (it is possible for miscalibrated
forecasts to provide good regret guarantees for all possible agents), and
calibrated forecasting procedures have provably worse convergence rates than
forecasting procedures targeting a single scoring rule.
  Motivated by this, we present a new metric for evaluating forecasts that we
call U-calibration, equal to the maximal regret of the sequence of forecasts
when evaluated under any bounded scoring rule. We show that sublinear
U-calibration error is a necessary and sufficient condition for all agents to
achieve sublinear regret guarantees. We additionally demonstrate how to compute
the U-calibration error efficiently and provide an online algorithm that
achieves $O(\sqrt{T})$ U-calibration error (on par with optimal rates for
optimizing for a single scoring rule, and bypassing lower bounds for the
traditionally calibrated learning procedures). Finally, we discuss
generalizations to the multiclass prediction setting.