Bandits with Anytime Knapsacks

Dear reviewer, thank you for the comments, and also for sharing this interesting reference.

In the traditional LP sense, non-degeneracy issue stipulates that there exists a unique base that solves the LP. This is generally needed for multi-dimensional costs, where a mixture of different optimal bases might not be optimal, hence switching back and forth from different optimal bases might lead to suboptimal performance. Since our problem is one-dimensional, non-degeneracy in this traditional LP sense is not needed. We still make the assumption for a single optimal base for convenience in proof, this is similar to the regular multi-armed bandit problem where the existence of a single best arm is assumed. Hence, this assumption can be relaxed.

However, we have a non-degeneracy issue from the cost gaps of the arms, which we define as the distance between $c$ and the mean cost of an arm. In our algorithm, we need to determine if the mean cost of an arm is less or greater than $c$ in order not to violate the anytime constraint (if an arm with a mean cost greater than $c$ is incorrectly identified as a low-cost arm it can lead to violating the constraint). For this, we sample the arms until their confidence interval does not include $c$, and necessitates us to assume $\delta_{\min} > 0$.

Regarding your second comment, yes, the paper can be generalized to handle multi-dimensional cost constraints. The only part that needs to be generalized is the anytime constraint, since the LP part that solves for the base can already handle multi-dimensional costs. In terms of the anytime constraint, it can easily be generalized if $\omega$ is defined based on the minimum cost gap among all dimensions, though this will not be an optimal solution and have a high regret. A more optimal solution would be to define a separate $\omega$ value for each dimension, however, this would require a more involved theoretical analysis as under-budgeting applied in one dimension also affects other dimensions by altering the frequency of arm pulls within a base. Hence, while the relaxation to multiple dimensions can simply be done by defining $\omega$ based on the minimum gap among all dimensions, we leave it as a future work to implement it more optimally.

We will add the following discussion on extension to multi-dimensional costs in the final version of the paper.

Extension to multi-dimensional costs: While we only consider one-dimensional costs in this work, this work can be extended to consider multi-dimensional costs. For such an extension, first thing that needs to be considered is generalizing the the anytime constraint to multiple dimensions. The constraint can easily be generalized if $\omega$ is the same for all dimensions, and defined based on the minimum cost gap among all dimensions. However, this will not be an optimal solution and have a high regret. A more optimal solution would be to define a separate $\omega$ value for each dimension, however, this would require a more involved theoretical analysis as under-budgeting applied in one dimension also affects other dimensions by altering the frequency of arm pulls within a base, which we leave as future work.

Another consideration is the non-degeneracy issue, where a unique optimal base is commonly assumed for problem settings with multi-dimensional costs. Relaxing this non-degeneracy assumption is considered recently in (https://arxiv.org/abs/2402.16324). They propose a novel algorithm that uses an eliminating procedure to identify the optimal base, and a resolving procedure that is adaptive to the remaining resources. A similar implementation as in this related work can be considered in our setting to prevent the need for assuming a unique optimal base in the extension to multi-dimensional costs.

4) On gap-independent (worst-case) regret

As the reviewer 8A3V pointed out, there is prior work that can achieve $O(\sqrt{KT})$ instance-independent regret in our problem setting; we have revised our paper and added the following to our prior work section:

In [1], a more general BwK formulation with long-term constraints is considered where the costs can be negative as well as positive. The long-term constraint is defined such that the total consumption of each resource at round $T$ should be less than zero up to small sublinear violations. This is again similar to this setting if we do not allow any violation of the constraint as our problem setting can be reduced to this setting again by subtracting $c$ from the costs of all arms. They show that regret is upper bounded by $O(\sqrt{KT}\log(KT))$ when the {\emph EXP3-SIX} algorithm is used with the Primal-Dual algorithm based framework that they propose for their problem setting. They also remark that initial $o(T)$ rounds can be skipped to cover the potential violations and implement the long-term constraint as a hard constraint like in our setting. However, they provide an upper bound of $O(\sqrt{KT})$ constraint violations in [2, Corollary 8.2], which suggests that the initial $O(\sqrt{KT})$ rounds would need to be skipped to achieve hard constraints, which would lead to $O(\sqrt{KT})$ gap-independent regret in our problem setting. In our work, we show that we achieve $O(K \log T)$ gap-dependent regret for the same problem setting.

[1] Bernasconi, Martino, Matteo Castiglioni, and Andrea Celli. "No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization."

