On Stochastic Contextual Bandits with Knapsacks in Small Budget Regime
Authors: Hengquan Guo
Xin Liu
Venue: ICLR 2025 Poster (2025)
Keywords: Contextual bandits with knapsacks
small budget
Primary area: optimization

Abstract: This paper studies stochastic contextual bandits with knapsack constraints (CBwK), where a learner observes a context, takes an action, receives a reward, and incurs a vector of costs at every round. The learner aims to maximize the cumulative rewards across $T$ rounds under the knapsack constraints with an initial budget of $B$. We study CBwK in the small budget regime where the budget $B = \Omega(\sqrt{T})$
and propose an Adaptive and Universal Primal--Dual algorithm (AUPD) that achieves strong regret performance: 
i) AUPD achieves $\tilde{O}((1 + \frac{\nu^*}{\delta b})\sqrt{T})$ regret under the strict feasibility assumption without any prior information, matching the best-known bounds;
ii) AUPD achieves $\tilde{O}(\sqrt{T}+ \frac{\nu^*}{\sqrt{b}}T^{\frac{3}{4}})$ regret without strict feasibility assumption, 
which, to the best of our knowledge, is the first result in the literature. Here, the parameter $\nu^*$ represents the optimal average reward; $b=B/T$ is the average budget and $\delta b$ is the feasibility/safety margin.
We establish these strong results through the adaptive budget-aware design, which effectively balances reward maximization and budget consumption. We provide a new perspective on analyzing budget consumption using the Lyapunov drift method, along with a refined analysis of its cumulative variance. Our theory is further supported by experiments conducted on a large-scale dataset.

