Evgenii Chzhen
email: evgenii.chzhen@universite-paris-saclay.fr

Christophe Giraud
email: christophe.giraud@universite-paris-saclay.fr

Zhen Li
email: zhen.li@bnpparibas.com

Gilles Stoltz
email: gilles.stoltz@universite-paris-saclay.fr

Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with Application to Fairness

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 estimateda 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 √ 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

√

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.

1 Setting, literature review, and main contributions

We consider contextual bandits with knapsacks [CBwK], a setting where at each round t 1, the learner, after observing some context x t ∈ X , where X ⊆ R n , picks an action a t ∈ A in a finite set A. We do not impose the existence of a null-cost action. Contexts are independently drawn according to a distribution ν. The learner may pick a t at random according to a probability distribution, denoted by π t (x t ) = π t,a (x t ) a∈A for consistency with the notion of policy defined later in Section 2. The action a t played leads to some scalar reward r t ∈ [0, 1] and some signed vector-valued cost c t ∈ [-1, 1] d . Actually, r t and c t are generated independently at random in a way such that the conditional expectations of r t and c t given the past, x t , and a t , equal r(x t , a t ) and c(x t , a t ), respectively. We denoted here by r : X × A → [0, 1] and c = (c 1 , . . . , c d ) : X × A → [-1, 1] d the unknown expected-reward and expected-cost functions. The modeling and the estimation of r

 [START_REF] Chohlas-Wood | Learning to be fair: A consequentialist approach to equitable decision-making[END_REF]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 T B were so far typically assumed to be linear, which is undesirable in fairness applications, where one wishes that T B is sublinear-and actually, is sometimes as close as possible to the natural √ T deviations suffered even in a perfectly fair random allocation scheme. Also, there is no null-cost action and costs are signed-two twists to the typical settings of CBwK that only [START_REF] Slivkins | Contextual bandits with packing and covering constraints: A modular Lagrangian approach via regression[END_REF] 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 T B. The literature so far mostly considered linear total-cost constraints T B (see, e.g., [START_REF] Han | Optimal contextual bandits with knapsacks under realizability via regression oracles[END_REF][START_REF] Ai | On the re-solving heuristic for (binary) contextual bandits with knapsacks[END_REF] among recent references), with two series of exceptions: (i) the primal strategy by [START_REF] Li | Contextual bandits with knapsacks for a conversion model[END_REF] handling total-cost contraints of the order of

√

T up to poly-logarithmic terms but critically assuming the finiteness of the context set X ; and (ii) the two-stage dual strategies of Agrawal and Devanur [2016], [START_REF] Han | Optimal contextual bandits with knapsacks under realizability via regression oracles[END_REF] handling T 3/4 total-cost constraints. These two-stage strategies use

√

T 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 T 3/4 ; see discussions after Lemma 2. In contrast, we provide a 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 T B j T 3/4 (actually, any rate T B j T 1/2+ε is suitable for a sublinear regret), while for other components k, the total-cost constraints T B k 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 on learning a finite-dimensional parameter given by the optimal dual variables λ (see the beginning of Section 3), while primal approaches rely on learning the distribution ν of the contexts in L 1 -distance. This may be achieved in some cases, like finiteness of the context set X (Li andStoltz, 2022, Ai et al., 2022) or, at the cost of degraded regret bounds and under additional assumptions on ν when resorting to L 1 -density-estimation techniques [START_REF] Ai | On the re-solving heuristic for (binary) contextual bandits with knapsacks[END_REF]. On top of these strong limitations, such primal approaches are also typically computationally inefficient as they require the computation of expectations over estimates of ν.

Typical CBwK strategies: dual approaches are modular and somewhat indirect. Typical dual approaches in CBwK take two general forms. One, illustrated in [START_REF] Slivkins | Contextual bandits with packing and covering constraints: A modular Lagrangian approach via regression[END_REF] (extending the non-contextual approach by [START_REF] Immorlica | Adversarial bandits with knapsacks[END_REF], takes a game-theoretic 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 a t and an opponent picking dual variables λ t . The second approach (Agrawal andDevanur, 2016, Han et al., 2022) learns more directly the λ t via some online convex optimization algorithm fed with the suffered costs c t ; this second approach however requires, at the stage of picking a t , a suitable bound Z on the norms of the λ t .

The dual strategies discussed above are modular and indirect as they all consist of using as 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 t that maximizes the Lagrangian penalization of rewards by costs through the current λ t-1 (see Step 2 in Box B), as also proposed by Agrawal and Devanur [2016] (while [START_REF] Han | Optimal contextual bandits with knapsacks under realizability via regression oracles[END_REF] add some randomization to this step), and then, performs some direct, explicit, projected-gradient-descent update on λ t-1 to obtain λ t , with step size γ. We carefully and explicitly tune γ (in a 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-purpose 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 a nullcost action, we provide refined regret bounds that go beyond the typical (OPT(r, c, B)/ min B)

√

T bound offered by the literature so far (see, among others, Agrawal and Devanur, 2016[START_REF] Li | Contextual bandits with knapsacks for a conversion model[END_REF][START_REF] Han | Optimal contextual bandits with knapsacks under realizability via regression oracles[END_REF], where OPT(r, c, B) denotes the expected reward achieved by the optimal static policy (see Section 2 for definitions). Namely, our bounds are of the order of λ

√

T , where λ 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 -α) min B , for some α < 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 explain why λ

√

T appears as the correct target. We compare therein our problem-dependent lower bound-approach to the minimax ones of [START_REF] Han | Optimal contextual bandits with knapsacks under realizability via regression oracles[END_REF] and [START_REF] Slivkins | Contextual bandits with packing and covering constraints: A modular Lagrangian approach via regression[END_REF].

Outline

In Section 2, we further describe the problem of CBwK (by defining the regret and recalling how r and c may be estimated) and state our motivating example of fairness. Section 3 is devoted to our new dual strategy, which we analyze first with a fixed step size γ, for which we move next to an 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 to optimality.

2 Further description of the setting, and statement of our motivating example

We define a static policy as a mapping π : X → P(A), where P(A) denotes the set of probability distributions over A. We denote by π = (π a ) a∈A the components of π. We let E X∼ν indicate that the expectation is taken over the random variable X with distribution ν. 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 , ν) is feasible if there exists a stationary policy π such that E X∼ν a∈A c(X, a) π a (X) B .

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 a feasible problem (r, c, B , ν), the optimal static policy π is defined as the policy π : X → P(A) achieving Maximizing the sum of the r t amounts to minimizing the regret R T = T OPT(r, c, B ) -T t=1 r t .

Motivating example: fairness-equalized average costs between groups

This example is inspired from [START_REF] Chohlas-Wood | Learning to be fair: A consequentialist approach to equitable decision-making[END_REF] (who did not provide a strategy to minimize regret), and features a total budget constraint T B total 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 t include the group index gr(x t ) ∈ 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) ∈ X × A, on top of leading to some expected reward r(x, a), also corresponds to some spendings c spd (x, a). We recall that we denoted that r t and c t (here, this is a scalar for now) the individual payoffs and costs obtained at round t; they have conditional expectations r(x t , a t ) and c spd (x t , a t ). 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 or of public money not optimally used. [START_REF] Chohlas-Wood | Learning to be fair: A consequentialist approach to equitable decision-making[END_REF] consider a situation where unfavored groups should get slightly more spendings than favored groups.)

Formally, we denote by gr(x) ∈ G the group to which a given context x belongs and introduce a 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 γ g = ν x : gr(x) = g of the sub-groups may be known. 1 The total-budget and fairness constraints then read:

T t=1 c t T B total and ∀g ∈ G, 1 T γ g T t=1 c t 1 {gr(xt)=g} - 1 T T t=1 c t τ ,
which corresponds, in the setting of Box A, to the following vector-valued expected-cost function c, with d = 1 + 2|G| components and with values in

[-1, 1] 1+2|G| : c(x, a) = c spd (x, a), c spd (x, a)1 {gr(x)=g} -γ g c spd (x, a), γ g c spd (x, a) -c spd (x, a)1 {gr(x)=g} g∈G
as well as to the average-constraint vector B = B total , γ g τ, γ g τ g∈G .

The regimes we have in mind, and that correspond to the public-policy issues reported by [START_REF] Chohlas-Wood | Learning to be fair: A consequentialist approach to equitable decision-making[END_REF], are that the per-instance budget B total is larger than a positive constant, i.e., a constant fraction of the T individuals may benefit from some costly action(s), while the fairness threshold τ must be small, and even, as small as possible. Because of central-limit-theorem fluctuations, a minimal value of the order of 1/ √ T , or slightly larger (up to logarithmic terms, say), has to be considered for τ . The salient point is that the components of B may therefore be of different orders of magnitude, some of them being as small as 1/

√

T , up to logarithmic terms. More details on this example and numerical simulations about it are provided in Section 5 and Appendix G.

Modelings for, and estimation of, expected-reward and expected-cost functions

