On Stochastic Contextual Bandits with Knapsacks in Small Budget Regime

We appreciate the reviewer’s comments and want to address your major concerns below.

• The CBwK setting without a "null action" is relevant and common in most practical settings.
  The "null action" is not always feasible in most practical applications. We list a few representative examples:

  • In a patient boarding system [R1, R2], patients arrive sequentially, and hospitals must allocate suitable medical resources (e.g., physicians or treatment facilities) to each patient. Here, a "null action" or "do nothing action" is neither suitable nor practical.
  • In a load-balancing system for a cloud platform [R3], user-submitted jobs (e.g., machine learning workloads) are distributed to servers for processing. Assigning a "null server" with zero rewards and costs is not a good choice for either users or the platform, as jobs that fail to find an available server upon arrival are blocked and ultimately lost.
  • In a recommendation platform [R4], the platform must display appropriate items to each incoming user to maximize click-through rates, where item display typically incurs a cost. A "null item" is not a good option as it would degrade both the user experience and platform profits.

  We will incorporate these examples in our revision if the reviewer considers them appropriate.

• Technical challenges and differences with respect to existing studies.
  CBwK is a challenging problem as it requires balancing reward maximization and resource consumption without prior knowledge of the context distribution (the "spend-or-save dilemma"). This challenge is particularly pronounced in settings with small budgets and without strict feasibility.

  Previous studies, such as Han et al. (2023), Slivkins et al. (2023), and Chzhen et al. (2024), rely on knowledge of the strict feasibility margin and require either an extra learning process to estimate the optimal value $\nu^*$ or a doubling trick to learn the optimal step-size for dual updates (a proxy for managing budget usage).

  Without the strict feasibility assumption or feasibility margin knowledge, it is unclear how these approaches address the "spend-or-save dilemma."

  In contrast, our algorithm is direct, single-stage, and adaptive, leveraging the initial budget information in both the primal decision domain and the dual domain through the virtual queue design. This eliminates the need for extra estimation or tuning processes, enabling effective operation even without relying on the strict feasibility assumption.

• The advantage of Lyapunov drift analysis.
  The budget consumption process is key to understanding the regret performance of CBwK. Lyapunov drift analysis is effective in analyzing this process from two perspectives:

  1. With the strict feasibility assumption, Lyapunov drift analysis establishes an upper bound on the virtual queue (a proxy for the budget consumption process) without requiring explicit knowledge of the strict feasibility margin. This sets our approach apart from existing methods, where no-regret learning techniques (e.g., Slivkins et al., 2023) and optimization-based techniques (e.g., Han et al., 2023; Chzhen et al., 2024) rely on explicit feasibility margin knowledge to bound dual updates (also proxies for the budget consumption process).
  2. Without the strict feasibility assumption, Lyapunov drift analysis, particularly using quadratic Lyapunov functions, can still provide an upper bound on the virtual queue. This might not be feasible with existing techniques, such as those by Slivkins et al. (2023), Han et al. (2023), and Chzhen et al. (2024), where the strict feasibility assumption is a requirement.

We hope that our response addresses the reviewer’s concerns and that the reviewer can re-evaluate our work. Please let us know if you have any further comments, and we will try our best to address them.

References

• [R1] Zhalechian, M., Keyvanshokooh, E., Shi, C., et al. Personalized hospital admission control: A contextual learning approach. Available at SSRN, 2020.
• [R2] Tewari, A., Murphy, S. A. From ads to interventions: Contextual bandits in mobile health. Mobile Health: Sensors, Analytic Methods, and Applications, 2017.
• [R3] Verma, A., Pedrosa, L., Korupolu, M., et al. Large-scale cluster management at Google with Borg. In Proceedings of European Conference on Computer Systems, 2015.
• [R4] Smith, B., Linden, G. Two decades of recommender systems at Amazon.com. IEEE Internet Computing, 2017.

