A seller who sets prices from customer features (a "context" vector $x\in\mathbb{R}^d$) must experiment to learn how demand responds to price. Only yes/no purchases are observed. The most sample-efficient known strategy is localized exploration: find a rough estimate of the best price, then test only small price nudges around it. For linear demand, Localized exploration in contextual dynamic pricing achieves dimension-free regret shows this yields $O(\sqrt{T}\log T)$ regret with no dependence on $d$, but only once the horizon exceeds $T>d^4$. The single-index model $d(p,x)=g(\theta^\top x, p)$ passes a linear score through an unknown smooth curve $g$. For that model, Semi-Parametric Contextual Pricing with General Smoothness gets the optimal rate in $T$ but carries the same theoretical $d^4$ warm-up. Its own simulations show regret growing roughly linearly in $d$. So in both lines the warm-up cost appears to be an artifact of how the proof is done, and it is the main reason these guarantees say nothing useful at realistic catalog sizes and feature counts.
Our explanation for the $d^4$ is that both analyses demand that the pilot estimate put every possible customer inside the small neighborhood where the revenue curve is nearly quadratic. That is a worst-case guarantee over the whole context space, and in high dimension it scales with $\sup\|x\|\sim\sqrt d$. Quantitative combinatorial geometry replaces such existence-or-supremum statements with statements about how much measure survives after trimming a thin boundary. Quantitative (p, q) theorems in combinatorial geometry does this with floating bodies, and Quantitative Combinatorial Geometry for Continuous Parameters does it for Helly and Carathéodory. We apply the same trade to pricing. The algorithm certifies localization on a set of customers of probability at least $1-\delta$, and handles the untrimmed remainder conservatively. We conjecture this shrinks the warm-up from $d^4$ to roughly linear in $d$. It should also leave the leading regret term free of $d$ for nonlinear single-index demand, with explicit constants that can be checked against simulation.
Core Claim
Let $\hat\theta$ be the pilot estimate and let $\hat\Sigma_n^{-1}$ be the shape of its confidence ellipsoid after $n$ pilot rounds. A context $x$ is localized at radius $r$ if every plausible parameter moves its score by at most $r$:
$$ x \in \mathcal{L}_r \iff \beta_n^2\, x^\top \hat\Sigma_n^{-1} x \le r^2, $$
where $\beta_n$ is the confidence multiplier. When contexts have covariance $\Sigma$ and $\hat\Sigma_n\approx n\Sigma$, Markov's inequality gives the bound on the mass of the trimmed region:
$$ \Pr\big(x\notin\mathcal{L}_r\big) \le \frac{\beta_n^2\,\mathrm{tr}(\hat\Sigma_n^{-1}\Sigma)}{r^2} \approx \frac{\beta_n^2\, d}{n\, r^2}. $$
It follows that making all but a $\delta$ fraction of customers localized needs only $n\approx \beta_n^2 d/(\delta r^2)$ pilot rounds. The dependence on $d$ is linear. Contrast the worst-case requirement, which adds a $\sup\|x\|^2$ factor and compounds through the downstream local-regression analysis.
Customers inside $\mathcal{L}_r$ receive Rademacher price nudges around the estimated optimum, in the style of LetC. Their data feed a local quadratic fit of $g$ in price near the peak. Customers outside $\mathcal{L}_r$ receive a conservative price and are used to refine $\hat\theta$. Those customers contribute regret at most $\delta T$ times the per-round revenue range, so we choose $\delta\asymp T^{-1/2}$ or smaller.
The theorem we aim to prove has three parts. The warm-up length is linear in $d$ up to logarithms. The regret after warm-up matches LPSP's $T^{(\beta+1)/(2\beta+1)}$ rate in $T$, where $\beta$ is the smoothness of $g$ (since LPSP shows that rate is optimal, we do not claim $\sqrt T$). The leading term does not depend on $d$. We will also give explicit leading constants, obtained by running the local regression step through the offset-process argument of Learning with Square Loss: Localization through Offset Rademacher Complexity. That argument subtracts a quadratic penalty from the empirical process so that no radius has to be tuned by hand. The authors fixed their constant at $c=1/18$ for readability; we will optimize it for the pricing loss.
Research Program
The analytic work has three parts. First, we identify exactly where the $d^4$ enters the LetC and LPSP proofs and replace each uniform-over-contexts step with a statement that holds on $\mathcal{L}_r$ plus a mass bound on its complement. Second, we extend LetC's "critical inequality" from a linear to a smooth single-index demand curve. That inequality is the bias–variance balance behind its dimension-free rate. The key technical step is showing that, restricted to $\mathcal{L}_r$, the unknown $g$ only needs to be learned in a one-dimensional neighborhood of the optimal price. This neighborhood is where local polynomial regression converges at a rate free of $d$. Third, we track every constant, including the confidence multiplier $\beta_n$, which is where the heavy-tail caveat of offset complexity matters. The goal is a bound that can be evaluated as a number and plotted next to empirical regret.
Each input direction plays a distinct role. Geometric measure theory supplies the form of the guarantee, which is measure-level rather than supremum-level. The $\epsilon$-slack we accept is the analogue of the slack that continuous quantitative Helly theorems require. We are not computing floating bodies; Quantitative (p, q) theorems in combinatorial geometry notes these are expensive in high dimension. Here the trimmed region is an ellipsoid, and membership costs one quadratic form. The move away from linear demand is the application regime. Constant optimization is the standard of evidence. The dimension barrier is the target.
The file's tensions constrain the design. Robust Contextual Pricing proves that under adversarial corruption, deterministic pricing algorithms cannot avoid a multiplicative $C\cdot d$ overhead. We therefore restrict the claim to stochastic, uncorrupted demand and do not claim that trimming defeats that lower bound. The gate is deterministic given data, so that lower bound applies to it in the corrupted setting.
Baselines
The naive reference point is the retailer's offline static policy, meaning prices fit once from historical data. Localized exploration in contextual dynamic pricing achieves dimension-free regret reports, on the INFORMS 2023 Blue Summit Supplies data under parametric bootstrap, "revenue improvement of more than 5%" of LetC over such offline policies for the majority of 200+ products. We will reproduce that simulator and report our method's revenue gain against the same offline policy.
We also include Linear Greedy. Context-Based Dynamic Pricing with Partially Linear Demand Model reports that it incurs linear regret under nonlinear demand, with no numerical value given. It serves as a floor.
The two strongest competitors are LetC itself, which is the right answer if demand is close to linear, and LPSP, which is the strongest method for nonlinear single-index demand. No reported regret number was found on Lacuna for LPSP; its paper states only that it outperforms explore-then-commit and scales nearly linearly in $d$ empirically. For the sparse high-dimensional setting ($d=100$, four influential features), Semi-Parametric Dynamic Contextual Pricing reports that Sparse DEEP-C achieves "33% lower 95th-percentile regret" than simpler decoupled methods, and we include it there.
All methods get identical simulators, horizons, and random seeds. Each method gets the same budget of hyperparameter configurations for its warm-up length and perturbation scale, selected on held-out seeds. Beating a baseline means lower mean and 95th-percentile cumulative regret at $T=10^5$ across 50 seeds, with non-overlapping bootstrap intervals. On BSS, it means revenue improvement over offline exceeding LetC's on a majority of products.
Three ablations isolate what is new. The first turns the gate off: every customer is treated as localized after the same shortened warm-up. The second restores the worst-case $d^4$-length warm-up. The third replaces local Rademacher nudges with global random price shocks.
Why not just…?
Why not just run LPSP or LetC with a shorter warm-up, since the $d^4$ is probably a proof artifact? This is the most serious threat. If it works as well, the practical contribution collapses to a better proof. The "gate off, short warm-up" ablation tests it directly. We expect the ungated version to fail specifically on heavy-tailed or anisotropic contexts, where a nonnegligible fraction of customers have scores far outside the pilot's reliable range and are nudged around the wrong price. If it does not fail even there, we will say so plainly. The proposal then stands as a theory result: the first explicit-constant, dimension-light guarantee for nonlinear demand.
Why not just use per-context confidence widths, as in optimistic linear bandits? The gate is indeed an elliptical confidence width. What differs is the treatment inside the gate. Optimism explores along a global confidence set and pays the $d$ factor in its leading term. We use width only to decide whether to trust localization, then learn a one-dimensional local curve. The comparison is part of the synthetic study. The prediction is that regret curves for optimism separate by dimension, while ours converge to a common slope, as LetC's did for linear demand.
Why not just reduce dimension with PCA or Lasso first, then run a low-dimensional pricer? Semi-Parametric Dynamic Contextual Pricing reports that decoupled pipelines of this kind trail its integrated method by 33% in 95th-percentile regret at $d=100$. Separately, Low-Rank Bandit Methods for High-Dimensional Dynamic Pricing finds three singular vectors explain 99.9% of Grupo Bimbo demand variation, which suggests reduction can work when a low-rank structure truly exists. We run PCA-then-LPSP on both low-rank and full-rank synthetic contexts. That comparison says when reduction is enough.
Proposed Experiments
The synthetic study extends LetC's $d=4$ to $64$ sweep up to $d=256$. It uses single-index demand whose link $g$ ranges over logistic, S-shaped (prospect-theory-like), and non-monotone "prestige" shapes. It uses Gaussian, Student-$t$, and low-rank context distributions.
The first decisive check is warm-up scaling. We find the smallest warm-up at which each method's regret slope stabilizes, and fit its growth against $d$. Our conjecture predicts exponent near 1. The inherited analyses predict 4.
The second check is constants. We plot the explicit bound divided by empirical regret against $T$. Success means a ratio within one order of magnitude at $T=10^5$, far tighter than tilde-notation bounds typically are. That would make the bound usable for choosing warm-up length in practice.
The third check is real data. We compare revenue against the offline policy on the BSS bootstrap simulator next to LetC's reported >5%, and use Grupo Bimbo as a low-rank stress test. If the gated method beats LPSP and LetC at large $d$ on nonlinear demand, and ties LetC on near-linear products, the claim holds. If the gate-off ablation matches it everywhere, the contribution is analytic only, and we will report it that way.
References
- Localized exploration in contextual dynamic pricing achieves dimension-free regret
- Semi-Parametric Contextual Pricing with General Smoothness
- Quantitative (p, q) theorems in combinatorial geometry
- Quantitative Combinatorial Geometry for Continuous Parameters
- Learning with Square Loss: Localization through Offset Rademacher Complexity
- Robust Contextual Pricing
- Context-Based Dynamic Pricing with Partially Linear Demand Model
- Semi-Parametric Dynamic Contextual Pricing
- Low-Rank Bandit Methods for High-Dimensional Dynamic Pricing