Stronger Benchmarks for Prediction as a Service with Constraints

We study a learner who sequentially makes and broadcasts predictions of some underlying adversarially varying state. Many downstream decision makers with different goals and different long-term constraints consume these decisions to choose actions. In this setting we give the first algorithm that obtains simultaneous dynamic regret guarantees for all of the decision makers --- where regret for each agent is measured against a potentially changing sequence of actions across rounds of interaction, while also ensuring vanishing constraint violation for each agent. We can promise these dynamic regret bounds not just marginally, but simultaneously on many different intersecting subsequences, which lets decision makers compete with strategies that adapt with both long-term drift and short-term variation. Our results do not require the decision makers to maintain any state, but just to react myopically to our predictions.

Imagine one forecasting service, say of electricity prices, whose predictions are used at once by households, factories, and hospitals. Each has its own goals and its own hard rules, like a hospital that can never lose power. The challenge is making a single stream of forecasts everyone can trust and act on, even as conditions shift and what counts as a safe choice keeps changing. We designed a method that lets every decision maker simply treat our predictions as true, react in the moment, and still be guaranteed good long-term outcomes while keeping rule violations negligible over time. These guarantees hold not just on average, but across many different time windows, even ones that overlap, such as stormy days that fall on weekends. This means one shared forecaster can safely serve many users with different goals and rules, without anyone tracking complicated histories.