Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand

Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.

39,435 characters · 10 sections · 22 citation commands

Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.

abstractWe study contextual dynamic pricing with linear valuations and bounded-support agnostic noise, whose induced demand curve may be non-Lipschitz with arbitrary jumps and atoms. Such discontinuities break the cross-context interpolation arguments used by smooth-demand pricing algorithms, while the best previous method achieved only $\widetilde O(T^{3/4})$ regret. We propose Conservative-Markdown Redirect-UCB Pricing, a polynomial-time algorithm that combines randomized parameter estimation, conservative residual-grid probing, and confidence-based one-step redirection. Our algorithm achieves $\widetilde O(T^{2/3})$ optimal regret, matching the known lower bounds of kleinberg2003value up to logarithmic factors and improving over the previous upper bound of xu2022towards. Under stochastic well-conditioned contexts, this closes the long-existing open regret gap in linear-valuation contextual pricing under agnostic non-Lipschitz noise distribution.

Introduction

Learning from censored feedback is a recurring challenge across machine learning: the learner makes a decision, but observes only a partial outcome rather than the full reward landscape. Contextual dynamic pricing is a canonical instance of this challenge. A seller observes a feature vector describing the current buyer or product, posts a price in real time, and observes only whether the buyer purchases. The seller never observes the buyer's valuation itself. The goal is to learn a pricing policy whose cumulative revenue is close to that of a clairvoyant policy that knows both the linear valuation parameter and the noise distribution.

A standard model writes the valuation as a linear contextual component plus an idiosyncratic noise:

\fbox{\parbox{0.95\textwidth}{Contextual pricing. For $t=1,2,\ldots,T$:

enumerate[leftmargin=*,align=left,itemsep=0pt,topsep=2pt] • A context $x_t\in\mathbb{R}^{d}$ is observed. • The buyer has private valuation $y_t=x_t^\top\theta^{\star}+\xi_t$. • The seller posts a price $p_t\in[0,B]$. • The seller observes only $o_t=\mathbf{1}\{p_t\le y_t\}$. • The seller receives revenue $p_t o_t$.

} }

The statistical difficulty of the problem depends strongly on the regularity of the noise distribution. If the noise distribution is known, parametric, log-concave, Lipschitz, or sufficiently smooth, existing algorithms can exploit this structure to transfer information across nearby residual prices. In many pricing environments, however, such regularity is not realistic. Buyers may cluster around psychological thresholds, reservation values may contain mass points, and heterogeneous subpopulations may create sharp jumps in the demand curve. In these cases, the survival function may be discontinuous and non-Lipschitz. A small residual perturbation can then change the purchase probability by a constant amount, invalidating interpolation arguments based on smoothness.

This paper studies contextual dynamic pricing in this fully agnostic non-Lipschitz regime. We impose no density, Lipschitz, smoothness, log-concavity, single-crossing, or parametric condition on the noise distribution beyond mild boundedness and i.i.d. assumptions. The noise may have arbitrary atoms and jumps. The formal setup and assumptions are given in Section (ref).

\paragraph{Main contribution.} We introduce Conservative-Markdown Redirect-UCB Pricing, a polynomial-time algorithm that achieves $\widetilde O(T^{2/3})$ regret for linear-valuation contextual pricing with fully agnostic bounded noise. This rate is optimal in its $T$-dependence up to logarithmic factors. A $T^{2/3}$ lower bound already holds for an interior non-contextual subclass kleinberg2003value that can be embedded into our stochastic-context model, and xu2022towards establish the same barrier for contextual pricing under Lipschitz demand. Therefore, our result closes the $T^{3/4}$ versus $T^{2/3}$ gap for agnostic linear-valuation pricing under the stochastic contextual setting studied here.

\paragraph{Scope of agnosticism.} Our agnosticism is with respect to the residual demand curve: we impose no Lipschitz continuity, smoothness, density, log-concavity, or parametric structure on the valuation noise distribution, but only boundedness to avoid boundary clipping.

\paragraph{Algorithmic idea.} The algorithm reduces contextual pricing to confidence-bound learning on a one-dimensional residual grid. A uniformly randomized first stage estimates the linear valuation component; subsequent prices use a conservative markdown so that every binary observation becomes a one-sided probe of two adjacent survival levels, a relation that remains valid even when the demand curve has jumps. In the adaptive stage, an upper-confidence rule probes uncertain grid points directly and redirects to the left once their confidence radius reaches the grid scale, so discontinuity costs are paid only during a limited exploration period.