Published as a conference paper at ICLR 2025
ON STOCHASTIC CONTEXTUAL BANDITS WITH KNAP- SACKS IN SMALL BUDGET REGIME
Hengquan Guo and Xin Liu"
School of Information Science and Technology
ShanghaiTTcch University
(guohq, liuxin7] @ehanghaitae ttch.. .dd.ccn
ABSTRACT
This paper studies stochastic contextual bandits with knapsack constraints (CBwK), where learner observes a context, takes an action, receives reward, and incurs a vector of costs at every round. The learner aims to maximize the cumulative rewards across T rounds under the knapsack constraints with an initial budget of B. [2( and
We study CBwK in the small budget regime where the budget propose an Adaptive and Universal Primal- Dual algorithm (AUPD) that achieves strong regret performance: 1) AUPD achieves Õ((1
* VV) regret under the 56
strict feasibility assumption without any prior information, matching the best- known bounds: 2) AUPD achieves Ö(VT+ ~*
v6 T² regret without strict feasibility assumption, which, to the best of our knowledge, the first result in the litera- ture. Here, the parameter 2** represents the optimal average reward; b = B/T is the average budget and 8b is the feasibility/safety margin. We establish these strong results through the adaptive budget- aware design, which effectively balances reward maximization and budget consumption. We provide a new perspective analyzing budget consumption using the Lyapunov drift method, along with a refined analysis of its cumulative variance. Our theory is further supported by experiments conducted on large-scale dataset.
INTRODUCTION
Stochastic contextual bandits with knapsacks (CBwK) a general framework for online decision- making under resource-constrained applications and has been applied to broad range of practical scenarios (e.g., resource-consstriiee recommendation Balakrishnan et al. (2018); Yang et al. (2020), clinic trials in healthcare Tewari & Murphy (2017); Tomkins et al. (202T content moderation for
[ Lee et al. (2024). online advertisement platform Lucier al. (2024) Feng et al.) | (2024); Gaitonde al. (2022) ). At each round t, the learner observes context Jy X and chooses an action E A. The learner then receives a reward R2 and also consumes types of resources or costs C. The initial budget of the ktth type of resource is B3 and let B min; B& and its average version be b B/T. The interaction with the environment stops after 7 rounds or when one of the resource budgets has been exhausted. The goal the learner is to maximize the cumulative reward under the constrained resource budget.
healthy social platform Lykouris & Weng (222))
CBwK contextual version of BwK, initially introduced the literature Agrawal & Devanur (2014); Badanidiyuru al. (0018) 3) and has been extensively studied in Slivkins et al. (2023); y A Agrawal
& Devanur (2016); Han et al. (2023); ; [hzzhen et al. (2024). The work Slivkins et al. (2023) assumes online learning oracles accessed to estimate the rewards and costs and leverages inverse gap weighting method Abe & Long (199)); Foster & Rakhlin (2020) to balance exploration, reward acquisition, and cost consumption. However, this work assumes a large initial budget (or large budget regime) such that B = S(T'). In many real-world applications, the budget is precious and scarce (i.e., B < T). For example, store with a limited supply of B items of product provides customized offers to T users in contextual dynamic pricing. Users arrive sequentially with different contexts, and the number of users much larger than the number of items, i... B < T; In task
"Corresponding author

---

Published as a conference paper at ICLR 2025
scheduling for the crowdsourcing platform, the tasks with different contexts arrive sequentially, and the platform decides if a task is good to assign to an expert or an ordinary worker. In this setting, the number of experts is much smaller than the number of tasks; In content moderation for healthy online review platforms, reviews are constantly posted on the platform, and the platform is required to filter out harmful reviews within limited number of queries from human experts, where the query budget is much smaller than the number of reviews.
To solve problems with limited total budgets, the work Agrawal & Devanur (2016); Han al. (2023) studied CBwK under either linear or general realizability assumptions on rewards/costs and attempt to relax the large budget requirement. However, these work still assume B = ((T+)) due to the proposed two-stage strategies where an initial warm-up stage with vT rounds is required in learning the optimal value for the subsequent decision-making. A very recent work Chzhen et al. (2024) further relaxed the budget requirement of ((VT) by assuming the strict feasibility assumption (a.k.a the Slater's s condition) and the prior knowledge of the feasibility/safety margin. However, obtaining such information can be quite (if not impossible) challenging in real-world scenarios. Besides, the work utilizes double-tricking to learn the optimal stepsize in tracking the dual variable (the proxy for budget consumption) to achieve good balance between rewards and resource consumption, which shares a similar flavor the two-stage approach in AAgraall & Devanur (2016); Han et al.) (023). This raises a natural open question:
Can we design an adaptive (ideally single-stage) algorithm solve CBwK under the small budget B (D(T)), achieving the universal and optimal performance regardless of the strict feasibility assumption and any prior knowledge about it?
In this paper, we provide positive answer to this question by introducing the Adaptive and Universal Primal-Dus -ual algorithm (AUPD). Our contributions can be summarized as follows:
Algorithm: AUPD is motivated by the primal-dual approach which has also been widely explored in safe online learning Yu & Neely (2000); [Slivkins et al. (2023); Guo & Liu (202)): [Gangrade et al. (2024), but with adaptive budget-aware design and novel perspective from Lyapunov optimization. In the dual modular, we design the virtual queues {Q (*)) ). resemble scaled dual variables, to track the
cumulative over-used budget consumption. Unlike previous studies in [Agrwwal & Devanur (2016);
Han et al. (003); ;; [Chzhen et al.] (2024), we do not impose any upper bound or any conservative factors in the dual update. In the primal decision modular, we explicitly incorporate the knowledge of the initial budget V = byT, in addition to the virtual queues that capture the over-used resource, to balance the reward and resource consumption. The scaled virtual queues (Q{²²) /V3 can be regarded as the estimators of the optimal dual variables, which avoids an explicit learning process used in Agrawal & Devanur (0066); Han et al. (203)); Chzhen et al. 2024).. The budget-aware strategy and virtual queue design are the keys for AUPD to minimize regret and establish strong theoretical
performance under the small budget regime without any prior information on the problem instance.
Reference
Regret
Budget
Striet Feasibility
SquareCBwk Han et al.
2023
Õ((1 + )VT)
2((+))
Required and known safery margin
PGD Adaptive Chzhen et al.
2024
Õ(11 + IVT)
9(vT)
Required and known safety margin
AUPD
Õ((1 55 (TT
((VT)
Required
AUPD
Ó(VT + -VT++++) +
((VT)
Not Required
Table 1: Our results and most related works.
Theoretical Results: AUPD achieves the strong regret performance for CBwK in the small budget regime, regardless of the strict feasibility assumption (our results and most related work are summa- e* VT) rized in Table (i) When the strict feasibility assumption holds, AUPD achieves Ō((1 + 86
in the small budget regime B = 22( (T( regret under the general realizability assumption of reward and cost functions, where the parameter y is the average performance of an optimal static policy and 8b is the feasibility/ssfety margin. This result matches the regret guarantee in Agrawal & Devanur (2016); Han et al. (2023): Chzhen et al. (2024). However, unlike in Agrawal & Devanur (2016); Han et al. (2023) y Chzhen et al. (2024), Lyapunov drift analysis establishes upper bound on the virtual queue (a proxy for the budget consumption process) without requiring any prior knowledge
of the safety margin nor the extra implement parameter search steps. (ii) When the strict feasibility
2

---

Published as a conference paper at ICLR 2025
<b assumption does not hold, AUPD achieves worst-case regret of Ö( ( ) in the small budget
regime B 92( (T) To the best of our knowledge, there are existing results even in the large budget regime B = (T( without the strict feasibility assumption.
Experiments: We evaluate AUPD using real-world learning-to-rar to-rank dataset in the small budget regime. Our experimental results demonstrate that AUPD outperforms baseline algorithms and achieves the best performance under various initial budgets.
RELATED WORK
Contextual bandits and bandits with knapsacks have been studied extensively. We only focus on the literature most related to ours.
(Contextual) BwK:
"large" budget regime and two-stage design. Bandits with knapsacks (BwK)
was initialized by Agrawal & Devanur (2014); Sankararaman & Slivkins (0018 2021]; |Badanidiyuru et al. (0188) where the well-known optimistic exploration with the primal dual design has been extensively studied in Agrawal Devanur (2014) 2019); Agrawal et al. (2016); BBdanidiyuru et al. (2018); Immorlica et al. (2022) to reduce BwK to unconstrained bandits. BwK has been further extended to the contextual version of BwK in Agrawal & Devanur (2016); Badanidiyuru et al. (2014); Agrawal et al. (2016): Li & Stoltz (2022); Slivkins et al. (2023); Han et al. (2023) under different realizability assumptions for rewards and costs, such as linear class, logistic function class or even general function class. When the linear structure is imposed
the rewards and costs, the work Agrawal & Devanur (2016) integrates the primal-dual design with LinUCB exploration and designs a
two-stage learning method to achieve the regret of Ō( + い*
5 5>vT (T) when B = S((T)) ). Inspired by
framework for contextual bandits in Foster & Rakhlin (022)) CBwK under general realizability conditions is studied in Slivkins et al. (2023): Han et al. 2023 by assuming access to online learning oracles. However, the work Slivkins et al. (2023) requires a large budget assumption where B = (T) and the work Han et al. )223) still assumes B = 2(T as it also utilizes the two-stage method search the optimal value Z D* / as in AArawal & Devanur 2016).
the
both of these works assume prior knowledge about the strict feasibility margin.
Contextual BwK: "small" budget regime and strict feasibility assumption. There exist two recent work Kim et al. (2023); Chzhen al. (2024) that attempt to break the barrier of B ((T)), where they achieve the regret of O((1 + à
=* ) T) under the relaxed budget = ((vT)). However,
these works rely on specific assumptions: Kim et (2023) requires null action (which a more stringent requirement), while [hzhen et al. (2024) assumes strict feasibility. Besides, Kim et al. (2023) assumes linear rewards and costs, and Chzhen et al. (2024) presumes the safety margin is known, allowing the learner to make conservative decisions. Although (Czzhen et al.] (2024) claims that their proposed algorithm is direct primal-dual approach (unlike the previous two-stage designs), they still need to implement a doubling trick to search for the optimal dual variables, which shares a similar spirit to the two-stage algorithm Agrawal & Devanur (2066).
(Contextual) BwK: "flexible" budget regime and without hard-stopping. There exists another line of literature where the interaction can continue even after the budget is exhausted Kumar & Kleinberg 2022); [Bernasconi et al. (2024a b). which we call a "flexible" budget regime. Kumar & Kleinberg 2022) consider non- mon-moootonic or replenishable resource utilization for cont-contextual)
stochastic bandits with knapsacks, where "null action" is introduced to allow the budgets to be replenished. [Bernasconi et al. (0224b) extended bandits with replenishable knapsack constraints into regret guarantees. Very recently, [Bernasconi et al. (2024a) studied stochastic and adversarial bandits with general constraints, where constraint violations are allowed and hard stopping is imposed. They proposed weakly adaptive primal and dual algorithms that achieve tight regret bounds in both stochastic and adversarial settings. However, extending these results to the hard stop setting might require additional and dedicated procedures.
adversarial scenarios and achieved thest-of-both-woole
STOCHASTIC CONTEXTUAL BANDITS WITH KNAPSACKS
In this section, we introduce Stochastic Contextual Bandits with Knapsacks (CBwK) defined by {X' A, r, c, B), where X' is the context set (a countable set), A is the action set (a finite set), X A [0, R] is the reward function, e X x A [0, CJK are the cost functions, and
3

---

Published as a conference paper at ICLR 2025
B= [=I...... Bx] is the initial total budget vector. Without loss of generality we assume the uniform budget B& = B, A E [K]. At the beginning of every round E [T], the learner observes a context 2, that is randomly generated from the context set X' according an unknown probability distribution Ps- The learner takes an action at E AA according to a policy defined by π : - A, and then observes the noisy reward, i.e., [2 at), and the noisy costs, denoted by Cr (z). Given the initial budgets B, the interaction terminates once any type of resource is exhausted or it reaches the end of time horizon T. Note that the context distribution, reward, and cost functions are all unknown to the learerr. We present the following assumption on them.
Assumption The context {ct] are i..dd across rounds. There exists reward function r X x A [0, RJ and cost fimnttions с X x A - [0, CJKK satisfy that r(z, a) [ a)} x] and c(x, a) = (2,, a) a)| Dz = xJ. Vx E X, a E A.
Let a. be the action taken by the policy xe given context xy in round t. For the given instance {zehe drawn from certain distribution, the learnrr's ' objective is to design dynamic policies that maximize the cumulative rewards over horizon T under the knapsack construints:
max Σ rlz,, a.) s.t. Ee & B.
(I)
Note it could be quite challenging to solve (I) because the reward, cost, and context distributions all unknown to the learner. The budget constraint further complicates the problem because all actions coupled over the time horizon, making it difficult balance the reward acquisition and budget consumption. To evaluate the performance of a policy, we introduce the definition of regret.
Regret: We begin with offline problem by assuming the full knowledge of rewards, costs, and context distribution. Define b = B/T = [b..... b) with = B/T, the offlin problem in { can be
reformulated as follows
max
Σ ae
Par(s, p
(2)
S.t.
Σ
Pa (I, a) bb the [K]
Σ
x(x,a)= x x(x a) 02
where π(x, a) can be viewed as the probability of taking action a on context x, and Pa is the probability that context x is sampled in each round. The next lemma shows that the optimal value of
serves as an upper bound on that of (T. The detailed proof can be found in Appendix A
Lemma Under Assumption | let v* be the optimal value of the offiine problem 2 4 and OPT
be the expected reward of the optimal dynamic policies the problem 7.. respectively. We have OPT & Tu².
Now we define (pseudo) based on the bascline above for an algorithm as follows
Regret(T) = Tv* E
Σ r(z), a.)
(5)
The expectation is taken w.r.t. randomness from {ar} drawn by the algorithm and the environment.
Before presenting algorithm and analyzing the regret performance, we first introduce the modeling and estimation reward and cost functions.
Learning Oracles: We assume there exist online learning oracles for reward and cost func- tions such that the corresponding estimators are either optimistic or pessimistic and the cumu- lative estimation errors
be bounded. Specifically, given the historical feedback information (R, ag), C, (I, az) ), 1-11 at every round t, the online learning oracles will output the estimators
of reward and costs f. X x [0, R] and é : X x A - [J, that satisfy the following assumptions.
II the initial budgets {B&) are different, we can always make them identical with the scaling factor By/ ming B& for every type of resource.
4

---

Published as a conference paper at ICLR 2025
Assumption 2 There exist online learning oracles (O)r, such that the reward and cost estimators fe a) and (/)) (ar, a) satisfy the the following conditions with a high probability at least - p.
00 (x, a) - r(x, & 22,(zr,,1),
& - 0
( (I, a) (k) (z. & 22, a. p), vk E [K], ZE H, a A, te
where p = 1/T², and U (T. = E Ex dz, p) = O
This assumption describes the performance of learning oracles, a common condition that can be met in contextual bandits Abbasii-ydkoon et al. (201T); Filiippi et al. (2010); Foster et al. (2018); Han et al. (202);; Chzhen et al. (2024). When the reward and cost functions belong to the linear class, the classical online least-square regression oracle satisfy Assumption 2
and Ex a, is et al. (201T). When the reward and cost maaxmmm--ikelihooe functions belong to the generalized linear class, the online maximum likelihood estimate oracles satisfy Assumption 2 and ( a, a. is the generalized upper/llwer confidence bound Filippi et al. (20T0). When the reward and cost functions are general and do not have good structure, the weighted online regression estimators still satisfy Assumption 2 and (I, a, p) can be calculated efficiently via binary search method Foster al. (018))
simply the upper/lower confidence bound Abbasi--addaaaae
ADAPTIVE AND UNIVERSAL PRIMAL-DUAL ALGORITHM FOR CBwK
In this section, introduce AUPD, adaptive, single-stage algorithm for solving CBwK, designed to achieve the universal regret guarantee under both the absence and presence of the Slater's ' condition in the small budget regime. AUPD does not require any prior knowledge except the initial budgets B and the time horizon T. The design of AUPD is motivated by the primal-dual optimization approach Wright (197)) [Bertsimas & Tsitsiklis (1977), incorporating
adaptive budget-aware design with new perspective from Lyapunov optimization. We utilize the virtual queues to estimate the over-used budget consumption and carefully choose the tradeoff parameter to balance the rewards and budget consumption. AUPD algorithm comprises the following key components:
Budget-Aware Decision-Making: At each round 1, AUPD first obtains estimated reward and cost functions from the learning oracles (O)nc. which used to construct optimistic/pessimitii
estimators é and č₁ The action is chosen to maximize F. - Σe Q of /V, inspired by "Reward
Lyapunov Drift" in Lyapunov optimization, where the Lyapunov drift En((O is approximated by Σ, 2,th afh)// /V according the virtual queues update in ( This resembles the primal-dus method, where the primal modular is to maximize the approximated Lagrangian function
(Q(
Mx a) = r(zt, a) Σ (k) (c (1,, b)),
K
where the Lagrange multiplier (A) is approximated by (* /V, and the reward and cost functions are approximated by the optimistic/pessimisti estimators. The key design is the budget-aware trade-off parameter V = byT (resembling an adaptive learning rate). It is different from the traditional Lyapunov optimization method where the trade-off parameter is only related to the time horizon T. Intuitively, when the budget is small, V is small, and it prompts more conservative decisions; otherwise, it prompts relatively optimistic decisions.
Unlike the approaches in Agrawal & Devanur (2016); Han et al. (0033): Chzhen et al. (004)). which require the extra parameter search stage, AUPD enjoys a single-stage and direct greedy structure in decision decision-making. Besides, the primal decision module implicitly learns the context distribution, as the decision (6) tends to avoid overspending the resources on contexts with low rewards and high costs.
Oracles Update and Budget Pacing: After observing the noisy reward R, at) and noisy costs Ca(22, at), AUPD feeds them into learning oracles (e.g., online weighted regression oracles) con- struct estimators for future rounds. The other key design in AUPD is budget pacing, where we design
the virtual queues track the cumulative over-used budget consumption Σ.= (e(*) (x2, a,) b). The concept of virtual queues originates from queueing theory and is widely used in networking and operations research in Hajek 1982); Neely (2010) Eryilmaz & Srikant (2012). In real queueing
5

---

Published as a conference paper at ICLR 2025
system, customers arrive, receive service, and leave, with the queues capturing the carryover effect and representing the number of waiting customers. The real queues motivate the design of virtual queues 0,²² in our setting, it represents the cumulative overuse of a resource, where the "arrival" corresponds to the current resource consumption and the "service" corresponds to the average budget. When the virtual queues increase, it implies that we might have spent too many resources so far, and it encourages a relatively conservative decision. The virtual queues can be regarded as the scaled dual variables in the primal-dual design in AArawal & Devanur (2016); Han al. (2023):
Chzhen et al.] (2024).
However, unlike these works, which either impose upper bounds or conservative factors in the dual update that require two-stage learning process, strict feasibility assumption, or the knowledge of feasibility/safeee margin, the virtual queues update in AUPD is again natural and direct. This is the key reason we do not require strict feasibility assumptions or any prior information about the feasibility/safety margin. Furthermore, by treating the virtual queues as Markovian processes, we can use Lyauunov drift analysis to establish their upper bound, which can then be translated into a strong lower bound the stopping time.
Algorithm 1 Adaptive and Universal Primal-Dual Algorithm for CBwK
1: Initialization: À = 1, o((h) 0, vk [K] and V by learning oracles set (O)r,e.
2: for t fort=111 1, ,T, do
3: Parameters Estimation: Given a context æt, estimate the reward functions (I a) and the cost function Ca( a) from learning oracles [O)r.-
4:
Budget-Aware Decision-Making: Take the action de such that
= argmax Virlz,, a) - Ql of (xt, a).
(6)
anA
5: Feedback and Oracles Update: Observe noisy reward R2 az) and noisy costs C. (z at) and feed them to (r... Budget Pacing: Update virtual queues as follows
6:
Q = Qi =| + c. (x), as) -6) b)" Aa [K].
7: end for
In summary, AUPD provides novel algorithm design template and theoretical analysis for CBwK. The budget-aware decision decision-making and virtual queue-bascd based oudget-pacing are crucial in developing fully adaptive algorithm to achieve a strong regret performance in the small budget regime.
4
MAIN RESULTS
In this section, we analyze the regret performance for AUPD in Algorithm 1 We begin by stating the strict feasibility assumption for the performance analysis.
Assumption There exists a constant e (0, 1] such that a feasible solution x to the optimization problem
4 satisfies Exex, Pac (z), (l),,))(zz0 a) & b(1- 5), Vk [K].
The term 8b plays a similar role with the Slater's constant in optimization. However, the term øb differs from the traditional Slater's 's constant because the definition 6 B/T implies it is both budget and time horizon related. Note that the existence of null action is a special case of this assumption with 8 = 1. This assumption has been used in the literature of BwK (Agrawal & Devanur (2014 2016); Badanidiyuru et al. (2014) 2018); Chzhen et al. (2024).
Now, ready to present the theoretical results of our algorithm, which given in order-wise sense. The detailed proof and parameters are in the appendix.
Theorem Under Assumptions and AUPD achieves the following regret in the small budget
regime B Q(vT) that
Regret(T) T) - Ô ((VT
4* =T
vbb

---

Published as a conference paper at ICLR 2025
When the additional strict feasibility assumption in Assumption 3 regret in the small budget regime
holds, AUPD achieves the following
Regret = = 8b
NTTT
Remark When the strict feasibility assumption holds, AUPD achieves Ō((1 +
85 (TT
Ô (VT+ + regret in the small budget regime B = T = (((T)) under the general realizability assumption of reward and cost functions. The parameter v /8b in the regret captures the effect of knapsack constraints, where it could be large when the safety margin ōb is small, indicating the challenge of distinguishing the budget consumption among context-action pairs. The typical and practical setting would have Tv = ((T*) (i.e., Tv* = ( because it represents "one unit of reward earned by consuming one unit of cost". In this setting, we can get the classical and optimal Ö(VT) regret. This result matches the regret guarantee in Han et al. (2023); Chahen et al. (2024). Unlike these works, AUPD does not require the doubling trick or other parameter search stages, thus providing a more direct and adaptive structure.
When the strict feasibility assumption does not necessary to hold, AUPD achieves worst-case theoretical guarantee of Ö(VT+ 5 ++ - Ô (VT Tu+T+=9) in the small budget regime, which, to be the best of our knowledge, is the first result for CBwK without strict strict feasibility assumption even when B = (T) Intuitively, the additional term vb T2 is due to the "hard" problem instance. When Tv² ((T²)= @(B). i.e., one unit of reward for each unit of cost, AUPD achieves the regret ÖTT)) performance, instead of the classical regret Ö(VT). This might imply that the CBwK instance, without a strict feasibility assumption, is indeed challenging.
Finally, it is worth emphasizing that all these results are achieved with single AUPD algorithm, without any tailored adjustment or any prior knowledge of the problem instance. This demonstrates that AUPD quite adaptive and universal for CBwK.
The classical lower bound for CBwK is MVVT) in Agrawal & Devanur 2016) derived by reducing the constrained contextual bandits into unconstrained ones. 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 el al. (2024). With the assumption of strict feusibility, Section E in Chzhen el al. (2024) provides problem-dependee
Remark 2
lower bound of Df v² /b)//T) for CBwK with B = ((vT)). 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 strict feasibility, which is an interesting direction for future work.
To establish these strong results, we need to carefully analyze the budget consumption processes. The key is to identify when the interaction terminates/stops and how much cumulative rewards AUPD gains during the process. When the strict feasibility assumption holds, we provide new perspective on the stopping time (i.e., the first time when any type of resource budget is exhausted) and a refined analysis of the cumulative variance of budget consumption. Our analysis treats the virtual queue update as a Markovian process and leverages the Lyapunov-driff analysis to establish the expected upper bound on the virtual queues (i.e., the over-consumed budgets), which translated be the lower bound of the stopping time. Without the strict feasibility assumption, we directly establish the upper bound of the virtual queues. These bounds will be used to establish the regret bounds in Theorem [ as we detailed in the next section.
5 THEORETICAL ANALYSIS
In this section, we provide a detailed proof of Theorem 1 the regret defined (5) according to the stopping time T. The stopping time defined as the first time when one of the resource budgets is exhausted
To state these results, we first decompose
argmin r'e[T]
7' 3k,
Σ
(k) (Iz, 01) > ²B.
(8)
7

---

Published as a conference paper at ICLR 2025
5.1 REGRET DECOMPOSITION
Let n** be the optimal solution to the baseline problem 2 and oz be the optimal actions sampling from it, i.e., of T* We decompose the regret as follows
(T)
r(z,, a7)
Σ (l(xe
r r(ze,
Regret after stopping
Regret before stopping: Regret(r)
The decomposition includes two parts:
"regret after stopping" and "regret before stopping". The former one is simply bounded by the remaining rounds x the optimal value v*; the latter one denoted by E[Regret( 7)] the difference between our policy and the optimal one.
As discussed, we provide new perspective on analyzing the regret via Lyapunov drift analysis, which can be used to bound both "regret before stopping" and process and study its connection
Regret via Lyapunov Drift Analysis:
"regret after stopping". We view {Q+} as stochastic/Markovia
with regret. Let L, = QQ = (Q,))) /2/2 be the Lyapunov function and A, L++1 L be its drift. Further let Ex, [.] E[- where Hi [r,, ćt2 Q.] We establish the following key lemma that bridges the one-step regret and Lyapunov drift. The detailed proof is in Appendix [B.T]
Lemma' Under Assumptions 7 and AUPD in Algorithm|
establishes that for any feasible policy
T to
f
with a ı that
Regret(æ,, a) + A
Ex.
Σ
(c)))
(xI, -b)
2 22r((e, at, 2V
1
26 (1e, b)) Σ 2Q (1 b) P (E
< EEH,
T2
(E)
where Regret( F2, a) a( rxx,, az) and the event defined in Assumption
This Lemma is the key lemma that establishes the bound of "one-step regret + Lyapunov drift". bridges the analysis bound both "regret before/after stopping" as we will demonstrate in the following. Note that the lemma holds without strict feasibility assumption in Assumption 3
5.2 REGRET BEFORE STOPPING
Letting a a. n in Lemma 2 and ignoring the low probability event 8 then the inequality suggests that step-step regret Lyapunov drift" is upper bounded by three related terms: the optimal budget consumption Σn (c( (2,)) az) - b), the single-step estimation error Ez az. p), the estimated consumption resource Σx (c) (e(()) a.) b)2. Bounding "regret before stopping" E [Regret(T)] requires establishing their cumulative counterparts: the expected optimal budget consumption is always negative according to the definition; the cumulative estimation error is bounded by Assumption 2; the estimated consumption resource is the most important part and provide refined analysis that bound this term by O(TTb + Ti2), /V), which is one of the key components in proving the strong results in Theorem The result of "regret before stopping" is summarized in the following lemma and the detailed proof is in Appendix B.2
Lemma 3 Under Assumptions 7 and 2 the budget-aware optimistic exploration algorithm in Algo- rithm Machieees
= -OV + K(Tb + TVP)
E [egree(T]]]
5.3 REGRET AFTER STOPPING
In the regret decomposition, the "regret after stopping" is bounded by = =]. To minimize this regret, it crucial establish "large" lower bound on the stopping time ideally depleting the
8

---

Published as a conference paper at ICLR 2025
budget only when it is very close to T. To (lower) bound the stopping time need to analyze the behavior the virtual queue because it captures the coes-cond budget against the average usage b for the round t.
Recall we have the virtual queue update Q441 = max(Qu (h) + 2 ( a³) b, 0). Let M, =
Σi 0e) ett) (ct, at)), then for certain budget k that is first to exhausted, we have
Q441 + br + M
(k') (
(10)
From learning oracle errors in Assumption 2 we already have a high probability upper bound for M Vkk E [K], then we can consequently define virtual stopping time such that TO argmin,rerry (r' 2 + b O(VF)= > B), where k' denotes the resource that was first depleted. The virtual stopping time is the first time when the upper bound of budget consumption in (TO) is greater than B. The inequality (10) indicates that the value Q reflects how soon the algorithm will deplete the resource. Combined with the definition the stopping time in (8). we immediately have that the true stopping time is lower bounded by the virtual stopping time, i.e.,
Tn- Now we only need to establish the lower bound on To, and the key is to prove an upper bound for the virtual queue length the stopping time, which can be provided through Lyapunov drift analysis.
Lyapunov drift analysis for establishing TD: As discussed, we view [Q:} as a stochastic/Markovian process and study its convergence or upper bound via Lyapunov analysis. When the strict feasibility assumption in Assumption holds, from Lemma 2 we establish a "negative drift" of the Lyapumov drift function, implying "small" expected upper bound of the virtual queues in the following lemma. Without Assumption
3 we establish slightly worse upper bound.
Lemma 4 Under Assumptions
1 and 2
when B Q(vT), AUPD in Algorithm I achieves that
E
Σ
x = O(VKVT), e [T].
with the additional Assumption
3
AUPD guarantees that
E
Σ 2 (k)
O(VKV/6b) et [T].
(11)
The above lemma demonstrates that the virtual queues are "stable" and relatively "small", indicating that our algorithm utilizes the resources effectively and does not terminate early. Intuitively, the underlying reasons behind virtual queues staying within "small" region because, upon detecting over-consumption (the virtual queues increases), the algorithm would make conservative decisions to reduce the queue length. Now, we are ready to establish the expected upper bound on the remaining rounds in the following lemma, which is the key to establishing the regret performance.
Lemma Under Assumptions Mand 2
the expected remaining round in the small budget regime B 2( (V) under AUPD in Algorithml satisfies that
E[T r] - (VKVT /T/b),
with the additional Assumption 3 the expected remaining round under AUPD satisfies that
E[T - 7] = (VKV/188 +VT///+++).))) vT.b).
Proving Theorem 1 [emmaa]demonstratee that the algorithm's performance approaches the optimal policy before stopping, while Lemma ensures that the algorithm would not exhaust resources and terminate prematurely. Combine them into ( we immediately have the regret bound for two cases. Specifically, for the worst-case without any reasibility assumptions, we have
(T) & u E 7] + E [[eegret( [)]
Ō (v 1K VT K(Tb+

---

Published as a conference paper at ICLR 2025
With the strict feasibility assumption in Assumption 3 have (T) < 1 V - - E[Regret(T))
= - /VKV=*/b0> + KTT/=+
Let V = bvT and we prove Theorem
!
EXPERIMENTS
In this section, we validate our algorithm through numerical experiments using the large-scale learning- to-rank dataset Qin & Liu (2013) in the small budget regime. We compare algorithm AUPD with
SquareCBw Han et al. 2202), an oraclc-based primal- algorithm under B 2 ), and PGD Adaptive Chzhen et al.
2024). a primal-dual algorithm with doubling trick for learning the optimal
stepsize that claims to achieve optimal performance under = ((VT). The large-scale learning-to- rank dataset MSLR-WEB30K Qin & Liu (2013) contains 31, 278 queries. Each query includes various document-query contexts, each with a dimensionality of 136, and there are 20 documents/arms. The reward function r(z; a) is defined the relevance of each document-context pair as collected in the dataset. We construct the expected cost of each arm c(2, a) by uniformly drawing from the interval [0, 5]. and these values remain fixed throughout each trial. The observations are corrupted with Gaussian noise N (0, 0.05). All the algorithmss utilize gradient-boosted tree regression as the learning oracle for the reward function and the empirical mean for the cost function. We set the time horizon T = 5000 and vary the budgets B = {100, 600, 1000} to represent the budget regime (@(VT), O(T*), ((T)), respectively. The interaction terminates once the budget is exhausted, incurring zero reward and cost for the remaining rounds. The further details on the experiments and hyperparameters can be found in Appendix [D] Our experimental results shown in Figure [ These
results are obtained by averaging over 50 trials and are reported with a 95% confidence interval.
1.0
1.0
AUPD
AUPD
AUPD Adapttive SquareCBwK
Averaged Reward
0.8
PGD Adaptive
Averaged Roward
0.0
Adaptivee SquareCBwi
Averaged sewardd
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
1000
2000
3000
4000
5000
0.0
1000
2000
3000
4000
5000
0.0
1000
2000
3000
4000
5000
(a) Budget B = O(VT).
(b) Budget @(T
(c) Budget (
Figure 1: Experiments under different budget regimes.
From Figure we observe our algorithm AUPD achieves the best performance compared to SquareCBwK and PGD Adaptive under various budget regimes. Especially when the budget is relatively small, as shown in Figures Tal AUPD outperforms the baselines by a large margin. This justifies that the joint design of budget-aware decision-makin and virtual queue-based budget pacing is very adaptive and effective to balance the reward and budget consumption.
7 CONCLUSIONS
In this paper, we studied stochastic contextual bandits with knapsack constraints under the small budget regime. We introduced an Adaptive and Universal Primal-Dual Algorithm and provided new perspective of Lyapunov drift analysis to establish strong theoretical guarantees under the small budget regime B ((vT): AUPD achieves the best well-known regret under the strict feasibility assumption; AUPD achieves the first regret result without the strict feasibility assumption. The experiments further confirmed our thcoretical results.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
The work was partly supported by the National Nature Science Foundation of China under grant 62302305 and Shanghai Sailing Program 22YF1428500.
REFERENCES
Yasin Abbasi-yadken Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24, 2011.
Naoki Abe and Philip M. Long. Associative reinforcement learning using linear probabilistic concepts. In Int. Conf. Machine Learning (ICML), 1999.
Shipra Agrawal and Nikhil Devanur. Linear contextual bandits with knapsacks. In Advances Neural Information Processing Systems (NeurIPS), 2016.
Shipra Agrawal and Nikhil R. Devanur. Bandits with concave rewards and convex knapsacks. In Proceedings of the Fifieenth ACM Conference on Economics and Computation. Association for Computing Machinery, 2014.
Shipra Agrawal and Nikhil R Devanur. Bandits with global convex constraints and objective. Operations Research, 1585 2019.
Shipra Agrawal, Nikhil R. Devanur, and Lihong Li. An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives. In Proc. Conf. Learning Theory (COLT), 2016.
Ashwinkumar Badanidiyuru, John Langford, and Aleksandrs Slivkins. Resourceful contextual bandits. In Proc. Conf. Learning Theory (COLT), 2014.
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. J.
ACM, 2018
Avinash Balakrishnan, Djallel Bouneffouf, Nicholas Mattei, and Francesca Rossi. Using contextual bandits with behavioral constraints for constrained online movie recommendation. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 5802-5804, 2018.
Martino Bernasconi, Matteo Castiglioni, and Andrea Celli. No-regret not enough! bandits with general constraints through adaptive regret minimization. arXiv preprint arXiv:2405.06575, 2024a.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. Bandits with replenish- able knapsacks: the best of both worlds. The Twelfth International Conference on Learning Representations, 2024b.
Dimitris Bertsimas and John N Tsitsiklis. Introduction to linear optimization, volume 6. Athena Scientific Belmont, MA, 1997.
Evgenii Chzhen, Christophe Giraud, Zhen Li, and Gilles Stoltz. Small total-cost constraints in contextual bandits with knapsacks, with application to faimess. Advances in Neural Information Processing Systems, 36, 2024.
Nikhil R Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher Wilkens. Near opti- mal online algorithms and fast approximation algorithms for resource allocation problems. In Proceedings of the 12th ACM conference on Electronic commerce, pp. 29-38, 2011.
Atilla Eryilmaz and R. Srikant. Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Syst., 72(3-4):311-559 December 2012.
Yiding Feng, Brendan Lucier, and Aleksandrs Slivkins. Strategic budget selection in competitive autobidding world. Proceedings of the 56th Annual ACM Symposium on Theory of Computing. pp. 213-224, 2024.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Lafferty, C. Williams, J. Shawe- Taylor, R. Zemel, and A. Culotta (eds.), Advances in Neural Information Processing Systems, 2010.

---

Published as a conference paper at ICLR 2025
Dylan Foster and Alexander Rakhlin. Beyond ueb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pp. 3199-32100 PMLR, 2020.
Dylan Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert Schapire. Practical contextual bandits with regression oracles. In International Conference on Machine Learning, pp. 1549-1548. PMLR, 2018.
Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. Budget pacing in repeated auctions: Regret and efficiency without convergence. arXiv preprint 220.:22005.0867.,
2022.
Aditya Gangrade, Tianrui Chen, and Venkatesh Saligrama. Safe linear bandits over unknown polytopes. In The Thirty Seventh Annual Conference on Learning Theory, pp. 1755-1795. PMLR, 2024.
Hengquan Guo and Xin Liu. Stochastic constrained contextual bandits via Iyapunov optimization based estimation decision framework. In The Thirty Seventh Annual Conference on Learning Theory, pp. 2204-2222222 2231. PMLR, 2024.
B. Hajek. Hitting-time titting-timeete and occupation-tima time bounds implied by drift analysis with applications. Ann. Appl. Prob., pp. 502-525, 1982.
Yuxuan Han, Jialin Zeng, Yang Wang, Yang Xiang, and Jiheng Zhang. Optimal contextual bandits with knapsacks under realizability via regression oracles. In International Conference on Artificial Intelligence and Statistics, pp. 5011-5035. PMLR, 2023.
Nicole Immorlica, Karthik Sankararaman, Robert Schapire, and Aleksandrs Slivkins. Adversarial bandits with knapsacks. Journal of the ACM, 69(6),1477, 2022.
Wonyoung Kim, Garud Iyengar, and Assaf Zeevi. Improved algorithms for multi-period multi-class packing problems with bandit feedback. In International Conference Machine Learning, pp. 16458-16500 PMLR, 2023.
Raunak Kumar and Robert Kleinberg. Non-monotonic resource utilization in the bandits with knapsacks problem. Advances in Neural Information Processing Systems, 15:19288-1925, 2022.
Jiung Lee, Hongseok Namkoong, and Yibo Zeng. Design and scheduling of an ai-based queueing system. arXiv preprint arXiv:2406.06855, 2024.
Zhen Li and Gilles Stoltz. Contextual bandits with knapsacks for conversion model. Advances in Neural Information Processing Systems, 35:35590-35602, 2022.
Xin Liu, Bin Li, Pengyi Shi, and Lei Ying. An efficient pessinistic-optimistic algorithm for stochastic linear bandits with general constraints. In Advances Neural Information Processing Systems (NeurIPS), 2021.
Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, and Mengxiao Zhang. Autobidders with budget and roi constraints: Efficiency, regret, and pacing dynamics. In The Thirty Seventh Annual Conference on Learning Theory, pp. 3642-3643. PMLR, 2024.
Thodoris Lykouris and Wentao Weng. Learning to defer in content moderation: The human-ai interplay. arXiv preprint arXiv:2402. 2024.
M. J. Neely. Energy-aware wireless scheduling with near-optimal backlog and convergence time tradeoffs. IEEE/ACM Transactions on Networking, 24(4):2223-2233 2016.
M. J. Neely. Stochastic network optimization with application to communication and queueing systems. Springer Nature, 2022.
Michael J. Neely. Stochastic network optimization with application to communication and queueing systems. Synthesis Lectures on Communication Networks, 3(1):12211, 2010.
Tao Qin and Tie-Yar Liu, Introducing letor 4.0 datasets. arXiv preprint arXiv:1306.2597 2013.
12

---

Published as a conference paper at ICLR 2025
Karthik Abinav Sankararaman and Aleksandrs Slivkins. Combinatorial semi-bandits with knapsacks. In International Conference on Artificial Intelligence and Statistics, pp. 1760-1770. PMLR, 2018.
Karthik Abinav Sankararaman and Aleksandrs Slivkins. Bandits with knapsacks beyond the worst case. Advances Neural Information Processing Systems, 34:23191-23204, 2021.
Aleksandrs Slivkins, Karthik Abinav Sankararaman, and Dylan Foster. Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression. In The Thirty Sixth Annual Conference on Learning Theory, pp. 4633-4656. PMLR, 2023.
Ambuj Tewari and Susan Murphy. From ads to interventions: Contextual bandits mobile health. Mobile health: sensors, analytic methods, and applications, pp. 495-4195517 2017.
Sabina Tomkins, Peng Liao, Predrag Klasnja, and Susan Murphy, Intelligentpooling:: Practical thompson sampling for mhealth. Machine learning. 110(9))268--2227, 2022.
2021.
Stephen J Wright. Primal-dual interior-point methods. Society for Industrial and Applied Mathemat- ics, 1997.
Mengyue Yang, Qingyang Li, Zhiwei Qin, and Jieping Ye. Hierarchical adaptive contextual bandits for resource constraint based recommendation. In Proceedings of the web conference 2020, pp- 292-302, 2020.
Hao Yu and Michael J. Neely. A low complexity algorithm with O(vT) regret and O(1) constraint violations for online convex optimization with long term constraints. Journal of Machine Learning Research, 21(1):1-24, 2020.
13

---

Published as a conference paper at ICLR 2025
A PROOF OF LEMMA I
and let of be the The proof similar to that in Devanur et al. (011). Recall the problem adaptive optimal solution:
max
r(z,, a
subject to: Σ c(r,, a. & B
Recall the context is i.i.d. across rounds and r(v, a) and c(1,, a) are the expected functions given I. We have
r (2,,
a)
=
E
Σ r aT)
E
Σ> Par a [ xt 2, H4-1l
E
Par x
E [TT( x, 11-11
par(a,
E [ (2, (x, Σ
Similarly, we have
T Σ
Σ
(0)
= ΣΣ Pac (I, a)
(T( æ], wk: [K].
Define #* (z, = -
El 2 = æ], where nे.. a feasible solution 2
because
** is feasible solution to 11. Therefore, we have
E
(( a) a)= (2),
= T ΣΣ
Par a)*"
& Tv*
B REGRET ANALYSIS
For the sake simplicity, we initially let the reward and cost upper bounds C' in Assumption before delving into detailed proofs.
B. PROOF OF LEMMA 2
In Algorithm I
the action a, is the optimal solution such that for any a A.
fe(z),)) Σ !h & (t)) (z,, a) (r at) 1 Σ of
( al0 (z,, at).
Add Regret(ar, a) = r(xt, a) r(z,, ar) on both sides and rearrange these terms, we have
Regret(x1t a)
(12)
<(r(It, a) - fe(we, a)) + (fr(sr,, ar) - r(ze, ar)) +
1 V
2 (zt, - - (11,
14

---

Published as a conference paper at ICLR 2025
According to the virtual queue update
Q max
(0.²) + ek) (x) b,0). vk.
The following inequality holds for the Lyapunov drift that
1 Σ (1t1)) 2 - Σ (o!h))² A. == 2
2 E 2
1
(e
( of - b)(c b) -b)(
Of!th th) (sr, - -b) Σ
(o (I2, b)²
k
Combine this inequality with 12 we can establish the following key bound on the "Regret + Lyapunov drift":
A. V
Regret a) <(((x), a) ()( (F)( -((2),)))) at))
1 E olth (c - b) 2V
1
1 Σ (z)) - b)² k
(13)
k
To proceed, we recall the following event defined in Assumption 2 least 1 p:
which holds with probability of
E 0 a) r(z,a)) & 20,(s,
0 ( a) - (1) (z. a) < 20,(2, a,p. Ak E [K], a X, a A, te [T)
Recall p 1/T², now taking the conditional expectation E[ HH, h] on 13 where [z, f. ē, Q]. we obtain that
E [Regret( ø1, a)/ = hl + E
V 17 = h
E [[((z, a) f,(x,, a)) + (fr (2,, ax) - r((z, at) a))) [1]111,1.10 =1, (x,, or,
(k) (b)) (Ir, - b) + 2V Σ ( (11,
( at) b) 174
+ E
2
(1 ar p) +E
1
Σ
kK)
(Ie, ac) - b)² 1741
72
2V
(k)
(4)) a) -b)
+
E
V
2
20,(Ire az, p) +E
1
Σ
c
(k)
(zt; ac) -b)² 174, h
h
72
2V
Q()((1 b) p (E
(())
(c)0) a) - b) | Ht = h,,
+ Σ
+
V
v
x
< 7
2
20, ar
+E
2V Σ
(k) c (Iz, -b)) 1744 =
(c(0) - 14+ h + Σ h1+ 2Q(h) (1 + b) PP (8))
+ v
B R
(14)
K V P())
where the second and third inequalities hold because of the definition of event E. The last inequality holds because the context is independent of H. and the distribution of xx does not change conditioned on H4. Therefore, we have
PP P(++ x: HH h E) = TP (x+ x1
15

---

Published as a conference paper at ICLR 2025
Then calculate that
P(x+ x2,) PP (I+ P()
P (az = x|E) - -P (x = x)
P(E)
[2t 2) (P(E) x) P()))
P(E)
<P <P (It x)) - IP (E)
IP (8)
which implies that
Σ x (c(A) (c(0) a) - 6)17,, = -1, Σ Q (c)) - -b))/4
2
< Σ (1+ (1+0 1-P(E)
PE
(1 b)
(E k
P(E)
B.2 PROOF OF LEMMA 3
Since the action could be any action in A, we can let oz T in 14 obtain:
A
E Regret( (z, az 17c h:]
+
H7
V
& T + 25, ar, p) + 2V Σ
2
4 (1s, at) -b) 176 +
2Q K0 (1
b)
(E
V
P
(15)
where the inequality holds because the action of satisfies the constraint in 3 such that E [(el a²) - 14 h] < 0. We further take the expectation on both sides of the inequality and then take summation from
that
[ (k) )²
(4 2V
E
Regret Fe, a²)
+ E
2
2V
2r
+
2
Σ 1-1
Eo( ac. E
Σ
(1)
(z ax) - -b)²
+
2Q (1 + b) ((8))
72
2V
V (()
Since (())) conclude that
o, vk
1/T and a & ((4)
+ < T, Vk
[K], E [T]. we
T
Reg a²)
$ <
+
ce( at p) + 4K(1 + b) +
Σ
c (12, - -b) b)²
2V
k
< < + 2U p) + 4K + b) + E
Σ
(Ze, at) -b)
2V
where the first inequality holds since stopping time < T, and the second inequality comes from the learning oracle assumption. Finally, we complete the proof by providing simple but refined analysis on the cumulative budget consumption that
1 2V
Σ
(k) (2), ai) -b)²
(k) D2, a,) 2, + 622
E
E
V
+ TKb²
E
(k) (Iz, az)
where the second inequality holds because & (26, az) is bounded by 1. Moreover, we have
E
Σ (Iz, ar)
= E
Σ (k) (Ir, az) - ( (25, (2), ar)
+
(k) (1r, at)
< El+ 1 + Tb,
16

---

Published as a conference paper at ICLR 2025
where the last inequality holds because of Assumption 2 and the definition of stopping time т. Therefore, we have
ar) 1))
K(1 + Tb+ +b2)
K(1 + Tb + Tb²)
E
Σ
(1r,
2V
V
V
E
By combining all these facts, we derive an upper bound for the regret incurred before stopping.
K(1 + Tb Tb²)
I [Regret(T]] & T + (T) + 4K(1 + +b)
V
22 + 2 + 4K b) + K
+1+bb
VT
bVT
< {6K 4K6) + 20 K(2 b)
=C + 21=+CooToog(T/// + K(2 K(2+
where 1
6K + 4Kb and the second inequality holds due to the value of V, while the third inequality is consequence of the fact that K > 1.
B.3
PROOF OF LEMMA 4
B.3.1
LYAPUNOV DRIFT ANALYSIS
From
14
we have established the Lyapunov drift
(Q++))
(k)
)
Σ
(Q) )
He
2
2
k
2V
2V p).p) + E - -VRegret(zzs x2, a)
+
1
Σ
(K)
(Ie, (z), - b)² He
72
2
2Q2 b) PP (8
Σ
( (12, a)
-)b)(1) -b)17(e
Σ
V
P())
k
<VV + E
VRRgret(Tr, a) Σ
1
c
(Ir, ..) - b)² ? 74
k
(() (1 b) ((
Σ (E (cc (ITe: a) - -b)
Σ
(16)
P(
<6V E
Σ
(2) (1e, a1)
ax)- -b)² H.
( 8b
2Q (1 6) IP (E
P(E)
K
<6V E
Σ
(K)
(I2, az) b)) 2 17
Σ ( 5b
Σ (1())(1+)))
VT2
K
<VV E
Σ &
(z), - b)² 74
> Q 5b
4K(1 + b)
(17)
VT
where the second inequality holds because e (I,,, p) & 1 as specified by the estimators' and the function's upper bounds; the third inequality holds because of the upper bounds of reward function and cost estimators and the "Slater condition" in Assumption that there exists feasible policy such that
E
(Ie, a) - bl He = h & Sōb Vk E [K].
B.4 CBwK WITHOUT STRICT FEASIBILITY ASSUMPTIONS
For CBwK without striet feasibility assumptions, we can set a* * in (6). This allows us to obtain inequality similar (17) replacing
Σ. (K)) with 0, can then directly take the
17