We sincerely appreciate the reviewer’s great comments and positive evaluation of our paper. We will provide more intuition on the theoretical analysis and fix the typos in our revision. We focus on addressing your major comments as follows.

• Experiments:
  The experiments in Figure 1 of our submission suggest that our algorithm performs particularly well as the budget becomes small. We consider the same setup as in the paper but with an even smaller budget, $B = 30$, to simulate the regime $B = \Theta(T^{1/4})$, even though our theoretical results are guaranteed only for $B = \Theta(\sqrt{T})$. Recall the previous experiments with budgets $B = \{100, 600, 1000\}$ represent the budget regimes $\{\Theta(\sqrt{T}), \Theta(T^{3/4}), \Theta(T)\}$. The average cumulative rewards are summarized in the table below, where the values for $B = \{100, 600, 1000\}$ are from Figure 1. These results suggest that our algorithm adapts effectively to varying budget regimes and achieves much better performance as the budget decreases or the constraints become tight. We will include these additional results in our revision per the reviewer’s suggestion.

• The budget-aware design $V$:
  The trade-off parameter $V = b\sqrt{T}$ is budget-aware and adaptive to different budget regimes. Qualitatively, the budget-aware design of $V = b\sqrt{T}$ prompts more conservative actions, ensuring the resource is spent more carefully in the small budget regime. Removing $b$ in $V$ (i.e., $V = \sqrt{T}$) might cause the algorithm to overuse the resource, especially when the budget is small. This overuse could result in a large virtual queue, causing our algorithm to stop early and incur a large regret. Quantitatively, this is reflected in the proof of Lemma 4, where we establish the upper bound of the virtual queue. When $V = \sqrt{T}$, we would have a large virtual queue $O(\sqrt{T}/b)$ (see lines 953–969 in Section B.4.1) instead of $O(\sqrt{T})$ obtained with the budget-aware design. This eventually leads to a worse regret bound of $O((1 + \frac{\nu^*}{b^2})\sqrt{T})$ compared to the $O((1 + \frac{\nu^*}{b})\sqrt{T})$ bound with the budget-aware design.

• The terminology of "virtual queue":
  The concept of a virtual queue originates from queueing theory and is widely used in networking and operations research [R1, R2, R3]. In a real queueing system, customers arrive, receive service, and leave, with the queue capturing the carryover effect and representing the number of waiting customers. In CBwK, the term $Q_t$ represents the cumulative overuse of a resource, where the “arrival” corresponds to the current resource consumption and the “service” corresponds to the average budget. This analogy to real queue dynamics motivates the term “virtual queue.”

• Intuition behind Lemma 4 and Lemma 5:
  Lemma 4 establishes the upper bound of the virtual queue $Q_t$, which quantifies how much of the budget is overused until round $t$. Intuitively, the algorithm would stop when the resource is used up, i.e., the actual resource usage $\sum_{t=1}^{\tau} c_t \geq Q_{\tau} + \tau b \geq B$. We hope $Q_t$ is small so that our algorithm does not stop early. Lemma 4 suggests this is true, and $Q_t = O(\sqrt{T})$ holds. This translates into a lower bound on stopping time in Lemma 5.

• Potential improvements on $T^{3/4}$:
  The main challenge in improving the $T^{3/4}$ regret lies in obtaining a refined bound on the virtual queue when the strict feasibility does not hold, as this directly impacts the stopping time and the regret. To address this, we may need to redesign the budget-aware action and the virtual queue update to make the algorithm schedule the resource more effectively. From an analytical perspective, we may need to develop new Lyapunov functions that better capture the overused resource so that we can achieve a refined upper bound on it.

• Minor comments and typos:
  1, 2, 3, 4, 5, 7, 8, 9, 10, 11: We greatly appreciate your comments. We will carefully modify them in our revision.
  6: Apologies for the confusion. The definition of $\text{Regret}(x_t, a)$ first appears in Appendix, line 697. We will move it up to an earlier section where it is first referenced.
  12: Thank you for pointing out this mismatch. We cannot directly use (16). The correct way is to analyze the drift function based on the equation on line 848 by taking $a \sim \pi^*$. We will revise it.