As is common in the literature (see [START_REF] Han | Optimal contextual bandits with knapsacks under realizability via regression oracles[END_REF][START_REF] Slivkins | Contextual bandits with packing and covering constraints: A modular Lagrangian approach via regression[END_REF], 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 t picked by the main strategy (this is what the "otherwise" is related to therein). We denote by r t : X × A → [0, 1] and c t : X × A → [-1, 1] d the estimations built based on (x s , a s , r s , c s ) s t , for t 1. We also assume that initial estimations r 0 and c 0 , based on no data, are available. We denote by 1 the column-vector (1, . . . , 1). Assumption 2. There exists an estimation procedure such that for all individual sequences of contexts x 1 , x 2 , . . . and of actions a 1 , a 2 , . . . played otherwise, there exist known error functions ε t : X × A × (0, 1] → [0, 1], relying each on the pairs (x s , a s ) s t , where t = 0, 1, 2, . . ., ensuring that for all δ ∈ (0, 1], with probability at least 1 -δ, ∀0 t T, ∀x ∈ X , ∀a ∈ A, r t (x, a) -r(x, a) ε t (x, a, δ)

and c t (x, a) -c(x, a) ε t (x, a, δ) 1 ,
where we assume in addition that β T,δ

def = T t=1 ε t-1 (x t , a t , δ) = O √ T ln T δ .
This assumption is satisfied at least for the two modelings discussed below, which are both of the form: for known transfer functions ϕ, link functions Φ, and normalization function η, for some unknown finite-dimensional parameters µ , θ ,1 , . . . , θ ,d ,

∀x ∈ X , ∀a ∈ A, r(x, a) = η r (a, x) Φ r ϕ r (x, a) T µ ,
and for all

1 i d, c i (x, a) = η c,i (a, x) Φ c,i ϕ c,i (x, a) T θ ,i .
See also the exposition by Han et al. [2022, Section 3.3].

Based on Assumption 2 and given the ranges [0, 1] for rewards and [-1, 1] d for costs, we may now define the following (clipped) upper-and lower-confidence bounds : given a confidence level 1 -δ where δ ∈ (0, 1], for all t T , for all x ∈ X and a ∈ A,

r ucb δ,t (x, a) def = clip r t (x, a)+ε t (x, a, δ) 1 0 and c lcb δ,t (x, a) def = clip c t (x, a)-ε t (x, a, δ)1 1 -1 , (2
) where we define clipping by clip[x] u = min max{x, }, u for a scalar value x ∈ R and lower and upper bounds and u, and apply clipping component-wise to vectors. Under Assumption 2, we have that for all δ ∈ (0, 1], with probability at least 1 -δ, ∀0 t T, ∀x ∈ X , ∀a ∈ A, r(x, a) r ucb δ,t (x, a) r(x, a) + 2ε t (x, a, δ) and c(x, a) -2ε t (x, a, δ)1 c lcb δ,t (x) c(x, a) .

(3)

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 a t+1 played, and only these, we will also use the control from the other side, which will lead to manageable sums of ε t (x t+1 , a t+1 , δ), given the control on β T,δ by Assumption 2.

Modeling 1: Linear modeling. Agrawal and Devanur [2016] (see also [START_REF] Li | Contextual bandits with knapsacks for a conversion model[END_REF], Appendix E) consider the case of a linear modeling where η r = η 1 = . . . = η d ≡ 1 and Φ is the identity (together with assumptions on the range of ϕ and on the norms of µ and the θ ,i ).

The LinUCB strategy by [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF] may be slightly adapted (to take care of the existence of a transfer function ϕ depending on the actions taken) to show that Assumption 2 holds; see Li and Stoltz [2022, Appendix E, Lemma 3].

Modeling 2: Conversion model based on logistic bandits. Li and Stoltz [2022, Sections 1-5] discuss the case where Φ(x) = 1/(1 + e -x ) for rewards and costs. The Logistic-UCB1 algorithm of [START_REF] Faury | Improved optimistic algorithms for logistic bandits[END_REF] (see also an earlier version by [START_REF] Filippi | Parametric bandits: The generalized linear case[END_REF]

OPT(r, c, B) = sup π:X →P(A) inf λ 0 E X∼ν a∈A r(X, a) π a (X) + λ, B - a∈A c(X, a) π a (X) = min λ 0 sup π:X →P(A) E X∼ν a∈A π a (X) r(X, a) -c(X, a) -B, λ = min λ 0 E X∼ν max a∈A r(X, a) -c(X, a) -B, λ . (4)
We denote by λ B a vector λ 0 achieving the minimum in the final equality. Virtually all previous contributions to (contextual) bandits with knapsacks learned the dual optimal λ in some way; see the discussion in Main contribution #3 in Section 1. 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 over X ∼ ν replaced by a point evaluation at x t , and that it sequentially chooses some λ t based on projected-gradient-descent 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 γ 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 γ > 0; number of rounds T ; confidence level 1 -δ; margin b on the average constraints; estimation procedure and error functions ε t of Assumption 2; optimistic estimates (2)

Initialization: λ 0 = 0; initial estimates r ucb δ,0 and c lcb δ,0

For rounds t = 1, 2, 3, . . . , T :

1. Observe the context x t ; 2. Pick an action a t ∈ A achieving

max a∈A r ucb δ,t-1 (x t , a) -c lcb δ,t-1 (x t , a) -(B -b1), λ t-1 ;
3. Observe the payoff r t and the costs c t ;

4. Compute λ t = λ t-1 + γ c lcb δ,t-1 (x t , a t ) -(B -b1) + ;
5. Compute the estimates r ucb δ,t and c lcb δ,t .

Analysis for a fixed step size γ

The strategy of Box B is analyzed through two lemmas. We let min v = min{v 1 , . . . , v d } > 0 denote the smallest component of a vector v ∈ (0, +∞) d and take a margin b in (0, min B). We assume that the problem is feasible for some B < B -b1, and denote by λ B-b1 the vector achieving the minimum in (4) when the per-round cost constraint is B -b1. We use • for the Euclidean norm. The bounds of Lemmas 1 and 2 critically rely on λ B-b1 , which we bound and interpret below in Section 3.3. We denote

Υ T,δ = max β T,δ/4 , 2 dT ln T 2 δ/4 , 2T ln 2(d + 1)T δ/4 .
Lemma 1. Fix δ ∈ (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 δ/4 ensures that the costs satisfy, with probability at least 1 -δ,

∀ 1 t T, t τ =1 c τ -t (B -b1) + 1 + 3 λ B-b1 γ + 20 √ d Υ T,δ .
Lemma 2. Fix δ ∈ (0, 1) and 0 < b < min B. Under the same assumptions as in Lemma 1 and on the same event with probability at least 1 -δ as therein, the regret of the Box B strategy run with δ/4 satisfies

∀ 1 t T, R t λ B-b1 t b √ d + 6Υ T,δ + 36γ √ d Υ T,δ 2 + 8ln T 2 δ/4 .
Ideal choice of γ. The margin b will be taken proportional to the high-probability deviation provided by Lemma 1, divided by T . Now, the bounds of Lemmas 1 and 2 are respectively of the order

T b ∼ 1 + λ B-b1 /γ + √ T and λ B-b1 T b + √ T + γT ,
again, up to logarithmic factors. To optimize each of these bounds, we therefore wish that b be of order 1/ √ T and that γ be of the order of λ B-b1 / √ T . Of course, this wish stumbles across the same issues of ignoring a beforehand bound on λ B-b1 , exactly like, e.g., in Agrawal and Devanur [2016], [START_REF] Han | Optimal contextual bandits with knapsacks under realizability via regression oracles[END_REF] (where this bound is denoted by Z). We were however able to overcome this issue in a satisfactory way, i.e., by obtaining the ideal bounds implied above through adaptive choices of γ, discussed in Section 3.2.

Suboptimal choices of γ. When γ is badly set, e.g., γ = 1/ √ T , the order of magnitude of the regret remains larger than λ B-b1 T b and the cost deviations to T (B -b1) become of the larger order λ B-b1

√

T , which dictates a larger choice for T b. Namely, if in addition λ B-b1 is bounded in some worst-case way by 1/ min B (see Section 3.3), the margin T b is set of the order of √ T / min B. But of course, this margin must remain smaller than the total-cost constraints T B. This is the fundamental source of the typical min B T -1/4 constraints on the average cost constraints B observed in the literature: see, e.g., Agrawal andDevanur, 2016, Han et al., 2022, where the hyperparameter Z plays exactly the role of λ B-b1 .

Proof sketch. Lemmas 1 and 2 are proved in detail in Appendix B; the two proofs are similar and we sketch here the one for Lemma 1. The derivations below hold on the intersection of four events of probability at least 1 -δ/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 inequality. In this sketch of proof, denotes inequalities holding up to small terms.

By the Hoeffding-Azuma inequality and by Assumption 2, the sum of the c τ -(B -b1) is not much larger than the sum of the ∆ c τ = c lcb δ/4,τ -1 (x τ , a τ ) -(B -b1). We bound the latter by noting that by definition, λ τ λ τ -1 + γ∆ c τ , so that after telescoping,

t τ =1 c τ -t(B -b1) + t τ =1 ∆ c τ + λ t γ λ B-b1 γ + λ B-b1 -λ t γ . (5)
We are thus left with bounding the λ B-b1 -λ t . The classical bound in (projected) gradient-descent analyses (see, e.g., [START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF] reads:

λ τ -λ B-b1 2 -λ τ -1 -λ B-b1 2 2γ ∆ c τ , λ τ -1 -λ B-b1 + γ 2 4d ∆ c τ 2 .
The estimates of Assumption 2, and the definition of a t as the argument of some maximum, entail

∆ c τ , λ τ -1 -λ B-b1 = c lcb δ/4,τ -1 (x τ , a τ )-(B-b1), λ τ -1 -λ B-b1 g τ (λ B-b1 )-g τ (λ τ -1 ) , where g τ (λ) = max a∈A r(x τ , a) -c(x τ , a) -(B -b1), λ .
We also introduce

Λ t = √ d max 1 τ t λ B-b1 -λ τ -1 .
We sum up the bounds above, use telescoping, and get

λ t -λ B-b1 2 λ B-b1 2 + 4d γ 2 t + 2γ τ t g τ (λ B-b1 ) -g τ (λ τ -1 ) 0+3Λt √ t ln(T /δ) , (6)
where the of the sum in the right-hand side comes from a version of Bernstein's inequality, the fact that E g τ (λ B-b1 ) = OPT(r, c, B -b1) is larger than the conditional expectation of g τ (λ τ -1 ). Since ( 6) holds for all t, we may then show by induction that for some constants and ,

λ t -λ B-b1 λ B-b1 + γΥ T ,
and we conclude by substituting this inequality into (5).

Meta-stategy with adaptive step size γ

As indicated after the statements of Lemmas 1 and 2, we want a (meta-)strategy adaptively setting γ to learn λ B-b1 . We do so via a doubling trick using the Box B strategy as a routine and step sizes of the form γ k = 2 k / √ T in regimes k 0; 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 , δ, and d.

BOX C: PROJECTED GRADIENT DESCENT FOR CBWK WITH ADAPTIVE STEP SIZE

Inputs: number of rounds T ; confidence level 1 -δ; margin b on the average constraints; estimation procedure and error functions ε t of Assumption 2; optimistic estimates (2)

Initialization: T 0 = 1; sequence γ k = 2 k / √ T of step sizes; sequence M T,δ,k = 4 √ T + 20 √ d Υ T,δ/(k+2) 2 of

cost deviations

For regimes k = 0, 1, 2, . . .:

• Take a fresh start of the Box B strategy with step size γ k , risk level δ/ 4(k + 2) 2 , and margin b;

• Run it for t T k until t τ =T k c τ -(t -T k + 1) (B -b1) + > M T,δ,k ;
• Stop regime k, and move to regime k + 1 for the next round, i.e., T k+1 = t + 1.

Bandit problems containing a null-cost action (which is a typical assumption in the CBwK literature) are feasible for all cost constraints B 0; the assumption of (B -2b T 1)-feasibility in Theorem 1 below is therefore a mild assumption. Apart from this, the following theorem only imposes that the average cost constraints are larger than 1/

√

T , up to poly-logarithmic terms. We let O denote orders of magnitude in T up to poly-logarithmic terms.

For x > 0, we denote by ilog x = log 2 x the upper integer part of the base-2 logarithm of x. Theorem 1. Fix δ ∈ (0, 1) and let Assumption 2 hold. Consider the Box C meta-strategy, run with confidence level 1 -δ and with margin b

T = (1 + ilog T ) M T,δ,ilog T + 2 √ d /T = O 1/ √ T .
If the average cost constraints B are such that B 2b T 1 and if the problem (r, c, B -2b T 1, ν) is feasible, then this meta-strategy satisfies, with probability at least 1 -δ:

R T O 1 + λ B-b T 1 √ T and t T c t T B ,
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 k the realized lengths of the regime. First, the number of regimes is bounded by noting that if regime K = ilog λ B-b T 1 is achieved, then by Lemma 1 and the choice of M T,δ,K , the stopping condition of regime K will never be met; thus, at most K + 1 regimes take place. We also prove that ilog λ B-b T 1 K T = ilog T . Second, on each regime k, the difference of cumulated costs to k (B -b T 1) is smaller than M T,δ,k by design, so that the total cumulative costs are smaller than T (B -b T 1) plus something of the order of (K T + 1) M T,δ,K T , which is a quantity that only depends on T , δ, d, and not on the unknown λ B-b T 1 , and that we take for T b T . Third, we similarly sum the regret bounds of Lemma 2 over the regimes: keeping in mind that b T = O √ T , we have sums of the form

λ B-b T 1 k K b T k + √ T λ B-b T 1 O √ T and k K γ k T 2 K+1 √ T 4 λ B-b T 1 √ T .

Discussion of the obtained regret bounds

The regret bound of Theorem 1 features a multiplicative factor λ B-b T 1 instead of the typical factor OPT(r, c, B)/ min B proposed by the literature (see, e.g., Agrawal and Devanur, 2016[START_REF] Li | Contextual bandits with knapsacks for a conversion model[END_REF][START_REF] Han | Optimal contextual bandits with knapsacks under realizability via regression oracles[END_REF]. In view of the lower bound proof scheme discussed in Section 4, this bound λ B-b T 1 √ T seems the optimal bound. We thus now provide bounds on λ B-b T 1 that have some natural interpretation. We recall that feasibility was defined in Assumption 1. The elementary proofs of Lemma 3 and Corollary 1 are based on (4) and may be found in Appendix D.

Lemma 3. Let b ∈ [0, min B) and let 0 B < B -b1. If the contextual bandit problem with knapsacks (r, c, B , ν) is feasible for some B < B, then λ B-b1 OPT(r, c, B -b1) -OPT r, c, B min B -b1 -B .
Corollary 1. When there exists a null-cost action, λ B-b1

2 OPT(r, c, B) -OPT(r, c, 0) min B for all b ∈ [0, min B/2].
The bounds provided by Lemma 3 and Corollary 1 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 a null with some positive expected rewards and no cost, and additional actions with larger rewards and scalar expected costs c(x, a) α > 0. Denote by B the average cost constraint. Then actions a = a null may only be played at most B/α times on average, and therefore, OPT(r, c, B) -OPT(r, c, 0) B/α. In particular, the bound stated in Corollary 1 may be further upper bounded by 1/(2α), which is fully independent of T and B; i.e., a √ T -regret only is suffered in Theorem 1.

Optimality of the upper bounds, and limitations

The main limitations to our work are relative, in our eyes, to the optimality of the bounds achievedup to one limitation, already discussed in Section 2.1: our fairness 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 a minimax sense than the ones obtained for non-contextual bandits with knapsacks (see, e.g., Agrawal and[START_REF] Agrawal | An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives[END_REF][START_REF] Li | Contextual bandits with knapsacks for a conversion model[END_REF], or by leveraging a minimax regret lower bound for a subroutine of the strategy used [START_REF] Slivkins | Contextual bandits with packing and covering constraints: A modular Lagrangian approach via regression[END_REF]. We rather focus on problem-dependent regret bounds but only offer a proof scheme, to be made more formal-see Appendix E.1. 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 b T of order 1/ √ T to satisfy the total T B cost constraints. This imposes that only T OPT(r, c, B -b T 1) is targeted, thus the regret is at least of order

T OPT(r, c, B) -OPT(r, c, B -b T 1) + √ T , i.e., 1 + λ B √ T .
This matches the bound of Theorem 1, but with λ B-b T 1 replaced by λ B .

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 1 and 2, we did not try to optimize the constants but targeted readability. The resulting values in Theorem 1, namely, the recommended choice of b T and the closed-form bound ( 19) on the regret, therefore involve constants that are much larger than needed.

Limitation 2: Not capturing possibly fast regret rates in some cases. Second, a careful inspection of our proof scheme for lower bounds shows that it only works in the absence of a null-cost action.

When such a null-cost action exists and costs are non-negative, Example 1 shows that costly actions are played at most B/α times on average. If the null-cost action has also a null reward, the costly actions are the only ones generating some stochasticity, thus, we expect that the √ T factors (coming, among others, from a version of Bernstein's inequality) be replaced by B/α factors. As a consequence, in the setting of Example 1, bounds growing much slower than

√

T should be achievable, see the discussion in Appendix E.1.

Limitation 3:

√ T regret not captured in case of softer constraints. For the primal strategy discussed in Appendix F, we could prove a general

√

T regret bound in the case where total costs smaller than T B + O √ T are allowed. We were unable to do so for our dual strategy.

Brief overview of the numerical experiments performed

In Appendix G, we implement a specific version of the motivating example of Section 2.1, as proposed by [START_REF] Chohlas-Wood | Learning to be fair: A consequentialist approach to equitable decision-making[END_REF] in the public repository https://github.com/ stanford-policylab/learning-to-be-fair. 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 τ = 10 -7 . The Box B strategies with fixed step sizes may fail to control the budget when γ is too large: we observe this for γ = 0.01. We see overall a tradeoff between larger average rewards and larger average costs. The Box C strategy navigates between three regimes, γ = 0.01 to start (regime k = 0), then γ = 0.02 (regime k = 1), and finally γ = 0.04 (regime k = 2), which it sticks to. It overall adaptively finds a decent tuning of γ. In this section, we explain why the equalities (4) hold when the problem (r, c, B , ν) is feasible for some B < B. We restate first these inequalities for the convenience of the reader:

OPT(r, c, B) = sup π:X →P(A) inf λ 0 E X∼ν a∈A r(X, a) π a (X) + λ, B - a∈A c(X, a) π a (X) ( ) = min λ 0 sup π:X →P(A) E X∼ν a∈A π a (X) r(X, a) -c(X, a) -B, λ = min λ 0 E X∼ν max a∈A r(X, a) -c(X, a) -B, λ .
We deal here with a linear program, with primal variables in functional space X → R A and dual variables in the finite-dimensional space R d .

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 λ 0 equals -∞ for policies with expected costs strictly larger than B and is achieved at λ = 0 otherwise. The third inequality follows from identifying that for a given λ, the best policy may be defined pointwise as the argument of the maximum written in the expectation. Thus, only the middle equality ( ) deserves a proof. We obtain it by applying a general theorem of strong duality (which requires feasibility for slightly smaller cost constraints).

Statement of a general theorem of strong duality. We restate a result extracted from the monograph by [START_REF] Luenberger | Optimization by Vector Space Methods[END_REF]. It relies on the dual functional ϕ, whose expression we recall below.

Theorem 2 (stated as Theorem 1 in Section 8.6, page 224 in [START_REF] Luenberger | Optimization by Vector Space Methods[END_REF]. Let f be a realvalued convex functional defined on a convex subset Ω of a vector space X, and let G be a convex mapping of X into a normed space Z. Suppose there exists an x 1 such that G(x 1 ) < θ and that

µ 0 = inf f (x) : G(x) θ, x ∈ Ω is finite. Then inf G(x) θ x∈Ω f (x) = max z θ ϕ(z )
and the maximum on the right is achieved by some z 0 θ.

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 P ⊂ Z, and let P = z ∈ Z : ∀ z ∈ P, z, z 0 be its corresponding positive cone in the dual space Z . The dual functional is defined, for each element z ∈ P , as

ϕ(z ) = inf x∈Ω f (x) + G(x), z .
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 → P(A), and note that the function f is actually linear in our situation:

f (π) = -E X∼ν a∈A r(X, a) π a (X) .
(We take asign to match the form of the minimization problem over π in Theorem 2.) We take

Z = R d = Z with positive cones P = P = [0, +∞) d . The mapping G is a linear mapping from X to Z = R d : G(π) = E X∼ν a∈A c(X, a) π a (X) -B ,
and we take θ = 0. We have that µ 0 = OPT(r, c, B) is indeed finite. We note that the condition "(r, c, B , ν) is feasible for some B < B" is required to apply the theorem. The result follows from noting that we exactly have, for z = λ ∈ P ,

ϕ(λ) = inf π:X →P(A) E X∼ν - a∈A r(X, a) π a (X) + a∈A c(X, a) -B, λ π a (X) .

B Proofs of Lemmas 1 and 2

In both proofs, we will use the following deviation inequalities, holding on an event E H-Az ∩ E β of probability at least 1 -δ/2, where the event E β is defined in Assumption 2 with a confidence level 1 -δ/4 and the event E H-Az is defined below: on

E H-Az ∩ E β , ∀ 1 t T, t τ =1 c τ α t,δ/4 + 2β t,δ/4 1 + t τ =1 c lcb δ/4,τ -1 (x τ , a τ ) (7)
and

t τ =1 r τ -α t,δ/4 + 2β t,δ/4 + t τ =1 r ucb δ/4,τ -1 (x τ , a τ ) , (8)
where β t,δ/4 is also defined in Assumption 2 and

α t,δ/4 = 2t ln 2(d + 1)T δ/4 .
These inequalities come, on the one hand, by the Hoeffding-Azuma inequality applied (d + 1)T times on the range [-1, 1]: it ensures that on an event E H-Az with probability at least 1 -δ/4, for all

1 t T , t τ =1 c τ - t τ =1 c(x τ , a τ ) ∞ α t,δ/4 1 and t τ =1 r τ - t τ =1 r(x τ , a τ ) α t,δ/4
(where we denoted by • ∞ the supremum norm). On the other hand, Assumption 2 and the clipping (3) entail, in particular, that on an event E β of probability at least 1 -δ/4, for all 1 t T ,

t τ =1 c(x τ , a τ ) t τ =1 c lcb δ/4,τ -1 (x τ , a τ ) + 2ε τ -1 (x τ , a τ , δ/4) 1 = 2β t,δ/4 1 + t τ =1 c lcb δ/4,τ -1 (x τ , a τ )
and (similarly)

t τ =1 r(x τ , a τ ) -2β t,δ/4 + t τ =1
r ucb δ/4,τ -1 (x τ , a τ ) .

B.1 Proof of Lemma 1

For τ 1, by definition of λ τ in Box B,

λ τ -λ τ -1 = λ τ -1 + γ c lcb δ/4,τ -1 (x τ , a τ ) -(B -b1) + -λ τ -1 γ c lcb δ/4,τ -1 (x τ , a τ ) -(B -b1) .
For t 1, as λ 0 = 0 and λ t 0, we get, after telescoping and taking non-negative parts,

λ t γ t τ =1 c lcb δ/4,τ -1 (x τ , a τ ) -(B -b1) + , thus t τ =1 c lcb δ/4,τ -1 (x τ , a τ ) -(B -b1) + λ t γ . ( 9
)
Up to the deviation terms (7), λ t /γ bounds how larger the cost constraints till round t are from t(B -b1). Most of the rest of the proof, namely, the Steps 1-4 below, thus focus on upper bounding the λ t , while Step 5 will collect all bounds together and conclude.

Step 1: Gradient-descent analysis. We introduce

∆ c τ = c lcb δ/4,τ -1 (x τ , a τ ) -(B -b1) (10)
and prove the following deterministic inequality: for all 1 t T ,

∀ λ 0, λ t -λ 2 λ 2 + 4d γ 2 t + 2γ t τ =1 ∆ c τ , λ τ -1 -λ . ( 11
)
To do so, we proceed as is classical in (projected) gradient-descent analyses; see, e.g., [START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF]. Namely, for all 1 τ T ,

2 -∆ c τ , λ τ -1 -λ = 1 γ λ τ -1 -λ 2 + γ∆ c τ 2 -λ τ -1 -λ + γ∆ c τ 2 = γ ∆ c τ 2 + 1 γ λ τ -1 -λ 2 -λ τ -1 + γ∆ c τ -λ 2 γ ∆ c τ 2 + 1 γ λ τ -1 -λ 2 -λ τ -λ 2 ,
where the inequality comes from the definition λ τ = λ τ -1 + γ∆ c τ + and the fact that

∀ x ∈ R, ∀ y 0, (x) + -y |x -y|
(which may be proved by distinguishing the cases x 0 and x 0).

We note that

B -b1 ∈ [0, 1] d and c lcb δ/4,τ -1 (x τ , a τ ) ∈ [-1, 1] d , so that ∆ c τ 2 4d .
Collecting all bounds above, we get, after summation and telescoping,

t τ =1 -∆ c τ , λ τ -1 -λ 2d γt + 1 2γ λ 0 -λ 2 -λ t -λ 2 .
Rearranging and substituting λ 0 = 0 yields the claimed inequality (11).

Step 2: Relating estimated costs (and rewards) to true conditional expectations. In this part, we upper bound the right-hand side of (11) by showing that on the event E β ,

∀ λ 0, ∀ 1 t T, t τ =1 ∆ c τ , λ τ -1 -λ 2 1 + λ 1 β t,δ/4 + t τ =1 g τ (λ) -g τ (λ τ -1 ) , (12)
where

g τ (λ) = max a∈A r(x τ , a) -c(x τ , a) -(B -b1), λ
and where we recall that • 1 denotes the 1 -norm.

Adding and subtracting r ucb δ/4,τ -1 (x τ , a τ ), here, we deal with

t τ =1 ∆ c τ , λ τ -1 -λ = t τ =1 r ucb δ/4,τ -1 (x τ , a τ ) -c lcb δ/4,τ -1 (x τ , a τ ) -(B -b1), λ - t τ =1 r ucb δ/4,τ -1 (x τ , a τ ) -c lcb δ/4,τ -1 (x τ , a τ ) -(B -b1), λ τ -1 .
Now, for each τ , by (3) and the fact that λ 0,

r ucb δ/4,τ -1 (x τ , a τ ) -c lcb δ/4,τ -1 (x τ , a τ ) -(B -b1), λ r(x τ , a τ ) + 2ε τ -1 (x τ , a τ , δ/4) -c(x τ , a τ ) -(B -b1), λ + 2ε τ -1 (x τ , a τ , δ/4) λ 1 g τ (λ) + 2 1 + λ 1 ε τ -1 (x τ , a τ , δ/4) .
On the other hand, by definition of a τ for the equality, and then by the other inequalities in (3), for each τ , and the fact that λ τ -1 0,

r ucb δ/4,τ -1 (x τ , a τ ) -c lcb δ/4,τ -1 (x τ , a τ ) -(B -b1), λ τ -1 (13) = max a∈A r ucb δ/4,τ -1 (x τ , a) -c lcb δ/4,τ -1 (x τ , a) -(B -b1), λ τ -1 max a∈A r(x τ , a) -c(x τ , a) -(B -b1), λ τ -1 = g τ (λ τ -1 ) .
Collecting the two series of bounds concludes this part.

Step 3: Application of a Bernstein-Freedman inequality. We recall that we denoted by λ B-b1 the optimal dual variable in (4) for OPT(r, c, B -b1); it exists because we assumed feasibility of a problem with average cost constraints B < B -b1.

We now upper bound the sum appearing in the right hand side of ( 12) at λ = λ B-b1 by showing that on an event E Bern-c of probability at least 1 -δ/4, for all 1 t T ,

t τ =1 g τ (λ B-b1 ) -g τ (λ τ -1 ) (1 + 2Λ t ) 2t ln T 2 δ/4 + 2K t ln T 2 δ/4 , (14)
where

Λ t = max 1 τ t λ B-b1 -λ τ -1 1 and K t = 4 1 + λ B-b1 1 + 2dγt .
We will do so by applying a version of the Bernstein-Freedman inequality for martingales stated in Cesa-Bianchi et al. [2005, Corollary 16] involving the sum of the conditional variances (and not only a deterministic bound thereon); it is obtained via peeling based on the classic version of Bernstein's inequality [START_REF] David A Freedman | On tail probabilities for martingales[END_REF]. We restate it here for the convenience of the reader (after applying some simple boundings).

Lemma 4 (a version of the Bernstein-Freedman inequality by [START_REF] Cesa-Bianchi | Minimizing regret with label-efficient prediction[END_REF]. Let X 1 , X 2 , . . . be a martingale difference with respect to the filtration F = (F s ) s 0 and with increments bounded in absolute values by K. For all t 1, let

S t = t τ =1 E X 2 τ F τ -1
denote the sum of the conditional variances of the first t increments. Then, for all δ ∈ (0, 1) and all t 1, with probability at least 1 -δ,

t τ =1 X τ 2S t ln t δ + 2K ln t δ .
We introduce, for all λ 0, the common expectation of the g τ (λ), namely,

G(λ) = E g τ (λ) = E X∼ν max a∈A r(X, a) -c(X, a) -(B -b1), λ ,
and consider the martingale increments

X τ = g τ (λ B-b1 ) -g τ (λ τ -1 ) -G(λ B-b1 ) -G(λ τ -1 ) .
As B -b1 ∈ [0, 1] d and c takes values in [-1, 1] d , for all x ∈ X , all a ∈ A, and all v ∈ R d , the quantities r(x, a) -c(x, a) -(B -b1), v take absolute values smaller than 1 + 2 v 1 . Using that a difference of maxima is smaller than the maximum of the differences, we get, in particular,

g τ (λ B-b1 ) -g τ (λ τ -1 ) 1 + 2 λ B-b1 -λ τ -1 1 a.s. ( 15
)
and

G(λ B-b1 ) -G(λ τ -1 ) 1 + 2 λ B-b1 -λ τ -1 1 .
Now, given the update step in Step 3 of Box B, we have the deterministic bound λ t 1 2dγt for all 1 t T . Therefore, by a triangle inequality, the martingale increments are bounded in absolute values by K t , as

2 1 + 2 λ B-b1 1 + 1 + 2 max τ t λ τ -1 1 4 1 + λ B-b1 1 + 2dγt = K t .
The conditional variance of X τ is smaller than the squared half-width of the conditional range (Popoviciu's inequality on variances); in particular, (15) thus entails

S t t τ =1 1 + 2 λ B-b1 -λ τ -1 1 2 (1 + 2Λ t ) 2 t .
We now get the claimed inequalities ( 14) first by noting that by ( 4), for all τ T ,

G(λ B-b1 ) -G(λ τ -1 ) 0 ,
and second, by applying Lemma 4 for each 1 t T , using a confidence level δ/(4T ). By a union bound, this indeed defines an event E Bern-c of probability at least 1 -δ/4.

Step 4: Induction to bound the Λ t . In this step, we show by induction that, with high probability, the norms λ B-b1 -λ t satisfy the bound (18) stated below.

To do so, we combine the outcomes of Steps 1-3 and obtain that on the event

E β ∩ E Bern-c , for all 1 t T , λ B-b1 -λ t 2 λ B-b1 2 + 4d γ 2 t + 2γ 2 1 + λ B-b1 1 β t,δ/4 + t τ =1 g τ (λ B-b1 ) -g τ (λ τ -1 ) λ B-b1 2 + 4d γ 2 t + 4γ 1 + λ B-b1 1 β t,δ/4 + 2γ(1 + 2Λ t ) 2t ln T 2 δ/4 + 4γK t ln T 2 δ/4 ,
where we recall that norms not indexed by a subscript are Euclidean norms, and

Λ t = max 1 τ t λ B-b1 -λ τ -1 1 and K t = 4 1 + λ B-b1 1 + 2dγt .
We upper bound λ B-b1 1 and Λ t in terms of Euclidean norms,

λ B-b1 1 √ d λ B-b1 and Λ t √ d max 1 τ t λ B-b1 -λ τ -1 ,
perform some crude boundings like √ t √ T and β t,δ/4 β T,δ/4 , and obtain the following induction relationship: on the event E β ∩ E Bern-c , for all 1 t T ,

λ B-b1 -λ t 2 A + B t + C max 1 τ t λ B-b1 -λ τ -1 , (16)
where

A = λ B-b1 2 + γ 4 1 + √ d λ B-b1 β T,δ/4 + 2 2T ln T 2 δ/4 + 16 1 + √ d λ B-b1 ln T 2 δ/4 , B = 4dγ 2 + 4 × 4 × 2dγ 2 ln T 2 δ/4 = 4 + 32 ln T 2 δ/4 dγ 2 36 dγ 2 ln T 2 δ/4 , C = 4γ 2dT ln T 2 δ/4 .
We now show that ( 16) implies that on

E β ∩ E Bern-c , ∀ 0 t T, λ B-b1 -λ t M def = C 2 + A + BT + C 2 4 . (17)
Indeed, for t = 0, given that λ 0 = 0, we have λ B-b1 -λ t = λ B-b1 √ A. Now, if the bound ( 17) is satisfied for all 0 τ t, where 0 t T -1, then (16) implies that

λ B-b1 -λ t+1 A + B (t + 1) + CM A + B T + CM M 2 ,
where the final inequality follows from the fact that (by definition of M , and this explains how we picked M )

M 2 -CM = M - C 2 2 + C 2 4 = A + BT .
Below, we will make repeated uses of √ x + y √ x + √ y, of xy 2(x 2 + y 2 ), and of √ x 1 + x, for x, y 0. From ( 17), we conclude that on the event

E β ∩ E Bern-c , ∀ 0 t T, λ B-b1 -λ t √ A + √ BT + C = √ A + 6γ dT ln T 2 δ/4 + 4γ 2dT ln T 2 δ/4 √ A + 6γβ T,δ/4 ,
where we denoted

β T,δ/4 = max β T,δ/4 , 2 dT ln T 2 δ/4 ln T 2 δ/4 .
For the sake of readability, we may further bound √ A as follows (in some crude way):

√ A λ B-b1 + √ γ 4 1 + √ d λ B-b1 β T,δ/4 + 2 2T ln T 2 δ/4 + 16 1 + √ d λ B-b1 ln T 2 δ/4 λ B-b1 + √ γ 22β T,δ/4 + 20 √ d λ B-b1 β T,δ/4 λ B-b1 + 1 + 6γβ T,δ/4 + λ B-b1 + 5γ √ d β T,δ/4 ,
where we used the facts that √ 20xy = 2 √ 5xy x + 5y and

√ 22x = 2 22x/4 1 + 6x.
All in all, we proved that on the event

E β ∩ E Bern-c , ∀ 0 t T, λ B-b1 -λ t 2 λ B-b1 + 17γ √ d β T,δ/4 + 1 . (18)
Step 5: Conclusion. We combine the bound (18) with the bound (9) of Step 1 and the bound (7): on the intersection of events E β ∩ E Bern-c ∩ E H-Az , which has a probability at least 1 -3δ/4, for all 1 t T ,

t τ =1 c τ -t(B -b1) + √ d α T,δ/4 + 2β T,δ/4 + λ t γ √ d α T,δ/4 + 2β T,δ/4 + λ B-b1 γ + λ B-b1 -λ t γ 3 λ B-b1 + 1 γ + √ d α T,δ/4 + 19β T,δ/4 .
This entails in particular the stated result, given the definition of Υ T,δ as max β T,δ/4 , α T,δ/4 .

B.2 Proof of Lemma 2

The proof is similar to (but much simpler and shorter than) the one of Lemma 1 and borrows some of its arguments. We use throughout this section the notation introduced therein; we also define a new event E Bern-r of probability at least 1 -δ/4.

We start from (8) and introduce the same ∆ c t quantity as in ( 10): on the event E H-Az ∩ E β , for all

1 t T , t τ =1 r τ -α t,δ/4 + 2β t,δ/4 + t τ =1 r ucb δ/4,τ -1 (x τ , a τ ) -α t,δ/4 + 2β t,δ/4 + t τ =1 r ucb δ/4,τ -1 (x τ , a τ ) -∆ c τ , λ τ -1 + t τ =1 ∆ c τ , λ τ -1 .
On the one hand, the result (11) with λ = 0 exactly states that

t τ =1 ∆ c τ , λ τ -1 λ t 2 2γ -2d γt -2d γt .
On the other hand, the result (13) states that on E β , for all 1 τ T ,

r ucb δ/4,τ -1 (x τ , a τ ) -∆ c τ , λ τ -1 = r ucb δ/4,τ -1 (x τ , a τ ) -c lcb δ/4,τ -1 (x τ , a τ ) -(B -b1), λ τ -1 g τ (λ τ -1 ) .
A similar application of Lemma 4 as in the proof of Lemma 1 shows that on a new event E Bern-r of probability at least 1 -δ/4, for all 1 t T ,

t τ =1 g τ (λ τ -1 ) t τ =1 G(λ τ -1 ) -2 t τ =1 1 + 2 λ τ -1 1 2 ln T 2 δ/4 -8(1 + 2γt) ln T 2 δ/4 .
We relate 1 -norms to Euclidean norms, resort to a triangle inequality, and substitute (18) to get that on E Bern-c , for all 1 t T ,

-2 t τ =1 1 + 2 λ τ -1 1 2 ln T 2 δ/4 -1 + 2 √ d max 0 τ t-1 λ τ -1 2t ln T 2 δ/4 -1 + 2 √ d λ B-b1 + 2 √ d max 0 τ t-1 λ B-b1 -λ τ -1 2t ln T 2 δ/4 -8 √ d λ B-b1 + 34γd β T,δ/4 + 2 √ d + 1 2t ln T 2 δ/4 -8 √ d λ B-b1 + 34γd β T,δ/4 + 4 √ d 2t ln T 2 δ/4 -6 λ B-b1 β T,δ/4 -25γ √ d β T,δ/4 2 -2 √ 2 β T,δ/4 -6 λ B-b1 β T,δ/4 -28γ √ d β T,δ/4 2 ,
where we performed some crude boundings using the definition of 1 β t,δ/4 β T,δ/4 . We also note that

8(1 + 2γt) ln T 2 δ/4 8 ln T 2 δ/4 + 4γ β T,δ/4 2 .
By (4), we have OPT(r, c, B -b1) = G(λ B-b1 ) G(λ), for all λ 0. Also,

G(λ B-b1 ) + b λ B-b1 1 = E X∼ν max a∈A r(X, a) -c(X, a) -(B -b1), λ B-b1 + b λ B-b1 1 = E X∼ν max a∈A r(X, a) -c(X, a) -B, λ B-b1 OPT(r, c, B) ,
where we used again (4). In particular,

t τ =1 G(λ τ -1 ) t OPT(r, c, B) -t b λ B-b1 1 t OPT(r, c, B) -t b √ d λ B-b1 1 .
Collecting all bounds above and using the definition of Υ T,δ as max β T,δ/4 , α T,δ/4 and the fact that dt (Υ T,δ ) 2 , we proved the following. On E H-Az ∩ E β ∩ E Bern-c ∩ E Bern-r , which is indeed an event with probability at least 1 -δ, for all 1 t T ,

t τ =1 r τ -3Υ T,δ -2d γt + t τ =1 G(λ τ -1 ) -2 T t=1 1 + 2 λ t-1 1 2 ln T 2 δ/4 -8 ln T 2 δ/4 -4γ β T,δ/4 2 t OPT(r, c, B) -λ B-b1 t b √ d + 6Υ T,δ -36γ √ d Υ T,δ 2 -8 ln T 2 δ/4 .
Algorithm 1: Pseudo-code for the Box C strategy Input: number of rounds T ; confidence level 1 -δ; margin b on the average constraints; estimation procedure and error functions ε t of Assumption 2; optimistic estimates (2)

Initialization: T 0 = 1; sequence γ k = 2 k / √ T of step sizes; sequence M T,δ,k = 4 √ T + 20 √ d Υ T,δ/(k+2) 2 of cost deviations 1 for k 0 do // Box C part 2 λ T k -1 = 0; 3 for t T k do // Box B

C Proof of Theorem 1

The proof is divided into three steps: on a favorable event E meta of probability at least 1 -δ, (i) we bound by ilog T the index of the last regime achieved in Box C; (ii) we bound by (1 + ilog T )

√

T the excess cumulative costs with respect to T (B -b T 1) and deduce that the cumulative costs are smaller than B; (iii) we provide a regret bound, by summing the bounds guaranteed by Lemma 1 over each regime.

The favorable event E meta is defined as follows. By construction, and thanks to the assumption of feasibility for B -2b T 1, the results of Lemmas 1 and 2 hold with probability at least 1 -δ/(k + 2) 2 at each round of each regime k 0 that is actually achieved. Given that

k 0 1 (k + 2) 2 k 0 1 (k + 1)(k + 2) = 1 ,
we may define E meta as the event indicating that the (uniform-in-time) bounds of Lemmas 1 and 2 are satisfied within each of the regimes achieved.

C.1 Step 1: Bounding the number of regimes achieved

We show that, on E meta , if regime K = ilog λ B-b T 1 is achieved, then this regime does not stop. Hence, on E meta , at most K + 1 1 + ilog λ B-b T 1 regimes take place.

Indeed, in regime K = ilog λ B-b T 1 , if it is achieved, the meta-strategy resorts to the Box B strategy with

γ K = 2 K √ T max λ B-b T 1 , 1 √ T .
Therefore, the bound of Lemma 1 entails that on E meta , for all t T K ,

t τ =T K c τ -(t -T k + 1) (B -b T 1) + 1 + 3 λ B-b T 1 γ K + 20 √ d Υ T,δ/(K+2) 2 4 √ T + 20 √ d Υ T,δ/(K+2) 2 = M T,δ,K
. 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 λ B-b T 1 by ilog T : this holds because the assumption of (B -2b T 1)-feasibility entails, by Lemma 3 and as OPT is always smaller than 1, the crude bound

λ B-b T 1 OPT(r, c, B -b T 1) -OPT r, c, B -(3/2)b T 1 b T /2 2 b T √ T 7 T ,
where we used that b T 14/ √ T 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-b T 1 ilog(T ), and that for k 0, regime k starts at T k and stops at T k+1 -1. By convention, T 0 = 1 and T K+1 = T +1.

By the very definition of the stopping condition of regime

k 0,   T k+1 -2 t=T k c t -(T k+1 -T k -1) (B -b T 1)   + M T,δ,k .
For rounds of the form t = T k+1 -1, we bound the Euclidean norm of c t -(B -b T 1) by 2 √ d. Therefore, by a triangle inequality, satisfied both by the non-negative part ( • ) + and the norm • functions, we have

T t=1 c t -T (B -b T 1) + K k=0   T k+1 -2 t=T k c t -(T k+1 -T k -1) (B -b T 1)   + + K k=0 c T k+1 -1 -(B -b T 1) (K + 1) M T,δ,ilog T + 2 √ d T b
T , where we used the fact that M T,δ,k increases with k, the bound K ilog T proved in Step 1 and holding on the event E meta , as well as the definition of b T . Therefore, on E meta , no component of

C.3 Step 3: Computing the associated regret bound

The total regret is the sum of the regrets suffered over each regime:

R T = K k=0   (T k+1 -T k )OPT(r, c, B) - T k+1 -1 t=T k r t   .
On the favorable event E meta , the bound of Lemma 2 holds in particular at the end of each regime; i.e., given the parameters γ k = 2 k / √ T and δ/ 4(k + 2) 2 to run the Box B strategy in regime k ∈ {0, . . . , K}, it holds on E meta that

(T k+1 -T k ) OPT(r, c, B) - T k+1 -1 t=T k r t λ B-b T 1 (T k+1 -T k ) b T √ d + 6Υ T,δ/(k+2) 2 + 36 √ d Υ T,δ/(k+2) 2 2 2 k √ T + 8 ln T 2 δ/ 4(k + 2) 2 .
We now sum the above bounds and use the (in)equalities Υ T,δ/(k+2

) 2 Υ T,δ/(K+2) 2 , K k=0 (T k+1 -T k ) b T = T b T ,
and

K k=0 2 k 2 K+1 2 1+ilog λ B-b T 1 4 λ B-b T 1 to get R T λ B-b T 1 T b T √ d + 6KΥ T,δ/(K+2) 2 + 144 √ d λ B-b T 1 Υ T,δ/(K+2) 2 2 √ T + 8K ln T 2 δ/ 4(K + 2) 2 .
The final regret bound is achieved by substituting the inequality K ilog T proved in Step 1:

R T λ B-b T 1 144 √ d Υ T,δ/(2+ilog T ) 2 2 √ T + T b T √ d + 6Υ T,δ/(2+ilog T ) 2 ilog T + 8 ln T 2 δ/ 4(2 + ilog T ) 2 ilog T . (19)
The order of magnitude is

√

T , up to poly-logarithmic terms, for the quantity Υ T,δ/(2+ilog T ) 2 , thus for M T,δ,ilog T , thus for T b T , therefore, the order of magnitude in √ T of the above bound is, up to poly-logarithmic terms,

1 + λ B-b T 1 √ T , as claimed.

D Proofs of Lemma 3 and Corollary 1

Proof of Lemma 3. For λ 0 and C ∈ [0, 1] d , we denote

L(λ, C) = E X∼ν max a∈A r(X, a) -c(X, a) -C, λ
so that by (4) and the feasibility assumption, we have, at least for C = B and C = B -b1:

OPT(r, c, C) = min λ 0 L(λ, C) = L(λ C , C) . The function L is linear in C, so that OPT r, c, B = L λ B , B L λ B-b1 , B = L λ B-b1 , B -b1 -λ B-b1 , B -b1 -B = OPT r, c, B -b1 -λ B-b1 , B -b1 -B . The result follows from substituting λ B-b1 , B -b1 -B λ B-b1 1 min B -b1 -B λ B-b1 min B -b1 -B
and from rearranging the inequality thus obtained.

Proof of Corollary 1. We apply Lemma 3 with B = ε1 for some ε > 0 sufficiently small and obtain

λ B-b1 OPT(r, c, B -b1) -OPT r, c, ε1 min B -(b + ε)1 .
We conclude by substituting OPT(r, c, B -b1) OPT(r, c, B) and OPT r, c, ε1 OPT r, c, 0 as well as min(B -b1) min B/2, and by letting ε → 0.

E Additional (sketch of) results concerning optimality

We detail here two series of claims made in Section 4 .

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+ λ B √ T announced in Section 4.

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 T B. If we considered softer constraints, of the form T B + O √ T , then O √ T regret bounds would be possible (see Appendix F); i.e., the factor λ B-b T 1 of Theorem 1 could be replaced by a constant. Thus, lower bounds are only interesting in the case of hard constraints stated in Box A.

Step 1: Necessity of a margin b T of order 1/ √ T . First, a 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 π B a (quasi-)optimal policy for the average cost 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 π B at each round, the cumulative costs must (almost-surely, as T → +∞) be larger than T B plus a positive term of the order of

√

T ln ln T . Therefore, to meet the hard constraints, one should pick B of the form B -b T 1, where b T is of order 1/

√

T up to logarithmic terms.

Step 2: Consequences in terms of regret. Therefore, the largest average reward a strategy may target is OPT(r, c, B -b T 1). Deviations of the order √ T are also bound to happen. Therefore, up to logarithmic terms, the regret lower bound is approximatively larger than something of the order

T OPT(r, c, B) -OPT(r, c, B -b T 1) + √ T .
Now, an argument similar to the one used in the proof of Lemma 3 shows that

OPT(r, c, B) -OPT(r, c, B -b T 1) L(λ B , B) -L(λ B , B -b T 1) = b T λ B .
All in all, the regret lower bound is thus approximatively larger than something of the order of

1 + λ B √ T .
This matches the form of the bound of Theorem 1, but the dual vector λ B-b T 1 present in the upper bound is replaced by λ B in our lower bound.

E.2 Faster rates may be achievable in some specific cases

We explain here why, in some specific cases, faster rates would be achievable-with √ T in the regret bound of Theorem 1 replaced by

√

T B for a problem with scalar costs and total-cost constraints B.

Indeed, consider a problem similar to Example 1: with scalar costs, total-cost constraint B > 0, featuring a baseline action a null with null cost but also null reward, and additional actions with larger rewards and expected costs c(x, a) α > 0. Let N T denotes the number of times non-null cost actions are played within the first T rounds. Deviation inequalities have it that

T t=1 c t αN T -Õ N T ,
where we recall that Õ is up to poly-logarithmic factors; as a consequence, the total-cost constraint enforces that

N T T B α + Õ T B α .
In particular, the margin b T only needs to be of order √ N T /T , i.e., B/(αT ) , instead of 1/ √ T .

Similarly, since at most N T non-null actions are played, the regret should be lower bounded by something of the order of

T OPT(r, c, B) -OPT(r, c, B -b T ) + N T , where, as in Step 2 above, OPT(r, c, B) -OPT(r, c, B -b T ) b T |λ B | = Õ B αT |λ B |.
This suggests a lower bound on the regret of the order (up to poly-logarithmic factors) of

|λ B | + 1 T B/α instead of 1 + |λ B | √ T .
The difference between the two bounds is significant when B is small, i.e., B 1. While proving a matching upper bound with the Box B and Box C strategies looks a bit tricky, we feel that it must be possible to do so with the primal approach of Appendix F, at least when the context space X is finite. If our intuition holds, then it would be possible to get an upper bound

R T Õ T b T 1 + |λ * B-b T | = Õ T B α 1 + OPT(r, c, B) -OPT(r, c, 0) B = Õ T B/α 3 ,
where the last bound follows from OPT(r, c, B) -OPT(r, c, 0) B/α, as explained in Example 1.

F Primal strategy

This section studies the primal strategy stated in Box D, which, at every round, solves an approximation of the primal optimization problem (1). The key issue in running such a primal approach is estimating ν, see comments after Notation 1; 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.1, we provide a theory of "soft" constraints, when total-cost deviations from T B of order √ T up to logarithmic terms are allowed; at least when X is a finite set, the regret bound then becomes proportional to

√

T up to logarithmic terms. 2. In Appendix F.2, we revisit and extend the results by [START_REF] Li | Contextual bandits with knapsacks for a conversion model[END_REF]. The extension consists of dealing with possibly signed constraints, and the revisited analysis (of the same strategy as in [START_REF] Li | Contextual bandits with knapsacks for a conversion model[END_REF] consists in not directly dealing with KKT constraints (which, in addition, imposed the finiteness of X ) but in only relating optimization problemsdefined with the true r and c or estimates thereof. We also offer a modular approach and separate the error terms coming from estimating ν and from estimating r and c. 3. In Appendix F.3, 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 1 and the interpretation thereof offered by Lemma 3, at least in the case of a finite X . Actually, in our research path, we had first obtained these primal results, before trying to obtain them in a more general case of a continuous X , by resorting to a dual strategy. The proof technique in Appendix F.3 also inspired our approach to proving problem-dependent lower bounds presented in Appendix E.1.

Throughout this appendix, we will assume that the context distribution ν can be estimated in some way. We provide examples and pointers below. Notation 1. Fix δ ∈ (0, 1). We denote by ν δ,t a sequence of estimators of ν, each constructed on the contexts x 1 , . . . , x t , and by ξ t,δ a sequence of estimation errors such that, with probability at least 1 -δ, for all bounded functions f :

X → [-1, 1], E X∼ν f (X) -E X∼ ν δ,t f (X) ξ t,δ .
We also denote Ξ T,δ = T t=1 ξ t-1,δ .

We consider the strategy described in Box D, whether X is finite (as in [START_REF] Li | Contextual bandits with knapsacks for a conversion model[END_REF], 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 X∼ ν δ,t-1 a∈A c lcb δ,t-1 (X, a) π a (X) B + b t 1 .
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, as the problem then corresponds to a finite-dimensional linear program. In general, we may note that when (4) holds, we read therein the optimal policy, as a pointwise maximum involving the optimal dual variables. The proofs reveal that up to slightly augmenting the ξ t-1,δ of Notation 1, we may assume that the strict feasibility sufficient for (4) indeed holds.

We also note that even if the argument of the maximum π t is guaranteed to exist, it may be difficult to compute: the linear program of Box D cannot be solved exactly if the ν δ,t 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 is an ideal strategy anyway, that we study for the sake of shedding lights on our results for 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 to as signed slacks.

BOX D: PRIMAL CBWK STRATEGY, GENERALIZED FROM LI AND STOLTZ [2022]

Inputs: confidence level 1 -δ; estimation procedure and error functions ε t of Assumption 2; optimistic estimates (2); estimation procedure for ν as in Notation 1

Hyperparameter: signed slacks b 1 , b 2 , . . . , b T ∈ R
Initialization: initial estimates r ucb δ,0 (x, a) and c lcb δ,0 (x, a), as well as ν δ,0 For rounds t = 1, 2, 3, . . . , T :

1. Compute a policy π t achieving max π:X →P(A)

E X∼ ν δ,t a∈A r ucb δ,t-1 (X, a) π a (X) under E X∼ ν δ,t-1 a∈A c lcb δ,t-1 (X, a) π a (X) B + b t 1
when the empirical cost constraints are feasible, and pick an arbitrary policy π t otherwise; 2. Observe x t and draw an action a t ∼ π t (x t ); 3. Compute the estimate r ucb δ,t (x, a) and c lcb δ,t (x, a), as well as ν δ,t .

Discussion of the estimation of ν. The simplest case is when X is a finite set; in this case, we may take

ξ t,δ of order |X | ln(1/δ) t ,
where X denotes the cardinality of X ; see [Ai et al., 2022, Section 4.1], see also a less sharp bound based on Hoeffding's inequality in [Li and Stoltz, 2022, Section 5]. This leads to a total error term Ξ T,δ of order √ T up to poly-logarithmic term.

When X is a continuous subset of R n , some regularity conditions are put on ν, which is typically assumed to have some smooth density with respect to the Lebesgue measure m. Estimates ν δ,t are obtained by estimating the density dν/dm: the criterion in Notation 1, which is proportional to the total-variation distance between ν and ν δ,t , is then given by the L 1 (m) distance between the two densities. To control the latter with uniform convergence rates, so as to obtain deviation terms ξ t,δ only depending on t and δ, heavy assumptions on the model to which ν belongs are in 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/ √ t. The total error terms Ξ T,δ then prevent the bounds stated below in Proposition 1 and Theorems 3 and 4 from sharing the same orders of magnitude than the bounds proved with our dual approach in Theorem 1 and interpreted in Section 3.3. On this topic, see also [Ai et al., 2022, Section 4.1] for the estimation rates as well as a 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 [START_REF] Devroye | Nonparametric Density Estimation: The L 1 View[END_REF] in L 1 and [START_REF] Tsybakov | Introduction to Nonparametric Estimation[END_REF] in L 2 .

Note that in the dual approach, the knowledge of (the possibly complex) ν is replaced by the knowledge of the (finite-dimensional) optimal dual variables λ B ∈ R d , which is easier to learn. This explains the fundamental efficiency of the dual approach compared to the primal approach.

F.1 Analysis with "soft" constraints

We first provide an analysis for a version of the Box D strategy that may possibly breach the total-cost constraints T B. More precisely, we allow deviations to T B of the order of

√

T times poly-log factors: this is what we refer to as "soft" constraints. Our result is that the regret may then be bounded by a quantity of order

√

T 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 a 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 F.2).

Proposition 1 (soft constraints). Fix δ ∈ (0, 1). Under Assumption 2 and with Notation (1), the strategy of Box D, run with δ/4 and positive slacks b t = ξ t-1,δ/4 , ensures that with probability at least 1 -δ, In particular, when X is finite, the deviation terms 2α T,δ/4 + β T,δ/4 + 2Ξ T,δ/4 are of order √ T up to poly-logarithmic terms, so that the bound of Proposition 1 reads: with high-probability,

T t=1 c t T B + O √ T and R T O √ T .
Put differently, soft-constraint satisfaction allows for O √ T regret bounds when X is finite.

Proof. As in the proofs of Lemmas 1 and 2 in Appendix B, we consider four events, each of probability at least 1 -δ/4: two events E H-Az1 and E H-Az2 , defined below, following from applications of the Hoeffding-Azuma inequality, the favorable event E TVD of Notation 1 with δ/4, and the favorable event E β of Assumption 2 with δ/4. Namely, given the value for α

The first two inequalities are obtained by considering conditional expectations with respect to the past, x t and a t , while the second two inequalities follow from taking conditional expectations with respect to the past and x t ; we crucially use that, by definition, x t ∼ ν is independent from π t and the estimates r ucb δ/4,t-1 and c lcb δ/4,t-1 . We first note that by B-feasibility of the problem, by (3), and by Notation (1), a policy π t satisfying the constraints stated in Box D exists at each round t 1 on the event E β ∩ E TVD . Indeed, denoting by π feas such a B-feasible policy, this existence follows from the inequalities

E X∼ ν δ/4,t-1 a∈A c lcb δ/4,t-1 (X, a) π feas a (X) E X∼ ν δ/4,t-1 a∈A c(X, a) π feas a (X) ξ t-1,δ/4 + E X∼ν a∈A c(X, a) π feas a (X) B ( 22
)
and from the choice b t = ξ t-1,δ/4 .

Cost-wise, we then successively have, by (20), then (3) and Assumption 2, and finally (21) and Notation (1), on the event The control for rewards mimics the steps above for costs (and then resorts to an additional argument).

E H-Az1 ∩ E β ∩ E H-Az2 ∩ E TVD of probability at least 1 -δ, T t=1 c t α T,δ/4 1 + T t=1 c(x t , a t ) α T,δ/4 + β T,δ/4 1 + T t=1 c lcb δ/4,t-1 (x t , a t ) 2α T,δ/4 + β T,δ/4 1 + T t=1 E X∼ν a∈A c lcb δ/4,t-1 (X, a) π t,a (
We obtain first that on

E H-Az1 ∩ E β ∩ E H-Az2 ∩ E TVD , T t=1 r t -2α T,δ/4 + β T,δ/4 + Ξ T,δ/4 + T t=1 E X∼ ν δ/4,t-1 a∈A r ucb δ/4,t-1 (X, a) π t,a (X) .
We denote by π B an optimal static policy for the average cost constraints B-when it exists, e.g., by (4), as soon as the problem is feasible for some B < B; otherwise, we take a static policy achieving OPT(r, c, B) up to some small e > 0, which we let vanish in a final step of the proof. As in ( 22), we have, on E β ∩ E TVD ,

E X∼ ν δ/4,t-1 a∈A c lcb δ/4,t-1 (X, a) π B,a (X) E X∼ ν δ/4,t-1 a∈A c(X, a) π B,a (X) ξ t-1,δ/4 1 + E X∼ν a∈A c(X, a) π B,a (X) B ,
where the B inequality follows from the definition of π B . Thanks to the choice b t = ξ t-1,δ/4 , we have, by definition of π t as some optimal policy in Box D and on E β ∩ E TVD , E X∼ ν δ/4,t-1 a∈A r ucb δ/4,t-1 (X, a) π t,a (X) E X∼ ν δ/4,t-1 a∈A r ucb δ/4,t-1 (X, a) π B,a (X) .

Again by (3) and Notation (1), we have, on E β ∩ E TVD ,

E X∼ ν δ/4,t-1 a∈A r ucb δ/4,t-1 (X, a) π B,a (X) E X∼ ν δ/4,t-1 a∈A r(X, a) π B,a (X) -ξ t-1,δ/4 + E X∼ν a∈A r(X, a) π B,a (X) =OPT(r,c,B)
.

Collecting all bounds, we proved that on

E H-Az1 ∩ E β ∩ E H-Az2 ∩ E TVD , T t=1 r t T OPT(r, c, B) -2α T,δ/4 + β T,δ/4 + 2Ξ T,δ/4 ,
which corresponds to the claimed regret bound.

F.2 Analysis with "hard" constraints and a 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-which we refer to as "hard" constraints. For the sake of simplicity, we do so for now in the presence of a null-cost action; Appendix F.3 explains how the analysis may be generalized to cases without such null-cost actions.

The following result corresponds to the combination of Theorem 1 with Corollary 1, and also, to Li and Stoltz [2022, main result Proof. We explain how the proof of Proposition 1 may be adapted. We first justify the existence at each round t 1 of a policy π t satisfying the cost constraints stated in Box D: for the null-cost action a null , we may impose that, for all x ∈ X , all t 0, and all δ ∈ (0, 1), c t (x, a null ) = 0 and ε t (x, a null , δ) = 0 , so that c lcb δ,t (x, a null ) = 0 a.s.; this shows that at least the static policy π null always playing a null satisfying the defining cost-constraints for π t . (Alternatively, we may note that the policy π t defined below also satisfies the cost constraints stated in Box D, on the high-probability event considered.)

We then handle total-cost constraints similarly as in the proof of Proposition 1 and obtain that on the event

E H-Az1 ∩ E β ∩ E H-Az2 ∩ E TVD of probability at least 1 -δ, T t=1 c t 2α T,δ/4 + β T,δ/4 + Ξ T,δ/4 1 + T t=1 E X∼ ν δ/4,t-1 a∈A c lcb δ/4,t-1 (X, a) π t,a (X) B-∆ T ,δ/4 1 T B ,
where this time, the slacks b t = -∆ T,δ/4 are negative and were set to cancel out the positive deviation terms. Similarly, on

E H-Az1 ∩ E β ∩ E H-Az2 ∩ E TVD , T t=1 r t -T ∆ T,δ/4 + T t=1 E X∼ ν δ/4,t-1 a∈A r ucb δ/4,t-1 (X, a) π t,a (X) . (23)
Now, the main modification to the proof of Proposition 1 is that (with its notation) we rather consider the policy

π t = (1 -w t )π B + w t π null , where w t = min ∆ T,δ/4 + ξ t-1,δ/4 min B , 1 .
As in ( 22), we see that this policy satisfies, on E β ∩ E TVD :

E X∼ ν δ/4,t-1 a∈A c lcb δ/4,t-1 (X, a) π t,a (X) E X∼ ν δ/4,t-1 a∈A c(X, a) π t,a (X) ξ t-1,δ/4 1 + E X∼ν a∈A c(X, a) π t,a (X)
(1-wt)B

.

By using B (min B)1 and since we assumed that ∆ T,δ/4 < min B, we may continue the series of inequalities as follows:

ξ t-1,δ/4 1 + (1 -w t )B B + ξ t-1,δ/4 1 -w t (min B)1 = B -min ∆ T,δ/4 , min B -ξ t-1,δ/4 1 B -min ∆ T,δ/4 , ∆ T,δ/4 -ξ t-1,δ/4 1 = B + b t 1 ,
meaning that π t is a policy satisfying the constraints stated in Step 2 of Box D on round t 1. The consequence is that, first by definition of π t as a maximizer and then by the optimistic estimates (3) and Notation (1), on E β ∩ E TVD ,

E X∼ ν δ/4,t-1 a∈A r ucb δ/4,t-1 (X, a) π t,a (X) E X∼ ν δ/4,t-1 a∈A r ucb δ/4,t-1 (X, a) π t,a (X) -ξ t-1,δ/4 + E X∼ν a∈A r(X, a) π t,a (X) = -ξ t-1,δ/4 + (1 -w t )OPT(r, c, B) + w t OPT(r, c, 0) = OPT(r, c, B) -ξ t-1,δ/4 -min ∆ T,δ/4 + ξ t-1,δ/4 min B , 1 OPT(r, c, B) -OPT(r, c, 0) ,
where OPT(r, c, 0) refers to the expect reward achieved by the null-cost action a null . After combination with (23) and summation, we get that on E

H-Az1 ∩ E β ∩ E H-Az2 ∩ E TVD : T t=1 r t -T OPT(r, c, B) -T ∆ T,δ/4 -Ξ T,δ/4 - T t=1 min ∆ T,δ/4 + ξ t-1,δ/4 min B , 1 OPT(r, c, B) -OPT(r, c, 0) -T ∆ T,δ/4 + Ξ T,δ/4 1 + OPT(r, c, B) -OPT(r, c, 0) min B ,
which corresponds to the stated regret bound.

F.3 General analysis with "hard" constraints

We finally generalize Theorem 3 and get a result corresponding to Theorem 1 combined with Lemma 3.

Here, we "mix" the slacks +ξ t-1,δ/4 and -∆ T,δ/4 of Appendices F.1 and F.2, with a slight modification of ∆ T,δ/4 to compensate for the ξ t-1,δ/4 : we rather have a 2Ξ T,δ/4 term in the numerator of ∆ T,δ/4 , compared to the Ξ T,δ/4 term in the numerator of ∆ T,δ/4 . Theorem 4 (hard constraints). Fix δ ∈ (0, 1). We consider the strategy of Box D, run with δ/4 and signed slacks (depending on t 1) b t = -∆ T,δ/4 + ξ t-1,δ/4 where ∆ T,δ/4 = 2α T,δ/4 + β T,δ/4 + 2Ξ T,δ/4 T and α T,δ/4 = 2T ln (d + 1)/(δ/4) . Assume that the problem is (B -m)-feasible for some m that does not need to be known by the strategy, with Bm B -∆ T,δ/4 1. Then, under Assumption 2 and with Notation (1), with probability at least 1 -δ, Proof. We rather sketch the differences to the proofs of Theorem 3 and Proposition 1. We denote by E all the event of probability at least 1 -δ obtained as the intersection of four convenient events of probability each at least 1 -δ/4. All inequalities below hold on E all but for the sake of brevity, we will not highlight this fact each time.

We denote by π feas a (quasi-)optimal static policy among the ones achieving expected costs smaller than Bm; it therefore ensures that its expected costs are smaller than Bm and achieves an expected reward of OPT(r, c, Bm) -e, possibly up to a small factor e 0 which we let vanish. We note that for each round t 1,

E X∼ ν δ,t-1 a∈A c lcb δ,t-1 (X, a) π feas a (X) ξ t-1,δ/T 1 + E X∼ν a∈A c(X, a) π feas a (X) ξ t-1,δ/T 1 + B -m1 B + b t 1 ,
given the definition b t = -∆ T,δ/4 + ξ t-1,δ/4 and the assumption Bm B -∆ T,δ/4 1. Thus, on E all , the strategy π t is indeed defined at each round t 1 by the optimization problem stated in

Step 2 of Box D (and not in an arbitrary manner).

Cost-wise, we thus have

T t=1 c t 2α T,δ/4 + β T,δ/4 + Ξ T,δ/4 1 + T t=1 B+bt1 E X∼ ν δ/4,t-1 a∈A c lcb δ/4,t-1 (X, a) π t,a (X) T B + 2α T,δ/4 + β T,δ/4 + Ξ T,δ/4 1 -T ∆ T,δ/4 + Ξ T,δ/4 = T B ,
where the final equality follows from the definition of ∆ T,δ/4 , which involves a 2Ξ T,δ/4 term in its numerator.

Reward-wise, we introduce for each t 1,

π t = (1 -w t )π B + w t π feas , where w t = min ∆ T,δ/4 min m , 1 ,
whose empirical expected cost at round t 1 is smaller than

E X∼ ν δ/4,t-1 a∈A c lcb δ/4,t-1 (X, a) π t,a (X) ξ t-1,δ/4 1 + E X∼ν a∈A c(X, a) π t,a (X) ξ t-1,δ/4 1 + (1 -w t )B + w t (B -m) = B + ξ t-1,δ/4 1 -w t m .
By using m (min m)1 and thanks to the assumption Bm B -∆ T,δ/4 1, which can be equivalently formulated as min m ∆ T,δ/4 , we may continue this series of inequalities by

B + ξ t-1,δ/4 1 -w t m B -min ∆ T,δ/4 -ξ t-1,δ/4 , min m -ξ t-1,δ/4 1 B -min ∆ T,δ/4 -ξ t-1,δ/4 , ∆ T,δ/4 -ξ t-1,δ/4 1 = B + b t 1 ,
meaning that π t is a policy satisfying the constraints stated in Step 2 of Box D on round t 1. In particular, by definition of π t as a maximizer,

E X∼ ν δ/4,t-1 a∈A r ucb δ/4,t-1 (X, a) π t,a (X) E X∼ ν δ/4,t-1 a∈A r ucb δ/4,t-1 (X, a) π t,a (X) -ξ t-1,δ/4 + E X∼ν a∈A r(X, a) π t,a (X) -ξ t-1,δ/4 + (1 -w t )OPT(r, c B) + w t OPT(r, c B -m) = OPT(r, c B) -min ∆ T,δ/4 min m , 1 OPT(r, c B) -OPT(r, c B -m) -ξ t-1,δ/4 . (24)
Finally, by combining ( 23) and ( 24),

T t=1 r t - =T ∆ T ,δ/4 -Ξ T ,δ/4 2α T,δ/4 + β T,δ/4 + Ξ T,δ/4 1 + T t=1 E X∼ ν δ/4,t-1 a∈A r ucb δ/4,t-1 (X, a) π t,a (

G Numerical experiments: full description

This appendix reports numerical simulations performed on simulated data with the motivating example described in [START_REF] Chohlas-Wood | Learning to be fair: A consequentialist approach to equitable decision-making[END_REF] and alluded at in Section 2.1. These simulations are for the sake of illustration only.

A brief summary of the applicative background in AI for justice is the following. The learner wants to maximize the total number of appearances to 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 of help). There are of course budget limits on these assistance means, and the learner also wants to control how (un)fair the assistance policy is, in terms of subgroups of the population, while maximizing the total number of appearances. Some subgroups take a better advantage of assistance to appear in court, thus, without the fairness control, all assistance would go to these groups. The fairness costs described in Section 2.1 force the learner to perform some tradeoff between spending all assistance on 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]in particular, how contexts, rewards, and costs are generated in 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.

where

ϕ(x, a) =      x age x prox 1 {a=a voucher } x prox 1 {a=a voucher } 1 {gr(x)=0} x pov 1 {a=a ride } x pov 1 {a=a ride } 1 {gr(x)=0}      and µ =      -1 1 1 2 2     
.

The learner ignores the coefficients µ of this structure and only knows that expected rewards are of the form Φ ϕ(x, a) T θ for some parameter θ ∈ R 5 . The learner will estimate the reward function r by estimating µ .

Reward estimation. We deal with a logistic model and follow the methodology described in [START_REF] Li | Contextual bandits with knapsacks for a conversion model[END_REF]; see Modeling 2 in Section 2.2. In particular, the parameters µ are estimated, after each round t 1, thanks to the maximum likelihood estimator µ t ∈ arg max µ∈R 5 t s=1 r s Φ ϕ(a s , x s ) T µ + (1 -r s ) ln 1 -Φ ϕ(a s , x s ) T µ -

λ logistic 2 µ 2 ,
where λ logistic 0 is a regularization factor. We define as r t (x, a) = Φ ϕ(x, a) T µ t the estimated expected rewards, and the associated uniform estimation errors (see Assumption 2) are of the form ε t (x, a, δ) = C δ 1 + ln t ϕ(a, x) T V -1 t ϕ(a, x) where V t = t s=1 ϕ(a s , x s ) ϕ(a s , x s ) T + λ logistic I 5 , where I 5 is the 5 × 5 identity matrix.

In our simulations, we tested a range of values and picked (in hindsight) the well-performing values C δ = 0.025 and λ 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, τ, τ, τ, τ ) , where τ ∈ {10 -7 , 0.025} , but take a margin b = 0.005 and use B = B -(b, b, 0, 0, 0, 0) instead. This is a 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 to report the level of violation on 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 ) is another benchmark, see 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 ν, we compute 100 estimates For each j, we sample S = 10,000 contexts from the distribution ν, and denote by ν Mixed policy knowing λ B but estimating r. For the sake of illustration, we report the performance of a policy that would have oracle knowledge of λ B , which is a finite-dimensional parameter that summarizes ν, but would ignore r, i.e., the underlying logistic model. That is, this mixed policy would pick, at each round, max a∈A r ucb δ,t-1 (x t , a) -c lcb δ,t-1 (x t , a) -B , λ B , (and would omit the λ update in Box B).

To compute (an approximation of) λ B , we proceed 100 times as described below to compute estimates Finally, we note that in our experiments, the regimes in PGD Adaptive strategy typically covered range from k = 0 (corresponding to γ 0 = 1/ √ T = 0.01) to k = 2 (corresponding to γ 2 = 2 2 / √ T = 0.04). The PGD Adaptive strategy performs well and is (only) outperformed by the PDG strategy with a fixed γ = 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, we provide details on the computation time and environment. Our experiments were ran on the following hardware environment: no GPU was required, CPU is 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 on each algorithm for a single run was inferior to 10 minutes.

A

  Proof of the strong duality (4)

  T (B -b T 1) + can be larger than T b T , which yields the desired control T t=1 c t T B.

  B + 2α T,δ/4 + β T,δ/4 + 2Ξ T,δ/4 1 and R T 2α T,δ/4 + β T,δ/4 + 2Ξ T,δ/4 ,where α T,δ/4 = 2T ln (d + 1)/(δ/4) .

E

  X) 2α T,δ/4 + β T,δ/4 + Ξ T,δ/4 1 + T t=1 X∼ ν δ/4,t-1 a∈A c lcb δ/4,t-1 (X, a) π t,a (X) B+bt1 , where the inequalities B + b t 1 follow from the definition of π t in Box D. Substituting the choice b t = ξ t-1,δ/4 , we thus proved that on E H-Az1 ∩ E β ∩ E H-Az2 ∩ E TVD , T t=1 c t T B + 2α T,δ/4 + β T,δ/4 + 2Ξ T,δ/4 1 , as claimed.

:

  Theorem 2]. Theorem 3 (hard constraints). Fix δ ∈ (0, 1). We consider the strategy of Box D, run with δ/4 and negative slacks all equal to b t ≡ -∆ T,δ/4 , where ∆ T,δ/4 def = 2α T,δ/4 + β T,δ/4 + Ξ T,δ/4 T and α T,δ/4 = 2T ln (d + 1)/(δ/4) . Assume that a null-cost action exists, that ∆ T,δ/4 < min B, that Assumption 2 holds, and use Notation (1). Then, with probability at least 1 -δ, T t=1 c t T B and R T 2α T,δ/4 + β T,δ/4 + 2Ξ T,δ/4 1 + OPT(r, c, B) -OPT(r, c, 0) min B .

  δ/4 + β T,δ/4 + 2Ξ T,δ/4 1 + OPT(r, c, B) -OPT(r, c, Bm) min m .

  X) T OPT(r, c B) + Ξ T,δ/4 -T ∆ T,δ/4 1 + OPT(r, c B) -OPT(r, c Bm) min m -Ξ T,δ/4 , as claimed.

0 E

 0 empirical distribution; we then solve numerically the problem (4) with ν replaced by this empirical distribution: OPT (j) (r, c, B) = min λ X∼ ν (j) S max a∈A r(X, a) -c(X, a) -B, λ .

0 EFigure 1 :

 01 Figure 1: Performance of the PGD strategies.

  may be slightly adapted (again, because of ϕ) to show that Assumption 2 holds; seeLi and Stoltz [2022, Lemma 1 in Appendix B, as well as Appendix C].3 New, direct, dual strategy for CBwKOur 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.,[START_REF] Slivkins | Contextual bandits with packing and covering constraints: A modular Lagrangian approach via regression[END_REF], end of Section 2); we detail them carefully in Appendix A. We introduce dual variables λ ∈ [0, +∞) d , denote by • , • the inner product in R d , and we have, provided that the problem (r, c, B , ν) is feasible for some B < B:

  T,δ/4 proposed in the statement (note this value is slightly different from the one considered in Appendix B), we have, on the one hand, on E H-Az1 ,

	T	T			T	T
	c t α T,δ/4 1 +	c(x t , a t )	and	r t -α T,δ/4 +	r(x t , a t ) ,	(20)
	t=1	t=1			t=1	t=1
	and on the other hand, on E H-Az2 ,
	T			T
		c lcb δ/4,t-1 (x t , a t ) α T,δ/4 1 +	E X∼ν	c lcb δ/4,t-1 (X, a) π t,a (X)
	t=1			t=1	a∈A
	T			T
	and	r ucb δ/4,t-1 (x t , a t ) -α T,δ/4 +	E X∼ν	r ucb δ/4,t-1 (X, a) π t,a (X) .
	t=1			t=1	a∈A

Table 1 :

 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, c, 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 (<0.0001) 0.1962 (0.0002) 0.0004 (<0.0001)
	PGD γ = 0.05 0.4554 (0.0002) 0.0476 (<0.0001) 0.1961 (0.0002) 0.0003 (<0.0001)
	PGD γ = 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, c, B )	0.4691 (0.0002)
	PGD γ = 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 γ = 0.04 0.4621 (0.0004) 0.0478 (<0.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 γ = 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)

This simplification is not unheard of in the fairness literature; see, for instance,[START_REF] Chzhen | A unified approach to fair online learning via Blackwell approachability[END_REF]. It 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 γg is key for determining the average-constraint vector B.

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.

G.1 The experimental setting of [START_REF] Chohlas-Wood | Learning to be fair: A consequentialist approach to equitable decision-making[END_REF] We follow strictly the experimental setting of [START_REF] Chohlas-Wood | Learning to be fair: A consequentialist approach to equitable decision-making[END_REF] as provided in the public repository https://github.com/stanford-policylab/learning-to-be-fair. This experimental setting, as reverse-engineered 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 E], which would anyway rely on proprietary data that could not be made public.

Context generation. Each individual is described by four variables x: age, proximity, poverty, and group, which are to be read in x in its components, referred to as x age , x prox , x pov and gr(x) = x group . The first three variables are assumed to be normalized and are simulated independently, according to uniform distributions on [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 ν.

As we describe now, assistance has stronger impact on group 0 than in group 1.

Cost generation. We recall that three actions are available: offering some rideshare assistance (action a ride ), providing a transportation voucher (action a voucher ), or providing no help (which is a control situation: action a control ). The associated spending costs are deterministic and do not depend on x, and there are two separate budgets for rideshares and vouchers. More precisely, at round t, upon taking action a t , the following deterministic spending costs are suffered: c ride (x t , a t ) = 1 {at=a ride } and c voucher (x t , a t ) = 1 {at=a voucher } , where the corresponding average budgets are B ride = 0.05 and B voucher = 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 is given by

, and the second series is given by the opposite values of these costs. We denote by τ the corresponding average cost constraints τ , and set τ = 10 -7 or τ = 0.025 in our experiments.

All in all, the global (spending and fairness) vector costs c t takes deterministic values in R 10 . The vector cost function c is fully known to the learner, and no estimation is needed.

Reward generation. The rewards are binary: r t = 1 if the t-individual appeared in court, and r t = 0 otherwise. That is, the expected reward equals the probability of appearance. A logistic regression model is assumed: denoting by Φ(u) = 1/(1 + e u ), we assume r(x, a control ) = Φ(-x age ), r(x, a voucher ) = Φ(-x age + 2x prox )1 {gr(x)=0} + Φ(-x age + x prox )1 {gr(x)=1} , r(x, a ride ) = Φ(-x age + 4x pov )1 {gr(x)=0} + Φ(-x age + 2x pov )1 {gr(x)=1} . We may write these six equalities in a compact format as: r(x, a) = Φ ϕ(x, a) T µ PGD γ. We refer to the Box B strategy as PGD γ, for which we report the performance for values γ ∈ {0.01, 0.02, 0.04, 0.05, 0.1}.

We also implemented the Box C strategy, with an alternative value of M T,δ,k , given that the one exhibited based on the theoretical analysis was too conservative, so that no regime break occurred. We resort to a value of the same order of magnitude:

for a numerical constant c that we set to 0.01 in our simulations. We call this strategy PGD Adaptive in Figure 1 and Table 1.

G.3 Outcomes of the simulations

We take T = 10,000 individuals (instead of T = 1,000 as in the code by [START_REF] Chohlas-Wood | Learning to be fair: A consequentialist approach to equitable decision-making[END_REF] and set initial 50 rounds as a 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 ±2 times standard errors (shaded areas in the graphs or values in parentheses in the table ).

Graphs. In the first line of graphs in Figure 1, 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, we plot

We report the values of OPT(r, c, B) and OPT(r, c, B ) as dashed horizontal lines.

In the second and third lines of graphs in Figure 1, we report the average costs suffered; again, with obvious notation, we plot

We include the average budget constraints B ride = 0.05 and B voucher = 0.20 as dashed horizontal lines.

Finally, the fourth line of the graphs in Figure 1 reports the fairness costs; we average their absolute values and draw, again with obvious notation,

We include the fairness tolerance τ as a dashed horizontal line.

Table . We also report the performance of the strategies at 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 fairness costs, which is why we omitted it on the graphs, to keep them readable.

Comments. When γ is well set, i.e., large enough (see the bound of Lemma 1), 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 γ, 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 γ 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 λ B summarize the distribution ν, it seems that λ B has to be used with care: only with the exact values r and c, and not with estimates. On the contrary, the PGD strategies of Box B are more stable, as the dual variables are learned based also on the estimated reward and cost functions.