Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: (Disclaimer: I have previously reviewed this paper for ICML 2021).

This paper develops algorithms for the problem of contextual dynamic pricing. This is an online learning problem that takes place over T rounds. There is a customer with a hidden value vector theta in R^d. Every round, the learner is given as context a feature vector x in R^d (both x and v are suitably bounded), representing the features of the current item. The customer is willing to pay up to v = <x, theta> + a Gaussian noise term for the item. The learner must set a price p for the item this round; if p > v the customer does not buy the item (and the learner receives 0 utility), otherwise the customer buys the item at price p and the learner receives p utility. The goal of the learner is to maximize their total learner (minimizing their regret compared to the optimal dynamic policy).

This paper presents two algorithms for two different settings. Their first algorithm (EMLP) applies when the feature vectors x_t are iid drawn from an unknown distribution. Their second algorithm (ONSP) applies when the feature vectors x_t are chosen adversarially. In both cases, they obtain O(d*log T) regret. Both algorithms require that the noise is Gaussian with a known variance sigma^2 (The authors show an O(sqrt(T)) lower bound if sigma is unknown). (In fact, this known variance sigma influences the constant in the O(d*log T) regret; see comments below). 

Roughly, both algorithms work by maintaining an estimate of theta, and submitting the expected-utility-maximizing price p (assuming the theta estimate is accurate) per round. The two algorithms differ in how they maintain their estimate of theta. EMLP divides the rounds into log T geometrically-sized epochs, and uses a MLE to recompute the value of theta at the end of each epoch. ONSP instead runs an online Newton step method each round to obtain an estimate of theta.

The authors additionally present some empirical simulations of their algorithms (on synthetic data), showing that they outperform EXP4.
main_review: I am generally positive about this paper: I think contextual pricing is a pretty interesting and important question, and I think this paper makes concrete and novel progress in developing algorithms in a noisy setting.

One concern from the previous submission of this paper was that it was missing important citations in the literature (namely a line of a recent work on contextual pricing and contextual search). The paper now contains a good discussion of how this paper significantly differs from the models considered in these papers (and as far as I can tell, I agree).

One other concern was that the regret of the authors’ algorithms depended in a significant (and non-intuitive way) on sigma -- in particular, as sigma gets small (less noise), the regret of their algorithms blow up. This was not made very clear in the earlier submission, but in the current draft there is now some discussion of this in section 7. This phenomenon still somewhat bothers me; it feels in some sense that the algorithms the authors present are mostly taking advantage of how the noise smooths out the reward function rather than dealing with the core difficulties of dynamic pricing, but I admit that this is still an interesting regime. 

The paper was well-written and easy to read. 

limitations_and_societal_impact: No concerns here.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the recently active problem of regret minimization in feature-based pricing.

main_review: In feature-based pricing, we have a buyer with a high-dimensional value theta that is held privately. Features x_t from the same dimension arrive online, and the value w_t for round t is <theta,x_t> + zero-mean-strictly-log-concave-noise. The noise is drawn i.i.d. from a known bounded strictly log-concave distribution (e.g., Gaussian noise). The buyer is posted a price p_t at round t, and buys when his value is at least the price, and rejects otherwise. The algorithm designer who posts the price gets to see only the features (before posting the price) and the binary decision of sale or no sale (after posting the price). The goal of the seller is to post a stream of prices that minimizes the revenue regret --- compare the obtained revenue with the optimal revenue obtainable had the seller known the hidden vector theta.

The paper studies two settings, one where the features are stochastic (drawn i.i.d. from an unknown distribution) and the other where the features are drawn adversarially. In both the settings, the paper gives algorithms that achieve O(d log T) regret.

I generally like this line of work as it provides a neat playground to develop good theory and techniques. Achieving a regret bound of O(d log T) in this model is a nice/clean result. Knowing the noise is a reasonable assumption and there is anyway regret lower bound of \sqrt{T} when not knowing the noise distribution.

My primary question is regarding the regret bound: what is the dependence on the level of noise in the regret bound of O(d log T)? To take a simple case, with Gaussian noise, when sigma approaches zero, can this paper get a O(d log T) bound? If not, is there a reason to expect that achieving O(d log T) regret is impossible when sigma is zero? A priori, it seems like getting O(d log T) is not impossible. The current writing conceals the dependence on the noise (or specifically sigma for the Gaussian case), and it is hard to figure out from the paper what the dependence on sigma is. Typically one would think that the less noise case is the easier one, and more the noise harder it is. But given the highly discontinuous nature of pricing loss, noise can help "smooth out". 

Regardless of the answer, there should be a clear discussion on the dependence on noise in the regret achieved. 

