Contextual Decision-Making with Knapsacks Beyond the Worst Case
Authors: Zhaohua Chen
Rui Ai
Mingwei Yang
Yuqi Pan
Chang Wang
Xiaotie Deng
Venue: NeurIPS 2024 poster (2024)
Keywords: Contextual Decision-Making with Knapsacks
Re-Solving
Primary area: learning_theory

Abstract: We study the framework of a dynamic decision-making scenario with resource constraints.
In this framework, an agent, whose target is to maximize the total reward under the initial inventory, selects an action in each round upon observing a random request, leading to a reward and resource consumptions that are further associated with an unknown random external factor.
While previous research has already established an $\widetilde{O}(\sqrt{T})$ worst-case regret for this problem, this work offers two results that go beyond the worst-case perspective: one for the worst-case gap between benchmarks and another for logarithmic regret rates.
We first show that an $\Omega(\sqrt{T})$ distance between the commonly used fluid benchmark and the online optimum is unavoidable when the former has a degenerate optimal solution.
On the algorithmic side, we merge the re-solving heuristic with distribution estimation skills and propose an algorithm that achieves an $\widetilde{O}(1)$ regret as long as the fluid LP has a unique and non-degenerate solution.
Furthermore, we prove that our algorithm maintains a near-optimal $\widetilde{O}(\sqrt{T})$ regret even in the worst cases and extend these results to the setting where the request and external factor are continuous.
Regarding information structure, our regret results are obtained under two feedback models, respectively, where the algorithm accesses the external factor at the end of each round and at the end of a round only when a non-null action is executed.