\paragraph{Technical contribution.} The analysis compares the oracle value directly with the optimistic score of a maintained residual-grid index, rather than estimating demand at oracle-selected points. Direct probes pay grid, confidence, and adjacent-jump costs, while redirected probes pay only a grid-scale price loss; summing these terms with $\Delta\asymp T^{-1/3}$ yields $\widetilde O(T^{2/3})$ regret. The same residual grid has size $\widetilde O(T^{1/3})$, giving a direct polynomial-time implementation.

table[table omitted — 1,151 chars of source]

comment\paragraph{Algorithmic idea.} The algorithm has three stages. Stage 1 uses uniformly randomized prices to estimate the linear parameter $\theta^\star$ from binary feedback. Stage 2 collects initial observations on a one-dimensional residual grid. Stage 3 uses upper confidence bounds on this residual grid to choose prices adaptively. The central device is a conservative markdown. If probe index $j$ is selected, the algorithm posts a price of the form \[ p_t=\hat u_t+w_{j+1}-3\Delta, \qquad \hat u_t=\langle x_t,\hat\theta\rangle, \] where $2\Delta$ is the residual-grid spacing and $\Delta$ is the target prediction accuracy from Stage 1. On the good event $|\hat u_t-u_t|\le\Delta$, this markdown forces the effective residual $p_t-u_t$ to lie in $[w_{j-1},w_j]$. Therefore the conditional purchase probability is deterministically sandwiched as \[ S(w_j) \le \mathbb E[o_t\mid x_t,\mathcal H_{t-1},\text{probe }j] \le S(w_{j-1}). \] This one-sided structural relation remains valid even if $S$ has arbitrary jumps. The only possible bias is the adjacent jump height $\alpha_j=S(w_{j-1})-S(w_j)$. Stage 3 uses the upper confidence score \[ U_{t,j}=(\hat u_t+w_{j+1}+\Delta)\min\{1,\hat m_j+b_j\}, \] after which it either probes $j$ directly or redirects one grid point to the left. Direct probes are used only while the confidence radius $b_j$ is larger than the grid scale $\Delta$; once $b_j\le\Delta$, selecting $j$ triggers a probe at $j-1$. This redirect rule is what makes discontinuities harmless: the cumulative jump cost is paid only during the limited direct-probe period, while later redirected probes incur only $O(\Delta)$ price loss per round. \paragraph{Technical contribution.} The proof avoids estimating the survival function at oracle-selected grid points. Instead, it compares the oracle value directly to the optimistic score of a maintained grid index. The key regret decomposition has two parts. Direct probes incur a cost of order \[ O(\Delta)+O(b_j)+O(\alpha_j), \] but each index is directly probed only $O(\log T/\Delta^2)$ times before entering redirect mode, and $\sum_j\alpha_j\le1$. Redirected probes incur no adjacent-jump cost and lose only $O(\Delta)$ per round. With $\Delta\asymp T^{-1/3}$ and $M\asymp\Delta^{-1}$ grid points, the standard confidence-radius summation gives \[ \sum_t b_{a_t}=\widetilde O(\sqrt{MT})=\widetilde O(T^{2/3}), \] and the total regret is $\widetilde O(T^{2/3})$.

Table (ref) summarizes the regret landscape for linear-valuation contextual pricing under different noise assumptions. The rest of the paper is organized as follows. Section (ref) reviews related work. Section (ref) formalizes the model and assumptions. Section (ref) presents the algorithm. Section (ref) gives the main regret theorem and proof roadmap. Section (ref) reports numerical experiments, and Section (ref) discusses limitations, ethical considerations, and conclusions. Full proofs appear in the appendix.

Related Work

We review the closest literature on contextual dynamic pricing with unknown demand. Additional background on parametric pricing, non-contextual posted-price learning, confidence-bound methods, and adjacent contextual pricing models appears in Appendix (ref).

