Bandits with Replenishable Knapsacks: the Best of both Worlds

On the $B=\Omega(T)$ assumption: We do not need to assume $B=\Omega(T)$. Indeed, one of the main contributions of our paper is to show that when $B=0$ and the replenishable factor is constant, we can still achieve $O(\sqrt{T})$ regret in the stochastic setting and constant competitive ratio in the adversarial setting. Nonetheless, we agree with the reviewer that our results are meaningful only when the budget or the replenishment factor is ``large enough''. This is common to all the previous work on BwK in which the regret depends on $B/T$. We observe that this is not a limitation of our analysis but rather an intrinsic feature of the problem. Indeed, Balseiro and Gur (2019) provide a lower bound $\Omega(B/T)$ on the competitive ratio in the adversarial setting without replenishment. Hence, it is impossible to obtain a constant competitive ratio in general.

Constant budget: The observation is correct only if there is no replenishment. If the replenishment factor $\beta$ is constant, we obtain meaningful regret bounds (e.g., a $O(\sqrt{T})$ in the stochastic setting). In the extreme case when the budget is constant and there is no replenishment our theorems hold but become meaningless. However, this is fine since any algorithm fails in this setting, as it does not have enough time to learn before depleting the budget (think about the case in which the initial budget is $1$ and it is depleted at the first round if an expensive action is played). We remark that this problem is present in all the algorithms for BwK. For instance, the regret in BwK problems depends on $B/T$ (see, e.g., Castiglioni et al. (2022)) while for the case of bandits with replenishable knapsacks Kumar and Kleinberg (2022) provide a regret bound that depends on the replenishment factor (as in our work).

Regarding the assumption about the replenishment range: this is without loss of generality since we can always scale the budget, costs, and replenishments to have replenishments $\beta$ in $[-1,0]$. So it might be the case that the costs and replenishments are similar, that costs are close to 1, and the replenishments are very small, or the opposite. Our algorithm can deal with all these scenarios. As is the case in previous works, this flexibility of the model and algorithm motivates the choice of keeping the problem at a high level of abstraction without the need to focus on specific applications.

Relation with prior work: From a high-level, many studies on BwK may appear similar in their approaches, yet they differ fundamentally in their analysis. For instance, ``Online Learning with Knapsacks: the Best of Both Worlds’’ (ICML 2022) employs almost the same algorithm of Immorlica et al. (FOCS 2019). This similarity is also present in subsequent works such as Slivkins et al. (COLT 2023), Castiglioni et al. (NeurIPS 2023). The reason why all these works might look similar at first glance is that they usually present a general primal-dual template, which is then instantiated with different subroutines. The real contribution of these works, as in our case, lies in the specific subroutines and the new analysis of the framework.

We strongly believe that our techniques introduce several important innovations which distinguish them from the algorithms and analysis used in prior related works:

• Extending primal-dual methods to adversarial BwK with non-monotone resource consumption is highly non-trivial. A non-monotone constraint is more complex than monotone one, and our constraints are also hard (i.e., they must be satisfied at each round like any budget constraint). Our proofs crucially rely on the fact that the regret minimizers have sublinear regret in different sub-intervals (see proofs of Thm. 4.1 and Thm. 4.3). Most of the existing literature relies on standard regret minimization algorithms, which would prove inadequate in our setting.
• One of the key technical challenges is bounding the Lagrangian multipliers. This can be easily done in classical BwK problems (without replenishment) since a bound on the Slater’s parameter is available. Here, the replenishment factor is unknown and, therefore, the dual space cannot be bounded a priori. To circumvent this issue, we exploit no-adaptive-regret guarantees of the primal and dual regret minimizer. Dealing with such constraints requires different techniques and a new analysis, like the division of the rounds into three phases and a novel use of the dual regret minimizer with no-adaptive-regret.

We thank the Reviewer for their comments.

There is a misunderstanding. We require that the global budget constraint must be satisfied at each round, i.e., the budget cannot be negative $B_t>0$ for all $t\in [T]$. This is not the case for general (soft) constraints that can be globally violated in some rounds, i.e., $c_t<B/T$ for all $t\in[T]$. Of course the two problems are related (but not equivalent) to satisfying the per-round consumption constraint $c_t<B_0/T$ at each round.

Lower bounds: Our setting strictly generalizes the classical (i.e., without replenishment) BwK model. In this setting, the lower bound is $\Omega(\sqrt{T})$ (as in standard bandit problems without constraints) in the stochastic setting, and $1/\alpha$-competitive ratio (that in the BwK framework is equivalent to $B/T$) in this adversarial setting (see Balseiro and Gur (2019)). We match the lower bounds in both settings.

Q2: We partially agree with the reviewer. However, budget constraints cannot be violated (globally) at any round. This makes the problem harder. Moreover, we are unaware of any best-of-both-worlds algorithm working with general soft constraints and unknown Slater’s parameter.

Optimizing coefficients: Most recent research on BwK primarily focuses on theoretical characterization instead of experimental evaluations. Also for this reason, we tried to prioritize clear result presentation over constant optimization. This helps to simplify the presentation of the analysis and results of the paper which, as noticed by other reviewers, is already quite complex.

We thank the Reviewer for their comments.

Lower bounds: Our setting strictly generalizes the classical (i.e., without replenishment) BwK model. In this setting, the lower bound under stochastic inputs is $\Omega(\sqrt{T})$ (as in standard bandit problems without constraints), and $1/\alpha$-competitive ratio (that in the BwK framework is equivalent to $T/B$) in the adversarial case (see Balseiro and Gur (2019)). We match the lower bounds in both settings.

Experimental Evaluations: Most studies on BwK have focused more on theoretical contributions than on experimental evaluations. Moreover, since we are the first to study an adversarial BwK model with replenishment, we would have no previous algorithms to employ as a meaningful baseline. We observe that all the existing algorithms would fail in the case $B=0$ (existing algorithms cannot even be initialized in this case) while ours will still provide meaningful performance. Therefore, we have chosen to prioritize theoretical characterization of the problem. An experimental evaluation will certainly be valuable once there is a deeper understanding of adversarial BwK problems with replenishment and more algorithms are available in this context.

The case of $\beta=0$: When there is no replenishment, our algorithms would resemble existing ones, though not exactly the same, as they both utilize the same primal-dual structure. We remark that our approach requires more advanced regret minimizers to address the general case. This makes sense since we want to recover the optimal guarantees of previous works when $\beta=0$.

We thank the Reviewer for their comments.

The presence of negative costs makes existing algorithms ineffective for the following two reasons. First, previous algorithms have regret upper bounds that depend on the ratio $T/B$ and, therefore, these guarantees are not meaningful when $B$ is small compared to $T$ (e.g. $B=O(1)$). Our algorithm works regardless of the initial budget $B$. It might seem that extending the classical algorithm by playing the void action when required is sufficient. In our paper, we show that this is not the case. For instance, we show that regret minimizers with weakly-adaptive regret guarantees are a crucial requirement for obtaining meaningful guarantees.

Finally, it's important to note that although our algorithm and existing ones might appear similar due to their use of a primal-dual framework, the underlying analysis differs significantly. For example, our analysis divides the rounds into 3 separate phases, and our proofs crucially rely on the fact that the regret minimizers that we use are weakly adaptive and have sublinear regret in different sub-intervals (see the proofs of Theorem 4.1 and Theorem 4.3). Most existing literature relies on standard regret minimization algorithms, which would prove inadequate in this particular scenario.