Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints
Authors: Martino Bernasconi
Matteo Castiglioni
Andrea Celli
Federico Fusco
Venue: NeurIPS 2024 poster (2024)
Keywords: bandits with knapsacks
long-term constraints
Primary area: online_learning

Abstract: We address a generalization of the bandit with knapsacks problem, where a learner aims to maximize rewards while satisfying an arbitrary set of long-term constraints. Our goal is to design best-of-both-worlds algorithms that perform optimally under both stochastic and adversarial constraints. Previous works address this problem via primal-dual methods, and require some stringent assumptions, namely the Slater's condition, and in adversarial settings, they either assume knowledge of a lower bound on the Slater's parameter, or impose strong requirements on the primal and dual regret minimizers such as requiring weak adaptivity. We propose an alternative and more natural approach based on optimistic estimations of the constraints. Surprisingly, we show that estimating the constraints with an UCB-like approach guarantees optimal performances.
Our algorithm consists of two main components: (i) a regret minimizer working on moving strategy sets and (ii) an estimate of the feasible set as an optimistic weighted empirical mean of previous samples. The key challenge in this approach is designing adaptive weights that meet the different requirements for stochastic and adversarial constraints. Our algorithm is significantly simpler than previous approaches, and has a cleaner analysis. Moreover, ours is the first best-of-both-worlds algorithm providing bounds logarithmic in the number of constraints. Additionally, in stochastic settings, it provides $\widetilde O(\sqrt{T})$ regret without Slater's condition.

Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints
Martino Bernasconit
Matteo Castiglioni
Andrea Cellif
Federico Fusco"
Bocconi university
Politecnico di Milano
Sapienza University of Rome
imarttino.eernacccoo andrea celli2] @uni cunibocconi. it,
matteo. matteo iattto..astigiiiine@eo.... federico. fuscoluniromat
Abstract
We address a generalization of the bandit with knapsacks problem, where learner aims to maximize rewards while satisfying an arbitrary set of long-term constraints. Our goal is to design best-of-both- booth-wooldss algorithms that perform optimally under both stochastic and adversarial constraints. Previous works address this problem via primal-dual methods, and require some stringent assumptions, namely the Slater's condition, and in adversarial settings, they either assume knowledge of lower bound on the Slater's parameter, impose strong requirements on the primal and dual regret minimizers such as requiring weak adaptivity. We propose alternative and more natural approach based on optimistic estimations of the constraints. Surprisingly, we show that estimating the constraints with an UCB- like approach guarantees optimal performances. Our algorithm consists of two main components: (i) a regret minimizer working on moving strategy sets and (ii) estimate of the feasible set as optimistic weighted empirical mean of previous samples. The key challenge in this approach is designing adaptive weights that meet the different requirements for stochastic and adversarial constraints. Our algorithm is significantly simpler than previous approaches, and has a cleaner analysis. Moreover, ours the first best-of-bothhwooldds algorithm providing bounds logarithmic in the number of constraints. Additionally, in stochastic settings, it provides Ö(vT) regret without Slater's condition.
1 Introduction
We address the problem faced by a decision maker who aims to maximize its cumulative reward over time horizon T, while satisfying arbitrary set of long-term constraints. At each round the learner selects an action a₂ from a finite set of K actions, and then observes a reward f((a)) and some costs 9a (a.) E 1-1, The goal is design rest-of-both-worlee algorithms for this problem that perform optimally under both stochastic and adversarial constraints. We always assume rewards generated adversarially. This is because the real complexity of the problem is captured by the nature of the constraints, so that transitioning from adversarial to stochastic rewards under the same type of constraints does not affect our results.
The first works on bandits with constraints focus on budget constraints, a.k.a bandit with knapsack (Bw3) [7] study the settings in which both rewards and constraints i.id. and propose UCB- based approach, combined with primal-dual method. Agrawal and Devanur [2) provide an UCB-like approach for more general rewards and costs. Immorlica al. [21], Kesselheim and Singla [22]
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

analyse settings with adversarial constraints and rewards, providing primal-dual algorithm to tackle the problem. Castiglioni et al. [15] show that a similar primal-dual approach provides best-of-both- worlds guarantees. Many subsequent works extend the setting to more general constraints, mostly employing primal-dual methods [16, 17, 28, 11, 13, 10, 18). Primal-dual methods have been the only effective method that provides best-of-both-wort both-worlds guarantees for bandits with constraints [16, 17, 11, 13, 10J. However, such methods require assumptions that are particularly stringent in settings beyond knapsack constraints. First, they require the existence of a strictly feasible solution (i.e. Slater's s condition) to avoid regret of order ((T [16, 28]. While this assumption always holds in bandits with knapsack setting (where "doing nothing" incurs in a negative cost equal to the per-round budget), this assumption is far more stringent with general constraints. Moreover, some works require the knowledge of lower bound on the Slater's parameter [16, 28). Subsequent works circumvent this assumption the expense of strong requirements the primal and dual regret minimizers [17, 11. 13, 11. In particular, such approaches require weakly-adaptive primal and dual regret minimizers. The challenge of applying such primal-dual algorithms to bandit beyond knapsack constraint is reflected in regret bounds that exhibit non-optimal dependencies on some parameters. For instance, a polynomial (instead of logarithmic) dependence on the number of constraints [17, 11, 13]. For further pointers to the literature, we refer to Appendix A.
1.1 Our contribution
We propose an alternative and insightful approach to design best-of-both-worff algorithms for bandit with long-term constraints. Our method relies on optimistic estimations of the constraints through a weighted empirical mean of past samples. Surprisingly. we demonstrate that using a UCB-based approach to estimate the constraints ensures optimal performance under both stochastic and adversarial constraints. Our algorithm differs significantly from previous (CB-based approaches. For instance, it guarantees no-regret even with adversarial rewards and stochastic constraints, unlike previous works [2. 7. 23]. Moreover, it is the first UCB-like approach that provides an optimal competitive ratio of + 1/p with adversarial constraints, where p is the unknown Slater's parameter.
Our algorithm consists of two simple components. The first is an adversarial regret minimizer working on moving strategy sets. In particular, at each round, the regret minimizer chooses a strategy in the current optimistic estimation of the feasible set, and is required to achieve no-regret with respect any strategy in the intersection of all feasibility set estimations. The second component is a tool for estimating the feasible set using an optimistic weighted mean of previous samples. The key challenge in this approach is designing adaptive weights that meet the different requirements for stochastic and adversarial constraints. Intuitively, in stochastic settings, we aim to converge to the (unweighted) empirical mean of the observed constraints. Conversely, adversarial settings, we should assign larger weights to recent samples to address time- time-dependent constraints.
Not only is algorithm significantly simpler than previous approaches, with clean and insightful analysis, but also provides better theoretical performance than primal-dual methods. Indeed, is the first woof--ooh-worllee algorithm to provide bounds logarithmic in the number of constraints. Moreover, in stochastic settings, it is the first algorithm to provide Ö(vT) regret without requiring Slater's ' condition. Finally, it guarantees that the expected violation in the current round converges to zero, making our algorithm "converge" to strategies that are feasible in expectation. This provides a more stable and consistent control on the violations.
2 Model and Preliminaries
We address the problem faced by an agent aiming at maximizing its cumulative reward over a time horizon T, while satisfying [m]] long-term constraints. The agent has set [K] of available actions and, at each round E [7]], selects d, E [K]. The agent then observes the corresponding reward fe(a:) [0. 1] and a cost 9; (a+) E [-1,, 1). for each constraint i E [m]]] We define the cumulative violation of the tt constraint as
(t) = ExETT Di (
(a:))
T
For any N E N. we use [JV] to denote the set (1....,A N).

---

