Contextual Multi-Armed Bandits with Minimum Aggregated Revenue Constraints
Authors: Ahmed Ben Yahmed
Hafedh El Ferchichi
Marc Abeille
Vianney Perchet
Venue: ICLR 2026 Poster (2026)
Keywords: Multi-Armed Bandit with Constraints
Exploration-Exploitation
Regret
Constraint Violation
Primary area: learning theory

Abstract: We examine a multi-armed bandit problem with contextual information, where the objective is to ensure that each arm receives a minimum aggregated reward across contexts while simultaneously maximizing the total cumulative reward. This framework captures a broad class of real-world applications where fair revenue allocation is critical and contextual variation is inherent. The cross-context aggregation of minimum reward constraints, while enabling better performance and easier feasibility, introduces significant technical challenges—particularly the absence of closed-form optimal allocations typically available in standard MAB settings. We design and analyze algorithms that either optimistically prioritize performance or pessimistically enforce constraint satisfaction. For each algorithm, we derive problem-dependent upper bounds on both regret and constraint violations. Furthermore, we establish a lower bound demonstrating that the dependence on the time horizon in our results is optimal in general and revealing fundamental limitations of the free exploration principle leveraged in prior work.

Published as a conference paper at ICLR 2026
CONTEXTUAL MULTI-ARMEI BANDITS WITH MINI- MUM AGGREGATED REVENUE CONSTRAINTS
Ahmed Ben Yahmed! 12,3+, Hafedh El Ferchichi Mare Abeille & &Vianney Perchet! -2.3
1 Criteo AI Lab, Paris, France
2 CREST, ENSAE, Institut Polytechnique de Paris, France
3 FairPlay joint team, Inria, France
ABSTRACT
We examine a multi-armed bandit problem with contextual information, where the objective is to ensure that each receives minimum aggregated reward across contexts while simultaneously maximizing the total cumulative reward. This framework captures broad class of real-world applications where fair revenue allocation is critical and contextual variation is inherent. The cross-context aggrega- tion of minimum reward constraints, while enabling better performance and casier feasibility, introduces significant technical challengess-particulaayy the absence of closed-form optimal allocations typically available in standard MAB settings. We design and analyze algorithms that either optimistically prioritize performance or pessimistically enforce constraint satisfaction. For each algorithm, we derive problem-dependent upper bounds on both regret and constraint violations. Further- more, we establish a lower bound demonstrating that the dependence on the time horizon in our results is optimal in general and revealing fundamental limitations of the free exploration principle leveraged in prior work.
INTRODUCTION
The Multi-Armed Bandit (MAB) problem provides a foundational model for sequential decision- making under uncertainty (Thompson 1933; Lattimore and Szepesvári, 2020 Auer et al., 2002 Bubeck and actions (arms), each yielding stochastic rewards, with the goal of maximizing cumulative reward. central challenge is to balance exploration-gaaherrii information about unknown rewards and intoiitationn-everaainn current knowledge to optimize performance. Many variants and extensions of the synthetic bandit framework have been proposed to address specific challenges arising in real-world applications. In particular, for clinical trials, stringent safety constraints require the selection of treatment- dosage dosage combinations that balance efficacy with the mitigation of adverse effects (Chen et al.] [0026]] Pacchiano et al.] [021 Amani et al.) 2019). Similarly, budget- budget-constrained maximize cumulative rewards while adhering to a fixed resource allocation (Badanidiyura et al., 2018 Chzhen et al. 2023). Additionally, fairness considerations may impose further constraints, such as ensuring equitable exposure across arms (Wang et al., 2021 Li ct al., 2020) or guaranteeing minimum revenue thresholds for each arm (Baudry et al. 2024). Those settings require to extending the MAB framework to accommodate
2012). At each step of a T period run, an agent selects one of K
scenarios give rise knapsuck bandits, where the objective
with reward maximization under various constraints.
We investigate a contextual MAB problem subject to per-arm minimum revenue guarantees. The learner's 's objective is to maximize the cumulative reward over time while ensuring that, on average, each arm A achieves a reward of at least Xạ. a predefined minimum aggregated reward over all contexts. The learner must balance the trade-off between selecting the best arm in a given context and favoring a suboptimal arm to ensure it meets its minimum revenue requirement. As illustrated in Figure [ depending on the problem parameters, different regimes can arise: (i) infeasibility, where the constraints cannot be satisfied; (ii) feasibility with high cost, where satisfying the constraints requires playing significantly suboptimal arms; and (iii) feasibility with moderate cost, where the performance gap is small and balancing reward and constraint satisfaction is relatively easy. This rich setting is motivated by several real-world applications. For instance, consider a movie recommendation platform that collaborates with multiple content providers. Each provider offers catalog of movies spanning various categories, such as action, romance, and comedy. Users interact with the platform
*Correspondence a.benyahmed@criiee cecotmme@@@crittccoom

---

Published as a conference paper at ICLR 2026
by selecting category, and the system recommends movie accordingly. While the platform aims to match users with the most relevant content (i.e., to maximize the reward), it must also ensure that each provider receives minimum level of user engagement revenue. This guarantee is essential to maintain providers' incentives for participating in the platform.
Amm 2
Means ja
0.8
0.6
0.4
0.2
0
3
5
7
9
10
Contexts
Figure 1: Illustration of MAB problem with minimum aggregated reward constraints with two arms and multiple contexts. Arm is optimal in all contexts. We fix the threshold A for arm I and consider how different thresholds X for arm 2 change the problem. If X2 A/ the problem becomes infeasible. If X2 X then arm 2 must be played frequently in contexts c 2 6, which
substantially reduces overall performance due the large performance gap. However, if X2 x² it is sufficient to play arm 2 in contexts S 5, where the performance gap is small, thus preserving overall reward.
1.1 RELATED WORK
Motivated by the demands of world applications, several extensions the MAB framework have been proposed (hun Kim et al., 20224] Ben Yahmed et al. 2024a b). The problem studied in this work belongs to the broader class of constrained bandit problems, which have been investigated under various motivations such as safety (Chen et al., 2022b), fairness (Wang al. 2021 return-on-spend guarantees (Feng et al. 2023), conservative behavior (Wu et al. 2016 Deb et al. (025), and knapsack
constraints (Badanidiyuru al. 2018 Bernasconi et 2024
Constrained bandit problems has been studied under two distinct perspectives: a first stream of research focuses on hard constraints where violations are strictly prohibited, for instance in the linear constrained bandits setting (see (Pacchiano et al. 2021; Amani et al. 2019)). These approaches require prior knowledge of a feasible (safe) policy and employ carefully constructed pessimistic confidence sets to maintain zero constraint violation while achieving O (VVT) regret. An alternative approach relaxes the initial safe action requirement, allowing round- round-wise constraint violations while studying the fundamental trade-off between performance and constraint satisfaction, the two central metrics in constrained bandit problems. Notably, (Chen et al., 2022b) developed two algorithms for the non-contextual MAB setting: the first achieves O ((VT) regret with logarithmic constraint violation, while the second exhibits the inverse behavior. (Gangrade et al.] 2024) introduced an algorithm for safe linear bandits to learn the optimal action defined by max 8* s.t. Ar b,
achieving poly-logarithmic regret with ((VT) constraint violation.
Bandits with knapsacks (BwK) have been extensively studied (Tran- Thanhh et al. 2012 Badanidiyuru
al. 2014 Sivakumar et al. 2022 Kumar and Kleinberg, 2022 Han al.] 2023 Slivkins al.
2024
Guo and Liu 2025). Notably, Agrawal et al. (2016) extend BwK to contextual settings using the optimization framework of Agarwal et al. (0144, incorporating constraints via a primal-
approach to achieve ((VT) regret. Chen al. 2024h consider related contextual decision-making -makin framework with knapsacks, but under a different feedback structure. In their model, reward and cost functions are known and depend on a random request, an external random variable, and the chosen action. Building elegantly on network revenue management techniques (Chen et al. 2022a Balseiro cet al., 2024), they employ a re-solving method conceptually similar to ours, providing guarantees for both full and partial information regimes, including beyond- wooonddwoott-ase analysis. A fundamental distinction between our setting and BwK lies in the nature of constraints: in BwK, costs accumulate until a fixed budget exhausted, ensuring hard constraint satisfaction, whereas constraints stochastic and enforced in expectation, permitting explicit trade-offs between regret and constraint violation.
2

---

Published as a conference paper at ICLR 2026
A special case of our setting is the context-free MAB with per-arm revenue guarantees studied in [Baudry et al.] (2024). Here, the optimal strategy pulls all arms linearly, proportional to their ratio. The authors propose learning strategies using optimistic/pessimisiic estimators: optimism improves rewards but increases constraint violation, while pessimism has the opposite effect. They demonstrate trade-off between constant regret with (vTT) violation or vice versa, improving on Chen et al. (2022b). This constant regret is possible due free exploration from the optimal allocation's 's structure.
caurantee-to-eeroommen
A generalization of our setting is the stochastic contextual bandit problem under general constraints, considered by (Slivkins et al. (023). Assuming strict feasibility characterized by known Slater constant y", they introduce a primal-dual optimization algorithm and establish O O(VT/>" upper bounds on both regret and constraint violation. (Guo and Liu 2024) extend this setting by removing the Slater condition, proving (TT5/4) bounds for both regret and constraint violation. Furthermore, when Slater's condition does hold, their method achieves improved bounds of O(VT/>"3 notably without requiring prior knowledge of y* The recent work of (Guo et al. 2025) considers exactly the same setting and assumptions as (Guo and Liu 2024). but proposes an algorithm that integrates a primal-dual approach with optimistic estimation, yielding (VVT) bounds on both metrics.
1.2 CHALLENGES AND CONTRIBUTIONS
How to leverage contextual information while preserving revenue guarantee for each arm is challenging (and open) question (Baudry et al.) 2024). The reason is that most contextual learning problems can be reduced bandit problem reduces to many standard multi-armed bandits (Perchet and Rigollet] 2013). where the optimal decision can be computed based solely on the reward functions. context by context. With revenue constraints, this would be possible if the latter were defined context-wise - i..., by specifying At.e for all pairs (k:, c), and would result in straightforward extension (by considering |C| parallel instances). Unfortunately, with aggregated constraints, this local reduction is impossible: it is not enough to learn that an arm is sub-optimal for a given context; what really matters is how much sub-optimal it is compared to others, so that global planning can be computed. Even the planning problem becomes more complex with global constraints; we shall show that it can be reduced to solving linear program, which preserves computational efficiency but sacrifices the closed-form solution that played a central role in the theoretical analysis of (Baudry et al. 2024).
family of "local" independent problems. For instance, a contextual
While the works of (Slivkins et al. 2023 Guo and Liu 2024 Guo et al. 2025) address contextual
MAB problems that subsume our setting, we claim that their primal-dual approach Shich which guarantees (VT) bounds for both performance and constraint regret- is suboptimal in our case, as overlooks the finer structure inherent our problem formulation.
Consequently, our work is the first to bridge the gap between the non-contextual MAB with minimum revenue constraints studied in (Baudry al., 22024), and the contextual MAB frameworks with general
stochastic constraints explored in (Slivkins et al. [2023] Guo and Liu 2024 Guo et al. 2025). We achieve this by introducing novel approach that circumvents the absence closed-form solution to the planning problem, without relying on the primal-dual methodology, Our main contributions are the following:
1. We introduce two novel algorithms, OLP and OPLP, that seamlessly integrate linear programming with optimistic and pessimistic estimation techniques. These algorithms effectively navigate the trade-off between performance and constraint satisfaction, each capturing distinct points along the Pareto frontier of these competing objectives. They provably achieve poly-logari regret with O(VT) constraint violation, and vice versa.
2.
The analytical techniques employed in this work are non-standard and may be of indepen- dent interest to the MAB literature. particular, we derive poly-logarithmic bounds by introducing novel and more refined notion of the sub-optimality gap, which leverages the structure of the underlying linear program and quantifies the complexity of learning the optimal policy. The proposed methodology extends naturally to wide range of MAB problems that require enforcing global linear constraints.
3. We establish lower bound that confirms the (near) optimality of our algorithms and highlight a more intriguing interpretation of the exploration exploitation trade-off in MAB with revenue guarantees. While non-contextual setting enjoys a free-exploration property
ipploratio-exploitation
3

---

Published as a conference paper at ICLR 2026
inherited from the constrained structure, this no longer holds in the contextual setting, where the exploration-exploittieee trade-off is reinstated.
PROBLEM STATEMENT
Notations Let denote generic quantity of interest. We use the notation Ok,e E R represent the value associated with arm k in context c. The vector a, (I...)) in R collects these values across arms for fixed context c, and the matrix a = (Et..)) all arm-context values. We denote by (t,e ac(t), and a(t) the time-dependent versions of these quantities at round t. We denote by e& the matrix in I x with a in the (k, k--th position and zeros elsewhere, and by e₁ the k-th canonical basis vector in Ix The set of arms is KC = {......A and the set of arm-context pairs is J {(k: c)
in Rx gathers
K, E C). with total cardinality K K|C).
Finally, т denotes the K ---imensional probability simplex, "K denotes the set of K x |C' matrices whose columns each belong to the simplex Tx. (z)+ = max( 0) represents the positive part of z. and [S] stands for the cardinality of set S.
2.1 SETTING
We study a multi-armed bandit problem involving K stochastic arms and a number of contextual scenarios. Let C' denote the set of all possible contexts where each E C occurs with probability pe- The expected reward of arm & in a given context e is represented by Pk.e.
At each time step the learner observes text C, selects an arm hy E K and receives a re- ward rts which is independently drawn from the distribution Dx. At each time I, the choice of the arm is based on history of past interactions H4-1 (C1, k1, .t-1: Ct-1,1111 k and cur-
MAB-ARC: MAB with Aggregated Revenue
Constraints
Inputs: {Ax hee
for t = 1 to T do
Observe context 6;
Choose arm kt
rent context Ct- The interaction structure of this Multi-Armed Bandit with Aggregated Revenue Con- straints (MAB-ARC) is summarized on the right.
Receive reward T; ~ Hke.e Update He Hi-1 U (ce, ke,
The learner aims to maximize the expected cumulative revenue over '" time steps while ensuring that the expected aggregated revenue from each arm over all contexts larger than a predefined threshold Ape
Planning Problem. Formally, given known thresholds d and mean reward μr, the optimization problem is defined as:
T Σ
T Σ rel re
OBJ: : max Je..........
E
rt
subject to: Vk E K, E
2 AgT.
Optimal solutions to this constrained optimization problem consist in policies, i.e. allocation rules that map the current context to the probability of sampling an arm. We summarize allocation rules by w, where Wk.e [k]cc.. Interestingly, there is in general no unique optimal solution to OBJ - but of time-varying allocation rules, of the form (w=(tt) (t))sT. Indeed, the objective and constraint criteria do not penalize strategy that periodically violates then over-satisfies the constraint as long as it remains met over the whole trajectory. In contrast, an optimal stationary solution, denoted by w", would ensure uniform performance and constraint satisfaction over the trajectory. This stability is crucial in applications where constraint satisfaction is monitored over sliding windows, or where oscillatory behavior must be strictly avoided, such as in clinical medical trials. Interestingly, an optimal stationary policy can always be derived from an optimal time-varying one by leveraging the (t)
linearity of the problem and the use of expectations, constructing w= J
We focus from now on the stationary solution of the planning problem, which can be reformulated as solution of the linear program:
LP obj cone): max
s4 w))
with s(u, w) = Σ Pe oot we
t. D& (1 cons w/) 2 Ats EK,
(H w) =E= Ecec Pe u W.
hu w) 2 0. V(k, c) E J.
ha(c,w) el We, (e(w) 1 T We
(ww) = 1, Vcc E C,
4

---

Published as a conference paper at ICLR 2026
Namely, f denotes the expected total revenue; 9& represents the expected aggregated revenue of arm over all contexts; ( (c, w) = Wikcc the probability of selecting arm & in context c; and 9, is the noom of w. used to ensure that the vector lies in the K -d-dimensinal probability simplex. Hence, the optimal stationary allocation wT is the solution to (,, p4) and sampling arm according to the optimal weights w upon observing context yields the optimal strategy of interest for OBJ.
Learning Problem. At each round I, the learner utilizes the available information Hz-1 U Ct. and selects arm according to learned allocations w(t). To evaluate the performance of the learner's algorithm, two key metrics are considered: the performance regret and the constraint violation.
Definition 1. The cumulative regret RT and the cumulative constraint violation VT are respectively defined as:
RT Σ ((,,,")) f(H, ((())(())) VT
Σ
Σ
(x (e ((())
The positive part accounts only for non-negative deviations and its role is twofold. First, it favors stable long-term behavior and prevents convergence to optimal time-vane varying allocation. Second, penalizes strategies that oscillate during the learning between being overly conservative and severely violating the constraints to ease the exploration, hence favoring a tracking w" in a round wise stable manner.
2.2 ASSUMPTIONS
We rely on the following standard assumptions, which concern the stochastic nature of the setting and the feasibility of the associated planning problem. Assumption 1 (Sub-Gaussian rewards). The reward distributions conditionally
(1²
vb E R, E exp (b - -Err (ct,ka)))) | ka) S exp
2
Assumption (Known Contexts Probabilities). The contexts probabilities {peleec are known.
We adopt the same context prior assumption as Guo et al. (222)), which is here mild and used primarily for expository simplicity. In Section 7 we discuss straightforward relaxation of this assumption.
Assumption Feasibility and Non-degeneracyy. The optimization problem LP LP( is feasible and non-degenerate.
Assumption 4 (Strict Feasibility and Non-degeneracy). The optimization problem LP( p1) is strictly feasible and non non-degenerate.
Assumption is specifically required for OPLP, with the corresponding feasibility margin quantified by y². In contrast, OLP only requires Assumption B and its guarantees are independent of the slack parameter y*
Definition (Feasibility Margin).
[c] 7" max {s E R (s) () + 0}, where ((s) E T
Vk K, gk (M, w) 2 d + +
In addition, we quantify the sensitivity the optimal performance w.r.t. uniform constraint perturba- tions through problem dependent constant S.,,, intrinsically linked to the feasibility margin. We prove Appendix B Prop. B.1 that S.,- < oc for any MAB-ARC instance satisfying Assumption 3
Definition (Performance Sensitivity Coefficient).
Sy, min(S e R4 4A s1 St', max f(u, w) wE(b(a1)
max f(w,w) S S(22 $1)
wE
For brevity, we adopt the shorthand: wn arg max LP 11)

---

Published as a conference paper at ICLR 2026
3 GRACLE-GUIDER BEHAVIOR AND OPTIMALITY CHARACTERIZATION
Proper Tracking of the Optimal Planning. The problem formulation yields linear program (LP) optimizing allocations over the probability simplex, whose solution lies vertex determined by binding constraints (Boyd and Vandenberghe 20044, Nesterov 2014). The characterization of the optimal solution can thus be decomposed into identifying the optimal active set of constraints I for (P
pr, pe), then computing the best allocation that saturates these constraints. More precisely:
(i) If k E I" n K,K, then Ihe (1,, w²) Ag. indicating that arm & exactly attains its minimum required revenue.
iii) If (k, E I* n', then wx) = 0, which implies that arm & is never selected in context e, i.e., " O.
Consequently, the oracle effectively solves the optimization problem (p, na. I"). defined as:
Op 0bj L con' I):
maximize
fl w)
subject to
Db (11 (w) = AK AREKNZ,
h2 (c, w) = 0,
go =1, VCEC.
Directly quantifying the sub-optimality of an allocation w w.r.t. w² is challenging due to the linear nature of the allocation problem. Yet, the introduction of the intermediate quantity I allows us to retrieve notion of gap, similarly standard MAB problem. In what follow, we define p(Z) which quantifies the sub-optimality of candidate set I. p(I) will play key role in showing that I* can be quickly identified by learning strategy.
Optimality Characterization. One form of sub-optimality arises from aafcasibility-thal is, the absence of any allocation that satisfies the constraints in We formalize this as follows.
Definition (Feasibility Gap). For any set I, define:
s(I) = min {s 2 0
Is 0} where:
W K. gk ( w 2 A - Yk EKE
(s = w
T
IC
Ih (M, w S A +
C ha
w)
The quantity s(I) captures the minimum slack required to make the revenue constraints feasible while saturating up to some margin- the arms in K. n I and satisfying the allocation sparsity prescribed by I nI (i.e, the set of (k, e) s.t. Wh.c = 0).
Beyond feasibility, we also quantify sub-optimality from a performance standpoint.
Definition 5 (Performance Gap). For any candidate set I, define the performance sensitivity L(I) and the performance gap PII) as:
CT)) == min{f E RR VT S 81 < 82, max [1,, w)
max [(1, un) S L(82 81 } (E
WEV(s2.7)
P(Z)= = ((()=))) (X))
The denominator of PII,, beyond its technical role the proof, can be interpreted as a scaling factor that reflects both the geometry of the candidate set I and the problem's 's sensitivity to perturbations. Proposition B.2 in Appendix shows that, for any candidate I, L(I) is finite Combining feasibility and performance considerations, we define the overall sub-optimality gap as follows:
Definition 6 (Sub-optimality Gap). For candidate set I, the sub-optimality gap is defined as p(Z) == max (IT)),((I)) with the worst-case sub-optimality given by p² == min p(I).
I.I+I
This characterization enables distinguishing optimal from suboptimal sets of saturated constraints.
Lemma 3.1 formalizes this, showing that p(I) plays a role analogous to the gap in classical MAB. The proof's is deferred to Appendix B.I
Lemma 3.1 (Suboptimality Characterization), Under Assumption 3
p(I*) and p" > 0.

---

Published as a conference paper at ICLR 2026
4 ALGORITHMS
The learner's objective is to find the optimal allocation w² without prior knowledge of the true parameters μ.. While estimates can be constructed from data, the agent must carefully trade-off between exploration and exploitation. We summarize in this section the confidence set construction and our proposed strategies that focus either on performance or on constraints satisfaction.
Confidence Set. The unknown parameter can be estimated online from past interactions with a standard empirical mean, formally given by:
(1) (1),e(t) Σ rs c,,c) where (1) = Σ [k.
(I)
Further, the concentration of the empirical estimator prescribed by the set
2 log 2g
S.(p()).)) {p= V(k, c), (1)),(()) - /kk,cl (t)) with (k,((t)
Proposition 4.1 ensures that S, is valid confidence set for and provides prediction error bounds on the performance and constraints violation. The proof is deferred to Appendix C Proposition 4.1 (Confidence set). Under Assumption let (t) and St defined in Eq.
7 and
then:
11 2 1, P (μ E S,(P()) 8)) 2 1 - 5,
ICI 8, for any w E T ((() E S,(i((),)) and & EKK
14 > 1, w.p. at least
19 (T)(), w - gu μ1, w) S (E(())), w)
where
pk (x w) E EEC 2en,(t)uuk,o(t)
[f((()), w f(, w) S p(E(t), w
plc(t), w) ExE(x] Pa(c(t),
Equipped with the confidence construction, we define the upper and lower confidence bounds as UCB(t) = (tt + e(t) and LCB(t) = (t() - Ett), both of which belong to (f)
OLP: Optimistic Linear Programming
OPLP: Optimistic-Pessimisiii Linear Program-
Inputs: (I...k( {Pelcee
ming
for
I....,TT do
Inputs: (Ax (E...E (PeJoec
Observe context
for = 1...., T do
Set 8
3
Observe context Ct
w(()=
argmax LP(UCB((). UCB(U) wEn
Set 6 + 1/c
s
if LP(UCB( LCB(I)) feasible then we argmax LP(UCB(I), LCB(L)
Sample arm k; wa (t) Receive reward ~ Pkg.
wEr CI
Update (2), (t()). (t)
end else
Update history H. = H:-1 U k1,
10 end
wc) argmax LP(UCB(t)) UCB (t)
wERK
We propose two algorithms that focus either on the performance or on the constraint violation. OLP adopts an optimistic approach by solving the underlying LP problem using UCB(t) as a parameter for both the objective function and the constraints. Under Asm. E the inner maximiza- tion problem remains feasible at all times.
end
Sample arm K2 we, (t)
Receive reward rt 1kk.
Update n2f), fa((), (t))
Update history H. He-1 U (et, rx,
end
On the other hand, OPLP proposes an asymmetric estimation strategy that leverages an optimistic estimate UCB(t) for the objective and a pessimistic estimate LCB(t) for the constraints parameters. In contrast with OLP, the inner maximization problem may not always be feasible. such cases, a fallback procedure based on doubly optimistic approach is used instead.
7

---

Published as a conference paper at ICLR 2026
5
MAIN RESULTS
5.1
ALGORITHM GUARANTEES
The following theorems provide regret and constraint violation guarantees for OLP and OPLP, highlighting their respective focus on reward performance and constraint satisfaction. The proof sketches are presented in Appendix while the detailed proofs are deferred to Appendix Theorem 5.1 (Upper bounds for OLP). Under Assumptions and the performance and con- straint regret of OLP satisfy:
log (T)
B 0
log (T)
E s O
+
KINI log (T)
Theorem 5.2 (Upper bounds for OPLP). Under Assumptions constraint regret of OPLP satisfy:
7 and the performance and
(
1
[(Rr] 0
log (T)² v VIKnz 1 log (T)T)
D²?
B[y]] < 0
A
log (T)²)
where == Σ A
y22
REK
Discussion. OLP and OPLP enjoy regret guarantees that stand at two different points in the performance/coostraiin violation Pareto front. OLP prioritizes performance, achieving polyloga- rithmic regret, but may incur constraint violations as large as ((VT). Interestingly, its bounds adapt to the number of arms that saturate their minimum reward constraints. In particular, when no arm saturates its constraintPiic. |K I+| = O), we recover polylogarithmic guarantees for both regret and constraint violations. In contrast, OPLP emphasizes constraint satisfaction at the cost of performance. Its theoretical guarantees depend on richer set of problem-dependen constants. In Theorems 5.1 and 5.2 p* characterizes the speed at which each algorithm converges to the optimal set of saturated constraints, i.e., the point at which Z₁ = I² The constant ?" which appears only in OPLP arises from its intrinsic phased structure and quantifies how fast LCB becomes feasible. The pessimistic strategy ensures a more conservative treatment constraints by incorporating safety margins. However, this comes at the expense of performance, portion of the allocation budget is diverted from non-saturating (typically high-reward) arms to those saturating their constraints leading to V loss in performance.
5.2 LOWER BOUND
In line with previous works in the non-contextual setting, OLP and OPLP enjoys a cumulated guarantee on + V of order VT. On the other hand, the performance (resp. constraint violation) regret bound for OLP (resp. OPLP) is only logarithmic, in contrast with the no-regret (constant) guarantee of (Baudry et al., 2024). We propose in this section lower bound which stresses this is not due to algorithmic design analysis weaknesses but structural to the MAB-ARC setting. In particular, this refutes the free exploration property leveraged prior work as soon as [C] > 1 and
K >>> 2.
Let (,, (Petaec) represent generic MAB-ARC instance, and denote by R2 (T) and (T)) the performance and constraint re- gret under policy æ on instance v. We consider nominal instance z0() with K = arms and |C| 3 contexts as well as set of nearby in- stances ((, =) defined in Table. and Eq. 3 respectively.
Table 1: Nominal instance (0))
k
Pe Pk.c
À
c
C c=2
11,1 =
[4, = 1
M1,3 =
1
2
N2,1
P2,2 =
122.3
3
#3,1
M3.2 0
13.3 2
i
T(p (()()) f (n, A (0) (p_ Jc) p2
12,2
12,2
(0)
2
otherwise Pkke
Mk,e
(0)
(3)
This when the revenue constraints are small compared the optimal performance of each
8

---

Published as a conference paper at ICLR 2026
Theorem 5.3 (Lower Bound). Let v and Tv) E) defined in Table and Eq.
then
(i) For T 2 16, there exists gy small enough such that:
E Ru (T) + Vu, (T)] =T) (VV)).
min (ET ,52)
max
(ii) For any consistent policy E To 2 S.t. A T To.
E [R (T)] = S2 (log T).
Discussion. Theorem 5.3 establishes two distinct results (the proof is deferred in Appendix F.I The first assertion proposes a locally minimax lower bound around the nominal instance (0) and confirms that no strategy can enjoy a cumulated regret R. + V uniformly better than /T in a neighborhood of (0), There always exists a nearby alternative which suffers from large performance (R) or constraint violation (V)) regret. Such result offers finite time counterpart to the asymptotic lower bound of 2024 extended to the contextual setting but limited to the instance (0))
(Baudry et al.
Theorem 5.3 (i) indicates that both OLP and OPLP offer the correct vT dependency (but for
logarithmic factor) for the overall regret R + V but leaves open the question of whether the pair (R, V) is optimally positioned in the performaance/oontrrint violation Pareto front. Indeed, in the non-contextual setting, constant performance regret and vT constraint violation is attainable.
The second assertion (ii) rules out this possibility in the contextual setting and shows that no policy can offer better guarantees than VT constraint violation and log(T') performance regret for the instance (0), This demonstrates the near-optimality of OLP with respect to I but more importantly refutes the possibility of free exploration in the contextual setting. This is in shark contrast with the non-contextual setting where all arms sampled linearly with T, property heavily exploited in (Baudry et al., 2024). In MAB-ARC, optimal allocations may assign zero probability to certain arms, meaning that natural exploration occurs, which reinstates the exploration-exploittiin trade-off. Notice that while (0) exhibits such optimal allocation structure, the following lemma ensures this is shared among a large family of instances. The proof of Lemma 5.1 is deferred to Appendix F2
Lemma 5.1. For any MAB-ARC instance such that K and |C| 1, there exists at least one pair (k, E for which the optimal allocation satisfies w = 0.
Numerical Illustrations. For completeness, we conduct numerical evaluations on synthetic data to concretely illustrate the concept of I and to compare our algorithms with Optimistic from Guo et al. (025)) well as with DOC and SPOC from Baudry et al. (2024). We further examine the sensitivity of the OPLP algorithm with respect to variations in >" Complete experimental details and results are provided in Appendix G
COMPUTATIONAL COMPLEXITY
Saving Computation: To reduce computational cost, we employ lazy update scheme. Rather than solving the LP in every round, the policy is recomputed only when the number of pulls for any arm-context pair has doubled since the last update. Between these events, the confidence bounds and resulting policy remain unchanged. This ensures that the LP is solved at most Oloo I') times over the horizon T' yielding substantial computational savings while preserving the original regret guarantees up to constant factors. Detailed implementation and theoretical justification provided in Appendix
Computational Overhead and Practical Deployment: Our method requires solving a linear program frequently, resulting in a higher per-iteration cost than the gradient-basse approach of Guo et al. (025). However, their computational efficiency is achieved the expense of weaker theoretical guarantees. Consequently, practitioner faces a clear trade-off: stronger theoretical guarantees (ours) versus greater computational efficiency [uoo et al. 20025). The choice between them depends on the specific priorities of the application. From practical standpoint, the computational burden of our approach can be mitigated through several techniques. Modern LPP solvers reduce overhead via presolve to simplify problems and warm-starting to prior solutions of similar LP. Furthermore, solver tolerance can be relaxed to match the statistical confidence width of reward estimates, avoiding unnecessary precision without impacting practical performance.

---

Published as a conference paper at ICLR 2026
7 LIMITATIONS AND FUTURE WORK
Assumption 2 is mild and can be relaxed through appropriate empirical estimation. The key insight is that the estimation target shifts from the conditional reward Ui,e the product Ur.c = PeMk,es which integrates the context probability. Once optimistic and pessimistic estimators for u'g, are constructed, they integrate directly into the OLP and OPLP frameworks. However, effective estimation in this case requires additional smoothness assumptions on the context distribution. We anticipate that similar theoretical guarantees can be obtained through direct adaptation of our analytical techniques.
Context Prior:
Infeasibility Issue: If Assumption 3 is violated, infeasibility of LP(,,, u)) is detected with high probability when the optimistic counterpart LP(UCB, UCB) is infeasible. While no unique corrective procedure is prescribed, standard recourse is relax the problem to find the closest feasible approximation. A possible strategy is to iteratively scale the constraint thresholds until feasibility is restored, for instance, via the update A ad,; where a E (0,1) is judiciously chosen scaling parameter.
Beyond the optimistic and pessimístic strategies discussed in this paper, the greedy policy is well-known but inefficient in the contextual setting. In the single-context case [audry al. (2024), it achieves sublinear regret as constraints enforce exploration: satisfying per-arm revenue constraints requires playing all arms, improving estimates over time. In contrast, in the multi-context setting, constraints do not inherently induce exploration- a counterexample illustrating this is provided in the Appendix 0
Greedy Policy:
Extending our framework to infinite context or action sets a compelling direction for future work. Conceptually, the OLP and OPLP approaches are based on constructing optimistic or pessimistic reward estimates and then solving a linear program defined by expectations with respect to the context distribution. Technically, efficient reward estimation in infinite spaces requires structural assumptions to ensure tractability. A standard approach to posit a linear model of the form Mk.e (6*, @kk, e)), where is known feature mapping. Using established results from linear bandit theory, one can then derive efficient optimistic and pessimistic reward estimates for all context-action pairs. Alternatively, kernelized methods could be employed by assuming the mean reward function lies in a reproducing kernel Hilbert space (RKHS), which also enables the construction of practical confidence estimators. Once such estimators are available and the corresponding LP can be solved, we anticipate that a theoretical analysis analogous to ours could be developed. However, this would also necessitate research into discretization techniques or heuristics for solving the resulting optimization problem efficiently, accompanied by formal analysis of the induced approximation errors. While highly interesting, this comprehensive extension falls outside the scope of the present paper multi-armed bandits, as it constitutes a separate research centered on linear and kernelized bandits.
Future Work:
CONCLUSION
We introduced a novel contextual bandit problem with minimum aggregated reward constraints, along with analytical tools tailored to the structure of this constrained optimization problem. We proposed two algorithms that explore different regions of the Pareto frontier-one favoring performance, the other emphasizing constraint satisfaction. Our upper bound analysis highlights the adaptability of the proposed approach across regimes with both saturating and non-saturating constraints, outperforming standard linear bandit models that rely on self-normalized concentration inequalities and fail to capture the fine structure of the problem. We also established lower bound that confirms the near optimality of our upper bounds and challenges the previously leveraged notion of free exploration in the non-contextual setting. While our primary focus is on guaranteeing a minimum aggregated revenue per arm, the algorithmic and analytical framework generalizes naturally to broader constraint structures, such as ensuring that the cumulative reward from subset of arms exceeds given threshold-a formulation relevant in generic monitoring problems.
10

---

Ahmed Ben Yahmed, Clément Calauzènes, and Vianney Perchet. Strategic multi-armed bandit problems under debt-free reporting. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Advances in Newral Infor- mation Processing Systems, volume 37. pages 106105-106134, Curran Associates, Inc.. /iles/ppperr/222 Published as a conference paper at ICLR 2026
REFERENCES
Alckh Agarwal, Daniel Hsu, Satyen Kale, John Langford. Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31st International Conference on Machine Learning. volume 32 of Proceedings of Machine Learning Research, pages 1638 1646, Bejing, China, 22-24 24 Jun 2014. mlr www. press wttpp//sss././/aaaaaaaaaaaaa http//aaawwwabaaaa [httr
PMLR.
Shipra Agrawal, Nikhil R. Devamur, and Lihong Li. An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 4-18, Columbia University, New York, New York, USA, 23-26 html
Jun 2016. PMLR. URL hattpp::/ppoceeddingg. mlr www.ppressspp.. wtt.a//eeeees//////aaaaaaaa
Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. In H. Wallach, H. Larochelle, Beygelzimer, F'Alcéé-Buc, Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL 2015//fiee//aaa887776aadeeeeeeee
Paper.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-256, 05 2002. doi: 10.1023/A:101336970000
Ashwinkumar Badanidiyuru, John Langford, and Aleksandrs Slivkins. Resourceful contextual bandits. In Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pages 1109-1134, Barcelona, Spain, 13-15 Jun 2014, PMLR. URL httl:tttt///sceeeeeeeet html
mlr
prrss//335/adaniddi
Ashwinkumar Badamidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. J. ACM, 65(3). March 2018. ISSN 0004-5411, doi: 10.1 10.1145/3164539, URLpttpp://doo..org 10.1145/3164533
Santiago R. Balseiro, Omar Besbes, and Dana Pizarro. Survey of dynamic resource-constrained reward collection problems: Unified model and analysis. Operations Research, 72(5):2168-2188 September 2024. doi: 10. 20.128770pr. 2023. 2441. URL. httts:://ddest repec. aapec.org org/a/
htmm/rropre//22y22222244 20ppp2211111111 .html]
Dorian Baudry, Nadav Merlis, Mathieu Benjamin Molina, Hugo Richard, and Vianney Perchet. Multi- armed bandits with guaranteed revenue per arm. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li, editors, Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 379-387, PMLR, 02- 04 May 2024. URL https: http::///ooceeedieeee ngs ml prrss v238 baudrr24ddrrraarr html
www.:ssserrrrrrsrsr....aoo f 1aee
2024a. URL
Ahmed Ben Yahmed, Clément Calauzènes, and Vianney Perchet. Strategic arms with side com- munication prevail over low-regret mab algorithms. In ICASSP 2024 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), page 7435-7439. IEEE, April 2024b. doi: 10. 10.1111111000 1099 222p::p4444888222...2222 10446894 URL http://tx.xpceeeeo http:://xxxdddiioo.o www.://o...oo.//...00/0011 1109/ ICASSP48485.0 2tt.:455522224.1144533
Martino Bernasconi, Mattco Castiglioni, Andrea Celli, and Federico Fusco. Beyond primal-dua methods in bandits with stochastic and adversarial constraints. In The Thihth- Annual Conference on Neural Information Processing Systems, 2024. URL MtLL:tttps///peeeeev// net:/ f -d= 1dd.d===1wwwWW
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
11

---

Published as a conference paper at ICLR 2026
Sébastien Bubeck and Nicolò Cesa- Bianchi. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012. ISSN 1935-8237. doi: 10.1561/22000000244,
Guanting Chen, Xiaocheng Li, and Yinyu Ye. An improved analysis of Ip-based control for revenue management, 2022a. URL / arrivv.vvv. www.wiwww.aaa..aaaa.ooo..oooootr abs/
Tianrui Chen, Aditya Gangrade, and Venkatesh Saligrama. Strategies for safe multi-armed bandits with logarithmic regret and risk. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepes- vari, Gang Niu, and Sivan Sabato, editors, Proceedings the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 3123-3148. PMLR, 17-23 Jul 2022b. URL https: h/tpps////pcccednnnss. ml www.smmm.....sssseee www.pprsssill... wt.pprsssww1./ccheene2 w2/ph/n2cccceeeeeee html
Zhaohua Chen, Rui Ai. Mingwei Yang, Yuqi Pan, Chang Wang, and Xiaotie Deng. Contextual decision-making with knapsacks beyond the worst case. In A. Globerson, I.. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Advances in Newral Information Process- ing Systems, volume 37, pages 88 88147-88193, Curran Associates, Inc., 2024. doi: 10.52202/ 079017-2798. URL https:: www.::iiiinnee.i...ie.omm.... wwwpppsrrccpppppppppppeeeeeeeee files/paper 2DD0///.w/A0aLec200000/////11312 ort.r/aoeesspppppprooooeeeeeeee.
Conference. ppf
Evgenii Chzhen, Christophe Giraud, Zhen LI, and Gilles Stoltz. Small total-cost constraints in contextual bandits with knapsacks, with application to fairness. In Thirly-seventh Conference Neural Information Processing Systems, 2023. httpttts/s//ppeeeeiieewe wwtp:/eefooorr.oo
1d=u2vGOHLKOE
Rohan Deb, Mohammad Ghavamzadeh, and Arindam Banerjee. Conservative contextual bandits: Beyond linear representations. In The Thirteenth International Conference on Learning Represen- tations, 2025.
net/ fttt:/oorumlld=SShtee
Roberto Mínguez Enrique Castillo, Antonio J. Conejo and Carmen Castillo. A closed formula for local sensitivity analysis in mathematical programming. Engineering Optimization, 38(1): 93 112, 2006. doi: 10. 10.10800033521155002224411 030521505002283
URL
Zhe Feng. Swati Padmanabhan, and Di Wang. Online bidding algorithms for return-on-spend constrained advertisers. In Proceedings of the ACM Web Conference 2023, WWW '23, page 3550-3560, New York, NY, USA, 2023, Association for Computing Machinery. ISBN 978 151839941... doi: 10. 00.145/354350.3388441.. 3543507. 3583491
URL https: /ttp://o....g../////// 1145/
Aditya Gangrade, Tianrii Chen, and Venkatesh Saligrama. Safe linear bandits over unknown polytopes. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 1755- 1795. PMLR, 30 Jun 00 Jul 2024. URL gangrade24a.io html
mlr. press/v247/ Strp
Hengquan Guo and Xin Liu. Stochastic constrained contextual bandits via lyapunov optimization based estimation to decision framework. In Shipra Agrawal and Aaron Roth, editors, Proceddings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 22204-2233 PMLR, 30 Jun-03 Jul 2024. URL BRRLattps//pppoeeed.im mir
press/v247/quo224 .hmll
Hengquan Guo and Xin Liu. On stochastic contextual bandits with knapsacks in small budget regime. In The Thirteenth International Conference on Learning Representations, 2025. URL https: https://oppereviiet net/ wttee//ooormmm1dFc0i000000
Hengquan Guo, Lingkai Zu, and Xin Liu. Triple-opimmistic learning for stochastic contextual bandits with general constraints. In Forty- International Conference on Machine Learning, 2025.
URL wtt.thppss//pppeeeeiieeeee wttp:/wwwwweeeeeoo/moooiioa.
fq
12

---

Published as a conference paper at ICLR 2026
Yuxuan Han, Jialin Zeng, Yang Wang. Yang Xiang, and Jiheng Zhang. Optimal contextual bandits with knapsacks under realizability via regression oracles. In Francisco Ruiz, Jennifer Dy, and Jan Willem de Meent, editors, Proceedings of The 26th International Conference Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages m htw.phhww............ppp.p www.ppresssseee
5011-5035. PMLR, 25-27 Apr 2023. URL
lbnn3bb.. html
Jung hun Kim, Milan Vojnovic, and Se- Young Yun. An adaptive approach for infinitely many- armed bandits under generalized rotting constraints. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024. URL
forum?
id=1 @d=1cxdndzkx))
Raunak Kumar and Robert D. Kleinberg. Non- mon-monotonic resource utilization in the bandits with knapsacks problem. In Proceedings of the 36th International Conference on Neural Informa- fion Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 9781713871088.
Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. ISBN 9781 108486828. URL https://books.. wttgg/e.r/bbooss..ddodaaaaaae.e.
Fengjiao Li, Jia Liu, and Bo Ji. Combinatorial sleeping bandits with fairness constraints. IEEE Trunsactions on Network Science and Engineering, 17991199), 2020, doi: 10.1109/ 2019.295430
Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer Publishing Company, Incorporated, edition, 2014. ISBN 1461346916.
Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, and Heinrich Jiang. Stochastic bandits with linear constraints. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2827 -835.. PMLR, 13-15 Apr 2021. URL https htmll
/pppoeeeiiggss... ml www...prreseee. wrwpsreesssss...
Vianney Perchet and Philippe Rigollet. The multi-armed bandit problem with covariates. The Annals of Statistics, (222),,9-77,, 2013.
Vidyashankar Sivakumar, Shiliang Zuo, and Arindam Banerjee. Smoothed adversarial linear con- textual bandits with knapsacks. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Confer- ence on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pages 20253-20277. PMLR, 17-23 Jul 2022. URL http::: httpp::/pproceciigg.... .ml...............m..........m.. www.s..preesvvv111 sivakumar22a. html
Aleksandrs Slivkins, Karthik Abinav Sankararaman, and Dylan Foster. Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 4633-463 PMLR, 12-15 Jul 2023. URL WR. htt.:tttt:///rooottett
ngs ml www.s//ssvv... . 95/ wow///23teeeee html
Aleksandrs Slivkins, Xingyu Zhou, Kanthik Abinav Sankararaman, and Dylan J. Foster. Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression, 2024. U 07484
www.
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):255-994,, 12 1933. ISSN 0006-3444, doi: 10.10993/biomee/5544255.....
285
Long ThanTThah, Archie Chapman, Alex Rogers, and Nicholas R. Jennings. Knapsack based optimal policies for budget-limited multi-armed bandits, 2012. URL CRLattps: httlaats///aiiiv.rrrt /oss/124..0 1909
13

---

Published as a conference paper at ICLR 2026
Lequn Wang, Yiwei Bai, Wen Sun, and Thorsten Joachims. Fairness of exposure in stochastic bandits. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pages 106966 PMLR, 18-24 Jul 2021. URL pletps://proceediin wttpp//w........./s.s/.e../.
ml wttpss/ve////e/eee.e.p
html
Yifan Wu. Roshan Shariff, Tor Lattimore, and Csaba Szepesvari. Conservative bandits. In
Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd Interna- tional Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1254-1262, New York, New York, USA, 20-22 Jun 2016. PMLR. URL https: https://proceddngs. mlr press/ /v88/ wul6 6 html
14

---

Published as a conference paper at ICLR 2026
APPENDICES
APPENDIX CONTENTS
Useful Inequalities
16
Oracle Behavior
16
B.1 Sub-Optimality Gap
17
Confidence Set Construction
18
Proof Ideas for the Upper-Bound Results
20
Upper-Bounds
21
Results of OLP
21
E.1.1
Regret of OLP
22
1.2
Constraints Violation of OLP
24
E,2
Results of OPLP
26
E.2.1
Constraints Violation of OPLP
26
F.2.2
Regret of OPLP
27
Lower Bound
30
Lower Bound Theorem
30
F2
Rich Family of MAB-ARC with No Free Exploration
33
Numerical Illustrations
34
G.I Sensitivity of OPLP to the Feasibility Margin
35
Lazy Update
36
Counterexample Demonstrating the Inefficiency Greedy Behavior
37
15

---

Published as a conference paper at ICLR 2026
A USEFUL INEQUALITIES
Theorem A.1 (Hoeffding's s Inequality). Let X1 XI..... Xn be a sequence of independent 1 I-subgaussian random variables with mean p.. Define it _i=1 X, Then, for any O, have:
TEE"
( 1 2 2 2xxp (-2
(4)
Fact A.1. For sufficiently large T, the following inequality holds:
ΣV. -2V
(5)
Fact A.2. For sufficiently large T, the following inequality holds:
Σ S log (T)+ +1++ (log (T))
(6)
B ORACLE BEHAVIOR
Lemma B.1. Let be the optimal solution of the problem OPT μt, J. The following property holds:
If ((.e)EnnI =0, then [EKKIz
Pk.c
||
In other words, for any arm in context e, if the optimal allocation probability Wkec is strictly positive (Wk.e 0) and the arm's revenue gk (H, w) exceeds its minimum constraint Å (i.e., (p, w) Axd,
then arm must necessarily be the optimal arm for context c.
Proof of Lemma B. The proof is based in the dual analysis of the optimization problem. Recall:
:):
maximize
f(u, w
subject to
gh gx w) AR: WeEnn
ha w) -0, (
(e(w)= =1 VCEC.
Let a. B, and 17 be dual vectors of dimensions K, K, and [C]. respectively. The Lagrangian function associated with the primal problem is:
L(w,a. (.1) f(u, w) + Σ an (9 (H, Ne)
Σ
Bechx (c, w) + Σ ne
(()((()) -
kEKnI
(k,c)EJnZI
= -mw, +
Σ
Orgl w. +
Σ
BEdhR w + Σ
(w))
Σ
AEcak Σ ml
kEKnI*
(K.)EENII
CEC
KEKCII
CEC
-En Me we Σ
O&k
Me ekuw.
Σ
BRoeg w. Σ
nel w.
Σ tle
cEC
kEKinI
(K.))EJNT
kERnI
Σ CEC
Me Tw
Σ
Me
Ou 1 peenz-Jen W.
Σ
1(0.00E5TE We Σ nol Two
w.
CEC
Σ XbaR
Σ 7e DEC
KEKNI
K
Σ cEC
Ho
O% (EEKIZ
+ Σ
Bre ((ho)) me1
W Σ
A Σ ne
k=1
kERNI
16

---

Published as a conference paper at ICLR 2026
Given that the primal problem is feasible and finite, the dual problem is also feasible and finite. This implies the following condition:
0, VeEC
+ Pk.c + Iee ((c))((tt) + The 0, vk VkEK,cEC
(7)
Let k, such that [(A.))EENZ)) = 0 meaning that Wkec # 0. Hence, equation becomes:
Mk.c + ar IeEEEECZz = -/e
From this, we deduce:
[KEKINZ*] 0
Mrccc -le.
From strong duality we have OPT H4, () = E
Exeknn= Xeax - Ecec To, hence to maximize
the performance, ~%e should be as maximum as possible. result:
((,,))a7TI = then [KeKnzy = = Pkke = Mell = 77c
B. SUB-OPTIMALITY GAP
Proposition B.1 (S,, Property). The coefficient S., given in Definition 3 is positive and finite.
Proof of Proposition B.1 The positivity of S., follows immediately from its definition. To establish finiteness, we adopt sensitivity analysis approach. Consider the mapping:
vs E [0, S, s + y(s) max f(u. w). (=0
It is easy to show that the mapping is decreasing and bounded.
Following steps in the proof of Lemma B.1 the Lagrangian function associated to the optimization problem defined by y(s) is given by:
L. (ss,) w) Σ (x((s) (k w) dx - -s)
KER
Σ
(kc()) Σ ne(s) (46(2)) -1
(K.O)ET
LEC
K
= Σ oEC
He +
Σ Am
(x(s)ckk Me + Σ
(kc(s)ex + nc()1
We
Ene + s)ar(s) - AEK
Σ (s(s)
keR
LEC
ac
= Σ (A+ + s)au(s)
-
nc(s)
kEK.
CEC
where the last line is due to finiteness of the objective function and the strong duality of the linear programming. Furthermore, using (Enrique Castillo and Castillo, 2006). it follows that:
dy
Σ (o) REK
Is
The latter is bounded, given the feasibility of the linear programming 2g- This completes the proof.
Proposition B.2 (C(I) Property). For any candidate set I, the coefficient L(I) given in Definition positive and finite.
17

---

Published as a conference paper at ICLR 2026
Proof of Proposition B.2 The positivity of ((I) follows immediately from its definition. To estab-
lish finiteness, we adopt a sensitivity analysis approach. Consider the mapping:
ss 2 s 8 zr (s)
max f(p. uz).
is easy to show that the mapping is increasing and bounded.
Following same steps as in the proof of Lemma B.1 the Lagrangian function associated to the optimization problem defined by 23 is given by:
(w, (((Wwa(s), a(s), B(s). (())s((s))))))) (s), f(u, w)
Σ
as(s) (x((e, w) de +
KEX
+ E
(e, de(s) ( w) + d +
Σ
(ko(s)ha(c,20)) w) + Σ En((s)) no((s) (c((w)) -
KEKnI
cEC
Σ REC
He Σ
(ax(s) ( ( + Σ [ + ne(s)1
we
k=1
Σ
(Ae s)ax()) + E
(Au + +))a((0))
KEK
AEKiN
CEC
Σ(A AA+ s)ou(s)+ + kEK
E (Ak + s)a AEKrZ
Σ
Tee
eEC
where the last line is due to finiteness of the objective function and the strong duality of the linear programming. Furthermore, using Enrique Castillo and Castillo (2006). it follows that for all 2 s()):
dzi
Σ Apan(s(Z)) - Σ (sa))s(ZZ)..
0s
KEK
keKrz
The latter is bounded, given the feasibility of the linear programming zr (I{)). This completes the proof.
Lemma 3.1 (Suboptimalitty Characterization) Under Assumption 3
p(T*) and p" 0.
Proof of Lemma
3.1 The result p(T*) O follows directly from the fact that wn (0, and max f(1, w). )
that {u, w²)
Let I # I", then:
If (), = 0, then s(I) > and thus p(Z) >
Otherwise, if (0. * 6. then s(I) 0 and all allocations in e)( feasible for max [11 w) > 0, and thus p(Z) > 0.
LP(H, implying [11, w²) (E
Since the number of suboptimal I is finite (of number (.+*) ), it follows that p² 0.
C CONFIDENCE SET CONSTRUCTION
Proposition 4.1 (Confidence set), Under Assumption
let ((t) and St defined in Eq. 7 and then:
(i) 2 P (μ E (,(p(t), 8)) > 1
(i) 2 1, w.p. at least for any w E TH) p(t) E St(ū(t), and E K.
19x (ī(t), w) - gu [1, w)
< pp (E(Et(t) w) where px (E((t)) w) = E 2ex,(t)Wa,o(t), plE(t), w) -Eeexo] pn(E(t), w).
(ā)(), w) w)) S p(c(t), w),
18

---

Published as a conference paper at ICLR 2026
Proof of Proposition 4.7 The confidence set relies concentration inequalities bound the de- viation between the empirical mean (t)) and the true mean Mele for each arm & and context
Using Hoeffding's inequality, the probability that (tt,(t) deviates from Pk.e is bounded as:
Pr (1) Ma,el S (()) 2 1
Applying a union bound over k and e, we ensure that:
Pr (v(k, c), (t),e(t) Mkkeel S (k,,e(t) 2
This establishes that the true parameter μ lies within S,(ā(t), with probability at least 6. Under the consistency property, both (a() and y belong to the confidence set (,(((t),)) Therefore, for any k E [K] and e E C, we have:
[xx,o(t) - -kkol (()) cxt,((t) + (k,,(() Mkkel
(1x, (1), l(x,o(1) Mkkel
(t) + Et,o(t)
et).
Expanding f and gl with respect to their definitions concludes the proof.
We finish this section by a result on the estimation error that plays central role in deriving the upper bounds for both OLP and OPLP. Proposition C.1 (Pairwise Estimation Error Upper Bound). For any arm k E K. and context e C where at each step 8, 1/1, the following bounds hold:
E
(ck,((t)u,,ctt))
= O (log (T) E [log (T))))
o (Viog (T) Vmed(T))
E
Ck (t),kt))
Proof of Proposition C.
We denote by Fe the sigma algebra containing the information available
t, i. set J, = 1H Then:
T
E
(Ex,C(1)
Σ (1),,.,))))))))
log (2nit)
ΣE
nu, - 1) w..,(t))
((k(rr)) (k.c)) (t - 1)
$ 2 log (2nTT)
IE
F
1 [(k mk,all - 1)
< 22 (2KTT) E
< <2 (2k(T) E
cx nt,c(t - 1)
< 2 log (2xT)) E [log(nx. + 1)]
(uses Fact A.2
< 0 (log (T) E [log (n (T))))
19

---

Published as a conference paper at ICLR 2026
T
Σ
Ch (t)
1 $ log (2n:T)
Wk.c
Mkko 1)
1=1
1 [(kr))))((k)))) Fi-11
I 2 log (2xTT)
E
((k,,)))=((,,0}
I log (2KTT)
v /nt,olt 1)
2 log (2KT)E
mk)((T +
(uses Fact A.1
0
Vlog (T) (T)
/mu.o(())
D PROOF IDEAS FOR THE UPPER-BOUND RESULTS
Theorem 5.1 (Upper bounds for OLP). Under Assumptions 7 2 and the performance and con- straint regret of OLP satisfy:
log (T)²
B
pr
log (T)² + VKNII*
E S
Iongi*loooo log (T)
Theorem 5.2 (Upper bounds for OPLP). Under Assumptions 7 and the performance and constraint regret of OPLP satisfy:
((11))
1
[[R]] -
log (T)² + MKNI (T)T)
E B < 0
A
log (T)2) where A= -=Em, d
722
REX
From Section the problem of learning the optimal allocation w² can be decomposed in two parts: first, identifying the optimal allocation structure governed by I", and then, determining the optimal weights for such structure. This decomposition allows finer analysis the intersection between MAB - Min-finding I*, which plays the role of the optimal arm, and linear bandit - finding the optimal structured allocation.
Both OLP and OPLP recover I at logarithmic rate, with convergence speed governed by p* which is connected to the notion of gap in MAB: when either algorithm activates an incorrect constraint set (I, # It), this indicates insufficient estimation precision. Formally, the confidence radius satisfies p(E(t), (t)) p", as shown in Propositions
and E.6
The optimistic strategy used by OLP ensures no performance regret once the optimal constraint set I" is identified, thus leading to logarithmic performance regret overall. When no arms saturate their revenue constraints, this is also the only source of constraint violation. With binding revenue constraints, however, finding the exact structured allocation which satisfies the constraints resembles a linear bandit problem and translates in O(vT) additional term VT.
OPLP operates in phases and builds on pessimism to propose conservative allocations that satisfies the constraints by design in the second stage (Proposition E.3h. The constraint violation Vr is thus tied to the number of rounds where LP(UCB(()) LCB(t) (t) is infeasible, which implies insufficient precision as p(E(t), wt)) 2 7* This occurs only logarithmically often, with the bound scaling inversely with 7² (Proposition E.2). On the performance side, the regret incurred to identify I* and reach feasibility scales logarithmically (Propositions E.4 andE.6). Once those are met, the pessimistic strategy's 's surplus allocation to saturating arms in K. I dominates the regret. The resulting cumulative regret is bounded by: O (VVKKNZ)TT) established in Proposition E.5
20

---

Published as a conference paper at ICLR 2026
E UPPER-BOUNDS
E. RESULTS OF OLP
Theorem 5.1 (Upper bounds for OLP). Under Assumptions 7 straint regret of OLP satisfy:
and the performance and con-
log (T)
B[RT] S 0
Pr
log (T) [KCnI* log (T)
E < O
P
The proof of Theorem 5.1 primarily relies on analyzing the rate at which Algorithm succeeds in identifying the optimal set I", and understanding the implications of correctly (or incorrectly) identifying this set on both the regret and the constraint violations.
Knowing I* effectively localizes and defines the optimal allocation w². Hence, having very tight estimate is strongly tied to activating I' and achieving the optimal allocation. Conversely, activating suboptimal set L, is closely linked to the largeness of the confidence radius p(E((), ao(l)) Proposition E.1. For all rounds t where OLP saturated the wrong set Ia $ I", the following inequality holds w.h.p l/t:
ple(t), w(t)) 2 p²
This implies that if suboptimal Z, is activated, the corresponding confidence set is necessarily loose, indicating the presence of a non-negligible confidence radius.
Proof of Proposition E.1 We rely for the proof on the impact of saturating the wrong set Ij # I on feasibility and perfomance.
Infcasibility. Recall the set (8,8, I), given in Definition 4
E
gh (H 2 A e
(x w E T
I A + V(k, E INI, (R(C, m) 0
9l (p. w
At round t, this set allows to link effectively the chosen allocation w(t), the set of activated constraints I, and the radius of confidence set. Lemma E. If w()) is the allocation chosen by OLP at time I, then w.h.p - 1/2:
w(t) ((p(e(t), w())),
Proof of Lemma E.
By the definition of UCB(I) and w()), we have: Wk K, Vk E
gb (UCB (t), w()) Aks
(8)
go (CCB (t), wt)) Ak
(9)
[cl =n() E T
(10)
Given Proposition 4. w.h.p 1 1/4, we also have: Vk K. ( ut)) (a(c(t), (t)) < g (UCB(t), w(t))
s g (n, w(t)) + Pk (c(t), w())).
(11)
From 8 and 11 we conclude:
Vk K,,
gk (1,, mn)) 2 d Pr (E(t), m(()) 2 d p(E(1), w()))
Similarly, from 9 and
Vk E ENII, go (n w(() S d + Px(E(1), w())).
Finally, by the definition of I., we also have:
= 0, V(k, c) E J nI,
which completes the proof.
21

---

Published as a conference paper at ICLR 2026
The inclusion w(() E pp(((t)),
w(t)),Ii, ( ((p(e(t),I)) must contain at least one feasible point. For this to hold, it must be the case that:
established in Lemma E.1 implies that the set
(c(tt,,(()) 2 s s(T)),
where s(4) is given in Definition
Performance Gap.
Another tension arises due to performance. We consider the following problem:
2z (p,
max =EV((.,T)
M(,, w)
Given Definition we have:
(()) (1, IT) 2.(2,) (1, (o((0))) a(T)))
On the other hand, it holds that:
f(u, w())) & ((t) II)
and by optimism:
f41, w²) ple(t), (1,,,()))
Hence, we obtain:
flu, w²) p(c(t), w(()) (4, S L(I.) (((e(t,,((t)) s(Io))
This implies:
fu, w²) Zo(I.) (H, + ((II))((I))
S p(E(()) ((t))))zz(t))
1 C(I,)
f1, u²) - =2((I,) (1, It)
max L(Ie) S p(E(1), (((((),)((1)
= +(I)) S ple(t), w(f))
Hence, Ie is sub-optimal then p(I,) 2 p² which completes the proof.
E.1.1 REGRET OF OLP
To prove the upper bound on the regret OLP, we examine the per-round regret incurred when the algorithm activates (or fails to activate) the optimal set of constraints, I*. Note that for any round of OL.,, it holds:
w.h.p - 1/,, w() - f(u, w(t)) & (t))))).(tt)
(12)
Proof of Equation 12 Optimism ensures that I' [1,, w²) ((UCB(), w()).. By Proposition
we have /UCB (t)) & f4,, (() + p(e(t), (t)). Combining these two steps concludes the
proof.
For Suboptimal I, + I": Recall the Proposition E.1 on p", then w.h.p 1 1/4:
w(,,w") w²) f(u, w(t) Eq
((t)) & P(E(t), w(t))²
plE(t), (t)
p*
(13)
22

---

Published as a conference paper at ICLR 2026
For optimal I = I Both w(() and w" share the same localization of non-zero entries. However,
the estimate (t( used at time may lead to differences in their values. Given that nu = Knz
vk EInK, 9h (UC v0() ) = =p w Ak I nI, (p, S 9h (e, 20)
(14)
Notice that:
K 1k
f(1. w²)
cEC k=1
(a)
wkg.ellpeoloo + Σ
aEC
Σ
|| - Σ
Wkoowkie
cEC
(b)
||Aoll00
Σ kEkin
Wk,e
oEC
where in (a), k argmax;e[K] Mk,cs and (b) uses Lemma the only non-saturating arm that may have non-zero probabitity is the best arm that context.
B.1 which shows that in given context,
And given that Iz = I+, then similarly:
((p,))())==))))))))))))))))))(
=()) ||molls0 - Σ
AR..WK.((t)
CEC
kElCNI
Hence:
f(u w²) f(H,, w(t))
Σ Σ
DK. (Wk,elt) wkec) 50
(15)
GEC kEKnI*
This demonstrates that, the UCB- based approach ensures regret between the optimal solution w and the estimated solution (t),, if I, = I*
Thus, the regret upper bounded by:
Rr <
[f,,,"" - f(u, w())))
<
(f(,. w²) - f(y, w(())) 1 Lr, z- Σ (f(,, - f(1 ((t))) [7
Eq 15
(f(,, w²) f(p, w()))) [[z
T
E. Rr
< RR
Σ
(f(), - w(())) [Z,ZZ))
For each round, we decompose the round wise regret by analyzing two distinct scenarios: the good event (denoted by GE) occurring with high probability 1/2 as guaranteed by Proposition 4.1 and the bad event occurring with complementary probability 1/s. In the latter case, we conservatively bounded the roundwise regret by the quantity Σ Meloo which provides a worst-case losses.
cEC
23

---

Published as a conference paper at ICLR 2026
Hence:
E RTi S E
Σ (s(,, (f(, f(u, w()))) 1x
(f(u, ((t))) 11, 30 .1 EE (f(u, w²) - flu, ((t)))))))++ [zz 30 3/4
p(E(t)),uu 2()))2
+ P
t=1
p(E(t), 2()))²
IE
+ O (o (T))
Where in (a), we use Equation (13) for the first term and as discussed we upper bound the roundwise regret by for the second term. Hence, control the expected regret, it remains to control
T
E
(((((,,w()))
Σ (Lo())aal()) h,c
pt
E
(EH, (en,c(t)wx,,(tt)
k.c
Prop C.
log (T)
Σ
log (nt.
pr
h.c
log( cconcvvvyy
log (I72)
0
(16)
which concludes the proof.
E.1.2 CONSTRAINTS VIOLATION OF OLP
Using Proposition 4.1 w.h.p 1 1/4, for any arm k; the constraints evaluated using the estimated and true means satisfy the following relationship:
g& (CCB(t) u())) S gu ut)) ps(E(t),
Additionally, by the feasibility condition of the solution to LP(UCB((). UCB(()), we have:
9k (UCB(t). (t)) 2 AEs
E..
Combining the above results yields:
A go (e w()) S (x(E(1) mn))), Ak e K.
(17)
Now, consider rounds t such that I, = I::
1. If KnI* then (4,, w0) dR. On the other hand, given 14 we have Ioe (M,, wn) 2 (1, w()).. Thus,
A 2 gk (1,. ur(t))
2. k & KnI*. then d S gh (1,, w*) Furthermore, we have
gk (1, w²) S go 1L, (t) A S gk (p,
Consequently, when Ie = It, the violation arises only from saturating arms and is given by:
V(t) Σ
d gk ( w())
Σ
((()))),(())))
keknn
ReKnz-
24

---

Published as a conference paper at ICLR 2026
Thus, the total constraint violation up to time T can be expressed as:
T
Vr- ΣΣ5
94 (M,, w(())
KER
T
[==10
Σ
(Ae- mu ((())
+
Σ
[
Σ bER
gu uo(l))
kEK
T
Σ kEKiI
(Ax gu (1e, 20 20())
(Ae go ge(,,,((1))
+
pz,
AEN
We proceed by establishing upper bounds for the expected values of both and B. Our analysis decomposes these quantities under two scenarios: the good event GE from Proposition 4. and its complementary event. Let À = EkEK A denote the worst-case constraint violation that may occur in any given round t.
T
E E
E
Σ kEKnI
(AE (1, mn(())
+
F
(>e - gle 11 ((()))((())) 33
.1 1 F
|,-1
Σ kEknz
(^e
(e(
33 1/1
kEKiN
Σ
(=(E(1), m0())
+ A
11=-I+
kEKnI
Σ kEKnn*
E
Pk (E(t)) z0(t))
+ +0 (Alog (T))
Σ
Σ
E
(t)c(t)(k.(tt)
+ + (Alog (T))
kEKnI sEC
)
Prop C.1
E
log (T)
Σ Σ KEK-II
V (T)
+ O (Alog (T))
cEC
Vi concaviity
I
0 OVIccI log T + A log (T)
(18)
T
EB = E
1 1
Σ (Ax 9u (H, w())
kek
E p(e)) w(t)) [3 AE [1 [
93 3/6
E (p(E(t), w(()) (((()))))
2())22)
335 + A/4
plE(t), we (t)))
E
+ O (T))
1=1
Eg
x2 (
log (7)²
Combining F[AA] FB concludes the proof.
25

---

Published as a conference paper at ICLR 2026
E.2 RESULTS OF OPLP
Theorem 5.2 (Upper bounds for OPLP), Under Assumptions 7 and 4 constraint regret of OPLP satisfy:
the performance and
((
E[R S
log (T)² + v I N log (T)T)
pt?
[ & 0
log (T)²) where A= =
Σ REA
AR-
yx2
The specificity of OPLP lies in its use of pessimistic estimates as parameters for the constraints, introducing safety margin that enhances constraint satisfaction. However, steplois not guaranteed to be feasible from the outset. For this reason, the algorithm relies on an optimistic approach as a fallback. Under Assumption 4 one control the number of rounds during which the pessimistic step is infeasible. Recall the Definition 2ff y", that quantifies the strong feasibility the problem. is crucial control the number of rounds pessimism is infeasible.
Proposition E.2. Consider the event (t) {p(c(t), w())) 2 7}. and define Er = 1gg()) Lei t denote the number of rounds in which step 9 of Algorithm is executed. Then, under OPLP, the following holds:
TS ET,
2n² 72
2k:
)
E(Er] S 0
log (T) log 8
Proof of Proposition E.2 Consider the event {t) = {p(e(t), w wt)) 2 }}
To ensure the feasibility of the LCB, the following suffices hold:
Ew E π K
JCl Vk [K], ge(p,, w) - (E, w) 2 AE.
Thus, it suffices to ensure that:
Vk V Pale, w) S:
Implying that:
T E
T p(e(t), w(t))²
S t=1
[E(0) = Eq <
Σ (le(())
same Eq
x2 log (T)²
E[r] < E[Er] <
[P(c(t),2(())}
E.2.1 CONSTRAINTS VIOLATION OF OPLP
The use of pessimistic estimates for the constraints is advantagcous terms of limiting constraint violations.
Proposition E.3. at round the problem LP(UCB()) LCB(I) (t) is feasible, then w.h.p - 1/e, the corresponding constraint violation is zero.
Proof of Proposition E.. Suppose that step 6 of OPLP is feasible at round t, and let un( denote
the corresponding solution. Then, by feasibility, we have:
Yk KC 9n (LCB())) wx))) AR-
By the pessimism property of the lower confidence bounds in Proposition 4.1
we know that w.h.p
1 1/:
Iv. (1, w (t)) 2 9k (LCB((). w() 2 Ap-
Hence, the constraints are satisfied under the true means μ. implying that the constraint violation is
[T
26

---

Published as a conference paper at ICLR 2026
Thus, each round
If step i feasible, then the per-round constraint violation is zero.
Otherwise, the per-round constraint violation is at most À = Σ Ag.
kgk
Using Proposition E. we have:
Vr -
(Dx
gh (p, w)))+ (1E(0))
[E(0]
[00] + 1 [0(0] [ax)
T
=
E
XE ET
O
log (T)2
(6)
Where (a) is the consequence of Proposition E.2 (b) the consequence of Proposition E.3 and (c) is the result of the low probability event of Proposition 4.1 This concludes the proof of the upper bound on the cumulative constraints violation under OPLP.
E.2.2
REGRET OF OPLP
The regret of OPLPs can be decomposed based whether step 6 is feasible not. Once the pessimistic step is feasible, a further decomposition considers whether the optimal set of constraints, I*, is saturated not.
T
(f(,, w²) - f(u, w())))+
T (f(u, w0) - w(())) [(SC0)) +
T
(J(,, 5(1,, w())))
l [(0]
(f(p, w²) 20())) [[(C))]
(f(1, - (1, vn(()) |E I I==Z")
A2
(f w²) -m,, w(())) | 1
As
Then we proceed by upper-bounding each term A A2 and Ag. Upper-bounding Ar. This quantifies the regret induced during the infeasibility of the pessimistic approach.
Proposition E.4. Under OPLP, we have:
E B[AI] S O ( log (T))
22
Proof of Proposition E.4
The per round regret is upperbounded by μ Σ
Molloc. Hence:
E [1] E
(f,, w²) f(1. w()))) [((())
E
M [E())]
0
log (T)²
where (a) is based on Proposition
H.2
27

---

Published as a conference paper at ICLR 2026
Upper-bounding Ag. This term corresponds to the rounds where of OPLP is feasible and the optimal constraints are saturated, i.e, I, = I During these rounds, the algorithm safely activates the saturating arms, i.e., & E nI by allocating them more budget, which induces the regret. Proposition E.5. Under OPLP, we have:
I8 [12 = (vielKKVV log (T)T).
Proof of Proposition E.5 rounds t where I arms, i.e:
For the second phase, when using LCB becomes possible, we consider This implies that both LP (1) and LP( LCB(t)) saturate the same
Ak VEEZNK 9h (LCB(() m(t) X = Ih ( w²)
= w.h.p: 1 1/11/, E IK,, w()) Pk (c((t)) w(t)) _ g (p. w') w.h.p: 1 1- VK E IIK,, gx(p, gh w²) I (x((((), wn(t) (19)
Notice that:
k
oEC k=1
k=1
Wkg.ell + Σ
REC
||uello0 Σ
aEc
(b)
||Mallo0
A Wk,o
cEC
kEKiN
where in (a), k-- argmaxne [K] Mkee, and (b) uses Lemma the only non-saturating arm that may have non-zero probability is the best arm that context.
B.1 which shows that in given context,
And given that Z, = I*, then similarly:
f(u, w(())
Σ
||
Σ
DR.owH,((t)
LEC
kEXinI
Hence:
w() 10 -f(,,, (0(1)
Σ
Σ
DK.c (Wk,c(t) wk.c)
REC MEATI
Anie Mkke (Wk, wk.e)
Mk,ec
kEK DEC
S a
Σ kEKCNI GEC
Σ
Pk.c (Wk,e(t) wk.c)
S a Σ
9h (H,, wx()) Ie (pe, w²)
kEKnZ
Thus w.h.p 1/4, we get:
((,,w)) 8(1 w (t))
Σ KEKNZ
Pk (x(e(t), w())
Taking the expectation:
T [A4a oE oE
T
E
Σ Σ pa(E(1), v((1)
+
Σ t=1
7
KEKNZ.
Fq
o
(T) T + p log (T)
28

---

Published as a conference paper at ICLR 2026
Upper-bounding A3. This term corresponds to the rounds where step of OPLP is feasible, but the algorithm saturates the wrong set of constraints, i.c., It * It
Proposition E.6. Under OPLP, the following holds:
1. If + I and Et) holds, then w.h.p. - 1/4:
(((()),2((1)) p²
2. Moreover, it holds that
E [ so ( log (T)²
Proof of Proposition Σ.6 We prove each point of the Proposition separately,
Proof of Point 1.
Recall the definition of set v already introduced in Definition 4
vk K, gle ( (),,w) d 8, E II,, g w) S Ae (k,,)) E II, helc, w) =
(88
u E
ICl K
It is straightforward to verify that w.h.p 1 :: we(() (p(E((), (.)..
(20)
Infeasibility. Given that wtt) E & (p(e(t), w(t)), [T) then the latter is not empty, implying that p(c(t), w()) 2 s(I)).
Performance Gap.
Recall the set + introduced in Definition 2
(s) w E a Ak E [K]. (,, w) 2 A +
is clear that Vs [0, 7), the set (s)) is non-empty. Furthermore, using Definition of S.y, with #2 p(e(t), w(t)) S 7 and
yields:
max max f(1, w) wEo(plE())
1/1, w) S S. p((())
wc (0)
and hence:
S4, w²)
we (n(()((())) [10 w) S S.e
f(u, 20) LP(μ, LCB(t)) < S. p(E(t), w(()
[11, un) LP(μ, LCB(() & mmx (1, S. ( w()))
Now using Definition 5
f(1. w)
MEV(s(Z.) f(1, w) L(I)) (p(e(t), w(t)) - s(I,))
(EV((le(D)
max LP(H,LCB(I) (EW()(IT).TT)
[4,, () S L(I)) (plE(1), w(()) - s(T))).
We conclude that:
[10 w²)
max MEE()(())..II)
s(, w) +[II))(IT) < (max(1,8..) ) ((T)))((((()) w()))
f(H, w*)
max wEV(0.I,)
f(M,, w) + C(II)s(I)
S p(c(t), w()))
max(1, Sy,) S.,) ) + L(I,)
f(1, w²) W...
max
fu, w)
E p(E(t), w(())
mT. + C(I,)
p(z))= S p(E(t), w())
Hence, if I, is sub-optimal then p(I,) p² which concludes the proof of first point.
29

---

Published as a conference paper at ICLR 2026
Proof of Point 2.
T
A =
(1,,,/) -
1I [(t)
|2 [e(t]]
t=l
= 1[A3| 1
1b 1 [
$ 11 Σ
[I+ 8(0]
T
$ Σ
E 1 11 [(0)
30
.1 +
Σ
t
IE (e0ce(0)
[E(O] |Gε]
+ Oeulog (T))
1=
plE(t), 2()))²
+ Oog (1))
x=²
same as Eq
T6
n² p0r log (T))
(
In conclusion, combining Proposition E.4 Proposition of the upper bound on the regret of OPLP.
E.5 and Proposition
E.6 completes the proof
F LOWER BOUND
F.1 LOWER BOUND THEOREM
Theorem 5.3 (Lower Bound). Let ( and (()()) e) defined in Table ! and Eq.
then:
(i) For T 2 16, there exists small enough such that:
E [Ru (T) + Ve, (T) = =S(VV).
min max VET(MO))
.T))
(ii) For any consistent policy 3 To S... 1...VTZ To:
E R (T)] S2 (log
Proof of Theorem 5.3 We proof each point separately.
(i) First Lower Bound. We start by proving the first lower bound focusing on the sum of the regret and constraints violation.
Used Instances. Consider the nominal instance v (0) and two perturbed instances, 2 and both belonging the uncertainty set ((, E) with Gaussian distributions (".,,) 1). These instances are respectively defined in Table[]am Table 3 with the perturbation parameter æ constrained to the interval (0. f) Each these instances admits a distinct optimal allocation, summarized Table
and Table 5 respectively.
2. Effect of Wrong Beliefs on the Regret-Constraint Violations Trade-off. The lower bound is derived from the fact that an incorrect belief about the ground truth leads to either non-zero regret when the belief is overly pessimistic, or a constraint violation when the belief is overly optimistic.
Let w2, = 1/2 be the optimal allocation under the nominal instance o of the second arm at the secon context:
30

---

Published as a conference paper at ICLR 2026
Arm k
Pe Akke
X
Arm k
Pe Pk.c
X
c = 1
C 2
C 3
= 1
c= 2
C = 3
k=1
F1,1 3
21, 1
|1,3 1
1
k=1
A1, 3
11,2 1
|1,33 1
1
P2,1
12, 1tc
|2, = 0
k=2
2211 = 0
12,2 1-c
22, = 0
k=3
A3,1
1432
13, 2
k=3
[43.1
33,2
133.3 2
Table 2: ++ instance.
Table 3: V_ instance.
Arm k
Arm k
X
c
C
2
C
3
C = 1
C
C
1
14:2s
0
1
1
1- 25
0
1
2(1+c)
2[1-c]
2
0
2
0
2([+5)
2(1-5)
3
3
0
0
Table 4: Optimal allocation for instance v-.
Table 5: Optimal allocation for instance
If the instance is 44 and w2,((1) 2 w2.2. then the algorithm leads to regret of at least
2(1 + E) )
(1-12
1 +
1- c(1 - 5)
r(t) 2
12.
2
2(1 +
2
4(1 + 10"
If the instance is -_ and (t)
2,2 then the algorithm leads to constraint violation
at least
1 1
1
1
v(t)
2.2
4 2
4 10
3. Information Theory. Let Pv., and P._. denote the distributions induced by the learning algorithm under the two problem instances 14 and v_, respectively. Explicitly consider the policy æ, and let Fr denote the trajectory induced by that policy. Given the assumptions the rewards, the KL-divergence between the distributions over the trajectory of rounds satisfies:
Tea
D (FT) (Fr)) S
(21)
Proof of equation (1 We denote by Gt) the aggregated gain received by the player at time under policy л. Hence:
D (Pv, (Gx(t)) (Gx(t))) = Σ w
(t)D 1)
c=1
2122(()) (L) ())
22
2
Summing over the trajectory ends the proof.
Consider the event
T
r
mh
(1)
2
>
2
Note that:
ET
I holds under /
R₁ >
10
and similarly,
I holds under v_
11 2
10
31

---

Published as a conference paper at ICLR 2026
Using the Bretagnolle-Hon Huber inequality Lattimore and Szepesvári 2220
1
1
TE?
P2y (T) + Pu_ (T)
2 2 exp (-D (Fr) (Fr)) exp
2
4. Lower Bound Explicitly. For any policy generated by any learning algorithm:
E (T) + Vu+, (T) + [R=_. (T) + Vu_ (T) 2 E RRv (T) +
Ve_ (T)
Te (Fv (T) + P.P
10
Te
TE²
2
exp
20
2
Choosing = VT
1 for 2 16 leads to:
VT
E RRw (T) + Ve Ve,, (T)] + + E RR, (T) + Vv 1 (T)) 2
20c
Let ēr = T-1/2 (where T 2 16). For any policy æ, since both 4 and v belong to ((v(0),TT))
eT the following holds:
1
max VET(wiO) .T))
R (T) + V2, (T)
[E
Ry4. (2) + Vu (T)] + E Rv a (T) + Vv_ (T)))
VT
max WE ((()))
[R (T) V2, (T))
40e
VT
min
max (ET( .T)
E [R (T) + V2 (7)
40e2
This concludes the proof (i).
case. It worth noting that the instance used in the lower bound is not corner case; that is, the characterizing gaps are non-zero. In particular, strict feasibility is ensured by setting > I. and the performance gap p² 0 because the problem is not degenerate. Specifically, there exists a unique solution, which results in non-zero performance gap while activating suboptimal indices.
This instance is not
(ii) Second Lower Bound. We now derive the second lower bound the regret.
Used Instance. Consider the same nominal instance (0) as previously defined, and introduce modified instance v' that differs from ()) only in the reward parameter of arm in the third context:
(1,)(v") + e', E (0, 1]. The modified instance v and its corresponding optimal allocations
are summarized in Table 6 and Table respectively.
Arm k
Pe Hk.c
A
Arm k
w
A
3
c
3
F1,1 = 3
P1.2
11,3 = 2 5 6'
1
1
2
1
12,1 =
22.
42, =
1
2
2
0
A3,1 0
M3,
|3.3 2
1
3
2
Table 6: Instance v'_
Table 7: Optimal allocation for instance v'.
Note that context c does not contribute to satisfying the constraint of arm l: = 1, while under (0) arm is the besf-performing arm in that context and can only satisfy its constraint due to rewards obtained in context 3.
Let π any consistent policy such that there exists a strictly positive constant 3 such that for sufficiently large? T
E( (T) (r)) BVT.
(22)
32

---

Published as a conference paper at ICLR 2026
Information Theory.
Consider the event
Ps7
r n1,3 (1,3(T) (T) 2
Note that:
(2 1)T
T
I holds under (0)
R2t00 xx (7) 2
4
T T
ET
F't holds under v'
(T) 2 E
4
4
Using the Bretagmolle- Huber inequality
Lattimore and Szepesväri 2020
1
E [m1,a(T]](1 + E²)
Po (I") PP exp (-D u (FP) 2 exp
(23)
Lower Bound Explicitly.
Leveraging Equation
RRuco, a (T) + Re,, (T) 2 [Rom a (T) E Ru, (T)
2 T''
(Peio (T") + (P)(((()
4
Te'
E [m), +2')
2
exp
8
2
2
TE
E, [1133 >
log
log (L RRi10, (T) + Re Re,,x()))
8')²
Ee
2
log
Tt'
log (3VT)
(1 E')
8
2
log (T) + log
ET)²
83
Consequently, for all T > To. where To is defined by the condition log (Tb) >> (88() we obtain the following regret lower bound:
E
R (T) 2 (2 1) [M [M),3(T))
Ω (log (T)).
F.2 RICH FAMILY MAB-ARC WITH NO FREE EXPLORATION
Lemma 5.1. For any MAB-ARC instance such that K and |C| 1, there exists at least one pair (k,, c) E I for which the optimal allocation satisfies wkee = 0.
Proof of Lemma 5.1
We proceed by contradiction. Suppose there exists a feasible instance such that |C| K- and for every (k, c) J. holds that wi.e + 0.
By Assumption 3 the linear program is feasible and non-degenerate. Hence, the optimal solution must saturate exactly ς constraints.
There are |C] equality constraints (i.e., the ge constraints). Thus, |C] constraints are already saturated. The remaining
|C| [C - 1) constraints must be saturated by the arm-level aggregated reward constraints (i.e., the gs constraints) because by assumption, no variable w is zero, meaning that none of the non-negativi constraints Wk.e 2 is active, and hence saturation occurs there. This implies that all C 1) yet to saturate constraints must come from the K minimum reward constraints, which is only possible if K [C](K 1). But this contradicts the assumption that
33

---

Published as a conference paper at ICLR 2026
CC K K-1 Therefore there must exist at least pair c) such that wh., 0. Given that the function + is strictly decreasing for all x 2 3, we obtain the inclusion relationship
[MABARRC: K 2, 1) (MAB-ARC; |C| x
This completes the proof.
G NUMERICAL ILLUSTRATIONS
We validate theoretical results through numerical experiments simulated data. Specifically, we consider the instance V defined T where rewards follow Gaussian distributions N 1) and contexts uniformly distributed. The corresponding optimal allocation, which serves our benchmark, is provided in Table 9 For this instance the optimal set of active constraints is:
I [2, 3, (2, 1), (3, 1), (3, (2,
For comparison, we evaluate both our algorithms (OLP and OPLP) alongside Optimistic" from Guo al. (2025) and the DOC and SPOC algorithms from Baudry al. (2024). There is no established baseline in the literature that directly addresses contextual multi-armed bandits with revenue con- straints for benchmarking our algorithms. However, Guo et al. (2025) introduced Optimistic for MABs with general stochastic constraints, which can be readily adapted to our setting. In addition, one may adapt non-contextual algorithms such as DOC and SPOC by disregarding contextual information. While this leads to unfair comparison-sinng informational assumptions it underscores the importance of leveraging contextual information when available, doing yields markedly superior performance. Indeed, DOC and SPOC in- herently neglect the contextual dimension of the problem, instead estimating quantities of the form / Eeec Pr for each arm and proceeding accordingly.
the algorithms operate under different
We conduct experiments over T = 50 x 10 rounds, repeated for 5 independent epochs.
Arm &
Pe Mk.e.
Arm
w
C
3
c
C
3
11,1 3
P1.2
11,3 2
1
1
12,
P2.
22, = 0
2
2
0
M3.1 0
M3. = 0
μ3,3 =
3
0
1
Table 8: Instance V.
Table 9: Optimal allocation for instance V.
Figure reports:
The cumulative regret and constraint violation for OLP, OPLP and Optimistic*,
The cumulative performance of all five algorithms
From a regret perspective, OLP achieves superior performance compared to OPLP, exhibiting logarithmic regret versus the O(VT) regret of OPLP. Conversely, OPLP ensures stronger constraint satisfaction than OLP, achieving logarithmic rather than O(VT) constraint violation. In contrast, Optimistic" yields O(VT)) bounds for both regret and constraint violation. Hence, OLP and OPLP are better suited to the considered setting, as they achieve polylogarithmic regime compared the (VVT) behavior of Optimistic
The third plot highlights the performance advantage of our contextual approach: both OLP and OPLP outperform the non-contextual baselines DOC and SPOC, justifying the need for additional work beyond existing literature better adapt the MAB-ARC setting.
34

---

Published as a conference paper at ICLR 2026
Cumulerive
Cumuletive Constraine Vialatioo
Com/lattv Serformance
QUP
COC
2XX0X
1.2
Comulatiee
100043
224
50063
CAP
13
Round 111
Round 30
Rtand: (1)
Figure 2: Display of the cumulative regret and constraint violation for OLP, OPLP and Optimistic" (denoted by OPT3), and the cumulative performance of all five algorithms, under identical conditions (K 3, |C| 3, T 50,000, Gaussian distributions, (M,, 1), epochs).
Non Saturating Arms. For the sake of completeness, we include an additional experiment to illustrate the correct adaptability our analysis the regime where no arm saturates its revenue constraints. We consider an instance v defined in Table [1 where rewards follow Gaussian distribu- tions (N,, ; 1) and contexts are uniformly distributed, and, according to the oracle solution given in Table 11 none of the arms saturates its respective revenue constraint. For this instance the optimal set of active constraints is:
I= = ( 1), (3, (1. 2), (1, (2,3))
Pe Pk.e
w
Arm k
À
Arm
c= 2
c= 3
C
c=
2
= 3
H1,1 = 3
M1,
M1,3
1
1
1
0
0
22,1 0
222
N2,3
1
2
0
1
0
A3,1
M3,2
P3.3
3
0
0
1
Table 10: Instance v'.
Table 11: Optimal allocation for instance v'.
In accordance with Theorems 5.1 and 5.2 Figure shows that both the regret and the constraint
violations for OLP and OPLP exhibit logarithmie behavior.
CLmss bnive Regpet Over Time
Currabativ Concro Vodatio Over Time
Oordate hawe
12
10
Figure 3: Cumulative regret and constraint violation for OLPand OPLP, evaluated under identical epochs) on an instance where, according to the optimal stationary policy, no saturates its revenue constraint.
conditions (K 3, [C| = 3.7 500, Gaussian distributions. (.,, (., 1).
G.1 SENSITIVITY OF OPLP TO THE FEASTBILITY MARGIN
The OPLP algorithm heavily relies the feasibility margin y² it adopts a conservative strategy that prioritizes constraint satisfaction through the use of LCB estimator for the constraints. However, this approach may not always be feasible, which motivates the of UCBB-ased strategy
35

---

Published as a conference paper at ICLR 2026
Corru alse Regeet Time
Carsa othe Conpmant Volition Dep Tire
131
0807 getres 641
Ol0 genia 6.41
31
Figure 4: Cumulative regret and constraint violation of OPLP under different values of the feasibility margin y*. (K = 33, |C] = 3,7 = 50,000, Gaussian distributions. N(,, 1), 5 epochs)
fallback. To illustrate this, we deploy OPLP under different values of yy, as shown in Figure 4 In fact, for small values of y* (i.e., 7 0.001 and y 0.01), the LCB estimator during the entire time horizon, and the behavior of OLP was observed instead, yielding logarithmic regret and ((VT) constraint violations. However, for larger values such as y = 0.1 and 7 = 1, the LCB estimator becomes feasible, and the standard behavior of OPLP; logarithmic constraint violations and O(v regret, is recovered. Notably, observe the expected rate of y+z scaling in front of the logarithmic behavior of the constraint violation under OPLP.
never feasible
H LAZY UPDATE
Lazy-OLP: Lazy Optimistic Linear Program-
Lazy-OPLP: Lazy Optimistic-Pessinitiee Lin- ear Programming
ming
Inputs:
(AE (1.....K (Po)oEc
Inputs: {AR (A...e( (PeLeec
7=1 {Ths is the last timestep that we changed the policy)
1 (This is the last timestep that we changed the policy)
for t 1,,...,,7 do
for = 1...., T do Observe context Ct
Observe context Ct. Set 8 1 1/t Ec, h. nt,elt 1) > c then (1) argmax (P(UCB(I). UCB(() (()
4
Set 8 4 1/c
if 3c, k. ne,olt - -1) 2 then if LP(UCB(I). LCB(()) feasible
wEx 1cl
then
wx(1)
=
end else
argmax LP(CCB(t) LCB(t)) wEn
w = w(T)
end else
11
end
13
Sample arm KG ~ wc, (t)
11
w( argmax LP(UUC((t, UCB(t)) =E
Receive reward rt 1kg,0
15
Update (2t)), pa(t), (t)
16
Update history H, H4-1 U k
end T ==t end
17 end
else
w(() =(())
end
Sample arm k2 ~ w (t)
Receive reward rt 1kk
Update n2t), fa(t), <(t)
Update history He He-1 U (ce, kz
end
36

---

Published as a conference paper at ICLR 2026
Both Lazy OLP and Lazy OPLP employ reduced update frequeney compared to their vanilla counterparts, OLP and OPLP. The policy optimization step is triggered only when the number of pulls for any arm context pair has doubled since the last update. Between these events, the policy and confidence intervals from the most recent update are retained. This scheme reduces the number most (log 7) over horizon T. Interestingly, this reduction in update frequency does not deteriorate the theoretical guarantees. The analysis and characterization of the saturating constraint remain exactly valid as in the non-lazy case. Consequently, the polylogarithmic and ((VT) bounds are intrinsically tied to the respective bounds of
of required computations
T Σ
E
Σ (x(e(t), px(e(t),2(tt)
and
E
Px(E(t),
w(t)
Let denote the most recent round prior to at which policy update occurred. Under both Lazy OLP and Lazy OPLP, we have:
2 log (2NTT)
E
Ma (E(() w(())
= E
(1)²
nk,ee (Tt)
t=
CEC
Wko (1)
< EE
log (2AT)
Tkkee
CEC
WK. (t)² Tkk (1)
<
E
log (2HTT)
(na,o(1) S (Te))
EEC rm
I o
(log (27)²)
(similar Proposition C.1
T
T
log (2ATT))
E
Σ
pa (e())))) m())
= E
(k)c(()
Tkk.o (Tt)
CEE
(k.
E
log (2xT)
(Te)
CEC
T
V2 (h)
< E
V 2 log (2xT)
(na,c(1) S (TT))
(t).
CEC tm
< 0 (Vlog (T)T)
(similar to Proposition C.1
As result, the lazy versions of the algorithms preserve the same theoretical guarantees as their vanilla counterparts.
I COUNTEREXAMPLE DEMONSTRATING THE INEFFICIENCY OF GREEDY BEHAVIOR
Greedy achieves sublinear regret in the single-context setting because the constraints enforce ex- ploration: order to satisfy the revenue constraint for each arm, Greedy is forced to play all arms and eventually refines its estimates. However, in the multi-context setting, the constraints do not necessarily enforce exploration. For instance, consider the example in Table 12
Arm
Pe Hk.e
X
C = 1
C 2
1
M1, 1
M1,2 2
0.1
2
P2.1
= 2
#2,2
= 0.1
Table 12: Counterexample instance illustrating Greedy's inefficiency in the multi-context setting.
In this setting, the optimal allocation is P1,2 2 = 1, P2,1 = However, the Greedy algorithm may incorrectly conclude, with constant probability, that the optimal allocation is Pı,1 P2,2
37

---

Published as a conference paper at ICLR 2026
thereby incurring linear regret. This inefficiency arises because the constraints not tight enough to enforce sufficient exploration. It is worth noting that in the single-constraitt case, Greedy may also yield linear regret if 0₂ 0 for the best arm in the instance.
38


Reviews:
[{"review_id": "omR5PyWISx", "reviewer": "Reviewer_ArM6", "summary": "This paper makes meaningful contributions to the multi-armed bandit (MAB) field by proposing the novel MAB-ARC (Multi-armed Bandit with Adaptive Resource Constraints) problem, filling a gap in the intersection of bandit optimization and dynamic resource constraint management. The two tailored algorithms (OLP for performance priority, OPLP for constraint priority) and their complete theoretical bounds (regret and constraint violation upper/lower bounds) demonstrate rigorous academic thinking and practical problem-solving awareness. However, the work is limited by restrictive finite space assumptions and high computational overhead, which affect its generalization and real-world applicability.", "questions": "Extend the MBA-ARC model to infinite context spaces (e.g., continuous features) or high-dimensional arm spaces, and adjust the algorithms/ theoretical analysis accordingly (e.g., using kernel methods to map continuous contexts to finite feature spaces, or adopting dimensionality reduction techniques for high-dimensional arms).​ Quantify the time/memory cost of solving the LP problem per time step, and compare it with baseline algorithms to highlight the overhead issue. Add a section discussing practical deployment considerations, such as how to set hyperparameters for OLP/OPLP (e.g., constraint violation tolerance, LP solving precision) based on scenario requirements, and how to handle edge cases (e.g., sudden resource shortages, context distribution shifts).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduces the MAB-ARC problem, a new research direction that integrates adaptive resource constraints into traditional multi-armed bandits. This fills a gap in existing literature—most MAB studies either ignore resource constraints or assume static constraints, while MAB-ARC focuses on dynamic resource allocation scenarios (e.g., real-time budget adjustment in advertising, resource-limited industrial control). The problem is not only theoretically innovative but also highly aligned with practical needs, providing a new research paradigm for constraint-aware bandit optimization.", "weaknesses": "The paper assumes that both the context space (decision-making feature space) and arm space (optional action set) are finite. This assumption simplifies theoretical derivation but severely limits generalization:​\nIn many practical scenarios (e.g., continuous context features like user age/income in recommendations, high-dimensional arm spaces like multi-channel advertising combinations), the context or arm space is infinite or high-dimensional.​\nThe algorithm cannot be directly applied to these scenarios, reducing its practical value and narrowing its target audience (e.g., excluding researchers/engineers working on continuous-space bandits). The algorithm requires constructing and solving a linear programming (LP) problem at each time step. As the number of time steps increases, the cumulative computational cost grows linearly. For large-scale scenarios (e.g., online advertising with daily impressions, real-time control systems with millisecond-level time steps), this overhead will cause decision delays or even system unresponsiveness.​\nThe paper does not analyze computational complexity in depth, nor does it propose optimization strategies (e.g., approximate LP solving via heuristic methods, batch processing of time steps to reduce LP calls, or leveraging dual decomposition for faster computation). This lack of engineering consideration hinders the algorithm’s practical deployment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iQD5z9mYnF", "reviewer": "Reviewer_G73K", "summary": "This paper studies a new constrained bandit setting where the learner must not only maximize cumulative reward but also ensure that per arm revenue constraints are satisfied. Unlike Bandits with Knapsacks (BwK), which constrain resource consumption, here the constraints are on revenue accumulation. The learner’s decisions must generate sufficient revenue over time for all arms, not just maximize expected reward. The paper proposes modified UCB-style algorithms that solve a linear program (LP) that accounts for both reward maximization and constraint satisfaction. Based on using UCB only or UCB and LCB as the surrogate for reward and revenue parameters in the LP formulation of the optimal allocation problem, the proposed algorithms achieve different tradeoffs between reward maximization and constraint satisfaction. These tradeoffs are explained via regret bounds. The paper also presents an interesting lower bound that refutes the free exploration property used in prior works in non-contextual setups. Simulations depict that the proposed algorithms work reasonably well.", "questions": "1. Please provide further insight on Assumption 3. Line 366 says that inner maximization in OLP is feasible under Assumption 3. Line 253 says that strict feasibility is required only for OPLP. \n\n2. How can the algorithms be extended to the case with infinite contexts? \n\n3. Is “known context probabilities” assumption be still reasonable in the infinite context setting?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Revenue-based constraints are practically relevant (e.g., ensuring minimum revenue in ad allocation, subscription systems, or online platforms). \n\nTheorems are cleanly stated, with clear regret definitions and decomposition. The lower bound that refutes free exploration is interesting and strengthens the theoretical contribution of the work. \n\nThe paper is overall well-written (except for some small typos and notational inconsistencies, which can be addressed by carefully going over the entire paper). \n\nThe comparison with related work is adequate. There are Works that address more general constraints, but they have suboptimal regret bounds for the specific problem considered in this work because they do not utilize the problem structure specific to this work. This paper's analysis is based on a new suboptimality gap based on saturated constraints of the LP and can be regarded as an important theoretical contribution.", "weaknesses": "Algorithms are intuitive and clearly explained. Their design principle is quite standard. Use UCB or combine LCB or UCB, which is the two things that are expected to achieve the tradeoffs between reward maximization and constraint satisfaction. The design process of the algorithms are clear and intuitive. However, they do not require out-of-the-box thinking. This is not a significant weakness, but it makes the novelty of the algorithms somewhat incremental.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "107BYkp8QX", "reviewer": "Reviewer_fiZz", "summary": "This paper considers the contextual multi-arm bandit problem with minimum aggregated revenue constraints, i.e., the average revenue of each arm should be above a given threshold. This problem is subsumed by the more general problem of contextual bandits with linear constraints [Slivkins et al. 2024], but the authors go beyond their results by providing two algorithms OLP and OPLP: OLP achieves polylog regret and square root constraint violation, while OPLP has the reversed guarantee. Further, there is a lower bound regret of $\\Omega(\\log T)$ and a lower bound sum of regret and violation of $\\Omega(\\sqrt{T})$.", "questions": "See the above \"weaknesses\" part. Feel free to answer those questions.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ The paper studies a sub-problem of a more general problem which is of independent interest, and obtains a better upper bound result than the general problem. \n+ The authors show the possibility of applying re-solving-based techniques (though not emphasized) in the contextual bandits with linear constraints, which I feel really interesting.", "weaknesses": "- I feel like the \"contextual\" term should appear in the title. \n- The authors do not discuss the literature on the re-solving technique which is widely used in contextual decision-making problems, e.g., [Chen et al., NeurIPS 2024]. \n- Though the main results are already interesting, I still encourage the authors to justify the following points, which would be better for the understanding of the whole community:\n  1. There is underlying hardness for re-solving based techniques to work in the CBwK problem. Intuitively, samples for certain (context, arm) pairs can be unattainable because the probability of selecting such a pair could be zero in the LP [Chen et al., NeurIPS 2024]. But this problem does not seem to happen for the considered problem. Can the authors explain an intuition? \n  2. Why is the sub-Gaussian reward assumption necessary?\n  3. Do you have a beyond-the-worst-case result, which says that the algorithm still has a performance guarantee when the non-degeneracy condition does not hold? \n  4. What will happen if the fluid LP is infeasible? This may happen in real life, and is there any way to detect this without losing too much?\n  5. What does $\\rho^*$ mean intuitively? And can you give an intuitive explanation of why the regret relies on $\\rho^*$?\n- The author(s) suppose that the context prior is known. This assumption should be relaxed for a general CB paper. \n\n\nReference:\n\nChen et al. Contextual Decision-Making with Knapsacks Beyond the Worst Case. NeurIPS 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)