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: This paper studies dynamic pricing with contextual information under linear customer valuation model. The paper considers two types of market noise distribution and proposes a unified algorithm for the two types. The proposed algorithm is nearly optimal for one type and improve existing algorithm for the other. The paper also establishes a new lower bound and conducts numerical experiments.
strengths_and_weaknesses: Strengths:
The paper is well written and well organized. For Lipschitz and concavity market noise, the paper improves the existing regret bound and provides a better lower bound. The theoretical result is also verified by numerical experiments.

Weaknesses:
The time and space complexity of the proposed algorithm is unclear, which may hinder its practical applications.
questions: How to configure the hyperparameters $C_1$ and $C_2$ of ExUCB in practice?
limitations: Yes
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 studied the problem of contextual pricing problem with the customer's evaluation is linear in the context, with an unknown market noise $F$. The paper proposed an ExUCB policy to tackle this setting, 1) with Lipshitz and concavity smoothness assumptions, the ExUCB algorithm achieves $\tilde{O}(T^{2/3})$ regret. 2) with only Lipschitz smoothness assumptions, the ExUCB matches the best existing upper bound as $\tilde{O}(T^{3/4})$. Additionally, the paper gives proof of the lower bound of $\tilde{O}(T^{3/5}$ ) for the Lipschitz and concavity smoothness assumptions. 
strengths_and_weaknesses: Strengths:
1. The presentation of this paper is super clean, i.e., with table (Table 2) and figure illustration(Figure 1), and the descriptions of the algorithms are clean. 

2. The paper carefully analyzes the behavior of ExUCB under different settings with different algorithm parameters, which implies the generality of the proposed algorithm.

3. The paper also provides a regret lower bound under the Lipshitz and Concavity smoothness, and clearly explain the intuition behind the proof of the lower bound. 

4. The paper clearly states their assumptions' generality with citations of recent literature.

5. The paper illustrates the algorithm's empirical performance. 

Weakness:

No conclusion section. [Addressed in the rebuttal period. ]

Minor Issues:
1. Some of the theorem statement is incomplete:

-- [line 252-253] proposition 1:it should be "there exists positive $C_1', C_2'$ \emph{and $C_3'$}'"

2. Section 3.1 lists many assumptions without connecting paragraphs between them.

questions: 1. In Table 1, what is the range of $\alpha$?

2. How is this setting different from linear bandit?
limitations: If this paper can include a conclusion section in the end, that would be great.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studies the learning of posted prices in a bandit setting with buyer valuations having a linear structure + noise. They provide regret guarantees under different sets of assumptions on the distribution of the noise. When the noise cdf F is only Lipschitz, it recovers the upper-bound guarantee $\tilde{O}(T^{\frac{3}{4}})$ of [48]. If the expected revenue function (under F) additionally satisfies a strong-concavity property locally at its maximum, this work provides a $\tilde{O}(T^{\frac{2}{3}})$ regret guarantee that improves over the $\tilde{O}(T^{\frac{2}{3}\vee (1-\alpha)})$ from [35]. Finally, it formalizes the $\Omega(T^{\frac{3}{5}})$ lower-bound hinted in [35] for the same assumptions.
strengths_and_weaknesses: In my opinion, the paper has mainly two contributions that concern the second set of assumptions where the expected revenue is "locally strongly concave":
1. Improving the upper-bound of [35]
2. Providing a lower-bound

My main critic is about the significance of the first contribution. Indeed, the algorithm follows a similar doubling trick period split as [35] and it feels like a strait-forward extension: 
1. It is possible to perform pure exploration on $O(\ell_k^\beta)$ samples per period without impacting the regret guarantee as long as $\beta \leq \frac{2}{3}$ (so the additional regret is bounded by $\tilde{O}(T^{\frac{2}{3}})$)
2. these $\ell_k^\beta$ can be used to estimate $\hat{\theta}_{k+1}$ which by Hoeffding concentration will lead to $\|\hat{\theta}_k - \theta_0\|_1 = O(\ell_k^{-\frac{\beta}{2}})$
3. Remember the proof of [35] ensures that: If the estimate $\hat{\theta}_k$ is such that $\|\hat{\theta}_k - \theta_0\|_1 = O(\ell_k^{-\alpha})$, then the regret is bounded by $\tilde{O}(T^{\frac{2}{3}\vee (1-\alpha)})$. 
4. Using $\alpha = \frac{\beta}{2}$ and choosing $\beta = \frac{2}{3}$ leads to an upper-bound on the regret that is $\tilde{O}(T^{\frac{2}{3}})$
Except for this additional exploration, the algorithm is very similar to [35].


Then, the paper is hard to follow. A couple of examples:
* The perturbed linear bandit is introduced at the very beginning, at this point, it's hard to make the link with the problem. This link is only explained much later in the paper page 7.
* It's a bit hard to understand the role of the discretization without reading [35]
questions: I'm not sure to understand why the knowledge of $T$ is so crucial to need to use a doubling trick:
* Anytime concentration inequalities are usually used so UCB does not need the knowledge of $T$
* The exploration can be done continuously over time by choosing to explore with proba $t^{-\frac{1}{3}}$ at each time step $t$

I know this remark also applies to [35] so I probably missed something.


