在资源受限的动态环境中,只需一个支出计划就能实现近似最优决策。
No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!
- 用预设的支出计划指导资源分配,构建可适应变化的在线决策框架。
- 算法在遵循支出计划时达到次线性遗憾,性能随预算分布均衡而提升。
- 适用于需要长期资源管理的场景,如广告投放、金融投资等。
我们研究在资源约束下的在线决策问题,其中收益和成本函数可能随时间以对抗方式变化。重点关注两种典型设置:(i) 在动作选择前观测到收益与成本的在线资源分配;(ii) 在动作选择后观测收益与成本的在线学习,支持完整反馈或弱反馈。已知在收益与成本分布任意变化的情况下,实现次线性遗憾是不可能的。为此,我们分析一种由支出计划引导的学习框架——该计划为各轮预设预期资源使用量。我们设计了通用的(原语)对偶方法,在与遵循该支出计划的基准竞争时实现了次线性遗憾。关键在于,当支出计划使预算在各轮间分布均衡时,算法性能更优。此外,我们还提出了鲁棒变体以应对支出计划严重失衡的最坏情况。最后,我们研究了算法在与偏离预定支出计划的基准比较时的遗憾表现。
原文摘要 · Abstract (English)
We study online decision making problems under resource constraints, where both reward and cost functions are drawn from distributions that may change adversarially over time. We focus on two canonical settings: $(i)$ online resource allocation where rewards and costs are observed before action selection, and $(ii)$ online learning with resource constraints where they are observed after action selection, under full feedback or bandit feedback. It is well known that achieving sublinear regret in these settings is impossible when reward and cost distributions may change arbitrarily over time. To address this challenge, we analyze a framework in which the learner is guided by a spending plan--a sequence prescribing expected resource usage across rounds. We design general (primal-)dual methods that achieve sublinear regret with respect to baselines that follow the spending plan. Crucially, the performance of our algorithms improves when the spending plan ensures a well-balanced distribution of the budget across rounds. We additionally provide a robust variant of our methods to handle worst-case scenarios where the spending plan is highly imbalanced. To conclude, we study the regret of our algorithms when competing against benchmarks that deviate from the prescribed spending plan.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。