High Dimensional Unbiased Estimation for Sequential Decision Making

We study the problem of making predictions of an adversarially chosen high dimensional state that are \emph{unbiased} subject to an arbitrary collection of conditioning events, with the goal of tailoring these events to downstream decision makers. We give efficient algorithms for solving this problem, as well as a number of applications that stem from choosing the set of conditioning events appropriately. For example, we can efficiently produce predictions targeted at any polynomial number of decision makers, such that if they best respond to our predictions, each of them has diminishing swap regret at the optimal rate. We then generalize this to the online combinatorial optimization problem, where the decision makers have large action spaces corresponding to structured subsets of a set of base actions: We give the first algorithms that can guarantee (to any polynomial number of decision makers) regret to the best fixed action, not just overall, but on any polynomial number of subsequences that can depend on the actions chosen as well as any external context. We show how playing in an extensive form game can be cast into this framework, and use these results to give efficient algorithms for obtaining subsequence regret in extensive form games, which gives a new family of efficiently obtainable regret guarantees that captures and generalizes previously studied notions like regret to informed causal deviations, and is generally incomparable to other known families of efficiently obtainable guarantees.We then turn to uncertainty quantification in machine learning, and consider the problem of producing \emph{prediction sets} for multiclass and multilabel classification problems. We show how to produce class scores that have \emph{transparent coverage guarantees} --- they can be used to produce prediction sets that cover the true labels at the rate that they would have had the scores been true conditional probabilities. Moreover, we show how to do this such that the scores have improved Brier score (or cross-entropy loss) compared to any collection of benchmark models. Compared to conformal prediction techniques, this both gives increased flexibility and eliminates the need to choose a non-conformity score.