Contextual Decision-Making with Knapsacks Beyond the Worst Case

Authors: zhaohua  chen
rui  ai
mingwei  yang
yuqi  pan
chang  wang
xiaotie  deng
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 18:09:17

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.

Main paper: 
 introduction: 
 In online contextual decision-making problems with knapsack constraints (CDMK for short), an agent is required to make sequential decisions over a finite time horizon to maximize the accumulated reward under initial resource constraints [13, 14] . To be more specific, in each round t = 1, . . . , T , a request θ t and an external factor γ t are independently generated from two distributions, and only θ t is revealed to the agent. Based on the request, the agent should irrevocably choose an action a t , which results in a reward r(θ t , a t , γ t ) and a consumption vector c(θ t , a t , γ t ) of resources. The agent's target is to optimize the sum of rewards T t=1 r(θ t , a t , γ t ) before the resources are depleted. 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 it 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 θ t for each repository, the factory chooses the number of goods transported to it as action a t . However, the factory has randomized transportation costs for different locations and traffic conditions denoted by an external factor γ t for the t-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 [8, 9] ). In this circumstance, an advertiser acquires the value of the ad slot θ t at the start of each auction and chooses a bid a t accordingly. The agent's gain in this auction, as a consequence, is collaboratively determined by the value, the bid, and the highest competing bid γ t , and has a form of θ t 1(a t > γ t ). Additionally, the payment is a t 1(a t > γ t ) for the first-price auction and γ t 1(a t > γ t ) for the second-price auction, 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.The CDMK model can also capture other well-studied problems, including multi-secretary, online linear programming, online matching, etc., as discussed in Balseiro et al. [8] . Previous studies of the CDMK problem have shown that the worst-case regret is O( √ T ) when the initial resources are linearly proportional to the horizon length T [35, 23] . However, it is still unclear whether we can achieve a better regret guarantee for the CDMK problem beyond worst-case scenarios. In particular, can we design algorithms to obtain an o( √ T ) 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.This work makes three main contributions, summarized as follows.The fluid optimum can be Ω( √ T ) 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 a common choice [23, 34] . However, we demonstrate that when the fluid benchmark has a unique and degenerate solution, then an Ω( √ T ) gap is unavoidable between these two optima (cf. Theorem 2.1). While Han et al. [23] 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 [37] to the CDMK problem.An O(1) regret via re-solving under mild assumptions with full/partial information feedback. Since an O( √ T ) worst-case regret is already known [35] , we investigate how well an online algorithm can perform beyond worst cases by applying the re-solving heuristic in conjunction with distribution estimation techniques, as given in Algorithm 1. This method has been considered in the problems Table 1 : A summary of our algorithmic results on Algorithm 1. Constants are omitted. 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 be made according to the request. To avoid worst cases, we explicitly suppose that the fluid problem has a unique and non-degenerate solution (cf. Assumption 3.1). This assumption is mild in three aspects: (1) it captures almost all CDMK problem instances, as slightly perturbing any LP can help it satisfy the unique optimality and non-degeneracy conditions; (2) it is less restrictive than the assumptions given in Sankararaman and Slivkins [31] , which require that there are at most two resources; and (3) it is almost necessary for an o( √ T ) regret bound to be established by Theorem 2.1, when using the fluid optimum as the benchmark. Under the assumption, our main results show that the re-solving heuristic reaches an O(1) regret with full information (cf. Theorem 3.1) and an O(log T ) regret with partial information (cf. Theorem 4.1). To our knowledge, these are the first O(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 1.1, if the factory can learn the road condition via map services, it 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 non-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 a 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 a specific (e.g., linear) relationship between the conditional expected reward-consumption pair and the request [3, 31, 23, 35] , whereas our results do not impose any underlying distribution structures, bypassing realizability issues [23] . On this side, our information model is comparable to those in existing work.A near-optimal regret even in worst cases with full/partial information feedback and an extension to continuous randomness. We further explore how well our Algorithm 1 performs even in worst-case scenarios. With full information feedback, we show that an O( √ T log T ) regret is achieved (cf. Theorem 5.1). This bound is asymptotically equal to the state-of-the-art with this information model [23, 35] . Even with partial information, we can still guarantee a universal O( √ T log T ) regret (cf. Theorem 5.2), which is optimal up to a logarithmic factor. These results demonstrate the applicability and robustness of the re-solving heuristic in CDMK problems, regardless of some specific instances. For completeness, we extend our algorithm and analysis to the situation in which the distributions of request and external factor are continuous and derive corresponding regret results (cf. Theorems A.1 and A.2).We summarize our algorithmic results on Algorithm 1 in Table 1 .Contextual decision-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 are revealed to the agent at 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 to select the best probabilistic strategy within the policy set [7] , and Agrawal et al. [4] adopts this approach to achieve an O( √ T ) regret. This heuristic originates from the subject of contextual bandits [16, 2] , and requires a 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 a dual update method that reduces the CBwK problem to the online convex optimization (OCO) problem. In particular, some work [3, 31, 34, 29] 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 [1, 6, 33, 17] and combines them with OCO methods to achieve sub-linear regret.Apart from the above studies, some results [23, 35, 36] are not restricted to linear expectation functions. To deal with more general problems with bandit feedback, they plug model-reliable online regression methods [21, 20] 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 reward-consumption functions.In the CDMK literature, Liu and Grigas [29] 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)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 [41] . Some researches in this setting also assumes known request distributions [25, 5, 24, 18, 12, 27, 15, 10, 38, 11, 26] . These works show that the re-solving-based method can obtain a constant regret under certain non-degeneracy assumptions and can generally obtain a square-root regret [15] . Recently, the re-solving method is also extended to the general dynamic resourceconstrained reward collection problem in Balseiro et al. [8] , which assumes the knowledge of request and external factor distributions and achieves O(1) to O(log T ) regret for different action space cardinalities.We should mention that the re-solving technique, together with other methods, has also been adopted for the bandits with knapsacks (BwK) problem [22, 19, 41, 38, 28, 31] to achieve an O(log T ) regret under different assumptions. For example, an essential result by Sankararaman and Slivkins [31] achieves O(log T ) regret in BwK under the best-arm assumption and two resources. However, CDMK is 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 a layer of complexity to the re-solving method. 