limitations: I don't see an obvious limitation / negative impact that is relevant.
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 an online contextual dynamic pricing problem with linear-noisy valuations and Boolean feedback.

The author introduces an algorithm, ExUCB, that is a combination of epsilon-greedy and Upper Confidence Bound algorithms.

They show that their algorithm would achieve an $\tilde{O}(T^{\frac23})$ regret upper bound under Lipschitz and "concavity"(see Strengths and Weaknesses session below) assumptions, which improves existing results substantially. They also show that ExUCB would achieve an $\tilde{O}(T^{\frac34})$ regret upper bound under a Lipschitz assumption only, which matches existing results but with a more efficient algorithm. They also have an $\tilde{\Omega}(T^{\frac35})$ lower bound for the Lipschitz and concavity setting.

They finally presents numerical results that matches their theories.
strengths_and_weaknesses: Strengths:

 (1) First of all, the theoretical result on this problem (especially Case (a)) is better than existing works. Two existing works [23] and [35] introduced \epsilon-greedy and UCB methods for pricing sequentially, but each of them suffered suboptimality and is hard to improve. This work eases these suboptimalities by subtly combining them with each other! 

(2) They also improve the algorithm computational efficiency on Case (b) where their result matches existing best results (under additional assumptions) but not improve, which lets their algorithm more practical.

(3) Their lower bound is developed based on existing methods but still meaningful.

(4) Their numerical experiments matches their theoretical results very tightly.

(5) Their writing quality is good.


I think this work should be worth at least 7, as they indeed improve existing results in an interesting way. However, there are still some doubts on my side. I'll tentatively give a 6 and promise to rise my score as long as the authors address my concerns.

Weakness: 

(1) (This is a question, but seems rather important.) What they claimed in Assumption 7 is actually a 2nd-order-smooth instead of  a concavity. See [15]: they have both upper and lower constant bound on the 2nd-order derivatives at p^* by assuming both smoothness and concavity, but you only have upper bound (i.e. smooth). Please check if this affects any of your claims or the fairness of any comparison with existing results (e.g., is your lower bound still unique).

(2) Assumptions are slightly more than mild. E.g., Assumption 2 (especially the condition number lower bound $c_0$) is not assumed in some of [15,23,26,28,35,48]. Assumption 5 can be implied by 4. (P.S., Assumption 3 combining with Assumption 4 is indeed exactly a bounded noise assumption in [23,26,48].)

(3) Missing of results and/or discussions in some related works. E.g., [44] has an $\Omega(T^{\frac{m+1}{2m+1}})$ lower bound that can fill in the blank of Table 1. E.g.2., Some works in contextual searching should also be briefly discussed, including:

      [a.1] A. Liu et al. Optimal contextual pricing and extensions. (SODA-21)

      [a.2] A. Krishnamurthy et al. Contextual search in the presence of irrational agents. (STOC-21)

Their various assumptions on the noise distributions need discussing.
questions: Questions:

(0) Recall my question above regarding Assumption 7: is it really a concavity assumption, or smoothness instead?

(1) What are the regret dependences on the feature dimentionality $d_0$? Are they still polynoimal, or they have to become exponential? To be optimal is not required, but this would contribute to the comparisons with other exisiting results on the same problem setting.


Suggestions:

(1) The discussions in Remark 1 on the $\Omega(T^{\frac35})$ lower bound of [35] should be earlier (i.e., in Introduction or Literature Review). This would cause misunderstandings as you also have a $\tilde\Omega(T^{\frac35})$ lower bound.

(2) It would make sense to highlight your ExUCB algorithm on the computational efficiency even it matches instead of improving the existing result of [48].

(3) Notations $d_0$ and $d_k$ for $k=1,2,\ldots, n$ are easy to confound. Maybe replace one of them instead.
limitations: Yes. They mentioned their limitations and discussed the ethic issues related to their paper. It would be better if a discussion/conclusion session occurs at the end of the main pages.
review_title: null

Meta-review: metareview: The authors make multiple contributions in this work. Under a Lipschitz and second order smoothness assumption, their algorithm ExUCB obtains regret of order $\tilde{O}(T^{2/3})$, which is an improvement upon a recent result of Luo et al. (2021) that has an additional dependence on a parameter $\alpha$. In addition, under a Lipschitz assumption, the authors’ algorithm matches the best known regret of $\tilde{O}(T^{3/4})$. In summary, the authors give a theoretical advancement over previous work; notably, in the Lipschitz case, their improvement in terms of computation is exponential (going from exponential in dimension $d_0$ from EXP4 to $\mathrm{poly}(d_0)$ for ExUCB.

In the discussion period, there was some disagreement with regards to the novelty of the design of ExUCB. One reviewer whom I believe has sufficient experience mentions that a Explore-then-UCB structure is standard in bandits. Yet, another reviewer highlighted that the execution of this strategy in this particular case is considerably more complicated due to additional challenges, with the exploration phase not being similar to warm-up periods sometimes used for multi-armed bandit algorithms. I tend to believe that there indeed are additional challenges posed here and that there is sufficient novelty. In light of the advances the authors have made in terms of improved regret bounds and improved computational efficiency, this work merits publication and should be accepted.
confidence: Certain
Decision: Accept