Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints

Authors: martino  bernasconi
matteo  castiglioni
andrea  celli
federico  fusco
†  bocconi
politecnico  di milano
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 14:56:03

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.

Main paper: 
 introduction: 
 We address the problem faced by a decision maker who aims to maximize its cumulative reward over a time horizon T , while satisfying an arbitrary set of m long-term constraints. At each round t, the learner selects an action a t from a finite set of K actions, and then observes a reward f t (a t ) and some costs g t (a t ) ∈ [-1, 1] m . The goal is to design best-of-both-worlds algorithms for this problem that perform optimally under both stochastic and adversarial constraints. We always assume rewards are 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 (BwK) [7] study the settings in which both rewards and constraints are i.i.d. and propose an UCBbased approach, combined with primal-dual method. Agrawal and Devanur [2] provide an UCB-like approach for more general rewards and costs. Immorlica et al. [21] , Kesselheim and Singla [22] analyse settings with adversarial constraints and rewards, providing a primal-dual algorithm to tackle the problem. Castiglioni et al. [15] show that a similar primal-dual approach provides best-of-bothworlds 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-worlds guarantees for bandits with constraints [16, 17, 11, 13, 10] . 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 condition) to avoid a regret of order O(T 3 /4 ) [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 a lower bound on the Slater's parameter [16, 28] . Subsequent works circumvent this assumption at the expense of strong requirements on the primal and dual regret minimizers [17, 11, 13, 1] . 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.We propose an alternative and insightful approach to design best-of-both-worlds 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 UCB-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 +1 /ρ with adversarial constraints, where ρ 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 to 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, in adversarial settings, we should assign larger weights to recent samples to address time-dependent constraints.Not only is our algorithm significantly simpler than previous approaches, with a clean and insightful analysis, but it also provides better theoretical performance than primal-dual methods. Indeed, it is the first best-of-both-worlds algorithm to provide bounds logarithmic in the number of constraints. Moreover, in stochastic settings, it is the first algorithm to provide O( √ T ) 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.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
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. 1 The agent has a set K of available actions and, at each round t ∈ T , selects a t ∈ K . The agent then observes the corresponding reward f t (a t ) ∈ [0, 1] and a cost g(i) t (a t ) ∈ [-1, 1],for each constraint i ∈ m . We define the cumulative violation of the i th constraint asV (i) T := t∈ T g (i) t (a t ), while V T := max i∈ m V (i)T is the maximum violation across all constraints. At a high level, we want to minimize the regret while keeping the violation of each constraintV (i)T sublinear in T . The focus of this paper is on handling both stochastic and adversarial constraints. Conversely, we 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. 2 In the stochastic setting, we assume that g t = {g (i) t } i∈ m is drawn i.i.d. from a fixed but unknown distribution G, and we let ḡ(i) (a) = E g∼G [g (i) (a)] be the expected cost of action a for the i th constraint. On the other hand, in the adversarial setting {g t } t∈ T is an arbitrary sequence of cost functions.Let ∆ K to be the set of discrete probability distributions over the set K . Then, at round t ∈ T , given a randomized strategyx t ∈ ∆ K , the expected learner reward is a∈ K f t (a)x t (a) = x t , f t . Similarly, x t , g (i) tdenotes the expected cost of the i th constraint. Finally, we use n t (a) to denote the number of times arm a was played up to time t, i.e., n t (a) = t τ =1 I(a τ = a). We want to design algorithms which achieve good performances in both the adversarial and the stochastic setting. As it is customary in the literature, we compare our learning algorithm with different benchmarks according to the setting.In the stochastic setting, the constraints g (i) t are i.i.d. samples with mean ḡ(i) 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 i and X as follows:X i := x ∈ ∆ K : x, ḡ(i) ≤ 0 and X := ∩ i∈ m X i .Then, we can define the stochastic baseline as:OPT S := maxx∈X t∈ Tx, f t .We naturally assume the existence of safe mixed strategies, i.e., that X = ∅. This is equivalent to assume the existence of a randomized strategy x ∅ such that x ∅ , ḡ(i) ≤ 0 for all i. Notice that this is a weaker assumption than the one commonly assumed by best-of-both-worlds algorithms in which x ∅ , ḡ(i) ≤ -ρ, where ρ is a strictly positive constant (see, e.g., [16, 11, 10] ).Adversarial Benchmark In the adversarial setting, {g t } t∈ T is an arbitrary sequence of constraints. We consider as benchmark the best unconstrained strategy:OPT A := max x∈∆ K t∈ Tx, f t .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 a competitive ratio that is optimal even for the weaker baselines commonly adopted in the literature [16, 10, 9] .Our goal is 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 R T w.r. ĝ(i) t (a) ← τ ∈Tt-1,a w (i) t,a (τ )g (i)τ (a) for all a ∈ K and i ∈ m 5:X (i) t ← {x ∈ ∆ K : x, ĝ(i) t -b t ≤ 0} 6: X t ← ∩ i∈ m X (i) t 7:Regret minimization:8: Get prediction from R on set X t : x t ← R( X t ) 9:Sample a t ∼ x t and receive {g(i) t (a t )} i∈ m and f t (a t )and specifically we require both R T and V T to be in O( √ T ) with high probability. This clearly matches the standard Ω( √ T ) lower bound that holds even without constraints [5] .In the (harder) adversarial setting, we pose the less ambitious goal of achieving a constant competitive ratio with respect to OPT A , or equivalently sublinear α-regret with constant α. Formally, given an α < 1, we define the α-regret as:α-R T = α • OPT A -t∈ T f t (a t ).As it is customary in the literature [15] , the competitive ratio α obtained by our algorithms depends on the following Slater's parameter ρ:EQUATIONThe parameter ρ is related to the existence of strictly-feasible 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 a feasible strategy we assume that ρ ≥ 0.Then, our goal is to guarantee that both V T and the α-regret, with α = ρ /ρ+1, belong to O( √ T ) with high probability. Note that this matches the lower bound of Bernasconi et al. [11] .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 a 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 on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 1 for the pseudocode. At each step t, the algorithm works in two phases: i) it estimates the feasible set, and ii) it plays a strategy in the estimated set. Each phase requires a specific ingredient:i) An estimator ĝ(i) t of the costs functions g (i)t that is used together with the optimistic bonus b t to define the estimation of the feasible set defined as X t := ∩ i∈ m X (i) t . In the stochastic case, we would like X t ⊇ X , while in the adversarial case our goal is to maintain a sequence of sets that always contains a version of the action set X , properly scaled around a ∅ (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 t ⊆ ∆ K , and then selects a strategy x t ∈ X t . We require the regret minimizer to achieve Õ( √ KT ) regret with respect to any x ∈ ∩ t∈ T X t ;In the following we define the two phases more in details. Let T t,a := {τ ≤ t : a t = a} be the set of rounds in which the algorithm plays action a. xt (a) ← x t-1 (a)e β( ft-1(a)-1) for all a ∈ K 5:x Observe f t (a t ) and set ft (a) ← 1 for all a = a t and ft (a t ) ← 1 -1-ft(at)xt(at)+γ as the weighted mean of available past observations {g(i) τ (a)} τ ∈ t-1for each actions a ∈ K and constraint i ∈ m , for some weights w (i) t,a . 3 Then, the estimates together with the optimistic bonus {b t (a)} a∈ K are used to define the moving sets X t , which are fed to the regret minimizer R which in turn selects a point x t ∈ X t .One crucial property that is required for the execution of the regret minimizer R is that all the sets X t 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 C := X t = {∅} ∀t ∈ 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 1 we left unspecified two crucial parts of our approach. The first is how to build the regret minimizer R, and the second concerns how to actually generate the sets X t , i.e., the weights w (i) t,a and the bonus b t (a). We delve into these details in Section 4 and Section 5, respectively.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to 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 to 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. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
no-regret on moving sets: 
 We describe the regret minimizer R that exhibits no-regret with respect to any x ∈ ∩ t∈ T X t . We achieve this via a 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 a randomized strategy x t ∈ ∆ K which is updated using the biased reward estimate ft (a) as in Neu [25] and then projected onto X t according to the negative entropy Bregman divergence B(x||y) = a∈ K [x(a) log ( x(a) /y(a)) -x(a) + y(a)]. We refer to Algorithm 2 for the pseudocode, and present here the main result of the Section. Theorem 4.1. Let x t be selected accordingly to Algorithm 2 run with arbitrary sequence of convex sets X t ⊆ ∆ K with γ = β 2 and β = log( K /δ 1 ). Then, with probability at least 1 -δ 1 it holds that t∈ Tf t , x -f t (a t ) ≤ 4 KT log( K /δ1), ∀x ∈ t∈ T X t .This result establishes no-regret in the case of moving sets, taking as benchmark the optimal strategy in the intersection of all sets. To exploit this result in Algorithm 1, we have to make sure that in both the stochastic and adversarial setting the intersection of the sets X t contains "good" strategies. In the stochastic setting, we show that with high probability it includes X , while, in the adversarial setting, it includes a strategy with utility ρ /1+ρ • OPT A .5 How to build the sets X tIn this section, we show how to design estimations X t of the feasible sets that, surprisingly, are effective both in stochastic and adversarial settings. Indeed, the main challenge is to design sets X t that accommodate the different requirements of the two settings. First, in Section 5.1, we discuss how to set the optimistic bonuses b t and then in Section 5.2 we focus on how to set the weights w (i) t,a . 
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 |ĝ(i) t (a) -ḡ(i) (a)| ≤ b t (a)with high probability. Indeed, this is sufficient to show that X ⊆ ∩ t∈ T X t in the stochastic setting.Theorem 5.1. Consider the stochastic setting. Given any δ > 0, let b t (a) be such that with probability at least 1 -δ it holds:|ĝ (i) t (a) -ḡ(i) (a)| ≤ b t (a) ∀t ∈ T , i ∈ m , a ∈ K .Then, it holds X ⊆ ∩ t∈ T X t with probability at least 1 -δ.Even tough it is crucial in the stochastic setting, it turns out that in the adversarial setting the optimistic bonus b t is not really needed. Indeed, as we will show in the following, we are interested in obtaining no-regret with respect to the set X ∅ which is obtained via interpolation of points in X and the strictly feasible actions a ∅ . Let x ∅ be such that x ∅ (a ∅ ) = 1 and x ∅ (a) = 0 for all a = a ∅ . Formally:EQUATIONwhere A + B is the Minkowski sum between sets and αA indicates the set that contains each element of A multiplied by α. 4 The following theorem proves that X ∅ ⊆ X t for all t.Theorem 5.2. In the adversarial setting, it holds X ∅ ⊆ X t for all t ∈ T .Notice that having no-regret with respect to the set X ∅ is not sufficient to achieve no-regret in the adversarial setting. Nonetheless, we will show that this is sufficient to guarantee no-α-regret, for α = ρ /1+ρ with respect to any strategy x ∈ ∆ K .We focus on the design of estimators ĝ(i) t that are good approximations of the real functions g (i)t . Algorithm 1 computes the estimators ĝ(i) t by using a weighted mean of all past observations:ĝ(i) t (a) = τ ∈Tt-1,a w (i) t,a (τ )g (i) τ (a) ∀t ∈ T , a ∈ K , i ∈ M .However, to simplify the exposition, we use the following equivalence between online gradient descent (OGD) on quadratic lossesĝ(i) t (a t ) → 1 2 g (i) t (a t ) - ĝ(i) t (a t ) 2and weighted means. In particular this equivalence is realized by observing that such loss has gradient g(i)t (a t ) -ĝ(i) t (a t ). Lemma 5.3. Given any sequence {y t } t∈ T such that y 1 = 0 and any sequence of learning rates {η t } t∈ T such that η 1 = 1, let {ŷ t } t∈ T be the estimator updated as:ŷt+1 = ŷt + η t (y t -ŷt ). Then, it holds that ŷt = t-1 τ =1 y τ w t (τ ) where w t (τ ) = η τ t-1 k=τ +1 (1 -η k ). Moreover, t-1 τ =1 w t (τ ) = 1 for any t ≥ 2.Clearly, in the OGD interpretation of our update, we only update ĝ(i) t (a) only when a t = a, and thus we only need to define learning rates for action a for the times t in which a t = a. Based on this observation, we are going to update ĝ(i) t (a) asĝ(i) t+1 (a t ) = ĝi t (a t ) + η (i) t (a t ) g (i) t (a t ) -ĝi t (a t ) ĝ(i) t+1 (a) = ĝ(i) t (a) ∀a = a t .Thus, given an action a ∈ K and a time t ∈ T the corresponding weights {w(i)t,a (τ )} τ ∈Tt-1,a are:w (i) t,a (τ ) = η (i) τ (a) k∈Tt-1,a:k>τ (1 -η (i) k (a)) ∀τ ∈ T t-1,aWe 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. 5Proposition 5.4. If η(i) t (a t ) = 1 nt(at) for each τ ∈ T t-1,a , then w (i) t,a (τ ) = 1 nt-1(a)and we recover the empirical mean estimator forĝ(i) t (a) = 1 nt-1(a) τ ∈Tt-1,a g (i) τ (a). Proposition 5.5. If η (i) t (a t ) = η then w (i) t,a (τ ) = η(1 -η) |{k∈Tt-1,a:k>τ }|for each τ ∈ T t-1,a and we recover an exponentially weighted average estimator for ĝ(i) t (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 to bounds the violations suffered by the algorithm. First, we define the violations in an interval [t 1 , t 2 ] := {t ∈ T : t 1 ≤ t ≤ t 2 } as:V (i) [t1,t2] = t2 t=t1 g (i) t (a t ).Then, in the following lemma we show that the violations in the interval are related to the variation of the estimates ĝ(i) t (a). Theorem 5.6. Given an interval [t 1 , t 2 ] ⊆ T , an i ∈ m , and a δ > 0, with probability at least 1 -δ it holds:V (i) [t1,t2] ≤ a∈ K τ ∈Tt 2 ,a ∩[t1,t2] 1 η (i) τ (a) ĝ(i) τ +1 (a) -ĝ(i) τ (a) + t2 τ =t1 x τ , b τ + 4 (t 2 -t 1 ) log( 1 /δ).By a simple telescoping argument, we have the following corollary, which holds whenever the learning rates are non-increasing within a time interval. Let (a, [t 1 , t 2 ]) be the last rounds in the interval [t 1 , t 2 ] in which action a is played. Corollary 5.7. Given an interval [t 1 , t 2 ] ⊆ T , a i ∈ m , and a δ > 0, assume that for any a ∈ K it holds η(i) τ (a) ≥ η (i) τ (a) ∀τ < τ ∈ T t2,a ∩ [t 1 , t 2 ].Then, with probability at least 1 -δ it holds:V (i) [t1,t2] ≤ a∈ K 2 η (i) (a,[t1,t2]) (a) + t2 τ =t1 x τ , b τ + 4 (t 2 -t 1 ) log( 1 /δ).Corollary 5.7 shows how to bound the violation as a function of the learning rates η (i) t and the bonus terms b τ . 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 a c > 0, an α ∈ (0, 1), a t ∈ T , and a δ > 0, let b t (a) = c nt(a) α for all a ∈ K . Then, with probability at least 1 -δ, it holds:t τ =1 x τ , b τ ≤ c 1 -α K α t 1-α + 4 t log( 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. 
adaptive learning rates: 
 The previous section highlights the main difficulties of obtaining best-of-both-world algorithms: we need to set the weights w(i)t,a (or equivalently -by Lemma 5.3 -the learning rates η(i)t (a t )) and the optimistic bonuses b t so that they meet, at 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) t (a t ) = 1 / √ T .With this choice, we can apply a weighted version of Azuma-Hoeffding inequality and find that |ĝ(i) t (a) -ḡ(i) (a)| ∈ O n t (a) -1 /4, with high probability. Thus, as discussed in Section 5.1, we would need to define b t (a) ∈ O n t (a) -1 /4 , which, by Corollary 5.7 and Lemma 5.8 would imply a suboptimal Õ(T 3 /4 ) rate for the violations.The second option is to set η (i) t (a t ) = 1 /nt(at). In the stochastic setting, we have an optimal rate of concentration of the terms |ĝ(i) t (a) -ḡ(i) (a)| ∈ O n t (a) -1 /2as, by Proposition 5.4, this is equivalent to 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, a learning rate of order 1 /nt(a) makes the update of the estimates too slow when the underlying constraints change, as it does happen in the adversarial setting. This trade-off forces us to employ adaptive learning rates. Our idea is to use learning rates of the order 1 /nt(a) with an adaptive multiplicative term that depends on the current violation of the constraint. Formally, we use learning rates:η (i) t (a t ) := 1 n t (a) 1 + Γ (i) t ,whereΓ (i)t is a bonus term defined as The following theorem shows that such approach guarantees O( √ KT ) violations in both adversarial and stochastic settings. Theorem 6.1. Both in the stochastic and the adversarial setting, with probability at least 1-2mT 2 δ 2 it holds thatΓ (i) t := V (i) t-1 -21 Kt log( 1 /δ2)V t ≤ 53 Kt log( 2 /δ2) ∀t ∈ T .The previous theorem shows that this choice of learning rates is sufficient to guarantee optimal bounds on the violations. However, to achieve this result we are setting b t (a) ∈ O(n t (a) -1 /2 ). As we showed in theorem 5.1, this requires a concentration on the estimates |ĝ(i) t (a) - ḡ(i) t (a)| of the same magnitude (in the stochastic setting). This is 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. Lemma 6.2. In the stochastic setting, with probability at least 1 -5mKT δ 2 , it holds that:|ĝ (i) t (a) - ḡ(i) t (a)| ≤ b t (a) ∀a ∈ K , t ∈ T , i ∈ mThe proof of the previous result relies on the fact that in the stochastic case the bonus Γ (i) t does not "kick in" ensuring that η (i) t (a) = 1 /nt(a). Thus, ĝ(i) t 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 -5mKT δ 2 , it holds that X ∈ X t for all t ∈ T . This proves that the clean event C holds with high probability, as promised in Section 3. 
putting everything together: 
 Now, we have everything in place to easily prove the our main theorems. First, we define the parameters δ 1 = δ 1 ( ) and δ 2 = δ 2 ( ) in order to guarantee that our theorems hold with probability at least 1 -. In particular, we set δ 1 ( ) = /2, where we recall that δ 1 is the parameter used to set β and γ in Algorithm 2, and δ 2 ( ) = /(14mKT 2 ), where δ 2 is used to set the optimistic bonus and learning rate of Algorithm 1.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 > 0 Algorithm 1 guarantees that with probability at least 1 -:R T ≤ 4 KT log( 2K / ) and V t ≤ 53 Kt log(28mKT 2 / ) ∀t ∈ T .Now, we turn to the adversarial setting. Theorem 6.1 guarantee O( √ T ) 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 > 0 Algorithm 1 guarantees that with probability at least 1 -:α-R T ≤ 4 KT log( 2K / ) and V t ≤ 53 Kt log(28mKT 2 / ) ∀t ∈ T ,where α = ρ /(1+ρ).Note that in both settings, the regret upper bound is of order O( √ KT ) and it is independent from the number of constraints m, while the violations are of order O( KT log(m)) and depend only logarithmically on m. This is in contrast to the other best-of-both-world algorithms for bandits with long term constraints, based on primal-dual methods, in which both the regret and the violations depends polynomially in m.Another interesting characteristic of our methodology is that we guarantee an anytime bound on the constraint violation. Indeed, this matches the guarantees provided by the most recent primal-dual methods [11, 1] that, however, require weakly-adaptive underlying regret minimizers.To conclude, we point to a nice byproduct of our analysis. In the stochastic setting, we can easily prove a sort of "convergence rate" of x t to the set X . Formally, we can prove that positive violations are bounded by O( √ Kt log m) as long as we consider expected violations. Let us define x + := max(x, 0) andV + t := max i∈ m t τ =1 x τ , ḡ(i) τ + .Then, we can state the following theorem:Theorem 7.3. Algorithm 1, in the stochastic setting, guarantees that with probability at least 1 -, it holds that:V + t ≤ 16 Kt log(28mKT 2 / ) ∀t ∈ 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 a linear number of times "close" to the set X . This is a much stronger result then just guaranteeing that V T is sublinear, as in that case it might be a linear number of times the algorithm plays "far" from X as long as it plays strictly inside of X often enough.Best-of-Both-Worlds. A long line of work has investigated Best-of-Both-Worlds 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 Θ( √ T ) regret bound that characterizes the adversarial settings [14, 4, 27, 26, 29, 30] . 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 an 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 f t as well as the g i t are drawn i.i.d. from a non-negative distribution (so that the budget available for each resource can only decrease over time) is formally introduced and solved in Badanidiyuru et al. [6] (see also its journal version [7] ). Agrawal and Devanur [2] studies a more general stochastic setting, which subsumes knapsack and exhibit optimal guarantees via optimism in the face of uncertainty [see also 3] . Moving to the adversarial BwK problem (which corresponds to our model when the g i t are all non-negative), an optimal solution is proposed in Immorlica et al. [20] [see also 21]; there, the authors propose the LagrangeBwK framework, which has a 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 a dual player, and by showing convergence to a Nash equilibrium of the expected Lagrangian game. Differently from the stochastic version, the adversarial BwK does not admit no-regret algorithms, but Θ(log T ) competitive ratio. In a subsequent work, [22] provides a new analysis obtaining a O(log m log T ) competitive ratio, which is optimal both in the time horizon T and in the number of resources m (and improves on the O(m log T ) of Immorlica et al. [20, 21] ). In the special case in which budgets are Ω(T ), Castiglioni et al. [15] further improves the competitive ratio to 1 /ρ where ρ is the per-iteration budget.More general constraints. Castiglioni et al. [15] studies a setting with general constraints, and show how to adapt the LagrangeBwK framework to obtain best-of-both-worlds 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 LagrangeBwK framework, and provides guarantees in the specific case of one budget constraint and one return-on-investments constraint.Other related works. In an effort to bridge the results for adversarial and stochastic BwK, Fikioris and Tardos [18] investigates a 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 across rounds. A similar effort is undertaken in Liu et al. [24] , that study a 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] .Theorem 4.1. Let x t be selected accordingly to Algorithm 2 run with arbitrary sequence of convex sets X t ⊆ ∆ K with γ = β 2 and β = log( K /δ 1 ). Then, with probability at least 1 -δ 1 it holds thatt∈ T f t , x -f t (a t ) ≤ 4 KT log( K /δ1), ∀x ∈ t∈ T X t .Proof. Let us define the negative entropy for a vector x ∈ R K ≥0 as:Ψ(x) := a∈ K x(a) (log(x(a)) -1)and the Bregman divergence using Ψ can be written as B(x||y) := Ψ(x) -Ψ(y) -∇Ψ(y), x -y .For the Bregman divergence it holds the following:Claim B.1 ([19]). For any z 1 , z 2 , and z 3 , it holds:B(z 1 ||z 2 ) + B(z 2 ||z 3 ) -B(z 1 ||z 3 ) = z 1 -z 2 , ∇Ψ(z 3 ) -∇Ψ(z 2 ) .Moreover, given z, define z = arg min z∈K B(z||z). Then:B(z||z ) ≤ B(z ||z) + B(z||z ) ≤ B(z||z) ∀z ∈ K.At this point, is more convenient to work with losses rather then rewards. Define t (a) := 1 -f t (a) and ˆ t (a) := 1 -ft (a). Note that:ˆ t (a) = 1 -ft (a) = 0 if a = a t 1-ft(a) xt(a)+γ if a = a t .Then, it is easy to verify that ∇Ψ(x) = log(x) in which log(x) has to be interpreted to be applied entry-wise. Simple calculations also show that β ˆ t = log(x t ) -log(x t+1 ). Thus, we can apply Claim B.1 with z 1 = x, z 2 = x t and z 3 = xt+1 and this gives us the following:EQUATIONMoreover using the second part of Claim B.1 in which z = x, z = x t , z = x, and K = X t , we can conclude that B(x||x t ) ≤ B(x||x t ). Notice that here we use x ∈ X t for each t. Then, we have the following chain of inequalities:β t∈ T x t -x, ˆ t = t∈ T B(x||x t ) + B(x t ||x t+1 ) -B(x||x t+1 ) (By Equation (3)) = B(x||x 1 ) -B(x||x T +1 ) + T -1 t=2 (B(x||x t ) -B(x||x t )) + t∈ T B(x t ||x t+1 ) ≤ B(x||x 1 ) + t∈ T B(x t ||x t+1 ) (B is non-negative and B(•||x t ) ≤ B(•||x t )) = B(x||x 1 ) + t∈ T -1 B(x t ||x t+1 )Combining the two we can find that:EQUATIONEQUATIONNow we analyze the term B(x t ||x t+1 ).B(x t ||x t+1 ) ≤ B(x t ||x t+1 ) + B(x t+1 ||x t ) = x t -xt+1 , ∇Ψ(x t ) -∇Ψ(x t+1 ) (Definition of B(•||•)) = β x t -xt+1 , ˆ t (∇Ψ(x) = log(x) and β ˆ t = log(x t ) -log(x t+1 )) = β a∈ K x t (a)(1 -e -β ˆ t(a) ) ˆ t (a) ≤ β 2 a∈ K x t (a) ˆ t (a) 2 (1 -e -x ≤ x) ≤ β 2 a∈ K 1 -f t (a) x t (a) + γ x t (a) ˆ t (a) ≤ β 2 a∈ K ˆ t (a),where, in the last inequality, we use that xt(a) /(xt(a)+γ) is at most 1. Thus, by choosing x 1 (a) = 1 /K for all a, we have that B(x||x 1 ) ≤ log(K) and thus:EQUATIONForm [25, Corollary 1] we know that with probability at least 1 -δ 1 we have:EQUATIONMoreover, it is easy to verify that:EQUATIONThe regret is with probability at least 1 -δ 1 : 6) and Equation ( 7))t∈ T [ x, f t -f t (a t )] = t∈ T [(1 -f t (a t )) -(1 -x, f t )] = t∈ T [(1 -f t (a t )) -x, ˆ t ] + t∈ T [ x, ˆ t -(1 -x, f t )] ≤ t∈ T x t -x, ˆ t + t∈ T [ x, ˆ t -(1 -x, f t )] + γ t∈ T a∈ K ˆ t (a) (Equation (8)) ≤ log(K) β + log( K /δ1) 2γ + (γ + β) t∈ T a∈ K ˆ t (a) (Equation (≤ log(K) β + log( K /δ1) 2γ + (γ + β)   t∈ T a∈ K (1 -f t (a)) + K log( K /δ1) 2γ   ≤ log(K) β + log( K /δ1) 2γ + (γ + β)KT + (γ + β)K log( K /δ1) 2γ = log(K) β + log( K /δ1) β + 2βKT + 2Klog( K /δ1)where in the last inequality we used that β = 2γ. By taking β = log( K /δ 1 )KT we obtain, that with probability at least 1 -δ 1 :t∈ T [ x, f t -f t (a t )] ≤ 4 KT log( K /δ1), as desired.C Proofs omitted from Section 5.1: How to set the optimistic bonus Theorem 5.1. Consider the stochastic setting. Given any δ > 0, let b t (a) be such that with probability at least 1 -δ it holds:|ĝ (i) t (a) -ḡ(i) (a)| ≤ b t (a) ∀t ∈ T , i ∈ m , a ∈ K .Then, it holds X ⊆ ∩ t∈ T X t with probability at least 1 -δ.Proof. In the following, we assume that the condition in the statement of the theorem holds. Hence, our result with hold with probability 1 -δ as promised. Let x ∈ X i . Consider a t ∈ T and an i ∈ m . Then, consider the following inequalities:x, ĝ(i) t = x, ĝ(i) t -ḡ(i) + x, ḡ(i) ≤ x, ĝ(i) t -ḡ(i) (x ∈ X i ) = a∈ K x(a)(ĝ (i) t (a) -ḡ(i) (a)) ≤ x, b t .Thus, x, ĝ(i) t -b t ≤ 0 which, by definition, proves that x ∈ X (i)t . This concludes the proof.Theorem 5.2. In the adversarial setting, it holds X ∅ ⊆ X t for all t ∈ T .Proof. In the adversarial setting, by Equation (1) we have thatg (i) t (a ∅ ) ≤ -ρ,for all t ∈ T and constraint i ∈ m . Moreover, for each t ∈ T , i ∈ m , and a ∈ K , it holdsĝ(i) t (a) = τ ∈Tt-1,a w (i) t,a (τ ) g (i) τ (a)and τ ∈Tt-1,a w(i) t,a (τ ) = 1.Then, for all t ∈ T and constraint i ∈ m , ĝ(i) t (a ∅ ) ≤ -ρ and ĝ(i) t (a) ≤ 1 for each a = a ∅ . 6 Thus, we can consider the following inequalities for any x ∈ X ∅ :x, ĝ(i)t = 1 1 + ρ ĝ(i) t (a ∅ ) + ρ 1 + ρ x, ĝ(i) t ≤ 1 1 + ρ (-ρ) + ρ 1 + ρ ≤ 0, thus proving that x ∈ X t .D Proofs omitted from Section 5.2: How to set the weights Lemma 5.3. Given any sequence {y t } t∈ T such that y 1 = 0 and any sequence of learning rates {η t } t∈ T such that η 1 = 1, let {ŷ t } t∈ T be the estimator updated as:ŷt+1 = ŷt + η t (y t -ŷt ).Then, it holds that ŷt =t-1 τ =1 y τ w t (τ ) where w t (τ ) = η τ t-1 k=τ +1 (1 -η k ). Moreover, t-1 τ =1 w t (τ ) = 1 for any t ≥ 2.Proof. The first part of the statement is trivial as it can be easily checked that:ŷt = t-1 τ =1 y τ η τ t-1 k=τ +1 (1 -η k ) .Then, we prove the second part of the lemma by induction on t. The base case holds trivially asw 2 (1) = η 1 = 1. Moreover, assuming t-2 τ =1 w t τ = 1, it holds: t-1 τ =1 w t (τ ) = t-2 τ =1 w t-1 (τ )(1 -η t-1 ) + w t (t -1) = (1 -η t-1 ) + η t-1 = 1,where in the second-to-last equality we use the inductive hypothesis. This concludes the proof.Proposition 5.4. If η (i) t (a t ) = 1 nt(at) for each τ ∈ T t-1,a , then w (i) t,a (τ ) = 1 nt-1(a)and we recover the empirical mean estimator forĝ(i) t (a) = 1 nt-1(a) τ ∈Tt-1,a g (i) τ (a).Proof. Consider an a ∈ K , an i ∈ m , and a t ∈ T . Then, by applying Lemma 5.3 to the set of rounds T t-1,a we have that:w (i) t,a (τ ) = 1 n τ (a) k∈Tt-1,a:k>τ 1 - 1 n k (a)∀τ ∈ T t-1,a .k∈Tt-1,a:k>τ1 - 1 n k (a) = k∈Tt-1,a:k>τ n k (a) -1 n k (a) = nt-1(a) j=nτ (a)+1 j -1 j = n τ (a) n t-1 (a) ,and thus w(i) t,a (τ ) = 1 nt-1(a), as desired.Theorem 5.6. Given an interval [t 1 , t 2 ] ⊆ T , an i ∈ m , and a δ > 0, with probability at least 1 -δ it holds:V (i) [t1,t2] ≤ a∈ K τ ∈Tt 2 ,a ∩[t1,t2] 1 η (i) τ (a) ĝ(i) τ +1 (a) -ĝ(i) τ (a) + t2 τ =t1 x τ , b τ + 4 (t 2 -t 1 ) log( 1 /δ).Proof. First, applying Lemma G.1, we have that with probability 1 -δ it holds:EQUATIONConsider the following chain of inequalities:V (i) [t1,t2] = t2 τ =t1 g (i) τ (a τ ) ≤ t2 τ =t1 g (i) τ (a τ ) - t2 τ =t1 ĝ(i) τ , x τ + t2 τ =t1 x τ , b τ (x τ ∈ X τ ) ≤ t2 τ =t1 g (i) τ (a τ ) -ĝ(i) τ (a τ ) + t2 τ =t1x τ , b τ + 4 (t 2 -t 1 ) log( 1 /δ) (Equation ( 9))= a∈ K τ ∈Tt 2 ,a ∩[t1,t2] (g (i) τ (a) -ĝ(i) τ (a)) + t2 τ =t1 x τ , b τ + 4 (t 2 -t 1 ) log( 1 /δ) = a∈ K τ ∈Tt 2 ,a ∩[t1,t2] ĝ(i) τ +1 (a) - ĝ(i) τ (a) η (i) τ (a) + t2 τ =t1 x τ , b τ + 4 (t 2 -t 1 ) log( 1 /δ),where the last equality follows by the definition of the update:ĝ(i) τ +1 (a) = 1 -η (i) τ (a) ĝ(i) τ (a) + η (i) τ (a)g (i) τ (a) for a = a τ .This concludes the proof.Corollary 5.7. Given an interval [t 1 , t 2 ] ⊆ T , a i ∈ m , and a δ > 0, assume that for any a ∈ K it holds η(i) τ (a) ≥ η (i) τ (a) ∀τ < τ ∈ T t2,a ∩ [t 1 , t 2 ].Then, with probability at least 1 -δ it holds:V (i) [t1,t2] ≤ a∈ K 2 η (i) (a,[t1,t2]) (a) + t2 τ =t1 x τ , b τ + 4 (t 2 -t 1 ) log( 1 /δ).Proof. We assume that Theorem 5.6 holds, and hence our statement holds with probability 1 -δ. Then, to prove the statement it is sufficient to show thata∈ K τ ∈Tt 2 ,a ∩[t1,t2] 1 η (i) τ (a) ĝ(i) τ +1 (a) -ĝ(i) τ (a) ≤ a∈ K τ ∈Tt 2 ,a ∩[t1,t2] 1 η (i) t2 (a).Fix any a ∈ K , and let k = |T t2,a ∩ [t 1 , t 2 ]| be the number of times action a is played in the interval [t 1 , t 2 ]. Moreover, let τ (j) be the rounds in which action a is played the j-th time in the interval [t 1 , t 2 ]. Then:EQUATIONEQUATIONη (i) τ (j) (a) ĝ(i) τ (j) (a)   + 1 η (i) τ (k) (a) ĝ(i) τ (k)+1 (a) - ĝ(i) τ (k) (a) = 1 η (i) τ (k) (a) ĝ(i) τ (k)+1 (a) - 1 η (i) τ (1) (a) ĝ(i) τ (1) (a) ≤ 2 η (i) τ (k) (a) = 2 η (i) (a,[t1,t2]) (a)Summing over all the actions we obtain the desired inequality. Lemma 5.8. Given a c > 0, an α ∈ (0, 1), a t ∈ T , and a δ > 0, let b t (a) = c nt(a) α for all a ∈ K . Then, with probability at least 1 -δ, it holds:t τ =1 x τ , b τ ≤ c 1 -α K α t 1-α + 4 t log( 1 /δ).Proof. Consider the following inequalities:t τ =1 b τ (a τ ) = c a∈ K τ ∈ t 1 n τ (a) α I(a τ = a) = c a∈ K nt(a) k=1 1 k α ≤ c 1 -α a∈ K n t (a) 1-α ( N k=1 k -α ≤ N 0 x -α dx) ≤ c 1 -α K α t 1-α (Jensen's inequality)The proof is concluded by using Lemma G.1.Theorem 6.1. Both in the stochastic and the adversarial setting, with probability at least 1-2mT 2 δ 2 it holds thatV t ≤ 53 Kt log( 2 /δ2) ∀t ∈ T .Proof. We prove that given an i ∈ m , it holds:V (i) t ≤ 53 Kt log( 2 /δ2) ∀t ∈ T with probability 1 -2T 2 δ 2 .Then, a union bound over i completes the proof.Given an i ∈ m , we first assume some high-probability events. In particular, we assume that Corollary 5.7 with δ = δ 2 holds for any interval, and that Lemma 5.8 with δ = δ 2 holds for all t ∈ T . This happens with probability at least 1-2T 2 δ 2 . We consider two cases. IfV (i) t ≤ 53 KT log( 2 /δ2) for all t ∈ T , then the statement it is trivially satisfied. Otherwise, there exists an a time t for which V (i) t ≥ 53 Kt log( 1 /δ2). Clearly, this implies that there exists a t < t such thatV (i) t ≥ 42 Kt log( 2 /δ2) for all t ∈ [t, t] and V (i) t-1 ≤ 42 Kt log( 1 /δ2). Since V (i) t ≥ 42 Kt log( 1 /δ2) for all t ∈ [t, t] we have that:V (i) t -21 Kt log( 1 /δ2) ≥ 42 Kt log( 1 /δ2) -21 Kt log( 1 /δ2) ≥ 21 Kt log( 1 /δ2) and thus Γ (i) t = 21 Kt log( 1 /δ2) for all t ∈ [t, t].Hence, on the interval t ∈ [t, t] we known that the learning rate can be lower bounded by a non-increasing function of time asη (i) t (a t ) = 1 + 21 Kt log( 1 /δ2) n t (a t ) ≥ 21 K log( 1 /δ2) n t (a t ) .This let us use Corollary 5.7 (that we assumed to hold) to show that:V (i) [t, t] ≤ 2 21 K log( 1 /δ2) a∈ K nt(a) + t τ =t x τ , b τ + 4 t log( 1 /δ2) ≤ 2 √ K t 21 K log( 1 /δ2) + t τ =t x τ , b τ + 4 t log( 1 /δ2) (Jensen's inequality) ≤ 2 √ K t 21 K log( 1 /δ2) + 2 2Kt log( 2 /δ2) + 8 t log( 1 /δ2) (Lemma 5.8) ≤ ( 1 /10 + 10) Kt log( 2 /δ2). Now, V (i) t ≤ V t + V (i) [t, t] ≤ (42 + 1 /10 + 10) Kt log( 2 /δ) < 53 Kt log( 2 /δ).We thus reached a contradiction and there is no such a t. The union bound on all i ∈ m concludes the proof. Lemma 6.2. In the stochastic setting, with probability at least 1 -5mKT δ 2 , it holds that:|ĝ (i) t (a) - ḡ(i) t (a)| ≤ b t (a) ∀a ∈ K , t ∈ T , i ∈ mProof. First, we show some concentration inequalities that will be useful in the following. By an Hoeffding's inequality and an union bound with probability at least 1 -mKT δ 2 , it holds:EQUATIONMoreover, by Lemma Lemma G.1 and an union bound, with probability at least 1 -mT δ 2 , it holds:EQUATIONSimilarly, by Lemma Lemma G.1 and an union bound, with probability at least 1 -mT δ 2 , it holds:EQUATIONBy Lemma G.2 and an union bound, with probability at least 1 -mT δ 2EQUATIONFinally, by Lemma 5.8 and an union bound, with probability 1 -T δ 2 , it holds:EQUATIONIn the following, we will assume the the previous events hold, and hence our result holds with probability at least 1 -5mKT δ 2 .First, we show that V i t ≤ 21 Kt log( 2 /δ2) for each t and i. Our proof works by induction on t. Clearly, the inequality holds for t = 1. Now, assume that it holds for all τ ≤ t -1. By the definition of Γ (i) τ , the induction assumption implies that η(i) τ (a) = 1 nτ (a)for all a ∈ K , i ∈ m and τ ≤ t -1. Then, thanks to Proposition 5.4 we have that:EQUATIONHence, by Equation (10) , it holds that:ĝ(i) τ (a) -ḡ(i) (a) ≤ 2 log( 2 /δ2) n τ (a) ∀τ ≤ t -1.and thus that X (i) τ = {∅} for all τ ≤ t -1. Assuming that the events above holds, consider now the following inequalities:V (i) t = V (i) t-1 + g (i) t (a t ) ≤ t-1 τ =1 x τ , g (i) τ + g (i) t (a t ) + 4 t log( 1 /δ2) (Equation (11)) ≤ t-1 τ =1 x τ , g (i) τ -ĝ(i) τ + t-1 τ =1 x τ , b τ + g (i) t (a t ) + 4 t log( 1 /δ2) (x τ ∈ X (i) τ ) ≤ t-1 τ =1 x τ , g (i) τ -ĝ(i) τ + 2 2Kt log( 2 /δ2) + g (i)t (a t ) + 8 t log( 1 /δ2) (Equation ( 14))≤ t-1 τ =1 x τ , g (i) τ -ĝ(i) τ + 2 2Kt log( 2 /δ2) + 1 + 8 t log( 1 /δ2) (g (i) t (a) ≤ 1) ≤ t-1 τ =1 x τ , ḡ(i) -ĝ(i) τ + 2 2Kt log( 2 /δ2) + 1 + 12 t log( 1 /δ2) (Equation (13)) ≤ t-1 τ =1 (ḡ (i) (a τ ) -ĝ(i) τ (a τ )) + 2 2Kt log( 2 /δ2) + 1 + 12 t log( 1 /δ2) (Equation (12)) = a∈ K t-1 τ =1 (ḡ (i) (a) -ĝ(i) τ (a))I(a τ = a) + 2 2Kt log( 2 /δ2) + 1 + 12 t log( 1 /δ2) ≤ 2 log( 2 /δ2) a∈ K t-1 τ =1 1 n τ (a) I(a τ = a) + 2 2Kt log( 2 /δ2) + 1 + 12 t log( 1 /δ2) ≤ 2 2Kt log( 2 /δ2) + 2 2Kt log( 2 /δ2) + 1 + 12 t log( 1 /δ2)and thusV (i) t ≤ 21 Kt log( 2 /δ2).Thus Γ (i) t = 0 and ĝ(i) t (a) is the empirical mean of past observations. This concludes the induction step, showing that V i t ≤ 21 Kt log( 1 /δ2) for all t ∈ T , and Γ (i) t = 0 for all t ∈ T and i ∈ m . Now, we proved that with probability 1 -3mKT δ 2 , all Γ (i) t = 0, and hence by Equation ( 10) we have that:ĝ(i) t (a) -ḡ(i) (a) ≤ 2 log( 2 /δ2) n t (a) ∀i ∈ m , t ∈ T , a ∈ K as desired.F Proofs omitted from Section 7Theorem 7.1. In the stochastic setting, for any > 0 Algorithm 1 guarantees that with probability at least 1 -:R T ≤ 4 KT log( 2K / ) and V t ≤ 53 Kt log(28mKT 2 / ) ∀t ∈ 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 ⊆ ∩ t∈ T X t .Moreover, by Theorem 4.1, we have that for each x ∈ X with probability at least 1 -δ 1 :t∈ T f t , x -f t (a t ) ≤ 4 KT log( K /δ1).Let x = arg max x∈X t∈ T x, f t . Then, by union bound we have that with probability at least 1 -5mKT δ 2 -δ 1 it holds:t∈ T f t , x -f t (a t ) ≤ 4 KT log( K /δ1),proving the bound on the regret. The bound on the violations holds with probability at least 1 -2mT 2 δ 2 by Theorem 6.1, and guarantees:V t ≤ 53 Kt log( 2 /δ2).By an union bounds on all events, the guarantees hold with probability at least 1 -7mKT 2 δ 2 -δ 1 . Thus by taking δ 1 = /2 and δ 2 = /(14mKT 2 ) we obtain the desired result. Theorem 7.2. In the adversarial setting, for any > 0 Algorithm 1 guarantees that with probability at least 1 -:α-R T ≤ 4 KT log( 2K / ) and V t ≤ 53 Kt log(28mKT 2 / ) ∀t ∈ T ,where α = ρ /(1+ρ).Proof. Combining Theorem 5.2 and Theorem 4.1 readily proves that with probability at least 1 -δ 1 we have that for all x ∈ X ∅ ⊆ X t , we have:t∈ T f t , x -f t (a t ) ≤ 4 KT log( K /δ1).Let x = arg max x∈∆ K t∈ T x, f t . Then, observe that x = 1 1+ρ x ∅ + ρ 1+ρ x * ∈ X ∅ , where x ∅ (a ∅ ) = 1 and x ∅ (a) = 0 for each a = a ∅ . Then, we have that:t∈ T x, f t = t∈ T 1 1 + ρ x ∅ + ρ 1 + ρ x , f t ≥ ρ 1 + ρ t∈ Tx , f t . since f t (a ∅ ) ≥ 0. This proves that with probability at least 1 -δ 1 :ρ 1+ρ -R T ≤ 4 KT log( K /δ1).Similarly to the proof of Theorem 7.1, we can prove that the bound on the violations holds with probability at least 1 -2mT 2 δ 2 by Theorem 6.1, and give:V t ≤ 53 Kt log( 2 /δ2).Overall these events hold with probability at least 1 -2mT 2 δ 2 -δ 1 . By defining δ 1 = /2 and δ 2 = /(14mKT 2 ) we have that the desired results hold with probability at least 1 -. Theorem 7.3. Algorithm 1, in the stochastic setting, guarantees that with probability at least 1 -, it holds that:V + t ≤ 16 Kt log(28mKT 2 / ) ∀t ∈ T .Proof. Define for each i ∈ m and t ∈ TV i,+ t := t τ =1 x τ , ḡ(i) τ + .Then, given an i and a t consider the following chain of inequalities:V i,+ t = t τ =1 x τ , ḡ(i) τ + = t τ =1 x τ , ḡ(i) τ -ĝ(i) τ + ĝ(i) τ + = t τ =1 x τ , ḡ(i) τ -ĝ(i) τ + x τ , ĝ(i) τ + ≤ t τ =1 x τ , ḡ(i) τ -ĝ(i) τ + x τ , b τ + (x τ ∈ X τ ) ≤ t τ =1 x τ , ḡ(i) τ -ĝ(i) τ + + x τ , b τ ] + ≤ 2 t τ =1 x τ , b τ + (Lemma 6.2)where last inequality both hold with probability 1 -5mKT δ 2 jointly for each i and t.Since b t = 2 log( 2 /δ 2 )nt-1(a) we can apply Lemma 5.8 and an union bound on all t to find that with probability at least 1 -T δ 2 -5mKT δ 2 :V i,+ t ≤ 4 2Kt log( 2 /δ2) + 8 t log( 1 /δ2) ∀i ∈ m , t ∈ T .Thus, we can conclude that:V + t ≤ 16 Kt log( 2 /δ2) ∀i ∈ m , t ∈ T with probability at least 1 -6mKT δ 2 . Recalling that δ 2 = /(14mKT 2 ) we obtain the result.Lemma G.1. For any sequence of function r t : K → [-1, 1] which is t -1 predictable and any sequence of randomized strategy x t ∈ ∆ K , it holds that with probability at least 1 -δ:t∈ T x t , r t - t∈ T r t (a t ) ≤ 4 T log( 1 /δ). Proof. By definition E a∼xt [r t (a)] = a∈ K r t (a)x t (a) = x t , r t . Thus the sequence X t = t τ =1 [r τ (a τ ) -x τ , r τ ] is a martingale and |X t -X t-1 | ≤ 2.Thus we can apply Azuma inequality and find that with probability at least 1 -δ:t∈ T x t , r t - t∈ T r t (a t ) ≤ 4 T log( 1 /δ).Lemma G.2. For any sequence of randomized strategy x t ∈ ∆ K and any function r(a) such that r t (a) are sampled from a distribution with mean r(a), i.e., E[r t (a)] = r(a) and P(|r t (a)| ≤ 1) = 1, it holds that with probability at least 1 -δ:t∈ T x t , r t - t∈ T x t , r ≤ 4 T log( 1 /δ).Proof. This holds by simple application of Azuma's inequality, similarly to the proof of Lemma G.1. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? 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 a 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 not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or 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? 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?38th Conference on Neural Information Processing Systems (NeurIPS 2024).For any N ∈ N, we use N to denote the set {1, . . . , N }.Indeed, when the constraints are stochastic, we obtain the state-of-the-art O( √ T ) regret even with adversarial rewards.If a given action has been played at least once, we require τ ∈T t-1,a w (i) t,a (τ ) = 1, i.e., that ĝ(i) t (a) is actually a weighted mean. Otherwise, the estimation is simply set to 0.Formally Minkowski sum between sets A + B is defined as A + B := {a + b : a ∈ A, b ∈ B}.The proof of the first proposition can be found in Appendix D, while the proof of the second is straightforward and thus it is omitted.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 bt. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.

Throughout, 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))$. 