Another subtlety to point out is the somewhat unusual notion of regret: usually we talk about E[max], but here we have max E. In other words, rather than compare with the expectation of the ex post optimal policy that posts a price of w_t, the comparison is w.r.t. the price offering the maximum expected reward. While understandably, comparison w.r.t. the former will lead to a \sqrt{T} regret due to the variance induced by the noise, this is an important enough aspect that deserves to be discussed.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the feature-based dynamic pricing setting. This setting is a sequential setting in which in each round a learner is to predict the price of a product based on a feature vector. Then, if the customer's private value exceeds the price predicted by the learner, the customer buys the product. The goal is to control the difference between the difference between the cumulative price of the sold products and the best offline pricing policy. 

On of the main challenge in this setting lies in the feedback that the learner receives. Since the learner only sees whether or not a product is sold, he receives limited feedback about the customers private value for a product. To remediate this issue, the authors assume that the private value of the customer is the inner product between a unknown parameter vector and the feature vector plus some noise. Another important assumption is that the distribution of the the noise is known exactly and that both the cumulative distribution $F$ and $1-F$ are strictly log-concave. 

With this set of assumptions (plus some additional standard assumptions) the authors provide two new algorithms, one for stochastic feature vectors and one for adversarial feature vectors. Both algorithms rely on the fact that as soon as both $F$ and $1-F$ are strictly log-concave and $F$ is known, one can derive a surrogate loss which is almost quadratic. Because of the nice properties of this surrogate loss functions to show that the regret is $O(d \ln(T))$. 

The paper also contains a lower bound, roughly stating that as soon as the distribution of the noise is not exactly known, the regret has a $O(\sqrt{T})$ lower bound. 

Finally, the paper contains some experiments which compare the performance of the two new algorithms to EXP-4. 
main_review: The idea of using the log-concavity of the noise is nice and turns out to be quite effective in deriving small regret bounds. 

One of the arguments for using the new methods over previous methods is that existing results have regret bounds that scale are $O(\min\{\frac{1}{\lambda^2_{min}}\ln(T), \sqrt{T}\})$, where $\lambda_{min}$ is the smallest eigenvalue of the second moment matrix of the feature vectors, which can be arbitrarily small depending on the distribution of the feature vectors. Since there are also constants that depend on a distribution in the new bounds it would be nice to have some idea of how big this constants are. While in appendix C there are some lower bounds for the constants I would like to seem an upper bound as well to get an idea of how the new regret bounds compare with the literature. Also, note that for the Newton algorithm to work one needs to know the exp-concavity parameter of the surrogate losses, which seem to be tied to the same constants. So for the algorithm to have any practical relevance it would be a good idea to provide the constants for some common distributions. 

On a similar note, I think the statement in line 142-143 that the CDF might not be known is practice is acceptable is wrong. As demonstrated by the lower bound, even very small differences in between the assumed CDF and actual CDF may lead to $\sqrt{T}$ regret. Since it is not clear how either new algorithm reacts to misspecification of the noise, I do not think that we can claim that not knowing the CDF is acceptable in practice. 

I also have a slightly more technical question. I have not seen the requirement that $1-F$ is log-concave before and I wonder if there is a relationship between $F$ being log-concave and $1-F$ being log-concave. If not, is there a straightforward manner in which I can verify that for example a gaussian distribution satisfies the requirement that $1-F$ is log-concave?

Overall, the paper contains some interesting results. Although I doubt the practical relevance of the results I do appreciate the technique to use the log-concavity property to derive surrogate losses. I also appreciate the lower bound an it's implications. 

The writing could be improved as there are some unclarities. For example, upon my first reading I read assumption 2 as if the true parameter was known to us. In the sentence starting on line 74 it is unclear to me what "when we explain the results" means. There are also bothersome inconsistencies in the use of big $O$ notation. For example, in line 44 $d$ is included in the big $O$ notation but in line 49 it is not. In line 16 it is not clear to me what an acceptable price is and to me it seems that finding the price that is the most profitable is the goal. The $C$ used in Lemma 8 does not appear to be defined in equation 11. 

Minor comments
- I do not understand the "|" symbols in lines 295 and 294.
- line 226: $C$ and $C_{down}$ is defined --> $C$ and $C_{down}$ are defined.
- perhaps the greater than zero is unnecessary in equation (12) due to the definition of semi-positive definite matrices. 
- as a personal preference I try to avoid the use of obviously and clearly as whenever I do not understand statements which include either of these words immediately I always feel a little bit stupid. I do not think it would harm the paper if these words are removed so I suggest you remove them.
- line 131: till is perhaps too informal --> until  
- line 570: following --> follows
- line 561: curve --> curves
- line 536: In specific --> to be specific.
- line 536: a "." before Define is missing.
- line 537: there is a "." missing at the end of the sentence. 


