Contextual Decision-Making with Knapsacks Beyond the Worst Case

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.

Strengths

I am wondering if in Theorem 3.1 the display equation should say $V^{ON}$ instead of $V^{FL}$. If it is indeed $V^{FL}$ then your goal is only comparing to $V^{FL}$ so what is the point of the “worst case” discussion comparing $V^{FL}$ to $V^{ON}$? If is is meant to be $V^{ON}$ in Theorem 3.1 then I think that this is an interesting result. However, if it is indeed $V^{FL}$ then the result is much weaker as you have not shown any improvement over $O(\sqrt{T})$ with respect to the optimal policy. My final score will be highly dependent on your answer to this question.

Weaknesses

If Theorem 3.1 is written correctly then please see the “strengths” section for a major weakness. 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

Can you give examples to show that the non-degeneracy of $J(\rho_1)$ is common.

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

N/A

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.

Strengths

Under the unique non degenerate LP assumption, the paper has provided regret bounds that are better than the worst cases in both full information and partial information setting, which is novel. It further shows that without this assumption, the regret bound is indeed $O(\sqrt{T})$ that matches the lower bounds. The paper further provides regret bounds when the request and context are continuously distributed. It greatly enhances the understanding of the problem.

Weaknesses

1. I found the presentation can be further improved, particularly about why the unique non-degenerate solution can greatly improve the regret bound and provide a proof sketch. This is the main contribution of the work yet the intuition is not fully clear. 2. See questions below.

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.

Rating

5

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

Comparison to continuous optimization methods in NRM problems are not discussed.

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.

Strengths

The paper is well written. The relation between the worst case condition and the degeneracy of linear constraints is novel and inspiring. The intuition behind the proposed algorithm is clearly explained.

Weaknesses

1. Is $T$ known beforehand? If $T$ is unknown, how to compute the leftover budget $\rho_t$? If $T$ is known, how to design an algorithm with unknown $T$? 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

1. It is slightly confusing to use $\rho^i$ to denote the $i$th entry since it also means exponent.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

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.

Strengths

1. The model considered in the paper is quite general to cover several interesting problems. 2. The results provided under the proposed model is relative sharp and complete.

Weaknesses

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

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.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N.A.

Acknowledgement

Thanks for your responses! It addresses my questions well. I will raise the score to 5.