The 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 

1. 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  
2. In the adverasrial case, $\frac{\delta\_{a^{\emptyset}}}{1+\rho} + \frac{\rho}{1+\rho} \mathcal{X}$ remains within the same.
3. The net violation is small.

As 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) }$$

For 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$.
strength_weakness: strength_weakness: 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.
questions: 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.

[1]: Chen et al., Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk, ICML 22
[2]: Gangrade et al., Safe Linear Bandits over Unknown Polytopes, COLT 24
limitations: limitations: This is fine.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Minor typos:
line 517: This let us...
line 517: The underscored t subscript is larger
Equation 10: \bar g^{i}a -- brackets are missing
questions: 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: Limitations are appropriately addressed and there is no obvious negative societal impact as this work is theoretical.
paper_summary: paper_summary: This paper studies the problem of multi-armed bandits under long-term constraints.
They give an algorithm with regret and violation guarantees simultaneously for both stochastic and adversarial constraints (i.e. best-of-both-worlds guarantees).
Specifically, 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}$).
strength_weakness: strength_weakness: My main concern is that the paper is missing key literature that render the contributions rather limited.
More details in the following:
- [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.
- 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).
- 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].

[R1] Gangrade et al, "Safe Linear Bandits over Unknown Polytopes", COLT 2024 (first appeared on arXiv in 2022 as 2209.13694).

