No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization

We thank the reviewer for the positive feedback about our paper.

• The weak adaptivity property was used in a simplified setting in the very recent paper by Castiglioni et al. (2024). Here, the authors only study the case in which they have a single budget constraint and a single consumption constraint (ROI). However, in our paper, we have to deal with an arbitrary number of constraints. In particular, proving lemma 6.1 in this setting is far more challenging. Indeed, the multiple constraints “move” independently but affect the constraints “jointly”. This originates difficult technical challenges that we highlight in more detail in the answer to your third question.
• Some prior works, such as Balseiro et al. (2020), could, in principle, accommodate stronger benchmarks through a refinement of their analysis. However, this was not explicitly pointed out by the authors, likely due to their adherence to the conventions of the online allocation literature and its standard benchmarks. Some very recent works also highlighted this stronger benchmark (see, e.g., Bernasconi, Martino, et al. (2024)).
• The proof relies on the key observation that Lagrangian multipliers jointly affect the primal utility but evolve independently. Thus, we need to reason about the joint behavior of the Lagrangian multipliers and look at the L1 norm. In particular, our proof proceeds by contradiction: if the Lagrangian multipliers exceed a certain threshold, then they must have remained "large" for an extended period of time (Equation 3 in the appendix). Now we can exploit the scale freeness of the primal regret minimizer and its regret property with respect to the action that satisfies the constraints (Equation 4), to claim that the primal utility is large in such interval (Equation 6). However, this is in contradiction with the fact that the dual utility is also large (because of the growth of the Lagrangian multipliers, see Claim B.4). The proof of Claim B.4 is particularly involved, as it needs to analyze the separate behavior of the Lagrangian multipliers relative to different constraints. Indeed, it is possible for the $\ell_1$ norm of the multipliers to increase without having all individual components growing. This makes it nontrivial to conclude that the dual utility must have increased as well.

References:

• Castiglioni, Matteo, et al. "Online learning under budget and ROI constraints via weak adaptivity." ICML 2024
• Balseiro, Santiago, Haihao Lu, and Vahab Mirrokni. "Dual mirror descent for online allocation problems." ICML 2020
• Bernasconi, Martino, et al. "Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints." NeurIPS 2024

On the questions about the Theoretical proofs:

Thanks for taking the time to carefully read our proofs. We really appreciate the effort.

• Thanks. We meant to cite the following works:

  • At line 660: Hazan, Elad. "Introduction to online convex optimization." Foundations and Trends® in Optimization (2016).
  • At line 1100: Foster, Dylan, and Alexander Rakhlin. "Beyond ucb: Optimal and efficient contextual bandits with regression oracles." International conference on machine learning. PMLR, 2020.

• Yes, you are right; $c_2$ should be 13m.

• The confusion likely stems from our informal definition of $t_1$, which we agree could be improved upon. We will update it with the following more precise definition: $t_1$ is the largest time smaller that $t_2$ such that $\|\|\lambda_{t_1}\|\| \ge \frac{c_1}{\rho}$ and $\|\|\lambda_{t_1-1}\|\|\le \frac{c_1}{\rho}$. Therefore, $\|\|\lambda_{t_1-1}\|\|\le \frac{c_1}{\rho}$ holds by definition. Remember that the Lagrangian multipliers are initialized to $0$, and at time $t_2$ they reach $\frac{c_2}{\rho}$, which is strictly larger than $\frac{c_1}{\rho}$.

On the paper by Ding et. al (2013):

We appreciate the reviewer for bringing this paper to our attention. We will include it in our discussion of related work on the stochastic BwK model. While the paper explores a variant of the stochastic BwK model, its connection to our work is relatively limited. Several key differences set the two settings apart: their setting assumes rewards and costs are generated i.i.d., whereas we focus on algorithms that remain robust even in adversarial environments; their costs are discretized; and their regret baseline is defined with respect to the stopping time of the algorithm rather than a fixed time horizon $T$. As a result, the guarantees they achieve (i.e., a regret bound of $O(\log B)$) are not comparable to those in our setting. In particular, in the stochastic case, our framework aligns with the standard lower bound of $\Omega(\sqrt{T})$ from the (unconstrained) multi-armed bandit problem, making a direct comparison challenging.