while Vi == mm] Vz is the maximum violation across all constraints. At a high level, we want to minimize the regret while keeping the violation of each constraint v sublinear in T.
The focus of this paper is handling both stochastic and adversarial constraints. Conversely, always assume the rewards to be generated up-front by an adversary; we do not treat explicitly the situation where the rewards are generated i.i.d. because our guarantees are already tight for the harder case of adversarial rewards. In the stochastic setting, we assume that 9r = {9; he[m] is drawn i.idd from a fixed but unknown distribution g, and we let (a) = Eg [g (a)] be the expected
(2)
cost of action for the nd constraint. On the other hand, in the adversarial setting {gi (erterrr is an arbitrary sequence of cost functions.
Let Ax to be the set discrete probability distributions over the set []] Then, at round E [T], given randomized strategy 22 A the expected learner reward is EeElK] f((a)xx(a)) ( st).
Similarly, (rt, St ) denotes the expected cost of the ith constraint. Finally, we use ni (a) denote I(a, the number of times arm a was played up to time t, i.e. nı(a) Ia, = a).
We want to design algorithms which achieve good performances in both the adversarial and the stochastic setting. As customary in the literature, we compare our learning algorithm with different benchmarks according to the setting.
Stochastic Benchmark In the stochastic setting, the constraints g;" are i.i.d. samples with mean g(d) and thus we consider as benchmark the best fixed randomized strategy that satisfies the constraints in expectation, which is a standard choice in bandits with constraints [11, 28, 16). Formally, in the stochastic setting, we can define the feasible sets X and X as follows:
x = x E AK: (x, ( s of and x = =<ee[m] X
Then, we can define the stochastic baseline as:
OPTs == max
Σ St). x XE[T]
We naturally assume the existence of safe mixed strategies, i.e. that X** 0. This is equivalent to assume the existence of randomized strategy x such that (x ,g()) < for all i. Notice that this a weaker assumption than the one commonly assumed by best-of-boothworlde algorithms in which (x (g()) S -p, where p is a strictly positive constant (see, e.g., [16. 11, 10].
Adversarial Benchmark In the adversarial setting, (acher an arbitrary sequence of con- straints. We consider as benchmark the best unconstrained strategy:
OPTA = max
((, tE[T]
Σ
(t)
ZEAK
While this baseline has already been used [e.g.. 11, 13]), other works on adversarial bandit with constraints employ weaker baselines [e.g.. 21, 16). For instance, Castiglioni et al. [16] consider the best fixed strategy which is feasible on average. However, we show that, despite using a stronger baseline, we obtain competitive ratio that is optimal even for the weaker baselines commonly adopted in the literature [16, 10, 9].
2.1
Guarantees
Our goal to design learning algorithms that exhibit optimal guarantees both in the stochastic and adversarial settings. In the stochastic setting, we are interested in minimizing the regret Rt w.r.t. OPTs:
R OPTs EiErry f((a)).
Indeed, when the constraints are stochastic, obtain the state-of-the ofeee--f-th--arr Õ(VT) regret even with adversar- ial rewards.
3

---

Algorithm
Require: bonuses b (a), weights w and parameter |
1: Initialize regret minimizer R with
2: for each step & I,...,
,...,, do
3: Estimation:
4:
9:
(a) (a) t EreTi wi,a (T) (a) for all a E [K] and e [m]]
(8) (8)
5:
2000 - fx E Ak (z.
(x. 0(
b,) - 00}
- [-] 8(11
6:
7:
Regret minimization:
8: Get prediction from R on set R; R(Z)) (8) 9: Sample a, 24 and receive {g: (ee)) and fa(
and specifically we require both Ry and VT to be in Õ(vT) with high probability. This clearly matches the standard ! (V(T) lower bound that holds even without constraints [5].
In the (harder) adversarial setting, pose the less ambitious goal of achieving a constant competitive ratio with respect to OPTA, or equivalently sublinear a-regret with constant a. Formally, given an 1, we define the a-regret as:
a-RT a OPT
Exery Ss(ae).
As eustomary in the literature [15], the competitive ratio a obtained by our algorithms depends on the following Slater's parameter p:
p= inf [ (E]]
max 9: (a).
(1)
The parameter p is related to the existence of strictly- actions, and only depends on the constraints. Our definition is slightly stronger than the one in most previous works where the inf is over randomized strategies. To guarantee the existence of feasible strategy we assume that 2 0. Then, our goal is to guarantee that both Vr and the a-regret, with 9/p+1, belong to Ö(vT) with high probability, Note that this matches the lower bound of Bernasconi et al. [11].
3 Our Approach
In this section, we present the main components of our algorithm, while the following sections will describe the specific components in details. We refer to Algorithm for the pseudocode. At each step f, the algorithm works in two phases: i) estimates the feasible set, and ii) plays strategy in the estimated set. Each phase requires a specific ingredient:
An estimator dt of the costs functions gi that used together with the optimistic bonus by to define the estimation of the feasible set defined as & == [ p(() In the stochastic case, we would like & 2 X", while in the adversarial case our goal is to maintain a sequence of sets that always contains version of the action set X, properly scaled around n (see Equation (2) for a formal definition).
ii) A regret minimizer R for adversarial linear reward function that, at each round, takes in input a convex set of feasible strategies X, C AR, and then selects a strategy F, E L, We require the regret minimizer to achieve Õ(VKT) regret with respect to any E (xelT] &g;
In the following we define the two phases more in details. Let Tr, (T S (: 0r a} be the set of rounds in which the algorithm plays action a. Then, at each round I, Algorithm computes the estimate
of (
Σ
( (1)g
Va E [K] and i [m]
TET-1.00

---

Algorithm 2 No Regret on Moving Sets
Require: Parameter B > 0
1: Set y= f/2
2: for each step t 1, , do
3: Receive Xe
4: Er(a) f- Ht- (a)e(()))(/
for all a [K]
5: It f g2 (ft) = arg ze [xx]((a))
6: Sample
7: Observe fi(a)) and set fi(a) for all + at and f((as) t- - 1-fi(a)) (e
as the weighted mean of available past observations (9+² (e)t)[( for each actions [K] and constraint E [m], for some weights w Then, the estimates together with the optimistic bonus {br [aE[]] are used to define the moving sets R, which are fed to the regret minimizer R. which turn selects a point 22 E &..
One crucial property that is required for the execution of the regret minimizer R that all the sets & are non-empty (as otherwise the regret minimizer has no feasible strategies). To simplify exposition, in the following sections we assume that the clean event == & * v E [T]] holds. In Corollary 6.3, we prove that this event holds with high probability in the stochastic setting, while in Theorem 5.2 we argue that it holds deterministically in the adversarial one.
In Algorithm we left unspecified two crucial parts of our approach. The first is how to build the regret minimizer R. and the second concerns how actually generate the sets &, i.e., the weights wi, and the bonus by (a). We delve into these details Section and Section 5, respectively.
No-regret on moving sets
We describe the regret minimizer R that exhibits no-regret with respect to any x E Overry &c We achieve this via simple modification to the EXP-IX algorithm of Neu [25] that provides high probability results for multi-armed bandits via implicit exploration. More specifically, our algorithm maintains randomized strategy He E Ak which is updated using the biased reward estimate (a) as in Neu [25] and then projected onto X₁ according the negative entropy Bregman divergence B (xxl(y) = Ene [K] [a<a) log (d(a)//(a)) z<a) + y(a)). We refer to Algorithm for the pseudocode, and present here the main result of the Section.
Theorem 4.1. Let xe be selected accordingly to Algorithm 2 run with arbitrary sequence of convex sets 8g C AK with 7 = and B =
log k/6)) KT
Then, with probability at least 1 - ò1 holds that
Σ (f. fe(a:) < 4V Loglog(K/o)) LETT
Va
n & LE[T]
This result establishes no-regret in the case of moving sets, taking as benchmark the optimal strategy in the intersection all sets. To exploit this result in Algorithm the stochastic and adversarial setting the intersection the sets & contains "good" strategies. the stochastic setting, show that with high probability it includes X", while, in the adversarial setting, it includes a strategy with utility r/1+p- OPTA-
have to make sure that in both
How to build the sets &
In this section, we show how to design estimations X, of the feasible sets that, surprisingly, are effective both in stochastic and adversarial settings. Indeed, the main challenge is to design sets &,
IIf given action has been played at least once, require ΣTET.LI. (022 1. i.e., that d (a)
actually weighted mean. Otherwise, the estimation is simply set 0.
5

---

that accommodate the different requirements of the two settings. First, in Section 5.1, we discuss how to the optimistic bonuses b, and then in Section 5.2 we focus on how the weights w
5.1 How to set the optimistic bonus
The optimistic bonuses have the main purpose of balancing the estimation error in the stochastic setting. As the following lemma show, we simply need that (a) - (a) S be(a) with high probability. Indeed, this is sufficient to show that X EtEeTT 2 in the stochastic setting.
Theorem 5.1. Consider the stochastic setting. Given any 5 0, ler (a) be such that with probability at least 5 holds:
10 10 (a) (a)) b.(a) WE [7] E [m] E [K].
Then, it holds X' E Chelrr &e with probability at least
Even tough it is crucial in the stochastic setting, it turns out that in the adversarial setting the optimistic bonus by is not really needed. Indeed, as we will show in the following, we are interested obtaining no-regret with respect to the set X2 which is obtained via interpolation of points in X' and the strietly feasible actions a Let x be such that x (a*) =1 and x (a) 0 for all o a Formally:
P X
I+p
1+p
where A + B is the Minkowski sum between sets and aA indicates the set that contains each element of A multiplied by a. The following theorem proves that X2 S X, for all t.
Theorem 5.2. In the adversarial setting, it holds X' C &g for all t E [7]-
Notice that having no-regret with respect the set N is not sufficient to achieve no-regret in the adversarial setting. Nonetheless, we will show that this sufficient to guarantee no-a-regret, for p/I+p with respect any strategy AR.
5.2 How to set the weights
We focus the design of estimators Algorithm computes the estimators 91 by using a weighted mean of all past observations:
(t) P that are good approximations of the real functions gi
(a)==
ΣTET 1.a Wi,
12 (7) (a) Vt E [T],e E [K], i E [M]]
However, to simplify the exposition, we use the following equivalence between online gradient descent (OGD) quadratic losses gf (a:) - 9: (4) (ax) of0h (a:) and weighted means. In
particular this equivalence is realized by observing that such loss has gradient dh ((x)) - -. (at). Lemma 5.3. Given any sequence herrr such that y12 = and any sequence of learning rates (nceet such that Th = 1, let (ūcherr be the estimator updated as:
Det1 De + T/e -e)-
Then, it holds that Ot. Σ wr(T) = for any t 2 2.
E1=1 (T) where wx(T) 1/ I1 mp)). Moreover,
Clearly, in the OGD interpretation of our update, we only update of (a) only when at = a, and thus we only need to define learning rates for action a for the times f in which = a. Based on this observation, we are going to update (a) as
o (a.) (ax) + uie (8)
(ax) (vt" (()() - ((((a))
(12, 9f90 (a)
Ya + at
'Formally Minkowski sum between sets A + B is defined as A B (bb

---

Thus, given action E [K] and time & [T] the corresponding weights (T) are:
( wi, (T) T
II
(1-
(8) Th (a)) VT E T--1.
KETE 1,0:27
We now proceed to give two notable examples on how to instantiate the learning rates and recover commonly used estimators such as the empirical mean and the exponentially weighted mean."
Proposition 5.4. 1h (0) (at) = 1
me(as) for each E Ti- then w (T) me-i(a) and we recover
the empirical mean estimator for 9:¹ (a) ar 2(a) ErET Or ( Proposition 5.5. Th (at) = then
(a).
w 1/(1 (MET latksr)
for each T E Te- and we recover an exponentially weighted average estimator for ( (a).
As it will turns out, these are the two extreme cases that we want to interpolate between. Indeed, the empirical mean estimator is particularly effective in the stochastic case but ineffective in the adversarial case, while the converse happens with the exponentially weighted estimator.
Now, we show that the OGD interpretation is particularly useful bounds the violations suffered by the algorithm. First, we define the violations in an interval [41 [2] == {i E [T] : 4 S L S (2] as:
O (a.).
Then, in the following lemma show that the violations in the interval are related the variation of the estimates gf5² (a).
Theorem 5.6. Given interval [t,,t]] t2] S [T]] an i [m]] and 8 0, with probability at least
1 it holds:
( (11
S
Σ EE
(00 - +
(I b,) 44 t, loggo(((/))
NE[K] (1 M ()(() (a)
By simple telescoping argument, have the following corollary, which holds whenever the learning rates are non-increasing within time interval. Let E(a, (2]) be the last rounds in the interval [41, to] in which action played.
Corollary 5.7. Given an interval [1,42] C [T]. a E [m]. and a > O, assume that for any E [K] holds (8) (a) Ti (a) VT I'' Taga n [11,12] 12). Then, with probability at least 6
(8)
holds:
V (txtal
2
(ar, + +4 - tt log(//)))
(a)
aE[K] (t(a
(8) Corollary 5.7 shows how to bound the violation a function of the learning rates my and the bonus terms by. The following lemma shows how to bound the second term of the violations depending on the structure of the bonus terms.
Lemma 5.8. Given с > O, an a E (0, 1), a t e [T], and a 0, let (a = mx(aj= for all
E [K]. Then, with probability at least 1 5, it holds:
Σ (ar,
Kayl-a + 4 (lg(1/)).
In this section, we saw how the choice of the learning rates of the estimator affects the estimators. In the following section, we will see how to adaptively set those learning rates to handle both stochastic and adversarial settings.
'The proof of the first proposition can be found in Appendix D, while the proof of the second is straightiorward and thus it is omitted.

---

Adaptive learning rates
The previous section highlights the main difficulties of obtaining best-of-both-wort woold algorithms: we (6) (at)) and the need to set the weights wie (or equivalently by Lemma 5.3 the learning rates Y)
(6)
optimistic bonuses so that they meet, the same time, the requirements needed by the stochastic and the adversarial settings.
We start presenting two possible choices and show that they fail either in the stochastic or the adversarial setting. Then, we show how adaptive learning rates combine the strengths of both approaches. The first, natural, choice of setting the learning rate is to use an exponentially weighted estimator, i.e., choose '/i (ax) = 1/VT. With this choice, we can apply weighted version of Azuma- Hoeffding inequality and find that 19t (a) (a)) E Ô (v.(a)=//) with high probability. Thus, as discussed in Section 5.1, we would need to define be(a) (mi(a)-Va) which, by Corollary 5.7 and Lemma 5.8 would imply suboptimal Ö(T%/4) rate for the violations.
The second option is set 1i ( (at) 1/melar) In the stochastic setting, have an optimal rate of concentration of the terms 19. () (a) (a)) E (n,(a)-1/a) as, by Proposition 5.4, this is equivalent compute the empirical mean. However, this second option fails disastrously in the adversarial setting as highlighted in Corollary 5.7, where the first component of the violations becomes linear in T. Intuitively, learning rate of order (a) makes the update of the estimates slow when the underlying constraints change, as it does happen in the adversarial setting.
This trade-off forces to employ adaptive learning rates. Our idea is to learning rates of the order l/n.(a) with an adaptive multiplicative term that depends on the current violation of the constraint. Formally, we use learning rates:
ne ( (as) ne(a) (1+1(").
where r.00 is bonus term defined as
21 Ki
(v())
/ Kt log(1/8))
and [=]] = min(max(( a), 6) is the clipping of a between a and b. Moreover, we set the exploration bonus
2 2l0((3/)))
be(a)
The following theorem shows that such approach guarantees Ö(vKT) violations in both adversarial and stochastic settings.
Theorem 6.1. Both in the stochastic and the adversarial setting, with probability at least 1 2m1 holds that
V1 S Ktlo((2////
Vt [T].
The previous theorem shows that this choice of learning rates sufficient to guarantee optimal bounds on the violations. However, to achieve this result we are setting (a) E (nn,())- As we showed in theorem 5.1, this requires concentration the estimates Ig. (a) g. magnitude (in the stochastic setting). This crucially needed to ensure that the regret minimizer R provides the desired guarantees and that the event C defined in Section 3 actually holds with high probability.
(t) (a) of the same
Lemma 6.2. the stochastic setting, with probability at least 5mKT5,, holds that:
(1) (a) (a)) < be(a) Va E [K], E [T], E [m]
The proof of the previous result relies the fact that in the stochastic case the bonus 1 does not "kick in" ensuring that (0) (a) = (o). Thus, g. is the empirical average of past observations. The previous result, together with Theorem 5.1 proves the following corollary.

---

Corollary 6.3. In the stochastic setting, with probability at least 1 5mKTT2, it holds that X E R, for all [T].
This proves that the clean event C holds with high probability, as promised in Section 3.
7 Putting everything together
Now, we have everything in place to easily prove the our main theorems. First, we define the parameters 51 81 (c) and 82 52(c) in order guarantee that theorems hold with probability at least - c. particular, we set (c( = $/2, where we recall that 61 is the parameter used to set and 7 in Algorithm 2, and 62(e) //11mmT*) where 82 is used learning rate of Algorithm 1.
the optimistic bonus and
In the stochastic setting, the violation guarantees directly follow from Theorem 6.1, while the regret guarantee follows by combining Theorem 4.1 and Corollary 6.3. Formally:
Theorem 7.1. In the stochastic setting, for any > Algorithm 1 guarantees that with probability at least 1 -
RT S BLKKKoogg22 and Vi S / Ktt//toooo(28mK//66 Vt [T].
Now, turn to the adversarial setting. Theorem 6.1 guarantee Ö(VT) violations even with adversarial constraint, while the regret guarantees follows by combining Theorem 5.2 and Theorem 4.1
Theorem 7.2. In the adversarial setting, for any e > 0 Algorithm I guarantees that with probability at least c
a-RT S 4v KT (2g(2//) and V₁ S 53 Kt Ktloog
Vt E [2].
where a = P/(Lt)))
Note that in both settings, the regret upper bound is of order Ö(v KT) and it is independent from the number of constraints m, while the violations are order Ö KT log(m)) and depend only logarithmically m. This is in contrast to the other best-of sesttoof-bohhwooor algorithms for bandits with long term constraints, based on primal-dual methods, which both the regret and the violations depends polynomially in m.
Another interesting characteristic of methodology is that guarantee anytime bound on the constraint violation. Indeed, this matches the guarantees provided by the most recent primal-dual methods [11, that, however, require weakly-adaptive underlying regret minimizers.
7.1 Convergence rate in the stochastic setting
To conclude, we point nice byproduct of analysis. In the stochastic setting, we can easily prove a sort of "convergence rate" of Ie to the set X'. Formally, we can prove that positive violations are bounded by OlyKtlo m.) as long we consider expected violations. Let us define x+ = max(x, (z, 0) and
V =
( 0f0000000
maax [m]m
Then, we can state the following theorem:
Theorem 7.3. Algorithm I, in the stochastic setting, guarantees that with probubility at least 1 e, it holds that:
Vt s (tt/KKloo(22mKT
Vt [T].
Intuitively, our result shows that our algorithm plays only a sublinear number of times "far" from the set X", or that our algorithm plays línear number of times "close" to the set X This is much stronger result then just guaranteeing that Vr is sublinear, as in that case might be a linear number of times the algorithm plays "far" from X' as long as it plays strictly inside of X often enough.

---

Acknowledgments
MB, MC, AC, FF are partially supported by the FAIR (Future Artificial Intelligence Research) project PE0000013, funded by the Nex(GenerationEU program within the PNRR-PE-AI scheme (M4C2, investment 1.3, line on Artificial Intelligence). is also partially supported by ERC Advanced Grant 788893 AMDROMA "Algorithmic and Mechanism Design Research in Online Markets", and PNRR MC is also partially supported by the EU Horizon project
MUR project So00000 ELIAS (European Lighthouse of AI for Sustainability, No. 101 101120237). AC is partially supported by MUR - PRIN 2022 project 2022R45NBB funded by the NextGeneration program.
References
[1] Gagan Aggarwal, Giannis Fikioris, and Mingfei Zhao. No-regret algorithms in non-truthful auctions with budget and ROI constraints. arXiv preprint, Jbs/2444409882,, 2024.
[2] Shipra Agrawal and Nikhil R. Devanur. Bandits with concave rewards and convex knapsacks. In EC, pages 989-1006. ACM, 2014.
[3] Shipra Agrawal and Nikhil R Devanur. Bandits with global convex constraints and objective. Operations Research, 67(5): 1502, 2019.
[4] Peter Auer and Chao-Kai Chiang. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. In COLT, volume 49 of JMLR Workshop and Conference Proceedings, pages 1 116-120. JMLR.org. 2016
[5] Peter Auer, Nicolo Desa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-777 77, 2002.
[6] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knap- sacks. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013, pages 207-216. IEFE, 2013.
[7] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knap- sacks. J. ACM, 65(3), 2018.
[8] Santiago Balseiro, Christian Kroer, and Rachitesh Kumar. Online resource allocation under horizon uncertainty. SIGMETRICS Perform. Eval. Rev., 51(1):63-66 64, 2023.
[9] Santiago R Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, 65(9):3952-3968, 2019.
[10] Santiago R Balseiro, Haihao Lu, and Vahab Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. Operations Research, 2022.
[11] Martino Bernasconi, Matteo Castiglioni, and Andrea Celli. No-regret is not enough! bandits with general constraints through adaptive regret minimization. arXiv preprint, abs/2405.06675. 2024.
[12] Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. No-regret learning in bilatcral trade via global budget balance. In STOC. ACM, 2024.
[13] Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. Bandits with replenishable knapsacks: the best of both worlds. In International Conference on Learning Representations (ICLR), 2024.
[14] Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. In COLT, volume 23 of JMLR Proceedings, pages 42.1-42.23. JMLR.org. 2012.
[15] Matteo Castiglioni, Andrea Celli, and Christian Kroer. Online learning with knapsacks: the best of both worlds. In International Conference on Machine Learning, pages 2767-2783. PMLR, 2022.
[16] Matteo Castiglioni. Andrea Celli, Alberto Marchesi, Giulia Romano, and Nicola Gatti. A unifying framework for online optimization with long-term constraints. In Advances in Neural Information Processing Systems, volume 35, pages 33589-33602, 2022.
[17] Matteo Castiglioni, Andrea Celli, and Christian Kroer. Online learning under budget and ROI constraints via weak adaptivity. In ICML. OpenReview.net, 2024.
10

---

[18] Giannis Fikioris and Eva Tardos. Approximately stationary bandits with knapsacks, In Proceed- ings of Thirty Sixth Conference on Learning Theory, volume 195, pages 3758-3782, 12-15 Jul 2023.
[19] Elad Hazan et al. Introduction to online convex optimization, volume Now Publishers, Inc., 2016.
[20] Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, and Aleksandrs Slivkins. Adversarial bandits with knapsacks. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 202-219. IEEE Computer Society, 2019.
[21] Nicole Immorlica, Karthik Sankararaman, Robert Schapire, and Aleksandrs Slivkins. Adversar- ial bandits with knapsacks. J. ACM, 69(6), 2022. ISSN 0004-5411.
[22] Thomas Kesselheim and Sahil Singla. Online learning with vector costs and bandits with knapsacks. In Conference on Learning Theory, pages 2286-2305. PMLR, 2020.
[23] Raunak Kumar and Robert Kleinberg. Non-monotonic resource utilization in the bandits with knapsacks problem. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[24] Shang Liu, Jiashuo Jiang, and Xiaocheng Li. Non-stationary bandits with knapsacks. Advances Neural Information Processing Systems, 35:16522-16532, 2022.
[25] Gergely Neu. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 28, 2015.
[26] Yevgeny Seldin and Gábor Lugosi. An improved parametrization and analysis of the EXP3++ algorithm for stochastic and adversarial bandits. In COLT, volume 65 of Proceedings of Machine Learning Research, pages 1743-1759. PMLR, 2017.
[27] Yevgeny Seldin and Aleksandrs Slivkins. One practical algorithm for both stochastic and adversarial bandits. In ICML,, volume 32 of JMLR Workshop and Conference Proceedings, pages 1287-1295. JMLR.org. 2014.
[28] Aleksandrs Slivkins, Karthik Abinav Sankararaman, and Dylan J Foster. Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression. In The Thirty Sixth Annual Conference on Learning Theory, pages 4633-4656 PMLR, 2023.
[29] Chen-Yu Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In COLT; volume 75 of Proceedings of Machine Learning Research, pages 1263-1291. PMLR, 2018.
[30] Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. J. Mach. Learn. Res., 22:28:1-28:49 2021.

---

A Further Related Works
Best-of-Botte Word-- A long line of work has investigated Best-of-Both- Wordds algorithms for bandits without constraints. These algorithms aim to achieve an instance-dependent logarithmic regret bound in stochastic environments, while also ensuring the worst-case e regret bound that characterizes the adversarial settings [14, 4, 27, 26, 29, 30J. Although our focus is on the generation model of the constraints, our motivation in this paper is affine: retaining the best of the stochastic (sublinear regret with respect to the optimal dynamic policy) and adversarial world (tight competitive ratio with respect to the adversarial benchamrk). Furthermore, our idea of setting adaptive learning rate that forces the learning algorithm to interpolate between an adversarial and a stochastic routine is reminescent of some of the techniques adopted in, e.g.. Bubeck and Slivkins [14].
Bandits with Knapsacks. The (stochastic) BwK problem, where the rewards ft as well as the gf are drawn ii.d. from non-negative distribution (so that the budget available for each resource can only decrease over time) is formally introduced and solved in Badanidiyuru al. [6] (see also its journal version [7]). Agrawal and Devanur [2] studies more general stochastic setting, which subsumes knapsack and exhibit optimal guarantees via optimism the face of uncertainty [see also 31. Moving to the adversarial BwK problem (which corresponds to our model when the 9f are all non-negative), an optimal solution is proposed Immorlica al. [20] [see also 21]; there, the authors propose the LagrangeBvi framework, which has natural interpretation: arms can be thought of as primal variables, and resources as dual variables. The framework works by setting up a repeated two-player zero-sum game between a primal and dual player, and by showing convergence to Nash equilibrium of the expected Lagrangian game. Differently from the stochastic version, the adversarial BwK does not admit no-regret algorithms, but @ I') competitive ratio. In a subsequent work. [22] provides a new analysis obtaining a Olog m log 7') competitive ratio, which is optimal both in the time horizon T and in the number of resources Immorlica et al. [20, 21I). In the special case in which budgets are ((TT), Castiglioni et al. [15] further improves the competitive ratio to 1/p where p is the per-iteration budget.
(and improves on the Om log T)) of
More general constraints. Castiglioni et al. [15] studies setting with general constraints, and show how to adapt the LagrangeBwK framework to obtain tosstoof-bth-worfde guarantees when Slater's parameter is known a priori. Similar guarantees are also provided, in the stochastic setting, by Slivkins et al. [28], which then extend the results to the contextual model. Finally, Castiglioni et al. [17] introduces the use of weakly adaptive regret minimizers within the BagrangeBBW framework, and provides guarantees in the specific case of one budget constraint and one return-on-ines on-investmentss constraint.
Other related works. In an effort to bridge the results for adversarial and stochastic BwK, Fikioris and Tardos [18] investigates data generation model that interpolate between the fully stochastic and the fully adversarial setting, depending on the magnitude of fluctuations in expected rewards and resources consumption actoss rounds. A similar effort is undertaken in Liu et al. [24], that study non-stationary setting and provide no-regret guarantees against the best dynamic policy through a UCB-based algorithm. A recent line of work also investigates the natural situation where resources can be replenished in certain rounds (as also captured in our model) [23, 13, 12]. Finally, a related line of works is the one on online allocation problems with fixed per-iteration budget, where the input pair of reward and costs is observed before the learner makes a decision [10, 8).
B Proofs omitted from Section 4
Theorem 4.1. Let xe be selected accordingly to Algorithm 2 run with arbitrary sequence of convex sets Le C Ax with 7- = 2 and B = log( (
Then, with probability at least 1 - 8, it holds that KT
Σ 2) - fe(a.) < 4 (o]o)(()))).
Vx E n &, :E[T]
3E [E[T]
12

---

Proof. Let us define the negative entropy for vector 2 E Ry as:
(x)
Σ dE|K]
x(a)
(log(<(a)) - 1)
and the Bregman divergence using V can be written as
B(ally) == (x) ( - (VV()), - v)-
For the Bregman divergence holds the following:
Claim B.1 ([19)). For any 21, =2, and 23, holds:
B(alll22 + (322|123) (221l(za) (21 1 V2)(23) (22(2))
Moreover, given z, define = arg minlee [=] Then:
B( - B(*1l1²) {()) B(8l(²)
v E K.
At this point, is more convenient to work with losses rather then rewards. Define (((a) = 1 - fi(a) and (a) == 1- (a). Note that:
{ if + ar if
L((a) (10)==1f(())
I-f((a)
(a(a))
at-
Then, it easy to verify that (x) = log(z) which log(x) has to be interpreted to be applied entry-wise. Simple calculations also show that Glg = log(z,) - log((z+1). Thus, we can apply Claim B.1 with 21 I, 22 I2 and 23 f.-1 and this gives us the following:
B(ze z. 2.) (z)) + B(zr|l - B(x||
Moreover using the second part of Claim B. in which = = 5., = Dt. = x, and K. = &, we can conclude that (xx])ax;) < ((r|(2)). Notice that here we use x E Rr for each t. Then, we have the following chain of inequalities:
B (xt x, 2,) =
Σ
B(x + B(x, (1044)) B(x1(8141)
(By Equation (3))
1E[21
tel7
B(<[(=)) - ((x
Σ (B(x|l=;)- B(xl(a)) +
Σ B(xe|(ir+1)
< B(+]|=)) +
Σ B(xillee+1) (B is non-negative and B(-1laa)) < B(-l(a)))
[E[T]
B(([(²1) +
B(Ielle+41
1E|T
Combining the two we can find that:
Σ ( - x,
22) <
[B( B(xalle44)) (x]l))44))
(4)
<
B(xl(a))
B(ralle441)
(5)
13

---

Now we analyze the term B(xe|l@t+t))
((+1) I B(sel [(+1) 1) + B(fe+1llzz)
= (ore - Bit1, (1)) - vV((++1))
(Definition of B--1l.)
B(xx 11t1,l)) la) (VV()) log(2) and S6, log(zs) log (1+1))
B Σ
aE[K]
S 8 <E[K]
Σ (a))))((a)²
(1- 5
1- filo)
18 Σ
(a(a){((a)
(1(a)
18
Σ (((a).
where, in the last inequality, we that (x()) is most 1. Thus, by choosing x (a) for all a, we have that [(x((=1)= S log( K) and thus:
-/KK
Σ (a.- 10-2,6) S
log( K)
+ Σ Σ
E
(((a)
(6)
3
1E[2]
1E[2
Form [25, Corollary 1] we know that with probability at least 1 - 81 we have:
1og(K/6.)
E
- -
fx(a) <
Va E [K]]
27
:E[T]
Moreover, it is easy to verify that:
1 - fe(a.)= = Σ T(a = a) - -(((a) Tt((a) +7
ze((a +y
dε]A]
4(a)l(a: =
Σ (((a)z(()+ +7 Σ
aE[K] (1 +7
[E[K]
= (2,, 42) +y Σ (a(a)
(8)
[E[K]
The regret is with probability at least 1 81:
Σ [E[T]
[1x, fi) fe()))]
Σ [11 fe((a)) - (x,, fi))
[E[T]
Σ [11 Se(ax)) - -(x, 20)++ + Σ [/,, E.) - (1 - (1-(x, (x))1
[E[T]
[E[T]
<
Σ (xt x, Ee) + Σ
Ka,, Ex) (1 - (2,, fo)) +7 Σ Σ (((a
(Equation (8))
LElT]
LEl2T
KE|2 aE[K]
log(K) K)
log(K/6))
+
+ + +) Σ Σ L((a)
(Equation (6) and Equation (7))
B
27
1E[T] aE[K]
log(K) K)
log( (8/8))
(K/1)
+ +
Σ f((a)) + K
B
27
27
log(K)
log( (g/51)
(og(K/6))
+
+ + + KT + (r + B)
B
27
27
log(K) K)
log( log(K/81)
23KT (Klog(K/s.)
B
8
14

---

(log(//5)) KT
where in the last inequality we used that / = 2y. By taking 3 probability least 1 - ō1:
we obtain, that with
Σ
(e, fi) f+(a:)) 4v (Tlog(K//))
as desired.
C Proofs omitted from Section 5.1: How to set the optimistic bonus
Theorem 5.1. Consider the stochastic setting. Given any let (a(a) be such that with probabiliity at least - 5 it holds:
19 1 (a) (a)) WE [ [m] [K].
Then, it holds X C [ Me with probability at least 1 - 5.
Proof. In the following, we assume that the condition the statement of the theorem holds. Hence, our result with hold with probability 1 - 8 as promised. Let E X Consider a & E [7] and an i [m]] Then, consider the following inequalities:
(x.9) br.9!"; (z, 01 -g(0) + (I,
- (z, ((0 - g ())
(x E X,)
Σ xla)(ii (a) - (a)
(
aE[K]
(x, be).
Thus, (x, g(0) be) S which, by definition, proves that x E 2000) This concludes the proof.
Theorem 5.2. In the adversarial setting, it holds N' C & for all t e [T].
Proof. In the adversarial setting, by Equation (1) we have that
gi <a))
for all [2] and constraint E [m]. Moreover, for each & [T], i E [m]] and [K], it holds
9 (a) Σ ( gf
gf (a)
TET.
and ΣTET, 1. (T) 1. Then, for all / E [T] and constraint i E [m]] (0) (a 5 -p and (3)
Hi (a) for each o a Thus, we can consider the following inequalities for any f E X
(5, 0600 = 1
(10 (a
+ P
(cc, 9t
+ p
1
1
<
(-p)
+
1+ p
1 1+p
<
thus proving that ã X
'Notice that these inequalities hold only for action played at least one time. Otherwise, similar inequalities continue to be true thanks to the optimistic bonus by.
15

---

D Proofs omitted from Section 5.2: How to set the weights
Lemma 5.3. Given any sequence (UeTEETTy such that y1 and any sequence of learning rates hnetrty such that Th 1. ler (eerre be the estimator updated as:
De+1 = Dt + T) (V+ - -e)-
Then, it holds that
Σx= (T) where wx(r) 1/7 Il ms)- Moreover,
Er=l we(T) = for any t 2 2.
Proof. The first part of the statement is trivial as it can be easily checked that:
Σ
II (1 mm)m))
y/r
k=T+1
Then, we prove the second part of the lemma by induction on The base case holds trivially as (1) 77 1. Moreover, assuming Σ w
holds:
Σ -m(()== ( 1)- + we(t = 7/- 1/--)) 7/-
where in the second-to-last equality we use the inductive hypothesis. This concludes the proof.
Proposition 5.4. If (6) (ax) Relas] for each E Tr then ((,a(T) me-i(a) and we recover
the empirical mean estimator for g. (a) me-1(a) ET gr (a).
Proof. Consider an a E [K] an E [m]. and & [T]. Then, by applying Lemma 5.3 the of rounds Te-1,a we have that:
( Tor (a)
II KETi-TatRSt
(1-
(1-ma(a)
1 na(aa
Vr E Ti-1a.
Now, we show that
II
1 nex (a)
II
(x(a) -
nx(aa
kET: luck>r
KET Lackke
14)1(a)
j= (a)+1
(a
R4-1(a)
(1) and thus w (T) mt-i(aj. as desired.
Theorem 5.6. Given interval [f1, t2] S [T]] an i E [m]] and 8 > 0, with probability at least
1 it holds:
(1)
Σ Σ
(fth - + Σ (x b.) 4/ log())))))
(1.tal
ny ()(()
aE[K]
rET (t
Proof. First, applying Lemma G.I, we have that with probability it holds:
4 Σ
(o xx) 2 Σ (0) (ar)
4/(12 t1 log(1/)
(9)
T=h
16

---

Consider the following chain of inequalities:
tg
v(()
Σ
(a+)
[(1)12]
gm
12
97 (a+)
(1)
kT) +
Σ
(er, bz)
(x, E &,)
1=11
==
T=11
(i) (ar)
(ar)
(Tr, br) 1//(12
(l2 (1) log(1/6)
(Equation (9))
7=t1
t2
E
Σ
(0 0.th g.
+
Σ
(Ir, br) + +4V(12 - t1) log(/8)
rESK TET
T=
(6) (a) (a) 9o
E
Σ
+
by) + 4/ (96--(4)11 11))108( 1o8(1/6)
aE[K] TETey
7=
where the last equality follows by the definition of the update:
(a) = (1 (1-7 (1) (a) + n (a) for a = ar-
This concludes the proof.
Corollary 5.7. Given an interval [ti, t2] S [2], a E [m], and a ô > 0, assume that for any E [K] holds T/ (a) 2 n (a) Vr o' E Tia n [11, 12). Then, with probability at least 5 holds:
(8)
( (nitt) S
2
(ar, b,) + 4t - t1 log(1/))
(a)
aE[K]
T=h
Proof. We assume that Theorem 5.6 holds, and hence our statement holds with probability 1 6. Then, to prove the statement it is sufficient to show that
Σ
1 - (a)
Σ Σ
S
"E[K] (E OF (a)
Ttz (a)
aW[K] rETiz.an(t.taa)
Fix any a E [K], and let = [Tea n [21, be the number times action a is played in the interval [1, 12). Moreover, let r(j) be the rounds in which action is played the j-th time in the
interval [ti, t2). Then:
Σ
(0)2(()- - -o,²(a)
Nlt dol nh (a)
Σ
1
(10
(o()tt)(a)) -0 -a())(a)
1
(0))))+(a)-
960
jEIK-11 (a)
(
(a)
(
Σ
(0) (a)
(7(+1)((a)
(a)
1
(0(0))+((a)
- (a)
jelk-11
TT
(
1 (a)
(a)
(
(a)
040)41 (a)
(a)
(r( (a)
(a()(aa)
(
2
<
(T(1)(a) (a)
2
(1)
(a)
Summing over all the actions obtain the desired inequality.
17

---

Lemma 5.8. Given e > 0, an E (0, a E [T], and ó > 0, let bi(a) = m(aa for all
[K]. Then, with probability at least holds:
cr, bx)
Kayta + 4 1 tlog(1/))
Proof. Consider the following inequalities:
Σ (ar) =c E E
nr(aja I(a, ( a)
7=1
aE[K] rEld
(a(a)
Σ
c
ka
Σ ne(a)²-a
E Ekml k- S Jo x dx)
a [E[K]
Kayl-a
(Jensen's 's inequality)
The proof is concluded by using Lemma G.1.
E Proofs omitted from Section 6
Theorem 6.1. Both in the stochastic and the adversarial setting, with probability at least 22 822 holds that
V, S
Vt [T].
Proof. We prove that given an i [m], holds:
vl < 53 Ktlog(2/6)
Vt E [T]
with probability 2T 82. Then, union bound over completes the proof.
Given an i E [m]] we first assume some high- eigh-rrobbbility events. In particular, we assume that Corollary 5.7 with 8 82 holds for any interval, and that Lemma 5.8 with 8 5g holds for all [T].
This happens with probability at least 1 27. We consider two cases. ( < 53 KT log log(2/6g) for all t E [[T]], then the statement it is trivially satisfied. Otherwise, there exists
time & for
which V 2 53 (og)//))))) Clearly, this implies that there exists a f < such that V. >
42, / KT. Ktlog log(3/62) for all E [.. 7 and ((() t-1 < 42 Kt (o/))/)).. Since V(() 2 42 Kt (oglog///// for all t [t, f] we have that:
v 21 Ktlog(//.)) 2 42 KKtllgg//// 21 Ktlog((/6.) 2 21 Kttog(//á))
and thus ((() 21 / Kt log( for E f). Hence, the interval E [t, we known that the learning rate can be lower bounded by non non-increasing function of time as
1 21 (tllg(1/88)) (at)
K Klog(1/62)
21
(a))
((()))
18

---

This let us use Corollary 5.7 (that we assumed to hold) to show that:
2
nz(aa +
Cr, b,) + 4 [log(1/6))
L.
21 / K log (3bb)
aε[K]
2 2vKi
$
Σ r=t
(ET. by) + 4Vtlog(//6))
(Jensen's ' inequality)
21 K log(4/b))
Kv
+ +2/2ktlog(//6) 8 (lg((//s))
(Lemma 5.8)
21 V K log (4/b2
$ (1/10 + 10) (ttoo(?/o,).
Now, V < V (() 1.
- (42 + 1/10 + 10) / (og( < 53 Kt log(35). We thus reached
contradiction and there is such f. The union bound on all [m]] concludes the proof.
Lemma 6.2. In the stochastic setting, with probability at least 5mkTT5,, it holds that:
Ig(" (a) 9: (4) (a)) S ba(a) Ya [K], [7], E [m]
Proof. First, we show some concentration inequalities that will be useful in the following. By an Hoeffding's 's inequality and an union bound with probability at least mKT82, it holds:
1
Σ
(a)
g a <
2 log(3/6)) (a(a)
VL e [K] [m]
(10)
(a)1(a) TET--14
Moreover, by Lemma Lemma G.1 and union bound, with probability at least 1 m2'6 82. it holds:
Σ (Er, (:) + 44V/log(//)) 1I E [T]. [m]
(11)
Similarly, by Lemma Lemma G.1 and an union bound, with probability at least m2, it holds:
Σ (Cr. gf
(az) + 4 (o/loo(///z) 1i E [7].4 E [m]]
(12)
By Lemma G.2 and an union bound, with probability at least - m775g
Σ Tr
(er.g()) + 4//tlog(//b)) Vt [T] [m]
(13)
Finally, by Lemma 5.8 and an union bound, with probability 1 T82, it holds:
Σ (o, b,) (2/2/K(lo/(//b) + 4 4/
V E [T]
(14)
In the following, we will assume the the previous events hold, and hence our result holds with probability least 1 5mKT8,.
First, show that V. < 21/K's Ktt log(2/6g) for each and i. Our proof works by induction Clearly, the inequality holds for 1. Now, assume that it holds for all r S 1. By the definition of (() the induction assumption implies that 7/ (a) n.(aj for all [K]. e [m]]
and 5 1. Then, thanks to Proposition 5.4 have that:
g (a)
Σ
g (0) 5-
(15)
nl (a)
19

---

Hence, by Equation (10), it holds that:
2 210g(2/6z) (a
(c)
VT St
and thus that R o (0) for all st 1. Assuming that the events above holds, consider now the following inequalities:
vi() 1 + 9: (ac)
(4)
(or,
) (rr)g("))
+ + (a.)
(a,) + 4/tlog(//b))
(Equation (11))
1- (x ( - - +
xr b7) + 9: gt (a.) + 4v/llo(\/6))
(x, E )
(Cr, 0 ) + 2 2Kt + 00 (a.) + 8 (18()8))
(Equation (14))
(0r,0:) - / + - 21 +1+
(a) C (a) S 1)
(2r,g(") - - + 2 2kt 2Ktlog(2/b) + +1+ 12 (log(1/b))
(Equation (13))
0 (a+) (a+)
/ (a,)) + 2
12 (0g((/62)
(Equation (12))
Σ
60 (a) 0 (a)) = a) =a) 22/2Ktlog(///)) +1+ 12 (log(2/2)) 1
RE[K]
S (2log(3//2)
I(a, a) 2 2Ktlog(7/o)) + +1+ 12 1 (lo((1/b))
(a)
aE[A]
/2/2Kt (2/82) + 2 2k (3622) +1+ 12, [lo((1662
and thus v,(0) < / Kt log(3/)))
Thus 1 0 and g.
(0)( (a) is the empirical mean of past observations. This concludes the induction
step. showing that V, < 21 / Ki for all / E [T], and r(() 0 for all / E [7] and E [m]]
Now, we proved that with probability 3mkT8,, all r( 0, and hence by Equation (10) have that:
1og((3/6) (4(a)
0e (a) <
Vi [m], L [7],a a [K]
as desired,
F Proofs omitted from Section 7
Theorem 7.1. In the stochastic setting, any > 0 Algorithm 1 guarantees that with probability at least 1 c:
Kt Ri 5 K44KKllo/2K// and V. < / Ktlog(28mKTT///
Vt E [T].
Proof. To prove the upper bound on the regret, we simply have to combine Corollary 6.3 with Theorem 4.1. By Corollary 6.3 which probability at least 1 5mKT',, it holds X S &.
20

---

Moreover, by Theorem 4.1, we have that for each x E X with probability at least 1 51:
Σ
(ft.)) - f((a:) s 4v KTloog(/6.)
EE[T]
Let x" arg m ExEry (2z, fi). Then, by union bound we have that with probability least 1 5mKT6, it holds:
Σ (h,x'> fe(a.) S 4v KT (oToo/(K/))) NE[T]
proving the bound on the regret. The bound the violations holds with probability at least 1 2mTT28 by Theorem 6.1, and guarantees:
S 53
By an union bounds on all events, the guarantees hold with probability at least 7mKT 81- Thus by taking 51 s/2 and 82 =TT we obtain the desired result.
Theorem 7.2. In the adversarial setting, for any e >> O Algorithm I guarantees that with probability least
a-RT S 4v KT (og(K/)))) and V₁ S 53 Kt Kttlog(8mmK3///
vt [7].
where a = p/(L+p).
Proof. Combining Theorem 5.2 and Theorem 4.1 readily proves that with probability least 1 ò1
we have that for ã X C Lr we have:
Σ LE[T]
(f..z) - f((a)) S 4v (K/k).
Let x² arg max Everyy (a, ft). Then, observe that F 11 + 11 20 where
x (a²) = 1 and x (a) = for each a * a². Then, we have that:
Σ (1.
Σ (E[T]
1+p To + 1+p x Je 2 1 rE[T]
Σ (x),
TE[T]
since f((a 2 This proves that with probability least 87:
1+f PCr < 4v
Similarly to the proof of Theorem 7.1, we can prove that the bound on the violations holds with probability least 1 2mT2 52 by Theorem 6.1, and give:
V S 53 (oo////)..
Overall these events hold with probability least 2mI S2 8,. By defining ó 5/2 and 82 s/(1mmTT)) we have that the desired results hold with probability at least
Theorem 7.3. Algorithm 1, in the stochastic setting, guarantees that with probability at least 1 e, holds that:
V < 16 Ktlog(28mkTT//e) Vt [7].
Proof. Define for each i [m] and t [T]
Vi+
(Ir: of [(0
21

---

Then, given an i and at consider the following chain of inequalities:
Vi+
r (xr.f(1))
(f - - )
(2r, ofth - + (or, gf
(Dors (1rr, ,f
-000) + (0r,br)
(xr Rx)
(Irr sft) - -/oo (xr,
S (5r, bz)+
(Lemma 6.2)
where last inequality both hold with probability 5mKT8, jointly for each and t.
Since b, V
apply Lemma 5.8 and union bound all t to find that with probability at least 1 Tō2 - 5mkT652
2 log(3/a2) ni ((a)
D < /2 2/tKKllg(//))) + 8 tlog/////)) Vi E [m]], e [T]-
Thus, we can conclude that:
V < 16 Kt log(3/6)) vi [m]], [T]]
with probability at least - 6m Recalling that 82 s/(1mKT9) obtain the result.
G Further technical lemmas
Lemma G.1. For any sequence of function Tt [K] + sequence of randomized strategy E AR. it holds that with probability at least - 8:
[-1, which is 1 predictable and any
Σ SE[T]
Σ re(at) AE[T]
< 4 Tlog(1/8).
Proof. By definition Eø-z, [r((a]] EoE[K] (a)
(ar, rt). Thus the sequence X,
Etmir Irr and find that with probability at least -:: 6:
(a,)- (rr, rr)] is martingale and [r X,-II
Thus can apply Azuma inequality
(oa, Σ LE[T]
Σ re(as) LE[T]
< <4 Tlog(188)
Lemma G.2. For any sequence of randomized strategy E Aς and any function F(a) such that (a) are sampled from a distribution with mean F(a). i.e., Elrx(a)) = F(a) and (()r((a)) s 1) 1, it holds that with probability at least 1 8:
Σ (R)TT)) Σ (a,,7) < 4, 4/oloo/)//) FELT]
[E[T]
Proof. This holds by simple application of Azuma's inequality, similarly to the proof of Lemma G.
22

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We included the main contributions and scope in the abstract
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, the paper discusses limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

Justification:
Assumptions are explicitly discussed and all the proofs are provided.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper is theoretical and we do not have any experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
24

---

Answer:
[NA]
Justification:
The paper is theoretical and we do not have any experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https: //tp//ips.aa cc/ des /oodeSuommi ss ssion iisooooll iicy) for more details.
public / guides
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips. cc/
httpsscccppbliiii pppppcuicc../ saaicc/uuiissseeeeeeee /Codee/CC "CdeSouuuai Submi commissia ieiionnoliinn
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper is theoretical and we do not have any experimental results. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper is theoretical and we do not have any experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
25

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper is theoretical and we do not have any experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttt:::://euurri /nwurips..pp.. cc httppp/bliee/thhhccc..eee....a.a
Answer: [Yes]
Justification:
The paper conforms.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theoretical without any immediate societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
26

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No data has been used in this paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No data has been used in this paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of the package should be provided. For popular datasets, papers wwwwwwie swith com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
27

---

Answer: [NA]
Justification: No new assets have been introduced in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsoureing have been used in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing have been used in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "RFvQ1ag3U2", "reviewer": "Reviewer_Q9L2", "summary": "This paper studies multi-armed bandits with cumulative cost connstraints, with the focus of designing a 'best of both worlds' algorithm that has small constraint violations in both the stochastic and adverasarial settings (where the constraints as well as rewards can vary with time arbitrarily), and attain either low-regret for the stochastic setting, or low $alpha$-regret for the adversarial setting (i.e., ensure that the reward accrued is at least $\\alpha$ times the best-in-hindsight reward accrued by a constant unconstrained assignment probability x, up to $o(T)$ terms). The main desiderata is to design methods that avoid explicit knowledge of a slater parameter, and avoid polynomial dependence on m, the number of unknown constraints, in the regret and violations, both of which are cons of prior work using the  Langrangian BwK design.\n\nThroughout, the setup adopted is linearised, i.e., at each time, the authors select a distribution $x_t$ over the actions [1:K], and the action $a_t$ is selected by sampling from $x_t$. A bandit feedback of both the reward, $f_t(a)$, and the constaint violations $g_{t}^i(a), i \\in [1:m]$ is assumed, where these functions are stochastic perturbations of an expected function in the stochastic setting, and are selected arbitrarily in the adversarial setting. Throughout, it is assumed that $f_t \\in [0,1]$ and $g\\_t^i \\in [-1,1]$. The constraint is of the form $\\forall i, g_t^i \\le 0$, Net violations are defined as $V_T = \\max_{i} V_T^{i}, $ where $V_T^i = \\sum_t g_t^i(a_t).$ Note that this equals $\\sum_t \\langle x_t, g_t^i\\rangle,$ up to a $\\sqrt{T}$ concentration term. In the adverarial case, the paper studies the regret $\\frac{\\rho}{1+\\rho} \\max_{x} \\sum f_t(x) - \\sum f_t(a_t),$ where $\\rho$ is the minimax Slater parameter $\\rho:=  \\max_a \\min_{i,t} (-g_{t}^i(a))$. \n\nThe overall strategy adopted by the paper is very natural: for each time, the method constructs a set of \"plausibly\" feasible distributions as $\\widehat{\\mathcal{X}}\\_t = \\{x \\in \\Delta\\_K : \\forall i, \\langle x, \\hat{g}\\_t^i - b\\_t\\rangle \\le 0\\}$, where $\\hat{g}\\_t^i$ serve as \"estimates\" for $g\\_t^i,$ and $b$ is a nonnegative 'bonus' that ensures optimism in the stochastic scenario. The method then just selects actions from $\\widehat{\\mathcal{X}}\\_t$, using a (small modification of) the EXP-IX strategy, thus ensuring low regret relative to any constant $x \\in \\bigcap \\widehat{\\mathcal{X}}\\_t$. The main results then need to select $\\hat{g}_t^i$ and $b_t$ in such a way that \n\n1. In the stochastic case, $\\mathcal{X}^* = \\{x : \\forall i, \\langle \\mathbb{E}[g_t^i], x\\rangle \\le 0\\}$ remains within this intersection of $\\widehat{\\mathcal{X}}s$, and  \n2. In the adverasrial case, $\\frac{\\delta\\_{a^{\\emptyset}}}{1+\\rho} + \\frac{\\rho}{1+\\rho} \\mathcal{X}$ remains within the same.\n3. The net violation is small.\n\nAs is natural, the $b_t(a)$ is set to just $\\sqrt{ \\log(mT^2/\\delta)/n_{t}(a)},$ where $n_t(a)$ is the number of times action $a$ has been played up to time $t$. The $\\hat{g}\\_t^i$ are estimated using OGD as $$ \\hat{g}\\_{t+1}^i(a)  =  \\hat{g}\\_t^i(a)\\mathbf{1}\\{a\\_t \\neq a\\} + ( (1-\\eta\\_{t}^i(a) \\hat{g}\\_t^i(a) + \\eta\\_t^i(a) g\\_t^i(a))\\mathbf{1}\\{a\\_t = a\\}.$$ The chief question becomes how to select the learning rates $\\eta\\_t^i(a)$. The basic tension is illustrated thus: in the stochastic case, we'd like $\\eta\\_t^i$ to be roughly $1/n\\_{t}(a),$ so that $\\hat{g}\\_t^i(a)$ is essentially the empirical average of the feedback. However, in the adversarial case, such a rate would be way too slow, and one needs quicker adaptation. The authors elegantly resolve this dilemma by setting $ \\eta\\_t^{i}(a) =(1+\\Gamma\\_t^i)/n\\_t^i,$ where $$ \\Gamma\\_t^t = \\min( \\zeta\\_t , \\max( 0, V\\_t^i - \\zeta\\_t )), \\textrm{ where } \\zeta\\_t = 21\\sqrt{Kt \\log(mT^2/\\delta) }$$\n\nFor the stochastic case, the analysis directly shows that, whp, $V\\_t^i$ never crosses the $21\\sqrt{Kt}$ threshold, and thus the desired $\\eta\\_t = 1/n\\_t(a)$ is retained. For the adversarial case, the analysis proceeds by first controlling the violation over any interval in terms of the updates to $\\hat{g}\\_t$ over the same, and then arguing via contradition by showing that that if $V_\\tau/\\sqrt{K\\tau}$ is ever too large, then $\\eta_t$ is large over a significantly sized interval before it, which in turn implies strong adaptation and a small $V_\\tau$. Finally, the point 1 follows by the choice of $b_t(a) \\sim 1/\\sqrt{n\\_t(a)}$, and 2 follows directly from the boundedness of the $g\\_t^i$, by interpreting $\\hat{g}_t^i$ as a weighted sum of the observed $g\\_t^i(a_t)$s with net weight $1$.", "questions": "Comment: Comment: the roundiwse violation bound on V_T^+ of theorem 7.3 has previously been observed for the stochastic setup in the \"safe bandit\" literature, and this point of contact should perhaps be acknoweldged. See, e.g., [1,2]. The method these papers study is Agarwal and Devanur's style of \"doubly-optmistic\" selection.\n\n[1]: Chen et al., Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk, ICML 22\n[2]: Gangrade et al., Safe Linear Bandits over Unknown Polytopes, COLT 24", "limitations": "This is fine.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The subject of the paper is of course very peritnent to the online learning subcommunity at Neurips. I think the technical contribution of the paper, i.e., the design of a BOBW method for the bandits with cumulative constraints that avoids knowledge of Slater parameters is quite interesting. Furthermore, the removal of the poly(m) factors from the ensuing bounds is an important improvement in the same.\nexplained\nI find the paper to be quite well written. The thought process behind the design of the method is well explained, and the intuition behind the design of the learning rate is clear. Prior work is contextualised well, and the contribution of the paper is clearly outlined. To my understanding, the proofs are correct.\n\nThe design of the scheme, and the analysis, are simple, but well motivated and elegant. Altogether, while I don't see this paper as especially groundbreaking, I do find it to be a well executed contribution that develops a simple idea and does interesting things with it to clean up the theory of bandits with cumulative constraints.", "weaknesses": "Perhaps the main weakness is that the structure of $\\Gamma\\_t^i$ bakes in the large constant 21 (and this of course leads to the large constant 53 in the bound). I find it natural to wonder if this constant is necessary, or if can be set in a path-dependent way that avoids both the large constant, and potentially offers improvements if the $g$s are somehow 'nice'. That said, I think that such a lacuna is not a major weakness, and such questions are find being left to follow-up work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive comments about our work and for pointing out the line of research on safe bandits. We will acknowledge it in the final version of the paper. \n\nOn the constants: we didn’t try to optimize the constants as we were mainly interested in achieving asymptotically optimal regret rates. We agree that it would be interesting to explore the methodology suggested by the Reviewer; we will add it as a future research direction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uadUCuW1uG", "reviewer": "Reviewer_EcmS", "summary": "This work studies the bandit with constraints problem where the authors consider two possible settings for the constraints -- one where the constraints are stochastic, sampled i.i.d. from some unknown distribution, and one where the constraints are adversarial. The rewards are always assumed to be generated by an oblivious adversary. The authors present a novel algorithm which is able to achieve the optimal competitive ratio, up to O(\\sqrt{T}) regret in the constraints and objective, in the adversarial constraints setting and O(\\sqrt{T}) regret in the constraints and objective in the stochastic setting which is also min-max optimal.", "questions": "Is it possible to show some type of gap-dependent regret guarantees for the regret of the constraint violation using the same type of estimator? Intuitively it seems like there would still be fast enough concentration of the empirical estimator of the constraints, so that infeasible actions are eliminated quickly in case of a large gap, however, it's not completely obvious how to handle some parts of bound for V_t.", "limitations": "Limitations are appropriately addressed and there is no obvious negative societal impact as this work is theoretical.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "To the best of my knowledge the proposed algorithms and regret bounds are novel. The results are nearly min-max optimal (up to small logarithmic factors in K). The presentation of the work is overall good and there seems to be good technical novelty in developing the algorithms. The challenge in this work for achieving best of both worlds regret for the constraints is in constructing the right empirical estimators for the constraints. This is explained well in Section 6. In particular there is tension between tightly bounding V_t and having an estimator which constraints well in the stochastic setting. The main novelty seems to be the choice of adaptive step size in the definition of the empirical constraints which leads to the neat proof of Lemma 6.2 and Theorem 6.1.", "weaknesses": "I do not find any major weaknesses in this work. Perhaps the authors can do slightly better in highlighting the tension between bounding V_t and concentration of the empirical estimators. It was also not entirely clear to me what is the benefit of viewing the estimator update as a variant of gradient descent.\n\nMinor typos:\nline 517: This let us...\nline 517: The underscored t subscript is larger\nEquation 10: \\bar g^{i}a -- brackets are missing", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive comments about our paper.\n\n**On the OGD interpretation of the estimator updates:** the main benefit of viewing the update as a variant of gradient descent is that it allows us to simplify the analysis in the proofs. We will add a remark in the main paper to clarify this point. \n\n**On the instance-dependent result in the stochastic case:** Note that it is not trivial to find a good definition of “gap” in settings with long-term constraints. The presence of constraints implies that the optimal strategy may be a mixed distribution, and thus, a  “second best” arm may not exist. There are some works that try to conjugate a logarithmic dependence in $T$ with some instance-dependent quantities (see e.g. [1,2]). However, these works require strong assumptions to establish such dependencies, making this direction less explored compared to the standard MAB setting. We will add some comments about this in the final version of the paper.\n\n\n\n[1] Sankararaman, K. A., & Slivkins, A. (2021). “Bandits with knapsacks beyond the worst case.” Advances in Neural Information Processing Systems, 34, 23191-23204.\n\n[2] Li, Xiaocheng, Chunlin Sun, and Yinyu Ye. “The symmetry between arms and knapsacks: A primal-dual approach for bandits with knapsacks.” International Conference on Machine Learning. PMLR, 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QvCUTl5sMS", "reviewer": "Reviewer_EbNg", "summary": "This paper studies the problem of multi-armed bandits under long-term constraints.\nThey give an algorithm with regret and violation guarantees simultaneously for both stochastic and adversarial constraints (i.e. best-of-both-worlds guarantees).\nSpecifically, they guarantee $\\tilde{O}(\\sqrt{T})$ regret and violation under stochastic constraints (without Slater's condition), as well as $\\tilde{O}(\\sqrt{T})$ $\\alpha$-regret and violation under adversarial constraints (with Slater's condition with parameter $\\rho$ where $\\alpha=\\frac{\\rho}{\\rho +1}$).", "questions": "- Could you provide more clarification on how this setting generalizes Bandits with Knapsacks?\n- Given the references I gave, could you provide any insight on how this work contributes to this literature?", "limitations": "I did not see clear discussion of limitations. See the \"Weaknesses\" section for my discussion on limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper appears to improve on [11] in that it's regret scales logarithmic with the number of constraints and doesn't require Slater's condition for stochastic constraints.\n- The exposition is clear and there are nice insights from the theoretical results.", "weaknesses": "My main concern is that the paper is missing key literature that render the contributions rather limited.\nMore details in the following:\n- [R1] gave a similar algorithm that uses an \"optimistic set\" to overestimate the constraint and then playing regret minimizer within this set. They showed $\\tilde{O}(\\sqrt{T})$ regret and violation without Slater's condition. In light of this, it appears the only contribution is extending [R1] to adversarial costs (and more restrictive finite action set). Although useful, this result is more limited than claimed.\n- The line of literature on stochastic bandits with round-wise constraints (e.g. [R2],[R3],[R4]) is directly relavant because it considers stochastic constraints with stronger constraint satisfaction guarantees (i.e. no violation).\n- The abstract claims that their particular problem setting generalizes Bandits with Knapsacks, which is unclear to me. Without this being the case, it seems that the only improvement on the literature would be for the recent arXiv paper [11].\n\n[R1] Gangrade et al, \"Safe Linear Bandits over Unknown Polytopes\", COLT 2024 (first appeared on arXiv in 2022 as 2209.13694).\n\n[R2] Amani et al, \"Linear Stochastic Bandits Under Safety Constraints\", NeurIPS 2019.\n\n[R3] Pacchiano et al, \"Stochastic Bandits with Linear Constraints\", AISTATS 2021.\n\n[R4] Moradipari et al, \"Safe Linear Thompson Sampling With Side Information\", IEEE TSP 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback on our work.\n\n### On related works: \n\nWe will gladly include the related works highlighted by the reviewer in the final version of the paper. However, we do not consider these works to be technically very related to ours. We outline the main reasons below.\n\nFirst, we disagree with the claim that “*it appears the only contribution is extending [R1] to adversarial costs (and more restrictive finite action set). Although useful, this result is more limited than claimed.*” Indeed, it is well-known since the seminal work of Mannor et al. [1] that the adversarial setting is far more challenging than the stochastic one. We design a minimax optimal algorithm that provides optimal rates under **stochastic and adversarial** constraints. This was explicitly indicated as one **key question for the BwK set-up** in the Immorlica et al. paper [4].  \n\nThe papers pointed out by the reviewer only consider the stochastic setting, and the techniques that they propose clearly fail to carry over to the adversarial case, thereby rendering it impossible to give guarantees for BOTH stochastic & adversarial inputs. Extending the techniques of [R1] to the adversarial case is a non-trivial task, and it is unclear whether it is even feasible. In our paper, we use entirely different techniques. Therefore, we strongly disagree with characterizing our results as “*extending the results of [R1] to adversarial costs.*”\n\nEven if we just look at the stochastic setting, there are multiple points in which our work differs from the set of papers suggested by the reviewer. Some notable examples are the following: \n* [R2] provide $O(T^{2/3})$ regret guarantees in the case of unknown $\\Delta$ ($\\Delta$ in [R2] takes the role of our Slater’s parameter), while we always achieve $O(\\sqrt{T})$ regret. \n* [R3] works with stage wise constraints and thus has to assume the knowledge of a safe action.\n\nMoreover, the stage wise guarantees are not stronger than ours, since they are defined on the expected costs (expectation with respect to the environment and the inner randomization of the algorithm), while we define violations on the realizations, and thus it is clearly impossible to achieve no violations at all rounds.\n\n### On the relationship with BwK:\n\nWe omitted a formal discussion on this matter due to space constraints, but we will include it in the final version of the paper using the extra space. We extend the BwK framework along two key directions:\n1. We do not assume knowledge of Slater’s parameter. In the classical BwK framework this is assumed to be known. Indeed, assuming that you know the budget $B$ and the time horizon $T$, the per budget constraint is $cost_t \\le B/T:=\\rho$, and there is a void action which always provides a cost of zero. \n2. We can handle both positive and negative costs (some prior literature refers to this problem as bandits with knapsacks with non-monotonic resource utilization; see [2, 3]).\n\nFinally, we observe that we can implement hard constraints (i.e., no violation) by virtually augmenting the costs by $O(1/\\sqrt{T})$.\n\n### References\n\n[1] Mannor, Shie, John N. Tsitsiklis, and Jia Yuan Yu. \"Online Learning with Sample Path Constraints.\" Journal of Machine Learning Research 10.3 (2009).\n\n[2] Kumar, Raunak, and Robert Kleinberg. \"Non-monotonic resource utilization in the bandits with knapsacks problem.\" Advances in Neural Information Processing Systems 35 (2022): 19248-19259.\n\n[3] Bernasconi, M., Castiglioni, M., Celli, A., & Fusco, F. (2022). “Bandits with replenishable knapsacks: the best of both worlds.” The Twelfth International Conference on Learning Representations.\n\n[4] Immorlica, N., Sankararaman, K., Schapire, R., & Slivkins, A. (2022). “Adversarial bandits with knapsacks”. Journal of the ACM, 69(6), 1-47.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4UmtQbiNJy", "reviewer": "Reviewer_RfbD", "summary": "This article tackles the problem of multi-armed bandits with general constraints: at each time step, the learner receives a reward and $m$ costs, corresponding to $m$ independent constraints, and its goal is to maximize the reward while maintaning the cumulative cost corresponding to each constraint at a sub-linear level in the time horizon. To choose the action played at each time step (in the sense of the probability to play each arm), the authors propose an adaptation of Exp-IX, that chooses an action in an optimistic feasible set. Their main contribution consists in proving *best-of-both-worlds* guarantees for this algorithm *without knowing* a slackness parameter, usually assumed as known in the related literature. In this setting, best-of-both world guarantees consist in establishing sub-linear regret with respect to the best feasible probability on one side, and establishing simultaneously a competitive ratio determined by the slackness parameter (which is, again, not known and thus not used by the algorithm) on the other hand, if rewards are adversarial. This is the first result of this kind without knowledge of the Slater’s parameter.", "questions": "* Please elaborate on the definition of the Slater’s condition. In particular, I am interested in understanding if the definition is indeed necessary for the guarantees to hold of if it is an artifact of the analysis.\n\n* You claim that the competitive ratio matches the lower bound obtained in another paper. However, this seems inexact to me because the lower bound do not consider the same definition of the slackness parameter. I am missing something?", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "I found the paper very clear and well written. The setting and the algorithm are well presented, as well as the results. Clear intuitions are provided, especially in the presentation of the technical results.", "weaknesses": "In my opinion, there is a major issue with the results,which is that they are obtained with a modified definition of the Slater’s parameter. As stated by the authors, in the literature it is generally defined with the set of probabilities allocated to each arm, while in the paper it is defined with the arm set. While the author claim that this definition is « slightly stronger », I disagree with this claim. It seems to me that on the contrary the problem becomes much simpler if we know in advance a set of K atoms in the simplex that contain for sure a safe policy (even the safest in a sense). To me, this seems like trading a strong assumption (knowing the Slater’s parameter) by another strong assumption. This assumptions also considerably restricts the class of problems that can be considered. Furthermore, from my current understanding of the arguments it seems that the assumption is not just an artifact of the analysis and that the results would not be guaranteed to work if the infimum in the Slater’s condition was achieved by a mixed strategy.\n\nIn itself, I find the paper interesting despite this limitation, but I believe that this should be discussed more thouroughly because it reduces the potential impact of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments about the paper. \n\nWe agree that a more detailed discussion on this point is necessary and will include an extended version of our response in an additional paragraph. However, we would like to emphasize that the primary contribution of our paper is demonstrating that, perhaps surprisingly, a new and more natural **UCB-style approach** can be effectively employed in the **adversarial** BwK setup.\n\n### On Slater’s condition:\n\nFirst, we disagree with the claim that our definition of Slater’s condition “*greatly simplifies the problem*”. While, as the reviewer noted, this may facilitate the identification of a safe strategy, this aspect is not the most challenging part of the problem. Indeed, this can be easily done by simply estimating the cost of all the arms. For example, in the BwK framework, the learner knows a safe action that satisfies all the constraints at the same time, and yet many challenges remain to be addressed.\n\nOn a minor note, we point out that in the stochastic setting, Slater’s condition is not even necessary and only pertains to the adversarial setting. \n\nMoreover, we would like to highlight that our definition of Slater’s condition coincides with the one on mixed strategies in the case of a single cost/constraint.\n\nFinally, we would like to remark that in most works (e.g., in the BwK literature), it is assumed that there exists a void action that does not use resources, and hence satisfies all the constraints. This assumption is consistent with our definition.\n\n### On the lower bound:\n\nRegarding the reviewer’s second question, it is true that the paper from which we borrow the lower bound uses a different definition of Slater's parameter. However, in the instance used in the lower bound, the strategy maximizing the feasibility margin puts all the probability on a single action. We will add a remark on this point to avoid confusion. This supports our assertion that our definition of Slater’s parameter is not significantly weaker than the one commonly used in the literature.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper makes a clear contribution to bandits with cumulative constraints. It overcomes prior difficulties in obtaining BOBW results by using the existence of a safe arm (instead of a safe mixture).
The literature is not settled on a standard assumption and I ask the authors to make it very clear in the main body of the final version that this is a stronger assumption than in some of the prior work they compare themselves to.

Nonetheless, it is an assumption that is not uncommon in the literature and achieving BOBW in this regime is a novel and significant contribution. The reviewers are in agreement that the paper is well written and that the results are significant.
Decision: Accept (poster)