Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studied dynamic multi-product pricing and assort problems under the Multinomial Logit Model (MNL). For multi-product pricing problems, they proposed the Online Newton method for multiple product pricing algorithms with $O(d\sqrt{T}\log(T))$ regret bound. For assort problems, they proposed OFU-MNL with better dependency on the problem-dependent parameter $\kappa$.
strengths_and_weaknesses: For dynamic pricing, the paper extends the current literature to multiple products with feature-dependent price sensitivities. I believe it is an important extension and has many applications in practice. The idea is that it can consider the problem as an online convex optimization problem and use a famous technique (Online Newton step) to deal with it. However, due to the existence of uninformative prices, it can break the ONS algorithm. Therefore, the proposed algorithm needs to introduce random shock to increase exploration. 

Technically, both online newton step and random shocks have been applied to dynamic pricing under different settings as the authors pointed out in the literature, therefore I am not surprised when the authors can derive the regret bound for a new setting of multiple products. I think a very strong assumption in the paper compared to the related work is that after each round $t$, the seller can observe $q_t$, the customer probability of buying products (so that the seller can update the estimate $\gamma_t$). In Xu and Wang's work (Logarithmic Regret in Feature-based Dynamic Pricing), it seems that they only require observing indicator $y_t$ of customer buying the product or not, which is more practical. 

Experiment: the experiment results in Appendix D show an advantage of the proposed algorithm compared to a similar online Newton method (ONSP) with a single product. However, the experiment result is not convincing since it is based on a stochastic setting whereas all the theoretical results in this paper focus on adversarial counterparts.
questions: The author mentioned that optimal regret bound $(O(\sqrt{T}))$ is achievable in the case of a single product with Feature-based dynamic pricing. Does it mean that if we apply the algorithm in the paper to a single product, it will lead to a slightly worse regret bound compared to the optimal one? 

Can the author comment on the running of Algorithm 1? Since it requires an inverse of a Hessian matrix at every time step, it may not be as efficient as first-order methods.
limitations: There is no potential societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper, the authors studied contextual dynamic pricing and assortment optimization problems under the MNL choice model. They proposed two algorithms: (1) a dynamic pricing algorithm which combines a variant of the ONS algorithm and random price shocks, and showed that this algorithm achieves $O(d \sqrt{T} \log{T})$ regret under adversarial arrival. (2) an optimistic algorithm for the adversarial MNL contextual bandits problem, and showed that it achieves better dependency on parameter $\kappa$ than existing algorithms, where $\kappa$ is a problem-dependent constant that measures deviation from the linear model. 
strengths_and_weaknesses: Strengths:
1. The dynamic pricing policy proposed in Section 2 uses interesting ideas that combine ONS method with random price shocks, and is shown to attain near-optimal performance. 
2. The optimistic algorithm for adversarial MNL contextual bandits proposed in Section 3 is shown to achieve better dependency on $\kappa$, and does not assume knowledge of $\kappa$ a priori. 
3. The authors provide clear and thorough proof for their theoretical results. 

Weaknesses: 
1. The authors provided a brief discussion of related literature on contextual dynamic pricing/assortment problems in the beginning of section 1. It could be desirable to have a separate and more detailed discussion of related work that compares this work with the previous literature. 
2. While the regret bounds are theoretically sound, it could be good to also include some numerical studies here to demonstrate the performance of the algorithm and verify the dependency on parameters $T$ and $d$ of the regret bound. Another thing that is missing from the current work is the runtime for both algorithms. 
3. It appears that the design of the algorithms leverages the self-concordant property of the MNL log likelihood function. More discussions can be provided here to motivate why the use of self-concordant property is important to the proof. 

questions: 1. In Algorithm 2, there is a step that requires one to choose the set of $K$ items maximizing the expected revenue. Are you simply selecting the $K$ items with the highest $x_{t, i}^\top \tilde{\theta}_i$ here? 
2. If so, any ideas what will happen when the rewards are no longer uniform and we also need to consider assortments with size less than $K$?

limitations: None.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this work, the authors study two different online-learing problems, a multi-product dynamic pricing problem and a multi-product dynamic assortment optimization problems, under a multinomial logit (MNL) model choice model. In the pricing problem, at each round t, a customer comes with a candidate set of features describing her preference on corresponding products, and the seller (we) are asked to set prices for these candidate products. After seeing these prices, the customer will choose at most one of them to buy, according to the MNL model with linear parameters. The goal is to maximize the expected revenue. In the assorting problem, the situation is slightly different: At each round t, a customer comes with a set of features describing her preference on all products, and the seller (we) are asked to propose a list of $\leq K$ products as candidates. After seeing these candidates, the customer would take at most one product from these candidates. In the assorting problem, the goal is to maximize the probability of not-buying-empty.

