arXiv：cs.LG· Eray Can Elumar, Cem Tekin, Osman Yagan·· 13 小时前
带任意时刻背包约束的 Bandit 问题：SUAK 算法实现 O(K log T) 遗憾上界
Bandits with Anytime Knapsacks
AI 导读
研究者提出 BwAK（带任意时刻背包约束的 Bandit）问题，将 BwK 的总预算约束改为任意时刻都需满足的成本约束，并给出算法 SUAK，通过上置信界寻找最优臂组合、在可能违反约束时跳过该轮，并以略微低用预算减少跳轮次数。
正文
Abstract: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 (Strategic Under-utilization for Anytime Knapsacks), 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, where $K$ denotes the number of arms, and $T$ denotes the time horizon. We also establish an instance-dependent lower bound showing that the $O(K\log T)$ dependence is unavoidable. Finally, we show via extensive simulations that SUAK achieves considerably higher rewards than naive adaptations of BwK algorithms that do not optimize learning under anytime cost constraints.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2501.18560 [cs.LG] |
| (or arXiv:2501.18560v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2501.18560 arXiv-issued DOI via DataCite |
Submission history
From: Eray Can Elumar [view email]
[v1]
Thu, 30 Jan 2025 18:36:13 UTC (3,455 KB)
[v2]
Fri, 9 Oct 2026 04:20:36 UTC (1,235 KB)
来源：arXiv：cs.LG · arxiv.org