\paragraph{Contextual pricing with smooth or Lipschitz noise.} A large body of work obtains strong regret guarantees by imposing regularity on the noise distribution. javanmard2019dynamic study dynamic pricing with known log-concave noise, where the revenue function is well behaved enough for greedy pricing after parameter learning. ban2021personalized obtain $\widetilde O(\sqrt T)$ regret under parametric demand assumptions. luo2022contextual achieve $\widetilde O(T^{2/3})$ regret under second-order smoothness of the noise distribution through an explore-then-UCB strategy. fan2024policy exploit higher-order smoothness and introduce a semiparametric parameter-estimation method based on uniformly randomized prices, which we also use in Stage 1. tullii2024improved obtain $\widetilde O(T^{2/3})$ regret under Lipschitz noise via cross-context learning. These works use smoothness to transfer demand information between nearby residuals. Such transfer is unavailable in the agnostic setting considered here, where a residual perturbation of arbitrarily small size may cross an atom and change demand by a constant amount.

\paragraph{Fully agnostic contextual pricing.} The closest work is xu2022towards, who study linear-valuation contextual pricing with an unknown noise distribution and no smoothness assumptions. Their D2-EXP4 algorithm discretizes a large policy class and applies an adversarial bandit method, obtaining $\widetilde O(T^{3/4})$ regret for adversarial context sequences. They also prove a $\widetilde\Omega(T^{2/3})$ lower bound for contextual pricing under a Lipschitz subclass, which applies to the larger agnostic model. Our algorithm works directly on a one-dimensional residual grid rather than enumerating a high-dimensional policy class. The conservative markdown creates a stable one-sided observation model on this grid, and the redirect-UCB rule controls discontinuity-induced bias through confidence-radius accounting. This yields the optimal $\widetilde O(T^{2/3})$ regret rate in polynomial time.

\paragraph{Lower bounds.} The $\widetilde O(T^{2/3})$ rate is tight in its dependence on $T$. Xu and Wang xu2022towards prove a $\widetilde\Omega(T^{2/3})$ lower bound for contextual pricing under Lipschitz noise, showing that the $T^{2/3}$ barrier already appears in a regular subclass of demand functions. In addition, the classical non-contextual lower bound of kleinberg2003value can be embedded into our model by using a constant linear valuation together with independent dummy covariates to satisfy the full-rank stochastic-context condition. The hard valuation distributions can be placed in an interior price interval, so bounded support, zero-mean normalization, and the price-buffer condition are satisfied after the usual recentering of the noise into the intercept. Appendix (ref) gives the formal embedding.

Problem Setup

We study contextual dynamic pricing with linear valuations and binary purchase feedback. At each round $t=1,\ldots,T$, the seller observes a context $x_t\in\mathbb{R}^d$. The customer's valuation is $y_t=\langle x_t,\theta^{\star}\rangle+\xi_t$, where $\theta^{\star}\in\mathbb{R}^d$ is unknown and $\xi_t$ is an unobserved noise. The seller posts a price $p_t\in[0,B]$ based on past observations and observes only $o_t=\mathbf{1}\{p_t\le y_t\}$.

We write the demand curve in residual coordinates through the survival function $S(w):=\mathbb{P}(\xi_t\ge w)$. This convention handles atoms without additional notation: if $F(w)=\mathbb{P}(\xi_t\le w)$ is the usual right-continuous CDF, then $S(w)=1-F(w^-)$, so $\mathbb{E}[o_t\mid x_t,p_t]=S(p_t-\langle x_t,\theta^{\star}\rangle)$ for arbitrary noise distributions. We extend $S$ outside the support by setting $S(w)=1$ for $w\le -c$ and $S(w)=0$ for $w>c$.

The expected revenue at context $x$ and price $p$ is $\pi(x,p):=pS(p-\langle x,\theta^{\star}\rangle)$. Let

equation[equation omitted — 164 chars of source]

For compactness, write $u_t:=\langle x_t,\theta^{\star}\rangle$ and $V_t(w):=(u_t+w)S(w)$. The oracle value in round $t$ is $V_t^\star:=\max_{w\in[-c,c]}V_t(w)$; residuals outside $[-c,c]$ cannot improve revenue under the bounded-support model.

Assumptions

We impose boundedness and identifiability conditions on the linear contextual component, while leaving the demand curve otherwise unrestricted: $S$ may be discontinuous, non-Lipschitz, and may contain arbitrary jumps and atoms.

