Online Omniprediction with Long-Term Constraints

• URL: http://arxiv.org/abs/2509.11357v1
• Date: Sun, 14 Sep 2025 17:22:47 GMT
• Title: Online Omniprediction with Long-Term Constraints
• Authors: Yahav Bechavod, Jiuyao Lu, Aaron Roth,
• Abstract summary: We study the problem of online omniprediction with long-term constraints.<n>We show how to make a single set of predictions so that each of the downstream agents can guarantee this.<n>We also show how to extend our guarantees to arbitrary intersecting contextually defined emphsubsequences
• Score: 13.637004009810285
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce and study the problem of online omniprediction with long-term constraints. At each round, a forecaster is tasked with generating predictions for an underlying (adaptively, adversarially chosen) state that are broadcast to a collection of downstream agents, who must each choose an action. Each of the downstream agents has both a utility function mapping actions and state to utilities, and a vector-valued constraint function mapping actions and states to vector-valued costs. The utility and constraint functions can arbitrarily differ across downstream agents. Their goal is to choose actions that guarantee themselves no regret while simultaneously guaranteeing that they do not cumulatively violate the constraints across time. We show how to make a single set of predictions so that each of the downstream agents can guarantee this by acting as a simple function of the predictions, guaranteeing each of them $\tilde{O}(\sqrt{T})$ regret and $O(1)$ cumulative constraint violation. We also show how to extend our guarantees to arbitrary intersecting contextually defined \emph{subsequences}, guaranteeing each agent both regret and constraint violation bounds not just marginally, but simultaneously on each subsequence, against a benchmark set of actions simultaneously tailored to each subsequence.

Related papers

• Fundamental Novel Consistency Theory: $H$-Consistency Bounds [19.493449206135296]
  In machine learning, the loss functions optimized during training often differ from the target loss that defines task performance.<n>We present an in-depth study of the target loss estimation error relative to the surrogate loss estimation error.<n>Our analysis leads to $H$-consistency bounds, which are guarantees accounting for the hypothesis set $H$.
  arXiv  Detail & Related papers  (2025-12-28T11:02:20Z)
• Distribution-informed Online Conformal Prediction [53.674678995825666]
  We propose Conformal Optimistic Prediction (COP), an online conformal prediction algorithm incorporating underlying data pattern into the update rule.<n>COP produces tighter prediction sets when predictable pattern exists, while retaining valid coverage guarantees even when estimates are inaccurate.<n>We prove that COP can achieve valid coverage and construct shorter prediction intervals than other baselines.
  arXiv  Detail & Related papers  (2025-12-08T17:51:49Z)
• Dynamic Regret Bounds for Online Omniprediction with Long Term Constraints [13.637004009810285]
  We present an algorithm guaranteeing dynamic regret bounds for online omniprediction with long term constraints.<n>The goal in this recently introduced problem is for a learner to generate a sequence of predictions which are broadcast to a collection of downstream decision makers.<n>Within this framework, we give the first algorithm that obtains simultaneous emphdynamic regret guarantees for all of the agents.
  arXiv  Detail & Related papers  (2025-10-08T17:28:05Z)
• Core Safety Values for Provably Corrigible Agents [2.6451153531057985]
  We introduce the first implementable framework for corrigibility, with provable guarantees in multi-step, partially observed environments.<n>Our framework replaces a single reward with five *structurally separate* utility heads.<n>For open-ended settings where adversaries can modify the agent, we prove that deciding whether an arbitrary post-hack agent will ever violate corrigibility is undecidable.
  arXiv  Detail & Related papers  (2025-07-28T16:19:25Z)
• Online Fair Division for Personalized $2$-Value Instances [51.278096593080456]
  We study an online fair division setting, where goods arrive one at a time and there is a fixed set of $n$ agents.<n>Once a good appears, the value each agent has for it is revealed and it must be allocated immediately and irrevocably to one of the agents.<n>We show how to obtain worst case guarantees with respect to well-known fairness notions.
  arXiv  Detail & Related papers  (2025-05-28T09:48:16Z)
