Abstract
In the contextual pricing problem, a seller repeatedly prices products described by adversarial feature vectors, observing only binary purchasing decisions from a buyer with an unknown linear valuation. We present a polynomial-time algorithm that achieves $O(d \log \log T + d \log d)$ regret, nearly matching the $\Omega(d \log \log T)$ lower bound. By extending this to symmetric loss, we obtain a nearly optimal regret of $O(d \log d)$. These results are powered by a novel "Multiscale Steiner Potential" based on integral geometry, which bounds the value of the Steiner polynomial of a convex region across multiple scales. We further generalize this to abstract hypothesis classes and noisy feedback models.
Introduction
Contextual search is a fundamental problem in online learning where an agent seeks to learn a hidden function $f$ from a hypothesis class $\mathcal{H}$ through sequential interactions. In the specific case of contextual pricing, a seller offers an item with features $x_t \in \mathbb{R}^d$ at price $p_t$. The buyer, having a secret valuation $v$, buys if $x_t \cdot v \ge p_t$. The seller's feedback is purely binary: "bought" or "not bought."
The primary challenge in high-dimensional contextual search is that binary feedback provides very little information per round. Previous approaches often suffered from high regret (e.g., $O(d^4)$) because the "version space"—the set of candidate valuations consistent with observations—could become extremely thin or geometrically complex, making it difficult to find a "central" point for the next query.
The Multiscale Steiner Potential
This work introduces a breakthrough geometric technique: the Multiscale Steiner Potential. Instead of measuring the raw volume of the version space, the algorithm tracks the volume of the version space after it has been "inflated" by a ball of radius $z$. This inflated volume is described by the Steiner polynomial, a degree-$d$ polynomial whose coefficients are the intrinsic volumes of the set.
As illustrated above, the algorithm operates across multiple scales. By evaluating the "width" of the uncertainty set in the direction of the current context vector, the learner can decide which scale $i$ is most appropriate for the current round. This multiscale approach ensures that the learner always makes progress, regardless of whether the uncertainty set is large and round or narrow and elongated.
Regularization via Inflation
The use of Steiner polynomials acts as a form of geometric regularization. By considering the Minkowski sum of the uncertainty set and a ball, the algorithm effectively smooths the search space. This prevents the cutting process—where the version space is halved based on feedback—from creating sets that are too difficult to navigate.
In each round, the algorithm uses a randomized perturbation of the median value within the inflated set. This ensures that, in expectation, each query significantly reduces the Steiner potential, leading to rapid convergence toward the true valuation.
Key Results and Generalizations
The proposed framework yields several state-of-the-art results:
- Contextual Pricing: Regret is reduced to $O(d \log \log T + d \log d)$, a significant improvement over the previous $O(d^4 \log \log T)$.
- Symmetric Contextual Search: For symmetric loss, the algorithm achieves $O(d \log d)$ regret, nearly matching the $\Omega(d)$ lower bound.
- General Hypothesis Classes: The geometric ideas are abstracted to any class with a finite covering dimension $d$, resulting in $O(d^2)$ regret. This applies to complex models like sparse linear functions or unit-demand buyers.
- Noisy Feedback: The algorithm is robust to noise. Even if feedback is flipped with probability $p < 1/2$, the learner can achieve $O(\text{poly}(d))$ regret that does not grow with the number of rounds $T$.
Conclusion
By shifting the focus from raw volume to the more robust Steiner potential, this work provides a near-optimal solution to the contextual search problem. The multiscale geometric framework not only settles long-standing questions in contextual pricing but also provides a powerful toolkit for learning abstract hypothesis classes under thin, binary feedback.
Summary updated