On the competitive ratio

Thank you for raising this possible source of confusion about the competitive ratio. The issue here is primarily one of nomenclature rather than our choice of a stronger benchmark. We agree that adding further clarification in the final version will be beneficial.

The key distinction lies in the interpretation of $\rho$ in our work versus its meaning in the BwK literature. In our setting, we normalize the constraint so that costs must remain below a fixed threshold of 0, whereas in the BwK literature, the costs are constrained by a per-round budget of $\rho_{BwK}$.

To see how our approach translates to the BwK model, consider how we would redefine the costs $g_t$ to solve BwK via our framework. Specifically, we could set $g_t(x) = \frac{x^\top c_t - \rho_{BwK}}{1 - \rho_{BwK}}$. Under this transformation, playing the void (``free’’) action in the BwK setting results in $g_t(0) = \frac{-\rho_{BwK}}{1 - \rho_{BwK}} = -\rho_{Adv}$, where $\rho_{Adv}$ is what we called $\rho$ in our paper. From this, it becomes evident that our competitive ratio of $1 + 1/\rho_{Adv}$ is equivalent to $1/\rho_{BwK}$.

We thank the reviewer again for highlighting this potential source of confusion, and we will incorporate this clarification, including this short proof sketch, in the final version of the paper.

On technical contributions

Due to space constraints, we have deferred all proofs to the appendix and instead focused on providing a clear and intuitive explanation of the key ideas in the main paper. We are pleased that the reviewer appreciated our efforts to make these concepts more intuitive and accessible (especially how Example 5.2 highlights the necessity of using adaptive regret minimizers). However, we respectfully disagree with the idea that our contributions lack technical depth.

Several key components of our proof are far from straightforward. In particular, in Section 6, we discuss the self-bounding lemma, which demonstrates that the Lagrangian variables remain automatically bounded when using scale-free primal algorithms. We find the proof of the main lemma (Lemma 6.2) highly nontrivial, and we will include a sketch of the proof in the main paper using the extra page available in the camera ready. See the answer to Reviewer Ldsh for more details on the proof (that we will include in the final version of the paper).

Moreover, we believe that handling general constraints is a highly non-trivial task.Indeed, many previous works on BwK have attempted to achieve similar results under assumptions as weak as ours. However, they have only partially succeeded, addressing the problem only in the stochastic setting [1,2,3,4,5]. Removing the knowledge on the Slater parameter is both important on the practical size and interesting from a technical standpoint, even more so when it comes from the elegant idea of using adaptivity to self-bound the Lagrangian multipliers.

These results are not only technically challenging but also highly relevant as they enable significant applications. In the paper, we highlight two key examples: bandits with general constraints and the contextual bandits with linear constraints problem recently introduced by Slivkins et al. (2023b). Both models have practical implications, including applications in autobidding for first-price auctions. Given the generality of our approach, it is likely that there are additional applications we have yet to explore.

References:

[1] Agrawal, Shipra, and Nikhil R. Devanur. "Bandits with concave rewards and convex knapsacks." Proceedings of the fifteenth ACM conference on Economics and computation. 2014.

[2] Agrawal, Shipra, and Nikhil R. Devanur. "Bandits with global convex constraints and objective." Operations Research 67.5 (2019): 1486-1502.

[3] Yu, Hao, Michael Neely, and Xiaohan Wei. "Online convex optimization with stochastic constraints." Advances in Neural Information Processing Systems 30 (2017).

[4] Wei, Xiaohan, Hao Yu, and Michael J. Neely. "Online primal-dual mirror descent under stochastic constraints." Proceedings of the ACM on Measurement and Analysis of Computing Systems 4.2 (2020): 1-36.

[5] Castiglioni, Matteo, et al. "A unifying framework for online optimization with long-term constraints." Advances in Neural Information Processing Systems 35 (2022): 33589-33602.