[R2] Amani et al, "Linear Stochastic Bandits Under Safety Constraints", NeurIPS 2019.

[R3] Pacchiano et al, "Stochastic Bandits with Linear Constraints", AISTATS 2021.

[R4] Moradipari et al, "Safe Linear Thompson Sampling With Side Information", IEEE TSP 2021.
questions: questions: - Could you provide more clarification on how this setting generalizes Bandits with Knapsacks?
- Given the references I gave, could you provide any insight on how this work contributes to this literature?
limitations: limitations: I did not see clear discussion of limitations. See the "Weaknesses" section for my discussion on limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

In 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.
questions: 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.

* 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: limitations: N/A

Comments: title: Thank you for your response; concerns about contribution
comment: Thank you for the time dedicated to our paper. We think we have addressed all the weaknesses highlighted by the reviewer. Based on our responses, we respectfully ask the reviewer to consider adjusting their evaluation. Thank you.
Thank you for the clarifying response. I do believe that the paper makes useful contribution to the literature on best-of-both worlds guarantees in bandits with long term constraint. I am raising my score under the expectation that [R1] and [R6] are cited in reference to the conceptual similarities in algorithm design (i.e. use of "optimistic estimations" of the constraints) and the relevant results for stochastic settings. (I'm also including [R6], which was pointed out by reviewer Q9L2, as it also uses this design approach and was published back in 2022.)

[R6] Chen et al., Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk, ICML 22
Thank you very much for your response, I have no more question for now.
We thank the reviewer for the timely answer. We think the reviewer is referring to our sentence (line 71): “Moreover, in stochastic settings, it is the first algorithm to provide $\tilde O(\sqrt{T})$ regret without requiring Slater’s condition.” We acknowledge that the original statement can be misleading when taken out of context. What we intended to convey is that our algorithm is the first **best-of-both-worlds** approach that, in the stochastic case, does not require the Slater condition while still achieving $\tilde O(\sqrt{T})$ regret and constraint violations. We agree that this should have been communicated more clearly, and we are grateful to the reviewer for bringing this to our attention.

However we do not agree that our main claim is that “ this paper gives the first algorithm with regret without Slater's condition in stochastic settings”. This is not one of our primary contributions at all! Our main contribution is designing a simple and intuitive algorithm that provides best-of-both-worlds guarantees in bandits with general constraints while also being minimax optimal. This algorithm is UCB-like in the stochastic constraints case, but the reviewer's intuition that we can simply swap a UCB-like regret minimizer for stochastic rewards with an adversarial one (since we need to handle adversarial inputs) is wrong. Our algorithm indeed needs to account for the adversarial nature of the constraints, and it does so by automatically switching to alternative methods of estimating them, adjusting the computation of estimates and increasing the learning rate as needed. The techniques we developed to prove that this approach works and achieves optimal rates in adversarial and stochastic settings are far from trivial and do not rely on the techniques used in [R1]. We hope that a closer examination of our paper will convince the reviewer of this point.

We therefore propose to revise the claim in line 71 and include a discussion of the related works for the stochastic setting, as suggested by the reviewer, including but not limited to [R1] (we initially overlooked [R1] since it was only recently published at COLT 2024, but we agree that it relevant to the discussion).
Thank you for the response.

To be clear, my main concern is in the contributions of the proposed algorithm with respect to [R1], which uses a similar algorithm for the case of stochastic costs and stochastic constraints. Indeed, both algorithms "overestimate" the constraint set and then run a regret minimizer within this overestimated set. The main difference is that [R1] uses a UCB based regret minimizer (to handle the stochastic rewards), while this paper uses an adversarial bandit regret minimizer (to handle adversarial rewards). Furthermore, *[R1] gives similar regret and violation bounds ($\tilde{O}(\sqrt{T})$ regret and violation) and also doesn't require Slater's condition.* One of the main claims is that this paper gives the first algorithm with $\tilde{O}(\sqrt{T})$ regret without Slater's condition in stochastic settings, which appears to be incorrect.

As for my question about the relationship with BwK, I was more interested in how exactly this setting generalizes BwK as it wasn't immediately clear to me. I think I cleared this up by looking at prior works so this is not an issue, other than that I believe it needs to be stated more clearly.