We very much appreciate the reviewer for the constructive comments and want to address your major concerns below.

• Related works (citation numbers are from reviewer comments):
  Thank you for pointing out these related papers. We will definitely incorporate them in our revision and provide a more comprehensive overview. Specifically, we will discuss them from the perspectives of model, algorithm design, and theoretical results. For example:

  • [1] and [4] study non-monotonic/replenishable resource utilization in non-contextual bandits with knapsacks.
  • [2] studied both stochastic and adversarial bandits with constraints, where constraint violations are allowed. Adapting their algorithm to the hard-stopping setting might require additional procedures.
  • [3] was included in our initial submission, but we will provide a more detailed discussion and comparison (e.g., the strict feasibility assumption) to highlight our contribution, as you suggested.

• Technical challenges of the existing approaches:
  For CBwK (i.e., the hard-stopping setting in Corollary 5.3(c)), Slivkins et al. (2023) assume the large budget regime, which is more explicitly presented in their standalone technical report focusing on CBwK (arXiv:2211.07484v1). Slivkins et al. (2023) inherited the technique from Immorlica et al. (2022), where a large budget and strict feasibility margin are assumed.
  It remains unclear whether their technique can be extended to small-budget settings without knowledge of a strict feasibility margin or even without assuming strict feasibility.

  Other existing techniques in Han et al. (2023) and Chzhen et al. (2024) have similar issues, relying on the knowledge of strict feasibility margins to determine the key trade-off parameter (e.g., the dual variables). Without this knowledge, applying these algorithms may fail to achieve a good or sublinear regret, as it is challenging to schedule resources effectively without such key information.

  However, our algorithm only uses the initial budget information to adapt to the (small) budget regime and does not require knowledge of the strict feasibility margin or even the assumption of strict feasibility.

• Our results are meaningful in most typical and practical settings:
  Recall the regret is $O(\sqrt{T} + \frac{\nu^*}{\sqrt{b}} T^{3/4})$ without strict feasibility assumption, where the parameter $\frac{\nu^*}{\sqrt{b}}$ can be understood as a problem-dependent parameter. The typical and practical setting would have $\nu^* = \Theta(b)$ (i.e., $T\nu^* = \Theta(B)$), representing "one unit of reward earned by consuming one unit of cost." In this setting, the dominant term becomes $\frac{\nu^*}{\sqrt{b}} T^{3/4} = \sqrt{b}T^{3/4},$ which is meaningful when $B = \Omega(\sqrt{T})$.

  In an "extreme" setting where $T\nu^* = \Theta(T)$ is earned with little cost consumption ($B = \Omega(\sqrt{T})$), i.e., "one unit of reward is earned with very little ($1/\sqrt{T}$) effort," a linear regret may be unavoidable. The lower bound $\Omega((1 + \nu^*/b) \sqrt{T})$ in Chzhen et al. (2024) under the strict feasibility assumption suggests this lower bound is $\Omega(T)$ in the "extreme" setting.

  We will incorporate these discussions in our revision by explicitly representing the regret with respect to $\alpha$.

• Our adaptive design "solves" the small budget:
  When the budget varies from $\Theta(\sqrt{T})$ to $\Theta(T)$, our algorithm adapts to different budget regimes through the carefully designed trade-off parameter $V = b\sqrt{T}$ and the virtual queue updates. Intuitively, when the budget becomes smaller, $V$ prompts more conservative actions, and the budget is spent more carefully.

  With this adaptive design and refined theoretical analysis, we achieve a regret of $O(\sqrt{T} + \frac{\nu^*}{\delta b} \sqrt{T})$ with $B = \Omega(\sqrt{T})$, which is consistent with the result in the large budget regime ($\Theta(T)$) and matches the lower bound suggested in Chzhen et al. (2024). Without the strict feasibility assumption, our algorithm establishes a regret bound of $O(\sqrt{T} + \frac{\nu^*}{\sqrt{b}} T^{3/4})$.

  These bounds are meaningful in typical settings, as discussed above. We believe these results provide a relatively complete picture of BwK in the small budget regime.

