Contextual Dynamic Pricing with Heterogeneous Buyers

Thank you for taking the time to review our submission and for the clarifying questions.

Thank you for the suggestion. We will include a table before “Basic pricing facts” in Section 2 summarizing all of the main notation (rev, dem, proj, br, etc.).

Yes, the techniques extend to a broader class of pricing problems. As noted in Appendix C.1, we present a more general formulation involving a class of contextual demand functions that are not necessarily Lipschitz. Provided that the disagreement coefficient of this class is bounded, our algorithm yields a regret guarantee that scales with the disagreement coefficient.

Thank you for taking the time to review our submission and for the clarifying questions.

Weakness, overly technical: As suggested by the reviewer, we will update the writing of the paper to present more intuition for the algorithms/concepts and move more of the technical analysis to the appendix. In particular, for the disagreement coefficient, we will add the following:

"In our application, each function $f$ will represent the gap between the demand function predicted by some model $D$ and that of the true model $D\_\star$, for a fixed context. In our analysis, the distribution $\nu$ will be supported on prices which our algorithm estimates to be near-optimal based on historical feedback. The disagreement coefficient is small if, by playing price $p$ sampled from $\nu$, it is unlikely for any model $D$ to disagree substantially with $D\_\star$ at $p$ if this model agrees with $D\_\star$ on average."

This is inherently a bit tricky to conceptualize due to the nested quantifiers, but we emphasize that the disagreement coefficient is a standard quantity of interest in active learning and empirical process theory (see the existing Remark 3.7).

In Section 4, we will remove the technical lemmas (4.2 and 4.3) and extend the discussion after the theorem to better describe the variance-aware zooming dimension and why it can be significantly smaller. The key here is that, when expected revenue at a price is small, so is the variance of the revenue at this price.

In Section 5, we will update the discussion after Theorem 5.2 to be less technical, instead focusing on the high-level fact that best responding to historical data leads to dependence on the VC dimension of the relevant function class.

Q1, cover details: $\mathcal{D}$ is taken to be a large set of distributions such that every distribution $D$ over the type space $\Theta$ is close to some $D’ \in \mathcal{D}$ under the Levy distance. See Appendix C.9 for the precise construction, where we specify “close” and also construct the needed nonuniform prior over $\mathcal{D}$. Since the exact details require some careful parameter tuning and several concerns were raised about Section 3 being too technical, we prefer to leave the full construction in the appendix. However, we will add a pointer after introducing $\mathcal{D}$ to this appendix section to direct the reader to a more detailed discussion.

Thank you for taking the time to review our submission and for the clarifying questions.

Thank you for pointing out [1], we will update our literature review to include their work.

Regarding Q1, this is an interesting question. We first note that our bound on the disagreement coefficient extends even to unbounded type distributions (it is a consequence of monotonicity and a bounded number of jumps for the demand functions). That being said, our bound on the covering number requires that the support of the types is bounded. However, if instead of being supported in the unit cube, the types were supported in $[0,R]^d$, we would still get a covering number bound of $\widetilde{O}(d K\_\star \log(R/\varepsilon))$, leading to regret $\widetilde{O}(K\_\star \sqrt{d T \log R})$ with only logarithmic dependence on $R$. If one imposes additional structure on the type distribution, this would be reflected in a smaller covering number and lower regret. We will add a short remark to this effect at the end of Section 3.2.

Regarding Q2, our attempts to generalize the analysis of Section 4 to higher dimensions encountered a number of significant challenges. It is difficult to maintain uncertainty sets in high dimensions without incurring an exponential dependence in the dimension. While this is achievable for $d=1$, a key difficulty for $d > 1$ with multiple types is that you do not know which type the feedback you obtain at time $t$ corresponds to. This is why, in Section 5, we consider a model where types are identified, allowing for simpler, more efficient algorithms. Currently, we lack substantial evidence to make a conjecture on the optimal regret.

Thank you for taking the time to review our submission and for the clarifying questions.

Weakness, exponential cover: Yes, the cover is exponential in $d$, and Algorithm 2 is statistically efficient but computationally inefficient (as stated in the intro to Section 3). In this case, even designing a statistically efficient algorithm required significant care. These computational issues were the motivation for Section 5, where we incorporate additional information in order to design computationally efficient algorithms.

Weakness, infinite types case: You are correct to point out that the submission did not treat infinite $K\_\star$ in the contextual setting — we explored this regime but ended up removing the relevant remark due to space. We will add the following back to the end of Section 3.3 in the revised manuscript:

