Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
Authors: Hengquan Guo
Lingkai Zu
Xin Liu
Venue: ICML 2025 poster (2025)
Keywords: tripe-optimitistic framework
contetxual bandits
general constraints
Primary area: optimization

Abstract: We study contextual bandits with general constraints, where a learner observes contexts and aims to maximize cumulative rewards while satisfying a wide range of general constraints.
We introduce the Optimistic$^3$ framework, a novel learning and decision-making approach that integrates optimistic design into parameter learning, primal decision, and dual violation adaptation (i.e., triple-optimism), combined with an efficient primal-dual architecture. Optimistic$^3$ achieves $\tilde{O}(\sqrt{T})$ regret and constraint violation for contextual bandits with general constraints. This framework not only outperforms the state-of-the-art results that achieve $\tilde{O}(T^{\frac{3}{4}})$ guarantees when Slater's condition does not hold but also improves on previous results that achieve $\tilde{O}(\sqrt{T}/\delta)$ when Slater's condition holds ($\delta$ denotes the Slater's condition parameter), offering a $O(1/\delta)$ improvement. Note this improvement is significant because $\delta$ can be arbitrarily small when constraints are particularly challenging.
Moreover, we show that Optimistic$^3$ can be extended to classical multi-armed bandits with both stochastic and adversarial constraints, recovering the best-of-both-worlds guarantee established in the state-of-the-art works, but with significantly less computational overhead.

Orimle-Opiimistic Learning for Stochastic Contextual Bandits with General Constraints
Hengquan Guo!
Lingkai Zu
Xin Liu
Abstract
each round the learner observes context 2, E X, se- lects an action a, A, and then receives the corresponding noisy reward (2(2,, 0z) and cost (2 0z). The goal is to maximize the cumulative reward while ensuring the con- straints are satisfied. Our framework addresses a general setting where the cost functions belong to general func- tion classes and can take both positive and negative values. This flexibility allows the model to represent wide variety of constraints, such as knapsack constraints (Badanidiyuru et al., 2014; 201 8; Agrawal & Devanur, 2016; Immorlica et al., 2022), where the cost is positive and the interaction stops once the resource is depleted, replenishable Knapsacks constraints (Kumar Kleinberg, 2022; Bernasconi et al., 2024a;b), where resources may restore; faimess constraints (Li et al., 2019; Chen al., 2020; Claure al., 2020; Sinha, 2024), ensuring equitable outcomes of the decision.
We study contextual bandits with general con- straints, where learner observes contexts and aims to maximize cumulative rewards while sat- isfying wide range of general constraints. We introduce the Opt inttimist st i framework, novel learning and decision-making approach that in- tegrates optimistic design into parameter Iearn- ing, primal decision, and dual violation adapta- tion (i.e., triple-optimism), combined with an ef- ficient primal-dual architecture. Opt ipttmmio it achieves Ö(VT) regret and constraint violation for contextual bandits with general constraints. This framework not only outperforms the state- of-the-art results that achieve Ö(T guaran- tees when Slater's condition does not hold but also improves on previous results that achieve ((VT/8) when Slater's condition holds (ō de- notes the Slater's condition parameter), offering a (11/8) improvement. Note this improvement is significant because ô can be arbitrarily small when constraints are particularly challenging. More- over, we show that Optimi mi in i i can be ex- tended classical multi- bandits with both stochastic and adversarial constraints, recovering the best-of-bothh serf-bothwwwodde worlds guarantee established in the state-of- of-the-art works, but with significantly less computational overhead.
The most closely related literature on contextual bandits with general constraints is (Slivkins et al., 2023; Guo & Liu, 2024). In (Slivkins et al., 2023), the authors proposed the LagrangeCBWL.C algorithm to establish the first opti- mal O(VT/8) bounds for both regret and constraint vio- lation. Their results rely two key assumptions: (1) the existence of Slater's condition, which guarantees a strictly feasible solution, and (2) prior knowledge of Slater's con- stant 8, which quantifies the strictness of the constraints. These results were later refined by (Guo & Liu, 2024), who achieved Ô regret and violation bounds without re- quiring Slater's condition. When Slater's condition holds, their 8-agnostic algorithm achieves D(VT/5*) regret and violation, exhibiting 1/6 worse dependency compared to the full-knowledge algorithm in (Slivkins et al., 2023). The elimination of prior 5 6-knowledge represents a significant advancement, as obtaining such information is often im- practical in real-world applications. However, the Ö(T?) regret and violation bounds in (Guo & Liu, 2024) without Slater's condition remain substantially weaker than the opti- mal Ö(VT/8) bound. For the setting where constraints tight (i.e., å + O), even the Ö(VT/8) guarantee becomes problematic, incurring critical limitation both in theory and practice. A recent work by (Bernasconi et al., 2024a) shows that Ö(VT) regret and violation bounds are achievable for classical multi-armed bandits with constraints without re- quiring Slater's condition. However, their approach cannot
1. Introduction
We study contextual bandits with general constraints, a broad online learning framework that boosts a wide range of applications (e.g., online recommendation (Balakrishnan et al., 2018; Yang et al., 2020), resource constraied health- care (Tewari & Murphy, 2017; Tomkins et al., 2021)). In
'School of Information Science and Technology, ShanghaiTech University, Shanghai, China. Correspondence to: Xin Liu <li- uxin7 shanghaitech..du.....
Proceedings of the 4dnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
be extended to contextual bandits with general constraints and relies on computationally intensive safe decision set construction. This raises natural and open question:
Chzhen et al., 2024; Guo & Liu, 2025), where the inter- action terminates upon any constraint violates. For linear function classes, (Agrawal & Devanur, 2016) established the optimal theoretical guarantee of Õ((1 + (()) was achieved by (Agrawal & Devanur, 2016) for the linear fune- tion class. This result was subsequenty extended to general function classes by (Han et al., 2023; Slivkins & Foster, 2022) through the introduction of regression oracles for joint reward and cost estimation. A shared assumption across these works is the existence of null action, which ensures Slater's 's condition holds.
Is there an efficient algoritiu for contextual bandits with general constraints that can achieve the optimal Ö(VT) regret and violation without the Slater's condition?
In this paper, we provide a positive answer to this question, and make the following technical contributions: First, we introduce Opt immi stic c², framework that incorporates triple-optimistic design: optimistic estimates, optimistic pri- mal decisions, and optimistic dual updates, The key to these improvements lies in our optimistic dual design. The opti- mistic dual update able to more precisely and smoothly predict the expected violation, thus preventing overly ag- gressive decisions. The optimism in the dual design makes Opt iimmstmiii more adaptive to the constraints, enabling it to timely switch to conservative decisions when overcon- sumed costs are detected. Second, we establish the first optimal Õ(VT) regret and violation bound in the absence of Slater's condition. This not only significantly improves the saate-of-the-ane O guarantee, but also surpasses the previous best ((VT/8) bound with 1/0 improvement. The ((VT/8) guarantees require both Slater's condition and its prior knowledge of Slater's ss constant. A detailed com- parison has been shown in Table 1. Our results can be easily applied to specific types of constraints, including knapsack constraints and fairness constraints. Third, we extend our results into aumdi- bandits with both stochastic and adversarial constraints, and prove the sottoof-two-orlldd guarantee, covering the state-of-the -hr results with greater computational efficiency.
Fairness constraints have also been extensively studied in the bandit problem. One prominent notion of fairness in multi-armed bandits is the requirement that similar indi- viduals and/or groups are treated similarly, as discussed in (Dwork et al., 2012; Joseph et al., 2016; Chzhen et al., 2024). Another widely explored fairness constraint ensures that each arm receives minimum fraction of pulls, prevent- ing any arm from being disproportionately neglected (Li et al., 2019; Chen et al., 2020; Claure et al., 2020; Sinha, 2024). There are also studies on group fairness (Chohlas- Wood al., 2024; Chzhen et al., 2024), where fairness is defined by minimizing the difference in average spending across different groups. These studies design algorithms for specific constraints that incorporate faimess into the decision-making process.
In (Slivkins et al., 2023), a generalization is considered where the constraint should be satisfied in the long term, the cost can be both negative and positive, and the perfor- mance of the algorithm is evaluated through both regret and cumulative violation. They provide the first Ö(vT /8) regret and violation guarantee, which, however, relies on the assumption that Slater's is condition holds and prior knowl- edge about it is available. The first theoretical guarantee without Slater's condition is provided by (Guo & Liu, 2024), where they establish Ö(T?) regret and violation. When the Slater's condition holds, they also achieve ((VT/8²² regret and violation but do not require prior knowledge of the Slater parameter ó. In the non-context bandit problem, Ö(T3) regret and violation is also proved in (Sinha, 2024) without the Slater condition. The optimal Ö(VT) guarantee without Slater's condition in non-context bandits with con- straints is provided by (Bernasconi et al., 2024a), however, their algorithm requires constructing safe decision set for every round, suffering from high computational overhead, especially when the constraints are general and complicated. It remains open whether Õ(VT) regret and violation can be achieved with an efficient algorithm for contextual ban- dits with general constraints without Slater's condition, as addressed in this paper. A related line of work (Moradipari et al., 2021; Amani al., 2019; Khezeli & Bitar, 2020; Pacchiano et al., 2024: Gangrade et al., 2024; Chen et al., 2022a; Gangrade & Saligrama, 2025) studies stage-wise
2. Related Works
Contextual bandits extend the multi-armed bandit (MAB) framework by incorporating contextual information avail- able at the time of decision-making. In (Dudik et al., 2011; Agarwal et al., 2014), contextual bandits with classification oracles were explored, where the algorithms assume access to cost-sensitive classification oracles. To enhance computa- tional efficiency, contextual bandits with regression oracles were studied in (Foster et al., 2018; Foster & Rakhlin, 2020; Simchi-Levi & Xu, 2022), enabling more computationally efficient designs and making the approach applicable wider range of real-world problems, especially in scenarios where accessing classification oracles may not be feasible.
Contextual bandits with constraints by introducing addi- tional costs, requiring the learner to maximize cumulative reward while satisfying constraints. Initial research focused on knapsack constraints (Badanidiyuru et al., 2014; Agrawal & Devanur, 2014; Wu al., 2015; Agrawal & Devanur, 2016; Badanidiyuru et al., 2018; Sivakumar et al., 2022;
2

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
Regret/Violation (General constraint)
Regret (Knapsack constraint)
Slater's condition free/ Slater constant agnostic
Reference
Optimistic (Slivkins et al., 2023)
Ö(VT), Õ(VT)
0 (1+ (1++)VT
017)) O
0 (1+%) VV
X, x
O(Ti), O(T+)
x
v, r
(Guo & Liu, 2024)
0( o(f)
o o SIVT
X, v
(Chzhen al., 2024)
x
0 (11+ +VVT
X, X
(Guo & Liu, 2025)
x
0 (1+%) VVV
X, v
Table 1. Comparison with related works. Optimistic achieves optimal theoretical guarantee for general constraints without requiring the Slater's 's condition, significantly improving upon the Ö(T?) bound in (Guo & Liu, 2024). Even when the Slater's condition holds, our results outperform those in (Guo & Liu, 2024; Slivkins & Foster, 2022) by getting rid of the dependency on ó. Notably, our guarantees for general constraints also recover the late-of-the-ar results in (Chzhen et al., 2024; Guo & Liu, 2025). which focus on the knapsack constraints. While (Guo & Liu, 2025) further relaxes the requirement of knowing the Slater's constant assumed in (Chzhen al., 2024), it still depends on the Slater's condition, whereas our approach does not.
constraints, enforeing safety with high probability at each step. However, these methods rely on an initially known feasible action the construction of safe region in every round.
x. The goal of the learner is to design a policy to optimize the cumulative rewards while satisfying the constraints
max Σ re(ar. mi)
3. Stochastic Constrained Contextual Bandits
s.t. Σ ca ar) 00
In this section, we introduce the problem formulation and performance metric for stochastic constrained contextual bandits with general constraints.
The problem formulation in (1) is general enough to model different types of constraints, including the most common knapsack and fairness constraints:
Stochastic Constrained Contextual Bandits: We study
stochastic constrained contextual bandits denoted by {H, FJ). where X' is the context set, AA is the ac- tion set (a finite set), F is the reward function class, G the cost function class. At period f, the learner observes context Fe randomly generated from the context set X according to known probability law PP()). The learner takes action a, E A, and then receives random reward re (2,, ax) E j0, 1] and a random cost ea (2,, az) E []. Note that we consider a single constraint for ease of expo- sition, and our results are readily generalized to multiple constraints. We study a stochastic environment where the arrival of contexts i.id; the observations for rewards and costs are drawn from unknown i.i.d. distributions. We fur- ther assume key general realizability condition for the reward and cost functions (Slivkins et al., 2023; Han al., 2023; Guo & Liu, 2024; Chzhen et al., 2024).
(Replenishable) Knapsack constraints (Han et al., 2023; Slivkins et al., 2023; Chzhen et al., 2024; Bernasconi et al., 2024b): Define et (2, a) == wy (2. a) b and the constraint in (2) represents Σ w(x,,, at) S B, where B is the initial budget and b B/T is the average budget (per round). For the most classical bandit with knapsack, the cost function w, a) is non-negative, and the inter- action would stop once the budget is exhausted. When the knapsack is replenishable, the cost wr(2, a) could be both positive and negative, where a negative cost implies restoring a positive amount to the budget. The interaction would continue until the end of the time horizon T.
(Min-selection) Fairness constraints (Li et al., 2019; Chen et al., 2020; Claure et al., 2020; Sinha, 2024): Define (xx == X; I[a 1} for arm i and the constraint in (2) represents A; S Σ T(a, = i)/T, which means the learner has to choose arm at least X; faction of times, i.e., guarantee minimum selection fairness for arm i.
Assumption 3.1. There exists functions f E and g E G such that f(z, a) = (rr and g(z,a) = E (c, a))= Ve X.a A.
We detine a policy : X + A(A), which maps a context to probability simplex over action set A. Let f(x) (r)()) and g(x) (z) denote the reward vectors and the cost vectors, respectively, over the action set given the context
(Group) Fairness constraints (Chohlas- -ood et al., 2024; Chzhen et al., 2024): Define c,, a) = (g)(()) = i} - (x, a), and at- =
3

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
Ty00 (2, a) w,( (gr(()) i} for group i, where gr(ar) E [7] denotes the group index, and 7/ is the pected proportion for group i. This constraint reduces disparities in average spending among groups, thereby mitigating equity issues.
(Foster et al., 2018). Based on online learning oracles, we have optimistic learning for rewards and costs.
For completeness, we introduce key assumption, Slater's condition, used in the existing literature, and note our work does not make this assumption.
Assumption 3.3 (Slater's 's condition). There exists positive constant such that a feasible solution To to the optimiza- tion problem (3) satisfies EE| (TT. g(z))) s -6.
Regret: To define regret, we first introduce the underlying offline problem of (1)-());
max E (TT, f(xM s.t. E (T, g(x) S O.
(3)
This assumption guarantees the existence of a strictly feasi- ble solution, commonly used in constrained bandit literature (Slivkins et al., 2023; Chzhen et al., 2024; Guo & Liu, 2024; 2025). In contrast, our algorithm eliminates this require- ment entirely, and our guarantees are independent of the Slater parameter 8, which may be arbitrarily small in tightly constrained scenarios.
Note the optimal value of this offline problem serves as an upper bound the optimal value of (2), which has been proved in (Devanur et al., 201 Agrawal & Devanur, 2016; Badanidiyuru al., 2018). Let π be the solution to this offline problem and we define v" := E [(T", f(x)) as the optimal value. For any sequence of action {ar h. the corre- sponding (pseudo) regret against this baseline is
4. Triple-optimistic framework for contextual bandits with constraints
T Σ ra an)
R(T) = Tv" - E
(4)
In this section, we introduce Opt inttimiin st i learning and decision framework for contextual bandits with general con- straints This framework incorporates triple optimistic design in parameter learning, primal decision, and dual vi- olation update to achieve optimal theoretical guarantees.
Constraint Violation: The constraint violation is straight- forward to be defined as
Σ (a ai)
V(T) = E
(5)
Optimistic learning and decision framework
Note in the classical contextual bandit with knapsacks, V(T) 0 due to the "hard stopping" when the budget is exhausted.
Initialization: Q1 0, 2 2, uniform policy To, and KL divergence D1-1I-). For f ,T
Assumption 3.2. There exist online learning oracles {Ore such that the reward and cost estimators fe a) and de (ar, a) satisfy the following conditions with a high proba- bility at least 1 -
Optimistic Learning: Observe the context Tt, con- struet UCB and LCB estimators for rewards fe a) and costs Or (zz, a) from the learning oracles (O)r.-
0 s f(xx a) f(x,a) < (2,
Optimistic Decision: Construct the optimistic surro- gate function for any a E A that
8
0 g(I, a) 51(2z,) a) 22, a,p)
İ(,, a) = fe( a) (zt
(6)
where 1/72, and we have ΣTH az, ((og((max((F))1)))))))
Find the optimal policy n, for pxoplbbllisiiccellloooooooo
The above assumption defines two online regression oracles and their performance, which is common in contextual ban- dits with constraints (Foster et al., 2018; Han et al., 2023; Slivkins et al., 2023; Guo & Liu, 2024; Chzhen et al., 2024; Guo & Liu, 2025). For the (non-context) multi-armed ban- dits problem, standard UCB (LCB) estimation satisfies the constraint. If the reward and cost functions belong to the generalized linear class, the online least-square estimate oracles satisfy the assumption. When the reward and cost functions are in general class, the weighted online regres- sion estimators still satisfy the assumption, and (z, a, p) can be calculated efficiently via a binary search method
m. arg max (T,, i(x))) aD(TT
(7)
Sample an action ar Tr.
Observe Feedback: Observe noisy reward (2 at)
and cost Cx(x,, a.).
Optimistic Dual Update: Update the optimistic dual
variable Q++1 as follows:
Q1+1 (Q+ E 1 2(Te, &. (

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
aptimiisiin framework is rooted in efficient primal- dual decision-makin makiin, leveraging the power of optimism to smoothly control exploration-exploittiio tradeoff's under general constraints. It contains the key components:
contextual bandit problems. The optimistic and smooth design in primal decisions and dual updates serve as the cornerstone of this framework. By synergistically integrat- ing optimistic estimators with dual variable updates. the optimistic surrogate decision function achieves an elegant balance between reward maximization and cost constraint satisfaction. This approach not only attains optimal theo- retical guarantees without requiring Slater's condition but also demonstrates great generality achieving the best-of- both-worlds in multi-armed bandit with both stochastic and adversarial constraints (as shown in Section 7).
Optimistic Parameter Learning: Opt immmmiss st i incor- porates standard learning oracles for reward and cost func- tions as in (Slivkins et al., 2023; Chzhen al., 2024; Guo & Liu, 2024). Specifically, the algorithm leverages online regression oracles that collect historical observations of the noisy reward rx (1z, as) and cost (I dz). Using these collected samples, the algorithm constructs optimistic esti- mates of the reward and cost for the next round based on the given context, which is achieved through the UCB estimator for rewards and the LCB estimator for costs.
5. Theoretical Results
In this section, we present the theoretical performance of Opt aptimiisto imisticc in contextual bandits with general con- straints and sketch the proof. We begin by stating the main results in the following theorem, which offers a positive answer to the open question posed in the introduction.
Optimistic Primal Decision/Explorattin:: Upon the op- timistic estimators for reward and cost, the framework first constructs an optimistic surrogate function I( a). We then introduce KL divergence as regularization term to translate the surrogate function into action probabil- ity, which ensures probabilistic, smooth and efficient ex- ploration. This design differs from the "greedy" deci- sion in (Chzhen et al., 2024; Guo & Liu, 2025) and inverse-gap gap weighting exploration strategy in (Slivkins et al., 2023; Guo & Liu, 2024). Besides, the decision in (7) is very efficient because it is based on online mirror de- scent and has a closed-form Exp3 update, i.e., (=(a) = (a-1 (a (/teeaaa)/... ma-1 (a (x(z).)))
Theorem 5.1. For contextual bandits with general con- straints, Optimistic" achieves the following regret and violation:
R(T) - V()= Ö(VT).
These results demonstrate that Opt imi st ic achieves strong regret and violation bounds when Slater's condition does not hold. These results improve upon (Guo & Liu, 2024), which establishes Ö(T+) regret and violation and only improves to /8) regret and violation when Slater's 's condition holds. While their results focus on the parameter-agnostie setting, (Slivkins et al., 2023) shows that even with prior knowledge of the Slater's condition parameter, the results can only improve to Ö Õ(VT/ /8) regret and violation, still retaining a dependency on ó. In con- trast, Opt merimiiiii does not require Slater's condition and achieves a clean and elegant Ö(VT) guarantee, elimi- nating the dependency on 6, which could be small or even vanish in many real-world applications. These results can be further extended into knapsack constraints. Our results sig- nificantly advance the theoretical guarantees for contextual bandits with general constraints.
Remark 5.2.
Optimistic Violation Adaptation: Once the policy has been determined, Opt immmmiiiiii then conduct optimistic dual update on Qt, which is the key design to provide im- proved guarantee. Unlike the traditional dual updates
Q++1 -Q+ + (T., (x or (Qz + ca )+))+,
which can be interpreted as standard gradient ascent step on the dual variable, we introduce an additional correction term: E. ( & (x)) - [ ( which serves as the "momentum" " to smooth the update and accelerate convergence. The expectation E. denotes expectation over the context variable (drawn from the known context distri- bution P..)). The optimistic dual gradient ascent mitigates fluctuations in the dual variable and smooths out abrupt changes in constraint violations across rounds. Interestingly, this optimistic design enables Opt imi st. 13 to achieve the minimal violation even without Slater's condition. The current update requires knowledge of context distribution. When the context distribution is unknown, one can first esti- mate its empirical distribution and use it in the update. This would not degrade the theoretical analysis when the context distribution satisfies a certain smooth property, suggested in (Li& & Stoltz, 2022; Chen et al., 2022b).
5.1. A Unified Bound of "Regret plus Drift"
To prove our main results, we first introduce the following lemma that provides unified bound for both regret and drift, serving as key step in the proof of Theorem 5.1. We first define the historical information H4 = {xt. fc, gt. Q.}. The expectation the following lemma denotes the conditional expectation [[.) given H..
Lemma 5.3. Let He be the policy returned by (7) in
In summary, Opt imistic presents a novel framework for algorithm design and theoretical analysis in constrained
Opt imistiie Define a shift dual variable qi = Qi F.z ( ((=--,,:-1(x))) (x)) and its corresponding drift D =
5

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
(( af) We have
can obtain
BK - -TT, f(xxMM + [[A
( Te, f(xz)) + Qe (x())) (DD(=l
T
<(T - -e, ((xx)) (x g(x)))
ne,
S 21( - (x))l +E
Σ ( - -
+ ( + a || m (T)) (8)
+ +aB[D(="||T=-) [(=T||==))
Recall Ø: - Q.- - and its corresponding
+ + [x)=
drift 4, the following property holds due to the update rule of the optimistic dual
1 (R (T),) + 2
Lemma 5.6. Under the Opt imistici framework, the following inequality holds for the drift term
Remark 5.4. The above lemma provides unified bound for both the single-step regret (x* - Te. (zx)) and the single- step drift A, enabling us to analyze regret and violation simultaneously. The drift captures the stability of the dual variable, thereby reflecting the extent to which the total con- straint is violated. This lemma refines the results of (Guo & Liu, 2024) by leveraging the power of optimism, allowing us to eliminate additional trade-off parameters between re- ward and cost that could affect the efficiency of bounding the unified terms and necessitate Slater's s condition.
E2 (1)
Sq.
F. B.
(mTe Bb (x))))
Q KTTe g (z)) - (e (+)))
+ Eg (TTe Bi (z)))²
(9)
The cross term
& (z)) is chal-
lenging to analyze directly, so we introduce the following property to facilitate the analysis:
Lemma 5.7. The following inequality holds for t E [TT]
We provide a proof sketch below, with the detailed proof available in Appendix A.
F. ( 1, 80-- (x)) Bz [x:))]
Proof Sketch: To begin, we first introduce the following pushback lemma.
E2 (T (x)))) BT (x=))²
2
Ex [| g 1 - {x(()) - || - n 111 (10)
Lemma 5.5 (Pushback Property). Let II be convex set. Let function h be convex on II and Topt E II be a global minimum of h(T) + +(((I((T)))) on II. For any æ E II,
Remark 5.8. Suppose the algorithm is designed without leveraging any prior knowledge of the context distribution. In this case, the optimistic dual update takes the form
h(TTpp)) + a a: (ToppTTl 1
<h(T) + aD(= - a (Top))
Q++1 (Q, - (Te-1 10te-11/-1( ( + 2( gr (zx)))++
Pushback lemma is fundamental result in online opti- mization (Nemirovski et al., 2009; Yu et al., 2017: Wei et al., 2020), particularly when working with Bregman di- vergences (here we specify as KL divergence). This lemma originates from the strong convexity property and guaran- tees that the optimization process inherently resists devia- tions from the optimal solution, with the term aD( (T (Tpp) quantifying the magnitude of this "pushback" effect. By leveraging this property, we effectively analyze the opti- mistic decision-making process in (7).
As shown in Lemma 5.7, this update introduces the term ( - ge (xx))) which poses significant analyt- ical challenges, as it reflects the complexity of context- dependent variations. To circumvent this issue, we have to adopt the mild assumption that the context distribution is known and leverage this knowledge in the dual update. An important direction for future work is to develop tech- niques that remove the assumption of prior knowledge of the context distribution.
With the above two lemmas, 24 and substitute (9) and (10) into (8), which gives
take expectation w.r.t.
Let /T))) = (- -,, fx(xx))
(xx)) according to the optimistic decision in (7), we have Topt = Te. Therefore, we can apply Lemma 5.5 to get that for any policy æ E IT,
(n - ne, E, [f(x)))) + +
(Tr-1 - ne, (xx)) + Qr (. + aD(Tal(=-
<(n" - ne, B2 (xx)) - (x())))) + E2 (Q( ()(())))))) - -(x))))
+ a aDD( (T((T"((TT)))) ( axD(
(. {x)
<(T - 7, (x.)) + (T + (D(
-aD(m (T|| (e))
B. - (
-
2
Let π = n" and add (TT Tt-1, ((xz)) on both sides, we
+ .| - - Il2 aD (- + R. [((r,,
6

---

Triplc-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
For the last term, we have Eg ( g(x)))] cording to the definition of x². Then it remains prove
bounds for each component, we can easily derive:
T
||T, TT- Ili 11lf-aD(mm aD(TTilTTT I O, for which the following
E
((D(
((a" Ö(1),
lemma holds:
Lemma 5.9 (Pinsker's inequality). Let ie and Tt-1 be two probability distributions over action set A and - be KL Divergence, we have
T
I (iT,, Br (x)))
E [ gi- 11-1(1)))1 =O(1,
2
2
- S (
-
Finally, for the terms in (12), we have
Applying Pinsker's inequality and recalling 2 2, then we can take the expectation w.r.t. the remaining terms in H4 to complete the proof. We might also consider alterna- tive generating functions in the Bregman divergence, which yield properties similar to Pinsker's inequality and obtain the same guarantees in Theorem 5.1. This might require selecting an appropriate learning rate a in our algorithm such that the key Lemma 5.3 holds.
g (x) - {x))1
T
T
g (x) -(xx))}
+E
Σ
[x(x) - g(x)
<2
|,, a. p)1 = Ö())
where the last inequality holds due to the learning oracle assumption. Combining all these terms, we prove the upper bound of regret such that R(T)) = Ö(VT). Please refer to Appendix B.1 for the detailed proof.
5.2. Regret analysis
To establish the regret bound, we first sum the inequality in Lemma 5.3 to get
5.3. Violation analysis
T
T
E
Σ (T" ne, f(x)))
+E
Σ
A
To establish the cumulative violation guarantee, we first need to analyze the relationship between violation and dual variable. According the update rule of Qe, we have
T
T
<B
[f(z;) f((x))1l + Σ Q ,r(())))))))))))))))))))))))), - g(z,))
Q+1 2 Q 1 (+)) + ( (x))))
T
(11) Summing the above inequality over T rounds and taking expectation, we can obtain that:
+ E
a(D(T")|T<>)) - D(T (I(
+ E
Σ
(x) {1))
(12)
E
Σ Te. (i()) < S @T +
E [ (x)))
E ( 1x:)))
This demonstrates that the expected estimated cumulative violation can be upper bounded by the "dual" term 9r+1-
2
2
(13)
Then we can prove the constraint violation through the fol- lowing decomposition:
The first two terms denote the learning errors of reward and cost functions, for which we have the following upper bound due to our learning oracle assumptions.
T
T
V(T)
=E
Te g(x) -B((z))
+ E
Σ
(me, 8
(z))
T
<E
(g(a) - Bx)3)] + + +
(14)
E
[lf(ar) f((2))) Ö((T))
where we can complete the proof by analyzing the cumu- lative learning error and the upper bound of ęr. Recall in Section 5.2, we have proved unified bound for regret plus drift, which gives
T
E
Σ Qm .g(())))))))))))))))())))))))( - g(xe)) ò(1),
where the last one holds since we have Q(t) < 2T from the update rule of the dual variable.
T
E
Σ (n
ne, f(x())
+E
Σ A
Ö(VT),
From the telescoping nature of (11) and (13) and the upper
7

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
substitute the definition of drift, recall Q1 and rearrange the inequality, can obtain
The regret bound holds for a universal budget regime where B 2(1) without assuming Slater's condition the information of Slater's constant. This greatly improves upon the state-of-the the-the-rtt in (Chzhen et al., 2024; Guo & Liu, 2025), where guarantees are limited to a small-budget regime B = S2( D(VT), with (Chzhen et al., 2024) additionally requiring explicit knowledge of Slater's condition.
+ 2
E
=Ö(VT) E
Σ T n² n, f(xs))
<Ō(VT)+ +T,
where the last inequality holds due to the bound of the reward function. Finally, we show that qr-1 = Ö(VT), we then prove the constraint violation by substituting into
7. Optimistic' for MAB with Stochastic and Adversarial Constraints
(14).
A very recent paper (Bernasooni et al., 2024a) studied clas- sical (non-contextual) multi-armed bandits (MAB) with stochastic and adversarial constraints, which achieve "best- of-two-worlds" guarantees by constructing the feasible set through adaptive weighted estimates. Interestingly. they also establish an optimal Ö(VT) regret guarantee without Slater's ' condition under the stochastic setting. We also il- lustrate Opt iimmsiii it can be readily generalized to MAB with both stochastic and adversarial constraints and recover the "best-of- www.oo-wwowoodss results with a much less computa- tional overhead as Opt immistiii has gradient-tyn ttype deci- sion while (Bernasconi et al., 2024a) requires solving linear programming for each round.
6. Optimistic' for CBwK
This section instantiates Opt apttmiiti"" stice for contextual ban- dits with knapsack constraints and shows how the theoret- ical guarantee in Theorem 5.1 can be translated into the knapsack constraints with "hard-stopping".. Intuitively, the constraint violation is a proxy for the early stopping and will be accounted for regret.
For the knapsack constraints, we have ca( as) (x ax) and Ei= we (24,, a4) S B. The regret def- inition is the same as in (4). To present our results, we first define the stopping time under our algorithm, where T arg (i Ei=1 w(Er, ar) 2 B}. We then de- couple the regret as follows
In MAB with stochastic and adversarial constraints, at time i, the learner chooses an arm at E A and receives re- ward r. (ax) and a cost (a()). Similar (Bernasconi et al., 2024a), we consider the reward to be arbitrary and adver- sarial. Then the cost functions are the key to dividing this problem.
re (e( ail)
RTT) = E
Σ
+ (T - +) -T)
The first term represents the "regret before stopping" and can be bounded using our regret analysis of contextual ban- dits with general constraints, i.e., R(T). Specifically, it is bounded by Ö(VF) = Ö(VT) in Theorem 5.1.
Stochastic Setting. The cost at each round is indepen- dently drawn from an i.i.d. distribution with expected value c(a) = E[e, Va E A, E [T]. The baseline is defined as the best fixed policy that satisfies the constraints in expec- tation. Consequently, the definitions of regret and constraint violation remain the same those in the main text, with the slight modification that the contexts are omitted.
The second term, (T - F)=" represents the "regret after stopping." " and its upper bound can be determined by ana- lyzing the upper bound of the constraint violation. From immediately have E (w,, dz) b)] = Ö(VT), in conjunction with the definition of stopping time, we know satis- fies Õ(vT) + rb 2 B = Tb, which establish that T --r= == (b)T/b) such that
the violation bound in Theorem 5.1,
Adversarial Setting. The cost sequence {c+} can arbitrary. As the baseline, we consider the best unconstrained policy:
Tddo arg max Σ (T)
In this more challenging setting, as a sublinear regret re- sult is impossible (Immorlica et al., 2022; Castiglioni et al., 2022), we aim for less ambitious objective: achieving constant competitive ratio with respect to OPT
E[[T - - (F=
These results are summarized in the following theorem, and its proof can be found in Appendix C.
Σ -t=1 (TT a rt)). the cumulative reward of the unconstrained optimal policy. Formally, given the competitive ratio 3 S 1. we establish the following 8-regret as:
Theorem 6.1. For contextual bandits with knapsack con- straints, Opt iotim mi st i achieves the regret that
T Σ
R((T) -
-01+
1 b
[-R(T) = B OPT ade E
re(ai)
8

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
The definition of violation remains unchanged.
In the stochastic setting. (Bernasconi et al., 2024a) also achieves the optimal O(vT) regret and violation with- out Slater's condition. result that is, of course, covered by our work. In the adversarial setting, their analysis further requires Slater's condition to hold, where p :- innfaeA maX (a) is the Slater constant. They con- sider the competitive ratio be p/(1+ and achieve O(VT) regret and violation. To achieve these "best-of-twer worlds" guarantees, they estimate the cost function using a weighted average of past observations combined with an optimistic bonus. They adaptively design the weights based on the current level of constraint violation, allowing the estimates to accommodate the differing requirements of stochastic and adversarial constraints. However, the algo- rithm proposed in Bernasconi et al. (2024a) incurs additional computational overhead, as it constructs feasible set using estimated costs and solves constrained optimization prob- lem at each round. Next, we will show that Optim stic can recover their performance guarantees while retaining a gradient-based update scheme to ensure computational efficiency.
0.26
LagrangetBWLc
Optimicttc'
Averaged Reward
0.22
0.20
0.18
0.16
0.12
1000
2000
3000
4000
5000
0.4
LOE2b
LagrangeCTMtcc
Optimieii"*
Averaged Violation
0.3
1000
2000
3000
4000
5000
Figure 1. Averaged reward and constraint violation under I.0E2D, LagrangeCBwLC and Opt imi imistic".
To apply Optimistic to this problem, only need to modify the optimistic learning components for the re- ward and constraint functions. Specifically, to handle ad- versarial rewards, we can use standard EXP3-style esti- mators. To accommodate both stochastic and adversarial constraints, we adopt the adaptive weighted estimator pro- posed in (Bernasconi al., 2024a). The details of the ppttimiste i c algorithm for MAB with stochastic and adversarial constraints are provided in the Appendix D. For this problem, we have the following guarantee:
8. Experiments
In this section, conduct experiments using the large-scale teaning-too-rank dataset Microsoft MSLR- WFB30k (Qin & Liu, 2013). We adopt similar general constraint setting as (Guo & Liu, 2024), where the reward function r(x, a) corresponds to the relevance score (normalized to [0, 1) assigned to the recommended document and the incoming customer. The cost c(x, a) for each arm is randomly gener- ated from uniform distribution over [-0.5, 1] and remains fixed throughout each trial. We employ gradient-boosted tree regression and the empirical mean to estimate reward and cost functions, respectively. Observations of rewards and costs are perturbed by Gaussian noise (0, 0.05). The reported experimental results are averaged over 50 trials, with 95% confidence interval. Figure 1 demonstrates that Opt i m mistic a outperforms both L.FE2D (Guo & Liu, 2024) and LagrangeCBwl (Slivkins al., 2023), which verifies our theoretical results.
Theorem 7.1. For MAB with stochastic and adversarial constraints, Opt imi imistiii stis for stochastic constraints
d achieves the following results
R(T)= =(T)) V(T) Ö(VT),
and for adversarial constraints with 3 p1 + p), under the Slater's condition, Optimistion achieves
(R(()=O(VV]) V(T) - Ö(VT)
9. Conclusion
The above theorem shows that Optimiste achieves optimal Ö(VT)) regret and violation in the stochastic set- ting without assuming Slater's condition. For adversar- ial constraints, let condition, Optimi iniimiise iistiic achieves Ö(VT) ß-regret and violation. These results match the fbest-of-both-worll guarantees established in (Bernasconi et al., 2024a), while Optimis 3 achieves these results with significantly less computational overhead.
In this paper. we propose optimal framework for contextual bandits with general con- straints. Optimissto it significantly improves the theoret- ical guarantees in the setting where Slater's 's condition does not hold. Furthermore, we demonstrate that these results can extended to the non-contextual MAB setting, achieving the best-of- both guarantee for MAB with stochastic and adversarial constraints.
an efficient and
p1 + p): under the Slater's

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
Acknowledgments
Castiglioni, M., Celli, A., Marchesi, A., Romano, G., and Gatti, N. A unifying framework for online optimization with long-term constraints. Advances in Neural Informa- tion Processing Systems, 35:33589 -33822 2022.
This work was supported by the National Natural Science Foundation of China under Grant 62302305 and the Core Facility Platform of Computer Science and Communication, SIST, ShanghaiTech University.
Chen, T., Gangrade, A., and Saligrama, V. Strategies for safe multi-armed bandits with logarithmic regret and risk. In International Conference on Machine Learning, pp. 3123-3144 PMLR, 2022a.
Impact Statement
This paper presents work whose goal is to advance the field of Optimization. There are many potential societal conse- quences of our work, none which we feel must be specifi- cally highlighted here.
Chen, Y. Cuellar, A., Luo, H., Modi, J., Nemlekar, H., and Nikolaidis, S. Fair contextual multi-armed bandits: Theory and experiments. In Conference on Uncertainty in Artificial Intelligence, pp. 181-190. PMLR, 2020.
References
Chen, Z., Ai, R., Yang, M., Pan, Y., Wang, C., and Deng, X. Contextual decision-making with knapsacks beyond the worst case. In The T'hirty-iigtt Annual Conference on Neural Information Processing Systems, 2022b.
Agarwal, A., Hsu, D., Kale, S., Langford, J., Li, L.,, and Schapire, R. Taming the monster: A fast and simple algo- rithm for contextual bandits. In International Conference on Machine Learning, pp. 1638-1646. PMLR, 2014.
Mhohlas-Woode A., Coots, M., Zhu, H., Brunskill, E., and Goel, S. Learning be fair: A consequentialist ap- proach to equitable decision making. Management Sci- ence, 2024.
Agrawal, S. and Devanur, N. Linear contextual bandits with knapsacks. Advances in Neural Information Processing Systems, 29, 2016.
Agrawal, S. and Devanur, N. R. Bandits with concave rewards and convex knapsacks. In Proceedings of the fifteenth ACM conference on Economics and computation, pp. 989-1006, 2014.
Chzhen, E., Giraud, C., Li, Z., and Stoltz, G. Small total- cost constraints in contextual bandits with knapsacks, with application fairness. Advances in Neural Informa- tion Processing Systems, 36, 2024.
Amani, S., Alizadeh, M., and Thrampoulidis, C. Linear stochastic bandits under safety constraints. Advances in Neural Information Processing Systems, 32, 2019.
Claure, H., Chen, Y., Modi, J., Jung, M., and Nikolaidis, S. Multi-armed bandits with faimeess constraints for dis- tributing resources to human teammates. In Proceed- ings of the 2020 ACM/IEEE International Conference on Human-Roud Robot Interaction, pp. 299-308, 2020.
Badanidiyuru, A., Langford, J., and Slivkins, A. Resource- ful contextual bandits. In Conference on Learning Theory, pp. 1109-1134. PMLR, 2014.
Devanur, N. R., Jain, K., Sivan, B., and Wilkens, C. A. Near optimal online algorithms and fast approximation algo- rithms for resource allocation problems. I Proceedings of the 12th ACM conference on Electronic commerce, pp. 29-38, 2011.
Badanidiyuru, A., Kleinberg, R., and Slivkins, A. Bandits with knapsacks. Journal of the ACM (JACM), 65(3):1555, 2018.
Balakrishnan, A., Bouneffouf, D., Mattei, N., and Rossi, F. Using contextual bandits with behavioral constraints for constrained online movie recommendation. In Pro- ceedings of the 27th International Joint Conference Artificial Intelligence, pp. 5802-5804, 2018
Dudik, M., Hsu, D.,, Kale, S., Karampatziakis, N., Langford, J., Reyzin, L., and Zhang. T. Efficient optimal learning for contextual bandits. In Proceedings of the SSeenth Conference on Uncertainty in Artificial Intelligence, pp. 169-178. AUAI Press, 2011 ISBN 9780974903972..
Bernasconi, M., Castiglioni, M., Celli, A., and Fusco, F. Be- yond primal-dual methods in bandits with stochastic and adversarial constraints. arXiv preprint arXiv:2405.100 18, 2024a.
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 214-226,62221222 2012.
Bernasconi, M.. Castiglioni, M., Celli, A., and Fusco, F. Bandits with replenishable knapsacks: the best of both worlds. In The Twelfth International Conference on Learning Representations, 2024b.
Foster, D. and Rakhlin, A. Beyond ucb: Optimal and ef- ficient contextual bandits with regression oracles. In International Conference on Machine Learning, pp. 3199- 3210. PMLR, 2020.
10

---

Triplc-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
Foster, D., Agarwal, A., Dudík, M., Luo, H., and Schapire, R. Practical contextual bandits with regression oracles. In International Conference Machine Learning, pp. 1539- 1548. PMLR, 2018.
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Ro- bust stochastic approximation approach stochastic pro- gramming. SIAM Journal optimization, 19(4):1574- 1609, 2009.
Gangrade, A. and Saligrama, V. Constrained linear thomp- son sampling, arXiv preprint arXiv:2503.0204 020043333 2025.
Pacchiano, A., Ghavamzadeh, M., and Bartlett, P. Contex- tual bandits with stage-wise constraints. arXiv preprint arXiv:2401.004 08016, 2024.
Gangrade, A., Chen, T., and Saligrama, V. Safe linear bandits over unknown polytopes. In The Thirty Seventh Annual Conference on Learning Theory, pp. 1755-1795. PMLR, 2024.
Qin, T. and Liu, T. Introducing LETOR 4.0 datasets. CoRR, 2013. URL http:///axxv..r
abs/ Abs/1306.2599
Guo, H. and Liu, X. Stochastic constrained contextual bandits via ыyаршnov optimization based estimation to de- cision framework. In The Thirly Seventh Annual Confer- ence on Learning Theory, pp. 2200-2202222 1. PMLR, 2024.
Simchi-Levi, D. and Xu, Y. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits un- der realizability. Mathematics of Operations Research, 47(3):1904-199 1931, 2022.
Guo, H. and Liu, X. On stochastic contextual bandits with knapsacks in small budget regime. In Proceedings of the International Conference on Learning Representations, 2025.
Sinha, A. Banditq: Fair bandits with guaranteed rewards. In The 40th Conference on Uncertainty in Artificial Intel- ligence, 2024.
Sivakumar, V., Zuo, S., and Banerjee, A. Smoothed adver- sarial linear contextual bandits with knapsacks. In Inter- national Conference on Machine Learning, pp. 20253- 20277. PMLR, 2022.
Han, Y., Zeng. J., Wang, Y., Xiang, Y., and Zhang. J. Opti- mal contextual bandits with knapsacks under realizability via regression oracles. In International Conference on Ar- tificial Intelligence and Statistics, pp. 501 1-5355. PMLR, 2023.
Slivkins, A. and Foster, D. J. Efficient contextual ban- dits with knapsacks via regression. arXiv preprint arXiv:2211.077 1..04484, 2022.
Immorlica, N., Sankararaman, K. Schapire, R., and Slivkins, A. Adversarial bandits with knapsacks. Journal of the ACM, 69(6):1-47, 2022.
Slivkins, A., Sankararaman, K. A., and Foster, D. J. Con- textual bandits with packing and covering constraints: modular lagrangian approach via regression. In Annual Conference Computational Learning l'heory, 2023.
Joseph, M., Kearns, M.. Morgenstem, J. H., and Roth, A. Faimess in learning: Classic and contextual bandits. Advances in neural information processing systems, 29, 2016.
Sun, W., Dey, D., and Kapoor, A. Safety-aware algorithms for adversarial contextual bandit. In International Con- ference Machine Learning, pp. 2017.
Khezeli, K. and Bitar, E. Safe linear stochastic bandits. In Proceedings of the AAAI Conference Artificial Intelli- gence, 2020.
PMLR,
Tewari, A. and Murphy, S. A. From ads interventions: Contextual bandits in mobile health. Mobile health: sen- sors, analytic methods, and applications, pp. 495-517, 2017.
Kumar, R. and Kleinberg, R. Non-monotonic resource utilization in the bandits with knapsacks problem. Ad- vances in Neural Information Processing Systems, 35: 19248-19259, 2022.
Tomkins, S., Liao, P., Klasnja, P., and Murphy, S. Intelli- gentpooling: Practical thompson sampling for mhealth. Machine learning, 1689))2685-2227, 2021.
Li, F., Liu, J., and Ji, B. Combinatorial sleeping bandits with fairness constraints. IEEE Transactions on Network Science and Engineering, 7(3):1799-188 1813, 2019.
Wei, X., Yu, H., and Neely, M. J. Online primal-dual mir- ror descent under stochastic constraints. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(2):1-36, 2020.
Li, Z. and Stoltz, G. Contextual bandits with knapsacks for a conversion model. Advances in Newral Information Processing Systems, 25:35590-35600 2022.
Moradipari, A., Amani, S.. Alizadeh, M., and Thram- poulidis, C. Safe linear thompson sampling with side information. IEEE Transactions on Signal Processing, 69:3755-3767 2021.
Wu, H., Srikant, R., Liu, X., and Jiang, C. Algorithms with logarithmic or sublinear regret for constrained contextual bandits. Advances in Neural Information Processing Systems, 28, 2015.

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
Yang, M., Li, Q.. Qin, Z., and Ye, J. Hierarchical adaptive contextual bandits for resource constraint based recom- mendation. In Proceedings of the web conference 2020, pp. 292-302, 2020.
Yu, H., Neely, M. J., and Wei, X. Online convex opti- mization with stochastic constraints. In Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017.
12

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
A. Proof of the key property in Lemma 5.3
In this section, we provide detailed proof Lemma 5.3, which provides a unified bound for both regret and violation. begin by establishing the following pushback property (for detailed discussion and analysis, we refer the reader to (Wei al., 2020), which provides the first proof of the general pushback lemma).
Lemma A.I (Restatement of Lemma 5.5). Let X be convex set. Let function h be convex II, and let Topt II be global minimum of h(m) + D( II. Then, for any π E II, we have:
hopp))) + a (TT- S h(T) aD(T - (
Proof. Due to the definition of Tapt, we have
Vh((Fopt) + (To((Top O,
A standard "three-point" expansion of the second bracket shows
( [T-1) - (Fop T(-1) = (Tpp( (TDpl (Toppp/((T---1) π -Topt):
Recall (Topt) + V oppt 1-- 0, then can get
(h(T) h(TTpt))))))))))))))(()()))))( + al D (e-1) (Top ( =(h(T) - h((Topt) - (Vh(Tope)) π Topp)) + (T(pp
(=
Rearranging the above inequality, complete the proof.
We consider the case conditioned on the historical information H4. Then, we can apply the pushback lemma to our decision which implies that for any policy II:
process in (7), where (TT)) (TT-1 n. (zx))
(T fz.))( Q +D(==l
S(m - т. (x))) (e( (x,)) + + aD(()())
Let = x² and add - Tt-1 f f(r:)) on both sides, obtain
(T" T2, f(x,)) + Q (m & (ar) + +aD(m[lTT)))
S(mT" f(x) f (zt)) Q (x))) - g(x))) + (o(r".((()))) + aD(="||<(-) aD(T" [|T)).
To address the term Qe ği (xx)), recall that q: (T.- (x))), and the corresponding drift is A, 22 o2 For the drift term, the following property holds: Lemma A.2 (Restatement of Lemma 5.6). Under the Opt Optimime.... intiiimiiiiio... e framework, the following inequality holds for the drift term
2
Ex [A]] Sq. (iTe, (x)M) E. l (
1E (x))] - E,
(x))))
+ En (TTe (x)))
Proof. Recall the definition of and the optimistic dual update:
Q+1 = (Q+ - (, (x)) ((m,,
We can derive the update rule of 9:41
g++1 + Ez (TT, ge (=))) = (gt + 2E, (TT. (z))))
4+1 max(-la-a)). (iTT, &r (z))) ar + Er ( &i (x)))),
13

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints To facilitate the analysis of yts we define the following ((TT)::
Ex (T Bi if q: + (TT, 2 -Ba[(me (x)))
((T)))
qt E g else.
Then we can rewrite the update of qt+1 as Recall the definition of the drift term, we have
a++ = qe + ((T)).
(
+ (:)(T))
2
TTT,)²
+ ( - E. (T. (x))))
2
qe (T,, g (1)) (0(=)) (T g (z)))) E. & (x))))
2
=q, (ig (TT, Be (x) R. (TT, (x))) p(T,)²
2
Bz &r (x)) R., ( () (z)))
where the third equality follows from the fact that (:(((()))) ( E: (x)))) (d(mz) + (e))),,(()))))((
ET (=])),,,((=)))),, which can be proven by considering the cases ((T+)) Ex ( Er (x))) and (())) + E [x(T)))
Finally, we substitute qt= Qt ( 8 (z:))], which completes the proof.
When analyzing the upper bound of the drift term, the cross term (T 1 (z)) (x))) presents significant analytical challenges. To resolve this, we derive the following lemma. Lemma A.3 (Restatement of Lemma 5.7). The following inequality holds for t [T].
(() 2 BTI (x)))
(x)1
2
2
E2 11 (xr) [x(())
|| --11l
Proof.
- (m-11)(((=))))+ [[E, (r()) - ن ( + -
1)11)))²
<(E [1 - 8 [x] + [,,1,: 1llo |. 111))
(E, (z)1 + E.
1
<2E, [z) (z)) 2|| -
where the first inequality comes from Hölder's inequality, the second and third inequality hold since || < 1 and
| < 1, the last inequality holds since (a + b)2 < 2a² + 21 and E[X]² < E[X²]. Then we can obtain
E, [TTe, & (z))²
1.- l 1 (z)) & (x) < E E- (z) ge (x)))
+ ||
T-1
Rearranging these terms and then we complete the proof.
By combining the two lemmas above with the inequality derived from the pushback property and applying Pinsker's inequality-oue whiih states || - x < 2D(==l(==-)) S ( we derive the following bound:
[T[(TT Te, f(,)( |E,AAHH <I.[2]|((<;) - (xxx:))l
+ E.
Σ (B(() g(x;)) [H,
+ [a
a (D( (TT)) H..
+ E.
g. (x:) 12 [H.]]
+ 7 (EE ( 8: (=)) |H., - EE (2))
Taking expectation w.r.t. the historical information H4, we complete the proof of Lemma 5.3.
14

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
B. Proof of Theorem 5.1
In this section, we prove our main results Theorem 5.1 by leveraging Lemma 5.3, which establishes unified bound for both regret and Lyapunov drift. We first derive the regret bound, followed by the constraint violation analysis.
B.1. Proof Regret bound
We begin by summing the inequality Lemma 5.3 over T to obtain:
T
T [f()))
E
ne, f(2)))
+
Σ
4
E
f((x1)]
T
+ E
Q1 , - 8(r+))
+ E
a(D(T ([T'' D( (mx))
E [l] (I) [x(
(Te, (e()))²
(0-11;(01(11))
+ E
2
2
We analyze these terms one by For the first term, based on the learning oracle assumption, obtain:
E 2 [f)))
f((w))) < 2 Σ (l,( $2|A1, T
[ p)ll2
- V Tlog (1)/p)) Ö((T),
where the second inequality comes from the Cauchy-Schwarrs Schwarz inequality. For the term E ΣT= ()) g(zz)) we decompose the expectation using the event defined in Assumption 3, considering both & and its complement &
E
Σ Q - (zz)))
=E
Σ (o(=".g(aa - g(x)))|
+ E Σ Qut .g())) g(x)))E
<
Σ Qe
(x())) (0t"",((())
g(x)))E
<E
1Qlll (1li, - g(x;)118
<4|A|pT2
where the last inequality holds since the event & holds with probability and the facts that ||Q:1 S 2T, ||>'|| < 1, (x.) g(xx)]l < 2 Then we show that E Σ Qe(T"" (.. (x.) - g(x))) = O(1) since p = +/--
Next we analyze Σ a(D(T"1(z=1)) - (( (1 and E Σnn
(m)) 8.)1)) ] 2
For these two
2
terms, it's easy get that
E
Σ a(D(TT)lm -((r)))))((xx(())))) ((x=)
=ElaD( [)o))
Salog((AA])
15

