仅用每期一个样本,实现非平稳环境下的多资源动态分配。
Non-Stationary Online Resource Allocation: Learning from a Single Sample
- 基于类型分层的分位数元策略,分离估计、优化与决策模块。
- 在有奖励信息样本下达到$ ilde{O}( oot orom o T)$后悔率。
- 无奖励信息时首次实现$( ext{log} hinspace T)^3$的对数后悔,适合数据稀缺场景。
研究在非平稳需求下,仅需每期一个历史样本的在线资源分配问题。决策者需在有限周期内,将多种资源分配给陆续到来的查询。每个查询属于有限类型,具有固定资源消耗和来自未知类型专属分布的随机收益。环境存在任意非平稳性——到达分布可能不可预测地变化,但算法只需每期一个样本即可有效运行。区分两类样本:(i) 包含查询类型与收益实现的收益可观测样本;(ii) 仅提供查询类型信息的类型仅知样本。提出一种新型类型依赖的分位数元策略,将问题解耦为收益分布估计、通过流松弛优化目标服务概率、以及通过动态接受阈值进行实时决策。对于收益可观测样本,静态阈值策略达到$ ilde{O}( oot orom o T)$后悔率。对于类型仅知样本,首先证明在无额外结构下子线性后悔不可能;在最小到达概率假设下,设计出部分自适应策略,达到相同$ ilde{O}(T)$边界,并进一步提出全自适应可调节策略,首次实现非平稳多资源分配的多项式对数后悔$O(( ext{log} hinspace T)^3)$。该框架在最小离线数据(每期一样本)、无需变差预算假设、支持多资源约束方面优于已有工作。
原文摘要 · Abstract (English)
We study online resource allocation under non-stationary demand with a minimum offline data requirement. In this problem, a decision-maker must allocate multiple types of resources to sequentially arriving queries over a finite horizon. Each query belongs to a finite set of types with fixed resource consumption and a stochastic reward drawn from an unknown, type-specific distribution. Critically, the environment exhibits arbitrary non-stationarity -- arrival distributions may shift unpredictably-while the algorithm requires only one historical sample per period to operate effectively. We distinguish two settings based on sample informativeness: (i) reward-observed samples containing both query type and reward realization, and (ii) the more challenging type-only samples revealing only query type information. We propose a novel type-dependent quantile-based meta-policy that decouples the problem into modular components: reward distribution estimation, optimization of target service probabilities via fluid relaxation, and real-time decisions through dynamic acceptance thresholds. For reward-observed samples, our static threshold policy achieves $\tilde{O}(\sqrt{T})$ regret. For type-only samples, we first establish that sublinear regret is impossible without additional structure; under a mild minimum-arrival-probability assumption, we design both a partially adaptive policy attaining the same $\tilde{O}({T})$ bound and, more significantly, a fully adaptive resolving policy with careful rounding that achieves the first poly-logarithmic regret guarantee of $O((\log T)^3)$ for non-stationary multi-resource allocation. Our framework advances prior work by operating with minimal offline data (one sample per period), handling arbitrary non-stationarity without variation-budget assumptions, and supporting multiple resource constraints.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。