arXiv:2607.02196cs.LG2026-07被引 1

提出在线资源分配新方法,突破传统退化情况下的性能瓶颈。

Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy

  • 基于请求类型与价值密度的动态决策机制,处理连续消费分布。
  • 当参数p>1时,后悔上界为T^(1/2−1/(2p)),p=2时可实现o(√T) regret。
  • 适用于资源分配中存在退化或解不唯一的情形,适合算法设计者参考。

研究在奖励与消耗量均连续分布下的在线资源分配问题。请求按序到达,需不可撤销地决定接受或拒绝,受限于固定资源容量。每类请求属于有限可观测类型;给定类型后,奖励和标量消耗量为随机变量,实际消耗量按固定类型相关的资源消耗向量缩放。该模型允许确定性流松弛退化。我们发现,加性后悔由位于活跃接受阈值附近的请求的价值-尺寸比质量加权决定。通过主动加权质量指数p形式化该量:当p > 1时,该质量稀疏,问题本质困难——任何在线策略至少需承受阶为T^{1/2−1/(2p)}的后悔,对所有p > 1成立。一个样本路径边际策略在多对数因子内达到此下界;当p = 1时,其后悔为O((log T)^2)。例如,若尺寸与价值密度独立且均匀分布,则p = 1;若尺寸与奖励独立且均匀分布,则p = 2。因此,该策略在整个正则类中实现o(√T)后悔,无需流非退化假设,同时容忍原始退化与对偶不唯一性。

原文摘要 · Abstract (English)

We study online resource allocation when both rewards and consumption sizes may be continuously distributed. Requests arrive sequentially and must be accepted or rejected irrevocably under fixed resource capacities. Each request belongs to one of finitely many observable types; conditional on an observable request type, both the reward and the scalar size are random, and the realized size scales a fixed type-specific resource-consumption vector. The model allows the deterministic fluid relaxation to be degenerate. We show that additive regret is governed by the size-weighted mass of requests whose value-to-size ratios lie near the active acceptance cutoffs. We formalize this quantity through an active weighted-mass exponent p. When p > 1, this cutoff mass is thin, and the problem is genuinely hard: every online policy must incur regret of order at least $T^{1/2 - 1/(2p)}$, and this holds for every p > 1. A sample-path marginal policy matches this lower bound up to polylogarithmic factors; and when p = 1, so that the mass grows linearly near the cutoff, it attains $O((\log T)^2)$ regret. For example, if the size and the value-to-size ratio are independent and uniformly distributed, then p = 1; if instead the size and the reward are independent and uniformly distributed, then p = 2. Thus the policy achieves $o(\sqrt{T})$ regret throughout this regularity class without any fluid non-degeneracy assumption, allowing both primal degeneracy and dual non-uniqueness.

资源分配在线学习后悔分析退化问题

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。