High-Dimensional Prediction for Sequential Decision Making
Authors: Georgy Noarov
Ramya Ramalingam
Aaron Roth
Stephan Xie
Venue: ICML 2025 oral (2025)
Keywords: online decision making
combinatorial optimization
multicalibration
calibration
swap regret
no-regret
conditional guarantees
Primary area: theory->online_learning_and_bandits
TL;DR: A general framework for online adversarial vector-valued prediction with decision making applications

Abstract: We give an efficient algorithm for producing multi-dimensional forecasts in an online adversarial environment that have low bias subject to any polynomial number of conditioning events, that can depend both on external context and on our predictions themselves. We demonstrate the use of this algorithm with several applications. We show how to make predictions that can be transparently consumed by any polynomial number of downstream decision makers with different utility functions, guaranteeing them diminishing swap regret at optimal rates. We also give the first efficient algorithms for guaranteeing diminishing conditional regret in online combinatorial optimization problems for an arbitrary polynomial number of conditioning events --- i.e. on an arbitrary number of intersecting subsequences determined both by context and our own predictions. Finally, we give the first efficient algorithm for online multicalibration with $O(T^{2/3})$ rates in the ECE metric.

High-Dimensional Prediction for Sequential Decision Making
Georgy Noarov! Ramya Ramalingam
Aaron Roth Stephan Xie
Abstract
omitted), compares the utility of agent's play to that of the best-in- -hstiin-hindsihht fixed strategy. It is marginal guar- antee, in the sense that it forces the agent to do as well as the benehmark cumulatively over all rounds t = =1... T, but does not imply locally optimal performance on any subset of rounds. Thus, various extensions to more challenging bench- mark classes have been developed, giving rise notions such as swap regret, adaptive regret, and beyond.
We give an efficient algorithm for producing multi- dimensional forecasts in an online adversarial en- vironment that have low bias subject to any poly- nomial number of conditioning events, that can depend both on external context and on our pre- dictions themselves. We demonstrate the use of this algorithm with several applications. We show how to make predictions that can be transparently consumed by any polynomial number of down- stream decision makers with different utility func- tions, guaranteeing them diminishing swap regret at optimal rates. We also give the first efficient algorithms for guaranteeing diminishing condi- tional regret in online combinatorial optimization problems for an arbitrary polynomial number of conditioning events - i... on an arbitrary number of intersecting subsequences determined both by context and our own predictions. Finally, we give the first efficient algorithm for online multicali- bration with 2/3) rates in the ECE metric.
Typically, regret minimization algorithms directly optimize the agent's loss or reward function. This works well in single-agent settings and for simple regret guarantees. How- ever, this direct approach does not naturally address se- quential environments which (a) involve multiple decision- making agents with different utilities/rewards; or (b) de- mand performance guarantees conditionally on the agents' actions. Motivated by these challenges, in this paper we take different route and shift from direct reward opti- mization to a more subtle but flexible approach.
Recipe
1. Distill the decision-making relevvan aspects of the sequential environment into a sequence of "suffi- cient statistics": vector-valued states of the environ- ment, such that all agents could easily identify their swward-maiimizing actions if they perfectly knew the next state.
1. Introduction
Decision making in sequential settings a challenging prob- lem from both the theoretical and the applied perspective. Tackling the nonstationarity inherent sequential interac- tive decision making settings is the subject of the online learning, reinforcement learning, and bandits literatures (see e.g. Slivkins et al. (2019)).
2. Devise an efficient online adversarial algorithm that predicts the upcoming state of the environment with such granular accuracy guarantees that the agents can treat our predictions as the true states for the purposes of picking reward- wwwardmmximiziig actions.
The dominant paradigm is regret minimization, which places emphasis on optimizing various notions of regret for dacision-making agents, thus ensuring that these agents' mulative rewards stay ahead of nontrivial benchmark classes of strategies. The most basic and tractable notion of regret, called external regret (with the qualifier "external" usually
Step of this recipe will naturally always require insight into the specific setting at hand, and identifying appropriate sufficient statistics can often be an art. However as we will show in this paper- - Step 2, which may appear just as hard to execute, turns out to have a "silver-bullet" solution that applies to a wide variety of complex secision-making settings: our event- unbiased prediction framework.
'Department of Computer and Information Science, Univer- sity of Pennsylvania 'Machine Learning Department, Carnegie Mellon University. Correspondence to: Georgy Noarov <gnoarov@ scas.upe...duu>.
1.1. Our Contributions
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Our central contribution is a general and efficient algorith- mie framework for event-unbiased prediction of vector quan-

---