"Large/infinite $K\_\star$: Our lower bound above can be restated as $\Omega(\min\\{\sqrt{K\_\star d T}, d^{1/3}T^{2/3}\\})$. When $K\_\star = \Omega((T/d)^{1/3})$ and the second term is active, POPS no longer has an advantage over EXP4 with naively discretized actions. In particular, one can run EXP4 with a policy cover of log cardinality $\widetilde{O}(d \varepsilon^{-2})$ and price set $\{\varepsilon,2\varepsilon, \dots, 1\}$, incurring regret overhead $\varepsilon T$ due to discretization. This gives a regret bound of $\widetilde{O}(\sqrt{Td^2\varepsilon^{-3}} + \varepsilon T)$, which balances out to $d^{2/5}T^{4/5}$ after tuning. Characterizing the optimal regret in this large $K_\star$ regime is an interesting question beyond the current scope."

In the non-contextual case, Theorem 4.1 features a worst-case $T^{2/3}$ bound which holds for all $K\_\star$ (even infinite).

Weakness, non-contextual contribution: The non-contextual setting in the paper is significant in trying to understand what the optimal dependence on $K\_\star$, the number of types, is. For the contextual setting, we obtain regret $K\_\star \sqrt{dT}$ but are unable to achieve $\sqrt{K\_\star dT}$. However, our $d=1$ result shows that $\sqrt{K\_\star}$ dependence is possible in some cases. Moreover, our $\sqrt{K\_\star T}$ bound closes a gap in the existing literature on dynamic pricing with finitely many types, fully resolving the optimal regret up to logarithmic factors. As discussed in Remark 4.4, the recent work of Cesa-Bianchi, Cesari, & Perchet includes an additional instance-dependent term that can explode to infinity. Finally, we believe that our algorithmic methodology and analysis, which replaces the standard zooming dimension with a smaller variance-aware dimension, may be of independent interest.

Thank you for taking the time to review our submission and for the clarifying questions.

Q1, added noise: In the presence of such added noise, our existing analysis mostly goes through, except for the bound on the disagreement coefficient. This noise smooths out demand functions, and we would then require a bound on the disagreement coefficient for the induced family of smoothed demand functions. When the noise has low variance, matching our existing disagreement coefficient bound is still possible (after introducing price discretization). In fact, our extension from a finite to infinite model class in Section 3.2 employs such an argument (see end of proof in Section B.6). The analysis there can tolerate bounded noise up to scale 1/T, without worsening our regret bound. A slight extension of this argument can extend to sub-Gaussian noise of the same scale. We will add a remark summarizing this explanation for the noisy setting to the end of Section 3.2.

We suspect that noise at substantially larger scales would worsen the achievable regret, but an exact characterization of this question is beyond the current scope. We remark that a noise threshold of 1/T appears in previous literature on contextual search with a single type, while noise at much larger levels leads to a jump in regret from logarithmic to polynomial. We expect that a similar jump arises in our setting but this is definitely an intriguing open direction and we will explicitly add it as an open question.

Q2, clarity: We apologize for the confusion regarding notation. We will tweak the introduction of the projection operator as follows:

"Once we restrict to a fixed context $u \in \mathcal{U}$, each type $\theta \in \Theta$ induces value $v = \langle u,\theta \rangle$. Thus, each type distribution $D \in \Delta(\Theta)$ induces a projected value distribution $Q = \mathsf{proj}(D,u) \in \Delta([0,1])$, where $\mathsf{proj}(D,u)$ denotes the probability law of $\langle u,\theta \rangle$ when $\theta \sim D$."

Moreover, we will add a table in Section 2, before “Basic pricing facts”, which contains all of the main notation terms with their definitions (proj, rev, dem, gap, etc.).

We will seek to include clarifying explanations where appropriate throughout the paper. In particular, for the disagreement coefficient, we will add the following:

"In our application, each function $f$ will represent the gap between the demand function predicted by some model $D$ and that of the true model $D\_\star$, for a fixed context. In our analysis, the distribution $\nu$ will be supported on prices which our algorithm estimates to be near-optimal based on historical feedback. The disagreement coefficient is small if, by playing price $p$ sampled from $\nu$, it is unlikely for any model $D$ to disagree substantially with $D\_\star$ at $p$ if this model agrees with $D\_\star$ on average."

This is inherently a bit tricky to conceptualize due to the nested quantifiers, but we emphasize that the disagreement coefficient is a standard quantity of interest in active learning and empirical process theory (see the existing Remark 3.7).

Q3, experiments: Unfortunately, there are significant limitations to performing meaningful experiments (beyond fully synthetic ones which simply verify the theorem statements). Indeed, while there are large datasets containing purchase records of the form “item - buyer - price - purchase decision”, the buyers’ values are unavailable. Thus, in order to determine purchase decisions for prices not used in the dataset, we must simulate buyer behavior. One could fit a $K\_\star$-types model to the dataset, and then use this for simulations/evaluation, but such an experiment would not tell us whether or not the performance of POPS translates to practice (since we are using the $K\_\star$-types assumption to simulate). In summary, it is non-trivial to design a proper experiment for our setting due to the necessary reliance on synthetic purchase feedback, and we view this as beyond the scope of this work.