As can be seen in [1], the number of constraint violations in their setting is upper bounded by $O(\sqrt{KT})$, which suggests that if their algorithm was equipped with skips to achieve the anytime constraint that we consider here, it would need $O(\sqrt{KT})$ skips, which would lead to an instance-independent regret upper bound of $O(\sqrt{KT})$. Hence, when $\omega$ is small, it is a better idea only use skips and not utilize under-budgeting. For our algorithm, we have added the following discussion to our paper:

SUAK is not optimal if the value of $\omega$ is small, i.e. if $\omega \leq 1/\log(T)$ assuming the time horizon $T$ is known. Under this case, prior work [1] can be used to achieve $O(\sqrt{KT})$ gap-independent regret in our setting.

5) Clarification on the simulations

In the first simulation, we use an instance with a high $\delta_{\min}$ value to demonstrate the design idea of our algorithm. There, $\delta_{\min}=0.25$, which leads to $\omega=0.143$. In the second simulation, $\omega=0.0625$, which leads to a higher regret for SUAK. Note that the main regret term for the One Phase algorithm is skipping, and for SUAK, it is under-budgeting. For theoretical analysis, we assume we are given an $\omega$ value. For the simulations, we used $\omega=\delta_{\min}/(2+\delta_{\min}-c)$. For the case where $\delta_{\min}$ is not known, LCB of $\delta_{\min}$ can be used in implementation to update the value of $\omega$ every round.

We updated the paper and added the $\omega$ values used in the simulations. Regarding the experiment details, with this addition we believe we have provided all the details needed to be able to replicate the experiments, as we have provided our pseudo code, and the reward and cost distributions that we use.

6) Polishing of the proof

Thank you for the comment, we have made some revisions on the proof to make it more clear. Below are responses for each of your examples.

Line 1086 - 1094: Thank you for pointing this out, we had several typos here; the correct relation is $E[N_j(t)] \geq \omega \cdot N_{(i,j)}(t)$ instead of $E[N_j(t)] \leq N_{(i,j)}(t)/ \omega$, we fixed this in the revision. We also fixed $\geq$ to $\leq$ in line 1100 due to this typo. The lines after 1100 are not affected from this mistake.

Line 1183 - 1190: We corrected the proof around this part to use an upper bound on the under-budgeting amount instead of its mean amount.

Line 1197 - 1205: We improved the proof to make it more clear.

Line 1269: We corrected the proof around this part to use the upper bound on the empirical cost instead of the mean cost. The constant term in front of the second $\log T$ term in the final regret bound increased from $194$ to $202$ as a result of this.

Dear reviewer, thank you for the comments. We are providing our responses to each of the comments below.

1) Concern on the skipping mechanism

First, thank you, we fixed '+' to '-'. The main reason we employ skipping in SUAK is to prevent violating the anytime constraint. We check for the possibility of violating the constraint in lines 4-6 in the algorithm, and skip a round if there is any such possibility. The skipping mechanism in lines 8-10 is preventative, while there is no possibility of violating the anytime constraint we skip in that round to prevent a future skip. However, since this preventative action and the action we take if there is the possibility of violating the constraint are the same (both are skipping), it does not really matter both in practice and in theory if we skip now or later. For theoretical analysis, we separately consider the pulls from lines 8-16 and the pulls from lines 18-37 and consider their skips separately. In proof, we consider lines 4-6 to be the skipping mechanism for the lines 18-37, and we consider lines 8-10 to be a separate skipping mechanism for the lines 8-16. If the lines 8-10 did not exist, then we would need to distinguish the reason for the skip which would complicate the theoretical analysis. In simulations, while we did not report it, the algorithm performs slightly better if we ignore the skipping mechanism in lines 8-10. This is as expected since if lines 8-16 consume more than $c$ average budget and the lines 18-37 consume less than the targeted budget, there is no need to skip. However, if the lines 18-37 consume its targeted budget, then there would be the need to skip in lines 4-6, however in the worst case, the skips needed will be upper bounded by the number of skips that would have been performed in lines 8-10.

We provide the relevant code blocks from the algorithm below

4. If S_c(t-1) + 1 > ct then
5.      Skip round t
6.      continue

8. If S_p(t-1) + 1 > c*N_p(t-1) then
9.      Skip round t
10.      continue

Lines 8-16: To determine if the mean cost of an arm is greater than or less than c

Lines 18-37: Solves the optimization problem and pulls an arm

I would like to thank the authors for providing detailed response. I will keep my score for now and reconsider adjusting my score if the authors can further improve their paper. Some additional comments below:

