Paper deep dive
Minimax-Optimal Semiparametric Contextual Dynamic Pricing with Multimodal Revenue
Xueping Gong, Zhuoluo Zhang, Zhaowei Miao, Jiheng Zhang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/5/2026, 5:10:44 AM
Summary
This paper addresses contextual dynamic pricing with arbitrary covariate sequences and bounded, possibly nonbinary purchase quantities. It proposes a pilot-corrected layered decision-partitioning (LDP) policy that handles semiparametric demand models with unknown linear valuation parameters and Hölder-smooth response functions. The method removes assumptions of concavity or strong unimodality on revenue, allowing for multimodal revenue landscapes. The policy achieves minimax-optimal regret rates up to logarithmic factors, matching a derived lower bound.
Entities (6)
Relation Signals (5)
Layered Decision-Partitioning (LDP) Policy → solves → Contextual Dynamic Pricing
confidence 97% · We develop a pilot-corrected layered decision-partitioning policy... The policy attains the minimax smoothness-dependent horizon rate
Contextual Dynamic Pricing → uses → Semiparametric Surplus-Index Model
confidence 95% · Demand follows a semiparametric surplus-index model with an unknown linear valuation parameter and an unknown Hölder-smooth response.
Semiparametric Surplus-Index Model → has → Hölder Smoothness
confidence 93% · Demand follows a semiparametric surplus-index model with an unknown linear valuation parameter and an unknown Hölder-smooth response.
Layered Decision-Partitioning (LDP) Policy → achieves → Minimax Regret
confidence 92% · The policy attains the minimax smoothness-dependent horizon rate up to logarithmic factors
Contextual Dynamic Pricing → relaxes → Strong Unimodality
confidence 90% · We impose neither concavity nor strong unimodality on revenue
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study contextual dynamic pricing with arbitrary covariate sequences and bounded, possibly nonbinary purchase quantities. Demand follows a semiparametric surplus-index model with an unknown linear valuation parameter and an unknown Hölder-smooth response. We impose neither concavity nor strong unimodality on revenue and allow nonunique optimal prices. We develop a pilot-corrected layered decision-partitioning policy that combines directional pilot estimation, local polynomial learning, predictable data assignment, and global action elimination. Pilot correction removes the first-order effect of valuation-parameter error, while permanent labels enable concentration under adaptive sampling. The policy attains the minimax smoothness-dependent horizon rate up to logarithmic factors; a matching lower bound already holds for a constant-context binary-demand subclass.
Tags
Links
- Source: https://arxiv.org/abs/2608.03142v1
- Canonical: https://arxiv.org/abs/2608.03142v1
Trouble viewing inline? Open PDF directly →
Full Text
196,210 characters extracted from source content.
Expand or collapse full text
Minimax-Optimal Semiparametric Contextual Dynamic Pricing with Multimodal Revenue Xueping Gong School of Management, Xiamen University, xgongah@xmu.edu.cn Zhuoluo Zhang School of Management, Xiamen University, zhangzhuoluo@xmu.edu.cn Zhaowei Miao School of Management, Xiamen University, miaozhaowei@xmu.edu.cn Jiheng Zhang Department of Industrial Engineering and Decision Analytics, The Hong Kong University of Science and Technology, jiheng@ust.hk Abstract We study contextual dynamic pricing with arbitrary covariate sequences and bounded, possibly nonbinary purchase quantities. Demand follows a semiparametric surplus-index model with an unknown linear valuation parameter and an unknown Hölder-smooth response. We impose neither concavity nor strong unimodality on revenue and allow nonunique optimal prices. We develop a pilot-corrected layered decision-partitioning policy that combines directional pilot estimation, local polynomial learning, predictable data assignment, and global action elimination. Pilot correction removes the first-order effect of valuation-parameter error, while permanent labels enable concentration under adaptive sampling. The policy attains the minimax smoothness-dependent horizon rate up to logarithmic factors; a matching lower bound already holds for a constant-context binary-demand subclass. Keywords: contextual dynamic pricing; semiparametric demand; bounded quantity feedback; shape-free revenue; minimax regret. 1 Introduction Dynamic pricing is a central problem in revenue management. A seller must learn how demand responds to prices while simultaneously using the accumulated information to generate revenue. This learning problem becomes more challenging when customer, product, or market heterogeneity is observed through covariates. Although such information enables personalized pricing, every posted price also determines what the seller subsequently learns. This feedback creates the exploration–exploitation trade-off at the heart of contextual dynamic pricing; see Den Boer (2015) for a broad review and Saharan et al. (2020) for applications. A widely studied framework models a customer’s latent valuation as a finite-dimensional function of the observed covariates plus an additive market shock. In semiparametric formulations, the contextual component is typically linear, whereas the distribution of the market shock is left unspecified (Javanmard and Nazerzadeh, 2019; Luo et al., 2022, 2024; Fan et al., 2024). This framework combines an interpretable representation of customer heterogeneity with a flexible demand curve. Binary purchase feedback dominates this single-index literature. Shape-free regret guarantees are available for Lipschitz links, whereas the higher-order-smooth literature typically couples smoothness with distributional coverage and/or stable revenue geometry. At Lipschitz smoothness, Tullii et al. (2024) allow arbitrary adaptive contexts and Gong et al. (2025) allow general valuation classes under independent and identically distributed contexts; both obtain the optimal shape-free two-thirds horizon exponent with binary feedback. For smoother links, recent improvements rely on nondegenerate or feature-diverse stochastic contexts together with stable revenue geometry (Han et al., 2026; Chai et al., 2026), or on a smooth oracle-price map induced by strong unimodality (Fan et al., 2026). A particularly consequential restriction is strong unimodality (Wang and Chen, 2025; Han et al., 2026; Fan et al., 2026). In the form used by recent smooth-pricing analyses, this condition requires every contextual revenue function to have a unique interior maximizer and its revenue loss to be uniformly comparable to the squared distance from that maximizer. It is therefore considerably stronger than smoothness or a local second-order condition. Strong unimodality rules out separated revenue modes, flat optimal-price regions, and many asymmetric or boundary-optimal revenue landscapes. At the same time, it provides several powerful analytical advantages: the policy can safely localize around one estimated optimizer, price-estimation errors translate into quadratic revenue losses, and the context-dependent optimal price can often be represented by a regular oracle price map. Indeed, these properties are central to the algorithms and improved regret guarantees in Wang and Chen (2025), Han et al. (2026), and Fan et al. (2026). This paper studies contextual pricing without these structural conveniences. In each period, the seller observes a covariate vector, posts a price, and observes a bounded purchase quantity, which may be binary, discrete, or continuous. Latent valuation is linear in the observed covariates and subject to an unknown market shock. After integrating out the shock, expected demand is an unknown function of the difference between price and a linear contextual valuation index; both the index parameter and the response function are unknown. The usual binary-purchase model is obtained as a special case, but the formulation also accommodates bounded unit sales and purchase volume. We allow the covariates to arrive arbitrarily and impose only Hölder smoothness on the observable response function. The induced revenue function may consequently be multimodal, may contain a flat optimal region, and need not have a unique maximizer. The smoothness assumption also has natural primitive foundations: it follows, for example, when the market-shock distribution is smooth and the quantity-response function has bounded variation, or when the quantity-response function is itself sufficiently smooth. Removing strong unimodality fundamentally changes the learning problem. Hölder smoothness controls only local approximation and provides no information about the global geometry of revenue. Learning accurately near a provisional optimizer is therefore insufficient: another, statistically similar region may contain a better and well-separated revenue mode. A policy that localizes prematurely may never collect enough information to discover that region. Consequently, the algorithm must preserve and compare candidates across the entire price domain rather than organize its exploration around a single estimated optimum or oracle price map. A second difficulty arises from the interaction between the unknown valuation parameter and the nonparametric response function. Directly inserting a pilot parameter estimate into a nonparametric regression transfers the pilot error to the fitted response curve at first order. This error can dominate the higher-order approximation accuracy that smoothness would otherwise provide. A natural remedy, used in classical single-index estimation and recent semiparametric pricing analyses, is to profile a nonparametric fit over candidate index parameters and refine the parameter through constrained least squares (Härdle et al., 1993; Ichimura, 1993; Horowitz and Härdle, 1996; Wang and Chen, 2025; Han et al., 2026). This remedy is statistically and computationally demanding. Because the local fits and their underlying sample assignments vary with the candidate parameter, the resulting objective is generally nonconvex, even in the twice-smooth case. Standard local optimization methods thus do not provide a global-solution guarantee. Moreover, the same observations are used both to construct the nonparametric fit and to evaluate the least-squares criterion, creating a complex dependence structure in online settings and making finite-sample confidence analysis delicate (Han et al., 2026). These issues motivate an approach that exploits higher-order smoothness without repeatedly solving a nonconvex joint-estimation problem. Adaptive data collection introduces a third challenge. Posted prices, residual bins, and subsequent exploration decisions all depend on previous outcomes. If past observations are reassigned whenever the valuation estimate changes, membership in a local dataset is determined retrospectively using information that was unavailable when the observation was collected. This destroys the predictable sampling structure needed for martingale concentration and makes standard offline nonparametric guarantees inapplicable. We address these challenges through a pilot-corrected layered decision-partitioning (LDP) policy. The pilot module uses uniform-price exploration to estimate the linear valuation component and evaluates its uncertainty only along the currently observed covariate direction. A well-covered direction enters the main pricing stage immediately, whereas an insufficiently covered direction triggers additional pilot exploration. This directional mechanism avoids distributional assumptions on the covariate sequence. During the main pricing stage, prices are represented relative to the estimated valuation index, and demand is learned locally in the resulting residual coordinate. An augmented local-polynomial representation absorbs the leading pilot perturbation into the regression coefficients, leaving only a second-order pilot error in addition to the usual nonparametric approximation error. Thus, the policy benefits from higher-order smoothness without solving the nonconvex constrained least-squares problems used in alternative joint estimation procedures. Each observation is also assigned a permanent layer–bin label before its demand is observed. These labels are never recomputed after the pilot estimate changes, preserving predictable sampling and enabling self-normalized concentration within every local dataset. Finally, the layered policy maintains candidate actions over the entire residual domain. An action is eliminated only when its optimistic revenue is statistically separated from the best surviving benchmark. This design protects distant modes and flat near-optimal regions and therefore performs global rather than local revenue learning. Balancing pilot exploration, local approximation, and statistical uncertainty yields the minimax smoothness-dependent horizon rate, up to logarithmic factors, for fixed problem primitives. We establish a matching expected-regret lower bound over an admissible constant-context, binary-demand subclass. The construction begins with a smooth instance whose revenue is flat over a nondegenerate interval and introduces statistically indistinguishable perturbations in separated price regions. Together, the upper and lower bounds characterize the minimax dependence on the horizon for the general revenue class considered here. 2 Contributions and Related Literature Contributions. Our contributions are twofold. • A shape-free model and higher-order online method. We combine arbitrary context sequences, general Hölder smoothness, and bounded quantity feedback in a translated-residual single-index model without concavity, strong unimodality, or a unique optimal price. Our pilot-corrected LDP policy integrates directional exploration, higher-order local polynomials, predictable permanent labels, and global elimination. Relative to the Lipschitz LDP framework of Gong et al. (2025), this replaces an episodic offline pilot and piecewise-constant learning with an online directional pilot, first-order error correction, and higher-order residual learning. • Minimax-optimal regret for shape-free smooth links. For fixed dimension and fixed problem primitives, the proposed policy achieves ~(Tβ+12β+1) O\! (T β+12β+1 ) regret, matching Ω(Tβ+12β+1) \! (T β+12β+1 ) lower bound. Together, the upper and lower bounds characterize the minimax horizon dependence for the general revenue class studied in this paper. 2.1 Related Literature Semiparametric contextual dynamic pricing. Contextual pricing with a linear valuation component and an additive shock has been studied under known parametric noise distributions (Javanmard and Nazerzadeh, 2019; Ban and Keskin, 2021), unknown nonparametric noise (Luo et al., 2022, 2024; Fan et al., 2024; Choi et al., 2023; Xu and Wang, 2022; Chai et al., 2026), and more general valuation or utility classes (Chen et al., 2024; Gong et al., 2025). These works differ in the feedback available, the distributional assumptions on contexts, and the geometry imposed on revenue. The papers most closely related to ours are summarized in Table 1. The rates in the last column suppress logarithmic factors and polynomial dependence on fixed problem primitives. Table 1: Representative results for smooth semiparametric contextual pricing. Here β denotes link or tail smoothness; rates suppress logarithmic factors and dependence on fixed problem primitives. Work Feedback Contexts Smoothness Revenue geometry Regret Tullii et al. (2024) Binary Arbitrary β=1β=1 General ~(T2/3) O(T^2/3) Gong et al. (2025) Binary i.i.d. β=1β=1 General ~(T2/3) O(T^2/3) Wang and Chen (2025) Binary i.i.d. β=2β=2 Strongly unimodal ~(T3/5) O(T^3/5) Han et al. (2026) Binary i.i.d. β≥2β≥ 2 Strongly unimodal ~(Tβ+12β+1) O(T β+12β+1) Fan et al. (2026) Binary Arbitrary β≥2β≥ 2 Strongly unimodal ~(T2β−14β−3+T) O(T 2β-14β-3+ T) This paper Bounded quantity Arbitrary β≥1β≥ 1 General ~(Tβ+12β+1) O(T β+12β+1) The principal comparison at β=1β=1 is Tullii et al. (2024): it already allows arbitrary adaptive contexts and general revenue geometry, and attains the same T2/3T^2/3 horizon exponent, but is restricted to binary feedback and Lipschitz smoothness. Gong et al. (2025) introduce the LDP architecture for a shape-free Lipschitz problem with binary feedback and i.i.d. contexts. Thus, our claim at β=1β=1 is not a better horizon exponent. The contribution is to retain arbitrary contexts and shape-free revenue while covering general β and bounded quantity feedback. For twice-smooth demand, Wang and Chen (2025) establish the sharp ~(T3/5) O(T^3/5) regret rate under strong unimodality and nondegenerate i.i.d. contexts, using contextual successive elimination together with semiparametric estimation. Han et al. (2026) extend this line to general Hölder smoothness by combining local-polynomial estimation with the stationary learning subroutine of Wang and Chen (2025), while retaining similar revenue-geometry and context-coverage conditions. Fan et al. (2026) also impose strong unimodality but allow arbitrary contexts; by directly learning the resulting smooth oracle-price map, they obtain a faster horizon exponent when β>2β>2. Our result addresses the complementary regime in which higher-order smoothness is available but the revenue geometry remains unrestricted. The flat-optimum construction underlying our lower bound shows that this distinction is structural: without strong unimodality, the hard instances need not admit a unique and stable oracle-price map on which localization can be based. Xu and Wang (2026) study an adjacent, nonnested regime: binary feedback with possibly discontinuous demand, including jumps induced by atoms, under stochastic well-conditioned contexts. Their model relaxes link regularity, whereas ours uses Hölder smoothness to handle arbitrary contexts and bounded quantity feedback. Algorithmically, our closest antecedent is the policy of Gong et al. (2025). Relative to its episodic offline pilot and piecewise-constant residual learning, our policy uses an online directional pilot, higher-order local polynomials, an augmented correction that makes pilot error second order, and permanent residual labels that preserve predictable sampling as the pilot evolves. Uniform-price exploration in Javanmard and Nazerzadeh (2019); Fan et al. (2024); Chen et al. (2024) and the arbitrary-context mechanisms in Tullii et al. (2024) provide additional points of contact. Nonparametric and multimodal pricing. Without covariates, nonparametric dynamic pricing has been studied under a range of smoothness and shape conditions (Besbes and Zeevi, 2009, 2015; Wang et al., 2021). In particular, Wang et al. (2021) establish the minimax rate ~(T(β+1)/(2β+1)) O(T^(β+1)/(2β+1)) for smooth multimodal revenue using local-polynomial optimism. Their confidence indices explicitly incorporate a local approximation envelope, and thus require the corresponding smoothness radius. Bounded quantity observations are not new by themselves. Wang et al. (2021) analyze general demand feedback without contexts, while Bu et al. (2022, 2025) study partially linear and separable contextual demand models. The present model instead places the unknown context effect inside the translated residual p−⊤⋆p- x θ_ . Consequently, the valuation shift and the nonparametric link must be learned jointly under an arbitrary context sequence. This translated single-index structure, rather than nonbinary feedback alone, is the relevant distinction. Layered contextual bandits. Our analysis draws on standard confidence-based methods for contextual bandits (Auer, 2002; Chu et al., 2011; Abbasi-Yadkori et al., 2011; Lattimore and Szepesvári, 2020). Classical layered partitioning separates observations by precision level to obtain sharper confidence control. In the present problem, however, the local regression model itself depends on an evolving pilot index and is only approximately specified. The permanent labeling rule is therefore essential: it fixes the residual coordinate, local bin, and stopping layer used for each observation before the outcome is revealed. This converts the adaptively collected local samples into predictable martingale arrays while retaining global price exploration. Organization. Section 3 introduces the model, the induced demand link, and its regularity. Section 4 presents the directional pilot, pilot-corrected local regression, and layered pricing policy. Section 5 establishes the regret upper bound and the matching minimax lower bound. The paper concludes with directions for future research. 3 Problem Formulation Notation. Throughout the paper, we write [n]:=1,…,n[n]:=\1,…,n\ for any positive integer n, denote the cardinality of a set A by |A||A|, and use E1\E\ for the indicator of an event E. For vectors, ∥⋅∥p\|·\|_p denotes the standard ℓp _p norm for 1≤p≤∞1≤ p≤∞. The notation ~ O suppresses absolute constants and logarithmic factors. For a positive definite matrix A, define ‖A:=⊤A\| z\|_A:= z A z. For an interval I=[a,b]I=[a,b], let ΠI(z):=minb,maxa,z _I(z):= \b, \a,z\\ denote projection onto I. Basic Model. We consider a contextual dynamic pricing problem over a finite horizon T. In each period t∈[T]t∈[T], a customer arrives and the seller observes a covariate vector t∈⊆ℝd x_t ^d that characterizes the observable customer, product, or market characteristics. Unlike standard i.i.d. assumptions, we do not impose any distributional assumption on the covariate sequence tt=1T\ x_t\_t=1^T; it can be arbitrary and possibly dependent. The covariate space is bounded, i.e., there exists Cx<∞C_x<∞ such that sup∈‖2≤Cx _ x \| x\|_2≤ C_x. For each t∈[T]t∈[T], let ℱt−1F_t-1 denote the σ-field generated by all observations and policy randomization available up to the end of period t−1t-1. Let UtU_t collect all within-period randomization used by the policy after observing t x_t. Conditional on ℱt−1∨σ(t)F_t-1 σ( x_t), the seed UtU_t is drawn independently of the current valuation shock. The customer’s valuation for the product is modeled as a linear function of the covariates plus random noise: vt=t⊤⋆+ϵt,v_t= x _t θ_ + _t, where ⋆∈Θ=∈ℝd:‖2≤Cθ θ_ ∈ =\ θ ^d:\| θ\|_2≤ C_θ\ is an unknown parameter vector, and ϵt _t is an unobserved random shock. The shocks ϵtt=1T\ _t\_t=1^T are independent and identically distributed according to an unknown cumulative distribution function F with zero mean. For every t∈[T]t∈[T], ϵt _t is independent of ℱt−1∨σ(t,Ut)F_t-1 σ( x_t,U_t). Assumption 3.1 (Bounded Valuations) There exist B>0B>0 and Bϵ∈(0,B/2)B_ε∈(0,B/2) such that: • The noise is uniformly bounded: |ϵt|≤Bϵ| _t|≤ B_ε almost surely. • The linear valuation satisfies ⊤⋆∈[Bϵ,B−Bϵ] x θ_ ∈[B_ε,B-B_ε] for all ∈ x . Assumption 3.1 guarantees that vt=t⊤⋆+ϵt∈[0,B]v_t= x _t θ_ + _t∈[0,B] almost surely, so the realized valuation and any feasible posted price lie in the same known interval [0,B][0,B]. This is a standard and natural requirement in practical pricing applications. After observing t x_t, the seller posts a per-unit price pt∈[0,B]p_t∈[0,B]. The price and every auxiliary action label constructed by the policy before demand is observed are measurable with respect to the full pre-demand information field t:=ℱt−1∨σ(t,Ut).G_t:=F_t-1 σ( x_t,U_t). If the realized valuation satisfies vt≥ptv_t≥ p_t, a sale occurs and the seller observes a positive purchase quantity yt>0y_t>0; otherwise, no sale occurs and yt=0y_t=0, i.e., yt>0=vt≥pt1\y_t>0\=1\v_t≥ p_t\ almost surely. The observed quantity yty_t may be discrete (e.g., number of units) or continuous (e.g., physical volume or usage), depending on the application. We assume there exists a constant 0<D<∞0<D<∞ such that 0≤yt≤D0≤ y_t≤ D almost surely. The realized revenue at time t is ptytp_ty_t, and each round yields the observation triple (t,pt,yt)( x_t,p_t,y_t). We set ℱt:=t∨σ(yt)F_t:=G_t σ(y_t), so tG_t and ℱtF_t describe, respectively, all information immediately before and after current demand is observed. Generalized Single Index Model. The basic model above only specifies the qualitative relationship between yty_t and the surplus vt−ptv_t-p_t. However, to enable statistical learning and regret minimization, the seller must quantify how the expected demand varies with the posted price and covariates. To make the problem tractable while retaining flexibility, we adopt a surplus-dependent single-index structure. This formulation generalizes the widely studied binary purchase model (Fan et al., 2026; Han et al., 2026; Luo et al., 2024; Fan et al., 2024; Gong et al., 2025) by allowing the realized demand quantity to depend on the surplus through a function q(⋅)q(·), rather than restricting to a binary sale indicator. Specifically, we posit that, conditional on the information available before demand is observed and on the realized valuation, the expected demand depends on the current price and covariates only through the net surplus vt−ptv_t-p_t. This single-index form is natural: it implies that a customer’s purchasing quantity decision is driven by the perceived value relative to the price, rather than by their absolute levels separately. Under this premise, there exists an unknown baseline function q(⋅)q(·) that maps the surplus to the expected quantity. Importantly, we impose no parametric form, such as a linear or logistic specification, on q, allowing it to accommodate richly heterogeneous and potentially nonmonotone demand responses. The formal statement is as follows. Assumption 3.2 (Surplus-dependent demand response) There exists an unknown measurable function q:ℝ→[0,D]q:R→[0,D] with q(z)=0q(z)=0 for z<0z<0 or z>Bz>B and q(z)>0q(z)>0 for z∈[0,B]z∈[0,B], such that, for every t∈[T]t∈[T], [yt|t∨σ(vt)]=q(vt−pt)almost surely.E\! [y_t\, |\,G_t σ(v_t) ]=q(v_t-p_t) surely. Assumption 3.2 formalizes the surplus-dependent single-index structure introduced above. It posits that, conditional on all pre-demand information and the realized valuation, the conditional mean demand is determined solely by the realized surplus vt−ptv_t-p_t and the functional form q(⋅)q(·) is left fully nonparametric. The zero restriction for negative surplus is consistent with the no-sale condition. The zero extension beyond B is only a technical convention, because such surplus cannot arise under Assumption 3.1. For an affordable purchase, the incidence condition implies positive realized quantity, and we choose the version of the conditional-mean function that is strictly positive on [0,B][0,B]. Crucially, we impose no monotonicity, concavity, or unimodality assumptions on q. This allows q to capture rich and potentially irregular demand patterns—such as quantity discounts, satiation effects, or Giffen-like behaviors at the micro level—that are often excluded by parametric specifications. Define the effective residual domain ℐg:=[−B+Bϵ,B−Bϵ]I_g:=[-B+B_ε,B-B_ε]. The function q characterizes the expected demand conditional on the realized valuation vt=sv_t=s, which is unobservable to the seller. For decision-making and regret analysis, however, we require the expected demand conditional on the information available before the current demand is observed. To bridge this gap, we integrate out the noise ϵt _t from the surplus s−pt=⋆⊤t+ϵt−pts-p_t= θ_ x_t+ _t-p_t. This yields an induced link function g, defined as the convolution of q with the noise distribution F: g(u):=[q(ϵt−u)],u∈ℐg,g(u):=E\! [q( _t-u) ], u _g, where u=p−⋆⊤u=p- θ_ x. Then, by iterated expectations and the sequential exogeneity of ϵt _t, we obtain, [yt|t]=g(pt−t⊤⋆).E\! [y_t\, |\,G_t ]=g\! (p_t- x_t θ_ ). In this way, g serves as the demand link that replaces the latent q, and all subsequent estimation and regret guarantees will be stated in terms of g. Revenue and Regret. Given covariate x and price p, the expected revenue is (,p)=pg(p−⋆⊤), Rev( x,p)=p\,g(p- θ_ x), Let p⋆()∈argmaxp∈[0,B](,p)p ( x)∈ _p∈[0,B] Rev( x,p) be an arbitrary maximizer, and write pt⋆:=p⋆(t)p_t :=p ( x_t) for period t. The cumulative regret is Reg(T)=∑t=1T((t,pt⋆)−(t,pt)).Reg(T)= _t=1^T ( Rev( x_t,p_t )- Rev( x_t,p_t) ). The goal is to design a nonanticipating pricing policy that, for each t, selects ptp_t based on the current covariate t x_t and all past observations (s,ps,ys)s=1t−1\( x_s,p_s,y_s)\_s=1^t-1, so as to minimize Reg(T)Reg(T) while learning the unknown valuation parameter ⋆ θ_ and the induced demand link g. Regularity. To enable nonparametric estimation, we directly assume the observable induced link function g belongs to a Hölder class. This direct approach is standard in the dynamic pricing literature (Bu et al., 2025; Wang et al., 2021) and facilitates transparent convergence analysis, since g is the direct object of estimation. Definition 3.3 (Hölder class) Let ℐ⊂ℝI be a compact interval, β≥1β≥ 1, and 0<L<∞0<L<∞. Define ϖ(β):=maxk∈ℤ≥0:k<β. (β):= \k _≥ 0:k<β\. A function f:ℐ→ℝf:I belongs to ℋ(β,L;ℐ)H(β,L;I) if f is ϖ(β) (β)-times differentiable on ℐI and |f(ϖ(β))(u)−f(ϖ(β))(u′)|≤L|u−u′|β−ϖ(β),∀u,u′∈ℐ. |f^( (β))(u)-f^( (β))(u ) |≤ L|u-u |^β- (β), ∀ u,u . Assumption 3.4 (Smoothness of the Induced Link) The induced link function satisfies g∈ℋ(β,Lg;ℐg)g (β,L_g;I_g) for some β≥1β≥ 1 and 0<Lg<∞0<L_g<∞. For the contextual policy, the smoothness parameters β and LgL_g are treated as known. Throughout this paper, CgC_g denotes a fixed, class-level upper envelope for the derivatives of g up to order ϖ(β) (β). Because 0≤g≤D0≤ g≤ D on the interval ℐgI_g, a standard one-dimensional interpolation inequality allows CgC_g to be chosen as a function only of B,Bϵ,D,βB,B_ε,D,β, and LgL_g. Thus, the constants used by the policy do not depend on unknown instance-specific derivative values. When the domain ℐI is clear from the context, we write ℋ(β)H(β) for simplicity. Justification of Assumption 3.4. A natural question is whether directly assuming Hölder smoothness on g is too restrictive. In our framework, this assumption is in fact mild, because the convolutional structure g(u)=[q(ϵt−u)]g(u)=E[q( _t-u)] allows g to inherit smoothness from more primitive components. The following concrete scenario shows when Assumption 3.4 automatically holds. Smooth noise distribution. Suppose the noise distribution F itself is Hölder smooth, i.e., F∈ℋ(β,LF;[−B,B])F (β,L_F;[-B,B]). Even if the nonparametric demand response q only has bounded variation (allowing jumps and discontinuities), the convolution with F regularizes g. The following proposition formalizes this. Proposition 3.5 Under Assumptions 3.1 and 3.2, and assuming that q is of bounded variation on [0,B][0,B], if F∈ℋ(β,LF;[−B,B])F (β,L_F;[-B,B]), then g∈ℋ(β,(D+Vq)LF;ℐg)g (β,(D+V_q)L_F;I_g), where VqV_q denotes the total variation of q on [0,B][0,B]. In the special case of binary demand where q(z)=0≤z≤Bq(z)=1\0≤ z≤ B\, the induced link reduces to the survival function g(u)=1−F(u)g(u)=1-F(u) whenever F is continuous, thereby recovering the classical binary-purchase dynamic pricing model. This special case encompasses a broad range of existing work that assumes F to be Lipschitz (Besbes and Zeevi, 2009; Gong et al., 2025), to have a Lipschitz first derivative (Wang and Chen, 2025), or to be m-times continuously differentiable (Fan et al., 2024; Wang et al., 2021). This example demonstrates that Assumption 3.4 is not an extraneous restriction: it follows from smooth valuation noise even when the quantity response itself has jumps. The model contains the bounded binary-purchase formulation as a special case while relaxing its revenue-geometry restrictions; it does not require the revenue function to be concave or the optimal price to be unique. Remark 3.6 (Strong unimodality) Several recent studies impose a strong-unimodality condition: for every context x, the function (,⋅) Rev( x,·) has a unique interior maximizer, and the revenue loss is comparable to the squared distance from that maximizer (Wang and Chen, 2025; Han et al., 2026; Fan et al., 2026). This structure permits the policy to localize around a single price and, under additional smoothness, to learn a stable oracle-price map. We do not impose strong unimodality. Consequently, (,⋅) Rev( x,·) may have multiple separated modes or nonunique maximizers, and small estimation errors may change which price region appears optimal. Localized search and oracle-price-map reductions are therefore not generally valid, motivating the global residual-space learning procedure developed in Section 4. 4 Algorithm The policy has three coupled components, summarized in Figure 1. First, uncertainty-triggered uniform-price exploration estimates the valuation index only along the current context direction. Second, a pilot-corrected local-polynomial feature absorbs the first-order index error, leaving the usual local approximation error and a second-order pilot term. Third, a layered rule compares candidate residual actions globally, rather than localizing around one provisional optimizer. Every main-policy observation receives its residual-bin and stopping-layer labels before demand is observed, and these labels are never recomputed. The resulting predictable datasets support martingale concentration even though prices and visited bins are selected adaptively. The following subsections define the pilot, correction, confidence radius, and global elimination rule in that order. (a) Adaptive pilotObserve context t x_tCompute ^t θ_t and γT‖t‖Mt−1 _T\| x_t\|_M_t^-1>η>η? Pilot exploration pt∼Unif[0,B]p_t [0,B] Update (Mt,t)(M_t, b_t) Certified pilot index u^t=Π[0,B](t⊤^t) u_t= _[0,B]( x_t θ_t) yesno|u^t−t⊤⋆|≤η| u_t- x_t θ_ |≤η(b) Global residual learning p^t(w)=u^t+w p_t(w)= u_t+w, w∈[−B,B]w∈[-B,B] wwI1I_1I2I_2IjI_jIj+1I_j+1INI_Nwwwttrue:=p^t(w)−t⊤⋆w_t true:= p_t(w)- x_t θ_ , |wttrue−w|≤η|w_t true-w|≤η (ϕj(w)+(p^t(w)−w)ϕj′(w)−j(,w)) pmatrix _j(w)+( p_t(w)-w) _j (w)\\[-2.84526pt] -X_j( x,w) pmatrix local polynomial + first-order pilot correction g(p^t(w)−t⊤⋆)=ψt,j(w)⊤j+(hβ+η2) g\! ( p_t(w)- x_t θ_ )= _t,j(w) z_j+O(h^β+η^2) (c) Layered global UCBs=1s=1s=2s=2s=3s=3precision passand eliminationfiner layer Explore and stop at sts_t Choose largest UCB Fix (st,jt,wt)(s_t,j_t,w_t) before observing yty_t pt=p^t(wt)⟶yt⟶Ψt+1,stjt=Ψt,stjt∪t p_t= p_t(w_t)\; \;y_t\; \; _t+1,s_t^j_t= _t,s_t^j_t∪\t\ Figure 1: Overview of the proposed adaptive semiparametric pricing policy. Panel (a) shows the uncertainty-triggered pilot module. Panel (b) illustrates global residual-space learning and the augmented first-order correction for pilot-index error. Panel (c) depicts nested survivor sets under layered UCB exploration and elimination; outline, hatching, and solid fill distinguish active, surviving, and final actions in grayscale. 4.1 Adaptive Pilot Estimation The pilot module is introduced first because the subsequent residual representation requires an accurate valuation index at the current covariate. Importantly, the policy does not require ^t θ_t to approximate ⋆ θ_ uniformly in Euclidean norm. It only needs to certify the scalar index t⊤⋆ x_t θ_ along the currently observed direction. This context-specific requirement is particularly useful when the covariates need not be independently sampled: directions that are already well covered can immediately enter the main pricing module, whereas insufficiently covered directions trigger additional pilot exploration. The pilot estimator is constructed exclusively from uniform-price exploration rounds. On such a round, the pseudo-response Byt>0B1\y_t>0\ is an unbiased observation of t⊤⋆ x_t θ_ . Accordingly, MtM_t and t b_t form the regularized design matrix and response vector based on the pilot-exploration data, and ^t=Mt−1t θ_t=M_t^-1 b_t. The quantity γT‖t‖Mt−1 _T\| x_t\|_M_t^-1 measures the remaining uncertainty in the current valuation index. If this quantity exceeds the target accuracy η, the policy collects an additional uniform-price observation. Otherwise, it invokes the layered pricing module. Algorithm 1 Contextual Dynamic Pricing with Adaptive Pilot and Permanent Bin Labels 1:Pilot accuracy η, horizon T, smoothness β, bounds Cθ,Cx,B,DC_θ,C_x,B,D, number of bins N, regularization λ>0λ>0, confidence constants Cz,Cψ,ClC_z,C_ψ,C_l, and confidence level δ∈(0,1)δ∈(0,1) 2:Set γT←Bdlog(1+TCx2/d)+2log(4/δ)+Cθ _T← B d (1+TC_x^2/d )+2 (4/δ )+C_θ and S←max1,⌈log2T⌉,S← \1, _2 T \, 3:Initialize exp←∅T exp← , M1←IdM_1← I_d, 1←d b_1← 0_d, and Ψ1,sj←∅ _1,s^j← for every s∈[S]s∈[S] and j∈[N]j∈[N] 4:for t=1,…,Tt=1,…,T do 5: Observe t x_t and set ^t←Mt−1t θ_t← M_t^-1 b_t 6: if γT‖t‖Mt−1>η _T\| x_t\|_M_t^-1>η then 7: Set exp←exp∪tT exp exp∪\t\ 8: Draw pt∼Unif[0,B]p_t Unif[0,B], post ptp_t, and observe yt∈[0,D]y_t∈[0,D] 9: Set Mt+1←Mt+tt⊤,t+1←t+Byt>0tM_t+1← M_t+ x_t x_t , b_t+1← b_t+B1\y_t>0\ x_t 10: Set Ψt+1,sj←Ψt,sj, _t+1,s^j← _t,s^j, for all s∈[S]s∈[S] and j∈[N]j∈[N] 11: else 12: Run Algorithm 2 and obtain (st,jt,wt,pt)(s_t,j_t,w_t,p_t) 13: Record (st,jt,wt)(s_t,j_t,w_t) as the permanent layer, bin, and residual-action labels of period t 14: Post ptp_t and observe yt∈[0,D]y_t∈[0,D] 15: Set Mt+1←MtM_t+1← M_t, t+1←t b_t+1← b_t, and Ψt+1,sj←Ψt,sj∪t,s=st,j=jtΨt,sj,otherwise. _t+1,s^j← cases _t,s^j∪\t\,&s=s_t,j=j_t\\ _t,s^j,&otherwise. cases Algorithm 1 gives the outer wrapper of the policy; the layered pricing subroutine is specified subsequently. We refer to rounds on which uniform pricing is used as pilot-exploration rounds, and to all remaining rounds as LDP rounds. Although later pilot-exploration rounds may update ^t θ_t, the bin and layer labels assigned to an LDP observation are permanent and are never recomputed using a later pilot. Algorithm 2 assigns each LDP round a stopping layer sts_t and a permanent bin label jtj_t. For each pair (s,j)(s,j), the outer wrapper maintains a dataset Ψt,sj, _t,s^j, which stores all past LDP observations carrying that fixed label. The task of selecting (st,jt)(s_t,j_t) is entirely delegated to Algorithm 2; the outer algorithm only appends the current observation to the corresponding Ψt+1,stjt _t+1,s_t^j_t. The following lemma validates the uncertainty gate in Algorithm 1. It provides a time-uniform, direction-dependent confidence bound and therefore guarantees that the valuation index is sufficiently accurate whenever the policy enters an LDP round. Lemma 4.1 (Pilot estimation confidence) With the value of γT _T specified in Algorithm 1, with probability at least 1−δ/21-δ/2, simultaneously for every t≤Tt≤ T and every ∈ℝd x ^d, |⊤(^t−⋆)|≤γT‖Mt−1. | x ( θ_t- θ_ ) |≤ _T\| x\|_M_t^-1. (1) Consequently, on the event in Lemma 4.1, every LDP round t satisfies |Π[0,B](t⊤^t)−t⊤⋆|≤η. | _[0,B] ( x_t θ_t )- x_t θ_ |≤η. Therefore, for every feasible pilot-residual action w, p^t(w)−t⊤⋆=w+[Π[0,B](t⊤^t)−t⊤⋆], p_t(w)- x_t θ_ =w+ [ _[0,B] ( x_t θ_t )- x_t θ_ ], so the true residual differs from its pilot counterpart w by at most η. This certification localizes the evaluation point of g, but it does not by itself eliminate the resulting first-order error. We next incorporate this displacement directly into the local regression feature. 4.2 Pilot-Corrected Local Regression The pilot certificate controls the valuation-index error at the current context, but does not by itself remove its effect on estimating the unknown demand link. On the pilot-confidence event, |p^t(w)−w−t⊤⋆|≤η| p_t(w)-w- x_t θ_ |≤η. An ordinary local-polynomial regression indexed by w ignores this displacement and therefore incurs a first-order error of order η. When β>1β>1, this error may dominate the target local-polynomial bias hβh^β, where h denotes the bin width defined below. Existing smooth semiparametric pricing methods address this coupling by jointly refining the index parameter and the local approximation of g (Wang and Chen, 2025; Han et al., 2026). Conditional on a candidate θ, both the local regressors and their Gram matrix depend on θ. Profiling out the polynomial coefficients consequently leads to a constrained least-squares problem that is generally nonconvex and does not, in general, admit a globally certified solution. Our key simplification is to target prediction rather than structural joint identification. Pricing requires accurate predictions of g(p−⊤⋆),g\! (p- x θ_ ), but does not require a separate refinement of ⋆ θ_ within every local regression. We therefore retain the complete first-order effect of the pilot-index displacement and estimate the resulting products as composite coefficients. This prediction-preserving lifting converts the coupled estimation problem into a convex ridge regression while leaving only a second-order pilot remainder. To formalize this construction, partition the residual space [−B,B][-B,B] 111For the analysis, we extend g from ℐgI_g to [−B,B][-B,B] by its endpoint Taylor polynomials of order ϖ(β) (β), and continue to denote the extension by g. The extension agrees with the original induced link on ℐgI_g and belongs to ℋ(β,Lg;[−B,B])H(β,L_g;[-B,B]). It is used only to define the comparison coefficients and does not modify the demand model or the policy. into N bins of equal width h=2B/Nh=2B/N. Let aj=−B+2BjN,a_j=-B+ 2BjN, for j=0,1,…,N,j=0,1,…,N, and define Ij=[aj−1,aj),j=1,…,N−1,IN=[aN−1,aN].I_j=[a_j-1,a_j), j=1,…,N-1, I_N=[a_N-1,a_N]. For each IjI_j, define the local-polynomial feature anchored at aj−1a_j-1 by ϕj(u):=(1,u−aj−1,…,(u−aj−1)ϖ(β))⊤∈ℝ1+ϖ(β), _j(u):= (1,\,u-a_j-1,\,…,\,(u-a_j-1) (β) ) ^1+ (β), and let ϕj′(u) _j (u) denote its componentwise derivative. When ϖ(β)≥1 (β)≥ 1, define j(,u):=(2(u−aj−1)⋮ϖ(β)(u−aj−1)ϖ(β)−1)∈ℝϖ(β)d;X_j( x,u):= pmatrix x\\ 2(u-a_j-1) x\\ \\ (β)(u-a_j-1) (β)-1 x pmatrix (β)d; when ϖ(β)=0 (β)=0, let j(,u)X_j( x,u) be the empty vector. For w∈Ijw∈ I_j, expanding around the bin anchor and retaining the first-order pilot displacement gives g(p^t(w)−t⊤⋆)= g\! ( p_t(w)- x_t θ_ )= ϕj(w)⊤(g(aj−1)g′(aj−1)⋮g(ϖ(β))(aj−1)/ϖ(β)!) _j(w) pmatrixg(a_j-1)\\ g (a_j-1)\\ \\ g^( (β))(a_j-1)/ (β)! pmatrix (2) +(p^t(w)−w−t⊤⋆)ϕj′(w)⊤(g(aj−1)g′(aj−1)⋮g(ϖ(β))(aj−1)/ϖ(β)!)+Rt,j(w), +( p_t(w)-w- x_t θ_ ) _j (w) pmatrixg(a_j-1)\\ g (a_j-1)\\ \\ g^( (β))(a_j-1)/ (β)! pmatrix+R_t,j(w), where, under η≤hη≤ h, |Rt,j(w)|≤Cl(hβ+η2).|R_t,j(w)|≤ C_l (h^β+η^2 ). The two components of the remainder correspond to the local-polynomial approximation error and the second-order pilot-displacement error, respectively. Hence, the first-order representation in (2) can be rewritten as [ϕj(w)+(p^t(w)−w)ϕj′(w)]⊤(g(aj−1)g′(aj−1)⋮g(ϖ(β))(aj−1)/ϖ(β)!)−j(t,w)⊤(g′(aj−1)⋆⋮g(ϖ(β))(aj−1)ϖ(β)!⋆). [ _j(w)+ ( p_t(w)-w ) _j (w) ] pmatrixg(a_j-1)\\ g (a_j-1)\\ \\ g^( (β))(a_j-1)/ (β)! pmatrix-X_j( x_t,w) pmatrixg (a_j-1) θ_ \\ \\ g^( (β))(a_j-1) (β)! θ_ pmatrix. The second term contains products between the local derivative coefficients and ⋆ θ_ . Enforcing their common factorization through ⋆ θ_ would recover the nonlinear coupling underlying the constrained joint estimators in prior work. Instead, we treat these products directly as composite coefficients. Specifically, define a 1+ϖ(β)(d+1)1+ (β)(d+1)-dimensional column vector j:=(g(aj−1),g′(aj−1),…,g(ϖ(β))(aj−1)ϖ(β)!,(g′(aj−1)⋆)⊤,…,(g(ϖ(β))(aj−1)ϖ(β)!⋆)⊤)⊤, z_j:= (g(a_j-1),\ g (a_j-1),\ …,\ g^( (β))(a_j-1) (β)!,\ (g (a_j-1) θ_ ) ,\ …,\ ( g^( (β))(a_j-1) (β)! θ_ ) ) , and, for every t, j, and w∈Ijw∈ I_j, define the pilot-corrected feature ψt,j(w):=(ϕj(w)+(p^t(w)−w)ϕj′(w)−j(t,w))∈ℝ1+ϖ(β)(d+1). _t,j(w):= pmatrix _j(w)+ ( p_t(w)-w ) _j (w)\\[2.84526pt] -X_j( x_t,w) pmatrix ^1+ (β)(d+1). (3) Equation (2) then becomes g(p^t(w)−t⊤⋆)=ψt,j(w)⊤j+Rt,j(w),|Rt,j(w)|≤Cl(hβ+η2).g\! ( p_t(w)- x_t θ_ )= _t,j(w) z_j+R_t,j(w), |R_t,j(w)|≤ C_l (h^β+η^2 ). (4) Thus, up to a higher-order deterministic remainder, the conditional mean belongs to a finite-dimensional linear prediction class. When β=1β=1, we have ϖ(β)=0 (β)=0; the derivative block is absent, and the pilot displacement is absorbed into the (h)O(h) approximation error under η≤hη≤ h. For each layer–bin pair (s,j)(s,j), we estimate the composite coefficient using observations carrying the corresponding permanent labels. Define Λt,sj:=∑i∈Ψt,sjψi,j(wi)ψi,j(wi)⊤. _t,s^j:= _i∈ _t,s^j _i,j(w_i) _i,j(w_i) . Fix a regularization parameter λ>0λ>0. The ridge estimator is ^t,sj z_t,s^j :=argmin∈ℝ1+ϖ(β)(d+1)∑i∈Ψt,sj(yi−ψi,j(wi)⊤)2+λ‖22=(λI+Λt,sj)−1∑i∈Ψt,sjyiψi,j(wi). = *argmin_ z ^1+ (β)(d+1) \ _i∈ _t,s^j (y_i- _i,j(w_i) z )^2+λ\| z\|_2^2 \= (λ I+ _t,s^j )^-1 _i∈ _t,s^jy_i _i,j(w_i). (5) For w∈Ijw∈ I_j, the corresponding demand estimate based on Ψt,sj _t,s^j is g^t,sj(w):=Π[0,D](ψt,j(w)⊤^t,sj). g_t,s^j(w):= _[0,D]\! ( _t,j(w) z_t,s^j ). (6) The estimator in (5) does not approximate a local solution of the preceding nonconvex joint-estimation problem. Instead, it relaxes the factorization restrictions among the derivative coefficients and estimates the prediction-sufficient composite coefficients directly. The population vector j z_j remains in the lifted class, so this relaxation introduces no additional first-order approximation error. Its deterministic misspecification is bounded by (hβ+η2)O(h^β+η^2). Once the lifted features have been constructed, (5) is a standard strictly convex ridge regression and therefore has the displayed unique global solution. Moreover, each feature ψi,j(wi) _i,j(w_i) is determined before yiy_i is observed, allowing the stochastic regression errors to be analyzed as a predictable martingale transform. Under η2≲hβη^2 h^β, the lifting preserves the local-polynomial approximation order while avoiding nonconvex joint refinement altogether. The next subsection converts these point predictions into confidence bounds and incorporates them into the layered decision rule. 4.3 Layered Decision Making The preceding pilot-corrected regression converts the coupled semiparametric estimation problem into a convex linear prediction problem and provides a point estimate of demand for each feasible residual action. Point predictions alone, however, are insufficient for sequential pricing: the amount of information varies across layer–bin pairs, and the lifted representation retains a deterministic approximation error of order (hβ+η2)O(h^β+η^2). We therefore construct confidence bounds that jointly account for stochastic estimation error, ridge regularization, and this remaining approximation error, and use them to form optimistic estimates of the corresponding revenues. Confidence radius. The explicit form of the radius is rt,sj(w)=minD, r_t,s^j(w)= \D, CψDιT‖ψt,j(w)‖(Λt,sj+λI)−1⏟stochastic estimation error+Czλ‖ψt,j(w)‖(Λt,sj+λI)−1⏟ridge bias C_ψD _T \| _t,j(w) \|_( _t,s^j+λ I)^-1_ stochastic estimation error+ C_z λ \| _t,j(w) \|_( _t,s^j+λ I)^-1_ ridge bias (7) +Cl(hβ+η2)|Ψt,sj|‖ψt,j(w)‖(Λt,sj+λI)−1⏟historical approximation error+Cl(hβ+η2)⏟current-action approximation error, + C_l(h^β+η^2) | _t,s^j| \| _t,j(w) \|_( _t,s^j+λ I)^-1_ historical approximation error+ C_l(h^β+η^2)_ current-action approximation error \, with ιT:=2log(4SNδ)+[1+ϖ(β)(d+1)]log(1+Tλ). _T:=2 ( 4SNδ )+ [1+ (β)(d+1) ] (1+ Tλ ). (8) If |Ψt,sj|=0| _t,s^j|=0, we set rt,sj(w)=Dr_t,s^j(w)=D. The four summands in (7) have distinct roles: self-normalized concentration controls the centered demand noise; the ridge penalty contributes CzλC_z λ; the accumulated historical remainders contribute the term proportional to |Ψt,sj| | _t,s^j|; and the final term controls the current action’s approximation error. Projection onto [0,D][0,D] cannot increase error relative to a target in that interval. Proposition 4.2 formalizes this decomposition and proves that rt,sj(w)r_t,s^j(w) is a simultaneous confidence radius. Proposition 4.2 (Confidence bound) Suppose Assumptions 3.1, 3.2, and 3.4 hold. Let λ>0λ>0, δ∈(0,1)δ∈(0,1), and 0<η≤h0<η≤ h. Let Cz,Cl,Cψ>0C_z,C_l,C_ψ>0 be the finite constants specified in (25), (27), and (35). Then, with probability at least 1−δ1-δ, simultaneously for every LDP round t, every s∈[st]s∈[s_t], and every (j,w)∈t,s(j,w) _t,s, |g^t,sj(w)−g(p^t(w)−t⊤⋆)|≤rt,sj(w). | g_t,s^j(w)-g\! ( p_t(w)- x_t θ_ ) |≤ r_t,s^j(w). (9) Layered exploration and elimination. Algorithm 2 Layered Decision Making with Pilot-Residual Actions 1:Current round t, context t x_t, certified pilot ^t θ_t, permanent datasets Ψt,sjs∈[S],j∈[N]\ _t,s^j\_s∈[S],j∈[N], bin partition Ijj∈[N]\I_j\_j∈[N], and constants Cψ,Cz,ClC_ψ,C_z,C_l 2:Discretize the residual-action space by :=−B+kT−1/2:k=0,1,…,⌊2BT⌋∪0,B.W:= \-B+kT^-1/2:k=0,1,…, 2B T \∪\0,B\. 3:Set u^t←Π[0,B](t⊤^t),p^t(w)←u^t+w. u_t← _[0,B]\! ( x_t θ_t ), p_t(w)← u_t+w. 4:for each j∈[N]j∈[N] do 5: Set t,j←w∈∩Ij:0≤p^t(w)≤B.W_t,j← \w ∩ I_j:0≤ p_t(w)≤ B \. 6:Set s←1,t,1←(j,w):j∈[N],w∈t,j.s← 1,A_t,1← \(j,w):j∈[N],\ w _t,j \. 7:repeat 8: Set t,s←j∈[N]:(j,w)∈t,s for some w.J_t,s← \j∈[N]:(j,w) _t,s for some w \. 9: for each j∈t,sj _t,s do 10: Compute ^t,sj z_t,s^j by (5) 11: for each (j,w)∈t,s(j,w) _t,s do 12: Compute g^t,sj(w)←Π[0,D](ψt,j(w)⊤^t,sj). g_t,s^j(w)← _[0,D]\! ( _t,j(w) z_t,s^j ). 13: Compute rt,sj(w)r_t,s^j(w) by (7) 14: Set Ut,sj(w)←p^t(w)minD,g^t,sj(w)+rt,sj(w),widt,sj(w)←p^t(w)rt,sj(w).U_t,s^j(w)← p_t(w) \D,\, g_t,s^j(w)+r_t,s^j(w) \,wid_t,s^j(w)← p_t(w)r_t,s^j(w). 15: if s=Ss=S then 16: Select (jt,wt)∈argmax(j,w)∈t,sUt,sj(w),st←s.(j_t,w_t)∈ *argmax_(j,w) _t,sU_t,s^j(w), s_t← s. 17: else if max(j,w)∈t,swidt,sj(w)≤BD 2−s _(j,w) _t,swid_t,s^j(w)≤ BD\,2^-s then 18: Set t,s+1←(j,w)∈t,s:Ut,sj(w)≥max(j′,w′)∈t,sUt,sj′(w′)−BD 21−s,A_t,s+1← \(j,w) _t,s:U_t,s^j(w)≥ _(j ,w ) _t,sU_t,s^j (w )-BD\,2^1-s \, 19: Set s←s+1s← s+1. 20: else 21: Set t,su←(j,w)∈t,s:widt,sj(w)>BD 2−s.A_t,s^u← \(j,w) _t,s:wid_t,s^j(w)>BD\,2^-s \. 22: Select (jt,wt)∈argmax(j,w)∈t,suUt,sj(w),st←s.(j_t,w_t)∈ *argmax_(j,w) _t,s^uU_t,s^j(w), s_t← s. 23:until (jt,wt)(j_t,w_t) has been selected 24:Set pt←p^t(wt)p_t← p_t(w_t). 25:return (st,jt,wt,pt)(s_t,j_t,w_t,p_t). The layered decision rule proceeds by refining the revenue resolution level by level. At layer s, the target resolution is BD 2−sBD\,2^-s. For every action (j,w)(j,w) surviving in the current active set t,sA_t,s, the algorithm maintains an optimistic revenue Ut,sj(w)U_t,s^j(w) and a width widt,sj(w)wid_t,s^j(w) that measures the remaining uncertainty in its estimated revenue. The policy then decides whether to sample at this layer or to advance. If there exists an action in t,sA_t,s with width strictly greater than BD 2−sBD\,2^-s, the policy selects one such under-explored action and assigns the current observation permanently to layer s and the corresponding bin j. This sampling step directly reduces the uncertainty of that action. Otherwise, if every surviving action satisfies widt,sj(w)≤BD 2−swid_t,s^j(w)≤ BD\,2^-s, then the layer is considered sufficiently resolved. Our policy eliminates all actions whose optimistic revenue falls more than BD 21−sBD\,2^1-s below the largest optimistic revenue among the survivors, and passes the remaining actions to the next layer s+1s+1. The safety of this elimination follows from the confidence bounds. Crucially, this argument does not require strong unimodality, local curvature, or uniqueness of the revenue maximizer, because it compares all surviving actions globally. If the policy proceeds to layer s+1s+1, it repeats the same check with the finer resolution BD 2−(s+1)BD\,2^-(s+1). Once all layers up to S have been passed, the final action is chosen as the one with the largest UCB among the remaining active set. Algorithm 2 implements this layered procedure. It starts with the full feasible residual grid and sequentially examines the layers. At each layer, it first computes the required estimates and widths; if an under-explored action is found, the round stops and the observation is assigned to that layer. Otherwise, it performs elimination and continues without consuming the current observation. The process terminates when either an action is selected for sampling or the final layer is reached, in which case the action with the highest UCB is chosen. 5 Regret Analysis 5.1 Upper Bound We now analyze the regret of the proposed policy. The proof follows the two operating modes of Algorithm 1. On LDP rounds, the confidence bounds translate the stopping layer into a one-period revenue guarantee. We then control how often the policy can stop at each layer by combining the layer-specific uncertainty threshold with an elliptical-potential bound for the permanently labeled observations. This yields a bound on the regret accumulated over all LDP rounds. Separately, the uncertainty gate limits the number of pilot-exploration rounds through the growth of the pilot design matrix. Combining these two components gives the finite-sample regret bound, after which we establish a matching lower bound in its dependence on the horizon. We begin with the one-period analysis of an LDP round. The confidence event guarantees that the best action in the current discretized candidate set survives every completed layer. Consequently, the stopping layer controls the revenue loss relative to the best discretized action, while the mesh of the residual grid controls the additional loss relative to the continuous oracle price. Lemma 5.1 Fix an LDP round t, and suppose that the confidence bounds (9) hold at every layer visited in period t. For each visited layer s, define Vt,s:=max(j,w)∈t,s(t,p^t(w)).V_t,s:= _(j,w) _t,s Rev ( x_t, p_t(w) ). Then: 1. If the algorithm passes the precision check at a layer s<Ss<S, then Vt,s+1=Vt,s.V_t,s+1=V_t,s. 2. If st≥2s_t≥ 2, then Vt,1−(t,pt)≤8BD 2−st.V_t,1- Rev( x_t,p_t)≤ 8BD\,2^-s_t. Moreover, there exists a finite constant LRev>0L_Rev>0, such that, for every st∈[S]s_t∈[S], (t,pt⋆)−(t,pt)≤LRevT+8BD 2−st. Rev( x_t,p_t )- Rev( x_t,p_t)≤ L_Rev T+8BD\,2^-s_t. (10) Lemma 5.1 reduces the regret over LDP rounds to the weighted layer occupancy ∑s=1S2−s|ΨT+1,s|. _s=1^S2^-s| _T+1,s|. Here ΨT+1,s:=⋃j=1NΨT+1,sj _T+1,s:= _j=1^N _T+1,s^j denotes the set of all LDP rounds assigned to layer s. It therefore remains to control the number of rounds terminating at each layer. The required auxiliary results are established in the appendix. Lemma A.2 bounds the cumulative revenue uncertainty within a layer by applying a sequential elliptical-potential argument within each permanently labeled residual bin and then aggregating across bins; the resulting bound separates statistical uncertainty from the approximation error induced by the local-polynomial remainder and the residual second-order pilot-index error. Lemma A.3 then exploits the fact that every round terminating at a nonterminal layer s<Ss<S has revenue width exceeding BD2−sBD2^-s to convert the cumulative-width bound into an occupancy bound whenever the layer resolution dominates the approximation floor (hβ+η2)O(h^β+η^2). These results provide the ingredients needed to aggregate the layer-dependent losses. These ingredients lead to a natural three-regime decomposition of the LDP regret. For nonterminal layers whose resolution remains above the approximation floor, the occupancy bounds apply, and the resulting contribution is governed by statistical uncertainty. Once the resolution falls to the approximation scale, a separate occupancy bound is no longer needed, because the per-round loss at these finer layers can be charged directly to the approximation error. Finally, each round reaching the terminal layer contributes at most its prescribed resolution 2−S2^-S. Summing the contributions from these three regimes yields the total regret incurred over the LDP rounds. Proposition 5.2 (Regret of the discretized LDP step) On the uniform confidence event in Proposition 4.2, we have ∑t∈[T]∖exp[(t,pt⋆)−(t,pt)]≤ _t∈[T] exp [ Rev( x_t,p_t )- Rev( x_t,p_t) ]≤ 64CωB(DιT+λ)NTιT 4C_ωB (D _T+ λ ) NT _T (11) +16CωBT(hβ+η2)ιT+(8BD+LRev)T. +6C_ωBT(h^β+η^2) _T+ (8BD+L_Rev ) T. Suppose that λ>0λ>0 is fixed independently of T, η2≤cηhβη^2≤ c_ηh^β for some fixed constant cη>0c_η>0 in addition to η≤hη≤ h, N=⌈T12β+1⌉N= T 12β+1 and h=2B/Nh=2B/N, then there exists a finite constant CLDP>0C_LDP>0 such that ∑t∈[T]∖exp[(t,pt⋆)−(t,pt)]≤CLDPιTTβ+12β+1. _t∈[T] exp [ Rev( x_t,p_t )- Rev( x_t,p_t) ]≤ C_LDP\, _TT β+12β+1. (12) It remains to control the pilot-exploration rounds. Such a round is triggered only when the leverage score of the current covariate exceeds the target index accuracy. Each trigger produces a multiplicative increase in the determinant of the pilot design matrix. Since the determinant is also bounded above by the trace of that matrix, only a limited number of pilot-exploration rounds can occur. This argument is pathwise and does not consume any additional failure probability. Lemma 5.3 (Pilot-exploration count and regret) Suppose that Algorithm 1 is implemented with η>0η>0. Then the number of pilot-exploration rounds satisfies, pathwise, |exp| |T exp | ≤minT,dlog(1+TCx2/d)log(1+η2/γT2)≤minT,d(1+γT2η2)log(1+TCx2d). ≤ \T,\, d (1+TC_x^2/d ) (1+η^2/ _T^2 ) \≤ \T,\,d (1+ _T^2η^2 ) (1+ TC_x^2d ) \. (13) Consequently, the regret incurred on pilot-exploration rounds satisfies ∑t∈exp[(t,pt⋆)−(t,pt)]≤BDminT,d(1+γT2η2)log(1+TCx2d). _t exp [ Rev( x_t,p_t )- Rev( x_t,p_t) ]≤ BD \T,\,d (1+ _T^2η^2 ) (1+ TC_x^2d ) \. (14) The regret decomposition is now complete. The pilot-exploration bound in Lemma 5.3 holds pathwise, whereas the LDP bound in Proposition 5.2 holds on the uniform confidence event. Hence, their sum holds on the same event, without an additional union bound. The following theorem first states the resulting finite-sample guarantee and then specializes it to compatible choices of the residual-bin width and pilot accuracy. Theorem 5.4 (Regret upper bound) Suppose Assumptions 3.1, 3.2, and 3.4 hold. Let 0<η≤h0<η≤ h, and γT,ιT _T, _T be defined as in Algorithm 1 and (8), respectively. Then, with probability at least 1−δ1-δ, Reg(T)≤ (T)≤ BDminT,dlog(1+TCx2/d)log(1+η2/γT2)+64CωB(DιT+λ)NTιT BD \T,\, d (1+TC_x^2/d ) (1+η^2/ _T^2 ) \+4C_ωB (D _T+ λ ) NT _T (15) +16CωBT(hβ+η2)ιT+(8BD+LRev)T, +6C_ωBT(h^β+η^2) _T+ (8BD+L_Rev ) T, where CωC_ω and LRevL_Rev are the constants in Lemma A.2 and Lemma 5.1. Moreover, let N=⌈T12β+1⌉N= T 12β+1 and η2=minh2,hβη^2= \h^2,h^β\. Then with probability at least 1−δ1-δ, there exists a finite constant C>0C>0 such that Reg(T)≤C[d(1+γT2)log(1+TCx2d)+(1+λ)ιT]Tβ+12β+1. (T)≤ C [d (1+ _T^2 ) (1+ TC_x^2d )+(1+ λ) _T ]T β+12β+1. (16) The theorem separates the main sources of regret. Pilot exploration pays for certifying the valuation index along the covariate directions encountered by the policy; its contribution is controlled by the uncertainty-triggered determinant argument. On LDP rounds, NT NT is the statistical cost of learning across the N residual bins, whereas ThβTh^β is the local-polynomial approximation cost. The pilot-corrected lifting leaves only the second-order contribution Tη2Tη^2, so choosing η2≤hβη^2≤ h^β prevents pilot-index error from worsening the nonparametric rate. The residual-grid discretization and terminal layer contribute only order T T. Choosing N≍T12β+1N T 12β+1, h≍T−12β+1h T^- 12β+1 and η2≤hβη^2≤ h^β balances the statistical and approximation terms. For fixed d and fixed problem primitives, this yields the regret on the order of ~(Tβ+12β+1) O\! (T β+12β+1 ). Remark 5.5 (Adaptation to an unknown time horizon) The knowledge of T can be removed using the standard doubling trick, as commonly adopted in the dynamic-pricing literature (Javanmard and Nazerzadeh, 2019; Luo et al., 2024; Fan et al., 2024; Wang and Chen, 2025; Han et al., 2026). Specifically, the policy is restarted over epochs of geometrically increasing lengths, with all horizon-dependent parameters, including N, calibrated to the current epoch length. 5.2 Lower Bound We next establish a minimax lower bound that matches the horizon dependence of the regret upper bound in Theorem 5.4, up to logarithmic factors. The construction uses a constant-covariate, binary-demand subclass. Hence, the lower bound isolates the difficulty of learning an unknown smooth demand function and does not rely on estimating the contextual parameter. A hard binary-demand subclass. Consider the admissible demand subclass yt=Dvt≥pt,q(z)=D0≤z≤B.y_t=D1\v_t≥ p_t\, q(z)=D1\0≤ z≤ B\. (17) For every u∈ℐgu _g, this subclass gives g(u)=[q(ϵt−u)]=Dℙ(ϵt≥u).g(u)=E[q( _t-u)]=DP( _t≥ u). Indeed, if u∈ℐgu _g and ϵt≥u _t≥ u, then 0≤ϵt−u≤Bϵ−(−B+Bϵ)=B.0≤ _t-u≤ B_ε-(-B+B_ε)=B. Thus, on the effective residual domain ℐgI_g, the normalized link g/Dg/D is the survival function of the valuation shock. Fix an admissible ∘∈Θ θ ∈ satisfying Assumption 3.1 over X, and fix any ∘∈ x . Because deterministic covariate sequences are admissible, the minimax problem contains the subclass t≡∘,⋆=∘. x_t≡ x , θ_ = θ . For every p∈[0,B]p∈[0,B], p−(∘)⊤∘∈[−(∘)⊤∘,B−(∘)⊤∘]⊆ℐg,p-( x ) θ ∈[-( x ) θ ,B-( x ) θ ] _g, and the corresponding expected revenue reduces to (p)=pg(p−(∘)⊤∘). Rev(p)=p\,g\! (p-( x ) θ ). Theorem 5.6 (Minimax lower bound) There exist finite constants L¯g>0 L_g>0, c>0c>0, and T0<∞T_0<∞ such that, for every Lg≥L¯gL_g≥ L_g and every T≥T0T≥ T_0, infπsup(Lg)π[Reg(T)]≥cTβ+12β+1. _π _P(L_g)E^π\! [Reg(T) ]≥ cT β+12β+1. (18) Here, the infimum is over all nonanticipating, possibly randomized, pricing policies, and the supremum is over all instances in (Lg)P(L_g). The class (Lg)P(L_g) contains all instances satisfying Assumptions 3.1, 3.2, and 3.4 with Hölder constant at most LgL_g, together with all admissible covariate sequences. The expectation is taken over both the demand randomness and randomization of the pricing policy. Corollary 5.7 (Expected-regret upper bound and minimax horizon rate) Fix Lg≥L¯gL_g≥ L_g, the dimension, and the problem primitives, and suppose the confidence constants used by the policy are chosen uniformly over (Lg)P(L_g). For all sufficiently large T, there are finite constants 0<c¯≤C¯<∞0< c≤ C<∞, independent of T, such that c¯Tβ+12β+1≤infπsup(Lg)π[Reg(T)]≤C¯(logT)2Tβ+12β+1. cT β+12β+1≤ _π _P(L_g)E^π[Reg(T)]≤ C( T)^2T β+12β+1. (19) In particular, the upper and lower bounds match in their horizon exponent. Construction overview. The main difficulty is to construct a hard family that simultaneously satisfies the smoothness, monotonicity, bounded-support, and zero-mean requirements imposed on the valuation shock. We first construct a smooth baseline link whose expected revenue is constant over a nondegenerate interior price interval. We then place a smooth local perturbation in one of KTK_T disjoint subintervals of this flat region. Each perturbation creates a hidden revenue improvement, while a smaller adjustment away from the flat region preserves the zero-mean condition. The following lemma provides the required baseline link and the function used for the compensating adjustment. Lemma 5.8 (A flat zero-mean baseline) There exist constants 0<pL<pU<B,0<p_L<p_U<B, a nonnegative infinitely differentiable function χ:ℝ→[0,∞)χ:R→[0,∞), and a nonincreasing function g0:ℝ→[0,D]g_0:R→[0,D] satisfying the following properties: 1. The function g0g_0 is infinitely differentiable, g0(u)=Dg_0(u)=D for u≤−Bϵu≤-B_ε, and g0(u)=0g_0(u)=0 for u≥Bϵu≥ B_ε. 2. The function g0g_0 belongs to ℋ(β)H(β) on [−B,B][-B,B], with a finite Hölder constant. 3. The normalized function g0/Dg_0/D is the survival function of a zero-mean distribution supported on [−Bϵ,Bϵ][-B_ε,B_ε]. In view of the monotonicity and endpoint conditions above, its zero-mean property is equivalently expressed as ∫−BϵBϵg0(u)du=DBϵ. _-B_ε^B_εg_0(u)\,du=DB_ε. 4. The baseline revenue satisfies pg0(p−(∘)⊤∘)≤D((∘)⊤∘−Bϵ2),p∈[0,B],p\,g_0\! (p-( x ) θ )≤ D (( x ) θ - B_ε2 ), p∈[0,B], (20) with equality for every p∈[pL,pU]p∈[p_L,p_U]. 5. The function χ satisfies supp(χ)⊂(−Bϵ,Bϵ)∖[pL−(∘)⊤∘,pU−(∘)⊤∘],∫ℝχ(u)du=1.supp(χ)⊂(-B_ε,B_ε) [p_L-( x ) θ ,p_U-( x ) θ ], _Rχ(u)\,du=1. On neighborhoods of both [pL−(∘)⊤∘,pU−(∘)⊤∘][p_L-( x ) θ ,p_U-( x ) θ ] and supp(χ)supp(χ), the function g0g_0 is bounded away from 0 and D, and g0′g_0 is uniformly negative. Starting from Lemma 5.8, partition the flat revenue interval into KTK_T disjoint price regions. For the kkth region, add a smooth local perturbation Δk _k and subtract the compensating term akχa_kχ, where ak=∫ℝΔk(v)dv.a_k= _R _k(v)\,dv. Thus, the perturbed link is of the form g0(u)+Δk(u)−akχ(u).g_0(u)+ _k(u)-a_kχ(u). Because ∫ℝχ(u)du=1 _Rχ(u)\,du=1, ∫ℝ(Δk(u)−akχ(u))du=0. _R ( _k(u)-a_kχ(u) )du=0. Consequently, the perturbation does not alter the integral condition corresponding to the zero-mean valuation shock. The local perturbation has width (KT−1)O(K_T^-1) and raises the revenue in its associated region by order KT−βK_T^-β. Its integral therefore satisfies ak=(KT−(β+1)).a_k=O\! (K_T^-(β+1) ). Hence, the compensating adjustment is smaller than the local perturbation by a factor of order KT−1K_T^-1. By placing its support away from the flat region and choosing the perturbation magnitude sufficiently small, all perturbed links remain nonincreasing, take values in [0,D][0,D], and belong to a common Hölder ball. Figure 2: Illustration of the lower-bound construction. Panel (a) constructs a smooth, nonincreasing baseline demand function g0g_0 satisfying the zero-mean integral condition. Panel (b) shows the induced flat revenue region and a local perturbation of width (KT−1)O(K_T^-1) and height κKT−βκ K_T^-β. Panel (c) adds the compensating term −akχ-a_kχ, where ak=∫Δk(v)dv=(KT−(β+1))a_k= _k(v)\ dv=O(K_T^-(β+1)), so that the perturbation preserves the zero-mean shock condition. Panel (d) summarizes the information–regret balance: choosing KT≍T1/(2β+1)K_T T^1/(2β+1) keeps the KL divergence bounded and yields the regret lower bound Ω(T(β+1)/(2β+1)) \! (T^(β+1)/(2β+1) ). Information–regret balance. Under the baseline instance, the expected total number of visits to all KTK_T disjoint perturbation regions is at most T; hence some region is visited at most T/KTT/K_T times in expectation. In that region, the perturbation changes the Bernoulli success probability by Θ(KT−β) (K_T^-β), producing a per-observation KL divergence of order KT−2βK_T^-2β. The local KL contribution is therefore (TKTKT−2β)=(TKT−(2β+1))O ( TK_TK_T^-2β )=O(TK_T^-(2β+1)). The compensating adjustment, of magnitude (KT−(β+1))O(K_T^-(β+1)), contributes at most (TKT−2(β+1))O(TK_T^-2(β+1)) to the KL divergence, which is of lower order. Hence the total KL divergence remains bounded when KT≍T1/(2β+1)K_T T^1/(2β+1). A standard testing argument then shows that with probability bounded away from zero, the policy fails to identify the perturbed region for a constant fraction of the horizon. Since any price outside that region incurs a revenue loss of order KT−βK_T^-β, the expected regret is at least of order TKT−β≍Tβ+12β+1TK_T^-β T β+12β+1, proving Theorem 5.6. Therefore, for fixed problem primitives, the regret rate ~(Tβ+12β+1) O\! (T β+12β+1 ) is minimax optimal in its dependence on the horizon. Remark 5.9 (The effect of strong unimodality) The hard family of instances underlying Theorem 5.6 is based on a revenue function that is flat over a nondegenerate price interval. It therefore lies outside any class that satisfies the strong unimodality condition. The strong unimodality condition, however, rules out such flat alternatives and ensures that price errors translate into quadratic revenue losses. For β≥2β≥ 2, Fan et al. (2026) obtain the matching horizon exponent 2β−14β−3. 2β-14β-3. Thus, strong unimodality fundamentally changes the learning difficulty and permits higher-order smoothness to be exploited more effectively. 6 Conclusion and Future Research This paper studies contextual dynamic pricing with an unknown linear valuation component and an unknown nonparametric demand response. The model accommodates bounded discrete or continuous purchase quantities and imposes only Hölder smoothness on the induced demand function. In particular, the revenue function may be multimodal and its maximizer need not be unique. The framework therefore applies beyond the binary purchase model and avoids the strong shape restrictions commonly used to make contextual pricing analytically tractable. To address the interaction between parametric estimation, nonparametric learning, and adaptive pricing, we develop a layered decision-partitioning framework that combines directional pilot learning, pilot-corrected local polynomial regression, and permanent layer–bin assignments. The pilot correction reduces the remaining index error to second order, whereas the permanent data partition preserves predictability and enables concentration under adaptively collected observations. Together with a global elimination procedure, these ingredients yield the regret bound Reg(T)=~(Tβ+12β+1),Reg(T)= O\! (T β+12β+1 ), which matches our lower bound in its dependence on the horizon. Two directions appear particularly promising for future research. First, it would be valuable to develop a policy that adapts simultaneously to the unknown Hölder radius LgL_g and smoothness order β, while preserving predictable data assignment and valid confidence guarantees under adaptive sampling. An accompanying question is whether such simultaneous adaptation necessarily incurs an additional statistical cost. Second, although the present framework accommodates general, possibly multimodal revenue functions, it does not exploit favorable local revenue geometry when such structure is present. Developing a shape-adaptive policy that achieves faster regret under quadratic revenue growth or strong unimodality, while retaining the minimax guarantee over the unrestricted revenue class, would yield a desirable best-of-both-worlds result. References Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári (2011) Improved algorithms for linear stochastic bandits. Advances in neural information processing systems 24. Cited by: §2.1. P. Auer (2002) Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research 3 (Nov), p. 397–422. Cited by: §2.1. G. Ban and N. B. Keskin (2021) Personalized dynamic pricing with machine learning: high-dimensional features and heterogeneous elasticity. Management Science 67 (9), p. 5549–5568. Cited by: §2.1. O. Besbes and A. Zeevi (2009) Dynamic pricing without knowing the demand function: risk bounds and near-optimal algorithms. Operations research 57 (6), p. 1407–1420. Cited by: §2.1, §3. O. Besbes and A. Zeevi (2015) On the (surprising) sufficiency of linear models for dynamic pricing with demand learning. Management Science 61 (4), p. 723–739. Cited by: §2.1. J. Bu, D. Simchi-Levi, and C. Wang (2022) Context-based dynamic pricing with partially linear demand model. Advances in Neural Information Processing Systems 35, p. 23780–23791. Cited by: §2.1. J. Bu, D. Simchi-Levi, and C. Wang (2025) Context-based dynamic pricing with separable demand models. Management Science. External Links: Document Cited by: §2.1, §3. J. Chai, Y. Duan, J. Fan, and K. Wang (2026) Optimal semiparametric dynamic pricing with feature diversity. arXiv preprint arXiv:2605.04207. External Links: Document Cited by: §1, §2.1. E. Chen, X. Chen, L. Gao, and J. Li (2024) Dynamic contextual pricing with doubly non-parametric random utility models. arXiv preprint arXiv:2405.06866. Cited by: §2.1, §2.1. Y. Choi, G. Kim, C. Yunseo, W. Cho, M. C. Paik, and M. Oh (2023) Semi-parametric contextual pricing algorithm using cox proportional hazards model. In International Conference on Machine Learning, p. 5771–5786. Cited by: §2.1. W. Chu, L. Li, L. Reyzin, and R. Schapire (2011) Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, p. 208–214. Cited by: §2.1. A. V. Den Boer (2015) Dynamic pricing and learning: historical origins, current research, and new directions. Surveys in operations research and management science 20 (1), p. 1–18. Cited by: §1. J. Fan, Y. Guo, and M. Yu (2024) Policy optimization using semiparametric models for dynamic pricing. Journal of the American Statistical Association 119 (545), p. 552–564. Cited by: §1, §2.1, §2.1, §3, §3, Remark 5.5. Y. Fan, Y. Han, J. Lv, X. Xu, and Z. Zhou (2026) Harnessing unimodality in semiparametric contextual pricing via oracle price map learning. arXiv preprint arXiv:2605.15411. Cited by: §1, §1, §2.1, Table 1, §3, Remark 3.6, Remark 5.9. X. Gong, W. You, and J. Zhang (2025) Minimax optimality in contextual dynamic pricing with general valuation models. Operations Research 74 (2), p. 879–897. External Links: Document Cited by: §1, 1st item, §2.1, §2.1, §2.1, Table 1, §3, §3. Y. Han, X. Xu, Y. Wen, Y. Han, I. Lobel, and Z. Zhou (2026) Semi-parametric contextual pricing with general smoothness. In The Fourteenth International Conference on Learning Representations, Cited by: §1, §1, §1, §2.1, Table 1, §3, Remark 3.6, §4.2, Remark 5.5. W. Härdle, P. Hall, and H. Ichimura (1993) Optimal smoothing in single-index models. The Annals of Statistics 21 (1), p. 157–178. Cited by: §1. J. L. Horowitz and W. Härdle (1996) Direct semiparametric estimation of single-index models with discrete covariates. Journal of the American Statistical Association 91 (436), p. 1632–1640. Cited by: §1. H. Ichimura (1993) Semiparametric least squares (SLS) and weighted SLS estimation of single-index models. Journal of Econometrics 58 (1–2), p. 71–120. Cited by: §1. A. Javanmard and H. Nazerzadeh (2019) Dynamic pricing in high-dimensions. Journal of Machine Learning Research 20 (9), p. 1–49. Cited by: §1, §2.1, §2.1, Remark 5.5. T. Lattimore and C. Szepesvári (2020) Bandit algorithms. Cambridge University Press. Cited by: §2.1. Y. Luo, W. W. Sun, and Y. Liu (2022) Contextual dynamic pricing with unknown noise: explore-then-ucb strategy and improved regrets. Advances in Neural Information Processing Systems 35, p. 37445–37457. Cited by: §1, §2.1. Y. Luo, W. W. Sun, and Y. Liu (2024) Distribution-free contextual dynamic pricing. Mathematics of Operations Research 49 (1), p. 599–618. Cited by: §1, §2.1, §3, Remark 5.5. S. Saharan, S. Bawa, and N. Kumar (2020) Dynamic pricing techniques for intelligent transportation system in smart cities: a systematic review. Computer Communications 150, p. 603–625. Cited by: §1. M. Tullii, S. Gaucher, N. Merlis, and V. Perchet (2024) Improved algorithms for contextual dynamic pricing. In Advances in Neural Information Processing Systems, Vol. 37, p. 126088–126117. Cited by: §1, §2.1, §2.1, Table 1. Y. Wang, B. Chen, and D. Simchi-Levi (2021) Multimodal dynamic pricing. Management Science 67 (10), p. 6136–6152. Cited by: §2.1, §2.1, §3, §3. Y. Wang and B. Chen (2025) Tight regret bounds in contextual pricing with semi-parametric demand learning. Available at SSRN 5133677. Cited by: §1, §1, §2.1, Table 1, §3, Remark 3.6, §4.2, Remark 5.5. J. Xu and Y. Wang (2022) Towards agnostic feature-based dynamic pricing: linear policies vs linear valuation with unknown noise. In International Conference on Artificial Intelligence and Statistics, p. 9643–9662. Cited by: §2.1. J. Xu and Y. Wang (2026) Optimal contextual pricing under agnostic non-lipschitz demand. arXiv preprint arXiv:2605.05609. External Links: Document Cited by: §2.1. Appendix A Proofs Proof roadmap. The appendix follows the logical dependency of the results. We first justify the induced link and the uniform-price pilot identity. We then establish pilot confidence, the pilot-corrected local approximation, and the uniform layer–bin confidence event. These ingredients feed the one-period gap and layer-counting arguments used in the contextual upper bound. The lower-bound construction is proved next. A.1 Proofs for the Model Proof of Proposition 3.5. Proof. Let ℐg=[−B+Bϵ,B−Bϵ]I_g=[-B+B_ε,B-B_ε]. Since q:ℝ→[0,D]q:R→[0,D], the function g(u)=[q(ϵt−u)]g(u)=E\! [q( _t-u) ] is well-defined and satisfies 0≤g(u)≤D0≤ g(u)≤ D for all u∈ℐgu _g. Let F¯(u):=ℙ(ϵt≥u) F(u):=P( _t≥ u) be the survival function of the noise. Since F∈ℋ(β,LF;[−B,B])F (β,L_F;[-B,B]) with β≥1β≥ 1, F is continuous. Hence ϵt _t has no atoms. By Assumption 3.1, the support of ϵt _t is contained in [−Bϵ,Bϵ][-B_ε,B_ε]. Therefore F¯ F is constant on (−∞,−Bϵ](-∞,-B_ε] and on [Bϵ,∞)[B_ε,∞). Since Bϵ<B_ε<B, the function 1−F1-F is already constant on [−B,−Bϵ][-B,-B_ε] and on [Bϵ,B][B_ε,B]. Thus, when viewed on the interval [−B+Bϵ,2B−Bϵ][-B+B_ε,2B-B_ε], the survival function F¯ F belongs to ℋ(β,LF;[−B+Bϵ,2B−Bϵ])H(β,L_F;[-B+B_ε,2B-B_ε]). Because q has bounded variation on [0,B][0,B], it has at most countably many discontinuities. Let q+q^+ be a right-continuous representative of q on [0,B][0,B] with TV[0,B](q+)≤VqTV_[0,B](q^+)≤ V_q, extend it by zero outside [0,B][0,B], and continue to denote the resulting function by q+q^+. Since ϵt _t has no atoms, for each fixed u∈ℐgu _g, [q(ϵt−u)]=[q+(ϵt−u)].E\! [q( _t-u) ]=E\! [q^+( _t-u) ]. Hence g can be represented using q+q^+. By the Lebesgue–Stieltjes representation for bounded-variation functions, there exists a finite signed measure μq _q on (0,B](0,B] such that q+(w)=q+(0)+μq((0,w]),w∈[0,B],q^+(w)=q^+(0)+ _q((0,w]), w∈[0,B], and moreover, |μq|((0,B])≤Vq,|q+(0)|≤D.| _q|((0,B])≤ V_q, |q^+(0)|≤ D. For u∈ℐgu _g, Assumption 3.1 implies that ϵt−u≤B _t-u≤ B almost surely whenever ϵt−u≥0 _t-u≥ 0. Therefore, q+(ϵt−u)=q+(0)ϵt≥u+∫(0,B]ϵt≥u+aμq(da).q^+( _t-u)=q^+(0)1\ _t≥ u\+ _(0,B]1\ _t≥ u+a\\, _q(da). Taking expectations and applying Fubini’s theorem for finite signed measures gives g(u)=q+(0)F¯(u)+∫(0,B]F¯(u+a)μq(da),∀u∈ℐg.g(u)=q^+(0) F(u)+ _(0,B] F(u+a)\, _q(da), ∀ u _g. Let m:=ϖ(β)m:= (β). Since μq _q is finite and F¯∈ℋ(β,LF;[−B+Bϵ,2B−Bϵ]) F (β,L_F;[-B+B_ε,2B-B_ε]), differentiating under the finite signed measure yields g(m)(u)=q+(0)F¯(m)(u)+∫(0,B]F¯(m)(u+a)μq(da).g^(m)(u)=q^+(0) F^(m)(u)+ _(0,B] F^(m)(u+a)\, _q(da). Thus, for any u,u′∈ℐgu,u _g, |g(m)(u)−g(m)(u′)| |g^(m)(u)-g^(m)(u )| ≤|q+(0)||F¯(m)(u)−F¯(m)(u′)| ≤|q^+(0)|\,| F^(m)(u)- F^(m)(u )| +∫(0,B]|F¯(m)(u+a)−F¯(m)(u′+a)||μq|(da) + _(0,B]| F^(m)(u+a)- F^(m)(u +a)|\,| _q|(da) ≤(|q+(0)|+|μq|((0,B]))LF|u−u′|β−m ≤(|q^+(0)|+| _q|((0,B]))\,L_F|u-u |^β-m ≤(D+Vq)LF|u−u′|β−m. ≤(D+V_q)L_F|u-u |^β-m. Therefore g∈ℋ(β,Lg;ℐg)g (β,L_g;I_g) with Lg≤(D+Vq)LFL_g≤(D+V_q)L_F. The proof is complete. □ A.2 Proofs for the Contextual Policy Proof of Lemma 4.1. Proof. On an exploratory round, pi∼Unif[0,B]p_i [0,B] is drawn independently of ϵi _i conditional on ℱi−1∨σ(i)F_i-1 σ( x_i). Since yi>0=vi≥pi1\y_i>0\=1\v_i≥ p_i\ and vi∈[0,B]v_i∈[0,B], we have [Byi>0∣ℱi−1,i,i∈exp]=[vi∣ℱi−1,i]=i⊤⋆.E\! [B1\y_i>0\ _i-1, x_i,\i exp\ ]=E[v_i _i-1, x_i]= x_i θ_ . Thus, Byi>0B1\y_i>0\ is an unbiased measurement of i⊤⋆ x_i θ_ on pilot rounds. The observation error is bounded by B in absolute value, and i∈expi1\i exp\ x_i is determined before yiy_i is revealed. By the standard self-normalized concentration inequality for adaptive linear regression, with probability at least 1−δ/21-δ/2, simultaneously for all t≤Tt≤ T, ‖∑i<t,i∈expi(Byi>0−i⊤⋆)‖Mt−1≤Blogdet(Mt)+2log4δ. \| _i<t,i exp x_i (B1\y_i>0\- x_i θ_ ) \|_M_t^-1≤ B (M_t)+2 4δ. The update rules give Mt=Id+∑i<t,i∈expii⊤,t=∑i<t,i∈expByi>0i.M_t=I_d+ _i<t,i exp x_i x_i , b_t= _i<t,i expB1\y_i>0\ x_i. Since ‖i‖2≤Cx\| x_i\|_2≤ C_x, standard elliptical-potential arguments yield logdet(Mt)≤dlog(1+TCx2d). (M_t)≤ d (1+ TC_x^2d ). Since ^t=Mt−1t θ_t=M_t^-1 b_t, we have ^t−⋆ θ_t- θ_ =Mt−1t−Mt−1Mt⋆=Mt−1(t−Mt⋆). =M_t^-1 b_t-M_t^-1M_t θ_ =M_t^-1 ( b_t-M_t θ_ ). (21) Moreover, Mt⋆ M_t θ_ =(Id+∑i<t,i∈expii⊤)⋆=⋆+∑i<t,i∈expi(i⊤⋆). = (I_d+ _ subarrayci<t,i exp subarray x_i x_i ) θ_ = θ_ + _ subarrayci<t,i exp subarray x_i ( x_i θ_ ). (22) Substituting (22) into (21) yields ^t−⋆ θ_t- θ_ =Mt−1[∑i<t,i∈expByi>0i−⋆−∑i<t,i∈expi(i⊤⋆)] =M_t^-1 [ _i<t,i expB1\y_i>0\ x_i- θ_ - _i<t,i exp x_i ( x_i θ_ ) ] =Mt−1[∑i<t,i∈expi(Byi>0−i⊤⋆)−⋆]. =M_t^-1 [ _i<t,i exp x_i (B1\y_i>0\- x_i θ_ )- θ_ ]. For any ∈ℝd x ^d, the Cauchy–Schwarz inequality in the Mt−1M_t^-1-norm gives |⊤(^t−⋆)| | x ( θ_t- θ_ ) | ≤‖Mt−1[‖∑i<t,i∈expi(Byi>0−i⊤⋆)‖Mt−1+‖⋆‖Mt−1] ≤\| x\|_M_t^-1 [ \| _i<t,i exp x_i (B1\y_i>0\- x_i θ_ ) \|_M_t^-1+\| θ_ \|_M_t^-1 ] ≤‖Mt−1[Bdlog(1+TCx2d)+2log4δ+Cθ], ≤\| x\|_M_t^-1 [B d (1+ TC_x^2d )+2 4δ+C_θ ], where the second inequality uses ‖⋆‖Mt−1≤‖⋆‖2≤Cθ,\| θ_ \|_M_t^-1≤\| θ_ \|_2≤ C_θ, and Mt−1⪯IdM_t^-1 I_d. The bracketed expression is precisely γT _T, completing the proof. □ The proof of Proposition 4.2 uses the following martingale property. Proposition A.1 (Martingale property) For notational convenience, set si=ji=wi=0s_i=j_i=w_i=0 whenever i∈expi exp. Use the chronological fields defined in Section 3 and write ℱi−:=i,ℱi=ℱi−∨σ(yi),i∈[T].F_i^-:=G_i, _i=F_i^- σ(y_i), i∈[T]. In particular, the exploration decision, price, stopping layer, bin, and residual label are all ℱi−F_i^--measurable. For each i∈[T]i∈[T], define εi:=yi−g(pi−i⊤⋆). _i:=y_i-g\! (p_i- x_i θ_ ). Then [εi∣ℱi−]=0,|εi|≤Da.s.E\! [ _i _i^- ]=0, | _i|≤ D .s. For fixed s∈[S]s∈[S] and j∈[N]j∈[N], define the zero-padded feature vector ψ¯i,j,s:=ψi,j(wi),if i∉exp,si=s,ji=j,,otherwise. ψ_i,j,s:= cases _i,j(w_i),&if i exp,\ s_i=s,\ j_i=j,\\[2.84526pt] 0,&otherwise. cases Then ψ¯i,j,s ψ_i,j,s is ℱi−F_i^--measurable, ‖ψ¯i,j,s‖2≤Cψ\| ψ_i,j,s\|_2≤ C_ψ for some Cψ>0,a.s.C_ψ>0,a.s., and [ψ¯i,j,sεi∣ℱi−]=.E\! [ ψ_i,j,s _i _i^- ]= 0. Consequently, 0s,j:=,ts,j:=∑i=1tψ¯i,j,sεi,t∈[T], M_0^s,j:= 0, M_t^s,j:= _i=1^t ψ_i,j,s _i, t∈[T], defines a vector-valued martingale with respect to ℱtt=0T\F_t\_t=0^T, whose increments satisfy ‖ts,j−t−1s,j‖2≤CψDa.s. \| M_t^s,j- M_t-1^s,j \|_2≤ C_ψD .s. In particular, for every t∈[T]t∈[T], t−1s,j=∑i∈Ψt,sjψi,j(wi)εi. M_t-1^s,j= _i∈ _t,s^j _i,j(w_i) _i. Proof. By policy nonanticipativity and the sequential exogeneity of the current valuation shock, ℙ(ϵi≤u∣ℱi−)=F(u).P\! ( _i≤ u _i^- )=F(u). Moreover, the surplus-demand model gives [yi∣ℱi−∨σ(vi)]=q(vi−pi).E\! [y_i _i^- σ(v_i) ]=q(v_i-p_i). Therefore, by the tower property, [yi∣ℱi−]=[q(vi−pi)∣ℱi−]=∫q(i⊤⋆+ϵ−pi)dF(ϵ)=g(pi−i⊤⋆).E[y_i _i^-]=E\! [q(v_i-p_i) _i^- ]\\ = q\! ( x_i θ_ +ε-p_i )\,dF(ε)\\ =g\! (p_i- x_i θ_ ). It follows that [εi∣ℱi−]=0.E\! [ _i _i^- ]=0. Since yi∈[0,D]y_i∈[0,D] almost surely and g∈[0,D]g∈[0,D], we have εi∈[−g(pi−i⊤⋆),D−g(pi−i⊤⋆)], _i∈ [-g\! (p_i- x_i θ_ ),D-g\! (p_i- x_i θ_ ) ], and hence |εi|≤D.| _i|≤ D. Now fix s∈[S]s∈[S] and j∈[N]j∈[N]. The exploration decision, permanent layer–bin labels, residual action, and posted price are all determined before yiy_i is observed. Hence ψ¯i,j,s ψ_i,j,s is ℱi−F_i^--measurable. Furthermore, whenever this feature is nonzero, wi∈Ij,pi−wi=p^i(wi)−wi∈[0,B],‖i‖2≤Cx.w_i∈ I_j, p_i-w_i= p_i(w_i)-w_i∈[0,B], \| x_i\|_2≤ C_x. Since the local-polynomial degree is fixed, the definition of ψi,j _i,j implies that there exists a deterministic constant Cψ<∞C_ψ<∞ such that ‖ψ¯i,j,s‖2≤Cψ.\| ψ_i,j,s\|_2≤ C_ψ. Consequently, [ψ¯i,j,sεi∣ℱi−]=ψ¯i,j,s[εi∣ℱi−]=,E\! [ ψ_i,j,s _i _i^- ]= ψ_i,j,sE\! [ _i _i^- ]\\ = 0, which proves the martingale-difference property. To make the associated martingale explicit, define, within this proof, 0s,j:=,ts,j:=∑i=1tψ¯i,j,sεi,t∈[T]. M_0^s,j:= 0, M_t^s,j:= _i=1^t ψ_i,j,s _i, t∈[T]. The process ts,jt=0T\ M_t^s,j\_t=0^T is ℱtt=0T\F_t\_t=0^T-adapted and integrable. Since ℱt−1⊆ℱt−F_t-1 _t^-, the tower property yields [ts,j∣ℱt−1]=t−1s,j+[[ψ¯t,j,sεt∣ℱt−]|ℱt−1]=t−1s,j.E\! [ M_t^s,j _t-1 ]= M_t-1^s,j+E\! [E\! [ ψ_t,j,s _t _t^- ]\, |\,F_t-1 ]\\ = M_t-1^s,j. Thus, ts,j,ℱtt=0T\ M_t^s,j,F_t\_t=0^T is a vector-valued martingale, interpreted componentwise, with increments satisfying ‖ts,j−t−1s,j‖2≤CψDa.s. \| M_t^s,j- M_t-1^s,j \|_2≤ C_ψD .s. Finally, by the permanent-label definition, Ψt,sj=i<t:i∉exp,si=s,ji=j, _t,s^j= \i<t:i exp,\ s_i=s,\ j_i=j \, and therefore t−1s,j=∑i∈Ψt,sjψi,j(wi)εi. M_t-1^s,j= _i∈ _t,s^j _i,j(w_i) _i. This is precisely the stochastic score appearing in the layer–bin ridge estimator. □ Proof of Proposition 4.2. Proof. We proceed in five steps. Step 1: pilot-index control. Let ℰpil:=|⊤(^t−⋆)|≤γT‖Mt−1 for every t≤T and every ∈ℝd.E_ pil:= \| x ( θ_t- θ_ )|≤ _T\| x\|_M_t^-1 for every t≤ T and every x ^d \. Lemma 4.1 gives ℙ(ℰpil)≥1−δ/2P(E_ pil)≥ 1-δ/2. If i is a main-policy round, then the exploration test did not trigger, and therefore γT‖i‖Mi−1≤η _T\| x_i\|_M_i^-1≤η. On ℰpilE_ pil, we have |i⊤(^i−⋆)|≤η| x_i ( θ_i- θ_ )|≤η. Because Euclidean projection onto [0,B][0,B] is nonexpansive and i⊤⋆∈[0,B] x_i θ_ ∈[0,B], |Π[0,B](i⊤^i)−i⊤⋆|≤η. | _[0,B]( x_i θ_i)- x_i θ_ |≤η. (23) The same inequality holds for the current LDP round t. Step 2: local Taylor expansion and joint linearization. Since 0≤g≤D0≤ g≤ D on ℐgI_g, g∈ℋ(β,Lg;ℐg)g (β,L_g;I_g), and ℐgI_g is a fixed nondegenerate compact interval, a standard one-dimensional interpolation inequality implies max0≤k≤ϖ(β)supu∈ℐg|g(k)(u)|≤Cg, _0≤ k≤ (β) _u _g|g^(k)(u)|≤ C_g, where CgC_g is the fixed class-level envelope specified after Assumption 3.4. To make the Taylor coefficients at all bin endpoints well defined, extend g from ℐg=[−B+Bϵ,B−Bϵ]I_g=[-B+B_ε,B-B_ε] to [−B,B][-B,B] by its endpoint Taylor polynomials of order m:=ϖ(β)m:= (β), while continuing to use the same notation g. The extension agrees with g and its derivatives up to order m at both endpoints of ℐgI_g, and is therefore m-times differentiable on [−B,B][-B,B]. Moreover, g(m)g^(m) is constant on each added interval and equals the corresponding endpoint value. Hence, Assumption 3.4 implies |g(m)(u)−g(m)(u′)|≤Lg|u−u′|β−m,u,u′∈[−B,B]. |g^(m)(u)-g^(m)(u ) |≤ L_g|u-u |^β-m, u,u ∈[-B,B]. Indeed, when u and u′u lie in different regions, the original Hölder bound is applied to the corresponding endpoint or endpoints, whose separation is no greater than |u−u′||u-u |. Therefore, the extension belongs to ℋ(β,Lg;[−B,B])H(β,L_g;[-B,B]). After increasing the fixed value of CgC_g, if necessary, the extension therefore satisfies max0≤k≤msupu∈[−B,B]|g(k)(u)|≤Cg. _0≤ k≤ m _u∈[-B,B]|g^(k)(u)|≤ C_g. (24) This extension is used only in the analysis and leaves g unchanged on its original domain ℐgI_g; hence it does not alter the demand model or the algorithm. For the proof, use the convention g(0)=g^(0)=g and define the coefficient vector corresponding to the joint feature. Recall j=g(aj−1). z_j=g(a_j-1). if ϖ(β)=0 (β)=0, and j=(g(aj−1)g′(aj−1)⋮g(ϖ(β))(aj−1)/ϖ(β)!g′(aj−1)⋆⋮[g(ϖ(β))(aj−1)/ϖ(β)!]⋆) z_j= pmatrixg(a_j-1)\\ g (a_j-1)\\ \\ g^( (β))(a_j-1)/ (β)!\\[2.84526pt] g (a_j-1) θ_ \\ \\ [g^( (β))(a_j-1)/ (β)! ] θ_ pmatrix if ϖ(β)≥1 (β)≥ 1. Define Cz:=Cg[∑k=0m1(k!)2+Cθ2∑k=1m1(k!)2]1/2.C_z:=C_g [ _k=0^m 1(k!)^2+C_θ^2 _k=1^m 1(k!)^2 ]^1/2. (25) Equation (24) and ‖⋆‖2≤Cθ\| θ_ \|_2≤ C_θ imply that, uniformly over j∈[N]j∈[N], ‖j‖22 \| z_j\|_2^2 =∑k=0m|g(k)(aj−1)k!|2+‖⋆‖22∑k=1m|g(k)(aj−1)k!|2≤Cg2[∑k=0m1(k!)2+Cθ2∑k=1m1(k!)2]=Cz2. = _k=0^m | g^(k)(a_j-1)k! |^2+\| θ_ \|_2^2 _k=1^m | g^(k)(a_j-1)k! |^2≤ C_g^2 [ _k=0^m 1(k!)^2+C_θ^2 _k=1^m 1(k!)^2 ]=C_z^2. Since the right-hand side does not depend on j, we obtain supj∈[N]‖j‖2≤Cz. _j∈[N]\| z_j\|_2≤ C_z. (26) Define Cl:=max2βLgϖ(β)!,Cg∑k=2ϖ(β)(2k−k−1)(2B)k−2k!.C_l:= \ 2^βL_g (β)!,\;C_g _k=2 (β) (2^k-k-1)(2B)^k-2k! \. (27) We next establish the joint linearized representation on the event ℰpilE_ pil. Fix i∈Ψt,sji∈ _t,s^j. Since the bin label assigned to period i is permanent, wi∈Ijw_i∈ I_j, and hence 0≤wi−aj−1≤h0≤ w_i-a_j-1≤ h. Moreover, since pi=p^i(wi)=Π[0,B](i⊤^i)+wip_i= p_i(w_i)= _[0,B] ( x_i θ_i )+w_i, (23) gives that |(pi−wi)−i⊤⋆|≤η. |(p_i-w_i)- x_i θ_ |≤η. (28) The true residual can therefore be written exactly as pi−i⊤⋆= p_i- x_i θ_ = aj−1+(wi−aj−1)+((pi−wi)−i⊤⋆). a_j-1+(w_i-a_j-1)+ ((p_i-w_i)- x_i θ_ ). (29) Moreover, since pi∈[0,B]p_i∈[0,B] and i⊤⋆∈[Bϵ,B−Bϵ] x_i θ_ ∈[B_ε,B-B_ε], pi−i⊤⋆∈[−B+Bϵ,B−Bϵ]=ℐg.p_i- x_i θ_ ∈[-B+B_ε,B-B_ε]=I_g. Hence g(pi−i⊤⋆)g(p_i- x_i θ_ ) is evaluated on the original domain of the induced demand link; the extension in Step 2 is used only to define the Taylor coefficients at aj−1a_j-1. Thus, relative to the expansion point aj−1a_j-1, the true residual contains two deviations: the within-bin deviation wi−aj−1w_i-a_j-1, whose absolute value is at most h, and the pilot-index error (pi−wi)−i⊤⋆(p_i-w_i)- x_i θ_ , whose absolute value is at most η. We next identify the function value represented by the joint feature. By the definitions of ψi,j(wi) _i,j(w_i), ϕj _j, ϕj′ _j , jX_j, and j z_j, we have ψi,j(wi)⊤j= _i,j(w_i) z_j= ∑k=0ϖ(β)g(k)(aj−1)k!(wi−aj−1)k+[(pi−wi)−i⊤⋆]∑k=1ϖ(β)g(k)(aj−1)(k−1)!(wi−aj−1)k−1. _k=0 (β) g^(k)(a_j-1)k!(w_i-a_j-1)^k+ [(p_i-w_i)- x_i θ_ ] _k=1 (β) g^(k)(a_j-1)(k-1)!(w_i-a_j-1)^k-1. (30) The first sum in (30) is the local Taylor polynomial centered at aj−1a_j-1 and evaluated at wiw_i. The second sum is the derivative of this polynomial at wiw_i, multiplied by the pilot-index error in (28). Hence, ψi,j(wi)⊤j _i,j(w_i) z_j represents the local Taylor polynomial together with the complete first-order correction for the pilot-index error. When ϖ(β)=0 (β)=0, the derivative term is absent. If β=1β=1, then ϖ(β)=0 (β)=0 and ψi,j(wi)⊤j=g(aj−1). _i,j(w_i) z_j=g(a_j-1). Since g is Lipschitz continuous, (29) gives |g(pi−i⊤⋆)−ψi,j(wi)⊤j| |g(p_i- x_i θ_ )- _i,j(w_i) z_j | =|g(pi−i⊤⋆)−g(aj−1)| = |g(p_i- x_i θ_ )-g(a_j-1) | ≤Lg(|wi−aj−1|+|(pi−wi)−i⊤⋆|) ≤ L_g (|w_i-a_j-1|+ |(p_i-w_i)- x_i θ_ | ) ≤Lg(h+η)≤2Lgh≤Cl(hβ+η2), ≤ L_g(h+η)≤ 2L_gh≤ C_l(h^β+η^2), because hβ=h^β=h, η≤hη≤ h, and Cl≥2LgC_l≥ 2L_g. Suppose now that β>1β>1. Applying the Hölder Taylor expansion at aj−1a_j-1 and using (29), we obtain g(pi−i⊤⋆)= g(p_i- x_i θ_ )= ∑k=0ϖ(β)g(k)(aj−1)k![(wi−aj−1)+(pi−wi)−i⊤⋆]k+Ri, _k=0 (β) g^(k)(a_j-1)k! [(w_i-a_j-1)+(p_i-w_i)- x_i θ_ ]^k+R_i, (31) where |Ri| |R_i| ≤Lgϖ(β)!(|wi−aj−1|+|(pi−wi)−i⊤⋆|)β≤Lgϖ(β)!(h+η)β≤2βLgϖ(β)!hβ≤Clhβ. ≤ L_g (β)! (|w_i-a_j-1|+ |(p_i-w_i)- x_i θ_ | )^β≤ L_g (β)!(h+η)^β≤ 2^βL_g (β)!h^β≤ C_lh^β. For each k≥1k≥ 1, applying the binomial formula to the kkth power in (31) gives [(wi−aj−1)+(pi−wi)−i⊤⋆]k=∑r=0k(kr)(wi−aj−1)k−r((pi−wi)−i⊤⋆)r. [(w_i-a_j-1)+(p_i-w_i)- x_i θ_ ]^k= _r=0^k kr(w_i-a_j-1)^k-r ((p_i-w_i)- x_i θ_ )^r. The term with r=0r=0 does not contain the pilot-index error, while the term with r=1r=1 is linear in the pilot-index error. After multiplying by the Taylor coefficients and summing over k, these terms are exactly the two terms in (30). Therefore, ψi,j(wi)⊤j _i,j(w_i) z_j contains all terms in the Taylor expansion that involve at most one factor of (pi−wi)−i⊤⋆.(p_i-w_i)- x_i θ_ . The remaining terms correspond to r≥2r≥ 2. For every 2≤r≤k2≤ r≤ k, using |wi−aj−1|≤h,|(pi−wi)−i⊤⋆|≤η,η≤h,|w_i-a_j-1|≤ h, |(p_i-w_i)- x_i θ_ |≤η, η≤ h, we obtain |wi−aj−1|k−r|(pi−wi)−i⊤⋆|r |w_i-a_j-1|^k-r |(p_i-w_i)- x_i θ_ |^r ≤hk−rηr≤hk−rη2hr−2 ≤ h^k-rη^r≤ h^k-rη^2h^r-2 =hk−2η2≤(2B)k−2η2, =h^k-2η^2≤(2B)^k-2η^2, where the second inequality follows because η≤hη≤ h and r≥2r≥ 2 and the last inequality follows because h≤2Bh≤ 2B. Moreover, (24) uniformly bounds the Taylor coefficients by CgC_g, and the numbers of possible values of k and r depend only on β. Hence, ∑k=2ϖ(β)|g(k)(aj−1)|k!∑r=2k(kr)|wi−aj−1|k−r|(pi−wi)−i⊤⋆|r _k=2 (β) |g^(k)(a_j-1)|k! _r=2^k kr|w_i-a_j-1|^k-r |(p_i-w_i)- x_i θ_ |^r ≤Cgη2∑k=2ϖ(β)(2k−k−1)(2B)k−2k! ≤ C_gη^2 _k=2 (β) (2^k-k-1)(2B)^k-2k! ≤Clη2, ≤ C_lη^2, where we used ∑r=2k(kr)=2k−k−1. _r=2^k kr=2^k-k-1. Combining this bound with the Taylor remainder |Ri|≤Clhβ|R_i|≤ C_lh^β, we have g(pi−i⊤⋆)=ψi,j(wi)⊤j+Ri,j(wi),|Ri,j(wi)|≤Cl(hβ+η2).g(p_i- x_i θ_ )= _i,j(w_i) z_j+R_i,j(w_i), |R_i,j(w_i)|≤ C_l(h^β+η^2). (32) When 1<β≤21<β≤ 2, we have ϖ(β)=1 (β)=1, so the sums over k≥2k≥ 2 are empty. In this case, no quadratic or higher-order term in the pilot-index error is omitted, and the additional η2η^2 term is unnecessary but remains a valid uniform upper bound. The same argument applies to every current candidate action w∈t,jw _t,j. Indeed, p^t(w)∈[0,B] p_t(w)∈[0,B], so Assumption 3.1 implies p^t(w)−t⊤⋆∈ℐg. p_t(w)- x_t θ_ _g. Moreover, w∈Ijw∈ I_j and Step 1 give 0≤w−aj−1≤h,|p^t(w)−w−t⊤⋆|≤η.0≤ w-a_j-1≤ h, | p_t(w)-w- x_t θ_ |≤η. Therefore, g(p^t(w)−t⊤⋆)=ψt,j(w)⊤j+Rt,j(w),|Rt,j(w)|≤Cl(hβ+η2).g\! ( p_t(w)- x_t θ_ )= _t,j(w) z_j+R_t,j(w), |R_t,j(w)|≤ C_l(h^β+η^2). (33) Step 3: ridge-error decomposition. For every i∈Ψt,sji∈ _t,s^j, Proposition A.1 and (32) give yi=ψi,j(wi)⊤j+Ri,j(wi)+εi.y_i= _i,j(w_i) z_j+R_i,j(w_i)+ _i. Thus each observed demand consists of the linear approximation ψi,j(wi)⊤j _i,j(w_i) z_j, the approximation error Ri,j(wi)R_i,j(w_i), and the demand noise εi _i. By the definition of ^t,sj z_t,s^j, (Λt,sj+λI)^t,sj=∑i∈Ψt,sjyiψi,j(wi).( _t,s^j+λ I) z_t,s^j= _i∈ _t,s^jy_i _i,j(w_i). Substituting the preceding expression for yiy_i yields (Λt,sj+λI)^t,sj ( _t,s^j+λ I) z_t,s^j =∑i∈Ψt,sjψi,j(wi)(ψi,j(wi)⊤j+Ri,j(wi)+εi) = _i∈ _t,s^j _i,j(w_i) ( _i,j(w_i) z_j+R_i,j(w_i)+ _i ) =∑i∈Ψt,sjψi,j(wi)ψi,j(wi)⊤j+∑i∈Ψt,sjψi,j(wi)Ri,j(wi)+∑i∈Ψt,sjψi,j(wi)εi. = _i∈ _t,s^j _i,j(w_i) _i,j(w_i) z_j+ _i∈ _t,s^j _i,j(w_i)R_i,j(w_i)+ _i∈ _t,s^j _i,j(w_i) _i. By the definition Λt,sj=∑i∈Ψt,sjψi,j(wi)ψi,j(wi)⊤, _t,s^j= _i∈ _t,s^j _i,j(w_i) _i,j(w_i) , the first term on the right-hand side equals Λt,sjj _t,s^j z_j. Hence (Λt,sj+λI)^t,sj=Λt,sjj+∑i∈Ψt,sjψi,j(wi)Ri,j(wi)+∑i∈Ψt,sjψi,j(wi)εi.( _t,s^j+λ I) z_t,s^j= _t,s^j z_j+ _i∈ _t,s^j _i,j(w_i)R_i,j(w_i)+ _i∈ _t,s^j _i,j(w_i) _i. Subtracting (Λt,sj+λI)j( _t,s^j+λ I) z_j from both sides gives (Λt,sj+λI)(^t,sj−j) ( _t,s^j+λ I) ( z_t,s^j- z_j ) =∑i∈Ψt,sjψi,j(wi)εi+∑i∈Ψt,sjψi,j(wi)Ri,j(wi)−λj. = _i∈ _t,s^j _i,j(w_i) _i+ _i∈ _t,s^j _i,j(w_i)R_i,j(w_i)-λ z_j. The term −λj-λ z_j appears because Λt,sjj−(Λt,sj+λI)j=−λj. _t,s^j z_j-( _t,s^j+λ I) z_j=-λ z_j. Since λ>0λ>0, the matrix Λt,sj+λI _t,s^j+λ I is positive definite and therefore invertible. Multiplying both sides by (Λt,sj+λI)−1( _t,s^j+λ I)^-1 gives ^t,sj−j=(Λt,sj+λI)−1( z_t,s^j- z_j=( _t,s^j+λ I)^-1 ( ∑i∈Ψt,sjψi,j(wi)εi+∑i∈Ψt,sjψi,j(wi)Ri,j(wi)−λj). _i∈ _t,s^j _i,j(w_i) _i+ _i∈ _t,s^j _i,j(w_i)R_i,j(w_i)-λ z_j ). (34) The three terms on the right-hand side arise, respectively, from the random demand noise, the approximation error in (32), and the ridge regularization. Step 4: noise, approximation, and regularization bounds. Fix s∈[S]s∈[S] and j∈[N]j∈[N]. Proposition A.1 shows that ψ¯i,j,s ψ_i,j,s is determined before yiy_i is observed and that [ψ¯i,j,sεi∣ℱi−]=.E\! [ ψ_i,j,s _i _i^- ]= 0. Moreover, conditional on ℱi−F_i^-, εi _i has mean zero and lies in an interval of length D. Hence, by the conditional Hoeffding lemma, for every γ∈ℝγ , [exp(γεi)∣ℱi−]≤exp(γ2D28).E\! [ (γ _i) _i^- ]≤ \! ( γ^2D^28 ). Thus, εi _i is conditionally D/2D/2-sub-Gaussian, and the standard time-uniform self-normalized concentration inequality applies to the features ψ¯i,j,s ψ_i,j,s. By the definition of ψ¯i,j,s ψ_i,j,s, for every t≤T+1t≤ T+1, ∑i<tψ¯i,j,sεi=∑i∈Ψt,sjψi,j(wi)εi, _i<t ψ_i,j,s _i= _i∈ _t,s^j _i,j(w_i) _i, and ∑i<tψ¯i,j,s(ψ¯i,j,s)⊤=∑i∈Ψt,sjψi,j(wi)ψi,j(wi)⊤=Λt,sj. _i<t ψ_i,j,s ( ψ_i,j,s ) = _i∈ _t,s^j _i,j(w_i) _i,j(w_i) = _t,s^j. Hence, for pair (s,j)(s,j), with probability at least 1−δ/(2SN)1-δ/(2SN), for every t≤T+1t≤ T+1, ‖∑i∈Ψt,sjψi,j(wi)εi‖(Λt,sj+λI)−1≤Dlogdet(Λt,sj+λI)det(λI)+2log(2SNδ). \| _i∈ _t,s^j _i,j(w_i) _i \|_( _t,s^j+λ I)^-1≤ D ( _t,s^j+λ I) (λ I)+2 ( 2SNδ ). The matrix Λt,sj _t,s^j has dimension 1+ϖ(β)(d+1)1+ (β)(d+1). Define Cψ2:= C_ψ^2= 1+∑k=1ϖ(β)[(2B)k+Bk(2B)k−1]2+Cx2∑k=1ϖ(β)k2(2B)2(k−1). 1+ _k=1 (β) [(2B)^k+Bk(2B)^k-1 ]^2+C_x^2 _k=1 (β)k^2(2B)^2(k-1). (35) Since 0≤wi−aj−1≤h≤2B0≤ w_i-a_j-1≤ h≤ 2B, 0≤pi−wi≤B0≤ p_i-w_i≤ B, and ‖i‖2≤Cx\| x_i\|_2≤ C_x, the definition of the joint feature gives ‖ψi,j(wi)‖2≤Cψ\| _i,j(w_i)\|_2≤ C_ψ. The product of positive numbers is no larger than the corresponding power of their average, and hence logdet(Λt,sj+λI)det(λI) ( _t,s^j+λ I) (λ I) ≤[1+ϖ(β)(d+1)]log(1+tr(Λt,sj)λ[1+ϖ(β)(d+1)]) ≤ [1+ (β)(d+1) ] (1+ tr( _t,s^j)λ[1+ (β)(d+1)] ) ≤Cψ2[1+ϖ(β)(d+1)]log(1+Tλ)≤Cψ2ιT, ≤ C_ψ^2 [1+ (β)(d+1) ] (1+ Tλ )≤ C_ψ^2 _T, where the second inequality follows because tr(Λt,sj)=∑i∈Ψt,sj‖ψi,j(wi)‖22≤Cψ2|Ψt,sj|≤Cψ2T.tr( _t,s^j)= _i∈ _t,s^j\| _i,j(w_i)\|_2^2≤ C_ψ^2| _t,s^j|≤ C_ψ^2T. It follows that, for this fixed pair (s,j)(s,j), with probability at least 1−δ/(2SN)1-δ/(2SN), ‖∑i∈Ψt,sjψi,j(wi)εi‖(Λt,sj+λI)−1≤CψDιT \| _i∈ _t,s^j _i,j(w_i) _i \|_( _t,s^j+λ I)^-1≤ C_ψD _T simultaneously for every t≤T+1t≤ T+1. There are SNSN layer–bin pairs. Since the failure probability for each fixed pair is at most δ/(2SN)δ/(2SN), the probability that the preceding bound fails for at least one pair is at most SNδ2SN=δ2.SN δ2SN= δ2. Therefore, there exists an event ℰscE_ sc with ℙ(ℰsc)≥1−δ/2,P(E_ sc)≥ 1-δ/2, on which, simultaneously for every t≤T+1t≤ T+1, s∈[S]s∈[S], and j∈[N]j∈[N], ‖∑i∈Ψt,sjψi,j(wi)εi‖(Λt,sj+λI)−1≤CψDιT. \| _i∈ _t,s^j _i,j(w_i) _i \|_( _t,s^j+λ I)^-1≤ C_ψD _T. (36) We first control the term involving the approximation errors Ri,j(wi)R_i,j(w_i). For any vector a, the Cauchy–Schwarz inequality gives |a⊤∑i∈Ψt,sjψi,j(wi)Ri,j(wi)| |a _i∈ _t,s^j _i,j(w_i)R_i,j(w_i) | =|∑i∈Ψt,sj(a⊤ψi,j(wi))Ri,j(wi)| = | _i∈ _t,s^j (a _i,j(w_i) )R_i,j(w_i) | ≤[∑i∈Ψt,sj(a⊤ψi,j(wi))2]1/2×[∑i∈Ψt,sjRi,j(wi)2]1/2. ≤ [ _i∈ _t,s^j (a _i,j(w_i) )^2 ]^1/2× [ _i∈ _t,s^jR_i,j(w_i)^2 ]^1/2. By the definition of Λt,sj _t,s^j, ∑i∈Ψt,sj(a⊤ψi,j(wi))2 _i∈ _t,s^j (a _i,j(w_i) )^2 =a⊤Λt,sja≤a⊤(Λt,sj+λI)a=‖a‖Λt,sj+λI2. =a _t,s^ja≤ a ( _t,s^j+λ I)a=\|a\|_ _t,s^j+λ I^2. Therefore, |a⊤∑i∈Ψt,sjψi,j(wi)Ri,j(wi)|≤‖a‖Λt,sj+λI[∑i∈Ψt,sjRi,j(wi)2]1/2. |a _i∈ _t,s^j _i,j(w_i)R_i,j(w_i) |≤\|a\|_ _t,s^j+λ I [ _i∈ _t,s^jR_i,j(w_i)^2 ]^1/2. Taking a=(Λt,sj+λI)−1∑i∈Ψt,sjψi,j(wi)Ri,j(wi)a=( _t,s^j+λ I)^-1 _i∈ _t,s^j _i,j(w_i)R_i,j(w_i) in the preceding inequality yields ‖∑i∈Ψt,sjψi,j(wi)Ri,j(wi)‖(Λt,sj+λI)−12≤‖∑i∈Ψt,sjψi,j(wi)Ri,j(wi)‖(Λt,sj+λI)−1[∑i∈Ψt,sjRi,j(wi)2]1/2. \| _i∈ _t,s^j _i,j(w_i)R_i,j(w_i) \|_( _t,s^j+λ I)^-1^2≤ \| _i∈ _t,s^j _i,j(w_i)R_i,j(w_i) \|_( _t,s^j+λ I)^-1 [ _i∈ _t,s^jR_i,j(w_i)^2 ]^1/2. Canceling the common factor when it is nonzero, while the zero case is immediate, gives ‖∑i∈Ψt,sjψi,j(wi)Ri,j(wi)‖(Λt,sj+λI)−1≤[∑i∈Ψt,sjRi,j(wi)2]1/2. \| _i∈ _t,s^j _i,j(w_i)R_i,j(w_i) \|_( _t,s^j+λ I)^-1≤ [ _i∈ _t,s^jR_i,j(w_i)^2 ]^1/2. Since |Ri,j(wi)|≤Cl(hβ+η2)|R_i,j(w_i)|≤ C_l(h^β+η^2), for every i∈Ψt,sji∈ _t,s^j, we have ∑i∈Ψt,sjRi,j(wi)2 _i∈ _t,s^jR_i,j(w_i)^2 ≤Cl2|Ψt,sj|(hβ+η2)2. ≤ C_l^2| _t,s^j|(h^β+η^2)^2. It follows that ‖∑i∈Ψt,sjψi,j(wi)Ri,j(wi)‖(Λt,sj+λI)−1≤Cl|Ψt,sj|(hβ+η2). \| _i∈ _t,s^j _i,j(w_i)R_i,j(w_i) \|_( _t,s^j+λ I)^-1≤ C_l | _t,s^j|(h^β+η^2). (37) It remains to control the term caused by the ridge regularization. Since Λt,sj+λI⪰λI, _t,s^j+λ I λ I, we have (Λt,sj+λI)−1⪯1λI.( _t,s^j+λ I)^-1 1λI. Therefore, ‖λj‖(Λt,sj+λI)−12 \|λ z_j\|_( _t,s^j+λ I)^-1^2 =λ2j⊤(Λt,sj+λI)−1j≤λ‖j‖22. =λ^2 z_j ( _t,s^j+λ I)^-1 z_j≤λ\| z_j\|_2^2. Taking square roots and using (26) gives ‖λj‖(Λt,sj+λI)−1≤λ‖j‖2≤Czλ.\|λ z_j\|_( _t,s^j+λ I)^-1≤ λ\| z_j\|_2≤ C_z λ. (38) Step 5: uniform confidence bound and completion. We work on the event ℰpil∩ℰscE_ pil _ sc, which has probability at least 1−δ1-δ. Fix a main-policy round t, a layer s∈[st]s∈[s_t], and an action (j,w)∈t,s(j,w) _t,s. Assume first that |Ψt,sj|≥1| _t,s^j|≥ 1. By (34) and multiplying both sides by ψt,j(w)⊤ _t,j(w) , taking absolute values, and applying the triangle inequality gives |ψt,j(w)⊤(^t,sj−j)|≤∥ψt,j(w)∥(Λt,sj+λI)−1[∥∑i∈Ψt,sjψi,j(wi)εi∥(Λt,sj+λI)−1 | _t,j(w) ( z_t,s^j- z_j ) |≤ \| _t,j(w) \|_( _t,s^j+λ I)^-1 [\ \| _i∈ _t,s^j _i,j(w_i) _i \|_( _t,s^j+λ I)^-1 +∥∑i∈Ψt,sjψi,j(wi)Ri,j(wi)∥(Λt,sj+λI)−1+∥λj∥(Λt,sj+λI)−1]. 119.50157pt+ \| _i∈ _t,s^j _i,j(w_i)R_i,j(w_i) \|_( _t,s^j+λ I)^-1+ \|λ z_j \|_( _t,s^j+λ I)^-1 ]. Using (36), (37), and (38), we obtain |ψt,j(w)⊤(^t,sj−j)| | _t,j(w) ( z_t,s^j- z_j ) | ≤(CψDιT+Czλ)‖ψt,j(w)‖(Λt,sj+λI)−1 ≤ (C_ψD _T+C_z λ ) \| _t,j(w) \|_( _t,s^j+λ I)^-1 +Cl(hβ+η2)|Ψt,sj|‖ψt,j(w)‖(Λt,sj+λI)−1. +C_l(h^β+η^2) | _t,s^j| \| _t,j(w) \|_( _t,s^j+λ I)^-1. The preceding inequality controls the error caused by replacing j z_j with its estimator ^t,sj z_t,s^j. We must also account for the approximation error at the current action. By (33), g(p^t(w)−t⊤⋆)=ψt,j(w)⊤j+Rt,j(w),g\! ( p_t(w)- x_t θ_ )= _t,j(w) z_j+R_t,j(w), where |Rt,j(w)|≤Cl(hβ+η2).|R_t,j(w)|≤ C_l(h^β+η^2). Therefore, |ψt,j(w)⊤^t,sj−g(p^t(w)−t⊤⋆)| | _t,j(w) z_t,s^j-g\! ( p_t(w)- x_t θ_ ) | =|ψt,j(w)⊤(^t,sj−j)−Rt,j(w)| = | _t,j(w) ( z_t,s^j- z_j )-R_t,j(w) | ≤|ψt,j(w)⊤(^t,sj−j)|+|Rt,j(w)| ≤ | _t,j(w) ( z_t,s^j- z_j ) |+|R_t,j(w)| ≤(CψDιT+Czλ)‖ψt,j(w)‖(Λt,sj+λI)−1 ≤ (C_ψD _T+C_z λ ) \| _t,j(w) \|_( _t,s^j+λ I)^-1 +Cl(hβ+η2)[1+|Ψt,sj|‖ψt,j(w)‖(Λt,sj+λI)−1]. +C_l(h^β+η^2) [1+ | _t,s^j| \| _t,j(w) \|_( _t,s^j+λ I)^-1 ]. The algorithm restricts the estimated demand to the interval [0,D][0,D]: g^t,sj(w)=Π[0,D](ψt,j(w)⊤^t,sj). g_t,s^j(w)= _[0,D]\! ( _t,j(w) z_t,s^j ). This restriction cannot increase the error because the true mean demand also belongs to [0,D][0,D]. Indeed, for every a∈ℝa and every b∈[0,D]b∈[0,D], |Π[0,D](a)−b|≤|a−b|. | _[0,D](a)-b |≤|a-b|. Moreover, both Π[0,D](a) _[0,D](a) and b belong to [0,D][0,D], so |Π[0,D](a)−b|≤D. | _[0,D](a)-b |≤ D. Applying these two inequalities with a=ψt,j(w)⊤^t,sja= _t,j(w) z_t,s^j and b=g(p^t(w)−t⊤⋆)b=g\! ( p_t(w)- x_t θ_ ) gives |g^t,sj(w)−g(p^t(w)−t⊤⋆)| | g_t,s^j(w)-g\! ( p_t(w)- x_t θ_ ) | ≤minD,(CψDιT+Czλ)∥ψt,j(w)∥(Λt,sj+λI)−1 ≤ \D,\, (C_ψD _T+C_z λ ) \| _t,j(w) \|_( _t,s^j+λ I)^-1 +Cl(hβ+η2)[1+|Ψt,sj|∥ψt,j(w)∥(Λt,sj+λI)−1]≤rt,sj(w). 51.21495pt+C_l(h^β+η^2) [1+ | _t,s^j| \| _t,j(w) \|_( _t,s^j+λ I)^-1 ] \≤ r_t,s^j(w). It remains to consider the case |Ψt,sj|=0| _t,s^j|=0. Then Ψt,sj=∅ _t,s^j= and Λt,sj= _t,s^j= 0. The optimization problem reduces to minλ‖22. _ zλ\| z\|_2^2. Since λ>0λ>0, its unique minimizer is ^t,sj=. z_t,s^j= 0. It follows that g^t,sj(w)=Π[0,D](0)=0. g_t,s^j(w)= _[0,D](0)=0. The algorithm sets rt,sj(w)=D.r_t,s^j(w)=D. Since the true mean demand belongs to [0,D][0,D], |g^t,sj(w)−g(p^t(w)−t⊤⋆)|=|g(p^t(w)−t⊤⋆)|≤D=rt,sj(w). | g_t,s^j(w)-g\! ( p_t(w)- x_t θ_ ) |= |g\! ( p_t(w)- x_t θ_ ) |≤ D=r_t,s^j(w). Finally, the event ℰpilE_ pil controls all periods simultaneously, and the event ℰscE_ sc controls all periods, layers, and bins simultaneously. Once these two events occur, the preceding inequalities can be applied to every residual action w because they use only the already established vector bounds and the Cauchy–Schwarz inequality. Thus no separate probability bound is needed for each w. Therefore, (9) holds simultaneously for every main-policy round t, every s∈[st]s∈[s_t], and every (j,w)∈t,s(j,w) _t,s. □ A.3 Proofs for the Contextual Regret Bounds Proof of Lemma 5.1. Proof. We proceed in four steps. Step 1: Revenue-UCB sandwich. Fix a visited layer s and an action (j,w)∈t,s(j,w) _t,s. On the confidence event, |g^t,sj(w)−g(p^t(w)−t⊤⋆)|≤rt,sj(w). | g_t,s^j(w)-g\! ( p_t(w)- x_t θ_ ) |≤ r_t,s^j(w). Because the true conditional mean belongs to [0,D][0,D], g(p^t(w)−t⊤⋆) g\! ( p_t(w)- x_t θ_ ) ≤minD,g^t,sj(w)+rt,sj(w)≤g(p^t(w)−t⊤⋆)+2rt,sj(w). ≤ \D, g_t,s^j(w)+r_t,s^j(w) \≤ g\! ( p_t(w)- x_t θ_ )+2r_t,s^j(w). Multiplying by p^t(w)≥0 p_t(w)≥ 0 and using the definitions of Ut,sj(w)U_t,s^j(w) and widt,sj(w)wid_t,s^j(w) gives (t,p^t(w)) Rev ( x_t, p_t(w) ) ≤Ut,sj(w)≤(t,p^t(w))+2widt,sj(w). ≤ U_t,s^j(w)≤ Rev ( x_t, p_t(w) )+2wid_t,s^j(w). (39) Step 2: Preservation of the discrete benchmark. Suppose that the precision check passes at a layer s<Ss<S. Then widt,sj(w)≤BD 2−sfor every (j,w)∈t,s.wid_t,s^j(w)≤ BD\,2^-s every (j,w) _t,s. Choose (j⋆,w⋆)∈argmax(j,w)∈t,s(t,p^t(w)).(j ,w )∈ *argmax_(j,w) _t,s Rev ( x_t, p_t(w) ). By the lower side of (39), Ut,sj⋆(w⋆)≥Vt,s.U_t,s^j (w )≥ V_t,s. By its upper side, for every (j,w)∈t,s(j,w) _t,s, Ut,sj(w)≤Vt,s+2BD 2−s=Vt,s+BD 21−s.U_t,s^j(w)≤ V_t,s+2BD\,2^-s=V_t,s+BD\,2^1-s. Consequently, Ut,sj⋆(w⋆)≥max(j,w)∈t,sUt,sj(w)−BD 21−s.U_t,s^j (w )≥ _(j,w) _t,sU_t,s^j(w)-BD\,2^1-s. By the definition of t,s+1A_t,s+1 in Algorithm 2, the preceding inequality implies that (j⋆,w⋆)∈t,s+1(j ,w ) _t,s+1. Since (j⋆,w⋆)(j ,w ) attains Vt,sV_t,s, it follows that Vt,s+1≥(t,p^t(w⋆))=Vt,s.V_t,s+1≥ Rev ( x_t, p_t(w ) )=V_t,s. On the other hand, t,s+1⊆t,sA_t,s+1 _t,s, and hence Vt,s+1≤Vt,sV_t,s+1≤ V_t,s. Therefore, Vt,s+1=Vt,sV_t,s+1=V_t,s. Step 3: Gap between the selected price and the initial discrete benchmark. Suppose that st≥2s_t≥ 2. To reach layer sts_t, the algorithm must have passed the precision check at layer st−1s_t-1. Moreover, (jt,wt)∈t,st(j_t,w_t) _t,s_t, so this action survived the refinement from layer st−1s_t-1 to layer sts_t. Hence Ut,st−1jt(wt) U_t,s_t-1^j_t(w_t) ≥max(j,w)∈t,st−1Ut,st−1j(w)−BD 22−st≥Vt,st−1−BD 22−st. ≥ _(j,w) _t,s_t-1U_t,s_t-1^j(w)-BD\,2^2-s_t≥ V_t,s_t-1-BD\,2^2-s_t. (40) The upper side of (39) and the precision check at layer st−1s_t-1 give Ut,st−1jt(wt) U_t,s_t-1^j_t(w_t) ≤(t,pt)+2BD 2−(st−1)=(t,pt)+BD 22−st. ≤ Rev( x_t,p_t)+2BD\,2^-(s_t-1)= Rev( x_t,p_t)+BD\,2^2-s_t. (41) Combining (40) and (41) yields Vt,st−1−(t,pt)≤2BD 22−st.V_t,s_t-1- Rev( x_t,p_t)≤ 2BD\,2^2-s_t. Every layer preceding sts_t passed the precision check. Repeated application of Step 2 therefore gives Vt,st−1=Vt,1V_t,s_t-1=V_t,1, which proves the second assertion of the lemma. Step 4: Discretization of the continuous oracle price. If β=1β=1, Assumption 3.4 implies that g is LgL_g-Lipschitz. If β>1β>1, Step 2 of the proof of Proposition 4.2 gives supu∈ℐg|g′(u)|≤Cg. _u _g|g (u)|≤ C_g. Hence g is Lipschitz on ℐgI_g with constant maxLg,Cg \L_g,C_g\. Since both residual arguments below belong to ℐgI_g by Assumption 3.1, for every ∈ x and p,p′∈[0,B]p,p ∈[0,B], |(,p)−(,p′)| | Rev( x,p)- Rev( x,p ) | ≤D|p−p′|+B|g(p−⊤⋆)−g(p′−⊤⋆)|≤LRev|p−p′|, ≤ D|p-p |+B |g(p- x θ_ )-g(p - x θ_ ) |≤ L_Rev|p-p |, where one may take LRev=D+BmaxLg,CgL_Rev=D+B \L_g,C_g\. The oracle residual pt⋆−Π[0,B](t⊤^t)p_t - _[0,B]\! ( x_t θ_t ) belongs to [−B,B][-B,B]. The feasible residual set is the interval [−Π[0,B](t⊤^t),B−Π[0,B](t⊤^t)], [- _[0,B]\! ( x_t θ_t ),B- _[0,B]\! ( x_t θ_t ) ], which contains both zero and the oracle residual. By choosing a point of W between zero and the oracle residual, the mesh definition of W, together with the explicitly included endpoints, gives a feasible w∈w satisfying |w−[pt⋆−Π[0,B](t⊤^t)]|≤T−1/2. |w- [p_t - _[0,B]\! ( x_t θ_t ) ] |≤ T^-1/2. Assigning this w to its unique bin yields an action in t,1A_t,1, and |p^t(w)−pt⋆|≤T−1/2. | p_t(w)-p_t |≤ T^-1/2. Hence (t,pt⋆)−Vt,1≤LRevT. Rev( x_t,p_t )-V_t,1≤ L_Rev T. If st≥2s_t≥ 2, combining this inequality with the bound established in Step 3 proves (10). If st=1s_t=1, then 0≤(t,p)≤BD0≤ Rev( x_t,p)≤ BD for every feasible price, so (t,pt⋆)−(t,pt) Rev( x_t,p_t )- Rev( x_t,p_t) ≤LRevT+Vt,1−(t,pt)≤LRevT+BD≤LRevT+8BD 2−st. ≤ L_Rev T+V_t,1- Rev( x_t,p_t)≤ L_Rev T+BD≤ L_Rev T+8BD2^-s_t. Thus the same conclusion holds for st=1s_t=1. □ Proof of counting lemmas. Lemma A.2 (Cumulative revenue uncertainty within one layer) There exists a finite constant Cω≥1C_ω≥ 1, such that, for every s∈[S]s∈[S], pathwise, ∑t∈ΨT+1,swidt,sjt(wt)≤CωB[ _t∈ _T+1,swid_t,s^j_t(w_t)≤ C_ωB [ (DιT+λ)N|ΨT+1,s|ιT+(hβ+η2)|ΨT+1,s|ιT]. (D _T+ λ ) N| _T+1,s|\, _T+(h^β+η^2)| _T+1,s| _T ]. (42) The right-hand side is interpreted as zero when ΨT+1,s=∅ _T+1,s= . Proof. Fix s∈[S]s∈[S]. The claim is immediate if ΨT+1,s=∅ _T+1,s= . We first work within one nonempty bin and then sum over bins. Step 1: Sequential Gram matrices within a permanent bin. Fix j∈[N]j∈[N] with ΨT+1,sj≠∅ _T+1,s^j≠ , and enumerate its observations chronologically as ΨT+1,sj=tj,1<⋯<tj,|ΨT+1,sj|. _T+1,s^j=\t_j,1<·s<t_j,| _T+1,s^j|\. Permanent labeling and the definition of Λt,sj _t,s^j imply that, for every k≤|ΨT+1,sj|k≤| _T+1,s^j|, Λtj,k,sj+λI=λI+∑ℓ<kψtj,ℓ,j(wtj,ℓ)ψtj,ℓ,j(wtj,ℓ)⊤,|Ψtj,k,sj|=k−1. _t_j,k,s^j+λ I=λ I+ _ <k _t_j, ,j(w_t_j, ) _t_j, ,j(w_t_j, ) , | _t_j,k,s^j|=k-1. (43) Step 2: Elliptical-potential bound. The uniform feature bound established in the proof of Proposition 4.2 gives ‖ψt,j(wt)‖2≤Cψ\| _t,j(w_t)\|_2≤ C_ψ. Applying the matrix determinant lemma sequentially to (43), and using min1,x≤2log(1+x) \1,x\≤ 2 (1+x) for x≥0x≥ 0, yields ∑k=1|ΨT+1,sj|min1,‖ψtj,k,j(wtj,k)‖(Λtj,k,sj+λI)−12 _k=1^| _T+1,s^j| \1, \| _t_j,k,j(w_t_j,k) \|_( _t_j,k,s^j+λ I)^-1^2 \ ≤2logdet(λI+∑k=1|ΨT+1,sj|ψtj,k,j(wtj,k)ψtj,k,j(wtj,k)⊤)det(λI) ≤ 2 \! (λ I+ _k=1^| _T+1,s^j| _t_j,k,j(w_t_j,k) _t_j,k,j(w_t_j,k) ) (λ I) ≤2[1+ϖ(β)(d+1)]log(1+Cψ2|ΨT+1,sj|λ[1+ϖ(β)(d+1)]) ≤ 2 [1+ (β)(d+1) ] \! (1+ C_ψ^2| _T+1,s^j|λ[1+ (β)(d+1)] ) ≤2max1,Cψ2ιT. ≤ 2 \1,C_ψ^2\\, _T. (44) The last inequality follows from |ΨT+1,sj|≤T| _T+1,s^j|≤ T, the definition of ιT _T, and log(1+ax)≤max1,alog(1+x) (1+ax)≤ \1,a\ (1+x) for a,x≥0a,x≥ 0. By Cauchy–Schwarz and (44), ∑k=1|ΨT+1,sj|min1,‖ψtj,k,j(wtj,k)‖(Λtj,k,sj+λI)−1 _k=1^| _T+1,s^j| \1, \| _t_j,k,j(w_t_j,k) \|_( _t_j,k,s^j+λ I)^-1 \ (45) ≤|ΨT+1,sj|∑k=1|ΨT+1,sj|min1,‖ψtj,k,j(wtj,k)‖(Λtj,k,sj+λI)−12≤2max1,Cψ2|ΨT+1,sj|ιT. ≤ | _T+1,s^j| _k=1^| _T+1,s^j| \1, \| _t_j,k,j(w_t_j,k) \|_( _t_j,k,s^j+λ I)^-1^2 \≤ 2 \1,C_ψ^2\\, | _T+1,s^j| _T. Step 3: Sum of confidence radii within one bin. The first observation in the bin satisfies |Ψtj,1,sj|=0,| _t_j,1,s^j|=0, and therefore (7) gives rtj,1,sj(wtj,1)=D.r_t_j,1,s^j(w_t_j,1)=D. For k≥2k≥ 2, we have |Ψtj,k,sj|=k−1≤|ΨT+1,sj|.| _t_j,k,s^j|=k-1≤| _T+1,s^j|. Therefore, the radius definition and its truncation at D imply rtj,k,sj(wtj,k)≤maxCψ,Cz(DιT+λ)min1,‖ψtj,k,j(wtj,k)‖(Λtj,k,sj+λI)−1 r_t_j,k,s^j(w_t_j,k)≤ \C_ψ,C_z\ (D _T+ λ ) \1, \| _t_j,k,j(w_t_j,k) \|_( _t_j,k,s^j+λ I)^-1 \ +Cl(hβ+η2)[1+|ΨT+1,sj|min1,‖ψtj,k,j(wtj,k)‖(Λtj,k,sj+λI)−1]. +C_l(h^β+η^2) [1+ | _T+1,s^j| \1, \| _t_j,k,j(w_t_j,k) \|_( _t_j,k,s^j+λ I)^-1 \ ]. (46) Summing (46) over k≥2k≥ 2, adding the first radius, and applying (45) gives ∑t∈ΨT+1,sjrt,sj(wt)≤ _t∈ _T+1,s^jr_t,s^j(w_t)≤ D+maxCψ,Cz2max1,Cψ2(DιT+λ)|ΨT+1,sj|ιT D+ \C_ψ,C_z\ 2 \1,C_ψ^2\ (D _T+ λ ) | _T+1,s^j| _T +Cl(hβ+η2)[|ΨT+1,sj|+2max1,Cψ2|ΨT+1,sj|ιT]. +C_l(h^β+η^2) [| _T+1,s^j|+ 2 \1,C_ψ^2\\,| _T+1,s^j| _T ]. Since |ΨT+1,sj|≥1| _T+1,s^j|≥ 1, ιT>1 _T>1, and DιT+λ≥D _T+ λ≥ D, the first and third terms can be absorbed, yielding ∑t∈ΨT+1,sjrt,sj(wt)≤ _t∈ _T+1,s^jr_t,s^j(w_t)≤ [1+maxCψ,Cz2max1,Cψ2]⋅(DιT+λ)|ΨT+1,sj|ιT [1+ \C_ψ,C_z\ 2 \1,C_ψ^2\ ]· (D _T+ λ ) | _T+1,s^j| _T (47) +Cl[1+2max1,Cψ2](hβ+η2)|ΨT+1,sj|ιT. +C_l [1+ 2 \1,C_ψ^2\ ](h^β+η^2)| _T+1,s^j| _T. Step 4: Sum over bins and convert demand radii to revenue widths. By Cauchy–Schwarz, ∑j=1N|ΨT+1,sj|≤N∑j=1N|ΨT+1,sj|=N|ΨT+1,s|, _j=1^N | _T+1,s^j|≤ N _j=1^N| _T+1,s^j|= N| _T+1,s|, and, by the permanent partition, ∑j=1N|ΨT+1,sj|=|ΨT+1,s|. _j=1^N| _T+1,s^j|=| _T+1,s|. By choosing Cω=max1+maxCψ,Cz2max1,Cψ2,Cl(1+2max1,Cψ2),C_ω= \1+ \C_ψ,C_z\ 2 \1,C_ψ^2\,\;C_l (1+ 2 \1,C_ψ^2\ ) \, both coefficients in (47) are bounded by CωC_ω. Summing over bins and using widt,sjt(wt)=p^t(wt)rt,sjt(wt)≤Brt,sjt(wt),wid_t,s^j_t(w_t)= p_t(w_t)r_t,s^j_t(w_t)≤ Br_t,s^j_t(w_t), therefore proves (42). □ Lemma A.3 (Occupancy of a nonterminal LDP layer) Let CωC_ω be as in Lemma A.2. For every s<Ss<S, pathwise, D2−s|ΨT+1,s|≤Cω[ D2^-s| _T+1,s|≤ C_ω [ (DιT+λ)N|ΨT+1,s|ιT+(hβ+η2)|ΨT+1,s|ιT]. (D _T+ λ ) N| _T+1,s|\, _T+(h^β+η^2)| _T+1,s| _T ]. (48) Moreover, if D2−s≥2Cω(hβ+η2)ιT,D2^-s≥ 2C_ω(h^β+η^2) _T, (49) then |ΨT+1,s|≤4Cω2(DιT+λ)2D222sNιT.| _T+1,s|≤ 4C_ω^2 (D _T+ λ )^2D^22^2sN _T. (50) Proof. Fix s<Ss<S. If ΨT+1,s=∅ _T+1,s= , both conclusions are immediate. Suppose that ΨT+1,s≠∅ _T+1,s≠ . Every round t∈ΨT+1,st∈ _T+1,s is assigned to the nonterminal layer s. Under Algorithm 2, selection at such a layer can occur only through the under-explored branch. Therefore, widt,sjt(wt)>BD 2−swid_t,s^j_t(w_t)>BD\,2^-s for t∈ΨT+1,s.t∈ _T+1,s. Summing this inequality over t∈ΨT+1,st∈ _T+1,s and applying Lemma A.2 gives BD 2−s|ΨT+1,s| BD2^-s| _T+1,s| <∑t∈ΨT+1,swidt,sjt(wt) < _t∈ _T+1,swid_t,s^j_t(w_t) ≤CωB[(DιT+λ)N|ΨT+1,s|ιT+(hβ+η2)|ΨT+1,s|ιT]. ≤ C_ωB [ (D _T+ λ ) N| _T+1,s|\, _T+(h^β+η^2)| _T+1,s| _T ]. Since B>0B>0, dividing by B and weakening the resulting strict inequality proves (48). Suppose now that (49) holds. Then Cω(hβ+η2)ιT≤D22−s.C_ω(h^β+η^2) _T≤ D22^-s. It follows from (48) that D22−s|ΨT+1,s| D22^-s| _T+1,s| ≤[D2−s−Cω(hβ+η2)ιT]|ΨT+1,s|≤Cω(DιT+λ)N|ΨT+1,s|ιT. ≤ [D2^-s-C_ω(h^β+η^2) _T ]| _T+1,s|≤ C_ω (D _T+ λ ) N| _T+1,s|\, _T. Both sides are nonnegative. Squaring this inequality gives D242−2s|ΨT+1,s|2≤Cω2(DιT+λ)2N|ΨT+1,s|ιT. D^242^-2s| _T+1,s|^2≤ C_ω^2 (D _T+ λ )^2N| _T+1,s| _T. Because |ΨT+1,s|>0| _T+1,s|>0, canceling this factor and rearranging yields |ΨT+1,s|≤4Cω2(DιT+λ)2D222sNιT,| _T+1,s|≤ 4C_ω^2 (D _T+ λ )^2D^22^2sN _T, which proves (50). □ Proof of Proposition 5.2. Proof. We proceed in five steps. Throughout the proof, C denotes a finite constant depending only on the fixed problem primitives and on Cψ,Cz,ClC_ψ,C_z,C_l; its value may increase from line to line. Step 1: Reduction to a dyadic layer sum. Note that, the sets ΨT+1,1,…,ΨT+1,S _T+1,1,…, _T+1,S are disjoint and contain all LDP rounds. Therefore, ∑s=1S|ΨT+1,s|≤T. _s=1^S| _T+1,s|≤ T. (51) By Lemma 5.1, every LDP round t satisfies (t,pt⋆)−(t,pt)≤LRevT+8BD 2−st. Rev( x_t,p_t )- Rev( x_t,p_t)≤ L_Rev T+8BD\,2^-s_t. Summing over the LDP rounds and using their layer partition gives ∑t∈[T]∖exp[(t,pt⋆)−(t,pt)]≤LRevT+8BD∑s=1S2−s|ΨT+1,s|. _t∈[T] exp [ Rev( x_t,p_t )- Rev( x_t,p_t) ]≤ L_Rev T+8BD _s=1^S2^-s| _T+1,s|. (52) Step 2: Nonterminal layers dominated by statistical uncertainty. For every nonterminal layer s<Ss<S satisfying (49), Lemma A.3 gives |ΨT+1,s|≤4Cω2(DιT+λ)2D222sNιT.| _T+1,s|≤ 4C_ω^2 (D _T+ λ )^2D^22^2sN _T. The deterministic bound |ΨT+1,s|≤T| _T+1,s|≤ T also holds. Note that for every a>0a>0, we have ∑s≥12−sminT,a22s≤4aT, _s≥ 12^-s \T,a2^2s\≤ 4 aT, (53) because if a≥Ta≥ T, the left-hand side is at most T∑s≥12−s≤T≤aT _s≥ 12^-s≤ T≤ aT, while if a<Ta<T, choose an integer s0≥0s_0≥ 0 such that 2s0≤T/a<2s0+12^s_0≤ T/a<2^s_0+1, then ∑s≥12−sminT,a22s _s≥ 12^-s \T,a2^2s\ ≤a∑s≤s02s+T∑s>s02−s≤2a2s0+T2−s0≤4aT. ≤ a _s≤ s_02^s+T _s>s_02^-s≤ 2a2^s_0+T2^-s_0≤ 4 aT. Applying (53) with a=4Cω2(DιT+λ)2D2NιTa=4C_ω^2 (D _T+ λ )^2D^2N _T yields ∑s<S:D2−s≥2Cω(hβ+η2)ιT2−s|ΨT+1,s|≤4aT=8CωDιT+λDNTιT. _ subarraycs<S:\ D2^-s≥ 2C_ω(h^β+η^2) _T subarray2^-s| _T+1,s|≤ 4 aT=8C_ω D _T+ λD NT _T. (54) Step 3: Nonterminal layers dominated by approximation bias. For every remaining nonterminal layer, D2−s<2Cω(hβ+η2)ιT,D2^-s<2C_ω(h^β+η^2) _T, and hence 2−s<2Cω(hβ+η2)ιTD.2^-s< 2C_ω(h^β+η^2) _TD. Consequently, ∑s<S:D2−s<2Cω(hβ+η2)ιT2−s|ΨT+1,s| _ subarraycs<S:\\ D2^-s<2C_ω(h^β+η^2) _T subarray2^-s| _T+1,s| ≤2Cω(hβ+η2)ιTD∑s<S|ΨT+1,s|≤2Cω(hβ+η2)ιTDT. ≤ 2C_ω(h^β+η^2) _TD _s<S| _T+1,s|≤ 2C_ω(h^β+η^2) _TDT. (55) Step 4: Terminal layer and completion of the explicit bound. For the terminal layer, 2−S|ΨT+1,S|≤T2−S.2^-S| _T+1,S|≤ T2^-S. (56) Combining (54), (55), and (56), we obtain ∑s=1S2−s|ΨT+1,s|≤ _s=1^S2^-s| _T+1,s|≤ 8CωDιT+λDNTιT+2Cω(hβ+η2)ιTDT+T2−S. 8C_ω D _T+ λD NT _T+ 2C_ω(h^β+η^2) _TDT+T2^-S. Substituting this inequality into (52) gives ∑t∈[T]∖exp[(t,pt⋆)−(t,pt)] _t∈[T] exp [ Rev( x_t,p_t )- Rev( x_t,p_t) ] ≤64CωB(DιT+λ)NTιT+16CωBT(hβ+η2)ιT+8BDT2−S+LRevT. ≤ 4C_ωB (D _T+ λ ) NT _T+6C_ωBT(h^β+η^2) _T+8BDT2^-S+L_Rev T. For S=max1,⌈log2T⌉S= \1, _2 T \, we have T2−S≤T2^-S≤ T. Therefore, (11) follows. Step 5: Simplified rate under algorithmic tuning. Let λ>0λ>0 be fixed independently of T, let η2≤cηhβη^2≤ c_ηh^β, and let N=⌈T12β+1⌉N= T 12β+1 . Since T≥1T≥ 1, we have T12β+1≤N≤2T12β+1T 12β+1≤ N≤ 2T 12β+1. It follows that NT≤2Tβ+12β+1, NT≤ 2T β+12β+1, and, because h=2B/Nh=2B/N, T(hβ+η2)≤(1+cη)Thβ=(1+cη)(2B)βTN−β≤(1+cη)(2B)βTβ+12β+1. T(h^β+η^2)≤(1+c_η)Th^β=(1+c_η)(2B)^βTN^-β≤(1+c_η)(2B)^βT β+12β+1. Moreover, T≤Tβ+12β+1 T≤ T β+12β+1 for every finite β≥1β≥ 1. By the definition of ιT _T, we have ιT>1 _T>1. Since λ>0λ>0 is fixed independently of T, (DιT+λ)ιT=DιT+λιT≤(D+λ)ιT, (D _T+ λ ) _T=D _T+ λ _T≤(D+ λ) _T, and ιT≤ιT _T≤ _T. Applying these inequalities to (11) gives ∑t∈[T]∖exp[(t,pt⋆)−(t,pt)] _t∈[T] exp [ Rev( x_t,p_t )- Rev( x_t,p_t) ] ≤[642CωB(D+λ)+16CωB(1+cη)(2B)β+8BD+LRev]ιTTβ+12β+1. ≤ [4 2\,C_ωB (D+ λ )+6C_ωB(1+c_η)(2B)^β+8BD+L_Rev ] _TT β+12β+1. One may take CLDP:= C_LDP= 642CωB(D+λ)+16CωB(1+cη)(2B)β+8BD+LRev. 4 2\,C_ωB (D+ λ )+6C_ωB(1+c_η)(2B)^β+8BD+L_Rev. This proves (12). □ Proof of Lemma 5.3. Proof. Fix an arbitrary realization of the policy. If exp=∅T exp= , all conclusions are immediate. Otherwise, enumerate the pilot-exploration rounds chronologically as exp=τ1<⋯<τ|exp|.T exp= \ _1<·s< _|T exp| \. Step 1: Leverage on exploration rounds. For every k=1,…,|exp|k=1,…,|T exp|, period τk _k is a pilot-exploration round. Therefore, by the uncertainty gate in Algorithm 1, γT‖τk‖Mτk−1>η. _T\| x_ _k\|_M_ _k^-1>η. Since γT>0 _T>0, squaring both sides gives ‖τk‖Mτk−12>η2γT2.\| x_ _k\|_M_ _k^-1^2> η^2 _T^2. (57) Step 2: Exact determinant recursion. The matrix MtM_t is updated only on pilot-exploration rounds. In particular, Mτ1=M1=IdM_ _1=M_1=I_d, and, for every k=1,…,|exp|−1k=1,…,|T exp|-1, Mτk+1=Mτk+τkτk⊤,M_ _k+1=M_ _k+ x_ _k x_ _k , because MtM_t remains unchanged on all LDP rounds strictly between τk _k and τk+1 _k+1. Similarly, MT+1=Mτ|exp|+τ|exp|τ|exp|⊤.M_T+1=M_ _|T exp|+ x_ _|T exp| x_ _|T exp| . Since Mτk⪰IdM_ _k I_d, it is positive definite. The matrix determinant lemma therefore gives det(Mτk+τkτk⊤) (M_ _k+ x_ _k x_ _k ) =det(Mτk)(1+τk⊤Mτk−1τk)=det(Mτk)(1+‖τk‖Mτk−12). = (M_ _k) (1+ x_ _k M_ _k^-1 x_ _k )= (M_ _k) (1+\| x_ _k\|_M_ _k^-1^2 ). Iterating this identity and using det(Mτ1)=det(Id)=1 (M_ _1)= (I_d)=1 yields logdet(MT+1)=∑k=1|exp|log(1+‖τk‖Mτk−12). (M_T+1)= _k=1^|T exp| (1+\| x_ _k\|_M_ _k^-1^2 ). (58) Step 3: Lower bound on the determinant growth. By (57), every summand in (58) satisfies log(1+‖τk‖Mτk−12)>log(1+η2γT2). (1+\| x_ _k\|_M_ _k^-1^2 )> (1+ η^2 _T^2 ). Summing over k gives, |exp|log(1+η2γT2)<logdet(MT+1). |T exp | (1+ η^2 _T^2 )< (M_T+1). (59) Step 4: Upper bound on the determinant. By the update rule, MT+1=Id+∑t∈exptt⊤.M_T+1=I_d+ _t exp x_t x_t . Therefore, we have tr(MT+1)=d+∑t∈exp‖t‖22≤d+TCx2. (M_T+1)=d+ _t exp\| x_t\|_2^2≤ d+TC_x^2. Since MT+1M_T+1 is positive definite, by the arithmetic–geometric mean inequality applied to the eigenvalues of MT+1M_T+1, det(MT+1)1/d≤tr(MT+1)d. (M_T+1)^1/d≤ tr(M_T+1)d. Consequently, logdet(MT+1)≤dlog(tr(MT+1)d)≤dlog(1+TCx2d). (M_T+1)≤ d ( tr(M_T+1)d )≤ d (1+ TC_x^2d ). (60) Combining (59) and (60) yields |exp|<dlog(1+TCx2/d)log(1+η2/γT2). |T exp |< d (1+TC_x^2/d ) (1+η^2/ _T^2 ). Together with the trivial bound |exp|≤T |T exp |≤ T, this proves the first inequality in (13). For every x≥0x≥ 0, log(1+x)≥x/(1+x). (1+x)≥ x/(1+x). Applying this inequality with x=η2/γT2x=η^2/ _T^2 gives 1log(1+η2/γT2)≤1+γT2η2. 1 (1+η^2/ _T^2 )≤ 1+ _T^2η^2. This proves the second inequality in (13). Step 5: Pilot-exploration regret. Since 0≤g(u)≤D0≤ g(u)≤ D and 0≤p≤B0≤ p≤ B, 0≤(,p)=pg(p−⊤⋆)≤BD.0≤ Rev( x,p)=p\,g(p- x θ_ )≤ BD. Therefore, for every t∈expt exp, 0≤(t,pt⋆)−(t,pt)≤(t,pt⋆)≤BD. 0≤ Rev( x_t,p_t )- Rev( x_t,p_t)≤ Rev( x_t,p_t )≤ BD. Summing over t∈expt exp and applying (13) proves (14). □ Proof of Theorem 5.4. Proof. We work throughout on the uniform confidence event in Proposition 4.2, which occurs with probability at least 1−δ1-δ. Step 1: Decomposition of the regret. The pilot-exploration rounds and the LDP rounds form a disjoint partition of the horizon. Therefore, Reg(T)=∑t∈exp[(t,pt⋆)−(t,pt)]+∑t∈[T]∖exp[(t,pt⋆)−(t,pt)]. (T)= _t exp [ Rev( x_t,p_t )- Rev( x_t,p_t) ]+ _t∈[T] exp [ Rev( x_t,p_t )- Rev( x_t,p_t) ]. (61) Step 2: Finite-sample bound. Lemma 5.3 gives the pathwise ∑t∈exp[(t,pt⋆)−(t,pt)]≤BDminT,dlog(1+TCx2/d)log(1+η2/γT2). _t exp [ Rev( x_t,p_t )- Rev( x_t,p_t) ]≤ BD \T,\, d (1+TC_x^2/d ) (1+η^2/ _T^2 ) \. (62) Proposition 5.2 and the choice S=max1,⌈log2T⌉S= \1, _2 T \ give ∑t∈[T]∖exp[(t,pt⋆)−(t,pt)] _t∈[T] exp [ Rev( x_t,p_t )- Rev( x_t,p_t) ] (63) ≤64CωB(DιT+λ)NTιT+16CωBT(hβ+η2)ιT+(8BD+LRev)T. ≤ 4C_ωB (D _T+ λ ) NT _T+6C_ωBT(h^β+η^2) _T+ (8BD+L_Rev ) T. Substituting (62) and (63) into (61) proves (15). Step 3: LDP regret under the prescribed tuning. Let N=⌈T12β+1⌉N= T 12β+1 and η2=minh2,hβη^2= \h^2,h^β\. Because η2≤h2η^2≤ h^2, we have η≤h.η≤ h. Moreover, since η2≤hβη^2≤ h^β, we have hβ+η2≤2hβh^β+η^2≤ 2h^β. Thus the prescribed tuning satisfies the conditions used in Proposition 4.2 and Proposition 5.2. Since T≥1T≥ 1, we have T12β+1≤N≤T12β+1+1≤2T12β+1.T 12β+1≤ N≤ T 12β+1+1≤ 2T 12β+1. It follows that NT NT ≤2T12+12(2β+1)=2Tβ+12β+1. ≤ 2\,T 12+ 12(2β+1)= 2\,T β+12β+1. (64) Since N≥T1/(2β+1)N≥ T^1/(2β+1) and h=2B/Nh=2B/N, Thβ Th^β =T(2BN)β≤(2B)βT1−β2β+1=(2B)βTβ+12β+1. =T ( 2BN )^β≤(2B)^βT^1- β2β+1=(2B)^βT β+12β+1. (65) Furthermore, since (β+1)/(2β+1)>1/2,(β+1)/(2β+1)>1/2, we have T≤Tβ+12β+1 T≤ T β+12β+1. By the definition of ιT _T, ιT≥2log4>1. _T≥ 2 4>1. Therefore, ιT≤ιT. _T≤ _T. In addition, (DιT+λ)NTιT=(DιT+λιT)NT≤(D+1)(1+λ)ιTNT. (D _T+ λ ) NT _T= (D _T+ λ _T ) NT≤(D+1)(1+ λ) _T NT. (66) Combining (66) with (64) gives 64CωB(DιT+λ)NTιT≤642CωB(D+1)(1+λ)ιTTβ+12β+1. 4C_ωB (D _T+ λ ) NT _T≤ 4 2\,C_ωB(D+1)(1+ λ) _TT β+12β+1. Next, by hβ+η2≤2hβh^β+η^2≤ 2h^β, (65), and ιT≤ιT _T≤ _T, 16CωBT(hβ+η2)ιT≤32CωBThβιT≤32CωB(2B)β(1+λ)ιTTβ+12β+1. 6C_ωBT(h^β+η^2) _T≤ 2C_ωBTh^β _T≤ 2C_ωB(2B)^β(1+ λ) _TT β+12β+1. Finally, by T≤Tβ+12β+1 T≤ T β+12β+1 and (1+λ)ιT≥1(1+ λ) _T≥ 1, (8BD+LRev)T≤(8BD+LRev)(1+λ)ιTTβ+12β+1. (8BD+L_Rev ) T≤ (8BD+L_Rev )(1+ λ) _TT β+12β+1. Consequently, we have ∑t∈[T]∖exp[(t,pt⋆)−(t,pt)] _t∈[T] exp [ Rev( x_t,p_t )- Rev( x_t,p_t) ] (67) ≤[642CωB(D+1)+32CωB(2B)β+8BD+LRev](1+λ)ιTTβ+12β+1. ≤ [4 2\,C_ωB(D+1)+2C_ωB(2B)^β+8BD+L_Rev ](1+ λ) _TT β+12β+1. Step 4: Pilot-exploration regret under the prescribed tuning. For every x≥0x≥ 0, log(1+x)≥x/(1+x). (1+x)≥ x/(1+x). Applying this inequality with x=η2/γT2x=η^2/ _T^2 gives 1log(1+η2/γT2)≤1+γT2η2. 1 (1+η^2/ _T^2 )≤ 1+ _T^2η^2. Thus, by (62), ∑t∈exp[(t,pt⋆)−(t,pt)]≤BDd(1+γT2η2)log(1+TCx2d). _t exp [ Rev( x_t,p_t )- Rev( x_t,p_t) ]≤ BDd (1+ _T^2η^2 ) (1+ TC_x^2d ). (68) Since N≤2T12β+1,N≤ 2T 12β+1, we have h=2B/N≥BT−12β+1.h=2B/N≥ BT^- 12β+1. Because η2=minh2,hβ,η^2= \h^2,h^β\, it follows that 1η2 1η^2 =maxh−2,h−β≤maxB−2T22β+1,B−βTβ2β+1≤maxB−2,B−βTβ+12β+1. = \h^-2,h^-β\≤ \B^-2T 22β+1,B^-βT β2β+1 \≤ \B^-2,B^-β\T β+12β+1. (69) Since T(β+1)/(2β+1)≥1T^(β+1)/(2β+1)≥ 1, 1+γT2η2 1+ _T^2η^2 ≤[1+maxB−2,B−βγT2]Tβ+12β+1≤max1,B−2,B−β(1+γT2)Tβ+12β+1. ≤ [1+ \B^-2,B^-β\ _T^2 ]T β+12β+1≤ \1,B^-2,B^-β\(1+ _T^2)T β+12β+1. Substituting this inequality into (68) gives ∑t∈exp[(t,pt⋆)−(t,pt)]≤BDmax1,B−2,B−βd(1+γT2)log(1+TCx2d)Tβ+12β+1. _t exp [ Rev( x_t,p_t )- Rev( x_t,p_t) ]≤ BD \1,B^-2,B^-β\d(1+ _T^2) (1+ TC_x^2d )T β+12β+1. (70) Step 5: Completion of the tuned bound. Define C:=max C= \ BDmax1,B−2,B−β,642CωB(D+1)+32CωB(2B)β+8BD+LRev. BD \1,B^-2,B^-β\,4 2\,C_ωB(D+1)+2C_ωB(2B)^β+8BD+L_Rev \. By Lemma A.2 and Lemma 5.1, C is finite and depends only on the fixed problem primitives. Combining (67) and (70) yields Reg(T)≤C[d(1+γT2)log(1+TCx2d)+(1+λ)ιT]Tβ+12β+1, (T)≤ C [d(1+ _T^2) (1+ TC_x^2d )+(1+ λ) _T ]T β+12β+1, which proves (16). Finally, the definitions of γT _T and ιT _T imply γT2=(logT),ιT=(logT). _T^2=O( T), _T=O( T). Consequently, d(1+γT2)log(1+TCx2d)+(1+λ)ιT=(log2T),d (1+ _T^2 ) (1+ TC_x^2d )+(1+ λ) _T=O( ^2T), and it follows that Reg(T)=~(Tβ+12β+1)Reg(T)= O\! (T β+12β+1 ) with probability at least 1−δ1-δ. This completes the proof. □ Proof of Lemma 5.8. Proof. We construct g0g_0 in four steps. We first build a nonincreasing envelope that generates a flat globally optimal revenue region and has more mass than required by the zero-mean condition. We then smooth its only kink without changing the flat region, truncate its right tail so that the zero-mean condition holds exactly, and finally verify the remaining properties and construct the compensation function χ. Step 1: Constructing a flat-revenue envelope. We first construct a nonincreasing function whose associated revenue is constant at its global maximum over an interior price interval. The construction initially has more total mass than required by the zero-mean condition; this excess mass will be removed in Step 3. Define g¯(u):=minD,D((∘)⊤∘−Bϵ/2)(∘)⊤∘+u,u∈[−Bϵ,Bϵ], g(u):= \D,\, D(( x ) θ -B_ε/2)( x ) θ +u \, u∈[-B_ε,B_ε], where the ratio is interpreted as +∞+∞ when (∘)⊤∘+u=0( x ) θ +u=0. Then g¯(u)=D,∀u≤−Bϵ2andg¯(u)=D((∘)⊤∘−Bϵ/2)(∘)⊤∘+u,∀u>−Bϵ2. g(u)=D,\,\ ∀ u≤- B_ε2 g(u)= D(( x ) θ -B_ε/2)( x ) θ +u,\,\ ∀ u>- B_ε2. Consequently, ∫−BϵBϵg¯(u)du _-B_ε^B_ε g(u)\,du =DBϵ2+D((∘)⊤∘−Bϵ2)log(1+3Bϵ2((∘)⊤∘−Bϵ/2)). = DB_ε2+D (( x ) θ - B_ε2 ) (1+ 3B_ε2(( x ) θ -B_ε/2) ). (71) For every a>0a>0, the function xlog(1+a/x)x (1+a/x ) is strictly increasing in x on (0,∞)(0,∞), because dx[xlog(1+ax)]=log(1+ax)−ax+a>0. ddx [x (1+ ax ) ]= (1+ ax )- ax+a>0. Since (∘)⊤∘−Bϵ/2≥Bϵ/2( x ) θ -B_ε/2≥ B_ε/2, take a=3Bϵ/2a=3B_ε/2 and equation (71) implies ∫−BϵBϵg¯(u)du≥DBϵ2+DBϵ2log4>DBϵ. _-B_ε^B_ε g(u)\,du≥ DB_ε2+ DB_ε2 4>DB_ε. (72) Set pL:=(∘)⊤∘−3Bϵ8,pU:=(∘)⊤∘−Bϵ4.p_L:=( x ) θ - 3B_ε8, p_U:=( x ) θ - B_ε4. Because (∘)⊤∘∈[Bϵ,B−Bϵ]( x ) θ ∈[B_ε,B-B_ε], we have 0<pL<pU<B0<p_L<p_U<B and [pL−(∘)⊤∘,pU−(∘)⊤∘]=[−3Bϵ8,−Bϵ4]⊂(−Bϵ,Bϵ).[p_L-( x ) θ ,p_U-( x ) θ ]= [- 3B_ε8,\,- B_ε4 ]⊂(-B_ε,B_ε). For every p∈[pL,pU]p∈[p_L,p_U], we have p−(∘)⊤∘≥−3Bϵ/8>−Bϵ/2.p-( x ) θ ≥-3B_ε/8>-B_ε/2. Hence, pg¯(p−(∘)⊤∘) p\, g\! (p-( x ) θ ) =pD((∘)⊤∘−Bϵ/2)p =p\, D (( x ) θ -B_ε/2 )p =D((∘)⊤∘−Bϵ2). =D (( x ) θ - B_ε2 ). (73) Thus, the revenue induced by g¯ g is constant on [pL,pU][p_L,p_U]. Step 2: Smoothing the envelope without changing the flat region. The envelope g¯ g is continuous but has a kink at −Bϵ/2-B_ε/2. We smooth this kink over a short interval while preserving monotonicity, remaining below g¯ g, and leaving the flat-revenue region unchanged. Fix a nondecreasing infinitely differentiable function ρ:ℝ→[0,1]ρ:R→[0,1] satisfying ρ(z)=0for z≤0,ρ(z)=1for z≥1,ρ′(z)>0for z∈(0,1).ρ(z)=0 z≤ 0, ρ(z)=1 z≥ 1, ρ (z)>0 z∈(0,1). Choose ζ>0ζ>0 sufficiently small that ζ<Bϵ/64and6Dζ<∫−BϵBϵg¯(u)du−DBϵ.ζ<B_ε/64 6Dζ< _-B_ε^B_ε g(u)\,du-DB_ε. (74) There exists z0∈(−Bϵ/2−2ζ,−Bϵ/2)z_0∈ (-B_ε/2-2ζ,\,-B_ε/2 ) such that ∫−Bϵ/2−2ζ−Bϵ/2+2ζD((∘)⊤∘−Bϵ/2)((∘)⊤∘+v)2ρ(v−z0ζ)dv=D−D((∘)⊤∘−Bϵ/2)(∘)⊤∘−Bϵ/2+2ζ. _-B_ε/2-2ζ^-B_ε/2+2ζ D(( x ) θ -B_ε/2)(( x ) θ +v)^2ρ ( v-z_0ζ )\,dv=D- D(( x ) θ -B_ε/2)( x ) θ -B_ε/2+2ζ. (75) Since (∘)⊤∘≥Bϵ( x ) θ ≥ B_ε, we have (∘)⊤∘−Bϵ/2−2ζ>0,( x ) θ -B_ε/2-2ζ>0, and the denominator above is strictly positive. Indeed, the left-hand side is continuous in z0z_0, whereas the right-hand side equals ∫−Bϵ/2−Bϵ/2+2ζD((∘)⊤∘−Bϵ/2)((∘)⊤∘+v)2dv. _-B_ε/2^-B_ε/2+2ζ D(( x ) θ -B_ε/2)(( x ) θ +v)^2\,dv. When z0=−Bϵ/2−2ζz_0=-B_ε/2-2ζ, we have ρ(v−z0ζ)=1for every v≥−Bϵ2−ζ.ρ ( v-z_0ζ )=1 every v≥- B_ε2-ζ. Hence the left-hand side of (75) is at least ∫−Bϵ/2−ζ−Bϵ/2+2ζD((∘)⊤∘−Bϵ/2)((∘)⊤∘+v)2dv, _-B_ε/2-ζ^-B_ε/2+2ζ D(( x ) θ -B_ε/2)(( x ) θ +v)^2\,dv, which is strictly larger than the right-hand side since the additional integral over [−Bϵ/2−ζ,−Bϵ/2] [-B_ε/2-ζ,-B_ε/2 ] is strictly positive. In contrast, when z0=−Bϵ/2z_0=-B_ε/2, the multiplier is zero for v≤−Bϵ/2v≤-B_ε/2, lies strictly between zero and one for v∈(−Bϵ/2,−Bϵ/2+ζ),v∈ (-B_ε/2,-B_ε/2+ζ ), and equals one for v≥−Bϵ/2+ζv≥-B_ε/2+ζ. Therefore, the left-hand side is strictly smaller than ∫−Bϵ/2−Bϵ/2+2ζD((∘)⊤∘−Bϵ/2)((∘)⊤∘+v)2dv, _-B_ε/2^-B_ε/2+2ζ D(( x ) θ -B_ε/2)(( x ) θ +v)^2\,dv, which is precisely the right-hand side. Applying the intermediate value theorem therefore yields a z0∈(−Bϵ/2−2ζ,−Bϵ/2)z_0∈ (-B_ε/2-2ζ,-B_ε/2 ) for which (75) holds. Define g~(u):=D,u≤−Bϵ/2−2ζ,D−∫−Bϵ/2−2ζuD((∘)⊤∘−Bϵ/2)((∘)⊤∘+v)2ρ(v−z0ζ)dv,−Bϵ/2−2ζ<u<−Bϵ/2+2ζ,D((∘)⊤∘−Bϵ/2)(∘)⊤∘+u,u≥−Bϵ/2+2ζ. g(u):= casesD,&u≤-B_ε/2-2ζ,\\[2.84526pt] D- _-B_ε/2-2ζ^u D(( x ) θ -B_ε/2)(( x ) θ +v)^2ρ ( v-z_0ζ )\,dv,&-B_ε/2-2ζ<u<-B_ε/2+2ζ,\\[11.38109pt] D(( x ) θ -B_ε/2)( x ) θ +u,&u≥-B_ε/2+2ζ. cases The choice of z0z_0 in (75) ensures that the middle piece and the fractional piece of g~ g have the same value at u=−Bϵ/2+2ζu=-B_ε/2+2ζ. At the left junction point, the multiplier involving ρ equals zero on a neighborhood, so the middle piece coincides locally with the constant D. At the right junction point, the multiplier equals one on a neighborhood, and (75) ensures that the middle piece coincides locally with the fractional piece. Therefore, all derivatives match at both junction points, and g~ g is infinitely differentiable on [−Bϵ,Bϵ][-B_ε,B_ε]. We verify the monotonicity and range of g~ g. On the middle interval, we have g~′(u)=−D((∘)⊤∘−Bϵ/2)((∘)⊤∘+u)2ρ(u−z0ζ)≤0. g (u)=- D(( x ) θ -B_ε/2)(( x ) θ +u)^2ρ ( u-z_0ζ )≤ 0. Hence the middle piece is nonincreasing. It starts from D at u=−Bϵ/2−2ζu=-B_ε/2-2ζ and, by (75), ends at D((∘)⊤∘−Bϵ/2)(∘)⊤∘−Bϵ/2+2ζ>0. D(( x ) θ -B_ε/2)( x ) θ -B_ε/2+2ζ>0. (76) Since the left piece is constant at D and the right piece is positive and decreasing, g~ g is nonincreasing on [−Bϵ,Bϵ][-B_ε,B_ε] and satisfies 0≤g~(u)≤D0≤ g(u)≤ D for u∈[−Bϵ,Bϵ]u∈[-B_ε,B_ε]. We next show that g~≤g¯ g≤ g. If u≤−Bϵ/2u≤-B_ε/2, then g¯(u)=D g(u)=D and g~(u)≤D g(u)≤ D, so the desired inequality holds. If u≥−Bϵ/2+2ζu≥-B_ε/2+2ζ, we have g~(u)=g¯(u) g(u)= g(u) by definition. It only remains to consider the case u∈[−Bϵ/2,−Bϵ/2+2ζ]u∈ [-B_ε/2,-B_ε/2+2ζ ]. For every such u, by (76), we have g~(u) g(u) =D((∘)⊤∘−Bϵ/2)(∘)⊤∘−Bϵ/2+2ζ+∫u−Bϵ/2+2ζD((∘)⊤∘−Bϵ/2)((∘)⊤∘+v)2ρ(v−z0ζ)dv = D(( x ) θ -B_ε/2)( x ) θ -B_ε/2+2ζ+ _u^-B_ε/2+2ζ D(( x ) θ -B_ε/2)(( x ) θ +v)^2ρ ( v-z_0ζ )\,dv ≤D((∘)⊤∘−Bϵ/2)(∘)⊤∘−Bϵ/2+2ζ+∫u−Bϵ/2+2ζD((∘)⊤∘−Bϵ/2)((∘)⊤∘+v)2dv ≤ D(( x ) θ -B_ε/2)( x ) θ -B_ε/2+2ζ+ _u^-B_ε/2+2ζ D(( x ) θ -B_ε/2)(( x ) θ +v)^2\,dv =D((∘)⊤∘−Bϵ/2)(∘)⊤∘+u=g¯(u). = D(( x ) θ -B_ε/2)( x ) θ +u= g(u). Consequently, we have 0≤g~(u)≤g¯(u)0≤ g(u)≤ g(u) for u∈[−Bϵ,Bϵ]u∈[-B_ε,B_ε]. Finally, the smoothing modification does not affect the flat-revenue region. Indeed, by (74), −Bϵ2+2ζ<−3Bϵ8=pL−(∘)⊤∘.- B_ε2+2ζ<- 3B_ε8=p_L-( x ) θ . Thus the smoothing interval lies strictly to the left of [pL−(∘)⊤∘,pU−(∘)⊤∘]. [p_L-( x ) θ ,\,p_U-( x ) θ ]. It follows from the definition of g~ g that g~(u)=D((∘)⊤∘−Bϵ/2)(∘)⊤∘+u g(u)= D(( x ) θ -B_ε/2)( x ) θ +u on a neighborhood of [pL−(∘)⊤∘,pU−(∘)⊤∘]. [p_L-( x ) θ ,\,p_U-( x ) θ ]. Hence the smoothing operation leaves the flat-revenue region unchanged. Step 3: Enforcing the zero-mean condition. Although g~ g is smooth and preserves the flat-revenue region, its integral remains larger than DBϵDB_ε. Indeed, g~ g differs from g¯ g only on [−Bϵ/2−2ζ,−Bϵ/2+2ζ], [-B_ε/2-2ζ,\,-B_ε/2+2ζ ], whose length is 4ζ4ζ. Since both functions take values in [0,D][0,D], equations (72) and (74) give ∫−BϵBϵg~(u)du _-B_ε^B_ε g(u)\,du ≥∫−BϵBϵg¯(u)du−4Dζ>DBϵ. ≥ _-B_ε^B_ε g(u)\,du-4Dζ>DB_ε. We therefore remove part of the right tail of g~ g smoothly, while leaving the flat-revenue region unchanged. For every ξ∈[pU−(∘)⊤∘+ζ,Bϵ−2ζ],ξ∈[p_U-( x ) θ +ζ,\,B_ε-2ζ], define gξ(u):=g~(u)[1−ρ(u−ξζ)],u∈[−Bϵ,Bϵ].g_ξ(u):= g(u) [1-ρ ( u-ξζ ) ], u∈[-B_ε,B_ε]. For u≤ξu≤ξ, the multiplicative factor equals one, whereas for u≥ξ+ζu≥ξ+ζ, it equals zero. On the interval (ξ,ξ+ζ)(ξ,ξ+ζ), it decreases smoothly from one to zero. Thus gξg_ξ agrees with g~ g to the left of ξ and vanishes to the right of ξ+ζξ+ζ. Since g~ g is nonnegative and nonincreasing, and since ρ is nondecreasing, gξ′(u)= g_ξ (u)= g~′(u)[1−ρ(u−ξζ)]−g~(u)ζρ′(u−ξζ)≤0. g (u) [1-ρ ( u-ξζ ) ]- g(u)ζρ ( u-ξζ )≤ 0. Hence gξg_ξ is nonincreasing. Moreover, we have 0≤gξ(u)≤g~(u)≤g¯(u).0≤ g_ξ(u)≤ g(u)≤ g(u). Because ξ≥pU−(∘)⊤∘+ζ,ξ≥ p_U-( x ) θ +ζ, the multiplicative factor equals one throughout [pL−(∘)⊤∘,pU−(∘)⊤∘].[p_L-( x ) θ ,\,p_U-( x ) θ ]. Therefore, on this interval, gξ(u)=g~(u)=D((∘)⊤∘−Bϵ/2)(∘)⊤∘+u.g_ξ(u)= g(u)= D(( x ) θ -B_ε/2)( x ) θ +u. In addition, gξ=Dg_ξ=D on a neighborhood of −Bϵ-B_ε and gξ=0g_ξ=0 on a neighborhood of BϵB_ε. For every fixed u, the function gξ(u)g_ξ(u) is continuous and nondecreasing in ξ. Since 0≤gξ(u)≤D0≤ g_ξ(u)≤ D, the dominated convergence theorem implies that ξ⟼∫−BϵBϵgξ(u)duξ _-B_ε^B_εg_ξ(u)\,du is continuous and nondecreasing. At ξ=pU−(∘)⊤∘+ζ,ξ=p_U-( x ) θ +ζ, the function gξg_ξ vanishes for u≥pU−(∘)⊤∘+2ζ.u≥ p_U-( x ) θ +2ζ. Consequently, ∫−BϵBϵgξ(u)du _-B_ε^B_εg_ξ(u)\,du ≤D(Bϵ+pU−(∘)⊤∘+2ζ)=D(3Bϵ4+2ζ)<DBϵ. ≤ D (B_ε+p_U-( x ) θ +2ζ )=D ( 3B_ε4+2ζ )<DB_ε. At ξ=Bϵ−2ζξ=B_ε-2ζ, the functions gξg_ξ and g¯ g may differ only on [−Bϵ2−2ζ,−Bϵ2+2ζ]∪[Bϵ−2ζ,Bϵ], [- B_ε2-2ζ,\,- B_ε2+2ζ ]∪[B_ε-2ζ,B_ε], whose total length is at most 6ζ6ζ. Since both functions take values in [0,D][0,D], equations (72) and (74) imply ∫−BϵBϵgBϵ−2ζ(u)du _-B_ε^B_εg_B_ε-2ζ(u)\,du ≥∫−BϵBϵg¯(u)du−6Dζ>DBϵ. ≥ _-B_ε^B_ε g(u)\,du-6Dζ>DB_ε. Therefore, by continuity, there exists ξ⋆∈[pU−(∘)⊤∘+ζ,Bϵ−2ζ] _ ∈[p_U-( x ) θ +ζ,\,B_ε-2ζ] such that ∫−BϵBϵgξ⋆(u)du=DBϵ. _-B_ε^B_εg_ _ (u)\,du=DB_ε. Step 4: Verifying the baseline properties and constructing the compensation function. We now set g0=gξ⋆g_0=g_ _ . We first verify that g0g_0 corresponds to an admissible zero-mean noise distribution and generates the desired flat globally optimal revenue region. We then construct χ, which will be used to preserve the zero-mean condition in the subsequent perturbation construction. Set g0=gξ⋆g_0=g_ _ on [−Bϵ,Bϵ][-B_ε,B_ε], and extend it to ℝR by g0(u)=Dg_0(u)=D for u≤−Bϵu≤-B_ε, and g0(u)=0g_0(u)=0 for u≥Bϵu≥ B_ε. Because gξ⋆g_ _ is constant on neighborhoods of both endpoints, this extension is infinitely differentiable on ℝR. In particular, g0∈ℋ(β)g_0 (β) on [−B,B][-B,B], with a finite Hölder constant. The function g0/Dg_0/D is continuous, nonincreasing, equals one to the left of −Bϵ-B_ε, and equals zero to the right of BϵB_ε. It is therefore the survival function of a continuous distribution supported on [−Bϵ,Bϵ][-B_ε,B_ε]. Moreover, by the choice of ξ⋆ _ in Step 3, [ϵt] [ _t] =∫−BϵBϵg0(u)Ddu−Bϵ=0. = _-B_ε^B_ε g_0(u)D\,du-B_ε=0. We next verify the revenue properties. If p−(∘)⊤∘∈[−Bϵ,Bϵ]p-( x ) θ ∈[-B_ε,B_ε] and p>0p>0, then g0≤g¯g_0≤ g, and hence pg0(p−(∘)⊤∘) p\,g_0(p-( x ) θ ) ≤pminD,D((∘)⊤∘−Bϵ/2)p≤D((∘)⊤∘−Bϵ2). ≤ p \D,\, D(( x ) θ -B_ε/2)p \≤ D (( x ) θ - B_ε2 ). If p=0p=0, the same inequality is immediate. If p−(∘)⊤∘≤−Bϵp-( x ) θ ≤-B_ε, then g0(p−(∘)⊤∘)=Dg_0(p-( x ) θ )=D and pg0(p−(∘)⊤∘)=Dp≤D((∘)⊤∘−Bϵ)<D((∘)⊤∘−Bϵ2).p\,g_0(p-( x ) θ )=Dp≤ D(( x ) θ -B_ε)<D (( x ) θ - B_ε2 ). If p−(∘)⊤∘≥Bϵp-( x ) θ ≥ B_ε, then g0(p−(∘)⊤∘)=0g_0(p-( x ) θ )=0. This proves the inequality in (20). For every p∈[pL,pU]p∈[p_L,p_U], Step 3 gives g0(p−(∘)⊤∘)=D((∘)⊤∘−Bϵ/2)p.g_0(p-( x ) θ )= D(( x ) θ -B_ε/2)p. Therefore, pg0(p−(∘)⊤∘)=D((∘)⊤∘−Bϵ2),p∈[pL,pU],p\,g_0 (p-( x ) θ )=D (( x ) θ - B_ε2 ), p∈[p_L,p_U], which proves the equality in (20). Furthermore, for every p∈[pL,pU]p∈[p_L,p_U], 0<D((∘)⊤∘−Bϵ/2)pU≤g0(p−(∘)⊤∘)≤D((∘)⊤∘−Bϵ/2)pL<D.0< D(( x ) θ -B_ε/2)p_U≤ g_0(p-( x ) θ )≤ D(( x ) θ -B_ε/2)p_L<D. Because the same representation holds on a neighborhood of [pL−(∘)⊤∘,pU−(∘)⊤∘],[p_L-( x ) θ ,\,p_U-( x ) θ ], the function g0g_0 is bounded away from both 0 and D, and g0′(u)=−D((∘)⊤∘−Bϵ/2)((∘)⊤∘+u)2<0g_0 (u)=- D(( x ) θ -B_ε/2)(( x ) θ +u)^2<0 throughout that neighborhood. It remains to construct the compensation function. Define χ(u):=2ζρ′(2(u−ξ⋆)ζ−12).χ(u):= 2ζρ ( 2(u- _ )ζ- 12 ). Since ρ′≥0ρ ≥ 0, we have χ(u)≥0.χ(u)≥ 0. By the definition of χ, ∫ℝχ(u)du=∫ℝ2ζρ′(2(u−ξ⋆)ζ−12)du=[ρ(2(u−ξ⋆)ζ−12)]u=−∞u=∞=1−0=1. _Rχ(u)\,du= _R 2ζρ ( 2(u- _ )ζ- 12 )\,du= [ρ ( 2(u- _ )ζ- 12 ) ]_u=-∞^u=∞=1-0=1. Moreover, since ρ′ρ vanishes outside (0,1)(0,1), by the choice of ξ⋆ _ in Step 3 supp(χ)⊂[ξ⋆+ζ4,ξ⋆+3ζ4]⊂(−Bϵ,Bϵ)∖[pL−(∘)⊤∘,pU−(∘)⊤∘].supp(χ)⊂ [ _ + ζ4,\, _ + 3ζ4 ]⊂(-B_ε,B_ε) [p_L-( x ) θ ,p_U-( x ) θ ]. On a sufficiently small neighborhood of supp(χ)supp(χ), the factor 1−ρ(u−ξ⋆ζ)1-ρ ( u- _ ζ ) is bounded away from both zero and one. Since g~ g is also bounded away from both zero and D there, the same holds for g0g_0. Finally, g0′(u)= g_0 (u)= g~′(u)[1−ρ(u−ξ⋆ζ)]−g~(u)ζρ′(u−ξ⋆ζ)<0, g (u) [1-ρ ( u- _ ζ ) ]- g(u)ζρ ( u- _ ζ )<0, because g~′(u)<0 g (u)<0, g~(u)>0 g(u)>0, and ρ′≥0ρ ≥ 0 there. Since g0′g_0 is continuous, it is uniformly negative on a sufficiently small closed neighborhood of supp(χ)supp(χ). □ Proof of Theorem 5.6. Proof. Step 1: Constructing the perturbed instances. Let g0,pL,pUg_0,p_L,p_U, and χ be as in Lemma 5.8. Set KT:=⌈T1/(2β+1)⌉K_T:= T^1/(2β+1) and, for every k∈[KT]k∈[K_T], define p¯k:=pL+(k−12)pU−pLKT. p_k:=p_L+ (k- 12 ) p_U-p_LK_T. Thus, p¯1,…,p¯KT p_1,…, p_K_T are equally spaced in [pL,pU][p_L,p_U]. For brevity, write uk:=p¯k−(∘)⊤∘.u_k:= p_k-( x ) θ . Choose a sufficiently small constant κ>0κ>0, depending only on the fixed problem primitives. For every k∈[KT]k∈[K_T], define Δk(u):=κKT−β((∘)⊤∘+u)ρ′(1/2)ρ′(4KT(u−uk)pU−pL+12),|u−uk|<pU−pL8KT,0,otherwise, _k(u):= cases κ K_T^-β (( x ) θ +u )ρ (1/2)ρ ( 4K_T(u-u_k)p_U-p_L+ 12 ),& |u-u_k|< p_U-p_L8K_T,\\[14.22636pt] 0,& otherwise, cases (77) and gk(u):=g0(u)+Δk(u)−χ(u)∫ℝΔk(v)dv.g_k(u):=g_0(u)+ _k(u)-χ(u) _R _k(v)\,dv. (78) The term Δk _k creates a local revenue increase near p¯k p_k, while the term involving χ removes the same total mass away from this region. Because ρ′(1/2)>0ρ (1/2)>0, Δk _k is well defined and nonnegative. Moreover, supp(Δk)⊂[p¯k−(∘)⊤∘−pU−pL8KT,p¯k−(∘)⊤∘+pU−pL8KT].supp( _k)⊂ [ p_k-( x ) θ - p_U-p_L8K_T,\, p_k-( x ) θ + p_U-p_L8K_T ]. These supports are pairwise disjoint and contained in [pL−(∘)⊤∘,pU−(∘)⊤∘].[p_L-( x ) θ ,\,p_U-( x ) θ ]. Since (∘)⊤∘+u≥pL>0( x ) θ +u≥ p_L>0 on their union, the height of Δk _k is of order KT−βK_T^-β, while the length of its support is of order KT−1K_T^-1. Hence 0≤∫ℝΔk(u)du≤ClbκKT−(β+1)0≤ _R _k(u)\,du≤ C_lbκ K_T^-(β+1) (79) uniformly in k and T, where Clb<∞C_lb<∞ denotes a constant that may change from line to line. Because ρ is infinitely differentiable and constant outside [0,1][0,1], all derivatives of ρ′ρ vanish at zero and one. Therefore, the piecewise-defined function Δk _k is infinitely differentiable on ℝR. Since the supports of Δk _k and χ lie in (−Bϵ,Bϵ)(-B_ε,B_ε), and ∫ℝχ(u)du=1 _Rχ(u)\,du=1, ∫−BϵBϵgk(u)du=∫−BϵBϵg0(u)du+∫ℝΔk(u)du−(∫ℝχ(u)du)(∫ℝΔk(u)du)=DBϵ. _-B_ε^B_εg_k(u)\,du= _-B_ε^B_εg_0(u)\,du+ _R _k(u)\,du- ( _Rχ(u)\,du ) ( _R _k(u)\,du )=DB_ε. Thus, gkg_k and g0g_0 have the same integral on [−Bϵ,Bϵ][-B_ε,B_ε]. We first verify that the constructed functions satisfy the required smoothness condition. By enlarging ClbC_lb, if necessary, repeated application of the product and chain rules gives supu∈ℝ|Δk(r)(u)|≤ClbκKTr−β,r=0,1,…,ϖ(β)+1. _u | _k^(r)(u) |≤ C_lbκ K_T^r-β, r=0,1,…, (β)+1. (80) We now verify the Hölder condition. Fix u,u′∈ℝu,u . If |u−u′|≤KT−1,|u-u |≤ K_T^-1, the mean-value theorem gives |Δk(ϖ(β))(u)−Δk(ϖ(β))(u′)| | _k^( (β))(u)- _k^( (β))(u ) | ≤ClbκKTϖ(β)+1−β|u−u′| ≤ C_lbκ K_T (β)+1-β|u-u | =Clbκ|u−u′|β−ϖ(β)(KT|u−u′|)ϖ(β)+1−β =C_lbκ|u-u |^β- (β) (K_T|u-u | ) (β)+1-β ≤Clbκ|u−u′|β−ϖ(β). ≤ C_lbκ|u-u |^β- (β). If |u−u′|>KT−1,|u-u |>K_T^-1, then |Δk(ϖ(β))(u)−Δk(ϖ(β))(u′)| | _k^( (β))(u)- _k^( (β))(u ) | ≤2supv∈ℝ|Δk(ϖ(β))(v)|≤ClbκKTϖ(β)−β≤Clbκ|u−u′|β−ϖ(β). ≤ 2 _v | _k^( (β))(v) |≤ C_lbκ K_T (β)-β≤ C_lbκ|u-u |^β- (β). Therefore, we have |Δk(ϖ(β))(u)−Δk(ϖ(β))(u′)|≤Clbκ|u−u′|β−ϖ(β). | _k^( (β))(u)- _k^( (β))(u ) |≤ C_lbκ|u-u |^β- (β). (81) By Lemma 5.8, g0g_0 satisfies the required Hölder condition. Moreover, χ is fixed and infinitely differentiable, while (79) uniformly bounds the coefficient multiplying χ. Combining these facts with (81), there exists a finite constant L¯g L_g, independent of k and T, such that gk∈ℋ(β,L¯g;[−B,B])g_k (β, L_g;[-B,B]) for every k∈[KT]k∈[K_T]. We next verify the range and monotonicity requirements. The supports of Δk _k and χ are disjoint. By Lemma 5.8, g0g_0 is bounded away from both 0 and D, and g0′g_0 is uniformly negative, on neighborhoods of these supports. By enlarging ClbC_lb, if necessary, (80) and (79) imply ‖Δk‖∞+‖Δk′‖∞+‖χ(⋅)∫ℝΔk(v)dv‖∞+‖χ′(⋅)∫ℝΔk(v)dv‖∞≤Clbκ. \| _k\|_∞+\| _k \|_∞+ \|χ(·) _R _k(v)\,dv \|_∞+ \|χ (·) _R _k(v)\,dv \|_∞≤ C_lbκ. On supp(Δk)supp( _k), gk=g0+Δk,g_k=g_0+ _k, whereas on supp(χ)supp(χ), gk=g0−χ(⋅)∫ℝΔk(v)dv.g_k=g_0-χ(·) _R _k(v)\,dv. Outside these two supports, gk=g0g_k=g_0. Combining these observations with the preceding bounds, for all sufficiently small κ>0κ>0, uniformly in k and T, 0≤gk(u)≤D0≤ g_k(u)≤ D and gk′(u)≤0g_k (u)≤ 0 for u∈ℝu . Since the supports of Δk _k and χ lie strictly inside (−Bϵ,Bϵ)(-B_ε,B_ε), gk(u)=Dg_k(u)=D for u≤−Bϵu≤-B_ε and gk(u)=0g_k(u)=0 for u≥Bϵu≥ B_ε. Therefore, gk/Dg_k/D is the survival function of a distribution supported on [−Bϵ,Bϵ][-B_ε,B_ε]. Moreover, the preceding integral identity gives [ϵt] [ _t] =∫−BϵBϵgk(u)Ddu−Bϵ=0. = _-B_ε^B_ε g_k(u)D\,du-B_ε=0. Under instance k, the shocks are i.i.d. with the constructed distribution and are independent of the policy randomization. Moreover, because yt=Dvt≥pty_t=D1\v_t≥ p_t\, the demand is measurable with respect to σ(pt,vt)σ(p_t,v_t). Therefore, [yt|ℱt−1∨σ(t,pt,vt)]=Dvt≥pt=q(vt−pt). \! [y_t\, |\,F_t-1 σ( x_t,p_t,v_t) ]=D1\v_t≥ p_t\=q(v_t-p_t). Hence, Assumption 3.2 holds. Furthermore, by (17), for every u∈ℐgu _g, [q(ϵt−u)]=Dℙ(ϵt≥u)=gk(u).E[q( _t-u)]=DP( _t≥ u)=g_k(u). Thus, each constructed instance satisfies the original model assumptions provided that Lg≥L¯gL_g≥ L_g. Step 2: Establishing the revenue gap and statistical closeness. Under instance k, the perturbation raises the revenue near p¯k p_k, while prices outside its support receive no such increase. Since the support of χ is disjoint from [pL−(∘)⊤∘,pU−(∘)⊤∘],[p_L-( x ) θ ,\,p_U-( x ) θ ], the definition of Δk _k gives p¯kgk(p¯k−(∘)⊤∘)=D((∘)⊤∘−Bϵ2)+κKT−β. p_kg_k ( p_k-( x ) θ )=D (( x ) θ - B_ε2 )+κ K_T^-β. If p−(∘)⊤∘∉supp(Δk),p-( x ) θ ( _k), then Δk=0 _k=0. Since the term involving χ is nonpositive, pgk(p−(∘)⊤∘)≤pg0(p−(∘)⊤∘)≤D((∘)⊤∘−Bϵ2).p\,g_k (p-( x ) θ )≤ p\,g_0 (p-( x ) θ )≤ D (( x ) θ - B_ε2 ). Consequently, maxp′∈[0,B]p′gk(p′−(∘)⊤∘)−pgk(p−(∘)⊤∘)≥κKT−β,p−(∘)⊤∘∉supp(Δk). _p ∈[0,B]p \,g_k (p -( x ) θ )-p\,g_k (p-( x ) θ )≥κ K_T^-β, p-( x ) θ ( _k). (82) Fix an arbitrary nonanticipating policy π. Let ℙkP_k denote the law of the complete observed history, including posted prices and demands, under instance k, and let ℙ0P_0 denote the corresponding law under the baseline instance g0g_0. Conditional on the past and ptp_t, the normalized observation yt/Dy_t/D is Bernoulli with success probability gk(pt−(∘)⊤∘)/Dg_k (p_t-( x ) θ )/D. Since the policy uses the same conditional decision rule under every instance, the chain rule for relative entropy gives DKL(ℙ0∥ℙk)=ℙ0[∑t=1TDKL(Bern(g0(pt−(∘)⊤∘)D)∥Bern(gk(pt−(∘)⊤∘)D))]. D_KL (P_0\, \|\,P_k )=E_P_0 [ _t=1^TD_KL (Bern ( g_0 (p_t-( x ) θ )D )\, \|\,Bern ( g_k (p_t-( x ) θ )D ) ) ]. (83) By the properties established in Step 1, the relevant Bernoulli probabilities on the supports of Δk _k and χ lie in a fixed subinterval of (0,1)(0,1). By enlarging ClbC_lb, if necessary, DKL(Bern(a)∥Bern(b))≤Clb(a−b)2D_KL (Bern(a)\, \|\,Bern(b) )≤ C_lb(a-b)^2 for all probabilities appearing above. Moreover, |gk(p−(∘)⊤∘)−g0(p−(∘)⊤∘)| |g_k (p-( x ) θ )-g_0 (p-( x ) θ ) | ≤ClbκKT−βp−(∘)⊤∘∈supp(Δk) ≤ C_lbκ K_T^-β1 \p-( x ) θ ( _k) \ +ClbκKT−(β+1)p−(∘)⊤∘∈supp(χ). +C_lbκ K_T^-(β+1)1 \p-( x ) θ (χ) \. Using (80) with r=0r=0 and (79), and enlarging ClbC_lb if necessary, we obtain DKL(ℙ0∥ℙk)≤Clbκ2KT−2β0[∑t=1Tpt−(∘)⊤∘∈supp(Δk)]+Clbκ2KT−2β−2T. D_KL (P_0\, \|\,P_k )≤ C_lbκ^2K_T^-2βE_0 [ _t=1^T1 \p_t-( x ) θ ( _k) \ ]+C_lbκ^2K_T^-2β-2T. (84) Because the supports of Δ1,…,ΔKT _1,…, _K_T are pairwise disjoint, ∑k=1KT∑t=1Tpt−(∘)⊤∘∈supp(Δk)≤T _k=1^K_T _t=1^T1 \p_t-( x ) θ ( _k) \≤ T pathwise. Hence there exists k⋆∈[KT]k ∈[K_T] such that 0[∑t=1Tpt−(∘)⊤∘∈supp(Δk⋆)]≤TKT.E_0 [ _t=1^T1 \p_t-( x ) θ ( _k ) \ ]≤ TK_T. For this k⋆k , we have DKL(ℙ0∥ℙk⋆) D_KL (P_0\, \|\,P_k ) ≤Clbκ2TKT−(2β+1)+Clbκ2TKT−(2β+2). ≤ C_lbκ^2TK_T^-(2β+1)+C_lbκ^2TK_T^-(2β+2). Since KT≥1K_T≥ 1, by enlarging ClbC_lb, if necessary, we have DKL(ℙ0∥ℙk⋆)≤Clbκ2TKT−(2β+1).D_KL (P_0\, \|\,P_k )≤ C_lbκ^2TK_T^-(2β+1). (85) Step 3: Deriving the regret lower bound. The KL bound in Step 2 shows that instance k⋆k is difficult to distinguish from the baseline. We now use this fact to show that the policy misses the corresponding perturbation region sufficiently often. Under instance k⋆k , (82) gives Reg(T)≥κKT−β∑t=1Tpt−(∘)⊤∘∉supp(Δk⋆).Reg(T)≥κ K_T^-β _t=1^T1 \p_t-( x ) θ ( _k ) \. (86) For every t, apply the Bretagnolle–Huber inequality to the event pt−(∘)⊤∘∈supp(Δk⋆). \p_t-( x ) θ ( _k ) \. Summing over t gives 0[∑t=1Tpt−(∘)⊤∘∈supp(Δk⋆)]+k⋆[∑t=1Tpt−(∘)⊤∘∉supp(Δk⋆)] _0 [ _t=1^T1 \p_t-( x ) θ ( _k ) \ ]+E_k [ _t=1^T1 \p_t-( x ) θ ( _k ) \ ] ≥T2exp−DKL(ℙ0∥ℙk⋆). ≥ T2 \-D_KL (P_0\, \|\,P_k ) \. (87) By the definition of KTK_T, we have TKT−(2β+1)≤1.TK_T^-(2β+1)≤ 1. By further decreasing κ, if necessary, assume that Clbκ2≤log2.C_lbκ^2≤ 2. This choice preserves all the range, monotonicity, and smoothness properties established above. Equation (85) then implies DKL(ℙ0∥ℙk⋆)≤log2.D_KL (P_0\, \|\,P_k )≤ 2. Increasing T0T_0, if necessary, also guarantees KT≥8K_T≥ 8. Consequently, 0[∑t=1Tpt−(∘)⊤∘∈supp(Δk⋆)]≤TKT≤T8.E_0 [ _t=1^T1 \p_t-( x ) θ ( _k ) \ ]≤ TK_T≤ T8. Combining this bound with (87) gives k⋆[∑t=1Tpt−(∘)⊤∘∉supp(Δk⋆)]≥T4−T8=T8. _k [ _t=1^T1 \p_t-( x ) θ ( _k ) \ ]≥ T4- T8= T8. Taking k⋆E_k on both sides of (86) therefore yields k⋆[Reg(T)]≥κ8TKT−β.E_k [Reg(T)]≥ κ8TK_T^-β. Finally, since KT≤2T1/(2β+1),K_T≤ 2T^1/(2β+1), we obtain k⋆[Reg(T)]≥κ2β+3Tβ+12β+1.E_k [Reg(T)]≥ κ2^β+3T β+12β+1. The policy π was arbitrary. Taking the infimum over policies and the supremum over admissible instances completes the proof. □