Venue: NeurIPS 2022 Conference

Reviews:

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: The paper studies an online learning and contextual pricing problem with semi-parametric partially linear demand models, where the demand function is the sum of a linear function with an unknown coefficient(s) of price (or context, resp.) and an unknown function of the context (or price, resp.). For the above two demand models, the paper develops two corresponding online pricing algorithms with provable regret upper bounds and matching lower bounds with respect to the horizon $T$.
strengths_and_weaknesses: Strengths:
Overall, the paper is well-written. 
Formulation-wise, the paper generalizes the commonly used Lipschitz continuous assumption to Holder continuity. Importantly, the results show that the additional structure of linearity indeed improves the regret bound. 
Algorithm-wise, the paper combines several online learning techniques, including binning and approximation, random shock in pricing, and upper confidence bound algorithm, so as to estimate the non-parametric part of the demand functions. 
Analysis-wise, the paper gives a comprehensive analysis of the statistical complexity/regret of the formulated problems.

Weakness: 
 1. In Algorithm 2, when solving the UCB optimization problem in line 10, what is its complexity? And in general how to solve it (efficiently)?
 2. The algorithms seem to require the knowledge of $\beta$ and $k$, the authors should state these explicitly in the assumptions and discuss how to estimate these quantities when there is no such prior knowledge. 

Minor comment:
Upon reviewing the literature, the paper misses one stream of works related to semi-parametric dynamic pricing (see below). The author should discuss the contribution against these works.
- Policy optimization using semiparametric models for dynamic pricing (Fan et al. 2021)
- Distribution-free contextual dynamic pricing (Luo and Sun, 2021)
- Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise (Xu and Wang, 2022)

Also, the authors should mention that the matching of lower bounds refers to the dependency on $T$ but not with respect to $d$. As in the discussion of Theorem 4, one of the lower bounds doesn't meet the corresponding upper bound in the context dimension.
questions: I hope the author can address in the rebuttal the two points mentioned in the weakness above and I may adjust my final rating based on the response. 
limitations: NA.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies two online contextual dynamic pricing problem settings: DPLPE where demand is linear wrt price, and DPLCE where demand is linear wrt context. For DPLPE problem, they assume the realized demand $D_t = bp_t+g(x_t) + \epsilon_t$ with $g(x)$ being $\beta$-Holder continuous and $\epsilon_t$ being a subGaussian noise. They propose an ADPLP algorithm that adopts a space binning and a random shock techniques. With ADPLP, they achieve an optimal $\tilde{O}(\sqrt{T}\vee T^{\frac{d}{d+2\beta}})$ regret up to logarithmic factors by proving both the upper and the lower regret bounds, where $d$ is the dimentionality of features. For DPLCE problem, they assume the realized demand $D_t = f(p_t) +a^{\top}x_t + \epsilon_t$, with $f(p)$ being $k^{\text{th}}$-order smooth with a small parameter $\delta$ that could be $T$-dependent. They present an ADPLC algorithm that adopts a local polynomial approximation and a biased linear contextual bandit with an optimistic OFU strategies. With ADPLC, they achieve an optimal $\tilde{O}_d(\sqrt{T}\vee(\delta T^{k+1})^{\frac1{2k+1}})$ regret up to logarithmic factors, by proving both the upper and the lower regret bounds. Finally, they conduct numerical experiments and show that the simulation results of ADPLP and ADPLC ourperform all benchmarks.
strengths_and_weaknesses: Strengths:

(1) This work generalizes the problem settings of both linear demand and linear context problems. For DPLPE, they consider $\beta$-Holder class instead of only Lipschitz that was broadly assumed by previous works, and they improve the comparison by replacing the linear benchmark with the true demand function in [8] and [23]. For DPLCE, they consider $k$-th-order smooth with not only integer but also non-integer $k$'s, and they also emphasize the role that $\delta$ plays instead of treating it as a constant as previous works did.

(2) For both DPLPE and DPLCE, they design algorithms with provable optimal regret bounds. These results are significant as they not only match the order of $T$ but also those of $\beta$ and $\delta$. Moreover, for DPLCE, their upper and lower bound match those in [30], indicating that a linear context added on the demand curve might not require substantially more information to learn.

(3) Their numerical experiments are comprehensive and the results are well-displayed.

Weaknesses:

(1) Some related literatures should be discussed with more details. For example, the stream of binary demand model. As this work also assume a noisy feedback, the only difference of binary feedback is that the noise distribution is dependent on $p$ and $x$ while this work assumes iid. Since the closely-related work [30] also assumes a binary feedback, the results of this work do not actually cover those in [30]. Overall, the binary feedback is an important property in many pricing problem settings, and I suggest the authors to be aware of this issue and place this paper in the related literatures with more precision.


questions: Questions:

(1) See the related work issue I mentioned above. Maybe a good idea is to list these key properties/assumptions in categories (like what they did in [30] Table 1).

(2) Notice that ADPLC require knowledge on the noise std $\sigma$. Does ADPLP require it as well? It is sometimes decisive to assume a parametric or non-parametric noise in an online learning problem, so I suggest the authors to specify these properties in detail, and briefly discussion how they contribute to your analysis and results.

Minor suggestions:

(1) Avoid notation repeatance: e.g., $d$ for feature dimension and also for expected demand.

(2) A few typos: e.g. line 42: $x_t\in[0,1]^d$.

