Stronger Benchmarks for Prediction as a Service with Constraints

Yahav Bechavod, Jiuyao Lu, Aaron Roth
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:7195-7225, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-bechavod26a, title = {Stronger Benchmarks for Prediction as a Service with Constraints}, author = {Bechavod, Yahav and Lu, Jiuyao and Roth, Aaron}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {7195--7225}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/bechavod26a/bechavod26a.pdf}, url = {https://proceedings.mlr.press/v306/bechavod26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Stronger Benchmarks for Prediction as a Service with Constraints %A Yahav Bechavod %A Jiuyao Lu %A Aaron Roth %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-bechavod26a %I PMLR %P 7195--7225 %U https://proceedings.mlr.press/v306/bechavod26a.html %V 306 %X 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.
APA
Bechavod, Y., Lu, J. & Roth, A.. (2026). Stronger Benchmarks for Prediction as a Service with Constraints. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:7195-7225 Available from https://proceedings.mlr.press/v306/bechavod26a.html.

Related Material