Contextual Pricing for Lipschitz Buyers

Jieming Mao, Renato Paes Leme, Jon SchneiderNeurIPS 2018 · OpenReview

Overview

This paper provides optimal algorithms and tight regret bounds for learning a Lipschitz function using only binary feedback (e.g., "was the guess too high or too low?"). The authors apply these theoretical results to the problem of contextual dynamic pricing, where a seller must set prices for differentiated products based on limited "sold/not sold" data, achieving significantly better performance than previous general-purpose bandit methods.

The Challenge of Contextual Pricing

Imagine a seller offering unique items, such as online ads or specialized products, to buyers. Each item has a feature vector $x$ (the context), and the buyer has a hidden valuation $f(x)$.

The seller faces two major hurdles:

  1. Binary Feedback: The seller doesn't see the buyer's actual valuation. They only observe whether the item sold at the posted price $p$. If it sold, $f(x) \ge p$; if not, $f(x) < p$.
  2. Asymmetric/Discontinuous Loss: In pricing, if you price $1\phi$ above the buyer's valuation, you get $0$ revenue (a large loss). If you price $1\phi$ below, you lose only $1\phi$ in potential profit.

While previous work often assumed valuations were linear functions of features, this paper explores the more realistic—and difficult—setting where valuations are Lipschitz continuous (meaning small changes in features lead to small changes in valuation) but potentially non-linear.

Algorithmic Frameworks

The paper introduces two primary algorithmic frameworks to minimize "regret" (the difference between the seller's revenue and the maximum possible revenue):

1. Iterative Partition Refinement

This is a "divide-and-conquer" approach. The algorithm partitions the feature space into small cells. It probes the function within a cell until it has a good estimate, then bisects that cell into smaller ones to increase precision.

Iterative Partition Refinement

2. The Midpoint Algorithm

This is a more global approach that leverages the Lipschitz property across the entire domain. The algorithm maintains two sets: $S^+$ (points known to be above the function) and $S^-$ (points known to be below).

The Midpoint Algorithm Envelopes

Using the Lipschitz property, these points define a "feasible envelope" for the function. For any new context $x_t$, the algorithm simply guesses the midpoint $y_t$ between the highest and lowest possible values allowed by that envelope.

3. Spherical Coordinate Mapping

To handle the specific case of multiple buyers with linear valuations, the authors map the problem to learning the extreme points of a convex set using generalized spherical coordinates. This allows them to treat the "upper envelope" of multiple linear functions as a single Lipschitz function.

Key Insights

  • Information Propagation: Because the function is Lipschitz, a single "sold/not sold" data point at context $x$ provides information about the valuation at all nearby contexts. The Midpoint Algorithm is particularly effective at exploiting this global structure.
  • Pricing vs. Symmetric Loss: The authors show that the "pricing loss" (revenue-focused) is fundamentally harder than "symmetric loss" (distance-focused). For a 1D problem, symmetric loss can achieve logarithmic regret ($O(\log T)$), while pricing loss is stuck with square-root regret ($\Theta(\sqrt{T})$).
  • The "Curse" of Dimensionality: Regret grows exponentially with the number of dimensions $d$. The paper quantifies this precisely, showing how the "surface area" of the function's domain dictates the learning rate.
  • Linear Buyer Populations: Even if individual buyers are simple (linear), a population of them creates a non-linear "max-valuation" function. The authors show this specific non-linearity has a structure that can be exploited to get better bounds than general Lipschitz functions.

Key Results

The paper establishes tight regret bounds (where the upper and lower bounds match, or nearly match) against an adversarial sequence of contexts:

Setting Loss Function Regret Bound
1D Lipschitz Symmetric ($|f(x)-y|$) $O(\log T)$
d-D Lipschitz Symmetric ($|f(x)-y|$) $\Theta(T^{(d-1)/d})$
d-D Lipschitz Pricing (Revenue) $\Theta(T^{d/(d+1)})$
Linear Buyers Pricing (Revenue) $O(T^{(d-1)/d})$

Specifically, for $d > 1$, the pricing regret of $\Theta(T^{d/(d+1)})$ is a significant improvement over the $O(T^{(d+1)/(d+2)})$ bound one would get by blindly applying standard "semi-Lipschitz bandit" algorithms.

Limitations and Future Work

  • The 1D Gap: For the 1D symmetric loss case, there is a small remaining gap between the lower bound of $\Omega(\sqrt{\log T})$ and the upper bound of $O(\log T)$.
  • Known Lipschitz Constant: The algorithms assume the Lipschitz constant $L$ is known beforehand. In practice, $L$ might be unknown, requiring an adaptive approach.
  • Computational Complexity: While the partition algorithm is computationally efficient, the Midpoint Algorithm requires maintaining and querying complex polygonal shapes in high dimensions, which could become computationally expensive as $T$ and $d$ increase.
  • Stochastic Contexts: The paper focuses on adversarial contexts; exploring how these bounds change if contexts are drawn from a fixed probability distribution is a suggested next step.

Summary updated

Abstract

We investigate the problem of learning a Lipschitz function from binary feedback. In this problem, a learner is trying to learn a Lipschitz function $f:[0,1]^d \rightarrow [0,1]$ over the course of $T$ rounds. On round $t$, an adversary provides the learner with an input $x_t$, the learner submits a guess $y_t$ for $f(x_t)$, and learns whether $y_t &gt; f(x_t)$ or $y_t \leq f(x_t)$. The learner's goal is to minimize their total loss $\sum_t\ell(f(x_t), y_t)$ (for some loss function $\ell$). The problem is motivated by \textit{contextual dynamic pricing}, where a firm must sell a stream of differentiated products to a collection of buyers with non-linear valuations for the items and observes only whether the item was sold or not at the posted price. For the symmetric loss $\ell(f(x_t), y_t) = \vert f(x_t) - y_t \vert$, we provide an algorithm for this problem achieving total loss $O(\log T)$ when $d=1$ and $O(T^{(d-1)/d})$ when $d&gt;1$, and show that both bounds are tight (up to a factor of $\sqrt{\log T}$). For the pricing loss function $\ell(f(x_t), y_t) = f(x_t) - y_t {\bf 1}\{y_t \leq f(x_t)\}$ we show a regret bound of $O(T^{d/(d+1)})$ and show that this bound is tight. We present improved bounds in the special case of a population of linear buyers.
BibTeX
@inproceedings{mao2018contextual,
  author = {Jieming Mao and Renato Paes Leme and Jon Schneider},
  title = {{Contextual Pricing for Lipschitz Buyers}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=H1W6vdWuWr},
}
Figure