---

Triplc-Optimiste Learning for Stochastic Contextual Bandits with General Constraints the inequality holds due the uniform initialization of Tт-
E [(T,, (x))) EE [ 1. (x)))
I [TTT gr (x))]²
2
2
2
where the last inequality holds since 0r(z, a) E [-1, 1] and øт E II is the probability distribution. Finally, we have
T 1 (2)
T
E
-
<E
- g(x)11
+E
Σ
(x) - --)))
(e(,,,,)))1
2|| log(mxx) (g1)/)) (01)/))=000) Ó().
where the last inequality holds due learning oracle assumption. Combining all these terms, then for the regret term, we have
E
Te. f(x1))
A + +244 +|A/pp2 + +llo((AA) + 2| (og(max((F)))1))))) 2
+
4|A a + 2 log ( (1)/p)) +
2
22 A2 (og(
4.App2 alg(((1)1)) 2| log(max(()) (9)/p) + Ö(VT).
where the last inequality holds since the initialization of QI and set E., (TT, (o(r)) 0, then complete the proof of the regret bound.
B.2. Proof of Violation bound
From the update rule of Q+. we have
E
Σ (o
Bi
< Qr+1 +1 gr+1 +
Then the cumulative constraint violation can be bounded by
T
T
E
TE
g(x))
=E
me g(xg(()) - -g(()))
+ Σ
FTx (x
<
g((z) - B,(x)||
+ +9r+1 +
Recall that we have already proved a unified upper bound for both regret and violation, which gives
T
E
Σ (n"
ne, f(x1))
+E
Σ
A
+ 4.2pp2 alog(()) +
1
16

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
Rearrange these terms, have
E
A
9T+1
Σ ae - x,, f(x)))
+ Tloll/ + 4|AApT2 aloog((A))
1
4|Al) 44
2T + 2|A1v (oloooogaaa((ii)
aoo(( + 2
(15)
where the last inequality holds since f(x, a) S 1. The above results imply that ElgH+1] OT)), which equivalent to
Tr+1 OV)T). Combining these results, we have
E
Σ
Te 8(z))
<E Σ [l(()) Bx(+))] 9T+1 +2
g(x) Bx(r] 0
T AA
[ a.p) + 97+1 +2
T ||| [/ogm
which completes the proof that V(T) = Ö(VT).
C. Proof of Theorem 6.1
For the regret analysis in contextual bandits with knapsack constraints, we have established the following decomposition into "regret before stopping" and 'regret after stopping":
RT(T) = TD"
Σ Te, f(x))) + [T T]u"
We first analyze the regret before stopping, where we can apply Lemma 5.3 and sum over 7 to get:
E
G Te, ((xx))
E
Σ
A
<E
[[()))) (x(e)))
E
g - (w) 8
+ E
Qe(m ( g(xx))
E
Σ Ca(D(mill= -((blll)m)))))))))
E ( (x)))
E 11
+
First, we can conduct telescoping sum to get:
E
((((F")|== D ((T')
E[aD(=TI[TI) S a log((A)))
E KTT, (x))
E 1 (x)))
E ( (x)))) 1 2
Σ
2
2
Then the remaining terms be similarly bounded by the learning oracle error, which gives
E
[[f()))) ((x00
< E
[((()) - f((=)0| Ö(VT)
17

---

Triplc-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
T
E
18g-1(2) (2) - Bx
$ 2|
1e, a. a, = Ō(1)
E
Σ
(B g(x)))
=E
8 g(x)))|E
+ E
Σ 1=1
Q1 ( -g(s))1
E
(
g(x,)))E
<
11
g(
=4|App===
Combining these terms, we prove an upper bound for regret before stopping:
TV" Σ Tee f(x))) = E Σ ( - ne, f(x)))
= =Ō(TT).
Next, we prove the part of the regret after stopping. From the update rule of Qt. we can immediately obtain the following inequality:
4++1 + rb
Tee ge (x())))
and, using the definition of stopping time, know that satisfies g++1 + 2 B = Tb, which leads to the conclusion that
1/a " Blgr+i].
B(T++)Ju1]
From (15), we can derive that for any E (T), we have B[gd] Ö(vT). Setting / = r, and combining all these terms, we complete the proof.
D. Proof of Regret and Violation for MAB with stochastic and adversarial constraints
As discussed above, have Opt imi iimisiiiiiiii iti 3 be readily applied MAB with stochastic and adversarial constraints. The only difference is that need to plug in dedicated estimators for this setting. In particular, since target is to handle the adversarial reward, we use the EXP-3 style estimator for reward
re(a) (((()
(a)
lla az).
(16)
For the constraints, we use weighted empirical estimation in (Bernasconi et al., 2024a) such that it can adapt to both stochastic and adversarial settings. particular, we design the cost estimator (a) and the bonus term (a(a) such that (a) satisfies
(a) S (a) ba(a).
The bonus term is as the classical upper/lower confidence terms b,(a) =
7 log m.(a)
Let Te,a = (r S t, az = a} be the set of rounds in which the algorithm plays the action a:
(a(a)=
Σ
w+(a)c+(a)
(17)
TET
18

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
The weights (a)) need careful design such that is good track the "slow" change in the stochastic setting and the "fast" change in the adversarial setting. In particular, motivated by online learning, (Bernasconí al., 2024a) designs the following weights
1 1+ Mr,a
wr (a) - (a( sPT, sETi,a
II
(1-n((a)) with 77 na(a)
(18)
where nr,0 is the number of action a taken by the algorithm and r, EE'= Ca(a)) Vmax KT
Minax KT
is the
clipped constraint violation to regulate the learning rate. This design is motivated by the online gradient descent regard (Cr(a) ca (a)))²//)) /2 as the loss function and update follows
(((a) - (a))(a cc(a)) if = at if + at.
(+)(a)= [t(a).
Intuitively, let (T((a)= = mi(a] and (a)) = Erera cr(a) become the empirical mean, which works for the stochastic setting,
R((a)
To capture the "fast" change of adversarial setting, the violation Ir is imposed to pay more attention to the recent samples. Then we can construct an LCB-type estimator as
= = ((a)= - (a))
(19)
optimistic for MAB with Stochastic and Adversarial Constraints
Initialization: To, Q1 = 0, a 2 2 and the regularization norm D(-II-)
For = -I.,TTT-1
Optimistic Learning: in (16) and (19).
Optimistic Decision: Construct policy ne to minimize the surrogate function:
71 arg min (,) Qe(m, 2x) + aD(m
(20)
Sample action 0g TT.
Observe Feedback: Observe noisy reward (ar) and cost o (uz).
Optimistic Dual Update: Update the optimistic dual variable Q++1 as follows:
Q++1 = [Q - (T: ē.-1) + 2(T,, 2,
(21)
Lemma D.1. Let be the policy decided by (20), define Qi (,--1, and its corresponding drift A.
( )²). For any feasible policy π, Optimista achieves
(TT Te-1, Fr- +
< E 1 (x)] + (E(D(T|(T:-)) a
- [T][
1 a č. | + _ [ o,)² ( 1) | #]- - 112].
+ Elll::
Proof. The proof is almost very similar except we need to pay some attention to the reward part. Note we have r:-1 = 1E(r.. We have
(T--1- n,, (.) + Q ē.) (
<(T-- ,, f.) Qe ét) + aD(T aTT(Im)
19

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
Take the expectation both sides of the inequality
E ( - -1-1. + [ - Te. a ( (TQ ct) < Qq c,)] + -
Then we leverage the local normal analysis of online mirror descent in (Sun et al., 2017) such that
1
(Te-1 ne, r2-1) + +
r--1 1| 2
a
Therefore, we have
BI(T T- r-)) +1 (+)
- -B[|r-1113]
<B c.)] + a - [(T[[=]]] + a
Following the exact steps to handle the virtual queue and the constraints in Appendix A, we have two key inequalities from Lemmas 5.6 and 5.7
A S (me,, Cx) + (Me, é-11
Qi(Te, Cx) (T) + (.).
and
(n-1,CC-1(n (2) ( ||ē,-1 -ill2 fel12-1(Te T.11
1|
Combine these inequalities, we have
E[(T Tt-1, Ft- B|A:] s (Q( 8,)l + aE (E(((==|T - [()
+ E[ll,,11 è: c.13 + f [T), (MT-1, 1)
1 Bl[lr r [13]
a
Lemma D.2. Optimistic achieves
T
Σ
2 - -
< 16 + 16 VKT + 27 log T.
Proof. Let's focus on the difference of (() - (a) when a = a, (otherwise the difference is zero)
- < (() =a(a))² - 2(b - b,(
(22)
where
4(1 + T(-1)?
(a) (r(a))² = vi (0) -
<
n²-1(0)
(Vm-laa) Vn((a)
< ? log
(b)-1(a) - bx(a))² logT
(1)((a)
Note Σ, (a) t. This implies that
T
T'
16 16T2 1-1
27 log T n4 1 (a+)
E
Σ
8
22122
SE
(at)
T
16 16T2
< E
+ 2y log TT'
n (a.)
< 16 16 V KT + 2 log"
20

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
where the first inequality holds because of (a b)2 s 2(a² b²); the second inequality holds because the upper bound will be attained when (a(a) J Va E [K] time the last inequality holds similarly due the definition of
T Ex co(oz) - Vmax v KT Mmax KT and when (a) = [t/K], Va [K] at time t. Specifically, we use
Vmax v KT (tt
Pama KT
0
n (4))
f2
1=1
1=1
Mmax VKT
Vmax V KT
Vmuax K2
T Σ
(lt
max
KT
Mmuax KT 10
t²
t= Venax v KT]+1
T
([t
Mmxx v KT 10
Vanax VKT
Σ
t= Pmaz J+1
u2
KT
Σ
maz
12
t= Pinax VKT 1+1
Vima KT
Vmax KT
Vmax V KT
Based on Lemmas D.1 and D.2, we have
([(TT T2-1, )] E < E ( e,)l aB[ (-]]m
_ 2
[(TE. ē,)2 (m--1,
B 1|]])==113 + 16 16V V KT + log" 2gg T.
(23)
The inequality in (23) is the key and unified result to establish both sublinear regret and violation for MAB with stochastic constraint and 3-regret for MAB with adversarial constraint. As discussed before, we need to impose different baselines for stochastic and adversarial settings.
Recall the offline problem for MAB
max E
(
(24)
TTy Ce)
5.
(25)
We just need to impose different baselines for these two settings. Intuitively, for the stochastic constraint, we can compare with the optimal offline policy n" to (24)-225); for the adversarial constraint, we only compare with a weak 3-optimal offline policy 3-7*
D.I. Optimistic for MAB with Stochastic Constraint
When the constraints are stochastic, i.e., E(ca] = c, Vl E [T], the offline problem is equivalent to
T
max E
(T, rz)]
(26)
s.t.
[T, c) 0.
(27)
Based on the key inequality (23), we let π = n² be the optimal offline policy to (26)-227). Therefore, we have the key term to be non-positive
Q.E [.) < Q. .c) H4.
21

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
Therefore, have
BI(TT + aBiD(r" D( E [ 02)² ( ( cc-1)
B[ [19] 16 + 16 V KT + 27 log²T. T.
This implies
TK 1 2 ((T, 16 + 16 VKT +2 log" T
E
n ne rx)]
Elgi+al 5 aBB[D(='||
TK
aa K+ +
+ 17 + 16/ v KT 27
a
Recall VTK/ log K, we eventually have
Ne. r()) + 2
BB S 22/TKlo K 17 + 16 max v KT 2y 2og T.
(28)
D.1.1. REGRET ANALYSIS
From (28), we directly have
R(T) S v TK log K + 17 + 16 v KT + +2y T.
D.1.2. VIOLATION ANALYSIS
From (28), we have
B[g7+1] 2T 2(2 log K + 17+ 16 VKT 27 log T).
This implies that
E Elgr+1] 2VT 2/ VTK log K 17 167 v KT + 2y log T.
According to the definition of Qi (TT-1, c.-1) and the update of Qe in (21), have
(TT, 0x) < QT+1 + + 2 2VT +2 TKlog K + 17 + 162 KT + 27 log2 T
Now, we proceed to bound the constraint violation, where with high probability,
me, c)
Te, ox)
Te, Et)
T Tee 0z)
Σ
mTe c - ox) +
T ba) Σ
T
T
< 3
Σ (T bi) + Σ (TTe
t=1
< <6/Tlogg T +3+ 2VT 2/ VTK log 17 16V 16 2 log T,
where the first inequality holds from Bernasconi al. (2024a, Lemma 6.2) that the gap between the empirical mean and (17) is also bounded by ba(a), and the last inequality holds due to the definition of (a()) and the upper bound of estimated violation. Then we proved V(T) E Din(mee c) Ö(VT).
22

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
D.2. Optimistic" for MAB with Adversarial Constraint
When the constraints are adversarial, we can only impose weak baseline that mixes between the unconstrained optimal policy Tade and null policy Anult that minimizes the costs by ignoring the rewards. The trade-off is controlled by competitive ratio B, then the mixed policy is Tmiz = 3 Fode (1 B) Tnull. As in the setting of stochastic constraints, we study the key term Q, Tiiz. (x) [H]] and hope to find a mixed policy such that it is non-positive.
According to the definition of č₂ C₁ b,, we have
E [(Tmia [e) S E [iiii Cx) Hi].
Let's study the key term of (Tmizz Ci) as follows
maiz Ct)
Σ T mine (a)
Σ
wr (r(a)cr(a)
TETe,
8 Σ add (a)
Σ
Wy (=(ec)((a)) + (1--3) 3) Σ Tnuu (a)
Σ
(r(a)c+(a)
TETra
TETe.a
$ Σ adu (a)
Σ
(a(a) + (1- ()pp)
Σ wr(a)
TETeaa
TETe,a
3 (1- 3)(p))
(29)
where the third inequality holds because e, (a) S 1, Va, and e, (analt) c(anui)) = -p. the last equality holds because EreT.. Wr (a) 1; Finally, recall the definition for competitive ratio p/ p) such that (Tiii Ct) O.
Therefore, we have
T
E
Tmia Te, rz)
+ 1 [1] S 22/TK log K + 17 + 16Pmax V KT + 2og T.
(30)
D.2.1. REGRET ANALYSIS
Obviously, we have E ET (Tiias r()] 18 1E (Ifp Todo re)],
Then we can prove the regret directly from (30),
p adv Te, re) S v TK TKlog K 17 may v KT + 2y log T.
3-R(T) E
+ p
D.2.2. VIOLATION ANALYSIS
From (30), we have
Blg7+1] 27 2(2 TK log K 17+ 16 max V KT 27 log² T).
This implies that
E[gr+1] 22TT++ + 2/ VTK log K + 17 + 16 / KT + 2y log² T.
According to the definition of Q: (TT--1 Cr-1) and the update of Q. in (21), we have
E
m ax)
< <E + 2 2 2 TT log K 17 + 16V v KT 27 log2 T
Now, we proceed to bound the constraint violation
T
T (T, Ei)
V(T) E
T ci)
E
Te, Ct ē,)
1=1
E
Te, C₁ c.)
(Te, bi) +
(TTe Ec)
23

---

Tripl--Optimistic Learning for Stochastic Contextual Bandits with General Constraints
Note (a) 3v
T (a): we have
R
(m ba) S T
where the second inequality holds because the upper bound will be attained when nz(a) = [t/K], Va [K] at time Therefore, we have
T (e ct - C2) + 5 + 2V VTK log K + 17 + 162 KT + 27 log
V(T) <
Σ
Let's focus on the key term Ei=1 (Te. Ct ē Here recall an important corollary in Bernasconi et al. (2024a, Corollary 5.7), from the fact that the learning (a) rates are non-increasing, which gives
Ce (c+1(a)- a(a)
1
E
TTe Ct ot)
=
(e(a)
9T (a)
TETT.a
where (a) (1+T)) and T3 1E'= C. (a,) Vmax KT Menax KT following. Fix action and let k [Traa be the number of times action is played before time horizon T. Define ((j) be the rounds in which action is played the j-th time. We can obtain:
We provide simplified proof in the
(a) ((a) Te((a)
tETr.a
Σ
(bo+1)((a)= (ct)(a))+ + (a) (C)())+1(a) Tecas (a))
(a))
jE(K-1]
< Σ
(hu+1)(a) (1o4))()G4OADD0 ((o+1)(a)) jE(K-1]
mis(aa (us(aa) (us((a) + (aas((a) (c())) ((x)(())
(31)
1
1
((())+((a)
(a))(a) (())aa)
(a)
(1)))+((a) S mT((a)
(a)
The above proof requires that the costs (or the estimated ones) non-negative in the adversarial setting. Specifically, the key inequality (31) requires not only that the learning rate sequence (a(a) be non-increasing, but also that ((aa) 2 0 for all t.
Combining these facts, we have
KT
V(T) <
+3+ TogoTT + 2/ / TK log K + 17 + 16p KT + log" T
+ lT
Now, if V(T) 2 21 max v KT KT'log have PT Mmax / KT logT such that
KT
V(T) < 2v Imax / /og
3+ 5. Tlog 2 VTK log K + 17+ 16Pmax V KT + 22ylog* T
< 3/max
KT log
Therefore, it concludes the proof of violation of adversarial constraints.
E. A Additional experiment on BwK with stochastic and adversarial constraints
We evaluate our approach through numerical experiments on non-contextual multi-armed bandits across both stochastic and adversarial environments. We consider |A] = 10 arms and the time horizon T 10000. All results are obtained by averaging over 50 trials and reported with 95% confidence interval.
24

---

Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints
In the stochastic setting, each arm's mean reward r(a) = Pu drawn from the uniform distribution of [o, 1] while constraint c(a) X is drawn from the uniform distribution of (-0.5, 1]. Observations of rewards and costs perturbed by Gaussian noise (0,, 0.05).
In the adversarial setting, rewards and constraints adopt varying dynamics: rz(a) Ma + og sin(w)t) and (a(a) = Ay + a sin(wat), where Ma: Aa match the stochastic setting, amplitude and frequencies a a w w Uniform (0, 0.2). Observations of rewards and costs are perturbed by Gaussian noise (0, 0.05).
Figures demonstrates that Optimiss imiisiii outperforms all baseline algorithm, which justify our theoretical guarantecs.
1.0
0.3
LGEZD
LOEAD
Laghenge/Biwtt:
Legrengechiic Optimtatc"
Optimistic
0.2
Averaged Reward
0.8
Beyond
Averaged Violation
Beyond
0.1
0.6
0.0
0.4
-0.1
0.2
0.0
2000
4000
6000
8000
10000
-0.30
2000
4000
6000
8000
10000
(a) Averaged reward under stochastic setting
(b) Averaged constraint violation under stochastic setting
1.0
0.3
LDEZO
LagrangeCBALC Optinictica Boyond Pamaa
CB
Optiniitice Beyond Primal Dual
0.8
Averaged Reward
Averaged Violation
0.1
0.6
0.0
0.4
0.2
-0.2
0.0
2000
4800
6000
8000
10000
0.3
2000
4000
6000
8000
10900
Averaged reward under adversarial setting
(d) Averaged constraint violation under adversarial setting
Figure 2. Averaged reward and constraint violation under LOE2D (Guo & Liu, 2024), LagrangeCBwLC (Slivkins et al., 2023), Beyond Primal-Dual (Bernasconi et al., 2024a) and Opt imisstic.
25


Reviews:
[{"review_id": "LvKwNH5B7m", "reviewer": "Reviewer_G6Cx", "summary": "The submission studies contextual bandits where the agent aims to minimize the regret (Eqn. (4)) and the constraint violation (Eqn. (5)) simultaneously. The submission shows that the previous bounds can be improved (in the sense of removing the need for Slater’s condition or lowering the upper bounds) by a clever choice of the dual update mechanism (i.e., the update of $Q_t$ in line 189R). The key inequality is Lemma 5.3 and the main result is Theorem 5.1. The proposed method, Optimistic3, is applied to solve CBwK, multi-armed bandits, and the best-of-both-worlds problem.\n\n\n## Update after rebuttal\n\nThe authors' reply addressed my concerns. Thus, I will maintain my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the positive feedback. We would like to address your questions as follows.\n\n- **\"Tripe-optimism\".** The intuition behind our optimistic dual update stems from the Optimistic Online Mirror Descent in [R1], which accelerates convergence through effectively using predictions. Building on its success in min-max optimization [R2], we adapt this paradigm to design a momentum-driven dual update mechanism. Mathematically, our update incorporates a correction term that acts as a momentum term to predict and exploit trends in the reward-cost tradeoff dynamics, thereby accelerating convergence. We will incorporate these discussions in our revision.\n\n- **Regret analysis and prior works.** The regret in (4) measures the performance gap between the algorithm's policy and the optimal fixed policy in hindsight, where $\\mathbb{E}[\\langle \\pi^* - \\pi_t, \\mathbf{f}(x_t) \\rangle] $ represents the instantaneous regret at step $t$. Classical primal-dual methods (e.g., Slivkins et al., 2023) necessitate manual bounding of the dual variables and further decouple regret and constraint violation guarantees by independently bounding primal and dual regret terms. Recent work (Guo & Liu, 2024) introduced a refined Lyapunov drift framework to eliminate the knowledge requirement of Slater's condition but still require it hold. In contrast, our approach integrates a unified analytical framework via the pushback lemma (Lemma 5.3), enabling simultaneous control of regret and constraint violations. The optimistic design further facilitates bounding $Q_t$ by incorporating a momentum-driven correction term, circumventing the need for the Slater condition entirely. We will include a comprehensive comparative analysis of these methodologies.\n\n- **The pushback lemma.** Pushback lemma is a fundamental result in online optimization, particularly when working with Bregman divergences (here we specify as KL divergence). This lemma comes from the strong convexity property and guarantees that the optimization process inherently resists deviations from the optimal solution, with the term $\\alpha D(\\pi||\\pi_{opt})$ quantifying the magnitude of this \"pushback\" effect.  \nHere, $h(\\cdot)$ denotes the primary objective function; it forms an OMD-style update as in (7) when combined with the regularization term. By specifying $h(\\cdot)$ as the surrogate function in (6), the solution $\\pi_{opt}$ corresponds directly to the policy $\\pi_t$.  \nWe have included the discussion of these key terms and supplemented it with additional references to enhance clarity and accessibility.\n\n- **Comparable performance with LOE2D.** Although both Optimistic$^3$ and LOE2D significantly outperform LagrangeCBwLC (which requires knowledge of Slater's condition), there remains a noticeable gap between them, which appears smaller due to plotting averages. Unlike LOE2D, our approach employs an optimistic design for $Q_t$, which accelerates convergence to the optimal reward-cost tradeoff. This design enables a more refined theoretical analysis that cannot be achieved through LOE2D.\n\n---\n\n**Reference**\n\n[R1] Rakhlin, Sasha, and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems (NeurIPS), 2013.\n\n[R2] Mokhtari, Aryan, Asuman E. Ozdaglar, and Sarath Pattathil. Convergence rate of O(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization.", "claims_and_evidence": "Theoretically, the submission upper bounds the regret and the cost (Theorem 5.1). In the experiments, the performance curves show that the proposed method (Optimistic3) outperforms the existing baselines in terms of regret and cost (Figure 1).\n\nHowever, there are several disconnections within the analysis and between the literature. Please see the comments/questions in the next two sections.", "methods_and_evaluation_criteria": "What is the intuition of the 3rd optimistic update (line 192R)? A high-level discussion of its design and comparison can be found between lines 225L – 237L, but there is no further connection to the corresponding mathematical derivations.", "theoretical_claims": "- How is the first equation (line 293R) derived from (4)? How did the previous work analyze regret under the primal-dual framework? We need a reference and an explanation to clarify which parts of the analysis follow the previous framework and which parts are novel.\n- Lemma 5.3 provides a crucial inequality in the analysis. However, there is no explanation of its connection to the primal-dual framework in either the main text or the appendix.\n- There is no discussion of several key concepts such as the pushback lemma and the function $h()$. This submission only writes down the derivation lines, but lacks the connection to the existing analysis in the literature and fails to articulate the novelty of the submission. For instance, besides the novel dual update rule (line 192R), is there any new technical tool developed from this submission? Is the pushback lemma (line 277L) novel on its own, or is it a refinement of an existing result?\n- The pushback lemma is applied in lines 557 and 660. What is its intuition? What is pushback to what?\n- The submission claims to be able to relax Slater's condition. In which line of the derivation can we see that the novel dual update removes the need for Slater's condition? Again, without referencing the literature and discussing the details of the derivation, it is difficult for a reader to understand the novelty of the submission.", "experimental_designs_or_analyses": "The experimental results show that the proposed method (Optimistic3) achieves lower regret and lower cost than the baselines. However, LOE2D shows a comparable performance. This is in contrast to the non-optimal upper bounds listed in Table 1 (the (Guo & Liu, 2024) row). Perhaps LOE2D is good enough, but poorly analyzed?", "relation_to_broader_scientific_literature": "Instead of focusing on regret minimization, the submission analyzes multiple measures for the bandit problem.", "essential_references_not_discussed": "The related work discussed in Section 2 is fine.", "other_strengths_and_weaknesses": "A minor issue: the sentence in line 658 is misplaced.", "other_comments_or_suggestions": "The dual update is novel. The submission achieves better bounds. If the submission can refine its discussion of its contributions and the connections between the literature, it would provide a comprehensive knowledge to this line of research.", "questions_for_authors": "Please see the questions in the sections above.", "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": "HLfdkQ5Qj6", "reviewer": "Reviewer_MfNn", "summary": "$\\newcommand{\\vg}{\\textrm{\\v{$g$}}}$\n$\\newcommand{\\ip}[1]{\\langle #1\\rangle}$\n\nThis paper is concerned with contextual finite-action bandits with unknown aggregate constraints. Concretely, in every round, the learner first observes a context $x_t$ drawn iid from a law which is known to the learner, and selects an action $a_t$. As feedback, the learner observes a reward $r_t(x_t,a_t)$ and a cost $c_t(x_t, a_t),$ which are each realisable in that there exist classes $\\mathcal{F}, \\mathcal{G}$ with good regression oracles such that $\\forall t, a, x, \\mathbb{E}[ r_t(x_t,a) | x_t = x] = f(x,a), \\mathbb{E}[ c_t(x_t,a) | x_t = x] = g(x,a)$ for some $f \\in \\mathcal{F}$ and $g \\in \\mathcal{G}$. Note that since the number of arms is finite, these can instead just be written as vectors $f(x)$ and $g(x)$. The goal is to maximise the accumulated reward, while ensuring that the violation $\\sum c_t(x_t, a_t)$ is small. \n\nNotice that this setting admits a static offline optimal policy, $\\pi^*$ which solves $\\max_{\\pi} \\mathbb{E}[ \\langle \\pi, f(x)\\rangle] \\textrm{ s.t. } \\mathbb{E}[ \\langle \\pi, g(x)\\rangle \\le 0,$ where the expectation is over $x$. The paper proposes a new `triply optimistic' algorithm that ensures that the pseudo-regret $\\mathcal{R}\\_T :=  T \\mathbb{E}[ \\langle \\pi^*, f(x)\\rangle] - \\mathbb{E}[ \\sum r\\_t(x\\_t,a\\_t)]$ and violations $\\mathcal{V}\\_T := \\mathbb{E}[\\sum_t c\\_t(x\\_t, a\\_t)]$ are both bounded as $\\tilde{O}(\\sqrt{T})$ without knowledge of or dependence on a Slater parameter (i.e., the gap in Slater's condition) for the static problem. This offers a significant improvement in that prior work on this problem either assumes knowledge of the Slater parameter (and incurs an inverse dependence it), or suffers a weakened $T^{3/4}$ regret in the absence of the same.\n\nThe algorithm underlying this method first computes optimistic estimates of $f, g,$ i.e., a $\\hat{f}_t$ such that $\\hat{f}_t \\ge f$ and $\\vg_t$ such that $\\vg_t \\le g$ everywhere (which high probability). The policy $\\pi_t$ is selected by optimising $\\langle \\pi, \\hat{f}\\_t\\rangle - Q\\_t \\langle \\pi,\\vg\\_t\\rangle - \\alpha D( \\pi \\| \\pi\\_{t-1}),$ the final term serving as a regulariser. The most interesting aspect of this method is the choice of the multiplier $Q_t$, which is updated as $ Q\\_{t+1} = \\max(0, Q\\_t + 2 \\mathbb{E}\\_x[ \\langle \\pi\\_t, \\vg\\_t(x)\\rangle] - \\mathbb{E}\\_x[ \\langle \\pi\\_{t-1}, \\vg\\_{t-1}]),$ which the authors term to be an \"optimistic adaptation\" of the multiplier, viewing $\\mathbb{E}\\_x [ \\langle \\pi\\_t , \\vg\\_t\\rangle - \\langle \\pi\\_{t-1}, \\vg\\_{t-1}\\rangle]$ as a momentum term. This method is analysed by developing a direct bound on $\\mathbb{E}[ \\langle \\pi^* - \\pi\\_t, f(x\\_t)\\rangle] + \\mathbb{E}[ q\\_{t+1}^2 - q\\_t^2],$ where $q\\_t = Q\\_t - \\mathbb{E}\\_x[ \\langle \\pi\\_{t}, \\vg\\_t\\rangle],$ which is bounded by a bunch of telescoping terms along with estimation error terms of the form $\\\\| f(x) - \\hat{f}_t(x)\\\\|$ that are controlled by assumption.\n\nAlong with the above result, this same method also yields a bound for the \"BwK\" case by a standard calculation. The authors also argue (albeit in a fairly terse section) that the same approach can be combined with a (context-free) estimation technique due to a recent work of Bernasconi et al. to yield \"best of both worlds\" guarantees in bandits with aggregate stochastic _and_ adversarial constraints.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer’s meticulous review and constructive feedback. The reviewer's concern is correct, where there are big typos in Lemma $5.6$ (and propagated into Lemma $5.7$). We sincerely apologize for the oversight and any confusion caused. Our proof remains valid when these typos are fixed. We are very thankful that the reviewer liked our \"optimistic\" idea and theoretical results (yes, they are correct). We are also very excited about these results when we realize that \"optimistic\" design from adversarial online learning can address the long-standing challenges in stochastic bandits. We sincerely invite the reviewer to re-evaluate the paper based on our response.\n\n- **Definition of $\\mathbb{E}_x$.** The expectation $\\mathbb{E}_x$ is taken w.r.t. the context variable, as correctly noted by the reviewer. Here, the variable $x$ follows the distribution $\\mathbb{P}$, identical to the distribution of $x_t$. We will specify the definition in our revision.\n\n- **Typos in Lemma $5.6$ and Lemma $5.7$.**  \n  As the reviewer correctly identified, the typo in Lemma 5.6 involves the cross term:  \n  $$\\mathbb{E}_x[\\langle \\pi_t,\\check g_t(x)\\rangle]\\mathbb{E}_x[\\langle \\pi_t,\\check g_{t-1}(x)\\rangle]$$  \n  which is misplaced by $\\mathbb{E}_x[\\langle \\pi_t,\\check g_t(x)\\rangle\\langle \\pi_t,\\check g_{t-1}(x)\\rangle]$. This typo is unfortunately propagated into Lemma 5.7. Therefore, Lemma 5.7 needs to take care of the corrected cross term, and it is indeed correct by fixing the corresponding terms as follows  \n\\begin{aligned}\n&\\mathbb{E}_x [\\langle \\pi_{t-1}, \\check{\\mathbf{g}}_{t-1}(x)\\rangle] \\mathbb{E}_x [\\langle \\pi_{t}, \\check{\\mathbf{g}}_{t}(x)\\rangle] \\\\\n\\geq  &\\frac{\\mathbb{E}_x [\\langle \\pi_{t}, \\check{\\mathbf{g}}_{t}(x)\\rangle]^2}{2} + \\frac{\\mathbb{E}_x [\\langle \\pi_{t-1}, \\check{\\mathbf{g}}_{t-1}(x)\\rangle]^2}{2} \\\\\n& - \\mathbb{E}_x [\\| \\check{\\mathbf{g}}_{t-1}(x) - \\check{\\mathbf{g}}_{t}(x) \\|^2] - \\|\\pi_t - \\pi_{t-1}\\|_1^2.\n\\end{aligned}\n  where we fixed the typo of $\\mathbb{E}_x [\\langle \\pi_{t}, \\check{\\mathbf{g}}_{t}(x)\\rangle^2]$ in the original version.  \n  We have attached a complete corrected proof in [https://anonymous.4open.science/r/Pr25/](https://anonymous.4open.science/r/Pr25/). We apologize for the typo again and thank you very much for your time to read the correction.\n\n- **The origin of the typo.**  \n  We want to explain that the reason behind the typo is that when we started working on this problem, we indeed tried the ambitious sample-based design, as you suggested. However, this would have issues when establishing Lemma 5.7.  \n  Specifically, this design would introduce $$\\|\\check{g}_t(x_t) - \\check{g}_{t-1}(x_{t-1})\\|^2,$$ which is extremely challenging to quantify as the difference between two realizations are involved. Then, when we switched to the current \"expected\" design, we apologize that we had the copy-paste typos.\n\n- **Extension to other Bregman divergences.** This can be extended to other Bregman divergences, and we will include a discussion in the appendix.\n\n- **\"Triple-optimism\":**  \n  The term $Q_t$ is characterized as \"optimistic\" due to its conceptual roots in the Optimistic Online Mirror Descent framework in [R1], which leverages predictions to accelerate convergence. Inspired by its application to min-max problems in [R2], we designed an optimistic dual update mechanism, accelerates adaptation through a correction term that incorporates predictive insights, unlike traditional methods that rely solely on current feedback and employ a \"pessimistic\" exploration to balance trade-offs without leveraging historical trends. We will incorporate these discussions in our revision.\n\n- **Our algorithm for BwK in both worlds:**  \n  We introduce BwK in both worlds to demonstrate the versatility and broad applicability of our triple-optimistic framework. We will explicitly describe the problem setting and background to ensure clarity.\n\n- **Other typos and careless expression:**  \n  We greatly appreciate your meticulous feedback and have carefully modified all typos in our revision. We have conducted a full manuscript audit to eliminate any residual oversights.\n\nWe emphasize that our results **are unaffected** by the typos. We sincerely apologize for any confusion caused and deeply appreciate the reviewer's invaluable feedback. We hope the reviewer can re-evaluate our work in light of these clarifications.\n\n---\n\n**Reference**  \n\n[R1] Rakhlin, Sasha, and Karthik Sridharan. Optimization, learning, and games with predictable sequences. *Advances in Neural Information Processing Systems (NeurIPS)*, 2013.  \n\n[R2] Mokhtari, Aryan, Asuman E. Ozdaglar, and Sarath Pattathil. Convergence rate of O(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. *SIAM Journal on Optimization*.", "claims_and_evidence": "I think the main claim of Theorem 5.1 is incorrect due to a bug in Lemma 5.6. Please see the 'Theoretical Claims' section below.", "methods_and_evaluation_criteria": "---", "theoretical_claims": "The theoretical issues I raised have been clarified by the rebuttal, and to my understanding, the results are correct.\n\n~~I think there is a serious bug in the paper, which breaks the results.~~\n\n~~Firstly, let me note that the notation $\\mathbb{E}_x$ was never defined, which is important since expressions like $\\mathbb{E}_x[ \\ip{ \\pi\\_t, \\vg\\_t(x)}]$ are constantly used within the paper. My interpretation of these is that this is the expectation of $\\langle \\pi_t, \\vg_t(Z)\\rangle$ where $Z$ is drawn from the same law as the context $x_t$. This is more or less the only reasonable thing I could infer, because this notation appears with both $\\vg_t(x)$ and $\\vg\\_{t-1}(x),$ and of course since it is explicitly said that the knowledge of the law of the context is needed (and I don't see where else this is employed). I think the mistake however would be present even if this expectation were with respect to something else.~~\n\n~~In any case, I think there is a mistake in Lemma 5.6: From line 631, we should get the term $-\\mathbb{E}_x[ \\langle \\pi_t, \\vg_t(x)\\rangle ]\\cdot \\mathbb{E}_x[ \\langle \\pi\\_{t-1}, \\vg\\_{t-1}(x)\\rangle ] \\neq -\\mathbb{E}_x[ \\langle \\pi_t, \\vg_t(x)\\rangle \\langle \\pi\\_{t-1}, \\vg\\_{t-1}(x)\\rangle],$ i.e., the product of expectations rather than the expectation of the product. However the statement of Lemma 5.6 has the expectation of products instead.~~\n\n~~This is far from inconsequential: through Lemma 5.7, this expectation of products is utilised to gain terms of the form $- ( \\mathbb{E}_x[\\ip{\\pi_t, \\vg_t(x)}^2] + \\mathbb{E}\\_x[ \\ip{\\pi\\_{t-1}, \\vg\\_{t-1}(x)}^2 ])/2, $ which interacts with a $+ \\mathbb{E}_x[ \\ip{\\pi_t, \\vg_t(x)}^2]$ term to gain a telescoping expression $( \\mathbb{E}_x[\\ip{\\pi_t, \\vg_t(x)}^2] - \\mathbb{E}\\_x[ \\ip{\\pi\\_{t-1}, \\vg\\_{t-1}(x)}^2 ])/2$ in Lemma 5.3. However, the corrected version (controlling the product of the expectations) would give lower bounds in terms of $\\mathbb{E}_x[ \\langle \\pi_t, \\vg_t(x)\\rangle]^2$ (square outside the expectation), which means that now instead of this telescoping sum, there's a $ \\sum \\mathbb{E}_x[ \\langle \\pi_t, \\vg_t(x)\\rangle^2] - \\mathbb{E}_x[\\langle \\pi_t, \\vg_t(x)\\rangle ]^2/2 - \\mathbb{E}_x[\\langle \\pi\\_{t-1}, \\vg\\_{t-1}(x)\\rangle]^2/2$ left dangling. Adding and subtracting the appropriate squares of the expectation, this gives a (non-telescoping) overhead of $\\frac12\\sum \\mathrm{Var}_x( \\ip{\\pi_t, \\vg\\_t(x)}) + \\mathrm{Var}_x(\\ip{\\pi\\_{t-1}, \\vg\\_{t-1}(x)}) = \\sum \\mathrm{Var}_x( \\ip{\\pi_t, \\vg_t(x)}) + O(1)$. I don't think this term can be considered sublinear in $T$ (let alone $O(\\sqrt{T})$), which means that the bound instead obtained is that $\\mathcal{R}_T + q_T^2 \\le O(T)$, which gives no control on the regret.~~\n\n----\n\n~~By the way, I think the above might be fixable, in that I don't really see why you need the $\\mathbb{E}\\_x$ everywhere: suppose that this is dropped, and you operate with $\\tilde{Q}\\_{t+1} = \\max(0, \\tilde{Q}\\_t + 2\\ip{\\pi\\_t, \\vg\\_t(x_t)} - \\ip{\\pi\\_{t-1}, \\vg\\_{t-1}(x_{t-1})})$. Then an appropriate version of Lemma 5.6 does go through (seeing as there is now no expectation operator that is falsely distributed), and thus Lemma 5.7 goes through. The resulting bound is then on $\\mathcal{R}\\_T + \\mathbb{E}[\\tilde{q}\\_{T+1}^2],$ where $\\tilde{q}\\_{T+1} = \\tilde{Q}\\_{T+1} - \\ip{\\pi\\_T, \\vg\\_T(x_T)}.$ The regret bound is immediate, and for the violation bound, you instead get via a telescope that $\\sum \\ip{\\pi_t, \\vg_t(x_t)} \\le \\tilde{q}\\_{T+1} + O(1)$ surely, at which point you can pass to $\\sum \\ip{\\pi_t, g(x_t)}$ and hit things with an expectation, using the bound on $\\mathbb{E}[\\tilde{q}\\_{T+1}^2] \\ge \\mathbb{E}[ \\tilde{q}\\_{T+1}]^2$. Of course I might have something wrong here, and even if this works, then the edits should be made and the paper re-reviewed.~~\n\n---\n\nBesides this the analysis appears to be correct, although there are a bunch of carelessly written proofs (see the comments section below).", "experimental_designs_or_analyses": "---", "relation_to_broader_scientific_literature": "This is a nice paper. The approach taken is a simple change to the multiplier design, but has a far-ranging effect by attaining the tight square root regret without dependence on the Slater parameter. This would definitely be of interest to the online learning community at ICML.", "essential_references_not_discussed": "This is fine. Not essential, but I would prefer if the distinction from the \"safe bandit\" literature (where constraints are enforced in every round) were discussed briefly.", "other_strengths_and_weaknesses": "I think the approach of the paper is interesting, and the results are remarkable, given the nearly decade-long history of the Slater parameter and cost sign assumptions bumping along in the aggregate constraint bandit literature. The augmentation is simple, but quite elegant. \n\nThe natural sticking point is that the method requires knowing the context distribution a priori. This is certainly restrictive, but in my opinion the results are valuable nevertheless, particularly when compared to the recent work establishing similar guarantees in the noncontextual setting due to the much simpler algorithmic structure.\n\nI think that with the promise that the paper will be edited both for typos, and to expand the discussion of section 7, I am quite happy to recommend this paper.", "other_comments_or_suggestions": "- I understand that you want the name \"triple optimism\", but I don't see why the setting of $Q_t$ can be interpreted as \"optimistic\". This choice of name needs to be justified.\n\n- I think section 7 is way too terse of a presentation of these results. Like, I don't think the adversarial problem is even properly set up in the paper, so it's very hard to be certain of the meaning of anything said. Appendix D is similarly terse - I happen to be familiar with the Bernasconi et al. paper, so could plod through, but surely this should be self-contained enough that a reader has a hope of understanding what is being said (especially to do with the estimation, which is the main change). Expanding this should be important.\n\n- I don't really understand why the min-selection fairness constraints are discussed - aren't the $\\lambda_i$ known a priori in this problem? I also think the explicit discussion of the group-fairness constraints is somewhat unnecessary unless the paper explicitly addresses the further structure in this problem (in that it is obvious that such a constraint can be written in the form stated).\n\n- A bunch of proofs are somewhat carelessly written, and should be addressed:\n\n    - Line 645: why is $\\\\|\\vg\\_t(x)\\\\| \\le 1? $ Aren't you only told that $c\\_t \\in [-1,1]$. This means that the only reasonable assumption is that $\\\\|\\vg_t\\\\| \\le \\sqrt{ |\\mathcal{A}|}$, not that it is $\\le 1,$ right? Which would in turn bump up $\\alpha$? This all still works - use Hoelder's to bound as $\\\\|\\hat{g}\\_{t-1}\\\\|\\_{\\infty} \\cdot \\\\| \\pi_t - \\pi\\_{t-1}\\\\|\\_{1},$ and hit the second with Pinsker's, but as written, I think it's natural for me to assume that the norm just means 2-norm, and then it's full-on confusion city (and worrying about contagion). Please rewrite this stuff correctly. \n    - Line 627: the equality here is only true if $h(\\pi_t) = -q_t - \\mathbb{E}\\_{x} [ \\langle \\pi_t, \\hat{g}_t(x)\\rangle].$ Of course, in the other case the inequality is trivial, but this needs to be written, otherwise the proof as stated is incomplete.\n    - Line 568: there's a typo: should be $D(\\pi\\\\|\\pi\\_{\\mathrm{opt}})$ on the RHS. Also, while I'm at it, not sure that the $\\hat{h}$ notation adds any clarity, since it is always expanded immediately, and in line 572, it's probably worth explicitly invoking convexity of $h$ to write $h(\\pi) - h(\\pi\\_{\\mathrm{opt}}) \\ge \\langle \\nabla h(\\pi\\_{\\mathrm{opt}}), \\pi - \\pi\\_{\\mathrm{opt}}\\rangle,$ which would add some clarity.\n    - Line 313 Col 2: the $\\sum \\\\|f - \\hat{f}\\_t\\\\|$ should be $O(\\sqrt{T})$ instead of $O(1)$?\n    - Line 618: I got confused because the main text had already defined a $h(\\pi)$. Maybe use a different letter?\n    - Line 654: should be $2a^2 + 2b^2$.", "questions_for_authors": "- I liked the use of the OMD-style regularisation to eliminate the $\\\\|\\pi\\_t - \\pi_{t-1}\\\\|_1$ drift term showing up in the analysis. Presumably this can be extended to other Bregman divergences? A short account would be nice (perhaps in an appendix).", "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": "MXqOLKJ311", "reviewer": "Reviewer_cndg", "summary": "The paper proposes a Triple-Optimistic Learning method for contextual bandit with general unknown constraints. And further the paper shows a regret and violation of $\\tilde{O}(\\sqrt(T))$, which outperforms the previous method on $\\tilde{O}(T^{3/4})$.  They also provide the regret bound of CBwK and extend to the adversarial and stochastic bandit.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We very appreciate the reviewer for the constructive comments and want to address your major concerns below.\n\n- **Online regression oracle.** The online regression oracle assumption is standard in contextual bandits (Foster et al., 2018; Slivkins et al., 2023; Han et al., 2023; Guo \\& Liu, 2024; Chzhen et al., 2024; Anonymous, 2025). This assumption extends the UCB/LCB (upper/lower confidence bound) paradigm to handle diverse environmental settings. The LinearUCB algorithm serves as a fundamental example that inherently satisfies this assumption. For broader applications, [R1] presents an efficient binary search method for UCB/LCB construction.\n\n- **The usage of UCB/LCB.** Both UCB and LCB enhance algorithmic exploration in online learning but serve distinct roles: UCB optimistically guides exploration toward actions with lower estimated rewards but higher uncertainty, prioritizing under-explored regions of the reward space. LCB encourages the exploration of actions that appear marginally unsafe under current estimates (i.e., with higher predicted costs) but may still satisfy constraints upon further investigation. By assigning LCB estimators to cost function, the algorithm temporarily treats these actions as ``safe,\" enabling exploration of uncertain constraint regions.\n\n- **$Q_t$ and $\\mathbb{E}_{x}$.** While $Q_t$ can be interpreted analogously to Lagrange multipliers (or dual variables), its update rule differs fundamentally due to its optimistic design and unbounded property. This design accelerates convergence and enables our key analytical framework to operate without reliance on the Slater condition. \n  The notation $\\mathbb{E}_{x}$ denotes expectation only over the context variable (drawn from a known distribution $\\mathbb{P}$), not over the entire history.\n  We apologize for any confusion caused by this notation and have clarified it in the revised manuscript.\n\n- **Optimistic decision process.** The surrogate function in (6) represents the estimated scores over actions. While prior works (e.g., Chzhen et al., 2024; Anonymous, 2025) directly optimize these scores, we introduce an additional regularization term in (7) to stabilize and smooth the update since we introduce the optimistic design to speed up dual updates and encourage exploration.\n\n- **The drift term $\\Delta_t$.** The Lyapunov drift term $\\Delta_t$ quantifies the stability of the virtual queue, enabling us to bound cumulative constraint violations through its analysis (see lines 375–381). This term comes from the direct usage of Lemma 5.6 to replace $Q_t \\mathbb{E}_x[\\langle\\pi_t,\\check g_t(x)\\rangle]$ in line 293.\n\n- **Other comments.** (i) The cumulative error of reward in line 312 is a typo, and it should be $\\tilde{O}(\\sqrt{T})$, the proof can be found in line 699. (ii) We will briefly introduce contextual bandits under stage-wise constraints (also termed safe bandits), where algorithms typically assume access to an initial safe region and rely on the iterative construction of safe decision sets. (iii) We sincerely appreciate your suggestions and will incorporate more intuitive explanations and detailed discussions to ensure the methodology and proofs are easy for readers to follow.\n\nWe hope that our response addresses the reviewer's concerns and that the reviewer can re-evaluate our work. Please let us know if you have any further comments, and we will try our best to address them.\n\n---------------------------------------------Reference-------------------------------------------------\n\n[R1] Foster, Dylan, et al. Practical contextual bandits with regression oracles. International Conference on Machine Learning (ICML), 2018.", "claims_and_evidence": "Some of the writing/assumptions might not be clear and need further clarification. \n\n1, In assumption 3.2, why the sum of UCB/LCB uncertainty $\\epsilon$ is bounded by the term in Line 191? Is it from the general UCB algorithm? And further, does UCB and LCB for reward and cost share the same \\epsilon? If yes, I believe this could be a wrong assumption? \n\n2, Why in Optimistic Learning part, you are learning the LCB for the cost? I know some of the paper uses UCB for the cost and some uses LCB. Can you provide more details why using LCB? How does it compared to UCB?\n\n3, If I understand correctly, is the $Q_t$ similar to the idea of lagrange multipliers? Does the expectation of $E_x$ taking the expectation over all the historical data?\n\n4, Why uses (7) to find the optimal policy instead of selecting the argmax of the L?\n\n5, Why including the $\\Delta_t$ in the regret bound in Lemma 5.3? Where does it come from?", "methods_and_evaluation_criteria": "Yes. But only includes one dataset.", "theoretical_claims": "Some of them are mentioned in Claims And Evidence*. \n\n1) why the error of the reward is $\\tilde{O}(1)$ in Line 312 Left column.", "experimental_designs_or_analyses": "Yes. The experiment section makes sense to me.", "relation_to_broader_scientific_literature": "It contributes to the bandit under the safety constraint, provide an algorithm that has a lower regret and violations.", "essential_references_not_discussed": "The paper doesn't discuss the contextual bandit under stage-wise constraint.", "other_strengths_and_weaknesses": "See above.", "other_comments_or_suggestions": "I feel the writing can be more clear, including what is the Slater’s condition, how does it connect to your method. Also, page 6 left column is a bit hard to follow, maybe provide more takeaway or remark will be helpful.", "questions_for_authors": "See above.", "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": "Qckef2HWob", "reviewer": "Reviewer_38bH", "summary": "The paper introduces Optimistic³, a triple-optimistic framework for stochastic contextual bandits with general constraints. The main contribution is that it achieves regret and constraint violation bounds of without requiring Slater’s condition. It is applicable not only to general constrained contextual bandits but also to classical multi-armed bandit scenarios. Experiments are conducted using the real dataset comparing Optimistic³ with previous approaches, showing empirical advantages.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's comments and want to address your major concerns below.\n\n- **Table reference (Guo \\& Liu, 2024).** We adopt a row-wise split in referencing their work to properly represent their work, as their unified algorithm delivers distinct theoretical guarantees across two regimes: (i) a Slater-free setting yielding $\\tilde{O}(T^{\\frac{3}{4}})$ bounds for both regret and constraint violation, and (ii) a Slater-satisfied regime achieving sharper $\\tilde{O}(\\sqrt{T}/\\delta^2)$ guarantees.\n\n- **The Slater's condition.** The Slater condition assumes the existence of a strict feasible solution and is a standard assumption in constrained optimization. While our analysis does not explicitly rely on this condition (its elimination constitutes a key theoretical contribution), we acknowledge the need to formally define it and have included this in our revision.\n\n- **Clarification on $\\tilde{O}$.** The notation $\\tilde{O}$ suppresses logarithmic factors, which is consistent with the state-of-the-art works. We will explicitly define it in our revision.\n\n- **Experimental setup.** Our experiments replicate the methodology in (Guo \\& Liu (2024)), where contexts are randomly sampled from the MSLR dataset to simulate customer arrivals. We have included a more detailed description in our revision.\n  We have conducted additional experiments to verify our results in non-contextual bandits with stochastic and adversarial constraints. Optimistic$^3$ outperforms all baseline algorithms in both settings, which aligns with our theoretical guarantees. Complete implementation details and supporting figures are available at [https://anonymous.4open.science/r/Test-25FA/additional_exp.pdf](https://anonymous.4open.science/r/Test-25FA/additional_exp.pdf).\n\nWe hope our responses have clarified the reviewer's concerns and that the reviewer can re-evaluate our work. Please feel free to share any additional feedback, and we will address it thoroughly.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No due to time limit.", "experimental_designs_or_analyses": "Yes, no obvious issue on experiments as the paper is largely theoretical.", "relation_to_broader_scientific_literature": "Its key contributions closely relate to and extend existing literature on both of contextual and non-contextual bandits under constraints.", "essential_references_not_discussed": "References are well discussed.", "other_strengths_and_weaknesses": "Strengths:\n- The theoretical results are robust and generalize well, effectively removing problematic dependencies.\n- The references listed are recent and highly relevant.\n\nWeaknesses:\n- Please see the suggestions below.", "other_comments_or_suggestions": "- A minor formatting issue is that the paper largely overlooks in-context citations.\n- The table referencing (Guo & Liu, 2024) is confusing due to unclear splitting across rows. I am not sure what they are referring to.\n- Including formal mathematical definitions of Slater’s condition and the Slater parameter would enhance clarity.\n- Explicitly clarifying the optimality hidden within the \\(\\tilde{O}(\\cdot)\\) notation is recommended, as precise descriptions are typically preferred in bandit literature. It is not clearly what is hidden in \\(\\tilde{O}(\\cdot)\\) now or if same things are hidden throughout. This is a major clarity issue of this paper, optimal vs nearly optimal.", "questions_for_authors": "Could the authors please provide additional details on the experimental setup? For instance, it would be helpful to explain explicitly how the context is generated. Additionally, is it possible to run a non-contextual version of the experiment to validate the claims made in Section 7?", "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 studies contextual bandits with general constraints, where the learner must simultaneously minimize regret and control constraints violations. The authors proposed a triple-optimism framework, and theoretically show that the proposed approach achieves $\sqrt{T}$-type bounds on both regret and constraint violations, without knowing the Slater's condition. The authors have addressed most of the reviewers’ concerns during the rebuttal, and the majority of reviewers are now leaning toward acceptance.
Decision: Accept (poster)