Dynamic Regret Bounds for Online Omniprediction with Long Term Constraints

• URL: http://arxiv.org/abs/2510.07266v1
• Date: Wed, 08 Oct 2025 17:28:05 GMT
• Title: Dynamic Regret Bounds for Online Omniprediction with Long Term Constraints
• Authors: Yahav Bechavod, Jiuyao Lu, Aaron Roth,
• Abstract summary: 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.
• Score: 13.637004009810285
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present an algorithm guaranteeing dynamic regret bounds for online omniprediction with long term constraints. 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. Each decision maker has their own utility function, as well as a vector of constraint functions, each mapping their actions and an adversarially selected state to reward or constraint violation terms. The downstream decision makers select actions "as if" the state predictions are correct, and the goal of the learner is to produce predictions such that all downstream decision makers choose actions that give them worst-case utility guarantees while minimizing worst-case constraint violation. Within this framework, we give the first algorithm that obtains simultaneous \emph{dynamic regret} guarantees for all of the agents -- 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. Our results do not require the agents themselves to maintain any state -- they only solve one-round constrained optimization problems defined by the prediction made at that round.

Related papers

• Sample-Efficient Omniprediction for Proper Losses [7.615840544913577]
  We consider the problem of constructing probabilistic predictions that lead to accurate decisions when employed by downstream users to inform actions.<n>For a single decision maker, designing an optimal predictor is equivalent to minimizing a proper loss function corresponding to the negative utility of that individual.<n>For multiple decision makers, our problem can be viewed as a variant of omniprediction in which the goal is to design a single predictor that simultaneously minimizes multiple losses.
  arXiv  Detail & Related papers  (2025-10-14T17:49:05Z)
• Online Omniprediction with Long-Term Constraints [13.637004009810285]
  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
  arXiv  Detail & Related papers  (2025-09-14T17:22:47Z)
• A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding [68.43987626137512]
  We propose a principled framework for randomized decision-making based on interval estimates of the quality of each item.<n>We introduce MERIT, an optimization-based method that maximizes the worst-case expected number of top candidates selected.<n>We prove that MERIT satisfies desirable axiomatic properties not guaranteed by existing approaches.
  arXiv  Detail & Related papers  (2025-06-23T19:59:30Z)
• Online Decision Mediation [72.80902932543474]
  Consider learning a decision support assistant to serve as an intermediary between (oracle) expert behavior and (imperfect) human behavior. In clinical diagnosis, fully-autonomous machine behavior is often beyond ethical affordances.
  arXiv  Detail & Related papers  (2023-10-28T05:59:43Z)
• High-Dimensional Prediction for Sequential Decision Making [9.684829814477526]
  We study the problem of making predictions of an adversarially chosen high-dimensional state that are unbiased subject to an arbitrary collection of conditioning events. We give efficient algorithms for solving this problem, as well as a number of applications that stem from choosing an appropriate set of conditioning events.
  arXiv  Detail & Related papers  (2023-10-26T17:59:32Z)
• 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)
• 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)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty [87.81197574939355]
  We study the nature of both the optimization and learning problems. We provide an algorithm, namely GCB, guaranteeing sublinear regret at the cost of a potentially linear number of constraints violations. More interestingly, we provide an algorithm, namely GCB_safe(psi,phi), guaranteeing both sublinear pseudo-regret and safety w.h.p. at the cost of accepting tolerances psi and phi.
  arXiv  Detail & Related papers  (2022-01-18T17:24:20Z)
• 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)
• Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games [102.23975166536326]
  Tree-form sequential decision making (TFSDM) extends classical one-shot decision making by modeling tree-form interactions between an agent and a potentially adversarial environment. It captures the online decision-making problems that each player faces in an extensive-form game, as well as Markov decision processes and partially-observable Markov decision processes where the agent conditions on observed history. In this paper, we give the first algorithm for the bandit linear optimization problem for dilatedDM that offers both (i) linear-time losses and (ii) $O(sqrtT)$ cumulative regret in
  arXiv  Detail & Related papers  (2021-03-08T05:00:13Z)

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.