High-Dimensional Prediction for Sequential Decision Making
Georgy Noarov, Ramya Ramalingam, Aaron Roth, Stephan Xie
[arXiv]
We study the problem of making predictions of an adversarially chosen high-dimensional state that are 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 an appropriate set of conditioning events.
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 will have 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 such as 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 prediction sets for online adversarial multiclass and multilabel classification. We show how to produce class scores that have \emph{transparent coverage guarantees}: they can be used to produce prediction sets covering the true labels at the same rate as they would had our scores been the true conditional class probabilities. We then show that these transparent coverage guarantees imply strong online adversarial conditional validity guarantees (including set-size conditional coverage and multigroup-fair coverage) for (potentially multiple) downstream prediction set algorithms relying on our class scores. Moreover, we show how to guarantee that our class scores have improved L2 loss (or cross-entropy loss, or more generally any Bregman loss) compared to any collection of benchmark models. This can be viewed as a high-dimensional, real-valued version of omniprediction. Compared to conformal prediction techniques, this both gives increased flexibility and eliminates the need to choose a non-conformity score.