Summary
This paper studies the problem of online contextual pricing under a linear noisy valuation model, with the noise distribution **unknown** to the seller. This work proposes an "exploration-then-elimination" algorithm that achieves $O(T^{2/3})$ **optimal** regret under the assumptions of (1) stochastic feature sequence, (2) Lipschitz noise CDF, and (3) bounded feature norm and noise range. Besides, this work also studies the non-parametric $\beta$-Holder valuation model, and propose an algorithm that achieves $O(T^{d+2\beta/d+3\beta})$ regret.
Strengths
1, The problem of contextual pricing problem has been extensively studied over the past few years. However, the minimax regret of linear noisy valuation model with unknown noise distribution is a long-existing open problem. Existing works leave a gap between $O(T^{3/4})$ and $\Omega(T^{2/3})$ under the assumption of Lipschitz noise CDF. This work closes the gap by showing that $O(T^{2/3})$ is the correct minimax regret, under certain assumptions.
2, This work also considers the non-parametric $\beta$-Holder valuation model, and propose an algorithm that achieves $O(T^{d+2\beta/d+3\beta})$ regret. This problem is relatively new to the community but it is important as well. In most of the cases, we cannot rely on the correctness of a linear model (although it is causally sound), and therefore this non-parametric model is of significance.
Weaknesses
1, The algorithm, VAPE, proposed in this work is quite similar to the "Explore-then-UCB" algorithm in Luo et al. (2022, Neurips). Seems like the authors are unaware of this work at all. The only difference is that VAPE adopts a policy-elimination design in the second stage after uniformly pure exploration, while Luo et al. (2022) uses a UCB-style strategy. From the perspective of regret analysis, I do not think there are much difference between those two methods. I then went back to the previous work and looked into their regret analysis, and noticed that they were using a linear bandit model instead of a multi-armed bandit (which is also applicable), which brings an extra $\sqrt{\frac1{\Delta}}$ multiplier on the regret of the second stage, where $\Delta$ is the discretization grid size. In other words, by slightly modifying the "Explore-then-UCB" algorithm, it is able to achieve $O(T^{2/3})$ regret instead of $O(T^{3/4})$ as they claimed. Since both of your works share the same idea of uniformly-pure-exploration stage for an unbiased estimate of $x^\top\theta^*$, which actually originates from Fan et al. (2024, JASA), I am skeptical to the novelty of this work, especially from the perspective of methodology.
The authors are encouraged to discuss how their methods and analysis are different from Luo et al. (2022) in the rebuttal. This is the major concern that I (and other reviewers as I expect) would have.
2, The authors claim that it is required to assume Lipschitzness on the noise CDF, which is commonly applied except for Xu and Wang (2022, Aistats). It is worth noting that Xu and Wang (2022) have proposed an insight on the "Half-Lipschitz" nature of a pricing problem, indicating that the regret rate would not be different with or without Lipschitz assumption.
If this is not applicable, the authors are encouraged to explain in the rebuttal how the "Half-Lipschitz" nature does not work.
References:
Xu, Jianyu, and Yu-Xiang Wang. "Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.
Luo, Yiyun, Will Wei Sun, and Yufeng Liu. "Contextual dynamic pricing with unknown noise: Explore-then-ucb strategy and improved regrets." Advances in Neural Information Processing Systems 35 (2022): 37445-37457.
Fan, Jianqing, Yongyi Guo, and Mengxin Yu. "Policy optimization using semiparametric models for dynamic pricing." Journal of the American Statistical Association 119.545 (2024): 552-564.
Questions
The authors are encouraged to respond to the following questions at a secondary priority (i.e. after kindly answering my questions in "Weaknesses").
1, Regarding Weakness 1, is there any necessity to apply a policy eliminiation strategy in stage 2 of VAPE? Can it be replaced by a (version of) UCB without impairing the regret rate?
2, On Page 5 Line 196, Please kindly explain the difference between your work and Fan et al. (2024) for valuation estimation methods in details.
Limitations
The authors have discussed the limitations in their Conclusions. Overall, this is a theoretic work and there are not much societal impact involved. However, the authors are encouraged to discuss more on the societal aspect of the work, e.g. personalized pricing and unfairnesses.