preliminaries: 
 We consider an agent interacting with the environment for T rounds. There are n kinds of resources, with an average amount of ρ i for resource i in each round, resulting in a total of ρ i T amount of resource i. We suppose that 0 < ρ = ρ 1 = (ρ i ) i∈[n] ≤ 1 is independent of T , with a maximum entry of ρ max ≤ 1 and a minimum entry of ρ min > 0.At the beginning of each round t ≥ 1, the agent observes a request θ t ∈ Θ drawn i.i.d. from a distribution U and should choose an action a t from a set of actions A. Given the request θ t and the action a t , the agent receives a random reward r t ∈ [0, 1] and a consumption vector of resources c t ∈ [0, 1] n , both of which are related to an external factor γ t ∈ Γ drawn i.i.d. from a distribution V. In other words, there is a reward function r : Θ × A × Γ → [0, 1] and a consumption vector function c : Θ × A × Γ → [0, 1] n , such that r t = r(θ t , a t , γ t ) and c t = c(θ t , a t , γ t ). We suppose these two functions are pre-known to the agent. We further define R(θ, a) := E γ [r(θ, a, γ)], andC(θ, a) := E γ [c(θ, a, γ)].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 = |Θ| be the size of the request set. We denote the mass function of U and V by u(θ) and v(γ), 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-making 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(θ t , 0, γ t ) = 0 and c(θ t , 0, γ t ) = 0 for any (θ t , γ t ) ∈ Θ × Γ. We use A + := A \ {0} to denote the set of non-null actions and let m := |A + | be its size.We would like to discuss here the necessity of the null action, which is widely used in related works [7, 3, 4, 35] . An alternative common choice for the null action is the so-called "early stop when resource exhausted" [31] in the BwK problem with no contexts. In reality, when the agent faces some "bad" contexts, a better choice is not "entering the market" to avoid, for example, small rewards but large consumption. As a comparison, struggling to come up 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 Ω(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-anticipating strategies Π. In particular, let H t be the history the agent could access at the start of round t. Then, for any non-anticipating strategy π ∈ Π, a t should depend only on (θ t , H t ), that is, a t = a π t (θ t , H t ). For abbreviation, we write a π t = a π t (θ t , H t ) when there is no confusion. Therefore, we can define the agent's optimization problem as below:V ON := max π∈Π E θ∼U T ,γ∼V T T t=1 r(θt, a π t , γt) , s.t. T t=1 c(θt, a π t , γt) ≤ ρT, ∀θ ∈ Θ T , γ ∈ Γ T .The fluid benchmark. In 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:V FL := T • max φ:Θ×A + →R E θ∼U   a∈A + R(θ, a)φ(θ, a)   , s.t. E θ∼U   a∈A + C(θ, a)φ(θ, a)   ≤ ρ; a∈A + φ(θ, a) ≤ 1, ∀θ ∈ Θ; φ(θ, a) ≥ 0, ∀(θ, a) ∈ Θ × A + .For a better understanding, V FL reflects the maximum expected total rewards an agent can win when a static strategy is adopted and the resource constraints are only to be satisfied in expectation. Therefore, this optimization problem is a linear program in which the decision variable φ(θ, a) represents the probability that the agent chooses action a upon seeing request θ. It is a well-known result that V FL gives an upper bound on V ON . Proposition 2.1 (Balseiro et al. [8] ). V FL ≥ V ON .Thus, we evaluate the performance of a non-anticipating strategy π by comparing its expected accumulated reward Rew π with the fluid benchmark V FL , which is a common choice in literature [34, 23] . However, we prove that such a benchmark choice may lead to a Ω( √ T ) gap as long as V FL is degenerate. Theorem 2.1 (Worst-case gap). When V FL has a unique and degenerate optimal solution, V FL -V ON = Ω( √ T ).Despite the worst-case lower bound, we prove in this work that for any CDMK instance in which V FL has a unique non-degenerate optimal solution (cf. Assumption 3.1), we can obtain an O(1) gap compared to the fluid benchmark. Thus, it is still a good choice in most cases.Information feedback model. In this work, we consider two types of information feedback models, with increasing difficulty obtaining a sample of the external factor γ.• [Full information feedback.] The agent is able to observe γ t at the end of each round t.• [Partial information feedback.] The agent can observe γ t at the end of round t only if a t = 0.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 a = 0. Thereby, a 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 1.1 and 1.2, as we have discussed in the introduction. 
the re-solving heuristic: 
 In this work, we introduce the re-solving heuristic to the CDMK problem. The resulting algorithm is presented in Algorithm 1.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 κ ∈ [0, 1] n , we define J(κ) as the following optimization problem:J(κ) := max φ:Θ×A + →R E θ∼U   a∈A + R(θ, a)φ(θ, a)   , s.t. E θ∼U   a∈A + C(θ, a)φ(θ, a)   ≤ κ; a∈A + φ(θ, a) ≤ 1, ∀θ ∈ Θ; φ(θ, a) ≥ 0, ∀(θ, a) ∈ Θ × A + .Evidently, we haveV FL = T • J(ρ) = T • J(ρ 1) by definition. Intuitively, in each round t, the best fluid choice of the agent is given by the optimal solution φ * t of LP J(ρ t ), where ρ t is the average budget of the remaining rounds, including round t. Nevertheless, since full knowledge of the exact distributions U and V is lacking, the agent can only solve an estimated programming J(ρ t , H t ) as outlined in Algorithm 1, with the following realization:J(ρt, Ht) := max φ:Θ×A + →R E θ∼ U t   a∈A + E γ∼ V t [r(θ, a, γ)] φ(θ, a)   , s.t. E U t   a∈A + E V t [c(θ, a, γ)] φ(θ, a)   ≤ ρt; a∈A + φ(θ, a) ≤ 1, ∀θ ∈ Θ; φ(θ, a) ≥ 0, ∀(θ, a) ∈ Θ × A + .Here, U t and V t represent the empirical distribution of θ and γ, respectively, according to the sample history given by H t . Specifically, let I t be the set of rounds that the agent accesses the external factor. The mass functions of these two estimated distributions are standard as follows: u t (θ) := #[θ appears in previous t- It is worth noting that the estimated distribution of θ, U t , is always based on t -1 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 γ, V t , is estimated from |I t | independent samples. With full information feedback, |I t | = t -1; whereas with partial information feedback, |I t | ≤ t -1 equals the number of times the agent chooses an action a = 0 before round t. For brevity, for the estimated programming, we write C t (θ, a):= E γ∼ Vt [c(θ, a, γ)] and R t (θ, a) := E γ∼ Vt [r(θ, a, γ)].As per Algorithm 1, the agent's decision mode in round t is given by the optimal solution φ * t of programming J(ρ t , H t ). The algorithm stops when the resources are near depletion, that is, B i < 1 for some resource i ∈ [n], and we use T 0 to denote the stopping time of Algorithm 1, i.e., T 0 := min{T, min{t : ∃i ∈ [n], B i t+1 < 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(ρ 1 ) is unique and non-degenerate.As pointed out by Bumpensanti and Wang [12] , uniqueness and non-degeneracy are a critical factor for an o( √ T ) regret bound to hold in the CDMK problem, at least for the frequent re-solving technique we use in this work [25] . Intuitively, if J(ρ 1 ) is degenerate, then with any minor error on the estimation, the optimal solution to J(ρ t , H t ) can have a major different landscape with the optimal solution to J(ρ 1 ) in the sense of basic variables and binding constraints, and this will lead to an O( √ T ) accumulated regret. For completeness, we formally define the above concepts. Definition 3.1. A context-action pair (θ, a) is a basic variable for J(ρ 1 ) if φ * 1 (θ, a) > 0, or else, it is a non-basic variable. Similarly, define basic/non-basic variables forJ(ρ t , H t ). Definition 3.2. i ∈ [n] is a binding constraint for J(ρ 1 ) if θ∈Θ,a∈A + u(θ)C i (θ, a)φ * 1 (θ, a) = ρ i 1 ,or else it is a non-binding constraint. We let S := {i is a binding constraint for J(ρ 1 )}, T = [n] \ S, and we use κ| S or κ| T to define the sub-vector of κ confined on S or T , respectively. Further, θ ∈ Θ is a binding constraint for J(ρ 1 ) if a∈A + φ * 1 (θ, a) = 1, or else it is a non-binding constraint. Similarly, define binding/non-binding constraints for J(ρ t , H t ).As stated above, we want to guarantee that when the "distance" between J(ρ t , H t ) and J(ρ 1 ) is sufficiently small, the optimal solution to these two programmings have the same landscapes. In this sense, we consider a stability factor D to measure such a threshold, as presented by Mangasarian and Shiau [30] . Proposition 3.1 (Stability). Under Assumption 3.1, there is a maximum D > 0, such that when the following holds:EQUATIONJ(ρ 1 ) and J(ρ t , H t ) share the same sets of basic/non-basic variables and binding/non-binding constraints.With the assumption, below we present the main result of this work, which is proved in Appendix C.1. Theorem 3.1. Under Assumption 3.1, with full information feedback, the expected accumulated reward Rew brought by Algorithm 1 when T → ∞ satisfies:V FL -Rew = O n 2 + k D 2 ,which is independent of T .The intuition behind Theorem 3.1 is to conduct a regret decomposition in a Lagrangian manner, motivated by Chen et al. [15] . This leads to 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 error of O(D), which will happen with high probability after a constant number of rounds. The last term reflects how the stopping time of Algorithm 1 is close to the total time-span T . On this front, we are left to 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 in the estimation world due to the re-solving step, and (2) the distance between the estimation world and the real world diminishes to zero, with the accumulation of samples. The complete reasoning is much more detailed.We now compare Theorem 3.1 with results in prior work. We first mention that our benchmark V FL is larger than the benchmark used in Slivkins and Foster [35] and Slivkins et al. [36] , 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 O( √ m) reliance [7, 4, 35, 23] . As an intuitive reason, the number of actions does not explicitly appear in our Algorithm 1, but only contributes to the dimension of the linear program. Second, although k does not always appear in previous works, this is inevitable in our bound, brought by the estimation error of the context distribution. Third, for the BwK problem, the well-known O(log T ) result given by Sankararaman and Slivkins [31] supposes that n ≤ 2, and it is still unclear whether their analysis can be extended to an arbitrary number of resources. Our result does not suffer from such a limit. Finally, we remark that in the absence of resource constraints, D is precisely half the gap between the mean rewards of the best and second-best arms. Thus, D resembles the reward-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 [31] and is the same with Chen et al. [15] , 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.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 over previous state-of-the-art results under mild assumptions, surpassing the solutions proposed by Han et al. [23] and Slivkins and Foster [35] . In particular, their solutions come from the BwK literature and rely on dual update and upper confidence bound (UCB) heuristics, which only provide a worst-case regret of O( √ T log T ). 
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 γ t when her choice is non-null in round t, i.e., a t = 0. 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 T ) multiplicative degradation under partial information feedback. Our primary theorem in this section is as follows:Θ(log T ) Θ(T )Overall Ω(1) frequencyUniform Ω(1/ log T ) frequency Figure 1 : An illustration of Lemma 4.1. Before Θ(T ) rounds, the probability of accessing frequency at any time step is at least Ω(1/ log T ), and we have an overall Ω(1) frequency with high probability.Theorem 4.1. Under Assumption 3.1, with partial information feedback, the expected accumulated reward Rew brought by Algorithm 1 when T → ∞ satisfies:V FL -Rew = O n 2 + k + log T D 2 .Before we come to the technical parts, we first place Theorem 4.1 within the literature. As previously mentioned, Ω( √ T ) is a 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 4.1 steps beyond the worst case by providing an O(log T ) upper bound for regular problem instances. This result outperforms the universal O( √ T log T ) regret by Han et al. [23] and Slivkins and Foster [35] . While the result is asymptotically equivalent to that of Sankararaman and Slivkins [31] , 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 1 can access an independent sample of the external factor. To this end, we use Y t = |I t | ≤ t -1 to denote the number of times a non-null action is chosen before time t, or equivalently, the number of i.i.d. samples from V observed by the agent before time t under partial information feedback. The following crucial technical lemma provides a lower bound on Y t . Lemma 4.1. There is a constant 0 < C b < 1/2, such that with probability 1 -O(1/T ), the following hold for Algorithm 1:1. For any Θ(log T ) ≤ t ≤ C b • T , Y t ≥ C f • (t -1)/ log T for some constant C f ; 2. For any t > C b • T , Y t ≥ C r • T for some constant C r .The proof of Lemma 4.1 is deferred to Appendix D.2, and an illustration is presented in Figure 1 . In simple terms, during the initial Θ(log T ) rounds (the shaded segment), the re-solving method cannot guarantee the accessing frequency since the learning of the request distribution U has yet to converge sufficiently. However, after Θ(log T ) rounds, Algorithm 1 ensures a constant probability of obtaining a new example in each round, provided that the remaining resources are sufficient. As a consequence, before Θ(T ) rounds, we can guarantee an Ω(1/ log T ) accessing frequency at any time step and an overall Ω(1) frequency with high probability, as established by a concentration inequality. The remaining proof of Theorem 4.1 is provided in Appendix D.1. 
relaxing the regularity assumption -a worst-case guarantee: 
 In Sections 3 and 4, we have proved that Algorithm 1 can achieve an O(1) regret for CDMK problems under full and partial information feedbacks, assuming certain regular conditions (cf. Assumption 3.1). 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.1 and E.2, respectively. Theorem 5.1. With full information feedback, the expected accumulated reward Rew brought by Algorithm 1 satisfies:V FL -Rew = O(k √ T log T + n), as T → ∞. Theorem 5.2.With partial information feedback, the expected accumulated reward Rew brought by Algorithm 1 satisfies: As given by Theorem 2.1, the worst-case regret of any online CDMK algorithm is Ω( √ T ), while Theorems 5.1 and 5.2 indicate that the re-solving heuristic reaches near-optimality in such cases. Further, state-of-the-art algorithms [23, 35] can at most obtain an O( √ T ) regret even with full/partial information feedback. Our algorithm also achieves this near-optimal regret bound in worst cases.V FL -Rew = O(k √ T log T + n), as T → ∞. 
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 a 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 F.Figure 2 describes the relationship between the regret and the number of total rounds T under all four settings. We set the horizon T to be 2000 • 2 k for integer 0 ≤ k ≤ 5. The figure displays both the sample mean (the line) and the 99%-confidence interval (the light color zone) calculated by the results of 50 estimations for the regret, where each estimation comprises 400 independent trials. Observe that when the LP J(ρ) is degenerate, the regret grows on the order of Õ( √ T ) under both full information and partial information settings. Further, when the underlying LP J(ρ) has a 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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 in the core of the paper to a 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, or as supplemental material. 
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 the fluid optimum and online optimum is Ω( √ T ) when the fluid LP has a unique and degenerate optimal solution. Further, we show that the re-solving method reaches an O(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 the Ω( √ T ) lower bound, our non-degeneracy assumption is mild, especially when comparing with the two-resource condition required in Sankararaman and Slivkins [31] .Further, we show that even in worst cases, the re-solving method achieves an O( √ T log T ) regret with full information feedback and an O( √ T log T ) regret with partial information feedback. These results are comparable to start-of-the-art results [23, 35] . We also extend our analysis to the continuous randomness case for completeness.In the main body of this work, we explicitly assume that both the context set and the external factor set are discrete. Such an 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 is the highest competing bid, it is natural to suppose that all these three values are discrete. Nevertheless, for theoretical completeness, we expand our results in this section to circumstances 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 is continuous would be analogous in 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, 1] du and the external factor set Γ = [0, 1] dv . We denote u(θ) and v(γ) as the density function of U and V, respectively. We assume that p ∈ {u, v} belongs to the β p -order L p -Hölder smooth class Σ(β p , L p ). Here, for the foundation, given a vector s = (s 1 , ..., s d ), define|s| = s 1 + • • • + s d , D s = ∂ s1+•••+s d ∂x s1 1 • • • ∂x s d d .Subsequently, for a positive integer β, the β-order L-Hölder smooth class is defined asΣ(β, L) :={g : |D s g(x) -D s g(y)| ≤ L x -y 2 ,for all s such that |s| = β -1, and all x, y}.Now, suppose X 1 , • • • , X k are k i.i.d. samples from a distribution with density function p ∈ Σ(β, L). According to Wasserman [39] , 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 [39] ). Suppose X 1 , • • • , X k are drawn i.i.d. from a d-dimension distribution P, with density p ∈ Σ(β, L) for some L > 0, and k is sufficiently large. Then there exists an estimator p k such that for any > 0, Pr supx |p(x) -p k (x)| > C log(k/ ) k β/(2β+d) ≤ ,with C a constant.The details of constructing such a density estimator are postponed to Appendix G.1. We now return to the re-solving heuristic and Algorithm 1. In the algorithm, with continuous randomness, the constrained optimization problem to be solved in each round J(ρ t , H t ) for t = 1, 2, • • • becomes:J(ρ t , H t ) := max φ:Θ×A + →R θ a∈A + φ(θ, a) γ r(θ, a, γ) v t (γ) u t (θ) dγ dθ, s.t. θ a∈A + φ(θ, a) γ c(θ, a, γ) v t (γ) u t (θ) dγ dθ ≤ ρ t , a∈A + φ(θ, a) ≤ 1, ∀θ ∈ Θ, φ(θ, a) ≥ 0, ∀(θ, a) ∈ Θ × A + .Correspondingly, the reference optimization problem J(ρ t ) is given below:J(ρ t ) := max φ:Θ×A + →R θ a∈A + φ(θ, a) γ r(θ, a, γ)v(γ)u(θ) dγ dθ, s.t. θ a∈A + φ(θ, a) γ c(θ, a, γ)v(γ)u(θ) dγ dθ ≤ ρ t , a∈A + φ(θ, a) ≤ 1, ∀θ ∈ Θ, φ(θ, a) ≥ 0, ∀(θ, a) ∈ Θ × A + .At this point, it is worth mentioning that solving J(ρ t , H t ) in each round could be hard as it could be a continuous yet non-convex constrained optimization problem. Nevertheless, we assume the existence of an oracle that aids us in solving this optimization, and we focus on the regret of the re-solving method. Letα u := (β u + d u )/(2β u + d u ) and α v := (β v + d v )/(2β v + d v ), and we have the following two results, respectively, under full and partial information feedback. Theorem A.1. Under continuous randomness, with full information feedback, the expected accumulated reward Rew brought by Algorithm 1 satisfies:V FL -Rew = O((T αu + T αv + T 1/2 ) log T + n), T → ∞.Theorem A.2. Under continuous randomness, with partial information feedback, the expected accumulated reward Rew brought by Algorithm 1 satisfies:V FL -Rew = O((T αu + T 1/2 ) log T + T αv log 3/2-αv T + n), 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.1 and 5.2.To prove the lemma, we first introduce an intermediate value, which we denote as V Hyb , to upper bound V ON , and show that the gap between V Hyb and V FL is O( √ T ) under the given condition. Specifically, we have the following definition:EQUATIONTo see that V Hyb gives an upper bound on V ON , we fix a request trajectory θ 1 , • • • , θ T . Now, for any non-anticipating strategy π, we letp π t (a) = Pr[a π t = a | θ 1 , • • • , θ t ]be the total probability that a π t = a conditioning on the pre-determined request sequence, with respect to γ 1 , • • • , γ t-1 and the randomness of strategy π. We show that {p π t } t=1,••• ,T is a feasible solution to V Hyb under θ 1 , • • • , θ T . Here, a key observation is that for any t ∈ [T ]:E [c(θ t , a π t , γ t ) | θ 1 , • • • , θ t ] = E γt a∈A + c(θ t , a π t , γ t ) • Pr[a π t = a | θ 1 , • • • , θ t ] = a∈A + C(θ t , a)p π t (a).In the above, the first expectation is taken on γ 1 , • • • , γ t and the random choice of strategy π. Since T t=1 c(θ t , a π t , γ t ) ≤ ρ T always holds, we derive thatT t=1 a∈A + C(θ t , a)p π t (a) = E T t=1 c(θ t , a π t , γ t ) | θ 1 , • • • , θ T ≤ ρT, which indicates that {p π t } t=1,••• ,T is feasible to V Hyb under θ 1 , • • • , θ T .To the same reason, we also haveT t=1 a∈A + R(θ t , a)p π t (a) = E T t=1 r(θ t , a π t , γ t ) | θ 1 , • • • , θ Tequals the conditional expected reward of strategy π. Thus, since V Hyb is a maximization problem for any request trajectory, we conclude that V Hyb ≥ V ON .It remains to show that when V FL , or J(ρ) has a unique and degenerate solution, V FL -V Hyb = Ω( √ T ). We first present a transformation of V Hyb . We letx(θ) := #[appearance of θ] Tbe the random variable indicating the frequency of θ when θ is drawn T times i.i.d. from U. Obviously, the mean of x is u. We now demonstrate thatEQUATIONTo see this, in form (2), it is not hard to see that conditioning on θ 1 , • • • , θ T , the value of the optimization is only related to the number of times that any θ ∈ Θ appears in the sequence, and irrelevant with their arriving order. Therefore, by taking an average, it is without loss of generality to suppose that φ * t1 = φ * t2 as long as θ t1 = θ t2 . Under such an observation, it is natural that ( 2) is equivalent to (3).For convenience, we now recall the definition of V FL :V FL = T • max φ:Θ×A + →R θ∈Θ u(θ) a∈A + R(θ, a)φ(θ, a), s.t. θ∈Θ u(θ) a∈A + C(θ, a)φ(θ, a) ≤ ρ, a∈A + φ(θ, a) ≤ 1, ∀θ ∈ Θ, φ(θ, a) ≥ 0, ∀(θ, a) ∈ Θ × A + .By Sierksma [32] , we know that when J(ρ) has a unique and degenerate solution, then its dual form has multiple solutions. We then adopt the framework of Vera and Banerjee [37] . In particular, we let λ ≥ 0 be the dual variable vector for the resource constraints, and µ ≥ 0 be the dual variable vector for the probability feasibility constraints. If we take ω(θ) = µ(θ)/u(θ), then the dual programming of V FL /T is the following as a function of u:D[Z(u)] = min λ,ω ρ λ + u ω, s.t. λ C(θ, a) + ω(θ) ≥ R(θ, a), ∀(θ, a) ∈ Θ × A + , λ ≥ 0, ω ≥ 0.Now, suppose (λ 1 , ω 1 ) and (λ 2 , ω 2 ) are two different optimal solutions to D[Z(u)], which directly leads to λ 1 = λ 2 by the programming formation. We let λ = λ 1 -λ 2 and ω = ω 1 -ω 2 . Then,EQUATIONFurther, notice that (λ 1 , ω 1 ) and (λ 2 , ω 2 ) are both feasible for D[Z(x)] for any x. Since D[Z(x)] is a minimization problem, by a convex combination, we haveD[Z(x)] ≤ (ρ λ 1 + x ω 1 )1[ρ λ + x ω ≤ 0] + (ρ λ 2 + x ω 2 )1[ρ λ + x ω > 0].Further, by optimality, we know that for any x,D[Z(u)] = (ρ λ 1 + u ω 1 )1[ρ λ + x ω ≤ 0] + (ρ λ 2 + u ω 2 )1[ρ λ + x ω > 0].Now, by weak duality, since V Hyb /T for any given x is a maximization problem, we know from the above two equations that(V FL -V Hyb )/T ≥ D[Z(u)] -E x [D[Z(x)]] ≥ E x ((u -x) ω 1 )1[ρ λ + x ω ≤ 0] + ((u -x) ω 2 )1[ρ λ + x ω > 0] (a) = E x ((u -x) ω 1 )1[(u -x) ω ≥ 0] + ((u -x) ω 2 )(1 -1[(u -x) ω ≥ 0]) (b) = E x ((u -x) ω )1[(u -x) ω ≥ 0] .Here, (a) is due to (4), and (b) is since the mean of x is u. Now, we let ξ = √ T (u -x) ω be the normalized scaled variable. By the Central Limit Theorem, ξ1[ξ ≥ 0] converges to a half-normal distribution, which has a constant expectation. Thus, we arrive at V FL -V Hyb = Ω( √ T ), which finishes the proof.C.1 Proof of Theorem 3.1We now give a proof of Theorem 3.1. The proof draws inspiration from that of Chen et al. [15] , but significantly diverges in terms of the problem setting.We start by presenting a regret decomposition approach, which stands on the dual viewpoint. We first recall the optimization problem V FL = T • J(ρ 1 ):J(ρ 1 ) := max φ:Θ×A + →R E θ∼U a∈A + R(θ, a)φ(θ, a) , s.t. E θ∼U a∈A + C(θ, a)φ(θ, a) ≤ ρ 1 , a∈A + φ(θ, a) ≤ 1, ∀θ ∈ Θ, φ(θ, a) ≥ 0, ∀(θ, a) ∈ Θ × A + .Recall that u(θ) denotes the mass function of U, then the above linear program can be expanded asJ(ρ 1 ) := max φ:Θ×A + →R θ∈Θ,a∈A + u(θ)R(θ, a)φ(θ, a), s.t. θ∈Θ,a∈A + u(θ)C(θ, a)φ(θ, a) ≤ ρ 1 , a∈A + φ(θ, a) ≤ 1, ∀θ ∈ Θ, φ(θ, a) ≥ 0, ∀(θ, a) ∈ Θ × A + .Now let λ ≥ 0 be the dual vector for the consumption constraint and {µ * (θ)} θ∈Θ ≥ 0 be the dual variables for the action distribution constraint. By the strong duality of linear program, there is an optimal dual variable tuple (λ * , {µ * (θ)} θ∈Θ ) ≥ 0 such that:EQUATIONHere φ * 1 is the optimal solution to J(ρ 1 ). With (5), we have the following lemma for regret decomposition. Lemma C.1. For any stopping time T e ≤ T 0 adapted to the process {B t }'s, we haveEQUATIONThe 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 1 and the optimal decision. This is apparent for the first term. For the second term, we should notice that by complementary slackness, for each θ ∈ Θ,µ * (θ) • 1 - a∈A + φ * 1 (θ, a) = 0.Therefore, the second term in ( 6) is bounded if φ * t is close to φ * 1 . On the other hand, the last two terms are closely related to the choice of stopping time T e and the consumption behavior of Algorithm 1. Intuitively, if T e is sufficiently close to T , then E[T -T e ] should be appropriately bounded. Nevertheless, if the algorithm spends the resources too fast, then such a sufficiently large T e would be impossible. Conversely, if the resources are consumed substantially slower than the optimal, then the term E[B Te+1 ], the remaining resources at the stopping time, would be unbounded.In the following, we will deal with these two parts correspondingly. A crux to the analysis is to pick a satisfying stopping time T e , which we will first cover.We first give a realization of the stopping time T e . With Proposition 3.1 in hand, we can derive that when condition (1) is met, it holds thatEQUATIONEQUATIONTo see these, notice that by the dual feasibility of J(ρ 1 ), we have u(θ) R(θ, a) -(λ * ) C(θ, a)µ * (θ) ≤ 0. When u(θ) R(θ, a) -(λ * ) C(θ, a) -µ * (θ) < 0, by primal optimality, φ * 1 (θ, a) = 0 and thus (θ, a) is non-basic for J(ρ 1 ). By Proposition 3.1, (θ, a) is also non-basic for J(ρ t , H t ) and φ * t (θ, a) = 0 holds as well. This finishes the deduction of (7) . A similar reasoning on binding constraints would help us achieve (8) , which we omit here.As the above goes, it is then natural for us to define T e the stopping time in our analysis as follows:T e := min{T 0 , min{t : max{EQUATIONwhere T 0 is the stopping time of Algorithm 1. With the definition, we always have max{ρ 1 | S - ρ t | S ∞ , max{ρ 1 | T -ρ t | T }} ≤ D when t ≤ T e .What we are left is to bound the situation when max{ (u(θ)-u t (θ)) θ∈Θ ∞ , (v(γ) -v t (γ)) γ∈Γ 1 } > D for 1 ≤ t ≤ T e .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.1, with full information feedback, we have when T → ∞:E   Te t=1 θ∈Θ,a∈A + u(θ) R(θ, a) -(λ * ) C(θ, a) -µ * (θ) φ * 1 (θ, a) -φ * t (θ, a)   = O k D 2 , E Te t=1 θ∈Θ µ * (θ) 1 - a∈A + φ * t (θ, a) = O k D 2 .We are now only left to bound the last two terms in (6) .As presented in (6) , we now bound the remaining two terms, respectivelyE[B Te+1 ] and E[T -T e ]for T e defined in (9) . It turns out that these two terms are closely related. Due to this observation, we would first bound Now by the strong duality of J(ρ 1 ), we know that complementary slackness holds, that is λ * | T = 0. We therefore have(λ * ) • E[B Te+1 ] by E[T -T e ],EQUATIONIn the above, recall that ρ max denotes the maximum coordinate of ρ 1 , and D is specified in Proposition 3.1. Consequently, (a) is due to the definition of T e and that ρ 1 + D1 ∞ ≤ ρ max + D.We are left to bound E[T -T e ]. 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.1, with full information feedback, we have when T → ∞:(λ * ) E [B Te+1 ] + max θ∈Θ,a∈A + R(θ, a) -(λ * ) • C(θ, a) E [T -T e ] = O n 2 D 2 .Combining Lemmas C.1 to C.3, we arrive at Theorem 3.1.The proof is obtained by the following set of (in)equalities.V FL -Rew = T • J(ρ 1 ) -E T0 t=1 r(θ t , a t , γ t ) (a) ≤ T • J(ρ 1 ) -E Te t=1 r(θ t , a t , γ t ) (b) = T • J(ρ 1 ) -E   Te t=1 θ∈Θ,a∈A + u(θ)R(θ, a) φ * t (θ, a)   (c) = T •   θ∈Θ,a∈A + u(θ)(R(θ, a) -(λ * ) C(θ, a)) -µ * (θ) φ * 1 (θ, a) + (λ * ) ρ 1 + θ∈Θ µ * (θ)   -E   Te t=1 θ∈Θ,a∈A + u(θ)R(θ, a) φ * t (θ, a)   (d) = E   Te t=1 θ∈Θ,a∈A + u(θ) R(θ, a) -(λ * ) C(θ, a) -µ * (θ) φ * 1 (θ, a) -φ * t (θ, a)   + E Te t=1 θ∈Θ µ * (θ) 1 - a∈A + φ * t (θ, a) + θ∈Θ * µ * (θ) 1 - a∈A + φ * 1 (θ, a) • E [T -T e ] + (λ * ) E   T ρ 1 - Te t=1 θ∈Θ,a∈A + u(θ)C(θ, a) φ * t (θ, a)   +   θ∈Θ,a∈A + u(θ)(R(θ, a) -(λ * ) C(θ, a)) φ * 1 (θ, a)   • E [T -T e ] (e) ≤ E   Te t=1 θ∈Θ,a∈A + u(θ) R(θ, a) -(λ * ) C(θ, a) -µ * (θ) φ * 1 (θ, a) -φ * t (θ, a)   + E Te t=1 θ∈Θ µ * (θ) 1 - a∈A + φ * t (θ, a) + (λ * ) E [B Te+1 ] + max θ∈Θ,a∈A + R(θ, a) -(λ * ) C(θ, a) • E [T -T e ] .In the above set of derivations, (a) holds since T 0 ≥ T e , (b) is due to Optional Stopping Theorem since T e is a stopping time, (c) is by the strong duality of J(ρ 1 ) as given by ( 5), (d) establishes by rearranging terms. At last, for (e), 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 a∈A + φ * 1 (θ, a) ≤ 1 for any θ ∈ Θ and θ∈Θ u(θ) = 1.We will apply the stability result in Chen et al. [15] as an intermediate to prove our version. As given, we know that J(ρ 1 ) and J(ρ t , H t ) has the same set of basic/non-basic variables and binding/non-binding constraints as long as the following conditions hold for some constant D 0 > 0:EQUATIONNow, by a standard insertion technique, we haveEQUATIONFor (a), the first term is bounded since r(θ, a, γ) ≤ 1 and γ v(γ) = 1. The second term is similarly bounded as u t (θ) ≤ 1. Therefore, we let D = D 0 /2, then when we have(u(θ) -u t (θ)) θ∈Θ ∞ ≤ D, (v(γ) -v t (γ)) γ∈Γ 1 ≤ D,the first condition in ( 11) is met. An almost identical reasoning also holds for the second condition in (11) . Consequently we finish the proof of the lemma.Recall that we are going to prove thatE   Te t=1 θ∈Θ,a∈A + u(θ) R(θ, a) -(λ * ) C(θ, a) -µ * (θ) φ * 1 (θ, a) -φ * t (θ, a)   = O k D 2 , E Te t=1 θ∈Θ µ * (θ) 1 - a∈A + φ * t (θ, a) = O k D 2 ,when T → ∞ under Assumption 3.1. For simplicity, we give the following abbreviations:P t := θ∈Θ,a∈a + u(θ) R(θ, a) -(λ * ) C(θ, a) -µ * (θ) φ * 1 (θ, a) -φ * t (θ, a) , Q t := θ∈Θ µ * (θ) 1 - a∈A + φ * t (θ, a) , E u,t := [ (u(θ) -u t (θ)) θ∈Θ ∞ ≤ D], E v,t := [ (v(γ) -v t (γ)) γ∈Γ 1 ≤ D].On this end, we first utilize Proposition 3.1 to show that when condition (1) holds, we haveP t = Q t = 0.Specifically, for P t , by the dual feasibility of J(ρ 1 ), we have u(θ) R(θ, a) -(λ * ) C(θ, a) - µ * (θ) ≤ 0. When u(θ) R(θ, a) -(λ * ) C(θ, a) -µ * (θ) < 0, by primal optimality, φ * 1 (θ, a) = 0and thus (θ, a) is non-basic for J(ρ 1 ). By Proposition 3.1, (θ, a) is also non-basic for J(ρ t , H t ) and φ * t (θ, a) = 0 holds as well. In conjunction with the case that u(θ) R(θ, a) -(λ * ) C(θ, a)µ * (θ) = 0, we obtain that P t = 0.For Q t , notice that we have µ * (θ) ≥ 0 for any θ ∈ Θ. The case that µ * (θ) = 0, again, does not contribute to the total sum. When µ * (θ) > 0, by complementary slackness, a∈A + φ * 1 (θ, a) = 1, i.e., θ is a binding constraint for J(ρ 1 ). This, by Proposition 3.1, implies that θ is also binding for J(ρ t , H t ), which shows that the second term is also zero.With the above, it remains to consider the situation that condition (1) does not hold when t ≤ T e , or in other words, E u,t ∧ E v,t does not hold. Note that P t ≤ 1 and Q t ≤ 1 always hold. Thus, we only need to bound the probability that ¬(E u,t ∧ E v,t ). By a union bound, we havePr[¬(E u,t ∧ E v,t )] = Pr[¬E u,t ∨ ¬E v,t ] ≤ Pr[¬E u,t ] + Pr[¬E v,t ].For the first term above, we apply the Hoeffding's inequality and a union bound to derive thatPr[¬E u,t ] = Pr[ (u(θ) -u t (θ)) θ∈Θ ∞ > D] ≤ 2k exp -2D 2 (t -1) .Whereas for the second term, we use the concentration result in Weissman et al. [40] to derive thatPr[¬E v,t ] = Pr[ (v(γ) -v t (γ)) γ∈Γ 1 > D] ≤ 2 |Γ| -2 exp -D 2 (t -1)/2 .Synthesizing the above all, we haveEQUATIONEQUATIONSumming ( 13) and ( 14) from 1 to T e , we achieve thatE Te t=1 P t , E Te t=1 Q t ≤ T t=1 2k exp -2D 2 (t -1) + 2 |Γ| -2 exp -D 2 (t -1)/2 ≤ 2k 1 -exp (-2D 2 ) + 2 |Γ| -2 1 -exp (-D 2 /2) = O k D 2 ,which conclude the proof of the lemma.As implied by (10) , the proof of this lemma reduces to bound E[T -T e ], i.e., showing that T e is sufficiently close to T . On this side, we first recall the definition of T e in (9):T e := min{T 0 , min{t : max{ ρ 1 | S -ρ t | S ∞ , max{ρ 1 | T -ρ t | T }} > D} -1},where T 0 is the stopping time of Algorithm 1, and S and T correspondingly represent the set of binding/non-binding resource constraints in LP J(ρ 1 ). For simplicity, we defineN (ρ 1 , D, S) := {κ : max{ ρ 1 | S -κ| S ∞ , max{ρ 1 | T -κ| T }} ≤ D}.It is without loss of generality to suppose that D < ρ min . We letT D := min{t : ρ t / ∈ N (ρ 1 , D, S)} -1, T -= T + 1 -1/(ρ min -D) .We show that if t ≤ T -and t ≤ T D , then t ≤ T e . In fact, under the condition, we derive thatB t ≥ (T -t + 1)(ρ 1 -D1) ≥ 1 ρ min -D (ρ 1 -D1) ≥ 1,which implies that t ≤ T 0 , and therefore t ≤ T e . As a result, we haveEQUATIONBefore we continue to bound (15) , we first give an observation on the dynamics of ρ t . By the update process of the budget, we have for any t ≥ 1,B t+1 = B t -c t =⇒ ρ t+1 (T -t) = ρ t (T -t + 1) -c t =⇒ ρ t+1 = ρ t + ρ t -c t T -t .M C t := ρ t -E θ∼U a∈A + φ * t (θ, a)C(θ, a) T -t , N C t := E θ∼U a∈A + φ * t (θ, a)C(θ, a) -c t T -t .We then haveEQUATION)We now define an auxiliary process that benefits the analysis. Specifically, for t ∈ [T ], letρt := ρ t , t ≤ T D ; ρ T D , t > T D . Therefore, ρt+1 -ρt = M C t + N C t , t ≤ T D ; 0, t > T D .We further define the following two auxiliary variables for t ∈ [T ]:M t := M C t , t ≤ T D ; 0, t > T D . , N C t := N C t , t ≤ T D ; 0, t > T D .As a result, we haveρt+1 -ρt = M C t + N C t .Now we come back to (15) . Notice thatEQUATION)For the second term in (18) , we observe that each entry of { τ <t N C τ } t is a martingale with the absolute value of the τ -th increment bounded by 1/(T -τ ). Sincet-1 τ =1 1 (T -τ ) 2 ≤ 1 T -t ,by applying the Azuma-Hoeffding inequality and a union bound, we achieve thatPr t-1 τ =1 N C τ ∞ ≥ D/2 ≤ 2n exp - (T -t)D 2 8 .We now come back to the first term in (18) , for any{D 1 , • • • , D t-1 } such that t-1 τ =1 D τ /(T -τ ) ≤ D/2, we have t-1 τ =1 M C τ S ∞ > D/2 or min t-1 τ =1 M C τ T < -D/2 =⇒ M C τ S ∞ > D τ T -τ or min M C τ T < - D τ T -τ for some τ ∈ [T -1].We now defineE τ (D τ ) := M C τ S ∞ ≤ D τ T -τ ∧ min M C τ T ≥ - D τ T -τ holds for ∀ρ τ ∈ N (ρ 1 , D, S).Since M C τ = 0 only when t ≤ T D , i.e., ρ t ∈ N (ρ 1 , D, S), by the definition of E τ (D τ ), we have the following claim:EQUATION)Thus, we forward to bound Pr[¬E τ (D τ )] for a suitable choice of {D τ } 1≤τ ≤T . Recall that we have defined events E u,τ and E v,τ as follows:E u,τ := [ (u(θ) -u τ (θ)) θ∈Θ ∞ ≤ D], E v,τ := [ (v(γ) -v τ (γ)) γ∈Γ 1 ≤ D].We have the following lemma, which we are going to prove in Appendix C.6:Lemma C.4. When ρ τ ∈ N (ρ 1 , D, S) and E u,τ ∧ E v,τ hold, (T -τ ) M C τ S ∞ ≤ (u(θ) -u τ (θ)) θ∈Θ 1 + (v(γ) -v τ (γ)) γ∈Γ 1 , (T -τ ) min M C τ T ≥ -(u(θ) -u τ (θ)) θ∈Θ 1 -(v(γ) -v τ (γ)) γ∈Γ 1 .Further, it is clear that (T -τ ) M C τ S ∞ ≤ 1 and (T -τ )M C τ T ≥ -1 holds. Inspired by the above observations, we let the series of D 1 , • • • , D T -1 be the following form:D τ = 1, τ ≤ ηT ; (τ -1) -1/4 , τ > ηT ,where η ∈ (0, 1) is a constant to be specified. We need to satisfy the following constraints:T -1 t=1 D t T -t ≤ D/2, (ηT ) -1/4 < D.Here, the first constraint is instructed by (19) , and the second is to guarantee that when (u(θ) -u τ (θ)) θ∈Θ 1 + (v(γ) -v τ (γ)) γ∈Γ 1 < (τ -1) -1/4 for τ > ηT , E u,τ ∧ E v,τnaturally holds, and therefore we can apply Lemma C.4. For the first one, we notice thatT -1 τ =1 D τ T -τ = ηT τ =1 1 T -τ + T -1 τ =ηT +1 1 (T -τ )(τ -1) 1/4 ≤ log T -1 (1 -η)T -1 + log T (ηT ) 1/4 .Therefore, for some η such that log(1 -η) ≥ -D/4, T t=1 D t /(T -t) ≤ D/2 establishes for sufficiently large T 1, and the second constraint is also satisfied.We are now prepared to bound Pr[¬E τ (D τ )] for the {D τ } we just proposed. To start with, when τ ≤ ηT , E τ (D τ ) always holds, thus Pr[¬E τ (D τ )] = 0. When τ > ηT , since τ -1/4 /2 < D, by Hoeffding's inequality and union bound, we havePr[¬E τ (D τ )] (a) ≤ Pr (u(θ) -u τ (θ)) θ∈Θ 1 ≤ (τ -1) -1/4 /2 + Pr (v(γ) -v τ (γ)) γ∈Γ 1 ≤ (τ -1) -1/4 /2 ≤ 2k exp - (τ -1) 1/2 8k 2 + 2|Γ| exp - (τ -1) 1/2 8|Γ| 2 .Here, (a) is by Lemma C.4 and a union bound. Therefore, according to (19) , we havePr t-1 τ =1 M C τ S ∞ > D/2 or min t-1 τ =1 M C τ T < -D/2 ≤ t-1 τ =1 Pr[¬E τ (D τ )],and therefore,Pr t-1 τ =1 M C τ S ∞ > D/2 or min t-1 τ =1 M C τ T < -D/2 ≤      0, t ≤ ηT + 1; t-1 τ =ηT +1 exp -τ 1/2 , t > ηT + 1.Plugging the into ( 18) and ( 15), we obtain that when T → ∞,E [T -T e ] ≤ T -T - + T- t=1 Pr t-1 τ =1 M C τ S ∞ > D/2 or min t-1 τ =1 M C τ T < -D/2 + 2n exp - (T -t)D 2 8 ≤ 1 ρ min -D + 2n(1 -exp(-D 2 /8)) -1 + O(T 2 ) exp -T 1/2 = O n D 2 .At last, combining with (10) , we finally finish the proof of Lemma C.3.To start with, we notice that(T -τ )M C τ = ρ τ -E θ∼U a∈A + φ * τ (θ, a)C(θ, a) .Now, notice that ρ τ ∈ N (ρ 1 , D, S) and E u,τ ∧ E v,τ are the condition of Proposition 3.1, therefore, the set of resource binding constraints of J(ρ t , H t ) are identical to that of J(ρ 1 ), i.e., S. Hence, for any i ∈ [n],ρ i τ | S -E θ∼U a∈A + φ * τ (θ, a)C i (θ, a)| S = θ∈Θ,a∈A + u τ (θ) φ * τ (θ, a) γ v τ (γ)c i (θ, a, γ)| S - θ∈Θ,a∈A + u(θ) φ * τ (θ, a) γ v(γ)c i (θ, a, γ)| S = θ∈Θ,a∈A + (u(θ) -u τ (θ)) φ * τ (θ, a) γ v(γ)c i (θ, a, γ)| S + θ∈Θ,a∈A + u τ (θ) φ * τ (θ, a) γ ( v τ (γ) -v(γ))c i (θ, a, γ)| S (a) ≤ (u(θ) -u τ (θ)) θ∈Θ 1 + (v(γ) -v τ (γ)) γ∈Γ 1 .Here, the bound on the first term in (a) establishes because for any θ ∈ Θ,a∈A + φ * τ (θ, a) γ v(γ)c i (θ, a, γ)| S ≤ 1 since a∈A + φ * τ (θ, a) ≤ 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 Lemma D.1. Under Assumption 3.1, with partial information feedback, we have when T → ∞:ρ τ |T ≥ θ∈Θ,a∈A + u τ (θ) φ * τ (θ, a) γ v τ (γ)c(θ, a, γ)| T .E   Te t=1 θ∈Θ,a∈A + u(θ) R(θ, a) -(λ * ) C(θ, a) -µ * (θ) φ * 1 (θ, a) -φ * t (θ, a)   = O k D 2 log T , E Te t=1 θ∈Θ µ * (θ) 1 - a∈A + φ * t (θ, a) = O k + log T D 2 .Lemma D.2. Under Assumption 3.1, with partial information feedback, we have when T → ∞:(λ * ) E [B Te+1 ] + max θ∈Θ,a∈A + R(θ, a) -(λ * ) • C(θ, a) E [T -T e ] = O n D 2 .Lemmas C.1, D.1 and D.2 in together leads to Theorem 4.1.Some preparations are required before we come to prove the lemma. To start with, we notice thatY τ = Pr[a 1 = 0] + • • • + Pr[a t-1 = 0]. By the control rule of Algorithm 1, we havePr[a τ = 0] = E θ∼U a∈A + φ * τ (θ, a) | H τ .We first give a lower bound onE θ∼U [ a∈A + φ * τ (θ, a) | H τ ] with ρ τ , taking E θ∼ Uτ [ a∈A + φ * τ (θ, a) | H τ ] as an intermediate. Lemma D.3. E θ∼ Uτ a∈A + φ * τ (θ, a) | H τ ≥ min {1, min ρ τ } .Proof of Lemma D.3. To start with, when ρ τ ≥ 1, then clearly, all the resource constraints in J(ρ τ , H τ ) are satisfied even when a∈A + φ(θ, a) = 1 holds for any θ ∈ Θ. Therefore, an optimal solution should have this form.We now consider the case that min ρ τ < 1. In this case, if there is a feasible solution that a,∈A + φ * τ (θ, a) = 1 holds for any θ ∈ Θ, then the proof is also finished. Otherwise, there is at least a binding resource constraint in J(ρ τ , H τ ), which we denote by i * . Consequently,E θ∼ Uτ a∈A + φ * τ (θ, a) ≥ E θ∼ Uτ a∈A + φ * τ (θ, a) C i * τ (θ, a) = ρ i * τ ≥ min ρ τ .This finishes the proof of the lemma.Thus, we haveEQUATIONFurther, we have the following result bounding min ρ τ when t is no larger than a fraction of T . Lemma D.4. When t ≤ (ρ min /2) • T , min ρ τ ≥ ρ min /2.Proof of Lemma D.4. In fact, for t ≤ (ρ min /2) • T ,ρ τ = T • ρ 1 - t-1 τ =1 c τ T -t + 1 ≥ T • ρ 1 -t • 1 T ≥ ρ 1 2 .This concludes the proof. Now, by Weissman et al. [40] , with probability 1 -O(1/T ), we haveu(θ) -u τ (θ) 1 ≤ ρ min 4 , ∀τ ≥ Θ(log T ).Taking into (20), we derive thatPr[a τ = 0] ≥ ρ min 4 , ∀Θ(log T ) ≤ t ≤ ρ min 2 • T.Consequently, within the period, the probability that there are Ω(log T ) consecutive rounds in which the agent chooses to quit in all these rounds is O(1/T ). This proves the first part. Meanwhile, at time t = (ρ min /2) • T + 1, by Azuma-Hoeffding inequality, we derive that with probability1 -O(1/T ), Y t = t-1 τ =1 Pr[a τ = 0]≥ Ω(T ), which proves the second part.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 O(1/T ), and the sum is upper bounded by O(T ), therefore the failure case only contributes O(1) to the total expectation. Now, recall the following definitions:P t := θ∈Θ,a∈a + u(θ) R(θ, a) -(λ * ) C(θ, a) -µ * (θ) φ * 1 (θ, a) -φ * t (θ, a) , Q t := θ∈Θ µ * (θ) 1 - a∈A + φ * t (θ, a) , E u,t := [ (u(θ) -u t (θ)) θ∈Θ ∞ ≤ D], E v,t := [ (v(γ) -v t (γ)) γ∈Γ 1 ≤ D],and by ( 13) and ( 14), we haveE[P t ] ≤ Pr[¬E u,t ] + Pr[¬E v,t ], E[Q t ] ≤ Pr[¬E u,t ] + Pr[¬E v,t ].Now, the bound on Pr[¬E u,t ] 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[¬E u,t ] = Pr[ (u(θ) -u t (θ)) θ∈Θ ∞ > D] ≤ 2k exp -2D 2 (t -1) .For Pr[¬E v,t ], when t ≤ Θ(log T ), it is obviously bounded by 1. By Lemma 4.1, when Θ(log T ) ≤ t ≤ C b • T , by Weissman et al. [40] , we havePr[¬E v,t ] = Pr[ (v(γ) -v t (γ)) γ∈Γ 1 > D] ≤ 2 |Γ| -2 exp - D 2 C f (t -1) 2 log T .Further, when t > C b • T , we correspondingly derivePr[¬E v,t ] ≤ 2 |Γ| -2 exp - D 2 C r (t -1) 2 .Putting the above together, we achieve thatE Te t=1 P t , E Te t=1 Q t ≤ T t=1 2k exp -2D 2 (t -1) + Θ(log T ) + 2 |Γ| -2   C b •T t=Θ(log T ) exp - D 2 C f (t -1) 2 log T + T t=C b •T +1 exp - D 2 C r (t -1) 2   ≤ Θ k D 2 + Θ(log T ) + 2 |Γ| -2 Θ(1) 1 -exp (-Θ(D 2 / log T )) + exp(-Θ(T )) ≤ O k + log T D 2 .This finishes the proof.As in Appendix D.3 when we prove Lemma C.2, we only consider the case when the conditions in Lemma 4.1 establish, as the contribution of the failure cases on the expectation-sum is O(1). We now bound E[T -T e ] 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:T- t=ηT +2 t-1 τ =ηT +1 Pr (v(γ) -v τ (γ)) γ∈Γ 1 ≤ (τ -1) -1/4 /2 .Here, η is specified in the definition of D τ . It is hard for us to directly compare η and C b in Lemma 4.1.Nevertheless, in any case, we know that when T is sufficiently large, Y τ /(τ -1) = Ω(1/ log T ) for τ ≥ ηT . Therefore, we havePr (v(γ) -v τ (γ)) γ∈Γ 1 ≤ (τ -1) -1/4 /2 ≤ 2|Γ| exp - (τ -1) 1/2 |Γ| 2 O(log T ) . Hence, T- t=ηT +2 t-1 τ =ηT +1 Pr (v(γ) -v τ (γ)) γ∈Γ 1 ≤ (τ -1) -1/4 /2 ≤ 2|Γ| T- t=ηT +2 t-1 τ =ηT +1 exp - (τ -1) 1/2 |Γ| 2 O(log T ) = O(T 2 ) exp -Ω T 1/2 log T = O(1).Combining with the other parts, Lemma D.2 is proved.E.1 Proof of Theorem 5.1We will prove Theorem 5.1 in the following, and we are inspired by the analysis in Chen et al. [15] .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, we no longer have any local stability guarantee even when the estimates are close. Therefore, the decision given by Algorithm 1 does not coincides with the 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 a more general regret decomposition as follows:EQUATIONHere, (a) holds due to the Optimal Stopping Theorem, since T 0 is a stopping time. Meanwhile, by the decision process, we have for any θ t :E at,γt [r(θ t , a t , γ t ) | θ t ] = a∈A + φ * t (θ t , a)R(θ t , a).Further, (b) is by a re-arrangement. To give a bound for ( 21), we respectively analyze E[T -T 0 ] the stopping time, and difference between the optimal accumulated rewards and the real ones.To settle the stopping time, we first reduce it to max(ρ 1 -ρ t , 0) for t ≤ T 0 , and then deals with these values. We notice that t ≤ T 0 as long as that B t ≥ 1, or ρ t ≥ 1/(T -t + 1). Now, since for any i ∈ [n],EQUATIONSinceE[T 0 ] ≥ Pr[T 0 ≥ t] • t for any t ∈ [T ],we only need to bound the following term for some certain t:Pr max (ρ 1 -ρ t , 0) ≤ ρ min - 1 T -t + 1 .We will further prove the following lemma in Appendix E.3: Lemma E.1. It holds for any t < T thatPr max (ρ 1 -ρ t , 0) ≥ Θ 1 T -1 + k t-1 τ =2 log T (T -τ ) 2 (τ -1) + log T T -t ≤ O k + n T .With the light of Lemma E.1, it is natural for us to computet-1 τ =2 log T (T -τ ) 2 (τ -1) ≤        log T • 4 √ t -2 T -1 , 2 ≤ t ≤ (T + 1)/2; log T • 2 √ T -t , t > (T + 1)/2.In fact, to derive the above, we notice that when 2 ≤ t ≤ (T + 1)/2,t-1 τ =1 1 (T -τ )(τ -1) 1/2 ≤ 2 T -1 t-1 τ =2 1 (τ -1) 1/2 ≤ 4 √ t -1 T -1 .Meanwhile, when t > (T + 1)/2, we have T -t < t -1, which leads tot-1 τ =2 1 (T -τ )(τ -1) 1/2 ≤ 8 T -1 + t-1 τ =(T +1)/2 1 (T -τ ) 3/2 ≤ 2 √ T -t .With these calculations, we come back to the bound on E[T 0 ], we notice that when T is sufficiently large and t = T -O(log T ), it holds thatΘ 1 T -1 + k t-1 τ =2 log T (T -τ ) 2 (τ -1) + log T T -t + 1 T -t + 1 = O(1) ≤ ρ min .Thus, we haveEQUATIONIn the above, (a) is becauseE[T 0 ] ≥ Pr[T 0 ≥ t]• t for any fixed t, and (b) is due to Lemma E.1. Consequently, we finish the analysis of the stopping time in (21) .The rest part of ( 21) that we are left to consider is the following:EQUATIONNote 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 be proved in Appendix E.4: Lemma E.2. We have for t ≥ 2:E J(ρ t , H t ) -E θ a∈A + φ * t (θ, a)R(θ, a) ≤ O k log T t -1 + k T .Lemma E.2 induces an O( √ T log T ) accumulated regret considering (24) when summing from t = 2 to T 0 ≤ T . While for the first term in (24) , our main thread here is to bound J(ρ t , H t ) with J(ρ t ). To fix the idea, we compare these two optimization problems:J(ρ t ) := max φ:Θ×A + →R+ θ∈Θ,a∈A + u(θ)φ(θ, a) γ r(θ, a, γ)v(γ), s.t. θ∈Θ,a∈A + u(θ)φ(θ, a) γ c(θ, a, γ)v(γ) ≤ ρ t , a∈A + φ(θ, a) ≤ 1, ∀θ ∈ Θ, φ(θ, a) ≥ 0, ∀(θ, a) ∈ Θ × A + .Synthesizing the above two parts, ( 26) is proved.As for E[max(ρ 1 -ρ t , 0)], we note that for any non-negative random variable X with upper bound X and any positive ξ, we haveEQUATIONNotice that max(ρ 1 -ρ t , 0) is certainly upper bounded by 1. Therefore, as a corollary of Lemma E.1, we haveE [max (ρ 1 -ρ t , 0)] ≤            O k (t -2) log T T + log T T -t + k + n T , 2 ≤ t ≤ (T + 1)/2; O k log T T -t + k + n T , t > (T + 1)/2.We almost finish the bound now except for determining η t in (25) , which we hope is as 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.E T0 t=1 J(ρ 1 ) -J(ρ t , H t ) = O(k T log T + n).Now, we sum the result in Lemma E.2 from t = 2 to T 0 , and plus the constant term for t = 1 to obtain thatE T0 t=1 J(ρ t , H t ) -E θ a∈A + φ * t (θ, a)R(θ, a) = O(k T log T ).Synthesizing Lemma E.3, ( 24), (23) , and ( 21), we derive Theorem 5.1.The proof of this theorem follows the line of Theorem 5.1, and the only difference is to adopt Lemma 4.1 when considering the concentration of estimates. On this side, we can disregard the cases when t ≤ Θ(log T ), as the accumulated regret in this phase is bounded by O(log T ). On the other hand, the time range that t ≥ Θ(T ) is asymptotically identical to the full information setting since the accessing frequency is a constant. We only need to consider the case that Θ(log T ) ≤ t ≤ Θ(T ), when we haveEQUATIONTaking into the proof of Lemma E.1 and then into the main body, we should find a sufficient large t such that Nevertheless, for the counterpart of Lemma E.2, by (28) , when we sum from t = 1 to T 0 ≤ T , we derive thatΘ   log T T -1 + k Θ(T ) τ =Θ(log T ) log T (T -τ ) 2 (τ -1) + k t-1 τ =Θ(T ) log T (T -τ ) 2 (τ -1) + log T T -t   ≤ ρ min - 1 T -t + 1 ,E T0 t=1 J(ρ t , H t ) -E θ∼U a∈A + φ * t (θ, a)R(θ, a) ≤ O(k √ T log T ).At last, for J(ρ 1 ) -J(ρ t , H t ), we face the same degradation on the estimation accuracy, which leads toE T0 t=1 J(ρ 1 ) -J(ρ t , H t ) = O(k √ T log T + n).Therefore, Theorem 5.2 is achieved.E.3 Proof of Lemma E.1Now that we are going to bound max(ρ 1 -ρ t , 0). Recall the definitions below which we give in Appendix C.5 when we prove Lemma C.3:M C t := ρ t -E θ∼U a∈A + φ * t (θ, a)C(θ, a) T -t , N C t := E θ∼U a∈A + φ * t (θ, a)C(θ, a) -c t T -t .By ( 16), we haveρ t+1 -ρ t = ρ t -c t T -t = M C t + N C t .Consequently,max(ρ 1 -ρ t ) = max - t-1 τ =1 M C τ + t-1 τ =1 N C τ ≤ -min t-1 τ =1 M C τ -min t-1 τ =1 N C τ .For the second term, we notice that each entry of { τ <t N C τ } t is a martingale with the absolute value of the τ -th increment bounded by 1/(T -τ ). Sincet-1 τ =1 1 (T -τ ) 2 ≤ 1 T -t ,by applying the Azuma-Hoeffding inequality and a union bound, we achieve thatEQUATIONOn the other hand, for the first term, when τ = 1, it is apparent that -minM C 1 ≤ 1/(T -1). When τ ≥ 2, we have for any i ∈ [n], (T -τ ) M C τ i = ρ i τ -E θ∼U a∈A + φ * τ (θ, a)C i (θ, a) (a) ≥ θ∈Θ,a∈A + u τ (θ) φ * τ (θ, a) γ v τ (γ)c i (θ, a, γ) - θ∈Θ,a∈A + u(θ) φ * τ (θ, a) γ v(γ)c i (θ, a, γ) = θ∈Θ,a∈A + ( u τ (θ) -u(θ)) φ * τ (θ, a) γ v τ (γ)c i (θ, a, γ) + θ∈Θ,a∈A + u(θ) φ * τ (θ, a) γ ( v τ (γ) -v(γ))c i (θ, a, γ) ≥ -(u(θ) -u τ (θ)) θ∈Θ 1 -(v(γ) -v τ (γ)) γ∈Γ 1 .In the above, (a) is because φ * τ is feasible for J(ρ τ , H τ ). By Hoeffding's inequality and a union bound, we havePr (u(θ) -u τ (θ)) θ∈Θ 1 ≤ -k log T τ -1 ≤ k T 2 , Pr (v(γ) -v τ (γ)) γ∈Γ 1 ≤ -|Γ| log T τ -1 ≤ |Γ| T 2 .Thus, suppose the above events hold for all τ ≤ T with failure probability only O(1/T ),EQUATIONCombining ( 29) and ( 30), we derive the lemma.E.4 Proof of Lemma E.2We notice thatJ(ρ t , H t ) = θ∈Θ,a∈A + u t (θ) φ * t (θ, a) γ r(θ, a, γ) v t (γ),andθ∈Θ,a∈A + u t (θ) φ * t (θ, a) γ v t (γ)r(θ, a, γ) - θ∈Θ,a∈A + u(θ) φ * t (θ, a) γ v(γ)r(θ, a, γ) = θ∈Θ,a∈A + ( u t (θ) -u(θ)) φ * t (θ, a) γ v t (γ)r(θ, a, γ) + θ∈Θ,a∈A + u(θ) φ * t (θ, a) γ ( v t (γ) -v(γ))r(θ, a, γ) ≤ (u(θ) -u t (θ)) θ∈Θ 1 + (v(γ) -v t (γ)) γ∈Γ 1 .Thus,J(ρ t , H t ) -E θ∼U a∈A + φ * t (θ, a)R(θ, a) ≤ (u(θ) -u t (θ)) θ∈Θ 1 + (v(γ) -v t (γ)) γ∈Γ 1 .By Hoeffding's inequality and a union bound, we havePr (u(θ) -u t (θ)) θ∈Θ 1 ≥ k log T 2(t -1) ≤ k T , Pr (v(γ) -v t (γ)) γ∈Γ 1 ≥ |Γ| log T 2(t -1) ≤ |Γ| T .Further, the difference we hope to analyze is certainly upper bounded by 1. As a result, with (27) , we finish the proof.We come to consider J(ρ 1 ) -J(ρ t , H t ). As per the thread in the main body, we letδ t := (u(θ) -u t (θ)) θ∈Θ ∞ + (v(γ) -v t (γ)) γ∈Γ 1 min θ∈Θ,a∈A + {min{u(θ)C(θ, a) > 0}} .We now claim that for any (θ, a, i)∈ Θ × A + × [n], u t (θ) γ c i (θ, a, γ) v t (γ) ≤ (1 + δ t )u(θ) γ c i (θ, a, γ)v(γ).The above is obvious if C i (θ, a) = 0, or c i (θ, a, γ) = 0 holds for any γ. When C(θ, a) = 0, then for any i ∈ [n],u t (θ) γ c i (θ, a, γ) v t (γ) -u(θ) γ c i (θ, a, γ)v(γ) = ( u t (θ) -u(θ)) γ c i (θ, a, γ) v t (γ) + u(θ) γ c i (θ, a, γ)( v t (γ) -v(γ)) ≤ (u(θ) -u t (θ)) θ∈Θ ∞ + (v(γ) -v t (γ)) γ∈Γ 1 ≤ δ t u(θ) γ c i (θ, a, γ)v(γ).This finish the explanation of the claim. Upon that, if we let η t := 1 -δ t ≤ 1/(1 + δ t ), we derive thatu(θ) γ c(θ, a, γ)v(γ) ≤ 1 1 + δ t u t (θ) γ c(θ, a, γ) v t (γ) ≤ η t u t (θ) γ c(θ, a, γ) v t (γ).With respect to ( 25) and ( 26), we obtain thatEQUATIONAs we have already shown in the main part thatE [max (ρ 1 -ρ t , 0)] ≤            O k (t -2) log T T + log T T -t + k + n T , 2 ≤ t ≤ (T + 1)/2; O k log T T -t + k + n T , t > (T + 1)/2.it suffices for us to boundE[ (u(θ) -u t (θ)) θ∈Θ ∞ ], E[ (u(θ) -u t (θ)) θ∈Θ 1 ], E[(v(γ) -v t (γ)) γ∈Γ 1 ].On this side, as we have shown thatPr (u(θ) -u t (θ)) θ∈Θ 1 ≥ k log T 2(t -1) ≤ k T , Pr (v(γ) -v t (γ)) γ∈Γ 1 ≥ |Γ| log T 2(t -1) ≤ |Γ| T , it is natural that {E[ (u(θ) -u t (θ)) θ∈Θ ∞ ], E[ (u(θ) -u t (θ)) θ∈Θ 1 ], E[(v(γ) -v t (γ)) γ∈Γ 1 ]} ≤ O k log T t -1 + k T .Thus, putting all the above into (31) and summing from t = 1 to T 0 ≤ T , we haveE T0 t=1 J(ρ 1 ) -J(ρ t , H t ) = O(k T log T + n).This concludes the proof.Specifically, we 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(θ 1 ), u(θ 2 ), u(θ 3 )) = (0.3, 0.3, 0.4) and (v(γ 1 ), v(γ 2 )) = (0.5, 0.5), respectively. The resource consumption is represented byEQUATION= 2.1 1.9 0.8 1.2 0.9 1.1,EQUATIONi,j , Ci,j ) for all (i, j). The reward function is represented byR = 1.2 0.8 1.3 1.1 0.7 0.9, where r(θ i , 1, γ j ) = R i,j for all i, j. Thus the underlying LP isJ(ρ) = max 0.3 • x 1 + 0.36 • x 2 + 0.32 • x 3 , s.t. 0.3 • x 1 + 0.6 • x 2 + 0.4 • x 3 ≤ ρ 1 , 0.6 • x 1 + 0.3 • x 2 + 0.4 • x 3 ≤ ρ 2 , 0 ≤ x i ≤ 1, i = 1, 2, 3,where x i = φ(θ i ) for all i = 1, 2, 3. For a degenerate instance, we set ρ = (1, 1.15) with the optimal solution x * = (1, 0.5, 1) . For a non-degenerate problem instance, we set the average resources as ρ = (1, 1) and the unique optimal solution is x * = (2/3, 2/3, 1) ; Here we 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 a relaxation is to make the LP form more visually appealing.We now present details on the kernel density estimator which we apply in Appendix A for approximating continuous distributions, which comes from Wasserman [39] . We consider a one-dimensional kernel function K such that• K(x) dx = 1; • x s K(x) dx = 0, ∀1 ≤ s ≤ β; • |x| β |K(x)| dx < ∞.Now, given independent samples X 1 , • • • , X from P and a positive number h called the bandwidth, the kernel density estimator is defined asp (x) = 1 i=1 1 h d K x -X i 2 h .Furthermore, to satisfy Proposition A.1, we should choose h k 1/(2β+d) log k when p ∈ Σ(β, L) is the density of P on R d .By (21), we know thatV FL -Rew = J(ρ 1 ) • E [T -T 0 ] + E T0 t=1 J(ρ 1 ) -E θ a∈A + φ * t (θ, a)R(θ, a) ,and we bound these terms in order. For the expected stopping time E[T 0 ], by the analysis in Section 5, our goal turns into bounding max(ρ 1 -ρ t , 0), which further by ( 16) and ( 29), reduces to bound M C τ . With continuous randomness, we have for anyi ∈ [n], (T -τ ) M C τ i = ρ i τ -E θ a∈A + φ * τ (θ, a)C i (θ, a) (a) ≥ θ a∈A + φ * τ (θ, a) γ c i (θ, a, γ) v τ (γ) u τ (θ) dγ dθ - θ a∈A + φ * τ (θ, a) γ c i (θ, a, γ)v(γ)u(θ) dγ dθ = θ a∈A + φ * τ (θ, a) γ c i (θ, a, γ) v τ (γ)( u τ (θ) -u(θ)) dγ dθ + θ a∈A + φ * τ (θ, a) γ c i (θ, a, γ)( v τ (γ) -v(γ))u(θ) dγ dθ (b) ≥ -sup θ |u(θ) -u τ (θ)| -sup γ |(v(γ) -v τ (γ)|.In the above, (a) is by the constraint feasibility of φ * τ , and (b) is because a∈A + φ * τ (θ, a) ≤ 1 holds for any θ ∈ Θ. Further, by Proposition A.1, we have for τ = Ω(1),Pr sup θ |u(θ) -u τ (θ)| ≤ -Θ log T (τ -1) αu-1 ≤ 1 T 2 , Pr sup γ |v(θ) -v τ (θ)| ≤ -Θ log T (τ -1) αv-1 ≤ 1 T 2 .Thus, when t = Ω(1), we derive that with failure probability O(n/T ), it holds thatmax (ρ 1 -ρ t , 0) ≤ Θ   1 T -1 + log T t-1 τ =Θ(1) (τ -1) αu-1 T -τ + (τ -1) αv-1 T -τ + log T T -t   .Further, for p ∈ {u, v}, when t ≤ (T + 1)/2,t-1 τ =Θ(1) (τ -1) αp-1 T -τ ≤ 2 T -1 t-1 τ =2 (τ -1) αp-1 ≤ 2(t -2) αp α p (T -1) ;and when t > (T + 1)/2, we havet-1 τ =Θ(1) (τ -1) αp-1 T -τ ≤ 1 α p 2 T -1 1-αp + t-1 τ =(T +1)/2 (T -τ ) αp-2 ≤ (T -t) αp-1 1 -α p .Thus, when t = T -Θ(log (2(1-max{1/2,αu,αv})) -1 T ), we haveΘ   1 T -1 + log T t-1 τ =Θ(1) (τ -1) αu-1 T -τ + (τ -1) αv-1 T -τ + log T T -t   ≤ ρ min - 1 T -t + 1 , which leads to E [T -T 0 ] = O log (2(1-max{1/2,αu,αv})) -1 T .This concludes the analysis of the stopping time.For the second part, By (24), we haveJ(ρ 1 ) -E θ a∈A + φ * t (θ, a)R(θ, a) = J(ρ 1 ) -J(ρ t , H t ) + J(ρ t , H t ) -E θ a∈A + φ * t (θ, a)R(θ, a) .On the second difference term, similar to the proof of Lemma E.2, we haveJ(ρ t , H t ) -E θ a∈A + φ * t (θ, a)R(θ, a) = θ a∈A + φ * t (θ, a) γ r(θ, a, γ) v t (γ) u t (θ) dγ dθ - θ a∈A + φ * t (θ, a) γ r(θ, a, γ)v(γ)u(θ) dγ dθ ≤ sup θ |u(θ) -u t (θ)| + sup γ |(v(γ) -v t (γ)|.Thus, when t = Ω(1), by taking = 1/T in Proposition A.1 and ( 27), we arrive thatE J(ρ t , H t ) -E θ a∈A + φ * t (θ, a)R(θ, a) = O log T (t -1) αu-1 + (t -1) αv-1 + 1 T .We now focus on J(ρ 1 ) -J(ρ t , H t ). We letδ t := sup θ |u(θ) -u t (θ)| + sup γ |(v(γ) -v t (γ)| min θ∈Θ,a∈A + {min{u(θ)C(θ, a) > 0}} .We prove thatu t (θ) γ c i (θ, a, γ) v t (γ) dγ ≤ (1 + δ t )u(θ) γ c i (θ, a, γ)v(γ) dγholds for any (θ, a, i) tuple, which is obvious if c i (θ, a, γ) is almost surely zero with respect to γ.Otherwise, we observe thatu t (θ) γ c i (θ, a, γ) v t (γ) dγ -u(θ) γ c i (θ, a, γ)v(γ) dγ = ( u t (θ) -u(θ)) γ c i (θ, a, γ) v t (γ) dγ + u(θ) γ c i (θ, a, γ)( v t (γ) -v(γ)) dγ ≤ sup θ |u(θ) -u t (θ)| + sup γ |(v(γ) -v t (γ)| ≤ δ t u(θ) γ c i (θ, a, γ)v(γ) dγ.and thus, withη t := 1 -δ t ≤ 1/(1 + δ t ), we derive that u(θ) γ c i (θ, a, γ)v(γ) dγ ≤ 1 1 + δ t u t (θ) γ c i (θ, a, γ) v t (γ) dγ ≤ η t u t (θ) γ c i (θ, a, γ) v t (γ) dγ.This proves the above inequality. Thus, for an optimal solution φ * t of J(ρ t ), we see that η t φ * t is a feasible solution of the programming J(ρ t , H t ). Thus, we notice thatJ(ρ t , H t ) ≥ η t θ a∈A + φ * t (θ, a) γ r(θ, a, γ) v t (γ) u t (θ) dγ dθ ≥ η t θ a∈A + φ * t (θ, a) γ r(θ, a, γ)v(γ)u(θ) dγ dθ -η t (sup θ |u(θ) -u t (θ)| + sup γ |(v(γ) -v t (γ)|) = η t J(ρ t ) -(sup θ |u(θ) -u t (θ)| + sup γ |(v(γ) -v t (γ)|).With respect to (26) , we obtain thatJ(ρ 1 ) -J(ρ t , H t ) ≤ J(ρ 1 ) • 1 -η t + max (ρ 1 -ρ t , 0) ρ min + sup θ |u(θ) -u t (θ)| + sup γ |(v(γ) -v t (γ)| = J(ρ 1 ) • δ t + max (ρ 1 -ρ t , 0) ρ min + sup θ |u(θ) -u t (θ)| + sup γ |(v(γ) -v t (γ)|.Now, when t = Θ(1), we haveE sup θ |u(θ) -u t (θ)| = O log T (t -1) αu-1 + 1 T , E sup γ |v(γ) -v t (γ)| = O log T (t -1) αv-1 + 1 T .By the previous reasoning on max(ρ 1 -ρ t , 0), we obtain that when t = Ω(1),E [max(ρ 1 -ρ t , 0)] ≤ Θ   1 T -1 + log T t-1 τ =Θ(1) (τ -1) αu-1 T -τ + (τ -1) αv-1 T -τ + log T T -t + n T   .Therefore, summing from t = 1 to T 0 ≤ T , we achieve thatE T0 t=1 J(ρ 1 ) -J(ρ t , H t ) = O (T 1/2 + T αu + T αv ) log T + n .Combining with previous bounds on E[T -T 0 ] and the estimation errors, we derive the theorem.Similar to the proof of Theorem 5.2, we concentrate on re-bounding the three terms under partial information feedback, respectivelyE[T -T 0 ], J(ρ t , H t )-E θ [ a∈A + φ * t (θ, a)R(θ, a)],and J(ρ 1 )-J(ρ t , H t ). As for E[T -T 0 ], with Lemma 4.1, we argue here that the main term in bounding max(ρ 1 -ρ t , 0) when t = Θ(T ) becomesΘ   log T   t-1 τ =Θ(1) (τ -1) αu-1 T -τ + Θ(T ) τ =Θ(1) ((τ -1)/ log T ) αv-1 T -τ + t-1 τ =Θ(T ) (τ -1) αv-1 T -τ     .Consequently, when t is close to T , we have with failure probability O(1/T ), max(ρ 1 -ρ t , 0)≤ Θ 1 T -1 + log T (T -t) αu-1 + (T -t) -1/2 + (T -t) αv-1 log 3/2-αv T .This leads toE[T -T 0 ] = O log max(1,1/(2-2αu),(3-2αv)/(2-2αv)) T .For the estimation error term J(ρ t , H t ) -E θ [ a∈A + φ * t (θ, a)R(θ, a)], when Ω(1) ≤ t ≤ Θ(T ), the bound now becomesE J(ρ t , H t ) -E θ a∈A + φ * t (θ, a)R(θ, a) = O log T (t -1) αu-1 + log 3/2-αv T • (t -1) αv-1 + 1 T .At last, for J(ρ 1 ) -J(ρ t , H t ), we derive thatE T0 t=1 max(ρ 1 -ρ t , 0) = O log T T αu + T 1/2 + log 3/2-αv T • T αv + n , E T0 t=1 sup θ |u(θ) -u t (θ)| = O log T • T αu , E T0 t=1 sup γ |v(γ) -v t (γ)| = O log 3/2-αv T • T αv .Putting together, we obtain thatE T0 t=1 J(ρ 1 ) -J(ρ t , H t ) = O log T T αu + T 1/2 + log 3/2-αv T • T αv + n .Synthesizing all the above, we finish the proof of the theorem.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes]Justification:The paper provides open access to 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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It 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 a 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 of range (e.g. negative error rates). • If error bars are 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. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: The paper provides sufficient information on 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, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs 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). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 societal impacts and negative societal impacts of the work performed.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: 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 is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 
√: 
 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 Ω( √ 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 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 O( √ 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. 
 
 Appendix:  


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The assumption on the randomness is stronger than those made in the contextual decision-making literature.

2. 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.
questions: 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?



Ref:

[1] Arlotto A, Gurvich I. Uniformly bounded regret in the multisecretary problem[J]. Stochastic Systems, 2019, 9(3): 231-260.

[2] Bray R L. Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations[J]. arXiv preprint arXiv:1912.08917, 2019.

[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: limitations: N.A.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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$?

2. What's the difference between Rew and V^{on}?

3. 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$?

4. In the simulation, how does the proposed algorithm compare with the existing algorithms proposed for this problem?
questions: questions: 1. It is slightly confusing to use $\rho^i$ to denote the $i$th entry since it also means exponent.
limitations: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 
2. See questions below.
questions: 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. 
2. 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? 
3. 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?
4. 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. 
5. 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. 

I am happy to raise the score if these issues are well addressed.
limitations: limitations: Comparison to continuous optimization methods in NRM problems are not discussed.
paper_summary: paper_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.
strength_weakness: strength_weakness: If Theorem 3.1 is written correctly then please see the “strengths” section for a major weakness.

In 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)).

Line 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.

Line 171: Theorem 2.1 does not show an \Omega(\sqrt{T}) regret lower bound when you define the regret relative to $V^{FL}$.
questions: questions: Can you give examples to show that the non-degeneracy of $J(\rho_1)$ is common.
limitations: limitations: N/A

Comments: title: Acknowledgement
comment: Thanks a lot! We will surely improve our manuscript on noting more about problem-dependent constants.
Thanks a lot!
Thanks a lot!
Thanks a lot!
Yes - sorry - of course you can replace $V^{\mathrm{FL}}$ with $V^{\mathrm{ON}}$ - I was thinking "losses" rather than "rewards". I am therefore increasing my score - but I feel strongly that, if this paper is accepted, you should include all problem-dependent constants in Theorem 3.1
Thank you for your response. I will keep my score positive.
Hi, we are looking forward to seeing your opinion on our rebuttal!
Hi, we are looking forward to seeing your opinion on our rebuttal!
Thanks for your responses! It addresses my questions well. I will raise the score to 5.
Thanks for your responses! I will keep my score.