No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!
Authors: Francesco Emanuele Stradi
Matteo Castiglioni
Alberto Marchesi
Nicola Gatti
Christian Kroer
Venue: NeurIPS 2025 poster ()
Keywords: Online Learning
Online Allocation
Resource Constraints
Budget Constraints
Spending Plan
Primary area: theory

Abstract: We study online decision making problems under resource constraints, where both reward and cost functions are drawn from distributions that may change adversarially over time. We focus on two canonical settings: $(i)$ online resource allocation where rewards and costs are observed before action selection, and $(ii)$ online learning with resource constraints where they are observed after action selection, under full feedback or bandit feedback. It is well known that achieving sublinear regret in these settings is impossible when the rewards and cost distributions may change arbitrarily over time. To address this challenge, we analyze a framework in which the learner is guided by a spending plan—a sequence prescribing expected resource usage across rounds. We design general (primal-)dual methods that achieve sublinear regret with respect to baselines that follow the spending plan. Crucially, the performance of our algorithms improves when the spending plan ensures a well-balanced distribution of the budget across rounds. We additionally provide a robust variant of our methods to handle worst-case scenarios where the spending plan is highly imbalanced. To conclude, we study the regret of our algorithms when competing against benchmarks that deviate from the prescribed spending plan.

No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!
Francesco Emanuele Stradi"
Matteo Castiglioni
Politecnico di Milano
Politecnico di Milano
francescoemanuele stradi @erradd@polmii
matteo.. catteo.castigllaee wwwtiilllon@poooooooooooooooiiil
Alberto Marchesi
Nicola Gatti Politecnico di Milano
Politecnico di Milano
alberto. marcheesi@olliiii.t it
nicola. gatti@polimi
Christian Kroer Columbia University ck29458cclumbia. edu
Abstract
We study online decision making problems under resource constraints, where both reward and cost functions are drawn from distributions that may change adversari- ally over time. We focus on two canonical settings: (i) online resource allocation where rewards and costs are observed before action selection, and (ii) online learn- ing with resource constraints where they observed after action selection, under well known that achieving sublinear regret
full feedback or bandit feedback. in these settings is impossible when reward and cost distributions may change arbitrarily over time. To address this challenge, we analyze a framework in which the learner is guided by spending plan-a sequence prescribing expected source usage across rounds. We design general (primal-)dual methods that achieve sublinear regret with respect baselines that follow the spending plan. Crucially, the performance of our algorithms improves when the spending plan ensures a cell-balanced distribution of the budget across rounds. We additionally provide a robust variant of our methods to handle worst-case scenarios where the spending plan is highly imbalanced. To conclude, we study the regret of our algorithms when competing against benchmarks that deviate from the prescribed spending plan.
Introduction
In this paper we study online decision making problems with resource constraints. In this class of problems, decision maker has resources and decision set X. Across sequence of T timesteps, the decision maker must repeatedly choose decisions &; X. where each decision leads to some resource depletion specified by cost function (x();) E [0, 1]mh and reward f((x;) [0, 1]. We study two canonical settings. (i) Online resource allocation (ORA). In this setting, the decision maker observes the reward and cost functions ft, Ct before choosing T., This setting captures problems such as budget management in second-price auctions [12] and network revenue management [57]. (ii) Online learning with resource constraints (OLRC). where the decision maker chooses s; first, and then receives some feedback on rewards and costs. Under full feedback, they observe the entire
Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

functions ft. Ct, while under bandit feedback, only the values fi (zz) and ct ( This setting captures problems such as budget management in first-price auctions and online pricing [7. 15, 19].
Across the two settings, there have been extensive studies on what types of regret guarantees are possible under different input models. First, in ORA one studies dynamic benchmarks that vary the decision over time (this is made possible due to observing ft, Ct before making a decision), whereas in OLRC the benchmark the best single decision in hindsight. In both settings, it is known that is possible achieve O( regret when the rewards and costs are drawn from fixed distribution at each time step [14, 7]. In contrast, Balseiro and Gur [12] show that it is not possible to achieve no-regret guarantees when the inputs ft, Cr are chosen adversarially. Their result is for ORA, but it extends easily to OLRC. It is also possible to achieve "best-of- both worlds" guarantees where a single algorithm asymptotically achieves the optimal regret guarantee in the stochastic setting while simultaneously guaranteeing the optimal competitive ratio on adversarial input [14, 19].
In real- settings such as when an advertiser performs budget management in internet ad advertising, the environment is not stationary, both due to the time-varying nature of internet traffic, but also due the fact that other advertisers are simultancously adjusting their bidding behavior. Yet the worst-case guarantees offered in the adversarial setting are not sufficiently strong for such real-world scenarios. To address this issue, platforms such as Meta and Google typically provide a predicted spending plan [38, 13]. A spending plan for a given advertiser specifies a recommended amount that the advertiser should aim to spend in each timestep. In other words, the spending plan takes the advertiser's 's daily (or weekly) budget, and allocates it non-uniformly across time based on the predicted behavior of the advertising ecosystem in each timestep. Typically, advertisers cede control of their budget management to an algorithm offered by the platform. Such an algorithm typically takes as input the spending plan and uses a control algorithm (known as a pacing algorithm in the ad auction industry) to attempt to match the predicted spending plan.
Contributions Inspired by the use of spending plans in practice, we study the two types of online decision making with resource constraints ORA and OLRC-in in scenarios where the decision maker is additionally given a suggested spending plan, and the baseline that we compare to must similarly follow the spending plan. We focus on the case in which both reward and cost functions are sampled from distributions that adversarially change over time, thus generalizing the standard adversarial case. In ORA, we develop a dual algorithm that exploits the knowledge of the spending plan to attain dynamic regret of order ( (LLVT), where T is the horizon and Pmin the minimum per-round budget expenditure of the spending plan, i.e., the Slater parameter of the offline allocation problem. Next, we focus on the OLRC setting. For the full feedback case, we develop a primal-dual
procedure that attains static regret of order O( Pmii VT). Similarly, we show that the results attained with full feedback can be generalized to the bandit feedback setting. All the algorithms mentioned above employ black box regret minimizers as primal and dual algorithms in order to be as general as possible. 2 We then focus on the case in which Pmin can be arbitrarily small and the results mentioned above become vacuous. For this case, we propose general meta- pert--proeeuree that modifies the input parameters of our (primal-)dur -dual methods, thereby attaining sublinear regret in the worst-case scenario, which is when Pmin I O(T-1/4), 1/4). For ORA, we show that the meta-procedure can still obtain Ö(T3/4) dynamic regret. For OLRC, we show that our meta-procedure guarantees (TT344) static regret. Finally, we show that the results mentioned above are robust to optimal solutions that follow the spending plan up to a sublinear error, thus analyzing sensitivity to suboptimal spending plans.
Comparison with [34, 13] In the context of ORA, variations of the spending plan problem have been previously studied by Jiang et al. [34], Balseiro et al. [13]. Specifically, [34, 13] study the ORA problem in which rewards and costs are drawn from adversarially changing distributions. In this setting, they assume that a certain amount of samples from the time-varying distributions are given beforehand. Then, the authors show how to use samples to build a spending plan that guarantees no regret during the madget-constrained learning dynamic. On the one hand, [34, 13] do not assume that a spending plan is given as input. Instead, their works focus on how to design robust spending plans and algorithms using available prior data. On the other hand, their analysis relies on the assumption that there exists a K. E 12 s.t. f((x) S (x) for all a E X,i E [m]. & E (7), and their regret
We remark that, in the ORA setting, there need for primal regret minimizer.

---

bound scales as (KKVT). This assumption allows them to avoid one of the main challenges in our work, which is the dependence on the minimum per-round budget provided by the spending plan. We refer to Appendix A for more detailed discussion of related work.
2 Preliminaries
We study problems where decision maker (the learner) is given T rounds, resources, and non- empty set of available strategies X C R", which may be non-convex, integral or even non-compact. At each round
[T] the learner selects strategy 2; E X, gains reward f((z)) [0. 1], and pays a cost ee ( [b] E [0. 1] for each resource E [m]." At each round t E [T), the reward function f::t X + [0, 1] is sampled from reward distribution Fi, while the cost function Ct X + [0, 1] is sampled from a cost distribution G.¹. We do not make any assumption on how Fr and C. are selected, namely, we allow them to be chosen adversarially, and thus change arbitrarily over the rounds. In the following, we will denote by Jt X > [0, 1] the expected value of Fg and by & X' + [0, 1) the expected value of Cr-
Each resource E [m]] is en- dowed with budget B; > 0 that the learner is allowed to spend over the T rounds. With- out loss of generality, we assume that B, = B for all E [m]] As is standard in the literature, focus the regime where B = Q(T) and we define the av- erage budget per round as p B/T. The interaction between
Protocol
Interaction
1: for 1 E [T] do
2:
Fi and C, are selected adversarially
3: Reward function ft ~ Fi and cost function C2 C. sampled
4:
Learner observes f. and ct
ORA
5:
Learner chooses strategy mixture E
6:
Learner plays a strategy æ; E.
7: Learner observes f; and ct
OLRC Full feed.
8:
Learner observes f((())) and (ars) OLRC Bandit feed.
9: Learner gets reward f((x:) and pays cost et (ax.))])) Vi E [m]
the learner and the environment stops at any round which the total cost associated to any resource E [m]] exceeds its budget B, The goal of the learner is to maximize the cumulative rewards attained during the learning process. As is standard in the literature (see, e.g., [14]), we assume that there exists void action x: E X' such that fe(x*) ) = for all & E [7]. and (x [[]] = 0, for every E [m] and & E [T]. This is done in order to guarantee that a feasible solution exists, namely, a sequence of decisions {a, { that does not violate the budget constraints. In the following, we will refer to the set of probability measures on X' as E, and
10: end for
[T'] in
we will call the set of strategy mixtures. Moreover, we will denote by e the Dirac strategy that deterministically plays the void action "
Protocol depicts the Seamee-ennironment interaction in the ORA setting, in the OLRC setting with full feedback, and in the OLRC with bandit feedback.
Remark 2.1 (Relation to the adversarial setting). In the standard adversarial setting. fi and ca are directly selected adversarially (refer to [14] for adversarial ORA and to [32] for adversarial OLRC), Our framework generalizes the adversarial setting. While the reward functions ft and the cost functions e are sampled from a distribution at each round, the distributions are allowed to change over the rounds. Thus, the standard adversarial setting can be recovered by assuming that Fe and C, always put their mass on a single point.
We now introduce the notion of spending plan. The learner is provided with sequence B {B(") p()) of per-round budgets for each resource E [m]] where Σ B.") B for all i [m] and B(() [0, 1] for all t [T', [m]. We refer (z(²) as the spending plan for the i-th resource, as it defines the maximum budget the learner can allocate at each time step t E [T], in expectation. Notice that the spending plan does not define hard budget constraints, differently from
We denote by 'n] the set (1,..., n with a Nyo- 'Given a vector we will denote by v[i] its j-th component.
"Notiee that J, and C. may correlated.
A problem with arbitrary budgets can be reduced to one with equal budgets by dividing, for every resource i (m]. all por-round resource consumptions (-)]i) by B,/ min, B3.
3

---

the overall budget constraint defined in Section 2. Indeed, the learner is allowed to deviate from the prescribed spending plan Byy as long as the overall budget constraint is satisfied.
We introduce two baselines to evaluate the performance of our algorithms. The dynamic optimal solution is defined by means of the following optimization problem:
SuPeE
ET f(( Ex [<: - B ViE [m]. Vt e [T]
Burng
OPT
(I)
s.L.
where E =
1=1 and & the i-th component of &. Problem (1) computes the expected value
attained by the optimal dynamic strategy mixture that satisfies the spending plan. The dynamic baseline is common in the ORA literature [14].
Similarly, we introduce the fixed optimum in hindsight by means of the optimization problem:
En-E ET [((
suppes
OPT
(2)
BE-e [[]] S B,O)) ViE [m], AL e [T]
s.t.
Problem (2) computes the expected value attained by the hindsight-optimal fixed strategy mixture that satisfies the spending plan. The fixed baseline is standard in OLRC [32, 19].
We define the minimum per-round budget in the spending plan as Punin == min min B(") Notice that Pmin is the Slater parameter of both Problems (1) and (2). Indeed, Pmin denotes the minimum margin by which the void action xº satisfies the constraints defined by the spending plan. Clearly, when Pmin = O, Slater's constraint qualification does not hold, meaning that the problem does not admit a strictly feasible solution. Intuitively, when Pmin is large, the spending plan distributes the budget B reasonably well across the rounds. This will lead to better performance during the learning dynamic
Performance Metrics In the ORA setting, we evaluate the performance of our algorithm via its dynamic cumulative regret Ry OPT Σ (xx)), which compares the total reward attained by the algorithm with the optimal dynamic solution that follows the spending plan recommendations. In the OLRC setting, evaluate the performance of our algorithm via its static cumulative regret
RT = OPTx - Σi= fz.z),, which compares the total reward attained by the algorithm with the optimal fixed solution that follows the spending plan recommendations. The aim of our work is to develop algorithms that attain sublinear regret bounds in their specific setting: Ry = o()) in ORA, and RT o(T) in OLRC.
Remark 2.2 (On the impossibility result of learning with budget constraints). It is well known that when no spending plan is available, it is impossible to achieve sublinear regret bounds in all the settings presented in this work, that is, when rewards and costs are allowed to vary over time (see, e.g. [12] for ORA and [32] for OLRC). We will show that exploiting the information given by the spending plan is enough to achieve sublinear regret.
Regret Minimizers We will employ regret minimizers (that is, no-regret algorithms) black-box tools. This is done to make the results as general as possible. Specifically, a regret minimizer RAA for a decision space W is an abstract model of a decision maker that repeatedly interacts with a black-box environment. At each time step E [T]. Rd may perform two operations: (i) RA .SelectDecision(). which outputs an element w. E W: (ii) R ReceiveFeeddacc(() (alternatively, R using feedback received from the environment. The feedback is given in terms of reward function r: W + [a, b). where (a, b] C IR when the regret minimizer is tailored for full feedback. When the regret minimizer tailored for bandit feedback, the feedback is given in terms of the reward attained in the previous timestep re (.x). The reward function r; may depend adversarially on the previous decisions W1 Wt- The goal of R is to output a sequence WI,... WT such that its cumulative regret, defined as supwew Σ (re(w) - re(w)) grows sublinearly with the time horizon T, that is, it is oT). For convenience, we introduce the notion of a regret minimizer constructor, a procedure
(1xx)) which updates the regret minimizer's 's internal state
We underline that regret minimizers with bandit feedback generally attain sublinear regret bounds which hold with probability at least 1 O(8), for all E (0, 1).

---

denoted as RA. .Iittaaize(WW, [a. b)) that builds regret minimizer based on two imput parameters: the decision set W and the payoff range [a, b]. This constructor returns a regret minimizer tailored to the given inputs, with the guarantee that its cumulative regret grows sublinearly in T. We will refer to the regret upper bound of the regret minimizer R.A time E [T] as R,A. Throughout the paper, we will assume that R I Rd for all < tt.
Online Resource Allocation
In this section, we provide the algorithm and analysis for the ORA setting.
Following the ORA literature, our algorithm works with the Lagrangian formulation of the problem where the budget constraints are relaxed with Lagrange multiplier vector X, namely f1,0, (E. =
Ex=s [=)] + Exe(m) A[i] (B(() E [c])) where f.c c are arbitrary reward and cost functions, and B is the per-round expenditure goal. Since both the reward function and the cost one are observed the beginning of the round have that the optimal strategy mixture &. of the Lagrangian function at time 1 E [T] can be computed directly for a fixed A by solving arg maxe ,,, (E. A²). On the other hand, the choice of X is not as obvious. This choice is handled by employing dual regret minimizer RP
Algorithm Dual Algorithm for ORA
Require: Horizon T. budget B, spending plans B for all i E [mn]. dual regret minimizer R (full feedbuck)
1: Set B B, for all E [m]]
2: Define = (> R20 : ||||| S 1/pmal)
3: RD Initialize 1-1//mnn 1/Pminl)
4: A + RD_ "...SeeetDecssion]]
5: for t [2] do
6: Observe reward function ft and costs function Ct
7:
&, - argmax Eang [fe(x))] - Eie[m) Ae[i] Eene (x)
w &. if Br, 2 1, vi E [m]]
8:
Play strategy: a. +
x otherwise
9:
Update budget availability Bi,t11 &- Bi, es (ax, [i] Vi [m]]
10:
rP - Evemin A (B()) Ea (c)]
11: R. ReceiveFeedback((?)
12: Update dual variable A441 t R2, .SeeecDDecision))
13:
end for
In Algorithm we provide the pseudocode of our algorithm. Specifically, the algorithm requires as input a dual regret minimizer R with feedback. Notice that the Lagrangian variable receives full feedback at each episode, as the reward r! associated to each possible Lagrangian space, can easily be computed. Line 1 initializes the budget available to the learner. Then, the Lagrangian space is built according to Pminn the Slater parameter of Program (1). It is well-known that in the standard ORA problem, it is sufficient to set L == {> R. ||||| S 1/p} to obtain the
L. where the
optimal competitive ratio In the ORA with spending plan setting, we extend this idea by bounding the Lagrangian space given the minimum per-round budget given by the spending plan. The dual algorithm is initialized work on the L decision space and with a payoff range [-1/Pmin, 1/Pmin.) while the first Lagrangian vector A₁ is selected given the initialization of the algorithm (Line 3 4). At each round
[T', the algorithm observes the feedback (Line 6), selects the strategy mixture & E E which maximizes the Lagrangian LJ. (E, A.) (Line 7) and accordingly plays the strategy when enough budget available (Line 8). Then, the algorithm updates the remaining budget (Line 9), builds the dual reward r for all À E L (L.ine 10) and inputs it to the dual regret minimizer (Line 11). Finally, the Lagrangian multipliers are updated given the feedback (Line 12).
II the ORA setting, when online mirror descent with fixed learning rate employed, dual regret minimizer can be directly instantiated in the positive orthant [14]. We explicitly bound the Lagrangian space to allow the choice of dual regret minimizers with time-varying learning rates, which generally need explicit bounds on the "dimeeter" of the decision space.
5

---

We highlight a subtle distinction between deterministic and randomized adversarial rewards in the spending- setting. In standard adversarial ORA settings where both the reward and the costs are deterministically chosen at each round, the spending-plan ORA problem can trivially be solved by setting & argmaxgez Be (f( s.t. Ben [o [x]] < B Vi E [m]] (for the sake of simplicity, we are assuming that this problem admits solution). This is not the case for our setting, because the baseline satisfies the spending plan only in expectation, whereas we observe only a
sample from the per-round reward and cost distributions.
3.1 Theoretical Results
In this section we show theoretical guarantees attained by Algorithm For additional lemmas and omitted proofs, we refer to Appendix 1.1. We first provide the following lemma which lower bounds the expected utility attained by Algorithm
Lemma 3.1. For any ò (0, Algorithm I, when instantiated with a dual regret minimizer which attains a regret upper bound RR. guarantees, with probability at least 1 - 6, Eis Ex-E, [fe( z
OPT -T- -- + 4 maxxec [1Al11) 2 % Ei= Eie(m (B, ( Eg Ice (zx(z))()))
2- RR,, where X E L is an arbitrary Lagrange multiplier and T is the stopping time of the algorithm.
Panin
Lemma 3.1 states that the expected cumulative reward attained by the algorithm until the stopping time T lower bounded by the dynamic optimum OPT minus the following quantities. The second term T - 7 measures early stopping time. The third term arises from a concentration argument. The fourth term captures the violation of the spending plan constraint by the algorithm during the learning dynamic. Finally, the last term is the regret guarantee attained by the dual algorithm. The multiplicative factor (m)) is due to the payoff range given to the dual regret minimizer.
We are now ready to show the final dynamic regret bound of Algorithm 1.
Theorem 3.2. For any ó E (0, 1), Algorithm instantiated with a dual regret minimizer which attains T h with
regret upper bound RT. guarantees Ry S 1+ probability at least 28.
1 Panin
2 Panin
RP
(
+
8 Pmin \v 2T
Theorem 3.2 has linear dependence the quantity 1/pmin- We underline that it is standard for (primal-)duu methods to have a dependence on the inverse of the Slater parameter of the offline problem in the regret bound (e.g. [25, 19, 14, 51]). From technical perspective this occurs because when T > T (i.e. the algorithm has depleted the budget associated with some resource), the Lagrangian variable associated with that specific resource must be set at 1/ //min to compensate the loss in terms of rewards given by the difference T - r. Given Theorem 3.2, it is easy to see that by employing online mirror descent [46] as a dual regret minimizer, the dynamic regret guarantee of Algorithm is of order Ry S 011 VT).
Online Learning with Resource Constraints
In this section we study the OLRC setting under both full feedback and bandit feedback. Notice that when the the reward and cost functions cannot be observed at the beginning of the round, it provably not possible achieve Ry oT)). Thus, we will focus on the less challenging objective of attaining Rr o(T). In Algorithm 2. we provide the pseudocode of our primal-dual method for OLRC. The parts highlighted in red are specific to OLRC with full feedback while the ones highlighted in blue are specific to OLRC with bandit feedback. The key differences between Algorithm 2 and our dual algorithm for the online resource allocation problem are as follows. First, since f. and o are not revealed in advance, the per-round optimal strategy mixture E., which maximizes the B, (E. A,) at time E [T), cannot be computed. We address this problem by employing a primal regret minimizer R. R which optimizes over the decision space E. In OLRC with full feedback, it is sufficient to employ a primal regret minimizer tailored for full feedback. In the bandit feedbuck case, a primal regret minimizer tailored for bandit feedback is necessary (e.g., EXP-3 IX [45], when X' is discrete number of arms). The primal regret minimizer is initialized with the strategy mixture decision space and the payoff range defined by the per-round Lagrangian (Line 3). At each round E [T', the strategy mixture is selected by the primal regret minimizer R (Line 6). In
Lagrangian function L,

---

Algorithm 2 Primal-Dual Algorithm for OLRC
Require: Horizon Т. budget B, spending plans ByG for all i E [m]] primal regret minimizer R² (full feedback/handit feedback), dual regret minimizer R. (full feedback)
1: Set B1, = B. for all i E [m]
2: Define L = (> R5o ||a|| 11/miin }
3: R" Initiaaize (E, 1/ Pmiin 1 + 1/ L/Pmin))
4: RD IInitialize (c. 1/ Pminn 1/Piil))
5: for t E [T] do
6: Select strategy mixture & R² SelectDecision(
7: Play strategy:
x ~ & Br, 2 1, Vi E [m]]
a
otherwise
8:
Observe the seedback as prescribed in Protocol 1
9:
Update budget availability B. &- Bi, - (xx)))] Vi E [m]]
10:
Update dual variable A R SelectDecision)(
11:
ri E 3 ++ Ense [[(())] Eve(m) Arli] En [x]]
12:
re (xx) + ((x)) Eie(m) Ax(i] (x(a))((i]
13:
R² ".RceiieFeedbacc((f))
: -Ee(m)) A/ll (B(²) Ex (x)))))))]
14:
p :LBA -vemm A/1 (B()) - (x))))11)
-
R Receivveeeddacc((()
17: end for
the full feedback case, the primal reward function- given for all possible strategy mixtures & E E-is fed back into R. (Line 1 11). In the bandit feedback case, the per round Lagrangian to be fed into the primal regret minimizer is computed as r. (xx) + (xx - ExE(m [ c (xx)) [i] (Line 12 13). Since the complete reward and costs function unknown with bandit feedback, it is not possible to build the Lagrangian for any strategy mixture & E E. Finally, we underline that since the dual
reward built as r? C A Eieimi A[i] (B() Eg [c((z)(i]] for the full feedback
case (Line 14) and as rP: L A +
Eie(m) A[i] (B,²) e (xx) the bandit feedback case (Line 15), it is still sufficient to employ a dual regret minimizer tailored for full feedback in the bandit case.
4.1 Theoretical Results
In this section, we provide the theoretical guarantees attained by Algorithm 2. We mainly focus on the full feedback case; we show later that almost identical theoretical results can be obtained for bandit feedback. For additional lemmas and omitted proofs with full feedback, we refer to Appendix C.I. Similarly, for additional lemmas and omitted proofs with bandit feedback, refer to Appendix D.1.
We start by lower bounding the expected reward attained by Algorithm
Lemma 4.1. For any å E (0, Algorithm 2 instantiated the full feedback setting with primal regret minimizer which attains a regret upper bound R2 and dual regret minimizer which attains a regret upper bound R.P, guarantees the following bound, with probability at least - 5:
IT Exrg, [ff( OPT (T 7) -) (D. -a Ica (x)) multiplier and T is the stopping time of the algorithm.
maxxeL 112111) 2 - Ali]-
2 2_RD
RD - Punia
2 R_, where X C is an arbitrary Lagrange
Puin
Lemma 4.1 shares many similarities with Lemma 3.1. Nonetheless, there are fundamental differences. First, the baseline is the fixed optimum OPT This is consequence of the primal update performed
7

---

by Algorithm 2. which is no-regret with respect to fixed strategy mixtures only. Furthermore, in Lemma 4.1 the expected reward lower bounded has an additional term which depends on the theoretical guarantees of the primal regret minimizer with a multiplicative factor (1 + 2/Pmin) due to payoff range given to the primal algorithm.
We now present the final regret bound.
Theorem 4.2. For any E (0.1) Algorithm 2, when instantiated in the full feedback setting with a primal regret minimizer which attains a regret upper bound Ri and dual regret minimizer which attains regret upper bound R.p. guarantees, with probability at least 25, the following regret
bound R S 1
RD + (1 Pmnin R )
8
V
Pinin
Punin
Pesin
Theorem 4.2 shows that learning with spending plan is still possible when both the reward and the costs functions are not observed beforehand. The main difference with the online resource allocation setting is that focus the standard regret definition Ry-and not dynamic regret- and pay an additional factor given by the primal no-regret guarantees. Finally notice that when RD ((VT) and R7 = Ö(VT), the cumulative regret is of order Pr < 01/ VT).
To extend the results above to the bandit feedback case, it is sufficient to notice that the optimal strategy mixture with respect to the Lagrangian a pure strategy, that
f((x)+ + E Aolil (B.² 1 -c(()
sup EEN
1=1
:E|m)
sup EE
[[(x))] + a
E
Σ Aeli iE(m]
- aree
The equation above allows us relate the regret guarantees attained by the primal regret minimizer with bandit feedback to the ones attained by the primal regret minimizer in the full feedback setting and thus, obtaining almost identical results. Finally, we remark that algorithms designed for bandit feedback typically guarantee performance only with high probability. Consequently, the bandit feedback regret bound holds with probability at least (8 + 8p), where åp is the confidence of algorithm R""
Remark 4.3 (Applications to multi-armed bandits with knapsacks). Consider the bandits with knapsacks problem with K arms (i.e. X [K]. We employ EXP-3 IX [45] as primal regret minimizer and online mirror descent with the negative entropy regularizer [46] as dual regret minimizer, and we assume that Puin constant independent of T. Then, for any 5 E (0,1), Algorithm 2 attains, with probability at least 1 - 25, Rr S O( / KT (og(mm/))).
5 Extensions
We provide extensions to our algorithms and analysis. We first show how to modify our algorithms in order ensure sublinear regret when Pmin is arbitrarily small. Then, we show performance guarantees for our algorithms against baselines which do not follow the spending plan.
5.1 Dealing with Arbitrarily Small Pmin
In this section we show how our algorithms may be modified to attain sublinear regret when Pmin is arbitrarily small. Specifically, we show that a regret of order ((T3/4) is still attainable for all Pmin S. p//1//1 Due to space constraints, we will focus on the online resource allocation problem. Nevertheless, the same ideas apply to the OLRC setting. We refer Appendix B.2, C.2, D.2 for the complete analysis, and the results for all three settings.
In Algorithm 3, we provide meta- meta- procedure which, by suitably modifying the input parameters given to Algorithm 1, achieves the desired theoretical guarantees. The meta-procedure is designed to be used when Pmin S // condition that can be checked in advance- in this regime, the dependence on 1/ 1/Pmin leads to suboptimal bounds compared to those obtain below. Specifically,

---

Algorithm 3 Meta-algorithm for arbitrarily small Priin
Require: Horizon T, budget B, spending plans B,6 for all i E [mm]. dual regret minimizer R (fill feedbuck)
1: Define P == p/T"/ where p = B/TT
2/4 2: Define B.") = ( - 4/44 vt e
3: Run Algorithm with Puiin + P, B + B
Algorithm 3 defines the capped minimum per-round budget ý = P/T (Line 1). This is done to prevent Algorithm from instantiating the dual regret minimizer over a decision space L which scales as 1/ Pmin- leading to the same dependence in the regret bound. Then, the algorithm rescales the spending plan by a (1 V4) factor (Line 2). Intuitively, this is necessary because the modified Lagrangian space L = {A R ||||| I 1/ is not large enough compensate the spending plan violations. Thus, we force the algorithm to learn a harder constraint associated to the rescaled
(t) spending plan. Finally, Algorithm is instantiated employing ý in place of Pmin and in place of B,O), for all t E [T], à E [m]] (Line 3).
Employing Algorithm 3, it is possible prove a similar result to Lemma 3.1. The key difference is that the payoff range of the dual and, in general, all the quantities which depend on the Lagrangian decision space, no longer scale as ((1/Pmin): ). but as OTT)/4/4/ /p). Moreover, while in the analysis of Algorithm 1 compensate the (T 7) term with Σi=1 Eie(m) Ali] (B, Ex [ce(z) in this case, we bound (T 7) directly. This is done in the following lemma.
Lemma 5.1. For any 8 E (0, 1), Algorithm 3 instantiated with dual regret minimizer which attains regret upper bound RP,, guarantees with probability least 1 6, T - T 14 P (V
B T
Lemma 5.1 is proved by contradiction. Intuitively, we show that scaling the spending plan by 7-14/ factor results in the impossibility to have both T > CT3/4 where C is a constant to be chosen, and the optimality of the strategy & with respect to the Lagrangian L,,,,, (E. Ae), which is true by definition. We underline that the RP/ / /TTT factor is independent of T for dual regret minimizer which attains regret of order O(VT).
We are now ready to provide the final dynamic regret bound.
Theorem 5.2. For any d (0,1), 1), Algorithmm 3, when instantiated with a dual regret minimizer which attains regret upper bound RP, guarantees, with probability at least - 35, Ri S
14
( In
T
R vT
T
+ T
+
47
/
2r +
Theorem 5.2 is proved employing Lemma 5.1 and bounding the loss in performance given by the fact the dynamic optimal baseline is not guaranteed to satisfy the scaled budgets B for all t E [7], E [m]] Finally, notice that employing online mirror descent [46] as a dual regret minimizer, the dynamic regret guarantees of Algorithm when compared with baseline which follows the spending plans are of order My S Ö(T3/1), since 1/p constant by definition.
As a final remark, we point out that if the number of rounds in which the per-round spending plan budget is smaller than T-444p p is at most vT, then employing the meta-procedure defined by Algorithm 3 can be avoided. Instead, one directly modify Algorithm so that it plays the void action x in each of those rounds. Since the entire spending plan is known in advance, this preprocessing step can be performed before the start of the learning dynamic. This modification allows us to obtain the same theoretical guarantees of Section 3 (i.e., when Pmin > T-1/1p). p). Intuitively, since the number of such rounds is relatively small compared to the time horizon, their contribution to the regret remains negligible.
5.2 Robustness to Baselines Deviating from the Spending Plan
In this section, we study the performance of our algorithms compared to baselines which do not strictly follow the spending plan. Due to space constraints, we will focus on the ORA set-

---

ting. Nevertheless, the same ideas apply to both the OLRC case. We refer to the Appendix (B.1.1, B.2.1. C.1.1 C.2.3, D.1.1, D.2.3) for the analysis and the results for all three settings.
Suppose we give the baseline an error budget E 2 0 for each i E [m]. f E [T], and allow the baseline to violate the per-round constraint by the given error. We define the dynamic optimal solution parametrized by the errors as the following optimization problem:
E Ele f(()))
SUPGEET S.
OPT (ft)
( (0) [m Eaing (xx)) S Bid + +
(3)
E Barre [x, S ViE [m]
Problem (3) computes the expected value attained by the optimal dynamic strategy mixture that satisfies the spending plan at each round E [T] up to the error term e defined for all i [m] and E [7]. The performance of our algorithms will smoothly degrade with the magnitude of these errors. We remark that the last group of constraints in Problem (3) ensures that the error terms do not allow the optimal solution to violate the aggregate budget constraints. Observe that when c, = 0 for all i E [m] and [T]- meaning that the spending plan is strictly followed by the optimal solution-the aggregate budget constraint is satisfied by the definition of the spending plan.
Similarly, we define the following notion of cumulative dynamic regret Rt(e))) OPT E.m fe(x;), which simply compares the rewards attained by the algorithm with respect to the optimal dynamic solution which follows the spending plan recommendations up to the errors.
We first provide the performance of Algorithm
Theorem 5.3. For any 5 E (0, 1), Algorithm I instantiated with a dual regret minimizer which attains regret upper bound R.p. guarantees, with probability least 1 - 26, Rr(() S 1 14 Amin
RD + (8
8 Pmiin
2T In
+
Pmnin ET= Ei=Em c0
Panin
Theorem 5.3 provides similar regret bound to the one of Theorem 3.2. The main difference is that Algorithm suffers an additional 1 +ET Eiejm) 4 term due to the error in the baseline definition and where the l/Pmi.. factor follows from the Lagrangian space definition. As is easy to see, the regret bound in Theorem 5.3 remains sublinear as long as the sequence of errors is itself sublinear.
Amin
We conclude by showing the dynamic regret of Algorithm 3 for arbitrarily small pmin-
Theorem 5.4. For any 5 E (0,1), 1), Algorithm 3, when instantiated with dual regret minimizer which attains a regret upper bound RP, guarantees, with probability at least 1 - -38, Ryr(e)) S
(V T
T
47
2T
2T RD +
2T
T
ΣJ Exe(m) "2 (1)
vT
Theorem 5.4 shows that it is possible to robust against a baseline which does not strictly follow the spending plan when Pmin is arbitrarily small. In such a case, the algorithm pays additional
T
(i) P E1= Eielm] et term, which follows from the definition of the Lagrangian space based on p.
T
Acknowledgments
This paper is supported by the Italian MIUR PRIN 2022 Project "Targeted Learning Dynamics: Computing Efficient and Fair Equilibria through No-Regret Algorithms", by the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationEU program within the PNRR- PE-AI scheme (M4C2, Investment 1.3, Line on Artificial Intelligence), and by the EU Horizon project ELIAS (Furopean Lighthouse of AI for Sustainability, No. 101 101120237). Christian Kroer is supported by the Office of Naval Research awards N00014-22-1 1-2300 and 400014-23-1-2374, and the National
Science Foundation awards IIS- 144361 and 2238960..
References
[1] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. International Conference Machine Learning, pages 1638-1646. PMLR, 2014.
10

---

[2] Shipra Agrawal and Nikhil R. Devanur. Fast algorithms for online stochastic convex program- ming. In Proceedings of the twenty- sixtt annual ACM-SIAM symposium on Discrete algorithms, pages 1405-1424, 2014.
[3] Shipra Agrawal and Nikhil R Devanur. Bandits with concave rewards and convex knapsacks. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 989-1006.
ACM, 2014.
[4] Shipra Agrawal and Nikhil R Devanur. Bandits with global convex constraints and objective. Operations Research, 67(5): 2019.
[5] Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A dynamic near-optimal algorithm for online linear programming. Operations Research, 62(4):876-88) 890, 2014.
[6] Shipra Agrawal, Nikhil R Devanur, and Lihong Li. An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives. In 29th Annual Conference Learning Theory (COLT), 2016.
[7] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knap- sacks. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013, pages 207-216. IEEE, 2013.
[8] Ashwinkumar Badanidiyuru, John Langford, and Alcksandrs Slivkins. Resourceful contextual bandits. In Conference Learning Theory, pages 1109-1134. PMLR, 2014.
[9] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knap- sacks. J. ACM, 65(3), 2018
[10] Qinbo Bai, Vaneet Aggarwal, and Ather Gattami. Provably efficient model-free algorithm for mdps with peak constraints. arXiv preprint arXiv:2003. 055555, 2020.
[11] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Dual mirror descent for online allocation problems. In International Conference on Machine Learning. pages 613 328. PMLR, 2020.
[12] Santiago R Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, 65(9):3952-390 2019.
[13] Santiago R Balseiro, Rachitesh Kumar, Vahab Mirrokni, Balasubramanian Sivan, and Di Wang. Robust budget pacing with a single sample. In International Conference on Machine Learning, pages 1636-1659. PMLR, 2023.
[14] Santiago R Balseiro, Haihao Lu, and Vahab Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. Operations Research, 7 71(1):101-119, 2023.
[15] Omar Besbes and Assaf Zeevi. Dynamic pricing without knowing the demand function: Risk bounds and optimoltimal algorithms. Operations Research, 57(6): (00.):1407-14000 1420, 2009.
[16] Kianté Brantley, Miro Dudik, Thodoris Lykouris, Sobhan Miryoosefi, Max Simchowitz, Alek- sandrs Slivkins, and Wen Sun. Constrained episodic reinforcement learning in concave-convex and knapsack settings. Advances in Neural Information Processing Systems, 33:163155-63222 2020.
[17] Mark Braverman, Jingyi Liu, Jieming Mao, Jon Schneider, and Eric Xue. A new benchmark for online learning with badeet-balancing constraints, 2025, URL https: h org/ abs/ 2503. 14796.
[18] Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor. Online primal-dual algorithms for maxi- mizing ad-auctions revenue. In European Symposium on Algorithms, pages 253-264. Springer, 2007.
[19] Matteo Castiglioni, Andrea Celli, and Christian Kroer. Online learning with knapsacks: the best of both worlds. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 2767-2783 PMIR, 17-23 Jul 2022. URL tttps://proceede
mlr, www.ss/sssseee wwt.///asssgggionn2222 html.
11

---

[20] Matteo Castiglioni. Andrea Celli, Alberto Marchesi, Giulia Romano, and Nicola Gatti. A unifying framework for online optimization with long-term constraints. Advances in Neural Information Processing Systems, 35:33589-33602, 2022.
[21] Nikhil Devanur and Thomas Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce, pages 71-78, 2009.
[22] Nikhil R Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A Wilkens. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Journal of the ACM (JACM), 66(1):1-41, 2019.
[23] Yuhao Ding and Javad Lavaci. Provably efficient primal reinforcement learning for cmdps with non-stationary objectives and constraints. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 7396-7404, 2023.
[24] Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits. In Proceedings of the Twenty-Seventh Conference Uncertainty in Artificial Intelligence, pages 169-178, 2011.
[25] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitttio in constrained mdps, 2020. URL ptctts://arrtn org http//aab////...0./ 02189.
[26] Jon Feldman, Nitish Korula, Vahab Mirrokni, Shanmugavelayutham Muthukrishnan, and Martin Pál. Online ad assignment with free disposal. In International workshop on internet and network economics, pages 374-385. Springer, 2009.
[27] Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, and Cliff Stein. Online stochastic packing applied to display ad allocation. In Proceedings of the 18th annual European conference on Algorithms, 2010.
[28] Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. Budget pacing in repeated auctions: Regret and efficiency without convergence. 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251, page 52, 2023.
[29] Aditya Gangrade, Tianrui Chen, and Venkatesh Saligrama. Safe linear bandits over unknown polytopes. In Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 1755-1795. PMLR, 2024.
[30] Anupam Gupta and Marco Molinaro. How the experts algorithm can help solve lps online. Mathematics of Operations Research, 41(4):1404-1431, 2016.
[31] Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, and Aleksandrs Slivkins. Adversarial bandits with knapsacks. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 202-219, IEEE Computer Society, 2019.
[32] Nicole Immorlica, Karthik Sankararaman, Robert Schapire, and Aleksandrs Slivkins. Adversar- ial bandits with knapsacks. Journal of the ACM, 69(6):1-47, 2022.
[33] Rodolphe Jenatton, Jim Huang, and Cédric Archambeau. Adaptive algorithms for online convex optimization with long-term constraints. In International Conference on Machine Learning. pages 402-411. PMIR, 2016.
[34] Jiashuo Jiang. Xiaocheng Li, and Jiawei Zhang. Online stochastic optimization with wasserstein based non-stationarity. arXiv preprint urXiv:2012.06661, 2020.
[35] Yash Kanoria and Pengyu Qian. Blind dynamic resource allocation in closed networks via mirror backpressure. In Proceedings of the 2 ACM Conference on Economics and Computation, page 503, New York, NY, USA, 2020. Association for Computing Machinery.
[36] Thomas Kesselheim and Sahil Singla. Online learning with vector costs and bandits with knapsacks. In Conference on Learning Theory, pages 2205-2305. PMLR, 2020.
12

---

[37] Thomas Kesselheim, Andreas Tönnis, Klaus Radke, and Berthold Vöcking. Primal beats dual on online packing lps the random-order model. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 303-312, 2014.
[38] Bhuvesh Kumar, Jamie Morgenstem, and Okke Schrijwers. Optimal spend rate estimation and pacing for ad campaigns with budgets. arXiv preprint arXiv:2202.0588)) 2022.
[39] Nikolaos Liakopoulos, Apostolos Destounis, Georgios Paschos, Thrasyvoulos Spyropoulos, and Panayotis Mertikopoulos. Cautious regret minimization: Online optimization with long- term budget constraints. In International Conference on Machine Learning, pages 3944-3952. PMLR, 2019.
[40] Tao Liu, Ruida Zhou, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Learning policies with zero or bounded constraint violation for constrained mdps. Advances in Neural Information Processing Systems, 14:17183-17199 2021.
[41] Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: online convex optimization with long term constraints. The Journal of Machine Learning Research, 13(1): 2503-2528, 2012.
[42] Shie Mannor, John N. Tsitsiklis, and Jia Yuan Yu. Online learning with sample path constraints. Journal of Machine Learning Research, 10(20):56--590, 2009. URL http:// /mmr org/ papers/v catrr//v1mmmamoor// html.
[43] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22-es, 2007.
[44] Adrian Müller, Pragnya Alatur, Volkan Cevher, Giorgia Ramponi, and Niao He. Truly no-regret learning in constrained mdps. In Forty-first International Conference on Machine Learning. 2024.
[45] Gergely Neu. Explore more: Improved high probbabbbbbilitt regret bounds for non- stochastic bandits. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, ed- itors, Advances in Neural Information Processing Systems, volume 28, Curran Associates, Inc., 2015.
neurueeriddnnnnnnnnnpppee. cc/paper.r.p.....e httppprrfileespppprr//////////// (5a4661100122887777666600....dd0 Paper. .df.
[46] Francesco Orabona. A modern introduction online learning. CoRR, abs/1912.13213. URL http://arxiv wtw.a/wwwwwi..aaaaaeeaaaeeooeeee httgg/bb/1991..11.1
[47] Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, and Heinrich Jiang. Stochastic bandits with linear constraints. In International conference on artificial intelligence and statistics, pages 2827-2835. PMLR, 2021.
[48] Karthik Abinav Sankararaman and Aleksandrs Slivkins. Combinatorial semi-bandits with knapsacks. In International Conference on Artificial Intelligence and Statistics, pages 1760- 1770. PMLR, 2018
[49] Abhishek Sinha and Rahul Vaze. Optimal algorithms for online convex optimization with adversarial constraints. Advances in Neural Information Processing Systems, 37:41274-41302, 2024.
[50] Aleksandrs Slivkins, Karthik Abinav Sankararaman, and Dylan J Foster. Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression. In The Thirty Sixth Annual Conference on Learning Theory, pages 4633-4656. PMLR, 2023.
[51] Francesco Emanuele Stradi, Jacopo Germano, Gianmarco Genalti, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Online learning in CMDPs: Handling stochastic and adversarial constraints. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller. Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 16721. PMLR, 21-27 Jul 2024. URL https: https:t/t///ooteeeeee procceeddinggs mlr. .pees// v235/ sttssstri4.. html.
13

---

[52] Francesco Emanuele Stradi, Anna Lunghi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Learning constrained markov decision processes with stttstottonayy rewards and con- straints, 2024. URL. https: /tappp:://rxiiiii //txxvixvvvv//////// http://wwwww....aaaaaa//eaaaaa/e
14372.
[53] Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Learning adversarial mdps with stochastic hard constraints. In Forty- -Sccnn- International Conference on Machine Learning, 2025.
[54] Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Optimal strong regret and violation in constrained mdps via policy optimization. In The Thirteenth International Conference on Learning Representations, 2025.
[55] Francesco Emanuele Stradi, Anna Lunghi, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti, al. Policy optimization for emdps with bandit feedback: Learning stochastic and adversarial constraints. In Forty-Second International Conference on Machine Learning. 2025.
[56] Rui Sun, Xinshang Wang, and Zijie Zhou. Near-optimal primal-dual algorithms for quantity- based network revenue management. Available SSRN 3728397, 2020.
[57] Kalyan T Talluri and Garrett Van Ryzin. The theory and practice of revenue management, volume 68. Springer Science & Business Media, 2006.
(58) Xiaohan Wei, Hao Yu, and Michael J. Neely. Online learning in weakly coupled markov decision processes: A convergence time study. Proc. ACM Meas. Anal. Comput. Syst. 2(1), 2018.
[59] Hao Yu, Michael Neely, and Xiaohan Wei. Online convex optimization with stochastic con- straints. Advances in Neural Information Processing Systems, 30, 2017.
[60] Liyuan Zheng and Lillian Ratiff. Constrained upper confidence reinforcement learning. In Alexandre M. Bayen, Ali Jadbabaic, George Pappas, Pablo A. Parrilo, Benjamin Recht, Claire Tomlin, and Melanie Zeilinger, editors, Proceedings of the 2nd Conference on Learning for Dynamics and Control, volume 120 of Proceedings of Machine Learning Research, pages 620- URL https: httpps:///rrroee http///pooeeeen...///////// mlr, press/sssseee.... /vts//v1///////// wtlvvv/2//e2/g/e zzhngg2a..
629. PMLR, 10-11 Jun 2020.
html.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction state all the main contributions made by the
paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
14

---

Justification:
All the assumptions are clearly stated in Section 2.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approxinations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All the theoretical results clearly state their assumptions, while all their proof's are provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
15

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
Beeiiiigguides/Codeeuue www.ssubbsssioooooooooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //n cta.pss.cc/uubiccuuuuuu gesds//////eeeeeee/e /CodeSubmian ss onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
16

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
17

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //tpprs////uuss.../// cc/public/Ethi ctwuidelsclllllcccccccccccc ines?
Answer: [Yes]
Justification:
The paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed, since the work is mainly theoretical.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
18

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- ce-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
19

---

Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification:
The paper does not involve LLMs as any important, original, or non- non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non- non-standard components.
Please refer to our LLM policy (https:/ httpp:////eurips// wweeurips.cc/oofeeeeeeeeeeeee erc/oonffrennee/22255 for what should or should be described.
20

---

Appendix
The appendix is structured as follows:
In Appendix A, we provide further discussion on related works.
Appendix B, we provide additional lemmas and the omitted proof for the ORA setting.
In Appendix C, we provide additional lemmas and the omitted proof for the OLRC setting under full feedback.
In Appendix D, we provide additional lemmas and the omitted proof for the OLRC setting under bandit feedback.
In Appendix E, we provide some technical lemmas which are necessary to prove the main results of our work.
A Related Works
In the following, we highlight the works that are mainly related to ours. Specifically, we will focus on the ORA literature, on the OLRC (in particular, bandits with knapsacks) one and, finally, on the learning with general constraints literature.
Online Resource Allocation Early works on online allocation mostly focus on settings where the reward and costs/resource functiins are linear in the decision variables, especially in the random permutation model. In this setup, an adversary chooses a fixed list of requests, which are then shown in random order. Devanur and Hayes [21] studied the AdWords problem and introduced a two-step method using dual variables. Their method has regret of order ( Feldman et al. [27] proposed similar training- bbsed methods for a wider range of linear allocation problems. attaining comparable regret bounds. Later, Agrawal et al. [5]. Devanur et al. [22], and Kesselheim et al. [37] improved these ideas by designing algorithms that update decisions over time by solving linear programs repeatedly using accumulated data. These methods brought the regret down to O(T)/2) and scale better with more resources. Gupta and Molinaro [30] extended this type of approach to the random permutation model. Agrawal and Devanur [2] suggested a similar algorithm that keeps and updates dual variables, but it either needs prior knowledge of a benchmark value or must solve extra optimization problems to estimate it. Balseiro et al. [11] proposed dual mirror descent algorithm for problems with concave rewards and stochastic rewards/costs, getting (TT)/) regret. Sun et al. [56] showed algorithm that gets better than O /2) regret when the request distribution is known. Kanoria and Qian [35] used online dual mirror descent in managing circulating resources in closed systems, such as those used in ride-hailing platforms. Differently, in the adversarial online allocation problem, sublinear regret is not possible, so the goal becomes designing algorithms with constant-factor guarantees compared to the offline optimum. Mehta al. [43] and Buchbinder et al. [18] studied the AdWords problem- a special case of online matching where rewards are proportional to resource usage. They proposed primal-dual algorithms that get (1 1/e) competitive ratio, which is known be the best possible. But when rewards are not proportional to the resource consumption, a fixed competitive ratio cannot be ensured. To handle this, Feldman et al. [26] suggested a version with free disposal, where resource limits can be exceeded, and only the highest-reward allocations count in the objective. Their method also achieves a (1 1/e) competitive ratio. Gaitonde et al. [28] study bidding algorithms with aggregate guarantees in terms of overall market efficiency, without relying convergence. Balseiro al. [14] develop the first manooaaooooldds algorithm for the online allocation problem. Their algorithm simultaneously handle stochastic, adversarial and non-stationary rewards/costs. In a recent work, Balseiro et al. [13] study the online allocation problem where a sample from each adversarially changing distributions Fe, C. is known beforehand. To show that, in such a setting, it is possible to achieve sublinear regret-this is possible when the samples are slightly corrupted, too-, the authors develop a dual algorithm which works with estimated spending plan. When this spending plan is correct, their algorithm shares different similarities with Algorithm 1. Nonetheless, their analysis relies on the assumption that there exists a R2o s.t. fx S (z)) for all x E X, E [T]. and their regret bound scales as T(. This is not the case in our work, where we study the standard online allocation problem as presented in Balseiro et al. [14].
Balseiro et al. [13] focus online allocation with single resource.
21

---

Online Learning with Resource Constraints The stochastic bandits with knapsacks framework was originally introduced and optimally solved by Badanidiyuru al. [7. 9]. Subsequently, other algorithms achieving optimal regret in the stochastic setting were developed by Agrawal and Devanur [3, 4] and Immorlica et al. [31]. Over time, the bandits with knapsack framework has been extended to variety of scenarios, including more general types of constraints [3, 4), contextual bandits [24, 8, I, 6, 50], and combinatorial semi-bandits [48]. The adversarial version of bandits with knapsacks was introduced by Immorlica et al. [31, 32], who showed that it is possible to achieve a (m log T") competitive ratio when an oblivious adversary selects the rewards and costs. Immorlica et al. [31, 32] also establish matching lower bound, proving that algorithm
achieve better than O T) competitive ratio on all instances, even with just two arms and one resource. This lower bound was further tightened by Kesselheim and Singla [36], who show an (log log T`) competitive ratio, and demonstrate that it is optimal up to constant factors for the general adversarial bandits with algorithm for bandits with knapsacks. The authors propose primal-dual algorithm which simultaneously handle stochastic and adversarial rewards/cost function. They propose algorithm for the full feedback setting and one for the bandit feedback case. In contemporaneous work, Braverman et al. [17] show how it possible overcome the impossibility result for adversarial bandits with knapsacks for specific benchmarks, which, intuitively, are not too far from the solution who spends the budget uniformly over the rounds.
knapsacks setting. Castiglioni et al. [19] propose the first best-of-both-wond
Learning with General Constraints There exists an extended literature on online learning problem with general constraints (e.g., [42, 39J). Two main settings are usually studied. In the soft constraints setting (e.g.. [20]). the aim is to guarantee that the constraint violations incurred by the algorithm grow sub-linearly. In the hard constraints setting, the algorithms must satisfy the constraints at every round, by assuming knowledge of a strictly feasible decision (e.g., [47]). Both soft and hard constraints have been generalized settings that are more challenging than multi armed bandits, such as linear bandits (e.g., [29]). We acknowledge that online learning with constraints has been studies even in multi-state environment such as constrained Markov decision processes (CMDPs) [58, 25, 60, 10, 16, 40, 23, 51, 53, 44, 52, 54, 55J. Some works focus on constrained online convex optimization settings (egg.. [41, 33, 49]).
B Omitted Proofs for Online Resource Allocation
In this section, we provide the results and the omitted proofs for the online resource allocation setting.
B.1 Theoretical Guarantees of Algorithm 1
We start by providing the results for Algorithm 1. Specifically, lower bound the expected rewards attained by the algorithm as follows.
Lemma B.1. Algorithm 1, when instantiated with a dual regret minimizer which attains a regret upper bound R2F guarantees the following bound:
Σ E
[f(())]
>
E (ee)(e)
[f((z)] - Σ Acle (1(0-
- E m)git)
Ic (2)(2))
3Emml
Σ Ao] t=1 [E(m)
B(O))
[c((z)101]
2 R.D Pmiin
where À E C is an arbitrary Lagrange multiplier, (E(()) = an arbitrary sequence of strategy mixtures and is the stopping time of the algorithm.
Proof. In the following, we aim at bounding the rewards attained by Algorithm I during the learning dynamic, that is, until the round 7 the algorithm has depleted its budget. First, by the strategy mixture selection criterion, it holds:
[f(())] - Σ X w>w
E.
E ane [c]())[[]]
< E
[[((=)]
Σ [E(m)
Aeli
E. znde.
[c](x)((]].
(4)
a~E.
sE(m]
22

---

for all & E E and for all t E [7].
Summing Equation (4) over t we obtain, for all sequences
(5(0)
E E the following bound:
E [f(())]
Σ
E #)
[c(
sc(m)
Σ tml
E
[f((z)]
E
E argg.
[cr())
ærde
ic(m)
which in turn implies:
E [+()
Σ
[f(()]]
Σ +E|m]
A
[+(x)|+++++++++
Σ ic(m]
E Ir
[c(()))ii]
Employing the dual regret minimizer guarantees, we have, for any Lagrange variable A A L:
Ald
[
E m-
Σ
Σ
A
[B
E
[c((z)(11]
R..
Pmin
1=1 1m|m
1=1 FE[m]
where the 2 dependence follows from the payoff's' range of the dual regret minimizer.
Prom
Thus, substituting Equation (5) in the previous bound, we get:
Σ E x~
[ff((=)]
[f(())]
Σ
Aclll B
Ic
(x)))
xngit)
xm(m)
2 Pmin
Alil
B
E x
[cr(z)lil)
R2.
t=
kE|m]
This concludes the proof.
We proceed by relating the previous lower bound to the dynamic optimum.
Lemma 3.1. For any 8 E (0, 1), Algorithm 1, when instantiated with a dual regret minimizer which attains regret upper bound Rp. guarantees, with probability at least 1 - 5. Σ En [fr
- -) -4 maxxec [[Ali)) / 2r In 2 - Eie[m) (BB En [ce (())
Panin RD, where À L is arbitrary Lagrange multiplier and is the stopping time of the algorithm.
Proof. We first employ Lemma B.1 to obtain, for all strategy mixtures sequences (g(() E EE) and for all Lagrangian variables X E L, the following lower bound:
Σ E t=1 Eー
[f(()))
[f(())]
Σ
Acli)
B
(ea (a:) (c)
(t))(t))
1=1
sE/m]
Ali
B
[c((z))(l]]
2 RDD
Pmin
KE km|m
We now focus on lower bounding the following term:
[f(())]
Σ
E [cx(x)[[]] aneilo
(E(m)
Thus, notice that by the definition of Program (I), there exists sequence strategy mixture {$t [ such that Ex-g; (x)) < B for all t [T], e [m] and ΣT Ex-e; [fo())] 2 OPT for
23

---

all > O. In the rest of the proof, we will omit the the dependence on y, since it can be chosen arbitrarily small, thus being negligible in the regret bound.
and employing Lemma E.2, the quantity of interest is lower bounded Selecting (T {E
as:
E
[[([z]]
Σ Arli]
(B())
E wm
2 w~/r
ic(m]
[x( ) w
E wn
[f((z))] - Σ
B
E
1=1
iE[ma
4 + max |
2T In 8
XEC
which holds with probability least 1 - 8. Moreover, by the baseline definition, it holds:
ΣΣ x1
E 2~
[=(())(i]] 2 0,
1=1 6e[m]
since the dynamic optimum satisfies the learning plan each round.
Combining everything, we get, with probability at least - 8, the following lower bound:
E
[f((z)]
-
Σ Aol [B.)
E a
(es(2)1111
E
RE|m
[F((x)] - Σ Aolil - (D!
E
E.
arer
t=1
iE(m)
(4 + 4 max |
1 27 In
T
dEC
T
E [f((z)]
+4+4
4max [1 XEC
2T In
m=/
x
OPT - -T-
max Aec
||
/ 8"
Noticing that by the update of Algorithm 1, it holds:
T E [1(())] = Σ [(((t)] E
Σ
x
1=1
which concludes the proof.
We are now ready to prove the final regret bound for Algorithm 1.
Theorem 3.2. For any 8 1), Algorithm instantiated with dual regret minimizer which attains a regret upper bound RR. guarantees Ri 1++ Proin
2
RP
+
_8__
v 2T T. with
Priit
Pmm
probability at least 28.
Proof. We start by employing Lemma 3.1 to get, with probability least
the following bound:
/ 2 In T 5
Σ
E E-
[f(())] > OPTp (T -T-7) -) 4 4 max
|A]ls
ACC
Alil
((())
E.
[ct(x)((1]
2 RD Pmin
x-E.
1=1 mm(m)
24

---

Thus, we employ Lemma E.I, to recover the following result, which holds with probability at least
1 26, by Union Bound:
T
Σ (()) 2 OPTD - (T (T- (4+
000+ max dEC
|All1)
2 In
T
8
ΣΣ A|l- -c(
2
R (4 + 4|12111)
T 2n
Pmin
8'
ic/m]
which in turn implies the following dynamic regret bound:
Mi S (T -)
Aid (B. - c2((x))()) + R² + +8+ 8 max
XEL |1l1))
V
T 2T In
8
Punin
km(m)
which holds with probability at least 26. We now split the analysis in two cases. Specifically, in case (t), it holds 7 = namely, the algorithm has not depleted the budget during the learning dynamic, while case (ii), it holds T > T.
Bound for case (i). When I' T, we choose À 0 to obtain, with probability at least 1 - 28:
Mr S (T -)
2 R. + (s+ max Pmin
|AlI,)
y 2n 8
T
XEL
Bound for case (it). When T> > T, we notice that, due the budget constraints, there exists a resource i' E [m] such that the following holds:
Ea(a))1+1123
Σ B(D)
t=1
Thus, the dynamic regret can be bounded with probability at least 25 as follows:
Ri s (T- +)+ + 8
8 Pmin
2T In
T
Alt]
(B -c( +
2
R
8
Pmin
1=1 iE[m]
ST T) + 8
8
2T 6
In
T
+
B
Σ
B
(()) +1/
+
2 R
Pmin
Pmin
Pain
t=1
T
(T 7) +
+
2T 8
In
T
B(t")
+1
2
R
Pmin
Pmin
Pmin
Mer+1
T Σ
8
T
1
2
(T 7) + 8 +
2r
In
Pmin + 1
+
R
Pinin
8
Pain 115+|
Puin
8
T
$ (T 7) + 8 +
2r
In
(T T) 11
R
Pinin
8
Pmin
Pmin
S1+ +
8 +
2T In
+
RP.
Punin
Pauin
8
Pmin
where the first incquality holds since maxxec ||A||1
< Piotn and the second inequality holds by
selecting À such that A[;*|= 1 and A = 0 for all others E [m]]
Pmin
Finally, we notice the following trivial bounds:
8
)
T 2r
<
8 Pwii
T 8
R < RG,
(s+
<
V 22T In
Pmin
8
This concludes the proof.
25

---

B.1.1 Robustness to Baselines Deviating from the Spending Plan
We provide the regret of Algorithm with respect to a baseline which deviates from the spending plan.
Theorem 5.3. For any å E (0, 1), Algorithm 1 instantiated with dual regret minimizer which
attains a regret upper bound RG. guarantees, with probability at least 1 - 26, Rr(e;) S 1+
R
+
8 +
8 Pmin
2T 1n
E
Panin
Similarly to Lemma 3.1, we employ Lemma B.1 to obtain, for all strategy mixtures sequences (g(t) E =m1 and for all Lagrangian variables X E C. the following lower bound:
Proof.
Σ E [ff())] Sr
[f(())]
Σ
Acli]-
(B(")
Ice (2))
xn(())
sE/m]
A
B
E
[er(z))ii)]
R²P
Pmin
t=
RE
The key difference with respect to the analysis of Lemma 3.1 is how to bound the following term:
x Ex10 (B(0)
E a0((())
[[(x=)]
E ange(e
[cc(ar](i]
rE(m]
Thus, notice that by the definition of Program (3), there exists sequence strategy mixture [$:]7=
such that Ez-e; [x)] S BiS9) ( for all E [T], [m] and Σ/= Ez-E; [f) 2
(PT - 7. for all y > 0. In the rest of the proof, we will omit the the dependence on 7
since it can be chosen arbitrarily small, thus being negligible in the regret bound.
Selecting (_= (Er) and employing Lemma E.2, the quantity of interest is lower bounded as:
[f((x)]
Σ iE[m]
Aell
B(())
(e(())(01)
x-
E am
[f((z)]
- Σ Aelil
(z)
iE(m)
T
4 max
DEL [1
V 2T In 8:
which holds with probability at least 1 8. Moreover, by the baseline definition, it holds:
Σ
Acli] - ( -
[=(())[i]]
Σ
Pmin t=1 (m(m)
(=1 [m(m)
since the dynamic optimum satisfies the learning plan at each round, up to the error terms.
Combining everything, we get, with probability at least 1- - 8, the following lower bound:
[c((=)10]] )
E [f((z)] - Σ Aeli
Bi
E w
eE(m)
E
[f(()]]
Σ Ar [
E
[2, (z) (x))
4 + 4 4mx AEC
[1|11)
2 In
T
x
1=1
5Emm]
F.
[f(x))]
(1) (1
max
|| ||
V
27 In
T
Pmin
dEc
1=1 (m]
26

---

(1) - -(1+ 4mx 12lla) 4
2 T
OPTp(()) (T -)
Pmin [=1 (E(m]
Noticing that by the update of Algorithm 1, holds:
Σ E x~
[1(x))= x~
[f(x)))
and employing Lemma E.I, we get the following bound:
Σ (1)))) OPTo(e) - (T -
T
ct (1)
+ max 12
V 2T T
Pmii iE(mm]
dEC
Σ Σ Abi (B()) - -ce(ac)li)
2
R2 (4 (4
27 +4
T
Pmin
t=1 [E[m]
which holds with probability at least Theorem 3.2 and noticing that:
25, by Union Bound. Thus, employing the same analysis of
ΣΣ t=1 ve(m
[E(m]
concludes the proof.
B.2 Theoretical Guarantees of Algorithm 3
In this section, we present the results attained by the meta procedure provided in Algorithm 3. We start by the following lemma.
Lemma B.2. Algorithm when instantiated with dual regret minimizer which attains regret upper bound R2,, guarantees the following bound:
Σ E x>
[fa(z)]
2
[f((x)]
Σ xE(m]
Acli).
B
lc(())((])
senug(e)
ang(())
t=1
Σ Ail--
B ang.
E
[c(())lil]
RDD
where À E C is an arbitrary Lagrange multiplier, (g(() mixtures and is the stopping time of the algorithm.
= an arbitrary sequence of strategy
Proof. The proof equivalent the one of Lemma B.1 after substituting Pmin with P and B with D for all i [m]] t [T].
Lemma B.3, For any å E (0, 1), Algorithm 3, when instantiated with a dual regret minimizer which attains a regret upper bound R guarantees, with probability at least
- Σ E I OPT- (I - 4
4T
V
In
T
2T
RP
where is the stopping time of the algorithm.
Proof. We first employ Lemma B.2 and the definition of و to obtain:
Σ
Σ E x
[f((())
[f(())]
Σ
A
B
[c(x)((i]
1=1 sn
xmmm]
27

---

27
Σ
E
[0]
B
E
RpP
p
t=1 kE|m]
Hence, we select the Lagrange variable as x
vector to get the following bound:
la (c(())
27 R.D
E
[f)(
[f(())]
Σ
B
@)g())
p
XE [m]
We now focus on bounding the term:
E [f(())] - Σ angitt)
A
B
E w
(cx( [x]]
(E[m]
Similarly to Lemma 3.1, we notice that by the definition of Program (1), there exists a se- quence strategy mixture (E:)=1 such that En-e; [<x(,)] S B(") for all / E [T], E [m]] and Ezrg: [f(())] 2 OPTp - 7 for all y > 0. In the rest of the proof, we will omit the the dependence on y, since it can be chosen arbitrarily small, thus being negligible in the regret bound.
We then define the following strategy mixture E: for all E [T] as follows:
x E w.p. 1 - 1/T1/44
w.p. 1/r1/4
===
Thus, we first show that E satisfies the per-round expected constraints defined by B," Indeed holds, for all i E [m]:
B
E [x)( = B!()) x-
(1-
1
E
[x)
E [()(
[(x(2)]
T1/1
T1/I
a=
1
1
BB())
1
E
1
E [c))
T1/4
T1/4
w
T1/4
m_ea
1
1
Bi
())
1
E [cx(x)]
71/1
T1/4
0,
where we employed the definition of Eū and 8². Thus, returning to the quantity of interest and selecting (g(0)T = Hm.. it holds:
E + Σ A1ll-
[f(())]
Bid))
E m())())
(e((z)((il)
((t)
xE|ml
E [f(())] + Σ
Acl1] -
B (
[cd(x)](1]]
m
1=1
(c(m)
E
[f((x)]
+ Σ
A ,
B (t)
(4+ 4+ 472/4)
T 2n
8
+E(m²
E
[[((ar]]
-
4
4T1/44
1 27
In
T
|
71/4
1
E
[f((z]]
+
7//4
x
E
[f((
-
4
4T1/44
V
2
T
3
(1- T1/4
1
E.
[[(a))]]
- (4+
V
2T In
T
28

---

Σ t=1
E m=
[f((z]] - -T3/4 -(++ /
4T
2 In
T
P
OPT 73/4 - -3 -04 4/ 2T In 8
where the second inequality holds, with probability at least 8, by Lemma E.2 and upper bounding the Lagrangian multiplier with T /e. This concludes the proof.
Hence, we proceed upper bounding the difference between the horizon T and the stopping time T. Lemma 5.1. For any 8 (0, 1), Algorithm 3 instantiated with dual regret minimizer which attains
regret upper bound Re., guarantees with probability least 1 6, T - 14
In
R
T
vT
Proof. Suppose by contradiction that T - CT3/4 thus, it holds T T CT
We proceed upper and lower bounding the value of the Lagrangian. We first lower bound the quantity of interest employing the strategy mixture selection of Algorithm 3. Given that, holds:
E
[fe(z)]
A1l
E
[x)
[f(())] - Σ A1
E
[=(())][]]]
a-
a
a
[e[m)
t=1
xE(m)
0.
Differently, to upper bound the same quantity, we employ the no-regret property of the dual algorithm R.D. Hence, it holds:
E [f((z)]
Σ
Ao
E
[c]]
E+
kE/m)
ST
A [i]
[c(()][1]]
E
1=1 [m]
2T
A[i]
B
E
[co(z)][]]
+
R
X x
B,"
(6a)
1=1 sE/m]
t=1 ic(m]
2T RD
+
Σ Aiil
B
(1)
[c](
+
smmm
Ail- (1-
1
+ 27
B(
E
[c(( (il]
R
T1/4
a~
P
1= sE/ml
1/4
+ 27 RºD
=T
B((e)
E [c<(xx)]7{]]
(6b)
T1/4
TT T1/4
B(())
c((x))197)
+
3/3/4
In
T
2T :
R
(6c)
T1/4
p
T1/4
1
8/3/4
T
2T
ST
Tp Tp-Tp+1)
+
V
In
RD
(6d)
P
T1/4
P
p
1//4
3/3/4
T
2T
=
-T+
In
RD
P
P
1/4
873/4
T
2T
<T
3/4
T
In
R.
(6e)
P
P
P
T1/4
873/4
T
2T
3/73/4
In
DD
P
0
29

---

where Inequality (6a) holds by the no-regret property of the dual regret minimizer R Equation (6b) holds selecting À s.t. {[i*] / and A i = 0 for all other i E [m=]. where i" is the depleted resource notice that, there must exists a depleted resource since - 7 > 0 Inequality (6c) holds with probability at least 1 employing the Azuma-Höeffding inequality, Incquality (6d) holds since the following holds for the resource i* E [m]:
Σ cllm))i+12B--
and finally Inequality (6e) holds since T CT
Setting C 2
14 p In _
we reach the contradiction. This concludes the proof.
We conclude the section by proving the final dynamic regret bound of Algorithm 3.
Theorem 5.2. For any ō E (0, Algorithm 3, when instantiated with a dual regret minimizer which attains regret upper bound R.P, guarantees, with probability at least 35, Re S
14
(
in
T
RD
T
47 8 +
/2T
I 2T R
P
VT
P
Proof. We first employ Lemma B.3 to get the following bound, with probability at least 1 - d:
4T's
T
2T
Σ E [+(=)) 2 D (T ())-- -T 4 + x~E.
2T ln
R
Thus, we employ the Azuma-Höefiding inequality to get, with probability at least 26 by Union Bound:
4T
T
2T
T 8
f((a)) OPTp - (T -T) T) 4+
V
2r
In
RD
4
2T In
which in turn implies, with probability at least - 28:
4T's
T
2T
T 8
Ri S (T -) +
4
V
2T
In σ
+
R +
4
2r In
p
We then apply Lemma 5.1 to obtain, with probability at least 1 regret upper bound:
3d, by Union Bound, the following
Ry
14 p
In
T
D T
T
4+
- p
4T's 2n
2
In
T 2T Rº + 4
27 In
T g
VT
To get the final regret bound notice the following trivial upper bounds:
T S
T 8
R <
RP,
2r In 8 2
This concludes the proof.
B.2.1 Robustness to Baselines Deviating from the Spending Plan
We provide the regret of Algorithm with respect to a baseline which deviates from the spending plan.
Theorem 5.4. For any 5 E (0, 1), Algorithm 3, when instantiated with dual regret minimizer
which altains a regret upper bound RT. guarantees, with probability at least 1 - 36, Ry((e)) S
14
(v
In
no
T +
8
/ 2T 22
2T
RD
T ΣT Eie(m) (1)
vT
30

---

Proof. Similarly to Lemma B.3, we first employ Lemma B.2 and the definition of p:
Σ E w~
[1(x))]
2
E @ergit)
[f((2t]]
Σ
A [i]
Be
E am(i))
[ea ((x)))11]
xm1
scmm]
2T R.P.
Ali]
B
[c
[z((2))(]]
m-
E
&E m
Hence, we select the Lagrange variable as vector to get the following bound:
E [f(())] S:
[((())]
Σ
B
(c (c(()))1))
27
R.P
1=1
sE/m]
We now focus on bounding the following term when a baseline deviating from the spending plan is employed:
E angett
[f((z)]
- Σ A. B,""
E wne
Ice(2)) [=x(())
(E(m)
We notice that by the definition of Program (3), there exists a sequence strategy mixture {E/ [4:)%1 such that Ex~e; (x)] S B (() for all E [T], [m] and Σ Ee [f(())] 2 OPT -% for all y > O. In the rest of the proof, we will omit the the dependence on 7, since can be chosen arbitrarily small, thus being negligible in the regret bound.
We then define the following strategy mixture & for all E [T] as follows:
w.p. 1/T2/4
w.p. - 1/22/41
Thus, we first show that & satisfies the per-round expected constraints defined by B,a up to the errors terms. Indeed it holds, for all E [m]:
1
B
E [x)( a
B
E angg
E [[x(x)]
71/4
71/L a~e"
B
[()(2))
E
[xx
T1/4
T1/4
T1/4 a-ez
Bi (i)
1
EE [x)(
T1/4
T1/4
T1/4
where we employed the definition of E and ~² Thus, returning to the quantity of interest and selecting (g())T = (E.) M... it holds:
E
[f(())]
Σ Aoll-- B
E x(()())
[e((z))(i]
((e)
sE/m]
E. [f((x)]
+ Σ
Arli] - (
[ce(x)]([]]
x
$c xc(m)
Σ
E [f((z)] + Σ A B
(x)
4+
47T/1
2r 8
T
x~
*E[m]
31

---

E
[
/1/4
(1)
V 2 (1+
(4+ 1
T
P
p
8
t=1
1=1 ic(ml
Σ
(1-
1
E
[[((a)]]
71/4
(4)
71/4
T2/4
w
1=1 iE [m
4/
T
4
2r In
8
1
T1/4
4T 4
E
[f((x)]
2T In
T1/4
1=1 smmml
T1/4
(a+ 4T
T
E #~
[(((z)]
-T3/4
2r
sc/m]
T1/4
2 - (++ 4TT/1)
(444))) 12 8"
T
-PTpp()) - 33/4 (T -)-
ΣΣ El
P
vm|m
where the second inequality holds, with probability at least 1 - 8, by Lemma E.2 and upper bounding
the Lagrangian multiplier with T+ /p. Employing the same analysis of Theorem 5.2 and noticing that:
Σ t= [E
(8)
concludes the proof.
C Omitted Proofs for OLRC with Full Feedback
In this section, we provide the results and the omitted proofs for the OLRC with full feedback setting.
C.1 Theoretical Guarantees of Algorithm 2
We start by providing a lower bound to the expected rewards attained by Algorithm 2.
Lemma C.1. Algorithm when instantiated in the full feedback setting with primal regret minimizer which attains regret upper bound Ry and a dual regret minimizer which attains regret upper bound Ro for all E (T), guarantees the following bound:
Σ E S
[(((=))
2
sup EEE
E x-
[[(())] +
Σ <E(m)
Aeli]
[B
E ane
la(
Σ Σ B
Ice (z)) w~L.
RP
(1+
2 Punin
R.P
Pinin
(=1 [E[ml
where X E L is an arbitrary Lagrange multiplier and T is the stopping time of the algorithm.
Proof. In the following proof, we will refer to the stopping time of Algorithm 2 as т. Notice that there are two possible stopping criterion for Algorithm 2: (i) the budget is depleted before reaching
T. that is, at time T. (ii) the algorithm stops the end of the learning horizon, namely, T.
We first employ the no-regret property of the primal regret minimizer P. Given that, it holds:
sup
E m
[f((x]] - Σ Arli]
E (x)([]]
EEE
sE(m)
m
< (1+ 2
[f((x)]
Σ A [c(]]]ii]]
RP, (7)
a
Pmnin
mm|m]
32

---

where the (1 + 2/ Pmin) factor is the dependence on the payoff's range given as feedback to the primal regret minimizer.
Thus, we can rearrange Equation (7) to obtain the following lower bound the expected reward attained by Algorithm 2:
Σ E a
[f(())] 2 sup $E=
Σ
E [f(())]
Σ iE[m]
E
[ox(2)
20
[c(x)][1]] - (1+ 2
E w
(8)
Pmin
t=1 1E|m)
Thus, we make similar reasoning for the dual regret minimizer. Specifically, we have, for any Lagrange multiplier À E C the following bound:
ΣΣ
A
B
E x~
[e(())ii])
ΣΣ kE(m)
Aill
[
E x
[=((2)1i]]
R
Pmin
1=1 im(m]
which in turn implies:
ΣΣ
E wnde.
[c)()x)(11] z
[=1 (E(m)
ΣΣ>M B(a)
ΣΣ
[
E
[ca())[ii]
2 R2 Pmin
(9)
4E/m]
3E|m]
where the 2/pmin factor follows from the bound on the payoff's range of the dual regret minimizer. We then substitute Equation (9) in Equation (8) obtain:
E [((())]
2 sup EE=
E x-
[f(()))
+
Σ
(B(0)
E
[a(())(]]]
anE
iE(m)
ΣΣ t=1 (m(m]
B
E 2
(x)())
2 Pmin
R
(1 (1+
2 Pmin
This concludes the proof.
Thus, we refine the lower bound to the expected rewards by means of the following lemma.
Lemma 4.1. For any d E (0, 1), Algorithu 2 instantiated in the full feedback setting with primal regret minimizer which attains a regret upper bound Re and dual regret minimizer which attains a regret upper bound RP, guarantees the following bound, with probability at least - 5:
EiEEE [f(())] OPT - (T 7) -)- (4+ maxxec [||1I)) 22 - E Ali]-
- Ica (x)
RD 1 Puin
R.,, where X L is arbitrary Lagrange
Puin
multiplier and T is the stopping time of the algorithm.
Proof. We first employ Lemma C. obtain:
E [f((w)] E
2 sup
[f(())] +
Σ Aelie
(B(0
E we
[c((x)))1)
EE
(e(m)
Σ
B
E
[x)(
2 R² (1
2
R.P
x~gi
Puni
Puin
1= m
33

---

To conclude the proof, we focus on bounding the term:
sup EEE
[f(()]]+
+ Ex1 (B())
la (c)()))1)] m-e
:c(m]
First we define E as the set which encompasses all safe strategy mixtures during the learning dynamic. Specifically, we let = == (5 E (exe(((()) I BB" Vi E [m]. [7]] Now, notice that by definition of Problem (2), there exists strategy 8" E such that Σ Exng- [f(())] > OPTH 7, for all 7 > O. In the rest of the paper, we omit the factor 7, since it can be chosen arbitrarily small, thus being a negligible factor in the regret bound. Moreover, since the strategy belongs to E", thus, it satisfies the budget constraints imposed by the spending plan, we additionally have:
ΣΣ A= [m(m
Arl
B
[a(())((1] 2 0. x~
E
Thus, we can conclude that:
sup EEE
E
[f((z)] + Σx10 A.11..
BB())
E
(2)1))))1]
8c/m]
E [f((z)]
+ Σ
Xx B
E x~
[cx(x))(i)
xnde
[=1
E [f((z)]
+ Σ
Aolil
BB(0
- E
[=o()))81]
- -(4+4men
max
AEc |Alls) 2
[= m-
mm
vE(m)
[[((z)]] - -4
| 1 2T
T
max DEL
2 OPTH - -T- (4+
T
max XEE
|||ll 27 In
where the second inequality holds with probability at least 1 - by Lemma E.2. Noticing that by the update of Algorithm 2, it holds:
T
E m=
[f(())] Σ x~Ei
E [f((z)),
concludes the proof.
We are now ready to prove the final regret bound.
Theorem 4.2. For any (0, 1), Algorithm 2, when instantiated in the full feedback setting with primal regret minimizer which attains a regret upper bound R2 and dual regret minimizer which attains a regret upper bound RP,, guarantees, with probability at least 25, the following regret
bound R < 1
RD + (1+ Pmin
22) R
8
Panin 2 3-
Pmin
Pentn
Proof. We employ Lemma 4.1 to recover the following bound, which holds with probability at least
1 8:
Σ E [f(x:)) > OPT - (T- -)-) - 4 + 4 max S~
|1||
v 2T In
T
XEC
ΣΣ XiI
B
E
[c2(
2 Puii
1+
2
R.P
x~ei
Puin
1= mlim
34

---

Thus, we apply Lemma E. to obtain:
OPTH (T- (1 (1+ 4 max
T
Σ f(x)))
(2/11) V In
dEL
ΣΣ AlI -c(=))1))))))
2 R2
I1
2 14-21
RC - - (4+44)
2r In g
T
Pmin
Pmin
(=1 [e[m
which holds with probability at least probability, the following regret bound:
28 by Union Bound, form which we have, with same
Rr S (T -
Σ iE(mi
Ali]
(B(") ca(a))(l)
2 Pmin
R
2 Re +
T 8
+ 1+
8 + 8 max
[|
2 In
Punin
AEL
We finally focus on bounding the term Σi= Eie(m) A|i]
(B(') ce(ars)li))
We split the analysis
in two cases: (i) T T and (ii) < T.
Bound for case (i). When T, we select the Lagrange multiplier À the zero vector 0 to get the following regret bound:
RT S 2 2R
R2
+
1
2 Punin
R + (8+ 8 max
V 2n In T g. (2|l1)
Punin which holds with probability at least 1 25.
AEL
Bound for case (i.). In such a scenario, the budget has been depleted before the spending plans suggestions. Hence, the following holds for a resource E [m]:
Σ (x:))() +1 B
B
Thus, we can conclude that:
Σ> Σ
Alil (B.") (x,
Σ
Bi(²)
(2x,)1))
(10)
Pinin
Am mm(m)
B(6")
B((
1
Puin
Pmin
B((e)
1
+
Puni t=7+1
Pmin
1
Punin
(T
1)
+
Pmin
Pmiin
(T 1) +
Pmin
where Equation (10) holds selecting À s.t. A[i*] = 1 and Ald] = 0 for all others E [m]. Thus, substituting the result in the regret bound, we obtain:
Panin
Ri Pmin
2 R
2
R. (8+ 8 max (1111)
2 In 8*
T
Puin
Pwin
which holds with probability at least 1 - 25.
To get the final regret bound we notice the following trivial upper bounds:
R R RC S Rf. (8+ max |All)) This concludes the proof.
T 2r In
S (8+
(8+
2T T
XEC
Punin
35

---

C.1.1 Robustness to Baselines Deviating from the Spending Plan
In this section, we first provide the definition of the fixed baseline which deviates from the spending plan. Specifically, we first define the fixed optimal solution parametrized given the errors 6 specified for all t E [2], [m], by means of the following optimization problem:
Σ [1(())
suPEE= s.t.
O H (4) =
E [x)x[[ S B
+ E ( [ie Vt [T]
(11)
Σt= Beoe (x) B Vi [m]
Problem (11) computes the expected value attained by the optimal fixed strategy mixture that satisfies the spending plans each round 1 (T), up error terms et (6) > 0, defined for all i E [m]] and t E [T]. Similarly to the dynamic baseline, we do not make any assumption on the error terms c Nonetheless, the performance of our algorithms will smoothly degrade with the magnitude of these erros. Moreover, the errors must allow Problem (I1) to be feasible. We remark that the last group of constraints in Problem (11) ensures that the error terms do not allow the optimal solution violate
the general budget constraint. Observe that when c 0 for all i E [m] and t E meaning that the spending plan is strictly followed by the optimal solution-thh general budget constraint is satisfied by the definition of the spending plan.
Similarly, we define the following notion of cumulative static regret (+) = (PT
E fe( which simply compares the rewards attained by the algorithm with respect to the optimal fixed solution which follows the spending plans recommendations up to the errors.
We provide the regret of Algorithm 2 with respect to a baseline which deviates from the spending plan.
Theorem C.2. For any d E (0, 1), Algorithm when instantiated in the full feedback setting with primal regret minimizer which attains a regret upper bound R2 and a dual regret minimizer which attains a regret upper bound RP, guarantees, with probability at least - 25, the following regret bound:
Ro(()) 11+ 1
2
Rp +
(1 1+
2
Ref
8
8
22
T 8
Σ Puin t= ic(m)
Puin
Pinin
Pmin
Punin
Proof. Similarly to Lemma 4.1, we employ Lemma C.I to obtain:
E
[f(())]
2 sup EE= t=1
E xne
[f(()))
+
Σ x
B
E ane
lc((2)(11)
lc
E
vE[mi
Σ Σ
Alil
B
[ca())((1]
R2
1
2
R.f.
Pmii
Pmin
1=1 [m(m]
We now bound the term:
sup EEE
[f((z)]
Σ Aelil (B(0
E [c [cc(o0111) m-
KE[m)
which is done taking into account the possible error. First we define E" as the set which encompasses all safe strategy mixtures during the learning dynamic. Specifically, we let = {E E E (x)) & B,dh & Vi E [m]. E [T]]. Now, notice that by definition Problem (11), there exists a strategy 8* E such that Σt= Ex-ee- [f(()) (PTx(E)) 7, for all y 0. In the rest of the paper, we omit the factor 7, since it can be chosen arbitrarily small, thus being a negligible
factor in the regret bound. Moreover, since the strategy belongs to =", thus, it satisfies the budget constraints imposed by the spending plan, up to the error term, we additionally have:
Σ
Acll)
(B(a)
[e((x)((]]] 2
x-
Pmin t=1 [m[m]
1=1 [m(m)
36

---

Thus, we can conclude that:
sup EEE
E æ
[[((a)]]
+
Σ
BB(0)
E 2~~
lce
(2)())
iE|m]
E [f(()))]
Σ
A
B
E x-~
[c((2))11]
m m-
iE|ml
13
[fi(t)]
Σ A
B
18 a-ee
[3c(20)00]]
(4
max AEL
|
2
T
x-
ie(m)
-(1 4
(4+ max AEL
E a
[f((z))]
2 In |211a
Prain 1=1 im/ml
2 (P)H(() - -
ΣΣ Pmii t=1 AE(m]
(3) 4 4
max AEC |1
/ 27 8
where the second inequality holds with probability at least 5 by Lemma E.2. Thus, notice that by the update of Algorithm 2, holds:
T - Σ
Σ 1=1
E
[f(())]
E [f((x]]
1=1 w
The final result follows from the same analysis of Theorem 4.2, after noticing that:
Σ t= [E
t=1 EE mm]
This concludes the proof.
C.2
Theoretical Guarantees of Algorithm 4
In this section, we present the results attained by the meta procedure provided in Algorithm 4.
C.2.1 Algorithm
We first provide the algorithm for the full feedback case.
Algorithm 4 Meta-algorithm for arbitrarily small Pmin full feedback
Require: Horizon T, budget B, spending plans B for all i E [m], primal regret minimizer R. ( feedback), dual regret minimizer RD (full feedback)
1: Define = p==p/TT4
2: Define B.") D (1-T~V/) Vt E [T] [m]
3: Run Algorithm 2 for full feedback with Punin +- p, B(. t- -B
C.2.2 Analysis
In this section, we provide the analysis of Algorithm 4. We start by lower bounding the expected rewards attained by the meta procedure.
Lemma C.3. Algorithm 4, when instantiated with a primal regret minimizer which attains a regret upper bound Rf and a dual regret minimizer which attains a regret upper bound R2, guarantees the following bound:
E [f(())] > sup Φ
+ [f((x)]+
Σ A1l
B
[c(()))0]]
EEB
kE(m
2
37

---

Σ
B
E
[c((
2
R2
(1+ 2 R.
t= 1m/m
where À E C is an arbitrary Lagrange multiplier and T is the stopping time of the algorithm.
Proof. The proof is analogous to the one of Lemma C.I after substituting Pmin with ý and Bi") with B," for all i [m], t E (T].
We refine the previous lower bound as follows.
Lemma C.A. For any E (0, 1), Algorithmm 4, when instantiated with a primal regret minimizer which attains regret upper bound Ry and a dual regret minimizer which attains regret upper bound RP, guarantees the following bound, with probability at least - 6:
4T's
T
2T R
2T's
Σ E [f(())] 2 1=1 g:
4
2T
In
1---
1
R,,
6
P
where is the stopping time of the algorithm.
Proof. We first employ Lemma C.3 to obtain:
Σ E E
[f(()))]
2 sup
Σ
E m~6
[f(())]
+
Σ
Acll).
(
E la(x)1i1)
EEE 1=1
sE[m]
2T
2
ΣΣ
B
E w
(x))
1
P
[=1 sE|m]
Thus we select the Lagrange variable
0 vector to establish the following bound:
E
[f(())]
2
sup EE
E ane
[f(())]
+
Σ
Aelil
B
E a
[c(())
E
(=1
KE m
27
2T
Rd
1
R..
We now focus on bounding the term:
sup EEE
[[(x)]] Σ x~6
Aeli]
B
E a~3
rE(m)
Similarly to Lemma 4. we define E as the set which encompasses all safe strategy mixtures during the learning dynamic. Specifically, we let =- {E E E: Ex-<(c((x) s B(") Vi [m], e [T]} Now, notice that by definition of Problem (2), there exists a strategy e* E E such that Exrg [xx) OPT 7 for all 0. In the rest of the paper, omit the factor % since it can be chosen arbitrarily small, thus being a negligible factor in the regret bound. We then define the following strategy mixture Ço as follows:
c f=
w.p. 1/T1/4
g
w.p. 1 1/71/4
Thus, we first show that 5o satisfies the per-round expected constraints defined by B Indeed holds, for all i E [m]:
[x][ = B(O)-
(1
1
1
B
(1- T1/4
[e((x)]
E
[0((x)]
ame-
T1/4
-11- T1/4 Bid))
1
1
[t)())]
1
E
[x)]
T1/4
m
T1
x
38

---

1 0
T Bi
1
-
-11
1
[c(z)]
T1/a m~
where we employed the definition of f- and g².
Thus, returning to the quantity of interest, it holds:
sup 5e
E
[f(())]
+
Σ Aulll-
E are
(=)x
RE[m]
[f(()]]
+ Σ
B!!)
E
[x)(]]]
a~5²
x~
=c(m)
[f(())] + Σ
A
()) B
E [o((0)111]
- 4 -
V
2T In
T
a
P
ic(m)
[F(aar]] - -(++ 4+ -
T
EE serugo
V 2r
In
8
472//1
T
T-/4
E ange
[F((w]] + TILI aneo
E
[F((co]]
-
4
2r
P
4T2/1)
T
E zoni"
[[((ar]]
- (1+
2T
In
T'//4
5
-73/4 (++ 4T1/4)
T
[f((z)]
V
12T
In g
P
OPT 7/4 (T 7)) - 472/4
T 8
12 In
P
where the second inequality holds, with probability at least 1 8, by Lemma E.2 and upper bounding the Lagrangian multiplier with T Tå/p. This concludes the proof.
Hence, we proceed upper bounding the difference between the horizon T and the stopping time т. This is done by means of the following lemma.
Lemma C.5. For any 5 (0, 1), Algorithm 4, when instantiated with a primal regret minimizer which attains a regret upper bound Ry and a dual regret minimizer which attains a regret upper bound RP, guarantees the following bound with probability at least 1-60 8:
14 T-TS
T In
R2. +
R$ VT
T
P
6
Proof. Suppose by contradiction that T - r > CT334 thus, it holds 7 < - CT3//
We proceed upper and lower bounding the value of the Lagrangian given as feedback to the primal regret minimizer. Thus, we employ the no-regret property of the primal regret minimizer RP. Given that, it holds:
E g.
[f((x)]
Σ Acli] IE mee.
[=]l]]
[m(m)
-(1+ 271/1
[f((z)] - Σ A E [c]())[[]] -
R.
m=e
p
t=1
[m(m]
39

---

(-(1+
2T///)
R.,
where we already substituted the value of p.
To upper bound the same quantity, we follow the same analysis of Lemma 5.1. Hence, it holds:
E
[f(()]]
A
E
[c]())]
km(m]
T
E 2~
[=)
mm]
2T
S +
Ali
B
E
[c](
+
R
Σ
A
B
(12a)
E:
1=1 mm/
t=1 EE [m|m]
2T RD
Alil-
B
E
[x]())
mm(m)
+
Σ Alil (11- -1--///
((1-Zz7a)
T2/4
B(a))
E
[c(())[i]]
+
2T
R
mm
P
1=1 mm/ma
1/4
27
=
Ti/á
B(
E
[c(())((+1]
+
RD
(12b)
P
mm
ST + 1/4
1
1
[ - cc(2x1117))
+
87
T
2T
R
(12c)
P
0
P
ST + 1//
(1-
873/4
2T 7
Tp- - 1D-T++1)
In
R5
(12d)
71/4
P
+ + T2/4
8/3/4
T +
2T
T
In
R
P
T1/4
873/4
T
2T
< T - 3/
T
V
In
+
R
(12c)
8
P
P
P
T 3/4
T
2T
CT33//4
In
+
RPD
where Inequality (12a) holds by the no-regret property of the dual regret minimizer RD, Equa- tion (12b) holds selecting À s.t. A[F*] /2/ /o and A|i] 0 for all other i E [m]. where i* is the depleted resource notice that, there must exists a depleted resource since T - > 0-, Inequality (12c) holds with probability at least 1-6 employing the Azuma-Höeffdine inequality, Inequality (12d) holds since the following holds for the resource i" [m]:
Σ +12 B Tp.
and finally Inequality (12e) holds since T - CT3/4
Setting C 2 14 P ( In Rf+RR VT
we reach the contradiction. This concludes the proof.
We are now ready to prove the final regret bound of Algorithm 4.
Theorem C.6. For any å E 1), Algorithm 4, when instantiated with primal regret minimizer which attains a regret upper bound Rf, and a dual regret minimizer which attains a regret upper bound Rp. guarantees, with probability at least 1 - 36, the following regret bound:
R <
14 T
n
R. + RD
T
4T 8
2T
T
2T
RD
+
1
2T
R
p
VT
P
5
40

---

Proof.
We first employ Lemma C.4 to get the following bound, with probability at least 1 - 8:
E [f(())] 2 OPTx (T -))- - 4
4T (* ( P
T
27 R - - 27 R.
2r
In
5
P
P
Thus, we employ the Azuma-Höefiding inequality to get, with probability at least 1 28 by Union Bound:
4T's
T
Je(ar)) 2 OPTH - (T - T) -7 -
4+
V
2T In
x
P
2T R 1+
2T
T
RCf - 11
2r In
P
P
which in turn implies, with probability at least 1 - 20:
( 4+
4T
T 2T
2T
T 8"
RT S (T-))++
V 2n
In
+
R + 1 +
R.f +
27 27
8
P
P
P
We then apply Lemma C.5 to obtain, with probability at least 1 - 36, by Union Bound, the following regret upper bound:
14 S
T
RT
+
RD
T T++T++ + 4+ 47
T
RT
In
+
2r In
VT
2
(1+ 2T
T
RD +
Rº + 4v
2r
To get the final regret bound we notice the following trivial upper bounds:
T S 2 ln 8 1 2m In
T
R S RP.
R < Rp
8
This concludes the proof.
C.2.3 Robustness to Baselines Deviating from the Spending Plan
We provide the regret of Algorithm 4 with respect to a bascline which deviates from the spending plan.
Theorem C.7. For any ô E (0, 1). Algorithm 4, when instantiated with primal regret minimizer which attains a regret upper bound Ry and a dual regret minimizer which attains regret upper bound R7. guarantees, with probability at least 1 - 36, the following regret bound:
14 RT(()) S
T
R +
RD VT
4
T
V
Vin
T
T
T
+
8
2T
P
P
T
2T
2T
(4)
RC
(1
Rf.
P
[m(m]
Proof. Similarly to Lemma C.4, we first employ Lemma C.3 and the definition of p::
E [((()))
2 sup
E. x~6
[f((
+
Σ
xeli).
B
(
E [ca(w)\(1)
EEE 1=1
xE(m)
x~
27
2
ΣΣ Ali] N
B
E
[c](
R2
1
R.C
p
p
#liemm)
41

---

Thus we select the Lagrange variable as X = 0 vector to establish the following bound:
Σ E E
[f(xa]]
2 sup
E a~~
[[(
+
Σ
Aolil
B
E a
la (((())
EE=
iE mm)
2T'
2T
R
1
R².
We now focus on bounding the following term when the baseline deviates from the spending plan:
sup SEE
[e(x)]]+ +
x Σx0 [
E lca (coc mng
cc(m)
We define Ex as the set which encompasses safe strategy mixtures during the learning dynamic. Specifically, we let = == {E E =: (m=e((((=]] & B ,,",, Vi E [m]]. E [7]}. Now, notice that by definition of Problem (11), there exists strategy e* E = such that Σi= Exng- [f(( > (c.) 7 for all 0. In the rest of the paper, we omit the factor since it can be chosen arbitrarily small, thus being a negligible factor in the regret bound. We then define the following strategy mixture 8 follows:
5= x E
w.p. 1/1"/1
5
w.p. 1/T2/4
Thus, we first show that 6 satisfies the per-round expected constraints defined by B, Indeed it holds, for all i [m]:
1
1
B
E [x)]] 2~
B,
E
[xx]
E a
[c)())]
T1/4
a~
T1/4
1
1
1
1
BiS))
1
E
[x(()]]
E [x))
T1/4
T1/4
mm
T1/4
1
1
B
(i)
1
E
[<)))
T1/4
T1/
x~
1
(
T1/4
where we employed the definition of Er and g Thus, returning to the quantity of interest, it holds:
sup Ee
E m
[f(())]
+ PE(m)
E Aoli-
B E a
[cc(z)((0]
M
E [f(())]] + Σ
Acli] ((0))
E [x]
=c(m)
- 4 4T1/1)
T
[f((z)]
+ Σ A
B
EE w
(e.(00)(111
27 In 8
tE(m]
IE x
[F((
1/4
(t) (4+
4T
V
2T In
T
P
xc(m)
P
(1- T
E
[[((x)]
+
E.
[[((r]]
1
TI/I
anEa
P
1=1 (E(m)
42

---

4 44
T
2T
In
6
(1-
T
E
[[((r)]]
114
(4 44
4T
2r
In
T
ande
1=1 1E/m]
[((())
-33/4
T1/4
(8)
4+
4T1/4)
12
T
P
P
tE/m]
T
- (1+4-(++771)
4T1/4)
T
OPTN(() - 73/4 -T)
V
2T
In
P
P
8'
where the second inequality holds, with probability at least - 8, by Lemma E.2 and upper bounding the Lagrangian multiplier with 2 /p. Following the same analysis of Theorem C.6 and noticing that:
Σ t= kc(m)
t= [m
concludes the proof.
D Omitted Proofs for OLRC with Bandit Feedback
In this section, we provide the results and the omitted proofs for OLRC with bandit feedback.
D.1 Theoretical Guarantees of Algorithm 2
Similarly to the full feedback case, we start by providing a lower bound to the expected rewards attained by Algorithm 2.
Lemma D.1. Algorithm 2, when instantiated in the bandit feedback setting with a primal regret minimizer (with bandit feedback) which attains regret upper bound R with probability at least 1- Sp, and a dual regret minimizer which attains regret upper bound RP, guarantees the following bound:
Σ f((z)) 2
f((x)= - Σ Aeli] (B() -ce(z)l1))
sup TEX 1=1
(E(m]
Alil (B()- cca(z))(())
2 Pmin
R
(1
1+
2 Pmin
R
sc(m)
which holds with probability least 8p, where L is an arbitrary Lagrange multiplier and
is stopping time of the algorithu.
Proof. Similarly the proof of Lemma C.I, will refer the stopping time of Algorithm 2 as т. We employ the no-regret property the primal regret minimizer R.P. which works with bandit feedback. Given that, holds, with probability least 6p:
Σn Ex1l (B! - (z))))
sup x
f((x)) +
iE [m)
[((x))) Σ Aal (xx)(1)
<(1
2
R2.
(13)
Puii
7Elm)
where the (1 + P/iin) factor the dependence on the payoffs range given as feedback the primal regret minimizer.
43

---

Thus we can rearrange Equation (13) to obtain the following bound:
((()))) 2 sup
f((x)) + Σ Ax11] (B. (z)))))))
:E/ml
_
A a (x,)(
1+
R
(14)
Pmin
t=1 ic[m]
which holds with probability at least 1 8p. Given the dual regret minimizer, it holds, for any Lagrange multiplier À E L:
ΣΣ>M
x (B. (2x)))))
Σ
Σ
A[i]
(B())
cx(2)))))) = R.P
Pmin
(=1 mm
1=1 ic(m)
which in turn implies:
Σ - 2
Σ
Σ [m(m
B
Σ
Σ ie(m]
Aiil (B -c(()()))))0))
2 Pmin
R&.
ic/m)
(15)
where the 2/Pmin factor follows from the dual payoffs range. We substitute Equation (15) in Equation (14) to obtain, with probability at least 1 6p:
Σ f(())) 2 sup DEX
f((x) + E Aid (B - (
xE/mm
Σ iE(m)
\ii (B(0) (a)))(l))
2 Pmin
Re
1+
2 Pmin
R.
This concludes the proof.
We refine the previous lower bound. This done by means of the following lemma.
Lemma D.2. For any ô E (0,1), Algorithm 2, when instantiated in the bandit feedback setting with primal regret minimizer (with bandit feedback) which attains regret upper bound Rý, with probability at least - ōp, and a dual regret minimizer which attains a regret upper bound Re. guarantees the following bound:
Σ f((x,) 2 OPTH - -T-
EE - 44 4max [1a111)
/ 27
T
Pmin
dEL
1=1 1c(m)
ΣΣ iE|m]
(B(0 - (=)))))
2
RD.
(1
2
Rf.
Puin
Pinin
which holds with probability at least 1 (6 8p), where A E L is an arbitrary Lagrange multiplier and T is stopping time of the algoritlum.
Proof. We employ Lemma D.I to obtain:
f((z) + Σ Aolec (D.² c(<=)11)))
(xx sup xER t=1
A - -
R2 - [+
2
R..
Pmin
Pmin
t=1 [[(mm
To conclude the proof, we focus on bounding term:
sup
f((x)+ +
Σ AMll (B!²- 180--clos -c((=)1)))
1
ME E.
[E(m]
44

---

Specifically, notice that by definition of the probability mixture E, it holds:
[x(x) + Σ A (B.²) -c(())11)
sup
EE(m]
sup EE=
[f(())]]
Aolil
(B(")
E x=~
[ct(2=)(0]]
x~
rE(m
Thus, employing the same analysis of Lemma 4.1 concludes the proof.
We are ready to prove the final result on the regret bound of Algorithm 2 for bandit feedback.
Theorem D.3. For any 8 (0, 1), Algorithm 2, when instantiated in the bandit feedback setting with primal regret minimizer (with bandit feedback) which attains, with probability at least 8p. regret upper bound Ry and dual regret minimizer which attains regret upper bound R.. guarantees, with probability at least 1 (8 + 8p), the following regret bound:
2
2 Pmiin
4
T
PT <
11
R2
1
Rh
4
12T
2T
In
Pmin
Pinin
Pinin
8
Proof. The analysis is equivalent to the one of Theorem 4.2, once applied Lemma D.2 and after noticing the employment of Lemma E.1 is not necessary.
D.1.1 Robustness to Baselines Deviating from the Spending Plan
We provide the regret of Algorithm 2 with respect to a baseline which deviates from the spending plan.
Theorem D.4. For any 5 (0, 1), Algorithm 2, when instantiated in the bandit feedback setting with primal regret minimizer (with bandit feedback) which attains, with probability at least 8p. regret upper bound Ry and dual regret minimizer which attains regret upper bound R.T. guarantees, with probability at least (8 + 8p), the following regret bound:
T
Rr 11+
Rp
1+
2
Rf +
44+
4
V
2T
5 +
Σ
Puiin
Pmin
Pmin
Pmin
Puin t=1 xE[ml
Proof. We employ Lemma D.I to obtain:
Σ [e((xt) 2 sup xEX 1m]
[xx)))
+
Σ Ax(i] (B() cc((x)(li)
E [m]
Σ b (B()) (2()))66)
2 R2P
(1+
2
R.P
Pmin
Pmin
vE[m)
The proof follows from noticing that:
sup 2
f((x)
Σ A (D -c(
xE|m]
(B(()
sup EEB
E [[(())]
Σ
E are
[cr [ca(ar)
(c(m)
and employing the same analysis of Theorem C.2.
D.2 Theoretical Guarantees of Algorithm 5
In this section, we present the results attained by the meta procedure provided in Algorithm 5.
45

---

D.2.1 Algorithm
We first provide the algorithm for the bandit feedback case.
Algorithm 5 Meta-algorithm for arbitrarily small Pmin and bandit feedback
Require: Horizon T, budget B, spending plans B/6 for all i E [m]) primal regret minimizer R ( feedback), dual regret minimizer RD (full feedback)
1: Define -== P/T
2: Define B, B (1-T~V+) WI E [T) [m]
3: Run Algorithm 2 for bandit feedback with Puiin + p, B t- B
D.2.2 Analysis
In this section, provide the analysis of Algorithm 5. We start by lower bounding the expected rewards attained by the meta procedure.
Lemma D.5. Algorithm 5, when instantiated with primal regret mininizer (with bandit feedback)
which attains a regret upper bound Rf., with probability at least - 8p, and a dual regret minimizer which attains a regret upper bound Rp, guarantees the following bound:
Σ [((x)) 2 1=1
sup mEX
f(())) +
Σ Aelil B c((2)(11) sE[m]
Aill (B," c((z))ii))
RD 2)) P
- R.
which holds with probability least 8p, where X L an arbitrary Lagrange multiplier and is stopping time of the algorithm.
Proof. The proof is analogous to the one of Lemma D.1 after substituting Pmin with and B with B for all i E [m], [T].
We refine the previous lower bound as follows.
Lemma D.6. For any (0, 1), Algorithm 5, when instantiated with primal regret minimizer (with bandit feedback) which attains a regret upper bound Rf, with probability at least 1 8p and dual regret minimizer which attains regret upper bound R guarantees the following bound, with probability at least - (8 8p):
Σ f((z1) 2 OPT (T - - t=1
4+
47's P
)
2
2T In
T
2T
R
27 P
R.
8
p
where is the stopping time of the algorithm.
Proof. We first employ Lemma D.5 and the definition of f to obtain, with probability at least 8p:
Σ (xx))) 2 sup
fe(x)) +
Ax[i]
Bi( - c=(=))11)
xeX
rE(m)
Aii
(
a (x))
27
RD
(1 |+
27
R.P.
1e[m]
Thus we select the Lagrange variable as 0 vector to establish the following bound:
27
27
Σ f(())) 2 sup xEX
f((x)+ + Σ
B - c2(2)11)
R_D
1 +
R..
:E|m
46

---

which holds with probability at least 1 - 8p. We now focus on bounding the term:
sup 2EA
Selar)
Σ
A (B)- - -ca(cc)))))))
<E[m)
This is done equivalently to Lemma C.4 once noticed that, by definition of the strategy mixture space, it holds:
sup œEA
f((x)+
Σ
A
BB
iE/m]
sup
Σ EE t=1
E
[f(())] + Σ
A
E x~e
[c)(
ie(m!
This concludes the proof.
L
Hence, we proceed upper bounding the difference between the horizon T and the stopping time т, when only bandit feedback is available. This is done by means of the following lemma.
Lemma D.7. For any (0, 1), Algorithm 5, when instantiated with primal regret minimizer (with bandit feedback) which attains a regret upper bound R.. with probability at least 8p and a dual regret minimizer which attains a regret upper bound Rpp. guarantees the following bound:
14
R
RD T
T-TS
P
VT
which holds with probability at least 1 Spp.
Proof. We proceed similarly to Lemma C.5 and we suppose by contradiction that T CT3/1 thus, holds T CT3/4
We proceed upper and lower bounding the value of the Lagrangian given as feedback to the primal regret minimizer. Thus, we employ the no-regret property of the primal regret minimizer R.. Given that, it holds, with probability at least 1 - 8p:
f((x)) - Σ
Ael cx(x))
E=1
iE m)
-(1+ 2T-1/4
>
Σ
fe(x0) Σ
Acli] ci )[]
-
R
t=1
<E(m)
1/1
R.P
where already substituted the value of P.
Similarly, to upper bound the same quantity, we proceed as follows:
fe(x))
Σ xE[m]
Xeli] (2x)
Σ
Σ
x (x++0
t=1 ic(m)
2T +
< T
Σ
Σ
A|i (T - -00
Rp
A
BB.
(16a)
P
[1
1= [E(m)
47

---

2T R,
| (B8 ca(ar:)(1))
ST+
P
[=1 rE(m)
Σ {|i|
(1-
1
B,o0 cxxx)))1))
2T Rop
T1/4
P
fE(m
T1/4
1
1
Bl()) -c ca(
27 Rop
(16b)
T1/4
P [ml
P
1/4
((1-7//
((1-
1
2T
S T
-p-18
Sp-Tp+11
R
(16c)
T1/4
T1/4
27's R
=T
T
P
P
714
21
<T C/4
+
T
RD
(16d)
T1/1
2T
-CT3//1
+
R
P
where Inequality (16a) holds by the no-regret property of the dual regret minimizer RD, Equa- tion (16b) holds selecting À s.t. {[i*] T* and A 0 for all other i E [m]. where i" the depleted resource notice that, there must exists a depleted resource since T T > 0 -, Incquality (16c) holds since the following holds for the resource i [m]]
Σ
1-122=Tp Tp.
and finally Inequality (16d) holds since T - CT3/4 Setting C 2 14. R R
we reach the contradiction. This concludes the proof.
p VT
We are now ready prove the final regret bound of Algorithm 5.
Theorem D.8. For any 8 E (0, 1), Algorithm 5, when instantiated with primal regret minimizer (with bandit feedback) which attains regret upper bound Rf, with probability at least 1 8p, and dual regret minimizer which attains regret upper bound R2, guarantees, with probability least 1 - (5 + 8r), the following regret bound:
Rr <
14 R + RD T
+ +
4+
47's (++))) p
27 In
T 8
2T
RT
+
1
2T
Re.
VT
P
Proof. The analysis equivalent to the one Theorem C.6, once applied Lemma D.6 and Lemma D.7 and after noticing the employment of the Azuma- inequality is not necessary.
L
D.2.3 Robustness Baselines Deviating from the Spending Plan
We provide the regret of Algorithm with respect to a baseline which deviates from the spending plan.
Theorem D.9. For any 8 E (0, 1), Algorithm 5, when instantiated with primal regret minimizer (with bandit feedbackk which attains regret upper bound RÝ. with probability at least 8r, and a dual regret minimizer which attains regret upper bound RV. guarantees, with probability at least 1 (8 + 6p), the following regret bound:
14
Rf + RD
4
T 5
RT(E:) <
T
+
4+
2T 2T'
VT
T
T
2T
27
RP +
Rf.
p
1=1
[E|m]
48

---

Proof. We follow the proof of Lemma D.6 to obtain:
21
(
27
Σ (a()))) 2 sup nEX
Se(x)) + Σ x (D.²- -90--cafe -ca()))i))
R2
Rej
*E|m]
P
which holds with probability at least 8p. To get the final bound we proceed as in Theorem C.7 noticed that, by definition of the strategy mixture space, it holds:
f((x) + Σ x (B," 1 -c((0011)
mE
.E(m]
]
(D
sup EE=
18 mue
[f(()]]+
Σ
Aclil
E
lc
VE
and employing Lemma D.7 after noticing that the employment of the Azuma-Höeflding inequality is not necessary. This concludes the proof.
E Technical Lemmas
In this section, we present some concentration results which are necessary to prove the regret bounds of the algorithms we propose.
Lemma E.1. For any å E (0, 1) and far all t [T]. with probability at least - 8, it holds:
Σ
(xr
Σ /E(m)
(x
(x,
Σ
E [f()
A
E
(x)]]]]
m
3E(mJ
s (4 + (||1)
21
Proof. The proof follows from the fact that the quantity of interest is Martingale difference sequence where the per-step difference is bounded by (2 + 21) Thus, employ the Azuma-Höeffddig inequality with a Union Bound on the rounds to conclude the proof.
Lemma E.2. For any d E (0, 1). far all t for any sequence of strategy mixtures { for any sequence of Lagrange multipliers {>r Ytm it holds, with probability at least 6:
and
Σ
E [x)]
Σ (E(m)
[ E [c, [x)][b] ar
(4+ max |AlI)) XEL
T o 2
E wngt
[f+())]]
E (x)]]]] anig.
xE[m]
Proof. The proof follows from the fact that the quantity of interest is Martingale difference sequence where the per-step difference is bounded by max (2 + 2|[ Thus, we employ the Azuma- Höeffding inequality with Union Bound on the rounds to conclude the proof.
49


Reviews:
[{"review_id": "Wrrm1JiQip", "reviewer": "Reviewer_yQdM", "summary": "The paper studies the problems of online resource allocation (where rewards and costs are observed before action selection) and the online learning with resource constraints (where rewards and costs they are observed after action selection, under full feedback or bandit feedback). While it is known that a sublinear regret isn't achievable by any spending plan in these setting, the current paper considers the easier, but still realistic, setting where a budget plan is given to the algorithm. The paper provides algorithms with sublinear regret bounds in this case.", "questions": "Please elaborate on how to reduce the bandit setting to the full information setting.", "limitations": "The authors did not explicitly discuss the limitations of their work in the main body.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper tackles a practically relevant problem in ML.\n- The algorithms presented are intuitive and simple. \n- The paper is very well-written and easy to follow. \n\nWeaknesses: \n- Having access to a good budget plan is not always possible, and so the methods proposed may have a narrow scope. \n- The paper does not provide any experimental validation. \n- There are a couple of places where the paper would have benefited from more detailed explanations (see my comments below).\n\nComments: \n- After Theorem 4.2, it would have been helpful to elaborate a little more on how the bandit setting can be reduced to the full-information setting. \n- Same comment for Section 5.1 (lines 352-358); more explanation on how to deal with small rho would have been very helpful. \n- $\\rho$ in Algorithm 3 (and in Section 5.1 in general) is not defined/scoped.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the positive evaluation of our work.\n\n> Having access to a good budget plan is not always possible, and so the methods proposed may have a narrow scope.\n\nWe agree with the Reviewer that having access to a good spending plan is not always possible. Nonetheless, spending plans are used in practice, and thus it is of interest to develop a theoretical understanding of how they should be used. We believe that our work of providing theoretical guarantees (for both ORA and OLRC) while assuming a good spending plan is a fundamental and necessary step towards an understanding of the real-world problem of how to learn with a spending plan. Second, our baseline follows the spending plan in expectation only. This is important because it means that our setup can be combined with spending-plan estimation algorithms that then feed those estimates to our algorithms. Finally, in Section 5.2, we show how our algorithms are robust to baselines that do not follow the spending plan, thus improving their applicability in practice.\n\n> After Theorem 4.2, it would have been helpful to elaborate a little more on how the bandit setting can be reduced to the full-information setting.\n\nWe thank the Reviewer for the comment. We did our best to give as many insights as possible about our algorithms, but due to space constraints, we had to prioritize some settings over others.\n\nWe better highlight the relation between full and bandit feedback in the following. Notice that our primal-dual algorithm exploits the no-regret guarantees of the primal and the dual regret minimizer. Thus, if a bandit regret minimizer yields guarantees similar to those for OLRC with full feedback, our analysis for the bandit feedback follows immediately from the full feedback one. \nThe main difference lies in the fact that, in general, the guarantees provided by primal regret minimizers under bandit feedback differ from those obtained with full feedback. This is because the Lagrangian observed as feedback is different, which can, in principle, lead to different optima. Nonetheless, we can employ the fact that, by definition of the strategy mixture space $\\Xi$, it holds that $\\sup_ {\\boldsymbol{\\xi}\\in\\Xi} \\sum_{t=1}^\\tau r_t^P = \\sup_ {\\boldsymbol{x}\\in\\mathcal{X}} \\sum_{t=1}^\\tau r_t^P$, where $r_t^P$ is the (Lagrangian) loss built for the full feedback setting. Specifically, the optimal solution defined over the \"full-feedback\" Lagrangian is a pure strategy; thus, the optimal solution for the \"full-feedback\" Lagrangian and the \"bandit\" one are equivalent (see lines 321-322). Consequently, the regret guarantees of the primal bandit feedback regret minimizer are comparable to the full feedback one, up to the fact that, in the bandit feedback, the regret bound holds with high probability.\n    \nPlease let us know if further discussion is necessary.\n    \nWe commit to enlarging the explanation on this part in the final version of the paper.\n\n> Same comment for Section 5.1 (lines 352-358); more explanation on how to deal with small rho would have been very helpful.\n\nSimilarly to the previous answer, we commit to enlarging the explanation on this part in the final version of the paper.\n\nFrom a technical perspective, the key problem for handling small $\\rho_{\\min}$ is that the Lagrangian space must be instantiated so that the Lagrangian may reach a value of $1/\\rho_{\\min}$ to compensate budget violation. Thus, the primal regret bound (a similar reasoning holds for the dual, too), which scales linearly in the payoff range, would be of order $1/\\rho_{\\min}\\sqrt{T}$, which can be linear for small $\\rho_{\\min}$. In order to get a sublinear result, we cap the Lagrangian to $T^{1/4}/\\rho$, attaining a regret of order $T^{3/4}$, since $\\rho$ is constant by definition. Nonetheless, capping the Lagrangian to $T^{1/4}/\\rho$ is not sufficient to \"satisfy\" the budget constraints, that is, to allow the budget violation to compensate large rewards in the Lagrangian function. Thus, we rescale the spending plan with the same quantity, in order to be slightly pessimistic in the budget constraints part of the Lagrangian and, subsequently, to allow a Lagrangian of order $T^{1/4}/\\rho$ to be large enough to satisfy the new pessimistic constraint.\n\nPlease let us know if further discussion is necessary.\n\n> $\\rho$ in Algorithm 3 (and in Section 5.1 in general) is not defined/scoped.\n\nWe thank the Reviewer for pointing out this aspect. The parameter $\\rho$ is defined in the preliminaries at line 101. Specifically, $\\rho$ is the ratio between the overall budget $B$ and the horizon $T$, which is constant by definition since $B=\\Omega(T)$. Nonetheless, we agree with the Reviewer that, for the sake of clarity, the definition of $\\rho$ can be remarked in the final section. We commit to doing it in the final version of the paper."}, {"review_id": "wH9QmYNNdI", "reviewer": "Reviewer_VN8t", "summary": "The paper proposes a framework for online decision-making with resource constraints, focusing on adversarial environments where standard regret benchmarks are unachievable. The key contribution is the introduction of a spending plan benchmark: a user-specified resource consumption profile that serves as a feasible benchmark for regret analysis. The authors design primal-dual algorithms, applicable to both full and bandit feedback settings, that achieve sublinear regret relative to this spending plan. The analysis includes a meta-algorithm to handle small minimum budget values and provides robustness guarantees for small deviations from the spending plan. The work aims to unify online resource allocation and online learning with resource constraints under a common regret framework.", "questions": "1) In the ORA setting, since the reward and cost functions are fully known before action selection, the \"regret\" essentially measures the loss of the proposed dynamic optimization heuristic relative to a feasible baseline spending plan. There is no learning of unknown quantities involved. Could the authors clarify this point and distinguish their notion of regret from standard regret in learning settings?\n\n2) The authors claim in Remark 2.2 that sublinear regret is impossible in all settings without a spending plan. However, in the stochastic setting, standard benchmarks are achievable with sublinear regret. The authors may wish to clarify this distinction.", "limitations": "The paper lacks a discussion on limitations and potential negative societal impacts.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1) The paper introduces a general framework for online decision-making under resource constraints that applies to both adversarial and stochastic settings, including bandit and full-information feedback. \n\n2) The spending plan concept provides a structured and feasible baseline in adversarial environments, allowing the authors to derive regret guarantees that are meaningful when competing with a pre-specified resource usage profile.\n\n3) The algorithmic design is modular, leveraging black-box regret minimizers in the primal updates and providing adaptability across different feedback structures.\n\nWeaknesses:\n\n1) The paper’s novelty lies primarily in the design of the spending plan benchmark and its associated regret analysis, rather than in new algorithmic techniques.\n\n2) The choice of spending plan is external and assumed given, yet the regret guarantee depends heavily on this plan’s quality. The paper does not discuss how to design or learn a good spending plan or analyze sensitivity to suboptimal plans.\n\n3) The regret notion in the ORA setting does not reflect classical learning. Since the algorithm operates with full feedback before action selection, there is no learning of unknown reward or cost functions. The regret measure essentially tracks the loss of a dynamic optimization heuristic relative to the spending plan, rather than regret in the traditional online learning sense.", "was_revised": true, "final_justification": "Authors clarified key points, I increased my score to borderline accept.", "rebuttal": "We thank the Reviewer for the effort in evaluating our work.\n\n> The paper’s novelty lies primarily in the design of the spending plan benchmark and its associated regret analysis, rather than in new algorithmic techniques.\n\nWe agree with the Reviewer that the novelty of our work does not primarily lie in the primal-dual template. However, we highlight that this is a common feature of many works on both ORA and OLRC (e.g., [1], [2], [3]). The main contribution in this literature, as well as in our work, lies in the analysis and in the small--but fundamental--changes that are necessary in order to achieve various properties of the general primal-dual template.\n    \nFurthermore, while Algorithm 3 acts as a wrapper for the primal-dual template, it is, to the best of our knowledge, a novel technique in the literature. We believe this contribution is algorithmically valuable as well.\n\n> The choice of spending plan is external and assumed given, yet the regret guarantee depends heavily on this plan’s quality. The paper does not discuss how to design or learn a good spending plan or analyze sensitivity to suboptimal plans.\n\nWe believe that providing theoretical guarantees (for both ORA and OLRC) while assuming a good spending plan is given as input is a fundamental and valuable step towards the complete understanding of the learning with spending plan framework. We strongly believe that future works can build on our results in order to design meaningful spending plans. Indeed, our baseline follows the spending plan in expectation only. This is important because it means that our setup can be combined with spending-plan estimation algorithms that then feed those estimates to our algorithms.   \n\n    \nFinally, on the statement that we do not analyze sensitivity to suboptimal spending plans, this is not correct. In Section 5.2, we show how our algorithms are robust to baselines that do not follow the spending plan exactly. Notice that by relaxing the baseline in this way, we are actually showing results exactly for the case where the spending plan is not accurate: if you follow the predicted spending plan, but it is not accurate, then there will be some sequence of relaxation parameters $\\epsilon_t$ such that the optimal spending rates are captured by that relaxed plan. Thus, our results in Section 5.2 actually show that our approach degrades gracefully with the amount of inaccuracy in the spending plan: you incur regret linear in the amount of error. Looking at the paper, we did not add enough explanation of the equivalence between these two things. In the final version of the paper we will make this much clearer.\n\n> The regret notion in the ORA setting does not reflect classical learning. Since the algorithm operates with full feedback before action selection, there is no learning of unknown reward or cost functions. The regret measure essentially tracks the loss of a dynamic optimization heuristic relative to the spending plan, rather than regret in the traditional online learning sense. In the ORA setting, since the reward and cost functions are fully known before action selection, the \"regret\" essentially measures the loss of the proposed dynamic optimization heuristic relative to a feasible baseline spending plan. There is no learning of unknown quantities involved. Could the authors clarify this point and distinguish their notion of regret from standard regret in learning settings?\n\nWe respectfully disagree with the Reviewer on this point. The Reviewer may be conflating \"classical learning\" and the online resource allocation literature. Our (dynamic) regret notion in the ORA setting is standard for the ORA literature (see e.g., [1,2,4,5,6]). Notice that, even though rewards and costs are fully revealed before action selection, there is still learning involved. What is being learned is the appropriate way to bid in order to expend the budget at the correct rate. The reason this must be learned is that the requests (i.e., the reward and cost functions) are sampled from some underlying distributions (in the stochastic setting), or generated arbitrarily (in the adversarial setting). In either case, the online aspect arises because the algorithm must learn how to act in a way such that the budget expenditure is smoothed out in a reasonable way. All of this occurs because the resource constraint means that these decisions are connected across rounds, and thus affect each other.\n\nWe will surely include this discussion in the final version of the paper.\n\n> The authors claim in Remark 2.2 that sublinear regret is impossible in all settings without a spending plan. However, in the stochastic setting, standard benchmarks are achievable with sublinear regret. The authors may wish to clarify this distinction.\n\nWe would like to clarify the quote from Remark 2.2, which says:\n\n\"It is well known that when no spending plan is available, it is impossible to achieve sublinear regret bounds in all the settings presented in this work ...\"\n\nThis quote is correct. The Reviewer's comment only applies to the classical stochastic setting where the **same** distribution is used at every time step, which is not a setting presented in our paper. In the final version of the paper, we will more clearly specify \"unlike the setting with a fixed distribution that does not vary with time\".\n    \nIn more detail, in our work, the rewards and costs are sampled at each episode from adversarially changing distributions. Thus, our setting is more general than the standard adversarial one---where the rewards and costs change over time but the true function is observed---and the lower bounds from the adversarial setting still hold in our case. In ORA with adversarial rewards and costs, sublinear dynamic regret is provably impossible (see [4]). A similar result extends to OLRC (with adversarial rewards and costs) for the static regret. \n\nWe hope to have addressed the Reviewer's concerns. Please let us know if further discussion is necessary.\n\n[1] \"Dual Mirror Descent for Online Allocation Problems\", Balseiro et al. (2020)\n\n[2] \"The best of many worlds: Dual mirror descent for online allocation problems\", Balseiro et al. (2023)\n\n[3] \"Adversarial Bandits with Knapsacks\", Immorlica et al. (2023)\n\n[4] \"Learning in repeated auctions with budgets: Regret minimization and equilibrium\", Balseiro et al. (2019)\n\n[5] \"Online Resource Allocation under Horizon Uncertainty\", Balseiro et al. (2023)\n\n[6] \"Robust budget pacing with a single sample.\", Balseiro et al. (2023)"}, {"review_id": "FS7iYUeJoA", "reviewer": "Reviewer_5sDf", "summary": "This paper studies the online decision-making problem under adversarial resource constraints. In this problem, a decision maker has a fixed budget for multiple resources. Requests arrive sequentially, and each request generates a reward and consumes resources based on a given allocation. Before the decision-making process, a spending plan, which specifies the spending budget for each step (or request), is provided to the decision maker. The goal of the algorithm is to minimize the regret with respect to a benchmark that follows the spending plan.\n\nThe paper considers two settings based on the timing of decisions:\n\n- Online resource allocation, where the algorithm observes the reward and resource consumption functions before making decisions.\n\n- Online learning with resource constraints, where the algorithm makes decisions first and then observes the reward and consumption functions (under full feedback or bandit feedback).\n\nThe authors develop online algorithms for both settings. In the online resource allocation setting, the algorithm achieves a dynamic regret of $\\tilde{O}(\\sqrt{T}/\\rho_{\\min})$. In the online learning with resource constraints setting, the algorithm achieves a static regret of $\\tilde{O}(\\sqrt{T}/\\rho_{\\min})$, where $\\rho_{\\min}$ is the minimum spending budget across all steps and resources.\n\nTo address scenarios where $\\rho_{\\min}$ is small, the paper proposes modifications by redefining $\\rho_{\\min}$ and the spending plan. These modifications yield regret bounds independent of $\\rho_{\\min}$, which is desirable when $\\rho_{\\min}$ is small. Additionally, the paper demonstrates robustness to sub-linear errors in the spending plan.", "questions": "- In the adversarial setting, a worst-case instance could involve that all resources are consumed in a single step, with no resource consumption in other steps. This corresponds to a spending plan where one step receives the entire budget and all others receive zero. Can the extended version of the algorithm handle this case? What happens if there are errors in the spending plan in such scenarios?\n\n- The regret bounds depend on $\\rho_{\\min}$, which is defined as the minimum budget across all steps and resources. Would it be possible to redefine $\\rho_{\\min}$ to exclude zero elements, using the minimum among all non-zero elements instead?\n\n- In practice, the full spending plan may not be available at the beginning of the decision process. Can the algorithm handle an online revelation of the spending plan? Moreover, the horizon $T$ is assumed to be known in advance, which is not always realistic. Can the algorithm be adapted for an unknown time horizon?\n\n- In the theorems in Section 5, the parameter $\\rho$ appears in many expressions, but I believe it should be $\\rho_{\\min}$. Could you clarify this?", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength\n- The paper addresses an important online decision-making problem with broad applications. The notion of a spending plan is a practical and reasonable addition, helping to overcome worst-case impossibility results.\n\n- The systematic algorithm design and analysis for both settings, online resource allocation and online learning with constraints, are nice.\n\n- The analysis of robustness to errors in the spending plan is a valuable and practical addition to the main results.\n\n\nWeakness\n\n\n- The algorithmic ideas are not entirely new. The online resource allocation algorithm closely resembles that of Santiago et al. (ICML 2020), with the main change being the use of a predefined spending plan instead of a uniform budget $B/T$. The online learning with constraints approach shares similarities with the bandits with knapsacks literature. The paper lacks a thorough comparison between its proposed algorithm and those existing approaches.\n\n- There are no lower bounds provided, making it unclear how tight the regret bounds are.", "was_revised": true, "final_justification": "The authors have answered my questions; however, my original concerns about the algorithmic novelty and lower bound are not fully resolved. So I will keep my positive rating, albeit with some reservations.", "rebuttal": "We thank the Reviewer for the positive evaluation of our work.\n\n> The algorithmic ideas are not entirely new. The online resource allocation algorithm closely resembles that of Santiago et al. (ICML 2020), with the main change being the use of a predefined spending plan instead of a uniform budget $B/T$. The online learning with constraints approach shares similarities with the bandits with knapsacks literature. The paper lacks a thorough comparison between its proposed algorithm and those existing approaches.\n\nWe agree with the Reviewer that the novelty of our work does not primarily lie in the primal-dual template. Nonetheless, we believe that this is a common feature of many works on both ORA and OLRC (see [1], [2], [3]), where the main contribution lies in the analysis, while the algorithms are subject to small---but fundamental---changes. Furthermore, notice that Algorithm 3 is indeed novel in the literature; thus, we believe that our work is valuable from an algorithmic perspective, too. \n\nWe commit to inserting a more comprehensive discussion in the final version of the paper.\n\n> There are no lower bounds provided, making it unclear how tight the regret bounds are.\n\nWe thank the Reviewer for the insightful comment. Assuming $1/\\rho_{\\min}$ is constant, we can easily state that our bounds for OLRC are provably tight in $T$. Indeed, even in the simpler multi-armed **unconstrained** case (where the decision space is a set of finite arms), a lower bound of the form $R_T=\\Omega(\\sqrt{T})$ holds (see, [4]). For ORA, the standard $\\Omega(\\sqrt{T})$ lower bound on the dynamic regret in the stochastic setting, which is presented in [1], still holds when a spending plan is given in input.\n\nAs concerns the $1/\\rho_{\\min}$ dependence in the regret bound, we believe that it is necessary when primal-dual methods are employed. Indeed, a dependency on the inverse of the Slater's parameter is standard for primal-dual algorithms for constrained online learning setting (see [5],[6], and many others). We leave as an interesting open problem to develop algorithms for both ORA and OLRC, which are not primal-dual. \n\nWe will surely include this discussion in the final version of the paper.\n\n> In the adversarial setting, a worst-case instance could involve that all resources are consumed in a single step, with no resource consumption in other steps. This corresponds to a spending plan where one step receives the entire budget and all others receive zero. Can the extended version of the algorithm handle this case? What happens if there are errors in the spending plan in such scenarios?\n\nWe thank the Reviewer for pointing out this aspect. As is standard in the literature, the costs (and the per-round spending plan) are assumed to be in $[0,1]$ and we are in the regime $B=\\Omega(T)$; thus, it is not possible that the entire budget is allocated in a single round. Technically, it is well known that it is impossible to learn in settings in which the budget can be depleted in a single round. Intuitively, this is related to learning problems with a constant number of rounds, in which regret algorithms are ineffective.\n\nPlease let us know if further discussion is necessary.\n\n> The regret bounds depend on $\\rho_{\\min}$, which is defined as the minimum budget across all steps and resources. Would it be possible to redefine $\\rho_{\\min}$ to exclude zero elements, using the minimum among all non-zero elements instead?\n\nWe thank the Reviewer for the interesting question. The answer is yes and we will explain this in the paper.\n\nIn general, some preprocessing steps can improve the empirical results. Removing zero elements is a good starting point that does not change the results. More generally, it is possible to remove all the elements below a given threshold. Specifically, when the number of rounds where $B_t^{(i)}$ is small is of order $\\mathcal{O}(\\sqrt{T})$, those rounds can be erased (playing the void action) and it is possible not to count the associated $B_t^{(i)}$ in the computation of $\\rho_{\\min}$, without changing the theoretical guarantees of the algorithm.\n\nPlease let us know if further discussion is necessary.\n\n> In practice, the full spending plan may not be available at the beginning of the decision process. Can the algorithm handle an online revelation of the spending plan? Moreover, the horizon $T$ is assumed to be known in advance, which is not always realistic. Can the algorithm be adapted for an unknown time horizon?\n\nWe thank the Reviewer for the interesting question. We believe that handling an online revelation of the spending plan and an unknown time horizon is indeed possible. For the unknown time horizon, it is sufficient to employ a primal and a dual regret minimizer that works with an adaptive time horizon (e.g., online gradient descent with adaptive learning rate for the dual). For the online revelation of the time horizon, we believe that a doubling trick approach could work. Specifically, the algorithm is instantiated with an estimate of $\\rho_{\\min}$, which we call $\\tilde{\\rho}$ (and is initialized to $1$). Every time the online spending plan reveals a new $B^{(i)}_t\\leq \\tilde \\rho/2$, we reset the algorithm with the new $\\tilde \\rho = B^{(i)}_t$ and the results still hold up to logarithmic terms.\n\nWe will include this discussion in the final version of the paper.\n\n> In the theorems in Section 5, the parameter $\\rho$ appears in many expressions, but I believe it should be $\\rho_{\\min}$. Could you clarify this?\n\nIn Section 5.1, we obtain regret bounds which are independent of $\\rho_{\\min}$. The quantity the Reviewer noticed is $\\rho=B/T$, which is constant by definition. Since this is one of the main contributions of our work, please let us know if further discussion on this point is necessary.\n\n[1] \"Dual Mirror Descent for Online Allocation Problems\", Balseiro et al. (2020)\n\n[2] \"The best of many worlds: Dual mirror descent for online allocation problems\", Balseiro et al. (2023)\n\n[3] \"Adversarial Bandits with Knapsacks\", Immorlica et al. (2023)\n\n[4] \"Bandit algorithms\", Lattimore and Szepesvári (2020)\n\n[5] \"Exploration-Exploitation in Constrained MDPs\", Efroni et al. (2020)\n\n[6] \"Truly No-Regret Learning in Constrained MDPs\", Müller et al. (2024)"}, {"review_id": "iiOnyJ4Zaw", "reviewer": "Reviewer_AGGq", "summary": "This work considers online resource allocation (ORA) and online learning with resource constraints (OLRC). To achieve sublinear regret in adversarial scenarios, the authors assume that a spending plan is provided to the learner at the outset. They then establish sublinear regret guarantees with respect to baselines that follow the spending plan in expectation.", "questions": "In lines 70–81, the authors compare their approach with [13,33]. Specifically, this work assumes that the spending plan is given at the beginning, whereas [13,33] construct the spending plan during the learning process. Which setting is more challenging? Intuitively, constructing the spending plan on the fly might be more natural.\n\nWhy do the baselines only satisfy the spending plan in expectation? Is this an inherent limitation of the proposed method?\n\nAlthough Remark 4.3 and Theorem D.3 illustrate some results for the bandit case, a corresponding formal theorem is not presented in the main paper. Could the authors clarify or include a formal theorem for the bandit setting?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nUsing the spending plan to construct baselines is the main novel contribution of this work and may have wide-ranging applications.\n\nThe paper addresses both the ORA and OLRC settings. For OLRC, the analysis covers both the full-information and bandit feedback scenarios. The results appear to be solid and rigorously derived.\n\nWeaknesses:\n\nThe work does not provide lower bounds, so it remains unclear whether the obtained results are optimal.\n\nThe readability of the paper could be enhanced; for example, adding proof sketches and technical challenges in the main text would help improve clarity.\n\nAdditionally, numerical experiments could further increase the work’s appeal by demonstrating its practical performance.", "was_revised": true, "final_justification": "After carefully reviewing the rebuttal, I have decided to increase my score by 1.", "rebuttal": "We thank the Reviewer for the positive evaluation of our work.\n\n> The work does not provide lower bounds, so it remains unclear whether the obtained results are optimal.\n\nWe thank the Reviewer for the interesting question. Assuming $1/\\rho_{\\min}$ is constant, we can easily state that our bounds for OLRC are provably tight in $T$. Indeed, even in the simpler multi-armed **unconstrained** case (where the decision space is a set of finite arms), a lower bound of the form $R_T=\\Omega(\\sqrt{T})$ holds (see, [1]). For ORA, the standard $\\Omega(\\sqrt{T})$ lower bound on the dynamic regret in the stochastic setting, which is presented in [2], still holds when a spending plan is given in input.\n\nAs concerns the $1/\\rho_{\\min}$ dependence in the regret bound, we believe that it is necessary when primal-dual methods are employed. Indeed, a dependency on the inverse of the Slater's parameter is standard for primal-dual algorithms for constrained online learning setting (see [3],[4], and many others). We leave as an interesting open problem the development of algorithms for both ORA and OLRC, which are not primal-dual.\n\nWe will include this discussion in the final version of the paper.\n\n> The readability of the paper could be enhanced; for example, adding proof sketches and technical challenges in the main text would help improve clarity.\n\nWe thank the Reviewer for the comment. We did our best to include as many insights as possible on the techniques and results within the main text. However, due to space constraints, some technical details had to be deferred to the appendix. We commit to incorporating additional details in the main body of the paper in the final version, using the extra page available.\n\n> In lines 70–81, the authors compare their approach with [13,33]. Specifically, this work assumes that the spending plan is given at the beginning, whereas [13,33] construct the spending plan during the learning process. Which setting is more challenging? Intuitively, constructing the spending plan on the fly might be more natural.\n\nWe thank the Reviewer for the interesting question.\n\nFirst, we would like to highlight that our paper is motivated by the fact that on several internet platforms, the spending plan is given to the budget-management algorithm (coming from some ML model). In that sense, it is useful to develop a set of algorithms that work directly with an arbitrary given spending plan.\n\nThat said, building the spending plan is more challenging than assuming to have one as input. But in order to handle that setting, [13] and [33] make assumptions that simplify their analysis, for example allowing them not to deal with the $1/\\rho_{\\min}$ dependence. Moreover, they deal with the ORA case only, while we study the OLRC and  bandit setting, too.\n\nTo conclude, we believe that providing theoretical guarantees (for both ORA and OLRC) while assuming a given spending plan is a fundamental step towards the complete understanding of the learning with spending plan framework, and also arguably the more realistic setup, given that in practice these spending plans will be derived from heuristic ML approaches.  Of course, we also believe that future work can build on our results in order to design meaningful algorithms for constructing spending plans that are optimized to work well with our primal-dual setup.\n\n> Why do the baselines only satisfy the spending plan in expectation? Is this an inherent limitation of the proposed method?\n\nWe believe that it is a point in favor of our work. The baseline that satisfies the spending plan in expectation is much stronger than the one that satisfies the plan deterministically. Intuitively, constraints in expectation are weaker than constraints that must hold deterministically. Similar results for simpler settings are provided for instance, in [19].\n\nAs further evidence, when comparing with a baseline that satisfies the constraints deterministically, the ORA problem becomes trivial, since it is possible to directly solve a LP problem at each round, finding the optimal per round solution. Instead, since only a sample of the rewards and costs function is observed and the baseline satisfies the spending plan in expectation, the algorithm has to dynamically adapt to the changing environment in order to attain sublinear regret, while satisfying the budget constraints.\n\nPlease let us know if further discussion on this point is necessary.\n\n> Although Remark 4.3 and Theorem D.3 illustrate some results for the bandit case, a corresponding formal theorem is not presented in the main paper. Could the authors clarify or include a formal theorem for the bandit setting?\n\nDue to space constraints, we have deferred the formal theorem in the Appendix (see Theorem D.3. and Theorem D.8.). We commit to inserting it in the main text in the final version of the paper, where we will be allowed to use an additional page.\n\n[1] \"Bandit algorithms\", Lattimore and Szepesvári (2020)\n\n[2] \"The best of many worlds: Dual mirror descent for online allocation problems\", Balseiro et al. (2023)\n\n[3] \"Exploration-Exploitation in Constrained MDPs\", Efroni et al. (2020)\n\n[4] \"Truly No-Regret Learning in Constrained MDPs\", Müller et al. (2024)"}]

Author rebuttal:

Meta-review: Overall, reviewers are positive about the paper. They think the paper studies a well-motivated and practically relevant problem, and the paper offers a nice framework to tackle the problem. 

The following two papers might be worth citing in "Related Work" section "Online Learning with Resource Constraints" paragraph (and  they might be solving special cases of the submission):

Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression.  Aleksandrs Slivkins, Xingyu Zhou, Karthik Abinav Sankararaman, Dylan J. Foster. COLT 2023, JMLR 2024.
Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence. Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. ITCS 2023.

In particular, the open problem (emphasized in conclusions) of the COLT 2023 paper might be quite related to this paper.
Decision: Accept (poster)