Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with Application to Fairness
Authors: Evgenii E Chzhen
Christophe Giraud
Zhen LI
Gilles Stoltz
Venue: NeurIPS 2023 poster (2023)
Keywords: mutli-armed bandits
bandits with knapsacks
primal-dual approaches
TL;DR: Motivated by a fairness application, we extend typical OPT/B \sqrt{T} results in contextual bandits with knapsacks to work with small total-cost constraints T B, that can be as close as possible to \sqrt{T}

Abstract: We consider contextual bandit problems with knapsacks [CBwK], a problem where at each round, a scalar reward is obtained and vector-valued costs are suffered. The learner aims to maximize the cumulative rewards while ensuring that the cumulative costs are lower than some predetermined cost constraints. We assume that contexts come from a continuous set, that costs can be signed, and that the expected reward and cost functions, while unknown, may be uniformly estimated---a typical assumption in the literature. In this setting, total cost constraints had so far to be at least of order $T^{3/4}$, where $T$ is the number of rounds, and were even typically assumed to depend linearly on $T$. We are however motivated to use CBwK to impose a fairness constraint of equalized average costs between groups: the budget associated with the corresponding cost constraints should be as close as possible to the natural deviations, of order $\sqrt{T}$. To that end, we introduce a dual strategy based on projected-gradient-descent updates, that is able to deal with total-cost constraints of the order of $\sqrt{T}$ up to poly-logarithmic terms. This strategy is more direct and simpler than existing strategies in the literature. It relies on a careful, adaptive, tuning of the step size.

Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with Application to Fairness
Evgenii Chzhen
Christophe Giraud
Université Paris-Saclay, CNRS, Laboratoire de mathématiques d' O'Orrayy 91405, Orsay, France fevgenii chzhen, christophe g
Zhen
BNP Paribas Corporate and Institutional Banking, 20 boulevard des Italiens, 75009 Paris, France zhen. li@bmpparibaar com
Gilles Stoltz
Université Paris-Saclay, CNRS, Laboratoire de mathématiques d' d'Orsay, 91405, Orsay, France HEC Paris, 78351 Jouy-en-Josas, France
gilles silllessstoltttuuuuvvrrstee-eeee sarisssalaaassssss..aa...... st:oltzheec..
Abstract
We consider contextual bandit problems with knapsacks [CBwK], problem where at each round, a scalar reward is obtained and vector-valued costs are suffered. The learner aims to maximize the cumulative rewards while ensuring that the cumulative costs are lower than some predetermined cost constraints. We assume that contexts come from continuous set, that costs be signed, and that the expected reward and cost functions, while unknown, may be uniformly estimated- typical assumption in the literature. In this setting, total cost constraints had far to be least of order 73/4 where T is the number of rounds, and were even typically assumed to depend linearly on T. We are however motivated to CBwK to impose fairness constraint of equalized average costs between groups: the budget associated with the corresponding cost constraints should be as close as possible to the natural deviations, of order vT. To that end, we introduce dual strategy based on projected- gradient-descent updates, that able to deal with total-cost constraints of the order of VT up to poly-logarithmic terms. This strategy is more direct and simpler than existing strategies in the literature. It relies on careful, adaptive, tuning of the step size.
Setting, literature review, and main contributions
We consider contextual bandits with knapsacks [CBwK], a setting where at each round > 1, the learner, after observing some context E X, where X' C TR" picks an action a, E .A in a finite set A. We do not impose the existence of null-cost action. Contexts are independently drawn according to distribution v. The learner may pick at random according to probability distribution, denoted by (x;) = (Tr, (xx)) aEAA for consistency with the notion of policy defined later in Scction 2 The action a, played leads to some scalar reward r E [o, 1] and some signed vector-valued cost C: E []. Actually, F, and c are generated independently at random in a way such that the conditional expectations of r, and given the past, H;, and ae equal r(æ az) and c(æ,, az), respectively. We denoted here by r X' x A + [0. 1] and c (CI...,, ca) X x A - [-1, unknown expected-reward and expected-cost functions. The modeling and the estimation of
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Box A: CONTEXTUAL BANDITS WITH KNAPSACKS [CBwK]
Known parameters: finite action set A; context set A' C R"; number of rounds; vector average cost constraints B E [0, 1]
Unknown parameters: context distribution
X; scalar expected-reward function
X' x - [0.1] and vector-valued expected-cost function с x A + [-1,1], both
enjoying some modeling allowing for estimation, see Section 2.2
For rounds 1,2,3.....
1. Context ~ / is drawn independently of the past;
2. Learner observes x, and picks an action a, E A, possibly at random according to distribution (xx (Tr. (Ri))ac.
3. Learner gets reward r, E [0, 0] with conditional expectation r(æ,, a.) and suffers constraints C₁ with conditional expectations c(2,, a.).
Goal:
Maximize
Σ 7
while ensuring
Σe CGTTB CST
The aim of the learner is maximize the sum of rewards (or equivalently, to minimize the regret defined in fection@] while controlling cumulative costs. More precisely, denote by B (BI.... Ba) E [0, 1 the normalized (i.e., average per-instance) cost constraints, which may depend on the coordinates. The number 7 rounds is known, and the learner must play in a way such that e₁ + ... CT TB. The example of Section 2.1 illustrates how this setting allows for controlling costs in absolute values. The setting described is summarized in Box A.
and discussed in Section 2.2
Overview of the literature review. Contextual bandits with knapsacks [CBwK] is setting that is combination of the problems of contextual bandits (where only rewards are obtained, and no costs: see, among others. [Lattimoee and Szepesvári 2020) Chapter 18 for survey of this rich area) and of bandits with knapsacks (without contexts, as mitially introduced by Badanidiyuru et al.) 2013 2018).
The first approaches to CBwK (Badanidiyuru al., 2014 Agrawal al. (2066) relied
specific modeling of the rewards and costs, and made the problem tractable by using as a benchmark a finite of so-called static policies (but picking this set is uneasy, as noted by Agrawal and Devanur 2016). Virtually all subsequent approaches to CBwK thus introduced structural assumptions in one way or the other. The simplest modelings are linear dependencies of expected rewards and costs on the contexts (Agrawal and Devanur (0166) and a logistic conversion model (Li and Stoltz 2022). ) The problem of CBwK attracted attention in recent past: we discuss and contrast the contributions by Chohlas Goood et al. [2021), Slivkins et al. [2022). Han et al.) 2022 Ai et al. 2022 and Stoltz 2022 after stating our main contributions.
Overview of our main contributions. Fach contribution calls or allows for the next one.
1. This article revisits the CBwK approach by [hhhlaas Wood al. [2021] to problem of fair spending of resources between groups while maximizing some total utility. Fairness constraints require to deal with signed costs and with possibly small total-cost constraints (typically close to T2),,, while having null-cost action at disposal.
We therefore provide a new CBwK strategy dealing with these three issues, the most significant being handling cost constraint T as small ///2+e, breaking the state-of-the-arn 3/4 barrier for CBwK with continuous contexts, while preserving attractive computational efficiency.
This new strategy is a direct, simple, explicit, dual strategy, relying on projected crojected-gradient-eee gradient-descent updates (instead of using existing general algorithms as subroutines). We may perform an ad hoc analysis. The latter leads to refined regret bounds, in terms of the norms of some optimal dual variables. We also discuss the optimality of the results achieved by offering a proof scheme for problem-dependent (not only minimax) regret lower bounds.
1.1 Detailed literature review
We now contrast our main contributions to the existing literature.
CBwK and fairness: missing tools. In the setting of Chohlas Wood et al. [021] there is budget constraint on the total spendings on top the wish of sharing out these spendings among groups (possibly favoring some maximal extent some groups that are more in need). However,

---

Chohlas- Wood et al. [02TT]
incorporated the fairness constraints in the reward function (through some Lagrangian penalty) instead of doing so in the vector-cost function, which does not seem the most natural way to proceed. One reason is that (see a discussion below) the total cost constraints TB were so far typically assumed to be linear, which undesirable in fairness applications, where one wishes that TB is sublinear and actually, is sometimes as close as possible to the natural vT deviations suffered even in perfectly fair random allocation scheme. Also, there is no null-cost action and costs are signed-tve two twists to the typical settings of CBwK that only (Slivkins et al. [2022] and our approach deal with, to the best of our knowledge. We describe our alternative modeling of this fairness problem in Section 2.1
Orders of magnitude for total-cost constraints TB. The literature so far mostly considered linear total-cost constraints TB (see, e.g.. HHan et al.) 2022 or Ai et al. 2022 among recent references), with two series of exceptions: (i) the primal strategy by Li and Stoltz [022] handling total-cost contraints of the order of vT up to voly-logarithmic terms but critically assuming the finiteness of the context set X: and (ii) the wto-stage dual strategies of AAgawal and Devanur (2016), Haan et al. 2022) handling 7 total-cost constraints. These two-stage strategies use vT preliminary rounds to learn some key hyperparameter Z and then transform strategies that work with linear total-cost constraints into strategies that may handle total-cost constraints larger than T3/4; see discussions after Lemma 2 In contrast, we provide general theory of small cost constraints for continuous context sets, while obtaining similar regret bounds as the literature does: for some components j. we may have TB₁ < T3/4 (actually, any rate TB; > 11/2-é is suitable for sublinear regret), while for other components k, the total-cost constraints TB may be linearly large.
Typical CBwK strategies: primal approaches suffer from severe limitations. CBwK is typically solved through dual approaches, as the latter basically rely learning finite-dimensional parameter given by the optimal dual variables X (see the beginning of Section 3). while primal approaches rely on learning the distribution y of the contexts in LL distance. This may be achieved in some cases, like finiteness of the context set 2' (Li and Stoltz, 2022 Ai et al. 2022) or, at the cost of degraded regret when resorting to ..--denity-estimaan
bounds and under additional assumptions
techniques
(Ai et al., 2022). On top of these strong limitations, such primal approaches are also typically computationally inefficient as they require the computation of expectations over estimates of v.
Typical CBwK strategies: dual approaches are modular and somewhat indirect. Typical dual approaches in CBwK take two general forms. One, illustrated in (Slivkins et al. [2022] (extending the non-contextual approach by Immorlica et al. 2019 takes a game-theereticc approach by identifying the primal-dual formulation (4) as some minimax equilibrium, which may be learned by separate regret minimization of a learner picking actions ay and an opponent picking dual variables A The second approach (Agrawal and Devanur 2016 Han et al. (022) > learns more directly the X, via some online convex optimization algorithm fed with the suffered costs e₁; this second approach however requires, the stage of picking at, a suitable bound Z on the norms of the X
The dual strategies discussed above are modular and indirect as they all consist of using building blocks some general-purpose strategies. We rather propose a more direct dual approach, tailored to our needs. (We also believe that it is simpler and more elegant.) Our strategy picks the arm a, that maximizes the Lagrangian penalization of rewards by costs through the current X (see Step 2 in Box B), as also proposed by Agrawal and Devanur (2016) (while Han et al.) 2022 add some randomization to this step), and then, performs some direct, explicit, projected-gradien--eesee update on A to obtain A,, with step size 7. We carefully and explicitly tune 7 (in sequential fashion, via regimes) to achieve our goals. Such fine-tuning is more difficult to perform with approaches relying on the black-box use of subroutines given by existing general- pprppoee strategies.
Regret (upper and lower) bounds typically proposed in the CBwK literature. A final advantage of our more explicit strategy is that we master each piece of its analysis: while not needing null- cost action, we provide refined regret bounds that go beyond the typical (OPT(r, c, B) min B) bound offered by the literature so far (see, among others, Agrawal and Devanur] 2016 Li and Stoltz, 2022 Han et al. 2022). where OPT(r, c, B) denotes the expected reward ac achieved by the optimal static policy (see Section for definitions). Namely, our bounds are of the order of || V[,, where A is the optimal dual variable; we relate the norm of the latter to quantities of the form (OPT(r, c, B) - OPT(r, c, B)) ((1-o) a) min B), for some a < 1. Again, we may do so without the existence of a null-cost action, but when one such action is available, we may take = 0 in the interpretation of the bound. We also offer a proof scheme for lower bounds in Section 4 and
3

---

explain why | VT appears as the correct target. We compare therein our problem- dependent
lower bound-approach the minimax ones of Han et 2022 and Slivkins et al. [2022]
1.2 Outline
In Section further describe the problem of CBwK (by defining the regret and recalling how and e may be estimated) and state our motivating example of fairness. Section Bs devoted to our new dual strategy, which we analyze first with fixed step size y, for which adaptive version, and whose bounds we finally discuss. Section 4 offers a proof scheme for regret lower bounds and lists some limitations of our approach, mostly relative optimality.
move next to an
2 Further description of the setting, and statement of our motivating example
We define a static policy as mapping : X - P(A), where P(A) denotes the set of probability distributions over A. We denote by π = (TA) the components of т. We let Ex~, indicate that the expectation is taken over the random variable X with distribution v. In the sequel, the inequalities & or between vectors will mean pointwise satisfaction of the corresponding inequalities.
Assumption 1. The contextual bandit problem with knapsacks (r, c, B', v) is feasible if there exists a stationary policy π such that
(x) [x(X(a))a(() B'.
Ex mov
LAEA
We denote the average cost constraints by B' in the assumption above as in Section 3 we will actually require feasibility for average cost constraints B' < B, not just for B.
In feasible problem (r, c, B', v), the optimal static policy π defined as the policy π : X + P(A) achieving
OPT(r, c, B') = sup Ex
Σ a) TT (x(
Exav
Σ c(X a) (X(
< < B'
(1)
LaEA
LaEA
T
Maximizing the sum of the ry amounts to minimizing the regret R = ToPT(r, B')
Σ rt-
2.1 Motivating example: fairness equalize average costs between groups
This example is inspired from Chohlas Wood et al. [2021] (who did not provide strategy to minimize regret), and features total budget constraint T T'Bual together with fairness constraints on how the budget is spent among finitely many subgroups, whose set is denoted by G. We assume that the contexts x, include the group index gr(æ::) E G, which means, in our setting, that the learner accesses this possibly sensitive attribute before making the predictions (the so-called awareness framework in the fairness literature). Each context- action pair (x, a) E X x A, on top of leading to some expected reward r(x, a), also corresponds to some spendings Gpp (x, a). We recall that we denoted that re (a,
and o (here, this is a scalar for now) the individual payoffs and costs obtained at round f; they have conditional expectations r(z,, az) and (Z at). We want to trade off the differences in average spendings among groups with the total reward achieved: larger differences lead to larger total rewards but generate feelings of inequity of public money not optimally used. (Chohlas- Wood et al. [2021] consider a situation where unfavored groups should get slightly more spendings than favored groups.)
Formally, we denote by gr(x:) E G the group to which given context x belongs and introduce tolerance factor т, which may depend on T'. We issue a simplifying assumption: while the distribution of the contexts is complex and is unknown, the respective proportions % =v(x x gr(x) g) of
the sub-groups may be known p The total-budget and faimess constraints then read:
T
T
T
Σ
c. & T Boal
and
Agg E 9,
Σ a a1
Σ
Co
ET.
Thg
T
'This simplification not unheard in the fairness literature; see, for instance, Chzhen et 2021 amounts to having a reasonable knowledge of the breakdown of the population into subgroups. We use this assumption to have an easy rewriting of the fairness constraints in the setting of Box A. The knowledge of the Ny is key for determining the everage-constrain vector B.

---

which corresponds, in the setting of Box A, to the following vector-valued expected-cost function with d = 1 + || components and with values in [-1, 1]1111) (S,( a). (Squ(ar, a) (Br(#)=g) - ( (2,a),))))))))))()) a), (x, a) Cap a) (B(())=9)) 9E9)
c(2, a)
well to the average-constrait vector B (Buatt (7s T, "ig r) 9EG)
The regimes we have in mind, and that correspond to the public-policy issues reported by (Chhhlas Wood et al. [022]] J. are that the per-instance budget Buea is larger than positive constant, I.e., constant fraction of the T individuals may benefit from some costly action(S), while the fairness threshold must be small, and even, small as possible. Because of
fluctua- tions, minimal value of the order of 1/ I/VT, or slightly larger (up to logarithmic terms, say), has to be considered for 7. The salient point that the components of B may therefore be of different orders magnitude, some of them being as small as 1/VT,, up to logarithmic terms. More details on this example and numerical simulations about it are provided in Section 3 and Appendix G
2.2 Modelings for, and estimation of, expected-reward and expected-cost functions
As is common in the literature (see Han et 2022 and Slivkins et al. 2022, who use the terminology of regression oracles), we sequentially estimate the functions r and c and assume that we may do so in some uniform way, e.g.. because of the underlying structure assumed. Note that the estimation procedure of Assumption 2 below does not force any specific choice of actions, it is able to exploit actions a, picked by the main strategy (this what the "otherwise" related to therein). We denote by F, X' x A + [0, 1] and C₁ X' x A - [-1, 1]d the estimations built based on (Iz, Ts. for / > 1. We also assume that initial estimations To and Co. based on no data, are available. We denote by 1 the column-vector (1....,1), 1).
T'.. C.)egt-
There exists an estimation procedure such that for all individual sequences of contexts I1. .2..... and of actions a1, ...... played otherwise, there exist known error functions E, : A x (0, 1] - [0, 1]. relying each on the pairs (Iz, 0z) where 0, 0,1,2, 2.... ensuring that for all 5 E (0, 1), with probability at least 1 5,
Assumption
vO < l & T, VE E N, Va E A,
[r(2r, a) - r(x, a) & a, (2(1, c(x, a) & a,
and
where we assume in addition that BT def
6t (Z), az 0) o
0( VT (VTTI T 5
This assumption is satisfied at least for the two modelings discussed below, which are both of the form: for known transfer functions so, link functions Q and normalization function 17, for some unknown miteedimennsionll parameters pe, O.,1...., 0 O.,d Va X, Va A,
r(a, a) 1 (a, 2)) (, a) 1s.) c( a) (a, .)) Pe a) 0..))
and for all < & d,
See also the exposition Han et al. [002 Section 3.3].
Based on Assumption 2 and given the ranges [0, 1] for rewards and 1-,, for costs, we may now define the following (clipped) upper- and lower-confidence bounds given a confidence level 1 8 where 5 (0, 1), for all & T, for all X' and A.
ucb Th
(x. a) def clip(fo(z, a) +E( a, 8)]g and Ci a) def cliple, = a, 0)
(2)
where define clipping by clip[z]y min max(xx, (x, u} for scalar value R and lower and upper bounds & and u, and apply clipping component-wise to vectors. Under Assumption that for all 8 (0, 1], with probability at least 8, 1.
2 we have
4A T, Vx X, Va E A,
r(z, a) < (x, a) < r(x, a) 2x, a, F.
(3)
and
c(x,a) - 28, (xc, a, 0) & 25 < c(æ;, a).
Doing so, we have optimistic estimates of rewards (they are larger than the actual expected rewards) and of costs (they are smaller than the actual expected costs) for all actions a, while for actions de+1 played, and only these, we will also use the control from the other side, which will lead to manageable sums of Ez Ee(x++1, a++1, ö), given the control on ST,s & by Assumption 2
5

---

Linear modeling. Agrawal and Devanur [2016] (see also Li and Stoltz 2022 Appendix E) consider the case of linear modeling where 7)- 77
Modeling 1:
Ta 1 and + the identity (together with assumptions on the range of &p and on the norms of μ4, and the 0.,)). The LinUCB strategy by Yabasii Yadkori et al. (2011) may be slightly adapted (to take care of the existence of transfer function &p depending on the actions taken) to show that Assumption 2 holds; see and Stoltz 2022 Appendix E, Lemma 3j.
Modeling 2: Conversion model based on logistic bandits. Li and Stoltz 2022 Sections 1-5] discuss the case where ((x) 1/(1+ + for rewards and costs. The Logistic- UCBI algorithm of Faury et al. 2020) (see also an earlier version by Filippi et al., 2010) may be slightly adapted (again, Lemma I in Appendix B, as
because of (p) to show that Assumption hholds; see Li and Stoltz 2022
well as Appendix CJ.
3 New, direct, dual strategy for CBwK
Our strategy heavily relies on the following equalities between the primal and the dual values of the problem considered. The underlying justifications are typically omitted in the literature (see, e.g.. Slivkins et al., 2022, end of Section 2); we detail them carefully in Appendix[A] We introduce dual variables À E 00 +oo)%, denote by (..)) the inner product in RR and we have, provided that the problem (r, c, B', v) is feasible for some B' B:
OPT B)
sup (PA) 2
inf Ex
Σ
A,
A, B
c(X, (a) (x)
LEEd
aEA
Σ (X) (((x,a) (e((X B, 21)
min
sup ((A-((
Ex~V
A
LaEA
(X, (c(X B, 2)}1
min E Ex A
max aEA
We denote by AB vector X 0 achieving the minimum in the final equality. Virtually all previous contributions to (contextual) bandits with knapsacks learned the dual optimal X in some way; see the discussion in Main contribution #3 in Section T Our strategy is stated in Box B. A high-level description is that it replaces (Step 2) the ideal dual problem above by an empirical version, with estimates of r and C, with the expectation that it sequentially chooses some X based on projected-gradient-deseee
X ~ // replaced by point evaluation 2t, and
steps (Step 4 uses the subgradient of the function in defined in Step 2). The gradient-descent steps are performed based
on fixed step sizes y in Section 3.1] and Section 3.2 will explain how to sequentially set the step sizes
based on data. We also take some margin b1 on B.
Box B: PROJECTED GRADIENT DESCENT FOR CBwK WITH FIXED STEP SIZE
Inputs: step size 7 > 0; number of rounds T': confidence level 1 g; margin b the
average constraints; estimation procedure and error functions e, of Assumption 2 optimistic
estimates 2
Initialization: Ao 0; initial estimates Ruuch and C50
ldb
For rounds
= 1, 3,.., T:
1. Observe context æt;
2. Pick an action a, achieving
max ( a)
lbb ( -(B))(-B-- (bb1), )
3. Observe the payoff r; and the costs C;; az) (B 61))
4. Compute X, ( +
5. Compute the estimates Pub and G6.

---

3.1 Analysis for fixed step size Y
The strategy of Box B is analyzed through two lemmas. We let min min(............................ v2) denote the smallest component of vector (0, xx) and take margin b in (0, min B). We assume that the problem feasible for some B' < B h1, and denote by X AB-01 the vector achieving the minimum in (4) when the per-round cost constraint is B b1. We use
for the Euclidean norm. andd 2 critically rely on B ll. which we bound and interpret below in
The bounds of Lemmas
Section 3.3
We denote
T
27 2(d + 1)T 6/4
TT. max B1,5/1 2 dT'n
8/4"
Lemma 1. Fix 8 E (0, 1) and 0 < b < min B. If Assumption 2 holds and if the CBwK problem is feasible for some B' B b1, the Box B strategy run with 6/4 ensures that the costs satisfy, with probability at least - 8.
Ee, C t b1)
1 1+3 1B m1l 20V
VIETET,
Lemma 2. Fix E (0, and 0 < b < min B. Under the same assumptions as in Lemma 1 and on the same event with probability at least 8 as therein, the regret of the Box B strategy run with 8 satisfies
T2
VIETET,
Rs < 12 I (Ilv
36 (Tr:s) 8ln
8/4"
Idell choice of 7. The margin will be taken proportional to the high-probability deviation provided divided by T. Now, the bounds of Lemmas [ and are respectively of the order
by Lemma D
Tb (1 | 11/1/1>//-- VT
and
| b1 (Tb VT) +TT,
again, up to logarithmic factors. To optimize each of these bounds, we therefore wish that b be of order 1/vT and that be of the order of || lo--alll/V..... Of course, this wish stumbles across the same issues ignoring a beforehand bound on | ll. exactly like, e.g., in Agrawal and Devanur (2066), Han al. [2022] (where this bound is denoted by 2). We were however able overcome this issue in satisfactory way, i.e., by obtaining the ideal bounds implied above through adaptive choices of 7, discussed in Section 3.2
Suboptimal choices of y. When is badly set, e.g., 7 1/vT, the order of magnitude of the regret remains larger than || Tb and the cost deviations to T(B b1) become of the larger order B a1 VT, which dictates a larger choice for Tb. Namely, if in addition || || is bounded some worst-case way by 1/ min B (see Section 3.3). the margin Tb is the order of /T/ min B. But of course, this margin must remain smaller than the total-cost constraints T'B. This the fundamental source of the typical min > - constraints on the average cost constraints B observed in the literature: see, e.g.. Agrawal and Devanur 2016 Han et al. 2022 where the hyperparameter Z plays exactly the role of [
Proof sketch. Lemmas I and 2 are proved in detail in Appendix B the two proof's are similar and we sketch here the one for Lemma | The derivations below hold on the intersection of four events of probability at least 5/4 each: one for Assumption 2 one for the application of the Hoeffding- Azuma inequality, and two for the application of a version of Bernstein's 's inequality. In this sketch of proof, S denotes inequalities holding up small terms.
By the Hoeffding-Aree Azuma inequality and by Assumption 2 the sum of the c, - (B b1) is not much B bl). We bound the latter by noting that
larger than the sum of the Ač_- = -08/4,5-1 (I=, ax)
lch
by definition, X, > A + AA,, so that after telescoping.
|
|| .1 Aell
(B (B-- 61)
x
(5)
+
We are thus left with bounding the 1X analyses (see, c.g., Zinkevich 2003) reads:
>
The classical bound in (projected) gradient-descent
7

---

E
|| X -61l11 | A 12-b1 112 (7, - 7 -
The estimates of Assumption and the definition of at the argument of some maximum, entail
(Ac,, - Ai1-1) (C8/4.--1 1 a+) (BB-))), 2-11 a1) - 9r (> B-)1 - 9r (2,-1),
r r( a) - (c(2), (B b1), }
where
gr gr = max
aEA
We also introduce Ar = Vd max 1ErEl
X - Ar- We sum up the bounds above, use telescoping,
and get
1 B-- 2 | a1l 4d 27
Σ gr (A 51) 9r 9- (2,-1), T
(6)
2043A (ll(TT/)
where the S of the sum in the right-hand side comes from a version of Bernstein's inequality, the fact that IE (> (b)) = OPT(r, B b1) is larger than the conditional expectation of g- (Xy-1).
Since (6) holds for all f, we may then show by induction that for some constants D and A,
| X b1 E x will + ByTr,
and we conclude by substituting this inequality into S
3.2 Meta-stategy with adaptive step size 7
As indicated after the statements of Lemmas] I and we want (meta-)strategy adaptively setting learn Bo We do via a doubling trick using the Box B strategy as routine and step sizes of the form 7/. = 2 /VT regimes > O; the resulting meta-strategy is stated in Box C (a more detailed pseudo-code is provided in Appendix C). As the theorem below will reveal, the margin b therein can be picked based solely on T, 5, and d.
Box C: PROJECTED GRADIENT DESCENT FOR CBwK WITH ADAPTIVE STEP SIZE
Inputs: number of rounds T: confidence level - 8 margin b on the average constraints; estimation procedure and error functions E, of Assumption 2
optimistic estimates 2
Initialization: To = 1; sequence = 2* VT of step sizes;
sequence MT,3,K = 4VT + 20 Tr.s/(422)) of cost deviations
For regimes h 0, 1,
Take a fresh start of the Box B strategy with step size %ks risk level 5/ and margin b;
5/(4(A: (4(k: + 2))),
ct- b1))
Run it for t Ta until
Mr...i >MrBBi
T=T
Stop regime k and move to regime 1 for the next round, i.e., Ts+1 = =t+1.
Bandit problems containing a null-cost action (which is a typical assumption in the CBwK literature) feasible for all cost constraints B' > O; the assumption of (B 2)y f-aasibilltt in Theorem below is therefore a mild assumption. Apart from this, the following theorem only imposes that the average cost constraints are larger than 1/ VT, up to loly-logarithmic terms. We let Ô denote orders of magnitude T up to yoly-logari terms.
For æ > 0, we denote by ilog x = [log2 x1 the upper integer part of the base-2 logarithm of x. Theorem 1. Fix 10 and let Assumption hold. Consider the Box meta-strategy, run with confidence level 8 and with margin by =
TT (My &.ilog + 2/d) /T ((1/VT). If the average cost constraints are such that > 2br and if the problem (r, c, B 2br 1, is feasible, then this meta-strategy satisfies, with probability least 1 6:
8

---

Rr & ((+ (,
and
Σ c S TTB.
TB.
1ET where a fully closed-form, non-asymptotic, regret bound is stated in (19) in Appendix C
A complete proof may be found in Appendix C Its structure is the following; all statements hold with high probability. We denote by & the realized lengths of the regime. First, the number of regimes is bounded by noting that if regime K = ilog - || is achieved, then by Lemma [ and the choice of Mr,,, the stopping condition of regime K will never be met; thus, at most ' + 1 regimes take place. We also prove that ilog 1XB-brill & KT ilog T. Second, on each regime k. the difference of cumulated costs to & [ by is smaller than Mr,,5. a by design, so that the total cumulative costs are smaller than T by plus something of the order of (KT + 1) MT, Kr which is a quantity that only depends on T, 6, d, and not on the unknown | and that we take for T by. Third, we similarly sum the regret bounds of Lemma over the regimes: keeping in mind that bt = (VTT), we have sums of the form
\ byi
Σ (bTlx VT) < I b 0l and K
Σ kEK
TT
2k+1
A B
by
VT
3.3
Discussion of the obtained regret bounds
The regret bound of Theorem features a multiplicative factor || B B-br1 instead of the typical
factor (PT(r, C, / min B proposed by the literature (see, e.g., e.g.,,.Araaar.. [Agraal and Devanur 2016 Li and
Stoltz
2022 Han et al. 2022). In view of the lower bound proof scheme discussed in Section
this bound B 1 v seems the optimal bound. We thus now provide bounds on || A that have some natural interpretation. We recall that feasibility was defined in Assumption The elementary proofs of Lemma 3 and Corollary
[
based on (4) and may be found in Appendix D
Lemma 3. Let b E [0, min B) and let O & B B b1. If the contextual bandit problem with knapsacks (r, c, B', Bv) is feasible for some B' B, then
|A b1ll & OPT(r, e, B - b1) OPT (r, (r, B)
min (B b1 B Corollary 1. When there exists a null-cost action, all E [0, min B/2].
OPT c. B) - OPT((: c, 0) -1ll < B
for
min B
The bounds provided by Lemma 3 and Corollary | must be discussed in each specific case. They are null (as expected) when the average cost constraints B are large enough so that costs do not constrain the choice of actions; this was not the case with the typical OPT(r, c, B)/ min B bounds of the literature. Another typical example is the following.
Example 1. Consider a problem featuring a baseline action omn with some positive expected rewards and no cost, and additional actions with larger rewards and scalar expected costs c(æ, a) > a > O. Denote by B the average cost constraint. Then actions a o Gum may only be played at most B/o times on average, and therefore, OPT(r, c, B) OPT(r, (rrrr,,,)) & B B/o. In particular. the bound stated in Corollary [ may be further upper bounded by 1/(2x), which is fully independent of T and B; ie.. -T-regret
VT regret only is suffered in Theorem 7
4 Optimality of the upper bounds, and limitations
The main limitations to our work are relative, in our eyes, to the optimality of the bounds achieved- up to one limitation, already discussed in Section 2.1 our faimess example is intrinsically limited to the awareness set-up, where the learner has access to the group index before making the predictions.
A proof scheme for problem-dependent lower bounds. Results offering lower bounds on the regret for CBwK are scarce in the literature. They typically refer to some minimax regret, and either do so by indicating that lower bounds for CBwK must be larger in minimax sense than the ones obtained for non-contextual bandits with knapsacks (see, e.g., Agrawal and Devanur 2016, Li and Stoltz 2022), or by leveraging a minimax regret lower bound for subroutine of the strategy used (Slivkins et al. 2022). We rather focus on -eeeem-deepenent regret bounds but only offer proof scheme, to be made more formal see Appendix E.I Interestingly, this proof scheme follows closely the

---

analysis of a primal strategy performed in Appendix F First, an argument based on the law of the iterated logarithm shows the necessity of a margin by of order 1/vT to satisfy the total TB cost. constraints. This imposes that only ToPT(r, c, B by 1) is targeted, thus the regret least of order
T(OPT(r, e, B) OrT e, B by1)) + VT, i.e.
(1+
This matches the bound of Theorem D but with A replaced by XBB
We now turn to the list of limitations pertaining to the optimality of our bounds.
Limitation 1: Large constants. First, we must mention that in the bounds of Lemmas I and 2 did not try to optimize the constants but targeted readability. The resulting values in Theorem [ namely, the recommended choice of by and the closed-form bound (99) on the regret, therefore involve constants that are much larger than needed.
Not capturing possibly fast regret rates in some cases. Second, careful inspection of our proof scheme lower bounds shows that it only works in the absence of null-cost action. When such null-cost action exists and costs non-negative, Example shows that costly actions played at most B/a a times on average. If the null-cost action has also a null reward, the costly actions are the only ones generating some stochasticity, thus, expect that the v'T factors (coming, among others, from a version of Bernstein's 's inequality) be replaced by v B/a factors. As a consequence, in the setting of Example bounds growing much slower than v should be achievable, the discussion in Appendix
Limitation 2:
Limitation 3: VT regret not captured in case of softer constraints. For the primal strategy discussed in Appendix F we could prove general vT regret bound in the case where total costs smaller than TB + (VVT) are allowed. We were unable to do so for our dual strategy.
Brief overview of the numerical experiments performed
In Appendix G implement specific version of the motivating example of Section 2.1
as proposed by Chohlas-Wood et al. (2021] in the public repository h com/ stanford wwwerddpoocyyyyyllllboaaa hawplaaabaeaannngg... bo- Fairness costs together with spendings related to rideshare assistance or transportation vouchers are considered. We report below the performance of the strategies considered only in terms of average rewards and rideshare costs, and for the fairness threshold r = 10-7, The Box B strategies with fixed step sizes may fail to control the budget when large: we observe this for y 0.01. We see overall tradeoff between larger average rewards and larger average costs. The Box C strategy navigates between three regimes, Y = 0.01 to start (regime k = 0), then y 0.02 (regime kt = 1), and finally 7 = 0.04 (regime k 2), which sticks to. It overall adaptively finds a decent tuning of
Ganma Cuems 94
0.49
0.09
Average Rewards
carna 04
Rideshare Costs
0.48
0.08
0.46
0.06
0.45
0.44
2000
4000
6000
8000
10000
0.04
20000
4000
6000
8000
10000
Acknowledgments and Disclosure of Funding
Evgenii Chzhen, Christophe Giraud, Zhen Li, and Gilles Stoltz have no direct funding to acknowledge other than the salaries paid by their employers, CNRS, Université Paris-Saclay, BNP Paribas, and HEC Paris. They have no competing interests to declare.
10

---

References
Y. Abbasi-Yadkort Pál, and Szepesvári. Improved algorithms for linear stochastic bandits, In Advances in Neural Information Processing Systems (NeurIPS'1I), volume 24, 2011.
S. Agrawal and N. Devanur. Linear contextual bandits with knapsacks. In Advances in Neural Information Processing Systems (NeurIPS' 16), volume 29, 2016.
Agrawal, N.R. Devanur, and L. Li. An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives. In Proceedings of the 29th Annual Conference on Learning Theory (COLT 16), volume PMLR:49, pages 18, 2016.
R. Ai, Z. Chen, X. Deng, Y. Pan, C. Wang, and M. Yang. On the re-solving heuristic for (binary) contextual bandits with knapsacks, November 2022. Preprint, arXiv:2211.1329 1319552.
A. Badanidiyura, R. Kleinberg, and A. Slivkins. Bandits with knapsacks. In IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS'13), pages 207-216, 2013. Latest extended version available at arXiv: 1305.2545, dated September 2017.
A. Badanidiyuru, J. Langford, and A. Slivkins. Resourceful contextual bandits. In Proceedings of the 27th Conference on Learning Theory (COLT" volume PMLR:35, pages 1109-1134, 2014.
A. Badanidiyuru, R. Kleinberg, and A. Slivkins. Bandits with global convex constraints and objective. Journal of the ACM, 65(3):155,, 2018.
N. Cesa- BitaaaBaanchi..coo G. Lugosi, and G. Stoltz. Minimizing regret with label-efficient prediction. IEEE Transactions Information Theory, 51:2152-2162, 2005.
A. Chohlas-Wodd M. Coots, H. Zhu, E. Brunskill, and S. Goel. Learning be fair: A consequentialist approach to equitable decision-making making, 2021. Preprint, arXiv:2109.08792
E. Chzhen, C. Giraud, and G. Stoltz. A unified approach to fair online learning via Blackwell approachability. In Advances in Neural Information Processing Systems (NeurIPS' volume 34, 2021.
Devroye and L. Györfi. Nonpurametric Density Estimation: The The View. John Wiley Sons, 1985.
L. Faury, M. Abeille, C. Calauzenes, and O. Fercoq. Improved optimistic algorithms for logistic bandits. Proceedings of the 37th International Conference on Machine Learning (ICML 20), volume PMLR: 19,, pages 3052-3060, 2020.
S. Filippi, O. Cappe, A. Garivier, and C. Szepesvári. Parametric bandits: The generalized linear case. In Advances Neural Information Processing Systems (NeurIPS' 10), volume 23, 2010.
David A Freedman. On tail probabilities for martingales. The Annals of Probability, pages 100-118, 1975.
Y. Han, J. Zeng, Y. Wangy, Y. Xiang, and J. Zhang. Optimal contextual bandits with knapsacks under realizability via regression oracles, October 2022. Preprint, arXiv:2210.118.. 11834.
N. Immorlica, K.A. Sankararaman, R. Schapire, and A. Slivkins. Adversarial bandits with knapsacks. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS' 19), pages 202-219, 2019.
T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Z. Li and G. Stoltz. Contextual bandits with knapsacks for conversion model. In Advances in Neural Information Processing Systems (NeurIPS 22), volume 35, 2022.
D. Luenberger. Optimization by Vector Space Methods. Series in Decision and Control. John Wiley & Sons, 1969.
A. Slivkins, K.A. Sankararaman, and D.J. Foster. Contextual bandits with packing and cover- ing constraints: modular Lagrangian approach via regression, November 2022. Preprint, arXiv:2211.0748.
11

---

A.B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, 2008.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML'03) pages 928- 935, 2003.
12

---

A Proof of the strong duality
4
In this section, we explain why the equalities 44 hold when the problem (r,, c, ,V) is feasible for some B' < B. We restate first these incqualities for the convenience the reader:
OPT(T, c, B)
sup
inf Ex~y 230
Σ r(( (a)) A, B Σ
c(X, a(x,a) (a)
-PA)
LEEd
aEA
Σ (a( (((x,a)((c(x,0))))
- (c(X.a) (c B, 21)
min
sup m: P(A)
Ex
LAEA
r(x, a) ((xx x)
min 0
E x
max aEA
We deal here with linear program, with primal variables in functional space X' - R- and dual variables in the mnite-dimensional space R.
The first and third equalities are straightforward. The first equality holds because in OPT(r, c, B). we want to consider only policies with expected cost smaller than or equal to B; the infimum over A > O equals -oo for policies with expected costs strictly larger than B and is achieved at À = 0 otherwise. The third inequality follows from identifying that for given X, the best policy may be defined pointwise as the argument of the maximum written in the expectation. Thus, only the middle equality (+) deserves proof. We obtain it by applying general theorem of strong duality (which requires feasibility for slightly smaller cost constraints).
Statement of general theorem of strong duality. We restate result extracted from the mono- graph by Luenberger [1699]. It relies on the dual functional whose expression we recall below. Theorem 2 (stated as Theorem 1 in Section 8.6, page 224 in [ueenbeegr 1969). Let f be a real- valued convex functional defined on a convex subset of vector space X, and let G be a convex mapping of X into a normed space Z. Suppose there exists an Φ such that G(x1) < 0 and that Ho = inf (ff()(()= f(x) G(x) & 0, x E L} is finite. Then
inl [() = max y(=*)
G(z)
x" 30
and the maximum on the right is achieved by some 2 >> 8.
The dual function is defined as follows (Luenberger] 1969 pages 215, 223, and 224, which we quote). We denote by P a positive convex cone C Z, and p {2* E Z* Ve P. (2, 2*) > 0} be its corresponding positive cone in the dual space Z*. The dual functional is defined, for each element 2* E P p(z") inf [f(x) + (G(x), x*)).
=eil
Application. To prove the middle equality (+), we apply Theorem 2 with the vector space X of all functions X' - R.A, its convex subset formed by functions X' ((A), and note that the function is actually linear in our situation:
f(x) = -
Σ rrx a) n (x)
LaE
(We take sign to match the form of the minimization problem over in Theorem 2
We take
= Rd Z with positive cones P p = [0, +20 The mapping a linear mapping from X Rd:
G(T)) Exar
Σ a) (l,,aaaa(X)) ma( B.
LGEA
and we take 0 = O. We have that μt OPT(r, B) is indeed finite. We note that the condition "(r, c, B', v) is feasible for some B' B" required to apply the theorem. The result follows from noting that we exactly have, for X Pt.
*(A)=
inf Exar x.X--((A))
Σ ((( [(c(X, B, A)To
13

---

B Proofs of Lemmas and
In both proofs, will the following deviation inequalities, holding event EHAZ & of probability at least - 6/2, where the event Eg is defined in Assumption 1 6/4 and the event EH-Az is defined below: EntAr n ngg
2 with a confidence level
v ETT
Σ < (AL66/4 + 28r,6/a1 +
0//,r- (2 a7)
(7)
and
Σ - (a0,6)4 + 28/,5/44
+ Σ
6/4, (2T, ar),
uch
(8)
r=1
where Be,8/4 is also defined in Assumption 2 and
2(d + 1)T
0,/6/4
2t in
8/4
These inequalities come, the one hand, by the Hoeffding-Azuma incquality applied (d + 1)T times on the range [-1, 1]: it ensures that on an event EHAZ with probability at least 8/4. for all
1 TT
E - a())
0r/8/4 and Σ rr-
-rr--rrzz rr(,, a+)
& 0t,66/4
20
(where we denoted by olc the supremum norm). On the other hand, Assumption and the clipping (3) entail, in particular, that event &g of probability at least 1 5/4, for all I Ett
Σ c cx ax) & Σ (2,/4,-- ( ar) + 2E, (z,, a,, a,, 6/4) = 2/2,8/4 1
Σ r=1
C3/4, (2, a.)
r=1
and (similarly)
r(E,, 0r) -23,,6/4 + Σ
2. ucb
8//4,r-1 (0 a7)
7=1
r=1
B.1 Proof of Lemma
For 1, by definition of X in Box B,
d A--1 \ + > (c6/4,r- ( - -B b1))) -
> y (6/44,-1 (I,, ar) - (B-b1))
kb
For 3 1, as A0 = and d > O, we get, after telescoping and taking non non-negative parts,
Σ lbb (0)) (bb))
Ae >
|
thus
Σ ( 1 ar) - 61))
Up the deviation terms 7 Aill/y bounds how larger the cost constraints till round are from t B - b1). Most of the rest of the proof, namely, the Steps 1-4 below, thus focus on upper bounding the ||>el. while Step 5 will collect all bounds together and conclude.
Step Gradient-descent analysis.
We introduce
á = C3/4.r-1 (x a,) (B - b1)
lcb
(10)
and prove the following deterministic inequality: for all L.571
AY O,
| 2ll < 2 + 2d 21 + 27 Σ Aer, A--1 A).
(11)
14

---

To do so, we proceed as is classical in (projected) crudient-descent analyses; see, e.g., Zinkevich
2003]. Namely, for all 1 < T < T,
2(- - X) 7 ( - 212 + 11> 22- || - 1²)
1
= || A2; ||2 + 1 (1 - 1/2 | 11²)
<> Aट, 2 + (1 - 211 -11 X11)).
1
7
where the inequality comes from the definition A, = 7 and the fact that
E Vy > 0, (which may be proved by distinguishing the cases and > 0). We note that
[(x) y/ < | yl
B b1 E [0, 1j and 03/4.-- a,) E [-1,1 so that
Ac 1|² < 4d.
Collecting all bounds above, we get, after summation and telescoping.
Σ(-se, 1 A) < yd + 1
27 [1 - 2|l 1|x - AIl))
Rearranging and substituting An 0 yields the claimed inequality
11
Step 2: Relating estimated costs (and rewards) to true conditional expectations. In this part, upper bound the right-hand side of (IT) by showing that the event Eg,
O, VI
Σ Cc, 7,-1 A)
< 2(1 1111) -(0((A)-9-(A)-11))))) -2-(
(12)
9- (A) = max max{{(es r(x (c(xt, -B bb), 2)
where
aEA
and where we recall that - |l denotes the noorm.
Adding and subtracting 7 ucb - (wr, a,), here, we deal with
P scb Σ ACr, d,-1 ---1-A) A) Σ
kb 11 (1, -- -b1, 2))
Σ
p 10/ - (2,)4 (B -b1), xy-1))
Now, for each T, by 33 and the fact that X 3 0,
(11,)-1(0r,,00 a lcb ( (z., a,) -BB b1). X)
a,, 5/4) (c( (+) (B h1), X) + 1 0r, 8/4) |||]] & (A) + 2( + (1 ar. 8/4).
< rrx (7) + 28, a
On the other hand, by definition of a, for the equality, and then by the other inequalities in 3 for each r. and the fact that A 3 0,
8 66/4. (wr, ar)
/ kbb
(0// ( u7) -B (b)),, Ar-1)
(13)
= max
aEA 1x0, a) - (C8/4,7-1 (II,, a) - (B - bl), x--1)
Pub
max A
r(xx a) (c(#r, a) - (B -B,, ) gr (A7-1).
Collecting the two series of bounds concludes this part.
15

---

Step 3: Application of a Bernstein-Freedman inequality. We recall that we denoted by X the optimal dual variable 4 for OPT(r, , c. B b1); exists because we assumed feasibility of problem with average cost constraints B' < B --- b1.
We now upper bound the appearing in the right hand side of at X on an event B of probability at least - 8/4, for all 1 & & T,
12
B-11 by showing that
T
7
Σ (A b1) gr (2, & (1 2At)
21 In
+ 2K, In
(14)
8/4
5/4
where
A max
- - gt
and
K, = 4(1 + | -1 |l + 2dyt).
We will do so by applying a version of the Cernstein-Freeddnee inequality for martingales stated in Resa-Bianchi al. 2005 Corollary 16] involving the sum of the conditional variances (and not only a deterministic bound thereon); is obtained via peeling based on the classic version of Bernstein's inequality (Freedman 1975). We restate it here for the convenience of the reader (after applying some simple boundings).
Lemma 4 (a version of the Gernstein-Freedmen inequality by Cesa-Bianchh et al. 2005). Let X1, X2, ... be a martingale difference with respect to the filtration F (Fa)ez0 and with incre- ments bounded in absolute values by K. For all 2 1, let
1
G, Σ E [ F-
denote the sum of the conditional variances of the first t increments. Then, for all 8 E (0, 1) and all t 1, with probability least
8.
Σx, E 26, In 8
+ 2K In
We introduce, for all X > 0, the common expectation of the (A), namely,
r(x,a) - (e(Xxa) (B - (B- -b1b), (B-b1), x)}}
G(A) (A) Ex
max
and consider the martingale increments
X (gr (A gr (A. (G(A -((A-B--)CC(A--1)))
As B - b1 E 00, 1 and takes values in [-1, for all X, all A, and all Rd, the quantities r(zz a) (c(æ, a) (B- - b1), v) take absolute values smaller than 1 + 2////11 Using that difference maxima is smaller than the maximum of the differences, we get, in particular,
1 (AB m1) gr (Ar-1)| < + 2 - A a.s.
(15)
and
G m1) G()+-1) < 1 2 -
-
Now, given the update step in Step 3 of Box B. have the deterministic bound |eell1 2dytt for all 1 & t < T. Therefore, by a triangle inequality, the martingale increments are bounded in absolute values by K,, as
2 + 2 X bn + max r
A A 11-1h 11)) < 4(1 || 61 |l + 2dyt) K,
The conditional variance of X, is smaller than the squared half-width of the conditional range (Popoviciu's 's inequality on variances); in particular, (15) thus entails
6 2 b1 X \ (1 22.
We now get the claimed inequalities first by noting that by (4). for all < T.
G - G(A,-1) <
and second, by applying Lemma for each 1 < 1 & T, using a confidence level 6/(4T). By union bound, this indeed defines event Exme of probability at least 1 6/4.
16

---

Step 4: Induction to bound the A₁- In this step, we show by induction that, with high probability. the norms B -xll satisty the bound (T8) stated below.
To do so, we combine the outcomes of Steps 1-3 and obtain that on the event Eg n &Bames for all 1 ETET.
AB Xrl1
1BB-aal 42 2y 22(1+ (1 +
gor (AB-b1) gr or(rr-))) Σ r=1
T 2/
7 8/4
< A 1| 4d + + |X 1/. 2 + 21:)
+ 4y Kr In
5/4
where we recall that norms not indexed by subscript are Euclidean norms, and
A,
max E
1 61 X--1
and
K, =,=40 =,=4(1 3- 2d-1)
We upper bound b and A, in terms of Euclidean norms,
A &
and
A <
max X B-b1 - A1-1
1
perform some crude boundings like V & VT and Br,5/4 & BT,8/4, and obtain the following induction relationship: on the event Eg n ERem-co for all EL T,
PA drl1 & Bt+ C max
| X--
(16)
16rst
where
T2
T2
A = | aill +7 4(1 vdllAp -o) +2
2T In
+ 16(1 + Vdll 11)
3/4
8/4
T2
T2
T
B 2dy² +4x 4 x 2 IIn
44+32ln 32nn
dr² & 36d;
In
8/4
8/4
5/4"
T2 2dT
C= 4 vn
8/4
We now show that (16) implies that on Eg n &Benes
del C
C (17)
VOCIET,
PA dell & M
+
A + BT +
2
Indeed, for O. given that A we have
| 61
ai 01 VA. Now, the
bound 17 is satisfied for all 0 & r & (, where 0 < < T T- 1, then T6
implies that
| A < A B (1 1) + CM & A+ BT + CM & M²
where the final inequality follows from the fact that (by definition of M, and this explains how we picked M)
2 CM (M (M- - - -M--))
C²2
C2
=
Below, will make repeated uses of /I + y & Vx + VT. oy & 2(x² + +2), and of vr & 1 1+ for I, y > O. From [7) we conclude that on the event Eg n E
4 t < T,
I b1 - >ell & VA+ +C
T
T 2dT In
=VA+ 07 dT'
+ 47
& V + Gy
8/4
8/4
where we denoted
T2 dT
T2
8T.3/4 = max (T.0/4 2/
> In
8/4
8/4
17

---

For the sake of readability, we may further bound VA as follows (in some crude way):
T
T
VA < AB-ball + V 4(1 vall 0r.))/ + +2
2T in
+ 16(1 + VdllAB -1 in
5/4
5/4
| || + VTV 22 + 20 | B- 1//4
| B b11l
B b1 5 ,///44
where we used the facts that v 220zy 2 /5y & x by and /22r 2 < 6z.
All all, we proved that on the event Eg n ERan-es
0A V
X M Avll < 2 B- 61 ll 17y / Vd 8// +1
(18)
Step 5: Conclusion. We combine the bound
18) with the bound ( of Step and the bound (7)
on the intersection of events Eg n Eperne n EhAzA which has probability at least - 35/4, for all 1 & t < T,
Σ (BB (B-b1) m1
VV 28r,,//1)
A
7
|| - Arl
Va(arT884 + 2BT,8/4) +
7
311 Vd(aT,664 + 193/
This entails in particular the stated result, given the definition of Y,,5 as m ( 0T,611--
B.2 Proof of Lemma 2
The proof is similar to (but much simpler and shorter than) the one of Lemma I and borrows some of its arguments. We use throughout this section the notation introduced therein; also define new event Epan. of probability at least 1- 5/4.
We start from 1 TT
8 and introduce the same AC, quantity as in (10 on the event En n Eg, for all
Σ rr >
(01.8/4 2B2,,/4)
F ucb 8/4,7- (I,, a7)
7=1
+ > +-
p uch
6/4,7-1 (IT; 0T) - (Acr, )v11)) + Σ Ac. 2--1).
On the one hand, the result
with x = 0 exactly states that
|
(Ac. X x
2d > -2d
2-y
On the other hand, the result
(13 states that Eg, for all TT
P uch
6/11 (2,, 07) (Acr. ))- f - (Z,
(2 a.) - (2./4,--1 a7) -(B (B-bl), \
> (),1))
similar application of Lemma 4 as in the proof of Lemma 1 shows that new event E of
probability at least 1 - 5/4, for all < 1 & T,
T
T
Σ (-(A-1)) > EG(A--)) -
G(
2 Σ
(1 + 2 A
a11))
8(1 + 2yt) In
5/4
8/4
T=1
7=1
18

---

We relate e' norms to Euclidean norms, resort to triangle inequality, and substitute 18 to get that on Re for all 1 < T.
2 Σ + 21 111 I
T 8/4
7 (1 11+2Vd
max UETEL-1
|
26
7
5/4
72
1 + 2+2V0|| 2vd
max
|1 - -dr-1ll)
2/
0g7E1-1
8/4
T
2vd+1)
22/1
8/4
T2
3 s/d - + 34d 104ddBBT.551 T7.4 + 4Vd
2n
6/4
6|| AB b1 ll 1T,6/4 25 (37,8/4)
2v2
3/44/4
6 b1 || T/58/11 28yv (3T,3/4)
where we performed some crude boundings using the definition of 1 < 3/,0/4 < 3/,8/4- We also note that
T2
T2
+(1+ In
& 8ln
+ (3'
8/4
8/4
By we have OPT(r, e, B - b1) = G -1) GG()), for all > Also,
G()B-b1) + bb BB ||1
r r(X,a) a) (c(( a) - b1), X XB-01) } b b11li
E Exar
max aEEA
7 (X, a) -(c(X,a) B, {>) > oPT(r,c, B)
Ex-v
max [uEA
where we used again
In particular,
Σ 2()--))> LoPT(r, B) - tb -bbliB (Ai--alll > LOPT(r,e, B) LbVd -
Collecting all bounds above and using the definition of TT.5 max 8/r,/44 aT3/44) } and the fact that dt & (Yr,s)², we proved the following. On & N n &anee O Enem which is indeed an event with probability at least - 8, for all 1 < t & T,
r=l
72
7
> -3T 2d + Σ G()--)) + 1
Σ tOPT(r, c, B) 1i (ebVa+ I
In
81n
(8(
5/4
8/4
T
36,vo 2 8ln
8/4
This entails in particular the stated result.
C Proof of Theorem 1
The proof is divided into three steps: on favorable event Emen of probability at least (i) we bound by ilog I' the index of the last regime achieved in Box C;
19

---

Algorithm 1: Pscudo-code for the Box C strategy
Input: number of rounds T; confidence level 6; margin b on the average constraints;
estimation procedure and error functions eN of Assumption 2 optimistic estimates
Initialization: To = 1; sequence = 2 /vT of step sizes;
sequence MT. = 4vT + 20 Y (1)((2)))) of cost deviations
for k > do
// Box C part
Ar, for t > Tx do
// Box B part
if - then
Terminate algorithm; end
Observe the context æ;; Pick an action
E arg max i uch (,,111 (21;0) a) (c,,e- (2 ( [B- - b1), >
aEA
Observe the payoff T, and the costs C₁; Compute A (Ae-1 + Yh (co,-- (2), at) (B (B-b1)) -11) -b1))) // make PCD update
lcb
11
Compute the estimates uch
o6t and Cats
lbb
12
c ---
61)
MT, 8.k then
// Box part
Break inner for loop; Tx+1 = 1 1;
finish phase l and move phase + // record beginning of phase k +
14
15
end
16 end
end
(ii) we bound by (1 + (loilog T the excess cumulative costs with respect to T(B (BBbbr) br) and deduce that the cumulative costs are smaller than B: (iii) we provide regret bound, by summing the bounds guaranteed by Lemma over each regime.
The favorable event Emes is defined as follows. By construction, and thanks to the assumption of fcasibility for B - 1b, the results of Lemmas and and hold with probability at least 8/(k k + 2)3 each round of each regime & > 0 that is actually achieved. Given that
Σ AG
11
2)
(ke + 1+(k)++22)
kzu
we may define Emera as the event indicating that the (uniform-in-time) bounds of Lemmas satisfied within each of the regimes achieved.
| and 2
are
C.1 Step Bounding the number regimes achieved
We show that, Emers if regime K ilog |X b- is achieved, then this regime does not stop. Hence, on Ene.s at most K < + ilog | bb, regimes take place.
Indeed, regime = ilog | bb ||, if it is achieved, the meta-strategy resorts to the Box B strategy with
max { |> by 1} 2K
7K
VT
VT
20

---

Therefore, the bound of Lemma] entails that on Emau. for all t > Tk.
+ 3 B br1l
Σ c. - (t- (t- by1)) TT
<
+ (T55/222
KK
4VT 20v 20 MT,.KK
This is exactly the contrary of the stopping condition of regime K: the latter thus cannot be broken.
In some bounds, we will further bound ilog A by by ilog T: this holds because the assumption of 2br 1 feasibility entails, by Lemma and as OPT is always smaller than 1, the crude bound
OPT(r, c, B - by1) OpT B - (3/2)br1)
2 bt
VT 7 <T,
A &
br/2
where used that by 14/vT given its definition. (Of course, sharper but more complex bounds could be obtained; however, they would only improve logarithmic terms in the bound, which we do not try to optimize anyway.)
C.2 Step 2: Bounding the cumulative costs
We still denote by K the index of the last regime and recall that K & ilog | B- & ilog(TT), and that for k > regime starts T3 and stops T++1 1. By convention, To and TK+1 T
By the very definition of the stopping condition of regime > O,
Th+1-2
Σ 1
(Tu+1 - Th 11 (B)
bT1)
< Mr.ak
For rounds of the form 1- T++1 1, we bound the Fuclidean norm of C₁ (B by 1) by 2vd. Therefore, by triangle inequality, satisfied both by the non-negative part ( )+ and the norm functions, we have
Σ c: T - CTBBBB- bT1)
K
T
C - 4 Tk - 11) by.1) )
K + + k=0
ee (B 1r
k=0
t=T
(K + M) + 2Vd) Tbb,
where we used the fact that MT.8,e increases with k. the bound K & ilog T proved in Step and holding on the event Emers as well as the definition of by. Therefore, E no component of
Σ c T(B -br1))
T
can be larger than Tbr, which yields the desired control
Σ
4 TB.
C.3 Step 3: Computing the associated regret bound
The total regret is the sum of the regrets suffered over each regime:
K
Tk41-1
Ry
(Tet1 - -a)n-T))or((rcc.
Σ
Tt
k=0
t=
21

---

On the favorable event Emeu, the bound of Lemma 2 holdd in particular at the end of each regime; i.e, given the parameters " = /VT and 8/ (4 2)²) to run the Box B strategy in regime
k E J. it holds on Emera that
Tht1-1
(Tk+1 - -T) OPT() B)
Σ
n A brz I ((T++1
- Tx) by 6
6T
t=
+ 36Vd (TT,8/((+22)) 2h
T
In
VT
5/(4(k 2)2)
We now sum the above bounds and use the (in)equalities TT,6/((+222 & TT
E(E+: - Tx) br Tbr and
Σ 2h 2 < upall < 4 B-
to get
(Tr,//(42)))
Rr & b- ( GK T.8KK42)))) + 1444
by
VT
T
+ In
8/(4(K + 2)
The final regret bound is achieved by substituting the inequality K & ilog proved in Step 1:
Rr E 1 b ll [IAVVa (Y (/
+ 6,55//t aya ilog T
/T
7
8
ilog? T. (19)
5/(4(2 ilog 2)2)
ilogg
The order of magnitude is vT, up poly-logarithmic terms, for the quantity Y (2 272, thus for &r,8,ilog thus for T by, therefore, the order of magnitude / of the above bound is, up to poly-logarithmic terms.
(1 + | II) VT.
as claimed.
D Proofs of Lemma and Corollary
Proof of Lemma
For 0 and C E [0, 1] we denote
L(A.C) Ex max (X, a) (c(X, 2)3 "EAA
so that by and the feasibility assumption, we have, at least for C = B and C B bl: OPT(r, C)
min L(X, C) = L()C,C). A
The function L is linear in C, so that OPT(r, e, B) L(> B B) L(> B) 1(\iBb1: B b1) (XB- B B
OPT(r; C, -1) (>B--11 B b1 B)
The result follows from substituting
( B b1
B)
> | min B
B) > X m min B B
and from rearranging the inequality thus obtained.
Proof of Corollary 7 We apply Lemma
3 with B = el for some e > 0 sufficiently small and obtain
OPT(r, e, b1) opT(r,
<
min B (b++)1)
We conclude by substituting OpT(r, c, B b1) < OPT(r, c, B) and opT(r,c,e1) > ort(r.c,0) well min(B b1) > min B/2, and by letting : + 0.
22

---

E Additional (sketch of) results concerning optimality
We detail here two series of claims made in Section
E.1 A proof scheme for problem-dependent lower bounds
We provide the proof scheme for proving the problem-dependent lower bound of order (1+11xBll) VT announced Section
Step 0: Considering strict cost constraints. Our aim, as described in Box A, is to make sure that with high probability the cumulative costs are smaller than B. If we considered softer constraints, of the form I' B + (VT),, then (vVT) regret bounds would be possible (see Appendix F i.c., the factor b of Theorem could be replaced by constant. Thus, lower bounds are only interesting in the case of hard constraints stated Box A.
Step 1: Necessity of margin bt of order 1/VT. First, classical lemma in CBwK (see, e.g., Agrawal and Devanur 2016 Lemma 1) indicates that a sequence of adaptive cannot perform better than an optimal static policy. Denote by T (quasi-Joptimal policy for the average constraints B'. Provided that costs are truly random (i.e., do not stem from Dirac distributions, which in particular, does not cover the cases where there is a null-cost action, see Limitation 2 in Section(4) then the law of iterated logarithm shows that when playing T at each round, the cumulative costs must (almost-surely, as T + +oo) be larger than T plus a positive term the order of vT In In T. Therefore, meet the hard constraints, should pick B' of the form B br where by is of order TT up logarithmic terms.
Step 2:
Consequences in terms of regret. Therefore, the largest average reward a strategy may target is OPT(r, c, B by. Deviations of the order V are also bound to happen. Therefore, up to logarithmic terms, the regret lower bound is approximatively larger than something of the order
Tort((r, c, B) - -OP((rr c, B - by + VT.
Now, an argument similar to the one used in the proof of Lemma 3 shows that
OPT(r, c, B) OpT(r, b, > L(X B)
L(> B by br |
All in all, the regret lower bound is thus approximatively larger than something of the order of
(1 \| VT.
This matches the form of the bound of Theorem I but the dual vector X present in the upper bound is replaced by A in our lower bound.
E.2 Faster rates may achievable some specific cases
We explain here why, some specific cases, faster rates would be achievable-with VT the regret bound of Theorem replaced by vTB B for a problem with sealar costs and total-cost constraints B.
Indeed, consider a problem similar to Example [ with scalar costs, total-cost constraint B > O. featuring baseline action amm with null rewards and expected costs c(æ, a) > a > 0. Let Nr denotes the number of times non-null cost actions played within the first T rounds. Deviation inequalities have that
but also null reward, and additional actions with larger
Σ e > aNr - - -((
where we recall that Ô is up to loly-logari factors; consequence, the total-cost constraint enforces that
TB
TB a
N <
+
a
23

---

In particular, the margin by only needs to be of order /NT/T,ie. VB/(aT). instead of 1/VT.
Similarly, since most Nr non-null actions are played, the regret should be lower bounded by something of the order of
T(oPT(r,c, B) or br)) + NNT,
where, as in Step 2 above,
(oPT(r, B) OpT(r, -b)) bt 1 (
B
M&
aT
This suggests a lower bound on the regret of the order (up to poly-logarithmic factors) of
(1ai) +
TB/a instead of (1+ (A VT.
The difference between the two bounds is significant when B is small, i.e., B < 1. While proving matching upper bound with the Box B and Box strategies looks a bit tricky, we feel that must be possible to do so with the primal approach of Appendix [ at least when the context space X' is finite. our intuition holds, then it would be possible to get an upper bound
Rr < Ö Tbr o by
TB -6(
OpT(r, B) - =
=
1
B
where the last bound follows from OPT(r, c, B) Opt(r, e, 0) & B/a, as explained in Example
F
Primal strategy
This section studies the primal strategy stated in Box D, which, every round, solves approxi- mation of the primal optimization problem (T). The key issue in running such primal approach is estimating v, comments after Notation I this primal approach is essentially worth for the case of finite context sets X. The aim of this section is threefold:
1. In Appendix F.I we provide a theory of "soft" constraints, when total-cost deviations from T B of order vT up to logarithmic terms are allowed; at least when A' is a finite set, the regret bound then becomes proportional to vT up to logarithmic terms.
2. In Appendix F.2 consists of dealing with possibly signed constraints, and the revisited analysis (of the same strategy in Li and Stoltz 2022) consists in not directly dealing with KKT constraints (which, in addition, imposed the finiteness of X') but in only relating optimization problems- defined with the true r' and e or estimates thereof. We also offer modular approach and separate the error terms coming from estimating v/ and from estimating r and c.
revisit and extend the results by Li and Stoltz (2022). The extension
3. In Appendix F3 we generalize the results of Appendix F.2 which rely on the existence of a null-cost action, and get guarantees that correspond quite exactly to the combination of Theorem
I and the interpretation thereof offered by Lemma at least in the case finite X. Actually, in our research path, we had first obtained these primal results, before trying to obtain them proof technique in Appendix F3 also inspired our approach to proving problem-dependent lower bounds presented Appendix E.1
more general case continuous X, by resorting to dual strategy. The
Throughout this appendix, we will assume that the context distribution v can be estimated some way. We provide examples and pointers below.
Notation 1. Fix 8 (0, We denote by Vø,t a sequence of estimators of v, each constructed on the contexts æ..... , Lt, and by E., sequence of estimation errors such that, with probability at least 1- 8, for all bounded functions f X' + [-1,
Ex ~m [[(]] Ex [f(X]] Ee,5
T
We also denote
ET
1=1
24

---

results for We consider the strategy described in Box D, whether A' is finite (as in Li and Stoltz 2022 where it was first considered) or not. Our simplified analyses do not rely on explicit KKT inequalities and therefore do not require anymore that X' is finite. In Box D, by "when the empirical cost constraints are feasible", we mean that there exists some policy π such that
E
Σ C ( LaEA
(X) & b+b
We need to guarantee the existence of a policy achieving the constrained maximum of Step 2 in Box D. This is immediate when X' is finite, the problem then corresponds to diteesiimmniinal linear program. In general, we may note that when (4) holds, we read therein the optimal policy, pointwise maximum involving the optimal dual variables. The proofs reveal that up slightly augmenting the 1,- of Notation we may assume that the strict feasibility sufficient for (4) indeed holds.
We also note that even if the argument the maximum n. is guaranteed exist, may be difficult to compute: the linear program of Box D cannot be solved exactly if the Vs., are not finitely supported (which happens in general when X' is not finite). We do not see this as a severe issues as the Box D strategy an ideal strategy anyway, that study for the sake of shedding lights the dual approach in the main body of the article.
A final remark on the Box D strategy is that the margins on the average cost constraints B can now be signed, which is why they will be referred as signed slacks.
Box D: PRIMAL CBWK STRATEGY, GENERALIZED FROM Li AND STOLTZ [0022]
Inputs: confidence level - o; estimation procedure and error functions E, of Assumption
optimistic estimates (2]: estimation procedure for as Notation I
Hyperparameter: signed slacks b1, b2...., br E R
Initialization: initial estimates 7,00 (ax a) and 2o a), well as 18.0
For rounds f 1,2, 3....
Compute a policy n, achieving
max m.Y (P(A)
Ex-ess
8,6-1
uch (X, a) (x)
LECA
under
Ex Ex-it,
C XX, (X, (X)
< B + b,1
LaEA
when the empirical cost constraints are feasible, and pick an arbitrary policy n otherwise;
2. Observe and draw action (xx)):
Compute the estimate Patttas a) and 1/ (ax a). as well as P/.e.
Discussion of the estimation of v. The simplest case is when A' is a finite set; in this case, we may take
X In(1/5)
of order
where denotes the cardinality of X: see et al.
2022
Section 4.1], see also a less sharp bound Section 5]. This leads total error term
based on Hoeffding's inequality in [Li and Stoltz 2022
Sy.5 of order VT up poly-logarithmic term.
When continuous subset of R", some regularity conditions are put on v, which is typically assumed to have some smooth density with respect to the Lebesgue measure m. Estimates Vg,, are obtained by estimating the density dv/dm: the criterion in Notation I which proportional to the total-variation distance between and Ø5.s, is then given by the L (m)
(mm distance between the two
25

---

densities. To control the latter with uniform convergence rates, so as to obtain deviation terms ςr,ō only depending on and heavy assumptions on the model to which belongs are order, e.g.. some Hölderian regularity, and uniform estimation rates obtained degrade with the ambient dimension n; they are generally much slower than 1/vt. The total error terms E7, then prevent the bounds stated below Proposition and Theorems 3 a from sharing the same orders of magnitude than the bounds proved with our dual approach in T'horrmm | and interpreted in Section 3.3] On this topic. see also [Ai al. 2022, Section 4.1] for the estimation rates well as similar description in Han et al.] [2022] end of Section 1] of the limitation of the primal approach in CBwK due to the estimation of densities. General references on density estimations are the monographs by Devroye and Györfi 1985 in I.- and Tsybakov (2008) in I.2.
Note that in the dual approach, the knowledge of (the possibly complex) v is replaced by the knowledge of the (fiittedimmnnsional) optimal dual variables X R which is easier to learn. This explains the fundamental efficiency of the dual approach compared to the primal approach.
E1 Analysis with "soft" constraints
We first provide an analysis for a version of the Box strategy that may possibly breach the total-cost constraints TB. More precisely, we allow deviations to TB of the order of vT times poly-log factors: this is what refer to "soft" constraints. Our result is that the regret may then be bounded by quantity of order vT times poly-log factors, at least when X' is finite.
We do so for two reasons: first, because we do not think that this is well-known result, and second, for pedagogic reasons, as the proof for "hard" constraints follows from adapting the proof scheme for soft constraints (see Appendix (.2).
Proposition (soft constraints). Fix 8 E (0,1). Under Assumption 2 and with Notation ①I, the strategy of Box D, run with 6/4 and positive slacks b, = Ec-1,8/4, ensures that with probability at least 1 8
Σ TB (2001 5/4 + B1,6/1 + 2 1=1
and
Rr & 200 + ST,6/1 + 23
where 0/4 (nT
In particular, when X' is finite, the deviation terms 20r,,6/4 + BT,6/4 + 237,8/4 are of order vT up to poly logarithiie terms, so that the bound of Proposition reads: with high nigh-rrobability,
T
c < TB TT++OvVT
and
Rr < Ö(VT).
Put differently, soft-constraint satisfaction allows for ((VT) regret bounds when A' is finite.
Proof. As in the proofs of Lemmas T and in Appendix B consider four events, each of
probability at least 1 - 6/4: two events EhAA and EnAv2, defined below, following from applications of the Hoeffding-Azuma. inequality, the favorable event εTTD of Notation [ with 8/4, and the favorable event E of Assumption 2 with 0/4. Namely, given the value for oT,5/41 proposed in the statement we have, on the one
(note this value slightly different from the one considered in Appendix B hand, on Ei
T
T Σ t=1
T
Ea 2o.0/15 + Σ c(())a)))
and
> -TT / +
r( at); (20)
1=1
and on the other hand, on EnAZ.
Σ c icb
1 (Ei, aT, + Ex
Σ
C8/4,t-1 1
^ 10b
(x,, (x, (X)
LEEA
T
T
and
Σ
6/4,0-1 (I), -0T.8/4
rch
Exay
(xx)) (X (x((X)
Σ
8/4,1-1 (X,
uch
(21)
LaEA
26

---

The first two inequalities are obtained by considering conditional expectations with respect to the past, 2y and a,, while the second two inequalities follow from taking conditional expectations with respect to the past and zy; we crucially use that, by definition, at v is independent from æ, and the estimates f ucb
8/4,t-1 and 12/4.t11'
We first note that by B-feasibility of the problem, by and by Notation ( policy satisfying the constraints stated in Box D exists each round 1 on the event &g &TVD. Indeed, denoting by π such a B-feasible policy, this existence follows from the inequalities
Ex-Ps/A,1-1
Σ LEEA
28%4,t-11X,00 (X, Ta (X)
< E Ex Xx-0o14,111
Σ c(X a) na (X)
Ria
LaEA
< Ê1-1,5/1 + ExNv
Ee(X, a) aea (X)
(22)
LOEA
B
and from the choice b, 1,6/4
Cost-wise, we then successively have, by (20). then (3) and Assumption and finally Notation T the event En-aa n E3 n Ena O ErvD of probability at least 8,
21 and
Σ c < 0T. Σ c(at, 0t)
T
< (ar,,5/4 - Br,5/1) +
C8/4,1-1 (It, 0t)
< (20 Br,6/a) 1
Exnv
Σ
- C8/4,1-((X,0 Te, (X)
t=1
LaEd
(20T,884 +
Ex-Ps/ae11
Σ
28/4,1- (X a) Tr,
LEEA
B+b11 where the inequalities & B + be follow from the definition of क, in Box D. Substituting the choice be f--1,6/4, thus proved that Eusa O &g O Enaz O ETdD.
TB + (20T + BT,3/4 + 2ETT5544
as claimed.
The control for rewards mimics the steps above for costs (and then resorts to additional argument). We obtain first that on EaAZ EE n EHAZz O EivD.
~ BT,8/4 1 ET,814) + Σ Ex-
-200,
Σ LOEA
p ucb 1 (X, a) ne,a (x)
t=1
We denote by i an optimal static policy for the average cost constraints when exists, e.g.. by (4). soon the problem feasible for some B' B; otherwise, take statie policy achieving OPT(r, c, B) up to some small e > O, which we let vanish in final step of the proof. As (22). we have, on &g n ETvD.
E X Ex-Po/4.11
C (X) < EExnssaac-
Σ c(x a) a) (
LEEA
LaEA
E1-18//4 1 + Ex
Σ
a T (B.
LaEd
<B
27

---

where the & B inequality follows from the definition of B. Thanks to the choice d, 1,844 we have, by definition of n as some optimal policy Box D and on Eg n ENTD,
Ex Ex -x-as
Σ i 88/41-11 (X, Te (X) > Bx-01/41111
P 16/4,1-1 (X, B
Again by (3 and Notation ① have, on Eg n ETVD.
E X Ex-B6/4.1-1
Σ
uch 8/1,t-1 (X,, (x TB (X)
> E Ex
Σ r( TB
LaEA
LAEA
11-11/44 Ex noy
Σ
r(X a) T T (X) (X)
LaEA
=or((r.,
Collecting all bounds, we proved that on EnAi n Egg EH, O ELVD.
Σ ri > ToPt(r, c, B) (20T,554 + ST,6/4 + 2ET,6/4)
which corresponds the claimed regret bound.
F.2 Analysis with "hard" constraints and null-cost action
We now turn our attention to the main kind of result that we want to achieve: when constraints must be strictly satisfied-wii which we refer as "hard" constraints. For the sake of simplicity, do for now in the presence to cases without such null-cost actions.
null-cost action; Appendix F3 explains how the analysis may be generalized
The following result corresponds to the combination of Theorem with Corollary || and also, Li and Stoltz 2022 main result: Theorem 2].
Theorem (hard constraints). Fix 5 E (0, 1). We consider the strategy of Box D, run with 8/4 / and negative slacks all equal to
where TT,5/4 def 20 BT,5// + ET,8/4
b, = A
T
and OT,55/1 that Assumption
2T In (d 1)/(4/4)). Assume that null-cost action exists, that AT,5/1 min B, holds, and use Notation ( Then, with probability at least - 5,
T
B (1+ OPT(r, e, B) OPT(r, e, 0)
Σ
C STTB and Rr <
min B
Proof. We explain how the proof of Proposition D may be adapted. We first justify the existence at each round > 1 of a policy म, satisfying the cost constraints stated in Box D: for the null-cost action Omil we may impose that, for all E X. all > O, and all 5 E (0, 1),
(xx, amm))
and ex Omm, 8) = 0,
that C/ (2, amai) a.s.;
this shows that least the static policy mull always playing amu satisfying the defining cost-constraints for πe (Alternatively, we may note that the policy defined below also satisfies the cost constraints stated in Box D, on the gighpprobbbility event considered.)
We then handle total-cost constraints similarly as in the proof of Proposition I and obtain that on the event EnA & n Enaa ETVD of probability least 1-88 8,
Σ a & (20T,5844 + +1,,5/1 + ET,51) 1+ Σ
Ex-is/s.t-
Ex
8// (X,0) xx)(
lcb
TB,
LaEA
BB -7
28

---

where this time, the slacks b, - T,,6/4 are negative and were set to cancel out the positive deviation terms. Similarly, on En. nEg Enrae ETDD
n -TA +
Σ
E xx-Drx x
Σ F 8/4,2-1 (X)
(23)
Now, the main modification to the proof of Proposition Dis that (with its notation) we rather consider the policy
Tr.6/4 + 11-1.8/4
T = (1 - We)T + We T
where
We = min
min B
As in 22 we see that this policy satisfies, on Eg ETND:
E Ex~
Σ
(X, (X)
< Ex
Σ a) (X)
LAEA
LaEA
< E1-18/411 + EX
Σ
c(X, X a) tea
LoEA
<(I-w:)B
By using > (min B)1 and since we assumed that 4T,5/4 min B, we may continue the series of inequalities as follows:
&r-1,8/41 (1 w. & B 1,6/4/411 w/ B)1
min AT,8/4 min B 1,-4
- E1-1,611 < B min AT,6/1: -
B + 4,1
meaning that is policy satisfying the constraints stated in Step 2 of Box D on round / >> 1. The consequence is that, first by definition of π as a maximizer and then by the optimistic estimates and Notation (T. on Eg ENd.
Ex~ Bx-Pajatt1
p ucb Σ LaEA
8/4,t- (X, a) (X)
E Ex-Ds/aa-11
L ucb 8/4,t-11
(X, a) Teta
LEEA
> ----186/4 + Ex-o
Σ r(x Trea
1-118/4 + w.)oPT(T,CCCcmm e, B) wrOPT(r,c.O)
1 (opT(r, B) opt(r,
opT(r, c, B) 1,-1.5/4 min
min
where OPT(r, 0) refers to the expect reward achieved by the null-cost action amo- After combination with (23) and summation, we get that on EnAA EE n EHazz n ETvn:
Pt TopT(r,e,B)
T
AT.8/4 11-1,6
> TAT,8/4 - -
min
(opT(r, -PTr,,((,,
min B
OPT(r, e, B) OPT(r, 0,
> -T ET,y44 1
min B
which corresponds to the stated regret bound.
29

---

F.3 General analysis with "hard" constraints
We finally generalize Theorem B and get a result corresponding to Theorem combined with Lemma
Here, "mix" the slacks 1,644 and -Ar,6/4 of Appendices F.1 and F.2
with slight modifi-
cation of Ar,5/1 to compensate for the fr-1.5/1 we rather have a T-56 term in the numerator of AT,5/4, compared to the ET,6/4 term in the numerator of DT,6/4-
Theorem (hard constraints). Fix å E (0, We consider the strategy of Box D, run with 8/4 and signed slacks (depending on
where TT,5/1 20/T,8/4 + -r,6/4 2ET,6//
be = T + 11-16611
T
and 0'4,6/4 = / 2 (dd 1)/(6/4))- Assume that the problem
m) feasible for some
m that does not need to be known by the strategy, with B m & B - Ar,,/a Then, under Assumption 2 and with Notation ① with probability at least - 8,
C TB
Pr (2 BT,5/1 25 (1+ OPT c, B) OPT((r c, m)
and
min m
Proof. We rather sketch the differences to the proofs of Theorem and and Proposition We denote by En the event of probability at least 8 obtained as the intersection of four convenient events of probability each at least 8/4. 4. All inequalities below hold on &n but for the sake of brevity, we will not highlight this fact each time.
We denote by π a (quasi-)optimal static policy among the ones achieving expected costs smaller than m; it therefore ensures that its expected costs are smaller than B m and achieves an expected reward of OPT(r, B - m) e, possibly up to small factor e > 0 which we let vanish. We note that for each round 3
E Ex~
Σ LaEA
Jes (X) C (X aa
lob
< 11-1,//11 + Ex
Σ c c(xx, T Ta (x)
LAEA
E1 + B ml
< B B b,,
given the definition b, T 1--15//1 and the assumption B on Ean, the strategy is indeed defined each round > by the optimization problem stated in Step 2 of Box D (and not in an arbitrary manner).
B A
8 1. Thus,
Cost-wise, we thus have
& B+bb1
Σ Ci (20 + Br,6/4 Br,6/4)
Σ
E Ex-insa,-1
Σ
c/4,t- aX Te (X)
lub
1=1
LaEA
TB (20 31,5/4 - + E2,5/4 TA4.84
TB,
where the final equality follows from the definition of A7,5/1 which involves 23 term in its numerator. Reserd-wise, we introduce for each > 1,
A T/44
म.. TT + Wyrr
where we min
1
min m
whose empirical expected cost at round > is smaller than
Ex
Σ
C8/4,1-1 (X,, Te (x)
< E,1188/1 Ex
Σ c(Xx, a) Tea
LEEAA
LOEA
< f1-188/11 1 + +1
we - m)
B + + E,- 5.-1144111 wim.
30

---

By using m > (min m) and thanks to the assumption B - m B - 4,,6/1
which can be
equivalently formulated as min m 2 T.,6/2 may continue this series of inequalities by
B 1-88/411 wi B min A
min m 1,-1,8/4 T/88/ - 1,-1/8/4
min T,5/
- - E1-16/ TT,5/4 E1-1.5/1
B b
meaning that ग. is policy satisfying the constraints stated in Step of Box D on round In particular, by definition of nI as a maximizer,
Ex Ex~isran
Σ LEE
r 18/,,-1((X, (X, a) (X))
Ex-
wcb 8 (X, (X,)) Te,a (X)
Σ
LaEA
> 11-1.6/4 + Ex
Σ r(X, a) (X)
LEEd
5--15/1 ((1-0)111))) (r -
= Or min
1
o m)) 11-148 (24)
min m
Finally, by combining
23 and 24
=TA 7/ 3/.
T
Σ rt
20TT,8/4 + ST,6/4 3T,614
Σ
E Ex-
Σ
8/4,1 1 (X, (X)
ach
Laa
OPT(N, OPT(r, cB - m
> +)) -
(1
Er,6/4
min m
as claimed.
G Numerical experiments: full description
This appendix reports numerical simulations performed on simulated data with the motivating example described in Chohlhh-hoanle Wood et al. [202] and alluded at in Section 2.1 These simulations are for the sake of illustration only.
A brief summary of the applicative background in Al for justice is the following. The learner wants maximize the total number of appearances court for people of concern. To achieve this goal, the learner is able to provide, or not, some transportation assistance: rideshare assistance (the highest level of help), or a transit voucher (a more modest level help). There are of course budget limits on these assistance means, and the learner also wants control how (un)fair the assistance policy is, terms of subgroups of the population, while maximizing the total number of appearances. Some subgroups take better advantage of assistance to appear in court, thus, without the fairness control, all assistance would go to these groups. The faimesss costs described in Section 2. force the learner to perform some tradeoff between spending all assistance most reactive subgroups and spending it equally among subgroups.
Outline of this appendix. We first recall the experimental setting of Chohlas Wood et al. [2021
particular, how contexts, rewards, and costs are generated their simulations (we cannot replicate their study on real data, which is not accessible). We then specify the strategies we implemented and how we tuned them-this includes describing the estimation procedure discussed in Section 2.2 We finally report the performance observed, in terms of (average) rewards and costs.
31

---

G.1 The experimental setting of Chohlass et al. 2021
We follow strictly the experimental setting of Chohlas- Wood et [002]] as provided the public repository https://githun com/ imental setting, as weveerse-engineeee
com/stanf stant d- www.lpolllllllaaaaaaaaeallaaaa /eaana////aaaaaaae ing /ot//////aaafooooooooo/aaaa///ea
This exper-
from the code, deals with purely simulated data and seems actually inconsistent with the description made in Chohlas- Wood et al. [2021] Section 5.4 and
Appendix EJ, which would anyway rely on proprietary data that could not be made public.
Context generation. Each individual is described by four variables æ: age, proximity, poverty, and group, which are be read in æ in its components, referred to Tages Zpmax I and gr(x) grop The first three variables are assumed to be normalized and are simulated independently. according to uniform distributions [0, 1]. Groups are also simulated independently of these three variables: two groups are assumed, with respective probabilities of 1/2. This defines the context distribution 1/.
As describe now, assistance has stronger impact on group than in group 1.
Cost generation. We recall that three actions are available: offering some rideshare assistance (action anee), providing transportation voucher (action Ovouches. or providing no help (which is control situation: action Grourat) The associated spending costs are deterministic and do not depend on œ, and there are two separate budgets for rideshares and vouchers. More precisely, at round t, upon taking action as, the following deterministic spending costs are suffered:
(Fs 01) fac== and
Cyoucher (12, a2) = 1l (
where the corresponding average budgets are Bade = 0.05 and Byoucher = 0.20.
We measure the extent of unfair allocation of spendings among groups with the following eight fairness costs: a first series of four fairness costs given by
2 1 (a, mand)) 1 (xr(m,)=0) L (
1 (a.=ana) ((r((=)==1) 1 (a.=ana))
2 [a,== =dcccher } 1l (=) 1l (a.=oru
2 1 (a, ayoacher [gr(m,)=1) (as=awucher) )
and the second series is given by the opposite values of these costs. We denote by r the corresponding average cost constraints T, and set = 10-7 or 0.025 in experiments.
All all, the global (spending and fairness) vector costs C. takes deterministic values in R. The vector cost function is fully known to the learner, and no estimation is needed.
Reward generation. The rewards are binary: r, if the L-individual appeared in court, and 0 otherwise. That is, the expected reward equals the probability of appearance. A logistic regression model is assumed: denoting by ((u) 1/(1 + e"), we assume
r (D, acconrat) = (--wan)) )
r r(x, avocther) of aage + pron) ())( + (b- + xpox) ) (<(())=1))
r(x, anax) Tage + 4m 1 (gr(m)==) (- + 2xpmr) ([r(x)=1}
We may write these six equalities in compact format as: r(z, a) = 2 (x(((,, a) p.)
Fage
-1
Tproo
{a=ovoucter
where
a)
Zprox
(a=0 (gr(#)=0)
and
=
Fopo
[a=ande)
Epuy
{a=aadee
1 (gr(w)==)
The learner ignores the coefficients μ4, of this structure and only knows that expected rewards are of the form & ((p( a) 0) for some parameter 0 E 1255 The learner will estimate the reward function by estimating (la.
We deal with a logistic model and follow the methodology described in Li and Stoltz [022]: see Modeling 2 Section 2.2 In particular, the parameters μ4, are estimated, after each round / > 1, thanks to the maximum likelihood estimator
Reward estimation.
A lugistic
14 E arg max MERS
r. (4p(a,,,,))))) u) + (1 - r.) In In (1 (vp(a,, x.)
||
2
32

---

where A Ingistic > 0 is regularization factor. We define as fz a) - 4 ((((z, 1z a)
(.) the estimated
expected rewards, and the associated uniform estimation enrors (see Assumption are of the form
Ex a, Co Int) x)(0, V x((a.x)
Σ ((a,; v.,) ppsa. R... + TogisticTs
where
Vi
where 15 is the 5 x identity matrix.
In our simulations, we tested a range of values and picked (in hindsight) the well-performing values C 0.025 and X logistic = 0.
G.2 Strategies implemented in this numerical study
We run all these strategies not with the total-cost constraints
B (0.05, 0.2, T, T, r): where
TE EE110, 0.025).
but take margin b 0.005 and B' = B (,, instead. This is slightly different way of taking some margin on the average cost constraint: we do so because we are not aiming for a strict respect of the fairness constraints but rather want report the level of violation
it. Again, we tried a range of values for b (between 0.001 to 0.01) and this value of 0.005 led to a good balance between (lack of) total-cost constraint violations and rewards.
Performance of optimal static policies. We use OPT(r, c, B) as the benchmark in the definition of regret; our methodology also reveals that OPT(r, c, B') 3)) is another benchmark, the discussion in Section 4 We report both values on our graphs. To compute them, we proceed as follows, e.g.. for B. As computing directly the minimum stated in (4) is difficult, even when fully knowing the distribution v, we compute 100 estimates
(r, B),
which we average out into
OPT(r, B)
Σ (r.
100
For each j. we sample S = 10,000 contexts from the distribution and denote by Dl) the associated empirical distribution; we then solve numerically the problem (4) with v replaced by this empirical distribution:
OP c, B) min A
mmxxfr(2 (c(x,) aEA
(c(X, B, -) x
B.
xx-00)
Mixed policy knowing A but estimating r. For the sake illustration, we report the perfor- mance of policy that would have oracle knowledge of AB which is finite-dimensional parameter that summarizes v, but would ignore r, i.e., the underlying logistic model. That is, this mixed policy would pick, each round,
max
T 15 (wi, a) - (2 (x), a) aEA
B', XB:)
(and would omit the À update in Box B).
To compute (an approximation of) Xgr, we proceed 100 times as described below to compute estimates
100
which average out into
1
x.
100
where noted that the numerical values obtained for the X x+(() are rather similar. With the notation above, for each j, we sample = 10,000 contexts from the distribution v, and solve
(.)) B
E arg min E
max
( ((XX(X)) ( B, -B. {))] AEA
X
(These estimations are independent from the estimations used to compute the OPT values, i.e., we use different seeds.)
33

---

PGD We refer to the Box B strategy as PGD 7,, for which we report the performance for values Y E {0.01, 0.02, 0.04, 0.05, 0.13.
We also implemented the Box C strategy, with an alternative value Mr,,, given that the one exhibited based the theoretical analysis was conservative, that regime break occurred. We resort to value of the same order of magnitude:
Mr, = c TT 22),
for numerical constant c that we set to 0.01 in our simulations. We call this strategy PGD Adaptive in Figure and Table
G.3 Outcomes of the simulations
We take = 10,000 individuals (instead of T = 1,000 as in the code by Chohlas Wood et al. 2021) and set initial 50 rounds warm start for strategies (mostly because of the logistic estimation). We were limited by the computational power (see Appendix G.4) and could only perform N 100 simulations for each (instance of each) strategy- We report averages (strong lines in the graphs) as well as + times standard errors (shaded areas in the graphs or values in parentheses in the table).
Graphs. In the first line of graphs in Figure I we report the average rewards (over the N runs) of the strategy under scrutiny as a function of the sample size. More precisely, with obvious notation, plot
N
We report the values of OpT(r, B) and OPT(r, B') dashed horizontal lines.
In the second and third lines of graphs Figure T obvious notation, we plot
we report the average costs suffered; again, with
N
N
and
N
(m)
N
(a
Ovancher)
n=1
We include the average budget constraints Bas 0.05 and Byouchr 0.20 as dashed horizontal lines.
Finally, the fourth line of the graphs in Figure reports the fairness costs; we average their absolute values and draw, again with obvious notation,
1
Σ
Σ
1
Σ
i
21 (a(")=a) (gr(al"))s)) 1 11a5" mai)
4
aEfande #voacher gE(0,1)
We include the fairness tolerance as a dashed horizontal line.
Table. We also report the performance of the strategies the final round T in following table, with +2 times standard errors in parentheses. We note that the performance of the mixed policy is poor, in particular in terms of faimess costs, which is why we omitted it on the graphs, keep them readable.
Comments. When y is well set, i.e., large enough (see the bound of Lemma D the PGD strategies control spending costs thanks to targeting B' instead of B. We observe that for 0.01, the PGD strategy does not control the rideshare costs, but for all larger values of 7, the associated strategies control the three costs considered. The average rewards achieved are coherent with the average spendings: the smaller the average spendings, the smaller the average rewards. There is some lag: the strategies tuned with y parameters in (0.04, 0.05, 0.1) could use costly actions more. We also observe that fairness costs remain under the target limits.
The mixed policy does not success in controlling the costs, in particular, the fairness costs. While the optimal dual variables >ig summarize the distribution v, it seems that XB has to be used with care: only with the exact values r and and not with estimates. On the contrary, the PGD strategies of Box are more stable, as the dual variables are learned based also on the estimated reward and cost functions.
34

---

Fairness Tolerance = 1e-7
Fairness Tolerance = 0.025
0.50
0.50
PGD Gamria 0.54
PGD Gamria 0.02
0.49
PCD Gammaa 0.54
0.49
PCD Gammia 0.05
Average Rewards
PCD Gammia 0.1
0.48
PCD Atppiiv
0.48
0.47
OPTIEE
0.47
Opri6 6.
0.44
0.44
0
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
0.10
0.10
0.09
Rideshare Costs
0.08
0.07
0.07
0.06
0.06
0.05
Budget Rideshore
0.05
0.04
0.04
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
0.25
0.25
0.24
0.24
Voucher Costs
0.23
0.23
0.22
0.22
0.21
0.21
0.20
Budgat Mothhe
0.20
0.19
0.19
0.18
0.18
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
0.05
0.05
0.04
0.04
Fairness Costs
0.03
0.03
0.02
0.02
0.01
0.01
0.00
-0.01
-0.01
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Figure 1: Performance of the PGD strategies.
35

---

Table 1: Performance of the strategies as computed at the final round T'.
Average rewards
Rideshare costs
Voucher costs
Fairness costs
Fairness tolerance 10-7
OpT(r, B)
0.4688 (0.0002)
OPT(r,c, B')
0.4648 (0.0002)
PGD = 0.01
0.4651 (0.0002)
0.0519 (<0.0001)
0.1984 (<0.0001)
0.0006 (<0.0001)
PGD 0.02
0.4613 (0.0002)
0.0492 (<0.0001)
0.1967 (0.0004)
0.0004 (<0.0001)
PGD = 0.04
0.4571 (0.0002)
0.0479 (c0.0001)
0.1962 (0.0002)
0.0004 (<00.001)
PGD 0.05
0.4554 (0.0002)
0.0476 (<0.0001)
0.1961 (0.0002)
0.0003 (<0.0001)
PGD 7 0.1
0.4502 (0.0002)
0.0471 (<0.0001)
0.196 (0.0002)
0.0003 (<0.0001)
PGD Adaptive
0.4581 (0.0002)
0.0498 (0.0002)
0.1971 (0.0002)
0.0005 (<0.0001)
Mixed Policy
0.4402 (0.0056)
0.0499 (0.0058)
0.1056 (0.017)
0.0411 (0.0052)
Fairness tolerance 0.025
OPT(r, c, B)
0.4731 (0.0002)
OPT(r, B')
0.4691 (0.0002)
PGD 7 = 0.01
0.4698 (0.0002)
0.0518 (0.0002)
0.1983 (<0.0001)
0.0246 (0.0002)
PGD 0.02
0.4663 (0.0002)
0.0492 (<0.0001)
0.1966 (0.0006)
0.0242 (0.0002)
PGD 7 0.04
0.4621 (0.0004)
0.0478 (c0.0001)
0.1958 (0.001)
0.0223 (0.0004)
PGD 0.05
0.4604 (0.0004)
0.0476 (<0.0001)
0.1955 (0.0014)
0.0208 (0.0004)
PGD 7 0.1
0.4538 (0.0002)
0.0471 (<0.0001)
0.1958 (0.0004)
0.0128 (0.0004)
PGD Adaptive
0.4634 (0.0002)
0.0499 (0.0002)
0.1972 (0.0002)
0.0228 (0.0002)
Mixed Policy
0.4466 (0.0054)
0.0566 (0.0052)
0.1053 (0.0164)
0.0473 (0.0054)
Finally, note that in experiments, the regimes in PGD Adaptive strategy typically covered range
from k = 0 (corresponding " 1/VTT 0.01) to k 2 (corresponding to "/2 2// /TTT 0.04). The PGD Adaptive strategy performs well and is (only) outperformed by the PDG strategy with fixed y 0.02 (of course difficult to pick in advance). In particular, the PGD Adaptive strategy controls costs, and does so by switching to larger step sizes when needed.
G.4 Computation time and environment
As requested by the NeurIPS checklist, provide details the computation time and environment. Our experiments were ran on the following hardware environment: no GPU was required, CPU 3.3 GHz 8 Cores with total of 16 threads, and RAM is 32 GB 4800 MHz DDR5, We ran 100 simulations with 10 different seeds on parallel each time. In the setting and for the data described above, the average time spend each algorithm for single was inferior to 10 minutes.
36


Reviews:
[{"review_id": "y2KOo1Y6Tf", "reviewer": "Reviewer_aT3N", "summary": "The paper considers the problem of general contextual bandits with knapsacks in the regime where Omega(sqrt{T}) <= B <= O(T^{3/4}). The paper provides a new algorithm that is based on prior methodologies of primal-dual algorithm, but instead of relying on them as black-boxes, updates the dual variables using adaptive step-sizes (for the same algorithm using fixed step-size reduces to prior works (e.g., Agrawal and Devanur 2016). The main contribution of this paper is to notice this fact, show a scheduling scheme for the adaptive step-size and prove regret bounds in this regime.", "questions": "Nothing in particular, that could help change my mind. Please see my suggestions above on simulations.", "limitations": "This is a mathematical paper and no societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "+ The proposed algorithm is clean and builds on understanding from prior works. Notion of using adaptive step-sizes is common in the optimization literature and bringing that understanding/techniques to contextual bandits with knapsacks is novel. Combining this with existing primal-dual approach is natural.\n\n+ The paper is well-written and easy to understand. The paper also provides problem dependent lower-bounds and surprisingly (for modern papers) honestly discusses the limitations of the algorithm (e.g., not being able to prove a worst case regret bound, when B is actually large). ", "weaknesses": "- Overall, I do not find the fairness example particularly motivating or the right example. The paper is useful for the mathematical/algorithmic insights. Not sure if this example adds any value to the paper. \n\n- One place where this paper could have really shone is to actually run simulations and show that even in practice the adaptive step-size actually improves the regret in the claimed range. In particular, it would tease out the effect of inability to analyze prior works better vs needing new algorithmic technique (such as adaptive step-size) conclusively.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading and generally agree with the evaluation.\n\nFor the fairness example: It was our own motivating example for developing a CBwK theory able to handle small total-cost constraints. (Chohlas-Wood et al., 2021, who first introduced this example, could not propose regret bounds, see lines 62-73.) Admittedly, better examples could be provided and it is clear that breaking the artifical T^{3/4} barrier in the literature was an interesting problem per se. \n\nFor simulations: Indeed. We only provide (very) preliminary simulations (see pages 33-35), rather illustrating how to successfully deal with the fairness constraints. What these simulations do not illustrate, however, is how useful adaptive step-sizes are: this is because total-cost constraints are never broken therein during the regime k=0. We were too short on time to provide improved simulations investigating the usefulness of the adaptive step-sizes and offering comparisons to other algorithms. We will provide such simulations in the final version of the paper (including a summary thereof in the main body)."}, {"review_id": "mSVaKG8Xba", "reviewer": "Reviewer_EATd", "summary": "This paper studied contextual bandit problems with knapsacks (CBwK). Under this setting, at each time step, a scalar reward is obtained and vector-valued costs are suffered.  The agent aims to maximize the cumulative rewards while ensuring that the cumulative costs are lower than some predetermined cost constraints.\nIn this setting, total cost constraints had so far to be at least of order $T^{3/4}$, where $T$ is the number of time steps, and were even typically assumed to depend linearly on $T$. \nThis paper imposed a fairness constraint by applying the CBwK model and introduced a dual algorithm based on projected-gradient-descent updates in order to deal with total-cost constraints of the order of $\\sqrt{T}$ up to poly-logarithmic terms.\n\n\n================\n\nThe score is kept unchanged.", "questions": "I suggest to compare the performance of the proposed algorithm and some other algorithms with numerical experiments.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is in general well organized and presents a detailed literature review.\n2. The motivation of considering faireness with the CBwK setting is explained and convincing.\n3. Beyond the strengths of the proposed algorithms, the authors also listed the limitations of this work in Section 4.", "weaknesses": "1. My major concern is that no numerical results are presented in this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading and generally agree with the evaluation.\n\nFor the weakness raised: We only provide (very) preliminary simulations (see pages 33-35), rather illustrating how to successfully deal with the fairness constraints. What these simulations do not illustrate, however, is how useful adaptive step-sizes are: this is because total-cost constraints are never broken therein during the regime k=0. We were too short on time to provide improved simulations investigating the usefulness of the adaptive step-sizes and offering comparisons to other algorithms. We will provide such simulations in the final version of the paper (including a summary thereof in the main body)."}, {"review_id": "4oyARMp0RQ", "reviewer": "Reviewer_Hs7n", "summary": "The problem studies the contextual bandit with knapsack problem with contexts coming from a continuous set, signed costs, and under the assumption that expected reward and cost functions can be uniformly estimated. The learner aims at maximizing their cumulative rewards while guaranteeing constraints of the form $\\sum_{t=1}^T c_t\\le TB$, where the rhs $TB$ may be as small as $T^{1/2+\\epsilon}$. The proposed algorithm is based on a projected gradient descent scheme with adaptive step size. The author discuss applications of the algorithm to problems related to fairness. ", "questions": "Can you provide some further details about the statements of the paragraph starting at line 158 (e.g.  what scenarios do you have in mind when you say \"typically\")?", "limitations": "Yes, limitation are adequately discussed. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The authors present an interesting set of results. The model is well motivated and presents some interesting complications wrt the traditional BwK framework. The paper is generally well written and mostly clear. ", "weaknesses": "I don't have any major concern.\n\nSome minor comments:\n\n- Line 113: \"go go\"\n- It would be good to mention closer to Assumption 1 that, in order to derive guarantees, you need  strict feasibility.\n- Paragraph starting at line 158 lacks convincing examples. \n- Assumption 2: why are you defining $\\beta$ there? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading and fully agree with the evaluation.\n\nFor the statements of the paragraph starting at line 158, including twice the word \"typically\": We agree that this paragraph will benefit from some rewriting. For the total spendings B_total, we had in mind the example by Chohlas-Wood et al. [2021], where a constant fraction of the T individuals may benefit from some costly action, hence a linear total budget T B_total, or, put differently, B_total is larger than some positive constant. This is better detailed on page 31 in appendix. For the fairness threshold \\tau, we meant that in some cases we would ideally have \\tau = 0, but due to central-limit-theorem fluctuations, this is not possible and a \\tau with a minimal value of the order of 1/\\sqrt{T} has to be considered. In general, Chohlas-Wood et al. [2021] want to ensure some fair treatment among groups, so would pick some \\tau that is rather small (though would be ready to have it larger than 1/\\sqrt{T} as this entails some positive discrimination and is effective in practice). All in all, we would entirely rewrite this paragraph, by suppressing all occurrences of 'typically' and summarize the ideas above. \n"}, {"review_id": "M8ssFUO5Ei", "reviewer": "Reviewer_3rBq", "summary": "This paper deals with the CBwK problem with a fairness constraint of equalized average costs between groups. The authors propose a dual algorithm: PGD for CBwK (with adaptive stepsize) and provides regret bounds.", "questions": "The authors make an assumption that the respective proportions $\\gamma_g$ is known. Could you please discuss the limitations of such assumption? And what analytical convenience this assumption buys you? Are there any less restrictive alternatives?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The problem statement is pretty clear and the related work is relatively thoroughly presented. The limitations are clearly and explicitly stated.", "weaknesses": "The algorithm (PGD) seems to be established in the online optimization and bandit literature, and the proofs also seem standard. Also the regret bound is only superior under some circumstances (e.g. not working for soft constraints, loose bound when for example null action has null reward). My major concern is on the novelty. I think to stand out from the existing papers, the authors may want to specify a more narrow scheme and claim the contributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the reading but would respectfully disagree with the evaluation.\n\nFor the PGD algorithm (and the proofs) being standard: Yes, the PGD approaches in the CBwK litterature are standard, as we acknowledge and as other rewievers point out (see, e.g., Agrawal and Devanur 2016). Our main point, however, is the adaptive step-size tuning of PGD. We carefully explain in lines 229-244 why and how previous contributions provided suboptimal tunings for PGD, leading to the impossibility of going beyond the T^{3/4} total-cost constraint. Section 3.2 then provides our main contribution: a careful adaptive tuning of the hyperparameters of PGD, allowing to total-cost constraints as small as 1/\\sqrt{T} up to logarithmic factors. We agree and acknowledge that its analysis partially relies on some known building blocks. \n\nFor the regret bound being only superior under some circumstances (e.g., not working for soft constraints, loose bound when for example null action has null reward): We would like to discuss more in depth this comment, which we object to. \n- First, Section 3.3 explains in detail why our bounds in terms of the norms of \\lambda^* are sharper than the usual OPT/min B bounds of the literature. This new form of the bound is important in view of the lower bounds alluded at in lines 330-331 and because it does not require the existence of a null-cost action. So, our bounds do provide improvement upon the literature.\n- Second, the literature was only (and rightfully) interested in hard constraints so far. We introduce in appendix the concept of soft constraints, as we noticed some new phenomena in this setting compared to the usual hard-constraints setting. We actually deal with them in some optimal manner, but with a different algorithm---a primal strategy, see Section F in the supplementary material. Dealing with such (non-classical) soft constraints is an open problem for the PGD strategy considered in the main body. It is also an open problem for all previous strategies in the literature (that did not cover this aspect). To sum up, we have identified tackling soft constraints as a possible extension to CBwK theory, not addressed so far in the literature, and for which we provide partial results (with a primal algorithm). This, in our opinion, cannot be considered as a weakness, on the contrary.\n- Third, the 'loose bound’ is the classical bound in the literature, and it is generally optimal. We mention in Limitation 2 that however, faster rates should be possible in some very specific settings---a possibility which was not identified at all in the literature. The precise study of this very specific, yet interesting, setting would require some space not available in a NeurIPS format. This new insight should then be seen as an open problem stimulating future research, rather than a weakness of our contribution.\n\nFor not claiming the contributions: We summarized them in lines 48-59 in Section 1. \n\nFor the respective proportions gamma_g being known: In practice (at least in the example by Chohlas-Wood et al. [2021]) this should be a mild restriction, that is not unheard of in the fairness literature. It amounts to having a reasonable knowledge of the breakdown of the population into subgroups. We use this assumption in line 156: the cost function is then known, as required. Replacing T \\gamma in line 154 by the empirical number of individuals in the group induces many additional technicalities, while it only presents a limited practical interest, given that the fairness literature has little issues with assuming a reasonable knowledge of the breakdown of the population into subgroups. "}]

Author rebuttal:
We generally agree with the evaluations by Reviewers aT3N - EATd - Hs7n but respectfully disagree with the evaluation by Reviewer 3rBq. We explain below in detail the main two issues we disagree with: 
- The main algorithmic contribution is not the PGD approach per se, but its adaptive step-size tuning (see lines 229-244), for which we present a novel contribution, namely, handling the total-cost regime Omega(sqrt{T}) <= T B <= O(T^{3/4}).
- Our regret bound is sharper than existing bounds in the literature (with some norm of \lambda^* replacing the larger OPT/min B term, see Section 3.3) and does not require a null-cost action. That being said, we have identified possible improvements and extensions (listed in Section 4) that are not addressed in the literature, and that we propose as open problems for future research.

Meta-review: The paper considers the problem of general contextual bandits with knapsacks where the the budget is considerably much smaller than the time horizon. This is a new and challenging setting as the underlying offline knapsack problem is also much harder. In particular, for the case the budget is of magnitude of T and the costs are bounded above by constants, the underlying offline (unbounded) knapsack problem has a computational complexity in P (see the work of Pisinger for more details). Note that this was the common setting that ALL the prior work in knapsack bandits relied on.

The new setting moves away from this rather restrictive assumption and the authors provide a new algorithm that is based on prior methodologies of primal-dual algorithm, but instead of relying on them as black-boxes, updates the dual variables using adaptive step-sizes (for the same algorithm using fixed step-size reduces to prior works (e.g., Agrawal and Devanur 2016). The main contributions of this paper are: (i) to design a new scheduling scheme for the adaptive step-size;  and (ii) prove regret bounds for this setting.

There was a disagreement between the reviewers, as one stated that this paper is rather incremental. I strongly disagree with this statement. As someone very familiar with knapsack bandit literature, and claim that bandits with small total cost constraints is a very new and challenging setting (personally I have been working on this for a few years now, without much success). I am very glad that the authors has managed to provide a first non-trivial result in this open question. Therefore I strongly recommend to accept this paper.
Decision: Accept (poster)