在数据极少时，仍能高效应对动态资源分配问题。
A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming
- 基于动态规划与对偶框架设计新重求解算法
- 资源随订单线性增长时，后悔值仅约(log n)²
- 适合资源约束强、环境多变的实时决策场景
我们研究非平稳在线线性规划（OLP）问题：共n个订单按序到达，每个订单的收益-资源消耗对为独立但未必同分布的随机向量。决策者在规划期初获得足够覆盖大部分请求的资源配额，需立即且不可撤销地决定接受或拒绝每个订单以最大化总期望收益。研究聚焦于单样本设定——仅在规划期初可获取每类分布的一个样本。提出一种融合动态规划视角与传统对偶框架的新型重求解算法。在大资源情形下（资源配额随订单数线性增长），证明该算法对广泛非平稳分布序列实现O((log n)²)的后悔界。结果表明，即使在显著环境变化与极低数据量条件下，仍可实现亚对数级后悔，弥合了平稳与真实世界波动环境之间的差距。
原文摘要 · Abstract (English)
We study nonstationary Online Linear Programming (OLP), where $n$ orders arrive sequentially with reward-resource consumption pairs that form a sequence of independent, but not necessarily identically distributed, random vectors. At the beginning of the planning horizon, the decision-maker is provided with a resource endowment that is sufficient to fulfill a significant portion of the requests. The decision-maker seeks to maximize the expected total reward by making immediate and irrevocable acceptance or rejection decisions for each order, subject to this resource endowment. We focus on the challenging single-sample setting, where only one sample from each of the $n$ distributions is available at the start of the planning horizon. We propose a novel re-solving algorithm that integrates a dynamic programming perspective with the dual-based frameworks traditionally employed in stationary environments. In the large-resource regime, where the resource endowment scales linearly with the number of orders, we prove that our algorithm achieves $O((\log n)^2)$ regret across a broad class of nonstationary distribution sequences. Our results demonstrate that polylogarithmic regret is attainable even under significant environmental shifts and minimal data availability, bridging the gap between stationary OLP and more volatile real-world resource allocation problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。