Bandits with Anytime Knapsacks
Eray Can Elumar, Cem Tekin, Osman Yağan · 2025
Read Bandits with Anytime Knapsacks by Eray Can Elumar, Cem Tekin, Osman Yağan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18560.txt.
Introduction
Eray Can Elumar, Cem Tekin, and Osman Yağan study online decision making where a cost limit must hold at every moment, not just on average by the end. In this bandit problem, each choice earns rewards and spends from a budget that can never be breached mid stream. Their 2025 algorithm, SUAK, uses confidence bounds to find the best mix of options while slightly under spending on purpose.
Holding a small reserve cuts how often rounds must be skipped for safety. The authors prove the method reaches the same regret rate known for the easier total budget version, and prove that rate cannot be beaten in general. Simulations show SUAK earning far more than plain adaptations of older budget algorithms.
Catalog record
| CREATOR | Eray Can Elumar, Cem Tekin, Osman Yağan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 103 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-18560
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bandits with Anytime Knapsacks Eray Can Elumar, Cem Tekin, Osman Yağan Abstract We consider bandits with anytime knapsacks (BwAK), a novel version of the BwK problem where there is an 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 ) O(K\log T) established in prior work under the simpler BwK framework, where K K denotes the number of arms, and T T denotes the time horizon. We also establish an instance-dependent lower bound showing that the O ( K log T ) 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. 1 Introduction Multi-armed bandits (MAB) is one of the fundamental problems in the field of sequential decision-making under uncertainty. In its essence, it is a problem setting where an agent must strategically allocate resources among the arms to maximize cumulative reward over time, navigating the trade-off between gathering information about uncertain arms (exploration) and exploiting known information to optimize immediate rewards (exploitation). This problem finds applications across diverse domains, including reinforcement learning ( Intayoad et al., 2020 ) , online advertising ( Slivkins, 2013 ) , clinical trials ( Villar et al., 2015 ) , and resource allocation ( Soare, 2015 ) . The Bandits with Knapsacks (BwK) problem, introduced by Badanidiyuru et al. (2013) , is an extension of the classical multi-armed bandit problem, with the additional constraint of limited resource capacity akin to the knapsack problem ( Tran-Thanh et al., 2012 ) . In this scenario, an agent is confronted with a set of arms, each associated with an unknown reward and cost distribution. Unlike the traditional bandit setting, selecting an arm incurs both a reward and a cost here, and the objective is to maximize the total reward while respecting the total capacity constraint of the knapsack. The BwK problem encapsulates the trade-off between exploration and exploitation while managing resource constraints, presenting a rich framework with applications such as online advertising ( Avadhanula et al., 2021 ; Badanidiyuru et al., 2018 ) , dynamic resource allocation ( Kumar and Kleinberg, 2022 ) , and personalized recommendations ( Yu et al., 2016 ) . In this paper, we consider a specific variant of this problem, which we call the bandits with anytime knapsacks (BwAK) problem, where instead of a total cost budget there is an anytime constraint on the average cost. This problem setting introduces an additional level of complexity as a mixture strategy needs to be employed to be able to pull arms with mean costs higher than the average cost budget without violating the anytime constraint. 1.1 Limitations of the State-of-the-Art Standard BwK algorithms are designed for a total resource budget over the horizon. A policy can satisfy a budget cT even if its early consumption exceeds rate c , provided that its terminal consumption remains within the total budget. BwAK instead requires S_{c}(t)\leq ct,\qquad\forall t\geq 1, where S_{c}(t) is the cumulative realized cost through round t . Hence a policy that is feasible under the standard BwK criterion can violate the BwAK constraint at an intermediate round. At round t , the learner can use only the accumulated budget slack ct-S_{c}(t) . Existing BwK algorithms use, among other approaches, optimistic estimates of the reward–cost optimization problem, primal–dual resource prices, or allocations based on the remaining budget and horizon; these methods are reviewed in § 2.1 . None of these approaches, without an additional feasibility mechanism, guarantees the prefix-wise constraint above for every realized cost sequence ( Badanidiyuru et al., 2013 ; Agrawal and Devanur, 2014 ; Flajolet and Jaillet, 2015 ; Li et al., 2021 ) . A natural adaptation to overcome this is to pull the arm selected by a BwK rule only when that pull cannot violate the current prefix constraint and to pull the null arm otherwise. This enforces feasibility, but the underlying BwK rule is not designed to accumulate budget slack for future high-cost pulls. It can therefore remain close to the constraint boundary, increasing the number of null-arm pulls imposed by this feasibility check. We introduce a baseline, Safe-Skip BwK (SS-BwK) , in § 3.1 ; it applies this feasibility check to a standard BwK decision rule. The simulations show that this direct adaptation can incur more regret from null-arm pulls than a policy that considers the anytime constraint when deciding which arm to pull. 1.2 On the Importance of Anytime Constraints The formulation of the anytime constraint considered here has broad applications across various fields. A notable example is inventory management, where a factory produces goods at a constant rate and seeks to maximize revenue by selling to buyers in a marketplace, where bids consisting of price and order size are placed. Our anytime constraint is especially relevant in such scenarios since having a negative inventory is not possible. An important aspect of this constraint is that it introduces the trade-off between exploiting the available inventory, and skipping a round to accumulate more inventory in order to capture bids with higher order sizes. This highlights the added complexity of our problem setting and underscores its broader applicability in settings beyond the standard BwK framework. Another example is in clinical trials, where drugs or treatment plans with unknown costs, which can be side effects; and rewards, which can model treatment efficacy; need to be evaluated. This example can be modeled using the anytime constraint if participants are recruited to the trials at a constant rate per week, and are not allowed to trial more than one drug. In online advertising, an advertiser may have a daily budget limit to prevent overspending. In this context, the ‘arms’ represent different ad campaigns or strategies, each with varying costs that can be selected for the day. The reward can be modeled as the daily revenue generated from clicks or the number of users who subscribe. One last example is in satellite systems, where solar panels generate energy and excess energy can be stored in a battery. Here, c can correspond to the energy generated per unit time, and arms can correspond to different tasks that need to be performed, with their rewards reflecting the importance of the tasks. The cost of an arm then represents the energy needed for the task. 1.3 Contributions 1. SUAK Algorithm: SUAK utilizes the upper confidence bounds to explore the optimal base that solves the problem, and also strategically under-utilizes the available budget to limit the