• An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
  We study Online Convex Optimization (OCO) with adversarial constraints.<n>We focus on a setting where the algorithm has access to predictions of the loss and constraint functions.<n>Our results show that we can improve the current best bounds of $ O(sqrtT) $ regret and $ tildeO(sqrtT) $ cumulative constraint violations.
  arXiv  Detail & Related papers  (2024-12-11T03:06:42Z)
• Robust Yet Efficient Conformal Prediction Sets [53.78604391939934]
  Conformal prediction (CP) can convert any model's output into prediction sets guaranteed to include the true label. We derive provably robust sets by bounding the worst-case change in conformity scores.
  arXiv  Detail & Related papers  (2024-07-12T10:59:44Z)
• On Dynamic Regret and Constraint Violations in Constrained Online Convex Optimization [17.412117389855222]
  We propose an algorithm that follows projected gradient descent over a suitably chosen set around the current action. We show that both the dynamic regret and the constraint violation is order-wise bounded by the it path-length, the sum of the distances between the consecutive optimal actions.
  arXiv  Detail & Related papers  (2023-01-24T04:22:13Z)
• Autoregressive Bandits [58.46584210388307]
  We propose a novel online learning setting, Autoregressive Bandits, in which the observed reward is governed by an autoregressive process of order $k$. We show that, under mild assumptions on the reward process, the optimal policy can be conveniently computed. We then devise a new optimistic regret minimization algorithm, namely, AutoRegressive Upper Confidence Bound (AR-UCB), that suffers sublinear regret of order $widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G
  arXiv  Detail & Related papers  (2022-12-12T21:37:36Z)
• Once-for-All Sequence Compression for Self-Supervised Speech Models [62.60723685118747]
  We introduce a once-for-all sequence compression framework for self-supervised speech models. The framework is evaluated on various tasks, showing marginal degradation compared to the fixed compressing rate variants. We also explore adaptive compressing rate learning, demonstrating the ability to select task-specific preferred frame periods without needing a grid search.
  arXiv  Detail & Related papers  (2022-11-04T09:19:13Z)
• Batch Multivalid Conformal Prediction [13.077246342082294]
  We develop fast distribution-free conformal prediction algorithms for obtaining multivalid coverage on exchangeable data in the batch setting. We give two algorithms: both take as input an arbitrary non-conformity score and an arbitrary collection of possibly intersecting groups. We evaluate the performance of both of our algorithms in an extensive set of experiments.
  arXiv  Detail & Related papers  (2022-09-30T00:18:27Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  We study online learning problems in which a decision maker has to take a sequence of decisions subject to $m$ long-term constraints. The goal is to maximize their total reward, while at the same time achieving small cumulative violation across the $T$ rounds. We present the first best-of-both-world type algorithm for this general class problems, with no-regret guarantees both in the case in which rewards and constraints are selected according to an unknown model, and in the case in which they are selected at each round by an adversary.
  arXiv  Detail & Related papers  (2022-09-15T16:59:19Z)
• Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization [24.97580261894342]
  This paper considers the distributed online convex optimization problem with time-varying constraints over a network of agents. Two algorithms with full-information and bandit feedback are proposed.
  arXiv  Detail & Related papers  (2021-05-01T18:28:53Z)
• Contract Scheduling With Predictions [12.335698325757491]
  We study the setting in which there is a potentially erroneous prediction concerning the interruption. For both settings, we investigate tradeoffs between the robustness (i.e., the worst-case performance assuming adversarial prediction) and the consistency (i.e., the performance assuming that the prediction is error-free)
  arXiv  Detail & Related papers  (2020-11-24T23:00:04Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  We study the Safe Reinforcement Learning (SRL) problem using the Constrained Markov Decision Process (CMDP) formulation. We present an provably efficient online policy optimization algorithm for CMDP with safe exploration in the function approximation setting.
  arXiv  Detail & Related papers  (2020-03-01T17:47:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.