---

Published as a conference paper at ICLR 2025
expectation both sides to obtain:
(k)
)2
(2)
ae) 3b)² (2t, ar)
4K + b)
E
<VV + E
2
2
2 4
VT
4K (1++1 +
<VV + IE
Σ
(zt, ar) +
VT
where the incquality holds since Q44, 6, 3 0, (a b)² & a² + b² and the value of ct (ax, a) are bounded. Sum this inequality from 1 to т, then have
(R)
)²
)² \
4KT(1 + b)
E
<VV + E
19 (x) + 12)
+
2
2
2 h t=1
VT
h
8
1
4KT(1 +
<6VT +
+ B +b²)+
2 T
VT
<6V + K(1 + B Tb*) 4K(1+ + b)
V
<VT + 6KB + KTB + 4KVTT
where the second inequality holds due to the high probability event &, the last inequality holds since 1/V & VT and b/V < vTb & B, Combine the facts that Q = 0, and Cauchy-Schward inequality, we have
Σx (1))
2
r++1
E
6VT + 6KB + KTV + 4KVT.
2K
Rearrange these terms, we obtain that
E
Σ
& 12KV7 + 12K B + + VT.
Then we have
E
Σ (k)
< < 4-KK66+ +3TT
B.4.1 CBwK WITH STRICT FEASIBILITY ASSUMPTION IN ASSUMPTION 3
We define the Lyapunov function T. v {) 1Q To establish the expected bound on the virtual queue, we prove conditions (i) and (ii) in Lemma 6 for L.. From
17
we have
E| Qu+1 1Q
<VV + E
(Iz, at) - 6) 74
Σ Q0418
4K(1 + b)
2
VT
<VV + (1 + 6)2 Σ (1)88 4K(1 + b)
VT
<V + 6K + 6)
Σ (8)) 8b.
Given Hi = h and L, > +3K(1+))+)) the conditional expected drift of T., is
E[|| - ||Qr|||74 hJ
< 2
E[ - 1Q.1 = h]
2
6V + 6K (1 + 6)2 1Q 1886
2|Q2
18

---

Published as a conference paper at ICLR 2025
8b
+ 3V
(1
+ b)?
2
[Q]
8b
4
where the first inequality holds because 2( 1
the second inequality holds by the "negative drift" in 17 above; the third inequality holds since QQ1 > |Q 2:
& 1Q
1. -Q
and the last incquality holds given the condition |Qr12 2 > P = 1(3V ( condition (ii) in Lemma 6 we have
Moreover, for db
QQ+1122 1Q:12 & || - Qr112 E QQ+1 - Qe1l < K,
where the last inequality holds because 10(4] Q(a)) $ 1 b, A [K].
Let 4: max and recall Q((h) = 0, vk [K]. We are ready to apply Lemma 6 for L(t)
and obtain
2e((mmentis))
P
E
1
with (
(18)
Cp
U + /maxxp33
Then according to Cauchy- Schwarz inequality, we have
(Vmaxxtpp
E
e R
1Q.11
< 1
Sp
Applying Jensen's inequality, we obtain that
Se
& 1 + TevxlQ11 QQ:11
&
E
Sp
Finally, for any e
[T]
K
2e tipe)
E
Σ
log
1
Sp
K
Sw muxx ((pm
log
1
3p2
K
11v2
max S tipe)
log
5
3p2
2
K
log max/ (p) K KKpt
<
2VK
4VK(3V (K(1 + b)2)
log (8K/ōb) + K
5
8b
2
12K (1 + b)2 12 KT
log (8K/ōb)
+ K
8b
where the second, the third and the fourth inequality comes from the definition of Ç and the fact that p & Vmax and Vmaa K, the last two equalities comes from the definition of yp: and V.
B.5 PROOF OF LEMMA UNDER ALGORITHM II
Recall the definition of virtual stopping time
To = argmin, { (11QQ.) Q(4) + br + M > B, 3k}
where Ma ΣT (c()) (are, a+) - 2(x) (xx,, at)). Divide both sides of the stopping time definition inequality by b and take the expectation, we have
(()
E T 7] E To]
19

---

Published as a conference paper at ICLR 2025
E Q / + E1 |
(K) /bb
E [1 ||/
[[M,
where the first inequality holds since any &
To according the definition (8) From Assumption for
M Σ Ex(2,, ae p) <
Ex( ac, & 2Co V log(T/p).
then the stopping time bound can be established by
r| & E 1 2C 2CovTlog(T/p)
E T
We first consider the case without strict feasibility assumption, then we can establish the bound through Lemma such that:
K T /
T 2K 3KT 2C 2CoVTlog(T/p) 4K
E B[T-
b
We can then get a refined result with the Slater condition in Assumption an upper bound Lemma the stopping time can be bounded by
Since we have established
2vK ςb
log (8K/ōb) K Kåb-1 12K (1 + 6)²
12 KT
20 log(Tp)
E [T - -
8b2
8b
B.6 PROOF OF THEOREM UUNDE ALGORITIIMI 1
Now we aggregate the regret after stopping and before stopping as follows. For the general case, we have
Regret( (T) & E
Σ
r Fr ae)
Σ at)
regret after stopping
regret before stopping
cC + 2CooVToogT(T//)
K(2+ b)vT
K T + VV
3KT
20oV (ooVT))(T/p)) v². (19)
4k
V
f 2KVT
b
With the Slater condition in Assumption
we have
(Tg
ETT 7
r(n at)
E
a()
regret alter stopping
regret before stopping
<C1 + 2C- log + (22 b)TT
2
12K 6)2
12
20 log(T/p)
+
log (SK /8)) + K b
+
4
ςb
502
8b
b
(20)
which proves the regret bounds in Theorem
C SUPPORTING LEMMAS
C.1 LYAPUNOV DRIFT LEMMA
We present a lemma that will be used to derive the high probability of (Qt). The lemma is from Liu ct al. (202I), which a minor variation of Lemma 4.1 Neely (2016) 2022) and the results Hajek (982). where the radius of yo, could be time dependent.
20

---

Published as a conference paper at ICLR 2025
Lemma 6 Let S(t be random process. ((t) be its Lyapunov function with ( 4u and
((t) ((t + 1) (t) be the Lyapunov drift. Given an increasing sequence (Gt), and Vmaa with
0 <<p p Vmaxx the expected drift [[A(t)]S(t) s) satisfies the following conditions:
(i) There exists constants
0 and upt such that B[A(0)S(() s) & p when
(t) 2 :p: and
(ii) (t + (()) & Vmax holds with probability one:
then we have
2e
Bleso(tt) & Sc +
(21)
Sp
where Ç
taxx +mmaxp
D EXPERIMENTAL DETAILS AND ADDITIONAL EXPERIMENTS
D.1 EXPERIMENTAL DETAILS
In this section, we provide the experimental details of our evaluations. We first discuss the learning- to-rank dataset we use as the reward functions: Microsoft Learning to Rank. We use the MSLR- WEB30K dataset Qin & Liu (213) which is available at https: /www. mi micooofft.......m com/ ap-uu//researcc/proo ject /m/ This dataset has 31,278 arrivals, and the contextual di- mension 136. We extract |A| = 20 documents (arms) per query and the reward defined as the relevance judgments in the dataset which take 5 values from (irrelevant) to (perfectly relevant). We set the time horizon = 5000 and randomly draw an arrival from the 31,278 data points.
We then provide the hyperparameters of tested algorithms in our experiments.
Algorithm
Parameters
AUPD Algorithm
V 0.1byT
PGD Adaptive Chzhen et al. (2044)
My = 4VT + 2 5b = 1/VT
SquareCBwK Han et al. (2023)
U /T log 7 0.1/TIU
Table 2: Parameters in the experiment.
1.0
AUPD PGD Adaptive
0.8
Averaged Reward
SquareCBwK
0.6
0.4
0.2
0.0
1000
2000
3000
4000
5000
Figure 2: Budget = 30.
21

---

Published as a conference paper at ICLR 2025
Table Average cumulative rewards under various budgets.
B 30
B 100
B = 600
B 1000
Our Algorithm (AUPD)
0.105
0,233
0.238
0.344
PGD Adaptive
0.012
0.051
0.230
0.336
SquareCBwK 0.007
0.028
0.174
0.298
D.2 EXPERIMENTS UNDER OTHER BUDGET REGIMES
Recall the previous experiments with budgets B {100, 600, 1000} to represent different budget regimes (0(vT), (TT4/4), ( We consider the same setting and vary the budget with smaller budgets, where B (30). The experimental results are shown in Figure 2 which suggests that our algorithm adapts effectively to varying budget regimes and achieves much better performance as the budget decreases the constraints become tight. A summary of average cumulative rewards can be found in Table where the values for { (100, 600, 1000) are from Figure]
22


Reviews:
[{"review_id": "1LIWEFztiz", "reviewer": "Reviewer_Nbbq", "summary": "This paper studies the contextual bandits with knapsack problem under the small budget scenario. Previous research needs to know the safety margin of the budget constraint for their algorithms. This work gives an algorithm achieving the best known regret without knowledge of the safety margin. Furthermore, the algorithm can achieve sub-linear regret with not-strictly-feasible constraints in some cases.", "questions": "Question 1: What is the relationship between contextual bandits with knapsack and standard bandits with knapsack? Although we are working with contextual bandits, the final result does not rely on the context numbers. Is this due to the learning oracle? 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? \n\nQuestion 2: What is the existing lower bound for this problem? How large is the gap between the lower bound and the existing upper bound? Please discuss this point.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper gives a good contribution to a natural problem. The contextual bandit with small budget knapsacks is a natural problem. Existing research requires knowledge about the safety margin, which is hard to know. This paper gets rid of this demanding requirement. Furthermore, this paper gives the first result in the not-strictly-feasible case. \n\nThis paper is very well written. It is really easy to follow the paper. Everything is clearly defined and stated.\n\nOverall, I think this is a well written paper, makes a good contribution to a natural problem. I am happy to see it published.", "weaknesses": "This paper has few weaknesses; I would only suggest that the authors further discuss the relationship between contextual bandits with knapsack and standard bandits with knapsack, and provide the existing lower bound. Please see the specific questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vQXRAzh9T4", "reviewer": "Reviewer_UqkS", "summary": "The paper studies contextual bandit with knapsack in the small budget regime (B=o(T), B=\\Omega(T)).\nThe paper provides an algorithm which achieves O(sqrt(T)/(d*B/T)) without knowing \"slater\" action d and O(T^{3/4}/sqrt(B/T)) without strictly feasibility (d=0).", "questions": "What are the technical challenges that prevent adapting existing techniques such as \"Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression\" to this context? Is it true that the authors assume large budget, but it is not obvious that their framework cannot be used to solve the small budget case. At least this merits an explanation, which might also add relevancy to your technical contributions, which at the moment are not really highlighted.\nWhen are your results meaningful? For example, if B=sqrt(T), then the results are linear and meaningless in the case of no strictly feasible. It would be helpful to plot/discuss a B=T^alpha vs R_T tradeoff as a function of alpha.\nHow do your algorithms really solves the small budget? I fail to understand how your algorithm behaves differently when B=sqrt(T) or B=\\Theta(T).\nWhat would happen if you used one of the existing algorithms that do not use knowledge of the later parameter and applied it to the small-budget case?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The setting studied is interesting and not trivial and leads to intriguing scientific questions.", "weaknesses": "The paper is a bit difficult to read, and I think I could benefit from being inserted in a larger context with respect to prior/concurrent literature.\nFor example, the recent literature that considers bandits with constraints (of which bwk is a special case) has much more relevancy than what the authors seem to realize. In particular, I'm referring to\n\n[1] Raunak Kumar and Robert Kleinberg. Non-monotonic resource utilization in the bandits with\nknapsacks problem. In Advances in Neural Information Processing Systems (NeurIPS), 2022.\n[2] Bernasconi, Martino, Matteo Castiglioni, and Andrea Celli. \"No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization.\"\n[3] Slivkins, Aleksandrs, Karthik Abinav Sankararaman, and Dylan J. Foster. \"Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.\n[4] Bernasconi, Martino, et al. \"Bandits with Replenishable Knapsacks: the Best of both Worlds.\" The Twelfth International Conference on Learning Representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "odorbJptWI", "reviewer": "Reviewer_2HF3", "summary": "This paper studies the contextual bandits with knapsacks problem with a focus on when the budget is \"small\" (i.e., $B = \\Omega(\\sqrt{T})$). The authors present an algorithm with $\\sqrt{T}$ regret under the strict feasibility assumption and $T^{\\frac{3}{4}}$ regret without it. Notably, the algorithm does not need to know which of these two regimes it is in. The algorithm improves upon prior work by being a single-stage algorithm and by using the cumulative over-consumption of resources as a Lagrange multiplier.", "questions": "Questions:\n1. You claim that your algorithm is \"budget-aware\" because of the parameter $V = b \\sqrt{T}$, as opposed to $V = \\sqrt{T}$. I am wondering how crucial this choice is. Quantitatively, what would have been the regret bound had you chosen $V = \\sqrt{T}$? Qualitatively, where does including $b$ in the parameter help you in the proof?\n2. Why are the variables $Q_t^k$ called \"virtual queues\"? I'm trying to understand the motivation for this terminology and if there is a connection to literature on \"virtual queues\" that is helpful here.\n3. I understand the technical details proof of Lemma 5, but can you provide some intuition for how Lemma 4 is helpful for proving Lemma 5?\n4. Do you have thoughts on whether $T^{\\frac{3}{4}}$ can be improved when strict feasibility does not hold?\n\nMinor comments and typos:\n1. Line 314: \"is not necessary to hold\" -> \"does not necessarily hold\".\n2. Line 337: \"provide detailed proof\" -> \"provide a detailed proof\".\n3. Equation 8: This is a very minor nitpick, but I personally find it easier to parse the statement when it's written in the format $\\exists k$ s.t. {condition}.\n4. Line 346: Should this be denoted $a^*_t$ instead of $a^*$ since a different action will be sampled in different rounds depending on the context? Also, \"be the optimal action sampling from it\" -> \"optimal action sampled from it\".\n5. Line 363-364: What is $f$? Did you mean $r$?\n6. Line 368: Regret($x_t, a$) has not been defined before. But I guess it means $r(x_t, a^*_t) - r(x_t, a)$?\n7. Line 400-401: \"against the average usage $t \\times b$ for the round t\" - Isn't the average usage $b$?\n8. Line 418-419: This is a very minor nit, but I suggest rewording \"we have established\" to \"we establish\". When I first read this, I was wondering where this established in the paper so far. Then I read the full sentence and realized it is proved in the next lemma.\n9. Line 483-484: Did you mean 1a instead of 1b?\n10. Line 708-709: Should $c$ be $\\check{c}$?\n11. Line 981-982: It took me some time to understand what you meant by \"divide both sides\". It might be clearer to explicitly say that you divide both sides of the inequality inside the argmin.\n12. In Section B.3.1, you use Assumption 3. Then you use the resulting inequality (16) in Section B.4 where you don't assume Assumption 3. My guess is that this is ok since Eq 16 has a $-Q \\delta b$ term and you upper bound this by 0 in Section B.4? It might be good to be clear about this in Section B.3.1.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* Contextual bandits with knapsacks (CBwK) is an important model of online decision-making with many applications. This paper advances our knowledge in this area by improving upon an important limitation in existing work, namely, considering the regime of $B = \\Omega(\\sqrt{T})$ with and without strict feasibility. Their regret bound for the setting without strict feasibility is also the first such result.\n* The algorithm has some good features: it is simple and it does not need to know whether strict feasibility holds or not.\n* The choice to use the cumulative over-consumption as a Lagrange multiplier is a natural and effective idea.", "weaknesses": "* Overall, it's a well-written paper. But I would have loved to see some intuition behind the proofs of the lemmas in the main text. When I read through the proofs in the appendix, I followed the steps. But I still would have liked to see an explanation in words about the main ideas in the proof.\n* In the three settings considered in the experiments, the proposed algorithm is strictly better than the alternatives in only 1 setting; it is roughly the same as PGD Adaptive in the other two settings. It would have been nice to see other settings in which the proposed algorithm is strictly better than the alternatives.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ApqJM7IZTQ", "reviewer": "Reviewer_E8sG", "summary": "The paper studies stochastic contextual bandits with knapsack. In this model, at each round the learner observes a context before taking an action. The goal of the learner is to maximize its utility subject to a knapsack constraint. The paper presents an algorithm that guarantees an instance-dependent regret bound both with and without the strictly feasibility assumption. The paper provides meaningful guarantees even with budget $B=\\Omega(\\sqrt{T})$.", "questions": "The algorithm and the analysis look quite standard. Which are the technical difference and challenges with respect to previous works? Why is Lyapunov Drift more effective than previous approaches?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "It is the first paper to work without knowing the safe margin or without a safe margin.", "weaknesses": "The improvements with respect to previous works are minimal, and it is not clear the importance and technical challenges in removing the assumptions in previous works. Indeed, the assumption of a cost 0 \"do nothing\" action is fairly natural.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)