assumption[Bounded support, exogeneity, and normalization] There exist known constants $B_x,B_\theta,c,B<\infty$ such that, almost surely, $\|x_t\|_2\le B_x$, $\|\theta^{\star}\|_2\le B_\theta$, $\xi_t\in[-c,c]$, and $0\le y_t\le B$. The noises $\{\xi_t\}_{t=1}^T$ are i.i.d. from an unknown distribution $F$ and independent of the context sequence. We use the location normalization $\mathbb{E}[\xi_t]=0$.

The valuation bound $0\le y_t\le B$ is used only in Stage 1 to convert uniformly randomized prices into an unbiased linear signal. The zero-mean normalization is without loss of generality when the context contains an intercept, since a nonzero noise mean can be absorbed into the intercept coefficient. The independence condition can be weakened to $\mathbb{E}[\xi_t\mid x_t]=0$ for the Stage 1 argument.

assumption[Stochastic contexts] The contexts $\{x_t\}_{t=1}^T$ are i.i.d. from a distribution $\mathcal D_x$ supported on $\{x:\|x\|_2\le B_x\}$, and $\lambda_{\min}(\mathbb{E}[x_tx_t^\top])\ge\lambda_0>0$.

Assumption (ref) ensures that the linear parameter is identifiable from the randomized Stage 1 observations.

assumption[Buffered admissible prices] There exists a constant $\kappa>0$ such that $\langle x_t,\theta^{\star}\rangle-c\ge\kappa$ and $\langle x_t,\theta^{\star}\rangle+c\le B$ almost surely. We assume the horizon is large enough that $2\Delta\le\kappa$, where $\Delta$ is the Stage 1 target accuracy in Algorithm (ref); smaller horizons are absorbed into the problem-dependent constant.

\paragraph{Scope of the assumptions.} Bounded support and bounded valuations make the residual grid finite and justify the randomized-price regression in Stage 1. The i.i.d. full-rank context condition is used only for estimating the linear component, while the price-buffer condition avoids boundary clipping in the markdown probes. None of these assumptions imposes continuity, density, Lipschitzness, smoothness, slope, or margin conditions on $F$ or $S$; arbitrary atoms and jumps remain allowed.

Notation

Let $\hat u_t:=\langle x_t,\widehat{\theta}\rangle$ be the predicted linear value after Stage 1, and define the Stage 1 good event

equation[equation omitted — 123 chars of source]

Given $\Delta$, define a residual grid with spacing $2\Delta$ by $M:=\lceil c/\Delta\rceil$ and $w_i:=-c+2i\Delta$ for $i=0,1,\ldots,M$. The queried index set is $\mathcal I:=\{0,1,\ldots,M-1\}$. We use the boundary convention $w_{-1}:=w_0-2\Delta$ and $S(w_{-1}):=1$.

For each queried index $j\in\mathcal I$, define the adjacent jump height $\alpha_j:=S(w_{j-1})-S(w_j)\ge0$. Since $S$ is non-increasing and bounded in $[0,1]$, $\sum_{j=0}^{M-1}\alpha_j\le1$. This quantity captures the maximum discontinuity cost associated with probing the interval $[w_{j-1},w_j]$. Let $\mathcal{H}_t$ denote the sigma-algebra generated by observations through round $t$. We use $\widetilde O(\cdot)$ to hide factors polylogarithmic in $T$ and polynomial in $(d,B_x,B_\theta,B,c,1/\lambda_0,1/\kappa)$. We focus on the horizon dependence and treat $d$ and other problem constants as fixed.

Algorithm

We present Conservative-Markdown Redirect-UCB Pricing (CMRUP) in Algorithm (ref). The algorithm has three stages. Stage 1 estimates the linear valuation parameter. Stage 2 collects initial demand observations on a residual grid. Stage 3 uses upper confidence bounds on the residual grid, together with a one-step redirect rule, to choose prices adaptively.

\paragraph{Markdown probes.} For a queried index $j\in\mathcal I=\{0,\ldots,M-1\}$, define the probe price

equation[equation omitted — 118 chars of source]