In this work, the authors propose algorithms for both problems: For the pricing prolem, they propose an Online-Newton (ON)-based pricing algorithm which achieves an $O(d\log{T}\sqrt{T})$ regret. This result matches the existing information-theoretic lower bound at $\tilde{O}(\sqrt{T})$. For the assorting problem, they propose an OFU-MNL algorithm that achieves an $O(d\sqrt{\kappa T}+d^2\frac{\log(T)}{\kappa})$ regret. This result improve the existing results by reducing the dependence on $\frac1{\kappa}$ as $\kappa=o(1)$.
strengths_and_weaknesses: Strength:

1, This work studies online multi-product pricing and assortment problems and proposes provable algorithms. The problem setting is meaningful. Their regret upper bounds are either optimal (for pricing) or better than existing results (for assortments).

2, For the pricing problem, they use Online Newton method + self-concordant-like property to substitute the role of an ONS algorithm, while also saving the regret dependence on constants. Their numerical result (in Appendix) also shows the significance of their work over existing methods in practice.

Weakness:

1, Their improvement from existing theoretical results on the assorting problem is not substantial.

2, Problem formulation and literature reviews are insufficient: It is unclear how to place this work in the stream of pricing/assorting researches.

Overall, this is a good work to get in, and I would like to raise my score as long as the authors properly address my concerns.
questions: Please point it out directly in the rebuttal if I am wrong in the following questions/suggestions.

1, In Line 34 the authors mentioned the regret on the assorting problem, without firstly describing the goal of assorting and the (informal) definition of its regret. This could be confusing to the readers.

2, In Line 86, the authors mentioned that an $O(d\log{T})$ regret is implied by their result for single-product pricing problem. However, I did not find such a reduction in the paper. Is there a remark/corollary regarding this, or a trivial reduction to this result?

3, In Line 93, the authors mentioned that their ON-based pricing algorithm outperforms the ONS-based pricing algorithm in [41] by improving the dependence on a "potentially exponentially small constant". However, I did not find (1) how the small constant is like and (2) what improvement this work has made, in either the main pages or Appendix D. Only descriptive words are in Line 181-191

I guess this small constant could be $\kappa$ as is mentioned in Line 190-191, but I am not quite sure: (1) a $\kappa$ is defined for the assorting problem (see Line 267) instead of the pricing problem (as they have different definitions on the $q_{t,j}$ functions), and (2) the constant in the regret of Algorithm 1 is also $\Omega(\frac1{\kappa^2}$ (see Line 592). Please explain this issue briefly as [41] adopts a quite similar method and this work indeed outperforms [41] in practice.

4, In Line 139, I think it is not a proper way to describe the probabilistic distribution like this: As the authors only specified the probability of product $j$ being purchased, a straightforward question could be: how are these purchases correlated to each other? Of course, we know from context that these purchases are mutually exclusive and the probability is a multinomial on these products, but this could still be very misleading. I suggest the authors clarify this part by saying "the customer purchases one product $j\in[k_t]\cup 0$ ...".

5, There should be an explanation on Assumption 2.3. My understanding: price elasticity (or "price sensitivity" in this work) should not be too small (i.e., close to 0). This is reasonable and practical, but needs explanation.

6, In Line 166, where does this $\lambda$ sequence come from? This makes the adjacent paragraph (Line 166-169) unclear. (A minor issue: for the convexity of $l_t$, either prove it or cite it.)

7, In Line 196, the author said that they treated $K$ as a constant. This is important for regret analysis and comparison, so I suggest the authors to make it as an assumption and state it with other assumptions (e.g., after Assumption 2.3).

8, In Line 219, the author said "it is meaningful only with random price experimentation". This seems not very clear to me. Does it mean that you have to further make use of the randomness of $p_{t,j}$ to upper bound the first term of (1)?

Maybe an equation showing how to apply Lemma 2.6 to the proof of Theorem 2.4 would be more informative and concise.

9, In Line 257, the author denoted the "optimal assortment" as $S_t^*$. My understanding: $S^* = \arg\max_S q_{t,j}(S, \theta^*)$, i.e., minimize the prob of choosing nothing. This is equivalent to maximizing the sum of $exp\{x^{\top}\theta\}$? Is that right?

Besides, I noticed a number of notation inconsistence in this paper. Therefore, I strongly recommend the authors to carefully examine the paper and fix all notation issues.
limitations: The authors indeed discussed the potential extension of this work (e.g., "the nested logit model" as mentioned in their conclusions). However, there's not much on the social impact. This is not a big issue as it is a theoretic-oriented research, but I recommend the authors to discuss more on the limitations and potential social impacts (especially these negative aspects) in their Appendix.
review_title: null

Meta-review: metareview: In this paper the authors study the problem of dynamic multi-product pricing and assort under the Multinomial Logit model (MNL). For multi-product pricing problems, they propose the Online Newton method for multiple product pricing  with provable regret bound of O(d\sqrt(T)\logT). For the assort problems, they proposed OFU-MNL with better dependency on the problem-dependent parameter.

Overall, the authors have done a good job addressing the reviewers' concerns. While there is still lots of things to do in order to update the paper to meet the suggestions of the reviewers, I think this is a good paper and worth being published at NeurIPS, subject to the aforementioned edits.
confidence: Certain
Decision: Accept