limitations: Limitations and potential extensions of this work are well discussioned. 
There is no discussions on social impact as it is a work of theory. However, I indeed suggest the authors to consider any potential ethic issue that might occur in a pricing problem with these assumptions you have specified.
review_title: null

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 studies the context-based dynamic pricing, where the unknown expected demand admits a semi-parametric partially linear structure. Two special cases of semi-parametric partially linear models (Linear Pricing Effect and Linear Contextual Effect) are considered. Two new algorithms (DPLPE and DPLCE) are proposed and their regret upper bounds and matching lower bounds are established. 

strengths_and_weaknesses: Strengths

(1) In spite of a theoretical paper, it is well written and easy to follow. 

(2) The proved matching lower bound is useful to understand the limit of the considered problem. 


Weaknesses

(1) Technical novelty: The proposed partially linear demand model is a natural extension of existing linear demand model and nonparametric demand model. On the other hand, a similar partially linear demand model has been proposed in dynamic pricing literature, see below. None of them was mentioned in the paper. In fact, these papers consider a binary choice model which is arguably more challenging than the one considered in this paper. 

Jianqing Fan, Yongyi Guo, Mengxin Yu (2021), Policy Optimization Using Semi-parametric Models for Dynamic Pricing, https://arxiv.org/abs/2109.06368. 

Jianyu Xu, Yu-Xiang Wang (2022), Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noise, AISTATS 2022. 

(2) The proposed algorithm and theoretical analysis require the knowledge of some true parameters, e.g., the upper and lower bounds of price, the upper and lower bounds of the true price coefficient, The continuous parameter $\beta$ of the unknown function $g$. In practical pricing applications, knowing upper and lower bounds of price is arguable and a mild assumption. But it is less justifiable to know the bound of $b$ and $\beta$ in practice. 

(3) It is unclear what assumptions were assumed in the main Theorems (Theorems 1-4). In addition, when the authors compare the proved regret bounds with those in the literature, it is also important to discuss if their model assumptions are comparable. It would be more convincing if the faster regret bound is not obtained under much stronger assumptions.

(4) The experiments of this paper only study the performance when the true model is the proposed partially linear demand model. No model misspecification was studied. It is unclear if it is always safe to use the proposed algorithm in practical pricing applications. 

~~~~~~~~~~~~~
After rebuttal: Thanks the authors for carefully addressing all my concerns. My last three comments have been nicely addressed. I have raised my rating to Borderline Accept. On the other hand, while I understand the difference (e.g., nonparametric on noise v.s. nonparametric on covariates; binary feedback v.s. continuous feedback) of this paper compared to existing pricing literature with partial linear demand model, I am not fully convinced by the "technical novelty" beyond them. So I choose to only increase the rating to Borderline Accept.



questions: (1) It is important to discuss the technical novelty of this paper beyond existing semi-parametric dynamic pricing papers. 

(2) It is important to provide some guidance on how to choose the unknown parameters (bounds of $b$, $\beta$, etc) in a data-driven way. It is also helpful to study the sensitivity of the choice of these parameters in experiments. 

(3) It is helpful to list all assumptions used for the theorems. When discussed with regret bounds in the literature, it is important to also mention the difference in the assumptions. 

(4) It is important to study the model misspecification case, e.g., when the true model is linear or purely nonparametric, in the experiments. 



limitations: No potential negative societal impact was discussed in the checklist. No limitation was discussed in the paper.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the contextual dynamic pricing problem under partially linear structural assumptions. In particular, the authors consider two demand models **DPLPE** and **DPLCE**. The former assumes a linear term in the price with an additive $\beta$-Holder continuous function of the context. The latter assumes a linear term in the context with an additive $k$-th order smooth function of the price.
The authors present two online algorithms and provide regret upper bound as well as lower bound guarantees for each of the models:
1. **DPLPE**:
   - upper bound of $\mathcal{O}\left(\sqrt{T} + \ln T\cdot T^{\frac{d}{d+2\beta}}\right)$.
   - lower bound of $\Omega\left(\max(\sqrt{T}, T^{\frac{d}{d+2\beta}})\right)$.
2. **DPLCE**:
   - upper bound of $\mathcal{O}\left(d\ln T(\sqrt{T} + (\delta T^{k+1})^{\frac{1}{2k+1}}))\right)$.
   - lower bound of $\Omega\left(\max(\sqrt{T},(\delta T^{k+1})^{\frac{1}{2k+1}}))\right)$.
strengths_and_weaknesses: **Strenghts**:
- The paper in general is well written and its contribution over previous works is presented clearly by the authors.
- The models considered in the paper are more general compared to known works and they provide new results on the problem of dynamic pricing.
- I find the algorithm design of both algorithms to be interesting and novel as it combines multiple ideas from previous works.
- The authors also provide lower bound guarantees which enhances the main results of the paper.

**Weaknesses**:
- As stated by the authors the lower bound in Theorem 4 is missing the dependence in $d$ which makes this lower bound less significant compared to the lower bound in Theorem 2.
- I believe that the problem setup can be presented more clearly for the reader with better formatting.
- I feel like the main text could benefit from a more comprehensive technical overview.
questions: As this paper presents theoretical results I find the Numerical Study section redundant and would suggest providing more background on the proof techniques used in the paper.
limitations: I don't see any potential negative societal impact.
review_title: null

Meta-review: metareview: The reviewers found the paper to be novel and interesting. The introduced model was found to be innovative and leading to cleaner/better regret bounds.  The only major concern that was raised and not resolved was lack of technical novelty. However, it seems that this work provides new and relevant results to the existing literature. And it seems that clean and fundamental techniques are indeed adequate for achieving the result of this paper.
confidence: Certain
Decision: Accept