On $\mathcal E_\theta$ and under Assumption (ref), clipping does not occur in Stages 2--3. Since $|\hat u_t-u_t|\le\Delta$, the effective residual of this probe satisfies \[ p^+_{t,j}-u_t =w_{j+1}-3\Delta+(\hat u_t-u_t) \in [w_{j-1},w_j]. \] Thus the conditional purchase probability of probe $j$ obeys

equation[equation omitted — 149 chars of source]

This deterministic sandwich is the basic observation model used by the algorithm on the residual grid.

\paragraph{Empirical means and confidence radii.} For each queried index $j$, let $n_j(t)$ be the number of times before round $t$ that probe action $j$ has been played, and let $\hat m_j(t)$ be the empirical mean of the corresponding binary observations. If $n_j(t)=0$, set $\hat m_j(t)=0$. Define

equation[equation omitted — 99 chars of source]

The constant $C_{\rm ucb}$ is chosen large enough for the uniform concentration event in Lemma (ref).

\paragraph{Optimistic scores.} At a Stage 3 round $t$, each queried index receives the score

equation[equation omitted — 133 chars of source]

The first factor is an optimistic price multiplier for residuals in $[w_j,w_{j+1}]$, and the second factor is an upper confidence estimate for $S(w_j)$.

algorithm[algorithm omitted — 2,252 chars of source]

Mechanics of the Algorithm

\paragraph{Residual-grid observations.} The $3\Delta$ markdown combines one grid step of length $2\Delta$ with the prediction-error allowance $\Delta$. As a result, a probe indexed by $j$ generates an observation whose conditional mean lies between $S(w_j)$ and $S(w_{j-1})$. The possible mismatch between these two values is exactly the adjacent jump height $\alpha_j$.

\paragraph{Upper confidence search.} The score $U_{t,j}$ is an upper confidence estimate of the revenue associated with residual interval $[w_j,w_{j+1}]$. Lemma (ref) shows that, on the joint good event, the maximum score upper bounds the oracle revenue in every Stage 3 round. The score uses only observations collected from probes that were actually played.

\paragraph{One-step redirect.} Directly probing index $j$ may incur a discontinuity cost proportional to $\alpha_j$. The algorithm directly probes $j$ only while $b_j>\Delta$, which limits the number of direct probes at each index. Once $b_j\le\Delta$, the selected index is executed by probing $j-1$ instead. This redirected probe has at least the demand level needed to validate the selected score, and the incurred price loss is only of order $\Delta$.

\paragraph{Role of the warmup stage.} The warmup stage initializes the residual-grid observations and gives every grid point a chance to be sampled before the adaptive stage. It is not the source of the $T^{2/3}$ rate: the Stage 3 confidence analysis depends only on counts of actually played probes and would also work with infinite initial radii and forced first visits. We use $T_w=\lceil T^{2/3}\rceil$ because this cost is of the same order as the target regret and keeps the algorithmic description simple. A shorter initialization or a Stage 3-only initialization rule can be analyzed with the same counting argument.

Regret Analysis

We state the regret guarantee for Algorithm (ref) and summarize the proof. Full proofs are in Appendix (ref).

theorem[Cumulative regret] Under Assumptions (ref)--(ref), Algorithm (ref) satisfies \[ R_T\le \widetilde O(T^{2/3}). \] The guarantee allows arbitrary bounded-support noise distributions, including distributions whose CDF or survival function has atoms, jumps, and no Lipschitz or smoothness regularity.

The constants hidden in $\widetilde O(\cdot)$ may depends polynomially on $(d,B_x,B_\theta,B,c,1/\lambda_0,1/\kappa)$. Please kindly find these detailed dependence in Appendix (ref).

\paragraph{Proof architecture.} The proof has four ingredients. First, uniformly randomized prices in Stage 1 produce $\widehat{\theta}$ with $\max_t|\hat u_t-u_t|\le\Delta=\widetilde O(T^{-1/3})$ with high probability. Second, conservative markdown converts this prediction guarantee into the deterministic sandwich $S(w_j)\le m_{t,j}\le S(w_{j-1})$ whenever probe index $j$ is played. Third, empirical confidence bounds on adaptively collected probe means imply optimism: the largest score $\max_j U_{t,j}$ upper bounds the oracle revenue in each Stage 3 round. Finally, direct probes and redirected probes are charged separately. Direct probes may pay the adjacent jump cost $\alpha_j$, but each index is directly probed only until its confidence radius reaches the grid scale; redirected probes avoid this jump cost and lose only $O(\Delta)$ in price.