1. It is clear to me now. I think the authors should include a discussion in the paper.
2. I think the authors should include a discussion in the paper. While I now understand the setting and implementation may be different, I do not think it is fair to claim the problem in [1] is much easier to solve. The difficulty lies in different directions. Plus, in [1] they also consider the more challenging degenerate case which is not considered in this work.
3. As is also pointed out by other reviewers, the assumption is crucial and can be restrictive. I think your reasoning of knowing $\omega$ is primarily focusing on the SUAK algorithm. I know relaxing it might be difficult, but I think a thorough discussion is needed in the paper for the possibility of relaxing the assumption.

4-6. Thank you for the comments. All clear to me.

Dear reviewer, thank you for the comments and providing these existing works. We have updated our related work section in the paper with these relevant work you have provided, for your reference we have also included the changes below our response here.

Regarding your first comment, yes, it is possible to instantiate the problem with $B-O(\sqrt{T})$ initial budget, or skip the first $O(\sqrt{T})$ initial rounds and use any of the algorithms you have cited or any BwK algorithm to solve our bandits with anytime knapsacks problem. However, doing so will result in $O(\sqrt{T})$ gap-dependent or gap-independent regret as this $O(\sqrt{T})$ part of the budget is unused. Using our algorithm, we can achieve a gap-dependent regret bound on the order of $O(\log T)$. This, which is our main result, is a big improvement over this naive approach. Note that our approach will also have a gap-independent regret bound of $O(\sqrt{T})$, and since this naive approach will also have a gap-independent bound of $O(\sqrt{T})$, our algorithm does not have an improvement in this part, and hence we do not report a gap-independent bound. We also would like to note that the main idea that lets us achieve the $O(\log T)$ gap-dependent regret is under-budgeting, skipping is an extra guard-rail that we use for the case where under-budgeting fails. If skipping is not one of the optimal arms, the number of skips in our algorithm is upper bounded by $O(1)$ ($O(1)$ skips in initialization and $3 \pi^2/\delta_{\min}^2$ expected number of skips from the probability that anytime constraint might be violated even though under-budgeting is used).

Below is a copy of what we have added to the relevant works section in our paper (citation numbers follow the citation numbers in your comments):

In [3], the contextual bandits with linear constraints (CBwLC), a more generalized version of the contextual bandits with knapsacks (CBwK) problem, which allows packing and covering constraints, as well as positive and negative resource consumption, is considered. Their algorithm also works when the initial budget is $B=\Omega(T)$, or $B=o(T)$, compared to the prior work which mostly restricts the initial budget to $B=\Omega(T)$. This is similar to our setting since our problem setting can be reduced to their problem setting by implementing the budget increase as subtracting $c$ from the costs of all arms (this also makes the skip arm in our setting have negative cost $c$ and function as the resource replenishing arm). However, their algorithm is suboptimal in our problem setting with a zero initial budget, as they remark in the discussion of [3, Theorem 3.6], their proposed algorithm LagrangeCBwLC achieves optimal $O(\sqrt{KT})$ regret when the initial budget $B>\Omega(T)$; and when $B= o(T)$ its regret is suboptimal. This is as expected as they require knowing the ratio $T/B$, which goes to infinity when $B= o(T)$. In our work, we are only interested in the case where the initial budget is zero, and we consider gap-dependent results instead of the gap-independent results considered here, and we propose an algorithm that achieves an order-optimal $O(K \log T)$ gap-dependent regret bound.

In [2], a more general BwK formulation with long-term constraints is considered where the costs can be negative as well as positive. The long-term constraint is defined such that the total consumption of each resource at round $T$ should be less than zero up to small sublinear violations. This is again similar to this setting if we do not allow any violation of the constraint as our problem setting can be reduced to this setting again by subtracting $c$ from the costs of all arms. They show that regret is upper bounded by $O(\sqrt{KT}\log(KT))$ when the {\emph EXP3-SIX} algorithm is used with the Primal-Dual algorithm based framework that they propose for their problem setting. They also remark that initial $o(T)$ rounds can be skipped to cover the potential violations and implement the long-term constraint as a hard constraint like in our setting. However, they provide an upper bound of $O(\sqrt{KT})$ constraint violations in [2, Corollary 8.2], which suggests that the initial $O(\sqrt{KT})$ rounds would need to be skipped to achieve hard constraints, which would lead to $O(\sqrt{KT})$ gap-independent regret in our problem setting. In our work, we show that we achieve $O(K \log T)$ gap-dependent regret for the same problem setting.