----------------------------------
In the rebuttal the authors have adequately addressed my concerns and I have raised my score.
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: This paper studies the problem of feature-based dynamic pricing and offers strong new regret bounds. The headline result is the construction of Online Newton Step Pricing and the proof that it obtains regret $O(d \log T)$ even with adversarial features. This had been proven before only by assuming either (1) small noise or (2) iid features plus a minimum-eigenvalue assumption.
main_review: 
This paper studies the problem of feature-based (or contextual) dynamic pricing. There exists an unknown vector $\theta$ that characterizes a consumer's preferences. At every period $t=1,...,T$, a new product is on offer with a set of characteristics described by $x_t$. The consumer's valuation for this product is given by $\theta^\top x_t + N_t$, where $N_t$ is some iid noise from a known distribution. The problem is how to set a price $v_t$ such that the product will be sold if and only if $v_t \leq \theta^\top x_t + N_t$. 

There are two different variations of this problem depending on whether the feature vectors are drawn iid or are generated adversarially. For the adversarial features problem, Cohen, Lobel and Paes Leme (EC 2016 and MS 2020) proved a $O(poly(\log T))$ regret bound assuming the noise $N_t$ is small (of order $O(1/(T\log T))$. For the noise-free case, Paes Leme and Schneider (FOCS 2018) proved a $O(\log \log T)$ regret bound. For the iid case, Javanmard and Nazerzadeh (JMLR 2019) proved a $O(\log T)$ bound assuming the covariance matrix of the feature vectors has a smallest eigenvalue bounded away from zero. Note that, following the template of the discussion in the paper being evaluated, I am ignoring the dependance on the feature dimension $d$ in this paragraph.

This paper's main contribution is an algorithm called Online Newton Step Pricing (ONSP) that obtains $O(d\log T)$ regret for the adversarial version of this problem, without the small noise assumption (noise is assumed to be $O(1)$). The idea is pretty simple (though the proof isn't): use the log-likelihood as a loss function and then use online Newton's method to optimize it. 

The paper also presents a separate algorithm for the iid case, called the Epoch-based Max-Likelihood Pricing (EMLP) algorithm. This algorithm is the exact same as the one proposed by Javanmard and Nazerzadeh, except it replaces a Lasso regression with a standard one. They prove the same $O(d\log T)$ regret as Javanmard and Nazerzadeh for the iid case using this algorithm, without invoking any sort of smallest-eigenvalue assumption. The paper further proves that if the noise distribution is unknown, no bound stronger than $O(\sqrt T)$ is attainable.

This paper is impressive, and I support its publication at NeurIPS. I would say the paper is original, high-quality, clear and significant. Here is some feedback and questions:

1. What is the point of EMLP? ONSP can obviously also be used with iid features. Does EMLP offer any advantages?

2. The paper clearly dominates the earlier results of Javanmard and Nazerzadeh. They obtain the same regret bound without the eigenvalue assumption. They even do so with the same algorithm (EMLP). The main exception to the point is that the current paper does not have sparsity-related results, as it dropped the Lasso regression.

3. The paper also solves an open question in this literature: is it possible to obtain $O(d\log T)$ regret with $O(1)$ noise? They paper settles this issues affirmatively. In my opinion, this is an important result.

Typo: "vice versa" not "vise versa" on page 3.

limitations_and_societal_impact: As for limitations, the paper  makes an intriguing point in Section 7: the regret bound of ONSP and EMLP becomes worse as the noise becomes smaller. Noise is helpful because it makes the regret smoother and induces exploration. Therefore, their analysis does not apply if the noise is $O(T^{-\alpha})$ for $\alpha > 0$. Interestingly, we now have logarithmic regret bounds for $\alpha = 0$ from this paper and $\alpha = 1$ from Cohen, Lobel and Paes Leme, but we do not have logarithmic regret bounds for $\alpha \in (0,1)$.

As for potential negative societal impacts, the same algorithms that are proposed here for pricing a large collection of products could alternatively be used for personalized pricing, which could potentially be problematic depending on the situation. This point is properly disclosed in the appendix.
review_title: null

Meta-review: All the reviewers agree on the importance of the contribution. It is also my view that obtaining logarithmic regret is an important open problem in contextual pricing without any assumption of small noise. I am aware of many papers that tried to establish similar results but failed. 

The only concern shared by the reviewers is that the regret bound is inversely proportional to noise, but this was  adequately addressed this in the rebuttal by saying that larger noise leads to more exploration. The authors are encouraged to make this more explicit in the revision.

The review team is confident that this should be one of the top papers in NeurIPS and enthusiastically recommends acceptance.
Decision: Accept (Spotlight)