\paragraph{Key lemmas.} The first lemma gives the prediction guarantee for the linear component.

lemma[Parameter estimation] Under Assumptions (ref)--(ref), if $T_1=\lceil T^{2/3}\rceil$ and $\Delta$ is chosen as in Algorithm (ref), then with probability at least $1-T^{-2}$, we have $\max_{1\le t\le T}|\hat u_t-u_t|\le \Delta.$

proof[Proof sketch] For $p_t\sim\mathrm{Unif}[0,B]$ and $y_t\in[0,B]$, the signal $z_t:=Bo_t$ satisfies $\mathbb{E}[z_t\mid x_t]=\mathbb{E}[y_t\mid x_t]=\langle x_t,\theta^{\star}\rangle$, using exogeneity and $\mathbb{E}[\xi_t]=0$. Standard bounded-design least-squares concentration, together with the empirical covariance lower bound implied by Assumption (ref), gives $\|\widehat{\theta}-\theta^{\star}\|_2\lesssim (B B_x/\lambda_0)\sqrt{d\log(T)/T_1}$ with high probability. Multiplying by $B_x$ and using the definition of $\Delta$ yields the claim. See Appendix (ref) for a detailed proof.

lemma[Markdown sandwich] On $\mathcal E_\theta$, for every Stage 2--3 round in which probe index $j$ is played, its conditional purchase probability $m_{t,j}:=\mathbb{E}[o_t\mid \mathcal{H}_{t-1},x_t,\text{probe }j]$ satisfies \[ S(w_j)\le m_{t,j}\le S(w_{j-1}). \]

proof[Proof sketch] The un-clipped probe price is $\hat u_t+w_{j+1}-3\Delta$. Assumption (ref) prevents clipping, and $|\hat u_t-u_t|\le\Delta$ places the realized residual in $[w_{j-1},w_j]$. Monotonicity of $S$ gives the sandwich. See Appendix (ref) for more details.

lemma[Uniform confidence for adaptive probes] There exists a sufficiently large constant $C_{\rm ucb}$ such that, with probability at least $1-T^{-2}$, simultaneously for all Stage 3 rounds $t$ and all $j\in\mathcal I$, \[ |\hat m_j(t)-\bar m_j(t)|\le \frac12 b_j(t), \qquad b_j(t):=C_{\rm ucb}\sqrt{\frac{\log T}{\max\{1,n_j(t)\}}}. \] On the same event, $S(w_j)\le \hat m_j(t)+b_j(t)\le S(w_{j-1})+2b_j(t)$.

proof[Proof sketch] For each queried index, enumerate the stopping times at which that index is actually probed. The centered observations at these times form a bounded martingale-difference sequence under the stopped filtration, even though the probing times are adaptive and may include redirected plays. A Hoeffding--Azuma bound for each index and sample size, followed by a union bound over $j$ and $m\le T$, yields the uniform event. Combining it with Lemma (ref) gives the two one-sided inequalities. See Appendix (ref) for a complete proof.

lemma[Optimism of the score] On $\mathcal E_\theta\cap\mathcal E_{\rm conf}$, every Stage 3 round $t$ satisfies \[ V_t^\star\le \max_{j\in\mathcal I}U_{t,j}. \]

proof[Proof sketch] Let $w_t^\star$ be an optimal residual and choose $q$ such that $w_t^\star\in[w_q,w_{q+1}]$. Such a $q\le M-1$ exists because $w_0=-c$ and $w_M\ge c$; if $w_t^\star=c$, we take $q=M-1$. On $\mathcal E_\theta$, the price multiplier in $U_{t,q}$ dominates $u_t+w_t^\star$, while monotonicity gives $S(w_q)\ge S(w_t^\star)$. Lemma (ref) gives $\hat m_q+b_q\ge S(w_q)$, so the score of $q$ upper bounds $V_t^\star$. By Assumption (ref) and $2\Delta\le\kappa$, all candidate price levels appearing in the optimistic scores are nonnegative. See Appendix (ref).