We sincerely thank the reviewer for the encouraging comments. We would like to address your questions as follows (citations are consistent with our submission).

• BwK and Contextual BwK:
  The standard bandits with knapsacks (BwK) is a special case of Contextual BwK (CBwK), where no context exists, or a single/fixed context exists. CBwK is usually much more challenging because it needs to balance reward maximization and resource consumption without prior knowledge of context distribution.

  Our final results depend not on the number of contexts but on the context dimension (we apologize for not explicitly clarifying this relationship).
  This is due to two main reasons: 1) The use of learning oracles, where the learning error depends on the context dimension, and more importantly. 2) The budget-aware/adaptive design, which implicitly learns the context distribution and takes "greedy" decisions to guarantee "context-number-free" dependence.

• Technical difference with existing primal-dual approaches:
  Existing primal-dual approaches with learning oracles, such as those in Agrawal & Devanur (2016), Han et al. (2023), and Chzhen et al. (2024), rely on prior knowledge of the strict feasibility margin and often require additional steps, such as estimating the optimal value $\nu^*$ through an extra learning process or employing a doubling-trick to learn the optimal step size for dual gradient descent. These steps and information are essential for effectively utilizing resources to maximize rewards.

  However, our algorithm is direct, single-stage, and adaptive. It leverages the initial budget information only in the primal decision domain and in the dual domain through the virtual queue design. This eliminates the need for extra estimation or tuning processes, allowing our algorithm to operate effectively even without the strict feasibility assumption.

• Lower Bound in CBwK:
  The lower bound in CBwK is relatively rare in the literature. The classical lower bound for CBwK is $\Omega(\sqrt{T})$ in Agrawal & Devanur (2016), derived by reducing the problem into unconstrained contextual bandits. However, this lower bound did not capture the effect of knapsack constraints. To our knowledge, the most relevant lower bound for CBwK is from Chzhen et al. (2024). With the assumption of strict feasibility, Section 4 (or Section E) in Chzhen et al. (2024) provides a problem-dependent lower bound of $\Omega((1+ \|\boldsymbol{\lambda}_b^*\|) \sqrt{T}),$ where $\boldsymbol{\lambda}_b^*$ is the optimal dual variable with the average budget $b.$ This result implies the lower bound is $\Omega((1 + \nu^*/b) \sqrt{T})$ for CBwK according to the duality of linear programming (LP) formulation.
  Therefore, our regret bound is tight when the assumption of strict feasibility holds. However, no existing lower bounds are reported without the assumption of strict feasibility, which is a very interesting future work.

Dear Authors,

It seems that you have misunderstood my question:
"Given a learning oracle, are there any technical differences between this approach and the algorithms for standard bandits with knapsack based on UCB and primal-dual methods?"

Your response addressed the relationship between your algorithm and other primal-dual approaches that rely on a learning oracle. However, that’s not what I meant. My question refers to the many algorithms designed for BwK (the non-contextual version), many of which are based on UCB and primal-dual methods.

What I want to understand is: apart from relying on a learning oracle, what are the differences between algorithms for contextual BwK and these non-contextual BwK algorithms? Are these algorithms essentially a combination of those non-contextual BwK algorithms with a learning oracle, or do them have unique characteristics of its own?

Specifically, does the problem you are studying have a counterpart in the non-contextual BwK setting (i.e., BwK under the small budget scenario)? If so, what is the relationship between your algorithm and the algorithms for non-contextual BwK under the small budget scenario? Is your algorithm essentially a combination of those non-contextual BwK algorithms with a learning oracle, or does it have unique characteristics of its own?