Hlihh-Dimensionll Prediction for Sequential Decision Making
tities in the online adversarial setting. It accommodates arbitrary finite collections of (unweighted weighted) con- ditioning events, which may depend on external contexts or on the predictions themselves, and guarantees optimally converging bias conditional on each of these events. We introduce the framework, and formally derive the algorithm and its guarantees, in Section 2.
also, e.g., over those days when it rained and they went to get coffee their way work; or over those days when their local football team was playing.
Our algorithm has an efficient dependence on the dimension d of the combinatorial problem (e.g. d is the number of edges in online routing): it runs using only poly(d) calls to the offline oracle for the problem (e.g. shortest-path -ptt algo- rithm for routing) and has O(d) regret dependence. Prior techniques for giving conditional regret guarantees by direct regret minimization (e.g. the algorithm of Blum & Mansour (2007)) have running time scaling with the number of ac- tions (e.g. paths in online routing), which can be exponential in d in online combinatorial optimization. See Section 4.
We then show how our framework implements the above recipe in complex environments shared by one more decision-making agents. In this context, as our Recipe pre- scribes, we use it in a "Predict-then-Act" manner, which allows us to bypass direct optimization of policy rewards for any given agent, instead focusing on forecasting the evolv- ing state of the environment, which the agents' rewards ultimately depend on. The main advantages this offers are:
Swap Regret for Multiple Agents In the classical experts setting but with multiple regret-minimizing agents, we show how to use our framework to issue single coordinating prediction at all rounds that will guarantee swap regret at optimal rates to all agents simultancously. See Section 3.
(1) Strong conditional regret guarantees: By leveraging our predictions, the agents can minimize their regret not just marginally over the whole sequence of the interaction, but also on arbitrary context- and action- defined subsequences of the rounds. This is enabled by our framework's ' ability to de-bias its state predictions over arbitrary such subse- quences of rounds, thus endowing the agents' decisions with corresponding regret guarantees on these subsequences.
Online Multicalibration In Section 2.2 we show that our algorithm, when appropriately instantiated, gives the first ef- ficient O(T2/3) online multicalibration algorithm. Multical- ibration "Hébert-Johnson et al., 2018) is a strengthening of the classical statistical concept of calibration (Dawid, 1985), and promises calibrated predictions on rich collections of contextually defined groups in the data. The best-known efficient algorithm for (vanilla) online calibration is due to Abernethy et al. (2011), and we match its rate in the more challenging multicalibration setting. The best-known multi- calibration bound achieved in the ECE metric was O(T3/4) (Gupta et al., 2022).
(2) Coordination of multiple agents: Instead of letting all agents take the burden of running their respective regret min- imization algorithms locally, we are able to instead provide a single public- koowleeenwwe state prediction, which all agents can then use to inform their actions in a straightforward way: They can just best-respond to the announced state.
We illustrate the power of our framework on the following concrete examples:
1.2. Follow-up Work and Impact
Online Combinatorial Optimization We consider a gen- eral online combinatorial optimization setting, which mod- els a sequential interaction of multiple agents with combi- natorially large action spaces corresponding to structured subsets of some set of d base actions, and which encom- passes a variety of classical problems such as online routing. We show how to endow all agents with conditional regret guarantees, letting the agents incur only sublinear regret on any given finite collection of subsequences defined by external contexts and even by their own actions.
Since the appearance of the preprint of this paper, our methodology has been employed in several subsequent works, showing the broad utility of our framework.
Collina et al. (2024b) apply our algorithms in a repeated principal-agent setting defined by Camara et al. (2020) to obtain exponentially improved bounds. Briefly, Camara et al. (2020) gave a mechanism that replaced the standard "coommon prior" assumptions that underlie principal-agent models with calibrated forecasts of an underlying state, and is applicable in adversarial settings. Camara et al. (2020) use the traditional notion of calibration, and as a result inherit exponential computational and statistical dependencies on the cardinality of the state space. Collina et al. (2024b) show how to apply our techniques to recover the same results (under weaker assumptions) with exponentially improved dependence the cardinality of the state space.
An example instantiation is the online routing problem in which multiple agents are trying to get from home work as fast as possible every day. We can issue trustworthy daily road congestion forecasts, such that each agent who always selects the fastest route according to our forecast is guaranteed no regret conditional both on salient covariate information (such as the weather) and on their own choice of route (e.g. downtown route; interstate route; route visiting their favorite coffee shop). Thus, each agent will then be happy with their average travel time not just overall, but
Roth & Shi (2024) apply our algorithms to produce fore- casts that guarantee all downstream decision makers O ((VT) swap regret without the need to know their utilities in ad-
2

---

Hlihh-Dimensionll Prediction for Sequential Decision Making
vance, improving on the simultaneous no-external regret guarantees of Kleinberg al. (2023).
in the Appendix. As one important precursor to our work, Haghtalab et al. (2023a) develop a general online multiobjec- tive learning framework based on game between no-regret and best-response algorithms, with the focus on deriving im- proved multicalibration guarantees in the online and batch settings. Their reduction to no-regret learning allows them, in particular, to obtain small-loss group-calibration bounds, mirroring our small-loss event-conditional bias bounds.
Hu & Wu (2024), using our algorithm, further remove any dependence on the cardinality of the decision maker's 's action space in the 1-dimensional setting.
Collina et al. (2024a) use our algorithm as part of their construction giving computationally tractable "agreement" protocols generalizing Aumann's agreement theorem.
Lehrer (2003) defined notion of "wide-range regret" which is equivalent to conditional regret: that player should have no regret not just overall on the whole sequence of rounds, but also conditional on various events - subsequences that can be defined both as a function of time ("time selection functions") and as a function of the actions of the learner. Blum & Mansour (2007) gave algorithms for obtaining this kind of conditional regret guarantees (including, notably in- ternal (or "swap") regret as special case). The algorithm of Blum & Mansour (2007) is efficient when the action space is polynomially sized: it requires computing eigenvectors of a square matrix of dimension equal to the number of actions in the game. Motivated by fairness concerns, Blum & Lykouris (2020) give an algorithm for obtaining diminish- ing "groupwise" regret, which is equivalent to regret with respect to collection of time selection functions. These results do not accommodate events that can depend on the actions of the learner, which are crucial for our applications.
Our original extended preprint contains another application of our algorithm, to decision conditional "score-free" con- formal prediction. By appropriately de-biasing the scores of any online multiclass predictor, we can make them look like correct class probability vectors to downstream prediction set algorithms, letting prediction sets with valid conditional coverage guarantees be simply "read off" from the multi- class probability vectors.
1.3. Related Work
Our framework extends an array of recent prior works decision-focused prediction. Zhao et al. (2021) introduce decision calibration: a calibration basedd framework for the offline (batch) setting. Decision calibration is less expressive than our weent-unbiasedness notion: e.g.. unlike our frame- work, it does not imply swap regret guarantees. Gopalan et al. (2022a) introduce omniprediction: an approach for making predictions that simultaneously can be used opti- mize multiple downstream loss functions. Omniprediction is related to our Predict-then-Ae approach to optimizing utilities for multiple agents: the onni-predictions need to be post-processed downstream to optimize each loss, but can be treated as if they are real probabilities in that down- stream optimization. Dwork et al. (2021) study outcome indistinguishability: a complexity making predictions that appear indistinguishable from the ground truth to rich class of distinguishers. These works have generated considerable follow-up research, which we discuss in Appendix A. We extend these insights into a broadly applicable, efficient online adversarial framework with optemal-rate guarantees.
2. General Framework and Algorithm
Unbiased Prediction Setting Let X' be context space which can be arbitrary. Let the state space S be any convex and compact subset of Rd and assume without loss of gener- ality that max,ss || < 1. Any element s E S is called a state. The space of distributions over S is denoted AS.
perspective on
In this section, we consider the task of online adversar- ial contextual prediction of the states over E [T] := {l...., TT. time steps. The learner sequentially observes contexts (Z))<E(T) E (X"T, T and makes randomized state predictions (5e)ce(r)) E (AS)T. The adversary sequentially responds by generating the true states (St)se(m) E (S)T.
No-Regret Guarantees in Online Learning No-regret learning has been studied at least since Hannan (1957); see Hazan (2016) for modern treatment of this literature. Kalai & Vempala (2005) gave efficient no regret algorithms in online linear and combinatorial optimization problems. Internal regret, which corresponds to regret on the subse- quences defined by the play of each action, was first defined by Foster & Vohra (1999), who also showed it could be obtained by best responding to calibrated forecasts.
The learner aims to make predictions unbiased conditional on a given collection = (FE))sew) of 2 events.
Definition 2.1 (Event;
Bias). An event is mapping E :: X S - |0, 1); the event's value in round I is E(x,, 8z). If the range of E is (0, 1} then we call E a binary event.
The cumulative E-conditionall bias in coordinate i E [d] of the state predictions after T rounds is defined as:
The seminal contribution of Foster & Vohra ( (1999) has led to long list of works exploring the interplay of no-regret and online calibration algorithms, discussed in more detail
Biast (E,1)=
E 8 VE
Σ t
E (w1, (Be, -8.s)
3

---

High-Dimensional Prediction for Sequential Decision Making
The general protocol is as follows. In rounds = ....P:
one such method called MsMwC (Multiscale Multiplicative Weights with Correction) due Chen al. (2021) whose domain is the d' d'-dimensional simplex: C = Da. This special setting is also called the experts setting, as each of the vertices (ea)se(ar) of the simplex (e: E Rdd denoting the ith standard basis vector) can be viewed as an expert. Rather than only promising O(vT) regret to the best expert, MsMwC obtains small-loss bounds simultaneously each expert, which scale with the losses of the expert:
1. The learner observes context 2, E X, and receives event functions = [0, 1] for F. E E.
2. The learner makes state prediction st E AS.
3. The adversary sees & and generates frue state s E.
4. The (realized) prediction s E S is sampled: s ~ s'
Theorem 2.3 (Theorem 2 of Chen et al. (2021)). There exists experts OLO algorithu AMsMwo with per-round time complexity poly(d") ( for d' experts, whose chosen points wy E A'a,t E [2], achieve the following regret bound to every expert e, E [d') provided all losses la E [-1,
The learner's goal is to make predictions that are unbiased in all coordinates i E [d] conditional on all events E E &. In fact, we define our desideratum by requir- ing the bias rate conditional on every event to diminish as a function of the event's 's frequency (rather than as a func- tion of the time horizon T'); such strengthened bounds are referred to as small-loss in online learning-
Objective:
Regr (AMsMwO, e,) =0 (Log(dT)+ log(d'T)
Σ G
Definition 2.2 (Unbiased Prediction). Let (T)
E En_ (E (z), {.))²] denote the incidence! of event F. Then we call the learner's predictions unbiased conditional on event collection& & if for all events E' E E,
The General Unbiased Prediction Algorithm We now apply the OLO tools described above to obtain an efficient unbiased prediction algorithm that achieves the guarantee of Definition 2.2 for any finite event collection E, state space S and feature space X.
max Biast (F, 0 (log(dE)T)) (F) :E[d]
For notational convenience, we will represent any event collection & (Ej)ge(m) as a single vector-valued event function E : X x S - [0, 1J" Definition 2.2 essen- tially requires us learn to make randomized state predic- tions ($)) to optimize the quantity: v ((x.),, (s)) ==
We further denote Biasy == max Biast (E,
2.1. General Algorithm with Bounds
OLO Primitives We now develop a general algorithm that achieves the above bias bounds for any given finite event collection. It will rely on online linear optimization (OLO) methods. We briefly review the OLO protocol over any d'- dimensional convex domain C C Rdd. In rounds t = 1...T, an OLO algorithm Aoto plays some & E C, the adversary observes that and generates a loss vector l E Rd, and AOLO observes l, and suffers loss (2) in that round. The overall performance of AOLO is measured via OLO regret to the best point in C that could have been played. Letting the regret to any admissible point be defined as Regr(Aoto, c)= := aemiifee C2- - c). the OLO regret of AOLO is defined as:
max] Σ T Ey &e) st..) |. However, this
objective has a complex. and generally nonconvex and non- differentiable, dependence on the predictions &, so directly optimizing it appears out of reach. Yet, we will now show how to achieve this via a two-layer algorithmic technique: first, a reduction to a surrogate minimax objective, followed by a "simulated play" solution of that minimax problem. For both layers, will use OLO algorithms subroutines.
First Step: We identify weights Wi E Azan, t E [T], in an online fashion such that the following surro- gate objective
Σ u closely approximates V: :5.(5)))1))
Regr == max Regr eEC
ΣT
Σ W((Gas) a. (x,, (t). (E(d).E(M)
Many OLO algorithms AOLO achieve the classic minimax regret bound
= OVVT) for all convex com- pact domains C and bounded losses; the simplest one is online gradient descent (OGD) of Zinkevich (2003).
Second Step: While the surrogate function Ee ue usefully separates the original objective across rounds E [T'] each u ($,, s:) still depends on & through the event mappings, which need not be convex or differentiable. However, it is linear in the adversary's 's choice of st, and this can be exploited due to the following observation: If the adversary committed to s first, the learner could achieve value 0 in the zero-sum game max,, ming, u4 (e(,,, 8t) by simply copy-
However, for particular domains C, algorithms with even stronger regret bounds have been developed. We will use
Note: nT (E) is most the expected count of E's occurrences (i.c., rounds where F( &t) = 1), with equality for binary F.
4

---

Highh-imennional Prediction for Sequential Decision Making
ing the adversary, i.e., with &, st. Therefore, simalating the reverse playthrough of this game, with the adversary going first and the learner copying, can give us a random- ized saddle-point strategy 6 for the learner: namely, the empirical distribution of the learner's simulated plays. This will suffice so long as the adversary plays to optimize the variable 8, using any no-regret OLO algorithm. Therefore, by simulating sufficiently many rounds of this "no-regret adversary copycat learner" game, we can get as close as we want to the value of the game.
Regr (o
Σ
(coutor Wt -o",""1
[E[T]
= =E Wri(ass) a. E3 (1)) $2,3)
+
Rearranging and taking max over o", we get for all i"
Now we are ready to present our general Algorithm 1. For the first step, it instantiates the Chen et al. (2021) MsMwC
T
Σ F (8t) - s1,50]
algorithm for 2dn experts corresponding to signs o = =, coordinates E [d] and events j E [m]. to enable bias bounds that depend on each event's incidence count. For the second step. it uses any no-regret OLO algorithm As that can optimize over the state space S; this could be OGD or any other general-purpose O O(VT)) algorithm.
I max Regr (AMaMwC, cor, o e
E "ilaii))) a- Eij (Bt. T,odi
T
= =0 +1 log(dnit)yer (oggddit)t (Ejr.
Algorithm 1 Unbiased Prediction
ue (Se, st),
Initialize 8g = 0%,,, 80 = 0", (.) = 0", and AMsMWC-
for t = 1...T' do
where us is as defined above, and the regret bound follows from Theorem 2.3 since the total squared 2
Get context 24 E X. and define E¹()) := E(z,,)) .). Get new weights we by updating AMsMWWC: with losses:
loss of each expert (o, is: Et=1 (Centoer.))
q--1 a E - (Be-1) (8t-1.2 -82 a.d. Initialize a new instance of As and any stout E S. for 7 = 1...t? do
O (ELn &)))) = O(nr(EE)).
Step 2: By definition of regret for As, we have for any t:
Get simulated prediction steu by updating As with:
Rege (As) = max SES
ginner
TE(M
ginnrr
Σ
W (a,k)) Ey (s
Σ
Σ
E3 (stene)
(ston 8:)
JE(m]
iE(d]
max SES
Wi.la,is)
TE(E"] o..
end for Set 8 < Unif (1sfout, pent
max SES rE(t"]
Σ
Ut (stont .)) =t_
mmxx E SES Bewds
[uo(Se, $)
Sent J).
8/2
Predict & ~ 5t.
Observe true state 8t.
The last line uses 5, + Unif (Isbout, stent
tent }).
end for
Thus, using that As has regret O(VT), we have ELe (e 8t) I
Theorem 2.4 (Bias of Algorithm 1). For any time horizon T, and instantiated with any O O(VT)-regret OLO method As over domain S, Algorithm 1 produces (randomized) predictions (T whose realizations (St) achieve the desired bias bounds for all i E [d] and Ez.j j E [n]:
E BeruBete
(As)
O 1- = O(log T): lower-order term. Taking the expectation of the Step 1 bound thus gives the result. O
2.2. Efficient ((T2/3) Online Multicalibration: Sketch
Biast (E,i) S O (log(d(E(Z) + (E)
We now sketch a simple application illustrating that our high- dimensional prediction methodology can be useful even for migle-dimensiooal forecasting. This application also showcases the utility of our per-event bias bounds scaling optimally as O S/rr((F) (( rather than as O(VT).
Proof. Step 1: We instantiate AMAMWC for 2dn experts, corresponding to signs = 11, coordinates E [d] and events E [m]. Let the weights of MsMwC be (wE)221. and denote our loss vectors for MsMwC by (Equter) )r21. as defined in Algorithm 1. Denote experts' basis vectors by Caji.j. For every a² = =1 i" E [d],3" " E [n]:
Online Multicalibration In this setting (Gupta et al., 2022; Hebert-Johnson et al., 2018), a learner, in each round
5

---

Hlgh--iimensionl Prediction for Sequential Decision Making
L E (T), receives context 3y X, makes (randomized) prediction Pt E [0, 1). and receives true adversarial label y E [0, 1j. Upfront, group collection G S 2 is specified, and the learner's goal is to minimize the expected calibra- tion error (ECE) conditional on every group G E g: i.e. to minimize, for all groups E G. the expectation of:?
We call an agent straightforward if they trust the predictions correct (as if S; 5.) and thus always best respond: Definition 3.3 (Straightforward Agent), An agent with util- ity u who treats predictions as correct and on every round t chooses d, BR,,, (8x)) is called straighfforward.
Regret Since our predictions need not be correct, a straight- forward agent may regret not having taken some other se- quence of actions in hindsight (i.e. with knowledge of the true states 81, ,1,)..,8() We study several regret notions.
ECE(G)=
E DC 1E(0
Σ
1x. G] pl(ee -p)
8(). Definition 3.4 (External regret). The external regret of a utility-w u agent is defined as:
Obtaining the 0(T2/3) Bound via Unbiased Prediction We instantiate our framework by letting P = (P.).e(m) be the m-point uniform discretization of [0, 1], and defining
T Σ u(a, 81) u(ae: st).
the following mn [ group-calibration events:
Regr = max aEA
EG. 1 [2, E G.P. E (P;
1. P. 2m P.
Definition 3.5 (Swap regret). A mapping Ø : A + A is called a strategy modification mapping. Let T be the set of all such mappings. The swap regret of a utility-u agent is:
For each "bucket" (P:= 1.): tions pt that fell in this bucket to be P.. For each group G, let ( G be the incidences of all discretized predicted values on G. We can then derive the bound:
), imagine reassigning all predic-
T
SwapRegr(u) == max des
u(p(a)), st) u(a,, $t).
ECE(G) = O(T/m)+
Σ O(VTuG)). sE(m]
External regret compares the agent's play to the best fixed ac- tion. Swap regret (Blum & Mansour, 2007) is strictly more challenging (indeed, external regret is equivalent to compet- ing against the K constant strategy modification functions (Øa) (oa)EEA where 6a : A + A is given by (a = a for a' E A), and allows the agent to compete against all re- re-mappings of their actions into other actions.
where the first term is the discretization error, and the rest are bias bounds. In the worst case, this is O /m + my TT/mm) O(T/m /mmm+ + VTm). By tuning m 72/3, we thus obtain the first efficient ((T2/a) online multicalibra- tion method. This rate in particular matches the rate of the algorithm of Abernethy et al. (2011) for vanilla calibration.
We now introduce the strong notion of conditional regret, parameterized by collections of events that may depend on the contexts and on the agent's 's actions. It requires the agent to have no external regret conditional on every event.
3. Unbiased Prediction for Decision Making
We now apply the unbiased framework to making predic- tions in the service of online adversarial decision making.
Agents (Decision Makers) We study agents (decision makers) who can choose amongst a set of actions A = (1...., K.. They want to maximize utility as a function of both the action they take and of the state s E S C Rd.
Definition 3.6 (Conditional Regret (Lehrer, 2003; Blum & Mansour, 2007; Lee et al., 2022)). Fix E, a finite collection of covariate dependtt and action-dependent subsequences of rounds: each member & is a mapping X'x - [0, 1]. The E-conditional regret of a utility-u agent is:
Definition 3.1 (Agent's Utility). A utility function u
A S + [0. 1] maps an action a E A and state s E S to u(a, s). We assume that for every action a E A, u is linear and L-L-ipschizz in 8, so that [u(a, $1) u(a, 82) I L| s2 11.00 for all 81, 82 E S and some L > 0. Definition 3.2 (Best-Responsed
CRegr(E,
T
= max 6E5,0EAA
E(rr, (u(a, 8t) u(a,, 8i))
The best response func- tion' BR.: S for utility u is: BR,(s)= = =armmax u(a,s).
3.1. Swap Regret Guarantees for Many Agents
dEA
Environment Consider any convex compact state space S C Rd. Suppose there are agents, each with K dis- crete actions and with utility functions (u:)een) that are linear and L-Lipschitz the state variable s E S. We will now show how to make predictions ($t) to simul- taneously guarantee no swap regret to every agent, given
Suppose we make predictions s,...., &t. An agent with util- ity u may use them to take corresponding actions a,...., at.
The summation over p E [0, 1), despite looking uncountable,
only has 7 nonzero terms, corresponding to pop5 {pt,...,pr)) .pr). assume that all ties are hroken lexicographically.
6

---

Hlihh-Dimensionl Prediction for Sequential Decision Making
that all agents are straightforward, i.e. they all best-respond: d BR.,, (8+) for i [n]. We will do it by applying the unbiased prediction framework with the following natural collection of nK events.
pected L [ Biasr (Bur.a)
error away
from:
Ue ((a)), Eu, au, Eu, (81)5) Us a. E E Eu,
(5))))
aEA
However, this last expression can be rewritten as E'= uo(((ar,)), 84) - u,(us,,, i00e,,i,, 8t), which is nonpositive since actions at = BR,, (8:) obtain the best utility when evaluated on predicted states &G. This means that we have shown L L (ias)(Eu,a)) expected regret bound for any agent to any swap function & A - A, which implies that each agent has expected swap regret at most L [nE(K] Biast(En...))
Best-Response Events We write (s) = 1 (s) = a] to denote the binary event that a is a best response to a for utility u. These events are essentially level-ser events of the agent's best-response correspondence. We will now see that producing E-conditionally unbiased predictions (TT) for the ni-si event collection & = (iEjt))))))) will suffice to guarantee no swap regret to all agents.
Informally, the reason these events give no swap regret to each agent w, is the following. Fix any strategy modification function @ E 4. Then each event Eu..a will ensure that on those rounds & where u; played a [K], the predictions & are sufficiently unbiased that response that assumes the predictions are correct, is in fact the (approximately) best action to play over those rounds; in particular, a will have no regret to the re-mapped action á(a) E [K] on those rounds. Since this argument applics to all re-mappings á E and all actions E [K], it will by definition ensure swap regret to agent ug.
Note that exactly one event from {Eu,,a occurs at each time I. Thus, EnE NT (T((Bu,)) S T, so that L EuEg K] Biastr(Eu,.)) = O(L EaElK] (Fura)) S OLLK \T/K) OLLVKT), Therefore, we have shown:
BR.,, (št), the best
Theorem 3.7 (No Swap Regret for Multiple Agents). the above setting with n agents, all with K actions and Lipschitz utilities, if all agents best-respond to our forecasts (& (TT)) then by making these forecasts via E-unbiased prediction for & = (Eu,,) (aE,,)) [E(()) the we efficiently obtain (() swap regret bounds for all agents simultaneously.
Formally, fix any u, and swap Φ: A + A. We express the agent's 's regret to swap & in terms of (Eu(a))E(K] as:
In the context of experts learning for single decision maker, similar observations about the relevance of best-response partitions have been previously made by Perchet (2011) and Haghtalab et al. (2023b).
(((((a)s) - St)
Σ
u,(o(a), st) - -u,(as))) st)
4. Conditional Regret Guarantees for Online Combinatorial Optimization
at A A.RR, (5)
T
Σ
(1,((()))) - s.(a,))))
The regret guarantees that we just obtained for n agents with size-K action sets required unbiased predictions con- ditional on O(n)) events, resulting in poly(nK) runtime. This method applies to any finite action sets, and will be efficient where agents' action sets are modestly sized. How- ever, when the agents' action sets are combinatorially large, this runtime is prohibitive. Below we identify an impor- tant setting in which an exponentially improved (oracle-) complexity poly(n K)) can be obtained.
tE1t=1
By linearity of u; in 8t, we combine terms to get:
T Euqia (8t)))
Σ
p(a),
a
Σ Uj
a
(
aEA
4.1. Setting: Online Combinatorial Optimization
Now, by L-Lipschitzness of us for a' (()) we have
In a combinatorial optimization setting (as studied by Kalai & Vempala (2005)), there are d 2 1 base elements, or base actions, e B : {I,..., ..,,..... d]. each offering an associated reward r. E [-1, 1]. In this setting, an agent has action space A C 2 - arbitrarily structured collection of subsets of the base action set and their utility AxS + [-d, d] is defined as the sum of the rewards of the base actions in the chosen action:
T
T
EC
Uj
Eu, (8:
ui a', Σ
Eu, (8c)st
1=1
T
< L
E
Σ
Fansaa (8t) (8+ se)
L BiasT am
x
Applying this to both terms in the above &- regret expression, we have that it is only an ex-
u(a,r) ((ar))= := =Ire for a A. 111
eEa
7

---

fligh-Dimensional Prediction for Sequential Decision Making
Thus, given a vector r (re) (ee) of d base rewards, the agent's optimization task is to identify, from among their actions E A. the highest-reward subset of the base action set. An offtine oracle for this problem is any algorithm that, given r, computes the agent's best action in A.
in T, by directly optimizing over the entire action set A, of each agent. However, their runtime will then scale polyno- mially in |A.] which can be large as 12(2), thus making the runtime exponentially large in the problem size.
Our framework, by contrast, will let us give the agents con- ditional regret guarantees simply by unbiasedly predicting the d- d-dimensional base reward vectors (conditionally on appropriate events). Our general algorithm will thus run in time poly(d), giving us efficient algorithm with an exponential runtime improvement compared to prior work.
Now, we define a contextual online n-agent setting in which base rewards vectors rt are generated by an adversary in rounds t E [T]. In this setting, each agent i's goal will be to learn to play actions (E(T) that will minimize an appropriate notion of regret to the hindsight-best policy from some benchmark policy class.
4.2. Conditional Regret via Unbiased Prediction
Formally, consider an arbitrary context space X, and n 2 combinatorial agents with action sets (A,) ketml repeatedly playing the following game in rounds t [T). In round
To derive conditional regret guarantees via unbiased predic- tion, we will use the same Predict-then-Act approach as in Section 3. At the beginning of each round t, we will (ap- propriately unbiasedly) predict the rewards vector i E S. Every agent E [rx] will then best-respond to our prediction and select action dr,, = BR., (fr).
1. Agents i E [n] observe context di E X' and commit to their actions Cr E A;;
2. Adversary produces base rewards vector rz E [111, 1jd,
However, to make this approach efficient, must now design our event collection differently than before. Indeed, consider the simplest case where we ask for no external regret to downstream agents. The collection of "level set" events { aE [e([)),,,EA, studied in Section 3 will imply sublinear regret as before - but will too big as it scales with | which can be exponential in d.
3. Agents see r4 and get utilities u,(ae,s)r)) re) = Σ Te,--
eEar,
Examples Suppose the base elements B correspond to the roads in a road network, the feasible subsets A, for each agent i E [n]] correspond to collections of roads that form source-to-sink paths for that agent in the network, and the reward for each road (edge) E B in the network is the (negative) latency on this edge. This classic instance of online combinatorial optimization is called online routing or online shortest paths (Takimoto & Warmuth, 2003; Kalai & Vempala, 2005). More generally, the action spaces A; could represent any combinatorial structure; other well- studied examples include spanning trees, Hamiltonian paths, and fixed-size subsets of the base set. For many of these classical examples, there exist efficient offline oracles, such as Bellman-Fore for shortest paths or Prim or Kruskal for spanning trees.
To overcome this, we will take advantage of the special structure of the payoffs, which are all linear in the base element rewards. The idea is to condition on events defined by the base elements e E B = [d]. Again starting with no external regret, it turns out that for each agent i E [n] it suffices to condition on the always-on event, and on d events (Ee) (Ee)ae(d: for each base element e, E, will be the event that the agent's 's chosen action de,5 contains e, i.e. Eg 1[e E BR,, (s)]. This requires just nd events over all agents. From here, if we now desire E-conditional regret guarantees, it will suffice to expand this event collection to ( events per agent: for each E < E, the intersectional events E (z, s) = {(x, s) Es (s) for e E [d[ (that both & is active and Eg is active), as well as the event that is active whenever & is active, will imply no external regret conditional on E.
The FTPL algorithm of Kalai & Vem- pala (2005) reduces the problem of obtaining efficient exter- nal regret bounds for combinatorial optimization problems to the offline problem of linear optimization over the ac- tion spaces A₁. Here we show for the first time how to efficiently obtain much stronger and more granular regret bounds: namely, E-conditional regret bounds for any poly- nomially large collection of events E. Moreover, unlike prior results, our result will provide these guarantees si- multaneously for any finite collection of agents, letting publish concise forecast that is simultaneously useful for many downstream consumers.
Regret Guarantees
Importantly, observe that all these events can be evaluated via direct calls to the offline optimization oracle for the problem (e.g.. Bellman-Forr for routing); therefore, the unbiased prediction algorithm will be oracle efficient. We now state and prove our conditional regret bound.
Theorem 4.1. Consider online combinatorial optimization over context space X with d base actions and n. agents with action sets A, C 2íd), Suppose each agent is straightfor- ward, and wants to obtain no E,-conditional regret for some
Some existing general-purpose purpose online algorithms (Blum & Mansour, 2007: Lee et al., 2022; Haghtalab et al., 2023a) could be used to obtain conditional regret bounds sublinear
8

---

Highh-Dimensionl Prediction for Sequential Decision Making
events E. Define the following set of events:
Acknowledgements
8 U (LEakhero U {
We are grateful to Edgar Dobriban, Amy Greenwald, Ja- son Hartline, Michael Jordan, Shuo Li, Jon Schneider, and Rakesh Vohra for insightful conversations various stages of this work.
Here, Eg (2) = 1/c- BR (Fr) BRu, (fr)); and (t) = E( BR (fe)). for all e, E
Impact Statement
Then, running Unbiased Prediction on state spuce S [-1, with event collection & will produce a sequence of predictions (fe) such that each agent playing their best-response actions at,; BRu, (fe) at all rounds, will obtain () expected Excoodiitioaa regret. The runtime will consist of poly (dT Σi=1 [E;]) oracle calls the offline optimization oracle for the setting.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
[n], by
References
Proof. It suffices to fix any agent [n] and event & E E, and show that best-responding the E-unbiased predictions (fe (T)) gets no external regret subsequence ç. Denote the agent's external regret on the subsequence g by:
Abemetty,, J., Bartlett, P. L.., and Hazan, E. Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 27-46. JMLR Workshop and Conference Proceedings. 2011.
CRogr(E,
T
Bastani, O., Gupta, V., Jung, C., Noarov, G., Ramalingam, R., and Roth, A. Practical adversarial multivalid con- formal prediction. In Advances in Neural Information Processing Systems, 2022.
Σ E(ar, ar,)) (u;(a" u, (ar,5; Tt)). E.A,A
=max
Now, consider the hypothetical "ideal" scenario in which our predictions exactly correct every round, i.e., fr for all t. Then, our "ideal" regret would be nonpositive:
Blum, A. and Lykouris, T. Advancing subgroup fairness via sleeping experts. In 11th Innovations Theoreti- cal Computer Science Conference (ITCS 2020). Schloss DaasstuhlLLeinnizzzeemnn für Informatik, 2020.
IdRegr (E)
T
Σ
E(r))r))) (uz(a", ft) u,(ar,s, 0 1=1
max E.E.A
Blum, A. and Mansour, Y. From external to internal regret. Journal of Machine Learning Research, 8(6), 2007.
since for each t, at, BR,, (ft) and thus u,(ae,s; ft) maxacA; ui(a, fz) u,(a" fr). Therefore,
Camara, M. K., Hartline, D., and Johnsen, A. Mechanisms for no-regret agent: Beyond the common prior. In 2020 ieee 6lst annual symposium foundations of computer science (focs), pp. 259-270. IEEE, 2020.
CRegr(E, s CRegr (5, (S,
This difference in regrets can be expressed as:
Chen, L., Luo, H., and Wei, C.-Y. Impossible tuning made possible: A new expert algorithm and its applications. In Conference on Learning Theory. pp. 1216-1259, PMLR, 2021.
max a' EA.
(x ar,)) uula", re)
Σ E( a1,)) u,(a",
max a" EA,
Collina, N., Goel, S., Gupta, V., and Roth, A. Tractable agreement protocols. arXiv preprint arXiv:2411. 197991, 2024a.
T
+ Σ E( a..)) (uz(ar,s, ft) - us (a rt)).
Collina, N., Roth, A., and Shao, H. Efficient prior-free mechanisms for no-regret agents. In Proceedings of the 25th ACM Conference on Economics and Computation, pp. 511-541, 2024b.
It is easy to check that the first line's expectation is at most Biast(FF) EE). Similarly, by decomposing the second line's expression across the d coordinates, it can be seen that its expectation is at most Eneoy Biast(E (Ees) Hence, the expected regret of agent i conditional on { is at most Eeeld Biasr (F(.g) + BiasT(FE) = OddvT).
Condat, L. Fast projection onto the simplex and the I ball. Mathematical Programming, 158(1-2):575-588 2016.

---

Hligh-Dimensional Prediction for Sequential Decision Making
Dawid, A. P. Calibration-based empirical probability. The Annals of Statistics, (3(4):1251-12) 1985.
rules. In Proceedings of the 24th Annual Conference Learning Theory, pp. 293-314. JMLR Workshop and Conference Proceedings, 2011.
Demirović, E., Stuckey, P. J., Bailey, J., Chan, J., Leckie, C., Ramamohanarao, K., and Guns, T. An investigation into prediction+ optimisation for the knapsack problem. In Integration of Constraint Programmingg Artificial In- telligence, and Operations Research: 16th International Conference, CPAIOR 2019, Thessaloniki, Greece, June 4-7, 2019, Proceedings 16, pp. 241-257. Springer, 2019.
Garg, S., Jung, C., Reingold, O., and Roth, A. Oracle efficient online multicalibration and onniprediction, In ACM-SIAN Symposium on Discrete Algorithms, 2024.
Clobus-Harris I., Harrison, D., Kearns, M., Roth, A., and Sorrell, J. Multicalibration as boosting for regression. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), International Confer- ence on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 11459-114111 11492. PMLR, 2023. URL.tttsss:/pprreeedii v202 gww.gluuooorriiiie
Donti, P., Amos, B., and Kolter, J. Z. model learning in stochastic optimization. Advances in neural information processing systems, 30, 2017.
end-to-end
Dwork, C., Kim, M. P., Reingold, O., Rothblum, N.N., and Yona, G. Outcome indistinguishabiiity. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1095-1108, 2021.
ml press/ html.
Gopalan, P., Kalai, A. T., Reingold, O., Sharan, V., and Wieder, U. Omnipredictors. In Braverman, M. (ed.), 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, Jamuary 31 -Febuurry 3, 2022, Berkeley, CA, USA, volume 215 of LIPlcs, pp. 79:1-79:21, Schloss Dagstuhl Leibniz-Zenntrmm für Informatik, 2022a. doi: 10. 0123300LPPics..TTSS.022222. org 10. 4230/ http/IIIIIIISSS ITCS. 79.
Dwork, C.. Kim, M., Reingold, O., Rothblum, G., and Yona, G. Beyond bernoulli: Generating random out- comes that cannot be distinguished from nature. In Das- gupta, S. and Haghtalab, N. (eds.), Proceedings of The 33rd International Conference on Algorithmic Learning Theory, volume 167 of Proceedings of Machine Learn- ing Research, pp. 342-380. PMLR, 29 Mar-01 Apr 2022. httpttps: httpp//ooceennnsseeeee ings .ml.. press// v16 21677/cwon /wwwww222222..m.. html.
URL https: /doi.
Gopalan, P., Kim, M. P., Singhal, M. A., and Zhao, S. Low- degree multicalibration. In Conference on Learning The- ory, pp. 3193-3234. PMLR, 2022b.
El Balghiti, O., Elmachtoub, A. N., Grigas, P., and Tewari, A. Generalization bounds in the preoiii-teen-optiiize framework. Advances in neural information processing systems, 32, 2019.
Gopalan, P., Hu, L.., Kim, M. P., Reingold, O., and Wieder, U. Loss minimization through the lens of outcome indis- tinguishability. In 14th Innovations in Theoretical Com- puter Science Conference (ITCS 2023). Schloss Dagstuhl- Leibniz-Zentrum für Informatik. 2023a.
Elmachtoub, A. N. and Grigas, P. Smart "predict, then optimize". Management Science, 68(1):9-266 2022.
Gopalan, P., Kim, M. P., and Reingold, O. Characterizing notions of omniprediction via multicalibration. arXiv preprint arXiv:2302.06726, 2023b.
Fisch, A., Jaakkola, T., and Barzilay, R. Calibrated selective classification. arXiv preprint 2r0i / 12084, 2022.
Foster, D. P. and Hart, Smooth calibration, leaky forecasts, finite recall, and nash dynamics. Games and Economic Behavior, 109:271-293, 2018.
Gopalan, P., Kim, M., and Reingold, O. Swap agnostic learning, or characterizing omniprediction via multical- ibration. Advances in Neural Information Processing Systems, 36, 2024.
Foster, D. P. and Kakade, S. M. Calibration via regression. In 2006 IEEE Information Theory Workshop-I7W Punta del Este, pp. 82-86. IEEE, 2006.
Grötschel, M., Lovász, L., and Schrijver, A. Geometric Algorithms and Combinatorial Optimization, volume Algorithms and Combinatorics. Springer, 1988. ISBN 008-3-642-9788833 doi: 10. 10.10077978----442-7788
Foster, D. P. and Vohra, R. Regret in the on-line decision problem. Games and Economic Behavior, 29(1-)):7335 1999.
Gupta, C. and Ramdas, A. and multiclass-to-binrry reductions. arXiv preprint WrXi::210700835. 2021.
Top-label calibration
Foster, D. P. and Vohra, R. V. Asymptotic calibration. Biometrika, 85(2):379-390, 1998.
Foster, D. P., Rakhlin, A., Sridharan, K., and Tewari, A. Complexity-ban approach calibration with checking
Gupta, V., Jung, C., Noarov, G., Pai, M. M., and Roth, A. Online multivalid learning: Means, moments, and
10

---

Prediction for Sequential Decision Making
prediction intervals. In 13th Innovations in Theoreti- cal Computer Science Conference (ITCS 2022). Schloss Degsuubl-Lcibniz-Zzntttu für Informatik, 2022.
Processing Systems, volume 30. Curran Associates, Inc., 2017. URL httpps:/ neguri cc /c//apper_fillee/pprr/////////Le 1b99f000ccaad0000cccffffetb..... pdf.
Haghtalab, N., Jordan, M., and Zhao, E. A unifying per- spective on multi-calibration: Game dynamics for multi- objective learning. Advances in Neural Information Pro- cessing Systems, 36:72464-72506 2023a.
Kim, M. P. and Perdomo, J. C. Making decisions under outcome performativity. In 14th Innovations in Theoreti- cal Computer Science Conference (ITCS 2023). Schloss- Dagstuhl-Leibniz Zentrum für Informatik, 2023.
Haghtalab, N., Podimata, C., and Yang, K. Calibrated stack- elberg games: Learning optimal commitments against cal- ibrated agents. urXiv preprint Niv:22306002004, 2023b.
Kim, M. P., Ghorbani, A., and Zou, J. Multiaccuracy: Black- box post-processing for fairesss in classification. In Pro- ceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pp. 247-254, 2019.
Hannan, J. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, 3:97-139, 1957.
Hazan, F. Introduction to online convex optimization. Foun- dations and Trends@ in Optimization, 2(3-4):157-325, 2016.
Kleinberg, R., Leme, R. P., Schneider, J., and Teng, Y. U- calibration: Forecasting for unknown agent. arXiv preprint arXiv:2307.000 2023.
Hazan, E. and Kakade, S. M. (weak) calibration is computa- tionally hard. In Conference on Learning Theory, pp. 3-1. JMLR Workshop and Conference Proceedings, 2012.
Kuleshov, V. and Liang, P. S. Calibrated structured predic- tion. Advances in Neural Information Processing Systems, 28, 2015.
Héhert-Johnson, U., Kim, M., Reingold, O., and Rothblum, G. Multicalibration: Calibration for the (computationally- identifiable) masses. In International Conference on Ma- chine Learning, pp. 1939-1948. PMLR, 2018.
Lee, D., Noarov, G., Pai, M., and Roth, A. Online minimax multiobjective optimization: Multicalibeating and other applications. Advances in Neural Information Processing Systems, 555299551-29065 2022.
Hu, L. and Wu, Y. Predict to minimize swap regret for all payoff-bounde tasks. In 65th IEEE Annual Sym-
Lehrer, E. A wide range no-regret theorem. Games and Economic Behavior, 42(1):101-115, 2003.
posium on Foundations of Computer Science, FOCS 2024, Chicago, II, USA, October 27-30, 2024, pp. 244- 263. IEEE, 2024. doi: 10.11099FO03611222222400000 URL https: //o::///ooi// http:///.........1//111 http://1111199///// 2024. 00024.
Liu, H. and Grigas, P. Risk bounds and calibration for smart predict-then-opting ooen-ipt method. Advances in Neural Information Processing Systems, 34:22083-22094, 2021.
Mandi, J., Stuckey, P. J., Guns, T., et al. Smart predict-and- optimize for hard combinatorial optimization problems. In Proceedings of the AAAI Conference on Artificial In- telligence, volume 34 (02). pp. 1603-1610, 2020.
Jung, C., Lee, C., Pai. M., Roth, A., and Vohra, R. Moment multicalibration for uncertainty estimation. In Conference on Learning Theory, pp. 2634-2678. PMLR, 2021.
Jung, C., Noarov, G., Ramalingam, R., and Roth, A. Batch multivalid conformal prediction. In International Confer- ence on Learning Representations (ICLR), 2023.
Noarov, G. and Roth, A. The statistical scope of multicali- bration. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), International Con- ference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceed- ings of Machine Learning Research, pp. 26283-26310. PMLR, 2023. URL httpp::/pproeeeeeeeeett press/ Tress/v202/nooo w222//oaaoo223aaammmmm .htmlll..............m.mm html.
Kakade, S. M. and Foster, D. P. Deterministic calibration and nash equilibrium. Journal of Computer and System Sciences, 74(1):115 10::115-1330 2008
mllr
Kalai, A. and Vempala, S. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-3077 2005.
Perchet, V. Internal regret with partial monitoring: Calibration-based optimal algorithms. Journal of Ma- chine Learning Research, 12(6), 2011.
Khalil, E., Dai, H., Zhang, Y., Dilkina, B., and Song, L. Learning combinatorial optimization algorithms over graphs. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information
Qiao, M. and Valiant, G. Stronger calibration lower bounds via sidestepping. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 456-466, 2021.

---

Hligh-Dimensional Prediction for Sequential Decision Making
Roth, A. Uncertain: Modern topies in uncertainty estimation. http://www.ckk.upnn..ttuu aanoth/nnerraintyynotee....p 2022.
Roth, A. and Shi, M. Forecasting for swap regret for downstream agents. In Proceedings of the 25th ACM Conference Economics and Computation, pp. 466- 488, 2024.
Rothblum, G. N. and Yona, G. Decision-making under miscalibration. arXiv preprint arXiv:2203.09853 2022.
Slivkins, A. et al. Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1- 2):1-286, 2019.
Takimoto, E. and Warmuth, M. K. Path kernels and mul- tiplicative updates. The Journal of Machine Learning Research, 4:773-818, 2003.
Vanderschueren, T., Verdonck, T., Baesens, B., and Verbeke, W. Predict-then-opiimize or predictandd-opimmize" an empirical evaluation of cost-sensitive learning strategies. Information Sciences, 194:400-415, 2022.
Wang, L., Joachims, T., and Rodriguez, M. G. Improv- ing screening processes via calibrated subset selection. In International Conference on Machine Learning, pp. 22702-22726. PMLR, 2022.
Wilder, B., Dilkina, B., and Tambe, M. Melding the data- decisions pipeline: decision-focused learning for combi- natorial optimization. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 33 (01), pp. 1658-1665, 2019.
Zadrozny, B. and Elkan, C. Transforming classifier scores into accurate multiclass probability estimates. In Proceed- ings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 2002.
Zhao, S., Kim, M., Sahoo, R., Ma, T., and Ermon, S. Cal- ibrating predictions to decisions: A novel approach to multi-class calibration. Advances in Neural Information Processing Systems, 34:22313-222
2021.
Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pp. 928-936, 2003.
12

---

Hlihh-Dimensional Prediction for Sequential Decision Making
A. Additional Related Work
The study of sequential calibration goes back to (Dawid, 1985) who viewed as a way to define the foundations of probability, and algorithms for producing calibrated forecasts an adversarial setting were first given by (Foster& & Vohra, 1998). (Foster& & Vohra, 1999) were the first connect sequential calibration to sequential decision making, showing that decision maker who best responds to (fully) calibrated forecasts obtains diminishing internal regret (and that when all agents in a game do so, empirical play converges to correlated equilibrium). (Kakade & Foster, 2008) and (Foster & Hart, 2018) make a similar connection between "smooth calibration" (which in contrast to classical calibration can be obtained with deterministic algorithms) and Nash equilibrium.
Calibration
Much of the calibration literature has focused on the binary prediction and one dimensional regression settings, where labels are in (0. 1} or in [0. 1), and predictions are in [0, 1]. Comparatively few works, including (Zadrozny & Elkan, 2002; Kuleshov & Liang, 2015; Gupta & Ramdas, 2021), have addressed higher dimensional predictions, which, as discussed, are challenging because of the curse of dimensionality; many of these works have sought to reduce multiclass calibration problems to binary calibration. In this context, our work in particular proposes tractable notions of online multiclass calibration for cases when there is a specific downstream task that the forecasts will be used for.
Multicalibration In the recent computer science literature, there has been interest in constructive calibration guarantees (obtained by efficient algorithms and obtaining good rates) that hold conditional on context in various ways, called multi- calibration (Hébert-Johnson et al., 2018). Multicalibration has been studied both in the batch setting (Hébert-Johnson et al., 2018; Kim et al., 2019; Globus- Harris et al., 2023; Haghtalab al., 2023a) and in the online sequential setting (Foster Kakade, 2006; Foster et al., 2011; Gupta et al., 2022: Garg et al., 2024). For the most part (with a few notable exceptions (Gopalan et al., 2022b; Zhao et al., 2021)) multicalibration has been studied in the 1-dimensional setting in which the outcome being predicted is boolean. This has been extended to predicting real-valued outcomes, with notions of calibration tailored to variances (Jung et al., 2021), quantiles (Bastani et al., 2022; Jung et al., 2023), and other distributional properties (Noarov& & Roth, 2023). See (Roth, 2022) for an introductory exposition of this literature. Our algorithm can be used to recover many of the above online multicalibration guarantees by plugging in appropriate events, but it goes beyond multicalibration constraints.
Omniprediction A growing line of work (Gopalan et al., 2022a; 2023a;b; 2024) aims to use (multi)calibration as a tool for a mieddmmeniional form of downstream decision making, called onniprediction. The goal of omniprediction is to make probabilistic predictions of binary outcome as a function of contextual information that are useful for simultaneously optimizing variety of downstream loss functions. E.g., (Gopalan et al., 2022a) show that a predictor that is multicalibrated with respect to a benchmark class of functions H and of binary label can be used to optimize any convex, Lipschitz loss function of an action and binary label. Also related is the outcome indistinguishability strand of research (Dwork et al., 2022), which studies producing decisions that are indistinguishable from the ground truth according to a collection of tests.
Conceptually, our motivation is slightly different than for omniprediction: while omniprediction aims to produce forecasts that are good enough to optimize for large (typically infinitely large) family of possible downstream tasks characterized by their associated losses- such that may not know ahead of time which task will present itself our framework is developed to handle finitely many arbitrary but specific (i.e., known-in-advance) downstream tasks. The above mentioned results are in the batch setting.
In the online setting, (Kleinberg et al., 2023) defined "U-calibration,, which can be viewed as a non-contextual version of omniprediction where the goal is to make predictions that guarantee an arbitrary downstream decision maker no external regret. In comparison to (Kleinberg et al., 2023), our goal is to give both stronger guarantees than external regret, and be able to do even when the state space is very large.
Calibration for Decision Making The most closely related work is (Zhao et al., 2021), who define and study "decision calibration" in the batch setting in the context of predicting a probability distribution over k discrete outcomes. Decision calibration is slightly weaker requirement than what we study, also defined in terms of the best-response correspondence of a decision maker's 's utility function. Decision calibration asks, informally, that a decision maker be able to correctly estimate the expected reward of their best response policy; we ask for a slightly stronger condition that requires them to also be able to estimate the utility of deviations as a function of their play. This kind of unbiased estimation (based on the best-response correspondence of a decision maker) has also been previously observed to be related to swap regret in (Perchet, 201 1) and
13

---

Hlihh-iimension Prediction for Sequential Decision Making
(Haghtalab et al., 2023b). The algorithmic portion of our work can be viewed as extending (Zhao et al., 2021) from the batch to the online adversarial setting: Our applications hinge erucially on both the online aspect of our algorithm and on the more general setting we consider, beyond predicting distributions on & outcomes.
Subsequently to (Zhao et al.. 2021), decision calibration has been extended to, or applied in, several specific downstream tasks in the batch setting. For instance, (Fisch et al., 2022; Wang et al., 2022) applied decision calibration in the presence of downstream selection or screening processes. These and omniprediction ideas were also used to obtain new performative prediction algorithms in (Kim & Perdomo, 2023). In the opposite direction, (Rothblum & Yona, 2022) study how downstream decision policies can be modified in response to miscalibrated forecasts.
Predict then Optimize An expansive recent literature has focused on the similarly named predict- thelicttthen-aeeee tepptiiitee prob- lem (Elmachtoub & Grigas, 2022; El Balghiti et al., 2019; Liu & Grigas, 2021). This line of work investigates a setup in which predictions made from data are to be used in a linear optimization problem downstream in the pipeline. This is similar in motivation to our framework, but with two important differences: (1) the predict-then-optimie aims to optimize for single downstream problem, whereas we aim to simultaneously provide guarantees to an arbitrary finite collection of downstream decision makers; and (2) the surrogate loss approach studied in this literature is naturally embedded a batch/distributioonal setting, where the goal is to exactly optimize for the Bayes optimal downstream decision policy, up to generalization/risk bounds; meanwhile, our framework naturally lives in the online adversarial setting, and aims for different notions of optimality defined in terms of regret bounds, as well as omniprediction -type 'best-in-class' optimality. Both frameworks can be used to solve downstream combinatorial optimization problems (Mandi et al., 2020; Demiovvíć et al., 2019); but our framework appears to have broader set of applications as consequence of its strong calibration properties, we are able to apply our framework to derive strong uncertainty quantification guarantees, which do not appear to naturally fit within the predict-then--piimize framework. There also exist other approaches for learning in batch decision making pipelines, that are different from the predict-then-optimg method; see e.g. (Donti et al., 2017; Khalil al., 2017; Wilder et al., 2019; Vanderschueren et al., 2022).
framework
B. Calibration and Decision Making
The notion of calibration (Dawid, 1985) requires that predictors make forecasts that are consistent with the ground truth conditional on the predicted values themselves. For instance, for a binary predictor f X + [0, 1], it enforces, roughly speaking, that B(z.g) (x) = o] x v, for all v E [0.
Calibration has very strong -theoretc properties. When making predictions about a payoff-relevan state, in very general setting it is dominant strategy amongst all prediction-to-action policies for every downstream decision maker to best-respond calibrated predictions as if they were correct. This has strong semanties as "trustworthiness" can do no better than to trust calibrated predictions and act accordingly. It also implies strong performance guarantees for the downstream decision makers. Here are two examples: First, decision makers who best respond to calibrated forecasts are guaranteed to have no swap regret- - meaning that they obtain utility that is as high as the best action they could have played in hindsight, not just marginally, but also conditionally on each action that they played (Foster & Vohra, 1999). The second example concerns multi-class prediction, where a from some large set. Standard machine learning methods for multi-class classification will, given features, predict "scores" for each label that look like probabilities in that they are non-negative and sum to 1. These scores not probabilities; nevertheless, decision makers who produce "prediction sets" of labels by treating calibrated scores as if they were real probabilities will find that their prediction sets cover the true label with the same frequency that they would if the scores really were conditional label probabilities. So sequential calibration offers very strong guarantees - and it has been known since (Foster& & Vohra, 1998) that it is possible to produce calibrated forecasts even in adversarial environments.
one
maker observes features and predicts an unknown label
But calibration is in different senses both too strong and too weak. On the one hand, calibration is too weak in that it provides only a marginal guarantee; calibrated forecasts will in general fail to be calibrated conditional on external information. Thus, the property that downstream agents can do no better than to treat calibrated forecasts correct will fail to hold if the downstream agents have access to external context. In one-dimensional prediction settings (such as real-valued regression), multicalibration (Hébert-Johnson et al., 2018) mitigates this weakness: it allows one to enforce calibration not just marginally, but also conditionally on any collection of context-dependent groups or subpopulations in the data.
On the other hand, calibration is too strong in that (because it is agnostic to downstream decisions) it conditions on fine distinctions in its predictions that may be irrelevant to the downstream task at hand. As a result, calibration is intractable in
14

---

High--imensional Prediction for Sequential Decision Making
high-dimensional settings. Since calibrated predictions must be statistically unbiased conditional on their own values, then for d-dimensional prediction problems in which, up discretization, there are 52(24) possible values may predict- we, naively, need to respect (2(24) possible conditioning events to stay calibrated. Given this intuition, it should come as no surprise that the best known calibration algorithms have exponential computational and statistical complexity in dimension d of the outcome space; there exist some lower bounds in the literature that confirm this hardness, see e.g. the PPADD-hardness result of (Hazan & Kakade, 2012)). In fact, even in dimension, it is known that achieving adversarial calibration at a rate of O (vT) is impossible (Qiao & Valiant, 2021) - even though is possible to obtain swap regret at this rate (Blum Mansour, 2007). Thus, despite its remarkable guarantees, calibration has been of little utility in designing online algorithms for high-dimensional problems.
C. Connecting Prediction and Decision Making
We next make connections between our ability to make unbiased predictions and the quality of decisions that are made downstream as a function of our predictions in a general setting. The form of the argument will proceed in the same way that it will in our main applications, and so instructive.
Specifically, we will show that straightforward decision maker who simply best responds to our predictions can be guaranteed no swap regret if we just make our predictions unbiased conditional on the events defined by the decision maker's best-response correspondence.
The Predict-then-Act Paradigm These results, whose formal statements given below, suggest a natural design paradigm for sequential decision algorithms, which we call predict-then-act. The idea is simple: first we make a prediction & for an unknown payoff-relevant parameter 8t, and then we choose an action as if our prediction were correct - i.e. we best respond to 8g. We can parameterize the predict-then-ai algorithm with various events E, such that our predictions will be unbiased with respect to events in E. Whenever & is a collection of polynomially many events that can each be evaluated in polynomial time, the predict-then-act algorithm can be implemented in polynomial time per step. While Predict-Then-AAe quite simple, its flexibility variety of settings lies the design of the event set & and prediction space S. By choosing the events& & to be appropriately tailored to the task at hand, we can arrange that Predict-Then-Ae Act has guarantees of various sorts.
Algorithm 2 Predict Mielict-Thennn Teee-heeeeneeeee (T,
for t 1 do Compute 1 <-UnbiasedFred
Predict 8, ~ w/ for Uj E ll do Decision maker i selects action dz = BR,, (8t) = argmax aEA (a(a,8)
end for Observe outcome 8, S end for
We now develop, and use, our machinery based on the Predict-then-Ace approach powered by our Unbiased Prediction algorithm's guarantees, to give algorithms with strong no-regret guarantees variety of sequential settings. In all cases, the scenario we analyze is that rounds f, predictor makes state predictions š,, after which one or more decision makers choose actions that are best responses to & (i.e. they function as straightforward decision makers). When are designing an algorithm for single decision maker, we always use the predict-then-are paradigm (Algorithm 2). When we are designing a coordination mechanism, we imagine that our predictions are simultaneously issued, on every round, to multiple decision makers, who each independently act. We show how guaranteeing that our predictions are unbiased subject to appropriately chosen events gives desirable guarantees for downstream decision makers of various sorts.
C.1. Transparent Policy Evaluation and Its Downstream Benefits
In this subsection, we introduce the main benefit of calibration that underlies, in one form or another, all our following applications. Namely, calibrated (or, as we will see, sufficiently unbiased) predictions result in what we call a transparent policy evaluation property, whereby downstream agents' prediction-to-actie policies will in hindsight (once the true states
15

---

High--imensional Prediction for Sequential Decision Making
are revealed) bring as much utility to the agents they would get had the predictions been exactly correct. In that sense, the predicted states are indistinguishable from true states for the purposes of policy evaluation. In nutshell, this enables straightforward downstream optimization of the next action to play while only having access to predicted, rather than realized, quantities - and is the main vehicle that drives our Predict-then-Ase approach where agents simply best-respond to the predictions. This general "transparency" property of calibration is also what underlies outcome indistinguishabiity (Dwork et al., 2021) and omniprediction (Gopalan et al., 2023a) in I-dimensional batch settings, and (Zhao et al., 2021) gave similar transparency guarantees multi-dimennional batch settings - but as we will see, will be especially useful for us in problems arising in high-dimensional online settings.
In this and the next subsection, we begin by deriving this transparency property (and its downstream consequences) in the idealized scenario where the predictions å are exuctly calibrated (i.e., there is no error term). This, of course, is a statistically unachievable goal in high dimensions, and so these results won't It yet be implementable. However, this presents no issue for our algorithmic results- - which do have error rates- - because given access to approximately calibrated or unbiased predictions (which we will generally obtain by invoking our Unbiased Prediction algorithm), bias error propagation through our idealized proof templates is quite easy. Meanwhile, these idealized statements and their proofs provide the core statistical intuition about why our approach works.
We begin by formally defining how we want to evaluate the long-tern success of any prediction-to-accion policy in online setting.
Definition C.1 (Policy Evaluation Function). A policy evaluation function is mapping U (S + A) S S R. The interpretation is that for any prediction-to-action policy f 8 + A and any two sequences of states 5, 8 E S with len(s) = len($) < co, Uff s) will give the total utility of the policy f evaluated on the ground truth state sequence s when actions are taken according to the predicted state sequence 8.
We will usually instantiate this definition as follows. Fixing any time horizon T' and any decision maker with utility function u: : A x + R. we will let the evaluation function U be defined as the decision maker's cumulative (total) utility of employing the policy f applied to predictions á across rounds I,..., T. namely,
Ua(J, 8,) = Σ u 88))
where s = (si...., ST) are the ground truth states and 8 = (s....... R are the predicted states. Note that due to our assumption that the decision maker's 's utility u is linear and Lipschitz in its second argument, the policy evaluation function Un will linear and Lipschitz its last (ground-truth) argument 8.
Our main results will all follow from appropriately instantiating our event collection such that it guarantees the following property of our sequence of predicted states, relative to (relevant) prediction-te io-action policies.
Definition C.2 (Transparent Policy Evaluation). Fix a crddiction-to-cctinnn policy f : - and a policy evaluation function U: : (S A) x S* S* R. Consider any two sequences of states 8, 8 E S with len(s) (en(() < co. We interpret s as the ground truth state sequence, and & as predicted state sequence.
Then, the predictions á are (f, U, s) transspaenttt if:
= U U(,
Henceforth, we will keep the ground truth sequence implicit and refer to predictions 3 as Uf, -raasspaptr
This notion of transparency it at the core of our proposal for how to define trustworthy predictions in decision pipelines: If the predictions are (f, transspeant, then decision maker with utility u who employs prediction-to -o-atiionoooooionnnno policy f can safely view the predictions & as exactly coinciding with the ground truth states s - in the sense that she can measure the performance of f (using U') against the predictions rather than against the true states. This is often useful property on its own - but when it holds for multiple prediction prediction-to-action policies f. then optimizing amongst these policies on the basis of the predicted outcomes implics performance guarantees corresponding to optimality within this benchmark set.
Enforcing Transparency via (Full) Calibration We now see how full calibration lends transparency to all prediction-to- action policies with respect to all evaluation functions Un as defined above.
16

---

Hligh-Dimensional Prediction for Sequential Decision Making
Theorem C.3 (Calibration Lends Transparency All Prediction-to-Action Policies), Fix any time horizon T. Consider any ($1.-..,58 ST) and any fully calibrated sequence of predictions & = (81y...; ST), meaning
ground truth sequence states that for all { ST) ). it holds that [ f A and every u A x S + R. that is linear in its second argument.
v #(t E [T] 5t = v.. Then, & is (f, U U.).aaaaapparee for all
Proof. The proof follows directly by definition of (full) calibration (equality (2)) and by linearity of u in the state (equalities (1) and (3)). Letting The == # #(1 E [7) & = o) for any value E IR, we get:
U,( Σ u u([(B)),))) = E E
m((()),
11
Σ
[(v),
Σ
WER :E
VER
:E(T):
T
uff()).un.)
Σ n u(f()),)) PER
Σ
u(f($)), = -U,(f,,,8)
Using Transparency for Downstream Optimization Transparency its own is valuable insofar it means that decision maker can follow prediction-to-action policy f with respect to predicted outcomes without being surprised about her long-run utility. But as we will now observe, it is also directly useful to decision makers for the purposes of optimizing their prediction-to-actiin policy. In fact, we will now see that enforcing the transparency property over all policies / in any prediction-to-aat to-action policy class F that includes the best-response policy (.) == (R.( lets the decision maker obtain no regret to any other policy that class F by simply playing /BR in all rounds (i.e., trusting the predictions and acting
accordingly).
Theorem C.4 (Transparency over Policy Class FF Implies Best Best-Response Optimality over F). Consider a decision maker with utility function u A - R. Consider any collection of prediction-to toatonn-ttt-ttioonno policies C S such that the decision maker's 's best response policy is included it: JBR E F.F
Suppose the sequence of predictions is (f, Ua) transsaaapprr all f E F. Then, committing JBB gives the decision maker no regret with respect to the policy class F:
U Ua
BR 3. max U 3,)
JEJ
Proof. Fix any policy f E F. By the definition of transparency (noting that foR E F) and the definition of the best response policy:
U.
BR 8) Uu(f. U.RR 8, Uv(58855)
max S-S-A
U Ud((,,,8)) 20,
implying the desired statement.
As an immediate corollary, we see that full calibration implies that the best response policy is simultaniously optimal for all downstream decision makers, amongst all prediction-to-acet -oaacioon policies.
Corollary C.5 (Calibration Implies Global Optimality of Best-Response Policy to All Decision-Makers), Suppose the predictions& & are fully calibrated. Then, simultaneously for all downstream decision makers (i.e., for all utilities u : AxS + RR,, playing the best-response policy f gives the decision maker no regret to all prediction-to- to-action policies:
J.SAA U. U.BB 8, max Un(,, 8,8) for all decision makers' utilities u
Proof. As established, full calibration gives transparency to every decision maker (with any utility u) with respect to the entire class of all peeictionnto-action policies Fru := SA, Thus, by the preceding theorem, playing the best-response policy gives no regret all f S A.
17

---

Hlihh-Dimensional Prediction for Sequential Decision Making
C.2. Transparency via Level-Set Unbiasedness and Swap Regret
Let us re-examine what properties our predictors should have in order achieve transparency for various prediction-to-action policies. Fix any such policy S + A, and suppose for a moment that we only need (f. U,) transparency for this specific f and for all u A x S + R.
We already know that calibration - which demands unbiasedness from our predictions conditional on every possible prediction value v E S - is sufficient for this purpose (Foster & Vohra, 1999). But it is not necessary. Intuitively, this is because the total utility U. of policy f does not require such granular predictions for estimation. In particular, consider the collection of level sets of policy f. defined as LS(f) := {f (a))aAA These level sets form a partition of the state space S, but unless the mapping / : S + A is injective (which would necessitate the action space A being at least as complex as the space of predictions S), this partition will be (likely much) less granular than the partition of S into single points as required by full calibration. To determine which action to play, policy f only requires knowledge of the level set that the prediction belongs to, not the exact predicted value- and in this sense, LS(f) provides the right level of granularity over the state space S for us to confidently estimate the total utility of f. We formalize this as follows.
Theorem C.6 (Transparent Policy Evaluation via Level-Set Set Unbiasedness). Consider any policy f: + A. Suppose the predictions are unbiased on the level sets of J. in the sense that for each level set V E ELS(f) (note that V S {S)i it holds that E 8t St = 0. Then, the predictions are (f, -taaspapppa for all possible decision makers' utilities u: A S RR
Proof. For each level set V E LS(f), let f(V) E A denote the action to which f maps every prediction in V.
T
Un(f = Σ
s(f( = Σ Σ
v((())) = Σ
Σ
u(f(V), st)
t=1
VELS, tE(T):&EE
VELS, :E[T]&&
= Σ u [(V),
Σ
Σ " S(V),
Σ
81
Σ
Σ
u(J(V), 8.)
VELS,
EE EE
VELS,
1E :E(TISSLEV
VELS, tElTiSs.Ev
T
Σ VELS, LE
E
m(f($)),
= Σ -
But in fact, this result can be significantly strengthened at no cost. Consider the set 4 =(:: A + A} of all self-maps of the action set A. For reasons that will become clear very soon, we will also refer to self-map & E A as a swap. As it turns out, predictions that are unbiased on the level sets LS(f) of a policy f lend transparency not just to the f itself but also to each prediction-to-action policy f that is a post-processing of the map f by a swap 6 E A, that is, So = =.of.
Theorem C.7 (Level-Set Unbiasedness Gives Transparency under All Swaps). Consider any policy f : S + A. As in the above theorem, suppose the state predictions á are unbiased on all level sets V E &S(()) of f. Then, they are (Φ o J, U.) ttanssparen for all swaps Φ : A A A and for all decision makers' utilities u : A x R.
- A. Then, the level sets of & e f either coincide with, or are strictly coarser than, the level sets of f. Indeed, viewing LS(f) and LS(ø f) as partitions of S, it is easy to see that LS(f) is refinement of LS(Ø f), in the sense that for any V T.S(f) there exists some V' E TSS( o f' with V VV. As a result, each level set of @ o f is a disjoint union of one or more level sets of f. Thus, since the predictions å are unbiased on the level sets LS(f) of f. they are also unbiased on the level sets LS(Ø o f) of Φ o f. implying by the above theorem that they are (o f. -tan-ttaaspar for all decision maker's utilities u.
Proof. Fix any swap ø: : :A-4
This strengthened result is very useful because implies no swap regret guarantees for decision makers when the predictions are unbiased on the level sets of the decision maker's 's best-response policy.
Theorem C.8 (No Swap Regret via Unbiasedness on Best Rest-RRspponse Level Sets). Fix any decision maker with utility function Ax& S + R. Consider her best-response policy fBR : + A. Then, if the predictions 8 are unbiased on the level sets LS(FRR) of the best-response policy, the decision maker will obtain no swap regret by employing the best- policy:
Un (FBR 8, max Un (0 o fBB 8,,8).
AAA-A
18

---

By relaxing the minimization player's domain from to ASS), the set of distributions over predictions, we have made the objective linear (and hence convex/concave), but we have continuously many optimization variables - both primal variables (for the minimization player) and dual variables (for the maximization player). Our strategy for solving this problem in polynomial time will be to argue that has a solution in which only |E] many primal variables take non-zero values, that efficiently identify those variables, and that can implement separation oracle for the dual "constraints" in efficiently solve with Hlghh-iimensionl Prediction for Sequential Decision Making
Proof. Since the predictions á are (do feR, , -tanspaappr for all swaps @ : A A, by the definition of the best-response policy, we get:
Un CBR 8,8)
Un (oo JBR 8,6) U. (JuR 8, max
Un (1b PBR 8,
max O:A+A
d.A+A
D. Faster Unbiased Prediction for Disjoint Events
In this section we show how to find an e-approximate solution to the minimax problems min max u, at all rounds E [7]. defined in Section 2. with running time that is polynomial in d, |&], and log(1/e) in the case in which the events E' E & are EREE
binary valued and disjoint: for all x, 8: > REE (x 8) S 1. We will also assume that for every history и and context æ, the predictions& that satisfy E(T, x, 8) = form a convex set for which we have polynomial time separation oracle.
Throughout this appendix, we refer to weights we from Section de and to the randomized strategies & from Section 2 as thr
Our goal is to solve for the learner's equilibrium strategy dhe A(S) in the game with utility function
d (3, = E E E (l 1 a. 1( 8) (8, - -s,)
Σ
i=1 o= FEE
corresponding to the per-round gain of MsMwC. In other words, we need to approximately solve:
V argmin max E [ux s}]. WEA(S) sES gmap
(I)
polynomial time. This will allow us construct reduced but equivalent linear program that the Ellipsoid algorithm.
We first observe that in the utility function (A, 8), the learner's predictions "interact" with the outcomes only through the activation of the events (( Zt, 6). This implies that conditional on the values of the events (T Te, 8), there is a unique á that minimizes ue(-,s) simultaneously for all s. general, the collection of events E F,, $) could take on many different combinations of values but our assumption in this section that the events are disjoint and binary means that there in fact only ||] different candidate values of for us consider namely, those defined by the following efficiently solvable convex programs:
Definition D.1. For E E &, let " be solution to the following convex program (selecting arbitrarily if there are multiple optimal solutions):
d
minimizeses
It.bo,.)) a -8
1=1 0
subject to
E( 1.
Let P.- (8) "TEE Remark D.2. As we have assumed in this section, the set of & such that E(T,-1,, 24, 8) is convex region endowed with a separation oracle, and so these are indeed convex programs that we can efficiently solve with the Ellipsoid algorithm. This is often the case: for example, if we have decision maker with a utility function u over K actions, the disjoint binary events E... (for each action a E [K] are defined by K linear inequalities, and so form convex polytope with a small number of explicitly defined constraints; this collection of events is relevant for obtaining diminishing swap regret for downstream decision makers.
TEEs be collection of [E] vectors in S constituting solutions to the above programs.
We next verify that the prediction values defined in Definition D.I are best responses for the minimization player against all possible realizations &t that the maximization player might choose, conditional on a positive value of a particular event:
19

---

High- High-Diimensioal Prediction for Sequential Decision Making
Lemma D.3. Simultaneously for all S, we have:
$t" argmin
u4 (3.
consequence this is that solutions to the following reduced minimax problem (which now has only |E| variables for the minimization player - the weights defining distribution over the |&] points $ ) are also solutions to our original minimax problem 1:
argmin max E [1,(6,))) *EA(P)) aES Smup
(2)
Lemma D.4. Fix any optimal solution of to minimax problem 2. Then ui{ is also an optimal solution to minimax problem 1.
Thus, to find a solution to minimax problem 1, suffices to find solution to minimax problem 2. Minimax problem 2 can be expressed as a linear program with | + variables but with continuously many constraints, one for each 8 E ES:
minimize subject to
Eu-plue(B, S Vs E.
We can find an e-approximate solution to Salynomial-variable linear program using the Ellipsoid algorithm in time polynomial in the number of variables and log(1/e so long as we have efficient separation oracle - i..., an algorithm to find an c-violated constraint whenever one exists, given a candidate solution. this case, implementing a separation oracle corresponds to computing a best response for the adversary (the maximization player) our game-and since the utility function in our game is linear in the adversary's chosen action s, implementing a separation oracle corresponds to solving linear maximization problem over the convex feasible region S-a problem that can solve efficiently assuming we have separation oracle for S. There
number of technical details involved in making this rigorous, which can be found in Appendix D. Here we state the final algorithm and guarantee.
Algorithm 3 Get-AAproo-
(f,
for F E & do
Solve the convex program from Definition D.I to obtain B7
end for
Let P, = ($. BES-
Solve linear program over P. using the weak Ellipsoid algorithm to obtain solution 1y/
Let o/r be the Euclidean projection of vi onto ((P:) returned by the simplex projection algorithm.
Return vr.
Theorem D.5. Given polynomial time separation oracle for for any e >> O, there exists an algorithm (Algorithm 3) that
returns an e-approximately optimal solution vi minimax problem 1 and runs in time polynomial in d, [8), log( (
We solve for e-approximate solution of linear program using weak separation oracle, using an approximate version of the Ellipsoid algorithm.
Definition D.6. For any > O and any convex set S, let
S {s: ||s - 3||2 Se for some ă E S} S-c {s: B2(s, C
be the positive and negative c-approximate sets of S, where Bz(xrr) r) is ball of radius under the f2 norm.
Definition D.7. A weak separation oracle for convex set S is an algorithm that, when given input t E Q4 and
positive Q, confirms that vb S if true, and otherwise returns a hyperplane a e Qd such that ||a]loc 1 and (a, v) < (a, v/") + c for all s/ E S-
We express a separation oracle for linear program 3 as the convex program that solves for the most violated constraint given a candidate solution v), which is simply the best response problem for the maximization player in minimax problem This the problem of maximizing d-variable linear function over the convex set S. To make sure that we can control the bit
20

---

Hlgh--iieensioal Prediction for Sequential Decision Making
complexity of the constraint returned by the separation oracle we round the coordinates of the constraint a E Rd output by the separation oracle rational-valued vector within + of the exact solution by truncating each coordinate of a to log(?) bits.
Definition D.8. A solution vp E Sth is e-weakly optimal if, given e > 0, [u(s, s)] S Es [u(8, 8)] - ee for all
V S and for all s.
For an e-approximate solution to minimax problem 2, it suffices to find an c-weakly optimal solution to linear program 3, which we can do using the Ellipsoid method. However, the solution the weak optimization may not even be valid probability distribution (since it only approximately satisfies the constraints) in this case, we can project our infeasible solution back to feasibility. We use the simplex Euclidean projection algorithm given by (Condat, 2016) to project the candidate solution back to feasible region and show that this projected feasible solution is still e-approximately optimal.
Theorem D.5. Given polynomial-time separation oracle for S. for any > O, there exists an algorithm (Algorithm 3) that returns an e-approximately optimal solution यंद to minimax problem I and runs in time polynomial in d, log(
Proof. Linear program encodes minimax problem 2. approximate solution in polynomial time under the following conditions:
To solve LP 3, we use the Ellipsoid algorithm, which gives an
Theorem D.9 (Grrötschel et al., 1988), Theorem 4.4.7). Given a weak separation oracle over convex constraint set S and > O, the Ellipsoid algorithm finds e-weakly optimal solution over S in time polynomial in the bit complexity of the constraints returned by the separation oracle, the bit complexity of the objective function, and the bit complexity of c.
Fix some e > 0. Let S be the constraint set, which are a set of linear constraints over a convex compact set (i.e. s E S) and constraints enforcing a probability simplex (i.e. v/ E A(P)), implying that S is a convex set. Let e' 2cviei Given an
exact separation oracle over S. preserving log( () bits of the most violated constraint given by the separation oracle and rounding to rational number yields an rational é' e'paproxx most violated constraint, which satisfics the conditions for weak separation oracle. Thus, we can find an e'-weakly optimal solution (7' b²) to minimax problem 2, where v/ E S++. In the case that v/ is valid probability distribution, we have found an e-approximate optimal solution 1/r = v.
Otherwise, v/d may violate conditions for a valid probability distribution if the linear constraints do not constrain the feasible set (i.e. S = (P)). Since v/ E Stc,, there exists some x// E S such that || w'll S é'. We find this point vf via the simplex projection algorithm in (Condat, 2016).
We show that this projection back to a feasible probability distribution still leaves us with e-approximately optimal solution. Let (8 s) be the -dldimensio vector such that each coordinate E' has entry uz s). First, we show that |u, (87.") [)] is bounded by C = 2 max ||/||> for E. E E:
d
|u(37- $)1 S Σ
Σ
I,.i., : -E(,, 87 B7 187,5 sil
im
rE( (-1,1) FEE
d
Σ (t.lt.o
187, sil
Σ Uiii,oE)) C = C,
1=1 oE 1,1) EEE
1=1
(-11)
EEE
where we used that F(x,, 87 BB < and |o| |0|=1, and that q E A(2d)))), implying must sum to 1. From this, we find that
(8 S /CP + .... + P88 < C CV8.
Next, by continuity of inner product, given 0,8 S, there exists 5 0 such that 1lyl - 8 implies that ||
[[Easjs (arappp(ue(,,, [M)( Ea (ur(8, < e. By Cauchy-Schward we can bound the difference between the expectations as
follows:
[ur( [S) Brague
E
( s]] -v- 6. ur(65 5)) S 11 4//12
< 6.CVV.
Thus, using vir = v as the solution and setting 8 e' gives us e' CV 20
approximate solution. By Lemma D.4, any optimal solution to minimax problem is an optimal solution to minimax problem 1, so we must have that vir is an e-approximate solution to minimax problem 1.
21

---

Tligh-Dimensional Prediction for Sequential Decision Making
Now consider the runtime of the algorithm. In order for LP to be well-formulated, we first solve E convex programs (one for each $*.E), which takes time polynomial in d. Now, consider the bit complexity of the constraints. For the inequality constraints, the bit complexity of each constraint bounding the objective function is given by the bit complexity of (eww/u((8, s)]. Each coefficient of ( is u :s) which is bounded by C' from above. Since there are |&| variables in this constraint, the maximum bit complexity of any constraint is bounded by Oloog())))) Similarly, the objective function has polynomial bit complexity on the scale of (llo((C))))) Finally, has bit complexity of log(;). The simplex projection algorithm has quadratic runtime in the dimension of the vector, which takes ((E))) time. Thus, the runtime of the algorithm polynomial in [E],
and log(?).
Lemma D.3. Simultaneously for all s S, we have:
St" F.
argmin (((8, 8).
Proof. The constraint that (( 1, F4, together with the fact that the set of events & is disjoint and binary implies that for all other events E" E E, E" ( 24, 6) = O. For any such that ETT 24, 8) 1, we therefore have that un (3, 8) reduces to:
(B)
(.(i..)) a. 8, (t,tt..)) a Si-
(E(-).1)
But in this expression, the terms have no interaction with the terms, and hence we have that for any s:
argmin
()
argmin 11,
Σ
Irli,.,))) o - 3.
B: me- +1)==
0-(-1.1)
Lemma D.4. Fix any optimal solution vig minimax problem 2. Then v/t is also an optimal solution to minimax problem I.
Proof. We first observe that minimax problem 2 is only more constrained problem for the minimization player than minimax problem I, P. C S. Thus it suffices to show that given solution &ú for minimax problem 1, we can transform it into new solution v5, such that:
1. the has support only over points in P., and
2. For all s E S, Ba [u(Se, s)] 2 Eg, [u($;,
Given ii, construct 1/2 follows: for each event E,, take all of the weight that de places points & such that E( 8) 1, and place that weight s; E Pr:
( = (i E(TE-1,21,)) 1}).
By construction dhe has support over points in Pt. It remains to show that the has objective value that is at least as high as gb. for every E S:
(u(Se. s)]
Σ Pr [E(T:-1, I', 8t) =1 E. 5)) 8t) 1]
Se
EEe 8
Σ Pr. [E(T 8:) 1).
EEE keweee
E [u($t, s)]
&
The inequality follows from Lemma D.3.
22


Reviews:
[{"review_id": "Dq1NS5U28w", "reviewer": "Reviewer_XKgH", "summary": "This paper introduces a general decision-making framework for the design of efficient algorithms with the objective of producing multi-dimensional forecasts in adversarial, sequential decision-making environments\nThe main ides is to first design a way to sequentially predict the future state of the environment, ensuring low bias across a polynomial number of conditioning events, and second to design regret-minimizing agents that essentially assume perfect knowledge of the next state.\nTherefore, the framework shifts the traditional focus from direct regret minimization to predicting a sequence of \"sufficient statistics\" of the environment, as it suffices for the agents to best-respond with respect to the predicted states.\nBy guaranteeing small cumulative bias of the state predictions, the overall regret of the agents can be bounded in a nontrivial way while guaranteeing efficiency at the same time by cleverly designing the event collection of interest for the sequential decision-making problem at hand.\nThe authors demonstrate that these almost unbiased state predictions can be used to guarantee strong conditional regret bounds, even when dealing with complex online combinatorial optimization problems and multiple agents.\nThey also show that the algorithm obtained via this framework can efficiently achieve the $T^{2/3}$ rate in online multicalibration.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nAs 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. \n\nTo summarize, our framework remains state-of-the-art, and subsequent work has used it for various interesting applications. \n\nPlease 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.", "claims_and_evidence": "The theoretical claims are clearly stated with complete proofs.\nThe authors provide a detailed description of the proposed framework and the resulting algorithms, which is well-structured and easy to follow.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "Yes, I verified the proofs in this paper and they seem correct.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The authors provide a comprehensive overview of the related prior work and discuss their contribution with respect to existing results.\nMy only concern is that the paper, as the authors explicitly state, had an extended preprint version that appeared in 2023.\nEven so, the authors are careful in pointing out that the proposed method lead to follow-up work that achieved improved results for specific sequential decision-making problems.\nHowever, there is a chance that a more recent paper could potentially already contain improved results.\nThe authors should further clarify this specific point, for instance by explicitly stating that the proposed technique is not obsolete and currently remains a main reference.", "essential_references_not_discussed": "To the best of my knowledge, the paper seems to discuss the relevant references.", "other_strengths_and_weaknesses": "I found the proposed methodology to be very interesting and the paper to be well-written.\nThe authors provide a clear and detailed description of the proposed framework and the resulting algorithms, which is well-structured and easy to follow.\nI also appreciated the instantiation of the framework to specific problems, which not only demonstrates the versatility and effectiveness of the proposed approach by deriving improved results in relevant problems, but also helps the reader in further understanding how to apply the framework to other problems.", "other_comments_or_suggestions": "- Line 223, second column: shouldn't there be some expected value since $n\\_T$ is defined as an expectation (Definition 2.2) whereas the realized predictions $\\\\hat s\\_t$ are random variables?\n- Line 247, second column: \"(1)\" seems to be superfluous.\n- Line 260, second column: the sum $\\\\sum\\_{p \\\\in [0,1]}$ is somewhat ill-defined at first glance because of the uncountable range. Then, given the term in the sum, it would be clearer (and equivalent) to have $p \\\\in \\{p\\_1, \\\\dots, p\\_T\\}$. Even just a comment would make this clear.\n- Line 271, second column: the first comma should be a period.\n- Lien 298, second column: $nK$ instead of $nd$.\n- Line 368, first column: $O(nK)$ is actually just $nK$ to be precise.\n- Line 384, second column: \"for any set\" instead of \"for any of a set\".", "questions_for_authors": "Could you clarify the relevance of the current work with respect to any potential work that extended or improved the framework since the publication of its preprint version?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Qv0HhJbxzr", "reviewer": "Reviewer_MMHe", "summary": "The paper advances sequential prediction in high-dimensional settings while maintaining unbiasedness across a possible set of events. For this, the paper utilises the multipliscale multiplicative weights with correction algorithm and the standard minmax machinery that is common in this line of work. This unbiased across a set of events prediction is then used to derive a range of other properties: like swap-regret control for downstream decision makers who will best respond to such predictions, online multi-calibration with favorable rates, and control over conditional regret in online optimisation problem.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n1. 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. \nIn 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.\n\n2. 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. \nFor 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. \nThe 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. \nWe look forward to further applications of our framework in this vein.\n\n3. 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.", "claims_and_evidence": "The paper makes convincing claims with proper evidence.", "methods_and_evaluation_criteria": "The paper is primarily theoretical, and is rigorous in that sense.", "theoretical_claims": "I haven't checked the written proofs word by word, but I do get the intuition and the argument of the proofs.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "The paper is certainly relevant on multiple fronts. While the paper does not propose significant technical tools, Algroithm 1 is based on linearising the bias objective, and then to use the standard argument of min-max theorem to control the bias, the work itself is consequential as in encapsulates a range of related yet distinct problems: for example multi-calibration in online setting with rates of $T^{2/3}$, decision-making for any polynomial number of agents---achieving such decision-making guarantee algorithmically is challenging, and conditional regret guarantees. This work unifies multiple lines of research---calibration, no-regret learning, and combinatorial optimisation---into one efficient framework that handles arbitrary polynomial-size event families.\nOverall, this is a solid paper.", "essential_references_not_discussed": "not applicable", "other_strengths_and_weaknesses": "The paper is generally well-written as is easier to follow despite being dense. As stated above, the proposed approach is general (however there are costs to generality, and I'd appreciate some discussion around that).", "other_comments_or_suggestions": "None", "questions_for_authors": "Some questions that can get some clarifications are:\n1. What are the practical limits of specifying the finite collection of events E. Are there heuristic or data-driven methods for identifying the most relevant events, especially in high-dimensional contexts? Is it feasible to adaptively add or remove events over time? I assume one can plug-in new events sequentially, or my understanding wrong?\n\n2. Related to above: guaranteeing no-swap-regret, as proposed, is based on explicitly constructing ‘best-response events’ for each agent’s utility, and knowing there are exactly n decision-makers. However, practically one might not know an agent’s utility function in advance, or there is only a partial information, plus new agents with different utilities may arrive at any time step. Could the authors discuss whether their approach can be adapted to handle unknown or changing utilities? In particular, is there a way to achieve similar no-swap-regret guarantees without having to explicitly compute best-response events for each agent ahead of time? I assume the traditional calibration (binary forecasts) result in swap-regret guarantees without any specification of the utility function?\n\n3. The paper treats each round's state $s_t$ as \"sufficient statistics\"  for\ndownstream decision-making, implicitly assuming that an agent's utility depends only on\nthese $d$ coordinates. What is the nature of the sufficient statistics: is it just high-dimensional object or encapsulates higher order moments like variance etc.?  I assume not, as the decision-maker still has the linear utility in terms of the state. So I guess I'm asking what does \"sufficient statistics\" mean in the context of the paper, as it states sufficient for all decision-makers?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "38ssl70plQ", "reviewer": "Reviewer_daBU", "summary": "This paper introduces a two-step framework for decision-making in an online adversarial setting in which a \"master\" algorithm makes predictions of vector-valued \"states\" that encode the decision-making relevant features of the environment by achieving low bias subject to a collection of conditioning events. Downstream agents may then consume those states through the a simple best-response strategy to enjoy strong regret guarantees themselves, such as online multicalibration or swap regret. The \"master\" algorithm is efficient so long as the number of conditioning events is polynomial or, in settings with combinatorially large action spaces, it has access to an optimization oracle. Crucially, the power of the master algorithm comes from properly defining a set of conditioning events, $\\mathcal{E}$, which lead to the following downstream results in the paper.\n\nThe authors show three main applications of this \"master\" algorithm (and slight variants of it):\n1. Efficient online multicalibration with $O(T^{2/3})$ rate in the expected calibration error metric.\n2. A polynomial number of downstream agents can *all* achieve diminishing swap regret by just \"best responding\" to the \"master\" algorithm.\n3. A polynomial number of downstream agents can *all* achieve diminishing \"conditional\" regret in a combinatorial optimization problem over a polynomial number of conditioning events *efficiently* given an optimization oracle for the combinatorial problem.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nWe 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})$. \n\nMeanwhile, 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.", "claims_and_evidence": "In my reading of the paper, I saw that there was one major claim in **Theorem 2.4**, which gives the bias guarantee of the \"master\" algorithm, Algorithm 1. The other claims in the paper follow from applying Theorem 2.4 in various ways by changing the events $\\mathcal{E}$ for which Algorithm 1 ensures unbiased prediction against. In particular:\n\n1. Section 2.2 shows an algorithm for achieving $O(T^{2/3})$ online (one-dimensional) multicalibration error by defining the events as the collection of groups cross the collection of discretizaiton of $[0, 1]$.\n2. Theorem 3.7 demonstrates that $n$ downstream agents with $K$ actions can simultaneously achieve diminishing $O(\\sqrt{KT})$ swap regret by best-responding to the \"master algorithm\" states, so long as the master algorithm is instantiated with the event set as a collection of $nK$ \"best-response\" events, or indicators that agent $i \\in [n]$ had best response to the state equal to action $a$ (of the $K$ actions).\n3. Theorem 4.1 demonstrates that $n$ downstream agents with combinatorial action sets granted oracle access to an offline optimization oracle playing best-response actions achieves $O(d \\sqrt{T})$ where $d$ is the number of \"base\" actions in the action sets.\n\nI checked the proofs and proof sketches that are present in the main body of the paper, and I believe they are correct.", "methods_and_evaluation_criteria": "The paper is a theoretical work in online learning, and the evaluation criteria of regret (specifically, notions such as online multicalibration and swap regret) are well established definitions in the literature. The proposed evaluation criteria make sense.", "theoretical_claims": "I checked all the proofs that were included in the main body, and they were correct in my understanding.", "experimental_designs_or_analyses": "N/A -- this paper is mainly a theoretical work.", "relation_to_broader_scientific_literature": "The key contributions of the paper are situated, in my view, in the literature in online learning, sequential decision-making, and calibration. Specifically, it follows a line of work started in [BM07] for guaranteeing online adversarial learning guarantees against a collection of *conditioning events*, originally termed \"time selection functions.\" This original work motivates the authors' focus on swap regret, a very strong regret guarantee that has further implications in algorithmic game theory and correlated equilibria. The authors also design an algorithm for the online adversarial version of multicalibration, a desideratum originally introduced for the algorithmic fairness literature by [HKRR18] (albeit in a batch/i.i.d. formulation). Finally, the work touches on the literature on optimization in combinatorially large action spaces, where the Learner is assumed to have access to an offline optimization oracle. These \"oracle-efficient\" regret guarantees follow the early work of [KV05].\n\n[BM07] Blum, Avrim, and Yishay Mansour. \"From external to internal regret.\" Journal of Machine Learning Research 8.6 (2007).\n[HKRR18] Hébert-Johnson, U., Kim, M., Reingold, O., & Rothblum, G. (2018, July). Multicalibration: Calibration for the (computationally-identifiable) masses. In International Conference on Machine Learning (pp. 1939-1948). PMLR.\n[KV05] Kalai, A., & Vempala, S. (2005). Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3), 291-307.", "essential_references_not_discussed": "To my knowledge, the authors discuss all the relevant work to the results of this paper.", "other_strengths_and_weaknesses": "**Strengths**\n- The paper is well-written and the proofs of the main theorems are organized in an easy-to-understand manner.\n- The \"Predict-then-Act\" framework the authors propose in its own right, and it presents a different model of looking at sequential decision-making that I believe is appealing and worth further investigation.\n- The techniques for proving the main results are clean and appealing. I particularly enjoyed how the arguments take a similar form to the omniprediction/outcome indistinguishability literature, in which the \"states\" the master algorithm supplies are, in effect, indistinguishable from the true states so long as the downstream decision-makers are concerned with an appropriate collection of conditioning events.\n\n**Weaknesses**\n- I believe the main weakness of this work is that the \"Predict-then-Act\" motivation for these guarantees can be muddled in the exposition. One suggestion I have would be to begin the introduction with a motivating example to make clearer this framework, as readers may be more familiar with the online learning setting where there is a single agent making actions over $T$ rounds, possibly with access to a context. This additional \"layer\" of a \"master\" algorithm producing states for *multiple* agents to consume and then act on is interesting, but I found it difficult to follow at times without referring back to a guiding example.\n- It would be helpful to present, in a more self-contained way, existing rates in the literature for the three applications you consider so the reader can disentangle and better understand the optimality of the results you propose. Perhaps a table, even in the Appendix, comparing the results to existing results in online multicalibration, swap regret, and online combinatorial optimization would be helpful.", "other_comments_or_suggestions": "A couple of small suggestions:\n- Page 4: I believe that the $w_{\\sigma, i, j}$ should have a $t$ subscript as well.\n- Page 4: I would suggest motivating the form of \"Unbiased Prediction\" in Definition 2.2 with the existing \"small-loss\" rates in case readers aren't familiar with these faster rates for regret. Or, to prevent confusion, it might be helpful to just denote \"Unbiased Prediction\" as decaying sublinearly, and then add a remark that the goal is to achieve the \"fast rate\" decay that MsMwC affords.", "questions_for_authors": "I had one main question for the authors concerning the multicalibration result:\n1. Perhaps this is from my lack of familiarity with existing rates for multicalibration, but does the $O(T^{2/3})$ rate come from the fact that the algorithm you propose enjoys the \"fast-rate\" guarantee that scales with $n_T$ which allows a sharper tuning? In the first paragraph in Section 2.2, you claim that the fast $O(\\sqrt{n_T})$ rates are useful, and I was wondering why exactly. I assumed that it was because existing methods for online multicalibration don't exploit such \"small-loss\" regret guarantees. This might also be worth clarifying in the main paper (second bullet point of \"Weaknesses\").", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vBLFNv4vVQ", "reviewer": "Reviewer_RVzC", "summary": "This paper introduces a general framework for constructing sequential decision-making strategies by predicting the states of the environment. The basic idea is that if we can estimate the *future* states of the environment, we can make decisions based on these predictions. However, the challenge is that, since the states are generated adversarially, it is not possible to predict them accurately. Nevertheless, this paper demonstrates that for many sequential decision-making problems, it suffices to construct a predictor that is *unbiased* when weighted by certain events.\n\nThe main technical contribution is a general prediction strategy that achieves low weighted bias for arbitrary events of polynomial size. The construction is based on a clever reduction to the problem of prediction with expert advice. Furthermore, the paper applies the general state prediction strategy to several concrete problems, including online multicalibration, swap regret, and online combinatorial optimization.\n\nI find the idea of reducing sequential decision-making to unbiased state estimation both interesting and original. I expect that this technique will be applicable to a broader range of problems and deserves wider recognition in the community. Therefore, I strongly recommend accepting this paper.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.", "claims_and_evidence": "The claims are clear and supported by rigorous proofs, which are sound.", "methods_and_evaluation_criteria": "This is a pure theory paper. The authors apply their method to a broad range of problems, which is convincing.", "theoretical_claims": "I checked almost all the proofs in the main text and am convinced that they are correct. However, the paper also provides many additional results in the appendix, which I did not check and therefore cannot guarantee their correctness.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper provides a general methodology for resolving sequential decision-making problems in adversarial environments, which unifies and simplifies many prior approaches.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "One complaint about the paper is that the notation is quite difficult to parse, e.g., the subscripts are messy. Moreover, it seems that the derived regret inevitably depends on the size of the decision space, which may not be applicable for large decision spaces. Although the authors provide an example in the context of online combinatorial optimization, it relies on a very specific additive property of the utility function.", "other_comments_or_suggestions": "- In line 259 (right), the definition of ECE must be $\\sup_{p\\in [0,1]}$, not $\\sum_{p\\in [0,1]}$.\n- In page 5, you use both $w_{\\sigma,i,j}^t$ and $w_{t,(\\sigma,i,j)}$, I suggest sticking to $w_{\\sigma,i,j}^t$.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper develops algorithms for predicting underlying “states” of a sequential process. These state predictions, if sufficiently accurate, can then be used by downstream algorithms to minimize stronger notions of regret such as swap regret. The state predictions are generated by a kind of online analog of moment matching. The reviewers all were impressed with the strong theoretical contributions in this paper.
Decision: Accept (oral)