lemma[One-round regret] On $\mathcal E_\theta\cap\mathcal E_{\rm conf}$, let $j_t$ be the score maximizer in Stage 3. \begin{enumerate}[label=(\roman*),topsep=2pt,itemsep=2pt] • If Algorithm (ref) is in direct-probe mode and plays $j_t$, then \[ V_t^\star-\pi(x_t,p_t) \le C\Delta+B\alpha_{j_t}+CB b_{j_t}(t). \] • If Algorithm (ref) is in redirect mode, then \[ V_t^\star-\pi(x_t,p_t) \le C_B\Delta, \] where $C_B$ depends only on $B$. \end{enumerate}

proof[Proof sketch] By optimism, the oracle value is at most the selected score. In direct-probe mode, the selected score can exceed the revenue of the played probe only through the grid-scale price slack, the adjacent jump $\alpha_{j_t}$, and the confidence radius $b_{j_t}$. The truncation $\min\{1,\hat m_j+b_j\}$ can only reduce the score. In redirect mode, the algorithm probes $j_t-1$ when $j_t\ge1$; this action has conditional demand at least $S(w_{j_t-1})$, which covers the selected score's demand component up to the confidence radius. Since redirect mode occurs only when $b_{j_t}\le\Delta$, the remaining gap is $O(\Delta)$. The boundary case $j_t=0$ uses $S(w_{-1})=S(w_0)=1$. See Appendix (ref) for more details.

lemma[Cumulative Stage 3 regret on the good event] On $\mathcal E_\theta\cap\mathcal E_{\rm conf}$, the cumulative regret in Stage 3 is $\widetilde O(T^{2/3})$.

proof[Proof sketch] Redirect rounds contribute at most $O(\Delta)$ each by Lemma (ref), hence $O(T\Delta)=\widetilde O(T^{2/3})$. Direct-probe rounds contribute $\Delta$, $b_{j_t}(t)$, and $\alpha_{j_t}$. The first term is again $O(T\Delta)$. The confidence terms satisfy the standard counting bound $\sum_{\rm probe}b_{j_t}(t)\le \widetilde O(\sqrt{MT})=\widetilde O(T^{2/3})$ since $M=O(\Delta^{-1})$. For the jump terms, index $j$ is directly probed only while $b_j>\Delta$, so it is directly probed at most $O(\log T/\Delta^2)$ times; therefore $\sum_{\rm probe}\alpha_{j_t}\le O(\log T/\Delta^2)\sum_j\alpha_j=\widetilde O(T^{2/3})$. See Appendix (ref).

\paragraph{Proof sketch of Theorem (ref).} Stages 1 and 2 each last $O(T^{2/3})$ rounds and have per-round regret at most $B$. Lemma (ref) controls Stage 3 on the joint good event, whose complement has probability $O(T^{-2})$ and contributes at most $BT\cdot O(T^{-2})=O(1/T)$. Thus $R_T\le\widetilde O(T^{2/3})$. Full details are in Appendix (ref).

Numerical Experiments

figure[figure omitted — 588 chars of source]

We report synthetic experiments designed to verify the final-regret scaling predicted by Theorem (ref). The experiments compare CMRUP with the agnostic D2-EXP4 baseline of xu2022towards on both a smooth Lipschitz noise distribution and a discontinuous non-Lipschitz distribution containing an atom. The primary quantity of interest is the final cumulative pseudo-regret $R_T$ as a function of the horizon $T$.

\paragraph{Setup.} We generate i.i.d. contexts $x_t\in\mathbb R^5$ with an intercept coordinate $x_{t,0}=1$ and independent features $x_{t,j}\sim\mathrm{Unif}(0,1)$ for $j=1,\ldots,4$. The parameter is $\theta^\star=(2,0.125,0.125,0.125,0.125)^\top$, so that $u_t=\langle x_t,\theta^\star\rangle\in(2,2.5)$. We set the noise support to $[-1,1]$ and consider two noise distributions: uniform noise, $\xi_t\sim\mathrm{Unif}[-1,1]$, whose survival function is Lipschitz; and cliff noise, where $\xi_t=0$ with probability $0.3$ and otherwise $\xi_t\sim\mathrm{Unif}[-1,1]$, creating a jump discontinuity of height $0.3$ in the survival function at $w=0$.

