一篇论文提出统一预测方法，让多个下游代理在长期约束下实现低后悔与零累积违规。
Online Omniprediction with Long-Term Constraints
- 设计统一预测机制，使各代理仅需根据预测做简单决策
- 保证每个代理的后悔值为˜O(√T)，累计约束违规为O(1)
- 适用于多代理、异构目标与子序列场景，适合系统级优化研究者
我们提出并研究在线全能预测与长期约束问题。每轮中，预测者需对一个自适应或对抗性选择的状态生成预测，并广播给多个下游代理，每个代理根据自身效用函数和向量约束函数选择行动。各代理的目标是保证自身无后悔，同时避免累计违反约束。我们证明，通过单一预测集，每个代理可基于预测做出简单决策，实现˜O(√T)的后悔上界与O(1)的累计约束违规。进一步，我们扩展至任意交叠的上下文定义子序列，确保每个代理在每个子序列上同时满足后悔与约束违规的可调基准，且基准针对子序列独立优化。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。