Contextual Decision-Making with Knapsacks Beyond the Worst Case
Zhaohua Chen School of Computer Science
Rui Ai IDSS & LIDS
Peking University Haidian, Beijing, China
Massachusetts Institute of Technology Cambridge, MA 02139, USA ruiai @mi edu
chenzhaohua@pku.. edu. cn
Mingwei Yang
Yuqi Pan
Dept. of Management Science and Engineering
School of Engineering and Applied Sciences Harvard University
Stanford University
Stanford, CA 94305, USA
Cambridge, MA 02138, USA yuqipan0g. harvard edu
mxyang@stanffrd.com edu
Chang Wang Dept. of Computer Science Northwestern University Evanston, IL 60208, USA wc@u. northwesthwwerr.c.mmmm edu
Xiaotie Deng
School of Computer Science Institute for Artificial Intelligence
Peking University Haidian, Beijing, China xiaotielpku, edu,
Abstract
We study the framework of a dynamic decision-making scenario with resource constraints. In this framework, an agent, whose target is to maximize the total reward under the initial inventory, selects an action each round upon observing random request, leading to reward and resource consumptions that are further associated with an unknown random external factor. While previous research has already established an Õ(VT) worst-case regret for this problem, this work offers two results that go beyond the worst-case perspective: one for the worst-case gap between benchmarks and another for logarithmic regret rates. We first show that an (T) distance between the commonly used fluid benchmark and the online optimum is unavoidable when the former has degenerate optimal solution. On the algorithmic side, we merge the re-solving heuristic with distribution estimation skills and propose an algorithm that achieves an ((1) regret as long as the fluid LP has a unique and non-degene solution. Furthermore, we prove that our algo- rithm maintains a near-optimal Ō D(VT) regret even in the worst cases and extend these results the setting where the request and external factor are continuous. Regarding information structure, our regret results are obtained under two feedback models, respectively, where the algorithm accesses the external factor at the end of each round and at the end of a round only when a non-null action is executed.
Introduction
In online contextual decision decision-making problems with knapsack constraints (CDMK for short), an agent is required make sequential decisions over a finite time horizon maximize the accumulated
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

reward under initial resource constraints [14 15I. To be more specific, in each round = ....., request 9r and an external factor n are independently generated from two distributions, and only 02 is revealed to the agent. Based on the request, the agent should irrevocably choose an action de; which results in a reward r(0,, at, 7t)) and a consumption vector c(0:, (tt, 7tt) of resources. The agent's ss target is to optimize the sum of rewards Σí= r(0z, Gt, (t,7)) before the resources are depleted.
T,
The contextual decision-making with knapsacks problem presents two key challenges when compared to closely related problems (e.g., the network revenue management problem): (1) choices are made without observing the external factor, and (2) distributions of requests and external factors are unknown. However, the complexity of CDMK makes a suitable mathematical abstraction for many real-life scenarios, and there are extensive application scenarios with this kind of information structure. We use the following examples as illustrations and motivation.
Example 1.1 (Supply chain management). In supply chain management, a factory needs to allocate among T' repositories consecutively and is constrained by the total inventory. Given the request O, for each repository, the factory chooses the number of goods transported to it as action de. However, the factory has randomized transportation costs for different locations and traffic conditions denoted by an external factor "t for the f-th repository, which finally influences rewards. The factory needs to form an optimal scheme to allocate its goods under uncertainty to all these repositories.
Example 1.2 (Dynamic bidding in repeated auctions with budgets 9 [O]. In this circumstance, an advertiser acquires the value of the ad slot 0g at the start of each auction and chooses a bid ae accordingly. The agent's gain in this auction, as a consequence, is collaborativey determined by the value, the bid, and the highest competing bid 7/s and has form of 02 (a; > 7)). Additionally, the payment is a, (a, respectively. It is to be noted that the highest competing bid is inaccessible to the agent before committing to the bid, as all advertisers bid simultaneously. Meanwhile, its distribution is decided by other advertisers, which is also unknown to the agent before the auctions.
()t) for the first-price auction and (a, > (v)) for the second-pris auction,
The CDMK model can also capture other well-studied problems, including multi- online linear programming, online matching, etc., as discussed in Balseiro et al. (9. Previous studies of the CDMK problem have shown that the worst-case regret is Õ(VT) when the initial resources are linearly proportional to the horizon length T 36 24]. However, is still unclear whether we can achieve better regret guarantee for the CDMK problem beyond worst-case scenarios. In particular, can we design algorithms to obtain an of VT) regret only under mild assumptions that hold for almost all possible CDMK instances? Meanwhile, can these algorithms still obtain good regret guarantees even in the worst cases? At last, previous works would adopt specific benchmarks to measure the regret of algorithms, but how are these benchmarks close to the rewards that the optimal online algorithm can achieve? This work widely addresses these questions.
1.1 Our Contributions
This work makes three main contributions, summarized as follows.
The fluid optimum can be ((vT) away from the online optimum. Since the online optimum is hard to characterize, previous works always use an alternative benchmark to measure the performance of any online algorithm, and the fluid optimum (also known as the deterministic LP) is common choice [24 333. However, we demonstrate that when the fluid benchmark has a unique and degenerate solution, then an ((VT) gap is unavoidable between these two optima (ef. Theorem 2.1 While Han et al. (4 has also provided a similar lower bound result for the related contextual bandits with knapsacks (CBwK) problem, their condition depends on the inseparability of the possible expected reward/consumption function set. In other words, their condition may not perform well when this feasible set is small. Furthermore, their condition is rather complicated to verify. In contrast, our condition only depends on the underlying problem instance and is concise and easy to check. The proof of our result extends the approach of Vera and Banerjee [38 to the CDMK problem.
An Ō1)) regret via re-solving under mild assumptions with full/partial information feedback. Since an Ō ((VT) worst-case regret is already known (36], we investigate how well an online algorithm can perform beyond worst cases by applying the re-solving heuristic conjunction with distribution
estimation techniques, as given in Algorithm[] This method has been considered in the problems

---

Table I: A summary of our algorithmic results on Algorithm
Constants are omitted.
Beyond the Worst Case
Worst Case
Uniq., Non- Non-Degen. LP
Discrete
Continuous
Full-Info.
((1) O 7)
O OVTTlog T) ( + T TV/) V O(vTlog T) O + Vlog T + T (log T75/2--a))
Part.-Info.
u, u: the mass/density function of context and the external factor. (pe( (3 d)/(28 d) if p is d-dimension distribution and E E(3, L). (See Appendix A
of network revenue management (NRM) and bandits with knapsacks (BwK). (See Section 1.2 for a literature review.) However, to our knowledge, we are the first to extend this method to the CDMK problem, which poses new challenges as decisions should made according to the request. To avoid worst cases, we explicitly suppose that the fluid problem has unique and non-degenerate solution (cf. Assumption 3.1). This assumption is mild three aspects: (I) it captures almost all CDMK problem instances, as slightly perturbing any LP can help it satisfy the unique optimality and non-degeneracy conditions; (2) is less restrictive than the assumptions given in Sankararaman and Slivkins [32,, which require that there are at most two resources; and (3) it is almost necessary for an of (()T) regret bound to be established by Theorem 2.1 when using the fluid optimum the benchmark. Under the assumption, our main results show that the re-solving heuristic reaches an (11) regret with full information (cf. Theorem 3.1) and Olog T) regret with partial information (cf. Theorem 4.1). To our knowledge, these are the first Õ(1) regret results in the CDMK problem beyond the worst case with only mild assumptions. Importantly, unlike previous results, these regret bounds are also independent of the number of actions.
Within our results, the full information model assumes that the agent sees the external factor at the end of each round. In contrast, in the partial information model, the agent acquires the external factor only when a non-null action is adopted. In Example T.I if the factory can learn the road condition via map services, then observes the external factor no matter its chosen action, reflecting the full information feedback. However, it can sometimes only observe transportation costs when it transports goods, resembling a nol-null action. This is a case of partial information feedback. In the auction market illustrated in Example 1.2. agents might also face these two kinds of information models. In some situations, bidders can always view others' bids after the auction, while in other cases, only those who bid non-zero values can observe others' bids. Non-zero bidding here reflects non-null action. Therefore, these two information models hold strong practical significance.
Other state-of-the-art results consider bandit information feedback, in which the agent only sees the reward and the consumption rather than the external factor. However, they explicitly assume specific (e.g.. linear) relationship between the conditional expected
pair and the request [3] 32 24 36). whereas our results do not impose any underlying distribution structures, bypassing realizability issues [24]. On this side, our information model is comparable to those in existing work.
near-optimal regret even in worst cases with full/partial information feedback and an ex- tension to continuous randomness. We further explore how well our Algorithm (T performs even in worst-case scenarios. With full information feedback, we show that an O O(VT' log T') regret is achieved (cf. Theorem 5.11) This bound is asymptotically equal the ttate-of-the-ar with this infor- mation model 24 36 Even with partial information, can still guarantee universal O(VT log T') regret (cf. Theorem 5.2 which is optimal up to logarithmic factor. These results demonstrate the applicability and robustness of the re- heuristic in CDMK problems. regardless of some specific instances. For completeness, we extend our algorithm and analysis to the situation which the distributions of request and external factor continuous and derive corresponding regret results (cf. Theorems A. and A.2).
We summarize algorithmic results Algorithm D in Table

---

1.2 Related Work
Contextual decision- decision-making/Nn making/bandits with knapsacks. The issue most closely related to the CDMK problem is the problem of contextual bandits with knapsacks (CBwK), introduced by Agrawal and Devanur [3). The main difference between the CDMK problem and the CBwK problem is that in the latter, an explicit model of the external factor is missed, and the bandit information feedback is considered. That is, only the consumption and the reward revealed to the agent the end of a round rather than the external factor. Along this research line, two primary methodologies have been proposed to solve the problem. The first approach aims select the best probabilistic strategy within the policy set [8] and Agrawal al. adopts this approach achieve an O(VT) regret. This heuristic originates from the subject of contextual bandits 117 and requires cost-sensitive classification oracle to achieve computation efficiency.
On the other hand, another approach views the problem from the perspective of the Lagrangian dual space. It uses dual update method that reduces the CBwK problem to the online convex optimization (OCO) problem. In particular, some work 3 32 35 30] assumes a linear relationship between the conditional expectation of the reward-consumption pair and the request-action pair. This line adopts techniques for estimating linear function classes to achieve sub-linear regret.
18 and combines them with OCO methods
are not restricted to linear expectation functions. To deal with more general problems with bandit feedback, they plug medel-reliable online regression methods [2 21 into the dual update framework. As a result, their algorithms regret is the sum of the regret on online regression and online convex optimization, respectively. Nevertheless, the online regression technique still limits the conditionally expected sewardccnssmpiig functions.
Apart from the above studies, some results 24
36 37
In the CDMK literature, Liu and Grigas 330 have considered full information feedback, where the agent sees the external factor at the end of each round. Motivated by practice, our work further considers a partial feedback model, in which the agent observes the external factor when a non-null action is chosen (cf. Section 2
The re-solving heuristic and related problems. Unlike the above approaches, our work adopts the re-solving method, also known as the "certainty equivalence" (CE) heuristic. Under this approach, the agent (in) (in)frequently solves the fluid optimization problem with the remaining resources to obtain a probability control in each round. This method comes from the literature on the network revenue management (NRM) problem, which can be seen as a simplification of the CDMK problem without the existence of external factors or the external factor not getting involved in the resource consumption 42 Some researches in this setting also assumes known request distributions [26] 5 12 These works show that the re-solving-bert based method can obtain a constant regret under certain non-degeneracy assumptions and can generally obtain a square-rov regret [6]. Recently, the re-solving method is also extended to the general dynamic resource- constrained reward collection problem in Balseiro et al. (9. which assumes the knowledge of request and external factor distributions and achieves (1)) to O(log T) regret for different action space cardinalities.
25
19
13
We should mention that the re-solving technique. together with other methods, has also been adopted for the bandits with knapsacks (BwK) problem [3 20 42 39 29 32) to achieve an O(log T') regret under different assumptions. For example, an essential result by Sankararaman and Slivkins B2 achieves Olog 7) regret in BwK under the best-arm assumption and two resources. However, CDMK a more challenging problem than BwK in that the decision has to be based on the received request. Thus, no optimal static action mode is irrelevant to the round, which adds layer of complexity to the re-solving method.
2 Preliminaries
We consider an agent interacting with the environment for rounds. There are n kinds of resources, with an average amount of p' for resource in each round, resulting in total of p'T amount of resource i. We suppose that 0 < p = P1 = (p')xe(x) < 1 is independent of T, with maximum entry of max < 1 and minimum entry of min > 0.

---

At the beginning of each round t 2 1, the agent observes request 0, E θ drawn i.dd. from distribution U and should choose an action a; from a set of actions A. Given the request 0, and the action dz. the agent receives random reward E [0, 1] and consumption vector of resources C: E [0, 1)", both of which are related to an external factor 7t E r drawn i.i.d. from a distribution V. In other words, there is reward function r θ x A x T - [0, 1] and consumption vector function e ④ x x I + [0, 1]", such that r. = r(Or. Oe, 7t) and C₁ = c(O,, or.
dt.7t), 7t), We suppose
these two functions are pre-known to the agent. We further define Ri(0,)) a) E,(r(0, a, 7)]. and C(O, a) = [c(0, a, 7)].
We impose minimum restrictions on the distributions U/ and V. In the main body of this work, we only suppose that the support sets of both distributions are finite. Specifically, we let k |e] be the size of the request set. We denote the mass function of U and V by u(f) and v(7). respectively. We will extend to the situation that these two distributions can be continuous in Appendix [A]
The agent's objective is to maximize the cumulative rewards over the period under initial resource constraints, which is a sequential decision- makinn problem. To ensure feasibility, we assume the existence of a null action (denoted by 0) in the action set A. Under the null action, the reward and the consumption of any resource are zero, regardless of the request and the external factor. In other words, we have r(0,, 0, 77) = 0 and c(0,, 76) = 0 for any (0,, (0,,74) denote the of non-null actions and let m = |A+ be its size.
) E θ x r. We use A+ = A {0} to
We would like to discuss here the necessity of the null action, which is widely used in related works 8 4 36 An alternative common choice for the null action is the so-called "early stop when resource exhausted" (32) in the BwK problem with no contexts. In reality, when the agent faces some "bad" contexts, better choice is not "entering the market" avoid, for example, small rewards but large consumption. As a comparison, struggling to come with a non-null action here could occupy the space for serving those "good" contexts, and stopping before these contexts arrive may inevitably cause an Q(T)) regret. This illustrates that introducing a null action is necessary in the CDMK problem. In fact, in this problem, contexts play the role of revealing information and deterring unreasonable deals.
We consider the set of non-an non-anticipatinn strategies II. In particular, let He be the history the agent could access at the start of round f. Then, for any non-anticipating strategy π E TI, de should depend only (0,, Ha), that is, 0g am (0., H4). For abbreviation, write a. oz (0e, He) when there is no confusion.
Therefore, we can define the agent's optimization problem as below:
OON max EQ-iE N-OT
Σ r(0,, aF ne)
s.t. Σ c(lr, ot 7) PT, 40 O², ,E.".
The fluid benchmark. practice, however, computing the expected reward of the optimal online strategy would require solving a high-dimension (probably infinite) dynamic programming, which is intractable. Hence, we turn to consider the fluid benchmark to measure the performance of a strategy, which is defined as follows:
FL = T
max ++
Egwul
Σ DEA
a)0,a)
s.t. Ea-u
Σ C(0, ((0,a)
Sp: Σ
(0, S 1, E (0, 2.000.))0
For a better understanding. FLL reflects the maximum expected total rewards an agent can win when a static strategy is adopted and the resource constraints only be satisfied in expectation. Therefore, this optimization problem is a linear program in which the decision variable @00, a) represents the probability that the agent chooses action a upon seeing request 0. is well-known result that FFL gives an upper bound on VON
Proposition 2.1 (Balseiro et al. FL VON
Thus, we evaluate the performance of non-anticipating strategy æ by comparing its expected accumulated reward Rew with the fluid benchmark VLL, which is common choice in literature [35]
5

---

24 However, we prove that such benchmark choice may lead to a ( gap as long as V is degenerate.
Theorem 2.1 (Worst-case gap). When VFL has unique and degenerate optimal solution, VFL VON ((VT)).
Despite the worst-case lower bound, we prove in this work that for any CDMK instance in which VEL has a unique non-degenerate optimal solution (cf. Assumption 3.1 we can obtain an ((1) gap compared to the fluid benchmark. Thus, it is still good choice in most cases.
Information feedback model. In this work, we consider two types of information feedback models, with increasing difficulty obtaining sample of the external factor y.
[Full information feedback.] The agent is able to observe "/. at the end of each round L.
PPartial information feedback.] The agent can observe "/r the end of round L only if az A O.
In general, with full information feedback, the agent can observe an i.i.d. sample from V each round, which is the optimal scenario for learning the distribution. Nevertheless, such an assumption could be strong since the reward and consumption vector are irrelevant to the external factor when the agent chooses the null action 0. Thereby, more realistic information model is the partial feedback one, where the external factor is only accessible when a * 0. This limitation also increases the difficulty of learning the distribution V since the agent observes fewer samples under this model than under full information feedback. It is important to note that the partial information model represents a transition from full to bandit information feedback, under which only the reward and consumption vector are accessible in each round, rather than the external factor. Real-life instances of partial information feedback include Examples and 1.2 as we have discussed in the introduction.
3 The Re-Solving Heuristic
In this work, we introduce the re-solving heuristic to the CDMK problem. The resulting algorithm is presented in Algorithm !
To briefly describe the algorithm, we start by defining an optimization problem that captures the optimal fluid control for each round, assuming complete knowledge of U and V. For any x. E [0, 1]", we define J (K) as the following optimization problem:
J(k) = max
BEnet
Σ aEA+
R(O, a))(0,a)
$.0xA1 -2
s.t. Ee-ee
Σ C(e,a)o(8,a) aee+
K; Σ
a(B,a) $ (0,,0) 0, =0x
aEA+
Evidently, we have FFL = ((p) TT - by definition. Intuitively, in each round t, the best fluid choice of the agent is given by the optimal solution o; oP (p:)). where P. is the average budget of the remaining rounds, including round t. Nevertheless, since full knowledge of the exact distributions U and is lacking, the agent can only solve estimated programming J(p,, He) as outlined in Algorithm with the following realization:
J(p., = max E
Σ E BAn (10,,,,))) 6(0, LeE
6.0xAt to smile
s.t. Ba,
Σ +
Eg. (c(0, a (10
Pp: Σ a( 1 (00 2,000 000
REAt
Here, Eh and 9) represent the empirical distribution 0 and 7, respectively, according to sample history given by H.. Specifically, let Z, be the set of rounds that the agent accesses the external factor. The mass functions of these two estimated distributions are standard as follows: (0) = # appears previous (-1 roundal/t-1; 2e(r)) == #ly appears in rounds in Zel//z.)

---

Algorithm 1 Re-Solving with Empirical Estimation.
Input: p. T.
Initialization: I1 + 6. B1 + pT.
fort 1 to T do
Observe 8;; P: -
1 f the solution to [pt. He);
Choose as E A randomly such that for a E Pr/a a] = (0c. a), and Pr(o, =0] =0]
A+ (6,, a):
if (FULL-INFO) V (PARTIAL-INFO A.e + 0) then
Observe Yt:
I++1 t I (()):
else
I++1 c- Iti
end if'
B++1 + B: - ce:
if Bi < 1 for some E [n] then
break;
end if end for
is worth noting that the estimated distribution of 0, Uh. is always based on t -- samples since the agent received an independent sample from U at the beginning of each round. On the other hand, the empirical distribution of the external factor 7, V. estimated from [Ic] independent samples. With full information feedback, [Z, = I. - 1; whereas with partial information feedback, [Zel S 1 equals the number of times the agent chooses an action a * 0 before round For brevity, for the estimated programming, we write (f) = E [c(0, a, 7)) and Re a) == E, [r(0, a, 7)]-
As per Algorithm [ the agent's decision mode in round t is given by the optimal solution क of programming J(p: He). The algorithm stops when the resources are near depletion, that is, B < for some resource E [z]], and we use To to denote the stopping time of Algorithm i.e. To == min min 3i E [m), Bi+ <1}}.
For an analysis beyond the worst-case scenario, a crucial assumption we will make is that the fluid problem possesses good regularity properties, i.e., it is an LP with a unique and non-degenerate solution.
Assumption 3.1. The optimal solution to J(p)) ) is unique and non-degenerate.
As pointed out by Bumpensanti and Wang 13 uniqueness and non-degeneracy are a critical factor for an o( (TT) regret bound hold in the CDMK problem, at least for the frequent re-solving technique we use in this work (26). Intuitively, if ((p)) is degenerate, then with any minor error on the estimation, the optimal solution to J(p., H4) can have major different landscape with the optimal solution to (p1) in the sense of basic variables and binding constraints, and this will lead to an (VT)) accumulated regret. For completeness, we formally define the above concepts.
Definition 3.1. context-action pair (0, a) is a basic variable for J(p) (0,00) a) > 0, or else, is a bon-basic variable. Similarly, define basic/non- -osiiaic variables for [p., Hz).
Definition 3.2. E [m] a binding constraint for J(p) if Eoce uO0)C" a),,a)o (0, a) pl. or else is a non- non-bonniene mind-inning constraint. We let == {i is a binding constraint for J(p))) T= [n] SS
and we klss or klTT to define the sub-vector of k confined on S T, respectively. Further, 0 E θ is a binding constraint for J(11) if Eae of (8, a) = 1, or else it a non-binding constraint. Similarly, define binding/non-binding constraints for J(p,, H.).
As stated above, we want to guarantee that when the "distance" between J(p: Hi) and J(pi) is sufficiently small, the optimal solution to these two programmings have the same landscapes. In this sense, we consider stability factor D to measure such a threshold, as presented by Mangasarian and Shiau [3
7

---

Proposition 3.1 (Stability). Under Assumption 3.7 there is a maximum D > 0. such that when the following holds:
max {ll(u(0) - u.
((((()) - ,e(t)) - D, max (1pils - Prlsll max (pilT- ptlT)) $ D,
(I)
(p1) and Mpe. He) share the same sets of basichonn-basic variables and binding/non- constraints.
With the assumption, below we present the main result of this work, which is proved in Appendix C.1 3.1 with full information feedback, the expected accumulated reward Rew brought by Algorithm when T + Do satisfies:
Theorem 3.1. Under Assumption
VFL Rew O 0 n12 + +k
D2
which is independent Tf
The intuition behind Theorem 3.1 is to conduct a regret decomposition in Lagrangian manner, motivated by Chen al. [16]. This leads three remaining terms (cf. Appendix C For the first two Lagrangian product terms, thanks to Proposition 3.1, they equal 0 as long as the estimates of the distributions are sufficiently accurate with an errоr of ODD, which will happen with high probability after a constant number of rounds. The last term reflects how the stopping time of Algorithm [ is close to the total time-span T'. On this front, we are left demonstrate that the resources are spent smoothly. Intuitively, this property is guaranteed by combining two observations: (1) In each round, the action mode ensures that resources are spent evenly in expectation the estimation world due to the re-solving step, and (2) the distance between the estimation world and the real world diminishes zero, with the accumulation of samples. The complete reasoning is much more detailed.
with results in prior work. We first mention that our benchmark VEL larger than the benchmark used in Slivkins and Foster (36] and Slivkins al. (37], as proved in Appendix B Thus, our result provides a stronger regret upper bound. As for the constants in the regret bound, first, our regret does not involve m explicitly. This is superior to existing results, which report an ((ym) reliance 8 36
We now compare Theorem 3.1
As an intuitive reason, the number of actions does not explicitly appear in our Algorithm but only contributes to the dimension of the linear program. However, m could appear some complex and problem-specific constants that we omit in the bound. Interested readers can refer to Appendix [foo more details. Second, although l does not always appear in previous works, this is inevitable our bound, brought by the estimation error of the context distribution. Third, for the BwK problem, the well-know O T") result given by Sankararaman and Slivkins [32] supposes that n S 2, and it is still unclear whether their analysis can be extended to arbitrary number of resources. Our result does not suffer from such limit. Finally, we remark that in the absence of resource constraints, is precisely half the gap between the mean rewards of the best and accond-best arms. Thus, D resembles the reward-gan seeaaddgap-liie gap-like parameter in the multi-armed bandit literature. The dependence on D of our result is similar to the first result in Sankararaman and Slivkins 32 and is the same with Chen al. (16), and it is still unclear whether the dependence can be improved. We should also note that we omit the dependence of our regret bound on the unknown size of the external factor set in all our results, which could be improved via parameterized estimation techniques.
24
One key implication of Theorem 3.1 is that the re-solving heuristic's regret is independent of the number of rounds beyond the worst-case with full information. This result significantly improved previous state-of-the the-art results under mild assumptions, surpassing the solutions proposed by Han et al. [24 and Slivkins and Foster [36]. In particular, their solutions come from the BwK literature and rely dual update and upper confidence bound (UCB) heuristies, which only provide a worst-case regret of O( O(yTlog T)
4 Partial Information Feedback
We now shift to consider the re-solving method's performance with partial information feedback, under which the agent only sees the external factor " when her choice is non-null in round t, i.c.
8

---

a; * O. Apparently, with less information, the learning speed of the distribution V decreases, hindering the re-solving procedure's quick convergence to an optimal solution. Nevertheless, we demonstrate that the performance of the re-solving method only faces an O(log 7) multiplicative degradation under partial information feedback. Our primary theorem in this section is as follows:
Theorem 4.1. Under Assumption reward Rew brought by Algorithm when T + 00 satisfies:
3.7 with partial information feedback, the expected accumulated
VFL Rew 0 n. + l log T
D2
Before come to the technical parts, first place Theorem 4.1 within the literature. As previously mentioned, 92( (T) is worst-case lower bound on the regret even with full information feedback and thus also extends as a lower bound with partial information feedback. However, Theorem 1.1 steps beyond the worst case by providing Olog T) upper bound for regular problem instances. This result outperforms the universal ToT T)) regret by Han et al. [24] and Slivkins and Foster [36]. While the result is asymptotically equivalent that of Sankararaman and Slivkins 32 it imposes fewer restrictions on the problem structure, as previously discussed.
We now provide an intuitive understanding of the proof of Theorem 4.1 The crux lies in analyzing the frequency with which Algorithm can access an independent sample of the external factor. To this end, we use Y; [Zel S 1 to denote the number of times non-null action is chosen before time f, or equivalently, the number of i.i.d. samples from V observed by the agent before time f under partial information feedback. The following crucial technical lemma provides a lower bound on Y,.
Lemma 4.1. There is a constant 0 < C < 1/2, such that with probability O(1/T), the following hold for Algorithm 7
T for some constant Cj; 2. For any > C. T, Y, 2 C, T for some constant Cy,.
1. For any (log T) S C. T, (t- log
The proof of Lemma 4.1 is deferred to Appendix D.2 In simple terms, during the initial O(log T) rounds (the shaded segment), the re-solving method cannot guarantee the accessing frequency since the learning of the request distribution 24 has yet to converge sufficiently. However, after O(log T) rounds, Algorithm [ ensures a constant probability of obtaining a new example each round, provided that the remaining resources are sufficient. As consequence, before ((T) rounds, we can guarantee an 12(1/ log T) accessing frequency at any time step and an overall (2(1) frequency with high probability, established by concentration inequality. The remaining proof of Theorem 4.1 is provided in Appendix D.I
Relaxing the Regularity Assumption - Worst-Case Guarantee
In Sections and 4 we have proved that Algorithm can achieve an Õ(1) regret for CDMK problems under full and partial information feedbacks, assuming certain regular conditions (cf. Assumption B. Put differently, the re-solving heuristic nicely deals with regular scenarios. In this section, we complement the above by showing that this method can attain nearly optimal regret in the worst cases. Furthermore, in Appendix A we extend our analysis to cases where the context and external factor distributions can be continuous.
Our main results are given below, and their proofs are provided in Appendices E. and respec- tively.
Theorem 5.1.
With full information the expected accumulated reward Rew brought by satisfies: FLL Rew OokkTToo + n),, as T co.
Algorithum 1
Theorem 5.2.
With partial information feedbuck, the expected accumulated reward Rew brought by
Algorithm satisfies: FL.
Rew = OOk log log T + n), as T
00.
As given by Theorem
2.1 the worst-case regret of any online CDMK algorithm is R(VT), while
Theorems 5.1 and 5.2 indicate that the re-solving heuristic reaches near-optimality in such cases.
24 36 can at most obtain an Ö(VT) regret even with full/partial information feedback. Our algorithm also achieves this near-optimal regret bound in worst cases.
Further, ofate-of-the-art algorithms

---

Info
Partial
Partill
40
Regres
Rounds 110")
Total Rounds (10%)
Total Rounce (30')
Total Rounds (30")
Figure 1: Regret of Algorithm under different number of total rounds 7 = 2000 2 for integer S S
worth noticing that we omit some wroblem-specife constants in the previous bounds, e-g., the fluid optimum J(1)), which could be related to the number of non-null arms m. Therefore, our results do not conflict with the well-known D(VmT) regret lower bound as given by Auer et al. [7].
6 Numerical Validations
In this section, we use numerical experiments to verify our analysis. We perform our simulation experiments with either full or partial information feedback under two cases. The first is with degenerate optimal solution, and the second is with a unique and non-degenerate optimal solution. We delay more details, including the choice of the problem instances, to Appendix
Figure D describes the relationship between the regret and the number of total rounds T under all four settings. We the horizon T to be 2000 2 for integer 0 <. k S The figure displays both the sample mean (the line) and the 99%--confidnnc interval (the light color zone) calculated by the results of estimations for the regret, where each estimation comprises 400 independent trials. Observe that when the LP (()) degenerate, the regret grows on the order of Ö under both full information and partial information settings. Further, when the underlying LP J(p) has unique and non-degenerate optimal solution, the regret does not scale with T under the full information setting. In the partial information setting, the regret slowly grows with T, which matches our O(1) theoretical guarantee.
7 Concluding Remarks
This work establishes the effectiveness of the re-solving heuristic in the contextual decision-making problem with knapsack constraints. We first prove that the gap between fluid optimum and online optimum 2(VT) when the fluid I.P has unique and degenerate optimal solution. Further, we show that the re-solving method reaches an ((1) regret with full information and an O(log T") regret with partial information when the fluid LP has a unique and non-degenerate optimal solution, even compared to the fluid benchmark. Considering the sufficient condition for Q(v lower bound, non-degeneracy assumption is mild, especially when comparing with the two-resource condition required in Sankararaman and Slivkins [32].
Further, we show that even in worst cases, the re-solving method achieves an O T' regret with full information feedback and an O(vT log 7') regret with partial information feedback. These results are comparable to ofart-oftthe-ar results 36]. We also extend our analysis to the continuous randomness case for completeness.
Acknowledgement
This work is supported by the National Natural Science Foundation of China (Grant No. 62172012). by Alibaba Group through Alibaba Innovative Research Program, and by Peking University-Alimant Joint Laboratory of AI Innovation. Part of this work was done when Rui Ai, Mingwei Yang, Yuqi Pan, and Chang Wang were undergraduates Peking University. The authors thank Yinyu Ye for his kind suggestions and all anonymous reviewers for their helpful feedback.
10

---

References
[1] Yasin Abbasi- Yadkor, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24, 2011.
[2] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference Machine Learning, pages 1638-1646. PMLR, 2014.
[3] Shipra Agrawal and Nikhil Devanur. Linear contextual bandits with knapsacks. Advances in Neural Information Processing Systems, 29, 2016.
[4] Shipra Agrawal, Nikhil R Devanur, and Lihong Li. An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives. Conference on Learning Theory, pages 4-18. PMLR, 2016.
[5] Alessandro Arlotto and Itai Gurvich. Uniformly bounded regret in the multisecretary problem. Stochastic Systems, 9(3):231 2019.
[6] Peter Auer. Using confidence bounds for exploiaation-expllration trade-offs. of Machine Learning Research, 3(Nov):397-422, 2002.
[7] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77,200 2002.
[8] Ashwinkumar Badanidiyuru, John Langford, and Aleksandrs Slivkins. Resourceful contextual bandits. In Conference on Learning Theory, pages 1109-1134. PMLR, 2014.
[9] Santiago Balseiro, Omar Besbes, and Dana Pizarro. Survey of dynamic resource constrained reward collection problems: Unified model and analysis. Available at SSRN 3963265, 2021.
[10] Santiago R Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, 65(9))3952-3968, 2019.
[11] Omar Besbes, Yash Kanoria, and Akshit Kumar. The multisecretary problem with many types. arXiv preprint arXiv:2205.09077 2022.
[12] Robert L Bray. Logarithmic regret in multisecretary and online linear programs with continuous valuations. Operations Research, 2024.
[13] Pornpawee Bumpensanti and He Wang. A re-solving heuristic with uniformly bounded loss for network revenue management. Management Science, 66(7):2993-3009 2020.
[14] Matteo Castiglioni, Andrea Celli, and Christian Kroer. Online learning with knapsacks: the best of both worlds. International Conference on Machine Learning, pages 2767-2783. PMLR, 2022.
[15] Andrea Celli, Matteo Castiglioni, and Christian Kroer. Best of many worlds guarantees for online learning with knapsacks. arXiv preprint arXiv:2202. 13710, 2022.
[16] Guanting Chen, Xiaocheng Li, and Yinyu Ye. An improved analysis of Ip-based control for revenue management. Operations Research, 2022.
[17] 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.
[18] Adam N Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 68(1):9-26, 2022.
[19] Kris Johnson Ferreira, David Simchi-Levi. and He Wang. Online network revenue management using thompson sampling. Operations research, 1666):158--160) 2018
[20] Arthur Flajolet and Patrick Jaillet. Logarithmic regret bounds for bandits with knapsacks. arXiv preprint 1rXiv:1510.01800 2015.

---

[21] Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199-3210. PMLR, 2020.
[22] Dylan Foster, Alekh Agarwal, Miroslav Dudik, Haipeng Luo, and Robert Schapire. Practical contextual bandits with regression oracles. In International Conference on Machine Learning, pages 1539-1548. PMLR, 2018.
[23] András György, Levente Kocsis, Ivett Szabó, and Csaba Szepesvári. Continuous time associative bandit problems. In IJCAI, pages 830-835. 2007.
[24] Yuxuan Han, Jialin Zeng, Yang Wang, Yang Xiang, and Jiheng Zhang. Optimal contextual ban- dits with knapsacks under realizibility via regression oracles. arXiv preprint arXiv:2210. 1184, 2022.
[25] Stefanus Jasin. Performance of an lp-based control for revenue management with unknown demand parameters. Operations Research, 63(4))909-915, 2015.
[26] Stefanus Jasin and Sunil Kumar. A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Mathematics of Operations Research, 37(2): 313-345, 2012.
[27] Jiashuo Jiang, Will Ma, and Jiawei Zhang, Degeneracy is ok: Logarithmic regret for network revenue management with indiscrete distributions. arXiv preprint vrXiv22200009990 2022.
[28] Xiaocheng Li and Yinyu Ye. Online linear programming; Dual convergence, new algorithms, and regret bounds. Operations Research, 2021.
[29] Xiaocheng Li, Chunlin Sun, and Yinyu Ye. The symmetry between arms and knapsacks: A primal-dual approach for bandits with knapsacks. In International Conference on Machine Learning, pages 6483-6492. PMLR, 2021.
[30] Heyuan Liu and Paul Grigas. Online contextual decision- making with a smart predict-then- optimize method. arXiv preprint 2xXiv:2206.07316 2022.
[31] Olvi L. Mangasarian and T-H Shiau. Lipschitz continuity of solutions of linear inequalities. programs and complementarity problems. SIAM Journal on Control and Optimization, 25(3): 583-595, 1987.
[32] Karthik Abinav Sankararaman and Aleksandrs Slivkins. Bandits with knapsacks beyond the worst case. Advances in Neural Information Processing Systems, 34:23191-2322 2021.
[33] Gerard Sierksma. Linear and integer programming: theory and practice. CRC Press, 2001.
[34] Vidyashankar Sivakumar, Steven Wu, and Arindam Banerjee. Structured linear contextual bandits: A sharp and geometric smoothed analysis. In International Conference Machine Learning, pages 9026-9035. PMLR, 2020.
[35] Vidyashankar Sivakumar, Shiliang Zuo, and Arindam Banerjee. Smoothed adversarial linear contextual bandits with knapsacks. In International Conference on Machine Learning, pages 20253-20277. PMLR, 2022.
[36] Aleksandrs Slivkins and Dylan Foster. Efficient contextual bandits with knapsacks via regression. arXiv preprint arXiv:2211.07488. 2022.
[37] 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.
[38] Alberto Vera and Siddhartha Banerjee. The bayesian prophet: A low-regret framework for online decision making. Management Science, 67(3):1368-139)) 2021.
[39] Alberto Vera, Siddhartha Banerjee, and Itai Gurvich. Online allocation and pricing: Constant regret via bellman incqualities. Operations Research, 69(3):821-844 1-800, 2021.
12

---

[40] Larry Wasserman. Density estimation lecture note for 36-708 statistical methods for machine learning, Carnegie Mellon University. 2019.
[41] Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. Inequalities for the II deviation of the empirical distribution. Hewweet-Puckard Labs, Tech, Rep, 2003.
[42] Huasen Wu, Rayadurgam Srikant, Xin Liu, and Chong Jiang. Algorithms with logarithmic or sublinear regret for constrained contextual bandits. Advances in Neural Information Processing Systems, 28, 2015.
13

---

Appendix of "Contextual Decision-Making with Knapsacks Beyond the Worst Case"
We begin by outlining the structure of the whole appendix. In Appendix A we state our regret results with continuous randomness. Appendix B we prove the regret worst-case result (ef. Theorem 2.1
Appendix C.I devotes to proving the main result (cf. Theorem 3.1b. where Appendix C.I.I presents
the Lagrangian regret decomposition, and Appendices C.1.2 and C.1.3 analyze different terms in the decomposition. Appendices C.2 to C.6 complement missing proofs of lemmas arising in Appendix Appendix[D]oos focuses on proving the regret results in the partial information setting, where Appendix [.I derives Theorem 4.1 and Appendix D.2 proves the crucial Lemma [.] for the partial feedback model. Appendices D.3 and D.4 prove lemmas arising previous parts of Appendix
D Appendix [] with Theorems 5.1 and which show that the re-solving method is near-optimal even in worst cases. At last, Appendix G complements the missing details of Appendix A with continuous randomness.
A From Discrete Randomness to Continuous Randomness
In the main body of this work, we explicitly assume that both the context set and the external factor set are discrete. Such assumption can suitably capture most real-life situations. For example, in an agent's online bidding problem with budget constraints, if we presume that the context is the agent's actual value and the external factor the highest competing bid, it natural to suppose that all these three values are discrete. Nevertheless, for theoretical completeness, we expand our results in this section cireumstances where these two sets are infinite, i.e., the two underlying randomnesses are continuous. It is imperative to note that the scenario where one randomness is discrete and the other continuous would analogous analysis by incorporating the techniques presented in Section 5
Conceptually, the re-solving heuristic still works: we solve the optimization problem in each round concerning the remaining resources based on previous estimates. However, technically. since the distributions of context and external factors are continuous, we should further elaborate on the setting. In this section, we suppose that the context set = [0, _]d. and the external factor set 1 [0, 1]d- We denote u(f) and v(r) as the density function of ll and V. respectively. We assume that E {u, v} belongs the 3p-order Hp-Held smooth class 3(pp. Lp). Here, for the foundation, given a vector ($1,..., s2), define
|s| = + sd,
D
0xj
Subsequently, for positive integer B, the 8-order L Hölder smooth class is defined
E(8, L) =00: (D)(()) D g(v)l & L|| 3ll2, for all such that |s| = 3 - 1, and all v)
Now, suppose "I,..., Xg are le i..dd. samples from a distribution with density function p E E(8, L). According to Wasserman [40], we have the following result, which implies that we can calculate an estimator from these samples that converges to the density function.
Proposition A.1 (Wasserman [40]) Suppose _ .x are drawn i.i.d. from a d-dimension distribution P, with density E EBS, L) for some L > O, and k is sufficiently large. Then there exists an estimator Pk such that for any >>
Pr sup (px) - px(x)) CVlog(k/e) 13/(23+d)
Se,
with C' a constant.
The details of constructing such a density estimator are postponed to Appendix G.I We now return to the re-solving heuristic and Algorithm [] In the algorithm, with continuous randomness, the constrained optimization problem to be solved in each round J(p., H4) for 1.2, ... becomes:
Mpt, H4)
Σ +R aEAt
/
a(0,a) ( ((8, dy de,
max x:0xA
14

---

1 v(0,a)
(0,0) / c(0,,,, (00,,,,)00 (0) d0 s Pr.
s.L.
aEA+
Σ ((0,a) 5 V0E aEAt (0,,0) a) 20, (0, E At.
Correspondingly, the reference optimization problem (p:) is given below:
| @(0.0) / a ((0,),))((()(())dd))
J(p)) = d
max
GEAt
Σ v(0,a) I, c0, a, dh S Pr.
s.1.
aEA+
Σ 000,0) SL V0
aEA+
(0,0)200 v(0,a) E@x
At this point, it is worth mentioning that solving J(p Hz) in each round could be hard it could be a continuous yet non-convex constrained optimization problem. Nevertheless, we assume the existence of an oracle that aids in solving this optimization, and we focus the regret of the re-solving method. Let a. == (3u. + d2,/ d.) and a₂ == (3. + d.)/(23, + d.), and we have the following two results, respectively, under full and partial information feedback.
Theorem A.I. Under continuous randomness, with full information feedback, the expected accumu- lated reward Rew brought by Algorithm 7 satisfies:
FLL Rew O( T + +T2 /lg + T
Theorem A.2. Under continuous randomness, with partial information feedback, the expected satisfies:
accumulated reward Rew brought by Algorithm ]
VFL - Rew =( T Vlog T lo2 2/2-0===TT + T
The proofs of the above theorems are presented in Appendices G.2 and G.3 respectively, which almost follow the threads of Theorems 5. and 5.2
B Specifying the Worst-Case Gap Proof of Theorem 2.1
To prove the lemma, first introduce intermediate value, which we denote Hyyb, to upper bound VON, and show that the gap between Hyyb and FLL is O(VT) under the given condition. Specifically, we have the following definition:
T
Hyb = Bo,... Pr
R(Or, ((0r,a)
max
1=1
De
Σ Σ C(ona))i(a) S PT,
s.t.
(2)
(=1 a
Σ (1)a) 1 [7,
a
(, 2 0, V(t,a) E [ A+.
To see that Hyb gives an upper bound on VON we fix a request trajectory ., Or. Now, for any non-anticipating strategy म, let
(F Pr(a, a 01. 0.]
15

---

be the total probability that a. = conditioning on the pre-determined request sequence, with respect 7i.-. - and the randomness of strategy и. We show that {pF It,,,.., is feasible solution Hy under "1, Cr. Here, key observation is that for any E [7]:
[c(0,, a7. 0. 0r] = Erg
Σ LaEA+
al n)) Pr(a - a a1,,,.. 0r]
= Σ
aEA
In the above, the first expectation is taken on " Tn and the random choice of strategy Since
Ei= c(O,, al, 7e) I Pr always holds, we derive that
T
T
ΣΣ
C(O.. a)p = Σ
c(0,, of 7e) .1,... Or
Or S sT,
[=1 DEAt
which indicates that have
{pT h==,,... is feasible to Hyb under 0,, Or. To the same reason, we also
T
Σ
Σ a) (a) = E Σ r0 of m) 01,... Or aEA+
equals the conditional expected reward of strategy т. Thus, since Hyb is maximization problem for any request trajectory, we conclude that H VON
remains to show that when VFL, or (p) has unique and degenerate solution, V Hyyb ((VT). We first present transformation of Hyy We
# lappearance of (
x (0)
T
he the random variable indicating the frequency of when is drawn T times i.i.d. from U. Obviously, the mean of is u. We now demonstrate that
Hyb T Ex
max Σx x0)
Σ
R(0, ((00,)
d:0xA+ -
DEG
aEA+
8.b.
Σ (0) Σ
C(O,a)o(0, a) S p.
(3)
9
RE
Σ
@ a S1, VEE
aEA1
@(0 a) 20, ((O.a) A
To see this, in form it is not hard to see that conditioning on ... Gr, the value of the optimization is only related to the number of times that any E θ appears the sequence, and irrelevant with their arriving order. Therefore, by taking average, it is without loss of generality to suppose that o = or as long as 0,, = Ozg- Under such an observation, it is natural that (2) is equivalent
For convenience, we now recall the definition of VPL:
= =T
Σ u()) Σ ((0,a)o(0.a),
max
DEE
aeAt
Σ
Σ ((0,a))(0,a) Spp
REA+
Σ
@(8, a) 11,
10 10E
REA!
@(0, 20, ((0,a)x0xA
16

---

By Sierksma [31, we know that when (() has a unique and degenerate solution, then its dual form has multiple solutions. We then adopt the framework of Vera and Banerjee [38.. In particular, we let À 220 0 be the dual variable vector for the resource constraints, and μa 2 0 be the dual variable vector for the probability feasibility constraints. If we take w()) = uu00/ u (0), then the dual programming of VFL is the following as function of u.
DIz(u)] min p uuuw w,
s.t. XTC(O, w 2 R(0,a), a),
A 0, w 2 0.
Now, suppose (Aa w and (X², w²) are two different optimal solutions to D[Z(u)], which directly leads to X * X² by the programming formation. We let = X X² and w' w w Then,
x uu =p x uu
P X Tww'= =0
(4)
Further, notice that (A, and (A², w are both feasible for D [xx)] for any Since D(Z(z)) is a minimization problem, by convex combination, we have
X + w')llp X' x Di S Tp
T w <o w X + 0j.
Further, by optimality, we know that for any x.
DIZ(u)] = (p (T X +u ToTTT" w' X a w 50 Tx +u u wo> X + x w > 0].
Now, by weak duality, since HHy /T for any given æ is a maximization problem, we know from the above two equations that
(MPL - /
D[]((=)] - E. [a]
2 Eg [((u - . w 11p X' t T < + ((u - x) T wT> X' + Tw' > 0]
Eg [((u x²) wh ) x) Tw' 2 0] + ((u x)) TT) w 1[(u x) Tw' 2 0))
Ex [(u - TT)TTT') w - Tw 2 0]
Here, (a) is due 4 and (b) is since the mean of u. Now, we let vT(u x) T w/ be the normalized scaled variable. By the Central Limit Theorem, {1|E 2 0] converges to a half-normal distribution, which has a constant expectation. Thus, we arrive at VFL /Hyb ((vT), which finishes the proof.
C Missing Proofs in Section
C.1 Proof of Theorem 3.1
We now give proof of Theorem 3.1 The proof draws inspiration from that of Chen et al. [6 but significantly diverges in terms of the problem setting.
C.1.1 Regret Decomposition
We start by presenting a regret decomposition approach, which stands on the dual viewpoint. We first recall the optimization problem FFL = T ((::):
J(pi) == max
Esnu
Σ
R(O,a)
LEAt
s.t. Ex-ell
Σ
C(0,a)o(0.a) S1,
LeEA!
17

---

Σ a(0,a) S1, V
aEA+
(0, 20,
v(0,a) E x
Recall that u()) denotes the mass function U, then the above linear program can be expanded as
((p)
max
Σ
(()00))
x
PEA,
s.t.
Σ
(0)C((,a))(0).0 S Pl
BEA
Σ aEA+
(0, a) 51, ve
() 20, E0x
Now let À 2 0 be the dual vector for the consumption constraint and {u² (0)]ae 2 the dual variables for the action distribution constraint. By the strong duality of linear program, there is an optimal dual variable tuple (A", (ur (E)) 2 such that:
((p))
Σ BEO,
(u(0) (R(0)a) a) (x*) C(e. - -² (().)) o1(0. + (Xx) Pr E2((0)
u(0) (R(O, a) - (Xx) (0,4) PI.
AE
(5)
Here oj the optimal solution to J(p)). With 5) we have the following lemma for regret decompo- sition.
Lemma C.1. For any stopping time Te S To adapted to the process {B,} 's we have
FLL
Rew
E
Σ
((0)
(0)) (((1,a)-6i(0..))
t=l DEA+
(6)
(0)
Σ (((0,a)
AEE
aEA+
(X*) TE [BT.+1]
(R(0, - (x(0,,)-(X")TTC( C(O)a) - ET Te).
aE0,aEA+
The proof of Lemma C.1 is deferred to Appendix C.2 We now give a brief explanation on this result. The first two terms in (6) depicts the gap between the choice of Algorithm and the optimal decision. This is apparent for the first term. For the second term, we should notice that by complementary slackness, for each 0 E O,
" (0) (1- (1- Σ (1( = O.
(00 aEA+
-110.0)=
Therefore, the second term in 66) is bounded if 0t close to Φj.
On the other hand, the last two terms are closely related to the choice of stopping time T. and the consumption behavior of Algorithm [ Intuitively, if T. is sufficiently close to T', then [E[T-- - T.] should be appropriately bounded. Nevertheless, if the algorithm spends the resources too fast, then such sufficiently large Te would be impossible. Conversely, if the resources are consumed substantially slower than the optimal, then the term E B[Br,+1] the remaining resources at the stopping time, would be unbounded.
In the following, we will deal with these two parts correspondingly. crux to the analysis to pick satisfying stopping time Te. which will first cover.
18

---

C.1.2 The Gap to Optimal Decision
We first give a realization of the stopping time Te. With Proposition 3.1 in hand, we can derive that when condition T is met, it holds that
(u(0) (R(O, a) (X*) ((),a)) - (0)) (oi(0,a) ()](0,))) (0.0.) = 0,
(7)
[o) 1 (1-
E1-E Σ (1 O.
(8)
DEG
REA+
To see these, notice that by the dual feasibility of (pi), have u(0)
(X-)
1 (0) S O. When u(0) (R(0, a) - (A*)T a(), - 1 (0) < 0, by primal optimality, o $0 a) =
and thus (0, a) is non-basic for ((1). By Proposition 3.1 (0, a) is also non-basic for [pt. Ha)
and 0z (0, a) = holds as well. This finishes the deduction of 7 similar reasoning on binding constraints would help us achieve (8. which we omit here.
As the above goes, is then natural for us define T. the stopping time in our analysis follows:
Tg == min (To, min {t= max (1 Is pelsslsse max((117> - Ptlr)) > D) 1},
(9)
where To the stopping time of Algorithml 1 With the definition, we always have max
Pils alll max (P1lT p.]T}] < D when / < Te- What we are left is to bound the situation when max (m(( We (0)) (l(((()) Tr <errrll
D for 1 < 1 S Te. In total, we arrive at the following result for this part, with the proof given in Appendix C.4
Lemma C.2. Under Assumption 3.7
withfull information feedback, have when T
Tx
E
Σ
(u(0) (R(O,a) (Ar) - 1r ()i(0.a) - -3:(0a))
1=1
AEO,aEA+
k
0
D
T
(1-Σ
(1- Σ (((0,a)
] =0
E
Σ
(0)
D2
LEB
GEA+
We are now only left to bound the last two terms in (6)
C.1.3 The Gap to Optimal Consumption
As presented in (6). we now bound the remaining two terms, respectively BT.+,+1] and E Tel
for Te defined in (9.. It turns out that these two terms are closely related. Due to this observation, would first bound (X*) E E[Br,,1] by E[T Te], and then bound E(T - Te].
Now by the strong duality of (p:)). ). we know that complementary slackness holds, that is A = 0. We therefore have
(At)Te T [Br++]]
$ (A*) T Br. = (s) E ls] = (A*1s) TH [(T- T + 1)Pr. Is]
(10)
2 ma + D| [T
+ 1].
In the above, recall that pma denotes the maximum coordinate of pl. and is specified in Proposi- tion 3.1 Consequently, (a) is due to the definition T. and that ||p| D1 I p D.
We are left bound E[T Tel. Nevertheless, this part would be rather technical and involved. Therefore we defer the analysis to Appendix C.5 and only give the final bounds.
Lemma C.3. Under Assumption
3.7 with full information feedback, we have when T Co:
112
(Xt)T E [r.+t]]
+
max 0e
(R(0,a) -200)-((7)) (X+)T C(O. E Tol 0
D
Combining Lemmas C.I to arrive at Theorem 3.1
19

---

C.2 Proof of Lemma C1
The proof is obtained by the following set of (in)equalities.
VFL_ Rew
To r0,, as, To)
T ((pi) -
(0)
I T J(1)) - EE
Σ r(0e, 71)
Te
(b) T J(p)) E
Σ
((0))(())));(00.))
(=1 aEA
Σ (0(1))
T
AEA,aEA+
0E6
Tc
E
u(0)R(0, (0)
t=1 DEA,
(
T
(u(0) (R(O, a) - (2-) C(O,a)) (())) -1((0) (6)(0,a)-3:00 (310.a))
AE
x +
+ EEn00) 1- Σ ( st((,a) a)) )) E Tel
E
(0)
E
1- Σ
('(0)
1=1 BEB
DEA!
BEE
aEA
Te
+(A*)TE
Tpı Σ
Σ
(0))((10))))00..)
BEB,aEAt
Σ (u(0)(R(O,a) C(O, ()) (i)
ET -T.]
AEA.EEA!
(u(0) (R(0, ((()) -0))) (((0:a))0((01)))
E
1=1 aEA+
1- Σ 8((0.a) }
E
(0)
BEB
GEA+
(X*) T [
(R(0, a) - (x)))C((O,))) E - TTl
max AE
In the above set derivations, (a) holds since To 2 Te, (b) is due to Optional Stopping Theorem since T. is stopping time, (c) is by the strong duality of (p1) as given by (5). (d) establishes by rearranging terms. At last, for (c), the diminishing term is by strong duality, the transformation from the fourth term in (d) to the third term in (e) is derived by another application of Optional Stopping Theorem on the accumulated consumption vector, and for the last term, the upper bound is achieved since EncA' (1, a) for any 0 θ and Eace u(0) 1.
C.3 Proof of Proposition 3.1
We will apply the stability result in Chen et al. [6] as an intermediate to prove our version. As given, know that J (p1) and ((, H.) has the same set of basic/non-basie variables and binding/non-
20

---

binding constraints as long as the following conditions hold for some constant Do > 0:
1( (ulo) ((() Σ u(1)r(0,a,)) - (,(0) Σ ((())((0)
Do.
(0.0)E0xA+ 1000
(11)
u Σ (0,,7) -i((0) Σ - (f(.))
$ Du,
vi [n],
(0.0)E0xA+ 10
pils Polslloo Do. max (piTT m pilT) S Do.
Now, by a standard insertion technique, we have
u(0) Σ v())r((,a,,) (x(() Σ ((())((,,an))
(u(0) (0) Σ (())r(0, a, (0) -
(u(()) ü. (0))oell + [1(((T)) - 8r -
(12)
For (a), the first term bounded since r(0,a, 0, 7) S and Σ, v(7) = The second term similarly bounded as (0) < 1. Therefore, we let D Do/2, then when we have
II(u(0) (E)) D. [1((()) (()))) < D,
the first condition in (11) is met. An almost identical reasoning also holds for the second condition in Consequently we finish the proof the lemma.
C.4 Proof of Lemma
Recall that we are going to prove that
T
E
(u(0)
-rr()))))) 1²)) (0100,0)3:10.0)))
AE
=
D2
Tx
1- Σ @,(0,a)
k ) =0
E
(0)
# (0)
D2
t=
BEB
aeA!
when T + 2o under Assumption 3.1 For simplicity, we give the following abbreviations:
Pa Σ (R(0, - (A-) C(()) -0) (oi(0.a) (0i(0.a)-0:00 -0:(0a))
8EB,aEat
Q= E1' 1- E--E Σ (..
DEA-
Ey, = [I)( (1)) s D).
Ex = [1(((()) - 6.(1)) S D).
On this end, we first utilize Proposition 3.1 to show that when condition | holds, we have
Pt = Q. 0.
Specifically, for Pt. by the dual feasibility of J(1),, we have u(f) (
C(B,a))
4" (0) < O. When u(O) (R(0,a) a) a)) μ² (0) < 0, by primal optimality, (0,
21

---

and thus (0, a) is non-basie for Jp1). By Proposition 3.1 (0,a) is also non-basic for [p: H4) and 07 (0. a) holds as well. In conjunction with the case that u(0) (R(0, a) (A0) a)) u² (0) = 0. we obtain that P. = 0.
For Qt. notice that we have (0) 2 0 for any 0 E O. The case that (²(0) 0, again, does not contribute to the total sum. When μ (0) > O, by complementary slackness, Exe (i a) = 1, i.e., 0 is a binding constraint for J(p)). This, by Proposition 3.1 implies that 0 is also binding for (pt: Hr). which shows that the second term is also zero
With the above, it remains to consider the situation that condition TT) does not hold when & I Te or in other words, ε., A E. does not hold. Note that Pt S and Qr S 1 always hold. Thus, we only need bound the probability that -(Eu, A E, By a union bound, we have
Pr[-(Eu, E), Pr(-Eu, V - & Pr[-Eu,]] + Pr[-Ee,r]-
For the first term above, we apply the Hoeffding's s inequality and a union bound to derive that
Pr[-Eu,1] (u() ãn (e)))ee > D $ 2k exp (-2D² 10:-1 11)
Whereas for the second term, the concentration result in Weissman et al. 41 derive that
pr[-Ew,)] Pr[l((((7) - (r)))rlll DJ 5 (2 exp (-D² 1)/2..
Synthesizing the above all, we have
E[P:] = E[ Eu, A E Pr(Eu, A Ev,1l + E(Pp | (E A E,,1) Pr(-(Eu, A E,,A)
5 1++1-0 Pr(-(Eu, A E,,1)
s 2k exp (-2D 1)) + (2 - exp (-Di(t 1)/2).
(13)
B[Q:] < 2k exp
(-2 1)) + 2 - exp (- (P 1)/2).
(14)
Summing
and
14
from to Te, we achieve that
Te
Tc Σ
E
Pa
E
Q+
1=1
1==1
exp exp
2k
(-2D2(1- + (2 - exp (-D2 - 1)/2))
24
1 exp (-12/2) = -
21L4 -
k
exp 222)
1
which conclude the proof of the lemma.
C.5 Proof of Lemma
As implied by (1),, the proof of this lemma reduces bound E/T To) i.e., showing that T. is sufficiently close to T. On this side, we first recall the definition of T. in (
Tc = min To, min (t: max (llp Pelslloc, max prl7)) > D} 11,
where To is the stopping time of Algorithm T and S and T correspondingly represent the set of aading/non--indiig resource constraints in L.P ((p)). ). For simplicity, we define
N(p,, D, {x max || k|s loo, max(pxlr - klT s D).
It is without loss of generality to suppose that D < p min We let
To = min(t: P: & N(1. D.S) - 1, T_ = [T+1 1/(pmin D)J-
We show that if f. T_ and E Tp. then 1 < Tg. In fact, under the condition, we derive that
1
B, 2 (T - t + () - D1)
مiin - (pI D1) 1,
22

---

which implies that S To. and therefore t S Tg. As a result, we have
T
T
T- Pr TT = Σ
E [T.
Σ
Pr
2
Pr T. 20
Pr|t Tb] (15)
Before we continue bound (15). we first give an observation on the dynamics of p.. By the update process of the budget, we have for any 2
B B. et = Pt+1 (T - -P:(T - 1) Ct.
Pt Ct --
Pi+1 pit
Now let
Eane EmEAt (0,
Eawul
Enest @0
M
No.
T-
T-
We then have
PL+1
Pt
Pt Ct
M + N.C
(16)
T -
We now define an auxiliary process that benefits the analysis. Specifically, for t E [7]. let
{
x TD: Pro: t> TT.
Pt.
P. =
Therefore,
M + No, t t TD:
iut - P: =10 0,
t> TD.
We further define the following two auxiliary variables for I E [T]:
[M..
t ts Tbi
No,
t S Tbi
MC =
No
0,
t> Tb.
0,
t TD.
As result, we have
P++ - p: M + N.C
Now come back to 15 Notice that
Pr > Tpl
(17)
=Pr(p. $ (pi, D) for some -11==Pp $ NN(pi, D,S)]
Pr
M + No Is D min Σ M N:.) 1 < -D
Pr
Σ
M
Cl ss
> D/2 or min
M 1f < -1/2
+Pr
Σ N
> D/2
(18)
For the second term in (18 observe that each entry of ( NC): }e is martingale with the absolute value of the 7-th increment bounded by I/(T T). Since
Σ
1
T T
by applying the Azuma Hoenf-igg inequality and a union bound, we achieve that
2n exp (-(T- (T-
Pr
Σ
No
D/2
23

---

We now come back to the first term in 18 for any {Di,... , such that Σ D+ -
D D/2, we have
M 8
D/22or or min Σ M
I -D/2
00
D,
Dr T TTT -
}
>
min M T
<
for some 7 E [T - 1].
T-
We now define
ED(+)) = [1M
Dr
min M (min 2 T-
Dr
holds for vp, EN D,
T T-
Since M * 0 only when t < TD. Pt EN(,,.D,S) by the definition of E (D,), we have the following claim:
1-1
C M
D/2 or min
M , < -D/2 c U-E
A
Σ T --T
Dr
<
D/2.
s
7=1
(19)
Thus, we forward bound Pr[-E, (D,)) for a suitable choice of defined events Ex, and En,r as follows:
Recall that we have
E = (l((u()) ū, (0))eelll S D), E,, = - (1)) S D].
-
We have the following lemma, which we are going to prove in Appendix C.6 Lemma C.4. When Pr N(p., D) and Eu,r A Ev, hold,
(T [) ||M 1 $ ]I(u(0) &, (0))ocel11 + (1(u(n) - 0r (7))eerl,,
(T - -) min M 2 -l((u(0) ū. (0) - [[((7)) 8. (r))erll..
Further, clear that (T -) || soloo S and (T - r) -1 holds. Inspired by the above observations, let the series D1, DT be the following form:
1, D,
T T T/T: (1-1)-1/4
T T> nTT,
where 1) E (0, 1) is constant to be specified. We need to satisfy the following constraints:
T-1 Dr
Σ S D/2 (/T) D.
Here, the first constraint instructed by 19). and the second is to guarantee that when ([((()) ū, (0)))e + (2(()) Or (er) < (r - 1)-1/4 for t > nT, Eu, A Ev,r naturally holds, and therefore apply Lemma C.4 For the first one, notice that
Σ T- -P
D. - T-T Σ
- T T)(T 1)1/4 (1 [ - 174
log T
S log
Therefore, for n such that log(1 n) -D/4, Ei DT/(T 1) < D/2 establishes for sufficiently large T > 1, and the second constraint is also satisfied.
We now prepared to bound
for the {D,} we just proposed. To start with, when
< 1/T, E, (D,,) always holds, thus Pr[-E,(D,) 0. When > 1/T, since - 11/1/2 < D, by Hoeffding's 's inequality and union bound, we have
Pr(-E,(D,))
24

---

(n)
S Pr [[(u(0) - (0) beall $ (T- /2) + Pr
[[(((>)- - - (6) $ (T - 1)-1/4/2
(T - 1/2
(T 1)
2k exp
+ 2 exp
8k2
8|1|2
Here, (a) is by Lemma
C.4
and a union bound. Therefore, according to 19
we have
t-1
t-1
Pr
M s
> D/2 or min
M
0 T
< -D/2
(D,)),
T=1
and therefore,
0
1 S +1:
Pr
Σ
M
> D/2 min
M T < -1/2
Σ
exp { [-11/2,
t nyT +1.
T=/++
Plugging the into 188 and
15
obtain that when T 00,
E E
Te]
<T-T.
(T (-(T-t)D -2)
Pr
M s
> D/2 or min
M
0 T < <D/2
+ 2n exp
1=1
r=1
T=1
+ 2n(1 exp(-DD /apD2//8) /8))) +( exp (-T!/2)
n
=0
pmin D
12
At last, combining with 10), we finally finish the proof of Lemma
C.3
C.6 Proof of Lemma
To start with, we notice that
T) pr -Enee
Σ ((00,))
LeEAt
Now, notice that Ps E E D, and Eu,r A Ev,r are the condition of Proposition 3.1 therefore, the set of resource binding constraints of N(e, He) are identical to that of (pt), i.e. S. Hence, for any E [nz].
pl Egnill
Σ
LREAt
Σ
(+) a) Σ (
E
u(0)) a) [0())c(0,
=
AE
AEO,EEA
Σ
(u(0) &. (0)) Σ
(()))
Σ
( (0. a) Σ - (7))
(a)
< (I((()) - (0)) + [1(x(7) Er {+(7))erlli
Here, the bound the first term in (a) establishes because for any E O
(0, a) Σ (0, 7)s <
at
since EaEA A- (0, a) S 1. The bound on the second term is similar. Thus, we achieve the result for binding constraints. The proof for non-binding constraints resembles the above by noticing that
pr ITZ 2 Σ
(0)) a) Σ Gr (x)c((0 a, 7))T.
DEO
25

---

D Missing Proofs in Section
D.1 Proof of Theorem
Specifically, the regret decompo- sition technique in Lemma C.I still works fine. We only need to re-derive corresponding results for Lemmas C.2 and C.3 We have the following results on this side, which are proved respectively in
With Lemma 4.1 in hand,
show how derive Theorem 4.1
Appendices D.3 and D.4
Lemma D.I. Under Assumption 3.1 with partial (etimmattioooeedbbeece we have when T - oc:
To
-² (00)))))())))) - (0,
E
(n(0)
BEO,aEA+
k
= 0
log T
D
(1-Σ
Σ (0.0)) ]]
=0 k log I
E
(0)
1
D2
Lemma D.2. Under Assumption 3.1 with partial information feeeback we have when T -> 0o:
(X*) [[T+ill
max AEA,
T.l 0
D
Lemmas
C.1
D.I and D.2 in together leads to Theorem 4.1
D.2 Proof of Lemma 4.1
Some preparations are required before we come to prove the lemma. To start with, we notice that Y, Pr[a1 # 0) Pr(a,-1 # 0]. By the control rule of Algorithm I we have
Pr(a, + 0] Eng-e
Σ
(0,
H4
LaEAt
We first give lower bound B [EEEAI (0, a) H.,] as an intermediate.
Ea-ai ECEA+ (0,
H+l with Pr.
taking
Lemma D.3.
Σ (0, H, > min min LEEA+
E Benat
Proof of Lemma D.3 To start with, when Pr 2 1. then clearly, all the resource constraints in [pp H.) are satisfied even when ΣaEA) (00, a) holds for any 0 E θ. Therefore, optimal solution should have this form.
We now consider the case that min p. 1. In this case, if there is a feasible solution that En,es- (z(0,a) a) 1 holds for any E O, then the proof is also finished. Otherwise, there is at least a binding resource constraint in J(r. Hl)), which we denote by it, Consequently,
E By-ih.
Σ (1
Eyna. LaeAt
Σ
a1 (0,a)
pt 2 min Pr.
LeEA!
This finishes the proof of the lemma.
26

---

Thus, we have
Pr(a, #0 EBnul
Σ (70,aa
7l
2 B
Σ a0) H.r
-l/u(0) ã (0)ll
LEeA
LEENT
2 min (1, min p.} - [1 ūr (0)ll
(20)
Further, we have the following result bounding min P, when t is no larger than fraction of T.
Lemma D.4. When S (pmin//3 /2) T, min pr 2 pmin|/ /2.
Proof of Lemma D.4 fact, for t S (pmin/ (2)
T. P1 Er=l Cr
T t.
Pr
T-t+1
T
2
This concludes the proof.
Now, by Weissman et al. 41), with probability 1 O(/T), we have
min
(l()) ū., (0)11
Vr 2 O T).
4
Taking into 20 we derive that
min
(l St min
Pr(a, * 0
T.
Consequently, within the period, the probability that there are St(log T) consecutive rounds which the agent chooses to quit in all these rounds is O1)/T). This proves the first part. Meanwhile, at time t mminn (2) T 1, by Azuma Hoeffding inequality, we derive that with probability O1//T)
Y, --- Pr(a, * 0] 2 (TT). which proves the second part.
D.3 Proof of Lemma D.1
We concentrate on adapting the proof of Lemma C.2 into the partial information feedback setting. To start with, we suppose that the conditions given in Lemma 4.1 hold. In fact, since the failure probability is only (1/TT), and the sum is upper bounded by OTT), therefore the failure case only contributes (11) to the total expectation.
Now, recall the following definitions:
P =
Σ
(u(0) (R(P,
- (di(0,a)-
-0i,)))))))))) (0))a)
oEA,aEa!
Q= E30 1- Σ (0,
AEO
aEA-
Ey, = (u))) (0)) & D).
E,,t = [l(((()) - -,(7)) S DD,
and by (13 and
have
E P. Pr(-Eu,] + Pr(-Ec.].
E[Q1] < Pr(-E Pr[-Ev,1]
Now, the bound on Pr[-Eu. inherits the analysis in the proof of Lemma C.2 as partial information feedback does not affect the learning of the request distribution. That is,
Pr(-Eu,1] Pr[])(u(0) (.(0))eeell> D $ 2kexp 222 1))
For Pr(--v,d,, when t (log T), it is obviously bounded by 1. By Lemma t < C. T, by Weissman et al. [41] we have
4.1 when O(log 7) <
Pr|-Ec,] = Pr(l((((7) ee(r)) > D] (2) exp
2 log
27

---

Further, when t > C. T, we correspondingly derive
D²
Pr|-E,,11 < (2!T) - exp
Putting the above together, we achieve that
E
Pt
E
Σ Q1
<
2k exp (-2D² - 1)) + (log
C.T
(tC
T
D2C, 1)
(2 - -2)
Σ exp
Σ exp
2logT
O T)
t=C,T++1
k
+ Oloog + (211-2) (
TI- (- (-O(D"//ogg)) +exp(-O(T))
(1)
D2
A: + log T
0
This finishes the proof.
D.4 Proof of Lemma
D.2
when we prove Lemma C.2 we only consider the case when the conditions in Lemma 4.1 establish, the contribution of the failure cases the expectation-sum is O(1). We now bound E T.] in the good case when the sample accessing frequency under partial information feedback is guaranteed. Specifically, as predefined in the proof of Lemma C.2] we only need to re-calculate the following, as the other terms remain unchanged with partial information:
As in Appendix D.3
Σ E Pr [[((((7) Pr((O)))
(1)) s -
42 T=
Here, 17 is specified in the definition of D,. is hard for us to directly compare 1) and C, in Lemma 4.1
Nevertheless, in any case, we know that when T is sufficiently large, Y+/(T - 11) (1 log T') for 2 n/.. Therefore, we have
Pr Pr[l(((T) Er (therlla S (1
2 exp (-
(-Ir
(T 1)
Hence,
Σ
Pr [1((7]) (+(7)) I (7--1) 11-1/112
t=nT+2 r=1T+1
Σ exp (-
(T 1)112
S 2[
Σ
(TT T)
11if +2 r=
(-
T1/2
( exp
0(1).
log
Combining with the other parts, Lemma D.2
proved.
E Missing Proofs in Section
E.1 Proof of Theorem 5.1
We will prove Theorem 5. in the following, and we inspired by the analysis in Chen et al. [16].
28

---

E.1.1 Another Regret Decomposition
Different from our analysis for the regular cases, in general circumstances, we introduce another regret decomposition method. The reason for involving such an alternative is that without the regularity assumptions, no longer have any local stability guarantee even when the estimates are close. Therefore, the decision given by Algorithm S does not coincides with optimal decision even when the distribution learning process converges well, and the corresponding analysis in Section 3 does not work out anymore.
We now present more general regret decomposition as follows:
Ta
FLL Rew = T(p(p)
r(0e, at, 7c)
J(p)) - IF
Σ (0, a)
(21)
LaEA1
To
(0, a R(O, a) )]
h
- +
((pi) - Eg
Σ
LaEA+
Here, (a) holds due to the Optimal Stopping Theorem, since To is stopping time. Meanwhile, by the decision process, we have for any 0e:
Earm [r(,,, ar, 7)) |0,]
Σ GEA+
(0,0
Further, (b) is by re-arrangement To give bound for (2T). we respectively analyze E To] the stopping time, and difference between the optimal accumulated rewards and the real ones.
E.1.2 Bounding the Stopping Time
To settle the stopping time, we first reduce to max Pt, 0) for < To. and then deals with these values. We notice that t < To as long as that B, 1. or P: 2 1/(T - ++ 1). Now, since for any E [n]]
p - pi (p) pp))* 2 p min max (pi Pc: 0),
have min P: 2 pmin max(pp Pt. 0). Therefore,
t To = p min max (p: Pt. 2 --t+1
max (p: Pt, 0) min T-t+1
(22)
Since E[To] 2 Pr[To for any t [T], only need to bound the following term for some certain l:
1
Pr max (p) Pr, < min
T T-1+1
We will further prove the following lemma in Appendix E.3 Lemma E.1. It holds for any t < T that
log T
log T
<0 n
Pr max (p1 Pt,
e
+
T T-1
(T - r) () -
T
T
With the light of Lemma
E.1 it is natural for us to compute
VlgTT. 4vt-2
2
log T
T-1
2 5
Vlg
t> (1 -T-E"
29

---

In fact, to derive the above, we notice that when
(
Σ Σr--rr--njı
2
4vt -
Σ (T 1)1/2 S
1)1/2 T
T --1
r=1
Meanwhile, when
(T 1)/2, we have
-
1, which leads
1-1
-T- - 1)1/2 -
8
Σ
2
-
(T 7)-1)3/2 S (=(++1)/2
T -
VT -
With these calculations, we come back the bound on B[T,), we notice that when T is sufficiently large and
T - O(log 7'), it holds that
log T
log T
1
+
(T V T
+ T = 0(1) S min.
Thus, we have
(2)
E T -o] = -BB[ool
S - Pr(To 2 T O [)] - O T))
(h) - T - 12-(1-11 (1-0
1 +
O(log 7)) Oloo T))
(23)
In the above, (a) is because E[To] > Pr[To 2 4/.6 Consequently, we finish the analysis of the stopping time in 21
/ for any fixed 4, and (b) is due to Lemma E.1
E.1.3 The Gap to the Optimal Reward
The part of 21 that are left consider is the following:
((p)) Es
Σ
(00,a))((0,a)
LaEA+
= -(((p))- ( Ho)) + (pp..Hh - Eg Σ
@1 R(0,))
(24)
LEEA
Note that the second difference term in (24) reflects the estimation error on distributions of the context and the external factor, which leads to the following result as to proved Appendix E.4 Lemma E.2. We have for 2
(
logT k 50 KV
IE Mp: H4)
Lgg
Σ LaEA+
5. (0(0,))((0.0))
1-1 T
Lemma E.2 induces an O(VTlog T' accumulated regret considering (4 when summing from f = 2 To < T. While for the first term in (24). our main thread here is to bound i(p, He) with J(p)). To fix the idea, we compare these two optimization problems:
J(pt) =
max d18xA+-1 +R_
Σ
u(0)@(0, a) Σ 7)0(())
DE
Σ
u(0))(0,a) Σ (0(0,a,)0(7)) S pr.
s.t.
At
Σ ((0,a) S1, V0E
aEA!
((0,a) 20, (0.0))xxA1
30

---

J(r, Ha) =
E T,(0)((0,0) a) Σ Er( a, 2)),()),
max
+ +R+
DEO,EEAT
s.t. Σ
Te(0)((0, a) E Ec(0,a,) S Pa.
DEA.EEA+
Σ (00,0) 51, V0E
aeAt
((0,a) 2 0, =0x
Now, conceptually, if there is 0 < t 1 such that for any (0, E
u()) Σ c(0, a, ))v(n) 2 me) (0) Σ ()(0)),))((1))
then for optimal solution of of (p:), that oe is feasible solution of the programming
[Pe. H4). Thus,
Σ (0)00) a) ar(0,a,7)6)
2 1/t
8EB,aEA+
(
Σ
u(0) a) Σ T(O, a, r)(())
0E0,aEA+
(m(((((()) (0)) ((((()) -erl))
= m))(p)) (1(((()) (0))ccell + [[(((t)) ,rr))erll1..
Here, since r(0, a, 7) S 1 and
for any (a) is expanded as (0)0 a) Σ (1()))(),,,))
(0, < (0).a)
Σ
Σ
u(0) Σ (()))((,,,))
OE0,aEA+
DE0
Σ
(Q(())
((0)) a) Σ ((())((0,a,1)
6EB,
Σ
(0)) a) (()))))-()))((00))))))
AEB,aEA+
< [I[u(()) - ( (0))eelll + [1(u(t) - (r(1))
Consequently,
J(p.) - J He)
$ 11m-mi (p))))((p))>) + m(((p))) J(p)) + ((((()) (.(0)) + [[(b()) - (r(r)) (25)
On top of this, key observation is that
J(pi) J(p.) < max (p) - -pi-- J(p.).
(26)
guin
In fact, when P1 S Pt. (26 is natural as ((p)) s (pt). Otherwise, let of be the optimal solution to the programming J(p)). Let i" be the index that minimizes of /pi"- We have pf pf" Evidently, we know that oं P. /Pf" is a feasible solution to the programming of (p:).. By the optimality of J (pt). we have
((pi) 2 ((p)), pf
which leads to
J(pi) - ((pi)-((p))+ S (1- pi
pt -p:."
max (pi pP). -(()). pmin
((p))
((p)) <
p
pr
31

---

Synthesizing the above two parts, 26 is proved.
As for E[[ma((p Pt: 0)], note that for any non-negative random variable X with upper bound
X and any positive ç. we have
X - { Pr[X S E] + ( - Pr[x =
- =
(27)
Notice that max (1: Pt, 0) is certainly upper bounded by we have
Therefore, as corollary Lemma
log T
log T
k +
0
k
2315 (T 1)/2:
T
[max (p1 Ps, 0)]
log
+ T
T
0
k
1> (T + 1)/2.
T
We almost finish the bound now except for determining in (25 which we hope is close to 1 as possible. Nevertheless, we leave the technical parts to Appendix E.5 which derives the following lemma on the total bound: Lemma E.3.
To Σ
J(pi)- -(p H.)) = o T + n).
Now, we sum the result in Lemma obtain that
E.2 from
= 2 to To, and plus the constant term for t = 1 to
To Σ
1)
E
J(p. H.)
Ep
Σ
(0 (()00))((0.0))
O Tog T).
LaE ++
Synthesizing Lemma
and
we derive Theorem 5.1
E.2
Proof of Theorem 5.2
The proof of this theorem follows the line of Theorem 5.1 and the only difference is to adopt Lemma 4. when considering the concentration of estimates. On this side, when t (log T', as the accumulated regret in this phase is bounded by Ollog On the other hand, the time range that & 2 ((T) is asymptotically identical the full information setting since the accessing frequency is a constant. We only need to consider the case that Oloog 7) I t S O(T), when we have
disregard the cases
log T k t 1-1
k T2
Pr [[u(()) - a,(())eell s -
(28)
log Vt
T
-((()) - - S -
[T)
Taking into the proof of Lemma H.T and then into the main body, should find sufficient large t such that
@
θ
T
log T
k
Σ
V(T - ()
log T
+k Σ
V (T ()
log T
+ V T
log T
7=0(T)
p min
T-L+1
and = T O(log T) still suffices. Therefore, ET Tul O(log T) also holds under partial
information feedback.
Nevertheless, for the counterpart of Lemma derive that
E.2 by 28 when sum from -= 1 to To S T, we
@((0,a) a) ]]
E
M(pt H4) Ex-u
Σ
O(KVTTOoTT)
Laedt
32

---

At last, for J(pi) [pt. H4), we face the same degradation on the estimation accuracy, which leads
To
- -(pr, -(pr..))
E
Σ
OkkVTToog + n))
Therefore, Theorem 5.2 is achieved.
E.3 Proof of Lemma F.1
Now that we are going to bound max p1 Appendix C.5 when we prove Lemma C.3
Pr.0). Recall the definitions below which we give in
EaEat कī ((,))
Eanu EoEst (((
C Pt
No.
-
--t
By 16, we have
Pt - Ct M + NoC
Pr+l Pr.
T-1
Consequently,
Σ M + Σ CNO )
max(p: Pt) = max
< min M min Σ No.
For the second term, notice that each entry of (E N Jt is martingale with the absolute value of the 7-th increment bounded by 1/(T 7). Since
Σ
1
TT-
T-
by applying the Azuma Hoeffding inequality and a union bound, we achieve that
Pr
min
N C
2 2og T
S n
(29)
T - t
T
On the other hand, for the first term, when 1, it is apparent that min M S 1//TT 1). When
т 2 2, we have for any E [n]]
(T - (C-T)((M) (M
pz Equall
Σ
(1,
LREA+
Σ
To (1)3; (0,a) a) Σ (+(7)c
Σ
((0)5;(0, a) Σ (0,)))(0,0a)))
aEA
0E
Σ
(O) u(()) u(0)) a) Σ (.(1))((),,,))
aEA
Σ
a. Σ (0-(7)) (0,)
((7))
2 (f) a (0) oell: - [[(x(t) - 8 7<(7)))rll1.
In the above, (a) is because क; is feasible for H(p. H.). By Hoeffding's inequality and union bound, we have
log <
Pr [((u()) a. (e)))el & -ki
-
T
33

---

log T
r
Pr
[[((()) - ser) S -
T
Thus, suppose the above events hold for all s T with failure probability only O(1/T),
log T
k
Pr
min
M
0 T-1 (T- () - 1)
00
(30)
T
Combining
(29) and
30
we derive the lemma.
E.4
Proof of Lemma
We notice that
Jp.. H4)
E (,(0) Σ (00,).))0((7)
DEB,aEA+
and
Σ (0)0 (0.a) a) Σ ((())(()an))---)
Σ
(0,)0 Σ v())r(0,a.7)
aEA,
0E0,EEA
E
(Q,(0) u(0)) a) Σ ((17)((),a,))
BEB,EAA
Σ (0)) a) ( (+)))(0,aa)))))
aE
$ Il(u(()) - 8e (e)) + [1(u(n) - (r(1)))
Thus.
[pr. H.) Eanil
Σ
(0,0,
< (l(u(0))a,())) - (,)0)eeelll + ((((7) - (c(7))
L
By Hoeffding's inequality and a union bound, we have
log T
k
Pr [[((()) - (0)) 2 |/
2(t 1)
T
log T
T
Pr [[((7)) ((()))e 1 2
1Fly
2(t 1)
T
Further, the difference we hope to analyze certainly upper bounded by 1. As result, with (27). we finish the proof.
E.5
Proof of Lemma
We come consider ((pi) -[pp, H.). As per the thread in the main body, we let
6, = [[(u(0) - ū. (o)) + [[(((7) - (((7)))erll,
mingge (1) 0)}
We now claim that for any ( A+ [n].
Tg (0) Σ c(( = (1 (() Σ d' (0,)))))))))
The above is obvious if (8, 0. c' a, 7) 0 holds for any y. When C(A, a) * then for any i [n).
i (0) Σ c'(0,a, u(0) Σ c'( (0, r)((7)
34

---

(ū,(0) u(0)) Σ (0, (,,,)))))))))) + u(0) Σ )((())))((())) -(7)) [1(((() x { Σ c0(0),,))0(7)
+ (1(((T) (r)))
This finish the explanation of the claim. Upon that, if we let f/ 1 1- S 1/((1+
derive that
0( Σ c(0 a, ()(()))()) i 1 oz (0) Σ 2)),())
S T)) Σ c(0,,a7)0t(1))
With respect to 25 and (26). we obtain that
J(pi) Tip. Ha)
(1-1 1/1 max (p1 1an-Pr pn.-Pr. pt:0)
S((p))
+ [[(u(0) (((0))e + -
- (er)
pula
= = (8. max (p1 Pc.
([(((()) -((u(())a,,(0))))) (,)0)) +1(((()) - (31)
piiin
As we have already shown in the main part that
2)
T
log
k ++n
+
+
2T
T
T T
T
E [max (p1 Pc. 0)]
log
k +
ky
+
1> + 1)/2
T
T
it suffices for to bound
(u() (.()))eeell [o)) (u)) (O)) B((,)) - (,(1))
On this side, as we have shown that
log T
h
Pr [(((()) (,))seellll 2 1
2(t 1)
T
log T
r
Pr
[[(())) (e(r)) 2 11/
2(t 1)
T
it is natural that
(u(()
E
T. (()))) - -1( (.(r))
log T
k T
< k
Thus, putting all the above into 31 and summing from to To T, have
(J(P)) (J(P)) Ton.Hi)
E
O(k T log + n).
This concludes the proof.
35

---

Details of Numerical Validations
Specifically, consider the following instance: There are two types of resources, three types of contexts, and two types of external factors. The unknown mass function of context and external factor are (u(01), (02), u(0s)) (0.3, 0.3, 0.4) and (v(11), v(12) (0.5, 0.5), respectively. The
resource consumption is represented by
T0. 1.17
2..1
1.9
CO =
1.8
2.2
(
0.8
1.2
1.2
0.8
0.9
1.1]
where ((0,,1,7))== =CC, 0 T for all (i.j).
The reward function is represented by
1.2
0.87
R
1.3
1.1
[0.7
0.9
where 10,,1,77) R for all i.j. Thus the underlying I.P
((p) = max 0.3 .1 + 0.36 + 0.32 13,
s.t. 0.3 + 0.6 22 + 0.4 S p
0.6 0.3 0.4
ppp
0 5 x 1, =
where x; - (0,) for all i 1,2,3, 3. For a degenerate instance, we set p = (1, 1.15) with the optimal solution
(1, 0.5, 1) For a non-degenerate problem instance, we set the average resources p = (1, 1) and the unique optimal solution x= 2/33,2/3, 1) Here relax the restriction that the consumption and reward are upper bounded by 1, as this condition can be met easily by scaling, with the regret accordingly scaling. Such relaxation is to make the LP form more
visually appealing.
G
Missing Details in Appendix A
G.1
The Density Estimator
We now present details on the kernel density estimator which we apply in Appendix A for approxi- mating continuous distributions, which comes from Wasserman 44)] We consider one-dimensional kernel function K such that
f K(x) dr 1;
(=' dz vi
||]| Xo.
Now, given ( indeppndent samples X1, the kernel density estimator is defined as
X5 from P and a positive number h called the bandwidth,
|| Xill2
(x(
K
hd
Furthermore, to satisfy Proposition A.1 should choose h =2 k1/(2+d)) log k when p E E(B, L) is the density of P on Rdd.
G.2 Proof of Theorem A.1
By 21). we know that
1)
FLL Rew J(p))
E T
Tol +
E
J(pz) E.
Σ
30 R(0,) R(0,
LaEA1
36

---

and we bound these terms in order. For the expected stopping time [[To), by the analysis in Section 5 our goal turns into bounding max(pı - Pt. which further by (T6) and (29). reduces to bound M With continuous randomness, we have for any E [n],
(T T) (M,))*
p - Eo
Σ (0,
LaEA+
(0,,a) a) S ((00,a,)))6(())))0)00))))
dEAt
Σ (,,,a)) a) J, [c000an)0())00000
GEA+
Σ (000a)) /, (000)anj((((( ((0) do
a+
(0,,a) c(00, -(
(()) d de
atA+
sup (0) --(0)] (())) [-((-
0
In the above, (a) is by the constraint feasibility of क7, and (b) is because EeEst (0. a) S 1 holds for any 0 E O. Further, by Proposition A.I we have for T = S2(1).
Pr sup lu(0) ū, (0) = e ( (vlog T(r 1)). 1) -1
1 T
Pr sup (0) E. (0)) < - Vlgg T(T - 1)a0-1 -1
x T
Thus, when t = [1)), we derive that with failure probability O(n/T), it holds that
[-1
(T - 1)an
(T 1)au-1
log T T-1
max (01 5p e T-1 + Vlog T
Σ
+
+
T -
7 T
r=)(1)
Further, for p E v),
v), when t S (T++ + 1)/2.
Σ
[-1
(T-1)ap 1)
2
t-1
(T 1) <
2(t 2)
T-T
T
a, (T - 1)
T=)(1)
T=2
and when / > (T 1)/2, we have
1- 11
1
2
1-ap
TT 1)0y-1
(T -
T -
Op
T T-1
1 Op
(=)
r=(f+1)/2
Thus, when / = T T= (2(1 2(1-max(122000))
T), we have
θ
1
+ log T
Σ
1-1
( (T- 1)00 (7-11)au1
(T- - 1)0001
+
log T T
--1 1
T T-
r=0(1)
mim - +++
which leads
E [T - Tol =0 (log 11g T).
37

---

This concludes the analysis of the stopping time. For the second part, By (24)
have
J(p)) - Es
Σ
((0,a)
LEEA+
(J(n ((pr,HHa)) ((..
35 (1.0))
Egg
Σ LaEAt
On the second difference term, similar to the proof of Lemma
E.
we have
Hp: Ho) - Ee
Σ
(0,,))
LaEAt
- - Σ (0,a) / r(0,, (0) - Σ (i(0,a) / ((0, ((0,), (0)))))))
GEA+
aE
2 sup /u(0) 0r (0) + sup (((()) (,())
Thus, when t (2)1), by taking 1/"T in Proposition A.l and 27). arrive that
a) | =
-0 00 (VloR ((t- - 1)a--1 = (t- 1)a0-1) + 7
E
J(p. Ho) - Ep
Σ
L
We now focus on ((pi) Tp: H.). We let
8, sup, (=(0) m,( + sup, (((()) - b((7)
minego (mniee))eee_(mnmunn(((( > 0}}
We prove that
0,) / df S
/ d' (00)
holds for any (0, a, i) tuple, which is obvious if c0 7, is almost surely zero with respect to Otherwise, we observe that
nc(0) / e' c' a, ()6(7) u(0) / ( ((,,)))0(1)d
(ū) - u(0)) / c'(0, a, 7)0 dr + u(0) / ((0()))) - v(7)) dr
sup (u(0) - (0) + sup (u(n) 8,(7))
8
< (00 /
d7.
and thus, with = 1 - 6, 111(11 dz), we derive that
(()) / (100,,,)u(11 ((0)))))0(7)d7 1+ (n) mm
c' (((0,a))76()))
s n / é' c(0,,,))
This proves the above inequality. Thus, for an optimal solution oं of J(p)), we see that of is feasible solution of the programming J(p.. He). Thus, we notice that
p(pr, H4) 2 ne J. Σ (7(0,a) / (1)
aEAt
38

---

n ! E (5(0,a) / r(0, a,, ())())((() dy
aEAt
n (sup [(0) ū0) + sup (((()) (c()))
0 mpi( - (sup lu(0) Te(0)) + sup [(({7) (x))))
With respect to 26 we obtain that
(P1) [pp. Ha)
{((p))
( (1- m7
max (p1 - -..PP..). p):
+ sup lu(0) (i) + sup (((>) (n(l
pmin
max (p) Pt:0) + sup (u(0) [,( sup (((()) (r
J(1))
6z +
pmin
Now, when = (11), we have
E
sup u(0) - [.,(
0
Vlog T(t 11)a + T
0
E
sup (o(?) [b( = 0
VVog T(1 -1-1)a0-1 1)a0-1 + T
By the previous reasoning max(p1 Pt, 0), obtain that when / 12(1),
[max((p - -P,,
(T- 1)a
(1-1)a--1
log T
< T T-1 + Mog T
Σ
+ 1
T
T T-
T
(=)(
Therefore, summing from 1= to To S T, we achieve that
To
((()))-((pp)) - (W)) = =0 - + +T + TTo) (To.)//og. log + m)
E
Σ
Combining with previous bounds on E - To] and the estimation errors, we derive the theorem.
G.3 Proof of Theorem A.2
Similar to the proof of Theorem 5.2 we concentrate on re-bounding the three terms under partial information feedback, respectively E[T-To], To), J(p. H:)- |Eue Φi (0, a) a(,, a)], and (pi)-
(pt. He). As for E -T), with Lemma 4.1 argue here that the main term in bounding max(p1 - Pc, 0) when = ((T) becomes
θ ViogT
Σ
(T - 1)a--1
@(T)
Σ
((r -
+
Σ
1-
(r (r-1)0o 1)00-1
))
T-T
T-T 7
T T-T
(1)
7=0(1)
r=0(2)
Consequently, when t is close to T, we have with failure probability O(1/T),
max P1 Pt,
-
T-1 Vlog T (TT (T- + (T 1)-1/) + (T' -))00- 10g 3/2
1
This leads
E[T - Tg] = =0 -10g 20.00222///22222// 1((2-2c0)) T).
39

---

For the estimation error term J(p. H.) - Ee EelEreAt (0, a)}, when ((1) - t S ( the bound now becomes
Mp, H.) - Eg
Σ LaEA+
क (0,,))(((..)
=0 ( VlogT(t 1)au + log
1
T (t 1)au-1 + T 3/2 -
At last, for J(p)) - [pt. He., we derive that
To
= 0 @Vllog? (T T1/2) log3/2-an T Tas +n)
E
max (p: Pc. 0)
To
E
sup lu(0) (0)
0 (VoogT. .Tam)
To
E
sup (u(7) - mc(T))
= =0 (1og)// 3/2-as T. TTo.)
Putting together, obtain that
(J(PI) ( -Tpr J(pr Hal) Hai) = =0 -Vioog (ras + T2/2) + 3/g3/2 aor ga. + +n)
E
Synthesizing all the above, we finish the proof of the theorem.
40

---

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

---

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

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The paper provides open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httpss:/miis.cce)
abblic/guides//ooeeuuuiiiss
www.sssiynnooooiooooooiooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ Stltps.ccc/ubbiccc//e
wtteeee//ooSSSeeesesseeee ssisssssiiipyyy 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 proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper specifies all the training and test details necessary to understand the results.
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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The paper reports error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
43

---

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 caleulating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of 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 are out range (e.g. negative emror 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 in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The paper provides sufficient information the computer resources needed to reproduce the experiments. All experiments can be conducted on a personal computer.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as 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 it 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://neurips..c http:////eeeeeecccc////////iiiee inn
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses both potential positive socictal impacts and negative societal impacts of the work performed.
Guidelines:
44

---

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 societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used 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 unintentional) misuse of the technology.
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 no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
45

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information 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 of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
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 crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country 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 crowdsourcing 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.
46

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
47


Reviews:
[{"review_id": "UbTDHMoY4X", "reviewer": "Reviewer_c8Hc", "summary": "This paper considers a new contextual decision-making model with knapsack constraints, which is highly related to the CBwK setting but features a different information feedback structure. Under this model, the authors nearly characterize the conditions under which $\\tilde{O}(1)$ regret can be achieved based on the degeneracy of the optimal solution of the fluid LP. Specifically, the re-solving heuristic is proposed to achieve $\\tilde{O}(1)$ regret under these conditions. Additionally, the $\\tilde{O}(\\sqrt{T})$ worst-case regret of the algorithm is provided.", "questions": "Both the feedback structure and the degeneracy-based condition for breaking $O(\\sqrt{T})$ regret make me think it is similar to the corresponding results in online linear programming [1,2,3]. While several structures are different (e.g., the context and the action set), are there any high-level heuristics that can explain such similarity? Moreover, [3] provides a condition for breaking $O(\\sqrt{T})$ regret beyond degeneracy. Can the idea in [3] be utilized in this setting to further characterize the conditions for breaking $O(\\sqrt{T})$ regret in this paper?\n\n\n\nRef:\n\n[1] Arlotto A, Gurvich I. Uniformly bounded regret in the multisecretary problem[J]. Stochastic Systems, 2019, 9(3): 231-260.\n\n[2] Bray R L. Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations[J]. arXiv preprint arXiv:1912.08917, 2019.\n\n[3] Jiang J, Ma W, Zhang J. Degeneracy is ok: Logarithmic regret for network revenue management with indiscrete distributions[J]. arXiv preprint arXiv:2210.07996, 2022.", "limitations": "N.A.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The model considered in the paper is quite general to cover several interesting problems.\n\n2. The results provided under the proposed model is relative sharp and complete.", "weaknesses": "1. The assumption on the randomness is stronger than those made in the contextual decision-making literature.\n\n2. While I understand that this paper considers a new setting and that the works in CBwK are the most related, it is acceptable that the authors mainly compare their results with those in CBwK. However, since the information feedback assumption in this paper is strictly stronger than in CBwK, I suggest the authors provide more comments regarding this difference to make the comparison fairer.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your kind comments and suggestions. \nWe now respond to your concerns and questions. \n\n**Stronger assumptions on the randomness.**  \nIndeed, our model requires an explicit form of randomness $\\gamma$ for the external factor. \nThis explicit model is crucial for us in this work to learn its distribution. \nWe will work on to see how to relax this assumption. \n\n**Comparison with CBwK.**  \nDue to the space limit, we have to delay the comparison between our model and CBwK to Appendix A, Lines 469--498. \nThere, we emphasize the difference between our results and results in CBwK, as well as the difference in feedback models. \nIn short, although our full/partial feedback models are stronger than the bandit feedback model, techniques in the literature for CBwK would require assumptions on the problem structure, e.g., linear dependence between expected rewards/cost vectors and the action (linear CBwK). \nWith these model assumptions, existing regression modules can help to address the problem of learning unknown parameters. \nIn our work, we do not take any of these simplifying assumptions and no learning oracles (Line 492); therefore, we would require a stronger feedback model to ensure the efficient learning of randomness. \n\nIn fact, we give a novel, important, and non-trivial analysis for the learning guarantee under partial feedback (Lemma 4.1), which is crucial for our regret results in this model. \nLemma 4.1 itself could also be of independent interest. \n\n**Degeneracy-based conditions, and other heuristics.**  \nThis is a very interesting topic. \nIn general, we believe that non-degeneracy is a critical factor to an $O(\\sqrt{T})$ regret bound in the CDMK/CDwK problems, at least for the re-solving technique we use in this work (e.g., Jasin and Kumar (2012)), as pointed out by Bumpensanti and Wang (2020). \n\nTo break the $O(\\sqrt{T})$ regret without the degeneracy assumption, we should explore other heuristics that are already discovered in the online linear programming problem, as you mentioned, and see whether other conditions could be characterized for breaking the $O(\\sqrt{T})$ regret. \nDespite this, our work is an important first trial of extending the re-solving technique to the CDMK problem. \n \n**Reference:**  \nJasin, S., & Kumar, S. (2012). A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Mathematics of Operations Research, 37(2), 313-345.  \nBumpensanti, P., & Wang, H. (2020). A re-solving heuristic with uniformly bounded loss for network revenue management. Management Science, 66(7), 2993-3009.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "J9giGKLHob", "reviewer": "Reviewer_m7z3", "summary": "This paper studies an online contextual optimization problem with resource constraints. The paper provides a sufficient condition (worst case condition) under which the fundamental limit on the regret bound is reached. The paper further provides an algorithm that can achieve \\tilde O(1) regret when the worst case condition does not hold. Numerical results are also provided to validate the theory.", "questions": "1. It is slightly confusing to use $\\rho^i$ to denote the $i$th entry since it also means exponent.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written. The relation between the worst case condition and the degeneracy of linear constraints is novel and inspiring. The intuition behind the proposed algorithm is clearly explained.", "weaknesses": "1.  Is $T$ known beforehand? If $T$ is unknown, how to compute the leftover budget $\\rho_t$? If $T$ is known, how to design an algorithm with unknown $T$?\n\n2. What's the difference between Rew and V^{on}?\n\n3. if there is $\\rho^i$ amount of resources per stage, why does the problem formulation only respect the resource constraint at stage $T$, instead of considering resource constraint at every stage $t$, i.e. total resources available to be used in stages $t$ <= $\\rho^i t$ for all $t\\geq T$?\n\n4. In the simulation, how does the proposed algorithm compare with the existing algorithms proposed for this problem?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for appreciating our work. \nWe will now answer your questions. \n\n**Known $T$.**  \n$T$ is known beforehand in this work, which is a common assumption in the literature, as supposed by the survey of Balseiro, Besbes, and Pizarro (2023). \nWe have not yet considered the problem of unknown $T$, which is certainly an important future direction. \n\n**$Rew$ and $V^{\\mathrm{ON}}$.**  \n$Rew$ is the expected total reward of *our algorithm*, while $V^{\\mathrm{ON}}$ is the expected total reward of the *optimal algorithm*.\n\n**Resource constraint for each stage.**  \nThis is a very interesting question. \nIn practice, only the global constraint is taken since we usually have an initial inventory of resources and only require that all the allocations should be done concerning this initial inventory. \nThus, a resource constraint for the later stages is unnecessary. \nConsidering resource constraints for every stage will make the problem much more difficult, as an algorithm cannot sufficiently explore all actions in the beginning stages. \nThis is certainly a future extension of our model. \n\n**Simulation.**  \nIn this work, we do not compare our algorithm with other existing algorithms mainly because CDMK with partial feedback is a new model. \nFurther, the regret results highly rely on instance-dependent factors for both existing algorithms and ours.\nAltogether, it is a bit unfair to conduct such a comparison under only some instances since they could be biased. \nOur simulation results mainly aim to justify our theoretical regret bounds, and we do see a match there. \n\n**Usage of $\\rho^i$.**  \nWe are sorry for causing such confusion. We will work on improving the notation. \n\n**Reference:**  \nBalseiro, S. R., Besbes, O., & Pizarro, D. (2023). Survey of dynamic resource-constrained reward collection problems: Unified model and analysis. Operations Research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FCbKpYbNta", "reviewer": "Reviewer_TgME", "summary": "This paper studies contextual decision making with Knapsack constraints assuming that the requests and the contexts follows some distributions. It studies the full information setting when each context is revealed after the decision is made and the partial information setting when the context is revealed only when a non-null decision is taken. The paper provides regret bounds under various settings.", "questions": "1. In the motivating example, it is unclear why for the dynamic bidding problem, the highest competing bid would follow a distribution. It seems to be more adversarially chosen. \n2. In the partial information setting, since choosing a null action will not be able to observe the context, does the $\\hat v_t(\\gamma)$ still provide an unbiased empirical estimator of the distribution of $\\gamma$? Since the decision depends on previous observed contexts, observing the next context or not depends on the previous observations. Thus $\\hat v_t(\\gamma)$ does not seem to be an unbiased empirical estimator anymore. What are the techniques used to address such bias? \n3. Since the context $\\gamma$ is revealed after the decision is made, is it worthy to take more non-null decisions in the early stages and try to learn the distribution faster?\n4. The relationship of the proposed problem comparing to the NRM problem is not explicitly discussed. Please compare the similarities and differences, particularly regarding the measurements. \n5. The linear programming is only solvable when $\\theta$ and $a$ admit finite support. What if they are continuous variables? Continuous variables are quite common in both inventory and bidding situation. \n\nI am happy to raise the score if these issues are well addressed.", "limitations": "Comparison to continuous optimization methods in NRM problems are not discussed.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Under the unique non degenerate LP assumption, the paper has provided regret bounds that are better than the worst cases in both full information and partial information setting, which is novel. It further shows that without this assumption, the regret bound is indeed $O(\\sqrt{T})$ that matches the lower bounds. The paper further provides regret bounds when the request and context are continuously distributed. It greatly enhances the understanding of the problem.", "weaknesses": "1. I found the presentation can be further improved, particularly about why the unique non-degenerate solution can greatly improve the regret bound and provide a proof sketch. This is the main contribution of the work yet the intuition is not fully clear. \n2. See questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and questions. We will now answer them. \n\n**Why uniqueness and non-degeneracy is important.**  \nThe corresponding discussion is located in *Lines 233--243* in our paper. \nIn short words, under this assumption (Assumption 3.1), we have the stability property that if all estimated parameters in $\\hat{J}(\\rho_t, \\mathcal{H}_t)$ are not far away from the true parameters, then $\\hat{J}(\\rho_t, \\mathcal{H}_t)$ and $J(\\rho_1)$ have the same set of basic variables and binding constraints, respectively. \nThis property is given in Lemma D.2 in the appendix and plays a crucial role in our analysis. \nWe will work on to make that clearer. \n\n**Stochastic highest competing bids in the dynamic bidding problem.**  \nThis is a good question. \nSuppose we stand in the view of a single bidder and consider a large auction market.\nIn this scenario, even if each of the other bidders bid strategically, their highest bid can still be regarded as being stochastic due to the large market.\nThis is sometimes referred to as the \"mean-field approximation\" in economics.\nIn the related literature, such a stochastic assumption on the highest competing bids is also widely taken, for example, Balseiro and Gur (2019), Feng, Padmanabhan, and Wang (2023), and Chen et al. (2024).\n\n**Unbiased estimation of $\\hat{v}_t$.**  \nThis is an important question. \nIn fact, $\\hat{\\mathcal{V}}_t$ is still an unbiased estimation of $\\mathcal{V}$ even under partial feedback. \nThe reasoning here is that $\\gamma_t$ is drawn independently with the context $\\theta_t$, and the action $a_t$ is also chosen before $\\gamma_t$ is revealed. \nThus, we have that $\\Pr[\\gamma_t | \\theta_t, a_t] = \\Pr[\\gamma_t]$, or that $\\gamma_t$ is independent with $(\\theta_t, a_t)$.\nThis guarantees that $\\hat{\\mathcal{V}}_t$ is unbiased. \n\n**More non-null decisions in the beginning.**  \nThis is a very good thought experiment. \nHowever, although it seems delightful to make more non-null decisions initially, we have to ensure that we are not \"exploring\" too much or that we could be too far from the optimal and may not \"rescue back\" in the later time slots. \nIn fact, our key ingredient for the proof is Lemma 4.1, which indicates that under the re-solving heuristic, we explore in every $O(\\log T)$ rounds and have an $O(1)$ overall exploring frequency in the beginning.\n(Please also refer to Figure 1.)\nThis is already asymptotically much efficient for getting samples. \nYou raised a very important question, and we will see if we can do better by slightly modifying the algorithm and obtaining a better regret bound. \n\n**Relationship between CDMK and NRM.**  \nDue to the space limit, we defer the discussion to Appendix A, Lines 499--512. \nPut simply, NRM is a sub-problem of our CDMK problem with no external factors and only a binary action space $A = \\{0, 1\\}$, where $0$ is the null action and $1$ is the \"accept\" action. \nTherefore, our CDMK is generally \"harder\" than the NRM problem. \nAs for the measurements, our fluid benchmark is identical to the deterministic LP (DLP) benchmark introduced in classical works on NRM, e.g., Jasin and Kumar (2012) and Balseiro, Besbes, and Pizarro (2023). \nThus, we believe that our work is built on a strong literature basis. \n\n**Continuous variables.**  \nThis is also an important question. \nIn Appendix B, we suppose that there is an outside oracle that can help us solve the programming in each round for continuous variables. \nYet, this could be hard in practice if we are not facing a convex continuous programming. \nRelated works in the literature would mostly suppose a finite context and external factor set or similarly suppose an oracle for continuous variables, e.g., Balseiro, Besbes, and Pizarro (2023). \nAlso, in real-life scenarios, e.g., inventory or bidding, even though the action space is large, it is still finite since the allocation/bid is usually required to be a multiple of a minimum unit. \n\n**Reference:**  \nBalseiro, S. R., & Gur, Y. (2019). Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, 65(9), 3952-3968.  \nFeng, Z., Padmanabhan, S., & Wang, D. (2023, April). Online Bidding Algorithms for Return-on-Spend Constrained Advertisers. In Proceedings of the ACM Web Conference 2023 (pp. 3550-3560).  \nChen, Z., Wang, C., Wang, Q., Pan, Y., Shi, Z., Cai, Z., ... & Deng, X. (2024, March). Dynamic budget throttling in repeated second-price auctions. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 9, pp. 9598-9606).  \nJasin, S., & Kumar, S. (2012). A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Mathematics of Operations Research, 37(2), 313-345.  \nBalseiro, S. R., Besbes, O., & Pizarro, D. (2023). Survey of dynamic resource-constrained reward collection problems: Unified model and analysis. Operations Research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pWCELAxndC", "reviewer": "Reviewer_ZSDZ", "summary": "This paper considers the problem of dynamic decision making with resource constraints. They show that under certain conditions they can achieve O(1) regret with respect to the time horizon. However, I am not sure whether this is true regret (i.e. with respect to the best policy in hindsight) or regret with respect to a number $V^{FL}$. My final score is highly dependent on the author’s response to this question.", "questions": "Can you give examples to show that the non-degeneracy of $J(\\rho_1)$ is common.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I am wondering if in Theorem 3.1 the display equation should say $V^{ON}$ instead of $V^{FL}$. If it is indeed $V^{FL}$ then your goal is only comparing to $V^{FL}$ so what is the point of the “worst case” discussion comparing $V^{FL}$ to $V^{ON}$? If is is meant to be $V^{ON}$ in Theorem 3.1 then I think that this is an interesting result. However, if it is indeed $V^{FL}$ then the result is much weaker as you have not shown any improvement over $O(\\sqrt{T})$ with respect to the optimal policy. My final score will be highly dependent on your answer to this question.", "weaknesses": "If Theorem 3.1 is written correctly then please see the “strengths” section for a major weakness.\n\nIn Theorem 3.1 I believe that the O(1) must be hiding problem-dependent constants. I don’t just mean constants like the sizes of the sets but constants that are based on the linear program itself. I.e. are there some non-degenerate linear programs in which the hidden constant factor blows up arbitrarily high - e.g. when we limit to degeneracy. This is the same concept as in stochastic bandits: the $O(Kln(T))$ factor hides the gap between the mean rewards of the optimal and second-optimal arms - which limits to infinity as the gap limits to zero (although the regret actually never goes above $O(\\sqrt{KT})$). You should certainly include any problem-dependent constants in your bound (although I do understand they may be complex to bound - so at least point out that they exist (if they do)).\n\nLine 226 (and line 78): You say that any LP can easily escape from degeneracy. Doe this mean that you can improve on the sqrt{T} bound when $J(\\rho_1)$ is degenerate? Otherwise this statement (which appears twice) is highly misleading.\n\nLine 171: Theorem 2.1 does not show an \\Omega(\\sqrt{T}) regret lower bound when you define the regret relative to $V^{FL}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and comments.\nWe now respond to your concerns and questions. \n\n**Theorem 3.1.**  \nIt is *completely correct* for you to say that in the equation of Theorem 3.1, $V^{\\mathrm{FL}}$ could be replaced by $V^{\\mathrm{ON}}$. \nIn other words, we are talking about the *true regret*, and we indeed obtain an $O(1)$ true regret under Assumption 3.1. \nThis is also true for *all* our regret results, including Theorems 4.1, 5.1, 5.2, B.1, and B.2. \nWe hope that our claim here could eliminate your concerns. \n\nNevertheless, we should notice that from Proposition 2.1, we know that $V^{\\mathrm{FL}} \\geq V^{\\mathrm{ON}}$, and of course, we have $V^{\\mathrm{ON}} \\geq Rew$. \nThus, the formulae we write in this paper are, in fact, stronger in the sense that if $V^{\\mathrm{FL}} - Rew = O(f(T))$, then $V^{\\mathrm{ON}} - Rew = O(f(T))$ also holds. \nFor Theorem 2.1, we only want to know how far $V^{\\mathrm{FL}}$ could be above $V^{\\mathrm{ON}}$ at worst and the corresponding conditions so as to make our work more complete. \n\n**Problem-dependent constants in Theorem 3.1.**  \nIt is true that our regret bound consists of problem-dependent variables, as we discussed in *Lines 233--258*. \nMore specifically, as you mentioned, we have a constant $D$ in the bound based on the linear program $J(\\rho_1)$. \nThis constant represents the minimum $L_\\infty$ distance between the LP $J(\\rho_1)$ and any LP with multiple optimal solutions or a degenerate optimal solution (Lines 237--238).\nWhen our CDMK problem degenerates to stochastic decision-making by removing the context and resource constraints, $D$ is precisely *half the gap between the mean rewards of the best and second-best arm*. \nThus, $D$ resembles the reward-gap-like parameter in the multi-armed bandit literature (Lines 252--253).\nAnd our bound goes quadratically with $1/D$ (Line 258, with a typo, we will correct that.). \nWe will work on to make our arguments clearer. \n\n**Escaping from degeneracy.**  \nIn fact, we are not saying that we can improve the $O(\\sqrt{T})$ regret under degeneracy. \nWe mean that in practice, we can prevent the real-world problem from $J(\\rho_1)$ being degenerate by minorly changing the resource constraints, e.g., neglecting some of the resources. \nWe will show in the later response that non-degeneracy for $J(\\rho_1)$ is common. \nWe will clarify this part, of course, to eliminate any misleading information. Thanks a lot for pointing that out. \n\n**Regret lower-bound.**  \nYou are correct. \nWe will surely clarify these arguments by clearly differentiating the \"true regret\" and the regret we define in this work's main body.\n\n**Non-degeneracy for $J(\\rho_1)$ is common.**  \nWe simplify the example that we use in our numeric validations (Appendix G) by disregarding the third context, renormalizing, and letting the first resource constraint be $0.75$ and the second be $y$. Then the LP $J(\\rho_1)$ is now maximizing $0.3x_1 + 0.36x_2$, under the constraint that $0.3x_1 + 0.6x_2 \\leq 0.75$, $0.6x_1 + 0.3x_2\\leq y$, and $0\\leq x_1, x_2\\leq 1$. \nThis LP always has a unique solution, and the *only* value $y > 0.6$ such that $J(\\rho_1)$ is degenerate is $y = 0.825$, with the degenerate solution being $(x_1, x_2) = (1, 0.75)$. \nThat is to say, if we suppose that $y$ is uniformly located between 0.6 and 1, for example, then $J(\\rho_1)$ is almost surely non-degenerate. \nI hope this can address your question, and this is the reason why we say that any LP can easily \"escape\" from being degenerate. \nNevertheless, we will correct the misleading sentences.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of maximizing the total reward under resource constraints in the online setting. The paper establishes an $\Omega(\sqrt{T})$ lower-bound on the worst-case regret. Under a non-degeneracy assumption (that helps avoid the worst-case scenario), the paper proposes an algorithm that achieves $O(1)$ regret in the full information setting, and $O(\log(T))$) regret in the partial information setting. 

The reviewers agree that the paper is well-written, and its contributions merit acceptance. After carefully reading the paper and the corresponding discussion, I tend to agree. Please incorporate the reviewers' feedback. In particular, addressing the following concerns will help strengthen the paper:
- Move the comparison to the CBwK from the Appendix to the main paper (response to Rev. c8Hc)
- Add a more detailed comparison to the papers (pointed by Rev. c8Hc) that break the $O(\sqrt{T})$ lower-bound without the non-degeneracy assumption.
- More intuition/explanation on why uniqueness and non-degeneracy help break the $O(\sqrt{T})$ lower-bound (response to Rev. TgME). 
- Move the comparison to NRM from Appendix A to the main paper  (response to Rev. TgME). 
- Include problem-dependent constants in the theorems, and explain their dependence (response to Rev. ZSDZ)
Decision: Accept (poster)