For CMRUP, we run horizons $T\in\{500,1000,2000,\ldots,1{,}024{,}000\}$ with $10$ independent seeds per horizon. In the experiments we set $\Delta=\Delta_{\rm mult}\sqrt{d\log(T)/T_1}$ with $\Delta_{\rm mult}=0.35$. This multiplier controls only the residual-grid scale; the conservative markdown coefficient remains fixed at $3$, so Stage-2/3 probes use a $3\Delta$ markdown. For D2-EXP4, we use the same synthetic streams and pseudo-regret metric, running horizons $T\in\{500,1000,2000,\ldots,256{,}000\}$ with $5$ independent seeds per horizon. Since exact enumeration of the D2-EXP4 policy class is computationally prohibitive at these horizons, we use the sampled-policy implementation described in Appendix (ref). All experiments use CPU-only local computations.

\paragraph{Final-regret scaling.} Figure (ref) plots $R_T$ against $T$ on log-log axes. For each algorithm and noise distribution, we fit a power law $R_T\approx C T^\alpha$ by ordinary least squares in log-log space using all available horizons for that algorithm.

On the uniform noise instance, CMRUP has fitted exponent $0.67$, while D2-EXP4 has fitted exponent $0.78$. Although the two algorithms have comparable regret at small horizons, D2-EXP4 exhibits a visibly steeper growth rate, whereas CMRUP tracks the predicted $T^{2/3}$ scaling. On the cliff noise instance, the separation is more pronounced: CMRUP has fitted exponent $0.56$, while D2-EXP4 has fitted exponent $0.77$. This is consistent with the role of the conservative markdown and redirect rule, which prevent the atom-induced jump from causing a worse asymptotic scaling.

\paragraph{Scope.} These simulations are rate-verification experiments rather than a comprehensive empirical benchmark. The D2-EXP4 baseline is a sampled-policy implementation of the prior agnostic reduction, included to illustrate the empirical scaling difference under the same synthetic environment; it is not an exhaustive implementation of the exponentially large policy class. We do not include ablations of the markdown coefficient or the redirect rule. Such ablations would further isolate the algorithmic mechanism, but the present experiments focus on the main rate comparison under smooth and discontinuous demand.

Discussion and Conclusion

We close with limitations, ethical considerations, and a summary of the main result. Additional related discussions appear in Appendix (ref).

\paragraph{Limitations and extensions.} Our theorem is stated for bounded-support noise, i.i.d. well-conditioned contexts, and an interior price range. These conditions are used for finite-grid learning, Stage-1 parameter estimation, and avoiding boundary clipping in the markdown probes, respectively; they are not continuity assumptions on the demand curve. Extensions to light-tailed noise, horizon-free operation, boundary-clipped probes and richer context processes are discussed in Appendix (ref).

\paragraph{Computation.} The direct implementation is polynomial time: Stage 1 solves a $d$-dimensional least-squares problem, and Stage 3 scans $M=\widetilde O(T^{1/3})$ residual-grid points per round. This gives total time $\widetilde O(T^{4/3}+T^{2/3}d^2+d^3)$ and memory $\widetilde O(T^{1/3}+d^2)$. Faster score maximization may improve constants in large-scale deployments, but is orthogonal to the regret analysis.

\paragraph{Ethical considerations.} This paper studies a theoretical online pricing model. The algorithm prices one item or service instance at a time and does not simultaneously offer the same identical good to different buyers at different prices. Nevertheless, contextual pricing can create disparate-impact concerns if contexts contain protected attributes or proxies. Responsible deployment should audit features, monitor realized prices and acceptance rates across groups, and enforce policy or fairness constraints when appropriate. The proposed method is relatively transparent---a linear predictor, a residual grid, and explicit confidence bounds---which can facilitate such audits.

\paragraph{Conclusion.} We presented a polynomial-time algorithm for contextual dynamic pricing with linear valuations and fully agnostic non-Lipschitz noise. The algorithm combines randomized estimation of the linear component, conservative markdown probes on a residual grid, and an optimistic redirect rule that controls discontinuity-induced bias without assuming smoothness of the demand curve. It achieves $\widetilde O(T^{2/3})$ expected regret, matching known lower bounds up to logarithmic factors. The result shows that atoms and arbitrary jumps in the noise distribution do not preclude optimal regret in contextual pricing, provided the algorithm uses a pricing rule that respects the one-sided structure of censored feedback.