提出可随时满足资源约束的强化学习算法，兼顾探索与效率。
Bandits with Anytime Knapsacks
- 用置信上界动态选择最优动作组合，自适应分配每轮预算。
- 在任意时刻均满足成本约束，且达到理论最优的 $ O(K \log T) $ 误差上界。
- 适合资源受限的实时决策场景，如在线广告投放、智能调度系统。
我们研究带任意时间背包的贝叶斯优化问题（BwAK），其中成本约束是任意时间都必须满足的，而非总预算限制。该设定带来新挑战：需在整个决策过程中持续遵守约束。为此，我们提出 SUAK 算法，利用置信上界识别最优动作混合，并在探索与利用间保持平衡。该算法会根据当前可用预算动态调整策略，当可能违反约束时跳过本轮决策。特别地，通过适度低效使用预算，减少跳过次数。我们证明，SUAK 在问题相关条件下实现与传统 BwK 框架相同的 $ O(K \log T) $ 误差上界。实验验证了其在实际场景中的有效性。
原文摘要 · Abstract (English)
We consider bandits with anytime knapsacks (BwAK), a novel version of the BwK problem where there is an \textit{anytime} cost constraint instead of a total cost budget. This problem setting introduces additional complexities as it mandates adherence to the constraint throughout the decision-making process. We propose SUAK, an algorithm that utilizes upper confidence bounds to identify the optimal mixture of arms while maintaining a balance between exploration and exploitation. SUAK is an adaptive algorithm that strategically utilizes the available budget in each round in the decision-making process and skips a round when it is possible to violate the anytime cost constraint. In particular, SUAK slightly under-utilizes the available cost budget to reduce the need for skipping rounds. We show that SUAK attains the same problem-dependent regret upper bound of $ O(K \log T)$ established in prior work under the simpler BwK framework. Finally, we provide simulations to verify the utility of SUAK in practical settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。