In [1], they consider the same problem setting as in [2]. Instead of a Prior-Dual algorithm based approach, they use a UCB-based approach to optimistically estimate the constraints through a weighted empirical mean of past samples. This approach lets them provide $O(\sqrt{T})$ regret in stochastic settings without assuming Slater's condition. The upper bound on constraint violations is still $O(\sqrt{KT})$, which would again lead to a $O(\sqrt{KT})$ gap-independent regret in our problem setting.

Dear reviewer, thank you for the comments. We have updated our paper with a more through prior work section to better motivate our approach. First, we would like to note that based on the comments of Reviewer 8A3V, we have added the following to our prior work section:

In [1], a more general BwK formulation with long-term constraints is considered where the costs can be negative as well as positive. The long-term constraint is defined such that the total consumption of each resource at round $T$ should be less than zero up to small sublinear violations. This is again similar to this setting if we do not allow any violation of the constraint as our problem setting can be reduced to this setting again by subtracting $c$ from the costs of all arms. They show that regret is upper bounded by $O(\sqrt{KT}\log(KT))$ when the {\emph EXP3-SIX} algorithm is used with the Primal-Dual algorithm based framework that they propose for their problem setting. They also remark that initial $o(T)$ rounds can be skipped to cover the potential violations and implement the long-term constraint as a hard constraint like in our setting. However, they provide an upper bound of $O(\sqrt{KT})$ constraint violations in [2, Corollary 8.2], which suggests that the initial $O(\sqrt{KT})$ rounds would need to be skipped to achieve hard constraints, which would lead to $O(\sqrt{KT})$ gap-independent regret in our problem setting. In our work, we show that we achieve $O(K \log T)$ gap-dependent regret for the same problem setting.

In [2], they consider the same problem setting as in [1]. Instead of a Primal-Dual algorithm based approach, they use a UCB-based approach to optimistically estimate the constraints through a weighted empirical mean of past samples. This approach lets them provide $O(\sqrt{T})$ regret in stochastic settings without assuming Slater's condition. The upper bound on constraint violations is still $O(\sqrt{KT})$, which would again lead to a $O(\sqrt{KT})$ gap-independent regret in our problem setting.

In [3], the contextual bandits with linear constraints (CBwLC), a more generalized version of the contextual bandits with knapsacks (CBwK) problem, which allows packing and covering constraints, as well as positive and negative resource consumption, is considered. Their algorithm also works when the initial budget is $B=\Omega(T)$, or $B=o(T)$, compared to the prior work which mostly restricts the initial budget to $B=\Omega(T)$. This is similar to our setting since our problem setting can be reduced to their problem setting by implementing the budget increase as subtracting $c$ from the costs of all arms (this also makes the skip arm in our setting have negative cost $c$ and function as the resource replenishing arm). However, their algorithm is suboptimal in our problem setting with a zero initial budget, as they remark in the discussion of [3, Theorem 3.6], their proposed algorithm LagrangeCBwLC achieves optimal $O(\sqrt{KT})$ regret when the initial budget $B>\Omega(T)$; and when $B= o(T)$ its regret is suboptimal. This is as expected as they require knowing the ratio $T/B$, which goes to infinity when $B= o(T)$. In our work, we are only interested in the case where the initial budget is zero, and we consider gap-dependent results instead of the gap-independent results considered here, and we propose an algorithm that achieves an order-optimal $O(K \log T)$ gap-dependent regret bound.

[1] Bernasconi, Martino, Matteo Castiglioni, and Andrea Celli. "No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization."

[2] Bernasconi, Martino, et al. "Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints."

[3] Slivkins, Aleksandrs, Karthik Abinav Sankararaman, and Dylan J. Foster. "Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression."

As can be seen in [1], the number of constraint violations in their setting is upper bounded by $O(\sqrt{KT})$, which suggests that if their algorithm was equipped with skips to achieve the anytime constraint that we consider here, it would need $O(\sqrt{KT})$ skips, which would lead to an instance-independent regret upper bound of $O(\sqrt{KT})$. Using our algorithm, we can achieve an instance-dependent regret bound on the order of $O(\log T)$. This, which is our main result, is a big improvement over this naive approach. Note that we do not report an instance-independent bound in our paper as SUAK will also have an instance-independent regret bound of $O(\sqrt{KT})$, which is not an improvement over this naive approach. Hence, while other algorithms complemented with some modifications might also work for our problem setting, and even achieve order-optimal instance-independent regret; the novelty of our work is proposing an algorithm with an order-optimal instance-dependent regret upper bound.