High-Dimensional Prediction for Sequential Decision Making

We thank the reviewer for the insightful reading and positive assessment of our paper, and for the feedback! We will make sure to address the notational comments in our revision.

We thank the reviewer for the careful reading and positive assessment of our paper, and appreciate the insightful comments! We agree with, and will make sure to address, your comments in the revision. Among other things, we completely agree that starting with a single agent case would further enhance the exposition and readability; in fact, the only reason that prevented us from doing so was the page limit on the submission. Also, having a condensed reference paragraph/table for prior state of the art in the directions of our applications will help further clarify the landscape for the readers. Furthermore, we completely agree that first defining unbiased prediction as requiring sublinear (o(T)) bias, and only then instantiating it with the concrete regret bounds, is an excellent expository idea --- and in fact, we had our presentation laid out just like that in the pre-submission manuscript, and had to cut it down to the direct small-loss definition purely because of the page limit.

We now give a clarification regarding your question about the utility of sharp “small loss”, group-specific, rates. In the multi-calibration example, please note that for each group, as stated on line 266, the bound is O(T/m + \sum_{i \in [m]} \sqrt{\text{# rounds on which bucket i got played}}). As mentioned further in the argument, by concavity of the sqrt function, we can conclude that the worst-case split of the T rounds into the m buckets is when each bucket gets played equally often, i.e. the worst case bound is $O(T/m + m \sqrt{T/m}) = O(T/m + \sqrt{m T})$, which when choosing the optimal m (that equalizes both terms), results in $m \sim T^{1/3}$ and thus in the overall per-group bound of $O(T^{2/3})$.

Meanwhile, suppose our framework only gave $\sqrt{T}$ bounds for each group rather than \sqrt{E[\text{# rounds on which each group appeared}]}. Then, the calibration error bound for each group would simply be $O(T/m + \sum_{i \in [m]} \sqrt{T}) = O(T/m + m \sqrt{T})$, which due to an extra $\sqrt{m}$ factor in the right-hand term leads to the choice of $m \sim T^{1/4}$ and hence implies a worse $O(T^{3/4})$ error bound. In this way, our ability to use our framework without any modifications to get the (currently best-known) rate very concretely hinges on the “small-loss” per-group guarantees. And indeed, as you correctly assumed, the prior method of Gupta et al (2021) didn’t achieve such small-loss bounds and could thus only achieve the 3/4 exponent.

We thank the reviewer for the careful reading and positive assessment of our paper, and for the very insightful feedback! Indeed, as pointed out in your review, our framework is quite general, and discussing the costs of this generality is very pertinent and we will do so in the revision. To address specific points you have raised:

1. Regarding how to specify, and work with, the event collection. Indeed, our framework allows you to flexibly add new events to the event collection at any time point, without advance notice to the algorithm, as well as — conversely — terminate events that are not useful anymore. All this while barely incurring extra cost (cf. log |E| in the bias bound) for doing so. This is enabled by the fact that our algorithm at each round only works with events that are currently active and doesn’t require knowledge about other events, whether or not they were active before or will be active later. In terms of data-driven approaches, indeed in the presence of high-dimensional covariates one can for instance take a dimensionality-reducing bounded representation map, which, when applied to the covariates, results in much smaller-length vectors e.g. in the [0, 1]^d-hypercube, and define events e.g. as the outputs (or a more complex function) of this representation. E.g. the case of linear, bounded, representations give rise to the “multiaccurate” or “multigroup” setting in the literature on algorithmic fairness, and the groups there can be defined either normatively as e.g. demographic groups (age/income/etc), or — using a data-driven approach as you suggest — as adaptively identified high-bias regions in the data that would make the most sense to debias your predictions on.

2. Regarding avoiding explicit computation of best-response events for all agents: This is a great question, and answering it in specific settings is possible and has led to novel follow-up results, in particular addressing the desideratum you describe where we may wish for no swap regret for all downstream agents with utility functions in a certain class. For instance, the follow-up work of Roth and Shi (2024) give a simple method for doing this using our algorithm. Their observation is that for any (linear) utility function, best response regions are convex --- so it suffices to use our algorithm to produce unbiased predictions for all regions defined by the convex hull of points in our prediction space. Each of these defines an event that can be plugged into our algorithm. For one dimensional outcome spaces, these are simply intervals. This gives us a finite collection of events that includes the best response events for all possible downstream agents, even though we don’t have knowledge of their utility functions. The upshot of the described construction of Roth and Shi is that relative to implementing full calibration (which you point out in your review as another agent-agnostic approach), you get better regret rates — O(sqrt(T)) vs. O(T^2/3) in one dimension, and much better improvements in higher dimensions, since bounds for full online calibration scale exponentially with the dimension. Again, their bounds follow from simply instantiating our algorithm with the right choice of events. We look forward to further applications of our framework in this vein.

3. Regarding the notion of “sufficient statistics”: We have referred to the state vectors’ entries as “sufficient statistics” in the intro, to informally convey their meaning. Rigorously, as you indeed say, we define them as the (finite as we require) collection of quantities that the agent’s utility mapping is a function of, for every action. Whether or not they represent some statistics of some implicit/underlying distributions on which the agents’ utilities depend, does not affect our framework. In this work, we focus on establishing the foundational case where the utility is an affine function of these statistics. However, this linearity should not be viewed as some very restrictive assumption that would preclude the use of the framework for nonlinear utilities, but rather as the key tool for nonlinear extensions: this is similar to how linear optimization serves as the core of most convex/nonconvex optimization methods. To be more specific, lots of very important classes of (utility) functions have small functional bases (needed to keep our event collection small), and linearize over the states once an appropriate representation map is applied to the state vectors. E.g. for polynomials of fixed degree, for the states we would consider the moments up to the d-th, and this can be taken far beyond polynomial utilities, too, provided some other smoothness guarantees on the function class are given. For instance a very recent preprint (https://arxiv.org/abs/2502.12564) looks at such extensions and once again directly applies our framework and algorithm on those.

We thank the reviewer for the careful reading and positive assessment of our paper, and appreciate the detailed comments. We will incorporate, in the updated version of the paper, the modifications proposed in Other Comments and Suggestions.

As for the relevance of the preprint to future work that followed up on it, such as the cited references in the submission: Indeed, our proposed framework and the algorithm we develop within it is not obsolete and remains state of the art and continues to be used. Subsequent work has not generalized or subsumed our general framework. Rather, follow-up papers have used our framework and algorithm and its generic guarantees as a technical tool towards achieving goals in concrete settings (such as high-dimensional contract design, or no regret guarantees for infinite families of downstream agents, etc) — which is the type of follow-up work that we have envisioned for our paper from the beginning.

To summarize, our framework remains state-of-the-art, and subsequent work has used it for various interesting applications.

Please feel free to look at the responses to other reviewers for some brief points on a couple of follow-ups and on ways in which these follow-ups use our framework.